【西瓜书】第十六章 强化学习

本文是周志华老师《机器学习》第十六章强化学习的学习笔记。

任务与奖励

强化学习通常用马尔科夫决策过程(Markov Decision Process, MDP)来描述. 其对应一个四元组:

　　

$$E=(X, A, P, R)$$

其中$E$为环境, $X$为状态空间, $A$为动作空间, $P:X\times A\times X$为状态转移概率, $R: X\times A\times X$为奖励.
机器要做的就是在环境中不断尝试而学的一个策略(policy)$\pi: X\times A$, 策略的优劣则取决于长期执行这一策略后得到的累积奖励. 这里的计算方式有多种, 常用的有”T步累计奖励”$\mathbb{E}[\frac{1}{T}\sum{t=1}^T]r_t$和$\gamma$折扣累计奖励$\mathbb{E}[\sum{t=0}^{+\infty}\gamma^tr_{t+1}]$.

K-摇臂赌博机

我们先来考虑最简单的情况,即只有一步操作. 在这个设定下,我们需要考虑两方面: 一是需要知道每个动作对应的奖励, 二是要执行奖励最大的动作. 如果每个动作的奖励是确定值, 那么我们试一遍所有动作就能找到这个奖励最大的动作. 但是往往奖励是一个概率分布, 那么此时这个单步强化学习任务就对应了”K-摇臂赌博机”模型:

K-摇臂赌博机有K个摇臂, 赌徒在投入一个硬币后可以选择按下其中一个摇臂, 每个摇臂都以一定概率吐出硬币, 当然赌徒并不知道这个概率. 赌徒的目标就是以一定的策略最大化自己的奖赏, 即获得最多硬币.

最简单的方法有:

• 仅考虑获知每个摇臂的期望奖赏时, 可采用”仅探索(exploration only)”法, 将所有尝试机会平分给每个摇臂然后以每个摇臂各自的平均吐币概率作为其奖励期望的近似估计
• 仅考虑执行奖励最大的动作, 可采用”仅利用(exploitation only)”法, 按下目前最优的摇臂

显然这两者是矛盾的,因为尝试次数有限, 加强了一方就会削弱另一方,这就是强化学习面临的探索-利用困境(Exploration-Exploitation dilemma).

$\epsilon$贪心

$\epsilon$贪心基于一个概率来对探索和利用进行折中: 每次尝试时, 以$\epsilon$的概率进行探索, 以$1-\epsilon$进行利用. 令$Q(k)$记录摇臂$k$的平均奖赏, 若摇臂$k$被尝试了$n$次, 得到的奖赏为$v_1, v_2, \cdots, v_n$则平均奖赏为:

$$Q(k)=\frac{1}{n}\sum_{i=1}{n}v_i$$

另初始时$Q0(k)=0$, 对于任意的$n\ge 1$若第$n-1$次尝试后的平均奖励为$Q{n-1}(k)$, 则经过第$n$次奖励后平均奖励更新为:

$$Q _ { n } ( k ) = \frac { 1 } { n } \left( ( n - 1 ) \times Q _ { n - 1 } ( k ) + v _ { n } \right)$$

那么整个$\epsilon$贪心算法的描述如下:

当摇臂奖励的不确定性较大时, 则需要更多探索, 此时则需要较大的$\epsilon$, 否则则可以降低该值. 当尝试次数非常大, 一段时间后摇臂奖励的期望稳定,则可以令$\epsilon$随着尝试次数增加而逐渐减小.

softmax

softmax算法是另一种对探索和利用进行这种的算法, 它基于Blotzmann分布:

$$P ( k ) = \frac { e ^ { \frac { Q ( k ) } { \tau } } } { \sum _ { i = 1 } ^ { K } e ^ { \frac { Q ( i ) } { \tau } } }$$

其中$Q(i)$为当前摇臂的平均奖励,$\tau$为温度, 其越小则平均奖励搞得摇臂被选取的概率越高, 当$\tau$趋于0时策略将趋于仅利用, $\tau$趋于无穷大时策略则将趋于仅探索.

$\epsilon$贪心算法和softmax算法的优劣取决于具体应用.

有模型学习

下面进一步考虑多步强化学习任务, 我们暂且假定任务对应的马尔可夫决策过程四元组$E=(X,A,P,R)$均为已知, 即”模型已知”. 在已知模型的环境中学习称作”有模型学习”(model-based learing). 这里为了便于讨论, 我们假设状态空间和动作空间都是有限的.

策略评估

我们令函数$V^\pi(x)$表示从状态x出发, 使用策略$\pi$所带来的累计奖励, 函数$Q^\pi(x, a)$表示从状态x出发,执行动作$a$后再使用策略$\pi$带来的累计奖励. 前者称作状态值函数, 后者称作状态-动作值函数, 分别表示指定状态和指定状态-动作上的累计奖励.
针对之前定义过的两种累计奖励(T步和$\gamma$折扣), 我们有状态值函数(上面是T步, 下面是$\gamma$折扣):

$$\left\{ \begin{array} { l } { V _ { T } ^ { \pi } ( x ) = \mathbb { E } _ { \pi } \left[ \frac { 1 } { T } \sum _ { t = 1 } ^ { T } r _ { t } | x _ { 0 } = x \right] } \\ { V _ { \gamma } ^ { \pi } ( x ) = \mathbb { E } _ { \pi } \left[ \sum _ { t = 0 } ^ { + \infty } \gamma ^ { t } r _ { t + 1 } | x _ { 0 } = x \right] } \end{array} \right.$$

同样的,状态-动作值函数为:

$$\left\{ \begin{array} { l } { Q _ { T } ^ { \pi } ( x , a ) = \mathbb { E } _ { \pi } \left[ \frac { 1 } { T } \sum _ { t = 1 } ^ { T } r _ { t } | x _ { 0 } = x , a _ { 0 } = a \right] } \\ { Q _ { \gamma } ^ { \pi } ( x , a ) = \mathbb { E } _ { \pi } \left[ \sum _ { t = 0 } ^ { + \infty } \gamma ^ { t } r _ { t + 1 } | x _ { 0 } = x , a _ { 0 } = a \right] } \end{array} \right.$$

由于MDP的马尔可夫性质(系统下一时刻的状态仅由当前时刻的状态决定而不依赖于以往任何状态), 因此值函数可以写成简单的递归形式, 对于T步累积奖励:

$$V^\pi_T(x)= \sum _ { a \in A } \pi ( x , a ) \sum _ { x ^ { \prime } \in X } P _ { x \rightarrow x ^ { \prime } } ^ { a } \left( \frac { 1 } { T } R _ { x \rightarrow x ^ { \prime } } ^ { a } + \frac { T - 1 } { T } V _ { T - 1 } ^ { \pi } \left( x ^ { \prime } \right) \right)$$

对于$\gamma$折扣累积奖励有:

$$V _ { \gamma } ^ { \pi } ( x ) = \sum _ { a \in A } \pi ( x , a ) \sum _ { x ^ { \prime } \in X } P _ { x \rightarrow x ^ { \prime } } ^ { a } \left( R _ { x \rightarrow x ^ { \prime } } ^ { a } + \gamma V _ { \gamma } ^ { \pi } \left( x ^ { \prime } \right) \right)$$

这里是一种动态规划算法, 对于T步奖励而言具体算法描述为:

只要T轮迭代就能算出精确的值函数.

而由于$\gamma$折扣累计奖励的$\gamma^t$在$t$很大时趋近于0,因此也可以用类似的算法. 计算得到状态值函数后, 就可以直接计算处状态-动作值函数:

$$\left\{ \begin{array} { l } { Q _ { T } ^ { \pi } ( x , a ) = \sum _ { x ^ { \prime } \in X } P _ { x \rightarrow x ^ { \prime } } ^ { a } \left( \frac { 1 } { T } R _ { x \rightarrow x ^ { \prime } } ^ { a } + \frac { T - 1 } { T } V _ { T - 1 } ^ { \pi } \left( x ^ { \prime } \right) \right) } \\ { Q _ { \gamma } ^ { \pi } ( x , a ) = \sum _ { x ^ { \prime } \in X } P _ { x \rightarrow x ^ { \prime } } ^ { a } \left( R _ { x \rightarrow x ^ { \prime } } ^ { a } + \gamma V _ { \gamma } ^ { \pi } \left( x ^ { \prime } \right) \right) } \end{array} \right.$$

策略改进

有了评估手段后, 我们希望将策略进行不断改进直到得到最优策略. 理想的策略应该可以最大化累积奖励:

$$\pi ^ { * } = \underset { \pi } { \arg \max } \sum _ { x \in X } V ^ { \pi } ( x )$$

最优策略所对应的值函数$V^*$称为最优值函数,即:

$$\forall x \in X : V ^ { * } ( x ) = V ^ { \pi ^ { * } } ( x )$$

由于最优值函数的累积奖励值已经达到最大,因此我们求最优值函数可以将之前对动作求和改成取最优:

$$V ^ { * } ( x ) = \max _ { a \in A } Q ^ { \pi ^ { * } } ( x , a )$$

也就可以得到最优状态-动作值函数:

$$\left\{ \begin{array} { l } { Q _ { T } ^ { * } ( x , a ) = \sum _ { x ^ { \prime } \in X } P _ { x \rightarrow x ^ { \prime } } ^ { a } \left( \frac { 1 } { T } R _ { x \rightarrow x ^ { \prime } } ^ { a } + \frac { T - 1 } { T } \max _ { a ^ { \prime } \in A } Q _ { T - 1 } ^ { * } \left( x ^ { \prime } , a ^ { \prime } \right) \right) } \\ { Q _ { \gamma } ^ { * } ( x , a ) = \sum _ { x ^ { \prime } \in X } P _ { x \rightarrow x ^ { \prime } } ^ { a } \left( R _ { x \rightarrow x ^ { \prime } } ^ { a } + \gamma \max _ { a ^ { \prime } \in A } Q _ { \gamma } ^ { * } \left( x ^ { \prime } , a ^ { \prime } \right) \right) } \end{array} \right.$$

上述关于最优值函数的等式称作最优Bellman等式, 其唯一解是最优值函数.同时该等式揭示了非最优策略的改进方式: 将策略选择的动作改变当前最优动作.
由于值函数对于策略的每一点的改进都是单调递增的, 所以我们对当前策略可以放心的将其修改为:

$$\pi ^ { \prime } ( x ) = \underset { a \in A } { \arg \max } Q ^ { \pi } ( x , a )$$

当$\pi’$和$\pi$一致而不再变化时, 就满足了最优Bellman等式, 即找到了最优策略.

策略迭代和值迭代

通过之前的了解,我们明白了评估策略和改进策略的方法, 二者结合起来就可以得到求解最优解的方法:
从一个初始策略开始, 先进行策略评估, 然后改进策略, 评估改进的策略, 再进一步改进, 重复步骤知道策略收敛,这种做法称为策略迭代(policy iteration). 下面给出了基于T步累计奖赏策略评估的策略迭代算法. 这种算法在每次改进策略后都需要重新进行策略评估, 这就较为耗时.

另外,我们可以将策略改进视作值函数的改善, 这样就能得到:

$$\left\{ \begin{array} { l } { V _ { T } ( x ) = \max _ { a \in A } \sum _ { x ^ { \prime } \in X } P _ { x \rightarrow x ^ { \prime } } ^ { a } \left( \frac { 1 } { T } R _ { x \rightarrow x ^ { \prime } } ^ { a } + \frac { T - 1 } { T } V _ { T - 1 } \left( x ^ { \prime } \right) \right) } \\ { V _ { \gamma } ( x ) = \max _ { a \in A } \sum _ { x ^ { \prime } \in X } P _ { x \rightarrow x ^ { \prime } } ^ { a } \left( R _ { x \rightarrow x ^ { \prime } } ^ { a } + \gamma V _ { \gamma } \left( x ^ { \prime } \right) \right) } \end{array} \right.$$

于是也可以得到值迭代算法:

无论是策略迭代还是值迭代, 它们都是基于动态规划的寻优问题.

免模型学习

在实际的强化学习任务中, 环境的转移概率和奖赏函数等等往往是未知的,此时需要学习算法不依赖于环境建模, 称作”免模型学习”(model-free learning), 显然, 相比有模型学习, 这个任务困难得多.

蒙特卡罗强化学习

在面模型情况下, 遇到的第一个问题是模型未知带来的无法评估策略. 这里一种替代的方法是多次”采样”取平均累积奖励作为期望累计奖励. 这就称作蒙特卡洛强化学习. 在这种情况下, 更适用于使用T步累积奖励的强化学习任务.
同时,由于模型未知, 因此由状态值函数$V$求得状态-动作值函数$Q$的难度也增加, 因此需要直接估计状态-动作值函数.

那么,在模型未知的情况下, 我们需要从起始状态开始, 依据某张策略采样, 执行T步得到轨迹, 接着对轨迹中的每一对状态-动作, 计算其奖赏之和, 作为该状态-动作对的一次累积奖赏采样值. 对多条采样得到的轨迹数据取平均, 来得到状态-动作值函数的估计.

这就存在一个问题, 对于一个确定性策略, 采样得到的轨迹是相同的, 这里可以使用折中的方法例如$\epsilon$-贪心法: 在每次执行动作时,以$\epsilon$的概率从所有动作中随机选取, 以$1-\epsilon$的概率选取最优动作. 这里标记确定性的策略$\pi$为原始策略, 而基于原始策略的$\epsilon$-贪心策略记作$\pi$. 当前最优动作被选中的概率为$1-\epsilon + \frac{\epsilon}{|A|}$, 每个非最优动作被选中的概率为$\frac{\epsilon}{|A|}$

在策略改进上,由于对于任意原始策略的$\epsilon$贪心策略仍然保持单调性, 因此我们可以使用和前述相同的方法来进行策略改进. 下图给出了算法的具体描述, 由于这里评估和改进的是同一个策略,因此又称作”同策略”(on-policy)蒙特卡洛强化学习算法.

但是实际上我们引入贪心策略仅仅是为了便于评估而不是为了最终使用, 那么我们能否尽在评估时引入贪心而在策略改进时改进原始策略呢.

我们知道, 函数$f$在概率$p$下的期望可以表达为: $\mathbb { E } [ f ] = \int _ { x } q ( x ) \frac { p ( x ) } { q ( x ) } f ( x ) \mathrm { d } x$
这里的$q(x)$互相消掉不会对结果有影响, 但是我们同时也可以将其看作是$\frac { p ( x ) } { q ( x ) } f ( x )$ 在分布$q$下的期望. 因此该期望可以通过采样估计为:

$$\hat { \mathbb { E } } [ f ] = \frac { 1 } { m } \sum _ { i = 1 } ^ { m } \frac { p \left( x _ { i } ^ { \prime } \right) } { q \left( x _ { i } ^ { \prime } \right) } f \left( x _ { i } ^ { \prime } \right)$$

回到问题上来, 使用策略$\pi$的采样轨迹来评估策略$\pi$其实就是求累计奖赏估计期望:

$$Q ( x , a ) = \frac { 1 } { m } \sum _ { i = 1 } ^ { m } r _ { i }$$

其中$r_i$表示第$i$条轨迹上自状态$x$到结束的累积奖励. 这时, 我们需要改用策略$\pi’$的采样轨迹来评估策略$\pi$, 这时需要对累积奖励加权:

$$Q ( x , a ) = \frac { 1 } { m } \sum _ { i = 1 } ^ { m } \frac { P _ { i } ^ { \pi } } { P _ { i } ^ { \pi ^ { \prime } } } r _ { i }$$

其中$P^{\pi}_i$和$P^{\pi’}_i$分别表示两个策略产生第i条轨迹的概率, 并有:

$$\frac{P^\pi}{P^{\pi'}} = \prod_{i=0}^{T-1}\frac{\pi(x_i, a_i)}{\pi'(x_i, a_i)}$$

当然$\pi$为确定性策略而$\pi’$为$\pi$的$\epsilon-$贪心策略时, 则$\pi(x_i, a_i)$对于$a_i=\pi(x_i)$始终为1, $\pi’(x_i, a_i)$为$\frac{\epsilon}{|A|}$或$1-\epsilon + \frac{\epsilon}{|A|}$, 这就是如下所谓的”异策略”(off-policy)蒙特卡罗强化学习算法:

时序差分学习

由于蒙特卡罗算法没有充分利用强化学习任务的MDP结构,因此效率很低, 一种结合了蒙特卡罗方法思想和动态规划的方法叫做时序差分学习(Temporal Difference, TD).

蒙特卡罗算法的本质是多次采样取平均作为期望,但是它的求平均是在每个完整的采样轨迹结束后进行的, 但是实际上这个过程可以增量式的实时更新:

$$Q _ { t + 1 } ^ { \pi } ( x , a ) = Q _ { t } ^ { \pi } ( x , a ) + \frac { 1 } { t + 1 } \left( r _ { t + 1 } - Q _ { t } ^ { \pi } ( x , a ) \right)$$

上式的后一项就是增量, 更一般的可以将$\frac{1}{t-1}$换成一个系数$\alpha_{t+1}$ (通常设置为一个较小的正数).

以$\gamma$折扣累积奖赏为例, 就有:

$$Q^\pi_{t+1}(x, a)=Q^\pi_t(x,a) + \alpha (R^a_{x\rightarrow x'} + \gamma Q^\pi_t(x', a') -Q^\pi_t(x,a))$$

由该式就可以得到如下的算法,该算法每次更新值函数都需要知道前一步的状态(State), 前一步的动作(action), 奖赏(award), 当前状态(state)和将要执行的动作(action),因此该算法称作Sarsa算法, 这是一个同策略算法.

Sarsa的异策略改进叫做Q-learning算法, 算法步骤如下.

模仿学习

从人类专家等渠道得到决策过程范例并进行学习的任务叫做模仿学习(imitation learning).

直接模仿学习

假设我们获得一批专家的决策轨迹数据, 那么我们可以其中所有的状态-动作对抽取出来, 将动作作为标签, 状态作为特征来训练一个分类/回归学习器, 并由此得到策略模型. 该策略可以作为强化学习的初始策略, 再用强化学习方法基于环境反馈进行改进.

逆强化学习

现实任务中, 奖赏函数的设计非常困难, 例如浇水和施肥对植物生长的好处如何在不同状态下量化? 一种想法就是从人类专家提供的范例数据中反推出奖赏函数, 这也被称作逆强化学习(inverse reinforcement learning). 其基本思想是: 想要使最优策略产生的决策轨迹和范例数据一直, 我们需要寻求某种奖励函数使得范例数据最优, 然后利用这个奖励函数来训练强化学习策略.

不妨假设奖励函数为状态特征的线性函数, 即$R(x)=w^Tx$, 则策略的累计奖励可以写作:

$$\rho^\pi=\mathbb{E}[\sum_{t=0}^{+\infty}\gamma^tw^Tx_t|\pi]$$

将状态向量的期望$\mathbb{E}[\sum_{t=0}^{+\infty}\gamma^tx_t | \pi]$简写为$\bar{x}^\pi$. 这里为了求状态向量的期望, 我们可以用蒙特卡罗算法通过采样来近似期望, 而范例数据刚好可以看作最优策略的采样, 因此我们可以将每个范例轨迹上的状态加权求和再平均记作$\bar{x}’$, 那么对于最优奖赏函数$R(x)=w’^{T}x$和其他任意策略产生的$\bar{x}^\pi$有:

$$w'^T\bar{x}' - w'^T\bar{x}^\pi = w'^T(\bar{x}'-\bar{x}^\pi)\ge 0$$

接着若能对所有策略计算$(\bar{x}’ - \bar{x}^\pi)$则可以解除奖励函数的参数:

$$w'=\arg \max_w \min_\pi w^T(\bar{x}'-\bar{x}^\pi)$$

不过由于我们无法获得所有策略, 所以一个较好的方法是从随即策略开始, 迭代求解更好的奖励函数.
具体算法如下: