Note for CS 285, Deep Reinforcement Learning

This is note for CS 285, DRL @ UCB.

Following http://rail.eecs.berkeley.edu/deeprlcourse-fa21/.

Lec 2. Supervised Learning of Behaviors

首先引入一些记号输入的 Observation 记为 $\mathbf o$输入图像输出的 Action 记为 $\mathbf a$预测标签而策略网络Policy记为 $\pi_\theta(\mathbf a \mid \mathbf o)$我们使用下标 $t$ 来表示离散化之后的时间步$\mathbf o_t$$\mathbf a_t$$\pi_\theta(\mathbf a_t \mid \mathbf o_t)$有时我们使用 $\mathbf s_t$ 来表示当前时间步的状态State$\mathbf s_t$$\mathbf o_t$ 的区别在于(1) Observation 是观察到的现象State 是由 Action 决定的反应系统状态的量(2) 仅使用 Observation 可能没办法去推断 State不同的 Observation 可能对应同一个 State(3) 状态 State 往往是被认为满足马尔科夫性质的而 Observation 却不是如此也有的记号用 $\mathbf x_t$ 表示 State$\mathbf u_t$ 表示 Action

image-20230910152826762

Imitation Learning 是一种学习 Policy 的方式它也叫 behavioral cloning即收集了大笔 $\mathbf o_t$ 和专家给出的 $\mathbf a_t$ 对作为训练数据使用有监督学习的方式去进行学习跟常见的有监督学习不同这种方式通常来说是不工作的除非训练数据照顾到足够多的 Corner Cases这是因为 State 的误差会随着多次 Inference 的时间步累积如下图所示

image-20230909231207503

解决方案 1DAgger 想要解决上述的问题Distributional drift Problem解决思路 1 应该是尽可能减少因为误差累积导致的 State 偏差一个可能的解决方案是从训练数据的角度出发我们尽可能照顾到更多的情况如下图所示

image-20230909231654997

也就是说我们尝试去修改我们的训练数据 $p_\text{data} (\mathbf o_t)$我们可以试着以 $p_{\pi_\theta} (\mathbf o_t)$ 作为训练状态然后让人工标注在这个训练状态下需要什么样的 Action $\mathbf a_t$然后使用当前的策略网络去进行推理收集下一个需要标注的状态这种方法叫做 DAggerDataset Aggregation

image-20230909232153665

解决方案 2更好地拟合专家 另一种解决方案是更好地去拟合专家给出的 Action 数据减少单步产生的误差这主要从以下两个方面着手

  • Observation 不满足马尔科夫性质将 Policy 的 Formulation 从 $\pi_\theta(\mathbf a_t \mid \mathbf o_t)$ 改为 $\pi_\theta(\mathbf a_t \mid \mathbf o_t, \mathbf o_{t-1}, \cdots, \mathbf o_1)$这通过采用一些具有记忆功能的网络结构来实现
    • 这样做会一定程度上减轻 Causal Confusion 的问题fixed-capacity policies that are trained to fixed training error on the same demonstrations with access to more information can actually yield worse performance
  • 从人类中学到的 Action 并不是唯一的(1) 可以考虑输出 mixture of Gaussians 作为答案(2) 可以考虑让策略网络输入 latent variable 作为输入将 observation 作为 condition 对 random latent variable 进行 decode(3) 自回归离散化 Autoregressive discretization逐个输出维度进行离散化后对 softmax 之后的结果采样将采样得到的结果输入另一个网络中进行下一个输出维度的离散化和采样如此迭代

解决方案 3更稳定的 trajectory 我们也可以让 trajectory 的性质更稳定对微小误差有容忍度来解决 Distributional drift 的问题具体方案在后面的章节介绍

小结Imitation Learning 这种范式的固有问题就是需要人类专家来提供数据而这往往是有限或者在表示方式上十分困难的

Cost functionsReward functions 的相关介绍从一个具体例子出发我们可以形式化表示我们的目标为

$$\min _\theta E_{\mathbf{a} \sim \pi_\theta(\mathbf{a} \mid \mathbf{s}), \mathbf{s}^{\prime} \sim p\left(\mathbf{s}^{\prime} \mid \mathbf{s}, \mathbf{a}\right)}\left[\delta\left(\mathbf{s}^{\prime}=\text { eaten by tiger }\right)\right] \\ \Rightarrow \min _\theta E_{\mathbf{s}_{1: T}, \mathbf{a}_{1: T}}\left[\sum_t \delta\left(\mathbf{s}_t=\text { eaten by tiger }\right)\right] \\ \Rightarrow \min _\theta E_{\mathbf{s}_{1: T}, \mathbf{a}_{1: T}}\left[\sum_t c\left(\mathbf{s}_t, \mathbf{a}_t\right)\right] (*) $$

这里 $c(\mathbf s_t, \mathbf a_t)$ 就是 cost function或者我们将 min 改成 max 就是 reward function $r$

Goal-conditioned Policies. 我们将最终的 Goal State 也作为 Policy Network 的输入通过仿真环境采集足够多的数据并筛选到达某个最终 Goal 的数据出来进行 Retrai

image-20230910002855958

Lec 4. Introduction to Reinforcement Learning

Notations

Markov Decision Process (MDP)

image-20230910153641900

$r$ : $\mathcal S \times \mathcal A \rightarrow \mathbb R$, 是 reward function.

Partially-observed MDP

image-20230910153835737

强化学习的 Objective 由于 Markov 性质我们可以将强化学习的目标写成

$$\begin{gathered} \underbrace{p_\theta\left(\mathbf{s}_1, \mathbf{a}_1, \ldots, \mathbf{s}_T, \mathbf{a}_T\right)}_{p_\theta(\tau)}=p\left(\mathbf{s}_1\right) \prod_{t=1}^T \pi_\theta\left(\mathbf{a}_t \mid \mathbf{s}_t\right) p\left(\mathbf{s}_{t+1} \mid \mathbf{s}_t, \mathbf{a}_t\right) \\ \\ \theta^{\star} =\arg \max _\theta E_{\tau \sim p_\theta(\tau)}\left[\sum_t r\left(\mathbf{s}_t, \mathbf{a}_t\right)\right] \\ =\arg \max _\theta \sum_{t=1}^T E_{\left(\mathbf{s}_t, \mathbf{a}_t\right) \sim p_\theta\left(\mathbf{s}_t, \mathbf{a}_t\right)}\left[r\left(\mathbf{s}_t, \mathbf{a}_t\right)\right] \end{gathered} $$

这里 $\tau$ 表示整个 trajectory$p_\theta\left(\mathbf{s}_t, \mathbf{a}_t\right)$ 是 state-action marginal distribution

当我们考虑无穷步的时候由于 $p_\theta\left(\mathbf{s}_t, \mathbf{a}_t\right)$ 最终会收敛成静态分布 $p_\theta\left(\mathbf{s}, \mathbf{a}\right)$我们可以将强化学习的目标写成

$$\theta^{\star}=\arg \max _\theta \frac{1}{T} \sum_{t=1}^T E_{\left(\mathbf{s}_t, \mathbf{a}_t\right) \sim p_\theta\left(\mathbf{s}_t, \mathbf{a}_t\right)}\left[r\left(\mathbf{s}_t, \mathbf{a}_t\right)\right] \rightarrow E_{(\mathbf{s}, \mathbf{a}) \sim p_\theta(\mathbf{s}, \mathbf{a})}[r(\mathbf{s}, \mathbf{a})] $$

Value Functions

image-20230910162227134

image-20230910162501088

Algorithms

The anatomy of a RL Algo. is a loop of following three steps:

  • Generate Samples (i.e. run the policy)
  • Fit a model, and then estimate the return
  • Improve the policy

image-20230910162725476

image-20230910163605865

在考虑 sample efficiency 时off policy 是说 sample 与 policy 无关on policy 是说如果 policy 修改就需要生成新的 sample

image-20230910163741440

Lec 5. Policy Gradients

我们考虑对 Objective 进行求梯度

$$\begin{aligned} &\theta^{\star}=\arg \max _\theta \underbrace{E_{\tau \sim p_\theta(\tau)}\left[\sum_t r\left(\mathbf{s}_t, \mathbf{a}_t\right)\right]}_{J(\theta)}\\ &\begin{gathered} J(\theta)=E_{\tau \sim p_\theta(\tau)}[r(\tau)]=\int p_\theta(\tau) r(\tau) d \tau \\ \end{gathered} \end{aligned} $$

进行简单的代换我们有

image-20230910224304717

由于

$$\log p_\theta(\tau)=\log p\left(\mathbf{s}_1\right)+\sum_{t=1}^T \left( \log \pi_\theta\left(\mathbf{a}_t \mid \mathbf{s}_t\right)+\log p\left(\mathbf{s}_{t+1} \mid \mathbf{s}_t, \mathbf{a}_t\right)\right) $$

而且

$$\nabla_\theta\log p\left(\mathbf{s}_1\right) = 0, \\ \nabla_\theta\log p\left(\mathbf{s}_{t+1} \mid \mathbf{s}_t, \mathbf{a}_t\right) = 0, $$

于是

$$\nabla_\theta J(\theta)=E_{\tau \sim p_\theta(\tau)}\left[\left(\sum_{t=1}^T \nabla_\theta \log \pi_\theta\left(\mathbf{a}_t \mid \mathbf{s}_t\right)\right)\left(\sum_{t=1}^T r\left(\mathbf{s}_t, \mathbf{a}_t\right)\right)\right] $$

然后我们可以用采样 N 个小样本作为一个 Batch 的方法来对期望值进行估计

image-20230910224815354

image-20230910225128255

这个 formulation 在 partially observed (no states but observations) 的情况下也适用

Policy gradient 的方法也有一定的问题比如在下图所示

image-20230910234333172

image-20230910234411440

这是 Policy gradient 方法存在的 High Variance 问题具体来说上述两幅图的有颜色的线段代表 samplebar 代表 reward 的大小横轴表示 trajectory蓝色的线表示在某个 Policy 下的 possibility distribution上下两幅图的区别是给 reward function 加了一个常量而这导致这次对策略的更新变得十分不稳定如果采到的数据集足够大这个问题自然可以缓解但在有限数据集下这个问题仍然存在

This problem can be identified as follows. Without any a prior model of the system we’re seeking to optimize, we begin with a policy whose distribution of actions over a given state is effectively uniform. Of course, as we train the model we hope to shape the probability density so that it’s unimodal on a single action, or possibly multimodal over a few successful actions that can be taken in that state. However, acquiring this knowledge requires our model to observe the outcomes of many different actions taken in many different states. This is made exponentially worse in continuous action or state spaces as visiting even close to every state-action pair is computationally intractable.

Variance Reduction 的有关方法这里首先介绍 reward to go 方法这个方法基于 causality即当 $t \lt t'$$t$ 时刻获得的 reward 不会被 $t'$ 时刻做出的策略影响即现在的策略的更新方向不应该与过去的 reward 有关这也就是说我们可以将 policy gradient 的 formulation 修改为

$$\nabla_\theta J(\theta) \approx \frac{1}{N} \sum_{i=1}^N \sum_{t=1}^T \nabla_\theta \log \pi_\theta\left(\mathbf{a}_{i, t} \mid \mathbf{s}_{i, t}\right) \underbrace{(\sum_{t'=t}^T r\left(\mathbf{s}_{i, t^{\prime}}, \mathbf{a}_{i, t^{\prime}}\right)}_{\begin{array}{c} \text { "reward to go" } \\ \hat{Q}_{i, t} \end{array}}) $$

然后是 Baseline 方法这个方法的 intuition 非常简单即我们让比平均更好的 policy 的 reward 是正数不然 reward 是负数我们只需要简单修改

image-20231008024353485

方法的正确性可以被证明即使从 reward function 中减去了一项对于 policy gradient 的期望估计仍然是无偏的同时我们还可以通过对 policy gradient 的方差对 b 求偏导的方式derive 出可以使 policy gradient 方差最小的 b 值

Off-policy Policy Gradients. 上述的 Policy Gradients 方法是经典的 On-policy 方法因为每次对 Policy Network 进行更新后都要重新采样数据因为 underlying distribution of trajectories 发生了改变而我们在估计 $\nabla_\theta J(\theta)$ 时需要在 $E_{\tau \sim p_\theta(\tau)}$ 的设定下采样这里我们尝试解决如果我们没有从 $p_\theta(\tau)$ 从采样的数据而只有从另一个分布 $\bar{p}(\tau)$ 中采样的数据的问题这里的解决方法叫做 Importance Sampling.

image-20231008025328594

image-20231008025458518

这样我们可以从某个时刻的 Policy 中采样一些数据然后用来优化另一个时间步的 Policy

image-20231008025847265

我们可以再将 causality 的考量加进去这样得到 Off-policy 的 Policy Gradients 算法的新版本

image-20231008030141540

但是最后一项从 t’‘=t 到 t’‘=t’Importance Weight 往往因为是多个 <1 的数相乘而变得很小在实际运用时往往忽略本项即使忽略也不影响正确性会得到一个 Policy Iteration 算法

image-20231008031023217

同时Policy gradient 还有一些其他的数值上的问题比如下面这个例子

image-20231008034637690

我们可知这时最优的 $\theta$$k=-1, \sigma \rightarrow 0$ 时取得但是我们可以看到右图中policy gradient 的方向并不总是指向 optimal solution这时因为在 $\sigma \rightarrow 0$由于导数的数值精度问题大部分精力用于优化 $\sigma$从数值分析的角度这是只考虑了一阶导数所导致的

下面是解决这个问题的方法我们考虑一次优化的过程我们现在是在 Parameter Space 搜索使得在一个 Step 变化不超过 $\epsilon$ 的前提下寻找可以最大化 reward value 的方式而这样做是有问题的因为有些参数的 gradient 相对于其他参数的 gradient 来说在数值意义上更加 bad-conditioned于是取而代之的我们不在参数空间考虑而是在 Policy space 上考虑寻找一个在 Policy 变化不大的情况下的优化 Step其中 Policy 的变化用类似于 KL 散度的 divergence 度量来衡量这里我们用 KL 散度的二阶近似展开结果如下图所示

image-20231008035712021

这里可以将结果写成

image-20231008040240492

c.f. Trust Region Policy Optimization.

Lec 6. Actor-Critic Algorithms

Actor-Critic 算法基于 Policy Gradients 算法的基础上改进将表示 reward to go 的 Q 函数与表示状态价值的 V 函数视为可学习的这样做是为了减少只 sample 一条或几条 trajectory 去估计 Q 和 V 时的误差

image-20231008045136911

我们这里给出 Advantage Function $A^\pi(\mathbf s_t, \mathbf a_t)$ 的定义如下

image-20231008045352674

有了这些函数的定义后我们首先决定要去拟合其中的哪些函数我们首先可以近似地将 Q 和 A 表示成 V

image-20231008050002515

Policy Evaluation. 我们接下来关注拟合 $V^\pi$ 函数的过程这个过程也被叫做 Policy Evaluation比较 Naive 的拟合方法是使用 Monte Carlo evaluation即每次都将仿真器的状态 reset 回 $\mathbf s_t$然后 rollout 多次取 reward 的平均值我们可以进一步优化这个 rollout 的过程一般叫做 bootstrapped estimate将考虑拟合的 V 函数 target 近似如下

image-20231008051058971

Discount Factors. 使用 bootstrapped estimate 去做 policy evaluation 时如果是对于 episodic 的任务可能没有很大问题但如果是对于 infinite horizon 的任务如果每一步都用估计的 V 值的话可能最终会 accumulate 到正无穷解决的方法是用下图所示的 simple trick, where $\gamma \lt 1$

image-20231008052047673

我们可以根据以上分析导出 online 的 Actor-Critic 算法

image-20231008053205903