强化学习：动态规划（DP）

---

为什么可以使用动态规划解MDP问题？

动态规划能够解决的问题通常含有两个性质：
1） 拥有最优子结构：最优解可以分解为多个子问题。
2）含有重复子问题:子问题重复了很多次，其解可以存储下来重复利用。

马尔科夫决策过程满足上述两个性质：
1）贝尔曼方程给出了递归分解；
2）价值函数可以被存储及重复利用。

MDP使用DP时，需要知道全部的知识，也就是说模型 <S,A,P,R,γ> < S , A , P , R , γ > <script type="math/tex" id="MathJax-Element-1"></script>是已知的。如果求解最优策略 π∗ π ∗ <script type="math/tex" id="MathJax-Element-2">\pi_*</script>和最优价值函数 v∗ v ∗ <script type="math/tex" id="MathJax-Element-3">v_*</script>,则是控制问题；如果策略 π π <script type="math/tex" id="MathJax-Element-4">\pi</script>也已知求解最优值函数 v∗ v ∗ <script type="math/tex" id="MathJax-Element-5">v_*</script>则是预测问题。

策略迭代

策略评估

评估给定的策略 π π <script type="math/tex" id="MathJax-Element-6">\pi</script>

在一个MDP <S,A,P,R,γ> < S , A , P , R , γ > <script type="math/tex" id="MathJax-Element-7"></script>问题中，当策略 π π <script type="math/tex" id="MathJax-Element-8">\pi</script>是已知的时候，我们有：

<script type="math/tex; mode=display" id="MathJax-Element-9"> v_{\pi}(s) = \sum_{a\in A} \pi(a|s) \left( R_s^a + \gamma \sum_{s'\in S}P_{ss'}^a v_{\pi}(s')\right) </script>

在上述方程中， Pass′,γ,Ras,π(a|s) P s s ′ a , γ , R s a , π ( a | s ) <script type="math/tex" id="MathJax-Element-10">P_{ss'}^a,\gamma, R_s^a,\pi(a | s)</script>均是已知的，需要求解的是 vπ(s) v π ( s ) <script type="math/tex" id="MathJax-Element-11">v_{\pi}(s)</script>。对于每一个状态 s s <script type="math/tex" id="MathJax-Element-12">s</script>,我们均可以得到一个这样的方程。因此，我们就可以获得n $n$<script type="math/tex" id="MathJax-Element-13">n</script>个(状态的个数)方程构成的线性方程组。当问题规模较小时，可以使用闭式解直接求得价值函数的值；当问题规模较大时，需要使用迭代的方法来求得解。此处使用高斯-赛德尔迭代算法来进行求解。

<script type="math/tex; mode=display" id="MathJax-Element-14"> v_{k+1}(s) = \sum_{a\in A} \pi(a|s) \left( R_s^a + \gamma \sum_{s'\in S}P_{ss'}^a v_{k}(s')\right) \\ {\bf v}^{k+1} = {\bf R^{\pi}} + \gamma {\bf P^{\pi} v}^k </script>

————————————————–伪——码————————————————————

v(1) = 0;
while 1
    for 1 : n
      v(k+1) = f(v(k));
    endfor
    if |v(k+1) - v(k)| < err
        break;
    endif
endwhile     

————————————————–伪——码————————————————————

策略改进

求解最优策略
已知当前策略的价值函数时，如何改进策略从而获得最优策略。可以使用贪婪策略获取一个比当前策略要好的策略：

<script type="math/tex; mode=display" id="MathJax-Element-15">\pi_{l+1}(s) = \underset{a \in A}{\arg \max} \ \ q^{\pi_l}(s,a) </script>

针对每一个状态，求取全部可能的策略所对应的行为价值函数值，取其最大值所对应的策略为新确定的“策略”中的一部分。

策略迭代算法

策略迭代算法包括策略评估和策略改进两个步骤。在策略评估中，给定策略，通过数值迭代算法不断计算该策略下每个状态的值函数，利用该值函数和贪婪策略得到新的策略。如此循环下去，最终得到最优策略。这是一个策略收敛的过程。

————————————————–伪——码————————————————————

v(1) = 0; 
pi(1) = random();
Repeat l = 0,1,...
    寻找当前策略下最好的V(l);
    贪婪地更新策略 pi(l+1)
until pi(l+1) = pi(l)

————————————————–伪——码————————————————————

价值迭代算法

在策略评估过程中，并不需要等到策略评估收敛之后才能进行策略改进。如果在进行一次评估之后就进行策略改善，则称为值函数迭代算法。值函数迭代是动态规划算法最一般的计算框架。
最优性原理

任何最优的策略都可以被分解为两部分：
一次最优的行为 A∗ A ∗ <script type="math/tex" id="MathJax-Element-16">A_*</script>;
后续状态 S‘ S ‘ <script type="math/tex" id="MathJax-Element-17">S‘</script>的一个最优策略。

v∗(s)=maxa∈ARas+γ∑s′∈SPass′v∗(s′) v ∗ ( s ) = max a ∈ A R s a + γ ∑ s ′ ∈ S P s s ′ a v ∗ ( s ′ )

<script type="math/tex; mode=display" id="MathJax-Element-18">v_*(s) =\underset{a \in A} \max R_s^a + \gamma \sum_{s'\in S}P_{ss'}^av_*(s')</script>

<script type="math/tex; mode=display" id="MathJax-Element-19"> v_{k+1}(s) = \underset{a \in A} \max \left( R_s^a + \gamma \sum_{s'\in S}P_{ss'}^a v_{k}(s')\right) \\ {\bf v}^{k+1} =\underset{a \in A} \max {\bf R^{a}} + \gamma {\bf P^{a} v}^k </script>

————————————————–伪——码————————————————————

v(1) = 0; 
pi(1) = random();
Repeat l = 0,1,...
     for every s do
       值函数迭代公式；    
until v(l+1) = v(l)

————————————————–伪——码————————————————————
需要注意的是在每次迭代过程，需要对状态空间进行一次扫描，同时在每个状态对动作空间进行扫描以便得到贪婪的策略。

References

[1] 动态规划
[2] 强化学习入门 第二讲 基于模型的动态规划方法