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.