RL-多臂老虎机

强化学习
强化的不是机器模型
而是我的猪脑

老虎机

单臂

现在在你面前有一台老虎机，它有固定的中奖率，当你拉动它，你就会从固定的概率分布中得到奖励。而这个情况不能视作一个强化学习问题，因为它只有一个状态和一个动作，你不能通过任何方法来优化你的策略。

多臂

既然如此，我们就拿来多台老虎机。现在在你面前有数台单臂老虎机，它们各自有不同的中奖分布。现在给定有限的拉动次数 T，你如何拉动这些老虎机来最大化你的收益呢？

这个问题是一个 非联想的，评估性的反馈问题，及每次反馈只评估当前动作，也就是独立事件。

定义

• 非联想的：Non-Assocative，即每次动作的结果不会影响到接下来你对其他老虎机的预期收益。你只是单纯的记录下每个老虎机的平均奖励，然后选择最大的那个。

• 联想的：Associative，当前动作的结果会影响到未来动作的预期收益。你从这次拉动中获得的信息，会影响到你对其他老虎机的选择。在类似于上下文老虎机中，你的动作会影响其他老虎机的中奖概率。

• 评估性的：Evaluative，你得到的奖励，只是你当前动作的结果，你只能知道你刚刚得到了多少收益，而不能知道其他老虎机的中奖概率。

• 指导性的：Instructive，在这种情况下，你不光能得到当前的结果，还能得到其他可能的结果信息。比如你拉动了一个老虎机，你不仅得到奖励，还能得到其他老虎机的奖励信息，即使你没有选择它们。

Formalization

需要数学的方式表达此问题才能应用到计算机中。所以我们定义：

• t 时刻
• $A_t$ 在 t 时刻选择的动作
• $R_t$ 在 t 时刻得到的奖励
• $q_*(a)$ 动作 a 的真实值，是一个固定值，但通常未知
• $Q_t(a)$ 在 t 时刻对动作 a 的估计值，根据过去的经验得到

例子

假设你面前有三个老虎机 1, 2, 3，你有 4 个可用次数：

时刻 t	选择 $A_t$	奖励 $R_t$	期望 $Q_t(1)$	$Q_t(2)$	$Q_t(3)$
1	1	5	5	0	0
2	2	3	5	3	0
3	3	4	5	3	4
4	1	4	4.5	3	4

每次选择一个动作并获得奖励后，需要更新对该动作的估计值。这里我们使用简单的平均值来估计：

$$ Q_t(a) = \frac{\sum_{i=1}^{t-1} R_i \cdot \mathbb{1}_{A_i = a}}{\sum_{i=1}^{t-1} \mathbb{1}_{A_i = a}} $$

$\mathbb{1}_{A_i = a}$ 是一个指示函数，当 $A_i = a$ 时为 1，否则为 0。确保了只有选择了动作 a 的时候才会更新估计值。

这就是 Action-value Methods，即通过动作的估计值来选择动作。

大数定律

简而言之，如果一个事情你做的次数足够多，那么它的平均结果（预估收益）就会接近于它的真实情况。比如抛硬币，正反面比例会越来越接近 0.5。

探索和利用

让我们来理解一下 探索 (Exploration) 和 利用 (Exploitation) 的概念。

• 在任何时间步，至少有一个动作的估计值是最大的。也就是说如果我们选择了一个最大的动作，这就是利用，或者贪婪动作。

• 如果我们选择非贪婪动作，那么就是探索，去试试看能否找到更好的动作。

像之前表中我们在 t=4 的时候选择了 1，这就是贪婪动作。但是我们会发现一个问题：

• 为了获得最大奖励，我们偏好选择已知的最大动作
• 但是如果我们不去探索其他动作，我们就无法知道其他动作的真实值
• 所以我们需要在探索和利用之间找到一个平衡

$\epsilon$-greedy

它是平衡探索和利用的一个简单有效的方法。

• 以 $\epsilon$ 的概率进行探索，而不考虑价值估计
• 以 $1-\epsilon$ 的概率进行利用（贪心动作），选择已知的最大价值动作

练习：计算概率

当 $\epsilon = 0.5$ 时，计算有两个动作，且选择贪心动作的概率。

two actions 不是说你选两次，而是说你在每次选择动作的时候，一共有两个可能，如选 A 或 B。

1. 情况 1：确定选择 ($1-\epsilon$)：= 0.5 的概率直接选择贪心动作

2. 情况 2：随机选择所有动作，也包括选中贪心动作的概率，此时：

   • 选择贪心动作的概率 = 非贪心动作的概率 = 0.5
   • 同时发生 情况 2 & 情况 2 选中贪心动作 的概率 = 0.5 * 0.5 = 0.25

所以选择贪心动作的概率 = 情况 1 + 情况 2 = 0.5 + 0.25 = 0.75

           选择方式
          /      \
   情况1 (0.5)   情况2 (0.5)
      /             /   \
选贪心动作      选A(0.5) 选B(0.5)

练习：策略选择

有 K 臂老虎机，K = 4，四个动作标记为 [1, 2, 3, 4]。应用 $\epsilon$-greedy & sample-average 方法来选择动作。所有动作初始值 $Q_1(a) = 0$。假设前五个时间步的动作和奖励序列如下：

时刻 t	选择 $A_t$	奖励 $R_t$
1	1	1
2	2	1
3	2	2
4	2	2
5	3	0

问：在哪些时间步 一定 发生了探索？在哪些时间步 可能 发生了探索？

解：

由于 5 步内未选择 4，所以在表中隐去。情况描述的是从上一个状态到当前状态。

时刻 t	选择 $A_t$	奖励 $R_t$	期望 $Q_t(1)$	$Q_t(2)$	$Q_t(3)$	情况	细节
0	-	-	0	0	0	-	初始值
1	1	1	1	0	0	可能	所有动作初始等效，无法区分
2	2	1	1	1	0	一定	选择了一个非最优动作
3	2	2	1	1.5	0	可能	选择了最大值动作，但是 1 和 2 值相同
4	2	2	1	1.66	0	可能	2 成为最优，但 2 可能是被随机选中的
5	3	0	1	1.66	0	一定	选择了一个非最优动作

增量更新

记录所有的奖励数据需要占用大量内存，incremental implementation 可以节省内存。通过推导，我们能够得到加权平均的增量更新公式：

$$
Q_{n+1} = Q_n + \alpha \cdot (R_n - Q_n)
$$

其中：

• $Q_{n+1}$ 是新的估计值
• $Q_n$ 是旧的估计值
• $R_n$ 是本次奖励
• $\alpha$ 是学习率，通常是一个小于 1 的值

学习率

• 静态环境
  当 $\alpha = \frac{1}{n}$ 时，即学习率随着时间步的增加而减小，适用于 Stationary Environment，即环境的奖励分布不会随时间变化，保证了所有过去的数据都以同等权重参与更新。

• 动态环境
  当学习率是一个固定值，通常 $0 < \alpha \leq 1$ 时，适用于 Non-Stationary Environment，即环境的奖励分布会随时间变化，近期的奖励对估计值影响更大，而早期的奖励影响较小。

而使用固定的学习率，其实是一种 指数加权平均 (Exponential Weighted Average)，通过对普通加权平均公式的变形，我们可以得到：

$$
Q_{n+1} = (1-\alpha)^n Q_1 + \sum_{i=1}^n \alpha(1-\alpha)^{n-i} R_i
$$

阅读公式我们可以知道：

• 当 $n$ 很大时，$(1-\alpha)^n$ 趋近于 0，即初始值的影响越来越小
• 第二项是一个加权和，权重随着时间步的增加而减小，也就是说近期的奖励对估计值影响更大
• 较大的 $\alpha$ 适合快速变化的环境

乐观初始值

Optimistic Initial Values 通过人为的为所有动作的估计值设置一个过高的初始值，可以鼓励探索。随着时间步的增加，估计值会逐渐收敛到真实值。相比与 $\epsilon$-greedy，它不依赖随机探索，而是基于策略性搜索。代理会确保所有动作都被选择一次，然后根据奖励来调整估计值，而不会陷入局部最优。适用于静态环境和早期探索。

上限置信区间

一种更智能的决策方案是 Upper Confidence Bound (UCB)。它的公式是：

$$
A_t = \arg \max_a \left[ Q_t(a) + c \sqrt{\frac{\ln t}{N_t(a)}} \right]
$$

公式直观的分为三部分：

• $Q_t(a)$ 利用项，是动作 a 当前的最佳估计值，高则 UCB 也高，意味着可能是好选择

• $\sqrt{\frac{\ln t}{N_t(a)}}$ 探索项

  • 未被尝试的动作 $N_t(a)$ 较小，置信界较大，需要更多的探索
  • 已被尝试的动作 $N_t(a)$ 较大，置信界较小，主要依赖于 $Q_t(a)$，即利用
  • 随着时间步的增加，探索压力逐渐减小，因为 $ln t$ 的增长速度很慢，而 $N_t(a)$ 一直增加
  • $c$ 是一个探索参数，控制探索的强度，越大越多探索

• $A_t$ 是选择的动作，$\arg \max_a$ 来决定最大 UCB 值及其对应的动作

当 UCB 高的时候，代表了两种情况，一是动作本来就很好（$Q_t(a)$ 高），二是动作未被充分尝试过（$N_t(a)$ 低），而这个结果本身代表着 探索 + 利用 的收益估计值。该方法优于 $\epsilon$-greedy，减少随机性带来的浪费，适用于静态环境。

探索项其实是通过 Hoeffding Inequality 推导出来的，不等式提供了样本均值与真实均值的误差范围，误差项的形式正是 $\sqrt{\frac{\ln t}{N_t(a)}}$。

策略梯度

它通过调整每个动作的概率来优化策略。使用 softmax 函数来表示：

$$
\pi_t(a) = \frac{e^{H_t(a)}}{\sum_{b=1}^K e^{H_t(b)}}
$$

其中：

• $\pi_t(a)$ 是动作 a 在 t 时刻被选择的概率
• $H_t(a)$ 是动作 a 在 t 时刻的偏好值，不直接表示概率，而是一个中间量
• K 是动作的数量

此算法不会死板地只选一个动作，因为所有的选择都有一定概率被探索，更适合非静态环境，但是对学习率较敏感，不容易调优。

梯度上升（Ascent）

我们的目标是优化动作选择的概率，而不是直接估计奖励值。在时间 t：

1. 选中动作 a
2. 得到奖励 $R_t$
3. 计算奖励与 平均奖励 $\bar{R_t}$ 的差值 $\delta_t = R_t - \bar{R_t}$
   • 如果 $\delta_t > 0$，则动作 a 是好的，我们希望增加它的概率
   • 如果 $\delta_t < 0$，则动作 a 是坏的，我们希望减少它的概率
4. 更新偏好值 $H_t(a)$，其他未选中的 $H_t(b)$ 也会轻微变化，因为 softmax 函数的特性

所以公式如下, 其中 $\alpha$ 是学习率：

$$
H_{t+1}(a) = H_t(a) + \alpha (R_t - \bar{R_t})(1 - \pi_t(a))
$$

其他未选中的动作：

$$
H_{t+1}(b) = H_t(b) - \alpha (R_t - \bar{R_t})\pi_t(b)
$$

关联搜索

Assocative Search 是对之前 联想任务 的扩展，是在 多情境（context）下的决策优化。

• 在 Associative 中，动作可能影响未来收益，但问题仍然是单一情境。
• 而在 Associative Search 中，不仅要学习单个情境下的最优动作，还需要在多个情境中学习不同策略。

对于这种问题，我们为每一种情境学习一个独立的策略。如果动作不仅影响奖励，还影响接下来的情境，那么这个问题就升级为完整的强化学习任务。

练习

现在有两组 2-臂老虎机，你面对的老虎机组会在每个时间步随机变化：

1. A 组（概率 0.5）：
   • Arm 1 的真实值：0.1
   • Arm 2 的真实值：0.2
2. B 组（概率 0.5）：
   • Arm 1 的真实值：0.9
   • Arm 2 的真实值：0.8

你无论如何也不知道它们的真实值，问：

1. 如果你 不知道 当前是 A 组还是 B 组，你会如何选择动作？
2. 如果你 知道 当前是 A 组还是 B 组，你会如何选择动作？

情况 1

如果我不能知道当前情况，那么我只能根据期望值来决策：

对于 Arm 1，它的期望奖励是：

$$
E[R_1] = 0.5 \cdot 0.1 + 0.5 \cdot 0.9 = 0.5
$$

对于 Arm 2，它的期望奖励是：

$$
E[R_2] = 0.5 \cdot 0.2 + 0.5 \cdot 0.8 = 0.5
$$

所以，由于两个动作的期望奖励相同，我会随机选择一个动作。
最大期望收益就是 0.5。

情况 2

当我知道现在的情况时，我就能够有针对性的选择策略。

1. 在 A 组时（概率 0.5）：

   • 选择 Arm 1 的期望奖励是 0.1
   • 选择 Arm 2 的期望奖励是 0.2
   • 所以我会选择 Arm 2

2. 在 B 组时（概率 0.5）：

   • 选择 Arm 1 的期望奖励是 0.9
   • 选择 Arm 2 的期望奖励是 0.8
   • 所以我会选择 Arm 1

它的最大期望奖励是：

$$
E[R_best] = 0.5 \cdot 0.2 + 0.5 \cdot 0.9 = 0.55
$$

有额外的上下文信息（context）可以帮助提高决策质量，这正是 关联搜索（Associative Search） 的关键思想。