强化学习——学习笔记1（概念+MDP）_所有的目标都可以描述为某种期望累计的最大化

什么是强化学习

参考：
视频：
【中文字幕】David Silver深度强化算法学习 +项目讲解
周博磊：强化学习纲要
网上的资料：
David Silver强化学习公开课中文讲解及实践

研究智能体(Agent) 如何从与环境的交互中，通过获得成功与失败、奖励与惩罚的反馈信息来进行学习

有一个非常重要的前提条件，即智能体在与环境交互时，需要环境时时提供反馈信息——强化 (Reinforcement) 信息或奖励 (Reward) 信息，以便让智能体知道哪些行为能够获得正奖励，而哪些行为获得负奖励，并据此调整自己的行为策略。

这种学习方式，与动物依靠强化信息建立条件反射的原理非常类似——动物将疼痛与饥饿识别为负奖励，将快乐和食物识别为正奖励，并依此产生相应的行为。

强化学习领域中， “奖励” 是正奖励与负奖励的统称。

在另一些环境中，奖励出现的次数较少，并且还可能是延时出现的。

例如，在诸如围棋、国际象棋、 TicTacToe 等棋类游戏中，每次的奖励总是出现在棋局终局时。这个问题被称为延时信度分配问题，它是强化学习面临的一个重要问题

强化学习是机器学习的一个分支：监督学习、无监督学习、强化学习

强化学习的特点：

1. 没有监督数据、只有奖励信号
2. 奖励信号不一定是实时的，而很可能是延后的，有时甚至延后很多。
3. 时间（序列）是一个重要因素
4. 当前的行为影响后续接收到的数据

环境智能体交互模型

环境与智能体的一个基本交互序列是：智能体感知到环境的当前状态，然后进行决策以选择合适的动作去执行，环境为此作出响应：更新状态并产生一个奖励或回报（Reward）。

奖励是一个特定的数值信号，用来反映动作执行结果的受欢迎程度。

强化学习中一些基本概念

• 奖励 Reward

  $R_t$是信号的反馈，是一个标量，它反映个体在t时刻做得怎么样。个体的工作就是最大化累计奖励。

  强化学习主要基于这样的”奖励假设”：所有问题解决的目标都可以被描述成最大化累积奖励。

• 序列决策 Sequential Decision Making

  • 目标：选择一定的行为系列以最大化未来的总体奖励

  • 这些行为可能是一个长期的序列

  • 奖励可能而且通常是延迟的

  • 有时候宁愿牺牲即时（短期）的奖励以获取更多的长期奖励

• 个体和环境 Agent & Environment

  可以从个体和环境两方面来描述强化学习问题。

  在t时刻，个体可以：

  1. 有一个对于环境的观察评估 $O_t$ ，
  2. 做出一个行为 $A_t$，
  3. 从环境得到一个奖励信号$R_{t+1}$。

  环境可以：

  1. 接收个体的动作 $A_t$，
  2. 更新环境信息，同时使得个体可以得到下一个观测 $O_{t+1}$，
  3. 给个体一个奖励信号 $R_{t+1}$ 。

  

• 历史和状态 History & State

  • 历史

    历史是观测、行为、奖励的序列： $H_t=O_1,R_1,A_1,...,O_{t-1},R_{t-1},A_{t-1},O_t,R_t,A_t$

  • 状态

    状态是所有决定将来的已有的信息，是关于历史的一个函数：$S_t=f(H_t)$

  • 环境状态

    是环境的私有呈现，包括环境用来决定下一个观测/奖励的所有数据

    通常对个体并不完全可见，也就是个体有时候并不知道环境状态的所有细节。

    即使有时候环境状态对个体可以是完全可见的，这些信息也可能包含着一些无关信息。

  • 个体状态

    是个体的内部呈现，包括个体可以使用的、决定未来动作的所有信息。

    个体状态是强化学习算法可以利用的信息，它可以是历史的一个函数： $S_t^a=f(H_t)$

  • 信息状态

    包括历史上所有有用的信息，又称Markov状态。

• 马儿可夫属性 Markov Property

  一个状态$S_t$是马尔可夫的，当且仅当：$P[S_{t+1}|S_t]=P[S_{t+1}|S_1,...,S_t]$

  下一个状态至于当前状态有关，而与历史状态无关

• 完全可观测的环境 Fully Observable Environments

  个体能够直接观测到环境状态。在这种条件下:

  个体对环境的观测 = 个体状态 = 环境状态​

  正式地说，这种问题是一个马儿可夫决定过程（Markov Decision Process， MDP）

• 部分可观测的环境 Partially Observable Environments

  个体间接观测环境

  eg:一个扑克牌玩家只能看到自己的牌和其他已经出过的牌，而不知道整个环境（包括对手的牌）状态。

  在这种条件下：

  个体状态 ≠ 环境状态

  正式地说，这种问题是一个部分可观测马儿可夫决策过程。

  个体必须构建它自己的状态呈现形式，比如：记住完整的历史：$S_t^a=H_t$

  这种方法比较原始、幼稚。还有其他办法，例如 ：

  1. Beliefs of environment state：此时虽然个体不知道环境状态到底是什么样，但个体可以利用已有经验（数据），用各种个体已知状态的概率分布作为当前时刻的个体状态的呈现：

  

  2. Recurrent neural network：不需要知道概率，只根据当前的个体状态以及当前时刻个体的观测，送入循环神经网络(RNN)中得到一个当前个体状态的呈现：

  

强化学习个体的主要组成部分

强化学习中的个体可以由以下三个组成部分中的一个或多个组成：

• 策略 Policy

  策略是决定个体行为的机制。是从状态到行为的一个映射，可以是确定性的，也可以是不确定性的。

• 价值函数 Value Function

  是一个未来奖励的预测，用来评价当前状态的好坏程度。当面对两个不同的状态时，个体可以用一个Value值来评估这两个状态可能获得的最终奖励区别，继而指导选择不同的行为，即制定不同的策略。同时，一个价值函数是基于某一个特定策略的，不同的策略下同一状态的价值并不相同。某一策略下的价值函数用下式表示：

• 模型 Model

  个体对环境的一个建模，它体现了个体是如何思考环境运行机制的，个体希望模型能模拟环境与个体的交互机制。

  模型至少要解决两个问题：一是状态转化概率，即预测下一个可能状态发生的概率：

  

  另一项工作是预测可能获得的即时奖励：

  

  模型并不是构建一个个体所必需的，很多强化学习算法中个体并不试图（依赖）构建一个模型。

强化学习个体的分类

解决强化学习问题，个体可以有多种工具组合

• 通过建立对状态的价值的估计来解决问题

• 通过直接建立对策略的估计来解决问题。

这些都是个体可以使用的工具箱里的工具。因此，根据个体内包含的“工具”进行分类，可以把个体分为如下三类：

1. 仅基于价值函数的 Value Based：

   在这样的个体中，有对状态的价值估计函数，但是没有直接的策略函数，策略函数由价值函数间接得到。

2. 仅直接基于策略的 Policy Based：

   这样的个体中行为直接由策略函数产生，个体并不维护一个对各状态价值的估计函数。

3. 演员-评判家形式 Actor-Critic：

   个体既有价值函数、也有策略函数。两者相互结合解决问题。

此外，根据个体在解决强化学习问题时是否建立一个对环境动力学的模型，将其分为两大类：

1. 不基于模型的个体:

   这类个体并不视图了解环境如何工作，而仅聚焦于价值和/或策略函数。

2. 基于模型的个体：

   个体尝试建立一个描述环境运作过程的模型，以此来指导价值或策略函数的更新。

学习和规划 Learning & Planning

• 学习：环境初始时是未知的，个体不知道环境如何工作，个体通过与环境进行交互，逐渐改善其行为策略。
• 规划: 环境如何工作对于个体是已知或近似已知的，个体并不与环境发生实际的交互，而是利用其构建的模型进行计算，在此基础上改善其行为策略。

一个常用的强化学习问题解决思路是，先学习环境如何工作，也就是了解环境工作的方式，即学习得到一个模型，然后利用这个模型进行规划。

探索和利用 Exploration & Exploitation

强化学习类似于一个试错的学习，个体需要从其与环境的交互中发现一个好的策略，同时又不至于在试错的过程中丢失太多的奖励。探索和利用是个体进行决策时需要平衡的两个方面。

一个形象的比方是，当你去一个餐馆吃饭，

“探索”意味着你对尝试新餐厅感兴趣，很可能会去一家以前没有去过的新餐厅体验，

“利用”则意味着你就在以往吃过的餐厅中挑一家比较喜欢的，而不去尝试以前没去过的餐厅。

这两种做法通常是一对矛盾，但对解决强化学习问题又都非常重要。

预测和控制 Prediction & Control

在强化学习里，我们经常需要先解决关于预测（prediction）的问题，而后在此基础上解决关于控制（Control）的问题。

• 预测：给定一个策略，评价未来。可以看成是求解在给定策略下的价值函数（value function）的过程。
• 控制：找到一个好的策略来最大化未来的奖励。

eg:

预测：现在给出了从A到A’的奖励以及从B到B’的奖励，在“随机选择4个方向进行移动”的策略下，如何得知每一个位置的价值。

控制：同样的条件，在所有可能的策略下最优的价值函数是什么？最优策略是什么？

马尔科夫决策过程

马尔科夫决策过程（Markov decision process, MDP）是对完全可观测的环境进行描述的，也就是说观测到的状态内容完整地决定了决策的需要的特征。几乎所有的强化学习问题都可以转化为MDP

马尔科夫过程 Markov Process

马尔科夫性 Markov Property

某一状态信息包含了所有相关的历史，只要当前状态可知，所有的历史信息都不再需要，当前状态就可以决定未来，则认为该状态具有马尔科夫性。

可以用下面的状态转移概率公式来描述马尔科夫性：
$$P_{s{s}^{\prime }}=P[S_{t+1}=s^{\prime }|S_t=s]$$
下面状态转移矩阵定义了所有状态的转移概率：
P = ( p 11 … p 1 n ⋮ ⋱ ⋮ p 1 n … p n n ) P =

$$\begin{pmatrix} p_{11} & \dots & p_{1n} \\ \vdots & \ddots &\vdots \\ p_{1n} & \dots & p_{nn} \end{pmatrix}$$ P=⎝⎜⎛​p11​⋮p1n​​…⋱…​p1n​⋮pnn​​⎠⎟⎞​
式中n为状态数量，矩阵中每一行元素之和为1

马尔科夫过程 Markov Property

马尔科夫过程 又叫马尔科夫链(Markov Chain)，它是一个无记忆的随机过程

可以用一个元组<S,P>表示，其中S是有限数量的状态集，P是状态转移概率矩阵。

eg:

圆圈表示学生所处的状态，方格Sleep是一个终止状态箭头表示状态之间的转移，箭头上的数字表示当前转移的概率。

当学生处在第一节课（Class1）时

​ 他/她有50%的几率会参加第2节课（Class2）

​ 当学生进入到第二节课（Class2）时

​ 会有80%的几率继续参加第三节课（Class3）

​ 当学生处于第三节课这个状态时，

​ 他有60%的几率通过考试，继而100%的退出该课程，

​ 也有40%的可能性需要到去图书馆之类寻找参考文献，

​ 此后根据其对课堂内容的理解程度，又分别有20%、40%、40%的几率返回值第一、二、三节课重新 继续学习。

​ 也有20%的几率觉得课程较难而退出（Sleep）。

​ 同时在也有50%的几率不在认真听课，进入到浏览facebook这个状态中。

​ 在浏览facebook这个状态时，

​ 他/她有90%的几率在下一时刻继续浏览，

​ 也有10%的几率返回到课堂内容上来。

一个可能的学生马尔科夫链从状态Class1开始，最终结束于Sleep，其间的过程根据状态转化图可以有很多种可能性，这些都称为Sample Episodes。

以下四个Episodes都是可能的：

• C1 - C2 - C3 - Pass - Sleep

• C1 - FB - FB - C1 - C2 - Sleep

• C1 - C2 - C3 - Pub - C2 - C3 - Pass - Sleep

• C1 - FB - FB - C1 - C2 - C3 - Pub - C1 - FB - FB - FB - C1 - C2 - C3 - Pub - C2 - Sleep

该学生马尔科夫过程的状态转移矩阵如下图：

马尔科夫奖励过程 Markov Reward Process

马尔科夫奖励过程在马尔科夫过程的基础上增加了奖励R和衰减系数γ：<S,P,R,γ>。

R是一个奖励函数。S状态下的奖励是某一时刻(t)处在状态s下在下一个时刻(t+1)能获得的奖励期望
$$R_s=E[R_{t+1}|S_t=s]$$
衰减系数 Discount Factor: γ∈ [0, 1]

下图是一个“马尔科夫奖励过程”图示的例子，在“马尔科夫过程”基础上增加了针对每一个状态的奖励，由于不涉及衰减系数相关的计算，这张图并没有特殊交代衰减系数值的大小。

收获 Return

定义：收获$G_t$为在一个马尔科夫奖励链上从t时刻开始往后所有的奖励的有衰减的总和。也有翻译成“收益”或"回报"。公式如下：

当 γ = 0 时，智能体是缺乏远见的，因为它只考虑使当前的奖励最大化；而当 γ 越接近 1 时，表明智能体是越有远见的，因为智能体越重视将来获得的奖励

即使 T = 1，只要 γ < 1 且$R_t$是有界的，那么$G_t$ 就是有限的。在某些情况下，如果不会导致$G_t$ 是无限的,允许 γ = 1。

价值函数 Value Function

价值函数给出了某一状态或某一行为的长期价值。

定义：一个马尔科夫奖励过程中某一状态的价值函数为从该状态开始的马尔可夫链收获的期望：$v(s)=E[G_t|S_t=s]$

注：价值可以仅描述状态，也可以描述某一状态下的某个行为，在一些特殊情况下还可以仅描述某个行为。在整个视频公开课中，除了特别指出，约定用状态价值函数或价值函数来描述针对状态的价值；用行为价值函数来描述某一状态下执行某一行为的价值，严格意义上说行为价值函数是“状态行为对”价值函数的简写。

举例说明收获和价值的计算

为方便计算，把“学生马尔科夫奖励过程”示例图表示成下表的形式。

表中第二行对应各状态的即时奖励值，其他区域数字为状态转移概率，表示为从所在行状态转移到所在列状态的概率：

考虑如下4个马尔科夫链。现计算当γ= 1/2时，在t=1时刻（$S_1=C_1$）时状态 $S_1$ 的收获分别为：

从上表也可以理解到，收获是针对一个马尔科夫链中的某一个状态来说的。

当γ= 0时，各状态的即时奖励就与该状态的价值相同。

当γ≠ 0时，各状态的价值需要通过计算得到，这里先给出γ分别为0, 0.9,和1三种情况下各状态的价值，如下图所示。

各状态圈内的数字表示该状态的价值，圈外的R=-2等表示的是该状态的即时奖励。

价值函数的推导

• Bellman方程

先尝试用价值的定义公式来推导看看能得到什么：

这个推导过程相对简单，仅在导出最后一行时，将$G_{t+1}$变成了 $v(S_{t+1})$

其理由是收获的期望等于收获的期望的期望。Bellman方程：

通过方程可以看出$v(s)$由两部分组成

一是该状态的即时奖励期望，即时奖励期望等于即时奖励，因为根据即时奖励的定义，它与下一个状态无关；

另一个是下一时刻状态的价值期望，可以根据下一时刻状态的概率分布得到其期望。

如果用s’表示s状态下一时刻任一可能的状态，那么Bellman方程可以写成：

• 方程的解释

下图已经给出了γ=1时各状态的价值，状态 $C_3$的价值可以通过状态Pub和Pass的价值以及他们之间的状态转移概率来计算：

4.3 = -2+1.0*(0.6*10+0.4*0.8)​

• Bellman方程的矩阵形式和求解

结合矩阵的具体表达形式还是比较好理解的：

Bellman方程是一个线性方程组，因此理论上解可以直接求解：

实际上，计算复杂度是 $O(n^3)$， 因此直接求解仅适用于小规模的。

大规模的求解通常使用迭代法。常用的迭代方法有：

• 动态规划Dynamic Programming
• 蒙特卡洛评估Monte-Carlo evaluation
• 时序差分学习Temporal-Difference

马尔科夫决定过程 Markov Decision Process

相较于马尔科夫奖励过程，马尔科夫决定过程多了一个行为集合A

它是这样的一个元组: <S, A, P, R, γ>。看起来很类似马尔科夫奖励过程，但这里的P和R都与具体的行为a对应，

而不像马尔科夫奖励过程那样仅对应于某个状态，A表示的是有限的行为的集合。具体的数学表达式如下：

• 示例——学生MDP

下图给出了一个可能的MDP的状态转化图。

图中红色的文字表示的是采取的行为，而不是先前的状态名。

策略Policy

策略$\pi$是概率的集合或分布，其元素$\pi (a|s)$为对过程中的某一状态s采取可能的行为a的概率。用$\pi (a|s)$表示。
$$\pi (a|s)=P[A_t=a|S_t=s]$$
一个策略完整定义了个体的行为方式，也就是说定义了个体在各个状态下的各种可能的行为方式以及其概率的大小。

Policy仅和当前的状态有关，与历史信息无关；同时某一确定的Policy是静态的，与时间无关；但是个体可以随着时间更新策略。

当给定一个MDP:$M=<S,A,P,R,\gamma >$和一个策略$\pi$

• 状态序列$S_1,S_2,S_3,...$是一个马尔科夫过程 $<S,P^{\pi }>$

• 状态和奖励序列 $S_1,R_2,S_2,R_3,S_3,...$是一个马尔科夫奖励过程$<S,P^{\pi },R^{\pi },\gamma >$

  并且在这个奖励过程中满足下面两个方程

  

  用文字描述是这样的，在执行策略$\pi$时，状态从s转移至 s’ 的概率等于一系列概率的和，

  这一系列概率指的是在执行当前策略时，执行某一个行为的概率与该行为能使状态从s转移至s’的概率的乘积。

  奖励函数表示如下：

  

  用文字表述是这样的：当前状态s下执行某一指定策略得到的即时奖励是该策略下所有可能行为得到的奖励与该行为发生的概率的乘积的和。

基于策略π的价值函数

定义$v_{\pi }(s)$是在MDP下的基于策略π的状态价值函数，

表示从状态s开始，遵循当前策略时所获得的收获的期望；或者说在执行当前策略π时，衡量个体处在状态s时的价值大小。数学表示如下：
$$v_{\pi }(s)=E_{\pi }[G_t|S_t=s]$$

注：策略就是用来描述各个不同状态下执行各个不同行为的概率。

定义 $q_{\pi }(s,a)$行为价值函数，表示在执行策略π时，对当前状态s执行某一具体行为a所能的到的收获的期望；

行为价值函数一般都是与某一特定的状态相对应的，更精细的描述是状态行为对价值函数。行为价值函数的公式描述如下：
$$q_{\pi }(s,a)=E_{\pi }[G_t|S_t=s,A_t=a]$$

Bellman期望方程 Bellman Expectation Equation

MDP下的状态价值函数和行为价值函数与MRP下的价值函数类似，可以改用下一时刻状态价值函数或行为价值函数来表达，具体方程如下：
$$v_{\pi }(s)=E_{\pi }[R_{t+1}+\gamma v_{\pi }(S_{t+1})|S_t=s]$$

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

• $v_{\pi }(s)$与$q_{\pi }(s,a)$的关系

  

  上图中，空心较大圆圈表示状态，黑色实心小圆表示的是动作本身，

  在遵循策略π时，状态s的价值体现为在该状态下遵循某一策略而采取所有可能行为的价值按行为发生概率的乘积求和。

  

  类似的，一个行为价值函数也可以表示成状态价值函数的形式：

  

  它表明，一个某一个状态下采取一个行为的价值，可以分为两部分：

  • 其一是离开这个状态的价值，
  • 其二是所有进入新的状态的价值于其转移概率乘积的和。

  

  如果组合起来，可以得到下面的结果：

也可以得到下面的结果：

下图解释了红色空心圆圈状态的状态价值是如何计算的，遵循的策略随机策略，即所有可能的行为有相同的几率被选择执行。

• Bellman期望方程矩阵形式

最优

• 最优价值函数

  最优状态价值函数 $V_{\ast }(x)$指的是在从所有策略产生的状态价值函数中，选取使状态s价值最大的函数：

$$V_{\ast }=\underset{\pi }{\max }{v}_{\pi }(s)$$

​ 类似的，最优行为价值函数$q_{\ast }(s,a)$ 指的是从所有策略产生的行为价值函数中，选取是状态行为对 $<s,a>$ 价值最大的函数：
$$q_{\ast }(s,a)=\underset{\pi }{\max }{q}_{\pi }(s,a)$$

• 最优策略

  当对于任何状态 s，遵循策略π的价值不小于遵循策略 π’ 下的价值，则策略π优于策略 π’：

  

  定理 对于任何MDP，下面几点成立：

  • 存在一个最优策略，比任何其他策略更好或至少相等；
  • 所有的最优策略有相同的最优价值函数；
  • 所有的最优策略具有相同的行为价值函数。

• 寻找最优策略

  可以通过最大化最优行为价值函数来找到最优策略：

  

Bellman最优方程 Bellman Optimality Equation

针对 $V_{\ast }$一个状态的最优价值等于从该状态出发采取的所有行为产生的行为价值中最大的那个行为价值：

针对 $q_{\ast }$ ，在某个状态s下，采取某个行为的最优价值由2部分组成，

• 一部分是离开状态 s 的即刻奖励，

• 另一部分则是所有能到达的状态 s’ 的最优状态价值按出现概率求和：

  

组合起来，针对$v_{\ast }$ ，有

针对$q_{\ast }$，有：

• 求解Bellman最优方程

Bellman最优方程是非线性的，没有固定的解决方案，通过一些迭代方法来解决：价值迭代、策略迭代、Q学习、Sarsa等。

动态规划寻找最优策略

简介 Introduction

动态规划算法是解决复杂问题的一个方法，算法通过把复杂问题分解为子问题，通过求解子问题进而得到整个问题的解。

在解决子问题的时候，其结果通常需要存储起来被用来解决后续复杂问题。

当问题具有下列特性时，通常可以考虑使用动态规划来求解：

• 一个复杂问题的最优解由数个小问题的最优解构成，可以通过寻找子问题的最优解来得到复杂问题的最优解；

• 子问题在复杂问题内重复出现，使得子问题的解可以被存储起来重复利用。

马尔科夫决定过程（MDP）具有上述两个属性：Bellman方程把问题递归为求解子问题，价值函数就相当于存储了一些子问题的解，可以复用。因此可以使用动态规划来求解MDP。

我们用动态规划算法来求解一类称为“规划”的问题。“规划”指的是在了解整个MDP的基础上求解最优策略，也就是清楚模型结构的基础上：包括状态行为空间、转换矩阵、奖励等。这类问题不是典型的强化学习问题，我们可以用规划来进行预测和控制。

具体的数学描述是这样：

**预测：**给定一个MDP $<S,A,P,R,\gamma >$和策略$\pi$ ，或者给定一个MRP$<S,P^{\pi },R^{\pi },\gamma >$ ，要求输出基于当前策略π的价值函数 $V_{\pi }$

**控制：**给定一个MDP $<S,A,P,R,\gamma >$，要求确定最优价值函数$V_{\ast }$和最优策略 ${\pi }_{\ast }$

迭代法策略评估Iterative Policy Evaluation

理论

问题：评估一个给定的策略π，也就是解决“预测”问题。

**解决方案：**反向迭代应用Bellman期望方程

具体方法：

同步反向迭代，即在每次迭代过程中，对于第 k+1次迭代，所有的状态s的价值用$v_k(s^{\prime })$ 计算并更新该状态第 k+1次迭代中使用的价值$v_k(s)$，其中s’是s的后继状态。

此种方法通过反复迭代最终将收敛至 $V_{\pi }$

也可以异步反向迭代，即在第k次迭代使用当次迭代的状态价值来更新状态价值。

公式为：

即：一次迭代内，状态s的价值等于前一次迭代该状态的即时奖励与所有s的下一个可能状态s’ 的价值与其概率乘积的和

公式的矩阵形式是：
$$v^{k+1}=R^{\pi }+\gamma p^{\pi }{v}^k$$

例子

方格世界

已知：

状态空间S：如图。S1 - S14非终止状态，ST终止状态，下图灰色方格所示两个位置；

行为空间A：{n, e, s, w} 对于任何非终止状态可以有东南西北移动四个行为；

**转移概率P：**任何试图离开方格世界的动作其位置将不会发生改变，其余条件下将100%地转移到动作指向的状态；

**即时奖励R：**任何在非终止状态间的转移得到的即时奖励均为-1，进入终止状态即时奖励为0；

衰减系数γ：1；

**当前策略π：**Agent采用随机行动策略，在任何一个非终止状态下有均等的几率采取任一移动方向这个行为，即π(n|•) = π(e|•) = π(s|•) = π(w|•) = 1/4。

**问题：**评估在这个方格世界里给定的策略。

该问题等同于：求解该方格世界在给定策略下的（状态）价值函数，也就是求解在给定策略下，该方格世界里每一个状态的价值。

迭代法求解（迭代法进行策略评估）

状态价值在第153次迭代后收敛

• 如何改善策略

通过方格世界的例子，我们得到了一个优化策略的办法，分为两步：

首先我们在一个给定的策略下迭代更新价值函数：

随后，在当前策略基础上，贪婪地选取行为，使得后继状态价值增加最多：

在刚才的格子世界中，基于给定策略的价值迭代最终收敛得到的策略就是最优策略，但通过一个回合的迭代计算价值联合策略改善就能找到最优策略不是普遍现象。通常，还需在改善的策略上继续评估，反复多次。不过这种方法总能收敛至最优策略${\pi }^{\ast }$。

策略迭代 Policy Iteration

在当前策略上迭代计算v值，再根据v值贪婪地更新策略，如此反复多次，最终得到最优策略 ${\pi }^{\ast }$ 和最优状态价值函数 $V^{\ast }$ 。

贪婪 指的是仅采取那个（些）使得状态价值得到最大的行为。

• 策略改善

1. 考虑一个确定的策略： $a=\pi (s)$

2. 通过贪婪计算优化策略：

   

3. 更新新的行为价值函数q的值

   

   经过一轮的迭代就会有新的策略，根据新的策略获得新的行为价值函数q

4. 不断迭代出最优的函数

   

有时候不需要持续迭代至最有价值函数，可以设置一些条件提前终止迭代，比如设定一个Ɛ，比较两次迭代的价值函数平方差；直接设置迭代次数；以及每迭代一次更新一次策略等。

值迭代

值迭代也是基于贝尔曼最优方程推导出来的，只不过值迭代把贝尔曼最优方程转换为 update rule 来进行不断的回溯迭代，整个迭代的过程没有 policy 的参与

1. 迭代找最优值函数：先不断迭代贝尔曼最优方程（就是最大化Q函数）得到最优的 v*

2. 最佳策略提取过程：用argmax把Q函数重构出来，然后找到那个最大值的action就是他要选择的策略

Policy Iteration和Value Iteration对比

这两种方法都是为了解决MDP控制问题。

Policy Iteration由policy evaluation和policy improvement两部分组成。两步交替迭代进行，比较直观。

Value Iteration则是直接利用贝尔曼最优等式迭代求解，最后再有一个policy extraction，由动作值获得最终策略。

如果是Prediction问题，可直接用贝尔曼期望等式迭代求解。

如果是Control问题，可用贝尔曼期望等式+策略迭代更新的方法或直接使用贝尔曼最优等式进行值迭代。