Mean-Variance Optimization in Markov Decision Processes

Abstract

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 pseudopolynomial exact and approximation algorithms.

A full version of an ICML 2011 paper

Cited by in corpus (4)

• Exploration vs Exploitation vs Safety: Risk-averse Multi-Armed Bandits
• Risk-Sensitive Reinforcement Learning: a Martingale Approach to Reward Uncertainty
• Estimation Error Correction in Deep Reinforcement Learning for Deterministic Actor-Critic Methods
• Expectations or Guarantees? I Want It All! A crossroad between games and MDPs