[RL Notes] 策略迭代
由策略改进定理,对于给定策略 π,在每一个状态都根据价值函数 vπ 贪心的选择动作,就可以得到一个更优的策略 π′
π′(s)≐argmaxa∑s′,rp(s′,r|s,a)[r+γvπ(s′)]
然后计算 π′ 的价值函数 vπ′,通过相同的方式就可以找到一个新的更优的策略 π′′。不断地对价值函数进行评估(evaluation),并对策略进行改进(improvement),得到一个不断改进的策略和价值函数序列
π0E→vπ0I→π1E→vπ1I→π2E→⋯I→π∗E→vπ∗
在上面的序列中,每一个策略都严格优于上一个策略,除非上一个策略已经最优。有限 MDP 只有有限种策略,故在有限次迭代后,上面的序列一定收敛到一个最优策略和最优价值函数。
上面这种寻找最优策略的方法称为策略迭代,其完整版本如下所示。
策略迭代(使用迭代策略评估),用于估计 π≈π∗
-
初始化
对 s∈S,任意设定 V(s)∈R 以及 π(s)∈A(s) -
策略评估
循环:
Δ←0
对每一个 s∈S 循环:
v←V(s)
V(s)←∑s′,rp(s′,r|s,π(s))[r+γV(s′)]
Δ←max(Δ,|v–V(s)|)
直到 Δ<θ(一个决定估计精度的小正数) -
策略改进
policy-stable←true
对每一个 s∈S:
old-action←π(s)
π(s)←argmaxa∑s′,rp(s′,r|s,a)[r+γV(s′)]
如果 old-action≠π(s),那么 policy-stable←false
如果 policy-stable 为 true,那么停止并返回 V≈v∗ 以及 π≈π∗;否则跳转到 2。