  This paper studies optimization of the Conditional Value at Risk (CVaR) for a
discounted total-cost Markov Decision Process (MDP) with finite state and
action sets. This CVaR optimization problem can be reformulated as a Robust
MDP(RMDP) with a compact state space. States in this RMDP are the original
states of the problems augmented with tail risk levels, and the Decision Maker
(DM) knows only the initial tail risk level at the initial state and time.
Thus, in order to find an optimal policy following this approach, the DM needs
to solve an RMDP with incomplete state observations because after the first
move, the DM observes the states of the system, but the tail risk levels are
unknown. This paper shows that for the CVaR optimization problem the
corresponding RMDP can be solved by using the methods of convex analysis. This
paper introduces the algorithm for computing and implementing an optimal CVaR
policy by using the value function for the version of this RMDP with completely
observable tail risk levels at all states. This algorithm and the major results
of the paper are presented for a more general problem of optimization of sum of
a mean and CVaR for possibly different cost functions.
