提出一种高效求解线性约束MDP的算法，理论证明其样本复杂度接近最优。
Sample Complexity Bounds for Linear Constrained MDPs with a Generative Model
- 基于生成模型与对偶框架，可对接任意无约束MDP求解器。
- 允许轻微违反约束时，样本量约需 $\tilde{O}\left(\frac{d^2}{(1-γ)^4ε^2}\right)$。
- 严格满足约束时，样本量依赖于可行域大小参数 $ζ$，且上下界接近。
我们研究无限时长远折扣（线性）约束马尔可夫决策过程（CMDP），目标是寻找在满足期望累积约束条件下最大化期望累积奖励的策略。在生成模型假设下，提出一种基于原始-对偶框架的算法，可调用任意黑箱无约束MDP求解器。针对特征维度为 $d$ 的线性CMDP，使用镜面下降价值迭代（MDVI）作为具体求解器。分别在两种情形下提供样本复杂度上界：（i）放宽可行性（允许小量约束违规），此时算法以高概率返回 $ε$-最优策略，所需样本数为 $\tilde{O}\left(\frac{d^2}{(1-γ)^4ε^2}\right)$；（ii）严格可行性（策略必须精确满足约束），样本数为 $\tilde{O}\left(\frac{d^2}{(1-γ)^6ε^2ζ^2}\right)$，其中 $ζ$ 为刻画可行域大小的问题相关Slater常数。进一步证明严格可行性下的下界为 $Ω\left(\frac{d^2}{(1-γ)^5ε^2ζ^2}\right)$。两种情形的上界在 $d$、$ε$、$ζ$ 上均接近最优。最后，将框架应用于表格型CMDP，恢复了该场景下的近优样本复杂度。
原文摘要 · Abstract (English)
We consider infinite-horizon $γ$-discounted (linear) constrained Markov decision processes (CMDPs) where the objective is to find a policy that maximizes the expected cumulative reward subject to expected cumulative constraints. Given access to a generative model, we propose to solve CMDPs with a primal-dual framework that can leverage any black-box unconstrained MDP solver. For linear CMDPs with feature dimension $d$, we instantiate the framework by using mirror descent value iteration (\texttt{MDVI})~\citep{kitamura2023regularization} an example MDP solver. We provide sample complexity bounds for the resulting CMDP algorithm in two cases: (i) relaxed feasibility, where small constraint violations are allowed, and (ii) strict feasibility, where the output policy is required to exactly satisfy the constraint. For (i), we prove that the algorithm can return an $ε$-optimal policy with high probability by using $\tilde{O}\left(\frac{d^2}{(1-γ)^4ε^2}\right)$ samples. For (ii), we show that the algorithm requires $\tilde{O}\left(\frac{d^2}{(1-γ)^6ε^2ζ^2}\right)$ samples, where $ζ$ is the problem-dependent Slater constant that characterizes the size of the feasible region. Furthermore, we prove a lower-bound of $Ω\left(\frac{d^2}{(1-γ)^5ε^2ζ^2}\right)$ for the strict feasibility setting. We note that our upper bounds under both settings exhibit a near-optimal dependence on $d$, $ε$, and $ζ$. Finally, we instantiate our framework for tabular CMDPs and show that it can be used to recover near-optimal sample complexities in this setting.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。