Span-based Optimal Sample Complexity For Average Reward Mdps

Abstract

We study the sample complexity of learning an \(\epsilon\)-optimal policy in an average-reward Markov decision process (MDP) under a generative model. We establish the complexity bound \(\widetilde\{O\}\left(SA\frac\{H\}\{\epsilon^2\} \right)\), where \(H\) is the span of the bias function of the optimal policy and \(SA\) is the cardinality of the state-action space. Our result is the first that is minimax optimal (up to log factors) in all parameters \(S,A,H\) and \(\epsilon\), improving on existing work that either assumes uniformly bounded mixing times for all policies or has suboptimal dependence on the parameters. Our result is based on reducing the average-reward MDP to a discounted MDP. To establish the optimality of this reduction, we develop improved bounds for \(\gamma\)-discounted MDPs, showing that \(\widetilde\{O\}\left(SA\frac\{H\}\{(1-\gamma)^2\epsilon^2\} \right)\) samples suffice to learn a \(\epsilon\)-optimal policy in weakly communicating MDPs under the regime tha

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyzurek2023span

Related papers

• Span-based Optimal Sample Complexity For Weakly Communicating And General Average Reward Mdps (2024)0.00
• Optimal Sample Complexity For Average Reward Markov Decision Processes (2023)0.00
• Near Sample-optimal Reduction-based Policy Learning For Average Reward MDP (2022)0.00
• Model-free Reinforcement Learning: From Clipped Pseudo-regret To Sample Complexity (2020)0.00
• Projection By Convolution: Optimal Sample Complexity For Reinforcement Learning In Continuous-space Mdps (2024)0.00
• Stochastic Primal-dual Methods And Sample Complexity Of Reinforcement Learning (2016)0.00
• Sample Complexity Of Distributionally Robust Average-reward Reinforcement Learning (2025)0.00
• Sample-efficient Reinforcement Learning For Linearly-parameterized Mdps With A Generative Model (2021)0.00