动态规划求解强化学习任务——策略改进定理公式推导

• 目录
• • 策略改进定理——逻辑引导
  • 铺垫：策略(Policy)$\pi$、奖励(Reward)之间的关系讨论
  • • 重温策略$\pi$
    • 状态(State)和动作(Action)之间的关系讨论
    • 策略(Policy)和奖励(Reward)之间的关系
  • 策略改进定理及推导

目录

前面两节讲到了在策略评估过程中使用解析和迭代两种方式在给定策略$\pi$的情况下求解最优价值函数。今天将介绍策略迭代的第二个部分：策略改进。

策略改进定理——逻辑引导

策略改进，顾名思义，就是更新/优化策略$\pi$。
给出一个策略$\pi$，通过策略改进的方法，产生一个新的策略 π ′ \pi' π′，使得策略 π ′ \pi' π′比策略$\pi$在马尔可夫决策过程中表现的更加优秀。
问题：假定我们根据一个策略$\pi$求得了一个新的策略 π ′ \pi' π′后，如何判定新的策略 π ′ \pi' π′比更新前的$\pi$更加优秀呢？
最直接的方式：价值函数(Value Function)。直接用价值函数结果的大小来映射策略的优劣性：谁的价值函数结果更大，谁的策略就更优秀。

至此，我们确定了使用价值函数衡量$\pi$和 π′ \pi' π′之间优劣性的评估规则。
∀ s ∈ S →Vπ ( s ) ≤V π ′ ( s ) \forall s\in \mathcal S \to V_{\pi}(s) \leq V_{\pi'}(s) ∀s∈S→Vπ​(s)≤Vπ′​(s)
我们称满足上式的策略 π ′ \pi' π′不亚于策略$\pi$。

按照上述思路，既然要比较价值函数 $\to$ 需要将某状态下两种策略对应的价值函数求出来。
根据前面介绍的策略评估方法，我们可以使用迭代方式对价值函数进行求解。但即便是迭代方式(时间复杂度$k\times |\mathcal{S}|$)求解2个价值函数，并且在每次策略迭代过程中都会求解2个价值函数 $\to$ 这种方式依然非常消耗资源。

是否存在更加简便的方式去处理上述问题？$\to$ 策略改进定理就提供了这样一种方式。

铺垫：策略(Policy)$\pi$、奖励(Reward)之间的关系讨论

重温策略$\pi$

在介绍策略改进定理之前，需要对相关概念进一步进行解析。
我们在马尔可夫奖励过程中介绍了策略$\pi (a\mid s)$。策略$\pi (a\mid s)$本质上一个条件概率，在假定$s,a$均属于离散型随机变量的条件下，$\pi (a\mid s)$本意表示“在$s$状态发生的条件下，有意义的动作$a$发生可能性的概率分布。”
无论是确定性策略还是随机性策略,都可以用这种方式表示，只不过概率分布较特殊：确定性策略概率分布矩阵中只包含唯一一个元素1，其余元素均为0。
$$\pi (s\mid a)=[0,0,1,...,0,0]$$

状态(State)和动作(Action)之间的关系讨论

在重温一遍策略$\pi$的概念之后，我们考虑下面这个问题：
状态s是否能够操控动作a？/ 状态s确定的条件下，是否存在唯一一个动作a与其进行映射？
当然是有的 $\to$ 上面的确定性策略就是一个很好的例子。如果策略是随机性策略呢？
答案是否定的。
我们这里引用打篮球例子进行解释：
假定状态集合$\mathcal{S}$中包含5种状态：

数学表示如下：
S = {s1 ,s2 ,s3 ,s4 ,s5 } \mathcal S = \{s_1,s_2,s_3,s_4,s_5\} S={s1​,s2​,s3​,s4​,s5​}
假定动作集合$\mathcal{A}$中包含6种状态：

数学表示如下：
A = {a1 ,a2 ,a3 ,a4 ,a5 ,a6 } \mathcal A = \{a_1,a_2,a_3,a_4,a_5,a_6\} A={a1​,a2​,a3​,a4​,a5​,a6​}
篮球规则就不赘述了，假设当前时刻状态是 s3 s_3 s3​(持球进攻)状态，在 s 3 s_3 s3​状态有意义的动作如下：
A (s3 ) = {a2 ,a3 ,a5 } \mathcal A(s_3) = \{a_2,a_3,a_5\} A(s3​)={a2​,a3​,a5​}
我们知道 $\to$ "运球，投球，传球"是必须在“持有球”的条件下发生的动作，我们不否认状态和动作之间可能存在关联关系，但在上述示例下，通过上述状态去直接操控某个单一动作肯定是不合逻辑的。我们只能认为在当前时刻状态的条件下，某一动作发生的条件概率可能很高(不是等概率分布)。
示例几种影响策略的条件(在"我"手持球的条件下)：

• 当前时刻状态距离篮筐较远 $\to$ 投篮命中的概率较低，并且附近队友被防守很紧 $\to$ 传球被抢断的概率较高。该时刻策略选择“运球 - 等待良好的进攻时机”概率更高一些；
• 当前时刻状态在三分线附近，对方对于你的防守较宽松，但对三分线内的队友防守很严格 $\to$ (常规逻辑)运球，投球概率会更高一些；
• 当前时刻状态距离篮筐较近(如：对方的三分线内)此时投球被盖帽的风险极高，并且运球的空间也被压缩的极小 $\to$ 被抢断的风险极高；此时我们策略对应的概率更偏向投球(搏一搏) 、传球一些；

以上三种例子中，状态确实对动作产生一定的影响，在某些状态下，即便被选中的概率再低 $\to$ 也有可能被选中。

策略(Policy)和奖励(Reward)之间的关系

针对上述“持球进攻状态”例子，设计动作发生的奖励如下(可能不完全，但不影响讲解)：

根据上面的奖励情况，归纳奖励集合如下：
$$\mathcal{R}=\{-3,0,3\}$$
我们知道，动作(Action)是通过策略$\pi$的概率分布随机选择产生的结果，而奖励(Reward)是通过确定的状态，确定的动作，通过系统内部状态转移得到的结果。
基于上述例子 $\to$ 假设我们确定当前时刻状态是 s3 s_3 s3​(持球进攻)状态，并从基于该状态下的策略π ( a ∣s3 ) ( a ∈ A (s3 ) ) \pi(a \mid s_3)(a \in \mathcal A(s_3)) π(a∣s3​)(a∈A(s3​))中选择一个动作 a3 a_3 a3​(投球)，产生的奖励可能性如下：

通过观察可发现，我们即便是确定了策略： π ( a 3 ∣ s 3 ) \pi(a_3 | s_3) π(a3​∣s3​)，但最终的奖励结果依然存在不同的选择结果。下面对上述情况进行总结：

• 在随机性策略中，$t$时刻状态 St S_t St​和动作 At A_t At​之间无 必然联系；
• $t+1$时刻奖励 R t + 1R_{t+1} Rt+1​的结果和策略π (At ∣St ) \pi(A_t \mid S_t) π(At​∣St​)无 必然联系；
• 我们不否认策略 π ( A t∣ S t) \pi(A_t \mid S_t) π(At​∣St​)对 R t + 1 R_{t+1} Rt+1​产生影响，但影响 R t + 1R_{t+1} Rt+1​的因素不只是策略，还包含其他因素。在马尔可夫奖励过程一节中介绍到 R t + 1R_{t+1} Rt+1​是系统内部产生的结果，可能存在客观因素的影响。例如动态特性函数p (s′ , r ∣ s , a ) p(s',r \mid s,a) p(s′,r∣s,a)，在打篮球的例子中，能够影响p (s′ , r ∣ s , a ) p(s',r \mid s,a) p(s′,r∣s,a)转移概率的因素都算是客观因素。例如球员身高，弹跳能力，投球精准度等等。

策略改进定理及推导

定理：给定 π , π ′ , ∀ s ∈ S \pi,\pi',\forall s \in \mathcal S π,π′,∀s∈S，从 π ′ \pi' π′中产生的动作 π ′ ( s ) \pi'(s) π′(s)满足：
qπ [ s ,π′ ( s ) ] ≥Vπ ( s ) q_\pi[s,\pi'(s)] \geq V_\pi(s) qπ​[s,π′(s)]≥Vπ​(s)
那么则有：
∀ s ∈ S ,V π ′ ( s ) ≥Vπ ( s ) \forall s \in \mathcal S,V_{\pi'}(s) \geq V_\pi(s) ∀s∈S,Vπ′​(s)≥Vπ​(s)

对该定理进行证明：
根据条件 → V π ( s ) ≤ q π [ s , π ′ ( s ) ] \to V_\pi(s) \leq q_\pi[s,\pi'(s)] →Vπ​(s)≤qπ​[s,π′(s)]，对 q π [ s , π ′ ( s ) ] q_\pi[s,\pi'(s)] qπ​[s,π′(s)]进行展开：
q π [ s , π ′ ( s ) ] = p ( s ′ , r ∣ s , a ) [ r + γ V π ( s ′ ) ] = E π [ G t ∣ S t = s , A t = π ′ ( s ) ] \begin{aligned} q_\pi[s,\pi'(s)] & = p(s',r \mid s,a)[r + \gamma V_\pi(s')] \\ & = \mathbb E_{\pi}[G_t \mid S_t = s,A_t = \pi'(s)] \\ \end{aligned} qπ​[s,π′(s)]​=p(s′,r∣s,a)[r+γVπ​(s′)]=Eπ​[Gt​∣St​=s,At​=π′(s)]​

关键步骤：沿着贝尔曼期望方程继续展开 $\to$
= E [R t + 1 + γVπ (S t + 1 ) ∣St = s ,At =π′ ( s ) ] =\mathbb E[R_{t+1} + \gamma V_\pi(S_{t+1}) \mid S_t = s,A_t = \pi'(s)] =E[Rt+1​+γVπ​(St+1​)∣St​=s,At​=π′(s)]
细心的小伙伴发现，这里的期望形式$\mathbb{E}$下标没有标注任何策略，为什么不标注？ $\to$
根据前面的讲述，由于$t$时刻动作 At A_t At​产生所使用的策略由 π → π ′ \pi \to \pi' π→π′，对应时刻的奖励 R t + 1R_{t+1} Rt+1​也被影响。
需要注意的是， π ′ \pi' π′只影响了当前时刻的 At ,R t + 1A_t,R_{t+1} At​,Rt+1​的选择，对后续时刻没有产生影响，因此针对上述式子 Rt+1 + γ V π ( St+1 ) R_{t+1} + \gamma V_\pi(S_{t+1}) Rt+1​+γVπ​(St+1​)中：

• R t + 1R_{t+1} Rt+1​是由 π′ \pi' π′影响的；
• γVπ (S t + 1 ) \gamma V_\pi(S_{t+1}) γVπ​(St+1​)是由$\pi$影响的；

因此没有进行下标的标注，但可以换一种方式对上式进行表达：只有当前时刻的 At A_t At​是由 π′ \pi' π′产生的, R t + 1R_{t+1} Rt+1​是由 π′ \pi' π′影响的 $\to$ 当前时刻$\mathbb{E}$的下标自然是 π′ \pi' π′，其余回馈 Rt+1 , Rt+2 , . . . → V π ( St+1 ) R_{t+1},R_{t+2},... \to V_\pi(S_{t+1}) Rt+1​,Rt+2​,...→Vπ​(St+1​)仍然使用策略$\pi$不变。
=E π ′ [R t + 1 + γVπ (S t + 1 ) ∣St = s ] =\mathbb E_{\pi'}[R_{t+1} + \gamma V_\pi(S_{t+1}) \mid S_t = s] =Eπ′​[Rt+1​+γVπ​(St+1​)∣St​=s]

经过上述逻辑整理，可获得：
V π ( s ) ≤ q π [ s , π ′ ( s ) ] = E π [ G t ∣ S t = s , A t = π ′ ( s ) ] = E [ R t + 1 + γ V π ( S t + 1 ) ∣ S t = s , A t = π ′ ( s ) ] = E π ′ [ R t + 1 + γ V π ( S t + 1 ) ∣ S t = s ] \begin{aligned} V_\pi(s) & \leq q_\pi[s,\pi'(s)] \\ & = \mathbb E_{\pi}[G_t \mid S_t = s,A_t = \pi'(s)] \\ & = \mathbb E[R_{t+1} + \gamma V_\pi(S_{t+1}) \mid S_t = s,A_t = \pi'(s)] \\ & = \mathbb E_{\pi'}[R_{t+1} + \gamma V_\pi(S_{t+1}) \mid S_t = s] \end{aligned} Vπ​(s)​≤qπ​[s,π′(s)]=Eπ​[Gt​∣St​=s,At​=π′(s)]=E[Rt+1​+γVπ​(St+1​)∣St​=s,At​=π′(s)]=Eπ′​[Rt+1​+γVπ​(St+1​)∣St​=s]​

又根据条件 → V π ( St+1 ) ≤ q π [ St+1 , π ′ ( St+1 ) ] \to V_\pi(S_{t+1}) \leq q_\pi[S_{t+1},\pi'(S_{t+1})] →Vπ​(St+1​)≤qπ​[St+1​,π′(St+1​)]，可以将上式中的 V π ( St+1 ) V_\pi(S_{t+1}) Vπ​(St+1​)继续展开：
V π ( s ) ≤ q π [ s , π ′ ( s ) ] = E π ′ [ R t + 1 + γ V π ( S t + 1 ) ∣ S t = s ] ≤ E π ′ [ R t + 1 + γ q π [ S t + 1 , π ′ ( S t + 1 ) ] ) ∣ S t = s ] = E π ′ [ R t + 1 + γ R t + 2 + γ 2 V π ( S t + 2 ) ∣ S t = s ] ≤ E π ′ [ R t + 1 + γ R t + 2 + γ 2 q π [ S t + 2 , π ′ ( S t + 2 ) ] ) ∣ S t = s ] = E π ′ [ R t + 1 + γ R t + 2 + γ 2 R t + 3 + γ 3 V π ( S t + 3 ) ) ∣ S t = s ] ≤ . . . \begin{aligned} V_\pi(s) & \leq q_\pi[s,\pi'(s)] \\ & = \mathbb E_{\pi'}[R_{t+1} + \gamma V_\pi(S_{t+1}) \mid S_t = s] \\ & \leq \mathbb E_{\pi'}[R_{t+1} + \gamma q_\pi[S_{t+1},\pi'(S_{t+1})]) \mid S_t = s] \\ & = \mathbb E_{\pi'}[R_{t+1} + \gamma R_{t+2}+\gamma^2 V_\pi(S_{t+2}) \mid S_t = s] \\ & \leq \mathbb E_{\pi'}[R_{t+1} + \gamma R_{t+2} + \gamma^2 q_\pi[S_{t+2},\pi'(S_{t+2})]) \mid S_t = s] \\ & = \mathbb E_{\pi'}[R_{t+1} + \gamma R_{t+2}+\gamma^2 R_{t+3} + \gamma^3 V_{\pi}(S_{t+3})) \mid S_t = s] \\ & \leq ... \end{aligned} Vπ​(s)​≤qπ​[s,π′(s)]=Eπ′​[Rt+1​+γVπ​(St+1​)∣St​=s]≤Eπ′​[Rt+1​+γqπ​[St+1​,π′(St+1​)])∣St​=s]=Eπ′​[Rt+1​+γRt+2​+γ2Vπ​(St+2​)∣St​=s]≤Eπ′​[Rt+1​+γRt+2​+γ2qπ​[St+2​,π′(St+2​)])∣St​=s]=Eπ′​[Rt+1​+γRt+2​+γ2Rt+3​+γ3Vπ​(St+3​))∣St​=s]≤...​
随着我们展开的次数越多，我们发现：

• 连加式中除去最后一项元素 →R t + 1 + γR t + 2 +γ2 R t + 3 + . . . =Gt \to R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... = G_t →Rt+1​+γRt+2​+γ2Rt+3​+...=Gt​
• 连加式中最后一项元素 →γT Vπ (S t + T ) \to \gamma ^T V_\pi(S_{t+T}) →γTVπ​(St+T​)，随着迭代步骤$T$的增加； γT → 0 ( γ ∈ ( 0 , 1 ) ) \gamma^T \to 0 (\gamma \in (0,1)) γT→0(γ∈(0,1))

通过极限的方式求得：
Vπ ( s ) ≤ E [R t + 1 + γR t + 2 +γ2 R t + 3 + . . . ∣St = s ] =V π ′ ( s ) V_\pi(s) \leq \mathbb E[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... \mid S_t =s] = V_{\pi'}(s) Vπ​(s)≤E[Rt+1​+γRt+2​+γ2Rt+3​+...∣St​=s]=Vπ′​(s)

本节关于策略改进定理的介绍到此结束，下一节将介绍基于贪心策略下使用策略改进定理迭代求解策略$\pi$的算法过程。

相关参考：
【强化学习】动态规划【白板推导系列】
深度强化学习原理、算法pytorch实战 —— 刘全，黄志刚编著