离线约束强化学习的低秩 MDP 原始 - 对偶算法
内容提要
本文综述离线强化学习与原始-对偶优化的进展，包括线性规划原对偶方法、悲观离线线性MDP算法（达极小极大最优）、弱化Bellman完备性等假设并以单策略集中性实现多项式样本复杂度、无探索离线RL、DPDL及策略梯度原对偶算法（保证收敛与低遗憾），以及在线MDP随机原对偶法、无奖励探索和低秩离线策略评估。
延伸解读
离线强化学习中的假设弱化趋势
文章梳理了多篇研究，显示离线强化学习算法设计正逐步弱化传统强假设。例如，2022年2月的工作证明，基于原始-对偶算法可在单策略集中性下实现多项式样本复杂度，而无需Bellman完备性和全策略集中性。2023年6月的Primal-Dual-Critic算法进一步仅需集中性和价值函数/边际重要性加权实现等条件。这反映出领域在降低对数据覆盖和函数逼近的严格要求，使算法更适应实际数据受限场景。
原始-对偶方法在约束与无约束问题中的统一性
文章提及的多个工作均围绕原始-对偶优化展开，覆盖了约束马尔可夫决策过程（CMDP）和无约束MDP。例如，DPDL算法针对离线数据约束MDP，保证无约束违规；而2024年1月的策略梯度原始-对偶算法同时保证收敛至最优策略、次线性遗憾和多项式样本复杂度。这表明原始-对偶框架能灵活处理约束与无约束目标，并在理论保证上取得进展，但具体性能依赖问题设置和假设条件。
低秩结构与无奖励探索的实用潜力
文章提到两项工作值得关注：一是利用隐含低秩结构进行离线策略评估，可估计未被覆盖的状态-动作对的值，并附带离线策略优化算法；二是无奖励强化学习，通过基于内核和神经函数逼近的乐观价值迭代，在任意外界奖励下以O(1/ε²)采样复杂度产生准最优策略或近似Nash均衡。这些方法针对数据覆盖不足和奖励稀疏的挑战，但实际应用效果需进一步验证。
Q&A
离线约束强化学习中的原始-对偶算法主要解决了哪些问题？
原始-对偶算法用于离线约束强化学习，旨在解决在有限数据下学习满足约束的策略的问题。它通过线性规划或策略梯度方法，在不需要强假设（如Bellman完备性）的情况下，实现多项式样本复杂度，并保证收敛性和低遗憾。
离线线性MDP的悲观算法如何实现极小极大最优性？
该算法基于悲观主义，使用参考函数进行不确定性分解，通过理论分析证明其性能可匹配下界，并扩展到两人零和马尔可夫博弈，从而验证了极小极大最优性。这是首个使用线性函数逼近的单智能体MDP和MG的极小极大最优算法。
在离线强化学习中，如何弱化Bellman完备性和全策略集中性假设？
通过基于MDP的原始-对偶算法，可以弱化这些假设，仅需单策略集中性即可实现多项式样本复杂度。这提供了不同假设下的替代分析，为离线RL的原始-对偶算法提供了新方法。
DPDL算法在离线约束MDP中有什么特点？
DPDL算法针对离线数据的约束马尔可夫决策过程，引入了单策略集中度系数，并建立了样本复杂度下界，保证无约束违规。
策略梯度原始-对偶算法在约束MDP中如何保证收敛和低遗憾？
该算法具有均匀概率近似正确性保证，同时保证收敛至最优策略、次线性遗憾和多项式样本复杂度。在简单CMDP示例中，它收敛至最优策略，而现有算法则表现出振荡性能和约束违规。
在线MDP的随机原始对偶方法有哪些优势？
这些方法利用Bellman方程的内在极小极大对偶性进行优化，具有小的存储空间和低的计算复杂度，通过观察新的状态转移更新值和策略估计的少数坐标。对于无限时间折扣奖励MDP，使用O(|S|^4|A|^2σ^2/(1-γ)^6ε^2)的迭代/样本数可以高概率找到绝对ε-最优策略；对于有限时间MDP，迭代次数为O(|S|^4|A|^2H^6σ^2/ε^2)。
