多臂赌博机问题
问题陈述
多臂赌博机考虑的是这样一个问题：假设有一台赌博机里面有 $k$ 个摇臂，每拉下一个摇臂赌博机都会掉出一些硬币，每个摇臂掉出硬币数量服从一个平稳的分布，因此一台赌博机中含有 $k$ 个平稳分布。我们的目标是在一段时间内最大化总收益。例如，拉下 1000 次摇臂，最大化收益。
我们令 $t$ 时刻执行的动作（选择的摇臂）记为 $a_t$，其对应的收益（赌博机掉出的硬币价值）记为 $r_t$，动作 $a$ 对应的价值记为 $Q^*(a)$。一般的这是这个动作对应的分布的期望。
$$ Q^*(a):=\mathbb{E}[r_t|a_t=a] $$
如果我们知道所有动作的 $Q^\star(a)$ 那么每次拉下最大价值的摇臂就行了。由于我们刚开始不知道 $Q^{\star}(a)$ 具体的值，因此需要对 $Q^{\star}(a)$ 进行估计。为了最大化累计收益，我们选择要拉下的摇臂就存在探索和利用的问题。前者用于更好的估计 $Q^*(a)$ 后者用于获得更大的收益。
动作-价值方法
我们可以利用某个摇臂收益的平均值来估计 $Q^*(a)$，此处令估计值为 $Q_t(a)$，它表示 $t$ 时刻对摇臂 $a$ 的动作价值估计。
$$Q_t(a):=\frac{\sum_{i=1}^{t-1}r_i \cdot 1\{a_i=a\}}{\sum_{i=1}^{t-1} \cdot 1\{a_i=a\}}$$
这种估计方法被称之为采样平均法，根据大数定律 $Q_t$ 会收敛到 $Q^*$。
在利用阶段我们可以选取当前估计中摇臂价值最高的摇臂作为当前动作：
$$a_t := \arg\max_a Q_t(a)$$
为了更好的估计 $Q^*$，我们以 $\epsilon$ 的概率随机从所有动作中选取一个动作，而以 $1-\epsilon$ 的概率选取当前估计对应价值最大的动作。这种选取动作的方法称之为 $\epsilon$ 贪心方法。那么选择动作的公式如下：
$$ a_t:=\left\lbrace \begin{aligned}\arg\max_a Q_t(a),\quad 以概率 1-\epsilon 选择 \\ 在所有动作中随机选一个,\quad 以概率 \epsilon 选择 \end{aligned} \right. $$
在非平稳的价值分布下以及分布方差较大的情况下，随机探索是很有必要的。
公式（2）可以写成增量式的版本，为了简化标记不妨设 $r_i$ 表示某动作被选择 $i$ 次后获得的收益，$Q_n$ 表示某动作被选择 $n-1$ 次后它的估计的动作价值
$$\begin{aligned} Q_{n+1} &= \frac{1}{n}\sum_{i=1}^{n}r_i \\ &= \frac{1}{n}\left(r_n+\sum_{i=1}^{n-1}r_i\right) \\ &= \frac{1}{n}\left(r_n+(n-1)\frac{1}{n-1}\sum_{i=1}^{n-1}r_i\right) \\ &= \frac{1}{n}\left(r_n+(n-1)Q_n\right) \\ &= Q_n+\frac{1}{n}(r_n-Q_n) \end{aligned}$$
增量式计算的好处在于当时间不长很长的时候，值不会溢出，并且计算量更小。公式（6）的更新方法可以看成一个很一般的形式：
$$\text{新估计值} \leftarrow \text{旧估计值} + \text{步长}\times \underbrace{[\text{目标}-\text{旧估计值}]}_{估计值的误差}$$
所以一个简单的多摇臂赌博机算法如下
跟踪一个非平稳问题
如果赌博机中每个摇臂产生的收益不是一个平稳分布，那么上面的算法就无效了。在这种情况下，我们可以给最近收益更大的权重，来实现跟踪非平稳收益。目前，比较常见的作法是使用一个固定的步长：
$$Q_{n+1}:=Q_n+\alpha [r_n-Q_n]$$
其中 $\alpha \in (0,1]$ 是一个常数，公式 (7) 是对所有过去的收益采取了加权平均的操作，可以看下面公式：
$$\begin{aligned} Q_{n+1} &=Q_{n}+\alpha\left[r_{n}-Q_{n}\right] \\ &=\alpha r_{n}+(1-\alpha) Q_{n} \\ &=\alpha r_{n}+(1-\alpha)\left[\alpha r_{n-1}+(1-\alpha) Q_{n-1}\right] \\ &=\alpha r_{n}+(1-\alpha) \alpha r_{n-1}+(1-\alpha)^{2} Q_{n-1} \\ &=\alpha r_{n}+(1-\alpha) \alpha r_{n-1}+(1-\alpha)^{2} \alpha r_{n-2}+\\ & \cdots+(1-\alpha)^{n-1} \alpha r_{1}+(1-\alpha)^{n} Q_{1} \\ &=(1-\alpha)^{n} Q_{1}+\sum_{i=1}^{n} \alpha(1-\alpha)^{n-i} r_{i} \end{aligned}$$
很容易证明 $(1-\alpha)^n+\sum_{i=1}^{n}\alpha(1-\alpha)^{n-i}=1$。因此，公式（8） 是对所有 $r_i$ 的加权平均，越靠近当前时刻的 $r_i$ 权重越大。
乐观初始值
乐观初始值是一种鼓励智能体去探索的初始化技巧，在普通情况下我们会令 $Q_1(a)=0$。乐观初始值的技巧是将初始值设置为一个较大的数（这个数大于实际价值），例如设置为 5。因此这个初始值 5 为一个乐观估计。这种乐观估计会鼓励动作-价值方法去更多的试探。因为无论哪一个动作被选择，收益都比最开始的估计值要小，更新 $Q_t(a)$ 的时候这个值会变小。因此再取 $\arg\max_a Q(a)$ 的时候就会优先去选其他的动作。其结果就是，所有动作在估计值收敛之前都被尝试了好几次，鼓励智能体去探索。我们把这种鼓励探索的方法叫做乐观初始值。这种技巧在平稳问题中非常有效，但并不是一个普适的方法，它对非平稳问题不适用。
基于置信度上界的动作选择
$\epsilon$-贪心方法虽然会尝试一些不同的动作，但在尝试过程中会随机选择动作，这种动作选择是盲目的。我们最好是根据不同动作的潜力来选择可能是最优的动作。一个有效的方法是按照以下公式来选择动作：
$$ a_t:=\arg\max_a \left[Q_t(a) + c\sqrt{\frac{\ln t}{N_t(a)}} \right] $$
其中 $N_t(a)$ 表示 $t$ 时刻之前动作 $a$ 被选择的次数。$c$ 是一个常数。
这个公式称之为置信度上界 (upper confidence bound, UCB)，公式中的第二项是衡量某一动作被探索的程度，如果某一个动作几乎没有被探索那么第二项就会很大，会鼓励智能体去探索这个动作。公式 (9) 与公式（4）相比，对于多摇臂赌博机问题来说，效果一般会更好，因为它的探索更具有针对性。
梯度赌博机算法
上述两种选择动作的方法并不是唯一可用的方法，还有梯度赌博机算法，它的本质是梯度上升法。我们针对每个动作 $a$ 考虑学习一个数值化的偏好函数 $H_t(a)$。偏好函数越大，动作就越被频繁的选择。这里的偏好不是有具体的收益决定的，而是由与其他动作相比决定的。我们定义 $t$ 时刻动作 $a$ 被选择的概率为 $\pi_t(a)$，它等于：
$$\pi_t(a)=\frac{e^{H_t(a)}}{\sum_{b=1}^k e^{H_t(b)}}$$
每个步骤中偏好函数的更新如下：
$$ \begin{aligned} H_{t+1}(a_t)&:=H_t(a_t)+\alpha (r_t-\bar{r}_t)(1-\pi_t(a_t)), \quad t时刻选了动作 a_t \end{aligned} $$
$$ \begin{aligned} H_{t+1}(a)&:=H_t(a) - \alpha (r_t-\bar{r}_t)\pi_t(a), \quad 对所有 a\neq a_t \end{aligned} $$
其中 $\alpha$ 是步长，$\bar{r}_t$ 表示在时刻 $t$ 内所有收益的平均值（把所有不同动作下的收益都求和，取平均），它可以看成一个基准线。如果收益高于基准线，那么未来选择动作会增加 $a_t$ 的概率，反之就降低。虽然基准项不影响收敛性质，但是基准项可以大大提高收敛速度。书中 P38 页证明了公式 （11） 的更新本质上是一种梯度上升的算法，完全可以从理论上保证（11）的收敛性。
先验采样 (Thompson Sampling)
此外，还有先验采样的方法。先验采样的思路也很简单，由于一个摇臂产生硬币的概率为 $r(a_i)\sim p_{\theta_i}(r_i)$，那么多摇臂赌博机的模型可以表示为：$p(\theta_1,…,\theta_K)$。那么先验采样方法为：
