强化学习基础 (1)：多臂赌博机

2025-09-25 强化学习基础 #强化学习 #多臂赌博机约 21 分钟 · 7028 字

引言

我属于半路出家强化学习，上来就是策略梯度PPO的那种人。最近深感自己的理论基础不够扎实，因此想着全面补充一下强化学习的技术栈。本身我的工作方向也是在LLM应用、搜推系统，这两个方向都是常用到强化学习的，花一点时间打好理论基础总是有益无害的。

这里主要参考的是Richard S. Sutton的 “Reinforcement Learning: An Introduction” 一书，感觉这一本书在传统强化学习方面讲的很不错。如果有任何的错误，请各位大佬指正。

这章主要讲述了多臂赌博机问题。

一、k臂赌博机问题

区分强化学习和其他机器学习方法的一个重要特征在于：强化学习通过监督信号来【评估】当前采取行动的质量，而不是通过给予正确的行动来【指导】模型。这两种反馈是完全不同的：

评估性反馈完全取决于当前采取的行动，它表明当前采取的行动【有多好】，但不表明它是不是【最好】的行动
指导性反馈与当前的行动完全无关，它表明【最好】的行动是什么。

当强化学习问题的状态空间和动作空间足够小时，我们可以用一张表格表达所有的值函数。在这种情况下，我们通常能够找到问题的最优解，即最优的策略。赌博机问题是最简单的一个强化学习问题，它只有一个状态，因此非常适合作为入门问题来求解。

k臂赌博机的问题设定如下：你需要多次在 $k$ 种动作中选择一个 $A_t$ 。在每次选择过后，你会得到一个奖励 $R_t$ ，这个奖励取决于你所选择的行动对应的固定的概率分布。你的目标是在一定时间内（如选择1000次），最大化预期的总奖励。

在上面的问题设定中，每个动作 $a$ 都有一个价值 (Value) $q_*(a)$ ，表示选择动作 $a$ 所带来的期望奖励，即：

(1)

当我们已经知道所有动作的价值之后，最优策略就是每次选择具有最高价值的动作。但一般情况下，我们都无法精确求出 $q_*(a)$ ，我们可能只能得到在时间 $t$ 下采取动作 $a$ 所带来的价值估计 $Q_t(a)$ 。因此我们的目标就是让 $Q_t(a)$ 尽可能接近 $q_*(a)$ 。

这里注意到，我们的价值估计引入了新的变量，即时间 $t$ 。因此，某个时间下 $Q_t(a)$ 最大的动作 $a$ 并非必然是全局最优动作，这也就带来了两种不同的行动策略：

如果你在每一个时刻都选择 $Q_t(a)$ 最大的动作，则你正在【利用】(exploit) 你对当前动作价值的了解。这种策略也称为贪婪策略，因为你总是贪婪地选择当前的最优解。
如果你选择了一个次优解，则你正在【探索】(explore) 当前动作的价值，因为你期望当前的次优解可以导向全局的最优解，以此更新你对当前动作价值的判断。

在强化学习算法中，平衡【探索】和【利用】是一个非常重要的问题，我们的k臂赌博机问题可以很好地展示这一点。

二、动作价值方法

估算在时间 $t$ 下采取动作 $a$ 所带来的价值，一种自然的方法就是平均实际收到的奖励，即：

(2)

由大数定律，当分母趋于无穷大时， $Q_t(a)$ 能够收敛到真实价值 $q_*(a)$ 。

这种方法称为【样本平均】方法，这是最简单的一种估算动作价值的方式，但并不一定是最佳方法。

在得到动作价值估计后，我们可以定义贪婪策略为：在任意时刻选择价值估计最高的动作，即

(3)

2.1. $\varepsilon$ -greedy动作选择策略

贪婪策略总是最大程度地利用当前的知识来最大化瞬时收益，并没有尝试采取目前看起来次优的行动来探索。

一种简单的改进方法被称为 $\varepsilon$ -greedy策略，它在大多数情况下贪婪地选择动作，但仍然有较小的概率 $\epsilon$ 在所有动作中做随机选择，即：

(4)

$\varepsilon$ -greedy策略和纯粹的贪婪策略的好坏是取决于具体任务的。当任务奖励的方差比较大，此时就需要更多的探索才能找到最优动作，因此 $\varepsilon$ -greedy会更好。如果奖励方差为0，则贪婪策略在尝试一次之后就能够知道每个动作的真实价值。

2.2. 置信上界动作选择策略

$\varepsilon$ -greedy 策略强迫模型去尝试一些非贪婪的动作，但没有对某些动作设定特殊偏好（比如那些价值几乎最优，或者特别不确定的动作）。

如果有一种方法，能够在非贪婪的动作之中按照其称为最优解的潜力 (potential) 来选择，那么能够更加有效地进行探索。

一种有效的方法是按照下面的策略进行动作选择：

(5)

其中， $N_t(a)=\sum_{i=1}^{t-1}\mathbb{I}(A_i=a)$ 表示动作 $a$ 被选择的次数，超参数 $c$ 控制探索的力度。

这个动作选择策略被称为【置信上界策略】(Upper Confidence Bound, UCB)，平方根里的项实际上是对估计 $q_*(a)$ 的不确定性或方差的度量。

每次选择动作 $a$ 时， $N_t(a)$ 变大，不确定性降低
每次选择其他动作时， $t$ 变大，不确定性增加

2.3. 增量实现

这里我们介绍，在实际情况中如何动态维护和更新 $Q_t(a)$ 的值。

为了简化符号，我们只考虑某一个动作 $a$ 。令 $R_i$ 为第 $i$ 次选择动作 $a$ 所带来的价值， $Q_n$ 表示在选择 $n-1$ 次动作 $a$ 之后，这个动作对应的价值估计。因此，我们有

(6)

因此， $Q$ 值有如下的递推公式

(7)

公式 $(6)$ 是强化学习中一种非常常见的迭代方式，其一般形式为：新估计 <-- 旧估计 + 步长 * (目标 - 旧估计)。

2.4. 收敛性条件

公式 $(6)$ 的收敛性和更新步长有关。我们考虑更加一般的情况，设在第 $n$ 次选择动作 $a$ 时，更新步长为 $\alpha_n(a)$ 。下面的定理告诉我们，当 $\alpha_n(a)$ 满足一些条件时，公式 $(6)$ 能够收敛。

Theorem 1 (Robbins-Monro) 考虑递推关系

(8)

其中， $y_n$ 是满足 $\mathbb{E}[y_n\mid x_n]=f(x_n)$ 的随机变量。

若 $f(x)=0$ 有唯一解 $x^*$ ，且满足：

$\sum_{i=1}^\infty\alpha_n=\infty$ ；
$\sum_{i=1}^\infty\alpha_n^2=0$ ；
$f$ 在 $x^*$ 附近连续且满足某种稳定性条件（如局部Lipschitz性或单调性）

则 $x_n\rightarrow x^*$ 几乎必然成立（收敛的概率为1）

在公式 $(6)$ 中，我们令 $f(x)=q_*(a)-x$ ，收敛值 $x^*=q_*(a)$ 。此时迭代公式可以等价变形得到：

(9)

这正是Robbins-Monro定理中的形式。这里的 $f$ 是线性的，满足稳定性条件。

因此，只要步长满足

$\sum_{i=1}^\infty\alpha_n=\infty$ ：保证迭代不会过早停止，能够持续修正估计偏差。
$\sum_{i=1}^\infty\alpha_n^2=0$ ：控制噪声项 $\epsilon_n$ 的影响，保证算法稳定收敛（鞅收敛定理）

则迭代能够保证收敛。

三、非稳定奖励问题

在上面的讨论中，我们都假设k臂赌博机问题的奖励只与选择的动作 $a$ 有关，而与时间 $t$ 无关。

然而在实际情况中，不同时间下选择同一动作带来的奖励应该是不一样的。在这种情况下，最近的动作带来的收益应该更加重要。一个最常用的方式就是【指数加权平均】，这种方法将更新步长固定为一个常数 $\alpha\in(0,1]$ 。因此我们有：

(10)

注意到权重系数之和 $\sum_{i=1}^n\alpha(1-\alpha)^{n-i} + (1-\alpha)^n=1$ ，因此实际上 $Q_{n+1}$ 就是过去所有奖励和初始估计 $Q_1$ 的加权平均。

此外由于 $1-\alpha<1$ ，因此最近的奖励（ $i$ 越大）的权重是越大的。

四、赌博机问题的梯度算法

在上面介绍的动作价值方法中，我们通过估计每个动作的价值 $Q_t(a)$ ，并通过一定的策略来选择动作。

这种方法并非唯一解法。我们在这里介绍一种基于梯度的方法，主要思想是为每个动作学习一个偏好值 $H_t(a)$ 。偏好越大，采取动作 $a$ 的概率就越大：

(11)

我们可以使用梯度上升法，来求解最优的策略 $\pi_t$ 。在每一个时间步 $t$ 后，假设我们选择了动作 $A_t$ 并获得奖励 $R_t$ ，动作 $a$ 的偏好值更新方式如下所示：

(12)

这里 $\overline{R}_t$ 是目前为止获得的所有奖励的均值，也被称为基准线 (baseline)。

公式 $(15)$ 正是梯度上升法推导的结果。如果读者感兴趣，可以在附录中看到相关的证明。

附录

公式(12)的证明

梯度上升法的更新公式为：

(13)

其中，梯度项可以做下面的等价变化：

(14)

这里引入了一个基线项 $B_t$ ，可以是任何不依赖于 $x$ 的数值。这个等号的成立是因为 $\sum_x \frac{\partial \pi_t(x)}{\partial H_t(a)}=0$ 。当 $H_t(a)$ 变化时，一些动作的概率变大，另一些动作变小，但所有动作变化量之和一定是0，因为概率之和一定为1。

继续推导，我们有：

(15)

我们选择基线 $B_t=\overline{R}_t=\sum_{i=1}^tR_i$ 。此外，我们有 $q_*(A_t)=R_t$ 。因此，梯度项的最终形式为：

(16)

下面我们来推导 $\frac{\partial \pi_t(x)}{\partial H_t(a)}$ 的形式：

(17)

代入公式 $(16)$ 得：

(18)

公式 $(12)$ 得证。

引言