提出新算法求解多约束强化学习问题，给出样本复杂度理论保证。
Primal-Dual Sample Complexity Bounds for Constrained Markov Decision Processes with Multiple Constraints
- 基于生成模型设计模型化算法，处理多个约束的马尔可夫决策过程。
- 在宽松可行性下需约 $\tilde{\mathcal{O}}(d |S| |A| / (1-γ)^3ε^2)$ 样本。
- 严格可行性下需更多样本，依赖于约束间隙 $ζ_{\mathbf{c}}^*$ 的倒数平方。
本文研究未知转移动态下具有 d > 1 个约束的无限时域马尔可夫决策过程（CMDP）的求解问题，假设可通过生成模型获取样本。提出一种基于模型的算法，在表格设置下针对松弛可行性和严格可行性两种情形，推导并证明了近似最优策略的学习样本复杂度边界。在松弛可行性下，算法所需样本量为 $\tilde{\mathcal{O}} \left( \frac{d |\mathcal{S}| |\mathcal{A}| \log(1/δ)}{(1-γ)^3ε^2} \right)$，可输出 ε-最优策略；在严格可行性下，样本复杂度为 $\tilde{\mathcal{O}} \left( \frac{d^3 |\mathcal{S}| |\mathcal{A}| \log(1/δ)}{(1-γ)^5ε^2{ζ_{\mathbf{c}}^*}^2} \right)$，其中 $ζ_{\mathbf{c}}^*$ 表示约束间隙。该工作首次为多约束 CMDP 提供了紧致的样本复杂度分析。
原文摘要 · Abstract (English)
This paper addresses the challenge of solving Constrained Markov Decision Processes (CMDPs) with $d > 1$ constraints when the transition dynamics are unknown, but samples can be drawn from a generative model. We propose a model-based algorithm for infinite horizon CMDPs with multiple constraints in the tabular setting, aiming to derive and prove sample complexity bounds for learning near-optimal policies. Our approach tackles both the relaxed and strict feasibility settings, where relaxed feasibility allows some constraint violations, and strict feasibility requires adherence to all constraints. The main contributions include the development of the algorithm and the derivation of sample complexity bounds for both settings. For the relaxed feasibility setting we show that our algorithm requires $\tilde{\mathcal{O}} \left( \frac{d |\mathcal{S}| |\mathcal{A}| \log(1/δ)}{(1-γ)^3ε^2} \right)$ samples to return $ε$-optimal policy, while in the strict feasibility setting it requires $\tilde{\mathcal{O}} \left( \frac{d^3 |\mathcal{S}| |\mathcal{A}| \log(1/δ)}{(1-γ)^5ε^2{ζ_{\mathbf{c}}^*}^2} \right)$ samples.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。