Sample Complexity Reduction via Policy Difference Estimation in Tabular Reinforcement Learning
Authors: Adhyyan Narang
Andrew Wagenmaker
Lillian J. Ratliff
Kevin Jamieson
Venue: NeurIPS 2024 spotlight (2024)
Keywords: pure exploration
tabular RL
bandits
best policy identification
instance-dependent
Primary area: bandits

Abstract: In this paper, we study the non-asymptotic sample complexity for the pure exploration problem in contextual bandits and tabular reinforcement learning (RL): identifying an $\epsilon$-optimal policy from a set of policies $\Pi$ with high probability. Existing work in bandits has shown that it is possible to identify the best policy by estimating only the *difference* between the behaviors of individual policies–which can have substantially lower variance than estimating the behavior of each policy directly—yet the best-known complexities in RL fail to take advantage of this, and instead estimate the behavior of each policy directly. Does it suffice to estimate only the differences in the behaviors of policies in RL? We answer this question positively for contextual bandits, but in the negative for tabular RL, showing a separation between contextual bandits and RL. However, inspired by this, we show that it *almost* suffices to estimate only the differences in RL: if we can estimate the behavior of a *single* reference policy, it suffices to only estimate how any other policy deviates from this reference policy. We develop an algorithm which instantiates this principle and obtains, to the best of our knowledge, the tightest known bound on the sample complexity of tabular RL.

edu Sample Complexity Reduction via Policy Difference Estimation in Tabular Reinforcement Learning
Adhyyan Narang University of Washington adhyyan@us. edu
Andrew Wagenmaker University of California, Berkeley ajwagen@berkeley edu
Lillian Ratliff University of Washington ratliffl@ux edu
Kevin Jamieson University of Washington j jamiesonccs. washington www.oonssss.wsiinttta..
Abstract
In this paper, we study the non-asymptotic sample complexity for the pure ex- ploration problem in contextual bandits and tabular reinforcement learning (RL): identifying an e-optimal policy from a set of policies II with high probability. Existing work in bandits has shown that it is possible to identify the best policy by estimating only the difference between the behaviors of individual policies- which can be substantially cheaper than estimating the behavior of each policy directly -yet the best-known complexities in RL fail to take advantage of this, and instead estimate the behavior of each policy directly. Does it suffice to estimate only the differences in the behaviors of policies in RL? answer this question positively for contextual bandits, but in the negative for tabular RL, showing separation between contextual bandits and RL. However, inspired by this, we show that it almost suffices to estimate only the differences in RL: if we estimate the be- havior of a single reference policy, suffices to only estimate how any other policy deviates from this reference policy. We develop algorithm which instantiates this principle and obtains, to the best our knowledge, the tightest known bound the sample complexity of tabular RL.
Introduction
Online platforms, such AirBnB, often try to improve their services by A/B testing different marketing strategics. Based on the inventory, their strategy could include emphasizing local listings versus tourist destinations, providing discounts for longer stays, de-prioritizing homes that have low ratings. In order to choose the best strategy, the standard approach would be to apply each strategy sequentially and measure outcomes. However, recognize that the choice of strategy (policy) affects the future inventory (state) of the platform. This complex interaction between different strategies makes it difficult to estimate the impact of any strategy, if it were to be applied independently. To address this, we can model the platform as an Markov Decision Process (MDP) with an observed state [17, 15] and finite of policies IT corresponding data by playing exploratory actions which will enable us to estimate the true value of each policy II. and identify the best policy from quickly as possible.
possible strategies. We wish collect
In addition to A/B testing, similar challenges arise in complex medical trials, learning robot policies to pack totes, and autonomous navigation in unfamiliar environments. All of these problems be formally modeled as the PAC (Probably Approximately Correct) policy identification problem in reinforcement learning (RL). An algorithm is said be (c, PPAAC if, given set of policies II, returns a policy π E II that performs within of the optimal policy in II, with probability 8. The
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

goal is to satisfy this condition whilst minimizing the number of interactions with the environment (the sample complexity).
Traditionally, prior work has aimed to obtain minimax or worst-case guarantees for this problem- guarantees that hold across all environments within a problem class. Such worst-case guarantees typically scale with the "size" of the environment, for example, scaling as (ppoly A, H)) for environments with S states, A actions, horizon H. While guarantees of this form quantify which classes of problems are efficiently learnable, they fail to characterize the difficulty of particular problem instances producing the same complexity on both "easy" and "hard" problems that share the same "size". This is not simply a failure of analysis recent work has shown that algorithms that achieve the minimax-optimal rate could be very suboptimal on particular problem instances [46]. Motivated by this, a variety of recent work has sought to obtain mnstance-depende complexity measures that capture the hardness of learning each particular problem instance. However, despite progress in this direction, the question of the optimal instance-depende complexity has remained elusive, even in tabular settings.
Towards achieving instance-optimaalty in RL, the key question is: what aspects of a given environment must be learned, in order to choose near-optimal policy? In the simpler bandit setting, this question has been settled by showing that it is sufficient to learn the differences between values of actions rather than learning the value of each individual action: is only important whether given action's 's value is greater or lesser than that of other actions. This observation can yield significant improvements in sample efficiency [37, 16, 13, 30J. Precisely, the best-known complexity measures in the bandit setting scale as:
11 (=(I(((TTX))) 1
inf max Teap EEl
(1.1)
A(T)2
where o= is the feature vector of action n, o² the feature vector of the optimal action, A(x) is the suboptimality of action Here, MTTexp) are the covariates induced by Texp. our distribution of exploratory actions. The denominator of this expression measures the performance gap between action π and the optimal action. The numerator measures the variance of the estimated (from data collected by Texp) difference in values between T"). The max over actions follows because to choose the best action, we have to rule out every sub-optimal action from the set of candidates II; the infimum optimizes over data collection strategies.
In contrast, in RL, instead of estimating the difference between policy values directly, the best known algorithms simply estimate the value of each individual policy separately and then take the difference. This obtains restance-dependee complexities which scale as follows [42]:
11 1 (Texp)) + 11,%% (xx
Σ inf max Teep NE
(1.2)
A(T)2
where 0% is the state-action visitation of policy π at step h. Since now the difference is calculated after estimation, the variance of the difference is the sum of the individual variances of the estimates of each policy, captured in the numerator of (1.2). Comparing the numerator of (1.2) to that of (1.1) begs the question: in RL can we estimate the difference of policies directly to reduce the sample complexity of RL?
To motivate why this distinction is important, consider the tabular MDP example of Figure 1. In this example, the agent starts in state $1, takes one of three actions, and then transitions to one of states 82, 83, 84. Consider the policy set IT (T1, 22), where ni always plays action 01, and na is identical, except plays actions 02 in the red states. If di E Assx denotes the state-action visitations of policy n. at time h 1, 2. then we see that "h oi since тi and T2 agree on the action in s1. But 65 + d as their actions differ on the red states.
Since these red states will be reached with probability at most 3e, the norm of the difference
(0] 0z a))²
+5 1 (TTxp)))
Ø2 (s,a)
Teep
8.0
significantly less than the sum of the individual norms
(s, + Φi ())
|| 1 (g( + 11 (
R (8,a)
Texp
2

---

3e
$2
2
0/
r2(83: a1)
1
dg
S4
r2(ss; ag) =
Figure 1: A motivating example for differences. The rewards for all actions other than the ones specified in the figure are O. Define policy set II = {Ti π2) so that Hı always plays d1, whereas T2 plays an on green states but d2 red states. The difference of their state-action visitation probabilities is only non-zero in states 83, 84 and are just O(e) apart.
Intuitively, to minimize differences Tex can explore just states $3, $4 where the policies differ, whereas minimizing the individual norms requires wasting lots of energy in state $2 where the two policies and the difference zero. Formally:
Proposition On the MDP and policy from Figure have that
inf max |055 (A
and inf max 11
o5 (2 S 15e
Wexp mEll
Reoep
Proposition shows that indeed, the complexity the form Equation (1.1) (generalized to RL) in terms of differences could be significantly tighter than Equation (1.2); in this case, it is factor of e? better. But achieving a sample complexity that depends on the differences requires more than just better analysis: it requires new estimator and algorithm exploit it.
Contributions. In this work, we aim to understand whether such a complexity is achievable in RL. Letting PI denote the generalization of (1.1) to the RL case that is, (1.2) but with | II, (Tow)))
replaced by |,, o%. ([ our contributions are as follows:
In the Tabular RL case, [2] recently showed that Pn lower bound on the sample complexity of RL by characterizing the difficulty of learning the unknown reward function; however, they did resolve whether is achievable when the state- transitions are unknown as well. We provide lower bound which demonstrates that (pn) is not sufficient for learning with state transitions.
We provide an algorithm PERP, which first learns the behavior a particular reference policy म, and then estimates the difference in behavior between and every other policy æ, rather than estimating the behavior of each directly.
In the case of tabular RI, we show that PERP obtains a complexity that scales with O(pn), ). in addition to extra term which measures the cost of learning the behavior of the reference policy म. We argue that this additional term critical to achieving instance-optimal guarantees RL, and that PERP leads improved complexities over existing work.
4. In the contextual bandit setting, we provide upper bound that scales (up lower order terms) as (pn)) for the unknown-context distribution case. This matches the lower bound from [30] for the known context distribution case, thus showing that Pn is necessary and sufficient in contextual bandits even when the context distribution is unknown. Hence, we observe a qualitative information - separation between contextual bandits and RL.
The key insight from our work that it does not suffice to only leam the differences between policy values in RL, but it almost suffices to-iff we can learn how single policy behaves, it suffices to leam the difference between this policy and every other policy.
2 Related Work
The reinforcement learning literature is vast, and here we focus on results tabular RI. and instance- dependent guarantees in RL.

---

Minimax Guarantees Tabular RL. Finite-time minimax-style results on policy identification in
tabular MDPs go back to at least the late 90s and early 2000s [24, 26, 25. 8, 21]. This early work was built upon and refined by variety of other works over the following decade [38, 4, 34, 39], leading poly(H)/e2) More recently. [10, 11,33) 33] have proposed algorithms which achieve the optimal dependence of OSSA (oly(H)/e2
up to works such as [28, 9], which establish sample complexity bounds of (
with [11, 33] also achieving the optimal // dependence. The question of regret minimization is intimately related to that of policy identification any low-regret algorithm can be used to obtain a near-optimal policy via an online-to-batch conversion [19]. Early examples of low-regret algorithms in tabular MDPs are [3, 4, 5, 48), with more recent works removing the horizon dependence or achieving the optimal lower-order terms as well [50. 51]. Recently, [6, 7] provide minimax guarantees in the multi-task RL setting as well.
in RL. While the problem of obtaining worst-case optimal guarantees in tabular RI. is nearly closed, we are only beginning to understand what types of instance-dependen guarantees are possible. In the setting of regret minimization, [35, 14] achieve instance-optimal regret for tabular RL asymptotically. Simchowitz and Jamieson [36] show that standard optimistic
Dustance-Dependee
algorithms achieve regret bounded as O(Es,a,h [..ss.a) ), result later refined by [47, 12]. In settings
log K
of RL with linear function approximation, several works achieve instance-depencee
regret guarantees [18, 44]. Recently, Wagenmaker and Foster [45] achieved finite-time guarantees on instance-optimal regret in general deeiiionnmmaking settings, a setting encompassing much of RL.
On the policy identification side, early works obtaining instance-dependent guarantees for tabular MDPs include [49, 20, 31, 32], but they all exhibit shortcomings such as requiring access to generative model or lacking finite-time results. The work of Wagenmaker et al. [46] achieves a finite-time rastance-dependent guarantee for tabular RL, introducing new notion of complexity, the gap-visitation complexity. In the special case of deterministic, tabular MDPs, Tirinzoni et al. [41] show matching finite-time instance instance-dependent upper and lower bounds. For RL. with linear function approximation, [42, 43) achieve restance-deendee
guarantees on policy identification, in particular, the complexity given in (1.2), and propose algorithm, PEDEL, which directly inspires our algorithmic approach. On the lower bound side, Al-Marjani et al. [2] show that fn is necessary for tabular RL, but fail close the aforementioned gap between pm and (1.2). We will show instead that this gap is real and both the lower bound of Al-Marjani et al. [2] and upper bound of Wagenmaker and Jamieson [42] are loose.
Several works on linear and contextual bandits are also relevant. In the seminal work, [37] posed the best-arm identification problem for linear bandits and beautifully argued-withon proof that estimating differences were crucial and that (1.1) ought to be the true sample complexity of the problem. Over time, this conjecture was affirmed and generalized [16, 13, 22]. This improved understanding of pure-exploration directly led to instance- instance-dependent optimal linear bandit algorithms for regret [29, 27J. More recently, contextual bandits have also been given similar treatment [40, 30].
3 Preliminaries and Problem Setting
Let ||~|| = xx _TAr Ax for any (z, A). We let E,, denote the probability measure induced by playing policy x in our MDP.
Tabular Markov Decision Processes. We study episodic, finite-horizon, time inhomogenous and tabular Markov Decision Processes (MDPs), denoted by the tuple (S, A, H, (Pa) (vr ) where the state space and action space are finite, H is the horizon, Pa. E R denote the transition matrix at stage h where [Phler.ea = P( s' s'|s,,
s,a, = a). and v4 (s, a) E p denote the distribution over reward stage h when the state of the system is and action a is chosen. Let Th (8 a) be the expectation of reward drawn from (8, a). We assume that every episode starts in state 81, and that 1/, and Pr, are initially unknown and must be estimated over time.
Let क = distribution over actions for the policy at (s, f);; when the policy is deterministic, (s(s) E A outputs a single action. An episode begins in state s1, the agent takes action @i ~~ π (31) and receives reward Ri vi (31, a1) with expectation ri (81, ai) ); the environment transitions to state $2 ~ Pa (8), a1). The process repeats until timestep H, at which point the episode ends and the agent returns to state $1. Let Vg (s) E, D = The (sw, ar) |sa =s. Vo the total expected reward, V := VT (so).
H denote a policy mapping states to actions, so that (s) E AA denotes the
4

---

The (sk ss. = 8, = =a] the amount of reward we expect to collect if we are in state s step h, play action a and then play policy iT for the remainder of the episode. Note that we can understand these functions as S and S A-A-dmmensinaa vectors respectively. We use V = Vo' when clear from context.
and
We call W E As the state visitation vector at step h for policy म, so that w (s) captures the probability that policy æ would land in state at step h during an episode. Let TTy E RSAXS denote the policy matrix for policy n, that maps states state-actions as follows
(T)() = T( = & (TT(())
Denote 67 E ASA as 0% == TA as the state-action visitation vector: 0% (s. a) measures the the probability that policy π would land in state and play action a at step during episode. From these definitions, it follows that [Pac9]] a = [Pa Fra = wh+1 For policy т, denote the covariance matrix at timestep h as As = E. 0% (8, ().)))))) (o.0)
(c, 8)C Best Policy Identification. For a collection of policies II, define '- arg max V as the optimal policy, V its value, and 6% as its state-action visitation vector. Let Amin = min V* V* in the case when n is unique, and otherwise Amin == O. Define A(T)
max(V* - V Amin J- Given e 2 0, 5 E (0, 1) an algorithm is said to be (c, if at a stopping time 7 of its choosing, it returns a policy से which satisfies (TT) S with probability 1 - 6. Our goal is to obtain an (e,5)-PAC algorithm that minimizes T. A fundamental complexity measure used throughout this work is defined as
10% 0% ( m
PIL inf max Keep TEll
for 1 - A
Σ 3,0
(Feap)
Texp Texa) (s,a)
where the infimum is over all exploration policies Texp (not necessarily just those in II). Recall that for c = 0, [2] showed any (c, 6PAAC algorithm satisfies B[r] 2 Pm log( 2.48
4 What is the Sample Complexity of Tabular RL?
In this section, we seek to understand the complexity of tabular RL. We start by showing that Pn is not sufficient. We have the following result. Lemma 1. For the MDP M and policy set I1 from Figure 1,
-10% +7 (maap)-
1. Σ h=l inf Texp max
< 15,
max ( AA))
2. Any (e, 8)-C algorithm must collect at least E [7] EM
1 log 2.45
I. samples.
Where does the additional complexity arise on the instance of Figure 1? As described in the introduction, and T2 differ only on the red states, and a complexity scaling as Pn quantifies only the difficulty of distinguishing [T] Ø2] on these states. Note that on this example σ1 plays the optimal action in state $3 and suboptimal action in state $4, and T2 plays a suboptimal action in sy and the optimal action in $4. The total reward of policy πi is therefore equal to the reward achieved at state 83 times the probability it reaches state 83, and the total reward of policy л2 is the reward achieved at state 84 times the probability reaches state 84. Here, pn would quantify the difficulty of learning the reward achieved at each state. However, it fails to quantify the probability of reaching each state, since this depends on the behavior at step 1, not step 2.
Thus, on this example, to determine whether Ti or T2 is optimal, we must pay some additional complexity to learn the outgoing transitions from the initial state, giving rise to the lower bound in Lemma 1. Inspecting the lower bound of [2], one realizes that the construction of this lower bound only quantifies the cost of learning the reward distributions {2% } and not the state transition matrices [Ph h-- On examples such as Figure 1, this lower bound then does not quantify the cost of learning the probability of visiting each state, which we've argued is necessary. We therefore conclude that, while pm may be enough for learning the rewards, it is not sufficient for solving the full tabular RL problem. Our main algorithm builds on this intuition, and, in addition to estimating the rewards, aims to estimate where policies visit efficiently as possible.
5

---

4.1 Main Result
Pn is not achievable as the sample complexity for Tabular RL, what is the best that we can do? In this section, we answer this question with our sample complexity bound; we later describe the algorithmic insights that enable us to achieve this result in the following section. First, for any n, i E II, we define
RT En (s) Q.. 7 (sw)))))
(4.1)
Now, state main result.
Theorem There exists an algorithm (Algorithm 1) which, with probability at least 1 26, finds an e-optimal policy and terminates after collecting most
1 0% 19l1AA An (Faxe)) -132
max (TT REll max ( log #
Cpoyy
Σ inf max Texp WEll
max [()))
max
[c3, A
min
episodes, for Cpoly (S A, H, log 1/6, log 11), Vvlog
log((
SH
and
Amin
log
Amm
Theorem shows that, up to terms lower-order in e and Amin Pn is almost sufficient, if we are willing pay for additional term scaling (xz, 't" "/)/A()))) Recognize the similarity of this term to the that from the performance difference lemma: if there were no square inside the expectation, the quantity (TT ) would be equal to ( However, the square may change the scaling in some instances. Below, Lemma 2 shows that there exist settings where the complexity of Theorem 1 could be significantly tighter than Equation (1.2), the complexity achieved by the PEDEL algorithm of [42]. We revisit the instance from Figure I to show this; recall from Lemma that the first term from Theorem is a universal constant for this instance.
Lemma 2. On MDP M and policy set 11 from Figure 1, we have:
1. max (U(TT")
SH
(())(T))
T (mosp)-1
2. Σ inf Texp max+em (a
2-
Furthermore, the complexity of Theorem never worse than Equation (1.2).
Lemma 3. For any MDP instance and policy set II. we have that
110% 0% 112 (
HU(T, x²) ((T))
1 11 (T (Texp))
max
Σ
inf max TEll
max A( A(T)2) max max()2A(())))
S
inf max
HEll maxfe? A(T)²)
7=
hml
We briefly remark on the lower-order term for Theorem 1, max 3757 Note that for small or
Cpoly
Amin this term will be dominated by the leading-ore order terms, which scale with minfe 2 A }. While we make no claims on the tightness of this term, we note that recent work has shown that some lower-order terms necessary for achieving instance-optimality [45].
4.2 The Main Algorithmic Insight: The Reduced- Variiacce Difference Estimator
In this section, we describe how we can estimate the difference between the values of policies directly, and provide intuition for why this results in the two main terms in Theorem 1. Fix any reference policy मे and logging policy (neither are necessarily in II). Here μ can thought of as playing the role of Texp- Or, can consider the A/B testing scenario from the introduction, where policy is taking random actions and one wishes to perform off off-po estimation over some set of policies II (17, 15). For any S, we define
(x) = w (s) w.f (s)
as the difference in state- visttvisit of policy æ from reference policy म, and 8% IRS as the vectorization of (s').

---

Policy selection rule. First, we describe our procedure of data collection and estimation. We collect K trajectories from and K₂ trajectories from p. and let { (s) denote the empirical state visitations from playing म. From the data collected by playing μ4, we construct estimates (P a)) s,,,,' of the transition matrices. Note that 1 (s) simply counts visitations, so that B[ (s) W (s)) (x)
R= for all h, 8. Define estimated state visitations for policy ı in terms of deviations from गे as Wg. wi + 5% Here, 07 is defined recursively as:
h- == O + PT -n)
Then, assuming, for simplicity, that rewards are known, we recommend the following policy:
î arg max DT TEll
where
D=== == (Th, T (rns (TA - )T)
Sufficient condition for cooptimality
Here, we show that if
Yπ E II,
D - 1 3
1 max(c,A(r))
(4.2)
then मे is e-optimal. First, write the difference between values of policies and म as:
:= Vo- - V0=h = -It (Th, T) - Σm (Ths tn
(4.3)
H (Ths Tx,7) (rh; (M TT TT)wW))
Then, it is easy verify that if D 1/3 ( then D= - D 0; hence, म + Hence, under Condition (4.2), either = x* or or DD - D S E. In the first case, clearly 7 is e-optimal. In the second case, add and subtract terms write
< D - - 5=* - + 15
Dd S 3 D D
3
The last inequality follows since ã maximizes D= Hence, मे would be e-optimal in this case as well.
Sample complexity. Now, we characterize how many samples must be collected from μ and # in order to meet Condition (4.2). After dropping some lower-order terms and unrolling the recursion (see Section A for details), observe that
4/ 07 ~ (Ph - PoT 0%, + PA ( - + Pa n (6, 5%
- [[ P)TT,) ((P: Pa) o4) + Ps (Tx Tt) wf))
After manipulating this expression bit more, we observe that
(rh, nh (og 0) Σ (P Pk)(OT x%) Pk(TT Tx) w())
k=
Recognizing 0% Th + P Vh++
- - = Σ (Th nh (3 -7)) + (rh, (Tr - - wxli
H Σ (VTT (Ph - Ph)(oT oi)) + (rn + PN Vitti (TT = wiii
We can bound this as:
(8, a))
2
12
Σ (Q((s (s))
K
/ (a)-
U(
2
+
K₁
K2
7

---

the standard Here, we applied Bernstein's 's inequality and observed that E. V (s) S H² Now, we have that if
H2 1,
0% 11 ( max (
U π well max (2, ( (T)
max K P
and
K 2 max
(4.4)
TEll
h=0
then Condition (4.2) holds. Notice that up to H and log(-) factors, this is precisely the sample complexity of Theorem 1 if we set x² and minimize over all logging/exploration policies /// T Texp- Note that, if V denotes the average reward collected from rolling out से K2 times, then
H2 IV V0 K;
by Hoeffding's inequality. Thus, one could use 7 D= + V as effective off-policy estimator. Likewise, D" D'' an effective estimator for Vi"" - Vo
This calculation (elaborated on in Appendix A) suggests that our analysis is tight, and clearly illustrates that the (TT #) term arises due to estimating the behavior of the reference policy w The UTT, т) term is, to the best of our knowledge, novel in the literature. More precisely, this term corresponds to the cost of estimating where स visits, if our goal is to estimate the difference in value between policy л and म. If, for a given state, the actions taken by π and मे achieve the same long-term reward, then it is not critical that the frequency with which स visits this state estimated, as does not affect the difference in values between and म; if the actions take by and ø do achieve different long-term reward at s, then we must estimate the behavior each policy at this state. This is reflected by the term inside the expectation of (TT,, R); this will be O in the former case, and scale with the difference between long-term action reward in the latter case.
Additionally, note that if we had offline data from some policy n, that had been played for a long time, so that K3 co, then we would only incur the K₁. term; this is precisely pr., but with x² replaced with our reference policy स in the numerator.
5 Achieving Theorem 1: PERP Algorithm
While the above section provides intuition for where the terms Theorem come from, it does not lead to practical algorithm. This is because the desired number of samples in Equation (4.4) are in terms of unknown quantities: {1 - o (l (TT), (T, #)), which depend on our unknown environment variables Uh, Ph: hence, we would not know how many samples to collect. In this
section, we propose algorithm that will proceed in rounds, successively improving estimates of these quantities. Define
(T, := B.r. (( (80, TT..s,T.6 TT(s)) Q (sh, T (8)))))
(5.1)
where Ee denotes the expectation induced playing policy n' on the MDP with transitions Pe. and Qi,, denotes the Q-function of policy æ on this same MDP. To compute Pr,m,
estimator: (s'
(s' | ss
Ne..s,,.s") for (e, a) and Ne. (s, a, s') the visitation counts in EDD (i.)
We set (e a) = US) if (e, a) = O. The analogous estimator is used to estimate ře. The quantity 07 of is estimated as in the previous section: (TT #1.1 ) + TT
Algorithm proceeds in epochs. It begins with a policy set IT, which contains all policies of interest, ЛI. It then gradually begins refine this policy set, seeking to estimate the difference in values between policies in the set up to tolerance < = 2- To achieve this, it instantiates the intuition above. First, it chooses reference policy मe. then running this estimate sufficient number of times to estimate wx at Given this estimate, it then seeks to estimate 5% for each π in the active set of policies, IT, by collecting data covering the directions (T, ) T for all Л,, To efficiently collect this covering data, on line 12, we run a data collection procedure first developed in [42]. Finally, after estimating each 5%, it estimates the differences between policy values as in (4.3), and eliminates suboptimal policies.
The computational complexity of PERP poly (8, A, 1/e, (ol.(o((/)))) The primary contributor to the computational complexity is the the use of the Franke- Wolfe algorithm for experiment design in the OPTCOV subroutine. Lemma 37 from Wagenmaker and Pacchiano [43] shows that the number of iterations of the Tranke-Wolfe algorithm is bounded polynomially in the problem parameters,
8

---

Algorithm PERP: Policy Elimination with Reference Policy (informal)
Require: tolerance e, confidence 6, policies II 1: 1 <- II, Po < arbitrary transition matrix
2: for / ===1, 1,,,3...... [ogg2 do
3: Set ce + 2
4: // Compute new reference policy
5: Compute L, r') in (5.1) for all (IT, x²) ) ll
6: Choose म. + minæenf max Σn=1 (e-,,
7: Collect the following number of episodes from He and store in dataset D
( max (0)-1(T.51) log H
8: Compute { (s) using empirical state visitation frequencies in Dzof // Estimate Policy Differences
9:
10: Initialize 57 +-0
for h = I..... do Run OPTCOV (Algorithm 3) to collect dataset such that:
12:
sup (1 Te,,) + T A nelle
S 5 for Aen En
and Be O( Olvlog SH2 11//88)
Use DED to compute (e. a) and Pr,
Compute 87 0,1+1 (T, Te, 1e end for
16:
// Eliminate suboptimal policies
17:
Compute D= (T) + (Fe Th + Et (Tr, Te,n)
Update πT = TAM E [l maxx' Di (T²) D+c(TT) > 8c./ }
18:
19:
if [T
then return 1T+1
20:
end for
return any π E 11++1
and from the definition of this procedure given Wagenmaker and Pacchiano [43], we see that each iteration of Maake-WWlff, has computational complexity polynomial in problem parameters. We omit several technical details from Algorithm for simplicity, but present the full definition in Algorithm 2.
6
When is pn Sufficient?
Our results so far show that PT not in general sufficient for tabular RL, In this section, we consider several special cases where it is sufficient.
Tabular Contextual Bandits. The tabular contextual bandit setting is the special of the RL setting with H = 1 and where the initial action does not affect the next-state transition. Theorem 2.2 of Li al. [30] show that the rewards distributions v(s,, a) are Gaussian for each (s, a), where here denotes the context, any (0, PPC algorithm requires at least samples. Crucially, however, they assume that the context distribution this case corresponding to the initial transition Pi-is known. Their algorithm makes explicit use of this fact, using this to estimate the value of Φ² The following result shows that knowing the context distribution not critical we can achieve complexity of O(p)) without this prior knowledge.
Corollary 1. For the setting of tabular contextual bandits, there exists an algorithm such that with probability at least 1 26, as long II contains only deterministic policies, it finds e-optimal

---

policy and terminates after collecting at most the following number of samples:
inf 110² x= 11 (moop) Teep alll max (()))
Opoly
3 log
Amin Ve
max max/e5/3, A 5/3
for Opoly poly([S), A, log 1/6, log 1/(mmin Ve), log [I] and CV log
S|I
Amin
The theorem is proved in Appendix D, and follows from the application of our algorithm PERP the contextual bandit problem. The key intuition behind this result is that, in the contextual case:
UTT, #t Es,,, [(ri Tı (s)) rı (s, #1 (s)) I Bg-r, [T(T * (s)))]
It is then possible show that, since Texp only has choices of which actions taken (and cannot affect the context distribution), this can be further bounded by inf xesp -
This is not true the full MDP case, where our choice of exploration policy in Texp could make inf 10
3² 3 [ significantly smaller than U (TT, F) (as is the case in Lemma 2). Hence, we observe that the cost of learning the contexts is dominated by that of learning the rewards in the case of contextual bandits. This is the opposite of tabular RI, where our complexity from Theorem is unchanged (as seen in Section 4.2) even if we knew the reward distribution. This shows that there is a distinct separation between instance-optimal learning in tabular RL vs contextual bandits.
Transitions. In the special case of MDPs where the transitions do not depend on the actions selected, the complexity simplifies to O(pT). Note that this exactly matches (up to lower order terms) the lower bound from [2].
MDPs with Action-Independe
Corollary 2. Assume that all Pp. are such that Pa (, a) = (s d') for all (a, a') E A. Then, (s''ss,,
with probability at least 1 28, PERP (Algorithm 2) finds an e-optimal policy and terminates after collecting at most the following number of episodes:
H
10 17 (T
Opoly
inf max Teep NEll
32 +
max ((T))
max (65/3
A Amn)
5/3
for Cpoly, 3 as defined in Theorem 1.
The intuition for Corollary 2 is similar to that of Corollary 1, and proved in Appendix E.
7 Discussion
In this paper, we performed a fine-grained study of the instance-dependent complexity of tabular RL. We proposed a new off- off-policy estimator that estimates the value relative to a reference policy. We leveraged this insight to close the instance-dependent contextual bandits problem and obtained the tightest known upper bound for tabular MDPs.
L Limitations and Future work One limitation of the present work is that PERP, in it's current form, would be too computationally expensive to run for most practical applications: enumerating the policy set IT is often intractable, but works in contextual bandits have avoided this issue by only relying on argmax oracles over this set [1, 30]; an interesting direction of future work would be to extend this technique to tabular RL. Extending the results from this paper to obtain refined instance-dependen bounds for linear MDPs and general function approximation is an exciting direction as well.
The new estimator and its improved sample complexity raise additional theoretical questions. Our U(r,a))
upper bound has unfortunate low order terms; can these be removed? Can one show that max (x))) unavoidable for all MDPs in general, thereby matching our upper bound? As discussed above, few works have proven gap-dependent regret upper bounds, but we are unaware of any matching lower bounds besides over restricted classes of MDPs; can our estimator involving the differences result in even tighter instance-dependent regret bounds for MDPs?
Acknowledgments
AN and IJR are supported in part by ONR YIP N0001 42012571 and NSF CAREER 1844729. AN was supported, part by the Amazon Hub Fellowship at the University of Washington. KJ and AW were funded in part by NSF CAREER 2141511 and NSF TRIPODS 2023239.
10

---

References
[1] Alckh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire. Taming the monster: A fast and simple algorithm for contextual bandits. In International Conference on Machine Learning, pages 1638-1646. PMLR, 2014.
[2] Aymen Al-Marjani, Andrea Tirinzoni, and Emilie Kaufmann. Towards instance-optimality in online pac reinforcement learning. arXiv preprint 1.Ki::33/10056... 2023.
[3] Peter Auer and Ronald Ortner. Logarithmic online regret bounds for undiscounted reinforcement learning, Advances in neural information processing systems, 19, 2006.
[4] Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
[5] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263-272.
PMLR, 2017.
[6] Avinandan Bose, Mihaela Curmei, Daniel L. Jiang, Jamie Morgenstern, Sarah Dean, Lillian J. Ratliff, and Maryam Fazel. Initializing Services in Interactive ML Systems for Diverse Users. arXiv preprini 2rXiv:2312..1888 2023.
[7] Avinandan Bose, Simon Shaolei Du, and Maryam Fazel. Offline Multi-task Transfer RL with Representational Penalization. arXiv preprint arXiv:2402.12570 2024.
[8] Ronen Brafman and Moshe Tennenholtz. R-max-a general polynomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research, 310e)):213-331, 2002.
[9] Christoph Dann and Emma Brunskill. Sample complexity of episodic fixed-horizon reinforce- ment learning. Advances in Neural Information Processing Systems, 2015.
[10] Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 2017.
[11] Christoph Dann, Lihong Li, Wei Wei, and Emma Brunskill. Policy certificates: Towards accountable reinforcement learning. In International Conference on Machine Learning, pages 1507-1516. PMIR, 2019.
[12] Christoph Dann, Teodor Vanislavov Marinov, Mehryar Mohri, and Julian Zimmert. Beyond value-function gaps: Improved instance- cestance-dependent regret bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
[13] Rémy Degenne, Pierre Ménard, Xuedong Shang, and Michal Valko. Gamification of pure exploration for linear bandits. In International Conference on Machine Learning, pages 2432- 2442. PMLR, 2020.
[14] Kefan Dong and Tengyu Ma. Asymptotic instance algorithms for interactive decision making. arXiv preprint arXiv:2206.02.33 2022.
[15] Vivek Farias, Andrew Li, Tianyi Peng, and Andrew Zheng. Markovian interference in experi- ments. Advances Neural Information Processing Systems, 35:535-544 2022.
[16] Tanner Fiez, Lalit Jain, Kevin Jamieson, and Lillian Ratliff. Sequential experimental design for transductive linear bandits. Advances in neural information processing systems, 32, 2019.
[17] Peter W Glynn, Ramesh Johari, and Mohammad Rasouli. Adaptive experimental design with temporal interference: A maximum likelihood approach. Advances in Neural Information Processing Systems, 33: 150444 2020.
[18] Jiafan He, Dongruo Zhou, and Quanquan Gu. Logarithmic regret for reinforcement learning with linear function approximation. International Conference on Machine Learning, 2021.

---

[19] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is q-learning provably ef- ficient? In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pages 4868 4878, 2018.
[20] Anders Jonsson, Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Edouard Leurent, and Michal Valko. Planning in markov decision processes with gap-dependent sample complexity. Advances in Neural Information Processing Systems, 2020.
[21] Sham Machandranath Kakade. On the sample complexity of reinforcement learning. PhD thesis, UCL (University College London), 2003.
[22] Julian Saazusaueels, Lalit Jain, and Kevin Jamieson. An empirical process approach to the union bound: Practical algorithms for combinatorial and linear bandits. Advances in Neural Information Processing Systems, 13:10711-10382 2020.
[23] 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 1-42, 2016.
[24] Michael Kearns and Satinder Singh. Finite-sample convergence rates for q-learnin and indirect algorithms. Advances in neural information processing systems, 11, 1998.
[25] Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Machine learning, 49(2):209-23) 232, 2002.
[26] Michael Kearns, Yishay Mansour, and Andrew Ng. Approximate planning in large pomdps via reusable trajectories. Advances in Neural Information Processing Systems, 12, 1999.
[27] Johannes Kirschner, Tor Lattimore, Claire Vernade, and Csaba Szepesvári. Asymptotically optimal information-directtdd sampling. In Conference on Learning Theory. pages 2777 2821. PMLR, 2021.
[28] Tor Lattimore and Marcus Hutter. Pac bounds for discounted mdps. International Conference on Algorithmic Learning Theory, pages 320-334. Springer, 2012.
[29] Tor Lattimore and Csaba Szepesvari. The end of optimism? an asymptotic analysis of finite- armed linear bandits. In Artificial Intelligence and Statistics, pages 728-737. PMLR, 2017.
[30] Zhaoqi Li, Lillian Radiff, Houssam Nassif, Kevin Jamieson, and Lalit Jain. Instance-optimal PAC algorithms for contextual bandits. Advances in Neural Information Processing Systems, 2022.
[31] Aymen Al Marjani and Alexandre Proutiere. Adaptive sampling for best policy identification in markov decision processes. International Conference Machine Learning, 2021.
[32] Aymen Al Marjani, Aurelien Garivier, and Alexandre Proutiere. Navigating to the best policy in markov decision processes. Neural Information Processing Systems, 2021.
[33] Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration in reinforcement learning. International Conference on Machine Learning, 2021.
[34] Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008
[35] Jungseul Ok, Alexandre Proutiere, and Damianos Tranos. Exploration in structured reinforce- ment learning, arXiv preprint 18Xiv:1806.000 2018.
[36] Max Simchowitz and Kevin G Jamicson. Non-asymptotic gap-dependent regret bounds for tabular mdps. Advances in Neural Information Processing Systems, 32, 2019.
[37] Marta Soare, Alessandro Lazaric and Rémi Munos. Best-arm identification in linear bandits. Advances in Neural Information Processing Systems, 27, 2014.
12

---

[38] Alexander L Strehl, Lihong Li, Eric Wiewiora, John Langford, and Michael L Littman. Pac model-free reinforcement learning. In Proceedings of the 23rd international conference on Machine learning, pages 881 881-88 1-888, 2006.
[39]
Alexander L Strehl, Lihong Li, and Michael L Littman. Reinforcement learning in finite mdps: Pac analysis. Journal of Machine Learning Research, 10(11), 2009.
[40] Andrea Tirinzoni, Matteo Pirotta, Marcello Restelli, and Alessandro Lazaric. An asymptotically optimal primal-dual incremental algorithm for contextual linear bandits. Neural Information Processing Systems, 2020.
[41] Andrea Tirinzoni,
Aymen Al-Marjani, and Emilie Kaufmann. Near instance-optimal pac reinforcement learning for deterministic mdps. Neural Information Processing Systems, 2022.
[42] Andrew Wagenmaker and Kevin G Jamieson. Instance-dependent near-optimal policy identifi- cation in linear mdps via online experiment design. Advances in Neural Information Processing Systems, 35:5968-500 -5911, 2022.
[43] Andrew Wagenmaker and Aldo Pacchiano. Leveraging offline data in online reinforcement learning. International Conference of Machine Learning, 2023.
[44] Andrew Wagenmaker, Yifang Chen, Max Simchowitz, Simon S Du, and Kevin Jamieson. First- order regret in reinforcement learning with linear function approximation: A robust estimation approach. International Conference of Machine Learning. 2022.
[45] Andrew J Wagenmaker and Dylan Foster. instance-optimality interactive decision making: Toward non-asymptotic theory. In The Thirty Sixth Annual Conference on Learning Theory, pages 1322-14722 PMLR, 2023.
[46] Andrew dependent pac reinforcement learning. In Conference Learning Theory, pages 358-418. PMLR, 2022.
Wagenmaker, Max Simchowitz, and Kevin Jamieson. Beyond no regret: Instance-
[47] Haike Xu, Tengyu Ma, and Simon S Du. Fine-grained gap-dependent bounds for tabular mdps via adaptive multi-step bootstrap. Conference Learning Theory, 2021.
[48] Andrea Zanette and Emma Brunskill, Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312. PMLR, 2019.
[49] Andrea Zanette, Mykel J Kochenderfer, and Emma Brunskill. Almost horizon-free free structure- aware best policy identification with generative model. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[50] Zihan Zhang, Xiangyang Ji, and Simon Du. Is reinforcement learning more difficult than bandits? mear-optimal algorithm escaping the curse of horizon. Conference Learning Theory, 2021.
[51] Zihan Zhang, Yuxin Chen, Jason D Lee, and Simon S Du. Settling the sample complexity of online reinforcement learning. arXiv preprint arXiv:2307.13556 2023.
13

---

Contents
Introduction
2 Related Work
3 Preliminaries and Problem Setting
4 What is the Sample Complexity of Tabular RL?
4.1
Main Result
4.2 The Main Algorithmic Insight: The Reduced- Variance Difference Estimator
5
Achieving Theorem 1: PERP Algorithm
When is pn Sufficient?
7 Discussion
10
A Understanding the origins of UTx, T))
15
Tabular MDPs: Comparison with Prior Work and Lower Bounds
17
B.1 Comparison with complexities from prior work
18
B.2
Lower bound
20
Tabular MDP Upper Bound
20
C.1
Notation
20
C.2
Technical Results
22
C,3 Concentration Arguments and Good Events
24
C.4 Estimation of Reference Policy and Values
30
C.5 Conrectness and Sample Complexity
35
D Tabular Contextual Bandits: Upper Bound
37
MDPs with Action-Indeeendent Transitions
40
Tabular Franke Wolfe
41
F.I
Data Conditioning..
44
F.2
Online Frank-Wolfe
47
F3
Pruning Rarchto-Reach States
49
14

---

Notation
Description
S
State space
Action space
H
Horizon
Ph
Transition matrix at stage
Ph
Distribution over reward at stage h
(s,))a)
Expected reward at stage for state and action a
Policy
Set of candidate policies
(s)s)
Distribution over actions for policy state and stage h State visitation vector at step for policy π Policy matrix for policy step h State-action visitation vector for policy и at step h Expected covariance matrix timestep h for policy Q-value function for policy π at state action a, and step h Value function for policy state and step h. Value of policy π
Th
OR
(A)
Q (s.a)))
V (8)
T
Optimal policy within 11 Suboptimality of policy π Maximum probability of reaching state s step over all policies Context space (for contextual bandits)
A(T)
(s)
C
Context distribution (for contextual bandits) Reward parameters (for contextual bandits)
O
Pn
Complexity measure based on feature differences Reference policy
Te
8
Difference state visitation between policy ı and reference policy step Difference in value between policy and reference policy Expected squared difference Q-values between policies т and nt at step h Set of reachable states at epoch
Dn, (TT)
Un m')
S
skeop
Synif
Minimum reachability threshold at epoch
Tolerance for experiment design epoch
Fexp
Be.
Confidence parameter at epoch
ne, K
Number of samples and minimum exploration at epoch
Deh
Dataset collected during exploration PERP
Dr
Dataset collected from reference policy
Table
Table of notation used the paper
A Understanding the origins of ( 7
This section is inspired by the exposition Soare et al. [37] for justifying the sample complexity of linear bandits. Fix reference policy म and some (stochastic) logging policy For K E N to determined later, roll out म K times and compute the empirical state visitations (s)
K EEEE. Es,t 1s =s}. Also roll out K times and compute the empirical transition probabilities Pr s. = ΣK ΣK ((()),)))=(+a))
1
For any x + म. use (s'(ss a) he...".. to compute 0g (s). With o, = wh+t wh+1 = PATAWR u = P + PA(TT, #n) set
H
H (he T wf - + w Σ
D(T) = ViT V
Σ
(Th T + (rhs (TT TI w))
h=l
and also define the empirical counterparts
34 = Pr & + PA( #,) with
H Σ
D(T)
(nh m + (reo (T -.)))))
hml
15

---

f = arg ma D(T)), how large must K be to ensure that ß = x²' := arg max D(x) = arg ma V
Assume at time h 0 all policies are initialized arbitrarily in some state so so that Po(s' |s. a) simply defines the initial empirical state distribution at time h = 1. Let पे (50) w (so) We can then unroll the recursion for = 0, O..... H
h+1 0 = O + Ph - 22 57+1
= -Ph p + +Ph
(T) kn (T ( - w/,) PT (8% 6%.
+ (Pn - PT) (8% - 5% + (Pr PT) (w) - -wA)
Low order torms
~
(Pr
Po)
x + Pi(TTA - ( wx)) + PA - -0%)
h
Σ
II
Ph-- Øh- + Ph-i(TTh- Ah- An- - wh-1))
==0
j=h-i+1
h
h
= - II ((P PP) - -00) + PA - (00 - -w
K=
j=H
where we recall 0% Tuug. If cf+1 = (Pr- (T)(TTUEE +wg)+ + PE - +x)( - -wg) then
h-1
h-1
(rh, Th 16
(6
(Ths Th
II PSTT)Eati)
j=k+1
H
h-1
H-1
Σ (Th: Th
II PyTz)
Σ k=
k= 0 Am1+1
g=k+1
#-
Σ (VE,,, PP) - o%) + PE(TT: ( - -wf))
k=
Finally, we use these calculations to compute the deviation
- =
rh n (57 - -67)) + (Tp, (TA (n) - wxi)
Σ
(Vh+1 (Pr PP)(05 - Φi)) + (rh PT V Vi+
(TT (T
(ū -w())
(V (P%- - -PA)( - (b)) + +0 (Th - ( - -wx))
Σ Σ
V V (s,
h=0 s,a,"
H
- (T(s, wi
h=0
H-1
Viti (s))2 (s(
Σ
(0)(s) (()
(
1=0 8,0,s'
H-1
ΣΣ (Q, (s))
K
16

---

1 - 3e
a2
(2(33,
03
e2
01(1 =1
81
(2(44, ag) =
Figure 2: A motivating example for differences. All rewards other than the ones specified in the figure are O.
Applying Es V (s' S H², we observe that if
H Σ aa (0% /
K 2 min max H²
A(T)2
Σ, (Q7 TA (s)) - Q7 HA (s)) 2 (s)))
A(T)²
and we employ the minimizers μ, क to collect data, then D(T)= D(*) < ( and मे arg max ((T)= arg max,en D(T). Notice that up to H and log factors, this is precisely the sample complexity of our algorithm. A natural candidate for म is x* so that the first term matches the lower bound [2].
On the other hand, suppose we used the data from the logging policy y to compute the empirical state visitations Ti for all π E II and set â = arg max Ehzi (Th, TWg) =: VoT Using the same techniques as above, is straightforward to show that
Th h+1
w = TA ύ7, W
(Pr Pr. + PT ww + w()) PRTTE
= (Pr - w + (AT wh) + (Pr Ph TT W w/
Low order terms Ps 0
Σ
II PITT)(
PA-
-=U
j=h-i-1
Σ k=
II
(PT, j=H+1
-P:)TR
and employ the minimizer to collect data, then ViJ -V0 S S and म arg max V arg max Vig.
B Tabular MDPs: Comparison with Prior Work and Lower Bounds
Illustrative Family of MDP Instances Recall the family of MDP instances in the introduction (visualized in Figure 2 for ease of reference). The family of MDPs is parameterized by e, c1 > 0, {si, 52, $3, 83,84), 84), and A = {a1, a2 a3). which start state so and defined as:
with H 2. S
Pi (82 (1, 1 3e, Pi (sa 81, el, (i $1,a1) =2
Pi 51, 02) = P1 (s4 31, 03) 1.
We define the reward function so that all rewards are except ri (81, (81,01) r2(33, ai) r2(54, (2)) 1 for all a.
Let M denote the MDP above with E 22, and M' the MDP above with E 6, 2e.
17

---

Let II = 1T.I т2} denote some set of policies. Let æi denote the policy which always plays 01 and के the policy which plays aj green states and 02 red states i.e (2( (T2 aj and (2(3) (844)
Now note that Vo Vo 1 2e, Vo VoM e, Vo 1 e, and Vo 1/ 2c.
B.1 Comparison with complexities from prior work
The lemma below shows that the upper bound presented in Theorem is smaller than that of PEDEL from Theorem of [42] for all MDP instances.
Lemma 4. For any MDP instance and policy set II, we have that
H (TeXp)-
1. inf Teap mAX max A(T) min
max
2.
H
|10 0% (Tez))))
| 1| An (mexp)
H
inf max
)1
4H
inf max
Meep #ell max (TT) A2 2min
Meep sell maxfc², ((T)) A
h=1
min
11 1 (eepp) inf moep max max(==,A(Mt 2 minn I H E
HU(x 3. [ax ( 3
Proof. Proof of Claim 1. Note that
(8) a)² (s, a)
(s,
100% 1 (Teop))
inf NEASA
Σ
As.a
In order to solve this optimization problem, we can consider the KKT conditions. We can verify from stationarity that at optimality, Asya o% (e.a) for some constant 8 > 0. But since X must live in
vB
the simplex ASA, and since (b%, (s, a) is itself distribution over S A, follows that B must
be true. Plugging this optimal value into the above, we obtain that
as) A
|00 (TTop)))) 1 inf Σ
XEASA
Then,
1 11 (Teep)
1
inf max Teap fElf max(e? (22, A(T)² A 2 max(2² (axx(2,((T))) A(T)², A m
directly follows from the above.
Proof of Claim 2. From the triangle inequality,
1o 0f 113 (TrepT)
inf max Teap wEll max A(T)² A2 A
|| 12, (Fexw)
|0 112
(Fewo) max (22, (TT)² A
2 inf max Toxp well
max(E? ((T)² 2 m
min
|1 12 A, (TTON)))
| 2
(Fexp)
inf max Seep well
maxxfe2 A(T
A2 min
max (22, A (TT)²
2
min
|1 An )1
< inf max
Keep xell max A(T)² A2
min
where we have used that (m)) > A(**) for w. Plugging this bound into the expression from (2) from the Lemma statement completes the proof.
18

---

Proof of Claim 3.
We have that
HU( H E
Σ
(()
(h TH (s))))
h HP h=1
h=1
Then,
(U, π²)
H+
S
max()2,A(T)3 A min)
m A (m A min
110 (Feup) )-
inf max
max A(T)² A min
Seep
h=1
Where the final inequality follows from Claim above.
The lemma below shows that there are some instances where the complexity from Theorem is strictly smaller in terms of e dependence than that from Theorem from [42] for PEDEL. Lemma 5. On MDP M defined above, we have:
14, 9% (Tepp)) S 15
1. Ei=1 inf max max(f",A(1))) (
Seep
A min
a 2. maXxell max A(r) A
I (Torp))
3. =1=1 inf Fexp max;
H
max A(m)* A
Proof. Proof of 1. In this case we have that x² TT, and the only other of interest is πτ. Note that Ti and differ only at state and 84 at h = 2. Let Texp be the policy that plays actions uniformly random. Then, we have
H
ll 0% Al (Terp) well fa2 A(T)2 2 A2
1
2 11A,,
An, (Toxp))
Σ
inf max
inf Keep
22
W (8g)²
Wey (s1)
+
2
W2
(83)
W12
(84)
4e2
62
$
1/3
1/3
15.
Proof 2. Note that
HU(x, n²)
HU( m1)
max A(T))(T)))))))))))) (TT) A2
62
min
Then,
U( m1) =
Σ B s [Q27] 11,A - 1t11 (8, (2,())))))
h=1
E. Eg 1102 (8, ( Q (s, (2,))))))
+ 3c.
Combining these proves the result.
Proof of 3. By Claim 1 in Lemma the stated result then follows by recognizing that max (c2, A(T)2, 2, 2 S 2
19

---

B.2
Lower bound
Lemma 6. On MDP M defined above, any (c, C.PC algorithm must collect
BM 1
log 2.45
samples.
Proof. Consider M, and M' defined above. Let & denote the event { πi}. ). By the above observations, we have that πı e-optimal M while स2 is not, and that T2 is e-optimal on M' while πi is not. Then by the definition of an 5c,5)-PAC algorithm, [M 2 1 - 5 and pM [E] < 8. (s, a) is the same on M'. Then, letting +- Th, U// x- 74 and otherwise adopting the same notation as in Lemma F.1 of [46], we have from Lemma F.1 of [46] that:
Let yn (s, a) denote the distribution of (rh, 8h+1) given (s, a, h) on M, and 7/,
Σ s,a.h
())) (MMN a),
sup d(PM(E)) pM (MT) get,
2 d(pM)1), pad [E)
log 2.48
where the last inequality follows from [23].
Note that M and M' differ only at (s1,
E [MN
8,0.h
Furthermore, we see that
2c
(1)) 2c 2clog clog S
2E
So follows that we must have
1 log 2.45
E I (5L, a1)]
E
Noting that EMMINT (s1, a1)l < E [M] completes the proof.
C Tabular MDP Upper Bound
C.1 Notation
Covariance matrices. We use
An (TTxp) = Brrope lessan TT,,,,]
denote the expected covariance matrix and Ne, denote the empirical covariance matrix collected
from D 2,h-
State visitations. Let (s') = wTi(ss) wh (s'). for म. the reference policy, 87,n the vector- ization of , (s'), and w = Pa = s) the visitation probability, and (x) = sup, wx((s) Then, we can recursively define
T5 = PA(TTA - JENN + PATTOOTA
(C.1)
Similarly,
87 = Mr. (Pr(TA - =E, + Ph. O
(C.2)
And
8h Mn Mn, -Pea(Tm--aaaa # + + PenNThoiN))
(C.3)
20

---

Algorithm 2 PERP: Policy Elimination with Reference Policy
Require: tolerance e, confidence 6, policies II
1: 1 < II, Po < arbitrary transition matrix
2: for 1,2,3..... [log2 do
3: Set +- 2- E 62 K
+
2/3
4: St Skeep = PRUNEE(Cnn) (umit 8/382) (Algorithm 5) // Prune states that are hard to reach
5: Use (Pr- to compute (,,,, x²) for all (π, 11, // Compute new reference
policy
6: Choose मe + min maX Σn= (1,
7: Collect the following number of episodes from Hy and store in dataset Di
HŪ,-I me) + HAS log
SAHE
1/3 Ee +
H Unif
60HE [T,
nr max C. TELT.
log
ef
8
8: Compute { (s)) using empirical state visitation frequencies in Deaf
9: Initialize 87 +- 0
// Exploration via experiment design
for /1 = I..... ; do
11:
Define Me, E SAA as Me, + diag(as
ass aes.aa)) where agaa = 1(s E S
sf { Men (ITh TE, + TTōōīnn Ell
12:
<xp /2/H 37 for Be + (2200 60SH2
log 2 26 [lcl
3
c K
unit
Run DED OPTCOV (Øe, (exp: THe S Kt
unit Skoep h)) (Algorithm 3)
Use 2ih to compute (s Nea(d',s if (s, > 0, unif(S) otherwise, Nen(s.a)
and (s, 1
r'. I((s,a) (s',a') if (e,((s,)) > 0,
otherwise
Compute 0,1+1 Me,n(Pet TE OE
17:
end for
18: Compute Dae (T)) + ExiFrn, EnfFenTThren + (Fehh (Tr, - t W
Update II++1 11 E Il. : maxx D (T') Die(TT) SE;
19:
20:
if [[][+++| = then return E III+1
21:
end for
22:
return any E II+
Value functions.
Note that we can express the value function as:
V
II PyTty j=h+1
कं Th
On the "pruned" MDP, define
Fe, Me
and
H Σ k=h
Ven
II
Mes+1P,TTy
T Tek
1=
Reward difference term. Define
Un( m²) = E,r((QR =s(s)) - (T((.. (+))))
21

---

and x) == Em=1 UT, x'). Additionally, define
(T, T²)) == Ex .ll( ms)) Q7 (sh, Ty. (s)))
where E denotes the expectation induced playing n' the MDP with transitions Pe, and Q7, denotes the Q Q-function for policy æ on this same MDP. Let x') = Σ (e)
C.2 Technical Results
Lemma 7. Let D
uT; 84y)} be any dataset of transitions collected from level
N(e'ss,a) if (s, a) > 0, and 0 otherwise, for N(s' | |s, a) E, K((r, at s)) (s, o, 5')3 and N(, Σ 2,
h. Let P E SXSA denote the empirical transition matrix with [P] esa N(s,a)
(s, a)). Consider any v E [0, and E I and assume that N a) A for all
(s, a, E suppoot(uu. Then, for P the true transition matrix, we have that with probability at least
1 6:
1 (P-P-))W
P)u| s
[u]2
(1210S
(
4 log
)
N(s.a)
3
8,0
Proof. First write
N(s' 18,)) Usa
1 T ((P- ΣE
P(s' s,a)
N(s.a)
sa
Ee (P(s') (t, -11/ s'}) Uggae
(81,0))
where the second equality follows from some simple manipulations. Note that, for any we have
Ug (P(s'
St. a.) 1[s = s'}) Uocar
E
8t, Ot
=
(()
and can bound
Ua (P(s') 81, a.) Ifst 8')) usias
2dsaas
2
Us,or
$ N(s,, at)
((s,aa)
V
VN(s, dc)
2
2
V
((s.a)
where we have used the fact that ((s.a) 2 X for (s) E support(u). and since v has entries in [0. 1] and P(s' az) and Ifs = ss} are valid distributions, so E. Us (P(s' st, s2, - Ifs 8')) E [-, Furthermore, we have that
Ust (P(s') S2, s2, - 11%6 s'}) Morae ) N(8,, a+)
[
)
2
2
Usias (Mos).
Usiar
Egg
< Esg
(N
where we have again used that En us (P(s') 8c, (e) 1166 s'}) E 1-1, By Bernstein's inequality, therefore have that with probability least 1 8:
b. T(PP- TPp-P)ul-
Σ
Uscar
2
log
2
4
2a N(8,,a))
llog 2 g
(s),a)))
3
A
2
2
+
4
log
2
Σ
u
N(s,a)
22

---

Lemma 8. Let D = ((.1,01. 01. ri)........ (sT, ar. -ss,,ar.Fi" }r)} be any dataset of ttte-accion-rewart tuples collected from level h. Let RSA denote the empirical reward estimation with [f] N(s.a]
Eizre Tt H(s an) = (s, if (() > O, and 0 otherwise, for N a) = [. ar) ) = (8,0)}. Consider any u E R and assume that N(s, a) > À for all (5, a) E support(u). Then, for the true reward mean, have that with probability at least 1 8:
(r (r- (u
Σ 8,0
[u]2.0
(V2loss
(5)
+
4
log
(s)
3
Proof. First write
(r(s), az) -ra) Usiae (()
(r F) a
Note that, for any t, we have
(r(s;, ar) -rt) Ualas
E
$t, at 0
a1)
and can bound
(r(s), az) r2) Ussas
Ug
Us.ar
u2 (s,
$ N(s
N(s, ai)
VA
VN(s, ar)
6,a
where we have used the fact that a(s.a) 2 for (s) support (u), and since assume rewards are in [0, 1]. Furthermore, we have that
(r(se, ax) -re) Usias )
27
[
Usiar
- Ma
Uxcar
Er, By Bernstein's inequality, we therefore have that with probability least 1 5:
(ss.
S Er.
(.)
NN (1)s,,a))
[(r - F) u S
2 Σ
Usia:
2
log
2
u2 llog 2 5 N(s,, a4)
N(81, ae)
3VA
2 log
2
4
log
2
Σ
2
N(. a)
Lemma 9. Let E SR.S be any vector such that Vs, |ual S M. Then, for any (e, h), the following holds with probability (1 16-00 -8):
2.g
2E
[
2M
2
E Banwe [ua] E Eaway [Ma] S
log
log
3πg
Proof. The left side of the inequality above takes the form of the deviation between an empirical and true mean of the random variable u. Hence, the result follows directly from Bernstein's 's inequality since we know [ug| M is bounded.
Lemma 10. Assume that A and B are matrices with entries in [0, 1] and whose rows sum to a value < 1. Then AB also satisfies this.
Proof. To see this, consider the ith row of AB, and note that the sum of the elements in this row can be written as, for ag the ith row of A. and by the jihh column
Eatb,=I>>
anbbjk Σ ask Σ bjk).
Now note that E, bys is the sum actoss the kth row of B, so this is < by assumption. Furthermore, Ex am < 1 for the same reason. Thus, the ith row of AB sums to a value S 1. Furthermore, it is easy to see a, b, & for each j. Thus, AB has values in [0, 1] and rows that sum to value < 1. D
23

---

Lemma 11. We have that M - PATTA 22 S VS for any i.j, h.
Proof. By definition PA is a transition matrix-each row has values in [0, 1] and sums to l-and M141 is diagonal with diagonal elements either 0 or 1. Thus, each matrix M₁ Pa Th has values in [0, and rows that sum to value I, Lemma 10 implies that II M TT, does as well. We can then bound
T
Denote A = | Mn P
| M, PA
| S All
=
ΣΣ 4 S Eiss,
which proves the result. The bound on ||T T l| follows from the same argument.
Lemma 12. have
0g
h-2
h
(Ph- - Pen (TT Re.h + Thh Th-182 MET 1=h-i+1
II
2=0
Proof. This follows immediately from the definition of o 8, and simple manipulations.
C.3
Concentration Arguments and Good Events
Lemma 13. Let Emme be the event for which the call to PRUNE in epoch E in Algorithm will terminate after running for at most
SAHe
poly(S, A, H, log
)
dee
episodes and will return set S. skepp such that, for every (8, h) St Skeep then Wr < 32c Then P(Eprume) 2
h) E Sk we have (s) 2 émai and,
Proof. From Lemma 38, this event follows directly with probability (1 3/2 ).
Lemma 14. Let gt. be the event for which:
1. The exploration procedure in Algorithm 3 will produce DED such that
max [|Me,a((TA TE, + TR xElle
S Eoep for Neh =
Σ
C sar (C.4)
R2h
(B
and will collect most
C. inf Texp max [MMe, Te, + T Tho (
Ch
(E 14/5
Clu (og(C Kt Kinif
uniff
episodes.
Kt Kingg for any E A.
2. For each E S we have that (l) l((ssaa') (ss >
Above, C universal constant and Cif
poly(S, A, H. log l/5, log 1/c, log (o)) Then
P((Ets)) n Crrune E Eest n (Owsh-ieehh st,ll (Nw5k-1elhl ot,h'
6H
24

---

Since the event Eprune holds, for each Stoep we have (T))) 2 Sinit. Now, observe that, for s E Skeep and any a:
Proof.
[[ Te,h T TT (s,,aa)))
< [. + |o = [w + 1177, 1107, (0)) -10
By construction, we have [w 167,1el = (b). By Lemma 19, on Eest we can bound | w wool $ V //8E//3 5/3 By Lemma 18, on Eprune n (NW ethh (n ). we can bound
|[ 18%, & SHH + SH( 88, 5/3 + 32c(mit)
Altogether then, we have
TI Ne, )w² + T
S (s) SSHBICExp + SH(V 8c
5/3 32c + V (8SE 5/3
By our choice of E'x and e mmirr we can bound all of this as
SCs - (W) + / Kr Kimir"" unt expp)
for Cs cSH3e. This is the condition required by Theorem 2, so the result follows from Theorem 2.
Lemma 15. Let eli be the event at epoch for step h which:
(1) For all E TTe h $ h:
h
Thh Te,
MI.SIIPPT N==4+1
II
(Pw -e,N) (TT - FEN) + TN
Mee (ITN Te )o0 THe )² (m)aa)
S BEn
Σ S,a
(8,
(2) For all canonical vectors in TR. E Tlg, and h' < h,
E
II
Me,441P.T
(Ph Pe.n)Mer (TTN ) + TT Tr.
N=+++
[M ((TR TeW )w7, + T
< Br
(8,
8,0
(3) For each (s, a), have
log
485² AHP
Σ PP (8,0) -P((s - S $
(e,
(4) For each at E IT
IFe. Fe,b, Tn h. + (TT #.,))
Me. (ITT. - )EE (Th,)
+ +T (s.a)
< Be
Ne,(ss,))
s,a
Then (P(((t)) ge prune
(Ow Su Sw etb))
< 6/
Proof. We prove each of the events sequentially.
25

---

Proof of Event (1). Consider any fixed choice of (TT, h.). By Lemma 10 and since our re-
wards are [0, 1), we have that (II= Mei++1 P.T.) Th ret is vector in [0, 1].
Let
(N MeTT n. Fe, and Men (Th T + T. EN
Note that by
construction we have that usa for & Stopp and so on Et.k' we have Ne, a) eepp
Ki & 25A
for all (s, a) E support(u). On prume n n above to get that the bound fails with probability at most 30 Union bounding over h' and m we get that the stated result fails with probability at most 30H??
then apply Lemma 7 with u. and defined
Proof of Event (2). Choose
II V=M+41
M2, Pite
and Ma ((TT)) Re,w)) + TN.
Note that by construction of w and 07, we have that Usa = 0 for 8 & S and so on E we have N (8, a) 2 Kumttiiit for all (s, a) support(u). Furthermore, we have that E [0, 1] by 25A
Lemma 10. Then, the event follows by invoking Lemma 7.
Proof of Event (3). By Hoeffding's inequality, for any (s,a), we have, with probability at least 1
8 AHE
log 2452 24S2AHH AHE
PP s. - Pa(s' ss
(e,
Thus, have that with probability at least 1
8 24SAHE*
log A1E
Σ (P (8,0) Pa(s' [s,a)] s S
(e,
Union bounding over all (s, a), we obtain that this holds with probability at least 1 24H
Proof Event (4). Note first that (Fe,h Tea:: T + (T - Te,)) (Fen
Te, Men(TT (Th (0 The result then follows on Eprume by direct application of Lemma 8.
The final result then holds by union bound.
Lemma 16. Let Et denote the event that at epoch and for each h:
(I) For all Tle and h E [H), have
2H
62
(P% Me,4+1 Venti + The (IT Te,n)(w0 (.2N3)
log
3mg
2E 2n [P,T] Me, Vihea + The (TT -Te,n)eo)2)
60 TT
log
72e
8
(2) For all canonical vectors es RS.
30
2 log (30H22
2 log
He,, T7,n w 5
7tg
Then P(((E))) 5 1522
5
26

---

Proof. Proof of Event (1), Consider a fixed choice of n, and let 2
Ph Vin+1 + +h, (Th Te,,)es) and note that lull s H for all Lemma 9 then gives that with probability at least 1 30 we have
(Ph Me, Venti + vhi (T (wr w(tn)
2E
Me, VTN+ + The (Th # srwe [PP
60H
2H
60H E [Ie]
loog 5
log
fhg
3mg
8
Proof of Event (2). For fixed choice of E [S], the event follows from Lemma 9 with u e, with probability 1 - 8, where ó = 5
Once we take the union bound over all 8 [S]. then the
30
event follows with probability 1 30
The result then holds by union bounding over each of these for h.
Lemma 17. On E for all h and π have
87
11h+1
h-2
Σ
II
MeT+
Men-st1Ph--(TTT-- (w
w wi + A
1=
j=h-it1
for some A7,
E
R
with | S 22
Furthermore, for any π and any i, k satisfying
s i
H. we have
Me Me
II PTT
322H Ennif
2
Proof. By definition, we have that
11 6EA+1
PTT we T1 + PATTOOT Me FEN) -Men-1PPTThONN
(T M2,++1) (T Te,,))u + Me,411 PA(TT -een -(7T))
+(I Me + Ph - (8,m)
h-2
h
PyT j=h-it1
II
(I [I- Me.h-itt) Meen--tt)PP-ssTTT-- Th-
Th Tn- - (. + (I Me MMgh-it1P Ph-
Note that [Ph-i(TT-i Th-1)w whlle S W (s). and similarly
5
W (s). On the event Ef Eprnee we have that [Men = 0, then W (s) < 32c _ -uit.
It follows from this that every non-zero element in (I Ph
Th : wi and
is bounded by f2e f So:
[I(T Me, i+ Ph- (Th TV - ll2 S 3e (mir and
[|(1 MM.--++ 1 PA
-7, S 322
By Lemma 11, can bound
II
Meyt1P s Vs.
j=h-i41
27

---

Combining these gives the result.
We now prove the second part of the result. Denote A₁
Maj+1 PTT and By pz Then
II j=i
Maj+i Pat
P
11
A3
Bj
==i
j=s
R-1
A-
R-1
A
II
A
II
Bj
+
(Ak-
B&)
II
B
f=1
s-1
A
(Aa (Ao-Ba) Ba)
II B3
j=++1
j'=i
By Lemma 11 we have || I[ A,l12 S VS. Furthermore, note that [1 By = w So
follows that
Mr Ma P,TT,
11 PTTT) yu?
VS][(A, Bl)wsll2-
By the same argument above, bound II(Ag w Se Emir
Lemma 18. the event & Epeune (NNSsEe cf. (Nwsne we have, for all π II.:
| 1
d2.til < /SHBereup SH(V Se,
5/3 + 32c (mtr).
Proof. We can write
16 11++1 87 87,t1l1 S 160 82 2|2 + 110 07,1+1122
From Lemma 12 have
02,1+11
87
h-2
Σ
II
MeSTiPPTTy (Pa-i - ie. (TT- - )z.-)) + I Tn-
j=h-it1
From Event (2) ch.h in Lemma 15, we have that for all canonical vectors e, and π E l1fe
Cs:
II
Mejt1P,TTj
(Ph-i Me M) =) + Th 00.-1
j=h-i+1
[Mr,n-
T Tt.h-i)w Th -,
Σ
Ne,
Now, summing over the bound above for all canonical vectors, and applying this for each i, it follows that
h
[M. Re, ) h: + Te. 3 11
87
S
SB2
SH3
Ne, a)
s,a
where the last inequality holds on Cnenet
28

---

62,t1112 122. By Lemma 17 we have We now turn to bounding |0ī
E,h+1
08
2-2
h
II
MTT
Men-st2Ph-l(Th an-i)(Ehhh wihh-s) A4,
1=
for bound
by Lemma 19 IRS with 1 32SH muit Furthermore, on Eest gf.h
1 fll I V / 5/3
Combining this with Lemma 11 gives the result.
Lemma 19. event Eest we huve:
10 w 85
Proof. From Event (2) of Lemma 16, we have that for all canonical vectors e, E RRS:
30
log
30HPS
log
Ke, 07,n w/ S
+
7i
flg
Then, combining these bounds together for all
4S log 30
4S log²
30
I 4SS
5/3
+ 4S
10/3
S 88 5/3
fig
n
where the last inequality follows from our choice of nu in Algorithm 2.
Lemma 20. Let Egood == 1 prene)) n (n E n (n ONenH] Ele ) (0 DNelH] Elsp).
Then PP P(Egood]
25.
Proof. By a union bound and basic set manipulations, we have:
PP glogo S Σ
P((E )9+ +
P P((E)))) n n n E n (OW
gth' (OWgh-1E 6h,h
E= 1=1
(P((Efl n gg (n
{=1 11=1
By Lemma 13, we have P((Cprune) < 8/302, By By Lemma 16, we have P(( ) < Lemma 14, we have PP((Eh)) n Eprune n Ee, n (Ow oLM'' n (Nw )) < Lemma 15 we have P((E())) ) n st the above
1527. By
GHE By
prune n (Owsnethh) sth) $ Bnp-- Putting this together we can bound
H
28
6 < 25.
3
15
Fm hm
29

---

C.4 Estimation of Reference Policy and Values
Lemma 21. On Egood we have that:
H
H
Σ
(ee TA(0,, d(,n) Sep
and
Ifer -eeh - sec Ec. (C.5)
h=1
Proof. From Lemma 12 we have:
57 1
h-2
Σ
II
MTT (Ph-t Me (Th-- Tcn-:) Th-18
1=
5=h-i+1
A sufficient condition for (C.5) is that, for each i:
K
T Th Te,
II
MastiPPm (Pa-i-PAy -
/=h-i+1
Men-- (Th-s-- - Tee -Th- + Th Th- )
On Egood. and in particular
shh est
(Lemma 15), we can bound the left-hand side of this as:
Me (Th-i Ne,h-i) (n Th - (8 (8.0)
1
S Bt
No,
$ BEV 27 (8/
$ <2/H²
where the second inequality holds on Egood (in particular g(.A-1). This proves the first inequality.
On
E.h ret we can also bound
[fe,
Te,ns Tn + ( - -Fe,n)
Me.h ((TTh Tee WT,,, + Tn (e,
) 1
(x.a)
B
S cs/ H2
This proves the second incquality.
Lemma 22. On event Egood for any timestep h, policies ग, x,, and action a, we have:
Alog AH
E. E. 1 a) - (s.. a)ll 2 53/
EE + 24HH2
1/3
(C.6)
Proof. By Lemma E. of [10], we have that:
@7,((s,) a) ()
H
=E, -Ex Σ E (Perr(s (ws,ww Pr((s') sw, an Vx) 18. = s, 04
30

---

On Egood. in particular ch.h'' can bound, for E Sth and any
E(PEN (,,0) (,,
PM(s' (.
log
245 AHP
SA log 245 AHP
S S
6 New (s,
S SH
6
K unit unif
and where the last inequality follows on E bound this as
By our choice of K and cymii we can further
24S
< SSH SAlog log 8
1/3
For & skeep we can bound
Ex (Prar(o
- -,a)-Pa(s 8, 8,a)) V (s S 2H. We therefore
have that
E
11 (Sh, a)
(P),)))))))
248²AHe AHE
Ex
E
Σ SH
SAlog
1/3 Et
-IsS E Sth
8
h/mb h
2HT
Skopp)
8h
0,
H
1/3 248²
Σ
SH
log
Hsw E ( } + 2HT & s }
5
M==h
< $12
log
1/3 + Se
where the last inequality follows by definition of Stop, and x' is the policy which plays के for the first h steps and then plays x. This proves the result.
Lemma 23. On event Egood for all h and any at and n', we have that
Alog
24S AH
E6 +
1/3 Se
Se
Proof. We have
Ten(T,T'= - , (hh (9h (k())))
where Er', denotes the expectation induced playing policy n' on the MDP with transition Pr. We can think of this simply value function for policy on the reward (x
(S,n,s (x)) - Qr,,, (s, a)) Let V' denote the value function on this reward on Pe. and note that (s(s) E [0, H2] for all (s, h). By Lemma E.15 of [10]. we then have that
DeL(TT - E., E.r (OIIn(n, Ta(s)) Q7 ((()))
Exp
Σ
Pr.n (o.0''1sh,,a (n) Pa(s' 8/, an V (5')
H
< 2
Ex
Σ Penls' 8h, an) Pa(s' 8h, anl
hm1 1
31

---

Note that we always have Ex ( (s'1 sh. an) - PPa(s'
Sh. an)l 2. Furthermore, on Egood we
log 2492
also have Est |Panld') an) (o 18, [h,an]] SSV above as
We can therefore bound (5,
log 249 A4
2
min 2
(e, ah
h=1
log 2482 AHE
< HH
E
2 Issh & St SV
1fsh keep
(e, an)
hum
1
For E Sheep on Egood we have (5h, an) 2
K King
E. 2////5A /SA, and we also have for
SA
8h Skeep that (s) 32d muif- Putting this together bound the above
248*AH 1/3
2
645 + +S
SA
Et
24,² 2452 AHC 1/3 Ce
64SH H
A Alog
Furthermore,
Ex, (QIN(OTTA(S)) - (t)) E.d ((7(s ((9(6=)mm())0((((77())))))))
-|RAw TRay [(0In((07)))) (s ( - (7,((,
Er (QEn((.T (T (70 (s,
(x (5( ((((s (+))
< 4HE 11Q7, (s, TA (8)) (7 ( (s)) 4HE (1Q7s (s, (s)()))
1/3 AHE
< 83/2 A log
cg + 512H3 S Sc
where the final inequality follows from Lemma 22. Combining this with the above bound completes the argument.
Lemma 24. On event ggood. all epochs E, we have that
Σ
(57,, (g - (Fe,h (TT (u, w7,n)) S cE
(C.7)
P=
Proof. We first bound [MeeThh Tn( - M.. By Lemma 17 we have that
87
En 021++1
11h+1
h-2
b
πI
Mes+1P,TT
Pe Ren-s)(wk -. + Ai,
Z=0
1=h-it1
32

---

for some 1 E R with 1 l2 S 32SH unir. Furthermore, note that
H
Te Th
II Mes+
Teh Te Me (i,n-))
j=h-itt
Te Th
II Mes+iPp3T
MEX+IP Tex wx,k)
j=k+1
H
TEA Thb
π 11g++Pp7TT
MeRA:IP((TT-TTAAA - (T(xk)
2= hank
Σ
Ve - ((,))
It follows that
Fenny Th (67,1 (7,1)) + (Fenn Ten)(uR (221))
H
(Pp M1 Vent41 + Feh (TT Te, -W (T,,)) +
h= 2
for some A satisfying
H2 On Egoud (specifically Etst), we can bound | < 32.53/2
H
IPp Me Vent1 + Ten (TT - Te,n) - wF,W
2=2
H
2E 2E [(PT) Me, VT Vh+t + Fe,ns (Tt Te.,)ea))
60 [T.
loog 8
The
h=
2HH
60
log
3mg
6
We can also bound
Egwu?, 1.P. Me,4 V
2 Fe, -e,n)a))
< 2E 2B [(PTT 1
h+1 The (IT (T,,)ee)) 2H 1||TT PT (M I Ven4z
+ +2HB, 22HB,
2. [1 P (Men+1 Vēn+1 V 1l+ + 4B (sup In (n((8)) (s,
Furthermore,
E Exwun i. [|| P.T.P.T (Men+1 V 1ell
[TT PTT (Me,t1 Vih+1 ((
(M VT - VR++)) PATTAWAL
< VSII - PATA + v3]] 64s2 2
where the last inequality follows from the definition of V and Lemma 17. A similar bound can be shown for E, E,,wg [|| (Mr V Vi In addition, by definition of Te, we have
Eawug isup (s, a) (s, a)l] < Eswug [I(s & St
skeepy }] S 328c
33

---

Thus, we have
(Pp M Me Venti + The (Th (w, -wb,))]
1=2
2E 2B A [(P) Me Whhti
thb, (Th =tch)e,)
60H 2 11g
-log
nl
A=2
2H
60H [Tg]
log
3nd
5
AU Te) -8445
unif
2H
6 11
S
log
log
nt
3ng
By Lemma 23 and Jensen's incquality, this can be further bounded
(L-IN(TT me) + 83/2 58/221 Alog 24
Ef
1/3
52 unif
60H (2
[T
log
72g
2H
22
+
log
3îg
5
HŪ,-I(T, Te) + 53/2 H1
A Alg
A4EE
'6
1/3
+ S2 52 4
unif
60H II
log
Zg
5
2H
2 (T
+
log
3ng
The result then follows from this, choice of ne and emit and the bound on A above.
Lemma 25. On Egood we can bound
inf Teep max ||Men - Te, + +,,37, (Texp)
inf Teep Tal, A||Tt,,u T.w (x(op)))
<xxp
(852 325 AH² 5/3
2S² AHB + 409653 A ( (<(
+
E Eni Eepp
Proof. We can bound:
inf max [M TEN) + TT (l (Texp)) nelle
< inf max 4|| (2,A((TA - HENDWR + Tn 11 (Toup))) selle
+ inf max Topp SEIT
(TI - (EN - 11 -
+ M8, (57 -2.
34

---

We can write
(T - TEN)(WEn - w6 1 An
(Tn ten ()) (w 10 (s))2
I[((s,)) E st
[An (Texp)) Ina,sa
I((s,) E st.mp) (s) (2)(
8,a [A (T (eopp)lo,,,
On Egood, for each (s, a) E St, we have (s) 2 Sunit Let T denote the policy which achieves wh (s) (s))), and then plays actions uniformly at random at (s, h). Let Texp unif ))***)))))
Then we have [An (An(Texp))san 2 ($)/SAA / SSA for each (8, a) E Skeep so we can bound the above as
SA S
SA _
852 Ac,
Σ (w)
17 (8))
w7,n S
Cunif 8,a
uunif
Enif
where the last incquality follows from Lemma 19.
can obtain a bound on || (67,, ( (Fimp)) ( using a similar argument but now applying Lemma 18 to get that:
AS2AHBB AHBICeND
325 A 5/3
Me (07 -
+ 40965 AH -
( )-1
Emif.
Euiff
Finally, note that [Maa((TE - TeN) 01 (TTN))
| (Fe, + 1l (F I l - TA 11
where the equality holds by definition, and the inequality by simply manipulations. Combining these bounds gives the result.
C.5
Correctness and Sample Complexity
Lemma 26. On the event Egoods for all π E le+1 we have VG (1I) - V S 16Eg, and n* 11.-
Proof. Recall Dx, (x) = ViT vo For a E 1lg we have
Da (TT) Da,(
(Fen Tnōū + (TT ((,)) (rhs TnoZ (TT tT
H
H
Ieen Fe,hs 3 + (mr #e,1)
(ee T. (67
87,
(b)
Fehh ( (7,w) + (rh, (Th
(w,
w
(c)
H
(Fe The Th + +TT, ne, ww
(d)
35

---

By Lemma 21, on Egood we have (a) S and (b) S ce, and by Lemma 24, (c) S ce. To bound (d).
we note that T 6, + (TT Fe.nwui T,W% Te, and so, on Egood and by definition of Tg,
H
(d) S
Σ +
64HS S EE.
h=1 2
keep
Note that only eliminate policy II round if max, D (x')
Dzc 8cp. Assume
that x² E H. By what we have just shown, if policy æ is eliminated, we then have
SE < max (Te( - D (x) + SE, Vo Vo + SEz T'Elly
V0 Vo.
It follows that x² will not be eliminated at round l, as long x² E Ilg. By simple inductive argument, since x* E My it follows that on Egood л E IIl for all
Furthermore, for each æ E I1 we have max (T') DE, (T) S 8cc. Which, again by what have just shown, implies that
SE; 2 max Dae(T') (TT) Dae SEE V/= Vi" 8Eg
V0 V0- 16Eg.
E'elle
Theorem There exists an algorithm (Algorithm 1) which, with probability least 1 28, finds an e-optimal policy and terminates after collecting at most
11 An (Towo)
HU (T, maxfe?, (ax))))((T) A(T)2)
Cpoly minJ
inf max well
-,32 + max max ((T)))
log IIle +
mell
max
h=1
episodes, for Cpoly == (S, A, H, log 1/6, log II);; = Cylog( SHIII
Amin and
t = log Amin
Proof. First, by Lemma 20, we have that P(Egood) 2 25. For the remainder of the proof we assume we are on Egood-
By Lemma 26, we have that on Egood. for every π E 11++1. Vi Vo < 16Eg, and that x² 1Ig for all é. It follows that, since we for [log, 16/e é epochs, when terminate each policy II, satisfies V VTTh < 166g, 16 2 < Furthermore, if terminate early on Line 20, then we know that II++1| = and since n² E II we have that the algorithm returns n². Thus, the policy returned by Algorithm is always e-optimal.
therefore remains to bound the sample complexity of Algorithm At round of Algorithm we collect Л. samples plus the number of samples collected from OPTCoV, On Egood, have that the
36

---

number of samples collected by OPTCOV at round l step h is bounded by
inf Texp maxxem, ([ Reh 2 TI, & (Feap)
C.
EExp
Cf fwr
+ log(((w) K
(cexp) 44/5 Eunif
(0)
inf Teap maxxEll,
|| /
Trwr (a (Tezs)
Che (Cox))1/5
Civ
C.
+ Log(CFu) K unif
<xxp
(85" ) + 25 AH Arc + 40965 (H (c
Sexp
inf Keop max | - TA w. T. (n
C 5/3
C.
H B7
of
(0)
inf Raxp maxxell, ( - nh u (T
Kexp
H 32 +
Cle 5/3
poly
o7
Cf
| wh
H43 + Th Wh 12 (Teas))
poly 5/3
C. inf max #ETT
m ((T))
where the initial bound holds from Lemma 14, the (a) follows from Lemma 25, and (b) follows plugging in our choice of Emii and <xxp and with C
"plly = poly(S,, H, log f/6, log 1/c, log II). (c) holds by the triangle inequality and since सe E HT, and (d) holds because, for all π E IT, we have (Tr) 32cg. Furthermore,
bound i4g
HŪ,-1(T, #) H
A Alog SAHE
1/3 Et +
unif
60 TT,
ne min max xell rell.
log
HU(T, H453/2 V log
SAne 1/3
'4 + H
unif
60H IT,
min max C #Ell, sell,
log
2
5
HU( m)) max(e, [(T]]] log 60 [TT]]
poly
max C. xEll
5/3
Cg
where (a) follows from Lemma 23, and (b) since " E IT, and by similar argument as above.
Thus, if we run for a total of L rounds, the sample complexity is bounded as
|
Th TT W. ll (Tesp)
inf max
14 32
Teop
NEll
max ((T)²)
h=1
( xT) max (67, (TT)2]
log 6
L.L Poly
+ max C
TEll
8
E
By construction, we have that L < [log2 16/c]. However, we terminate early if Me+1l = 1, and since each π E II++1 satisfies A(x) S ce, it follows that we will have [Ie+1 once eg Amin- which will occur for l 2 [log2 Amin
+ Thus, we can bound
I. S min (log 16/el, [logz 1/Amin] + 1},
and so for all ee, L, we have εs 2 c- max(c, Amia). Plugging this into the above gives the final complexity.
D Tabular Contextual Bandits:
Upper Bound
Setting and notation. We study stochastie tabular contextual bandits, denoted by the tuple
(C, A, n², v). At each episode, context 4¹' arrives, the agent chooses action a A.
37

---

and receives reward r(c, a) ~ v(c, a) in R. Note that this is a special case of the Tabular MDP when H 1. In this setting, we use the terminology "contexts" " instead of "states" highlight that the agent has no impact on these. The vector Jz" plays the same role as the state visitation vectors wi previously, except this is now poliey-independent. The notation for policy matrix म,, values V* features 4 (c, a) are inherited directly from the general case.
Define 0 E Rl as the vector of reward means, so that [0"](e,a) = Ev(r(c,))) Then, we can write the value of as:
Bu (r(c, [()))] - Oaalaaa ( T T
For any (0, pu) define OPT
arg max P TH,, where 0 is any hypothetical vector of reward-means and μr E A a hypothetical context distribution.
Recall that we use π E R c CI to refer to the policy matrix. The vector тµ E IRC contains context-action visitations for policy æ under context distribution μ. Define function G(p, π) (TT which returns the expected covariance matrix of policy under context distribution J.. For shorthand, we refer to Á(T) G(āe, Texp) and A(T)) G(u", Texp) for any n Lemma 27. Define the experimental design objective
F(Texp: Mr n, T²) = |1( - TTM [
Then, for any μ E De.
min max F(Fexp- 14, 5, T²) max min F(Texp M4 n. T') Teep k
n. ETT,
Teep
Proof. We can rewrite the maximization problem to be over the simplex An instead:
min
max
Σ
Ax (Texp: U1 ,.
(D.1)
Texp AE AE
T. x11,
This does not change the objective value. To see this, note that for any selection (x1, n2) in the original problem, the same objective value can be obtained by setting À = en hence, the modification the optimization cannot reduce the value. Further if F (Texpp μ4, ग,, x is maximized by (T1 T2). setting À as anything other than 6Ti. cannot increase the objective value.
Now, note that both the minimization and maximization problems over simplices, which compact and convex sets. The objective is linear in the maximization variable, and hence concave. The objective can be rewritten
ΣΣ CES&EA
π
T')
T
C, TT)
Pe.a
Here, Pe.a the probability that Texp plays action a, given that are in context From this representation, we can clearly see that the objective is convex in each Pe.a. Hence, since we are optimizing over finite-dimensional spaces (IA) and |C] are finite), Von Neumann's 's minimax theorem applies and the proof is complete.
Lemma 28. For the contextual bandit problem, define the experimental design objective
(Teep Ph π. T') [| (0:-=r))p TT) (l
Then, for any and assuming that all policies in 11, are deterministic, we have:
min max F(TTeDD M4 n, T²) max
(6-_][4l[[TTC)) o n x'(i),, ell
(D.2)
Texp N.s''lll
38

---

Proof. Below, we refer to Pe,a as the probability that Texp plays action given that we are in context We have:
min max Teep n, Elle
11( - TT)p ( TT)pl(/( (prtop))
max min |I( T1 ((pp)))))))
x, Teep
T T Ca,cfa, TT')
Σ
max min T PEE. 0,0
MePr,a
T') ea,ee a (T TT¹)
Σ
max
min aEA
x,l'Ell,
Pe.a
mAX
Σ Me
AEEA V ( T²) Ta - T³)
x. ElL,
Here the first equality follows from Lemma 27, and the last from Lemma D.6 of [30].
We have assumed that the policies in IIg are deterministic. Hence, the only two actions in the summation over A above that are relevant are (c) and (c).. For all other a E A, the term in the square root evaluates to If π (c) = n' (c), then the entire summation over A evaluates to O; else, the terms indexed by π (c) and I (c) are both 1, and the summation evalutes to 2. Hence, we can simplify the expression to exactly the form Equation (D.2) from the lemma statement, and the proof is complete.
Lemma 29, For the contextual bandits problem, we have that
max Ee [(rc,(((,, r(c, =( < FENl
inf max 11o" - -d"1 -0"13((TTOD))) Texp Tell
Proof. Observe that r(c, (() = x (c): else, |r(c, ((( xc)) 2 Then, it follows that
max Be [B [[r[[ n (c)) r (c))
< max 4eeyy [(T(c) # x (c))
sell
inf max 1| x= A
Seep #Ell
where the equality follows from Lemma 28.
Now, we state our main upper bound for contextual bandits.
Corollary 1. For the setting of tabular contextual bandits, there exists an algorithm such that with probability at least 1 - 26, as long as II contains only deterministic policies, it finds an e-optimal policy and terminates after collecting at most the following number of samples:
1105 o= [13(m
Opoly
inf max
3 log
Texp TEll
m ((T)]]
Amin Ve
max(e5/3
55/3
for Cpoly poly((S),A,1o log 1/(Amin V log III and CV /log(
Amin Ve
Proof. In the special case of contextual bandits, Un, T²) defined in Theorem can be written more simply as Eo-w [E [[r(e, (c)) - r(c, (c))) Then, by Lemma 29, we have that:
U π
110 Φ 112 (T
inf max
max (22 A
Nexp Tell max(e² A(T)² A minJ
min
Plugging this into Theorem completes the proof.
39

---

E MDPs with Action-Independent Transitions
We consider here special class of MDPs where the transitions only depend the states and independent of the actions selected i. all Pa are such that (s a) = (s, a') for all (a, a') E A. In this special case, we prove in this subsection that the (leading order) complexity of PERP reduces to (pm)
Lemma 30. For the ergodic MDP problem.
min max
|| 0% - (Fexp)-1 max min 10% Tell
0% 1i 11
Rexp Tell
Kexp
Proof. We can rewrite the maximization problem to be over the simplex An instead:
Σ min max
Am 1o - -0%% 1i
(Frep))-
(E.
Sesep XE A
This does not change the objective value. To see this, note that for any selection 11 in the original problem, the same objective value can obtained by setting = ex in Equation (E.1); hence, the modification to the optimization cannot reduce the value. Further if | 4% lI An (xeep) )-1 is maximized by for any fixed Texp- setting À as anything other than eạ cannot increase the objective value.
Now, note that both the minimization and maximization problems over simplices, which are compact and convex sets. The objective is linear in the maximization variable, and hence concave. The objective can be rewritten
Σ Th TT,)) Cx,a C ( 7T,))
T
Ps.a
Here, Ps.a is the probability that Texp plays action a, given that it is in context From this representation, we can clearly see that the objective is convex in each Ps.a- Hence, Von Neumann's minimax theorem applies and the proof is complete.
Lemma 31. For the setting of ergodic MDPs,
min max
Texp #Ell 1107 21 111 (TT max 2IE 21 [TTA 4 (+)],
(E.2)
well
Proof. Below, refer to Ps.a the probability that Texp plays action given that it is in context The second equality follows from Lemma 30.
min max
||0]
17 (7.133. (1mmp)-1
Texp sell
min max [[TT) w f I (
=
REll
max min [(TT) Tr/, P (Femp)
#Ell Resp
(Th - T
e ( TT)))
Σ (w)()))
max min
well
PSEA
W (s)paa
(Th Tht) 6s (TT TT/,)
max nell
w
min P.EDA
Ps.a
2
max TENl
(s)
Σ
EmT (Th (iin-T))+' Ta
(Th - -TT)
The optimization problems in the final line were solved using KKT conditions. We assume that the two policies are deterministic. Hence, the only two actions in the summation over A above that are relevant are Ti (s) and n/, (s). For all other a A, the term the square root evaluates to (s) = 7 (s), then the entire summation over A evaluates to 0; else, the terms indexed by T(c) and
n' (c) are both and the summation evalutes to Hence, we can simplify the expression to exactly the form of Equation (E.2) from the lemma statement, and the proof is complete.
40

---

Lemma 32. For the ergodic MDP problem, we have that
HU, TT) HEM max e, A(T), A
1
0% 11113, (Feup)
2H
inf max Heep
max A(T)) A
min
Proof. Recall the definition of U (T,
H
U(T, xT
E Nu ((QT Th (s)) - Q7 (sh: {s
k=1
Then, we have that
HU )
max Tell max
( ((T)), A min
H 2h=1
H
E Snnuag (s, - (sh. (8)))
max TEll
maxfe2, (TT) A min)
E Sy ww
112 Sh, Th (s))
0% (8h, x (+)))
< H
max
xell
max 6², (TT) A min)
h=1
2H AN TTT (8) + m (x))
<
max #Ell
max (TT)² ; A
h=1
110% 0% 11 (n( inf max Sexp Well
H
max A(T) A min!
h=1
The final equality follows from Lemma 31.
Corollary 2. Assume that all Pn. are such that Pr(''(s,a) = Po (sdlssd)) d') for all (a, a') E A. Then, with probability at least 1 28, PERP (Algorithm 2) finds an e-optimal policy and terminates after collecting at most the following number of episodes:
10% 37
Opoly
inf max Teep TEll
33 +
max ((T)))
max3
A
5/3
min
for Cpoly, 3 as defined in Theorem 1.
Proof. The proof follows directly from Theorem and Lemma 32.
F Tabular Franke Wolfe
Theorem 2. Fix parameters Kunif O, Cexp 0, and consider some T C TRA and set So C S. Let Eunif > 0 be some value satisfying
(i(() > Cunif, Vs E So, and Kunit 2 Cuulf-
Assume that [p)() S Cs (s) + (Ta) for all & E So, db E D and some Co > 0, and that [0)(...) = 0 for s & Sg. Additionally, let the parameters be such that c (K/K S Cexp- Then with probability at least 5, algorithm Algorithm 3 run with these parameters will collect most
min C. infAen, max |011
CFw
Ctw(
(-
1
+
Kunitt
}+
Ctw
+ +lo((Ct)) Kunit
Gexp
Coxp
4/5
Cexp
Cunif
episodes, for C universal constant and Ctw = poly(S, (S, A, H, Ca, log 1/0, log 1/ log (0)), and will produce covariates E such that
max ΦE#
||
| $ fexp
(F.1)
and, for all E So.
[ ((,)) 2
Eunif Kumif-
(F.2)
2SA
41

---

Algorithm 3 Online Experiment Design (OPTCOV)
1: input: directions Φ, tolerance Sexp- confidence 8, minimum reachability éunif, minimum explo- ration Kunif, pruned states So, step h
2: (-1 1
3: while TiK; I poly(S. H, Co. log 1/6, log 1/Eexps log [+]) Cexp do
4: D Pinif - UNIIFEX((Euntt K;T; ; + Kuiff 6/8(²)
5: A - 1 T,K, (via where [e']ea
[(s''aa)==saau) (s, for Sy, and T,K;
otherwise
6: Run iteration of Algorithm 4 of [43] on objective
f((A)
1
log Σ nh (ulllblllaa
for A(A) A+ A "h = =221/5
obtain data D
7:
if Algorithm 4 reaches termination condition then
8: return D' D init
9: end if
<- i+1
11: end while
AS2 (8.5
D < UNIFEXP(EEnit Guniff Soep
K 6/4)
13: return D
Proof. To prove this result, we apply Lemma 37 combined with Lemma 36.
Let Sxp denote the success event of rumning Algorithm 4 at epoch i, defined in Lemma 36. On this event, and under the assumption that (x(s) Eunif for each Sp. we have that
(a) (T,K, + Kunit) for each (s, a) with E Sy and Eg the covariates induced by [E)(),)) 2 28A
D unit. which implies that
(s) (T,K, + K Kunit) 2
(s)
Adl(s.)) 2 T,K; 2SA
2SA
for each (s, a) with s E Sg. and, furthermore, Algorithm 4 collects at most
T,K; + Kunit + poly(S, A, H, T2K )
1
(F.3
deanif
Cunif
episodes. Furthermore, by Lemma 36, we have P P
2 8/202, so it follows that
6
(E <
S 6/4.
82
Henceforth, we therefore assume that Eixp holds for each i. This immediately implies that (F.2) holds.
It remains to show that (F.1) is satisfied, and that sample complexity guarantee is met. To this end (;)
we apply Lemma 37 with Ao a diagonal matrix, with [Aol(s.a) = 2SA for E So. and otherwise [Ao](..a) = 1. Note that with this choice of Ao. by what we wejjust showed above, we have Aj > Ao. required by Lemma 37.
We next turn to bounding the smoothness constants, and M. First, note that by Lemma 34, at epoch i we have that all iterates of FWREGRET live in the set Q (5/8i2) with probability 1 5/8/² Union bounding over this event for all with probability least 1 - 5/4, have that for each i K2 (5/8i)). By Lemma 35, since we have assumed that | ( < Cs (s) + /Es) for all (s, a) with E Sp and otherwise ( 0 for all
all iterates of FWREGRET live in the set DA,T,
42

---

Φ E D we can then bound
2SAC
2SAC
(a+ O'T,K,W7(()
SAH
M, S max
log 8
sESu
C
C² C² (T.W)())))))))))))))))()))
2SAC $
2SAC EF
)
2
SAH
B
max (21/ 22 sESo
log
C' (x()
C
(,T.KWWA
On the event Ee as noted above we have (e,)),
(
2SA
+
Kanit T.K.
for E So. so we can take
C² = 25A (1 +
Kunit)
We can then bound
T.K;
AS
2S GE C
(
2
SAH 8
log
SESo
C²
(
45 AS 6 T,K;
(ASA+ +
4SA
SAH 5
4S A +
log
Kunit unit
K Muniffuntt
where we have used that (s) 2 Cunif for all E So. by assumption. By assumption we have Co S Eexp. Note that by construction, the while statement on Line 3 will ensure that we always Kunit
have T,K: S pSly(S, A, H, CΦ. log 1/5, log 1 1/xxxp log (b)) <app so bound T.K; S poly (S, A, H, Co. log 1/ log 1/eexp: log ()).
Coxp
It follows that it suffices to take
3. S poly(S, A, H, Cø, log 1/6, log 1/Eexps log (+)).
We now consider two cases. In the first case, when the termination criteria on Line 7 is met, we can apply Lemma 37, to get that with probability at least 55/4 we have that the procedure terminates after running for at most
max
min 16N
s.t.
inf max TT (NA + Ao) S
Fexp 6
AEΩ De
poly R, d, H, M, log 1/6, log 1 1/eexps log +
Eoxp
I max
min 16N
s.t.
inf max oJ (NA+ Ao) ' ACR De
Cexp
6
poly A, H. Co. log 1/8.log e/ooxps log (4))
4/5
Eoxp
episodes, and returns data ΣN such that
ANN S Neexps
where is the index of the epoch on which it terminates. By Lemma D.I of [42], we have
max Φ
|
| S -ANN-1EN S Neexp
which implies
max 11 Φc (Ex+E,)-
Cexps
which proves (F.I). Furthermore, (F.2) holds since as noted [E)(s..) 2 each (s, a) with E Sg. and since (s) 2 Emii for all E Sg.
WX(s)
(T,K, + Kunit) for 28A
In the second case, when the while loop on Line 3 terminates since T.K; < pSly(S, A, H, C2, log 1/6, log 1/exxps log ( < we can bound the total number of episodes collected within the calls Algorithm 4 of [43] within the while loop by
43

---

poly(S, A, H, Co. log 1/6, log 1/Cxxp, log (0)) Gaxp' Furthermore, by Lemma 36, with probability at least 1 - 6/4, we have that the call to UNIFEXP on Line 12 terminates after running for at most
852 A (852 CPC3 + 1nik + poly(S, A, H, log
T2K,²²
Coxp
8eunit
Cunif
episodes, and that the returned data satisfies (x) 2
(g)
85 x
8. A Kunif
2SA
Kuuit). Since | (s,a:) I C$ (W) + VEØ) and
( unii
Cexp by assumption, some
manipulation shows that
(
C3 (W + VE6)2
6exp SA
No. (s, a)
(.(a) 28A
A.S.ARC
+ 852 A²C Kumir + Kunit)
Cexp
It follows then that, letting Σ denote the covariance obtained by the call to UNIFEXP on Line 12,
max
|
Σ
S
Eexp
ΦE
as desired. Furthermore, it is straightforward to see that [i((,a)) 2 28A Kunit for s So as well.
To complete the proof, union bound over these events holding, and take the minimum of the sample complexity bounds from either case.
F.1 Data Conditioning
Lemma 33, Consider running any algorithm for episodes. Let Kn(s, a) denote the number of
visits to (s, a, h). Then with probability at least 1 - for all (s, a,,h, h) simultaneously. we have
SAH
SAH
Kn(s, S WX(s) (5) log
log
Proof. By definition, have
sup (s) (s).
This implies that any policy will reach (s, h) with probability at most (s). We can therefore think of this as the sum of Bernoullis with parameter most W so the bound follows by applying Bernstein's 's inequality and union bound.
Lemma 34. Consider the set
DA,K (8) diag(v)
RSA (M) S (s)
(w) K
llog
SAH 8
+ log
1
SAH
K
Consider rumning some set of policies for K episodes, and let A be defined as
(o)(a.a) Kn(s,a)
An = diag(
Then with probability at least 1 5, have that D E (5) for all h E [H] simultaneously:
Proof. This an immediate consequence of Lemma 33.
We will denote S2 == x2,,x(() when the choice of is clear from context.
Lemma 35. Consider the function
f(A)
1
log
Σ
blooblaac ) for A(A) A
7)
ΦEO
44

---

Assume that for all Φ E ① we have
max SE
[+)() S Cs (W + E), Vs E Sn
for some So and some CΦ. c O, and otherwise ( (s.a) O. Assume that Ag diag(u) for some to satisfying
(o)(s,)) 2 C- (s),,,,, Vs So
and otherwise [o]()))) 2 >, for some C² Then we can bound
sup ,,,
|
25AC3
2
)
(- (s)) log 8
SAH
< max sESo
C
O' (7.)((s))
and
sup A. LAEAE
25AC
25AC2
( + ('KWE($)
2
SAH
< max(2 + 2n) SES
+ C' Wh(s)
log
C'
Proof. By Lemma D.5 of [42], we have that
VaS(A)IA=xIA)) - Σ
e 2
DE#
We have
[0 (e.a) AA (A((s.)
| (s,a) [A'(
Φ T A A(A - Σ
Σ
Σ
8.0 A(A))
[A [A(
(s.a)
SESU a
where the last equality follows since, for s & So, we have assumed (d)(a..)) = O.
Now consider some E Sp. By assumption we have (ol2..) S 20 assumption on Ag we can lower bound (A()))( 2 C".WA(C Furthermore, since A' Gg we have
(WT e²) and by our
(s)
SAH
SAH log 8
A ( I (s) +
llog
K
S (8) 2
SAH
log
Putting this together, we have
[ (x.0) (Al(m,a)
402 . (W) + +) (W)()) + K log SAH
A (A (
(C'. (s))
2C + (s)
2
(~: C'KW
SAH
log 8
It follows that
[ ((.aa)) A
2SAC2
28 +
(a+ ('KWA(s)
2
SAH
max SESo
CW
log
[A J...)....
C'
8
#ESo
The second bound follows in analogous fashion, using the expression for the second derivative given in Lemma D.5 of [42].
45

---

K Algorithm 4 Uniform Exploration (UNIFEXP)
input: tolerance Cunif, reruns K, confidence step
2 f- 0
for (s,a) E A do
// LEARN2EXPLORRE is as defined in [46]
[(X) J. N2)) [log, 1/cuait] +- LFARN2EXPLLOREL ((8, a)), h, 28A' 2K9A Sunif)
if 3jsa such that (s, a) E X2 then
Rerun every policy in _1, Keo 3 end if end for return
times, store observed transitions in D
Lemma 36. With probability at least 1 6, Algorithm 4 will terminate after rumning for at most
K + poly A, H, log
deunit
6unif
episodes and will collect at least
(*) 25A
samples from each (s. a) such that (s)))) >
Cunif.
Proof. By Theorem 13 [46], with probability at least - 8//2SA for any (s,a).
LEARN2EXPLOORE will for most poly(S,A) A, H, Seuntt
K
episodes.
Cunif
Rerunning every policy in Ilj.. once, with probability least - 8/ K will collect samples from as, for [I O(2 A32 H log 1/8).
N = 2 J..
We have that (s) S iva+
IF (s, a) & X, for all j 1, 1,2, [log L/Eunit] then (s) S Eunif-
By the above conclusions, rerumning policies in II on Line 7, with probability at least - 6628AA we will collect
K SA
2 2h K
Kea 2 N.
SA
samples from (s, a). As noted, (s) < 2-a++1, so this implies that we will collect at least (X
25.4
samples from (s, a). Union bounding over this holding for all (s, a). and noting that we only fail to collect this many samples if (x) I Cunif gives the collection guarantee.
To bound the total number of episodes, note that the procedure Line will, in total collect at most
I1 1K <
Σ 8,0ifan exists
I1 +
Σ
K
I1 + K
SA
8,0tjao
episodes. IF Jsn exists, this implies that [I, S O(2 $ H log 1/8), and since jaa
21.2... [og 1/e }}, this implies that the above is bounded by
K + O S 2 log 1/8).
Combining this with our bound on the total number episodes collected by LEARN2EXPLORE, we have that the number of episodes collected by Algorithm 4 is bounded by
K
K + poly(S, A, H. log Öeanif
Cunif
46

---

F.2 Online Prank-Wolfe
Lemma 37. Let
M(A)
1 a)
log Σ +E
7: [
A,(A)= - A+ Ao,i
T:K;
for some Ao, satisfying Ao, = for all i, and Tj = 221/5 Let (Bs, M,) denote the smoothness and magnitude constants for ft. Let (B, M) be some values such that Br S nxB, M, M for all i, and R the diameter of the domain of possible values of A.
Then, if run Algorithm 4 of [43] on (fi); with constraint tolerance and confidence 5 and K; = T; = 2', we have that with probability at least 6, it will run for at most
poly(3, R, H, M, log 1/6, log (+))
min 16N s.t. inf max & J'NNNA + Ao) N
max
AES ΦE
e/5
episodes, and will return data {Ø+) ) with covariance EN Σx= Φ such that
J(N- S SNe,
where i is the iteration on which OPTCOV terminates.
Proof. Our goal is to simply find setting of i that is sufficiently large to guarantee the condition (((A,) < K;T, is met. By Lemma C.I of [43], we have with probability at least - 62(2²²)
(AAa)) S inf ((A) + R2 (log T, + 3)
4M log(8/2T,/5)
AER
2T,
K;
ci M2d H log (8P H
C2 Md H log 7/2 (K,TT//)
K,
K:
4M2 (og(ii2)/ 3 R R. T; +
I 3 max
inf AER
JA(
2T:
K,
MMM2d log 28 HK.T.88
c2 H3 log 2/2 (4:
K;
Kg
So sufficient condition for f((A.) S K,T.e is that
3
R (log +3)
4M (og(8(77:/5)
K.T. 2- max
inf fi(A), AE
2T;
K;
(F.4)
M H log (88 HK,T.18)
Md H log
3/2
K,
K
Recall that
nel A,c, ) A,(A) A Ao.i-
A(A) = Σ
log
T,K;
ΦE
By Lemma D.I [42], we can bound
log D Y/
max Φ
s((A S max 11 ΦE
Thus,
log +
inf M((A) AEn
< inf max
ASA de ||)1
77s
log {
inf max T,K (T,KA + An. Ada)
Uen de#
47

---

By our choice of 1/s = -2 and K; = 2', = 2", we can ensure that
K,T. 6 log +
7
as long as 2 loga!
Glog [0
To ensure that
6
inf maxT,K, (TKKA+ -o
suffices to take
2 arg mind s.t.
inf max Φ (2 A + Ao.:) Acn dEb
Since we assume that we can lower bound Ao ł Ag for each so this can be further simplified to
arg mini
s.t.
inf max Φ T (2 A + Ao) -o)
(F.5)
Acf dEd
We next want to show that
T,K, 3. 3 3 T; 3)
2T; Bounding 3, S n,S, a sufficient condition for this is that
1
i2
loga (125R2) + log2
5
By Lemma A.I of [43], suffices to take
1 -)
2
log2 (93R2 R² logz
log2
(F.6)
51
to meet this condition (this assumes that 12 and log, 1- either of these not case we can just replace them with without changing the validity of the final result). Finally, we want to ensure that
4 log (8/T.15)
TKK 2 e VV
K,
C 4 H log (882 (872H,,)
c2Md H log" 7/2 (4;H//
+
K;
K;
To guarantee this, it suffices that
M2 (iH/5), 20//2 2
23 2
Mdd H2/7/2 log" 7/2 (1HH/
or 12 loga (cMdHilogy (ogHH)))HHH)) 2
1
1 1
loga i2 (cdH (H (H/))) + log2 c
By Lemma A.1 of [43], then suffices take
N log(cMdH log (// loga 1/c) + logz
e
(F.7)
log2 Thus, a sufficient condition to guarantee (F.4) is that i is large enough to satisfy (F.5), (F.6), and (F.7)
> (cMdll log log (0) log, 1/e)
and > loga
Blog
I 7 is the final round, the total complexity scales as
T.K. = Σ 22 2.
Using the sufficient condition on i given above, we can bound the total complexity as
16.V s.t. inf max & T(NA + An) poly(3, R, d, H, M, log 1/5, log (+))
max
min N
AES de#
c/5
48

---

F.3
Pruning Hard-to-Reach States
Algorithm 5 PRUNE: Prune Maad-to-Reach States
input: tolerance Cunif, confidence 8
Skeep { 0
for E [H] do
for E S do
// LEERNZEXPLOORE is as defined in [46]
Tlgg azeunir
{(X), N,) A
+ LEARNZEXPLOREE((S,()) h, SH 2 3,322mmti for any
if 7j. such that (s,a) E X2 then
Skeep S skeep U hs)
end if end for end for return Skeep
Lemma 38. With probability at least 1 6, Algorithm will terminate after running for at most
1
poly(S, A, H, log
δeanif
Cunif
episodes and will return set Skeep such that, for every (s, h) E Skeep, we have (s) 2 Cuuifs and, if (s,h) & Skeop, then W I 32cuuif
Proof. As in Lemma 36, by Theorem 13 of [46], with probability least - 6/SH, , for any (s, h):
LEARN2EXPLORE will run for at most poly(S, A, H, log Sennt!
1
episodes.
Rerunning every policy in I1,, once, with probability least 1/2 we will collect N 2 2- [II,, samples from (s, a, h).
If (s,a) & X, for all j 1,2, [log 1/Eunit] ], then (s) 32
We union bound over this event holding for all (s, h), which occurs with probability least 1 8.
It is immediate by the last property that, if (s, h) & Skeep then (s) < 32
We next show that if (s, h) E Skeep, then this implies that (x) 2 Cunif- Let X be a random variable denoting the total number of samples collect from (s, a, h) when rerunning all policies in I1,,- Then by Markov's s Inequality, by the above properties we have
2E[X] N
2|11, (W) 8- 2 (s).
< P[X N2,
2
N₁.
follows that
1
% (s)
Cunif-
16 25.
llgaa 3renii
32 2 20082 Yaruii
This completes the proof.
NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
49

---

Justification:
These can be found in the abstract and the contributions section of the intro- duction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: These can be found in the Discussion section of the main body of the paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer:
[Yes]
Justification:
All proofs are found the Appendix.
Guidelines:
The answer NA means that the paper does include theoretical results. the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
50

---

All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification:
The contributions of this paper are entirely theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how construct the dataset).
(d) We recognize that reproducibility may tricky some cases, in which case authors welcome describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
The contributions of this paper are entirely theoretical.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
51

---

Please see the NeurIPS code and data submission guidelines (https://nips.. ca/ http://dddee/ooouuuuieeeeee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //iiss wwtpccccppcccaeccccccccccccccttt wwwic//gggs///eeeeeoeooio / /wode//umisiiionoooeeee ssioiiy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [NA]
Justification:
The contributions of this paper are entirely theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[NA]
Justification:
The contributions of this paper are entirely theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
52

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The contributions of this paper entirely theoretical.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: /ttp://eeeii....eee cc/ htte//ublcc//ee ppublic/Ethii Ie ines?
Answer: [Yes]
Justification: There are no human subjects and we discuss the ethical consequences in the "Broader Impact" section of the discussion.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This theoretical paper poses minimal public concerns but holds significant potential to inspire advancements in algorithm development, contributing positively to the field of machine learning.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to
53

---

generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The contributions are theoretical.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: The contributions are theoretical, and we not use any such assets. For prior theoretical work, have credited the authors appropriately.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
54

---

Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
The contributions are theoretical.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: No human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
55


Reviews:
[{"review_id": "XmCza1FlK1", "reviewer": "Reviewer_f5AC", "summary": "This paper studies the problem in tabular RL: finding an \\epislon-optimal policy given a set of policy with high probability. The author proposed with a new lower-bound of this problem and explained why the previous one is not correct with an example. The author proposed one algorithm PERP that computes reference policy, measures the difference between policies, and refines policy set through episodes. The author provided sample complexity analysis.", "questions": "How the sample complexity change when abitrary choosing a reference policy? The U(\\pi, \\bar{\\pi}) should be upper bounded by a constant value, if I could arbitrary choose a reference policy, does it mean that I sacrifice sample complexity for computational complexity? If so, how much? Since it seems costly computationally when I iterate through the whole policy set to find a reference policy but the sample complexity won't decrease much. Please correct me, thanks.", "limitations": "The authors have confronted the limitations in section 7.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "This paper is well presented. The idea is conveyed clearly. \nThe paper proposes a new lower bound and provide one example that is easy to understand. The explanation of algorithm is clear.", "weaknesses": "The paper didn't provide the computational complexity of the algorithm. It would be better to mention the computational complexity by the end of the section describing algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper and for the positive feedback. Please find answers to your questions below.\n\n**Computational Complexity**\n\n> The paper didn't provide the computational complexity of the algorithm\n\nThank you for pointing this out, and we will include additional description on the computational complexity in the final version of the paper, if accepted. The computational complexity of PERP is $\\text{poly}\\left(S, A, H, \\frac{1}{\\epsilon}, |\\Pi|, \\log \\left(\\frac{1}{\\delta}\\right)\\right)$. The primary contributor to the computational complexity is the use of the Frank-Wolfe algorithm for experiment design in the *OnlineExpD* subroutine. Lemma 37 from [1] shows that the number of iterations of the Frank-Wolfe algorithm is bounded polynomially in problem parameters, and from the definition of this procedure given in [1], we see that each iteration of Frank-Wolfe has computational complexity polynomial in problem parameters.\n\n[1] Wagenmaker, Andrew, and Aldo Pacchiano. \"Leveraging offline data in online reinforcement learning.\" International Conference on Machine Learning. PMLR, 2023.\n\n**Impact of fixing reference policy**\n\n> How the sample complexity change when abitrary choosing a reference policy? The U(\\pi, \\bar{\\pi}) should be upper bounded by a constant value, if I could arbitrary choose a reference policy, does it mean that I sacrifice sample complexity for computational complexity? Since it seems costly computationally when I iterate through the whole policy set to find a reference policy but the sample complexity won't decrease much.\n\nIf we fix the reference policy to a fixed $\\bar{\\pi}$, the numerator of the second term of the sample complexity would be replaced by $U(\\pi, \\bar{\\pi})$ as you observe and, additionally, the numerator of the first term would scale with $\\phi_h^{\\bar{\\pi}} - \\phi_h^\\pi$ rather than $\\phi_h^{\\star} - \\phi_h^\\pi$. However, the computational complexity would not be significantly affected since we need to iterate over $\\Pi$ in other parts of the algorithm (lines 7, 12, 18) as well, so the computational complexity will still scale as $|\\Pi|$. It is an exciting direction of work to design more practical algorithms that incorporate experiment design for exploration.\n\nPlease let us know if any of your questions were not clarified, and we would be happy to elaborate.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hP4p75iyUZ", "reviewer": "Reviewer_76qf", "summary": "The author investigate if estimating the difference in policies is sufficient in determining the best policy for contexual bandits and tabular RL. \nA (somewhat) practical algorithm is proposed to determine the number of samples needed without any unknown quantities.", "questions": "- In Lemma 1, what is the difference when $E^M[\\tau]$ when compared to $E[\\tau]$ on line 182?\n- Could an example be provided of an MDP with Action-Independent Transitions. It's unclear to me how a sub-optimal policy can exist in this setting.", "limitations": "No concerns.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- The motivating example clearly explained the difference between estimating policy values directly vs their difference\n- Identifying the when $\\rho_\\Pi$  is sufficient in determining the optimal policy in is novel \n- Limitations of the algorithm is clear", "weaknesses": "- Some intuition could have been provided to describe certain value such as $U(\\pi, \\bar{\\pi})$ or $\\hat{\\delta}^\\pi_h$ to make the resulting bounds easier to interpret.\n- In section 4.2,  it is difficult to see why the difference estimate has reduced variance", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our paper and for the positive feedback. Please find answers inline to your questions below.\n\n**Intuition for terms**\n\n> Some intuition could have been provided to describe certain value such as $U(\\pi, \\bar{\\pi})$ or $\\delta_h^\\pi$ to make the resulting bounds easier to interpret.\n\nThe notation $\\delta_h^\\pi(s) = w_h^\\pi(s) - w_h^{\\bar{\\pi}}(s)$ is used to refer to the difference in state visitations between policy $\\pi$ and the reference policy $\\bar{\\pi}$. We will include additional description on this in the paper.\n\nThe $U(\\pi, \\bar{\\pi})$ term is, to the best of our knowledge, novel in the literature. As we argue in Section 4.2, however, this term naturally arises when computing the variance of our estimator used to estimate the difference between the value of two policies. More precisely, this term corresponds to the cost of estimating where $\\bar{\\pi}$ visits, if our goal is to estimate the difference in value between policy $\\pi$ and $\\bar{\\pi}$. If for a given state $s$ the actions taken by $\\pi$ and $\\bar{\\pi}$ achieve the same long-term reward, then it is not critical that the frequency with which $\\bar{\\pi}$ visits this state is estimated, as it does not affect the difference in values between $\\pi$ and $\\bar{\\pi}$; if the actions take by $\\pi$ and $\\bar{\\pi}$ do achieve different long-term reward at $s$, then we must estimate the behavior of each policy at this state. This is reflected by the term in the expectation of $U(\\pi,\\bar{\\pi})$: $(Q_h^\\pi(s,\\pi_h(s)) - Q_h^{\\pi}(s, \\bar{\\pi}_h(s)))^2$; this will be 0 in the former case, and scale with the difference between long-term action reward in the latter case. We will add this additional intuition to the final version.\n\n**Clarifications on results**\n\n> In section 4.2, it is difficult to see why the difference estimate has reduced variance. \n\nThe PERP algorithm, which uses the differences estimator, achieves the sample complexity from Theorem 1, which we show can be arbitrarily smaller than that of prior work such as [40]. We attribute this reduction in complexity to the reduced variance of the estimator. The intuition for this is that only states where policies differ (“red states” in Figure 1) contribute to the upper bound for PERP, whereas all states contribute to the upper bound in [40]. \n\n> In Lemma 1, what is the difference when $\\mathbf{E}^{\\mathcal{M}}[\\tau]$ when compared to $\\mathbf{E}[\\tau]$ on line 182?\n\nLemma 1 is making a claim about the specific MDP $\\mathcal{M}$ from Figure 1, which is why we make the dependence on $\\mathcal{M}$ explicit here. Line 182 refers to the lower bound from [2], which applies to any MDP, which is why we drop the $\\mathcal{M}$ for notational convenience. Note that Lemma 1 shows that there exist instances where the bound from [2] is not tight. We will make this more explicit in the text.\n\n> Could an example be provided of an MDP with Action-Independent Transitions. It's unclear to me how a sub-optimal policy can exist in this setting.\n\nIn this class of MDPs that we consider for Corollary 2, the transition dynamics are independent of actions chosen by the agent but the rewards are not; the case of contextual bandits is a special case of this class of MDPs. Hence, policies which choose actions with low rewards would be suboptimal.\n\nPlease let us know if any of your questions were not clarified, and we would be happy to elaborate further.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JnZ5z7ZvCu", "reviewer": "Reviewer_FF9h", "summary": "The work is interested in answering the following question: \"In the RL setting, can we identify the best policy faster if we only estimate the difference between the value of individual policies?\". The paper provides a positive answer in the contextual bandit setting and a negative, but more nuanced answer for tabular RL. Exploiting the difference between value estimates of a reference policy and target policies, the authors propose an algorithm that achieves a better sample complexity than the best one in the literature so far, while matching the sample complexity achieved for contextual bandit in special settings.", "questions": "- In an A/B test scenario, we have only two policies that are compared. How does the PERP algorithm improve on naively looking at the difference (or relative difference) of the estimated value of A and B?\n\n- Intuitively, what makes the tabular RL way more difficult than the bandit setting? Can it be alleviated by adding more structure? Do we have the same guarantees for contextual bandit, with say, a linear assumption?\n\n- The PERP algorithm is complex and encapsulates other algorithms in the inner loop. Is there a way to reduce the complexity of the algorithm and come up with a more practical variant even if we lose some of the guarantees?", "limitations": "N/A.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- **Relevant Problem**: The question of reaching the optimal sample complexity of identifying the best policy (with high probability) is an important theoretical question that can have a big practical impact. \n\n- **Novel, important results**: The authors analyse the $(\\epsilon, \\delta)$-PAC policy identification for tabular RL, give valuable insight about the problem and derive an algorithm that improves on the best sample complexity obtained so far. \n\n- **The paper is beautifully written**: I genuinely enjoyed reading the first two sections. The authors do a magnificent job at introducing the problem and position their contribution in the literature. The next sections get more technical but they are still pleasant to read. The authors invest in sharing their intuition with the reader to alleviate the technical difficulties. The paper is well structured, and helps you understand the thought process of the authors which is highly appreciated.", "weaknesses": "- **The proposed algorithm is complex to implement**: As pointed out by the authors, enumerating all policies from $\\Pi$ can make the algorithm impractical. This narrows the applicability of the algorithm to simple problems even if I understand that the primary goal of the paper is of a theoretical nature.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your efforts to review the paper and for the positive feedback. Please find answers inline to your questions below.\n\n**Gains for simpler setting with two policies**\n> In an A/B test scenario, we have only two policies that are compared. How does the PERP algorithm improve on naively looking at the difference (or relative difference) of the estimated value of A and B?\n\nIn the case of two policies, if we naively rolled out each policy to estimate the difference in values, we would require $O(\\frac{1}{\\epsilon^2})$ samples from each policy to attain $\\epsilon$-optimality in the value estimate for $\\pi_1$ or $\\pi_2$. Our PERP complexity would be much smaller than this in cases where the policies agree on many states. \n\nFor instance, in the example from Figure~1, we have two policies that disagree on only the low-probability red states. Here, we attain a complexity of $O(\\frac{1}{\\epsilon})$ rather than $O(\\frac{1}{\\epsilon^2})$.\n\n**Comparison of tabular RL difficulty with contextual bandit**\n> Intuitively, what makes the tabular RL way more difficult than the bandit setting? Can it be alleviated by adding more structure? Do we have the same guarantees for contextual bandit, with say, a linear assumption?\n\nTabular RL is more difficult than the contextual bandit setting because of the cost of estimating the transitions – this is a well-known observation in the existing literature. In the contextual bandit setting, we show (Corollary 1) that the cost of learning the context distribution is at most the cost of learning the rewards. However, in the tabular RL setting, the story is exactly reversed - the cost of learning the rewards is at most that of learning the transitions. \n\nIf there is additional structure imposed, the sample complexity would accordingly reduce. For instance, when the transitions are action-independent, the complexity from Corollary 2 is the same as that from Corollary 1 for contextual bandits. For other types of structural assumptions, the complexity would depend on the type of assumption and it is difficult to say much.\n\n**Computational complexity of PERP**\n> The PERP algorithm is complex and encapsulates other algorithms in the inner loop. Is there a way to reduce the complexity of the algorithm and come up with a more practical variant even if we lose some of the guarantees?\n\nWhile the complexity of PERP could likely be reduced somewhat (for example, some of the subroutines it relies on were originally developed for linear MDPs, and could likely be simplified for tabular MDPs), at present each component of PERP seems critical for achieving the stated complexity. Developing simpler and easier-to-implement algorithms with similar sample complexity is an interesting direction for future work.\n\nPlease let us know if any of your questions were not clarified, and we would be happy to elaborate further.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents a very interesting finding regarding the sample complexity in PAC RL vs the gap of values among policies. A brilliant piece of theoretical work that is interesting to the RL community at large.
Decision: Accept (spotlight)