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

1 Introduction

• The setting is finite discounted MDPs under recursive entropic risk, with a generative model that supplies samples for arbitrary state-action pairs.The paper contrasts recursive application to reward-to-go at each step with a static risk measure applied to total return; the formulations are not directly comparable and may suit different applications.Source: §1 · p. 1
• The analysis refines MB-RS-QVI sample-complexity bounds for both ε-close optimal Q-value learning and ε-optimal policy learning.The method is a plug-in model-based approach.Source: §1 · p. 2
• The bounds improve on the best existing effective-horizon dependence and match the lower bounds in their exponential dependence.Table 1 summarizes sample-complexity comparisons in the small-ε regime.Source: §1 · p. 2, Table 1 · p. 2

2 Related Work

• Risk-neutral sample-complexity techniques often exploit the additive structure of returns and generally do not extend to risk-sensitive objectives.The cited literature includes generative, offline, and online settings; Li et al. [2024b] derive an optimal bound over the entire ε-range using model-based methods with reward perturbations or conservative planning.Source: §2 · p. 2
• Recursive CVaR work provides a generative-setting lower bound, but its analysis relies on CVaR-specific structure that does not extend to ERM..Source: §2 · p. 3
• For discounted recursive ERM with a generative model, Mortensen and Talebi [2026b] provide PAC upper and lower bounds and are the closest prior work.Essakine and Vernade [2026] instead study finite-horizon, stage-dependent policy learning with trajectory samples.Source: §2 · p. 3
• Recursive OCE results include discounted-MDP PAC upper and lower bounds, but Mortensen and Talebi [2026a] do not improve ERM bounds when applied to this setting.ERM is not coherent, though it belongs to the OCE class for β > 0.Source: §2 · p. 3

3 Background

• The notation uses the max norm by default and writes finite p-norms with an explicit subscript..Source: §3 · p. 3

3.1 Entropic Risk Preferences

• ERM is the certainty equivalent induced by exponential utility, and its risk-neutral limit is expected value as β approaches zero.Under the paper's sign convention, β > 0 is risk-averse and β < 0 is risk-seeking.Source: §3.1 · pp. 3–4

3.2 Discounted Markov Decision Processes with Entropic Risk

• The model is a finite discounted infinite-horizon MDP with finite states and actions, transition probabilities, deterministic rewards, and discount factor γ.A stationary deterministic policy maps states to actions.Source: §3.2 · p. 4
• Recursive ERM defines policy value by iterating the risk functional, and the optimal value functions satisfy Bellman optimality equations with a stationary deterministic optimal policy.The Bellman operators for Q-functions are γ-contractions in max norm, supporting value-iteration approximation.Source: §3.2 · p. 4
• A generative model samples next states for queried state-action pairs, while learning is assessed by ε,δ-correct Q-value or policy outputs.Value correctness uses max-norm error from Q*; policy correctness uses max-norm error from V*.Source: §3.2 · p. 5

• MB-RS-QVI [Mortensen and Talebi, 2026b] is a model-based algorithm for value and policy learning under ERM in the generative setting.Source: §4 · p. 5
• The method takes N samples from each state-action pair, requiring T = NSA calls to the generative model.Source: §4 · p. 5
• Its empirical MDP uses the plug-in transition estimator, and the approach can use any oracle that returns an ε-optimal policy.The oracle can be implemented using a Q-value iteration method akin to the classical risk-neutral setting.Source: §4 · p. 5

5 Sample Complexity Analysis of MB-RS-QVI

• In the section’s sample-complexity analysis, for sufficiently small ε, terms of order ε^-2 dominate and the bound simplifies.The analysis concerns MB-RS-QVI under policy learning and value learning; Theorem 1 states a value-learning result, while Theorem 2 offers a policy-learning bound.Source: §5 · pp. 5–6

5.1 Comparison with Existing Bounds

• The leading term improves by O(e^|β|/(1−γ)), although its numerical constant is larger than in Mortensen and Talebi [2026b].The same improvement is reported for policy learning.Source: §5.1 · p. 6
• Under H ≍ (1−γ)^−1, Essakine and Vernade [2026] have the same order of exponential dependence, but their finite-horizon analysis does not transfer directly.Their finite-horizon recursion has a linear conditional expectation; the discounted recursive ERM setting composes the transition expectation with x→x^γ.Source: §5.1 · p. 7
• Value and policy upper bounds match Mortensen and Talebi [2026b] in exponential dependence, removing the exponential gaps; value learning retains an (1−γ)^−2 polynomial gap.For value learning, the match also covers S, A, ε, and β up to logarithmic factors.Source: §5.1 · p. 7
• At β→0, the value-learning bound is off by γ²(1−γ)⁻¹, and policy learning by γ²(1−γ)⁻¹ min{S, γ²(1−γ)⁻²}, versus minimax-optimal risk-neutral rates.Source: §5.1 · pp. 7–8

6.1 Proof of Theorem 1

• The value proof splits ε-value-correctness between model-approximation error and optimization error, each bounded by ε/2.The optimization error is controlled by taking enough iterations of the optimization oracle.Source: §6.1 · p. 8, §6 · p. 8
• Bernstein concentration and a Bhatia–Davis variance bound control the sampled exponential terms used to bound model-estimation error.For β < 0, the shifted exponential terms preserve the logarithmic ratio, so the same sample-complexity bound applies.Source: §6.1 · pp. 9–10

6.1.1 Proof of Theorem 2

• The policy argument controls both optimal-policy and learned-policy value-estimation errors on a shared high-probability event, then applies a greedy-policy bound.The event is formed using the fixed-policy bound across the policy class.Source: §6.1.1 · pp. 10–11
• After suitably adjusting the error probabilities, the final bound guarantees ε-policy-correctness with probability exceeding 1 −δ if T ≥ min{T1,δ/2, T2,δ/2}.Source: §6.1.1 · p. 11

7 Conclusions

• The paper studies value and policy sample complexity in finite discounted MDPs under recursive entropic risk with a generative model.Source: §7 · p. 11
• Refined MB-RS-QVI PAC bounds have the same exponential dependence as the corresponding minimax lower bounds for this setting.The conclusion notes a remaining gap between the upper and lower bounds.Source: §7 · p. 11
• Future directions include closing the upper- and lower-bound gap, developing model-free algorithms, and studying MDPs with function approximation.Source: §7 · p. 11

8 Supporting Lemmas

• A mean-value-theorem argument for log differences uses an intermediate point between x and y.The accompanying fragment supplies a lower bound on that intermediate point when x > y.Source: §8 · p. 15
• Bernstein’s inequality applies to independent, zero-mean random variables bounded in magnitude, with variance term V.Source: §8 · p. 15
• The Bhatia–Davis inequality assumes a random variable bounded between m and M and identifies its mean as μ.Source: §8 · p. 15