The variance-penalized stochastic shortest path problem

2022/04/21 by Piribauer, Jakob, Sankur, Ocan, Baier, Christel · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Logic in Computer Science (cs.LO) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2204.12280

Abstract

The stochastic shortest path problem (SSPP) asks to resolve the non-deterministic choices in a Markov decision process (MDP) such that the expected accumulated weight before reaching a target state is maximized. This paper addresses the optimization of the variance-penalized expectation (VPE) of the accumulated weight, which is a variant of the SSPP in which a multiple of the variance of accumulated weights is incurred as a penalty. It is shown that the optimal VPE in MDPs with non-negative weights as well as an optimal deterministic finite-memory scheduler can be computed in exponential space. The threshold problem whether the maximal VPE exceeds a given rational is shown to be EXPTIME-hard and to lie in NEXPTIME. Furthermore, a result of interest in its own right obtained on the way is that a variance-minimal scheduler among all expectation-optimal schedulers can be computed in polynomial time.

Cited by

• Risk-aware Markov Decision Processes Using Cumulative Prospect Theory

Related

• Partial and Conditional Expectations in Markov Decision Processes with\n Integer Weights
• Stochastic Shortest Paths and Weight-Bounded Properties in Markov\n Decision Processes
• Computational Approaches for Stochastic Shortest Path on Succinct MDPs
• Variations on the Stochastic Shortest Path Problem
• Improved No-Regret Algorithms for Stochastic Shortest Path with Linear MDP