【上一篇 1 强化学习（Reinforcement Learning, RL）初步介绍 】 【下一篇 3 有限马尔可夫决策过程（Finite Markov Decision Processes）】

RL与其他学习方法最大的区别在于它使用的训练信息是对 actions 的评价，而其他方法是给出正常的 actions。这一次的教程就是通过一个具体的案例来对 RL 问题中的 “evaluative aspect” 进行介绍。

１ 问题介绍：k-armed Bandit Problem

Multi-armed bandit 原本是从赌场中的多臂老虎机的场景中提取出来的数学模型，其中 arm 指的是老虎机（slot machine）的拉杆，bandit 是多个拉杆的集合，$bandit=ar{m}_1,ar{m}_2,\dots \dots ,ar{m}_k$。每个 bandit setting 对应一个回报函数（reward function），现在需要经过多次的尝试，来评估每个 bandit 的 reward，这个问题的目标是如何最大化总的回报。

显然，在这个问题中一共包含 $k$ 种 actions （因为有 $k$ 个拉杆），每个 action 都有一个期望的或者平均的 reward，称为是这个 action 的 $value$。记时间 $t$ 选择的行为是 $A_t$，其相对应的 reward 为 $R_t$，任意一个行为 $a$ 的 value 记为 $q_{\ast }(a)$，因此，$a$ 期望的 reward 为： $$q_{\ast }(a)=E[R_t|A_t=a]$$

显然，如果我们知道了每个 action 的 value，只有每次选择具有最大 value 的 action 就可以解决这个问题，这里令 action $a$在时间 $t$ 的估计 value 为 $Q_t(a)\approx q_{\ast }(a)$。

实验中，在当前时刻，具有估计的 value 值最大的 action 就称为是 greedy actions，如果在下个时刻选择的是 greedy actions，那么这次选择就可以视为是 exploiting 当前已有的信息，相反如果在下个时刻选择的是 non-greedy actions，那么这次选择就可以视为是 exploring。下面将会介绍几种平衡 exploit 和 explore 的方法。

2 Action-Value Methods

对一个行为 $a$，最简单的评估方法就是用行为 $a$ 所返回的所有 rewards 进行平均，即： $$Q_{\ast }(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}}$$ 其中， $$l_{predicate}=\{\begin{array}{ll}1,& predicateistrue\\ 0,& otherwise\end{array}$$

若分母为 0，则令 $Q_{\ast }(a)$ 为一个默认的值。根据大数理论，当分母趋于无穷时，则 $Q_t(a)$ 趋近于 $q_{\ast }(a)$，我们将这种估计 action values 的方法称为是 sample-average 方法。

最简单的策略就是每个时间 $t$ 都选择当前的 greedy actions，这种方法称为是 greedy action selection method，该方法的选择策略可以记为是： $$A_t\doteq {argmax}_a{Q}_t(a)$$

可以看出，greedy action selection 每次都只会对当前的信息进行开发，而不会探索新的信息，对这种方法最简单的改进方式就是引入一个小的变量 $\epsilon$，每次选择 actions 时，以 $1-\epsilon$ 的概率选择 greedy acitons，以 $\epsilon$ 的概率从所有 actions 中以相等的概率随机选择，这种方法称为是 $\epsilon$-greedy method，这种方法的优点在于在无限的时间下所有的 actions 都有机会被选择过，因此所有的 $Q_t(a)$ 都会趋近于 $q_{\ast }(a)$ 。

3 Incremental Implementation（增量式实现）

上一节介绍的方法是将所有的历史信息全部记录下来然后求平均，不仅耗费内存也浪费时间，这一节介绍的增量式的方法仅耗费固定大小的内存，并且每个时间都可以进行更新。

为了简化符合，这里只关注一个action，令 $R_i$ 代表第 $i$ 次选择这个 action 获得的 reward，$Q_n$ 代表这个 action 被选择了 $n-1$ 次之后评估的 value 值，则有下面的等式成立：

$$\begin{array}{rl}{Q}_{n+1}& \doteq \frac{1}{n}\sum _{i=1}^n{R}_i\\ & =\frac{1}{n}(R_n+\sum _{i=1}^{n-1}{R}_i)\\ & =\frac{1}{n}(R_n+(n-1)\frac{1}{n-1}\sum _{i=1}^{n-1}{R}_i)\\ & =\frac{1}{n}(R_n+(n-1)Q_n)\\ & =\frac{1}{n}(R_n+n{Q}_n-Q_n)\\ & =Q_n+\frac{1}{n}[R_n-Q_n]\end{array}$$

上式中最后的更新规则可以写作是： $$NewEstimate\leftarrow OldEstimate+StepSize[Target–OldEstimate]$$

其中，表达式 $[Target–OldEstimate]$ 是估计中的 $error$ 项，可以看出在增量式学习方法中的 $StepSize$项为 $1/n$，是随时间不断变化的，之后会用 $\alpha$ 或 ${\alpha }_t(a)$ 来代表 step-size 参数。

算法的伪代码为：

4、针对非固定的问题

之前考虑的都是一个不变的环境，但如果 bandit 随时间不断变化该如何处理呢？这时有必要将当前的 rewards 赋予更高的权重，而过去的赋予较小的权重，最常用的实现方法就是使用一个固定的 step-size 参数，例如将上一节中的更新规则改为： $$Q_{n+1}\doteq Q_n+\alpha [R_n-Q_n]$$

其中，$\alpha \in (0,1]$ 是个常数。对该式进行分解就会得到

$$\begin{array}{rl}{Q}_{n+1}& \doteq 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 {)}^2{Q}_{n-1}\\ & =\alpha R_n+(1-\alpha )\alpha R_{n-1}+(1-\alpha {)}^2\alpha R_{n-2}+\cdots +(1-\alpha {)}^{n-1}\alpha R_1+(1-\alpha {)}^n{Q}_1\\ & =(1-\alpha {)}^n{Q}_1+\sum _{i=1}^n\alpha (1-\alpha {)}^{n-i}{R}_i\end{array}$$

因为 $(1-\alpha {)}^n+{\sum }_{i=1}^n\alpha (1-\alpha {)}^{n-i}=1$, 因此可以将上式视为是一种加权平均。由于 $1-\alpha <1$，因此 $i$ 越大赋予 $R_i$ 的权重越大。通常将这种更新方式称作是 exponential, recency-weighted average。

5 优化的初始值

前面介绍的几种方法都与初始的 action-value 的评估值 $Q_1(a)$ 有关，在统计学方面这称为是“有偏的（biased）”。对于 sample-average 方法，这种 bias 在所有的 actions 都被最少选择过一次之后会消失；而对于具有常量 $\alpha$ 的方法，这种 bias 是一直存在的。但是这种 bias 也不常常是有坏处的，也可以被利用起来，例如我们考虑 10-armed testbed 的问题，如果所有的初始值全部设为 $0$，第一个被随机选择的 action 只要回报不是 $0$ 一定会成为其中的 greedy action，但如果所有的初始值全部设为 $5$，若初始选择的 action 的回报小于 $5$ 则它的估计值就会降低，从而促进算法进行 explore 的过程。

6 Upper-Confidence-Bound Action Selection

在 action 选择过程中，greedy actions 是当前认为最优的行为，但是最优的行为可能并非是它们，因此就需要 exploration 过程，$\epsilon$-greedy action selection 强制使 non-greedy 的行为也有机会被选择，但这并不是最优的 exploration 方式，最好的方式应该是将每个 action 的评估值和不确定性值均考虑在内，这种有效的选择规则为： $$A_t\doteq {argmax}_a[Q_t(a)+c\sqrt{\frac{\log t}{N_t(a)}}]$$

其中 $log$ 指的是自然对数，$N_t(a)$ 指的是行为 $a$ 在时间 $t$ 已经被选择的次数，常数 $c>0$ 代表的是赋予 exploration 的权重。

这种选择方式称为是 Upper Confidence Bound (UCB) Action Selection，选择函数中的平方根项代表了对行为 $a$ 的不确定性，分子中对时间 $t$ 取自然对数是为了使分子的增长速度减慢。

参考文献 [1] Reinforcement Learning: An Introduction, Richard S. Sutton and Andrew G. Barto [2] UCL Course on RL