马尔可夫过程

马尔可夫性质

马尔可夫性质

定义

• 给定历史状态$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}})$$

优点

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

实际情况

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

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

马尔可夫链

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

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

回报

• 范围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 \mathrm{接}\mathrm{近}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{时}\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函数贝尔曼方程及其转换关系

VQ函数定义

动作价值函数

状态价值函数/V函数

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

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

动作价值函数/Q函数

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

$$Q^t(s)=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函数的贝尔曼方程，选择所有可能a的均值，通过V来计算V

$$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 }))}}$$

• 通过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函数计算分解

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函数计算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}$$

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函数计算分解

贝尔曼方程推导过程

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}$$

• 关键内容：证明如下公式 + 数学全期望公式 + $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值对应的动作即可。

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

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