IMED-RL: Regret optimal learning of ergodic Markov decision processes
Authors: Fabien Pesquerel
Odalric-Ambrym Maillard
Venue: NeurIPS 2022 Accept (2022)
Keywords: Reinforcement Learning
sequential learning
average-reward
lower bound
regret minimization
upper bound
optimal
Bandit
ergodic

Abstract: We consider reinforcement learning in a discrete, undiscounted, infinite-horizon Markov decision problem (MDP) under the average reward criterion, and focus on the  minimization of the regret with respect to an optimal policy, when the learner does not know the rewards nor transitions of the MDP. In light of their success at regret minimization in multi-armed bandits, popular bandit strategies, such as the optimistic \texttt{UCB}, \texttt{KL-UCB} or the Bayesian Thompson sampling strategy, have been extended to the MDP setup. Despite some key successes, existing strategies for solving this problem either fail to be provably asymptotically optimal, or suffer from prohibitive burn-in phase and computational complexity when implemented in practice. In this work, we shed a novel light on regret minimization strategies, by extending to reinforcement learning the computationally appealing Indexed Minimum Empirical Divergence (\texttt{IMED}) bandit algorithm. Traditional asymptotic problem-dependent lower bounds on the regret are known under the assumption that the MDP is \emph{ergodic}. Under this assumption, we introduce \texttt{IMED-RL} and prove that its regret upper bound asymptotically matches the regret lower bound. We discuss both the case when the supports of transitions are unknown, and the more informative but a priori harder-to-exploit-optimally case when they are known. Rewards are assumed light-tailed, semi-bounded from above. Last, we provide numerical illustrations on classical tabular MDPs, \textit{ergodic} and \textit{communicative} only, showing the competitiveness of \texttt{IMED-RL} in finite-time against state-of-the-art algorithms. \texttt{IMED-RL} also benefits from a lighter complexity.

IMED-RL: Regret optimal learning of ergodic Markov decision processes
Fabien Pesquerel"
Odalric-Ambrym Maillard malariic.aallard@nnriee fr
fabien. fabien.pesqueree @asquerel@inria.fr
Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9198-CRIStAL, F-59000 Lille, France
Abstract
We consider reinforcement learning in a discrete, undiscounted, infinite-horizon Markov Decision Problem (MDP) under the average reward criterion, and focus on the minimization of the regret with respect to an optimal policy, when the learner does not know the rewards nor the transitions of the MDP. light of their success at regret minimization in multi-armed bandits, popular bandit strategies, such as the optimistic UCB, KL-UCB or the Bayesian Thompson sampling strategy, have been extended to the MDP setup. Despite some key successes, existing strategies for solving this problem either fail to be provably asymptotically optimal, or suffer from prohibitive burn-in phase and computational complexity when implemented in practice. In this work, we shed a novel light on regret minimization strategies, by extending reinforcement learning the computationally appealing Indexed Minimum Empirical Divergence (IMED) bandit algorithm. Traditional asymptotic problem-dependent lower bounds the regret are known under the assumption that the MDP is ergodic. Under this assumption, we introduce IMED-RL and prove that its regret upper bound asymptotically matches the regret lower bound. We discuss both the case when the supports of transitions are unknown, and the more informative but priori harder-to-xxplot--pppmmlll case when they known. Rewards are assumed light-tailed semi-bounded from above. Last, we provide numerical illustrations on classical tabular MDPs, ergodic and communicating only, showing the competitiveness of IMED -RL in finite-time against state-of-the-art algorithms. IMED-RL also benefits from a light complexity.
1 Introduction
We study Reinforcement Learning (RL) with an unknown finite Markov Decision Problem (MDP) under the average-reward criterion in which learning algorithm interacts sequentially with the dynamical system, without any reset, in a single and infinite sequence of observations, actions, and rewards while trying to maximize its total accumulated rewards over time. Formally, consider finite MDP M - (S, AA p. where S is the finite set of states, AA = (A.)ses specifies the set of actions available in each state and we introduce the of pairs X'M = ((s,a) E S, A.) for convenience. Further"] p XM + P(S) is the transition distribution function and r X' - P(R) the reward distribution function, with corresponding mean reward function denoted by X' R. An agent interacts with the MDP at discrete time steps t E No and yields a random sequence (St, ac, Te) of states, actions, and rewards the following way. At each time step the agent observes the current state and decides the action a, to take based on and possibly past information, i.e. previous elements of the sequence. After playing a, observes reward r; (st, az), the current state of the MDP changes to $t11 p (-|st, 4z) and the agent proceeds sequentially. In the average-
Given set E, (E) denotes the set of probability distributions E.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

reward setting, one is interested in maximizing the limit, T ΣT= rt. when T - co, providing it exists. This setting is a popular framework for studying sequential decision making problems; it can be traced back to seminal papers such as those of Graves and Lai [997] and Burnetas and Katehakis trade-off that arises from the sequential optimization problem a learner is trying to solve while being uncertain about the very problem it is optimizing.
[1997] This theoretical framework allows to study the peploration-eplloaaaee
In this paper, one is interested in developing sampling strategy that is optimal amongst strategies that aim at maximizing the werage-reward, i.e. balancing exploration and exploitation in an optimal way. To assert optimality, we define the notion of regret and state regret lower bound with the purpose of defining a theoretically sound notion of optimality that regrer defines the discrepancy to optimality of a learning strategy, a problem-dependen regret lower bound will formally assess the minimal regret that any learning algorithm must incur on given MDP problem by computing minimal rate of exploration. Because this minimal rate of exploration depends on the problem, is said be problem-dependden
-eppedeet. While
as opposed to worst case regret study that can exist in the MDP literature (e.g. jaksch et al. (2010). Regret lower bounds currently exist in the literature when the MDP M is assumed to be ergodi Hence we hereafter make this assumption, in order to be able to compare the regret of our algorithm to an optimal bound. Similarly, to ensure fast enough convergence of the empirical estimate of the reward to the true mean, an assumption controlling the rate of convergence to the mean is necessary.
Assumption 1 (Light-tail rewards). For all x E XM, the moment generating funeerating,unncionn of the reward exists neighborhood 0:: ]ソ,> O. AA E IR such that [^] < Xa, [R=r(=)]eeepe) (exp( < oc.
Policy Regret and ergodicity are defined using properties of the set of stationary deterministic poli- cies (IM) on M. On M, each stationary deterministic policy æ S + As defines Markov reward process, i.e. a Markov chain on S with kernel Ps : s E S + p (-Is, (()) E P (S) together with rewards In : E S + r (s)) E P (R) and associated mean rewards my 8 E S + m (s)) E R. The t-steps transition kernel of π on M is denoted p We
denote p,, = Jim + Σ T-x00 1=1
p S + P(S) the Cesaro-average of Pr. A learning agent is executing a
sequence of policies ग. E (M), té 1, where n, depends on past information (Syr de, Tr yr With slight abuse of notation, a sequence of identical decision rules, म. = ग for all is also denoted x.
Gain The cumulative reward (value) at time T. starting from an initial state 8 of policy ã = (Te)e is formally given by
T Σ r2 = E M.
V., (M, n., T) = Er, M,
Σ m St, an)
= - [=1
II
Pa. M (81). (1)
1=1
For E I(M), the average-reward Vv,, (M, π,, 7) tends to m) (s1) as T - co. The gain of
policy π E I1(M). when starting from state $1 is defined by g. (51) = (D. (p.m)(11) and the optimal gain is defined as g" g=(ss) m ga (s1). (M)
{क E 11: g. (s) =g*(s) (s)) is the set of
policies achieving maximal gain on M starting from state s.
Definition 1 (Regret). The regret at time T of learning policy л = (TTe): starting at state on an MDP M is defined with respect to any x² E O, (M), as
RT, (M.T: V. x- xT (M,
In this paper, we aim find learning algorithm with asymptotic minimal regret. The Lemma ! will prove that for all optimal policies, x², regrets are the same up to a bounded term that therefore does not count in asymptotic analysis. Some authors such as Bourel et al. [202)] define the regret as TgM (s) V.(M, n, 7) which is equal to the one we defined up to a bounded term (again by Lemma D. No stationary policy can be optimal all time and the important fact that all those notions of regret induce the same asymptotic lower bound.
In the considered setting, the learning agent interacts with the MDP without any reset. The minimal assumption would be to allow the agent to come back with positive probability from any initial
We prefer the term ergodic over the more accurate one, irreducible as it is standard abuse of terminology in the MDP community. Mathematically, an MDP is ergodic if both irreducible, aperiodic and positive recurrent.

---

mistake in finite time, so that the agent is not stuck in a sub sub-optimal area of the system. This is assuming that the MDP is communicatingg that is Vs, s', 3τ, E N: p'* > 0. However, in the literature, lower bounds on the regret are stated for MDPs satisfying a stronger assumption, ergodicity. Since one is interested in crafting an algorithm matching a lower bound, we consider this stronger assumption.
Assumption 2 (Ergodic MDP). The MDP M is ergodic, that is Vs, 8', VT, 3t E : (5'1s) 0.
Intuitively, this means that for all policies and all couples of states, there exists a finite trajectory of positive probability between the states. Interestingly, the ergodic property can be assumed on the MDP or on the set of policies in which we seek an optimal one. For instance, in any communicating are MDP all s-soft policie are ergodic; more in the Experiment section S and Appendix E
Related work Had the MDP only one state, it would be bandit problem. Lower bound on the bandit regret and algorithms matching this lower bound, sometimes up to a constant factor, are well studied in the bandit literature. Therefore, bandit sampling strategies with known theoretical guarantees have inspired RL algorithms. The KL-UCB algorithm (Burnetas and Katehakis (1996]
Maillard et al. [201T). ), has inspired the strategy of the seminal paper of Burnetas and Katehakis 1997]]
as well the more recent KL-UCRL strategy (Filippi et al. 2010)) Talebi and Maillard (2018)) Inspired
by the UCB algorithm (Agrawal [195]] Auer et al. [2002] ), number of strategies implementing
the optimism principle have emerged such as UCRL (Auer and Ortne (2006)), UCRL2 (Jaksch et al.
(2010) and UCRL3 (Bourel et al. 2020] (and beyond. Azar et [201 Dann al. (2017) for the
related episodic setup). The strategy PSRL (Osband et al. 2013 is inspired by Thompson sampling (Thompson
)933).
Outline and contribution In this work, we build on the IMED strategy (Honda and Takemura (2055), a bandit algorithm that benefits from practical and optimal guarantees but has never been used by the RL community. We fill this gap by proposing the IMED-RL algorithm which we prove to be asymptotically optimal for the average-reward criterion. We revisit the notion of skeleton (Equation [2) introduced in the seminal work of Burnetas and Katehakis [1997]. with subtle but key modification that prevents prohibitive burn-in phase (see Appendix GG for further details). Further, this novel notion of skeleton enables IMED-RL to remove any tracking or hyperparameter and mimic wwwpsstiii-oooicctteettttt
algorithm. Further, this skeleton scales naturally with the studied MDP as it does not explicitly refer to absolute quantities such as the time. We prove that our proposed IMED-RL is asymptotically optimal and show its numerical competitivity.
Building on IMED, we make an additional assumption on the reward that is less restrictive than the common bounded reward hypothesis made in the RL community.
Assumption 3 to the learner There exists a known quantity M-max (I) E such that for all x E X, the support Supp(r(zz) of the reward distribution is semi-bounde from above, Supp(r(z)) c] - -o0, mmaz (z)]
rewards). For all x E X, r(z) belongs to subset Fg C P (R) known
and its mean satisfies m(x) < Mmmax (x)
Ergodic assumption
While many recent works focused worst-case regret bounds only (e.g. Domingues et al. [2021] Zanette and Brunskill 2019] Jin et al. (2018) and citations therein), studying
problem-depence optimal regret bounds has been somewhat overlooked. Being more general is always more appealing but the restriction from communicating MDPs to ergodic MDPs allows us to target exact asymptotic optimality: not just bound, not just worst-case bound. Ergodic MDPs is the only case in which explicit problem-dependent lower bounds are known and hence can be directly used build a strategy. Indeed, the main challenge towards problem-dependent optimality that existing lower bounds for exploration problems in MDPs are usually written in terms of non-convex optimization problems. This implicit form makes it hard to understand the actual complexity of the setting and, thus, to design optimal algorithms. Existing proof strategies for state-of of of-the-art algorithms (UCRL, PSRL, etc) ensure a regret for communicating MDPs but fail to provide optimality guarantees even in the ergodic case. We believe that deriving a sharp result in the ergodic case
'A policy म: S + P(A.) is e-soft if r(als) > e/|AAl for all s and a.
'The skeleton in Burnetas and Katehakis [1997 is sometimes empty some states, when too small, this causes the strategy to work well only after large enough to ensure that the skeleton contains at least one action in each state. eeg. Bernoulli, multinomial with unknown support, beta, truncated Gaussians, a mixture of those, etc.
3

---

might prove to be insightful to pave the way towards the communicating case. From a theoretical standpoint, related to UCRL type strategy, modern analysis of KL-UCRL by Talebi and Maillard (2018)
also makes the ergodic assumption. This hypothesis has also been used in the theoretical work of
Tewari and Bartlett (007) and the work offOk et al. (018 that concerns structured MDPs. Related to this assumption are works that are interested in identification and sample complexity, Waang] [2017)
introduced a primal-dual method to compute an e-optimal policy and bound the number of sample transitions to reach this goal. Jiin and Sidford [2020) relaxed the ergodic hypothesis by using a mixing hypothesis that implies the uniqueness of recurrent class for each policy. In this setting, the authors also derive a bound on the number of samples compute an s-optimal policy.
2 Regret lower bound
In this section, we recall the regret lower bound for ergodic MDPs and provide a few insights about it.
Characterizing optimal policies Relying on classical results that can be found in the books of
Puterman 1994] and Hemmndezz-Lerma and Lasserre [199]. we give a useful characterization of optimal policies that is used to derive a regret lower bound. Under the ergodic Assumption 2 of MDP M, for all policy и E MT(M), the gain is independent from the initial state, i.e. g (s) gn (8') for all states and s', and we denote it gx- Similarly, the set of optimal policies (MM) is inteeindepend since (M) = (M). Any policy π satisfy the following fixed point property
(Poisson equation)
gx + (s) = m, (s) + (x),,
where by= 8 + IR is called the bias function and is defined up to an additive constant by by (s) Σ [p= P mz) (s). We highlight that bias plays a role similar to the value function in the
discounted reward setting in which the gain always zero and Equation cattiionnrrduuee reduces the Bellman equation, giving direction in which extend our results to this other RL setuing. Interestingly, for any communicating and a fortiori ergodic MDP, the span S(bx) = max by(s) min b- (s) of the bias
sES
sES
function of any policy bounded, which allows decompose the regret in the useful following way. Lemma 1 (Regret decomposition). Under the ergodic assumption the regret of any policy π = (TT),, can be decomposed as
2 for all optimal policy O(M).
Rx.,1 (M,
Σ Ex..i (Nx(T) (M) + AEA
II Pm. - p by
(81),
(4)
<B(b.)
where No.a(T) -E-= fst 8,0, = a) counts the number of time the state-action pair (s, a) has been sampled and As,a (M) is the sub-optimality gap of the state-action pair (s, a) in M,
Asna (M) = m (s, a) (s) - -s, (s). = m (s.a) + b. g. b. (s) (5)
with pa. p(11s, a) by slight abuse of notation. Action a E As optimal if and only if As,a (M)
0, otherwise, it is said sub-optimal.
This result can be found in Puterman
1994 and is rederived in Appendix C
Under the ergodic Assumption 2 of MDP M. all optimal policies satisfy a Poisson equation while some are also being characterized by the optimal Poisson equation (see -errándee- and Lasserre 1996)), used to compute the optimal gain and bias function associated to an optimal policy,
g + Mb (s) = -mxx
m(s, + Σ p(s'ls, p(s S'ES
(6)
.E.A.
Lower bound To assess the minimal sampling complexity of sub-optimal state action pair, one must compute how far a sub-optimal state-action pair is from being optimal from an information point-of-view. A sub-optimal state-action pair (s, a) E XM said to be critical if it can be made optimal by changing reward r(s, a) and transition p (-18, a) while respecting the assumptions on the rewards and transitions. Formally, let PM P (R S)
R.
PM (v 2 q) ER R + qb M
(7)

---

denotes the potential function of v @ in M, where & q is the product measure of v and q. A pair (s, a) E AM is critical it sub-optimal and there exists Fssa and q E P (S) such that
PM (v & q) (M( where Yo (M) def g M b (s).
(8)
Note that 7/s (M)) max (M((((s p(s,a)) by the optimal Poisson equation 6
aEA,
Definition 2 (Sub-optimality cost). The sub-optimality cost of sub-optimal state-action pair (s,a) E AM is defined as K, (M) K,a (M,
def K (M, 7o (M)) where
inf (KL (r(s, @ p(l a (0 q) PM (
VEF,
REP(S)
and KL denotes the Ballback-Leibler divergence between distributions.
lower bound on the regret may now be stated for certain class of learner, the set of uniformly
consistent learning algorithm, i.e. those policies π = ) such that E.,, (N& (T)) = o (T*) for all sub-optimal state-action pair (s, a) and 0
(see Agrawal et al. 1989
Theorem 1 (Regret lower bound Burnetas and Katehakis [197]). Let M AS,,,,,r) be an MDP
satisfying Assumptions 7
2
3
For all uniformly consistent learning algorithm
B (Ns.(()))
1
lim inf
(10)
T-000
log T
K (M)
with the convention that 1/00- O. The regret lower bound is
Rx (M,T)
As.a (M)
lim inf
Σ
(11)
T-000
log
(s.a)EC(M) K (M)
where C ( K. (M) oo) is called the set of critical state-action pairs. Those
are the state-action pairs (s, a) that could be confused for an optimal one if we were to change their associated rewards and transitions distributions at the displacement cost of K. (M).
3 The IMED-RL RL Algorithm
In this section we introduce and detail the IMED-RL algorithm, whose regret matches this fundamental lower bound and extends the IMED strategy from Honda and Takemura (2015) ergodic MDPs. Indeed, for a single-state MDP, that is multi-armed bandit, IMED RL simply reduces to IMED.
Empirical quantities IMED-RL is model-based algorithm that keeps empirical estimates of the transitions p and rewards r as opposed to model-free algorithm such as Q-learning. We denote by fr(s, a) f(s, a; (1)) and (x(s, a) p(s, a; (4)) the empirical reward distributions and transition vectors after time steps, i.e. using (a,a(t) samples from the distribution r(s, a). Initially,
p(s, a; 0) the uniform probability over the state space and p(s, a; k) = (1 1/k) a; k - 1) (L/k)ss, where S& is vector of zeros except for a one at index the h samples drawn from p(-ls, a). This defines at each time step an empirical MDP M, (S,A, .A, p., On this empirical MDP, for each state, some actions have been sampled more than others and their empirical quantities therefore better estimated. We call skeleton time & the subset of state-action pairs that can be considered sampled enough at time t; it is defined by restricting A, to A. for all state 8 E S, with
(1 a A. As : (t,a(t) > log?
max N New (1) a'EA,
(12)
Since > log² x, (t) * O, hence A(t) (t), contains at least one deterministic policy. We
note that the MDP M(A(t)) del (S,A(t), r) defined by restricting the set of actions to A(t) S A
is an ergodic MDP. The restricted empirical MDP M.(((t) = (S,A(t), pr. ft) also is ergodic thanks the ergodic initialization of the estimate p. Inspired by IMED, we define the IMED-RL index.
def
Definition 3 (IMED-RL RL index). For all state-action pairs (s, a) E XM. let us define K K,,((t) def K. (M(()())) (x()) with empirical threshold (t(t) def
max (M,LA()) (f(s, a) @ p(s, a)) aEA.
Then, the IMED-RI RL index of (s, a) at time t, (t) is defined as Ht, Ne,a(t)Ks,a() + log Ns.a
(13)
Note that (t) # Yo (M, as the maximum is taken over all a A, an not just (t)..
5

---

Known support of transitions Were the support of transition known, the infimum in sub-optimality cost K,, defined by Equation p would be redefined as one over the set (gEP(() Supp(g) = Supp (P (-Is, a))}. modifying both the lower bound and IMED-RR index.
IMED-RL algorithm The ME algorithm consists in playing at each time step I, an action d, of minimal IMED-RL index at the current state st. The intuition behind the IMED-RL index is similar to the one of the IMED index for bandits and stems from an information theoretic point-of-view of the lower bound. At given time t, the frequency of play Nt,,(t) of action a E A, in state s E S, should be larger than or equal to its posterior probability of being the optimal action in that state, Nt,a(t)
(1)
exp (1N,,,a (4)), that is to say (!) 2 exp (NN (4)). Taking the logarithm and rearranging the terms, this condition rewrites H.,a (t) > log (t) at each time step The action that
is the closest to violate this condition or that violates this condition the most is the one of minimal
IMED RL index, arg min, (a),(t). (t), the one IMED-RL decides play.
Algorithm/ 1 IMED-RL: Indexed Minimum Empirical Divergence for Reinforcement Learning
Require: State-Action space XM of MDP M, Assumptions
Require: Initial state 81
for t > 1 do
Sample ag E aarg min (t) aEA.,
end for
Intuitions of the IMED -RL algorithm root the control theory of MDPs and optimal bandit theory; IMED-RL intertwines the two and the regret proof exactly follows from the following intuitions.
Control In control theory, we assume that both the expected rewards and transitions probabilities of an MDP M are known. Policy iteration (see Puterman| [1994), Bertsekas and Shreve [1978) ) is an
algorithm that computes a sequence (n,),, of deterministic policies that are increasingly strictly better until an optimal policy is reached. In the average- reward setting and under the ergodic assumption, a policy π is strictly better than another policy x' if 9x (M) > 9n' (M). The policy iteration algorithm computes the sequence of policies recursively in the following way. Initially, an arbitrary deterministic policy mo is chosen. At step n + 1 E N it computes m,,, and b,,, then swipes through the states s S in arbitrary order until it reaches one state such that there exists E A(s) with m(s, a) + p(-ls, a)b,,. > ma.. (s) + Pa (s) (s) If such an s does not exist, then it returns Ta as an optimal policy. Otherwise, un+1 1 is defined as 7z+ (s') Tn (s') for all A s' and 1 (s) E arg max {m(s, a) + p(-1s, , a) a)b=.. Such step is called a policy improvement step. Policy iteration is guaranteed finish in finite number as the cardinal of II(M) is finite. At each step E N (M.) is local function that takes into account the whole dynamic of the MDP and allows to compute, via an argmax, an optimal choice of improvement (or optimal action) based on local information; (M((T,) (r(s, (T(s, a) @ p(-|s, a)) m m(s, a) + p(s, a) a)ba... IMED-RI RL uses (M((()) and improves the skeleton similarly to policy iteration as it can be seen in the analysis 4
Bandit control A degenerate case of MDP would be one where there is only one state 8 with (PM(i) (r(s, a)) = m(s, a) by choosing the bias function be zerd Playing optimally consists in playing action with largest expected reward at each time step dg E arg max m(s a).
Bandit Learning occurs when rewards are unknown; this is the bandit problem. In that case, a lower bound on the regret similar to exxiss. Under some assumptions on the reward distributions. optimal algorithms whose regret upper bounds asymptotically match the lower bound can derived. IMED Honda and Takemura (2015), KL-UCB Maillard et al. [201]] Cappé et al. 2013 are two such examples that use indexes, i.e. computes a number I (t) at each time step and play E arg min a (t). Such indexes are crafted to correctly handle the explovation-xxploitattio trade-off.
The delayed rewards caused by the dynamic of the system is the main source of difficulty arising from having more than one state. IMED-RL -RL combines control and bandit theory
RL in Ergodic MDPs
recall that the bias function is defined up an additive constant

---

in the following way. At each time step i, restricted MDP (A(tt) is built from the empirical one M. If the condition belong to the skeleton is selective enough, then the potentials on the restricted empirical MDP (A()() may become close to those of the restricted true MDP ((A()), that (((t)) PMaAAm)) is small. We want to make policy improvements by finding, at each state an action a' E arg max (M(((())) (r(s, a) & p(-(s,)), play enough that it belongs to the skeleton which will modify yp and repeat until (M(A(())
PP Using s, the global dynamic is reduced to local function so that at each state, the agent is presented a bandit problem. This bandit problem is well estimated if MM
(M((A()))) oo is small. As opposed to the control setting, the learning agent cannot choose the state in which make the policy improvement step and it may be possible that no policy improvement step is possible at state st. However, thanks to the ergodic assumption 2 the agent is guaranteed to visit such state in finite time, it exists. There is trade-off off between the adptativity of the skeleton, i.e. how quickly one can add an improving action to define new and concentration of statistical quantities defined on the restricted MDP.
Our notion of skeleton is built on the work of Burnetas and Katehakis 1997]. We improve on their original notion of skeleton by correcting some troubles happening in the small sample regime. In particular, this forces the authors to introduce some forcing mechanism. The issues of the original definition and improvement induced by ours are listed in Appendix G One key point of our definition is that the skeleton is defined using only empirical quantities, the number of samples, and does not depends on some arbitrary reference, such as the absolute time.
Related work
Regret of IMED-RL
In this section we state the main theoretical result of this paper, which consists in the IMED-RL regret upper bound. We then sketch few key ingredients the proof.
Theorem (Regret upper bound for Ergodic MDPs). Ler M (S,A,pr)) be an MDP satisfying assumptions 1 2
Ler 0 < &
min min fIA.. (M(T)) Dea (M(T)) > 0}. The
#EIl(M) (e.0)EAM
regret of IMED is upper bounded,
D.. MM) K, (M) el', (M)
RISED-EL (M,T)=
Σ
log + 0(1),
(14)
(a.0)E((M)
where I. (M) is constant that depends on the MDP M and state s; it is made explicit in the proof detailed in Appendix D Taylor expansion allows to write the regret upper bound as
Σ
Ds,O (M)
logT +0 (log T) 10/11-
RINED- (M.T)
(15)
Kg,a (M)
(s.a)EC(M)
Were the coni-bounded reward assumption changed to a bounded reward one with known upper and lower bound, the O (log (loog)))//11// 10/11) could be made a O()) as explained Appendix
Theorem (Asymptotic Optimality). IMED RRD is asymptotically optimal, that is,
RIMSDD (M,
A s.a (M)
lim T-++o
Σ
(16)
log T
K
(M)
(s.0)EC(M)
The proof of Theorem 3 immediate from Theorem 2 by first dividing Equation 14 by log T, then by taking the limit T oo, and finally taking the limit c -> 0.
Remark While the regret lower bound, Theorem T is asymptotic by nature, our main Theorem states a finite time upper bound on the regret of IMED RL. Indeed, both Equations [4 and 13 are valid for all time T. The term O(1) appearing in Equation 14 does not depend time T and is constant that depends on both the MDP M and E. This dependency is hard to be made explicit as this term is computed as limits of convergent series that derived in the proof, Appendix [D] In Equation [4] in front of log does not exactly match the asymptotic the constant ((s.)) K (MM
(M)
7

---

upper bound (().))C(M)) K., (M) because of the e-term in the denominators. Equation 15 states
(M)
that using bounded reward hypothesis, instead of semi- bounded, allows the constant in front of the leading log T term to exactly match the asymptotic one, even in the finite time regret upper bound. In both cases, Theorem states that asymptotic optimality is achieved.
This Theorem proves the optimality of IMED-RL since the upper bound on the regret matches the lower bound of Theorem [T] Such a bound was asymptotically matched by the algorithm proposed by Burnetas and Katehakis| [1997] and recall that this algorithm and its problems are discussed in Appendix G On the other hand, the current state-of-the-ar algorithms UCRL3 and PSRL, while having some theoretical guarantees, have not been proved to match the regret lower bound. On the practical side, Q-learning is often used without much theoretical guarantee because of its usually strong practical performances. In the experiments, we will compare IMED-B RL to those three algorithms.
Related work Theorems 2 and 3 prove that IMED-RL RL is achieving the optimal rate exploration (in the wwwpiittttoonxxploatatti tradcoff sense) for ergodic MDPs. Its theoretical guarantees problem-dependent rather than forst-case/min-maal
Comparing to the log bound derived for UCRL in Theorem of Jaksch et al. (2010), less known than the vT bound, shows the benefit of our analysis for each instance, as we improve the constant factors in the leading terms: their dependency is 34D2 A.A.AAA/A..
A/A, A, where is a sub-optimality gap and D the diameter of the MDP.
Sketch of proof Though full proof is given in Appendix D we sketch here the main proof ideas that follow directly from the intuitions behind the IMED-RL conception. The regret is decomposed into two terms, the bandit term when the local bandit problems defined by (AA(O) is well estimated, and the skeleton improvement term that controls the probability that the local bandit problem not well estimated. This second term is managed by controlling the number of policy improvement steps and using concentration properties of empirical quantities defined on the skeleton.
The main Theorem 2 follows from the following proposition that is proved in Appendix D Recall from Lemma that for all state-action pair E .MM. N₂ (T) = =I= 1 ((s,,,)) x) counts the number of time the state-action pair x has been sampled.
Proposition 1. For all state-action pair x XM, for all
0,
(ttt) < (T) - S(T",
(17)
where we introduced the bandit term, (T), and the skeleton improvement term, S(T),
(T) Σ 1 { 2t = x, (M. _ CM (.(())))))) b & xe).
(18)
T'
S(T) = Σ
1
0 MM (A(1)) C (M (ID0),/bbM... (A()))) - bb EEJ.
(19)
Furthermore, E (S(T)) = (1), E (B, (B)) = (11 for non-critical state-action pair, while for a
critical state-action pair I,
4₂ (M)
E (B)
log + 0(1)
K MM) sT, (M)
5 Numerical experiments
In this section, we discuss the practical implementation and numerical aspects of IMED-RL and extend the discussion in Appendix Source code is available on github
Computing IMED-RL index At each time step, we run the value iteration algorithm on M.((()) to compute the optimal bias and the associated potential function (M,())())) This task is standard.
Once done, one must compute the value of the optimization problem K., (t) which belongs to the category of convex optimization problem with linear constraint. Such problems have been studied
Plain text URL is http://giilbbboom/ralleneggggggp

---

under the name of partially-fiitt convex optimization, e.g. in Borwein and Lewis [199]]. It is possible to compute ... (t) by considering the Legendre- Fenchel dual and one does not need to compute the optimal distribution to know the value of the optimization problem.
Proposition 2 (Index computation. Honda and Takemura 2015 Theorem 2). Let (s, a) be in XM. M = Mmaa (8.a) + max b b (s), and y > (M((((,,) a) & p( s, a)), then
x'ES
K 800 (M,7) {
max E R-r(s,a) [log (1 (R bM) - 7) 8-p(11.0)
FM>7
0G म
(20)
to0
otherwise
1/7 < (n((( a) 2 p(-1s, a)), then K. (M,7)=00 =0
In particular, this Proposition 2 sometimes allows to write K.. (t) almost in close form, e.g. when F.sa defined in Asumptions is set of multinomials with unknown support (and only the upper bound Mmaz is known). In Appendix
F we discuss this numerical computation further.
Computational complexity In terms of state and actions spaces sizes, the complexity of IMED-RL at each time step scales as O(5² A), the complexity of value iteration. Indeed, at each time step, IMED-RL runs value iteration using actions available the skeleton, then computes the indexes of the available actions at the current state, and finally pick an argmin. The complexity of value iteration is O(5"AA A), the complexity computing the A necessary indexes is O(S A), and the complexity of picking argmin amongst those A indexes is ((A). Therefore, the per-time-step complexity of IMED-RR RL scales as O(S²A) A). However, this scaling is mainly an upper-bound as value iteration is run with actions that within the skeleton. By design of the skeleton, experimentally observe that, after some time, the skeleton contains one action per state (the optimal onc). We provide more details in Appendix F Lazy update paragraph.
Practical comparison In practice, most of the complexity of IMED-RL is in the analysis rather than in the algorithm: compared to PSRL and UCRL3, IMED-RL. does not take confidence parameter nor any hyperparameter. Also, IMED-RL uses value iteration as a routine, which is faster than the extended value iteration used in UCRL3. Q-learning technically takes exploration parameter (e-greedy exploration) or exploration scheme when it is slowly decreased with time.
Environments In different environments, we illustrate in Figure 2 and Figure the performance of IMED-RL against the strategies UCRL3 Bourel et al. [2020). PSRL Oshand et al. (2013) and Q- learning (run with discount 7 0.99 and optimistic initialization). As stated during the introduction, any finite communicating MDP can be turned into an ergodic one, since on such MDPs, any stochastic policy क : S + P (As) with full support Supp (=()) A, is ergodic. Hence by mixing its transition p with that obtained from playing a uniform policy, formally P-(-1s, a)
(1 (1-E)p(-Is. a.)) + Σ p(-|s, a for an arbitrarily small
one obtain an ergodic MDP.
d'EA,
In the experiments, we consider an ergodic version of the classical s-state river-swim environment, 2-room and 4-room with 10-3, and classical communicating versions (E 0).
0.6
0.4
G.G
0.6
0.6
(r 0.989;
0.35
0.35
#2
#3
FL-1
LL
0.05
0.05
0.05
0.05
0.4
(r 0.05)
Figure 1: The ergodic n-state RiverSwim MDP. In each of the n states, there are two actions RIGHT and LEFT. The left action is represented with a dashed line and the RIGHT with plain line. Rewards are located at the extremities of the MDP.
n-states RiverSwim environment As illustrated by Figure 2 the performances of IMED -RL are particularly good and the regret of IMED-RL is below the regrets of all its competitors, even when the MDP is communicating only. This numerical performance grounds numerically the previous theoret- ical analysis. While using IMED RL in communicating MDPs is not endorsed by our theoretically analysis, is interesting to see how much this hypothesis amounts in the numerical performances of IMED-RL. We therefore ran experiment on another classical environment, 2-rooms.

---

RiverSwim v6
EigodicRiverSving v6
IMEC-AL
IMED-RL
20
PARL LECLL
PARI
LETILS
2.5
Regret Tg" sum tr.
2.0
2.0
Regret
1.5
1.5
1.0
0.5
00
0.0
Time slops
X12
Time steps
Figure Average regret and quantiles (0. and 0.9) curves of algorithms on standard communicating 6-states RiverSwim (left) and an ergodic 6-states RiverSwim (right).
x1o!
4-rooms
PSRL
UCRLa
Qlearning
2-
3-
Reggett:
4-
5-
14
6-
Time steps
x1e*
Figure 3: Average regret and quantiles (0.1 and 0.9) curves of algorithms (right) corresponding learning on 4-room (left) grid-world environment, with 20 states: the starting state is shown in red, and the rewarding state is shown in yellow. From the yellow state, all actions bring the learner the red state. Other transitions are noisy as in a frozen-lake environment.
n-rooms environment As illustrated by Figure 3 the performances of IMED-RL are particularly good, even surprisingly good, in this communicating only environment. Those experiments are clue that the IMED-RL strategy may still be reasonable, although not necessarily optimal in some communicating MDPs. All experiments take less than an hour to run on standard CPU.
Future work Although not intended for non-ergodic MDPs, IMED- RL exhibits taaee-of-th-attt numerical performances in communicating only MDPs (see Appendix F.2 for additional experiments). Hence, IMED-RL might prove be insightful pave the way towards the communicating case as it seems possible to get controlled regret also in the case of communicating MDPs. Both the problem-dependent and worst-case regret bounds are interesting in this regard. Another direction intend to explore is the adaptation of IMED- -RL main ideas to function approximation frameworks, such neural networks and kernel methods.
Conclusion
In this paper. we introduced IMED-RL, RLD a numerically efficient algorithm solve the average-reward criterion problem under the ergodic assumption for which we derive an upper bound on the regret matching the known regret lower bound. Further, its surprisingly good numerical performances in communicating only MDPs open the path to future work in MDPs that are communicating only.
Acknowledgments and Disclosure of Funding
This work has been supported by the French Ministry of Higher Education and Research, Inria, Scool, the Hauts-de-FF France region, the MEL and the I-Site ULNE regarding project R-PILOTE-19-0V APPRENF. The PhD of Fabien Pesquerel is supported by grant from École Normale Supérieure.
10

---

References
R. Agrawal. Sample mean based index policies with O(log n) regret for the multi-armed bandit problem. Advances Applied Probability, 27(4):1054-100 1078, 1995.
R. Agrawal, Teneketzis, and V. Anantharam. Asymptotically efficient adaptive allocation schemes for controlled processes: Finite parameter space. IEEE Transactions on Automatic Control, 34(3), 1989.
Auer and Ortner. Logarithmic online regret bounds for undiscounted reinforcement lcarningg In B. Schölkopf, J. C. Platt, and T. Hoffman, editors, Proceedings of the 20th conference on advances in Neurul Information Processing Systems, NIPS '06, pages 49-56, Vancouver, British Columbia, Canada, dec 2006. MIT Press. ISBN 0-262-19568-2.
P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed handit problem. Machine Learning, 47(2-3):235-256 2002.
M. G. Azar, I. Osband, and R. Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263 272. PMLR, 2017.
D. P. Bertsekas and S. F. Shreve. Stochastic Optimal Control (The Discrete Time Case). Academic Press, New York, 1978.
J. Borwein and A. Lewis. Duality relationships for entropy- like minimization problem. SIAM Journal on Computation and Optimization, 29(2):325-338, 1991.
H. Bourel, O. Maillard, and M. S. Talebi. Tightening exploration in upper confidence reinforcement learning. In International Conference on Machine Learning, pages 1056-1066. PMLR, 2020.
A. Burnetas and M. Katehakis. Optimal adaptive policies for Markov decision processes. Mathematics of Operations Research, pages 222-255, 1997.
A. N. Burnetas and M. Katchakis. Optimal adaptive policics sequential allocation problems, Advances Applied Mathematics, 17(2):122-144 1996.
X.-R. Cao. Reinforcement Learning, pages 289-340. Springer Boston, MA, 2007. ISBN 978- 778-0-387-69082-7. URL 1ttLL/tttt://dda...o//....0////0 org/oogg///... 10w00000009700 0 0-7 69082-7-6
doi: 00.10077978-0-387-66000
Cappé, A. Garivier, O.-A Maillard, R. Munos, and Stoltz. Kullback-Leibler upper confidence bounds for optimal sequential allocation. Annals of Statistics, 116))1511--141, 2013.
C. Dann, T. attimmree, and Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30, 2017.
A. Dembo and O. Zeitouni. Large deviations techniques and applications. Elearn, 1998.
O. D. Domingues, P. Ménard, E. Kaufmann, and M. Valko. Episodic reinforcement learning finite mdps: Minimax lower bounds revisited. V. Feldman, K. Ligett, and S. Sabato, editors, Proceedings of the 32nd International Conference Algorithmic Leurning Theory. volume 132 of Proceedings of Muchine Learning Research, pages 578-598. PMLR, 16-19 Mar 2021. URL https::/prooceednggs mlr. mlr press/ v132/ domingues21a. html
Filippi, O. Cappé, and A. Garivier. Optimism in reinforcement learning and Kullback- divergence. In Proceedings of the 48th Annual Allerton Conference on Communication, Control, and Computing, Monticello. US, 2010.
L. Graves and T. L. Lai. Asymptotically efficient adaptive choice of control laws incontrolled markov chains. SIAM journal on control and optimization, 35(3):715-743, 1997.
O. Hernández- and J.-B, Lasserre. Discrete-Time Markov Control Processes. Springer New York, 1996. doi: 10. 100100000771111 1-4612-0729-0. URL htttttttp///aal laas. fw/hall 02095866
J. Honda and A. Takemura. Finite-time regret bound of a bandit algorithm for the semi-bounded support model. arXiv:1202.2277 2012.
J. Honda and A. Takemura. aom-asymptotic analysis of a new bandit algorithm for semi-bounded rewards. Machine Learning, 16:3721-3756, 2015.
T. Jaksch, R. Ortner. and P. Auer. Near Netr-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research. 19:1563-16000 August 2010. ISSN 1532-4435.

---

C. Jin, Z. Allen-Zhu, S. Bubeck, and M. I. Jordan. Is q-learning provably efficient? In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL httplttt/ppppceeeeeeee meteredddnnnnneurppssss neurips Paper Paperrppff pdf
and A. Sidford. Efficiently solving MDPs with stochastic mirror descent. In D. III and A. Singh. editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 4890-4900. PMLR, 13-18 Jul 2020. URL https: pptpe//eicoceedisss mlr. jttps/eesse//jjjppp..... in20f. html
A. Maillard, R. Munos, and G. Stoltz. A finite-time analysis of multi-armed bandits problems with Kullback- Leibler divergences. In Proceedings of the 23rd Annual Conference Learning Theory, Budapest, Hungary, 2011.
J. Ok, A. Prouticre, and D. Tranos. Exploration in structured reinforcement learning. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Desa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. (tRtss/ps:// httcps://proceedinngg neurips pdf
cc/paper/ papaaprr2018//// /ctpppppp/o/ooo/////////////oa00
I. Oshand, D. Russo, and B. Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013.
M. L. Puterman, Markov Decision Processes Discrete Stochastic Dynamic Programming. John Wiley Sons, Inc., New York, NY, 1994.
M. S. Talebi and O.-A. Maillard. Variance-awar aware regret bounds for undiscounted reinforeement learning in mdps. In Algorithmic Learning Theory, pages 770-805, 2018.
A. Tewari and P. L., Bartlett. Optimistic linear programming gives logarithmic regret for irreducible mdps. In J. C. Platt, D. Koller, Y. Singer, and S. T. Roweis, editors, Proceedings of the 2 conference on advances in Neural Information Processing Systems, NIPS '07, Vancouver, British Columbia, Canada, dec 2007. MIT Press.
W. R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):255-294, 1933.
M. Wang. Primal-dual learning: Sample complexity and sublinear run time for ergodic markov decision problems. ArXiv, abs/1710.06100 2017.
A. Zanette and F. Brunskill. Tighter mublem-dependenn regret bounds in reinforcement learning without domain knowledge using value function bounds. K. Chaudhuri and R. Salakhutdinov, editors, Proceedings of 36th International Conference on Machine Learning, volume of Proceedings of Machine Learning Research, pages 7304-7312. PMLR, 09-15 Jun 2019. URL htttp:// mlr, S...ppeess/vV) v zanette19a. html
12


Reviews:
[{"review_id": "mCwa_0WHbpk", "reviewer": "Reviewer_mZe4", "summary": "This paper studies regret minimization in infinite-horizon average-reward MDPs. They propose a new algorithm based on Indexed Minimum Empirical Divergence (IMED) bandit algorithm, and show that the new algorithm achieves a regret matching the asymptotic problem-dependent lower bounds.", "questions": "1. How should I compare the asymptotic problem-dependent lower bound with the $\\sqrt{T}$-type minimax lower bound? Does the algorithm also ensures a $\\sqrt{T}$ finite time regret?\n2. What's the difficulty of extending current analysis to the communicating setting?\n3. The regret definition is different from the one used in UCRL paper: $R_T = \\sum_t (g_{\\pi^{\\star}} - r_t)$. How should I compare these two types of definitions?\n4. Do you see a direct way to extend to linear function approximation?", "limitations": "See \"Strengths And Weaknesses\"", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: the paper is clearly written. The proposed algorithm has strong theoretical guarantee and competitive empirical performance.\n\nWeakness: Many important details are hidden in the Appendix (for example, the limitation of existing work is deferred to Appendix G). Thus, the contribution of this paper is not clear at first glance compared to existing works. I think more highlight s on the ", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "7W7N-MoSeUH", "reviewer": "Reviewer_gX3h", "summary": "The paper considers ergodic MDPs and proposed an index policy IMED-RL. The IMED-RL index is built on the IMED policy for multi-armed stochastic bandits. Regret bound for IMED-RL is provided and shown to match the lower bound for ergodic RL problems.", "questions": "- It looks like one could compute the IMED-RL index for communicating MDPs. Would it be possible to apply IMED-RL to communicating MDPs with (possibly weaker) regret bounds?\n- Are there any connection between the IMED-RL index and some optimistic values?", "limitations": "The assumptions and limitations are clearly stated in the paper.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The proposed policy is based on the IMED-RL index which is new for RL and different from commonly used optimism based  algorithms.\n\n- Regret bounds of IMED-RL are provided for ergodic MDPs and the upper bound and lower bound match.\n\n- Numerical experiments show better performance of IMED-RL compared with prior algorithms with certain regret guarantees.\n\nWeaknesses:\n- The ergodic assumption is very strong. Most MDPs including RiverSwim in the numerical experiment are not ergodic. The ergodic assumption is not typical and there are many RL algorithms with performance guarantees without the ergodic assumption. Results requiring the ergodic assumption seem very limited. \n\n- The provided justification for focusing on ergodic MDPs is that it's the only class of MDPs with regret lower bounds. However, in Jaksch et al. [2010b], has a regret lower bound for the much more general class of communicating MDPs.\n\n- Minor: the definitions of several notations are hard to find, making the paper not easy to follow. For examples, the definition of the count number N_{s,a}(T) is hidden in the statement of Lemma 1, and the definition of \\phi_M is a bit hidden within lines.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "1gz6Dq7f_L-", "reviewer": "Reviewer_UdXd", "summary": "This paper considers regret minimization in ergodic undiscounted MDPs under the average-reward criterion. It builds upon the classic results by Burnetas and Katehakis (1997) for this setting, and provides an adaptation of the IMED bandit algorithm (Honda and Takemura, 2015) to this setting. This algorithm, called IMED-RL, matches asymptotically the lower bound by Burnetas and Katehakis, and can thus be considered optimal. The theoretical results are complemented by numerical simulations showing that IMED-RL is very efficient in practice.", "questions": "1. How would the worst-case regret of IMED-RL compare with the one of UCRL and PSRL?\n2. What do you think is the advantage of IMDEL-RL over the other exploration algorithms in practice?\n\nMinor:\n- line 19: communicative -> communicating\n- Definition 1: s_1 should be s or vice-versa\n- line 92: why is UCB \"infamous\"?\n- line 124: communication -> communicating\n- Footnote 2: square bracket\n- line 258: \"numerical issues\" is an odd choice of words, it usually refers to numerical problems in the implementation. I think you mean something like \"empirical aspects\"\n- line 273: missing space after PSRL", "limitations": "Limitations should be discussed more. For instance, how does IMED-RL scale to problems with many states and actions?", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well written and clear. The authors do a great job in explaining the theoretical framework, which is classic but is also a notoriously complicated one. The difference between existing results and original contributions is also well explained. I would only spend more words on describing the original IMED (bandit) algorithm of which IMED-RL is an adaptation to MDPs.\n\nOriginality is limited, since the work builds upon a well established theoretical framework and an existing algorithmic idea. However, there is some originality in the theoretical analysis, for instance in how the concept of skeleton.\n\nThe results are significant for the area of efficient exploration in RL. As mentioned by the authors, it is not easy to match the lower bound by B&K with a reasonably practical algorithm. Instead, besides its strong theoretical guarantees, IMED-RL shows good performance in practice too.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept