Conceptio › Archive › arXiv CS

arXiv CSopen access

Tight Sample Complexity Bounds for Entropic Best Policy Identification

2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

neural-networks

machine learning, deep learning, neural networks

Proceedings of Machine Learning Research vol :1–55, 2026

39th Annual Conference on Learning Theory

Tight Sample Complexity Bounds for Entropic Best Policy Identification Amer Essakine

[email protected]

ENS Paris Saclay

Claire Vernade

[email protected]

arXiv:2605.13717v1 [cs.LG] 13 May 2026

University of Technology Nuremberg Editors: Steve Hanneke and Tor Lattimore

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 Ωpe|β|H q where H is the horizon of the MDP, while the state-of-the-art upper bound achieves at best Ope2|β|H q (Mortensen and Talebi, 2025) 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. Keywords: Entropic risk measure, Risk-sensitive reinforcement learning, Best policy identification

1. Introduction Risk-sensitive Reinforcement Learning (RL) studies the problem of learning a policy whose return distribution, rather than only its expectation, satisfies desirable properties, typically with respect to downside risk or tail events. In many applications ranging from finance to robotics (Charpentier et al., 2023; Polydoros and Nalpantidis, 2017), it may be more important for a decision maker to certify with high confidence that the return does not fall below a critical threshold than to maximize the expected reward. A prominent example of a dynamically consistent risk criterion is the Entropic Risk Measure (Marthe et al., 2023; Howard and Matheson, 1972), which generalizes the expectation through an exponential utility function parameterized by a scalar β P R. The sign and magnitude of β control the risk sensitivity of the decision maker, interpolating between risk-seeking and risk-averse behaviors. Crucially, the entropic risk measure satisfies a risk-sensitive dynamic programming principle, yielding a Bellman-type recursion for finite-horizon Markov Decision Processes (MDPs) (Sutton and Barto, 2018). As shown by Marthe et al. (2023), this property in fact characterizes the entropic family among utility-based risk measures satisfying dynamic consistency. In RL, the MDP is unknown and the learner must rely on sampled trajectories to estimate the model and plan under uncertainty. Mortensen and Talebi (2025) study this problem in a discounted infinite horizon setting and show that the sample complexity of identifying an ϵ-optimal policy must © 2026 A. Essakine & C. Vernade.

Essakine Vernade

depend exponentially on the horizon. More precisely, for a horizon H and entropic parameter β, they prove a lower bound showing that any algorithm requires at least Ωpexpp|β|Hqq samples (up to polynomial factors in the number of states S, actions A, and 1{ϵ) to identify an ϵ-optimal policy. In the same work, the authors derive an upper bound in expp2|β|Hq using access to a generative model and a careful application of the simulation lemma (see Section 2 for precise statements). While this gap may look benign at first, we show that this constant term in the exponential is due to a fundamentally loose handling of exponential utilities in exploration bonuses. Beyond simply closing this open gap, we provide a new set of tools to design algorithms for risk-sensitive RL. Our algorithm builds on the forward-model framework (Menard et al., 2021) and tailors the exploration bonuses and stopping-time to the entropic risk measure. We also revisit previous analyses and extract a problem-dependent quantity, the maximal achievable reward Gmax , that gives a sharper dependence of the bounds on the MDP than directly using its upper bound H. The main contributions of the paper are the following: • First, we derive a lower bound for the best policy identification problem for the forward model. To the best of our knowledge, this is the first lower bound for BPI in this setting. The lower bound is expressed in terms of the maximal achievable reward Gmax that we argue is better suited for the entropic risk measure. • We present Entropic-BPI, an algorithm that outputs a policy π that achieves pε, δq-PAC with optimal sample complexity up to logarithmic factors and up to e2 maxt0,βu which is a constant for ε small enough. The exponential dependence is e|β|Gmax pMq ď e|β|H which removes the extra exponential factor with respect to previous work.

2. Risk-Sensitive Episodic Reinforcement Learning ˘ ` H We consider a finite-horizon MDP M “ S, A, H, trh uH h“1 , tph uh“1 where S and A denote the finite state and action spaces respectively, H P N is the fixed horizon length, ph p¨ | s, aq is the transition kernel at step h for each h P t1, . . . , Hu, and rh : S ˆ A Ñ r0, 1s is the deterministic reward function at step h, which we assume to be bounded in r0, 1s. In the learning problem, the transition kernels tph uH h“1 are unknown to the learner. Through interactions, the learner must devise a policy π that is a (possibly non-stationary) mapping prescribing which action to take in each state and step, with the goal of maximizing a suitable performance criterion. In the literature, this problem is addressed under two distinct interaction models. • Generative model (Azar et al., 2012; Kearns et al., 2002): In the generative model (also called a sample oracle), the learner has access to an oracle such that for any query ps, a, hq P SˆAˆt1, . . . , Hu, the oracle returns a sample pr, s1 q where r “ rh ps, aq and s1 „ ph p¨ | s, aq. Each call to the oracle is independent of the past, and the learner may choose its queries adaptively based on all previously observed samples. • Online (forward) model (Dann and Brunskill, 2015; Strehl et al., 2009): In the forward interaction model, the learner interacts with the MDP over episodes. At the beginning of each episode t, an initial state st1 is drawn from a fixed initial distribution µ1 on S. At each step 2

Entropic Best Policy Identification

h P t1, . . . , Hu of episode t, the learner observes the current state sth , selects an action ath P A according to some policy πt , then receives a reward rh psth , ath q and the environment goes to the next state sth`1 „ ph p¨ | sth , ath q. In this work, we focus exclusively on the online (forward) interaction model. Moreover, rather than the standard risk-neutral objective where we optimize the total expected reward along the trajectory, we adopt a risk-sensitive performance criterion based on the entropic risk measure which reflects the agent’s attitude toward uncertainty, allowing for both risk-seeking and risk-averse behavior. Policy & value functions A deterministic policy π is a collection of functions πh : S Ñ A for all h P t1, ..., Hu, where every πh maps each state to a single action. Let pSh , Ah qH h“1 be the random trajectory induced by the policy pπh qhPt1,...,Hu and the MDP dynamics, i.e., Ah “ πh pSh q and Sh`1 „ ph p¨ | Sh , Ah q starting from a fixed initial state s1 1 . Define the (random) cumulative return from step h by: H ÿ Rhπ “ ri pSi , Ai q i“h The entropic value function of π, denoted by Vhπ is defined as:

1 Vhπ psq fi log E β

H ÿ

exp β

¸ ri psi , ai q

ff | Sh “ s

i“h

where ai fi πi psi q and si`1 „ pi p¨ | si , ai q The optimal entropic value functions are defined as Vh‹ psq fi supπ Vhπ psq for h P rHs. As for the expected return, both Vhπ and Vh‹ satisfy the Bellman equation (Borkar and Meyn, 2000; Sutton and Barto, 2018; Marthe et al., 2023) and can thus be computed efficiently. To simplify notation, we introduce a couple of operators that allow us to write concisely the effect of transition kernels or policies on our functionals of interest. For any bounded function f : S Ñ R, we denote by pph f qps, aq fi ES 1 „ph p¨|s,aq rf pS 1 qs the action of the Markov kernel ph on f . For any function g : S ˆ A Ñ R and (possibly stochastic) policy πh , we write pπh gqpsq fi EA„πh p¨|sq rgps, Aqs for the composition with the policy at step h. Finally, we introduce a useful quantity that appears naturally in the analysis of the sample complexity. Definition 1 (Maximum achievable reward in a trajectory) For an episodic MDP M, define the maximal achievable return (a deterministic quantity depending only on M) as Gmax pMq “ sup sup R1π pωq π

where ω covers all sources of randomness (initial state, transitions, policy’s own randomization). Intuitively, Gmax pMq is the largest total reward that can occur in a single episode under the most favorable sequence of outcomes. We will express both the lower bound and the upper bound in the quantity Gmax pMq rather than the horizon in previous works. It is the natural scale for the entropic risk measure objective where the hardness comes from the exponential amplification of rewards. Remark that we have the inequality Gmax pMq ď H so our results can also be expressed (more loosely) as a function of the horizon. 1. As explained in (Fiechter, 1994), if the first state is sampled randomly as s1 „ p0 , we simply add an artificial first state s0 such that for any action a, the transition probability is defined as the distribution p0 ps0 , aq fi p0 . This augments the state space by one and the horizon by one, and the bounds carry over with only this constant-size modification.

Essakine Vernade

Empirical MDP. Let psth , ath , sth`1 q P S ˆ A ˆ S be a tuple observed by the algorithm at step h of episode t. For any h P t1, ..., Hu and ps, aq P S ˆ A, define the visitation counts nth ps, aq fi

t ÿ

1tpsih , aih q “ ps, aqu

nth ps, a, s1 q fi

t ÿ

1tpsih , aih , sih`1 q “ ps, a, s1 qu

i“1

These quantities induce the empirical transition probabilities $ t 1 ’ ’ nh ps, a, s q if nt ps, aq ą 0, & h t nh ps, aq ppht ps1 |s, aq fi 1 ’ ’ otherwise % |S| We denote nth ps, aq “ Ernth ps, aqs the expected number of visits, which is called the pseudo-counts. Best Policy Identification (BPI) under entropic risk Our objective is to identify a (near) optimal policy with high probability. In each episode t, the agent follows a policy π t (the sample rule) based only on the information collected up to and including episode t ´ 1. At the end of each episode, the agent can decide to stop collecting data according to a stopping rule (we denote by τ its random stopping time) and outputs a guess π̂ for the optimal ` policy. ˘ A BPI algorithm is therefore made of a triple pπ t qtPN , τ, π̂ . The goal is to build an pε, δq-PAC algorithm according to the following definition, for which the sample complexity, that is the number of exploration episodes τ , is as small as possible. Definition 2 (PAC algorithm for BPI) An algorithm is pε, δq-PAC for best policy identification if it returns a policy π̂ after some number of episodes τ that satisfies ´ ¯ P V1‹ ps1 q ´ V1π̂ ps1 q ď ε ě 1 ´ δ Prior bounds. For the entropic risk measure, the best policy identification problem is harder2 because it magnifies tail outcomes—inflating high rewards when β ą 0 and penalizing low rewards when β ă 0. Moreover, as this line of work is relatively recent and most of the results aim to establish regret bounds, the results on PAC bounds remain scarce; to our knowledge, there are no reward-free algorithms (Jin et al., 2020; Kaufmann et al., 2021) with theoretical guarantees specifically tailored to this criterion. Sample complexity with the generative model. In the discounted infinite-horizon, Mortensen and Talebi (2025) proved a lower bound on the number of oracle calls needed for an ε´optimal policy. In particular, they showed that an exponential dependency on the risk parameter β and on the horizon H is unavoidable: that outputs¸an ε-optimal policy with probability at least 1´δ must ˜ Any algorithm 1 ´ ¯ 2 |β| 1´γ e S ´3 make at least Ω SAγ log calls to the oracle. They also provided two model2 2 c2 δ c1 ε |β| ´ ¯2 ˜ ¸ 1 2|β| 1´γ ´ ¯ e ´1 SAγ 2 SA log c2 δ based algorithms with respective sample complexity Õ c1 p1´γq4 ε2 |β|2 2. In the sense that it admits higher lower bounds, see Sec. 3

Entropic Best Policy Identification

This gives the first explicit sample complexity characterization for the entropic risk measure objective 1 with a generative model. It can be mapped back to our finite-horizon setting using H “ 1´γ , the effective horizon. Forward model: There are no known BPI sample-complexity bounds for the entropic risk measure in this model. However, there exist bounds on the regret, a more forgiving metric that sums V πt ´ V ˚ over episodes that can be connected back to BPI as we explain next. The first nonasymptotic results algorithms RSVI/RSQ (Fei et al., 2020), establishing ? are for˘model-free optimistic ? ` ` ˘ Õ λp|β|H 2 q H 3 S 2 AT (RSVI) and Õ λp|β|H 2 q H 4 SAT (RSQ) regret with λpuq “ pe3u ´ 1q{u. Fei et al. (2021) introduce the exponential Bellman equation and a doubly-decaying bonus, ´ |β|H ? ¯ 2 e ´1 |β|H 4 2 removing an extra e factor and yielding a regret of Õ |β|H H S AK . More recently, Hu and Leung (2023) adapt UCB-ADVANTAGE (Zhang et al., 2020) to the exponential-utility ´ |β|H ¯ ? e ´1 2 SAK along setting and derive a worst-case problem-independent regret bound Õ H |β| with a tighter problem-dependent bound that matches the information-theoretic lower bound up to logarithmic factors on a class of MDPs. These results are not directly related to our problem, though in general there is a connection between controlling regret and BPI sample complexity. As noticed by Jin et al. (2020), a straightforward approach to convert the regret bound to a sample complexity bound is to output a random policy among the sequence of policies returned by the regret algorithm. This idea was later shown to be outperformed (for the expected return) by Kaufmann et al. (2021), and the same applies in the case of entropic risk measures. It can be easily checked that a naive conversion of the best regret upper bounds above would yield a sample complexity in e2|β|H and a dependence in δ12 . This upper bound can thus be considered the best achievable sample complexity so far for this problem.

3. Lower bound Under the entropic risk criterion, the exponential transform eβr amplifies tail behavior, placing disproportionate weight on rare, high-return trajectories when β ą 0. Therefore, if achieving nearoptimal performance requires hitting a “hard” state–action–time triple ps‹ , a‹ , h‹ q that is reached with tiny probability, the learner must repeatedly experience these rare transitions to accurately evaluate their contribution since a small number of tail episodes can dominate the entropic objective. As a result, learning becomes exponentially hard in the horizon H and the risk parameter β. Theorem 3 Fix S ě 6, A ě 2, H P N, β P R‹ , and δ P p0, 1{16q and ε small enough (See condition (20)). There exists an MDP M0 with S states, A actions, horizon H, and rewards in r0, 1s and nonstationary transitions such that for every algorithm A outputs a policy π̂ that is pε, δq-PAC for the entropic risk measure after sampling τ trajectories we have: ˆ ˙ 1 pe|β|Gmax pM0 q ´ 1q2 e2 mintβ,0uε SAH 1 EM0 rτ s ě log |β|G pM q |β|ε 2 max 0 1650 δ e pe ´ 1q Proof [Sketch of proof] We follow the hard episodic, stage-dependent MDP class introduced by Domingues et al. (2021). At a high level, these instances behave like a single multi-armed bandit with ΘpHSAq arms, where an “arm” corresponds to a triple (time, leaf, action). The agent starts in a waiting state sw and can play a special action aw to remain in sw up to some stage H̄; once it stops waiting (or after H̄), it is forced to leave sw and then traverses a full A-ary tree deterministically (each 5

Essakine Vernade

action selects the corresponding child), reaching a leaf after d steps. From a leaf state si P L, at stage h and action a, the process transitions to an absorbing good state sg with probability ph psg |si , aq and to an absorbing bad state sb otherwise. Rewards are obtained only in sg for the rest of the horizon. Consequently, achieving the optimal value requires (i) leaving sw so as to hit the correct stage ‹ h at the leaves, (ii) reaching the correct leaf sℓ‹ (via the deterministic actions along the tree), and (iii) playing the correct action a‹ at that leaf; only then does the probability of reaching sg increase from p´ to p` . We denote u “ ph‹ , l‹ , a‹ q for the rest of the proof. The lower bound proof then compares a reference instance M0 (where no unique action is optimal) to instances Mu (where only one triplet has the favorable probability p` ), and applies standard change-of-measure arguments to show that distinguishing these close Bernoulli transition models forces a large number of episodes visiting the special triplet. The construction of p´ for the entropic risk measure differs from the risk-neutral setting (where p´ “ 12 q to reflect the hardness induced by the entropic risk measure: • For β ą 0, the entropic criterion overweights rare high-return trajectories, so we make success (reaching the good state) rare by choosing p´ „ e´βH • For β ă 0, the entropic criterion is especially sensitive to adverse tail events, so we instead make failure rare by choosing p´ „ 1 ´ e´|β|H Then, we chose the gap ∆ “ p` ´ p´ so that, in instance Mu , any policy that does not identify the special triplet is ε-suboptimal for the entropic objective. A change of measure argument (Kaufmann et al., 2016) then gives the lower bound. The full proof together with details on the MDP construction can be found in Appendix C To the best of our knowledge, this establishes the first lower bound for Best Policy Identification (BPI) in the forward model setting with non-stationary transitions. When |β| goes to 0, the lower bound approaches: ˆ ˆ ˆ ˙˙ ˆ ˙˙ Gmax pM0 q2 SAH 3 1 1 Ω “Ω SAH log log ε2 δ ε2 δ The second equality holds because, in the construction of M0 , the maximum return Gmax pM0 q scales linearly with H. Thus, we recover the standard lower bound for the risk-neutral case. Moreover, for sufficiently small ε, the bound simplifies to: ˆ ˙ SAH |β|Gmax pM0 q Ω e ε2 This matches the lower bound derived by (Mortensen and Talebi, 2025) in the generative model setting up to an additional factor of H. This extra factor is inherent to the non-stationary transition dynamics of the finite-horizon setting. Another difference is that the exponential dependence in 1 our bound scales with Gmax pM0 q rather than the horizon H (or the effective horizon 1´γ ). This distinction is intuitive: since the hardness of the entropic risk measure comes from exponentially reweighting trajectory returns, the exponential dependence is naturally governed by the maximum cumulative reward (Gmax ) rather than the length of the episode.

Entropic Best Policy Identification

4. Algorithm and Matching Upper Bound We now present an algorithm whose sample complexity matches the lower bound (Theorem 3) up to logarithmic factors. A central difficulty with the entropic risk measure is that, unlike the riskneutral objective, it is neither additive nor sub-additive, which complicates both algorithm design and analysis. In particular, standard UCB-style approaches rely on concentration inequalities for additive returns, whereas the entropic criterion involves a log-moment generating function and does not directly fit into standard risk-neutral concentration frameworks. A common workaround is to use the Lipschitz continuity of the logarithm to reduce the analysis to risk-neutral quantities; however, this can yield coarse bounds and, more importantly, may break the dynamic-programming structure. As observed by Fei et al. (2021), losing a Bellman-type recursion can cause error terms to compound over the horizon, leading to substantially worse dependence on H 2 in the order of e2βH . Similarly to Fei et al. (2021), we instead work directly in the exponential space induced by the criterion. This restores a Bellman recursion for the exponentiated value functions and enables sharper control of uncertainty. In particular, Lemma 23 derives Bellman-type variance identities in this space, which are unavailable in the original entropic-value space due to the lack of sub-linearity3 . This identity highlights that the exponential parameterization is the natural domain for controlling uncertainty under the entropic criterion. For a policy π, the exponential transforms of the value and the state-value function are: Zhπ psq fi exppβVhπ psqq,

Uhπ ps, aq fi exppβQπh ps, aqq.

We introduce two novel techniques. We adapt the KL-based exploration bonuses introduced in (Menard et al., 2021) to the entropic criterion to get bonuses that admit variance-sensitive control in the exponential space defined by these exponential transforms. We also propose an entropic stopping rule that yields sharper horizon dependence, improving over bounds that incur an additional factor of order H 2 e|β|H (Mortensen and Talebi, 2025). Similarly to Azar et al. (2017), Zanette and Brunskill (2019) and Menard et al. (2021) we define optimistic (and pessimistic, see (12)) state-value functions for β ą 0 on the exponential transform r t ps, aq “ 1 and recursively, Uh‹ of Q‹h (see (18) for β ă 0): fix U H`1 # « ff+ ´ ¯ 1 t t t t βpH´h´1q βr ps,aq t t t r ps, aq “ min e pph Zrh ps, aq ` bh ps, aq ` pph Zrh`1 ´ Zh`1 ps, aq , U ,e h h H r (1) t where Zrht and Zh`1 ps, aq denote respectively the optimistic and pessimistic exponential value r 4 functions : (see again (12) for pessimistic versions) t ZrH`1 psq “ 1,

r ps, aq, and recursively Zrht psq “ max U aPA

(2)

and the bonus term is defined as: d t ‹ t ? α‹ pnth ps, aqq βpH´hq αpnh ps, aqq βpH´hq α pnh ps, aqq t bth ps, aq “ 2 2 Varppt pZrh`1 q ` 5e ` 4He h nth ps, aq nth ps, aq nth ps, aq (3) 3. As shown by Rowland et al. (2019), the variance is a Bellman-closed statistic and can be computed by dynamic programming. We derive this result for the variance of exponential utilities 4. We use upper and lower tilde accents to indicate optimism and pessimism.

Essakine Vernade

with the exploration rates α, α˚ (see Eq. (10) for exact definitions) being of the form n, δ ÞÑ OplogpSAH{δq ` logpnqq and coming directly from the Bernstein inequality. As stated before, our algorithm acts greedily on this optimistic value function. Specifically, at step h in episode t, given state sh,t , Entropic-BPI executes r t psh,t , aq ah,t “ πt psh,t q “ arg max U h a

(4)

Entropic certificate Following related work, we call certificate an upper bound on the width of the confidence interval for a policy π. We define it by backward recursion: " ˆ ˆ ˙ ˙* t`1 3 t t`1 t t`1 t t`1 t`1 βpH´h´1q βrh ps,πh psqq t πh`1 Gh psq “ min e ,e 3bh ps, πh psqq` 1` pp pπ G qps, πh psqq H h h`1 h`1 (5) with terminal GtH`1 ” 0. In particular, on the high-probability good event, the performance gap of the greedy policy πt`1 is controlled by the start-state certificate. Concretely, lemma 11 shows that with high probability 1 ´ δ: π π Z1‹ ps1 q ´ Z1 t`1 ps1 q ď Zr1 ps1 q ´ Z1 t`1 ps1 q ď πt`1,1 Gt1 ps1 q

(6)

Stopping rule We derive a stopping criterion based on the certificate Gth by relating the value function gap to the ratio of partition functions. The difference in value functions can be expressed in the exponential space as: ˆ ‹ ˙ 1 Z1 ‹ π t`1 pV1 ´ V1 qps1 q “ log ps1 q t`1 β Z1π ¸ ˜ t`1 1 Z1‹ ´ Z1π ps1 q. “ log 1 ` t`1 β Z1π To ensure the policy is ε-optimal, it suffices to satisfy at stopping time τ : ´ ¯ t π1t G1 ps1 q ď eβε ´ 1 Z1π ps1 q

(7)

However, Z1π is unknown as it relies on the true dynamics. We therefore substitute it with a computable lower bound. Using (6), we have: π Z1 t`1 ps1 q ě Zr1t ps1 q ´ πt`1,1 Gt1 ps1 q.

Substituting this lower bound into the optimality condition (7) yields a stronger, computable stopping rule: ´ ¯´ ¯ π1t G1 ps1 q ď eβε ´ 1 Zr1t ps1 q ´ π1t G1 ps1 q . Solving for π1t G1 ps1 q, we obtain the final stopping criterion: π1t G1 ps1 q ď

eβε ´ 1 rt Z1 ps1 q eβε

where both π1t G1 ps1 q and Zr1t ps1 q can be computed efficiently by dynamic programming. 8

(8)

Entropic Best Policy Identification

πt

Insight on the stopping rule To guarantee ε-optimality, we need π1 G1 ps1 q{Z1 1 ps1 q to be smaller than a threshold eβε ´ 1. Our analysis reveals that (see proof below) ˛ ¨g ¯ « ´ f ˇ ff f Var eβR1π ˇˇS “ s H ˇ ÿ 1 1 ‹ ˚f 1 πt ˇ π f ” E (9) π1 G1 ps1 q{Z1 1 ps1 q À O ˚ ˇs1 ‹ ı2 t ˇ ‚ ˝e π nh ps, aq ˇ βR ˇ 1 h“1 S1 “ s1 E e ´

Var eβR1 ˇS1 “s1

The bound consists of a decreasing visitation term and the constant

”

ı2 , which governs

E eβR1 ˇS1 “s1

ˇ the asymptotic rate in contrast to VarpRπ1 ˇS1 “ s1 q in the risk-neutral setting. It is insightful to make a short comment on the connection of this quantity with the probability space we are working with. Let us denote Pπ the probability distribution of a random trajectory ps1 , a1 , ..., sH , aH q in the MDP, and consider the tilted law Pπβ defined by the Radon-Nykodim π pωq dPπβ βR1 derivative π pωq “ eZ π ps . We can see the tilted measure as the law of a trajectory on a twisted 1q 1 P version of the original MDP that biases transitions towards states with high future exponential return. It can be easily computed that: ¯ ´ πˇ Var eβR1 ˇS1 “ s1 π 2 π ” ı2 “ χ pPβ , P q ˇ π E eβR1 ˇS1 “ s1 In other words, the constant leading the convergence speed in the upper bound (9) is the χ2 divergence mismatch between the tilted trajectory distribution and the nominal trajectory distribution: It measures the extent to which optimizing the entropic objective amounts to learning under an implicit twisted dynamics that over-samples trajectories with high exponentiated reward. This mismatch is precisely what gets introduced by maximizing the entropic risk measure and what βH drives the extra constant eβ 2 introduced in the sample complexity in contrast to the risk-neutral setting. Finally, notice that for β « 0, the χ2 -divergence admits the expansion χ2 pPπβ , Pπ q “ ` ˇ ˘ β 2 VarPπ R1π ˇS1 “ s1 ` Opβ 3 q, which reduces the term in Eq.(9) to the variance term that governs the risk-neutral case. Algorithm and sample complexity upper bounds. We summarize the elements described above into an algorithm we call Entropic-BPI (Algorithm 1). Using the optimistic proxies in Eq. (12) for β ą 0 and in Eq. (18) for β ă 0, it builds exploratory trajectories until our stopping criterion (Eq.8 for β ą 0 and Eq.(8) for β ă 0) is reached. We prove a sample complexity bound for Entropic-BPI in the following theorem. This complexity bound is valid for both β ą 0 (proof in Appendix B.1) and for β ă 0 (proof in Appendix B.2) Theorem 4 (sample complexity) For any δ P r0, 1s and ε ą 0 small enough and for any finite MDP M, Entropic-BPI (Algorithm 1) outputs a policy that is pε, δq-PAC for best policy identification problem for the entropic risk measure after τ episodes. Moreover, with probability 1 ´ δ: ˜ ¸ pe|β|Gmax pMq ´ 1q2 3SAH e2|β|ε τ “O ` SAH logp q ˘2 δ e|β|Gmax pMq e|β|ε ´ 1 9

Essakine Vernade

Algorithm 1 Entropic-BPI 1: Input: β ‰ 0, δ P p0, 1q, ε ą 0. 2: Initialize counts n0h p¨q “ 0 and p p0h p¨|s, aq “ 1{S. 3: for t “ 0, 1, 2, . . . do 4: 5: 6: 7: 8:

t t Terminal init: set ZrH`1 psq “ 1, ZH`1 psq “ 1, and GtH`1 psq “ 0 for all s. r for h “ H, H ´ 1, . . . , 1 do t Compute the bonus bh p¨q: use (11) if β ą 0, and (17) if β ă 0 Backup: for all ps, aq compute the optimistic and pessimistic quantities: use (12) if β ą 0, and (18) if β ă 0. Greedy action: for all s set # r t ps, aq, β ą 0, arg maxaPA U h πht`1 psq P r t ps, aq, β ă 0, arg minaPA U h

Certificate: Compute πht`1 Gth : use (13) if β ą 0, and (19) if β ă 0. 10: end for 11: Stopping test: βε 12: if β ą 0 and pπ1t`1 Gt1 qps1 q ď pe eβε´1q Zr1t ps1 q then 13: stop and output π t`1 . 14: end if 15: if β ă 0 and pπ1t`1 Gt1 qps1 q ď p1 ´ eβε q Z1t ps1 q then r 16: stop and output π t`1 . 17: end if 18: Execute episode t ` 1 with π t`1 , update counts and ppt`1 h . 19: end for 9:

The algorithm upper bound matches the lower bound derived in Theorem 3 up to a factor e2|β|ε which is a constant when ε is small enough and comes from having a stopping rule using comptable proxies instead of Zhπ . When |β| goes to 0, the upper bound approaches : ˆ ˙ ˆ ˙ Gmax pMq2 SAH SAH 3 Õ “ Õ ε2 ε2 and we recover the optimal sample complexity for the risk-neutral setting (Menard et al., 2021). Also remark that using the elementary inequality logp1 ` xq ě x2 for |β|ε P r0, 1s and using5 |β|Gmax pMq

´1q that pe e|β|Gmax pMq ď e|β|Gmax pMq ´ 1 ď e|β|H ´ 1 we have an upper bound of the order of : ˜ ¸ e|β|H ´ 1 SAH τ “ Õ β2 ε2

This matches the lower bound of Mortensen and Talebi (2025) when mapped to the finite-horizon setting, up to an additional factor H which is unavoidable as it is inherent to the non-stationary finitehorizon setting (with H separate kernels). Note that the upper bound is stated in terms of Gmax pMq rather than H. Since rewards lie in r0, 1s, Gmax pMq can be interpreted as an effective reward horizon, i.e., the maximal cumulative 5. since the rewards are in r0, 1s

Entropic Best Policy Identification

reward that can be accrued along a trajectory. This choice is natural for the entropic risk criterion, whose difficulty comes from the exponential amplification of accumulated rewards; using H may overestimate this effect in problems where rewards are sparse or concentrated near the end of the episode. Finally, our algorithm does not require prior knowledge of Gmax pMq. Experiments. To illustrate the gains in sample complexity, we propose a simple 8-state MDP and compare Entropic-BPI with regret algorithms in the literature. The results are discussed in Appendix D

5. Proof of Theorem 4 We present the main ideas of the proof for β ą 0. The full proof is given in Section B. We first control the concentration events (Lemma 5) and work on the good event E ` for β ą 0, which holds with probability at least 1 ´ δ. As explained in paragraph Stopping rule, when the algorithm stops, it outputs by design a policy π τ that is ε-optimal with high probability 1 ´ δ, this proves the first statement of Theorem 4. r t and U t are indeed optimistic and To upper bound the stopping time, we first show that U h h r pessimistic, respectively, for the exponential transform of the value functions Uh‹ (Lemma 8). Then, following a similar approach to (Menard et al., 2021; Dann et al., 2017), we bound the width certificate by a computable recursive upper bound, which serves as the stopping rule for our algorithm (6). Lemma 11 shows that, with probability at least 1 ´ δ, this width certificate upper bounds the optimality gap. Since the stopping condition is not met for episodes t “ t1, . . . , τ u, we have: τ

τ ÿ eεβ ´ 1 π1 Gt1 ps1 q ď rt eεβ t“1 Z1 ps1 q

We bound the right-hand side for episode t by replacing the empirical transition probabilities t with the true ones. We then unroll the resulting recursive inequality for πh`1 Gth under the true dynamics (see B.1.3 for details): « ˜ d ` πt`1 ˘ H h ´ ÿ ¯ ÿ ˘ ` Var Zh`1 pπ1 Gt1 qps1 q t`1 p h α‹ nth psh , ah q ^ 1 ď e13 Eπ exp β ri psi , ai q 36 t`1 2 π t pZ1 q Zr1 ps1 q i“1 h“1 ¸ˇ ff ` ˘ ˇˇ ` 81HeβpH´hq α nth psh , ah q ^ 1 ˇs1 ˇ We bound the first term using Cauchy-Schwartz inequality: » ˇ fi ˜d ` πt`1 ˘ ` t H h ˇ ´ ¯ ¯ ‹ ÿ ÿ ` ˘ Var Z α nh ps, aq ph ˇ h`1 π t`1 – E exp β ri psi , ai q ^ 1 ˇs1 fl t`1 2 t ps, aq π ˇ n pZ1 q h i“1 h“1 g d f h ´ ÿ ¯ Varp `Z πt`1 ˘ ı ” α‹ pnt ps, aqq ı f t`1 ” h h`1 h π t`1 ď eEπ exp 2β ri psi , ai q E t`1 t ps, aq π 2 n pZ q h 1 i“1

Essakine Vernade

Using lemma 23 and lemma 24 we bound the first term on the right-hand side as: ¯ ˇ ` βRπt`1 « ` πt`1 ˘ ff ` βG pMq ˘2 ˇS1 “ s1 H h 1 ¯ ´ Var e pS q ÿ ÿ 1 Var Z e max ´1 ph h`1 π t`1 “´ ” ri psi , ai q E exp 2β ı¯2 ď t`1 ˇ π t`1 eβGmax pMq pZ1π q2 i“1 h“1 E eβR1 pS1 q ˇS1 “ s1 For the second term, we bound it loosely by directly upper bounding the per-step reward by 1: « ¸ˇ ff ` t H h ˇ ¯ ´ ÿ ” α`nt ps, aq ı ÿ ` ˘ α n ps, aq t`1 ˇ h h βH ri psi , ai q HeβpH´hq Eπ exp β ^ 1 s ď He E ^ 1 ˇ 1 ˇ nth ps, aq nth ps, aq i“1 h“1 We sum over all episodes t “ 1, ..., τ . Then using a standard counting argument we have: H τÿ ´1 ÿ

π t`1

E t“1 h“1

” α‹ `nt ps, aq h

nth ps, aq

ı ^ 1 ď 3SAHα‹ pτ ´ 1, δq logpτ ` 1q

And we have a similar bound for α, Hence: d peβGmax pMq ´ 1q2 eβε ´ 1 τ SAHα‹ pτ ´ 1, δq logpτ ` 1q τ ď 36e13 βε e eβGmax pMq ` 84e13 eβH SAHαpt ´ 1, δq logpt ` 1q Solving this inequality using lemma 29, we find the exact upper bound on τ with probability 1 ´ δ.

6. Discussions and Conclusions We provide a new approach to entropic best arm identification that resolves a known suboptimality gap. Our approach builds a successful optimism-driven framework for the forward model, relying on a tight control of the variance of the estimators of the entropic value function, and on a specifically tailored stopping rule. Indeed, the dependence of the sample complexity on the horizon remains exponential, indicating one more time that learning exponential utilities in MDPs is a significantly harder problem than the standard expected return due to the focus on tail (rare) events. However, we show that the real MDPdependent term of interest in the exponential is the maximal return, which could be constant in some sparse reward problems, making the problem more amenable. Such problem-specific investigations could be an avenue for future work. Recently, Marthe et al. (2025) showed that there is a fundamental connection between the entropic risk measure and more practically-used metrics such as the (conditional) Value at Risk. Our forward-model approach could be combined with such optimization improvements to propose new algorithms for (C)VaR optimization in RL.

Acknowledgments C. Vernade is funded by the Deutsche Forschungsgemeinschaft (DFG) under both the project 468806714 of the Emmy Noether Programme and under Germany’s Excellence Strategy – EXC number 2064/1 – Project number 390727645. CV also gratefully acknowledges funding from the 12

Entropic Best Policy Identification

European Union (ERC, ConSequentIAL, 101165883). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them). CV also thanks the international Max Planck Research School for Intelligent Systems (IMPRS-IS).

References Mohammad Gheshlaghi Azar, Remi Munos, and Bert Kappen. On the sample complexity of reinforcement learning with a generative model. In Proceedings of the 29th International Conference on Machine Learning (ICML-12), ICML ’12, pages 1263–1270, New York, NY, USA, July 2012. Omnipress. ISBN 978-1-4503-1285-1. Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 263–272. PMLR, 06–11 Aug 2017. URL https://proceedings.mlr.press/v70/azar17a.html. V. S. Borkar and S. P. Meyn. The o.d.e. method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization, 38(2):447–469, 2000. URL https://doi.org/10.1137/S0363012997331639. Arthur Charpentier, Romuald Élie, and Carl Remlinger. Reinforcement learning in economics and finance. Computational Economics, 62(1):425–462, 2023. doi: https://doi.org/10.1007/ s10614-021-10119-4. Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. Wiley-Interscience, 2 edition, 2006. ISBN 9780471241959. URL https://doi.org/10.1002/047174882X. Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed-horizon reinforcement learning. In Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015. URL https://proceedings.neurips.cc/paper_files/ paper/2015/file/309fee4e541e51de2e41f21bebb342aa-Paper.pdf. Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. In I. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL https://proceedings.neurips.cc/paper_files/paper/2017/ file/17d8da815fa21c57af9829fb0a869602-Paper.pdf. Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory, volume 132 of Proceedings of Machine Learning Research, pages 578–598. PMLR, 16–19 Mar 2021. URL https://proceedings.mlr.press/v132/domingues21a.html.

Essakine Vernade

Yingjie Fei, Zhuoran Yang, Yudong Chen, Zhaoran Wang, and Qiaomin Xie. Risk-sensitive reinforcement learning: Near-optimal risk-sample tradeoff in regret. In Advances in Neural Information Processing Systems, volume 33, pages 22384–22395. Curran Associates, Inc., 2020. URL https://proceedings.neurips.cc/paper_files/paper/2020/ file/fdc42b6b0ee16a2f866281508ef56730-Paper.pdf. Yingjie Fei, Zhuoran Yang, Yudong Chen, and Zhaoran Wang. Exponential bellman equation and improved regret bounds for risk-sensitive reinforcement learning. In Advances in Neural Information Processing Systems, volume 34, pages 20436–20446. Curran Associates, Inc., 2021. URL https://proceedings.neurips.cc/paper_files/paper/2021/ file/ab6439fa2daf0246f92eea433bca5ac4-Paper.pdf. Claude-Nicolas Fiechter. Efficient reinforcement learning. In Proceedings of the Seventh Annual Conference on Computational Learning Theory, COLT ’94, page 88–97, New York, NY, USA, 1994. Association for Computing Machinery. ISBN 0897916557. URL https://doi.org/ 10.1145/180139.181019. Ronald A. Howard and James E. Matheson. Risk-sensitive markov decision processes. Management Science, 18(7):356–369, 1972. doi: https://doi.org/10.1287/mnsc.18.7.356. Xiaoyan Hu and Ho-Fung Leung. A tighter problem-dependent regret bound for risk-sensitive reinforcement learning. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 5411–5437. PMLR, 25–27 Apr 2023. URL https://proceedings.mlr.press/v206/ hu23b.html. Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 4870–4879. PMLR, 13–18 Jul 2020. URL https://proceedings.mlr.press/v119/jin20d.html. Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best-arm identification in multi-armed bandit models. Journal of Machine Learning Research, 17(1):1–42, 2016. URL http://jmlr.org/papers/v17/kaufman16a.html. Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. In Proceedings of the 32nd International Conference on Algorithmic Learning Theory (ALT), volume 132 of Proceedings of Machine Learning Research, pages 865–891. PMLR, 2021. URL https://proceedings.mlr. press/v132/kaufmann21a.html. Michael Kearns, Yishay Mansour, and Andrew Y. Ng. A sparse sampling algorithm for nearoptimal planning in large markov decision processes. Machine Learning, 49:193–208, 2002. URL https://doi.org/10.1023/A:1017932429737. Hao Liang and Zhi-Quan Luo. Bridging distributional and risk-sensitive reinforcement learning with provable regret bounds. Journal of Machine Learning Research, 25(221):1–56, 2024. URL http://jmlr.org/papers/v25/22-1253.html.

Entropic Best Policy Identification

Alexandre Marthe, Aurélien Garivier, and Claire Vernade. Beyond average return in markov decision processes. In Advances in Neural Information Processing Systems, volume 36, pages 56488–56507. Curran Associates, Inc., 2023. URL https://proceedings.neurips.cc/paper_files/paper/2023/file/ b0a34e3c64f7e842f20ec10479c32b35-Paper-Conference.pdf. Alexandre Marthe, Samuel Bounan, Aurélien Garivier, and Claire Vernade. Efficient risk-sensitive planning via entropic risk measures. arXiv preprint, 2025. doi: 10.48550/arXiv.2502.20423. URL https://arxiv.org/abs/2502.20423. Pierre Menard, Omar Darwiche Domingues, Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration in reinforcement learning. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 7599–7608. PMLR, 18–24 Jul 2021. URL https://proceedings.mlr.press/v139/menard21a.html. Oliver Mortensen and Mohammad Sadegh Talebi. Entropic risk optimization in discounted mdps: Sample complexity bounds with a generative model. arXiv preprint arXiv:2506.00286, 2025. URL https://arxiv.org/abs/2506.00286. Athanasios S. Polydoros and Lazaros Nalpantidis. Survey of model-based reinforcement learning: Applications on robotics. Journal of Intelligent & Robotic Systems, 86(2):153–173, 2017. doi: https://doi.org/10.1007/s10846-017-0468-y. Mark Rowland, Robert Dadashi, Saurabh Kumar, Remi Munos, Marc G. Bellemare, and Will Dabney. Statistics and samples in distributional reinforcement learning. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 5528–5536. PMLR, 09–15 Jun 2019. URL https://proceedings.mlr. press/v97/rowland19a.html. Alexander L. Strehl, Lihong Li, and Michael L. Littman. Reinforcement learning in finite mdps: Pac analysis. Journal of Machine Learning Research, 10(84):2413–2444, 2009. URL http: //jmlr.org/papers/v10/strehl09a.html. Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, second edition, 2018. Mohammad Sadegh Talebi and Odalric-Ambrym Maillard. Variance-aware regret bounds for undiscounted reinforcement learning in mdps. In Proceedings of Algorithmic Learning Theory, volume 83 of Proceedings of Machine Learning Research, pages 770–805. PMLR, 07–09 Apr 2018. URL https://proceedings.mlr.press/v83/talebi18a.html. Andrea Zanette and Emma Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 7304–7312. PMLR, 09–15 Jun 2019. URL https://proceedings.mlr. press/v97/zanette19a.html.

Essakine Vernade

Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost optimal model-free reinforcement learningvia reference-advantage decomposition. In Advances in Neural Information Processing Systems, volume 33, pages 15198–15207. Curran Associates, Inc., 2020. URL https://proceedings.neurips.cc/paper_files/paper/2020/ file/ad71c82b22f4f65b9398f76d8be4c615-Paper.pdf.

Entropic Best Policy Identification

Appendix Contents of Appendix A Concentration events

B Algorithm analysis B.1 Case β ą 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.1.1 Confidence bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.1.2 Stopping rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.1.3 Sample complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.2 Case β ă 0 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.2.1 Stopping rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.2.2 Confidence Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.2.3 Stopping rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.2.4 sample complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

19 21 21 23 26 32 32 32 35 38

C Lower bound

D Experiments D.1 Sample complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . D.2 Regret bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48 49 49

E Concentration inequalities E.1 Sanov’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . E.2 Concentration inequality for Bernoulli random variables . . . . . . . . . . . . . . E.3 Self-normalized Bernstein inequality . . . . . . . . . . . . . . . . . . . . . . . . . E.4 KL-Bernstein inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

50 50 52 52 52

F Technical results

Essakine Vernade

Appendix A. Concentration events Following the ideas of (Menard et al., 2021) we define the following quantities: αpn, δq “ logp3SAH{δq ` S logp8epn ` 1qq αcnt pδq “ logp3SAH{δq

and

‹

α pn, δq “ logp3SAH{δq ` logp8epn ` 1qq

(10)

We also define the KL-divergence concentration event as: ␣ ( EKL “ @t P N, @h P t1, ..., Hu, @ps, aq P S ˆ A : DKL pp pth ps, aq, ph ps, aqq ď αpnth ps, aq, δq and the Bernoulli concentration event for a series of function pfh qhPrH`1s in r0, bs: # Ef “

@t P N, @h P t1, ..., Hu, @ps, aq P S ˆ A : d

ˇ ˇ t ˇpp ph ´ ph qfh`1 ps, aqˇ ă

α‹ pnth ps, aq, δq α‹ pnth ps, aq, δq ` 3b 2 Varph pfh`1 qps, aq nth ps, aq nth ps, aq

And the counts concentration event: " * 1 E cnt “ @t P N, @h P t1, ..., Hu, @ps, aq P S ˆ A : nth ps, aq ě n̄th ps, aq ´ αcnt pδq 2 Using this, we define the good event for our algorithm analysis for β ą 0 and β ă 0: for β ą 0 E ` “ EKL X EV ˚ X E cnt And for β ă 0 we have almost the same thing but the definition of V̊ and the range of the functions changes: E ´ “ EKL X EV ˚ X E cnt Lemma 5 It holds that : δ PpEKL q ě 1 ´ , 3

δ PpE cnt q ě 1 ´ , 3

and

for any f

PpEf q ě 1 ´

δ 3

Consequently, PpE ` q ě 1 ´ δ

and

PpE ´ q ě 1 ´ δ

Proof The KL concentration event: δ and then do a union For ph, s, aq fixed, we apply lemma E.1 with confidence level δh,s,a “ 3SAH bound over h, s, a to get a concentration inequality that holds uniformly. The Bernstein concentration event: Let pfh qhPrH`1s be a sequence of function. Fix ph, s, aq and let pFτ qτ ě0 be the history filtration. Define wτ “ 1tpHτ , Sτ , Aτ q “ ph, s, aqu,

Yτ “ fh`1 pSτ `1 q ´ Erfh`1 pSτ `1 q | Fτ ´1 s 18

Entropic Best Policy Identification

Then pwτ q is predictable, ErYτ | Fτ ´1 s “ 0, |Yτ | ď H, and ErYτ2 | Fτ ´1 s “ Varph pfh`1 qps, aq Let St “

t ÿ

wτ Yτ ,

Vt “

τ “1

t ÿ

wτ2 ErYτ2 | Fτ ´1 s,

on twτ “ 1u

Wt “

τ “1

t ÿ

wτ “ nth ps, aq

τ “1

Then Vt “ Wt Varph pfh`1 qps, aq and, for Wt ě 1, pp pth ´ ph qfh`1 ps, aq “

St Wt

Applying lemma 21 with b and confidence δh,s,a yields (simultaneously for all t) d ˇ ˇ α‹ pnth ps, aq, δq α‹ pnth ps, aq, δq ˇ ˇ t ph ´ ph qfh`1 ps, aqˇ ď 2 Varph pfh`1 qps, aq ` 3B ˇpp nth ps, aq nth ps, aq where α‹ pn, δq “ log

` 4ep2n`1q ˘ δh,s,a

(using nth ps, aq ď t and monotonicity of the log term). Finally

δ and we apply a union bound over ph, s, aq to get the result for any state-action choose δh,s,a “ SAH pair The counts concentration event: ( ␣ The proof follows from lemma 20 applied to the Bernoulli random variable 1 psih , aih q “ ps, aq δ for δh,s,a “ SAH and then doing a union bound over h, s, a

Appendix B. Algorithm analysis Here we provide a detailed analysis of our algorithm. Our method is a UCB-style algorithm that plans over a KL confidence region, following the approach of Menard et al. (2021) for the risk-neutral objective. At each step t and stage h, we construct a confidence set around the true transition kernel: * " ` t ˘ αpnth ps, aq, δq t Ch ps, aq fi q P ΣS : KL pph ps, aq, qps, aq ď nth ps, aq The algorithm then acts optimistically by selecting, among all transition models q such that qp.|s, aq P Cht ps, aq, the one that yields the highest value function, and plans accordingly. For the entropic risk measure, we follow the same principle, but carry out optimistic planning in the exponential (log-moment-generating) space induced by the entropic criterion. As noted by Fei et al. (2021), working in this exponential space allows us to exploit a Bellman-type recursion that is generally lost if one applies Lipschitz arguments directly in the original value space. This means that the upper and lower confidence bounds on the optimal exponential transformation of the

Essakine Vernade

state-value function U ˚ and value function Z ˚ for β ą 0 are given by: t

U h ps, aq fi eβrh ps,aq t

max

ph PCht ps,aq

U th ps, aq fi eβrh ps,aq

ph Z h`1 ps, aq

min

p Z th`1 qps, aq

ph PCht ps,aq h

Z th psq fi max U th ps, aq

Z h psq fi max U h ps, aq a

t Z H`1 psq fi 0

Z tH`1 psq fi 0 t

pth ps, aq P arg max ph Z h`1 ps, aq

pth ps, aq P arg min ph Z th`1 ps, aq

pPCht ps,aq

π th ps, aq P arg max U h ps, aq

π th ps, aq P arg max U th ps, aq.

aPA

For β ă 0, U will correspond to the pessimistic Q via the log-transformation. As such, maximizing Q to define the policy π is equivalent to minimizing U . Similarly, finding the best action at each stage to define Z and Z corresponds to minimizing U and U respectively: t

U h ps, aq fi eβrh ps,aq t

min

ph PCht ps,aq

U th ps, aq fi eβrh ps,aq

ph Z h`1 ps, aq

max

p Z th`1 ps, aq

ph PCht ps,aq h

Z th psq fi min U th ps, aq

Z h psq fi min U h ps, aq

t Z H`1 psq fi 0

Z tH`1 psq fi 0 t

pth ps, aq P arg min ph Z h`1 ps, aq

pth ps, aq P arg max ph Z th`1 ps, aq

pPCht ps,aq

π th ps, aq P arg max U th ps, aq.

π th ps, aq P arg min U h ps, aq

aPA

The KL confidence sets Cht ps, aq are introduced solely to motivate an optimistic model interpretation. We instead build computable optimistic and pessimistic expressions in the empirical MDP by choosing the radius α so that the true transition kernel belongs to Cht ps, aq in the same style as (Menard et al., 2021). We then prove the corresponding optimism lemma, bound the certificate width, and derive the sample complexity. We treat the cases β ą 0 and β ă 0 separately. We first restate the theorem in more detail 2 Theorem 4 (sample complexity) For any δ P r0, 1s and ε Ps0, |β|HS s and for any finite MDP M, Entropic-BPI (Algorithm 1) outputs a policy that is pε, δq-PAC for best policy identification problem for the entropic risk measure after τ episodes. Moreover, with probability 1 ´ δ:

˜ τ “ Õ

e2 maxt0,βuε pe|β|Gmax pMq ´ 1q2 SAH ` ˘2 e|β|Gmax pMq e|β|ε ´ 1

Entropic Best Policy Identification

B.1. Case β ą 0 . We start by building optimistic and pessimistic functions for the state-value function B.1.1. Confidence bounds Let us start with a concentration inequality: Lemma 7 On the good event E ` we have: d ? ` ˘ αpnt ps, aqq αpnt ps, aqq αpnt ps, aqq ‹ t | ph ´ ppth Zh`1 ps, aq| ď 2 2 Varppt pZrh`1 q th ` 5eβpH´hq t h ` 4HeβpH´hq t h h nh ps, aq nh ps, aq nh ps, aq ¯ ´ 1 t ‹ ps, aq ´ Zh`1 ` ppth Zrh`1 H Proof On the good event E ` we have: d ‹ t ` ˘ α‹ pnth ps, aqq ‹ βpH´hq α pnh ps, aqq ‹ q | ph ´ ppth Zh`1 ps, aq| ď 2 Varph pZh`1 ` 3e nth ps, aq nth ps, aq ‹ under ph to the We apply lemma 25 and lemma 26 successively to transport the variance of Zh`1 t t r computable variance of Zh`1 under pph ‹ ‹ qps, aq ` 4e2βpH´hq q ď 2 Varppt pZh`1 Varph pZh`1 h

αpnth ps, aqq nth ps, aq t

αpn ps, aqq ‹ t t qps, aq ` 4e2βpH´hq t h ´ Zh`1 qps, aq ` 4eβpH´hq ppth pZrh`1 ď 4 Varppt pZrh`1 h nh ps, aq ? ? ? ? Hence, using the inequality a ` b ď a ` b and then ab ď aη ` ηb for η “ H and using that α‹ pn, δq ď αpn, δq: d d d ‹ pnt ps, aqq ‹ pnt ps, aqq α α‹ pnth ps, aqq α h h tq t pZ t ‹ qps, aq ‹ q βpH´hq p r r t p ď 2 ` p Z Varph pZh`1 Var 4e ´ Z pph h h h`1 h`1 nth ps, aq nth ps, aq nth ps, aq d αpnth ps, aqq α‹ pnth ps, aqq ` 2eβpH´hq nth ps, aq nth ps, aq d ‹ t α‹ pnth ps, aqq βpH´hq α pnh ps, aqq ď 2 Varppt pZrht q ` 4He h nth ps, aq nth ps, aq `

αpnt ps, aqq 1 t rt ‹ pph pZh`1 ´ Zh`1 qps, aq ` 2eβpH´hq t h H nh ps, aq

Hence, by plugging this upper bound and using again that α‹ pn, δq ď αpn, δq we obtain: d t ‹ t ? ` ˘ ‹ α‹ pnth ps, aqq t βpH´hq αpnh ps, aqq βpH´hq α pnh ps, aqq t | ph ´ pph Zh`1 | ď 2 2 Varppt pZrh`1 q ` 5e ` 4He h nth ps, aq nth ps, aq nth ps, aq ´ ¯ 1 t ‹ ` ppth Zrh`1 ´ Zh`1 ps, aq H 21

Essakine Vernade

Denote the bonus term: d ? α‹ pnth ps, aqq αpnt ps, aqq α‹ pnth ps, aqq t t bh ps, aq “ 2 2 Varppt pZrh`1 q ` 5eβpH´hq t h ` 4HeβpH´hq t h nh ps, aq nh ps, aq nth ps, aq (11) Now, following Azar et al. (2017), Zanette and Brunskill (2019) and Menard et al. (2021) we define define optimistic and pessimistic state-value function on the exponential transform of Q‹h which denoted by Uh‹ : #

ff+ ´ ¯ 1 r t ps, aq “ min eβpH´h´1q , eβrh ps,aq ppt Zrt ps, aq ` bt ps, aq ` ppt Zrt ´ Z t U ps, aq h h h h H h h`1 r h`1 r t ps, aq, Zrht psq “ max U h aPA #

t ZrH`1 psq “ 1

ff+ ¯ ´ 1 t t Uht ps, aq “ max 1, eβrh ps,aq ppth Zht ps, aq ´ bth ps, aq ´ ppth Zrh`1 ps, aq ´ Zh`1 H r r r Zht psq “ max Uht ps, aq, aPA r r

t ZH`1 psq “ 1 r

(12)

And we consider the greedy policy: r t ps, aq πht`1 psq “ arg max U h aPA

Now let us prove the optimism lemma: Lemma 8 With high probability 1 ´ δ we have: r t ps, aq Uht ps, aq ď Uh‹ ps, aq ď U h r and

Zht psq ď Zh‹ psq ď Zrht psq r Proof We proceed by induction over h. For h “ H ` 1 the result is trivially upper bounding and (resp. lower bounding ) Uh‹ by eβpH´hq and 1. r t ps, aq ă H since otherwise the Assume the inequality holds for h1 ą h. Fix ps, aq and assume U h inequality is trivial, we have that: ff « ´ ¯ 1 t ‹ βr ps,aq t t t t t t ‹ r ps, aq ´ U ps, aq “ e h U pph Zrh`1 ps, aq ` bh ps, aq ` pph Zrh`1 ´ Zh`1 ps, aq ´ ph Zh`1 ps, aq h h H r « ´ ¯ ´ ¯ t ‹ ‹ “ eβrh ps,aq ppth Zrh`1 ps, aq ´ Zh`1 ps, aq ` ppth ´ ph Zh`1 ps, aq ff ´ ¯ 1 t t ´ Zh`1 ps, aq ` bth ps, aq ` ppth Zrh`1 H r 22

Entropic Best Policy Identification

But we know by Bernstein inequality that: ´

¯ ¯ 1 ´ t ‹ ps, aq ´ Zh`1 ppth ´ ph Zh‹ ps, aq ě ´bth ps, aq ´ ppth Zrh`1 H

Hence: ff « ´ ¯ ´ ¯ ´ ¯ 1 1 ‹ t ‹ r t ps, aq ´ U ‹ ps, aq ě eβrh ps,aq 1 ´ ps, aq ě 0 U ´ Zh`1 ppt Zrt ps, aq ´ Zh`1 ps, aq ` ppth Zh`1 h h H h h`1 H r Where we used the induction hypothesis. We prove the pessimistic property in the same way

B.1.2. Stopping rule We define the width certificate for the algorithm for the case β ą 0: + # ı ´ ¯ ” 3 t ppt π t`1 Gth`1 psq Gth ps, aq “ min eβpH´hq , eβrh ps,aq 3bth ps, aq ` 1 ` H h

(13)

Lemma 9 establishes the validity of this stopping rule by showing that, with high probability, it bounds the certificate width: Lemma 9 On the good event E ` , for all t and all h, Zh‹ psq ´ Zhπ

t`1

psq ď πht`1 Gth psq

In particular, at the initial state s1 , Z1‹ ps1 q ´ Z1π

t`1

@s P S

ps1 q ď π1t`1 Gt1 ps1 q

t ” 1, we We prove the lemma 9 in this section : We define the auxiliary variable Z̊ht . Setting Z̊H`1 recurse backward for h “ H . . . 1: ! ” ı) t t t t q ´ Z̊h`1 Ůh,pes “ max 1, eβrh ppth Z̊h`1 ´ bth ´ H1 ppth pZrh`1 ) ! t t q, Ůh,pes Ůht “ min eβrh pph Z̊h`1 ` ˘ Z̊ht psq “ Ůht s, πht`1 psq t`1

Because Z t is pessimistic against Z ‹ , we cannot directly compare Z t to Z π . Intuitively, Z̊ t r exponential Bellman recursion under the true kernel pr , while being clipped by a satisfies the h t`1 pessimistic empirical backup; hence it serves as a worst-case lower bound for both Z t and Z π as r shows the next lemma: Lemma 10 For all ph, s, aq: ´ ¯ π t`1 Ůht ps, aq ď min Uht ps, aq, Uh h ps, aq r and

´ ¯ π t`1 Z̊ht psq ď min Zht psq, Zh h ps, aq r 23

Essakine Vernade

Proof We proceed by backward induction. For h “ H `1, all values are equal to 1 so the inequalities hold. Assume that for some h ď H we have for all ps, aq: ´ ¯ π t`1 t t Ůh`1 ps, aq ď min Uh`1 ps, aq, Uh h`1 ps, aq r and

¯ ´ π t`1 t t Z̊h`1 psq ď min Zh`1 psq, Zh h`1 ps, aq r

we have by construction: t`1

π t`1

t t π Ůht ps, aq ď Ůh,true ps, aq “ eβrh ps,aq pph Z̊h`1 qps, aq ď eβrh ps,aq pph Zh`1 qps, aq “ Uh h`1 ps, aq

Where we used the induction hypothesis and the monotonicity of the exponential Bellman operator. Again by construction; t Ůht ps, aq ď Ůh,pes ps, aq But since we have: ”´ ¯ ¯ 1 ´ t t t ps, aq ´ bth ps, aq ´ ppth Zrh`1 ppth Zh`1 ´ Zh`1 ps, aq H r ¯ r ¯ı ´ 1 t t t t t rt ´ pph Z̊h`1 ps, aq ´ bh ps, aq ´ pph Zh`1 ´ Z̊h`1 ps, aq H ´ ˘ı 1 ¯” t ` t t βrh ps,aq “e 1´ pph Zh`1 ´ Z̊h`1 H r ě0

t ps, aq “ eβrh ps,aq Uht ps, aq ´ Ůh,pes r ´

Where we applied the induction hypothesis, we conclude then: Ůht ps, aq ď Uht ps, aq r The bound on V follows immediately and we conclude the recursion On the good event E ` we have: Lemma 11 On the good event E ` ¯ ´ ” ´ ¯ı r t ps, aq ´ Ů t ps, aq ď eβrht ps,aq 3bt ps, aq ` 1 ` 3 ppt Zrt ´ Z̊ t U h h h h`1 H h h`1 Proof Fix a state-action pair ps, aq and h P t1, ..., Hu, we consider two cases: t First case: Ůht ps, aq “ Ůh,true ps, aq we then have: ´ ” ¯ ı t rt t r t ps, aq´Ů t ps, aq ď eβrht ps,aq bt ps, aq` 1 ppt Zrt ´Z t U ps, aq`p p Z ps, aq´p Z̊ ps, aq h h`1 h h h h h`1 H h h`1 r h`1 The last term can be written as: ´ ¯ ` ˘ ‹ ` ˘` ‹ ˘ t t t t t ppth Zrh`1 ps, aq ´ ph Z̊h`1 ps, aq “ ppth Zrh`1 ´ Z̊h`1 ps, aq ` ppth ´ ph Zh`1 ` ph ´ ppth Zh`1 ´ Z̊h`1

Entropic Best Policy Identification

For the second term, by lemma 7: ¯ ¯ ` ˘ ‹ 1 ´ t 1 ´ t ‹ t ps, aq ď bth ps, aq ` ppth Zrh`1 ps, aq ´ Zh`1 ´ Z̊h`1 | ph ´ ppth Zh`1 ps, aq| ď bth ps, aq ` ppth Zrh`1 H H ? For the third term, by the KL-Bernstein inequality 22 and using the inequality ab ď Ha ` bH: d `

ph ´ ppth

˘`

‹ t Zh`1 ´ Z̊h`1

t ‹ q ´ Z̊h`1 2 Varppt pZh`1

αpnth ps, aqq 2 βpH´hq αpnth ps, aqq ` e nth ps, aq 3 nth ps, aq

d ď ď

t ‹ q ´ Z̊h`1 2eβpH´hq ppth pZh`1

αpnth ps, aqq 2 βpH´hq αpnth ps, aqq ` e nth ps, aq 3 nth ps, aq

αpnt ps, aqq 2 βpH´hq αpnth ps, aqq 1 t rt t pph pZh`1 ´ Z̊h`1 q ` 2HeβpH´hq t h ` e H nh ps, aq 3 nth ps, aq

Hence by combining the two bounds: ´ ¯ 2 ¯ t ´ rt t t t ppth Zrh`1 ps, aq ď 2bth ps, aq ` 1 ` ps, aq ´ ph Z̊h`1 pph Zh`1 ´ Z̊h`1 H Hence by substituting and using lemma 10: ¯ı ´ ” ¯ ´ r t ps, aq ´ Ů t ps, aq ď eβrht ps,aq 3bt ps, aq ` 1 ` 3 ppt Zrt ´ Z̊ t U h`1 h h`1 h h h H t ps, aq. In this case: Second case: Ůht ps, aq “ Ůh,pes

” r t ps, aq ´ Ů t ps, aq ď eβrht ps,aq bt ps, aq ` 1 ppt pZrt ´ Z t qps, aq ` ppt Zrt ps, aq U h h h h h`1 H h h`1 r h`1 ´ ¯ ˘ ` 1 t t t ps, aq ´ bth ps, aq ´ ppth Zrh`1 ´ ppth Z̊h`1 ps, aq ´ Z̊h`1 H˙ ˆ ” ¯ ı 1 1 t t t t t ppth pZrh`1 “ eβrh ps,aq 2bth ps, aq ` 1 ` q ` pZrh`1 ´ Z̊h`1 q ps, aq ´ Zh`1 H H r Hence by lemma 10 we find: ” ´ ¯ ´ ¯ı r t ps, aq ´ Ů t ps, aq ď eβrht ps,aq 2bt ps, aq ` 1 ` 2 ppt Zrt ´ Z̊ t U h h h h`1 H h h`1 Which conclude the recursion We now prove lemma 9: Proof We first prove by backward induction that, for all h and s, Zrht psq ´ Z̊ht psq ď pπht`1 Gth qpsq. For h “ H ` 1 it holds since both sides are 0. Assume it holds at step h ` 1. For a “ πht`1 psq r t ps, aq ´ Ů t ps, aq. Zrht psq ´ Z̊ht psq “ U h h

(14)

Essakine Vernade

By lemma 11, we have : ¯ı ” ´ ¯ ´ r t ps, aq ´ Ů t ps, aq ď eβrht ps,aq 3bt ps, aq ` 1 ` 3 ppt Zrt ´ Z t U h h h H h h`1 r h`1 By the induction hypothesis inside the tilted expectation: t t ppth pZrh`1 ´ Z̊h`1 qps, aq ď ppth pπ t`1 Gth`1 qps, aq.

Thus, ´ 3 ¯ t t`1 t pp pπ Gh`1 qps, aq ď Gth ps, aq “ pπht`1 Gth qpsq Zrht psq ´ Z̊ht psq ď 3bth ps, aq ` 1 ` H h t`1 Finally, use optimism and the ring bridge: on E, Zh‹ ď Zrht (lemma 8) and Z̊ht ď Zhπ (lemma 10), hence t`1 Zh‹ psq ´ Zhπ psq ď Zrht psq ´ Z̊ht psq ď pπht`1 Gth qpsq

B.1.3. Sample complexity Now we prove theorem 4 for β ą 0 Proof the width certificate is: # t ps,aq βrh

Gth ps, aq “ min eβpH´hq , e

+ ” ´ ¯ ı 3 ppt π t`1 Gth`1 psq 3bth ps, aq ` 1 ` H h

Let us transition to the true MDP. Using Bernstein inequality: ˇ b ˇ t ˘ ` 2 ˇpp ph ´ ph qπ t`1 Gth`1 psqˇ ď 2 Varph π t`1 Gth`1 psq αpnth ps, aq ` eβpH´hq αpnth ps, aq 3 t`1 t t`1 t Gh`1 psq. Hence, using the inequalNow, we use the inequality Varpπh`1 Gh`1 psqq ď eβpH´hq πh`1 ? ity xy ď x ` y:

ˇ t ˇpp p ´ ph qπ t`1 Gt h

ˇ ˇ ď 1 ph π t`1 Gt psq ` 3HeβpH´hq αpnt ps, aqq h`1 h H

h`1 psq

Entropic Best Policy Identification

And using the variance transportation lemmas 25,26 and that α‹ pnth ps, aqq ď αpnth ps, aqq: d d d ‹ pnt ps, aqq ‹ t ‹ pnt ps, aqq α α t`1 h h π t βpH´hq p pZ rt ´ Z πt`1 qps, aq α pnh ps, aqq q q ď 2 pZ ` Varppt pZrh`1 Var 4e p h h h`1 h`1 h`1 h nth ps, aq nth ps, aq nth ps, aq αpnt ps, aqq ` 2eβpH´hq t h nh ps, aq d ‹ t α‹ pnth ps, aqq βpH´hq α pnh ps, aqq π t`1 q ` 4He ď 2 Varph pZh`1 nth ps, aq nth ps, aq αpnt ps, aqq 1 t ‹ ` ph pZrh`1 ´ Zh`1 qps, aq ` 2eβpH´hq t h H nh ps, aq d ‹ t α‹ pnth ps, aqq βpH´hq α pnh ps, aqq π t`1 rq ď 2 Varph pZh`1 ` 4He nth ps, aq nth ps, aq `

αpnt ps, aqq 1 ph π t`1 Gth`1 psq ` 2eβpH´hq t h H nh ps, aq

Hence, by coarsening the constants for the sake of simplicity: d ‹ t ? ? α‹ pnth ps, aqq βpH´hq α pnh ps, aqq π t`1 q ` 4p2 2 ` 1qHe bth ps, aq ď 4 2 Varph pZh`1 nth ps, aq nth ps, aq ? ? αpnt ps, aqq 2 2 ` p5 ` 4 2qeβpH´hq t h ` ph π t`1 Gth`1 psq nh ps, aq H d ? t ‹ t 2 2 t`1 α pnh ps, aqq βpH´hq αpnh ps, aqq t`1 t π ď 6 Varph pZh`1 q ` psq ` 27He p π G h h`1 nth ps, aq H nth ps, aq We combine the two terms: ? α‹ pnth ps, aqq 6 2 36 ` ph π t`1 Gth`1 psq nth ps, aq H ´ t 3¯ βpH´hq αpnh ps, aqq ` 81He ` 1` ph π t`1 Gth`1 psq nth ps, aq H ff ´ ´ ¯ t ps, aqq αpn 3¯1 3 ` 1` ph π t`1 Gth`1 psq ` 1 ` 3HeβpH´hq t h H H H nh ps, aq « d

Gth ps, aq ď eβrh ps,aq

t`1 Varph pZhπ q

Hence, simplifying it gives: « d

ff ˆ ˙ t ps, aqq ‹ pnt ps, aqq α αpn 13 h Gth ps, aq ď eβrh ps,aq 36 Varph pZh`1 q ` 1` ph π t`1 Gth`1 psq`84HeβpH´hq t h nth ps, aq H nh ps, aq π t`1

Essakine Vernade

Unrolling this inequality and using the terminal condition GtH`1 “ 0 we get: «

H ÿ

pπ1 Gt1 qps1 q ď Eπ

h ¯ˆ b ´ ÿ ` πt`1 ˘ ` t ˘ ri psi , ai q 36 Varph Zh`1 α‹ nh psh , ah q ^ 1 exp β

h´1

i“1

h“1

˙ˇˇ ff ` ˘ ˇ ` 84HeβpH´hq α nth psh , ah q ^ 1 ˇs1 ˇ 13 . Since we have: where κ “ 1 ` 11 h´1

´ 13 ¯h´1 13 ¯H “ 1` ď lim 1 ` “ e13 HÑ`8 H H ´

we get: « π t`1

pπ1 Gt1 qps1 q ď e13 E

H ÿ h“1

˜ h b ´ ÿ ¯ ˘ ` π ˘ ` t α‹ nh psh , ah q ^ 1 exp β ri psi , ai q 36 Varph Zh`1 i“1

¸ˇ ff ˇ ˘ ` ˇ ` 84HeβpH´hq α nth psh , ah q ^ 1 ˇs1 ˇ The algorithm stops when: π1τ G1 ps1 q ď We upper bound

e|β|ε ´ 1 rτ Z1 ps1 q e|β|ε

π1t G1 ps1 q rt ps1 q for t “ 1, ..., τ ´ 1, using optimism: Z 1

π1 Gt1 ps1 q pπ1 Gt ps1 q ď πt`11 Z1 ps1 q Zr1t ps1 q «

˜ d ` πt`1 ˘ h ¯ ´ ÿ ˘ Varph Zh`1 psh , ah q ` t 13 ri psi , ai q 36 exp β ďe E α nh psh , ah q ^ 1 t`1 2 π pZ1 q ps1 q i“1 h“1 ¸ˇ ff ` ˘ ˇˇ ` 84HeβpH´hq α nth psh , ah q ^ 1 ˇs1 ˇ π t`1

H ÿ

Let us bound the first term, using Cauchy-Schwartz inequality: » ˇ fi ˜d ` πt`1 ˘ ` t H h ˇ ¯ ´ ¯ ‹ ÿ ÿ ` ˘ Var Z α nh ps, aq ph ˇ h`1 π t`1 – ^ 1 ˇs1 fl E exp β ri psi , ai q t`1 2 t ps, aq π ˇ n pZ1 q h i“1 h“1 ˜d ` πt`1 ˘ ` H ÿ h ´ ÿ ¯ ÿ ` α‹ nth ps, aq ˘¯ Varph Zh`1 t`1 “ ph ps, aq exp β ri psi , ai q ^ 1 t`1 nth ps, aq pZ1π q2 i“1 h“1 s,a g g fH H ÿ h ´ ÿ ¯ Varp `Z πt`1 ˘ f fÿ ÿ fÿ α‹ pnth ps, aqq h h`1 e t`1 t`1 e ď ph ps, aq exp 2β ri psi , ai q p ps, aq t`1 h nth ps, aq pZ1π q2 i“1 h“1 s,a h“1 s,a

Entropic Best Policy Identification

For a policy π. By lemma 23 we have: ` π ˘ ` ˘ π σVhπ psq “ e2βrh ps,πpsqq Varph Zh`1 ps, πpsqq ` e2βrh ps,πpsqq ph σVh`1 ps, πpsqq ř Multiplying the equation by h´1 i“1 ri psi , ai q and take the expectation under π: ” řh ı ” řh´1 ” řh ı ` π ˘ı π psh`1 q ` Eπ e2β i“1 ri psi ,ai q σVh`1 Eπ e2β i“1 ri psi ,ai q σVhπ psh q “ Eπ e2β i“1 ri psi ,ai q Varph Zh`1 π By summing over h “ 1, ..., H and since σVH`1 “ 0 we get: H ÿ

« π

π t`1 Varph Zh`1 r ps ,a q i i i i“1 t`1 pZ1π q2

2β

˘ ff

„

řh

h“1

“E

σV1π ps1 q pZ1π q2

But notice that for a deterministic policy π: π

σV1π ps1 q VarpeβR1 |S1 “ s1 q “ π pZ1π q2 EpeβR1 |S1 “ s1 q2 Using lemma 24 we get that:

σV1π ps1 q peβGmax pMq ´ 1q2 ď pZ1π q2 eβGmax pMq

Applying this for π t`1 we get: H ÿ ÿ h“1 s,a

pt`1 h ps, aq exp

¯ Var `Z πt`1 ˘ peβGmax pMq ´ 1q2 ph h`1 2β ri psi , ai q ď t`1 eβGmax pMq pZ1π q2 i“1 h ÿ

For the second term: ¸ˇ ff « ` t h H ˇ ¯ ´ ÿ ÿ ` ˘ ps, aq α n t`1 ˇ h ri psi , ai q HeβpH´hq exp β ^ 1 Eπ ˇs1 t ˇ nh ps, aq i“1 h“1 ` H ÿ h ´ ÿ ¯ t ÿ ˘ ` βpH´hq α nh ps, aq “ pt`1 ps, aq exp β r ps , a q He ^1 i i i h t nh ps, aq i“1 h“1 s,a ` H ÿ t ÿ ` ˘ βh βpH´hq α nh ps, aq ď pt`1 ps, aqe He ^ 1 h nth ps, aq h“1 s,a ` H ÿ ÿ ` α nth ps, aq ˘ t`1 βH ^1 ď He ph ps, aq t nh ps, aq h“1 s,a

Essakine Vernade

Hence: g ` f H ÿ f βGmax pMq ´ 1q2 ÿ ˘ ` α‹ nth ps, aq t`1 t 13 e pe ^1 ph ps, aq pπ1 G1 qps1 q ď 36e t βG pMq max nh ps, aq e h“1 s,a ` H ÿ ÿ ` α nth ps, aq ˘ t`1 13 βH ` 84e e ph ps, aq ^1 t nh ps, aq h“1 s,a g d ` fH ÿÿ ` α‹ nth ps, aq ˘ peβGmax pMq ´ 1q2 f t`1 13 e ď 36e ph ps, aq ^1 t βG pMq nh ps, aq e max h“1 s,a ` H ÿ ÿ ˘ ` α nth ps, aq t`1 13 βH ` 84e e ph ps, aq ^1 t nh ps, aq h“1 s,a Let us sum over t ď τ . By sub-optimality for each episode t “ 0, ..., τ ´ 1 we have: π1t`1 G1 ps1 q ą

e|β|ε ´ 1 rt Z1 ps1 q e|β|ε

Hence by summing over all the episodes and using Cauchy-Schwartz: g ` τÿ ´1 f H ÿ βε f peβGmax pMq ´ 1q2 ÿ ˘ ` α‹ nth ps, aq e ´1 t`1 13 e ph ps, aq ^1 τ ď 36e t βε βG pMq max nh ps, aq e e t“1 h“1 s,a ` τÿ ´1 ÿ H ÿ ` α nth ps, aq ˘ t`1 13 βH ph ps, aq ` 84e e ^1 t nh ps, aq t“1 h“1 s,a g d ` fτ ´1 H ÿ ÿÿ ` α‹ nth ps, aq ˘ peβGmax pMq ´ 1q2 ? f t`1 13 e ď 36e p ps, aq T ^ 1 h t nh ps, aq eβGmax pMq t“1 h“1 s,a ` τÿ ´1 ÿ H ÿ ` α nth ps, aq ˘ t`1 13 βH ph ps, aq ` 84e e ^1 t nh ps, aq t“1 h“1 s,a Using lemma 27 to relate the true counts to pseudo-counts we get: τÿ ´1 ÿ H ÿ t“1 h“1 s,a

` ` α nth ps, aq

pt`1 h ps, aq

nth ps, aq

´1 ÿ H ÿ ˘ τÿ ` t ˘ rh ps, aq _ 1 ^1 ď pt`1 h ps, aqα n t“1 h“1 s,a

ď αpτ ´ 1, δq

τÿ ´1 ÿ H ÿ

pt`1 h ps, aq

t“1 h“1 s,a

ď αpτ ´ 1, δq

τÿ ´1 ÿ H ÿ

rth`1 ps, aq ´ n n rth ps, aq rth ps, aq _ 1 n t“1 h“1 s,a

ď 3SAHαpτ ´ 1, δq logpτ ` 1q

1 rth ps, aq _ 1 n

Entropic Best Policy Identification

Where in the final inequality we used lemma 29. Similarly, we find: τÿ ´1 ÿ H ÿ

` ` α‹ nth ps, aq

pt`1 h ps, aq

t“1 h“1 s,a

nth ps, aq

˘ ^ 1 ď 3SAHα‹ pτ ´ 1, δq logpτ ` 1q

Hence: d τ

eβε ´ 1 eβε

ď 36e13

peβGmax pMq ´ 1q2 τ SAHα‹ pt ´ 1, δq logpt ` 1q ` 84e13 eβH SAHαpt ´ 1, δq logpt ` 1q eβGmax pMq

Therefore, by replacing α˚ and α by their expression and using that logpτ ` 1q ď logp8eτ q since τ ě 1: d ´ ` ˘ ` ˘2 ¯ ` 3SAH ˘ eβε ´ 1 peβGmax pMq ´ 1q2 13 log 8eτ ` log 8eτ τ ď 36e τ SAH log δ eβε eβGmax pMq ´ ` 3SAH ˘ ` ˘ ` ˘2 ¯ ` 84e13 eβH SAH log log 8eτ ` S log 8eτ δ Finally, we use lemma 29 with : d βε e peβGmax pMq ´ 1q2 SAH C “ 36e13 βε p e ´1 eβGmax pMq D“

eβε 84e13 eβH H 2 SA eβε ´ 1

and

, A “ logp

3SAH q δ

,B “ 1

E“S

Which yield: ˆ ˙ ˆ ˙ βH H 2 SA e2βε 3SAH peβGmax pMq ´ 1q2 3SAH 2 βε e τď` SAH logp q ` 1 C ` 3e logp q ` S C12 ` 1 ˘2 1 βε ´ 1 βGmax pMq βε δ δ e e e ´1 ˙ ˆ pS`1qpH`1qe|βH SAH 2 8 17 Where C1 “ 5 log 4e eβε ´1 In particular, if ε is small enough so that the first term dominates the second then: τď`

e2βε eβε ´ 1

˘2

peβGmax pMq ´ 1q2 3SAH 2 SAH logp qC2 δ eβGmax pMq

Where C2 “ 3eC1 . We can finally hide the constants and the log terms to get: ˜ ¸ 1 peβGmax pMq ´ 1q2 τ “ Õ ` SAH ˘2 eβGmax pMq eβε ´ 1 Finally to see that the stopping rule implies pε, δqPAC, remark that at time τ : π1τ G1 ps1 q ď

eβε ´ 1 rt Z1 ps1 q eβε 31

Essakine Vernade

This is equivalent to : ˜

π1τ G1 ps1 q ď pe|β|ε ´ 1q Zr1t ps1 q ´ π1τ G1 ps1 q Since Zr1t ps1 q ´ Z1‹ ps1 q ď Zr1t ps1 q ´ Z̊1t ps1 q ď πt`1,1 Gt1 ps1 q, this stopping condition is stronger than the condition: τ π1τ G1 ps1 q ď peβε ´ 1qZ1π But we can write: 1 τ `1 pV1‹ ´ V1π qps1 q “ log

Z1‹ τ Z1π

˙ ˆ ˆ τ ˙ 1 1 Z1‹ ´ Z1π π1τ G1 ps1 q ps1 q “ log 1 ` ps1 q ď log 1 ` ps1 q ď ε τ τ β Z1π β Z1π

B.2. Case β ă 0 B.2.1. Stopping rule We first discuss the stopping rule for β ă 0. The difference in value functions can be expressed in the exponential space as: ˆ ‹ ˙ Z1 1 ‹ π t`1 pV1 ´ V1 qps1 q “ log ps1 q t`1 β Z1π ˜ ¸ t`1 Z1‹ ´ Z1π 1 ps1 q. “ log 1 ` t`1 β Z1π To ensure the policy is ε-optimal, it suffices to satisfy at stopping time τ : ´ ¯ t π1t G1 ps1 q ď eβε ´ 1 Z1π ps1 q t

(15)

However, Z1π is unknown as it relies on the true dynamics. We therefore substitute it with a computable lower bound: ´ ¯ t π1t G1 ps1 q ď eβε ´ 1 Z1π ps1 q (16) r where both π1t G1 ps1 q and Z1t ps1 q can be computed efficiently by dynamic programming. r B.2.2. Confidence Bounds We first start with a lemma: Lemma 12 On the good event E ´ : d ? ` ˘ ‹ α‹ pnth ps, aqq t | ph ´ pph Zh`1 | ď 2 2 Varppt pZht qps, aq ` 5p1 ´ eβpH´hq qαpnth ps, aqq t ps, aq h n r h ¯ ‹ t α pnh ps, aqq 1 t´ ‹ t p ` 4Hp1 ´ eβpH´hHq q ` p Z ´ Z ps, aq nth ps, aq H h h`1 r h`1 32

Entropic Best Policy Identification

Proof On the good event E ´ we have: d ‹ t ‹ t ˇ ˇpph ´ ppt qZ ‹ ps, aq| ď 2 Varp pZ ˚ q α pnh ps, aqq ` 3p1 ´ eβpH´hq q α pnh ps, aqq h h`1 h h`1 nth ps, aq nth ps, aq Since Zh‹ and ph are unknown, we use a variance transportation inequality to replace with its value for Zrt the optimistic bound for V ‹ . By applying lemma 25 and lemma 26 successively: h

‹ ‹ q ď 2 Varppt pZh`1 qps, aq ` 4p1 ´ eβpH´hq q2 Varph pZh`1 h

αpnth ps, aqq nth ps, aq

αpnt ps, aqq t ‹ t ď 4 Varppt pZh`1 qps, aq ` 4p1 ´ eβpH´hq qp pth pZh`1 ´ Zh`1 qps, aq ` 4p1 ´ eβpH´hq q t h h nh ps, aq r r ? ? ? ? Hence, using the inequality a ` b ď a ` b and then ab ď aη ` ηb for η “ H and using that α‹ pnth ps, aqq ď αpnth ps, aqq: d d ‹ pnt ps, aqq α‹ pnth ps, aqq α h t qps, aq t Varph pZh‹ qps, aq ď 2 Var p Z pph h nth ps, aq nth ps, aq r d α‹ pnth ps, aqq ‹ t pth pZh`1 ` 4p1 ´ eβpH´hq qp ´ Zh`1 qps, aq nth ps, aq r d α‹ pnth ps, aqq αpnth ps, aqq ` 2p1 ´ eβpH´hq q nth ps, aq nth ps, aq d ‹ t α‹ pnth ps, aqq βpH´hq α pnh ps, aqq ď 2 Varppt pZht qps, aq ` 4Hp1 ´ e q h nth ps, aq nth ps, aq r `

αpnt ps, aqq 1 t ‹ t pph pZh`1 ´ Zh`1 qps, aq ` 2p1 ´ eβpH´hq q t h H nh ps, aq r

Hence: d ? α‹ pnth ps, aqq ‹ ‹ t |ph Zh`1 ´ ppth ps, aqZh`1 | ď 2 2 Varppt pZh`1 qps, aq ` 5p1 ´ eβpH´hq qαpnth ps, aqq h nth ps, aq r ¯ α‹ pnth ps, aqq 1 t´ ‹ t p p ` 4Hp1 ´ eβpH´hq q ` Z ´ Z ps, aq nth ps, aq H h h`1 r h`1

Denote the bonus term as: d t ‹ t ? α‹ pnth ps, aqq βpH´hq αpnh ps, aqq βpH´hq α pnh ps, aqq bth ps, aq “ 2 2 Varppt pZht qps, aq `5p1´e q `4Hp1´e q h nth ps, aq nth ps, aq nth ps, aq r (17)

Essakine Vernade

Now, like the case β ą 0 we define define optimistic and pessimistic state-value function on the exponential transform of Q‹h which denoted by Uh‹ . ff+ ´ ¯ 1 r t ps, aq “ min 1, eβrh ps,aq ppt Zrt ps, aq ` bt ps, aq ` ppt Zrt ´ Z t ps, aq U h h`1 h h H h h`1 r h`1 #

r t ps, aq, Zrht psq “ min U h aPA #

t ZrH`1 psq “ 1 «

ff+ ¯ ´ 1 t t t ps, aq ´ bth ps, aq ´ ppth Zrh`1 ps, aq Uht ps, aq “ max eβpH´h´1q , eβrh ps,aq ppth Zh`1 ´ Zh`1 H r r r t Zht psq “ min Uht ps, aq, ZH`1 psq “ 1 aPA r r r And we consider the greedy policy:

(18)

πht`1 psq “ arg min Uht ps, aq aPA r Let us prove an optimism lemma: Lemma 13 On the good event E ´ we have: r t ps, aq Uht ps, aq ď Uh‹ ps, aq ď U h r and

Zht psq ď Zh‹ psq ď Zrht psq r Proof We proceed by induction over h. For h “ H ` 1 the result is trivially upper bounding and (resp. lower bounding ) Q‹ by H and 1. r t ps, aq ă H .we have that: Assume the inequality holds for h1 ą h. Fix ps, aq and assume Q h ff « ¯ ´ 1 t t t βr ps,aq ‹ t ‹ t t t r ps, aq ´ U ps, aq “ e h pph Zrh`1 ps, aq ` bh ps, aq ` pph Zrh`1 ´ Zh`1 ps, aq ´ ph Zh`1 ps, aq U h h H r « ¯ ¯ ´ ´ ‹ ‹ t ps, aq ` ppth ´ ph Zh`1 ps, aq ps, aq ´ Zh`1 “ eβrh ps,aq ppth Zrh`1 ff ´ ¯ 1 t t ´ Zh`1 ps, aq ` bth ps, aq ` ppth Zrh`1 H r But we know by Bernstein inequality that: ´ ¯ ¯ ¯ 1 ´ ‹ 1 ´ t t ‹ ppth ´ ph Zh‹ ps, aq ě ´bth ps, aq ´ ppth Zh`1 ´ Zh`1 ps, aq ě ´bth ps, aq ´ ppth Zrh`1 ´ Zh`1 ps, aq H H r Hence: r t ps, aq ´ U ‹ ps, aq ě eβrh ps,aq U h h

« ´

ff ¯ 1 ¯ t ´ rt ‹ 1` pp Z ps, aq ´ Zh`1 ps, aq ě 0 H h h`1

Where we used the induction hypothesis. We prove the pessimistic property in the same way

Entropic Best Policy Identification

B.2.3. Stopping rule We define the stopping rule for the algorithm for β ă 0 as: + # ” ´ ¯ ı 3 ppt π t`1 Gth`1 ps, aq Gth ps, aq “ min 1, eβrh ps,aq 3bth ps, aq ` 1 ` H h

(19)

Lemma 14 establishes the validity of this stopping rule by showing that, with high probability, it bounds the certificate width: Lemma 14 On the good event E ` , for all t and all h, Zhπ

t`1

psq ´ Zh‹ psq ď πht`1 Gth psq

In particular, at the initial state s1 , V1‹ ps1 q ´ V1π

t`1

@s P S

ps1 q ď π1t`1 Gt1 ps1 q

We prove the lemma 14 in this section : Like the case β ă 0. We define the auxiliary (analysis-only) t ” 1, we recurse backward for h “ H, . . . , 1: variable Z̊ht . Setting Z̊H`1 ! ” ı) ` ˘ t t t qps, aq ` bth ps, aq ` H1 ppth pZ̊h`1 ps, aq “ min 1, eβrh ps,aq pp pth Z̊h`1 Ůh,opt ´ Z th`1 q ps, aq , r ) ! t t t βrh ps,aq Ůh ps, aq “ max e pph Z̊h`1 qps, aq, Ůh,opt ps, aq , ` ˘ Z̊ht psq “ Ůht s, πht`1 psq . Because Zrt is pessimistic with respect to Z ‹ (and β ă 0 reverses the relevant order), we t`1 cannot directly compare it to Z π . We introduce Z̊ t as a bridge quantity. Intuitively, Z̊ t satisfies the exponential Bellman recursion under the true kernel ph while being clipped by an optimistic t`1 empirical backup; hence it serves as a worst-case upper bound for both Zrt and Z π . Lemma 15 For all t, For all ph, s, aq: ¯ ´ t`1 r t ps, aq, U πh ps, aq Ůht ps, aq ě max U h h and

´ ¯ π t`1 Z̊ht psq ě max Zrht psq, Zh h ps, aq

Proof We proceed by backward induction. For h “ H `1, all values are equal to 0 so the inequalities hold. Assume that for some h ď H we have for all ps, aq: ´ ¯ t r t ps, aq, U πt`1 h ps, aq Ůh`1 ps, aq ě max U h`1 h`1 and

´ ¯ t t π t`1 Z̊h`1 psq ě max Zrh`1 psq, Zh`1 ps, aq

we have by construction: t`1

t t π Ůht ps, aq ě Ůh,true ps, aq “ eβrh ps,aq pph Z̊h`1 qps, aq ě eβrh ps,aq pph Zh`1 qps, aq “ Uhπ

t`1

ps, aq

Essakine Vernade

Where we used the induction hypothesis and the monotonicity of the exponential Bellman operator. r t ps, aq ě Ů t ps, aq ´ U r t ps, aq Ůht ps, aq ´ U h h,opt h «

¯ 1 t´ t t ps, aq pph Z̊h`1 ´ Zh`1 H r ff ´ ¯ ¯ ´ 1 t t ´ ppth Zrht ps, aq ` bth ps, aq ` ppth Zrh`1 ps, aq ´ Zh`1 H r «ˆ ff ˙ ´ ¯ 1 βrh ps,aq t t t ěe 1` pph Z̊h`1 ´ Zrh`1 ps, aq H t ps, aq ` bth ps, aq ` ě eβrh ps,aq ppth Z̊h`1

Where we applied the induction hypothesis, we conclude then: r t ps, aq Ůht ps, aq ě U h For Z: Z̊ht psq ´ Zhπ

t`1

ps, aq “ Ůht ps, πht psqq ´ Uhπ

t`1

ps, πht`1 psqq ě 0

And: r t ps, aq “ Zrt ps, aq r t ps, π t psqq ě min U Z̊ht psq “ Ůht ps, πht psqq ě U h h h h aPA

Which conclude the recurrence Lemma 16 For anyt, any h P t1, ..., Hu and any state-action pair: ¯ ı ´ ” 3 ¯ t´ t t ps, aq pph Z̊h ps, aq ´ Zh`1 Ůht ps, aq ´ Uht ps, aq ď eβrh ps,aq 3bth ps, aq ` 1 ` H r r Proof Fix h P t1, ..., Hu and fix a state-action pair ps, aq. We have two cases: t ps, aq, we have: First case: Ůht ps, aq “ Ůh,true ” ¯ ı 1 ´ t t t t Ůht ps, aq ´ Uht ps, aq ď eβrh ps,aq bth ps, aq ` ppth Zrh`1 ´ Zh`1 ps, aq ` ph Z̊h`1 ps, aq ´ ppth Zh`1 ps, aq H r r r The last term can be written as: ´ ¯ ` ˘ ‹ ` ˘` t ˘ t t t t ‹ ph Z̊h`1 ps, aq ´ ppth Zh`1 ps, aq “ ppth Z̊h`1 ´ Zh`1 ps, aq ` ppth ´ ph Zh`1 ps, aq ` ph ´ ppth Z̊h`1 ´ Zh`1 r r For the second term, by lemma 12: ¯ ¯ ` ˘ ‹ 1 ´ t 1 ´ t ‹ t ´ Zh`1 ps, aq ď bth ps, aq ` ppth Zrh`1 ´ Z̊h`1 ps, aq | ph ´ ppth Zh`1 ps, aq| ď bth ps, aq ` ppth Zrh`1 H H

Entropic Best Policy Identification

? For the third term, by the KL-Bernstein inequality 22 and using the inequality ab ď Ha ` bH: d ¯ αpnt ps, aqq ` ˘` ˘ αpnt ps, aqq 2 ´ ‹ t h ‹ t 1 ´ eβpH´hq ´ Z̊h`1 q th ` ph ´ ppth Zh`1 ´ Z̊h`1 ď 2 Varppt pZh`1 h nh ps, aq 3 nth ps, aq d ¯ αpnt ps, aqq αpnt ps, aqq 2 ´ h ‹ t ď 2eβpH´hq ppth pZh`1 ´ Z̊h`1 q th 1 ´ eβpH´hq ` nh ps, aq 3 nth ps, aq ¯ αpnt ps, aqq αpnt ps, aqq 2 ´ 1 t t h ` ´ Z̊h`1 q ` 2HeβpH´hq t h ď ppth pZrh`1 1 ´ eβpH´hq H nh ps, aq 3 nth ps, aq Hence by combining the two bounds: ¯ ´ 2 ¯ t´ t t t t ps, aq ď 2bth ps, aq ` 1 ` ph Z̊h`1 ps, aq ´ ppth Zh`1 pph Z̊h`1 ´ Zh`1 H r r Hence by substituting and using lemma 15: ´ ” ¯ı 3 ¯ t ´ rt t t Ůht ps, aq ´ Uht ps, aq ď eβrh ps,aq 3bth ps, aq ` 1 ` pph Zh`1 ´ Z̊h`1 H r t ps, aq, we have: Second case: Ůht ps, aq “ Ůh,opt «

¯ 1 ´ t t t ps, aq ` bth ps, aq ` ppth Z̊h`1 Ůht ps, aq ´ Uht ps, aq ď eβrh ps,aq ppth Z̊h`1 ´ Zh`1 ps, aq H r r ˜ ¸ff ´ ¯ 1 t t t ps, aq ´ bth ps, aq ´ ppth Zrh`1 ´ ppth Zh`1 ´ Zh`1 ps, aq H r r ff « ˆ ˙ ´ ¯ ¯ ´ 1 1 t t t t ps, aq ` ppth Zrh`1 ´ Zh`1 ps, aq ´ Zh`1 “ eβrh ps,aq 2bth ps, aq ` 1 ` ppth Z̊h`1 H H r r Using lemma 15 we get: ” ´ ¯ ı 2 ¯ t´ t t pph Z̊h ps, aq ´ Zh`1 Ůht ps, aq ´ Uht ps, aq ď eβrh ps,aq 2bth ps, aq ` 1 ` ps, aq H r r

We now prove lemma 14: Proof We first prove by backward induction that, for all h and s, Z̊ht psq ´ Zht psq ď pπht`1 Gth qpsq. r For h “ H ` 1 it holds since both sides are 0. Assume it holds at step h ` 1. For a “ πht`1 psq Z̊ht psq ´ Zht psq “ Ůht ps, aq ´ Uht ps, aq r r Apply Lemma 15: ¯ ı ” ´ 3 ¯ t´ t t t Ůht ps, aq ´ Uht ps, aq ď eβrh ps,aq 3bth ps, aq ` 1 ` pph Z̊h ps, aq ´ Zh`1 ps, aq H r r 37

Essakine Vernade

By the induction hypothesis: ´ ¯ t ps, aq ď ppth pπ t`1 Gth`1 qps, aq. ppth Z̊ht ps, aq ´ Zh`1 r Thus, ´ 3 ¯ t t`1 t Z̊ht psq ´ Zht psq ď 3bth ps, aq ` 1 ` pp pπ Gh`1 qps, aq ď Gth ps, aq “ pπht`1 Gth qpsq H h r Finally, use optimism and the ring bridge: on E, Zh‹ ě Zht (optimism lemma 13) and Zhπ r (Lemma 15): t`1 Zhπ psq ´ Zh‹ psq ď Z̊ht psq ´ Zht psq ď pπht`1 Gth qpsq r

t`1

ď Z̊ht

B.2.4. sample complexity Proof the width certificate is: # Gth ps, aq “ min

t ps,aq βrh

1, e

+ ı ´ ” 3 ¯ t t`1 t t pp π Gh`1 psq 3bh ps, aq ` 1 ` H h

Let us transition to the true MDP. Using Bernstein inequality: d ˇ ˇ t ` ˘ αp nth ps, aq 2 αpnt ps, aqq ˇpp ph ´ ph qπ t`1 Gth`1 psqˇ ď 2 Varph π t`1 Gth`1 psq ` p1 ´ eβpH´hq q t h t nh ps, aq 3 nh ps, aq t`1 t t`1 t Gh`1 psq. Hence, using the Now, we use the inequality Varpπh`1 Gh`1 psqq ď p1 ´ eβpH´hq qπh`1 ? inequality xy ď x ` y:

ˇ ˇ t αpnt ps, aq 1 ˇpp ph ´ ph qπ t`1 Gth`1 psqˇ ď ph π t`1 Gth`1 psq ` 3Hp1 ´ eβpH´h`1q q t h H nh ps, aq And using the variance transportation lemmas 25 and 26 and that α‹ pnth ps, aqq ď αpnth ps, aqq: d d ‹ pnt ps, aqq α α‹ pnth ps, aqq h t π t`1 q qps, aq ď 2 Varppt pZh`1 Var pZ p h h`1 h nth ps, aq nth ps, aq r d α‹ pnth ps, aqq π t`1 ´ Z t ` 4p1 ´ eβpH´hq qph pZh`1 qps, aq h`1 nth ps, aq r αpnt ps, aqq ` 2p1 ´ eβpH´hq q t h nh ps, aq d ‹ t α‹ pnth ps, aqq βpH´hq α pnh ps, aqq π t`1 q ď 2 Varph pZh`1 ` 4Hp1 ´ e q nth ps, aq nth ps, aq αpnt ps, aqq 1 π t`1 t ` ph pZh`1 ´ Zh`1 qps, aq ` 2p1 ´ eβpH´hq q t h H nh ps, aq r d ‹ t α‹ pnth ps, aqq βpH´hq α pnh ps, aqq π t`1 q ď 2 Varph pZh`1 ` 4Hp1 ´ e q nth ps, aq nth ps, aq `

αpnt ps, aqq 1 ph π t`1 Gth`1 psq ` 2p1 ´ eβpH´hq q t h H nh ps, aq 38

Entropic Best Policy Identification

Since we have : t`1

π t t t Zh`1 ´ Zh`1 ď Z̊h`1 ´ Zh`1 ď Gth`1 psq r r Hence, using that α‹ pnth ps, aqq ď αpnth ps, aqq and simplifying constants and using that H ě 1: d t ‹ t 3 t`1 α pnh ps, aqq t`1 t βpH´hq αpnh ps, aqq bth ps, aq ď 6 Varph pZhπ q ` p π G psq ` 27Hp1 ´ e q h h`1 nth ps, aq H nth ps, aq

We combine the two terms: « d

? α‹ pnth ps, aqq 6 2 36 Varph pZh q ` ph π t`1 Gth`1 psq nth ps, aq H αpnt ps, aqq ´ 3¯ ` 81Hp1 ´ eβpH´hq q t h ph π t`1 Gth`1 psq ` 1` nh ps, aq H ff ´ ´ t 3¯1 3¯ t`1 t βpH´hq αpnh ps, aqq ` 1` ph π Gh`1 psq ` 1 ` 3Hp1 ´ e q t H H H nh ps, aq π t`1

Gth ps, aq ď eβrh ps,aq

Hence, simplifying it gives: « d

ff ˙ t ps, aqq t ps, aqq ˆ αpn αpn 13 t`1 ` 1` Gth ps, aq ď eβrh ps,aq 36 Varph pZhπ q t h ph π t`1 Gth`1 psq`81Hp1´eβpH´hq q t h nh ps, aq H nh ps, aq Unrolling this inequality like the case β ą 0: ˜ « h H b ¯ ´ ÿ ÿ ` π ˘ ` t ˘ t 13 π ri psi , ai q 36 Varph Zh`1 exp β pπ1 G1 qps1 q ď e E α nh psh , ah q ^ 1 h“1

i“1

¸ˇ ff ˇ ˘ ` ˇ ` 81Hp1 ´ eβpH´hq qα nth psh , ah q ^ 1 ˇs1 ˇ The algorithm stops when: π1τ G1 ps1 q ď p1 ´ eβε qZ1π r

This is equivalent to: π1τ G1 ps1 q ď

˘ e|β|ε ´ 1 ` πτ Z1 ` π1 Gt1 ps1 q |β|ε 2e ´1 r

We then need to upper bound the quantity

π1t G1 ps1 q for t “ 1, ..., τ ´ 1: t Z1π r

π1 Gt1 ps1 q π1 Gt1 ps1 q ď t`1 Z1 ` π1 Gt1 ps1 q Z1π ps1 q r « ˜ d ` πt`1 ˘ ´ ` H h ´ ¯ ¯ 13 ÿ ÿ Varph Zh`1 α nth psh , ah q e π t`1 ď E exp β ri psi , ai q 36 ^ 1 t`1 β nth ps, aq pZ1π q2 i“1 h“1 ¸ˇ ff ´ α`nt ps , a q ¯ ˇ ˇ h h h βpH´hq ` 81Hp1 ´ e q ^ 1 ˇs1 t ˇ nh ps, aq πt

Essakine Vernade

Like the case β ą 0 we write directly: H ÿ ÿ

pt`1 h ps, aq exp

h“1 s,a

h ¯ Var `Z π ˘ ´ ÿ π t`1 ‰ “ ph h`1 π σV1 ri psi , ai q 2β “ E t`1 t`1 pZ1π q2 pZ1π q2 i“1

But since the greedy policy is deterministic we have: π

VarpeβR1 |S1 “ s1 q σV1π ps1 q “ π pZ1π q2 EpeβR1 |S1 “ s1 q2 Where L “ eβ

řH

i“1 ri psi ,ai q

, using lemma 24 we get that: pe|β|Gmax pMq ´ 1q2 σV1π ps1 q ď pZ1π q2 e|β|Gmax pMq

Hence: ˜ d ` πt`1 ˘ ` h ´ ÿ ¯ ˘¯ ` α nth ps, aq Varph Zh`1 t`1 ph ps, aq exp β ri psi , ai q 36 ^ 1 t`1 nth ps, aq pZ1π q2 i“1 h“1 s,a g g fH h H ÿ ´ ÿ ¯ Varp `Z πt`1 ˘ f fÿ ÿ fÿ αpnth ps, aqq h h`1 e t`1 t`1 e ď 36 ph ps, aq exp 2β ri psi , ai q p ps, aq t`1 h nth ps, aq pZ1π q2 i“1 h“1 s,a h“1 s,a g d fH |β|G pMq 2 ÿÿ max α‹ pnth ps, aqq pe ´ 1q f t`1 e p ď 36 ps, aq h nth ps, aq e|β|Gmax pMq h“1 s,a H ÿ ÿ

For the second term: ¸ ˜ ` ˜ « ¸ˇ ff ˘ h H ˇ ÿ ÿ α nth ps, aq 1 ˇ βpH´hq π t`1 r ps , a q Hp1 ´ e q exp β E ^ 1 ˇs1 i i i t`1 t ps, aq ˇ n Z1π ps1 q h i“1 h“1 ˜ ¸ ˜ ` ¸ ˘ H h t ps, aq ÿ α n 1 ÿ ÿ t`1 h ph ps, aq exp β “ πt`1 ri psi , ai q Hp1 ´ eβpH´hq q ^1 nth ps, aq Z1 i“1 h“1 s,a ˜ ` ¸ ˘ H ÿ ÿ α nth ps, aq t`1 βh βpH´hq ď ph ps, aqe Hp1 ´ e q ^1 nth ps, aq h“1 s,a ˜ ` ¸ ˘ H ÿ t ps, aq ÿ α n h ^1 ď He|β|H pt`1 h ps, aq t ps, aq n h h“1 s,a We then sum on t ă τ and use that by sub-optimality we have for t “ 1, ..., τ ´ 1: π1 Gt1 ps1 q π1τ G1 ps1 q ě ě e|β|ε ´ 1 τ t`1 pZ1π ` π1 Gt1 ps1 qq Z1π r

Entropic Best Policy Identification

Hence: g τ pe

|β|ε

13 2|β|ε

´ 1q ď 36e e

τÿ ´1 f f

ep pe

t“1 13 2|β|ε

` 81e e

|β|H

|β|Gmax pMq ´ 1q2

e|β|Gmax pMq

τÿ ´1 ÿ H ÿ

H ÿ ÿ

nth ps, aq

h“1 s,a

` ` α nth ps, aq

pt`1 h ps, aq

t“1 h“1 s,a

` ` α‹ nth ps, aq

pt`1 h ps, aq

nth ps, aq

g ` f ´1 H |β|Gmax pMq ´ 1q2 ? fτÿ ÿÿ ` α‹ nth ps, aq ˘ pe t`1 13 2|β|ε e ď 36e e ph ps, aq ^1 p q T t |β|G pMq max nh ps, aq e t“1 h“1 s,a ` τÿ ´1 ÿ H ÿ ` α nth ps, aq ˘ t`1 13 2|β|ε |β|H ` 81e e He ph ps, aq ^1 t nh ps, aq t“1 h“1 s,a d

Similarly to the case β ą 0 we bound the other terms using the counting argument which yield: d pe|β|Gmax pMq ´ 1q2 τ pe|β|ε ´ 1q ď 36e13 e2|β|ε p qτ SAHα‹ pτ ´ 1, δq logpτ ` 1q ` 81e13 e2|β|ε e|β|H H 2 SAαpτ ´ 1, δq e|β|Gmax pMq We replace α‹ and α by their expressions and using that logpτ ` 1q ď logp8eτ q since τ ě 1: d ´ ` 3SAH ˘ ` ˘ ` ˘2 ¯ pe|β|Gmax pMq ´ 1q2 qτ SAH log log 8eτ ` log 8eτ τ pe|β|ε ´ 1q ď 36e13 e2|β|ε p δ e|β|Gmax pMq ´ ` ˘ ` ˘ ` ˘2 ¯ 3SAH ` 81e13 e2|β|ε e|β|H H 2 SA log log 8eτ ` S log 8eτ δ Finally, we use lemma 29 with : b pe|β|Gmax pMq ´1q2 p qSAH 3SAH e|β|Gmax pMq C “ 36e13 q , A “ logp |β|ε δ e ´1 81e13 eβH H 2 SA D“ and E “ S e|β|ε ´ 1

,B “ 1

Which yield:

ˆ ˙ ˆ ˙ pe|β|Gmax pMq ´ 1q2 e2|β|ε 3SAH e2|β|ε βH 2 3SAH 2 q ` 1 C1 ` 3 |β|ε e H SA logp q ` S C12 ` 1 τď ` ˘2 SAH logp |β|ε δ δ e|β|Gmax pMq e ´ 1 e ´1 ˆ ˙ |βH SAH 2 Where C1 “ 85 log 4e17 pS`1qpH`1qe pe|β|ε ´1q In particular, assuming that ε is small enough that the first term dominates the second term then: τď

pe|β|Gmax pMq ´ 1q2 e2|β|ε 3SAH 2 qC2 ` ˘2 SAH logp |β|G pMq max δ e e|β|ε ´ 1

Essakine Vernade

Where C2 “ 3C1 . We can finally hide the constants and the log terms to get: ¸ ˜ e2|β|ε pe|β|Gmax pMq ´ 1q2 SAH τ “ Õ e|β|Gmax pMq pe|β|ε ´ 1q2 Finally to see that the algorithm is pε, δq PAC, At time τ : τ

π1τ G1 ps1 q ď p1 ´ eβε qZ1π r τ τ Since Z1π ě Z1π , this is a stronger stopping condition than: r τ π1τ G1 ps1 q ď p1 ´ eβε qZ1π Now, we write: τ

τ V1‹ ´ V1π

´ ´ ` Z1‹ ¯ 1 1 1 Z1‹ ´ Z1π ¯ π1τ G1 psq ¯ ps1 q “ log ps q “ ps q ď ps1 q ď ε log 1 ` log 1 ` τ τ τ 1 1 β Z1π β Z1π β Z1π

Appendix C. Lower bound We first state a change of measure for bandit models result from (Kaufmann et al., 2016): ř Lemma 17 Let Na ptq “ ts“1 1tAs “au be the number of draws of arm a between the instants 1 and t and Na “ Na pτ q be the total number of draws of arm a by some algorithm A “ ppAt q, τ, Ŝm q. Let ν and ν 1 be two bandit models with K arms such that for all a, the distributions νa and νa1 are mutually absolutely continuous. For any almost-surely finite stopping time σ with respect to pFt q, K ÿ Eν rNa pσqsKLpνa , νa1 q ě sup dpPν pEq, Pν 1 pEqq EPFσ

a“1

where dpx, yq “ x logpx{yq ` p1 ´ xq logpp1 ´ xq{p1 ´ yqq is the binary relative entropy, with the convention that dp0, 0q “ dp1, 1q “ 0. We make the following assumption: Assumption 1 Let d “ rlogA ppS ´ 3qpA ´ 1q ` 1qs. Assume that H ě 3d This assumption means that the horizon is long enough with respect to the size of MDP so that the agent can reach the reward state. We state the proof under the stronger assumption that d “ logA ppS ´ 3qpA ´ 1q ` 1q for simplicity. But as discussed in (Domingues et al., 2021), we can extend the construction to the general case by not having a full A-ary tree. Condition A The bound is stated in the small ε regime. Let c “ e|β|H ´ 1, Assume that we have : ! ) $ 4pc`1q2 ’ βą0 &min 2c2 `7c`4 , 16 13 e|β|ε ă (20) ! ) ’ %min 11c`8 , 11 βă0 10c`8 10 When |β|H ě lnp2q, the condition is reduced to the constants and gets harder to satisfy as β goes to 0. Condition 20 is used to have a valid construction in the proof below i.e to ensure the transition probabilities are in r0, 1s 42

Entropic Best Policy Identification

Theorem 3 Fix S ě 6, A ě 2, H P N, β P R‹ , and ε, δ P p0, 1q such that δ ď 1{16 and ε verify the condition (20). Then there exists an MDP M0 with S states, A actions, horizon H, and rewards in r0, 1s such that for every algorithm A output a policy π̂ that is pε, δq-PAC for the entropic risk measure after sampling τ trajectories we have: ˆ ˙ 1 pe|β|Gmax pM0 q ´ 1q2 e2 mintβ,0uε SAH 1 EM0 rτ s ě log |β|G pM q |β|ε 2 max 0 1650 δ e pe ´ 1q Proof Consider the following MDP defined in (Domingues et al., 2021)(with different transitions). We have three special states sw (waiting state), sg (the good absorbing state) and sb (the bad absorbing state). The rest S ´ 3 are arranged in the form of a full A-tree of depth d ´ 1 denoted L whose root is sroot , this means that the number of states is 3`

d´1 ÿ

Ai “ 3 `

i“1

Ad ´ 1 “S A´1

The action set is A “ t1, ..., Au and let aw P A be a fixed action, denote L “ Ad´1 . Let H ď H ´ d be an integer to be chosen later. The episode starts at sw , for steps h “ 1, ..., H we have the transition kernel: ph psw |a, sw q “ 1ta“aw ,hďHu

and

ph psroot |sw , aq “ 1 ´ ph psw |sw , aq

This means that for the first H steps, you can either chose the action aw to stay in the waiting state sw , or pick any other action and enter the tree at the next step, and at step h “ H we exit regardless of the chosen action. Once you enter the tree, the transition is deterministic. From any internal node x, the action a deterministically goes to the a-th child of x. Thus, after exactly H ` d the policy reaches a leaf of the tree L. Define the index set of “triples” U “ rHs ˆ L ˆ rAs,

|U| “ HLA

A triple u “ ph, l, aq corresponds to: • exiting at step h (so leaf step is h ` d), • reaching leaf l, • choosing leaf action a Fix two numbers 0 ă p´ ă p` ă 1.The baseline instance M0 : for every triple u “ pt, l, aq, Ppsg | t, l, aq “ p´ For M0 , all leafs are the same and takes to the good state with probability p´ regardless of the chosen action. The Special instance Mu for each u “ ph‹ , l‹ , a‹ q P U: identical to M0 except that at the single triple u “, Ppsg | uq “ p` 43

Essakine Vernade

action “ aw

sw action ‰ aw sroot

s2 1 ´ p´

p´

1 ´ p`

rh psb , aq “ 0

rh psg , aq “ 1th ě H̄ ` d ` 1u

Figure 1: An example of the MDP construction. Here the state s2 is optimal and have a better probability p` of landing in the good state sg , p` and p´ are defined bellow in the proof. Figure reproduced from (Domingues et al., 2021) and for all other triples u1 ‰ u, Ppsg | u1 q “ p´ . This means that there exists one unique optimal leaf l‹ where the agent can chose one unique optimal action a‹ when exiting precisely at step h‹ Thus, the family is tM0 u Y tMu : u P U u, and any two instances differ in exactly one Bernoulli parameter at one triple. Let H̃ “ H ` d ` 1, H 1 “ H ´ H ´ d Define rewards by rh ps, aq “ 1ts “ sg u1th ě H̃u So rewards are in r0, 1s, and rewards only accumulate from H̃ onward. We give an illustration in figure (1) taken from (Domingues et al., 2021) and adapted to have our transisitions that are a bit different from the original construction: By construction, by time H̃ the chain has already entered sg or sb and is absorbing. Therefore the return is H ÿ G“ 1tSh “ sg u “ H 1 1tSH̃ “ sg u P t0, H 1 u h“H̃

For any policy π and instance M, let pM pπq “ PM,π pSH̃ “ sg q

Entropic Best Policy Identification

The probability of being at the good state by the time H̃. By construction, by the time H̃ we are either in sg or sh , Then: 1

EreβG s “ p1 ´ pM pπqq1 ` pM pπqeβH “ 1 ` cpM pπq, Hence V M pπq “

c “ eβH ´ 1

` ˘ 1 log 1 ` cpM pπq β

(21)

For a policy π, define the probability of sucess: νπ puq “ Pπ pthe episode’s exit/leaf/action triple equals uq,

uPU

Because each episode produces exactly one triple, we have ÿ νπ puq “ 1 uPU

In instance Mu , since only when the realized triple equals the special one do we get probability p` ; otherwise p´ . The success probability is pMu pπq “ p´ ` pp` ´ p´ qνπ puq Let ∆ “ p` ´ p´ ą 0. The optimal policy in Mu can choose t, route to l, and pick action a deterministically so that νπ puq “ 1. Hence the optimal success probability is p` , and V Mu ,‹ “

1 logp1 ` cp` q β

Let us now chose p` and p´ so any ε-optimal policy must satisfy νπ puq ą 21 in Mu . The entropic criterion overweights rare high-return trajectories, so we make success(reaching the good state) rare by choosing p´ „ e´βH , more precisely: p´ “ We have: VβMu pπq “

1 1 „ e´βH 2pc ` 1q

1 logp1 ` cpp´ ` ∆νπ puqqq β

We chose ∆ so that whenever we have a probability of success νπ puq smaller than 12 the the policy π is ε-suboptimal. When νπ puq ď 1{2, then pMu pπq ď p´ ` ∆{2. So it suffices to enforce 1 1 ` cpp´ ` ∆q 1 ` cpp´ ` ∆q log “ ε ðñ “ eβε β 1 ` cpp´ ` ∆{2q 1 ` cpp´ ` ∆{2q Hence, we must have: ∆“

p3c ` 2qpeβε ´ 1q cpc ` 1qp2 ´ eβε q

Since we have that eβε ă 2c4pc`1q 2 `7c`4 ă 2 by condition 20, the construction is admissible in the sense that 0 ă p´ ă p` ă 1. 45

Essakine Vernade

By this construction, we have for every u P U and every policy π, V Mu pπq ě V Mu ,‹ ´ ε ùñ νπ puq ą

1 2

(22)

Indeed, if νπ puq ď 1{2, then pMu pπq ď p´ ` ∆{2, while the optimal policy achieves p` “ p´ ` ∆. Hence 1 ` cpp´ ` ∆q 1 “ε V Mu ,‹ ´ V Mu pπq ě log β 1 ` cpp´ ` ∆{2q And the contraposition yields the claim (22). Let the algorithm output π̂ at stopping time τ . Define the event Eu “ tνπ̂ puq ą 1{2u By the previous remark and pε, δq-PAC correctness, Pu pEu q ě 1 ´ δ

@u P U

ř Also, since u νπ̂ puq “ 1, at most one u can satisfy νπ̂ puq ą 1{2. Hence the events tEu uuPU are mutually exclusive and in particular under M0 , ÿ P0 pEu q ď 1 uPU

Let Nu pτ q be the number of episodes k ď τ in which the algorithm’s realized triple equals u. Then ÿ Nu pτ q “ τ a.s. uPU

Fix u P U. We apply lemma 17 for the event Eu , the two instances Mu and M0 differ only in the Bernoulli transition at triplet u hence: ˆ ˙ 1 E0 rNu pτ qsdpp´ , p` q ě dpP0 pEu q, Pu pEu qq ě p1 ´ P0 pEu qq log ´ logp2q 1 ´ Pu pEu qq ˆ ˙ 1 ě p1 ´ P0 pEu qq log ´ logp2q δ Where we used the pε, δq-PAC in the last inequality. We sum over u P U: ˜ ¸ ˆ ˙ ˆ ˙ ÿ ÿ 1 1 1 1 E0 rτ s “ E0 rNu pτ qs ě p1 ´ P0 pEu qq log ´ logp2q ě |U| log dpp , p q δ 2dpp , p q δ ´ ` ´ ` uPU uPU Where we used in the final inequality that q2

pp` ´ p´ dpp´ , p` q ď ď pc ` 1q p´ p1 ´ p´ q

1 uPU P0 pEu q ď 1 and the condition δ ď 16 and since:

peβε ´ 1q2

3c`2 2pc`1q

c2 p1 ´ 21 eβε q2

¯2 pc ` 1q peβε ´ 1q2 “ c2 p1 ´ 12 eβε q2

Using the condition eβε ď 16 13 we get: dpp´ , p` q ď

1521 pc ` 1q βε pe ´ 1q2 100 c2 46

3c ` 2 2pc ` 1q

˙2

Entropic Best Policy Identification

Hence:

˘ ` ˆ ˙ 50 c2 H ´ H ´ d LA 1 E0 rτ s ě log βε 2 1521 c ` 1 δ pe ´ 1q

Since the number of leaves is given by L “ p1 ´ 1{AqpS ´ 3q ` 1{A ě S{4 (for A ě 2, S ě 6), and taking H “ H{3 with d ď H{3, we obtain the sample complexity lower bound: ´ 1 E0 rτ s ě 1650

eβpH´H´1q ´ 1 eβpH´H´1q

¯2 SAH log βε pe ´ 1q2

ˆ ˙ 1 δ

Since in the constructed MDP, we only accumulate rewards after H̃ and the optimal policy accumulate rewards across all subsequent steps, we have: Gmax pM0 q “ H ´ H̃ ` 1 “ H ´ H ´ d Hence: ` ˘2 ˆ ˙ SAH 1 1 eβGmax pM0 q ´ 1 log E0 rτ s ě βε 2 βG pM q max 0 1650 δ pe ´ 1q e For β ą 0 (risk-seeking entropic criterion), we choose p´ so that transitioning to the good absorbing state is a rare event. This makes upside tail events hard to detect and estimate, and since the entropic objective overweights favorable rare outcomes, this again leads to larger sample complexity. ´ ¯ 1 1 1 EreβG s “ p1 ´ pM pπqq1 ` pM pπqeβH “ eβH p1 ´ pM pπqqe|β|H ` pM pπq ´ ¯ ˘ 1 1 1 ` “ eβH p1 ´ pM pπqqpe|β|H ´ 1q ` 1 “ eβH p1 ´ pM pπqqc ` 1 And we have the entropic risk measure: V

´ ` ˘¯ ` ˘ 1 1 βH 1 M pπq “ ´ log e p1 ´ p pπqqc ` 1 “ H 1 ´ log p1 ´ pM pπqqc ` 1 |β| |β| 1

Where c “ e|β|H ´ 1. For β ă 0, the entropic criterion is especially sensitive to adverse tail events, so we instead make failure rare by choosing p´ „ 1 ´ e´|β|H , more precisely: p´ “ 1 ´

1 1 „ 1 ´ e´βH 2pc ` 1q

We derive p` similarly to β ą 0 and we find if p` “ p´ ` ∆ then: ∆“

p3c ` 2qpe|β|ε ´ 1q cpc ` 1qpe|β|ε ´ 12 q

Again, since we have e|β|ε ă 11c`8 10c`8 , this construction is admissible in the sense that 0 ă p´ ă p` ă 1. And we prove in the same way that: for every u P U and every policy π, V Mu pπq ě V Mu ,‹ ´ ε ùñ νπ puq ą

1 2

Essakine Vernade

The rest of the argument (change of measure and summing over U goes the same way )and we finally upper bound the kl divergence: ¯2 ´ 3c`2 ˆ ˙ pe|β|ε ´ 1q2 2pc`1q 9pc ` 1q pe|β|ε ´ 1q2 3c ` 2 2 ď dpp´ , p` q ď pc ` 1q c2 2pc ` 1q e2βε c2 pe|β|ε ´ 12 q2 Hence by having a looser constant to match the β ą 0 lower bound: ` ˘2 ˆ ˙ 1 e|β|Gmax pM0 q ´ 1 e2βε SAH 1 E0 rτ s ě log |β|G pM q |β|ε 2 max 0 1650 δ e pe ´ 1q

Appendix D. Experiments For our experiments, We consider a toy MDP that consists of 8-states and two actions, safe and risky. Starting from s0 , safe deterministically walks along the bridge s0 Ñ s1 Ñ s2 Ñ s3 Ñ s4 Ñ s5 Ñ sg , where sg is an absorbing goal state. The risky action attempts shortcuts: from early states it jumps directly to s4 but can fall into an absorbing bad state sb with state-dependent probability (start/mid/final risk); from s4 it makes a final dash to sg that can also fail and transition to sb . Both sg and sb are absorbing and we receive reward 1 in sg for the rest of the horizon. For analogy, think 1 ´ prisk,start 1 ´ prisk,mid

sta r

l na k,fi

isk

,m i

sk,

p ris

pri

all ,da

1 ´ pfall,dash

1 ´ prisk,final

Figure 2: toy MDP. Safe action follows the straight chain to sg ; risky action can shortcut but may fall to sb . safe action is presented by a black edge and risky action by a dashed red edge. of it as a child standing at the top of a long staircase. Taking safe means walking down (or along) the stairs one step at a time, steadily progressing. Taking risky means you try to jump over several steps at once to land much farther ahead saving time, but with some chance of missing the landing and falling into a pit (failure). After the staircase you reach a narrow bridge: safe is crossing it normally, 48

Entropic Best Policy Identification

while risky is a final dash across the bridge, which is faster but again risks falling into the pit. If you make it, you end in the goal; if!you fall, you’re stuck in failure. The ) MDP ! is visualized in the figure ) 2. In our experiments we take prisk,start , prisk,mid , prisk,final , pfall,dash “ 0.95, 0.75, 0.25, 0.85 , we also take ε “ 0.2 and δ “ 0.1 D.1. Sample complexity We study the sample complexity of our method as a function of the risk sensitivity β and the horizon H. In the first sweep, we fix H “ 7 and run the algorithm for β P t2.5, 3.0, 3.5, 4.0, 4.5u until the stopping condition is met. In the second sweep, we fix β “ 0.5 and vary the horizon H P t5, 7, 9, 11, 13, 15, 17u. For each configuration, we run 15 independent trials (different random seeds) and plot the mean stopping time τ ; the y-axis is shown on a log scale. For Figure 4, the

Figure 3: Sample complexity in function of β (log-scale y-axis)

Figure 4: Sample complexity in function of β (log-scale y-axis)

stopping time τ increases sharply as β grows. Moreover, the approximately linear trend on the log-scale y-axis suggests that log τ increases roughly linearly with β, i.e., the sample complexity is consistent with an exponential scaling τ « exppc βq over the tested range. This is in line with the intuition behind the entropic objective, where larger β amplifies tail events and makes BPI more demanding. Interestingly, the effective slope c is not constant across β. We hypothesize that this variation is driven by the χ2 -divergence term χ2 pPπβ , Pπ q discussed in Paragraph 4, which depends on the policy induced at each β. In our sweep, the learned policy changes substantially as β increases, reflecting policy changes as the agent shows increasingly risk-seeking behavior, and then stabilizes around β « 3.5. Beyond this point, further increases in β do not change the policy, which may explain the change in scaling behavior. For Figure 4, we observe a similarly sharp increase in the stopping time τ as the horizon H grows and is roughly linear on the log scale D.2. Regret bounds We now compare our approach to other regret algorithms. At each episode, we evaluate the current policy returned by each algorithm from the initial state s0 . We then compute the cumulative regret

Essakine Vernade

for each algorithm defined by: RpKq “

K ÿ

V ‹ ps0 q ´ V π

k`1

ps0 q

k“1

Where π k`1 is the algorithm returned by the algorithm at the end of episode k. We cap the stopping time at 107 episodes and draw the regret for β P r1.0, 2.0, 3.0, 4.0s. We compare our method to multiple regret algorithms: • RSVI and RSQ from (Fei et al., 2020) • RSVI2 and RSQ2 from (Fei et al., 2021) • UCB Advantage from (Hu and Leung, 2023) • RODI (OTP and PTO variants) and ROVI from (Liang and Luo, 2024) We report the findings of our experiment:

Figure 6: Regret for different algorithms for β “ 2.0

Figure 5: Regret for different algorithms for β “ 1.0

Figures 5, 6, 7, 8 shows that our algorithm consistently achieves the lowest cumulative-regret trajectory over all values of β. Since cumulative regret is computed by evaluating the current policy from the initial state each episode and summing the resulting value gap to optimality, the consistently flatter Entropic BPI curve indicates stronger learning efficiency and performance.

Appendix E. Concentration inequalities E.1. Sanov’s theorem First we introduce the K divergence concentration inequality derived via Sanov’s theorem řm Lemma 19 (High-probability KL bound via Sanov) Let Σm “ tq P Rm ě0 : i“1 qi “ 1u and let p P Σm . Let X1 , . . . , Xn be i.i.d. with law p, and let the empirical distribution ppn be n

ppn piq “

1 ÿ 1tXk “ iu, n k“1 50

i P rms.

Entropic Best Policy Identification

Figure 7: Regret for different algorithms for β “ 3.0

Figure 8: Regret for different algorithms for β “ 4.0

Then for any δ P p0, 1q, with probability at least 1 ´ δ, pm ´ 1q logpn ` 1q ` logp1{δq . n ) ! řm Proof Let Σm “ q P Rm ě0 : i“1 qi “ 1 be the pm´1q-simplex and let p P Σm . Let X1 , . . . , Xn be i.i.d. with law p, and let ppn denote the empirical distribution by pn }pq ď Dpp

1 ÿ ppn piq :“ 1tXk “ iu, n k“1

i P rms

Sanov’s theorem (Theorem 11.4.1 Cover and Thomas (2006)) states that for any set E Ď Σm ´ ¯ ` ˘ Pr ppn P E ď pn ` 1qpm´1q exp ´ n inf Dpq}pq qPE

Fix ε ą 0 and take the set E “ tq P Σm |Dpp||qq ě εu then inf qPE Dpq}pq “ ε and by Sanov’s theorem: ´ ¯ ` ˘ Pr Dpp pn ||pq ě ε ď pn ` 1qm exp ´ nε We turn it to high probability bound by setting the r.h.s to δ which yield: ε“

m logpn ` 1q ` logp1{δq n

Doing a union bound on all state action pairs and all time steps we get that with probability 1 ´ δ we have: pm ´ 1q logpn ` 1q ` logpSAH{δq pn ||pq ď Dpp n

Essakine Vernade

E.2. Concentration inequality for Bernoulli random variables We state a deviation inequality for Bernoulli random variables from Dann et al. (2017)(Lemma F.4): Lemma 20 Let Fi for i “ 1 . . . be a filtration and X1 , . . . Xn be a sequence of Bernoulli random variables with PpXi “ 1|Fi´1 q “ Pi with Pi being Fi´1 -measurable and Xi being Fi measurable. It holds that ˜ ¸ n n ÿ ÿ 1 P Dn : Xt ă Pt {2 ´ logp q ď δ δ t“1 t“1 E.3. Self-normalized Bernstein inequality We state the self-normalized Bernstein-type inequality by (Menard et al., 2021). Lemma 21 Let pYt qtPN‹ , pwt qtPN‹ be two sequences of random variables adapted to a filtration pFt qtPN . We assume that the weights are in the unit interval wt P r0, 1s and predictable, i.e. Ft´1 measurable. We also assume that the random variables Yt are bounded |Yt | ď b and centered ErYt |Ft´1 s “ 0. Consider the following quantities St fi

t ÿ

ws Ys ,

s“1

Vt fi

t ÿ

ws2 ¨ ErYs2 |Fs´1 s,

and

s“1

Wt fi

t ÿ

s“1

and let hpxq fi px ` 1q logpx ` 1q ´ x be the Cramér transform of a Poisson distribution of parameter 1. Then For all δ ą 0: ˆ ˆ ˙ ˙ b|St | 2 P Dt ě 1, pVt {b ` 1qh ě logp1{δq ` logp4ep2t ` 1qq ď δ. Vt ` b2 The previous inequality can be weakened to obtain a more explicit bound: with probability at least 1 ´ δ, for all t ě 1, |St | ď

a 2Vt logp4ep2t ` 1q{δq ` 3b logp4ep2t ` 1q{δq.

E.4. KL-Bernstein inequality We state a KL-Bernstein inequality from (Talebi and Maillard, 2018): Lemma 22 Let p, q P ΣS , where ΣS denotes the probability simplex of dimension S ´ 1. For all α ą 0, for all functions f defined on S with 0 ď f psq ď b, for all s P S, if KLpp, qq ď α then b 2 |pf ´ qf | ď 2Varq pf qα ` bα 3 where we use the expectation operator defined as pf fi Es„p f psq and the variance operator defined as Varp pf q fi Es„p pf psq ´ Es1 „p f ps1 qq2 “ ppf ´ pf q2 .

Entropic Best Policy Identification

Appendix F. Technical results The next lemma introduces the entropic variance under a fixed policy π, defined as the conditional π variance of the exponentiated return eβGh around its entropic value eβQh . It shows that σQπh satisfies a Bellman-style recursion: for each step h and state–action pair ps, aq, σQπh ps, aq decomposes into π 1 (i) the variance under the next-state transition ph p¨ | s, aq of eβprh ps,aq`Vh`1 ps qq and (ii) the expected π next-step entropic variance scaled by e2βrh ps,aq with terminal condition σH`1 Vhπ “ 0. Lemma 23 (Entropic variance recursion) Fix a (deterministic) policy π. «˜ ¸2 ˇ ff ˇ π ps,aq ˇ π π βRh βQπ ps,aq σQh ps, aq “ E e ´e h ˇSh “ s, Ah “ a ˇ π with terminal condition σH`1 ps, aq “ 0 and:

σVhπ psq “ σQπh ps, πpsqq Then, for every h P t1, ..., Hu and ps, aq P S ˆ A, ´ ¯ π π qps, aq σQπh ps, aq “ e2βrh ps,aq VarS 1 „ph p¨|s,aq Zh`1 pS 1 q ` e2βrh ps,aq pph σVh`1

(23)

Proof Fix h P t1, ..., Hu and ps, aq. By definition of Uhπ “ eβQh (exponential entropic Q), we have ” ı π Uhπ ps, aq “ Eπ eβRh | Sh “ s, Ah “ a , ˘ ` π hence σQπh ps, aq “ Var eβRh | Sh “ s, Ah “ a . Since rh ps, aq is deterministic given psh , ah q “ ps, aq, ´ ¯ π π π eβRh “ eβrh ps,aq eβRh`1 ñ σQπh ps, aq “ e2βrh ps,aq Var eβRh`1 | sh “ s, ah “ a Apply the law of total variance w.r.t. Sh`1 : ¯ ı ¯ ” ´ ´ π π Var eβRh`1 | sh “ s, ah “ a “ E Var eβRh`1 | Sh`1 “ sh`1 | Sh “ s, Ah “ a ´ ” ı ¯ π ` Var E eβRh`1 | Sh`1 “ sh`1 | Sh “ s, Ah “ a For the first term, conditioning on Sh`1 “ s1 and following π thereafter gives ´ ¯ π π Var eβRh`1 | Sh`1 “ s1 “ σVh`1 ps1 q so ” ´ ¯ ı “ π ‰ π π pS 1 q “ pph σVh`1 qps, aq E Var eβRh`1 | Sh`1 | Sh “ s, Ah “ a “ ES 1 „ph p¨|s,aq σVh`1 π

1 π ps1 q “ eβVh`1 ps q “ Eπ reβGh`1 | s For the second term, by definition of Zh`1 h`1 “ s s, ´ ¯ ´ ” ı ¯ π Var E eβGh`1 | Sh`1 | Sh “ s, Ah “ a “ VarS 1 „ph p¨|s,aq Zh`1 pS 1 q

Multiplying by e2βrh ps,aq yields ´ ¯ π π σQπh ps, aq “ e2βrh ps,aq VarS 1 „ph p¨|s,aq Zh`1 pS 1 q ` e2βrh ps,aq pph σVh`1 qps, aq as claimed.

Essakine Vernade

Lemma 24 [A normalized variance bound for an exponential transform] Let f : X Ñ r0, Rs and let β P R. Define Y “ eβf pXq Set

m “ emint0,βRu “ mint1, eβR u,

M “ emaxt0,βRu “ maxt1, eβR u.

Then Y P rm, M s a.s., µ P rm, M s, and pe|β|R ´ 1q2 VarpY q ď µ2 4e|β|R Proof If β “ 0 then Y ” 1 and Var “ 0, so assume β ‰ 0. Since f pXq P r0, Rs, we have βf pXq P rmint0, βRu, maxt0, βRus, hence m ď Y “ eβf pXq ď M

a.s.

and therefore µ “ ErY s P rm, M s. By the Bhatia–Davis inequality: VarpY q ď pM ´ µqpµ ´ mq Dividing by µ2 ą 0 yields VarpY q pM ´ µqpµ ´ mq ď 2 µ µ2 Now consider gpµq “

pM ´ µqpµ ´ mq , µ2

µ P rm, M s

Rewrite gpµq “

M ` m Mm ´ 2 ´ 1, µ µ

g 1 pµq “ ´

M ` m 2M m 2M m ´ pM ` mqµ ` “ µ2 µ3 µ3

2M m ‹ ‹ Thus g 1 pµq “ 0 iff µ‹ “ M `m P rm, M s, and g increases on rm, µ s and decreases on rµ , M s. ‹ Hence the maximum is attained at µ . Substituting gives ` ˘ ˘` 2M m 2M m M´M pM ´ mq2 `m M `m ´ m ‹ gpµ q “ “ ` 2M m ˘2 4M m M `m

so for all µ P rm, M s

pM ´ µqpµ ´ mq pM ´ mq2 ď µ2 4M m

Finally, since M {m “ e|β|R ě 1, we have pM ´ mq2 “ 4M m

m ´1 4M m

˘2 “

pe|β|R ´ 1q2 4e|β|R

We state lemma 11 and 12 from (Menard et al., 2021) that are used for the variance transportation: 54

Entropic Best Policy Identification

Lemma 25 Let p, q P ΣS and f is a function defined on S such that 0 ď f psq ď b for all s P S. If KLpp, qq ď α then Varq pf q ď 2Varp pf q ` 4b2 α

and

Varp pf q ď 2Varq pf q ` 4b2 α Lemma 26 For p, q P ΣS , for f, g two functions defined on S such that 0 ď gpsq, f psq ď b for all s P S, we have that Varp pf q ď 2Varp pgq ` 2bp|f ´ g|

and

Varq pf q ď Varp pf q ` 3b }p ´ q}1 , where we denote the absolute operator by |f |psq “ |f psq| for all s P S. We state the pseudo-counts lemma 7 that allows to go from counts to their mean the pseudo-counts and lemma 8 a standard inequality from (Menard et al., 2021) Lemma 27 On event E cnt , for any αp¨, δq such that x ÞÑ βpδ, xq{x is non-increasing for x ě 1, x ÞÑ βpx, δq is non-decreasing @h P t1, ..., Hu, ps, aq P S ˆ A. αpn̄th ps, aqq, δ αpnth ps, aq, δq ^ 1 ď 4 nth ps, aq n̄th ps, aq _ 1

@t P N˚ ,

Lemma 28 For T P N˚ and put qtPN˚ for a sequence where ut P r0, 1s and Ut fi

řt

i“1 ui , we get

T ÿ ut`1 ď 4 logpUT `1 ` 1q. U _1 t“0 t

Finally we state lemma 13 from (Menard et al., 2021) Lemma 29 Let A, B, C, D, E, and α be positive scalars such that 1 ď B ď E and α ě e. If τ ě 0 satisfies a ` ˘ τ ď C τ pA logpατ q ` B logpατ q2 q ` D A logpατ q ` E logpατ q2 (24) then

¯ ´ ? τ ď C 2 pA ` BqC12 ` D ` 2 DC pA ` EqC12 ` 1

where C1 “

` ˘ 8 log 11α2 pA ` EqpC ` Dq 5

Record · ID 180665 · SHA-256 3379464303b0a13b
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.