# Finite-Time Analysis of Discounted Exponential-Utility Reinforcement Learning

arXiv: https://arxiv.org/abs/2608.01917 · HTML: https://mlsanity.com/paper/2608.01917/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 11 of its 28 references that are in the map.
- First posted on arXiv 3 Aug 2026.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 11 of 11)

- [Risk-sensitive Reinforcement Learning](https://mlsanity.com/paper/1311.2097/) (2013)
- [A Lyapunov Theory for Finite-Sample Guarantees of Asynchronous Q-Learning and TD-Learning Variants](https://mlsanity.com/paper/2102.01567/) (2021)
- [Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation](https://mlsanity.com/paper/2207.04475/) (2022)
- [Cumulative Prospect Theory Meets Reinforcement Learning: Prediction and Control](https://mlsanity.com/paper/1506.02632/) (2015)
- [Variance-Constrained Actor-Critic Algorithms for Discounted and Average Reward MDPs](https://mlsanity.com/paper/1403.6530/) (2014)
- [Stochastic Approximation for Risk-aware Markov Decision Processes](https://mlsanity.com/paper/1805.04238/) (2018)
- [A Risk-Sensitive Approach to Policy Optimization](https://mlsanity.com/paper/2208.09106/) (2022)
- [Ergodic Risk-sensitive control -- A survey](https://mlsanity.com/paper/2301.00224/) (2022)
- [Risk Estimation in a Markov Cost Process: Lower and Upper Bounds](https://mlsanity.com/paper/2310.11389/) (2023)
- [Parameter-free Optimal Rates for Nonlinear Semi-Norm Contractions with Applications to Q-Learning](https://mlsanity.com/paper/2508.05984/) (2025)
- [Reinforcement Learning for Exponential Utility: Algorithms and Convergence in Discounted MDPs](https://mlsanity.com/paper/2605.08053/) (2026)

## Abstract (arXiv)

Discounted exponential utility provides a principled criterion for risk-sensitive sequential decision-making, but its nonlinear structure complicates reinforcement learning. A recent work citepthoppe2026reinforcement 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 tildeO (1/√n) for the aforementioned two algorithms under asynchronous Markovian sampling, where n is the iteration index and tildeO 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.