Near-Optimal Regret for Constrained MDPs with Hard Stopping

We introduce Constrained Markov Decision Processes with Hard Stopping, which generalize Contextual Bandits with Knapsacks (CBwK) and can be viewed as a hard-constraint variant of Constrained Markov Decision Processes (CMDPs). In each of $T$ episodes, the agent interacts with the environment through an $H$-step MDP, where at each step it takes an action based on the current state and receives stochastic reward and cost. The objective is to maximize cumulative reward until the end of $T$ episodes or the cumulative cost exceeds a budget $B$. We propose Agressive Online Gradient Descent (AOGD) and prove an upper regret bound of $\tilde{O}((1+\frac{1}{\sqrt{b}})H^{2}S\sqrt{AT})$, where $b=B/T$ is the average budget per episode, $S,A$ are the numbers of states and actions. Up to our knowledge, this is the first algorithm that can achieve sublinear regret guarantee as long as the budget $B=\tilde{\omega }(1)$. We also establish a lower bound of $\Omega \left(\sqrt{H^{4}SAT/b}\right)$, matching our upper bound up to a factor of $\sqrt{S}$, and showing our bounds are near optimal in the key parameters $T$ and $b$. Further, we also show that with a sliding-window design, our algorithm would also have strong performance under a non-stationary setting.