# A Two-Timescale Primal-Dual Framework for Reinforcement Learning via Online Dual Variable Guidance

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 19 of its 45 references that are in the map.
- First posted on arXiv 7 May 2025.

## 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, 19 of 19)

- [Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actor](https://mlsanity.com/paper/1801.01290/) (2018)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems](https://mlsanity.com/paper/2005.01643/) (2020)
- [A Theory of Regularized Markov Decision Processes](https://mlsanity.com/paper/1901.11275/) (2019)
- [A unified view of entropy-regularized Markov decision processes](https://mlsanity.com/paper/1705.07798/) (2017)
- [Equivalence Between Policy Gradients and Soft Q-Learning](https://mlsanity.com/paper/1704.06440/) (2017)
- [A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic](https://mlsanity.com/paper/2007.05170/) (2020)
- [Offline Reinforcement Learning with Realizability and Single-policy Concentrability](https://mlsanity.com/paper/2202.04634/) (2022)
- [A Primal-Dual Approach to Constrained Markov Decision Processes](https://mlsanity.com/paper/2101.10895/) (2021)
- [Offline Primal-Dual Reinforcement Learning for Linear MDPs](https://mlsanity.com/paper/2305.12944/) (2023)
- [Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning](https://mlsanity.com/paper/1612.02516/) (2016)
- [Boosting the Actor with Dual Critic](https://mlsanity.com/paper/1712.10282/) (2017)
- [Scalable Bilinear π Learning Using State and Action Features](https://mlsanity.com/paper/1804.10328/) (2018)
- [A Note on Optimization Formulations of Markov Decision Processes](https://mlsanity.com/paper/2012.09417/) (2020)
- [Convex Q Learning in a Stochastic Environment: Extended Version](https://mlsanity.com/paper/2309.05105/) (2023)
- [A Primal-Dual Algorithm for Offline Constrained Reinforcement Learning with Linear MDPs](https://mlsanity.com/paper/2402.04493/) (2024)
- [Convex Q-Learning, Part 1: Deterministic Optimal Control](https://mlsanity.com/paper/2008.03559/) (2020)
- [Accelerating Primal-dual Methods for Regularized Markov Decision Processes](https://mlsanity.com/paper/2202.10506/) (2022)
- [Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning](https://mlsanity.com/paper/2402.10810/) (2024)

## Abstract (arXiv)

We study reinforcement learning by combining recent advances in regularized linear programming formulations with the classical theory of stochastic approximation. Motivated by the challenge of designing algorithms that leverage off-policy data while maintaining on-policy exploration, we propose PGDA-RL, a novel primal-dual Projected Gradient Descent-Ascent algorithm for solving regularized Markov Decision Processes (MDPs). PGDA-RL integrates experience replay-based gradient estimation with a two-timescale decomposition of the underlying nested optimization problem. The algorithm operates asynchronously, interacts with the environment through a single trajectory of correlated data, and updates its policy online in response to the dual variable associated with the occupancy measure of the underlying MDP. We prove that PGDA-RL converges almost surely to the optimal value function and policy of the regularized MDP. Our convergence analysis relies on tools from stochastic approximation theory and holds under weaker assumptions than those required by existing primal-dual RL approaches, notably removing the need for a simulator or a fixed behavioral policy. Under a strengthened ergodicity assumption on the underlying Markov chain, we establish a last-iterate finite-time guarantee with tildeO (k-2/3) mean-square convergence, aligning with the best-known rates for two-timescale stochastic approximation methods under Markovian sampling and biased gradient estimates.