mlsanityData to 14 Oct 2026

Optimistic Q-learning for average reward and episodic reinforcement learning

arXiv 2407.13743 ↗First posted 18 Jul 2024cs.LG stat.MLcited by 9

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

We present an optimistic Q-learning algorithm for regret minimization in average reward reinforcement learning under an additional assumption on the underlying MDP that for all policies, the time to visit some frequent state s0 is finite and upper bounded by H, either in expectation or with constant probability. Our setting strictly generalizes the episodic setting and is significantly less restrictive than the assumption of bounded hitting time textitfor all states made by most previous literature on model-free algorithms in average reward settings. We demonstrate a regret bound of tildeO(H5 S√AT), where S and A are the numbers of states and actions, and T is the horizon. A key technical novelty of our work is the introduction of an overlineL operator defined as overlineL v = frac1H sumh=1H Lh v where L denotes the Bellman operator. Under the given assumption, we show that the overlineL operator has a strict contraction (in span) even in the average-reward setting where the discount factor is 1. Our algorithm design uses ideas from episodic Q-learning to estimate and apply this operator iteratively. Thus, we provide a unified view of regret minimization in episodic and non-episodic settings, which may be of independent interest.

Key facts. Cited by 9 papers in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 15 of its 27 references that are in the map. First posted on arXiv 18 Jul 2024.

Builds on

15 of 27 references.

Closest ancestors · 1

Same direction, newest first

  1. 2024Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs23 May

Other references · 14

  1. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  2. 2015Trust Region Policy Optimizationcited by 2,580
  3. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,258
  4. 2015Deep Reinforcement Learning with Double Q-learningcited by 1,745
  5. 2018Is Q-learning Provably Efficient?cited by 487
  6. 2013(More) Efficient Reinforcement Learning via Posterior Samplingcited by 233
  7. 2020Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisitedcited by 106
  8. 2019Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processescited by 82
  9. 2018Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learningcited by 66
  10. 2021Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learningcited by 53
  11. 2019Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Functioncited by 44
  12. 2023Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processescited by 29
2 more
  1. 2019Learning in structured MDPs with convex cost functions: Improved regret bounds for inventory managementcited by 22
  2. 2024Achieving Tractable Minimax Optimal Regret in Average Reward MDPscited by 15

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 4; 2026: 4.

9 papers.

  1. 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approachcited by 7
  2. 2026Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterizationcited by 4
  3. 2024On the Convergence of Single-Timescale Actor-Criticcited by 3
  4. 2026Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regretcited by 2
  5. 2025Q-learning with Posterior Samplingcited by 1
  6. 2025A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Modelcited by 1
  7. 2026Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterizationcited by 1
  8. 2025When a Reinforcement Learning Agent Encounters Unknown Unknownscited by 0
  9. 2026Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentumcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Minimax Optimal Reinforcement Learning with Quasi-Optimism
  2. 2026Non-asymptotic Convergence of Average-reward Q-learning with Options
  3. 2024Improved Regret Bound for Safe Reinforcement Learning via Tighter Cost Pessimism and Reward Optimism
  4. 2025Tail Distribution of Regret in Optimistic Reinforcement Learning
  5. 2025Provably Efficient and Agile Randomized Q-Learning
  6. 2025Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learning
  7. 2025Optimistic Reinforcement Learning with Quantile Objectives
  8. 2021Fast Rates for the Regret of Offline Reinforcement Learning