# A Finite-Sample Analysis of an Actor-Critic Algorithm for Mean-Variance Optimization in a Discounted MDP

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

## Key facts

- Cited by 1 papers 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.

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

- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Global Convergence of Policy Gradient Methods to (Almost) Locally Optimal Policies](https://mlsanity.com/paper/1906.08383/) (2019)
- [On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration](https://mlsanity.com/paper/2004.04719/) (2020)
- [On the Sample Complexity of Actor-Critic Method for Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/1910.08412/) (2019)
- [Risk-Averse Trust Region Optimization for Reward-Volatility Reduction](https://mlsanity.com/paper/1912.03193/) (2019)
- [Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation](https://mlsanity.com/paper/2207.04475/) (2022)
- [Variance-Constrained Actor-Critic Algorithms for Discounted and Average Reward MDPs](https://mlsanity.com/paper/1403.6530/) (2014)
- [Mean-Variance Policy Iteration for Risk-Averse Reinforcement Learning](https://mlsanity.com/paper/2004.10888/) (2020)
- [Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisation](https://mlsanity.com/paper/2210.05918/) (2022)
- [Improved High-Probability Bounds for the Temporal Difference Learning Algorithm via Exponential Stability](https://mlsanity.com/paper/2310.14286/) (2023)
- [Concentration bounds for temporal difference learning with linear function approximation: The case of batch data and uniform sampling](https://mlsanity.com/paper/1306.2557/) (2013)
- [Zeroth-Order Actor-Critic: An Evolutionary Framework for Sequential Decision Problems](https://mlsanity.com/paper/2201.12518/) (2022)

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

- [Nonparametric Variance-Penalized Actor-Critic: Statistical Inference for Risk-Sensitive Reinforcement Learning](https://mlsanity.com/paper/2609.14327/) (2026)

## 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.