11. 强化学习

11.1 强化学习基础 **

1. 强化学习基础 *

• Environment, Agent, State, Action, Reward

• 马尔可夫决策过程（Markov Decision Process, MDP）

  • Action 上下左右，State 坐标，Reward 移动-1，Time

  • 状态转移 Markov，累计收益 $R=E(\sum_{t=0}^T \gamma^t r_t|s_0=s)$

• 核心任务：学习一个 状态空间S 到 动作空间A 的映射，最大化累计收益

• 常见算法：Q-learning、策略梯度、Actor-Critic

2. 价值迭代 **

• 贝尔曼方程（Bellman Equation）$V_*(S)=\max_a\sum_{s',r} p(s',r|s,a)[r+\gamma V_*(s')]$

  • 采取动作 a 后，带来的奖励 r

  • 采取动作 a 后，到达新状态的价值 $V(s')$

3. 最优路线 **

• 策略评估（Policy Evaluation）

  • 初始化，策略评估，策略提升，迭代直至收敛

11.2 视频游戏里的强化学习 ***

• Q-learning：$Q(s_j,a_j)=E_{s_{j+1}}y_j$，其中 $y_j=r_j+\gamma\cdot \max_a Q(s_{j+1},a)$

  • $Q$ 为 动作效用函数（action-utility function），用于评价在特定状态下采取某个动作的优劣

  • 建立一个 Q-Table，以 State 为行、Action 为列，通过每个动作带来的奖赏更新Q-Table

• 迭代步骤

  • 根据当前的 $Q$ 函数执行一次行动 $a_t$

  • 获得本次收益 $r_t$ 及下个状态 $s_{t+1}$

  • 以某种方式获得一个四元组 $(s_j,a_j,r_j,s_{j+1})$

  • 计算 $y_j$

  • 对 $(y_j-Q(s_j,a_j;\theta))^2$ 执行一次梯度下降，完成参数更新

    • $Q(s_t,a_T)\leftarrow Q(s_t,a_t)+\alpha[r_t+\gamma\max_{a'\in A}Q(s_{t+1},a')-Q(s_t,a_t)]$

• 传统强化学习 vs. 深度强化学习

  • 小概率随机探索、历史回放

• 问题

  • 因为涉及在状态空间上求 Q 函数的最大值，只适用于 离散状态空间

  • 没有 收敛性保证

11.3 策略梯度 Policy Gradient ****

无差别处理 连续/离散 状态空间， 保证至少收敛到 local optima

• 基本思想：直接用 梯度方法 来优化 $R(\theta)$

  • 状态 $s_{t+1}\sim p(s_{t+1}|s_t,a_t)$，策略 $a_t\sim\pi_\theta(a_t|s_t)$ 是分布采样

  • 总收益函数 $R(\theta)=E(\sum_0^T z_t r_t)$，完全由 $\theta$ 决定

  • 与 Q-learning 不同，不估算 $Q$ 函数本身，而是直接生成 $a_t$

• 给定一个策略 $\pi_\theta$，模拟获得一些轨迹 $\tau$，获得 收益 $r(\tau)$ 以及每一步的 <s,a> 对

  • 对应的 梯度 $g(\tau)=\sum_{k=0}^T \nabla_\theta \log\pi_\theta (a_k|s_k)\cdot r(\tau)$，用来更新 $\theta$

11.4 探索与利用 ***

• 平衡 exploration vs. exploitation

• $\epsilon-greedy$ 算法：以 $\epsilon$ 的概率随机探索（不使用历史信息），以 $1-\epsilon$ 的概率选择利用

• 置信区间上界（UCB）算法：每次推荐时，总是乐观地认为每道菜的回报是 $\tilde p+\Delta$

  • Chernoff-Hoeffding Bound：$\Delta=\sqrt{\frac{2\ln T}{n}}$

    • $P\{|\tilde p-p|\le \sqrt{\frac{2\ln T}{n}}\}\ge1-\frac{2}{T^4}$