动态规划（Dynamic Programming，DP）是一类优化方法，在给定一个用马尔可夫决策过程（MDP）描述的完备环境模型的情况下，其可以计算最优的策略。

我们假设环境是一个有限MDP。我们假设状态集合S、动作A和收益集合R是有限的，并且整个系统的动态特性由对于任意$s\in S、a\in A(s)、r\in R和s^{\prime }\in S+$（S+表示在分幕式任务下S加上一个终止状态）的四参数概率分布$p(s^{\prime },r|s,a)$给出。尽管DP的思想也可以用在具有连续状态和动作的问题上，但是只有在某些特殊情况下才会存在精确解。一种常见的近似方法是将连续的状态和动作量化为离散集合，然后在使用有限状态下的DP算法。

DP的核心思想是使用价值函数来结构化地组织对最优策略的搜索。一旦我们得到了满足贝尔曼最优方程的价值函数v或q，得到最优策略就很容易了。对于任意$s\in S、a\in A(s)$和$s^{\prime }\in S+$，有

由上可见，通过将贝尔曼方程转化成为近似逼近理想价值函数的递归更新公式，就得到了DP算法。

策略评估（预测）

策略是根据环境反馈的当前状态，决定智能体采取何种行动的指导方法。策略评估通过计算与策略对应的状态值函数，以评估该策略的优劣。即给定一个策略，计算基于该策略下的每个状态的状态值的期望，并用该策略下的最终状态值的期望评价该策略。

策略评估通过迭代计算贝尔曼方程，以获得对应的状态值函数，进而利用该状态值函数评估该策略是否最优。
例如对于任意s∈S，有

其中π(a|s)指的是处于环境状态s时，智能体在策略π下采用动作a的概率。实际上我们可以使用迭代的方法来找到最优策略。初始的近似值V0可以任意选取。然后下一轮迭代的近似使用Vπ的贝尔曼方程进行更新，则有对于任意s∈S

比如一个4x4网格图

非终止状态集合$S=1,2,...,14$。每个状态有四种可能的动作， A = { u p , d o w n , r i g h t , l e f t } A=\{up,down,right,left\} A={up,down,right,left}。每个动作会导致状态转移，当动作导致智能体移出网格时，状态不变。比如，$p(6,-1|5,right)=1，p(7,-1|7,right)=1$和对于任意r∈R，都有$p(10,r|5,right)=0$。这是一个无折扣的分幕式任务。在到达终止状态之前，所有动作的收益均为-1。终止状态在图中以阴影显示。对于所有的状态s、s’与动作a，期望的收益函数均为$r(s,a,s^{\prime })=-1$。假设智能体采取等概率随机策略。

策略改进

如何对比两个策略的好坏？如果π和π‘是两个确定的策略，对任意s∈S，有：

那么我们称π‘比π好，其中q是期望，v为价值。将上式展开。

上式说明，如果策略的期望越高，那么策略的价值越大。所以可以在每个状态下根据$q_{\pi }(s,a)$选择一个最优的。假设一个新的贪心策略$\pi$’，满足

这里$argma{x}_a$表示能够使得表达式的值最大化的$a$。这个贪心策略采取在短期内看上去最优的动作，即根据$v_{\pi }$向前单步探索。这样构造出的贪心策略满足策略改进定理的条件。这种根据原策略的价值函数执行贪心算法，来构造一个更好策略的过程，称为策略改进。
假设新的贪心策略${\pi }^{\prime }$和原有的策略$\pi$，一样好，但不是更好，那么一定有$v_{\pi }=v_{{\pi }^{\prime }}$。则对于任意$s\in S$，有

这与贝尔曼最优方程一致，说明$v_{{\pi }^{\prime }}=v_{\ast }$，所以进一步说明了如果$v_{\pi }=v_{{\pi }^{\prime }}$，则$v_{{\pi }^{\prime }}(s)=v_{\ast }(s)$，换言之，如果存在一个新的策略与老的策略的价值相等，则这两个策略肯定是最优策略，否则，使用策略改进的方法可以得到一个更优的策略。

策略迭代

一旦一个策略$\pi$根据$v_{\pi }$产生一个更好的策略${\pi }^{\prime }$，我们就可以通过计算$v_{{\pi }^{\prime }}$，来得到${\pi }^{\prime \prime }$。这样一个链式的方法可以得到一个不断改进的策略和价值函数序列。

${\to }^E$代表策略评估，${\to }^I$表示策略改进。每一个策略都能保证比前一个更优（除非前一个已经是最优的）。由于一个有限MDP必然只有有限种策略，所以在有限次的迭代后，这种方法一定收敛到一个最优的策略与最优价值函数。这种寻找最优策略的方法叫策略迭代。
每一次策略评估都是一个迭代计算过程，需要基于前一个策略的价值函数开始计算。这通常会使得策略改进的收敛速度大大提高。策略迭代令人惊讶的是，它在几次迭代中就能收敛。

策略迭代 - 杰克租车问题

问题描述
假设Jack管理者一家租车公司，一共有两个租车点，每租出一部车，Jack可以赚10元，为了提高车子的出租率，Jack要在夜间调配车辆，也就是把车子从一个租车点调配到另一个租车点，成本是2元/辆。每个场地每天租车和还车的数量服从泊松随机分布，即其为$n$的概率为$\frac{{\lambda }^n}{n!}{e}^{-\lambda }$，$\lambda$是期望，租车点A和B的$\lambda$分别为3和4，还车的λ分别为3和2。问题进一步简化为，每个租车点最多可停20部车，超出的车辆会被认为报销。每个租车点最多调配5部车子。
问：Jack在每个场地应该部署多少部车子？每天晚上如何调配？

问题分析
（1）每个租车点最多可以停20辆车，则两个租车点可能出现的状态$21\ast 21=441$种，
（2）最多调配5辆车，即动作集合为：A={(-5,5),(-4,4),(-3,3),(-2,2),(-1,1),(0,0),(1,-1),(2,-2),(3,-3),(4,-4),(5,-5)}。每个元组两个元素分别代表A，B两个租车点的调配数量，正代表调入，负代表调出。
如下图的伪代码所示

from matplotlib import pyplot as plt
import numpy as np
from matplotlib import animation
from scipy.stats import poisson  # 统计学的包，用于生成泊松分布

plt.rcParams['font.sans-serif'] = ['SimHei']  # 正确显示中文
plt.rcParams['axes.unicode_minus'] = False  # 正确显示正负号


#初始化
poisson_cache = dict()
x = np.arange(0, 21)
y = np.arange(0, 21)
x, y = np.meshgrid(x, y)

value = np.zeros((21, 21))
policy = np.zeros(value.shape, dtype=np.int)  # 存储策略【0，1，2……20】

fig = plt.figure(figsize=(20, 10))

ax1 = fig.add_subplot(1, 2, 1, projection='3d')
ax2 = fig.add_subplot(1, 2, 2, projection='3d')

def init():                                     # 画布坐标轴范围初始化

    ax1.set_xlim([0, 20])
    ax1.set_ylim([0, 20])
    ax1.set_zlim([-6, 6])

    ax1.set_xlabel("场地A的车辆状态")
    ax1.set_ylabel("场地B的车辆状态")
    ax1.set_zlabel("决策中的动作分布")

    ax2.set_xlim([0, 20])
    ax2.set_ylim([0, 20])
    ax2.set_zlim([0, 1000])

    ax2.set_xlabel("场地A的车辆状态")
    ax2.set_ylabel("场地B的车辆状态")
    ax2.set_xlabel("场地A的车辆状态")
    ax2.set_ylabel("场地B的车辆状态")
    ax2.set_zlabel("决策中各动作的价值")

    plt.tight_layout()
    return ax1, ax2,

def poisson_probability(n, lam):
    """
    输出n个车辆在参数为lam下的泊松分布概率
    @n: 车辆数
    @lam: 期望值
    """
    global poisson_cache
    key = n * 10 + lam  # 给每个状态设置一个标签，防止出现重叠
    # 例如，第二个地点借车期望为4，还车期望为2，如果直接用n+λ表示，“还2辆车”“借0辆车”时间重合了。
    if key not in poisson_cache:
        poisson_cache[key] = poisson.pmf(n, lam)  # 储存n个车辆，发生的概率
    return poisson_cache[key]


def expected_return(state, action, state_value):
    """
    函数功能【策略评估】：在某一个状态下，根据一个策略，估计新的状态价值。
    @state：一个数组，state[0]存储A场地的车辆数；state[1]存储B场地的车辆数
    @action：动作
    @state_value:状态价值矩阵
    """
    returns = 0.0  # 初始化
    # step1  减去移车费
    returns -= 2 * abs(action)
    # 遍历所有可能的租车请求
    for rental_request_first_loc in range(10):
        for rental_request_second_loc in range(10):
            p1 = poisson_probability(rental_request_first_loc, 3)
            p2 = poisson_probability(rental_request_second_loc, 4)
            prob = p1 * p2  # 当前租车请求发生的概率
            # 更新状态——晚上运完以后的车辆状态
            num_of_cars_first_loc = min(state[0] - action, 20)
            num_of_cars_second_loc = min(state[1] + action, 20)
            # 有效租车数量     min（已有车辆和租车数量）
            valid_rental_first_loc = min(num_of_cars_first_loc, rental_request_first_loc)
            valid_rental_second_loc = min(num_of_cars_second_loc, rental_request_second_loc)
            # 获取盈利值
            reward = (valid_rental_first_loc + valid_rental_second_loc) * 10
            # 更新状态——减去租出去的车数量
            num_of_cars_first_loc -= valid_rental_first_loc
            num_of_cars_second_loc -= valid_rental_second_loc
            returned_cars_first_loc = 3
            returned_cars_second_loc = 2
            num_of_cars_first_loc = min(num_of_cars_first_loc + returned_cars_first_loc, 20)
            num_of_cars_second_loc = min(num_of_cars_second_loc + returned_cars_second_loc, 20)
            returns += prob * (reward + 0.9 * state_value[num_of_cars_first_loc, num_of_cars_second_loc])

    return returns


def optimize_action(value, policy, iterations):  # 策略优化过程
    actions = np.arange(-5, 6)
    while True:
        old_value = value.copy()
        for i in range(21):
            for j in range(21):
                value[i, j] = expected_return([i, j], policy[i, j], value)  # 状态、动作、价值————》新的状态价值
        max_value_change = abs(old_value - value).max()
        print('状态价值变化中的最大值为 {}'.format(max_value_change))
        if max_value_change < 1:
            break
    policy_stable = True
    for i in range(21):
        for j in range(21):
            old_action = policy[i, j]
            action_returns = []
            for action in actions:
                if (0 <= action <= i) or (-j <= action <= 0):
                    action_returns.append(expected_return([i, j], action, value))
                else:
                    action_returns.append(-np.inf)  # 挪车数目不够了，加上一个很大的负值
            new_action = actions[np.argmax(action_returns)]
            policy[i, j] = new_action
            if policy_stable and old_action != new_action:
                policy_stable = False
    print('policy stable {}'.format(policy_stable))
    return policy, value


def update_point(n):
    global value
    global policy

    if n != 0:
        policy, value = optimize_action(value, policy, n)

    ax1.scatter(x, y, policy, marker='o', c='r')
    ax2.scatter(x, y, value, marker='o', c='g')
    plt.suptitle('第%d回合'%n,fontsize = 20)

    return ax1, ax2,


ani = animation.FuncAnimation(fig=fig,
                              func=update_point,
                              frames=10,
                              interval=500,
                              repeat=False,
                              blit=False,
                              init_func=init)
ani.save('test3.gif', writer='pillow')
#plt.show()

价值迭代

价值迭代可以说是策略迭代的一个升级版本，策略迭代的策略评估需要价值函数完全收敛才进行策略提升的步骤，能不能对策略评估的要求放低，这样如果可以实现的话，速度会有所提升。所以价值迭代的方案是：使用贝尔曼最优方程，将策略改进视为价值函数的改进，每一步都求取最大的价值函数。具体的迭代公式如下：

异步动态规划

同步DP算法的主要缺点是每次迭代都需要对整个状态集进行扫描, 这对于状态数非常多的MDP来说耗费巨大. 而异步DP算法则将所有的状态独立地,以任意顺序进行备份, 并且每个状态的更新次数不一, 这可以显著地减少计算量。
为了保证算法的正确收敛, 异步动态规划算法必须保证所有状态都能够持续地被更新(continue to update the values of all the states), 也就是说在任何时刻任何状态都有可能被更新, 而不能忽略某个状态。

广义策略迭代

广义策略迭代(Generalized Policy iteration，GPI)指代让策略评估(policy-evaluation)和策略改进(policyimprovement)过程进行交互的一般概念, 其不依赖于两个过程的粒度(granularity)和其他细节。

动态规划的效率

DP算法也许对一些规模很大的问题并不是很适用，但是和其他解决马尔可夫决策过程的方法相比，DP算法实际上效率很高。如果我们忽略一些技术上的细节，动态规划算法找到最优策略的时间（最坏情况下）与状态和动作的数量是呈多项式级的关系的。如果我们用n和k表示状态和动作的数量，意味着一个DP所需要的计算操作数量少于n与k的某个多项式函数。即使策略的总量达到$k^n$，DP算法也能保证在多项式时间内找到一个最优策略。
DP算法有时会由于维度灾难而被认为缺乏实用性。维度灾难指的是，状态的总数量经常随着状态变量的增加而指数级上升，但是相比起直接搜索，线性规划，DP更加适合于解决大规模状态空间的问题。在实际应用中，采用今天的计算机实现DP算法，可以解决数百万个状态的马尔可夫决策过程。策略迭代和价值迭代都被广泛使用，并且目前仍没有定论到底这两种方法哪种更优