# Multi-Bellman operator for convergence of Q-learning with linear function approximation

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 53 references that are in the map.
- First posted on arXiv 28 Sep 2023.

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

- [Deep Reinforcement Learning and the Deadly Triad](https://mlsanity.com/paper/1812.02648/) (2018)
- [Stochastic Variance Reduction Methods for Policy Evaluation](https://mlsanity.com/paper/1702.07944/) (2017)
- [A Finite-Time Analysis of Q-Learning with Neural Network Function Approximation](https://mlsanity.com/paper/1912.04511/) (2019)
- [Breaking the Deadly Triad with a Target Network](https://mlsanity.com/paper/2101.08862/) (2021)
- [Multi-step Reinforcement Learning: A Unifying Algorithm](https://mlsanity.com/paper/1703.01327/) (2017)
- [Target Network and Truncation Overcome The Deadly Triad in Q-Learning](https://mlsanity.com/paper/2203.02628/) (2022)
- [Finite-Sample Analysis of Off-Policy Natural Actor-Critic with Linear Function Approximation](https://mlsanity.com/paper/2105.12540/) (2021)
- [Beyond the One Step Greedy Approach in Reinforcement Learning](https://mlsanity.com/paper/1802.03654/) (2018)
- [Proximal Reinforcement Learning: A New Theory of Sequential Decision Making in Primal-Dual Spaces](https://mlsanity.com/paper/1405.6757/) (2014)
- [Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs](https://mlsanity.com/paper/2110.08440/) (2021)
- [Regularized Q-learning](https://mlsanity.com/paper/2202.05404/) (2022)
- [Convergent and Efficient Deep Q Network Algorithm](https://mlsanity.com/paper/2106.15419/) (2021)
- [Planning and Learning with Adaptive Lookahead](https://mlsanity.com/paper/2201.12403/) (2022)
- [Estimating the Maximum Expected Value: An Analysis of (Nested) Cross Validation and the Maximum Sample Average](https://mlsanity.com/paper/1302.7175/) (2013)
- [Think Too Fast Nor Too Slow: The Computational Trade-off Between Planning And Reinforcement Learning](https://mlsanity.com/paper/2005.07404/) (2020)
- [Reinforcement Learning with Unbiased Policy Evaluation and Linear Function Approximation](https://mlsanity.com/paper/2210.07338/) (2022)

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

- [Beyond expected value: geometric mean optimization for long-term policy performance in reinforcement learning](https://mlsanity.com/paper/2508.21443/) (2025)
- [Analysis of Off-Policy n-Step TD-Learning with Linear Function Approximation](https://mlsanity.com/paper/2502.08941/) (2025)
- [Networked Restless Multi-Arm Bandits with Reinforcement Learning](https://mlsanity.com/paper/2512.06274/) (2025)

## Abstract (arXiv)

We study the convergence of Q-learning with linear function approximation. Our key contribution is the introduction of a novel multi-Bellman operator that extends the traditional Bellman operator. By exploring the properties of this operator, we identify conditions under which the projected multi-Bellman operator becomes contractive, providing improved fixed-point guarantees compared to the Bellman operator. To leverage these insights, we propose the multi Q-learning algorithm with linear function approximation. We demonstrate that this algorithm converges to the fixed-point of the projected multi-Bellman operator, yielding solutions of arbitrary accuracy. Finally, we validate our approach by applying it to well-known environments, showcasing the effectiveness and applicability of our findings.