强化学习系列（二）：Multi-armed Bandits(多臂*问题）

一、前言

强化学习系列（一）：强化学习简介中我们介绍了强化学习的基本思想，和工作过程，我们提到了强化学习的一大矛盾：平衡Exploration and Exploitation。本章我们以Multi-armed Bandits(多臂*问题）为例子，简单介绍一下针对该问题的Exploration and Exploitation平衡方法。

二、问题描述

想想一下你可以重复一个选择过程，每次有k个选项或动作可供选择，每次选择一个动作后会获得相应的奖励。你的目标是为了最大化k次后的奖励。这个抽象模型缘起与赌场中的Multi-armed bandits(多臂*)，其中 arm 指的是*（slot machine）的拉杆，bandit 是多个拉杆的集合 bandit=arm1,arm2,……,armk$bandit=ar{m}_1,ar{m}_2,\dots \dots ,ar{m}_k$。
假设 t 时刻我们选择动作为At$A_t$, 对应的奖励为Rt$R_t$, 则 t 时刻的任意action a 的期望奖励（value）可以表示为
q∗(a)=E[Rt|At=a]$q_{\ast }(a)=E[R_t|A_t=a]$
如果我们知道每个action对应的value，那么我们只需要每次都选择最高的那个value对应的action即可，但事实却是我们在玩*之前，不知道每个action确切的value，我们可以通过多次测试来估计每个action的value,将t 时刻的action a对应的估计价值（estimated value) 记作 Qt(a)$Q_t(a)$ ,我们的目标是使得 Qt(a)$Q_t(a)$尽可能的接近q∗(a)$q_{\ast }(a)$,然后根据Qt(a)$Q_t(a)$选择 a.

三、Action-value function

3.1 sample-average方法

最简单的value 估计方式就是sample-average（采样平均），即
Qt(a)≐sum of rewards when a taken prior to tnumber of times a taken prior to t=∑t−1i=1Ri⋅lAi=a∑t−1i=1lAi=a$Q_t(a)\doteq \frac{sumofrewardswhenatakenpriortot}{numberoftimesatakenpriortot}=\frac{\sum _{i=1}^{t-1}{R}_i\cdot l_{A_i=a}}{\sum _{i=1}^{t-1}{l}_{A_i=a}}$
其中，
lpredicate={1,0,predicate is trueotherwise$l_{predicate}=\{\begin{array}{ll}1,& predicateistrue\\ 0,& otherwise\end{array}$
通过增加实验次数，当实验次数趋于无穷大时，Qt(a)$Q_t(a)$ 趋于 $q_*(a),这种方法称为sample-average。

3.2 greedy 与 ϵ$ϵ$-greedy

greedy方法：

如果我们每次都选择最大value对应的action，即

At≐argmaxaQt(a)$A_t\doteq {argmax}_a{Q}_t(a)$

那么我们采取的是greedy policy，也就是我们将 Exploitation 运用到了极致，我们只关注我们可以获得的信息中的最优解，但没有对环境进行探索。有时候，当前最优是短期最优，在长远角度看来并不是最优，所以需要对环境进行探索。

ϵ$ϵ$-greedy：

如果我们会在一些时间内选择最大value对应action外的其他action，则表明我们对环境进行了Exploration。ϵ$ϵ$-greedy方法在greedy方法基础上进行改进：

At={argmaxaQt(a),a′(is different from argmaxaQt(a)),1−ϵϵ$A_t=\{\begin{array}{ll}argma{x}_a{Q}_t(a),& 1-ϵ\\ a^{\prime }(isdifferentfromargma{x}_a{Q}_t(a)),& ϵ\end{array}$

入一个小的变量 ε，每次选择actions时，以ϵ$ϵ$的概率选择最大value对应action之外的action a’,以1−ϵ$1-ϵ$的概率选择最大value对应的action a.

四、Incremental Implementation（增量式实现）

上一节介绍的sample average方法是将所有的历史信息全部记录下来然后求平均，如果历史记忆很长，甚至无限，那么直接求解将受到内存和运行时间的限制。下面将结合数学中的迭代思想推导出增量式的求解方法，该方法仅耗费固定大小的内存，且可以单步更新。
为了简化表达，我们只关注一个action,假设Ri$R_i$是第 i 次选择这个action所获得的reward， 将这个action第n 次被选择的estimate value表示为Qn+1$Q_{n+1}$，

这样每次只需要存储 Qn$Q_n$和n，就可以算出新的reward。这种方式称为增量式求解，伪代码如下：

上述过程可以简写为：
NewEstimate←OldEstimate+StepSize [Target–OldEstimate]$NewEstimate\leftarrow OldEstimate+StepSize[Target–OldEstimate]$

五、针对非固定性问题

前面讨论的问题是一个不变的问题，即bandits所获得的reward每次都变化不大，但是如果bandits随着时间不断变化，即他所获得的reward变化较大，那么我们需要增加当前的reward的权重，以表示我们对当前reward影响的重视。

一种常用的方式是固定stepsize为α$\alpha$（0,1],这样更新公式表示为

其中，(1−a)n+∑ni=1α(1−α)n−i=1$(1-a{)}^n+\sum _{i=1}^n\alpha (1-\alpha {)}^{n-i}=1$,是一种加权平均法（ weighted averaged）,α(1−α)n−i$\alpha (1-\alpha {)}^{n-i}$作为一个reward Ri$R_i$第n-i 次被观测到的权重，其中 1−α<1$1-\alpha <1$,因此i 越大 Ri$R_i$的权重越大，这种更新方式被称作exponential recency-weighted average。

六、最优化初始值

上述方法都依赖于初始动作价值 Q1(a)$Q_1(a)$，在静态分析中叫做偏置（biased)，sample-average的偏置随着每个action至少被选择了一次而消失，而加权平均方法中的偏置随着实验次数的增加而减小。在实际应用中，偏置常常很有用，不仅可以用于提供关于reward的先验知识，也可以作为一种提升探索率的简单方法。
以10-armed testbed 的问题为例，如果所有的Q1(a)=0$Q_1(a)=0$，第一个被随机选择的action只要回报不是0一定会成为其中的 greedy action，假如我们另所有Q1(a)=5$Q_1(a)=5$，若初始选择的action的回报小于5则它的估计值就会降低，从而促进算法进行explore的过程。
这种小技巧通常叫做 optimistic initial values，因为他对exploration的驱动是短期且固有的，如果任务改变，会对exploration有新的需求，这个方法将不再适用，所以不能广泛应用于非固定性问题中。

七、Upper-Condience-Bound动作选取

上文提到了ϵ$ϵ$-greedy在随机选择action时无差别的对待每个action，如果在随机选择action时考虑每个action的隐含属性有利于找到最优action。这种隐含属性一般包括与最大值的接近度，以及估计错误率。常用的一种动作选取方法是Upper-Condience-Bound方法：
At≐argmaxa[Qt(a)+clntNt(a)‾‾‾‾‾√]$A_t\doteq {argmax}_a[Q_t(a)+c\sqrt{\frac{\ln t}{N_t(a)}}]$
其中，lnt$\ln t$ 表示时间 t的自然对数，Nt(a)$N_t(a)$表示从开始到 t 时刻内选择动作 a 的次数，c>0$c>0$ 用于控制探索率，当Nt(a)=0$N_t(a)=0$时，a 表示最优动作。

在10-arm testbed 问题中，比 ϵ$ϵ$-greedy表现好，但和 ϵ$ϵ$-greedy 相比，UCB不容易扩展到一般强化学习中，因为该方法有两个局限性：

• 解决不确定性问题比较难
• 不适用于状态空间较大的问题，尤其是使用逼近函数的问题中

（10-arm testbed问题描述：假设这里有2000个随机产生的k-arm bandit(k个摇臂的*）问题，此处k=10。对每一个*问题，可以按照均值为0 方差为1 的高斯分布选择10个不同的动作a。当运用学习方法在 t 时刻选择一个动作At$A_t$，真实reward Rt$R_t$符合均值为q∗(At）$q\ast (A_t）$(action values) 方差为1 的分布。）

八、Gradient Bendit Algorithms

我们说到可以通过估计价值函数来选择action，但这并不是唯一的方法，本节我们介绍一种通过偏好Ht(a)$H_t(a)$来选取action的方法Gradient Bendit Algorithms，偏好越大，越常选择。偏好和reward直接没有直接关系，偏好通过相对大小影响action的选择概率：

其中，πt(a)${\pi }_t(a)$表示t时刻选择action a 的概率。
这种算法通常用随机梯度下降实现：

九、总结

我们介绍了四种用于平衡 Exploration 和 Exploitation的方法：

• ϵ$ϵ$-greedy （在强化学习中应用广泛）
• UCB方法（通过增加出现次数少的action的选择概率来增强Exploration，UCB不容易扩展到一般强化学习中）
• Gradient Bendit Algorithms（不依据价值估计来选取动作，通过action偏好来选择action)
• 优化初始值（不能用于非固定性问题中）

Reinforcement Learning: an introduction