Abstract: Stochastic domains often involve risk-averse decision makers. While recent work has focused on how to model risk in Markov decision processes using risk measures, it has not addressed the problem of solving large risk-averse formulations. In this paper, we propose and analyze a new method for solving large risk-averse MDPs with hybrid continuous-discrete state spaces and continuous action spaces. The proposed method iteratively improves a bound on the value function using a linearity structure of the MDP. We demonstrate the utility and properties of the method on a portfolio optimization problem.
Introduction
Standard algorithms for Markov Decision Processes (MDPs) typically operate under a risk-neutral paradigm, aiming to maximize the expected average reward. However, in critical domains such as finance and energy management, optimizing for the mean is insufficient if the policy permits a non-negligible probability of catastrophic loss. While coherent risk measures like Average Value at Risk (AV@R) provide a mathematical framework for risk-aversion, applying them to large-scale, continuous-state problems has historically been computationally prohibitive due to the "curse of dimensionality."
This paper introduces Risk-averse Dual Dynamic Programming (RDDP), a scalable algorithm designed to solve large-scale MDPs with continuous states and actions by exploiting the underlying linear structure of specific problem domains.
The RDDP Algorithm
RDDP targets Hybrid Linearly Controlled MDPs, which feature a combination of discrete states (e.g., market regimes) and continuous states (e.g., portfolio balances). The algorithm relies on the theoretical proof that for this class of problems, the cost-to-go value function is piecewise affine and convex. This allows the complex value function to be approximated as the maximum of a set of linear "cuts."
The algorithm proceeds through iterative refinement:
- Forward Pass: Samples likely states through simulation to explore the state space.
- Backward Pass: Calculates new linear cuts to sharpen the approximation of the value function.
- LP Duality: By representing the AV@R risk measure as a linear programming (LP) problem, the risk-aversion calculation is embedded directly into the optimization step, maintaining computational efficiency comparable to standard linear solvers.
Experimental Evaluation: Dynamic Portfolio Management
The authors evaluated RDDP using a dynamic portfolio management simulation based on historical NYSE data (1927–1996). The model estimated parameters for three risky assets and one risk-free asset across 19 discretized market states and four continuous dimensions of asset holdings. A traditional discretization of this state space would require solving for approximately 9 billion variables, a feat impossible for standard solvers but manageable via RDDP’s structural approximations.
Results and Insights
RDDP demonstrated rapid convergence and significant scalability. In the portfolio test, the algorithm successfully identified a policy that prioritized capital preservation. While a risk-neutral policy allocated 90% of wealth to volatile small-cap stocks, the RDDP-optimized risk-averse policy allocated 90% to cash, resulting in returns with near-zero variance.
As shown in the convergence plot, the RDDP upper bound on final wealth tightens significantly within the first few iterations. The algorithm identified critical risk areas of the state space almost immediately, with the bound reducing by a factor of 26.9 within just three iterations. This efficiency suggests that RDDP can effectively bypass the curse of dimensionality by focusing only on the linear cuts that define the optimal value function's boundary.
Conclusion and Future Work
RDDP provides a robust framework for solving high-dimensional, risk-averse MDPs. However, its application is currently limited to problems with linear (or affine) transitions and costs. Future research may explore extending this approach to non-linear systems or investigating the "diversification paradox" observed in the results, where the AV@R-optimized policy preferred a heavy cash position over traditional asset diversification. Additionally, developing more robust stopping criteria for tail-event optimization remains a key challenge for the field.
Summary updated