We introduce and study constrained Markov Decision Processes (cMDPs) with
anytime constraints. An anytime constraint requires the agent to never violate
its budget at any point in time, almost surely. Although Markovian policies are
no longer sufficient, we show that there exist optimal deterministic policies
augmented with cumulative costs. In fact, we present a fixed-parameter
tractable reduction from anytime-constrained cMDPs to unconstrained MDPs. Our
reduction yields planning and learning algorithms that are time and
sample-efficient for tabular cMDPs so long as the precision of the costs is
logarithmic in the size of the cMDP. However, we also show that computing
non-trivial approximately optimal policies is NP-hard in general. To circumvent
this bottleneck, we design provable approximation algorithms that efficiently
compute or learn an approximately feasible policy with optimal value so long as
the maximum supported cost is bounded by a polynomial in the cMDP or by the
absolute budget. Given our hardness results, our approximation guarantees are
the best possible in terms of tractability under worst-case analysis.

我们引入并研究了具有任意时间限制的受限马尔可夫决策过程（cMDPs）。我们提出了一种固定参数可处理的方法，将具有任意时间限制的 cMDPs 转化为无约束的 MDPs。我们设计出了适用于大表 cMDPs 的计划和学习算法，并设计了近似算法，可以高效地计算或学习一个近似可行策略。