有模型

已知环境信息，状态转移概率和奖励函数，就变成一个状态转移序列决策问题。

• 熊出现：人可以逃跑 或 装死
• 人装死：熊就一定会走开
• 熊发怒：人逃跑，成功概率0.1，失败概率0.9

但现实情况很难知道环境信息，压根不知道熊到底会做什么，一切都未知，需要免模型算法。

有模型预测-策略评估

动态规划方法

DP特性

动态规划特性

最优子结构/满足最优化原理

• 问题可拆分为多个子问题，问题最优解 包含的子问题的解也是最优的。
• 第一步执行最优动作，后续每一步都按最优策略去做，最终结果也是最优。
• 递归形态，当前状态 与未来状态 有迭代关系。

$$G_t=r_{t+1}+\gamma \cdot G_{t+1}$$

重叠子问题

• 子问题多次出现，其结果能被重复使用，可保存首次计算结果供后续使用
• 存储状态价值 $V(s)$

无有效性

• 某状态不受后面决策的影响，只与 前状态有关，即马尔科夫性质。

适用RL场景

• 要求环境已知，适用于规划问题，而非学习问题

DP做策略评估

使用动态规划做策略评估

核心思想

• 给定策略，通过贝尔曼期望方程来多次迭代 逐渐收敛价值函数
• DP算法本质：通过求解贝尔曼方程，来找到最优策略。

迭代过程

• 求解出每个 $V_{\pi }(s)$，k为迭代次数。
• 当前状态最优价值依赖下一状态最优价值。自举：用一个估计值去更新另一个估计值。
• 最大化即时奖励+下一个状态最优价值，保证当前最优决策建立在后续最优决策基础上。

$$\begin{array}{ll}{V}_{\pi }^{k+1}(s)& =\sum _{a\in A}\pi (a\mid s)\cdot Q_{\pi }(s,a)\\ & =\sum _{a\in A}\pi (a\mid s)\cdot (R(s,a)+\gamma \cdot \sum _{s^{\prime }\in S}p(s^{\prime }\mid s,a)\cdot V_{\pi }^k(s^{\prime }))\end{array}$$$$V_{\pi }^{k+1}(s)=\sum _{a\in A,s^{\prime }\in S}\pi (a\mid s)\cdot p(s^{\prime }\mid s,a)(r(s,a,s^{\prime })+\gamma \cdot V_{\pi }^k(s^{\prime }))$$

• 给定策略后，可以把其简化为马尔可夫奖励过程，去掉a

$$\begin{array}{ll}{V}_{\pi }^{k+1}(s)& =Q_{\pi }(s,\pi (s))\\ & =R(s)+\gamma \cdot \sum _{s^{\prime }\in S}p(s^{\prime }\mid s)\cdot V_{\pi }^k(s^{\prime })\end{array}$$

斯坦福GridWorld策略评估Case

有模型控制-寻找最佳策略

最佳价值和最佳策略

最佳价值和最佳策略

最佳价值函数和最佳策略

• 核心思想：搜索一种策略，让每个状态的价值函数 都取得最大值
• 最佳价值

$$V^{\ast }(s)=\underset{\pi }{max}{V}_{\pi }(s)$$

• 最佳策略

$${\pi }^{\ast }(s)=\arg \underset{\pi }{max}{V}_{\pi }(s)$$

通过最佳价值函数来获取最佳策略

$${\pi }^{\ast }(a\mid s)=\{\begin{array}{ll}1,& a=\arg \underset{a\in A}{max}{Q}^{\ast }(s,a)\\ 0,& \mathrm{其}\mathrm{他}\end{array}$$

• 最佳策略是稳定的，但不一定是唯一的，可能多种动作取得相同价值

最佳策略搜索方法

主要方法

• 穷举法：不现实
• 策略迭代：
• 价值迭代：

策略迭代方法

策略迭代算法

策略迭代

核心思想

• 策略评估：评估当前策略价值函数，推算出Q函数
• 策略改进：通过对Q函数做贪心搜索，来改进策略
• 不断踢皮球：评估策略 <--> 改进策略，一直迭代，直到收敛

策略评估

• 同上文，迭代求解V函数和Q函数

$$\begin{array}{ll}{V}_{{\pi }_{k+1}}(s)& =\sum _{a\in A}\pi (a\mid s)\cdot (R(s,a)+\gamma \cdot \sum _{s^{\prime }\in S}p(s^{\prime }\mid s,a)\cdot V_{{\pi }_k}(s^{\prime }))\end{array}$$$$Q_{{\pi }_{k+1}}(s,a)=R(s,a)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }\mid s,a)\cdot V_{{\pi }_k}(s^{\prime })$$

策略改进

• 根据Q函数 贪心改进策略，会变得更好或不变，但不会变差

$${\pi }_{k+1}(s)=\arg \underset{a}{max}{Q}_{{\pi }_k}(s,a)$$

• 当停止改进后，取让Q函数取得最大值的动作，Q函数就变成V函数了

$$Q_{\pi }(s,{\pi }^{\prime }(s))=\underset{a\in A}{max}{Q}_{\pi }(s,a)=Q_{\pi }(s,\pi (s))=V_{\pi }(s)$$

贝尔曼最优方程

贝尔曼最优方程

策略改进结束后

• 贝尔曼最优方程，最佳策略下的状态价值 必须等于 采取最佳动作 回报的期望。

$$V_{\pi }(s)=\underset{a\in A}{max}Q(s,a)$$$$V^{\ast }(s)=\underset{a\in A}{max}{Q}^{\ast }(s,a)$$

• 当马尔可夫决策过程满足贝尔曼最优方程时，整个状态 已收敛达最佳状态

Q函数贝尔曼最优方程

• 通过Q函数贝尔曼方程+上述简单最优方程得到

$$\begin{array}{ll}{Q}^{\ast }(s,a)& =R(s,a)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }\mid s,a)\cdot V^{\ast }(s^{\prime })\\ & =R(s,a)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }\mid s,a)\cdot \underset{a^{\prime }}{max}{Q}^{\ast }(s^{\prime },a^{\prime })\end{array}$$

V函数贝尔曼最优方程

$$V^{\ast }(s)=\underset{a}{max}(R(s,a)+\gamma \cdot \sum _{s^{\prime }\in S}p(s^{\prime }\mid s,a)\cdot V^{\ast }(s^{\prime }))$$

价值迭代方法

最优性原理

最优性原理

由动态规划策略评估可知

• 当前动作最优，未来每一步动作都是最优，那么最终结果就是最优的。

最优性原理

• 策略$\pi (a\mid s)$在状态$s$达最优价值，意味从$s$能到达的每一个状态$s^{\prime }$，该策略下都达最优价值

$$V_{\pi }(s)=V^{\ast }(s)\Rightarrow V_{\pi }(s^{\prime })=V^{\ast }(s^{\prime })$$

价值迭代算法

确认性价值迭代

核心思想

• 贝尔曼最优方程来迭代计算$V_{\pi }(s)$，当所有子问题$V^{\ast }(s^{\prime })$达最优时，$V_{\pi }(s)$也就达到最优
• 无需策略，直接迭代贝尔曼最优方程，价值函数就能趋向于最佳价值函数，最后取其策略即可

$$V(s)\leftarrow \underset{a}{max}(R(s,a)+\gamma \cdot \sum _{s^{\prime }\in S}p(s^{\prime }\mid s,a)\cdot V(s^{\prime }))$$

• 价值迭代类似于价值的反向传播
  • 每次迭代做一次传播，中间的策略和价值函数没有意义
  • 像是从一个状态反向传播到其他状态的过程，每次迭代只影响与之相关状态的过程

关键流程

• 所有状态初始化：$V_0(s)=0$，

• 从k=1迭代到H次，每次迭代如下：

  $$Q_{k+1}(s,a)=R(s,a)+\gamma \cdot \sum _{s^{\prime }\in S}p(s^{\prime }\mid s,a)\cdot V_k(s^{\prime })$$$$V_{k+1}(s)=\underset{a}{max}{Q}_{k+1}(s,a)$$

• 迭代完成后，提取最优策略

$$\pi (s)=\arg \underset{a}{max}(R(s,a)+\gamma \cdot \sum _{s^{\prime }\in S}p(s^{\prime }\mid s,a)\cdot V(s^{\prime }))$$