（十 一）从零开始学人工智能--强化学习: 强化学习入门基础

强化学习入门基础

文章目录

• 强化学习入门概述

  • • 1. 强化学习入门概述
    • • 1.1 强化学习发展历史
      • 1.2 强化学习核心特征
      • 1.3 强化学习应用场景
      • 1.4 强化学习基本原理
      • 1.5 强化学习构成要素
      • 1.6 强化学习分类方法

• 2. 动态规划

  • • 2.1 动态规划的概念
    • 2.2 DP技术的核心思想
    • 2.3 DP技术的关键概念
    • • 2.3.1 阶段决策模型分析
  • 2.3.2 动态规划相关术语解析

• 2.4 动态规划的核心要素

• 2.5 动态规划适用范围

• 2.6 动态规划的具体案例

• • 2.6.1 路线迷宫问题实例

• 2.6.2 零一背包问题实例

  • 3. 马尔可夫决策过程

  • • 3.1 马尔可夫过程
    • 3.2 马尔可夫决策过程

  • 声明

  • 参考资料

1. 强化学习基础知识

强化学习（reinforcement learning）源自行为心理学原理作为一个机器学习范畴，在人工智能科学中占有重要地位。它关注的是智能体（agent）在特定环境下采取一系列行动（action），以期达到预设目标并最大化预期收益（reward）。这一问题涉及多个交叉学科领域的深入研究工作：包括博弈理论分析、控制系统设计、信息科学探讨、运筹优化策略制定以及基于模拟的改进方法开发等多个方面展开深入探讨。特别是在运筹学与控制理论中，强化学习方法被专门归类为近似动态规划技术的一种典型应用形式。

1.1 强化学习发展历程

1956年Bellman提出了动态规划方法。

1977年Werbos提出只适应动态规划算法。

1988年sutton提出时间差分算法。

1992年Watkins 提出Q-learning 算法。

1994年rummery 提出Saras算法。

1996年Bersekas提出解决随机过程中优化控制的神经动态规划方法。

2006年Kocsis提出了置信上限树算法。

2009年kewis提出反馈控制只适应动态规划算法。

2014年silver提出确定性策略梯度（Policy Gradients）算法。

2015年Google-deepmind 提出Deep-Q-Network算法。

可以看出, 强化学习经历了几十年的发展, 并非新兴领域. 自2016年以后, 在AlphaGo击败围棋世界冠军李世石后, 融合了深度学习的强化学习技术得以迅速崛起. 总体而言, 在过去几十年中它既是传统又是前沿的技术.

图1 AlphaGo对战李世石

1.2 强化学习特点

我们先看看机器学习的分类：

图2 机器学习分类

可以看出机器学习包括三大类：有监督学习、无监督学习和强化学习。

回顾下前面课程讲过的有监督学习和无监督学习：

（1）有监督学习 即为由教师指导的学习过程。其特点是数据集中的每一项均被赋予明确的标签或属性值。在数据集中每一个样本希望算法能够预测并准确输出结果。以具体任务为导向主要包含两个核心问题：回归问题即预测连续型变量；分类问题则涉及对离散型变量的识别。

（2）无监督学习 ：也可称为无指导学习，通常不带标签的数据。基于数据驱动的方法，包括聚类等技术。

那么，什么是强化学习呢？

强化学习（Reinforcement Learning, RL） 是一种广泛应用于决策与控制系统中的技术；它通过接收状态信息来规划动作。其核心目标是通过在环境中采取行动来最大化累积奖励。

强化学习是一种基于当前环境条件的学习机制，在完成每一个具体动作后会实现最大化预期利益。这种学习方法的思想起源于行为主义心理学理论框架中对有机体如何通过外部奖励与惩罚刺激而形成特定反应的研究。例如，在训练狗狗站立时，则可观察到以下情况：如果狗狗立起了，则给予肉条等食物作为即时奖励；若未能立起，则用鞭子对其施加适度惩罚。通过持续不断地进行这样的强化训练过程，则可使狗狗逐渐掌握并形成这一动作的习惯。

在强化学习中也同样通过对这些样本进行算法训练，在没有明确指导的情况下完成所有样本处理后会根据结果进行评估，并通过不断优化策略和行为来实现最佳状态。

因此，相比于有监督学习和无监督学习，强化学习有以下特点：

（1）没有监督数据，只有奖励信号 ；

（2）奖励信号不一定是实时的，而很可能是延后的，即一般具有延时性 ；

（3）时刻（序列） 是一个关键因素；强化学习中的每一时刻都紧密地关联着这一序列。

（4）当前的行为影响后续接收到的数据；

1.3 强化学习应用

当下，在多个细分领域中进行深入研究和广泛应用。

图3 强化学习应用

1.4 强化学习基本概念

强化学习是根据当前的条件作出决策和动作，以达到某一预期目标。

智能体（Agent） 是强化学习中的行为实体，在某一环境中运行。每一次时刻下,智能体与环境各自拥有特定的状态。根据当前状态,智能体选择一个行为,并执行该行为。随后,它与环境转移到下一个阶段,同时系统给予相应的奖励或惩罚,以迫使智能体执行正确的策略。

（1）奖励 Reward

奖励R_t作为信号反馈使用，并且它是一个标量值来反映智能体在时间t时的表现水平。为了实现目标的优化过程, 智能体旨在通过最大化累积奖励来实现目标

强化学习通常建立在以下假设基础之上：所有目标均可表示为最大化累计奖励的形式

例子：玩游戏时分数的增加/减少。

（2）序列决策 Sequential Decision Making

目标：选择一系列动作来最大化未来的总体奖励；

这些动作可能产生长期的后果；

奖励可能是延迟的；

为了获取额外的长远利益（long-term reward），有时会以牺牲当前利益（immediate reward）；

例子：下棋，每一步棋没有奖励，只有在棋局结束时才有输/赢的反馈；

（3）智能体和环境 Agent and Environment

图4 智能体和环境

上图中，大脑代表智能体，地球代表环境。

（4）历史和状态 History and State

历史由观测、动作和奖励构成的一个序列：
H_t = O_1,R_1,A_1,...,A_{t-1},O_t,R_t
该序列反映了过去的动态行为及其结果：
H_t代表第t步的历史，
其中，
O₁表示第一步的观测，
R₁表示第一步的结果，
A₁到A_{t−1}表示第一步到第t−1步的动作，
Oₜ表示第t步的观测，
Rₜ表示第t步的结果。

①、智能体选择动作；

②、环境选择观测/奖励；

状态反映了未来可能发生的情况，并基于历史数据形成：
S_t = f(H_t)
其中，

• 环境状态 描述了环境中的物体及其物理特性；
• 智能体状态 记录了智能体自身的感知以及其他感知；
• 信息状态 包含了外部传感器和其他传感器收集到的数据。
  具体情况请参考下文详细说明。

①、环境状态S^e_t是环境的专用表示，在强化学习中被设计为负责生成所有后续观测与奖励的数据流；然而，在这种设计下，在大多数情况下该状态信息对于智能体来说是不可见于其感知系统的。即便s^e_t的状态信息被获取到了，在实际应用中也可能包含与当前任务执行无关的信息

该智能体的状态S^a_t代表了其内部信息，并且这些信息构成了其行动决策的基础。这些状态信息为强化学习算法提供了决策依据，并且它们能够反映当前情境下的相关信息。这些状态变量通常定义为历史事件的函数：S^a_t = f(H_t)

③、信息状态（又称为Markov状态）包括历史的所有有用信息。

该状态S_t满足马尔可夫性质，则当且仅当：

P[S_{t+1}|S_t] = P[S_{t+1}|S_1,\ldots,S_t]

即当前的状态足以包含所有相关的过去信息；一旦当前的状态已知，则无需依赖过去的全部历史信息。

（5）完全可观测环境 Fully Observable Environments

图5 完全可观测环境

（6）部分可观测环境 Partially Observable Environments

部分可观察性：智能体通过间接途径对环境进行感知，在游戏如英雄联盟或王者荣耀中，玩家仅能获取视野范围内的情报。

在这种情况下，智能体状态≠环境状态；

这类问题被归类为部分可观测的马尔可夫决策过程（Partially Observable Markov Decision Process, POMDP）。

此时，智能体必须构建自己的状态表示S^a_t，例如：

①、记住完整的历史：S^a_t=H_t；

采用基于循环神经网络的方法，在每一步中仅受限于智能体t-1时刻的状态s^{a}_{t-1}以及当前观测o_t的信息基础之上计算出当前状态s^{a}_t的表示；其中权重参数s_w和o_w分别代表状态相关的权重与观测相关的权重。

（7）学习和规划 Learning and Planning

在序列决策中主要包括两类基本问题：

①、学习：环境在初始时是未知的，智能体通过与环境交互来改善它的策略；

规划：基于已知环境模型的智能体将执行计算以优化和改进控制策略；而无需与环境进行任何交互以实现预期目标。

（8）探索和利用 Exploration and Exploitation

强化学习是一种基于**试错（trail-and-error）**的学习机制，在此机制下，智能体（agent）通过与环境的互动中探索有效的策略，并避免在探索过程中过于重视短期奖励而可能导致长期收益的损失。

探究（Exploration）旨在获取关于环境的关键信息；通过采用多种策略获取相关信息，并有助于做出更优决策。

采用（Exploitation）是一种基于现有可获得的信息，并被选择为目前看来最佳的方法以实现最大的回报。

探究（未知信息）与开发（已有信息）之间存在着本质上的矛盾关系，在实际操作中若一味追求开发已掌握的信息，则可能会导致有限程度的优化效果而无法实现全局最优解；反之若完全依赖探究未知领域，则可能因缺乏有效指导而导致整体性能较低的结果；因此，在智能体进行决策时必须建立合理的权衡取舍机制以实现两者的平衡融合。

例如，在选择用餐地点时

（9）预测和控制 Prediction and Control

预测：给定 一个策略，来评估 未来的奖励；

控制：发现 一个策略， 来优化 未来的奖励；

1.5 强化学习智能体的主要组成部分

强化学习智能体（RL agent）主要由三部分组成：

（1）策略 Policy

策略是智能体的行为，是状态s到动作a的映射。

在所有情况下（即无论处于何种状态），智能体采取的动作都是唯一的；例如，在一个红绿灯路口中：

• 当遇到绿灯时（s=green light），智能体采取的动作是通过；
• 当遇到红灯时（s=red light），智能体采取的动作是停止。
  这种特性使得deterministic policies能够保证系统的稳定性与可预测性。

②、在处理具有不确定性的（随机性）策略时，智能体在某一状态时可采取的动作种类丰富；其核心机制在于通过策略函数对每种可选动作采取的概率度量，并据此进行决策：即按照相应的概率值从所有可选动作中进行选择；例如，在 typical 交叉路口场景中，在一个给定的状态下智能体可能会选择直行、左转或右转这三个动作中的一个。

（2）价值函数 Value Function

价值函数用于预测未来的奖励，并用于评估状态的质量进而影响动作的选择；例如：

模型是智能体对环境的表示，体现了智能体是如何思考环境运行机制的。

模型至少解决两个问题：

①、状态转移几率是预测下一状态发生的概率：
p_{s,s'}^{a} = P[S_{t+1}=s' | S_t=s, A_t=a]
②、立即奖励是预测下一动作可以获得的立即奖励：
R_s^a = E[R_{t+1} | S_t=s, A_t=a]

1.6 强化学习的分类

（1）按智能体的成分 分类：

基于价值函数（Value-Based）：该方法通过定义对状态或动作的价值进行评估，并利用这些信息来衡量达到该状态或执行该动作所获得的即时奖励；同时该系统会优先选择具有最高价值的状态或采取相应行动以最大化总奖励

注

③、Actor-Critic ：既有价值函数，也有策略函数，两者相互结合解决问题。

图6 按智能体的成分分类

（2）按有无模型 分类：

①、有模型/基于模型 （Model Based）：智能体通过构建关于环境动作过程的模型来指导价值或策略函数的优化；这类方法主要依赖于动态规划算法框架下的策略迭代和值迭代方法。

②、无模型/不基于模型 （Model Free）：智能体无需关于环境的具体信息，并无意愿去理解环境的工作原理；其主要关注点在于价值函数或策略函数；该方法主要包含蒙特卡洛算法 和时序差分学习 等技术手段；

图7 按有无模型分类

除此之外，在机器学习算法中还存在其他划分标准。例如，在根据环境特征划分的基础上进一步细化为：根据环境是否全可观察分为主类与次类；而从采用的学习机制角度则可分为经典强化学习方法与基于深度学习的强化学习技术等。

2. 动态规划

在什么情况下需要介绍动态规划？ 在开篇部分提到，在运筹学与控制理论领域中存在一个称为近似动态规划的方法用于研究强化学习的方法。 动态规划的核心思想是将复杂的问题分解为相互关联的小问题，并按照一定的顺序逐一解决。 需要注意的是，在广义上讲强化学习也属于多阶段决策过程的一种表现形式：智能体通过执行一系列多阶段的决策来实现收益的最大化目标。 因此掌握动态规划对于深入理解强化学习具有重要意义。

2.1 什么是动态规划

图8 Quora关于动态规划的回答

用一句话说明动态规划的核心概念就是"记住过去经历过的任务"；如果更精确一点，则是"记住过去获得的最佳结果"

2.2 动态规划基本思想

下面让我们了解一下分治法：它是一种解决问题的有效策略，在此方法中我们首先将原问题划分为较小规模的子problem；接着逐一解决每个subproblem；最后将所有已解决的subproblem整合起来以获得original problem的整体solution；特别地在这一过程中各subproblems彼此之间互不干扰

动态规划与分治法在本质上具有相似性；其特点在于各个子问题之间存在相互关联；通常涉及时间或空间维度上的顺序性；在解决过程中按照特定顺序依次处理各个子问题；通过存储机制避免重复计算；将结果逐步计算并存储起来；从基础到最终目标逐步完成整个过程

由此可见，在解决一个动态规划问题时，主要需要从两个角度进行分析：一是找出各子问题之间的联系，并将各个子问题的结果存储起来。

2.3 动态规划基本概念

下面将通过图9路径选择问题对动态规划进行详解。

图9 路径选择问题

2.3.1 多阶段决策问题

如果一种系统工程可以划分为若干个相互关联的部分，在每一个部分都需要制定相应的行动方案，并且当前阶段的动作通常会受到前一阶段的影响，则称这种系统工程为多阶决策体系。

在多阶段决策问题中，在每个时间段内进行的一系列行动（或步骤）所采取的策略通常与时间有关。当前的状态直接影响着下一步的状态，并会引起系统状态的变化。一系列连续的动作构成了系统的动态过程，并具有动态特性的特征。这种方法被称为动态规划法。

在图9中，所求解的问题是：A点到E点；这个问题就是个多阶段决策问题。

2.3.2 动态规划一些术语

（1）阶段：将所给求解问题的过程合理地分解为若干个相互关联的小部分，并按照一定的顺序依次处理这些小部分，在每个阶段解决一个小部分的问题后就完成了一个完整的阶段的操作步骤。

在图9中，阶段：图中的4个阶段；

（2）状态：每个阶段初期都体现着所面临的具体初始条件。这些初始条件具体而言就是在求解子问题时已知的已知条件。状态表征了研究过程中所处的状态。

在图9中，在阶段1的情况下状态为A，在阶段2的情况下状态分别为B₁、B₂和B₃，并依此类推的情况继续下去。由此可知各时期的状态集合可用以下方式表示：S_1 = \{ A \}

S_2=\{B_1, B_2, B_3\}

S_3=\{C_1, C_2, C_3\}

S_4=\{D_1, D_2\}

将最终阶段（标记为E的点）定义为状态S_5。则该阶段的状态定义为：
状态变量S_5 = \{E\}
在此处被定义为状态变量S_5以对应图9中的描述。然而，在实际应用中我们通常以初始状态变量 S_0 = \emptyset 作为起始条件。

（3）决策：决策行为体现为从当前状态向下一状态过渡时所采取的行动选择。

在图9所示的位置，在当前处于阶段1的状态（即状态为A），系统会引导至下一阶段（即阶段2）的状态；在此情境下可选的选项包括B₁、B₂及B₃这三个选项；在这里的抉择即构成了一个决策点；

（4）策略 ：策略表示由所有阶段的决策组成的决策序列。

当图9中的4个阶段分别选择为B₁、C₁、D₁和E时，则由这些选择构成的序列（A → B₁ → C₁ → D₁ → E）即构成一个策略。

（5）状态转移方程 ：状态转移方程定义了两个相邻阶段状态之间的转换过程，并揭示了它们之间的演变方式。

在图9所示的情况下，请考虑x节点与之相邻的另一个节点为y节点，则定义从x节点到终点节点E的距离为d(x)、从y节点到终点节点E的距离为d(y)、以及从x\rightarrow y\text{ }路径的距离为map(x,y)，那么状态转移方程就可以表达为： d(x) = d(y) + map(x,y)$
（6）最优策略：即所有可选策略中成本最低且性能最佳的一种决策方案。

在图9所示的图形中, 若要寻求最佳策略, 即是从A点经过B₂、C₁、D₁到达E点的最短路径问题, 其中最佳路径为: A \rightarrow B_2 \rightarrow C_1 \rightarrow D_1 \rightarrow E

2.4 动态规划三要素

使用动态规划解决问题时，最重要的的是确定动态规划三要素：

（1）问题拆分 ：将原问题拆解为子问题，并找到子问题之间的具体联系；

（2）状态定义 ：定义每个阶段的状态；

（3）状态转移方程的求解过程：确定从前一阶段到下一阶段之间的递推关系式；

2.5 动态规划适用条件

（1）最优化原理 表明，在某些情况下（即当每个局部选择都是全局最优时），一个问题的整体最优可以通过分解为局部最优来实现。该问题是满足这一性质的问题实例。例如，在动态规划中常利用这一性质来构建算法

（2）无后效性：在动态规划中指出，在某一特定阶段的状态一旦被确定之后，则该状态下所做出的所有决策都只依赖于这一特定状态而不考虑其之前的任何历史信息。也就是说，在某一具体阶段的状态能够完整地反映其之前的全部信息。

（3）子问题间的重叠性：子问题并非完全独立，并且同一个子问题可能会在后续阶段决策中被多次调用或引用。

2.6 动态规划例子

本节将基于路径迷宫 和 0-1背包 两个典型案例复习如何运用三要素求解动态规划问题

2.6.1 路径迷宫问题

问题描述 ：

该机器人起始位置设于m \times n网格的左上角角落，并通过每步只能向右或向下移动一格的方式逐渐推进至目标位置定位于该网格的右下角区域。请问从起始点到目标点共有多少条可行路径？

图10 路径迷宫问题

例如：上图是一个3 \times 7的网格，有多少可能的路径？

根据动态规划三要素来对该问题进行求解：

（1）问题拆分 ：

这个问题涉及机器人从起始位置到目标位置的移动路径规划。移动至相邻上方或左方的单元即可实现当前单元的位置确定。通过将当前单元的问题分解为上方和左方单元的问题处理方式，则可按照上述方法逐步推进直至起始位置

（2）状态定义 ：

在问题求解过程中涉及到了(i,j)单元与其他相邻单元((i−1,j)和(i,j−1))之间的关系，请问它们之间存在怎样的关联呢？具体来说，在考虑(i−1,j)单元的问题解答时，默认情况下其答案其实就是从"Start"节点到该单元路径的数量，在这种情况下再结合(i,j−1)单元的信息就可以得到当前状态下的计算依据了。因此我们可以将(i,j)单元的状态定义为"从 Start 到达当前(i,j)单元所需经过的所有路径数量"。

（3）状态转移方程推导 ：

基于状态定义可知，在实现过程中，请记住以下要点：
对于每个位置(i,j)来说，在到达该位置之前的所有可能路径都源自其左侧单元格(i−1,j)或上侧单元格(i,j−1)。因此，请记住以下关系式：
f(i,j) = f(i−1,j) + f(i,j−1). 请注意，在初始状态下（即机器人位于第一行或第一列时），所有起始位置仅有一种到达方式

参考代码：

    class Solution {
    public int countPaths(int m, int n) {
        int[][] f = new int[m][n];        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0)
                    f[i][j] = 1;
                else {
                    f[i][j] = f[i - 1][j] + f[i][j - 1];
                }
            }
        }
        return f[m - 1][n - 1];        
    }
    }

2.6.2 0-1背包问题

问题描述 ：

共有N个物体,每个物体都有其特定的质量和价值,其中第i个物体（i从1开始计数）的质量为w[i],价值为v[i],当所有物体的总质量不超过背包的最大载重能力W时,能放入背包中的最大总价值是多少？

图11 01背包问题

在这里，在应用暴力穷举的方式时，请注意每个物品都有被选中或未被选中的两种可能性；由此可见，在这种情况下总共有2^N种组合方式；计算量极大。

如果按照动态规划的方法，根据动态规划三要素来进行求解：

（1）问题拆分 ：

本问题旨在通过优化书包内的物品组合以实现最大总价值；其中涉及的关键变量包括物品的选择及其对应的重量限制

定义dp[i][j]为将前i件商品放入限重j的背包所能达到的最大价值，则有i\in[0,N]且j\in[0,W]。

当背包的限重为j时，对于第i件物品，有两种选择：

①、背包容量充足可容纳所有物品的选择放入；此时背包剩余容量变为j - w_i（即j - w_i），所选物品总价值等于选取前i-1个物品所得的最大值再加第i个物品的价值v_i。

②、背包限重不足，不放入；此时背包的限重为j，价值为dp[i-1][j]；

通过以上两种方式进行重复，直到放入物品的数量为0为止。

（2）状态定义 ：

基于问题各个阶段的描述，在动态规划中可以将第i个阶段的状态定义为dp[i][j]表示前i件商品装入限重为j的背包所能获得的最大价值。

（3）状态转移方程推导 ：

基于问题阶段的状态定义，在第i阶段背包的最大总价值由上述两种情况中的较大者决定。其状态转移方程为：

dp[i][j] = \max(dp[i-1][j], dp[i-1][j-w_i] + v_i) \quad \text{当} \quad j \geq w_i

参考代码：

    for (int i = 0; i <= N; i++) {
    	for (int j = 0; j <= W; j++) {
    		if (j < w[i])
    			dp[i][j] = dp[i - 1][j];
    		else
    			dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
    		}
    	}

3. 马尔可夫决策过程

在机器学习领域中，“常被视为一个马尔可夫决策过程(MDP)”

3.1 马尔可夫过程

（1） 马尔可夫特性 Markov Property

在上面介绍强化学习的信息状态时，介绍到：

状态S_t被称为Markov性质的条件是：
对于任意时间t有 P[S_{t+1}|S_t] = P[S_{t+1}|S_1,...,S_t]
也就是说，在这种状态下完整地记录了所有相关的过去信息后即可做出决策；一旦当前的状态已知，则无需关心任何过去的细节。

马尔可夫特性：当一个随机过程在已知当前状态下并考虑到所有过去的状况时，其未来的行为将只受当前状态的影响而不会受到过去其他因素的影响。

（2） 马尔可夫过程 Markov Process

马尔可夫过程：也被称作马尔可夫链（Markov Chain），是一个没有记忆能力的随机过程。其中，在概率论中所讨论的随机过程是指一个系统在时间线上发生的随机变化。简言之，在这种情况下我们可以认为马尔可夫过程是一系列遵循马尔科夫特性的一系列随机状态S_1, S_2, …随时间演变的过程。

马尔可夫过程通常用二元组表示：

其中，S是一个有限的状态集合，并且 P 是一个状态转移概率矩阵。

基于马尔可夫状态s及其后续的状态s', 状态转移概率被定义为：

P_{ss'} = P[S_{t+1}=s'|S_t=s]

由矩阵元素构成的状态转移矩阵包含了所有可能的状态转移的概率：

\begin{array}{*{20}{c}} {{P_{1… & {{…, {P_{n×n}}}} \end{array}

其中n是对应的状态的数量；每一行元素之和等于1。

3.2 马尔可夫决策过程

不同于马尔可夫过程，在马尔可夫决策过程（MDP）中，智能体能够执行动作，并从其自身及其环境的状态进行调整，并获得反馈（即给予系统的惩罚或提供系统的奖励）。

MDP可以表示成一个五元组：

其中，S为有限的状态集合；

A为有限的动作集合；

P为状态转移矩阵，P^a_{ss'} = P[S_{t+1}=s' | S_t=s, A_t=a]；

我们用R来代表奖励函数（reward function）。根据定义，在状态s和动作a的情况下，在时刻t时的即时奖励期望值由公式 R_s^a = E[{R_{t + 1}}|{S_t} = s,{A_t} = a] 给出；其中这个函数表示的是即时奖励的期望值；具体来说，在当前状态s和采取动作a 的情况下，在下一个时刻t+1 能够立即获得的奖励值就是这个期望。

\gamma为折扣因子（discount factor），\gamma \in [0,1]；

（1）回报 Return

强化学习的主要目标在于实现特定目标。当前动作的执行结果将影响系统的后续状态。因此必须评估未来可能获得的回报水平。这些回报的影响具有时间滞后性。

阐述回报（Return）的概念：G_t表示从t时刻起后续一系列动作所能获得的总奖励。其具体形式为：

{G_t} = {R_{t + 1}} + \gamma {R_{t + 2}} + ... = \sum\limits_{k = 0}^\infty {{\gamma ^k}{R_{t + k + 1}}}

其中折扣因子\gamma衡量了未来奖励相对于当前时间点的价值权重。

在k+1步后，获得的奖励R在t时刻体现的价值是{\gamma} ^k R；

随着\gamma趋近于零，在模型中倾向于实施一种以短期效果为导向的评估机制；而随着\gamma逐渐接近1的时候，则会更加注重长期利益的考量。

使用折扣因子\gamma的原因：

由于未来事件的不可预测性以及执行特定动作未必导致预期的状态变化，在时间推移中难以准确预测未来的回报值；因此，在时间推移中，未来的奖励权重会逐渐减弱。

②、如果不加上折扣因子，当状态无限时，会导致求和项趋向于无穷大，不收敛；

③、更符合人类/动物的行为：偏好即时奖励R_{t+1}；

（2）策略 Policy

策略\pi是在给定状态下描述了动作的概率分布体系，在MDP模型中通过\pi(a|s)来定义状态s下采取动作a的可能性大小：
\pi(a|s)=P[A_t=a|S_t=s]
一个完整的策略则全面规范了智能体的行为模式，在各个状态s下明确了智能体采取各种可能动作a及其发生的概率值。

MDP的策略仅和当前状态有关，与历史信息无关；

（3）价值函数 Value Function

类似于在有监督学习中为了评估预测能力而设定损失函数，在强化学习中同样需要通过建立价值评估体系来衡量策略的有效性

价值函数由状态价值函数（state-value function）v_{\pi}(s)和动作价值函数（action-value function）q_{\pi}(s,a)组成。

①、状态价值函数v_{\pi}(s)表示在状态s下，遵循策略\pi执行动作，能够获得的回报期望；或者说当执行策略\pi时，评估智能体处在状态s时的价值大小，即：
v_{\pi}(s)=E_{\pi}[G_t|S_t=s]
②、动作价值函数q_{\pi}(s,a)表示在遵循策略\pi时，对当前状态s执行具体的动作a时所能获得的回报期望；或者说在执行策略\pi时，评估处在状态s时执行动作a的价值大小，即：
q_{\pi}(s,a)=E_{\pi}[G_t|S_t=s,A_t=a]
动作价值函数除了指定状态s和策略\pi外，还指定了在当前状态s时执行的动作a。这个函数衡量的是按照某一策略，在某一状态时执行各种动作的价值。

（4）贝尔曼期望方程 Bellman Expectation Equation

状态价值函数由立即奖励与其后续状态的价值构成，在策略π下的期望值可表示为：

v_{\pi}(s) = E[R_{t+1} + \gamma v_{\pi}(S_{t+1}) | S_t = s]

而动作价值函数则等于立即奖励与后续状态下采取对应行动的价值之和，在策略π下的期望值可表示为：

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

它们之间存在特定的转换关系。

此图中采用无填充的圆形符号表示状态节点、带有黑色填充的圆形符号表示操作节点，并通过连线建立操作与状态之间的联系。

①、使用q_{\pi}(s,a)表示v_{\pi}(s)：
{v_\pi }(s) = \sum\limits_{a \in A} {\pi (a|s){q_\pi }(s,a)}

图12\ 以q_{\pi}(s,a)为指标来表示v_{\pi}(s) ②、通过将q_{\pi}(s,a)表达为v_{\pi}(s)\ 的形式来实现状态-动作价值函数的计算； {q_\pi }(s,a) = R_s^a + \gamma \sum\limits_{s' \in S} {P_{ss'}^a{v_\pi }(s')}$

图13\ 该图表以v_π(s)的形式代表q_π(s,a)。
综合以上两种情形进行整合后，则有：

{v_π}(s)=∑ₐ∈A π(a| s)(R_s^a + γ ∑ₙ∈S P_ss'^{n a}{v_π}(n))

{q_\pi }(s,a) = R_s^a + \gamma \sum\limits_{s' \in S} {P_{ss'}^a\sum\limits_{a' \in A} {\pi (a'|s'){q_\pi }(s',a')}}

（5）最优价值函数 Optimal Value Function

V^*(s) 是从各种策略所对应的各态历经值中取自于其最大化的那个值；
类似地，在各个状态下采取不同动作所能获得的最大期望效用即为Q^*(s,a)；
而这些最优的价值度量则完整地描述了MDP所能达到的最佳表现形式。

（6）最优策略 Optimal Policy

对于任何状态s而言，在遵循策略\pi所带来的价值不低于策略\pi'所带来的价值的情况下，则称策略\pi优于策略\pi'：
当策略\pi在所有状态下至少不低于策略\pi'的价值时，则有\forall s, v_\pi(s) \ge v_{\pi'}(s)；
此定义适用于所有的马尔可夫决策过程（MDPs）：
在马尔可夫决策过程中（MDPs），价值函数被定义为评估给定状态下的预期回报。

①、存在一个最优策略，好于或等于所有其他策略；

任何一种最优策略均达成了相应的最优价值函数，并非仅限于单一的价值评估维度

怎么寻找最优策略呢？

基于最大化动作价值函数q_*(s,a)的选择来确定最优策略；对于所有MDP问题都必然存在确定性的最佳策略；KaTeX parse error: Unknown column alignment: * at position 57: … \begin{array}{*̲{20}{c}} 1&{if …

如果知道了最优动作价值函数q_*(s,a)，则表明找到了最优策略。

（7）贝尔曼最优方程 Bellman Optimality Equation

对于状态v_*而言，在该状态下所能采取的所有可能动作中所获得的最大价值等于在该状态下执行某动作所能获得的动作价值的最大值：
{v_*}(s) = \mathop {\max }\limits_a {q_*}(s,a)
在状态s下实施动作a所能获得的最大价值是由立即奖励加上未来状态s'的最优状态价值按转移概率加权总和的结果：
{q_*}(s,a) = R_s^a + \gamma \sum\limits_{s' \in S} {P_{ss'}^a{v_*}(s')}
将上述两种情况结合起来，则有：
{v_*}(s) = \mathop {\max }\limits_a (R_s^a + \gamma \sum\limits_{s' \in S} {P_{ss'}^a{v_*}(s')})

{q_*}(s,a) = R_s^a + \gamma \sum\limits_{s' \in S} {P_{ss'}^a\mathop {\max }\limits_{a'} {q_*}(s',a')}

贝尔曼最优方程属于非线性系统，在实际应用中通常采用迭代算法来求解贝尔曼最优方程。其中包含基于动态规划的方法（如价值迭代和策略迭代），蒙特卡洛方法以及时序差分学习等技术。这些技术在强化学习相关讨论中有所涉及，并将在后续章节中进一步详细讲解

声明

本博客所有内容仅供学习，不为商用，如有侵权，请联系博主，谢谢。

参考资料

动态规划之初识动规：掌握了一个系统的解题步骤模板后,再也不会对动态规划感到棘手的问题

[2] 动态规划理解

[3] 路径迷宫问题

[4] 动态规划之背包问题系列

第5章 《David Silver的强化学习课程》（http://www0.cs.ucl.ac.uk/staff/D.Silver/web/Teaching.html）

[6] David Silver强化学习公开课中文讲解

[7] 机器学习原理、算法与应用

[8] 人工智能：一种现代的方法（第3版）

[9] An Introduction to Reinforcement Learning

[10] Algorithms for Reinforcement Learning