# Stochastic Primal-Dual Q-Learning

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Oct 2018.

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

- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [Is Q-Learning Minimax Optimal? A Tight Sample Complexity Analysis](https://mlsanity.com/paper/2102.06548/) (2021)
- [Accelerating Primal-dual Methods for Regularized Markov Decision Processes](https://mlsanity.com/paper/2202.10506/) (2022)
- [Lagrangian Method for Q-Function Learning (with Applications to Machine Translation)](https://mlsanity.com/paper/2207.11161/) (2022)
- [Data-Driven Influence Functions for Optimization-Based Causal Inference](https://mlsanity.com/paper/2208.13701/) (2022)
- [Analysis of approximate linear programming solution to Markov decision problem with log barrier function](https://mlsanity.com/paper/2509.19800/) (2025)
- [Lifted Bellman Linear Programming for Offline Reinforcement Learning](https://mlsanity.com/paper/2609.24489/) (2026)

## Abstract (arXiv)

In this work, we present a new model-free and off-policy reinforcement learning (RL) algorithm, that is capable of finding a near-optimal policy with state-action observations from arbitrary behavior policies. Our algorithm, called the stochastic primal-dual Q-learning (SPD Q-learning), hinges upon a new linear programming formulation and a dual perspective of the standard Q-learning. In contrast to previous primal-dual RL algorithms, the SPD Q-learning includes a Q-function estimation step, thus allowing to recover an approximate policy from the primal solution as well as the dual solution. We prove a first-of-its-kind result that the SPD Q-learning guarantees a certain convergence rate, even when the state-action distribution is time-varying but sub-linearly converges to a stationary distribution. Numerical experiments are provided to demonstrate the off-policy learning abilities of the proposed algorithm in comparison to the standard Q-learning.