# 6. 强化学习 RL

## 6.1 RL 的基础知识

### 1. RL 和 Markov Decision Process

* RL 要素：状态集合 S，动作集合 A，状态转移函数 P，奖励函数 R
* 步骤：动作（连续 / 离散）、奖励（累积回报）、环境转移
* 分类
  * 是否对真实环境建模：有模型学习、免模型学习（主流，数据驱动，泛化能力强）
  * 更新策略：单步更新、回合更新
  * 行为策略和价值策略是否相同：现实策略（on-policy）、借鉴策略（off-policy）
  * 能否推测状态转移概率：动态规划、蒙特卡洛法

### 3. 基于策略迭代 和 基于价值迭代 的区别

* 基于策略迭代：给定状态下，采取何种动作，e.g. 策略梯度（Policy Gradients）
* 基于价值迭代：维护价值表格 / 函数，取最大（离散环境），e.g. Q-Learning, Sarsa
* 联合决策：演员-评论家（Actor-Critic）算法

## 6.2 RL 算法

### 1. 时序差分（TD）和 蒙特卡洛（MC） 的区别 \*

* 时序差分：采样不完整序列，快速、灵活
* 蒙特卡洛：经历完整状态序列

### 2. Q-learning（TD，基于价值迭代，免模型，借鉴策略）

* 动作价值函数 $$Q^\pi(s\_t,a\_t)=\mathbb E\[r\_t+\gamma Q^\pi(s\_{t+1},a\_{t+1})|s\_t,a\_t]$$，是 Bellman 方程
* 步骤（浅层时序差分采样）
  * 动作选择：贪心算法，$$\xi$$ 贪心策略（概率随机 / 贪心）
  * 执行动作，获得 $$r\_t$$ 以及 $$s\_{t+1}$$
  * 更新 Q 值：$$Q(s\_t,a\_t)\leftarrow Q(s\_t,a\_t)+\alpha(r\_t+\gamma \max\_{a\_{t+1}}Q(s\_{t+1},a\_{t+1})-Q(s\_t,a\_t))$$

### 3. Sarsa 和 Sarsa($$\lambda$$)（TD，基于价值迭代，免模型，现实策略）

* Sarsa 和 Sarsa($$\lambda$$)
  * Sarsa：单步更新，$$Q(s\_t,a\_t)\leftarrow Q(s\_t,a\_t)+\alpha(r\_t+\gamma Q(s\_{t+1},a\_{t+1})-Q(s\_t,a\_t))$$
  * Sarsa($$\lambda$$)：n 步更新，衰减求和，$$Q(s\_t,a\_t)\leftarrow Q(s\_t,a\_t)+\alpha(q\_t^\lambda -Q(s\_t,a\_t))$$
    * $$q\_t=r\_t+\gamma Q(s\_{t+1},a\_{t+1})$$
    * $$q\_t^\lambda=(1-\lambda)\sum\_{n=1}^\infty \lambda^{n-1}q\_t^{(n)}$$
* Sarsa 和 Q-learning
  * Q-learning 取 max 非常激进（每步最优），Sarsa 相对保守（安全迭代）
  * Q-learning 是 借鉴策略 的 TD，Sarsa 是 现实策略 的 TD

## 6.3 深度 RL

* 动作价值函数 $$Q(s,a;\theta)\approx Q\_\pi(s,a)$$，函数近似，替代表格存储
* 价值更新函数：类似 Q-learning
  * $$Q(s\_t,a\_t;\theta)\leftarrow Q(s\_t,a\_t;\theta)+\alpha(r\_t+\gamma \max\_{a\_{t+1}}Q(s\_{t+1},t\_{t+1};\theta)-Q(s\_t,a\_t;\theta))$$
  * 相应损失函数 $$Loss(\theta)=\mathbb E(r\_t+r\_t\max\_{a\_{t+1}}(s\_{t+1},a\_{t+1};\theta)-Q(s\_t,a\_t;\theta))^2$$
* 经验回放：从历史数据中随机采样

## 6.4 RL 的应用

* 游戏 - 策略指制定：Atari、星际争霸（多智能体）、AlphaGo（Zero）
* 自动驾驶 - 决策系统：强制性约束 + 可学习策略
* AutoML - 神经网络架构搜索：Google Brain
* NLP - 对话系统：任务型对话 / 非任务型对话，理解+生成+策略学习
* 广告 - 广告主竞价策略：探索 + 利用
