A Finite-Sample Analysis of an Actor-Critic Algorithm for Mean-Variance Optimization in a Discounted MDP
On the map: Deep reinforcement learning methods → RL theory and sample complexity
Abstract (arXiv)
Motivated by applications in risk-sensitive reinforcement learning, we study mean-variance optimization in a discounted reward Markov Decision Process (MDP). Specifically, we analyze a Temporal Difference (TD) learning algorithm with linear function approximation (LFA) for policy evaluation. We derive finite-sample bounds that hold (i) in the mean-squared sense and (ii) with high probability under tail iterate averaging, both with and without regularization. Our bounds exhibit an exponentially decaying dependence on the initial error and a convergence rate of O(1/t) after t iterations. Moreover, for the regularized TD variant, our bound holds for a universal step size. Next, we integrate a Simultaneous Perturbation Stochastic Approximation (SPSA)-based actor update with an LFA critic and establish an O(n-1/4) convergence guarantee, where n denotes the iterations of the SPSA-based actor-critic algorithm. These results establish finite-sample theoretical guarantees for risk-sensitive actor-critic methods in reinforcement learning, with a focus on variance as a risk measure.
Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 13 of its 33 references that are in the map. First posted on arXiv 12 Jun 2024.
Builds on
13 of 33 references.
References · 13
- 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
- 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 166
- 2019Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policiescited by 124
- 2020On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentrationcited by 68
- 2019On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximationcited by 54
- 2019Risk-Averse Trust Region Optimization for Reward-Volatility Reductioncited by 54
- 2022Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximationcited by 41
- 2014Variance-Constrained Actor-Critic Algorithms for Discounted and Average Reward MDPscited by 28
- 2020Mean-Variance Policy Iteration for Risk-Averse Reinforcement Learningcited by 28
- 2022Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisationcited by 23
- 2023Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stabilitycited by 20
- 2013Concentration bounds for temporal difference learning with linear function approximation: The case of batch data and uniform samplingcited by 13
Built on by
Citing papers per year: 2026: 1.
1 paper.
Similar, not cited
Close in wording, no citation either way
- 2024Stochastic Approximation with Unbounded Markovian Noise: A General-Purpose Theorem
- 2025Efficient Q-Learning and Actor-Critic Methods for Robust Average-Reward Reinforcement Learning
- 2025Finite-time Convergence Analysis of Actor-Critic with Evolving Reward
- 2026Optimistic Actor-Critic with Parametric Policies for Linear Markov Decision Processes
- 2024A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach
- 2024On the Convergence of Single-Timescale Actor-Critic
- 2025An Actor-Critic Algorithm with Function Approximation for Risk Sensitive Cost Markov Decision Processes
- 2025Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach