Tight Sample Complexity Bounds for Entropic Best Policy Identification
Abstract
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(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.
Related
- Near-Optimal Sample Complexity for Recursive Entropic Risk Reinforcement Learning with a Generative Model
- Sharp Convergence and Sample Complexity of Policy Mirror Descent for Average-Reward MDPs
- The Sample Complexity of Multiple Change Point Identification under Bandit Feedback
- Sample complexity bounds for categorical Markov random fields via Discrete Diffusions
- Improved Bounds for the Entropic Central Limit Theorem in the Log-Concave Case
BibTeX
@misc{essakine2026tight,
title = {{Tight Sample Complexity Bounds for Entropic Best Policy Identification}},
author = {Amer Essakine and Claire Vernade},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2605.13717},
eprint = {2605.13717},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2605.13717},
}
RIS
TY - UNPB
TI - Tight Sample Complexity Bounds for Entropic Best Policy Identification
AU - Amer Essakine
AU - Claire Vernade
PY - 2026
DA - 2026/09/21
PB - arXiv
DO - 10.48550/arxiv.2605.13717
UR - https://arxiv.org/abs/2605.13717
AB - 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.
ER -