马尔可夫过程

马尔可夫性质

马尔可夫性质

定义

• 给定历史状态$s_0,s_1,\cdots ,s_t$的情况下，未来$s_{t+1}$只与当前状态$s_t$有关，而与历史无关
• 即未来的转移和过去是独立的

$$p(s_{t+1}\mid s_t)=p(s_{t+1}\mid \underset{h_t}{\underbrace{s_0,s_1,\cdots ,s_t}})$$

优点

• 允许我们在不考虑完整系统历史的情况下，预测和控制 Agent行为

实际情况

• 很多例子，如棋牌游戏，是不符合马尔可夫性质的，不仅依赖当前，还依赖历史状态。

马尔可夫链/马尔可夫过程

马尔可夫链

• 离散时间的马尔可夫过程，是最简单的马尔可夫过程

$$s_0,s_1,\cdots ,s_t$$

状态转移矩阵

状态转移矩阵

• 状态转移概率：$p(s_{t+1}=s^{\prime }\mid s_t=s)$，状态从s转移到$s^{\prime }$的概率$p_{s{s}^{\prime }}$。

• 状态转移矩阵：有限状态的马尔可夫过程

$$P_{s{s}^{\prime }}=\left[\begin{array}{ccc}{p}_{11}& p_{12}& \cdots p_{1n}\\ p_{21}& p_{22}& \cdots p_{2n}\\ ⋮& ⋮& ⋮\\ p_{n1}& p_{n2}& \cdots p_{nn}\end{array}\right]$$

马尔可夫奖励过程

马尔可夫奖励过程

马尔可夫奖励过程

定义

• 在马尔可夫过程的基础上，仅增加奖励函数，R是一个期望

$$s_1,r_1,s_2,r_2,\cdots ,s_t,r_t$$

奖励、回报、价值函数

奖励、回报、价值函数

即时奖励

• 奖励$r_t$：环境给出的标量反馈信号，Agent 到达某状态 获得的即时奖励。
• 反应智能体在某状态采取某个动作 表现如何

回报

• 范围horizon：一个回合的长度
• 回报$G_t$：未来奖励之和，面向未来/无限累计，可通过贝尔曼方程 迭代计算。

$$G_t=r_{t+1}+r_{t+2}+\cdots +r_T$$

• 折扣回报：对未来奖励打折扣，更希望得到现在的奖励

$$G_t=r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+\cdots =\sum _{k=0}^{\mathrm{\infty }}{\gamma }^k{r}_{t+k+1}=r_{t+1}+\gamma G_{t+1}$$

• 折扣因子$\gamma$：对未来奖励的重要程度，平衡当前奖励和未来奖励。
  • $\gamma =0$ ，单步奖励，只关注当前；$\gamma$接近1，对所有未来奖励都同等重要
  • 越往后${\gamma }^k$越小，越后面的奖励对当前价值的影响，会越来越小

价值

• 价值函数：即时奖励+ 未来状态的折扣价值。
• 状态价值函数/V函数：进入某状态后 可能获得的平均回报。回报的期望

$$V^t(s)=\mathbb{E}[G_t\mid s_t=s]$$

• 状态动作价值函数/Q函数：在某状态 采取某动作 可能获得的平均回报。回报的期望。

$$Q^t(s,a)=\mathbb{E}[G_t\mid s_t=s,a_t=a]$$

• 更多VQ见下文

为什么能用未来总奖励评价当前动作的好坏?

• 现实世界奖励 往往是延迟的，强化学习需要学习远期奖励
• 后续有可能收到的奖励加起来，才算作当前动作的Q值，但不能太远，需要使用折扣因子

使用折扣因子的原因

• 某些马尔科夫过程是带环的，避免无穷奖励
• 未来评估 不一定准确，存在不确定性
• 可能更希望立刻就能得到奖励，而不是后面才得到奖励

V函数的贝尔曼方程

V函数贝尔曼方程

V函数的贝尔曼方程

• 定义当前状态和未来状态之间的迭代关系，即时奖励+未来奖励的折扣总和。

$$V(s)=\underset{\mathrm{当}\mathrm{前}s\mathrm{即}\mathrm{时}\mathrm{奖}\mathrm{励}}{\underbrace{R(s)}}+\underset{\mathrm{未}\mathrm{来}\mathrm{奖}\mathrm{励}\mathrm{的}\mathrm{折}\mathrm{扣}\mathrm{总}\mathrm{和}}{\underbrace{\gamma \sum _{s^{\prime }\in S}p(s^{\prime }\mid s)\cdot V(s^{\prime })}}$$

• 矩阵形式：状态特别多时，求解特别困难。

$$\mathbf{V}=\mathbf{R}+\gamma \mathbf{PV}$$

V函数贝尔曼方程的证明过程

• 推导过程：见下文

• 关键内容：证明如下公式 + 数学全期望公式 + $G_t$定义

马尔可夫奖励过程价值的迭代算法

状态太多时，不太能直接使用矩阵求逆求解价值函数，一般使用迭代算法来进行求解。包括蒙特卡洛方法，动态规划方法，时序差分方法等。

蒙特卡洛方法

核心思想

• 从某状态开始，按照状态转移矩阵，随波逐流产生多条轨迹，每条轨迹算出回报g
• 对多条轨迹的回报g 做平均，即得到状态价值

$$V(s)=\frac{1}{N}\sum _{i=1}^{N}G({\tau }_i)=\frac{1}{N}\sum _{i=1}^N\sum _{t=0}^{T-1}{\gamma }^t{r}_{t+1}$$

动态规划方法

核心思想

• 通过动态规划+自举的方法，一直迭代贝尔曼方程，直到价值函数收敛，得到状态价值。
• 动态规划：用未来的价值估计 来更新 现在的价值估计
• 自举(bootstrap)/强化：根据其他估算值来更新估算值
  • 用下一个状态价值 来更新 当前状态价值。

算法过程

• 直到更新差值 小于阈值时，就可以停止更新，$\Vert V-V^{\prime }\Vert <ϵ$
• 大于阈值时，对所有状态 $s\in S$，执行贝尔曼方程进行迭代更新

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

马尔可夫决策过程

马尔可夫决策过程

马尔可夫决策过程

关键定义

• 未来状态：同时依赖于当前状态和智能体 在当前状态采取的动作

$$p(s_{t+1}\mid s_t,a_t)=p(s_{t+1}\mid h_t,a_t)$$

• 奖励函数：由状态和当前动作决定

  $$R(s_t=s,a_t=a)=E[r_t\mid s_t=s,a_t=a]$$

• 轨迹

  $$s_1,a_1,r_1,s_2,a_2,r_2,\cdots ,s_t,a_t,r_t$$

核心思想

• 马尔可夫决策过程：寻找一个最佳策略，使价值函数最大

策略

• 定义了在某状态 该采取什么动作，可以输出动作概率、也可以输出确定的动作值。

$$\pi (a\mid s)=p(a_t=a\mid s_t=s)$$

• 可以是随机性策略 或 确定性策略
• 如果已知马尔可夫决策过程和策略$\pi$，就可将其转换成马尔可夫奖励过程

马尔可夫决策过程4元组：

状态转移和序列决策：

马尔可夫决策、奖励过程对比

马尔可夫决策过程

• 马尔可夫过程/马尔可夫奖励过程：状态转移直接由状态决定的
• 马尔可夫决策过程：状态转移 由状态和当前动作决定的
  • 在当前状态和未来状态间多了一层决策性

VQ函数贝尔曼方程及其转换关系

贝尔曼方程奇妙之处

• 把无限累加公式 --> 有限递归公式。
• 用迭代的方式 --> 去求解 这个状态方程

价值函数基础定义

动作价值函数

状态价值函数/V函数

• 在状态s，回报的期望。期望和策略相关

$$V_{\pi }(s)=E[G_t\mid s_t=s]$$

动作价值函数/Q函数

• 在状态s 采取动作a，可能得到回报的期望。

$$Q^t(s,a)=E[G_t\mid s_t=s,a_t=a]$$

贝尔曼期望方程

贝尔曼期望方程

贝尔曼期望方程

• 贝尔曼期望方程：当前状态和未来状态的关联关系
• V/Q函数：当前即时奖励 + 后续状态的折扣回报。

V函数的贝尔曼期望方程

$$V_{\pi }(s)=E_{\pi }[r_{t+1}+\gamma \cdot V_{\pi }(s_{t+1})\mid s_t=s]$$

Q函数的贝尔曼期望方程

$$Q_{\pi }(s,a)=E_{\pi }[r_{t+1}+\gamma \cdot Q_{\pi }(s_{t+1},a_{t+1})\mid \underset{\mathrm{条}\mathrm{件}}{\underbrace{s_t=s,a_t=s}}]$$

备份图

• 定义了未来下一时刻的价值函数与上一时刻价值函数的关联关系。

V函数

V函数

1. 基础定义

• 从状态s开始，执行策略$\pi$，获得的平均回报，回报的期望。

$$V_{\pi }(s)=E[G_t\mid s_t=s]$$

2. V函数的贝尔曼方程

• 贝尔曼期望方程

$$V_{\pi }(s)=E_{\pi }[r_{t+1}+\underset{\mathrm{未}\mathrm{来}\mathrm{状}\mathrm{态}}{\underbrace{\gamma \cdot V_{\pi }(s_{t+1})}}\mid \underset{\mathrm{条}\mathrm{件}}{\underbrace{s_t=s}}]$$

• 通过V计算V，V函数的贝尔曼方程，所有可能a的均值

$$V_{\pi }(s)=\sum _{a\in A}\pi (a\mid s)\cdot \underset{Q\mathrm{函}\mathrm{数}\mathrm{的}\mathrm{贝}\mathrm{尔}\mathrm{曼}\mathrm{方}\mathrm{程}}{\underbrace{(R(s,a)+\gamma \cdot \sum _{s^{\prime }\in S}p(s^{\prime }\mid s,a)\cdot V_{\pi }(s^{\prime }))}}$$$$V_{\pi }(s)=\sum _{a,s^{\prime }}\pi (a\mid s)\cdot p(s^{\prime }\mid s,a)\cdot (r(s,a,s^{\prime })+\gamma \cdot V_{\pi }(s^{\prime }))$$

• 通过Q计算V，策略$\pi$和状态价值之间，通过动作价值函数来联系。

$$\begin{array}{ll}{V}_{\pi }(s)& =\sum _{a\in A}\pi (a\mid s)\cdot Q_{\pi }(s,a)\end{array}$$

• V函数的贝尔曼方程推导过程 ⭐

$$\begin{array}{ll}{V}_{\pi }(s)& =E[\underset{\mathrm{当}\mathrm{前}\mathrm{状}\mathrm{态}}{\underbrace{r(s,a,s^{\prime })}}+\underset{\mathrm{未}\mathrm{来}\mathrm{状}\mathrm{态}}{\underbrace{\gamma V_{\pi }(s^{\prime })}}]\\ & =\underset{\mathrm{执}\mathrm{行}\mathrm{动}\mathrm{作}a}{\underbrace{\sum _{a\in A}\pi (a\mid s)}}\cdot \underset{\mathrm{状}\mathrm{态}\mathrm{转}\mathrm{移}}{\underbrace{\sum _{s^{\prime }\in S}p(s^{\prime }\mid s,a)}}\cdot [\underset{\mathrm{当}\mathrm{前}\mathrm{即}\mathrm{时}\mathrm{奖}\mathrm{励}}{\underbrace{r(s,a,s^{\prime })}}+\underset{\mathrm{未}\mathrm{来}\mathrm{折}\mathrm{扣}\mathrm{奖}\mathrm{励}}{\underbrace{\gamma \cdot V_{\pi }(s^{\prime })}}]\\ & =\sum _{a,s^{\prime }}\pi (a\mid s)\cdot p(s^{\prime }\mid s,a)\cdot [r(s,a)+\gamma \cdot V_{\pi }(s^{\prime })]\\ & =R(s)+\gamma \cdot \sum _{s^{\prime }\in S}p(s^{\prime }\mid s)\cdot V(s^{\prime })\end{array}$$

3. V函数的贝尔曼最优方程：直接选择回报最大的a

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

V函数计算分解

Q函数

Q函数

1. Q函数定义：从状态s开始 选择动作a，依照策略$\pi$执行，获得回报的期望。

$$Q_{\pi }(s,a)=E[G_t\mid s_t=s,a_t=a]$$

2. Q函数的贝尔曼期望方程

• Q函数贝尔曼期望方程

$$Q_{\pi }(s,a)=E_{\pi }[r_{t+1}+\underset{\mathrm{未}\mathrm{来}\mathrm{状}\mathrm{态}}{\underbrace{\gamma \cdot V_{\pi }(s_{t+1})}}\mid \underset{\mathrm{条}\mathrm{件}}{\underbrace{s_t=s,a_t=a}}]$$

• 通过V计算Q，Q函数贝尔曼方程，所有可能s的均值

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

• 通过Q计算Q，Q函数自身迭代计算

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

3. Q函数的贝尔曼最优方程，直接选择最大回报的a

$$\begin{array}{ll}{Q}^{\ast }(s,a)& =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}$$$$Q_{{\pi }_{\ast }}(s,a)=\sum _{s^{\prime }\in S}p(s^{\prime }\mid s,a)\cdot (r(s,a,s^{\prime })+\gamma \cdot \underset{a^{\prime }}{max}{Q}_{{\pi }_{\ast }}(s^{\prime },a^{\prime }))$$

Q函数计算分解

贝尔曼方程推导过程

V函数贝尔曼方程推导

数学全期望公式

设$A_i$是样本空间的有限或可数划分

$$E[X]=\sum _{i}p(A_i)\cdot E[X\mid A_i]$$

V函数贝尔曼方程推导过程

贝尔曼方程

• 定义当前状态和未来状态之间的迭代关系，即时奖励+未来奖励的折扣总和。

$$V(s)=\underset{\mathrm{即}\mathrm{时}\mathrm{奖}\mathrm{励}}{\underbrace{R(s)}}+\underset{\mathrm{未}\mathrm{来}\mathrm{奖}\mathrm{励}\mathrm{的}\mathrm{折}\mathrm{扣}\mathrm{总}\mathrm{和}}{\underbrace{\gamma \sum _{s^{\prime }\in S}p(s^{\prime }\mid s)\cdot V(s^{\prime })}}$$

V函数贝尔曼方程证明过程

$$\begin{array}{ll}V(s)& =E[G_t\mid s_t=s]\\ & =E[r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+\cdots \mid s_t=s]\\ & =E[r_{t+1}\mid s_t=s]+\gamma E[r_{t+2}+\gamma r_{t+3}+{\gamma }^2{r}_{t+3}+\dots \mid s_t=s]\\ & =R(s)+\gamma E[G_{t+1}\mid s_t=s]\\ & =R(s)+\gamma E[V_{t+1}\mid s_t=s]\\ & =R(s)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }\mid s)\cdot V(s^{\prime })\end{array}$$

这样也可以

$$\begin{array}{ll}V(s)& =E_{\pi }[G_t\mid s_t=s]\\ & =E_{\pi }[r_t+\gamma G_{t+1}\mid s_t=s]\\ & =E_{\pi }[r_t\mid s_t=s]+\gamma E_{\pi }[G_{t+1}\mid s_t=s]\\ & =\sum _{a,s^{\prime }}\pi (a\mid s)\cdot p(s^{\prime }\mid s,a)\cdot r(s,a,s^{\prime })+\gamma E_{\pi }[G_{t+1}\mid s_t=s]\end{array}$$

• 关键内容：证明如下公式 + 数学全期望公式 + $G_t$定义

$$E[V(s_{t+1})\mid s_t]=E[E[G_{t+1}\mid s_{t+1}]\mid s_t]=E[G_{t+1}\mid s_t]$$

V函数贝尔曼最优方程推导

V函数贝尔曼最优方程推导

$$\begin{array}{ll}{V}^{\ast }(s)& =\underset{a}{max}{Q}^{\ast }(s,a)=\underset{a}{max}E[G_t\mid s_t=s,a_t=a]\\ & =\underset{a}{max}E[r_{t+1}+\gamma G_{t+1}\mid s_t=s,a_t=a]\\ & =\underset{a}{max}E[r_{t+1}+\gamma V^{\ast }(s_{t+1})\mid s_t=s,a_t=a]\\ & =\underset{a}{max}E[r_{t+1}]+\underset{a}{max}[\gamma V^{\ast }(s_{t+1})\mid s_t=s,a_t=a]\\ & =\underset{a}{max}R(s,a)+\underset{a}{max}\gamma \sum _{s^{\prime }\in S}p(s^{\prime }\mid s,a)\cdot V^{\ast }(s^{\prime })\\ & =\underset{a}{max}\underset{Q^{\ast }(s,a)}{\underbrace{(R(s,a)+\sum _{s^{\prime }\in S}p(s^{\prime }\mid s,a)\cdot V^{\ast }(s^{\prime }))}}\end{array}$$

Q函数贝尔曼方程推导

Q函数的贝尔曼方程推导过程

Q函数贝尔曼方程

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

推导过程

• 从期望公式开始推导，同V函数推导过程

$$\begin{array}{ll}Q(s,a)& =E[G_t\mid s_t=s,a_t=a]\\ & =E[r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+\cdots \mid s_t=s,a_t=a]\\ & =E[r_{t+1}\mid s_t=s,a_t=a]+\gamma E[r_{t+2}+\gamma r_{t+3}+\cdots \mid s_t=s,a_t=a]\\ & =R(s,a)+\gamma E[G_{t+1}\mid s_t=s,a_t=a]\\ & =R(s,a)+\gamma E[V_{t+1}\mid s_t=s,a_t=a]\\ & =R(s,a)+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }\mid s,a)\cdot V(s^{\prime })\end{array}$$

预测和控制

预测和控制

预测/策略评估

• 核心：给定策略，求解价值函数 $V_{\pi }$，评估策略价值
• 输入：马尔可夫决策过程$<S,A,P,R,\gamma >$ 和 策略$\pi$
• 输出：价值函数$V_{\pi }$

控制/寻找最佳策略

• 核心：不限制策略，要去寻找 最佳策略和最佳价值
• 输入：马尔可夫决策过程$<S,A,P,R,\gamma >$
• 输出：最佳价值函数$V^{\ast }$、最佳策略${\pi }^{\ast }$

预测和控制的关系

• 预测方法，是为了帮助解决控制问题做铺垫。
• 为了解决控制问题，只需要直接预测Q函数即可，在决策时 选择最大Q值 对应的动作即可。

预测：给定策略，策略为等概率上下左右移动，求解价值函数

控制：不给定策略，直接求解最优价值，输出对应策略。