增强学习

文档还在动态更新维护中

首先我们要解决的是「什么是增强学习」,即Reinforcement Learning,的问题。为了学习这一点我选择了比较权威的增强学习教材,Reinforcement Learning: An Introduction。这本书是增强学习的开创者安德鲁·巴托和理查德·S·萨顿所撰写。

之前接触过的典型的神经网络,比如用于处理图像输入的卷积神经网络(CNN)和擅长处理自然语言的递归神经网络(RNN),其特点都是在已有数据集上训练处模型以后,将模型用于生产环境。模型的训练和模型的使用是分离的。其实从人类自身的经验来说,学习和应用的过程其实是一体的。人通过与环境的交互一边学习,一边应用,互相促进。增强学习就是基于这种方式的机器学习手段。具体而言:

We explore the desing for machines that are effective in solving learning problems of scientific or economic interest, evaluating the designs through mathematical analysis or computational experiments. The approach we explore, called reinforcement learning, is much more forcused on goad-directed learning from interaction than are other approaches to machine learning

1 Reinforcement Learning

增强学习的定义为

Reinforcement learning is learning what to do -- how to mapping situations to actions -- so as to maximize a numerical reward signal.

即,增强学习是用学习如何做出决策,也就是建立起状态(Situation)到行动(Action)的映射,以使得目标奖励信号最大化。注意这里的奖励可能并不是即时,而是可能出现在后续的状态中。因此,增强学习最鲜明的特点是尝试-错误(trial-and-error),以及延时奖励(delayed reward)

需要指出的是,很多以-ing结尾的术语其实表示了多重的概念。在增强学习中,Reinforcement Learning同时表达了,问题、方案、以及研究领域。在增强学习中要格外注意问题与方案这两个概念。

增强学习的概念来源于动态系统控制理论(Dynamic system theory),特别的,来自于的非全知【原文作incompletely-known】的马尔科夫决策过程的最优化控制。在增强学习中,一个agent必须要要有感知环境状态的能力,具有能够影响状态的行动力。同时这个agent还需要被赋予一个与环境有关的执行目标。这三个要素就是感知,行动和目标 (Sensation, action and goal)。任何用于解决这类问题的方法都可以被视为增强学习方法。

1.1 增强学习和监督学习的区别

增强学习不同于监督学习(Supervised learning)。监督学习是从一组由外部监督者提供的标注好的训练集合上学习。这种训练集一般提供了一组环境,以及各个环境下应该采取的决策(label)。监督学习的目标一般是将控制策略进行推广,一般化,是的控制器能够对于没有出现在训练集上的环境也能做出反应。不过这种学习方式不符合增强学习从交互中学习的特点(Learning from interaction)。对于交互式问题,一般很难找到有充足代表性和足够正确的训练集。

1.2 增强学习与非监督学习的区别

非监督学习一般的目的是寻找数据集合中的隐藏结构性。非监督学习的这种特点对于增强学习非常有用,但是只涵盖了增强学习的一部分概念。

综上,作者认为增强学习是于监督学习,非监督学习之后的第三种机器学习范式。

1.3 增强学习面临的挑战

增强学习需要解决的一个独有的问题是,如何平衡探索(Exploration)和使用(Exploitation)。为了在奖励函数上获得好的增益,agent一般会偏好已经尝试过的好的策略。但同时为了发现更多的这种好的策略,agent还需要尝试新的决策。

The agent has to exploit what is already experienced in order to obtain reward, but it also has to explore in order to make better action selections in the future.

针对Exploration-Exploitation的矛盾由来已久。而这类问题其实不是监督学习或者非监督学习所关心的。这也是为什么,作者要将增强学习列为新的机器学习范式。

1.4 增强学习元素

增强学习的系统的主要元素包括:

  1. a policy
  2. a reward signal
  3. a value function
  4. (Optionally) a model of the environment

1.4.1 A Policy

政策定义了agent在给定时刻的行为方式。粗略来说,政策是从环境中感知到的状态到需要执行的操作的映射。有时候,Policy可能是一个简单的函数或者一个查询表,而有时候这个映射可能会涉及非常复杂的运算。

1.4.2 A Reward Signal

Reward Signal定义了增强学习的目标。每次迭代时,环境向agent发送一个单独的数字(reward)。Agent在长期的执行中致力于最大化整体reward。Reward Signal定义了Agent遇到的事件的好与坏。在生物学意义上,reward可以类比于生物在与环境交互中得到的愉悦或者痛苦的体验。同时,Reward也是agent面临的问题的特征的直接表现。Reward是政策调整的最主要因素。

1.4.3 A Value Function

在已经有了Reward Signal的基础上引入Value函数的意义在与评估政策在更长期的尺度上的影响。简单来说,一个状态的value是之后未来agent能够收益到的reward的总量。Reward定义了环境能够基于的立即的、直接的响应,value则考虑了长期的影响。

进一步我们可以发现,一般Reward的定义是非常直接的,如何定于Value则是在建模过程中需要慎重考虑的问题。事实上我们可以发信啊在增强学习的研究中,最重要的一步通常是给出有效的估计Value的方法。

The central role of value estimation is arguably the most important thing that has been learned about reinforcement learning over the last six decades.

1.4.4 A Model of the Environment

对环境的建模就是对于问题本身的建模。模型要求能够反映环境的特点。在给定一个状态和行为时,模型要能够预测下一个时刻的状态以及相应的Reward。Model被用来做长期的计划性质的决策。上面提到Model是可选的因为还存在Model-free的方法。在Model-free的方法中,agent通过trial-and-error的策略来和环境交互。

2 Tabular Soluation Methods

为了准确性,之后术语部分还是直接使用英文记录

在这个部分通过一些比较简单的问题形式来探讨Reinforcement Learning的核心概念。在这些例子中,State和Action空间足够小,可以表示为数组或者表(tables)。这种情况下,理论上的我们是可以找到精确的最优解的。这和后面我们要说的Approximiate methods不同。

2.1 多臂老虎机问题(Multi-armed Bandits)

考虑下面的学习问题。你不断重复地面临一个有\(k\)个不同选项(即Actions)的选择问题。在每轮选择之后你会获得一个量化的Reward,Reward的分布是一个依赖于你的决策的平稳分布【平稳分布即这个分布不是时变的,强调只依赖于你的决策本身】。你的目的是最大化一段时间(比如1000轮选择)的总收益。

这是多臂老虎机问题的的原始形式。多臂老虎机问题是对老虎机的一个类比,只不过在这个问题中,有\(k\)个拉杆。每个动作的选择都像是拉动老虎机的拉杆,而奖励就是击中奖的收益。 通过反复的动作选择,您可以将动作集中在最佳杠杆上,从而最大程度地赢取奖金。 另一个比喻是,医生为一系列重病患者选择实验治疗。 每个动作都是治疗的选择,每个奖励都是患者的生存或福祉。 如今赌博机问题有时会指代更加泛化的问题集合,但是在这里我们只用来称呼这个简单的版本。

在我们的K臂老虎机问题中,\(k\)种行动中的每一种都有一个期望奖励。我们称之为这种行动的value。我们记在时刻\(t\)选择的行为时\(A_t\),对应的奖励是\(R_t\)【注意区分这里是时刻的奖励,前面说的value是期望】,对于任意行为\(a\)的value,我们记为$q_*(a),这是一个期望值:

\[ q_{*}(a) \doteq \mathbb{E}\left[R_{t} | A_{t}=a\right] \]

如果你能够知道每个行为的value值,那么解决k臂老虎机问题就非常简单了,只需要总是选择value最高的行为即可。我们假设你并不确定知道每个行为的value值,但是你可以对其有一个估计。我们记在时刻\(t\)的估计值为\(Q_t(a)\)。我们希望\(Q_t(a)\)能够接近\(q_*(a)\)

如果你始终维护对行为value值的估计,那么在任何时刻你总是能找到估计值最大的那个行为。我们将这些行为成为贪婪行为(Greedy Actions)。当你选择这些行为时,我们称你正在利用(Exploiting)对于这些行为的value的现有知识。如果你没有选择这些贪婪行为,则表示你正在进行探索(Exploring),因为这可以使你改善对非贪婪行为的value值的估计。利用现有知识的选择可以让你在单步操作中最大化期望奖励,但是探索可以在长期的尺度上产生更大的value总量。例如,假设贪婪行动的价值是确定的,而其他几项行动的评估结果几乎相同,但存在很大的不确定性。这种不确定性使得这些其他动作中的至少一个实际上可能比贪婪的动作要好,但是您不知道哪个。如果你在决策前还有很多时间,那么探索非贪婪的行动并发现其中哪个比贪婪的行动更好。在短期内,探索过程中的奖励较低,但从长期来看,奖励较高,因为发现更好的操作后,您可以多次使用它们。由于不可能通过任何一个单一的动作选择来进行探索和利用,因此人们经常提到探索与利用之间的“冲突”。

在任何特殊的场景下,探索还是利用哪个更好,会以一种很复杂的方式依赖于value估计精确值,不确定性,以及剩余的时间步骤。对于特定的k臂匪徒问题的数学形式,有很多复杂的方法可以平衡探索和利用。不过这些方法对于平稳性和先验证知识有很强的假设,这些假设要么难以实现,要么很难获取。

在这里我们无需担心需要以很复杂的方式去平衡探索和利用,我们只需要关注在整体上的平衡问题。在本章中,我们介绍了几种用于解决K臂强盗问题的简单平衡方法,并表明它们比总是利用的方法好得多。 平衡探索与开发的需要是强化学习中出现的一个独特挑战。我们的第K臂强盗问题的简单性使我们能够以特别清晰的形式展示这一点。

2.2 行动-价值方法

我们从研究对行为的value估计,及基于这些估计做出行为决策的方法开始。这类方法我们称为行动-价值(Action-Value)方法。一个行为的value的真值是行为被选择时产生的平均回报。一个直接的方法直接对于我们已经取得的奖励取平均。

\[ Q_t(a) \doteq \frac{\text{sum of rewards when} a \text{taken prior to} t}{\text{number of times} a \text{taken prior to} t} = \frac{\sum_{i=1}^{t-1} R_{i} \cdot \mathbb{1}_{A_{i}=a}}{\sum_{i=1}^{t-1} \mathbb{1}_{A_{i}=a}} \]

其中\(\mathbb{1}_{predicte}\)为指示函数,当下面的条件为真时取1,否则为0。当上式中分母为0时,\(Q_t(a)\)为默认值,例如0。当分母为无穷大时,理论上上式就会收敛到\(q_*(a)\)。我们把这种估计行为value值的方法称为sample-average方法。 当然,这只是估计行动价值的一种方法,不一定是最佳方法。 尽管如此,现在让我们继续使用这种简单的估算方法,然后转向如何将估算值用于选择行动的问题。

最简单的行动选择策略是选择value估计值最高的行动,即上一节中定义的贪婪策略。如果贪婪策略给出选项不只一种,则在其中随机选择。这种贪婪选择策略可以表示为:

\[ A_{t} \doteq \underset{a}{\arg \max } Q_{t}(a) \]

贪婪策略总是利用现有的知识来最大化当即的收益,其并不花费任何时间来尝试哪些明显更差一些的行为来看看这些行为会不会产生更好的结果。一个简单的改进策略是在大多数时候采用贪婪策略,但是偶尔,例如以概率\(\varepsilon\),在所有行为中以均等的概率随机选择。我们将这种策略称为\(\varepsilon\)-greedy方法。这种方法的好处是,随着步骤的增加,所有的行为都可以被尝试无限次, 从而确保所有的\(Q_t(a)\)都会收敛到\(q_*(a)\)。这也意味着选中最优的行为的概率会收敛到超过\(1-\epsilon\)的水平的,接近于1。上面这些都是理论上渐进收敛的保证,在实际使用中是什么效果还有待考察。

2.3 10臂测试问题

我们用一个具体的尝试来看看贪婪策略和\(\varepsilon\)-greedy方法的效果,并进行对比。这里使用到的测试数据是2000个随机生成的10臂老虎机问题,即\(k=10\)。对于每个老虎机问题,例如如下图所示,每个行为的的value值\(q_*(a), a = 1, 2, \dots, 10\),基于一个\(N(0,1)\)的正态分布随机选出。实际的奖励值\(R_t\)则是以\(q_*(A_t)\)为均值,方差为1的正态分布。

在这个测试集合的基础上我们可以评估学习方法的性能。对于每一个赌博机问题,我们执行1000步以观察模型的改善情况。然后我们尝试2000组不同参数定义的赌博机问题,从而得到一个平均的性能评估结果。

下图比较了贪婪策略和两个\(\varepsilon\)-greedy策略(\(\varepsilon = 0.01\)\(\epsilon= 0.1\))。其中上面的图给出了随着训练步数的增加,获得期望奖励的增长情况。贪婪策略在初期能够有更快的增长,但是最终的水平要更低一些。理论上每一步的最佳改进是1.55,但是的贪婪策略之取得了大约1的增益。贪婪策略失败的原因在于其常常被困在次优行为附近。下面的图显示了贪婪策略大约只在三分之一的任务中选中了最优的行为,在其他三分之二的情形下,最优行为的初始采样结果可能不佳,因此贪婪策略就再不会尝试选择这一选项。\(\varepsilon\)-greedy方法最终表现的更好,因为其总是尝试新的行为并提升其发现最优行为的能力。当\(\varepsilon=0.1\)时,由于尝试的比例更多,所以可以更快速地发现最佳的方法。但是选中最优行为的概率被局限为\(91%\)\(\varepsion=0.01\)时,发现最优策略会比较慢,但最终的稳定的性能表现会优于\(\varepsilon=0.1\)的情形。

不过,\(\varepsilon\)-greedy方法和贪婪策略的区别还是取决于任务类型。设想如果奖励分布的方差非常大,那么噪声水平会带来更大的影响,使得贪婪策略更难选中最优的行动。但是反过来如果奖励分布的方差为0,那么贪婪策略总是可以在第一时间选中最优的行为。即便在这种确定性的情形中,如果我们弱化其他的假设,使用探索功能也会带来更大的优势。例如假设赌博任务是非平稳的,即行为的value真值会随着时间变化而变化。

2.4 增量计算实现

这部介绍的是如何将之前提到的行动-价值方法的计算过程优化。为了简化问题表达我们先关注一个单独的行为。令\(R_i\)表示第\(i\)次选中这个行为的奖励,让\(Q_n\)表示这这个行为已经被选中\(n - 1\)次以后的行为value的估计值。那么

\[ Q_{n} \doteq \frac{R_{1}+R_{2}+\cdots+R_{n-1}}{n-1} \]

直接的实现方法是把所有的\(R_i\)存下来,然后计算均值。但是这样在大规模的问题中会消耗非常多的计算资源。下面我们推到递推的计算方法:

\[ \begin{aligned} Q_{n+1} &=\frac{1}{n} \sum_{i=1}^{n} R_{i} \\ &=\frac{1}{n}\left(R_{n}+\sum_{i=1}^{n-1} R_{i}\right) \\ &=\frac{1}{n}\left(R_{n}+(n-1) \frac{1}{n-1} \sum_{i=1}^{n-1} R_{i}\right) \\ &=\frac{1}{n}\left(R_{n}+(n-1) Q_{n}\right) \\ &=\frac{1}{n}\left(R_{n}+n Q_{n}-Q_{n}\right) \\ &=Q_{n}+\frac{1}{n}\left[R_{n}-Q_{n}\right] \end{aligned} \]

这种递推方式在后续还会非常常见,其一般形式为

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

这里的\(StepSize\)一般记为的\(\alpha\),或者\(\alpha_t(a)\)

2.5 追踪非平稳问题

上面说的用平均方法估计value的方法只适用于平稳的老虎机问题,即奖励的分布要是不变的。这个部分我们来讨论非平稳问题的处理。

非平稳问题的处理方法一般是使用一个常量的\(StepSize\)参数

\[ Q_{n+1} \doteq Q_{n}+\alpha\left[R_{n}-Q_{n}\right] \]

其中\(\alpha \in (0, 1]\)为一个常数,\(Q_{n + 1}\)为过去的奖励的加权平均。注意到

\[ \begin{aligned} Q_{n+1} &=Q_{n}+\alpha\left[R_{n}-Q_{n}\right] \\ &=\alpha R_{n}+(1-\alpha) Q_{n} \\ &=\alpha R_{n}+(1-\alpha)\left[\alpha R_{n-1}+(1-\alpha) Q_{n-1}\right] \\ &=\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{aligned} \]

\((1 - \alpha)^n + \sum_{i = 1}^{n}\alpha(1 - \alpha)^{n - i} = 1\),因此\(Q_{n+1}\)可以被称为\(R_i\)的加权平均。且加权系数的值决定了时间上越近的奖励权重越高,过去的奖励在新的行动中的贡献会指数下降。故这种方法也被称为exponential recency-weighted average

\(\alpha\)也可以随时间变化,记为\(\alpha_n(a)\)。当\(\alpha_n(a) = 1 / n\)时,表达式退化成简单平均,这意味着在样本数量足够大时可以收敛到真值。随机过程理论给出了这样的结论:当\(\{\alpha_n(a)\}\)序列符合下面的要求时,基于这一些结算的\(Q_{n}\)收敛到value的真值:

\[ \sum_{n=1}^{\infty} \alpha_{n}(a)=\infty \quad \text { and } \quad \sum_{n=1}^{\infty} \alpha_{n}^{2}(a)<\infty \]

第一个条件表明\(StepSize\)足够大,以克服任何初始条件和随机波动的影响;第二个条件表明步长足够小以使得最后的和收敛。

注意到对于简单平均算法,即\(\alpha_n(a) = 1 / n\)时,这两个条件都能得到满足,但是当\(\alpha_n(a)\)为常数时,第二个条件显然无法满足,这意味着采用这种计算方法,最终的估计值无法收敛,而是会持续波动。由于问题本身是非平稳的,这种不收敛的特性反而是符合我们的要求的。

2.6 乐观初始值

上面讨论的方法都依赖与如何确认最初的行为Value估计值,\(Q_1(a)\)。用统计学的语言来说,这些方法由于其初始估计值的选择是有偏的(biased)。对于sample-average方法来说,如果所有的行为都被选择了至少一次,那么这种偏差是可以消除的。但是当我们使用了常量的\(\alpha\)值时,初始值引入的偏差就会一直存在(虽然会不断减少)。在实践中,这种偏差一般不是问题,有时候也会显得非常有用。不过,缺点是这里的初始值选择会成为用户不得不设置了的初始超参数。不过好处是这也让我们能够为模型提前注入一些先验信息(奖励的期望水平)。

初始值的设置也可以被用来促进探索过程。假设不把这些初始值设置为0,而是设置成\(+5\)。注意到的\(q_*(a)\)是从\(N(0,1)\)的正态分布中生成的,那么\(+5\)的奖励就是一个非常高(或者说乐观,Optimistic)的值,这会促使模型去执行探索:在初始阶段,无论选择什么样的行为都会让模型失望,故促使模型多次尝试不同的行为。而随着不断迭代,初始注入的这个很高的奖励值会被「平均掉」,故使得真实的行为奖励能够被正确地选择出来。下图给出了性能对比:

在初始阶段,采用了乐观的初始值的方法性能比价差,因为这种方法进行了更多的探索。不过这些探索工作使得这种方法的性能可以后来居上。不过注意这种乐观初始值的方法并不是一种广泛有用的鼓励探索的方案,例如这种方法并不适合非平稳问题。

2.7 置信区间上界行为选择

需要进行探索,因为操作值估计的准确性始终存在不确定性。贪婪的行为是目前看来最好的行为,但其他一些行为实际上可能会更好。\(\varepsilon\)-greedy行为选择策迫使用户选择一些非贪婪的策略,不过这种策略会平等地尝试所有可能的行为选项,并没有对于次优选项和不确定性【这里指value估计值的不确定性】的偏好。更好的方法是一些更有潜力成为最优的行为中进行选择。这里的说的「潜力」取决于这些行为的value估计接近于最大值的程度,或者估计值中的不确定性的多少。一个有效的方法是根据下面的标准选择

\[ A_{t} \doteq \underset{a}{\arg \max }\left[Q_{t}(a)+c \sqrt{\frac{\ln t}{N_{t}(a)}}\right] \]

其中\(\ln t\)是自然对数,\(N_t(a)\)代表 \(a\) 在时刻\(t\)之前已经被选择的次数,变量\(c\)则控制了探索的偏好程度。如果\(N_t(a) = 0\),则\(a\)被认为是最大化的行为选项。

置信区间上界(Upper confidence bound, UCB)行为选择的概念,上面的平方根项是对\(a\)的value值的估计的不确定性(方差)度量。上面的式子中待最大化的项是一系列的\(a\)的value的可能真值的上界,其中\(c\)决定了置信度水平。每次\(a\)被选择时,不确定性下降。另一方面,如果别的行为被选择,会导致\(a\)的不确定性上升。在这个定义下,不同的选项的被选择的概率得到了均衡。在充分长的训练时间内,所有的行为都可以被选择。

2.8 梯度赌博机算法

到目前为止,在本章中,我们已经考虑了估计行为的value值并使用这些估计值选择行为的方法。 这通常是一种好方法,但并非唯一可行的方法。在本部分我们为每种行为\(a\)学习一个量化的偏好值、\(H_t(a)\)。这个偏好值越大,对应的行为被选择的几率就越大。偏好值没法从奖励的角度解释。偏好值的绝对大小没有意义,重要的是相对值。最终这些偏好值使用Softmax函数处理给出选择概率:

\[ \operatorname{Pr}\left\{A_{t}=a\right\} \doteq \frac{e^{H_{t}(a)}}{\sum_{b=1}^{k} e^{H_{t}(b)}} \doteq \pi_{t}(a) \]

这里我们还引入了一个新的标记 \(\pi_t(a)\),为在时刻\(t\)选择行动\(a\)的概率。在初始状态下,所有的行为的偏好都是相同,故每个行为被选择的概率是均等的。

在Softmax形式定义的问题上我们可以使用随机梯度下降法进行学习。在每一步选择\(A_t\)行为后,收到奖励\(R_t\),则行为偏好按照如下的方式进行更新:

\[ \begin{array}{cc} H_{t+1}\left(A_{t}\right) \doteq H_{t}\left(A_{t}\right)+\alpha\left(R_{t}-\bar{R}_{t}\right)\left(1-\pi_{t}\left(A_{t}\right)\right), & \text { and } \\ H_{t+1}(a) \doteq H_{t}(a)-\alpha\left(R_{t}-\bar{R}_{t}\right) \pi_{t}(a), & \text { for all } a \neq A_{t} \end{array} \]

其中\(\alpha > 0\)为前面提到的\(StepSize\)参数,\(\bar{R}_t \in \mathbb{R}\)为所有到\(t\)时刻位置的奖励的平均值(注意不包括\(R_t\)),这个平均值也可以用前面的章节提到的增量方法进行计算。上面的计算的基本原理是如果某个行为产生的奖励高于平均值,就增加这个行为的概率,反之降低这个概率。

2.9 关联搜索(Contextual Bandits)

目前我们仅仅考虑了非关联问题,即不需要将不同的行动和不同的状态关联起来考虑。在非关联任务中,学习者要么尝试在平稳问题下寻找单个最佳的行为,或者在非平稳问题下寻找不断变化的最佳选择。不过在更加一般的场景中,学习任务需要处理的会不只一个状态情形,最终的目的是学习一种策略:从情况到在这些情况下最好的行动的映射。 为了为整个问题奠定基础,我们简要讨论了非关联任务扩展到关联设置的最简单方法。

举个例子,假设有几个不同的k臂老虎机任务,在每一步你会随机的遇到其中的一种,这是一个典型的非平稳问题,你也可以尝试用之前我们提出的解决非平稳问题的方法来解决。不过,对于非平稳问题,除非问题变化的比较缓慢,不然这些方法的效果都不会很好。现在我们假设,当随机的老虎机问题被选择出来呈现给你的同时,提供给你关于这个问题的特征的一些额外的线索(当然不是直接给你这个问题的详细参数)。比如可能不同的老虎机会呈现不同的颜色。那么现在你可以学习一种策略,将你看到的颜色和k臂老虎机的问题关联起来。例如最后得到的策略可能是看见绿色的机器,就拉动第二个摇杆,看到红色的,选择第一个摇杆。在适当的策略下,拥有这些额外的信息可以比缺少这些信息时得到更好的结果。

这是一个典型的关联搜索任务的例子【这里说的关联,是将关于问题场景的其他要素同问题的特征关联起来,从而使得学习程序可以根据这些其他要素做出更好的判断】,之所以成为关联搜索是因为其涉及到基于trial-and-error搜索最佳行为的学习策略,以及将这些最佳策略成为最佳时的系统状态关联起来。目前关联搜索问题也被称为情境老虎机(Contextual Bandit)。关联搜索问题介于k臂老虎机问题和完全的增强学习问题之间。这类问题同完全的增强学习问题之间的相同点在于他们都涉及学习一个策略。而这个问题同k臂老虎机问题的相同点在于每个行为只会产生立即的回报效果。如果行为被允许对接下来的系统状态及对应的奖励产生影响,这就是我们后面要面临的完整的强化学习问题。

3 有限马尔科夫决策过程

这个章节介绍马尔科夫决策过程(Markove Decision Process, MDP)的正式形式。这个问题不仅涉及赌博机问题中的评估性反馈机制,同时也包含关联搜索的内容。MDP是序贯式决策过程的经典形式,在这类问题里面,选择不同的行动的不仅产生直接的奖励,而且会响应后续的系统状态,进而影响未来的奖励。因此MDP需要解决的一个重要问题就是即时奖励和延后奖励的平衡。在赌博机问题中,我们对于每个行为\(a\)估计其价值\(q_*(a)\),而在MDP汇总我们则需要估计每个行为\(a\)在每个状态下\(s\)下的价值\(q_*(s,a)\),或者我们计算在每个状态下选择最优的行为时得到的价值\(v_*(s)\)。这种状态相关的特质使得我们能够更好地根据长期的规划选择每个步骤的行为。

MDP问题是理想化的强化学习问题的的数学模型,在这类问题上我们可以得到精确的数学形式的结论。这里我们介绍这一问题的数学结构的关键要素,包括收益,价值函数和Bellman方程。同时我们寻找能够表达为有限MDP问题的应用。如同其他所有的人工智能问题一样,问题适用的广泛性同数学上的可处理性是一对矛盾。

3.1 代理-环境接口

MDP旨在为「通过交互过程学习达到指定目标」这类问题提供一种直接的解决框架。这里进行学习和决策的实体称为代理(Agent)。代理需要进行交互的为环境。它们不断地相互作用,代理选择动作,环境响应这些动作并向代理呈现新情况。环境还向代理提供奖励,奖励是代理追求的目标。

这个图很经典,很多介绍强化学习的视频和文章都会画类似的图

具体而言,代理同环境的交互以时间离散的方式进行,\(t=1,2,3,\dots\)。在每一个时刻\(t\),代理收到来自环境的状态表达,\(S_{t} \in \mathcal{S}\),并在此基础上选择一个行动,\(A_{t} \in \mathcal{A}(s)\)。当前时刻结束以后,作为对行为选择的反馈,dialing会收到一个量化的奖励值,\(R_{t+1} \in \mathcal{R} \subset \mathbb{R}\),环境进入新的状态\(S_{t+1}\)。故MDP和代理会经历如下的轨迹:

\[ S_{0}, A_{0}, R_{1}, S_{1}, A_{1}, R_{2}, S_{2}, A_{2}, R_{3}, \dots \]

在有限MDP中,状态、行动和奖励的集合(\(\mathcal{R}, \mathcal{S}, \text{and}\ \mathcal{R}\))都是是有限的。在这个条件下,随机变量\(R_t\)\(S_t\)有着良好定义的离散概率分布形式,且这一概率只取决于前一个时刻的状态和行为(马尔科夫模型的基本特征)。即如下形式

\[ p\left(s^{\prime}, r | s, a\right) \doteq \operatorname{Pr}\left\{S_{t}=s^{\prime}, R_{t}=r | S_{t-1}=s, A_{t-1}=a\right\} \]

函数\(p\)定义了MDP的动态特征(Dynamics)。在马尔科夫决策过程中,由\(p\)给出的转移概率完全描述了环境的动态特征。其实这也就是要求我们在建模时,对于环境的状态描绘要涵盖所有对未来会产生影响的历史信息。这样的状态会被称为Markov property。这样的马尔科夫模型是接下来的部分的基础假设。而且后面我们还将会看到我们可以从对环境的非马尔科夫观测中构建具有马尔科夫性质的状态定义。

\(p\)中的状态单拎出来得到状态转移概率

\[ p\left(s^{\prime} | s, a\right) \doteq \operatorname{Pr}\left\{S_{t}=s^{\prime} | S_{t-1}=s, A_{t-1}=a\right\}=\sum_{r \in \mathcal{R}} p\left(s^{\prime}, r | s, a\right) \]

我们还可以计算奖励期望

\[ r(s, a) \doteq \mathbb{E}\left[R_{t} | S_{t-1}=s, A_{t-1}=a\right]=\sum_{r \in \mathcal{R}} r \sum_{s^{\prime} \in \mathcal{S}} p\left(s^{\prime}, r | s, a\right) \]

上面计算的是前一个状态\(s\)下选择\(a\)行为会产生的平均奖励。我们也可以在已知当前时刻的状态的情况下给出对于自己活得的奖励的估计(也就是期望值):

\[ r\left(s, a, s^{\prime}\right) \doteq \mathbb{E}\left[R_{t} | S_{t-1}=s, A_{t-1}=a, S_{t}=s^{\prime}\right]=\sum_{r \in \mathcal{R}} r \frac{p\left(s^{\prime}, r | s, a\right)}{p\left(s^{\prime} | s, a\right)} \]

关于区分哪些部分是环境,有一条简单的判断标准:任何代理不能随意控制的部分的都可以被视为环境。我们并不假设代理总是对环境的信息一无所知。例如一般代理通常会知道奖励和环境状态与自身行为的关系。不过,奖励的具体值的产生或者计算过程一般都是在代理之外,无法由代理来决定的。甚至有时候代理可以对环境有着充分的认识,但是此时代理仍然可以能会面临需要强化学习解决的问题。例如我们充分了解魔方的玩法,但是没法将魔方复原。所以,代理和环境的边界代表的是代理完全控制的范围的边界,而不是其知识范围的边界

MDP框架是的对目标指导的基于交互的学习问题的良好抽象。它提出,无论感觉,记忆和控制装置的细节如何,以及人们试图实现的目标是什么,任何学习目标导向行为的问题都可以简化为在代理与其环境之间来回传递的三个信号: 一种信号代表代理做出的选择(动作),一种信号代表做出选择的依据(状态),另一种信号定义代理的目标(回报)。 该框架可能不足以有效地表示所有决策学习问题,但已被证明是广泛有用和适用的。

当然,对于原始问题的抽象方式会对最终的学习性能产生巨大的影响。不过在这个问题上,更多的是「艺术」的问题【玄学】,而非科学的问题。

3.2 目标与奖励

这部分内容其实和之前在多臂老虎机问题中讨论的Goal和Reward的关系是一样的。其中Reward是直接的反馈,而优化的目标是累积的Reward,这个累积量称为value。Reward和Value系统是对代理目标(Goal)的量化表达。Reward系统的设计同样会对最终的性能产生很大的影响。

3.3 Returns and Episodes

前面说的目标与奖励部分是定性的,这里提出定量描述。如果在时刻\(t\)以后获得的奖励分别为\(R_{t+1}, R_{t+2}, R_{t+3},\dots\),那么我们如何最大化这一序列呢?一般我们会寻求最大化返回的期望(Expected return)。这里返回\(G_t\)是奖励序列的一个函数。最简单的情形是

\[ G_{t} \doteq R_{t+1}+R_{t+2}+R_{t+3}+\cdots+R_{T} \]

其中\(T\)是最后一步。这个方法在有限步骤的应用场景中有作用,或者说,代理与环境的交互过程会明显地划分成多个段,这样的每一段称为一个Episode。每个Episode都会以一个特殊的状态结束(terminal state)。在结束状态之后通常是重置到开始的状态,或者是根据一定的分布进入多个开始状态中的一种。例如在玩游戏时,每一局可以被视为是一个Episode,在每个Episode结束以后,游戏会重新开始,且新的一局同上一局没有关系。

在这种具有Episode结构的任务中,我们将除了终止状态之外的的所有状态记为\(\mathcaf{S}\),而包含了终止状态的所有状态记为\(\mathcaf{S}^{+}\)。终止时刻\(T\)是一个随机变量。

当然在很多情况下,代理-环境的交互过程无法切分成这样的Episode结构,而是可以无限制地持续进行下去。很多与现实世界的任务打交道的问题都是这样的。一个控制一个机器人运行。我们将这类任务称为连续任务(Continuous tasks)。对于连续任务,返回(Return)的表达是一个问题,因为总体的回报加起来很可能是无限大的。因此我们需要合适地设计返回函数。解决这个问题的一个方法是discounting

\[ G_{t} \doteq R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\cdots=\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1} \]

这里的\(\gamma\in [0, 1]\)称为discount rate。这个折扣率决定了未来长期的汇报对于当前的整体回报的影响。且当\(\gamma < 1\)时,只要奖励值是有界的,那么上式计算出来的回报是能收敛的。当\(\gamma = 1\)时,则回报退化成单步奖励。

回报值可以序贯计算:

\[ \begin{aligned} G_{t} & \doteq R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\gamma^{3} R_{t+4}+\cdots \\ &=R_{t+1}+\gamma\left(R_{t+2}+\gamma R_{t+3}+\gamma^{2} R_{t+4}+\cdots\right) \\ &=R_{t+1}+\gamma G_{t+1} \end{aligned} \]

3.4 Episodic和Continuous任务的统一符号形式

对于Episodic任务,我们将连续的Episodes连接起来,对于这个序列上的任一一点的状态我们记为\(S_{t, i}\),其中\(i\)为Episode的编号,当然,行为、行为选择概率、奖励以及Episode的长度等变量的脚标也需要调整:\(A_{t,i}, R_{t,i}, \pi_{t,i}, T_{t,i}\)。是事实上我们在讨论Episodic任务时,我们几乎不需要强调不同的Episode,而是选择一个单独的Episode讨论,所以脚标\(i\)常常被省略。

为了统一两类任务的表达形式,我们考虑将Episode的终结视为进入了一个特殊的absorbing state,即吸收态。在状态转移图中,一旦进入吸收态就会一直停留在吸收态。且进入吸收态以后,之后的奖励会始终为0。

因此我们可以用如下的形式来统一表达两类任务:

\[ G_{t} \doteq \sum_{k=t+1}^{T} \gamma^{k-t-1} R_{k} \]

其中\(T\)可以取\(\infty\)

3.5 政策和价值函数

价值函数(value function)的含义和前面多臂赌博机问题中的价值函数的含义类似。价值函数的是环境状态(或者是状态-行为对)的函数,价值给出了代理处于当前状态(或者说实在当前状态下做出给定选择)到底有多好。价值考虑了未来的奖励情况。当然,既然价值取决于未来的奖励,而未来的奖励依赖于未来做出的行为决策。这里我们从现在出发到未来的行为决策序列称为政策(Policy)。

政策的正式定义是从状态到行为选择概率之间的映射。如果代理在时刻\(t\)遵循政策\(\pi\),那么\(\pi(a | s)\)为在状态\(S_t = s\)下选择行为\(A_t = a\)的概率。强化学习需要就是根据代理的经历,调整合适的政策。

状态\(s\)下采用政策\(\pi\)时的价值函数为\(v_{\pi}(s)\),是从状态\(s\)开始接下来使用\(\pi\)策略得到的Return值。对于MDP,\(v_{\pi}\)可以由下式计算:

\[ v_{\pi}(s) \doteq \mathbb{E}_{\pi}\left[G_{t} | S_{t}=s\right]=\mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1} | S_{t}=s\right], \text { for all } s \in \mathcal{S} \]

注意对于终止状态来说,其value值总是0。我们将\(v_{\pi}\)函数称为政策\(\pi\)的状态-价值函数(state-value function for policy \(\pi\))。

类似,我们定义在状态\(s\)下根据政策\(\pi\)选择行为\(a\)时的价值函数为\(q_{\pi}(s, a)\)

\[ q_{\pi}(s, a) \doteq \mathbb{E}_{\pi}\left[G_{t} | S_{t}=s, A_{t}=a\right]=\mathbb{E}_{\pi}\left[\sum_{k=0}^{\infty} \gamma^{k} R_{t+k+1} | S_{t}=s, A_{t}=a\right] \]

函数\(v_{\pi}\)\(q_{\pi}\)可以根据代理的经历进行估计。例如如果代理遵循政策\(\pi\)并且对每个状态维护实际收到的Return值的平均值,那么在遇到这个状态的次数充分大,这个平均值就将会收敛到这状态的价值\(v_{\pi}(s)\)。如果这个平均值是根据具体的行为选择进行统计的,那么类似的方法就能得到\(q_{\pi}(s, a)\)。我们将这类估计犯法称为蒙特卡洛方法(Monte Carlo methods)。不过如果状态空间非常庞大,那么这种统计方法就会非常困难。取而代之的方法是,代理将\(v_{\pi}\)\(q_{\pi}\)视为有参函数(参数的数量比起状态空间要小很多),通过调整这些参数让函数的结果尽可能拟合观测到的Return值。这种方法也可以产生精确的估计结果【这是因为状态空间中的不同状态之间通常不是独立的,而是耦合的,因此问题的实际自由度要比状态空间的维数要小很多。所以含参函数的参数数量只要高于自由度的数量,并通过函数关系将参数空间映射到状态空间,就能实现非常好的估计效果】

价值函数的一个基础属性是满足递归关系特性,即可以写成递推方式进行计算。对于任意的政策\(\pi\)以及任意的状态\(s\),下面的一致性条件在\(s\)的价值与\(s\)的可能后续状态的价值之间成立:

\[\begin{equation} \begin{aligned} v_{\pi}(s) & \doteq \mathbb{E}_{\pi}\left[G_{t} | S_{t}=s\right] \\ &=\mathbb{E}_{\pi}\left[R_{t+1}+\gamma G_{t+1} | S_{t}=s\right] \\ &=\sum_{a} \pi(a | s) \sum_{s^{\prime}} \sum_{r} p\left(s^{\prime}, r | s, a\right)\left[r+\gamma \mathbb{E}_{\pi}\left[G_{t+1} | S_{t+1}=s^{\prime}\right]\right] \\ &=\sum_{a} \pi(a | s) \sum_{s^{\prime}, r} p\left(s^{\prime}, r | s, a\right)\left[r+\gamma v_{\pi}\left(s^{\prime}\right)\right], \quad \text { for all } s \in \mathcal{S} \end{aligned} \label{eq:value_function_1} \end{equation}\]

\(s‘\)为下一个状态,\(p\)在之前我们提到,是环境的动态特征,反映了再特定状态下采用特定的行为会导致的后续状态及收益。上式中涉及两个求和,分别是对特定的行为选择产生的后果计算期望价值,和在不同的行为之间计算期望值。最终的期望实际上是在\(a, s'\)\(r\)这三个变量上去期望。对应的三个随机变量的分布可以认为是\(\pi (a | s) p(s', r | s, a)\)

上面的公式,是\(v_\pi\)Bellman方程,该公式表现了当前状态value值与下一个状态的value值之间的关系。如下图:

注意我们再说Bellman方程时,\(v_\pi\)作为这个方程的未知数出现。这里\(v_\pi\)是强化学习需要学习的内容。

我们来看一个例子。下面的图中有一个方格矩阵,其中每个格子代表一个状态。在每个格子上可以选择四种行为:上下左右,来决定代理在矩阵中的位置变化。如果行为会导致格子离开矩阵【例如在最上方边界还要选择网上走】,那么代理的位置不变,但会产生-1的奖励。其他的行文一般的Reward都是0,但是在特定的的位置上会不同。在\(A\)位置上,任何行为都会把代理带到\(A'\)位置,并产生+10的奖励。在\(B\)位置上,任意行为都会将代理带到\(B'\)位置上并产生+5的奖励。

假设代理再任意位置上选择任意行为的概率都是相等,那么上面图中右侧部分给出了\(v_\pi\)函数(\(\gamma = 0.9\))。这个结果是通过求解线性方程组\(\eqref{eq:value_function_1}\)得到的【上面一共25个格子,即一共25个状态,而根据\(\eqref{eq:value_function_1}\)可以给出每个状态和其他所有状态的value之间的关系,那么将每个状态都带入到\(\eqref{eq:value_function_1}\)的左边,得到25个线性方程就可以求得所有状态的value值】。观察结果我们可以看到,位于下部边缘状态会产生负的value。另外不出所料\(A\)是最好状态,不过其value值是小于10的。相反,\(B\)状态的value值又大于5。这是因为从A出发获得了最高的单步奖励,由于后续可能遇到负的单步奖励,所以整体上的value会降低一些。不过从\(B\)出发以后可能经过\(A\)从而获得一个较大增益,所以整体的value会升高一些。

3.6 最优政策与最优的Value函数

在上一个部分我们引入了政策函数和value函数的概念,其中value函数是直接依赖于政策函数的选择的。而方程\(\eqref{eq:value_function_1}\)中的\(p\)\(r\)是环境决定的。在比较两个政策时,如果其中一个政策\(\pi\)给出的value函数在任何状态下都要更好一些(或者相等),那么这个政策就被认为比另一个政策\(\pi'\)更好。那么始终存在比其他任何政策都好的政策, 这样的政策为最优政策。注意最优政策可能不止一个,我们将最优政策集合记为\(\pi_*\)。最优政策具有同样的状态value函数,这个函数被称为最优价值函数,记为\(v_{*}\)

\[ v_*(s) \doteq \max_{\pi} v_{\pi}(s) \]

最优政策同时也具有相同的行为-价值函数\(q_*\)

\[ q_*(s, a) \doteq \max_{\pi} q_{\pi} (s, a) \]

根据定义我们可以给出\(q_*\)\(v_*\)的关系:

\[ q_*(s, a) = \mathbb{E}[R_{t+1} + \gamma v_*(S_{t+1}) | S_t = s, A_t = a] \]

\(v_*\)这个函数同样需要满足\(\eqref{eq:value_function_1}\)指定的一致性条件。不过由于经过最优化计算遍历了政策空间。所以最优价值函数的一致性条件可以写成不包含政策函数的形式。这个方程被称为最优Bellman方程:

\[\begin{equation} \begin{aligned} v_*(s) &= \max_{a \in \mathcal{A}(s)} q_{\pi_*}(s, a) \\ &= \max_{a} \mathbb{E}_{\pi_*}[G_t | S_t = s, A_t = a] \\ &= \max_{a} \mathbb{E}_{\pi_*}[R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a] \\ &= \max_{a} \mathbb{E}[R_{t+1} + \gamma v_*(S_{t+1}) | S_t = s, A_t = a] \\ &= \max_{a} \sum_{s', r}p(s', r | s, a)[r + \gamma v_*(s')] \end{aligned} \label{eq:value_function_optimal} \end{equation}\]

Emmm,上面这个式子的头一步推导是行为选择总是选择q值最大的那个决策,这不是实际上已经决定了\(\pi\)的形式了么???

然后我们可以得到\(q_*\)的Bellman最优方程

\[ \begin{aligned} q_{*}(s, a) &=\mathbb{E}\left[R_{t+1}+\gamma \max _{a^{\prime}} q_{*}\left(S_{t+1}, a^{\prime}\right) | S_{t}=s, A_{t}=a\right] \\ &=\sum_{s^{\prime}, r} p\left(s^{\prime}, r | s, a\right)\left[r+\gamma \max _{a^{\prime}} q_{*}\left(s^{\prime}, a^{\prime}\right)\right] \end{aligned} \]

二者对应的Backup图为

对于有限MDP,\(\eqref{eq:value_function_optimal}\)中的Bellman方程有唯一解。这里本质上Bellman方程是一个方程组,方程组中方程的数量取决于状态的数量。如果系统动态特征函数\(p\)已知,那么这个方程就可以进行求解。

在解出\(v_*\)之后,求最优政策就相对简单了。对于每个状态\(s\),选择能够将\(q\)最大化的\(a\)即可。

用这里提出的方法求解前一个章节提出的例子可以得到下面的结果:

3.7 最优化与近似

我们定义了最优的value函数和最优政策。取得最优的策略当然是最好的,但是实际环境中条件不一定这么完善,最优的策略不一定能够得到。又或者要获得最优的政策需要付出非常大的计算代价。内存方面的限制也是一个重要的因素。为了建立起包含完整的价值函数,政策和环境模型的强化学习模型,通常需要消耗大量的内存。在复杂的大规模问题下,内存消耗会非常巨大。在这些情况下,我们需要用一些近似的表达。

存在一些概率很低的状态,在这些状态上去寻求次优方案对于整体的效果的影响非常低。因此强化学习的在线学习的天性使其可以将更多的力量放到为更常见的状态做优化上。这是区分强化学习和其他解决MDP的方法的一个重要区别。

4 动态规划

动态规划(Dynamic programming, DP)是指一类在事先给定了环境的完美模型之后求解MDP最优解的一系列算法的集合。经典的DP算法一般在强化学习里面应用较少,因为假设太过完美,也因为其计算量很大。不过DP方法在理论上有很大的价值,有助于我们理解其他的方法。事实上,其他的求解MDP的方法,可以视为是以尽量小的代价取得DP一样的效果的尝试。

DP的核心思想(事实上也是强化学习方法的思想)是使用价值函数进行有组织,有结构性的最优政策搜索。同上一个章节中我们直接求解Bellman公式的方法不同,DP算法将Bellman公式转化成更新规则,以改进对最优价值函数的估计。

4.1 政策评估(预测)

首先我们考虑对任意的政策\(\pi计算状态价值函数\)v_{}\(。这个计算过程在DP中被称政策评估(Policy evaluation),同时我们也称之为预测问题(Prediction problem)。在上一个章节中我们提到对于\)s $,

\[ \begin{aligned} v_{\pi}(s) & \doteq \mathbb{E}_{\pi}\left[G_{t} | S_{t}=s\right] \\ &=\mathbb{E}_{\pi}\left[R_{t+1}+\gamma G_{t+1} | S_{t}=s\right] \\ &=\sum_{a} \pi(a | s) \sum_{s^{\prime}} \sum_{r} p\left(s^{\prime}, r | s, a\right)\left[r+\gamma \mathbb{E}_{\pi}\left[G_{t+1} | S_{t+1}=s^{\prime}\right]\right] \\ &=\sum_{a} \pi(a | s) \sum_{s^{\prime}, r} p\left(s^{\prime}, r | s, a\right)\left[r+\gamma v_{\pi}\left(s^{\prime}\right)\right] \end{aligned} \label{eq:4-value-function} \]

如果环境的动态特征(即\(p\))一直,那么\(\eqref{eq:4-value-function}\)就是有\(|\mathcal{S}|\)个未知变量的线性方程组。这个方程组的求解是非常直接的。

考虑一个近似价值函数组成的序列\(v_0, v_1, v_2, \dots\),其中第一个\(v_0\)为任意选择的(除了对终结状态的value值,这个值总是0),那么我们可以使用Bellman方程去更新:

\[ \begin{aligned} v_{k+1}(s) & \doteq \mathbb{E}_{\pi}\left[R_{t+1}+\gamma v_{k}\left(S_{t+1}\right) | S_{t}=s\right] \\ &=\sum_{a} \pi(a | s) \sum_{s^{\prime}, r} p\left(s^{\prime}, r | s, a\right)\left[r+\gamma v_{k}\left(s^{\prime}\right)\right] \end{aligned} \label{eq:4-value-function-iterative} \]

显然,\(v_k = v_\pi\)是上面的迭代式的不动点。因此不断重复这个迭代过程会使得\(\{v_k\}\)收敛到\(v_\pi\)。这个算法被称为迭代式政策评估。

从程序角度实现这种算法时,直接的思路是用两个数组分别代表\(v_k(s)\)\(v_{k+1}(s)\)。还有一种方法是只是用一个数组。在一个状态上计算的价值函数值更新时,直接"in-place"(原地)更新到数组的对应位置。那么事实上在单步计算内部的循环中,部分价值函数值的更新已经用到的更新后的值。这种计算方法也能收敛,且常常收敛的更快。在in-place的方法中,在单步计算中遍历不同状态的顺序会都收敛速度有比较大的影响。由于收敛速度的优势,in-place迭代是DP中的默认迭代方法。

完整的in-place迭代算法如下:

4.2 政策改进

我们计算价值函数的目的在于得到更好的政策。假设我们已经就任一种确定性的政策\(\pi\)给出了价值函数\(v_\pi\)。对于某种状态\(s\),我们希望知道是否我们应该调整政策以选择另一种行为\(a \neq \pi(s)\)。我们已知了如果在当前状态下遵循当前政策有多好 -- 即\(v_\pi(s)\)的含义,但是如果调整政策是否会得到更好的结果呢?一种做法是走状态\(s\)下选择\(a\)而非\(\pi(s)\),尔后在继续遵守政策\(\pi\)。这种方式得到行为-状态价值是

\[ \begin{aligned} q_\pi (s, a) &\doteq \mathbb{E}[R_{t+1} + \gamma v_{\pi} (S_{t+1}) | S_t = s, A_t = a] \\ &= \sum_{s', r} p(s', r | s, a)\left[ r + \gamma v_\pi (s') \right] \end{aligned} \]

最关键的问题是采用上面的方法选择了行为\(a\)以后得到的价值函数的取值是否高于\(v_\pi(s)\)。如果取值更高,那么学习者就会期待是是否是每次\(s\)状态下选择\(a\)都会取得更好的结果。那么种种判断是否合理呢?事实上根据政策改良理论(Policy improvement theorem),这种判断成立是更广泛的结果的一个特例。记\(\pi\)\(\pi'\)为任意两种不同的确定性政策。对于任意\(s \in \mathcal{S}\),有

\[\begin{equation} q_\pi(S, \pi'(s)) \geq v_\pi(s) \label{eq:temp-4.7} \end{equation}\]

即政策\(\pi'\)至少和\(\pi\)同样好,或者更好。那么有:

\[\begin{equation} v_{\pi'}(s) \geq v_{\pi}(s) \label{eq:temp-4.8} \end{equation}\]

如果\(\eqref{eq:temp-4.7}\)是在任意状态下都是严格的不等号,那么\(\eqref{eq:temp-4.8}\)也能在对应的状态上取得不等。基于这个理论,我们可以对本部分开头的例子做出下面的结论:对于确定性政策\(\pi\)\(\pi'\),如果\(\pi'\)\(\pi\)仅仅在状态\(s\)上的选择不同,即\(\pi'(s) = a \neq \pi(s)\)。那么对于任意其他状态,式子\(\eqref{temp-4.7}\)都成立(取等了)。那么如果$q_{}(s, a) > v_(s) \(,那么改进后的政策就要比\)$更好一些。

这个理论的证明比较容易理解。从\(\eqref{eq:temp-4.7}\)出发,

\[ \begin{aligned} v_{\pi}(s) & \leq q_{\pi}\left(s, \pi^{\prime}(s)\right) \\ &=\mathbb{E}\left[R_{t+1}+\gamma v_{\pi}\left(S_{t+1}\right) | S_{t}=s, A_{t}=\pi^{\prime}(s)\right] \\ &=\mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma v_{\pi}\left(S_{t+1}\right) | S_{t}=s\right] \\ & \leq \mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma q_{\pi}\left(S_{t+1}, \pi^{\prime}\left(S_{t+1}\right)\right) | S_{t}=s\right] \\ &=\mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma \mathbb{E}\left[R_{t+2}+\gamma v_{\pi}\left(S_{t+2}\right) | S_{t+1}, A_{t+1}=\pi^{\prime}\left(S_{t+1}\right)\right] | S_{t}=s\right] \\ &=\mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} v_{\pi}\left(S_{t+2}\right) | S_{t}=s\right] \\ & \leq \mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\gamma^{3} v_{\pi}\left(S_{t+3}\right) | S_{t}=s\right] \\ & \vdots \\ & \leq \mathbb{E}_{\pi^{\prime}}\left[R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\gamma^{3} R_{t+4}+\cdots | S_{t}=s\right] \\ &=v_{\pi^{\prime}}(s) \end{aligned} \]

上面的理论分析解决了在给定一个政策及其价值函数时,我们可以很容易地在单个状态上改进政策。很自然,在所有的状态机和可能的行为集上考虑这个问题,在每个状态上都使得\(q_{\pi}(s, a)\)最大化,这成为了一种贪婪策略:

\[\begin{equation} \begin{aligned} \pi'(s) & \doteq \mathop{\arg\!\min}_{a} q_{\pi}(s, a)\\ &= \mathop{\arg\!\min}_{a} \mathbb{E}[R_{t+1} + \gamma v_\pi(S_{t+1}) | S_t = s, A_t = a]\\ &= \mathop{\arg\!\min}_{a}\sum_{s',r}p(s', r | s, a)\left[r + \gamma v_{\pi}(s')\right] \end{aligned} \label{eq:temp-4.9} \end{equation}\]

这种逐步改善政策的方法称为policy improvement。不过这种逐步迭代的方法还缺少一个停止条件。假设迭代过程中,\(\pi'\)政策和迭代前的政策\(\pi\)是同等好的。那么\(v_{\pi} = v_{\pi'}\),且根据\(\eqref{eq:temp-4.9}\),有对于所有的\(s \in \mathcal{S}\),有

\[ \begin{aligned} v_{\pi'}(s) &= \max_{a}\mathbb{E}[R_{t+1} + \gamma v_{\pi '}(S_{t+1}) | S_t = s, A_t = a] \\ &= \max_{a}\sum_{s', r} p(s', r | s, a)\left[ r + \gamma v_{\pi'}(s') \right] \end{aligned} \]

注意到这个等式和\(\eqref{eq:value_function_optimal}\)中给出的Bellman方程具有相同的形式,这意味\(v_{\pi'} = v_{*}\),即为最优政策。这个结论给出了上述迭代过程的停止条件。

到这里我们讨论的都是确定性政策。在更加一般的情况下,随机政策\(\pi\)给出的是行为选择概率\(\pi(a | s)\)。我们这里不再深入到随机政策的细节研讨,不过这里可以给出的结论是本章节给出的概念都可以很容易地推广到随机政策的场景。