Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs
Authors: Andrea Tirinzoni
Aymen Al Marjani
Emilie Kaufmann
Venue: NeurIPS 2022 Accept (2022)

Abstract: In probably approximately correct (PAC) reinforcement learning (RL), an agent is required to identify an $\epsilon$-optimal policy with probability $1-\delta$. While minimax optimal algorithms exist for this problem, its instance-dependent complexity remains elusive in episodic Markov decision processes (MDPs). In this paper, we propose the first nearly matching (up to a horizon squared factor and logarithmic terms) upper and lower bounds on the sample complexity of PAC RL in deterministic episodic MDPs with finite state and action spaces. In particular, our bounds feature a new notion of sub-optimality gap for state-action pairs that we call the deterministic return gap. 
While our instance-dependent lower bound is written as a linear program, our algorithms are very simple and do not require solving such an optimization problem during learning. Their design and analyses employ novel ideas, including graph-theoretical concepts (minimum flows) and a new maximum-coverage exploration strategy.  

Near Instance-Optimal PAC Reinforcement Learning for Deterministic MDPs
Andrea Tirinzoni*
Aymen Al-Marjani UMPA, ENS Lyon Lyon, France aymen al aal__arjjani jl_marranniens--yyon fr
Meta AI Paris, France
tirinzoni@fb.com com
Emilie Kaufmann
Univ. Lille, CNRS, Inria, Centrale Lille, UMR 9189 CRISIAL
Lille, France
emilie kanffmam@@mi---llll.fff
Abstract
In probably approximately correct (PAC) reinforcement learning (RL), an agent is required to identify e-optimal policy with probability 1 8. While minimax optimal algorithms exist for this problem, its instance-dependent complexity re- mains elusive in episodic Markov decision processes (MDPs). In this paper, we propose the first nearly matching (up to a horizon squared factor and logarithmic terms) upper and lower bounds the sample complexity of PAC RL in determin- istic episodic MDPs with finite state and action spaces. In particular, our bounds feature new notion of sub-optimality gap for state-action pairs that call the deterministic return gap. While our instance-dependen lower bound is written linear program, our algorithms are very simple and do not require solving such an optimization problem during learning, Their design and analyses employ novel ideas, including craph-theoretical concepts (minimum flows) and new maximum-coverage exploration strategy.
1 Introduction
In reinforcement learning [RI., 40], an agent interacts with an environment modeled as a Markov decision process (MDP) by sequentially selecting actions and receiving feedhack in the form of reward signals. Depending on the application, the agent may seek to maximize the cumulative rewards received during learning (which is typically phrased or to minimize the number of learning interactions (i.c., the sample complexity) for identifying near-optimal policy. The latter pure exploration problem was introduced [21] under the name of Probably Approximately Correct (PAC) RL: given two parameters E, 6 > 0, the agent must return policy that e-optimal with probability at least 1 8. Our work focuses on this problem in the context of episodic (a.k.a. finite-horizon) tabular MDPs.
regret minimization problem)
The PAC RI problem has been mostly studied under the lens of minimax (or worst-case) opti- mality. In the episodic setting, the algorithm proposed in [12] has sample complexity bounded by O(SAH2 log EE2 for an MDP with states, A actions, horizon H, and hime-homogeneous transitions and rewards (i.e., not depending on the stage). This is minimax optimal for such a context [11]. Similarly, in [35] the authors designed strategy with AHSAH log (1/0)/e²) complexity in time-inhomogeneous MDPs, which was later shown to be minimax optimal [17].
Work done while at Inria Lille.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

While the minimax framework provides strong notion of statistical optimality, it does not account for one of the most desirable properties for an RL algorithm: the ability to adapt to the difficulty of the MDP instance. For this reason, researchers recently started to investigate the instance-dependee complexity of PAC RI.. Farlier attempts were made in the simplified setting where the agent has access to generative model (i.e., it can query observations from any state-action pair using simulator) in 7-discounted infinite-horizon MDPs [50, 5J. The online setting, where the agent can only sample trajectories from the environment, has been studied in [4] for discounted MDPs and in [46] for episodic amm-innooooeeeouu MDPs. All these works derive sample complexity bounds that scale with certain gaps between optimal value functions. For instance, in the episodic setting, the value gap 4,, (s, a) == V (s) Q7 (s, a)² intuitively characterizes the degree of sub-optimality of action a for state at stage h. Unfortunately, these bounds are known to be sub-optimal and how to achieve instance optimality remains one of the main open questions. In fact, recent works on regret minimization [42, 13] showed that value gaps are often overly conservative, and the same holds for PAC RL. We refer the reader to Appendix A for a deeper discussion on problem-dependent results in RL and the review of other related PAC learning frameworks.
The main challenge towards instance optimality is that existing lower bounds for exploration problems in MDPs [5, 42, 4, 13] are written in terms of non-convex optimization problems. Their "implicit" form makes it hard to understand the actual complexity of the setting and, thus, to design optimal algorithms. Existing solutions either derive explicit sufficient complexity measures that inspire algorithmic design [46]. or solve (a relaxation of) the optimization problem from the lower bound using the empirical MDP as a proxy for the unknown MDP [4]. The latter extends the Track-and-SS and-Stop idea originally proposed in [22] for bandits (H = 1), and requires in particular a large amount of forced exploration. Both solutions have limitations. On the one hand, it is not clear if and how such sufficient complexity measures or relaxations are related to an actual lower bound. On the other hand, strategies solving a black-box optimization problem to find an optimal exploration strategy are typically very inefficient and often come with either only asymptotic (ō - 0) guarantees or with poor (far from minimax optimal) sample complexity in the regime of moderate d.
This paper presents a complete study of PAC RL in tabular deterministic episodic MDPs with fime-inhomogeneous transitions. sub-class of stochastic MDPs where state transitions are deterministic and the agent observes stochastic rewards from unknown distributions. Our first contribution is an instance-dependen lower bound on the sample complexity of any PAC algorithm. We show that the number of visits ni (s, a) to any state-action-see triplet (s, h) at the stopping time 7 satisfies
Contributions
log(1/6)
B|n a)) 2 max Au (s, e),
where (s, := : - Vi,, with V/" the expected return of policy n, V/* the optimal expected return, and IT,, the set of all deterministic policies that visit (s,a) a) at stage h. We call these quantities the deterministic return gaps due to their closeness with the return gaps introduced in [13] for general MDPs. In deterministic MDPs, the deterministic return gaps are actually H times larger than the return gaps and they are never smaller than value gaps. Our lower bound on the sample complexity r is then the value of a minimum flor with local lower bounds (1), i.e., roughly the minimum number of policies that must be played to ensure (1) for all (s, h). To our knowledge, this is the first instance- dependent lower bound for the PAC setting in episodic MDPs.
On the algorithmic side, we design EPRL, a generic elimination-basse method for PAC RL, and couple it with a novel adaptive sampling rule called maximun-coverra sampling. The latter is a simple strategy which does not require solving the optimization problem from the lower bound at learning time a Track-and-Stop fashion. Instead, it greedily selects the policy that maximizes the number of visited under-sampled triplets (s, h). i.e. those having received the least amount of visits so far. We prove that EPRL is (e, (e,8))corree under any sampling rule. Moreover, we show that the sample complexity of EPRL with max-coverage sampling matches our instance-dependent lower bound up to logarithmic factors and a multiplicative ((H2) term, while also being minimax optimal. Finally, we perform numerical simulations on random deterministic MDPs which reveal that EPRL can indeed improve over existing minimax-optime algorithms tailored for the deterministic case.
2 and Q" respectively denote the optimal value and action-valie functions, that are defined in Section 2.

---

2 Preliminaries
Let M; = (S, A, (f, Ph hheme $1, H1) be a deterministic time-inhomooennouu finite-horizon MDP, where S is finite set of S states, is a finite set of A actions, fn 8 x A + S and pn 8 x A - (((R) are respectively the transition function and the reward distribution at stage h E [H], 81 E S is the unique initial state, and H is the horizon. Without loss of generality, we assume that, each stage h E [H] and state s E S, only a subset (s) C A of actions is available. We denote by (s, a) == (s.a) [z]] the expected reward after taking action a in state at stage h.
A deterministic policy π = { is a sequence of mappings Th : S + A. We let 11 := { wh E [ E S (s) E As be the set of all valid deterministic policies. Executing a policy π E II on MDP M yields deterministic sequence of states and actions (5% ([)H)) where of = $1, of (s7) for all h E [H) and sf fn-1($7-11 - ,) for all h E {2. ....... H). We let Sn = {s E S 3m E II: 3 5} be the subset of states that are reachable at stage h E [ff]. Finally, we define N := Σm= Eess, [s)) as the total number of reachable state-action staci triplets.
For each (s, h). the action-value function Q7, (s, a) of policy II quantifies the expected return when starting from at stage h. playing and following т thereafter. In deterministic MDPs, it has the simple expression (7, a) -r a) + h- (fa (s, a)), where V (s) :- Q7 (s, nr (s)) is the corre- 0). The expected return of ι is simply its value at the initial
(s,
sponding value function (with +
state, i.e., VT' = Σカ= rh (8% ai We let II* == f-* E II: VTT (s1) = max Vi" (81) be the set of optimal policies, i.e. those with maximal return. Finally, we denote by (s) and Q7 (s. the optimal value and action-value function, respectively. These are related by the Bellman optimality equations as (7,
Th (s, a) + (fa a)) and V = Aa 27, (s, a).
Learning problem The agent interacts with an MDP M in episodes indexed by t E N. At the beginning of the t-th episode, the agent selects a policy n' E Il based on past history through its sam- pling rule, executes it on M, and observes the corresponding deterministic trajectory (57 .a% )e{[H]
together with random rewards (vf, )е where v/. vn(s% ,a)'). ). At the end of each episode, the agent may decide to terminate the process through its stopping rule and return a policy रे prescribed by its recommendation rule. We denote by its random stopping time. An algorithm for PAC identification is thus made of a triplet ([ hEN,. T, 7). The goal of the agent is two-fold. First, for given parameters e, 5 > 0, it must return an e-optimal policy with probability at least 1 5.
Definition 1. An algorithm is (e.8)-PAC on a set of MDPs M if. for all M 27, it stops a.s. with
PM (F) 2 (1)) - 2 2-5
Second, it should stop as early as possible, i.e., by minimizing the sample complexity T. Henceforth, we assume that the transition function f is known but not the reward distribution v. Note that if the transitions are unknown, the agent can still estimate them (since it knows that M deterministic) with at most N= < SAH episodes.
Minimum flows We review some basic concepts from graph theory which will be the core
of our algorithms and analyses later. Full details can be found in Appendix B. First note that a deterministic MDP (without reward) can be represented as a directed acyclic graph (DAG) with one
are for each available state-action-stage triplet. Let & == [[ss, a, h) : h E [H], s E Sb, E }x{))) be the set of ares in the DAG. The minimum flow problem, originally introduced in [45] and later studied in, e.g., [1, 2, 10], consists of findining a flow (i.e.. an allocation of visits) of minimal value which satisfies certain demand constraints in each are of the graph. In our specific setting, we define a flow as any non-negative function 1) E - [0, oo) that belongs to the following set
(6',a)) a²) = EueA.(s) (8, a) 4h > 1,8 E Sn Ω = 11 E - [0, oo) E(s (( (8/
This implies that flow, seen an allocation of visits to the arcs, satisfies the navigation constraints (i.e., incoming and outcoming flows are equal at each state). The minimum flow for a non non-negative bower-bound function ç : E + [0, 20) is the solution to the following linear program (LP):
6 (c) min Σ
(() s.t. (s, 2 (s) V(s,a,h) E
nEn
(x1)
3

---

Intuitively, the goal is to minimize the amount of flow leaving the initial state while satisfying the navigation and demand constraints. We note that more efficient algorithms exist for this problem than the LP formulation, e.g., the variant of the Ford-Fulkerson method proposed in [10] which is guaranteed to find an integer solution when the lower bound function is integer-valued.
3 The Complexity of PAC RL in Deterministic MDPs
Before stating our lower bound, we formally introduce the new notion of sub-optimality gap it features and compare it with other notions that appeared in the literature.
On sub-optimality gaps The most popular notion of sub-optimality gap is the so-called value gap. It was introduced first in the discounted [e.g., 38, 48]. Formally, in the latter context, the value gap of any action a E As in state 8 E S₁, at stage h E [H] is An a) Vž (s) Q% (s,,a) a). Such notion of gap appears in the complexity measure for PAC RL proposed in [46]. In the deterministic setting, such a complexity measure can be written as c(M, = E(sa,,) (axx(S where (s, = miiaa'An An (s, a') if
setting [e.g., 50] and later for episodic MDPs
is the unique optimal action at (s, h)) and A (s. a) = (s, a) otherwise. Intuitively, the (inverse) value gap is proportional to the difficulty of learning whether an action a is sub-optimal for state at stage h. Then, C(M,e) E) is proportional and stages. Recent works [42, 13] showed that this is actually not necessary: if one only cares about computing a policy maximizing the return at the initial state, it is not necessary to learn an optimal action at states which are not visited by such an optimal policy, in particular when the return of all policies visiting the state is small. The return gap [13] was introduced to cope with this limitation. In deterministic MDPs, it can be expressed as gap, (s, a) == H min Ex (s af), where we denote by II == {a E II: s% = 8, aj = a} the subset of deterministic policies that visit (s, a) at stage h. In words, the return gap of (s, a, ht) is proportional to the sum of value gaps along the best trajectory (i.e., one with maximal return) that visits (8, a) at stage h. Intuitively, this means that, if A (s, a) is extremely small but all policies visiting (s, a) at stage h need to play highly sub-optimal action before, then An (s, a) < gap, (s, a). In the deterministic case, our lower bound reveals that the normalization by H is not necessary, and we define the deterministic return gap be
the difficulty of learning a near optimal action at all states
An = V*(s)) max rElI....
(s))).
(2)
Using the well-known relationship (((()) = it is easy to see that (n a) S (s, = x E
- (1
An ag)) [e.g.. 42, Proposition 5],
Lower Bound We now present our instance-dependen lower bound based on deterministic return gaps, which will guide us in the design and analysis of sample efficient algorithms. This result is the first instance-dependent lower bound for PAC RL in the episodic setting. Lower bounds for e-best arm identification in bandit model (which corresponds to // S = 1) were derived in [34, 14, 23], while problem-dependent regret lower bounds for finite-horizon MDPs are provided in [13, 42].
We consider the class M,, of deterministic MDPs with 02 -Gausssian rewards, in which 2n2 (s, a) = M (rrx(s, (s, a), o²). Let IIf == (N II V (s) 2 (i - =} be the set of all E-optimal policies and denote by 2 : {s Sn, E An N... O IT * () the set of state-action pairs that are reachable at stage h by some e-optimal policy. Note that An(s,)) a) S for all (s, a) E Z
Theorem 1. Let o² > O and fix any MDP M E Mzz. Then, any algorithm which is (),8)-PAC on the class Mz, must satisfy, for any h E [H] 8 E Sh, and a E An(s),
o² #log(1/40)
EMIn a)) 2 (s,
4 max (n a), Amin e)2²
where Amin == min ay Dnlss' An , a') if | = 1 and A 0 otherwise. Moreover, for g: E + [0, oo) the lower bound function defined above,
E EM[T] 2 (c).
(4)
The first lower bound (3) is on the number of visits required for any state-action-stage triplct. It intuitively shows that an (e, 8 algorithm must visit each triplet proportionally to its inverse

---

deterministic return gap. The second one (4) shows that the actual sample complexity of the algorithm must be at least the value of minimum flow computed with the local lower bounds (3), i.. that the
algorithm must play the minimum number of episodes (i.e., policies) that guarantees (3) for each (8, a, ht. Intuitively, due to the navigation constraints of the MDP, there might be no algorithm which tightly matches (3) for each (s, a, h), and (4) is exactly enforcing these constraints. While (*(c) has no explicit form, Lemma 6 in Appendix B gives idea of how it scales with the gaps:
o² (og(1/)))
o² log(1146)
Σ SES (x()) Am. a), m)m
5 (c) S Σ E
Σ
mAX
Ne [M]
hE|m] SES aEAr,() 4max(An, a), Amin: e)²
Observe that the quantity the right-hand side resembles the complexity measure c(M,s) [46], except that value gaps are replaced by return gaps. This implies that, in general, our lower bound can be much smaller than this complexity. For instance, in an MDP with extremely small value gaps in states which are not visited by an optimal policy, xp((c) (c) does not scale with such gaps at all.
In Appendix C.2 we further provide a minimax lower bound for PAC RL in deterministic MDPs scaling as Ω (SAH²² 2 log (1 (1/0)/=²), with a reduced H² dependency compared to the H that appear in the stochastic case [17]. We note that faster rates for deterministic MDPs have already been obtained in other RL settings [c.g., 49]. The BPI-UCRL algorithm [29] particularized to deterministic MDPs is matching this lower bound and is thus minixal optimal. We now present the first algorithm which is simultaneously minimax optimal for deterministic MDPs and nearly matching (up to 0
and logarithmic factors) the lower bound of Theorem 1.
4 EPRL and Max-Coveragee Sampling
We propose a general Elimination- -baee scheme for PAC RL, called EPRL (Algorithm 1). At each episode t E N, the algorithm plays a policy x' selected by some sampling rule. Then, based on the collected samples, the algorithm updates its statistics and eliminates all actions which are detected as sub-optimal with enough confidence. This procedure is repeated until stopping rule triggers.
Formally, EPRL maintains an estimate 1% (s, = nf,(o.a) Ei= v 1 (s/, = s. = a), with Ag 0,
of the unknown mean reward ru (s,ss a) for each (s, a, h). Here ni, (s. a):= Ei 1 (s), 8, dr = a) is the number of times (s, a) is visited at stage h up episode L. We define the following upper and lower confidence intervals to the value functions of a policy π E II:
Qh (s, a) = Fl, (s, a) + (1, + V (fh(s,))
1.5 Vi'(( (s) = Q (s, (n()))
= ((.
(s) == (s, (s)), (s))
where 1/ (s. a) is a bonus function, i.e., the width of the confidence interval at (s, a,aa,, h). We assume that rewards are o--sub-Gaussian with a known factor o², which allows us to choose
(s, = / (1, 8(t, = 202 log (s,
(4t2N 8
(5)
Elimination rule Algorithm keeps a set of active (or candidate) actions At, (s) for each stage h [H) state Sr. and episode t E N. Let IT' = {ir II Vs, h (s))) A (s) V A = 0) be the subset of active policies that only play active actions at episode t. Note that an active policy can play an arbitrary action in states where all actions have been eliminated. As can be seen in Line 7 of
V (s1) S max 111((s)) that is, when we are confident that none of the policies visiting (s, a) at stage h is optimal. We recall that II,, denotes the set of all deterministic policies that visit s, a at stage h. The maximum restricted to II, can be easily computed by standard dynamic programming (e.g., it is enough to set the reward to -o for all state- action pairs different than (s, a) at stage h). If Ilg h - = we set the maximum to 0o so that the elimination rule triggers.
Algorithm 1, action a is eliminated from (s) if max
Remark 1. While defining II' simplifies the presentation. EPRL neither stores nor enumerates the set of active policies. In particular, EPRL does not eliminate policies but rather (s, a, h) triplets. The sets Ai (8) can be updated in polynomial time by dynamic programming without ever computing IT'.
NNote that sub- Gaussianity generalizes the common assumption of bounded rewards in [0. 1] (in which case a 1/4) and the one of Gaussian rewards with variance o² (as used in the lower bound of Theorem l).
5

---

Algorithm Elimination-based PAC RL (EPRL) for deterministic MDPs
1: Input: deterministic MDP (without reward) M == (S,A, (fahne(m 81, H), E,
2: Initialize (s) f- (s) for all h E [H]] Sh
3: Set (s, a) <- 0 for all h E [H], E Sh, E (s)s)
4: for =
do
5: Play T' < SAMPLINGRULEO
6: Update statistics (6, a), (s,
7: () + A (s) E A max Vi' (s1) 2 ma VT (s1)
8: where I { E Vs,h: (s)) E ' Vs). 1 (s) =0} (need not be stored/computed)
V1 Mi (s) (a)) e vh [H]. E S : [sa(s) then
9: if maX
10: Stop and recommend arg a Vi (s1)
11: end if
end for
13: function MAXCOVERAGE)
14: Let & < min ke H ME,,,, (() (s) ni
(s, a) n
and tx. infientl: k4 ke}
if mod then
16: return x' 4- arg max n Ell Σ 1 01 E EAA "r (s%), m/ (57. kis)
17: else
18: return x² f- nelt- Σx=1 (5% o.))
(MAXDIAMETER)
19:
end if
Stopping rule EPRL uses two different stopping rules (Line 9). The first one checks whether, for all active policies π E II', the confidence interval on the return, V (s1) vT = 2 > (5% (5%,,a) ag), which we refer to as diameter, is below The second one checks whether each set Ai (s) contains either action or 0 actions (which happens when the state unreachable by an optimal policy). In both cases, we recommend the optimistic (active) policy (Line 10).
Sampling rule While EPRL may be used with different sampling rules, we recommend the max- coverage sampling rule described in Algorithm 1. This sampling rule aims at ensuring that no (8, a, ht) triplet remains unser-visited for too long. This is achieved by selecting the policy which greedily maximizes the number of visited under-sampled triplets, denoted by Ur. The quantity ke
f-1 min (s.,)))aa)) ((s) 1h (s, a) + can be interpreted as the target minimum number of visits from active triplets that we want to achieve in round t and permit to define
n' arg max NEll
Σ ((5h, ag. h) E Ub) with U4 {s, a T (s,,a) < }
(s),
where Eg = (t: k2 =} is the first round in which the target set to The argmax over II can be computed using dynamic programming. We emphasize that this argmax is not restricted to the set of active policies, meaning that we may play eliminated actions in order augment the coverage (that is, the minimal number of visits) faster. Every even round, max-coverage instead chooses active policy maximizing the diameter featured in the stopping rule (max-diamete, sampling). As we shall see in our analysis, this dichotomous behavior is needeed in order to maintain minimax-optimality
Comparison with other elimination-basee algorithms The work of [19] provides heuristic using action eliminations to find an c-optimal policy in discounted MDP. However, no sample complexity guarantees are given for this algorithm, which uses different elimination rule, based on confidence intervals on the optimal value function, and a uniform sampling rule. The MOCA algorithm [46] also uses different action elimination rule compared to ours. particular, the decision to eliminate (s. a, h) is made based only on rewards that can be obtained after visiting (s, a, ht. Moreover, this algorithm uses a complex phase-base based sampling rule, while the sampling rule of EPRL is fully adaptive.

---

5 Theoretical Guarantees
Our first result, proved in Appendix D.2.1, shows that EPRL is (z, 6)-PAC under any sampling rule. It follows from the fact that 1) the choice of bonus function (5) ensures that all the confidence intervals valid and 2) state-action pairs from optimal trajectories are never eliminated when this holds. Theorem 2. Algorithm is (e, 6PPAC provided that the sampling rule makes stop almost surely.
We now analyze the sample complexity of EPRL combined with max-coverage sampling.
Theorem 3. (Informal version of Theorem in Appendix D.3) With probability at least 6, the sample complexity of EPRL combined with the maximum-coverugs sampling rule satisfies
T = -0((((g)) where g E - [0, oo) is the lower bound function defined by
320² H² (n, = max (An o), Amin, 8)²
[4N3)
160 IT log max (An(s, a), Amin,
AN
5
log
+ 88 88log
+ 2.
8
Moreover, with the same probability, T Ō( SAH2 log(1/8)), where Ô hides logarithmic terms.
6²
First note that EPRL combined with such a sampling rule is minimax optimal, since it matches the worst-case lower bound derived in Appendix C.2. In addition, the leading term in the instance- dependent complexity is the value of minimum flow with lower bound function g that, in case multiple disjoint optimal trajectories exist', matches the gap-dependence in (1). If we suppose
that there exist at least two disjoint optimal trajectories, in which case Amin A O. then, thanks to Lemma 7 in Appendix B, one can easily see that yp" (g) S (c) + (g').. where go a) == O(H2/ max (s,( a), does not depend on 6, e is the "optimal" lower bound function from (1), and is a numerical constant. Hence, in the asymptotic regime (6 + 0), (g) matches our lower bound up to a O multiplicative factor.
Remark 2. Since Theorem was derived for Gaussian rewards, EPRL is instance-optingg only when the reward distribution is Gaussian. This is not surprising since it is well known from the bandit literature [e.g., 32] that sample complexity bounds scaling with a sum of inverse squared gaps are optimal only for Gaussian distributions. Note, however, that EPRL works in greater generality and achieves complexity 4" (c) for any 0² --sub-Gaussia distribution without knowing its specific form (e.g.. whether it Gaussian or not). What the optimal rate for other common distributions (e.g.. bounded rewards in [0, 1l) and how to achieve it remains an open question.
Finally, our sample complexity bound has an extra multiplicative logarithmic term which roughly scales as Olog((H) log(Et H log(1/8)/s)). While this term makes the dependence on å sub-optimal by a log 1og(1/8) factor, we show in Appendix E that it can be removed in the specific case of tree-based MDPs [13].
Remark 3. We believe that the sub-optimality on H could be reduced to single H factor by boosting the lower bound. In Appendix E, we show that this indeed possible in tree-based MDPs. for the upper bound, reducing 2 to H is likely to require tighter concentration bounds on values.
Remark 4. In Appendix D.4, we prove that, when using the max- max- diameter sampling rule (Line 18 in Algorithm 1) at each step, the sample complexity is ((E(e,,,)) H2 max(An((.
(s, a), Amin e)2). While this scales with the same gaps as Theorem 3, it is only a naive upper bound the minimum flow value (see Section 3). The intuition is that max-diameter sampling alone does not ensure that all triplets are visited sufficiently often, which prevents us from tightly controlling their elimination times.
Proof sketch The complete proof is given in Appendix D.3. It first relies on the following crucial result which relates the deterministic return gaps to the sum of confidence bonuses.
Lemma (Diameter vs gaps). With probability least 6, for any I N, h E [H] 8 E Sp,a Ax(s), if (s) and the algorithm did not stop at the end of episode t,
An(s, a)
Amin
H
max
S
max TETT--1
4
4
2
*When there is a unique optimal trajectory, our upper bound scales with Amin min A all stages h, while the lower bound scales with 2ht at stage h. We believe the latter should be improvable to obtain a dependence on Amin matching the one the upper bound.
7

---

where Amin == m minges, a: (s.a>0 (s a)) if there exists a unique optimal trajec- tory (5) (% anneem and Amin == in the opposite case.
In our analysis, we refer to the set of consecutive time steps { N: k, =k} as the k-th period. Using the fact that in period k + each active triplet has been visited at least & times (which allows to upper bound each bonus bj, (5% a%) for π I by a quantity scaling in /1/k), one can use Lemma to obtain an upper bound K,,a max (s.)), on the last period in which (s, a, h)
log(1/6)
is active (Lemma 18 in Appendix D.3). A crucial step of the proof is then upper bound the duration of the k-th period, d2 = Eim1 1 (kg = k).
Lemma 2. dy - (H) + (c") where (s, = 1(a E A. (s), Ay (s. a) < k).
The intuition behind this result is as follows. Recall that the goal of the max max-coverage sampling rule period is to visit at least once each (s, a, h)) that active (i.e., a E (s)) and undersampled (i.e., ni (s, a) < k). By definition, the minimum flow yo (c*) ) is the minimum number of policies that need to be played to achieve this goal. Interestingly, Lemma 2 shows that the number of policies played by max-coverage
visit all active undersampled triplets is very close to its theoretical minimum, despite the fact that the algorithm never computes an actual minimum flow. We prove this by interpreting max-coverage sampling a greedy maximization of some coverage function (related to minimum flow problem) and leveraging the theory of sub-modular maximization [e.g., 31].
Thanks to Lemma 2, we have that
T S 2(og H) + 1)
Σ x (c))
A=1
where ky is the index the period at which the algorithm stops. To bound this quantity we carefully apply the theory of minimum flows and their dual problem of maximum cuts. Let define cut C as any subset of states containing the initial state and let (C) be the set of ares that connect states in with states not in C. The well-known min-flow-mx--cut theorem (Theorem stated in Appendix B) states that, for any lower bound function &. pp" (c) = maxcee (s.a,h) (8, a), where C denotes the
set of all valid cuts. Then,
<
max CEE
Σ
k1 (1 (s)
< max
Σ
(R + +1 = (g).
CEE
(EE(C))
(s.a.A)EE(C)
where g 3 10, 00) is defined by gn(s, a) = Kisaah + 1. It follows that
2(log H) 1) Σ (0(())
2(log( H) + (log(k,, + +1))0(0)
2(log(H) (t) + 1) max log(Rs,a.h) + 10 (g).
(s,a,h)
Using the expression of R.,a,h given Lemma 18 Appendix D.3 concludes the proof of the stated (g)) instance-dependent bound. For the worse-case bound, we refer the reader to Theorem 12.
6
Experiments
We compare numerically EPRL to the minimax optimal BPI-UCRL algorithm [29], adapted to the deterministic setting, synthetic MDP instances. For EPRL, experiment with two sampling rules: max-coverage (maxCovv and max-diameter (maxD, see Line 18 of Algorithm 1). We defer to Appendix F some implementation details, including a precise description of the BPI-UCRL baseline.
We generate random "easy" deteministic MDP instances with Gaussian rewards of variance using the following protocol. For fixed S, A, H the mean rewards (s,s,, a) are drawn i..d. from uniform

---

distribution over [0, 1] and for each state-action pair, the next state is chosen uniformly at random in {l...., 5}. Finally, we only keep MDP instances whose minimum value gap. denoted by Amin+ is larger than 0.1. Our first observation is that depending on the MDP, the identity of the best performing algorithm can be different.
Figure we show the distribution of the sample complexity (estimated over 10 Monte Carlo simulations) for three different MDPs obtained from our sampling procedure with S, = and H = and for algorithms that are run with parameters 0.1 and e = 1.5Amin-
6000
5500
1600
5000
5000
4500
1200
4000
4000
1000
3500
3500
3000
600
2500
UPI_UCRL
UPLUCAL
maxD
[PLUURL
Figure 1: Distribution of stopping times on particular MDPs over 10 runs, with & = 1.55 17Amin The horizontal lines represent the average sample complexity.
To get better understanding of this phenomenon, we then generated 10 MDP instances of size (S, A. H) = 22,2, 3) and for each MDP we ran EPRL and BPI-UCRL for 25 values of in grid (0.05Amin: 10Amin] and 8 = 0.1. We ran 10 Monte-Carlo simulations for each value of the triplet (MDP, algorithm A, in order to estimate the expected sample complexity Ex [T]] In Figure 2 we plot the relative performance (ratio of sample complexities) of different algorithms as a function of the value of Amiii each point corresponds to different MDP and different value of E. We observe that for large values of E/ min. BPI-UCRL has a smaller sample complexity than both versions of EPRL, with ratio never exceeding (resp. 3) for max-diameter (resp. max-coverage). However, in the more interesting small E/ min regime EPRL is better by several orders of magnitude. This is expected since, for small E, EPRL is able, through its elimination rule, to identify the optimal policy long before the diameter goes below E. We observe that the threshold of E/ /Amin at which EPRL algorithms become better choice than BPI-UCRL seems to vary with the MDP.
100
1.0
10
0.8
10-2
0.6
10
maxD maxCov
2
for A in (maxD, maxCov} (left) and EmaxD [78)/ Emaxxoo (right) as function of E/ Amiin
Figure 2: Ratios in log-scale
Our experiments also reveal an intriguing phenomenon: the use of max-diameter sampling within EPRL often outperforms max-coverage sampling, even if there exists MDPs (2 out of 10 in our experiments) in which max-coverage is indeed empirically better. We leave future work to obtain a better characterizations of MDPs for which EPRL with max-coverage sampling performs best.

---

7 Discussion
We derived an instance-dependent and a worst-case lower bound characterizing the complexity of PAC RL in deterministic MDPs, and proposed a general elimination algorithm together with novel maximum-coverage sampling rule that nearly matches them (up to O(1²²) and logarithmic factors). We conclude with some discussion about our results and future directions.
Max-coverage vs max-diameter While minimax optimality can be easily achieved with very simple strategies (like max max-diameter or BPI-UCRL), instance optimality requires careful algorithmic design. Our coverage-based strategy is built around the idea of "uniformly" exploring the whole MDP, while using an elimination strategy to ensure that no (s, a, h) is sampled much more than what the lower bound prescribes. Notably, this sampling rule is very simple, while exiting PAC RL algorithms with instance-dependent complexity are all quite involved [46, 4]. Moreover, max-coverage sampling naturally extends to stochastic MDPs, e.g., by doing optimistic plamning function equal to for under-sampled triplets and for the others. Finally, in our experiments on random instances, observed that max-diameter is often comparable better than max-coverr coverage. We leave as future work to investigate whether the latter is also provably near instance-optimal.
MDP with reward
Computational aspects Our sampling rule requires solving one dynamic program per episode, which takes O(N) time. The bottleneck is the elimination rule, which requires O(N²) per-episode time complexity to solve one dynamic program for each active triplet. However, we note that climinations could be checked periodically (c.g., significantly compromising the sample complexity guarantees.
at exponentialll-ssearaad times) without
Improving our results Our instance-dependen upper bound for max-coverage sampling is sub- optimal by factor H and multiplicative Olog (1g(1/)) term. In Appendix E, we show that, for the specific sub-class of tree-based MDPs [13], we can obtain improved results all these aspects. In particular, show that (I) the lower bound scales with extra factor H and it is fully explicit, (2) the multiplicative log terms in the sample complexity of coverage- sampling can be removed, and (3) maximum-diamett sampling also achieves near instance-optimal guarantees.
Beyond Gaussian distributions As it is common, e.g., in the bandit literature, the gaps in our lower and upper bounds are optimal only for Gaussian reward distributions. Extending Theorem to general distributions is actually simple (see, e.g., [28] and Lemma 8 in Appendix C). However, this would yield gaps written in terms of KL divergences between arm distributions rather than differences of mean rewards as in the Gaussian case. How to match such gaps is an interesting open question.
Instance optimality in stochastic MDPs The main open question is how to achieve (near) instance- optimality for PAC RL in stochastic MDPs. We believe that many of the results presented this paper could help in this direction. First, our instance-dependent lower bound could be extended to the stochastic case by modifying return gaps to include visitation probabilities and minimum flows to account for stochastic navigation constraints. Second, the algorithmic side, maximum- coverage sampling rule casily extends to stochastic MDPs as mentioned above, while our elimination rule could also be adapted by computing the optimistic return of policies visiting certain (s, a, h) with least some probability, which corresponds to a constrained MDP problem [e.g.. 18). Studying how these components behave in stochastic MDPs is exciting direction for future work.
Acknowledgments and Disclosure of Funding
Aymen Al-Marjani ackowledges the support of the Chaire SeqALO (ANR-20-CHH) -0---AH-----000) Emilie Kaufmann acknoweldges the support of the French National Research Agency under the BOLD project (ANR-19-CH23-0022-00)
References
[1] Veena Adlakha, Barbara Gladysz, and Jerzy Kamburowski. Minimum flows in (s, t) planar networks. Networks, 21(7):767-773, 1991.
[2] Veena G Adlakha. An alternate linear algorithm for the minimum flow problem. Journal of the Operational Research Society, 5772):177-182, 1999.
10

---

[3] Alekh Agarwal, Mikael Henaff, Sham Kakade, and Wen Sun. Pe-pg: Policy cover directed exploration for provable policy gradient learning. Advances in Neural Information Processing Systems, 33:13399-13412, 2020.
[4] Aymen Al Marjani, Aurélien Garivier, and Alexandre Proutiere. Navigating to the best policy in markov decision processes. Advances Neural Information Processing Systems, 34, 2021.
[5] Aymen Al Marjani and Alexandre Proutiere. Adaptive sampling for best policy identification in markov decision processes. In International Conference on Machine Learning, pages 7459- 7468. PMLR, 2021.
[6] Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008
[7] Marco Brandizi, Natalja Kurbatova, Ugis Sarkans, and Philippe Rocca-Serry graph2tab, a library to convert experimental workflow graphs into tabular formats. Bioinformatics, 28(1 28(12)11665-1667 2012.
[8] S Bubeck and R Munos. Open loop optimistic planning. In Conference on Learning Theory, 2010.
[9] Apostolos N Burnetas and Michael Katehakis. Optimal adaptive policies for markov decision processes. Mathematics of Operations Research, 22(1):222-25) 255, 1997.
[10] Eleonor Ciurea and Laura Ciupala. Sequential and parallel algorithms for minimum flows. Journal of Applied Mathematics and Computing, 15(1):33-75, 2004.
[11] Christoph Dann and Emma Brunskill. Sample complexity of episodic seed-horizon reinforce- ment learning. In Advances in Neural Information Processing Systems (NIPS), 2015.
[12] Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards accountable reinforcement learning. In International Conference on Machine Learning, pages 1507-1516. PMLR, 2019.
[13] Christoph Dann, Teodor V. Marinov, Mehryar Mohri, and Julian Zimmert. Beyond value- function gaps: Improved instance-dependent regret bounds for episodic reinforcement learning. CoRR, abs/2107.01266 2021.
[14] Rémy Degenne and Wouter M. Koolen. Pure exploration with multiple correct answers. In NeurlPS, 2019.
[15] Rémy Degenne, Wouter M Koolen, and Pierre Ménard. Non-asymptotic pure exploration by solving games. In Advances in Neural Information Processing Systems, pages 14492-14501, 2019.
[16] Omar Darwiche Domingues, Yannis Flet- Edouard Leurent, Pierre Ménard, Xuedong Shang, and Michal Valko. rlberry A Reinforcement Learning Library for Research and Education. https: //gi //githubbbbb//t/// thub. htarr//berryyyp///bbrrr 2021.
[17] Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited. In Algorithmmic Learning
Theory (ALT), 2021.
[18) Yonathan Efroni, Shie Mannor, and Matteo Pirotta. Exploration-exploitation in constrained mdps. arXiv preprini arXiv:2003.02//88 2020.
[19] E. Even-Dar, S. Mannor, and Y. Mansour. Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems. Journal of Machine Learning Research, 7:1079-1105. 2006.
[20] Zohar Feldman and Carmel Domshlak. Simple regret optimization in online planning for markov decision processes. Journal of Artifial Intelligence Research, 51:165-205, 2014.
[21] Claude-Nicolas Fiechter. Efficient reinforcement learning. Proceedings of the Seventh Conference Computational Learning Theory (COLT), 1994.

---

[22] Aurélien Garivier and Emilie Kaufmann. Optimal best arm identification with fixed confidence. In Conference on Learning Theory, pages 992-1027. PMLR, 2016.
[23] Aurélien Garivier and Emilie Kaufmann. Nonasymptotic sequential tests for overlapping hypotheses applied near-optimal arm identification in bandit models. Sequential Analysis, 40(1))61-96, 2021.
[24] J.-B. Grill, M. Valko, and R. Munos. Blazing the trails before beating the path: Sample-efficien monte-carlo planning. In Neural Information Processing Systems (NeurIPS), 2016.
[25] Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. arXiv:2002.02794 2020.
[26] Anders Jonsson, Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Edouard Leurent, and Michal Valko. Planning markov decision processes with gap-dependent sample complexity. Advances in Neural Information Processing Systems, 33:1 15:31153,,,,, 2020.
[27] Sham Kakade. On the Sample Complexity of Reinforcement Learning. PhD thesis, University College London, 2003.
[28] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier. On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17(1):1-42, 2016.
[29] Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. In Algorithmic Learning Theory (ALT), 2021.
[30] Michael J. Kearns, Yishay Mansour, and Andrew Y. Ng. A sparse sampling algorithm for opar-optimal planning in large markov decision processes. Machine Learning, 49(2-3):193-22) 2002.
[31] Andreas Krause and Daniel Golovin. Submodular function maximization. Tractability, 3:71- 104, 2014.
[32] Tze Leung Lai and Herbert Robbins. Asymptotically efficient adaptive allocation rules. Ad- vances in applied mathematics, 6(1):4 22, 1985.
[33] Tor Lattimore and Csaba Szepesvari. Bandit Algorithms. Cambridge University Press, 2019.
[34] S. Mannor and J. Tsitsiklis. The Sample Complexity of Exploration the Multi-Armed Bandit Problem. Journal of Machine Learning Research, pages 623 648, 2004.
[35] Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration in reinforcement learning. In International Conference on Machine Learning (ICML), 2021.
(36] George I. Nemhauser, Laurence A Wolsey, and Marshall I. Fisher. An analysis of approximations for maximizing submodular set functions-is i. Mathematical programming, 14(1):265-29) 1978.
[37] Jungseul Ok, Alexandre Proutiere, and Damianos Tranos. Exploration in structured reinforce- ment learning. In Advances in Neural Information Processing Systems, pages 8874-8882, 2018.
[38] Max Simchowitz and Kevin G. Jamieson. Non-asymptotic gap-dependent regret bounds for tabular mdps. In NeurIPS, pages 1151-1160, 2019.
[39] Alexander Strehl, Lihong Li, and Michael Littman. Reinforcement learning in finite mdps: Pac analysis. Journal of Machine Learning Research, 10(11), 2009.
[40] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
12

---

[41] Ambuj Tewari and Peter L. Bartlett. Optimistic linear programming gives logarithmic regret for irreducible mdps. In NIPS, pages 1505-1512. Curran Associates, Inc., 2007.
[42] Andrea Tirinzoni, Matteo Pirotta, and Alessandro Lazaric. A fully problem-dependent regret lower bound for finite-horizon mdps. arXiv preprint arXiv:2106. 13013, 2021.
[43] Andrea Tirinzoni, Matteo Pirotta, Marcello Restelli, and Alessandro Lazaric. An asymptotically optimal primal-dual incremental algorithm for contextual linear bandits, Advances in Neural Information Processing Systems, 33:1417-1427, 2020.
[44] Damianos Tranos and Alexandre Proutière. Regret analysis in deterministic reinforcement learning. In CDC. IEEE, 2021.
[45] Yu V Voitishin. Algorithms for solving for the minimal flow in network. Cybernetics, 16(1)1311-33, 1980.
[46] Andrew Wagenmaker, Max Simchowitz, and Kevin G. Jamieson. Beyond no regret: Instance- dependent PAC reinforcement learning. In Conference On Learning Theory (COLT), 2022.
[47] Po-An Wang, Ruo-Chun Tzeng, and Alexandre Proutiere. Fast pure exploration via wolfe. In Thirty-Fiftt Conference on Neural Information Processing Systems, 2021.
[48] Haike Xu, Tengyu Ma, and Simon S Du. Fine-grained gap-dependent bounds for tabular mdps via adaptive multi-step bootstrap. arXiv preprint 20X1v 2021.
[49] Ming Yin and Yu-Xiang Wang. Towards instance-optimal offline reinforcement learning with pessimism. In NeurIPS, 2021.
[50] Andrea Zanette, Mykel J. Kochenderfer, and Emma Brunskill. Almost horizon-free structure- aware best policy identification with generative model. NeurIPS. pages 5626-5635, 2019.
[51] Xuezhou Zhang, Yuzhe Ma, and Adish Singla. Task-agnostic exploration reinforcement learning. In NeurlPS, 2020.
[52] Zihan Zhang, Simon Du, and Xiangyang Ji. Near optimal reward-free reinforcement learning.
In International Conference on Machine Learning, (ICML), 2021.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See the discussion section.
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our results are theoretical and the paper is not oriented towards specific application, so wider broader impact discussion is not applicable.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] These are stated in the preamble of every Theorem.
(b) Did you include complete proofs of all theoretical results? [Yes] See the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material as URL)? [Yes] See the appendix.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See the appendix.
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See the appendix.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "elQelNznvmj", "reviewer": "Reviewer_SFoB", "summary": "This paper studies PAC reinforcement learning, where an agent is required to identify an $\\epsilon$-optimal policy with probability $1-\\delta$. The instance-dependent complexity remains elusive in episodic Markov decision processes (MDPs). In this paper, the nearly matching upper and lower bounds on the sample complexity of PAC RL in deterministic episodic MDPs with finite state and action spaces. In particular, our bounds feature a new notion of sub-optimality gap for state-action pairs that we call the deterministic return gap. The design and analyses employ novel ideas, including graph-theoretical concepts (minimum flows) and a new maximum-coverage exploration strategy.", "questions": "I have already provided all the comments in above. ", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strgenths** This paper provides fine-grained solution for PAC reinforcement learning with the deterministic MDP setting. The Proposed algorithm is based on the elimination rule and the resulting complexity is expressed in terms of min flow with linear program formulation. The experiment is motivate. \n\n**Weakness**\n\n- The claimed optimality actually differs from the upper bound by a factor of $H^2$, therefore the gap is still there. While notice the discussion about this from 327-332, I still wondering if it is possible to improve horizon dependence for EPRL? Current analysis seems based on Hoeffding's technique eon(5), could some (empirical) Bernstein bonus be designed  for EPRL?\n\n- The key procedure for EPRL is the policy elimination. How do you conduct efficient procedure for this elimination step to make algorithm practical? Especially the policy set can be exponential large?\n\n- Deterministic MDP is a simpler setting comparing to stochastic MDPs since each state action only needs to be experienced and the problem size is $SA$ (instead of $S^2A$ for the stochastic case). Hence, it is expected to have faster convergence than the general tabular MDP problem. How do you interpret the $O(\\frac{SAH^2}{\\epsilon^2})$ sample complexity as the optimal complexity for deterministic MDP? Is there a minimax lower bound for that? Indeed, in the offline case, it has been noted learning deterministic MDPs can have faster convergence with rate $\\frac{1}{n}$ instead of the standard statistical rate $\\sqrt{\\frac{1}{n}}$ due to its instance dependent nature [Yin&Wang,21]. I believe it is very necessary to refer [Yin&Wang,21] and discuss potential connections to the current work, for example, can instance-dependent online RL also achieve smaller regret comparing to the standard $\\sqrt{T}$?\n\n[Yin&Wang,21] Towards Instance-optimal Offline Reinforcement Learning with Pessimism, NeurIPS 21.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Wl_zb_b4WsC", "reviewer": "Reviewer_n7wX", "summary": "This paper studies instance-dependent optimality of PAC reinforcement learning in tabular deterministic episodic MDP. \nIt first introduces a new notion of sub-optimality gap called deterministic return gap, then characterizes an instance-dependent lower bound in terms of this new definition. The paper also proposes an algorithm based on maximum coverage sampling and confidence-based elimination, and prove that it can match the lower bound up to a $H^2$ factor. Finally, the paper also provides empirical evaluation on synthetic MDPs.  \n\n", "questions": "\nHere are some question that I hope the authors can answer in the rebuttal. \n\n1. There is a factor $H^2$ gap between upper and lower bound. It seems to be the mismatch is caused by the lower bound as it is hard to get explicit dependence on the $H$ factor (because the lower bound is between max and sum over all horizons). Is there a room to improve this? \n\n2. How can the lower bound be generalized to the stochastic setting? I guess most part of the analysis (or the high level strategy) will remain unchanged. Basically one only needs to argue for the KL decomposition used in the proofs in Section C. But I am not sure if there are other difficulties. \n\nI also have some small suggestions. \n\n1. The notations can be improved somehow. For example, what's $n^\\tau_h(s,a)$ in equation (3)? What is $\\hat{pi}$ in line 727? Maybe all of these definitions are given somewhere in the paper, but it's hard for the readers to check back and forth to find them. After reading carefully I can understand the meaning of the notations, but it will be very helpful if the authors can add a some explanation in the proof. \n\n2. Lemma 1 from Kaufmann et al., 2016 has been used quite often in the proof of lower bound. Maybe it's helpful to include that in the appendix for completeness? \n\n3. Some discussion in the main paper about how to prove instance-dependent lower bound will be useful. ", "limitations": "Please see the above section. ", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\nI vote for acceptance as this paper presents solid contributions and novel proving techniques. \n\nInstance-dependent analysis is a very important topic in RL theory and this paper provides some really contributions. In general I really enjoying reading this paper. One of the main contribution is to include graph-theoretical concepts in the lower bound analysis: it first proves a lower bound on minimum number of visitation for each state-action pair, the instance-dependent lower bound follows immediately by realizing that the visitation counts follows a feasible flow. I think this novel technique also has potential application in  other analysis of RL problems. \n\nWeakness:\n\nSome notations and definitions can be improved. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "K9vM1WdefQH", "reviewer": "Reviewer_vy1w", "summary": "This work studies the PAC RL problem in the tabular finite horizon setting for deterministic transition MDPs. The paper derives instance dependent lower bounds and an algorithm which nearly matches the lower bounds.", "questions": "Given the discussion regarding computing a minimum policy cover through min-flow/max-cut (Algorithm 2) and the fact that once all paths to a state-action pair are eliminated, e.g., by eliminating all incomming edges into the state-action pair, will Algorithm 3 ever select a policy which visits the state-action pair with no incomming edges? Further, will Algorithm 1 play a policy which visits such a state-action pair?\n\nDo the authors think they can derive a meaningful lower bound, maybe in terms of a min-flow LP, for the setting of bounded rewards?\n\n", "limitations": "This work is theoretical in nature and future societal impacts are hard to judge.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1.) Originality -- the paper shows some interesting results in terms of relating the MaxCoverage function in Algorithm 1, to the StaticMaxCoverage in Algorithm 3. In particular the observation that the MaxCoverage function behaves similarly to computing a minimum cover of the remaining (not eliminated) state-actions pairs and playing according to this cover (as done in the StaticMaxCoverage) is interesting and could potentially lead to imporved PAC RL algorithms for more general settings.\n\n2.) Quality -- the paper is technically sound and provides some interesting new ideas as mentioned above. Further, the paper improves on prior work lower bounds by a polynomial factor of the horizon.\n\n3.) Clarity and significance -- the paper is well written and mostly clear and easy to understand.\n\nWeaknesses:\n\n1.) Originality -- while the authors claim to propose a new notion of sub-optimality gap, this notion already exists in prior work up to a normalization factor of horizon. The novel contributions of the paper seem to mostly be in terms of removing spurious factors of horizon in upper and lower bounds from prior work. It is worth mentioning that the lower bound stated in Theorem 1 can not be directly compared to regret minimization lower bounds in prior work as the regret minimization lower bounds are asymptotic and regret minimization and PAC RL are not really aligned in their objectives as pointed out by Wagenmaker et al. 2022.\n\n2.) Clarity and significance -- I do not find the claims of matching upper and lower bounds true. It is important to note that Theorem 1 holds in a different setting from Theorem 3, that is in Theorem 1 there are no assumptions made about boundedness of the rewards, and in fact this is a very important part of the proof, making the result similar in spirit to the lower bound in Theorem 4.5  (Dann et al. 2021). The results in Theorem 3, in my understanding, hold for the more standard setting of bounded rewards. It is important to note that there could be a large gap between the two settings, making the claims of matching upper and lower bounds inaccurate. In particular, for the bounded rewards setting, there exist MDPs in which state-action pairs need not be visited even once for to be eliminated. This is due to the fact, that it is possible to eliminate all actions on paths to such state-action pairs before ever visiting such state-action pairs and hence there is no alternative MDP as in Lemma 8 of the current paper.\n\nGiven that the paper does not really establish lower bounds in the more interesting setting of bounded rewards and the upper bounds mostly seem to remove horizon dependent factors, I am unsure of how strong the contributions of this work are.\n\nReferences: \n\nWagenmaker, Andrew J., Max Simchowitz, and Kevin Jamieson. \"Beyond no regret: Instance-dependent pac reinforcement learning.\" Conference on Learning Theory. PMLR, 2022.\n\nDann, Christoph, et al. \"Beyond value-function gaps: Improved instance-dependent regret bounds for episodic reinforcement learning.\" Advances in Neural Information Processing Systems 34 (2021): 1-12.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "A_FFWBpL6Zs", "reviewer": "Reviewer_ELtb", "summary": "This paper studies PAC RL in tabular deterministic MDPs with known transitions but unknown (stochastic) rewards. An instance-dependent lower bound is presented which bounds the sample complexity in terms of the solution to a min-flow problem where the edge function is related to (the inverse) of a newly-defined deterministic return gap. A new algorithm is presented (EPRL) which is worst-case minimax optimal and matches the instance-dependent lower bound up to an H^2 term and logarithmic factors.", "questions": "- How much is the assumption that transitions are known matter? It seems like it is mainly used in Line 7 of the algorithm (to calculate Pi_{s,a,h}). Can the algorithm be modified or this assumption be removed? ", "limitations": "Limitations: See \"Strengths and Weaknesses\" section above.\n\nPotential negative societal impacts: N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Significance: There has been quite a lot of work lately on instance-dependent results for RL. This paper adds nicely to that body of work. Unfortunately, the setting is restricted to known deterministic transitions, and there is quite a large gap between the lower bound and the upper bound (H^2, ignoring logarithmic factors). As a first instance-dependent PAC result, this is still a nice result. The experimental results and the discussion is interesting as well. For want of time I have not checked the proofs for any mistakes.\n\nOriginality: The connections with minimum flow are interesting. The EPRL algorithm is novel. \n\nClarity: The paper is well written overall. One complaint is that, since the upper bounds and the lower bounds differ by a factor of H^2, the claims that the algorithm nearly matches the lower bound is misleading and should be modified. Another misleading claim is that the transition function can be learned \"with only an additional constant\" (this constant would give an additional dependence on SAH). Lastly, the claim that this is \"the first instance-dependent lower bound for the PAC setting in episodic MDPs\" is technically true, but there are some instance-dependent bounds for best-policy identification in the cited papers [44] and [4] (a restricted case of PAC), as well as several instance-dependent regret bounds in cited papers [13] and [40] which should be mentioned. \n\nSmaller complaints:\n- The notation and naming for the different instance-dependent functions are quite similar to each other, making it difficult to easily remember which is which (e.g. value gap, return gap, deterministic return gap, and the notations  \\Delta, \\tilde\\Delta, \\bar\\Delta). \n- The definition of Pi^t should be included in the pseudo-code of Algorithm 1 for readability\n\nTypos:\n- Line 182 \"mimixal optimal\"\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept