Data- and Variance-dependent Regret Bounds for Online Tabular MDPs

This work studies online episodic tabular Markov decision processes (MDPs) with known transitions and develops best-of-both-worlds algorithms that achieve refined data-dependent regret bounds in the adversarial regime and variance-dependent regret bounds in the stochastic regime. We quantify MDP complexity using a first-order quantity and several new data-dependent measures for the adversarial regime, including a second-order quantity and a path-length measure, as well as variance-based measures for the stochastic regime. To adapt to these measures, we develop algorithms based on global optimization and policy optimization, both built on optimistic follow-the-regularized-leader with log-barrier regularization. For global optimization, our algorithms achieve first-order, second-order, and path-length regret bounds in the adversarial regime, and in the stochastic regime, they achieve a variance-aware gap-independent bound and a variance-aware gap-dependent bound that is polylogarithmic in the number of episodes. For policy optimization, our algorithms achieve the same data- and variance-dependent adaptivity, up to a factor of the episode horizon, by exploiting a new optimistic $Q$-function estimator. Finally, we establish regret lower bounds in terms of data-dependent complexity measures for the adversarial regime and a variance measure for the stochastic regime, implying that the regret upper bounds achieved by the global-optimization approach are nearly optimal.

This paper studies learning algorithms for tabular Markov decision processes (MDPs) with known transition dynamics, where a learner repeatedly makes decisions in an environment with finitely many states and actions. We develop algorithms that adapt to both stochastic and adversarial environments: they learn faster when losses are generated from a stable distribution, while remaining robust when losses are chosen unpredictably or adversarially over time. Beyond adapting to the environment type, our algorithms also adapt to the observed loss sequence. Their guarantees strengthen when the best policy incurs small loss, when losses fluctuate little around a baseline, when losses change slowly across episodes, or when the random noise in the losses is small. To achieve these guarantees, we design new loss and Q-function estimators and use them to obtain adaptive results for both global optimization and policy optimization methods. We also provide lower bounds for several loss- and variance-dependent quantities, supporting the near-optimality of the main global-optimization guarantees.