一杯为品

公告

品味不错，我的朋友。

了解更多

标签

2976 字

15 分钟

【强化学习基础】#2 多臂赌博机

2025-04-10

强化学习基础

无标签

一个k臂赌博机问题#

k臂赌博机问题是一个不存在状态信息，只有动作与奖励的简化情况，其原始形式如下：你要重复地在 $k$ 个选项或动作中进行选择。每次做出选择之后，你都会得到一定数值的收益，收益由你选择的动作决定的平稳概率分布产生。你的目标是在某一段时间内最大化收益期望。

$k$ 个动作中每一个在被选择时都有一个期望或者平均收益，我们称此为这个动作的价值。我们将在时刻 $t$ 选择的动作记作 $A_t$ ，并将对应的收益记作 $R_t$ 。任一动作对应的价值记作 $q_*(a)$ ，是给定动作 $a$ 时收益的期望：

q_*(a)\dot=\mathbb E[R_t|A_t=a]

通常我们不知道动作的价值，但可以估计。我们将对时刻 $t$ 的价值的估计记作 $Q_t(a)$ ，我们希望它接近 $q^*(a)$ 。

在任一时刻，至少有一个动作的估计价值是最高的，这些对应估计最高价值的动作被称为贪心的动作。从贪心动作中选择是开发当前你所知道的关于动作的价值的知识，从非贪心动作中选择则是试探，可以改善对非贪心动作的价值的估计。“开发”对于最大化当前这一时刻的期望收益是正确的做法，而“试探”从长远来看可能会带来总体收益最大化。在同一次动作选择中，开发和试探不可能同时进行，此为开发和试探之间的冲突。

动作-价值方法#

使用价值的估计来进行动作的选择的方法被统称为动作-价值方法。一种自然的方式就是通过计算实际收益的平均值来估计动作的价值：

Q_t(a)=\displaystyle\frac{\displaystyle\sum^{t-1}_{i=1}R_i\mathbb 1_{A_i=a}}{\displaystyle\sum^{t-1}_{i=1}\mathbb 1_{A_i=a}}

其中 $\mathbb 1_{\mathrm {predicate}}$ 表示随机变量，当 $\mathrm{predicate}$ （此处为时刻 $i$ 选择了动作 $a$ ）为真时其值为 $1$ ，反之为 $0$ 。当分母为 $0$ 时，我们将 $Q_t(a)$ 定义为某个默认值，比如 $Q_t(a)=0$ 。当分母趋向无穷大时，根据大数定律， $Q_t(a)$ 会收敛到 $q^*(a)$ 。这种估计动作价值的方法称为采样平均方法。

最简单的动作选择规则是选择贪心动作，如果有多个贪心动作就任选一个：

A_t\dot=\underset{a}{\mathrm{argmax}}Q_t(a)

选择贪心动作总是利用当前的知识最大化眼前的收益，不花时间尝试非贪心动作是否会更好。

贪心策略的一个简单替代策略是大部分时间都表现得贪心，但以一个很小的概率 $\epsilon$ 从所有动作中等概率随机做出选择，称为ε-贪心方法。其优点是如果时刻无限长，则每一个动作都会被无限次采样，从而确保所有的 $Q_t(a)$ 收敛到 $q^*(a)$ ，但这只是渐近性的保证。

$\epsilon$ -贪心方法相对于贪心方法的优点依赖于任务。当收益的方差更大时，由于收益的噪声更多，找到最优的动作所需的试探次数也更多。除此之外，如果动作的真实价值会随着时间而变化，试探也是需要的。

增量式实现#

下面探讨如何高效计算收益的样本均值。对于单个动作，令 $R_i$ 表示这一动作被选择 $i$ 次后获得的收益， $Q_n$ 表示被选择 $n-1$ 次后它的估计的动作价值，则：

Q_n\dot=\displaystyle\frac{R_1+R_2+\cdots+R_{n-1}}{n-1}

该实现需要维护所有收益的记录，并在每次估计时计算，内存和计算量会随着时间增长。

设计增量式公式可以以小而恒定的计算更新平均值。给定 $Q_n$ 和第 $n$ 次的收益 $R_n$ ，新的均值可以这样计算：

\begin{equation}\begin{split}Q_{n+1}&=\displaystyle\frac1n\sum^n_{i=1}R_i\\&=\displaystyle\frac1n\left(R_n+\sum^{n-1}{i=1}R_i\right)\\&=\displaystyle\frac1n\left(R_n+(n-1)\frac1{n-1}\sum^{n-1}_{i=1}R_i\right)\\&=\displaystyle\frac1n\left(R_n+(n-1)Q_n\right)\\&=\displaystyle Q_n+\frac1n\left(R_n-Q_n\right)\end{split}\end{equation}

更新公式的形式将会贯穿强化学习始终，其一般形式是：

$新估计值\leftarrow旧估计值+步长\times[目标-旧估计值]$

$[目标-旧估计值]$ 是估计值的误差，误差会随着向目标靠近的每一步而减小。

每个动作的步长会随着时间而变化，我们将其记作 $\alpha_t(a)$ 。

假设函数 $\mathit{bandit}(a)$ 接收一个动作作为参数并返回一个对应的收益， $N(A)$ 为动作被选择的次数，一个使用增量式计算样本均值和 $\epsilon$ -贪心动作选择的赌博机问题算法的伪代码如下：

初始化，令 $a=1$ $a = 1$ 到 $k$ $k$ ：
1. $Q(a)\leftarrow0$
2. $N(a)\leftarrow0$
无限循环：
1. $A\leftarrow\left\{\begin{matrix}\underset{a}{\mathrm{argmax}}Q(a)&以1-\epsilon概率\\一个随机的动作&以\epsilon概率\end{matrix}\right.$
2. $R\leftarrow\mathit{bandit}(A)$
3. $N(A)\leftarrow N(A)+1$
4. $Q(A)\leftarrow Q(A)+\displaystyle\frac1{N(A)}[R-Q(A)]$

非平稳问题#

在收益概率随时间变化的非平稳问题下，上述取平均方法不再合适，给近期的收益赋予比过去很久的收益更高的权值是一种更合理的处理方式，最流行的方法之一是使用固定步长：

Q_{n+1}\dot=Q_n+\alpha\left[R_n-Q_n\right]

式中，步长参数 $\alpha\in(0,1]$ 是一个常数，这使得 $Q_{n+1}$ 成为过去的收益和初始的估计 $Q_1$ 的加权平均：

\begin{equation}\begin{split}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}\\&=(1-\alpha)^nQ_1+\displaystyle\sum^n_{i=1}\alpha(1-\alpha)^{n-i}R_i\end{split}\end{equation}

其中 $1-\alpha<1$ ，因此赋予 $R_i$ 的权值 $\alpha(1-\alpha)^{n-i}$ 随着相隔次数的增加以指数形式递减，因此该方法也被称为指数近因加权平均。

大数定律的收敛性不能保证对任何 $\{\alpha_n(a)\}$ 序列都满足，随机逼近理论给出了保证收敛概率为 $1$ 所需的条件：

\displaystyle\sum^\infty_{n=1}\alpha_n(a)=\infty且\sum^\infty_{n=1}\alpha^2_n(a)<\infty

第一个条件保证有足够大的步长最终克服任何初始条件或随机波动，第二个条件保证最终步长变小以保证收敛。采样平均方法满足两个收敛条件，而常数步长参数不满足第二个收敛条件，这正是非平稳环境所需的，而且强化学习的问题常常是非平稳的。

乐观初始值#

目前我们讨论的所有方法都在一定程度上依赖于初始动作值 $Q_1(a)$ 的选择。其缺点是初始估计值如果不都设为 $0$ ，则变成了必须由用户选择的参数集，好处是通过它们可以简单地设置关于预期收益水平的先验知识。

初始动作的价值也提供了一种简单的试探方式。如果将所有动作都设置一个相比实际期望较高的初始值，那么这种乐观的初始估计会鼓励动作-价值方法去试探，因为无论哪一种动作被选择的收益都比最开始的估计值小，学习器会感到“失望”而转向另一个动作。这种鼓励试探的技术叫做乐观初始价值。

但这种方法不适合非平稳问题，因为其试探的驱动力是暂时的。任何仅仅关注初始条件的方法都不太可能对一般的非平稳情况有所帮助，但是它们都很简单，其中一个或几个简单的组合在实践中往往是足够的。

基于置信度上界的动作选择#

在非贪心动作中，最好是根据它们的潜力来选择可能事实上是最优的动作，而不是 $\epsilon$ -贪心算法的盲目选择。一个有效的方法是按照以下公式选择动作：

A_t\dot=\underset a{\mathrm{argmax}}\left[Q_t(a)+c\displaystyle\sqrt{\frac{\ln t}{N_t(a)}}\right]

其中 $N_t(a)$ 表示在时刻 $t$ 之前动作 $a$ 被选择的次数，如果 $N_t(a)=0$ ，则 $a$ 就被认为是满足最大化条件的动作。

这种基于置信度上界（UCB）的动作选择的思想是，平方根项是对 $a$ 动作值估计的不确定性或方差的度量。每次选择 $a$ 会使这一项减小（ $N_t(a)$ 增长大于 $\ln t$ ）)，而选择 $a$ 之外的动作会使这一项增大（ $\ln t$ 增长， $N_t(a)$ 不变）。

但是和 $\epsilon$ -贪心算法相比，它更难推广到跟一般的学习问题，其一是因为它处理非平稳问题时需要更复杂的估计更新方法，其二是因为它要处理更大的状态空间，特别是在后续会介绍的函数近似问题中。

梯度赌博机算法#

评估动作价值并使用估计值来选择动作并不是唯一可使用的方法。考虑到和绝对的收益相比，一个动作对另一个动作的相对偏好可能更为重要，于是我们引入softmax分布来计算动作 $a$ 在时刻 $t$ 的被选择概率：

\pi_t(a)\dot=\displaystyle\frac{e^{H_t(a)}}{\displaystyle\sum^k_{b=1}e^{H_t(b)}}

其中 $H_t(a)$ 是为了计算上式引入的偏好函数，如果每一个动作的偏好函数都增加相同的值，对上式得到的动作概率没有任何影响。

基于随机梯度上升的思想，在每个步骤选择动作 $a_i$ 并获得收益 $R_t$ 之后，偏好函数按如下方式更新：

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

H_{t+1}(a_j)\dot=H_t(a_j)-\alpha(R_t-\bar R_t)\pi_t(a_j),对所有j\neq i

下面我们来推导这一梯度更新公式，简记 $\theta_i = H_t(a_i)$ ，则其目标函数为

J(\theta) = \mathbb{E}_{a \sim \pi_\theta}[r(a)] = \sum_i r(a_i)\pi_\theta(a_i)

对其求梯度

\nabla_\theta J(\theta) = \sum_i r(a_i) \nabla_\theta \pi_\theta(a_i)

利用对数导数技巧

\nabla_\theta \ln \pi_\theta(a_i) = \frac{1}{\pi_\theta(a_i)} \nabla_\theta \pi_\theta(a_i) \quad \Rightarrow \quad \nabla_\theta \pi_\theta(a_i) = \pi_\theta(a_i) \nabla_\theta \ln \pi_\theta(a_i)

代入得

\nabla_\theta J(\theta) = \sum_i r(a_i) \pi_\theta(a_i) \nabla_\theta \ln \pi_\theta(a_i) = \mathbb{E}_{a \sim \pi_\theta} \left[ r(a) \nabla_\theta \ln \pi_\theta(a) \right]

进一步分析 $\ln \pi_\theta(a)$

\ln \pi_\theta(a_i) = \theta_i - \ln \sum_j e^{\theta_j}

计算其关于 $\theta_k$ 的偏导

\nabla_{\theta_k} \ln \sum_j e^{\theta_j} = \frac{e^{\theta_k}}{\sum_j e^{\theta_j}} = \pi_\theta(a_k)

因此，梯度分量为

\nabla_{\theta_k} \ln \pi_\theta(a_i) = \begin{cases} 1 - \pi_\theta(a_k), & k = i \\ -\pi_\theta(a_k), & k \ne i \end{cases}

最终梯度可写为期望形式

\nabla_\theta J(\theta) = \mathbb{E}_{a \sim \pi_\theta} \left[ r(a) \begin{bmatrix} -\pi_\theta(a_1) \\ \vdots \\ 1 - \pi_\theta(a_i) \\ \vdots \\ -\pi_\theta(a_n) \end{bmatrix} \right]

$\theta$ 是包含所有动作的偏好函数的向量，目标函数是期望奖励，梯度上升的过程就是调节所有动作的偏好函数使期望奖励最大化。

由于我们无法遍历所有动作来计算期望，只能对每个步骤选择的动作 $a_i$ 做单次采样近似

\nabla_\theta J(\theta) \approx r(a_i) \begin{bmatrix} -\pi_\theta(a_1) \\ \vdots \\ 1 - \pi_\theta(a_i) \\ \vdots \\ -\pi_\theta(a_n) \end{bmatrix}

最终我们得到参数更新规则为

$\theta_j \leftarrow \begin{cases} \theta_j + r(a_i)\left[1 - \pi_\theta(a_j)\right], & j = i \\ \theta_j - r(a_i)\pi_\theta(a_j), & j \ne i \end{cases}$

直接采用当前时刻观测到的奖励 $r(a_i)$ 来更新梯度的问题是，其方差带来的波动会使 $\theta$ 的更新不稳定，收敛速度变慢。为了削弱方差的影响，我们在此基础上减去一个较为稳定的基线 $b$ ，当 $b$ 选择过去收益的均值 $\bar R_t$ ，并辅以一个超参数 $\alpha$ 用于调控学习率，就得到了一开始给出的式子。

关联搜索#

一般的强化学习任务中，往往有不止一种情境。以一个非平稳的 $k$ 臂赌博机为例，我们为其添加外观颜色的情境，赌博机的外观颜色与其动作价值集合一一对应，并随着动作价值集合的改变而改变，那么学习器还需要学习外观颜色到动作价值集合的映射关系，将情境与最优动作关联起来，这便是关联搜索任务。

关联搜索任务介于 $k$ 臂赌博机问题和完整强化学习问题之间。和 $k$ 臂赌博机相比，它还需要学习一种策略。和完整强化学习问题相比，它的每个动作只影响即时收益。如果动作可以影响下一时刻的情境和收益，便是完整的强化学习问题，将在下一章具体提出。

【强化学习基础】#2 多臂赌博机

https://inkem.space/posts/强化学习基础/2-多臂赌博机/

作者

一杯为品

发布于

2025-04-10

许可协议

CC BY-NC-SA 4.0

部分信息可能已经过时

【强化学习基础】#3 有限马尔可夫决策过程

【强化学习基础】#1 引论

我是一杯为品