1. 1 同步价值迭代

动态规划来解决强化学习的规划问题。
在已经了解了状态、行为空间、转移概率矩阵、奖励等信息的基础上，判断一个策略的价值函数。或者判断策略的优劣寻找最优的策略。
一般强化学习是不知道上述的一些动力学环境，而且复杂的问题无法通过动态规划解决。

动态规划思想是把复杂问题变成求解子问题，最终再得到整个问题。子问题的结果一般需要保存以备后用。如果某个子问题重复出现，就可以重复使用结果。

马尔科夫决策过程最终用贝尔曼方程描述，贝尔曼方程是递归定义的。可以使用动态规划求解。

1.1. 概念：

预测prediction：已知MDP和一个策略$\pi$π，或者MRP，求解该策略的价值函数$v_\pi$vπ​。
控制control:已知MDP，求最优的价值函数$v_*$v∗​和$\pi_*$π∗​，为了寻找最优策略

1.2. 预测

1.2.1. 策略评估

Policy evaluation 给定策略，求这个策略下状态价值函数。

方法：同步迭代联合动态规划的算法

任意的状态价值函数开始，按照给定策略，通过贝尔曼方程、状态转移概率、奖励，同步迭代更新状态价值函数，到收敛为止。就可以得到这个策略的最优状态价值函数。
重点：在一个迭代周期如何更新每一个状态的价值
这个算法一定可以收敛形成一个稳定的价值函数。证明设置矩阵压缩映射理论。

回顾贝尔曼方程，计算当前状态的v需要后续的状态的v。
在同步迭代算法中，使用上一个周期k内的后续状态s的价值，来更新当前周期k+1的状态s价值。

$v_{k+1}(s) = \sum_{\alpha \in A}\pi (a|s)(R^a_s + \gamma \sum_{s' \in S}P_{ss'}^a v_{k}(s'))$vk+1​(s)=α∈A∑​π(a∣s)(Rsa​+γs′∈S∑​Pss′a​vk​(s′))

Notation:
v的下标代表第k代。v(s)代表s状态的价值函数
P的下标是s->s’的转移概率。a代表某个动作。

1.2.1.1. 例

• $\gamma$γ=1
• 状态1-14，两个灰色的是终止状态
• 不能走出边界，也不能斜着走
• 随机扔到一个格子，采用最少的步骤到达两个灰色的格子中，所以每一步的奖励设置-1，终止状态奖励0
• 采用均已随机策略，每个方向都是1/4
• 假设初始状态价值都为0

迭代结果：

可以看到，每次迭代都通过不断尝试，所有计算状态价值，最终会得到这个策略下的所有状态价值函数。

1.3. 策略的迭代

策略评估之后，我们得到的是在这个策略下每一个状态的价值。
不同的状态对应的价值一般都不同。
如果在每个状态下的行为选择都选择能够到达状态价值最大的行为，就能够得到较好的表现。这是一种贪婪策略的思想。

例如，通过第二次迭代后，根据迭代的结果改变策略(通过第一次迭代的结果进行选择，而不是上下左右动作都是1/4的可能性)，进行下一次策略评估。

右侧的策略明显是改变了。显然我们得到了更高效的策略。

一般地，给定一个策略，针对该策略进行完整的评价得到价值函数$v_\pi$vπ​，根据价值函数得到一个贪婪策略$\pi' = greedy(v_{\pi})$π′=greedy(vπ​)。反复进行，直到收敛。

1.4. 价值迭代

之前所说的饿都是先对策略进行完整的评价，然后再进行策略的迭代（上面采用的是贪婪策略）。不进行完整的迭代，指迭代几步之后提前终止，然后就改变策略是否可以呢？
最优策略的理解：

• 对当前状态s下能够产生最优行为
• s下的最行为的后续状态时，该状态也是最优状态。
  反向来说，一个策略不能在当前状态下产生最优行为，或者这个策略针对后续状态不能产生最优行为，那么一定不是最优策略。必须同时保证。

根据上面的原则，我们可以发现：
如果我们知道了s’的最优价值函数，那么s的最优价值函数$v_*(s)$v∗​(s)就可以通过向后看一下$v_*(s')$v∗​(s′)得到。

$v_*(s) \leftarrow max_{a \in A} R^a_s + \gamma \sum_{s' \in S}P^a_{ss'}v_*(s')$v∗​(s)←maxa∈A​Rsa​+γs′∈S∑​Pss′a​v∗​(s′)

价值迭代就是用这样思想进行更新。直觉上来讲，就是从最后的奖励开始并且从后往前进行
就算不知道最终状态，也可以使用上述公式不断迭代，不停更新，最终就会得到最优价值。

1.4.1.1. 例

只有左上角一个终止状态。

• 情形1：知道环境
  知道环境意味着知道最终状态的位置。那么左上角的两个状态分别为-1，接着往下延伸。利用上述价值迭代公式

• 情形二：不知道环境特征。即不知道最终状态在哪里，对于系统一开始来说，任何一个状态都有可能是最终得状态。
  这就需要需要agent对所有状态都进行价值更新。
  • 随机初始化所有的状态价值（V1），这里初始为0
  • 下一次迭对于没有终止的状态，任何的动作都将会得到一个-1的reward，从而得到V2
  • 再一次迭代，除了左上的两个已经得到了最优状态价值，因为他们的后续为终点0，其余的都需要进行一次迭代，得到-1的奖励，到达V3
  • 左上角的-2是最优的状态价值函数，因为后续状态-1和0都是最优。其余的需要继续迭代。
    

价值迭代的最终目标也是找到一个最优策略。它的基础迭代公式是通过贝尔曼最优方程(里面把行为价值函数替换成下一个状态的价值函数了)。
整个过程没有策略的参与。但是每一步的迭代都相当于贪婪算法选择了最优的。相当于策略迭代中迭代一次价值函数就更新一次策略。

1.5. 总结

这三个算法都是基于价值函数的。每一次迭代的时间复杂度$O(mn^2)$O(mn2)，m个动作，n个状态。
也可基于行为价值函数$q_\pi(s,a)$qπ​(s,a)或者最优行为价值函数来推导，那么每次迭代的复杂度是$O(m^2n^2)$O(m2n2)

2. 异步迭代过程

上面的算法中，在每次迭代中所有的状态都会得到更新，即状态之间是同步更新。是同步动态规划算法。
如果每一次迭代中，按照某个规则更新部分的状态值，显然可以减少每次迭代的计算量。从而提高计算效率。
但要保证所有的状态能够持续的被读取。

2.1. 对于异步动态更新的三个方法：

• In-place dynamic programming 原位动态规划
  同步价值迭代会存储价值函数的两个副本，用老的去更新新的。
  
  In-place 价值迭代只存储一个价值函数的副本。直接用后续的状态的价值去更新当前的状态的价值。
  

• Prioritised sweeping 优先级动态规划
  一种实现方法是根据贝尔曼方程的误差大小，来对每个状态的优先级进行排序，误差越大的越先得到更新。可以通过维护一个优先级队列来实现。
  例如使用如下的误差来决定状态的更新：
  

• Real-time dynamic programming 实时动态规划
  idea：只考虑和代理(agent)相关的状态。比如经常访问的状态将会得到较多次数的更新，不经常访问、关联较少的得到的更新次数也较少。

2.2. Full-width Backup 全宽度回溯机制

全宽度回溯机制是指：不论是同步还是非同步动态规划，在更新某个状态的价值函数时，后续所有的状态和动作都需要被考虑。
决策过程对于中等规模的问题(百万个状态)是有效的。
但是对于大规模问题，决策过程DP受到贝尔曼方程维数的限制，复杂度$O(mn^2)$O(mn2)，状态数量n二次方上升，每一次回溯都需要太昂贵的代价了。

如何解决大规模维度的问题，就需要后续的一些算法了~