mlsanityData to 14 Oct 2026

Average-Reward Policy Identification from a Single Continuing Trajectory

arXiv 2610.20486 ↗First posted 14 Oct 2026cs.LGcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity also fits: Deep RL algorithms and representations

Abstract (arXiv)

In reinforcement learning, an agent must explore an unknown environment to learn how to make good decisions. Unlike methods that can freely sample any state--action pair, an agent learning from a single trajectory must spend additional time navigating between states. It is therefore natural to expect that learning from a single trajectory requires more experience. In this paper, we show that this additional cost is not always necessary. For average-reward reinforcement learning, we develop an algorithm that learns where to collect information while ensuring that the required samples can be obtained efficiently. We establish an upper bound on the number of interactions needed to identify a near-optimal policy. Furthermore, we prove a matching information theoretic lower bound, showing that, for a broad class of environments and at sufficiently high accuracy, learning from a single trajectory is no harder in the worst case than learning with unrestricted access to state action samples. Our results reveal that the additional complexity cost of navigation can be avoided by adapting information gathering requirements to how the environment provides information.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 12 of its 12 references that are in the map. First posted on arXiv 14 Oct 2026.

Builds on

12 of 12 references.

Closest ancestors · 3

Same direction, newest first

  1. 2026Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning19 Jul
  2. 2026Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs25 Mar
  3. 2026Sample Complexity of Average-Reward Q-Learning: From Single-agent to Federated Reinforcement Learning20 Jan

Other references · 9

  1. 2021Navigating to the Best Policy in Markov Decision Processescited by 29
  2. 2022Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDPcited by 29
  3. 2020A Provably Efficient Sample Collection Strategy for Reinforcement Learningcited by 16
  4. 2024Finding good policies in average-reward Markov Decision Processes without prior knowledgecited by 13
  5. 2024The Plug-in Approach for Average-Reward and Discounted MDPs: Optimal Sample Complexity Analysiscited by 9
  6. 2025Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RLcited by 5
  7. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RLcited by 3
  8. 2026Learning Policy from a Single Trajectory in Average-Reward Markov Decision Processcited by 3
  9. 2025Finite-Time Bounds for Average-Reward Fitted Q-Iterationcited by 2

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2024Reinforcement Learning with Lookahead Information
  2. 2024Model-Free Active Exploration in Reinforcement Learning
  3. 2025An Optimal Policy for Learning Controllable Dynamics by Exploration
  4. 2021Information Directed Reward Learning for Reinforcement Learning
  5. 2024Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles
  6. 2020A Conceptual Framework for Externally-influenced Agents: An Assisted Reinforcement Learning Review
  7. 2025Beyond expected value: geometric mean optimization for long-term policy performance in reinforcement learning
  8. 2026Policy Gradient Methods for Non-Markovian Reinforcement Learning