{'fraction_non_alphanumeric': 0.058594041199711754, 'fraction_numerical': 0.014313048231990656, 'mean_word_length': 4.043107769423559, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 9, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Tightening Exploration in Upper Confidence Reinforcement Learning

The upper confidence reinforcement learning (UCRL2) strategy introduced in (Jaksch et al., 2010) is a popular method to perform regret minimization in unknown discrete Markov Decision Processes under the average-reward criterion. Despite its nice and generic theoretical regret guarantees, this strategy and its variants have remained until now mostly theoretical as numerical experiments on simple environments exhibit long burn-in phases before the learning takes place. Motivated by practical efficiency, we present UCRL3, following the lines of UCRL2, but with two key modifications: First, it uses state-of-the-art time-uniform concentration inequalities, to compute confidence sets on the reward and transition distributions for each state-action pair. To further tighten exploration, we introduce an adaptive computation of the support of each transition distributions. This enables to revisit the extended value iteration procedure to optimize over distributions with reduced support by disregarding low probability transitions, while still ensuring near-optimism. We demonstrate, through numerical experiments on standard environments, that reducing exploration this way yields a substantial numerical improvement compared to UCRL2 and its variants. On the theoretical side, these key modifications enable to derive a regret bound for UCRL3 improving on UCRL2, that for the first time makes appear a notion of local diameter and effective support, thanks to variance-aware concentration bounds.


Introduction
In this paper, we consider Reinforcement Learning (RL) in an unknown and discrete Markov Decision Process (MDP) under the average-reward criterion, when the learner interacts with the system in a single, infinite stream of observations, starting from an initial state without any reset. More formally, let M = (S, A, p, ν) be an undiscounted MDP, where S denotes the discrete state-space with cardinality S, and A denotes the discrete action-space with cardinality A. p is the transition kernel such that p(s |s, a) denotes the probability of transiting to state s , starting from state s and executing action a. We denote by K s,a the set of successor states of the state-action pair (s, a), that is K s,a := {x ∈ S : p(x|s, a) > 0}, and further define K s,a := |K s,a |. Finally, ν is a reward distribution function on [0, 1] with mean function denoted by µ. The interaction between the learner and the environment proceeds as follows. The learner starts in some state s 1 ∈ S at time t = 1. At each time step t ∈ N, where the learner is in state s t , she chooses an action a t ∈ A based on s t as well as her past decisions and observations. When executing action a t in state s t , the learner receives a random reward r t := r t (s t , a t ) drawn independently from distribution ν(s t , a t ), and whose mean is µ(s t , a t ). The state then transits to a next state s t+1 ∼ p(·|s t , a t ), and a new decision step begins. For background material on MDPs and RL, we refer to standard textbooks [2,3].
The goal of the learner is to maximize the cumulative reward gathered in the course of her interaction with the environment. The transition kernel p and reward function ν are initially unknown, and so the learner has to learn them by trying different actions and recording the realized rewards and state transitions. The performance of the learner can be assessed through the notion of regret, which compares the cumulative reward gathered by an oracle, being aware of p and ν, to that gathered by the learner. Following [1], we define the regret of a learning algorithm A after T steps as R(A, T ) := T g − T t=1 r t (s t , a t ), where g denotes the average reward (or gain) attained by an optimal policy. Alternatively, the objective of the learner is to minimize the regret, which calls for balancing between exploration and exploitation.
To date, several algorithms have been proposed in order to minimize the regret based on the optimism in the face of uncertainty principle, originated from the seminal work [4] on stochastic multi-armed bandits. Algorithms designed based on this principle typically maintain confidence bounds on the unknown reward and transition distributions, and choose an optimistic model that leads to the highest average long-term reward. A popular algorithm for the presented RL setup is UCRL2, which was introduced in the seminal work [1]. UCRL2 achieves a non-asymptotic regret upper bound scaling as O(DS √ AT ) with high probability, in any communicating MDP with S states, A actions, and diameter D 1 . [1] also report a regret lower bound scaling as Ω( √ DSAT ), indicating that above regret bound for UCRL2 is rate-optimal, i.e., it has a tight dependence on T , and can only be improved by a factor at most √ DS. Since the advent of UCRL2, several of its variants have been presented in the literature; see, e.g., [5,6,7,8]. These variants mainly strive to improve the regret guarantee and/or empirical performance of UCRL2 by using improved confidence bounds. Although these algorithms enjoy delicate and strong theoretical regret guarantees, their numerical assessment have shown that they typically achieve a bad performance even for state-spaces of moderate size. In particular, they suffer from a long burnin phase before the learning takes place, rendering them impractical for state-spaces of moderate size. It is natural to ask whether the bad empirical performance are due to the main principle of UCRL2 strategies, such as the optimistic principle, or to a not careful enough application of this principle. For instance in a different, episodic and Bayesian framework, PSRL has been reported to significantly improve on UCRL2. In this paper, we answer to this question by showing, perhaps surprisingly, that a simple but crucial modification of UCRL2 that we call UCRL3 significantly outperforms other variants, while preserving (an improving) theoretical guarantees. Though it does not mean optimistic strategies are the best, this shows they can be much stronger competitors than the vanilla UCRL2.
Contributions. We introduce UCRL3, a refined variant of UCRL2, whose design combines the following key elements: First, it uses tighter confidence bounds on components of transition kernel (similarly to [11]) that are uniform in time, a property of independent interest for algorithm design in other RL setups; we refer to Section 3.1 for a detailed presentation. More specifically, for each component of a next-state transition distribution, it uses one time-uniform concentration inequalities for [0, 1]-bounded observations and one for Bernoulli distributions with a Bernstein flavor. The second key design of the algorithm is to adaptively compute an estimate of the support of transition probabilities of various state-action pairs, which is further used to compute a nearoptimistic value and policy (Section 3.2). This step is non-trivial as it requires to consider a Algorithm Regret bound Comment

KL-UCRL [5]
O DS AT log(log(T )/δ) valid for fixed T provided as input.
O D s,a Ks,aT log(T /δ) without knowledge of the span. Figure 1: Regret bounds of state-of-the-art algorithms for average-reward reinforcement learning. Here we used the notation that for x + := max{x, 1}. For KL-UCRL, V s,a denotes the variance of optimal bias function of the true MDP, when the state is distributed according to p(·|s, a).
For UCRL3, L s,a := x∈S p(x|s, a) 1 − p(x|s, a) 2 denotes the local effective support of p(·|s, a).
near-optimistic, as opposed to fully optimistic, in the inner maximization of the Extended Value Iteration (EVI) procedure used in UCRL2. Our adaptive procedure enables to control this additional error. Further, this enables us to make appear in the analysis a notion of local diameter as well as a local effective support (Section 3.3), which in turns reduces the regret bounds. We define the local diameter below.
Definition 1 (Local Diameter of State s) Consider state s ∈ S. For s 1 , s 2 ∈ ∪ a∈A supp(p(·|s, a)) with s 1 = s 2 , let T π (s 1 , s 2 ) denote the number of steps it takes to get to s 2 starting from s 1 and following policy π. Then, the local diameter of MDP M for s, denoted by D local On the theoretical side, we show in Theorem 1 that UCRL3 enjoys a regret bound scaling similarly to that established for the best variant of UCRL2 in the literature as in, e.g., [7]. For better comparison with other works, we make sure to have an explicit bound including small constants for the leading terms. Thanks to a refined and careful analysis that we detail in the appendix, we also improve on the lower-order terms of the regret, that we show should not be overlooked in practice. We provide in Section 4 a detailed comparison of the leading terms involved in several state-of-theart algorithms to help better understand the behavior of these bounds. We also demonstrate through numerical experiments on standard environments that combining these refined, state-of-the-art confidence intervals together with this adaptive support estimation procedure yield a substantial improvement over UCRL2 and its variants. In particular, UCRL3 admits a burn-in phase, which is smaller than that of UCRL2 by an order of magnitude.
Related work. RL under the average-reward criterion dates back to the seminal papers [12] and [13], followed by [14]. Among these studies, for the case of ergodic MDPs, [13] derive an asymptotic MDP-dependent lower bound on the regret, and provide an asymptotically optimal algorithm. Algorithms with finite-time regret guarantees and for a wider class of MDPs are presented in [15,1,16,5,6,8,17,7,18,9]. Among these works, [5] introduces KL-UCRL, which is a variant of UCRL2 that uses the KL divergence to define confidence bounds. Similarly to UCRL2, KL-UCRL achieves a regret of O(DS √ AT ) for the class of communicating MDPs. A more refined regret bound for KL-UCRL for ergodic MDPs is presented in [8]. [16] presents REGAL and report a O(D S √ AT ) regret with high probability in the larger class of weakly communicating MDPs, provided that the learner knows an upper bound D on the span of the bias function of the true MDP. [7] presents SCAL, which similarly to REGAL works for weakly communicating MDPs, but admits an efficient implementation. A similar algorithm called SCAL + is presented in [9]. Both SCAL and SCAL + admit a regret scaling as O D s,a K s,a T . Recently, [18] presents EBF achieving a regret of O √ HSAT assuming that the learner knows an upper bound H on the span of the optimal bias function of the true MDP. 2 However, EBF does not admit a computationally efficient implementation.
We finally mention that some studies consider regret minimization in MDPs in the episodic setting, with a fixed and known horizon; see, e.g., [19,20,11,21,22]. Despite some similarity between the episodic and average-reward settings, the techniques developed in these papers strongly rely on the fixed length of the episode. Hence, the tools in these papers do not directly carry over to the case of undiscounted RL considered here.
In Figure 1, we report the regret upper bounds of algorithms for regret minimization in the average-reward setting. We do not report in this table, REGAL and EBF, as no efficient implementation is known. Let us remark that the presented regret bound for UCRL3 does not contradict the worst-case lower bound Ω( √ DSAT ) of [1]. Indeed, for the hard-to-learn MDP used in the proof of this lower bound in [1], the local and global diameters coincide.
Notations. We introduce some notations that will be used throughout. For a distribution p ∈ ∆ S and a vector-function f = (f (s)) s∈S , we denote P f its application f , defined by P f = E S∼p [f (S)]. Likewise, for p ∈ ∆ S×A S , we define the corresponding operator P such that P f : . For x ∈ R, we let x + := max{x, 1}. Under a given algorithm and for a pair (s, a), we denote by N t (s, a) the total number of observations of (s, a) up to time t. Let us define µ t (s, a) as the empirical mean reward built using N t (s, a) i.i.d. samples from ν(s, a), and p t (·|s, a) as the empirical distribution built using N t (s, a) i.i.d. observations from p(·|s, a).

Background: The UCRLAlgorithm
Before presenting UCRL3 in Section 3, we briefly present the UCRL2 algorithm [1]. To this end, let us introduce the following two sets: , . t,δ (s, a). It then implements the optimistic principle by trying to compute π + t = argmax π:S→A max{g M π : M ∈ M t,δ }, where g M π is the average-gain for policy π in MDP M . This is carried out approximately by EVI that builds a near-optimal policy π + t and an MDP M t such that g Mt We remark that the universal constants of the leading term here are fairly large. max π,M ∈M t,δ g M π − 1 √ t . Finally, UCRL2 does not recompute π + t at each time step. Instead, it proceeds in internal episodes k = 0, . . ., and computes π + t only at the starting time t k of each episode, defined as t 1 = 1 and for all k > 1, where v t 1 :t 2 (s, a) denotes the number of observations of pair (s, a) between time t 1 and t 2 , and where we recall that for x ∈ N, x + := max{x, 1}. The EVI algorithm writes as presented in Algorithm 1.

Algorithm 1 Extended Value Iteration (EVI)
In this section, we introduce the UCRL3 algorithm, a variant of UCRL2 with two main differences: (i) While being a theoretically appealing strategy, UCRL2 suffers from conservative confidence intervals, yielding bad empirical performances. Indeed the random stopping times N t (s, a) are handled using simple union bounds, causing large confidence bounds. The first modification we introduce has thus the same design as UCRL2, but it replaces these confidence bounds with tighter time-uniform concentration inequalities. Further, unlike UCRL2, it does not use L 1 norm to define the confidence bound of transition probabilities p. Rather it defines confidence bounds for each transition probability p(s |s, a), for each pair (s, a), similarly to SCAL or UCRL2B. Indeed one drawback of L 1 confidence bounds is that they require an upper bound on the size of the support of the distribution. Without further knowledge, only S can be provided. In UCRL2, this causes the factor S to appear inside the square-root, due to a union bound over 2 S terms. Deriving L 1 confidence bounds adaptive to the support size seems challenging. In stark contrast, entry-wise confidence bounds can be used without knowing the support: when p(·|s, a) has a support much smaller than S, this may lead to substantial improvement. Hence, the modified strategy UCRL3 relies on time-uniform Bernoulli concentration bounds (presented in Section 3.1 below).
(ii) In order to further tighten exploration, the second idea is to revisit EVI to compute a refined optimistic policy at each round. Indeed, the optimization procedure used in EVI considers all plausible transition probabilities without support restriction, causing unwanted exploration. We introduce a restricted support optimization, where the considered support is chosen adaptively in order to retain near-optimistic guarantees.
We discuss these two modifications below in greater detail.

Confidence Bounds
We now introduce the following high probability confidence set for the mean rewards, where we introduced the notation with σ 2 t (s, a) denoting the empirical variance of the reward function of (s, a) built using the observations gathered up to time t, and where n (δ) = η log log(n) log(ηn) log(η 2 )δ with η = 1.12, 3 and The definition of this confidence set is motivated by Hoeffding-type concentration inequalities for 1/2-sub-Gaussian distributions 4 , modified to hold for arbitrary random stopping time, using the method of mixture (a.k.a. the Laplace method) from [23]. This satisfies by construction that We recall the proof of this powerful result for completeness in Appendix A. Regarding the transition probabilities, we introduce the two following sets: , with g(p) = 1/2−p log(1/p−1) . The first inequality comes from a Bernstein concentration inequalities, modified using a peeling technique in order to handle arbitrary random stopping times. We refer the interested reader to [24] for the generic proof technique behind this result. In [11], the authors used similar proof techniques for Bernstein concentration, however with looser bounds. We discuss this more in Appendix A.3. The last two inequalities are obtained by applying again the method of mixture (a.k.a. the Laplace method) for sub-Gaussian random variables, with a modification: Indeed Bernoulli random variables are not only 1/2-sub-Gaussian, but satisfy a stronger sub-Gaussian tail property, already observed in [25,26]. We discuss this in great details in Appendix A.2. UCRL3 finally considers the set of plausible The confidence level is chosen as δ 0 = δ/(3 + 3S). 5 3 Any η > 1 is valid, and η = 1.12 yields a small bound. 4 Random variables bounded in [0, 1] are 1 2 -sub-Gaussian. 5 When an upper bound K over maxs,a Ks,a is known, one could choose the confidence level δ0 = δ/(3 + 3K).

Near-Optimistic Support-Adaptive Optimization
Last, we revisit the EVI procedure of UCRL2. When computing an optimistic MDP, EVI uses for each pair (s, a) an optimization over the set of all plausible transition probabilities (that is, the distributions q such that q ∈ C t,δ (s, a)). This procedure comes with no restriction on the support of the considered distributions. In the case when p(·|s, a) is supported on a sparse subset of S, this may however lead to computing an optimistic distribution with a large support, resulting in poorer performance. The motivation to revisit EVI is to provide a more adaptive way of handling sparse supports.
LetS ⊂ S, f be a given function (intuitively, the value function u + n at the current iteration step of EVI) and consider the following optimization problem for a specific state-action pair (s, a):

Remark 1 (Optimistic value)
The quantity f s,a ( S) is conveniently defined by an optimization over positive measures whose mass may be less than 1. The reason is that p(S|s, a) ≤ 1 in general. This ensures that p ∈ X indeed holds with high probability, hence f s,a (S) ≥ s ∈S f (s )p(s |s, a) as well.
The original EVI computes f s,a (S) for the function f = u + n at each iteration. When p = p(·|s, a) has a sparse support included inS, C t,δ (s , s, a) often does not reduce to {0} for s / ∈S, while one may prefer to force a solution with a sparse support. A naive way to proceed is to define S as the empirical support (the support of p t (·|s, a)). Doing so, one however solves a different optimization problem than the one using the full set S, which means we may loose the optimistic property ( f s,a (S) ≥ E S∼p(·|s,a) [f (S)] may not hold) and get an uncontrolled error. Indeed, the following decomposition shows that computing an optimistic value restricted onS only upper bounds the first term in the right hand side. The second term (the error term) needs to be upper bounded as well. Provided thatS contains the support of p n , it is easy to see thanks to Bernstein confidence bounds 6 that the first term contains terms scaling with O( 1 √ n ), while the error term contains only terms scaling with O( 1 n ). On the other hand, the error term sums |S \S| many elements, which can be large in case p is sparse, and thus may even exceed f s,a (S) for small n. To ensure the error term does not dominate over the first term we introduce Algorithm 2 that increases the size ofS adaptively. 6 They are of the form p − pn(s ) ≤ a √ p + b where a = Θ(1/ √ n) and b = Θ(1/n). This implies that for s outside of the support of pn, p ≤ a Algorithm 2 NOSS(f, S, C, κ) Input: Target function f , support S of empirical distribution, high probability confidence sets C, parameter κ ∈ (0, 1). 1: Let S = S ∪ argmax s∈S f (s), 2: Define f from (2) using f and confidence sets C. Near-optimistic value iteration In UCRL3 we thus naturally revisit the EVI procedure and replace the following step in EVI with the adaptive support strategy: for a state-action pair (s, a), UCRL3 applies Algorithm 2 to the function u + n − min s u + n (s) (that is, the relative optimistic value function), and empirical distribution p t (·|s, a). We set the value of κ chosen in step n of this modified EVI to The scaling with the size of the support and span of the considered function is intuitive. The reason to further normalize by max s ,a N t (s , a ) 2/3 is to deal with the case when N t (s, a) is small: First, in the case of Bernstein bounds, and sinceS contains at least the empirical support, min f s,a (S), f s,a (S \S) should essentially scale as O( 1 Nt(s,a) ). Hence for pairs such that N t (s, a) is large, κ is redundant. Now for pairs that are not sampled a lot, 1 Nt(s,a) may still be large for large t, resulting in a possibly uncontrolled error. Forcing a max s,a N t (s, a) 2/3 scaling ensures the near-optimality of the solution is preserved with enough accuracy to keep the cumulative regret controlled. This is summarized in the following lemma, whose proof is deferred to Appendix B.

Regret bound of UCRL3
We are now ready to present a finite-time regret bound for UCRL3. Before presenting the regret bound in Theorem 1 below, we introduce the notion of local effective support of a state-action pair. Given a pair (s, a), we define the local effective support L s,a of (s, a) as: In Lemma 4 below we show that L s,a is always controlled by the number K s,a of successor states of (s, a) (the cardinality of the support of p(·|s, a)). The lemma also relates L s,a to the Gini index of the transition distribution of (s, a), defined as G s,a := x∈S p(x|s, a)(1 − p(x|s, a)).
Lemma 4 (Local effective support) For any (s, a): Theorem 1 (Regret of UCRL3) With probability higher than 1 − 4δ, uniformly over all T ≥ 3, s,a D 2 s L s,a + 4 √ SA + 2D. Therefore, the regret of UCRL3 asymptotically grows as    we now discuss the regret bound of UCRL3 with respect to that of UCRL2B. As shown in Table  1

Numerical Experiments
In this section we provide illustrative numerical experiments that show the benefit of the UCRL3 over UCRL2 and some of its popular alternatives.
We conduct numerical experiments to examine the performance of the proposed variants of UCRL2, and compare it to that of state-of-the-art algorithms such as UCRL2, KL-UCRL, and UCRL2B. For all algorithm, we set δ = 0.05 and use the same tie-breaking rule (see Appendix E).
In the first set of experiments, we consider a S-state RiverSwim environment (corresponding to the MDP shown in Figure 4). To better understand Theorem 1 for such environments, we report in Table 1 a computation of some of the key quantities appearing in the regret bounds, as well as the diameter D, for several values of S.
We further provide in Table 2 a computation of the leading terms of several regret analysis. More precisely, for a given algorithm A, we introduce R(A) to denote the regret bound normalized by T log(T /δ) ignoring universal constants. For instance, R(UCRL2) = D √ SA. 7 In Table 2   R(UCRL2B) grows with T unlike R for UCRL2, SCAL + , and UCRL3. Note that even choosing T as small T = 100, and ignoring universal constants (which disadvantage UCRL3), we observe a benefit.
In Figure 3, we plot the regret under UCRL2, KL-UCRL, UCRL2B, and UCRL3 examined in a RiverSwim environment with S = 6 states. The curves show the results averaged over 50 independent runs along with the first and third quantiles. We observe that UCRL3 achieves the smallest regret amongst these algorithms. UCRL3 significantly outperforms UCRL2, KL-UCRL and UCRL2B (note the logarithmic scale). Figure 4 shows similar results on larger 25-state Riverswim environment; On this environment, UCRL2 only start learning after close to 10 7 time steps. We further provide results in larger MDPs. We consider two frozen lake environments of respective size 7 × 7 and 9 × 11 as shown in Figure 5, yielding MDPs with A = 4 actions and S = 20 states (respectively S = 55 )when taking off walls. In such grid-worlds the learner starts in the upper-left corner. A reward of 1 is placed in the lower-right corner, when this rewarding state is reached, the learner is sent back to the initial state. The learner can perform 4 actions: Going up, left, down, or right, there are probabilities of 0.1 to stay in the same state, and 0.1 to go in each of the two perpendicular directions (or stay if this leads to a wall), giving a 0.7 probability to go in the chosen direction.
Remark 2 Importantly, UCRL2 and its variants are generic purpose algorithms, and as such are not aware of the specific structure of the MDP, such as being a grid-world. In particular, no prior knowledge is assumed on the support of the transition distributions by any of the algorithms, which makes it a highly non trivial learning task, since the number of free variables (dimension) is then S 2 A (SA(S − 1) for the transition function, and SA for the rewards). For instance a 4-room MDP is really seen as a problem of dimension 1600 by these algorithms, and a 2-room MDP as a problem of dimension 12100.

Figures 6 (respectively 7)
show the regret performance of UCRL2, KL-UCRL, UCRL2B, and UCRL3 on these 2-room (respectively 4-room) grid-worlds MDPs. The full code and implementation details is made available to the community. Finally, since all these algorithms are generic-purpose MDP learners, we provide numerical experiments in a large randomly-generated MDP consisting of 100 states and 3 actions, hence seen as being of dimension 3.10 4 . UCRL3 still outperforms other state-of-the-art strategies by a large margin consistently in all these environments. We provide below, an illustration of a randomly-generated MDP, with 15 states and 3 actions (blue, red, green). Such an MDP is a type of Garnet (Generalized Average Reward Non-stationary Environment Test-bench) [27], in which we can specify the number of states, actions, average size of the support of transition distributions, sparsity of the reward function, as well as the minimal non-zero probability mass and minimal non-zero mean-reward.
Lemma 5 (Uniform confidence intervals) Let Y 1 , . . . , Y t be a sequence of t i.i.d. real-valued random variables with mean µ, such that Y t − µ is σ-sub-Gaussian.
(The "Laplace" method refers to using the Laplace method of integration for optimization)

Proof of Lemma 5:
Proof (of Lemma 5). We introduce for a fixed δ ∈ (0, 1) the random variable This quantity is a random stopping time for the filtration F = (F t ) t , where F t = σ(Y 1 , . . . , Y t ), since {τ ≤ m} is F m -measurable for all m. We want to show that P(τ < ∞) ≤ δ. To this end, for any λ, and t, we introduce the following quantity: By assumption, the centered random variables are σ-sub-Gaussian and it is immediate to show that {M λ t } t∈N is a non-negative super-martingale that satisfies ln E[M λ t ] ≤ 0 for all t. It then follows that M λ ∞ = lim t→∞ M λ t is almost surely well-defined and so is M λ τ . Further, using the fact that M λ t and {τ > t} are F t measurable, it comes The next step is to introduce the auxiliary variable Λ ∼ N (0, σ −2 ), independent of all other variables, and study the quantity Note that the standard deviation of Λ is σ −1 due to the fact we consider σ-sub-Gaussian random variables. We immediately get Thus, we deduce that We conclude by applying a simple Markov's inequality:

A.2 Time-Uniform Laplace Concentration for Bernoulli Distributions
We now want to make use of the special structure of Bernoulli variables to derive refined timeuniform concentration inequalities. Let us first recall that if (X i ) i≤n are i.i.d. according to a Bernoulli B(p) with parameter p ∈ [0, 1], then it holds by the Chernoff-method that for all ε ≥ 0, where kl(p, q) = p log(p/q)+(1−p) log((1−p)/(1−q)) denotes the Bernoulli Kullback-Leibler divergence. The reverse map of the Cramér transform ε → kl(p + ε, p) is unfortunately not explicit, and one may consider Taylor's approximation of it to derive approximate but explicit highprobability confidence bounds. More precisely, the following has been shown (see [28,29,25,26]): Lemma 6 (Sub-Gaussianity of Bernoulli random variables) For all p ∈ [0, 1], the left and right tails of the Bernoulli distribution are controlled in the following way where g(p) = 1/2−p log(1/p−1) . The control of the right-tail can be further refined when p ∈ [ 1 2 , 1], as follows: We note that the left and right tails are not controlled in a symmetric way. This yields, introducing , the following asymmetrical confidence set

Proof of Corollary 1:
Let us introduce for each λ the following quantities Note that M λ t is a non-negative super-martingale for all λ ∈ R + , and M λ t is a non-negative super-martingale for all λ ∈ R.
Note also that M t is still a non-negative super-martingale satisfying E[M t ] ≤ 1 for all t. Likewise, considering Λ to be a random variable with density M t is a non-negative super-martingale satisfying E[M t ] ≤ 1 for all t. Thus, we deduce that Combining the previous steps, we thus obtain for each δ ∈ (0, 1),

A.3 Comparison of Time-Uniform Concentration Bounds
In this section, we give additional details about the concentration inequalities used to derive the confidence bounds in UCRL3.
In order to obtain the confidence bound in the Bernstein form we simply resort to the generic peeling approach from [24], that we apply to sub-Gamma concentration. More precisely, using the notation therein, this corresponds to a direct application of the method, using the function ϕ −1 ,+ (z) = 2q(1 − q)z + z/3 classically used to derive Bernstein inequality for bounded random variables; see, e.g., [30].
In [11], the authors introduce an alternative time-uniform Bernstein bound. In order to compare the methods, we introduce the following two functions where n (δ) = 2 log log(max(e, n)) + log(3/δ) where n (δ) = η log log(n) log(ηn) log(η 2 )δ with η = 1.12 . Figure 10 plots the ratio r(p, n, δ) = C Bernstein-M (p, n, δ)/C Bernstein-D (p, n, δ) as a function of n for different values of p and for the fixed value δ = 0.01. This shows the clear advantage of using the considered technique over that of [11].   Figure 11: Plot of n → r(p, n, δ) for several values of p, with δ = 0.01. We put the constant line (1) for reference: above this line, the Laplace bound is less tight than the Bernstein bound, while below this line, the Gaussian Laplace bound is sharper. Left: using the first Bernstein bound, Right: using the second Bernstein bound.
In order to better understand the benefit of using a sub-Gaussian tail control for Bernoulli, we further introduce the following function and lot in Figure 11 the ratio r(p, n, δ) = C ex-Gaussian-Laplace (p, n, δ)/C e-Bernstein-peeling (p, n, δ) as a function of n for different values of p and for the fixed value δ = 0.01. It shows that up to 10 2 samples (for one state-action pair) (6) is sharper than (4) for p > 0.005. Hence this justifies using (6) in practice.

B Extended Value Iteration
Proof of Lemma 2: By the previous discussion, we have that where the first inequality holds with high probability by Remark 1 and the second one is guaranteed by the stopping rule of Algorithm 2. Indeed, Algorithm 2 by construction builds a minimal setS that contains the empirical support S n (plus eventually one point), and satisfies the condition f (S \S) < min κ, f (S) required to exit the loop.

Proof of Lemma 3:
Let us denote by an optimal policy. Let g : S → R denote the constant function equal to g , and κ t the constant function equal to κ t . Using vector notations, we have on the one hand On the other hand, for the MDP computed by the modified EVI procedure, it holds Hence, combining these two results, we obtain that with probability higher than 1 − δ, C Regret Analysis of UCRL3: Proof of Theorem 1 In this section, we prove Theorem 1. Our proof follows similar lines as in the proof of [1, Theorem 2].
We first provide the following time-uniform concentration inequality to control a bounded martingale difference sequence, which follows from Lemma 5: Corollary 2 (Time-uniform Azuma-Hoeffding) Let (X t ) t be a martingale difference sequence such that for all t, X t ∈ [a, b] almost surely for some a, b ∈ R. Then, for all δ ∈ (0, 1), it holds P ∃T ∈ N : Proof of Theorem 1: Let δ ∈ (0, 1). To simplify notations, we define the short-hand J k := J t k for various random variables that are fixed within a given episode k and omit their dependence on δ (for example Introducing ∆ k := s,a ν k (s, a) g − µ(s, a) for 1 ≤ k ≤ m(T ), we get with probability at least 1 − δ. A given episode k is called good if M ∈ M k (that is, the set of plausible MDPs contains the true model), and bad otherwise.
Control of the regret due to bad episodes. By Lemma 1, for all T , and for all episodes k = 1, . . . , m(T ), the set M k contains the true MDP with probability higher than 1 − δ. As a consequence, with probability at least 1 − δ, Control of the regret due to good episodes. To upper bound regret in good episodes, we closely follow [1] and decompose the regret to control the transition and reward functions. Consider a good episode k (hence, M ∈ M k ). By choosing π + k and M k , using Lemma 3, we get that where κ k = γS(u k )K maxs,a N k (s,a) 2/3 . Hence, with probability greater than 1 − δ, Using the same argument as in the proof of [1, Theorem 2], the value function u (i) k computed by EVI-NOSS at iteration i satisfies: max s u Using the Bellman operator on the optimistic MDP: Defining g k = g k 1, µ k := µ k (s, π + k (s)) s , P k := p k s |s, π + k (s) s,s and ν k := ν k s, π + k (s) s , we can rewrite the above inequality as: Combining this with (7) yields Similarly to [1], we define w k (s) := u k (s)) for all s ∈ S. Then, in view of the fact that P k is row-stochastic, we obtain The second term in the right-hand side can be upper bounded as follows: where we have used 1 ≤ N k (s, a) ≤ T and S ≥ 2 in the last inequality. Furthermore, using t k ≥ max s,a N k (s, a) and S(u k ) ≤ D yields s,a ν k (s, a) Putting together, we obtain In what follows, we derive an upper bound on ν k ( P k − I)w k . Similarly to [1], we consider the following decomposition: .
The following lemmas provide upper bounds on L 1 (k) and L 2 (k): Lemma 7 Consider a good episode k. Then, Lemma 8 For all T , it holds with probability at least 1 − δ, Applying Lemmas 7 and 8, and summing over all good episodes, we obtain the following bound that holds with probability higher than 1 − 2δ, uniformly over all T ∈ N: To simplify the above bound, we provide the following lemma: Lemma 9 We have: Putting everything together, it holds that with probability at least 1 − 4δ, Noting that for S, A ≥ 2, it is easy to verify that for T ≥ 3, T δ 6S 2 A ≤ 2 log 6S 2 A √ T + 1/δ . Hence, after simplification we obtain that for all T ≥ 3, with probability at least 1 − 4δ, Finally we remark that
Fix s and a, and introduce short-hands p k := p k (·|s, a), p k := p k (·|s, a), and p := p(·|s, a). We have To upper bound F 1 , we first show that max x∈supp( p k (·|s,a)) |w k (x)| ≤ Ds 2 . To show this, we note that similarly to [1], we can combine all MDPs in M k to form a single MDP M k with continuous action space A . In this extended MDP, in each state s ∈ S, and for each a ∈ A, there is an action in A with meanμ(s, a) and transitionp(·|s, a) satisfying (1). Similarly to [1], we note that u (i) k (s) amounts to the total expected i-step reward of an optimal non-stationary i-step policy starting in state s on the MDP M k with extended action set. The local diameter of state s of this extended MDP is at most D s , since by assumption k is a good episode and hence M k contains the true MDP M , and therefore, the actions of the true MDP are contained in the continuous action set of the extended MDP M k . Now, if there were states s 1 , s 2 ∈ ∪ a supp( p k (·|s, a)) with u k (s 2 ) > D s , then an improved value for u (i) k (s 1 ) could be achieved by the following non-stationary policy: First follow a policy which moves from s 2 to s 2 most quickly, which takes at most D s steps on average. Then follow the optimal i-step policy for s 2 . We thus have u k (s 2 ) − D s , since at most D s of the i rewards of the policy for s 2 are missed. This is a contradiction, and so the claim follows. Using a similar argument yields: max x∈supp(p(·|s,a)) |w k (x)| ≤ Ds 2 . To upper bound F 1 , noting that k is a good episode yields: where we have used that w k ∞ ≤ D 2 and max x∈Ks,a |w k (x)| ≤ Ds 2 . To upper bound F 2 , we will need the following lemma: Lemma 10 Consider x and y satisfying |x − y| ≤ 2y(1 − y)ζ + ζ/3. Then, Applying Lemma 10 twice and using the relation max x∈supp( p k (·|s,a)) |w k (x)| ≤ Ds 2 yield: Combininig the bounds on F 1 and F 2 , and noting that Proof of Lemma 10: By Taylor's expansion, we have Using the fact that a ≤ b √ a + c implies a ≤ b 2 + b √ c + c for nonnegative numbers a, b, and c, we get where we have used √ a + b ≤ √ a + √ b valid for all a, b ≥ 0. Taking square-root from both sides and using the latter inequality give the desired result:

Proof of Lemma 8:
Similarly to the proof of [1, Theorem 2], we define the sequence (X t ) t≥1 with X t := (p(·|s t , a t ) − e s t+1 )w k(t) I{M ∈ M k(t) }, for all t, where k(t) denotes the episode containing step t. For any k with M ∈ M k , we have that: so that m(T ) k=1 L 2 (k) ≤ T t=1 X t + m(T )D. Using w k ∞ = D 2 and applying the Hölder inequality give |X t | ≤ p(·|s t , a t ) − e s t+1 1 D 2 ≤ p(·|s t , a t ) 1 + e s t+1 1 D 2 = D .
Hence, we deduce that with probability at least 1 − δ, the result holds.

C.2 Proof of Supporting Lemmas
Proof of Lemma 9: Inequalities (i)-(iii) easily follow by applying Lemma 11, which is stated at the end of this proof, and using Jensen's inequality. Next we prove the inequality (iv). where we have used that for any L ≥ 1, L j=1 j −2/3 ≤ 1 + L 1 z −2/3 dz ≤ 3 2 L 1/3 , and where the last step follows from Jensen's inequality.

D Other Technical Lemmas
Proof of Lemma 4: The notion of local effective support could be related to Gini index of the transition distribution of (s, a) as follows. Given pair (s, a), let us introduce the Gini index G s,a := x∈S p(x|s, a)(1− p(x|s, a)). Given ε > 0, we introduce K ε s,a := {x ∈ S : p(x|s, a)(1 − p(x|s, a)) ≥ ε}, of cardinality K ε s,a . We have that L s,a ≤ min ε≥0 K ε s,a G s,a + K s,a where we have used the Cauchy-Schwarz inequality. Taking the infimum over ε ≥ 0 yields Note that the inequality above implies L s,a ≤ K s,a G s,a . Furthermore, In view of the concavity of z → x∈S z(x)(1−z(x)), the maximal value of G s,a is achieved when p(x|s, a) = 1 Ks,a for x ∈ K s,a . Hence, G s,a ≤ 1 − 1 Ks,a . Therefore, L s,a ≤ K s,a G s,a ≤ K s,a − 1 .

E Further Details for Experiments
Tie-breaking rule to compute optimistic policies All the considered algorithms ( UCRL2, KL-UCRL, UCRL2B, UCRL3) resort to a form of EVI internal procedure, that computes at each iteration n a policy π + n maximizing the current optimistic value u + n (see Algorithm 1). In practice, several policies may satisfy this, hence a tie-breaking rule is required. For fairness, we used the same tie-breaking rule for all algorithms. It consists, for a state s, to break ties by defining the policy to choose an action uniformly randomly amongst Argmin a∈A N k (s, a). Such breaking rules end to stabilize the algorithm.
Atypical sequences The concentration inequalities we have employed for UCRL3, are mostly tight. Unfortunately, concentration inequalities are also known to be loose in the specific case of atypical sequences of observations. Namely, the specific situation when n = N t (s, a) > 1 and all observed samples from s, a equal s 0 , corresponds to observing a sequence of n ones from a Bernoulli distribution with parameter θ = p(s 0 |s, a). Note that for n i.i.d. observations, this event should be of probability θ n . In such a situation when p t (s 0 |s, a) = 1, all concentration inequalities yield conservative lower bounds on p(s 0 |s, a). We replace these lower bounds with (1/2) n for this very specific situation.