Regularized Q-Learning with Linear Function Approximation
Not on the map. Why?
Abstract (arXiv)
Regularized Markov Decision Processes serve as models of sequential decision making under uncertainty wherein the decision maker has limited information processing capacity and/or aversion to model ambiguity. With functional approximation, the convergence properties of learning algorithms for regularized MDPs (e.g. soft Q-learning) are not well understood because the composition of the regularized Bellman operator and a projection onto the span of basis vectors is not a contraction with respect to any norm. In this paper, we consider a bi-level optimization formulation of regularized Q-learning with linear functional approximation. The em lower level optimization problem aims to identify a value function approximation that satisfies Bellman's recursive optimality condition and the em upper level aims to find the projection onto the span of basis vectors. This formulation motivates a single-loop algorithm with finite time convergence guarantees. The algorithm operates on two time-scales: updates to the projection of state-action values are `slow' in that they are implemented with a step size that is smaller than the one used for `faster' updates of approximate solutions to Bellman's recursive optimality equation. We show that, under certain assumptions, the proposed algorithm converges to a stationary point in the presence of Markovian noise. In addition, we provide a performance guarantee for the policies derived from the proposed algorithm.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 43 of its 69 references that are in the map. First posted on arXiv 26 Jan 2024.
Builds on
43 of 69 references.
References · 43
- 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
- 2015Continuous control with deep reinforcement learningcited by 3,279
- 2015Trust Region Policy Optimizationcited by 2,503
- 2015Deep Reinforcement Learning with Double Q-learningcited by 1,704
- 2016OpenAI Gymcited by 1,684
- 2017Reinforcement Learning with Deep Energy-Based Policiescited by 659
- 2016From Softmax to Sparsemax: A Sparse Model of Attention and Multi-Label Classificationcited by 337
- 2019Why gradient clipping accelerates training: A theoretical justification for adaptivitycited by 335
- 2019A Theory of Regularized Markov Decision Processescited by 279
- 2020On the Global Convergence Rates of Softmax Policy Gradient Methodscited by 258
- 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
- 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 221
31 more
- 2019A Theoretical Analysis of Deep Q-Learningcited by 212
- 2018Understanding the impact of entropy on policy optimizationcited by 171
- 2021Maximum Entropy RL (Provably) Solves Some Robust RL Problemscited by 169
- 2019Neural Policy Gradient Methods: Global Optimality and Rates of Convergencecited by 157
- 2020A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Criticcited by 141
- 2020A Finite Time Analysis of Two Time-Scale Actor Critic Methodscited by 120
- 2019Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscited by 113
- 2020Improved Analysis of Clipping Algorithms for Non-convex Optimizationcited by 88
- 2019Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learningcited by 67
- 2019A Finite-Time Analysis of Q-Learning with Neural Network Function Approximationcited by 47
- 2021Breaking the Deadly Triad with a Target Networkcited by 47
- 2021Twice regularized MDPs and the equivalence between robustness and regularizationcited by 46
- 2020Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithmscited by 43
- 2022Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guaranteescited by 42
- 2017Sparse Markov Decision Processes with Causal Sparse Tsallis Entropy Regularization for Reinforcement Learningcited by 36
- 2019Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samplescited by 31
- 2022Target Network and Truncation Overcome The Deadly Triad in Q-Learningcited by 31
- 2020Reanalysis of Variance Reduced Temporal Difference Learningcited by 23
- 2020Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithmscited by 19
- 2020Finite-sample Analysis of Greedy-GQ with Linear Function Approximation under Markovian Noisecited by 17
- 2022Finite-Time Analysis of Entropy-Regularized Neural Natural Actor-Critic Algorithmcited by 17
- 2022When is Realizability Sufficient for Off-Policy Reinforcement Learning?cited by 17
- 2019A Unified Switching System Perspective and O.D.E. Analysis of Q-Learning Algorithmscited by 14
- 2020Q-learning with Uniformly Bounded Variance: Large Discounting is Not a Barrier to Fast Learningcited by 13
- 2019Zap Q-Learning With Nonlinear Function Approximationcited by 10
- 2019Asymptotics of Reinforcement Learning with Neural Networkscited by 10
- 2021Sample Complexity and Overparameterization Bounds for Temporal Difference Learning with Neural Network Approximationcited by 9
- 2018Concentration bounds for two time scale stochastic approximationcited by 8
- 2021Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexitycited by 7
- 2023Stability of Q-Learning Through Design and Optimismcited by 7
- 2022Finite-Time Error Bounds for Greedy-GQcited by 3
Built on by
Citing papers per year: 2026: 1.
1 paper.