动态规划基础介绍
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
- 大致上，若要解一个给定问题，我们需要将其分解为不同部分（即子问题），再根据子问题的解以得出原问题的解。Optimal solution can be decomposed into subproblems
- 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。Subproblems recur many times; Solutions can be cached and reused
MDP问题分类
预测(prediction)：给定MDP和策略，或者给定一个MRP，求出基于该策略的价值函数
- 输入： MDP $
- 输出：值函数 $v_{\pi}$。
- 输入： MDP $
控制(control)：给定一个MDP，求出最优价值函数和最优策略。
- 输入： MDP $
- 输出：最优值函数$v{*}$以及最优策略$\pi{*}$
- 输入： MDP $
强化学习的核心思想是使用值函数$v(s)$或者动作值函数$q(s,a)$，找到更优的策略给智能体进行决策使用。由上一篇文章的内容可知，当找到最优的状态值函数$v(s)$或者最优的动作值函数$q(s,a)$，就可以找到最优策略$\pi$，公式如下:
其中状态$s \in S$、动作$a \in A$、新的状态$s’ \in S^+$。上面两式中：最优价值为环境中的每一个状态$s$和动作$a$对应的动作转换概率$p(s’,r|s,a)$乘以未来折扣奖励中最大的价值$[r+\gamma \max_{a’}value(s’,a’)]$。其中$value(s’,a’)$为价值函数，可以为$v^(s’)$或者为$q^(s’,a’)$。
动态规划法主要是将上式中的贝尔曼方程转换为赋值操作，通过更新价值来模拟价值更新函数。
迭代策略评估(Iterative Policy Evaluation)
目标：predict——求出价值函数
评估一个给定策略$\pi$，求对应的值函数$v{\pi}(s)$或者$q{\pi}(s,a)$，即解决预测（Prediction）问题。
- 同步迭代：反向迭代，在每次迭代过程中，
- 在第k+1次迭代，
- 对每一个状态s属于S，
- 所有的状态s的价值用$vk(s’)$ 来计算，并且更新$v{k+1}(s’)$的值。
- 其中s’为s的后继。
该方法最终能收敛到该MDP下对应策略的value function
- 异步迭代：在第k次迭代使用档次迭代的状态价值来更新状态价值
改善：在每一次迭代之后，马上根据迭代得到的价值函数贪婪地更新我们的策略。虽然不一定一次就能得到最好的策略，但是最终能够收敛到最佳策略。
Grid World:
评估在这个方格世界里给定的策略。即求解该方格世界在给定策略下的（状态）价值函数，也就是求解在给定策略下，该方格世界里每一个状态的价值。
策略迭代（Policy Iteration）
目标：control——求出最优策略
当前策略上迭代计算价值函数，再根据价值函数贪婪地更新策略。如此反复多次，最终得到最优策略和最优状态价值函数。（贪婪指总是采取使得状态价值最大的行为；其实不一定每次都要更新策略，也可以等迭代到一定次数之后再更新，不过这样可能会影响收敛速度）
改善：不一定每次都要把最优价值函数迭代出来，最优策略会更早的迭代出来。所以可以设置一个$\epsilon$来比较两次迭代的价值函数平方差，或者设置最大迭代次数，或者每次迭代更新策略。
分为以下2个步骤
- 策略评估（Policy evaluation）：根据策略$\pi$迭代式地计算值函数$v_{\pi}$。
- 策略改进（Policy improvement）：使用贪婪策略不断提升策略，使得$\pi’ \ge \pi$。
细节描述：
a、我们随机初始化一个值$V$以及策略$\pi$
b、通过策略评估求得当前策略下的值函数$V=V^{\pi}$
c、使用贪婪策略提升策略，$\pi=greedy(v_{\pi})$
d、基于新的策略$\pi$计算值函数$V=V^{\pi}$，使得$V$函数与新策略一致
如果评价过程和提升过程都稳定下来，即不再发生变化，那么值函数和策略必须都是最优的。这意味着贝尔曼最优方程成立。 还可以用两个目标来考虑GPI中评价和提升过程的相互作用，如上图所示，上面的线代代表目标 v = v π ，下面的线代表目标$\pi=greedy(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辆车，那么这一天的租收行为$A{rent,return}$可以是： $$ A{rent,return}= \begin{bmatrix} 10 & 0 \ , 11 & 1, \ 12 & 2, \ … & … \ 20 & 10 \end{bmatrix} $$ Rent与Return是相互独立的事件且皆服从泊松分布，所以要计算某个行为出现的概率直接将$P(A{rent})$与$P(A{return})$相乘。
但这里要计算的是条件概率，即为$P(A_{rent,return}|S’’=0)$，所以还需要再与傍晚清点时还剩0辆车的概率$P(S’’=0)$相除。
各个租收行为所获得的收益是以租出去的车辆数为准，所以当傍晚还剩0辆车时，这一天的收益期望可以写为： 其中，$P(S’’=0)$也可以写为： 在计算出矩阵$R(S’=10|S’’=0,1,2,…20)$后，再进行加权平均，即可得到状态“1号租车点有10辆车”的奖励期望$R(S’=10)$: 两个租车点，所有的状态按上述方法计算后，即可得出两个租车点的奖励矩阵$|R_1(S’),R_2(S’)|$。
在计算出奖励矩阵后，这个问题就变成了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)这三个算法都是基于状态值函数$v{\pi}(s)$或者$v{*}(s)$
- 如果动作数量为$m$，状态数量为$n$，那么每次迭代的计算复杂度为$O(mn^2)$。
- 这三个算法也同样可以应用到动作值函数$q{\pi}(s,a)$或者$q{*}(s,a)$，同时每次迭代的计算复杂度为$O(m^2n^2)$。
About this Post
This post is written by Rui Xu, licensed under CC BY-NC 4.0.