总起

本文继承前面的工作，对于分析历史数据进行网络视频QoE最优化这一大类问题，使用增强学习中EE的概念，期望在增加模型准确率的同时，保证实时性。

背景

Data-Driven QoE最优化问题

是指通过分析已有数据，提取特征和规律，来最优化当前session的QoE的问题。是一大类问题。
对已有数据的分析一般是使用统计分析手段与机器学习等方式
其中，此前研究中所用的方法，一般如下图：

• 训练部分通过无监督学习的方式，从历史数据中提取特征，得到决策模型。这部分需要大量的、全面的数据，所以设计成集中式的，并且由于计算复杂度高，间隔较长周期才会重新计算一次。
• 预测部分则使用学习好的决策模型进行预测。这部分开销较低，可以实现为分布式的实时预测。

之前方法的弊端

本文主要提出两个方面的局限性：

1. 预测偏差
   预测模型使用的是陈旧的数据，因此模型可能预测得不准，尤其是预测值方差很大的时候。
   并且收集数据和预测是分开的，预测的反馈不能马上告诉训练部分

2. 反应缓慢
   一个是，对于突发事件没法反应。
   另一个是，当当前决策模型做出的决策引发问题时，也没法马上对这个问题进行处理

EE

参考地址：
http://blog.csdn.net/coffee_cream/article/details/57085729

EE是增强学习里的重要概念。机器学习可分为三类：有监督学习、无监督学习、增强学习

其中增强学习与前两种的重要区别在于：

延迟反馈：其实相当于前两者的误差函数是已知的，而增强学习里是未知的。

就是说，对于前两者来说，哪怕我现在还没有输出结果，我也能知道假如我输出这个结果我会有多少误差。
而在增强学习里，我只有输出一个结果，然后别人给我一个误差反馈，我才能使用这个反馈进行下一步学习，我也不知道这个反馈有什么规律，甚至可能这个反馈规律还会随时间的变化而变化，还会被历史的输出结果影响。

因此增强学习的学习成果与前两者也是不同的，比如1+1=2，前两者学习完毕后，再问1+1等于几，会回答等于2。而增强学习学习完毕后，会告诉你：2最不容易出错，3有可能出错，其他没试过，不知道，假设一定会出错。
增强学习更适用于一种交互的环境中，比如下棋等。
增强学习中采用的是边获取样例边学习的方式，像一种试错过程。EE指的是Exploration-探索和Exploitation-开发。

探索：我还没做过这个决定，我决定冒险试试看，看有什么样的结果。
开发：我大概确定这片区域会有好结果，我决定在这片区域各处绕绕，看哪里最好
不探索可能只找到局部最优值，不开发可能只能找到次优值，它们之间需要折衷权衡

多杆老虎机问题

http://blog.csdn.net/coffee_cream/article/details/58034628

Multi-armed bandit原本是从赌场中的多臂老虎机的场景中提取出来的数学模型，其arm// 指的是老虎机（slot machine）的拉杆，bandit// 是多个拉杆的集合，bandit=arm1,arm2,……,armk// 。每个 bandit setting 对应一个回报函数（reward function），现在需要经过多次的尝试，来评估每个 bandit// 的reward// ，这个问题的目标是如何最大化总的回报。
这个问题重点在于评估每个老虎机的reward。因为只要评估完之后，选择最大的那几个就好了。
问题是怎么学习和评估呢？

在本文里，“时刻t要拉哪台老虎机”=“多个候选决策中选哪个”=“怎么学”，“每个老虎机的reward”=“选每个决策时得到的QoE”=“评估结果”

UCB算法

UCB是一种学习的方式，当然还有其它方式。
选择规则：

前半部分是value越大越容易被选中，为开发
后半部分N指的是t次里a被选了多少次，被选次数越少越容易被选，是探索

本文工作

本文主要工作是想把EE放到Data-driven里以改善上文所说的缺陷
但是“多杆老虎机问题”的学习成果能够指导下一个人选择拉杆是因为这几台老虎机是相同的老虎机
而对于QoE问题来说，不同的session，其QoE的影响因素等都不同，因此无法直接使用EE

按关键特征分组

每组里的“老虎机”是相似的，可以用EE来指导决策。

首先，要识别关键特征

会话s的关键特征集F*是使得：

1. 与s在F*上相同的session数足够多
2. 与s在F*上相同的session们只考虑关键特征得到的QoE与考虑全部特征得到的QoE是最接近的（比其它特征集合都近）

然后分组

1. 不能重叠
2. 同一组内，除直接决定决策的特征外的其他特征应相同

分析刚好发现，同一组的session倾向于被分到相同的前端cluster中：大概意思就是同一组的session倾向于在同一个AS中，因此很容易就被分到一个前端cluster。

Discout UCB

本文所使用的学习方式是Discout UCB，就是和的第一项里的Q被指数地减小了

系统架构

事实上还是分成集中式和分布式两部分：

1. 前端采用分布式，边训练边决策，由于同一组的session可能被分到不同的前端上，在这同一组的多个前端里，会确定一个leader。

   两种方式：

   1. 不是leader的cluster只等着leader给决策，leader只能看到它自己看到的session
   2. 不是leader的cluster会向leader发送信息，leader看到的是整个组的session

2. 后端采用集中式，收集全局数据，维护session到组的映射，并确定每个组的leader cluster

容错

1. 前端fail
   • leader挂掉：leader定期向后端报告自己存活，一旦不存活，后端马上换一个leader
   • 非leader挂掉：回退到本地选择策略
2. 后端fail
   等待后端修复即可，只是组不再更新，但不会影响使用