强化学习(三):动态规划

文章目录
  1. 1. 动态规划
    1. 1.1. 动态规划的性质
    2. 1.2. 用动态规划进行Planning
  2. 2. 策略评估
  3. 3. 策略改进
  4. 4. 策略迭代
    1. 4.1. 策略迭代
    2. 4.2. 策略迭代的扩展
      1. 4.2.1. 改良策略迭代
      2. 4.2.2. 广义策略迭代
  5. 5. 值迭代
    1. 5.1. 最优性原则
    2. 5.2. 确定性值迭代
  6. 6. 同步动态规划算法总结
  7. 7. 动态规划的扩展
    1. 7.1. 异步动态规划
      1. 7.1.1. 就地动态规划
      2. 7.1.2. 优先扫描
      3. 7.1.3. 实时动态规划
    2. 7.2. 全宽和采样备份
      1. 7.2.1. 全宽备份
      2. 7.2.2. 采样备份
  8. 8. 压缩映射
  9. 9. 参考资料

在上一篇文章 强化学习(二):马尔可夫决策过程 中, 我们介绍用来对强化学习问题进行建模的马尔可夫决策过程(Markov Decision Processes, MDPs).

由于MDPs的贝尔曼最优方程没有封闭解, 因此一般采用迭代的方法对其进行求解.

本文将介绍使用动态规划(Dynamic Programming)算法来求解MDPs.

动态规划

  • 动态(Dynamic): 问题中的时序部分

  • 规划(Planning): 对问题进行优化

动态规划将问题分解为子问题, 从子问题的解中得到原始问题的解.


动态规划的性质

  • 最优子结构(Optimal substructure)

    • 应用最优性原则(Principle of optimality)
    • 最优解可以从子问题的最优解中得到
  • 重叠子问题(Overlapping subproblems)

    • 相同的子问题出现多次
    • 问题的解可以被缓存和复用

马尔可夫决策过程满足上面两种性质:

贝尔曼方程 给出了问题的递归分解表示, 值函数 存储和复用了问题的解.


用动态规划进行Planning

动态规划假设我们知道MDP的所有知识, 包括状态、行为、转移矩阵、奖励甚至策略等.

对于预测(Prediction)问题:

  • 输入:

    • MDP $<\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma>$ 和 策略 $\pi$
    • MRP $<\mathcal{S}, \mathcal{P}^{\pi}, \mathcal{R}^{\pi}, \gamma>$
  • 输出: 值函数 $v_{\pi}$

对于控制(Control)问题:

  • 输入:

    • MDP $<\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma>$
  • 输出:

    • 最优值函数 $v_{*}$
    • 最优策略 $\pi_{*}$

策略评估

问题: 评估一个给定的策略 $\pi$
求解: 对贝尔曼期望方程进行迭代, $v_1 \to v_2 \to \dots \to v_{\pi}$

通常使用同步备份(synchronous backups)方法:

对于第 $k+1$ 次迭代, 所有状态 $s$ 在第 $k+1$ 时刻的价值 $v_{k+1}(s)$ 用 $v_k(s’)$ 进行更新, 其中 $s’$ 是 $s$ 的后继状态.

迭代策略评估


迭代策略评估算法:

迭代策略评估算法用来估计 $V \approx v_{\pi}$.

这里使用in-place版本, 即只保留一份 $v$ 数组, 没有新旧之分.

通常来说, 该方法也能收敛到 $v_{\pi}$, 而且收敛速度可能更快.

终止条件: $\max \limits_ { s \in \mathcal{S} } \left| v _ { k + 1 } ( s ) - v _ { k } ( s ) \right|$ 小于给定的误差 $\Delta$

迭代策略评估伪代码


例子: Small Gridworld [代码]

Small Gridworld

Small Gridworld Solution


策略改进

让我们考虑一个确定性策略(即对于一个状态来说, 其采取的动作是确定的, 而不是考虑每个动作的概率) $a = \pi(s)$.

我们可以通过贪心选择来改进策略 $\pi$:

即状态 $s$ 的新策略为令动作值函数 $q_{\pi}(s, a)$ 取得最大值的动作.

相应地, 动作值函数 $q _ { \pi } \left( s , \pi ^ { \prime } ( s ) \right)$ 得到了改进:

注: 确定性策略下的动作值函数 $q_{\pi}(s, a)$ 为:

从而, 值函数 $v _ { \pi ^ { \prime } } ( s )$ 也得到了改进:

当改进停止时, 有如下等式:

可以说, 此时公式(3)满足了贝尔曼最优方程:

从而, 对所有状态 $s$ 来说, 有$v_{\pi}(s) = v_{*}(s)$, 即策略 $\pi$ 改进到了最优策略.


策略迭代

策略迭代

给定一个策略 $\pi$, 我们可以首先对策略进行评估, 然后根据值函数 $v_{\pi}$ 进行贪心地改进策略.

其中, $\stackrel { \mathrm { E } } { \longrightarrow }$ 表示策略评估, $\stackrel { \mathrm { I } } { \longrightarrow }$ 表示策略改进.

  • 评估(Evaluate):

  • 改进(Improve):

由于每个策略都比前一个策略更优, 同时一个有限状态的马尔可夫决策过程(finite MDP)仅有有限个策略, 因此该过程一定能够在有限次的迭代中收敛到最优策略 $\pi_{*}$ 和最优值函数 $v_{*}$.


策略迭代


策略迭代算法:

策略迭代算法分为: 初始化, 策略评估 以及 策略改进 三部分.

其中, 策略改进部分的终止条件为: 是否所有状态的策略不再发生变化.

策略迭代算法


例子: Jack’s Car Rental [代码] (先占个坑 , 等有时间把这个例子详细写下)

Jack’s Car Rental

策略迭代求解结果:

Jack’s Car Rental Solution

图中纵坐标是位置 $1$ 的汽车数量, 横坐标是位置 $2$ 的汽车数量, 该问题共有 $21 \times 21$ 个状态.

图中的等高线将状态划分为不同的区域, 区域内的数值代表相应的策略(正数代表从位置 $1$ 移往位置 $2$ 的汽车数量, 负数则往反方向移动).


策略迭代的扩展

改良策略迭代

策略评估并不需要真正的收敛到 $v_{\pi}$. (比如在 Small Gridworld例子中, 迭代 $k=3$次 即可以得到最优策略.)

为此我们可以引进终止条件, 如:

  • 值函数的 $\epsilon$ -收敛
  • 简单地迭代 $k$ 次便停止策略评估

或者每次迭代(即 $k=1$ )都对策略进行更新改进, 这种情况等价于值迭代(value iteration).


广义策略迭代

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

几乎所有强化学习方法都可以很好地被描述为GPI. 也就是说, 它们都具有可辨识的策略与值函数. 其中, 策略 $\pi$ 通过相应的值函数 $v$ 进行改进, 而值函数 $V$ 总是趋向策略 $\pi$ 的值函数 $v^{\pi}$. 如下图所示,

广义策略迭代


值迭代

策略迭代的一个缺点是它的每次迭代都涉及策略评估, 这本身就是一个需要对状态集进行多次扫描的耗时迭代计算.

而在值迭代的过程中, 并没有出现显式的策略, 并且中间过程的值函数可能也不和任何策略对应.


最优性原则

一个最优策略可以被分解为两部分:

  • 当前状态的最优动作 $A_{*}$
  • 后继状态 $S^{\prime}$ 的最优策略

最优性原则

该原则的意思是说, 一个策略 $\pi(a|s)$ 在状态 $s$ 取到最优值函数 $v_{\pi}(s) = v_{*}(s)$ 当且仅当 对于所有从状态 $s$ 出发可到达的状态 $s^{\prime}$, 策略 $\pi$ 也能够在状态 $s^{\prime}$ 取到最优值函数.


确定性值迭代

如果我们已经知道子问题的最优解 $v_{*}(s^{\prime})$, 那么状态 $s$ 的最优解可以通过向前看(lookahead)一步得到, 这称为值迭代(Value Iteration):


值迭代算法:

值迭代算法和策略迭代算法一样, 是用来估计最优策略 $\pi_{*}$ 的, 它将策略评估和策略改进有效地结合在了一起.

值迭代算法


同步动态规划算法总结

问题 贝尔曼方程 算法
预测(Prediction) 贝尔曼期望方程 迭代策略评估
控制(Control) 贝尔曼期望方程 + 贪心策略改进 策略迭代
控制(Control) 贝尔曼最优方程 值迭代

对于有 $m$ 个动作和 $n$ 个状态 的MDP来说, 每次迭代的时间复杂度如下:

函数 复杂度
$v_{\pi}(s)$ or $v_{*}(s)$ $\mathcal{O}(mn^2)$
$q_{\pi}(s, a)$ or $q_{*}(s, a)$ $\mathcal{O}(m^2n^2)$

动态规划的扩展

异步动态规划

同步DP算法的主要缺点是每次迭代都需要对整个状态集进行扫描, 这对于状态数非常多的MDP来说耗费巨大. 而异步DP算法则将所有的状态独立地,以任意顺序进行备份, 并且每个状态的更新次数不一, 这可以显著地减少计算量.

为了保证算法的正确收敛, 异步动态规划算法必须保证所有状态都能够持续地被更新(continue to update the values of all the states), 也就是说在任何时刻任何状态都有可能被更新, 而不能忽略某个状态.

异步DP算法主要有三种简单的思想:

  • 就地动态规划(In-place dynamic programming)
  • 优先扫描(Prioritised sweeping)
  • 实时动态规划(Real-time dynamic programming)

就地动态规划

同步DP保留值函数的两个备份, $v_{new}$ 和 $v_{old}$

就地值迭代只保留值函数的一个备份.


优先扫描

使用贝尔曼误差的大小来进行状态的选择:

  • 仅备份有最大贝尔曼误差的状态

  • 在每次备份后, 需要更新受到影响的状态(即备份状态的前驱状态)的贝尔曼误差

  • 可以使用优先队列进行实现


实时动态规划

  • 思想: 只使用和Agent相关的状态
  • 使用Agent的经验来进行状态的选择
  • 在每个时间步 $S_t, A_t, R_{t+1}$ 对状态 $S_t$ 进行备份

全宽和采样备份

全宽备份

  • DP使用全宽备份(full-width backups)

  • 对于每次备份(不管同步还是异步)

    • 每个后继状态和动作都会被考虑进去
    • 需要知道MDP转移矩阵和奖励函数
  • 对于大规模DP问题会遇到维数灾难

  • 进行一次备份都太奢侈了


采样备份

采样备份(Sample Backups)使用采样的奖励和采样的转移 $< S , A , R , S ^ { \prime } >$ 来替代奖励函数 $\mathcal{R}$ 和 转移矩阵 $\mathcal{P}$.

采样备份的优点:

  • Model-free: 不需要知道MDP的先验知识
  • 通过采样缓解维数灾难
  • 备份代价成为常量, 独立于状态数 $n = |\mathcal{S}|$

压缩映射

关于上面的种种算法, 我们可能会有如下疑问:

  • 值迭代是否会收敛到 $v_{*}$ ?
  • 迭代策略评估是否会收敛到 $v_{\pi}$ ?
  • 策略迭代是否会收敛到 $v_{*}$ ?
  • 解唯一吗 ?
  • 算法收敛速度有多快 ?

为了解决这些问题, 需要引入压缩映射(contraction mapping)理论.
可以参考: 如何证明迭代式策略评价、值迭代和策略迭代的收敛性?


(关于压缩映射理论有时间再补充, 先到这里吧…)


参考资料

分享到 评论