A Strongly Polynomial Algorithm for Risk Constrained Problems

Abstract

We consider a Markov Decision Process problem with risk related constraint. The constraint is a linearized variance approximation. We find a policy that maximizes a ratio of the reward expectation to its linearized variance. We show that under monotonicity assumption which is natural for risk related problem the Simplex algorithm with Gass-Saaty shadow-vertex pivoting rule is strongly polynomial for both cost models: discounted and expected average for infinite horizon. We show an application of the algorithm to the problem of maximization of the Sharpe ratio.