003-马尔可夫决策过程

随机过程

随机过程是一个或者多个事件、随机系统或者随机现象随时间发生演变的过程

$$\mathbb{P}[S_{t+1}|S_1,...,S_t]$$

• 概率论研究静态随机现象的统计规律
• 随机过程研究动态随机过程的规律

马尔可夫过程

马尔可夫过程是具有马尔可夫性质的随机过程，未来取决于之前给订的状态 定义：状态 $S_t$ 是马尔可夫的，当且仅当

$$\mathbb{P}[S_{t+1}|S_t]=\mathbb{P}[S_{t+1}|S_1,\dots ,S_t]$$

性质：

• 状态从历史中捕获了所有相关信息
• 当状态已知时可以抛弃历史不管
• 即当前状态是未来的充分统计量

总结：这里的当前状态实际上是已经浓缩了之前所有状态的信息，而不是只有当前的信息

马尔可夫奖励过程

在马尔可夫过程的基础上加上奖励函数和折扣因子，就可以得到马尔可夫奖励过程

主要因素：

• 状态转移是马尔可夫的

$$\mathbb{P}[S_{t+1}|S_t]=\mathbb{P}[S_{t+1}|S_1,\dots ,S_t]$$

• 基于每个时间步的状态 S，环境产生相应的奖励 $r(S)$ ，随机变量记为 $R_t$
• 基于状态序列极其对应的奖励可以得到序列的回报

$$G_t=R_t+\gamma R_{t+1}{\gamma }^2{R}_{t+2}+\cdots ={\sum }_{k=0}^{\infty }{\gamma }^k{R}_{t+k}$$

这里的收益是对之前状态的加权和，$\gamma$ 取值在 $0-1$ 越大代表对更长远的收益考虑越多，越小对短期收益考虑的更多 这里 $G_t$ 是可以收敛的，所有存在收益最高的情况，让智能体可以找到最优操作

马尔可夫决策过程

马尔可夫决策过程-MDP

• 提供了一套为在结果部分随机、部分在决策者控制下的决策过程建模的数学框架

$$\begin{array}{rl}& \mathbb{P}[S_{t+1}|S_t]=\mathbb{P}[S_{t+1}|S_1,\dots ,S_t]\\ & \mathbb{P}[S_{t+1}|S_{t,A_t}]\end{array}$$

MDP 形式化地描述了一种强化学习的环境

• 环境完全可观测
• 即，当前状态完全表征过程（马尔可夫性质）

这里需要说明的是需要用当前一个状态来表示过去的所有过程的信息，这样可以简化我们决策的过程，只需要当前状态，当前动作就可以得到下一个状态

MDP 五元组

MDP 可以由五元组表示 ( $S,A,\{P_{sa}\},\gamma ,r$ )

• S 是状态的集合
  • 比如，迷宫中的位置，Atari 游戏中的当前屏幕显示
• A 是动作的集合
  • 比如，想上、下、左、右移动，手柄操控方向
• $P_{sa}$ 是状态转移概率|有时写成 $P(\cdot |s,a)$
  • 对于每一个状态 $s\in S$ 和动作 $a\in A$, $P_{sa}$ 是下一个状态在 S 中概率分布
• $\gamma \in [0,1]$ 是对未来奖励的折扣因子
• $r:S\times A\to \mathbb{R}$ 是奖励函数
  • 有时奖励只和状态有关

MDP 的动态

从状态 $S_0$ 开始 智能体选择某一个动作 $a_0\in A$ 智能体得到奖励 $r(S_0,a_0)$ MDP 随机转移到下一个状态 $S_1\sim P_{s_0{a}_0}$

以上过程不断进行 直到终止状态 $S_T$ 出现，或者无止地进行下去 智能体的总回报为

$$r(s_0,a_0)+\gamma r(s_1,a_1)+{\gamma }^{2}r(s_2,a_2)+\dots$$

大部分情况下，奖励只和状态相关

• 比如迷宫游戏中，奖励只和位置相关
• 在围棋中，奖励只基于最终所围地盘大小 此时，奖励函数为 $r(s):S\to \mathbb{R}$ MDP 的过程为

$$S_0\stackrel{a_0,r(s_0)}{\to }{S}_1\stackrel{a_1,r(s_1)}{\to }{S}_2\stackrel{a_2,r(s_2)}{\to }{S}_3\dots$$

累积奖励为

$$r(s_0)+\gamma r(s_1)+{\gamma }^{2}r(s_2)\dots$$

在 动态环境的交互中学习

有监督、无监督学习是 固定数据 ⇒ Model 强化学习是 动态环境⇒Agent

与动态环境交互产生的数据分布

智能体 ⇐> 动态环境 给定同一个动态环境，不同的策略采样出来的（状态-行动）对的分布是不同的

占用度量

⏱️第三讲 16：16 占用度量只 t 时刻的某事件发生，这个公式是某一个动作发生的影响系数 gamma 是对初始时间来说，它占的比例|影响，这里 1 + $\gamma +{\gamma }^2+\dots$ 是等比数列求和或者无穷级数，和是 $\frac{1}{1-\gamma }$，如果要对其归一化需要乘 $1-\gamma$，通常是要归一化的

$$\begin{array}{rl}{\rho }^{\pi }(s,a)& =\mathbb{E}\left[{\sum }_{t=0}^T{\gamma }^t\mathbb{I}(S_t=s,A_t=a)|\pi \right],\forall s\in S,a\in A\\ & ={\sum }_{t=0}^T{\gamma }^{t}P(S_t=s,A_t=a|s_0,\pi )\end{array}$$

其归一化形式 $P^{\pi }(s,a)={\rho }^{\pi }(s,a)=(1-\gamma ){\rho }^{\pi }(s,a)$

占用度量和策略

定理 1: 和同一个动态环境交互的两个策略 $p{i}_1$ 和 ${\pi }_2$ 得到的占用度量 ${\rho }^{{\pi }_1}$ 和 ${\rho }^{{\pi }_2}$ 满足

$${\rho }^{{\pi }_1}={\rho }^{{\pi }_2}⟺{\pi }_1={\pi }_2$$

即两个策略等价

定理 2: 给定一占用度量 $\rho$ ，可生成占用度量的唯一策略是

$${\pi }_{\rho }=\frac{\rho (s,a)}{{\sum }_{a^{{}^{\prime }}}\rho (s,a^{{}^{\prime }})}$$

总结：占用度量是在某一个策略之下，关于状态 s 和动作 a 的概率分布，这里 s 和 a 可以认为是绑定的二元组。不同策略会导致概率分布不一样，每一个策略对应不同的概率分布，因为定理 1 定义占用度量一样那两个策略是等价的

占用度量和累积奖励

占用度量

$$\begin{array}{r}{\rho }^{\pi }(s,a)=={\sum }_{t=0}^T{\gamma }^{t}P(S_t=s,A_t=a|s_0,\pi )\end{array}$$

策略的累积奖励

V(\pi) &= \mathbb{E}[r(S_{0},A_{0})+\gamma r(S_{1},A_{1})+\gamma^2r(S_{2},A_{2})+\dots|S_{0},\pi] \\ &=\textstyle \sum_{s,a} \textcolor{blue}{\sum_{t=0}^T \gamma^tP(S_{t}=s,A_{t}=a|s_{0},\pi)}r(s,a) \\ &=\textstyle \sum_{s,a} \textcolor{blue}{\rho^\pi(s,a)}r(s,a)=\mathbb{E}_{\pi}[r(s,a)] \end{align}

这样策略的累计奖励|状态价值函数可以使用占用度量来表示，最后的期望是强化学习中的简写，所有 $(s,a)$ 分布下收益的期望 这里 ${\gamma }^t$ 可以让我们不需要时间 t 来计算策略奖励，只需要继续向上乘 $\gamma$ 即可，因为从公式第一行可知，相邻时间的期望只需要乘 $\gamma$ 即可

MDP 中策略的目标

策略学习的目标：选择能够最大化累积奖励期望的动作

$$\begin{array}{rl}\underset{\pi }{\max }& \mathbb{E}[r(S_0,A_0)+\gamma r(S_1,A_1)+{\gamma }^{2}r(S_2,A_2)+\dots |s_0,\pi ]\\ & ={\sum }_{s,a}{\rho }^{\pi }(s,a)r(s,a)\end{array}$$

如何达到以上目标？

• 策略 $\pi$ 和其占用度量 ${\rho }^{\pi }$ 的对应关系是黑盒的，因此以上优化目标没有直接对 $\pi$ 更新方向的指导
• 每一个状态状态下策略改变了动作的选择之后，策略整体是否变得更优秀了？ 不一定得看奖励函数的数值是否更优秀

策略评估与策略提升

策略值函数估计

给定环境 MDP 和策略 $\pi$ ,策略值函数估计如下 状态价值

&=\mathbb{E}_{a\sim \pi(S)}\left[ r(s,a)+ \gamma \sum_{s'\in S}P_{s\pi(s)}(s^{\prime})V^\pi(s^\prime)\right] \\ &=\mathbb{E}_{a\sim\pi(S)}\left[Q^\pi(s,a)\right] \end{align}

动作价值

$$\begin{array}{rl}{Q}^{\pi }(s,a)& =\mathbb{E}\left[r(S_0,A_0)+\gamma r(S_1,A_1)+{\gamma }^{2}r(S_2,A_2+\dots )|S_0=s,A_0=a,\pi \right]\\ & =r(s,a)+\gamma \sum _{s^{\prime }\in S}{P}_{s\pi (s)}(s^{\prime })V^{\pi }(s^{\prime })\end{array}$$

总结：状态价值需要考虑当前状态下所有可选动作的价值，得到他们的期望；动作价值是当前状态下指定一个当前动作，但是后续动作还是按照策略考虑所有动作的价值

策略提升

对于两个策略 ${\pi }^{\prime }$, ${\pi }_{\prime }$ 如果满足：对任意状态 $s$，有

$$Q^{\pi }(s,{\pi }^{\prime }(s))\ge V^{\pi }(s)\text{\hspace{1em}(1)}$$

那么 ${\pi }^{\prime }$ 是 $\pi$ 的策略提升

这表示只改变一个当前动作，即改变当前选择动作的策略，其他状态下选择动作的策略不变，可以得到两个策略哪一个更好，这里动作价值函数是不变的，式子左表示只改变当前动作的选择（策略），式子右边表示原来策略的价值

策略提升定理

两个策略满足 $(1)$，进一步对任意状态 $s$，有

$$V^{{\pi }^{\prime }}(s)\ge V^{\pi }(s)$$

即 ${\pi }^{\prime }$ 的策略价值超过 $\pi$，${\pi }^{\prime }$ 比 $\pi$ 更优秀

策略提升定理的启示，找到更好的动作去更新我们的策略

$\epsilon$ -Greedy 策略提升定理

对于 m 个动作的策略：以 $1-\epsilon$ 概率选择最优的动作 $\arg ma{x}_{a\in A}Q(s,a)$, 以 $ϵ$ 概率随机选择动作，把最优动作和其他动作分开看，选择到他们的概率分别是

$$\pi (a|s)=\{\begin{array}{ll}\frac{ϵ}{m}+1-ϵ& \text{if }{a}^{\ast }=\arg \underset{a\in A}{\max }Q(s,a)\\ \frac{ϵ}{m}& \text{otherwise}\end{array}$$

延伸思考：对于随机策略，将策略的动作选择分布一项价值更高的动作