ERQDP Solves Long-Term Decision Making Under Risk

This research addresses the challenge of long-term sequential decision-making in environments where risk is a critical factor. Specifically, it focuses on finite-horizon Markov Decision Process (MDP) planning under "root-based" risk objectives, which apply a rank-dependent functional to the distribution of total returns. These objectives are non-linear and typically break standard Bellman optimality, making direct optimization computationally intensive. The paper proposes ERQDP (Enumeration-free Rank-Quantile Dynamic Programming), a novel method that avoids scenario-tree enumeration and sampling. ERQDP solves a rank-quantile surrogate problem using exact dynamic programming, then evaluates candidate policies precisely by applying dynamic programming over return Probability Mass Functions (PMFs) on a discretized grid. It refines the surrogate in an anytime loop, providing explicit upper-lower bounds (certificates) for the target objective. Benchmarks show ERQDP delivers certified solutions or clear residual gaps, significantly speeds up risk-parameter sweeps, and supports both risk-averse and risk-seeking behaviors.