{"id":"arxiv/2603.23926","url":"https://arxiv.org/abs/2603.23926","tags":["cs.LG","cs.IT","math.OC","stat.ML"],"score":0,"title":"Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs","domain":"cs.LG","source":"arxiv","authors":["Guy Zamir","Matthew Zurek","Yudong Chen"],"reviews":0,"subject":"cs.LG","summary":"Online reinforcement learning in infinite-horizon Markov decision processes (MDPs) remains less theoretically and algorithmically developed than its episodic counterpart, with many algorithms suffering from high ``burn-in'' costs and failing to adapt to benign instance-specific complexity. In this work, we address these shortcomings for two infinite-horizon objectives: the classical average-reward regret and the $γ$-regret. We develop a single tractable UCB-style algorithm applicable to both settings, which achieves the first optimal variance-dependent regret guarantees. Our regret bounds in…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-03-25","reactions":{}}