Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

Semismooth Newton Methods for Risk-Averse Markov Decision Processes

T0 review · 3 major / 4 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper shows that risk-averse Markov decision processes with coherent risk measures admit a unified semismooth Newton solution framework, with three provably convergent algorithms and risk-averse policy iteration as a special case.

desk verdict Solid semismooth Newton framework for risk-averse MDPs, with a real error in the CVaR dual set and a few proof gaps that should be fixed before publication. read the letter →

arxiv 2501.13612 v1 pith:6HPU5DHM submitted 2025-01-23 math.OC

Matilde Gargiani , Francesco Micheli , Anastasios Tsiamis , John Lygeros This is my paper · ORCID
classification math.OC MSC 90C4049M1590C39
keywords risk-averseMarkovdecisionprocessesMarkoviancoherentriskmeasuressemismoothNewtonmethodspolicyiterationoptimisticconditionalvalueatBellmanresidualconvergenceanalysis
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper is trying to establish that risk-averse Markov decision problems can be solved by a general class of semismooth Newton methods, rather than by algorithms tuned to one risk measure. Working with Markovian coherent risk measures, it rewrites the risk-averse Bellman equation $v = Dv$ as a nonsmooth root-finding problem for the residual $r(v)=v-Dv$, then builds three local approximations of this residual. Each approximation turns one Newton step into the solution of a surrogate Bellman equation or linear system, and each comes with convergence guarantees. The paper also shows that the already-known risk-averse policy iteration method is one of these Newton instances, which it offers as an explanation of that method's fast convergence relative to risk-averse value iteration. If the framework is right, the practical payoff is a unified recipe for designing provably convergent solvers across coherent risk measures, demonstrated numerically on CVaR benchmarks.

What carries the argument

The load-bearing object is the risk-averse Bellman residual $r(v)=v-Dv$, where $D$ is the risk-averse Bellman optimality operator built from the risk-transition map $\chi$. The enabling identity is the dual representation $\chi(v,P(i,a))=\max_{\tilde p\in\mathcal{P}_\chi(P(i,a))}\langle v,\tilde p\rangle$, which turns each evaluation of the risk measure into a worst-case expectation over a compact convex set of perturbed transition distributions. From this, the paper defines row-stochastic matrices $P^{\tilde v}_\pi$ whose rows are the argmax distributions, together with surrogate risk-neutral Bellman operators $T^{\tilde v}$ and $T^{\tilde v}_\pi$. The three approximation families $\Xi_1$, $\Xi_2$, and $\Xi_3$ plug these operators into the semismooth Newton local model $r(v)+\xi(v,d)=0$, so each Newton iterate becomes the fixed point of a surrogate Bellman operator or the solution of a linear system. This machinery carries both the convergence proofs and the interpretation of risk-averse policy iteration as an instance of Newton's method.

What would settle it

Fix a small finite MDP with CVaR as the risk measure, compute $v^*$ by risk-averse value iteration, and run SNMIII from several starting points within a shrinking neighborhood of $v^*$. The paper predicts Q-superlinear convergence in that neighborhood because CVaR is piecewise affine; if the measured ratios $\|v_{k+1}-v^*\|/\|v_k-v^*\|$ stay bounded away from zero for every starting point and neighborhood tested, the local convergence theorem would be contradicted. Independently, running SNMI and checking whether the iterates remain non-decreasing from the second step and bounded above by $v^*$ tests the global convergence claim directly.

Watch

Extended reading notes

Core claim

The central claim is that the risk-averse Bellman equation $v = Dv$, where $D$ is the risk-averse Bellman optimality operator formed from a Markovian coherent risk measure, can be solved by semismooth Newton methods on the nonsmooth residual $r(v)=v-Dv$. Using the dual representation of the risk-transition map as a support function over a compact convex set of transition probabilities, the paper constructs three local approximation schemes. The resulting algorithms, called SNMI, SNMII, and SNMIII, each reduce a Newton step to solving a surrogate Bellman equation or linear system for a risk-neutral MDP whose transition probabilities are worst-case distributions tied to the current cost estimate. The paper proves global convergence for SNMI and for a risk-averse optimistic policy iteration variant, identifies SNMII with the existing risk-averse policy iteration method, and proves local superlinear convergence for SNMIII, upgrading to Q-quadratic convergence when the risk measure is piecewise affine, as CVaR is. On this account, the observed speed advantage of risk-averse policy iteration over risk-averse value iteration is explained by its Newton-type local model rather than by the contraction rate alone.

Load-bearing premise

The entire construction relies on the assumption that the risk measure admits, for every state-action pair, a dual representation as the worst-case expectation over a compact convex set of perturbed transition probabilities; if that representation fails, the perturbed transition matrices used by every algorithm are undefined.

Editorial extensions

If this is right

  • If the framework is correct, any Markovian coherent risk measure that admits the dual representation can be plugged into the same three templates, so users are not locked into a single risk measure.
  • Risk-averse policy iteration is shown to be a semismooth Newton method, which explains why it converges much faster than risk-averse value iteration in practice.
  • Risk-averse optimistic policy iteration, with a finite number of inner value-iteration steps per outer loop, converges globally to the optimal cost from any starting vector.
  • For piecewise affine risk measures such as CVaR, the local Newton models satisfy the strong approximation condition, giving Q-quadratic convergence near the solution.
  • SNMIII reduces each iteration to solving one linear system of the state dimension, making it the cheapest Newton-type update among the three while retaining local superlinear convergence.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Editorial inference: because the dual set in the representation is also a distributionally robust ambiguity set, the same algorithms should apply to MDPs with uncertain transition kernels, a direction the paper does not explore.
  • Editorial inference: the framework separates the risk model from the solver, so other coherent risk measures with tractable dual sets could be substituted into the same convergence theorems, though only CVaR is tested here.
  • Editorial inference: the experiments indicate that risk-averse optimistic policy iteration is not time-competitive despite its global convergence; replacing its inner value-iteration steps with a small number of semismooth Newton steps would be a natural testable variant.
  • Editorial inference: each Newton step solves a surrogate risk-neutral MDP, so inexact and distributed linear-algebra techniques for large-scale risk-neutral MDPs could be imported to make the risk-averse solvers scale, a path the paper lists as future work.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper studies discounted infinite-horizon MDPs with finite state and action spaces and Markovian coherent risk measures in the sense of Ruszczynski [27]. It rewrites the risk-averse Bellman optimality equation v = Dv as a nonsmooth root-finding problem r(v) = 0 and proposes a semismooth Newton framework. Three approximation families are introduced, yielding SNMI, SNMII (shown to coincide with Ruszczynski's risk-averse policy iteration), and SNMIII; global convergence is proved for SNMI and for a risk-averse optimistic policy iteration (Algorithm 3), and local superlinear convergence is claimed for SNMIII under a piecewise continuously differentiable assumption. Numerical experiments on CVaR MDPs compare the proposed methods with risk-averse value iteration and optimistic policy iteration.

Significance. If the central claims are correct, the semismooth perspective provides a useful unifying explanation for risk-averse policy iteration and gives new convergent algorithms with competitive practical performance. The global convergence proofs for SNMI and risk-averse OPI are largely self-contained, and the public implementation is a strength. However, the CVaR dual set in Eq. (65) is internally inconsistent and must be corrected, and the local superlinear result for SNMIII rests on assumptions that are not fully verified; these issues do not invalidate the general framework but need to be fixed before the paper can be accepted.

major comments (3)
  1. [Section 8, Eq. (65)] The displayed dual set for CVaR is incorrect. Since p̃ ∈ S_n and p̃_i = P_i ξ_i with ξ_i ≥ 1, the constraint Σ p̃_i = 1 forces ξ_i = 1 for every i with P_i > 0; hence Pχ(P(s,a)) = {P(s,a)}. If this set were used in (26), all proposed algorithms would reduce to solving a risk-neutral MDP, contradicting the CVaR problem (64) and the LP in (66). The correct dual feasible set is {p̃ : 0 ≤ p̃ ≤ P(s,a)/ζ, Σ p̃ = 1}, i.e., the feasible set of (66). The manuscript must correct (65) and the surrounding text, including the sentence that defines p̃(s_t,a_t) = ⟨P(s_t,a_t), ξ⟩, which is dimensionally inconsistent.
  2. [Section 6, Theorem 8] The proof of local superlinear convergence relies on identifying the active pieces of the residual with Z(v) in (59) and on applying Theorem 7.2.15 of [11], but two assumptions are not verified. First, Algorithm 4 does not specify how π_{k+1} is chosen when multiple policies satisfy D_{π} v_k = D v_k, so the claim that the generated sequence is unique is not justified. Second, the identification of the active pieces as v - T^v_π v with D_π v = D v is asserted rather than proved. Please prove these statements or reformulate the convergence result for any selection from the greedy policy set under appropriate assumptions.
  3. [Section 5, Theorem 7] The proof of global convergence of Algorithm 3 defers the step lim_{k→∞} (v̄_k - v_k) = 0 to the authors' unpublished manuscript [14]. This is an auxiliary but necessary step for transferring convergence of the shifted sequence to the original sequence. It follows readily from Lemma 2 and the shift property; please include a direct, self-contained proof rather than citing [14].
minor comments (4)
  1. [Section 2, Lemma 2 proof] The sentence 'Similar step prove (9)' should read 'Similar steps prove (9).'
  2. [Section 4, Eq. (36)] The dummy variable is written '∀ V ∈ R^n' but V is not used; it should be v for consistency.
  3. [Section 6, Eq. (58)] The notation 'V*' in Eq. (58) should be 'v*' for consistency with the rest of the paper.
  4. [References] References [8] and [9] appear to be the same paper (arXiv and NIPS versions); consider citing a single version.

Circularity Check

1 steps flagged · score 2.0 of 10

No significant circularity: the Bellman-residual semismooth framework is derived from stated assumptions and external convergence theory; only a minor self-citation in the OPI proof and a separate CVaR dual-set inconsistency merit attention.

  1. other [Theorem 7 proof, Section 5 (risk-averse optimistic policy iteration convergence)]
    "Since lim k→∞ ¯v k − v k = 0 (for details see the proof of Proposition 9 in [14]), from (55) we can also conclude that {v k } converges to v ∗."

    This is a self-citation to the authors' own prior work [14] for the shift-limit argument that transfers convergence from the b-shifted iterates to the original unshifted iterates. The step is load-bearing for the proof of Algorithm 3, one of the paper's claimed contributions, but the cited proposition is a separately published convergence argument and the rest of the proof is carried out in the paper. It is therefore a minor, independently checkable self-citation rather than a definitional reduction; the central semismooth framework does not depend on it.

full rationale

No material circularity was found in the main derivation. The paper starts from Ruszczynski's Markovian coherent risk representation (5), defines the risk-averse Bellman residual (15), and chooses three Newton approximation families whose local models are algebraically verified in Lemma 5. The convergence theorems then follow from monotonicity, γ-contractivity, and standard semismooth Newton theory [11], not from fitting or from the target result being assumed. SNMII is explicitly identified as Ruszczynski's risk-averse policy iteration, so the 'semismooth Newton interpretation' is a genuine reframing rather than a circular prediction. The numerical section reports benchmark performance without fitting parameters to those benchmarks. Two caveats: (i) the proof of Theorem 7 cites the authors' [14] for a shift-limit detail; this is auxiliary and independently published, so it does not raise the circularity score above 2. (ii) Independently of circularity, Eq. (65) is internally inconsistent: since p̃ = P(s,a) ⊙ ξ with ξ ∈ [1,1/ζ]^n and p̃ must sum to one, the constraint forces ξ_i = 1 on every state with P_i(s,a)>0, so Pχ(P(s,a)) collapses to the nominal kernel {P(s,a)}; the correct CVaR dual feasible set is the box-and-simplex set in Eq. (66). This is a manuscript error in the CVaR example, not a circularity, and it should be corrected, but it does not invalidate the general framework.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claims rest on the Markovian coherent risk measure dual representation (5) and, for the local superlinear theorem, on PC1 regularity of chi. No free parameters are fitted to data, and no new physical or conceptual entities (particles, forces, etc.) are introduced.

assumptions (4)
  • domain assumption Markovian coherent risk measure with risk-transition mapping chi satisfying the dual representation (5) as a support function of a compact convex set P_chi(P(i,a)).
    Invoked at the start of Section 2 and used throughout to define the perturbed transition matrices in (26) and all three Newton approximation schemes. Taken from Ruszczynski [27].
  • ad hoc to paper chi is piecewise continuously differentiable (PC1) in its first argument for the local superlinear convergence of SNMIII (Theorem 8).
    Assumed in Theorem 8 to connect SNMIII to piecewise smooth Newton [11, Chapter 7]; verified for CVaR in Proposition 9.
  • standard math The risk-averse Bellman operators D and D_pi are monotone and gamma-contractive in the infinity norm, with unique fixed points.
    Cited from Ruszczynski [27, Lemma 1-2, Theorem 4] and used in almost every convergence proof in Sections 4-6.
  • standard math Semismooth Newton theory: strong Newton approximation schemes with the stated Lipschitz properties yield Q-quadratic convergence (Theorem 3); piecewise smooth Newton convergence (Theorem 7.2.15 in [11]).
    These are external standard results in nonsmooth analysis and variational theory, cited from [11] and [19].

how reviews work

0 comments
Cite this review

Pith. "Pith review of Semismooth Newton Methods for Risk-Averse Markov Decision Processes." pith.science (2026). https://pith.science/paper/6HPU5DHM

@misc{pith2026250113612,
  author       = {Pith},
  title        = {Pith review of: Semismooth Newton Methods for Risk-Averse Markov Decision Processes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/6HPU5DHM}},
  note         = {Machine review of arXiv:2501.13612}
}
read the original abstract

Inspired by semismooth Newton methods, we propose a general framework for designing solution methods with convergence guarantees for risk-averse Markov decision processes. Our approach accommodates a wide variety of risk measures by leveraging the assumption of Markovian coherent risk measures. To demonstrate the versatility and effectiveness of this framework, we design three distinct solution methods, each with proven convergence guarantees and competitive empirical performance. Validation results on benchmark problems demonstrate the competitive performance of our methods. Furthermore, we establish that risk-averse policy iteration can be interpreted as an instance of semismooth Newton's method. This insight explains its superior convergence properties compared to risk-averse value iteration. The core contribution of our work, however, lies in developing an algorithmic framework inspired by semismooth Newton methods, rather than evaluating specific risk measures or advocating for risk-averse approaches over risk-neutral ones in particular applications.

Figures

Figures reproduced from arXiv: 2501.13612 by the authors.

Figure 1
Figure 1. We consider an artificial MDP with n = 100, m = 5, γ = 0.9, CVaR with ζ = 0.3 as risk-measure. faster local contraction properties of semismooth New￾ton methods with respect to risk-averse value iteration. In particular, as it is displayed in Figure 1a, while SN￾MII (black bold line) reaches convergence to tolerance of 10−6 in less than 10 iterations, risk-averse value itera￾tion (= risk-averse OPI, w = 1 depicted w… view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Inside madupite: Technical Design and Performance

    cs.SE 2025-07 conditional novelty 5.0 of 10

    madupite is a distributed, customizable MDP solver based on inexact policy iteration that scales to millions of states on HPC clusters.

Reference graph

Works this paper leans on

31 extracted references · 28 canonical work pages · cited by 1 Pith paper

  1. [14]

    Inexact policy iteration methods for large-scale Markov decision processes, 2024

    Matilde Gargiani, Robin Sieber, Efe Balta, Dominic Liao- McPherson, and John Lygeros. Inexact policy iteration methods for large-scale Markov decision processes, 2024

    work page 2024

  2. [27]

    Risk-averse dynamic programming for Markov decision processes

    Andrzej Ruszczy´ nski. Risk-averse dynamic programming for Markov decision processes. Mathematical Programming, 125:235–261, 06 2014

    work page 2014

  3. [11]

    Finite-Dimensional Variational Inequalities and Complementarity Problems, Vol

    Francisco Facchinei and Jong-Shi Pang. Finite-Dimensional Variational Inequalities and Complementarity Problems, Vol. II. Springer, 1st edition, 2003

    work page 2003

  4. [1]

    CVXOPT: Convex Optimization

    Martin Andersen, Joachim Dahl, and Lieven Vandenberghe. CVXOPT: Convex Optimization. Astrophysics Source Code Library, record ascl:2008.017, August 2020

    work page 2008

  5. [2]

    Coherent measures of risk

    Philippe Artzner, Freddy Delbaen, Jean-Marc Eber, and David Heath. Coherent measures of risk. Mathematical Finance, 9(3):203–228, 1999

    1999

  6. [3]

    Dynamic Programming

    Richard Bellman. Dynamic Programming . Princeton University Press, Princeton, NJ, USA, 1 edition, 1957

    work page 1957

  7. [4]

    Bertsekas

    Dimitri P. Bertsekas. Dynamic Programming and Optimal Control, Vol. II. Athena Scientific, 3rd edition, 2007

    work page 2007

  8. [5]

    Markov decision processes with applications to finance

    Nicole B¨ auerle and Ulrich Rieder. Markov decision processes with applications to finance. Springer, Berlin, 2011

    work page 2011

Show all 31 references
  1. [6]

    Risk aversion in finite Markov decision processes using total cost criteria and average value at risk

    Stefano Carpin, Yin-Lam Chow, and Marco Pavone. Risk aversion in finite Markov decision processes using total cost criteria and average value at risk. In2016 IEEE International Conference on Robotics and Automation (ICRA), pages 335– 342, 2016

    2016

  2. [7]

    Algorithms for CVaR optimization in MDPs

    Yinlam Chow and Mohammad Ghavamzadeh. Algorithms for CVaR optimization in MDPs. In Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2 , NIPS’14, page 3509–3517, Cambridge, MA, USA, 2014. MIT Press

    2014

  3. [8]

    Risk-sensitive and robust decision-making: a CVaR optimization approach

    Yinlam Chow, Aviv Tamar, Shie Mannor, and Marco Pavone. Risk-sensitive and robust decision-making: a CVaR optimization approach. ArXiv, abs/1506.02188, 2015

    2015 arXiv

  4. [9]

    Risk-sensitive and robust decision-making: a CVaR optimization approach

    Yinlam Chow, Aviv Tamar, Shie Mannor, and Marco Pavone. Risk-sensitive and robust decision-making: a CVaR optimization approach. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems , volume 28. Curran Assoc...

    2015

  5. [10]

    Finite-Dimensional Variational Inequalities and Complementarity Problems, Vol

    Francisco Facchinei and Jong-Shi Pang. Finite-Dimensional Variational Inequalities and Complementarity Problems, Vol. I. Springer, 1st edition, 2003

    2003

  6. [12]

    Inexact GMRES policy iteration for large-scale Markov decision processes

    Matilde Gargiani, Dominic Liao-McPherson, Andrea Zanelli, and John Lygeros. Inexact GMRES policy iteration for large-scale Markov decision processes. IF AC-PapersOnLine, 56(2):11249–11254, 2023. 22nd IF AC World Congress

    2023

  7. [13]

    madupite: A high-performance distributed solver for large-scale Markov decision processes

    Matilde Gargiani, Philip Pawlowsky, Robin Sieber, Vaclav Hapla, and John Lygeros. madupite: A high-performance distributed solver for large-scale Markov decision processes. Under revision at JOSS , 2024

    2024

  8. [15]

    Dynamic programming through the lens of semismooth Newton-type methods

    Matilde Gargiani, Andrea Zanelli, Dominic Liao-McPherson, Tyler Summers, and John Lygeros. Dynamic programming through the lens of semismooth Newton-type methods. IEEE Control Systems Letters , 6:2996–3001, 2022

    2022

  9. [16]

    Iterative solution of large sparse systems of equations , volume 95 of Applied Mathematical Sciences

    Wolfgang Hackbusch. Iterative solution of large sparse systems of equations , volume 95 of Applied Mathematical Sciences. Springer-Verlag, New York, 1994

    1994

  10. [17]

    Markov Decision Processes with Their Applications

    Qiying Hu and Wuyi Yue. Markov Decision Processes with Their Applications. Springer New York, NY, 2010

    2010

  11. [18]

    On the convergence and optimality of policy gradient for Markov coherent risk

    Audrey Huang, Liu Leqi, Zachary Chase Lipton, and Kamyar Azizzadenesheli. On the convergence and optimality of policy gradient for Markov coherent risk. ArXiv, abs/2103.02827, 2021

    2021 arXiv

  12. [19]

    Izmailov and Mikhail V

    Alexey F. Izmailov and Mikhail V. Solodov. Newton- Type Methods for Optimization and Variational Problems . Springer, 1st edition, 2014

    2014

  13. [20]

    Value at risk models in finance

    Simone Manganelli and Robert Engle. Value at risk models in finance. SSRN Electronic Journal , 09 2001

    2001

  14. [21]

    Tsitsiklis

    Shie Mannor and John N. Tsitsiklis. Algorithmic aspects of mean–variance optimization in Markov decision processes. European Journal of Operational Research , 231(3):645–653, 2013

    2013

  15. [22]

    Georg Ch. Pflug. Some Remarks on the Value-at-Risk and the Conditional Value-at-Risk , pages 272–281. Springer US, Boston, MA, 2000

    2000

  16. [23]

    Puterman and Shelby L

    Martin L. Puterman and Shelby L. Brumelle. On the convergence of policy iteration in stationary dynamic programming. Mathematics of Operations Research, 4(1):60– 69, 1979

    1979

  17. [24]

    Qi and H

    L. Qi and H. Jiang. Semismooth Karush-Kuhn-Tucker equations and convergence analysis of Newton and quasi- Newton methods for solving these equations. Mathematics of Operations Research, 22(2):301–325, 1997

    1997

  18. [25]

    Lecture 7: Average value-at-risk

    Svetlozar Rachev. Lecture 7: Average value-at-risk. University Lecture, 2008

    2008

  19. [26]

    Tyrrell Rockafellar and Stanislav Uryasev

    R. Tyrrell Rockafellar and Stanislav Uryasev. Optimization of conditional value-at risk. Journal of Risk , 3:21–41, 2000

    2000

  20. [28]

    Iterative methods for sparse linear systems

    Yousef Saad. Iterative methods for sparse linear systems. SIAM, 2003

    2003

  21. [29]

    Value- at-risk vs conditional value-at-risk in risk management and optimization

    Sergey Sarykalin, Gaia Serraino, and Stan Uryasev. Value- at-risk vs conditional value-at-risk in risk management and optimization. Tutorials in Operations Research, 09 2008

    2008

  22. [30]

    Markov Decision Processes for Screening and Treatment of Chronic Diseases

    Lauren Steimle and Brian Denton. Markov Decision Processes for Screening and Treatment of Chronic Diseases. 03 2017

    2017

  23. [31]

    Policy gradient for coherent risk measures

    Aviv Tamar, Yinlam Chow, Mohammad Ghavamzadeh, and Shie Mannor. Policy gradient for coherent risk measures. In Proceedings of the 28th International Conference on Neural Information Processing Systems - Volume 1 , NIPS’15, page 1468–1476, Cambridge, MA, USA, 2015. MIT Press. 13

    2015

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.