- 强化学习基础 (1) 多臂赌博机
- 强化学习基础 (2) 有限马尔可夫过程
- 强化学习基础 (3) 动态规划求解
引言
我属于半路出家强化学习，上来就是策略梯度PPO的那种人。最近深感自己的理论基础不够扎实，因此想着全面补充一下强化学习的技术栈。本身我的工作方向也是在LLM应用、搜推系统，这两个方向都是常用到强化学习的，花一点时间打好理论基础总是有益无害的。
这里主要参考的是Richard S. Sutton的 “Reinforcement Learning: An Introduction” 一书，感觉这一本书在传统强化学习方面讲的很不错。如果有任何的错误，请各位大佬指正。
这章主要讲述了多臂赌博机问题。
一、k臂赌博机问题
区分强化学习和其他机器学习方法的一个重要特征在于：强化学习通过监督信号来【评估】当前采取行动的质量，而不是通过给予正确的行动来【指导】模型。这两种反馈是完全不同的：
- 评估性反馈完全取决于当前采取的行动，它表明当前采取的行动【有多好】，但不表明它是不是【最好】的行动
- 指导性反馈与当前的行动完全无关，它表明【最好】的行动是什么。
当强化学习问题的状态空间和动作空间足够小时，我们可以用一张表格表达所有的值函数。在这种情况下，我们通常能够找到问题的最优解，即最优的策略。赌博机问题是最简单的一个强化学习问题，它只有一个状态，因此非常适合作为入门问题来求解。
k臂赌博机的问题设定如下：你需要多次在 $k$ 种动作中选择一个 $A_t$。在每次选择过后，你会得到一个奖励 $R_t$，这个奖励取决于你所选择的行动对应的固定的概率分布。你的目标是在一定时间内（如选择1000次），最大化预期的总奖励。
在上面的问题设定中，每个动作 $a$ 都有一个价值 (Value) $q_*(a)$，表示选择动作 $a$ 所带来的期望奖励，即：
\[\begin{equation} q_*(a):=\mathbb{E}[R_t\mid A_t=a] \end{equation}\]当我们已经知道所有动作的价值之后，最优策略就是每次选择具有最高价值的动作。但一般情况下，我们都无法精确求出 $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$ 所带来的价值，一种自然的方法就是平均实际收到的奖励，即：
\[\begin{equation} Q_t(a):=\frac{\sum_{i=1}^{t-1}R_i\cdot \mathbb{I}(A_i=a)}{\sum_{i=1}^{t-1}\mathbb{I}(A_i=a)} \end{equation}\]由大数定律，当分母趋于无穷大时，$Q_t(a)$ 能够收敛到真实价值 $q_*(a)$。
这种方法称为【样本平均】方法，这是最简单的一种估算动作价值的方式，但并不一定是最佳方法。
在得到动作价值估计后，我们可以定义贪婪策略为：在任意时刻选择价值估计最高的动作，即
\[\begin{equation} A_t=\arg\max_a Q_t(a) \end{equation}\]2.1. $\varepsilon$-greedy动作选择策略
贪婪策略总是最大程度地利用当前的知识来最大化瞬时收益，并没有尝试采取目前看起来次优的行动来探索。
一种简单的改进方法被称为 $\varepsilon$-greedy策略，它在大多数情况下贪婪地选择动作，但仍然有较小的概率 $\epsilon$ 在所有动作中做随机选择，即：
\[\begin{equation} A_t= \begin{cases} \textrm{uniform}(\mathcal{A}),&rand() < \varepsilon\\ \arg\max_a Q_t(a),&otherwise \end{cases} \end{equation}\]$\varepsilon$-greedy策略和纯粹的贪婪策略的好坏是取决于具体任务的。当任务奖励的方差比较大，此时就需要更多的探索才能找到最优动作，因此 $\varepsilon$-greedy会更好。如果奖励方差为0，则贪婪策略在尝试一次之后就能够知道每个动作的真实价值。
2.2. 置信上界动作选择策略
$\varepsilon$-greedy 策略强迫模型去尝试一些非贪婪的动作，但没有对某些动作设定特殊偏好（比如那些价值几乎最优，或者特别不确定的动作）。
如果有一种方法，能够在非贪婪的动作之中按照其称为最优解的潜力 (potential) 来选择，那么能够更加有效地进行探索。
一种有效的方法是按照下面的策略进行动作选择：
\[\begin{equation} A_t=\arg\max_a\left[ Q_t(a)+c\sqrt{\frac{\ln t}{N_t(a)}} \right] \end{equation}\]其中，$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$ 之后，这个动作对应的价值估计。因此，我们有
\[\begin{equation} Q_n:=\frac{1}{n-1}\sum_{i=1}^{n-1}R_i \end{equation}\]因此，$Q$ 值有如下的递推公式
\[\begin{equation} \begin{aligned} Q_{n+1}&=\frac{1}{n}\sum_{i=1}^{n}R_i\\ &=\frac1n\left(R_n+\sum_{i=1}^{n-1}R_i \right)\\ &=\frac1n\left(R_n+(n-1)Q_n \right)\\ &=Q_n+\frac1n(R_n-Q_n) \end{aligned} \end{equation}\]公式 $(6)$ 是强化学习中一种非常常见的迭代方式，其一般形式为：新估计 <– 旧估计 + 步长 * (目标 - 旧估计)。
2.4. 收敛性条件
公式$(6)$的收敛性和更新步长有关。我们考虑更加一般的情况，设在第 $n$ 次选择动作 $a$ 时，更新步长为 $\alpha_n(a)$。下面的定理告诉我们，当 $\alpha_n(a)$ 满足一些条件时，公式 $(6)$ 能够收敛。
Theorem 1 (Robbins-Monro) 考虑递推关系
\[\begin{equation} x_{n+1}=x_n+\alpha_n(y_n-x_n) \end{equation}\]其中，$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)$。此时迭代公式可以等价变形得到：
\[\begin{equation} \begin{aligned} Q_{n+1}(a) &=Q_n(a)+\alpha_n(a)(R_n-Q_n(a))\\ &=Q_n(a)+\alpha_n(a)[(R_n-q_*(a)) + (q_*(a)-Q_n(a))]\\ &=Q_n(a)+\alpha_n(a)[\epsilon_n + (q_*(a)-Q_n(a))]\\ \end{aligned} \end{equation}\]这正是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]$。因此我们有：
\[\begin{equation} \begin{aligned} Q_{n+1} &=Q_n+\alpha(R_n-Q_n)\\ &=\alpha R_n+(1-\alpha)Q_n\\ &=\alpha R_n+(1-\alpha)(\alpha R_{n-1}+(1-\alpha)Q_{n-1})\\ &=\alpha R_n+(1-\alpha)\alpha R_{n-1}+(1-\alpha)^2Q_{n-1}\\ &=\sum_{i=1}^n\alpha(1-\alpha)^{n-i}R_i + (1-\alpha)^n Q_1 \end{aligned} \end{equation}\]注意到权重系数之和 $\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$ 的概率就越大：
\[\begin{equation} \pi_t(a):=P(A_t=a)=\frac{\exp(H_t(a))}{\sum_{a'\in\mathcal{A}}\exp(H_t(a'))} \end{equation}\]我们可以使用梯度上升法，来求解最优的策略$\pi_t$。在每一个时间步 $t$ 后，假设我们选择了动作 $A_t$ 并获得奖励 $R_t$，动作 $a$ 的偏好值更新方式如下所示：
\[\begin{equation} \begin{aligned} H_{t+1}(a)&:=H_t(a)+\alpha(R_t-\overline{R}_t)(\mathbb{I}(a=A_t)-\pi_t(a)) \end{aligned} \end{equation}\]这里 $\overline{R}_t$ 是目前为止获得的所有奖励的均值，也被称为基准线 (baseline)。
公式$(15)$正是梯度上升法推导的结果。如果读者感兴趣，可以在附录中看到相关的证明。
附录
公式(12)的证明
梯度上升法的更新公式为：
\[\begin{equation} \begin{aligned} H_{t+1}(a)&=H_t(a)+\alpha\frac{\partial \mathbb{E}[R_t]}{\partial H_t(a)}\\ \mathbb{E}[R_t]&=\sum_x \pi_t(x)q_*(x) \end{aligned} \end{equation}\]其中，梯度项可以做下面的等价变化：
\[\begin{equation} \begin{aligned} \frac{\partial \mathbb{E}[R_t]}{\partial H_t(a)} &=\frac{\partial }{\partial H_t(a)}\left[\sum_x \pi_t(x)q_*(x) \right]\\ &=\sum_x q_*(x)\frac{\partial \pi_t(x)}{\partial H_t(a)}\\ &=\sum_x (q_*(x)-B_t)\frac{\partial \pi_t(x)}{\partial H_t(a)}\\ \end{aligned} \end{equation}\]这里引入了一个基线项 $B_t$，可以是任何不依赖于 $x$ 的数值。这个等号的成立是因为 $\sum_x \frac{\partial \pi_t(x)}{\partial H_t(a)}=0$。当 $H_t(a)$ 变化时，一些动作的概率变大，另一些动作变小，但所有动作变化量之和一定是0，因为概率之和一定为1。
继续推导，我们有：
\[\begin{equation} \begin{aligned} \frac{\partial \mathbb{E}[R_t]}{\partial H_t(a)} &=\sum_x (q_*(x)-B_t)\frac{\partial \pi_t(x)}{\partial H_t(a)}\\ &=\sum_x \pi_t(x)\cdot\frac{(q_*(x)-B_t)}{\pi_t(x)}\cdot\frac{\partial \pi_t(x)}{\partial H_t(a)}\\ &=\mathbb{E}_{A_t\sim\pi_t}\left[\frac{(q_*(A_t)-B_t)}{\pi_t(A_t)}\cdot\frac{\partial \pi_t(A_t)}{\partial H_t(a)}\right] \end{aligned} \end{equation}\]我们选择基线 $B_t=\overline{R}t=\sum{i=1}^tR_i$。此外，我们有$q_*(A_t)=R_t$。因此，梯度项的最终形式为：
\[\begin{equation} \begin{aligned} \frac{\partial \mathbb{E}[R_t]}{\partial H_t(a)} &=\mathbb{E}_{A_t\sim\pi_t}\left[\frac{(R_t-\overline{R}_t)}{\pi_t(A_t)}\cdot\frac{\partial \pi_t(A_t)}{\partial H_t(a)}\right] \end{aligned} \end{equation}\]下面我们来推导$\frac{\partial \pi_t(x)}{\partial H_t(a)}$的形式：
\[\begin{equation} \begin{aligned} \frac{\partial \pi_t(x)}{\partial H_t(a)}\ &=\frac{\partial }{\partial H_t(a)}\frac{\exp(H_t(x))}{\sum_{y=1}^k\exp(H_t(y))}\\ &=\frac{\frac{\partial\exp(H_t(x))}{\partial H_t(a)}\cdot \sum_{y=1}^k\exp(H_t(y)) - \exp(H_t(x))\cdot\frac{\partial \sum_{y=1}^k\exp(H_t(y))}{\partial H_t(a)}}{\left(\sum_{y=1}^k\exp(H_t(y))\right)^2}\\ &=\frac{\mathbb{I}(a=x)\cdot\exp(H_t(x))\cdot \sum_{y=1}^k\exp(H_t(y)) - \exp(H_t(x))\cdot\exp(H_t(a))}{\left(\sum_{y=1}^k\exp(H_t(y))\right)^2}\\ &=\frac{\mathbb{I}(a=x)\cdot\exp(H_t(x))}{\sum_{y=1}^k\exp(H_t(y))} - \frac{\exp(H_t(x))\cdot\exp(H_t(a))}{\left(\sum_{y=1}^k\exp(H_t(y))\right)^2}\\ &=\mathbb{I}(a=x)\pi_t(x)-\pi_t(x)\pi_t(a)\\ &=\pi_t(x)(\mathbb{I}(a=x)-\pi_t(a)) \end{aligned} \end{equation}\]代入公式$(16)$得：
\[\begin{equation} \begin{aligned} \frac{\partial \mathbb{E}[R_t]}{\partial H_t(a)} &=\mathbb{E}_{A_t\sim\pi_t}\left[(R_t-\overline{R}_t)\cdot (\mathbb{I}(a=x)-\pi_t(a))\right] \end{aligned} \end{equation}\]公式$(12)$得证。
