aiqbench analysis
This research establishes the first finite sample complexity guarantees for learning policies in average-reward Markov decision processes using a single trajectory without restrictive assumptions like ergodicity or generative model access. By developing novel value-based and policy-free methods, it advances theoretical foundations for efficient reinforcement learning algorithms that operate with minimal prior knowledge of problem-dependent quantities.
Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process
arXiv:2606.16729v1 Announce Type: new Abstract: While there is an extensive body of work characterizing the sample complexity of discounted cumulative-reward MDPs, finite sample analyses for average-reward MDPs have been limited, and most existing works rely on restrictive assumptions such as ergodicity or access to a generative model. In this work, we establish the first finite sample complexity guarantees from a single trajectory for weakly communicating average-reward MDPs. To this end, we study the dynamics of a single trajectory in weakly communicating MDPs and based on this analysis, we develop novel model-free methods. Notably, our value-based and policy-based methods provide finite sample complexity guarantees of $\widetilde{O}(1/\varepsilon^2)$ and $\widetilde{O}(1/\varepsilon^4)$ from a single trajectory in weakly communicating MDPs, respectively. Furthermore, we introduce the first model-free method that requires no prior knowledge of problem-dependent quantities for communicating MDPs.
Abstract:While there is an extensive body of work characterizing the sample complexity of discounted cumulative-reward MDPs, finite sample analyses for average-reward MDPs have been limited, and most existing works rely on restrictive assumptions such as ergodicity or access to a generative model. In this work, we establish the first finite sample complexity guarantees from a single trajectory for weakly communicating average-reward MDPs. To this end, we study the dynamics of a single trajectory in weakly communicating MDPs and based on this analysis, we develop novel model-free methods. Notably, our value-based and policy-based methods provide finite sample complexity guarantees of $\widetilde{O}(1/\varepsilon^2)$ and $\widetilde{O}(1/\varepsilon^4)$ from a single trajectory in weakly communicating MDPs, respectively. Furthermore, we introduce the first model-free method that requires no prior knowledge of problem-dependent quantities for communicating MDPs.
Machine Learning (cs.LG); Optimization and Control (math.OC)
arXiv:2606.16729 [cs.LG]
(or arXiv:2606.16729v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2606.16729 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
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 · 227 words
Related coverage
When Partial Credit Opposes Completion
Snorkel AI Blog · Oct 15, 2026
Enhancing Personalized Bladder Cancer Treatment Through Reinforcement Learning: A Recurrent Patient State Transition Decision Support Framework
arXiv · Jul 21, 2026
Echoverse: Deep, evolving environments for computer-use agents
Microsoft Research · Jul 30, 2026
OneDemo: Unified Policy Learning and Data Generation from a Single Demonstration
arXiv · Oct 14, 2026