Average-Reward RL

RL: Reinforcement Learning

Average-reward RL optimizes long-run reward per time step in continuing tasks, rather than discounting distant rewards; it is useful when there is no natural episode end or discount factor. Methods include differential temporal-difference and Q-learning, relative-value iteration, actor-critic, and policy-gradient or mirror-descent algorithms, with tabular, linear, and neural critics and often a single Markovian trajectory. Current work develops convergence, regret, and sample-complexity guarantees for communicating and weakly communicating MDPs, while extending learning to constrained and robust problems, options, and multi-agent or mean-field settings. A central tension is that guarantees often depend on mixing, span, or ergodicity assumptions, while optimizing asymptotic reward can still permit poor transient performance or obscure different recurrent-class rewards in multichain systems.

Latest papers

35 papers9 papers in the last four weeks, up 200% on the four weeks before. 0.1% of all new papers.

Average-Reward Policy Identification from a Single Continuing Trajectory
Oct 14, 2026Tongxi WangReinforcement Learning Average-Reward RL
Southeast University
Non-asymptotic Convergence of Average-reward Q-learning with Options
Oct 14, 2026Kintan Saha, Ahana Deb, Anders Jonsson +1Q-Learning Average-Reward RL
Indian Institute of Science · Universitat Pompeu Fabra · Univ. Lille, Inria, CNRS- CRIStAL, Centrale Lille
Entropy-Regularized Mean-Field Games with Average-Reward Criterion: Span-Seminorm Contractions and Model-Free Learning
Oct 11, 2026Gunes Akbas, Naci Saldi, Berkay Anahtarci +1Mean Field Games Model-Free RL
Department of Mathematics, Bilkent University, Ankara 06800, Türkiye · Department of Mathematical Engineering, Özyeğin University, İstanbul 34794, Türkiye
Mixing Regularization for Average-Reward $Q$ -Learning and $Q$ -Planning
Oct 10, 2026Julien Roger, Sam Bodmer, Jian Qian +1Regularized RL Reinforcement Learning
École polytechnique · New York University · The University of Hong Kong
Average-Reward Reinforcement Learning for Multichain MDPs: A Hierarchical Decomposition Approach
Oct 7, 2026Huizhen Yu, Isaiah HeidtMarkov Decision Processes Average-Reward RL
Department of Computing Science University of Alberta, Canada
Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs
Oct 2, 2026Enes Arda, Atilla EryilmazMarkov Decision Processes Average-Reward RL
The Ohio State University
Learning Infinite-Horizon Average-Reward CMDPs via State Augmentation
Sep 30, 2026Kihyun Yu, Seoungbin Bae, Dabeen LeeRegret Minimization in RL Markov Decision Processes
KAIST · Seoul National University
Achieving an $O(1/N)$ Optimality Gap in Average-Reward Weakly-Coupled MDPs
Sep 29, 2026Yige Hong, Xiangcheng Zhang, Qiaomin Xie +2Markov Decision Processes Average-Reward RL
H. Milton Stewart School of Industrial & Systems Engineering, Georgia Institute of Technology · John A. Paulson School of Engineering and Applied Sciences, Harvard University · Department of Industrial and Systems Engineering, University of Wisconsin–Madison +2
Reward-rate Policy Gradient for Efficient Machine Learning Engineering Agents
Sep 28, 2026Muhang Tian, Sherry YangPolicy Gradient Agentic RL
New York University
Distributionally Robust Average-Reward Reinforcement Learning: Finite-Sample Guarantees under Weak Communication
Sep 26, 2026Chenyu Lu, Zijun Chen, Nian SiDistributionally Robust RL Average-Reward RL
The Hong Kong University of Science and Technology
A Concentration Bound for Two-Timescale Actor-Critic Algorithm
Sep 24, 2026Prashansa Panda, Shalabh BhatnagarAverage-Reward RL Two-Timescale Stochastic Approximation
Department of Computer Science and Automation IISc Bangalore
Vector Bellman Theory for Multichain Robust Average-Reward Markov Decision Processes
Sep 23, 2026Yue Wang, George AtiaRobust Markov Decision Processes Markov Decision Processes
Department of Electrical and Computer Engineering University of Central Florida
Finite Constant Frontiers and Auditable Regret Certificates for Average-Reward Reinforcement Learning
Aug 7, 2026Ibne Farabi Shihab, Abu Sa-Adat Mohamed Moon-Im Al Ahsan, Md Najmus SwaqeebRegret Minimization in RL Markov Decision Processes
Department of Computer Science, Iowa State University · Department of Computer Science & Engineering, BRAC University
Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions
Aug 6, 2026Yuepeng Yang, Yuxin Chen, Yuejie ChiRobust Markov Decision Processes Average-Reward RL
*Department of Statistics and Data Science, Yale University. · †Department of Statistics and Data Science, the Wharton School, University of Pennsylvania.
Hierarchical Multilevel Monte Carlo for Order-Optimal Neural Actor-Critic in Average-Reward CMDPs
Jul 30, 2026Ankur Naskar, Vaneet AggarwalAverage-Reward RL Constrained RL
Indian Institute of Science, India · Purdue University, USA
Bias-Controlled Primal-Dual Natural Actor-Critic: Optimal Rates for Constrained Multi-Objective Average-Reward RL
Jun 23, 2026Ankur Naskar, Swetha Ganesh, Vaneet AggarwalMulti-Objective Reinforcement Learning Reinforcement Learning
Indian Institute of Science, Bengaluru, India · Purdue University, USA
Maximum Entropy Inverse Reinforcement Learning for Mean-Field Games with Average Reward
Jun 15, 2026Şevket Kaan Alkır, Naci Saldı, Berkay Anahtarcı +1Reinforcement Learning Average-Reward RL
Department of Mathematics Bilkent University 06800 Ankara, Turkey · Department of Mathematical Engineering Özyeğin University 34794 Istanbul, Turkey
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
Lyapunov-Based Sample Complexity Analysis for Weakly-Coupled MDPs
Jun 12, 2026Tianhao Wu, Matthew Zurek, Weina Wang +1Multi-Armed Bandits Robust Markov Decision Processes
Department of Industrial and Systems Engineering, University of Wisconsin-Madison · Department of Computer Sciences, University of Wisconsin-Madison · Computer Science Department, Carnegie Mellon University
Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret
May 12, 2026Kihyun Yu, Beomhan Baek, Dabeen LeeRegret Minimization in RL Markov Decision Processes
1KAIST · 2Seoul National University
Quotient-Categorical Representations for Bellman-Compatible Average-Reward Distributional Reinforcement Learning
May 11, 2026Ege C. Kaya, Aliasghar Pourghani, Vijay Gupta +1Distributional RL Reinforcement Learning
Elmore Family School of Electrical and Computer Engineering Purdue University West Lafayette, IN 47906
On the Divergence of Differential Temporal Difference Learning without Local Clocks
May 7, 2026David Antrobius, Shangtong ZhangReinforcement Learning Average-Reward RL
Department of Computer Science University of Virginia
A Harmonic Mean Formulation of Average Reward Reinforcement Learning in SMDPs
May 6, 2026Erel Shtossel, Alicia Vidler, Uri Shaham +1Non-Stationary RL Reinforcement Learning
Bar Ilan University Ramat Gan, Israel
Bridging the Gap Between Average and Discounted TD Learning
May 3, 2026Haoxing Tian, Zaiwei Chen, Ioannis Ch. Paschalidis +1Reinforcement Learning Average-Reward RL
Department of Electrical and Computer Engineering Boston University · Edwardson School of Industrial Engineering Purdue University
Optimal Variance-Dependent Regret Bounds for Infinite-Horizon MDPs
Mar 25, 2026Guy Zamir, Matthew Zurek, Yudong ChenRegret Minimization in RL Average-Reward RL
Department of Computer Sciences, University of Wisconsin–Madison
Ergodicity in reinforcement learning
Mar 11, 2026Dominik Baumann, Erfaun Noorani, Arsenii Mustafin +5Reinforcement Learning Average-Reward RL
Cyber-physical Systems Group, Aalto University, Espoo 02150, Finland · Control & Autonomous Systems Engineering Group, MIT Lincoln Laboratory, Lexington, MA 02421-6426, USA · Data Analytics Lab, Vrije Universiteit Brussel, Brussel 1050, Belgium +2
Global Convergence of Average Reward Constrained MDPs with Neural Critic and General Policy Parameterization
Mar 8, 2026Anirudh Satheesh, Pankaj Kumar Barman, Washim Uddin Mondal +1Natural Policy Gradient Constrained RL
Department of Computer Science, University of Maryland, College Park, MD 20740, USA · Indian Institute of Technology, Kanpur, Uttar Pradesh, 208016, India · Department of Electrical Engineering, Indian Institute of Technology, Kanpur, Uttar Pradesh, 208016, India +1
Personalized Multi-Agent Average Reward TD-Learning via Joint Linear Approximation
Mar 2, 2026Leo Muxing Wang, Pengkun Yang, Lili SuTemporal-Difference Learning Multi-Agent Reinforcement Learning
Northeastern University · Tsinghua University
Non-Rectangular Average-Reward Robust MDPs: Optimal Policies and Their Transient Values
Mar 1, 2026Shengbo Wang, Nian SiRobust Markov Decision Processes Average-Reward RL
Daniel J. Epstein Department of Industrial and Systems Engineering, University of Southern California · Department of Industrial Engineering and Decision Analytics, Hong Kong University of Science and Technology
A Unified Framework for Locality in Scalable MARL
Feb 19, 2026Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni +1Multi-Agent Reinforcement Learning Average-Reward RL
University of Colorado, Boulder, USA. · INRIA Paris, France.

Oct 14, 2026J/K move · Enter open · S save

Average-Reward Policy Identification from a Single Continuing Trajectory

Tongxi Wang

Southeast University

Reinforcement Learning Average-Reward RL RL Exploration Sample-Efficient RL

Open paper AskPDF 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.