大规模分布式强化学习训练，使用多个actor搜集trajectory，使用1个或是多个带GPU的learner负责计算梯度，更新agent。Learner之间随机交换梯度、同步参数。Actor只需要cpu运行搜集trajectory，需要定期从Learner获取最新版本的参数。
这时就需要使用importance sample方法来让旧策略搜集的轨迹，在新策略的learner里能off-policy更新。
对比A3C里actor对learner传递梯度，importance sample传递的是$(s, a, \pi_{old}(s))$，相比之下的数据传输量小，传输负担轻。
回忆GAE对优势函数的估计方法：
$\hat{A}^{GAE}(t)= \sum\limits_{l=0}^{\infty} (\gamma\lambda)^{l} \delta_{t+l}$
where
$\delta{t}=r_t + \gamma V(s_{t+1}) – V(s_t)$
我们类似地定义一个针对V的估计：
$v_s = V(s_t) + \sum\limits_{l=0}^{\infty} \gamma^{l} \left(\prod_{i=0}^{l-1}c_i\right) \rho_{t+l}\delta_{t+l}$
这里把$\lambda$换成了$c_i$，where $c_i=min(\bar{c}, \frac{\pi(a_i \mid s_i)}{\pi_{old}(a_i \mid s_i)})$，是importance ratio的上界在常数$\bar{c}$位置的截取。
此外$\rho_{t+l}=min(\bar{\rho}, \frac{\pi(a_{t+l} \mid s_{t+l})}{\pi_{old}(a_{t+l} \mid s_{t+l})})$，是在不同地方截取的importance ratio乘到了$\delta$上，试图把使用旧轨迹的数据计算出的$\delta_t$转化为当前新参数策略下的$\delta_t$。
最后在修改后的Advantage估计上，添加了$V(s_t)$。
这样$v_s$即可作为$V_{\sigma}(s_t)$的target，在训练AC里的criti （参数$\sigma$）时更新value function。
而在更新AC的actor （参数$\theta$）时，只需要把原本的一步TD
$ (r_t + \gamma V(s_{t+1}) – V(s_t)) \nabla_{\theta} log \pi_{\theta}(a_t \mid s_t)$
替换成
$ (r_t + \gamma v_{s+1} – V(s_t)) \rho_t \nabla_{\theta} log \pi_{\theta}(a_t \mid s_t)$
where $\rho_t = min(\bar{\rho}, \frac{\pi(a_t \mid s_t)}{\pi_{old}(a_t \mid s_t)})$
这里把$V(s_{t+1})$改成了估算值$v_{s_{t+1}}$，之后添加了importance ratio $\rho_t$
要解释清楚V-trace的原理，需要先证明不同learner学习的估算$v_s$是收敛的。
定义V估算operator $\hat{R}V(s_t):=\mathbb{E}_{\pi_{old}}[v_s]$
$=\mathbb{E}_{\pi_{old}}[V(s_t) + \sum\limits_{l=0}^{\infty} \gamma^{l} \left(\prod_{i=0}^{l-1}c_i\right) \rho_{t+l}\delta_{t+l}]$
当t=0时，起点的$V(s)=\mathbb{E}_{\pi_{old}}[V(s)] \mid s=s_0$，所以放到预期括号外。
$=V(s) + \mathbb{E}_{\pi_{old}}[\sum\limits_{l=0}^{\infty} \gamma^{l} \left(\prod_{i=0}^{l-1}c_i\right) \rho_l \left( r_l + \gamma V(s_{l+1}) – V(s_{l}) \right)]$
展开后把$\rho_{l=0}$的一项扔到外面，再把剩下的按$V(s_{l+1})$项合并，可得：
$\hat{R}V(s) = (1 – \mathbb{E}_{\pi_{old}}[\rho_0]) V(s) + \mathbb{E}_{\pi_{old}} \left[ \sum\limits_{l=0}^{\infty} \gamma^{l} \left(\prod_{i=0}^{l-1}c_i\right) \left[ \rho_l r_l + \gamma(\rho_l – c_l\rho_{l+1}) V(s_{l+1}) \right] \right]$
注意到$\prod$项里最新的$c_{l}$原本属于$\hat{R}$的$l+1$项，被合并至$l$项之后，与$\prod_{i=0}^{l-1}c_i$相乘正好能够还原成$l+1$项里的$\prod_{i=0}^{l}c_i$，于是$c_i$的连乘就是这样迭代形成的。
假如两个learner，在初始$\pi_{old}$相同的情况下，通过不同batch学习更新出两个value函数$V_1(s)$和$V_2(s)$，则
$\hat{R}V_1(s)- \hat{R}V_2(s) = (1 – \mathbb{E}_{\pi_{old}}[\rho_0])(V_1(s)-V_2(s)) + \text{\\}$
$\mathbb{E}_{\pi_{old}}\left[ \sum\limits_{l=0}^{\infty} \gamma^{l+1} \left(\prod_{i=0}^{l-1}c_i\right) (\rho_l – c_l\rho_{l+1}) \left[V_1(s_{l+1}) – V_2(s_{l+1}) \right] \right]$
这里两个learner的$\rho_l r_l$项抵消了，因为旧策略生成轨迹的这项预期应该是一样的。
而两个learner的actor由于交换梯度、同步参数等操作，得到的$\rho_l$和$c_i$理论上也应该是一样的。
把第一项的$1 – \mathbb{E}_{\pi_{old}}[\rho_0]$看作$\mathbb{E}_{\pi_{old}}[\rho_{-1} – \rho_0]$，以及让$\rho_{-1}=1$，$c_{-1}=1$的话，就可以合并第一项与第二项，同时移动index $l \rightarrow l-1$得到：
$\hat{R}V_1(s)- \hat{R}V_2(s) = \mathbb{E}_{\pi_{old}}\left[ \sum\limits_{l=0}^{\infty} \gamma^{l} \left(\prod_{i=0}^{l-2}c_i\right) (\rho_{l-1} – c_{l-1}\rho_{l}) \left[V_1(s_{l}) – V_2(s_{l}) \right] \right]$
右边可以看作是$V_1(s_{l}) – V_2(s_{l})$的linear combination，即以任意state为起点时，$\hat{R}V_1(s)- \hat{R}V_2(s) $都可以视作是根据未来状态$l \ge 0$线性组合形成的函数，线性组合的coefficient 是$\alpha_l = \gamma^{l} \mathbb{E}_{\pi_{old}}\left[ \left(\prod_{i=0}^{l-2}c_i\right) (\rho_{l-1} – c_{l-1}\rho_{l}) \right] \forall l\ge 0$。
每个coefficient都大于等于0，因为只要满足超参$\bar{\rho} \ge \bar{c}$，就有$\mathbb{E}[\rho_{l-1} – c_{l-1}\rho_{l}] \ge \mathbb{E}[c_{l-1} (1 – \rho_{l})] \ge \mathbb{E}[c_{l-1}] \left( 1-\mathbb{E}[MIN(\bar{\rho}, \frac{\pi}{\pi_{old}})] \right) $
而显然$\mathbb{E}_{\pi_{old}}[MIN(\bar{\rho}, \frac{\pi}{\pi_{old}})] \le \mathbb{E}_{\pi_{old}}[\frac{\pi}{\pi_{old}}] = 1$
所以$\alpha_l \ge \mathbb{E}_{\pi_{old}}[c_{l-1}]\mathbb{E}_{\pi_{old}}[1-\rho_{l}]$右边面两项是预期值大于等于0的项相乘，得到linear combination的coefficient都大于等于0的结论。
那么所有$\alpha_l \ge 0$相加，即
$\sum\limits_{l \ge 0} \gamma^l \mathbb{E}_{\pi_{old}}\left[ \left( \prod_{i=0}^{l-2} c_i \right) (\rho_{l-1} – c_{l-1}\rho_l) \right]$
$=\sum\limits_{l \ge 0} \gamma^l \mathbb{E}_{\pi_{old}} \left[ \left( \prod_{i=0}^{l-2} c_i \right) \rho_{l-1} \right] – \left( \gamma^{-1} + \sum\limits_{l \ge 0} \gamma^l \mathbb{E}_{\pi_{old}} \left[ \left( \prod_{i=0}^{l-1} c_i \right) \rho_{l} \right] \right) + \gamma^{-1}$
$=\sum\limits_{l \ge 0} \gamma^l \mathbb{E}_{\pi_{old}} \left[ \left( \prod_{i=0}^{l-2} c_i \right) \rho_{l-1} \right] – \left( \gamma^{-1} + \sum\limits_{l \ge 1} \gamma^{l-1} \mathbb{E}_{\pi_{old}} \left[ \left( \prod_{i=0}^{l-2} c_i \right) \rho_{l-1} \right] \right) + \gamma^{-1}$
$=\sum\limits_{l \ge 0} \gamma^l \mathbb{E}_{\pi_{old}} \left[ \left( \prod_{i=0}^{l-2} c_i \right) \rho_{l-1} \right] – \gamma^{-1} \left( \sum\limits_{l \ge 0} \gamma^{l} \mathbb{E}_{\pi_{old}} \left[ \left( \prod_{i=0}^{l-2} c_i \right) \rho_{l-1} \right] \right) + \gamma^{-1}$
$=\gamma^{-1} – (\gamma^{-1} -1) \sum\limits_{l \ge 0} \gamma^l \mathbb{E}_{\pi_{old}} \left[ \left( \prod_{i=0}^{l-2} c_i \right) \rho_{l-1} \right] $
其中$\sum\limits_{l \ge 0} \gamma^l \mathbb{E}_{\pi_{old}} \left[ \left( \prod_{i=0}^{l-2} c_i \right) \rho_{l-1} \right] \ge 1+\gamma \mathbb{E}_{\pi_{old}} \left[ \rho_0 \right]$，因为后面还有$\rho_1, \rho_2, \rho_3, …$等剩下的项。
于是$\sum\limits_{l} \alpha_l \le \gamma^{-1} -(\gamma^{-1} – 1)(1+\gamma\mathbb{E}_{\pi_{old}}[\rho_0]) $
$=1-(1-\gamma) \mathbb{E}_{\pi_{old}}[\rho_0]$
所以只要$\mathbb{E}_{\pi_{old}}[\rho_0] > 0$，就有$\sum\limits_{l} \alpha_l < 1$
而importance ratio预期值在起点时>0一般都是满足的。
所以$|\hat{R}V_1(s)-\hat{R}V_2(s)| \le \eta |V_1(s) – V_2(s)|$
where
$\eta = \gamma^{-1} – (\gamma^{-1} -1) \sum\limits_{l \ge 0} \gamma^l \mathbb{E}_{\pi_{old}} \left[ \left( \prod_{i=0}^{l-2} c_i \right) \rho_{l-1} \right] $
$\le 1-(1-\gamma) \mathbb{E}_{\pi_{old}}[\rho_0] < 1$
于是多个Learner的value function在使用estimator $v_s = \hat{R}V(s)$时的收敛性被证明，只需要满足截取条件$\bar{\rho} \ge \bar{c}$即可。
这个收敛的value函数，可以学习到一个收敛的策略，把该策略记作$\pi_{\bar{\rho}}$，同时把收敛后的value函数记作$V^{\pi_{\bar{\rho}}}$
根据最开始的actor更新公式，
$grad = (r_t + \gamma v_{s+1} – V(s_t)) MIN(\bar{\rho}, \frac{\pi(a_t \mid s_t)}{\pi_{old}(a_t \mid s_t)}) \nabla_{\theta} log \pi_{\theta}(a_t \mid s_t)$
可反推1步TD的形式：
$\mathbb{E}_{\pi_{old}}[(r_t + \gamma v_{s+1} – V(s_t)) MIN(\bar{\rho}, \frac{\pi(a_t \mid s_t)}{\pi_{old}(a_t \mid s_t)}) ]$
收敛后$v_s \rightarrow V^{\pi_{\bar{\rho}}}(s)$，$V(s_t) \rightarrow V^{\pi_{\bar{\rho}}}(s)$
所以新策略在旧轨迹上的1步TD在收敛后满足
$\sum\limits_{a} \pi_{old}(a \mid s_t) MIN(\bar{\rho}, \frac{\pi(a \mid s_t)}{\pi_{old}(a \mid s_t)}) [r(s_t, a) + \gamma \sum\limits_{x} p(x \mid s_t, a) V^{\pi_{\bar{\rho}}}(x) – V^{\pi_{\bar{\rho}}}(s_t)]$
$=\sum\limits_{a} MIN(\bar{\rho}\pi_{old}(a \mid s_t), \pi(a \mid s_t)) [r(s_t, a) + \gamma \sum\limits_{x} p(x \mid s_t, a) V^{\pi_{\bar{\rho}}}(x) – V^{\pi_{\bar{\rho}}}(s_t)]$
可以看出如果定义策略$\pi_{\bar{\rho}} = MIN(\bar{\rho}\pi_{old}(\cdot \mid s_t), \pi(\cdot \mid s_t))$，那么1步TD的差，可以看作是新策略下的bellman equation，在收敛后应该成为0。
总结一下两个truncation的作用：
$\bar{\rho}$负责调整$\pi_{\bar{\rho}}$是更接近$\pi$还是$\pi_{old}$，如果$\bar{\rho} \rightarrow \infty$那么min操作总会获得$\pi$。如果$\bar{\rho} \rightarrow 0$那么min操作后再归一化，就总会获得$\pi_{old}$
$\bar{c}$负责影响operator $\hat{R}$作用在$V_1(s) – V_2(s)$上收敛的速度，因为就如同GAE里负责调整远端的td $\delta_l$的权重的$\lambda$一样，高$\bar{c}$会更倾向于放大远端的$\delta_l$，导致更高的variance。反之低$\bar{c}$更倾向于让estimator $v_s$反映近处的$\delta_l$以换取更低的variance，但可能会带来较高的bias。显然在两个learner存在策略差异时，侧重距离起点s近处的estimator的差异$v_{1}(s)-v_{2}(s)$会更小。这点也能从contraction modulus $\eta$上反应出来：
$\eta = \gamma^{-1} – (\gamma^{-1} -1) \sum\limits_{l \ge 0} \gamma^l \mathbb{E}_{\pi_{old}} \left[ \left( \prod_{i=0}^{l-2} c_i \right) \rho_{l-1} \right] < 1$
经过operator $\hat{R}$后计算出的$v_s$，并让它作为target监督value function的训练，每次更新参数后，$V_1(s) -V_2(s)$都会以$\eta$的比例减少（当然考虑学习速率后，减少的幅度也不会这么大，但趋势是一样的）。
