A Computationally Efficient and Rate-optimal Algorithm for Adversarial Linear MDPs with (Aggregate) Bandit Feedback

We study episodic linear Markov decision processes with unknown transitions, adversarial losses, and bandit feedback. The state-of-the-art result for this setting (Liu et al., 2024a) either achieves $\sqrt{K}$ regret with a computationally inefficient algorithm or achieves suboptimal $K^{3/4}$ regret, where $K$ is the number of episodes. Our work gives the first $\sqrt{K}$ regret with a polynomial-time algorithm. Our method reduces adversarial linear MDPs to adversarial linear bandits whose action set $\mathcal{K}$ consists of policies’ expected feature vectors. The central challenge is that $\mathcal{K}$ is unknown and can be estimated only through exploration. We address this challenge by constructing an *approximate separation oracle* for $\mathcal{K}$ that either generates executable policies from queried features or refines an outer approximation of $\mathcal{K}$. This approach draws inspiration from the reduction of van Erven et al. (2025) for linear contextual bandits and the oracle-efficient linear bandit algorithm of Ito et al. (2019), but additionally handles the imprecision of the oracle. The resulting algorithm requires only aggregate loss feedback and, to our knowledge, is the first polynomial-time algorithm for adversarial MDPs with aggregate feedback beyond the tabular case.