cs.LGNov 7, 2026

Finite Time Analysis of Risk-Sensitive RL via Noisy Power Iteration

Authors: Waqar Mirza, Yashaswini Murthy, Laixi Shi, Eric Mazumdar, Adam Wierman

Organizations: California Institute of Technology · University of Texas at Austin · Johns Hopkins University

Abstract

Estimating the principal eigenpair of a positive operator from stochastic evaluations gives rise to a noisy form of normalized power iteration: each step applies a sampled operator estimate and then renormalizes. We establish finite-time stochastic-approximation guarantees for this procedure, working in Hilbert's projective metric, which is well-suited to the multiplicative geometry of Perron--Frobenius eigenproblems. Our main application is risk-sensitive average-cost reinforcement learning (RL) with exponential utility. In this setting the Bellman equations are multiplicative, and value functions are characterized by nonlinear eigenvalue problems rather than additive fixed points. We cast both policy evaluation and control in this framework, obtaining risk-sensitive TD- and Q-learning algorithms that learn from a single Markovian trajectory. Under explicit positivity, mixing, and linear function approximation assumptions, we prove finite-time bounds on the recovered eigenvector and eigenvalue with O~(ε−2)\tilde{O}(ε^{-2}) sample complexity up to problem-dependent constants. The results cover both tabular and linear function approximation regimes, and through the duality between exponential utility and KL-robust control yield finite-time guarantees for KL-robust average-cost RL as well.

Explore similar work

CardsList
  1. Provably Efficient Risk-Sensitive Offline Reinforcement Learning via Optimized Certainty Equivalents

    Oct 15, 2026Hanzhen Wang, Boxiang Lyu, Zhongxiang Dai +3Reinforcement LearningRisk-Sensitive RL

  2. Finite-Time Analysis of Discounted Exponential-Utility Reinforcement Learning

    Aug 3, 2026Ankur Naskar, Vivek T A, Aditya Kumar +2Reinforcement LearningRisk-Sensitive RL