Reward is enough for convex MDPs
Tom Zahavy, Brendan O'Donoghue, Guillaume Desjardins, Satinder Singh
cs.AI, cs.LG, stat.ML
2021-06-02
把占用测度上的凸目标写成策略与代价的零和博弈,任意标准 RL 算法都能当子程序;双方低遗憾时平均占用以 O(1/√K) 收敛。
标准强化学习把目标写成一件事:找一条策略,让它的占用测度 dπ(状态-动作上的长期访问频率)和奖励向量 r 的内积最大。这条路覆盖了大多数「把标量奖励加总」的任务。
它盖不住的那一类,目标直接写在占用上,而且是凸的。学徒学习要让占用贴近专家;约束 MDP 要在占用上加不等式;纯探索要最大化占用的熵。DeepMind 把这类问题叫做凸 MDP:在可行占用多面体 K 上最小化凸函数 f(dπ)。标准 RL 是 f 取线性时的特例。
核心有两句。存在凸目标,没有任何稳态奖励能把它还原成标准 RL:标准 RL 总有确定性最优策略,负熵这类目标的最优解必须随机。写不成稳态奖励,任意能解标准 RL 的算法仍然能当子程序来解凸 MDP。
转换靠 Fenchel 对偶。凸函数 f 可以写成对偶变量 λ 上的最大化: f(d) = maxλ (λ · d − f(λ))。原问题变成策略玩家和代价玩家的零和博弈,两边都可以交换 min/max。
固定 λ 之后,策略侧就是标准 RL,奖励取 −λ。拿到最优 λ 也不足以只解一次 RL:最优占用往往不是任何一条确定性策略的占用。算法因此输出一串策略,对占用取平均才收敛到凸问题的解。
元算法每轮两步:
Theorem 1 说,策略侧平均遗憾不超过 εK、代价侧不超过 δK,则平均占用的目标值距离最优不超过 εK + δK。两边都是 O(1/√K) 时,间隙就是 O(1/√K)。
凸约束 gi(d) ≤ 0 用拉格朗日再扩一组对偶变量,对占用仍然线性,策略玩家不用换。非凸的 f 也能跑同一套博弈,得到的是弱对偶夹逼,不再保证全局最优。
主结果是样本复杂度。
| 策略玩家 | 代价玩家 | ε-最优的样本依赖 |
| PAC 近似最佳响应 | 遗憾 O(1/K) 的 oracle | O(tmix² SA / ε³)(平均奖励,Lemma 2) |
| PAC 近似最佳响应 | O(1/√K) oracle | O(tmix² SA / ε⁴) |
| UCRL2,非平稳已知奖励 | O(1/√K) oracle | O(D² S² A / ε²)(Lemma 4) |
Hazan 等人用近似 Frank-Wolfe 做纯探索,样本是 O(1/ε³)。UCRL2 路线在 ε 上好一档。两个没收紧的口写在讨论里:代价玩家若每轮单独估占用、不复用旧轨迹,整体会掉回 O(1/ε³);失败概率 δ 的依赖是 1/δ²,作者猜想能收到 log(1/δ)。
Table 1 把已有算法对上这套元算法。FTL 加最佳响应就是 Frank-Wolfe,覆盖 Abbeel 与 Ng 的投影学徒学习和 Hazan 的纯探索;OMD 加最佳响应是 MWAL;OMD 加 RL 覆盖约束 MDP、对抗 MDP 和 Wasserstein GAIL;FTL 加 RL 覆盖 GAIL 和状态边缘匹配。Abbeel 与 Ng 的 max-margin 变体对应 Fully Corrective Frank-Wolfe,在多面体上有线性收敛,比投影变体快,和当年的实验观察一致。
GAIL 和 DIAYN 共用同一项:各技能占用相对平均占用的 KL。GAIL 最小化它,落在凸 MDP 里;DIAYN 最大化它,不在凸框架的保证内。同一套 FTL 梯度碰巧给出相同的内在奖励 log p(z|s) − log p(z)。
实验只在附录。bsuite 的 Deep Sea 上做熵约束 RL:最大化环境奖励,同时要求占用熵不低于该环境最大熵的一半。代价玩家用 FTL,策略玩家用 Impala。原版 Impala 几乎解不开这个必须走对整条动作序列才看得到正奖励的环境;加上熵约束之后,曲线大致追上用 ensemble 处理不确定性的 Bootstrapped DQN。论文没有给出精确回报数字,只放了 Figure 2。
能直接拿走的是一条配方:凸目标对占用求梯度,当成非平稳奖励,塞进现成 RL 算法,最后对策略取平均。学徒学习、约束、探索、GAIL 不再是互不相干的算法家族,而是同一博弈里换了两个玩家。
这是框架工作,不是新的榜单算法。Deep Sea 说明启发式能用,但只有一个硬探索环境,当不了生产证据。真实环境里先确认目标对占用是凸的,并且占用估得动;估不准,代价玩家给的奖励就会漂。
Lemma 4 把代价玩家当成 oracle。真实占用必须从样本估,不复用历史轨迹就会把 O(1/ε²) 吃回 O(1/ε³)。δ 的多项式依赖没有收到对数。收敛对象是平均占用,最后一轮策略不必最优,这对深度 RL 不友好:训练结束时手里那条网络,理论并不保证接近最优。
实验只有 Deep Sea,对比原版 Impala 和 Bootstrapped DQN,没有报具体数字,也没有消融代价玩家的选择。DIAYN 出现在 Table 1,正文却写明它在最大化凸函数。全程假设有限状态动作,函数逼近下的遗憾没有理论。