Finite-Time Analysis of Discounted Exponential-Utility Reinforcement Learning
2026-08-03 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study a way to make decisions that consider risk by using discounted exponential utility, which is tricky because of its math complexity. They build on earlier work that created two learning algorithms but only showed they work in the long run. This paper proves how quickly these algorithms learn under realistic conditions, even without needing to fine-tune stepsizes. The authors handle tough math challenges by carefully analyzing operator properties and error behaviors, providing the first clear time-based guarantees for this kind of risk-sensitive learning.
discounted exponential utilityreinforcement learningBellman equationasynchronous Markovian samplingfinite-time convergenceone-timescale algorithmtwo-timescale algorithmPolyak--Ruppert averagingLyapunov functionmodel-free learning
Authors
Ankur Naskar, Vivek T A, Aditya Kumar, Gugan Thoppe, Prashanth L. A
Abstract
Discounted exponential utility provides a principled criterion for risk-sensitive sequential decision-making, but its nonlinear structure complicates reinforcement learning. A recent work \citep{thoppe2026reinforcement} addressed this difficulty by introducing a Bellman-compatible surrogate and two model-free fixed-point algorithms for optimizing it over stationary policies. However, their main convergence results are asymptotic. In this work, we establish finite-time rates of $\tilde{O} (1/\sqrt{n})$ for the aforementioned two algorithms under asynchronous Markovian sampling, where $n$ is the iteration index and $\tilde{O}$ hides logarithmic expressions. Importantly, we employ parameter-free choices for the stepsize parameter to derive these rate results. For the algorithmically simpler one-timescale method, the main challenge is that its update equation is not directly aligned with the contraction geometry of its underlying power-law operator. We overcome this mismatch by exploiting the boundedness, monotonicity, and homogeneity of the operator to obtain a local pseudo-contraction property for the relative-error dynamics. We then use a Moreau-envelope-based Lyapunov function and Polyak--Ruppert averaging to obtain the stated convergence rate with parameter-free stepsizes. For the two-timescale method, the main challenge is to control a tracking error on the faster timescale. These results provide the first finite-time guarantees for model-free discounted exponential-utility reinforcement learning.