Distributional DQN

A Distributional Perspective on Reinforcement Learning

在本文中,我们论证了价值分布(强化学习代理接收的随机回报的分布)的基本重要性。 这与强化学习的通用方法不同,后者为这种回归或价值的期望建模。尽管已经有一套研究价值分布的成熟的体系,但到目前为止,它一直被用于特定目的,例如实施风险敏感的的行为。 我们从策略评估和控制设置的理论结果开始,揭示了后者的显着分布不稳定性。 然后从分布的角度设计了一种新的算法,将Bellman等式应用于近似分布的学习。我们使用街机学习环境中的游戏集来评估我们的算法。我们获得了最新的结果和轶事证据,证明了价值分布在接近配偶强化学习中的重要性。最后,我们从理论和经验两方面论证了价值分布在近似环境下对学习的影响。

从算法的角度来看,学习近似分布而不是近似期望有很多好处。 分布式Bellman算子在有价值分布中保留多模态,我们相信这会导致更稳定的学习。 近似完整分布也减轻了从不稳定的学习的影响。

方法

贝尔曼等式

Qπ(x,a):=EZπ(x,a)=E[t=0γtR(xt,at)]xtP(xt1,at1),atπ(xt),x0=x,a0=a\begin{array}{l}{Q^{\pi}(x, a) :=\mathbb{E} Z^{\pi}(x, a)=\mathbb{E}\left[\sum_{t=0}^{\infty} \gamma^{t} R\left(x_{t}, a_{t}\right)\right]} \\ {x_{t} \sim P(\cdot | x_{t-1}, a_{t-1}), a_{t} \sim \pi(\cdot | x_{t}), x_{0}=x, a_{0}=a}\end{array}

其中 ZZ 是一个分布而不是期望值,为了最大化 QQ 值,通常使用下面的方法

Q(x,a)=ER(x,a)+γEPmaxaAQ(x,a)Q^{*}(x, a)=\mathbb{E} R(x, a)+\gamma \mathbb{E}_{P} \max _{a^{\prime} \in \mathcal{A}} Q^{*}\left(x^{\prime}, a^{\prime}\right)

贝尔曼/最优算子定义

分布贝尔曼算子

仅对算法贡献感兴趣的读者 可以选择跳过这一节

Distributional Equations

(Ω,F,Pr)(\Omega, \mathcal{F}, \mathrm{Pr})是概率空间

up\|\mathbf{u}\|_{p} 表示 uRX\mathbf{u} \in \mathbb{R}^{\mathcal{X}}LpL_{p} 范数

U:ΩRX( or RX×A)U : \Omega \rightarrow \mathbb{R}^{\mathcal{X}}\left(\text { or } \mathbb{R}^{\mathcal{X} \times \mathcal{A}}\right) ,有Up:=[E[U(ω)pp]]1/p\|U\|_{p} :=\left[\mathbb{E}\left[\|U(\omega)\|_{p}^{p}\right]\right]^{1 / p},并且 U=esssupU(ω)\|U\|_{\infty}=\operatorname{ess} \sup \|U(\omega)\|_{\infty}

累积分布函数 FU(y):=Pr{Uy}F_{U}(y) :=\operatorname{Pr}\{U \leq y\} ,逆函数 FU1(q):=inf{y:FU(y)q}F_{U}^{-1}(q) :=\inf \left\{y : F_{U}(y) \geq q\right\}

U:=DVU \overset{D}{:=}V 表示两个随机变量的分布相同

The Wasserstein Metric

定义两个累计分布函数的Wasserstein尺度

dp(F,G):=infU,VUVpd_{p}(F, G) :=\inf _{U, V}\|U-V\|_{p}

其中下界是关于累积分布的所有的随机变量 (U,V)(U, V) ,通过均匀随机变量 U in [0,1]\mathcal{U}\ in\ [0,1] 的逆累计分布函数获得此下限

dp(F,G)=F1(U)G1(U)pd_{p}(F, G)=\left\|F^{-1}(\mathcal{U})-G^{-1}(\mathcal{U})\right\|_{p}

p<p<\infty 时,可写为

dp(F,G)=(01F1(u)G1(u)pdu)1/pd_{p}(F, G)=\left(\int_{0}^{1}\left|F^{-1}(u)-G^{-1}(u)\right|^{p} d u\right)^{1 / p}

对于两个随机变量定义

dp(U,V)=infU,VUVpd_{p}(U, V)=\inf _{U, V}\|U-V\|_{p}

Wasserstein尺度有以下性质

dp(aU,aV)adp(U,V)(Pl)dp(A+U,A+V)dp(U,V)(P2)dp(AU,AV)Apdp(U,V)(P3)\begin{aligned} d_{p}(a U, a V) \leq|a| d_{p}(U, V) &(\mathrm{Pl}) \\ d_{p}(A+U, A+V) \leq d_{p}(U, V) &(\mathrm{P} 2) \\ d_{p}(A U, A V) \leq\|A\|_{p} d_{p}(U, V) &(\mathrm{P} 3) \end{aligned}

引理1、2

Wasserstein尺度引理

Policy Evaluation

定义转移算子 Pπ:ZZP^{\pi} : \mathcal{Z} \rightarrow \mathcal{Z}

PπZ(x,a):=Z(X,A)XP(x,a),Aπ(X)\begin{aligned} P^{\pi} Z(x, a) & :=Z\left(X^{\prime}, A^{\prime}\right) \\ X^{\prime} & \sim P(\cdot | x, a), A^{\prime} \sim \pi(\cdot | X^{\prime}) \end{aligned}

我们定义了分布Bellman算子 Tπ:ZZ\mathcal{T}^{\pi} : \mathcal{Z} \rightarrow \mathcal{Z}

TπZ(x,a):=DR(x,a)+γPπZ(x,a)\mathcal{T}^{\pi} Z(x, a) : \stackrel{D}{=} R(x, a)+\gamma P^{\pi} Z(x, a)

随机性的三个来源定义了复合分布,我们通常假设这三个量是独立的

引理3

这说明 Zk+1:=TπZkZ_{k+1} :=T^{\pi} Z_{k} 在尺度 dp\overline{d}_{p} 下收缩,然而可能不适用于其他的尺度。

Control

最优价值分布和贪心策略定义

最优贝尔曼算子等价于

引理4

因此,我们希望 ZkZ_k 能够快速收敛到一个fixed point,然而这可能很慢或者不确定。实际上,我们可以希望pointwise convergence,即收敛到 nonstationary optimal value distributions。

将定理1与引理4相比较揭示了分布框架和通常的期望设置之间的显著差异。虽然 ZkZ_{k} 的平均值迅速指数收敛到 QQ^* ,但它的分布不需要表现得那么好!为了强调这种差异,我们提供了一些负面结果,如下:

近似分布学习

在本节中,我们提出了一种基于分布Bellman最优性算子的算法。 特别是,这将需要选择近似分布。 已经有人使用过高斯分布了,这里我们考虑使用离散分布。

Parametric Distribution

我们将使用离散分布来模拟价值分布,离散分布具有高度表达和计算友好的优点:

Zθ(x,a)=zi w.p. pi(x,a):=eθi(x,a)jeθj(x,a)Z_{\theta}(x, a)=z_{i} \quad \text { w.p. } p_{i}(x, a) :=\frac{e^{\theta_{i}(x, a)}}{\sum_{j} e^{\theta_{j}(x, a)}}

其中 {zi=VMIN+iz:0i<N},Δz:=VmAxVMINN1\left\{z_{i}=V_{\mathrm{MIN}}+i \triangle z : 0 \leq\right.i<N \},\Delta z :=\frac{V_{\mathrm{mAx}}-V_{\mathrm{MIN}}}{N-1}

Projected Bellman Update

使用离散的分布造成了一个问题:贝尔曼更新 TZθ\mathcal{T} Z_{\theta} 和我们的 ZθZ_{\theta} 几乎总是有disjoint support(https://en.wikipedia.org/wiki/Support_(mathematics))。从前面一节(分布贝尔曼算子)的分析来看,将 TZθ and Zθ\mathcal{T} Z_{\theta} \text { and } Z_{\theta}的 Wasserstein metric(视为损失)最小化之间似乎很自然,但是Wasserstein loss无法在采样的样本下学习。

我们的解决方案是,将贝尔曼更新TZθ\mathcal{T} Z_{\theta} 投影到 ZθZ_{\theta} 的support

给定样本 (x,a,r,x)\left(x, a, r, x^{\prime}\right) ,贝尔曼更新为: T^zj:=r+γzj\hat{\mathcal{T}} z_{j} :=r+\gamma z_{j} ,然后将概率 pj(x,π(x))p_{j}\left(x^{\prime}, \pi\left(x^{\prime}\right)\right) 分配给 T^zj\hat{T} z_{j} 的邻居,第 ii 个投影更新 ΦT^Zθ(x,a)\Phi \hat{\mathcal{T}} Z_{\theta}(x, a) 为:

(ΦT^Zθ(x,a))i=j=0N1[1[T^zj]VminVmaxziΔz]01pj(x,π(x))\left(\Phi \hat{\mathcal{T}} Z_{\theta}(x, a)\right)_{i}=\sum_{j=0}^{N-1}\left[1-\frac{\left|\left[\hat{\mathcal{T}} z_{j}\right]_{V_{\mathrm{min}}}^{V_{\max }}-z_{i}\right|}{\Delta z}\right]_{0}^{1} p_{j}\left(x^{\prime}, \pi\left(x^{\prime}\right)\right)

其中 []ab[\cdot]_{a}^{b} 即限制上下界为 [a,b][a, b]

然后损失函数使用KL散度 DKL(ΦT^Zθ~(x,a)Zθ(x,a))D_{\mathrm{KL}}\left(\Phi \hat{\mathcal{T}} Z_{\tilde{\theta}}(x, a) \| Z_{\theta}(x, a)\right) ,再用梯度下降优化即可

由于此算法离散atom数量在ALE上设置51个效果最好,又被称为C51算法

伪代码

讨论

为什么使用分布DQN?

Reduced chattering 即减少震荡,降低不稳定性

State aliasing 由于部分观测,相似的状态可能Value很不相同,而使用distribution则可以缓解这个问题

A richer set of predictions

Framework for inductive bias 使用distribution可以很容易的添加bound假设

Well-behaved optimization ,使用KL Divergence可以很容易的最小化损失