强化学习基础 1：Multi-Armed Bandit Algorithms

2019-04-22 强化学习

Multi-Armed Bandit 模型是强化学习中一个最简单的问题模型——状态空间中仅有一个状态。因此，它是引导新手学习基础强化学习算法的一个很好的例子。

一、模型定义

有一台具有 $k​$ 个拉杆的老虎机，每个拉杆都会返回相应的奖励值。Agent 每一轮可以选择一个拉杆，并获得一个奖励，其最终目标是使得在多轮选择后总奖励最大。

形式化：用 $A_t$ 表示在第 $t$ 轮时 agent 执行的动作（选择哪个拉杆）；用 $R_t$ 表示相应得到的奖励；用 $q_\ast(a)$ 表示每个动作 $a$ 的价值，其定义为执行动作 $a$ 后获得的奖励的数学期望：

$$ q_\ast(a)\doteq\mathbb{E}[R_t\mid A_t=a] $$

如果准确知道了 $q_\ast(a)$，那这个问题将非常简单：每次选择 $q_\ast(a)$ 最大的 $a$ 就行了。但问题是不知道 $q_\ast(a)$，所以需要估计它。用 $Q_t(a)$ 表示在 $t$ 时刻对 $q_\ast(a)$ 的估计值，我们希望 $Q_t(a)$ 能尽可能准确地估计 $q_\ast(a)$ 。这种依赖动作价值 $Q_t(a)$ 的方法统称为 Action-Value 方法。

二、Action-value 方法

一个自然的想法是：用实际得到奖励的平均值来估计它的数学期望，即

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

在这种情况下，有以下几种不同的选择动作的方式。

Greedy

顾名思义就是每次选择 $Q_t(a)$ 最大的：

$$ \newcommand{\argmax}[1]{\underset{#1}{\operatorname{arg\,max\;}}} $$

$$ A_t\doteq \argmax{a} Q_t(a) $$

这种贪婪的选择方法一般效果不好，因为很可能落入局部最优。所以需要增加一些探索的概率。

$\varepsilon$-Greedy

这种选择方法有 $\varepsilon$ 的概率会探索：随机选择一个动作。这比贪婪方法好，因为有机会找到真正的最优动作。

$$ A_t\doteq \begin{cases} \argmax{a}Q_t(a)&\text{with probability } 1-\varepsilon\\ \text{a random action}&\text{with probability }\varepsilon \end{cases} $$

Upper-Confidence-Bound (UCB)

虽然 $\varepsilon$-greedy 方法提供了必要的探索率，但它随机选择时总是一视同仁。而 UCB 方法的思路是：对于那些尝试次数较少的动作，应该要以更大的概率选择它们，因为它们潜力（不确定性）更大。用数学语言来说，就是它们的的价值的置信区间的上界更大。这也就是它名字的由来。

UCB 算法的背后有严格数学理论的证明 (Chernoff-Hoeffding 不等式)，在此不介绍，直接给出动作选择公式：

$$ A_t\doteq\argmax{a}\left[Q_t(a)+c\sqrt{\frac{\ln t}{N_t(a)}}\, \right] $$

这里 $N_t(a)$ 表示动作 $a$ 在时间 $t$ 之前被选中的次数，常数 $c$ 用来权衡探索（Exploration）和利用（Exploitation）。这个公式很容易理解。

附 1：实现技巧

上面的算法都要计算平均值 $Q_t(a)$ ，常规的算法是记录之前所有的 $R_i$，最后统一计算。但这样的计算时间复杂度和空间复杂度都是 $O(N)$，效率太低。其实这里可以使用效率更高的增量更新来实现，即：

$$ Q_{n+1}=Q_n+\frac{1}{n}\left[R_n-Q_n\right] $$

这个式子显然是在计算平均值。并且只需要常数的计算时间和空间。

并且这个式子的形式其实可以推广：它实际上是一种迭代更新规则

$$ \text{NewEstimate}\gets\text{OldEstimate}+\text{StepSize}\left(\text{Target}-\text{OldEstimate}\right) $$

的一个实例。这种迭代更新规则在强化学习中很常见，它的目的就是使得估计值不断接近目标值。

三、Gradient Bandit 算法

除了 action-value 方法，还有一类算法也很有效，它们都基于梯度的计算，因此叫做 Gradient Bandit 算法。这一部分实际上是现在强化学习中最流行的 Policy Gradient 算法的基础。

考虑这样一种方法：在每个时刻 $t$，对每个动作 $a$，agent 有一个偏好值 (preference)，记为 $H_t(a)$；偏好值越大，则动作被选中的概率越大。这通过 Softmax 函数实现：

$$ \Pr{A_t=a}\doteq\frac{e^{H_t(a)}}{\sum_{b=1}^ke^{H_t(b)}}\doteq\pi_t(a) $$

由于 Softmax 函数的原因，偏好值的绝对大小没有意义，不同动作的偏好值之间的相对大小决定了哪个动作被选择。所以，最初可以令所有偏好值 $H_0(a)$ 都为 0，等价于每个动作以相等的概率被选中。

但我们希望学习得到一个最优的策略 $\pi_\ast(a)$ 使得系统性能最好，显然以相等的概率随机选择每个动作不会是最佳策略。形式化这个问题： 要求最大化目标函数（这里是期望的奖励值）

$$ \mathbb{E}[R_t]\doteq\sum_a\pi_t(a)q_\ast(a) $$

求解这个最优化问题可以用 梯度上升 (Gradient Ascend) 方法，即按照下式来更新优化变量 $H_t(a)$：

$$ H_{t+1}(a)\doteq H_t(a)+\alpha\frac{\partial\,\mathbb{E}[R_t]}{\partial H_t(a)}\tag{GA} $$

可惜这个算法无法实现：依照假设，我们并不知道真实的 $q_\ast(a)$，所以第二项梯度 $\frac{\partial\,\mathbb{E}[R_t]}{\partial H_t(a)}$ 算不出。但如果可以找到一个表达式，它的数学期望为 $\frac{\partial\,\mathbb{E}[R_t]}{\partial H_t(a)}$，那就可以通过随机梯度上升 (Stochastic Gradient Ascend) 来解决，也就是利用真实梯度的随机近似 (stochastic approximation，可参考 Stochastic Optimization 理论)。

事实上确实存在这样的近似。在每一步后，假设选择了 $A_t$，得到了 $R_t$，则偏好值的更新公式为：

$$ \begin{align} H_{t+1}(A_t)&\doteq H_t(A_t)+\alpha(R_t-\bar{R}_t)(1-\pi_t(A_t)),&\text{ and}\\ H_{t+1}(a)&\doteq H_t(a)-\alpha(R_t-\bar{R}_t)\pi_t(a),&\text{ for all } a \ne A_t \end{align}\tag{SGA} $$

下面是这个更新公式的证明。

首先证明一个 Softmax 函数的性质：$\sum_i\frac{\partial f_i(x)}{\partial x_a}=0$，即所有输出关于某个输入 $x_a$ 的梯度的求和为 0。 这个可以直观看出：当 $x_a$ 改变一个极小量后，某些输出会增大，某些输出会减小，但所有变化量的和必然是零，因为所有输出的和恒为 1. 下面是证明：

$$ \begin{align} \sum_i\frac{\partial f_i(x)}{\partial x_a}&=\frac{\partial f_a(x)}{\partial x_a}+\sum_{i\ne a}\frac{\partial f_i(x)}{\partial x_a}\\ &=\frac{e^{x_a}\left(\sum_je^{x_j}\right)-e^{x_a}e^{x_a}}{\left(\sum_je^{x_j}\right)^2}+\sum_{i\ne a}\frac{0-e^{x_i}e^{x_a}}{\left(\sum_je^{x_j}\right)^2}\\
&=\frac{e^{x_a}\left(\sum_je^{x_j}-e^{x_a}-\sum_{i\ne a}e^{x_i}\right)}{\left(\sum_je^{x_j}\right)^2}\\ &=0 \tag{Q.E.D.} \end{align} $$

接下来是正式的证明：

$$ \begin{align} \frac{\partial\,\mathbb{E}[R_t]}{\partial H_t(a)}&=\frac{\partial}{\partial H_t(a)}\left[\sum_x\pi_t(x)q_\ast(x)\right]\\ &=\sum_xq_\ast(x)\frac{\partial \pi_t(x)}{\partial H_t(a)}\\ &=\sum_x\big(q_\ast(x)-B_t\big)\frac{\partial \pi_t(x)}{\partial H_t(a)} \end{align} $$

其中 $B_t$ 被称为 baseline，它能被加进来的原因就是 $\sum_x\frac{\partial \pi_t(x)}{\partial H_t(a)}=0$ ——刚刚提到的 Softmax 的性质。然后对求和中每一项乘以 $\pi_t(x)/\pi_t(x)​$ 得到

$$ \begin{align} \frac{\partial\,\mathbb{E}[R_t]}{\partial H_t(a)}&=\sum_x\pi_t(x)\big(q_\ast(x)-B_t\big)\frac{\partial \pi_t(x)}{\partial H_t(a)}/\pi_t(x)\\ &=\mathbb{E}\left[\big(q_\ast(A_t)-B_t\big)\frac{\partial \pi_t(A_t)}{\partial H_t(a)}/\pi_t(A_t)\right]\\ &=\mathbb{E}\left[\big(R_t-\bar{R}_t\big)\frac{\partial \pi_t(A_t)}{\partial H_t(a)}/\pi_t(A_t)\right] \end{align} $$

这里我们选择 baseline 为 $B_t=\bar{R}_t$，并且用 $R_t$ 来替换 $q_\ast(A_t) $ ——因为 $q_\ast(A_t)=\mathbb{E}[R_t\mid A_t]$ 和全期望公式。

现在把 $\frac{\partial \pi_t(A_t)}{\partial H_t(a)}​$ 这一项拿出来分析，一般地，有

$$ \begin{align} \frac{\partial \pi_t(x)}{\partial H_t(a)}&=\frac{\partial}{\partial H_t(a)}\pi_t(x)\\ &=\frac{\partial}{\partial H_t(a)}\left[\frac{e^{H_t(x)}}{\sum_{y=1}^ke^{H_t(y)}} \right]\\ &=\frac{\frac{\partial e^{H_t(x)}}{\partial H_t(a)}\sum_{y=1}^ke^{H_t(y)}-e^{H_t(x)}\frac{\partial \sum_{y=1}^ke^{H_t(y)}}{\partial H_t(a)}}{\left(\sum_{y=1}^ke^{H_t(y)}\right)^2}\tag{quotient rule}\\ &=\frac{\mathbb{I}_{x=a}e^{H_t(x)}\sum_{y=1}^ke^{H_t(y)}-e^{H_t(x)}e^{H_t(a)}}{\left(\sum_{y=1}^ke^{H_t(y)}\right)^2}\\ &=\frac{\mathbb{I}_{x=a}e^{H_t(x)}}{\sum_{y=1}^ke^{H_t(y)}}-\frac{e^{H_t(x)}e^{H_t(a)}}{\left(\sum_{y=1}^ke^{H_t(y)}\right)^2}\\ &=\mathbb{I}_{x=a}\pi_t(x)-\pi_t(x)\pi_t(a)\\ &=\pi_t(x)\big(\mathbb{I}_{x=a}-\pi_t(a)\big) \end{align} $$

故 $\frac{\partial \pi_t(A_t)}{\partial H_t(a)}=\pi_t(A_t)\big(\mathbb{I}_{a=A_t}-\pi_t(a)\big)​$，代入原式得

$$ \begin{align} &=\mathbb{E}\left[\big(R_t-\bar{R}_t\big)\pi_t(A_t)\big(\mathbb{I}_{a=A_t}-\pi_t(a)\big)/\pi_t(A_t)\right]\\ &=\mathbb{E}\left[\big(R_t-\bar{R}_t\big)\big(\mathbb{I}_{a=A_t}-\pi_t(a)\big)\right] \end{align} $$

回想一下：我们的目标是将性能的梯度写成某个我们可以在每一轮采样的值的期望，正如上式所做的。接下来就是将 $\rm GA​$ 式中的梯度替换为上式期望的一个采样，得到

$$ H_{t+1}(a)= H_t(a)+\alpha\big(R_t-\bar{R}_t\big)\big(\mathbb{I}_{a=A_t}-\pi_t(a)\big),\text{ for all } a $$

这就是我们之前的更新公式 $\rm SGA\quad\blacksquare$

四、Associative Search (Contextual Bandits)

本文之前讨论的算法都仅仅只考虑一个状态下如何选择动作，而不需要将不同的动作与不同的场景联系 (associate) 起来。然而，在更常见的强化学习中，agent 面临的往往是多个状态。

例如，你面临多台 k-armed 老虎机，每个老虎机的性质都不同（每个拉杆对应的回报的期望不同）。每次你都会被要求去拉被随机选出来的一台老虎机。在这种情况下，要使得累计回报最大，就需要辨别不同的状态（这是哪一台老虎机？）

因此，在这种情况下， agent 需要不仅仅要在每个状态进行搜索 (searching)，还要将动作的选择与状态联系 (association) 起来。这就是所谓的 Associative Search，也叫 Contextual Bandits。

Associative Search 是 Multi-armed Bandit 问题与完整强化学习 (full reinforcement learning) 之间的过渡。它相比 Multi-armed Bandit 问题，增加了多个状态；但相比完整的强化学习，又少了点性质：它的动作选择不会影响下一个状态。（在下一篇文章中将对强化学习进行一个数学上的形式化描述 (FMDP)，届时读者将会对“动作影响下一个状态”有更好的理解。）

参考