Average-Reward Policy Identification from a Single Continuing Trajectory

Tongxi Wang

cs.LGOct 14, 2026

Average-Reward Policy Identification from a Single Continuing Trajectory

Authors: Tongxi Wang

Organizations: Southeast University

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

Method	Startup	Precision
Online-DFE ( Tuynman et al., 2024 )	$S^{2}AD^{3}$	$SAD^{2}/\epsilon^{2}$
Generative + GOSPRL ( Zurek and Chen, 2025a ; Tarbouriech et al., 2021 )	$S^{2}AD^{3/2}$	$SAD(B_{*}+1)/\epsilon^{2}$
Theorem 1	$D\sum_{i}\min\{d_{i},D\}$	$SA(B_{*}+1)/\epsilon^{2}$ $\hskip 9.24994pt{}+SAD/\epsilon$

Table 1: Continuing policy-identification upper bounds, suppressing logarithms.

B_{*}=\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

E_{q}=g_{P}^{*}-L_{n}

. (b)

E_{1/4096}/E_{1/16}

, paired by

S,n

and seed; one denotes equality. All three seeds, medians and observed min–max are shown. Color and shape identify

S

; line style identifies

q

. Policy gaps are reported below.

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

Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process
Jun 15, 2026Jongmin Lee, Ernest K. Ryu, Vaneet AggarwalMarkov Decision Processes Reinforcement Learning
Seoul National University · UCLA · Purdue University
Improved Bounds for Reward-Agnostic and Reward-Free Exploration
Feb 18, 2026Oran Ridel, Alon CohenRL Exploration Reward-Free RL
Department of Engineering, Tel Aviv University, Tel Aviv, Israel. · Google Research, Tel Aviv, Israel.
Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning
Jul 19, 2026Joseph Lazzaro, Alessio Russo, Aldo PacchianoMarkov Decision Processes RL Exploration
Imperial College London · Boston University · Broad Institute of MIT and Harvard

Jun 15, 2026J/K move · Enter open · S save

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

Jongmin Lee, Ernest K. Ryu, Vaneet Aggarwal

Seoul National University · UCLA · Purdue University

Markov Decision Processes Reinforcement Learning Average-Reward RL Markov Models Model-Free RL Policy Learning+1

Open paper AskPDF arXiv

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

Reinforcement Learning

Explore similar work

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

Improved Bounds for Reward-Agnostic and Reward-Free Exploration

Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning