强化学习复习

一、强化学习概述

实验1（20%）+实验2（30%）+考试（50%）

1. 强化学习过程

也称试错法trial and error
通过间接的奖励信号反应完成目标的情况

2. 强化学习与其他机器学习的不同

监督学习的training signal：target outputs 识别或估计观测的内容（感知）
强化学习的traning signal：rewards 根据观测做出行为（决策）

3. 强化学习发展历史

强化学习和马尔可夫决策过程：个体未来的状态只与当前时刻的状态有关
动态规划1957
策略迭代/值迭代
蒙特卡洛算法和时间差分学习算法
无模型学习控制：Sarsa和Q学习
函数逼近
TD-Gammon：1992年,IBM的研究员 Gerald Tesauro 开发了一个结合时间差分学习 (TD Learning)和神经网络的算法，给它取名 TD-Gammon, 专攻双陆棋
策略梯度
- REINFORCE
- Q Actor-Critic
- Advantage Actor-Critic
- TD Actor-Critic
- TD(\(\lambda\)) Actor-Critic
- Natural Actor-Critic
博弈强化学习
逆强化学习
DQN
AlphaGo

4. 强化学习典型应用

游戏AI、电梯调度、机器人、智能驾驶、交通信号控制、智慧城市、芯片设计、智慧医疗、量化金融

5. 强化学习基本元素

5.1 状态State

描述当前agent位置、姿态等信息变量

状态集State Space：agent所有可能states的集合S（离散/连续）

5.2 动作Action

agent能够执行，改变当前state的变量

动作集Action Space：agent所有可行的action集合A（离散/连续）

5.3 策略Policy

状态空间到动作空间的映射 \[ \pi:S \rightarrow A \] 确定策略deterministic: (基于脚本/规则树，每次行为都一样，完全没有变化，容易被对方利用exploitable) \[ a_t=\pi(s_t) \] 随机策略stochastic: \[ a_t \sim \pi(s_t) \\ \pi(a_t|s_t)=P(a_t|s_t) \]

5.4 状态转移State Transition（环境/模型）

描述agent在给定action下state的变化

离散时间：\((s_t,a_t)\rightarrow s_{t+1}\)
- 确定型：\(s_{t+1}=f(s_t,a_t)\) 由\(s_t\) 和 \(a_t\) 唯一决定
- 随机型：\(s_{t+1} \sim P(s_t,a_t)\) 满足一个和\(s_t\) 、\(a_t\) 相关的概率分布
连续时间：\(\dot{x}(t)=f(x(t),u(t))\)

5.5 奖励Reward

环境（算法）对agent当前的state/action好坏程度的反馈

是一个标量的反馈信号

agent的任务就是要最大化累加reward \[ r_{t+1} = R (s_t,a_t) \\ r_{t+1} \sim R (s_t,a_t) \] 某一时刻的瞬时奖励不能完全反映最终目标完成的情况，需要考虑未来奖励的变化

5.6 回报Return

agent从某一初始state出发，在policy下产生的轨迹上的奖励累加和（sum of rewards） \[ G_t=r_{t+1}+\gamma r_{t+1} + ...=\sum_{k=1}^\infin \gamma^k r_{t+k+1} \] 所有的目标都可以通过最大化期望累加奖励实现

5.7 价值Value（期望回报）

agent在当前state下return的期望V \[ V(s_t)=E[G_t]=E[r_{t+1}+\gamma r_{t+2}+...] \\ s_{k+1} \sim P(s_k,a_k),\quad a_k \sim \pi(s_k) \]

5.8 最优策略和最优价值

最优价值optimal value：agent在每个state下能获得的最高价值 \[ V^*(s)=max V(s)=max E[r_{t+1}+\gamma r_{t+1}+...] \] 最优策略optimal policy：能够使agent活的最高价值的策略\(\pi^*\) \[ \begin{align} V^*(s_t)&=E[\sum_{k=0}^\infin \gamma^k r_{t+k+1}|a_k \sim \pi(s_k^*)] \\ & \geq E[\sum_{k=0}^\infin \gamma^k r_{t+k+1}|a_k \sim \pi(s_k)],\forall \pi \end{align} \]

对每个马尔可夫决策问题，最优价值有且只有一个，最优策略不一定是唯一的

6. 强化学习算法分类

6.1 基于价值/基于策略/规划

6.2 在线/离线学习

6.3 基于模型/不基于模型

二、马尔可夫决策过程

1. 马尔可夫性

马尔可夫性

在给定现在state及过去所有states下，agent未来state的条件概率分布仅依赖于当前state

给定现在state时，未来state与过去state是条件独立的 \[ P[s_{t+1}|s_1,...,s_t]=P[s_{t+1}|s_t] \]
全观测/部分可观测

有时agent不能完全获得环境/模型的全部state信息，只能通过观测获得观测量observation

全观测full observable：\(s_t=o_t\)

部分可观测partial obserbale：\(s_t \neq o_t\)

有些场景下，根据observation可以推出state，将部分可观测问题转化为全观测问题
状态转移矩阵

从所有状态\(s\)到所有后继状态\(s'\)的转移概率

矩阵每行元素的和等于1

2. 马尔可夫过程（马尔可夫链）MP（state）

无记忆的随机过程
一组具有马尔可夫性的随机状态序列\(s_1,s_2,...\)
用一组\(<S,P>\)表示
- \(S\)是（有限）状态集
- \(P\)是状态转移概率矩阵，\(P_{ss'}=P[s_{t+1}=s'|s_t=s]\)

3. 马尔可夫奖励过程MRP（state+reward）

一个马尔可夫链MP+奖励reward
由一组\(<S,P,R,\gamma>\)构成
- \(S\)是一组有限状态集
- \(P\)是状态转移概率矩阵，\(P_{ss'}=P[s_{t+1}=s'|s_t=s]\)
- \(R\)是奖励函数，\(R_s=R(s)=E[r_{t+1}|s_t=s]\)
- \(\gamma\)是折扣因子，\(\gamma \in [0,1]\)
回报Return：\(G_t\)代表在 \(t\) 时刻之后轨迹的累加奖励（对应的是某一具体的轨迹） \[ G_t=r_{t+1}+\gamma r_{t+1}+...=\sum_{k=0}^\infin \gamma^kr_{t+k+1} \]
价值Value：一个MRP的价值 \(V\) 等于从状态 \(s\) 出发的期望回报（代表的是所有轨迹的期望） \[ V(s)=E[G_t|s_t=s] \]
折扣因子\(\gamma\)：在连续MDPs问题中可以避免无穷回报，重视近期奖励
MRPs的贝尔曼方程Bellman equation

将价值函数拆成两部分：瞬时奖励\(r_{t+1}\)和后继状态的折扣价值\(\gamma V(s_{t+1})\) \[ V(s)=E[r_{t+1}+\gamma V(s_{t+1}|s_t=s)] \\ V(s)=R(s)+\gamma \sum_{s'\in S}P_{ss'}V(s') \\ V=R+\gamma P V \] （推导略，公式2和上学期高级AI格子游戏的一样）

求解贝尔曼方程（线性方程：
- （状态空间小）直接求解：\(V=(I-\gamma P)^{-1}R\)
- （大规模MRPs问题）迭代/基于数据的方法：动态规划、蒙特卡洛估计、时间差分学习

4. 马尔可夫决策过程MDP（state+reward+action）

马尔可夫奖励过程MRP+智能体的决策action
由\(<S,A,P,R,\gamma>\)组成
- \(S\)是有限状态集
- \(A\)是有限动作集
- \(P\)是状态转移概率矩阵，\(P_{ss'}^a=P[s_{t+1}=s'|s_t=s,a_t=a]\)
- \(R\)是奖励函数，\(R_s^a=R(s)=E[r_{t+1}|s_t=s,a_t=a]\)
- \(\gamma\)是折扣因子，\(\gamma \in [0,1]\)

5. 策略与价值

5.1 策略

策略 \(\pi\) 是状态state到动作action的一种分布 \[ \pi(a|s)=P[a_t=a|s_t=s] \] 确定性/随机性

MDP问题动作的选择只取决于当前状态：\(a_t \sim \pi(s_t)\) （与历史无关，马尔可夫性）

\(\pi(s)\) 表示状态\(s\) 下动作的概率分布
\(\pi(s,a)\) 或\(\pi(a|s)\)表示状态\(s\)下选择动作\(a\)的概率

给定一个MDP问题\(M=<S,A,P,R,\gamma>\)和策略\(\pi\)

agent的state轨迹\(s_1,s_2,...\)是一个马尔可夫过程MP\(<S,P^\pi>\)
agent的state和reward轨迹\(s_1,r_2,s_2,r_3,...\)是一个马尔可夫奖励过程MRP\(<S,P^\pi,R^\pi,\gamma>\)

5.2 价值

根据某种策略决策的，状态价值V和动作价值Q

MDP的（状态）价值\(V_\pi(s)\)：从状态 \(s\) 出发，在策略 \(\pi\) 作用下的期望回报 \[ V_\pi(s)=E_\pi[G_t|s_t=s] \]
动作-价值 \(Q_\pi(s,a)\)：智能体从状态 \(s\) 出发，首先执行动作 \(a\) ，然后按照策略 \(\pi\) 的期望回报 \[ Q_\pi(s,a)=E_\pi[G_t|s_t=s,a_t=a] \]

\[ V_\pi(s)=\sum_{a\in A}\pi(a|s)Q_\pi(s,a) \]

5.3 贝尔曼期望方程Bellman Expectation\(E_q\) ， \(V_\pi\)，\(Q_\pi\)

\[ V_\pi(s)=\sum_{a\in A}\pi(a|s)(R_s^a+\gamma\sum_{s'\in S}P_{ss'}^aV_\pi(s')) \\ Q_\pi(s,a)=R_s^a+\gamma\sum_{s' \in S}P_{ss'}^a\sum_{a'\in A}\pi(a'|s')Q_\pi(s',a') \\ V_\pi=R^\pi+\gamma P^\pi(V_\pi) \]

5.4 最优价值Optimal value

最优价值代表了agent获得的最大期望累加奖励/回报

5.5 最优策略

所有的最优策略的价值/动作-价值都是相通的，等于最优价值/动作-价值

6. 最优化原理

6.1 贝尔曼最优化原理

最优策略具有如下性质：不论初始状态和初始决策如何，余下的决策依然是余下问题的最优策略

6.2 贝尔曼最优方程

\[ V_*(s)=\max_a(R_s^a+\gamma \sum_{s' \in S}P_{ss'}^aV_*(s')) \\ Q_*(s,a)=R_s^a+\gamma \sum_{s'\in S} P_{ss'}^a V_*(s') \\ V_*(s)=\max_aQ_*(s,a) \\ Q_*(s,a)=R_s^a+\gamma \sum_{s'\in S} P_{ss'}^a \max_{a'}Q_*(s',a') \]

6.3 寻找最优策略

\[ \begin{align} V_*(s)&=\max_a(R_s^a+\gamma \sum_{s' \in S}P_{ss'}^aV_*(s')) \\ &\geq R_s^b+\gamma \sum_{s' \in S}P_{ss'}^bV_*(s'),\forall b \in A \end{align} \]

最优策略可以基于\(V_*\)和模型计算最优动作 \[ \pi_*(s)=\arg\max_a(R_s^a+\gamma \sum_{s' \in S}P_{ss'}^aV_*(s')) \] 也可以直接最大化\(Q_*(s,a)\)得到最优策略 \[ \pi_*(s)=\arg\max_a Q_*(s,a) \] 确定性最优策略

求解贝尔曼最优方程需要：

求解非线性算子max
模型已知
足够的计算空间

7. MDPs扩展

MDP用5个元素表示\(<S,A,P,R,\gamma>\)

7.1 不同类型(从基本元素考虑)

连续状态/动作 vs 离散状态/动作
确定模型 vs 随机模型
连续时间 vs 离散时间

7.2 奖励vs惩罚

7.3 不同形式回报

无限时域的累加奖励
无限时域的平均奖励
有限时域的累加奖励和
有限时域的平均奖励

三、动态规划

1. 动态规划

动态规划：通过把原问题分解为相对简单的子问题来求解复杂问题的方法

两个适用条件：

最优子结构性质：问题最优解包含的子问题的解也是子问题的最优解
子问题重叠性质：使用递归算法自顶向下对问题进行求解，每次产生的子问题并不总是新问题

MDP满足以上两个性质：

贝尔曼方程具有递归形式
价值函数可以保存和重复利用

2. 价值迭代Value Iteration, VI

价值迭代算子 \(\Gamma\)

收缩算子

例子：扫地机器人

迭代价值函数，最优策略从收敛的价值函数题去

3. 策略迭代

3.1 提升策略

3.2 策略迭代

3.3 动态规划总结

4. 迭代策略评估

5. 广义策略迭代

6. 维数灾

四、无模型预测学习

0. 策略评估

1. 蒙特卡洛方法

2. 时间差分学习

3. n-步回报

4. TD(\(\lambda\))

5. 资格迹

五、无模型控制学习

0. 预测 vs 控制

预测问题：计算MDP某一策略的价值函数

输入：MDP 和策略
输出：状态值函数或者状态动作值函数

控制问题：计算MDP最优策略/最优价值函数

输入：MDP
输出：最优状态值函数或者最优状态动作值函数，和最优策略

无模型控制学习：

要么MDP本身的模型未知，只能根据观测的经验数据学习（参数未知的机械臂）
要么MDP太复杂，状态空间过大，根据在线样本训练更有效（围棋）

1. 蒙特卡洛控制

2. Sarsa

3. 重要性采样

4. Q-学习

5. Double Q 学习

6. 探索与利用

六、价值函数逼近VFA

1. 函数逼近器

2. 线性函数逼近

3. 常见的特征表示方法

查表法

离散化法：将连续的空间划分成非重叠的，相邻的子空间

粗糙编码coarse coding：特征可以重叠

径向基函数RBF：粗糙编码向连续性特征表示的泛化

4. 价值迭代+离散化方法

5. Fitted Q Iteration

6. 策略迭代+最小二乘

7. 预测学习+随机梯度下降法

梯度下降MC预测算法

梯度下降TD预测学习

梯度下降\(TD(\lambda)\) 算法

基于逼近器的预测学习算法收敛性

MC 可以看成 \(\lambda = 1\) 的特例

8. 控制学习+随机梯度下降法

控制=预测（策略评估）+策略提升

评估：定义Q函数逼近器，使用预测学习进行梯度下降训练（w，Q）
提升：定义具有一定探索性的策略

8.1 梯度下降MC控制算法

8.2 梯度下降Sarsa算法

8.3 梯度下降Q学习算法

七、策略梯度

1. 基于策略的强化学习

1.1 基于价值的RL（定义价值逼近器，隐式的策略）

特点：
- 学习价值函数逼近器
- 策略由价值逼近器提取
- 适用于有限动作集的MDPs问题
缺点：
- 策略是确定型的（greedy/e-greedy），无法表示随机策略
- 价值函数逼近器的误差往往会导致贪心策略和最优策略之间更大的误差
- 难以应对大规模动作集或连续动作空间

1.2 基于策略的RL（定义策略逼近器，没有价值函数）

好处：
- 更好的收敛性
- 有效解决大规模动作集或连续动作空间问题
- 能够学习随机策略
缺点：
- 通常只能收敛到局部最优解
- 对一个策略评估时会费时费力，而且方差较大

1.3 Actor-Critic （价值逼近器辅助策略逼近器训练）

1.4 策略逼近器\(\pi(\theta)\)

与价值函数一样，用参数化的逼近器近似策略

对有限动作集

表示给定状态下选择某一动作的概率 \[ p(a|s)=\pi(a|s,\theta) \]
- softmax策略，基于特征的线性组合表示每个动作被选择的概率 \[ \pi(a|s,\theta) \propto e^{\phi^T(s,a)\theta} \]
- 非线性逼近器（NN的input对应s，output对应a的softmax
对连续动作空间
- 表示给定状态下选择动作的概率分布，常见是高斯分布 \[ a \sim N(\mu(s,\theta),\Sigma) \quad 固定方差 \\ a \sim N(\mu(s,\theta),\Sigma(s,\theta)) \quad 参数化方差 \]
  - 用状态特征的线性组合表示均值
  \[ \mu(s,\theta)=\phi^T(s)\theta \]
  - 也可以用非线性逼近器输出\(\mu\)
- 表示给定状态下确定性的动作 \[ a=\pi(s,\theta) \]
  - 特征线性组合
    \[ \pi(s,\theta)=\phi^T(s)\theta \]
  - 非线性（神经网络）

1.5 策略优化目标\(J(\theta)\)

不同场景对应不同的优化目标

episodic场景：代表整个轨迹的奖励和（单一重复的机械臂任务）
连续运行场景
- 状态空间上的平均回报（绕地卫星的控制）
- 每步的平均奖励（德州扑克）

1.6 策略优化

无梯度的优化算法
- 爬山算法，单纯型算法，遗传算法，交叉熵算法，协方差矩阵自适应算法
- 优势：适用于任何形式的策略逼近器甚至是不可微的逼近器，很容易实现并行计算加快学习速度
- 缺陷：计算量大，数据利用率低，把问题看成黑箱没有考虑MDPs问题的时间连贯特性
基于梯度的优化算法
- 梯度下降法，共轭梯度法，拟牛顿法
- 优势：数据利用率高，有效利用MDPs的时间连贯特性

2. 有限差分策略梯度

不适用梯度公式, 直接使用梯度的定义来计算梯度

策略梯度算法根据梯度上升方向调整 \(\theta\) 找到 \(J(\theta)\) 的局部最大点

有限差分法Finite Difference

3. 解析法策略梯度

无偏、方差大

提高实用性：

时间连贯特性 temporal structure ➡️REINFORCE算法
价值函数 value function ➡️Actor-Critic
优势函数 advantage function ➡️Advantage Actor-Critic算法
自然梯度 natural gradient ➡️Natural Actor-Critic

4. REINFORCE算法（蒙特卡洛策略梯度算法）

时间连贯特性：

\(t' \lt t\) 时刻之前的奖励与t时刻的策略不管，所以对t时刻的梯度更新也没有任何影响

当前时刻的策略梯度使用当前时刻的回报 \(G_t=\sum_{t'=t}^{T-1}r_{t'+1}\)

5. Actor-Critic

估计的回报G具有明显的高方差，使用更稳定的Q函数降低策略梯度的方差