This paper studies the problem of Anytime-Competitive Markov Decision Process (A-CMDP). Existing works on Constrained Markov Decision Processes (CMDPs) aim to optimize the expected reward while constraining the expected cost over random dynamics, but the cost in a specific episode can still be unsatisfactorily high. In contrast, the goal of A-CMDP is to optimize the expected reward while guaranteeing a bounded cost in each round of any episode against a policy prior. We propose a new algorithm, called Anytime-Competitive Reinforcement Learning (ACRL), which provably guarantees the anytime cost constraints. The regret analysis shows the policy asymptotically matches the optimal reward achievable under the anytime competitive constraints. Experiments on the application of carbon-intelligent computing verify the reward performance and cost constraint guarantee of ACRL.

这篇论文研究了任何时候有竞争性的马尔可夫决策过程（A-CMDP）的问题。现有的约束马尔可夫决策过程（CMDP）的研究旨在优化预期奖励，同时约束于随机动力学下的预期成本，但是在特定情况下成本仍然可能过高。相反，A-CMDP的目标是在任何一轮任何剧集中的策略先验下，通过优化预期奖励来保证有限的成本。我们提出了一种新算法，称为Anytime-Competitive Reinforcement Learning（ACRL），它可以证明保证了任何时候的成本约束。后悔分析显示该策略在任何时候的成本要求下渐近匹配了最优奖励。对碳智能计算应用的实验证明了ACRL的奖励性能和成本约束保证。

具有策略先验的任意时间竞争强化学习