Span-based Optimal Sample Complexity For Weakly Communicating And General 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. For weakly communicating MDPs, we establish the complexity bound \(\widetilde\{O\}(SA\frac\{H\}\{\epsilon^2\} )\), 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. We also initiate the study of sample complexity in general (multichain) average-reward MDPs. We argue a new transient time parameter \(B\) is necessary, establish an \(\widetilde\{O\}(SA\frac\{B + H\}\{\epsilon^2\})\) complexity bound, and prove a matching (up to log factors) minimax lower bound. Both results are based on reducing the average-reward

Stats

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

Related papers

• Span-based Optimal Sample Complexity For Average Reward Mdps (2023)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
• Projection By Convolution: Optimal Sample Complexity For Reinforcement Learning In Continuous-space Mdps (2024)0.00
• Optimal Single-policy Sample Complexity And Transient Coverage For Average-reward Offline RL (2025)0.00
• Stochastic Primal-dual Methods And Sample Complexity Of Reinforcement Learning (2016)0.00
• Model-free Reinforcement Learning: From Clipped Pseudo-regret To Sample Complexity (2020)0.00
• Sample Complexity Of Distributionally Robust Average-reward Reinforcement Learning (2025)0.00