CS5446 0. Overview

Notes for CS5446 Reinforcement Learning.

我们到底要学什么？

RL 的目标可以一句话概括：

在环境（environment）中反复做决策（decision-making），学习一个策略（policy, $\pi$ ），使得长期回报（long-term return）最大化。

啥是好策略？

如果没有评价指标，就谈不上改进策略。RL 通过状态值 State Value 来评价一个策略的好坏。

状态值（state value）($v_\pi(s)$ ) 就是 从状态 $s$ 出发，按照策略 $\pi$ 行动，未来累计回报（return, $G_t$ ）的期望（expected return）。

这个状态值是人为规定的，我们在对问题建模的时候会把这些东西定义好。

而能拿到最大的状态值的策略就是最优策略（optimal policy）($\pi^*$ )

• 最优状态值一定存在
• 最优策略不一定唯一
• 最优策略可以是 deterministic 或 stochastic
  • deterministic 和 stochastic 的区别：我只有 40% 的概率向左走。这就是 stochastic。

怎么算状态值（价值）？

你现在读了这篇博客对你的未来能产生怎么的影响？读这篇博客的对你未来的预期价值是多少？

这个看起来很难计算。困难的点在于未来是无穷长的，而现在的动作能作用的范围是未知的。

为了定义这个问题，我们使用了贝尔曼方程（Bellman equation）刻画了“当前价值”和“下一步价值”的关系：

• $r_\pi$ ：在策略 $\pi$ 下的期望即时奖励（expected immediate reward）
• $P_\pi$ ：在策略 $\pi$ 下的状态转移矩阵（state transition under policy）
• $\gamma$ ：折扣因子（discount factor）

它表达的是：

当前价值 = 当前一步的期望奖励 + 折扣后的下一状态价值的期望

根据贝尔曼方程，给定策略 ($\pi$ )，我们可以求解 ($v_\pi$ ) 并根据这个结果来为策略打分。

怎么找到最优策略？

贝尔曼最优方程（Bellman Optimality Equation）把“在所有策略里找最优”写成一个固定点形式（fixed point equation）：

直观理解：

在每个状态上做“能让即时奖励 + 未来价值最大”的选择，从而得到最优价值与最优策略。

我真的知道 P 和 r 吗？

这就是 RL 的第一次大分叉：model-based vs model-free。

如果我们已知环境模型（environment model：$P$ 和 $r$ ），我们可以做规划（planning），通过迭代逼近最优。

典型算法包括：

1. Value Iteration（价值迭代）: 核心是直接对价值函数做迭代更新（value update），不断接近贝尔曼最优方程的固定点。

2. Policy Iteration（策略迭代）:核心是交替进行：

   1. Policy Evaluation：评估当前策略的价值
   2. Policy Improvement：用价值函数改进策略（policy update）

   直到策略不再变化（收敛）。

3. Truncated Policy Iteration（截断策略迭代） 它把 Value Iteration 和 Policy Iteration 统一到一个框架里： 评估阶段（evaluation）不必精确解到收敛，只做若干步迭代，然后就进入改进阶段（improvement）。

这类“value update + policy update 交替迭代直到收敛”的套路在 RL 中极其普遍。

我没有环境模型，我该怎么办？

如果我们不知道 $P$ 和 $r$ ，就无法直接计算期望。 那么第二种资源是什么？——数据（data）。

最基本的思想是用样本均值近似期望：

没有 model，就用采样估计价值。把依赖模型的评估替换为依赖采样的评估后我们的到了如下基于采样的算法：

• MC Basic
• MC Exploring Starts
• MC $\epsilon$ -greedy

MC 要等一整回合结束才更新，太慢了怎么办？

MC 的一个典型痛点是：更新不够在线（not online），样本利用效率不高。

这引出“增量式更新”的思想：

• Non-incremental：等数据齐了再算平均
• Incremental：每来一个样本就更新一次估计（online update）

增量式计算值的算法有：

1. Robbins-Monro
2. Stochastic Gradient Descent(SGD) 随机梯度下降
3. Batch Gradient Descent(BGD) 批量梯度下降
4. Mini-batch Gradient Descent(MBGD) 小批量梯度下降

基于这些计算值的方法，我们可以得到如下算法：

• TD learning of state values：学 ($v(s)$ )
• SARSA：学动作值（action-value）($q_\pi(s,a)$ )，通常是 on-policy
• Q-learning：学最优动作值 ($q^*(s,a)$ )，通常是 off-policy
• Unified point of view：可以把它们看作不同目标、不同采样/bootstrapping 方式的统一表达

状态空间巨大甚至连续，表格法不行怎么办？

当状态空间（state space）非常大，或者连续时，tabular methods（表格法）无法存储每个状态的价值，也无法泛化到未见状态。

解法是：函数逼近（function approximation）。

Value Function Approximation（VFA）

用一个参数化函数 ($\hat v(s; \mathbf w)$ ) 近似真实价值 ($v_\pi(s)$ )。 把学习变成优化问题：

于是思路回到通用的“优化三步”：

1. 明确目标函数（objective）
2. 求梯度（gradient）
3. 用梯度下降/上升（gradient descent/ascent）优化参数

Neural Network as VFA

神经网络（neural network）是很强的非线性逼近器，因此成为深度强化学习（Deep RL）的核心组件之一。

动作空间很大/连续时，从 value 里做 argmax 很难，能不能直接学策略？

Value-based 的路线通常是：

学 ($v$ ) 或 ($q$ ) → 用 greedy / $\epsilon$ -greedy 导出策略

当动作空间大或连续时，直接从 ($q$ ) 里做 ($\arg\max$ ) 可能很难，或者策略表达能力不足。这就引出 policy-based 方法。

Policy Gradient（策略梯度）

直接参数化策略 ($\pi(a\mid s;\theta)$ )，定义目标 ($J(\theta)$ ) 为平均回报，然后优化：

直觉是：

如果某个动作在某状态下带来更高回报，就提高它被选择的概率。

纯 Policy Gradient 方差大，训练不稳定怎么办？

Policy Gradient 的估计常见问题是方差大（high variance），学习信号不够稳定。 解法是把 value-based 的“评价能力”引入进来做方差降低与稳定训练。

Actor-Critic

Actor-Critic 结合两条路线：

• Actor：负责 policy update（更新策略）
• Critic：负责 value update（估计 value / advantage，给 Actor 提供更稳定的学习信号）

常见家族包括：

• Q-Actor-Critic（QAC）
• Advantage Actor-Critic（A2C / A3C 的思路）
• off-policy actor-critic：通过 importance sampling 实现 off-policy 训练
• Deterministic Policy Gradient（DPG）：适合连续动作的确定性策略

CheatSheet

• 最终目标：针对某个问题，找到一个最优策略，使得长期回报最大化。
• 什么是最优策略(optimal policy $\pi^*$ ): 使用这个策略可以获得最大的状态值(optimal state value), 其他所有的策略都没有它大
• 什么是状态值(state value): 从一个状态出发沿着某种策略（policy）所得到的奖励回报（reward）的平均值（或者说是期望回报）。
  • 状态值越高，说明这个策略越好。
  • 状态值可以用来评估一个策略的好坏。
  • 状态值的定义: $v_{\pi}(s) = \mathbb{E}_{\pi}[G_t | S_t = s], for\ all\ s \in \mathcal{S}$
• 贝尔曼公式(Bellman equation): 用来分析状态值的一个工具。描述了所有状态和状态值之间的关系: $v_{\pi} = r_{\pi} + \gamma P_{\pi}v_{\pi}$
  • 我们可以通过贝尔曼公式来求解状态值
  • 拿到了状态值就可以评估某个策略是否够好
• Policy Evaluation: 求解贝尔曼公式，得到状态值来评价某个策略是否够好的方法叫Policy Evaluation。
• 贝尔曼最优公式（Bellman Optimality Equation）: 求解最优策略的公式，用来找到最优策略: $v = \max_{\pi}(r_{\pi} + \gamma P_{\pi}v) = f(v) $
  • 最优状态值一定存在，但是最优策略不一定唯一
  • 最优策略可能是 deterministic 或者 stochastic
  • 有专门的算法来进行求解最优策略
• model-based 的 RL 最优策略的求解算法：
  1. Value Iteration
  2. Policy Iteration
  3. Truncated Policy Iteration
     1. 是前两者的统一化的表达方法
     2. 前两者是它的特殊情况

  都是迭代式算法，子步骤：

  1. policy update
  2. value update 依据某种策略先估计它的值（policy evaluation），然后根据这个值来更新策略（policy improvement），再根据新的策略来更新值，直到收敛为止。 这种策略是非常普遍适用的 environment model 指的是环境的状态转移概率和奖励函数

• model-free 的 RL 最优策略的求解算法：

  没有 environment model，我就只能用采样的方式来估计状态值.

  也就是说在强化学习中要么我们需要 model 要么我们需要数据做采样，二者必须得有一个。不然就没法学了。 $E[X] \approx \bar{x} = \frac{1}{N} \sum_{i=1}^{N} x_i$ 这个公式表示了对 x 这个事件的随机采样。公式是表示期望值。

  1. MC Basic: 本质上是 policy iteration，把依赖模型的部分换成通过采样的方式来估计状态值
  2. MC Exploring Starts
  3. MC $\epsilon$ -greedy
• incremental 与 non-incremental 的区别：比如我要计算期望 $E[X]$ :
  • non-incremental: 我等所有的数据到位，然后一次就进行求解
  • incremental: 我就可以每次采样一个 x，然后更新期望值
    1. Robbins-Monro
    2. Stochastic Gradient Descent(SGD) 随机梯度下降
    3. Batch Gradient Descent(BGD) 批量梯度下降
    4. Mini-batch Gradient Descent(MBGD) 小批量梯度下降
• 基于 incremental 的经典 RL 算法
  1. TD (Temporal Difference) learning of state values
  2. SARSA learning of action-values
  3. Q-learning: TD learning of optimal action-values
  4. unified point of view
• 如果状态空间非常大，我们怎么做？用 value function representation 来表示状态值来做近似（approximation）, 整体的算法思路是
  1. 明确一个目标函数
  2. 求目标函数的梯度
  3. 用梯度上升或者梯度下降来对目标函数进行优化
• VFA （Value Function Approximation）: 用一个函数来表示状态值，这个函数可以是线性的也可以是非线性的 $\min_w{J(w)} = \mathbb{E}[v_{\pi}(S) - \hat{v}(S, \mathbf{w})]$
  • $J(w)$ 是目标函数，表示了用一个函数来表示状态值，这个函数可以是线性的也可以是非线性的
  • $v_{\pi}(S)$ 是真实的 state value
  • $\hat{v}(S, \mathbf{w})$ 是价值函数的近似
  • 等号右边是真实值与近似值的差值的平均值
  • 我希望找到最优的 $w$ 使得这个差值的平均值最小，这样我们的这个函数近似就是最佳的拟合
  • $w$ 是值函数的参数，是我们要优化的对象
• Neural Network as VFA: 神经网络是一个很好的值方程方式
• from value-based to policy-based: 从值函数到策略函数
  • 上面我们都在讨论如何求解值函数，优化值函数
  • 同样策略如果空间很大，我们也可以用一个函数来表示策略
  • 对于策略函数的参数 $\theta$ , 我们也可以找一个方式对它直接进行优化
• 策略梯度算法（Policy Gradient）: 直接对策略函数的参数 $\theta$ 进行优化
  1. 找目标函数: $J(\theta) = \bar{v}_{\pi}, \bar{r}_{\pi}$
  2. 求目标函数的梯度: $\nabla J(\theta) = \mathbb{E}[\nabla_{\theta} \ln \pi(A | S, \theta)q_{\pi}(S, A)]$
  3. 用梯度上升或者梯度下降来对目标函数进行优化: REFERENCE
• Actor-Critic: 结合了值函数和策略函数
  • Actor: policy update
  • Critic: value update
  1. QAC: Q-Actor-Critic
  2. A2C: Advantage Actor-Critic
  3. off-policy actor-critic:
  • 适用 importance sampling 来实现 off-policy （是一种很重要的把 on policy 转换为 off policy 的方法）
  4. DPG: Deterministic Policy Gradient