David silver 强化学习 Lecture 3

课程主页: http://web.stanford.edu/class/cs234/index.html

这里回顾David silver 强化学习 Lecture 3的课程内容,这一讲简单介绍了通过动态规划进行控制。

介绍

DP的要求

动态规划用于解决满足以下条件的问题:

  • 最优子结构
  • 重叠子问题

而MDP同时满足以上两个特性。

通过DP规划
  • DP假设有MDP的完全信息
  • DP用于MDP的规划
  • 对于预测:
    • 输入:MDP $\langle\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma\rangle$和策略$\pi$
    • 或:MRP $\left\langle\mathcal{S}, \mathcal{P}^{\pi}, \mathcal{R}^{\pi}, \gamma\right\rangle$
    • 输出:价值函数$v_\pi$
  • 对于控制:
    • 输入:MDP $\langle\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma\rangle$
    • 输出:最有价值函数$v_\star$
    • 以及:最优策略$\pi_\star$

策略评估

迭代策略评估

注意上述情形对应同步更新(synchronous),与之对应的是异步更新(asynchronous)。

策略迭代

  • 给定策略$\pi$

    • 评估策略$\pi$

    • 关于$v_\pi$提升策略

上述过程被称为策略迭代,通常该策略会收敛到$\pi^\star$,上述过程可以用下图表示:

策略提升
  • 考虑确定性策略$a=\pi(s)$

  • 我们可以通过贪心的方式提升策略

  • 这一步就可以提升任何状态$s$的价值,

  • 因此也提升了价值函数,$V_{\pi^{\prime}}(s) \geq V_{\pi}(s)$

  • 如果上述提升停止,那么

  • 即贝尔曼最优方程得到满足

  • 因此对于所有$s\in \mathcal S$,我们有$v_{\pi}(s)=v_{*}(s)$

  • 即$\pi$是最优策略

价值迭代

最优准则

任何最优策略可以被划分为两个部分:

  • 最优的第一步动作$A_\star$
  • 后继状态$S’$的最优策略

定理(最优准则)

策略$\pi (a|s)$从状态$s$得到最优价值,$v_{\pi}(s)=v_{*}(s)$,当且仅当

  • 任何状态$s’$从$s$处可达
  • $\pi$达到状态$s’$的最优价值,$v_{\pi}\left(s^{\prime}\right)=v_{*}\left(s^{\prime}\right)$
确定性价值迭代
  • 如果我们已知子问题的解$v_\star(s’)$

  • 那么解$v_\star(s)$可以通过一步向前看求解

价值迭代

DP扩展

之前介绍的DP都是同步DP,实际中还有异步DP,有如下三个思想实现异步DP:

  • In-place DP
  • Prioritised sweeping
  • Real-time DP
In-place DP
  • 同步值迭代使用的方法是:

  • In-place值迭代使用的方法是:

Prioritised sweeping
  • 使用贝尔曼误差来指导状态的选择,例如

  • 备份Bellman剩余误差最大的状态

  • 每次备份后更新受影响状态的Bellman误差

Real-time DP
  • 思想:只有状态和智能体相关

  • 使用智能体的经验指导状态的选择

  • 在每个时间戳$S_{t}, A_{t}, R_{t+1}$

  • 备份状态$S_t$

压缩映像

这部分讨论策略迭代和价值迭代的收敛性问题,首先定义范数:

  • 定义贝尔曼期望备份算子$T^\pi$,

  • 那么$T^\pi$是$\gamma$压缩的,

这里给出如下定理:

定理(压缩映像定理)

对于任意完备度量空间$\mathcal V$,考虑定义在其上的$\gamma$-压缩算子$T(v)$:

  • $T$收敛到唯一的固定点
  • 收敛速度和$\gamma$呈线性关系

上述定理说明贝尔曼期望算子$T^{\pi}$存在不动点,即$v_\pi$。

本文标题:David silver 强化学习 Lecture 3

文章作者:Doraemonzzz

发布时间:2019年12月03日 - 22:53:00

最后更新:2019年12月03日 - 23:21:06

原始链接:http://doraemonzzz.com/2019/12/03/David silver 强化学习 Lecture 3/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。