Rate-Optimal Algorithm for Adversarial Linear CMDPs

We study episodic adversarial linear constrained Markov decision processes (CMDPs) with unknown transitions, where both the loss and constraint functions may vary adversarially across episodes. The best previous algorithm achieves widetildeO(K3/4) regret and cumulative constraint violation, leaving a gap to the optimal widetildeO(√K) dependence on the number of episodes K. We close this gap by proposing a new primal dual algorithm that achieves widetildeO(√K) regret and cumulative constraint violation without assuming Slater's condition. We further extend the algorithm to achieve the same widetildeO(√K) guarantees for regret and hard constraint violation, which does not allow constraint violations to cancel across episodes. The main challenge is that learning linear CMDPs requires uniform concentration over a value function class with a controlled covering number, whereas standard techniques in constrained online learning, such as policy mixing, can make this class more complex. Our algorithm combines adaptive Follow the Regularized Leader (FTRL), contracted value estimation, and an exponential Lyapunov function. An adaptive dual regularizer offsets the dependence on the dual weights in the primal regret bound, removing the need for policy mixing. We further show that the normalization in the FTRL update bounds the policy parameters independently of the magnitudes of the dual weights, which explains why the resulting policy class remains compatible with uniform concentration. Under feature access, the computational complexity is independent of the size of the state space.