Batch Constrain Q Learning | Hexo

Paper Reading——Off-Policy Deep Reinforcement learning without Exploration

Intro

本文主要探讨了一种名叫Batch Reinforcement Learning的方法，这种方法基于静态数据集进行学习，免去了与环境交互带来的开销

外延误差外延误差外延误差外延误差外延误差外延误差*，即没见过的状态-动作对在算法中被错误估计。外延误差被归结于当前策略产生的状态分布和行为策略产生的分布不同

BCQ算法的目标是在最大化奖励的同时减少state-action pair在训练策略和收集策略中出现概率的差别。

相似相似相似相似相似相似相似相似相似相似**的动作

背景

对于一般的强化学习问题，我们用$(\mathcal S,\mathcal A,p_M,r,\gamma)$描述，定义Bellman最优算子$\Tau^\pi$，它刻画了动作价值函数的性质，记作

$$\Tau^\pi Q(s,a) = E_{s^\prime}[r+\gamma Q(s^\prime,\pi(s^\prime))]$$

求解Q函数实际上变成了求解不动点问题

$$\Tau^\pi Q = Q$$

价值函数更新的范式是

$$Q(s,a) = r+\gamma Q(s^\prime,\pi(s^\prime)),\pi(s^\prime) = \arg\max Q(s^\prime,a)$$

最终策略为

$$\phi \leftarrow \arg\max_\phi E_{s\in \mathcal B}[Q_\theta(s,\pi_\phi(s))]$$

外延误差

实际推断中$(s^\prime,a^\prime)$可能并没有出现在静态数据集中，导致对它的估算不准

导致外延误差的原因

1. 数据缺失(数据集过小)
2. 模型误差，在数据集D上，贝尔曼最优算子被定义为

$$\Tau^\pi Q(s,a) \approx E_{s^\prime \in B}[r+\gamma Q(s^\prime,\pi(s^\prime))]$$

实际上应该来自真实的MDP

1. 训练不匹配，数据集$D=(s,a,r,s^\prime)$产生的loss被写为(TD Loss之和)

$$\frac{1}{|\mathcal B|}\sum_{(s,a,r,s^\prime)\in \mathcal B} \parallel r+\gamma Q(s,\pi_{\theta^\prime}(s^\prime)-Q_\theta(s,a))$$

这里用$\theta,\theta^\prime$区分的是target Q net和Q net，实际上求和号中的每个部分理应有着不同的权重，比如一个状态-动作对出现的概率越高显然权重越高

外延误差的启示

受限于数据集，我们需要在TD loss中增加权重以区分常见和罕见的状态-动作对。同时，在给定数据集上仅能对某些和收集策略相似的策略得到准确的评估

强化学习中的外延误差(本文所做的实验)

batch 1

实时用DDPG训练了100w步，训练中为了增加算法中exploration的部分，对动作增加了服从$\mathcal N(0,0.5)$分布的高斯噪声，保存训练中使用的transition

batch 2

貌似是相比batch 1添加更小的噪声？($\mathcal N(0,0.1)$)

同步训练off-policy和执行动作的DDPG Agent 100w次，执行动作Agent生成的数据用于训练off-policy Agent

边训练边生成数据

batch 3

训练好的DDPG被用作专家，收集得到100w数据集

先训练，再生成数据，最后训练另一个Agent

实验结论

1. offset agent价值估计非常不稳定，但是行为策略的价值估计非常稳定
2. 即便off-policy和behavior agent训练自同一个数据源，off-policy表现仍然比behavior要差(初始policy的差别)

Batch-Constrained Reinforcement Learning

相似相似相似相似相似相似相似相似相似相似相似相似相似相似**的行为有着准确的评估，由此反推得到如下结论

如果一个策略推断得到的动作-状态分布和数据集中类似，则对这个策略估算的价值函数是较为准确的，我们称满足这种条件的策略为batch-constrained

Three Objects for batch training

1. 最小化和收集数据的策略之间的距离
2. 当前策略产生的状态和观察得到的分布相似
3. 最大化价值函数

需要尽量减少距离，才能保证对状态价值准确估计

有限MDP中，扩展损失的影响

随机采样自经验回访数组中的四元组$(s,a,r,s^\prime)$用于更新Q函数

$$Q(s,a)\leftarrow (1-\alpha) Q(s,a)+\alpha (r + \gamma Q(s^\prime,\pi(s^\prime)))\\ \pi(s^\prime) =\arg\max_{a^\prime} Q(s^\prime,a^\prime)$$

先证明从静态数据集B中学习价值函数$\Leftrightarrow$从一个等价MDP过程$\mathcal M_B$中学习价值函数

$\mathcal M_B$和M有着相同的动作和状态空间，状态转移概率为

$$p_{\mathcal B}(s^\prime|s,a)=\frac{N(s,a,s^\prime)}{\sum_{s^\prime} N(s,a,s^\prime)}$$

实际上根据蒙特卡洛采样估算转移概率

定理1：Q学习的等价性

在静态数据集D上进行Q学习，等价于在MDP过程$\mathcal M_B$上进行学习直到收敛(两者具有相同的收敛结果)

定义$\epsilon_{MDP}$为外延损失，视为在Batch数据$ B$上学习的价值函数$Q_\mathcal B^ \pi$和真实策略的价值$Q^\pi$之差，记作

$$\epsilon_{MDP}(s,a) = Q^\pi(s,a)-Q^\pi_{\mathcal B} (s,a)$$

进一步拆分$Q^\pi(s,a)和Q_{\mathcal B}^\pi(s,a)$(Q函数的不动点性质)，于是有

$$\begin{aligned} Q^\pi(s,a)& =\sum_{s^\prime} p_M(s^\prime|s,a) (r(s,a,s^\prime)+\gamma \sum_{a^\prime} \pi(a^\prime|s^\prime) Q^{\pi}(s,a))\\ &=\sum_{s^\prime} p_M(s^\prime|s,a) (r(s,a,s^\prime)+\gamma \sum_{a^\prime} \pi(a^\prime|s^\prime)(Q^\pi_{\mathcal B}(s^\prime,a^\prime)+\epsilon_{MDP}(s^\prime,a^\prime))) \end{aligned}$$ $$\begin{aligned} Q^\pi_{\mathcal B}(s,a) &=\sum_{s^\prime}P_{\mathcal B}(s^\prime|s,a)(r(s,a,s^\prime)+\gamma \sum_{a^\prime} \pi(a^\prime|s^\prime)Q^\pi_{\mathcal B}(s^\prime,a^\prime))\\ &=\sum_{s^\prime}P_{\mathcal B}(s^\prime|s,a)(r(s,a,s^\prime)+\gamma \sum_{a^\prime} \pi(a^\prime|s^\prime)(Q^\pi(s^\prime,a^\prime)-\epsilon_{MDP}(s^\prime,a^\prime))) \end{aligned}$$

上面的推导可以看出，$Q^\pi,Q^\pi_{\mathcal B}$之间本质的区别就是它们刻画的实际上是不同的MDP过程！本质上是因为Monte Carlo对环境的建模存在方差导致的

因此$\epsilon_{MDP}(s,a)$拆分成

$$\begin{aligned} \epsilon_{MDP}(s,a)&=\sum_{s^\prime} (p_M(s^\prime|s,a)-p_{\mathcal B}(s^\prime|s,a))\times r(s,a,s^\prime)+\\ &\sum_{s^\prime} (p_M(s^\prime|s,a)-p_{\mathcal B}(s^\prime|s))\times \gamma \times \sum_{a^\prime}\pi(a^\prime|s)Q_{\mathcal B}^\pi(s^\prime,a^\prime)+\\&\gamma\sum_{s^\prime}p_M(s^\prime|s,a)\times\sum_{a^\prime} \epsilon_{MDP}(s^\prime,a^\prime) \end{aligned}$$

因此$\epsilon_{MDP}$归结于两个原因

1. 不同MDP过程状态概率之差
2. 下一个状态的MDP损失

我们将$\epsilon _{MDP}$写成如下形式(对于$p_M(s^\prime|s,a)=p_{\mathcal B}(s^\prime|s,a)$)的Transition

$$\epsilon_{MDP}^\pi = \sum_s \mu_\pi(s)\sum_a \pi(a|s)|\epsilon_{MDP}(s,a)|$$

由此得到如下推论

$$\epsilon_{MDP}^\pi =0\Leftrightarrow p_{\mathcal B}(s^\prime|s,a)=p_M(s^\prime|s,a),\forall s^\prime\in \mathcal S,\mu_\pi(s)>0 \pi(a|s)\geq 0$$

我们称一个策略是batch-constrained如果满足如下条件

$\forall (s,a)$如果满足$\mu_\pi(s)>0$并且$\pi(a|s)>0$，则有$(s,a)\in \mathcal B$

定理2:如何消除外延误差

对于确定性MDP过程，$\epsilon_{MDP}^\pi=0$当且仅当策略$\pi$是batch-constrained，如果$\mathcal B$是连贯的数据集(收集经验来自若干次决策过程)，其实策略$s_0\in \mathcal B$

Batch-Constrained Deep Reinforcement Learning

BCQ方法引入生成模型，评估动作与batch数据的相似程度，选择价值较高并与数据集尽量相似的动作。将相似度作为value估计的一部分

Batch constraint实现

定义相似矩阵，对于给定状态s，其关联的一个状态-动作序列(s,a)和数据集$\mathcal B$的相似程度使用后验概率$p_{\mathcal B}^G(a|s)$刻画。如果$p_{\mathcal B}^G(a|s)$尽量大，那么对$Q(s,a)$的估计较为准确。对于高维和连续任务，很难直接训练$p_{\mathcal B}^G$，一个替代的想法是训练带参数的生成模型$G_w(s)$，选择动作增加条件

$$a = \arg\max_a p_{\mathcal B}^G (a|s)$$

本文使用自动编码器作为生成模型，刻画潜在动作空间的概率分布。首先根据生成模型$G_w$选择n个动作，再选择价值函数$Q_\theta$中较高的那个

扰动模型(对于连续动作空间)

提升动作的多样性，扰动模型$\epsilon_\phi(s,a,\Phi)$输出在$-\Phi$到$\Phi$之间

$$\pi(s)=\arg\max_{a_i+\epsilon_\phi(s,a,\Phi)}Q_\theta (s,a_i+\epsilon_\theta(s,a_i,\Phi))\\ a_i\in G_w(s)$$

扰动模型的参数完全通过更新Q值实现，写成

$$\phi\leftarrow \arg\max_\phi \sum_{s,a\in \mathcal B}Q_\phi(s,a+\epsilon_\phi(s,a,\Phi))$$

Tradeoff

n和$\Phi$两个超参数实际上是模仿学习和强化学习算法之间的tradeoff

1. n=1，$\Phi =0$，完全变成模仿学习
2. $n\to \infty$，完全变成Q学习

算法概述

一个batch的数据分成多个Mini-batch进行训练

输入和初始化

1. Batch数据$\mathcal B$，迭代次数T
2. 目标网络更新参数$\tau$
3. Mini-batch大小N
4. 最大扰动$\Phi$
5. 采样的动作数n
6. 最小权重$\lambda$
7. 初始化两个Qnet(dualling Q net)，扰动网络$\epsilon_\phi$,VAE网络$G_w=(E_{w_1},D_{w_2} )$

算法(单步迭代)

1. 选择大小为N的四元组$(s,a,r,s^\prime)$
2. 计算$\mu,\sigma=E_{w_1}(s,a),a=D_{w_2}(s,z),z=\mathcal N(\mu,\sigma),w=\arg\min_w \sum{(a-\overline a)62 D_{KL}(\mathcal N(\mu,\sigma)\parallel \mathcal N(0,1))}$
3. 采样n个动作(能否将数据作为某种Ground Truth，训练生成对应的分类器？)
4. 对n个动作加扰动$a_i+\epsilon_\phi(s^\prime,a_i,\Phi)$
5. 计算target value
6. 更新Qnet
7. 更新target Q net

能否直接使用采样的动作，不用添加扰动？

训练更好的分类器/判别器