# Optimistic Q-learning for average reward and episodic reinforcement learning

arXiv: https://arxiv.org/abs/2407.13743 · HTML: https://mlsanity.com/paper/2407.13743/

## 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.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 15 of 15)

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Episodic Reinforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited](https://mlsanity.com/paper/2010.03531/) (2020)
- [Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes](https://mlsanity.com/paper/1910.07072/) (2019)
- [Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning](https://mlsanity.com/paper/1802.04020/) (2018)
- [Breaking the Sample Complexity Barrier to Regret-Optimal Model-Free Reinforcement Learning](https://mlsanity.com/paper/2110.04645/) (2021)
- [Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function](https://mlsanity.com/paper/1906.05110/) (2019)
- [Sharper Model-free Reinforcement Learning for Average-reward Markov Decision Processes](https://mlsanity.com/paper/2306.16394/) (2023)
- [Learning in structured MDPs with convex cost functions: Improved regret bounds for inventory management](https://mlsanity.com/paper/1905.04337/) (2019)
- [Achieving Tractable Minimax Optimal Regret in Average Reward MDPs](https://mlsanity.com/paper/2406.01234/) (2024)
- [Reinforcement Learning for Infinite-Horizon Average-Reward Linear MDPs via Approximation by Discounted-Reward MDPs](https://mlsanity.com/paper/2405.15050/) (2024)

## Built on by (most cited first, 9 of 9)

- [Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach](https://mlsanity.com/paper/2505.19986/) (2025)
- [Regret Analysis of Unichain Average Reward Constrained MDPs with General Parameterization](https://mlsanity.com/paper/2602.08000/) (2026)
- [On the Convergence of Single-Timescale Actor-Critic](https://mlsanity.com/paper/2410.08868/) (2024)
- [Learning Weakly Communicating Average-Reward CMDPs: Strong Duality and Improved Regret](https://mlsanity.com/paper/2605.11586/) (2026)
- [Q-learning with Posterior Sampling](https://mlsanity.com/paper/2506.00917/) (2025)
- [A Bit of Freedom Goes a Long Way: Classical and Quantum Algorithms for Reinforcement Learning under a Generative Model](https://mlsanity.com/paper/2507.22854/) (2025)
- [Provably Efficient Algorithms for S- and Non-Rectangular Robust MDPs with General Parameterization](https://mlsanity.com/paper/2602.11387/) (2026)
- [When a Reinforcement Learning Agent Encounters Unknown Unknowns](https://mlsanity.com/paper/2505.13188/) (2025)
- [Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentum](https://mlsanity.com/paper/2602.01505/) (2026)

## 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.