Near-Optimal Sample Complexity for Recursive Entropic Risk Reinforcement Learning with a Generative Model

Amirparsa Bahrami; Oliver Mortensen; Mohammad Sadegh Talebi

cs.LGOct 3, 2026

Near-Optimal Sample Complexity for Recursive Entropic Risk Reinforcement Learning with a Generative Model

Authors: Amirparsa Bahrami, Oliver Mortensen, Mohammad Sadegh Talebi

Organizations: School of Electrical Engineering, Sharif University of Technology · Department of Computer Science, University of Copenhagen

Abstract

In this paper, we study the sample complexities of value and policy learning in finite discounted Markov decision processes (MDPs) under recursive entropic risk preferences with risk parameter $β\neq 0$ , assuming access to a generative model of the MDP. We provide a refined analysis of model-based risk-sensitive Q-value iteration (MB-RS-QVI), a plug-in model-based method introduced in prior work, and derive $(\varepsilon,δ)$ -PAC guarantees for both learning the optimal $Q$ -value function and an $\varepsilon$ -optimal policy. Our bounds improve the exponential dependence on the effective horizon $1/(1-γ)$ compared with the best existing guarantees for this setting. In particular, they match the existing lower bounds in their exponential dependence on $|β|/(1-γ)$ , as well as in $S$ , $A$ , $\varepsilon$ , and $|β|$ , up to logarithmic factors. Consequently, our analysis removes the exponential gap between the previously known upper and lower bounds, leaving only a polynomial gap in the effective horizon.

Figures & tables

Problem	Upper Bound	Lower Bound
Value Learning	$\widetilde{\mathcal{O}}\Big(\frac{SA}{\varepsilon^{2}(1-\gamma)^{2}\|\beta\|^{2}}e^{\|\beta\|/(1-\gamma)}\Big)$ [Thm. 1 ]	$\widetilde{\Omega}\Big(\frac{SA}{\varepsilon^{2}\|\beta\|^{2}}e^{\|\beta\|/(1-\gamma)}\Big)$ [ Mortensen and Talebi, 2026b , Thm. 3]
Value Learning	$\widetilde{\mathcal{O}}\Big(\frac{SA}{\varepsilon^{2}(1-\gamma)^{2}\|\beta\|^{2}}e^{2\|\beta\|/(1-\gamma)}\Big)$ [ Mortensen and Talebi, 2026b , Thm. 1]
Policy Learning	$\widetilde{\mathcal{O}}\Big(\frac{SA}{\varepsilon^{2}(1-\gamma)^{2}\|\beta\|^{2}}\min\big\{S,\frac{1}{(1-\gamma)^{2}}\big\}e^{\|\beta\|/(1-\gamma)}\Big)$ [Thm. 2 ]	$\widetilde{\Omega}\Big(\frac{SA}{\varepsilon^{2}\|\beta\|^{2}}e^{\|\beta\|/(1-\gamma)}\Big)$ [ Mortensen and Talebi, 2026b , Thm. 4]
Policy Learning	$\widetilde{\mathcal{O}}\Big(\frac{SA}{\varepsilon^{2}(1-\gamma)^{2}\|\beta\|^{2}}\min\big\{S,\frac{1}{(1-\gamma)^{2}}\big\}e^{2\|\beta\|/(1-\gamma)}\Big)$ [ Mortensen and Talebi, 2026b , Thm. 2]

Table 1: Summary and comparison of sample complexity bounds for recursive ERM in the small-

\varepsilon

regime, where the quadratic terms in

1/\varepsilon

dominate.

\beta

denotes the risk parameter, where

\beta>0

(respectively,

\beta<0

) corresponds to a risk-averse (respectively, risk-seeking) agent.

Risk-Sensitive RL

Risk-sensitive reinforcement learning optimizes policies for downside risk, tail outcomes, uncertainty, or safety constraints beyond expected reward.

See all 85 papers

Tight Sample Complexity Bounds for Entropic Best Policy Identification
May 13, 2026Amer Essakine, Claire VernadeReinforcement Learning Risk-Sensitive RL
ENS Paris Saclay · University of Technology Nuremberg
On the Sample Complexity of Discounted Reinforcement Learning with Optimized Certainty Equivalents
May 20, 2026Oliver Mortensen, Mohammad Sadegh TalebiReinforcement Learning Risk-Sensitive RL
Department of Computer Science, University of Copenhagen.
Provably Efficient Q-learning for Robust Reinforcement Learning
Oct 26, 2026Yuchen Jiao, Gen LiRobust RL Distributionally Robust RL
Department of Statistics and Data Science, Chinese University of Hong Kong.

May 13, 2026J/K move · Enter open · S save

Tight Sample Complexity Bounds for Entropic Best Policy Identification

Amer Essakine, Claire Vernade

ENS Paris Saclay · University of Technology Nuremberg

Reinforcement Learning Risk-Sensitive RL Policy Learning Sample-Efficient RL

Open paper AskPDF arXiv

We study best-policy identification for finite-horizon risk-sensitive reinforcement learning under the entropic risk measure. Recent work established a constant gap in the exponential horizon dependence between lower and upper bounds on the number of samples required to identify an approximately optimal policy. Precisely, known lower bounds scale in

Ω(e^{|β| H})

where

H

is the horizon of the MDP, while the state-of-the-art upper bound achieves at best

O(e^{2|β| H})

(arXiv:2506.00286v2) using a generative model. We show that this extra exponential factor can be traced to overly loose concentration control for exponential utilities. To close this open gap, we revisit the analysis of this problem through a forward-model based algorithm building on KL-based exploration bonuses that we adapt to the entropic criterion. The improvement we get is due to two main novel technical innovations. We leverage the smoothness properties of the exponential utility to derive sharper concentration bounds, and we propose a new stopping rule that exploits further this tightness to obtain a sample complexity that matches the lower bound.

Abstract

Risk-Sensitive RL

Explore similar work

Tight Sample Complexity Bounds for Entropic Best Policy Identification

On the Sample Complexity of Discounted Reinforcement Learning with Optimized Certainty Equivalents

Provably Efficient Q-learning for Robust Reinforcement Learning