Achieving Tractable Minimax Optimal Regret in Average Reward MDPs

Authors: victor  boone
zihan  zhang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 10:17:24

Abstract: In recent years, significant attention has been directed towards learning average-reward Markov Decision Processes (MDPs).
However, existing algorithms either suffer from sub-optimal regret guarantees or computational inefficiencies.
In this paper, we present the first *tractable* algorithm  with minimax optimal regret of $\mathrm{O}\left(\sqrt{\mathrm{sp}(h^*) S A T \log(SAT)}\right)$ where $\mathrm{sp}(h^*)$ is the span of the optimal bias function $h^*$, $S\times A$  is the size of the state-action space and $T$ the number of learning steps. 
Remarkably, our algorithm does not require prior information on $\mathrm{sp}(h^*)$. 

Our algorithm relies on a novel subroutine, **P**rojected **M**itigated **E**xtended **V**alue **I**teration (`PMEVI`), to compute bias-constrained optimal policies efficiently. 
This subroutine can be applied to various previous algorithms to obtain improved regret bounds.

Main paper: 
 introduction: 
 Reinforcement learning (RL) Burnetas and Katehakis [1997] , Sutton and Barto [2018] has become a popular approach for solving complex sequential decision-making tasks and has recently achieved notable advancements in diverse fields of application. RL problems are generally formulated with Markov Decision Processes (MDPs) Puterman [1994] , where a learning agent seeks to maximize the rewards that are gathered by interacting with an unknown environment.This paper focuses on average reward MDPs where the learning agent must maximize the sum of rewards in the long run without any reset mechanism. In this setting, the proper balancing between exploration (i.e., playing sub-optimally to learn the unknown environment) and exploitation (i.e., planning optimally according to the current knowledge), usually known as the exploration-exploitation trade-off, is key to learn efficiently. The measure of learning performance that we adopt throughout is the regret, that compares the aggregate rewards collected by the learning agent during the learning process to the expected performance of an omniscient agent that knows everything in advance. The seminal work of Auer et al. [2009] provides a minimax regret lower bound of Ω √ DS AT , where D is the diameter (the maximal distance between two different states), S the number of states, A the number of actions and T the learning horizon. They also provide an algorithm achieving regret O √ D 2 S 2 AT , where O(-). Ever since Auer et al. [2009] , many works have been devoted to close the gap between the regret lower and upper bounds in the average reward setting Auer et al. [2009] , Bartlett and Tewari [2009] , Filippi et al. [2010] , Talebi and Maillard [2018] , Fruit et al. [2018 Fruit et al. [ , 2020]] , Bourel et al. [2020] , Zhang and Ji [2019] , Ouyang et al. [2017] , Agrawal and Jia [2023] , δ with probability 1 -26δ. Moreover, if PMEVI-DT runs with the same confidence regions that UCRL2 Auer et al. [2009] on a communicating environment, it has a time complexity O(DS 3 AT ).Taking δ = √ 1/T , we also obtain a O sp (h * )S AT regret bound in expectation. The geometry of the prior bias region H * that PMEVI-DT can support is discussed later (see Assumption 4). It can be taken trivial with H * = R S to obtain a completely prior-less algorithm.To the best of our knowledge, PMEVI-DT is the first tractable algorithm with minimax optimal regret bounds (up to logarithmic factors). The algorithm does not necessitate any prior knowledge of sp (h * ), thus circumventing the potentially high cost associated with learning sp (h * ). On the technical side, a key novelty of our method is the subroutine named PMEVI (see Algorithm 2) that improves and can replace EVI Auer et al. [2009] in any algorithm that relies on it Auer et al. [2009] , Fruit et al. [2018] , Filippi et al. [2010] , Fruit et al. [2020] , Bourel et al. [2020] to boost its performance and achieve minimax optimal regret. Related works on average reward MDPs. For communicating MDPs, the notable work of Auer et al. [2009] proposes the famous UCRL2 algorithm, a mature version of their prior UCRL Auer and Ortner [2006] , achieving a regret bound of O(DS √ AT ). This paper pioneered the use optimistic methods to learn MDPs efficiently. A line of papers Filippi et al. [2010] , Fruit et al. [2020] , Bourel et al. [2020] developed this direction by tightening the confidence region that UCRL2 relies on, and sharpened the analysis through the use of local properties of MDPs, such as local diameters and local bias variances. However, none of these works went beyond regret guarantees of order S Table 1 : Comparison of related works on RL algorithms for average-reward MDP, where S × A is the size of state-action space, T is the total number of steps, D (D s ) is the (local) diameter, sp (h * ) ≤ D is the span of the bias vector, t mix is the worst-case mixing time, t hit is the hitting time (i.e., the expected time cost to visit some certain state under any policy).Infinite-horizon MDP. An element M ∈ M is a tuple (S, A, p, r) where p is the transition kernel and r the reward function. The random state-action pair played by the agent at time t is denoted X t ≡ (S t , A t ), and the achieved reward is R t . A policy is a deterministic rule π : S → A and we write Π the space of policies. When coupled with a MDP M ∈ M, a policy properly defines the distribution of (X t , R t ) whose associated probability probability and expectation operators are denoted P π s , E π s , where s ∈ S is the initial state. Under M, a fixed policy has a reward function r π (s) := r(s, π(s)), a transition matrix P π , a gain g π (s) := lim 1 T E π s [R 0 + . . . + R T -1 ] and a bias h π (s) := Cesàro-lim E π s [ T -1 t=0 (R t -g(S t))], that all together satisfy the Poisson equation h π + g π = r π + P π h π , see Puterman [1994] . The Bellman operator of the MDP is:Lu(s) := max a∈A(s){r(s, a) + p(s, a)u}(1)The optimal gain is g * (s) := max π g π (s) and the optimal bias is h * (s) := max {h π (s) : π s.t. g π = g * }.Weakly-communicating MDPs. M is weakly-communicating Puterman [1994] , Bartlett and Tewari [2009] if the state space can be divided into two sets: (1) the transient set, consisting in states that are transient under all policies;(2) the non-transient set, where every state is reachable starting from any other non-transient state. In this case, h * is a span-fixpoint of L (see Puterman [1994] ), i.e., Lh *h * ∈ Re where e is the vector full of ones. We write h * ∈ Fix(L). Then g * = Lh *h * and every policy π satisfies r π + P π h * ≤ g * + h * . We accordingly define the Bellman gaps: ∆ * (s, a) := h * (s) + g * (s)r(s, a)p(s, a)h * ≥ 0.(2)Another important concept is the diameter, that describes the maximal distance from one state to another state. It is given by D := sup s s ′ inf π E π s [inf {t ≥ 1 : S t = s ′ }]. An MDP is said communicating if its diameter D is finite, in which case sp(h * ) ≤ sp(r)D, see Bartlett and Tewari [2009] , Fruit [2019] , where sp(-) is the span function given by sp (u) := max(u)min(u).Reinforcement learning. The learner is only aware that M ∈ M but doesn't have a clue about what M further looks like. From the past observations and the current state S t , the agent picks an available action A(S t ), receives a reward R t and observe the new state S t+1 . The regret of the agent is:EQUATIONIts expected value satisfies E[Reg(T )] = E[ T -1 t=0 ∆ * (X t )] + E[h * (S 0 )h * (S T )] and the quantity T -1 t=0 ∆ * (X t ) will be referred to as the pseudo-regret. This paper focuses on minimax regret guarantees. Specifically, for c ≥ 1, denote M c := M ∈ M : ∃h * ∈ Fix(L(M)), sp (h * ) ≤ c the set of weaklycommunicating MDPs that admit a bias function with span at most c. Following Auer et al. [2009] , every algorithm A, for all c > 0, we have maxEQUATION)The goal of this work is to reach this lower bound with a tractable algorithm.3 Algorithm PMEVI-DTThe algorithm PMEVI-DT that we present in this work is actually a general method can be applied to improve various existing algorithms Auer et al. [2009] , Filippi et al. [2010] , Fruit et al. [2018] , Bourel et al. [2020] , Tewari and Bartlett [2007] . All these algorithms work episodically, by maintaining a policy π k that drives play during a time-window {t k , . . . , t k+1 -1} called an episode. An episode rule determines when π k should be considered obsolete and defines the time t k+1 at which the policy is renewed. To compute π k , these algorithms follow the optimism-in-face-of-certainty (OFU) design principle, by choosing π k that achieves the largest possible gain that is plausible under their current information. This is done by building a confidence region M t ⊆ M for the hidden model M, then searching for a policy π solving the optimization problem:g * (M t ) := sup g π (M t ) : π ∈ Π, sp (g π (M t )) = 0 with g π (M t ) := sup g π ( M) : M ∈ M t .(5)The design of the confidence region M t varies from a work to another. Given a confidence region (M t ) t≥0 , OFU-algorithms work as follows: At the start of episode k, the optimization problem ( 5) is solved, and its solution π k is played until the end of episode. The duration of episodes can be managed in various ways, although the most popular is arguably the doubling trick (DT), that essentially waits until a state-action pair is about to double the visit count it had at the beginning of the current episode (see Algorithm 1).Notations. In the rest of this section, we use pt (s, a) (and rt (s, a)) to denote the empirical transition (and reward) of the latest doubling update before the t-th step, and further denote Mt := (r t , pt ).Extended Bellman operators and EVI. To solve (5) efficiently, the celebrated work Auer et al. [2009] introduce the extended value iteration algorithm (EVI), that can be run whenever M t is a (s, a)-rectangular confidence region, meaning that M t ≡ s,a (R t (s, a) × P t (s, a)) where R t (s, a) and P t (s, a) are respectively the confidence region for r(s, a) and p(s, a) after t learning steps. EVI is the algorithm computing the sequence defined by:v i+1 (s) ≡ L t v i (s) := max a∈A(s) max r(s,a)∈R t (s,a) max p(s,a)∈P t (s,a) (r(s, a) + p(s, a) • v i ) (6)until sp (v i+1v i ) < ϵ where ϵ > 0 is the numerical precision. When the process stops, it is known that any policy π such that π(s) achieves L t v i in (6) satisfies g π (M t ) ≥ g * (M) -ϵ, hence is nearly optimistically optimal. This process gets its name from the observation that L t is the Bellman operator of M t seen as a MDP, hence EVI is just the Value Iteration algorithm Puterman [1994] ran in M t . A choice of action from s ∈ S in M t consists in (1) a choice of action a ∈ A(s), (2) a choice of reward r(s, a) ∈ R t (s, a) and (3) a choice of transition p(s, a) ∈ P t (s, a); It is an extended version of A(s).Towards Projected Mitigated EVI. Obviously, the regret of an OFU-algorithm is directly related to the quality of the confidence region M t . That is why most previous works tried to approach the regret lower bound √ DS AT of Auer et al. [2009] by refining M t . The older works of Auer et al. [2009] , Bartlett and Tewari [2009] , Filippi et al. [2010] have been improved with a variance aware analysis Talebi and Maillard [2018] , Fruit et al. [2018 Fruit et al. [ , 2020]] , Bourel et al. [2020] that essentially make use of tightened kernel confidence regions P t . While all these algorithms successively reduce the gap between the regret upper and lower bounds, they fail to achieve optimal regret √ DS AT . Meanwhile, the EBF algorithm of Zhang and Ji [2019] is minimax optimal but (1) the algorithm is intractable because it relies on an oracle to retrieve optimistically optimal policies and (2) needs prior information on the bias function. Nonetheless, the method of Zhang and Ji [2019] strongly suggests that inferring bias information from the available data is key to achieve minimax optimal regret. Rather surprisingly and in opposition to this previous line of work, our work suggests that the choice of the confidence region M t has little importance. Instead, our algorithm takes an arbitrary (wellbehaved) confidence region in, infer bias information similarly to Zhang and Ji [2019] and makes use of it to refine the extended Bellman operator (6) associated to the input confidence region. Our algorithm can further take arbitrary prior information (possibly none) on the bias vector to tighten its bias confidence region. The pseudo-code given in Algorithm 1 is the high level structure our algorithm PMEVI-DT. In the next Section 3.1, we explain how ( 6) is refined using bias information.Algorithm 1: PMEVI-DT(H * , T, t → M t ) Parameters: Bias prior H * , horizon T , a system of confidence regions t → M t 1: for k = 1, 2, . . . do 2:Set t k ← t, update confidence region M t ;3:H ′ t ← BiasEstimation(F t , M t , δ):4: H t ← H * ∩ {u : sp (u) ≤ T 1/5 } ∩ H ′ t ; 5: Γ t ← BiasProjection(H t , -); 6: β t ← VarianceApprox(H ′ t , F t ); 7: h k ← PMEVI(M t ,until (DT) N t (S t , π k (S t )) ≥ 1 ∨ 2N t k (X t ). 14: end for Algorithm 2: PMEVI(M, β, Γ, ϵ) Parameters: region M, mitigation β, projection Γ, precision ϵ, initial vector v 0 (optional) 1: if v 0 not initialized then set v 0 ← 0; 2: n ← 0 3: L ← extended operator associated to M; 4: repeat 5: v n+ 1 2 ← L β v n ; 6: v n+1 ← Γv n+ 1 2 ; 7: n ← n + 1; 8: until sp (v n -v n-1 ) < ϵ 9: return v n .Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: We claim that the algorithm reaches minimax optimal regret, and it does.We claim that our algorithm can effectively use bias information, and the experimental illustration supports the claim.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
limitations: 
 Question: Does the paper discuss the limitations of the work performed by the authors?Answer: [NA] Justification: The paper is a theoretical one that covers all weakly communicating MDPs, and although it may help the design of algorithms intended to be applicable in real-life scenarios, our method is not meant to be directly applied.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
projected mitigated extended value iteration (pmevi): 
 Assume that an external mechanism provides a confidence region H t for the bias function h * . Provided that M t is correct (M ∈ M t ) and that H t is correct (h * ∈ H t ), we want to find a policy-model pair (π, M) that maximizes the gain among pairs with h π ( M) ∈ H t . This is done with an improved version of (6) combining two ideas, that are both necessary to achieve minimax optimal regret in the analysis.1. Projection (Section 3.2). Whenever it is correct, the bias confidence region H t informs the learner that the search of an optimistic model can be constrained to those with bias within H t . This is done by projecting L β t (see mitigation) using an operator Γ t : R S → H t , that has to satisfy a few non-trivial regularity conditions that are specified in Proposition 2. 2. Mitigation (Section 3.3). When one is aware that h * ∈ H t , the dynamical bias update p(s, a)v i in (6) can be controlled better, by trying to restrict (6) to the p(s, a) such that p(s, a)v i ≤ pt (s, a)v i + (p(s, a)pt (s, a))v i with the knowledge that v i ∈ H t . However, controlling the error (p(s, a)pt (s, a))v i by doing a union-bound on all possible values of v i is equivalent to building a confidence region for p(s, a), which produces an extra S 1/2 in the error term that cannot be afforded by a minimax optimal algorithm. We take a different approach instead. For a fixed u ∈ R S , the empirical Bernstein inequality (Lemma 38) provides a variance bound of the form ( pt (s, a)p(s, a))u ≤ β t (s, a, u). By estimating β t (s, a) := max u∈H t β t (s, a, u), the search makes sure that ( pt (s, a)p(s, a))u ≤ β t (s, a) holds with high probability for u = h * , even though h * is unknown. For β ∈ R X + , we introduce the β-mitigated extended Bellman operator:L β t u(s) := max a∈A(s) sup r(s,a)∈R t (s,a) sup p(s,a)∈P t (s,a) r(s, a) + min { p(s, a)u i , pt (s, a)u i + β(s, a)} (7)The mitigation β(s, a) is independent of u, which is crucial for L β t to be well-behaved.The proposition below shows how well-behaved the composition L t := Γ t • L β t is. Its proof requires to build a complete analysis of projected mitigated Bellman operators. This is deferred to the appendix.Proposition 2. Fix β ∈ R X + and assume that there exists a projection operator Γ t : R X → H t which is (O1) monotone: u ≤ v ⇒ Γu ≤ Γv; (O2) non span-expansive: sp (Γu -Γv) ≤ sp (uv); (O3) linear: Γ(u + λe) = Γu + λe and (O4) Γu ≤ u. Then, the projected mitigated extended Bellman operatorL t := Γ t • L βt has the following properties:(1) There exists a unique g t ∈ Re such that ∃h t ∈ H t , L t h t = h t + g t ;(2) If M ∈ M t , h * ∈ H t and ( pt (s, a)p(s, a))h * ≤ β(s, a), then g t ≥ g * (M);(3) If M t is convex, then for all u ∈ R S , the policy π =: Greedy(M t , u, β) picking the actions achieving L β t u satisfies L t u = rπ + Pπ u for rπ (s) ≤ sup R t (s, π(s)) and Pπ (s) ∈ P t (s, π(s)); (4) For all u ∈ R S and n ≥ 0, spL n+1 t u -L n t u ≤ sp (L t ) n+1 u -(L t ) n u .The property (1) guarantees that L t has a fix-point while (2) states that this fix-point corresponds to an optimistic gain g t if the model and the bias confidence region are correct and the mitigation isn't too aggressive. Combined with (3), the Poisson equation of a policy corresponds to this fix-point, i.e., rπ + Pπ h t = h t + g t , so that g t is the gain and h t ∈ H t is a legal bias for π under the model (r π , Pπ ). Lastly, the property (4) guarantees that the iterates L n t u converge to a fix-point of L at least as quickly as L n t u goes to a fix-point of L t ; The convergence of (L t ) n u is already guaranteed by existing studies and is discussed in the appendix.Provided that the bias confidence region is constructed, Proposition 2 foreshadows how powerful the construction is: The algorithm PMEVI, obtained by iterating L t instead of L t in EVI, can replace the well-known EVI within any algorithm of the literature that relies on it (UCRL2 Auer et al. [2009] , UCRL2B Fruit et al. [2020] or KL-UCRL Filippi et al. [2010] ) for an immediate improvement of its theoretical guarantees.The bias confidence region used by PMEVI-DT is obtained as a collection of constraints of the form:EQUATION)Such constraints include (1) prior bias constraints (if any) of the form of h(s)-h(s ′ ) ≤ c * (s, s ′ ); (2) span constraints of the form h(s)h(s ′ ) ≤ c 0 := T 1/5 spawning the span semi-ball {u : sp (u) ≤ T 1/5 }; and(3) pair-wise constraints obtained by estimating bias differences in the style of Zhang and Ji [2019] , Zhang and Xie [2023] that we further improve. We start by defining a bias difference estimator.Definition 1 (Bias difference estimator). Given a pair of states s s ′ , their sequence of commute times(τ s↔s ′ i ) i≥0 is defined by τ s↔s ′ 2i := inf{t > τ s↔s ′ 2i-1 : S t = s} and τ s↔s ′ 2i+1 := inf{t > τ s↔s ′ 2i : S t = s ′ } with the convention that τ s↔s ′ -1 = -∞. The number of commutations up to time t is N t (s ↔ s ′ ) := inf{i : τ s↔s ′ i≤ t}, and ĝ(t) := 1 t t-1 i=0 R i is the empirical gain. The bias difference estimator at time T is any quantity c T (s, s ′ ) ∈ R such that:EQUATION)Lemma 3. With probability 1 -2δ, for all T ′ ≤ T , we haveEQUATION)Lemma 3 says that the quality of the estimator c T (s, s ′ ) is directly linked to the number of observed commutes between s and s ′ as well as the regret. The idea is that if the algorithm makes many commutes between s and s ′ and if its regret is small, then the algorithm mostly takes optimal paths from s to s ′ . The bound provided by Lemma 3 is not accessible to the learner however, because sp (h * ) is unknown in general. To overcome this issue, sp (h * ) is upper-bounded by c 0 := T 1/5 . Overall, this leads to the design of the algorithm estimating the bias confidence region as specified in Algorithm 3. Coupled with prior information and span constraints, the bias confidence region H t is a polyhedron of the same kind as the one encountered in Zhang and Xie [2023] . When generated by constraints of the form (8), following [Zhang and Xie, 2023, Proposition 3] , one can project onto H t in polynomial time with Algorithm 4. Moreover, the resulting projection operator satisfies the prerequisites (O1-4) of Proposition 2, making PMEVI (Algorithm 2) well-behaved. See Appendix B.2 for proofs. Lemma 4. Assume that H is a set of h ∈ R S satisfying a system of equations of the form of (8). If H is non empty, then the operator Γu := BiasProjection(H, u) (see Algorithm 4) is a projection on H and satisfies the properties (O1-4) defined in Proposition 2.The fact that h * ∈ H t with high probability is used in PMEVI-DT to restrict the search of EVI by reducing the dynamical bias error. This reduction is based on a empirical Bernstein inequality (see Lemma 38) applied to ( p(s, a)p(s, a))u. Here, it gives that with probability 1 -δ, we have:EQUATIONwhere V( pt (s, a), u) is the variance of u under the probability vector pt (s, a). More specifically, if q is a probability on S and q ∈ R S , we set V(q, u) := s q(s)(u(s)q • u) 2 . In (11), u ∈ R S , (s, a) ∈ X and T ≥ 1 are fixed. Once is tempted to use (11) directly to mitigate the extended Bellman operator, but the resulting operator is ill-behaved because it loses monotony. This issue is avoided by changing β t (s, a, u) to max u∈H t β t (s, a, u) in (11). The resulting inequality is not guaranteed to hold simultaneously for all u ∈ H t and with high probability; However, it is guaranteed to hold with high probability for u = h * , which will be enough. Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Justification: To every result is attached a proof or a reference. Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced.• All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
regret guarantees: 
 Theorem 5 thereafter shows that PMEVI-DT has minimax optimal regret under regularity assumptions on the used confidence region M t . Assumption 1 asserts that the confidence region holds uniformly with high probability. Assumption 2 asserts that the reward confidence region is sub-Weissman (see var(s, a) ← V( pt (s, a), h 0 ) + 8c 0 s ′ ∈S pt (s ′ |s, a)c(s ′ , s); 7: β t (s, a) ← 2var(s, a)ρ + 3c 0 ρ or +∞ if N t (s, a) = 0; 8: end for 9: return β t .Lemma 35) and Assumption 3 assumes that the model confidence region makes sure that EVI (6) converges in the first place. Assumption 4 asserts that the prior bias region is correct.Assumption 1. With probability 1 -δ, we have M ∈ K(T )k=1 M t k . Assumption 2. There exists a constant C > 0 such that for all (s, a) ∈ S, for all t ≤ T , we have:R t (s, a) ⊆ r(s, a) ∈ R(s, a) : N t (s, a) ∥r t (s, a) -r(s, a)∥ 2 1 ≤ C log 2S A(1+N t (s,a)) δ .Assumption 3. For t ≥ 0, M t is a (s, a)-rectangular convex region and L n t u converges a fix-point. Assumption 4. The prior bias region H * contains h * (M) and is generated by constraints of the form:∀s s ′ , h(s) -h(s ′ ) ≤ c * (s, s ′ ) with c * (s, s ′ ) ∈ [-∞, ∞] (possibly infinite).Refer to Appendix A.2 for the feasibility of Assumption 1, Appendix A.2.3 for Assumption 2, and Appendix A.3 for Assumption 3. Theorem 5 (Main result). Let c > 0. Assume that PMEVI-DT runs with a confidence region system t → M t that guarantees Assumptions 1-3. If T ≥ c 5 , then for every weakly communicating model with sp (h * ) ≤ c and such that Assumption 4 is satisfied (h * ∈ H * ), PMEVI-DT achieves regret: To have a completely prior-less algorithm, pick H * = R S . The proof of Theorem 5 is tedious and its details are deferred to appendix. We will focus here on the main ideas.O cS AT log S AT δ + O cSNotations. At episode k, the played policy is denoted π k . As a greedy response to h k , by Proposition 2 (3), there exists rk (s) ≤ sup R t k (s, π k (s)) and Pk (s) ∈ P t k (s, π(x)) such that h k + g k = rk + Pk h k .The reward-kernel pair Mk = (r k , Pk ) is referred to as the optimistic model of π k . We write P k := P π k (M) the true kernel and Pk := P π k ( Mt k ) the empirical kernel. Likewise, we define the reward functions r k and rk . The optimistic gain and bias satisfyg k = g(π k , M k ) and h k = h(π k , M k ). We further denote c 0 = T 1 5 .The regret is first decomposed episodically with Reg(T ) = k t k+1 -1 t=t k (g * -R t ). The first step goes back to the analysis of UCRL2 Auer et al. [2009] , and consists in upper-bounding the regret of the episode k with optimistic quantities that are exclusive to that episode. Lemma 6 (Reward optimism). With probabililty 1 -6δ, we have:EQUATION)We introduce the two optimistic regrets B(T) := k t k+1 -1 t=t k (g k -R t ) and B(T ) := k t k+1 -1 t=t k (g k -r k (X t )).Rewriting the summand g krk (X t ) using the Poisson equation h k + g k = rk + Pk h k , we get:B(T ) = k t k+1 -1 t=t k pk (S t ) -e S t h k . Model region M t Bias region H t Mitigation β t Projected Mitigated EVI (Alg.1) Regret Reg(T ) k tk+1-1 t=tk (g * -R t ) Optimistic re- gret (Lemma 6) k tk+1-1 t=tk (g k -R t ) O S AT log(T ) Navigation error (Lemma 7) k,t (p(X t ) -e S t+1 )h k Emp. bias error (Lemma 8) k,t ( ptk (X t ) -p(X t ))h * Optimism over- shoot (Lemma 9) k,t ( pt k (S t ) -pt k (S t ))h k 2nd order error (Lemma 10) k,t ( pt k (S t ) -p(Xt))(hk -h * ) (in expectation) O(c 0 log(S AT )) sp (h * )S AT log(S AT ) S 2 Ac 0 log 2 (T ) Reg(T ) O c 0 S 2 A 2 T 1/4 log 2 (T )Figure 1 :An overview of PMEVI-DT and its regret analysis. In the above, g k and h k are the optimistic gain and bias functions produced by PMEVI (see Algorithm 2) at episode k, and pt k and pt k are respectively the empirical and optimistic kernel models at episode k.The analysis proceeds by decomposing the above expression of B(T ) in the style of Zhang and Ji [2019] . We write t k+1 -1 t=t k ( pk (S t )e S t )h k as:t k+1 -1 t=t k            p k (S t ) -e S t h k navigation error (1k) + ( pk (S t ) -p k (S t )) h * empirical bias error (2k) + ( pk (S t ) -pk (S t )) h k optimistic overshoot (3k) + ( pk (S t ) -p k (S t )) (h k -h * ) second order error (4k)           Each error term is bounded separately. Below, we denote V(q, u) := s q(s)(u(s)q • u) 2 . Lemma 7 (Navigation error). With probability 1 -7δ, the navigation error is bounded by:k t k+1 -1 t=t k (p k (S t ) -e S t )h k ≤ 2 T -1 t=0 V(p(X t ), h * ) log T δ + 2S A 1 2 3B(T ) log T δ + O T 7 20 .Lemma 8 (Empirical bias error). With probability 1 -δ, the empirical bias error is bounded by:k t k+1 -1 t=t k ( pk (S t ) -p k (S t )) h * ≤ 4 S A T -1 t=0 V(p(X t ), h * ) log S AT δ + O log 2 (T ) .Lemma 9 (Optimistic overshoot). With probability 1 -6δ, the optimistic overshoot is bounded by:k t k+1 -1 t=t k ( pk (S t ) -pk (S t )) h k ≤          4 2S A T -1 t=0 V(p(X t ), h * ) log S AT δ +8(1 + c 0 )S 3 2 A log 3 2 S AT δ √ B(T ) + O T 1 4          .Lemma 10 (Second order error). With probability 1 -6δ, the second order error is bounded by:k t k+1 -1 t=t k ( pk (S t ) -p k (S t )) (h k -h * ) ≤ 16S 2 A(1 + c 0 ) log 1 2 S 2 AT δ 2B(T ) + O T 1 4 .We see that the empirical bias error (Lemma 8) and the optimistic overshoot (Lemma 9) both involve the sum of variancesT -1 t=0 V(p(X t ), h * ), which is shown in Lemma 29 to be of order sp (h * )sp (r)T + T -1 t=0 ∆ * (X t ). The pseudo-regret term T -1 t=0 ∆ * (X t) is bounded with the regret using Corollary 31, then by B(T ). With high probability, we obtain an equation of the form:B(T ) ≤ C (1 + sp (h * ))S AT log T δ + CS 2 A(1 + c 0 ) log 2 (T ) B(T ) + Õ T 1 4where C is a constant. Setting α := CS 2 A(1 + c 0 ) log 2 (T ) andβ := C (1 + sp (h * ))S AT log(T/δ) + Õ(T 1/4 ), the above equation is of the form B(T ) ≤ β + α √ B(T ). Solving in B(T ), we find B(T ) ≤ β + 2 √ αβ + α 2 .The dominant term is β, hence we readily obtain:EQUATION) Since c 0 = o(T 1 4), we conclude that B(T ) = O sp (h * )S AT log(T/δ) , ending the proof.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: The algorithmic content in the main body is detailed enough to implement the algorithm, the exception being the confidence intervals and the implementation of EVI (because those come from already existing works). The confidence intervals are discussed in a dedicated section in the Appendix, while the works of Auer et al. [2009] , Filippi et al.[2010], Fruit et al. [2020] etc. provide detailed ready-to-implement pseudo-code for EVI.Our code is mostly written in Python. Experiments took a few dozen minutes on a low end laptop.Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
experimental illustrations: 
 To get a grasp of how PMEVI-DT behaves in practice, we provide in Fig. 2 a first round of illustrative experiments. In both, the environment is a river-swim which is a model known to be hard to learn despite its size, with high diameter and bias span, see Appendix D for the model's description. On the first experiment, we observe that PMEVI can exploit prior bias knowledge effectively and drastically improve the regret performance, depending on the quality of the prior region.On the second experiment however, we observe that without prior knowledge, PMEVI has nearly the same regret performance that its EVI counterparts, meaning that the bias confidence region is too large to effectively improve the regret performance. This observation is first to be taken with caution. Indeed, the regret that is being estimated above is model specific, hence is not an estimate of the minimax regret -This being said, it undoubtedly shows that the bias confidence region is ineffective and this can be explained as follows. On experiments, we see that most of the regret is due to the early phase of the learning process, where proper bias information is nearly impossible to get. Indeed, the regret is still growing linearly, so no bias information can be inferred. But in addition, this "bad" early data pollutes the bias estimator for a long duration. In other words, while the theoretical regret guarantees of PMEVI-DT are better than its EVI analogues, there is room to improve the bias estimation mechanism and the practical performance.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: The code is provided in the supplementary material, together with the scripts to reproduce the exact figures of the paper.Guidelines:• The answer NA means that paper does not include experiments requiring code.• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
conclusion: 
 In this work, we have shown that regret guarantees of order sp(h * )S AT log(T ) can be achieved for weakly communicating MDPs without prior knowledge, nor exponential computational cost.In particular, regret guarantees can scale with the bias span rather than the diameter without prior knowledge. This is in opposition to the recent results that the sample complexity cannot be bounded in term of bias span without prior knowledge for average reward MDPs Tuynman et al. [2024] , Wang et al. [2024] , Zurek and Chen [2024a,b] . This difference lies in the fact (ϵ, δ)-PAC algorithm must produce a policy π τ after τ learning steps where τ is a stopping time, with P(g π τ ≤ g * -ϵ) ≤ δ.Implicitly, these algorithms must hereby certify that the output policy is approximately optimal. In opposition, regret robust algorithms have no need to assess that deployed policies are indeed optimal.In the end, the regret advantages of PMEVI-DT over pure EVI-based methods remain theoretical, and the experimental shortcomings displayed in Section 5 leave a few opportunities for future work. Can bias information be inferred more efficiently? Or, do the experiments indicate that the regret analysis of EVI-based methods may be drastically improved?Because h * is a fixed vector, Bennett's inequality (see Lemma 39) guarantees that ( pk (S t )p k (S t )h * is small as follows. By doing a union bound over Lemma 39 with confidence δ S AT over all pairs (s, a) and visits counts N(s, a) ≤ T , we see that with probability 1 -δ, for all k, we have:t k+1 -1 t=t k ( pk (S t ) -p k (S t )) h * ≤ sp (h * )S A + t k+1 -1 t=t k 1 N t k (X t ) ≥ 1        2V(p(X t ),h * ) log( S AT δ ) N t k (X t ) + sp(h * ) log S AT δ 3N t k (X t )        (by doubling trick) ≤ sp (h * )S A + 2 t k+1 -1 t=t k 1 (N t (X t ) ≥ 1)        2V(p(X t ),h * ) log( S AT δ ) N t (X t ) + sp(h * ) log S AT δ 3N t (X t )        .Summing this over k and factorizing over state-action pairs, we get that with probability 1 -δ,k (2k) ≤ sp (h * )S A + 2 s,a         N T (s,a) n=1 2V(p(s,a),h * ) log( S AT δ ) n + N T (s,a) n=1 sp(h * ) log S AT δ n         ≤ sp (h * )S A + 4 s,a N T (s, a)V(p(s, a), h * ) log S AT δ + 2sp (h * )S A log S AT δ log(T ) (Jensen) ≤ sp (h * )S A + 4 S A s,a V(p(s, a), h * ) log S AT δ + 2sp (h * )S A log S AT δ log(T ) = sp (h * )S A + 4 T -1 t=0 V(p(X t ), h * ) log S AT δ + 2sp (h * )S A log S AT δ log(T )We recognize the sum of variances T -1 t=0 V(p(X t ), h * ), that is left to be upper-bounded later on. □Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: People that are unfamiliar with Markov decision processes may not know the river-swim setting in which experiments are driven, but it is not required to understand the figures and the discussion. Moreover, a description of the environment (river-swim) is provided in the appendix in addition to be referenced. See also Experimental Result Reproducibility for more.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [No] Justification: We did a hundred runs for every algorithm, which is enough to get statistical significance for the small sized problems that we experiment on. Also, experiments are mostly illustrative and do not account for an extensive numerical validation of the theoretical results.Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [No] Justification: This is mostly a theoretical paper. Most of the computational cost of the work is processing L A T E X and rendering a PDF. Like said earlier, experiments all together took less than a hour on a low end laptop.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: -Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.• The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: It's mainly a theoretical work on small sized Markov decision processes.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: -Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA]  
 
 Appendix: This section provides the technical details required to understand the design of PMEVI-DT in Section 3. We further discuss the assumptions 1-4 appearing in Theorem 5 and provide sufficient conditions so that they are met.A.1 Proof of Lemma 3, estimation of the bias error Fix s, s ′ ∈ S. We denoteα T := N T (s ↔ s ′ )(h * (s) -h * (s ′ ) -c T (s, s ′ )). We will start by considering the better estimator c ′ T (s, s ′ ) that satisfies the same equation ( 9) than c T (s, s ′ ) but with ĝ(T ) changed to g * , readily:N t (s ↔ s ′ )c ′ T (s, s ′ ) = N T (s↔s ′ )-1 t=0 (-1) i τ s↔s ′ i+1 -1 t=τ s↔s ′ i (g * -R t ).To avoid a typographical clutter, we write τ i instead of τ s↔s ′ i in the remaining of the proof and we write α′ T := N T (s ↔ s ′ )(h * (s) -h * (s ′ ) -c ′ T (s, s ′ ). (STEP 1)We start by relating the two estimators. Intuitively, ĝ(T ) is a good estimator for g * when the regret is small. Recall that ĝ(T ) := 1 T T -1 t=0 R t , hence: T -1 t=0 |ĝ(T ) -g * | = T -1 t=0 (R t -g * ) = Reg(T ) . Therefore, |α T | ≤ α ′ T + α T -α ′ T ≤ α ′ T + T -1 t=0 |ĝ(T ) -g * | ≤ α ′ T + Reg(T ) .We are left with upper-boundingα ′ T . (STEP 2) If i is even, then S τ i and S τ i+1 = s ′ ; otherwise S τ i = s ′ and S τ i+1 = s. In both cases, we have h * (S τ i+1 ) -h * (S τ i ) = (-1) i (h * (s ′ ) -h * (s)). Therefore, using Bellman's equation, the quantity A := τ i+1 -1 t=τ i (g * -R t ) satisfies: A = τ i+1 -1 t=τ i p(X t ) -e S t h * + τ i+1 -1 t=τ i (r(X t ) -R t ) + τ i+1 -1 t=τ i ∆ * (X t ) = τ i+1 -1 t=τ i e S t+1 -e S t h * + τ i+1 -1 t=τ i p(X t ) -e S t+1 h * + τ i+1 -1 t=τ i (r(X t ) -R t ) + τ i+1 -1 t=τ i ∆ * (X t ) = (-1) i (h * (s ′ ) -h * (s)) + τ i+1 -1 t=τ i p(X t ) -e S t+1 h * + τ i+1 -1 t=τ i (r(X t ) -R t ) + τ i+1 -1 t=τ i ∆ * (X t ).Multiplying by (-1) i and rearranging, h * (s ′ )h * (s) + (-1) i+1 τ i+1 -1 t=τ i (g * -R t ) appears to be equal to:(-1) i+1 τ i+1 -1 t=τ i p(X t ) -e S t+1 h * + r(X t ) -R t + τ i+1 -1 t=τ i ∆ * (X t ) .Proceed by summing over i. By triangular inequality, we obtain:α ′ T ≤ N T (s↔s ′ )-1 i=0 τ i+1 -1 t=τ i (-1) i+1 p(X t ) -e S t+1 h * + r(X t ) -R t + N T (s↔s ′ )-1 i=0 τ i+1 -1 t=τ i ∆ * (X t ).Because all Bellman gaps ∆ * are non-negative, the second term is upper-bounded by the pseudo-regretT -1 t=0 ∆ * (X t ).The first term is a martingale, and the martingale difference sequence (-1) i+1 ((p(X t )e S t+1 )h * + r(X t ) -R t has span at most sp (h * ) + 1 since rewards are supported in [0, 1]. Although the number of involved terms is random, it is upper-bounded by T , hence by the maximal version of Azuma-Hoeffding's inequality (Lemma 32), we have that with probability at least 1 -δ and uniformly for T ′ ≤ T ,N T ′ (s↔s ′ )-1 i=0 τ i+1 -1 t=τ i (-1) i+1 p(X t ) -e S t+1 h * + r(X t ) -R t ≤ (1 + sp (h * )) 1 2 T log 2 δ .(STEP 3) We conclude that with probability 1 -δ, for all T ′ ≤ T ,α T ′ ≤ (1 + sp (h * )) 1 2 T log 2 δ + T ′ -1 t=0 ∆ * (X t ) + Reg(T ′ ) .We are left with relating both T ′ -1 t=0 ∆ * (X t ) and Reg(T ′ ) to T ′ -1 t=0 (g-R t ). Using the Bellman equation again, we find that:T ′ -1 t=0 (g * -R t -∆ * (X t )) ≤ |h * (S 0 ) -h * (S T ′ )| + T ′ -1 t=0 p(X t ) -e S t+1 h * + (r(X t ) -R t ) ≤ sp (h * ) + (1 + sp (h * )) 1 2 T log 2 δwhere the last inequality holds with probability 1 -δ uniformly over T ′ ≤ T by Azuma-Hoeffding's inequality again (Lemma 32). Remark that if yz ≤ x ≤ y + z, then |x| ≤ |y| + |z|, hence we conclude that with probability 1 -δ, for all T ′ ≤ T :T ′ -1 t=0 ∆ * (X t ) + Reg(T ′ ) ≤ 2 T ′ -1 t=0 ∆ * (X t ) + (1 + sp (h * )) 1 2 T log 2 δ + sp (h * ) ≤ 2 T ′ -1 t=0 (g * -R t ) + 3(1 + sp (h * )) 1 2 T log 2 δ + 3sp (h * ) ≤ 2 T ′ -1 t=0 (g -R t ) + 3(1 + sp (h * )) 1 2 T log 2 δ + 3sp (h * )where the last inequality invokes g ≥ g * . We conclude that, with probability 1 -2δ, for all T ′ ≤ T , we have:N T ′ (s ↔ s ′ )(h * (s) -h * (s ′ ) -c T ′ (s, s ′ )) ≤ 3sp (h * ) + 1 + sp (h * ) 8T log 2 δ + T ′ -1 t=0 (g -R t ).This concludes the proof. □The algorithm PMEVI-DT can be instantiated with a large panel of possibilities, depending on the type of confidence region one is willing to use for rewards and kernels. In this work, we allow for four types of confidence regions, described below. For conciseness, q ∈ {r, p} is a symbolic letter that can be a reward or a kernel and we denote Q t (s, a) the confidence region for q(s, a) at time t. If q = r, then dim(q) = 2 (Bernoulli rewards) with Q(s, a) = [0, 1]; and if q = p, then dim(q) = S with Q(s, a) = P(S).(C1) Azuma-Hoeffding or Weissman type confidence regions, with Q t (s, a) taken as:q(s, a) ∈ Q(s, a) : N t (s, a) ∥ qt (s, a) -q(s, a)∥ 2 1 ≤ dim(q) log 2S A(1+N t (s,a)) δ .(C2) Empirical Bernstein type confidence regions, with Q t (s, a) taken as:             q(s, a) ∈ Q(s, a) : ∀i, | qt (i|s, a) -q(i|s, a)| ≤ 2V( qt (i|s,a)) log 2 dim(q)S AT δ N t (s,a) + 3 log 2 dim(q)S AT δ N t (s,a)             .with the convention that x/0 = +∞ for x > 0.(C3) Empirical likelihood type confidence regions, with Q t (s, a) taken as:q(s, a) ∈ Q(s, a) : N t (s, a) KL( qt (s, a)∥ q(s, a)) ≤ log 2S A δ + (dim(q) -1) log e 1 + N t (s,a) dim q-1 . (C4) Trivial confidence region with Q t (s, a) = Q(s, a).A few remarks are in order. When rewards are not Bernoulli, only the confidence regions (C1) and (C4) are elligible among the above. Then, Weissman's inequality must be changed to Azuma's inequality for σ-sub-Gaussian random variables, see Lemma 34. Since rewards are supported in [0, 1], Hoeffding's Lemma guarantees that reward distributions are σ-sub-Gaussian with σ = 1 2 .The confidence regions Q t (s, a) described with (C1-4) are tuned so that the following result holds:Lemma 11. Assume that, for all q ∈ {r, p} and (s, a) ∈ X, we choose Q t (s, a) among (C1-4). Then Assumption 1 holds. More specifically, the region of models M t := s,a (R t (s, a) × P t (s, a)) satisfiesP(∃t ≤ T : M M t ) ≤ δ.Proof. We show that, for all q ∈ {r, q} and (s, a) ∈ X, if Q t (s, a) is chosen amoung (C1-4), then In this section, we show that if Assumption 1 holds, then the bias confidence region constructed by PMEVI-DT is correct with high probability, and that the mitigation is not too strong. Recall that (g k , h k ) are the optimistic gain and bias of the policy deployed in episode k (see Algorithm 1). In particular, we haveP (∃t ≤ T : q(s, a) Q t (s, a)) ≤ δ. If Q t (g k = L t k h k -h k with h k ∈ H t k .We start by a result on the deviation of the variance, which is what the variance approximation Algorithm 5 is based on. Recall that the bias confidence region H t is obtained as the collection of constraints:(1) prior constraints (if any)h(s) -h(s ′ ) ≤ c * (s, s ′ ); (2) span constraints h(s) -h(s ′ ) ≤ c 0 := T 1/5 ; (3) dynamically inferred constraints |h(s) -h(s ′ ) -c t (s ′ , s)| ≤ error(c t , s ′ , s) (see Algorithm 3).We start with the technical result that is behind the variance approximation Algorithm 5.Lemma 12. Let u, v ∈ H t and fix p a probability distribution on S. Then for all s ∈ S,V(p, u) ≤ V(p, v) + 8c 0 s ′ ∈S p(s ′ ) error(c t , s ′ , s).Proof. We start by establishing the following result: If p is a probability distribution on S and u, v ∈ R S , we have:EQUATION)where • is the dot product, u 2 the Hadamard product uu and |u| the vector whose entry s is |u(s)|. ( 14) is obtained with a straight forward computation:V(p, u) -V(p, v) = p • (u 2 -v 2 ) + (p • v) 2 -(p • u) 2 = p • ((u -v)(u + v)) + (p • (u -v))(p • (u + v)) ≤ p • (|u -v| (u + v)) + (p • |u -v|)(p • |u + v|) ≤ 2(p • |u -v|) max(u + v).Observe that v can be changed to v + λe, where e is the vector full of ones, without changing the result. The same goes for u. We now move to the proof of the main statement. First, translate u and v such that u(s) = v(s) = 0. Then, we have:p • (u -v) = s ′ ∈S p(s ′ ) u(s ′ ) -u(s) -c t (s ′ , s) + v(s) -v(s ′ ) + c t (s ′ , s) ≤ s ′ ∈S p(s ′ ) u(s ′ ) -u(s) -c t (s ′ , s) + v(s ′ ) -v(s) -c t (s ′ , s) ≤ 2 s ′ ∈S p(s ′ ) error(c t , s ′ , s).Conclude using that max(u+ v) ≤ max(u) + max(v) + 2c 0 for u, v ∈ H such that u(s) = v(s) = 0. □Lemma 13. Assume that Assumption 1 holds and that c 0 ≥ sp (h * ). Then, with probability 1 -4δ, for all k ≤ K(T ), (1) g k ≥ g * and (2) h * ∈ H t k and (3) for all (s, a), ( pt k (s, a)p(s, a))h * ≤ β t k (s, a).Proof. Let E 1 the event (∀k ≤ K(T ), M ∈ M t k ). Let E 2 the event stating that, for all T ′ ≤ T ,N T ′ (s ↔ s ′ ) h * (s) -h * (s ′ ) -c T ′ (s, s ′ ) ≤ 3sp (h * ) + (1 + sp (h * )) 8T log( 2 δ ) + 2 T ′ -1 t=0 (g * -R t ),and let E 3 the event stating that, for all T ′ ≤ T and for all (s, a) ∈ X, we have:( pT ′ (s, a) -p(s, a)) h * ≤ 2V( pT ′ (s,a),h * ) log( S AT δ ) N T ′ (s,a) + 3sp(h * ) log( S AT δ ) N T ′ (s,a).By Assumption 1, we have P(E 1 ) ≥ 1 -δ. By Lemma 3, we have P(E 2 ) ≥ 1 -2δ and by Lemma 36, we haveP(E 3 ) ≥ 1 -δ, so P(E 1 ∩ E 2 ∩ E 3 ) ≥ 1 -4δ. We prove by induction on k ≤ K(T ) that, on E 1 ∩ E 2 ∩ E 3 , (1) g k ≥ g * , (2) h * ∈ H t k (3) and for all (s, a), ( pt k (s, a)p(s, a))h * ≤ β t k (s, a), where g k is the optimistic gain of the policy deployed at episode k.k = 0. Indeed, N 0 (s ↔ s ′ ) = 0 for all s, s ′ hence c 0 (s, s ′ ) = c 0 ≥ sp (h * ). Therefore, H 0 ⊇ h ∈ R S : sp (h) ≤ c 0 ⊇ h ∈ R S : sp (h) ≤ sp (h * )so contains h * , proving (2). Moreover, since N 0 (s, a) = 0, we have β 0 (s, a) = +∞, proving (3). Finally, since M ∈ M 0 on E 1 , by the statement (2) of Proposition 2, we have g k ≥ g * , hence proving (1). Now assume that k ≥ 1. By induction g ℓ ≥ g * for all ℓ < k, so on E 2 we have:N t k (s ↔ s ′ ) h * (s) -h * (s ′ ) -c t k (s, s ′ ) ≤ 3sp (h * )+(1+sp (h * )) 8T log( 2 δ )+2 k-1 ℓ=1 t ℓ+1 -1 t=t ℓ (g ℓ -R t ).By design of H t k (see Algorithm 3), we deduce that (2) h * ∈ H t k . Denote h 0 ∈ H t k the reference point used by Algorithm 5. We have, for all (s, a) ∈ X, on E 1 ∩ E 2 ∩ E 3 , we have:pt k (s, a) -p(s, a) h * ≤ 2V( pt k (s,a),h * ) log( S AT δ ) N t k (s,a) + 3sp(h * ) log( S AT δ ) N t k (s,a) (h * ∈ H t k + Lemma 12) ≤ 2(V( pt k (s,a),h 0 ) log( S AT δ )+8c0 s ′ ∈S pt k (s ′ |s,a) error(c t k ,s ′ ,s)) log( S AT δ ) N t k (s,a) + 3c 0 log( S AT δ ) N t k (s,a) =: β t k (s, a)by construction of Algorithm 5. Accordingly, (3) is satisfied. Finally, M ∈ M t k on E 1 so by Proposition 2, we have (1) g k ≥ g * . □Corollary 14. Assume that, for all q ∈ {r, p} and (s, a) ∈ X, we choose Q t (s, a) among (C1-4). Then, with probability 1 -4δ, for all k ∈ K(T ), we have g k ≥ g * and (2) h * ∈ H t k and (3) for all (s, a),( pt k (s, a) -p(s, a))h * ≤ β t k (s, a).Proof. By Lemma 11, Assumption 1 is satisfied. Apply Lemma 13. □Although the kernel confidence region can even chosen to be trivial with (C4), in order to work, PMEVI-DT needs the reward confidence region to be sub-Weissman in the following sense:Assumption 2. There exists a constant C > 0 such that for all (s, a) ∈ S, for all t ≤ T , we have:R t (s, a) ⊆ r(s, a) ∈ R(s, a) : N t (s, a) ∥r t (s, a) -r(s, a)∥ 2 1 ≤ C log 2S A(1+N t (s,a)) δ .This is indeed the case if R t (s, a) is chosen among (C1-3).We start with a preliminary lemma on the speed of convergence of EVI. The Lemma 15 is thought to be applied to extended MDPs. Below, when we claim that the action space is compact, we further claim that a ∈ A(s) → p(s, a) is a continuous map, so that the Bellman operator is continuous and that g * and h * are well-defined, see Puterman [1994] .Lemma 15. Let M a weakly-communicating MDP with finite state space R S and compact action space, and let L its Bellman operator. Assume that there exists γ > 0 such that, ∀u ∈ R S , ∀s ∈ S, ∃a ∈ A(s), Lu(s) = r(s, a) + p(s, a)u = r(s, a) + γ max(u) + (1 -γ)q u s u ( * ) with q u s ∈ P(S). Then, for all u ∈ R S and all ϵ > 0, if sp L n+1 u -L n u ≥ ϵ, then:n ≤ 2 + 4sp (w 0 ) γϵ + 2 γ log 2sp (w 0 ) ϵ .Proof. Since M is weakly communicating, has finitely many states and compact action space, it has well-defined gain g * and bias h * functions. Denote u n+1 := L n u.w n := maxπ∈Π {r π + P π u n-1 } -ng * -h * = max π∈Π {r π -g * + (P π -I)h * + P π (u n-1 -h * -(n -1)g * )} =: max π∈Π r ′ π + P π w n-1 .Observe that the policy achieving the maximum is the one achieving u n = r π + P π u n-1 . Remark that r ′ π (s) = -∆ * (s, π(s)) ≤ 0 is the Bellman gap of the pair (s, π(s)), that we more simply write ∆ π . For all n, there exists π n ∈ Π such that w n+1 = -∆ π n + P π n w n . Moreover, by assumption, we haveEQUATIONFix ϵ > 0, and let n ϵ := inf n : sp (w n ) < ϵ .Let π * an optimal policy. We have w n+1 ≥ P π * w n so by induction, w n+1 ≥ P n+1 π * w 0 ≥ min(w 0 )e. Meanwhile, we see that ∥w n ∥ 1 ≥ n-1 k=0 ∆ π k 1 + S min(w 0 ), so n-1 k=0 ∆ π k 1 ≤ sp (w 0 ). Since ∆ π k ≤ 0 for all k, we have sp ∆ π k ≤ ∆ π k 1 so n-1 k=0 sp ∆ π k ≤ sp (w 0 ). By (15), either sp (w n+1 ) ≤ (1 -1 2 γ) max(ϵ, sp (w n )) or sp ∆ π n ≥ 1 2 γϵ, but because +∞ k=0 sp ∆ π k ≤ sp (w 0 ), the second case can happen at most 2sp(w 0 ) γϵ times. We deduce that, for all n ≤ n ϵ ,sp (w n+1 ) ≤ 1 -1 2 γ n- 2sp(w 0 ) γϵ sp (w 0 ).In particular, for n = n ϵ -1, we get:ϵ ≤ 1 -1 2 γ n ϵ -2- 2sp(w 0 ) γϵ sp (w 0 ).We obtain:n ϵ ≤ 2 + 2sp (w 0 ) γϵ + 2 γ log sp (w 0 ) ϵ .To conclude, check that spL n+1 u -L n u = sp (w n+1 -w n ) ≤ 2sp (w n ). □Before moving to the application of interest, remark that this result can be greatly improved if the supremum sup {∆ * (s, a) : ∆ * (s, a) < 0} is not zero, to change the dominant term 4sp(w 0 ) γϵ for a constant independent of ϵ. Corollary 16. Assume that the M t has non-empty interior, and that its Bellman operator satisfies the requirement of Lemma 15, i.e., there exists γ > 0 such that, ∀u ∈ R S , ∀s ∈ S, ∃a ∈ A(s), ∃r t (s, a) ∈ R t (s, a), ∃ pt (s, a) ∈ P t (s, a):L t u(s) = rt (s, a) + pt (s, a)u = rt (s, a) + γ max(u) + (1 -γ)q us u for some q u s ∈ P(S). Then Assumption 3 is satisfied, and span fix-points ht of L t are such that g * (M t ) = L t htht .Proof. If M t is has non-empty interior, it means that for all (s, a), P t (s, a) has non-empty interior. Therefore, for all state-action pair, there exists pt (s, a) ∈ P t (s, a) that is fully supported. It follows that M t is communicating, and it follows from standard results Puterman [1994] that its span fix-points h do exist and that gt := L htht ∈ Re does not depend on the initial state.Moreover, if M ∈ M t and π ∈ Π with gπ ≡ g(π, M t ) ∈ Re, letting rπ := r π ( M) and Pπ := P π ( M), we have:rπ + pπ ht ≤ L t ht ≤ gt e + ht . So by induction and since L t is obviously monotone and linear, we show that:n k=0 Pk π rπ ≤ ng t e + (I -Pn π ) hπ .Dividing by n and letting it go to infinity, we obtain g(π, M t ) ≤ gt . Observe that we have equility by taking the policy achieving (g t , ht ).To see that EVI converges indeed, simply observe that Lemma 15 provides a finite bound on how much time is required until the sp L n+1 t u -L n t u ≤ ϵ. Hence sp L n+1 t u -L n t u vanishes to 0. □ About Assumption 3. The assumptions made by Corollary 16 are met if the kernel confidence regions are:• Built out of Weissman's inequality (C1) (see the next section, also Auer et al. [2009] );• Built out of Bernstein's inequality (C2) (because the maximization algorithm to compute pt (s, a)u i in EVI has the same greedy properties than with Weissman's inequality); • Trivial (C4).For confidence regions build with empirical likelihood estimates (C3), there is no guarantee of convergence (although we conjecture that one could be established), although the gain is still welldefined because M t remains communicating. However, just like the original work of Filippi et al. [2010] , the convergence is always met numerically.In this section, we show that when one is using Weissman confidence regions for kernels (C1), then the iterates of L t converge to an ϵ span-fix-point quickly. Proposition 17. Assume that PMEVI-DT uses kernel confidence regions of Weissman type (C1) satisfying Assumption 1. Then with probability 1 -δ, the number of iterations of PMEVI (see Algorithm 2) is O D √ S AT , hence the algorithm has polynomial per-step amortized complexity.Proof. With Weissman type confidence regions for kernels, for all t ≤ T and (s, a) ∈ X, we haveP t (s, a) ⊇        p(s, a) ∈ P(s, a) : ∥ p(s, a) -pt (s, a)∥ 1 ≤ S log(2S AT ) T        It follows that, for all t ≤ T , the extended Bellman operator L t satisfies the prerequisite ( * ) of Lemma 15 with γ = 1 2 S log(2S AT/δ) T = Ω        S log(T/δ) T        .Under Assumption 1, we have M ∈ M t with probability 1 -δ. Under this event, M t is weakly communicating and sp (h * (M t )) ≤ D(M), we can apply Lemma 15 and conclude that every calls toPMEVI (Algorithm 2) takes O             sp (w 0 ) √ T ϵ S log(T/δ) T             = O       DT √ S log(T )      where we use that ϵ = log(S AT/δ) T , that sp (w 0 ) = O sp (h * (M t )) = O(D(M)) and that δ ≥ 1 T . Since the number of episodes under the doubling trick (DT) is O(S A log(T )), we conclude accordingly. □ Every call to the projection operator solves a linear program. Although in theory, this time is polynomial (relying on recent work on the complexity of LP such as Cohen et al. [2020] , it is the current matrix multiplication time O(S 2.38 )), in practice, reducing the number of calls to the projection operator is key to run PMEVI-DT in reasonable time.In this section, we fix the model region M, the bias region H and the mitigation vector β, dropping the sub-script t for conciseness. We denote r, p the respective empirical reward and kernel. Further assume that H = H 0 + Re with H 0 a compact convex set. The associated projection operation (see Appendix B.2) is denoted Γ. The (vanilla) extended Bellman operator L associated to M is given by Lu(s) := max a∈A(s) sup R(s, a) + sup P(s, a)u . The β-mitigated extended Bellman operator associated to M is: (16)L β u(s) := max a∈A(s)The function Greedy(M, u, β) returns a stationary deterministic policy that picks its actions among the one reaching the maximum above. The projection of L β to H isEQUATION)The goal of this section is to establish Proposition 2 and The main goal is to find and optimistic policy under bias constraints (projection) and bias error constraints (mitigation). The bias constraints imply that we search for a policy π together with a model M such that h π ( M) ∈ H. The bias error means that, for h ≡ h π ( M), we want in addition p(s, π(s)) h ≤ p(s, π(s)) h + β(s, π(s)) where p is the transition kernel of M. In the end, our goal is to track the solution of the following optimization problem:g * (H, β, M) := sup          g π ( M) : π ∈ Π, M ∈ M, ∀s ∈ S, p(s, π(s)) h ≤ p(s, π(s)) h + β(s, π(s)), h ≡ h π ( M) ∈ H, sp(g π ( M)) = 0          (18)where the supremum is taken with respect to the product order R S . In particular, if U ⊆ R S , check that u * = sup U is obtained as u * (s) := sup {v(s) : v ∈ U}. The constraint sp(g π ( M)) = 0 is suggested by the work of Fruit et al. [2018] , Fruit [2019] and is key for the problem to be solvable.The bias constraint and the constraint involving β make the problem impossible to handle with a "pure" extended MDP solution, which is why the extended Bellman operators are mitigated (with β) then projected (with Γ). The mitigation operation guarantees that the constraint involving β is satisfied, while the projection on H makes sure that the bias constraint is satisfied. It is important for both operations to be compatible, i.e., that the constraint involving β that L β forces is not lost when applying Γ. As a matter of fact, projecting then mitigating would not work.We now explain why L can be used to solve (18).We start by discussing why L is well-defined at all. The well-definition of L β is obvious. The point is to explain why the projection onto H is possible while preserving mandatory structural properties such as monotony, non-expansivity, linearity and more. For general H, such properties are impossible to meet. But the bias confidence region constructed with Algorithm 3 has a specific shape that makes the projection possible. The central property is the one below:(A1) The downward closure {v ≤ u : v ∈ H} of every u ∈ R S has a maximum in H.The only order that we will be considering is the product order on R S . Recall that a set U ⊆ R S has a maximum if there exists u ∈ U such that v ≤ u for all u ∈ U. A supremum of U is a minimal upper-bound of U, i.e., u such that (1) v ≤ u for all v ∈ U and (2) no w satisfying (1) can be smaller than u. For the product order, the supremum of a subset U is unique and of the form u(s) = sup {v(s) : v ∈ U}.Define the projection Γ : R S → H as such:EQUATIONIn general, Assumption (A1) is satisfied when H admits a join, i.e., is stable by finite supremum: u, v ∈ H ⇒ sup(u, v) ∈ H. Lemma 18. If H is generated by constraints of the form h(s)h(s ′ )c(s, s ′ ) ≤ d(s, s ′ ), then it has a join and (A1) is satisfied. Moreover, Γ is then correctly computed with Algorithm 4.Proof. The first half of the result is well-known, see Zhang and Xie [2023] , but we recall a proof for self-containedness. Let v 1 , v 2 ∈ H and definev 3 := sup(v 1 , v 2 ). Observe that v 3 (s) -v 3 (s ′ ) ≤ max(v 1 (s) -v 1 (s ′ ), v 2 (s) -v 2 (s ′ )) ≤ c(s, s ′ ) + d(s, s ′ ). So v 3 ∈ H.We continue by showing that if H has a join, then ( 19) is well-defined. For s ∈ S, take a sequence v s n such that v s n (s) → α(s) := sup {v(s) : v ≤ u, v ∈ H}. Because the span of every element of H is upper-bounded by c := sup sp (v) : v ∈ H , it follows that v s n evolves in the compact region {v ≤ u : v ∈ H} ∩ {v : ∥v -αse∥ ∞ = 1 + c}. We can therefore extract a convergent sequence of v s n , converging v s * that belongs to H since the latter is closed. By construction, v s * (s) = α(s). Because H has a join, v * := sup v s * : s ∈ S ∈ H. □ Lemma 19. Under assumption (A1), the operator Γu := max {v ≤ u : v ∈ H} is well-defined, and is:(1) monotone: u ≤ v ⇒ Γu ≤ Γv;(2) non span-expansive: sp (Γu -Γv) ≤ sp (uv);(3) linear: Γ(u + λe) = Γu + λe;(4) Γu ≤ u.Proof. The well-definition of Γ is obvious from (A1). For (2), if u ≤ v then w ≤ u ⇒ w ≤ v.Hence Γu := max {w ≤ u : w ∈ H} ≤ max {w ≤ v : w ∈ H} =: Γv. For (3), check that it follows from H = H + Re. For (4), we obviously have Γu := max {v ≤ u : v ∈ H} ≤ u.The more difficult point is (2) span non-expansivity. Pick u, v ∈ R S . By linearity, it suffices to show the result for s u(s) = s v(s). In that case, we have sp (vu) = max(vu) + max(uv). Observe that for all w ≤ u, we have w + min(vu)e ≤ v. Since H = H + Re, it follows that:max {w ≤ u : u ∈ H} ≤ max {w ≤ v : w ∈ H} + max(u -v)e.Similarly, we have max {w ≤ u : w ∈ H} ≥ max {w ≤ v : w ∈ H} + min(vu)e. Using them both at once, we find sp (Γu -Γv) ≤ sp (vu). □The properties (1), ( 3) and ( 4) are essential for L to properly address the optimization problem (18). The property (2) is just as important, because it plays a central part in the convergence of value iteration. The next result shows similar properties for the β-mitigated extended Bellman operator L β . From now on, we will assume (A1), because it is almost-surely satisfied by the bias confidence region generated by Algorithm 3. Lemma 20. The β-mitigated extended Bellman operator L β is (1) monotone, (2) non-span-expansive and (3) linear.Proof. The properties (1) and (3) directly follow from the definition. We focus on (2). Fix u, u ′ ∈ R S . By Lemma 26, we can write L β u = rπ + Pπ u and L β u ′ = rπ ′ + Pπ ′ u ′ . In the following, we write β π (s) := β(s, π(s)). Check that:L β u -L β u ′ = rπ + Pπ u -rπ ′ + Pπ ′ u ′ ≤ rπ + Pπ u -rπ + min Pπ u ′ , Pπ u ′ + β π .If the minimum is reached with Pπ u ′ , then:L β u -L β u ′ ≤ Pπ (u -u ′ ).If the minimum is reached with Pπ u ′ + β π , then upper-bound Pπ u by Pπ u + β π to obtain:L β u -L β u ′ ≤ Pπ (u -u ′ ).Overall, we find that there existsQ π ∈ P π such that L β u -L β u ′ ≤ Q π (u -u ′ ). Similarly, we find Q π ′ ∈ P π ′ such that L β u -L β u ′ ≥ Q π ′ (u -u ′ ). We conclude that: sp L β u -L β u ′ ≤ sp (Q π -Q π ′ )(u -u ′ ) ≤ sp u -u ′ .This concludes the proof. □By composition, we obtain the following result.Corollary 21. L is (1) monotone, (2) non-span-expansive and (3) linear. Moreover, sp (Lu -Lv) ≤ sp (Lu -Lv) for all u, v ∈ R S .Lemma 22. L has a fix-point in span semi-norm, i.e., ∃u ∈ H, sp (Luu) = 0.Proof. The idea is to apply Brouwer's fix-point theorem in R S quotiented by the equivalence relation u ∼ v ⇔ sp (uv) = 0, where sp (-) becomes a norm. By linearity (Corollary 21), L is well-defined in this quotient space, and if L is shown continuous on R S , so will it be on the quotient.We show that L is sequentially continuous on H. Consider a sequence u n ∈ H N converging to u ∈ H and fix ϵ > 0. Provided that n > N ϵ for N ϵ large enough, we have ∥u n -u∥ ∞ < ϵ, i.e., u n -ϵe ≤ u n ≤ u + ϵe. Therefore, in the one hand, for all v ≤ u n , we have v -ϵe ≤ u so max {v ≤ u n : v ∈ H} ≤ max {v ≤ u : v ∈ H} + ϵe; And on the other hand, for all v ≤ u, v + ϵe ≤ u n so max {v ≤ u : v ∈ H} ≤ max {v ≤ u n : v ∈ H} + ϵe. Hence:∥max {v ≤ u : v ∈ H} -max {v ≤ u n : v ∈ H}∥ ≤ ϵ.It shows that Γ is continuous. The operator L β is obviously continuous as well, so L = Γ • L β is continuous by composition. Since H = H 0 + Re with H 0 compact and ocnvex, the quotient H/∼ is compact and convex, and is preserved by L/∼. By Brouwer's fix-point theorem, L/∼ has a fix-point in H/∼. So L has a span fix-point in H. □We write Fix(L) the span fix-points of L. Lemma 23. L has well-defined growth. Specifically, if Lu = u + ge, then:(1) There exists c > 0, s.t., for all v ∈ H 0 , (ngc)e + u ≤ L n v ≤ (ng + c)e + u;(2) If u ′ ∈ Fix(L), then Lu ′u ′ = ge.Proof. Setting c := max v∈H 0 ∥v -u∥ ∞ < ∞, one can check that uce ≤ v ≤ u + ce for all v ∈ H 0 . this proves (1) for n = 0 and we then proceed by induction on n ≥ 0. By induction, L n v ≤ u + (ng + c)e and by Corollary 21, L is monotone, so we have:L n+1 v ≤ LL n v ≤ L(u + (ng + c)e) = u + ((n + 1)g + c)ewhere the last inequality use the linearity of L together with Lu = u + ge. The lower bound of L n v is shown similarly, establishing (1).For (2), pick u ′ ∈ Fix(L) with Lu ′ = u ′ + g ′ e. Up to translating u ′ , we can assume that u ′ ∈ H 0 and apply (1). We get: (ngc)e + u ≤ ng ′ e + u ′ ≤ (ng + c)e + u. Divided by n and let it go to infinity. We conclude that g = g ′ . □We finally have everything in hand to claim that L solves (18).Corollary 24. The growth of L given by g = Luu for u ∈ Fix(L) is well-defined, and:∀u ∈ H, ge = lim inf n→∞ L n u n = lim sup n→∞ L n u n .Moreover, g ≥ g * (H, β, M).Proof. The growth property is a direct consequence of Lemma 23. We show g ≥ g * (H, β, M) which is defined in (18). Pick π ∈ Π, M ∈ M its model with h ≡ h(π, M) and Pπ h ≤ Pπ h + β π where β π (s) := β(s, π(s)). Up to translation, we can assume that h ∈ H 0 .We have g(π, M) = ge for g ∈ R, so h + ge = rπ + Pπ h ≤ L h by definition. By monotony of L, see Corollary 21, nge + h ≤ L n h follows by induction on n ≥ 0. By Lemma 23, we further have L n h ≤ n(g + c)e + u where u ∈ Fix(L). In tandem,ge ≤ ge + ce + u - h n .Letting n → ∞, we deduce that g ≤ g. Conclude by taking the best π and M. □The next theorem follows directly with the same proof technique, and guarantees optimism.Theorem 25. Assume that g * + h * ≤ Lh * . Then g ≥ g * .The condition "g * + h * ≤ Lh * " can be referred to as a weak form of optimism. We qualify this version of optimism as weak because it is much weaker than optimism property suggested by Fruit [2019] L ≥ L where L is the Bellman operator of the true MDP. Here, we only ask for Lh * ≥ Lh * , i.e., optimism at a span fix-point of L. This condition is met as soon as M ∈ M, h * ∈ H and β large enough.The aim of this paragraph is to establish Corollary 27, stating that Lu can be viewed as a policy produced by Greedy(M, u, β). Lemma 26 (Modelization). For π ∈ Π, denote β π (s) := β(s, π(s)), R π := s R(s, π(s)) and P π := s P(s, π(s)). Fix u ∈ R S and let π := Greedy(M, u, β).(1) If P is convex, then there exists (r π , Pπ ) ∈ R π × P π such that L β u = rπ + Pπ u.(2) Assume that L β u = rπ + Pπ u. There exists r ′ π ≤ rπ such that Lu = r ′ π + Pπ u.The convexity requirement of (1) is always true if the kernel confidence region is chosen via (C1-4).Proof. For (1), fix a state s ∈ S, let a := π(s) and ρ := min(sup P(s, a)u, p(s, a)u + β(s, a)). If ρ = sup P(s, a)u, then there is nothing to say because P is compact, hence the sup is a max and ρ is of the form p(s, a)u. Otherwise, let p(s, a)u > p(s, a)u + β(s, a) with p(s, a) ∈ P(s, a). Introduce, for λ ∈ [0, 1], pλ (s, a) := λ p(s, a) + (1 -λ) p(s, a). By continuity, there exists λ ∈ (0, 1) such that pλ (s, a)u = p(s, a)u + β(s, a) and by convexity of P(s, a), pλ (s, a) ∈ P(s, a). This proves (1).For (2), recall that Lu = ΓL β u = Γ(r π + Pπ u). Since Γv ≤ v, for v ∈ R S , we have:Γ(r π + Pπ u) ≤ rπ + Pπ u. Set r ′ π := Γ(r π + Pπ u) -Pπ u. Check that r ′ π satisfies r ′ π ≤ rπ and Lu = r ′ π + Pπ u. □The last corollary bellow is crucial to claim that greedy policies are good choices in PMEVI-DT.Corollary 27 (Greedy modelization). Let u ∈ R S and fix π := Greedy(M, u, β). If P is convex, then with the notations of Lemma 26, there exists rπ ≤ sup R π and Pπ ∈ P π such that Lu = rπ + Pπ u.Notations. At episode k, the played policy is denoted π k . As a greedy response to h k , by Proposition 2 (3), there exists rk (s) ≤ sup R t k (s, π k (s)) and Pk (s) ∈ P t k (s, π(x)) such that h k + g k = rk + Pk h k .The reward-kernel pair Mk = (r k , Pk ) is referred to as the optimistic model of π k . We write P k := P π k (M) the true kernel and Pk := P π k ( Mt k ) the empirical kernel. Likewise, we define the reward functions r k and rk . The optimistic gain and bias satisfy g k = g(π k , M k ) andh k = h(π k , M k ).We further denote c 0 = T 1 5 .Important remark. To slightely simplify the analysis, we assume that PMEVI is run with perfect precision ϵ = 0, i.e., thath k = PMEVI(M t k , β t k , Γ t k , 0) hence is a span fix-point of L t k .This assumption is mild and can be dropped by adding an extra error term that has to be carried out in the calculations.Lemma 28 (Number of episodes, Auer et al. [2009] ). The number of episodes up to time T ≥ S A is upper-bounded by: K(T ) ≤ S A log 2 8T S A .The Lemma 29 below shows that T -1 t=0 V(p(X t ), h * ) scales as T sp (h * )sp (r) + sp (h * ) Reg(T ) in probability. Lemma 29. With probability at least 1 -δ, we have:T -1 t=0 V(p(X t ), h * ) ≤ 2sp (h * )sp (r)T + sp (h * ) 2 1 2 T log 1 δ + 2sp (h * ) T -1 t=0 ∆ * (X t ) + sp (h * ) 2 .Proof. Using the Bellman equation h * (s) + g * (s) = r(s, a) + p(s, a)h * + ∆ * (s, a), we have:V(p(X t ), h * ) = p(X t ) -e S t h * 2 + 2h * (S t )(∆ * (X t ) + r(X t ) -g * (S t )).Since sp h * 2 ≤ sp (h * ) 2 , we get:T -1 t=0 V(p(X t ), h * ) ≤ T -1 t=0 p(X t ) -e S t h * 2 + 2sp (h * ) sp (r)T + T -1 t=0 ∆ * (X t ) = T -1 t=0 p(X t ) -e S t+1 h * 2 + 2sp (h * ) 1 2 sp (h * )sp (r)T + T -1 t=0 ∆ * (X t ) (Lemma 32) ≤ 2sp (h * )sp (r)T + sp (h * ) 2 1 2 T log 1 δ + 2sp (h * ) T -1 t=0 ∆ * (X t ) + sp (h * ) 2where the last inequality holds with probability 1 -δ. This concludes the proof. □In this paragraph, we bound the regret with respect to the pseudo-regret (and conversely) up to a factor of order (sp (h * )sp (r) log( T δ )) 1/2 . Hence, in proofs, the pseudo-regret can be changed to the regret with ease. Lemma 30. With probability 1 -4δ, the regret and the pseudo-regret and linked as follows:T -1 t=0 (g * -R t ) - T -1 t=0 ∆ * (X t ) ≤          2 2sp (h * )sp (r) + 1 8 T log T δ + 2sp (h * ) log T δ T -1 t=0 ∆ * (X t ) +sp (h * ) 1 2 T 1 4 log 3 4 T δ + 4sp (h * ) log T δ + 2sp (h * )          .Proof. We rely again on the Poisson equation g * (S t )r(X t ) -∆ * (X t ) = (p(X t )e S t )h * , so:A := T -1 t=0 (g * -R t -∆ * (X t )) ≤ T -1 t=0 p(X t ) -e S t h * + T -1 t=0 (R t -r(X t )) ≤ sp (h * ) + T -1 t=0 p(X t ) -e S t+1 h * + T -1 t=0 (R t -r(X t )) .Up to the constant sp (h * ), the two error terms are respectively a navigation and a reward error. The second is bounded using Azuma's inequality (Lemma 32), showing that with probability 1 -2δ, we have:T -1 t=0 (R t -r(X t )) ≤ 1 2 T log 1 δ .We continue by using Freedman's inequality, instantiated in the form of Lemma 33. With probability 1 -δ, we have:T -1 t=0 p(X t ) -e S t+1 h * ≤ 2 T -1 t=0 V(p(X t ), h * ) log T δ + 4sp (h * ) log T δ .The quantity T -1 t=0 V(p(X t ), h * ) is a classical one that appears at several places throughout the analysis. Using Lemma 29, we bount it explicitely. Further simplifying the bound with√ a + b ≤ √ a +√ b, we get that with probability 1 -4δ, we have:A ≤          2sp (h * )sp (r)T log T δ + 1 2 T log 1 δ + 2sp (h * ) log T δ T -1 t=0 ∆ * (X t ) +sp (h * ) 1 2 T 1 4 log 3 4 T δ + 4sp (h * ) log T δ + 2sp (h * )         .Bound log( 1 δ ) by log( T δ ) and use√ a + √ b ≤ 2 √ a + b to merge the terms in T log( T δ ) under a single square-root. □Overall, Lemma 30 states that the regret T -1 t=0 (g * -R t ) and the pseudo-regret T -1 t=0 ∆ * (X t ) differ by about (sp (h * )T log( T δ )) 1/2 in probability (up to asymptotically negligible additional terms). In general, the precise form of Lemma 30 is not convenient to use because it is of form form x ≤ y + α √ y + β that is not linear in y. Corollary 31 factorizes the result into one which will be more convenient in proofs.Corollary 31. Denote x := T -1 t=0 (g * -R t ) and y := T -1 t=0 ∆ * (X t ). Further introduce:α := 2sp (h * ) log T δ β := 2 2sp (h * )sp (r) + 1 2 T log T δ + sp (h * ) 1 2 T 1 4 log 3 4 T δ + 2sp (h * ) 2 log T δ + 1 .Then, with probability 1 -4δ, we have√ x ≤ √ y + 1 2 α + √ β and √ y ≤ √ x + α + √ β.Proof. This is straight forward algebra from the result of Lemma 30. □We start by getting rid of the reward noise. We have:Reg(T ) := T -1 t=0 (g * -R t ) = T -1 t=0 (g * -r(X t )) + T -1 t=0 (r(X t ) -R t ) ≤ T -1 t=0 (g * -r(X t )) + 1 2 T log 1 δwith probability 1 -δ by Azuma's inequality (Lemma 32). We are left with T -1 t=0 (g *r(X t )). We continue by splitting the regret episodically and invoking optimism. By Lemma 13, with probability 1 -4δ, we haveEQUATION)We focus on bounding B 0 (T ). By Assumption 2, rk (s, a) is of the form rk (s, a) + C log(2S AT/δ)/N t k (s, a) -η k (s, a) with η k (s, a) ∈ R. By the statement (3) of Proposition 2, η k (s, a) ≥ 0. Therefore,B 0 (T ) = k t k+1 -1 t=t k (g k -rk (X t )) + k t k+1 -1 t=t k ( rk (X t ) -r(X t )) ≤ k t k+1 -1 t=t k (g k -rk (X t )) + S A + k t k+1 -1 t=t k 1 N t k (X t ) ≥ 1            rk (X t ) -r(X t ) + C log 2S AT δ N t k (X t )            ( * ) ≤ k t k+1 -1 t=t k (g k -rk (X t )) + S A + k t k+1 -1 t=t k 1 N t k (X t ) ≥ 1            2 log 2S AT δ N t k (s, a) + C log 2S AT δ N t k (s, a)           where ( * ) holds with probability 1 -δ following Lemma 35. By the doubling trick rule (DT), we have N t (X t ) ≤ 2N t k (X t ) for t < t k+1 , so, with probability 1 -δ,B 0 (T ) ≤ k t k+1 -1 t=t k (g k -rk (X t )) + S A + 2 k t k+1 -1 t=t k 1 N t k (X t ) ≥ 1 (2 + C) log 2S AT δ N t k (s, a) ≤ k t k+1 -1 t=t k (g k -rk (X t )) + S A + 2 (2 + C) log 2S AT δ s,a N T (s,a)-1 n=1 1 n ≤ k t k+1 -1 t=t k (g k -rk (X t )) + S A + 4 (2 + C) log 2S AT δ s,a N T (s, a) (Jensen) ≤ k t k+1 -1 t=t k (g k -rk (X t )) + S A + 4 (2 + C)S AT log 2S AT δ .We conclude that with probability 1 -6δ, we have:EQUATIONThis concludes the proof. □We have:k t k+1 -1 t=t k (p k (S t ) -e S t )h k ≤ k t k+1 -1 t=t k (p k (S t ) -e S t+1 )h k + k sp (h k ) ≤ k t k+1 -1 t=t k (p k (S t ) -e S t+1 )(h k -h * ) A 1 + k t k+1 -1 t=t k (p k (S t ) -e S t+1 )h * A 2 + k sp (h k ).The last term is O(c 0 S A log(T )) by Lemma 28, hence is O(T 1/5 log(T )).(STEP 1) We start by bounding A 1 . By Lemma 13, with probability 1 -4δ, we haveh * ∈ H t k for all k ≤ K(T ). So sp (h k -h * ) ≤ sp (h k ) + sp (h * ) ≤ 2c 0. By Freedman's inequality invoked in the form of Lemma 33, we have with probability 1 -5δ,A 1 ≤ 2 k t k+1 -1 t=t k V (p(X t ), h k -h * ) log T δ + 8c 0 log T δIt suffices to bound the first term. Recall that e is the vector full of ones. We have:k t k+1 -1 t=t k V(p(X t ), h k -h * ) = k t k+1 -1 t=t k V (p(X t ), h k -h * -(h k (S t ) -h * (S t )) • e) ≤ k t k+1 -1 t=t k s ′ ∈S p(s ′ |X t ) h k (s ′ ) -h * (s ′ ) -(h k (S t ) -h * (S t )) 2 ( * ) ≤ 3 k t k+1 -1 t=t k E         s ′ ∈S p(s ′ |X t ) h k (s ′ ) -h * (s ′ ) -(h k (S t ) -h * (S t )) 2 F t         + 16c 2 0 log 1 δ = 3 k t k+1 -1 t=t k (h k (S t+1 ) -h * (S t+1 ) -(h k (S t ) -h * (S t ))) 2 + 16c 2 0 log 1 δ .Here the inequality ( * ) holds with probability 1 -δ following Lemma 40. We will bound the summand with the bias estimation error error(c k , s, s ′ ) that spawns the inner regret estimationB 0 (t k ) = k-1 ℓ=1 t ℓ+1 -1 t=t ℓ (g ℓ -R t ). This inner estimation is linked to B(T ) := k,t (g k -R t ) the overall optimistic regret by:B 0 (t k ) ≤ K(T ) ℓ=1 t ℓ+1 -1 t=t ℓ (g k -R t ) - K(T ) ℓ=k t ℓ+1 -1 t=t ℓ (g k -R t ) ( * ) ≤ K(T ) ℓ=1 t ℓ+1 -1 t=t ℓ (g k -R t ) - K(T ) ℓ=k t ℓ+1 -1 t=t ℓ (g * -R t ) ≤ K(T ) ℓ=1 t ℓ+1 -1 t=t ℓ (g k -R t ) - K(T ) ℓ=k T -1 t=t k ∆ * (X t ) + p(X t ) -e S t h * + r(X t ) -R t ≤ K(T ) ℓ=1 t ℓ+1 -1 t=t ℓ (g k -R t ) + sp (h * ) - K(T ) ℓ=k T -1 t=t k p(X t ) -e S t+1 h * + r(X t ) -R t ( †) ≤ K(T ) ℓ=1 t ℓ+1 -1 t=t ℓ (g k -R t ) + sp (h * ) + (1 + sp (h * )) 1 2 T log 1 δ =: B(T ) + sp (h * ) + (1 + sp (h * )) 1 2 T log 1 δ .In the above, ( * ) holds with probability 1 -4δ uniformly on k following Lemma 13 and ( †) holds, also uniformly on k, with probability 1 -δ by applying Azuma-Hoeffding's inequality (Lemma 32). Continuing, still on the event specified by Lemma 13, we have with probability 1 -6δ:k t k+1 -1 t=t k V(p(X t ), h k -h * ) ≤ 3 k t k+1 -1 t=t k 3c 0 + (1 + c 0 ) 8t k log 2 δ + 2B 0 (t k ) N t k (S t+1 ↔ S t ) + 16c 2 0 log 1 δ ≤ 3 k t k+1 -1 t=t k 4c 0 + (1 + c 0 ) 32T log 2 δ + 2B(T ) N t k (S t , A t , S t+1 ) + 16c 2 0 log 1 δ (DT) ≤ 12c 2 0 S 2 A + 3 4c 0 + (1 + c 0 ) 32T log 2 δ + 2B(T ) S 2 A log(T ) + 16c 2 0 log 1 δ .(STEP 2) For A 2 , by Freedman's inequality invoked in the form of Lemma 33 again, we have with probability 1 -δ,A 2 ≤ 2 k t k+1 -1 t=t k V(p k (S t ), h * ) log T δ + 8c 0 log T δ ≤ 2 T -1 t=0 V(p(X t ), h * ) log T δ + 8c 0 log T δ .We recognize the sum of variance T -1 t=0 V(p(X t ), h * ) that we leave as is. (STEP 3) As a result, with probability 1 -7δ, we have:k tk+1-1 t=tk (p k (S t ) -e S t )h k ≤ 2 T -1 t=0 V(p(X t ), h * ) log T δ + 2S A 1 2 3B(T ) log T δ + O S A 1 2 T 7 20 log 3 4 T δ when c 0 = T 1 5 . □ C.Because of the β-mitigation generated by Algorithm 5, the quantity ( pk (S t )pk (S t ))h k is shown to be directly related to V(p(X t ), h * ) up to a provably negligible error. Denote h ′ k the reference point BiasProjection(H t k , c t k (-, s 0 )) used in Algorithm 5 (denoted h 0 in the algorithm). By Lemma 13, with probability 1 -4δ, we have h * ∈ H t k for all k. To lighten up notations, we write d t k (s ′ , s) instead of error(c t k , s ′ , s).(STEP 1) Denote A := ( pk (S t )pk (S t ))h k . By construction of pk , we have A ≤ β t k (X t ), so:A ≤ β t k (X t ) =: 2 V( pk (S t ), h ′ k ) + 8c 0 s ′ ∈S pk (s ′ |S t )d t k (s ′ , S t ) log S AT δ N t k (X t ) + 3c 0 log S AT δ N t k (X t ) ≤ 2V( pk (S t ), h ′ k ) N t k (X t ) A 1 + 16c 0 s ′ ∈S pk (s ′ |S t )d t k (s ′ , S t ) log S AT δ N t k (X t ) A 2 + 3c 0 log S AT δ N t k (X t ) .The rightmost term of A is of order O(log 2 (T )) hence is negligible. We focus on the other two. The analysis of A 1 will spawn a term similar to A 2 , hence we start by the second. Recall that d t k is the bias error provided by Algorithm 3 and that the inner regret estimation isB 0 (t k ) = k-1 ℓ=1 t ℓ+1 -1 t=t ℓ (g ℓ -R t ). Now, remark that: B 0 (t k ) ≤ K(T ) ℓ=1 t ℓ+1 -1 t=t ℓ (g k -R t ) - K(T ) ℓ=k t ℓ+1 -1 t=t ℓ (g k -R t ) ( * ) ≤ K(T ) ℓ=1 t ℓ+1 -1 t=t ℓ (g k -R t ) - K(T ) ℓ=k t ℓ+1 -1 t=t ℓ (g * -R t ) ≤ K(T ) ℓ=1 t ℓ+1 -1 t=t ℓ (g k -R t ) - K(T ) ℓ=k T -1 t=t k ∆ * (X t ) + p(X t ) -e S t h * + r(X t ) -R t ≤ K(T ) ℓ=1 t ℓ+1 -1 t=t ℓ (g k -R t ) + sp (h * ) - K(T ) ℓ=k T -1 t=t k p(X t ) -e S t+1 h * + r(X t ) -R t ( †) ≤ K(T ) ℓ=1 t ℓ+1 -1 t=t ℓ (g k -R t ) + sp (h * ) + (1 + sp (h * )) 1 2 T log 1 δ =: B(T ) + sp (h * ) + (1 + sp (h * )) 1 2 T log 1 δ .In the above, ( * ) holds with probability 1 -4δ uniformly on k following Lemma 13 and ( †) holds, also uniformly on k, with probability 1 -δ by applying Azuma-Hoeffding's inequality (Lemma 32). Therefore, with probability 1 -5δ, for all k and t ∈ {t k , . . . , t k+1 -1}, we have:16c 0 s ′ ∈S pk (s ′ |S t )d t k (s ′ , S t ) log S AT δ N t k (X t ) ≤ 16c 0 log S AT δ s ′ ∈S N t k (S t , A t , s ′ )d t k (s ′ , S t ) N t k (X t ) ≤ 16c 0 log S AT δ s ′ ∈S N t k (S t ↔ s ′ )d t k (s ′ , S t ) N t k (X t ) ≤ 16c 0 log S AT δ S 3c 0 +(1+c 0 ) 1+ 8T log 2 δ +2B 0 (t k ) N t k (X t ) ≤ 16c 0 log S AT δ S (1+c 0 ) 3+2 8T log 2 δ +2B(T ) N t k (X t ) ≤ 16c 0 log S AT δ S (1+c 0 ) 3+2 8T log 2 δ +2B(T ) N t k (X t ). This bound will be enough. We move on to A 1 . We have:V( pk (S t ), h ′ k ) ≤ V( pk (S t ), h ′ k ) -V(p(X t ), h * ) + V(p(X t ), h * ) ≤ V( pk (S t ), h ′ k ) -V( pk (X t ), h * ) |V( pk (S t ), h * ) -V(p(X t ), h * )| + V(p(X t ), h * ) ( * ) ≤ 8c 0 s ′ ∈S pk (s ′ |S t )d k (s ′ , S t ) + sp (h * ) ∥ pk (S t ) -p k (S t )∥ 1 + V(p(X t ), h * ) ( †) ≤ 8c 0 s ′ ∈S pk (s ′ |S t )d k (s ′ , S t ) + sp (h * )         S log S AT δ N t k (X t )         1 4 + V(p(X t ), h * ) ≤ A 2 2N t k (X t ) + sp (h * )         S log S AT δ N t k (X t )         1 4 + V(p(X t ), h * )where ( * ) is obtained by applying Lemma 12 and ( †) holds with probability 1 -δ by applying Weissman's inequality, see Lemma 35. All together, with probability 1 -6δ, A is upper-bounded by:A ≤ 2V(p(X t ), h * ) log S AT δ N t k (X t ) + 2A 2 + sp (h * ) 2 log S AT δ S log S AT δ N t k (X t ) N t k (X t ) + 3c 0 log S AT δ N t k (X t ) A 3 (k,t).(STEP 2) The number of visits N k (X t ) is lower-bounded by 1 2 N t (X t ) when N k (X t ) ≥ 1 by doubling trick (DT). By summing over t and k, we find that with probability 1 -6δ,k (3k) ≤ S Ac 0 + k t k+1 -1 t=t k 1 N t k (X t )≥1 2V(p(X t ), h * ) log S AT δ N t k (X t ) + k t k+1 -1 t=t k 1 N t k (X t )≥1 (2A 2 (k, t) + A 3 (k, t)) (DT) ≤ S Ac 0 + 2 k t k+1 -1 t=t k 1 N t k (X t )≥1 2V(p(X t ), h * ) log S AT δ N t (X t ) + k t k+1 -1 t=t k 1 N t k (X t )≥1 (2A 2 (k, t) + A 3 (k, t)) ≤ S Ac 0 + 4 2S A T -1 t=0 V(p(X t ), h * ) log S AT δ + k t k+1 -1 t=t k 1 N t k (X t )≥1 (2A 2 (k, t) + A 3 (k, t))where the last inequality is obtained with computations that are similar to those detailed in the proof of Lemma 8. We recognize the variance that we will leave as is. We finish the proof by bounding the lower order terms A 2 and A 3 .(STEP 3) We start with A 2 . We have:k t k+1 -1 t=t k 1 N t k (X t )≥1 A 2 (k, t) := k t k+1 -1 t=t k 1 N t k (X t )≥1 16c 0 log S AT δ S (1+c 0 ) 3+2 8T log 2 δ +2B(T ) N t k (X t ) (DT) ≤ 2 16c 0 S log S AT δ (1 + c 0 ) 3 + 2 8T log 2 δ + 2B(T ) S A log(T ) ≤ 8(1 + c 0 )S 3 2 A log 3 2 1 4 log 3 4 S AT δ + 6c 0 S A log S AT δ = O sp (h * )S 5 4 AT 1 4 log S AT δ .This concludes the proof. □C.8 Proof of Lemma 10, second order errorRecall that by Lemma 13, with probability 1 -4δ, h * ∈ H t k for all k, hence sp (h kh * ) ≤ 2c 0 for all k on the same event. Therefore, with probability 1 -4δ,k (4k) := 2c 0 S A + k t k+1 -1 t=t k 1 N t k (X t )≥1 ( pk (S t ) -p k (S t )) (h k -h * ) = 2c 0 S A + k t k+1 -1 t=t k s ′ ∈S 1 N t k (X t )≥1 ( pk (s ′ |S t ) -p k (s ′ |S t ))(h k -h * (s ′ )) ( * ) ≤ 2c 0 S A + 2 k t k+1 -1 t=t k s ′ ∈S 1 N t k (X t )≥1 ( pk (s ′ |S t ) -p k (s ′ |S t ))d t k (s ′ , S t ) ( †) ≤ 2c 0 S A + 2 k t k+1 -1 t=t k s ′ ∈S 1 N t k (X t )≥1            d k (s ′ , S t ) 2 pk (s ′ |S t ) log S 2 AT δ N t k (X t ) + 3d k (s ′ |S t ) log S 2 AT δ N t k (X t )            ≤ 2c 0 S A + 2 k t k+1 -1 t=t k s ′ ∈S 1 N t k (X t )≥1            √ c 0 2 pk (s ′ |S t )d k (s ′ , S t ) log S 2 AT δ N t k (X t ) + 3c 0 log S 2 AT δ N t k (X t )            ≤ 2c 0 S A + 4 k t k+1 -1 t=t k s ′ ∈S 1 N t k (X t )≥1            √ c 0 2 pk (s ′ |S t )d k (s ′ , S t ) log S 2 AT δ N t (X t ) + 3c 0 log S 2 AT δ N t (X t )           where ( * ) uses that h * ∈ H t k , and ( †) is obtained by applying the empirical Bernstein's inequality, see Lemma 36, to pk (s ′ |S t )p k (s ′ |S t ), and holds with probability 1 -δ. The rightmost term's sum is upper-bounded by:4 k t k+1 -1 t=t k s ′ ∈S 3c 0 log S 2 AT δ N t (X t ) ≤ 12S 2 A log(T ) log S 2 AT δ .For the other term, follow the line of the proof of Lemma 9 (term A 2 ). We have with probability 1 -5δ (4δ of which is by invoking Lemma 13):pk (s ′ |S t )d k (s ′ , S t ) = N t k (S t , A t , s ′ ) (1 + c 0 ) 1 + 8t k log 2 δ + 2B 0 (t k ) N t k (S t ↔ s ′ )N t k (X t ) ≤ (1 + c 0 ) 3 + 2 8T log 2 δ + 2B(T ) N t k (X t ).Therefore,√ c 0 2 pk (s ′ |S t )d t k (s ′ , S t ) log S 2 AT δ N t (X t ) ≤ 4(1 + c 0 ) 3 + 2 8T log 2 δ + 2B(T ) log S 2 AT δ N t (X t ) .Summing over k, t, s ′ , with probability 1 -6δ, we have:k (4k) ≤          16S 2 A(1 + c 0 ) log 1 2 S 2 AT δ √ 2B(T ) + 2 8T log 2 δ 1 4 +32S 2 A log(T ) log S 2 AT δ + (1 + c 0 ) log 1 2 S 2 AT δ         This concludes the proof. □ 3-state river-swim. The gain is g * ≈ 0.82 and h * ≈ (-4.28, -2.24, 0.4).5-state river-swim. The gain is g * ≈ 0.82 and h * ≈ (-9.62, -7.58, -4.96, -2.27, 0.45) .Beyond communicating models, PMEVI-DT is superior to EVI-based methods. On Fig. 4 , we see that PMEVI-DT can learn in environments of infinite diameter while UCRL2 cannot. The gain is due to the truncation operation, that makes sure that the optimistic bias vector has span less than T 1/5 . Without the truncation operation, EVI-based methods can never reject the plausibility that the reward at s 0 is maximal (equal to one) and that there is a positive probability ϵ to switch from s 1 to s 0 when taking the sub-optimal action from s 1 . More precisely, denote the actions a, b where r(s 0 , a) = 1, r(s 1 , a) = 0.5 and r(s 1 , b) = 0.1, so that a is the optimal action and b is sub-optimal. There are two policies π a and π b choosing action a and b from s 1 respectively. Because s 0 is only visited once, the best reward that can be achieved from s 0 is rt (s 0 , a) = 1 at all times. If one runs UCRL2, the confidence region for transition kernels is roughly of the form P t (x) = { p(x) : N t (x) ∥ p(x)pt (x)∥ 2 1 ≤ C p log(t)} and the plausible transition kernel p(x) ∈ P t (x) that goes the quickest from s 1 to s 0 is of the form: After running EVI for i steps, the current vector v i (see ( 6)) is V * i (M t ), the maximal amount of reward that one can collect in i steps on M t seen as an extended Markov decision process, see Auer et al. [2009] . If the data is well concentrated, the optimal reward from s 1 are respectively rt (s 1 , a) ≈ 0.5 + C r log(t)/N t (s 1 , a) and rt (s 1 , b) = 0.1 + C r log(t)/N t (s 1 , b). From all this, one can argue that when i is large enough, the optimistic scores of π a and π b over i steps are roughly equal to:s 0 s 1 1 0.5 0.1 U C R L 2 PMEVIV π a i (s 1 ; M t ) ≈ i +          -0.5 + C r log(t) N t (s 1 , a)          N t (s 1 , a) C p log(t) = i -0.5 N t (s 1 , a) C p log(t) + C r C p V π b i (s 1 ; M t ) ≈ i +          -0.9 + C r log(t) N t (s 1 , b)          N t (s 1 , b) C p log(t) = i -0.9 N t (s 1 , b) C p log(t) + C r C p . So V π a i (s 1 ; M t ) ≤ V π b i (s 1 ; M t ) if N t (s, b) ≪ 25 81 N t (s, a). This means that EVI will output π b if N t (s, b) ≪ 2581 N t (s, a), leading to N t (s, a) ≍ N t (s, b) so both growing linearly with t. This informal argument can be generalized to EVI-based algorithms with other types of confidence regions: EVI-based methods such as UCRL Auer et al. [2002] , UCRL2B Fruit et al. [2020] and KLUCRL Filippi et al. [2010] will suffer from N t (s, b) = Θ(t) and their regret will grow linearly.In opposition, PMEVI-based methods use truncation, making sure that |v i (s 1 )v i (s 0 )| ≤ T 1/5 at all times. Intuitively, it makes PMEVI-based method "think" that pt (s 0 |s 1 , b) cannot be as small as C p log(t)/N t (s 1 , b), because the optimistic bias of π b would be too large otherwise; Or, equivalently, that pt (s 0 |s 1 , b) = C p log(t)/N t (s 1 , b) but with rt (s 0 , a) ≪ 1, hence killing the optimistic reward at (s 0 , a) to meet the bias constraints.Overall, these features of PMEVI-based methods are shared with algorithms such as REGAL Bartlett and Tewari [2009] and SCAL Fruit et al. [2018] . The difference is that these methods require precise prior information on sp(h * ) that PMEVI-DT does not need.Lemma 32 (Azuma's inequality, Azuma [1967] ). Let (U t ) t≥0 a martingale difference sequence such that sp (U t ) ≤ c a.s., i.e., there exists a t ∈ R such that a t ≤ U t ≤ a t + c a.s. Then, for all δ > 0,P T -1 t=0 U t ≥ c 1 2 T log 1 δ ≤ δ.Lemma 33 (Freedman's inequality, Zhang et al. [2020] ). Let (U t ) t≥0 a martingale difference sequence such that |U t | ≤ c a.s., and denote its conditional variance Vt := E[U 2 t |F t-1 ].Then, for all δ > 0,P        ∃T ′ ≤ T : T ′ -1 t=0 U t ≥ 2 T ′ -1 t=0 V t log T δ + 4c log T δ        ≤ δ.Lemma 34 (Time-uniform Azuma, Bourel et al. [2020] ). Let (U t ) a martingale difference sequence such that, for all λ ∈ R, E[exp(λU t )|U 1 , . . . , U t-1 ] ≤ exp( λ 2 σ 2 2 ). Then:∀δ > 0, P ∃n ≥ 1, n k=1 U k 2 ≥ nσ 2 1 + 1 n log √ 1+n δ ≤ δ.Lemma 35 (Time-uniform Weissman). Let q a distribution over {1, . . . , d}. Let (U t ) a sequence of i.i.d. random variables of distribution q. Then:∀δ > 0, P ∃n ≥ 1, n i=1 e U i -q 2 1 ≥ nd log 2 √ 1+n δ ≤ δ. Proof. Remark that n k=1 (e U k -q) 1 = max v∈{-1,1} d n k=1 e U k -q, v . Let W v k := e U k -q, v . Re- mark that for each v ∈ {-1, 1} d , (W v k ) is a family of i.i.d. random variables with -⟨q, v⟩ ≤ W v k ≤ 1 -⟨q, v⟩, so E[exp(λW v k )] ≤ exp( λ 2 8) by Hoeffding's Lemma. By Lemma 34, we have:P         ∃n ≥ 1, n k=1 (e U k -q) 1 ≥ nd log 2 √ 1+n δ         = P        ∃v ∈ {-1, 1} d , ∃n, n k=1 W v k ≥ nd log 2 √ 1+n δ        ≤ v∈{-1,1} d P        ∃n, n k=1 W v k ≥ nd log 2 √ 1+n δ        ≤ v∈{-1,1} d P        ∃n, n k=1 W v k ≥ 1 2 n 1 + 1 n log √ 1+n 2 -d δ        ≤ 2 d • 2 d δ = δ.This concludes the proof. □ ∀δ > 0, ∀T > 0, P ∃t ≤ T, t i=1 U i ≥ 2t Vt log 3T δ + 3c log 3T δ ≤ δ.Proof. This is obtained with a union bound on the values of n ≤ T , then applying Lemma 38. □Lemma 37 (Time-uniform Empirical Likelihoods, Jonsson et al. [2020] ). Let q a distribution on {1, . . . , d}. Let (U t ) a sequence of i.i.d. random variables of distribution q. Then:∀δ > 0, P ∃n ≥ 1, n KL( qn ||q) > log 1 δ + (d -1) log e 1 + n d-1 ≤ δ.Lemma 38 (Empirical Bernstein inequality, Audibert et al. [2009] ). Let (U k ) k≥1 a martingale difference sequence such that sp (U n ) ≤ c a.s., let Ûn := 1 Lemma 39 (Bennett's inequality, Audibert et al. [2009] ). Let (U t ) t≥0 a martingale difference sequence such that |U t | ≤ c a.s., and denote its conditional variance Vt := E[U 2 t |F t-1 ]. Then, ∀δ > 0, ∀n ≥ 1, P       ∃k ≤ n, k i=1 U i ≥ 2 n i=1 V i log 1 δ + 1 3 c log 1 δ       ≤ δ.Lemma 40 (Lemma 3 of Zhang and Xie [2023] ). Let (U t ) be a sequence of random variables such that 0 ≤ U t ≤ c a.s., and let F t := σ(U 0 , U 1 , . . . , U t-1 ). Then:∀δ > 0, P ∃T ≥ 0, T -1 t=0 U t ≥ 3 T -1 t=0 E[U t |F t-1 ] + c log 1 δ ≤ δ; ∀δ > 0, P ∃T ≥ 0, T -1 t=0 E[U t |F t-1 ] ≥ 3 T -1 t=0 U t + c log 1 δ ≤ δ.NeurIPS Paper Checklist 


Decision: This paper closes a gap in the theoretical literature. There might be some issues in the proof, but they appear fixable.

Reviews: review: paper_summary: paper_summary: The paper shows that by replacing the extended value iteration in optimistic methods, like UCRL2, it is possible to obtain regret that scales optimally with the number of states, actions, the time horizon and the span of the optimal value function, instead of the diameter, despite not knowing the diameter, assuming weakly communicating MDPs. In addition, a novel analysis is presented that also gives a polynomial bound on the compute cost of the algorithm. The new extended value iteration method is designed based on new ideas to refine the set of plausible MDPs considered in a given step: For this, an inequality is provided that relates the deviation of the values assigned to two states to observable quantities; creating a new set of constraints on the MDPs considered.
strength_weakness: strength_weakness: The presentation is not great; the paper feels rushed, the paper is full of (minor) grammatical and typographical errors (starting with the abstract: "encounter suffer"). While I did not go through the whole proof, there are many minor problems that are apparent: The paper is not very careful in tracking error events. For example, \tilde{beta} is sometimes appearing in a condition, but it is also constructed by the algorithm, perhaps things work out, but details are definitely missing.
The experimental results are unconvincing: Experiments that show scaling the optimal span would have been more convincing. The presented experiments do not help at all.
questions: questions: Are you sure you tracked all the error events correctly? (E.g. in Lemma 13, Lemma 3 is used, which needs $\tilde{g}\ge g^*$, but the proof of Lemma 13 does not mention why this would hold and exactly what value of $\tilde{g}$ is used here.)
One of the confusing aspects of the presentation of the insight was that on page 5, where the mitigation is explained, beta_t(s,a,u) is used and then a maximum over u is taken; while it is not explained whether beta_t(s,a,u) bounds the deviation that is a function of u for all u (needs a covering?). I guess this covering is not needed, but then why can we take the max as suggested in this paragraph (lines 155-161).
limitations: limitations: n.a.
paper_summary: paper_summary: This paper studies learning in average reward MDPs, and presents the first minimax optimal algorithm (in terms of $sp(h^*)$) which is computationally tractable, and also simultaneously the first which does not require prior knowledge of $sp(h^*)$.
strength_weakness: strength_weakness: The algorithm is rather complicated and has many components. The presentation also does not make it easy to determine the key ingredients of this method. While it is interesting that this method may incorporate different confidence regions, I wonder if it might be more clear to present things in less generality.

It is nice that experiments are included, but if anything they seem to contradict the claim that the method achieves minimax regret without prior knowledge of $sp(h^*)$ (due to the left plot in Figure 2). Since the bias estimation subroutine seems to be a key ingredient, it would be much better if an experiment was included where this subroutine was making a nontrivial contribution (by my understanding, in the left plot the bias estimation routine is not doing anything since it hasn't been given enough time, and in the right plot, it is not doing anything since much better prior information has been given to the algorithm).
questions: questions: Why is the main theorem stated with the parameter $c$? It seems like the best choice is always $c=sp(h^*)$? (And if $c \gg sp(h^*)$, then the theorem is not giving the minimax optimal regret.) Does the theorem hold for all $c$ simultaneously or is this parameter used somewhere that I didn't notice?

The main theorem mentions a confidence region system for communicating MDPs with a diameter-dependent computational complexity, but since the paper is for weakly communicating MDPs which generally have infinite diameter, I think a different system would be a better choice? Can the author(s) comment on the complexity when the diameter is infinite?
 
Many times notation like $h^*(\mathcal{M})$ is used, but is this well-defined? There can be multiple solutions to the Bellman optimality equation.

The paper https://arxiv.org/pdf/1905.12425 claims to achieve the optimal diameter-based $\sqrt{DSAT}$ regret, maybe it should be added to the related work.

In the display below line 785, the number of commutes between $S_t$ and $S_{t+1}$ is lower bounded by the number of transitions between these states. A similar bound is used under line 830. Does this suggest that the bias difference estimator could actually be formulated using only direct transitions between pairs of states?


Line 397: $h^*$ should be $g^*$?

Line 404: Some character I believe meant to be $S$ was used
limitations: limitations: No major limitations
paper_summary: paper_summary: The authors propose a novel algorithm for weakly communicating Markov Decision Processes (MDPs) with an average-reward objective. This algorithm, at the same time, is a) tractable since it does not rely on the exact solution to a high-dimensional non-convex optimization problem as prior work, and b) achieves minimax optimal regret up to logarithmic factors.
strength_weakness: strength_weakness: - The algorithm requires solving the linear programs for each doubling epoch, which is tractable but non-generalizable beyond the tabular setting;
- The large second-order term is dominated by the main asymptotic optimal term if $T > S^{20}$. This effect of a large second-order term is also observable during the experimental section.
questions: questions: - Discussion in Section 3.3 is a little bit misleading since it is formulated in terms of arbitrary vector u and may think that, afterward, the union bound over possible u should be applied to write down a bound of type $\max_{u} \beta_{t}(s,a,u)$ (and thus inducing additional $\sqrt{S}$ factor due to equivalent with purely $\ell_1$-confidence regions),  whereas you need to do it only for $u = h^\star$. I would suggest rewriting this discussion a little bit to avoid the confusion I experienced during the first reading of the text.
- Appendix C6. It's not clear what (2k) means in the equation after line 796. I have the same question about (3k) and (4k) after line 816 and 825.
- Additionally, I would appreciate the additional discussion on the difference between regret minimization and best policy identification settings for average-reward MDPs, especially in a glance at existing concurrent work Tuynman et al. 2024.
Tuynman, A., Degenne, R., & Kaufmann, E. (2024). Finding good policies in average-reward Markov Decision Processes without prior knowledge. arXiv preprint arXiv:2405.17108.
limitations: limitations: The paper is of a theoretical nature and thus does not have any direct impact.
paper_summary: paper_summary: The paper proposes the first tractable algorithm that achieves minimax optimal regret for average reward tabular MDPs. The algorithm does not require prior information on the span of the optimal bias function.
strength_weakness: strength_weakness: See questions.
questions: questions: 1. The minimax lower bound in [4] is sqrt{DSAT}. Because H=span(h^*) <= D, I wonder why sqrt{HSAT} is even achievable by the algorithm developed in the paper. 

2. The authors cited [14, 25] for the lower bound sqrt{HSAT}, but I can not find this result/theorem in these two papers with a rigorous proof.  In fact, [14] mentioned it is an open problem whether the “actual” lower bound depends on diameter D or the bias span H. Please provide a proper reference if the actual lower bound depends on H. 

3. As shown in Figure 2, PMEVI behaves almost the same with its EVI counterparts when no prior information on bias is given. This does not illustrate the advantage of PMEVI compared with UCRL2 or KLUCRL, even though the regret of the algorithm in this paper is claimed to be better. 

4. In Figure 2 (to the right), PMEVI is run with bias information c, but it is compared with UCLR2 which does not use c. This is not fair comparison. If PMEVI is given bias information, then it should be compared with other algorithms such as SCAL or UCB-AVG which require bias information for implementation. 

5. Computing max_u beta_t(s,a,u) may not be tractable in general. Algorithm 5 provides a way to bound/approximate this quantity. I wonder what is the intuition? I also can not find the proof that it is indeed a bound that does not impact the regret efficiency.  

6. The regret proof in Section 4 does not highlight how the key components projection and mitigation in the algorithm impact the regret. In particular, it is not clear from the proof sketch where these components are used, and how the beta-mitigated extended bellman operator is applied to achieve the minimax optimal regret.
limitations: limitations: I do not find the discussions of limitations in the main body of the paper.

Comments: title: Quality
acknowledgement of rebuttal
comment: Thank you for taking the time to read through. I agree with your assessment. If the results are indeed correct
The complaints of reviewer 9hWK29 fall into three categories:
1) Role of D vs. H. This was a confusion on part of the reviewer, which stems from the fact that early literature focused on D, and it was only later that the role of H was discovered. I think the authors gave an excellent answer, clarifying all the confusion.
2) The experiments are not really demonstrating that the theory holds up. I have the same problem as reviewer 9hWK29 in this regard and while I understand the response, I still think that it would have been better either completely omitting the experiments, or going after checking whether the claimed theoretical improvement also holds up in the experiments in some limited, but well chosen setting (i.e., design MDPs with variable H and confirm that the algorithm adapts to H as claimed).
3) Complaints on the presentation/explanations in the paper. I share some of these concerns. 
Overall, yet, I feel the rating of 4 is harsh and unjustified for a paper that is addressing a major open problem in the field and which, as far as we know, resolves this open problem. I, for one, would like to see papers at NeurIPS that do this, even if they are somewhat imperfect. In particular, I won't care even if there were absolutely no experiments. Of course, I also care about how well the paper is written and here I see room for improvement. However, I feel that in this regard the paper is passing the bar and I would hope the authors will improve the writing for the final paper. Eventually, what matters is whether the result is correct and whether it adds interesting new knowledge to the field and here I believe the answer is yes.
Thank you for your response. I find the global rebuttal still leaves me with doubts about the experimental results. Overall, I will keep my score.
I would like to thank the authors for their response and I am happy to keep my score.
The rebuttal is fine; I wish I could read a polished version of the paper before it gets published. However, I am optimistically assuming for now that the presentation issues will be smoothened out and the result will still hold.