动态规划基础介绍
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
- 大致上，若要解一个给定问题，我们需要将其分解为不同部分（即子问题），再根据子问题的解以得出原问题的解。Optimal solution can be decomposed into subproblems
- 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。Subproblems recur many times; Solutions can be cached and reused
MDP问题分类
预测(prediction)：给定MDP和策略，或者给定一个MRP，求出基于该策略的价值函数
- 输入： MDP
以及策略 。或者MRP 。 - 输出：值函数
。
- 输入： MDP
控制(control)：给定一个MDP，求出最优价值函数和最优策略。
- 输入： MDP
- 输出：最优值函数$v_{}
\pi_{}$
- 输入： MDP
强化学习的核心思想是使用值函数
其中状态
动态规划法主要是将上式中的贝尔曼方程转换为赋值操作，通过更新价值来模拟价值更新函数。
迭代策略评估(Iterative Policy Evaluation)
目标：predict——求出价值函数
评估一个给定策略
- 同步迭代：反向迭代，在每次迭代过程中，
- 在第k+1次迭代，
- 对每一个状态s属于S，
- 所有的状态s的价值用
来计算，并且更新 的值。 - 其中s’为s的后继。
该方法最终能收敛到该MDP下对应策略的value function
- 异步迭代：在第k次迭代使用档次迭代的状态价值来更新状态价值
改善：在每一次迭代之后，马上根据迭代得到的价值函数贪婪地更新我们的策略。虽然不一定一次就能得到最好的策略，但是最终能够收敛到最佳策略。
Grid World:
评估在这个方格世界里给定的策略。即求解该方格世界在给定策略下的（状态）价值函数，也就是求解在给定策略下，该方格世界里每一个状态的价值。
# 策略迭代（Policy Iteration）
目标：control——求出最优策略
当前策略上迭代计算价值函数，再根据价值函数贪婪地更新策略。如此反复多次，最终得到最优策略和最优状态价值函数。（贪婪指总是采取使得状态价值最大的行为；其实不一定每次都要更新策略，也可以等迭代到一定次数之后再更新，不过这样可能会影响收敛速度）
改善：不一定每次都要把最优价值函数迭代出来，最优策略会更早的迭代出来。所以可以设置一个
分为以下2个步骤
- 策略评估（Policy evaluation）：根据策略
迭代式地计算值函数 。 - 策略改进（Policy improvement）：使用贪婪策略不断提升策略，使得
。
细节描述：
a、我们随机初始化一个值$V$以及策略$\pi$
b、通过策略评估求得当前策略下的值函数$V=V^{\pi}$
c、使用贪婪策略提升策略，$\pi=greedy(v_{\pi})$
d、基于新的策略$\pi$计算值函数$V=V^{\pi}$，使得$V$函数与新策略一致
如果评价过程和提升过程都稳定下来，即不再发生变化，那么值函数和策略必须都是最优的。这意味着贝尔曼最优方程成立。
从一个策略
Jack’s Car Rental
1号租车点有10辆车”收益分析：
考虑状态“1号租车点有10辆车”的未来可能获得收益，需要分析在保有10辆车的情况下的租车（Rent）与回收（Return）的行为。计算该状态收益的过程实际上是，另外一个动作策略符合泊松分布的马尔可夫决策过程。
将1天内可能发生的Rent与Return行为记录为[#Rent, #Return]，其中“#Rent”表示一天内租出的车辆数，“#Return”表示一天内回收的车辆数，设定这两个指标皆不能超过20。
假设早上，1号租车点里有10辆车，那么在傍晚清点的时候，可能保有的车辆数为0~20辆。如果傍晚关门歇业时还剩0辆车，那么这一天的租收行为
但这里要计算的是条件概率，即为
各个租收行为所获得的收益是以租出去的车辆数为准，所以当傍晚还剩0辆车时，这一天的收益期望可以写为：
在计算出奖励矩阵后，这个问题就变成了bandit问题的变种，bandit问题是一个动作固定对应一个未来的状态，而这里虽然也是这样，不过所对应的状态却要以当前状态为基础进行计算得出，还是有些不同，所以称为bandit问题的一个变种。
# 价值迭代(Value Iteration)
目标：control——求出最优策略
一个最优策略可以分解为两部分
- 从状态s到下一个状态s’时采取了最优行为A
- 在s’时遵循最优策略。所以有以下定理：一个策略能够使得状态s获得最优价值，当且仅当：对于从状态s可以到达的任何状态s’，该策略能够使得状态s’的价值是最优价值。
Value Iteration：从初始状态价值开始同步迭代计算，最终收敛，整个过程中没有遵循任何策略。根据每一个状态的最优后续状态价值来更新该状态的最佳状态价值。在value iteration时候，算法不会给出明确的策略，迭代过程期间得到的价值函数，不对应任何策略。
5、策略评估（Policy Evaluation）、策略迭代(Policy Iteration)以及值迭代(Value Iteration)总结
这三个算法通过一张表可以总结如下：
| 问题（Problem） | 应用的贝尔曼方程 （Bellman Equation） | 使用到的算法（Algorithm） |
|---|---|---|
| 预测(Prediction） | 贝尔曼期望方程（Bellman Expectation Equation） | 迭代式策略评估（Iterative Policy Evaluation） |
| 控制（Control） | 贝尔曼期望方程（Bellman Expectation Equation）+ 贪婪策略改进（Greedy Policy Improvement） | 策略迭代(Policy Iteration) |
| 控制（Control） | 贝尔曼最优方程（Bellman Optimality Equation） | 值迭代(Value Iteration) |
- 策略评估（Policy Evaluation）、策略迭代(Policy Iteration)以及值迭代(Value Iteration)这三个算法都是基于状态值函数
或者 - 如果动作数量为
，状态数量为 ，那么每次迭代的计算复杂度为 。 - 这三个算法也同样可以应用到动作值函数
或者 ，同时每次迭代的计算复杂度为 。
About this Post
This post is written by Rui Xu, licensed under CC BY-NC 4.0.