Constrained Markov Decision Processes (CMDPs) formalize sequential
decision-making problems whose objective is to minimize a cost function while
satisfying constraints on various cost functions. In this paper, we consider
the setting of episodic fixed-horizon CMDPs. We propose an online algorithm
which leverages the linear programming formulation of finite-horizon CMDP for
repeated optimistic planning to provide a probably approximately correct (PAC)
guarantee on the number of episodes needed to ensure an $\epsilon$-optimal
policy, i.e., with resulting objective value within $\epsilon$ of the optimal
value and satisfying the constraints within $\epsilon$-tolerance, with
probability at least $1-\delta$. The number of episodes needed is shown to be
of the order
$\tilde{\mathcal{O}}\big(\frac{|S||A|C^{2}H^{2}}{\epsilon^{2}}\log\frac{1}{\delta}\big)$,
where $C$ is the upper bound on the number of possible successor states for a
state-action pair. Therefore, if $C \ll |S|$, the number of episodes needed
have a linear dependence on the state and action space sizes $|S|$ and $|A|$,
respectively, and quadratic dependence on the time horizon $H$.

本文研究了约束马尔可夫决策过程，并提出了一种在线算法，该算法利用了有限时间视角下的线性规划公式来进行乐观规划，以提供概率上正确的 γ 优化策略，该算法逐渐逼近最佳结果，并且保证结果最多只是 γ 深度有损失的结果，并且在指定公差范围内具有概率保证。

具约束的有限时间 MDP 的高样本效率算法

A Sample-Efficient Algorithm for Episodic Finite-Horizon MDP with  Constraints

In many sequential decision-making problems, the goal is to optimize a
utility function while satisfying a set of constraints on different utilities.
This learning problem is formalized through Constrained Markov Decision
Processes (CMDPs). In this paper, we investigate the exploration-exploitation
dilemma in CMDPs. While learning in an unknown CMDP, an agent should trade-off
exploration to discover new information about the MDP, and exploitation of the
current knowledge to maximize the reward while satisfying the constraints.
While the agent will eventually learn a good or optimal policy, we do not want
the agent to violate the constraints too often during the learning process. In
this work, we analyze two approaches for learning in CMDPs. The first approach
leverages the linear formulation of CMDP to perform optimistic planning at each
episode. The second approach leverages the dual formulation (or saddle-point
formulation) of CMDP to perform incremental, optimistic updates of the primal
and dual variables. We show that both achieves sublinear regret w.r.t.\ the
main utility while having a sublinear regret on the constraint violations. That
being said, we highlight a crucial difference between the two approaches; the
linear programming approach results in stronger guarantees than in the dual
formulation based approach.

本文研究了 Constrained Markov Decision Processes 下的 exploration-exploitation trade-off 问题，提出了两种方法：基于线性规划和基于对偶变量逐步更新的方法。研究结果表明，这两种方法都可以实现 sublinear regret，但是线性规划方法具有更强的保障性。