{"ID":6138911,"CreatedAt":"2026-07-09T01:07:32.349475501Z","UpdatedAt":"2026-07-10T23:21:00.654494504Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.06863","arxiv_id":"2607.06863","title":"Jacobi-like relative value iteration algorithms for ergodic risk-sensitive control of Markov chains","abstract":"We propose a Jacobi-like relative value iteration (RVI) algorithm and a Gauss-Seidel-like implementation for the ergodic risk-sensitive control (ERSC) problem of a controlled discrete time Markov chain (DTMC) on a finite state space. Under the assumption that the DTMC is irreducible and recurrent under every stationary Markov policy, we prove that the iterates of the proposed RVI algorithms converge at a geometric rate. The main challenge stems from the multiplicative structure of the ERSC cost criterion and the associated Bellman-like operators, which prevents us from adapting the analogous global contraction and bi-Lipschitz continuity properties that underlie the proof of convergence in the average cost setting. We overcome this by establishing local contraction properties for the risk-sensitive Bellman-like operators and a local bi-Lipschitz continuity property for their fixed points, and use these properties to show the iterates converge geometrically. We conclude by implementing our proposed RVI algorithms on two examples: service effort control for a single-server queue of finite capacity, and maximizing the exit rate from a finite domain (on a graph).","short_abstract":"We propose a Jacobi-like relative value iteration (RVI) algorithm and a Gauss-Seidel-like implementation for the ergodic risk-sensitive control (ERSC) problem of a controlled discrete time Markov chain (DTMC) on a finite state space. Under the assumption that the DTMC is irreducible and recurrent under every stationary...","url_abs":"https://arxiv.org/abs/2607.06863","url_pdf":"https://arxiv.org/pdf/2607.06863v1","authors":"[\"Sumith Reddy Anugu\",\"Guodong Pang\",\"Nicola Sassone\"]","published":"2026-07-07T23:30:34Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"math.PR\"]","methods":"[\"Large Language Model\"]","has_code":false}