Mahsa Asadi
email: mahsa.asadi@inria.fr

Upper Confidence Reinforcement Learning exploiting state-action equivalence

Leveraging an equivalence property on the set of states of state-action pairs in an Markov Decision Process (MDP) has been suggested by many authors. We take the study of equivalence classes to the reinforcement learning (RL) setup, when transition distributions are no longer assumed to be known, in a discrete MDP with average reward criterion and no reset. We study powerful similarities between state-action pairs related to optimal transport. We first analyze a variant of the UCRL2 algorithm called C-UCRL2, which highlights the clear benefit of leveraging this equivalence structure when it is known ahead of time: the regret bound scales as Õ(D

√

KCT ) where C is the number of classes of equivalent state-action pairs and K bounds the size of the support of the transitions. A non trivial question is whether this benefit can still be observed when the structure is unknown and must be learned while minimizing the regret. We propose a sound clustering technique that provably learn the unknown classes, but show that its natural combination with UCRL2 empirically fails. Our findings suggests this is due to the ad-hoc criterion for stopping the episodes in UCRL2. We replace it with hypothesis testing, which in turns considerably improves all strategies. It is then empirically validated that learning the structure can be beneficial in a full-blown RL problem.

Introduction

Let M = (S, A, p, ν) be an (undiscounted) MDP where S denotes the discrete state space, A the discrete action space, p the transition kernel such that p(s |s, a) denotes the probability of transiting to state s , starting from state s and executing action a, and ν is a reward distribution function on R = [0, 1] with mean function denoted µ. Many MDPs exhibit strong similarities between different transitions. This is typically the case in a grid-world MDP when taking action Up from state s or right from state s when both are far from any wall results in similar transitions (typically, move to the target state with probability p and stay still or transit to other neighbors with the remaining probability), see Figure 1. Leveraging an equivalence structure is popular in the MDP literature (see [START_REF] Abel | Near optimal behavior via approximate state abstraction[END_REF], [START_REF] Li | Towards a unified theory of state abstraction for mdps[END_REF] or Ravindran & Barto (2004)). However, most notions are unfortunately not well adapted to a reinforcement learning (RL) setup when the transition probabilities are unknown to the learner.

We further want not only to compute a near-optimal policy but to minimize the cumulative regret incurred while interacting with the MDP, in a never ending single stream of observations, against an optimal policy for the average regret criterion. This problem has received a lot of attention in the recent literature after the seminal work of [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] introduced the UCRL2 algorithm that uses the optimism in face of uncertainty principle coming from the multi-armed bandit literature [START_REF] Auer | Finite time analysis of the multiarmed bandit problem[END_REF] presents a regret guarantee of Õ(DS √ AT ) after T steps for any unknown MDP with S states, A actions per state, and diameter D. Obviously, the regret is dependent on the number of states and actions and increases as these parameters grow. Our goal in this paper is to leverage similarity structures to reduce this dependency. We consider to that end the following key definition: Definition 1 (Similar state-action pairs) The pair (s , a ) is ε-similar to the pair (s, a), for ε = (ε p , ε µ ) ∈ R 2 + , if p(σ s,a (•)|s, a) -p(σ s ,a (•)|s , a ) 1 ε p , (similar profile) and |µ(s, a) -µ(s , a )| ε µ , (similar rewards) where σ s,a : {1, . . . , S} → S indexes a permutation of states such that p(σ s,a (1)|s, a) p(σ s,a (2)|s, a) . . . p(σ s,a (S)|s, a). We call it a profile mapping. Remark 1 The similarity is not only stated about states, but about state-action pairs. Remark 2 (0, 0)-similarity is an equivalence relation. It thus induces a canonical partition of S × A, which we denote C. In appendix A, we show that in typical grid-world MDPs, the number of classes of state-action pairs using Definition 1 stays small even for large SA. This is no longer the case without the ordering. Also the ordering makes the notion more robust, see Lemma 2. Remark 3 The profile mapping σ s,a is not unique in general, especially if distributions are sparse. We assume in the sequel that the restriction of σ s,a to the support of p(•|s, a) is uniquely defined.

The goal of this paper is to adapt the UCRL2 strategy to take advantage of this structure which outperforms it when acting in MDPs with few number of classes and large number of state and actions. We do so by aggregating the information of similar state-action pairs when estimating MDP's transitions.

Literature overview The literature relevant to our standpoint can be categorized into two main parts. First, the rich literature on state-aggregation and state-abstraction. We refer to [START_REF] Abel | Near optimal behavior via approximate state abstraction[END_REF] for a good survey of recent approaches, [START_REF] Li | Towards a unified theory of state abstraction for mdps[END_REF] on earlier methods, Ravindran & Barto (2004) that introduces interesting definitions but with no algorithm or regret analysis, and [START_REF] Anand | Asap-uct: Abstraction of state-action pairs in uct[END_REF], similar to our work in that it considers state-action equivalence, but unlike us does not consider orderings, transition estimation errors or regret analysis; Interesting works revolving around complementary RL questions include the work on selection amongst different state representations in Ortner et al. (2014) or on state-aliasing from [START_REF] Hallak | Model selection in markovian processes[END_REF]. The most relevant works to our approach are the work of Ortner (2013) on aggregation of states (but not of pairs, and with no ordering) based on concentration inequalities, a path that we follow, and of Dean et al. (1997) considering partitions of the state-space. Further, [START_REF] Ferns | Metrics for finite markov decision processes[END_REF] and [START_REF] Ferns | Methods for computing state similarity in markov decision processes[END_REF] work on the bi-simulation metrics suggests to resort to optimal transport, which is intimately linked with Definition 1 when using the Hamming metric c(i, j) = I{i = j} defined on i, j ∈ {1, . . . , S} to define the transport cost (see details in Appendix B). However they consider an MDP, not RL setup. Second, the articles regarding UCRL2-style algorithms for discrete MDPs following [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] and inspired from multi-armed bandits. Let us mention the Regal algorithm [START_REF] Bartlett | REGAL: A regularization based algorithm for reinforcement learning in weakly communicating MDPs[END_REF], KL-UCRL that replaces Weissman concentration with a better-behaved Kullback Leibler concentration [START_REF] Filippi | Optimism in reinforcement learning and Kullback-Leibler divergence[END_REF], another powerful replacement of Weissman bounds suggested in [START_REF] Maillard | How hard is my MDP? "the distribution-norm to the rescue[END_REF], and a recent Thompson sampling approach inspired from bandits [START_REF] Agrawal | Optimistic posterior sampling for reinforcement learning: Worst-case regret bounds[END_REF]. Some analysis have tried to reduce the regret dependency on the number of states, such as in [START_REF] Azar | Minimax regret bounds for reinforcement learning[END_REF] (restricted to a fixed, known and small horizon), or in [START_REF] Dann | Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement learning[END_REF], using refined time-uniform concentration inequalities similar to that of Lemma 1 below. Although the concept of equivalence is well-studied in MDPs, no work seems to have investigated the possibility of defining an aggregation first based on state-action pairs instead of states only for reinforcement learning problems, and second using optimal transportation maps combined with statistical tests. Especially, the use of profile maps seems novel and we show it is also effective.

Outline and contribution

We first introduce a similarity measure of state-action pairs based on equivalence of profile distributions, see Definition 1. To our knowledge, while other notions of equivalence have been introduced, it is the first time profile (ordering) of distributions is explicitly used in a discrete reinforcement learning (as opposed to MDP) setup. Section 3, studies the potential benefit of exploiting this structure. We introduce C-UCRL2(C, σ), a natural variant of UCRL2 that has access to the equivalence classes. We prove in Theorem 1 that its regret scales as that of UCRL2, except by replacing a

√

SA factor with √ C, where C is the number of classes. More convincingly we provide numerical illustration that this improvement can be massive, reducing by one to several order of magnitudes the accumulated regret. In Section 4, we move to the more realistic situation when the profiles σ are unknown. We modify C-UCRL2(C, σ) to estimate the mappings, provide illustration as well as a novel theoretical regret guarantees thanks to a non-expensive property of the ordering operator (Lemma 2). Section 5 then deals with the fully agnostic and most challenging scenario, when the partition must be learned from data. While it is intuitive clear that an important regret reduction is achievable when knowing C and C SA, we ask the following non-trivial question: can such an improvement still be observed without any prior knowledge on the structure? The cost of learning C could indeed be prohibitive. To answer this question, we first provide an online clustering-based algorithm (agnostic to the number of classes) that provably guarantees valid cluster probability distribution estimations (see Lemma 3). We naturally modify C-UCRL2(C, σ) in a sound way and highlight the fact that this strategy still outperforms the vanilla UCRL2 algorithm on experiments, thus showing the advantage of considering the classes. However, we also note that the straightforward derivation of the algorithm from UCRL2 suffers from a much higher regret than its oracle counter part knowing C. While it suggests the price for learning C is too high, we show the high regret is in fact caused by the stopping criterion of UCRL2, that was actually a trick, as acknowledged by the authors, and reveals to be sub-optimal when handling the unknown classes. This leads us to the second main contribution of this paper, that is to revisit the stopping criterion used in UCRL2. The old intuition was to "recompute the policy when confidence bounds have changed a lot" following a simple "doubling trick" heuristics. We proposed instead a mathematically more rigorous stopping rule by testing whether "the optimistic model corresponding to the chosen policy is still correct". This very simple idea is illustrated on numerical experiments in section 6, where it proves to be massively beneficial, reducing the regret by several order of magnitudes again, even in the most challenging scenario (unknown C). Interestingly, the modification also benefits UCRL2.

While the main goal of the paper is to numerically illustrate the benefit of these two powerful ideas, we provide some theoretical results for soundness of the approach, thus paving the way towards a sharper understanding of regret minimization in discrete structured Markov Decision Processes.

UCRLsetup and notations

Let π : S → P(A) denote a possibly stochastic policy and µ π (s) = E Z∼π(s) [µ(s, Z)] denote the mean reward after following policy π in state s. Let p(s |s, π(s)) = E Z∼π(s) [p(s |s, Z)] and write P π f to denote the function s → s ∈S p(s |s, π(s))f (s ). Definition 2 (Value) The expected cumulative reward of policy π when run for T steps from initial state s 1 is denoted as:

V π T (s 1 ) = E T t=1 r(s t , a t ) = T t=1 (P t-1 π µ π )(s 1 ) .
where a t ∼ π(s t ), s t+1 ∼ p(•|s t , a t ), and r(s, a) ∼ ν(s, a).

Definition 3 (Average gain) The average transition operator is

P π = lim T →∞ 1 T T t=1 P t-1 π . The average gain g π is: g π (s 1 ) = lim T →∞ 1 T R π,T (s 1 ) = (P π µ π )(s 1 ) .
Definition 3 requires some mild assumption on the MDP for the limits to makes sense. It is shown (see, e.g. Puterman (2014)) that the average gain achieved by executing a stationary policy π in a communicating MDP M is well-defined and does not depend on the initial state, i.e., g π (s 1 ) = g π .

For this reason, we restrict to such MDPs in the rest of this paper. Let denote an optimal policy, that is such that 1 g = max π g π . The following definition captures the dominant term of the regret of any algorithm, as justified by the first steps of the regret analysis from where n t1:t2 (s, a) denotes the number of observations of state-action pair (s, a) between time t 1 and t 2 . We provide the detailed code of UCRL2 in Appendix D for reference.

Remark 4 The bounds bH and bW are obtained from simple union bounds with a slightly loose analysis. A more careful bound using similar arguments suggests to use

b H t (s, a, δ) = log(2t 2 (t+1)/δ) 2N t (s, a)∨1 , b W t (s, a, δ) = 2 log(t 2 (t+1)(2 K -2)/δ) N t (s, a)∨1 ,
where K |Support(p(•|s, a))|, instead to insure that M ∈ M t holds w.p.h. than 1-δ uniformly ∀t.

Tighter bounds An easy improvement is to further modify these naive bounds based on a unionbound argument over all time steps with proper time-uniform concentration bounds using selfnormalization (following the Laplace method to replace optimization with integration see Peña et al. (2008); Abbasi-Yadkori et al. ( 2011)), that we provide below for completeness.

Lemma 1 (Time-uniform concentration) ∀(s, a) ∈ S × A and any [0, 1]-bounded distribution with mean µ(s, a):

P ∀t ∈ N |µ Nt(s,a) (s, a) -µ(s, a)| b H Nt(s,a) (δ) δ , with b H n (δ) = (1+ 1 n ) log(2 √ n+1/δ) 2n .
Further, for any discrete distribution p(•|s, a) on S with support2 of size K |S|

P ∀t ∈ N p Nt(s,a) (•|s, a)-p(•|s, a) b W Nt(s,a) (δ) δ , with b W n (δ) = 2(1+ 1 n ) log √ n+1 2 K -2 δ n . Hence we replace b H t (s, a, δ 2SA ) with b H Nt(s,a) ( δ 2SA ), and b W t (s, a, δ 2SA ) with b W Nt(s,a) ( δ 2SA
) in the definition of M t . As the bounds for rewards and transitions are similar, from now on, we assume the mean function µ is known, to simplify the presentation. Remark 5 In contrast a peeling argument would lead to a seemingly better log log scaling in place of the log square-root scaling, but with increased multiplicative constants compared to (1 + 1/n). The bound using the Laplace method is better in practice (for n < 2.10 9 when δ = 0.01).

Class-UCRL : known class and profiles

We now introduce the first natural modification of UCRL2, that takes into account the similarity of state-action pairs. We assume that an oracle provides us with a perfect knowledge of the equivalence classes C plus profile maps σ = (σ s,a ) s,a of all state-action pairs. In this ideal situation, our goal is to illustrate the potential benefit of taking the similarity into account. We explain the modification of the algorithm, provide a bound on the regret and illustrate its behavior on numerical experiments.

Class-UCRL2

The most obvious modification is to aggregate observations from all state-action pairs in the same class in order to build more accurate estimates. Formally (i) for a class c ⊂ S × A, with N t (c) = s,a∈c N t (s, a) many observations, we define for each index ∈ {1, . . . , S},

p σ Nt(c) (i|c) = s,a∈c N t (s, a)p Nt(s,a) (σ s,a (i)|s, a) N t (c) .
Then, (ii) for a partition C of S × A in equivalence classes,

M t (C) = (S, A, p, ν) : p ∈ Pw(C), ∀c ∈ C∀(s, a) ∈ c, p σ Nt(c) (σ -1 s,a (•)|c) -p(•|s, a) 1 b W Nt(c) δ 2C .
where Pw(C) denotes the state-transition functions that are piecewise constant on C (p(•|s, a) has same value for all (s, a) ∈ c). Finally (iii), we redefine the stopping criterion as

t k+1 = min t > t k ; ∃c ∈ C : n t k :t (c) max{N t k (c), 1} .
The precise modified steps of the algorithm are presented in Algorithm 1 in appendix D.

Definition 5 (Class-UCRL2) C-UCRL2(C, σ) is defined as UCRL2 using modifications (i,ii,iii).

Remark 6 It is crucial to remark that the algorithm is not using classes as "meta" states (that is, replacing the states with classes); Rather, the classes are only used to group observations from different sources and build more refined estimates for each state-action: The plausible MDPs are built using the same underlying state S and action space A, unlike e.g. in Ortner ( 2013).

Regret guarantee A modification of the analysis from Jaksch et al. ( 2010) yields: Theorem 1 (Regret of C-UCRL2(C, σ)) With probability higher than 1 -2δ, uniformly over all time horizon T ,

Regret(C-UCRL2(C, σ), T ) D 4 ln 2C √ T + 1(2 K -2) δ + 2 √ 2 + 1 √ CT +D 2(T + 1) log( √ T + 1/δ) + DC log 2 ( 8T C ) 17D CT K ln(C √ T /δ)
, where K bounds the support of the transition maps, and the proof is provided in appendix F.

The regret of this algorithm that knows the structure (but not the distributions) thus scales with the number of classes C, hence achieving a massive reduction when C SA. This is the case in many grid-worlds thanks to our definition using orderings, see Appendix A. Also in such grid-worlds where transitions are local, K < 5 is a small constant. A comparison of the regret accumulated after T = 2 × 10 4 steps on a 2-room MDP with 25 states (see Section 7), shows that C -UCRL2 has regret in 149.0 ± 33.8 while UCRL2 has regret in 19487 ± 0.0 Now on a 4-room MDP with 49 states, we get a regret in 179.6 ± 35.7 versus 97131.8 ± 1003.3 for UCRL2 .

Known classes, unknown profile mappings

In this section, we consider a more realistic setting when the oracle provides the classes C to the learner but none of the profile mappings (σ s,a functions) are available. In this more challenging situation, the algorithm C-UCRL2(C, σ) must be amended to use estimates of the profile mappings σ s,a for each s, a; we call the resulting algorithm C-UCRL2(C). Modified aggregation Let σ s,a be any profile mapping σ such that at time t, p Nt(s,a) (σ(1)|s, a) p Nt(s,a) (σ(2)|s, a) . . . p Nt(s,a) (σ(S)|s, a). We build the modified empirical estimate as:

p σ Nt(c) (i|c) = s,a∈c N t (s, a)p Nt(s,a) ( σ s,a (i)|s, a) N t (c) .

Modified set of plausible MDPs

We then modify the definition of M t (C) to use for p ∈ Pw(C),

p σ Nt(c) ( σ -1 s,a (•)|c) -p(•|s, a) 1 b W Nt(c) δ 2C .
The previous construction is justified by the following non-expansive property of the ordering operator, as it ensures the Weissman concentration inequality also applies to the ordered empirical distribution. This also ensures that Theorem 1 also applies to C-UCRL2(C) with same regret bound.

Lemma 2 (Non-expansive ordering) Let p ∈ P(S) with profile map σ. Let p n be its empirical version built from n samples, with profile map σ n . Then (see appendix G),

p n (σ n (•)) -p(σ(•)) 1 p n (σ(•)) -p(σ(•)) 1 .

Unknown classes: clustering

We finally address the most challenging situation when both the classes and profile mappings are unknown to the learner. To this end, we first introduce an optimistic clustering procedure that groups distributions based on statistical tests and is provably consistent. Then, we introduce a natural modification of C-UCRL2(C) that uses a clustering algorithm to estimate the classes; We call this algorithm simply C-UCRL2, in contrast with C-UCRL2(C) which knows the classes, and C-UCRL2(C, σ) that also knows the profile mappings.

Since the non-trivial question is whether a benefit can be observed in practice, we illustrate this strategy on numerical experiments (Figure 2 and Section 7). They show that this strategy is promising as it does outperform UCRL2. But also that it suffers a much higher regret than its oracle counterpart, and is thus unable to leverage the unknown structure of the MDP. We realize this does not come from the clustering part that is sound, but rather from the episodes that stop too late. We thus introduce in Section 6 a key modification of the stopping rule, replacing the original heuristics from UCRL2 with hypothesis testing. This considerably improves its behavior on several illustrative examples, and also benefits the vanilla UCRL2 strategy.

Estimated clusters

The clustering algorithm is inspired from [START_REF] Khaleghi | Online clustering of processes[END_REF] and does not require to know the number of clusters in advance. This approach provides sound estimations by using tight concentration bounds from Lemma 1. Let J = {1, . . . , J} be an indexation of S × A, where J = SA. If index j corresponds to the pair (s, a), we write N (j) for N t (s, a) and introduce q(•|j) = p σ Nt(s,a) ( σ s,a (•)|s, a). We extend these notations to sets c ⊂ J with N (c) = j∈c N (j) and q(

•|c) = j∈c N (j)q(•|j) N (c)
. Now, starting from the trivial partition of J into singletons C 0 = {1}, . . . , {J} , Algorithm 3 builds a coarser partition, by iteratively merging sets of the partitions. Two sets (clusters) are merged if and only if they are statistically close. For a given partition C of J and c ∈ C, we define the statistically closest set c 0 ∈ C from c (when it exists) as:

Near(c, C) = argmin d(c, c 0 ) : c 0 ∈ C \ {c} s.t.d(c, c 0 ) 0 and ∀j ∈ c, j 0 ∈ c 0 d(j, j 0 ) 0 ,
where we introduced the penalized dissimilarities with the bound ε

C (n) = b W n ( δ 2|C| ) d(c, c 0 ) = q(•|c)-q(•|c 0 ) 1 -ε C (N (c))-ε C (N (c 0 )), d(j, j 0 ) = q(•|j)-q(•|j 0 ) 1 -ε J (N (j))-ε J (N (j 0 )) .
The clustering algorithm then proceeds as follows: From C 0 , the sets c ∈ C 0 are ordered in decreasing order of N (c), so as to promote sets with tightest confidence intervals. Then, starting from c with largest N (c), it finds c = Near(c, C 0 ) and merge it with c, thus creating the new cluster c ∪ c in the novel partition C 1 , and removing c and c from C 0 . The algorithm continues this procedure with the next set in C 0 , until exhaustion, thus producing a novel partition C 1 of J . The algorithm iterates this refinement process until iteration i when C i+1 = C i (convergence). It finally outputs at time t k the clustering C t k def = C i built from all the observations for episode k. At each iteration, either two or more clusters are grouped or the algorithm stops. Thus, it takes at most |J | -1 = SA -1 steps for the algorithm to converge. The clustering algorithm is presented in Algorithm 3 and further details about merging and convergence are provided in appendix H. Remark 7 (Optimistic clustering) Algorithm 3 thus produces a partition C t of J that clusters the distributions whose grouping satisfies the confidence bounds. As a result, when N (s, a) is small for all pairs, all distributions tend to be grouped; non-similar state-action pair are then separated only when more evidence is collected. The correctness of the clustering algorithm is ensured under the following required assumption: Assumption 1 (Separation between classes) There exists some

∆ > 0 such that ∀c = c ∈ C ∀(s, a) ∈ c, (s , a ) ∈ c , p(σ s,a (•|s, a)) -p(σ s ,a (•|s , a )) 1 ∆ . Lemma 3 Under assumption 1, provided that min s,a N t (s, a) > f -1 (∆), where f : n → 2b W n ( δ SA
) the clustering algorithm outputs the correct partition C of state-action pairs with high probability.

Having introduced a clustering mechanism to find classes, the rest of the procedure is similar to C-UCRL2(C) with a modified set of plausible MDPs (details in Algorithm 2 and Appendix D):

M t (C t ) = (S, A, p, ν) : p ∈ Pw(C t ), ∀c ∈ C t , (s, a) ∈ c, p σ Nt(c) ( σ -1 s,a (•)|c) -p(•|s, a) 1 b W Nt(c) δ 2|C t | ,
and a modified stopping condition coming from the fact we are using concentration bounds both for the classes and for the pairs when building an estimated clustering (and thus M t (C t )): Remark 8 Contrary to M t (C), this set is not guaranteed to be optimistic due to the fact C t may differ from C. However, it provides a computationally cheap way to build a set of MDPs, compared to a more complex algorithm that would consider all plausible partitions C.

t k+1 = min t > t k ; ∃c ∈ C k : n t k :t (c) max{N t k (c), 1}or ∃s, a : n t k :t (s, a) max{N t k (s, a), 1} .
Figure 2 reveals that the clustering algorithm is improving over UCRL2, but is little able to handle unknown classes. One possible cause is that M t (C t ) may is not guarantee to contain M with high probability. However, extending M t (C t ) to handle all plausible clustering as well seems computationally heavy. Also, we observe numerically that the classes are correctly estimated. We thus call for another explanation.

A sound and effective stopping criterion using hypothesis testing

In this section, we revisit the criterion used to stop an episode in UCRL2.

A novel stopping criteria: inconsistency checking Since the plausible MDPs of UCRL2 algorithm are defined based on confidence intervals, the initial heuristic idea that guides the stopping time is to recompute a policy when these bounds have changed a lot. In other words, when number of observations is doubled for at least one state-action pair. However, we suggest an alternative view, which is the second main contribution of this paper: since the optimistic policy in episode k corresponds to an optimistic MDP M + t = (S, A, p + t , ν + t ) built at time t k it is natural to check whether this optimistic MDP is still consistent with the observations at subsequent time steps t > t k , and to stop when this is no longer the case. Thus, should we be able to detect the inconsistency of empirical estimation and the optimistic one, we would be able to detect this phenomenon sooner and update the policy instead of waiting for a long time. We actually observe that the episodes in C-UCRL2 last much longer even after novel observations show clear inconsistency of M + t , which suggests this is the main reason for the observed regret. A closer look at Extended Value Iteration A close look at Extended Value Iteration from [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] reveals that it identifies a specific "optimistic" state s + with maximal optimistic value. This state is then used in order to build the optimistic transition model p + (•|s, a), by putting maximal mass compatible with the empirical observations to transit to s + . In grid-world MDPs, this often means that p + puts a large positive mass for transiting to a state s + from every (s, a), even when it is not reachable in one step from (s, a). This suggests detecting inconsistency of the optimistic model by looking at such specific transitions. Modified stopping criterion Formally, we make use of concentration inequalities for a single entry p(s |s, a), and check if p + t k is compatible with the empirical transition at any time t > t k , until the test fails. More precisely, for any pair s, a and s , it would make sense to use the test:

|p Nt(s,a) (s |s, a) -p + t k (s |s, a)| (1 + ε)b H Nt(s,a) δ S 2 A ,
where ε > 0 is a small margin. Indeed when ε = 0 and p + t k = p, the previous inequality is valid uniformly over all t, s, a, s with probability higher than 1 -δ. Considering ε > 0 allows to handle the case when p + t k differs a little from p. Further grouping the probabilities to transit to a target state s on all pairs enables to get some refinement: For any s ∈ S,g ⊂ S × A, and state-transition function q, we define the notation q(s |g) = s,a∈g q(s |s, a). We then define g t k (s 0 ) = {s, a :

s 0 ∈ argmax s q(s |s, a)}, for q = p + t k . Since p + t k ∈ Pw(C t k ), the set G t k = {g t k (s 0 ) : s 0 ∈ S}
p + t k (s tg |g)| (1 + ε)|g|b H Nt(g) δ SC , (1)
leading to the following modified stopping time t k+1 = min{t > t k : (1) fails}. We show in appendix I that a positive ε ensures that episodes for which p + t k is close to p, do not stop too early. Thus ensures a form of doubling stopping criterion (as for UCRL2) while the performed test enables an episode to terminate when an obvious mismatch between p + t k and p is detected. We use the value ε = 1 in the experiments, which is further discussed in appendix I. Remark 9 This novel stopping criterion is defined for an optimistic model p + t built at time t = t k . Thus, it applies without further modification to

p + t ∈ M t , p + t ∈ M t (C) or p + t ∈ M t (C t )
and all algorithms including UCRL2 can be compared by replacing "doubling" stopping criterion.

Numerical experiments: Empirical regret reduction in the agnostic case

We report in Figure 2 (see also appendix C) the outcome of running the algorithms on a few tasks (each averaged over 10 experiments). We consider: a) Four-Room MDP on a 5 × 5 grid world with four doors, and a total of SA = 100 pairs. and b) Two-Room MDP (wall in the middle) that is a 7 × 7 grid world, with one door. None of the algorithms is aware of the specific fact that the MDPs are grid-world, thus, instead of using support of K = 4, they all assume distributions with support S. We compare the UCRL2 algorithm using Laplace bounds with the semi-oracles C-UCRL2(C, σ), C-UCRL2(C) and the agnostic strategy C-UCRL2. Then, for each of these 4 algorithms, we consider their variants using the modified stopping criterion from section 6; they are denoted with suffix "replan". Discussion We note that the agnostic C-UCRL2-replan is outperforming UCRL2 by a huge margin and is also outperforming UCRL2-replan. This clearly indicates that using the notion of similarity between state-action pairs can benefit learning even in the fully agnostic case, which answers our initial question in a non-trivial way. In the two room environment (Figure 2), the algorithm has learned after about 2500 steps, given that there are about 50 states and 4 actions, this corresponds to about 12.5 observations per state-action pair on average, while UCRL2 is still suffering a linear regret event after 20000 steps (about 100 observations per state-action pair). UCRL2 indeed requires a much larger time horizon to converge on such experiments, of order 10 5 (see Appendix C). The improvement is achieved while using the same tools as UCRL2, which opens interesting area of research, in view of the KL-UCRL (see [START_REF] Filippi | Optimism in reinforcement learning and Kullback-Leibler divergence[END_REF]) and Thompson-Sampling alternatives.

Conclusion

While we believe it is more convincing to provide empirical evidence that one can leverage the structure of an MDP in the fully agnostic case to benefit regret minimization, our empirical findings obviously call for a theoretical regret analysis. We leave this intricate, but somehow secondary question for an extended version of this already dense article. We introduced a state-action pair similarity, borrowed from optimal transport, in a reinforcement learning setup. This similarity is based on discrete optimal transport between distributions and produces large equivalence classes, thus effectively reducing the number of parameters to be learned. First, we have shown on numerical experiments and in theory that taking advantage of this structure can massively reduce the cumulative regret of a simple UCRL2 algorithm. In the challenging scenario when the partition is unknown, a non-trivial question is whether such an improvement can still be observed. Interestingly, our findings have led us to consider a second important idea: changing the stopping criterion of UCRL2 to take into account the possible mismatch between the optimistic environment and the observed one. This simple idea is illustrated on numerical experiments, where it proves to be massively beneficial, reducing the regret by several orders of magnitude. Whether this improvement can be seen on regret bounds (whose constants are typically loose in such setups) is an intriguing open question. While the main goal of the paper is to illustrate the benefit of these two powerful ideas, we have provided several theoretical results regarding the soundness of the approach, thus paving the way towards a sharper understanding of regret guarantees in discrete Reinforcement Learning.

A Other examples of MDPs

We consider a grid-world MDP with four actions a ∈ {u, d, l, r}. Playing action a = u moves the current state up with probability 0.8, does not change the current state with probability 0.1, and moves left or right with same probability 0.05 (it never goes down). When the resulting state is a wall, the distribution is modified: the probability mass is reported on the current state. Other actions have similar effect. Finally, the goal-state is put in the bottom-right corner of the MDP.

We now illustrate the scalability of the state-action pair similarity notion, of Definition 1 involving permutations. We show below four examples of grid-worlds defined according to the above scheme, with different number of state-action pairs. Grid-world Figure 3

B Link with optimal transport

We now draw a connection between Definition 1 and optimal transport. Let us consider two discrete distributions p and q on S of size S. Let σ : {1, . . . , S} → S be such that p(σ(1)) . . . p(σ(S)).

Likewise, we consider a permutation τ such that q(τ (1)) . . . q(τ (K)), and define y i = τ (i).

Note that this can also be seen as considering the different level sets of the discrete distributions, a key notion when considering optimal transport.

An optimal transportation plan Γ between p • σ and q • τ for a cost c minimizes over

Γ S i,j=1
c(i, j)Γ(i, j) where

S j=1 Γ(i, j) = p • σ(i) and S i=1 Γ(i, j) = q • τ (j) .
When c(i, j) = I{i = j}, the minimal value coincides with the total variation cost between p • σ and q • τ , that is p • σ -q • τ 1 /2. Introducing s = σ(i) and s = τ (j) explicitly, the optimal transportation problem now rewrites

s,s ∈S c(σ -1 (s), τ -1 (s ))Γ(σ -1 (s), τ -1 (s ))
where

s ∈S Γ(σ -1 (s), τ -1 (s )) = p(s) and s∈S Γ(σ -1 (s), τ -1 (s )) = q(s ) ,
which corresponds to a cost C(s, s ) = I{σ -1 (s) = τ -1 (s )} defined on S.

C Further experiments

k : ∀c ∈ C : set ν k (c) := 0and compute N t k (c), p σ N k (c) (.|c), µ N k (c) (c
G k N ← C k .Centers r p G k N ← C k .Centers p N k (c) := #{τ < t k : s τ = s, a τ = a,
G C .Elements c that is, p+ (.|c) -p G k N k (.|c) 1 b W Nt(s,a) (δ) |r(c) -r G k (c)| b W n (δ)

E Time-uniform concentration inequalities

Theorem 2 (Hoeffding-Laplace concentration) Let µ n be the empirical mean built from n i.i.d. observations from a [0, 1]-bounded distribution with mean µ. For any random stopping time τ with respect to the filtration of the past observations,

P |µ τ -µ| (1+ 1 τ ) log(2 √ τ +1/δ) 2τ δ .
Corollary 1 (Weissman-Laplace concentration) For any random stopping time τ with respect to the filtration of the past observations, and any discrete distribution p on S with support of size K |S|,

P p τ -p 1 2(1+ 1 τ ) log √ τ +1 2 K -2 δ τ δ .

Proof of Corollary 1:

For discrete measures, P p τ -p 1 ε

B⊂S P p τ (B) -p(B) 1 2 ε . Algorithm 3 Confident Clustering 1: C ← [p (1) , . . . , p (k) ] {Each sample is it's own cluster center} 2: N ← [n 1 , . . . , n k ] 3: size ← [1, . . . ,
C k ← C k * size k +Ci * sizei size k +sizei 3: N k ← N k + N i 4: size k ← size i + size k 5: size ← size -size i 6: N ← N -N i 7: C ← C -{C i }
Algorithm 5 Find Closest Cluster 1: Function Near(index, C):

2: k ← -1 3: dist min ← ∞ 4: for all i ∈ getIndex(C), i! = index do 5: dist = C i -C index 1 -ε Ci -ε C index 6:
if dist < 0 and dist < dist min and isValid(i, index) then 7:

dist min ← dist 8: k = i 9:
end if 10: end for 11: return k Algorithm 6 Checks both cluster points to have valid distant Function isValid(i, j) : samples i ← getSamples(i) {samples of i th cluster} samples j ← getSamples(j) for all s i ∈ samples i do for all s j ∈ samples j do if s i -s j 1 -ε i -ε j > 0 then Return False end if end for end for Return True Corollary 2 Let N t (s, a) be the number of observation of a state action pair (s, a) at time t. Then

P ∃t ∈ N, |µ Nt(s,a) (s, a) -µ(s, a)| (1+ 1 Nt(s,a) ) log(2 N t (s, a)+1/δ) N t (s, a) δ . P ∃t ∈ N, p Nt(s,a) (•|s, a)-p(•|s, a) 1 2(1+ 1 Nt(s,a) ) log N t (s, a)+1 2 K -2 δ N t (s, a) δ .
Proof of Corollary 2:

P ∃t : |µ Nt(s,a) (s, a) -µ(s, a)| (1+ 1 Nt(s,a) ) log(2 N t (s, a)+1/δ) N t (s, a) P ∃t, ∃n t : |µ n (s, a) -µ(s, a)| (1+ 1 n ) log(2 √ n+1/δ) n P ∃n ∈ N : |µ n (s, a) -µ(s, a)| (1+ 1 n ) log(2 √ n+1/δ) n ,
Now, we recognize a uniform concentration inequality for the observations of the pair (s, a), which can be controlled by introducing the variable

τ = min n : |µ n (s, a) -µ(s, a)| (1+ 1 n ) log(2 √ n+1/δ) n ,
which is a stopping time with respect to the observations generated by the pair (s, a).

F Effective regret analysis of C-UCRL2(C, σ)

The analysis is based on the analysis of UCRL2 given by [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF]. We are going to investigate "State-Aggregated UCRL2" by analyzing the regret of the algorithm. The effective regret naturally decomposes episode-wise

R(A, T ) = T t=1 g (s 1 ) - T t=1 µ(s t , a t ) = m(T ) k=1 s,a∈S×A t k+1 t=t k +1 I{s t = s, a t = a} ν k (s,a) g -µ(s, a) = m(T ) k=1 c∈C t k+1 t=t k +1 I{(s t , a t ) ∈ c} ν k (c) g -µ(c) = m(T ) k=1 ∆ k .
where we used that µ(s, a) has constant value µ(c) for all (s, a) ∈ c and introduced the effective regret in episode k

∆ k = c∈C ν k (c) g -µ(c) .
We say an episode is good if M ∈ M t k (that is, the set of plausible MDPs contains the true model) and bad otherwise.

Control of the regret due to bad episodes: M / ∈ M t k Due to using time-uniform instead of time-instantaneous confidence bounds, we can show that with high probability, all episodes are good for all horizons. More precisely, with probability higher than 1 -δ, for all T , bad episodes do not contribute to the regret:

m(T ) k=1 ∆ k I{M / ∈ M t k } = 0 ,
where m(T ) is the number of episodes up to time T .

Control of the regret due to good episodes: M ∈ M t k

We closely follow [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] and decompose the regret to control the transition and reward functions. At a high level, the only modifications that we do are 1) to use a time-uniform bound to control the martingale difference sequence that appears in the proof, using the following result:

Lemma 4 (Time-uniform Azuma Hoeffding) For any martingale difference sequence (X t ) t bounded by D (that is, |X t | D for all t) it comes, by application of time-uniform Laplace concentration inequality for bounded variables,

P ∃T ∈ N, T t=1 X t D 2(T + 1) log( √ T + 1/δ) δ .
2) to control the number of episodes differently, due to the use of the partition C

Lemma 5 (Number of episodes) The number of episodes of C-UCRL2(C, σ) up to step T C, denoted by m(T) is upper bounded by:

m(T ) C log 2 ( 8T C )
Proof of lemma 5:

Having defined N T and ν k as the total number of state-action observations, up to step T and in episode k respectively, there is a state-action class(c) in each episode k < m with ν k (c) = N t k (c).

Let K(c) be the number of episodes with

ν k (c) = N t k (c) and N t k (c) > 0 for all c. It is worth mentioning that if N t k (c) > 0 and ν k (c) = N t k (c), N t k+1 (c) = 2N t k (c), therefore: N (c) = m(T ) k=1 ν k (c) 1 + k:ν k (c)=Nt k (c) N t k (c) 1 + K(c) i=1 2 i-1 = 2 K(c) (2) If N (c) = 0, K(c) = 0, therefore, N (c) 2 K(c)
-1 for all pair classes. Thus,

T = c∈C N (c) c∈C 2 K(c) -1 (3)
On the other hand, an episode has happened when either

N t k (c) = 0 or N t k (c) = ν k (c). Therefore, m 1 + C + c∈C K(c) and consequently, c∈C K(c) m -1 -C. As a result: c∈C 2 K(c) C2 c∈C K(c) C C2 m-1 C -1 (4)
Using the last two equations:

T C 2 m-1 C -1 -1 (5)
Therefore,

m 1 + 2C + C log 2 ( T C ) 3C + C log 2 ( T C ) C log 2 ( 8T C ) (6)
And the lemma is proved.

Details Since M ∈ M t k by assumption and by choosing π + t k and M + t k by following the algorithm, we get that g k def = g

M + t k π + t k g -1 √ t k
. Thus, it can be said that:

∆ k c∈C ν k (c) g -µ(c) c∈C ν k (c) g k -µ(c) + c∈C ν k (c) √ t k (7)
Besides, according to the proof of extended value iteration in UCRL2we also have, for the output value at iteration i max

s u i (s) -min s u i (s) D ( 8
)
where D is the diameter of the MDP. Moreover, when the convergence criterion of extended-value iteration holds we have:

|u i+1 (s) -u i (s) -g k | 1 √ t k ∀s ∈ S (9)
where g k is the average reward of the policy π + t k chosen on the optimistic MDP M + t k . Using Bellman operator on the optimistic MDP:

u i+1 (s) = µ + t k (s, π + t k (s)) + s p + t k (s |s, π + t k (s)).u i (s )
which can be written as:

u i+1 (s) = µ + t k (c s,π + t k (s) ) + s p + t k (s |c s,π + t k (s) ).u i (s )
where c s,a ∈ C s.t. ∃c ∈ C : (s, a) ∈ c. Employing the above equation alongside with 9 leads to:

| g k -µ + t k (c s,π + t k (s) ) - s p + t k (s |c s,π + t k (s) ).u i (s ) -u i (s) | 1 √ t k
By defining the column vector of g k = (g k (s)) (s) ) we can rewrite the above equation as:

| g k -rk s -( Pk -I)u i s | 1 √ t k
Therefore, equation 7 can be rewritten as:

∆ k c∈C ν k (c) g k -µ(c) + c∈C ν k (c) √ t k = c∈C ν k (c) g k -µ + t k (c) + c∈C ν k (c) µ + t k (c) -µ(c) + c∈C ν k (c) √ t k υ k ( Pk -I)u i + c∈C ν k (c) µ + t k (c) -µ(c) + 2 c∈C ν k (c) √ t k
Since each row of Pk sums up to one, we can add a constant to u i and still have the same equation. So, we are going to replace it with w k :

w k (s) := u i (s) - min s u i (s) + max s u i (s)
2 At this point we are going to bound the reward part using reward confidence bound. Knowing that

M ∈ M t k , then µ + t k (c) -µ(c) |µ + t k (c) -µ Nt k (c) (c)| + |µ Nt k (c) -µ(c)| can be bounded by 2. Therefore, ∆ k υ Ck ( Pk -I)w k + 2 c∈C ν k (c)b H Nt k (c) ( δ 2C ) + 2 c∈C ν k (c) √ t k υ Ck ( Pk -I)w k + 2 c∈C ν k (c) (1+ 1 Nt k (c) ) log(4C N t k (c)+1/δ) 2N t k (c) + 2 c∈C ν k (c) √ t k Since max{1, N t k (c)} t k T , ∆ k υ Ck ( Pk -I)w k + 4 ln( 2C √ T δ ) + 2 c∈C ν k (c) max{1, N t k (c)} (10)
Afterwards we have to bound the first part of the above equation, υ k ( Pk -I)w k , which is going to be done by using the confidence bound on the transition probability distribution introduced in 2. Having defined P k := p(s |c s,π + t k (s) ) s,s :

υ k ( Pk -I)w k = υ k ( Pk -P k + P k -I)w k = υ k ( Pk -P k )w k + υ k (P k -I)w k (11)
Assuming that M ∈ M t k while knowing that w k D 2 and taking advantage from holder inequality and 2:

υ k ( Pk -P k )w k = s s ν k (c s,π + t k (s) ) p + t k (s |c s,π + t k (s) ) -p(s |c s,π + t k (s) ) w k (s ) s ν k (c s,π + t k (s) ) p + t k (.|c s,π + t k (s) ) -p(.|c s,π + t k (s) ) 1 w k ∞ s ν k (c s,π + t k (s) )2b W Nt k (c s,π + t k (s) ) δ 2C D 2 s ν k (c s,π + t k (s) )D 2(1+ 1 Nt k (c s,π + t k (s) ) ) log 2C N t k (c s,π + t k (s) )+1 2 S -2 δ max(1, N t k (c s,π + t k (s) )) D 4 ln 2C √ T + 1(2 |S| -2) δ c ν k (c) max{1, N t k (c)} (12)
and to bound the second term in equation 11, we are going to use lemma 4 and lemma 5. Let us define X t := (p(.|c t ) -e st+1 )w k (t) M∈Mt k ∀t = 1, . . . , T . For any k with M ∈ M t k , we have that:

υ k (P k -I)w k = t k+1 -1 t=t k (p(.|c t ) -e st )w k = t k+1 -1 t=t k p(.|c t ) -e st+1 + e st+1 -e st w k t k+1 -1 t=t k X t + w k (s t+1 ) -w k (s t ) t k+1 -1 t=t k X t + D Knowing that |w k (t)| ∞ = D 2 and using holder inequality, |X t | |p(.|c t ) -e st+1 | 1 D 2 |p(.|c t )| 1 + |e st+1 | 1 D 2 = D.
So, X t is bounded by D and also E{X t |s 1 , a 1 , . . . , s t , a t } = 0, so that X t is a sequence of martingale differences. Therefore by using lemma 4 we get:

P(∃T : T t=1 X t D 2(T + 1) log( √ T + 1/δ) εp 2 δ .
Using lemma 5, we know that m C log 2 8T C . By summing over all episodes we get:

m(T ) k=1 υ k (P k -I)w k M∈Mt k T t=1 X t + m(T ) ε p2 + m(T )D ε p2 + DC log 2 ( 8T C ) (13)
with probability 1 -2δ.

Final control Using a union bound over the event that M is plausible at any time, and over the control of the martingale difference sequence (X t ) t appearing in the control of good episodes, we deduce that the regret is controlled with probability higher than 1 -2δ, uniformly over all T ∈ N.

More precisely, using 10, 11, 12 and 13 and summing over all episodes:

m k=1 ∆ k M∈Mt k m k=1 υ k ( Pk -P k )w k M∈Mt k + m k=1 υ k (P k -I)w k M∈Mt k + m k=1 4 ln( 2C √ T + 1 δ ) + 2 c∈C ν k (c) max{1, N t k (c)} D 4 ln 2C √ T + 1(2 |S| -2) δ + 4 ln( 2C √ T + 1 δ ) + 2 m k=1 c ν k (c) max{1, N t k (c)} +D 2(T + 1) log( √ T + 1/δ) + DC log 2 8T C (14)
To bound the above equation, we are going to introduce the below lemma:

Lemma 6 For any sequence of numbers z 1 , z 2 , . . . , z n with 0

z k Z k-1 := max{1, k-1 i=1 z i } n k=1 z k Z k-1 √ 2 + 1 Z n (15)
which is proved in [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF]. Knowing that N T (c) := k ν k (c), c N T (c) = T and N t k (c) = i<k ν i (c) and using the above lemma we get:

c∈C m k=1 ν k (c) max{1, N t k (c)} c∈C √ 2 + 1 N T (c)
On the other hand, using Jensen's inequality we get:

√ 2 + 1 c∈C N T (c) √ 2 + 1 C c∈C N T (c) C √ 2 + 1 √ CT Therefore, c∈C m k=1 ν k (c) max{1, N t k (c)} √ 2 + 1 √ CT
And by using the above result in equation 14, we get:

m(T ) k=1 ∆ k M∈Mt k D 2(T + 1) log( √ T + 1/δ) + DC log 2 ( 8T C ) + D 4 ln 2C √ T + 1(2 |S| -2) δ + 4 ln( 2C √ T + 1 δ ) + 2 √ 2 + 1 √ CT (16)
with probability of at least 1 -δ -δ.

Finally, the regret of C-UCRL2(C, σ) is controlled on an event of probability higher than 1 -δ, uniformly over all time T , by

R(C-UCRL2(C, σ), T ) D 4 ln 2C √ T + 1(2 |S| -2) δ + 4 ln( 2C √ T + 1 δ ) + 2 √ 2 + 1 √ CT +D 2(T + 1) log( √ T + 1/δ) + DC log 2 ( 8T C
) .

We conclude by polishing the bound to highlight the main terms of the regret:

R(C-UCRL2(C, σ), T ) [6( √ 2 + 1) + √ 2 + 1]D CT S ln(C √ T /δ) 17D CT S ln(C √ T /δ) .
The bound in the main body of the paper removes the 4 ln( 2C √ T +1 δ

) when assuming the mean rewards are known.

Initially, each sample is considered to be the center of a cluster and we have k clusters at the beginning. We sort the samples according to their corresponding value in N so as to guarantee that samples with higher confident are chosen sooner. Gaining advantage from the provided bounds, we search for the closest cluster assuring not only that the cluster centers are close enough, but also that all the cluster pairs satisfy 21 inequality. Thus, the clusters would be grouped when we have enough evidence to merge and would be left unchanged otherwise. The procedure is continued till the algorithm converges meaning that no cluster center alters. More exact procedure of the algorithm is demonstrated in 3.

Since the used samples for clustering are empirical probability distributions and there exists a deviation between empirical probability distributions and their corresponding true distribution, the measures are not exact and in order to bound error we are going to use Weissman concentration inequality measures to bound error. To find whether two samples should be grouped or not, we have to find the distance of their probability distributions. So,

p(i) -p(j) 1 p (i) -p (j) 1 + p(i) -p (i) 1 + p(j) -p (j) 1 p (i) -p (j)
1 + ε i + ε j In case that two samples have the same probability distribution, the difference of their true probability distribution is zero:

p(i) -p(j) 1 -ε i -ε j 0 (
17) Using Laplace inequality and knowing that it should hold for all state-action pairs of a cluster i, we can write: ∀(s, a) ∈ C i :

P(||p(.|s, a) -p(.|s, a)|| 1 ε) δ 2k (18)
Moreover, we also have to test the cluster centers to satisfy time uniform laplace inequality. Knowing that the number of clusters either reduces at least by one at each step or the clustering algorithm is converged, therefore the number of clusters for iteration th step would be at most "k -iteration + 1". So, ∀C i ∈ C :

P(||p(.|C i ) -p(.|C i )|| 1 ε) δ 2(k -iteration + 1) (19)
Therefore, using the above equation alongside with union bounds:

P(∀(s, a) ∈ C i : ||p(.|s, a) -p(.|s, a)|| 1 ε) +P(∀C i ∈ C : ||p(.|C i ) -p(.|C i )|| 1 ε) = (s,
+ Ci∈C P(||p(.|C i ) -p(.|C i )|| 1 ε) (s,a)∈Ci δ 2k + Ci∈C δ 2(k -iteration + 1) (s,a)∈Ci δ 2k + Ci∈C δ 2(k -iteration + 1) = |C i | 2k δ + |C| 2(k -iteration + 1) δ k 2k δ + k -iteration + 1 2(k -iteration + 1) δ = δ (20)
The last step of the above equation is due to the fact that C i and number of elements in C i are both a random variables and we do not know their exact value. So, we can replace them by the worst case scenario. However, this bound is still not accurate and can be improved knowing the fact that the worst case for both parts can not happen simultaneously. For instance, when a cluster contains k elements, the number of clusters will not be k -iteration and would be 1. Consequently, we can say that i and j should be grouped with high probability if inequality 17 is satisfied having used 18 to compute ε i and ε j :

ε i = 2 n i ln 2 |χ| -2 δ 2k (21)
where T is the maximum possible number of samples for a sequence. Following the same procedure, we can compare the distance of two clusters, C i and C j , using:

ε Ci = 2 N Ci ln 2 |χ| -2 δ 2(k-iteration+1) (22)
where N Ci = j∈Ci n j is the number of samples included in cluster i and iteration is the number of current iteration of clustering algorithm.

Moreover, following the same procedure for the reward part we would reach:

||r (i) -r(j) || 1 -ε r i -ε r j 0 (23)
And taking advantage from time uniform inequality for all state-action pairs we can find:

P ∀(s, a) ∈ C i : r(s, a) -r(s, a)|| 1 ε r i δ r 2k (24)
Considering the same condition as for probability distributions:

P(∀C i ∈ C : ||r(C i ) -r(C i )|| 1 ε r i ) δ 2(k -iteration + 1) (25)
Consequently, we can find

ε r i = 1 2n i ln 2k δ (26)
and

ε r Ci = 1 2N Ci ln 2(k -iteration + 1) δ (27)
and the idea is complete.

It is worth mentioning that this approach is only suitable when different class distributions are not overlapping which is the case of our reinforcement learning problem since in case of overlapping, they are having the same behavior and should be grouped consequently.

I A modified stopping criterion

The goal of the statistical test is to detect early enough a possible mismatch between the optimistic MDP M + t k identified at time t k and the correct MDP M. For a state s 0 ∈ S and a group of state-action pairs g ⊂ S × A and any state-transition distribution q, we denote by q(s 0 |g) = s,a∈g q(s 0 |s, a) the probability of reaching s 0 from any of the pair s, a ∈ g. Likewise, we denote N (g) = s,a N (s, a) for a counter N .

Proof :

Let g t k (s 0 ) = {s, a : s 0 ∈ argmax s q(s |s, a)}, for q = p + t k . Then, G δ SC .

In particular, on an event of high probability, episode k is bad only if

(2 + ε)b H Nt(gt) δ SC G gt ,
that is if N t (g t ) is small at the last time before the episode stops; typically N t (g t ) = Õ (2+ε) 2 Gg t . This ensures that we stop the episode early enough and recompute a better model in that case.

Good episodes Let us consider now a good episode such that |p + t k (s 0 |g) -p(s 0 |g)| |g|G g for all s 0 , g. We want to show that such an episode is not stopped too early. Indeed in that case, we have on an event of high probability, β 2 N t k (g) for some g.

|p
In particular, the specific value ε = √ 2 implements a criterion similar to the doubling stopping criterion of UCRL2 for good episodes.

On the other, an episode k is bad only if

(2 + ε)b H Nt(gt) δ SC βb H Nt k (gt)
δ SC thus typically if (2+ε) 2 β 2 N t k (g) N t (g) for all g.

Thus, we deduce that a "good" episode stops when N t (g)

ε 2
β 2 N t k (g) for some g, while a "bad" episode stops when N t (g) (2+ε) 2 β 2 N t k (g) for some g. For L1 norm, we can further show that for g ∈ G t k it holds

|p + t k (s 0 |g) -p(s 0 |g)| p + t k (•|g) -p(•|g) 1 2|g|b W Nt k (g) δ SC
This leads to the natural choice to rule out all bad episodes with high probability:

G = 2b W Nt k (g) δ SC b H Nt k (g) δ SC b H Nt k (g) δ SC .
This in turns suggests to choose

ε = 2 √ 2b W Nt k (g) δ SC b H Nt k (g) δ SC
.

Number of episodes

To conclude, it thus remains to compute a bound on the number of episodes and ensures that is stays logarithmic in the time horizon. This is done similarly to the count of episodes in UCRL2, since in each episode at least one group g gets a total number of observations multiplied by a constant factor.

Figure 1 :

 1 Figure 1: A grid-world MDP showing similar transitions from state-action pairs (6,up) and (8,right).

Figure 2 :

 2 Figure 2: Regret as a function of time in an illustrative 4-room MDP with 25 states (left) and 2-room with 49 states (right). Note that UCRL2 gets sub-linear regret only after 1.2 and 2.5 × 10 5 time steps.

  ∀s, s ∈ S i , ∀a ∈ A, µ(s, a) = µ(s , a) and ∀j, s ∈Sj p(s |s, a) = s ∈Sj p(s |s , a) .This readily prevents any two states s, s such that p(•|s, a) and p(•|s , a) have disjoint support from being in the same set S i . Thus, since in grid-world MDP where transitions are local, the number of pairs with disjoint support is (about linearly) increasing with S, this implies a potentially large number of classes for grid-worlds with many states. A similar criticism can be formulated for[START_REF] Anand | Asap-uct: Abstraction of state-action pairs in uct[END_REF], even though it considers sets of state-action instead of states only, thus slightly reducing the total number of classes.

Figure 3 :

 3 Figure 3: Left: Two-room grid-world (left) with walls in black, and goal state in yellow. Right: equivalence classes for state-action pairs (one color per class).

Figure 4 :

 4 Figure 4: Left: Four-room grid-world (left) with walls in black, and goal state in yellow. Right: equivalence classes for state-action pairs (one color per class).

Figure 5 :

 5 Figure 5: Left: A more complex grid-world (left) with walls in black, and goal state in yellow. Right: equivalence classes for state-action pairs (one color per class).

Figure 6 :

 6 Figure 6: Left: A more complex grid-world (left) with walls in black, and goal state in yellow. Right: equivalence classes for state-action pairs (one color per class).

Figure 7 :

 7 Figure 7: Regret as a function of time for an ilustrative for-room MDP, (standard, and loglog plot)

  (s, a) ∈ c} Compute Policy: Let M k be the set of all MDPs with states and actions as in M, and with transition probabilities p+ (.|c) close to p G k N k (.|c) and rewards r+ (c) ∈ [0, 1] close to r G k N k (c), where ∀(s, a)∃c ∈ C k .Centers : (s, a) ∈

  a)∈Ci P(||p(.|s, a) -p(.|s, a)|| 1 ε)

  A(s t , ({s t , a t , r t }) t <t ) and s 1 is the initial state. Hoeffding and Weissman inequality where ∨ represents max operator. Finally, UCRL2 does not recompute π + t at each time step. Instead, it proceeds in internal episodes k = 0, . . . and computes π + t only at the starting time t k of each episode, defined as t 1 = 1 and for all k > 1, t k = min t > t k-1 ; ∃s, a : n t k :t (s, a) max{N t k (s, a), 1} ,

	We now briefly present and revisit the UCRL2 algorithm from Jaksch et al. (2010). At a high level,
	UCRL2 follows the optimistic principle by trying to compute π + t = argmax π:S→A	max{g M π : M ∈ M t }
	where g M π is the average-gain for policy π in MDP M, and M t = (S, A, p, ν) : ∀(s, a) ∈ S ×A, |µ Nt(s,a) (s, a) -μ(•|s, a)| bH t (s, a,	δ 2SA	)
	and	p Nt(s,a) (•|s, a) -p(•|s, a) 1	bW t (s, a,	δ 2SA	) .
	This is achieved approximately by an Extended Value Iteration (EVI) algorithm that builds a near-
	optimistic policy π + t and MDP M + t such that g π + M + t t	max π,M ∈Mt g M π -1 √ t .
	Here µ n (s, a) denotes the empirical mean built using n i.i.d. rewards from ν(s, a), p n (•|s, a) is the
	empirical distribution built using n i.i.d. observations from p(•|s, a), N t (s, a) is the total number of
	observations of state action pair (s, a) up to time t, and finally bH t and bW t are the two functions
	bH t (s, a, δ) =	3.5 log(t/δ) N t (s, a)∨1	, bW t (s, a, δ) =	7S log(t/Sδ) N t (s, a)∨1	,
	respectively based on a
						Jaksch et al. (2010),
	Definition 4 (Effective-regret) we define the effective-regret of any learning algorithm A after T
	steps as:		T		T
		R(A, T ) :=	g (s 1 ) -	µ(s t , a t ) where
			t=1		t=1
	a t = 1 The maximum is reached since there are only finitely many deterministic policies.
					3

  contains at most |C t k | different groups. Thus, assuming that |C t k | C holds with high probability for some known constant C, the following test is valid uniformly over all t, s , g ∈ G t k |p Nt(g) (s |g) -p + t k (s |g)| (1 + ε)|g|b H with high probability upon replacing p + t k with p and setting ε = 0. This justifies to test at time t + 1, after playing s t , a t , whether for the (random) state s tg def = argmax s,a p + t k (s t , a t ) and the (random) group g = g t k (s tg ) it holds |p Nt(g) (s tg |g) -

	Nt(g)	δ SC	,

  Ortner, Ronald. Adaptive aggregation for reinforcement learning in average reward markov decision processes. Annals of Operations Research, 208(1):321-336, 2013. Ortner, Ronald, Maillard, Odalric-Ambrym, and Ryabko, Daniil. Selecting near-optimal approximate state representations in reinforcement learning. In International Conference on Algorithmic Learning Theory, pp. 140-154. Springer, 2014.

	Peña, Victor H, Lai, Tze Leung, and Shao, Qi-Man. Self-normalized processes: Limit theory and
	Statistical Applications. Springer Science & Business Media, 2008.
	Puterman, Martin L. Markov decision processes: discrete stochastic dynamic programming. John
	Wiley & Sons, 2014.
	Ravindran, Balaraman and Barto, Andrew G. Approximate homomorphisms: A framework for
	non-exact minimization in markov decision processes. 2004.

  ). In Compute Policy: Apply Extended Value Iteration to M t k (C) to get compute (near) optimistic policy π + t k . In Execute policy π + t k : while ν k (c t ) < max{1, N t k (c t )} where c t ∈ C is the class containing (a t , s t ) do Choose a t = π + t k (s t ), Update c t , and ν k (c t ) := ν k (c t ) + 1 Obtain reward r t , observe next state s t+1

	t := t + 1
	end while
	Algorithm 2 Modified steps for Unknown Class & Mapping C-UCRL2
	Find Similarity Classes and update:
	p

k ← σ • p k {Reorder all probability distributions according to their permutation function} C k ← clustering p k {An entity with all clustering information} r

  1] {k-element array of one} 4: Changed ← True 5: while not Converged and Changed do

	6:	Changed ← False
	7:	Ordering ← argsort(N )
	8:	for all i ∈ Ordering do
	9:	if n i = 0 then
	10:	break
	11:	end if
	12:	k ← Near(i, C) {Find the closest cluster to i}
	13:	if k = -1 then
	14:	Continue
	15:	end if
	16:	merge(k, i, C, N, size)
	17:	Changed ← True
	18:	end for
	19: end while
	Algorithm 4 Combines two cluster centers

1: Function merge(k, i, C, N, size): 2:

  s , rk := µ + t k (c s,π +

	p + t k (s |c s,π + t k	(s) ) s,s and υ k := ν k (c s,π + t k	t k	(s) ) s for π + t k policy, Pk :=

  t k = {g t k (s 0 ) : s 0 ∈ S} contains at most |C t k | different groups. At each time t + 1, after playing s t , a t , the test checks whether for the (random) state s tg def = argmax s,a p + t k (s t , a t ) and the (random) group g = g t k (s tg ) it holds |p Nt(g) (s tg |g) -p + t k (s tg |g)| (1 + ε)|g|b H We say episode k is good if there exists some (s 0 , g) such that |p + t k (s 0 |g) -p(s 0 |g)| |g|G g , and bad otherwise, for G g to be defined later. Closeness of p t and p. We first show that for all t > t k for the (random) state st def = argmax s,a p + t k (s |s t , a t ) and the (random) group gt = g t k (s t ) ∈ G t k , P ∃k, t k : ∃t > t k |p(s t |g t ) -p Nt(gt) (s t |g t )| |g t |b H Indeed, considering all the possible states st ∈ S and groups gt ∈ G t k , we get P ∃k, t k : ∃t > t k |p(s t |g t ) -p Nt(gt) (s t |g t )| |g t |b H Nt(gt) δ SC P ∀k, t k : ∃s ∈ S, g ∈ G t k : |p(s |g) -p Nt(g) (s |g)| |g|b H Since there are at most C many groups and S states, we simply use a union-bound argument over them. We then conclude by application of a time-uniform concentration bound for bounded distribution P ∀k, t k : |p(s |g) -p Nt(g) (s |g)| |g|b H Bad episodes The test (1) is satisfied at the last time before the end of the episode (t = t k+1 -1). Thus, by closeness of p t and p at that time and definition of the test being passed, we deduce that at the last time before the end of the episode, |p + t k (s t |g t ) -p(s t |g t )| (2 + ε)|g t |b H

	Nt(g)	δ SC	,	(28)
		Nt(gt)	δ SC	δ .
					Nt(g)	δ SC	.
	Nt(g)	δ SC			δ SC	.
	Nt(gt)

  + t k (s t |g t ) -p Nt(gt) (s t |g t )| |g t |G gt + |g t |b H

				Nt(gt)	δ SC	.
	Thus, the episode does not stop unless
	G gt > εb H Nt(gt)	δ SC	.
	βb H Nt k (g)	δ SC	> εb H Nt(gt)

Tuning Let G g = βb H Nt k (g) δ SC

. This ensures that a good episode stops only when δ SC thus typically when N t (g)

ε 2

Preprint. Work in progress.

In all this paper, we consider K = S, that is, we have no prior information on the support.

G Ordered Weissman

Proof of Lemma 2:

Let us consider the case when a switch occurs between index 1 and 2, that is σ n (1) = σ(2) and σ n (2) = σ(1). In this situation, we thus have p(σ(1)) > p(σ(2)) but p(σ n (1)) p(σ n (2)). Then, we study i=1,2 |p(σ(i)) -p n (σ n (i))|.

First, we note that if p n (σ n (1)) < p(σ(1)) and p n (σ n (2)) < p(σ(2)), then

Likewise, the same equality occurs if p n (σ n (1)) > p(σ(1)) and p n (σ n (2)) > p(σ(2)).

Thus, proceeding iteratively for all switch that occurs, and decomposing the permutations σ, σ n into elementary switches, this shows that almost surely

H Clustering Guarantees

H.1 Problem Definition

Consider the problem of having k different sequences x (1) , x (2) , . . . , x (k) generated using k probability distributions Q (1) , Q (2) , . . . , Q (k) where all of them share the same |χ| alphabets and some of them may even have the same probability distribution. Therefore, one can say that they may have k different classes of probability distributions where k k. In other words:

n } are elements of x (1) which are drawn i.i.d. according to Q (1) . P x represents the empirical probability distribution of a sequence x 1 , x 2 , . . . , x n and obviously, n is the length of the sequence. Therefore, we define N = {n 1 , . . . , n k } to represent the number of sampling steps our k sequences have. More concretely, P x is a vector with size of the alphabet |χ| that gives the number of occurrences of each element divided by sequence length, i.e. P x (a) = N (a|x) n .

In our problem setting, we receive a sample from one of the k different groups at each step. However, neither the probability distributions(Q (i) s) nor the number of different classes(k ) is known. We are going to propose a clustering approach so as to find this k classes of probability distribution using the samples obtained from k initial distributions.

H.2 Confident Clustering (proof of Lemma 3)

Given {P x (1) , . . . , P x (k) } which would be called "samples" from now on and represented by p (1) , . . . , p (k) for simplicity. In this section, we are going to propose a clustering approach to group samples and find the k distinct classes of probability distribution. More concretely, we can say that for k k, ∀Q (i) ∈ {Q (1) , . . . , Q (k) }∃Q (j) ∈ {Q (1) , . . . , Q (k ) } s.t. Q (i) ∼ Q (j) . It is worth mentioning that we do not know the number of classes and probability distributions beforehand. We are provided with merely k different samples and we require to find an acceptable grouping in the last resort.