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

• URL: http://arxiv.org/abs/2606.16729v1
• Date: Mon, 15 Jun 2026 13:53:19 GMT
• Title: Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process
• Abstract summary: We study the dynamics of a single trajectory in weakly communicating MDPs.<n>We introduce the first model-free method that requires no prior knowledge of problem-dependent quantities.
• Score: 66.74725576150941
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs [20.54731804867887]
  We study the sample complexity of learning in average-reward weakly-coupled Markov decision processes (WCMDPs) and Restless Bandits (RBs)<n>By exploiting the weakly coupled structure, we show that near-optimal policies can be learned with sample complexity and computational complexities in $N$.
  arXiv  Detail & Related papers  (2026-06-12T04:19:53Z)
• Model-Based Learning of Near-Optimal Finite-Window Policies in POMDPs [8.784438985280092]
  We study model-based learning of finite-window policies in partially observable Markov decision processes (POMDPs)<n>A common approach to learning under partial observability is to approximate history dependencies using finite action-observation windows.<n>Once a model of this superstate MDP is available, standard MDP algorithms can be used to compute optimal policies.
  arXiv  Detail & Related papers  (2026-04-01T15:32:47Z)
• Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentum [62.691095807959215]
  We establish an optimal sample complexity of $O(-2)$ for obtaining an $$-optimal global policy using a single-timescale actor-critic (AC) algorithm.<n>These mechanisms are compatible with existing deep learning architectures and require only minor modifications, without compromising practical applicability.
  arXiv  Detail & Related papers  (2026-02-02T00:35:42Z)
• Provably Sample-Efficient Robust Reinforcement Learning with Average Reward [4.530028899565083]
  We propose a new algorithm designed for robust Markov Decision Processes (MDPs) with transition uncertainty characterized by $ell_p$-norm and contamination models.<n>Our algorithm operates without requiring any prior knowledge of the robust MDP.<n>Our work provides essential theoretical understanding of sample efficiency of robust average reward RL.
  arXiv  Detail & Related papers  (2025-05-18T15:34:45Z)
• Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning [50.81240969750462]
  We present first finite-sample analysis of policy evaluation in robust average Markov Decision Processes (PMDs)<n>We show that the robust Bellman operator is a contraction under a carefully constructed semi-norm, and developing a framework with controlled bias.<n>Our method achieves the order-optimal sample complexity of $tildemathcalO(epsilon-2)$ for robust policy evaluation and robust average reward estimation.
  arXiv  Detail & Related papers  (2025-02-24T03:55:09Z)
• Near-Optimal Sample Complexity Bounds for Constrained MDPs [25.509556551558834]
  We provide minimax upper and lower bounds on the sample complexity for learning near-optimal policies in a discounted CMDP. We show that learning CMDPs is as easy as MDPs when small constraint violations are allowed, but inherently more difficult when we demand zero constraint violation.
  arXiv  Detail & Related papers  (2022-06-13T15:58:14Z)
• A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs [117.82903457289584]
  We derive a novel problem-dependent lower-bound for regret in finite-horizon Markov Decision Processes (MDPs) We show that our lower-bound is considerably smaller than in the general case and it does not scale with the minimum action gap at all. We show that this last result is attainable (up to $poly(H)$ terms, where $H$ is the horizon) by providing a regret upper-bound based on policy gaps for an optimistic algorithm.
  arXiv  Detail & Related papers  (2021-06-24T13:46:09Z)
• RL for Latent MDPs: Regret Guarantees and a Lower Bound [74.41782017817808]
  We consider the regret problem for reinforcement learning in latent Markov Decision Processes (LMDP) In an LMDP, an MDP is randomly drawn from a set of $M$ possible MDPs at the beginning of the interaction, but the identity of the chosen MDP is not revealed to the agent. We show that the key link is a notion of separation between the MDP system dynamics.
  arXiv  Detail & Related papers  (2021-02-09T16:49:58Z)
• Breaking the Sample Size Barrier in Model-Based Reinforcement Learning with a Generative Model [50.38446482252857]
  This paper is concerned with the sample efficiency of reinforcement learning, assuming access to a generative model (or simulator) We first consider $gamma$-discounted infinite-horizon Markov decision processes (MDPs) with state space $mathcalS$ and action space $mathcalA$. We prove that a plain model-based planning algorithm suffices to achieve minimax-optimal sample complexity given any target accuracy level.
  arXiv  Detail & Related papers  (2020-05-26T17:53:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.