Rate-Optimal Algorithm for Learning Adversarial Linear CMDPs

We study adversarial linear constrained Markov decision processes (CMDPs), where both the loss and constraint functions may change adversarially over episodes. The previous state-of-the-art algorithm achieves $\tilde{\mathcal{O}}(K^{3/4})$ regret and constraint violation guarantees, leaving a gap from the rate-optimal $\tilde{\mathcal{O}}(\sqrt{K})$ dependence on the number of episodes $K$. Motivated by this gap, we propose a new primal-dual algorithm that achieves rate-optimal $\tilde{\mathcal{O}}(\sqrt{K})$ regret and constraint violation guarantees. Closing this gap is challenging because learning linear CMDPs requires controlling the covering number of the value function class, which conflicts with standard techniques used in constrained online learning, such as policy mixing. Our key idea is to develop a new drift analysis for adversarial linear CMDPs that avoids policy mixing, thereby maintaining a sufficiently simple policy structure for controlling the covering number. Moreover, our algorithm does not require Slater's condition and accommodates adversarial constraints.