Reinforcement Learning： An Intro Ch02 - Multi-armed Bandits

  多臂老虎机问题的名字取得非常有特色，一开始我也没懂为什么转老虎机的把手会和不确定状态下的决策问题联系起来。为了理解这样的一个问题，我们不妨从一个更泛化但贴合生活的例子说起。这个例子来自Coursera上Reinforcement Learning Specialization。

  首先我们有一个决策者 (decision maker)，或者我们叫它个体 (agent)。作为一名医生，这个个体需要给病人开药治病。现在它的行动是选择其中一种药物来治疗病人，这里的k=3；它面前有三种药物: 粉、黄、蓝，而它的反馈是病人吃药后病情是否好转。这种反馈在病人吃药前都是未知的，所以该个体需要有一个预期反馈 (expected reward)——这很合理，因为医生也不能给病人胡乱喂药。既然有了预期反馈，那么我们就能够最终靠这个预期反馈来评估我们的行动了。为了评估医生采用哪种药物更好，我们大家可以把每个行动值 (action value)用概率的形式定义为

  为了更好地理解这个公式，我们不妨简化上面医生选药的例子。我们把用药后可能获得的反馈理解为血压变化，并且变化符合特定的概率分布，那么计算q_{*}(a)就变得简单起来。

  以上是我们大家都知道每个行动所对应的价值的情况下，但是现实中并不总能知道个体行动的好坏，所以解决这一个问题的方法就变成了根据样本平均值 (sample average) 的估值，这一系列用以对行动估值的方法称之为行动估值方法 (action-value method)。对于未知的q_* (a)，其在时间段t前的估计值记作Q_t(a)：

  其中I_{predicate}表示如果选择的行动为a那么predicate即为1，如果选择的行动不为a，那么就设置为0；这个公式可以被写成t-1的形式，而之所以是t-1是因为我们计算的是在时间段t之前的累积反馈。

  如果我们回到上文的医生开药的例子，假设我们知道真实的q_*(a)，分别为粉药0.25，黄药为0.75，蓝药为0.5；而医生只能通过Q_t(a)去估算哪种药的疗效更好，那么我们设置反馈 (reward) 有疗效为1，无疗效为0，就会得到：

  在得到Q_t(a)之后，我们采取的最简单的规则便是选择最大的Q_t(a)，即

  这种策略也被叫做贪婪行动选择 (greedy action selection)，它背后的核心便是选择当前最好的反馈，因为我们不知道真正最好的反馈是什么，但是真正最好的反馈一定包含在当前最好的反馈这一集合当中。

  贪婪行动策略的缺点也非常明显，因为总是选择当前最优意味着不能遍历全部的可能性，所以不能确保得到真实最优，所以它的替代方法便是在经过一段贪婪选择的时间之后，根据一个小概率\epsilon进行一次随机的行动选择。这种方法被称作\epsilon-greedy 方法。这种方法的优点便是可以确保所有的Q_t(a)都对q_*(a)收敛 (converge)，算法选择真正最优行动 (optimal action) 的概率为1-\epsilon，这大大提升了算法的准确性，但是也提升了时间复杂度 (time complexity)和空间复杂度 (space complexity)。平衡探索和拓展 (exploration and exploitation) 一直都是强化学习中的核心问题。

  既然我们知道了可以用Q_t (a)去趋近真实的q_*(a)需要耗费大量内存，那么我们可否改进该算法，让其处于一个可以接受的时间-空间复杂度内呢？改进该算法需要用到算法设计 (algorithm design) 中的动态规划 (dynamic programming) 的思想，通过这种方式我们可以把计算过程控制在常数复杂度 (constant) 之内。

  首先，让我们用R_i表示第i次行动的反馈，用Q_n表示第n-1次选择该行动的估值，那么我们就有了一种朴素方法 (naïve approach)：

  该公式和上文t-1是完全一致的；在执行该计算的时候，它所需要的时间-空间复杂度会随着R_i的增长而增长。

  现在，我们要用动态规划的思想去改进它，让这个算法不需要去记录R_i的值，这里需要用到增量公式 (incremental formulas)，即计算下一步Q_{n+1}的值：

  这样，我们就只需要记录Q_n和n的值并把它们带入最后推导出的公式中计算就行。这个规则在强化学习中非常常见，被称之为更新规则 (update rule)。它的一般形式为

  其中，[目标 - 旧估值]可以被理解为误差值 (error)，它会随着步幅 (step size) 朝目标R_n减小；步幅 (step size)则可以理解为机器学习中常见的学习率 (learning rate)，即处理行动a在被选择第n次时的函数，所以在本书中也被写作\alpha_t(a)。

  我们有了\epsilon-greedy 策略去选择行动，也有了增量公式计算该选择所获得的反馈，于是就有了简单老虎机算法 (simple bandit algorithm) ：

  简单老虎机算法可以解决稳态问题 (stationary problem)，即所获得的反馈概率 (reward probability) 分布平稳， 不会随着时间而改变。 然而，我们通常需要处理的问题都是非稳态的，所以我们需要调整算法的步幅来适应反馈概率的变化。

  有一个非常直观的改进算法的点子就是，我们可以通过给予最先获得的反馈一定的权重 (weight)，而随后获得的反馈会比上一步获得的反馈更大的权重。这样当前的反馈的对于行动估值的影响会比之前获得的反馈要大。

  对于一般形式的增量公式，我们先对最先获得的行动的估值Q_1给予权重，那么该公式可以改写成：

  是一种加权平均 (weighted average)，控制了目标反馈R_i获得的权重依次衰减。对于最早的估值Q_1的权重(1-\alpha) 1，这样时间越长，后续的反馈越多，该估值对最终结果的影响也越小。

  强化学习中权衡探索与拓展是一个大问题，多臂老虎机就是这样的一个问题很好的体现。

  个体 (agent) 在未来获得反馈的能力取决于它对行动 (拉动扳手) 的理解。因此，它必须探索行动的可能性，以了解它们并提高其获得未来正反馈的机会。但个体也必须利用它已经知道的东西，以使其总反馈最大化；因此，它必须通过拉动给予它最大正反馈的扳手来拓展它的总反馈。

  在上文部分，我们使用行动估值方法 (action-value methods)去定义探索与拓展。

  我们可以通过比较贪婪行动选择策略和\epsilon-greedy 策略的结果来说明权衡的困难：

  贪婪行动策略便是尽可能地去拓展正反馈，从上图可以看出这种策略在运行次数少的情况下表现得更好。这就说明如果一直选取当下最优解的拓展确实可以比探索在一定时间段内获得更好的总正反馈。但是当运行次数多了以后，\epsilon-greedy的探索显然要比拓展好得多。

  从上图不同的\epsilon的比较可以看出，0.1的结果显然比0.01更好。其原因是因为0.01太小了，0.01的个体显然不能探索足够多的可能性，这样它会持续陷入某种局部最优解 (suboptimal solution) 之中。

  相反作为贪婪策略的0.0却取得了比0.4更好的结果，这是因为0.4的个体探索了过多的局部最优解，在很多时候它都尝试过非最优的行动，这个过程显然花费了相当长的时间。

  运行次数在权衡过程也扮演了相当重要的角色，我们可以通过比较\frac{1}{n}和0.1来说明这一点：

  从上图可以看出，在1000次运行之前，\frac{1}{n}的表现显然优于0.1，但是大概在1100次之后，0.1的个体的表现便超过了\frac{1}{n}，甚至还有逐渐拉大差距的趋势。

  以上都是我们在强化学习中必须考虑的权衡类型。较大的步幅可以使我们更迅速地接近真实值，但会使我们的估算值 (estimated value) 在预期值 (expected value) 周围振荡；而随着时间推移而减小的步幅却可以收敛到接近预期值，并不会出现振荡，但是这种衰减的步幅并不能适应环境的变化。非稳态性——以及相关的可被部分观察的概念——一直都是强化学习和在线学习 (online learning)的一个共同特征。

  以上所有方法都依赖于初始值Q_1，这在统计学上叫做偏差值 (bias)。这种偏差值在样本平均值 (sample average) 的方法中会在所有行动都被选择了至少一次后消失，但是当\alpha为常数的时候，这种偏差值是永久存在于计算中的。偏差值的存在在实践中并不被视作为一个必须被解决的问题，但是它的缺点是需要我们自己去选择设置什么是合适的偏差值，而它的优点是如果我们自己是成熟老练的炼丹师，那么它提供了对于可能得到的反馈的预期。

  初始化行动值也鼓励个体去拓展。假设我们测试一个10臂老虎机问题，将Q_1(a) = 5带入计算中，与\epsilon-greedy 中的Q_1(a) = 0作比较：

  可以看出初始化行动值的方法有更好的表现。这种方法被称之为极大化初始值 (Optimistic Initial Values) 方法。这种方法的核心便是将初始值设置为一个任何反馈都不可能达到的极大值，这样它不管如何尝试探索都会得到比Q_1小的反馈，所以会探索更多行动，表现相对差；但是在多次尝试后，总是选择贪婪策略的个体便能更高效地拓展，并最终更快地收敛。

  极大化初始值方法在处理稳态问题时会有更好的表现，但并不适用于非稳态问题，因为非稳态问题中所获得的反馈的概率是会发生变化的。

  权衡探索与拓展的方法中都需要面临不确定性 (uncertainty) 的问题，假设我们大家都知道全部信息或者探索完毕的话，那么算法只需要不断拓展带来最大正反馈的行动即可。消除不确定性也是解决权衡问题的选项之一。

  如果估计值的信心区间大，那么说明它的不确定性大；相反，如果它的信心区间小，那么说明它的不确定性小。个体需要选择的当然是更有潜力的Q(a)，即更大上界，因为有可能带来更大的正反馈。

  如上图的情况，Q(1)更有可能得到更大的正反馈，所以个体会选择Q(1)，即上界最大的估计值；但同时选择Q(1)也有可能带来最小的正反馈。

  如果N_t(a) = 0，那么行动a可以被视作为能最大化正反馈的行动。每次当a被选择的时候，作为分母 (denominator) 的N_t (a)会增大，但UCB不确定性项会减少；而每次当并非a的行动被选择时，作为分子 (numerator) 的t会增大，但N_t (a)会减小。这里自然对数的作用是使得增幅跟着时间而变小，最终所有的行动都会被选中，而估计值较低的行动和被选过的行动再次被选中的频率也会随着时间的推移越来越低。

  这是UCB和\epsilon-greedy 在10臂问题下的对比。可以看出UCB对于简单的问题非常有效。但它的缺点在于相对于后者，UCB更难处理非稳态问题以及状态空间 (state space) 较大的问题。

  迄今为止我们讨论的方法都是个体根据估计值来选择相应的行动，现在我们不如换一种思路来思考如何让个体根据偏好 (preference) 来选择行动a，这种方法我们用H_t(a)表示。

  “偏好”的概念非常好理解，个体通过偏好来选择行动意味着它不需要考虑反馈，只需要比较每个行动的偏好值来选择行动。如果我们给每个偏好值加上1000，那么行动的概率分布不会有任何改变，这种分布叫做softmax分布，这种探索方法叫做softmax探索法。其公式如下：

  其中，\pi_t(a)表示在时间段t时选择行动a的概率。该公式的初始状态为所有的行动偏好都相等，这样所有的行动都会有相同的概率被选中。

  第二章讨论的内容都是围绕多臂老虎机问题展开的，作者引入该问题试图向读者说明在我们面对真正强化学习问题时需要注意的概念，并且介绍了解决多臂老虎机问题的一些方法。或许会有人问哪种方法是最好的？这样的一个问题其实在问该如何权衡探索与拓展。事实上，书上讲述的内容与真实世界所要面对的困难是不同的，书中的问题都能得到及时反馈 (immediate reward)，但是现实生活中的问题并不总是这么简单。就像《白色相簿2》中，到底是选冬马还是选雪菜一样，春希面对的正是权衡问题(手动滑稽。