Chap2 multi-arm-banner
第2章：多臂老虎机
一、引入
1. 定义
重复地在k个动作中进行选择。每次做出选择之后，你都会得到一定数值的奖励(return)，奖励由你选择的动作的平稳概率分布产生。你的目标是在某一段时间内最大化总奖励的期望，比方说1000次选择之后。
2. 实例
对于有k个控制杆的老虎机，每一次动作选择就是拉动老虎机的一个控制杆，而奖励就是得到的奖金。通过多次的重复动作选择，你要学会将动作集中到最好的控制杆上，从而最大化你的奖金。
医生在一系列疗法之间进行选择。每次动作选择就是选择一种疗法，每次的奖励是患者因为治疗而得到的愉悦舒适感。
3. 动作的价值
每个动作action在被选择时都有一个平均奖励（期望），我们称此期望值为该动作的“价值”(value)，记作$q_*(a)$
- 此处的$R_t$指的是当前选择动作后的 直接即时结果，比如你买了股票，第二天市场开盘时这只股票涨了或跌了，这个涨跌就是$R_t$，要和累计奖励$U_t$区分开；
- 此式所求的期望，是 “在已知选择动作a的情况下，$R_t$ 的平均值”。因为虽然所选择的动作固定了，但是所给的奖励return不是一定的，比如：动作A选取为a=”从1、2两个老虎机中选择了1号机”，但对于1号机，它可能返回给玩家的奖励$R_t$可能为：一枚、五枚或零枚硬币，而$q_*(a)$这个期望值，求的就是$R_t$的平均值。
比如选取了1号机，它有70%的概率返回100枚硬币，30%的概率返回0枚，则该选择动作的价值：
$q_∗(a)=0.7×100+0.3×0$
如果你知道每个动作的价值，则解决k臂赌博机问题就很简单：每次都选择价值最高的动作。我们假设你不能确切地知道动作的价值，但是你可以进行估计。我们将对动作 a在时刻t时的价值的估计记作 $Q_t(a)$，我们希望它接近 $q_*(a)$。
4. 开发vs.试探
如果你持续对动作的价值进行估计，那么在任一时刻，都至少有一个动作的估计价值是最高的，称这些估计价值最高的动作为贪心动作；
- 当你从贪心的动作中选择时，我们称此为开发；
当你选则了非贪心的动作，则称为试探；
“开发”对于最大化当前这一时刻的期望奖励是正确的做法，但是“试探”从长远来看可能会带来总体奖励的最大化。比如说，假设一个贪心动作的价值是确切知道的，而另外几个动作的估计价值与之差不多但是有很大的不确定性。这种不确定性足够使得至少一个动作实际上会好于贪心动作，但是你不知道是哪一个。那么对非贪心的动作进行试探并且发现哪一个动作好于贪心动作也许会更好。
实例
假设你在玩一个简单的赌博机游戏，只有两台机器：
- 机器A：中奖概率为 60%。
- 机器B：中奖概率为 90%。
一开始，你随机选择机器：
- 你第一次选择机器A，中奖。
- 你第二次选择机器A，中奖。
- 你第三次选择机器A，中奖。
此时，你可能会认为机器A的奖励更高，因此未来一直选择机器A。如果你从不试探机器B，那么即使机器B更优，你也永远不会发现。原因是：机器A的估计值（基于少量数据）误导了你。
下面讨论 估计动作的价值的方法，首先是动作价值方法：
二、动作价值方法(action-value method)
Step1 ： 估计价值
如前所述，动作的价值的真实值是选择这个动作时的期望奖励。因此，一种自然的方式就是 通过计算实际奖励的平均值 来估计动作的价值：
\[Q_t(a) = \frac{\text{到 $t$ 时刻，通过执行动作 $a$ 得到的收益总和}}{\text{到$t$ 时刻，执行动作 $a$ 的次数}} = \frac{\sum_{i=1}^{t-1} R_i \cdot \mathbf{1}(A_i = a)}{\sum_{i=1}^{t-1} \mathbf{1}(A_i = a)}\]Step2 ：选择动作
1）贪心方法
最简单的动作选择规则是选择具有最高估计值的动作，即贪心动作；
2）ϵ-贪心方法
贪心策略的一个简单替代策略是：大部分时间都表现得贪心，但偶尔（比如以一个很小的概率ϵ）以独立于动作-价值估计值的方式从所有动作中等概率随机地做出选择。
3）两种方法的比较
ϵ-贪心方法相对于贪心方法具有优势，但其优势依赖于具体任务：
假设奖励的方差很大，那么由于奖励的噪声更多，所以为了找到最优的动作需要更多次的试探，则ϵ-贪心方法会比贪心方法好很多；
但是，如果奖励的方差是0,那么贪心方法会在尝试一次之后就知道每一个动作的真实价值。在这种情况下，贪心方法实际上可能表现最好，因为它很快就会找到最佳的动作，然后再也不会进行试探。
三、增量式实现
现在让：
- $R_i$ 表示奖励表示第 i 次选择该动作后获得的奖励
- $Q_n$表示该动作被选择$n-1$次后，其价值(value)的估计值
则原来的估计动作价值的公式可以写为：
此式在符号上有所简化，但如果按它计算的话，需要维护所有奖励的记录，然后在每次需要估计价值时进行计算，这会占据很多存储和计算资源，所以再进行变换：
\[Q_{n+1} = Q_n + \frac{1}{n}\left(R_n - Q_n\right)\]现在得到了该公式的 增量式 形式，即通过 逐步更新 的方式计算新值，而无需完全重新计算所有历史数据，该增量式会贯穿本书始终。
观察此式，可以发现其形式是：
1
**新估计值 ← 旧估计值 + 步长 × [ 目标 - 旧估计值 ]**
- 其中[ 目标-旧估计值 ] 是估计值的 误差。误差会随着向 “目标” 靠近的每一步而减小。也就是说，在第n步，奖励$R_n$ 是实际观测到的奖励值，在单步更新中，它是当前唯一可用的反馈信号，因此被视为调整估计值的直接依据，即“目标”，我们希望旧估计值$Q_n$向$R_n$调整靠近。
- 虽然$R_n$的值在每次选择动作后会变化，但不用担心$Q_{n+1}$的值会不停浮动——别忘了还有步长1/n的存在！随着n增大，1/n越来越小，这个“误差”在计算式中的比重也越来越小，最后新估计值会渐趋稳定。（为什么确信它能趋于一个稳定值？见概率论）
- 值得注意的是，上式的 “步长” 1/n，也称为 “学习率” ，会随着时间 $n$ 而变化。处理动作a对应的第n个奖励的方法 用的“步长”是$1/n$。在本书中我们将“步长”记作 α，或者更普适地记作 $α_t(a)$。
四、跟踪一个非平稳问题
到目前为止我们讨论的取平均方法对平稳的赌博机问题是合适的，即收益的概率分布
不随着时间变化的赌博机问题。但如果赌博机的收益概率是随着时间变化的，比如摇臂A的
奖励概率随时间逐渐下降：
- 第1天：摇臂A有80%概率奖励10元；
- 第30天：概率降至40%；
第60天：概率进一步降至20%。
由倒数第二行可以看出，越早的奖励$R_i$前面所乘以的权重越小——$(1-α)$是个小数，它的次数越高，值就越小。
五、乐观初始值
1. 什么是乐观初始值？
将动作值函数的初始估计 $Q_1(a)$ 故意设置为高于真实值。例如，在10臂老虎机问题中，若真实奖励的均值为0，但将初始估计设为 +5 。这种策略通过“高估”动作的潜在收益，鼓励智能体主动探索所有动作，从而避免过早陷入局部最优。
2. 初始值的偏差及其影响
初始值 $Q_1(a)$ 的设定会导致估计值在初期偏离真实值。
- 采样平均法（步长 $\alpha_n = \frac{1}{n}$ ）：当所有动作至少被选择一次后，该初始值导致的偏差消失。
- 固定步长法（如 $\alpha = 0.1$ ）：该初始偏差随时间减小，但不会完全消失。
3. 乐观初始值如何促进试探？
以10臂老虎机为例：
- 初始设定：所有动作的初始值 $Q_1(a) = +5$ ，而真实奖励均值为0。
- 试探机制：
- 首次选择动作：无论选择哪个动作，实际奖励$R_1$大概率远低于初始估计$Q_1$，所以误差$R_1-Q_1$是一个很大的负值，那么计算出来的$Q_2$就比$Q_1$小，所以在下一次选择动作的时候，就不会选取第一轮所选取的这个动作，因为其动作价值的估计值比其他的小。
- “失望”效应：学习器发现实际奖励远低于预期（$R - Q(a) = -4$），更新后 Q(a) 降低。
- 转向其他动作：由于其他动作的初始值仍为+5，智能体倾向于尝试未充分探索的动作。
六、基于置信度上界的动作选择
ϵ-贪心算法虽然比贪心算法有所改进（增加了“探索”），但其对探索动作的选择是盲目的，而且不大会去选择接近贪心动作的动作。然而，在非贪心动作中，最好是根据它们的潜力来选择可能事实上是最优的动作，这就要考虑到它们的估计有多接近最大值，以及这些估计的不确定性。
一个有效的方法是按如下公式来选择动作：
\[A_t = \arg\max_a \left[ Q_t(a) + c \sqrt{\frac{\ln t}{N_t(a)}} \right]\]八、梯度赌博机算法
具体理论见链接（推导要了解机器学习的 梯度上升算法、softmax等），这里只贴出偏好函数H的更新公式：
九、关联搜索
阐述了K臂赌博机，情景式赌博和完全强化学习问题的区别。K臂赌博机只有一个状态（state，情景式赌博具有多个state（情景），但是决策是单步的，不会影响下一个状态和回报。完全RL问题具有多个状态，决策会影响到后续状态，近而影响长远的回报。