强化学习（一）- 强化学习介绍、Markov决策过程和贝尔曼期望方程

强化学习（英语：Reinforcement learning，简称RL）是机器学习中的一个领域，强调如何基于环境而行动，以取得最大化的预期利益。其灵感来源于心理学中的行为主义理论，即有机体如何在环境给予的奖励或惩罚的刺激下，逐步形成对

刺激的预期，产生能获得最大利益的习惯性行为。这个方法具有普适性，因此在其他许多领域都有研究，例如博弈论、控制论、运筹学、信息论、仿真优化、多主体系统学习、群体智能、统计学以及遗传算法。 – wikipedia

主要用到的资源：
《Reinforcement Learning: An Introduction》
在接下来的博客中，会遵循书中所规定的符号。

1.强化学习的组成

首先是两个基础元素，智能体（agent） 和环境（environment） 。

智能体（agent）是强化学习系统中的决策者和学习者，它可以做出决策和接受奖励信号。一个强化学习系统里可以有一个或者多个智能体。我们并不需要对智能体本身进行建模，只需要了解它在不同环境下可以做出的动作，并接受奖励信号。

环境（environment）本身可以是确定性的。也可以是不确定性的。环境可能是已知的，也可能是未知的。

除了只能体和环境之外，还有四个主要子元素: 策略（policy）、奖励信号（reward signal）、 价值函数（value function) 和可选的 环境模型(model of the environment)。

策略 定义学习智能体在给定时间的行为方式。粗略地说，策略就是从对环境状态的感知到在这些状态下要采取的行动的映射。它符合心理学中所谓的一套刺激-反应规则或关联分析（associations）。在某些情况下，策略可能是一个简单的函数或查找表，而在其他情况下，它可能涉及大量的计算，如搜索过程。策略是强化学习智能体的核心，因为它本身就足以决定行为。一般来说，策略可能是随机的，指定每个行动的概率。

奖励信号定义了强化学习问题的目标。在每个时间步长，环境向强化学习智能体发送一个单独的数字，称为奖励。智能体的唯一目标是使它在长期内获得的总回报最大化。因此，奖励信号定义了对智能体来说什么是好事，什么是坏事。在生物系统中，我们可能认为奖励类似于快乐或痛苦的体验。它们是行为人所面临的问题的直接和明确的特征。奖励信号是改变策略的主要依据；如果策略所选择的行动得到的回报较低，那么未来的策略可能会在这种情况下选择其他行动。一般来说，奖励信号可能是环境状态和所采取的行动的随机函数。

奖赏信号表明什么是即时意义上的好，而 价值函数 指定什么是长期意义上的好。粗略地说，一种状态的价值是智能体期望从该状态开始在未来积累的报酬总额。虽然奖励信号决定环境状态的直接可取性，但在考虑到接下来可能的状态和这些状态中可获得的奖励，价值函数则表明这些状态的长期可取性。例如，一个状态可能总是产生较低的奖励，但仍然具有较高的价值，因为在接下来会通常跟随一个拥有较高奖励的状态。或者情况正好相反。

做一个人类的类比，奖励在某种程度上类似于快乐(如果是高的)和痛苦(如果是低的)，而价值则对应于对我们在特定状态下对满意或不满意程度的更有远见的判断。从某种意义上说，奖励是主要的，而价值，作为对奖励的预测，是次要的。没有奖励就没有价值，评估价值的唯一目的就是获得更多的奖励。然而，我们在做和评估决策时最关心的是价值。

一些强化学习系统的第四个要素是 环境模型 。这是一种模仿环境行为的东西，或者更笼统地说，是一种可以对环境行为做出推断的东西。例如，给定一个状态和行为，模型可以预测下一个状态和下一个奖励的结果。模型是用于计划的，在实际经历未来可能发生的情况之前，通过对未来可能发生的情况进行考虑，从而决定采取何种行动。使用模型和计划来解决强化学习问题的方法被称为基于模型的方法，而不是简单的无模型的方法。无模型方法，即试错学习（trial-and-error）方法——几乎被视为计划方法的对立面。

2. 有限马尔可夫决策过程（Finite Markov Decision Processes）

MDPs是一种经典的顺序决策的形式化，在这种情况下，行为不仅影响即时的回报，还影响后续的情况或状态，并通过这些未来的回报。因此，MDPs涉及延迟奖励和权衡即时和延迟奖励的需要。

2.1 智能体 – 环境接口

MDPs是一个从交互中学习以实现目标的简单框架。学习者和决策者被称为智能体。它与之交互的东西，除智能体之外的一切，叫做环境。它们之间不断交互：智能体选择动作，环境响应这些动作并向智能体呈现新情况。环境也会产生奖励，这是一种特殊的数值，智能体通过选择行动，试图在一段时间内将其最大化。

更具体地说，agent和环境在一个离散时间序列的每个步骤中相互作用，t=0,1,2,3…。在每个时间步骤 t ，智能体接收到环境状态，S t ∈ S ,然后在此基础上选择行动，A t ∈ A ( s ) 。一个时间步后，作为其行动的部分结果，智能体收到一个奖励，R t + 1 ∈ R ,然后移动到一个新的状态，S t + 1。因此，MDP和智能体一起产生了这样一个序列或轨迹:

在有限MDP中，状态、动作和回报的集合（S 、 A 、 R ）都有有限的元素。在这种情况下，随机变量R t 和S t 有明确的离散概率分布，仅依赖于前一个状态和动作。对于随机变量的特定值，s ′ ∈ S ，r ∈ R，给定前一状态和动作的特定值，这些值在t时刻发生的概率是:

对于所有s ′ , s ∈ S , r ∈ R , a ∈ A 。函数p定义了MDP的动力（dynamics）。动力函数p : S × R × S × A → [ 0 , 1 ] 是一个普通的有四个参数的确定性函数。p函数中间的竖线“|”是来自于条件概率的符号，但这里它只是提醒我们p指定了s和a的每个选项的概率分布，也就是

在马尔可夫决策过程中，由p给出的概率完全描述了环境给出的动力。

2.2 目标和奖励

在强化学习中，主体的目的或目标被一种特殊的信号形式化，这种信号被称为奖励，从环境传递到主体。在每个时间步骤中，奖励是一个简单的数字，R t ∈ R 。非正式地说，智能体的目标是使它获得的奖励总量最大化。这意味着最大化的不是眼前的回报，而是长期累积的回报。我们可以把这个非正式的想法清晰地表述为奖励假设（reward hypothesis:）:

我们所说的目标和目的可以被认为是接收到的标量信号(称为奖励)累积和的期望值的最大化。

使用奖励信号使目标的概念形式化是强化学习最显著的特征之一。

虽然从奖励信号的角度制定目标乍一看可能会有局限性，但在实践中，它已被证明是灵活和广泛适用的。了解这一点的最好方法是考虑如何使用或可能使用它的例子。例如，为了让机器人学会走路，研究人员在每一个时间步数上提供与机器人的前进运动成比例的奖励。在让机器人学习如何从迷宫中逃生时，在逃生前每过一个时间步，奖励往往是-1；这鼓励智能体尽快逃生。为了让机器人学会寻找和收集空汽水罐进行回收，我们可能会在大多数时候给它零的奖励，然后每收集一个汽水罐就给+1的奖励。当机器人撞到东西或有人对它大喊大叫时，人们可能还想给它负奖励。对于一个智能体学习下跳棋或国际象棋，自然奖励是赢了+1，输了-1，平局和所有非最终位置的奖励为0。

智能体总是学会最大化它的回报。如果我们希望它为我们做一些事情，我们就必须以这样的方式为它提供奖励，使智能体在最大化奖励的同时也能实现我们的目标。因此，至关重要的是，我们设置的奖励要真正表明我们想要完成的目标。

特别是，奖励信号并不是向智能体传授如何实现我们希望它做的事情的先验知识的地方。 例如，一个下棋的智能体应该只对真正的胜利进行奖励，而不是对实现子目标进行奖励，比如夺取对手的棋子或获得棋盘中心的控制权。如果实现这些种类的子目标得到奖励，那么智能体可能会找到一种方法来实现它们而不实现真正的目标。例如，它可能会找到一种方法来夺取对手的棋子，甚至以输掉游戏为代价。奖励信号是你向机器人传达你希望它实现什么的方式，而不是你希望它如何实现的方式。

2.3 回报和事件(episodes)

到目前为止，我们已经讨论了非正式学习的目的。我们已经说过，智能体的目标是使其长期获得的累积回报最大化。这是如何正式定义的呢?

表示时间步t后得到的奖励序列R t + 1 , R t + 2 , R t + 3 ， … 那么我们希望最大化这个序列的哪个方面呢?

一般来说，我们寻求最大化预期回报（expected return,），其中回报，用G t 表示，被定义为奖励序列的特定函数。在最简单的情况下，回报是回报的总和:

G t = R t + 1 + R t + 2 + R t + 3 + … + R T (2.4) 

其中T为最后的时间步长。这种方法在有最终时间步自然概念的应用中是有意义的，也就是说，当主体与环境的交互自然地分解为子序列时，也就是我们称为事件（episodes） 的子序列，如游戏、迷宫旅行或任何类型的重复交互。每一个事件都以一种被称为终结状态的特殊状态结束，然后重置为标准起始状态或标准起始状态分布的样本。事件由不同的结束不同方式,如比赛胜利和失败,下一事件开始独立于前一个事件。因此，这些事件都可以被认为是以同一最终状态结束，不同的结果有不同的奖励。这种具有事件的任务称为事件性任务（episodic task）。在事件性任务中，我们有时需要区分所有非终端状态集合，用S表示，和所有状态加上终端状态集合，用S + 表示。终止的时间，T ，是一个随机变量，通常每个事件都是不同的。

另一方面，在许多情况下，智能体-环境的相互作用并不能容易的分为可分辨的事件，在很多情况下它们是无限地持续进行的。例如，形成持续过程控制任务的自然方法，或一个机器人的应用程序具有较长的寿命。我们称之为连续任务（continuing tasks）。对于连续任务来说，公式(2.4)是有问题的，因为最后的时间步长是T = ∞ T = \infinT=∞，而其返回值也将无穷大。

所以需要的另一个概念是折扣（discounting）。根据这种方法，智能体试图选择使其在未来获得的折现回报的总和最大化的行动。

其中，γ 为折扣因子，0 ≤ γ ≤ 1 。折扣因子决定了如何在最近的奖励和未来的奖励中进行折中。若指定γ = 0 ,智能体只会考虑眼前的利益，完全无视远期利益，就相当于贪心算法的效果。若指定γ = 1 ，智能体会认为当前的1单位奖励和未来的1单位奖励是一样重要的。对于连续性任务，一般设定γ ∈ ( 0 , 1 )。这时，如果未来每一步的奖励是有界的，则回报也是有界的。

连续时间步长的回报相互关联，这对强化学习的理论和算法很重要:

注意，尽管(2.6)是无限项的和，但如果回报是非零且恒定(γ < 1)，它仍然是有限的。例如，如果回报是常数+1，那么回报是

2.4 策略和价值函数

几乎所有的强化学习算法都涉及评估值函数状态函数(或状态动作对)，评估智能体在给定状态下有多好(或在给定状态下执行给定动作有多好)。这里的概念是根据未来的预期回报来定义的，确切地说，是根据预期回报来定义的。当然，智能体期望在未来得到的回报取决于它将采取什么行动。相应地，价值函数是根据特定的行为方式定义的，称为策略（policies）。

从形式上讲，策略是从状态到选择每个可能行动的概率的映射。如果agent在t时刻遵循策略，则π ( a ∣ s ) 是当S t = s时采取行动A t = a的概率。类似于p，π是一个普通函数。在π ( a ∣ s ) 中间的“|”只是提醒，它为每个s ∈ S 定义了一个a ∈ A ( s ) 的概率分布。强化学习方法指定了agent的策略是如何因其经验而改变的。

策略π 下状态s 的价值函数(value function)，记为v π ( s ) ，是以s 开始，之后是π 的预期回报。对于MDPs，我们可以正式定义v π ( s ) 

我们称q π 为动作价值函数（action-value function for policy π ）。价值函数v 和q 可以根据经验估计。例如，如果智能体遵循策略π ，并为所遇到的每个状态保持实际收益的平均值，那么平均值将收敛于状态s 的值v π ( s ) ，因为该状态遇到的次数趋于无穷。如果对每个状态下采取的每个行动保持单独的平均值，那么这些平均值将类似地收敛于行动值q π ( s , a )。我们称这种估计方法为蒙特卡洛方法，因为它们涉及对许多实际收益的随机样本进行平均。

2.5 贝尔曼期望方程

在强化学习和动态规划中使用的价值函数的一个基本属性是，它们满足递归关系，类似于我们已经为收益建立的递归关系。对于任何策略π 和状态s ，在s 的值与其可能继承状态的值之间保持以下一致性条件

其中存在来自于集合A ( s ) 的行动a ，来自于集合S 的下一个状态s ′ ′ (或s + ),来自于集合R ( s ) 的奖励r 。还要注意，在上一个方程中，我们是如何把两个和合并起来的，一个是所有s ′  的值另一个是所有r 的值，合并成一个对所有可能值的和。我们经常使用这种合并和来简化公式。请注意，最终的表达式可以很容易地作为预期值读取。它实际上是这三个变量a , s ′ , r 的值的和。对于每个三元数组，我们计算它的概率π ( a ∣ s ) p ( s ′ , r )，用这个概率给括号中的量赋权，然后对所有可能性求和得到一个期望值。

等式(2.9)是v π  的贝尔曼方程（Bellman equation），它表达了一个状态的值和它的后续状态的值之间的关系。如上图所示，从一个状态向前看，可以看到它可能的后续状态。每个开放的圆圈代表一个状态，每个实心圆圈代表一个状态动作对。从状态s，也就是最上面的根节点开始，智能体可以根据它的策略，采取图中所示的某一组行动中的任意三个。从每一个状态开始，环境可能会响应几个下一个状态中的一个，s ′(图中显示了两个)，以及一个奖励，r ，取决于其由函数p pp给出的动力。 贝尔曼方程(2.9)对所有的可能性进行平均，通过其发生的概率对每一个进行加权。它指出，开始状态的值必须等于预期下一个状态的（折扣）值，加上沿途预期的回报。价值函数v π 是其Bellman方程的唯一解。我们把上面这样的图称为备份图(backup diagrams)，因为它们图示的关系构成了更新或备份操作的基础，而这些操作是强化学习方法的核心。这些操作将值信息从其继承状态(或状态操作对)传回到状态(或状态操作对)。

2.6 最优策略和最优价值函数

2.7 贝尔曼最优方程

2.8 单步动力

2.9 小结

相关实例参考强化学习（三） – Gym库介绍和使用，Markov决策程序实例，动态规划决策实例

状态空间S 是所有(非终点)状态的集合。在事件性任务中，我们使用S +  来引用所有状态集合，包括终点状态。

动作空间A  是可能动作的集合。(或者，A ( s ) 指的是s ∈ S 中状态s 中可用的一组可能操作)环境的单步动力决定了环境如何决定每一步的状态和奖励。对于每一个可能的s ′ , r , s , a 。动力可以通过指定p （ s ′ ， r ∣ s ， a ） ≐ P （ S t + 1 = s ′ ， R t + 1 = r ∣ S t = s ， A t = a ）来定义。

(有限)马尔可夫决策过程(MDPs) :

状态的(有限)集合 S （或者S +, 在事件任务中)

动作的(有限)集合 A 

奖励集合 R

环境的单步动力

折扣因子 γ ∈ [ 0 , 1 ]