{"id":"6a1b006b-99b5-48ac-89ba-46bb54f429ac","arxiv_id":"2607.06863","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":3,"one_line_summary":"Two Jacobi- and Gauss-Seidel-like relative value iteration algorithms for finite-state ergodic risk-sensitive Markov decision processes are proven to converge geometrically under irreducibility and recurrence assumptions.","lead":"The paper proposes two new relative value iteration algorithms for solving ergodic risk-sensitive control problems on finite-state Markov chains, with proven geometric convergence. The methods offer practitioners new computational tools for optimization problems where decision-makers care about variance and tail risk, not just average cost.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"Geometric convergence in Theorem 2.2 requires step sizes bounded away from zero, a condition not explicitly stated; the proof in §4.3 asserts uniform geometric decay without establishing uniform contraction when γ_k → 0.","rationale":"The reader correctly identified Proposition 3.2 as a point of scrutiny, but upon careful examination, the bi-Lipschitz proof holds: the transformed chain's transition probabilities are bounded below by e^{-2M'} times the original (Eq. 3.18), and the original chain has uniform exponential tail bounds via L and α (Eqs. 3.12–3.13), giving finite expected return times under Q* (Eq. 3.26). The lower bound N_*(m,λ) is also finite because the exponent (δc̄-λ)τ̄ - m ≤ 0 (by Lemma 3.2), making the exponential moment bounded by E[τ_n] < ∞. So the reader's specific concern does not land. However, a different and more direct concern emerges in the final step of the main proof. The one-step bounds (2.23) are correctly established, but the leap from these bounds to the geometric convergence claim in Section 4.3 is not fully justified when step sizes decrease to zero. The contraction constant c_λ(γ_k, m) → 1 as γ_k → 0, so uniform geometric decay is not guaranteed. This is not a fatal flaw: the one-step bounds are correct, geometric convergence follows for constant step sizes, and the local contraction and bi-Lipschitz analysis (the paper's main technical contribution) is sound. The fix is a one-line qualification of the theorem (require γ_k ≥ γ_ > 0). I adjust the verdict from ACCEPT to CONDITIONAL because the geometric rate claim—the paper's central stated result—is overbroad as written. The paper's core innovation (new RVI algorithms with local contraction analysis for risk-sensitive control) remains valuable even with this qualification.","tokens_in":41975,"tokens_out":22875,"duration_ms":863761,"concrete_test":"Run Algorithm 1 on the single-server queue (Section 5.1, n=20, δ=10^{-2}) with two step-size schedules: (a) constant γ_k = γ̄, and (b) γ_k = 1/k. For each, log ||h^k - h*||_m versus k and fit the decay. If (a) shows linear decay in log-log (geometric) but (b) shows polynomial decay (linear in log k vs. log k), the geometric convergence claim requires qualification to constant or bounded-away-from-zero step sizes.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The proof of the 'in particular' part of Theorem 2.2 (Section 4.3) asserts that the one-step bounds (2.23) imply ||h^k - h*||_m ≤ C_0 e^{-C_1 k}. This step requires the contraction constants c_h(γ_k, m) and c_λ(γ_k, m) to be uniformly bounded away from 1 across all iterations. While c_h(γ, m) = β_m + γ(·) is increasing in γ and thus bounded above by c_h(γ̄, m) < 1, the constant c_λ(γ, m) = max{1 - γA, β_m γB, (1+β_m)/2} (from Lemmas D.3–D.4) approaches 1 as γ → 0, since the term 1 - γA → 1. The theorem states 'whenever γ_k ∈ (0, γ̄],' which includes sequences where γ_k → 0. For γ_k = 1/k (used in Section 5.2), the product Π c_λ(γ_k, m) decays polynomially (~k^{-A}), not geometrically. For γ_k = ξ^k (used in Section 5.1), the product Π(1 - Aξ^k) converges to a positive limit, so the bound does not even guarantee convergence to zero. The proof in Section 4.3 does not address this gap; it simply asserts the exponential bound follows from the one-step inequalities. The fix is straightforward—either require γ_k ≥ γ_ > 0 or restrict the geometric claim to constant step sizes—but as stated, the theorem's geometric convergence claim is not justified for all allowed step-size sequences. Remark 2.2 hints that 'an appropriate family of {γ_k}' is needed, but the theorem does not formalize this requirement.","agreement_with_reader":"partial"},"referee_report":{"model":"glm-5.2","summary":"The paper proposes two new relative value iteration (RVI) algorithms—a Jacobi-like version (Algorithm 1) and a Gauss-Seidel-like version (Algorithm 2)—for the ergodic risk-sensitive control (ERSC) problem of a finite-state controlled Markov chain. Under Assumption 2.1 (irreducibility and recurrence under every stationary Markov policy), the authors prove that the iterates converge geometrically to the solution pair (V*, λ*) of the multiplicative Bellman equation. The key technical innovation is overcoming the multiplicative structure of the risk-sensitive cost criterion, which prevents direct adaptation of the global contraction and bi-Lipschitz continuity arguments from the risk-neutral setting (Bertsekas, 1998). The authors instead establish local contraction properties for the risk-sensitive Bellman-like operators F and G (Propositions 3.1 and 4.3) and a local bi-Lipschitz continuity property for the fixed-point map λ ↦ h_λ (Proposition 3.2), using an entropy variational formula, Dynkin's formula, and a weighted supremum norm construction adapted from Tseng (1990). The paper concludes with two numerical examples: service-effort control for a finite-capacity queue and exit-rate maximization on a graph.","tokens_in":42266,"tokens_out":5464,"duration_ms":277945,"significance":"The paper makes a genuine contribution to the ERSC literature. The existing RVI algorithm for ERSC (Bielecki–Hernandez-Hernández–Pliska; Cavazos-Cadena–Montes-de Oca; Borkar–Meyn) requires either a self-loop positivity condition or an aperiodicity transformation, and its convergence analysis relies on span-semi-norm contraction of the multiplicative Bellman operator. The proposed algorithms avoid these requirements and introduce a fundamentally different update structure: the cost iterate λ_k is updated via a one-dimensional line-search rather than by direct evaluation of the Bellman operator at the reference state. The local contraction property (Proposition 3.1) is cleanly derived via the entropy variational formula and the weighted norm construction, and the local bi-Lipschitz continuity result (Proposition 3.2) is a non-trivial adaptation that addresses the failure of exponential moments to be finite for all λ ∈ ℝ (Remark 3.3). The Gauss-Seidel analysis (Lemma 4.1, Proposition 4.3) handles the additional recursive structure with appropriate uniform bounds. The numerical experiments are well-chosen, contrasting tridiagonal and sparse/dense transition structures, and the stepsize","major_comments":[{"comment":"Theorem 2.2, 'in particular' clause (Section 4.3): The geometric convergence claim is not justified for all step-size sequences satisfying γ_k ∈ (0, γ̄]. The one-step bounds (2.23) give |λ^{k+1} − λ*| ≤ c_λ(γ_k, m) |λ^k − λ*|, where c_λ(γ, m) = max{c_1(γ, m), c_2(m)} with c_1(γ, m) = max{1 − γA, β_m γ B} (A, B > 0; from Lemmas D.3–D.4) and c_2(m) = (1+β_m)/2. As γ → 0, the term 1 − γA → 1, so c_λ(γ, m) → 1. For a sequence γ_k → 0, the product Π_k c_λ(γ_k, m) may decay only polynomially (e.g., γ_k = 1/k gives ~k^{−A}) or may not converge to zero at all (e.g., γ_k = ξ^k gives Π(1 − Aξ^k) > 0). The proof in Section 4.3 simply asserts ||h^k − h*||_m ≤ C_0 e^{−C_1 k} without addressing this. The fix is straightforward: either require γ_k ≥ γ_ > 0 for all k (in which case c_λ(γ_k, m) ≤ c_λ(γ_, m) < 1 uniformly and geometric convergence follows), or restrict the geometric rate claim to constant","section":null}],"minor_comments":[{"comment":"Section 5: The numerical experiments use γ_k → 0 (γ_k ∝ ξ^k in Section 5.1, γ_k ∝ k^{−1} in Section 5.2), which are not covered by the geometric convergence guarantee even after the fix above. The authors should clarify that these are practical heuristics and that the theoretical guarantee applies to constant or bounded-away-from-zero step sizes.","section":null},{"comment":"Remark 2.7: The comparison with the existing RVI algorithm's convergence rate is useful, but it would help to note explicitly that the existing algorithm's multi-step span-semi-norm contraction (Eq. 2.24) and the proposed algorithms' one-step weighted-norm contraction (Eq. 2.23) are not directly comparable in terms of practical convergence speed, as confirmed by the numerical results in Table 1 where neither algorithm uniformly dominates.","section":null},{"comment":"Equation (2.17): The definition of η involves p(i,j) := inf_{u∈U} p(i,j,u), but the notation p(i,j) is also used for the transition probability p(i,j,u) with u suppressed. Consider using a distinct symbol (e.g., p̄(i,j)) for the infimum to avoid ambiguity.","section":null},{"comment":"Proposition 3.2, proof: The construction of the transformed DTMC with law Q* (Eq. 3.18) and the tail bound (3.24–3.25) are correct, but the inductive argument in (3.25) could benefit from explicitly stating the base case reference (it references (3.24) implicitly).","section":null},{"comment":"Appendix A: The notation table is helpful. Consider adding entries for χ(·) and η̄ (defined in (4.5) and Lemma 4.1), which appear in the Gauss-Seidel analysis.","section":null},{"comment":"Section 5.2: The recasting of the exit-rate problem as an ERSC problem is clean. It would be helpful to note that the running cost c(i,u) = log p_0(i,u) may be negative, and confirm that the theory (developed for c: S_U → ℝ_+) extends to this case. The lower bound c̄ in (2.22) would need adjustment.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The paper is a solid contribution that would fit well in a control/optimization journal. The step-size gap in Theorem 2.2 is the only substantive issue, and it is easily fixed. The local bi-Lipschitz continuity proof (Proposition 3.2) is the most technically delicate part; I verified the Dynkin formula argument and the tail bound construction and found them correct, though the dependence on the unknown fixed points h_λ, h_{λ'} makes the uniformity argument non-trivial. The authors should be asked to verify that the lower bound in (3.29) is indeed finite for the relevant λ-range (i.e., that the exponential moment E^{v'}_i[(τ_n − 1) e^{−((δc̄−λ)τ̄ − m) τ_n}] is finite), as this is assumed but not explicitly verified."},"author_rebuttal":null,"desk_editor":{"model":"glm-5.2","letter":"The paper proposes two new relative value iteration algorithms for finite-state ergodic risk-sensitive control: a Jacobi-like version and a Gauss-Seidel-like version. The key structural departure from existing RVI is the cost update via a one-dimensional line search with step-size γ_k, replacing the standard evaluation of the Bellman operator at a reference state. The authors prove geometric convergence under irreducibility and recurrence of the controlled chain under every stationary policy. The main technical contribution is a local contraction framework: because the multiplicative structure of the risk-sensitive cost prevents global contraction, they use the entropy variational formula to recast the Bellman-like operator in a variational form, establish local contraction under a weighted supremum norm (Proposition 3.1), and prove local bi-Lipschitz continuity of the fixed-point map λ ↦ h_λ (Proposition 3.2). The bi-Lipschitz proof is the hardest part — it constructs a transformed chain with unknown transition probabilities and bounds return times via tail estimates — and it's traceable, with the induction laid out explicitly. The Gauss-Seidel extension (Proposition 4.3) is nontrivial because of the recursive structure of the operator. Credit is due for a clean, self-contained proof that doesn't lean on aperiodicity or self-loop assumptions required by prior work. The numerical examples are illustrative but not the point. Now the soft spot, and it's real. The stress-test concern lands: the 'in particular' geometric convergence statement in Theorem 2.2 is not justified for all step-size sequences the theorem allows. The one-step bounds (2.23) give contraction constants c_h(γ_k, m) and c_λ(γ_k, m) that depend on γ_k. While c_h is bounded away from 1 for γ_k ∈ (0, γ̄], the constant c_λ(γ, m) from Lemmas D.3–D.4 contains the term 1 − γA, which approaches 1 as γ → 0. So for γ_k = 1/k (used in Section 5.2), the product of contraction constants decays polynomially, not geometrically. For γ_k = ξ^k (used in Section 5.1), the product converges to a positive limit and convergence isn't guaranteed at all. Section 4.3 simply asserts the exponential bound follows from the one-step inequalities without addressing this. The fix is straightforward: either require γ_k ≥ γ_ > 0 uniformly, or restrict the geometric claim to constant step sizes and state polynomial convergence for vanishing ones. This is a gap in the theorem statement, not a flaw in the core analysis. The local contraction and bi-Lipschitz machinery is sound. The paper deserves a serious referee who can verify the bi-Lipschitz tail bounds in Proposition 3.2 and push the authors to fix the step-size condition in Theorem 2.2.","headline":"New RVI algorithms for finite-state risk-sensitive control with a real but fixable gap in the geometric convergence claim","tokens_in":42896,"tokens_out":677,"would_cite":true,"duration_ms":143730,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"glm-5.2","headline":"New algorithms solve risk-sensitive control by local contraction","keywords":[],"falsifier":"A counterexample would be a controlled Markov chain satisfying the irreducibility assumption where the iterates of Algorithm 1 or 2 fail to converge geometrically—most plausibly because the local bi-Lipschitz constant N̄*(m, λ) blows up as m increases, meaning the region where the local estimates hold shrinks faster than the iterates can be confined, or because the fixed point h_λ ceases to exist for λ-values the algorithm visits during its line-search updates.","tokens_in":42237,"feed_emoji":"🎯","tokens_out":790,"duration_ms":154094,"temperature":0.7,"pith_summary":"The paper addresses a computational bottleneck in risk-sensitive control of Markov chains: how to numerically find optimal policies when the cost criterion involves an exponential utility, which makes the standard convergence tools from average-cost settings break down. The authors propose two iterative algorithms—a Jacobi-like and a Gauss-Seidel-like relative value iteration—that jointly update a value function and an optimal cost estimate. The key insight is that although the multiplicative (exponential) structure of the risk-sensitive Bellman operator prevents global contraction arguments, one can establish local contraction and local bi-Lipschitz continuity properties that are strong enough to guarantee geometric convergence. The central mechanism is a variational (entropy-based) reformulation of the Bellman operator that converts the multiplicative structure into an additive form with an auxiliary maximization over probability measures, allowing the authors to bound the operator's sensitivity using a carefully constructed weighted supremum norm. This norm, built from the transition graph's reachability structure, ensures that each iteration contracts the error by a fixed factor, provided the iterates stay within a bounded region—a condition the authors verify by tracking the step-size parameter and the state of the cost iterate.","feed_headline":"New algorithms solve risk-sensitive control by local contraction","feed_subtitle":"Jacobi and Gauss-Seidel value iterations converge geometrically for exponential-utility Markov control, via local contraction and bi-Lipsch","key_machinery":"The entropy variational formula (Donsker-Varadhan), applied to rewrite the logarithm inside the risk-sensitive Bellman operator as a supremum over probability measures; a weighted supremum norm built from the state-space partition by reachability classes and the minimum positive transition probability η; Dynkin's formula applied to the transformed Markov chain with law Q*; and tail-probability bounds on return times under Q* that circumvent the potentially infinite exponential moments in the stochastic representation of the fixed point h_λ.","core_discovery":"The paper's central claim is that the multiplicative structure of risk-sensitive control, which defeats the global contraction arguments used for average-cost problems, can be tamed locally: the risk-sensitive Bellman-like operators F and G (defined via logarithms of the multiplicative operator) satisfy local contraction properties under a weighted supremum norm, and the fixed points of these operators depend on the cost parameter λ in a locally bi-Lipschitz way. These two local properties, combined with a step-size-controlled line-search update for λ, suffice to prove geometric convergence of both algorithms. The bi-Lipschitz proof is the most delicate part: it constructs a transformed Mark","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["Local contractions tame risk-sensitive Markov control","Geometric convergence for risk-sensitive value iteration","Risk-sensitive Bellman operators contract locally","Multiplicative risk costs yield to local contraction","Jacobi RVI converges geometrically for risk-sensitive control"],"cache_read_input_tokens":0,"weakest_assumption_plain":"The local bi-Lipschitz continuity of the map from cost parameter to fixed point (Proposition 3.2) is load-bearing. The proof constructs a transformed Markov chain whose transition probabilities depend on the unknown fixed points h_λ and h_λ', then bounds expected return times under this transformed chain using tail-probability estimates. If these tail bounds are not uniform—or if the exponential moments in the stochastic representation of h_λ fail to be finite for the λ-range","fun_headline_variants_meta":{"raw":{"variants":["Local contractions tame risk-sensitive Markov control","Geometric convergence for risk-sensitive value iteration","Risk-sensitive Bellman operators contract locally","Multiplicative risk costs yield to local contraction","Jacobi RVI converges geometrically for risk-sensitive control","Local bi-Lipschitz unlocks risk-sensitive value iteration","Value iteration converges for exponential-utility control","Local contraction fixes multiplicative risk control","Gauss-Seidel meets risk-sensitive Markov chains","Step-size line search tames risk-sensitive Bellman iterates"]},"model":"glm-5.2","effort":"low","cost_usd":0.0,"raw_usage":{"total_tokens":822,"prompt_tokens":520,"completion_tokens":302,"prompt_tokens_details":null},"tokens_in":520,"tokens_out":302,"duration_ms":18790,"temperature":1.0,"reasoning_tokens":222,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-09T23:57:52.134346+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"A counterexample would be a controlled Markov chain satisfying the irreducibility assumption where the iterates of Algorithm 1 or 2 fail to converge geometrically—most plausibly because the local bi-Lipschitz constant N̄*(m, λ) blows up as m increases, meaning the region where the local estimates hold shrinks faster than the iterates can be confined, or because the fixed point h_λ ceases to exist for λ-values the algorithm visits during its line-search updates.","supporting_citations":[],"review_version":1}