Achieving Tractable Minimax Optimal Regret in Average Reward MDPs
Authors: Victor Boone
Zihan Zhang
Venue: NeurIPS 2024 poster (2024)
Keywords: Markov decision processes
Regret
Average reward
Minimax
Optimism
Model-based
Primary area: reinforcement_learning
TL;DR: We provide the first tractable algorithm that achieves minimax optimal regret in average reward MDPs.

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.

Achieving Tractable Minimax Optimal Regret in Average Reward MDPs
Victor Boone victor. booneluiv-grrenolee-ala
Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France
Zihan Zhang
zz54 01447@@princeeto edu Princeton University
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 Ö (ysp AT)) where sp (h') is the span of the optimal bias function ht, S x 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 sp (h*).
Our algorithm relies on a novel subroutine, Projected Mitigated Extended Value Iteration (PMEVI), compute bias-constrained optimal policies efficiently. This subroutine can be applied to various previous algorithms to improve regret bounds.
1 Introduction
Reinforcement learning (RL) Burnetas and Katehakis [1997], Sutton and Barto [2018] has become a popular approach for solving complex sequential decision-makinn 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 learning agent seeks maximize the rewards that are gathered by interacting with an unknown environment.
This paper focuses average reward MDPs where the learning agent must maximize the sum of rewards the long run without any reset mechanism. In this setting, the proper balancing between exploration (i.c., playing sub-optimally to learn the unknown environment) and exploitation (i.e., planning optimally according to the current knowledge), usually known as the exploration cetiiton-expiiittionnn trade-off, is key learn efficiently. The measure of learning performance that adopt throughout is the regret, that compares the aggregate rewards collected by the learning agent during the learning process the expected performance of omniscient agent that knows everything in advance. The seminal work of Auer al. [2009] provides a minimax regret lower bound of Ω (VDS AT). where D is the diameter (the maximal distance between two different states), the number of states, A the number of actions and 7' the learning horizon. They also provide an algorithm achieving regret (VD*S>AA7) where Ō(-). Ever since Auer al. [2009], many works have been devoted close the gap between the regret lower and upper bounds in the average reward setting Auer al. [2009], Bartlett and Tewari [2009], Filippi et al. [2010], Talebi and Maillard [2018], Fruit et al. [2018, 2020], Bourel et al. [2020], Zhang and Ji [2019], Ouyang al. [2017], Agrawal and Jia [2023].
O hides logarithmic factors of (S.A.T).
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Abbasi- Yadkori et al. [2019], Wei et al. [2020] and more. Subsequent works Fruit et al. [2018]. Zhang and Ji [2019] refined the minimax regret lower bound to 2 (y/sp(h (h* (ST) where sp (h') is the span of the bias function, which is the maximal gap of the long-te tergttermmmm accumulative rewards starting from two different states. The difference is significant, since sp (h*) I D and the gap between the two can be arbitrarily large. However, existing work achieves the following three requirements simultaneously:
(1) The method achieves minimax optimal regret guarantees Ō ((ss((h')AA)
The proposed method is tractable;
(3) No prior knowledge on the model is required.
Most algorithms simply fail to achieve minimax optimal regret, and the only method achieving Zhang and Ji [2019] is intractable because it relies an oracle to solve difficult optimization problems along the learning process. Naturally, we raise the question of whether these three requirements can be met all at once:
Is there a tractable algorithm with δ (vsp (hr )S minimax regret without prior knowledge?
Contributions. In this paper, we answer the above question affirmatively, by proposing a polynomial time algorithm with regret guarantees Ó (ysp (h" AT) for average-reward MDPs. Our method can further incorporate almost arbitrary prior bias information H, S R to further improve its regret. Theorem 1 (Informal). Provided that the confidence region used by PMEVI-D DT satisfy mild regularity conditions (see Assumption 1-3), then for every weakly communicating model M with sp(h") s T and sp(h") H., IMEVI-DT(HH 6, T) achieves regret:
(pph))STTT log
SAY
+ O (sp(h")) A log"
[AA
with probability 1 - 265. Moreover, if PMEVI-DD runs with the same confidence regions that UCRL2 Auer et al. [2009] on a communicating environment, has time complexity O(DS O(DSAAT).
Taking 6 VI/T. we also obtain a Ö (ssp AT regret bound in expectation. The geometry of the prior bias region H. that PMEVI-DT DT can support is discussed later (see Assumption 4). It can be taken trivial with H. R- to obtain a completely prior-less algorithm.
To the best of our knowledge, PME is the first tractable algorithm with minimax optimal regret bounds (up logarithmic factors). The algorithm does not necessitate any prior knowledge of sp (h"), thus circumventing the potentially high cost associated with learning sp (lt)). 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 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 Ö(DSVAT). This paper pioneered the use optimistic methods learn MDPs efficiently. 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 SVDAT and suffer from an extra v5. A parallel direction was initiated by Bartlett and Tewari [2009] with REGAL, obtaining regret bounds scaling with sp(h") instead of D. and extending the regret bounds MDPs in the mean time. The computational intractability of REGAL is addressed by Fruit et al. [2018] with SCAL, and regret guarantees are further improved by Zhang and Ji [2019] with EBF, eventually reaching optimal minimax regret but loosing tractability.
to rreakly-communicatiii
Another successful design approach is Bayesian- flavored sampling, derived from Thompson Sampling Thompson [1933], that usually replaces optimism. The regret guarantees of these algorithms usually stick to the Bayesian setting however Ouyang et al. [2017], Theocharous et al. [2017], although
2

---

Table 1:
Comparison of related works on RL algorithms for average-reward MDP, where S xA is the size of state-action space, the total number of steps, (D,) is the (local) diameter, sp (h") s D is the span of the bias vector, fmix is the worst-case mixing time, haa is the hitting time (i.e., the expected time cost to visit some certain state under any policy).
Algorithm
Regret OK-)
Tractable
Commen(/Requiremeen
REGAL Bartlett and Tewari [2009]
sp SSAT
x
knowledge of sp (h')
Auer al. [2009]
DSVAT
PSRL Agrawal and Jia [2023]
DSVAT
Bayesian regret
SCAL Fruit al. [2018]
th SSAT
knowledge of sp (h²)
UCRL2B Fruit et al. [2020]
SNDAT
extra ylog(T) in upper-bound
UCRL3 Bourel et al. [2020]
T Eea Dilna
Lya im E. Eptllssss p(rls,a)
KL-UCRL Filippi et al. [2010), Talebi and Maillard [2018)
SNDAT
EBF Zhang and Ji [2019]
SAT
optimal, knowledge of (p')
Optimistic-Q Wei al. [2020]
sp Ai
model- free
UCB-AVG Zhang and Xie [2023]
model- free, knowledge of (hh)
MDP-OOMD et al. [2020]
ergodic
Politex Abbasi- et al. [2019]
Omis I ATI
model-free, ergodic
PHEVI-DT (this work)
v AT
Lower bound
Q (PF)SAA
Agrawal and Jia [2023] also enjoys Ō(SYDAT) high probability regret by coupling posterior sampling with optimism. Another line of research focuses on the study of ergodic MDPs, where the environment is such that all states are visited infinitely often under every policy. To name few, the model-free algorithm Poli volitex/A Abbasi- Yadkori et al. [2019] attains a regret of O((Imix) (hn and fnr are respectively the mixing and the hitting times of the ergodic environment. By leveraging an optimistic mirror descent algorithm, Wei et al. [2020) achieve an enhanced regret of Oly
where mii
We refer the readers to Table I for (non-cxhaustin list of existing algorithms.
2 Preliminaries
We fix a finite state-action space structure X := Uses (s) x A(s), and denote M the collection of all MDPs with state-action space X and rewards supported in [0, 1].
Mulinitehhorizon MDP. An element M is tuple A. p. r) where p the transition kernel and r the reward function. The random state-action pair played by the agent at time is denoted X, = (S,,A,) and the achieved reward is R, A policy deterministic rule π we write II the space of policies. When coupled with MDP M E M, a policy properly defines the distribution of R,) whose associated probability probability and expectation operators are denoted P. E,, where s E S is the initial state. Under M, fixed policy has reward function (*() == r(s, xs)), a transition matrix pr, gain (s()) == lim E +... Ry and a bias 1r(ss) := Cesàro- lim E (R, g(S,))),, that all together satisfy the Poisson equation h² + g" = + pT see Puterman [1994]. The Bellman operator of the MDP is:
A and
Lu(s) == max (r(s, + p(s, a)i) ec7(3)
The optimal gain g(()) == max, (s)) and the optimal bias is h*()) == max (1*(s) : A S.t. g" g").
Weakly-communicating MDPs. M is weamly-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- transiente state. In this case, h² is a span fixpoiit of L (see Puterman [1994]). ie.. Lh - ht' E Re where is the vector full of ones. We write h e Fix(L). Then g" = Lkh h² and every policy æ satisfies pTt + prh" S g" h². We accordingly define the Bellman gaps:
A' a) := hs))s) (s)) r(s, a) - p(., a))"
Another important concept is the diameter, that describes the maximal distance from one state to another state. It given by D supser inf, E (t 1 S, s')] An MDP is said communicating
3

---

if its diameter D is finite, in which case sp(h") < sp(r) 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 E M but doesn't have a clue about what M further looks like. From the past observations and the current state S, the agent picks an available action A(S ,) receives reward R, and observe the new state S-1. The regret of the agent is:
Reg(T) == Tg"
R
Its expected value satisfies E[Reg(T)] EIE A'(X)] + Blh"(S - r)) and the quantity Ex A*XX) will be referred to as the psendo-regret. This paper focuses minimax regret guarantees. Specifically, for с 2 I, denote M. := [M E M: 3h' Fix(L(M)), sp (h') ) S c) the set of weakly- communicating MDPs that admit a bias function with span at most Following Auer et al. [2009], every algorithm A, for all c > O, we have
max E (Rg(T)(( 2 (VeSAAT).
(4)
MEM.
The goal of this work is to reach this lower bound with tractable algorithm.
3 Algorithm PMEVI-DT
The algorithm PMEVI-D" that we present in this work is actually general method can be applied to improve various existing algorithms Auer et al. [2009], Filippi al. [2010], Fruit et al. [2018], Bourel et al. [2020], Tewari and Bartlett [2007]. All these algorithms work episodically, by maintaining policy πt, that drives play during time-window (f,.... .f...... 1x+1 - 1) called an episode. An episode rule determines when πe should be considered obsolete and defines the time 4t-1 at which the policy is renewed. To compute nı, these algorithms follow the
(OFU) design principle, by choosing that achieves the largest possible gain that is plausible under their current information. This is done by building a confidence region M, S M for the hidden model M, then searching for a policy æ solving the optimization problem:
g'(M, := sup (g (M,): : I E sp (gM( = 0) with g'(M) == sup ( : M MEMI) M.).
(5)
The design of the confidence region M, varies from a work to another. Given confidence region (M)ro0. OFU-algorithms work as follows: At the start of episode k, the optimization problem (5) is solved, and its solution π. 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 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 Pi(s, a) (and P,,s, a)) to denote the empirical transition (and reward) of the latest doubling update before the r-th step, and further denote M, := (P,, P.).
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, is (s, a) rerecaatng confidence region, meaning that M, = (R, a) x a)),a)) where R,(s, a) and (, a) are respectively the confidence region for a(s,a) and p(s. a) after z learning steps. EVI is the algorithm computing the sequence defined by:
(s) = Liv(ss) := max max (E)(s) ((sA) KSSaPP
max (F(s, + p(s, a) v.)
(6)
until sp (Vi=1 v:) E where e is the numerical precision. When the process stops, it is known that any policy such that π(S) achieves Lv; in (6) satisfies (M,) 2 g g'(M) c. hence is nearly optimistically optimal. This process gets its name from the observation that L, is the Bellman operator of M, seen as MDP, hence EVI is just the Value Iteration algorithm Puterman [1994] ran in M, A choice of action from E S in M, consists in (1) choice of action a A(s), (2) choice of reward 7(s, a) E R, a) and (3) a choice of transition P(s, a) E (s.s,)) a); It is 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, That is why most previous works tried approach the regret lower bound VDS AT of Auer et al. [2009] by refining M, The older works of Auer 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. 2020], Bourel et al. [2020] that essentially make use of tightened kernel confidence regions P.. While all these algorithms successively reduce the gap between the regret upper and lower bounds, they fail to achieve optimal regret VDS AT. Meanwhile, the EBF algorithm of Zhang and [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, has little importance. Instead, our algorithm takes arbitrary (well- behaved) 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 is the high level structure algorithm PMEVI- DT. In the next Section 3.1, we explain how (6) is refined using bias information.
Algorithm 1: PMEVI-DI(H,, T, M2)
Algorithm 2: PMEVI(M.BBT,c)
Parameters: Bias prior 'H., horizon T,, system of confidence regions/ + M,
region M, mitigation B. projection r, precision e, initial vector vo (optional)
Parameters:
1: for k = 1, ... do
1: if not initialized then set vp < 0;
2: Set 4 t 1, update confidence region M,:
n
3: H, < BiasEstimationff: M,
3: f < extended operator associated to M:
4:
'H < 'H (u: sp())= 715) n H/:
4: repeat
5:
[, < BiasProjection(H:
5: In L.Vii
6: B. < VarianceApprooxHH; F,);
6: Pa+1 < Ivmt
7: hy < P..VIIM.,B....voooot// /log//())
7:
1;
8: 9 2/ h
8: until sp (Vn- Fn-1) <
E return Vn-
9: Update policy πy < Grredd(MM, bz.B,);
repeat
11: Play A, (S,,), observe R, S.15
Increment 1+ 1;
13: until (DT) (S. ,)) 2 1 2N, (X).
14: end for
3.1 Projected mitigated extended value iteration (PMEVI)
Assume that an external mechanism provides a confidence region H, for the bias function /t. Provided that M, correct (M E M,) and that H, correct (hi E HH,,, we want to find policy-model pair (x, M) that maximizes the gain among pairs with 4f (M) H, This 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, informs the learner that the search of an optimistic model can be constrained to those with bias within H, This is done by projecting L. (see mitigation) using an operator r, R - H,, that has to satisfy few trn-trivial regularity conditions that are specified in Proposition 2.
2. Mitigation (Section 3.3). When one is aware that ht E H, the dynamical bias update p(s, a)v; in (6) can be controlled better, by trying to restrict (6) to the p(s.a) such that p(s, a)v; I P(s,a)v; + (p(s, pr(s, a))v; with the knowledge that E H, However, controlling the error (p(s, (,(ssa)) by doing a union-bound on all possible values of vi 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 E R$, the empirical Bernstein inequality (Lemma 38) provides variance bound of the form (f,(s, a) p(s,a)uu S a,)s By
5

---

estimating B,(s.a) a) == mäX B, a, u), the search makes sure that (),(s,)) p(s, a) I B,(s, a) holds with high probability for u = h², even though h² is unknown. For (3 E R we introduce the ß-mitigated extended Bellman operator:
E. (())
max (c.R() (sa)) (s,a))
sup
sup
(F(s,a) min (p(s, a),, Pr(s, (ssa)), +(ss
(7)
The mitigation B(s, a) is independent of u, which is crucial for L to be well-behaved.
The proposition below shows how well-behaved the composition 2, : r, L is. Its proof requires to build complete analysis of projected mitigated Bellman operators. This is deferred to the appendix.
Proposition 2. Fix B E RC and assume that there exists projection openator I, R - H, which is (01) monotone: u S = Tu= S Tv; (02) non span-expansive (Tu S sp (u - v); (03) linear: [(u + Ae) = Tu- de and (04) Tu S Then, the projected mitigated extended Bellman operator
2, r, E has the following properties:
(1) There exists a unique 9r E Re such that 3b, E H, 2,b, b, 9r:
(2) If M,, H, and (fr(s, a) p(s, a))h" z B(s, a), then 9, 2 g gM));
(3) If M, is convex, then for all u E R the policy =: Greedy(M,, u. picking the actions achieving L. satisfies 2, Fe for (s) s (s, and (*(() (()))
(4) For all u R and
sp (1n+) 27 s sp (
The property (1) guarantees that 2, has a fix-point while (2) states that this fix-point corresponds to an optimistic gain 8, if the model and the bias confidence region are correct and the mitigation isn't isn't too aggressive. Combined with (3), the Poisson equation of a policy corresponds to this fix-point, i.c., 7 + b, b, 9r so that 9, is the gain and b E H, is a legal bias for under the model (FT, Pr). Lastly, the property (4) guarantees that the iterates 22t u converge to a fix- fix-point of 2 at least as quickly as L goes to fix-point of Li; The convergence of (L,Y"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 2, instead of L, 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.
3.2 Building the bias confidence region and its projection operator
The bias confidence region used by PMEVI-D' DT is obtained as a collection of constraints of the form:
V s' ((s) b(s') c(s, 5') s d(s,
(8)
Such constraints include (1) prior bias constraints (if any) of the form of b(s)-b(s') S c.(s, (s),s)); (2) span
constraints of the form b(s) - b(s') S co == 1/5 spawning the span semi-ball {u sp (u) s Tl:s); and (3) pair- mair-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 bias difference estimator.
Definition 1 (Bias difference estimator). Given a pair of states s # s', their sequence of commute times (77 1o is defined by T infl: _000? S, s) and T inf(/ > I :,, = s') with the convention that p-ss' -c0, The number of commutations up to time is N,(s + s') == inf(i 7, < f) and g(r) == E R; is the empirical gain. The bias difference estimator at time T is any quantity (s(s, s') R such that:
N,(s s')cr(s,s') En Nelsoorri
(-1y' Em (8(T)- R,).
(9)
Lemma 3. With probability - 226,
25. for all T' S T, we have
Ny e 1"(')) ((,,)) 3sp (+)) +1 88 logg Σx-11 (g' (10)

---

Lemma 3 says that the quality of the estimator ey (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 is not accessible the learner however, because sp (h") is unknown in general. To overcome this issue, sp (h²) is upper-hounded by co := 7 Overall, this leads to the design of the algorithm estimating the bias confidence region as specified Algorithm 3.
Algorithm 3: BiasEstimation(F. M,
Algorithm 4: BiasProjection(HH.
Parameters: History Fr, model region M,, confi-
Parameters: H, collection of linear constraints (8), E R$ to project
dence 5 > 0
1: Estimate bias differences c, via (9);
v 0S;
2: Estimate optimistic gain 3 < min 965
2: for s E do
3: Inner regret estimation Bo <- 18 Σ R;
Using linear programming, compute:
4: v(s) e sup (w(s): w s and w E H,);
4: E &- >
8T log ()) T
end for
5: Estimate the bias difference errors as:
6: return V.
M)s.K)= emor(c, s, 4,x') 300 + (1 + call + () 28 N/(s + x()
6: return errorr, -))), (8) defines Hf.
Coupled with prior information and span constraints, the bias confidence region H, is 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, in polynomial time with Algorithm 4. Moreover, the resulting projection operator satisfies the prerequisites (01-4) of Proposition 2, making PMEVI (Algorithm 2) well-behaved. See Appendix B.2 for proofs.
Lemma 4. Assume that H is a sel of R$ satisfying a system of equations of the form of (8). If non empty, then the operator Tu cllsProjection((( u) (see Algorithm 4) is projection on H and satisfies the properties (01-4) defined in Proposition 2.
3.3 Mitigation using finer bias dynamical error
The fact that It H, with high probability is used in PMEVI-DT to restrict the search of EVI by reducing the dynamical bias error. This reduction based on a empirical Bernstein inequality (see Lemma 38) applied to (p(s,a) p(s, a))u. Here, it gives that with probability 6, we have:
2V 2V a). u) log
37
3sp (u) log (27
(f,(s,a) - a(s
max (1. =: a,
(11)
max (1, a))
where V(A(s, u) is the variance of under the probability vector (,(s, More specifically, if q is a probability on S and 4 E R-S, we set V(q.u) := Σ. Σ.q(s)((ss) - 4 u)2. In (11), RS. as X and T 2 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 issuc is avoided by changing (sss, a, u) max B,(s, a. u) in (I.). The resulting inequality is not guaranteed to hold simultancously for all u E H, and with high probability; However, it is guaranteed to hold with high probability for Ir,, which will be enough.
The variance maximization problem max B,(s, a, u) is a convex maximization problem with linear constraints. Even in very simple settings, such optimization problems are NP-hard Pardalos and Schnitger [1988] hence computing max B.(s, a, 4) not reasonable in general. Thankfully, this value can be upper-bounded by tractable quantity that is enough in the regret analysis. The mitigation B, used by PMEVI-DT is provided by Algorithm See Lemma 12 and Appendix A.2.2 for details.
Regret guarantees
Theorem 5 thereafter shows that PMEVI-DT has minimax optimal regret under regularity assumptions on the used confidence region M, Assumption asserts that the confidence region holds uniformly with high probability, Assumption 2 asserts that the reward confidence region is oob-siissmnn (see
7

---

Algorithm 5: Variaancepppoxxinttoon//.7
Parameters: Bias region Hi, history F;
1: Extract constraints (c, error(c, --)) -,;;
2: Set co < <
3: Pick a reference point ha (issprojectioom///(((-)))))
4: for (s.a) E X do
5: f log o
SA7 max (1,N,as.a);
6: var( a) - V(prss, a), ho) + 8co Eves (r(s' a)e((',
7: Bf(s,a)
22arr(s, a)p 3cop or too if N,(s, a) = 0;
8: end for
9: return B..
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 - 6, we have M E 2a M Assumption 2. There exists constant C such that for all (s,a) S, for all T, we have:
K(T)
R(s,a) S (ī(s.a E R(s,a): (,(,,) [i a) a(s, S C'log (SAIL+NMaa))
Assumption 3. For forr2 0, M, is (s, recttnggll convex region and LN converges fix-point. Assumption The prior bias region H, contains h' (M) and is generated by constraints of the form:
Ys s', b(x) b(x') c.(s.5)
with cs(s, 5') E [-00, oo] (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
Theorem 5 (Main result), Ler O. Assume that PMEVI-DT runs with confidence region system I M, that guarantees Assumptions 1-3. IfT 2 è, then for every weakly communicating model with sp (h") s and such that Assumption 4 is satisfied (h* E H.),, PMEVI-DT achieves regret:
OVCSAT log
SAT
+ +c(cs 3 AATS log?
SAT
with probability 266, and in expectation if < <V/T. Moreover PMEMEV DT runs with the same confidence regions that UCRL2 Auer et al. [2009], then it enjoys a time complexity A())
To have a completely prior-less algorithm, pick H. R.S. The proof of Theorem is tedious and its details deferred to appendix. We will focus here the main ideas.
Notations. episode k, the played policy is denoted πy. As a greedy response bд. by Proposi- tion 2 (3), there exists 7z(s) sup R2, (s, (T)(s)) and Ps(s) P,,s,, (s,n(x)) such that by + 9x
Prha- The reward-kerned pair M2 = (Fx, Pt) is referred to as the optimistic model of ли. We write Pi Pz, (M) the true kernel and Pæ == Ps. (M₂) the empirical kemel. Likewise, we define the reward functions and Pr. The optimistic gain and bias satisfy 9a g(T,, M2) and h(m, M&). We further denote cu T
The regret is first decomposed episodically with Reg(T) = E. E (g' - R2). The first step goes back to the analysis of UCRL2 Auer et al. [2009], and consists upper-bounding the regret of the episode & with optimistic quantities that are exclusive to that episode.
Lemma 6 (Reward optimism). With probabililty 1 66, have:
Reg(T) - Σ 2
(ge - R₂) S Σ
Σ
A111 (oc px())) + ( log log(
(12)
We introduce the optimistic regrets B(T) En E R,) and B(T) E, (0 (Fx,)(( Rewriting the summand 8e Fx(),)) using the Poisson equation by + Se Pebr. we get: 1--11 (px(S,) ) - es,) DR-
E
B(T) Σ Σ
rea

---

Model
Projected Mitigated Ba 3IA) 1
Regret (eg(T) E. Phus (8" - R2)
Navigation (Lemma 7)
(in expectation)
region M,
Lx((((X)) es )bg
Ocoo log(SAT))
Emp. biss emorr (Lemma 8) (e (X,) p(X))
(p AAA log(SA7) (T)
Optimistic re- gret (Lemma 6) Lx h
Bias
region H4
1-11 (9c R,)
Optimism over-
shoot emmma 9)
A log (Rg()e(T
(S) (S,)).
Mitigation
o (VSAT log(T)
order error (Lemmna 10)
A(0052A211/000
(8)
Figure An overview PMEVI and its regret analysis. In the above, 92 and ha are the optimistic gain and bias functions produced by PMEVI (see Algorithm 2) at episode k, and ù. and Pr, are respectively the empirical and optimistic kernel models at episode k.
The analysis proceeds by decomposing the above expression of B(T) the style of Zhang and Ji [2019]. We write E
- (S) es,)be as:
(p.(s,) es,) by + - + - (PE(S,) P&(S (b2 h²)
navigation ernor (1R)
empirical emror (2x)
optimistic oversboot
second error
Each error term is bounded separately. Below, we denote V(q.u) u) = E. ((s)((()) q. u)2
Lemma (Navigation error). With probability
76, the navigation error bounded by:
Σ E Pur-1 (pr(S)) - es,)h, tb2 = v2 E
lo) A A log (2) O
Lemma 8 (Empirical bias error). With probability 1 ö, the empirical bias error is bounded by:
Mor-1 Eie (pe(S,) - P)(S,)) S
SA Σ
r=o hr
T-1
(SAT)
(log
Lemma 9 (Optimistic overshoot). With probability
66, the optimistic overshoot is bounded by:
Σ E M--11 1= (Pa(S)) bz S
4 4. 2 ETD V(p(X)). h-) log
SAT
+8(1 co) i log (SAZ) VB(T) + о (
Lemma 10 (Second order error). With probability 1 66, the second order error is bounded by:
Σ E 1 (px(S)) px) (b2 h²) s 16S A(1 + log S'AT)
V2B(T) + Õ
We see that the empirical bias error (Lemma 8) and the optimistic overshoot (Lemma 9) both involve the sum of variances E. V(p(X,), hi",, which is shown in Lemma 29 to be of order sp (hh))p(( (r)T + ET- (X)).. The pseudo-regret term E/D A d*(X,) bounded with the regret using Corollary 31, then by B(T). With high probability, we obtain an equation of the form:
B(T) s C. (1+ (p log
CS + co) log ((T) +
where C a constant. Setting a := CS + co) (T) and B C C sp ()S AT (og(T/5) + 144, the above equation is of the form B(T) s B a VBT).. Solving in B(T), we find B(T) s B 2 vaB a² The dominant term is hence readily obtain:
B(T) s C (1 + sp (Ir s)p AT) log
(
(pnssAtt co)
(13)
Since co = o(T?), we conclude that B(T) O log((/) ending the proof.

---

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 a river-swim which model known to be hard learn despite its size, with high diameter and bias span, see Appendix D for the model's description.
UGRL2
2500
UGAL2
PNEVICCH!
FMEVHURRL2
200
PNEVICHOO 5)
PHEVICH1.00
UCRL2
Regit: wegeeegedd oure 130
FMEVIKLUCAL UCAL28
KLUCAL
28 PHEVI UCRL2B
PNEVIC--1.5)
150
PNEVIC-22.9)
PHEVI 5)
FMEVIUCRL2S
1500
(xEVI(c==L)
UCRL2 & PREVI UCRL2
(NEVI(C-2)
300
XLUCRL & PHEVI-XLUCRL
1000
2000
3000
4002
5000
1000
2002
3000
6000
5000
Time
Time
Figure 2: (To the left) Running UCRL2 and PMEVI-DT with the same confidence region than UCRL2 on a 3-state river-swim. PMEVI-DT is run with prior knowledge (*(s) (52))) c S (s;)) - 2c for e (0, 0.5, 1, 1.5, 2}. (To the right) Running a few algorithms of the literature on 5-state river-swim and comparing their average regret against their PMEVI variants, obtained by changing calls to the EVI sub-routine to calls to PMEVI.
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 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- ineffective and this can be explained as follows. On experiments, we see that most of the regret is due the early phase of the learning process, where proper bias information nearly impossible 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 long duration. In other words, while the theoretical regret guarantees of PMEVI-D7 are better than its EVI analogues, there is room to improve the bias estimation mechanism and the practical performance.
This being said, it undoubtedly shows that the bias confidence region is
get.
6 Conclusion
In this work, we have shown that regret guarantees of order Vsp(h")S (ooth")SAT 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 al. [2024], Wang et al. [2024], Zurek and Chen [2024a.b]. This difference lies the fact (e, 6 algorithm must produce policy π, after learning steps where is stopping time, with P(g g E) < 6. Implicitly, these algorithms must hereby certify that the output policy is approximately optimal. In opposition, regret robust algorithms have need assess that deployed policies indeed optimal.
In the end, the regret advantages of PMEVI over pure EVI-based methods remain theoretical, and the experimental shortcomings displayed in Section 5 leave few opportunities for future work. Can bias information be inferred more efficiently? Or, the experiments indicate that the regret analysis of EVI-based methods may be drastically improved?
10

---

References
Yasin Abbasi- Yadkori, Nevena Lazic, Csaba Szepesvari, and Gellert Weisz. Exploration-cnhanced POLITEX. 2019. arXiv: 10479.
Shipra Agrawal and Randy Jia. Optimistic Posterior Sampling for Reinforcement Learning: Worst- Case Regret Bounds. Mathematics of Operations Research, 48(1):363-392, 2023. Publisher: INFORMS.
Jean-Yves Audibert, Rémi Munos, and Csaba Szepesvári. Exploration-exploittiio tradeoff using variance estimates in multi-armed bandits. Theoretical Computer Science, 410(19):187--100, 2009. Publisher: Elsevier.
Peter Auer and Ronald Ortner. Logarithmic Online Regret Bounds for Undiscounted Reinforcement Learning. Proceedings of the 19th International Conference on Neural Information Processing Systems, December 2006.
Peter Auer, Nicolò Cesa- Desa-Bianchh,, and Paul Fischer. Finite-Time Analysis of the Multiarmed Bandit Problem. Mach. Learn., 47(2-3):235-255 May 2002.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal Regret Bounds for Reinforcement Learning. In Advances in Neural Information Processing Systems, volume 21. Curran Associates, Inc., 2009.
Kazuoki Azuma. Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, 19(3):357 367, 1967. Publisher: Tohoku University, Mathematical Institute.
Peter L. Bartlett and Ambuj Tewari. REGAL: regularization based algorithm for reinforcement learning in weakly communicating MDPs. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, UAI '09, pages 35 42, Arlington, Virginia, USA, June 2009.
AUAI Press.
Hippolyte Bourel, Odalric Maillard, and Mohammad Sadegh Talebi. Tightening Exploration in Upper Confidence Reinforcement Learning. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 1056-1066. PMLR, July 2020.
Apostolos Burnetas and Michael Katehakis. Optimal Adaptive Policies for Markov Decision Pro- cesses. Mathematics of Operations Research MOR, 22:222-255, February 1997.
Michael B. Cohen, Yin Tat Lee, and Zhao Song. Solving linear programs in the current matrix multiplication time, 2020.
Sarah Filippi, Olivier Cappé, and Aurélien Garivier. Optimism in Reinforcement Learning and Kullback-Leibler Divergence. 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 115-122, September 2010. arXiv: 1004.5229.
Ronan Fruit. Exploration--xploittiie dilemma in Reinforcement Learning under various form of prior knowledge. PhD Thesis, Université de Lille 1, Sciences et Technologies; CRIStAL UMR 9189, 2019.
Ronan Fruit, Matteo Pirotta, Alessandro Lazaric, and Ronald Ortner. Efficient Bias Bias-Span Span-Constrained Exploration-EExlloitttooo in Reinforcement Learning. Proceedings of the 35 th International Conference on Machine Learning, 2018
Ronan Fruit, Matteo Pirotta, and Alessandro Lazaric. Improved Analysis of UCRL2 with Empirical
Bernstein Inequality. 2020. Nww:2007.054566
Anders Jonsson, Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Edouard Leurent, and Michal Valko. Planning in markov decision processes with gap-dependent sample complexity. Advances in Neural Information Processing Systems, 33:1253-122 1263, 2020.
Yi Ouyang, Mukul Gagrani, Ashutosh Nayyar, and Rahul Jain. Learning Unknown Markov Decision Processes: A Thompson Sampling Approach. September 2017. arXiv: 1709.04570.

---

Panos M. Pardalos and Georg Schnitger. Checking local optimality in constrained quadratic program ming is NP-hard. Operations Research Letters, 7:33-35, 1988.
Martin L. Puterman. Markov Decision Processes; Discrete Stochastic Dynamic Programming. Wiley Series in Probability and Statistics. Wiley, 1 edition, April 1994. ISBN 978-0-471-61977-2 978-0-470-31688-7
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Mohammad Sadegh Talebi and Odalric-Ambrym Maillard. Variance-Aware Regret Bounds for Undiscounted Reinforcement Learning in MDPs. Journal of Machine Learning Research, pages 1-36, April 2018. Publisher: Microtome Publishing.
Ambuj Tewari and P. Bartlett. Optimistic Linear Programming gives Logarithmic Regret for Irre- ducible MDPs. NIPS, 2007.
Georgios Theocharous, Zheng Wen, Yasin Yadkor, and Nikos Vlassis. Posterior sampling for large scale reinforcement learning. 2017.
William R Thompson. On the Likelihood that One Probability Exceeds Another in View of the Evidence of Two Samples. Biometrika, 25(3-4):285- 2944, December 1933. ISSN 0006-3444.
Adrienne Tuynman, Rémy Degenne, and Emilie Kaufmann. Finding good policies in average-reward Markov Decision Processes without prior knowledge, May 2024.
Shengbo Wang, Jose Blanchet, and Peter Glynn. Optimal Sample Complexity for Average Reward Markov Decision Processes, February 2024.
Chen-Yu Wei, Mehdi Jafarnia Jahromi, Haipeng Luo, Hiteshi Sharma, and Rahul Jain. Model- free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 10170-10180. PMLR. July 2020.
Zihan Zhang and Xiangyang Ji. Regret Minimization for Reinforcement Learning by Evaluating the Optimal Bias Function. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Bue, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Zihan Zhang and Qiaomin Xie. Sharper Model free Reinforcement Learning for Average-reward Markov Decision Processes. In The Thirty Sixth Annual Conference on Learning Theory, pages 5476-5477. PMIR, 2023.
Zihan Zhang, Yuan Zhou, and Xiangyang Ji. Almost Optimal Model-Free Reinforcement Learning via Seffrrece-Advantaage Decomposition, June 2020. arXiv: 2004.10019 [cs, stat].
Matthew Zurek and Yudong Chen. The Plug-in Approach for Average-Reward and Discounted MDPs: Optimal Sample Complexity Analysis, 2024a. arXiv:2410.07616 [cs.LG].
Matthew Zurek and Yudong Chen. Span-Based Optimal Sample Complexity for Weakly Communi- cating and General Average Reward MDPs, 2024b. arXiv:2403.11477 [cs.LG].
12

---

A Construction of PMEVI-DT
This section provides the technical details required to understand the design of PMEVI-DT 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, E S. We denote or := Nr(s e (s) h'(s") cr(s, s)). We will start by considering the better estimator ey (s, 5') that satisfies the same equation (9) than (s, s') but with g(T) changed to g', readily:
Ns(s + (')c = En N (-1)² Exe, (g -2)). -
To avoid a typographical clutter, we write T; instead of z, in the remaining of the proof and we write a4 := (s + s')( -
(STEP 1) We start by relating the two estimators. Intuitively, 8(7) a good estimator for g' when the regret small. Recall that 8(T) := + E/T R, hence:
Σ 1- (8(T) 8'1=
Σ (R, 8*) Regg()))
Therefore,
l0rl S |ost + |ar - - S |arl Σ (8(T) - 5 + +|eeg(T)/-
We are left with upper-bounding |
(STEP 2) If i is even, then S,, and S S 8: otherwise S, = s' and S S In both cases, have (S Tiai ) - (S,,,, = (-1)((h(ss') (s)). Therefore, using Bellman's equation, the quantity
A = st--l (g' - R,) satisfies:
A Tii- (p(X,) - ess)
1- (r(X,) - R2) + 2 A'(X,
Pii-1
Tai-1
Tul-1
(p(X,) es...) h1 + > Mui-l
(es..) -es,) hi
(r(X,) R,) +
('(X,)
=-1))(H(s') h²()))
(p(X,) es..,) 11- KET
(r(X,) - R2)
(x))).
Multiplying by (-1y and rearranging, h²((') (s)))) + (-1)41 EiSt Em (g" - R2) appears to be equal to:
(-1 Σ Tr---1 l ((p(X)) es, .) / + rX))) - RD) + Σ Tii-l A'(X)).
Proceed by summing over i. By triangular inequality, we obtain:
|ara
Σ Nr(ress))11
Σ T-i-l L (-1)++) ((p(X)) - es..) h² r(x,) R.)) Σ No(rers
Σ Tisrl (X))).
/=0
Because all Bellman gaps A' are non-negative, the second term is upper-bounded by the pseudo-regret x--11 A A'(X)). The first term is a martingale, and the martingale difference sequence (-1)itl ((p(,)((pp()) supported in [0, 1]. Although the
es..) >h rrX,)) R, has span at most sp (ht) + since rewards number of involved terms random, it is upper-bounded by T. hence by the maximal version of
Azuma-Hoeffdiie inequality (Lemma 32), have that with probability at least 1 ô and uniformly
for T' < T,
F-I (-1) ((((X) es...) ) r(X,) R.) (1 sp
TTog
1=0
(STE 3) We conclude that with probability 1 1- for all 7' - T,
ar $ (1 + +p
sph"))
T (2)+
ΣT
T-1 A A'X)) + |Rgg(T)).
13

---

We are left with relating both E/=01 (*X)) and Reg((") to -g- R2). Using the Bellman equation again, we find that:
Em (8- - RR.-AA - (A(A)())))
s (14((0) - ( (T(5+) En10 ((p(x)) - esm.) -ss + (r(X)) R.))
+ (1+ T 3
where the last inequality holds with probability - uniformly over 7' s 7 by Aruma-Hoefidinggs inequality again (Lemma 32). Remark that if y x then |x| s bl [c]. hence we conclude
that with probability 1- 6, for all T' S T:
T-1 Σ (xx)) | 2
T'-1
A'(X, + (1 sp(())) v 7 log (2) + sp spt' (!t')
1=0
2 2 >
T'-1
(x" R2) + 3(1 sp
T log 3sp (h*)
1m0
2
T'-1
(g (g-R) R2) + 3(1 (h")
7 log (3) + 3sp (h)
where the last inequality invokes 8 2 gg. We conclude that, with probability 1 1 26, for all T' = T, we have:
3sp + (1+ V87 log (3)+
Σ
T'
(r
1= (g R
This concludes the proof.
A.2 The confidence region of PME
The algorithm PMEVI
be instantiated with large panel of possibilities, depending 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, E (r, p) is symbolic letter that can be a reward or kernel and we denote Q, a) the confidence region for q(s, a) at time r. If
q = r, then dim(q) (Bernoulli rewards) with Q a) [0. 1]: and if q p, then dim(q) with Qss, a) = P(S).
(C1) Azuma-Hoeffding or Weissman type confidence regions, with Q, a) taken as:
(q(s. a) E Q(s,a) N,(s, a) (lq.() a) q(s, S dim(q) log (SA
8
(C2) Empirical Bernstein type confidence regions, with Q, a) taken as:
a)),a) a(s.a): Vi.lg.(ils,a) a(i 2V(2,10s..a)) 2dimtg
3log
N(s.))
N(s.00
with the convention that x/0 for 0.
(C3) Empirical likelihood type confidence regions, with Q, a) taken as:
(q(s, a) Q(s, a) N,(s, a) KL(G a)) 5 log
28 3
+ (dim(g) 1) I) (e((
Mis.a)
dim--1
(C4) Trivial confidence region with Q,(s, a) Q(s.a).
few remarks are order. When rewards are not Bernoulli, only the confidence regions (CI) and (C4) are elligible among the above. Then, Weissman's inequality must be changed to Azuma's inequality for o-sub-GGausiin random variables, see Lemma 34. Since rewards are supported in [o, 1J. Hoeffding's 's Lemma guarantees that reward distributions are o- Gaussian with 1.
14

---

A.2.1 Correctness of the model confidence region M, and Assumption 1
The confidence regions Q, 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, choose Q, a) among (C1-4). Then Assumption 1 holds. More specifically, the region of models M; := [I.(RR(s. a) x P,ss, satisfies P S M
Proof. We show that, for all E (r, q) and (s.a) E X, if (s, a) is chosen amoung (C1-4), then
P s T (ssa)) Qss,a)) s 6.
If IfQ,ss a) is chosen with (C1), this is direct application of Lemma 35; with (C2), this is Lemma 36; with (C3), this is Lemma 37; and with (C4) this is by definition.
A.2.2 Simultancous correctness of bias confidence region Hi, mitigation B, and optimism
In this section, we show that 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 (9t. ha) are the optimistic gain and bias of the policy deployed in episode k (see Algorithm 1). In particular, we have d 2g by with ha H2. We start by result on the deviation of the variance, which is what the variance approximation Algorithm 5 is based on. Recall that the bias confidence region Hf is obtained as the collection of constraints:
prior constraints (if any) h(s) b(s') c,(s, s');
(2) span constraints b(s) b(x') 5 co := 11/
(3) dynamically inferred constraints (b(s) - b(s') c,(s' error(e,, s) (see Algorithm 3).
We start with the technical result that is behind the variance approximation Algorithm 5.
Lemma 12. Let u. v E H, and fix p probability distribution on S. Then for all s E S,
V(p, u) S V(p.)) v) + Sco Eves p(s') crror(c,,s',55
Proof. We start by establishing the following result: If p is probability distribution S and u. RS, we have:
V(p, u) z V(p. v) + 2 ((--v) vi) max(u v)
(14)
where is the dot product, u2 the Hadamard product and [u] the vector whose entry s (u(s)). (14) obtained with straight forward computation:
v(p.u) V(p. v) p- (u² 1²) + ()- (p- u)²
= - ((u - v) + v)) + (p- (u v) (u + v))
$ p (Iu v (u v)) + (p |u v)(p |u +v
$ 2(p |u vl) max(u + v).
Observe that v can be changed to v + de, where e is the vector full of ones, without changing the result. The same goes for We now move the proof of the main statement. First, translate u and such that u(s) = v(s) = O. Then, we have:
p (u v) Eves p(s))(((s)) u(s) - v(s) v(s') +((s))++)))) + c,(ssss) s))
En p(s) p(s))(((( u(s) c.s s) (155) v(s) c((s'
Eres p(s') error(c,, s).
Conclude using that max(u v) max(u) max(v) + 2cp for u, v such that u(s) = v(s) = 0.
Lemma 13. Assume that Assumption holds and that co 2 sp (k"). Then, with probability 1 for all k < K(T), (I) ge and (2) h² e HH and for all (), (s. p(s,a))h' (s,
15

---

Proof.
Let Ej the event (Vk < K(T), M E M,). Let Eg the event stating that, for all T' 1 <T,
(r + (s) - s') 3sp + (1 + sp (1') 87 log( ( 2 En (8" R,).
and let Eg the event stating that, for all 7' s T and for all (s,a) X, have:
(Vibylsa))A" 241 Nyr(sa)
lug( 24
(pri(s,a) p(s,a))k's
Ny-(5.0)
By Assumption 1, we have P(E)) 1 - 8. By Lemma 3, have P(E2) 2 1 26 and by Lemma 36, we have P(E3) 2 1 so P(E, n E2 n E3) 1- 46. We prove by induction on S K(T) that, on E n Es Es. (1) 9ı g", (2) ht E ", (3) and for all (s.a), (p, p(s, a)), s (s,a), where 9a is the optimistic gain of the policy deployed at episode k.
It is obvious for k = O. Indeed, No(s 5') = O for all s hence co(s, s') = sp (h¹). Therefore,
R Ho 2 b (b) z coj (6 e R sp s sp (h*)
so contains h", proving (2). Moreover, since No a) = 0, we have Bo(s, a) = +oo, proving (3). Finally, since M Ma Et, by the statement (2) of Proposition 2, we have 9 g" hence proving (1). Now assume that & 2 1. By induction gr 2 g" for all f k, so on Eg we have:
(s s') 1') (s) (s'))) (s, 3sp (h') (1+sssp
8T log +2 Σ 44111 (Bc-R;).
(=1 M
By design of H₁ (see Algorithm 3), deduce that (2) h² E Hy. Denote ho E H, the reference point used by Algorithm 5. We have, for all (s,a) E X, on Ej n Eg n E3, we have:
2Vip, (saa) log SAT
3xp(K" log( Ny (s,0)
(f, a(s,
(r,a.)
(Vii,, log( +8c, Evess P (rllaa) enorley .f))) log( log]
S4T 2
3ra log( EAT
(h' E H4 + Lemma 1
+
N₂ (xa)
N, (saa)
(s,)
by construction of Algorithm 5. Accordingly, (3) is satisfied. Finally, M E Mr on Ei so by Proposition 2, we have (1) 9 2 g
Corollary 14. Assume that, for all E (r. p) and a) E X, choose Q, a) among (CI-4), Then, with probability - 46, for all K(T), we have de 2 g" and (2) ht E H. and (3) for all (s,a), (Pr, (s, a(s,a))h" (s.a).
Proof. By Lemma 11, Assumption is satisfied. Apply Lemma 13.
A.2.3 Sub- Sub-Weissman reward confidence region and Assumption
Although the kernel confidence region can even chosen to be trivial with (C4), order to work, PMEVI-DT needs the reward confidence region to be sub-Weissman in the following sense:
Assumption 2. There exists constant such that for all (s, a) E S, for all $ T, we have:
a) ()), e R(s,a): Ni(s, a) (P,,, a) C' loo
25A((+N((s.))
This is indeed the case if R,(s, a) is chosen among (C1-3).
A.3 Convergence of EVI and Assumption 3
We start with a preliminary lemma on the speed convergence EVI. The Lemma 15 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 continuous map, so that the Bellman operator continuous and that g" and h" are well-defined, see Puterman [1994].
16

---

Lemma 15. Let M weakty-commmiicatiin MDP with finite state space R and compact action space, and let L its Bellman operator. Assume that there exists y > such that, Yu R
Vs E S, 3e E A(S),
Lu(s) r(s,a) + p(s, r(s.a) max(u) (1 D)
with o; P(S). Then, for all E R and all e 0, sp L u L"u)
then:
4sp (wo) n 2
2
2sp (wo)
+
log
Proof. Since M is weakly communicating, has finitely many states and compact action space, it has well-defined gain g" and bias hi functions. Denote Unsl = L*u.
We == max (Tx p 11 - ng" h sell
= max (rx g" + (Px - D)h* Pa (1p-1 nell
1 (n 1)g") =: max [r'- Pa nell
Observe that the policy achieving the maximum is the one achieving that ((()) -s, s is the Bellman gap of the pair (s, that we more simply write Ag. For all n, there exists E IT such that Wa-1 -Az, Wre Moreover, by assumption, we have Ps.. = y.e. (1 2, where Q, stochastic matrix. Moreover,
p, Remark
(min(- A..) ywn(s))) e (1 2)a., I Wn+1 & (max( (A,, ywn(s,)) e + (1 - y),,..
Hence, sp (Wn+1) (1 - y)s (wr,)) + sp (A,.). In addition, Wn, L"u L"h", by non-expansiveness of L in span semi-norm, sp (Wn+1) sp (w,). Overall,
sp (w s min ((1 - (w.)) + sp sp
(15)
Fix E > O, and let n. = inf (n: (w,, E).
Let x² an optimal policy. We have Wio1 2 Pr- so by induction, Wh+t 2 Ps+ wo 2 min(wo)e.
Meanwhile, we see that ||w,lli 2 Ex= || + + min(wo), so ΣE ||alll s sp (wo). Since An, s 0 for all k, we have sp (Anr) s | so En= sp (A.,) S sp (wy).
By (15), either sp (1.+1) $ (1 4 max(e, sp (w,)) or sp (Ar.)) 2 ye, but because Σ1 sp (Arr) S sp (wo), the second case can happen at most 2sp(m) times. We deduce that, for all ne.
ye
2n(
(p S 5(1 {x)
sp (wo).
In particular, for n = ne - 1, we get:
1-- 20(mn)
S 11)
sp (wp).
We obtain:
n. 2 2sp(wo)
2
sp (wa)
log
ye
y
e
To conclude, check that sp (1 u L"u) sp (Wa+1 w.,) S 2sp (w,).
Before moving to the application of interest, remark that this result can be greatly improved if the supremum sup (A"(s, (s, < 0) is not zero, change the dominant term independent of e.
4sp(mo) for constant
ye
Corollary 16. Assume that the M, has non-empty interior, and that its Bellman operator satisfies the requirement of Lemma 15, iee. there exists y > 0 such that, Yu E R Ys e S. A(s). (7,(s, a), ()) E a)),a)):
La((s) = F,(s,)) p((s, a) a,) + max(u) + 7)
for some d. P(S). Then Assumption 3 is satisfied, and span fix-points h of L. are such that g'(M) Lh, h.
17

---

Proof. If M, is has non-empty interior, it means that for all (s. a), P,ss, a) has non-empty interior. Therefore, for all state-action pair, there exists p,(s, a) E (s,, a) that is fully supported. It follows that M, is communicating, and it follows from standard results Puterman [1994] that its span fix-points do exist and that g, == Lh, h, E Re does not depend on the initial state.
Moreover, if M e M, and II with & g(T, M,) E Re, letting ix == (M) and Ps Pr(M), have:
8 + psh; s Lh, s & + h, So by induction and since L, is obviously monotone and linear, we show that:
Σ P. S ngie (1 hT)
Dividing by and letting it to infinity, we obtain g(x, s 8r- Observe that we have equility by taking the policy achieving (g.hh))
To see that EVI converges indeed, simply observe that Lemma 15 provides finite bound on how much time is required until the sp (C u- LT s e. Hence sp (L u 4 vanishes to O.
About Assumption 3. regions are:
The assumptions made by Corollary 16 are met if the kernel confidence
Built out of Weissman's 's inequality (C1) (see the next section, also Auer et al. [2009]);
Built out of Bernstein's s inequality (C2) (because the maximization algorithm to compute pr(s, a)u, 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 established), although the gain still well- defined because M, remains communicating. However, just like the original work of Filippi et al. [2010], the convergence is always met numerically.
A.4 Proof of Theorem 5: Complexity of PMEVI with Weissman confidence regions
In this section, we show that when one is using Weissman confidence regions for kernels (C1), then the iterates of L, converge an e span-fix-poim, quickly.
Proposition 17. Assume that PMEVI-DT uses kernel confidence regions of Weissman type (CI) satisfying Assumption 1. Then with probability 1 ô, the number of iterations of PMEVI (see Algorithm 2) is (DVSATT) hence the algorithm has polynomial per-step amortized complexity.
Proof. With Weissman type confidence regions for kernels, for all r S T and (s. E X, we have
log(25
a) 2 p(s.a) E (s) 1Ip(s, a) - Pr(s, all s
T
follows that, for all / S T, the extended Bellman operator L, satisfies the prerequisite (+) of Lemma 15 with
1 y 2
S log(2SAT/0)
=oV
S log(T/0)
T
T
Under Assumption 1, we have M M, with probability 1 Under this event, M, is weakly communicating and sp (h"(M)) s D(M), we can apply Lemma 15 and conclude that every calls to PMEVI (Algorithm 2) takes
sp (wo) VT
DT
O
S log(7/5) I
VS log(T)
where we use that e the number of episodes under the doubling trick (DT) is O(S A log(T)), conclude accordingly.
(5
that sp (wo) O (sp (h' (M,)) = O(D(M)) and that ò 2 4. Since
18

---

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], is the currett matrix multiplication time O(S (S3)).)) in practice, reducing the number of calls to the projection operator is key run PMEVI-DT in reasonable time.
19

---

B Analysis of the projected mitigated Bellman operator
In this section, we fix the model region M. the bias region H and the mitigation vector B. dropping the sub-script/ for conciseness. We denote i, P the respective empirical reward and kernel. Further assume that HH Ho- + Re with Hg compact convex set. The associated projection operation (see Appendix B.2) is denoted r. The (vanilla) extended Bellman operator & associated to M is given by Lu(ss := maX (sup R(s, a) sup P(s, a))). The 3-mttigated extended Bellman operator
associated to Mis:
L
max AE Roaa)RRaa ((sa))
sup
sup
((s, + min (p(s, pls, a)u + B(s,
(16)
The function Greedy B) returns stationary deterministic policy that picks its actions among the one reaching the maximum above. The projection of L to ' is
gat = ro L
(17)
The goal of this section establish Proposition 2 and
Proposition statement (1) is consequence of Lemma 22;
Proposition statement (2) follows from Theorem 25;
Proposition statement (3) follows from Corollary 27;
Proposition 2 statement (4) follows from Corollary 21;
Proposition 2 prerequisites on the projection operator and Lemma 4 follows from Lemma 19.
B.1 Finding an optimistic policy under bias constraints
The main goal is to find and optimistic policy under bias constraints (projection) and bias error constraints (mitigationn. The bias constraints imply that we search for a policy together with model M such that h² (MM) E H. The bias error means that, for It" (MM,), we want in addition p(s, (()) s ((s)) B(s, (())) where P is the transition kernel of M. In the end, our goal is to track the solution of the following optimization problem:
TEILMEM M, g" g'H.B.M) == sup (M): E p(s, & (ss ((ss
(18)
h= (M)) H, (p) =
where the supremum taken with respect to the product order R$. In particular, if 11 S RS, check that u² = =sup 2/ is obtained as и (s) == sup (v(s) v E UI. The constraint sp(x"(M) = is suggested by the work of Fruit al. [2018], Fruit [2019] and is key for the problem 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 mitigated (with (3) then projected (with I). The mitigation operation guarantees that the constraint involving / is satisfied, while the projection 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 r. As matter of fact, projecting then mitigating would not work.
now explain why 2 can be used to solve (18).
B.2 Projection operation and definition of
We start by discussing why 2 is well-defined at all. The well-definition of L is obvious. The point is 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 meet. But the bias confidence region constructed with Algorithm has a specific shape that makes the projection possible. The central property is the one below:
(A1) The downward closure (v u: H) of every R$ has maximum in H.
The only order that we will be considering is the product order on RS. Recall that a set S R has maximum if there exists E '4 such that s for all E U. A supremum of U is
20

---

minimal upper- upper-bound of U1 i.e., such that (1) be smaller than и. For the product order, the supremum of a subset U/ is unique and of the form u(s) sup (v(s) v U/)
V S u for all e U and (2) no satisfying (1) can
Define the projection :: R H as such:
Tu max (v u: Ve H).
(19)
In general, Assumption (A1) is satisfied when H admits join, i.e., is stable by finite supremum: u, V H = sup(u,v) v) H.
Lemma 18. If is generated by constraints of the form b(s) - ((5') - c(s, s') d(s, s'), then it has join and (A1) is satisfied. Moreover, I is then correctly computed with Algorithm 4.
Proof. The first half of the result well-known, see Zhang and Xie [2023], but we recall proof for self-containednnsss. Let v1, 12 E H and define V3 ;= sup(rı, v2). Observe that vz(s) vz(s') max(r)(s)- v2(5) v2())) S c(s, s')+ + d(s, s'). So V33 E H.
We continue by showing that H has join, then (19) is well-defined. For s E S, take a sequence v such that (s) - a(s) == sup (v(s) v u H). Because the span of every element of H is upper-bounded by c == sup (sp (V)
H). it follows that V evolves in the compact region + c). We can therefore extract convergent sequence of vig converging v that belongs to H since the latter is closed. By construction, v²(s) a(s). Because H has a join, V, == sup (v:
(v u v E H) n [v: l|v-- arsell
S] E H.
Lemma 19. Under assumption (Af), the operator Tu := max (v S uuv V H) is well-defined, and is:
(1) monotone: = Tu S Tv;
(2) non span-expansive: sp (Tu - Iv) S sp v);
(3) linear: I(u + de) Iu + de;
(4) Tu S u.
Proof. The well-definition of r is obvious from (A1). For (2), if u S then w # w S V. Hence Tu := max (w S I: w E H) S max [w S v: w E H) =; Iv. For (3), check that it follows from
H= H + Re. For (4), we obviously have Tu max # E H) S u.
The more difficult point is (2) span non-expansivity. Pick u, v E R By linearity, it suffices to show the result for Σ, u(s) E, v(s). In that case, have sp (p that for all w I u, we have w + min(v - u)e I v. Since H = H + Re, it follows that:
max(v- u) max(u v). Observe
max (w S a u H) S max (w S : w E Ht + max(u v)e.
Similarly, we have max fw u w e H) 2 max fw once, we find sp (Tu ([T--Ii) Iv) s (v u).
H) + min(v - u)e. Using them both at
The properties (1), (3) and (4) are essential for 2 to properly address the optimization problem (18). The property (2) is just important, because it plays central part in the convergence of value iteration. The next result shows similar properties for the 3-mitigated extended Bellman operator L From 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 (I) monotone, (2) non-soon non-span-expansive and (3) linear.
Proof. The properties (1) and (3) directly follow from the definition. We focus on (2). Fix u' E R.S. By Lemma 26, we can write Lu Fy P_u and L ie + Pru' In the following, we write Ba(s) == ((s, ((S). Check that:
Lu L'd 7x Pau- (Fx + P S i P_u- (Fr + min ( Pru Parí Bal)
If the minimum is reached with P,u, then:
L uu - L' S Pr(u u').
21

---

If the minimum is reached with pnul + Bn. then upper- bound Pau by Pau + Bxx to obtain:
L ld & Pz(u= u¹).
Overall, we find that there exists 2, E Pr such that LLu LLu' & Qa(u - u'). Similarly, we find Or e Px such that L Lu 2 2x (u u(). We conclude that:
sp(L - L')) s sp ((((r - Qu-
- -²)) s sp -()- u²)
This concludes the proof.
By composition, obtain the following result.
Corollary 21. is (1) monotone, (2) ron-span-expansivee and (3) linear. Moreover, sp (Yu - 8v) S (_ for all u, u
B.3 Fix-points of and (weak) optimism
Lemma 22. has a fix-point span semi-norm, i.e., Au E Hp u) = 0.
Proof. The idea is to apply Brouwer's s fix-point theorem in R quotiented by the equivalence relation u ~ v + sp (u - v) = O, where sp (-) becomes a norm. By linearity (Corollary 21), 2 well-defined in this quotient space, and if 2 is shown continuous on R so will it be the quotient.
We show that
sequentially continuous on H. Consider a sequence 4₂ E HN converging to E H and fix E > 0. Provided that л > Ne for Ne large enough, we have I|u, - vllco < i.c.. Ee s so max (v & Ua : e H) S max (v $ E H) + ce; And on the other hand, for all v u, v ce un
Un Ee s un u + ce. Therefore, in the one hand, for all v un, we have
so max (v uuve H) S max (v S Hn v E H) ce. Hence:
||max (v S и E H max (v S u, HIll S
It shows that I' is continuous. The operator L is obviously continuous as well, so 2 To L is continuous by composition. Since H = -o Re with Hy compact and oenvex, the quotient H/- compact and convex, and is preserved by 2/~. By Brouwer's 's fix-point theorem, 2/~ has fix-point in H//. So has a span fix- fix-point in H.
We write Fix(y) the span fix-points of 2. Lemma 23, has well-defined growth. Specifically, if lu = u + ge, then:
(1) There exists O, s.t., for all Ho. (ng c)e 2"v (ng + c)e
(2) Ifu' E Fix(2), then Qu'
ge.
Proof. Setting maXveHo ||v
ulls- co, can check that u- u for all E Ho. this proves (1) for n and we then proceed by induction on 2 0. By induction, 2"v S u + (ng + c)e and by Corollary 21, 2 is monotone, we have:
gn+1p v s 22"v s 2(u + (ng + c)e) a ((1 + 1)g + c)e
where the last inequality use the linearity of 2 together with 2u + ge. The lower bound of @"v is shown similarly, establishing (1).
For (2), pick w' E Fix(2) with 2n' = u + g'e. Up to translating n', we can assume that u' e Ho and
apply (1). We get:
(ng c)e + S ng'e + u' s (ng c)e + u.
Divided by n and let it go infinity. We conclude that g = g'.
We finally have everything in hand to claim that 2 solves (18).
Corollary 24. The growth of 2 given by g = 2u u for E Fix(2) is well-defined, and:
2"u
Q"u
Vu H, ge = lim inf
lim sup
n-000
n-000
B
Moreover, g g'H,B,
22

---

Proof. The growth property is direct consequence of Lemma 23. We show 2 gHH, M) which is defined in (18). Pick E II, M e M its model with h(T, M) and P.h s p.h h Bx where B,(s) := B(s, x()). Up to translation, we can assume that h Ho.
We have g(n, M) ge for & R.
h+ge ixx Pah s 2h
by definition. By monotony of 2, see Corollary 21, nge + h = 2hh follows by induction on n 2 0. By Lemma 23, we further have 2hh n(g c)e + where E Fix(2). In tandem,
h
ge ge
n
Letting oo, deduce that s 9. 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 s 2h. Then 2 g
The condition "g" + 2hn can be referred of optimism as weak because it is much weaker than optimism property suggested by Fruit [2019] 2> where L is the Bellman operator of the true MDP. Here, only ask for 2h' 2 Lh', i.e., optimism at a span fix-point of I.. This condition is met as soon as M E M, hi E H and B large enough.
weak form of optimism. We qualify this version
B.4 Modelization of the projected mitigated Bellman operator
The aim of this paragraph is to establish Corollary 27, stating that Lu can be viewed as policy produced by Greedy( u.B).
Lemma 26 (Modelization). For E II, denote (s(s) := ((s, Rs == R(s,(s) and P. == II, Pls, T()). Fix u R and π == Greedy(M, B)
(1) IfP is convex, then there exists (f Px)= E R2 x Px such that LBu = ix + Pau.
(2) Assume that Lgu ix p.u. There exists ra s i such that = r', Pau.
The convexity requirement of (1) is always true if the kernel confidence region is chosen via (C1-4).
Proof. For (1), fix a state E S, let a == π(s) and == min(sup a),, p(s, a)u + f(s, a)) If p = sup P(s, a)u, then there is nothing say because P is compact, hence the sup is max and p is of the form p(s, a)u. Otherwise, let p(s, > p(s, a)u + B(s,a) with p(s.a) P(s,a). Introduce, for E [0, 1].
a)(s,a) == Ap(s, +1 a))(s,a).
By continuity, there exists A E (0, 1) such that (ı(s, a)u = p(s,a)u + +(s, a) and by convexity of P(s, a), p2(s,a) P(s.a). This proves (1).
For (2), recall that r F [(F, + P.u). Since Iv $ v, for v RSS we have:
[(F, P.u) S Fxx Pau.
Set := [(F, + P,u) P.u. Check that r satisfies 1 ix and Lu raK + P,u.
The last corollary bellow is crucial to claim that greedy policies are good choices in PMEVI-DT. Corollary 27 (Greedy modelization). Let e R$ and fix π := Greedy(M,u.f) IfP convex, then with the notations of Lemma 26, there exists 7x S R, and Pa E P. such that Lu F, + P.u.
23

---

C Proof of Theorem 5: Regret analysis of PMEVI-DT
Notations. episode k, the played policy is denoted æT. As a greedy response 6g. by Proposi- tion 2 (3), there exists 72(s) I sup Rr (s. (T)( and Ps(s) (s, x(x)) such that he + 9x = nx Paha- The reward-kernel pair Mj
(Fx. Pt) referred to as the optimistic model of πe. We write Pk := Px. (M) the true kernel and PA := Ps. (M,) the empirical kemell. Likewise, we define the reward functions and fr. The optimistic gain and bias satisfy 9 g(Tu, My) and by h(T, My). We further denote co T
Important remark. To slightely simplify the analysis, we assume that PMEVI is run with perfect precision 0, i.e. that 6y- PMEVI(M,,.Pp n. 0) hence is span fix- fix-point of 8g- This assumption is mild and can be dropped by adding an extra error term that has to be carried out in the calculations.
C.1 Number of episodes under doubling trick (DT)
Lemma 28 (Number of episodes, Auer et al. [2009]). The number of episodes up to time T 2 SA is upper-bounded by:
K(T) - SA log,
ST
34
C.2 Sum of bias variances
The Lemma 29 below shows that E V(p(X,), scales as Tsp (sp)sssp + sp (h") Reg(T) in probability.
Lemma 29. With probability at least 1 - 6, we have:
V(p(X),,")) s 2sp (h"))pp(()p)))))))))") (r)T (r) ( / /7 log (t) (h")
(h²) Ere T-1 (*Xx)) (p
Proof. Using the Bellman equation (i) + (s) ((s p(s,a)h" (s, we have:
V(p(X)), = (p(X))=ss)) +
Since sp (1*2)= S sp (,"),, we get:
Σn T-1 v(p(X), $
Σ T-1 (p(X,) es.) 122 2 (4') (T)T+++ ΣT ('(I))
1=0
- T-1 (x(X,) -ss,.) 112 2sp (1)) (s + EiO A'(x))
(Lemma 32) S 2sp (1' (s(()))p((r(T))))))) sp (h²))² T (t) 2sp (h") Σ A'(X) + sp')
where the last inequality holds with probability - 6. This concludes the proof.
C.3 Regret and pseudo-regret: tight relation
In this paragraph, we bound the regret with respect to the pseudo- regret (and conversely) up to factor of order (sp (h" 'sp''ppppp (r) log( 1) Hence, in proofs, the pseudo-regred can be changed to the regret with ease.
Lemma 30. With probubility
46, the regret and the pseudo-regret and linked as follows:
T-1 R,)
2 2sp (h )sp (r) + b) Tlo ( + 2sp
( E (
Σ 1=0
g
A')))
+sp (hi (TT) log (4) + 4sp (h') log ( 2sp (h")
1=0
Proof.
We rely again on the Poisson equation g(( r(X,) (x2) = (p(X,) - es, / so:
E1
T-1 (g" R, -xxx))
Σ T-1 (p(X,) es,) 1
- T-1 (R, r(x,))
A
Σ T-1 (p(X,) es..))
hr/
E T-1 (R, -(xi)
24

---

Up to the constant sp (h"), the two enror terms are respectively a navigation and reward error. The second is bounded using Azuma's inequality (Lemma 32), showing that with probability 1 25, we have:
Σ (R, s log
We continue by using Freedman's 's inequality, instantiated in the form of Lemma 33. With probability
1 6, we have:
Ene (p(x,) es
v2 ΣxD Vrp(X)) (() + 4sp (h") log (t)
log)
The quantity Σ V(p(X,, h") is classical one that appears at several places throughout the analysis. Using Lemma 29, bount explicitely. Further simplifying the bound with Va + b va vb, we get that with probability - 46, we have:
(s (r)T log ( + (og 2 (h* (1r) log E7= (x)))
+sp +sp(h") (hh') (1T) loga (7) 4sp (h") log (1) (h")
(h")
Bound log(t) by log(5) and use Va + vb s 2 va b to merge the terms in v (og(( under single square-root.
Overall, Lemma 30 states that the regret ΣTD (g' R2) and the pseudo-regret Σ/ (X),, differ by about (sp (h")T log( 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 S y + a vy + B that is not linear in y. Corollary 31 factorizes the result into one which will be more convenient in proofs.
Corollary 31. Denote x: (g" - R2) and y = EFo (X)). Further introduce:
==== 2s' log log
B : (2sp (Ir)sp )sp 1) log (5) sp (p())) (4T) log (4) + 2sp (11 (2 (2 ( +1). Then, with probability 46, we have Vi vF+ j + vB and vy s Vx + ar vB.
Proof. This straight forward algebra from the result of Lemma 30.
C.4 Proof of Lemma 6, reward optimism
We start by getting rid of the reward noise. We have:
7- Reg(T) = 1 (g' - RR) EL r(x,)) + E (M(X, - R2)
T-1
Σ T-1
m0 (g- r(X)) + T
with probability 1 1 ô by Azuma's 's inequality (Lemma 32). We are left with ΣT= (g" - -(X))). We continue by splitting the regret episodically and invoking optimism. By Lemma 13, with probability 1 46, we have E/- (g" r(X,)) s Ex Ean (B. r(X,)). Introduce
Bo(T) = Σ (Br r(X)))
(20)
We focus on bounding Br(T). By Assumption 2, as) of the form as)
(22 (s.a) ()(s,a) a) with a)(s,)) R. By the statement (3) of Proposition ()(s, a) 2 0. Therefore,
Bo(T) Σ 1---1
ha-1
(oe (x,))
Σ
(f(()) r(x,)
25

---

1111
Clog 2547
(9k +((x)))
(N, 2 1) ((X)) - -xx))
(X,)
F
R=-11 (N), 1)
2 2SAT
Clog (s,
25
8
(Oc F((X))) + SA +
(s,
where (+) holds with probability 1 - 6 following Lemma 35. By the doubling trick rule (DT), have N,(x)) s 2N, (X,) for < 1x-1. so, with probability 1 6-
(2+ C) log
224
Bo(T)
(0l +(x)) + 5A+ Σ
Σ 24
(x,, 1)
N₂ (s.
Ny(sa))1
(ge +xX))) + SS (2 C) log 25A7
(ol Fx(x))) + SA+4 (2+ log
25
(Nr(s.a)
(Jensen) <
Σ
(ox
( (2 C)SAT log
28
conclude that with probability 66, we have:
f-1-1 (ox xxx))) +4 (2 (2 C)SAT
(Tg(T)
2SA7
T log
2541
SA.
(21)
This concludes the proof.
C,5 Proof of Lemma 7, navigation error
We have:
-1 (Pa(S)) es )04 Σ (ba)
-
(pr(S) - es Σ sp (bx).
$
(pr(S) es... 1bx h1)++++++++ +
1=
The last term is O(coS A log(T)) by Lemma 28, hence is O(7 log(T)).
(STEP 1) We start by bounding A₁. By Lemma 13, with probability 1 46, we have Hl for all k < K(T). So sp (bx - h²) sp (bx sp (h*) 2cg. By Freedman's 's inequality invoked in the form of Lemma 33, we have with probability 56,
A
S
v (p(X,). ba log (+) Sco log ($)
It suffices to bound the first term. Recall that is the vector full of ones. We have:
Σ I---
V(p(X).
-h')= Σ
V (p(x). be - -
l
Σ (()) - - (S)))))
26

---

(0)
1111
Σ - ( F, + 160 log
S
3
- 16c log !!)
Here the inequality (+) holds with probability 5 following Lemma 40. We will bound the summand with the bias estimation error error(C,, S, 5') that spawns the inner regret estimation Bo(()) =
xk11 -is (gr- R,). This inner estimation is linked to B(T) Eey(ge R2) the overall optimistic
regret by:
K(T)
Mea-1
K(T)
Mar-
Bo(lx)
(9.-
R2)
(gs- R2)
1=
K(T)
Rar-
(9k R.) Σ K(T)
Rar-1
(g" R.)
KIT)
Mr--1
(0k R Lie K(T)
2ime
(A'(X) + (p(X)) es,) +x(,)) R.)
K(T)
(9x R,) + sp(')) - > X(T)
T-1
((p(X) - -es_)) + +r(X)) - R,)
t=l
1=
tck
(E1
K(T)
E (dt - R,) sp (h") + (1 + sp (h
T log
=: B(T) sp (1 sp (h")
! Tog
In the above, (+) holds with probability - 45 uniformly on following Lemma 13 and (+) holds, also uniformly k, with probability 1 - by applying Azuma- Azuma-Hoefdding's inequality (Lemma 32).
Continuing, still on the event specified by Lemma 13, we have with probability - 66:
ha
3ep + (1 co)
84 log (3) 2Bo(())
V(p(X).bb - 3
53) Σ
1603 log log
(a m1 S,)
h-1-1 4cp + (1 + (o) 327 log 2B(T)
+ 166 log (1)
A,, S..1)
1=4
(DT) < 12 A + 4co (1 (1+ 32T log +BB(T) S²A log(7)
+ 166 log (t).
(STEP For Ag, by Freedman's inequality invoked in the form of Lemma 33 again, we have with probability 1 1 6.
k=1-1
As S
2 V(pi(S)),"")og (+) + Scp log (7)
1=4
T-1
2
hr)( 8cp log log(
We recognize the sum of variance Σ V(p(X,, h²) that we leave as is.
3) As result, with probability -66, have:
Σ
(PE(S,) - -ss eb, 5 2 1r) + 25 (3B(T)log(?) OSAtrá log (?))
when Co = _
27

---

C.6 Proof of Lemma 8, empirical bias error
Because h" a fixed vector, Bennett's inequality (see Lemma 39) guarantees that (px(S,) P&(S,) B
is small as follows. By doing a union bound over Lemma 39 with confidence SAT over all pairs (s,, a) and visits counts a(s,a) T, we see that with probability 1-d 6, for all k, have:
spth logl SAT
(ix(S)) - PI(S,)) sp
(N,, 2 1)
2V1p(X)A EAI
3N, (X.)
sp(A") SAT
(N,(X) 2 D1
(by doubling trick) & (h' ) + 2
NAXO
3N,(0,)
Summing this over k and factorizing over state-action pairs, we get that with probability 1-
Σ (2k) & (p 2
Σ
Nx(sa)
N1l5a)
spg
SAT
6
s.d
n=1
#=
$ spp(h'SA+
Σ
Nr(s, a(p(ss.)
SAY
+ 2sp A log
SAZ log(7)
5.a
(Jensen) S sp(hh")
SA Σ..
V(p(s.a),1+)log
SAT)
+ 2sp (1' (I")
SAZ
log(T)
sp 4
En V(p(X)), log
7-1
SAT 5
+ 2sp ( log
SAT
log(T)
We recognize the sum of variances Σ/S V(p(X)) that is left to be upper-bounded later on.
C.7 Proof of Lemma 9, optimistic overshoot
Because the f-mitigation generated by Algorithm 5, the quantity (px(S,) ()),, is shown to be directly related to V(p(X,), ft' up to provably negligible error. Denote HÇ the reference point BiasPro ectiiinntin (nH,,, C₁2 So)) used in Algorithm 5 (denoted hg the algorithm). By Lemma 13, with probability - 46, we have h² E Hy for all k. To lighten up notations, we write d,, (s', s) instead of error(c,, s', ss)s).
(STEP 1) Denote A == (fx(S,) - (),,, By construction of Đc, we have A s (X,), so:
A s (X)
(V) 8co Eves (s.
SA7
3cp log
SAT
(X,)
N,, (X,)
2V(PE(S))
16cp Eras PA(S'S ,d,,ss,),,,,,
(d, (s', log
SAT
3co log
SAT
(X,)
N₂ (X,)
N₂ (X,)
A
A
The rightmost term of A is of order O(log2 hence is negligible. We focus on the other two. The analysis of A₁ will spawn a term similar to Ag, hence we start by the second. Recall that d, is the bias error provided by Algorithm 3 and that the inner regret estimation is Bo(ts) Σ Ei Now, remark that:
Iim (se R,)-
KCT
1
>
[K(T)
K(T)
1/411
Bo(t))
R2)
(gt R,)
P=1
1=1
1=bk
K(T)
K(T)
6--11
(gk - R2)
(g' - R,)
1=1
|=
K(T)
(Dx- R2) Σ K(T)
Σ
T-1
(A' (p(x)) es.) 10 +X())) R.)
1=1
pr=
1=n
KIT)
K(T)
7-1 ((p(X)) - -es, )K +((X) R.)
(gk R2) + sp (h')
rink
28

---

(1)
K(T)
Rii-1
(ge (R) sp (h") + (1 (1") T log (:)
(=1
=: B(T) sph" (1 (h)) Tlog
In the above, (+) holds with probability 46 uniformly on following Lemma 13 and (+) holds, also uniformly on k, with probability 1 by applying Azuma-Hoeffding 's inequality (Lemma 32). Therefore, with probability I 56, for all k and E (/.......... 1+1 - 11, we have:
16co Exes ( (s',, (X))
SAT
SAT 1600 log 0
Eves (S, Ar, 5a).5d)dd (')
(X,)
1600 log
SAT
Eves (S, s' (s'd,,
(X,)
SAT 166 log 0
3cn+(L+ou
I +28m00))
Ny (6)
16ca log 0
|s ( 5+2
ST (B(TT)
SAT 160g log
(1
3+2
1ST Wor 3)
0
This bound will be enough. We move to A1. We have:
(. 1V) + vV(p(X).Ar)
VI (2) -((,.))))) VIV V(p(X), + ((((()),
13 In
8co
E P sp(() (IPE(Ss) PM(S)II V(p(X),,1)
S I SAT (x,)
(
8cc
res Pa(s'S,)ddss S)) (p')
V((((x),,r)
S log SAT
Aa
*p
+ (V(())).
2N,
(X,)
Nr, (X,)
where (+) is obtained by applying Lemma 12 and (f) holds with probability 1 1- by applying Weissman's 's inequality, Lemma 35. All together, with probability 1 66, A is upper-boune bounded by:
A 2V(p(X,), hr) log SAT
2 log SAT
S log
SAT
3cp log (ST))
2A + (h")
(X,)
(X,) (X))
Nx,
As(knn
(STEP 2) The number of visits N2,X,) is lower-bounded by (N,(X,) when N₂(X,) 2 1 by doubling trick (DT). By summing over and k, we find that with probability - 65,
h--1
2V(p(X,), h² log 6 (X,)
Σ (3k) s SSAc Σ
Σ
10,0012
1 (2A22k)) As(k,
F=
h-r-1
vV(((X)) / l)) SAT
(DT) S SAco 2
Σ
1,,00221
(2,00) Aslk,
N,(X,)
1
h---1
SSAco +4
ASA
1=0
V(p(X)),
SAT
(2A,kk)) As(k,))
29

---

where the last inequality is obtained with computations that similar to those detailed in the proof of Lemma We recognize the variance that we will leave as is. We finish the proof by bounding the lower order terms A₂ and A3.
(STEP We start with A2. We have:
SAT 10co log 5
1oloogg ( -
Σ Σ
=
1N, 00021
1m
(DT) s 2 V 16008 log (
(1 co) + 2 88 log 1og( +2B(T))
SA log(7)
s 8(1 + co)S A Alog
(2aT) (2 + 47 log (SAI) (2B(T)
(STEP 4) We are left with A3. We have:
2 log
S log SAT 5
3ep log N,,))
SA7
1x AsCk,) =
Σ
I
oxDel
sp(k)
(X,) No, (X,)
mm
2m
2 log (SA7) Vs log sar sp(h")
m--1
8
3co log SAZ N₂ (X,)
(DT)
00,21
(X,) (X,)
s Csp (h' )s AT
log
(AT
6coS log (SAT)
= 0 (h") AT
log
SAT
This concludes the proof.
C.8 Proof of Lemma 10, second order error
Recall that by Lemma 13, with probability - 46, h" E Hy for k, hence sp (h. - 11) 2co for all k on the same event. Therefore, with probability 1 45,
Σ(4k) (4k) = 2005 A + Σ
12,21 (Px(S)) - Pc(S,)) (he h²)
= 2c0S'AA +
YES
(1)
$ 2c,SA 2
N, (2 pa(s'sS))
S
(
$ Ac Σ
1N,22 (X)21
de(s'.S))
2pa(s'1S,) log (X,)
S'AT"
(s'(s
log S'AT
N₂, (X,)
F=
YeS
$ 200 +2 Σ 4111
(Pi(s"S,)ddss"" S,) N2,)))
S'AT
3co log (X,)
S'AT
1 1,,002
Vco V
k
F= S'E
h+r-1
2p (d ,,, S,) log
(5-A7
3cu log (S²Ar) N,(X,)
Σ
$ SA +
1 1000
VeD
N₂(X))
FES
where (*) uses that hi" Hy. and (+) obtained by applying the empirical Bernstein's 's inequality, see Lemma 36, to (x(1'SS)) (x(s'SS)) and holds with probability 1 - 5. The rightmost term's sum is
30

---

upper-bounded by:
3eo log
StAr
log()) log (AT)
N,(X)
For the other term, follow the line of the proof of Lemma (term A2). We have with probability 1 - 56 (46 of which is by invoking Lemma 13):
Dd ,,, 8') (1 co) (1 1+ /88 log (5) 2Bb((s))
(S, s')N,
(1 + co) +2 87 log (5) 1)+ + +2B(T))
(X,)
Therefore,
4(1 co) (3+2 87 log (3)()) 2B(T)) log star)
(dd (s) log
S'AT
VCO
N,(X))
N₂(X))
Summing over k, 1, s', with probability 1 66, we have:
165 + log S'Ar V2B(T) + 2 log (2))
E(k)) s
+ (log(7) log stAr
+ (1 co) (stAT)
This concludes the proof.
31

---

D More details on experiments
D.1 River swim as a hard communicating environment
n-states river-swim. Such MDPs are, despite their size, known to be hard to learn. They consists it states aligned straight line with two playable actions RIGHT and LEFT whose dynamics are given in the figure below. Rewards Bernoulli and null everywhere excepted for r(s., RIGHT) = 0.95 and r(so, LEFT) = 0.05.
Experiments of Fig. 2
0.6
0.6
0.95
0.4
0.35
0.35
$1
$2
Sn
0.05
0.05
0.05
Figure 3: The kernel of a n-state river-swim.
3-state river-swim.
The gain is g" x 0.82 and h" (-4.28, -2.24.0.4
5-state river-swim.
The gain is g" x 0.82 and h" (-9.62, -7.58, -4.96, 2.27,
D.2 Experiments in weakly-communicating environments
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 the truncation operation, that makes sure that the optimistic bias vector has span less than 71/5
UGAL2 PMEUHLKRID
300
0.5
Swatth awemand osee 120 cume
UCRL2
0.1
S0
200
PMEVI
1000
2000
2000
4000
500D
Time
Figure 4:
Bernoulli bandit with dandling state choice of action whose label the mean reward of the associated state-action pair. The learner starts in state so and transitions to the absorbing state 5i as soon as an action is played.
model). Each arrow is
Without the truncation operation, EVI-based methods can never reject the plausibility that the reward so is maximal (equal to one) and that there is positive probability to switch from to when taking the sub-optimal action from 8). More precisely, denote the actions a. b where r(5n. a) = r(31.a) 0.5 and r(si, b) = O. so that is the optimal action and b is sub-optimal. There are two policies n, and n₂ choosing action a and b from 8 respectively. Because So is only visited once, best reward that can be achieved from So is 7,(5g. a) 1 at all times. If one runs UCRL2, the confidence region for transition kernels is roughly of the form (x) (p(x) : Nx llp(x) pxlll S Cp log(t)) and the plausible transition kernel p(x) (x) that goes the quickest from to of the form:
logg(()
log(t)
(.) V
N,(s,a) and b,(sols)bb)
b)(s1,b)*
32

---

After running EVI for steps, the current vector (see (6)) is V.(M), the maximal amount of reward that one can collect in i steps on M, seen as an extended Markov decision process, see Auer et al. [2009]. If the data is well concentrated, the optimal reward from are respectively F((1,,) a) = 0.5 vc, log(t)N,ssss a) and (.(5,,)) b) 0.1 + vc, (og()) b). From all this, one can argue that when i is large enough, the optimistic scores of πæ and πhh over steps are roughly equal to:
log(()
a( Cp
a)
C,
(s; i
0.5 +
= =1- 0.5,
a)
V
Cplog(1)
V Cp
log(()
N)(s..b
N(ss,b)
C, Cp
(s) a i+
-0.9 +
N.(s1. b) V Co
= =i- 0.9
+ Cp log(()
So (s: &
& N.
This means that EVI will output Tr if N, < N,,,, a), leading to N,(s,a) x N, b) so both growing linearly with 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,(s. b) O(r) and their regret will grow linearly.
In opposition, PMEVI-based methods use truncation, making sure that [v;(s)) v:(sa)l s 7 at all times. Intuitively, makes PMEVI-based method "think" that (r(sols), b) cannot be as small as vCp (og(t))))NN b), because the optimistic bias of n. would be too large otherwise; Or, equivalently, that p,(Suls1, b) = vCp log(t)/N,(s),)) b) but with Fy(so. a) < 1, hence killing the optimistic reward at (so. 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.
33

---

E Standard concentration inequalities
Lemma 32 (Azuma's inequality, Azuma [1967]). Let (U,)20 martingale difference sequence such that sp (U,) S a.s., i.e., there exists a, E R such that S U, s a, + a.s. Then, for all 5 0,
P End U, U, 2 tT (1) =
Lemma 33 (Freedman's 's inequality, Zhang al. [2020]). Let (U,) martingale difference sequence such that [U,] S с a.s., and denote its conditional variance V, := E[U?(Ti-1l. Then, for all 6 0,
P 3T ST: Σ U,Z 2 E
1, ( log (4)
26.
Lemma 34 (Time-uniform Azuma, Bourel et [2020]). Let (U₂) a martingale difference sequence such that, for all E R, Elexp(aU U-11 exp( Rod) Then:
46 O, P An 1 (E Us) 2
no (1 )
VI+I
S
Lemma 35 (Time-unffom Weissman). Let q a distribution over (I.....d .d). Let (U,) sequence of iidd random variables of distribution q. Then:
v5> > O, P(In 2 1. E (ev, - D 2 nel nog 2 S 6.
Proof. Remark that ||2 (eu, - 911111 max Σi=1 (ev, q.v). Let W (eu, 9. v). Re- mark that for each (-1, 1) (W") is family of i.i.d. random variables with - ().1) v) & W s
1 (g. v). so E[exp(aW() s exp( $ by Hoeffding's s Lemma. By Lemma 34, we have:
Σ (eu 2)
P In
2 nd log
P
TrE 111, An,
nd log
T
Σ 18111.11
P
3
W
nd log
2v
[=1
Σ
3n,
3n,
W Z
fn 5n(1 |1 + 1
Vitn
2-46
vE-1111
k=1
$ 2 2 =
This concludes the proof.
Lemma 36 (Time-uniform Empirical Bernstein). Let (Ux)al martingale difference sequence such that sp (U,) & a.s. Ü. := Σi=1 U2 the empirical mean and V, == Σn Ei= U.)² the population variance. Then,
Vō > V P. Σ U,2 2: log (
3c log 2
So.
Proof. This is obtained with union bound the values of n T, then applying Lemma 38.
Lemma 37 (Time-uniform Empirical Likelihoods, Jonsson et al. [2020]). Let q distribution (1....,)). d). Let (U,) a sequence of ii.d. random variables of distribution q. Then:
V8 > 0, p(3n 1,n KL(gullg) > log (1) + (d- I)log (e(1 - 2)) 56
Lemma 38 (Empirical Bernstein inequality. Audibert et al. [2009]). Let (URka1 a martingale difference sequence such that sp (U,) c a.s., let U. 1 ynn Up the empirical mean and V, (U, 0 7 the population variance. Then,
n
46 > 0, 1,
E
De U 2 2n log ( 3c 3clog 3c)o so.
34

---

Lemma 39 (Bennett's inequality, Audibert et al. [2009]). Let (U))zo martingale difference sequence such that [U,] c a.s., and denote its conditional variance V, := E[UR Then,
Vō V. P P
Σ 1=1 U Z 2 Σn Vo (1) log (1) S6
Lemma 40 (Lemma 3 of Zhang and Xie [2023]). Let (U,) be sequence of random variables such that 0 s U, S a.s., and let T, == o(U. Ul...., U,-1). Then:
v8>0, O, P P 2 0, Σ T-1
U, 3 Σ r=
ELU, + log clog())) so:
V8 0. P 1 0, E[U,FF-1]
Σnd U. + +coo (t) s 6.
35

---

NeurIPS Paper Checklist
1. Claims
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.
is fine to include aspirational goals as motivation long it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [NA]
Justification: The paper is 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 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 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 few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails 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 fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
36

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification:
To every result is attached 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 cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide 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 supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
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. pscudo-code for EVI. Our code is mostly written in Python. Experiments took few dozen minutes low end laptop.
[2010], Fruit et al. [2020] etc. provide detailed
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer 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 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 a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access 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 a hosted model (e.g., in the case of 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 submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
(b) If the contribution is primarily the architecture clearly and fully.
model architecture, the paper should describe
(c) the contribution a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
37

---

(d)
The authors should provide scripts to reproduce all experimental results for the new reproducible, they We recognize that reproducibility may be tricky in some cases, in which case authors are welcome 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.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The code is provided 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 NeurlPS code and data submission guidelines (https://nips.. cc/ public/guides/Codeet
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: /CodeSubbiisseeee / //nips. http/puullcggudeee httec//gugiie//eeSuumimiiiii wwweeeuubisssioPPPoo ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: People that are unfamiliar with Markov decision processes may not know the river-swim setting in which experiments driven, but it is not required to understand the figures and the discussion. Moreover, a description 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 the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
38

---

Justification: We did 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, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
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).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
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 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 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 the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [No]
Justification: This is mostly a theoretical paper. Most of the computational cost of the work is processing LTTX 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 well 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 into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https: https://neuuipee
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
39

---

The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. 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 no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), faimesss considerations (e.g., deploymeett 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 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 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 unintentional) misuse of the technology.
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 system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have 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 (c.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]
40

---

Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged to reach out the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
41

---

Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
42


Reviews:
[{"review_id": "0myxu6NdbH", "reviewer": "Reviewer_EC5m", "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.", "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.)\nOne 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": "n.a.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "A major breakthrough if the proof holds up. Interesting insight.", "weaknesses": "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.\nThe experimental results are unconvincing: Experiments that show scaling the optimal span would have been more convincing. The presented experiments do not help at all.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## About weaknesses\n\n> 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\")\n\nWe will do our best to correct as many typos as possible, that can make understanding the paper difficult.\n\n> 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. \n\nConcerning the tracking of events, we discuss in further details in the next section (see **About questions**).\n\n> 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.\n\nRegarding experiments, we have carefully entitled the section **Numerical illustrations** rather than **Experiments**, that we do not claim to account for a throughout experimental campaign. This paper is theoretical and our algorithm `PMEVI` was intentionally \"purified\" of any form of tuning and modification to improve its empirical performance. The point of `PMEVI` and Figure 2 is to show that the method can make very good use of pertinent bias information, provided that the quality of this information is high. By leaving `PMEVI` not tuned, we make it easier to build extensions of the algorithm for other settings. Obviously, one interesting follow-up of this work would be to provide a finely tuned version of `PMEVI` with a better bias estimation subroutine, a bit like what `UCRL3` [8] is to `UCRL2` [4]. However, such a heavily tuned version would become impossible to adapt to settings others than undiscounted infinite horizon reinforcement learning problems.\n\n## About your questions\n\n> 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 is used here.) \n\n**Concerning events.** If we understand your concern correctly, you legitimately fear the presence of a circular argument, because the optimism guarantees of an episode seem to depend on the preceding episodes. This is indeed the case, but there is no circularity and all risks of circularity are encapsulated in Lemma 13, that establishes anytime optimism guarantees (and more). Roughly speaking, there are two types of events in the analysis. There is the \"main event\" specified by Lemma 13, that provides time-uniform (1) optimism guarantees, (2) correctness of the bias confidence region (i.e., of projection) and (3) correctness of the mitigation. \n  + Indeed, Lemma 13 is established using Lemma 3. The blocked equation between lines 470 and 471 is universally quantified for $\\tilde{g} \\ge g^*$, i.e., we should read: \"Let $E_2$ the event stating that, for all $T' \\le T$ [and $\\tilde{g} \\ge g^*$], (...)\". We will make the correction.\n  + Then, we agree that $E_1, E_2, E_3$ do not depend on how $\\mathfrak{g}_k, \\mathfrak{h}_k$ are constructed, and hold **independently of how the driver chooses actions.** \n  + So, on $E_1, E_2, E_3$, we show that the properties (1-3) (optimism, correctness of the projection and of the mitigation) *will propagate* from episode to episode. \n  + This high level view will be added in the paper to help the understanding of the proof.\n\nAnd then, there are \"error terms specific\" events, that are invoked on the fly. These are only necessary in the regret analysis. Note that the quality of the bias estimator depends on the regret of the algorithm, hence we end up with a self-bound on the regret (see line 265). However, the self-bound is of the form $x \\le \\alpha + \\beta \\sqrt{x}$ hence ends up being useful at all.\n\n> 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).\n\nThis indeed needs to be clarified, because this is one of the key ideas. Any bound on $(\\hat{p}_t(s,a) - p(s,a))u$ that holds for *every $u$ simultaneously* will inevitably scale with $\\sqrt{S}$ and compromise the minimax optimality of regret guarantees. Therefore, with `PMEVI`, we do not use the event $\\{\\forall u, (\\hat{p}_t(s,a) - p(s,a)u \\le \\beta_t(s,a;u)\\}$. In fact, we only need $\\{(\\hat{p}_t(s,a) - p(s,a))u \\le \\beta_t(s,a;u)\\}$ to hold for $u = h^*$, and that does not require any covering. \n\nThe maximum is taken for \"algebraic\" reasons.\nThe mitigation operation makes sure that optimistic transitions $\\tilde{p}(s,a)$ are chosen so that $\\tilde{p}(s,a)u \\le \\hat{p}(s,a) u + \\beta_t(s,a;u)$. It happens that using a mitigation coefficient $\\beta_t(s,a;u)$ that depends on $u$ provides an ill-behaved operator (monotony is lost), and instead the mitigation coefficient $\\beta_t(s,a) := \\max_{u \\in \\mathcal{H}_t} \\beta_t(s,a;u)$ is used, leading to the current equation (7).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0FfKVZ6R8v", "reviewer": "Reviewer_zKbr", "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^*)$.", "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?\n\nThe 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?\n \nMany times notation like $h^*(\\mathcal{M})$ is used, but is this well-defined? There can be multiple solutions to the Bellman optimality equation.\n\nThe 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.\n\nIn 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?\n\n\nLine 397: $h^*$ should be $g^*$?\n\nLine 404: Some character I believe meant to be $S$ was used", "limitations": "No major limitations", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 4, "strengths": "The main theorem resolves a longstanding open problem which has been the subject of extensive research effort. Removal of knowledge of $sp(h^*)$ is a challenging problem in many settings beyond the one considered in this paper, and thus I hope that this work might lead to progress on this issue in other areas.", "weaknesses": "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.\n\nIt 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We have numbered your questions to gain a few characters and address all of them.\n\n## Concerning the weaknesses\n\n> The algorithm is rather complicated and has many components (...) 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.\n\nFrom a high level, there are two confidence regions. One is for the model parameters (rewards and kernels) and the other is for the bias function. This second confidence region can be considered as \"external\" and its purpose is to regularize the \"vanilla\" optimism machinery of `EVI` introduced by [4]. Actually, only the bias confidence region and the regularization mechanism (projection + mitigation) is necessary to achieve minimax optimal regret, although the model confidence region seems very important to reduce the burn-in time of the algorithm. We believe that the generality of the approach is a strong point, because it shows that many existing algorithms can be patched all at once with a single analysis.\n\n> 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 (due to the left plot in Figure 2). (...)\n\nYes, sadly, experiments are a bit disappointing. `PMEVI` provides solid formal grounds to use bias information in order to improve performance (this is displayed by the right part of Figure 2) and Figure 2 also shows that getting pertinent bias information is difficult (left part). This leaves opportunities for future work: Improving the bias estimation subroutine would directly improve the practical performance of `PMEVI`.\n\nFor instance, the performance of the algorithm is very bad in the early learning stages. This cannot be avoided because the algorithm has still to figure out which actions seem bad and which seem good. This early data pollutes the bias estimator, making the bias confidence region irrelevant for quite some time. To address it, one idea could be to trash data when it is considered too old. We do not do it in the paper because it would complicate the analysis even more. Also the current version of `PMEVI` was left \"not tuned\" on purpose, to ease the construction of algorithms based on `PMEVI` later on.\n\n## Concerning your questions\n\n1. We use $c > 0$ instead of $\\mathrm{span}(h^*)$ because the results holds for all MDPs with bias span less than $c$. This is just out of formality because the bound doesn't hide any other term than $\\mathrm{sp}(h^*), S, A, T$ and $\\delta$ (like $p_\\mathrm{min}$, or the diameter, or the mixing time, or else).\n\n2. 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?\n\nThe confidence region for $M$ is not specific to the fact that $M$ is communicating (in fact, the confidence region of `UCRL2` [4] and its variants do not rely on the communicating property). However, the complexity result only holds for communicating MDPs as it is currently written indeed. We see two ways of addressing this.\n  + Either we simply restrict the complexity result to communicating MDPs (no need for extra material required, just make the precision in Theorem 1);\n  + Or we generalize the complexity result to weakly-communicating MDPs. This can be done like so. The complexity result is established with Proposition 17 and at line 559, we show that the `PMEVI` needs $O(\\mathrm{span}(w_0)T/(S^{1/2} \\log(T)))$ iterations to converge, where $w_0$ is the error between the initial value of `PMEVI` and the bias function  $h^*(\\mathcal{M}_t)$ of the MDP confidence region $\\mathcal{M}_t$ seen as an extended MDP [4]. If $M$ is communicating, [4, 7] show that this bias span is bounded by $D$, the diameter of $M$. If $M$ is weakly-communicating, the argument of [4, 7] can be generalized to show that it is bounded by \"diameter of the communicating part of $M$\" + \"worst hitting time to communicating part of $M$\", that we refer to as the **weak diameter** (we say \"weak\" because it is finite if and only if the MDP is weakly communicating).\n\nThe first suggestion is better connected to the current literature because the diameter is a well-known object. The second is more complete, but requires a proof that is not currently written in the paper, and this notion of weak diameter is not standard. \n\n3. The notation $h^*(M)$ refers to the *optimal bias function* which is a special solution to the Bellman equations. It is the maximal bias vector over policies with optimal gain, see [18]. The notation $h^*(\\mathcal{M})$ is only used in the proof of Proposition 17 and is the optimal bias function of $\\mathcal{M}$ seen as an extended MDP (see [4]).\n\n4. Thank you for the pointer on https://arxiv.org/pdf/1905.12425, we will discuss discuss its contribution in the next revision opportunity.\n\n5. You are completely right: the proof only keeps tracks of the commutes between $S_t$ and $S_{t+1}$. The bias difference estimator can not work with only direct transitions. The term $A$ in page 13 is no longer a martingale if we only count direct transitions.\n\n> Line 397: should $h^*$ be $g^*$?\n\nYes, you are correct.\n\n> Line 404: Some character I believe meant to be $S$ was used\n\nYes, it should be $S_{\\tau_{i+1}}$ rather than $\\S_{\\tau_{i+1}}$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PK4VseNha4", "reviewer": "Reviewer_f6aP", "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.", "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.\n- 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.\n- 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.\nTuynman, A., Degenne, R., & Kaufmann, E. (2024). Finding good policies in average-reward Markov Decision Processes without prior knowledge. arXiv preprint arXiv:2405.17108.", "limitations": "The paper is of a theoretical nature and thus does not have any direct impact.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- First tractable algorithm that achieves minimax optimal regret bound;\n- The algorithm does not require any prior knowledge of the span of optimal bias function;\n- The algorithm does not require any reduction to a discounted setting and works directly in the average-reward setting.", "weaknesses": "- The algorithm requires solving the linear programs for each doubling epoch, which is tractable but non-generalizable beyond the tabular setting;\n- 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "## Concerning the weaknesses\n\n> The algorithm requires solving the linear programs for each doubling epoch, which is tractable but non-generalizable beyond the tabular setting;\n\nYes, the algorithm needs to solve many linear programs at every epoch for the vanilla version of `PMEVI`. However, solving *too many* linear programs can easily be avoided, especially in the early steps. Indeed, in the early steps of the process, the bias confidence is very bad and pretty much uninformative. After all, in order to estimate the bias correctly, the regret of the algorithm has to be sublinear and this is simply not the case in the early stages of learning. In practice, it means the the projection operation of `PMEVI` does nothing in the beginning. This can be used to avoid a call to a linear program solver (by trying beforehand if a projection on the bias confidence region is necessary at all) hence having the nearly the same running time than `EVI`. In the later stages of learning, changes of episodes are more and more rare, so solving these linear programs is somehow amortized. This is how we obtain the complexity result of Theorem 1.\n\n## Concerning your questions\n\n> 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(s,a,u)$ (and thus inducing additional factor $\\sqrt{S}$ due to equivalent with purely $\\ell_1$-confidence regions), whereas you need to do it only for $u = h^*$. I would suggest rewriting this discussion a little bit to avoid the confusion I experienced during the first reading of the text.\n\nWe suggest the following modification at line 214.\n\n\"(...) are fixed. [Many existing works [4,7,8,11,12,13,14] look for a bound on $(\\hat{p}_t(s,a) - p(s,a))u$ that holds uniformly for all vector $u$, because the values of $u$ encountered along the iterations of `EVI` are not known in advance, and depend on the random data gathered by the algorithm. This is morally achieved by doing a union bound for all $u$, which is responsible for the extra $\\sqrt{S}$ in the regret guarantees of these methods. In Appendix B, we show that we only need (11) to hold for $u = h^*$ that is a fixed constant, so] one is tempted to use (11) to mitigate (...).\"\n\n> 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.\n\n$(2k)$ is the empirical bias error (introduced when starting the regret decomposition at line 256). We will recall the definition of this shorthand. Similarly, the definitions of $(3k)$ and $(4k)$ can be found at line 256. We will recall their definitions at the beginning of every proof section.\n\n> 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.\n\nIndeed, it has been shown in the mentioned work that in the best policy identification setting (PAC learning), achieving performance that depend on the bias function rather than the diameter *requires* prior information on the bias function; While we achieve regret guarantees that depend on the bias function even though we have no prior information on it. This is because in PAC learning, the algorithms has (implicitely) to provide a certificate of optimality. It has to assess that the output policy is nearly optimal with high probability. This certificate of optimality is not necessary in regret minimization and in practice, `PMEVI` plays a policy that it thinks is optimal but it does not have a way to certify that it is optimal. This is very likely to mean that if the algorithm where to produce policy certificates in addition to minimizing the regret (see *Policy Certificates: Towards Accountable Reinforcement Learning*, Dann  et. al., 2019), then the regret $\\sqrt{\\mathrm{span}(h^*) S A T}$ would not be achievable. This discussion can be added to the conclusion.\n\nNote that there is sensible difference (in addition to the learning objective) between our work and the above mentioned work: **In our paper, the learner does not have access to a generative model**. With the generative model assumption, the learner can obtain a sample of any state-action pair in the MDP without constraints, making exploration much less difficult.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yMPqEDzy9a", "reviewer": "Reviewer_9hWK", "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.", "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. \n\n2. 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. \n\n3. 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. \n\n4. 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. \n\n5. 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.  \n\n6. 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": "I do not find the discussions of limitations in the main body of the paper.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The paper proposes the first tractable algorithm that achieves minimax optimal regret for average reward tabular MDPs.", "weaknesses": "See questions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We address your concerns below.\n\n> 1. The minimax lower bound in [4] is $\\sqrt{DSAT}$. Because $H=\\mathrm{span}(h^*) \\le D$, I wonder why $\\sqrt{HSAT}$ is even achievable by the algorithm developed in the paper. \n\nThe lower bound of [4] is indeed $\\sqrt{DSAT}$, but like pointed out by [14], the \"hard instance\" provided by [4] is one such that $\\mathrm{span}(h^*) = D$. To quote [14], \"*The proof of the lower bound relies on the construction of an MDP whose diameter actually coincides with the bias span (up to a multiplicative numerical constant), thus leaving the open question whether the “actual” lower bound depends on $D$ or the bias span.*\"\n\nWhat [4] actually shows is that, whatever the algorithm, there exists a MDP with $c = \\mathrm{span}(h^*) \\asymp D$ such that the regret is $\\sqrt{c S A T}$. It means that the lowerbound of [4] can be read $\\sqrt{\\mathrm{span}(h^*) S A T}$ just as $\\sqrt{DSAT}$.\n\n> 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$. \n\nIndeed, [14, 25] do not provide any explicit lower bound. Like said in 1., [14] precises that the lower bound of [4] can be read as $\\sqrt{\\mathrm{span}(h^*) S A T}$, and [25] shows that it can be achieved by an intractable method with prior knowledge on the bias span, implicitely showing the the lower bound is tight. It is even tighter than the diameter lower bound, since $\\mathrm{span}(h^*) \\le D$ and $\\mathrm{span}(h^*) \\ll D$ in general.\n\n> 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. \n\nThe left part of Figure 2 was very disappointing at first. The poor advantage of `PMEVI` compared to `UCRL2` or `KLUCRL` can be explained as follows: The advantage of `PMEVI` depends on the quality of the bias estimator, that itself depends on the current quality of play so far. The thing is that the *early* quality of play is bad, because the algorithm still has to figure out which are the optimal actions. This early phase pollutes the bias estimator for quite some time, making it somehow irrelevant for a long time. This is what the right part of Figure 2 is there for: It shows that if the bias estimation is better (e.g., under prior information), `PMEVI` is very efficient at using it to reduce the burn-in time. \n\nNow, the left part of Figure 2 shows that there are still room for improvement, for example by improving the inner bias estimation of the method. We think that this is a different work. This paper is mostly theoretical and gives a direction, showing how to use an external trajectorial bias estimation to improve the minimax regret guarantees. Optimizing this bias estimation subroutine is an interesting direction for future work.\n\n> 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. \n\nIn the right part of Figure 2, we indeed compare `PMEVI` to `UCRL2` instead of `SCAL`. We do not claim that `PMEVI` is *better* than `UCRL2` there, but rather that it can efficiently make use of a good quality prior information. This is to nuance the left part of Figure 2, that seems to show that the projection-mitigation procedure has no effect on the regret. Also, the kind of prior information that we feed to `PMEVI` is not one that `SCAL` can use that can only take a bias span upper bound (like \"$\\mathrm{span}(h^*) \\le c$\") into account. Even with tight bias information, `SCAL` will behave like just like `UCRL2` on this instance because plain bias span information is not really helpful here (the bias span is proportional to the diameter on river swim). We can discuss this further in the section **Details on Experiments** in the Appendix.\n\n> 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. \n\nThe correction of Algorithm 5 is established in section A.2.2 with Lemma 13. The estimation used by Algorithm 5 is based on Lemma 12 that provides a general bound of $\\mathbf{V}(p, u)$ with respect to $\\mathbf{V}(p, v)$ for two $u, v$ in the bias confidence region. It will be linked better in the main text to access the proof more easily.\n\nNote that Algorithm 5 runs in polynomial time by providing , and that its output is only an upper-bound of $\\max_u \\beta_t(s,a;u)$. However, it is enough to achieve minimax optimal regret guarantees.\n\n> 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.\n\nThe impact of the projection-mitigation operation can be tracked by looking at where Lemma 13 is invoked. It is invoked pretty much everywhere but is mostly critical to bound the optimism overshoot (Lemma 9) and the second order error (Lemma 10). It is also used to bound the navigation error in probability (Lemma 7) but isn't necessary for this term if one is just looking for a bound in expectation.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We appreciate the reviewers for their constructive suggestions. Please find our responses to the reviews below.

**From your collective feedback, it emerges a shared concern about the numerical experiments.** Indeed, the left part of Figure 2 shows that the projection-mitigation operations of `PMEVI` have very little impact on the behavior of the algorithm. 

By monitoring the execution of the algorithms more closely, this comes from the fact that the confidence region of the bias vector is very large in the early iterations, hence the projection operation does nothing, and the mitigation operation has a very minor effect. These two operations progressively trigger over the run, but in practice it takes time, for two reasons.

- The quality of the bias estimator depends on the regret. In the early stages of learning, the regret grows linearly hence the bias estimator is way off, and the bias confidence region is accordingly very wide.
- This early phase pollutes the bias estimator/confidence region for quite some time. One idea of optimization would be to discard the early history. This would directly improve the quality of the bias estimator. 

This is what the right part of Figure 2 is for: If `PMEVI` has good bias prior information, or if the bias estimation is much better, the performance are greatly improved. The current bias estimator is sufficient to obtain minimax optimal bounds and was left not tuned **on purpose**: to make sure that the theoretical analysis is free of hard-to-understand terms that only come from heavy hand-tuning. For now, the general analysis of `PMEVI` shows that all the optimistic algorithms based on `EVI` can be patched to achieve minimax optimal regret, with a bias estimation subroutine and the projection-mitigation regularization of `EVI`.

This is why the experiment section is named "**Numerical illustrations**".
This section provides a clear direction to improve `PMEVI`: improving the bias estimation subroutine. We believe that this is an interesting direction for future work.

Meta-review: This paper closes a gap in the theoretical literature. There might be some issues in the proof, but they appear fixable.
Decision: Accept (poster)