aiqbench analysis
This research introduces best-of-both-worlds algorithms for online tabular MDPs that adapt regret bounds to specific data complexities and variance levels in adversarial and stochastic regimes. By leveraging new data-dependent measures and optimistic Q-function estimators, the authors achieve nearly optimal performance with polylogarithmic dependence on episode counts in stochastic settings. The work establishes theoretical lower bounds confirming the optimality of these global optimization approaches, offering a rigorous foundation for adaptive reinforcement learning methods.
Data- and Variance-dependent Regret Bounds for Online Tabular MDPs
arXiv:2602.01903v2 Announce Type: replace Abstract: 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.
Abstract: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.
Accepted at ICML 2026. 72 pages, 4 tables
Machine Learning (cs.LG); Machine Learning (stat.ML)
arXiv:2602.01903 [cs.LG]
(or arXiv:2602.01903v2 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2602.01903 Focus to learn more arXiv-issued DOI via DataCite
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 300 words
Related coverage
A Unified Algorithmic Framework for Hybrid Reinforcement Learning in Tabular MDPs with Shifted Transition Dynamics
arXiv · Jul 29, 2026
Variance-Aware Fine-Grained Gap-Dependent Bounds for Online Reinforcement Learning
arXiv · Oct 6, 2026
Asymptotically Optimal Regret for Reinforcement Learning without Horizon Dependence
arXiv · Jul 23, 2026
Closing the Horizon Gap in Policy Optimization for Adversarial MDPs
arXiv · Oct 9, 2026