- 目录
- 回顾
- 逻辑执行过程
- 算法过程与解析
- 算法过程
- 算法解析
- 实例解析
- 逻辑场景介绍
- 策略评估过程求解
- 异步动态规划法和同步动态规划法；
上一节中讲到使用解析方式求解最优价值函数,我们对逻辑场景进行简单设计： 设定状态(State)属于离散型随机变量，状态集合 S \mathcal S S内部共包含 ∣ S ∣ |\mathcal S| ∣S∣个离散状态： S = { s 1 , s 2 , . . . , s ∣ S ∣ } = { s i } ∣ i = 1 ∣ S ∣ \mathcal S = \{s_1,s_2,...,s_{|\mathcal S|}\}=\{s_i\}\vert_{i=1}^{|\mathcal S|} S={s1,s2,...,s∣S∣}={si}∣i=1∣S∣ 设定动作(Action)属于离散型随机变量，动作集合 A \mathcal A A内部共包含 ∣ A ∣ |\mathcal A| ∣A∣个离散动作,并且任意一个动作在每个状态中均有意义： A = { a 1 , a 2 , a 3 , . . . , a ∣ A ∣ } = { a i } ∣ i = 1 ∣ A ∣ \mathcal A = \{a_1,a_2,a_3,...,a_{|\mathcal A|}\}=\{a_i\}\vert_{i=1}^{|\mathcal A|} A={a1,a2,a3,...,a∣A∣}={ai}∣i=1∣A∣ 设定奖励(Reward)属于离散型随机变量，奖励集合 R \mathcal R R内部共包含 ∣ R ∣ |\mathcal R| ∣R∣个离散奖励： R = { r 1 , r 2 , r 3 , . . . , r ∣ R ∣ } = { r i } ∣ i = 1 ∣ R ∣ \mathcal R = \{r_1,r_2,r_3,...,r_{|\mathcal R|}\}=\{r_i\}\vert_{i=1}^{|\mathcal R|} R={r1,r2,r3,...,r∣R∣}={ri}∣i=1∣R∣
基于上述逻辑场景，最优价值函数的解析解可以理解成求解由 ∣ S ∣ |\mathcal S| ∣S∣个贝尔曼期望期望方程组成的 ∣ S ∣ |\mathcal S| ∣S∣元1次方程组: V π ( s ) = ( V π ( s 1 ) V π ( s 2 ) V π ( s 3 ) . . . V π ( s ∣ S ∣ ) ) = ( r π ( s 1 ) + γ ∑ j = 1 ∣ S ∣ P π ( s 1 , s j ) V π ( s j ) r π ( s 2 ) + γ ∑ j = 1 ∣ S ∣ P π ( s 2 , s j ) V π ( s j ) r π ( s 3 ) + γ ∑ j = 1 ∣ S ∣ P π ( s 3 , s j ) V π ( s j ) . . . r π ( s ∣ S ∣ ) + γ ∑ j = 1 ∣ S ∣ P π ( s ∣ S ∣ , s j ) V π ( s j ) ) V_\pi(s) = \begin{pmatrix} V_\pi(s_1) \\ V_\pi(s_2) \\ V_\pi(s_3)\\ ...\\ V_\pi(s_{|\mathcal S|}) \end{pmatrix}= \begin{pmatrix} r_\pi(s_1) + \gamma \sum_{j=1}^{|\mathcal S|}P_\pi(s_1,s_j)V_\pi(s_j) \\ r_\pi(s_2) + \gamma \sum_{j=1}^{|\mathcal S|}P_\pi(s_2,s_j)V_\pi(s_j) \\ r_\pi(s_3) + \gamma \sum_{j=1}^{|\mathcal S|}P_\pi(s_3,s_j)V_\pi(s_j)\\ ...\\ r_\pi(s_{|\mathcal S|}) + \gamma \sum_{j=1}^{|\mathcal S|}P_\pi(s_{|\mathcal S|},s_j)V_\pi(s_j) \end{pmatrix} Vπ(s)=⎝⎜⎜⎜⎜⎛Vπ(s1)Vπ(s2)Vπ(s3)...Vπ(s∣S∣)⎠⎟⎟⎟⎟⎞=⎝⎜⎜⎜⎜⎜⎛rπ(s1)+γ∑j=1∣S∣Pπ(s1,sj)Vπ(sj)rπ(s2)+γ∑j=1∣S∣Pπ(s2,sj)Vπ(sj)rπ(s3)+γ∑j=1∣S∣Pπ(s3,sj)Vπ(sj)...rπ(s∣S∣)+γ∑j=1∣S∣Pπ(s∣S∣,sj)Vπ(sj)⎠⎟⎟⎟⎟⎟⎞
算法的时间复杂度 → ∣ S ∣ 3 \to |\mathcal S|^3 →∣S∣3，为了优化时间复杂度，本节我们介绍使用迭代方式求解最优价值函数。
逻辑执行过程迭代求解的大致思路表示如下： 构造一个关于价值函数的数列，每迭代一次，就将迭代后的价值函数从尾部插入到数列中，并随着迭代次数的增加，数列尾部的结果通过不断更新并最终优化到某个具体结果。
根据之前提到的不动点定理，贝尔曼期望方程完全满足上述逻辑场景中的条件，因为:
- 贝尔曼期望方程中的自变量和函数均是价值函数； 可以将其理解为：我们以之前的价值函数作为媒介/条件，产生一个优于之前价值函数的新的价值函数，我们称这种方法为 自举法(Boostrapping)
- 不动点定理是经过数学证明必然收敛的，因此贝尔曼期望方程输出结果随着迭代过程增加 必然收敛 。
结合上面逻辑，使用贝尔曼期望方程对迭代过程进行设计： V π ( s ) = ∑ a ∈ A π ( a ∣ s ) ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r + γ V π ( s ′ ) ] V k ( s ) = ∑ a ∈ A π ( a ∣ s ) ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r + γ V k − 1 ( s ′ ) ] \begin{aligned} V_\pi(s) & = \sum_{a \in \mathcal A}\pi(a \mid s) \sum_{s',r}p(s',r \mid s,a)[r + \gamma V_\pi(s')] \\ V_k(s) & = \sum_{a \in \mathcal A}\pi(a \mid s) \sum_{s',r}p(s',r \mid s,a)[r + \gamma V_{k-1}(s')] \\ \end{aligned} Vπ(s)Vk(s)=a∈A∑π(a∣s)s′,r∑p(s′,r∣s,a)[r+γVπ(s′)]=a∈A∑π(a∣s)s′,r∑p(s′,r∣s,a)[r+γVk−1(s′)] 观察上述两个公式，第一个是贝尔曼期望方程，第二个是基于贝尔曼期望方程修改的迭代公式，相比于期望方程，该公式仅修改了价值函数对应的下标，但是思路发生了很大变化； 策略评估的核心就是给定策略 π \pi π,求解最优状态价值函数 V π ( s ) → V_\pi(s) \to Vπ(s)→因此我们淡化对策略 π \pi π的表示( π \pi π是确定的)，注重对迭代步骤 k k k的表示。
- 贝尔曼期望方程中的 V π ( s ′ ) V_\pi(s') Vπ(s′)是 S t = s → S t + 1 = s ′ S_t=s \to S_{t+1}=s' St=s→St+1=s′的价值函数结果，是未来时刻价值函数的信息；
- 迭代公式中的 V k − 1 ( s ′ ) V_{k-1}(s') Vk−1(s′)是过去最新一次策略评估产生的状态价值函数结果。
以状态价值函数(state-value function)为例，我们构建基于状态价值函数的策略评估算法如下：
输入初始策略： π ( a ∣ s ) \pi(a \mid s) π(a∣s),动态特性函数： p ( s ′ , r ∣ s , a ) p(s',r\mid s,a) p(s′,r∣s,a),奖励： r r r,折扣系数： γ \gamma γ初始化操作(Initialization operation)1. 对 ∀ s ∈ S \forall s \in \mathcal S ∀s∈S,初始化状态价值函数：如 V ( s ) = 0 V(s) = 0 V(s)=0; 2.设置一个阈值 θ \theta θ,将其设置为很小的实数值，如 θ = 0.01 \theta=0.01 θ=0.01策略评估(Policy Evaluation)1. repeat 对每一轮策略评估： k = 1 , 2 , . . . k=1,2,... k=1,2,... 2. δ ← 0 \delta \gets 0 δ←0 3. for 每个状态 s s s do： 4. v ← V ( s ) \mathcal v \gets V(s) v←V(s) 5. V ( s ) ← ∑ a ∈ A π ( a ∣ s ) ∑ s ′ , r p ( s ′ , r ∣ s , a ) [ r + γ V ( s ′ ) ] V(s) \gets \sum_{a \in \mathcal A}\pi(a \mid s) \sum_{s',r}p(s',r \mid s,a) [r + \gamma V(s')] V(s)←∑a∈Aπ(a∣s)∑s′,rp(s′,r∣s,a)[r+γV(s′)] 6. δ ← m a x ( δ , ∣ v − V ( s ) ∣ ) \delta \gets max(\delta, \mid \mathcal v - V(s) \mid) δ←max(δ,∣v−V(s)∣)7. end for8. until δ < θ \delta < \theta δ ∣Vk+1(s)−Vinit(s)∣> 人为设置标准 δ → \delta \to δ→ 两次迭代结果有较大差距，需要安排下一次迭代( k = 2 k=2 k=2),直到状态价值函数收敛完成。 实例解析在这里使用刘全，黄志刚老师编著的《深度强化学习 ——原理、算法与pytorch实战》介绍策略评估中使用的确定性环境扫地机器人为例；
逻辑场景介绍确定状态集合 S \mathcal S S： 该实例将“需要清扫的环境”划分为25个格子(0~24)，并代表25个离散状态。表示如下：
其中0号位置为充电桩，12号位置为障碍物(机器人无法到达12号位置)，19号位置是需要清扫的垃圾
20212223241516171819(垃圾)101112(障碍物)1314567890(充电桩)1234状态集合 S \mathcal S S表示如下： S = { s 0 , s 1 , s 2 , . . . , s 24 } \mathcal S = \{s_0,s_1,s_2,...,s_{24}\} S={s0,s1,s2,...,s24} 接下来确定动作和策略： 基于规则,扫地机器人最多可采取 {上,下,左,右}四个动作；并设定策略为等概率策略，并且机器人一次只能移动1个格子。 π ( a ∣ s ) = 1 ∣ A ( s ) ∣ \pi(a \mid s) = \frac{1}{|\mathcal A(s)|} π(a∣s)=∣A(s)∣1 示例：
- 机器人在0位置(充电桩) → \to →只能向{上,右}两个方向前进；两个方向概率均为 1 2 \frac{1}{2} 21；
- 机器人在1位置 → \to →可以向{上,左,右}三个方向前进；三个方向概率均为 1 3 \frac{1}{3} 31；
- 机器人在8位置 → \to →可以向{上,下,左,右}四个方向前进；四个方向概率均为 1 4 \frac{1}{4} 41；
针对不同状态存在不同动作集合。 接下来确定奖励集合 R \mathcal R R： 共设定4种奖励类型：
- 机器人到达0位置(充电桩) → r 0 = + 1 \to r_0=+1 →r0=+1；
- 机器人到达19位置(垃圾) → r 19 = + 3 \to r_{19}=+3 →r19=+3；
- 机器人撞向12位置(障碍物) → r 12 = − 10 \to r_{12}=-10 →r12=−10；
- 除了上述3个位置的其他位置 → r o t h e r s = 0 \to r_{others}=0 →rothers=0；
根据奖励类型，我们确定奖励集合： R = { + 1 , + 3 , − 10 , 0 } \mathcal R = \{+1,+3,-10,0\} R={+1,+3,−10,0} 最后确定动态特性函数 p ( s ′ , r ∣ s , a ) p(s',r \mid s,a) p(s′,r∣s,a)： 由于设计场景存在规则限制(机器人一次只能移动一个格子) → \to → 该场景下的动态特性函数 p ( s ′ , r ∣ s , a ) = 1 p(s',r \mid s,a)=1 p(s′,r∣s,a)=1恒成立； 解释： 假设当前时刻 t t t扫地机器人在位置6( S t = s 6 S_t=s_6 St=s6)，该状态下存在4个动作可以选择 → A = \to \mathcal A = →A= {上,下,左,右}; 如果我们从动作集合 A \mathcal A A中选择动作“上”并执行 → \to → 扫地机器人的状态必然从 S t = s 6 → S t + 1 = s 11 S_t=s_6 \to S_{t+1}=s_{11} St=s6→St+1=s11。 这种情况就是确定性环境(deterministic environment)(在马尔可夫奖励过程中有提到~传送门)
策略评估过程求解我们将所有状态的状态价值函数进行初始化 → V i n i t ( s ) \to V_{init}(s) →Vinit(s),初始化结果如下：
0.000.000.000.000.000.000.000.000.000.000.000.00障碍物0.000.000.000.000.000.000.000.000.000.000.000.00设置 δ = 0.0001 \delta = 0.0001 δ=0.0001 ；折扣系数 γ = 0.8 \gamma = 0.8 γ=0.8；
下面执行第一轮策略评估：基于初始化价值函数，将所有的状态对应的第一轮价值函数进行求解； 以0位置和5位置为例：
- 0位置(仅存在2个动作，该位置是充电桩)：
在计算0位置之前，没有计算任何关于“第一轮策略评估”其他状态的价值函数，此时状态价值函数没有任何变化，仍然是初始化状态；0位置策略 → \to → {“上”： 1 2 \frac{1}{2} 21，“右”： 1 2 \frac{1}{2} 21}，即： π ( a u p ∣ s 0 ) = π ( a r i g h t ∣ s 0 ) = 1 2 \pi(a_{up} \mid s_0) = \pi(a_{right} \mid s_0) = \frac{1}{2} π(aup∣s0)=π(aright∣s0)=21 对应下一状态奖励：{ s 5 s_5 s5: r 5 = 0 r_5=0 r5=0, s 1 s_1 s1: r 1 = 0 r_1=0 r1=0} 计算第一轮策略评估中0位置( s 0 s_0 s0)的状态价值函数 V k = 1 ( s 0 ) V_{k=1}(s_0) Vk=1(s0)： V k = 1 ( s 0 ) = π ( a u p ∣ s 0 ) p ( s 5 , r 5 ∣ s 0 , a u p ) [ r 5 + γ V i n i t ( s 5 ) ] + π ( a r i g h t ∣ s 0 ) p ( s 1 , r 1 ∣ s 0 , a r i g h t ) [ r 1 + γ V i n i t ( s 1 ) ] = 1 3 × 1 × [ 0 + 0.8 × 0 ] + 1 3 × 1 × [ 0 + 0.8 × 0 ] = 0 \begin{aligned} V_{k=1}(s_0) & = \pi(a_{up} \mid s_0)p(s_5,r_5 \mid s_0,a_{up})[r_5 + \gamma V_{init}(s_5)] + \pi(a_{right} \mid s_0)p(s_1,r_1 \mid s_0,a_{right})[r_1 + \gamma V_{init}(s_1)] \\ & = \frac{1}{3} \times 1 \times [0 + 0.8 \times 0] + \frac{1}{3} \times 1 \times [0 + 0.8 \times 0]\\ & = 0 \end{aligned} Vk=1(s0)=π(aup∣s0)p(s5,r5∣s0,aup)[r5+γVinit(s5)]+π(aright∣s0)p(s1,r1∣s0,aright)[r1+γVinit(s1)]=31×1×[0+0.8×0]+31×1×[0+0.8×0]=0 此时，我们计算出 V k = 1 ( s 0 ) = 0 V_{k=1}(s_0) = 0 Vk=1(s0)=0,将该结果对之前初始化的 V i n i t ( s ) V_{init}(s) Vinit(s)对应0位置进行更新；黄色背景即状态更新后的结果，即便数值没有发生变化，但该信息仍是更新后的信息。
- 5位置(仅存在3个动作，该位置临近充电桩)：
由于计算5位置之前，已经计算好了0位置的状态价值函数，并进行更新，因此我们在计算位置5的状态价值函数时，需要使用“更新后0位置”的价值函数信息。5位置策略 → \to → {“上”： 1 3 \frac{1}{3} 31，“下”： 1 3 \frac{1}{3} 31，“右”： 1 3 \frac{1}{3} 31}，即： π ( a u p ∣ s 5 ) = π ( a d o w n ∣ s 5 ) = π ( a r i g h t ∣ s 5 ) = 1 3 \pi(a_{up} \mid s_5) = \pi(a_{down} \mid s_5) = \pi(a_{right} \mid s_5) = \frac{1}{3} π(aup∣s5)=π(adown∣s5)=π(aright∣s5)=31 对应下一状态奖励：{ s 10 s_{10} s10: r 10 = 0 r_{10}=0 r10=0, s 0 s_0 s0: r 0 = 1 r_0=1 r0=1, s 6 s_6 s6: r 6 = 0 r_6=0 r6=0} 计算第一轮策略评估中5位置( s 5 s_5 s5)的状态价值函数 V k = 1 ( s 5 ) V_{k=1}(s_5) Vk=1(s5)： 再次强调： s 6 , s 10 s_6,s_{10} s6,s10是未被更新的状态，因此下面公式中使用 V i n i t ( s 6 ) , V i n i t ( s 10 ) V_{init}(s_6),V_{init}(s_{10}) Vinit(s6),Vinit(s10)；而 s 0 s_0 s0是已经在第一轮策略评估中已经求出并更新的状态，因此下面公式中使用 V k = 1 ( s 0 ) V_{k=1}(s_0) Vk=1(s0); V k = 1 ( s 5 ) = π ( a u p ∣ s 5 ) p ( s 10 , r 10 ∣ s 5 , a u p ) [ r 10 + γ V i n i t ( s 10 ) ] + π ( a d o w n ∣ s 5 ) p ( s 0 , r 0 ∣ s 5 , a d o w n ) [ r 0 + γ V k = 1 ( s 0 ) ] + π ( a r i g h t ∣ s 5 ) p ( s 6 , r 6 ∣ s 5 , a r i g h t ) [ r 6 + γ V i n i t ( s 6 ) ] = 1 3 × 1 × [ 0 + 0.8 × 0 ] + 1 3 × 1 × [ 1 + 0.8 × 0 ] + 1 3 × 1 × [ 0 + 0.8 × 0 ] = 1 3 ≈ 0.333 \begin{aligned} V_{k=1}(s_5) & = \pi(a_{up} \mid s_5)p(s_{10},r_{10} \mid s_5,a_{up})[r_{10} + \gamma V_{init}(s_{10})] + \pi(a_{down} \mid s_5)p(s_0,r_0 \mid s_5,a_{down})[r_0 + \gamma V_{k=1}(s_0)] + \pi(a_{right} \mid s_5)p(s_6,r_6 \mid s_5,a_{right})[r_6 + \gamma V_{init}(s_6)] \\ & = \frac{1}{3} \times 1 \times [0 + 0.8 \times 0] + \frac{1}{3} \times 1 \times [1 + 0.8 \times 0] + \frac{1}{3} \times 1 \times [0 + 0.8 \times 0]\\ & = \frac{1}{3} \approx0.333 \end{aligned} Vk=1(s5)=π(aup∣s5)p(s10,r10∣s5,aup)[r10+γVinit(s10)]+π(adown∣s5)p(s0,r0∣s5,adown)[r0+γVk=1(s0)]+π(aright∣s5)p(s6,r6∣s5,aright)[r6+γVinit(s6)]=31×1×[0+0.8×0]+31×1×[1+0.8×0]+31×1×[0+0.8×0]=31≈0.333 同0位置策略，我们计算出 V k = 1 ( s 5 ) = 0.333 V_{k=1}(s_5) = 0.333 Vk=1(s5)=0.333,将该结果对之前初始化的 V i n i t ( s ) V_{init}(s) Vinit(s)对应5位置进行更新；黄色背景即状态更新后的结果。
以此类推，我们最终可以将所有状态进行更新，更新结束后，我们的第一轮策略评估正式结束。结果如下(黄色背景略)：
0.009-0.127-0.727-0.2711.3920.024-0.486-2.597-2.2890.000.089-2.456障碍物-2.5970.2730.3330.133-2.456-0.486-0.1270.000.3330.0890.0240.009通过比对第一轮策略评估产生的价值函数和初始状态下价值函数的差距： 这个差距如何计算呢？ 以上述2轮策略评估的 V ( s ) V(s) V(s)向量结果 V i n i t ( s ) , V k = 1 ( s ) V_{init}(s),V_{k=1}(s) Vinit(s),Vk=1(s)为例：
- 将上述2个向量对应位置元素相减并取绝对值(或者取平方) → \to → 从结果向量中选择值最大的元素。
- 将上述步骤的结果与
θ
\theta
θ进行比较
→
\to
→ 若该值
<
θ
< \theta
关注打赏
1664446683
查看更多评论
最近更新
- 深拷贝和浅拷贝的区别（重点）
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state，props，refs（你学废了吗）
- 【脚手架VueCLI】从零开始，创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解（含代码）
- 【React】DOM的Diffing算法是什么？以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面？
