cs.LGOct 14, 2026

Average-Reward Policy Identification from a Single Continuing Trajectory

Authors: Tongxi Wang

Organizations: Southeast University

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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.

Figures & tables

MethodStartupPrecision
Online-DFE ( Tuynman et al., 2024 )S2AD3S^{2}AD^{3}SAD2/ϵ2SAD^{2}/\epsilon^{2}
Generative + GOSPRL ( Zurek and Chen, 2025a ; Tarbouriech et al., 2021 )S2AD3/2S^{2}AD^{3/2}SAD(B∗+1)/ϵ2SAD(B_{*}+1)/\epsilon^{2}
Theorem 1D∑imin⁡{di,D}D\sum_{i}\min\{d_{i},D\}SA(B∗+1)/ϵ2SA(B_{*}+1)/\epsilon^{2} +SAD/ϵ\hskip 9.24994pt{}+SAD/\epsilon
Table 1: Continuing policy-identification upper bounds, suppressing logarithms. B∗=\spn(h∗)≤DB_{*}=\spn(h^{*})\leq D . The second row is a derived composition, derived in Appendix F .
Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Figure H.1: Certificate errors are similar across cycle probabilities at fixed span. (a) Absolute error Eq=gP∗−LnE_{q}=g_{P}^{*}-L_{n} . (b) E1/4096/E1/16E_{1/4096}/E_{1/16} , paired by S,nS,n and seed; one denotes equality. All three seeds, medians and observed min–max are shown. Color and shape identify SS ; line style identifies qq . Policy gaps are reported below.
More in this topic

Reinforcement Learning

Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.

See all 1,661 papers

Explore similar work

CardsList
Jun 15, 2026

Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process

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 O~(1/ε2)\widetilde{O}(1/\varepsilon^2) and O~(1/ε4)\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.

Jongmin Lee, Ernest K. Ryu, Vaneet Aggarwal

Seoul National University · UCLA · Purdue University

Markov Decision ProcessesReinforcement LearningAverage-Reward RLMarkov ModelsModel-Free RLPolicy Learning+1
AskPDF
Feb 18, 2026

Improved Bounds for Reward-Agnostic and Reward-Free Exploration

We study reward-free and reward-agnostic exploration in episodic finite-horizon Markov decision processes (MDPs), where an agent explores an unknown environment without observing external rewards. Reward-free exploration aims to enable εε-optimal policies for any reward revealed after exploration, while reward-agnostic exploration targets εε-optimality for rewards drawn from a small finite class. In the reward-agnostic setting, Li, Yan, Chen, and Fan achieve minimax sample complexity, but only for restrictively small accuracy parameter εε. We propose a new algorithm that significantly relaxes the requirement on εε. Our approach is novel and of technical interest by itself. Our algorithm employs an online learning procedure with carefully designed rewards to construct an exploration policy, which is used to gather data sufficient for accurate dynamics estimation and subsequent computation of an εε-optimal policy once the reward is revealed. Finally, we establish a tight lower bound for reward-free exploration, closing the gap between known upper and lower bounds.

Oran Ridel, Alon Cohen

Department of Engineering, Tel Aviv University, Tel Aviv, Israel. · Google Research, Tel Aviv, Israel.

RL ExplorationReward-Free RLSample-Efficient RL
AskPDF
Jul 19, 2026

Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning

In this work we study the Best Policy Identification (BPI) problem in online, tabular Reinforcement Learning. This is an active sequential hypothesis testing problem in which the learner's objective is to identify an optimal policy in a Markov Decision Process (MDP) with high confidence, while minimizing the expected sample complexity to do so. We consider an online setting with deterministic rewards, where the agent must strategically navigate through the MDP in order to effectively explore. Previous works in the literature have provided asymptotically optimal methods for BPI, such as the Navigate and Stop (NaS) algorithm and its variants, however existing analysis remains asymptotic. In this work, we fill that gap by providing the first non-asymptotic sample complexity guarantees for NaS, showing that its sample complexity depends not only on the characteristic time, but also on the connectivity of the underlying MDP, the curvature of the optimal characteristic time, and other instance-dependent quantities. We identify these additional attributes and make explicit their contributions to the overall sample complexity.

Joseph Lazzaro, Alessio Russo, Aldo Pacchiano

Imperial College London · Boston University · Broad Institute of MIT and Harvard

Markov Decision ProcessesRL ExplorationSample-Efficient RL
AskPDF