Publication
INFORMS 2021
Talk

A Strongly Polynomial Algorithm for Risk Constrained Problems

View publication

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.

Date

24 Oct 2021

Publication

INFORMS 2021

Authors

Tags

Share