这一讲的问题很有意思—-利用与探索,有点类似哲学问题。举个例子,比如牛排的酱汁,你会选择一个没有吃过的酱汁,还是选择经典黑椒汁。在这个问题上,我和我老婆总是不一致。她总是坚定的选择黑椒汁(Exploitation),而我每次都想尝试新的酱汁(Exploration),不过最后不得不承认黑椒汁味道最好。可以看出探索是有代价的,这个例子里面探索的代价较大,比不上带来的收益。换个例子,比如近代欧洲的大航海时代,葡萄牙,西班牙,英国,荷兰这些本土面积较小的国家,正是通过探索,找到了比自己本国大得多的殖民地,并且带来了巨大的财富。探索有利有弊,关键是否根据自身情况合理使用。

回想一下强化学习的环境下,哪个地方需要对利用和探索之间做出权衡?前面多次提到的$\epsilon-$greedy的策略就是利用与探索的例子。这是一个非常navie的方法。本讲后面会讨论其他设计更加精细的利用和探索策略。但是,介绍此方法时不宜在强化学习环境下探讨,因为太多不相关的东西,容易分散注意力。一般都简化为多臂老虎机问题上探讨这类问题。

问题定义

假设有10个老虎机,每个老虎机中奖的概率分布不同(如下图),如果在有限的选择下找到最好的那个老虎机,这就是多臂老虎机问题,

可以看到,10个老虎机,有5个的收益是正数,5个是负数。那么如果准确快速的找到那些收益正的老虎机?定义动作值函数

\[q(a) = E[R_t|A_t = a]\]

其含义是动作为a的期望收益。上面的例子中,如果a=3,那么$q(3)=1.5$。我们不是先知,这个值无法得到,但是可以通过统计的方法估算出来,

\[Q_t(a) = \frac{\sum_{i=1}^{t-1}R_i I(A_i = a)}{\sum_{i=1}^{t-1} I(A_i = a)}\]

所以,经过很多步后,我们可以估算出每个动作a的值,然后选择用贪心策略,

\[A_t = \arg_a \max Q_t(a)\]

得到最优的动作a。理论上,上面的方法一定能够找到最优动作,但是实际情况是我们没有那么多赌资去计算出所有的$Q(a)$。所以,后面的所有方法都是如何在较短的资源(动作)下,快速找到最优动作,使得总体收益快熟收敛到最优。

$\epsilon-Greedy$老虎机算法

算法伪代码如下,核心思想就是每次选择时,留下$\epsilon$的概率随机选择动作(Exploitation),剩下的$1-\epsilon$概率用贪心策略选择动作(Exploration)。

更新规则可以总结为

\[NewEstimate \leftarrow OldEstimate + StepSize[Target - OldEstimate]\]

此规则在后面会反复提到。其意义是每次更新,都是朝目标target进行小小的一步。StepSize在上面的例子是$\frac{1}{n}$,不过更为通用的形式为$\alpha_t(a)$。

处理非静态(Nonstational)分布问题

前面提到的算法可以处理静态分布的问题,即每个老虎机的奖励分布是不变的。但是大多数情况新,需要处理非静态分布问题,尤其是在强化学习问题中。在此情况下,一般需要将近期的奖励的权重放大,而不是像上面那样近期的奖励的权重会越来越小。比较常用的做法是将StepSize设置为常量$\alpha$。那么更新策略跟改为

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

其中$\alpha \in (0,1] $。将此公式递归展开

\[\begin{align} Q_{n+1} &= \alpha R_n + (1-\alpha)Q_n \\ &= \alpha R_n + (1-\alpha)(\alpha R_{n-1} + (1-\alpha)Q_{n-1}) \\ &= \alpha R_n + \alpha(1-\alpha)R_{n-1} + (1-\alpha)^2 Q_{n-1} \\ &= \alpha R_n + \alpha(1-\alpha)R_{n-1} + \alpha(1-\alpha)^2 R_{n-2} + (1-\alpha)^3 Q_{n-2} \\ &= (1-\alpha)^n Q_1 + \sum_{i=1}^n \alpha(1-\alpha)^{n-i}R_i \qquad (1) \end{align}\]

展开式非常有特点,$Q_1$与$R_i$的系数之和为1,且均大于等于0,即$(1-\alpha)^n+ \sum_{i=1}^n \alpha(1-\alpha)^{n-i}=1$,可以认为$Q_{n+1}$是$Q_1$与$R_i$的加权平均值。如果更为通用一点,可以将$a_n(a)=a$代入上面的公式,

\[Q_{n+1} = (1-\alpha_n(a))^n Q_1 + \sum_{i=1}^n \alpha_i(a) (1-\alpha_i(a))^{n-i}R_i\]

即学习率随着步长和行为变化,一个著名的随机逼近理论证明如果$\alpha_n(a)$满足下面条件,那么$Q_{n+1}$收敛。

\[\sum_{n=1}^\infty \alpha_n(a) = \infty \qquad and \qquad \sum_{n=1}^\infty \alpha_n^2(a) < \infty\]

如果$\alpha_n(a) = \frac{1}{n}$,即平均值,那么满足上面条件,最后会收敛。如果$\alpha_n(a) = a$为常量,不满足第二个条件,所以不会收敛。虽然不收敛,但是对于Nonstational的环境下,确实需要这种特性才能捕捉到最优的策略。

优化初始值

初始值的优化可以鼓励探索,因为重上面的公式(1)可以发现初始值对最后的收益和有一定的影响的。我们可以通过先验知识设定初始值,比如如果老虎机的收益最高不操过1,那么我们可以认为的设定所有的老虎机的初始值都是5,这样必然导致每个老虎机都不太好,从而算法会尝试所有的老虎机,等价于探索过程。当然,这也增加了我们设置初始值的工作。不过,此方法对Nonstational的环境效果不好,因为初始值的作用效果不会一直存在,随之步数的增加,作用会越来越小。下面看看初始值的实现腰果,

优化的初始值虽然开始很慢,但是由于强制尝试了很多,后面的收敛速率就明显比$\epsilon-greedy$快。

Upper Confidence Bound动作选择

此方法根据Hoeffding不等式推导出来,用于估计每个Q(a)上界, \(A_t = \arg_a \max \left[Q_t(a) + c\sqrt{\frac{\ln t}{N_t(a)}} \right]\) 其中$N_t(a)$表示执行t次中,选择动作a的次数,$t$表示总的次数。直观上解释,就是$a$执行的越多,那么就越能够确定a的上界,$a$的整体值的估计就越真实;如果$a$执行的越少,那么a的上界越大,也就会越多的选择a,类似一种探索过程。$c$是一个常量,用于控制探索的粒度,$c$越大,探索越频繁。UCB也常用于MCTS过程中。

梯度老虎机算法

使用一种倾向性指标$H(a)$作为选择a的权重,权重用soft-max计算出概率。$H(a)$的绝对值没有意义,只是他们的相对值可以计算出选择a的概率。H(a)的更新算法如下

\[H_{t+1}(A_t) = H_t(A_t) + \alpha(R_t - \bar{R})(1-\pi(A_t)) \ and \\ H_{t+1}(a) = H_t(a) - \alpha(R_t - \bar{R})\pi(a) \ for \ all \ a \ne A_t\]

$\bar{R}$是收益均值,可以用增量方法计算。如果当前动作$A_t$收益大于均值,那么就会增加再次选择$A_t$的概率,否则会降低其概率。此算法的更新方式,本质上是随机梯度递增(SGA),具体推导可以参考Sutton教材(2017)2.8节。

总结

到目前为止,介绍了4种多臂老虎机问题,但是这里面忽略了状态,如果考虑状态那就是马尔科夫决策过程(MDP)问题,可以利用之前学习到的技术解决。虽然教材和讲义中大多以$\epsilon-greedy$作为动作选择策略,但是上面提到的算法等价,可以相互替换其在强化学习中使用。