Reward Redistribution for CVaR MDPs using a Bellman Operator on L-infinity

Tail-end risk measures such as static conditional value-at-risk (CVaR) are used in safety-critical applications to prevent rare, yet catastrophic events. Unlike risk-neutral objectives, the static CVaR of the return depends on entire trajectories without admitting a recursive Bellman decomposition in the underlying Markov decision process. A classical resolution relies on state augmentation with a continuous variable. However, unless restricted to a specialized class of admissible value functions, this formulation induces sparse rewards and degenerate fixed points. In this work, we propose a novel formulation of the static CVaR objective based on augmentation. Our alternative approach leads to a Bellman operator with: (1) dense per-step rewards; (2) contracting properties on the full space of bounded value functions. Building on this theoretical foundation, we develop risk-averse value iteration and model-free Q-learning algorithms that rely on discretized augmented states. We further provide convergence guarantees and approximation error bounds due to discretization. Empirical results demonstrate that our algorithms successfully learn CVaR-sensitive policies and achieve effective performance-safety trade-offs.

When training AI agents to make decisions, it is common to optimize for average performance. But in safety-critical domains, rare catastrophic failures matter far more than the average case: a self-driving car that crashes 1% of the time is unacceptable, even if its average performance is excellent. A risk measure called CVaR (Conditional Value-at-Risk) captures exactly this concern by focusing the agent on its worst-case outcomes. The challenge is that CVaR is mathematically awkward to optimize: it depends on the full trajectory of an agent's behavior, making it hard to decompose into the step-by-step updates that make standard reinforcement learning algorithms practical. Prior approaches often introduce additional state variables to track this information, but even then the resulting learning problem lacks a well-behaved recursive structure and often leads to convergence issues and "sparse rewards," where the agent receives almost no useful feedback during training, causing learning to stall or collapse. We introduce a new formulation based on reward redistribution, which reshapes how feedback is assigned across time so that CVaR can be computed through a well-behaved Bellman operator. This restores the kind of recursive structure that makes dynamic programming effective, while preserving the original CVaR objective. The result is a more principled and computationally stable foundation for learning risk-averse policies, helping enable AI systems that better account for rare but high-impact failures.