mlsanityData to 14 Oct 2026

Tight Sample Complexity Bounds for Entropic Best Policy Identification

arXiv 2605.13717 ↗First posted 13 May 2026cs.LG stat.MLcited by 1

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (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 Omega(e|β| H) where H is the horizon of the MDP, while the state-of-the-art upper bound achieves at best O(e2|β| 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.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 2 of its 30 references that are in the map. First posted on arXiv 13 May 2026.

Builds on

2 of 30 references.

Closest ancestors · 1

Same direction, newest first

  1. 2025Recursive Entropic Risk Optimization in Discounted MDPs: Sample Complexity Bounds with a Generative Model30 May

Other references · 1

  1. 2025Efficient Risk-sensitive Planning via Entropic Risk Measurescited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Near-Optimal Sample Complexity for Recursive Entropic Risk Reinforcement Learning with a Generative Modelcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026On the Sample Complexity of Discounted Reinforcement Learning with Optimized Certainty Equivalents
  2. 2025Convergence and Sample Complexity of First-Order Methods for Agnostic Reinforcement Learning
  3. 2026Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning
  4. 2021Infinite-Horizon Offline Reinforcement Learning with Linear Function Approximation: Curse of Dimensionality and Algorithm
  5. 2022On Gap-dependent Bounds for Offline Reinforcement Learning
  6. 2026Sample complexity of variance-reduced policy gradient: weaker assumptions and lower bounds
  7. 2025Near-Optimal Sample Complexity for Iterated CVaR Reinforcement Learning with a Generative Model
  8. 2026Pure Exploration for a Good Policy in Reinforcement Learning with Bandit Feedback