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

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

【上一篇 2 从Multi-arm Bandits问题分析 - RL进阶】
【下一篇 4 动态编程（Dynamic Programming, DP）】

本次总结中的 1-4 小节主要介绍了增强学习中的一些重要的概念，如：Goals、Rewards、Returns、Episode 等，第 5 小节介绍了 Markov Property，第 6 小节介绍了 Markov Decision Processes，第 7、8 小节介绍了 RL 中的 Value Function。可以说这次总结也是为之后介绍 RL 相关算法做了铺垫。

1 增强学习中的一般模型

在强化学习（Reinforcement Learning, RL）初步介绍中曾经介绍了 RL 问题的一般模型，下面再简单回顾一下：

在 RL 中，agents 是具有明确的目标的，所有的 agents 都能感知自己的环境，并根据目标来指导自己的行为，因此 RL 的另一个特点是它将 agents 和与其交互的不确定的环境视为是一个完整的问题。在 RL 问题中，有四个非常重要的概念：

（1）规则（policy）

Policy 定义了 agents 在特定的时间特定的环境下的行为方式，可以视为是从环境状态到行为的映射，常用 π \pi π 来表示。policy 可以分为两类：

• 确定性的 policy（Deterministic policy）: a = π ( s ) a=\pi(s) a=π(s)
• 随机性的 policy（Stochastic policy）: π ( a ∣ s ) = P [ A t = a ∣ S t = t ] \pi(a|s)=P[A_t=a|S_t=t] π(a∣s)=P[At​=a∣St​=t]

其中， t t t 是时间点， t = 0 , 1 , 2 , 3 , … … t=0,1,2,3,…… t=0,1,2,3,……
　　　 S t ∈ S S_t\in{\mathcal{S}} St​∈S， S {\mathcal{S}} S是环境状态的集合， S t S_t St​代表时刻 t t t 的状态， s s s 代表其中某个特定的状态；
　　　 A t ∈ A ( S t ) A_t\in{\mathcal{A}}(S_t) At​∈A(St​)， A ( S t ) {\mathcal{A}}(S_t) A(St​) 是在状态 S t S_t St​ 下的 actions 的集合， A t A_t At​ 代表时刻 t t t 的行为， a a a 代表其中某个特定的行为。

（2）奖励信号（a reward signal）

Reward 就是一个标量值，是每个 time step 中环境根据 agent 的行为返回给 agent 的信号，reward 定义了在该情景下执行该行为的好坏，agent 可以根据 reward 来调整自己的 policy。常用 R R R 来表示。

（3）值函数（value function）

Reward 定义的是立即的收益，而 value function 定义的是长期的收益，它可以看作是累计的 reward，常用 v v v 来表示。

（4）环境模型（a model of the environment）

整个Agent和Environment交互的过程可以用下图来表示：

其中， t t t 是时间点， t = 0 , 1 , 2 , 3 , … … t=0,1,2,3,…… t=0,1,2,3,……
　　　 S t ∈ S S_t\in{\mathcal{S}} St​∈S， S {\mathcal{S}} S 是环境状态的集合；
　　　 A t ∈ A ( S t ) A_t\in{\mathcal{A}}(S_t) At​∈A(St​)， A ( S t ) {\mathcal{A}}(S_t) A(St​) 是在状态 S t S_t St​ 下的 actions 的集合；
　　　 R t ∈ R ∈ R R_t\in{\mathcal{R}}\in{\Bbb R} Rt​∈R∈R 是数值型的 reward。

在每个时间步骤中，agent 都会实现一个从 states 到每个可能的 actions 的 probabilities 的映射，这个映射函数就称作是这个 agent 的 p o l i c y policy policy，常用符号 π t \pi_t πt​ 来表示， π t ( a ∣ s ) \pi_t(a|s) πt​(a∣s) 指的就是在状态 S t = s S_t=s St​=s 下选择执行 A t = a A_t=a At​=a 的概率。

其实概括的来说，不同的 RL 方法的主要不同就是利用 experience 来改变自己的 π t \pi_t πt​ 的方法，毕竟RL 就是从 experience 中进行学习的一系列方法。

2 Goals 和 Rewards

在 RL 中，goals 和 rewards 是两个重要的概念，在每个时间步骤中，环境返回给 Agent 的 reward 就是一个简单的数值，而 Agent 的 goal 就是最大化它接受到的所有的 reward signal 的和，也就是说，它的目的不是最大化当前步骤的立即获得的 reward ，而是一个长远的目标，并且需要注意的是，这个 reward 是由 environment 定义的而非 Agent。

3 Returns

刚刚提到，Agent 的 goal 就是最大化它接受到的所有的 reward signal 的和，那么就需要将这个目标值用函数的形式来表达出来，这里令时间 t t t 获得的 reward 为 R t + 1 , R t + 2 , R t + 3 , … R_{t+1}, R_{t+2}, R_{t+3}, \ldots Rt+1​,Rt+2​,Rt+3​,… ，令 G t G_t Gt​ 代表期望的 return，那么最简单的 return 的形式为：
G t ≐ R t + 1 + R t + 2 + R t + 3 + … + R T (1) G_t \doteq R_{t+1}+R_{t+2}+R_{t+3}+\ldots +R_T \tag{1} Gt​≐Rt+1​+Rt+2​+Rt+3​+…+RT​(1)

其中， T T T 代表最后一个的时间步骤。

这时就需要再引入一个新的概念 episodes，翻译成中文的话就是“片段、插曲”的意思，这里指的是一个可以自然结束的 agent-environment 交互的过程，每个 episode 都会在一个特殊的状态下结束，这个状态就称作是 terminal state，因此每个 episode 的相同点是它们都以 terminal state 来结束，不同就是每个 episode 获得的 reward 不同，采用 episodes 形式的 tasks 就称为是 episodic tasks，在episodic tasks 中，常常将所有非终止的状态的集合记为是 S {\mathcal{S}} S，而把包含终止状态的所有状态的集合记为是 S + {\mathcal{S}}^+ S+。

与 episode task 相对应的另外一种是 continuing tasks，它们指的是那些不会自然结束，会一直持续进行的 task，这时 return 公式（1）中的 T = ∞ T=\infty T=∞。

还有一个比较重要的概念是 Discounting，它是对未来不同时刻的 reward 赋予不同的权重，距离现在较近的 reward 的权重较高，而时间越远的权重越低，这时选择行为 A t A_t At​ 的准则就是最大化期望的 Discounted Return：
G t ≐ R t + 1 + γ R t + 2 + γ 2 R t + 3 + … = ∑ k = 0 ∞ γ k R t + k + 1 G_t \doteq R_{t+1}+{\gamma}R_{t+2}+{\gamma}^2R_{t+3}+\ldots =\sum_{k=0}^{\infty}{\gamma_k R_{t+k+1}} Gt​≐Rt+1​+γRt+2​+γ2Rt+3​+…=k=0∑∞​γk​Rt+k+1​

其中 0 ≤ γ ≤ 1 0\leq\gamma\leq1 0≤γ≤1 称为是 Discount Rate，它代表未来第 k k k 步的 reward 的价值只是当前立即获得的 reward 的 γ k − 1 \gamma^{k-1} γk−1 倍，若 γ < 1 \gamma<1 γ<1，则当序列 { R k } \{R_k\} {Rk​} 有界的时候 G t G_t Gt​ 可以得到一个有限的值，若 γ = 0 \gamma=0 γ=0，则认为这个 agent 是 “myopic”（目光短浅的），它只关心当前的 rewards，选择下一个 A t A_t At​ 的准则就是最大化 R t + 1 R_{t+1} Rt+1​。 γ \gamma γ 越趋近于 1 1 1，则这个 agent 越是具有“远见的”。

4 Episodic 和 Continuing Tasks 的统一表达形式

增强学习任务大致可以分为两类：一类是 agent-environment 交互过程可以自然结束的 episodes 或者称为是 episodic tasks，另外一类是不能自然结束的 continuing tasks， 其中第一种任务的数学表达较为简单，因为每一个 action 只会影响有限数量的 rewards。

下面先介绍 episode 的数学表达形式，假设这里考虑的是一系列具有有限时间步骤的 episodes，每个 episode 的时间步骤都是从 0 0 0 开始标记的，这里用 S t , i S_{t,i} St,i​ 来代表第 i i i 个 episode 在第 t t t 时刻的状态，这种表达方式同样可以扩展到 A t , i , R t , i , π t , i , T i A_{t,i}, R_{t,i}, \pi_{t,i}, T_{i} At,i​,Rt,i​,πt,i​,Ti​ 等，之后的介绍中如果没有特别的标定 i i i，代表这个符号针对的是一个任意的 episode，它可以推广到所有的 episodes。

其实 episodic 和 continuing tasks 是可以表达成统一的形式的，比如考虑下图这种转换形式，它的特殊在于具有一个特殊的 Absorbing State，即图中用黑色阴影标识的状态，它的特点是这个状态只能转换到自己本身，而不能转换成其他的状态，从初始状态 S 0 S_0 S0​ 开始，它获得的 reward 序列为 + 1 , + 1 , + 1 , 0 , 0 , 0 , … +1,+1,+1,0,0,0, \ldots +1,+1,+1,0,0,0,…，则对这个序列求和得到的值与对前 T T T （这里 T = 3 T=3 T=3）个 reward 求和得到的结果相同。

因此，可以将这两种情况统一表达成：
G t ≐ ∑ k = 0 T − t − 1 γ k R t + k + 1 G_t \doteq \sum_{k=0}^{T-t-1}{\gamma_kR_{t+k+1}} Gt​≐k=0∑T−t−1​γk​Rt+k+1​

其中，包含了 T = ∞ T=\infty T=∞ 和 γ = 1 \gamma=1 γ=1 的情况（但是这俩不能同时满足）。

5 马尔可夫性质

在 RL 框架中，agent是依据环境的状态来做决定，那么这个环境的 state signal 能说明什么？不能说明什么呢？在 RL 中比较关心的一种情况是环境具有 Markov property 的情景。

通常，将能够成功保留所有相关信息的状态信号就称为是 Markov，或者称是具有 Markov Property。这种性质怎样用数学表达式来表示呢？我们知道，一般环境的下一个状态是由之前所有的状态来决定的，这种动态性可以表示成一个联合概率分布：

P r { S t + 1 = s ′ , R t + 1 = r ∣ S 0 , A 0 , R 1 , … , S t − 1 , A t − 1 , R t , S t , A t } Pr\{S_{t+1}=s',R_{t+1}=r|S_0,A_0,R_1,\ldots,S_{t-1},A_{t-1},R_t,S_t,A_t\} Pr{St+1​=s′,Rt+1​=r∣S0​,A0​,R1​,…,St−1​,At−1​,Rt​,St​,At​}

如果这个状态信号具有 Markov Property，那么环境的动态性完全由上一个状态和行为来决定，即：

p ( s ′ , r ∣ s , a ) ≐ P r { S t + 1 = s ′ , R t + 1 = r ∣ S t = s , A t = a } p(s',r|s,a)\doteq Pr\{S_{t+1}=s', R_{t+1}=r| S_t=s, A_t=a\} p(s′,r∣s,a)≐Pr{St+1​=s′,Rt+1​=r∣St​=s,At​=a}

如果满足这个属性，那么预测下一个 states 和期望的 reward 只需利用当前的状态和 action 即可，而不需要历史信息。

6 Markov Decision Processes

满足 Markov property 的 RL 任务就称作是 Markov Decision Process，简称为 MDP，如果状态和行为空间都是有限的，那么就称为是 Finite Markov Decision Process，简称为 Finite MDP。Finite MDPs 在 RL 理论中是非常重要的。

对一个 Markon 的状态 s s s 和下一个状态 s ′ s' s′，状态转移概率（State Transition Probability） 定义为：

P s s ′ = P [ S t + 1 = s ′ ∣ S t = s ] {\mathcal{P}}_{ss' }=P[S_{t+1}=s'|S_t=s] Pss′​=P[St+1​=s′∣St​=s]

状态转移矩阵（State Transition Matrix） P {\mathcal{P}} P 定义了从所有状态 s s s 到所有可能的下一个状态 s ′ s' s′ 的转移概率，可以写作为：

显然矩阵的每一行的和为 1。

对于一个特定的 finite MDP，它是由状态行为集合和环境的 one-step 动态定义的，给定状态 s s s 和行为 a a a，下一个可能的状态 s ′ s' s′ 和奖励 r r r 对的概率为：

p ( s ′ , r ∣ s , a ) ≐ P r { S t + 1 = s ′ , R t + 1 = r ∣ S t = s , A t = a } (2) p(s',r|s,a)\doteq Pr\{S_{t+1}=s', R_{t+1}=r| S_t=s, A_t=a\} \tag{2} p(s′,r∣s,a)≐Pr{St+1​=s′,Rt+1​=r∣St​=s,At​=a}(2)

这个等式完全定义了一个 finite MDP 的动态性，之后的理论基本都是建立在假设环境是 finite MDP 的基础上的。

有了等式（2），就可以计算我希望知道的很多量，如：
　　
State-Action 对的期望 Rewards 为：

r ( s , a ) ≐ E [ R t + 1 ∣ S t = s , A t = a ] = ∑ r ∈ R r ∑ s ′ ∈ S p ( s ′ , r ∣ s , a ) r(s,a)\doteq E[R_{t+1}| S_t=s, A_t=a] =\sum_{r\in {\mathcal{R}}}r\sum_{s' \in{\mathcal{S}}}{p(s',r|s,a)} r(s,a)≐E[Rt+1​∣St​=s,At​=a]=r∈R∑​rs′∈S∑​p(s′,r∣s,a)

状态转换概率（State-Transition Probabilities） 为：

p ( s ′ ∣ s , a ) ≐ P r { S t + 1 = s ′ ∣ S t = s , A t = a } = ∑ r ∈ R p ( s ′ , r ∣ s , a ) p(s'|s,a) \doteq Pr\{S_{t+1}=s' | S_t=s, A_t=a\}=\sum_{r\in {\mathcal{R}}}{p(s',r|s,a)} p(s′∣s,a)≐Pr{St+1​=s′∣St​=s,At​=a}=r∈R∑​p(s′,r∣s,a)

State - Action - Next State这个三元组合对应的期望 Rewards 为：

r ( s , a , s ′ ) ≐ E [ R t + 1 ∣ S t = s , A t = a , S t + 1 = s ′ ] = ∑ r ∈ R r p ( s ′ , r ∣ s , a ) p ( s ′ ∣ s , a ) r(s,a,s') \doteq E[R_{t+1} | S_t=s, A_t=a, S_{t+1}=s'] = \frac{\sum_{r\in {\mathcal{R}}}{rp(s',r|s,a)}}{ p(s'|s,a)} r(s,a,s′)≐E[Rt+1​∣St​=s,At​=a,St+1​=s′]=p(s′∣s,a)∑r∈R​rp(s′,r∣s,a)​

对 finite MDP 来说，Transition Graph 是一种总结其动态性的有效方式，比如下图所示，其中大的空心圆圈代表的是状态节点（ State Nodes ），圈圈中字是状态的名称，而小的实心的圆圈代表的是行为节点（ Action Nodes ），小圆圈旁边的字代表的是执行的行为，每条带箭头的线代表的是在状态 s s s 下选择行为 a a a 后转换到下一个状态 s ′ s' s′ 的概率 p ( s ′ ∣ s , a ) p(s'|s,a) p(s′∣s,a) 和相应的回报值 r ( s , a , s ′ ) r(s,a,s') r(s,a,s′)：

7 Value Functions

在RL问题中，Value Function 是一个重要的概念，几乎所有的 RL 算法都需要计算它，value function 是对 agent 的状态的评价，或者是对 state-action 对的评价，考虑到 agent 的 goal，不难想到这种评价一定是基于对未来期望的 rewards 的评价，当然，这种对未来期望的 rewards 依赖于 agent 选择的行为以及依据的 policy。

这里还按照之前的符号定义，令 π \pi π 代表 policy，即它是从每个状态 s s s 向每个行为 a a a 的映射， π ( a ∣ s ) \pi(a|s) π(a∣s) 代表在状态 s s s 下执行行为 a a a 的概率，则在规则 π \pi π 下状态 s s s 的 value 就用 v π ( s ) v_{\pi}(s) vπ​(s) 来表示，它表示从状态 s s s 开始一直遵从规则 π \pi π 的期望 return，对于 MDPs，可以得到：
v π ( s ) ≐ E π [ G t ∣ S t = s ] = E π [ ∑ k = 0 ∞ γ k R t + k + 1 ∣ S t = s ] v_{\pi}(s) \doteq {\Bbb E}_{\pi}[G_t|S_t=s]= {\Bbb E}_{\pi}[\sum_{k=0}^{\infty}{\gamma^kR_{t+k+1}}|S_t=s] vπ​(s)≐Eπ​[Gt​∣St​=s]=Eπ​[k=0∑∞​γkRt+k+1​∣St​=s]

其中， E π [ ⋅ ] {\Bbb E}_{\pi}[\cdot] Eπ​[⋅] 指的是给定规则 π \pi π 下随机变量的期望值，并且时间 t t t 是个任意值，通常将函数 v π v_\pi vπ​ 称为是 Policy π \pi π 的 State-Value Function。

相似的就可以定义在规则 π \pi π 和状态 s s s 下选择行为 a a a 的 value 值，用符号 q π ( s , a ) q_\pi(s,a) qπ​(s,a) 来表示，它表示的而是从状态 s s s 开始一直遵从规则 π \pi π，在状态 s s s 下选择行为 a a a 的期望 return，因此有：
q π ( s , a ) ≐ E π [ G t ∣ S t = s , A t = a ] = E π [ ∑ k = 0 ∞ γ k R t + k + 1 ∣ S t = s , A t = a ] q_{\pi}(s,a) \doteq {\Bbb E}_{\pi}[G_t|S_t=s, A_t=a] = {\Bbb E}_{\pi} [\sum_{k=0}^{\infty}{\gamma^kR_{t+k+1}}|S_t=s, A_t=a] qπ​(s,a)≐Eπ​[Gt​∣St​=s,At​=a]=Eπ​[k=0∑∞​γkRt+k+1​∣St​=s,At​=a]

通常将函数 q π q_\pi qπ​ 称为是 Policy π \pi π 的 Action-Value Function。

通常函数 v π v_\pi vπ​ 和 q π q_\pi qπ​ 是从经验中估计得到的，常用的是取平均的方法，当处于状态 s s s 的次数或者在状态 s s s 下执行行为 a a a 的次数趋于无穷时，平均值就可以收敛到 v π ( s ) v_\pi(s) vπ​(s) 或者 q π ( s , a ) q_\pi(s,a) qπ​(s,a)，因为这种方法是对真实返回值的许多次随机样本进行平均，因此称这种方法为 Monte Carlo Methods，这种方法之后也会再详细介绍。

在RL和动态编程（Dynamic Programming）中使用的 value function 具有一个重要的属性，即它们满足一种递归关系。对于规则 π \pi π 和状态 s s s，状态 s s s 的 value 和他之后的状态的 value 满足下面的等式关系：

v π ( s ) ≐ E π [ G t ∣ S t = s ] = E π [ ∑ k = 0 ∞ γ k R t + k + 1 ∣ S t = s ] = E π [ R t + 1 + γ ∑ k = 0 ∞ γ k R t + k + 2 ∣ S t = s ] = ∑ a π ( a ∣ s ) ∑ s ′ ∑ r p ( s ′ , r ∣ s , a ) [ r + γ E π [ ∑ k = 0 ∞ γ k R t + k + 2 ∣ S t + 1 = s ′ ] ] = ∑ a π ( a ∣ s ) ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r + γ v π ( s ′ ) ] , ∀ s ∈ S \begin{aligned} v_{\pi}(s) & \doteq E_{\pi}[G_t|S_t=s]\\ &= E_{\pi}[\sum_{k=0}^{\infty}{\gamma^kR_{t+k+1}}|S_t=s]\\ &= E_{\pi}[R_{t+1} + \gamma \sum_{k=0}^{\infty}{\gamma^kR_{t+k+2}}|S_t=s]\\ &= \sum_a \pi(a|s) \sum_{s'} \sum_{r} p(s',r|s,a)[r+\gamma E_{\pi}[\sum_{k=0}^{\infty}{\gamma^k R_{t+k+2}}|S_{t+1}=s']] \\ &= \sum_a\pi(a|s)\sum_{s',r}{p(s',r|s,a)[r+\gamma v_{\pi}(s')]},\ \ \forall s\in {\mathcal{S}} \end{aligned} vπ​(s)​≐Eπ​[Gt​∣St​=s]=Eπ​[k=0∑∞​γkRt+k+1​∣St​=s]=Eπ​[Rt+1​+γk=0∑∞​γkRt+k+2​∣St​=s]=a∑​π(a∣s)s′∑​r∑​p(s′,r∣s,a)[r+γEπ​[k=0∑∞​γkRt+k+2​∣St+1​=s′]]=a∑​π(a∣s)s′,r∑​p(s′,r∣s,a)[r+γvπ​(s′)],  ∀s∈S​

其中最后一个等式为：
v π ( s ) ≐ ∑ a π ( a ∣ s ) ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r + γ v π ( s ′ ) ] , ∀ s ∈ S (3) v_{\pi}(s) \doteq \sum_a\pi(a|s)\sum_{s',r}{p(s',r|s,a)[r+\gamma v_{\pi}(s')]},\ \ \forall s\in {\mathcal{S}} \tag{3} vπ​(s)≐a∑​π(a∣s)s′,r∑​p(s′,r∣s,a)[r+γvπ​(s′)],  ∀s∈S(3)

其中 a ∈ A ( s ) a\in{\mathcal{A}}(s) a∈A(s)， s ′ ∈ S s' \in{\mathcal{S}} s′∈S，公式(3) 称作是 v π v_{\pi} vπ​ 的 Bellman Equation，还有一个重要的概念是 Backup Diagrams，如下图的（a）所示，其中每个空心圆代表一个状态，每个实心圆代表一个 state-action 对，最初的状态即 root node 位于最上面，在每个状态 s s s 下，agent 可以从多个 action 中选择，每对 ( s , a ) (s,a) (s,a) 都会以一定的概率转化到状态 s ′ s' s′ 并伴随有回报值 r r r。

结合 Backup Diagrams，就可以更好的理解 Bellman equation，从公式（3）可以看出，它对所有的可能情况进行了平均，并且每个部分的权重为它发生的概率。这种图之所以称作是 Backup Diagrams，是因为它表达出了 RL 方法中 update 和 backup 操作的基础，这些操作将 value 信息从下一个状态（或下一个 state-action 对） back 到了当前的状态（或state-action 对）。

8 Optimal Value Functions

解决RL任务，就是找到一种 policy 来获得最大的长远 reward，对于有限的MDPs，可以精确地定义一种优化的规则，上面介绍的 value function 定义了 policies 之间的一种偏序关系，因此可以利用它来定义 Optimal Policy：

定义规则 π \pi π 与 规则 π ′ \pi' π′ 相比更好或者相当是指，对所有的状态规则 π \pi π 的期望 return 都比规则 π ′ \pi' π′ 的大或者相等。即：
π ≥ π ′ ⇔ v π ( s ) ≥ v π ′ ( s ) ∀ s ∈ S \pi \geq \pi' \Leftrightarrow v_\pi(s) \geq v_\pi' (s)\ \ \ \forall s\in{\mathcal{S}} π≥π′⇔vπ​(s)≥vπ′​(s)   ∀s∈S

则 Optimal Policy 指的就是比其他所有 policies 都好或者相当的规则，用符号 π ∗ \pi_{\ast} π∗​ 来表示。

同样地，也可以定义 Optimal State-Value Function，用符号 v ∗ v_{\ast} v∗​ 来表示，定义式为：
v ∗ ≐ max ⁡ π v π ( s ) ∀ s ∈ S v_{\ast} \doteq \max_\pi{v_\pi(s)}\ \ \ \ \forall s\in{\mathcal{S}} v∗​≐πmax​vπ​(s)    ∀s∈S

优化的 policies 也具有相同的 Optimal Action-Value Function，用 q ∗ q_{\ast} q∗​ 来表示，定义式为：

q ∗ ( s , a ) ≐ max ⁡ π q π ( s , a ) ∀ s ∈ S , ∀ a ∈ A ( s ) q_{\ast}(s,a) \doteq \max_\pi{q_\pi(s,a)}\ \ \ \ \forall s\in{\mathcal{S}},\forall a\in{\mathcal{A}}(s) q∗​(s,a)≐πmax​qπ​(s,a)    ∀s∈S,∀a∈A(s)

对于 state-action 对 ( s , a ) (s,a) (s,a)，该函数给出了在状态 s s s 下执行 a a a 的期望 return，因此可以将 q ∗ q_{\ast} q∗​ 用 v ∗ v_{\ast} v∗​ 来表示：
q ∗ ( s , a ) ≐ E [ R t + 1 + γ v ∗ ( S t + 1 ) ∣ S t = s , A t = a ] q_{\ast}(s,a) \doteq {\Bbb E}[R_{t+1}+\gamma v_{\ast}(S_{t+1})|S_t=s,A_t=a] q∗​(s,a)≐E[Rt+1​+γv∗​(St+1​)∣St​=s,At​=a]

9 Optimality and Approximation

上一小节介绍了优化的 value function和优化的 policies，但在真实情况中，即使拥有了环境动态性完整的精确的模型，也很难简单地求解 Bellman优化方程计算出优化的 policy。并且，当状态和行为集合很大时，也会需要非常大的内存，因此可用的内存也是直接求解的一个限制因素。解决这个的问题的办法就是采用近似的求解方法。

参考文献
[1] Reinforcement Learning: An Introduction, Richard S. Sutton and Andrew G. Barto
[2] UCL Course on RL