  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.
