Sample Complexity Reduction via Policy Difference Estimation in Tabular Reinforcement Learning

Authors: adhyyan  narang
andrew  wagenmaker
lillian j ratliff
kevin  jamieson
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 20:39:38

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.

Main paper: 
 introduction: 
 Online platforms, such as AirBnB, often try to improve their services by A/B testing different marketing strategies. Based on the inventory, their strategy could include emphasizing local listings versus tourist destinations, providing discounts for longer stays, or 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 a finite set of policies Π corresponding to possible strategies. We wish to collect data by playing exploratory actions which will enable us to estimate the true value of each policy π ∈ Π, and identify the best policy from Π as quickly as possible.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 can be formally modeled as the PAC (Probably Approximately Correct) policy identification problem in reinforcement learning (RL). An algorithm is said to be (ϵ, δ)-PAC if, given a set of policies Π, it returns a policy π ∈ Π that performs within ϵ of the optimal policy in Π, with probability 1 -δ. The 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 problemguarantees 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 O(poly(S, A, H)/ϵ 2 ), 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 instance-dependent complexity measures that capture the hardness of learning each particular problem instance. However, despite progress in this direction, the question of the optimal instance-dependent complexity has remained elusive, even in tabular settings.Towards achieving instance-optimality in RL, the key question is: what aspects of a given environment must be learned, in order to choose a 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: it is only important whether a given action's value is greater or lesser than that of other actions. This observation can yield significant improvements in sample efficiency [37, 16, 13, 30] . Precisely, the best-known complexity measures in the bandit setting scale as:EQUATIONwhere ϕ π is the feature vector of action π, ϕ ⋆ the feature vector of the optimal action, ∆(π) is the suboptimality of action π. Here, Λ(π exp ) are the covariates induced by π exp , 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 π exp ) difference in values between (π, π ⋆ ). 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 Π; 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 instance-dependent complexities which scale as follows [42] :H h=1 inf πexp max π∈Π ∥ϕ π h ∥ 2 Λ h (πexp) -1 + ∥ϕ ⋆ h ∥ 2 Λ h (πexp) -1 ∆(π) 2 (1.2)where ϕ π h 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 s 1 , takes one of three actions, and then transitions to one of states s 2 , s 3 , s 4 . Consider the policy set Π = {π 1 , π 2 }, where π 1 always plays action a 1 , and π 2 is identical, except plays actions a 2 in the red states. If ϕ πi h ∈ △ S×A denotes the state-action visitations of policy π i at time h = 1, 2, then we see that ϕ π1 1 = ϕ π2 1 since π 1 and π 2 agree on the action in s 1 . But ϕ π1 2 ̸ = ϕ π2 2 as their actions differ on the red states. Since these red states will be reached with probability at most 3ϵ, the norm of the difference∥ϕ π 2 -ϕ ⋆ 2 ∥ 2 Λ2(πexp) -1 = s,a (ϕ π 2 (s, a) -ϕ ⋆ 2 (s, a)) 2 ϕ πexp 2 (s, a)is significantly less than the sum of the individual norms∥ϕ π 2 ∥ 2 Λ2(πexp) -1 + ∥ϕ ⋆ 2 ∥ 2 Λ2(πexp) -1 = s,a ϕ π 2 (s, a) 2 + ϕ ⋆ (s, a) 2 ϕ πexp 2(s, a) . The rewards for all actions other than the ones specified in the figure are 0. Define policy set Π = {π 1 , π 2 } so that π 1 always plays a 1 , whereas π 2 plays a 1 on green states but a 2 on red states. The difference of their state-action visitation probabilities is only non-zero in states s 3 , s 4 and are just O(ϵ) apart.Intuitively, to minimize differences π exp can explore just states s 3 , s 4 where the policies differ, whereas minimizing the individual norms requires wasting lots of energy in state s 2 where the two policies and the difference is zero. Formally: Proposition 1. On the MDP and policy set Π from Figure 1 , we have thatinf πexp max π∈Π ∥ϕ π 2 ∥ 2 Λ2(πexp) -1 ≥ 1 and inf πexp max π∈Π ∥ϕ ⋆ 2 -ϕ π 2 ∥ 2 Λ2(πexp) -1 ≤ 15ϵ 2 .Proposition 1 shows that indeed, the complexity of 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 a factor of ϵ 2 better. But achieving a sample complexity that depends on the differences requires more than just a better analysis: it requires a new estimator and an algorithm to exploit it.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 a variety of other works over the following decade [38, 4, 34, 39] , leading up to works such as [28, 9] , which establish sample complexity bounds of O(S 2 A • poly(H)/ϵ 2 ).More recently, [10, 11, 33] have proposed algorithms which achieve the optimal dependence of O(SA • poly(H)/ϵ 2 ), with [11, 33] also achieving the optimal H 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.Instance-Dependence in RL. While the problem of obtaining worst-case optimal guarantees in tabular RL is nearly closed, we are only beginning to understand what types of instance-dependent 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 algorithms achieve regret bounded as O( s,a,h log K ∆ h (s,a) ), a result later refined by [47, 12] . In settings of RL with linear function approximation, several works achieve instance-dependent regret guarantees [18, 44] . Recently, Wagenmaker and Foster [45] achieved finite-time guarantees on instance-optimal regret in general decision-making 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 a generative model or lacking finite-time results. The work of Wagenmaker et al. [46] achieves a finite-time instance-dependent guarantee for tabular RL, introducing a 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-dependent upper and lower bounds. For RL with linear function approximation, [42, 43] achieve instance-dependent guarantees on policy identification, in particular, the complexity given in (1.2) , and propose an algorithm, PEDEL, which directly inspires our algorithmic approach. On the lower bound side, Al-Marjani et al. [2] show that ρ Π is necessary for tabular RL, but fail to close the aforementioned gap between ρ Π 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-without 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-dependent optimal linear bandit algorithms for regret [29, 27] . More recently, contextual bandits have also been given a similar treatment [40, 30] .Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes]• Please see the NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not 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 NeurIPS code and data submission guidelines (https: //nips.cc/public/guides/CodeSubmissionPolicy) 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. If only a 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 as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
preliminaries and problem setting: 
 Let ∥x∥ 2 Λ = x ⊤ Λx for any (x, Λ). We let E π denote the probability measure induced by playing policy π 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, {P h } H h=1 , {ν h } H h=1 ) where the state space S and action space A are finite, H is the horizon, P h ∈ R S×SA denote the transition matrix at stage h where [P h ] s ′ ,sa = P(s h+1 = s ′ |s h = s, a h = a), and ν h (s, a) ∈ △ [0,1] denote the distribution over reward at stage h when the state of the system is s and action a is chosen. Let r h (s, a) be the expectation of a reward drawn from ν h (s, a). We assume that every episode starts in state s 1 , and that ν h and P h are initially unknown and must be estimated over time.Let π = {π h } H h=1 denote a policy mapping states to actions, so that π h (s) ∈ △ A denotes the distribution over actions for the policy at (s, h); when the policy is deterministic, π h (s) ∈ A outputs a single action. An episode begins in state s 1 , the agent takes action a 1 ∼ π 1 (s 1 ) and receives reward R 1 ∼ ν 1 (s 1 , a 1 ) with expectation r 1 (s 1 , a 1 ); the environment transitions to state s 2 ∼ P h (s 1 , a 1 ). The process repeats until timestep H, at which point the episode ends and the agent returns to states 1 . Let V π h (s) = E π [ H h ′ =h r h ′ (s h ′ , a h ′ )|s h = s], V π 0 the total expected reward, V π 0 := V π 1 (s 0 ), and Q π h (s, a) = E π [ H h ′ =h r h ′ (s h ′ , a h ′ )|s h = s, a h = a]the amount of reward we expect to collect if we are in state s at step h, play action a and then play policy π for the remainder of the episode. Note that we can understand these functions as S and SA-dimensional vectors respectively. We use V π = V π 0 when clear from context. We call w π h ∈ △ S the state visitation vector at step h for policy π, so that w π h (s) captures the probability that policy π would land in state s at step h during an episode. Let π h ∈ R SA×S denote the policy matrix for policy π, that maps states to state-actions as follows[π h ] (s,a),s ′ = I(s = s ′ )[π h (s)] a .Denote ϕ π h ∈ △ SA as ϕ π h := π h w π h as the state-action visitation vector: ϕ π h (s, a) measures the the probability that policy π would land in state s and play action a at step h during an episode. From these definitions, it follows that[P h ϕ π h ] s = [P h π h w π h ] s = w π h+1 (s).For policy π, denote the covariance matrix at timestep h as Λ h (π) = s,a ϕ π h (s, a)e (s,a) e ⊤ (s,a) .(ϵ, δ)-PAC Best Policy Identification. For a collection of policies Π, define π ⋆ := arg max π∈Π V π as the optimal policy, V ⋆ its value, and ϕ ⋆ h as its state-action visitation vector. Let ∆ min := min π∈Π\{π ⋆ } V ⋆ -V π in the case when π ⋆ is unique, and otherwise ∆ min := 0. Define ∆(π) := max{V ⋆ -V π , ∆ min }. Given ϵ ≥ 0, δ ∈ (0, 1) an algorithm is said to be (ϵ, δ)-PAC if at a stopping time τ of its choosing, it returns a policy π which satisfies ∆(π) ≤ ϵ with probability 1 -δ. Our goal is to obtain an (ϵ, δ)-PAC algorithm that minimizes τ . A fundamental complexity measure used throughout this work is defined asρ Π := H h=1 inf πexp max π∈Π ∥ϕ ⋆ h -ϕ π h ∥ 2 Λ h (πexp) -1 max{ϵ 2 , ∆(π) 2 } for ∥ϕ ⋆ h -ϕ π h ∥ 2 Λ h (πexp) -1 := s,a (ϕ ⋆ h (s,a)-ϕ π h (s,a)) 2 ϕ πexp h (s,a)where the infimum is over all exploration policies π exp (not necessarily just those in Π). Recall that for ϵ = 0, [2] showed any (ϵ, δ)-PAC algorithm satisfiesE[τ ] ≥ ρ Π log( 1 2.4δ ).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 ρ Π is not sufficient. We have the following result. Lemma 1. For the MDP M and policy set Π from Figure 1,  1.H h=1 inf πexp max π∈Π ∥ϕ ⋆ h -ϕ π h ∥ 2 Λ h (πexp ) -1 max{ϵ 2 ,∆(π) 2 } ≤ 15, 2. Any (ϵ, δ)-PAC algorithm must collect at least E M [τ ] ≥ 1 ϵ • log 1 2.4δ. samples. Where does the additional complexity arise on the instance of Figure 1 ? As described in the introduction, π 1 and π 2 differ only on the red states, and a complexity scaling as ρ Π quantifies only the difficulty of distinguishing {π 1 , π 2 } on these states. Note that on this example π 1 plays the optimal action in state s 3 and a suboptimal action in state s 4 , and π 2 plays a suboptimal action in s 3 and the optimal action in s 4 . The total reward of policy π 1 is therefore equal to the reward achieved at state s 3 times the probability it reaches state s 3 , and the total reward of policy π 2 is the reward achieved at state s 4 times the probability it reaches state s 4 . Here, ρ Π 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 π 1 or π 2 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 {ν h } h and not the state transition matrices {P h } 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 ρ Π 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 as efficiently as possible. 
main result: 
 If ρ Π 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 π, π ∈ Π, we defineEQUATIONNow, we state our main result. Theorem 1. There exists an algorithm (Algorithm 1) which, with probability at least 1 -2δ, finds an ϵ-optimal policy and terminates after collecting at most Theorem 1 shows that, up to terms lower-order in ϵ and ∆ min , ρ Π is almost sufficient, if we are willing to pay for an additional term scaling as U (π, π ⋆ )/∆(π) 2 . Recognize the similarity of this term to the that from the performance difference lemma: if there were no square inside the expectation, the quantity U (π, π ⋆ ) 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] .EQUATIONWe revisit the instance from Figure 1 to show this; recall from Lemma 1 that the first term from Theorem 1 is a universal constant for this instance. Lemma 2. On MDP M and policy set Π from Figure 1 , we have:1. max π∈Π HU (π,π ⋆ ) max{ϵ 2 ,∆(π) 2 } = 3H ϵ , 2. H h=1 inf πexp max π∈Π ∥ϕ π h ∥ 2 Λ h (πexp) -1 max{ϵ 2 ,∆(π) 2 } ≥ H ϵ 2 .Furthermore, the complexity of Theorem 1 is never worse than Equation (1.2). Lemma 3. For any MDP instance and policy set Π, we have thatmax H h=1 inf πexp max π∈Π ∥ϕ ⋆ h -ϕ π h ∥ 2 Λ h (πexp) -1 max{ϵ 2 , ∆(π) 2 } , HU (π, π ⋆ ) max{ϵ 2 , ∆(π) 2 } ≤ H h=1 inf πexp max π∈Π ∥ϕ π h ∥ 2 Λ h (πexp) -1 max{ϵ 2 , ∆(π) 2 } .We briefly remark on the lower-order term for Theorem 1,C poly max{ϵ 5/3 ,∆ 5/3 min }. Note that for small ϵ or ∆ min , this term will be dominated by the leading-order terms, which scale with min{ϵ -2 , ∆ -2 min }. While we make no claims on the tightness of this term, we note that recent work has shown that some lower-order terms are necessary for achieving instance-optimality [45] .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 Π). Here µ can be thought of as playing the role of π exp . Or, we can consider the A/B testing scenario from the introduction, where a policy µ is taking random actions and one wishes to perform off-policy estimation over some set of policies Π [17, 15] . For any s ∈ S, we define δ π h (s) := w π h (s) -w π h (s) as the difference in state-visitations of policy π from reference policy π, and δ π h ∈ R S as the vectorization of δ π h (s ′ ).Policy selection rule. First, we describe our procedure of data collection and estimation. We collect K π trajectories from π and K µ trajectories from µ, and let { w π h (s)} s,h denote the empirical state visitations from playing π. From the data collected by playing µ, we construct estimates { P h (s ′ |s, a)} s,a,s ′ ,h of the transition matrices. Note that w π h (s) simply counts visitations, so thatE[( w π h (s) -w π h (s)) 2 ] ≤ w π h (s)Kπ for all h, s. Define estimated state visitations for policy π in terms of deviations from π as w π h := w π h + δ π h . Here, δ π h is defined recursively as:δ π h+1 := P h π h δ π h + P h (π h -πh ) w π hThen, assuming, for simplicity, that rewards are known, we recommend the following policy:π = arg max π∈Π D π where D π := H h=1 ⟨r h , π h δ π h ⟩ -⟨r h , ( πh -π h ) w π h ⟩Sufficient condition for ϵ-optimality. Here, we show that if∀π ∈ Π, | D π -D π | ≤ 1 3 max{ϵ, ∆(π)} (4.2)then π is ϵ-optimal. First, write the difference between values of policies π and π as:D π := V π 0 -V π 0 = H h=1 ⟨r h , π h w π h ⟩ - H h=1 ⟨r h , πh w π h ⟩ = H h=1 ⟨r h , π h δ π h ⟩ -⟨r h , ( πh -π h )w π h ⟩. (4.3)Then, it is easy to verify that if| D π -D π | ≤ 1/3 ∆(π), then D π ⋆ -D π ≥ 0; hence, π ̸ = π. Hence, under Condition (4.2), either π = π ⋆ or or | D π -D π | ≤ ϵ.In the first case, clearly π is ϵ-optimal.In the second case, we can add and subtract terms to writeV ⋆ -V π ≤ |D π ⋆ -D π ⋆ | + D π ⋆ -D π + | D π -D π | ≤ 2ϵ 3 + Dπ ⋆ -D π ≤ 2ϵ 3 .The last inequality follows since π maximizes D π . Hence, π would be ϵ-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), we observe thatδ π h+1 -δ π h+1 ≈ ( P h -P h )(ϕ π h -ϕ π h ) + P h (π h -πh )( w π h -w π h ) + P h π h ( δ π h -δ π h ) = h k=0 h j=k+1 P j π j ( P k -P k )(ϕ π k -ϕ π k ) + P k (π k -πk )( w π k -w π k ) .After manipulating this expression a bit more, we observe thatH h=1 ⟨r h , π h ( δ π h -δ π h )⟩ = H-1 k=0 ⟨V π k+1 , ( P k -P k )(ϕ π k -ϕ π k ) + P k (π k -πk )( w π k -w π k )⟩ Recognizing Q π h = r h + P ⊤ h V π h+1 , | D π -D π | = H h=1 ⟨r h , π h ( δ π h -δ π h )⟩ + ⟨r h , (π h -πh )( w π h -w π h )⟩ = H-1 h=0 ⟨V π h+1 , ( P h -P h )(ϕ π h -ϕ π h )⟩ + ⟨r h + P ⊤ h V π h+1 , (π h -πh )( w π h -w π h )⟩We can bound this as:≲ H 2 H-1 h=0 s,a (ϕ π h (s, a) -ϕ π h (s, a)) 2 K µ µ h (s, a) + H-1 h=0 s Q π h (s, π h (s)) -Q π h (s, πh (s)) 2 w π h (s) K π = H 2 H-1 h=0 ∥ϕ π h -ϕ π h ∥ 2 Λ h (µ) -1 K µ + U (π, π) K π .Here, we applied Bernstein's inequality and observed that s ′ V π h+1 (s ′ ) 2 P h (s ′ |s, a) ≤ H 2 . Now, we have that ifK µ ≳ max π∈Π H-1 h=0 H 2 ∥ϕ π h -ϕ π h ∥ 2 Λ h (µ) -1 max{ϵ 2 , ∆(π) 2 } and K π ≳ max π∈Π U (π, π) max{ϵ 2 , ∆(π) 2 } (4.4)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 π = π ⋆ and minimize over all logging/exploration policies µ/π exp . Note that, if V denotes the average reward collected from rolling out π K π times, then| V -V π 0 | ≤ H 2Kπ by Hoeffding's inequality. Thus, one could use V π = D π + V as an effective off-policy estimator. Likewise, D π -D π ′ is an effective estimator for V π 0 -V π ′ 0 . This calculation (elaborated on in Appendix A) suggests that our analysis is tight, and clearly illustrates that the U (π, π) term arises due to estimating the behavior of the reference policy w π h . The U (π, π) 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 is estimated, as it 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 of each policy at this state. This is reflected by the term inside the expectation of U (π, π); this will be 0 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 π, that had been played for a long time, so that K π ≈ ∞, then we would only incur the K µ term; this is precisely ρ Π , but with π ⋆ replaced with our reference policy π in the numerator. 
achieving theorem 1: perp algorithm: 
 While the above section provides intuition for where the terms in Theorem 1 come from, it does not lead to a practical algorithm. This is because the desired number of samples in Equation (4.4) are in terms of unknown quantities:{∥ϕ π h -ϕ π h ∥ 2 Λ h (µ) -1, ∆(π), U (π, π)}, which depend on our unknown environment variables ν h , P h ; hence, we would not know how many samples to collect. In this section, we propose an algorithm that will proceed in rounds, successively improving our estimates of these quantities. DefineEQUATIONwhere E π ′ ,ℓ denotes the expectation induced playing policy π ′ on the MDP with transitions P ℓ,h , and Q π ℓ,h denotes the Q-function of policy π on this same MDP. To compute P ℓ,h , we use the standard estimator: (s,a) for N ℓ,h (s, a) and N ℓ,h (s, a, s ′ ) the visitation counts in D ED ℓ,h . We set P ℓ,h (s ′ | s, a) = unif(S) if N ℓ,h (s, a) = 0. The analogous estimator is used to estimate r ℓ,h . The quantity ϕ π h -ϕ π h is estimated as in the previous section:P ℓ,h (s ′ | s, a) = N ℓ,h (s,a,s ′ ) N ℓ,h(π h -πℓ,h ) w π ℓ,h + π h δ π ℓ,h. Algorithm 1 proceeds in epochs. It begins with a policy set Π 1 , which contains all policies of interest, Π. It then gradually begins to 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 a reference policy πℓ , then running this estimate a sufficient number of times to estimate w πℓ h . Given this estimate, it then seeks to estimate δ π h for each π in the active set of policies, Π ℓ , by collecting data covering the directions (π h -πℓ,h ) w π ℓ,h + π h δ π ℓ,h 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 δ π h , it estimates the differences between policy values as in (4.3), and eliminates suboptimal policies. The computational complexity of PERP is poly (S, A, H, 1/ϵ, |Π|, log(1/δ)). 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 Franke-Wolfe algorithm is bounded polynomially in the problem parameters, Compute U ℓ-1,h (π, π ′ ) as in (5.1) for all (π, π ′ ) ∈ Π ℓ 6:Choose πℓ ← min π∈Π ℓ max π∈Π ℓ H h=1 U ℓ-1,h (π, π) 7:Collect the following number of episodes from πℓ and store in dataset Run OPTCOV (Algorithm 3) to collect dataset D ED ℓ,h such that: EQUATIONsup π∈Π ℓ ∥(π h -πℓ,h ) w π ℓ,h + π h δ π ℓ,h ∥ 2 Λ -1 ℓ,h ≤ ϵ 2 ℓ /H 4 β 2 ℓ for Λ ℓ,h = (s,Compute D πℓ (π) ← h ⟨ r ℓ,h , π h δ ℓ,h ⟩ + h ⟨ r ℓ,h , (π h -πℓ,h ) w π ℓ,h ⟩ 18: Update Π ℓ+1 = Π ℓ \{π ∈ Π ℓ : max π ′ D πℓ (π ′ ) -D πℓ (π) > 8ϵ ℓ } 19:if |Π ℓ+1 | = 1 then return π ∈ Π ℓ+1 20: end for 21: return any π ∈ Π ℓ+1 and from the definition of this procedure given in Wagenmaker and Pacchiano [43] , we see that each iteration of Franke-Wolfe has computational complexity polynomial in problem parameters. We omit several technical details from Algorithm 1 for simplicity, but present the full definition in Algorithm 2.6 When is ρ Π Sufficient?Our results so far show that ρ Π is 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 case of the RL setting with H = 1 and where the initial action does not affect the next-state transition. Theorem 2.2 of Li et al. [30] show that if the rewards distributions ν(s, a) are Gaussian for each (s, a), where here s denotes the context, any (0, δ)-PAC algorithm requires at least ρ Π samples. Crucially, however, they assume that the context distribution-in this case corresponding to the initial transition P 1 -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 is not critical-we can achieve a complexity of O(ρ Π ) without this prior knowledge.Corollary 1. For the setting of tabular contextual bandits, there exists an algorithm such that with probability at least 1 -2δ, as long as Π contains only deterministic policies, it finds an ϵ-optimal policy and terminates after collecting at most the following number of samples:inf πexp max π∈Π ∥ϕ ⋆ -ϕ π ∥ 2 Λ(πexp) -1 max{ϵ 2 , ∆(π) 2 } • β 2 log 1 ∆ min ∨ ϵ + C poly max{ϵ 5/3 , ∆ 5/3 min } , for C poly = poly(|S|, A, log 1/δ, log 1/(∆ min ∨ ϵ), log |Π|) and β = C log( S|Π| δ • 1 ∆min∨ϵ ).The theorem is proved in Appendix D, and follows from the application of our algorithm PERP to the contextual bandit problem. The key intuition behind this result is that, in the contextual case:U (π, π) = E s∼P1 [(r 1 (s, π 1 (s)) -r 1 (s, π1 (s)) 2 ] ≤ E s∼P1 [I{π 1 (s) ̸ = π1 (s)}].It is then possible to show that, since π exp only has choices of which actions are taken (and cannot affect the context distribution), this can be further bounded by inf πexp ∥ϕ π -ϕ π ∥ 2 Λ(πexp) -1 . This is not true in the full MDP case, where our choice of exploration policy in π exp could make inf πexp ∥ϕ πϕ π ∥ 2 Λ(πexp) -1 significantly smaller than U (π, π) (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 RL, where our complexity from Theorem 1 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.MDPs with Action-Independent Transitions. In the special case of MDPs where the transitions do not depend on the actions selected, the complexity simplifies to O(ρ Π ). Note that this exactly matches (up to lower order terms) the lower bound from [2] . Corollary 2. Assume that all P h are such that P h (s ′ |s, a) = P h (s ′ |s, a ′ ) for all (a, a ′ ) ∈ A. Then, with probability at least 1 -2δ, PERP (Algorithm 2) finds an ϵ-optimal policy and terminates after collecting at most the following number of episodes:H h=1 inf πexp max π∈Π ∥ϕ ⋆ h -ϕ π h ∥ 2 Λ h (πexp) -1 max{ϵ 2 , ∆(π) 2 } • ιH 4 β 2 + C poly max{ϵ 5/3 , ∆ 5/3min } for C poly , β as defined in Theorem 1.The intuition for Corollary 2 is similar to that of Corollary 1, and proved in Appendix E. 
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?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 of 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, or as supplemental material. 
discussion: 
 In this paper, we performed a fine-grained study of the instance-dependent complexity of tabular RL. We proposed a new 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.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 Π 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-dependent 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 upper bound has unfortunate low order terms; can these be removed? Can one show thatU (π,π) max{∆(π) 2 ,ϵ 2 }is unavoidable for all MDPs in general, thereby matching our upper bound? As discussed above, a 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? Difference in value between policy π and reference policy U h (π, π ′ ) Expected squared difference in Q-valuesThis section is inspired by the exposition of Soare et al. [37] for justifying the sample complexity of linear bandits. Fix a reference policy π and some (stochastic) logging policy µ. For K ∈ N to be determined later, roll out π K times and compute the empirical state visitations w π h (s) =1 K K k=1s,h 1{s k h = s}. Also roll out µ K times and compute the empirical transition probabilitiesP h (s ′ |s, a) = K k=1 1{(s k h ,a k h ,s k h+1 )=(s,a,s ′ )} K k=1 1{(s k h ,a k h )=(s,a)} . For any π ̸ = π, use { P h (s ′ |s, a)} s,a,s ′ ,h to compute w π h (s). With δ π h+1 := w π h+1 -w π h+1 = P h π h w π h -P h πh w π h = P h π h δ π h + P h (π h -πh )w π h set D(π) = V π 0 -V π 0 = H h=1 ⟨r h , π h w π h -πh w π h ⟩ = H h=1 ⟨r h , π h δ π h ⟩ + ⟨r h , (π h -πh )w π h ⟩and also define the empirical counterparts δ π h+1:= P h π h δ π h + P h (π h -πh ) w π h with D(π) = H h=1 ⟨r h , π h δ π h ⟩ + ⟨r h , (π h -πh ) w π h ⟩.If π = arg max π∈Π D(π), how large must K be to ensure that π = π ⋆ := arg max π∈Π D(π) = arg max π∈Π V π 0 ? Assume at time h = 0 all policies are initialized arbitrarily in some state s 0 so that P 0 (s ′ |s 0 , a) simply defines the initial empirical state distribution at time h = 1. Let w π 0 (s 0 ) = w π 0 (s 0 ) = 1 We can then unroll the recursion for h = 0, . . . , H -1δ π h+1 -δ π h+1 = P h π h δ π h + P h (π h -πh ) w π h -δ π h+1 = ( P h -P h )π h δ π h + ( P h -P h )(π h -πh )w π h + P h (π h -πh )( w π h -w π h ) + P h π h ( δ π h -δ π h ) + ( P h -P h )π h ( δ π h -δ π h ) + ( P h -P h )(π h -πh )( w π h -w π h )Low order terms ≈ 0≈ ( P h -P h )(ϕ π k -ϕ π k ) + P h (π h -πh )( w π h -w π h ) + P h π h ( δ π h -δ π h ) ≈ h i=0 h j=h-i+1 P j π j ( P h-i -P h-i )(ϕ π h-i -ϕ π h-i ) + P h-i (π h-i -πh-i )( w π h-i -w π h-i ) = h k=0 h j=k+1 P j π j ( P k -P k )(ϕ π k -ϕ π k ) + P k (π k -πk )( w π k -w π k )where we recallϕ π k = π k w π k . If ϵ k+1 := ( P k -P k )(π h w π k -πw π k ) + P k (π k -πk )( w π k -w π k ) then H h=1 ⟨r h , π h ( δ π h -δ π h )⟩ = H h=1 h-1 k=0 ⟨r h , π h h-1 j=k+1 P j π j ϵ k+1 ⟩ = H-1 k=0 H h=k+1 ⟨r h , π h h-1 j=k+1 P j π j ϵ k+1 ⟩ = H-1 k=0 ⟨V π k+1 , ϵ k+1 ⟩ = H-1 k=0 ⟨V π k+1 , ( P k -P k )(ϕ π k -ϕ π k ) + P k (π k -πk )( w π k -w π k )⟩.Finally, we use these calculations to compute the deviation D(π) -D(π) = H h=1 ⟨r h , π h ( δ π h -δ π h )⟩ + ⟨r h , (π h -πh )( w π h -w π h )⟩ = H-1 h=0 ⟨V π h+1 , ( P h -P h )(ϕ π h -ϕ π h )⟩ + ⟨r h + P ⊤ h V π h+1 , (π h -πh )( w π h -w π h )⟩ = H-1 h=0 ⟨V π h+1 , ( P h -P h )(ϕ π h -ϕ π h )⟩ + ⟨Q π h , (π h -πh )( w π h -w π h )⟩ = H-1 h=0 s,a,s ′ V π h+1 (s ′ )( P h (s ′ |s, a) -P h (s ′ |s, a))(ϕ π h (s, a) -ϕ π h (s, a)) + H-1 h=0 s Q π h (s, π h (s)) -Q π h (s, πh (s)) ( w π h (s) -w π h (s)) ≲ H-1 h=0 s,a,s ′ V π h+1 (s ′ ) 2 P h (s ′ |s, a) Kµ h (s, a) (ϕ π h (s, a) -ϕ π h (s, a)) 2 + H-1 h=0 s Q π h (s, π h (s)) -Q π h (s, πh (s)) s 1 s 2 s 3 s 4 a 1 a 2 a 3 1 -3ϵ ϵ 1 ϵ 2 1 1 r1(s1, a1) = 1 r2(s3, a1) = 1 r2(s4, a2) = 1Applying s ′ V π h+1 (s ′ ) 2 P h (s ′ |s, a) ≤ H 2 , we observe that if K ≥ min µ,π max π H 2 H-1 h=1 s,a (ϕ π h (s, a) -ϕ π h (s, a)) 2 /µ h (s, a) ∆(π) 2 + H-1 h=1 s Q π h (s, π h (s)) -Q π h (s, πh (s)) 2 w π h (s) ∆(π) 2and we employ the minimizers µ, π to collect data, then D(π) -D(π) < ∆(π) and π = arg max π∈Π D(π) = arg max π∈Π D(π). Notice that up to H and log factors, this is precisely the sample complexity of our algorithm. A natural candidate for π is π ⋆ so that the first term matches the lower bound of [2] .On the other hand, suppose we used the data from the logging policy µ to compute the empirical state visitations w π h for all π ∈ Π and set π = arg max π∈Π H h=1 ⟨r h , π w π h ⟩ =: V π 0 . Using the same techniques as above, it is straightforward to show that ifw π h+1 -w π h+1 = P h π h w π h -P h π h w π h = ( P h -P h + P h )π h ( w π h -w π h + w π h ) -P h π h w π h = ( P h -P h )π h w π h + P h π h ( w π h -w π h ) + ( P h -P h )π h ( w π h -w π h ) Low order terms ≈ 0 ≈ h i=0 h j=h-i+1 P j π j ( P h-i -P h-i )π h-i w π h-i = h k=0 h j=k+1 P j π j ( P k -P k )π k w π kand we employ the minimizer µ to collect data, thenV π 0 -V π 0 ≤ ∆(π) and π = arg max π∈Π V π 0 = arg max π∈Π V π 0 .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 ϵ, ϵ 1 , ϵ 2 > 0, with H = 2, S = {s 1 , s 2 , s 3 , s 4 }, and A = {a 1 , a 2 , a 3 }, which start in state s 0 and are defined as:P 1 (s 2 | s 1 , a 1 ) = 1 -3ϵ, P 1 (s 3 | s 1 , a 1 ) = ϵ 1 , P 1 (s 4 | s 1 , a 1 ) = ϵ 2 P 1 (s 3 | s 1 , a 2 ) = P 1 (s 4 | s 1 , a 3 ) = 1.We define the reward function so that all rewards are 0 except r 1 (s 1 , a 1 ) = r 2 (s 3 , a 1 ) = r 2 (s 4 , a 2 ) = 1 for all a.Let M denote the MDP above with ϵ 1 = 2ϵ, ϵ 2 = ϵ, and M ′ the MDP above with ϵ 1 = ϵ, ϵ 2 = 2ϵ.Let Π = {π 1 , π 2 } denote some set of policies. Let π 1 denote the policy which always plays a 1 , and π 2 the policy which plays a 1 at green states and a 2 at red states i.e π 2 (s1 ) = π 2 (s 2 ) = a 1 and π 2 (s 3 ) = π 2 (s 4 ) = a 2 . Now note that V M,π1 0 = 1 + 2ϵ, V M,π2 0 = 1 + ϵ, V M ′ ,π1 0 = 1 + ϵ, and V M ′ ,π2 0 = 1 + 2ϵ.The lemma below shows that the upper bound presented in Theorem 1 is smaller than that of PEDEL from Theorem 1 of [42] for all MDP instances. Lemma 4. For any MDP instance and policy set Π, we have that1. inf πexp max π∈Π ∥ϕ π h ∥ 2 Λ h (πexp ) -1 max{ϵ 2 ,∆(π) 2 ,∆ 2 min } ≥ 1 max{ϵ 2 ,∆(π) 2 ,∆ 2 min }2.H 4 H h=1 inf πexp max π∈Π ∥ϕ ⋆ h -ϕ π h ∥ 2 Λ h (πexp) -1 max{ϵ 2 , ∆(π) 2 , ∆ 2 min } ≤ 4H 4 H h=1 inf πexp max π∈Π ∥ϕ π h ∥ 2 Λ h (πexp) -1 max{ϵ 2 , ∆(π) 2 , ∆ 2 min } 3. HU (π,π ⋆ ) max{ϵ 2 ,∆(π) 2 ,∆ 2 min } ≤ H 4 H h=1 inf πexp max π∈Π ∥ϕ π h ∥ 2 Λ h (πexp) -1 max{ϵ 2 ,∆(π) 2 ,∆ 2 min } Proof. Proof of Claim 1. Note that ∥ϕ π h ∥ 2 Λ h (πexp) -1 = s,a ϕ π h (s, a) 2 ϕ πexp h (s, a) ≥ inf λ∈∆ SA s,a ϕ π h (s, a) 2 λ s,aIn order to solve this optimization problem, we can consider the KKT conditions. We can verify from stationarity that at optimality, λ s,a =ϕ π h (s,a) √ βfor some constant β > 0. But since λ s,a must live in the simplex ∆ SA , and since ϕ π h (s, a) is itself a distribution over S × A, it follows that β = 1 must be true. Plugging this optimal value into the above, we obtain that∥ϕ π h ∥ 2 Λ h (πexp) -1 ≥ inf λ∈∆ SA s,a ϕ π h (s, a) 2 λ s,a = 1Then,inf πexp max π∈Π ∥ϕ π h ∥ 2 Λ h (πexp) -1 max{ϵ 2 , ∆(π) 2 , ∆ 2 min } ≥ 1 max{ϵ 2 , ∆(π) 2 , ∆ 2min } directly follows from the above.Proof of Claim 2. From the triangle inequality,inf πexp max π∈Π ∥ϕ ⋆ h -ϕ π h ∥ 2 Λ h (πexp) -1 max{ϵ 2 , ∆(π) 2 , ∆ 2 min } ≤ 2 inf πexp max π∈Π ∥ϕ ⋆ h ∥ 2 Λ h (πexp) -1 max{ϵ 2 , ∆(π) 2 , ∆ 2 min } + ∥ϕ π h ∥ 2 Λ h (πexp) -1 max{ϵ 2 , ∆(π) 2 , ∆ 2 min } ≤ 2 inf πexp max π∈Π ∥ϕ ⋆ h ∥ 2 Λ h (πexp) -1 max{ϵ 2 , ∆(π ⋆ ) 2 , ∆ 2 min } + ∥ϕ π h ∥ 2 Λ h (πexp) -1 max{ϵ 2 , ∆(π) 2 , ∆ 2 min } ≤ 4 inf πexp max π∈Π ∥ϕ π h ∥ 2 Λ h (πexp) -1 max{ϵ 2 , ∆(π) 2 , ∆ 2min } where we have used that ∆(π) ≥ ∆(π ⋆ ) for all π. Plugging this bound into the expression from (2) from the Lemma statement completes the proof.Proof of Claim 3. We have thatHU (π, π ⋆ ) = H H h=1 E s h ∼w π ⋆ h [(Q π h (s h , π h (s)) -Q π h (s h , π ⋆ h (s))) 2 ] ≤ H H h=1 H 2 ≤ H 4Then,HU (π, π ⋆ ) max{ϵ 2 , ∆(π) 2 , ∆ 2 min } ≤ H 4 max{ϵ 2 , ∆(π) 2 , ∆ 2 min } ≤ H 4 H h=1 inf πexp max π∈Π ∥ϕ π h ∥ 2 Λ h (πexp) -1 max{ϵ 2 , ∆(π) 2 , ∆ 2 min }Where the final inequality follows from Claim 1 above.The lemma below shows that there are some instances where the complexity from Theorem 1 is strictly smaller in terms of ϵ dependence than that from Theorem 1 from [42] for PEDEL. Lemma 5. On MDP M defined above, we have:1. H h=1 inf πexp max π∈Π ∥ϕ ⋆ h -ϕ π h ∥ 2 Λ h (πexp ) -1 max{ϵ 2 ,∆(π) 2 ,∆ 2 min } ≤ 15 2. max π∈Π HU (π,π ⋆ ) max{ϵ 2 ,∆(π) 2 ,∆ 2 min } = 3H ϵ 3. H h=1 inf πexp max π∈Π ∥ϕ π h ∥ 2 Λ h (πexp) -1 max{ϵ 2 ,∆(π) 2 ,∆ 2 min } ≥ H ϵ 2Proof. Proof of 1. In this case we have that π * = π 1 , and the only other π of interest is π 2 . Note that π 1 and π 2 differ only at state s 3 and s 4 at h = 2. Let π exp be the policy that plays actions uniformly at random. Then, we haveH h=1 inf πexp max π∈Π ∥ϕ ⋆ h -ϕ π h ∥ 2 Λ h (πexp) -1 max{ϵ 2 , ∆(π) 2 , ∆ 2 min } ≤ inf πexp ∥ϕ π1 2 -ϕ π2 2 ∥ 2 Λ h (πexp) -1 ϵ 2 = 1 ϵ 2 w π1 2 (s 3 ) 2 w πexp 2 (s 3 ) + w π1 2 (s 4 ) 2 w πexp 2 (s 4 ) ≤ 1 ϵ 2 4ϵ 2 1/3 + ϵ 2 1/3 = 15. Proof of 2. Note that max π∈Π HU (π, π ⋆ ) max{ϵ 2 , ∆(π) 2 , ∆ 2 min } = HU (π 2 , π 1 ) ϵ 2 .Then,U (π 2 , π 1 ) = H h=1 E s∼w π 1 h [(Q π1 h (s, π 1,h (s)) -Q π1 h (s, π 2,h (s))) 2 ] = E s∼w π 1 2 [(Q π1 2 (s, π 1,2 (s)) -Q π1 2 (s, π 2,2 (s))) 2 ] = 2ϵ + ϵ = 3ϵ.Combining these proves the result.Proof of 3. By Claim 1 in Lemma 4, the stated result then follows by recognizing thatmax{ϵ 2 , ∆(π) 2 , ∆ 2 min } ≤ ϵ 2 .B.2 Lower bound Lemma 6. On MDP M defined above, any (ϵ, δ)-PAC algorithm must collectE M [τ ] ≥ 1 ϵ • log 1 2.4δ.Proof. Consider Π, M, and M ′ defined above. Let E denote the event { π = π 1 }. By the above observations, we have that π 1 is ϵ-optimal on M while π 2 is not, and that π 2 is ϵ-optimal on M ′ while π 1 is not. Then by the definition of an (ϵ, δ)-PAC algorithm,P M [E] ≥ 1 -δ and P M ′ [E] ≤ δ.Let γ h (s, a) denote the distribution of (r h , s h+1 ) given (s, a, h) on M, and γ ′ h (s, a) is the same on M ′ . Then, letting ν h ← γ h , ν ′ h ← γ ′ h and otherwise adopting the same notation as in Lemma F.1 of [46] , we have from Lemma F.1 of [46] that:s,a,h E M [N τ h (s, a)]KL(γ h (s, a), γ ′ h (s, a)) ≥ sup E ′ ∈Fτ d(P M [E ′ ], P M ′ [E ′ ]) ≥ d(P M [E], P M ′ [E]) ≥ log 1 2.4δwhere the last inequality follows from [23] .Note that M and M ′ differ only at (s 1 , a 1 ), sos,a,h E M [N τ h (s, a)]KL(γ h (s, a), γ ′ h (s, a)) = E M [N τ 1 (s 1 , a 1 )]KL(γ 1 (s 1 , a 1 ), γ ′ 1 (s 1 , a 1 )).Furthermore, we see thatKL(γ 1 (s 1 , a 1 ), γ ′ 1 (s 1 , a 1 )) = 2ϵ log 2ϵ ϵ + ϵ log ϵ 2ϵ ≤ ϵ.So it follows that we must haveE M [N τ 1 (s 1 , a 1 )] ≥ 1 ϵ • log 1 2.4δ.Noting that E M [N τ 1 (s 1 , a 1 )] ≤ E M [τ ] completes the proof. C Tabular MDP Upper Bound C.1 NotationCovariance matrices. We useΛ h (π exp ) = E πexp [e s h a h e ⊤ s h a h ]to denote the expected covariance matrix and Λ ℓ,h to denote the empirical covariance matrix collected fromD ED ℓ,h . State visitations. Let δ π ℓ,h (s ′ ) := w π h (s ′ ) -w πℓ h (s ′ ),for πℓ the reference policy, δ π ℓ,h the vectorization of δ π ℓ,h (s ′ ), and w π h (s) = P π [s h = s] the visitation probability, and W ⋆ h (s) = sup π w π h (s). Then, we can recursively defineδ π ℓ,h+1 = P h (π h -πℓ,h )w π ℓ,h + P h π h δ π ℓ,h . (C.1)Similarly, δ π ℓ,h+1 = M h P h (π h -πℓ,h ) w π ℓ,h + P h π h δ π ℓ,h . (C.2) And δ π ℓ,h+1 = M h P ℓ,h (π h -πℓ,h ) w π ℓ,h + P ℓ,h π h δ π ℓ,h . (C.Set ϵ ℓ ← 2 -ℓ , ϵ ℓ unif ← ϵ ℓ 64S 3/2 H 2 , K ℓ unif ← ϵ -2/3 ℓ ϵ ℓ unif 4:S keep ℓ = PRUNE(ϵ ℓ unif , δ/3ℓ 2 ) (Algorithm 5) // Prune states that are hard to reach 5:Use { P ℓ-1,h } H h=1 to compute U ℓ-1,h (π, π ′ ) for all (π, π ′ ) ∈ Π ℓ // Compute new reference policy 6: Choose πℓ ← min π∈Π ℓ max π∈Π ℓ H h=1 U ℓ-1,h (π, π) 7:Collect the following number of episodes from πℓ and store in datasetD ref ℓ nℓ = max π∈Π ℓ c • H U ℓ-1 (π, πℓ ) + H 4 S 3/2 √ A log SAHℓ 2 δ • ϵ 1/3 ℓ + S 2 H 4 ϵ ℓ unif ϵ 2 ℓ • log 60Hℓ 2 |Π ℓ | δ 8:Compute { w π ℓ,h (s)} H h=1 using empirical state visitation frequencies in D ref Define M ℓ,h ∈ R SA×SA as M ℓ,h ← diag(α s1,a1 . . . α s S ,a A ), where α s,a = 1(s ∈ S keep ℓ,h ).12:EQUATIONUseD ED ℓ,h to compute P ℓ,h (s ′ |s, a) ← N ℓ,h (s ′ ,s,a) N ℓ,h (s,a) if N ℓ,h (s, a) > 0, unif(S) otherwise, and r ℓ,h (s, a) = 1 N ℓ,h (s,a) (s ′ ,a ′ ,r ′ ,s ′′ )∈D ED ℓ,h r ′ • I{(s, a) = (s ′ , a ′ )} if N ℓ,h (s, a) > 0, 0 otherwise 16: Compute δ π ℓ,h+1 ← M ℓ,h ( P ℓ,h (π h -πℓ,h ) w π ℓ,h + P ℓ,h π h δ π ℓ,h ) 17:end for18: Compute D πℓ (π) ← h ⟨ r ℓ,h , π h δ ℓ,h ⟩ + h ⟨ r ℓ,h , (π h -πℓ,h ) w π ℓ,h ⟩ 19: Update Π ℓ+1 = Π ℓ \{π ∈ Π ℓ : max π ′ D πℓ (π ′ ) -D πℓ (π) > 8ϵ ℓ } 20:if |Π ℓ+1 | = 1 then return π ∈ Π ℓ+1 21: end for 22: return any π ∈ Π ℓ+1Value functions. Note that we can express the value function as:V π h = H k=h   k j=h+1 P j π j   ⊤ π ⊤ k r kOn the "pruned" MDP, defineEQUATIONV ℓ,h := H k=h   k j=h+1 M ℓ,j+1 P j π j   ⊤ π ⊤ k r ℓ,k . Reward difference term. Define U h (π, π ′ ) := E π ′ [(Q π h (s h , π h (s)) -Q π h (s h , π ′ h (s))) 2 ] and U (π, π ′ ) := H h=1 U h (π, π ′ ). Additionally, define U ℓ,h (π, π ′ ) := E π ′ ,ℓ [( Q π ℓ,h (s h , π h (s)) -Q π ℓ,h (s h , π ′ h (s))) 2 ]where E π ′ ,ℓ denotes the expectation induced playing π ′ on the MDP with transitions P ℓ , and Q π ℓ,h denotes the Q-function for policy π on this same MDP. Let U ℓ (π, π ′ ) :=H h=1 U ℓ,h (π, π ′ ).Lemma 7. Let D = {(s 1 , a 1 , s ′ 1 ), . . . (s T , a T , s ′ T )} be any dataset of transitions collected from level h. Let P ∈ R S×SA denote the empirical transition matrix with [ P ] s ′ ,sa = N (s ′ |s,a)N (s,a) if N (s, a) > 0, and 0 otherwise, for N (s ′ | s, a) = t I{(s t , a t , s ′ t ) = (s, a, s ′ )} and N (s, a) = t I{(s t , a t ) = (s, a)}. Consider any v ∈ [0, 1] S and u ∈ R SA and assume that N (s, a) > λ > 0 for all (s, a) ∈ support(u). Then, for P the true transition matrix, we have that with probability at least 1 -δ:v ⊤ (P -P )u ≤ s,a [u] 2 s,a N (s, a) • 2 log 1 δ + 4 3 √ λ log 1 δ .Proof. First writev ⊤ (P -P )u = s ′ s,a v s ′ P (s ′ | s, a) - N (s ′ | s, a) N (s, a) u sa = t s ′ v s ′ (P (s ′ | s t , a t ) -I{s ′ t = s ′ }) u stat N (s t , a t )where the second equality follows from some simple manipulations. Note that, for any t, we haveE v s ′ (P (s ′ | s t , a t ) -I{s ′ t = s ′ }) u stat N (s t , a t )| s t , a t = 0 and can bounds ′ v s ′ (P (s ′ | s t , a t ) -I{s ′ t = s ′ }) u stat N (s t , a t ) ≤ 2u stat N (s t , a t ) ≤ 2 √ λ • u stat N (s t , a t ) ≤ 2 √ λ • s,a u 2 sa N (s, a)where we have used the fact that N (s, a) ≥ λ for (s, a) ∈ support(u), and since v has entries in [0, 1] and P (s ′ | s t , a t ) andI{s ′ t = s ′ } are valid distributions, so s ′ v s ′ (P (s ′ | s t , a t ) -I{s ′ t = s ′ }) ∈ [-1, 1]. Furthermore, we have that E s ′ t   s ′ v s ′ (P (s ′ | s t , a t ) -I{s ′ t = s ′ }) u stat N (s t , a t ) 2   ≤ E s ′ t u stat N (s t , a t ) 2 = u stat N (s t , a t ) 2where we have again used thats ′ v s ′ (P (s ′ | s t , a t ) -I{s ′ t = s ′ }) ∈ [-1, 1]. By Bernstein's inequality, we therefore have that with probability at least 1 -δ:v ⊤ (P -P )u ≤ 2 t u stat N (s t , a t ) 2 • log 2 δ + 4 3 √ λ • t u 2 stat N (s t , a t ) • log 2 δ = 2 log 2 δ + 4 3 √ λ log 2 δ • s,a u 2 sa N (s, a) .Lemma 8. Let D = {(s 1 , a 1 , r 1 ), . . . (s T , a T , r T )} be any dataset of state-action-reward tuples collected from level h. Let r ∈ R SA denote the empirical reward estimation with [ r] sa = 1 N (s,a) • T t=1 r t • I{(s t , a t ) = (s, a)} if N (s, a) > 0, and 0 otherwise, for N (s, a) = t I{(s t , a t ) = (s, a)}. Consider any u ∈ R SA and assume that N (s, a) > λ > 0 for all (s, a) ∈ support(u). Then, for r the true reward mean, we have that with probability at least 1 -δ:(r -r) ⊤ u ≤ s,a [u] 2 s,a N (s, a) • 2 log 1 δ + 4 3 √ λ log 1 δ .Proof. First write(r -r) ⊤ u = t (r(s t , a t ) -r t ) u stat N (s t , a t ) .Note that, for any t, we haveE (r(s t , a t ) -r t ) u stat N (s t , a t ) | s t , a t = 0 and can bound (r(s t , a t ) -r t ) u stat N (s t , a t ) ≤ u stat N (s t , a t ) ≤ 1 √ λ • u stat N (s t , a t ) ≤ 1 √ λ • s,a u 2 sa N (s, a)where we have used the fact that N (s, a) ≥ λ for (s, a) ∈ support(u), and since we assume our rewards are in [0, 1]. Furthermore, we have thatE rt (r(s t , a t ) -r t ) u stat N (s t , a t ) 2 ≤ E rt u stat N (s t , a t ) 2 = u stat N (s t , a t ) 2 .By Bernstein's inequality, we therefore have that with probability at least 1 -δ:(r -r) ⊤ u ≤ 2 t u stat N (s t , a t ) 2 • log 2 δ + 4 3 √ λ • t u 2 stat N (s t , a t ) • log 2 δ = 2 log 2 δ + 4 3 √ λ log 2 δ • s,a u 2 sa N (s, a) .Lemma 9. Let u ∈ R S be any vector such that ∀s, |u s | ≤ M . Then, for any (ℓ, h), the following holds with probability (1 -δ):E s∼w π ℓ,h [u s ] -E s∼ w π ℓ,h [u s ] ≤ 2E s∼w π ℓ,h [u 2 s ] nℓ log 2 δ + 2M 3n ℓ log 2 δ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 s . Hence, the result follows directly from Bernstein's inequality since we know |u s | ≤ 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 a ⊤ i the ith row of A, and b j the jth column of B:j a ⊤ i b j = k j a ik b jk = k a ik ( j b jk ).Now note that j b jk is the sum across the kth row of B, so this is ≤ 1 by assumption. Furthermore, k a ik ≤ 1 for the same reason. Thus, the ith row of AB sums to a value ≤ 1. Furthermore, it is easy to see a ⊤ i b j ≤ 1 for each j. Thus, AB has values in [0, 1] and rows that sum to a value ≤ 1.Lemma 11. We have that ∥Π j h=i M h+1 P h π h ∥ 2 , ∥Π j h=i P h π h ∥ 2 ≤ √ S for any i, j, h.Proof. By definition P h π h is a transition matrix-each row has values in [0, 1] and sums to 1-and M h+1 is diagonal with diagonal elements either 0 or 1. Thus, each matrix M h P h π h has values in [0, 1] and rows that sum to a value ≤ 1, so Lemma 10 implies that Π j h=i M h+1 P h π h does as well. Denote A := ∥Π j h=i M h P h π h ∥ 2 . We can then bound∥Π j h=i M h+1 P h π h ∥ 2 2 = ∥A∥ 2 2 ≤ ∥A∥ 2 F = i j A 2 ij ≤ i 1 ≤ S,which proves the result. The bound on ∥Π j h=i P h π h ∥ 2 follows from the same argument.Lemma 12. We haveδ π ℓ,h+1 -δ π ℓ,h+1 = h-2 i=0   h j=h-i+1 M ℓ,j+1 P j π j   (P h-i -P ℓ,h-i )M ℓ,h-i (π h-i -πℓ,h-i ) w π ℓ,h-i + π h-i δ π ℓ,h-i .Proof. This follows immediately from the definition of δ π ℓ,h+1 , δ π ℓ,h+1 , and simple manipulations.C. , then W ⋆ h (s) ≤ 32ϵ ℓ unif . Then P(E ℓ prune ) ≥ 1 -δ 3ℓ 2 .Proof. From Lemma 38, this event follows directly with probability (1 -δ 3ℓ 2 ).Lemma 14. Let E ℓ,h exp be the event for which:1. The exploration procedure in Algorithm 3 will produce D ED ℓ,h such thatmax π∈Π ℓ ∥M ℓ,h ((π h -πℓ,h ) w π ℓ,h + π h δ π ℓ,h )∥ 2 Λ -1 ℓ,h ≤ ϵ ℓ exp for Λ ℓ,h = (s,a)∈D ED ℓ,he sa e ⊤ sa , (C.4)and will collect at mostC • inf πexp max π∈Π ℓ ∥M ℓ,h ((π h -πℓ,h ) w π ℓ,h + π h δ π ℓ,h )∥ 2 Λ h (πexp) -1 ϵ ℓ exp + C ℓ fw (ϵ ℓ exp ) 4/5 + C ℓ fw ϵ ℓ unif + log(C ℓ fw ) • K ℓ unif episodes. 2. For each s ∈ S keep ℓ , we have that (s ′ ,a ′ )∈D ED ℓ,h I{(s ′ , a ′ ) = (s, a)} ≥ K ℓ unif ϵ ℓ unif SAfor any a ∈ A.Above, C is a universal constant and C ℓ fw = poly(S, A, H, log ℓ/δ, log 1/ϵ, log |Π|). ThenP[(E ℓ,h exp ) c ∩ E ℓ prune ∩ Ēℓ est ∩ (∩ h ′ ≤h-1 E ℓ,h ′ est ) ∩ (∩ h ′ ≤h-1 E ℓ,h ′ exp )] ≤ δ 6Hℓ 2 .Proof. Since the event E ℓ prune holds, for each s ∈ S keep ℓ we have W ⋆ h (s) ≥ ϵ ℓ unif . Now, observe that, for s ∈ S keep ℓ and any a:|[(π h -πℓ,h ′ ) w π ℓ,h + π h δ π ℓ,h ] (s,a) | ≤ [ w π ℓ,h ] s + |[ δ π ℓ,h ] s | ≤ [w π ℓ,h ] s + |[δ π ℓ,h ] s | + |[ w π ℓ,h -w π ℓ,h ] (s) | + |[δ π ℓ,h ] s -|[ δ π ℓ,h ] s ||. By construction, we have [w π ℓ,h ] s , |[δ π ℓ,h ] s | ≤ W ⋆ h (s). By Lemma 19, on Ēℓ est , we can bound |[ w π ℓ,h - w π ℓ,h ] (s) | ≤ 8Sϵ 5/3 ℓ . By Lemma 18, on E ℓ prune ∩ (∩ h ′ ≤h-1 E ℓ,h ′ est ) ∩ (∩ h ′ ≤h-1 E ℓ,h ′ exp ), we can bound |[δ π ℓ,h ] s -|[ δ π ℓ,h ] s || ≤ SHβ ℓ ϵ ℓ exp + SH( 8ϵ 5/3 ℓ + 32ϵ ℓ unif ). Altogether then, we have |[(π h -πℓ,h ′ ) w π ℓ,h + π h δ π ℓ,h ] (s,a) | ≤ 2W ⋆ h (s) + SHβ ℓ ϵ ℓ exp + SH( 8ϵ 5/3 ℓ + 32ϵ ℓ unif ) + 8Sϵ 5/3ℓ . By our choice of ϵ ℓ exp and ϵ ℓ unif , we can bound all of this as≤ C ϕ • (W ⋆ h (s) + K ℓ unif ϵ ℓ unif ϵ ℓ exp ) for C ϕ = cSHβ ℓ. This is the condition required by Theorem 2, so the result follows from Theorem 2.est be the event at epoch ℓ for step h on which: (1) For all π ∈ Π ℓ , h ′ ≤ h:π ⊤ h r ℓ,h , h i=h ′ +1 M ℓ,i+1 P i π i (P h ′ -P ℓ,h ′ )M ℓ,h ′ (π h ′ -πℓ,h ′ ) w π ℓ,h ′ + π h ′ δ π ℓ,h ′ ≤ β ℓ s,a M ℓ,h ′ (π h ′ -πℓ,h ′ ) w π ℓ,h ′ + π h ′ δ π ℓ,h ′ 2 (s,a)N ℓ,h ′ (s, a) .(2) For all canonical vectors e s ′ in R S , π ∈ Π ℓ , andh ′ ≤ h, e s ′ , h i=h ′ +1 M ℓ,i+1 P i π i (P h ′ -P ℓ,h ′ )M ℓ,h ′ (π h ′ -πℓ,h ′ ) w π ℓ,h ′ + π h ′ δ π ℓ,h ′ ≤ β ℓ s,a [M ℓ,h ′ ((π h ′ -πℓ,h ′ ) w π ℓ,h ′ + π h ′ δ π ℓ,h ′ )] 2 s,aN ℓ,h ′ (s, a) .(3) For each (s, a), we haves ′ | P ℓ,h (s ′ | s, a) -P h (s ′ | s, a)| ≤ S log 48S 2 AHℓ 2 δ N ℓ,h (s, a) . (4) For each π ∈ Π ℓ , |⟨ r ℓ,h -r ℓ,h , π h δ π ℓ,h + (π h -πℓ,h ) w π ℓ,h ⟩| ≤ β ℓ s,a M ℓ,h (π h -πℓ,h ′ ) w π ℓ,h + π h δ π ℓ,h 2 (s,a)N ℓ,h (s, a) .Then P[(E ℓ,h est ) c ∩ E ℓ prune ∩ (∩ h ′ ≤h E ℓ,h exp )] ≤ δ 6Hℓ 2 .Proof. We prove each of the events sequentially.Proof of Event (1) . Consider any fixed choice of (π, h ′ ). By Lemma 10 and since our rewards are in [0, 1], we have thath i=h ′ +1 M ℓ,i+1 P i π i ⊤ π ⊤ h r ℓ,h is a vector in [0, 1]. Let v ← h i=h ′ +1 M ℓ,i+1 P i π i ⊤ π ⊤ h r ℓ,h and u ← M ℓ,h ′ (π h ′ -πℓ,h ′ ) w π ℓ,h ′ +π h ′ δ π ℓ,h ′ .Note that by construction we have that u sa = 0 for s ̸ ∈ S keep ℓ,h ′ , and so on E ℓ,h ′ exp , we have N ℓ,h ′ (s, a) ≥K ℓ unif ϵ ℓ unif 2SAfor all (s, a) ∈ support(u). On E ℓ prune ∩ E ℓ,h ′ exp , we can then apply Lemma 7 with u and v as defined above to get that the bound fails with probability at most δ 30H 2 ℓ 2 |Π ℓ | . Union bounding over h ′ and π we get that the stated result fails with probability at most δ 30Hℓ 2 .Proof of Event (2) .Choose v = e ⊤ i h i=h ′ +1 M ℓ,i P i π i and u = M h ′ ,ℓ (π h ′ -πℓ,h ′ )w π ℓ,h ′ + π h ′ δ π ℓ,h ′ .Note that by construction of w π ℓ,h ′ and δ π ℓ,h ′ we have that u sa = 0 for s ̸ ∈ S keep ℓ,h ′ , and so on E ℓ,h ′ exp , we have N ℓ,h ′ (s, a) ≥K ℓ unif ϵ ℓ unif 2SAfor all (s, a) ∈ support(u). Furthermore, we have that v ∈ [0, 1] S by Lemma 10. Then, the event follows by invoking Lemma 7.. By Hoeffding's inequality, for any (s, a), we have, with probability at least 1 -δ 24S 2 AHℓ 2 : | P ℓ,h (s ′ | s, a) -P h (s ′ | s, a)| ≤ log 24S 2 AHℓ 2 δ N ℓ,h (s, a) .Thus, we have that with probability at least 1 -δ 24SAHℓ 2 : s ′ | P ℓ,h (s ′ | s, a) -P h (s ′ | s, a)| ≤ S log 24S 2 AHℓ 2 δ N ℓ,h (s, a) .Union bounding over all (s, a), we obtain that this holds with probability at least 1 -δ 24Hℓ 2 .⟨ r ℓ,h -r ℓ,h , π h δ π ℓ,h + (π h -πℓ,h ) w π ℓ,h ⟩ = ⟨ r ℓ,h - r ℓ,h , M ℓ,h (π h δ π ℓ,h + (π h -πℓ,h ) w π ℓ,h )⟩.The result then follows on E ℓ prune by a direct application of Lemma 8.The final result then holds by a union bound.est denote the event that at epoch ℓ and for each h:(1) For all π ∈ Π ℓ and h ∈ [H], we have⟨P ⊤ h M ℓ,h+1 V ℓ,h+1 + r h , (π h -πℓ,h )(w π ℓ,h -w π ℓ,h )⟩ ≤ 2H 3n ℓ log 60Hℓ 2 |Π ℓ | δ + 2E s∼w πℓ ℓ,h [⟨P ⊤ h M ℓ,h+1 V π ℓ,h+1 + r h , (π h -πℓ,h )e s ⟩ 2 ] nℓ • log 60Hℓ 2 |Π ℓ | δ .(2) For all canonical vectors e s ∈ R S ,|⟨e s , w π ℓ,h -w π ℓ,h ⟩| ≤ 2 log 30Hℓ 2 S δ nℓ + 2 log 30Hℓ 2 S δ nℓ . Then P[( Ēℓ est ) c ] ≤ δ 15ℓ 2 .Proof. Proof of Event (1) .Consider a fixed choice of π, and let u π s = P ⊤ h V π ℓ,h+1 + r h , (π h -πℓ,h )e s , and note that |u π s | ≤ H for all s. Lemma 9 then gives that with probability at least 1 -δ 30Hℓ 2 |Π ℓ | we have ⟨P ⊤ h M ℓ,h+1 V ℓ,h+1 + r h , (π h -πℓ,h )(w π ℓ,h -w π ℓ,h )⟩ ≤ 2E s∼w πℓ ℓ,h [⟨P ⊤ h M ℓ,h+1 V π ℓ,h+1 + r h , (π h -πℓ,h )e s ⟩ 2 ] nℓ • log 60Hℓ 2 |Π ℓ | δ + 2H 3n ℓ log 60Hℓ 2 |Π ℓ | δ .Proof of Event (2) . For a fixed choice of s ∈ [S], the event follows from Lemma 9 with u = e s with probability 1 -δ, where δ = δ 30Hℓ 2 S . Once we take the union bound over all s ∈ [S], then the event follows with probability 1 -δ 30Hℓ 2 . The result then holds by union bounding over each of these for all h. Lemma 17. On E ℓ prune , for all h and π we haveδ π ℓ,h+1 -δ π ℓ,h+1 = h-2 i=0   h j=h-i+1 M ℓ,j+1 P j π j   M ℓ,h-i+1 P h-i (π h-i -πh-i )(w πℓ ℓ,h-i -w πℓ ℓ,h-i ) + ∆ π ℓ,h+1for some ∆ π ℓ,h ∈ R S with ∥∆ π ℓ,h ∥ 2 ≤ 32SHϵ ℓ unif . Furthermore, for any π and any i, k satisfying0 ≤ i ≤ k ≤ H, we have   k j=i M ℓ,j+1 P j π j - k j=i P j π j   w π i 2 ≤ 32SHϵ ℓ unif .Proof. By definition, we have thatEQUATIONs), and similarly[P h-i π h-i δ π ℓ,h-i ] s ≤ W ⋆ h-i+1 (s). On the event E ℓ prune , we have that if [M ℓ,h-i+1 ] s,s = 0, then W ⋆ h-i+1 (s) ≤ 32ϵ ℓ unif . It follows from this that every non-zero element in (I -M ℓ,h-i+1 )P h-i (π h-i -πh-i )w πℓ ℓ,h-i and (I -M ℓ,h-i+1 )P h-i π h-i δ π ℓ,h-i is bounded by 32ϵ ℓ unif , so: ∥(I -M ℓ,h-i+1 )P h-i (π h-i -πh-i )w πℓ ℓ,h-i ∥ 2 ≤ 32 √ Sϵ ℓ unif and ∥(I -M ℓ,h-i+1 )P h-i π h-i δ π ℓ,h-i ∥ 2 ≤ 32 √ Sϵ ℓ unif .∥ h j=h-i+1 M ℓ,j+1 P j π j ∥ 2 ≤ √ S.Combining these gives the result.We now prove the second part of the result. Denote A j := M ℓ,j+1 P j π j and B j := P j π j . Thenk j=i M ℓ,j+1 P j π j - k j=i P j π j = k j=i A j - k j=i B j = A k   k-1 j=i A j - k-1 j=i B j   + (A k -B k ) k-1 j=i B j . . . = k s=i   k j=s+1 A j   (A s -B s )   s-1 j ′ =i B j ′   .By Lemma 11 we have∥ k j=s+1 A j ∥ 2 ≤ √ S. Furthermore, note that s-1 j ′ =i B j ′ w π i = w π s . So it follows that ( k j=i M ℓ,j+1 P j π j - k j=i P j π j )w π i 2 ≤ k s=i √ S∥(A s -B s )w π s ∥ 2 .By the same argument as above, we can bound∥(A s -B s )w π s ∥ 2 ≤ 32 √ Sϵ ℓ unif .Lemma 18. On the eventE ℓ prune ∩ (∩ h ′ ≤h E ℓ,h ′ est ) ∩ (∩ h ′ ≤h E ℓ,h ′ exp ), we have, for all π ∈ Π ℓ : ∥ δ π ℓ,h+1 -δ π ℓ,h+1 ∥ 2 ≤ SHβ ℓ ϵ ℓ exp + SH( 8ϵ 5/3 ℓ + 32ϵ ℓ unif ).Proof. We can write∥ δ π ℓ,h+1 -δ π ℓ,h+1 ∥ 2 ≤ ∥ δ π ℓ,h+1 -δ π ℓ,h+1 ∥ 2 + ∥ δ π ℓ,h+1 -δ π ℓ,h+1 ∥ 2 .From Lemma 12 we haveδ π ℓ,h+1 -δ π ℓ,h+1 = h-2 i=0   h j=h-i+1 M ℓ,j+1 P j π j   (P h-i -P ℓ,h-i )M ℓ,h-i (π h-i -πℓ,h-i ) w π ℓ,h-i + π h-i δ π ℓ,h-i .From Event (2) of E ℓ,h est in Lemma 15, we have that for all canonical vectors e s and π ∈ Π ℓ :e s ,   h j=h-i+1 M ℓ,j+1 P j π j   (P h-i -P ℓ,h-i )M ℓ,h-i (π h-i -πh-i ) w π ℓ,h-i + π h-i δ π ℓ,h-i ] ≤ β ℓ s,a [M ℓ,h-i ((π h-i -πℓ,h-i ) w π ℓ,h-i + π h-i δ π ℓ,h-i )] 2 s,a N ℓ,h-i (s, a) .Now, summing over the bound above for all canonical vectors, and applying this for each i, it follows that∥ δ π ℓ,h+1 -δ π ℓ,h+1 ∥ 2 2 ≤ Sβ 2 ℓ h h ′ =1 s,a [M ℓ,h ′ ((π h ′ -πℓ,h ′ ) w π ℓ,h ′ + π h ′ δ π ℓ,h ′ )] 2 s,a N ℓ,h ′ (s, a) ≤ SHβ ℓ ϵ ℓ expwhere the last inequality holds on ∩ h ′ ≤h E ℓ,h ′ exp .We now turn to bounding ∥ δ π ℓ,h+1 -δ π ℓ,h+1 ∥ 2 . By Lemma 17 we haveδ π ℓ,h+1 -δ π ℓ,h+1 = h-2 i=0   h j=h-i+1 M ℓ,j+1 P j π j   M ℓ,h-i+1 P h-i (π h-i -πh-i )(w πℓ ℓ,h-i -w πℓ ℓ,h-i ) + ∆ π ℓ,h+1for some∆ π ℓ,h ∈ R S with ∥∆ π ℓ,h ∥ 2 ≤ 32SHϵ ℓ unif . Furthermore, on E ℓ,h-i est, by Lemma 19 we can bound∥w πℓ ℓ,h-i -w πℓ ℓ,h-i ∥ 2 ≤ 8Sϵ 5/3 ℓ .Combining this with Lemma 11 gives the result.Lemma 19. On event Ēℓ est we have:∥ w π ℓ,h -w π ℓ,h ∥ 2 2 ≤ 8Sϵ 5/3 ℓ .Proof. From Event (2) of Lemma 16, we have that for all canonical vectors e i ∈ R S :|⟨e i , w π ℓ,h -w π ℓ,h ⟩| ≤ 2 log 30Hℓ 2 S δ nℓ + 2 log 30Hℓ 2 S δ nℓ .Then, combining these bounds together for all s:∥ w π ℓ,h -w π ℓ,h ∥ 2 2 ≤ 4S log 30Hℓ 2 S δ nℓ + 4S log 2 30Hℓ 2 S δ n2 ℓ ≤ 4Sϵ 5/3 ℓ + 4Sϵ 10/3 ℓ ≤ 8Sϵ 5/3 ℓ ,where the last inequality follows from our choice of nℓ in Algorithm 2.Lemma 20. Let E good := (∩ ∞ ℓ=1 E ℓ prune ) ∩ (∩ ∞ ℓ=1 Ēℓ est ) ∩ (∩ ∞ ℓ=1 ∩ h∈[H] E ℓ,h est ) ∩ (∩ ∞ ℓ=1 ∩ h∈[H] E ℓ,h exp ). Then P[E good ] ≥ 1 -2δ.Proof. By a union bound and basic set manipulations, we have:P[E c good ] ≤ ∞ ℓ=1 P[(E ℓ prune ) c ] + ∞ ℓ=1 P[( Ēℓ est ) c ] + ∞ ℓ=1 H h=1 P[(E ℓ,h exp ) c ∩ E ℓ prune ∩ Ēℓ est ∩ (∩ h ′ ≤h-1 E ℓ,h ′ est ) ∩ (∩ h ′ ≤h-1 E ℓ,h ′ exp )] + ∞ ℓ=1 H h=1 P[(E ℓ,h est ) c ∩ E ℓ prune ∩ (∩ h ′ ≤h E ℓ,h exp )].By Lemma 13, we have P[(E ℓ prune ) c ] ≤ δ/3ℓ [(E ℓ,h exp ) c ∩ E ℓ prune ∩ Ēℓ est ∩ (∩ h ′ ≤h-1 E ℓ,h ′ est ) ∩ (∩ h ′ ≤h-1 E ℓ,h ′ exp )] ≤ δ 6Hℓ 2 . By Lemma 15 we have P[(E ℓ,h est ) c ∩ E ℓ prune ∩ (∩ h ′ ≤h E ℓ,h exp )] ≤ δ 6Hℓ 2 .Putting this together we can bound the above as≤ ∞ ℓ=1 ( δ 3ℓ 2 + δ 15ℓ 2 ) + ∞ ℓ=1 H h=1 2δ 6Hℓ 2 ≤ 2δ.Lemma 21. On E good we have that:H h=1 ⟨ r ℓ,h , π h ( δ π ℓ,h -δ π ℓ,h )⟩ ≤ ϵ ℓ and H h=1 |⟨ r ℓ,h -r ℓ,h , π h δ π ℓ,h +(π h -πℓ,h ) w π ℓ,h ⟩| ≤ ϵ ℓ . (C.5)Proof. From Lemma 12 we have:δ π ℓ,h+1 -δ π ℓ,h+1 = h-2 i=0   h j=h-i+1 M ℓ,j+1 P j π j   (P h-i -P ℓ,h-i )M ℓ,h-i (π h-i -πℓ,h-i ) w π ℓ,h-i + π h-i δ π ℓ,h-i .A sufficient condition for (C.5) is that, for each i:π ⊤ h r ℓ,h ,   h j=h-i+1 M ℓ,j+1 P j π j   (P h-i -P ℓ,h-i ) M ℓ,h-i (π h-i -πℓ,h-i ) w π ℓ,h-i + π h-i δ π ℓ,h-i ≤ ϵ ℓ .On E good , and in particular E ℓ,h est (Lemma 15), we can bound the left-hand side of this as:≤ β ℓ s,a M ℓ,h-i (π h-i -πℓ,h-i ) w π ℓ,h-i + π h-i δ π ℓ,h-i 2 (s,a) N ℓ,h-i (s, a) ≤ β ℓ ϵ 2 ℓ /H 4 β 2 ℓ ≤ ϵ ℓ /H 2where the second inequality holds on E good (in particular E ℓ,h-i exp ). This proves the first inequality.On E ℓ,h est we can also bound|⟨ r ℓ,h -r ℓ,h , π h δ π ℓ,h + (π h -πℓ,h ) w π ℓ,h ⟩| ≤ β ℓ s,a M ℓ,h (π h -πℓ,h ′ ) w π ℓ,h + π h δ π ℓ,h 2 (s,a) N ℓ,h (s, a) ≤ ϵ ℓ /H 2 .This proves the second inequality.Lemma 22. On event E good , for any timestep h, policies π, π ′ , and action a, we have:E π ′ [| Q π ℓ,h (s h , a) -Q π h (s h , a)|] ≤ H 2 S 3/2 A log 24S 2 AHℓ 2 δ • ϵ 1/3 ℓ + 64H 2 Sϵ ℓ unif . (C.6)Proof. By Lemma E.15 of [10] , we have that:Q π ℓ,h (s, a) -Q π h (s, a) = E π H h ′ =h s ′ ( P ℓ,h ′ (s ′ | s h ′ , a h ′ ) -P h (s ′ | s h ′ , a h ′ )) V π ℓ,h ′ +1 (s h ′ ) | s h = s, a h = a .On E good , in particular E ℓ,h ′ est , we can bound, for s ∈ S keep ℓ,h ′ and any a:s ′ ( P ℓ,h ′ (s ′ | s, a) -P h (s ′ | s, a)) V π ℓ,h ′ +1 (s ′ ) ≤ SH log 24S 2 AHℓ 2 δ N ℓ,h ′ (s, a) ≤ SH SA log 24S 2 AHℓ 2 δ K ℓ unif ϵ ℓ unifand where the last inequality follows on E ℓ,h ′ exp . By our choice of K ℓ unif and ϵ ℓ unif , we can further bound this as≤ SH SA log 24S 2 AHℓ 2 δ • ϵ 1/3 ℓ . For s ̸ ∈ S keep ℓ,h ′ , we can bound | s ′ ( P ℓ,h ′ (s ′ | s, a) -P h (s ′ | s, a)) V π ℓ,h ′ (s h ′ )| ≤ 2H.We therefore have thatE π ′ [| Q π ℓ,h (s h , a) -Q π h (s h , a)|] ≤ E π ′ E π H h ′ =h SH SA log 24S 2 AHℓ 2 δ • ϵ 1/3 ℓ • I{s h ′ ∈ S keep ℓ,h ′ } + 2HI{s h ′ ̸ ∈ S keep ℓ,h ′ } | s h = s, a h = a = H h ′ =h E π SH SA log 24S 2 AHℓ 2 δ • ϵ 1/3 ℓ • I{s h ′ ∈ S keep ℓ,h ′ } + 2HI{s h ′ ̸ ∈ S keep ℓ,h ′ } ≤ H 2 S 3/2 A log 24S 2 AHℓ 2 δ • ϵ 1/3 ℓ + 64H 2 Sϵ ℓ unif ,where the last inequality follows by definition of S keep ℓ,h ′ , and π ′ is the policy which plays πℓ for the first h steps and then plays π. This proves the result.Lemma 23. On event E good , for all h and any π and π ′ , we have that| U ℓ,h (π, π ′ ) -U h (π, π ′ )| ≤ 9H 3 S 3/2 A log 24S 2 AHℓ 2 δ • ϵ 1/3 ℓ + 576H 3 Sϵ ℓ unif .Proof. We haveU ℓ,h (π, π ′ ) = E π ′ ,ℓ Q π ℓ,h (s h , π h (s h )) -Q π ℓ,h (s h , π ′ h (s h ))2where E π ′ ,ℓ denotes the expectation induced playing policy π ′ on the MDP with transition P ℓ . We can think of this as simply a value function for policy π on the reward řh (s, a) =Q π ℓ,h (s, π h (s)) -Q π ℓ,h (s, a) 2. Let V denote the value function on this reward on P ℓ , and note that Vh (s) ∈ [0, H 2 ] for all (s, h). By Lemma E.15 of [10] , we then have thatU ℓ,h (π, π ′ ) -E π ′ Q π ℓ,h (s h , π h (s h )) -Q π ℓ,h (s h , π ′ h (s h )) 2 = E π ′ H h=1 s ′ ( P ℓ,h (s ′ | s h , a h ) -P h (s ′ | s h , a h )) Vh+1 (s ′ ) ≤ H 2 H h=1 E π ′ s ′ | P ℓ,h (s ′ | s h , a h ) -P h (s ′ | s h , a h )| .′ | P ℓ,h (s ′ | s h , a h ) -P h (s ′ | s h , a h )| ≤ 2. Furthermore, on E good we also have s ′ | P ℓ,h (s ′ | s h , a h ) -P h (s ′ | s h , a h )| ≤ S log 24S 2 AHℓ 2 δ N ℓ,h (s h ,a h ). We can therefore bound the above as≤ H 2 H h=1 E π ′   min    2, S log 24S 2 AHℓ 2 δ N ℓ,h (s h , a h )      ≤ H 2 H h=1 E π ′   2 • I{s h ̸ ∈ S keep ℓ,h } + S log 24S 2 AHℓ 2 δ N ℓ,h (s h , a h ) • I{s h ∈ S keep ℓ,h }   . For s ∈ S keep ℓ,h , on E good we have N ℓ,h (s h , a h ) ≥ K ℓ unif ϵ ℓ unif SA = ϵ 2/3ℓ /SA, and we also have fors h ̸ ∈ S keep ℓ,h that W ⋆ h (s) ≤ 32ϵ ℓ unif .Putting this together we can bound the above as≤ H 2 H h=1 64Sϵ ℓ unif + S SA log 24S 2 AHℓ 2 δ • ϵ 1/3 ℓ ≤ 64SH 3 ϵ ℓ unif + H 3 S 3/2 A log 24S 2 AHℓ 2 δ • ϵ 1/3 ℓ .Furthermore,E π ′ Q π ℓ,h (s, π h (s)) -Q π ℓ,h (s, π ′ h (s)) 2 -E π ′ (Q π h (s, π h (s)) -Q π h (s, π ′ h (s))) 2 = E π ′ Q π ℓ,h (s, π h (s)) -Q π h (s, π h (s)) + Q π h (s, π ′ h (s)) -Q π ℓ,h (s, π ′ h (s)) 2 + E π ′ Q π ℓ,h (s, π h (s)) -Q π h (s, π h (s)) + Q π h (s, π ′ h (s)) -Q π ℓ,h (s, π ′ h (s)) (Q π h (s, π h (s)) -Q π h (s, π ′ h (s))) ≤ 4HE π ′ [| Q π ℓ,h (s, π h (s)) -Q π h (s, π h (s))|] + 4HE π ′ [|Q π h (s, π ′ h (s)) -Q π ℓ,h (s, π ′ h (s))|] ≤ 8H 3 S 3/2 A log 24S 2 AHℓ 2 δ • ϵ 1/3 ℓ + 512H 3 Sϵ ℓ unifwhere the final inequality follows from Lemma 22. Combining this with the above bound completes the argument.Lemma 24. On event E good , for all epochs ℓ, we have thatH h=1 ⟨ r ℓ,h , π h (δ π ℓ,h -δ π ℓ,h )⟩ + ⟨ r ℓ,h , (π h -πℓ,h )(w π ℓ,h -w π ℓ,h )⟩ ≤ ϵ ℓ . (C.7)Proof. We first bound |⟨M ℓ,h r h , π h (δ π ℓ,h -δ π ℓ,h )⟩|. By Lemma 17 we have thatδ π ℓ,h+1 -δ π ℓ,h+1 = h-2 i=0   h j=h-i+1 M ℓ,j+1 P j π j   M ℓ,h-i+1 P h-i (π h-i -πℓ,h-i )(w π h-i -w π ℓ,h-i ) + ∆ π ℓ,h+1for some∆ π ℓ,h ∈ R S with ∥∆ π ℓ,h ∥ 2 ≤ 32SHϵ ℓ unif . Furthermore, note that H h=1 h-2 i=0 r ℓ,h , π h   h j=h-i+1 M ℓ,j+1 P j π j   M ℓ,h-i+1 P h-i (π h-i -πℓ,h-i )(w π h-i -w π ℓ,h-i ) = H h=1 h k=2 r ℓ,h , π h   h j=k+1 M ℓ,j+1 P j π j   M ℓ,k+1 P k (π k -πℓ,k )(w π k -w π ℓ,k ) = H k=2 H h=k r ℓ,h , π h   h j=k+1 M ℓ,j+1 P j π j   M ℓ,k+1 P k (π k -πℓ,k )(w π k -w π ℓ,k ) = H k=2 ⟨P ⊤ k M ℓ,k+1 V ℓ,k+1 , (π k -πℓ,k )(w π k -w π ℓ,k )⟩.It follows thatH h=1 ⟨ r ℓ,h , π h (δ π ℓ,h -δ π ℓ,h )⟩ + ⟨ r ℓ,h , (π h -πℓ,h )(w π h -w π ℓ,h )⟩ = H h=2 ⟨P ⊤ h M ℓ,h+1 V ℓ,h+1 + r ℓ,h , (π h -πℓ,h )(w π ℓ,h -w π ℓ,h )⟩ + ∆ for some ∆ satisfying |∆| ≤ 32S 3/2 H 2 ϵ ℓ unif . On E good (specifically Ēℓ est ), we can bound H h=2 |⟨P ⊤ h M ℓ,h+1 V ℓ,h+1 + r ℓ,h , (π h -πℓ,h )(w π ℓ,h -w π ℓ,h )⟩| ≤ H h=2 2E s∼w π ℓ,h [⟨P ⊤ h M ℓ,h+1 V π ℓ,h+1 + r ℓ,h , (π h -πℓ,h )e s ⟩ 2 ] nℓ • log 60Hℓ 2 |Π ℓ | δ + 2H 3n ℓ log 60H 2 ℓ 2 |Π ℓ | δWe can also boundE s∼w π ℓ,h [⟨P ⊤ h M ℓ,h+1 V π ℓ,h+1 + r ℓ,h , (π h -πℓ,h )e s ⟩ 2 ] ≤ 2E s∼w π ℓ,h [⟨P ⊤ h V π h+1 + r h , (π h -πℓ,h )e s ⟩ 2 ] + 2HE s∼w π ℓ,h [|[π ⊤ h P ⊤ h (M ℓ,h+1 V π ℓ,h+1 -V π h+1 )] s |] + 2HE s∼w π ℓ,h [|[ π⊤ ℓ,h P ⊤ h (M ℓ,h+1 V π ℓ,h+1 -V π h+1 )] s |] + 4E s∼w π ℓ,h [sup a |r h (s, a) -r ℓ,h (s, a)|]Furthermore,E s∼w π ℓ,h [|[π ⊤ h P ⊤ h (M ℓ,h+1 V π ℓ,h+1 -V π h+1 )] s |] = s |[π ⊤ h P ⊤ h (M ℓ,h+1 V π ℓ,h+1 -V π h+1 )] s |w π ℓ,h (s) ≤ √ S∥(M ℓ,h+1 V π ℓ,h+1 -V π h+1 ) ⊤ P h π h w π ℓ,h ∥ 2 ≤ √ S∥( V π ℓ,h+1 -V π h+1 ) ⊤ P h π h w π ℓ,h ∥ 2 + √ S∥(M ℓ,h+1 V π ℓ,h+1 -V π ℓ,h+1 ) ⊤ P h π h w π ℓ,h ∥ 2 ≤ 64S 2 H 2 ϵ ℓ unifwhere the last inequality follows from the definition of V and Lemma 17. A similar bound can be shown forE s∼w π ℓ,h [|[ π⊤ ℓ,h P ⊤ h (M ℓ,h+1 V π ℓ,h+1 -V π h+1 )] s |].In addition, by definition of r ℓ,h we haveE s∼w π ℓ,h [sup a |r h (s, a) -r ℓ,h (s, a)|] ≤ E s∼w π ℓ,h [I{s ̸ ∈ S keep ℓ,h }] ≤ 32Sϵ ℓ unif .Thus, we haveH h=2 |⟨P ⊤ h M ℓ,h+1 V ℓ,h+1 + r h , (π h -πℓ,h )(w π ℓ,h -w π ℓ,h )⟩| ≤ H h=2 2E s∼w π ℓ,h [⟨P ⊤ h M ℓ,h+1 V π ℓ,h+1 + r h , (π h -πℓ,h )e s ⟩ 2 ] nℓ • log 60Hℓ 2 |Π ℓ | δ + 2H 3n ℓ log 60H 2 ℓ 2 |Π ℓ | δ ≤ H h=2 4U h (π, πℓ ) + 384S 2 H 3 ϵ ℓ unif nℓ • log 60Hℓ 2 |Π ℓ | δ + 2H 3n ℓ log 60H 2 ℓ 2 |Π ℓ | δ .By Lemma 23 and Jensen's inequality, this can be further bounded as≤ H h=2 c U ℓ-1,h (π, πℓ ) + S 3/2 H 3 A log 24S 2 AHℓ 2 δ • ϵ 1/3 ℓ + S 2 H 3 ϵ ℓ unif nℓ • log 60Hℓ 2 |Π ℓ | δ + 2H 3n ℓ log 60H 2 ℓ 2 |Π ℓ | δ ≤ c H U ℓ-1 (π, πℓ ) + S 3/2 H 4 A log 24S 2 AHℓ 2 δ • ϵ 1/3 ℓ + S 2 H 4 ϵ ℓ unif nℓ • log 60Hℓ 2 |Π ℓ | δ + 2H 3n ℓ log 60H 2 ℓ 2 |Π ℓ | δ .The result then follows from this, our choice of nℓ and ϵ ℓ unif , and the bound on ∆ above.Lemma 25. On E good , we can boundinf πexp max π∈Π ℓ ∥M ℓ,h ((π h -πℓ,h ) w π ℓ,h + π h δ π ℓ,h )∥ 2 Λ h (πexp) -1 ϵ ℓ exp ≤ inf πexp max π∈Π ℓ 4∥ πℓ,h w π ℓ,h -π h w π h ∥ 2 Λ h (πexp) -1 ϵ ℓ exp + (8S 2 A + 32S 3 AH 2 )ϵ 5/3 ℓ + 2S 2 AHβ ℓ ϵ ℓ exp + 4096S 3 AH 2 (ϵ ℓ unif ) 2 ϵ ℓ unif ϵ ℓ exp .Proof. We can bound:inf πexp max π∈Π ℓ ∥M ℓ,h ((π h -πℓ,h ) w π ℓ,h + π h δ π ℓ,h )∥ 2 Λ h (πexp) -1 ≤ inf πexp max π∈Π ℓ 4∥M ℓ,h ((π h -πℓ,h )w π ℓ,h + π h δ π ℓ,h )∥ 2 Λ h (πexp) -1 + inf π ′ exp max π∈Π ℓ 8∥M ℓ,h (π h -πℓ,h )(w π ℓ,h -w π ℓ,h )∥ 2 Λ h (π ′ exp ) -1 + 8∥M ℓ,h π h (δ π ℓ,h -δ π ℓ,h )∥ 2 Λ h (π ′ exp ) -1 .We can write∥M ℓ,h (π h -πℓ,h )(w π ℓ,h -w π ℓ,h )∥ 2 Λ h (π ′ exp ) -1 = s,a (π h (a | s) -πℓ,h (a | s)) 2 (w π ℓ,h (s) -w π ℓ,h (s)) 2 [Λ h (π ′ exp )] sa,sa • I{(s, a) ∈ S keep ℓ,h } ≤ s,a (w π ℓ,h (s) -w π ℓ,h (s)) 2 [Λ h (π ′ exp )] sa,sa • I{(s, a) ∈ S keep ℓ,h }.On E good , for each (s, a) ∈ S keep ℓ,h we have W ⋆ h (s) ≥ ϵ ℓ unif . Let π sh denote the policy which achieves w π sh h (s) = W ⋆ h (s), and then plays actions uniformly at random at (s, h). Let π ′ exp = unif({π sh } s ).Then we have [Λ h (π ′ exp )] sa,sa ≥ W ⋆ h (s)/SA ≥ ϵ ℓ unif /SA for each (s, a) ∈ S keep ℓ,h, so we can bound the above as≤ SA ϵ ℓ unif s,a (w π ℓ,h (s) -w π ℓ,h (s)) 2 = SA ϵ ℓ unif ∥w π ℓ,h -w π ℓ,h ∥ 2 2 ≤ 8S 2 Aϵ 5/3 ℓ ϵ ℓ unif ,where the last inequality follows from Lemma 19.We can obtain a bound on∥M ℓ,h π h (δ π ℓ,h -δ π ℓ,h )∥ 2 Λ h (π ′exp ) -1 using a similar argument but now applying Lemma 18 to get that:∥M ℓ,h π h (δ π ℓ,h -δ π ℓ,h )∥ 2 Λ h (π ′ exp ) -1 ≤ 2S 2 AHβ ℓ ϵ ℓ exp ϵ ℓ unif + 32S 3 AH 2 ϵ 5/3 ℓ ϵ ℓ unif + 4096S 3 AH 2 ϵ ℓ unif .Finally, note that∥M ℓ,h ((π h -πℓ,h )w π ℓ,h + π h δ π ℓ,h )∥ 2 Λ h (πexp) -1 = ∥M ℓ,h ( πℓ,h w π ℓ,h + π h w π h )∥ 2 Λ h (πexp) -1 ≤ ∥ πℓ,h w π ℓ,h -π h w π h ∥ 2 Λ h (πexp) -1where the equality holds by definition, and the inequality by simply manipulations. Combining these bounds gives the result.Lemma 26. On the event E good , for all π ∈ Π ℓ+1 , we haveEQUATION.By Lemma 21, on E good we have (a) ≤ ϵ ℓ and (b) ≤ ϵ ℓ , and by Lemma 24, (c) ≤ ϵ ℓ . To bound (d), we note that π h δ π ℓ,h + (π h -πℓ,h )w π ℓ,h = π h w π h -πℓ,h w π ℓ,h , and so, on E good and by definition of r ℓ,h ,(d) ≤ H h=1 s̸ ∈S keep ℓ,h (w π h (s) + w π ℓ,h (s)) ≤ 64HSϵ ℓ unif ≤ ϵ ℓ .Note that we only eliminate policy π ∈ Π ℓ at roundℓ if max π ′ D πℓ (π ′ ) -D πℓ (π) > 8ϵ ℓ . Assume that π ⋆ ∈ Π ℓ .By what we have just shown, if policy π is eliminated, we then have8ϵ ℓ < max π ′ ∈Π ℓ D πℓ (π ′ ) -D πℓ (π) + 8ϵ ℓ = V ⋆ 0 -V π 0 + 8ϵ ℓ =⇒ V π 0 < V ⋆ 0 .It follows that π ⋆ will not be eliminated at round ℓ, as long as π ⋆ ∈ Π ℓ . By a simple inductive argument, since π ⋆ ∈ Π 0 , it follows that on E good , π ⋆ ∈ Π ℓ for all ℓ.Furthermore, for each π ∈ Π ℓ+1 , we have max π ′ D πℓ (π ′ ) -D πℓ (π) ≤ 8ϵ ℓ . Which, again by what we have just shown, implies that8ϵ ℓ ≥ max π ′ ∈Π ℓ D πℓ (π ′ ) -D πℓ (π) -8ϵ ℓ = V ⋆ 0 -V π 0 -8ϵ ℓ =⇒ V ⋆ 0 -V π 0 ≤ 16ϵ ℓ .Theorem 1. There exists an algorithm (Algorithm 1) which, with probability at least 1 -2δ, finds an ϵ-optimal policy and terminates after collecting at most Proof. First, by Lemma 20, we have that P[E good ] ≥ 1 -2δ. For the remainder of the proof we assume we are on E good .EQUATIONBy Lemma 26, we have that on E good , for every π ∈ Π ℓ+1 , V ⋆ 0 -V π 0 ≤ 16ϵ ℓ , and that π ⋆ ∈ Π ℓ for all ℓ. It follows that, since we run for ℓ ϵ = ⌈log 2 16/ϵ⌉ epochs, when we terminate each policyπ ∈ Π ℓϵ satisfies V ⋆ 0 -V π 0 ≤ 16ϵ ℓϵ = 16 • 2 -ℓϵ ≤ ϵ.Furthermore, if we terminate early on Line 20, then we know that |Π ℓ+1 | = 1, and since π ⋆ ∈ Π ℓ+1 , we have that the algorithm returns π ⋆ . Thus, the policy returned by Algorithm 2 is always ϵ-optimal.It therefore remains to bound the sample complexity of Algorithm 2. At round ℓ of Algorithm 2, we collect nℓ samples plus the number of samples collected from OPTCOV. On E good , we have that the number of samples collected by OPTCOV at round ℓ step h is bounded byC • inf πexp max π∈Π ℓ ∥M ℓ h ((π h -πℓ,h ) w π ℓ,h + π h δ π ℓ,h )∥ 2 Λ h (πexp) -1 ϵ ℓ exp + C ℓ fw (ϵ ℓ exp ) 4/5 + C ℓ fw ϵ ℓ unif + log(C ℓ fw ) • K ℓ unif (a) ≤ C • inf πexp max π∈Π ℓ ∥ πℓ,h w π ℓ,h -π h w π h ∥ 2 Λ h (πexp) -1 ϵ ℓ exp + C ℓ fw (ϵ ℓ exp ) 4/5 + C ℓ fw ϵ ℓ unif + log(C ℓ fw ) • K ℓ unif + (8S 2 A + 32S 3 AH 2 )ϵ 5/3 ℓ + 2S 2 AHβ ℓ ϵ ℓ exp + 4096S 3 AH 2 (ϵ ℓ unif ) 2 ϵ ℓ unif ϵ ℓ exp (b) ≤ C • inf πexp max π∈Π ℓ ∥ πℓ,h w π ℓ,h -π h w π h ∥ 2 Λ h (πexp) -1 ϵ 2 ℓ • H 4 β 2 ℓ + C ℓ poly ϵ 5/3 ℓ (c) ≤ C • inf πexp max π∈Π ℓ ∥π ⋆ h w π ⋆ h -π h w π h ∥ 2 Λ h (πexp) -1 ϵ 2 ℓ • H 4 β 2 ℓ + C ℓ poly ϵ 5/3 ℓ (d) ≤ C • inf πexp max π∈Π ∥π ⋆ h w π ⋆ h -π h w π h ∥ 2 Λ h (πexp) -1 max{ϵ 2 ℓ , ∆(π) 2 } • H 4 β 2 ℓ + C ℓ poly ϵ 5/3 ℓwhere the initial bound holds from Lemma 14, the (a) follows from Lemma 25, and (b) follows plugging in our choice of ϵ ℓ unif and ϵ ℓ exp , and with C ℓ poly = poly(S, A, H, log ℓ/δ, log 1/ϵ, log |Π|), (c) holds by the triangle inequality and since πℓ ∈ Π ℓ , and (d) holds because, for all π ∈ Π ℓ , we have ∆(π) ≤ 32ϵ ℓ . Furthermore, we can bound nℓ as nℓ = minπ∈Π ℓ max π∈Π ℓ c • H U ℓ-1 (π, π) + H 4 S 3/2 √ A log SAHℓ 2 δ • ϵ 1/3 ℓ + S 2 H 4 ϵ ℓ unif ϵ 2 ℓ • log 60Hℓ 2 |Π ℓ | δ (a)≤ minπ∈Π ℓ max π∈Π ℓ c • HU (π, π) + H 4 S 3/2 √ A log SAHℓ 2 δ • ϵ 1/3 ℓ + S 2 H 4 ϵ ℓ unif ϵ 2 ℓ • log 60Hℓ 2 |Π ℓ | δ (b) ≤ max π∈Π c • HU (π, π ⋆ ) max{ϵ 2 ℓ , ∆(π) 2 } • log 60Hℓ 2 |Π ℓ | δ + C ℓ poly ϵ 5/3 ℓwhere (a) follows from Lemma 23, and (b) since π ⋆ ∈ Π ℓ , and by a similar argument as above.Thus, if we run for a total of L rounds, the sample complexity is bounded asL ℓ=1 C • H h=1 inf πexp max π∈Π ∥π ⋆ h w π ⋆ h -π h w π h ∥ 2 Λ h (πexp) -1 max{ϵ 2 ℓ , ∆(π) 2 } • H 4 β 2 ℓ + max π∈Π c • HU (π, π ⋆ ) max{ϵ 2 ℓ , ∆(π) 2 } • log 60Hℓ 2 |Π ℓ | δ + LC L poly ϵ 5/3 L .By construction, we have that L ≤ ⌈log 2 16/ϵ⌉. However, we terminate early if |Π ℓ+1 | = 1, and since each π ∈ Π ℓ+1 satisfies ∆(π) ≤ ϵ ℓ , it follows that we will have |Π ℓ+1 | = 1 once ϵ ℓ < ∆ min , which will occur for ℓ ≥ ⌈log 2 1 ∆min ⌉ + 1. Thus, we can bound L ≤ min{⌈log 2 16/ϵ⌉, ⌈log 2 1/∆ min ⌉ + 1}, and so for all ϵ ℓ , ℓ ≤ L, we have ϵ ℓ ≥ c • max{ϵ, ∆ min }. Plugging this into the above gives the final complexity.Setting and notation. We study stochastic tabular contextual bandits, denoted by the tuple (C, A, µ ⋆ , ν). At each episode, a context c ∼ µ ⋆ arrives, the agent chooses an action a ∈ A, and receives reward r(c, a) ∼ ν(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" to highlight that the agent has no impact on these. The vector µ ⋆ plays the same role as the state visitation vectors w π h previously, except this is now policy-independent. The notation for policy matrix π, values V π , features ϕ π (c, a) are inherited directly from the general case. Define θ ⋆ ∈ R |C|A as the vector of reward means, so that [θ ⋆ ] (c,a) = E ν [r(c, a)]. Then, we can write the value of π as:E ν,µ ⋆ [r(c, π(c))] = c,a θ ⋆ c,a [µ ⋆ ] c [π(c)] a = (θ ⋆ ) ⊤ πµ ⋆For any (θ, µ) define OPT(θ, µ) := arg max π∈Π θ ⊤ πµ, where θ is any hypothetical vector of reward-means and µ ∈ ∆ |C| is a hypothetical context distribution.Recall that we use π ∈ R |C|A×|C| to refer to the policy matrix. The vector πµ ∈ R |C|A contains context-action visitations for policy π under context distribution µ. Define function G(µ, π) = E µ,π [(πµ)(πµ) ⊤ ] which returns the expected covariance matrix of policy π under context distribution µ. For shorthand, we refer to Â(π) = G( µ ℓ , π exp ) and A(π) = G(µ ⋆ , π exp ) for any π. Lemma 27. Define the experimental design objectiveF (π exp , µ, π, π ′ ) = ∥(π ′ -π)µ∥ 2 G(µ,πexp) -1 .Then, for any µ ∈ ∆ C ,min πexp max π,π ′ ∈Π ℓ F (π exp , µ, π, π ′ ) = max π,π ′ ∈Π ℓ min πexp F (π exp , µ, π, π ′ )Proof. We can rewrite the maximization problem to be over the simplex ∆ Π ℓ ×Π ℓ instead:min πexp max λ∈∆Π ℓ ×Π ℓ π,π ′ ∈Π ℓ ×Π ℓ λ π,π ′ F (π exp , µ, π, π ′ ) (D.1)This does not change the objective value. To see this, note that for any selection (π 1 , π 2 ) in the original problem, the same objective value can be obtained by setting λ = e π1,π2 ; hence, the modification to the optimization cannot reduce the value. Further if F (π exp , µ, π, π ′ ) is maximized by (π 1 , π 2 ), setting λ as anything other than e π1,π2 cannot increase the objective value. Now, note that both the minimization and maximization problems are over simplices, which are compact and convex sets. The objective is linear in the maximization variable, and hence concave. The objective can be rewritten asEQUATIONHere, p c,a as the probability that π exp plays action a, given that we are in context c. From this representation, we can clearly see that the objective is convex in each p c,a . Hence, since we are optimizing over finite-dimensional spaces (|A| and |C| are finite), Von Neumann's minimax theorem applies and the proof is complete.Lemma 28. For the contextual bandit problem, define the experimental design objectiveF (π exp , µ, π, π ′ ) = ∥(π ′ -π)µ∥ 2 G(µ,πexp) -1 .Then, for any µ and assuming that all policies in Π ℓ are deterministic, we have:EQUATIONProof. Below, we refer to p c,a as the probability that π exp plays action a, given that we are in context c. We have:min πexp max π,π ′ ∈Π ℓ ∥(π ′ -π)µ∥ 2 G(µ,πexp) -1 = max π,π ′ ∈Π ℓ min πexp ∥(π ′ -π)µ∥ 2 G(µ,πexp) -1 = max π,π ′ ∈Π ℓ min p1...p C ∈∆ A a,c µ 2 c (π -π ′ ) ⊤ e a,c e ⊤ a,c (π -π ′ ) µ c p c,a = max π,π ′ ∈Π ℓ c µ c min pc a∈A (π -π ′ ) ⊤ e a,c e ⊤ a,c (π -π ′ ) p c,a = max π,π ′ ∈Π ℓ c µ c a∈A (π -π ′ ) ⊤ e a,c e ⊤ a,c (π -π ′ ) 2 .Here the first equality follows from Lemma 27, and the last from Lemma D.6 of [30] .We have assumed that the policies in Π ℓ are deterministic. Hence, the only two actions in the summation over A above that are relevant are π(c) and π ′ (c). For all other a ∈ A, the term in the square root evaluates to 0. If π(c) = π ′ (c), then the entire summation over A evaluates to 0; else, the terms indexed by π(c) and π ′ (c) are both 1, and the summation evalutes to 2. Hence, we can simplify the expression to exactly the form of Equation (D.2) from the lemma statement, and the proof is complete.Lemma 29. For the contextual bandits problem, we have thatmax π∈Π E c∼µ ⋆ [E ν ⋆ [(r(c, π(c)) -r(c, π ⋆ (c))) 2 |c]] ≤ inf πexp max π∈Π ∥ϕ ⋆ -ϕ π ∥ 2 Λ(πexp) -1Proof. Observe that r(c, π(c))-r(c, π⋆ (c)) = 0 if π(c) = π ⋆ (c); else, |r(c, π(c))-r(c, π ⋆ (c))| ≤ 2.Then, it follows thatmax π∈Π E c∼µ ⋆ [E ν ⋆ [(r(c, π(c)) -r(c, π ⋆ (c))) 2 |c]] ≤ max π∈Π 4E c∼µ ⋆ I(π(c) ̸ = π ⋆ (c)) = inf πexp max π∈Π ∥ϕ ⋆ -ϕ π ∥ 2 Λ(πexp) -1 ,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 -2δ, as long as Π contains only deterministic policies, it finds an ϵ-optimal policy and terminates after collecting at most the following number of samples: Proof. In the special case of contextual bandits, U (π, π ⋆ ) defined in Theorem 1 can be written more simply asEQUATIONE c∼µ ⋆ [E ν ⋆ [(r(c, π(c)) -r(c, π ⋆ (c))) 2 |c]].Then, by Lemma 29, we have that:U (π, π ⋆ ) max{ϵ 2 , ∆(π) 2 , ∆ 2 min } ≤ inf πexp max π∈Π ∥ϕ ⋆ -ϕ π ∥ 2 Λ(πexp) -1max{ϵ 2 , ∆(π) 2 , ∆ 2 min } Plugging this into Theorem 1 completes the proof.We consider here a special class of MDPs where the transitions only depend on the states and are independent of the actions selected i.e all P h are such that P h (s, a) = P h (s, a ′ ) for all (a, a ′ ) ∈ A. In this special case, we prove in this subsection that the (leading order) complexity of PERP reduces to O(ρ Π ). Lemma 30. For the ergodic MDP problem,min πexp max π∈Π ∥ϕ π h -ϕ ⋆ h ∥ 2 Λ h (πexp)-1 = max π∈Π min πexp ∥ϕ π h -ϕ ⋆ h ∥ 2 Λ h (πexp)-1Proof. We can rewrite the maximization problem to be over the simplex ∆ Π instead:min πexp max λ∈∆Π π∈Π λ π ∥ϕ π h -ϕ ⋆ h ∥ 2 Λ h (πexp)-1 (E.1)This does not change the objective value. To see this, note that for any selection π ∈ Π in the original problem, the same objective value can be obtained by setting λ = e π in Equation (E.1); hence, the modification to the optimization cannot reduce the value. Further if ∥ϕ π h -ϕ ⋆ h ∥ 2 Λ h (πexp)-1 is maximized by π for any fixed π exp , setting λ as anything other than e π cannot increase the objective value. Now, note that both the minimization and maximization problems are over simplices, which are compact and convex sets. The objective is linear in the maximization variable, and hence concave. The objective can be rewritten asa (π h -π ⋆ h ) ⊤ e s,a e ⊤ s,a (π h -π ⋆ h ) p s,aHere, p s,a is the probability that π exp plays action a, given that it is in context s. From this representation, we can clearly see that the objective is convex in each p s,a . Hence, Von Neumann's minimax theorem applies and the proof is complete. Lemma 31. For the setting of ergodic MDPs,min πexp max π∈Π ∥ϕ π h -ϕ ⋆ h ∥ 2 Λ h (πexp)-1 = max π∈Π 2E s∼w ⋆ h I[π h (s) ̸ = π ′ h (s)], (E.2)Proof. Below, we refer to p s,a as the probability that π exp plays action a, given that it is in context s.The second equality follows from Lemma 30.EQUATIONThe 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 π h (s) and π ′ h (s). For all other a ∈ A, the term in the square root evaluates to 0. If π h (s) = π ′ h (s), then the entire summation over A evaluates to 0; else, the terms indexed by π(c) and π ′ (c) are both 1, and the summation evalutes to 2. Hence, we can simplify the expression to exactly the form of Equation (E.2) from the lemma statement, and the proof is complete. Lemma 32. For the ergodic MDP problem, we have thatmax π∈Π HU (π, π ⋆ ) max{ϵ 2 , ∆(π) 2 , ∆ 2 min } ≤ 2H 4 H h=1 inf πexp max π∈Π ∥ϕ ⋆ h -ϕ π h ∥ 2 Λ h (πexp) -1 max{ϵ 2 , ∆(π) 2 , ∆ 2 min } Proof. Recall the definition of U (π, π ⋆ ) U (π, π ⋆ ) = H h=1 E s h ∼w π ⋆ h [(Q π h (s h , π h (s)) -Q π h (s h , π ⋆ h (s))) 2 ].Then, we have thatmax π∈Π HU (π, π ⋆ ) max{ϵ 2 , ∆(π) 2 , ∆ 2 min } = max π∈Π H H h=1 E s h ∼w π ⋆ h [(Q π h (s h , π h (s)) -Q π h (s h , π ⋆ h (s))) 2 ] max{ϵ 2 , ∆(π) 2 , ∆ 2 min } ≤ H H h=1 max π∈Π E s h ∼w π ⋆ h [(Q π h (s h , π h (s)) -Q π h (s h , π ⋆ h (s))) 2 ] max{ϵ 2 , ∆(π) 2 , ∆ 2 min } ≤ H H h=1 max π∈Π 2H 2 E s∼w ⋆ h I[π h (s) ̸ = π ′ h (s)] max{ϵ 2 , ∆(π) 2 , ∆ 2 min } = H 4 H h=1 inf πexp max π∈Π ∥ϕ ⋆ h -ϕ π h ∥ 2 Λ h (πexp) -1 max{ϵ 2 , ∆(π) 2 , ∆ 2 min }.The final equality follows from Lemma 31.Corollary 2. Assume that all P h are such that P h (s ′ |s, a) = P h (s ′ |s, a ′ ) for all (a, a ′ ) ∈ A. Then, with probability at least 1 -2δ, PERP (Algorithm 2) finds an ϵ-optimal policy and terminates after collecting at most the following number of episodes:H h=1 inf πexp max π∈Π ∥ϕ ⋆ h -ϕ π h ∥ 2 Λ h (πexp) -1 max{ϵ 2 , ∆(π) 2 } • ιH 4 β 2 + C poly max{ϵ 5/3 , ∆ 5/3min } for C poly , β as defined in Theorem 1.Proof. The proof follows directly from Theorem 1 and Lemma 32.Theorem 2. Fix parameters K unif > 0, ϵ exp > 0, and consider some Φ ⊆ R SA and set S 0 ⊆ S. Let ϵ unif > 0 be some value satisfyingW ⋆ h (s) > ϵ unif , ∀s ∈ S 0 , and K unif ≥ ϵ -1 unif . Assume that |[ϕ] (s,a) | ≤ C ϕ • (W ⋆ h (s) + √ ϵ ϕ )for all s ∈ S 0 , ϕ ∈ Φ, and some C ϕ > 0, and that[ϕ] (s,a) = 0 for s ̸ ∈ S 0 . Additionally, let the parameters be such that ϵ ϕ /(K unif ϵ unif ) ≤ ϵ exp . Then with probability at least 1 -δ, algorithm Algorithm 3 run with these parameters will collect at mostmin C • inf Λ∈Ω h max ϕ∈Φ ∥ϕ∥ 2 Λ -1 ϵ exp + C fw ϵ 4/5 exp , C fw ( 1 ϵ exp + K unif ) + C fw ϵ unif + log(C fw ) • K unifepisodes, for C a universal constant and C fw = poly(S, A, H, C ϕ , log 1/δ, log 1/ϵ exp , log |Φ|), and will produce covariates Σ such thatmax ϕ∈Φ ∥ϕ∥ 2 Σ -1 ≤ ϵ exp (F.1)and, for all s ∈ S 0 ,[ Σ] (s,a) ≥ ϵ unif 2SA • K unif . (F.2)Algorithm 3 Online Experiment Design (OPTCOV)1: input: directions Φ, tolerance ϵ exp , confidence δ, minimum reachability ϵ unif , minimum exploration K unif , pruned states S 0 , step h 2: i ← 1 3: while T i K i ≤ poly(S, A, H, C ϕ , log 1/δ, log 1/ϵ exp , log |Φ|) • ϵ -1 exp do 4:D i unif ← UNIFEXP(ϵ unif , K i T i + K unif , δ/8i 2 )5:Λ i 0 ← 1 TiKi diag(v i ) where [v i ] sa = (s ′ ,a ′ )∈D i unifI{(s ′ , a ′ ) = (s, a)} for s ∈ S 0 , and T i K i otherwise 6:Run iteration i of Algorithm 4 of [43] on objectivef i (Λ) ← 1 η i log   ϕ∈Φ e ηi∥ϕ∥ 2 A(Λ) -1   for A(Λ) = Λ + Λ i 0 , η i = 2 2i/5to obtain data D i 7:if Algorithm 4 reaches termination condition then 8:return D i ∪ D i unif 9:end if10: i ← i + 1 11: end while 12: D ← UNIFEXP(ϵ unif , 8S 2 A 2 C 2 ϕ ϵexp + (8S 2 A 2 C 2 ϕ + 1)K unif , δ/4) 13: return D Proof.To prove this result, we apply Lemma 37 combined with Lemma 36.exp denote the success event of running Algorithm 4 at epoch i, as defined in Lemma 36. On this event, and under the assumption that W ⋆ h (s) > ϵ unif for each s ∈ S 0 , we have that[Σ i ] (s,a) ≥ W ⋆ h (s)2SA • (T i K i + K unif ) for each (s, a) with s ∈ S 0 and Σ i the covariates induced by D i unif , which implies that[Λ i 0 ] (s,a) ≥ 1 T i K i W ⋆ h (s) 2SA • (T i K i + K unif ) ≥ W ⋆ h (s) 2SAfor each (s, a) with s ∈ S 0 , and, furthermore, Algorithm 4 collects at mostT i K i + K unif + poly(S, A, H, log T i K i i 2 δϵ unif ) • 1 ϵ unif (F.3)episodes. Furthermore, by Lemma 36, we have P[E i exp ] ≥ δ/2i 2 , so it follows thatP[∪ i≥1 (E i exp ) c ] ≤ ∞ i=1 δ 8i 2 ≤ δ/4.Henceforth, we therefore assume that E i exp holds for each i. This immediately implies that (F.2) holds.It remains to show that (F.1) is satisfied, and that our sample complexity guarantee is met. To this end we apply Lemma 37 with Λ 0 a diagonal matrix, with[Λ 0 ] (s,a) = W ⋆ h (s)2SA for s ∈ S 0 , and otherwise [Λ 0 ] (s,a) = 1. Note that with this choice of Λ 0 , by what we just showed above, we have Λ i 0 ⪰ Λ 0 , as 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 Ω h,TiKi (δ/8i 2 ) with probability 1 -δ/8i 2 . Union bounding over this event for all i, with probability at least 1 -δ/4, we have that for each i all iterates of FWREGRET live in the set Ω h,TiKi (δ/8i 2 ). By Lemma 35, since we have assumedthat |[ϕ] (s,a) | ≤ C ϕ • (W ⋆ h (s) + √ ϵ ϕ) for all (s, a) with s ∈ S 0 and otherwise [ϕ] (s,a) = 0 for all ϕ ∈ Φ, we can then boundM i ≤ max s∈S0 2SAC 2 ϕ C ′ + 2SAC 2 ϕ ϵ ϕ C ′ • W ⋆ h (s) • 2 C ′ + 2 C ′ T i K i W ⋆ h (s) • log SAH δ β i ≤ max s∈S0 (2η i + 2) 2SAC 2 ϕ C ′ + 2SAC 2 ϕ ϵ ϕ C ′ • W ⋆ h (s) 2 • 2 C ′ + 2 C ′ T i K i W ⋆ h (s) • log SAH δ 2On the event E i exp , as noted above we haveEQUATION2SA (1 + K unif TiKi ) for s ∈ S 0 , so we can takeC ′ = 1 2SA (1 + K unif TiKi ). We can then bound max s∈S0 2SAC 2 ϕ C ′ + 2SAC 2 ϕ ϵ ϕ C ′ • W ⋆ h (s) • 2 C ′ + 2 C ′ T i K i W ⋆ h (s) • log SAH δ ≤ 4S 2 A 2 C ϕ + 4S 2 A 2 C 2 ϕ ϵ ϕ • T i K i K unif ϵ unif • 4SA + 4SA K unif ϵ unif log SAH δwhere we have used that W ⋆ h (s) ≥ ϵ unif for all s ∈ S 0 , by assumption. By assumption we haveϵ ϕ K unif ϵ unif ≤ ϵ exp .Note that by construction, the while statement on Line 3 will ensure that we always haveT i K i ≤ poly(S, A, H, C ϕ , log 1/δ, log 1/ϵ exp , log |Φ|) • ϵ -1 exp , so we can bound ϵ exp • T i K i ≤ poly(S, A, H, C ϕ , log 1/δ, log 1/ϵ exp , log |Φ|).It follows that it suffices to take β, M ≤ poly(S, A, H, C ϕ , log 1/δ, log 1/ϵ exp , 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 1 -δ/4 we have that the procedure terminates after running for at most max min EQUATIONf i (N -1 Σ N ) ≤ N ϵ exp ,where i is the index of the epoch on which it terminates. By Lemma D.1 of [42] , we havemax ϕ∈Φ ∥ϕ∥ 2 A(N -1 Σ N ) -1 ≤ f i (N -1 Σ N ) ≤ N ϵ exp which implies max ϕ∈Φ ∥ϕ∥ 2 ( Σ N +Σ i ) -1 ≤ ϵ exp ,which proves (F.1). Furthermore, (F.2) holds since as noted[Σ i ] (s,a) ≥ W ⋆ h (s) 2SA • (T i K i + K unif) for each (s, a) with s ∈ S 0 , and since W ⋆ h (s) ≥ ϵ unif for all s ∈ S 0 . In the second case, when the while loop on Line 3 terminates since T i K i ≤ poly(S, A, H, C ϕ , log 1/δ, log 1/ϵ exp , log |Φ|) • ϵ -1 exp , we can bound the total number of episodes collected within the calls to Algorithm 4 of [43] within the while loop by poly(S, A, H, C ϕ , log 1/δ, log 1/ϵ exp , log |Φ|) • ϵ -1 exp . Furthermore, by Lemma 36, with probability at least 1 -δ/4, we have that the call to UNIFEXP on Line 12 terminates after running for at most8S 2 A 2 C 2 ϕ ϵ exp + (8S 2 A 2 C 2 ϕ + 1)K unif + poly(S, A, H, log T i K i i 2 δϵ unif ) • 1 ϵ unifepisodes, and that the returned data satisfies N h (s, a) ≥W ⋆ h (s) 2SA • ( 8S 2 A 2 C 2 ϕ ϵexp + 8S 2 A 2 C 2 ϕ K unif + K unif ). Since |[ϕ] (s,a) | ≤ C ϕ • (W ⋆ h (s) + √ ϵ ϕ ) and ϵ ϕ /(K unif ϵ unif ) ≤ ϵ exp by assumption, some manipulation shows that [ϕ] 2 (s,a) N h (s, a) ≤ C 2 ϕ • (W ⋆ h (s) + √ ϵ ϕ ) 2 W ⋆ h (s) 2SA • ( 8S 2 A 2 C 2 ϕ ϵexp + 8S 2 A 2 C 2 ϕ K unif + K unif ) ≤ ϵ exp SA .It follows then that, letting Σ denote the covariance obtained by the call to UNIFEXP on Line 12,max ϕ∈Φ ∥ϕ∥ 2 Σ -1 ≤ ϵ exp as desired. Furthermore, it is straightforward to see that [ Σ] (s,a) ≥ ϵ unif 2SA• K unif for s ∈ S 0 as well. To complete the proof, we union bound over these events holding, and take the minimum of the sample complexity bounds from either case.Lemma 33. Consider running any algorithm for K episodes. Let K h (s, a) denote the number of visits to (s, a, h). Then with probability at least 1 -δ, for all (s, a, h) simultaneously, we haveK h (s, a) ≤ W ⋆ h (s)K + 2W ⋆ h (s)K • log SAH δ + log SAH δ .Proof. By definition, we havesup π w π h (s) = W ⋆ h (s).This implies that any policy will reach (s, h) with probability at most W ⋆ h (s). We can therefore think of this as the sum of Bernoullis with parameter at most W ⋆ h (s), so the bound follows by applying Bernstein's inequality and a union bound.Ω h,K (δ) := diag(v) : v ∈ R SA + , [v] (s,a) ≤ W ⋆ h (s) + 2W ⋆ h (s) K • log SAH δ + 1 K log SAH δ .Consider running some set of policies for K episodes, and let Λ be defined asΛ h = diag( v), [v] (s,a) = K h (s, a) K .Then with probability at least 1 -δ, we have that Λ h ∈ Ω h,K (δ) for all h ∈ [H] simultaneously.Proof. This is an immediate consequence of Lemma 33.We will denote Ω h,K := Ω h,K (δ) when the choice of δ is clear from context. Lemma 35. Consider the functionf (Λ) = 1 η log   ϕ∈Φ e η∥ϕ∥ 2 A(Λ) -1   for A(Λ) = Λ + Λ 0Assume that for all ϕ ∈ Φ we havemax ϕ∈Φ |[ϕ] (s,a) | ≤ C ϕ • (W ⋆ h (s) + ϵ), ∀s ∈ S 0for some S 0 and some C ϕ , ϵ > 0, and otherwise [ϕ] (s,a) = 0. Assume that Λ 0 = diag(v) for some v satisfying[v] (s,a) ≥ C ′ • W ⋆ h (s), ∀s ∈ S 0 and otherwise [v] (s,a) ≥ λ, for some C ′ , λ > 0. Then we can bound sup Λ, Λ ′ ∈ Ω h,K |∇ Λ f (Λ)| Λ= Λ [ Λ ′ ]| ≤ max s∈S0 2SAC 2 ϕ C ′ + 2SAC 2 ϕ ϵ 2 C ′ • W ⋆ h (s) • 2 C ′ + 2 C ′ KW ⋆ h (s) • log SAH δ and sup Λ, Λ ′ , Λ ′′ ∈ Ω h,K |∇ 2 Λ f (Λ)| Λ= Λ [ Λ ′ , Λ ′′ ]| ≤ max s∈S0 (2 + 2η) 2SAC 2 ϕ C ′ + 2SAC 2 ϕ ϵ 2 C ′ • W ⋆ h (s) 2 • 2 C ′ + 2 C ′ KW ⋆ h (s) • log SAH δ 2 .Proof. By Lemma D.5 of [42] , we have that∇ Λ f (Λ)| Λ= Λ [ Λ ′ ] = -   ϕ∈Φ e η∥ϕ∥ 2 A( Λ) -1   • ϕ∈Φ e η∥ϕ∥ 2 A( Λ) -1 ϕ ⊤ A( Λ) -1 Λ ′ A( Λ) -1 ϕ.We haveϕ ⊤ A( Λ) -1 Λ ′ A( Λ) -1 ϕ = s,a [ϕ] 2 (s,a) • [ Λ ′ ] (s,a) [A( Λ)] 2 (s,a) = s∈S0 a [ϕ] 2 (s,a) • [ Λ ′ ] (s,a) [A( Λ)] 2 (s,a)where the last equality follows since, for s ̸ ∈ S 0 , we have assumed [ϕ] (s,a) = 0. Now consider some s ∈ S 0 . By assumption we have[ϕ] 2 (s,a) ≤ 2C 2 ϕ • (W ⋆ h (s) 2 + ϵ 2) and by our assumption on Λ 0 we can lower bound[A( Λ)] (s,a) ≥ C ′ • W ⋆ h (s). Furthermore, since Λ ′ ∈ Ω h,K , we have [ Λ ′ ] (s,a) ≤ W ⋆ h (s) + 2W ⋆ h (s) K • log SAH δ + 1 K log SAH δ ≤ 2W ⋆ h (s) + 2 K log SAH δ .Putting this together, we have[ϕ] 2 (s,a) • [ Λ ′ ] (s,a) [A( Λ)] 2 (s,a) ≤ 4C 2 ϕ • (W ⋆ h (s) 2 + ϵ 2 ) • (W ⋆ h (s) + 1 K log SAH δ ) (C ′ • W ⋆ h (s)) 2 ≤ 2C 2 ϕ C ′ + 2C 2 ϕ ϵ 2 C ′ W ⋆ h (s) • 2 C ′ + 2 C ′ KW ⋆ h (s) log SAH δ . It follows that s∈S0 a [ϕ] 2 (s,a) • [ Λ ′ ] (s,a) [A( Λ)] 2 (s,a) ≤ max s∈S0 2SAC 2 ϕ C ′ + 2SAC 2 ϕ ϵ 2 C ′ W ⋆ h (s) • 2 C ′ + 2 C ′ KW ⋆ h (s) log SAH δ .The second bound follows in an analogous fashion, using the expression for the second derivative given in Lemma D.5 of [42] .F.2 Online Frank-Wolfe Lemma 37. Letf i (Λ) = 1 η i log   ϕ∈Φ e ηi∥ϕ∥ 2 A i (Λ) -1   , A i (Λ) = Λ + 1 T i K i Λ 0,ifor some Λ 0,i satisfying Λ 0,i ⪰ Λ 0 for all i, and η i = 2 2i/5 . Let (β i , M i ) denote the smoothness and magnitude constants for f i . Let (β, M ) be some values such that β i ≤ η i β, M i ≤ M for all i, and R the diameter of the domain of possible values of Λ.Then, if we run Algorithm 4 of [43] on (f i ) i with constraint tolerance ϵ and confidence δ and K i = T i = 2 i , we have that with probability at least 1 -δ, it will run for at most max minN 16N s.t. inf Λ∈Ω max ϕ∈Φ ϕ ⊤ (N Λ + Λ 0 ) -1 ϕ ≤ ϵ 6 , poly(β, R, d, H, M, log 1/δ, log |Φ|) ϵ 4/5 .episodes, and will return data{ϕ τ } N τ =1 with covariance Σ N = N τ =1 ϕ τ ϕ ⊤ τ such that f i (N -1 Σ N ) ≤ N ϵ,where i is the iteration on which OPTCOV terminates.Proof. Our goal is to simply find a setting of i that is sufficiently large to guarantee the condition [43] , we have with probability at least 1 -δ/(2i 2 ):f i ( Λ i ) ≤ K i T i ϵ is met. By Lemma C.1 off i ( Λ i ) ≤ inf Λ∈Ω f i (Λ) + β i R 2 (log T i + 3) 2T i + 4M 2 log(8i 2 T i /δ) K i + c 1 M 2 d 4 H 4 log 3 (8i 2 HK i T i /δ) K i + c 2 M d 4 H 3 log 7/2 (4i 2 HK i T i /δ) K i ≤ 3 max inf Λ∈Ω f i (Λ), β i R 2 (log T i + 3) 2T i , 4M 2 log(8i 2 T i /δ) K i + c 1 M 2 d 4 H 4 log 3 (8i 2 HK i T i /δ) K i + c 2 M d 4 H 3 log 7/2 (4i 2 HK i T i /δ) K i . So a sufficient condition for f i ( Λ i ) ≤ K i T i ϵ is that K i T i ≥ 3 ϵ max inf Λ∈Ω f i (Λ), β i R 2 (log T i + 3) 2T i , 4M 2 log(8i 2 T i /δ) K i + c 1 M 2 d 4 H 4 log 3 (8i 2 HK i T i /δ) K i + c 2 M d 4 H 3 log 7/2 (4i 2 HK i T i /δ) K i . (F.4) Recall that f i (Λ) = 1 η i log   ϕ∈Φ e ηi∥ϕ∥ 2 A i (Λ) -1   , A i (Λ) = Λ + 1 T i K i Λ 0,i .By Lemma D.1 of [42] , we can boundmax ϕ∈Φ ∥ϕ∥ 2 Ai(Λ) -1 ≤ f i (Λ) ≤ max ϕ∈Φ ∥ϕ∥ 2 Ai(Λ) -1 + log |Φ| η i . Thus, inf Λ∈Ω f i (Λ) ≤ inf Λ∈Ω max ϕ∈Φ ∥ϕ∥ 2 Ai(Λ) -1 + log |Φ| η i = inf Λ∈Ω max ϕ∈Φ T i K i ϕ ⊤ (T i K i Λ + Λ 0,i + Λ off ) -1 ϕ + log |Φ| η iBy our choice of η i = 2 2i/5 , and K i = 2 i , T i = 2 i , we can ensure thatK i T i ≥ 6 ϵ log |Φ| η i as long as i ≥ 2 5 log 2 [ 6 log |Φ| ϵ ].To ensure thatT i K i ≥ 6 ϵ inf Λ∈Ω max ϕ∈Φ T i K i ϕ ⊤ (T i K i Λ + Λ 0,i ) -1 ϕ it suffices to take i ≥ arg min i i s.t. inf Λ∈Ω max ϕ∈Φ ϕ ⊤ (2 3i Λ + Λ 0,i ) -1 ϕ ≤ ϵ 6 .Since we assume that we can lower bound Λ 0,i ⪰ Λ 0 for each i, so this can be further simplified toi ≥ arg min i i s.t. inf Λ∈Ω max ϕ∈Φ ϕ ⊤ (2 3i Λ + Λ 0 ) -1 ϕ ≤ ϵ 6 . (F.5)We next want to show that to meet this condition (this assumes that 12βR 2 ≥ 1 and 2 5 log 2 1 ϵ ≥ 1-if either of these is not the case we can just replace them with 1 without changing the validity of the final result).T i K i ≥ 3 ϵ • β i R 2 (log T i + 3) 2T i . Bounding β i ≤ η i β, aFinally, we want to ensure that ].T i K i ≥ 3 ϵ 4M 2 log(8iIf i is the final round, the total complexity scales as i i=1T i K i = i i=1 2 2i ≤ 2 • 2 2 i .Using the sufficient condition on i given above, we can bound the total complexity as max min Proof. As in Lemma 36, by Theorem 13 of [46] , with probability at least 1 -δ/SH, for any (s, h):• LEARN2EXPLORE will run for at most poly(S, A, H, log 1 δϵ unif ) • 1 ϵ unif episodes.• Rerunning every policy in Π js once, with probability at least 1/2 we will collect N = 2 -js |Π js | samples from (s, a, h).• If (s, a) ̸ ∈ X j for all j = 1, 2, . . . , ⌈log 1/ϵ unif ⌉, then W ⋆ h (s) ≤ 32ϵ unif .We union bound over this event holding for all (s, h), which occurs with probability at least 1 -δ.It is immediate by the last property that, if (s, h) ̸ ∈ S keep then W ⋆ h (s) ≤ 32ϵ unif . We next show that if (s, h) ∈ S keep , then this implies that W ⋆ h (s) ≥ ϵ unif . Let X be a random variable denoting the total number of samples we collect from (s, a, h) when rerunning all policies in Π js . Then by Markov's Inequality, by the above properties we have1 2 ≤ P[X ≥ N js /2] ≤ 2E[X] N js ≤ 2|Π js |W ⋆ h (s) N js = 8 • 2 js W ⋆ h (s).It follows thatW ⋆ h (s) ≥ 1 16 • 2 js ≥ 1 16 • 2 ⌈log 2 1 32ϵ unif ⌉ ≥ 1 32 • 2 log 2 1 32ϵ unif = ϵ unif .This completes the proof.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, confidence 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, or 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 or 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 a 96% CI, if the hypothesis of Normality of errors is not verified.• 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 of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce 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 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 of compute required for each of the individual experimental runs as well as 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 it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used tow π h (s) K . 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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: limitations: The authors have confronted the limitations in section 7.
paper_summary: paper_summary: The author investigate if estimating the difference in policies is sufficient in determining the best policy for contexual bandits and tabular RL. 
A (somewhat) practical algorithm is proposed to determine the number of samples needed without any unknown quantities.
strength_weakness: strength_weakness: - 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.
- In section 4.2,  it is difficult to see why the difference estimate has reduced variance
questions: questions: - In Lemma 1, what is the difference when $E^M[\tau]$ when compared to $E[\tau]$ on line 182?
- 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: limitations: No concerns.
paper_summary: paper_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.
strength_weakness: strength_weakness: - **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.
questions: 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?

- 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?

- 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: limitations: N/A.

Comments: comment: Thanks for your reply. I will keep my scores and think it would be a good paper to appear at Neurips.
Thank you for clarifying the points raised. I think that this paper is worth sharing with the NeuRIPS community, I will keep my score.
I appreciate the authors for their response and for the clarification. I will keep my decision as it.