Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approach

Yinlam Chow; Aviv Tamar; Shie Mannor; Marco Pavone

Source-linked AI summary

Risk-Sensitive and Robust Decision-Making: a CVaR Optimization Approach

Yinlam Chow, Aviv Tamar, Shie Mannor, Marco Pavone

arXiv:1506.02188v1Jun 6, 2015cs.AImath.OC

TL;DR

The paper addresses MDP decision making when both cost risk and modeling errors matter. It formulates a CVaR MDP, relates CVaR to worst-case model perturbations, and develops approximate value iteration with convergence and error guarantees. The resulting framework unifies risk-sensitive and robust decision making within the supported setting.

Problem
Standard risk-neutral MDP objectives do not account for cost variability or sensitivity to modeling errors, motivating a risk-sensitive formulation that addresses both concerns.
Method
The paper minimizes a CVaR objective and solves CVaR MDPs using approximate value iteration with linear interpolation over an augmented state space containing the confidence level.
Results
CVaR of discounted cost is equivalent to expected cost under worst-case transition-probability perturbations within an error budget, while the algorithm has explicit finite-time error bounds and convergence rates.
Takeaways & Limitations
CVaR MDPs provide a unified framework for planning under cost variability and model uncertainty, with error bounds that can determine when to stop the algorithm.
Takeaways & Limitations
The conclusion identifies extensions to large state spaces as future work, although it conjectures that sampling-based approximate dynamic programming may be feasible.

Abstract

from arXiv · show

In this paper we address the problem of decision making within a Markov decision process (MDP) framework where risk and modeling errors are taken into account. Our approach is to minimize a risk-sensitive conditional-value-at-risk (CVaR) objective, as opposed to a standard risk-neutral expectation. We refer to such problem as CVaR MDP. Our first contribution is to show that a CVaR objective, besides capturing risk sensitivity, has an alternative interpretation as expected cost under worst-case modeling errors, for a given error budget. This result, which is of independent interest, motivates CVaR MDPs as a unifying framework for risk-sensitive and robust decision making. Our second contribution is to present an approximate value-iteration algorithm for CVaR MDPs and analyze its convergence rate. To our knowledge, this is the first solution algorithm for CVaR MDPs that enjoys error guarantees. Finally, we present results from numerical experiments that corroborate our theoretical findings and show the practicality of our approach.

1 Introduction

The paper frames CVaR MDPs as a unified approach to decision making under cost variability and model uncertainty. It also develops an approximate solution algorithm with finite-time error guarantees and evaluates its practicality numerically.

Motivation: Risk-neutral MDP objectives overlook cost variability and sensitivity to modeling errors, while risk-sensitive and robust MDPs address these aspects separately.
Risk–robustness connection: CVaR of an MDP’s discounted cost equals the expected cost under worst-case transition-probability perturbations within a specified error budget.
Contributions: The paper’s first contribution interprets CVaR MDPs as a framework for decision making under both cost variability and model uncertainty.
Contributions: The proposed algorithm combines approximate value iteration with linear interpolation on an augmented state space, yielding explicit error bounds and convergence rates.
Contributions: Unlike prior methods described by the authors, the approach provides finite-time error guarantees and computes optimal policies across CVaR confidence intervals and initial states simultaneously.

2 Preliminaries, Problem Formulation, and Motivation

The paper formulates risk-sensitive decision making in MDPs through CVaR of discounted cost and interprets this objective as robustness against budgeted transition-probability perturbations.

2.1 Conditional Value-at-Risk: CVaR measures tail risk in discounted MDP costs, complementing standard expected-cost objectives that overlook cost variability and sensitivity to modeling errors.CVaR is useful for controlling rare, potentially disastrous events and has coherent risk-measure properties.
2.1 Conditional Value-at-Risk: CVaR admits a dual interpretation as the worst-case expectation under a perturbed probability distribution within a risk envelope.This representation motivates connecting CVaR to adversarial model perturbations.
2.2 Markov Decision Processes: An MDP comprises finite states and actions, bounded deterministic costs, transition probabilities, an initial state, and discount factor γ ∈[0, 1).Policies may depend on complete histories, with actions selected as functions of observed histories.
2.3 Problem Formulation: The CVaR MDP minimizes the CVaR of total discounted cost over a sequence of history-dependent policies.The formulation directly targets risk sensitivity in sequential decision making.
2.4 Motivation - Robustness to Modeling Errors: For a specific perturbation structure and budget, worst-case expected discounted cost equals the CVaR objective, linking risk sensitivity with robustness to transition-model errors.The perturbations modify transition matrices multiplicatively while preserving stochasticity.
2.4 Motivation - Robustness to Modeling Errors: The perturbation budget is split multiplicatively along each trajectory, preventing the adversary from selecting the worst perturbation independently at every time step.This temporal structure is less conservative than uncertainty sets allowing the worst case at each stage.
2.4 Motivation - Robustness to Modeling Errors: The paper develops a dynamic-programming formulation whose value function depends on both state and CVaR confidence level, supporting approximate solution methods.The subsequent approach addresses the continuous augmented confidence-level state through approximation and interpolation.

3 Bellman Equation for CVaR

The CVaR dynamic-programming formulation augments the MDP state with a confidence level and yields a Bellman equation whose unique fixed point is optimal. This supports value iteration and policy construction on the augmented state space.

CVaR Bellman formulation: CVaR decomposition recursively evaluates future costs using confidence levels that change with the next-state transition.The recursion maximizes an expectation over admissible risk distortions ξ and continuation CVaR terms.
CVaR Bellman formulation: The augmented value function depends on both the physical state x and confidence level y ∈ (0, 1].The additional continuous state records the CVaR confidence level required by the recursive decomposition.
Bellman-operator properties: The CVaR Bellman operator preserves concavity in y, making its maximization subproblem concave.This property later supports tractable optimization and interpolation-error control.
Optimality: The Bellman operator’s unique fixed point equals the optimal CVaR value for the MDP.For initial state x and confidence level α, the fixed point equals the minimum CVaR over history-dependent policies.
Optimality: An optimal stationary Markov policy can be obtained greedily from the value function over the augmented state space.An optimal history-dependent policy can also be constructed from the augmented Markov policy.
Value iteration: Value iteration converges to the optimal value by repeatedly applying the Bellman operator.The recursion starts from an arbitrary initial value-function guess and updates V_k+1(x, y) = T[V_k](x, y).

4 Value Iteration with Linear Interpolation

The paper approximates CVaR value iteration by interpolating the value function over a finite confidence-level grid. Concavity and contraction preserve tractability, convergence, and explicit interpolation-error guarantees.

Approximation design: Continuous confidence levels make direct value iteration impractical, motivating linear interpolation over finitely many y-values.The approximation evaluates the Bellman operator only at interpolation points and interpolates between them.
Assumptions: The initial value function must make yV_0(x, y) concave and V_0(x, y) continuous in y.These conditions ensure the structural properties needed by the approximation analysis.
Approximation design: The interpolation is applied to yV(x, y), whose piecewise-linear structure and preserved Lipschitzness support error control.Interpolating yV rather than V is central to the method.
Convergence: The interpolated Bellman operator preserves contraction and concavity, so each maximization is concave and the algorithm is tractable.Its contraction property also guarantees convergence to a limiting interpolated value function.
Convergence: The converged interpolated value iteration has geometric convergence rate γ.The rate follows from the contraction property of the interpolated operator.
Error guarantees: The interpolation approximation error is O((θ −1)+ϵ) and tends to zero as ϵ →0 and yi+1/yi →1.The theorem also characterizes the interpolated value function as a conservative estimate of the optimal solution.

5 Experiments

Experiments on a 3,312-state grid world evaluate the approximation and compare risk-neutral with risk-averse policies under terrain-map perturbations. Lower CVaR confidence reduces collisions while increasing travel distance, and risk aversion improves robustness to perturbations.

Experimental setup: The evaluation uses a 64 × 53 grid world with 3,312 states, δ = 0.05, γ = 0.95, and 21 log-spaced interpolation points.The setup includes 80 obstacles and an effective horizon of 200 steps.
Risk sensitivity: Decreasing the CVaR confidence parameter slightly increases average travel distance while decreasing collision probability.Figure 1 reports value functions and corresponding paths for three confidence levels.
Robustness to modeling errors: Over 400 perturbed-scenario evaluations, the risk-neutral policy incurred 120+ failed runs, whereas the risk-averse policy incurred 5.The policies were trained on the nominal terrain and tested across 20 perturbed maps with 20 Monte Carlo evaluations each.
Robustness to modeling errors: The risk-neutral policy’s average cost was 18.137 on successful runs, compared with 18.878 for the risk-averse policy.The longer risk-averse routes traded higher successful-run cost for substantially fewer failures under perturbations.
Computational cost: Computing Algorithm 1 took on the order of two hours in the reported implementation.The authors identify parallelization and sampling-based methods as possible improvements.

6 Conclusion

The paper concludes that approximate value iteration provides convergence and finite-time error guarantees for CVaR MDPs, while CVaR also connects risk sensitivity with robustness to correlated model perturbations. Extending the approach to large state spaces remains future work.

Contributions: The proposed augmented-state approximate value-iteration algorithm converges and has finite-time error bounds usable for stopping at a target error threshold.These guarantees are stated as central algorithmic outcomes of the paper.
Risk and robustness: CVaR of total cost is related to worst-case expected cost under adversarial model perturbations correlated over time.This differs from robust-MDP uncertainty that is temporally independent.
Implications: The resulting framework is presented as unifying robustness to stochasticity and model perturbations for computing control policies.The conclusion characterizes the framework as practical within the supported setting.
Future work: Future work should address extensions to large state spaces.The authors conjecture that sampling-based approximate dynamic programming may be feasible because the CVaR Bellman equation is contracting.

A.2 Proof of Lemma 3

Lemma 3 establishes structural properties of the Bellman operator, including monotonicity, constant shifts, contraction, and preservation of concavity. The proof derives these properties from nonnegative transition-weight terms, concavity, and the feasible uncertainty set.

The Bellman operator’s monotonicity and constant-shift properties follow directly from its definitions and nonnegative transition probabilities.
The contraction property follows by bounding two value functions uniformly and applying monotonicity and the constant-shift property.
The proof establishes concavity preservation by combining concavity of the minimum, the assumed concavity of the value expression, and nonnegative transition probabilities.
The inner maximization is shown to be a concave maximization, including the case y = 0 and the case y ≠ 0 under the concavity assumption.
Concavity in ξ together with the polytope structure of the feasible set completes the proof of the relevant claim.

A.3 Proof of Theorem 4

Theorem 4 proves that the Bellman fixed point equals the optimal infinite-horizon CVaR value. The proof uses finite-horizon induction, tail-subproblem decomposition, and contraction-based convergence.

Finite-horizon value iteration is linked to the CVaR objective by induction from the Bellman operator definition.
The contraction argument and bounded initialization support the limit characterization of the optimal CVaR objective.
Tail-subproblem arguments show that extending an optimal continuation policy yields a feasible policy for the preceding tail problem.
The Bellman expression combines immediate cost with a worst-case expectation over the CVaR uncertainty set and the updated confidence interval.
The value function is a fixed point of the Bellman operator, and uniqueness implies equality with the optimal history-dependent CVaR value.

A.4 Proof of Theorem 5

Theorem 5 characterizes optimality for augmented stationary Markovian policies through their induced Bellman operator and corresponding history-dependent policy. The proof relies on uniqueness of fixed points and equivalence of the induced policy value.

A policy-induced Bellman operator is defined for augmented stationary Markovian policies over the state and confidence variables.
The induced operator has a unique fixed point, which the CVaR decomposition theorem identifies with the corresponding policy value.
An augmented stationary Markovian policy is optimal if and only if its induced history-dependent policy is optimal for the original problem.
The proof concludes that the selected augmented policy u∗ is an optimal augmented stationary Markovian policy.

A.5 Proof of Lemma 6

Lemma 6 proves monotonicity, constant-shift behavior, contraction, and concavity preservation for the interpolated operator. The argument analyzes piecewise-linear interpolation across confidence-variable intervals.

Monotonicity follows because interpolation preserves the ordering of value functions, while CVaR transition weights are nonnegative.
The constant-shift property is obtained from the interpolation identity Ix[V + K](y) = Ix[V](y) + yK.
The contraction proof for the interpolated operator follows from its monotonicity and constant-shift properties.
Concavity is established by checking slope inequalities across adjacent and separated interpolation intervals.
The interpolated function is continuous and piecewise linear, and concavity on the nonzero domain extends to the full domain by continuity.

A.6 Useful Intermediate Results

The intermediate results establish that linear interpolation preserves concavity and does not increase the Lipschitz constant, enabling corresponding regularity bounds for the Bellman recursion.

Interpolation properties: Linear interpolation preserves concavity and has Lipschitz constant no greater than the original function's constant M.This follows for concave, almost-everywhere differentiable functions with Lipschitz constant M.
Interpolation properties: The interpolation slope on each segment is bounded by the maximum derivative magnitude on that segment, yielding MI ≤ M.The argument considers both increasing and decreasing endpoint values before maximizing over all segments.
Bellman regularity: If yV(x, y) is concave and M-Lipschitz, the Bellman-transformed function yT[V](x, y) is Lipschitz with constant Cmax + γM.The bound is obtained using the transition kernel, first-order optimality, and the envelope theorem.
Bellman regularity: Algorithm 1 preserves Lipschitz continuity across iterations, with M1 ≤ Cmax + γM0 and a recursively bounded constant thereafter.The induction applies the Bellman operator to the linearly interpolated value function at each iteration.

A.7 Proof of Theorem 7

The proof bounds interpolation and Bellman-recursion errors, then uses contraction to show convergence of interpolation-based value iteration to the CVaR value function.

Proof structure: Theorem 7's proof separately bounds statewise interpolation error, Bellman-operator approximation error, and the accumulated interpolation error under contraction.These are the three parts of the proof.
Interpolation error: The derivative bound from Lemma 10 is M := Cmax/(1 − γ) + M0, which controls the interpolation error across the four regions of the state space.The proof analyzes y = 0, interior intervals, the final interval, and the interval near zero.
Interpolation error: 0 ≥ Ix[Vt](y)/y − Vt(x, y) ≥ −2M(θ − 1) − ϵ for every iteration t, state x, and y.The bound combines the four interval cases and the geometric spacing condition yi+1 = θyi.
Convergence: Bellman contraction propagates the one-step interpolation bound geometrically, with γ^n vanishing as n approaches infinity.The recursion uses translational invariance and repeated application of the Bellman operator.
Convergence: As n → ∞, exact value iteration converges to the optimal CVaR objective while interpolated value iteration converges to bV*(x, y).The proof combines the contraction property with the interpolation-error bounds to establish the theorem's claim.