第一节 初探强化学习
1. 概念
广泛地讲,强化学习是机器通过与环境交互来实现目标的一种计算方法。 机器和环境的一轮交互是指,机器在环境的一个状态下做一个动作决策,把这个动作作用到环境当中,这个环境发生相应的改变并且将相应的奖励反馈和下一轮状态传回机器。这种交互是迭代进行的,机器的目标是最大化在多轮交互过程中获得的累积奖励的期望。
强化学习用智能体(agent)这个概念来表示做决策的机器。相比于有监督学习中的“模型”,强化学习中的“智能体”强调机器不但可以感知周围的环境信息,还可以通过做决策来直接改变这个环境,而不只是给出一些预测信号。
这里,智能体有3种关键要素,即感知、决策和奖励。
- 感知。智能体在某种程度上感知环境的状态,从而知道自己所处的现状。例如,下围棋的智能体感知当前的棋盘情况;无人车感知周围道路的车辆、行人和红绿灯等情况。
- 智能体根据当前的状态,计算出达到目标需要采取的动作的过程叫作决策。例如,针对当前的棋盘决定下一颗落子的位置;针对当前的路况,无人车计算出方向盘的角度和刹车、油门的力度。
- 奖励。环境根据状态和智能体采取的动作,产生一个标量信号作为奖励反馈。这个标量信号衡量智能体这一轮动作的好坏。例如,围棋博弈是否胜利;无人车是否安全、平稳且快速地行驶。【最大化累积奖励期望】是智能体提升策略的目标,也是衡量智能体策略好坏的关键指标。
【面向决策任务的强化学习】和【面向预测任务的监督学习】在形式上是有不少区别的:
- 首先,决策任务往往涉及多轮交互,即序贯决策;而预测任务总是单轮的独立任务。如果决策也是单轮的,那么它可以转化为“判别最优动作”的预测任务。
- 其次,因为决策任务是多轮的,智能体就需要在每轮做决策时考虑未来环境相应的改变,所以当前轮带来最大奖励反馈的动作,在长期来看并不一定是最优的。
2. 环境
生活中几乎所有的环境(或者说,系统)都在进行演变,例如一座城市的交通、一片湖中的生态、一场足球比赛、一个星系等,这在数学和物理中往往用随机过程来刻画。对于一个随机过程,其最关键的要素就是状态以及状态转移的条件概率分布。如果在环境这样一个自身演变的随机过程中加入一个外来的干扰因素,即智能体的动作,那么环境的下一刻状态的概率分布将由当前状态和智能体的动作来共同决定,用最简单的数学公式表示则是:
根据上式可知,智能体决策的动作作用到环境中,使得环境发生相应的状态改变,而智能体接下来则需要在新的状态下进一步给出决策。每一轮状态转移都伴随着两方面的随机性:一是智能体决策的动作的随机性,二是环境基于当前状态和智能体动作来采样下一刻状态的随机性。
3. 目标
智能体和环境每次进行交互时,环境会产生相应的奖励信号,其往往由实数标量来表示。整个交互过程的每一轮获得的奖励信号可以进行累加,形成智能体的整体回报(return)。根据环境的动态性我们可以知道,即使环境和智能体策略不变,智能体和环境交互产生的结果也很可能是不同的,对应获得的回报也会不同。因此,在强化学习中,我们关注回报的期望,并将其定义为价值(value),这就是强化学习中智能体学习的优化目标。
价值的计算有些复杂,因为需要对交互过程中每一轮智能体采取动作的概率分布和环境相应的状态转移的概率分布做积分运算。强化学习和有监督学习的学习目标其实是一致的,即在某个数据分布下优化一个分数值的期望。
对于一般的监督学习任务,我们的目标是找到一个最优的模型函数,使其在训练数据集上最小化一个给定的损失函数。在训练数据独立同分布的假设下,这个优化目标表示最小化模型在整个数据分布上的泛化误差(generalization error)
奖励函数是对于未来累积奖励的预测,评估给定策略下状态的好坏。相比之下,强化学习任务的最终优化目标是最大化智能体策略在和动态环境交互过程中的价值,而策略的价值可以等价转换成奖励函数在策略的占用度量上的期望,即:
二者优化的途径是不同的,监督学习直接通过优化模型对于数据特征的输出来优化目标,即修改目标函数而数据分布不变;强化学习则通过改变策略来调整智能体和环境交互数据的分布,进而优化目标,修改数据分布而目标函数不变。
但现在 RLFT 真的只能微调(顶多几个 epoch 就结束了),不管有没有收敛都得结束,再调下去原来的能力也要丢失了。目前仍缺少一个长期的、稳定的 RLFT 方法。
4. 数据
在强化学习中,数据是在智能体与环境交互的过程中得到的。如果智能体不采取某个决策动作,那么该动作对应的数据就永远无法被观测到,所以当前智能体的训练数据来自之前智能体的决策结果。智能体的策略不同,与环境交互所产生的数据分布就不同。
具体而言,强化学习中有一个关于数据分布的概念,叫作占用度量(occupancy measure),其具体的数学定义和性质会在第3章讨论,在这里我们只做简要的陈述:归一化的占用度量用于衡量在一个智能体决策与一个动态环境的交互过程中,采样到一个具体的状态动作对(state-action pair)的概率分布。
占用度量有一个很重要的性质:**给定两个策略及其与一个动态环境交互得到的两个占用度量,那么当且仅当这两个占用度量相同时,这两个策略相同。**也就是说,如果一个智能体的策略有所改变,那么它和环境交互得到的占用度量也会相应改变。
根据占用度量这一重要的性质,我们可以领悟到强化学习本质的思维方式。
- **强化学习的策略在训练中会不断更新,其对应的数据分布(即占用度量)也会相应地改变。**因此,强化学习的一大难点就在于,智能体看到的数据分布是随着智能体的学习而不断发生改变的。
- 由于奖励建立在状态动作对之上,策略对应的价值其实就是占用度量下对应的奖励的期望,因此寻找最优策略对应着寻找最优占用度量。
第二节 多臂老虎机
有一个拥有 根拉杆的老虎机,拉动每一根拉杆都对应一个关于奖励的概率分布 。我们每次拉动其中一根拉杆,就可以从该拉杆对应的奖励概率分布中获得一个奖励 。我们在各根拉杆的奖励概率分布未知的情况下从头开始尝试,目标是在操作 次拉杆后获得尽可能高的累积奖励。由于奖励的概率分布是未知的,因此我们需要在 “探索拉杆的获奖概率” 和 “根据经验选择获奖最多的拉杆” 中进行权衡。
有关多臂老虎机提出了算法的累积懊悔理论,-贪心算法、上置信界算法和汤普森采样算法在多臂老虎机问题中十分常用,其中上置信界算法和汤普森采样方法均能保证对数的渐进最优累积懊悔。多臂老虎机问题与强化学习的一大区别在于其与环境的交互并不会改变环境,即多臂老虎机的每次交互的结果和以往的动作无关,所以可看作无状态的强化学习。第 3 章将开始在有状态的环境下讨论强化学习,即马尔可夫决策过程。
第三节 马尔科夫决策过程
随机过程和马尔科夫过程
与多臂老虎机问题不同,马尔可夫决策过程包含状态信息以及状态之间的转移机制。如果要用强化学习去解决一个实际问题,第一步要做的事情就是把这个实际问题抽象为一个马尔可夫决策过程,也就是明确马尔可夫决策过程的各个组成要素。
随机过程(stochastic process)是概率论的“动力学”部分。概率论的研究对象是静态的随机现象,而随机过程的研究对象是随时间演变的随机现象(例如天气随时间的变化、城市交通随时间的变化)。当前 T 时刻的状态用 表示,所有可能的状态集合表示为 。在某时刻 的状态 通常取决于 时刻之前的状态,可以表示为:
当且仅当某时刻的状态只取决于上一时刻的状态时,一个随机过程被称为具有马尔可夫性质(Markov property)。马尔可夫过程(Markov process)指具有马尔可夫性质的随机过程,也被称为马尔可夫链(Markov chain)。我们用 描述这个马尔科夫过程,其中 是状态转移概率矩阵。
下图是一个具有 6 个状态的马尔可夫过程的简单例子。其中每个绿色圆圈表示一个状态,每个状态都有一定概率(包括概率为 0)转移到其他状态,其中通常被称为终止状态(terminal state),因为它不会再转移到其他状态,可以理解为它永远以概率 1 转移到自己。
给定一个马尔可夫过程,我们就可以从某个状态出发,根据它的状态转移矩阵生成一个状态序列(episode),这个步骤也被叫做采样(sampling)。例如,从 出发,可以生成序列等。
马尔可夫奖励过程
在马尔可夫过程的基础上加入奖励函数 r 和折扣因子 γ,就可以得到马尔可夫奖励过程(Markov reward process)。一个马尔可夫奖励过程由 构成,各个组成元素的含义如下所示:
- S 是有限状态的集合。
- P 是状态转移矩阵。
- r 是奖励函数,某个状态ss的奖励 r(ss)指转移到该状态时可以获得奖励的期望。
- 是折扣因子(discount factor),γ的取值范围为 [0,1)。引入折扣因子的理由为**远期利益具有一定不确定性,有时我们更希望能够尽快获得一些奖励,所以需要对远期利益打一些折扣。**接近 1 的 γ 更关注长期的累计奖励,接近 0 的 γ 更考虑短期奖励。
回报
在一个马尔可夫奖励过程中,从第 时刻状态 开始,直到终止状态时,所有奖励的衰减之和称为回报 (Return),公式如下:
其中,Rt 表示在时刻 t 获得的奖励。在下图中,我们继续沿用之前的例子,并在其基础上添加奖励函数,构建成一个马尔可夫奖励过程。例如,进入状态 s2 可以得到奖励 -2,表明我们不希望进入 s2,进入 s4 可以获得最高的奖励 10,但是进入 s6 之后奖励为零,并且此时序列也终止了。
价值函数
在马尔可夫奖励过程中,一个状态的期望回报(即从这个状态出发的未来累积奖励的期望)被称为这个状态的价值(value)。所有状态的价值就组成了价值函数(value function),价值函数的输入为某个状态,输出为这个状态的价值。
我们将价值函数写成 展开为:
在上式的最后一个等号中,一方面,即时奖励的期望正是奖励函数的输出,即 ;另一方面,等式中剩余部分 可以根据从状态 出发的转移概率得到,即:
上式就是马尔可夫奖励过程中非常有名的贝尔曼方程(Bellman equation),对每一个状态都成立。若一个马尔可夫奖励过程一共有 个状态,即 ,我们将所有状态的价值表示成一个列向量 ,同理,将奖励函数写成一个列向量 。于是我们可以将贝尔方程写成矩阵的形式:$$\nu=R+\gamma P\nu$$。
我们可以直接根据矩阵运算求解,得到以下解析解:$$\nu=(I-\gamma P)^{-1}R$$ ,以上解析解的计算复杂度是 ,其中是状态个数,因此这种方法只适用很小的马尔可夫奖励过程。求解较大规模的马尔可夫奖励过程中的价值函数时,使用动态规划、蒙特卡洛方法和时序差分,这些方法将在之后的章节介绍。
马尔科夫决策过程
马尔可夫过程和马尔可夫奖励过程都是自发改变的随机过程;而如果有一个外界的“刺激”来共同改变这个随机过程,就有了马尔可夫决策过程(Markov decision process, MDP)。我们将这个来自外界的刺激称为智能体(agent)的动作,在马尔可夫奖励过程(MRP)的基础上加入动作,就得到了马尔可夫决策过程(MDP)。马尔可夫决策过程由元组 构成,其中:
- S 是状态的集合;
- A 是动作的集合;
- 是折扣因子;
- 是奖励函数,此时奖励可以同时取决于状态 s 和动作 a;
- 是状态转移函数,表示在状态 s 执行动作 a 之后到达状态 的概率。
MDP 中的状态转移函数和奖励函数都比 MRP 多了动作 作为自变量。注意,在上面 MDP 的定义中,我们不再使用类似 MRP 定义中的状态转移矩阵方式,而是**直接表示成了状态转移函数。**这样做,一是因为此时状态转移与动作也有关,变成了一个三维数组,而不再是一个矩阵;二是因为状态转移函数更具有一般意义,例如,如果状态集合不是有限的,就无法用数组表示,但仍然可以用状态转移函数表示。
在马尔可夫决策过程中,通常存在一个智能体来执行动作。例如,一艘小船在大海中随着水流自由飘荡的过程就是一个马尔可夫奖励过程,它如果凭借运气漂到了一个目的地,就能获得比较大的奖励;如果有个水手在控制着这条船往哪个方向前进,就可以主动选择前往目的地获得比较大的奖励。
马尔可夫决策过程是一个与时间相关的,在智能体和环境 MDP 之间不断交互的过程。一般而言,它们之间的交互是如下图的循环过程:智能体根据当前状态选择动作;MDP 根据奖励函数和状态转移函数得到和反馈给智能体。智能体的目标是最大化得到的累计奖励。智能体根据当前状态从动作的集合中选择一个动作的函数,被称为策略。
策略
智能体的策略(Policy)通常用字母表示。策略表示在输入状态情况下采取动作的概率。
当一个策略是确定性策略(deterministic policy)时,它在每个状态时只输出一个确定性的动作,即只有该动作的概率为 1,其他动作的概率为 0;当一个策略是随机性策略(stochastic policy)时,它在每个状态输出的是关于动作的概率分布,然后根据该分布采样就可以得到一个动作。
在 MDP 中,由于马尔可夫性质的存在,策略只需要与当前状态有关,不需要考虑历史状态。
总言而之,原来马尔科夫过程只基于状态,现在同时基于状态和动作了,我们称其为基于策略。
我们用表示在 MDP 中基于策略的状态价值函数(state-value function),定义为从状态出发遵循策略能获得的期望回报。由于动作的存在,我们额外定义一个动作价值函数(action-value function)。我们用表示在 MDP 遵循策略时,对当前状态执行动作得到的期望回报。
不难看出,这两个函数存在以下关系:在使用策略中,状态的价值等于在该状态下基于策略采取所有动作的概率与相应的价值相乘再求和的结果:
另一方面,使用策略时,状态下采取动作的价值,等于 即时奖励 加上 经过衰减后的所有可能的下一个状态的状态转移概率与相应的价值的乘积:
综上,我们通过简单推导就可以分别得到两个价值函数的贝尔曼期望方程(Bellman Expenctation Equation):
状态价值函数的贝尔曼方程:
动作价值函数的贝尔曼方程:
接下来我们想要计算该 MDP 下,一个策略的状态价值函数。我们可以用蒙特卡洛方法来近似估计这个价值函数,好处在于我们不需要知道 MDP 的状态转移函数和奖励函数,它可以得到一个近似值,并且采样数越多越准确。
下图是一个马尔可夫决策过程的简单例子,每个浅色小圆圈旁的数字代表在某个状态下采取某个动作能获得的奖励。虚线箭头代表采取动作后可能转移到的状态,箭头边上的数字代表转移概率,如果没有数字则表示转移概率为 1。
蒙特卡洛方法(Monte-Carlo methods)也被称为统计模拟方法,是一种基于概率统计的数值计算方法。运用蒙特卡洛方法时,我们通常使用重复随机抽样,然后运用概率统计方法来从抽样结果中归纳出我们想求的目标的数值估计。一个简单的例子是用蒙特卡洛方法来计算圆的面积。
回忆一下,一个状态的价值是它的期望回报,那么一个很直观的想法就是用策略在 MDP 上采样很多条序列,计算从这个状态出发的回报再求其期望就可以了,即:
简单来讲,假设我们现在用策略从状态开始采样序列,据此来计算状态价值。我们为每一个状态维护一个计数器和总回报,计算状态价值的具体过程如下所示。
(1) 使用策略采样若干条序列:
(2) 对每一条序列中的每一时间步的状态进行以下操作:
更新状态的计数器;
更新状态的总回报;
(3) 每一个状态的值被估计为回报的平均值 。
根据大数定律,当 ,有。计算回报的期望时,除了可以把所有的回报加起来除以次数,还有一种增量更新的方法。对于每个状态和对应回报,进行如下增量式计算:
占用度量
在强化学习中,**占用度量(Occupancy Measure)**是指在一个策略下,某个状态和动作的组合在长期内被访问的频率(数据分布)。它告诉我们,某个状态-动作对在整个策略执行过程中“出现”的概率有多大。
我们可以用一个例子来说明:
假设你是一只老鼠,在一个迷宫里寻找奶酪。迷宫有不同的房间(状态),你可以在每个房间做出选择,比如向左或向右走(动作)。你有一套策略来指导你在每个房间的行动,可能是根据闻到奶酪味道的强弱来做出选择。
占用度量就是在长期探索中,你按照这个策略走了很多次迷宫后,统计在每个房间采取某个动作的频率。例如,你可能发现自己有80%的时间在某个特定的房间里选择向右走,而在另一个房间里只有20%的时间选择向左走。
这个度量在强化学习中很有用,本质上就是某个策略和环境交互时得到的数据分布本身。它能帮助我们理解策略的行为模式,以及在改进策略时,哪些状态和动作的组合最常使用,从而帮助我们优化策略。
贝尔曼最优方程
强化学习的目标通常是找到一个策略,使得智能体从初始状态出发能获得最多的期望回报。我们首先定义策略之间的偏序关系:当且仅当对于任意的状态都有 ,记为 。我们称这个策略为最优策略。
因此,我们定义了最优状态价值函数和最优动作价值函数,同时也得到了贝尔曼最优方程。
之后,我们将使用动态规划算法求解最优策略。