标题： 线性约束MDPs的样本复杂度界限与生成模型 显示英文标题

标题： Sample Complexity Bounds for Linear Constrained MDPs with a Generative Model

摘要： 我们考虑无限时间范围的$\gamma$-折扣（线性）约束马尔可夫决策过程（CMDPs），其中目标是找到一个策略，在满足预期累积约束的前提下最大化预期累积奖励。 在可以访问生成模型的情况下，我们提出了一种原始对偶框架来解决CMDPs，该框架可以利用任何黑箱无约束MDP求解器。 对于特征维度为$d$的线性CMDPs，我们通过使用镜像下降值迭代（\texttt{MDVI}）~\citep{kitamura2023regularization}作为一个示例MDP求解器来实例化该框架。 我们在两种情况下提供了所得到的CMDP算法的样本复杂度界限： （i）放松可行性，允许小的约束违反，以及 （ii）严格可行性，要求输出策略精确满足约束。 对于（i），我们证明该算法可以通过使用$\tilde{O}\left(\frac{d^2}{(1-\gamma)^4\epsilon^2}\right)$个样本以高概率返回一个$\epsilon$-最优策略。 我们注意到这些结果在$d$和$\epsilon$上表现出接近最优的依赖关系。 对于 (ii)，我们证明该算法需要$\tilde{O}\left(\frac{d^2}{(1-\gamma)^6\epsilon^2\zeta^2}\right)$个样本，其中$\zeta$是问题相关的 Slater 常数，用于表征可行区域的大小。 最后，我们将框架应用于表格型 CMDPs，并证明它可以用于在此设置中恢复接近最优的样本复杂度。 显示英文摘要

摘要： We consider infinite-horizon $\gamma$-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 $\epsilon$-optimal policy with high probability by using $\tilde{O}\left(\frac{d^2}{(1-\gamma)^4\epsilon^2}\right)$ samples. We note that these results exhibit a near-optimal dependence on both $d$ and $\epsilon$. For (ii), we show that the algorithm requires $\tilde{O}\left(\frac{d^2}{(1-\gamma)^6\epsilon^2\zeta^2}\right)$ samples, where $\zeta$ is the problem-dependent Slater constant that characterizes the size of the feasible region. Finally, we instantiate our framework for tabular CMDPs and show that it can be used to recover near-optimal sample complexities in this setting.