Maillard

Timothy A Mann
email: mann.timothy@gmail.com

Ronald Ortner
email: rortner@unileoben.ac.at

Shie Mannor

Active Roll-outs in MDP with Irreversible Dynamics Odalric-Ambrym

Keywords: Reinforcement learning, Regret analysis, Multi-chain, MDP, Recoverability

In Reinforcement Learning (RL), regret guarantees scaling with the square root of the time horizon have been shown to hold only for communicating Markov decision processes (MDPs) where any two states are connected. This essentially means that an algorithm can eventually recover from any mistake. However, real-world tasks usually include situations where taking a single "bad" action can permanently trap a learner in a suboptimal region of the state-space. Since it is provably impossible to achieve sub-linear regret in general multichain MDPs, we assume a weak mechanism that allows the learner to request additional information. Our main contribution is to address: (i) how much external information is needed, (ii) how and when to use it, and (iii) how much regret is incurred. We design an algorithm that minimizes requests for external information in the form of rollouts of a policy specified by the learner by actively requesting it only when needed. The algorithm provably achieves O( √ T ) active regret after T steps in a large class of multi-chain MDPs, by only requesting O(log(T )) rollout transitions. The superiority of our algorithm to standard algorithms such as R-Max and UCRL is demonstrated in experiments on some illustrative grid-world examples.

Introduction

In Reinforcement Learning (RL), an agent interacts with an environment by sequentially playing an action and then receiving an observation and a reward for that action. The goal of the agent is to maximize its accumulated reward, and the most popular model for representing RL problems is the Markov decision process (MDP) model.

In this paper, we consider an agent that interacts with a multi-chain MDP, in a single stream of observations-actions-rewards, with no reset. In a multi-chain MDP, there does not always exist a state-action path with positive probability between any two states. This is in stark contrast with the more common and restrictive assumption that the MDP is communicating (that is, between any two states, there always exist a finite path of positive probability that connects the two states). For illustration, we depict in Figure 1 an example of a communicating MDP, an example of a unichain MDP with one recurrent class, and an example of a multi-chain MDP with two recurrent classes. Note that without a special reset action that takes the learner back to an initial state, the learning problem is difficult. In fact, it is provably impossible to achieve sub-linear regret performance by only interacting with the environment and without prior information. This can be shown easily by looking at a so-called Heaven-or-Hell MDP depicted in Figure 2. In such an MDP, one action leads to an absorbing state giving reward 0 (Hell), and another action leads to an absorbing state giving reward 1 (Heaven). Without knowing which action leads to hell and which to heaven, an algorithm must incur linear regret in such MDPs (in a minimax sense). Thus, the only way to hope for sub-linear regret is to access an external source of information (in the sense that it does not result from an interaction between the learner and the MDP). We discuss later in the second next paragraph what type of external information does not trivialize the problem.

Motivation In this paper, we want to provide an answer to the open theoretical question: How to achieve near-optimal learning guarantees in this setting? Since learning without external information is not possible, the answer mainly deals with the external information used by the learner. That is, our contribution is three-fold, addressing:

(i) how much external information is needed, (ii) how and when to use it, and The Heaven-or-Hell MDP. The agent's choice from the initial state either sends it to the Heaven state where it receives a reward of +1 forever, or to the Hell state where it receives a reward of 0 forever. Once the agent is in either the Heaven or Hell state it cannot return to the initial state.

(iii) how much (active) regret is incurred.

More precisely, we introduce a setting where the learner is allowed to -instead of taking an action in the current state s t -ask for a rollout (starting in s t ) of a policy under a stopping condition both to be specified by the learner. For this setting we propose A-ROGUE (for Active RollOut-GUided Exploration), a learning algorithm that, using only O(log(T )) rollout transitions, achieves a O( √ T ) regret bound in multi-chain MDPs under some modest technical assumptions, see Theorem 7 in Section 4. This regret is optimal in T , as it matches the known lower bounds for communicating MDPs (see [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF]. The performance of the algorithm is supported by illustrative numerical experiments in Section 6.

Other types of external information In practice, one may sometimes have access to additional elements that help, or even trivialize the multi-chain MDP problem, such as a simulator, a harness, an expert, or a teacher. For instance, under the assumption that one has access to a harness designed by an expert that prevents a learner from accessing certain regions of the state space, then the initial multi-chain MDP can simply be reduced to a communicating MDP. Likewise, if one has a "rescue/repair" action that sets the learner back to an initial state, at the price of a large negative reward, then the initial MDP can again be reduced to an equivalent communicating MDP. Third, under the assumption that an inexpensive and accurate simulator is available, there is no need for learning in the real-world and the problem reduces to a planning problem. Thus, the multi-chain MDP formulation becomes potentially interesting when no harness, rescue/repair action is available, and when the only available simulators are either expensive or inaccurate. Finally, assuming that a good teacher is available, who provides examples of actions/policies to follow at various steps may also trivialize the problem. However, a good teacher has to know both the environment and what the learner has learned about the environment, and must monitor the learner to provide the right advice at the right moment. Note also that a teacher must be accurate. Such an assumption is however rarely met in practice, and designing a good teacher is difficult. Instead of assuming a teacher that constantly monitors the learner, we are interested in an active learner who can detect when it requires external information and can specify which kind of information she wants to get feedback on. Thus, we propose a setting where the learner can actively ask for rollouts of a policy with a stopping time criterion that are both designed by the learner.

Setting We target the challenging goal of learning in a single stream of state-actionrewards with no reset in a possibly non-recoverable multi-chain MDP, in the strong sense of regret minimization by combining standard MDP algorithms with active information retrieval : The learner can decide at any time not to act in the MDP but instead to propose a policy and a stopping condition and ask for a rollout of the policy until the stopping condition is met. To keep it simple, each rollout transition counts the same as a time step in which the learner executes an action and gives no reward. We capture this with the convenient notion of active regret that combines both the regret and the amount of rollout transition asked; see Section 2 for details. However, since our proof actually bounds the standard regret term and the extra information term separately, it is straightforward to adapt our approach to handle the case when different costs for rollout transitions and time-steps are used.

Previous work Previous work has mostly considered two types of performance guarantees: (1) regret and (2) sample complexity. Regret measures the difference between the sum of rewards received by the learning algorithm and the sum of rewards received by the optimal policy over a finite or infinite time horizon [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF]. Sample complexity measures the number of time steps the learning algorithm acts suboptimally from its current state [START_REF] Machandranath | On the Sample Complexity of Reinforcement Learning[END_REF]. Mostly, it is assumed that the underlying MDP has no transient region [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF][START_REF] Maillard | Optimal regret bounds for selecting the state representation in reinforcement learning[END_REF] or exactly one recurrent class [START_REF] Bartlett | REGAl: a regularization based algorithm for reinforcement learning in weakly communicating MDPs[END_REF], meaning that their guarantees do not hold in general multi-chain MDPs (such as the one given in Figure 2). Sometimes alternative guarantees are given that have the unintuitive property that if the learner is trapped in a region with low rewards, it can still learn to act "optimally" with respect to that region of the state-space.

With the goal of preventing the learner to take irreversible actions, various notions of "safety"have been discussed in the literature. Thus, [START_REF] Mihai | Safe exploration in Markov decision processes[END_REF] constrain the class of policies to satisfy a safety constraint. Although they provide some theoretical support for the resulting algorithm, they do not compare to the optimal policy (which may be considered as unsafe), and assume a prior that essentially tells where it is unsafe to go. Also, their formulation of the safety constraint makes the learning problem NP-hard, contrary to our approach. Further, note that in contrast to notions of safety [START_REF] Mihai | Safe exploration in Markov decision processes[END_REF][START_REF] García | Safe exploration of state and action spaces in reinforcement learning[END_REF], executing an irreversible action should not necessarily be avoided if it is the optimal thing to do. Indeed, if the region contains an optimal cycle the algorithm should enter it (but it first needs to be confident since the action is irreversible). Our approach is reminiscent of the earlier work of [START_REF] Clouse | On integrating apprentice learning and reinforcement learning[END_REF], [START_REF] Hailu | Learning by biasing[END_REF], [START_REF] Hans | Safe exploration for reinforcement learning[END_REF] and more recently of [START_REF] Geramifard | UAV cooperative control with stochastic risk models[END_REF] and [START_REF] García | Safe exploration of state and action spaces in reinforcement learning[END_REF], in which the agent explicitly asks for advice when it encounters specific situations. There, advice is generally an action proposed by a teacher, assumed to be good, or (in some sense) safe. [START_REF] Chernova | Interactive policy learning through confidence-based autonomy[END_REF] further propose to ask for a demonstration (rollout) from a teacher, who also chooses which policy to demonstrate. Unlike this, in our setting the learner proposes policies by herself.

In the planning community, some recent related work has shown how to plan efficiently in goal-oriented MDPs with traps, see (Teichteil-Königsbuch et al., 2011;[START_REF] Kolobov | A theory of goal-oriented MDPs with dead ends[END_REF]. However, none of these approaches provides any theoretical analysis but only gives experimental results. A notable exception, though in the different universal knowledge seeking framework, is [START_REF] Orseau | Universal knowledge-seeking agents for stochastic environments[END_REF], which provides a Bayesian algorithm that, given a set of models of the environment, tries to identify the right one by acting so as to maximize the information gain at each step.

The intuitive difficulty of dealing with many recurrent classes Regarding the amount of extra information asked by the learner (rollout transitions), our findings show that detecting whether an action is irreversible (enters a recurrent class) is generally not too costly, while deciding whether to execute a irreversible action is much more expensive. The reason is that since an optimal cycle may consist only of a single state, in the worst case every state-action pair inside a recurrent region reachable from the current state must be visited sufficiently often to decide whether to enter this class. Also, rollouts must be sufficiently long to reach any state in the class, which means that dealing with large traps (recurrent regions with large diameter) is intrinsically hard. Fortunately, in most applications, recurrent classes correspond to "traps" that -almost by definition-only consist of a few states. They typically model a physical component failure, where no (sensible) action can be performed from that point.

Contribution and outline

We consider finite (multi-chain) MDPs where some actions have (potentially) irreversible consequences that may cause high regret in the long-run. In Section 2, we introduce the convenient notion of active regret as well as two new quantities that capture the difficulty of learning optimal behavior in an MDP (as indicated in the previous paragraph): the local diameter d of an MDP intuitively measuring the "size" of a recurrent class and the sharpness of action-gaps γ that quantifies how bad an irreversible action can be. In Section 3, we introduce the A-ROGUE algorithm, that can handle multi-chain MDPs with possibly irreversible actions, by precisely deciding when and for which policy to ask for a rollout. A-ROGUE can be seen as a natural generalization of UCRL to the case of multi-chain MDPs, and indeed coincides with UCRL when one of its parameters (diameter guess) is set to ∞. Our main result Theorem 7 in Section 4 shows that A-ROGUE enjoys strong finite-time regret guarantees scaling as Õ

d γ + d √ T ,
by only resorting to O( 1 γ 5 log(T )) rollout transitions. Section 5 provides a detailed analysis of the regret performance, including some innovations of independent interest. Thus, we demonstrate how to estimate the return time to some state and give respective upper and lower bounds. Further, we obtain a bound on the number of rollouts needed to cover a subset of states from a given reference state. In the final Section 6, we present the results of some experiments in illustrative gridworlds. They show that popular algorithms driven by the "optimism in the face of uncertainty" principle such as UCRL and R-Max, and which enjoy strong performance guarantees in MDPs with strong recurrence properties, are clearly outperformed by A-ROGUE.

Setup and Notations

Setting Let Γ(X ) denote the set of all probability distributions over a non-empty set X . We consider an undiscounted Markov decision processes (MDP) M = S, A, p, ν with horizon T , finite state space S of size S, finite action space A of size A, transition kernel p : S × A → Γ(S) that maps each state-action pair to a distribution over next states, and reward function ν : S × A → Γ([0, 1]) that maps each state-action pair (s, a) to a real-value distribution over [0, 1] with mean µ(s, a). If the state and action spaces are clear from context and we are only interested in the mean rewards µ(s, a), we often write MDPs abbreviated as M = (µ, p). In any state s of the MDP, a learner is allowed to either 1. execute some action a, then receive a reward r(s, a) ∼ ν(s, a) and move to a next state according to p(•|s, a), or 2. ask for a rollout from the current state s for a policy π and a stopping criterion (both provided by the learner herself), until the stopping criterion is met.

All states visited and rewards generated during the rollout execution are reported to the learner, but the learner receives no rewards. After the rollout the learner is in the same state as before it, however each time-step in the rollout counts like a time-step in which an action is executed, cf. the definition of active regret below.

Regret Definition

We measure the regret of an algorithm A starting in state s 1 and interacting during T = T 1 + T 2 time steps with the MDP, where T 1 is the total number of actions executed in the MDP and T 2 is the total number of transitions of all requested rollouts. The regret is defined as the difference between the rewards accumulated by an optimal T -step policy π * run from s 1 during T time steps and the rewards accumulated by the algorithm A from s 1 (during the T 1 steps that A executed an action in the MDP). That is, we define the (expected) active regret by E R T , where

R T = T t=1 r(s t , a t ) - T t=1 r(s t , a t ) (1)
with r(s, a) ∼ ν(s, a), and where (s t , a t ) is the state-action pair visited at time step t when following π , and a t is the action executed by the algorithm A in the state s t visited by A at time step t. Note that counting the rollout transitions against the horizon is equivalent to putting an implicit cost on each rollout transition (the reward that an optimal policy would receive at the same time). Note also that the (expected) active regret is never smaller than the (expected) "traditional" regret [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF]. Note that access to rollouts does not eliminate the exploration-exploitation dilemma. Time increases independent of whether the learner is acting in the MDP or rather observing one step in a simulated rollout. Since the algorithm only receives reward when it is acting in the MDP, it must balance the number of time steps spent on observing rollouts with acting in the environment to obtain maximize rewards. As already mentioned, for the sake of simplicity we use the simplifying assumption that observing a rollout transition has the same cost as executing an action, while extensions to different cost functions are straightforward.

Measures of Complexity

For any two states s, s ∈ S and a policy π, let T M π (s, s ) be the (possibly infinite) expected number of steps needed to reach s starting from state s when following policy π in the MDP M . Further, let T M (s, s ) = min π T M π (s, s ) be the minimal transition time between s and s . Classically, the (global) diameter of an MDP M is defined to be D M = max s,s T M (s, s ) [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF], however in multi-chain MDPs, this quantity may be infinite. For a subset S ⊂ S, we also define D M S = max s,s ∈S T M (s, s ). Another standard notion is the action gap [START_REF] Massoud | Action-gap phenomenon in reinforcement learning[END_REF]. For horizon T , let Q M T -t (s, a) be the optimal action-value of the state-action pair (s, a) at time t for the MDP M (thus following an optimal policy), see [START_REF] Szepesvári | Algorithms for Reinforcement Learning[END_REF]. The action gap of (s, a) then is defined as

∆ M T -t (s, a) = max a ∈A Q M T -t (s, a ) -Q M T -t (s, a) .
Note that ∆ M T -t (s, a) > d implies that it is not possible to reach s from a successor state of (s, a) in d steps on average (since otherwise the difference of value would be less than d), that is T M (s , s) > d. Similarly, a (global) diameter D M d as assumed in [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF][START_REF] Brafman | R-max -a general polynomial time algorithm for near-optimal reinforcement learning[END_REF] implies that for all states and time steps every action is d-optimal, that is, ∆ M T -t (s, a) d. Local diameter We now introduce the new notion of local diameter. First, the d-covering

I G I G I G (a) (b) (c)
of an MDP M is a maximal set {S i ⊂ S|D M S i d} of maximally large state regions {S i } i I with S i ⊂ S that all satisfy D M S i d.
That is, each S i cannot be extended without increasing its diameter beyond d. We provide in Figure 3 an illustration of three coverings of a 4×4-gridworld MDP: The first covering corresponds to a partition with sets of diameter not larger than 2, but it is not a 2-covering, since it is a non-maximal set of maximally large regions with diameter not larger than 2. The second and third coverings are the unique 2covering and 4-covering of the MDP. The former one happens to be also a (trivial) partition of the state space. Note that if there is an overlap between S i and S i , then D M S i ∪S i 2d. In general, the S i of a d-covering will be multiply overlapping. Only in particular cases a d-covering will be a partition (non-overlapping covering) of the state space.

Definition 1 The local diameter d is the smallest d such that its d-covering is a partition of the state space. We denote the corresponding partition by {S i } i I .

For two sets S 1 , S 2 of this partition, and states s 1 ∈ S 1 , s 2 ∈ S 2 , we cannot have simultaneously T (s 1 , s 2 ) d and T (s 2 , s 1 ) d , since otherwise it would be possible to create a new set S I+1 with diameter less than d that overlaps the existing partition, which is not allowed by definition of d . Likewise, it is obvious that {S i } i I is unique. In the sequel, we will informally use the word "trap" to refer to regions S i from which it is difficult to escape, that is, such that min s / ∈S i min s∈S i T (s, s ) is "large". T -t (s, a) > γ (T -t), then the average number of steps needed to go from S i to S i cannot be less than γ (T -t) -2d .

Thus, in an MDP with large γ recovering from an action that enters a new region takes more time (actions are less "recoverable"). One needs to be more cautious, but at the same time such actions are easier to detect. In an MDP with small γ , recovering from an action that enters a new region takes less time. One need not be that cautious, but detecting such actions is more difficult.

To give further intuition about γ , we now consider a simple illustrative example that shows how it can be bounded.

Example 2 Consider an MDP with three disjoint regions A, B, C each with diameter d . Starting in A, one can only reach C from a state-action pair (s 1 , a 1 ) with deterministic transition, and B from (s 2 , a 2 ) with a transition that goes back to s 2 with probability 1 -p, and such that s 2 is d expected steps from s 1 . There are no other transitions between A, B and C. The learner always receives reward 0.5 in region A, 0.1 in B, and 0.9 in C. To compute γ , we look at ∆ M T -t (s 2 , a 2 ). We have V (s 2 ) = 0.5d + 0.9(T -t + 1 -d ), and otherwise ∆ M T -t (s 2 , a 2 ) d . Thus we deduce that γ 0.4p. In this example, the larger p, the less recoverable is action a 2 and we thus need to be confident when executing it. More generally, the larger γ, the less recoverable are actions and the more confident the learner needs to be.

Q(s 2 , a 2 ) p(T -t)0.1 + (1 -p)(0.5d + 0.9(T -t -d )), that is, ∆ M T -t (s 2 , a 2 ) 0.8p(T -t) -p(0.4d -0.9). Now, if T -t d , then ∆ M T -t (s 2 , a 2 ) > 0.4p(T -t),
Mobility assumption In the sequel, we only consider MDPs with local diameter d and γ -sharp action-gaps with non-trivial γ > 0. This ensures that irreversible actions can be detected and thus that an algorithm can decide to execute it nor not. To further focus on interesting cases, we make the following "mobility" assumption:

Assumption 1 There is a p 0 > 0 such that for all i, i with p(S i |S i , A) > 0 there is a (s, a) ∈ S i × A such that p(S i |s, a) p 0 and p(S i ∪ S i |s, a) = 1 .

That is, whenever it is possible to reach a region from another one, it is also possible to enter it easily (first condition) and without risking entering another region (second condition). This implies that there is always at least one action that does not lead to two regions at the same time. To give more intuition, an MDP that does not satisfy Assumption 1 contains a region such that any action leading to this region from another region also leads to a third one with positive probability. In such a situation, it is easy to design rewards such that no optimal policy can guarantee avoiding a "bad" region, see e.g. Figure 6. Thus Assumption 1 allows us to focus on cases where an optimal policy can achieve high cumulative reward. Note that this holds in most cases of practical interest, where "bad" regions are "well-separated" from "good" regions. We believe that Assumption 1 might be weakened further, for instance by assuming that the restriction only applies to regions S i visited by an optimal policy. However, since the analysis under such a weakened assumption would become more tedious, we did not investigate this direction in detail.

The A-ROGUE Algorithm

We now present the A-ROGUE algorithm (for Active RollOut-GUided Exploration) to handle the setting introduced in Section 2. We start with a high-level description as given in Algorithm 1, the full algorithm with all the technical details can be found below as Algorithm 2. B or D, the optimal policy will try to reach region A, which risks entering the bad regions C and E with high probability.

A-ROGUE is an extension of UCRL [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] designed to handle irreversible actions. As UCRL, A-ROGUE computes an optimistic policy, but before being executed, each optimistic action is first tested. If necessary, A-ROGUE asks for external information in an active way via rollouts. A-ROGUE tries to minimize the number of rollouts used and is thus rollout efficient.

High-level Description of A-ROGUE

Episodes, plausible MDPs, and optimistic policy Similar to UCRL, A-ROGUE proceeds in episodes1 k = 1, . . . , K of increasing length. At the start of each episode, a set of plausible MDPs M k is determined (using confidence intervals for rewards and transition probabilities, respectively), cf. line 4. The set M k is updated only when confidence intervals have changed a lot. In this case a new episode begins (line 6). Given the set M k , an optimistic policy π + k that maximizes the reward over all plausible MDPs in M k and all policies is computed (line 5).

Checking for irreversibility Unlike UCRL, A-ROGUE does not naively play the actions suggested by the optimistic policy. Instead, at each time step it is first tested whether the optimistic action recommended by π + k is potentially irreversible. Thus, A-ROGUE estimates the time needed to recover from this action (line 9), that is, to come back to the current state on a shortest trajectory after executing the action. The respective backup policy computed uses a pessimistic estimate in order to make sure that we can indeed come back to the reference state. An optimistic policy would obviously underestimate the real time to reach the reference state and may not be able to avoid traps. If the estimate of the recovery time is small enough (line 10), A-ROGUE plays the optimistic action, as there is a reliable way to get back to the reference state.

Testing for optimality If the estimate of the recovery time is large, the optimistic action is considered irreversible, and A-ROGUE evaluates whether the action is optimal (lines 12f). If A-ROGUE decides that the action is optimal (considering the optimality gap of the optimistic action), it is executed. In this case also the reference state is updated. Indeed, in the analysis it turns out to be important that the reference state is only updated after playing a near-optimal action with large return time. Indeed, updating the reference state at each time step to be the current state and thus computing a return path to the last visited state at each time step is not safe: Say each return path is guaranteed to be at most c-steps long, after executing m actions, one could only ensure a return path of at most cm-steps, that is linear in the number of executed steps. This is not enough to ensure sublinear regret guarantee in a worst case scenario. In contrast, updating the reference state and computing a return path to the last visited state reached after playing a near-optimal action with large return time enables to get a controlled regret.

Asking for rollouts Otherwise, if the optimistic action could not be identified as optimal, the algorithm needs more information and asks for a rollout (line 16). The policy that the algorithm asks the rollout for is not always the same. Alternatingly, the rollout is either asked for the optimistic policy π + k (which helps to decide whether the algorithm shall enter a transient region), or for the policy that plays the optimistic action suggested by π + k followed by the pessimistic backup policy (which helps improving the estimate of the return time to the reference state). The length of the rollout is of the order of the local diameter. However, the rollout is also stopped when the reference state is reached (indicating that the return time needs to be updated), or when the episode termination criterion is met, that is, when confidence intervals have changed a lot.

Remark 3 The choice of UCRL as base algorithm that is modified to work for multi-chain MDPs is to a certain extent arbitrary. We think that the presented methods could be adapted to work with different algorithms such as R-Max as well. However, for UCRL we have access to regret analysis that results in bounds nearly matching the known lower bounds. Thus, UCRL is a natural choice.

Details of A-ROGUE

After giving the high-level description, we are now ready to give the full technical details of A-ROGUE, cf. Algorithm 2.

Parameters Beside the horizon T and a confidence parameter δ, the algorithm uses a parameter ε > 0 and a function d : N → R in order to control the length of rollouts. That is, the length of a rollout is bounded by (1

+ 1 ε )D k , where D k = d(t k
) is an estimate for an upper bound on the local diameter of the MDP. Obviously, ε needs to be sufficiently small to guarantee that rollouts are long enough to provide the necessary information, but not too small to avoid incurring large regret for the steps of the rollout.

The parameter γ controls how conservative the algorithm behaves. Thus, for γ = 0, A-ROGUE won't execute any irreversible action with high-probability. This can be interesting if we know that all irreversible actions are bad. As γ gets larger, A-ROGUE behaves more and more like UCRL.

Algorithm 1 A high-level description of A-ROGUE 1: Set current time step t := 1. 2: for episodes k = 1, 2, . . . do 3:
Let the reference backup state s k be the current state s t .

4:

Define set of plausible MDPs M k based on past observations.

5:

Compute optimistic policy π + k that maximizes the reward over all MDPs in M k .

6:

7:

while confidence intervals haven't changed too much do 8:

Compute a pessimistic backup policy π k -that tries to reach the reference state s k after playing the optimistic action a + t = π + k (s t ).

9:

Compute the expected pessimistic recovery time to reach s k .

10:

if the expected time to reach s k after playing a + t is small enough then 11:

Phase I: Execute a + t , get reward r t and next state s t+1 . Set t := t + 1.

12:

else 13:

if the estimated optimality gap of a + t is small enough then 14:

Phase II: Execute a + t , get reward r t and next state s t+1 .

15:

Update the reference state s k = s t+1 . Set t := t + 1.

16:

else 17:

Phase III: Depending on the last rollout, ask either for a rollout of the optimistic policy π + k (if the last rollout was for the backup policy), or for a rollout that first plays a + t and then the backup policy π k -(if the last rollout was for the optimistic policy). Stop when the confidence intervals have changed a lot, or s k is reached, or the rollout is too long. Set t := t + 1 for each transition. Let t k := t (starting time of episode k) and set the reference backup state s k = s t k .

4:

Let M k := M t k (δ/T 2 ). 5: Compute M + k = (r + k , p + k ) that satisfies V M + k T -t k (s t k ) = sup M ∈M k V M T -t k (s t k ) as well as respective value Q + k and policy π + k . 6: Let Stop k (t) := {∃s, a : N t (s, a) 2N t k (s, a)∨1}. 7: while not Stop k (t) do 8: Compute backup MDP M k -= (r k , p k -) with reference state s k , horizon 2 γ (1 + 1 ε )D k , backup values Q k -and policy π k -, and D k = d(t k ).

9:

Compute the expected pessimistic recovery time

T - t = |Q k -(s t , π + k (s t ))|. 10: if T - t < 2D k then 11:
Phase I: Execute a + t = π + k (s t ), get reward r t and next state s t+1 . Set t := t + 1.

12:

else 13: if ∆ - T -t (s t , a + t ) < γ(T -t) then 14:
Phase II: Execute a + t , get reward r t and next state s t+1 .

15:

Update the reference backup state s k = s t+1 , t := t + 1.

16:

else 17:

Phase III: Depending on the last rollout, ask either for a rollout of π + k (if the last rollout was for a backup policy π ), or for a rollout that first plays a + t and then the backup policy π k -(if the last rollout was for an optimistic policy π + ). The rollout is stopped when either Stop k (t) happens, or s k is reached, or its length is more than (1 + 1 ε )D k . Set t := t + 1 for each observed transition.

18:

end if 19: end if 20:
end while 21: end for Plausible MDPs (line 4). In episode k starting at time t k , A-ROGUE defines, using the past observations, the empirical reward function r t k and the empirical transition kernel p t k . They are used to define the set M k of plausible MDPs as follows:

Definition 4 The set M t (δ) of δ-plausible MDPs at step t compatible with the empirical reward function r t and empirical transition kernel p t is the set of all MDPs S, A, p, ν with mean reward function μ : S × A → [0, 1] and transition kernel p : S × A → Γ(S) such that for all (s, a) ∈ S × A,

r t (s, a) -μ(s, a) C µ t (s, a) := log(2SA/δ) 2Nt(s,a) , (2)
p t (•|s,a) -p(•|s,a) 1 C p t (s, a):= log(2 S+1 SA/δ) 2Nt(s,a) , (3)
where N t (s, a) := t i=1 I{s i = s, a i = a} is the number of visits of the pair (s, a) up to time t.

2

We prove later in Section 5.1.2 that the true MDP is plausible with high probability:

Lemma 5 With probability higher than 1-2δ/T , the true model is plausible simultaneously for all episodes k. That is, M ∈ M t k (δ/T2 ) for all k.

Remark 6 Both quantities C µ t (s, a) and C p t (s, a) could be sharpened if some further knowledge is given about the reward and transitions. Also, following [START_REF] Filippi | Optimism in reinforcement learning and kullback-leibler divergence[END_REF] we recommend to use KL-based confidence-bounds instead of (3) for practical applications.

Extended Value Iteration (line 5). The so-called optimistic MDP

M + k = (r + k , p + k ) ∈ M k maximizes the optimal value V M T -t k (s t k
) among all plausible MDPs M and can be computed e.g. by Extended Value Iteration, see [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] via an augmented MDP which we denote andπ + k the respective optimistic policy (that is, the greedy policy w.r.t. Q + k ). We also use Q T -t to denote the Q-value function for the true MDP M and horizon T -t.

M + k . Q + k is the associated optimistic Q-function (with horizon T -t k ),
Estimating the return time (line 8-9). Before executing the optimistic action a + t = π + k (s) in some state s, A-ROGUE tests if there is a short path back to the reference backup state s k after playing a + t . That is, it tests if the action is reversible. This is a simple stochastic shortest path (SSP) problem: Defining a deterministic reward function by r k (s) = -1 if s = s k , and 0 else, consider the set of δ/T 2 -plausible backup MDPs M k = { M = (r k , p) : p satisfies (3)}. Any SSP algorithm (or also Extended Value Iteration) can be used to compute the pessimistic return policy π k -to the backup state s k , together with the pessimistic backup values Q k -. Both quantities are defined similarly to Q + k and π + k , but using the set of MDPs M k instead of M k . Since r k is negative, the Q-values are also negative, and

T - t = |Q k -(s t , a + t )| represents the minimal expected return time from s t back to s k after playing action a + t def = π + k (s t ), in the least favorable plausible backup MDP. Importantly, Q k -is computed with time horizon 2 γ (1 + 1 ε )D k (as opposed to T -t k for Q + k ), which implies that T - t is also less than 2 γ (1 + 1 ε )D k .
Note that we do not want to run rollouts for too long since we incur a linear regret along each rollout.

Deciding whether to act or to ask for a rollout (lines 10-13). If the estimated return time T - t is < 2D k ,3 where D k is an estimate of the local diameter of the MDP, A-ROGUE executes the optimistic action a

+ t = π + k (s t ). Otherwise, if T - t 2D k , a + t
is considered to be an irreversible action, since executing this action may lead to suffer a higher regret than the worst-case regret one would suffer for playing an action in a MDP with diameter D k . Thus, in the following we will refer to the test in line 10 of the algorithm as the recovery test and say that the test is passed, if T - t < 2D k . To decide if playing a + t is good or not, A-ROGUE computes a pessimistic estimate for the action gap. Intuitively, we want to test whether the quantity max

a Q T -t (s, a) - Q T -t (s, a + t ) is small. If it is smaller than the minimal action gap min a:∆ T -t (s,a)>0 ∆ T -t (s, a) of s, then the action a +
t must be optimal. Since we do not have direct access to Q T -t , the used optimality test uses the set of plausible models M k instead to compare to the action gap in the worst case plausible MDP:

∆ - T -t (s t , a + t ) sup M ∈M k max a Q M T -t (s t , a) -Q M T -t (s t , a + t ) .
(The supremum is actually a maximum, as it is enough to optimize over the simplex.) When ∆ - T -t (s t , a + t ) < γ(T -t), this means that the action gap is indeed small, thus action a + t is considered to be optimal and hence played. In the following, we refer to the test in line 13 as the optimality test and say that an action a + t passes the test, if

∆ - T -t (s t , a + t ) < γ(T -t).
Asking for a rollout (line 17). In case a + t does not pass the optimality test, A-ROGUE asks for an exploratory rollout from s t . As already explained, the algorithm alternates the policy for which a rollout is requested. Either A-ROGUE requests a rollout of the optimistic policy π + k , or (if the last rollout has been requested for the optimistic policy) a rollout of the non-stationary policy that first executes a + t = π + k (s t ) and then policy π k -, the pessimistic policy that tries to come back as fast as possible to the backup state s k . The rollout is stopped if either (i) the number of visits in some state-action pair has doubled (when also the episode terminates), (ii) the backup state s k is reached, or (iii) the length of the rollout exceeds 1 + 1 ε D k .

Performance Guarantees

The following theorem is, to the best of our knowledge, the first sublinear regret guarantee that holds for a large class of multi-chain MDPs with possibly infinite diameter. For convenience, it is stated and proved assuming that all regions are directly reachable from the region S i 0 where the learner starts. This assumption is relaxed below, see Remark 8.

Theorem 7 (Bound on active regret) Let M be an MDP with local diameter d and γ -sharp action-gaps that satisfies Assumption 1 with access probability p 0 . Assume also that all transition probabilities are either 0 or p min > 0. Given an upper bound D d , the active regret of A-ROGUE with parameters δ, d(t) = D, γ γ , and ε < min

p 0 d p 0 d +p 0 +d , p 0 1+p 0 after T steps is upper bounded by E R T 5 + 1 p 0 8d γ T + 2d γ + 4 + 1 p 0 d SA log 2 8T SA +6( √ 2+1) 2 + 1 p 0 + 1 p min d log(2 S/2+1 AST 2 /δ) √ SAT + 16 SD 3 (1 + ε) 4 γ 2 ε 3 (1 -ε) log(2 S+1 SAT 2 /δ)
Bound on number of asked rollout transitions

+ 1+ε γε D + 2δ .
Simplified, the regret is of order

E R T = O d S A log(TAS/δ) + d γ p 0 ∧ p min √ T + d SA p 0 log T

SA

Regret when acting

+ D 3 S 2 γ 2 ε 3 log TAS δ Extra information asked .
This bound captures the essential behavior of the algorithm: The first term is basically of the same order as the regret of UCRL [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF]. This term also gives the long-term regime of the algorithm (after it identified irreversible actions). The remaining term gives the number of transitions in rollouts the algorithm asked for. This happens in two situations: first when the algorithm wants to find out whether an action is irreversible, and second when it needs to know whether an action identified as irreversible is optimal. While the irreversibility of an action is rather cheap to identify and can be accomplished by rollouts of length O(D k ), the second case needs much more information, as it depends on the action-gap of the current state. Indeed, before playing an irreversible action the algorithm needs an accurate estimate not only of the value inside the region it intends to enter, but also of the value of states outside the region. Note that the algorithm not only suffers big loss when entering a bad region, it also incurs some regret when not entering an optimal region.

Remark 8 If no bound on d is available, one can use d(t) = log(t) instead. We get a similar bound, where one needs to replace D 2 in the first operand of the max by e d , and D in the second operand of the max by log(T ).

Remark 9 If all regions except the initial one cannot be escaped a.s., then one can replace the term 8d γ T + 2d γ in Theorem 7 with a constant. This term is indeed due to the possibility of escaping a region and re-entering it possibly several times, which in a worst case produces this additional regret term.

Remark 10 If not all regions are directly reachable from S i 0 but some are only reachable by crossing, say, intermediate regions, then the bound of Theorem 7 holds with d replaced with ( + 1)d and D replaced with ( + 1)D.

Remark 11 As a special case, the result holds as well in the case when the MDP is indeed weakly communicating and has small diameter D. Then d = D, γ = ∞, and p 0 = 1. Note that in this case A-ROGUE with parameter γ = ∞ coincides with UCRL.

Overview of the proof Before providing a fully detailed proof in Section 5, let us give some high-level sketches in order to highlight the main steps of the proof. The proof is based on ideas similar to those for showing the regret bound for UCRL in [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF]. However, we need to handle four additional difficulties: 1) the different behavior of A-ROGUE in each episode (cf. phases I, II, and III in lines 10, 13, and 15 of the algorithm), 2) the accurate estimation of the return time T - t to identify irreversible actions, 3) the decisions to play irreversible actions or not, and 4) the total number of roll-out transitions asked by the algorithm. First, the case when no irreversible action is played by the algorithm nor the optimal policy can be handled by standard concentration bounds and using the local diameter d , similar to the already mentioned proof in [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF]. When irreversible actions come into play, regret is incurred in two cases: when we play an irreversible action that leads to a bad region, or when we do not play an irreversible action that leads to a good region early enough. For the first case, we show that an action that passes the test of line 13 must be d -optimal with high probability, and that the estimated return time T - t for an irreversible action must be larger than 2D k with high probability. This prevents the algorithm from playing bad irreversible actions. For the second case, we show that any d -optimal action will pass the test of line 13 for small enough confidence bounds, depending on the γ-sharpness of the MDP. The last part of the proof is to show that the confidence bounds indeed shrink fast enough, and to handle the number of roll-out transition requested by A-ROGUE. This is a tricky part of the proof, where the length of the roll-outs as well as the policy chosen to be executed must be chosen carefully. Here, we first show that when the optimal return time in the true MDP

T t = |Q k (s t , a t )|is small, so is T - t = |Q k -(s t , a t )|
, so that the algorithm executes the optimistic policy (and does not ask for a roll-out). Then, we use the observation that by definition of d , and by Assumption 1, each region can be explored from its boundary by O( d)-long roll-outs. We show that a controlled number of roll-outs of length (1 + 1 ε )D k of the policies π -and π + k is enough to shrink the confidence bounds fast enough, leading to the final sub-linear regret.

Regret Analysis (Proof of Theorem 7)

In this section, we now provide a complete proof of Theorem 7. As the proof is a bit long, it is divided into several parts. At the core the proof follows the lines of proof of the regret bound of the regret bound for UCRL [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] However, there are several additional difficulties we need to take care of: 1) the different behavior of A-ROGUE in each episode (lines 10, 13, and 15 of the algorithm), 2) the accurate estimation of the return time T - t , 3) dealing with irreversible actions and 4) the total number of roll-out transitions asked by the algorithm. The proof provides a few innovations in order to handle these difficulties. Each of them may be of independent interest. We first give a brief overview of the single parts of the proof.

• Sections 5.1.1 and 5.4: Decomposing the cumulated reward / Bellman equation / confidence bounds.

In these first two sections, we provide an initial decomposition of the cumulative reward, disregarding regret due to entering another region, so as to provide the main picture of the proof. We use a new decomposition in Section 5.1.1 and control the regret backward from the last episode to earlier episodes, as opposed to standard proofs. A second innovation is that, when introducing the Bellman equation, following the proof technique from Jaksch et al. ( 2010) (see Section 5.4), we replace the span of the optimistic value function by a more accurate local span over the immediate successor of the current state, and control it using the local diameter of Definition 1.

• Section ??: Dealing with irreversible transitions.

We modify the decomposition from Sections 5.1.1 and 5.4, to control what happens when the optimal policy plays an irreversible action. One specific difficulty is to handle the case when we need to play an irreversible action to enter an optimal region but we do not play it for lack of confidence, thus causing possibly linear regret during this time lapse. We show in Lemma 12 that an action that passes the test in l.13 must be d -optimal (if the model M is plausible), and that every d -optimal action will pass the test in l.13 when confidence intervals become small enough. Here the notion of local diameter and γ-sharpness play an important role in defining the tests used in A-ROGUE. This result enables us to ensure that, provided that some states are visited often enough (so that confidence intervals become small), we eventually enter the optimal region after a controlled number of steps, and thus can control the regret.

• Section 5.1.2: Confidence intervals and high probability events.

We derive simple confidence bounds that characterize the uncertainty in our estimates of the reward and transition probability distributions as a function of the number of samples observed from each state-action pair and other relevant factors. In addition to showing how the learned model improves with samples (as is necessary in the regret analysis of UCRL), these confidence intervals also allow us to bound the minimum number of steps to return to the current backup state (which is unique to A-ROGUE). Specifically, we provide in Section 5.1.4 a bound on the estimated return time, by seeing it as a value function. We thus use the definition of the backup MDP and a Bellman decomposition similar to the one used for the MDP model in order to control the estimation error.

• Section 5.5: Total number of roll-outs.

In Section 5.5, we bound the number of episodes and the number of simulated roll-outs requested by A-ROGUE. This is a tricky part of the proof, where we have to show that the length of the roll-outs as well as the roll-out policy are well chosen by the algorithm. This is an important innovation of the proof, where we study in detail the number of roll-outs of some length d from some policy π needed to ensure that a stateaction that is reachable in d steps is visited a certain number of n times on average. We then use this to control the total number of roll-outs from such a policy π that are needed in order to visit often enough the set of all states reachable in d steps from one point, and apply it to π -. We believe that such results (as given in Section ??) are of independent interest. We then show that the backup-policy satisfies the desired property, and thus get a control on the number of roll-out transitions needed so that we have an accurate estimation of the back-up time.

• Section 5.6: Regret.

In this last section, we bound the regret of A-ROGUE first when the diameter is unknown and second when an upper bound for the diameter is known. This section, ties together the findings in the previous sections of the appendix and provides the main proof of Theorem 7.

1 K ... π π

Inside trap

Figure 7: A high over-view of the algorithm and of the proof: In black, the trajectory followed by one execution of A-ROGUE divided into K episodes (internal to the algorithm). In blue, optimal policies starting from the starting point of each A-ROGUE-episode. We consider a case in which it is optimal to enter a trap: the blue cross indicates when the optimal policy enters it, the red cross when A-ROGUE enters it. Finally, the green loops symbolize parts of episodes when roll-outs are asked and during which we accumulate regret for not acting. The proof starts by capturing what happens in the last episode K (Section 5.2.1), and progressively compares the algorithm to an optimal policy run from earlier and earlier starting points (Section 5.2.2). The special point when A-ROGUE enters the trap is dealt with separately in section ??. The total number of roll-out transitions (green parts) is handled in Section 5.5.

Let us start by introducing notations. The algorithm proceed in T time-steps t ∈ {1, . . . , T }. We denote this set T T , and introduce more generally for all t ∈ N the notation T t = {1, . . . , t}, with the convention that T 0 = ∅. We make a distinction between the timesteps when an action is output, which is called a decision-step, and the time-steps when an roll-out transition is observed, which we call a roll-out step. We denote T D t ⊂ T t the subset of time-steps corresponding to decision-steps until time-step t, and T R t = T t \ T D t the corresponding subset of roll-out steps.

The algorithm proceed in successive episodes. The number of episodes until time T is a random variable that we denote K T . For k ∈ {1, . . . , K T }, episode k starts at t k ∈ T T . Thus t 1 = 1, t k+1 -t k is the length of episode k, and we denote by convention t K T +1 = T + 1. Thus, the last episode starts at t K T ∈ T T , and stops at time T = t K T +1 -1. With this convention, we write T (k) = T t k+1 -1 \T t k -1 the time-steps corresponding to episode k, for k ∈ {1, . . . , K T }, and similarly, define

T D (k) = T D t k+1 -1 \T D t k -1 and T R (k) = T R t k+1 -1 \T R t k -1 .
We also introduce T k,t = T (k) ∩ T t , the set of time-steps between t k and t (that is T k,t = {t k , . . . , t}), as well as the corresponding set

T D k,t = T D (k) ∩ T D t of decision-steps and T R k,t = T R (k) ∩ T R
t and t R k = argmax t∈T R (k)
t are the first and last roll-out-steps in episode k. We also introduce the first and last time-steps of

T (k) , t k = argmin t∈T (k) t = t k and t k = argmin t∈T (k) t = t k+1 -1, for coherence.
Regarding states, starting from the same initial state s 1 , s t denotes a state reached by A-ROGUE at time-step t, and s t one reached by the optimal policy π T with horizon T at the same time-step. We say that the algorithm enters a region S i at time-step t if s t-1 / ∈ S i and s t ∈ S i . We say it leaves region S i at time-step t if s t-1 ∈ S i and s t / ∈ S i . In the sequel, we denote by t m i ∈ [-∞, +∞] the m-th smallest time-steps when the algorithm enters region S i , and t m i ∈ [-∞, +∞] the m-th smallest time-steps when it leaves region S i . We also denote t the first time-step when the algorithm leaves the initial region, and t the last time-steps when the algorithm leaves any region. Finally, we denote k the episode that contains t, that is such that t ∈ T (k) .

Preliminary results

Before presenting the core of the proof of Theorem 7, we start by introducing a few useful results ans lemmas.

Decomposing the cumulated reward.

The expected active regret E R T of A-ROGUE at time T can be decomposed using the cumulative rewards received during each episode k ∈ N until the last episode K T .

In the sequel, if a (possibly non-stationary) policy π = (π t ) t 1 is executed in an MDP M at (not necessarily consecutive) times t ∈ T = {t 1 , . . . , t τ }, starting from state s at time t 1 then we define its accumulated reward by R π M (T|s). Its is defined by

R π M ( T|s) = t ∈ T r(s t , π t (s t )) ,
where π t refers to the policy π at time t . Note that the time matters since the policy π needs not be stationary. Typically, an optimal strategy executes π at each time step in true MDP M , whereas A-ROGUE executes an optimistic policy π k in episode k in M only when it does not ask for roll-out transitions, that is when t ∈ T = T D (k) . Since A-ROGUE receives no rewards during the execution of a roll-out, the reward accumulated during episode k, from t k up to t k+1 -1, is

R A M ,k = R π k M (T D (k) |s t k ) .
Then, using these notations, we can rewrite the regret as

E R T = E T t=1 r(s t , a t ) -E T t=1 r(s t , a t ) = E R π M (T|s 1 ) - K T k=1 t∈T D (k) r(s t , a t ) + t∈T R (k) 0 = E K T k=1 R π M (T (k) |s t k ) -R π k M (T D (k) |s t k ) = E K T k=1 R π M (T (k) |s t k ) -R A M ,k
.

(4)

Confidence intervals and high probability events

In this section, we derive confidence intervals for the reward and transition kernel estimates.

Let us introduce

r t (s, a) = 1 N t-1 (s, a) t-1 t =1 r(s t , a t )I[s t = s, a t = a] ,
where we recall that T , and deduce that with probability higher than 1 -δ/T , simultaneously for all (s, a) ∈ S × A and all episodes k K T ,

N t-1 (s, a) = t-1 t =1 I[s t = s, a t =
|r M + k (s, a) -µ(s, a)| = r M + k (s, a) -r t k (s, a) + r t k (s, a) -µ(s, a) 2 log(2AST 2 /δ) 2N t k (s, a) = 2C µ k (s, a) , (5)
provided that the set of plausible MDPs chosen in A-ROGUE is M t (δ/T 2 ). Following a similar argument but with specific inequality for the • 1 control (Weissman et al., 2003), we obtain that with probability higher than 1 -δ/T , simultaneously for all (s, a) ∈ S × A, and all episodes k K T ,

p M + k (•|s, a) -p(•|s, a) 1 2 log(2 S+1 AST 2 /δ) 2N t k (s, a) = 2C p k (s, a) . (6)
Thus, combining ( 5) and ( 6) together with a union bound over all episodes, we obtain Lemma 5 On an event Ω of probability higher than 1 -2δ/T , the true model is plausible (that is M ∈ M t k (δ/T 2 )) simultaneously for all episodes k. This Lemma will help us show that A-ROGUE avoids entering a bad region with high probability. Now, on the complement of this event, Ω c , the regret is uncontrolled, and A-ROGUE incurs a possible linear regret, leading to an error term 2δ

T T = 2δ. In the sequel, we introduce the notation

E Ω [•] def = E[•I{Ω}]. Thus, by Lemma 5, it holds E R T E R T I{Ω} + 2δ T T = E Ω R T + 2δ . (7)

Sub-optimality test

In this section we consider the test on the sub-optimality gaps (Line 13). Without such a test, with high probability the algorithm would never decide to play an irreversible action even if this is the optimal thing to do. Indeed, since with high probability all played actions would not be irreversible due to test of Line 10 (See section 5.1.4), the algorithm would not enter another region. The regret can be linear in difference between the time t when the optimal policy would have entered an optimal region to the time t the algorithm enters the same region. The test of line 13 on sub-optimality gaps prevents tt (and thus the regret) to be too large. Note that in case when it is optimal to say in the initial region, t = ∞ and the difference is trivially bounded.

Lemma 12 On the event Ω that M is plausible, an action a t that passes the sub-optimality test in l.13 is d -optimal:

Q T -t (s, a ) -Q T -t (s, a t ) d .
Further, if a t is d -optimal, then it passes the sub-optimality test in l.13 as soon as

C µ k ∞ + 2 + 1 p 0 d C p k ∞ < γ 4 . ( 8
)
Note that if the test in l.13 is passed for a t , this implies that no roll-out is asked at that time.

Recall that Q T -t denotes the value function for the true model M at time t. Intuitively, we want to test at time t whether the quantity max a: a), that is, the action gap of s, then the optimistic action must be actually optimal. Since we do not have access to Q T -t , the test of line 13 uses the plausible models M k in episode k instead.

Q T -t (s,at) =Q T -t (s,a) Q T -t (s, a) - Q T -t (s, a t ) is small enough. If it is smaller than min a:Q T -t (s,a ) =Q T -t (s,a) ∆ t (s,
Step 1: We first show that if a t is a bad action, that is

∆ T -t (s, a t ) = Q T -t (s, a ) - Q T -t (s, a t ) > d then ∆ -
T -t (s, a t ) is big. Indeed, in this case and under the event

M ∈ M k we have ∆ - T -t (s, a t ) = sup M ∈M k max a =at Q M T -t (s, a) -Q M T -t (s, a t ) sup M ∈M k Q M T -t (s, a ) -Q T -t (s, a ) + Q T -t (s, a ) -Q T -t (s, a t ) + Q T -t (s, a t ) -Q M T -t (s, a t ) ∆ T -t (s, a t ) + sup M ∈M k Q M T -t (s, a ) -Q T -t (s, a ) + Q T -t (s, a t ) -Q M T -t (s, a t ) ∆ T -t (s, a t ) γ (T -t) ,
where in the third line, we used the fact that since M ∈ M k by assumption, then the supremum term is non-negative, and where in the last line, we used the property that since for all s, a either ∆

T -t (s, a ) -Q T -t (s, a + t ) d .
This proves the first part of Lemma 12.

Step 2: Now, we show that when an optimistic action a t is d -optimal, it passes the test after not too many time steps. To that end, we derive the following inequalities sup

M ∈M k max a =at Q M T -t (s t , a) -Q M T -t (s t , a t ) = sup M ∈M k Q M T -t (s t , a M ) -Q + T -t (s t , a t ) + Q + T -t (s t , a t ) -Q M T -t (s t , a t ) sup M ∈M k Q M T -t (s t , a M ) -Q + T -t (s t , a M ) + Q + T -t (s t , a t ) -Q M T -t (s t , a t ) sup M ∈M k Q + T -t (s t , a t ) -Q M T -t (s t , a t ) , (9)
where we introduced a M = argmax a =at Q M T -t (s t , a). In the second line we used the fact that

Q + T -t (s t , a t ) Q + T -t (s t , a M
) since a t is optimistic. In the third line, we used the fact that Q + is the optimistic Q-function. Note that there is no reason that a t be the best action for a plausible MDP M . Now, we want to control the difference of value between the successor states of a t . If s t ∈ S i 0 and a t is at the frontier of a region S i , then several situations may occur: First, if all the successor states of a t are inside the same communicating region S i , then the difference of value between the successor states must be less than the diameter d of the region. Second, in other cases two successor states of a t belong to different regions, say S i and S j . Since a t is d -optimal by assumption, the difference of values between its successor states cannot exceed d plus the difference of values between the successor states of s t , a , where a is an optimal action in state s t . Now the difference of values between successor states s ∈ S i , s ∈ S j of s t , a cannot be larger than d /p 0 + d = (1 + 1/p 0 )d : Indeed by assumption 1, at least one state-action pair (s, a) in the region S i satisfies p(S j |s, a) p 0 without risking entering a third region. Now, it requires at most d steps to reach s from a point in S i , and thus at most d /p 0 steps to enter S j . On the other hand, it requires at most d steps to reach this point from s ∈ S j , and thus the difference of value is at most max{(1 + 1/p 0 )d , d }. Thus, in this second case, the difference of values between the successor states of a t is bounded by (2 + 1 p 0 )d . We can now resort to a simple Bellman propagation error analysis to get the following inequality for all M ∈ M k

Q + T -t (s t , a t ) -Q M T -t (s t , a t ) T -t j=1 4 δ s P at P π T -t-j 1 C µ k ∞ +(2 + 1 p 0 )d C p k ∞ 4(T -t) C µ k ∞ + (2 + 1 p 0 )d C p k ∞ , (10)
where C µ k (s, a) and C p k (s, a) are the confidence bounds on the reward (2) and transition kernel (3), respectively. Here P a denotes the S × S transition matrix with (s, s ) entry p(s |s, a) (from the true MDP M ), and δ s the vector of size S with s th component equal to 1 and others equal to 0. Equation ( 10) is obtained by first expanding the Q-values using the Bellman equation, second inserting the true M , third controlling the error on the reward and on the probability distributions with the confidence bounds ( 5), (6) and fourth using the above discussion to control the range of the value function by (2 + 1 p 0 )d . Note that in case a leads to an absorbing state, δ s P a P π T -t-j 1 may be equal to one for each j. An action a t passes the test if ∆ - T -t (s t , a t ) γ(T -t). Now combining ( 9) and (10), we have shown that on the event that M is plausible, an optimistic action a t that is d optimal must satisfy

∆ - T -t (s t , a t ) 4(T -t) C µ k ∞ + 2 + 1 p 0 d C p k ∞
Thus, we deduce that in order that such an action passes the test of line 13 it is enough that

C µ k ∞ + 2 + 1 p 0 d C p k ∞ < γ 4 , (11)
which concludes the proof of Lemma 12.

Estimate of the return time

In this subsection, we relate

T - t = -Q k -(s t , a t ) to the return time T t = -Q k (s t , a t ) in
the true MDP. We want to show that T - t is not too small when T t is large (the action a t is irreversible), to avoid executing actions that we are not sure of. We also want that T - t is not much larger than T t when T t is small, to ensure that an optimistic action with low recovery time passes the test. Note that if T - t is too large, we may ask for more roll-outs and thus incur a regret fro each additional roll-out.

We study the recovery test of line 10. First, we want to show that if a t is a bad action, that is, ∆ T -t (s t , a t ) > γ (T -t) (see Definition 2), then a t does not pass the test. Indeed in that case, it must be that T t > γ (T -t) as well. Now T - t is computed using the (pessimistic) extended value iteration algorithm. It does not use the horizon T -t but instead c(1 + 1 ε )D k , where the value c = 2 γ is chosen in the algorithm. Thus, for any not too large t T -c(1 + 1 ε )D k , provided that M is plausible it must be the case that

T - t γ c(1 + 1 ε )D k ,
which is bigger than 2D k if ε < 1 and c 1/γ (We can further discard the case when t > T -c(1 + 1 ε )D k at the price of loosing at most a constant regret c(1

+ 1 ε )D k ).
In this case, a non recoverable action does not pass the recovery test (on the event that M is plausible). Thus, it holds that

Lemma 13 Assuming that T - t is computed with horizon c(1+ 1 ε )D k , for t T -c(1+ 1 ε )D k ,
where ε < 1 and c 1/γ , then on the event that M is plausible, then an action a t such that ∆ T -t (s t , a t ) > γ (T -t) does not pass the recovery test, that is T - t 2D k . Now, two cases can happen when a t is a good action ∆ T -t (s t , a t ) d : The recovery time T t is either small or big. It is not a problem if the return time is big but a t still passes the test. We want to prevent that when the return time T t is small and a t is not a bad action, then a t does not pass the test. To that end, we show a bound on T - t when T t D k : Lemma 14 Under the event that M is plausible, if T t D k , then it holds

T - t D k 1 + 2C p k,t c 1 + 1 ε D k , (12)
where

C p k,t = max s∈S(s t ,D k ),a∈A C p k (s, a) ,
and S(s, ) denotes the set of all states that are reachable from s in steps.

This result implies that if 2C p k,t c 1 + 1 ε D k < 1 then T - t < 2D k holds (on the event that M is plausible), that is the recovery test of line 10 is passed in this case. In Section 5.5, we bound the number of episodes that ensures that 2C p k,t c 1 + 1 ε D k α, for some α < 1.

Proof Let p k -be the kernel corresponding to the worst plausible backup MDP, that is one

associated to Q k -.
Then let π k be the optimal backup policy in the true MDP (that is with transition kernel p), and π k -the optimal backup policy in the worst plausible backup MDP. By construction of the backup MDPs, it holds that Q k (s, a) = 0 if s = s t k and otherwise

Q k (s, a) = -1 + s ∈S p(s |s, a)Q k (s , π k (s )) . ( 13
)
On the other hand, since Q k -is computed by the algorithm with look-ahead horizon

c(1 + 1 ε )D k , we get that Q k -(s, a) = 0 if s = s t k and otherwise Q k -(s, a) max -1 + s ∈S p k -(s |s, a)Q k -(s , π k -(s )), -c 1 + 1 ε D k .
Now let us compare these two values for the chosen action a t . It holds that

Q k (s t , a t ) -Q k -(s t , a t ) = s ∈S p(s |s t , a t ) Q k (s , π k (s )) -Q k -(s , π k -(s )) s ∈S p(s |s t , a t ) Q k (s , π k (s )) -Q k -(s , π k (s )) + s ∈S p(s |s t , a t ) Q k -(s , π k (s )) -Q k -(s , π k -(s )) + s ∈S p(s |s t , a t ) -p k -(s |s t , a t ) Q k -(s , π k -(s )) . ( 14
)
The second sum is negative since

Q k -(s , π k (s )) Q k -(s , π k -(s )
) by construction of the pessimistic π k -, and the third sum is less than p

(•|s t , a t ) -p k -(•|s t , a t ) 1 c(1 + 1 ε )D k since |Q k -(s , π k -(s ))| c(1+ 1 ε )D k by construction.
Thus, we make appear the confidence bound C p k from Lemma 5. More precisely, we consider the set S(s, ) of all states that are reachable from s in steps and introduce the quantity

C p k,t = max s∈S(s t ,D k ),a∈A C p k (s, a) .
Indeed, we are interested specifically in states that are reachable in less than T t D k steps from s t (when following π k ). Using this notation, and since the pessimistic backup MDP and M are plausible by assumption, it holds that

Q k (s t , a t ) -Q k -(s t , a t ) s ∈S p(s |s t , a t ) Q k (s , π k (s )) -Q k -(s , π k (s )) + 2C p k (s t , a t )c 1 + 1 ε D k 2C p k,t c 1 + 1 ε D k + s ∈S p(s |s t , a t ) Q k (s , π k (s )) -Q k -(s , π k (s )) .
We now apply the same decomposition as equation ( 14) to the term

Q k (s , π k (s )) - Q k -(s , π k (s ))
, that is, following the path of π k starting from s t . Propagating this decomposition j ∈ N times we get

Q k (s t , a t ) -Q k -(s t , a t ) E 2C p k,t c 1 + 1 ε D k j + s ∈S p(s |s j t , a j t ) Q k (s , π k (s )) -Q k -(s , π k (s )) , ( 15
)
where the expectation is over the trajectory {s j t , a j t } j , where s j t , a j t denotes the state-action pair reached after j steps when following π k from s t , and when we consider s t k to be absorbing, that is s j t is set to s t k for all j j 0 where j 0 is the first (random) time when

s j t = s t k . Now, since it holds that Q k (s t k , a t k ) -Q k -(s t k , a t k ) =
0 by construction, the term on the second line in (15) vanishes when π k reaches s t k , which in the worst case happens after no more than T t steps on average over the trajectory {s j t , a j t } j . Thus, we deduce that

Q k (s t , a t ) -Q k -(s t , a t ) 2C p k,t c 1 + 1 ε D k E[j 0 ] 2C p k,t c 1 + 1 ε D k T t .
Now, using the assumption that T t D k again, we obtain

T - t = -Q k -(s t , a t ) + Q k (s t , a t ) -Q k (s t , a t ) 2C p k,t c 1 + 1 ε D k T t + T t D k 1 + 2C p k,t c 1 + 1 ε D k ,
which concludes the proof of Lemma 14.

Number of episodes

To conclude this section of preliminary results, let us get a bound on on the number of episodes. Since the episodes stop only because of a doubling event, that is precisely as for UCRL we trivially have from [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] the following standard control of the number of episodes Lemma 15 The total number of episodes is bounded as in [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] by

K T SA log 2 8T SA . ( 16
)

Dealing with non-irreversible actions

The control of the cumulated reward of A-ROGUE proceeds backward from the last to the first episodes. We first start in this section by handling what happens during the lasts episodes k > k following the last entrance to a region S i . Then, we progressively unfold the control back to the first episode in the next sections. Since we want to apply Lemma 13, we accept to control the regret only up to T = T -c(1

+ 1 ε )D K T at the price of loosing only a regret of c(1 + 1 ε )D K T .
For notational convenience however, we slightly abuse of notation and state all sequel results and proofs until section 5.6 with horizon T while they hold for T instead.

We first show the following result, discarding what happens due to irreversible actions.

Lemma 16

The regret between the strategy used by A-ROGUE from time t k+1 (where it is in state s t k+1 ), and an optimal strategy starting at the same time in the same state, is

E R π M ( k>k T (k) |s t k+1 ) - k=k R A M ,k E K T -1 k=k+1 τ + (s t k+1 , s + t k+1 ) + τ π (s t k+1 , s t k ) + τ π (s t k , s t k+1 ) + E K T k=k+1 |T R (k) | -E K T -1 k=k+1 (23) k + (30) k -(17) ,
where all quantities are introduced in Sections 5.2.1-5.2.4.

The proof is in several steps that are detailed below (Section 5.2.1) In all these steps, we assume that K T > k (otherwise the sums are trivial).

First step decomposition

Let us start with what happens for one episode k > k. We have

E R A M ,k = E R π k M (T D (k) |s t k ) -R π k M + k (T D (k) |s t k ) (17) + E R π k M + k (T D (k) |s t k ) -R π k M + k (T (k) |s t k ) (18) + E R π k M + k (T (k) |s t k ) . ( 19
)
In this first step, we apply this decomposition specially to k = K T , for which

T (K T ) = [t K T : T ].
We handle (19) by noting that since π K T is the optimistic policy computed in episode K T , in satisfies that

(19) E R π M ([t K T : T ]|s t K T ) .
Since the rewards are bounded in [0, 1], it holds that

(18) -E |T (K T ) \ T D (K T ) | = -E |T R (K T ) | .
Thus, so far, combining these three equations together, we have shown that

E R A M ,K T E R π M ([t K T : T ]|s t K T ) + (17) -E |T R (K T ) | . (20)

Preparing the unfolding step

Equation ( 20) relates the reward accumulated by the algorithm to that of a trajectory of an optimal policy starting from s t K T , until the final time T . We now use this in order to progressively compare to the optimal policy starting from s t K T -1 until time T , then from s t K T -2 and so on, proceeding backward in the episodes, until comparing to the optimal policy starting from s t k+1 up to time T . An important property that we use in the following is that for all episodes k > k, by definition, the algorithm stays in the same region S i , from t k+1 until the final time T .

Considering that K T -1 > k for the sake of showing how works the decomposition in the general case (some terms simplify if K T k + 1), we proceed as follows

E k>k R A M ,k = E K T -2 k=k+1 R A M ,k + R A M ,K T -1 + R A M ,K T (21) E K T -2 k=k+1 R A M ,k + (17) -E |T R (K T ) | +E R π K T -1 M (T D (K T -1) |s t K T -1 ) + R π M ([t K T : T ]|s t K T ) , (22)
where for the first inequality, we applied (20) to control R A M ,K T -1 as well as the definition of R A M ,K T -1 . Now, in order to control ( 22), we use the following decomposition

(22) E R π K T -1 M (T D (K T -1) |s t K T -1 ) -R π K T -1 M + K T -1 (T D (K T -1) |s t K T -1 ) (23) + E R π K T -1 M + K T -1 (T D (K T -1) |s t K T -1 ) -R π M (T D (K T -1) |s t K T -1 ) (24) + E R π M (T (K T -1) |s t K T -1 ) -E T R (K T -1) + E R π M ([t K T : T ]|s t K T ) , (25)
where we used ni the last line the fact that rewards are in [0, 1]. Then, we use the fact that π is optimal in order to control the last term of ( 25)

E R π M ([t K T : T ]|s t K T ) E R π M ([t K T : t K T + τ -1]|s t K T ) +R π M ([t K T + τ : t K T + τ + τ -1]|s t K T -1 ) +R π K T -1 M ([t K T + τ + τ : T ]|s t K T ) . ( 26
)
Here we first introduced the policy π that goes from s t K T back to the state s t K T -1 visited at time t K T -1 as fast as possible and the random time τ = τ π (s t K T , s t K T -1 ) ∈ N to reach it using this policy. Let us remind that for states s, s ∈ S and some policy π, τ π (s, s ) denotes the random time corresponding to the first visit to state s when following policy π from state s (in the current MDP). Then we introduced the state s t K T that would have been reached at time t K T by the optimal policy π started at state s t K T -1 and time t K T -1 . We also introduced the policy π that goes from s t K T -1 to s t K T visited at time t K T -1 as fast as possible, together with its random time τ = τ π (s

t K T -1 , s t K T
). In the last term of equation ( 26), we denoted π K T -1 to insist on the fact that we use the optimal policy π started from state s t K T -1 at time t K T -1 , that we follow from state s t K T

(at the time it is reached) up to time T . Indeed, this is a priori different from the optimal policy that starts from s t K T at time t K T + τ + τ .

Regarding (26), since the rewards are all positive, on the one hand we have

R π M ([t K T : t K T + τ -1]|s t K T ) + R π M ([t K T + τ : t K T + τ + τ -1]|s t K T -1 ) 0 ,
and on the other hand, it holds that

E R π K T -1 M ([t K T + τ + τ : T ]|s t K T ) E R π K T -1 M ([t K T : T ]|s t K T ) -E τ + τ .
Thus, we deduce that ( 22) is bounded by ( 22) ( 23) + ( 24) 23) + ( 24)

-E τ + τ +E R π M ([t K T -1 : t K T -1]|s t K T -1 ) + E R π K T -1 M ([t K T : T ]|s t K T ) = (
-E τ + τ + E R π M ([t K T -1 : T ]|s t K T -1 ) ,
where we used the definition of π K T -1 and s t K T in the second line. Plugging in this back to the first step of this section, we deduce that

E k>k R A M ,k E K T -2 k=k+1 R A M ,k + E R π M ([t K T -1 : T ]|s t K T -1 ) (27)
+( 17)

-E |T R (K T -1) | -E |T R (K T ) | +(23) K T -1 + (24) K T -1 -E τ π (s t K T , s t K T -1 ) + τ π (s t K T -1 , s t K T ) ,
where we put the index of the episode in subscript of the equations for clarity purpose. The next step is now to handle the term (24) K T -1 , and more generally (24) k for k > k.

Optimistic model

We now control, for k > k, the quantity

(24) k = E R π k M + k (T D (k) |s t k ) -R π M (T D (k) |s t k ) .
For that purpose, we use that π k is the optimal policy for model M + k with horizon T , and reason trajectory wise (that is, following a random trajectory from the policy, as opposed for instance to a distribution of states). Thus, it holds that

E R π k M + k ([t k : T ]|s t k ) max π E R π M + k ([t k : T ]|s t k ) E R π M + k (T D (k) |s t k ) +R π M + k ([t D k : t D k + τ + (s t D k , s + t D k ) -1]|s t D k ) +R π k M + k ([t D k + τ + (s t D k , s + ) : T ]|s + t D k ) E R π M + k (T D (k) |s t k ) + E R π k M + k ([t D k : T ]|s + t D k ) -E τ + (s t D k , s + t D k ) , (28)
where we introduced st

, s + t D k ) to go from st D k to s + t D k
in the augmented MDP M + k . Thus, since on the other hand, we have the decomposition

E R π k M + k ([t k : T ]|s t k ) = E R π k M + k (T D (k) |s t k ) + E R π k M + k ([t D k : T ]|s + t D k
) ,

we deduce from (28) the following bound

(24) k -E τ + (s t k+1 , s + t k+1 ) + E R π M + k (T D (k) |s t k ) -R π M (T D (k) |s t k ) . (29)
For convenience, let us number the second term that appears in the right hand side of this inequality;

E R π M + k (T D (k) |s t k ) -R π M (T D (k) |s t k ) (30)
Plugging (29) back into ( 27), so far we have proved that

E k>k R A M ,k E K T -2 k=k+1 R A M ,k + E R π M ([t K T -1 : T ]|s t K T -1 ) + (17) (31)
+(23) K T -1 + (30) K T -1 -E |T R (K T -1) | -E |T R (K T ) | -E τ + (s t K T , s + t K T ) + τ π (s t K T , s t K T -1 ) + τ π (s t K T -1 , s t K T ) ,
Now, it is not difficult to see that ( 17), (23) K T -1 and (30) K T -1 are similar. Indeed, we have

(23) k = E R π k M (T D (k) |s t k ) -R π k M + k (T D (k) |s t k ) , ( 30
) k = E R π M + k (T D (k) |s t k ) -R π M (T D (k) |s t k ) , (17) = E R π K T M (T D (K T ) |s t K T ) -R π K T M + K T (T D (K T ) |s t K T ) = (23) K T .

Unfolding step within one region

Now, one can recognize in the first two terms of equation ( 31), the exact same form as what happens in equation ( 22). Indeed, it holds (provided that

K T -2 k + 1) that E K T -2 k=k+1 R A M ,k + E R π M ([t K T -1 : T ]|s t K T -1 ) = E K T -3 k=k+1 R A M ,k +E R π K T -2 M (T (K T -2) |s t K T -2 ) + R π M ([t K T -1 : T ]|s t K T -1 ) .
and we recognize in the last line equation ( 22) for episode K T -1 instead of K T . Thus, we use the same decomposition ( 22)-( 30)

using k = K T -1, K T -2, etc. up to k = k + 1
, and we deduce that

E k>k R A M ,k E R π M ([t k+1 : T ]|s t k+1 ) + E K T k=k+1 |T R (k) | +E K T -1 k=k+1 (23) k + (30) k + (23) K T -E K T -1 k=k+1 τ + (s t k+1 , s + t k+1 ) + τ π (s t k+1 , s t k ) + τ π (s t k , s t k+1 ) ,
That is, reorganizing the terms, we deduce that

E R π M ( k>k T (k) |s t k+1 ) - k=k R A M ,k E K T -1 k=k+1 τ + (s t k+1 , s + t k+1 ) + τ π (s t k+1 , s t k ) + τ π (s t k , s t k+1 ) +E K T k=k+1 |T R (k) | -E K T -1 k=k+1 (23) k + (30) k -(23) K T .

Continuing the unfolding step

A-ROGUE stays in the same region during all the episodes k > k. Now, the episodes can be decomposed into two categories. Those during which the A-ROGUE stays in the same region, and those during which A-ROGUE plays an action that leads to another region (than the one at the starting time of that episode). We use a generic index k for the first category, and k for the second category. It is natural to first look at episode k = k where the last change of region occurs, before continuing backwards up to the first episode.

When entering a different region, the return time suddenly becomes large, and thus the term τ π (s t k+1 , s t k ) may not be controlled anymore. To handle this difficulty, we use a slightly different decomposition than the one used for the proof of Lemma 16. We introduce t k ∈ [t k , t k+1 ) that corresponds to the time when A-ROGUE plays an irreversible action in episode k. Further let us split T (k) = T (k),1 ∪ T (k),2 in two parts first corresponding to time-steps between t k and t k + 1 (excluded) and second to time-steps between t k + 1 (included) and t k+1 . Likewise, we introduce

T D (k),1 , T D (k),2 , T R (k),1 and T R (k),2
. Decomposing the regret before and after the time t k is intuitively equivalent to introducing an additional episode starting at t k (with the difference that t k is unknown to the algorithm).

We start with k = k and handle the regret in [t k , T ] by applying the steps of Lemma 16 but replacing t k with t k . That is, it holds

E R π M (T (k),2 ∪ k>k T (k) |s t k +1 ) -R π k M (T (k),2 |s t k +1 ) - k=k R A M ,k E τ + (s t k+1 , s + t k+1 ) + τ π (s t k+1 , s t k +1 ) + τ π (s t k +1 , s t k+1 ) +E K T -1 k=k+1 τ + (s t k+1 , s + t k+1 ) + τ π (s t k+1 , s t k ) + τ π (s t k , s t k+1 ) + E |T R (k),2 | + K T k=k+1 |T R (k) | -(23) K T -E (23) k,2 + (30) k,2 + K T -1 k=k+1 (23) k + (30) k , where (23) k,2 is similar to (23) k except is uses T D (k),2 instead of T D (k)
, and likewise (30) k,2 is similar to (30) k in the same way. That is:

(23) k,2 = E R π k M (T D (k),2 )|s t k +1 ) -R π k M + k (T D (k),2 )|s t k +1 ) (30) k,2 = E R π M + k (T D (k),2 )|s t k +1 ) -R π M (T D (k),2 )|s t k +1
) . We focus on time t k when A-ROGUE plays an irreversible action. Note that the action played must pass either the test of line 10 or of line 13. Under the event Ω, by Lemma 14, if the action passes the test of line 10, then it is not irreversible, thus the action must pass the test of line 13, and is thus d -optimal by Lemma 12, that is , it holds

E R a t M ([t : t + 1]|s t ) + R π t+1 M ([t + 1 : T ]|s t+1 ) E R π t M ([t : T ]|s t ) -d . (32)
Now, assuming this was the only irreversible action played during the episode k, we can handle the regret on previous steps of the episode T (k),1 \{t k } using a similar decomposition as that for Lemma 16. More generally, if m k denotes the number of irreversible actions played A-ROGUE in episode k, at times {t k,m } m∈[m k ] , then by equation ( 32), the regret during episode an k looses at most m k d compared to an episode k > k (for which m k = 0). More formally, using for convenience the convention t k,m k +1 def = t k+1 and t k,0

def = t k -1, then we have proved that Lemma 17 (Main Decomposition) The regret of A-ROGUE is bounded as E R T = E R π M ( K T k=1 T (k) |s t k ) - K T k=1 R A M ,k E K T k=1 m k d + E K T k=1 m k +1 m=1 τ + (s t k,m , s + t k,m ) + τ π (s t k,m , s t k,m-1 +1 ) + τ π (s t k,m-1 +1 , s t k,m +E K T k=1 |T R (k) | -E K T k=1 m k +1 m=1 (23) k,m + (30) k,m , (33)
where, introducing the sets

T (k),m = [t k,m-1 + 1 : t k,m ] (with corresponding T D (k),m , T R (k),m ) (23) k,m = E R π k M (T D (k),m )|s t k,m-1 +1 ) -R π k M + k (T D (k),m )|s t k,m-1 +1 ) (30) k,m = E R π M + k (T D (k),m )|s t k,m-1 +1 ) -R π M (T D (k),m )|s t k,m-1 +1 ) .
Note that equation ( 33) handles the general case, without assuming that k

< K T . Also R π M ( K T k=1 T (k) |s t k ) = R π M (T|s 1
) is the reward accumulated by an optimal policy π from the initial state s 1 between time 1 and T . Thus this lemma successfully enables us to compare our strategy to the optimal policy, and not simply, for instance, to a local optimal action. Now, note that controlling the term E

K T k=1 |T R (k)
| is a priori not trivial: Indeed, at time t when A-ROGUE plays an irreversible action might a priori not be close to the time t when the optimal policy plays an irreversible action, since the algorithm must decide that it is "good" to play an irreversible action and this may require many roll-outs. That is, in case t k t t k +1 t k t for some episode k < k, the optimal policy enters a region earlier than A-ROGUE, and A-ROGUE may incur a linear regret between t and t for not entering an optimal region. We control the number of roll-outs in Section 5.5 and show that A-ROGUE does not incur too much regret due to this phenomenon.

Bounding the number of irreversible actions We now bound m = K T k=1 m k . First of all, if all regions except the initial one kS i 0 are not escapable with probability 1, then we simply have E md 1. In the other cases let us note that it must take at time t at least max{γ (T -t) -2d , d } steps on average to get from one region of the partition to a neighboring one. Thus in the worst case, we cannot cross more than m times on average, where m satisfies m i=1 (γ d i -2d ) T : Indeed, let t i be the i-th time when a crossing occurs. Since the last (m-th) time, at least d steps are required to transit between regions, we deduce that T -t m d on average. Likewise, applying this argument backward from m to i, we get T -t i (m -i + 1)d , and thus γ (T -t i ) -2d γ (m -i + 1)d -2d . We then deduce the (rough) bound γ d m 2 + (γ -4)d m 2T from which it follows that

E md 2T d γ + (4 -γ ) 2 d 2 4γ 2 + (4 -γ )d 2γ 2T d γ + 4d 2 γ 2 + 2d γ 2 2d γ T + 2d γ . ( 34
)

Bellman equation and local diameter

In this section, we control the terms (17), ( 23) k and (30) k , by resorting to the Bellman propagation equation as well as the definition of the confidence sets used by the A-ROGUE algorithm. Then, we make use of the local diameter d to handle the τ terms appearing in Lemma 16. We exhibit in particular the role of the assumption k > k and of the diameter of the local region S i , as well as of the computation of the return time by the algorithm.

Bellman Propagation equation

For any MDP M = (r M , p M ), and horizon h ∈ N it holds from the Bellman propagation equation that

E[R π M ([t : t + h -1] ∩ T D (k) |s t )] = E r M (s t , π(s t )) + s p M (s |s t , π(s t ))E[R π M ([t + 1 : t + h -1] ∩ T D (k) |s )] . (35)
Now let us focus on (23) k , for k > k. If we denote the episode length to be

h k = t k+1 -t k , we note that [t k + 1 : t k + h -1] ∩ T D (k) = T D (k) \ {t k },
and deduce by applying (35) to the two terms of (23

) k that (23) k = E µ(s t k , a t k ) + s p(s |s t k , a t k )E[R π k M (T D (k) \ {t k }|s )] -r M + k (s t k , a t k ) - s ∈S p M + k (s |s t k , a t k )E[R π k M + k (T D (k) \ {t k }|s )] ,
where

M + k = (r M + k , p M + k
) is the augmented MDP and M = (µ, p) the true MDP. Regrouping the terms to make appear the estimation error of the reward function and transition kernel, we obtain

(23) k = E µ(s t k , a t k ) -r M + k (s t k , a t k ) + s ∈S p M + k (s |s t k , a t k )-p(s |s t k , a t k ) E[R π k M + k (T D (k) \ {t k }|s )] + s ∈S p(s |s t k , a t k )E R π k M + k (T D (k) \ {t k }|s )-R π k M (T D (k) \ {t k }|s ) , (36)
where in the last line, the difference can be decomposed iteratively in the same way. Now, note that, in the second line, since p M + k and p both sum to 1, one can replace

V + T D (k) \{t k } (s ) def = E[R π k M + k (T D (k) \ {t k }|s )] by V + T D (k) \{t k } (s ) -c for any constant c.
In particular, if we introduce sp(f ) = max s∈S f (s) -min s∈S f (s), then for a specific choice of c we get

V + T D (k) \{t k } (s ) -c sp(V + T D (k) \{t k } )/2
. Now, a standard way to get a bound on (23) k is by unfolding the above equality, reorganizing the resulting terms according to each state-action pair and bounding the probability to reach a specific state-action pair in less than t k+1 -t k steps by 1. This leads to the bound

t∈T (k) sp(V + [t+1:t k+1 -1]∩T D (k) ) 2 ,
where we introduced the total number of visits in episode k (including roll-out transitions)

v k (s, a) = t∈T (k) I{s t = s, a t = a} . (37)
Note that we can proceed in the exact same way in order to derive a bound on (30) k by replacing π k with π , and on ( 17) by replacing T D (k) with T D (K T ) .

Span to Local span

However, apart from the special case when there is only one region S i , there is in general no reason that the term max

t∈T (k) sp(V + [t+1:t k+1 -1]∩T D (k)
) be small. Indeed, when it is not possible to reach a common state from two different states, their value can be arbitrarily different. Thus, we proceed with a different decomposition, that we detail in the next paragraph.

The second line of (36) satisfies the following, for t = t k and all c ∈ R:

E s ∈S p M + k (s |s t , a t )-p(s |s t , a t ) V + [t+1:t k+1 -1]∩T D (k) (s ) E s ∈S:p(s |st,at)>0 p M + k (s |s t , a t )-p(s |s t , a t ) V + [t+1:t k+1 -1]∩T D (k) (s ) -E ||p M + k (•|s t , a t ) -p(•|s t , a t )|| 1 max s ∈S:p(s |st,at)>0 V + [t+1:t k+1 -1]∩T D (k) (s ) -c ,
where we used the fact that the value is non negative. Thus, we can restrict our attention to the set S t = {s ∈ S : p(s |s t , a t ) > 0} ⊂ S.

By choosing c = 1 2 max s ∈St V + [t+1:t k+1 -1]∩T D (k) (s )+ min s ∈St V + [t+1:t k+1 -1]∩T D (k)
(s ) , and using the notation sp S (f ) = max S f -min S f , we get

E s ∈S p M + k (s |s t , a t )-p(s |s t , a t ) V + [t+1:t k+1 -1]∩T D (k) (s ) -E ||p M + k (•|s t , a t ) -p(•|s t , a t )|| 1 1 2 sp St (V + [t+1:t k+1 -1]∩T D (k)
) .

Thus, the main difference compared to the standard derivation is that we get sp

St (V + [t+1:t k+1 -1]∩T D (k) ) instead of sp(V + [t+1:t k+1 -1]∩T D (k)
). Proceeding now with the usual next steps that consist in rewriting the sums to make appear the number of visits to each state action pair, we thus get the following bounds:

Lemma 18 For all k > k, it holds that

(23) k = E R π k M (T D (k) |s t k ) -R π k M + k (T D (k) |s t k ) -E (s,a)∈S×A v k (s, a)|r M + k (s, a) -µ(s, a)| + (s,a)∈S×A v k (s, a) p M + k (•|s, a) -p(•|s, a) 1 max t∈T (k) sp St (V + [t+1:t k+1 -1]∩T D (k) ) 2 . where V + [t+1:t k+1 -1]∩T D (k) def = E[R π k M + k ([t + 1 : t k+1 -1] ∩ T D (k) |•)]. (30) k = E R π M + k (T D (k) |s t k ) -R π M (T D (k) |s t k ) -E (s,a)∈S×A v k (s, a)|r M + k (s, a) -µ(s, a)| + (s,a)∈S×A v k (s, a) p M + k (•|s, a) -p(•|s, a) 1 max t∈T (k) sp St (V +, [t+1:t k+1 -1]∩T D (k) ) 2 , where V +, [t+1:t k+1 -1]∩T D (k) def = E[R π M + k ([t + 1 : t k+1 -1] ∩ T D (k) |•)].
The result of Lemma 18 shows that actually only the difference of values between two possible successor states of a visited state (under M ) matters, and not between two arbitrary states: This is especially important in the setting of multi-chain MDPs.

Diameter and local diameter

First, let us bound the quantity τ π (s t k,m , s t k,m-1 +1 ). By construction, all actions that have been played on the path from state s t k,m-1 +1 to state s t k,m stay in the same region. Thus, s t k,m-1 +1 and s t k,m belong to the same region, and thus it holds

E τ π (s t k,m , s t k,m-1 +1 ) d . (38)
Second, let us focus on τ π (s t k,m-1 +1 , s t k,m ). In order that s t k,m ∈ S j is reached by the optimal policy from state s t k,m-1 +1 ∈ S i (with possibly i = j), then it must be that p(S j |S i ) > 0. Thus, by assumption 1, at least one state-action pair (s, a) in the region S i satisfies p(S j |s, a) p 0 without risking entering a third region. Now, it requires at most d steps on average to reach s from a point in S i , and thus at most d /p 0 steps to enter S j . On the other hand, it requires at most d steps in S i to reach this point from s t k,m-1 +1 , and then at most d steps in S j to reach s t k,m from a successor of s in S j . Thus, we deduce that:

E τ π (s t k,m-1 +1 , s t k,m ) (2 + 1 p 0 )d . (39)
Third, let us focus on the span of the optimistic value, restricted to successor states of the visited states. Once again by construction, all actions that have been played on the path {(s t , a t )} t∈T D (k),m from state s t k,m-1 +1 to state s t k,m stay in the same region (say S i ) and thus satisfy T (s t , a t ; s 0 ) d for some state s 0 ∈ S i . For any successor state s = s 0 , we must then have 1 + p(s |s t , a t )T (s ; s 0 ) T (s t , a t ; s 0 ) d , and thus T (s ; s 0 ) d -1 p min , assuming that all transitions happen with probability either 0 or at least p min > 0. Now, the expected value of π in state s must be at least the value in state s 0 plus the value on the way to reach it (by optimality in M ):

V + t (s ) E V + [t:t+τ (s ,s 0 )-1] (s ) + V + t+τ (s ,s 0 ) (s 0 ) E V + t+τ (s ,s 0 ) (s 0 ) ,
where the expectation is over the random variable τ (s , s 0 ) ∈ N. Likewise, V + t (s ) can be upper bounded by

E V + t-τ (s 0 ,s ) (s 0 ) E V + [t-τ (s 0 ,s ):t-1] (s 0 ) + V + t (s ) V + t (s ) .
Thus, we deduce that for any successor s , s of (s t , a t ) it holds

V + t (s ) -V + t (s ) E V + t-τ (s 0 ,s ) (s 0 ) -V + t+τ (s ,s 0 ) (s 0 ) E τ (s 0 , s ) + τ (s , s 0 ) (2 + 1 p 0 )d + d -1 p min .
Thus, the span restricted on S t is not greater than 2 + 1 p 0 + 1 p min d . Following [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF], the same argument applies to the span of the optimistic value (following the optimistic policy) as well, since the augmented MDP contains at least the transitions of the true MDP, provided that M is plausible. Thus, on the event Ω that M is plausible, it holds max

t∈T (k),m sp St (V + [t+1:t k+1 -1]∩T D (k),m ) 2 + 1 p 0 + 1 p min d . (40)
Now since the optimistic value of π in state s is larger than the optimal value of π , which must be at least the value in state s 0 plus the value on the way to reach it, we can follow a similar argument to show that: max

t∈T (k),m sp St (V +, [t+1:t k+1 -1]∩T D (k),m ) 2 + 1 p 0 + 1 p min d . (41)
Finally, we focus on the term τ + (s t k,m , s + t k,m ) that correspond to a shortest visit time when navigating in the augmented MDP M + k . The fact that the algorithm does not execute irreversible actions in M between time t k,m-1 + 1 and t k,m does not discard, a priori, the possibility that an optimal policy π started from s t k,m-1 +1 executes actions that are irreversible in the MDP M + k . Put differently, the time to go τ + (s t k,m , s t k,m-1 +1 ) from st k,m back to s t k,m-1 +1 in M + k may be huge if s t k,m-1 +1 ∈ S i and π enters a different region S j when acting in M + k during T (k),m . Note that if during T (k),m , π stays in the same region in M , then since A-ROGUE does the same, the expected time to reach the state reached by A-ROGUE from the one reached by π is bounded by d . Since times are shorten in the augmented MDP, τ + (s t k,m , s + t k,m ) d in this case. Thus, we deduce the following bound that holds when π stays in the same region on T (k),m :

τ + (s t k,m , s + t k,m ) d . ( 42
)
Now the regret for not entering an optimal region is due to lack of observations in this region, and possibly in the current region as well. Lemma 20 proves a worst-case bound that handles not only the maximum number of roll-outs asked by the A-ROGUE before it can decide to play an irreversible action, but actually the number of samples (not only coming from roll-outs) so that every reachable state is well estimated: If A-ROGUE acts in the MDP and gathers information, then it may require less roll-outs. Thus, this enables to capture the maximum regret due to not making an irreversible action when π does. That is, the regret due to the case when π enters another region in M but A-ROGUE does not can be handled by the bound on the total number of roll-out transitions from Lemma 20, and thus we can simply use the same bound.

Combining ( 42), ( 38) and (39) together, and slightly abusing notations (the following only applies to (k, m) such that π stays in the same region on T (k),m ), we deduce that

E Ω K T k=1 m k +1 m=1 τ + (s t k,m , s + t k,m ) + τ π (s t k,m , s t k,m-1 +1 ) + τ π (s t k,m-1 +1 , s t k,m E Ω K T k=1 (m k + 1) 4 + 1 p 0 d 4 + 1 p 0 E md + K T d .
Combining the result Lemma 18 with equations ( 40) and ( 41) we get an upper bound that can be extended to all episodes. Then, plugging this in the decomposition of the regret from Lemma 17 and continuing the unfolding steps, we deduce the following Corollary 19 Let us introduce the constant c p def = 2 + 1 p 0 + 1 p min . Then, it holds that

E Ω R T E[md ] + 4 + 1 p 0 E md + K T d + E K T k =1 |T R k |I{Ω} +3E Ω K T k =k (s,a)∈S×A v k (s, a) r M + k (s, a) -µ(s, a) + (s,a)∈S×A v k (s, a) p M + k (•|s, a) -p(•|s, a) 1 c p d ,
where m denotes the total number of actions played by A-ROGUE that exit the current region.

Cumulative estimation error

We can combine the confidence bounds ( 5) and ( 6) together with the cumulative estimation error over K episodes (the expectation term in the last term of (??)) and obtain by Lemma 5 that on an event Ω of probability higher than 1 -2δ/T , it is controlled as

K T k =1 (s,a)∈S×A v k (s, a) r M + k (s, a) -µ(s, a) + (s,a)∈S×A v k (s, a) p M + k (•|s, a)-p(•|s, a) 1 c p d 2 log(2 S/2+1 AST 2 /δ)c p d K T k =1 (s,a)∈S×A v k (s, a)N -1/2 t k (s, a) 2 log(2 S/2+1 AST 2 /δ)c p d ( √ 2+1) √ SAT , (43)
where we used in the second inequality the fact that v k (s, a) N t k (s, a) due to the criterion used for stopping episodes, together with an application of equation ( 20) from [START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] that uses Jensen's inequality, namely

K T k =1 (s,a)∈S×A v k (s, a) N t k (s, a) ( √ 2 + 1) √ SAT .
We now combine ( 43) and (34) together with (33), reorganize the terms and use the control on K T from Lemma 15, and obtain that the regret is controlled on an event Ω of high probability by

E Ω R T 5 + 1 p 0 2 2d γ T + 2d γ + 4 + 1 p 0 d SA log 2 8T SA +E K T k =1 |T R k |I{Ω} + 6 log(2 S/2+1 AST 2 /δ)c p d ( √ 2+1) √ SAT . ( 44
)
The notation E Ω has been introduced in section 5.1.2. Once again, we slightly abuse the notations, as here in

E K T k =1 |T R k |I{Ω}
we incorporate the episodes such that π exists the current region.

Total number of roll-outs

In this section, our goal is to control the cumulative sum of roll-out transitions K T k=1 |T R k | that remains to be controlled. Note that A-ROGUE stops asking for new roll-out at a time t such that at each time step t t, at least one of the test of Line 10 and of Line 13 is passed. We study these two tests in order to derive a round on the total number of roll-out transitions. We will show that Lemma 20 Under the assumption that the parameter ε <

1 of A-ROGUE is chosen such that ε < min p 0 d 1 + p 0 + d , p 0 1 + p 0 ,
and if Ω denotes the event that M is plausible for in all episodes, then it holds that

E K T k=1 |T R k |I{Ω} 16S (1 + ε) 3 γ 2 ε 2 (1 -ε) log(2 S+1 SAT 2 /δ)E k:D k-1 d D 2 k .
Part of this bound is obtained by computing the number of roll-outs executed from the initial region S i 0 to cover the entire state-space sufficiently often. Actually the same bound when adding to the number of roll-outs the regret in episodes such that π exists the current region. The proof is divided in several steps:

Number of roll-outs and covering times: Our goal is to control the number of roll-outs needed before we can ensure that in each state s t , the pessimistic return time satisfies T - t 2D k when T t D k . By the bound (12) of Lemma 14 in Section (5.1.4), this is linked to the number of times each state-action pair (s, a) with s ∈ S(s t , D k ) is visited in total, where S(s, ) is the set of all states that are reachable from s in steps. Thus let s be a state reachable in d steps from s t , and let us call a roll-out with maximal number of steps bounded by d a d-roll-out. We introduce p π,d s t ,s , the probability that visiting s for the first time, starting from s t and following policy π after playing a t takes no more than d steps (in total). It is not difficult to show that this probability is given by

p π,d s t ,s = δ s t P a t + d-2 j=0 P a t L,-s P π -s j P π R,-s δ s ,
where P a t L,-s (respectively P π R,-s ) is the S -1 × S transition matrix (S × S -1) induced by action a t (policy π) with line (row) corresponding to state s removed, and δ s is the S vector with values 1 for state s and 0 else. Note that it also means that with one d-roll-out of a policy π, s ∈ S(s t , d) is visited at least p π,d s t ,s times on average. Thus, we deduce that no more than n/p

d = (1 + 1 ε )D k in episode k. Note that 2C p k,t c 1 + 1 ε D k α happens (α = 1
is used in the recovery test l.10) as soon as all corresponding state-action pairs are visited at least

n 0 = 2c 2 1 + 1 ε 2 D 2 k α 2 log(2 S+1 SAT 2 /δ)
k - n(D k ) def = 2c 2 1 + 1 ε 3 D 3 k S(s t , 1 + 1 ε D k ) β α 2 log(2 S+1 SAT 2 /δ) .
Known and unknown local diameter Before determining β, let us discuss the guessed diameter D k a little bit. In case an upper bound D on the diameter d is known in advance D k = D, and thus at most n(D) many roll-out transitions from π k -are observed before the test of line 10 is passed for all states with T t D. Now, when no upper bound on the diameter d is known in advance and D k < d , that is the guessed diameter is smaller than the true local diameter, the states in S(s t , d )\S(s t , D k ) may not be visited often enough, and thus one cannot ensure accurate estimation. Since D k = log(t k ) increases with episodes, we eventually get to visit states reachable in S(s t , d ).

However visiting the D k+1 -reachable states may require to revisit all the D k reachable states as well and not only the frontier of this set (and this is reward consuming). In all cases, states are visited enough after the total number of roll-out transitions from π k -, k 1 is at most

k:D k d n(D k ) + n(D k) = k:D k-1 d n(D k ) , on
T π k -(s t , s) = ∞ d=0 p π k -,d s t ,s -p π k -,d-1 s t ,s d ∞ d> (1+ 1 ε )D k p π k -,d s t ,s -p π k -,d-1 s t ,s 1+1/ε D k +1 1 -p π k -, (1+ 1 ε )D k s t ,s 1 + 1 ε D k , (45)
where in the first inequality we used the fact that p π k -,d s t ,s is a not decreasing function of d, and in the second one a telescoping argument. Combining (45) together with T π k -(s t , s) (1 + α)D k and reorganizing the terms, we deduce that

p π k -, (1+ 1 ε )D k s t ,s (1 + 1 ε )D k -D k (1 + α) (1 + 1 ε )D k = 1 -αε 1 + ε ,
which means that, provided that αε < 1, we can use β = 1+ε 1-αε . Finally, A-ROGUE alternates between roll-outs of the optimistic policy π + k and rollouts of the pessimistic backup policy π k -. We focused here on controlling the number transitions generated by π k -only (at the price of losing a factor 2). More precisely, since the roll-outs from π + k and from π k -are of the same size and we alternate at every roll-out, by discarding the transitions received using π + k (as non-informative in the worst case) we at most double the number of transitions needed before the condition on the pessimistic return time is satisfied. Thus, we deduce that the backup time is accurately estimated when the total number of transitions

K T k=1 |T R k | is at most N (d ) def = 4 1 + ε 1 -αε c 2 1 + 1 ε 3 α 2 log(2 S+1 SAT 2 /δ) k:D k-1 d D 3 k S(s t , (1 + 1/ε)D k ) . (46)
Thus, far, we have seen that after this number of transitions on average has been observed for all visited states, every return time following an action that is not irreversible is well estimated, and thus no roll-out is asked for these states, that is, roll-out transitions may only be asked in case the optimistic action is irreversible.

Sub-optimality test The set s∈S i 0 S(s, (1 + 1/ε)D k ) covers the entire state space S if it is possible to reach any state from S i 0 is no more than (1 + 1/ε)D k steps. Since from the boundary of a region, we need no more than d + d /p 0 steps to enter the region and then d to reach any state inside the region, this requires at most (2 + 1 p 0 )d steps, and thus, we want condition on ε so that (1

+ 1 ε )D k (2 + 1 p 0 )d . If D k d
, then this inequality holds for ε p 0 1+p 0 . In this case, for the previous number of roll-out transitions (46), we deduce that each state-action pair is visited at least n 0 times and thus it holds

C p k ∞ α 2c(1 + 1 ε )D k . ( 47
)
This of course provides a control on C µ k ∞ as well (simply look at the expression for both terms). Now, we want to ensure that (8) holds so that a d optimal action does pass the test of line 13. Indeed in this case, no more roll-out is asked by A-ROGUE. Using (47) in order to control both C p k ∞ and C µ k ∞ , and reorganizing the terms, we obtain the inequality

C µ k ∞ + 2 + 1 p 0 d C p k ∞ α 2c(1 + 1 ε )D k 2 + 1 p 0 d + log(2AST 2 /δ) log(2 S+1 AST 2 /δ) .
As a result, the condition (11) for a d -optimal action to pass the sub-optimality test of A-ROGUE is satisfied when D k d , ε since α = 1 and c = 2 γ , then this simplifies to

1 1 + 1 ε 2 + 1 p 0 + 1 d that is ε 1 1 + 1/p 0 + 1/d . (48)
Thus, we deduce that for the choice ε min p 0 d p 0 d + p 0 + d , p 0 1 + p 0 , then after at most N (d ) roll-out transitions asked by A-ROGUE for the episodes such that k such that D k d , the recovering time is well-estimated and d -optimal actions do pass the test of line 13, that is at least one of the tests of line 10 and line 13 is passed. Thus the total number of roll-out transitions asked by the algorithm is upper-bounded by (let us remind that δ is also a parameter of the algorithm)

E K T k=1 |T R k |I{Ω} 4S (1 + ε) 4 ε 3 (1 -ε) c 2 log(2 S+1 SAT 2 /δ)E k:D k-1 d D 3 k .
This concludes the proof of Lemma 20.

Upper bound on the regret

We now bound the regret of the A-ROGUE first in the case when the diameter d is unknown, and then in the case an upper bound D d is known. We remind that the algorithm uses c = 2/γ for the scaling of the planning horizon of backup-up MDPs and α = 1 for the recovery test.

In this section, we stop using the abuse of notation introduced in section 5.2, that consists in using horizon T instead of horizon T = T -c(1 + 1 ε )D K T T , which was done at the price of loosing only a regret of c(1 + 1 ε )D K T = 1+ε γε D Kt .

Regret when an upper-bound on the diameter is given

In case when a bound D on the diameter is known, the algorithm can use D k = D for all episodes. In that case,the bound on the number of roll-out transitions simplifies into

E K T k=1 |T R k |I{Ω} 16S (1 + ε) 4 γ 2 ε 3 (1 -ε) log(2 S+1 SAT 2 /δ)D 3 . ( 49
)
We plug the previous bound (49) in the decomposition of the regret (44) and of ( 7), and deduce (provided that γ γ and ε is as in Lemma 20) that the expected regret is bounded by

E R T 5
√ SAT +16S (1 + ε) 4 γ 2 ε 3 (1 -ε) log(2 S+1 SAT 2 /δ)D 3 + 1 + ε γε D + 2δ .
This concludes the first part of Theorem 7.

Regret when the diameter is unknown

In the case the diameter is unknown, a proxy for the diameter is given by D k . Using a slowly increasing diameter D k = log(t k ), it becomes eventually larger than d . This results in a regret scaling with √ T with an additional constant term that is however exponential in the true diameter d . One could make this dependency polynomial in d at the price of using a D k polynomial in t k leading to worst dependency in T . More formally, we get, using the crude lower bound t k k This concludes the proof of Theorem 7.

Experiments & Results

We compared A-ROGUE to UCRL Jaksch et al. (2010) and R-Max [START_REF] Brafman | R-max -a general polynomial time algorithm for near-optimal reinforcement learning[END_REF] where UCRL enjoys strong regret guarantees for communicating MDPs 5 and R-Max has strong sample complexity guarantees. The reason for comparing only to such algorithms is because they are the only one we know that provably enjoy non-trivial performance guarantees in communicating MDPs. Thus they serve here as a benchmark.

For illustration, we used three 4 × 4 gridworld MDPs (Figure 8) with stochastic transition probabilities and four actions {n, s, e, w}. Of course, the algorithms did not have knowledge about this structure and thus had to consider the full S(S -1)A + SA = 1024-dimensional problem. Though these MDPs look extremely simple, they are actually tricky due to the presence of traps, and are enough to illustrate the main drawback of existing algorithms assuming fast recoverability. Given the agent's position (x, y), if the agent is not blocked by a wall or in an absorbing state, executing action n transfers the agent to state (x, y + 1) with probability 0.8 or to either (x -1, y + 1) or (x + 1, y + 1) each with probability 0.1.

5. We do not compare against REGAL, as it is still an open question whether this algorithm can be implemented, see [START_REF] Bartlett | REGAl: a regularization based algorithm for reinforcement learning in weakly communicating MDPs[END_REF]. Actions s, e, and w are defined similarly in the other three directions. Each gridworld has a single absorbing goal state, which gives a reward of 0.9. All three tasks contain one or more "trap" states, which are nearly-absorbing states where all actions give 0 reward and lead to the initial state with probability 10 -4 . The reason for this low-probability transition is to ensure that the MDP has finite (though huge) diameter, and thus that the regret bound for UCRL holds. Putting the probability from 10 -4 to 0 only favors our algorithm, but looks unfair with respect to other algorithms. Note also that this construction is different from imposing there is a reset action. The maximum possible immediate reward is R max = 1, which means that even if the goal state is discovered early, all state-action pairs need to be explored to determine an optimal policy. The horizon was set to T = 30, 000. R-Max, was run with sampling parameter m = 20 (see [START_REF] Jong | Hierarchical model-based reinforcement learning: Rmax + MAXQ[END_REF] for explanations). For UCRL, we used δ = 0.05. We loosely tuned A-ROGUE with δ = 0.05, γ = 0.35, ε = 1/3, assuming that p 0 1/2, and we used the upper bound D = 8 on d .

The first task (Figure 8a) contains a single trap and a non-absorbing goal state. The agent must take no irreversible actions to act optimally. UCRL and R-Max are expected to perform poorly here because even if they have discovered the goal state before the trap state, they keep exploring until all state-action pairs have been visited. Thus they get stuck in the trap state. A-ROGUE, on the other hand, can learn about the trap without entering it using roll-outs. As we can see in Figure 9a, A-ROGUE has small regret compared to the optimistic strategies UCRL and R-Max. In the second task (Figure 8b), there is one trap state and one absorbing goal state. Here UCRL and R-Max explore the environment optimistically and discover the goal or the trap state with about equal probability, which leads to large regret and high variance, while A-ROGUE is able to use roll-outs to learn about the trap states and avoid them. Figure 9b shows that UCRL and R-Max incur here large regret and high variance. A-ROGUE achieves both small regret and low variance. The third task (Figure 8c) contains four absorbing trap states and a single absorbing goal state. It is harder than the previous two because there are more "trap" states. Notice that again, A-ROGUE achieves low regret while UCRL and R-Max both have large regret and high variance (Figure 9c). In all tasks, A-ROGUE successfully avoids entering bad traps with high probability. On the other hand, UCRL and R-Max accrue very large regret.

Conclusion

We obtained the first sublinear regret performance for multi-chain MDPs, as we are unaware of any work providing theoretical performance guarantees in the multichain MDP setting with no reset. The key ingredient for achieving this performance is to actively ask for external information. We captured the notion of external information here by giving the learner the option to ask for roll-outs. Most of the other possibilities require stronger assumptions and trivialize the problem by recasting it into a standard communicating MDP aith modified state-action space. Other possibilities, that are however restricted to specific situations include resorting to an expert, a simulator, or a teacher and can be seen as special cases of our setting. A-ROGUE is able to detect when it requires such external information and what experiment to design and ask for a respective roll-out. The heuristic idea behind

Figure 1 :

 1 Figure 1: Example of (a) a communicating MDP, (b) a unichain MDP with a single recurrent class, and (c) a multi-chain MDP with two recurrent classes. The circles represent states while the labeled edges represent transitions due to executing actions {a, b, c}.

  Figure2: The Heaven-or-Hell MDP. The agent's choice from the initial state either sends it to the Heaven state where it receives a reward of +1 forever, or to the Hell state where it receives a reward of 0 forever. Once the agent is in either the Heaven or Hell state it cannot return to the initial state.

Figure 3 :

 3 Figure 3: Coverings of a 4 × 4-gridworld MDP: (a) a non-maximal set of maximally large regions with diameter not larger than 2; (b) the unique 2-covering of the MDP; (c) the unique 4-covering of the MDP, with partition {S 1 } where S 1 = S.

Example 1 Figure 4 :

 14 Figure 4: Some gridworld environments. The letter I denotes the agent's initial state, T an absorbing trap, and G a goal state. Arrows leaving a goal state indicate that it is not absorbing. Arrows entering a goal state indicate that it is absorbing.

Figure 5 :

 5 Figure 5: The MDP considered in Example 2.

Figure 6 :

 6 Figure 6: An example of MDP that does not satisfy Assumption 1. Here, when in region B or D, the optimal policy will try to reach region A, which risks entering the bad regions C and E with high probability.

  The A-ROGUE algorithm Require: Horizon T , confidence δ, lower bound γ on sharpness γ , function d : N → R for guessing the diameter, parameter ε ∈ (0, 1) for control of length of rollouts, initial state s 1 . 1: Set t := 1. 2: for k = 1, 2, . . . do 3:

  a]. Since the reward function r M + k is a plausible reward function according to Definition 4, r M + k (s, a) is close to r t k (s, a) by construction. On the other hand, r t k (s, a) is close to the mean µ(s, a) by concentration of measure. We use Hoeffding's inequality together with a union bound over all (s, a) ∈ S × A and all possible values of N t k (s, a) t k

  a) -µ(s, a)| + (s,a)∈S×A v k (s, a) p M + k (•|s, a) -p(•|s, a) 1 max

Figure 8 :

 8 Figure 8: Gridworld environments: I is the agent's initial state, T an absorbing trap, and G a goal state. Arrows entering (resp. leaving) a goal state indicate that it is absorbing (resp. not absorbing).

Figure 9 :

 9 Figure 9: Comparison of average regret achieved by A-ROGUE, UCRL, and R-Max on gridworlds from (a) Figure 8a, (b) Figure 8b, and (c) Figure 8c. The shaded area represents one standard deviation for each algorithm.

  Regret Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Measures of Complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . High-level Description of A-ROGUE . . . . . . . . . . . . . . . . . . . . . 3.2 Details of A-ROGUE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Preliminary results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Dealing with non-irreversible actions . . . . . . . . . . . . . . . . . . . . . . 5.3 Continuing the unfolding step . . . . . . . . . . . . . . . . . . . . . . . . . . 5.4 Bellman equation and local diameter . . . . . . . . . . . . . . . . . . . . . .

	2.1 3 The A-ROGUE Algorithm
	3.1 4 Performance Guarantees
	5 Regret Analysis (Proof of Theorem 7)
	5.1 6 Experiments & Results
	7 Conclusion
	Contents
	1 Introduction	2
	2 Setup and Notations	6

5.5 Total number of roll-outs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6 Upper bound on the regret . . . . . . . . . . . . . . . . . . . . . . . . . . .

  The letter I denotes the agent's initial state, T an absorbing trap, and G a goal state. Arrows leaving a goal state indicate that it is not absorbing. Arrows entering a goal state indicate that it is absorbing.Sharpness of action-gapsIn terms of rewards, inside a region S i , the action gaps cannot be too big: If s ∈ S i and a ∈ A are such that all possible successor states (i.e., supp(p(•|s, a))) are contained in S i , then for all t, we must have ∆ M T -t (s, a) d . Thus, only if a leads to a different region S i , the action gap can be bigger than d . We capture the size of the action gap at such frontiers by the following definition. An MDP M with local diameter d is said to have γ -sharp action-gaps if γ is the largest γ such that for all (s, a) ∈ S × A, either ∆ M T -t (s, a) d or ∆ M T -t (s, a) > γ(T -t) for all t T . In the latter case, we say action a is irreversible at state s. If s ∈ S i and (s, a) leads to S i with ∆ M

	Definition 2 Recalling that inside a region S i one can reach any state from any other state in no more
	then d steps on average, this definition immediately implies the following observation.
	Observation 1

t

  of roll-out steps in between steps t k and t. Finally, we use a specific notation for special time-steps in an episode: t D k = argmin t∈T D

	(k)	t and t D k = argmax t∈T D (k)	t are the first and last
	decision-steps in episode k. Likewise, t R k = argmin t∈T R (k)

  D k the random state reached by π t k after |T D (k) | steps when (virtually) acting in M + k from s t k , and s + t D k the state reached by π k after |T D (k) | steps when (virtually) acting in M + k from s t k . In the second inequality, π is the policy that minimizes in expectation, the time τ + (s t D k

  π,d s t ,s number of d-roll-outs of the policy π is needed so that s ∈ S(s t , d) is visited at least n times on average. It is worth noticing at this point that we only target a control on K T k=1 |T R k | in expectation, as opposed to a high probability bound. 4 Now, A-ROGUE uses roll-outs of length

  times, and for this to happen, no more than s∈S(s t ,D k ) n 0 /p for states s ∈ S(s t , D k ) this means that every state in S(s t , d) is visited enough when A-ROGUE has observed at most the following number of transitions from π

	π k s t ,s -,d	many 1 + 1 ε D k -roll-
	-(the backup policy to s k ) are required on average. Thus, assuming we can show -,d π k outs of π k that 1/p s t ,s

β

  average, where k is the smallest episode such that D k d . If k → D k does not reach d fast enough, this potentially causes a large waste of roll-outs (but we do not want that D k becomes to large with respect to d either) and thus a a large active regret. Choosing D k = log(t k ) ensures the loss is not too important. Lower bound on the probability of first visit in d-steps at most The next step is to find β such that β 1/p

	-,d → 1, and thus π k s π k -,d s t ,s d→∞

t ,s . First, note that in the case when

T π k -(s t , s) (1 + α)D k it holds that p

  is the agent's initial state, T an absorbing trap, and G a goal state. Arrows entering (resp. leaving) a goal state indicate that it is absorbing (resp. not absorbing). S+1 SAT 2 /δ)d 3 min{e d , SA log 2

	that the expected regret is controlled by
	E R T	5 +	1 p 0	2	2d γ	T +	2d γ	+ 4 +	1 p 0	d SA log 2	8T SA
		+6 log(2 S/2+1 AST 2 /δ) 2 +	1 p 0	+	1 p min	d ( √	√ 2+1)	SAT
		16S	(1 + ε) 4 γ 2 ε 3 (1 -ε)	log(2 8T SA }
		+	1 + ε γε	log(T ) + 2δ .

Note that the word "episode" her comes from[START_REF] Jaksch | Near-optimal regret bounds for reinforcement learning[END_REF] and only refers to internal stages of the algorithm. It has nothing to do with episodic learning, and does not involve any reset to an initial state. As already stated, our algorithm interacts with the environment in a single stream of state-action-rewards with no reset.

Further, in case it is known that each state has only L successor states, one can replace 2 S with 2 L in the definition of C p t (s, a).

To account for estimation errors of the return time, the algorithm tests if the return time is less than 2D k (and not simply D k ).

To derive such a stronger result, we would need, with the current proof, to get a control on the number of visits of s ∈ S(st, d) in high probability, and not only in expectation, which is more difficult and luckily not needed for our purpose here.

the algorithm is intuitive, which is a strength, but precisely quantifying the amount of external information needed, and how to use them in an efficient way is challenging and is the focus of this paper.

Trading-off planning costs and experimentation costs A key component in our model is that roll-outs are costly: We assume that a zero reward is given for each roll-out transition, thus incurring a maximal regret for each asked transition; this is a strong penalty. Instead, one could provide a small reward, especially when producing a roll-out step is much cheaper than a real execution. Alternatively, when roll-outs are numerical simulations, it makes sense to consider the numerical cost of running a simulation and the actual time it may take competing to executing the actual action. Since our analysis separates the bound on the total number of roll-out asked by the algorithm and the cumulative regret of the algorithm while acting, such modifications when using a different cost for roll-out transitions and executed actions can be done easily.

Perspective In the paper, we provide one answer to a critical question that appears in many realistic applications of Reinforcement Learning (that is, explicitly quantifying the amount of external information sufficient to guarantee a O( √ T ) learning regret when interacting with a multi-chain MDP). Obviously, when one wants to address a real-world problem, as one should pay attention to additional difficulties (such as inaccurate state model, trembling-hand phenomenon, robustness) that need to be addressed together with the multi-chain issue. In such situations, we do not claim to provide an end-to-end solution that can directly be used off-the-shelf but a component that must be combined with other mechanisms. Amongst the many questions one can ask, an interesting direction of research is how to deal with the case when the roll-outs requested by the learner only come from an approximate model, as opposed to the same model.

Florent Teichteil-Königsbuch, Vincent Vidal, and Guillaume Infantes. Extending classical planning heuristics to probabilistic planning with dead-ends. In Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2011, San Francisco, California, USA, 2011.

Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J. Weinberger. Inequalities for the l1 deviation of the empirical distribution. Technical Report HPL-2003-97, 2003. URL www.hpl.hp.com/techreports/2003/HPL-2003-97R1.pdf.