首个支持随机与对抗性约束的带偏反馈强化学习算法。
Best-of-Both-Worlds Policy Optimization for CMDPs with Bandit Feedback
- 基于策略优化，避免求解复杂凸问题。
- 随机约束下实现√T量级误差与约束违反。
- 适用于实际中只能获取局部反馈的场景。
我们研究了在奖励和约束可能为随机或对抗性情况下的约束马尔可夫决策过程（CMDPs）中的在线学习问题。此前，Stradi 等人（2024）提出了首个能在两种情形下无缝切换的最优最优算法，但仅适用于全反馈环境，且依赖于对占用测度空间的优化，计算效率低下。本文首次提出一种支持带偏反馈的最好两全算法：当约束为随机时，达到$ ilde{ m O}( oot T o)$的后悔和约束违反；当约束为对抗性时，实现$ ilde{ m O}( oot T o)$的约束违反，并获得接近最优奖励的比例。该算法基于策略优化，远比基于占用测度的方法高效。
原文摘要 · Abstract (English)
We study online learning in constrained Markov decision processes (CMDPs) in which rewards and constraints may be either stochastic or adversarial. In such settings, Stradi et al.(2024) proposed the first best-of-both-worlds algorithm able to seamlessly handle stochastic and adversarial constraints, achieving optimal regret and constraint violation bounds in both cases. This algorithm suffers from two major drawbacks. First, it only works under full feedback, which severely limits its applicability in practice. Moreover, it relies on optimizing over the space of occupancy measures, which requires solving convex optimization problems, an highly inefficient task. In this paper, we provide the first best-of-both-worlds algorithm for CMDPs with bandit feedback. Specifically, when the constraints are stochastic, the algorithm achieves $\widetilde{\mathcal{O}}(\sqrt{T})$ regret and constraint violation, while, when they are adversarial, it attains $\widetilde{\mathcal{O}}(\sqrt{T})$ constraint violation and a tight fraction of the optimal reward. Moreover, our algorithm is based on a policy optimization approach, which is much more efficient than occupancy-measure-based methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。