# Global Algorithms for Mean-Variance Optimization in Markov Decision Processes

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 40 references that are in the map.
- First posted on arXiv 27 Feb 2023.

## Builds on (most cited first, 7 of 7)

- [Risk-Averse Trust Region Optimization for Reward-Volatility Reduction](https://mlsanity.com/paper/1912.03193/) (2019)
- [Mean-Variance Policy Iteration for Risk-Averse Reinforcement Learning](https://mlsanity.com/paper/2004.10888/) (2020)
- [A Block Coordinate Ascent Algorithm for Mean-Variance Optimization](https://mlsanity.com/paper/1809.02292/) (2018)
- [Risk-Sensitive Markov Decision Processes with Combined Metrics of Mean and Variance](https://mlsanity.com/paper/2008.03707/) (2020)
- [A Generalized Fundamental Matrix for Computing Fundamental Quantities of Markov Systems](https://mlsanity.com/paper/1604.04343/) (2016)
- [A unified algorithm framework for mean-variance optimization in discounted Markov decision processes](https://mlsanity.com/paper/2201.05737/) (2022)
- [Mean-Variance Optimization of Discrete Time Discounted Markov Decision Processes](https://mlsanity.com/paper/1708.07095/) (2017)

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

- [Policy Optimization and Multi-agent Reinforcement Learning for Mean-variance Team Stochastic Games](https://mlsanity.com/paper/2503.22779/) (2025)

## Abstract (arXiv)

Dynamic optimization of mean and variance in Markov decision processes (MDPs) is a long-standing challenge caused by the failure of dynamic programming. In this paper, we propose a new approach to find the globally optimal policy for combined metrics of steady-state mean and variance in an infinite-horizon undiscounted MDP. By introducing the concepts of pseudo mean and pseudo variance, we convert the original problem to a bilevel MDP problem, where the inner one is a standard MDP optimizing pseudo mean-variance and the outer one is a single parameter selection problem optimizing pseudo mean. We use the sensitivity analysis of MDPs to derive the properties of this bilevel problem. By solving inner standard MDPs for pseudo mean-variance optimization, we can identify worse policy spaces dominated by optimal policies of the pseudo problems. We propose an optimization algorithm which can find the globally optimal policy by repeatedly removing worse policy spaces. The convergence and complexity of the algorithm are studied. Another policy dominance property is also proposed to further improve the algorithm efficiency. Numerical experiments demonstrate the performance and efficiency of our algorithms. To the best of our knowledge, our algorithm is the first that efficiently finds the globally optimal policy of mean-variance optimization in MDPs. These results are also valid for solely minimizing the variance metrics in MDPs.