[RL Notes] 动态规划的效率

Author: nex3z 2019-10-20

1. 对比蒙特卡洛方法

　　在进行策略评估时，除了使用迭代策略评估这种动态规划的方法外，还可以使用基于样本的策略评估方法，将计算每一个状态的价值看做是一个完全独立的估计问题。根据策略 $\pi$ 的状态价值函数 $v_\pi$ 的定义

$$\begin{equation} v_\pi \doteq \mathbb{E}[G_t | S_t = s] \tag{1} \end{equation}$$

为了估计某个状态 $s$ 的价值，可以在使用策略 $\pi$ 在状态 $s$ 下收集大量的回报样本，然后计算平均。这种方法称为蒙特卡洛方法（Monte Carlo method）。由于每一个回报都取决于策略 $\pi$ 选择的大量动作，以及由 MDP 动态特性决定的状态转换，存在大量的不确定性，因此每一个回报样本可能都会大幅度偏离于状态的真实价值。要保证收敛，需要在每个状态上都收集大量回报样本。

　　相比之下，动态规划并没有将每一个状态看成是一个独立的问题，迭代策略评估的更新公式为

$$\begin{align} v_{k+1}(s) \leftarrow \sum_a \pi(a|s) \sum_{s’} \sum_{r} p(s’, r | s, a) \Big[ r + \gamma v_k(s’) \Big] \tag{2} \end{align}$$

注意在更新某个状态的价值 $v_{k+1}(s)$ 时，利用了之前计算的结果如 $v_{k}(s’)$，减少计算量。动态规划算法利用后继状态价值的估计来改善当前状态价值的估计，这种方法称为自举（bootstrapping）。因此动态规划算法要比蒙特卡洛方法高效得多。

2. 对比暴力搜索

　　为了找到最优策略，除了策略迭代的方法外，还可以使用暴力搜索，即对每一个策略都进行评估，找到最优的那一个。有限 MDP 只有有限个确定性策略，且存在最优策略，因此暴力搜索最终会找到最优策略。每一个确定性策略在每一个状态都会选择一个动作，因此策略的总数可达 $|\mathcal{A}|^{|\mathcal{S}|}$，遍历所有策略会消耗大量时间。

　　相比之下，基于动态规划的策略迭代利用策略改进定理，每一步迭代都在原有策略的基础上进行改善，得到一个更优的策略，而不必遍历所有策略。策略迭代算法能在 $|\mathcal{S}|$ 和 $|\mathcal{A}|$ 的多项式时间内找到最优策略，指数级优于暴力搜索。而在实际中，随着迭代的进行，策略更新得越来越少，价值函数更新得也越来越少，算法通常会快速收敛，动态规划的效率还要远优于其最差情况的底线。

　　在实际问题中，状态总数经常会随着状态变量的增加而指数级上升，这称为维度灾难，即使使用动态规划算法也很难求解，但这种困难这是问题本身的复杂性所带来的，而不是动态规划带来的。