On the Maximization of Long-Run Conditional Value-at-Risk for Markov Decision Processes

Risk-seeking is a widely existing attitude of decision makers. This paper studies a risk-seeking Markov decision process (MDP), where the risk is measured by conditional value-at-risk (CVaR). The objective is to find a policy that maximizes the long-run CVaR of instantaneous rewards over an infinite horizon among all history-dependent randomized policies. By establishing two optimality inequalities with opposing directions, we prove that the maximum of long-run CVaR of MDPs can be found within the class of stationary randomized policies. In contrast to risk-neutral and risk-averse MDPs, we find that an optimal stationary deterministic policy may not exist for maximizing CVaR. Instead, we prove the existence of an optimal stationary randomized policy that requires randomizing over at most two actions. Via a convex optimization formulation of CVaR, we convert the long-run CVaR maximization MDP into a minimax problem. We prove the interchangeability of minimum and maximum and the existence of related saddle point solutions. Furthermore, we present a linear programming algorithm that finds an optimal policy by reformulating the saddle point problem into two linear programs. By utilizing the structure properties of the saddle point problem, we also propose a gradient descent algorithm that can globally find an optimal policy with faster computation. These results are then extended to objectives that involve maximizing the combination of mean and CVaR of rewards. Finally, we conduct numerical experiments to demonstrate the main results.

Funding: This work was supported in part by the National Key Research and Development Program of China [Grant 2022YFA1004600] and the National Natural Science Foundation of China [Grants 72342006, 72371253, 72301303, and 72461160315].

Supplemental Material: All supplemental materials, including the code, data, and files required to reproduce the results, are available at https://doi.org/10.1287/opre.2025.1811.