提出多项式时间算法，高效求解各类约束强化学习问题。
Polynomial-Time Approximability of Constrained Reinforcement Learning
- 设计了通用约束下的多项式时间近似算法
- 首次证明多类约束策略可多项式逼近
- 适合研究强化学习复杂性与算法设计的学者
我们研究了广义约束马尔可夫决策过程的近似计算复杂性。主要贡献是为一大类递归可计算约束（包括几乎必然、概率、期望及其即时变体）设计了多项式时间 (0,ε) 加性双目标近似算法，用于寻找最优约束策略。匹配的下界表明，只要 P≠NP，该近似保证即为最优。该方法的普遍性解决了约束强化学习领域中多个长期悬而未决的复杂性问题。具体而言，我们首次证明了以下情形的多项式时间可近似性：概率约束下的策略、多重期望约束下的确定性策略、非同质约束（即不同类型的约束混合）下的策略，以及连续状态过程中的约束策略。
原文摘要 · Abstract (English)
We study the computational complexity of approximating general constrained Markov decision processes. Our primary contribution is the design of a polynomial time $(0,ε)$-additive bicriteria approximation algorithm for finding optimal constrained policies across a broad class of recursively computable constraints, including almost-sure, chance, expectation, and their anytime variants. Matching lower bounds imply our approximation guarantees are optimal so long as $P \neq NP$. The generality of our approach results in answers to several long-standing open complexity questions in the constrained reinforcement learning literature. Specifically, we are the first to prove polynomial-time approximability for the following settings: policies under chance constraints, deterministic policies under multiple expectation constraints, policies under non-homogeneous constraints (i.e., constraints of different types), and policies under constraints for continuous-state processes.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。