Mean-Variance Optimization in Markov Decision Processes

By Shie Mannor, John N. Tsitsiklis. 2011

131 citations recorded by the source corpus.

We consider finite horizon Markov decision processes under performance measures that involve both the mean and the variance of the cumulative reward. We show that either randomized or history-based policies can improve performance. We prove that the complexity of computing a policy that maximizes the mean reward under a variance constraint is NP-hard for some cases, and strongly NP-hard for others. We finally offer pseudopoly-nomial exact and approximation algorithms.

Subfields: Artificial Intelligence, Computer Networks and Communications, Management Science and Operations Research, Reinforcement Learning, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Management Science and Operations Research

In Reinforcement Learning

In Optimization & Training

Citations in the corpus

Addressing Function Approximation Error in Actor-Critic Methods (2018, background): “Further, the variance of the value estimate has been considered directly for risk-aversion (Mannor & Tsitsiklis, 2011) and exploration (O’Donoghue et al., 2017), but without connection to overestimation bias.”
The Uncertainty Bellman Equation and Exploration (2017, background): “Unlike most prior work, we focus upon the epistemic uncertainty over the mean of the value function, rather than the higher moments of the reward-to-go [16, 1, 18].”
A Distributional Perspective on Reinforcement Learning (2017, background): “Mannor & Tsitsiklis (2011) provides negative results regarding the computation of a variance-constrained solution to the optimal control problem.”
Safe Exploration in Markov Decision Processes (2012, background): “The issue of safety, or risk aversion in MDPs has been addressed before [2, 3, 4, 5, 6, 7, 8], but few of the proposed methods provide strong probabilistic guarantees [6], and they tend to assume uncorrelated ambiguity in the system dynamics.”
A Review of Safe Reinforcement Learning: Methods, Theory and Applications (2022, background): “Moreover, it is deduced that the minus variance [178] and percentile optimisation [69] of safe RL is in general an NP-hard problem [193].”
A Review of Safe Reinforcement Learning: Methods, Theories, and Applications (2024, unknown): “Moreover, it is deduced that the mean minus variance [10] and percentile optimisation [11] of safe RL are, in general, NP-hard problems [12].”
Linear Fitted-Q Iteration with Multiple Reward Functions (2012, background): “Even within RL itself, our approach could provide a new perspective on trading off achieving high expected reward with avoiding risk, an issue explored by Mannor and Tsitsiklis (2011).”
Efficient exploration with Double Uncertain Value Networks (2017, background): “Mannor and Tsitsiklis (2011) theoretically studies policies that bound the variance of the return.”
Risk Aversion in Markov Decision Processes via Near Optimal Chernoff Bounds (2012, methodology): “A number of methods have been proposed for relaxations of mean minus variance optimization [3, 7].”
A comprehensive survey on safe reinforcement learning (2015, background): “Additionally, mean minus variance optimization within the MDP framework has been shown to be NP-hard in general, and optimizing this criterion can directly lead to counterintuitive policies (Mannor and Tsitsiklis, 2011).”
How Should a Robot Assess Risk? Towards an Axiomatic Theory of Risk in Robotics (2017, background): “ k. Before providing a formal deﬁnition, we note that failure to satisfy time consistency or the local property can lead to “irrational” behavior, including: (1) intentionally seeking to incur losses [21], or (2) deeming states to be dangerous when in fact they are favorable under any realization of”