动态规划

在算法设计中经常接触到DP这一思想，其属于一类优化方法，在给定一个用马尔可夫决策过程（MDP）描述的完备环境模型的情况下，可以计算最优的策略。
在强化学习中，DP的核心思想是使用价值函数来结构化地组织对最优策略的搜索：
$$
v_*(s) = max_a E[R_{t+1} + γv_*(S_{t+1}) | S_t=s, A_t=a]\\
q_*(s,a) = E[R_{t+1} + γmax_{a’} q_*(S_{t+1},a’) | S_t=s, A_t=a]
$$

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

策略评估

策略评估的目的是在给定策略π下，计算其状态价值$v_π$，通常依照如下式子进行迭代策略评估，即迭代着计算状态价值：
$$
v_{k+1}(s) = E_π[R_{t+1} + γv_k(S_{t+1}) | S_t=s]
$$

更新细节

通常而言，在编程实现时可以考虑用两种方法来实现策略评估部分的需求，即：

使用两个数组：

一个用于存储旧的价值函数vk(s)
一个用于存储新的价值函数vk+1(s)

也可以采用一个数组进行in place就地更新：每次直接用新的价值函数替换掉旧的价值函数。

如果使用就地更新，vk+1的在更新时，式子右侧有时会使用到vk的新的价值函数（各状态更新的先后顺序可能不同），而不是旧的价值。
而事实上，这种就地更新的方法依然能够收敛到实际状态价值$v_π$，而由于每次获得了新数据就能够马上使用，反而比双数组的传统更新算法要更快。

结果比对

我们再次以MDP章节提到的格子世界为例做一次对比。
使用双数组进行状态价值更新的代码如下：

new_state_values = np.zeros((WORLD_SIZE, WORLD_SIZE))
iteration = 0
while True:
    # 双数组
    state_values = new_state_values.copy()
    # 旧状态价值数组由新状态拷贝构造
    old_state_values = state_values.copy()

    for i in range(WORLD_SIZE):
        for j in range(WORLD_SIZE):
            value = 0
            for action in ACTIONS:
                (next_i, next_j), reward = step([i, j], action)
                value += ACTION_PROB * (reward + discount * state_values[next_i, next_j])
            new_state_values[i, j] = value

    max_delta_value = abs(old_state_values - new_state_values).max()
    if max_delta_value < 1e-4:
        break

    iteration += 1

使用in place进行状态价值更新的代码如下：

new_state_values = np.zeros((WORLD_SIZE, WORLD_SIZE))
iteration = 0
while True:
    # 只用一个数组进行就地更新
    state_values = new_state_values
    for i in range(WORLD_SIZE):
        for j in range(WORLD_SIZE):
            value = 0
            for action in ACTIONS:
                (next_i, next_j), reward = step([i, j], action)
                value += ACTION_PROB * (reward + discount * state_values[next_i, next_j])
            new_state_values[i, j] = value

    max_delta_value = abs(old_state_values - new_state_values).max()
    if max_delta_value < 1e-4:
        break

    iteration += 1