  This paper addresses objectives tailored to the risk-averse optimization of
accumulated rewards in Markov decision processes (MDPs). The studied objectives
require maximizing the expected value of the accumulated rewards minus a
penalty factor times a deviation measure of the resulting distribution of
rewards. Using the variance in this penalty mechanism leads to the
variance-penalized expectation (VPE) for which it is known that optimal
schedulers have to minimize future expected rewards when a high amount of
rewards has been accumulated. This behavior is undesirable as risk-averse
behavior should keep the probability of particularly low outcomes low, but not
discourage the accumulation of additional rewards on already good executions.
The paper investigates the semi-variance, which only takes outcomes below the
expected value into account, the mean absolute deviation (MAD), and the
semi-MAD as alternative deviation measures. Furthermore, a penalty mechanism
that penalizes outcomes below a fixed threshold is studied. For all of these
objectives, the properties of optimal schedulers are specified and in
particular the question whether these objectives overcome the problem observed
for the VPE is answered. Further, the resulting algorithmic problems on MDPs
and Markov chains are investigated.
