强化学习基础

强烈推荐：https://hrl.boyuai.com/

基本概念

RL, in a nutshell, is to “learn to make good sequences of decisions through trail-and-errors”

机器学习范式

• 监督

• 给定训练数据 training data

• 和期望的输出（标签）desired outputs (with labels)

• 半监督

• 给定训练数据 training data

• 和部分期望的输出 some labels

• 无监督

• 仅给定训练数据 training data

• without labels

• 强化学习 Reinforce Learning (RL)

• 从序列决策中获取奖励 observations and periodic rewards as the agent takes sequential actions;

强化学习是一种自动化目标导向的计算方法，与其他机器学习范式最大的区别在于：

• 交互：与环境之间存在交互，从环境中学习
• 决策序列：以前的决策会影响以后的决策，也就是学习的过程
• 探索：不断试错、探索的学习过程

强化学习算法构成

给定

三大集合

• 状态集合
• 动作集合
• 奖励值集合

两大模型 (两大主角)

环境模型（optional）

述了环境的具体表现。在给定状态和动作情况下，模型可能会预测结果的下一个状态和下一个奖励

• 有环境模型：定义了环境模型
• 无环境模型：不定义环境模型，靠智能体感知实时状态来理解环境

主角模型（智能体）

概念来源于分布式人工智能思想。通常意义上，智能体是一个能够感知并施加某种作用到自身和环境、有生命周期的一个物理的或抽象的计算实体。智能体接受一个任务指令后，经过学习，可自主完成该任务

目标

智能体获取从任务开始到任务结束过程中每一步的最优动作

三大特征

• 探索试错
• 延迟回报
• 长期目标

强化学习的关键特征是长期目标优化，智能体关注整体学习问题，优化整个过程

大多强化学习算法的关键特征是值函数的使用

特有挑战

探索和开发 (exploration and exploitation)：短期和长期目标的权衡

强化学习的问题建模

问题模型

状态空间

智能体所处的实际环境所有状态集合

当前状态

智能体感知到的环境当前所处的状态

动作策略

智能体在某时间的行为

奖励信号

智能体收到的关于动作效果的反馈

价值函数

奖励信号 只能说明 动作的即时效果，而 价值函数 则指明什么策略的 长期效果 是好还是差。

马尔科夫决策问题模型

• 参考

马尔可夫奖励过程(MRP)

马尔可夫奖励过程（Markov reward process）

动作序列集

动作序列集（Action Sequence Set）是指一组按特定顺序排列的动作序列。它通常用于描述某个系统、机器人或智能体在特定环境中的行为。动作序列集可以包含一系列离散的动作步骤，也可以包含连续的动作序列。

动作序列集可以被分为两类：

• 有终止态的离散动作（动作幕）
• 无终止态的连续动作

动作幕(Episode)

一个完整的有起始终止状态的动作序列集（Episode，简称动作幕）

• 从标准起始态或从标准分布的初始态集合中抽取初始态开始
• 以终止态结束
• 不同动作序列集都可以认为是在同一个终止态结束，只是序列具体元素不同

Warning

区分奖励和收益

简单收益

Return (aka cumulative future reward) ，未来的累积奖励，也就是简单收益

折扣回报

Discounted Return ，折扣回报，也就是引入了折扣因子的简单收益。

马尔科夫决策过程(MDP)

马尔可夫决策过程（Markov decision process，MDP）

MDP 与 MRP 非常相像，主要区别为 MDP 中的状态转移函数和奖励函数都比 MRP 多了动作 $a$ 作为自变量。

问题模型

MDP（马尔科夫决策过程）是一个描述智能体和环境交互的四元组 (S, A, 𝑅, 𝑝)

• S ：Status 状态的集合
• A ：Action 动作的集合
• R ：Reward 奖励的集合

• p ：当前状态执行了一个动作跳转到下一个状态的概率

• 对象

• 智能体
• 环境
• 交互
• 动作
• 状态
• 奖励

状态-奖励表

扫地机器人状态-奖励表

状态迁移图

扫地机器人状态迁移图

游戏轨迹

(state, action, reward) trajectory 游戏轨迹：

$$s_1,a_1,r_1,s_2,a_2,r_2,\cdots s_T,a_T,r_T$$

Info

即时奖励和长期目标的关系

某一决策的即时奖励较高不一定带来较高的长期目标

追求长期目标 ≠ 追求即时奖励

强化学习的值函数

基础概统知识

以下定义针对离散型随机变量：

概率

随机变量 A = a 发生的概率

$$p(A=a)$$

条件概率

在 C = c 条件下，A = a 的概率

$$p(A=a|C=c)$$

Abstract

智能体处于状态 $s(S=s)$ 时，它的策略 $\pi$ 执行动作 $a(A=a)$ 的概率

$$\pi (a|s)$$

期望

也称随机变量 𝑿 的期待值

$$\mathbb{E}[X]=\sum _i{x}_{i}p(X=x_i)$$

条件期望

Y=y 条件下，X 的期望

$$\mathbb{E}[X|Y=y]=\sum _i{x}_{i}p(X=x_i|Y=y)$$

简单值函数

直觉上看，为找到一个好的动作决策，需为每个动作赋值，只考虑了即时奖励，未考虑长期过程

有了值函数 q(a) ，决策问题即可转为优化问题求解，找最优动作：

$$\underset{a}{argmax}q(a)$$

定义

$$q(a)=\mathbb{E}[R|A=a]\mathrm{\forall }a\in \{1,...,k\}=\sum _{r}p(r|a)r$$

其中 p( r | a ) 是在执行 a 动作情况下观察到智能体获得奖励 r 的概率；R 字母表示 Reward 奖励。

采样平均

除了按定义方法计算，还可以通过采样平均方法计算，即通过以往动作所获奖励情况来估算值函数

$$Q(a)=\frac{\text{获得奖励的总和}}{\text{动作a的执行次数}}$$

具体计算公式为：

$$Q(a)=\frac{\sum _{i=1}^{n-1}{R}_i{\mathbb{1}}_{A_i=a}}{\sum _{i=1}^{n-1}{\mathbb{1}}_{A_i=a}}$$

其中 ${\mathbb{1}}_{A_i=a}$ 表示 $A_i=a$ 时取 1 ，否则取 0

问题

未考虑长期过程，实际并不采用

简单收益

简单收益的定义

G 字母表示 Gain 收益，也叫做回报 Return

$$G_t=R_{t+1}+R_{t+2}+R_{t+3}+...+R_T$$

简单收益的期望

离散动作的简单收益

$$\mathbb{E}[G_t]=\mathbb{E}[R_{t+1}+R_{t+2}+R_{t+3}+...+R_T]$$

连续动作的简单收益

$$\mathbb{E}[G_t]=\mathbb{E}[R_{t+1}+R_{t+2}+R_{t+3}+...]$$

存在问题

若奖励都是非负的，收益会不会是无穷大？

折扣目标收益

引入折扣因子 $\gamma$ ，$\gamma <1$，得到折扣回报（Discounted Return）：

$$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+...+{\gamma }^{k-1}{R}_{t+k}+...=\sum _{k=0}^{\mathrm{\infty }}{\gamma }^k{R}_{t+k+1}$$

当 $\gamma =0$ 时：

$$G_t=R_{t+1}+0R_{t+2}+0^2{R}_{t+3}+...+0^{k-1}{R}_{t+k}+...=R_{t+1}$$

令 $R_{max}$ 为智能体所能获取的最大奖励，则:

$$R_{t+k+1}\le R_{max}$$

$$G_t=\sum _{k=0}^{\mathrm{\infty }}{\gamma }^k{R}_{t+k+1}\le \sum _{k=0}^{\mathrm{\infty }}{\gamma }^k{R}_{max}=R_{max}\sum _{k=0}^{\mathrm{\infty }}{\gamma }^k=\frac{R_{max}}{1-\gamma }$$

目标收益的递归计算

定义 $G_T=0,t\le T$

$$\begin{array}{rl}{G}_t& =R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+...+{\gamma }^{k-1}{R}_{t+k}+...\\ & =R_{t+1}+\gamma (R_{t+2}+\gamma R_{t+3}+...+{\gamma }^{k-2}{R}_{t+k}+...)\\ & =R_{t+1}+\gamma G_{t+1}\end{array}$$

从而有：

$$G_t=R_{t+1}+\gamma G_{t+1}$$

特别地，t = T 时有 $G_T=0$ ；t = T-1 时有 $G_{t-1}=R_T+\gamma G_T$ 。

标准状态值函数

一个状态在策略 𝝅 下的值函数，记作：$v_{\pi }(s)$，是指该策略 𝝅 下，智能体在时间步 t 和所处状态 s 所能获得的奖励的期望值，即该值是从 s 开始，按照策略 𝝅 执行动作的预期收益

$$v_{\pi }(s)\doteq {\mathbb{E}}_{\pi }[G_t|S_t=s]={\mathbb{E}}_{\pi }[\sum _{k=0}^{\mathrm{\infty }}{\gamma }^k{R}_{t+k+1}|S_t=s]$$

Info

符号 $\doteq$ 表示两个数值、表达式、模型之间的近似等于关系。这个符号通常用于数学和工程领域，在数值计算中，表示两个量非常接近或几乎相等，但并非完全相等。

标准动作值函数

一个动作在某个策略下的值函数，记作：$q_{\pi }(s,a)$ ，是指该策略 𝝅 下, 智能体在时间步 t 和所处状态 s，执行动作 𝒂 所获得的奖励的期望值，即从 s 开始，按照策略 𝝅 执行动作 𝒂 ，能获得的预期收益

$$q_{\pi }(s,a)\doteq {\mathbb{E}}_{\pi }[G_t|S_t=s,A_t=a]={\mathbb{E}}_{\pi }[\sum _{k=0}^{\mathrm{\infty }}{\gamma }^k{R}_{t+k+1}|S_t=s,A_t=a]$$

Abstract

两种值函数的区别在于：

• 状态值函数相当于将当前状态 s 所有可能执行的动作都执行一遍，求奖励总和的期望
• 动作值函数相当于只求当前状态 s 下某一个动作 a 的奖励的期望

V 值的递归计算(贝尔曼方程)

由目标收益的递归计算可以得到 V 值的递归计算：

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

其中：

• $V(s)$ 是 $s$ 状态的 V 值；
• $R(s)$ 是 $s$ 状态的奖励
• $P(s^{\prime }|s)$ 是从 $s$ 状态转变为到 $s^{\prime }$ 的概率；
• $\gamma$ 是折扣因子。

该式子也就是贝尔曼方程(?)

从值函数计算最优策略

• 策略：在每一个状态下执行何种动作？
• 最优策略：能够最大化收益的动作执行决策

策略

确定性策略

在某一状态下智能体的策略采取动作 a 的概率是 100% ，即 $\pi (s)=a$

不确定性策略（随机策略）

也叫随机策略

$\pi (a|s)$ 是在状态 $s$ 上采取的动作的概率分布，也可以表示某一状态 s 采取可能的行为 a 的概率，满足：

$$\begin{gathered} \sum _{a\in \mathcal{A}(s)}\pi (a|s)=1 \\ \pi (a|s)\ge 0 \end{gathered}$$

值函数的应用

贝尔曼期望方程

贝尔曼方程(Bellman Equation) 就是递归计算值函数得到的值函数的方程。

贝尔曼期望方程（Bellman Expectation Equation）是为了与接下来的贝尔曼最优方程进行区分

状态值函数

v 值

$$\begin{array}{rl}{v}_{\pi }(s)& \doteq {\mathbb{E}}_{\pi }[G_t|S_t=s]\\ & ={\mathbb{E}}_{\pi }[R_{t+1}+\gamma G_{t+1}|S_t=s]\\ & ={\mathbb{E}}_{\pi }[R_{t+1}]+\gamma {\mathbb{E}}_{\pi }[G_{t+1}|S_t=s]\\ {\mathbb{E}}_{\pi }[R_{t+1}]& =\sum _a\pi (a|s)\sum _{s^{\prime }}\sum _{r}p(s^{\prime },r|s,a)[r]\\ \gamma {\mathbb{E}}_{\pi }[G_{t+1}|S_t=s]& =\sum _a\pi (a|s)\sum _{s^{\prime }}\sum _{r}p(s^{\prime },r|s,a)[\gamma {\mathbb{E}}_{\pi }[G_{t+1}|S_{t+1}=s^{\prime }]]\\ & =\sum _a\pi (a|s)\sum _{s^{\prime }}\sum _{r}p(s^{\prime },r|s,a)[\gamma v_{\pi }(s^{\prime })]\\ v_{\pi }(s)& =\sum _a\pi (a|s)\sum _{s^{\prime }}\sum _{r}p(s^{\prime },r|s,a)[r+\gamma v_{\pi }(s^{\prime })]\end{array}$$

其中 $S_{t+1}=s^{\prime }$

动作值函数

q 值

$$\begin{array}{rl}{q}_{\pi }(s,a)& \doteq {\mathbb{E}}_{\pi }[G_t|S_t=s,A_t=a]\\ & =\sum _{s^{\prime }}\sum _{r}p(s^{\prime },r|s,a)[r+\gamma {\mathbb{E}}_{\pi }[G_{t+1}|S_{t+1}=s^{\prime }]]\\ & =\sum _{s^{\prime }}\sum _{r}p(s^{\prime },r|s,a)[r+\gamma \sum _{a^{\prime }}\pi (a^{\prime }|s^{\prime }){\mathbb{E}}_{\pi }[G_{t+1}|S_{t+1}=s^{\prime },A_{t+1}=a^{\prime }]]\\ q_{\pi }(s,a)& =\sum _{s^{\prime }}\sum _{r}p(s^{\prime },r|s,a)[r+\gamma \sum _{a^{\prime }}\pi (a^{\prime }|s^{\prime })q_{\pi }(s^{\prime },a^{\prime })]\end{array}$$

其中 $S_{t+1}=s^{\prime },A_{t+1}=a^{\prime }$

最优策略的数学表达

$$\mathrm{\forall }s\in \mathcal{S}:{\pi }_1\ge {\pi }_2\iff v_{{\pi }_1}(s)\ge v_{{\pi }_2}(s)$$

$$\mathrm{\forall }s\in \mathcal{S},\mathrm{\forall }a\in \mathcal{A}:{\pi }_1\ge {\pi }_2\iff q_{{\pi }_1}(s,a)\ge q_{{\pi }_2}(s,a)$$

从而有：

$$v_{{\pi }_{\ast }}(s)\doteq {\mathbb{E}}_{{\pi }_{\ast }}[G_t|S_t=s]=\underset{\pi }{max}{v}_{\pi }(s),\mathrm{\forall }s\in \mathcal{S}$$

$$q_{{\pi }_{\ast }}(s,a)={\mathbb{E}}_{{\pi }_{\ast }}[G_t|S_t=s,A_t=a]=\underset{\pi }{max}{q}_{\pi }(s,a),\mathrm{\forall }s\in \mathcal{S},\mathrm{\forall }a\in \mathcal{A}$$

Abstract

$\ast$ 表示最优的，这里 ${\pi }_{\ast }$ 表示最优策略

贝尔曼最优方程

用 $v_{\ast }(s)=v_{{\pi }_{\ast }}(s)?$ 代替原来的 $v_{\pi }(s)$ ，$q_{{\pi }_{\ast }}(s,a)$ 代替原来的 $q_{\pi }(s,a)$ ，那么原本的贝尔曼方程就变成贝尔曼最优方程，得到的表达式就是最优值函数。

参考：https://blog.csdn.net/november_chopin/article/details/106589197，有 demo 更方便掌握。

最优状态值函数

$$\begin{array}{rl}{v}_{\ast }(s)& =\sum _{a={\pi }_{\ast }(s)}{\pi }_{\ast }(a|s)\sum _{s^{\prime }}\sum _{r}p(s^{\prime },r|s,a)[r+\gamma v_{\ast }(s^{\prime })]\\ & =\underset{a}{max}\sum _{s^{\prime }}\sum _{r}p(s^{\prime },r|s,a)[r+\gamma v_{\ast }(s^{\prime })]\end{array}$$

最优状态值函数

$$\begin{array}{rl}{q}_{{\pi }_{\ast }}(s,a)& =\sum _{s^{\prime }}\sum _{r}p(s^{\prime },r|s,a)[r+\gamma \sum _{a^{\prime }={\pi }_{\ast }(s^{\prime })}{\pi }_{\ast }(a^{\prime }|s^{\prime })q_{{\pi }_{\ast }}(s^{\prime },a^{\prime })]\\ & =\sum _{s^{\prime }}\sum _{r}p(s^{\prime },r|s,a)[r+\gamma \underset{a^{\prime }}{max}{q}_{{\pi }_{\ast }}(s^{\prime },a^{\prime })]\end{array}$$

两种最优值函数的关系

$$\begin{array}{rl}{v}_{\ast }(s)& =\underset{a}{max}\sum _{s^{\prime }}\sum _{r}p(s^{\prime },r|s,a)[r+\gamma v_{\ast }(s^{\prime })]\\ & =\underset{a}{max}{\mathbb{E}}_{\pi }[R_{t+1}+\gamma v_{\ast }(S_{t+1})|S_t=s,A_t=a]\\ & =\underset{a}{max}{\mathbb{E}}_{{\pi }_{\ast }}[R_{t+1}+\gamma G_{t+1}|S_t=s,A_t=a]\\ & =\underset{a}{max}{\mathbb{E}}_{{\pi }_{\ast }}[G_t|S_t=s,A_t=a]\\ v_{\ast }(s)& =\underset{a\in \mathcal{A}\mathcal{(}\mathcal{s}\mathcal{)}}{max}{q}_{{\pi }_{\ast }}(s,a)\end{array}$$

TDL

Temporal Difference Learning 差分学习

TD target ：

$$\begin{array}{rl}{y}_t& =r_t+\gamma \cdot Q(s_{t+1},a_{t+1};w)\\ & =r_t+\gamma \cdot \underset{a}{max}Q(s_{t+1},a;w)\end{array}$$

损失函数：

$$L=\frac{1}{2}[Q(w)-y{]}^2$$

梯度：

$$\frac{\partial L}{\partial w}=[Q(w)-y]\cdot \frac{\partial Q(w)}{\partial w}$$

梯度下降计算：

$$w_{t+1}=w_t-\alpha \cdot \frac{\partial L_t}{\partial w}{|}_{w=w_t}$$

算法流程

1. Observe state $S_t=s_t$ and perform action $A_t=a_t$
2. Predict the value: $q_t=Q(s_t,a_t;w_t)$
3. Differentiate the value network: $d_t=\frac{\partial Q(s_t,a_t;w)}{\partial w}{|}_{w=w_t}$；
4. Environment provides new state $s_{t+1}$ and reward $r_t$
5. Compute TD target: $y_t=r_t+\gamma \cdot \underset{a}{max}𝑄(s_{t+1},a;w_t)$
6. Gradient descent: $w_{t+1}=w_t-\alpha \cdot (q_t-y_t)\cdot d_t$

值估计

Sarsa

State-Action-Reward-State-Action (SARSA)

使用 $(s_t,a_t,r_t,a_{t+1})$ 更新 $Q_{\pi }$。

表格

Tabular version

神经网络

Value network version

Q-Learning

表格

Tabular version

神经网络

DQN version

策略