[RL Note] 动态规划的效率

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{}|}$,遍历所有策略会消耗大量时间。

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

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