Minimax Optimal Adversarial Reinforcement Learning

Consider episodic Markov decision processes (MDPs) with adversarially chosen transition kernels, where the transition kernel is adversarially chosen at each episode. Prior works have established regret upper bounds of O( √ T + C P ), where T is the number of episodes and C P quantifies the degree of adversarial change in the transition dynamics. This regret bound may scale as large as O(T ), leading to a linear regret. This raises a fundamental question: Can sublinear regret be achieved under fully adversarial transition kernels? We answer this question affirmatively. First, we show that the optimal policy for MDPs with adversarial transition kernels must be history-dependent. We then design an algorithm of Adversarial Dynamics Follow-the-Regularized-Leader (AD-FTRL), and prove that it achieves a sublinear regret of O( (|S||A|) K T ), where K is the horizon length, |S| is the number of states, and |A| is the number of actions. Such a regret cannot be achieved by simply solving this problem as a contextual bandit. We further construct a hard MDP instance and prove a matching lower bound on the regret, which thereby demonstrates the minimax optimality of our algorithm.

Published as a conference paper at ICLR 2026 regret scales with both the state and action space dimensions. This optimal minimax regret bound confirms the fundamental difficulty of the problem and the minimax optimality of our algorithm. In our proof, we introduce a new analytical approach for handling adversarial or time-varying transitions using information-theoretic tools from composite hypothesis testing. Our newly constructed hard instance of MDPs and accompanying analysis framework provide a unified and complete solution for the minimax optimal regret bound of adversarial RL.

Upper Bound Analysis. Firstly, we introduce the work for the regret against a fixed optimal policy among the total episodes. For the case with adversarial loss functions but a fixed transition kernel, adversarial RL has been widely studied in previous works (Even-Dar et al.