Distributional Value Iteration

Definition

Distributional value iteration is a Bellman-style dynamic programming method that stores a distribution over future return/cost for each state rather than a scalar expected value.

Why It Matters

Scalar value iteration can optimize expectation while hiding variance and tail risk. Distributional value iteration makes risk-sensitive objectives such as CVaR available in formal planning and verification workflows.

Formalism / Key Objects

• For an MDP state s, DVI maintains a value distribution mu_s.
• A risk-neutral update in Elsayed-Aly2024 - Distributional Probabilistic Model Checking uses a distributional Bellman backup of the form

$$\eta (s,a):=\mathrm{proj}\left(r(s,a)+\sum _{s^{\prime }}P(s,a,s^{\prime }){\mu }_{s^{\prime }}\right),$$

then chooses the action minimizing the expected value of eta(s,a).

• Practical implementations project distributions into finite categorical or quantile representations.
• Risk-sensitive DVI for CVaR augments the MDP with a discretized slack/risk-budget variable and chooses actions using the dual CVaR objective involving E([X-b]^+).

Connections

• Used by Elsayed-Aly2024 - Distributional Probabilistic Model Checking to optimize distributional reward/cost objectives under co-safe LTL specifications.
• Related to distributional reinforcement learning, but in the model-checking setting the model is explicitly solved rather than learned from samples.
• Sound Value Iteration is the scalar-bounded cousin: it does not preserve full return distributions, but it makes reachability and expected-reward value iteration sound enough to serve as a safety certificate.
• Supports Safe Reinforcement Learning when tail risk matters more than average performance.
• Depends on Probability and Statistics for distribution representation and on Decision Theory for objective choice.

Common Confusions

• DVI is not automatically more accurate than scalar value iteration for expectation; its purpose is to preserve more information about the return distribution.
• Approximate distribution representations can change policy quality, especially with heavy tails or coarse support.
• Risk-neutral DVI and risk-sensitive DVI solve different objectives even when they operate on the same MDP.

Key Sources

• Elsayed-Aly2024 - Distributional Probabilistic Model Checking
• Quatmann2018 - Sound Value Iteration
• Distributional Queries and DVI