12-强化学习

1. 起源

强化学习：不是数据驱动而是和环境的交互驱动，奖惩和试错(Trial and Error）

• 概念学习

  • 给定正例/反例，学习目标概念（如监督学习）

• 交互学习

  • 通过交互学习一个任务（如走出迷宫）
  • 系统/外部环境存在若干状态
  • 学习算法/动作影响状态的分布
  • Exploration： 尽快搜索解空间，有些解不合适，会犯错
  • Exploitation：尽可能不犯错

• 挑战

  • 环境、动作、反馈、模型

• 学习目标

  • 概念->决策
  • 优化目标：最大化长期奖励

2. MDP模型

序列决策过程

2.1. 数学模型

• Markov Decision Process: 四元组表示
  • S-set of states, 状态集合
  • A-set of actions, 动作集合
  • - transition probability，状态转移概率
  • R–immediate reward function, 即时奖赏函数

2.2. 状态和动作

2.3. 奖赏

• ： 从到采取动作a，获得的奖励
  • 确定性，已经知道
• R(s,a)=在状态s，采用动作a获得的奖赏
  • 不确定，是一个期望

2.4. 轨迹

• 在一次Episode中，所获得的经验或轨迹(trajectory)
  • 到经过的实际路径
  • 确定性

2.5. 动作选择

• 目标
  • 最大化期望奖励
• 策略
  • 状态到动作的映射

2.5.1. 例: N-臂老虎机

• 单状态学习问题
  • 没有后续状态
  • 采取行动后只有reward

2.6. 返回函数

• 返回函数（面向多状态学习）

  • 将所有的即时奖励组成一个单一值
  • 返回函数通常是即时奖励值的线性组合

• 问题

  • 轨迹中早期的奖励和晚期的奖励相比，谁更重要？
  • 系统是持续的，还是有终止状态？

• 有限窗口 Finite Horizon

  • 链不知道有多长

• 无穷窗口

  • 有折扣
    • 一般小于1
  • 无折扣

2.7. 动作选择

• 学习目标：期望返回值
  • 最大化期望返回
• 学习的对象：策略
  • 状态到动作的映射
• 潜在公理：最优策略
  • 如果是最有策略，则其从任一状态出发，均是最优的策略
  • 定理：必然存在一个确定性的最有策略

3. 动态规划

给定一个完全已知的MDP模型

强化学习：只知道s,a的MDP模型

• 策略评估
  • 给定一个策略，评估其返回值
• 最优控制
  • 寻找一个最优策略
  • 从任一状态出发，其返回值都为最大

3.1. 值函数

• ：从s状态出发，采用策略，所获得的期望返回值
• : 从s状态出发，采用a动作，继而采用策略，所获得的期望返回值
  • 只在s状态使用a动作
• 最优值函数$V^{}(s)Q^{}(s,a)\pi^{*}$所获得的期望 返回值

要求即使只自己决策一步，也要是最优的

3.2. 策略评估

• Bellman等式：有折扣的无限窗口
  • 当前状态值函数+后续状态值函数
• 重写

3.2.1. 例

确定的MDP模型

$\mathrm{V}^{\pi}\left(\mathrm{s}{0}\right)=0+\gamma\left[\pi\left(\mathrm{s}{0},+1\right) \mathrm{V}^{\pi}\left(\mathrm{s}{1}\right)+\pi\left(\mathrm{s}{0},-1\right) \mathrm{V}^{\pi}\left(\mathrm{s}_{3}\right)\right]$

可以写出四个方程

$$
\mathrm{V}^{\pi}\left(\mathrm{s}{0}\right)=0+\left(\mathrm{V}^{\pi}\left(\mathrm{s}{1}\right)+\mathrm{V}^{\pi}\left(\mathrm{s}_{3}\right)\right) / 4
$$

$$
\begin{aligned} \mathrm{V}^{\pi}\left(\mathrm{s}{0}\right) & =5 / 3 \ \mathrm{~V}^{\pi}\left(\mathrm{s}{1}\right) & =7 / 3 \ \mathrm{V}^{\pi}\left(\mathrm{s}_{2}\right) & =11 / 3 \ \mathrm{V}^{\pi}\left(\mathrm{s}_{3}\right) & =13 / 3\end{aligned}
$$

3.3. 最优控制

• 状态-动作对值函数(对任意确定策略)

其中：

• 贪心策略
  • 选择使得值函数最大的行动
• 贪心策略
  • 概率选择，
  • 以概率选择其他动作

3.4. 例

根据状态-动作值函数进行修改

3.5. 计算最优策略

4. 强化学习

无法通过bellman公式直接计算

4.1. Monte Carlo方法

学习率，

4.1.1. 评价测略

• 学习
• 访问状态，采取策略，获得若干经验
• 在访问状态s 后，对所获得的返回，进行平均。

4.1.2. 最优控制

• MC策略迭代：使用MC方法对策略进行评估，计算值函数；
• MC策略修正：根据值函数(或者状态-动作对值函数)，采 用贪心策略进行策略修正；

4.2. 时差学习

• Every-Visit MC
  • 目标：在经过若干次平均后，得到真实的返回值
• 最简单的时间差分方法(Temporal Difference)
  • 目标：在每一次经验后，都对返回值进行估计

4.3. Bootstraps和Sampling

• Bootstraps
  • 前一个状态值可以用后一个状态估计
  • 通过一个估计值进行更新
  • 动态规划/时差学习中采用
  • 蒙特卡罗方法不采用
• 采样
  • 不通过估计值进行更新，而根据经验进行更新
  • 蒙特卡罗方法/时差学习中采用
  • 动态规划中不采用

4.4. 离策略(off-policy)和在策略(on-policy)

off：假设之后选择最优的action

• Q-learning
  • 不采用真实的next-a，而采用使得下一步Q最大的next-a
• SARSA

4.5. N步TD预测

思路：当做TD回退式，可以看到“更远的未来”

• Monte Carlo
• TD(0)
• TD(n)

4.6. N步回退学习

可以将多个R平均，形成新的R

4.7. TD(λ)

对历史上的s更新