动态规划求解强化学习任务——价值迭代

目录

前面部分介绍了策略改进定理的理论推导和策略迭代求解策略 π \pi π的具体算法过程，本节将介绍动态规划求解强化学习任务最后一个模块——价值迭代。

回顾 - 策略迭代

在整体介绍中介绍了策略迭代共包含2个步骤：

• 策略评估(Policy Iteration) 给定一个策略 π \pi π,求出它的最优价值函数 V π ( s ) V_\pi(s) Vπ​(s)；
• 策略改进(Policy Improvement) 基于策略评估给出的 V π ( s ) → V_\pi(s) \to Vπ​(s)→ 使用贪心策略，获取收益最大的动作作为新的策略 π ( s ) \pi(s) π(s)

重复执行策略评估和策略改进，直到获取最优策略 π \pi π，迭代结束。

策略迭代缺陷

在整个迭代过程中，策略评估(迭代解) 本身就是一个迭代过程，即便使用了策略改进定理优化了计算最优价值函数的过程，但仍改变不了其循环嵌套循环的本质。 为了优化掉这个嵌套循环的过程，我们将介绍价值迭代。

价值迭代 价值迭代介绍

针对策略迭代中策略评估过程中的缺陷，思考如何优化策略评估步骤； 首先回顾策略评估的算法过程：

输入初始策略： π ( 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′,r​p(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 δ