deep|RUDDER（回报分解解决强化学习得奖励延迟问题） learning|reinforce

论文链接：https://arxiv.org/abs/1806.07857
本文为笔者阅读该文章的笔记整理，有任何问题欢迎与我交流，邮箱是zengcheng17@mails.ucas.edu.cn / zc0702@outlook.com
#解决奖励延迟的强化学习算法：RUDDER
强化学习
一、回顾马尔可夫决策过程（MDP）：在进行讨论之前我们有必要回顾MDP，MDP是由一个6元组（S,A,R,p,π,γ）唯一确定的，是有限状态集合，是表示t时刻状态的随机变量，A代表动作，代表t时刻动作的随机变量，R代表奖励，代表t时刻的奖励的随机变量，P是转移奖励，比如：
![title](leanote://file/getImage?fileId=5b3ea9a0ab644153560001bb) 表示t时刻处于s状态，并执行a动作，在t+1时刻达到状态并得到奖励r的概率策略是指在状态下的条件概率分布： $\pi(A_{t+1} = a'|S_{t+1}=s')$ 期望奖励为: $r(s,a) = \sum_r rp(r|s,a)$ 回报： $ G_t = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$ 在策略π下的动作-值函数为 $q^{\pi}(s,a) = E_{\pi}[G_t|S_t = s,A_t = a]$ 我们学习的目的是为最大化$G_0$ 二、MDP估计的偏差的方差分析： 1.奖励延迟使学习效果恶化文章用了大量的篇幅说明了奖励延迟造成的问题，在此我们不多做介绍，我们只接受事实，奖励延迟会造成估计的方差变大。
![](leanote://file/getImage?fileId=5b41a94c2f4a7e160300000a) # 三、回报分解以及奖励重新分配 ## 1.回报等价及状态丰富为了解释这个问题，我们要引入两个概念：Return-Equivalent（回报等价）以及state-Enriched(状态丰富)

回报等价的定义：如果两个MDP仅在 p ( r ~ ∣ s , a ) p(\tilde r|s,a) p(r~∣s,a)与 p ( r ∣ s , a ) p(r|s,a) p(r∣s,a)不同，但两者在相同策略下却有相同的期望回报 v ~ 0 π = v 0 π \tilde v_0^{\pi}=v_0^{\pi} v~0π?=v0π?,那么我们称这两个MDP过程是回报等价的。
【deep|RUDDER（回报分解解决强化学习得奖励延迟问题）】回报等价的性质：两个回报等价的过程具有相同的最优策略。
状态丰富的定义：我们称一个MDPP ~ \tilde P P~相比于 P P P是状态丰富的，当且仅当 p p p同构于 p ~ \tilde p p~?的子集,比较直观的描述是说：如果 p ~ \tilde p p~?与 P P P拥有相同的状态、动作、转移概率，以及奖励概率.但是 p ~ \tilde p p~?的状态拥有更多的更多的信息。
状态丰富的性质：状态丰富不改变最优策略以及 Q Q Q-values.

2.延迟奖励的MDP与即时奖励的MDP过程之间的等价首先，考虑一个即时奖励的MDP过程，我们将他转换成一个延时奖励的MDP过程 p ~ \tilde p p~?，这里有一种很显然的转换方式，定义转换后的过程 p ~ \tilde p p~?有如下奖励：

reward:

\begin{equation}
\begin{aligned}
\tilde R_t=\left{
\begin{aligned}
0 \qquad for \quad t \le T\
\sum_{k=0}^T R_{k+1} \qquad for \quad t = T\
\end{aligned}
\right.
\end{aligned}
\end{equation}

state
\begin{equation}
\tilde s_t = (s_t,\rho_t)
\end{equation}
\begin{equation}
\rho_t = \sum_{k=0}^{t+1} r_{k+1},\quad with \quad R_k = r_k
\end{equation}

其中 R k R_k Rk?的分布由 p ( r ∣ s k , a k ) p(r|s_k,a_k) p(r∣sk?,ak?)决定.
在这种情况下，我们有如下性质，如果一个即时MDP过程由上述过程转换成非延时的MDP，我们将有如下两个性质：

最优策略不变
对于 π ~ ( a ∣ s ~ ) = π ( a ∣ s ) \tilde \pi(a|\tilde s) = \pi(a|s) π~(a∣s~)=π(a∣s)我们有 q ~ π ~ = q π ( s , a ) + ∑ k = 0 t ? 1 r k + 1 \tilde q ^{\tilde \pi} = q^{\pi}(s,a) + \sum_{k=0}^{t-1} r_{k+1} q~?π~=qπ(s,a)+∑k=0t?1?rk+1?

（1）我们简单地分析一下为什么最优策略不变，事实上可以验证我们新的MDP可以回报等价于之前的MDP，这样由于回报等价的性质可以说明这件事。
3.最优回报分解现在我们考虑一下相反的方向：对于一个有延时奖励的MDP过程 p ~ \tilde p p~?,我们是否能找到一个return-equivalent的 P P P，我们将把 r ~ T + 1 \tilde r_{T+1} r~T+1?重新分配到前面的奖励中。
对于延时过程 r ~ ( s T , a T ) = E [ R ~ T + 1 ∣ S T , a T ] \tilde r(s_T,a_T) = E[\tilde R_{T+1}|S_T,a_T] r~(sT?,aT?)=E[R~T+1?∣ST?,aT?],这是由动作状态序列 ( s 0 , a 0 , s 1 , . . . , s T , a T ) (s_0,a_0,s_1,...,s_T,a_T) (s0?,a0?,s1?,...,sT?,aT?)得到的，又由于马氏性，实际上 r ~ \tilde r r~只是 ( s T , a T ) (s_T,a_T) (sT?,aT?)的函数，这样我们可以利用的信息将大大下降，为此，我们将序列变为 ( a 0 , Δ ( s 0 , s 1 ) ) , . . . , a T ? 1 , Δ ( s T ? 1 , s T ) , a T ) , (a_0,\Delta(s_0,s_1)),...,a_{T-1},\Delta(s_{T-1},s_T),a_T), (a0?,Δ(s0?,s1?)),...,aT?1?,Δ(sT?1?,sT?),aT?),其中 ( a , Δ ( s , s ′ ) ) (a,\Delta(s,s' )) (a,Δ(s,s′))相互独立。
我们引入几个记号
\begin{equation}
(a,\Delta){0:t}:=(a_0,\Delta(s_0,s_1)),…,a{t-1},\Delta(s_{t-1},s_t),a_t,\Delta(s_t,s_{t+1}))
\end{equation}
我们希望对函数 g g g进行分解
\begin{equation}
g((a,\Delta){0:T})=\sum{k=0}^{T}h(a_t,\Delta(s_t,s_{t+1}))=E[\tilde R_{T+1}|s_T,a_T]=\tilde r(s_T,a_T)
\end{equation}文中给出了三种分解方式Taylor decomposition、LRP分解、integrated gradients。
TODO:本质上是求泛函极小值值得过程，有非常多的经典得方法可以引入，比如直接求这个泛函的frech 导数
4.最优奖励分配现在，假设我们已经有了最优分解，我们来求出奖励分配的方案
\begin{equation}
g((a,\Delta){0:T})=\sum{k=0}^{T}h(a_t,\Delta(s_t,s_{t+1}))
\end{equation}
\begin{equation}
r_{t+1} = \frac{h(a_t,\Delta(s_t,s_t+1))}{g((a,\Delta)){0:T}}\tilde r{T+1}
\end{equation}
于是有， ∑ k = 0 T r ~ t + 1 = r ~ T + 1 = ∑ k = 0 T r t + 1 \sum_{k=0}^{T}\tilde r_{t+1} = \tilde r_{T+1} = \sum_{k=0}^{T} r_{t+1} ∑k=0T?r~t+1?=r~T+1?=∑k=0T?rt+1?
容易计算得
\begin{equation}
r(s_t，a_t) = E[R_t+1|s_t,a_t] = \frac{E[h_t|s_t,a_t]}{\tilde r_{(s_t,a_T)}}=\frac{E[h_t|s_t,a_t]}{\tilde r(s_T,a_T)}\tilde r(s_T,a_T)=E[h_t|s_t,a_t]
\end{equation}
之后它证明了最优分配方案导致了方差变低。
四、具体实现架构

文章图片

用一个LSTM去训练，用来估计累计回报，LSTM的输出由三部分构成，主任务 G 0 G_0 G0?，三个辅助任务(1) q t q_t qt?的预测(2) r t , 10 r_{t,10} rt,10?(3) r 0 , t r_{0,t} r0,t?损失为平方损失。输入图像数据时，LSTM对 G 0 G_0 G0?进行预测，再对其进行分解，得到每个时刻的奖励，在给出奖励的过程中，还会对从而给到PPO算法求解动作和价值函数，在具体实现的时候PPO是需要熟悉的。另外在训练的时候，它会评估 G 0 G_0 G0?估计的好坏，以及分解的质量，只有在两者满足一定条件的时候才会被使用。

PPO论文连接
https://arxiv.org/abs/1707.06347
IG论文连接
https://www.semanticscholar.org/paper/Axiomatic-Attribution-for-Deep-Networks-Sundararajan-Taly/efb7d981665dee38971f6372d0a0a1925b665db8

实验结果

文章图片