# Convex Q Learning in a Stochastic Environment: Extended Version

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

## Key facts

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

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

- [Logistic Q-Learning](https://mlsanity.com/paper/2010.11151/) (2020)
- [Q-learning with Uniformly Bounded Variance: Large Discounting is Not a Barrier to Fast Learning](https://mlsanity.com/paper/2002.10301/) (2020)
- [On the Exponential Stability of Primal-Dual Gradient Dynamics](https://mlsanity.com/paper/1803.01825/) (2018)
- [A Linearly Relaxed Approximate Linear Program for Markov Decision Processes](https://mlsanity.com/paper/1704.02544/) (2017)
- [Full Gradient DQN Reinforcement Learning: A Provably Convergent Scheme](https://mlsanity.com/paper/2103.05981/) (2021)
- [Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization](https://mlsanity.com/paper/2210.12057/) (2022)
- [Stability of Q-Learning Through Design and Optimism](https://mlsanity.com/paper/2307.02632/) (2023)
- [Controlled Interacting Particle Algorithms for Simulation-based Reinforcement Learning](https://mlsanity.com/paper/2107.01244/) (2021)

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

- [Optimistic Training and Convergence of Q-Learning -- Extended Version](https://mlsanity.com/paper/2602.06146/) (2026)
- [Regularized Q-learning through Robust Averaging](https://mlsanity.com/paper/2405.02201/) (2024)
- [Functional role of synchronization: A mean-field control perspective](https://mlsanity.com/paper/2502.00590/) (2025)
- [A Two-Timescale Primal-Dual Framework for Reinforcement Learning via Online Dual Variable Guidance](https://mlsanity.com/paper/2505.04494/) (2025)
- [Lifted Bellman Linear Programming for Offline Reinforcement Learning](https://mlsanity.com/paper/2609.24489/) (2026)

## Abstract (arXiv)

The paper introduces the first formulation of convex Q-learning for Markov decision processes with function approximation. The algorithms and theory rest on a relaxation of a dual of Manne's celebrated linear programming characterization of optimal control. The main contributions firstly concern properties of the relaxation, described as a deterministic convex program: we identify conditions for a bounded solution, and a significant relationship between the solution to the new convex program, and the solution to standard Q-learning. The second set of contributions concern algorithm design and analysis: (i) A direct model-free method for approximating the convex program for Q-learning shares properties with its ideal. In particular, a bounded solution is ensured subject to a simple property of the basis functions; (ii) The proposed algorithms are convergent and new techniques are introduced to obtain the rate of convergence in a mean-square sense; (iii) The approach can be generalized to a range of performance criteria, and it is found that variance can be reduced by considering ``relative'' dynamic programming equations; (iv) The theory is illustrated with an application to a classical inventory control problem.