[归纳]强化学习导论 - 第三章：有限马尔可夫过程_强化学习第三章 有限

1.本章内容概要

本章主要介绍有限马尔可夫决策过程(finite Markov Decision Processes，finite MDPs)的形式化描述(formal problem)，而RL就是针对这类问题建立的。这类问题具有评估性反馈(evaluative feedback, 主要指奖励reward)及联合性(associative aspect, 主要指在不同的状态s下建立不同的动作分布$\pi (a|s)$)的特征。MDPs是序列决策问题的经典模型，动作action不仅仅影响即时奖励，还影响未来一系列的状态及奖励。因此MDPs包含延迟的奖励，并需要对即时奖励与延迟奖励进行权衡。在MDPs中，我们估计最优策略下的动作值函数$q_{\ast }(s,a)$，或者估计最优策略下的状态值函数$v_{\ast }(s)$，而上一章我们估计的是$q_{\ast }(a)$。

MDPs是可以进行精确理论分析的RL问题的理想数学形式，其核心元素包括：returns，value functions，及Bellman方程。很多问题都可以用MDPs描述，但是在人工智能(AI)中，模型的广泛性与易处理性是有矛盾的，本章会介绍一些权衡这种矛盾方法，并介绍目前仍面临的挑战。RL不一定要基于MDPs，这在第17章中会加以介绍。

2.智能体-环境接口

在RL中，学习与决策组件合在一起叫做智能体(agent)，agent以外的全部合在一起叫做环境(environment)。agent观察环境状态，选择动作，环境响应这些动作并改变自身状态，agent再观察新的环境状态以选择新的动作…环境在改变状态的同时，也会反馈给agent一个即时的标量值——reward，而agent的目标就是最大化累计的回报(加权和)。

agent与环境按步(step)交互(t=0, 1,…)，在每个step t，agent得到环境的状态$S_t\in S$，并做出动作$A_t\in A(s)$，在step t+1，agent得到对其动作的评价$R_{t+1}\in R$，并得到新的环境状态$S_{t+1}$，这个过程构成了一个序列，称为一条轨迹(trajectory)：

$S_0,A_0,R_1,S_1,A_1,R_2,...$

finite MDP指的是状态空间、动作空间、奖励空间$(S,A,R)$的元素数都是有限的，而$R_t$和$S_t$完全由上一个step的状态和动作决定(Markov property，这要求状态必须包含能预测下一步的全部信息)[在本书后面的拟合值函数RL部分，会介绍不依赖Markov property的方法]，因此可以用$s^{\prime }\in S,r\in R$的联合条件概率函数描述环境，这就是MDP’s dynamics(四参数)：
p ( s ′ , r ∣ s , a ) = P r { S t = s ′ , R t = r ∣ S t − 1 = s , A t − 1 = a } p(s', r|s, a)=Pr\{S_t=s', R_t=r | S_{t-1}=s, A_{t-1}=a\} p(s′,r∣s,a)=Pr{St​=s′,Rt​=r∣St−1​=s,At−1​=a}

$\sum _{s^{\prime }\in S}\sum _{r\in R}p(s^{\prime },r|s,a)=1$

对MDP’s dynamics进行适当变形，可以得到：
state-transition probabilities(三参数):
$p(s^{\prime }|s,a)=\sum _{r\in R}p(s^{\prime },r|s,a)$

expected rewards for state–action pairs:
$r(s,a)=\sum _{r\in R}r\sum _{s^{\prime }\in S}p(s^{\prime },r|s,a)$

expected rewards for state–action–next-state(考虑Bayes公式):
$r(s,a,s^{\prime })=\sum _{r\in R}r\frac{p(s^{\prime },r|s,a)}{p(s^{\prime }|s,a)}$

MDP框架是很灵活的，这主要体现在：1. step不一定要在时间上等间隔，例如在控制问题中，控制的频率可以根据state确定，因此step可以是state的函数；2. 动作可以是底层的，例如电机电压，也可以是高层而抽象的，例如前进/后退；3.同样状态可以是底层的，如传感器读数，也可以是高层而抽象的，如天气好/大雨等。

agent与环境之间的边界，通常不像机器人和环境的物理界限那样。RL中agent与环境的边界更靠近agent，例如我们往往把机器人自身的一些部分(电机的动态模型等)也当作环境。只有能被agent随意改变而不受约束的量，才认为是agent的一部分，而reward的计算虽然是我们设计的，但是我们也认为它属于环境。agent只需要得到具体的奖励值就行了。

有时候，即便我们知道环境的全部信息，问题的解决还是很困难，例如围棋等问题。

在一个复杂的机器人中, 可能有许多不同的agent同时进行操作, 而每一个都有其自身的边界。这可以是分层的，一些agent做出高层次决策，而决策的结果可以作为下一层agent中状态的一部分。实践中, 一旦特定的状态、动作与奖赏被选定, agent与环境间的界限就确定下来了。

MDP 框架是对以目标为导向的、从交互中学习的问题的高度抽象，我们可以将其简化为在agent和环境间流动的三个信号，即actions, states和rewards。这种简化已被实践证明是可行的。

RL中actions和states的表示方式之设计是一种艺术(In reinforcement learning, as in other kinds of learning, such representational choices are at present more art than science.)，这种表示的好坏与RL算法的效果密切相关，本书不把这作为重点，但是会给出一些建议与示例。

example 3.3 Recycling Robot(垃圾回收机器人)

垃圾回收机器人收集办公室里散落的汽水罐，如果没电了可以自动去充电，而我们的目标是让它收集尽可能多的罐子。我们把这个问题简化一下：假设机器人只有两个描述电量的状态 S = { h i g h , l o w } S=\{high, low\} S={high,low}，各个状态下对应的动作空间为 A ( h i g h ) = { s e a r c h , w a i t } , A ( l o w ) = { s e a r c h , w a i t , r e c h a r g e } A(high)=\{search, wait\}, A(low) = \{search, wait, recharge\} A(high)={search,wait},A(low)={search,wait,recharge}。当状态处于high时，如果search，则有$\alpha$的概率维持high状态(否则转移到low)；如果wait，则维持high的概率为1。当状态处于low时，如果search，则有$\beta$的概率维持low的状态(否则没电强制充电，返回到high)；如果wait，则维持low的概率为1，如果recharge，则以概率1转移到high。search的reward为$r_{search}>0$，wait的reward为$0<r_{wait}<r_{search}$，recharge的reward为0，强制充电的reward为-3，那么可以画出状态转移表和状态转移图。

这里面值得注意的是，在状态转移图中，实心圆表示state-action pair，空心圆表示state。

3.目标和回报

在RL中，agent的目标用从环境提供的reward信号表述，在每个step，reward是一个反应我们目的的标量，而agent需要寻找一个策略最大化累计reward(后续reward折算到当前step上来)。使用reward信号形式化目标的概念，是RL的显著特征之一。

虽然使用奖赏信号来形式化目标可能初看上去颇具有局限性, 但在实践中其已被证明灵活且广泛可用,很多问题都可以建立reward形式的目标描述，例如棋类胜利时回报+1，输时回报-1，和棋或者中间局面回报0；机器人学习走路，以每个step间隔前进的距离作为目标等等。

因此, 我们设定的奖赏能否真实反映我们我们希望达成的目标就显得至关重要了。我们设计reward的时候，尽可能只描述我们最终的目的，不要把“我们认为的子目标”放到reward中，例如棋类游戏我们的目的是赢棋，因此除了结束时的设计以外，所有中间过程都设计reward为0。即使有这种子目标，我们也希望是智能体自己学习出来的，就如一些分层强化学习中研究的内容[2]。要记住：The reward signal is your way of communicating to the robot what you want it to achieve, not how you want it achieved。

4.returns和episodes

如何正式地定义累积回报呢？

假设在 t 时刻之后得到一个回报序列为 $R_{t+1},R_{t+2},R_{t+3},\dots$。我们用 $G_t$ 表示累积回报(单个episode的)。那么最简单的表达形式就是(return)：

$G_t\doteq R_{t+1}+R_{t+2}+R_{t+3}+\cdots +R_T$

其中T是终止的step，如果能最大化$G_t$的期望，我们就得到了最优的策略。根据是否存在自然的序列终止step，我们可以把RL任务分为两类：episodic tasks和continuing tasks。

episodic tasks：
agent与环境的交互可以自然地分割成多个episodes，例如棋类游戏，确定输赢的时候就是一个终止step。每个episode都结束于一个特殊的状态：terminal state，此后便开始新的一个episode(新的episode可能是从固定的starting state开始的，也可能从某个starting states分布中采样的)。无论episode的结局如何，我们认为terminal state都是一样的，但是可能得到不同的终止reward。用S表示所有非终止状态，$S^{+}$表示$S+terminalstate$，终止step T是一个随机变量。

continuing tasks：
有些任务没有自然的终止step，例如连续控制问题(机器人行走、飞机轨迹跟踪问题等)。这时 $T=\infty$，因此上面定义的$G_t$很可能是无限的，因此我们需要对$G_t$的定义进行一些修改：

$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}$

其中$0\le \gamma \le 1$为折扣因子(discounting)，如果$\gamma <1$且回报序列 { R k } \{ R_k \} {Rk​}是有界的，那么折扣$G_t$也是有界的，特别地，如果每个step的reward都是常数R，则由Taylor展开公式有${\sum }_{k=0}^{\infty }{\gamma }^{k}R=\frac{1}{1-\gamma }R$。无论是episodic tasks还是continuing tasks，我们都使用这个统一的累积回报定义。如果$\gamma$趋近于0，则agent会变得短视，更重视即时的回报；如果$\gamma$趋近于1，则agent变得目光长远，更重视累积回报，然而更大的$\gamma$意味着$G_t$收敛性变差。

定义$G_T=0$，则可以写出$G_t$的迭代计算(增量计算)关系：

G t = R t + 1 + γ R t + 2 + γ 2 R t + 3 + γ 3 R t + 4 + ⋯ = R t + 1 + γ ( R t + 2 + γ R t + 3 + γ 2 R t + 4 + ⋯ &ThinSpace; ) = R t + 1 + γ G t + 1

$$\begin{aligned} G_t &amp;= R_{t+1} +\gamma R_{t+2} + \gamma^2R_{t+3} + \gamma^3R_{t+4} + \cdots \\ &amp;= R_{t+1} +\gamma (R_{t+2} + \gamma R_{t+3} + \gamma^2 R_{t+4} + \cdots) \\ &amp;= R_{t+1} + \gamma G_{t+1}\end{aligned}$$ Gt​​=Rt+1​+γRt+2​+γ2Rt+3​+γ3Rt+4​+⋯=Rt+1​+γ(Rt+2​+γRt+3​+γ2Rt+4​+⋯)=Rt+1​+γGt+1​​

example 3.4 Pole-Balancing(二维倒立摆)
这既可以看作episodic任务，也可以看作continuing任务，而对应的return是有一定区别的；这个问题也必须折扣，或者设计正常状态reward=0，倒下reward=-1。CartPole问题在OpenAI的gym库有模型，可以用来帮助我们理解。

5.episodic和continuing任务的统一表示

这里建立episodic tasks和continuing tasks的统一表述。

对于episodic任务，状态、动作、回报、策略、终止step等都是跟episode有关的，因此我们应该同时标记出episode序号i和在该episode中的step t，即：$A_{t,i}$等。然而一般我们只分析单个episode中的元素，因此往往省略掉episode编号i，即：$A_t$等。

我们可以把episodic tasks统一为continuing tasks的形式，只需把terminal state考虑为absorbing state，即仅转移到自身且获得的所有奖赏均为 0 的状态。

因此得到两类任务统一的return:

$G_t\doteq {\sum }_{k=t+1}^T{\gamma }^{k-t-1}{R}_k$

其中$T$为正整数(也可是$\infty$)，$\gamma \in [0,1]$，注意$T=\infty$和$\gamma =1$不能同时出现。

6.策略和值函数

几乎所有RL方法或多或少涉及到值函数的概念(策略搜索方法除外)。状态值函数(state value function)或者动作值函数(action value function)是用来估计一个智能体在某个状态有多好或者在某个状态选择某个行为有多好的程度。“多好”定义为期望折扣累积回报(expected return)，当然未来的期望回报依赖于如何选择行为。因此值函数是基于某个特定行为方式来说的，我们把它叫做策略[2]。

策略：
把状态映射到一个动作的概率分布。如果在step t时使用策略$\pi$，则用$\pi (a|s)，s\in S,a\in A(s)$表示在状态$s=S_t$时选择动作a的条件概率。

状态值函数：
衡量在策略$\pi$下状态的好坏，定义为从 s 开始根据$\pi$选择动作而得到的期望折扣累积回报。如果s为terminal state，则它的状态值函数为0。

$v_{\pi }(s)\doteq {\mathbb{E}}_{\pi }[G_t|S_t=s]={\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}$

动作值函数：
衡量在策略$\pi$下状态-动作对的好坏，也就是在状态s下，选择动作a，后续按照$\pi$动作，所能够得到的期望折扣累积回报。

$q_{\pi }(s,a)\doteq {\mathbb{E}}_{\pi }[G_t|S_t=s,A_t=a]={\mathbb{E}}_{\pi }\left[{\sum }_{k=0}^{\infty }{\gamma }^k{R}_{t+k+1}|S_t=s,A_t=a\right],\text{for all}s\in \mathcal{S},a\in \mathcal{A}$

它和状态值函数的关系：
$v_{\pi }(s)={\mathbb{E}}_{\pi }[q_{\pi }(s,a)]=\sum _a\pi (a|s)q_{\pi }(s,a)$

$q_{\pi }(s,a)={\mathbb{E}}_{\pi }[R_{t+1}+\gamma v_{\pi }(s^{\prime })|S_t=s,A_t=a]=\sum _{s^{\prime },r}p(s^{\prime },r|s,a)\left[r+\gamma v_{\pi }(s^{\prime })\right]$

那么，如何估计值函数呢？
值函数的估计是RL的核心，本书介绍的各种方法(几乎)都是围绕这个问题展开的。估计值函数主要有两个思路：蒙特卡洛法(Monte Carlo method, MC)和时间差分法(Temporal Difference method, TD)。而值函数可以用表格记录(tabular method, 离散问题)，也可以用函数拟合(function approximation method, 问题规模太大或者连续问题)。MC方法就是通过大量仿真，根据仿真中出现的数据，利用上面的定义式直接计算出每次出现时的$G_t$，并用$G_t$的均值表示值函数；TD方法则是基于bootstrapping的，我们在后面章节详细介绍。

值函数的迭代关系

值函数一个重要特点就是他们满足迭代的关系，这是强化学习重要思想bootstrapping的基础。我们首先分析状态值函数，对于任何的策略 $\pi$ 和状态 s，s 的值函数和下一个状态 s’ 满足：

v π ( s ) ≐ E π [ G t ∣ S t = s ] = E π [ R t + 1 + γ G t + 1 ∣ S t = s ] = ∑ a π ( a ∣ s ) ∑ s ′ ∑ r p ( s ′ , r ∣ s , a ) [ r + γ E π [ G t + 1 ∣ S t + 1 = s ′ ] ] = ∑ a π ( a ∣ s ) ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r + γ v π ( s ′ ) ] = ∑ a , s ′ , r π ( a ∣ s ) p ( s ′ , r ∣ s , a ) [ r + γ v π ( s ′ ) ]

$$\begin{aligned} v_\pi(s) &amp; \doteq \mathbb{E}_\pi[G_t | S_t =s] \\&amp;= \mathbb{E}_\pi[R_{t+1} + \gamma G_{t+1} | S_t =s] \\ &amp;= \sum_a \pi(a|s) \sum_{s&#x27;} \sum_r p(s&#x27;,r | s,a) \left[ r + \gamma \mathbb{E}_\pi [G_{t+1} |S_{t+1} = s&#x27;] \right] \\ &amp;= \sum_a \pi(a|s) \sum_{s&#x27;, r} p(s&#x27;,r | s,a) \left[ r + \gamma v_\pi (s&#x27;) \right]\\ &amp;=\sum_{a, s&#x27;, r} \pi(a|s)p(s&#x27;,r | s,a) \left[ r + \gamma v_\pi (s&#x27;) \right]\end{aligned}$$ vπ​(s)​≐Eπ​[Gt​∣St​=s]=Eπ​[Rt+1​+γGt+1​∣St​=s]=a∑​π(a∣s)s′∑​r∑​p(s′,r∣s,a)[r+γEπ​[Gt+1​∣St+1​=s′]]=a∑​π(a∣s)s′,r∑​p(s′,r∣s,a)[r+γvπ​(s′)]=a,s′,r∑​π(a∣s)p(s′,r∣s,a)[r+γvπ​(s′)]​

这个式子即值函数的贝尔曼方程(Bellman equation)，阐述了某一状态值与其各个后续状态值间的关系。这个式子是一致性条件，也就是只有任何状态s的值函数都准确时，才满足Bellman方程。Bellman方程所表达的关系可以用如下backup diagram示意：

图中，每一个空心圆代表了一个状态，而每一个实心圆代表了一个动作-状态对(state-action pair)。s 是根节点，代表当前要求的值函数，从这个根节点构成一个树，每一个分支都代表了一种可能性。我们把这样的一个图叫backup diagram，因为其绘制出的关系是update/backup操作的基础，这些操作将值的信息从某一状态的后一状态 (或动作-状态对), 逆向传输到该状态 (或状态-动作对)（不像转移图, backup diagram中的状态结点并不一定表示不同的状态）。

动作值函数的Bellman方程为：
q π ( s , a ) = E π [ G t ∣ S t = s , A t = a ] = ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r + γ v π ( s ′ ) ] = ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r + γ ∑ a ′ π ( a ∣ s ′ ) q π ( s ′ , a ′ ) ]

$$\begin{aligned}q_\pi(s, a)&amp;=\mathbb{E}_\pi[G_t | S_t =s, A_t=a] \\&amp;= \sum\limits_{s&#x27;,r}p(s&#x27;, r|s, a)\left[ r + \gamma v_\pi(s&#x27;) \right]\\&amp;= \sum\limits_{s&#x27;,r}p(s&#x27;, r|s, a)\left[ r + \gamma \sum\limits_{a&#x27;}\pi(a|s&#x27;)q_\pi(s&#x27;, a&#x27;) \right]\end{aligned}$$ qπ​(s,a)​=Eπ​[Gt​∣St​=s,At​=a]=s′,r∑​p(s′,r∣s,a)[r+γvπ​(s′)]=s′,r∑​p(s′,r∣s,a)[r+γa′∑​π(a∣s′)qπ​(s′,a′)]​
其backup diagram为：

example 3.5 Gridworld(网格世界，实际上前八章几乎所有问题都是网格的)
agent处于不同的格子构成了共5*5=25个状态，在任何状态下都可以等概率向上下左右四个方向移动一格；如果移出边界，则reward=-1且agent回到移动前的位置；从A做任何动作，reward=+10且移动到A’，B与B’也是类似的；其余情况reward=0。设置$\gamma =0.9$，求解状态值的Bellman方程可以得到right图中的值，我们应该关注V(A)、V(B)、最下层的状态值这些特殊情况，我们还需注意到，reward是什么数字并不重要，它们的差值是最重要的，如果所有reward都加上常量C，则所有的状态值也都加上一个常数。

7.最优策略和最优值函数

对于finite MDP，好的策略能获得更多的期望累积折扣回报。最优策略在任何状态下都具有最高的值函数(最优性的定义，可以认为是有向无环图的分层搜索(动态规划))，我们用${\pi }^{\ast }$表示最优策略，$v_{\ast }(s),q_{\ast }(s,a)$表示最优值函数，则有：

$v_{\ast }(s)\doteq \underset{\pi }{\max }{v}_{\pi }(s)\text{for all}s\in \mathcal{S}$
$q_{\ast }(s,a)\doteq \underset{\pi }{\max }{q}_{\pi }(s,a)=\mathbb{E}\left[R_{t+1}+\gamma v_{\ast }(S_{t+1})|S_t=s,A_t=a\right]$

对于finite MDP，最优值函数是唯一的，但是最优策略可能有多个，它们具有相同的最优值函数。

example 3.6 Golf(高尔夫)
每一杆的reward=-1，直到进洞为止，那么状态的值为从当前位置到进洞所需的杆数的相反数。有两种击球方法：putter和driver，putter打得近，但是准确(只要在green上就能进球)，driver打得远，但是不准(只有在green上的小圆圈里才能进球)。图中上半部分是只用putter时的状态值分布，越远需要的杆数越多，状态值越小；图中下半部分则指定最初一定要用一次driver，然后后面就不加限定任意选择击球方式，这就是动作值函数，图中给出了最优策略时，动作值函数随状态s变化的分布情况。

既然最优值函数 $v_{\ast }$ 也是一个策略的值函数，那么它就必须满足贝尔曼方程的自治条件。但是因为是最优值函数，$v_{\ast }$具有特殊的形式，它不依赖于具体的策略。因此，可以得到贝尔曼最优方程(Bellman optimality equation)：

v ∗ ( s ) = max ⁡ a ∈ A ( s ) q π ∗ ( s , a ) = max ⁡ a E [ R t + 1 + γ v ∗ ( S t + 1 ) ∣ S t = s , A t = a ] = max ⁡ a ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r + γ v ∗ ( s ′ ) ]

$$\begin{aligned} v_*(s) &amp;= \max_{a \in \mathcal{A}(s)} q_{\pi_*} (s,a) \\ &amp;= \max_a \mathbb{E} [R_{t+1} + \gamma v_*(S_{t+1})| S_t =s, A_t =a] \\ &amp; = \max_a \sum_{s&#x27;,r}p(s&#x27;,r|s,a)[r+ \gamma v_*(s&#x27;)] \end{aligned}$$ v∗​(s)​=a∈A(s)max​qπ∗​​(s,a)=amax​E[Rt+1​+γv∗​(St+1​)∣St​=s,At​=a]=amax​s′,r∑​p(s′,r∣s,a)[r+γv∗​(s′)]​

对于 $q_{\ast }$ 的贝尔曼最优方程表示为：

q ∗ ( s , a ) = E [ R t + 1 + γ max ⁡ a ′ q ∗ ( S t + 1 , a ′ ) ∣ S t = s , A t = a ) ] = ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r + γ max ⁡ a ′ q ∗ ( s ′ , a ′ ) ]

$$\begin{aligned} q_*(s,a)&amp; = \mathbb{E} \left[ R_{t+1} + \gamma \max_{a&#x27;} q_*(S_{t+1}, a&#x27;) | S_t =s, A_t =a) \right] \\ &amp; = \sum_{s&#x27;, r} p(s&#x27;,r|s,a) \left[r + \gamma \max_{a&#x27;} q_*(s&#x27;, a&#x27;) \right] \end{aligned}$$ q∗​(s,a)​=E[Rt+1​+γa′max​q∗​(St+1​,a′)∣St​=s,At​=a)]=s′,r∑​p(s′,r∣s,a)[r+γa′max​q∗​(s′,a′)]​

最优贝尔曼方程和贝尔曼方程的最大区别就是分别多了最大化的操作，而最优Bellman方程暗含最优策略是确定性策略。

用弧线+max符号表示最大化操作，则上述两个最优方程的backup diagram为：

对于有限 MDP 而言，针对 v∗ 的贝尔曼最优性方程有不依赖于策略的唯一解(证明还需补充材料，需要深入研究)。贝尔曼最优性方程实际上是一个非线性方程组，每一个状态都对应于一个方程，因此如果有 n 个状态的话，那么就在 n 个方程中有 n 个未知数。如果环境的动态 p 是已知的，那么原则上说我们就可以利用非线性方程组的求解方法求得 v∗。同样，也可以解类似的方程组来求出 q∗。

得到v∗或者q∗，我们就能给出最优策略了，即：
(一步贪婪搜索)$\pi (a|s)=\underset{a}{\max }{\sum }_{s^{\prime },r}p(s^{\prime },r|s,a)[r+\gamma v_{\ast }(s^{\prime })]$
或者
$\pi (a|s)=\underset{a}{\max }{q}_{\ast }(s,a)$
以构建动作-状态对上而非状态上的函数为代价，最优动作值函数使得我们可以选择最优动作而不必了解任何和可能的后一状态与后一状态的值有关的信息，即不必了解关于环境的动态的任何信息，但是这导致存储量增加了，$|A|\ast |S|>>|S|$。

对于example 3.5 Girdworld问题，可以直接利用Bellman最优方程求出最优策略：

对于example 3.3 Recycling Robot问题，同样可以直接求得最优策略，也就是解以下方程：

通过上面方法显式地求解贝尔曼最优方程来找到最优策略，是一种思路。但是实际当中几乎很少这样做[2]。归结起来主要有三个难点，实际中这三点很难同时满足：

• 我们需要精确地知道环境的模型
• 我们需要足够的计算资源来完成求解
• 要满足马尔科夫性

很多决策方法都可以看成是近似求解贝尔曼最优方程的某种形式。比如启发式搜索、动态规划方法、强化学习方法等。

8.最优性和拟合器

我们已经定义了最优值函数与最优策略。很明显，学得了最优策略的智能体将表现得非常好，但在实际中这很少发生。在我们所关心的各种问题中，只有通过极大的计算开销才能获得最优策略。计算能力、内存都会限制求解，这迫使我们不得不采用近似的的办法，这有两个原则：在经常遇到的状态上投入更多的精力，使得能在这些状态上做出好的决策，在不常遇到的状态上投入更少精力为代价(RL与其它解决MDPs问题方法的区别)；对大规模问题，使用函数拟合器拟合值函数，代替查表的形式。

9.总结

• RL的核心元素：agent、环境、action、state、reward、value、return、policy。RL的目标是最大化累积奖励。
• MDPs表述：状态$S_{t+1}$可以由前一个状态$S_t$和动作$A_t$唯一确定，用概率$p(s^{\prime },r|s,a)$表述。有限 MDP 为拥有有限状态集、有限动作集以及 (于此处提出的) 有限奖赏集的 MDP。当前强化学习的多数理论都限定于有限 MDP，但是这些方法与理念可以应用于更一般的情形。
• episodic tasks及continuing tasks及它们的统一表述；
• 状态值函数、动作值函数、Bellman方程;
• 最优策略、Bellman最优方程；
• 虽然最优Bellman方程可以直接求解，但是在实际应用场景中，它有很多问题，我们常用近似的方法估计最优值函数。

本章有两个问题需要深入研究，Sutton书中的描述还不够深入：为什么最优策略如此定义？为什么finite MDP的最优值函数是唯一的？这两个问题需要更深入的分析。

参考文献

[1].(前三章翻译)https://blog.csdn.net/yuanyinshen/article/details/81904842
[2].(知乎专栏)https://zhuanlan.zhihu.com/c_1060499676423471104
[3].(迭代的收敛性证明：压缩定理)https://zhuanlan.zhihu.com/p/39279611
[4].(Sutton的课件)https://www.cs.utexas.edu/sites/default/files/legacy_files/research/documents/6 Bellman Eqs and DP.pdf