CS285

Imitation learning

behavior cloning

In behavior cloning, we train a policy \(\pi_\theta(a_t|s_t)\) by imitating an expert policy \(π_*(s_t)\) using supervised learning on demonstration data

训练目标

\[ \max_{\theta} \mathbb{E}_{s_t \sim p_{\text{data}}(s_t)} \left[ \log \pi_{\theta} (a_t = \pi^*(s_t) \mid s_t) \right] \]

问题在于

\[ p_{\text{data}}(s_t) \neq p_{\pi_\theta}(s_t) \]

behavior cloning 导致分布漂移，分布误差随 t（rollout长度）线性累积，最终导致 cost（行动误差） 随 t 平方增长

和监督学习的差别：

• IL 的 sample 不是 i.i.d. 的，每个 state-action pair 都依赖于上一个 pair

DAgger (Dataset Aggregation)

Collect data from \(p_{\pi\theta}\) instead of \(p_{data}\) to match distributions

先用人类演示训练一个 policy，然后让 policy 自己 rollout，取其 state(obs)，让人类专家标注演示动作，最后将这条数据合并到原有数据集

model selection

TBD

data collection

TBD

Reinforcement learning

what if we don’t have good demonstration data?

那就需要 RL 登场了

几个基本概念：

• Markov chain

  • 状态 \(\text{s}\in\mathcal{S}\)
  • 状态转移算子 \(\mathcal{T}\)，即概率分布 \(p(s_{t+1}|s_t)\)

  满足 Markov property：\(\mathbf{s}_{t+1}\) 只跟 \(\mathbf{s}_{t}\) 有关，而与之前的 \(\mathbf{s}_{t-1}\) 无关：

  \(\mathbf{s}_{t+1} \perp \mathbf{s}_{t-1} \mid \mathbf{s}_t\)

• Markov decision process (MDP)

  • 状态 \(\text{s}\in\mathcal{S}\)
  • 状态转移算子 \(\mathcal{T}\)
  • 行动 \(\text{a}\in\mathcal{A}\)
  • 奖励函数 \(r : \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}\)

  满足 Markov property：\(\mathbf{s}_{t+1}\) 只跟 \(\mathbf{s}_{t}\) 和 \(\mathbf{a}_{t}\) 有关；\(\mathbf{a}_{t+1}\) 只跟 \(\mathbf{s}_{t+1}\) 有关：

  \(p((\mathbf{s}_{t+1}, \mathbf{a}_{t+1}) \mid (\mathbf{s}_t, \mathbf{a}_t)) = p(\mathbf{s}_{t+1} \mid \mathbf{s}_t, \mathbf{a}_t) \pi_\theta(\mathbf{a}_{t+1} \mid \mathbf{s}_{t+1})\)

• Partially observed Markov decision process 观察到的状态 o，它不等于实际状态 s

RL的目标

最朴素的目标是最大化 reward 期望

\[ J(\theta) = E_\pi \left[ \sum_t r_t \right] \approx \frac{1}{N} \sum_{i=1}^N \sum_t r_t^i \]

\[ \theta^\star = \arg\max_\theta E_{(\mathbf{s},\mathbf{a}) \sim p_\theta(\mathbf{s},\mathbf{a})} [r(\mathbf{s}, \mathbf{a})] \\ \text{\textbf{infinite horizon case}} \]

\[ \theta^\star = \arg\max_\theta \sum_{t=1}^T E_{(\mathbf{s}_t,\mathbf{a}_t) \sim p_\theta(\mathbf{s}_t,\mathbf{a}_t)} [r(\mathbf{s}_t, \mathbf{a}_t)] \\ \text{\textbf{finite horizon case}} \]

RL范式

Policy Gradient

强化学习最直接的目标就是最大化决策轨迹的 reward，即

\[ J(\theta) = \mathbb{E}_{\tau \sim p_\theta(\tau)} \big[ r(\tau) \big] \tag{1} \]

其中轨迹的概率遵循 MDP

\[ p_\theta(\tau) = p(s_0, a_0, \dots, s_{H-1}, a_{H-1}) = p(s_0) \pi_\theta(a_0 \mid s_0) \prod_{t=1}^{H-1} p(s_t \mid s_{t-1}, a_{t-1}) \pi_\theta(a_t \mid s_t), \tag{2} \]

\[ r(\tau) = r(s_0, a_0, \dots, s_{H-1}, a_{H-1}) = \sum_{t=0}^{H-1} r(s_t, a_t). \tag{3} \]

在该目标中，每条 traj 的概率权重是不一样的，而我们需要优化的也就是概率权重 \(p_\theta\) ，让 policy 更可能采到高奖励的行动。为了更方便的求解目标，做如下推导：

\[ \begin{aligned} \text{(LHS)} &= \nabla_\theta \mathbb{E}_{\tau \sim p_\theta(\tau)} \big[ r(\tau) \big] && \text{(7)} \\ &= \nabla_\theta \int p_\theta(\tau) r(\tau) \, d\tau && \text{(8)} \\ &= \int \nabla_\theta p_\theta(\tau) r(\tau) \, d\tau && \text{(9)} \\ &= \int p_\theta(\tau) \cdot \frac{\nabla_\theta p_\theta(\tau)}{p_\theta(\tau)} r(\tau) \, d\tau && \text{(10)} \\ &= \int p_\theta(\tau) \Big[ \nabla_\theta \log p_\theta(\tau) r(\tau) \Big] \, d\tau && \text{(11)} \\ &= \mathbb{E}_{\tau \sim p_\theta(\tau)} \Big[ \nabla_\theta \log p_\theta(\tau) r(\tau) \Big] && \text{(12)} \end{aligned} \]

然后迁移到实际训练目标

\[ \begin{aligned} \nabla_\theta J(\theta) &= \nabla_\theta \mathbb{E}_{\tau \sim p_\theta(\tau)} \big[ r(\tau) \big] && (13) \\ &= \mathbb{E}_{\tau \sim p_\theta(\tau)} \big[ \nabla_\theta \log p_\theta(\tau) r(\tau) \big] && (14) \\ &\approx \frac{1}{N} \sum_{i=1}^N \nabla_\theta \log p_\theta(\tau^i) r(\tau^i) && (15) \\ &= \frac{1}{N} \sum_{i=1}^N \left( \sum_{t=0}^{H-1} \nabla_\theta \log \pi_\theta(a_t^i \mid s_t^i) \right) \left( \sum_{t=0}^{H-1} r(s_t^i, a_t^i) \right), && (16) \end{aligned} \]

不过我们最终优化的未必就是 reward 本身，变种有 reward-to-go、discount、baseline（也就是 advantage，也就是 reward-value）、n-step returns、GAE。统称优势

Variance Reduction

有了上式，我们在实际的训练中遇到最大的问题是采样方差过大。同一个 policy，同个初始 state，可能采出的轨迹五花八门，而且步数越多，轨迹之间偏差越大，最终得到的 \(G_t\) （优势）可能会天差地别，最终回传的梯度方差很大。这会导致学习效率低下，于是就有了很多减小方差的技巧，就是上述提到的各种变种

Reward-To-Go

只计算当前和未来步数的优势

Discount

在 rtg 基础上，对未来的优势乘折扣因子，使得目标更倾向于优化当前优势

Baseline

最原始的版本就是 reward 减去 baseline 常数，这样可以减小采样方差

为了减少实际采样次数，同时避免采样带来的方差，可以引入价值函数，作为对当前及未来优势的估计。价值函数可以取代未来的奖励（优势），同时可以充当 baseline；最原始的版本是 reward(t,...)-value(t)，仅充当 baseline；如果同时用于取代未来奖励，则可以进化为 reward(t)+value(t+1)-value(t)

由于 value 是估计值，所以上述引入价值函数的版本，都会引入偏差（bias）

为了减少 bias，可以增加采样步数，减少预估步数，形式为 reward(t,...,t+n-1)+value(t+n)-value(t)，这样就是 n-step returns；可以看到 1-step returns 就是上述的一个形式，称为 bootstrapped；n 取无穷大，则成为 monte-carlo return；任何 n 都是他俩的折中

将不同的 n-step returns 版本加权平均，就得到了 generalized advantage estimation (GAE) ；GAE 经过推导，可以近似成一种从 t+1 到 t 的递归的推导形式：

TBD

Q-Learning

Q 函数的定义

\[ \begin{align*} Q^\pi(\mathbf{s}_t, \mathbf{a}_t) &= \sum_{t'=t}^T \mathbb{E}_{\pi_\theta} \left[ r(\mathbf{s}_{t'}, \mathbf{a}_{t'}) \;\middle|\; \mathbf{s}_t, \mathbf{a}_t \right] \end{align*} \]

value 函数的定义

\[ \begin{align*} V^\pi(\mathbf{s}_t) &= \sum_{t'=t}^T \mathbb{E}_{\pi_\theta} \left[ r(\mathbf{s}_{t'}, \mathbf{a}_{t'}) \;\middle|\; \mathbf{s}_t \right] \\ &= \mathbb{E}_{\mathbf{a}_t \sim \pi(\mathbf{a}_t|\mathbf{s}_t)} \left[ Q^\pi(\mathbf{s}_t, \mathbf{a}_t) \right] \\ \end{align*} \]

对于上述的各种优势计算，我们可以将其整体替换为 Q 函数估计，用神经网络来预测特定状态、动作组合下的 Q 值；然后需要训练两个神经网络，

第一个，actor，即 policy，用于采样动作，训练使其采到更高 Q 值的动作；

第二个，critic，用于拟合 Q 值，使其对当前状态下 Q 值预测逼近理论值；

DQN

对于离散动作空间，Q 函数输入 state，输出每个 action 的概率，概率越大表明 action 可获取更高的 Q 值。该算法是 DQN

SAC

对于连续动作空间，Q 函数输入 (state, action) 元组，输出标量 Q 值，该算法是 SAC