The Power of Resets in Online Reinforcement Learning
Authors: Zakaria Mhammedi
Dylan J Foster
Alexander Rakhlin
Venue: NeurIPS 2024 spotlight (2024)
Keywords: Reinforcement learning
learning theory
generative model
simulator
coverability
Primary area: learning_theory
TL;DR: We show that online reinforcement learning with the power to reset to previously visited states unlocks new statistical guarantees that were previously out of reach.

Abstract: Simulators are a pervasive tool in reinforcement learning, but most existing algorithms cannot efficiently exploit simulator access -- particularly in high-dimensional domains that require general function approximation. We explore the power of simulators through online reinforcement learning with local simulator access (or, local planning), an RL protocol where the agent is allowed to reset to previously observed states and follow their dynamics during training. We use local simulator access to unlock new statistical guarantees that were previously out of reach:
- We show that MDPs with low coverability (Xie et al. 2023) -- a general structural condition that subsumes Block MDPs and Low-Rank MDPs -- can be learned in a sample-efficient fashion with only Q⋆-realizability (realizability of the optimal state-value function); existing online RL algorithms require significantly stronger representation conditions.
- As a consequence, we show that the notorious Exogenous Block MDP problem (Efroni et al. 2022) is tractable under local simulator access.
The results above are achieved through a computationally inefficient algorithm. We complement them with a more computationally efficient algorithm, RVFS (Recursive Value Function Search), which achieves provable sample complexity guarantees under a strengthened statistical assumption known as pushforward coverability. RVFS can be viewed as a principled, provable counterpart to a successful empirical paradigm that combines recursive search (e.g., MCTS) with value function approximation.

The Power of Resets in Online Reinforcement Learning
Zakaria Mhammedi Google Research mhanmedii@ooggle. com
Dylan J. Foster Microsoft Research dylanfoster&mi crosoft.comm
Alexander Rakhlin MIT rakhl makhlin@mit edu
Abstract
Simulators are pervasive tool in reinforcement learning, but most existing algo- rithms cannot efficiently exploit simulator access-particularyy in high-dimensions domains that require general function approximation. We explore the power of simulators through online reinforcement learning with local simulator access (or, local planning). an RL protocol where the agent allowed to reset to previously observed states and follow their dynamics during training. We use local simulator access to unlock new statistical guarantees that were previously out of reach:
1. We show that MDPs with low coverability [63]-a general structural con- dition that subsumes Block MDPs and Low-Rank MDPs-can be learned in a sample-efficient fashion with only Q" -realizzabily (realizability of the optimal state-value function); existing online RL algorithms require significantly stronger representation conditions.
2. As consequence, we show that the notorious Exogenous Block MDP problem [22] is tractable under local simulator access.
The results above are achieved through compurationall--inffficenn algorithm. We complement them with a more computationally efficient algorithm, RVFS (Recursive Value Function Search), which achieves provable sample complexity guarantees under strengthened statistical assumption known as pushforward coverability. RVFS can be viewed as principled, provable counterpart to successful empirical paradigm that combines recursive search (e.g., MCTS) with value function approximation.
Introduction
Simulators are a widely used tool in reinforcement learning. Many of the most well-known bench- marks for reinforcement learning research make use of simulators (Atari [9], MuJoCo [55], OpenAI Gym [11], DeepMind Control Suite [53]), and high-quality simulators are available for a wide range of real-world control tasks, including robotic control [45, 2]. autonomous vehicles [10, 6]. and game play- ing [51, 52]. Simulators also provide a useful abstraction for planning with a known or learned model, an important building block for many RL techniques [48]. Yet, in spite of the ubiquity of simulators, almost all existing research into algorithm online reinforcement learning (where only trajectory-based feedback is available), and does not take advantage of the extra information available through the simulator. Relatively little is known about the full power of RL with simulator access, either in terms of algorithmic principles fundamental limits.
and theoretical has focused on the
We explore the power of simulators through online reinforcement learning with local simulator access (RLLS for short), also known as local planning [57, 40, 3. 59, 65, 66). Here, the agent learns by repeatedly executing policies and observing the resulting trajectories (as in online RL), but allowed to reset to previously observed states and follow their dynamics during training.
Empirically, algorithms based on local simulators have received limited investigation, but with promising results. Notably, the Go-Explore algorithm [19, 20] uses local simulator access to achieve sfate-of-the-ee performance for Montezuma's Revenge difficult Atari game that requires systematic
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

exploration), beating the performance of the best agents trained with online RL [7, 27] by significant margin that has yet to be closed. The successful line of research on AlphaGo and successors [2,,52, 48] also uses local simulator access, albeit at test time in addition to training time.
These results suggest that developing improved algorithm design principles for RL with local simulator access could have significant practical implications, but current theoretical understanding of local simulators is limited. Recent work has shown that local simulator access has provable benefits for reinforcement learning with various types of linear function approximation [57, 40, 3, 65, 59], but essentially nothing is known for RL problems in large state spaces that demand general, potential neural function approximation. This leads us to ask: Can we develop algorithms for reinforcement learning with general f function approximation that provably benefit from local simulator access?
From an algorithm design perspective, perhaps the greatest challenge in using local simulators to speed up learning is understand which states are "informative" in the sense that we should prioritize revisiting them. Here, we are faced with a chicken-and-eg. problem: to understand which states to prioritize, we must explore and gather information, but it is unclear how to do so efficiently unless we already have way to understand which states are informative. It is natural to let function approximation guide us; to this end, recent research [40, 65, 59] on local simulators makes use of core-sets: small, adaptively chosen sets of informative state-action pairs designed to cover the feature space and enable efficient value function learning. Core-sets facilitate sample complexity guarantees for linear models that are not possible without local simulator access (e.g.. [40]). Yet, for general function caassss-prtticlaatt rich models like neural networks that do not readily support extrapolation derrapoaaion-ddefiinng suitable notion of core-set is challenging. Consequently, existing techniques have yet to meaningfully leverage local simulator access beyond the linear regime.
RL with
1.1 Contributions
We show that local simulator access unlocks new guarantees for online RL with general value function approximation-staaiiiicn and computational-taat were previously out of reach.
Sample-efficient learning. We show that MDPs with low coverability [63]-a general structural condition that subsumes Block MDPs and Low-Rank MDPs can be learned in a sample-efficient fashion with only Q" -e-rralizaability (that is, realizability for the optimal state-action value function). This is achieved through new algorithm, SimGolf, that augments the principle of global optimism with local simulator access, and improves upon the best existing guarantees for the fully online RL setting, which require significantly stronger representation conditions. As a consequence, we show for the first time that the notoriously challenging Exogenous Block MDP (ExBMDP) problem [22, 21] is tractable in its most general form under local simulator access.
Practical, computationally efficient learning. Our results above are achieved through computationally inefficient algorithm. We complement them with a practical and computationally efficient algorithm, RVFS ("Recursive Value Function Search"), which achieves sample-efficient learning guarantees with general value function approximation under a strengthened, yet novel, statistical assumption known pushforward coverability [62]. Assuming either i) realizability of the optimal vtate-value function V* and a state-action gap or ii) realizability of V for all म, RVFS achieves polynomial sample complexity in computationally efficient fashion, and leads to guarantees for a new class of Exogenous Block MDPs with weakly correlated exogenous noise. RVFS explores by building core-sets with novel value function function-guided scheme, and can be viewed as a principled counterpart to algorithms including MCTS and AlphaZero [51, 52, 19, 20, 66), that combine recursive search with value function approximation. Compared to these approaches, RVFS is designed to provably address stochastic environments and distribution shift.
Paper organization. Section 2 introduces the local simulator framework. Section 3 presents main sample complexity guarantees, and Section 4 gives computationally efficient algorithms. All proof's are deferred to the appendix.
2 Setup: Reinforcement Learning with Local Simulator Access
We consider an episodic reinforcement learning setting. A Markov Decision Process (MDP) is tuple M = (X, A, R, H). where X' is a (large/potentially infinite) state space, A is the action space (we abbreviate = [Al), H E N is the horizon, R { f is the reward function (where R2 : X x A + [0, 1)) and 7 = ) h-o is the transition distribution (where Tи : X x A - A(x)), with the conven-
tion that (- Ø) is the initial state distribution. A policy is a sequence of functions = {T : X
2

---

A(A))E we use IIs to denote the set of all such functions. When a policy is executed, it generates a trajectory (3), a1. ri......... ( TT.) via the process an TT ( rh R2 (zp, an). 2h+1 (. æn. ),), initialized from 21 ~ T- Ø) (we use 1++1 to denote terminal state with zero reward). We write [P and [=][-] to denote the law and expectation under this process.
For a policy n. (TT = ET [> ru] denotes expected reward, and the value functions are given by V (a) E [* Ty 2 = =]] and (T a) = E [- Tw wr, I, ag. = a]. We denote by and write Q :- Q" and V == V**
nt the optimal deterministic policy that maximizes Q" and
Online reinforcement learning with a local simulator. In the standard online reinforcement learning framework, the learner repeatedly interacts with an (unknown) MDP by executing a policy and observing the resulting trajectory, with the goal of maximizing the total reward. Formally, for each episode e [opp the learner selects policy x(1) = (n/,² Jh executes it in the underlying MDP MM and observes the trajectory {(af) a 2)) After all Nopisodes episodes conclude, the learner produces policy π E II; with the goal of minimizing the risk given by E[J(TT) - J()].
!
In online RL. with local simulator access, or RLLS, [57, 40, 65, 59, 66), we augment the online RL protocol as follows: At each episode E [N]. instead of starting from a random initial state 31 ~ T- 2). the agent can reset the MDP to any layer & E [ and any state 2i previously encountered, and proceed with new episode starting from Th. As in the online RL protocol, the goal is to produce a policy 7 E Ils such that (1)(x=)) (xx) (
with as few episodes of interaction as possible; our main results take Nepisodes poly(C,E for suitable problem parameter C.
Executable versus non-executable policies. We focus on learning policies that can be executed without access to a local simulator (in other words, the local simulator used train time, but not test time). Some recent work using local simulators for RL with linear function approximation [57] considers a more permissive setting where the final policy produced by the learner can be non-executable; our function approximation requirements can be slightly relaxed in this case.
Definition 2.1 (Non-executable policy). We refer to a policy π for which computing π (=)) E ((A) for any Z É X' requires local simulator queries
non-executable policy with sample complexity n.
Additional notation. For any m, n E N, we denote by [m_.n]] the integer interval [m.....n) n).. We also let [n] := [1.. We refer to scalar c > 0 an absolute constant indicate that it independent of all problem parameters and use Ō-) denote a bound up to factors poly- logarithmic in parameters appearing in the expression. We define Tunif IIs as the random policy that selects actions in A uniformly. We define the occupancy measure for policy π via dr, (x. = [x)
as a). For functions 9 X' x A + I and f : X + R, we de- fine Bellman backup operators by [2] a) [.[r, + max.'eA g a') xy = x. aj = a] and Pr[f((r, a)= E[r, + (2x-11 æ = 2, a₁ a]. For stochastic policy E HI, we will occasion- ally use the bold notation (2) as shorthand for the random variable an ~ T) E A(A). For a function f A + R, we write a' arg max f(a) to denote the action that maximizes f. If there are ties, we break them by picking the action with the smallest index; we assume without loss of generality that actions in A are index from I|.
3 New Sample-Efficiee
Learning Guarantees via Local Simulators
This section presents our most powerful results for RLLS. We present a new algorithm for learning with local simulator access, SimGolf (Section 3.1), and show that it enables sample-efficient RL for MDPs with low coverability [63] using only Q' preaaiizaability (Section 3.2). We then give implications for the Exogenous Block MDP problem (Section 3.3).
Function approximation setup and coverability. To achieve sample complexity guarantees for online reinforcement learning that are suitable for large, high- nigh-dimensional state spaces, we appeal to value function approximation. We assume access function class Q c (X Ax [H] [0, H])
that contains the optimal state-action value function Q"; we define On = (Q Q e Q).
Assumption 3.1 (Q' -realizabbility For all h [H], we have Qi Qh-
Q' p'rrealizability is widely viewed as minimal representation condition for online RL [61, 17, 16, 39, 58, 56). The class Q encodes the learner's prior knowledge about the MDP, and can be parameterized by rich function approximators like neural networks. We assume for simplicity of exposition that Q
3

---

and II are finite, and aim for sample complexity guarantees scaling with logl Q and log][]]; extending our results to infinite classes via standard uniform convergence arguments straightforward.
Coverability. Beyond representation conditions like realizabilitty online RL algorithms require structural conditions that limit the extent to which deliberately designed algorithms can be surprised by substantially new state distributions. We focus on structural condition known as coverability [63], which is inspired by connections between online and offline RL.
Assumption 3.2. The coverability coefficient is Ceov == [H] inf (EEA(EAA)) rells
di
Coverability is an intrinsic strutural property of the underlying MDP. Examples of MDP families with low coverability include (Exogenous) Block MDPs, which have Ccov S |S]|,A), where S is the latent state space [63], and Low-Rank MDPs, which have Coov d[Ai, where d is the feature dimension [29]; importantly, these settings exhibit high- sigh-dimensional state spaces and require nonlinear function approximation. As in prior work [63, 4], our algorithms require no prior knowledge of the distribution 14 that achieves the minimum in Assumption 3.2.
3.1 Algorithm
Our main algorithm, SimGolf, is displayed in Algorithm 1. The algorithm is a variant of the GOLF method of Jin et al. [32], Xie et al. [63] with novel adaptations to exploit the availability of local simulator. Like GOLF, SimGolf explores using the principle of global optimisim: At each iteration i [[N]. maintains a confidence set (or, version space) Q Q of candidate value functions with low squared Bellman error under the data collected so far, and chooses new exploration policy x(") by picking the most "optimistic" value function in this set. As the algorithm gathers more data, the confidence set shrinks, leaving only near-optimal policies.
The main novelty in SimGolf arises in the data collection strategy and design of confidence sets. Like GOLF, SimGolf f algorithm constructs the confidence set Q Q such that all value functions g e Q have small squared Bellman error:
Σ (9% (20n, an) - Th Th (( am) x logl 2), ict
Vh [H].
Due to the presence of the Bellman backup Tal [h[+++]] in Eq. (1), naively estimating squared Bellman error leads to the notorious double sampling problem. To avoid this, the approach taken with GOLF and related work [67, 32] is to adapt certain de-biasing technique to remove double sampling bias, but this requires access to value function class that satisfies Bellman completeness, a representation significantly more restrictive than realizability (e.g.. Foster et [26]).
The idea behind SimGolf is to use local simulator access to directly produce high-quality estimates for the Bellman backup function Ta [9h+1] in Eq. (1). In particular, for given state-action pair aI, X' x A, we can estimate the Bellman backup Tx[9h+ [Ix a) for all functions g Q simultaneously by collecting K next-state transitions , (KK) iid. Ta x. a) h+1
in R2 (z. a), then taking the empirical mean: [n]gh++][<, a) " Line 8 of SimGolf uses this technique to directly estimate the Bellman residual backup under trajectory gathered with π²), sidesteppni the double sampling problem and removing the need for Bellman completeness. We suspect this technique (estimation with respect to squared Bellman error using local simulator access) may find broader use.
Lid. and K rewards " ......, ((()
1 1 max4'sA gh-1 1 R
3.2 Main Result
We now state the main guarantee for SimGolf and discuss some of its implications.
Theorem 3.1 (Main guarantee for SimGolf). Let e, 5 10,1) be given and suppose Assumption 3. (Q' -eeaiiizzabil) and Assumption 3.2 (coverability) hold with Ccov > 0. Then the policy के produced by SimGolf( Q, Ccov, e, 5) (Algorithm 1) has J(TT)== [[]( S E with probability at least The total sample complexity in the RLLS framework is bounded by Ö(H$C2 log([2//6) =4).
This result (whose proof is in Appendix E) shows that under only Q' rralizaability and coverability, SimGolf learns an e-optimal policy with polynomial sample complexity, significantly relaxing the representation assumptions (Bellman completeness, weight function realizability) required by prior algorithms for coverability [63, 4]. This is the first instance are aware of where local simulator

---

Algorithm SimGolf: Global Optimism via Local Simulator Access
1: input: Value function class 2, coverability Ceav 0, suboptimality e 0, and confidence ó 0.
2: Set N - -GHHCCec, Sstat + 16log(2HN()6 3 23sttt, and K SN
Detat
3: initialize: 2 + Q
4: for iteration ( 11,,....,.. do
5: Select g arg mrgga Σ m (
6: For each h E [H] and x X, define ni (x:) E arg max Ih (I)
7: Execute T² for episode and observe 70)) := (at aj (2) ..... (a azj (1)
8: For h [H], draw K independent samples Th11 T ( x (1)
Ra x
9:
Compute confidence set:
(44)
g Q: Σ (a a²²)
(r
Σ
(e.1)
(1ik) .n)) _ 3, vh {m]
max gh-1
K k=
and
10: return: न == unif(( ((,))
access unlocks sample complexity guarantees for reinforcement learning with nonlinear function approximation that were previously out of reach; perhaps the most important technical idea here is our approach combining global optimism with local simulator access, in contrast greedy layer-by-layer schemes used in prior work on local simulators (with the exception of Weisz et al. [57]). In particular, we suspect that the idea of performing estimation with respect to squared Bellman error directly using local simulator access may find broader use beyond coverability. Improving the polynomial dependence on problem parameters an interesting question for future work.
A conjecture. By analogy to results in offline reinforcement learning, where Q' Q"-realizability and concentrability (the offline counterpart to coverability) alone are known to insufficient for sample-efficient learning [12, 26], we conjecture that Q" Q'-realizability and coverability alone are not sufficient for polynomial sample complexity vanilla online RI.. If true, this would imply a new separation between online RL with and without local simulators.
3.3 Implications for Exogenous Block MDPs
We now apply SimGolf and Theorem 3.1 to the Exogenous Block MDP (ExBMDP) problem [22, 21, 38, 30). a challenging rich-observation reinforcement learning setting in which the observed states 24 are high-dimensional, while the underlying dynamics of the system are low-dimensional, yet confounded by temporally correlated exogenous noise.
Formally, an Exogenous Block MDP M (,..S,E.HH,TT,R. g) is defined by a latent state space and an observation space. We begin with the latent state space. Starting from an initial endogenous state 81 ε S and exogenous state E1 E, the latent state zn (sh,En evolves for h e [H] via 8h+1 Trnddo (- 8h, adopt the convention that $1 ~ -ooddo (- Ø) and E ~ T (- Ø). Note that only the endogenous state is causally influenced by the action. The latent state is not observed; instead, at each step h. the agent receives an observation 2 X generated via' Fy " Es),En). where ghbs S = + X is the emission function. We assume the endogenous latent space and action space are finite, and define S = [S] and A [A]. However, the exogenous state space E and observation space X' may be arbitrarily large or infinite, with [3]. |2' >> |S).2
(+1 an.) and Ex+1 Tex0 (- (a). where a e A is the agent's 's action at layer h;; we
The final property of the EXBMDP model is decodability, which asserts the existence a decoder such that の. X - S such that d. (xx) = a.s. for all h & [f]] with ws - (sn. Ex),. Informally, decodability ensures the existence of an (unknown to the learner) mapping that allows one to perfectly recover the endogenous latent state from observations. In addition to decodability, we assume the rewards in the ExBMDP are endogenous; that is, the reward distribution R₁ ( (I), an) only
'A more standard formulation [22, 21, 38, 30] assumes that observations are generated via ay, qu (8h En): where gu (-s+) conditional distribution with the decodability property. This is equivalent to æi, gi. (s E..) randomness in the emission process can he included in the exogenous state w.l.o.g.
"To simplify presentation, we assume that 3\t and X' are countable; our results trivially extend to the case where the corresponding variables continuous with an appropriate measure- thheoreet treatment.
5

---

depends on the observations (æx) through the corresponding latent states (Ø" (x)) 8%.. To enable sample-efficient learning, we assume access to a decoder class & that contains Φ", as in prior work.
Assumption 3.3 (Decoder realizability). We have access to a decoder class & such that ø' &.
Applying SimGolf and Theorem 3.1. To apply Theorem 3.1 to the ExBMDP problem, we need to verify that Q" -realizzaaiiliyy and coverability hold. Realizability is straightforward consequence of decodability (Lemma D.1 in Part II of the appendix). For coverability, Xie al. [63] show that ExBMDPs have Ceov 5 SA under decodability, in spite of the time-correlated exogenous noise process (Er) and potentially infinite observation space X' (interestingly. coverability essentially the only useful structural property that ExBMDPs are known to satisfy, which is our primary motivation for studying it). This leads to the following corollary of Theorem 3.1.
Corollary 3.1 (SimGolf for ExBMDPs), Consider the ExBMDP setting. Suppose that Assumption 3.3 holds, and let Q be constructed as in Lemma D.1 of Part II. Then for any E, 8 (0, 1), the policy के = SimGolf( Q, 5,, has J ) - (R) S E with probability at least 1 - 6. The total sample complexity in the RLLS framework is N = Ö(H*(( A 1l
This shows for the first time that general ExBMDPs are learnable with local simulator access. Prior to this work, online RL algorithms for ExBMDPs required either (i) deterministic latent dynamics [22], or (ii) factored emission structure [21]. Xie al. [63] observed that ExBMDPs admit low coverability, but their algorithm requires Bellman completeness, which is not satisfied by ExBMDPs (see Islam al. [30]). See Appendix for more discussion.
4 Computationally Efficient Learning with Local Simulators
Our result in Section 3 show that local simulator access facilitates sample-efficient learning in MDPs with low coverability, challenging setting that was previously out of reach. However, our algorithm SimGolf is computationally-innfii -nieenlllilefiiiiennt because it relies on global optimism, a drawback found in most prior work on RL with general function approximation [31, 32, 18]. remains an open question whether any form of global optimism can be implemented efficiently, and some variants have provable barriers to efficient implementation [14].
To address this drawback, in this section we present a new algorithm, RVFS (Recursive Value Function Search; Algorithm 5), which requires stronger versions of the coverability and realizability assumptions in Section 3, but is computationally efficient in the sense that it reduces to convex optimization over the state-value function class V. RVFS makes use of sophisticated recursive exploration scheme based on core-sets, sidestepping the need for global optimism.
4.1 Function Approximation and Statistical Assumptions
To begin, we require the following strengthening of the coverability assumption in Assumption 3.2. Assumption 4.1 (Pushforward coverability). The pushforward coverability coefficient Cpush > is
given by Cpush m [i] (nx))))(X)) (5. xAxX
(x(2k)
Pushforward coverability is inspired by the pushforward concentrability condition used in offline RL by [62, 26). Concrete examples include, (i) Block MDPs with latent space S, which admit Cpush 1 (S], (ii) Low-Rank MDPs in dimension d, which admit Cpush d [62], and (iii) Exogenous Block MDPs for which the exogenous noise process satisfies a weak correlation condition that we introduce in Appendix B. Note that Coow I Al. but the converse is not true in general.
Instead of action value function approximation as in SimGolf, in this section we make use of state value function class V c (X' x [H] + [0. H]). but require somewhat stronger representation conditions than in Section 3. We consider two complementary setups:
Setup I: Assumptions 4.2 and 4.3 (V*/=" / and Assumption 4.4 (A (A-gap) hold.
Setup II: Assumption 4.5 (V (V"-realizabiility) and Assumption 4.6 (1-realizability) hold.
We describe these assumptions in more detail below.
Function approximation setup I. First, instead of Q' realliiizability. consider the weaker V*- realizability [31, (7, 57,
Assumption 4.2 (V* -realizability) For all h [H], we have V e Vn.

---

Under V r"-rralizabilityy our algorithm learns a near-optimal policy, but the policy is non-executable (cf. Definition 2.1); this property shared by prior work on local simulator access with value function realizability [57]. To produce executable policies, we additionally require access to policy class c ITş containing r²;; we define 1 (nA T IT).
Assumption 4.3 (x* iaa-raalizabillit). The policy class II contains the optimal policy n².
V y"-realizability (Assumption 4.2) and π²" r'-realizability (Assumption 4.3) are both implied by Q' o"rrealizability, and hence are weaker. However, we also assume the optimal Q-function admits constant gap (this makes the representation conditions for Setup I incomparable to Assumption 3.1).
Assumption 4.4 (A- (a-G..). The optimal action (1) is unique, and there exists A> > 0 such that for all h ε [)) E X, and a
(x)), Q (z., T (x)) (z,(),)+ A.
This condition has been used in a many prior works on computationally efficient RL with function approximation [16, 17, 24, 56].
Function approximation setup II. We also provide guarantees under the assumption that the class satisfies all-policy realizability [59, 65, 60] in the sense that V e for all x TTs.
Assumption 4.5 (VT-realizabilltt). The class V VI-H has VØ, e Vn, for all a IIs and h [H].
This assumption will be sufficient leam non-executable policy, but to learn executable policies we require an analogous strengthening of Assumption 4.5.
Assumption 4.6 (T-realizabillty). For all E Ils, we have that x + arg argmax PA[V 1...).a) II.
This assumption has been used by a number of prior works on computationally efficient RL [8, 44]. Assumptions 4.5 and 4.6 are both implied by the slightly simpler-to-staz assumption of -e-realizability [59, 65, 60], which asserts access to a class Q that contains Q for all π e IIs.
4.2 Algorithm
For case of exposition, we defer the full version of our algorithm, RVFS (Algorithm 5), Appendix F and present a simplified version here (Algorithm 2). The algorithms are nearly identical, except that the simplified version assumes that certain quantities of interest (e.g., Bellman backups) can be computed exactly, while the full version (provably) approximates them from samples.
RVFS maintains a value function estimator V = VILH that aims to approximate the optimal value function Vish well as core sets Cı,..., CH of state-action pairs that are used to perform estimation and guide exploration. At high level, RVFS alternates between (i) fitting the value function P,, for given layer / E [F] based on Monte-Carlo rollouts, and (ii) using the core-sets to test whether the current value function estimates V remain accurate as the roll-in policy induced by Vn, changes.
In more detail, RVFS is based on recursion across the layers h [. When invoked for layer h with value function estimates Vh+1- and core-sets Ca....,Ca CH. RVFS,, performs two steps:
1. For each state-action pair (Eh-1,9h-1) E Ch. the algorithm gathers Ntest trajectories by rolling out from (In-1, with the greedy policy (x) e arg max,e, Pe Pr[Ve, [z, a) that optimizes the estimated value function; in the full version of RVFS (see Algorithm 5), we estimate the bellman backup Pe[Ve-1](r:, a) using the local simulator. For all states Ti-1
encountered during this process, the algorithm checks whether [B]V<(>))- - V,, 0z-1 1t-1, az-1 at-1] s for all az-1 E A using test based on (im- plicitly maintained) confidence sets. If the test fails, this indicates that distribution shift has occurred, and the algorithm adds the pair (x)-1, to Ct and recurses on layer E via RVFS.-
2. If all tests above pass, this means that Vi..,...,, VH are accurate, and distribution shift has occurred. In this case, the algorithm fits V, by collecting Monte- Carlo rollouts from all state-action pairs in the core-set C₁ with के (x) arg ma Pe [Ve.a] a) (cf. Line 16), and returns.
When the tests in Item succeed for all E [H]], the algorithm returns the estimated value functions Viani in this case, the greedy policy (x) arg max a Pf[ 1 a) is guaranteed to be near
'Informally, C. represents a collection state-action pairs (#1-1, at layer 1 for which we want [[[ (wx) Vi, (æx)) 2 2h-1, a an-1] for some small 0.
7

---

Algorithm 2 RVFS4: Recursive Value Function Search (Informal version of Algorithm 5)
parameters: Value function class V, suboptimality (0, 1), confidence ò e (0, 1). 2: input: Level h [O.. HJ, value functions Vh-1:H1 confidence sets D core-sets Cre
3: Initialize parameters M, .Ntest, Nreg. Ereg. and 3 (see Algorithm for parameter settings).
/* Test the fit for the estimated value functions VALI at future layers. */
4: for (Ih-1, 6 Cn and & H.,..,, do
5: for n mmmm11.-. 1,.., Ntsst do
6: Draw 24, Th-1 (- Th-1 0h-1), then draw # by rolling out with The where
Vr E [ (+(+) E max Pr Pr(
(2)
7:
for a--1 E A do
/* Test fit; if test fails, re-fit value functions Viane up to layer f. */ if sup (Pte- (1211 t then
8:
9:
C. + b7...,.,,h do RVFS, (Vr+,:VV
10:
11:
(V~H,
12:
go line
13:
if h- 1 0 then return: (Vi.5.'s5.)).
1* Re-fit Vy and build new confidence set. */
14: for (Ih-1, (b-1) E Cn do R/ [Et Te mn can be estimated using local simulator.
15: Set Dr, (Ih-1,
Ø. For :o.i= I,..., Nreg. sample 2h ~ 'Th-1( (- 0h-1) and update
(z 4--1 Dí (2 ah-1) {(x,, E [Σ Ty [z,])):
16: Let VA arg min fe E(a, 1) (zn.m)) (11-1 (f(x)) - v2
17: Compute value function confidence set:
Dn = 7 (EV
Σ (#6-1,0h-1 DECs Nreg (znr)EDa (2h-1;0h))
Σ
(P)(Tn) ((xn)) s &
18: return (Viar, PhattCCen1
optimal. The full version of RVFS in Algorithm 5 uses local simulator access estimate the Bellman backups Pn [n[Vn=> [[>-1][2; a) for different state-action pairs (x, a). These backups are used to (i) compute actions of the greedy policy that maximizes ViSH via (e.g.. Eq. (2)); (ii) generate trajectories by rolling out from state-action pairs in the core-sets (Line 6); and (iii) perform the test in Item (Line 8).
RVFS is inspired by the DMQ algorithm [16, 56] originally introduced in the context of online re- inforcement learning with linearly realizable Q* RVFS incorporates local simulator access (most critically, via core-set construction) to allow for general nonlinear function approximation with- out restrictive statistical assumptions. Prior algorithms for RLLS have used core-sets of state-action pairs in similar fashion [40, 65, 59], but in way that is tailored to linear function approximation.
In what follows, we discuss various features the algorithm in greater detail.
Bellman backup policies. Since RVFS works with state value functions instead of state-action value functions, we need a way to extract policies from the former. The most natural way to extract a policy from estimated value functions VL E V is as follows: for all h E [H], define Rn (x)+ E arg max PA [V a). In reality, we do not have access to Pa, [V++i](r, directly, so the full version of RVFS (Algorithm 5) estimates this quantity on the fly using the local simu- lator using the following scheme (Algorithm 7 in Appendix F): Given a state for each a, we sample K rewards r4. ~ (x, a) and next-state transitions 0++1 T- a.,a), then approximate Pa Pr[Vn=1](z, a) by the empirical mean. We remark that the use of these Bellman backup policies is actually crucial in the analysis for RVFS; even if we were to work with estimated state-action value functions Q1: instead, our analysis would require executing the Bellman backup policies Tn (z) arg max QhlQn-1l [z, a) (instead of naively using 7. (z) arg max Q2(2,a)).

---

Invoking the algorithm. The base invocation of RVFS takes the form
VI-F RVFSo Vi.sr arbitrary, Vi.Hr = Mu: = (0) ;,,,),
Whenever this call returns, the greedy policy induced by Vi is guaranteed to be near-optimal. Naively, the approximate Bellman backup policy induced by VI-H (described above) is non-executable. and must be computed by invoking the local simulator. To provide an end-to-end guarantee to learn an executable policy, we give an outer-level algorithm, RVFS. bc (Algorithm 6, deferred to Appendix for space), which invokes RVFSu, then extracts an executable policy from VL us- ing behavior cloning. Subsequent recursive calls to RVFS take the form (Vi.H, VICH Cn:H) RVFS,, (Vi+1.H. Vh+ Cte:; V. E. The arguments here are: Importantly, the confidence sets 1h+1: do not need to be explicitly maintained, and can be used implicitly whenever regression oracle for the value function class is available (discussed below).
Remark 4.1 (Oracle-eflicieney). RVFS is computationally efficient in the sense that it reduces to convex optimization over the value function class V. In particular, the only computationally intensive steps in the algorithm are (i) the regression step in Line 16, and (ii) the test Line involving the confidence set Ve- For the latter, we do not explicitly need to maintain Dr, as the optimization problem over this set in Line 8 (for the full version of RVFS in Algorithm 5) reduces solving arg ev Σi_ V(I Σi- (V((")) y )² } for dataset {x!x) H ".y""" )) This convex optimization problem in function space, and in particular can be implemented in a provably efficient fashion whenever V is linearly parameterized. We expect that the problem can also be reduced to a square loss regression by adapting the techniques in Krishnamurthy el al. [37], Foster el al. [23], but we do not pursue this here.
4.3 Main Result
We present the main guarantee for RVFS under the function approximation assumptions in Section 4.1.
Theorem 4.1 (Main guarantee for RVFS). Let E, d' E (0,1) be given, and suppose that Assumption 4.1 (pushforward coverability) holds with Coush O. Further, suppose that one the following holds:
Setup I: Assumptions 4.2 and 4.3 (V* -realiiizabillty) and Assumption 4.4 (A-gap) hold,
and S 6H A.
Setup II: Assumption 4.5 (V" (V*-realizabillity and Assumption 4.6 (T-realizability) hold.
Then, WWFS.bc(I1 8, (Algorithm 6) returns policy R1. such that J(x") J(f1HH 2z with probability at least - and has total sample complexity bounded by
δ ÖC 22 e
Furthermore, the algorithm makes at most poly(C (ppush H, A,A, calls to the convex optimization oracle over value function space described in Remark 1.
Theorem 4.1 shows for the first time that sample- and computationally-effcciei RL with local simula- tor access is possible under pushforward coverability. In particular, RVFS is the first computationally efficient algorithm for RL with local simulator access that supports nonlinear function approximation. The assumptions in Theorem 4.1, while stronger than those in Section 3, are not known enable sample-efficient RL without simulator access. Nonetheless, understanding whether RVFS can be strengthened to support general coverability or weaker function approximation is important open problem. See Appendix H.1 for an overview of the analysis; we remark (Appendix I.1) that the result actually proven under slightly weaker assumptions than those Setup I/Setup II.
Connection to empirical algorithms. RVFS bears some similarity to Monte-Carlo Tree Search (MCTS) [13, 35] and AlphaZero [52], which perform planning with local simulator. Informally, MCTS can be viewed as a form of breadth-firs search over the state space (where each node represents a state at a given layer), and AlphaZero a particular instantiation of MCTS that leverages V-value function approximation to allow for generalization across states. Compared to RVFS, MCTS and AlphaZero perform exploration via simple bandit-style heuristics, and are not explicitly designed to handle distribution shifts that arise in settings where actions have long-term downstream effects. What is more, MCTS requires finite states to iterate over all possible child nodes of each state, making it inapplicable in environments with continuous states. RVFS may be viewed as a provable counterpart

---

that can handle continuous states and uses function approximation to address distribution shift in principled fashion (in particular, through the use of confidence sets and the test in Line 14).
Applying RVFS to Exogenous Block MDPs. ExBMDPs satisfy coverability (Assumption 3.2), but do not satisfy the pushforward coverability assumption (Assumption 4.1) in general. However, it turns out that ExBMDPs do satisfy pushforward coverability when the exogenous noise process is weakly correlated across time, a new statistical assumption we refer the weak correlatton condition. In Appendix B (Theorem B.I), we give a variant of RVFS for ExBMDPs that succeeds under (i) weak correlation, and (ii) decoder realizability, sidestepping the need for the A-gap or V=-realizability.
Discussion and Future Work
In this paper, we demonstrated that resets can substantially expand the range of reinforcement learning (RL) settings that are tractable, both statistically and computationally. Our practical algorithm, RVFS, provides principled counterpart to MCTS by supporting continuous state spaces and offering provable guarantees, setting it apart from traditional MCTS. Statistically, our results extend to MDPs with a finite Sequential Estimation Coefficient (SEC) [63], capturing a broader class MDPs beyond those with finite soverbblity-cmncooaasingn low Bellman Eluder MDPs [32] and MDPs with finite bilinear rank [18]. Although not formally developed here, is possible to generalize mush-forward coverability and our analysis to encompass range of linear function approximation settings (57, 40, 3, 59, 65, 66], thereby recovering known positive results under local access in these settings.
While our focus has been on theoretical contributions- antributions--anllyinng the sample and computational complexity of RL with access to a local simulator-this work also raises promising empirical questions. We are particularly interested in exploring these questions in future work, aiming to bridge these theoretical advances with empirical validation in practical RL settings.
'We note in passing that in the context of tree search, the pushforward coverability assumption (Assump- tion 4.1) may be viewed the stochastic analogue of branching factor.
10

---

References
[1] A. Agarwal, Hsu, S. Kale, J. Langford, I.. Li, and Schapire. Taming the monster: fast and simple algorithm for contextual bandits. In International Conference on Machine Learning. pages 1638-1646, 2014.
[2] I. Akkaya, M. Andrychowicz, M. Chociej, M. Litwin, B. McGrew, A. Petron, A. Paino, M. Plappert, G. Powell, R. Ribas, et al. Solving rubik's ' cube with a robot hand. arXiv preprint arXiv:1910.07113, 2019.
[3] Amortila, N. Jiang, D. Madeka, and D. P. Foster. A few expert queries suffices for sample- efficient with resets and linear value approximation. Advances in Neural Information Process- ing Systems, 35:29637-29648 2022.
[4] Amortila, D. Foster, N. Jiang. Sekhari, and T. Xie. Harnessing density ratios for online reinforcement learning, International Conference on Learning Representations (ICLR), 2024.
[5] Amortila, J. Foster, and A. Krishnamurthy. Scalable online exploration via coverability. arXiv preprini arXiv:2403.0657/ 2024.
[6] Aradi. Survey deep reinforcement learning for motion planning of autonomous vehicles.
IEEE Transactions Intelligent Transportation Systems, 23(2):740-759, 2020.
[7] A. P. Badia, B. Piot, S. Kapturowski, P. Sprechmann, A. Vitvitskyi, Z. D. Guo, and C. Blundell. Agent57: Outperforming the atari human benchmark. In International conference on machine learning, pages 507-517. PMLR, 2020.
[8] Bagnell, M. Kakade, J. Schneider, and A. Ng. Policy search by dynamic programming. Advances in neural information processing systems, 16, 2003.
(9] M. Bellemare, J. Veness, and M. Bowling. Investigating contingency awareness using atari 2600 games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 26, pages 864-871, 2012.
[10] M. Bojarski. D. Del Testa, D. Dworakowski, B. Firner, B. Flepp, P. Goyal, L. D. Jackel, M. Monfort, U. Muller, J. Zhang, et al. End to end learning for self-driving cars. arXiv preprint 160v: 2016.
[11] G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, Tang, and W. Zaremba. Openai gym. arXiv preprint
2016.
[12] J. Chen and N. Jiang. Information-theoreiic considerations in batch reinforcement learning, In International Conference on Machine Learning, pages 1042-1051. PMLR, 2019.
[13] R. Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In Interna- tional conference on computers and games, pages 72-83. Springer, 2006.
[14] C. Dann, N. Jiang, A. Krishnamurthy, A. Agarwal, J. Langford, and R. E. Schapire. On oracle- efficient PAC RL with rich observations. In Advances in neural information processing systems, pages 1422-133, 2018.
[15] S. Du, A. Krishnamurthy, N. Jiang, A. Agarwal, M. Dudik, and J. Langford. Provably efficient RL with rich observations via latent state decoding. In International Conference Machine Learning, pages 1665-1674. PMLR, 2019.
[16] S. S. Du, Y. Luo, R. Wang, and Zhang. Provably efficient Q-learning with function ap- proximation via distribution shift error checking oracle. In Advances in Neural Information Processing Systems, pages 8060-80700 8070, 2019.
[17] S. S. Du, S. M. Kakade, R. Wang, and L. F. Yang. Is a good representation sufficient for sample efficient reinforcement learning? International Conference on Learning Representations, 2020.
11

---

[18] S. S. Du, S. M. Kakade. J. D. Lee, S. Lovett, G. Mahajan, W. Sun, and R. Wang. Bilinear classes: A structural framework for provable generalization RL. International Conference on Machine Learning, 2021.
[19] A. Ecoffet, J. Huizinga, J. Lehman, K. O. Stanley, and J. Clune. Go-explore: new approach for hard-exploration problems. arXiv preprint arXiv:1901.19990 2019.
[20] A. Ecoffet, J. Huizinga, J. Lehman, K. O. Stanley, and J. Clune. First return, then explore. Nature, 590(78477:580-556, 2021.
[21] Y. Efroni, D. J. Foster, D. Misra, Krishnamurthy, and Langford. Sample-efficient reinforce- ment learning in the presence of exogenous information. In Conference Learning Theory, pages 5062-5127. PMLR, 2022.
[22] Y. Efroni, D. Misra, A. Krishnamurthy, A. Agarwal, and J. Langford. Provably filtering exogenous distractors using multistep inverse dynamics. In International Conference on Learning Representations, 2022.
[23] D. J. Foster, A. Agarwal, M. Dudík, H. Luo, and R. E. Schapire. Practical contextual bandits with regression oracles. International Conference on Machine Learning, 2018.
[24] D. J. Foster, A. Rakhlin, D. Simchi-Levi, and Y. Xu. Instance-dependen complexity of contextual bandits and reinforcement learning: A disagreeeeent-basee perspective. Conference on Learning Theory (COLT), 2020.
[25] D. J. Foster, S. M. Kakade, J. Qian, and A. Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.13452 2021.
[26] D. Foster, A. Krishnamurthy, D. Simchi-Levi, and Y. Xu. Offline reinforcement learning: Fundamental barriers for value function approximation. In Conference on Learning Theory, pages 3489-3489. PMLR, 2022.
[27] Z. Guo, S. Thakoor, M. Pislar, B. Avila Pires, F. Altché, C. Tallec, A. Saade, D. Calandriello, J.-B. Grill, Y. Tang, al. Byol-explore: Exploration by bootstrapped prediction. Advances in neural information processing systems, 1855-318700 2022.
[28] W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13 1963.
[29] A. Huang. J. Chen, and N. Jiang. Reinforcement learning in low-rank mdps with density features. International Conference Machine Learning (ICML), 2023.
[30] R. Islam, M. Tomar, A. Lamb, Y. Efroni, H. Zang, Didolkar, D. Misra. X. Li, H. van Seijen, R. T. d. Combes, et al. Agent-controller representations: Principled offline rl with rich exogenous information. International Conference on Machine Learning (ICML), 2023.
[31] N. Jiang, A. Krishnamurthy, A. Agarwal, Langford, and R. E. Schapire. Contextual decision processes with low Bellman rank are PAC-lcarnable. In International Conference on Machine Learning, pages 1704-1713, 2017.
[32] C. Jin, Q. Liu, and S. Miryoosefi. Bellman eluder dimension: New rich classes of RL problems, and sample-efficiet algorithms. Neural Information Processing Systems, 2021.
[33] S. M. Kakade. On the sample complexity of reinforcement learning. University of London, University College London (United Kingdom), 2003.
[34] M. Kearns and S. Singh. Finite-samae sample convergence rates for q-learning and indirect algorithms. Advances in neural information processing systems, 11, 1998.
[35] L. Kocsis and C. Szepesvári. Bandit based monte-carlo planning. In European conference on machine learning, pages 282-293. Springer, 2006.
[36] A. Krishnamurthy, A. Agarwal, and J. Langford. PAC reinforcement learning with rich observa- tions. In Advances in Neural Information Processing Systems, pages 1840-1848, 2016.
12

---

[37] A. Krishnamurthy, A. Agarwal, T.-K. Huang, H. Daumé III, and J. Langford. Active learning for cost-sensitive classification. In International Conference on Machine Learning, pages 1915-1924, 2017.
[38] A. Lamb, R. Islam, Y. Efroni, A. R. Didolkar, D. Misra, D. J. Foster, L. P. Molu, R. Chari, A. Krishnamurthy, and Langford. Guaranteed discovery of control-endogenous latent states with multi-step inverse models. Transactions on Machine Learning Research, 2023.
[39] T. Lattimore, C. Szepesvari, and G. Weisz. Learning with good feature representations in bandits and in with a generative model. In International Conference on Machine Learning, PMLR, 2020.
pages
[40] G. Li, Y. Chen, Y. Chi, Y. Gu, and Y. Wei. Sample-efficient reinforcement learning is feasible for linearly realizable mdps with limited revisiting. Advances in Neural Information Processing Systems, 34:16671 1-6666,11166,,,, 2021.
[41] Q. Liu, Netrapalli, Szepesvari, and C. Jin. Optimistic mle: generic model-based algorithm for partially observable sequential decision making. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 363-376, 2023.
[42] Z. Mhammedi, D. J. Foster, and Rakhlin. Representation learning with multi-step inverse kinematics: An efficient and optimal approach to rich-observation rl. International Conference on Machine Learning (ICMI., 2023.
[43] D. Misra, M. Henaff, A. Krishnamurthy, and Langford. Kinematic state abstraction and provably efficient rich-observation reinforcement learning, arXiv preprint arXiv: 1911 1.05815, 2019.
[44] D. Misra, M. Henaff, A. Krishnamurthy, and J. Langford. Kinematic state abstraction and provably efficient rich-observation reinforcement learning. In International conference machine learning. pages 6961-6971. PMLR, 2020.
[45] M. A. Qassem, I. Abuhadrous, and H. Elaydi. Modeling and simulation of dof educational robot arm. In 2010 2nd International Conference on Advanced Computer Control, volume pages 569-574. IEEE, 2010.
[46] S. Ross and D. Bagnell. Efficient reductions for imitation learning. In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 661-668. JMLR Workshop and Conference Proceedings, 2010.
[47] T. Salimans and R. Chen. Learning montezuma's 's revenge from single demonstration. arXiv preprint arXiv: 18/2 122003381, 2018
[48] Schrittwieser, I. Antonoglou, T. Hubert, K. Simonyan, L. Sifre, S. Schmitt, A. Guez, E. Lock- hart, D. Hassabis, T. Graepel, et al. Mastering atari, go, chess and shogi by planning with learned model. Nature, 588(7839)6004-699 2020.
[49] J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889-1897 PMLR, 2015.
[50] A. Sidford, M. Wang, X. Wu, L. Yang, and Y. Ye. Near-optimal time and sample complexities for solving markov decision processes with a generative model. Advances in Neural Information Processing Systems, 31, 2018
[51] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587)-484-48, 2016.
[52] D. Silver, T. Hubert, Schritwieser, Antonoglou, M. Lai, A. Guez, M. Lanctot, L.. Sifre, D. Kumaran, T. Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1 1144, 2018
[53] Y. Tassa, Doron, A. Muldal, T. Erez, Li, D. d. L. Casas, D. Budden, A. Abdolmaleki, J. Merel, A. Lefrancy, et al. Deepmind control suite. arXiv preprint arXiv:1801.00690. 2018.
13

---

[54] A. Tavakoli. V. Levdik, R. Islam, C. M. Smith, and P. Kormushev. Exploring restart distributions. arXiv preprint arXiv:1811.1122 2018.
[55] E. Todorov, T. Erez, and Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ international conference on intelligent robots and systems, pages 5026-5033, IEEE, 2012.
[56] Y. Wang, R. Wang. and S. M. Kakade. An exponential lower bound for linearly-realizable MDPs with constant suboptimality gap. Neural Information Processing Systems (NeurIPS), 2021.
[57] G. Weisz, P. Amortila, B. Janzer, Y. Abbasi-Yadkori. N. Jiang, and C. Szepesvári. On query- efficient planning in mdps under linear realizability of the optimal state-value function. In Conference on Learning Theory, pages 4355 4385. PMLR, 2021.
[58] G. Weisz, P. Amortila, and C. Szepesvári. Exponential lower bounds for planning in MDPs with linearly-realizable optimal action-value functions. In Algorithmic Learning Theory, pages 1237-1264. PMLR, 2021.
[59] G. Weisz, A. György, T. Kozuno, and C. Szepesvári. Confident approximate policy iteration for efficient local planning in q" r"-realizable mdps. Advances in Neural Information Processing Systems, 35:25547-2555 25559, 2022.
[60] G. Weisz, A. György, and C. Szepesvári. Online in linearly -"-realizable mdps is as easy as in linear mdps you learn what to ignore. arXiv preprint arXiv:2310.0781,, 2023.
[61] Z. Wen and B. Van Roy. Efficient reinforcement learning in deterministic systems with value function generalization. Mathematicss of Operations Research, 42(3):762-782) 2017.
[62] Xie and Jiang. Batch value-function approximation with only realizability. In International Conference Machine Learning, pages 1104-11413, PMLR, 2021.
[63] T. Xie, D. J. Foster, Y. Bai, N. Jiang, and S. M. Kakade. The role of coverage in online reinforcement learning. The Eleventh International Conference on Learning Representations, 2023.
[64] I.. Yang and M. Wang. Sample-optimal parametric Q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995-7004. PMLR, 2019.
[65] D. Yin, B. Hao, Y. Abbasi- Yadkori, N. Lazić, and C. Szepesvári. Efficient local planning with linear function upproximation. International Conference on Algorithmic Learning Theory, pages 1165-1192. PMLR, 2022.
[66] D. Yin, S. Thiagarajan, N. Lazic, N. Rajaraman, B. Hao, and C. Szepesvari. Sample efficient deep reinforcement learning via local planning. arXiv preprint arXiv:2301.12579 2023.
[67] A. Zanette, A. Lazaric, M. Kochenderfer, and E. Brunskill. Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pages 10978-10989. PMLR, 2020.
[68] X. Zhang, Y. Song, M. Uchara, M. Wang, A. Agarwal, and W. Sun. Efficient reinforcement learning block mdps: model-free representation learning approach. In International Conference on Machine Learning, pages 26517-26544 PMLR, 2022.
14

---

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

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We provide a proof-sketch in the main paper and detailed proofs in the appendix.
Guidelines:
The answer NA means that the paper does include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
16

---

(c) If the contribution is a new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g.. to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification: This paper has only mathematical congtent. There are no experiments in this paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.c/ Sellic/guiies//CC Submi SubmissionPolicy for more details.
While 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 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: //tpps.cc/pplltu cttpcc/pppbblccccccccccec couublic/guii des//ooeSSummi ssioPolicyy for more details.
The authors should provide instructions 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 proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: This paper has only mathematical congtent. There are experiments in this paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
17

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars 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 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 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.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper has only mathematical congtent. There are no experiments in this рaper.
Guidelines:
The answer NA means that the paper does 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 into the paper).
9. Code Of Ethics
18

---

Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips http://wwwwpp.....pii..cccccccca
Question:
Answer: [Yes]
Justification: This paper does conform the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [No]
Justification: This paper provides purely mathematical contribution. As such, it is subject to the standard ethical concerns present for all mathematical papers, but no further ones.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA 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 unintended uses (e.g., disinformation. generating fake profiles, surveillance), fairesss considerations (e.g., deploymentt 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 tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (c.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This paper has only mathematical congtent. There are experiments in this paper.
Guidelines:
19

---

The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question:
Are the creators or original owners of assets (c.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: This paper has only mathematical congtent. There are no experiments this paper.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, if possible, include URI..
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper has only mathematical congtent. There are experiments in this paper.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their
submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
20

---

At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper has only mathematical congtent. There are no experiments this paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information
supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper has only mathematical congtent. There are experiments in this paper.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
21

---

Contents of Appendix
Additional Related Work
23
I Additional Results
25
Applying RVFS to Exogenous Block MDPs
25
C Helper Lemmas
28
C.1 Concentration and Probability
28
C.2 Regression
29
Reinforcement Learning
30
II Proofs for SimGolf (Section 3)
33
D Preliminary Lemmas for Proof of Theorem 3.1
33
Proof of Theorem 3.1
35
III Proofs for RVFS (Section 4)
37
F Full Version of RVFS
37
F.1 RVFS Pseudocode
39
F22
RV Pseudocode
G Organization
43
Overview of Analysis and Preliminaries
43
H.1
Overview Analysis
H.2
Benchmark Policy Class and Randomized Policies
Peii............................
H.3
Additional Preliminaries
I
Guarantee under V VT-Realizability (Proof of Theorem 4.1, Setup II)
46
LI
Analysis: Proof of Theorem 4.1 (Setup II)
46
I.2
Proof of Lemma 1.1 (Number of Test Failures)
48
I.3
Proof of Lemma 1.2 (Consequence
Passing the Tests)
50
1.4
Proof of Lemma 1.3 (Value Function Regression Guarantee)
52
1.5
Proof of Lemma 1.4 (Guarantee for Confidence Sets)
54
1.6
Proof of Theorem 1.1 (Main Guarantee of RVFS)
1.7
Proof of Theorem 1.2 (Guarantee of RVFS.bo bc).
58
J
Guarantee under V Realizability (Proof of Theorem 4.1, Setup
59
J.1
Analysis: Proof of Theorem 4.1 (Setup I) Proof of Lemma J.1 (Relaxed ya -Realizability under Gap)
59
J.2
60
K
Guarantee for Weakly Correlated ExBMDPs (Proof of Theorem B.1)
61
K.1
Analysis: Proof of Theorem B.
K.2
Proof of Lemma K.1 (Endogenous Benchmark Policies)
65
K.3
Proof of Lemma K.2 (Snapping Probability).
65
K.4
Proof of Lemma K.3 (Coverability in Weakly Correlated ExBMDP)
K.5
Proof of Lemma K.6 (Confidence Sets)
67
K.6 Proof of Lemma K.7 (Main Guarantee of RVFSex0)
69
L Additional Technical Lemmas
70
M BehaviorCloning Algorithm and Analysis
73
22

---

A Additional Related Work
Local simulators: Theoretical research. RL with local simulators has received extensive interest in the context of linear function approximation. Most notably, Weisz et al. [57] show that reinforcement learning with linear V is tractable with local simulator access, and Li et al. [40] show that RL with linear Q" and a state-action gap is tractable; online RL known be intractable under the same assumptions [57, 56]. Amortila et al. [3] show that the gap assumption can be removed if small number of expert queries are available. Also of note are the works of Yin et al. [65], Weisz et al. [59], which give computationally efficient algorithms under linear Q" -eareliizbiility for all x; this setting known to be tractable in the online RI. model [60], but computationally efficient algorithms are currently only known for RLLS.
Global simulators in which the agent can query arbitrary state acttin pairs and observe next state transitions have also received theoretical investigation, but like local simulators, results are largely restricted to tabular reinforcement learning and linear models [34, 33, 50, 17, 64, 39).
Local simulators: Empirical research. The Go-Explore algorithm [19, 20] uses local simulator access to achieve state-of-the-art art performance for the Atari games Montezuma's ' Revenge and Pitfall both notoriously difficult games that require systematic exploration. To the best of our knowledge, the performance of Go-Explore on these tasks has yet to be matched by online reinforcement learning; the performing agents [7, 27] are roughly a factor of four worse in terms of cumulative reward. Interestingly, like RVFS, Go- Exploxp makes use of core sets of informative state-action pairs to guide exploration. However, Go-Explore uses an ad-hoc, domain specific approach to designing the core set, and does not use function approximation to drive exploration.
Recent work of Yin et al. [66] provides an empirical framework for online RL with local planning that can take advantage of deep neural function approximation, and is inspired by the theoretical works in Weisz et al. [57]. Li et al. [40], Yin et al. [65], Weisz et al. [59]. This approach does not have provable guarantees, but achieves super-human performance at Montezuma's Revenge.
Other notable empirical works that incorporate local simulator access, as highlighted by Yin et al. [66], include Schulman et al. [49], Salimans and Chen [47], Tavakoli et al. [54].
Planning. RI with local simulator access is a convenient abstraction for the problem of planning: Given a known (e.g., learned) model, compute an optimal policy. Planning with a learned model is an important task in theory [25, 41] and practice (c.g., MuZero [48]). Since the model is known, computing an optimal policy a purely computational problem, not a statistical problem. Nonethe- less, for planning problems in large state spaces, where enumerating over all states is undesirable, algorithms for online RL with local simulator access can be directly applied, treating the model as if it were the environment the agent is interacting with. Here, any computationally efficient RLLS algorithm immediately yields an efficient algorithm for planning.
Empirically, Monte-Carib Tree Search [13, 35] is a successful paradigm for planning, acting as a key component in AlphaGo [51] and AlphaZero [52]. Viewed as a planning algorithm, potential advantage of RVFS is that is well suited to stochastic environments, and provides a principled way to use estimated (neural) value function estimates to guide exploration.
Coverability. Xie et al. [63] introduced coverability as a structural parameter for online reinforce- ment leanring, inspired by connections between online and offline RL. Existing guarantees for the online RL framework based on coverability require either Bellman completeness [63], model-based realizability [5], or weight function realizability [4, 5J), and it is not currently known whether value function realizability is sufficient in this framework.
Exogenous Block MDPs. Our results in Section 3.3 (Corollary 3.1) show that general Exogenous Block MDPs are learnalle with local simulator access. Prior work, on learning EXBMDPs in the online RL model requires additional assumptions:
Deterministic ExBMDP [22]. In this setting, the latent transition distribution Tendo is assumed to be deterministie. In this case, suffices to learn open-loop policies (i.e.. policies that play deterministic sequence of actions). This avoids compounding errors due to
Compare to our work, a small difference is that these works are not concerned with producing executable policies, c.f. Definition 2.
23

---

learning imperfect decoders that depend on the exogenous noise, making this setting much less challenging than the general ExBMDP setting.
Factored ExMDP [21]. This an ExBMDP setting with a restrictive structure in which the observation is d-dimensional vector and the latent state is k-dimensional subset of the observed coordinates. This structure prevents the setting from subsuming the basic (non-exogenous) Block MDP framework, and makes possible to learn decoders that only on the endogenous state, preventing compounding errors.
Bellman completeness. Xie et al. [63] observed that ExBMDPs admit low coverability, but their algorithm requires Bellman completeness, which is not satisfied by ExBMDPs (see Efroni et al. [22]. Islam et al. [30]).
24

---

Part I
Additional Results
This section of the appendix contains additional results omitted from the main body due to space constraints.
B Applying RVFS to Exogenous Block MDPs
We now apply RVFS to the Exogenous Block MDP (ExBMDP) model introduced in Section 3.3. ExBMDPs satisfy coverability (Assumption 3.2), but do not satisfy the pushforward coverability assumption (Assumption 4. required by RVFS in general. However, it turns out that ExBMDPs do satisfy pushforward coverability when the exogenous noise process is weakly correlated across time; we refer to this new statistical assumption as the weak correlation condition.
Assumption B.1 (Weak correlation condition). For the underlying ExBMDP M, there is a constant Coxa 2 such that for all h [H - 1J and (5, Eh-1 x En. we have?
P =5, Eh+1 E'] Cexa IPE [] P[E E'].
The weak correlation property asserts that the joint for the exogenous noise variables En and E is at most multiplicative factor Cexo 1 larger than the corresponding product distribution obtained by sampling &n and E independently from their marginals. This setting strictly generalizes the (non-exogenous) Block MDP model [36, 15, 43, 68, 42], by allowing for arbitrary stochastic dynamics for the endogenous state and an arbitrary emission process, but requires that temporal correlations in the exogenous noise decay over time.
We show that under Assumption B.1, pushforward coverability is satisfied with Cgush & Cexa SA (Lemma K.3 in Appendix K.1). In addition, V -"-realizability is implied by decoder realizability (Lemma D.1). Thus, by applying Theorem 4.1 (Setup I), we conclude that RVFS efficiently learns near-optimal policy for any weakly correlated ExBMDP for which the optimal value function has A-gap.
An improved algorithm for ExBMDPs: RVFS At first glance, removing the gap assumption for RVFS in ExBMDPs seems difficult: The v 7F-rralizability assumption required to invoke Theorem 4.1 (Setup II) is not satisfied by ExBMDPs, as decoder realizability only implies V realizability for endogenous policies x. In spite of this, we now show that with a slight modification, RVFS can efficiently learn any weakly correlated ExBMDP under decoder realizability alone (without gap or V ""-rralizability).
Our new variant of RVFS, RVFS is presented in Algorithm 8 (deferred Appendix F for space). The algorithm is almost identical to RVFS (Algorithm 5), with the main difference being that we use an additional randomized rounding step compute the policies कI: from the learned value functions Vi-n. In particular, instead of directly defining the policies 71. based the bellman h+1 as in Eq. (14), RVFS targets "rounded" version of the backup given by backups PA [V
E [P (x, C+l.
where E (0, is rounding parameter and $1...., : SH are i..d. random variables sampled uniformly at random from the interval [0, 1/2] (at the beginning of the algorithm's 's execution). Concretely, RV estimates the bellman backup PA [V[e+1(<,, (x, a) in Eq. (3) using the local simulator (as in Eq. (14) of Algorithm 5), and defines its policies via
(-) arg max (Pl C.
(4)
oeA
Throughout this paper. when considering the law for the exogenous variables f Eu., write [P[]] instead of Pa [-] emphasize that the law is independent of the agent's policy.
*W say that policy л is endogenous if it does not depend on exogenous noise, in the sense that πt (2x)) is measurable function of o" (xx)..
25

---

This rounding scheme, which quantizes the Bellman backup into e-! bins with random offset, is de- signed emulate certain properties implied by the gap assumption (Assumption 4.4). Specifically, we show that with constant probability over the draw of Ç1:11, the policy मे in (4) "snaps" on to an endogenous policy æ. This means that for RVFS succeed (with constant probability), it suffices to pass it a class y that realizes the value functions (Vi,' for endogenous policies и Ils. Fortunately, such a function class can be constructed explicitly under decoder realizability (Assumption 3.3).
Lemma B.1 ([21]). For the ExBMDP setting, under Assumption 3.3, the function class Vn. (x f(o(z)) ff [0, HJ o } is such that VT Vv. for all endogenous policies и. Furthermore, the policy class nI (T) ()) arg max ((((), [0, HJ $) contains all endogenous policies.
small technical challenge with the scheme above is that it is only guaranteed to succeed with constant probability over the draw of the rounding parameters SH. To address this, provide an outer-level algorithm, RVF bc (Algorithm 9, deferred Appendix F for space), which performs confidence boosting by invoking RVFS multiple times independently, and extracts high-quality executable policy using behavior cloning.
Main result. We now state the main guarantee for RVFS (the proof is in Appendix K).
Theorem B.1 (Main guarantee of RVFS for EXBMDPs). Consider the ExBMDP setting. Suppose the decoder class & satisfies Assumption 3.3, and that Assumption B. holds with Ceso > O. Let è (0, 1) be given, and let Vo, and HI, be as in Lemma B. Then Rx bc(ll, V VIHH& CIHH. 8) (Algorithm 9) produces a policy R.H such that J(x))- (RWH) E, and has total sample complexity
Ōc 36
33 E-2)).
This result shows for the first time that sample- and computationally-effiieen learning is possible for ExBMDPs beyond deterministic factored settings [22, 21].
We mention in passing that our use of randomized rounding to emulate certain consequences of the A- A-gap assumption leverages the fact that ExBMDPs have finite number of (endogenous) latent states. It is unclear if this technique can be used when the (latent) state space is large infinite.
26

---

Algorithm 3 R Recursive Value Function Search for Exogenous Block MDPs
1: parameters: Value function class V suboptimality e E (0, seeds Ç1 (0, 1), confidence 8 E 10.
2: input: Level h [0.. value function estimates V4 confidence sets DR+1HHH state- action collections CR and buffers BыG and counters İHH
/* Initialize parameters. */
3: Set M + [88 [8 S
4: Set Ntett- 2 H log M
Nrog + 2 (og))))M00 = e 5: Set Nest (k) 2N (gg(88Aree)))) H /6) and 8' 6/(4M7 Nest
9M log(SM HIV/6) 34M log(885 18) Nces
6: Set Ereg
Nost
7: Set B(I)
(MM
1* Test the fit for the estimated value functions VeLi at future layers. */
8:
for (I E Cn do
9:
for layer 8 H
h do for n = 1,..., Ntet do Draw 2b
10:
11:
Th-1 (- Th-1, ah-1), then draw 2z-1 by rolling out with Th+1:H where
VT [H], F (-)
arg max 2, (Pr1)(())))) - + with DH-1 0.
aed
12:
for ae-1 A do
13:
Update Lg <- 11 +
/* Test fit; if test fails, re-fit value functions VhLie up to layer
C.
*/
if susp soD. (P Ci + Ce (2,--1 and B, Be u for T -
+ e² (tte(tt)) then u ( Vc, De,
15:
16:
do
(V..H VT. Cris. Br.. t.H) RVFS (V++i-t, D.- CT.H. BrH tri: V,E, S1.H6)..
18:
go to line
19: h then return (V........)).
Re-fit Vn and build for (zh-1,0h-1) CA do
confidence set. */
20:
21:
Set (Ih-1, for , do
22:
Sample 2y (- 0h-1). For each a .A, let Vn (a+)) ) Monte-Carlo estimate for R [Σ rz an.] computed by collecting Nest((Cal) trajectories starting from æ, and rolling out with WIcH.
25:
Update
0h-1) < D( ah-1) 1) (w (x)))).
Let VA arg min E(zn-g E(zn-j-am-)es )eC,
1EE.) E(s,, (D.- an-1) (IT)) 22
27: Compute value function confidence set
D == (EVV
Σ
Σ
(Vi(z))- SErss j. (5)
(In-11%) JeCn Nres (2n
28:
return (ViCH, Drat. CLuH. BlcHstraH))
27

---

Algorithm 4 RVFS .c:: Learn executable policy with RVFSex via imitation learning.
input: Decoder class Q, suboptimality E (0, 1). confidence ò (0.1).
/* Set parameters for RVFS and define the value function and policy classes. */
2: Set CRVES +- -HH//48
3: Set V VI.H. where V/ (xr f(o(2))) [0, ff
De 2). wh [H].
4: Set II I1 where II, (T(+ E arg max a ((((),(()))))))) f [0. Hj 2 $). 4h [H].
/* Set parameters for BehaviorCloning. */
5: Set Noc + 8H2 log( (4H)11/8)), Nooost log -olgg((/)//og((4AAA)) Neval 1622 1og /6).
6: Set M s S Nest M² HE N = FRrTs 0-1, and 8' 40M7 NO M
7: Set Nreg M ERVFS
2 log (800080//220000 HM Nooost
8: Set VI-H- arbitrary, DI.H- V. Co.H 2, BoH Ø, lopt and Jmax 0.
/* Repeatedly invoke RVFS and extract policy with BehaviorCloning to boost confidence.
9: for i= 1,....,Noooss.. do
Invoke RVFS
10:
(Vi 1:H"":''') + RVFS (V VIH, Ca.H Ba. V, P,,reg
/8 Imitation learning
BehaviorCloning. */
11:
Define Rh (.) arg max P Ph,cess.88
he (.,a).
12:
Compute "I BehaviorCloning(I)) IIH 8/(2Nooost)
RVFS
/* Evaluate current policy. */
13:
== 0.
14:
for= L,..,, Neval do
15:
Sample trajectory (I1, (1,,01, a1, ,1,...,, aH, TH) by executing (1)
Set
H Th-
17:
Set [[ + v/Velll
18:
if J( Jmax then
19:
Set Popt = i.
20:
Set Jmax = J(
1:H
return: #1.H "1:H"
(tt)
C
Helper Lemmas
This section of the appendix contains supporting lemmas used within the proofs of our main results.
C.1
Concentration and Probability
Lemma C.1. Ler ā é (0. and H 2 1 be given. If sequence of events En satisfies 8/H for all h [H]. then
P[E, EI....,
|[ELH] 1-
Proof of Lemma C.1. By the chain rule, we have
[[EE=]] II P[En E En-1 I ( 21-8. b([H]
he[H]
We make use of the following version of Freedman's 's inequality, due Agarwal et al. [1, Lemma 9]:
Lemma C.2. Let R> be given and let wi.... Wn, be a sequence of real-valued random variables adapted to filtration H1." .., Hn. Assume that for all t e [n], wn s R and TR] ws HH-1] O. Define S, Σt= un and V, Ex E[w? H.-1]. Then, for any 8 e (0,1) and [0, 1/R,, with probability at least - 8.
S, S XV, + log(1/8)/A.
We will also use the following lemma. which is a standard consequence of Freedman's incquality.
28

---

Lemma C.3 (e.g., Foster et al. (25]). Let (w)) be a sequence of random variables adapted to filtration (H.) 1f0 w, almost surely, then with probability at least 1- ö,
3 r
Σ
Σ
B
wi
4Rlog(25))) (2)1)
2
and
T
T Σ
Σ E
$
w. 8R lRlog(26
2=1
C.2 Regression
Using Lemmas C.2 and C.3, we obtain the following concentration lemma, which will be used to prove guarantees for square loss regression within our algorithms.
Lemma C.A. Let B > and n E N be given, and let y be an abstract set. Further, let Q {g: y B}} be finite function class and y1..... Yn be sequence of random variables adapted to filtration a H1,",, Hn. Then, for any ò (0,1). 1), with probability at least 1 - 8, we have
Vg e Q,
] |11112 2B log 22/21/)) ||lll s 2|gl1= 2B 1og(2)21/),,
where | = Ev (v )² 1H--1] and |g 1
Proof of Lemma C.4. Fix g Q. Applying Lemma C.2 with wn - Hi-1), for
all i E [n., and (R, A) [ 1 1/B²). we get that with probability at least 6/(2
| 1 | z AB 1B + log(2121/6)/.
By substituting X B-2 and rearranging, we get
lgl 2||g| B² log(2)2
(6)
Similarly, applying Lemma C.2 with wn; [[g )2 H - for all ie [n]] and (R, A) (B², ()(B3)))) we get that with probability least (2
|g|l - | s AB |g|| (2g(2)2//))/
By substituting 2 and rearranging, get
l 2 |وا|| log(1///1)))))
Combining this with (6) and the union bound, we get the desired result.
With this lemma, we now prove the following key result for square loss regression.
Lemma C.5 (Generic regression guarantee). Let B 0 and n N be given and y be abstract set. Further, let F s {f y [0, B}} be a finite function class, and suppose that there is a function f. E F and sequence of random variables (11,æ1),.... (yn, xn,) e Y R. such that for all i E [m]:
I f-(i)) + t E; b,:
|bilsE;
E B]; and
E[e, [3.] O, where 3; == ( #1 b1=-1)-
Then, for Fe argmin Σnh (f(yi) ) and any 8 (0, 1), with probability at least 1 6/2,
| f. l| 4B (2 4B [bb
where ff = ET - (2
29

---

Proof of Lemma C.5. Fix de (0, 1) and let (f) Ef =z)², for f E F, and note that
since f min In (f), we have
0 ()) - ((
foll
where V denotes directional derivative. Rearranging, we get that
-. -2V (1-)(( -4 - (vi)) - 15 -1---ell --llle
- (()))
$ Σ (e; -.)(((()))(((.))))))) -17 -1
< Σ E: (f(y:) f.())) f. Σ b, (f(y)) (v:)). (7)
Bounding Term I. To bound Term I, apply Lemma C.2 with we e.. (F(v.) (-():)), R= B3. A= = 1/(82),, and Hi 87+1 and use
1. the union bound over f F;; and
2. the facts that E[y; 8,] = y; and E[E; -
to get that with probability at least - 5/2.
Σ E, ff (nn) 1
1h. 4B² 1og(2[F1/8).
By rearranging, we get that with probability at least -5/2.
Term Is 4B² log (2
Bounding Term II. We now bound the second term in (7). For this, that since || fallo0 B, have
Term 5 4B Σ b,j
This completes the proof.
C.3 Reinforcement Learning
Lemma C.6 (Performance Difference Lemma (e.g.. Kakade [33])). For any two policies म. म. E IIs and [H], we have
(1,, (xt,, Ft (1211)
E. VV. E
In particular, applying this for t = gives
Σ of (on, (x())) Qo (xwn))
((m)- E
Lemma C.7 (Potential lemma [63]). Fix h é [H]. Suppose we have sequence of functions g()) gd [0, B] and policies o0), ...., (()) such that
Vt [T].
E [(g s
sct
30

---

for some B 2 O. Then under Assumption 4.1, we have
E
[ "
(xx)) 2/ 8 Pusn (T) 2BCuush:
and consequently
min E Ex"
(xx)) s 22
B BRChh log log((T)
2BC push
[[]]]
T
Proof of Lemma C.8. See proof of [63, Theorem 1].
The following result is variant of the coverabillty-based potential argument given in Xie et al. [63]. Lemma C.8 (Pushforward coverability potential lemma). Fix h E [H]. Suppose we have a sequence of functions g() ....." g [0, B] and state-action pairs (x ") )..... (o'T,aa"") such that
VLE [T), E((()"()))) 0h-1 = x00 00h-1 a
for some 2 0. Then under Assumption 4.1, we have
Σ (x)) #h-1 = x0), aa-1== a s 2/ P2Cpuss log(2l) 2BC
and consequently
32 PuCu log
2BC
min ([g"((xN)) [[[T]
0h-1 "0 a < 22
T
T
Proof of Lemma C.8. Define di (x) : P n x Øh-1 (t)
a a " and let Z. = Eiet d
Let
(x( = min t 7 (z) Cpush pn(x))
We have
Σ ( | aa a"
Σ Σ (1) (x) 1-1 xeX
$ 1-1 xeX
(1)) + B 1-1 xE
B Σ (=)(((()))))))
From the definition pushforward coverability, we can bound
T
E Σ Tt
2C push Σ (1))x) 2C 2Cpush-
1=1 xex
xet
xex
For the other term, bound
T
Σ Σ
Σ Σ (x))
1/2 1(t2
1/2 ( 1-1
1-1 ved (x)
(x)) [(t2 (x)
1/2
T
1/2
2h-1 _ ,
",0,==="ara111 dd1]
(d (x))² 2
1/2
Σ Σ
I(| Th (x))
3TTT.
d (x)
x
31

---

Finally, we have
(x)) (x)
(x))) )
ΣΣ tml
1[tt (x)) s 5 Σ
xel J. (I)
(x) + Cpushill (x)
di
2 p0puh Σ Σ
(M(
(x) Cussndlhh (v)
to lext
(x)
20push
Σ (2) max
Σ
D t=l h (x) + (psh
4Cushh lTg(T
(T + 1),
where the last line uses Lemma 4 of Xie et al. [63].
32

---

Part II
Proofs for SimGolf (Section 3)
As described in Section 3.1, the main difference between SimGolf and GOLF lies in the construction of the confidence sets. The most important new step in the proof of Theorem 3.1 is to show that the local simulator-basee confidence set construction in Line 9 is valid in the sense that the property Eq. (1) holds with high probability, From here, the sample complexity bound follows by adapting the thange-of-measun argument based coverability from Xie et al. [63].
To this end, this part of the appendix is organized follows. We first state and prove technical lemmas concerning realizabilitty (Lemma D.1) and the confidence set construction (Lemma D.2 and Lemma D.3) in Appendix D. Then, in Appendix E. we prove Theorem 3.1 consequence.
D Preliminary Lemmas for Proof of Theorem 3.1
For this section, we define
K
max gh+ (111 .1)
(g) (h 0a/²
(1.00 h
and
and
700 (g) :>:::""' ET(()) "E (g an) - -Th TT (x0 )
where (x) ah Th h+1 are as in Algorithm 1.
(0) (1,N) (.,4)
Lemma D.1 ((21). For the ExBMDP setting, under Assumption 3.3, the function class On = ((I,a) > (((()),))))))))))))(())))))))( a) ge [0, HAA A oe }b satisfies Assumption 3.1 and has logl Q+ log[II, log
Lemma D.2. With probability at least for all [H], te [N], and g Q.
$ 33
(9a an) [ Ta (2 an an))
8N
+ +6log(2HN(0))))
K
set
sct
and
8N
Σ 1T
(gn an) Th(on-I)(Eh,n))) $4 (9)+
64log(2HN(1)0"))
K
Proof of Lemma D.2. Let tetter E [N] and h [H] be fixed. Let denote 2
(((1)) (((1)))))(11))))
RR[[K]
Define a filtration
t = o =1
7())
(9)
where 7()) is the trajectory generated in the ith iteration of Algorithm 1 (see Line 7). Fix g Q. Observe that (g) e [0, 4], so Lemma C.3 ensures that with probability at least 1 - d,
3 Σ (g) S ( Ktt
16log(25-1)
2 ket
and
Σ (() H "1
"Is s M 20 (g) 32 log((2
(8)
iet
Formally, this requires standard covering number argument; omit the details.
33

---

By the AM-GM inequality, for all < t. we can bound
E 1h20 (g)
76 "]
K
ho1 (2)11) a)))
E
(1) (4)
-.h K
Σ
b
(1.b)
+ max gh+1
7
k=1
asA
$ 2 B
(1 h )
Talgh-1 (x (1)))))))))))))))))))))))))))( )) (1
K
h+1 a2) 17000
21
Th a
Σ
69.0
max
gh+
and
and
18 (g) [
gn (2/ , ) Ln 1 ,a [ E
2 2
K
1 h+1 .1)) H
E [ a
Σ
(1
max
(1.0)
We have
E
(gn(2of (()) )- TaLon- ,a 1)²² H((-11) ETT (gg an) Ta (2)))))))))))))))))))))))))))))) ax)
and
K
max gh- (x//+1 (=).._))))))))))))..)) .a)=.aa)))))) H((-)) and
E
Th 1 (
Σ
Th
k-1
K
h+1 ()) ab 20 an = a 1300-11
=
E
Th[9n+1](20,, -
Σ
(1,0)
+ max Jh+1 (20/1/1) and
K
k-1
Since
E pll max Ih+1 acd
(ar 1 a) Φn (6) an //2² Ty [n (a)
and
are i.i.d. conditioned on (æn, an) (x/) (.))),), we have, kEepy] (rrh 2h111) )
1 K
max gh- (z) / .))) .. x/ a a
E
(1 an)
Σ
rh
(1.))
k=1
and
E
Th[9h=1](2h, and -0rrh
(c.)) max A
gh+1 (z) (1.k) .a)
(1) R x au a
K
$
K
so that
K
max gh ( .n)) H 4
E
a
(0)
K
aEA
K
Combining these bounds with (8) and rearranging thus gives
Σ
pti A
(g)
$3
(0) (mn an) ) [T aw))
8N K
16 16log(25-1)
kd
ket
and
8N
Σ E (9h az) TT1 let
0 (g)
+ 64 log
K
set
Taking a union bound yields the result.
34

---

Lemma D.3. Define Sttat 16log(2HN]Q)6 Suppose we set K with probability at least 1 6, for all [N] and H:
and B 2Bstat- Then Datat
SN
Q' *
All g Q satisfy
Σ E
(9n(2n) an) (119h11(2 ax))²) s 93.
Proof of Lemma D.3. Condition on the event in Lemma D.2. For any fixed / e [N] and e [H]. we have that
Σ KCB
(Q')
S
Σ E ( "
8N (Qh an) Th (h.
-16log(HHN115
K
8.V 16 2Bstat,
K
where the first inequality uses that =Ta(Qhh+ and the second inequality uses our choice for K. It follows that Q* Qo as long as B 2/sttt-
To prove the second claim, we note that for g e Q by construction.
Σ E (6) (g)(z))
(Th(:n))T[(())()ae)) a)))
< 2 (g) 8N
+GAlog(HHN(Q)
K
< (t)) (g) 5,8 993.
E Proof of Theorem 3.1
Proof of Theorem 3.1. From Lemma D.3, the parameter setting in the theorem statement ensures that with probability at least 1 - 6, for all e [2. Q' Q(0, and all g Q satisfy
Σ ETT (o))))) 1 (x))))))) an 98.
for all h. Let us condition on this event going forward. First, note that since Q" Q for all te NJ. we have that
J(TT) S E
max Q (x11 a
s sup E max max (e ae
(1
(10)
On the other hand, we have g arg max Q(1)) Exer maX 91 (z( a). and so since ("), x
x'")...
are i.i.d. and any g E Q(9) take values [0, H], we have that by Hoeffding's inequality, there is an event & of probability least 1 - 5 under which
Vie [2..
E
mmagg
1 t
Σ
max (2 (a) 5 ( 10-1 ( (oN(2N
aEA
(11)
This implies that under E, have
Vt e N].
sup E max 91 (x), a))
sup
1
Σ
m
(x)) (x) + -t- -
gE
aeA
gE((s) -
sct aeA
1
Σ max 1 (z (x(1),a) a) (t- 1)- -
1
set and
$ E max oi o (2),a) + 2/ 1og(222)))))
aed
(12)
35

---

where in the last inequality we have used (11) with f= g Thus, summing (12) for t = .....N and using (10) gives that under E:
N Σ J(x') $
and since J ( $ H.
N
(T= s Σ (2) //ogg))))// H.
(13)
On the other hand, using that JH+1 = O. we
N
Σ (E
(x1,
-
$ Σ
Σ
9n (Ion, an.) E=(0
.hh - maxx asA
9h-1 (I 0))
1-1
h=1
N.
Σ
Σ
9h (1on, an)) - E
(2)
rh + max (t)
aEA th+1 (2)+1, Bh ah
(law of total expectation)
1-1 h=1
N
Σ
Σ
E
(1)
(1) (zh, an)) [T[ an)]
1-1 --1
and so, by the potential lemma (Lemma C.7) and (9), we have
6H (oggNN) 2H Coov-
Combining this with (13), we obtain that with probability at least 1 - 25,
- ((=))) /HH.HCC
(log(2N (ogN)) 4v N
3HHCC...
It follows that if = Ce..CCo then the policy
के É unif(r(") ....,T(!))
returned by SimGolf satisfies, with probability at least 1 6:
- - s
Sample complexity. We now bound the number of episodes. Note that that within an iteration t of SimGolf, the local simulator is called KH times to update the confidence set, where K s N N/log(2HN))1/)) Consequently, the total sample complexity is bounded by
HNK & Ō S & log(((/0))/e")
36

---

Part III
Proofs for RVFS (Section 4)
F
Full Version of RVFS
Algorithm 5 displays the full version of RVFS. Algorithm contains an "outer-level" wrapper for RVFS, RVFS.bc, which invokes RVFS and extracts executable policy with imitation learning, and Algorithm 7 contains the subroutine used within Algorithm 5 to approximate Bellman backups for value functions using local simulator access. Additionally, Exogenous Block MDPs, described in Appendix B, in Algorithms 8 and 9. Before diving into the proof, we first describe how the full version of the algorithm differs from the informal version presented in the main body in greater detail.
display the variant of RVFS for
Differences between full version (Algorithm 5) and informal version (Algorithm 2) of RVFS.
The main difference between Algorithm 2 and its full version in Algorithm 5 is that in the former simply assume access to quantities involving conditional expectations such as:
The bellman backups PA [V++1] 1.) which are required to evaluate the actions of RVFS's policies [A[V
(see (2)), and to perform the tests in Line 8; and
The value functions - [Σ Tr σh a, a] in Line 15, which are needed in the regression problem in Line 16.
These quantities are not available to the algorithm directly, but they can be estimated using the local simulator. This is reflected in the full version of RVFS in Algorithm
Extracting policies from value functions. Let us briefly comment in more detail how Algo- rithm 5 extracts the policy σ² from the optimistic value function fo V at iteration t. From the Bellman equation, the ideal choice would be to set (7 (z) = arg max Pa [1 (x, a). but this requires knowledge the transition distribution. Instead, given parameters e, å (0, 1), SimGolf
invokes Algorithm 7 via Th (z) arg max Phe.,sffi ptt) (xx The operator P Pi,..6[f]] (AI- gorithm 7), when given input (z,a) X' A and fh+1 X I, uses the local simulator to (Nete) iid. Ta(- a, to estimate the bellman back-up generate Nsin 2 1 next states 2 hht1 h+1
(t)
Pa[ff+1] via 1. E (rhh fu+1 (x/22) 1), where Th ...., ( (Nan) (I, The number of (1))
Nu. samples Nsin in Algorithm 7 is set function of (c such that with probability least 8, Ph.r,s[sh- (2, a) Pa[ [I(,]] a s.
Invoking the algorithm. The base invocation of RVFS takes the form
VIS - RVFS RVFS = arbitrary, DIH = [V] Co.H = (2) hh: Bu.H (0) t1: =(1) (1)mmii)).
Whenever this call returns, the greedy policy induced by ViH is guaranteed to be near-optimal. Naively, the policy induced by VE- non-executable, and must be computed by invoking the local simulator through Line 14. To provide an end-to-end guarantee to learn an executable policy, the outer-level algorithm, RVFS.bc bc (Algorithm 6, invokes RVFSg, then extracts an executable policy from ViSH using imitation learning.
Subsequent recursive calls take the form
(Vi.H, DICH. CroH: BLS ImaH RVFS, (Vh.1. Dh-THH CraH, BRGH (HH; O),
For such a call, the arguments above are:
ViLL::: Value function estimates for subsequent layers.
Dh-1:: Value function confidence sets Va-1-H Va+L-H, which are used in the test on Line 14 to quantify uncertainty new state-action pairs and decide whether to expand the core-sets.
CreH: Core-sets for current and subsequent layers.
37

---

Bis: Buffers of tuples (#y-1, ah-1, V., tn), which record relevant features of the
algorithm's 's state whenever the on Line 14 fails and recursive call is performed.
M Counters that track the number of times Algorithm 7 is called in the test on Line 14, which facilitate tuning of confidence parameters.
Importantly, the confidence sets Vho 1:H1 do not need to be explicitly maintained, and can be invoked implicitly whenever regression oracle for the value function class is available (ef. discussion in Section 4). Likewise, the buffers B are only used in our analysis, and do not need be explicitly maintained.
38

---

F1
RVFS Pseudocode
Algorithm 5 RVFS); Recursive Value Function Search
parameters: Value function class V, suboptimality (0, 1), confidence ó (0. 1).
2: input:
Level h (O.....Hf.
Valuue function estimates VR+1HH confidence sets D4+1:H, state-action collections CR:HH buffers BR:H. and counters UHH..
/* Initialize parameters. */
3: Set M -88 H.
4: Set Ntast 2 M H log(8.M R 2- Nrog - log 1))
5: Set Nest (k) + 2NN log( (ee and 8' NNs
6: Set ei 9MH2 log(8M /0)
34M log (8g No. 18)
Nics
Nest
7: Set B(1) - /21081/8 (8AM]V1(/0).
/* Test the fit for the estimated value functions PaLL at future layers. */
8: for ( Ch. do
9:
for layer & H h do
for 1,..., Nest do
11:
Draw 2b ~ Th-1 (- #h-11 an-1), then draw æe-1 by rolling out with RHe where 10
VT [H]. क, (-)
arg max P P... [V.+1((,a), with VH-1 = 0.
(14)
aeA
12:
for d:-1 A do
/* Number times P Priee (Algorithm 7) called in the test on Line
14. */
Update 11 < 1e + /* Test fit; if test fails, re-fit value functions Punn up to layer
C.
+/
14:
if sup yeD, sup, (( [V]]
- P (fee) (fl) >ete B(t,) then
15:
C (2 and B, B₁ {(x Ve,t)). for T= k,.,,,,,,h do
(PrH, D.H Cr.H. Byh (.H) RVFS, ( (Vr.I: Dr.is Cr.H (r. go line
br: v,,,)).
18:
19:
h 0 then return: (Pim))5.))).
/* Re-fit D, and build new confidence set. */
20:
for (xh-1, (/-1) E Cn do
21:
Set (Th-1,
Ø.
22:
for i= 1,....., .reg do x4-1:
23:
Sample zy (.
24:
Let V, (2x,) be Monte-Carlo estimate for B [Σ Pz my computed by collecting Nest (exx((Cx)) trajectories starting from and rolling out with ThcH.
25:
Update D,, (Ih-11
(P((h-1,44-1) ((x), (xx))))
26: Let V. arg min feD E(zi-1ax---ed E(e, De.. (Fa. (f (f(x)) un)
27: Compute value function confidence set
D (SEV)
Σ
1
Σ (7(En))f(ai) S s (15)
Nres (Fn-1110))
(xn-1-Rh-1)CC
28:
return (VuH, Druts Cr... BLAH tmrH).
39

---

Algorithm 6 RVFS.bc: Learn an executable policy with RVFS via behavior cloning.
input: Value function class policy class I1, suboptimality (0, 1), confidence ò (0,
/* Set parameters for RVFS. */
2: Set ERVFS + /48.
3: Set VI-H + arbitrary, DI:H V. Co.H 2, Bo:11 + Ø, and 4 + 0, for i [0.. H).
/n Set parameters for BehaviorCloning. w/
4: Set - Cpush and Nest 22 M HERV' log(S0M0 E
5: Nreg + 2 M log( log(o0))(()))) (8 and 8' 10M'N=HEM
Get value functions from RVFS */
6: (V1 RVFSo VI.H. V Co.H. Bo:H H V, Nreg Neett ERVFS, 8/10).
/* Extract executable policy via BehaviorCloning algorithm for imitation learning. */
7: Define (.) arg max P 8h.covs. [V (.:)(;a)) a).
8: Compute I1t BehaviorCloning(I... T11l 8/2)
9: return: T1
Algorithm 7 Ph.c. [f]: Estimate conditional expectation E[r, + f((((11) whh :, an = =.
1: parameters: Layer h, suboptimality (0, 1), confidence 8' (0, 1), target function f.
2: input: (I.a)
A.
3: Set Ngin log 1/8)/22
4: Set D + Ø
5: for i= I,..,, Nii do
6: Sample ra ~ Rí (N a) and Φh+1 ~ Th(:I a, a).
// Uses local simulator access.
7: Update D Du (1r) 1h=1))
8: return: N E(r,)eD(r f(x)).
40

---

F.2 RVFSexo Pseudocode
Algorithm 8 RVFS) Recursive Value Function Search for Exogenous Block MDPs
1: parameters: Value function class V, suboptimality e E (0, seeds Ç1и é (0, 1), confidence 8 é 10.
2: input: Level h [O.. value funetion estimates V confidence sets V state- action collections CI.H, and buffers Bы. and counters I..H.
Initialize parameters. */
3: Set M +
4: Set Niest ME log (8M H ( - 1og
5: Set Nest(k) 2N feg log(8ANreg 16) and 8' + -8/(4M (est
9M log(SM (118//) Nos
34M H log(sM Ne.. 15))
6: Set oPeg
Neest
7: Set B(t) (M8
Test the fit for the estimated value functions VaLEH future layers.
8: for (Ih-1, 0n-1) 1--))) 6 Cn. do
9:
for layer & H ........... h do
10:
for n = I,..., Ntest do
Draw 24 Th-1 (- Th-1, ah- then draw 0e-1 by rolling out with Whels where
VT E [H]. F. (-) arg max P P 8 [V = +r with PH =0
REA
for ae-1 A do
13:
Update le + 12 1.
Test fit; if test fails, re-fit value functions Vh+re up to layer
e.
*/
14:
Musp (PEEL,,
Pe- a (f)))( =²+ 52. ((t)) then
15:
C (ovu((2:0)) (x-11, and Be Be B ( Vo, De,ttt))) for Tort=(, l,. h+ do
16:
17:
(VTH, V.H Cr.H. BrH, trd) + RVFS (Vr+I.H, Dr-1HH Cr.H. Br. t.i V,E,S 6).,6). to line 8
18:
19:
if then return (f.H.....)))
Re-fit V, and build new confidence set. */
20:
for (Ih-1, (h-1) Ca do
21:
Set DA (P (4-1) 1 Ø.
22:
for i= 1, Nreg do
23:
Sample Tn Th-1 (:1 xb-11 For each a E .A, let V, (xx) be Monte-Carlo estimate for E [Σ/], Tz æ..] computed by collecting Nest((Cr.) trajectories starting from I,, and rolling out with Wh.H.
24:
25:
Update D D( ah-1) D( ab-1) u {(x,, (xx))))
26: Let Vn == arg min Σ(zr 1,0, .)Cc, Me
(f(x) - 2
27: Compute value function confidence set
D {
fEVN
Σ (#n-1. DeC, Nres (en.))eD
Σ
(v)) - S (16)
28: return (VuH, Drutt CN... BrAH tm
41

---

Algorithm 9 RVFS .cc: Learn executable policy with RVFSex via imitation learning.
input: Decoder class O suboptimality E (0, 1). confidence ò (0.1).
/* Set parameters for RVFS and define the value function and policy classes. */
2: Set CRVES + =HH
3: Set V VI.H. where V4 (xr f( f [0, oe D). wh [H].
4: Set II I1- where II, (T(+ E arg max f(((). f [0. HJ 2 $). Ah [H].
/* Set parameters for BehaviorCloning. */
5: Set Noc + 8H2 log( (4)) Noosst log - Neval 1622 (2NNoostt/ /6)
6: Set M
Nest 2 M² HE (00g(80M''))) N
F FRrTs 0-)). and 8' 40M7 NO M
7: Set Nreg 2 2 ERVFS log (80]6 Nooost
8: Set VI-H- arbitrary, DI.H V. Ca.H 2, BoH Ø, lopt and Jmax 0.
/* Repeatedly invoke RVFS and extract policy with BehaviorCloning to boost confidence.
9: for i= l,.,..., Nooost do
Invoke RVFS
10:
(Vi 1::"":))))) + RVFS (V VI, Co.H. Bu. ; V, ",,reg Neest: ERVES, 6/(10 boost)) /8 Imitation learning
BehaviorCloning. */
11:
Define R (.) arg max Ph, Ph.cess.88
he (.;
12:
Compute "I BehaviorCloning(I,, IIH (/(oooost)
RVFS
/* Evaluate current policy. */
13:
== 0.
14:
for= I...,, Neval do
15:
Sample trajectory (I1, a1, , aH, TH) by executing #1
Set
H Th-
17:
Set [[ + V/Velll.
18:
if J( Jmax then
19:
Set Popt = 1.
20:
1:H ) (m)) return: #1-H- "1:H"
Set Jmax = I(
42

---

G
Organization
This remainder of Part III the appendix contains the proofs for the main results concerning the RVFS algorithm (Theorem 4.1 and Theorem B.1).
First, in Appendix we give brief overview of the analysis and introduce restricted set of benchmark policies which will be used throughout the proofs for Theorem 4.1 and Theorem B.I. The benchmark policy class is central to the regret decomposition for RVFS, and facilitates an analysis that does not require optimism.
In Appendix I, we prove Theorem 4.1 under Setup II (V"-realizabilityy) This constitutes the main technical development for Theorem 4.1. The central technical results proven here are Theorem 1.1, Theorem 1.2 and which generalize Theorem 4.1.
In Appendix J, we prove Theorem 4.1 under Setup I (V' -raaiizizabill as straightforward consequence of the tools developed in Appendix I (Theorem 1.1 and Theorem I.2).
Finally, in Appendix K, we prove Theorem B.1 (analysis of RVFS for the ExBMDP problem). This analysis has similar structure to the proof of Theorem 4. under Setup II in Appendix I, and builds on the same analysis techniques, but requires specialized arguments due to extra technical challenges in the ExBMDP setting.
Appendix M gives self-contained presentation of the BehaviorCloning algorithm for imitation learning, which is used within RVFS. be and RVFS
H Overview of Analysis and Preliminaries
In this section, we present some notation, technical tools, and preliminary results we require for the analysis of RVFS in the settings we described in Section 4. We start by defining set of restricted benchmark policies used in the regret decomposition for RVFS.
H.1 Overview of Analysis
In this section we give brief overview of the analysis techniques behind Theorem 4.1 and Theo- rem B.I. We focus on Theorem 4.1 to begin.
Recall that RVFS recursive in the sense that whenever the test in Line 14 fails for layer h e [M], an recursive call RVFS, is initiated. Throughout the recursion, via the steps in Item I and Item 2. RVFS maintains the following invariant: whenever call to RVFS, (an instance of RVFS initiated at layer h) terminates, the confidence sets Dn-1:H that it outputs satisfy, with high probability:
vl II. H]. V Dz.
(Inv
In addition, RVFS, can only return the value function tests in Line 14 (which involve the confidence sets ))+1=)) all succeed. From the invariant in (Invl), it can be shown that the tests only succeed if the estimated value functions V satisfy:
vlE 11.
1.. H].
sup aeA
35
Etest
(Inv2)
where Etest > 0 is a parameter set by the algorithm. We use pushforward coverability to show that RVFS can only expand the core-sets CI.H a polynomial number of times before the algorithm terminates and (Inv2) is satisfied.
The invariant in (Inv2) is useful because it ensures that the greedy policies
Th (x) arg max PA [V++1](x,0)
ae,A
induced by the learned value functions ViSH near-op To make this precise, recall that given parameters e, 5 (0, 1), the action w (x:) of RVFS's policy at layer h and state x X, is given by
F (x) é arg maxp, Ph.e.al PaaxxP..elViian1t.....
(17)
aeA
where VR. is the estimated value function at layer / + 1. The operator P Ph.coo Phoi] (Algorithm 7), when given input (z,a) X x A, ensures that probability least 1 - 8, |Ph.s ( (V)
43

---

Px[Vi=1((z,0)) Combining this with the invariant in (Inv2) and the fact that V h-11 one can see that with high probability (over the randomness in 2/2 IP and P), we have:
max P Phr [
Vg (æx, 48.
(18)
Analysis under Setup I. For Theorem 4.1 (Setup D. Eq. (18) together with the definition of F. in Eq. (17) and the gap assumption (Assumption 4.4) implies that if e A/8, have that with high probability (over the randomness in w 1p and P).
R (Z arg max P P. [ a) arg max Vi (z, ( (zn).
acA
This suffices to show that is near-optimal, since by the performance lemma [33], the suboptimality of के can be bounded as
( s Σ (T)(() (x,))
(19)
h-1
This suffices to prove the performance bound Theorem under Setup
Analysis under Setup II. For Theorem 4.1 (Setup II), immediate challenge in applying similar analysis to Setup I is the lack of suboptimality gap A, which makes it impossible to directly bound the probability that म policy class I1g c IIs in Appendix H.2 below. The class II, c IIs is constructed such that that there exists policy
in Eq. (19). To address this, we introduce restricted benchmark
II, that (i) -ss--uubppimml and (ii) emulates certain properties of gap. Together, these properties facilitate analysis similar to Setup I. Overall, this argument is similar to the "virtual policy iteration" analysis in Yin al. [65].
Analysis of RVFS**0. The analysis of RVFS for ExBMDPs (Theorem B.1) uses the same idea as the analysis for Setup II, except that we can only realize V for endogenous policies that act on o² (.x). To address this, we use the randomized rounding scheme in RVFS*xo, and the crux of the proof is to show that with high probability, the rounded policies in RVF "snap" onto endogenous policies, facilitating argument similar to Setup II.
Generalizing the analysis. We mention in passing that RVFS can be slightly modified to recover other existing sample complexity guarantees for RL with linear function approximation and local simulator access that do not require pushforward coverability, including linear-Q" realizability with gap [40] and Q" Qerrealizability [65]; we leave a more general treatment for future work.
H.2 Benchmark Policy Class and Randomized Policies
As described above, central to our analysis is set of (s))suubopiimal policies against which we benchmark the policies returned RVFS, which emulate certain consequences of the A A-gap assumption (Assumption 4.4). Before introducing this concept formally, we first define the notion of a randomized policy.
Induced stochastic policies.
Given an arbitrary collection of independent random variables Q (Q (z. (...)))))). we say that a policy ι is induced by Q if x satisfies
vh [H], Vx e
(x) e arg max (x,,a,,
(20)
a'sA
where we use the bold notation Ty (2) as shorthand for the random variable an TA (2) E A(A): in other words, for each E X, TA (x) A(A) is the distribution induced by sampling Q (x.-) and playing the action (2) arg max Qn, a'). .. If there are ties in (20), we break them by picking the action with the smallest index; we assume without loss of generality that actions in A are index from IAI..
Benchmark policy class. We now define the benchmark policy class as follows.
Definition H.1 (Benchmark policy class). For e e (0, let IIg S IIs be the of stochastic policies such that E II. if and only if there exists collection of independent random variables Q = (2,
A in [0, H) such that:
* n is induced by Q (i.e. Eq. (20) is satisfied); and
44

---

For all (h, a) E [H] x X' x A. we have I(Q). (z.) a) s almost surely under the draw of Q.
Intuitively, the set II contains the set of all (stochastic) policies corresponding (randomized) state-action value functions that are point-wise OE)) close to Q" We formalize this claim in the next lemma.
Lemma H.1 (Suboptimality of benchmark policies). Let e e (0,1) be given. Let it e [Ig be stochastic policy induced by collection of (independent) random state-action value functions (Q (z, (...))))))) c [0, H] such that for all h [H] and all (I,a) X x A:
(Q)(x Q a almost surely, and +x) arg max (I a'eAA
Then, for all h [
Y ( +HE.
(21)
..... 1, we start by showing that all &: Proof of Lemma H.I. Using backward induction over é = H....
(2,za) Qx(2,)) a) 25 (H - 1). almost surely. We then instantiate this with e and use the fact that Q Q. s to get the desired result.
(22)
Base case [e = H]. By definition of the state-action value function, we have, for all т e lls. Q'H = Q7 Thus, since sup(r.a)exxa (Â - (x, a)l s almost surely (by definition of Q.H), get that
(x, X A, (1, (x)
almost surely. This implies (21) for 8 H.
General case [E < h]. Fix [H 1] and suppose that (22) holds for all L [h+ + l..... H] almost surely. We show that it holds for & = h almost surely. Fix (z, E X x A. We have
(z ax) Tn
To (n)+)) ((,,)))((n,,)))
2s (H h) Th (2
(23)
almost surely, where the last step follows by the induction hypothesis. Th TT[Quti((x,a) - (x, We have, almost surely, that
We now bound
Th (11 (=, ThIQu==](I,a) PAlV PP -
- QZ
(z,
Th (h( ( P +E, (by the assumption on 21)
E max Qin (8 d') Q (#h-1, Th.t (2h. 1)) wh x, an a +
d'ed
E @ (Ih+1, m1+1 Q (0h-1 the (x 2/ x, ab al +
2s,
(24)
where the penultimate inequality follows by the definition of カ4-1, and the last inequality follows by the fact that Q 1 oo $ almost surely, by assumption. Plugging (24) into (23) completes the induction, and so we have that
((x E X x A,
(i(z,a) s (I( s 2HE.
In particular, taking the max over a on both sides and using the definition of म, we get that
Vx X, (x' 2 मो (x)) 2Hs,
almost surely. Combining this with the fact that Q (z, म (x)) s Qf (z. क (x)) + e,, almost surely (since IQ Q loo S almost surely by assumption) implies that
Vi (x) S Q (z, म (x)) + 2H + Taking expectation 7 (x) and bounding 2He by 3He leads to the desired result.
45

---

H.3 Additional Preliminaries
The following lemma gives a guarantee for the Bellman backup approximation algorithm P (Algo- rithm 7) that is tailored to the analysis of RVFS.
Lemma H.2. Let E, (0.1), B > O, and h [H], be given and let V be a finite function class. For any sequence (2t)121 C X of state action pairs, the outputs (Ph.e,0 (f of Algorithm 7 satisfy, with probability at least 1 - 5,
Vi VAEE Phe. Lf][IL a) a)
Proof of Lemma H.2. By Hoeffding's inequality [28] and the union bound over a A and f V. we have that for any i 2 1, with probability least 1 1- 5/(2)")
Vf V, Va e A, P [f] a) PaLS](=),)) s (
/21081/
The desired result follows by the union bound over i 1 and the fact that Σe1 1/i² / 2.
I Guarantee under V ie-liiiiiayylytyy (Proof of Theorem 4.1, Setup II)
In this section, we prove Theorem 4.1 under Setup II. First, in Appendix I.1 we state a number of supporting technical lemmas, then use them to prove more general version of Theorem 4.1, Theorem 1.2, which holds under a weaker realizability assumption (informally, V V*-realizability only for near-optimal policies π); Theorem 4.1 follows as an immediate consequence. The remainder of the section (Appendix 1.2 through to Appendix 1.6) contains the proofs for the intermediate results.
L1 Analysis: Proof of Theorem 4.1 (Setup II)
We analyze RVFS in the setting of Theorem 4.1 (Setup II), where we have a function class V satisfying V""rralizabilityy (Assumption 4.5). We will actually show that the conclusion of Theorem 4.1 holds under a weaker function approximation setup we refer to as relaxed V -realizability: instead of requiring V /FF-realizability for all E Ils, we only require it for policies x in the set of near-optimal policies corresponding to the benchmark policy class Ie for some Ereal > 0 (IIg is defined in Appendix H).
Assumption L.1 (Relaxed V VT-realizability). For Ereal > and all π II and h é [H], we have (x) E V (f: X + [0, H]].
We will analyze RVFS under Assumption 1.1 and Assumption 4.1. However, it turns out that all of the main results for RVFS can be derived under this assumption: As we will see in Appendix in the sequel, when the A-gap assumption (Assumption 4.4) is satisfied, then II (^*) for all Greal A, allowing us to prove Theorem 4.1 under Setup I as a special case of relaxed V -*-realizability. Our analysis for the ExBMDP setting in Appendix K requires more work, but uses that for ExBMDPs, Assumption I.1 is satisfied for subset of II.... corresponding to endogenous policies.
We begin with our analysis under Setup II by bounding the number of times the test in Line 14 fails. Since the sizes of the core sets C1.H in RVF$ are directly related to the number of test failures, the next result, which bounds |Cxl for h E [H], allows iterations with high probability. The proof is in Appendix I.2.
show that RVFS terminates in polynomial
Lemma L.1 (Bounding the number of test failures). Let d, (0.1) be given, and suppose that Assumption 4.1 (pushforward coverability) holds with parameter Coush > O. Further, let f E V, be given, where V is arbitrary function class. Then there is an event & of probability at least 1 ô under which any call RVFS J, VI 2, 2, 0, 2) (Algorithm 5) terminates, and throughout the
execution of SV. we have
Vh [H], |CN1 S 18== "pussh H
(25)
In particular, Lemma 1.1 ensures that with high probability, every call to RVFS,, (made recursively via the call to RVFSg) terminates in polynomial iterations. When RVFS, terminates, all the tests in Line 14 must have passed for all l> h. Using this and standard concentration argument, we get the following guarantee for the estimated value functions and confidence sets returned by each call to R, The proof is in Appendix I.3,
46

---

Lemma 1.2 (Consequence of passing the tests), Let [O.. H] and E, (0,1) 1) be given and consider call to RVFS, the setting of Lemma 1.1. Further, let & be the event of Lemma 1.1. There exists event E, of probability at least 1 H H such that under e Eg if a call to RVFS,, within the execution of RVFS terminates and returns (VieH, Vus Cret Blatt taH)), then for any (h-1) Cb. and & & +...H..
4log(8M
test 18)
p
sup max (P-a] DeD, aEd
-t--- - 3e 0h-1 21-1; 01-1 0/-1
Ntest
(26)
where ( rehh is the stochastic policy induced by VICH and M and Ntest are defined as in Algo- rithm 5. Furthermore, under the event &, the total number of times the operator P is called in the test of Line of Algorithm is at most OCppssh Ntest H
We now give a guarantee for the estimated value functions VISH computed within RVFS in Line 26 (the proof is in Appendix I.4).
Lemma L. (Value function regression guarantee). Let h [O... H] and 0, e (0, be given, and consider a call to RVFS, in the setting of Lemma 1.1. Further, let II' S Ils be finite policy class such that the class V realizes the value fanctions V for TT' (i.e. V safisfies Assumption 1.1 with Nera replaced by IT'). Then, there is an event EK of probability at least - 5/ under which for all 2 if
1. RVFS,, gets called for the kth time during the execution of RVFSo; and
2. this kth call terminates and returns (Vnet, VusH. CI.H B
then if (Ry Frah is the policy induced by VICH and Nreg is set in Algorithm 5, we have that for all т e IT'
Σ
1
Σ
(Vn( Vo (xn))
(2h-1, 1.61 DEC, Nrez (En,))eDs (
(
9kH2 log(8h2 ((12111111116))))
8H²
Σ
[D) T TT,))
2h = Th-1, ah-1 an-1];
Nreg
7-h
where the datasets (Dx(I,a) a) (x, a) E C.} are as in the definition of Dj, in (15).
Next, we use this result to show that the confidence sets Di.H returned by RVFS, are "valid" in the sense that they contain a value function (V/²) ) corresponding to near-optimal stochastic policy ø in the benchmark class Ie In the sequel, we use this fact to substitute V for fe in Eq. (26) and bound the suboptimality of the learned policy म.
Lemma L.4 (Confidence sets). Let e, e (0, be given and suppose that Assumption 4. (push- forward coverability) holds with parameter Cpush 0. Let & V be arbitrary, and suppose that V satisfies Assumption I.l with Greal = 4e. Then, there is an event r of probability at least 1-36 35 under which call to RV V, 2, 0,0; V,,,, (Algorithm 5) terminates and returns tuple (VvR, DuH, C.... ByH,trH) such that
Wh [H].
V E
where R1. Tg is the stochastic policy defined recursively via
(2, P.IV
(1 (.LVA 48, for H. otherwise,
e X, (x) arg max acAA
(27)
where P [Vr, a) is a realization of the stochastic output of the P operator in Algorithm 7 given imput (z, a), and 8' is as in Algorithm S. Furtherore, we have î II
The proof of the lemma is in Appendix 1.5.
Equipped with the preceding lemmas, we now state the main technical result of this section, Theo- rem 1.1, generalization of Theorem 4.1 which holds under relaxed 4 /""rrealizaiility (Assumption 1.1).
The proof is in Appendix 1.6.
47

---

Theorem L.1 (Guarantee for RVFS under relaxed V ""-realizability). Let ò, (0,1) be given, and suppose that Assumption 4.1 (pushforward coverability) holds with parameter Cust > O. Let f be arbitrary, and assume that y that satisfies Assumption 1.1 with Greal = 4g. Then, with probability least 1 56, W e;V,e,) (Algorithm 5) terminates and returns value functions Vi.H that satisfy
vh [H]
pusC
where (x) arg ma Ph. & ( for all h [H]. with स e Ih defined as in Lemma 1.4 and 8' defined as in Algorithm 5. Furthermore, the number of episodes is bounded by
11 A.'
Next, we state a guarantee for the outer-level algorithm, RVFS.be under relaxed V*-realizability. Recall that RVFS. invokes RVFSu, then extracts an executable policy by applying the BehaviorCloning algorithm (see Appendix M), with the "expert" policy set to be the output of RVFS.
Theorem 1.2 (Main guarantee of RVFS.bc), Let e (0,1) be given, and define ÊRVES e &H- Suppose that
Assumption 4.1 (pushforward coverability) holds with parameter Cpush > 0; the function class V satisfies Assumption 1.1 with Ereal = 1 (i.e. all T-realizability); and the policy class II satisfies Assumption 4.3.
Then, with probability at least I:: =RVFS.bc[II, V,e,8) (Algorithm 6) satisfies - J( s.
(28)
Furthermore, the total number sample complexity in the RLLS framewokk is bounded by
(C 23 A--13)
The proof is in Appendix 1.7. Note that Theorem 1.2 is restatement of Theorem 4.1 in Setup II (restated for convenience). As result, Theorem 4.1 is an immediate corollary.
Proof of Theorem 4.1. The result follows from Theorem I.2, since Assumption 4.5 is stronger than Assumption I.I.
L,2 Proof of Lemma I.1 (Number of Test Failures)
Proof Lemma 1.1. Fix {H). note that size C, corresponds to number times the test in Line 14 fails for é h throughout the execution of RVFS 2,,,
Let M (H denote the desired upper bound on [Ca). Suppose that the in Line 14 fails at least twice for é h (if the test fails at most twice, then [Cxl 2 and so (25) holds for ? = trivially), and let
(D)) DO (.)) (2 1. 1..D (x h-11 h
D (
h-11
denote the elements of the set B₁ in the order which they are added to the latter in Line 15 of Algorithm 5. Note that [B,l |C,l-- Note also that t represents the number of times the subroutine P Ph-1.s,8 has been called in the test of Line 14 throughout the execution of RVFS, and up to the time the test failed for (1/() ( We will use this fact in concentration argument in the sequel.
By definition of (1(9) and Lemma C.4 (Freedman's 's inequality) instantiated with
(V fn f )
Yh æn:
B H: and
48

---

7t Nreg" i;
and the union bound over [M [Crl], get that there is event & of probability at least 1 6/(2H) under which
Vie [M A Call.
(#x) fa((x))2 0h-1 - :h1 0n-1 a
jai
411 log (1MH))111))
$ $ 2:
(29)
Nrea
Now, define fh arg max m Se we have that under Ex:
(6) E D(0) (xhh) - (n(())) 0h-1= = =111=xh11 h-1 00-1:00-11 -0
From (29),
Vie [M
EE((P - 1 (xx))) Ih-11 = - ah-1 = a,) E
(30)
j
We now use this to bound the number of times the test in Line 14 fails for 8 h. Suppose for the sake of contradiction that the test fails at least N times for some N M (i.e. [Cal N M). Conditioned on En. we have by Lemma C.8 and Eq. (30),
min sup E D (ax) fx))
xh-1 xh a/-1 0
(e[M] fe
min M[[M]
[ (1) (xx) f1. (xn)
0h-1 = x/ 0 0 1-1]
Coush M2
1/2 2Cpush
22
? log (2M)
Now, substituting the expression of EPeg in (29) and using the definition of eieg in Line 6 of Algo- rithm 5, we get
Cpush
4MH² log (og(4MH(11166) ))
1/2
2C
= 2
22 +
M
Nreg
M
Cpush
22M log log(SM* 6 log( (8M N /00)
1/2
2Cpush H
2
M
Nreg
Ntest
M
S,
(31)
where the last inequality uses that M =18= and
Nreg = 2 2 log 1og(81)) and Niest 2 -e- log((8M "))
Line 5 of Algorithm 5.
On the other hand, by Lemma H.2. there is an event E of probability at least 8/(2 under which for all f E V. all i E [M], and 8' as in Algorithm 5:
P P 1
[T (1
h- 22 (2
P P [n 2
< P n- (1 (- -21
210g1/8 (MM0))/(4MAAA (4MAHIV(09900))
1P-1IDD fn a
--1) + B(t()))
(32)
where ((t(2) is in Algorithm 5. Thus, under E,, the test in Line 14 fails for & h at least M times only if
Vie [M],
< sup G
(Ph-L. 7 - o
- ((
sup
E (10) (xx) (x()))
#h-1 x/ a/-1
100--1000 = [
(by (32)),
sup
E (1) (xx) (x()
0h-1 0h-1=-f111 a/-1 = (
--1
49

---

Unless N < M, this is contradiction to Eq. (31). We conclude that under the event En n E/ the test in Line 14 fails at most N < M C8s times for l h, and so under & n & NEH. we have
4h [H], |C s [8e Cpush H.
By the union bound, we have P[ε E/ n En E/y 2 1 8, which completes the proof.
1.3 Proof of Lemma 1.2 (Consequence of Passing the Tests)
Proof of Lemma I.2. Let e [H] be given. Fix & [h + H] and x g-13 2 g-10--- denote the sequence of states used in the tests of Line 14 throughout the execution of RVF we assume that the sequence is ordered the sense that if < j. then x²21 is used the test of Line 14 before (5) Let T₃ N U {+00) be the random variable representing the total number of times the operator Pe-1...0 invoked in Line throughout the execution of RVFSg (T, is also the random length of the sequence "8-1, 20 1-1..... if RVFS, terminates, then T. is finite. The first step of the proof will be to show that under the event & of Lemma 1.1, T. is no larger than M Nest H at any point during the execution of RVF This will help us establish key concentration results, leading to the desired inequality (26).
Bounding T3 under E. First, note that under the event & of Lemma I11, we have that for any 7 T [H).
|C+| M CCush H):
(33)
and so RVFS, gets called at most M times throughout the execution of RVFS For the rest of this paragraph, we condition on and fix T e [[... Within any given call to RVFS, (throughout the exccution of RVFS the operator P Pe-1,e,0 is invoked at most
Nces H
x
HM
S & Ntest 2
to loops Line Line Line 10
Number times RVFS, returs to (see helow)
times. This is because the for-loop Line of RVFS, resumes whenever a test in Line 14 fails for one of the layers 7 1, ...., H (see Line 18) once the recursive calls return, and the total number of test failures across all these layers is bounded by HM (by (33)). Now, since RVFS, gets called at most M times throughout the execution of RVF (as argued in the prequel), the total number of times the operator P P6,,,,8 is invoked in Line 14 within RVFS, is at most
M N
Finally, the total number of times the operator Pe-1,e,8 & is called in Line throughout the execution of RVFS is most H times larger (accounting for the contributions from RVFS, for all e [#]); that is, it is at most M Ntest H We conclude that the random variable Tç satisfies
Te M 2 3
(34)
under E.
Specifying E In this paragraph, we no longer condition on E. We will specify the event E, in the lemma statement. Let 5' defined as in Algorithm 5. By Lemma H.2, we have that there is an event E of probability at least 1 -8/(211)) under which:
Vie E [Tr], Vag- E A : sup (P.-1...8 [i] Pe. (6e)(()) az -8 (TTi
(P (P [1] P (f)) -c)) (1) (10_===----/1111/A/AAAAA///V/// (8AHPM)VIT/0))
= sup fei,
2 sup feV,
-
-s- / |
-e v 2 2200s
(LemmaH.2)
2 sup
1up - 25 V...Vloo.,). / (BAH 18).
fe,,
(35)
the other hand, for [T; Ntest + 1], we have by Lemma C.4 (Freedman's inequality) instantiated with
50

---

n Mest and yı = II (suu max
(211) .a) 3z for all
i [Ntest]]
@ {id}:
1; and
1= 1;
that there is event e,e, of probability least 1 6/(412 under which
Σ Nest
sup max fEL, aeA
-
aa)>>3
+
Σ
I sup LEii
.a) >E 3E.
OgieNeet
Now, let E%,2- Nkee T Nosst elf Che By the union bound and the fact that Σx21 1/h? = x2/6 22 we have that PP (2/1?). Furthermore, under Eh we have
vk E [T, Ntest 1].
Σ
P sup max JeD, aeA
aa)> 35
Nsi
4log(8H22T20))
Σ
I sup aE
-
aa)>>>3 313.....
(36)
OsisNoat
We define E == 8/1 E n E n Eh Note that by the union bound, we have P[&]] 2 desired.
Termination of RVFS; under & n E We now show that under & n E if RVFS, terminates, its output satisfies (26). For the rest of the proof, condition on & & Suppose that RVFS,, terminates and returns H DIeH, CR.H. BLH (uH). ). this case, the value function V. must have passed the tests in Line 14 for all (IN-1, E Ch. Ntest and a;-1 A. Fix (IΛ-1, a4-1) Cn and let k [Te - Neest
1] be such that (x=")) (efe))jeeoo... je(o....... represents subsequence of states that pass the tests in Line 14 layer for (#h-1,0;-1)) within the call to RVFS,. The fact that the sequence (1) )a2 is ordered (see definition in the first paragraph of this proof) and that (a. je(o... pass the tests imply that
1. The states (xx ve(oo..Nunu-1 at layer f- are i.i.d., and are obtained by rolling out with Rie starting from (#h-1, ah-1);; and
2. The test in Line 14 succeeds for all (xx(+²²) Jes....Nes...111 that is
Vj E Ntest - 1], Vac-1 A,
sup (P L-1.e,5 [Ve] Pe-Le (fll .axi)
feV
Sete. B(k +
<E+E e
< 2 (SAM)VIT7))))))))
51

---

This implies that
E [0.. (tet Vae-1 E
sup fel,
/Pa-1 [V, f/1(2 aa-1)l 33E
sup Pe- (110) , feV.
1--1 -E - 22 2
( (4AMHRIV(T20),
(37)
(35)
sup (Pe-Le, & [se] (n -0-)0----------0-0000 (
210gy0 (1AMFP1N//7
feVe
0.
(by Item 2)
(38)
where (37) follows by (34) and the choice 8 in Algorithm
Now, by Item 1, have that ( has probability law pasll [.] i E [0.. Ntest - 1]. and so by (36), we have:
2h-1 2b-1; 0h-1 ; 0h-1 for all
p
sup max (Pe- [Vc] - Pz- 36 0h-1 = Ih-1, ah-1 ah-1 foBe aed
log((8
Σ
sup SeDe,aEA
IP
(410) a
a)) 3e
Ntest
Neest OsveNess
4 1og(8M N2 test 18)
<
(using (34) and the fact that all the tests pass, i.e. (38)).
Ntest
Concluding. We have established that under & n E we have for all [h H. and all (hh-1, Cn:
4 Alog(8M*22 Nest H²/6)
sup max (P=A) 3s 0h-1 = Th-1, Oh--1 ah-1 S
foD a
Ntest
Furthermore, we have P[ 1 5/H. This completes the proof.
L.4 Proof of Lemma 1.3 (Value Function Regression Guarantee)
Proof of Lemma I.3, Fix æ II's s Пyş and 2 1, and consider the kth call to RVFS,, as per the lemma statement, and let Sg be the state of RVFSa during the :tth call to RVFS, and immediately before Line 20, i.e. immediately before gathering data for the regression step RVFS,.
Relating the regression targets to V, Observe that Vr, is the least-squares solution of the objective in Line 26, where the targets are empirical estimates of V,. In particular, if we let (Du (2, a) (x, a) E C.) be the datasets in the definition of V/, in (15), then for any (2h-1,ah-1) e C₁, and (In, 2n) E D (I (n-1)) the target Uy satisfies
Uh (TN):
where V (2r) is an empirical estimate of V.T (xx) obtained by sampling Nest((Cal) Nest (k) episodes (for N-st(.) defined as in Algorithm 5) by rolling out with मे after starting from & and playing action a at layer h; note that [Cxl & because we are considering the kth call to RVFS,, Thus, by Hoeffding's inequality and the union bound over (#t-1, 1.-11) C₁ and (.h, (x ah-1), there is an event E,A (Sx) of probability at least 1 - 8/88" H) under which
((Th- ah-1) E Cb. V(TN, -) Din ah-1):
2log(8|CA Hk218) Nest(k)
2 Hk3315)
( H
(39)
Nesc
52

---

where Nreg is as in Line 5, and the last inequality follows by |Cal S lt since we are considering the kth call RVFS,. Thus, under ki have
((-h-1,0-1)) Ch. (zz, 2h) Dn (I
(1221))
H
IV (x)) - un un V 2c, (Ia)) $ H
S
(40)
(k)
Nreg
where the second to-last inequality is by (39) and the last inequality follows by the choice of Nest in Algorithm 5.
Bounding the discrepancy VØ the value function V satisfies:
V.
On the other hand, by the performance difference lemma,
H (f
E -2)
E
=I],
r=h
H
E [ - (x,,, [.)),,(())))))) 2, =x]
(41)
r=h
Now, let 1 a (- ( ,.... denote the elements of Cn in the order in which they added to the latter in Line 15. By Lemma C.2 (Freedman's 's inequality) instantiated with
n Nreg
w; (x V (ax LUV (xx)) V (2n)) 3h-1 x15) 1 0/-1 (i for
all i [n] and j Li/Nregl + 1, where 2f (NNe)) 1, (N Nret 1) Ltd.
Th( Øh-1
(6) h-11 ah-1 1
Hi o
o ) for all [n]]
R and
> 1/H:
we get that there is an event Ek (Sx) of probability at least 1 1 60(868/8881))) 11-((8xx((11))) HI1l') under which:
Σ
Σ
(Ix) V (xx)
(z), 1: ,)ED (a.,
2.Nreg
Σ
E[ (*h) V (xx)) 0h Th-1, an-1 an-11+ H (01(8)((1(1110)
H E
< 22H 2HH
Σ
@h-1 Th-1, ah-1 ah-1] + H1 log (0000(8821110 (T.))
(18)),
(Zh-1 JED,
(42)
where the last inequality follows by (41) and the law of total expectation.
Regression guarantee. Since IT' IIş and Assumption I.1 holds, Lemma C.5 (regression guarantee) instantiated with
Vz))
B = H;
b. Uj VH. (m+) (where U; maxasA @ (Thh, and
{ H;;
53

---

implies that there is an event E,,,, (Sx) of probability at least 1 - 6/(422 have:
H -/((2H2111')
under which we
Σ
Σ
(Vr(x))) V/ (xx))²
Noeg (Enn))DDa( 2(n-1) (oo 1.11-11)
2 log(Ak2 1111111111)))
4H
Σ
Σ
1V (Ix) Unb
Nee
Nreg (en-1-0h-1188 JeCa ((n
4kH log((A HITI))))))))
4H
Σ
Σ
11 (In) - unl
Nreg
Nrea (h--) vn,,,,))Di (#1-1 (B
4H
E
Σ
(xn) (z+)))
(z+)),
(43)
Nreg (2n-1.9h-1 )EC (a Da (a--1)a--1))
where the last step follows by the triangle incquality. Thus, by plugging (42) and (40) into (43), we get that under (Sx) Eir KK,,, (Sx) n T
1
Σ
Σ
(Vn( (2+))
(#h-11mh-1)EC, DeCh Nreg (eD 9kH log(Sk, Sh2 H1T1)1111))
<
8H2
Σ ΣE (e)((
-n-11 24-1, a a4-1].
Nreg
(m) 1 1)C
(44)
Applying the union bound to conclude. Let Sy k be the random state of RVFS, during the kthh call to RVFS, and immediately before Line 20, i.e. immediately before gathering data for the regression step in RVFS,- Further, let S be the random state of RVFSo during the t call to RVFS, and immediately before Line 26, i.e. immediately before the regression step in RVFS If RVFS, terminates before the ttth call to RVFS,, we use the convention that S = S = t, where denotes a terminal state, and
define EK, (t)
G En (t) En (t) {t). Further, we define
EX
I(St E (Sx) n xeN,
πI
TH E (8x) n 54 (S (Sx)
Note that by the argument in the sequel and the union bound, we have that
Th vk 1, Vp, S (Sx) n Eh (Sx) & (Sw)) 2k²H
(45)
where Sy. denotes the state of RVFSa during the hthh call to RVFS,, and immediately before Line 20. By letting S S/...... denote an identical, independent copy of the sequence S1,, we have by the chain rule:
P[E]] Es, s....
Il P[S (St) n E (Sx) nk, (Sk) S = 5%,] k>1
(by (45))
2R22
kel
8
1
(46)
H
where the last inequality follows from the fact that for any sequence -2, (0, 1), have N (1 x4) 2
Σς Fg. Combining (46) with (44) implies that EY gives the desired result. [
1,5 Proof of Lemma I.4 (Guarantee for Confidence Sets)
To prove Lemma 1.4, we need one additional result pertaining to the order in which the instances (RVFS)) are called.
54

---

Lemma 155. Let h E [O.. H] be given, and consider the setting of Lemma 1.4. Further, consider call R. V. E, that terminates, and let h [H] be any layer such that RVFS,, is called during the execution of RVFSg. Then, after the last call to RVFS,, terminates, instance of RVFS in (RVFS,)r>h is called before RVFSa terminates.
Proof of Lemma 1.5, Suppose there is an instance of RVFS in (RVFS,) that is called after the last call RVFS,, terminates. Let T > h be the lowest layer where RVFS, is called after the last call to RVFS;, terminates. Let RVFS,at denote the corresponding instance of RVFS,. Further, let < T be such that RVFS; is the parent instance of RVFS,ast (i.e. the instance that called RVFS Note that we cannot have = as this would imply that an instance of RVFS), terminates after RVFS and we have assumed that RVFS terminates after the last call RVFS,, is also not possible to have L as this would imply that T is not the lowest layer where RVFS, is called after the last call to RVFS,, terminates. Thus, we must have that h. Now, the for-loop in Line 16 ensures that that there an instance of RVFS, that is called after RVFS terminates and before RVFS; does. This contradicts the assumption that RVFs is called after the last call to RVFS,.
Proof of Lemma L.4. We start by showing that á E Ia by constructing the corresponding collection of random state-action value functions [2 (z, a) (. c [0, HJ in the definition of II In particular, for (h, E [H] x x A. we define
(z,a,)
if Q2,-) -P h+ 12,, 4e, for h = H....,1 1. otherwise,
Qx( = [v h-1 (x,
where (x, a) = P--------- o (I, Note that @ (2. a) only depends on the randomness of P Ph.,.o-(V [I,, and so (Qn a)) (1)).)) are independent random variables. Further- more, since PA P.[Vi 07 we have that
V(z, a) E Xx A,
az) - -aataa---((TT, 54.
Finally, since (-)+) arg max Qn(,
have that स e IT
We show V e Dn- We prove that V Dh, for all E (H) under the event Edd Eng n.... En & where &, (E)), and (Eg) are the events defined in Lemma I.1, Lemma 1.2, and Lemma I.3, respectively. Throughout, we condition on E First, note that by Lemma 1.1, RVFS, terminates. Let (VER, ViSH CL.H B (1:H) ) be the tuple returns.
We will show via backwards induction over l H 1,..,,,, 1, that
v e Ve,
(47)
where 71. is the stochastic policy defined recursively via
T. (I,,), if -P. |bx 45, for H. H, otherwise,
म (x) arg max aEA
az)
where (x) == P- . (xr,).)).a).
Base case [f = H 1]. This holds trivially because VH+1 for any π E IIs by convention.
General case [e < HJ. Fix h [H] and suppose that (47) holds for all & E [h+ + 1.. + 1]. We show as a consequence that (47) holds for é= h. First, note that if RVFS, is never called during the execution of RVFS,, then D/,- V, and so (47) trivially holds for E = h under Assumption I.1 with Ereal 4s.
Now, suppose that RVFS,, called at least once, and let (VH.. VisH.C Ci. Bisu t be the output of the last call to RVFS,, during the execution of RVFSg. We claim that
(Vitn Dia Ci.H) (Vr.t, ChaH).
(48)
To see this, first note that the for-loop in Line 16 ensures that no instance of (RVFS,) can be called after the last call to RVFS, (by Lemma 1.5). Thus, the estimated value functions, confidence sets, and core sets for layers h 1,...,I H. remain unchanged after the last call to RVFS;; that is, (48) holds.
55

---

Thus, by Lemma 1.2, and since we are conditioning on E we have that for all (2h-1, an-1) Cr. and E [h + 1.. 1]:
Alog(8.M)
test
10)
p
sup max (Pe-l PP-Ll//)-Pe-lfi((tee....... 35 0h-1 = Th-1, Oh-- a/-1 feD, and
N
(49)
H. Now, by the induction hypothesis, we have V e Ve, and so substituting where M 18E- Cuun
V for ft in (49), we get that for all (Ih-1, ah-1) Cn and [h H 1]:
4log(8M No test
18)
max DEA
-
35 2h-1 2h-1, ah-1 = an-1 <
Ntest
Therefore, by Lemma I..1 (instantiated with s4[-] [ 2h-1 14-1, 0h-1 an-11, 1, and
V++ v, we have that (Ih-1, 0x-1) CA and & E [A + 1.. H. + 1]:
4log(8MM (est H*)
E²
Men (e- #h-1 Fh-1, a4-1 an-1]s
Ntest
(50)
where 8' is as in Algorithm 5.
Applying the regression guarantee to conclude the induction. Note that E II' where c IIs the set of stochastic policies such that II' if and only if there exists VaS V such that is defined recursively as
(x,o) = & [V++](z,,,, if P.. SE., otherwise,
T=: arg max asAA
P.[V
P T,,,8 [V+11[[ The policy class 11' is finite and [LI'| s V Furthermore, we have IT' S IT as shown at the beginning of this proof. Therefore, if we let (Da(2, a): (I, a) 3 be the datasets in the definition of 1/, in (15), we have by Lemma I.3 (under Assumption 1.1 with Ereal 45) and the conditioning on E 1:H and E:
T == H,... where Q- (x.a)==
Σ (2h-118h-1)Es )aC, Nreg (on-))EDa (2h-11000000 ab-1) (11P1))))))))))))
Σ
(Vi(Tn) - V (xx))²
9/Ca|112 log(S)C., 11 8H2
Σ
Σ E (I, xh-1 Zh-1, 11-1h1])
<
Nreg
(m1- 1)sC,, 7wh
9M log 212318))
H
8H2
Σ
D
0h-1 Th-1, ah-1 an-1],
Nreg
(ah-189)- 1:
JCC,
(51)
where the last inequality follows by the fact that [Crl M under & Combining (51) with (50), implies that
Σ Nreg (sn.-)eDu(zn, 1.91-1)
Σ
( - (xn))²
(I4-1,00 1)CC
9MH 1ogMH 8MM3. 4log(8M²'2
test H110)
+ +8MH38
Nreg
N Ntett
4log N2 test 11/1)
8
SMH.
8MH3
Nreg
Ntest
4M N2 test H
5 <
(52)
where the last inequality follows by the fact that d (0,1) 1) and the definition of e in Algo- rithm 5. By the definition of Dr (15), (52) implies that V Dh, which completes the induction. 0
56

---

16 Proof of Theorem 1.1 (Main Guarantee of RVFS)
Proof of Theorem I.1. We condition on the event = & n E" ng n E.H where &, E" and (E)) are the events in Lemma II1, Lemma I.4, and Lemma 1.2, respectively. Note that by the union bound, we have P[ž] 2 1 56. By Lemma I.2, we have that
Alog(8M<22 Anst H 16)
vh E [H],
p
sup max (PP==11Al-PP-(At)))ee....... feVn and
S
Ntest
(53)
where M = ( H| and Nestt 22 1f On the other hand, by Lemma 1.4, we have
Vh [H];
VI e Dn.
Thus, substituting Vi2t for fr. in (53) we get that for all h [ 1].
4 Alog(8M 2 Nlest 18)
max and
35
Neest
This together with Lemma L.1, instantiated with nl-] = 10x 8' as in Algorithm 5), translates
T V++1 v and ò = 8' (with
4 Alog(8M*N2 test H8 + E. [²[Dvv ( (a.)) az (xx))]
vh [H],
Ntest
4 log(8M
N2 H$18) Test
5
Ncest
4M N2 Nest H
4H3
where the last step follows from the fact that Ntest 2 23 " Ho in Line 3).
(with M as
Bounding the sample complexity. We now bound the number of episodes used by Algorithm under the event E. First, we fix h é [H], and focus on the number of episodes used within to call RVFS,, excluding any episodes used by any subsequent calls to RVFS, for T > h. We start by counting the number of episodes used to test the fit of the estimated value functions Vh+I-H Starting from Line 8, there are for-loops over (0h-1,ah-))
H H...., h and n E [Ntest] to collect partial episodes using the learned policy म in Algorithm 5, where Ntest 2 M He (8 3 22 and M [8 "Cushh H.. Note that executing म re- quires the local simulator and uses Nsin 1og (0og(4M N (( local simulator queries to output an action at each layer (since Algorithm 5 calls Algorithm 7 with confidence level 8 N/(8M" ( ())). Also, note that whenever test fails in Line and the recursive RVFS calls return, the for-loop in Line 8 resumes. We also know (by Lemma I.1) that the number of times the test fails in Line 14 is at most M. Thus, the number times the for-loop in Line resumes is bounded by HM; here, H accounts for possible test failures across all layers [h + 1 H). Thus, the total sample complexity required to generate episodes between lines Line and Line is bounded by
Cr.
# episodes for roll-outs
MH
M 2 L Ntett N
(54)
of times Line resumes
Sample complexity case no failures
Note that the test in Line 14 also uses episodes because it calls the operator P for every A. Thus, the number of episodes used for the test in Line 14 is bounded by
# episodes for the tests s
MH
MHAN Nuin
(55)
# of times Line resumes
Sample complexity for Line
We now count the number of episodes used to re-fit the value function Line 16 and onwards. Note that starting from Line 16, there for-loops over (IN-1, 0h-1) C₁, and i e [Nreg] to generate A Nest((C,, ((Cx.) s A (.st((MM partial episodes using स. where Nest (k) 2
reg log (
57

---

is defined as in Algorithm 5. Since मे uses the local simulator and requires Nest samples (see Algorithm to output an action at each layer, the number of episodes used to refit the value function is bounded by
# episodes for V-refitring & M Nreg ANest (M)
(56)
Therefore, by (54), (55), and (56), the number episodes used within a single call to RVFS), (not accounting for episodes used by recursive calls to RVFS,, for T h) is bounded by
episodes used locally within RVFS,, & M (HH NeNtestt + A.ee (M)
(57)
Finally, by Lemma I.1, RVFS, may be called at most M times throughout the execution of RVFSq- Using this together with (57) and accounting for the number of episodes from all layers h E [H]. we get that the total number of episodes is bounded by
M H² (H + A)Ntest Nei + M2 Nreg
Substituting the expressions of M, Ntest, Nest, Nsins and Nreg from Algorithm 5 and Algorithm 7, we obtain the desired number of episodes, which concludes the proof.
1.7 Proof of Theorem I.2 (Guarantee of RVFS.bc)
Proof of Theorem I.2. Let VisH be the value function estimates produced by RVFS, within Al- gorithm 6, and let # #RV (.) arg max P Ph.swes&8 [V,+)](,,), for all h e [H] with VH+1
with SaVEs and 8' as in Algorithm 6. Further, let and let #1: é IIş be the stochastic policy defined recursively via
az. P+[ P.[V%
if (x,)) Pr P.[V 1 [2, s 45
Vx E X, t.(1)) E arg max
(58)
otherwise,
anA
for r H,... 1, where Qr a) = = Priemss (x, By Theorem L.I, there is an event & of probability least 1 6/2 under which:
ने E 1l4emms
(59)
and
vhe [M],
ET
RVFS Div Th ( (In),, ,, कn (xx))) AusSh 41
SRVFS
8
(60)
where the last inequality follows by the choice of ERVES in Algorithm 6.
For the rest of the proof, we condition on E. By (59), (63), and Proposition M.1 instantiated with Emis = 0 (due to all x-realizability), we have that there is an event Er of probability at least 1 8/2 under which the policy Ris produced by BehaviorCloning ensures that
J( (RI.H)
(61)
Now, by Lemma C.6 (the performance difference lemma), we have for A as in (58):
- -J
RVFS
[ (xx)) Q (ax,, RRFF (*))))
A=1
H
< H
Σ
hits
[Div
RVFS ( t (xn))
h=1
and so by (63), we have
J( ( RVFS $ e/4.
(62)
Finally, since ग E Isness (see (59)), we have by Lemma H.l,
J(a') - J(+) s 12H ERVFS $ se/4,
where the last inequality follows by the choice ERVFS in Algorithm 6. Combining this with (61) and (62), we conclude that under En ;
J( ( SE.
By the union bound, we have P(ĚngT 2 1 8, and so the desired suboptimality guarantee in (28)
holds with probability at least 1- 6. 6.
58

---

Bounding the sample complexity. The sample complexity is dominated by the call to RVFS, within RVFS.bc bc (Algorithm 6). Since RV calls RVFS with EavES =H /48, we conclude from Theorem 1.1 that the total sample complexity is bounded by
Ô (C 113 (/23A A E
L
J Guarantee under V -'--Reaizzaiiliyy (Proof of Theorem 4.1, Setup I)
In this section, we prove Theorem 4.1 under Setup (V* / -realizability (Assumptions 4.2 and 4.3) and A-gap (Assumption 4.4)). We prove this result consequence of the more general results (Theorem 1.2) in Appendix by appealing to the relaxed V"*-realiabbility condition in Assumption I.1.
J.1 Analysis: Proof of Theorem 4.1 (Setup I)
begin by showing that Assumption 4.2 and Assumption 4.4 together imply that Assumption holds for any Greal A/2; we prove this by showing that the benchmark policy class IT (Ap- pendix H.2) reduces to {T") when E' A/2.
Lemma J.1. Assume that V satisfies Assumption 4.2 (V* -realizability), and that Assumption 4.4 (gap) holds with A Then, for all e' A/2, we have II. {x*} and V satisfies Assumption 1. with Creal E
Informally Lemma J.1, whose proof is in Appendix J.2, states that under Assumption 4.2, Assump- tion 4.4 with A > O, and Assumption 4. (pushforward coverability) with Cpush O, we are essentially in the setting of Theorem 1.1 (guarantee of RVFS under relaxed V V""-ralizabilityy, long as choose Greal & A/2. With this, we now state and prove a central guarantee for RVFS under V* -r-rralizabilityy with gap.
Lemma J.2 (Intermediate guarantee for RVFS under Setup I), Let ô E (0,1) be given, and suppose that:
Assumption 4.1 (pushforward coverability) holds with parameter Opush > 0:
Assumption 4.4 (gap) holds with parameter A > 0;
The function class V satisfies Assumption 4.2 (V* rrealizabbilly)))
Then, for any and (0, with probability at least 8, FVF (Algorithm 5) terminates and returns value functions VaH that satisfy
vh E [H] 1 (T))) m (x))s
4Cpuss H3'
where (z) é arg max Pr. (V, for all he [H], with 8' is defined as in Algorithu 5.
Proof of Lemma J.2. From Lemma J.1, have that IT (x²) and Theorem 1.1 implies that with probability at least - 5,
Vh E [H].
2 E [Div (Tt T (xx)) - (#n(xN) (TTh)))))))))))) # क, (xx)),
4C 4Cpush H1
where the equality follows by the fact that x is deterministic.
From here, Theorem 4.1 follows swiftly as a consequence.
Proof of Theorem 4.1 (Setup I). Let Vi-H be the value function estimates produced by RVFS, within Algorithm 6, and let * *.)) arg max Ph,cwess & [Vr+1 (::))(;a) a), for all e [H] with V
with ERVES and 8' as in Algorithm By Lemma J.2, there is an event E of probability least 1 8/2 under which:
T (xx) (xx))
ERVES
(63)
4H3Cpush 4H2
where the last inequality follows by the choice of Eaves in Algorithm 6.
59

---

For the rest of the proof, we condition on E. By (63) and Assumption 4.3 (T* -realizabbillyy) the policy
#RVES returned by RVFS, satisfies the condition in Proposition M.1 with Enis = push Thus, by Proposition M. there is an event E¹ of probability at least 1 - 8/2 under which the policies R1F produced by RVFS. be satisfy
J U RVSS LH
((T
8
38 2
H
We now condition on & E By Lemma C.6 (performance difference lemma), have
J(T")- - ((
E
10% (0h, M (xx)) Q% (æh, Th (xx))
H
P
n (xn)
(xn))
where the last inequality follows by (63).
Finally, by the union bound, have TP E' 1- 5, and so the desired suboptimality guarantee in (28) holds with probability at least
Bounding the sample complexity. The sample complexity is dominated by the call to RVFSa within RV (Algorithm 6). Since RVFS.bc calls RVFS, with == SavFS = eH-1/48, we conclude from Theorem I.I that the total number of episodes is bounded by
δ (Cpussh 2 A. A.
Bounding the number of oracle calls. We now bound the number of calls to the oracle described in Remark 4.1 that RVFS makes. To do this, note that bounding the number of calls the oracle is equivalent to bounding the number of executions of Line 14 in Algorithm 5, or, equivalently, the number of times the operator P in Line 14 is invoked during the entire execution of RVFS, including all subsequent recursive calls RVFS The proof of Lemma I.2 establishes a direct bound on the number of times the operator P is called, giving an upper limit of D(Cpusn-Vrest = where Ntest is polynomial in the problem parameters (see Algorithm 5) and does not depend on X.
J.2 Proof Lemma J.1 (Relaxed V Reaaiiizabiility under Gap)
Proof Lemma J.1. Fix e' 10 and क Hg. Let (@ (z, ((..: be independent random variables such that
Ah E [H], T+)+) arg max a'))a)) and 1 - Q 0m SE', almost surely. d'EA
Such collection of random state-action value functions (Q,(I, (z),a)))(,..o (ha.a)))1)))))> is guaranteed to exist for pi by the definition of IIg. We will show via backward induction over 8 H 1,..., that
Vx Xe, (T(x) = T (I)
(64)
almost surely, with the convention that TH+1 = Tit+ Tunif. This convention makes the base case, = H hold trivially.
Now, we consider the general case. Fix é [H] and suppose that (64) holds for all é e [h + 1., H + +1]. We will show that it holds for l h.
Thanks to the induction hypothesis, we have for all x Xha and e A:
(i+n()) Vit (x),
and so
= = PALVinl V/ Fix E X. We will show that (x) (x) almost surely. Note that thanks to (65), the fact that Q -TAQQ Illloo 5 gl almost surely, implics that
(65)
1 - 1illoo S'',
60

---

almost surely. Using this, we have, almost surely
(T)) Qn (z, (n))
(z)) -t',
(7 (x)) - =((() A.
(66)
On the other hand, if (T) # n (x), then
Q zz nA (1{,,, AA
which would contradict (66). Thus, nu (x) n (2), which concludes the induction and shows that = π.".. We conclude that M. }
K
Guarantee for Weakly Correlated ExBMDPs (Proof of Theorem B.1)
In this section, we prove Theorem B.1, I, the main guarantee for RVFS First, in Appendix K. we state number of supporting technical lemmas and use them prove Theorem B.1. The remainder of the section (Appendix K.2 through Appendix K.6) contains the proofs for the intermediate results.
K.1 Analysis: Proof of Theorem B.1
Recall that the the V V*"realizabilliy assumption required by RVFS for Theorem 4.1 not satisfied in ExBMDPs, as the value functions for policies that act on the exogenous noise variables cannot be realized as a function of the true decoder Φ" In RVFS we address this issue by applying the randomized rounding technique in Line 11 to the learned value functions. The crux of the analysis will be to show that for an appropriate choice of the rounding parameters Ç1:Fr, the policies produced by R are endogenous in the sense that allow us to leverage the decoder realizability (Assumption 3.3), which implies that the function class VI.H given by
write π (x)) x (66 (x)) for all æ X. This will
V4 { f((=)) : f [0, H1S o Φ)
(67)
satisfies V rrealizabiilty for all endogenous policies n.
In what follows, we first motivate the randomized rounding approach in RVFS in detail and prove that it succeeds, then use this result to proceed with an analysis similar to that of Theorem 4.1 (Setup I), re-using many of the technical tools developed for Theorem 4.1.
K.1.1 Randomized Rounding for Endogeneity
Naively, to ensure that the policies execute endogenous, it would seem that we require knowledge of the true decoder の² Alas, knowing ø trivializes the ExBMDP problem by reducing it to the tabular setting. To avoid requiring knowledge of ø², apply randomized rounding the policies learned by RVFSex0 to ensure their endogeneity.
Let E O be fixed going forward. Recall that compared to RVFS, RVFS (Algorithm 8) takes additional input Ç1:H c (0, 1/2) and executes the following coarsened policies:
F (.) arg max aeA
Ph,,,, (P.... Cal.
The rounding parameters ÇL.H. which can be thought of offset, are chosen randomly; this will be elucidated the sequel.
Following similar analysis to Appendix (Setup II), we can associate near-optimal benchmark policy स e Il with order to emulate certain properties the A A-gap assumption. particular, generalizing the construction in Eq, (27), we define near-optimal benchmark policy क recursively via:
(x, G7.. (2
if otherwise,
loo s 4c
Vr e X, it, (x: (1HH,, arg max A
(68)
for H 1, where ax(aa)= P ()))(.))).
61

---

Naively, to use the benchmark policy म within the analysis based on relaxed V V*-realizability (As- sumption I.1) in Appendix I, we would require the function class V realize (V% ). However, as argued earlier, this is not feasible unless गे is an endogenous policy. Fortunately, it turns out that if S1:11 (the additional input to RVFS are drawn randomly from uniform distribution over [0, 1/2], then with constant probability, ä is indeed endogenous. What's more, under such an event, and for all possible choices of (V,) in (68) uniformly, i "snaps" onto the stochastic endogenous policy ((s (i:we)) defined recursively as follows:
TA (iHH,) E arg max PA PML (ttl Cals
(69)
acA
for H,...,,. Informally, this happens because, as long as fI-H (0.1/2) avoid certain pathological locations in (0.1 the coarsened state-action value functions E --[P-[ [zz a)/s Ch defining exhibit a "gap" of order O(=²) separating optimal actions from the rest. This "snapping" behavior is analogous to what happens in Setup I with V* -reaizaability and A-gap. where II, reduces to (xr) for all & < / (see Lemma J.1). We formalize these claims the next two lemmas. We start by showing that म is endogenous and that स 22 The proof is in Appendix K.2.
Lemma K.1 (Endogenous Benchmark policies). For any ê ε (0, 1), S e (0, 1/2), and CL:H c (0, 1/2), the stochastic policy (1; &) defined in Eq. (69) is endogenous, and we have #(: (I.r,)) 1125-
Next, we show that से "snaps" onto हt for the certain choices of S1.H. The proof is in Appendix K.3.
Lemma K.2 (Snapping probability). Let 5 E (0.1), E E (0, 1/2) be given, and PS denote the probability law of CH. ~ unif([o, 1/2]). Then, there an event Erand of probability at least 1 24SAHI under Ç1:H ~ PL such that for all V (X [H] - [0. H]) simultaneously.
Whe [H], #n(:V V, E, = #n( S):
where T (vV S.,.,,,,,E, defined as in (68) with V = V, and defined as in (69).
The lemma together, with Lemma K.I, implies that with constant probability under FP, the benchmark policies (T%) used in the analysis of S are endogenous and satisfy स 1lls.
K.1.2 Pushforward Coverability
In order to proceed with the analysis strategy in Appendix I, we need to verify that pushforward coverability satisfied for ExBMDPs under the weak correlation assumption. We do in the next lemma; see Appendix K.4 for a proof.
Lemma K.3 (Pushforward coverability). A weakly correlated ExBMDP with constant Cexo (see Assumption B. satisfies Bushffraso coverability (Assumption 4.1) with Cpush Cexa S.A, where S E N is the number of endogenous states.
Equipped with the preceding lemmas, we proceed with an analysis similar to the approach for Theorem 4.1 (Setup II) in Appendix I. In what follows, state number of technical lemmas that apply the relevant results from Appendix to the ExBMDP setting we consider here.
K.1.3 Bounding the Number of Test Failures
Since the size of the core sets CI.Hr in RXFS is directly proportional to the number of test failures, the next result, which bounds [C,] for all h e [H], allows us to show that RVF (Algorithm 8) terminates in polynomial number of iterations.
Lemma K.4 (Bounding the number of test failures). Let 8, (0,1) and CL-H [0, 1/2] be given, and suppose that Assumption B. I. (weak correlation) holds with Cexo > Let f E V, be given, where V is an arbitrary function class. Then, there is an event & of probability at least 1 1- 8 under which the call to RVF RVFS (f, f, y! 20200000 0; V,V,e (1.H, (Algorithm 8) terminates, and throughout the execution of RVFS we have
CCal S Coxo
Proof of Lemma K.4. The results follows from Lemma K.3 and Lemma I.1.
62

---

K.1.4 Value Function Regression Guarantee
next give a guarantee for the estimated value functions VI-H computed within RVFS Line 26 of Algorithm 8.
Lemma K.5 (Value function regression guarantee). Let Let [O.. H), 8, (0, and ÇL- [0, 1/2] be given, and consider a call to R in the setting of Lemma K.4. Further, let V be defined as in Eq. (67), and assume that satisfies Assumption 3.3. Then, for any endogenous policy x Hss there is an event Eg of probability at least 1 - 8/ H under which for any k 1, if
RVFF gets called for the kth time during the execution of RVFS and
this kth call terminates and returns (Vnet, Vnats Cratt, B .l.1)..
then if (R2) is the policy induced by VICH and Nreg is set in Algorithm 8, we have
Σ
1
Σ
(vn( (z)))
Nreg (an.)
(In-1 De.
(En-))-D
9kH2 log( H(V/6)
" E (Dr
8112
Σ
T., Øh-1 24-1, ah-1 ak-1]
Nreg
(#h-1 (0--1, T-h
where the datasets (D, (x, Cr3 are as in the definition of Vn in (16).
Proof of Lemma K.5. Since & satisfies Assumption 3.3, the function class V Vi. satisfies V r"-realizabillty for all endogenous policies (see Lemma D.1). Thus, the proof of Lemma K.5 follows from that of Lemma 1.3 (see Appendix 1.4).
K.1.5 Confidence Sets
We now state version of the confidence set validity lemma (Lemma 1.4) that supports the ExBMDP setting.
Lemma K.6 (Confidence sets). Let (0,1/2) and GaH c [0, be given, and suppose that
Assumption B.1 holds with Covo
The decoder class & satisfies Assumption 3.3;
S1.H e Erand, where Erand is the event in Lemma K.2.
Let E V be arbitrary. There is event e of probability least 1- 35 under which call to RVFS
(,, (f,, that
2, SiH,, terminates and returns tuple (VLSH, VIHH CLH. BLHH (::) such
Vh e [H], where RIt is the policy defined recursively via
Vă Vn,
म, (x) E arg magmax(P2 ( (v, Gil, for -= H,..,,
(70)
aeAA
While the proof of this lemma is very similar to that of Lemma I.4, we need dedicated treatment to handle the rounding in RvF The fully proof of Lemma K.8 Appendix I.5.
K.1.6 Main Guarantee for Rx
We state the central technical guarantee for RVFSexo, Lemma K.7, which shows that the base invocation of the algorithm returns as long as the randomized rounding parameters Ç1-H satisfy Ç1:H Erana, where Erand is the success event Lemma K.2. The proof of the theorem is in Appendix K.6.
of value functions ViSH that induce near-optimal policy म.
Lemma K.7 (Main guarantee for RVFSeX0), Let 8, (0, and (a. c [0, 21 be given, and suppose that
Assumption B.1 holds with Coxa 0:
The decoder class & satisfies Assumption 3.3;
S1-H Erand, where Erand is the event in Lemma K.2.
63

---

Then, for any f & V. with probability at least 1 56, a call to R (Algorithm 8) terminates and returns value functions VL. such that
E²
vh [H],
( # Tn ( AHeo
where Rn (2) E arg max I e 8 [V-11 o)/e+ for all h é [H], is defined in Eq. (69),
and 8' is defined as in Algorithm 8. Furthermore, the number of episodes used by RVFS is bounded by
( S 1 1 6 e-20).
K.1.7 Concluding: Main Guarantee for RVFS .bc
To conclude, we prove Theorem B.I, which shows that RVFS bc succeeds with high probability, Recall that RVFS bc (i) invokes RVFS multiple times for random samples Ç1:H1 to ensure that the success event for Lemma K.7 occurs for at least one invocation, and (ii) extracts an executable policy using behavior cloning. Regarding the former point, note that the probability of the success event
of Lemma K.2 can be boosted by sampling i.idd (( S1:H..... ((m) ~ PK inputs to RVFSexo for n 2 1; as long as n polynomially large, with high probability at least one the inputs ((t) S1:f:-...; S will satisfy the conclusion of Lemma K.2. Thus, it suffices to pick the policy with the highest value function among the different calls to RVFS Using this, we prove Theorem B.I.
Proof of Theorem B.1. Recall that Algorithm 9 picks the final policy (ffer) based on empirical value function estimates. In particular, for every i [NNeoot]] (with Nboost in Algorithm 9), the estimate J( for [ is computed using Neval episodes. Thus, by Hoeffding's 's inequality and the union bound, we have that there an event & of probability least 8/4 under which -(#
Vie [Nooost]
|J
I:H ) 2 (2Nboootttt////// //
Therefore, by definition of hopt in Algorithm 9, we have that under E:
ViE [Nooost]
J J s (= 2 2og (ellog((Noosssee
S {( ) +/8,
(71)
where the last inequality follows by the choice of Neval Algorithm 9, On the other hand, by Lemma K.2, there is an event & Esuccess of PK PS-pobbability at least
1 (24SAHe) Nucout 2 21-6/4 6/4 (by the choice of Nboost in Algorithm 9)
under which there exists j [Nooost]] such that Gi-F E Erand, where Eaadd is defined as in Lemma K.2. In what follows, we condition on the event gsuccess and let j E [NNoost]] be such that ((3) 6 Erand #RVFS to denote the policy returned by the instance of RVF that is used by Further, we use I1H R bc to learn 20 1:#
By Proposition M.1 (instantiated with émis = 0), there is an event E of probability at least 1 - 6/4 under which the policy #0) produced by BehaviorCloning satisfies
( J ( 2
(72)
By Lemma K.7 and the fact that Sid Eaad, there is an event of probability at least 1 - 8/2 under which:
vh [H], vh [H],
1 (T)n(())) n. (xn))
FRVSS
(73)
2
where # #(-) == #(: (t)) S14 EREES which is defined in (69).
Moving forward, we condition on EnE By Lemma C.6 (the performance difference lemma), we have
RVFS
(xx)) Q (In, क (x)))(()))) (xx)))
A=1
H
s H
Σ
p (*x)) # # (xoh),
h=1
$ e/4,
(74)
64

---

where the last inequality follows by (73). Now, by Lemma K.I, we have π é II 2eans and so by Lemma H.1,
-( J(+) s GHervs & 8//8,
(75)
where the last inequality follows by the choice of ERvrs in Algorithm 9, Combining (75) with (71), (72), and (74), we get that
J(x J( J(T')=]===))))))) J( )
S.
Finally, by the union bound, have FL PLEnEnE 1- and the desired suboptimality guarantee holds with probability at least 1-
Bounding the sample complexity. The sample complexity dominated by the calls RVFS within RVFS .cc (Algorithm 9). Since RVFS .cc calls RVFS with suboptimality parameter ERVES = eH /48, we get by Lemma K.7 that the total sample complexity is bounded by
Ō O St 1136 . g-26).
K.2 Proof of Lemma K.1 (Endogenous Benchmark Policies)
Proof of Lemma K.1. Fix ō (0, 1). e (0, 1/2), and S. c [0, 1/2]. We show via backward induction over f= H I,... ...., that 7, &) is endogenous for all [e.. + 1], with the convention that #+1 Tunif- The base case holds trivially by convention.
Fix h [H] and suppose that the induction hypothesis holds for all & [h+1 1.. H 1J. We show that it holds for h. First, by the induction hypothesis, Te(: Fi. E) is endogenous for all & e [h+ + 1.. H]. Thus, there exists function fi-1: :5 - (0, - h] such that
(x))= fn-1 (x')), Va' e
Therefore, we have for all (I,a) 6 A:
PA[V Pa[Vita](z,a) rn (I, a) + E (o" (Ix+1) σ = a2=zz,0 =2 =a,
= (I. a) 1 (sh+1) I z, an aa]
(x, a) 1
= (z), a2 aa,
(76)
where the last equality follows by the ExBMDP transition structure. Eq. (76) together with the fact that the rewards are endogenous (by assumption) implies that there exists Ob. S A [0, H h such that
(<, E Xxxxxxx x A, PA[Va h+ [+, gn (z),
which in implies that [ V (xr, a)/E C. only function of through o' (I) for all A. Thus, n is an endogenous policy and the induction is completed.
For the second claim, observe that for the functions Q QH E [0, HJ defined as
Yh E (
(n. = [V,, 1(x a)/e 1h
we have
wh E [H]. (: arg (x(,o) and [ Q l00 s 22,
aeA
which implies that (sam))) 11ze.
Proof of Lemma K.2 (Snapping Probability) Proof of Lemma K.2. Fix 1) and 8 (0, 1/2). For f [H], let TP5 denote the probability law of Cr....,Ge. We also use the shorthand IPŞ for IP$ for all T [H]. We show via backward induction over = Hl + L,..., 1 that there exists an event & of 125 probbabity at least
K.3
1 1 A4H t 1)s under which for all V (X [H] H]):
VT [[..H]]
( V. 5,.,5,8) = n. (i)H.)))
65

---

with the convention that TH-1 ØH+1 = Tunir. We then set Erand = E1.
The base follows trivially by convention.
We now proceed with the inductive step. Fix h [H] and suppose that the induction hypothesis holds for all & [h+ 1.. H.. We show that it holds for l h. Throughout, we condition on Eλ-1- By
definition of Em-1, we have for all V (X x [H] [0, H)):
Vé [h+ 1.. H], Te(;
This implies that for all V (X [H] - [0, H]):
{
(1, a) / Cnls Ch],
if - (=, ((, s 4e2, otherwise,
Vo e X, #n (2: V. EI arg max aeA
by the definition nn in (68), where Qn(,,a) = Mhe [+ a). From this, we see that to prove TA (: V. (I:H,,,6) Fx (+ 51 for all V. it suffices to show that for all x X and V.
arg max Qz a)/=+ Cnl = arg max PA [M[Viia a)/= Sn whenever (Q,(x.a) - PA s asA
as
Observe that sufficient condition for this to hold is that 5 -..
Vx X. Va E A, v [-4=2,4e
+n
(77)
where 5 represents all the possible values that the difference @ (z, PA[V h+ 12,, a) is allowed take. By Lemma K.1, we know that is endogenous, and so there exists function Jb :S A [0, H h 1] such that
Vz aE PalVinn (")
Toward proving Eq. (77), observe that for any (s, S A, if Ch is such that
gn(s, + Cn 4s s (,, a / Cnl
(78)
and (n a)/a Sh 4e > [g a) e Cxl-1, 1,
then, for all 8 [-4=?,4e²] [=]] and all x X' such that o² (x) = we have
[(Ph[V/tn](,aa) 8)/= Cn (g)(s,a) 0)/= 4n (a,ss))/// Cn (PAVii Therefore, if we let (s, a) denote the event in (78), then under (ssa)eSxa &n (s, a), the desired condition in (77) holds. At this point, setting & (N( (s,ss a)) n Ek+1 would complete the induction long as [E,] 11-2445AFFF H h 1)c. We now show that this is indeed the case by bounding the probability the event (s.a)sSxA &n (8, By the union bound, we have
C%
pk h
(x, En+1 2 21 (x.a)sSxA
n
Σ (s,0)ESxd
h&H [En(s, a Ex+1]:
(79)
where En (s, a)) denotes the complement of (s, We now bound the probability
RuH [Ex (f) En+1]. Fix (8,0) S A. We have that Ca E a)) if and only if
(n ÇΛ 4E (s, Gul. (n(sa)) Cn 4e (g), Cal 1.
(80)
Now, since Ça E 1/2], Lemma L.3 (instantiated with (x, (gh a)/e, Sn. 4s)) implies that (80) holds only if
[g (x, /el - 48 S gn (s, Sn [9 a)/e] + 4e or 0 SA s 4s.
(81)
Further, note that since ÇA is uniformly distributed over [0, 1/2], the Pf probability of the event in (81) at most the sum of the lengths of the intervals
[[ a)/=l (s, a)/= 4e, [ (s,
and [0, 40],
66

---

multiplied by 2, which is equal to 24s. Therefore, we have Ph ()) Ex+1] < <Pf [[gn (8, a)/ 4e & gn (8,a)/e+ Sa s [g)( or 0. Ca 46) s 24c.
Combining this with (79), we obtain
n
(x E 21-
Σ Phe ( 2 24SAs.
(a.a)ESXA
(s,0)ESxA
Thus, by setting En = (Saa)ss a)) Eht1, we get that
F [n 1 [En+1] 1- P M Ex+1] 245 ( (A5
1 2----ASAAHHHH -h)
which completes the induction.
K.4 Proof of Lemma K.3 (Coverability in Weakly Correlated ExBMDP)
Proof of Lemma K.3, Fix [2.. HI] and define the measure 11 as
p(x)= c (o)( P(EA 5'] P( = 07 (x') 18h11 = 0h-1(a)) ah-1 =a]:
for all h & [[]] and x X. We show that satisfies Assumption 4. with Cpush = Cexo SA. First, note that y is indeed probability measure over X. Fix (x,,, X A X. We have
P[Z = x' 2h-1 = 2, ah-1 = a]
P(a, = -
ah-1
PP( x 0h-1 a)
P(æ, x²' 2h-1 = ah-1 =
P[z E.e a(' (*)())) 5)) g(x (0)-((x),{) P(s,, (x(x)) 8 ()-1(r), = ah-1
ExE g(x (x), P(s 1/-1(1)), (x),
En-1 =
and so by the ExBMDP structure:
Ex (a' (0)(2')))) q( (0 (z), Pl E {] P(sn = di (x)) 8h-1 ( an = a
Ex (z), P[ =
and by Assumption B.1
S Seeo Eg g(0' (d)(((())))))))) q(x (x), P(E. = C'. PIE P].PP[s, o1(()))) sh-1 (1) E]
E 1 (z)
= =Coo Egda' (0)(2') P(E, = 8'] P( 0j (x') 8h-1 Φ (z), a a),
812
= SA.
This completes the proof.
K.S Proof of Lemma K.6 (Confidence Sets)
To prove Lemma K.6, we need the following consequence of tests in Line 14 passing for all E [h + H..
Lemma K.8 (Consequence of passed tests). Let h e [0.. H), O, and SL.H [o, 1/2] be given and consider a call to RVFS (Algorithm 8) in the setting of Lemma K.4. Further, let E be the event of Lemma K.4. There exists an event E,, of probability least 1 8/H such that under E n E if a call to RVFS during the execution of RVFS terminates and returns (Vie DICH. CraH BRGH tiaH), then for any (Ih-1, 0h-1) e Cn and l 1 1.. +1]:
4 4log (MM N2
test 18)1)
p sup max
(Pt- - Pt-.lffe)((
35² 0h-1 Th-1, ah-1 ah-1
S
Ntest
[eD,
where (Tz) IIs, M, and Nrest are in RVFS (Algorithm 8).
67

---

Proof of Lemma K.8. This is just restatement of Lemma 1.2, and the proof is exactly the same as the latter.
We will also use Lemma 1.5; even though this result is stated in section for the -rerralizable setting, it is also applicable to the ExBMDP variant of RVFS as it merely says something about the order in which the (RVFS) instances are called. With this, now prove Lemma K.6.
Proof of Lemma K.6. The proof is very similar to that of Lemma 1.2, with differences to account for the "coarsening" of the learned and benchmark policies.
We prove the desired result for e" & E n E n.... E'g n where &. (E)), and (E%) are the events in Lemma K.4, Lemma K.8, and Lemma K.5, respectively. Throughout, we condition on E" First, note that by Lemma K.4, RVFS terminates. Let (VLH, ViHHi CL-H, B (::H) be its returned tuple.
We show via backward induction over 8 H + 1,...,1, that Vē Ve,
(82)
where RI is the stochastic policy defined recursively via
(r),
if ( P-[V (xx 1o00 S 46?,
Vo E N, te (x; CuHH,,,)) e, arg max a
Grb,
otherwise,
for r H...., 1, where (;,a) P Pr..ss P (,,a) Note that since ÇLH E Eand (for Eand is defined in Lemma K.2), we have ग n, where ह is in (70). Thus, instantiating the induction hypothesis with é = h and using the definition of the confidence sets (Vr) in (16) together with V,, V (since से = F) implies the desired result.
Base case [ = 1]. Holds trivially since V 0 for any π E IIs by convention.
General case [e s H}. Fix h [H] and suppose that (82) holds for all & E [h+ 1.. H 1]. We show that this remains true for = h. First, note that if RVFS is never called during the execution of RVFS then 1/, Vn, and so (82) holds for &= h, since म = R is endogenous under C1.H E E where Erand is the event in Lemma K.2.
Now, suppose that RVFS is called at least once, and let (Vi.g, Vie Ch B (hH) be the output of the last call RVFS throughout the execution of RVFS Next, show that
(VitH Vien Ch.) (VieH
(83)
The for-loop in Line 16 ensures that no instance of (RVFS can be called after the last call to RVFS (see Lemma I.5). Thus, the estimated value functions, confidence sets, and core sets for layers h + 1..., H remain unchanged after the last call to RVFS that is, (83) holds. Thus, by Lemma K.8, and since we are conditioning on E/ we have that for all (In-1, Cn and Le [h 1... H 1]:
4log(8M H2
pa
sup max PPaalWi-PPelff))eae... 35a xx-1 Th-1, ah-1 = ah-1 S
Ntest
feD
(84)
Now, by the induction hypothesis, we have V D/, and so substituting V for fe in (84), get that for all (zh-1, (0h-1,ah-1) 1) & Cn and E [h+ 1.. H + 1]:
4log(8M<N2 N2 Neett H7 11)18)
p max (Ptz [2] -p Pt 3ea and
0h-1 = Fh-1, a/-1 an-1
Noest
Therefore, by Lemma 1.2 (instantiated with y0-1] p 0h-1 Th-1, an-1 = a/-1),, t-1,
Th-1,0h-1
22, and V,-1 V,²), we have that for all (xy-1, 1)-1) Cn and le [++ 1.. 1]:
4 1lgg(8 N 11 (6) 8'. E (Tt क (x Bh-1 Th-1, 9 am-1]
Ntest
(855)
68

---

Now, since o (I-H,E) is endogenous and Ā т (thanks to ÇLH e &rand), Lemma K.5 (applied with π) and the conditioning on E imply that:
Σ
Σ
(vA( - V/2 (xx))²
(In-1: DECn Nrez (anr))ED (En-
9hH2 log(8k²
8H2 (822 HTVl/0)
H E (F., (x+)), #h-1 = 2h-1, ah-1 04-1)
<
Σ
Σ
Nreg
1el Twh
(86)
where the datasets (Da(x, a) (x, e C.. are as in the definition of Vo in (16), Combining (86) with (85), we conclude that
Σ
Σ
- (xn))
(2h-1 EC Nreg (en,- -eh.-)DDhhee JeDn (ah-)
9MH log/loogMMMM (8MP/1111 8MH 4log(8MNN N2 test H 18) 8MH38
Nreg
Niest
9M H log 1GMHHIIIN 8MH 4 4log(8M
N? test 1116)
8MH
Nreg
Ntest
4M
N HD
tast
Freg
(87)
where we have used that [Cal s M. By the definition of D/ in (16), (87) implies that V e Vho which completes the induction.
K.6 Proof Lemma K.7 (Main Guarantee of RVFS
Proof of Lemma K.7. We condition on the event E E n E n n... E/ where E, E" and (E)) are the events in Lemma K.4, Lemma K.6, and Lemma K.8, respectively. Note that by the union bound, we have P[g] 1 56. By Lemma K.6, have that
Alog(8MM N N
11
Yh [H)
sup max (Pa-1 (fa 35 fel and
Ntest
(88)
where M "ono SAH and Ntest 2 77 On the other hand, by Lemma K.6, we have
the [H]
Ví E Dr.
Thus, substituting V for fr. in (88) get that for all h [H 1].
4 1log(8M0)) N2
test H
max ae
(P [v.. PA- (V.
3
s
Nuest
This together with Lemma L.2, instantiated with n(.]] = p. [.] 8' as Algorithm 5), translates to:
h- 1; Vr+1
VAA and d = 8' (with
4 Alog(8M*N N2 test Hd +
vh [H),
E
Nrest
4 log( 8M1 22 Nest H818)))))))))
5
Nrest
4M7 N2 Ha|l'
< S
(89)
where the last step follows from the fact that Ntest M He " (with M as in Line 3). Now, since Ç1:H1 6 Erand (by assumption), Lemma K.2 implies that म, where the latter the deterministic policy defined in (69). Thus, by (89), have
Vh [H]. (T))) म. (xx)
(2W))) (T..) 41138AC.rO
where the first equality follows by the fact that P ((Tx(T) # (x) DAv. (1), Ry (x)), for all N, since n is deterministic.
69

---

Bounding the sample complexity. We now bound the number of episodes used by Algo- rithm 8 under E. First, we fix h E [ and focus on the number of episodes used within a to call RVFS excluding any episodes used by any recursive calls to RVFS for T > h. We start by counting the number of episodes used to test the fit of the estimated value functions Vh+1-H- Starting from Line 8, there are for-loops over (#h-1. ab-1)
Cr. L= H.....h+ 1, and n ε [Ntest] to collected partial episodes using the learned policy T Algorithm 8, where Neest = 2 M He log (0og(8807)) 225008""-0000000000 simulator and requires Nsin = 2 2oog(4M7 (4M N test H²1)//0)/2 samples to output an action at each layer (since Algorithm 8 calls Algorithm 7 with confidence level 8' = 6/((8M' Nest that whenever a test fails in Line 14, the for-loop in Line resumes. We also know (by Lemma K.4) that the number of times the test fails in Line 14 is most M. Thus, the number of times the for-loop in Line 8 resumes is bounded by H here, accounts for test failures for all layers T E [/+ 1.. H... Thus, the number of episodes required to between lines Line 8 and Line 11 is bounded by
and M = [8==2CexoS Se A.]. Note that тे uses the local
Also, note
# episodes for roll-outs <
MH
M MH N test Nsin
(90)
of times Line 8 resumes Number of episodes in of no failures
Note that the test in Line 14 also uses local simulator access because it calls the operator P for every A. Thus, the number of episodes used for the test in Line 14 is bounded by
# episodes for the tests S
MH
AMHANtest Nsin
(91)
of times Line resumes
Number of episodes used in Line 14
We now count the number of episodes used to re-fit the value function; Line 16 onwards. Note that starting from Line 16, there are for-loops over ((h-1,0k-1) Cn and i [Nrug] to generate A .Net ((Cx)) A Nest (Md) partial episodes using म. where Nest 2.22 reg log(SAINree is as in Algorithm 8. And, since म uses local simulator access and requires Nost samples (see
Algorithm 7) to output an action at each layer, the number of episodes used to refit the value function is bounded by
# episodes for V-refitting Ne (M
(92)
Therefore, by (90), (91), and (92), the number of episodes used within single call to RVFS (not accounting for episodes used by recursive calls to RVFS, for 7 > h) is bounded by
# episodes used locally within RVFS s M HH Ntett + M Mrog (M) H
(93)
Finally, by Lemma K.4, RVFS may be called at most M times throughout the execution of RVFS Using this together with (93) and accounting for the number of episodes from all layers h E [H) get that the total number of episodes is bounded by
2 (H+ N)Neest + 2 H2 Nres-
ANest (N) (M)Nsim-
Substituting the expressions of M, Ntest, Nest. Nsin. and Nreg from Algorithm 8 and Algorithm 7, we obtain the desired number of episodes, which concludes the proof.
L Additional Technical Lemmas
Lemma L.1. Let T [H] and 6,v e (0, 1) be given. Consider two value functions Vrss, Pras e [0, HJ and a measure p A(X) such that
l1 max [
P Pær-u
32 Sv.
(94)
aed
Further, for E X, let क (x(x) arg maxxed @x1 = P ( u) and inductively define randomized policy ã via
a),
( - PP. $ 4s,
(x) arg max A
P,
otherwise.
Then, we have
Ez,-ul DDv (x,),
70

---

Proof of Lemma L.1. In this proof, we let Pp denote the probability law of 2, and Pp denote the probability law of P T. Denote by & the -e-muuuuabble event that max -P:V-=))ee-V 32. Fix é E, and let &g be the Pe-mmasurable event that max P (.I.(lc,.))--/vvaall.....)) s 4e. From the definition of 7 we have that
(T, (T) (.)
Σ
Pr PP) ())
aed
Σ (,
[ (E, (x)
[..] Pp PP [ (x)
2 aed
$ acA
[x]
= (x)
(x)
(Jensen's inequality)
aed
and since Pp (2) P म E Va A, we have that
1 PolE
Pp (+)
8 Pr (x) [ 1.
2
<
Pp
[E]]
= Pp
max aed
< Pp
max [P,
[Fr+1] (P:-)((
(see below)
(95)
aed
$
(96)
where (95) follows from é E and the last inequality follows from Lemma H.2. Therefore, we have
(Tr (2,), 7 ar )) P [p] E,, [Dv (#. क. (x,)) 8] 8]+ (PP(("))
< + v,
where the first inequality follows by the fact that the total variation distance is bounded by 1, and the last inequality follows by (94) and (96).
Lemma L.2. Let T [H] and s', 8, e (0, 1), and Ç1:H [0, given. Further, consider two value functions Va+1, V.-1 E [0, H] and measure μ ((x) such that
P (o.nTT((mm aed
a) 36 Su.
(97)
Further, for x Xx let (x) arg (Q, Srl. where (x,0) Pr Pr [Vr+1] [1r, a), and inductively define
(2,2 Grl,
$5',
(x) aarg max aeA
+cl. otherwise.
Then, we have
Ea Dev (T. # (x=))
Proof Lemma L.2. In this proof, we let Pμ denote the probability law of æ, and Pp denote the probability law of P. Pre..- Denote by & be the me.-uururaal event that max,5 [(P.[V..]] PP) a) 3e'. Fix E, and let E, be the Pp -masurrable event
71

---

that maX
x 4E'. From the definition of म,, we have that
Dev (1)
1 Σ
2 and
[&] -1P-E (a)))])))] [ [ (x)
[
2
$ 1
2 1- [x]
PP []
(Jensen's inequality)
aEA
and since +| VaE
1 Σ Pp[E Pp (t) (z) 11
2 and
< Pp [E]]]
= Pp
max aeA
$ Pp
max P Tao
(see below)
(98)
$ dd
(99)
where (98) follows from é & and the last inequality follows from Lemma H.2. Therefore, we have
म (x, }]] P,
(T. (++))
S 5 v.
where the first inequality follows by the fact that the total variation bounded by 1, and the last inequality follows by (97) and (99).
L
Lemma L.3. Let x E IR and ve (0,1/2) be given. Further, let Ç 10)1 Then, > I 5s x 2
+
+
[x Ç) 1, x+ -
only if
or ssv.
Proof of Lemma L.3. To prove the claim, suffices to show the following items:
1. + + >> x
<1 only if æ0 2 x [x] - Vr and
2. x ( [ ()- - only [ar]
< [x]]
Ss..
We start by showing the first item. We proceed by showing the contrapositive; that is, we will show that if æ Ç [æ] or together with the fact that Ç 2 0, implies that
[x]. then æ < + [ C). Suppose that + S [x] This,
[x <7 |x +v
Now, suppose that x + Ç [x]. Then, we have
[ 57 [=] [x] ( x + C
where the penultimate inequality follows by ( (0, 1/2).
We now prove the second claim. Again, we proceed by showing the contrapositive; that is, will show that {[x] + x + or [x] x <} and Ç v, then + ( - > I <7 -1-1. 1.
Suppose that [x] + + < x Ç and < > The first inequality together with 2 0 implies that [ar + <]> [x:
On the other hand, since Ç 1/2, we have [x + <1 [x] 1, so
Ix <1 1 [ <
72

---

where the last inequality follows by the current assumption that [x] + x Now, suppose that [x]] + and that ( Then, have
[x+ + <) [a+] x < <=+(-++++++ where the last inequality follows by Ç > v. Rearranging (100) completes the proof.
(100)
M BehaviorCloning Algorithm and Analysis
In this section, we give self-contained presentation and analysis for the standard behavior cloning algorithm for imitation learning (e.g., Ross and Bagnell [46]), displayed in Algorithm 10. Given access trajectories from an expert policy # (which may be non-executable in the sense of Definition 2.1) the algorithm learns an executable policy nh with similar performance. We use this scheme within RVFS. and RVFSexo .bc.
Algorithm 10 BehaviorCloning: Imitation Learning Algorithm.
1: input: Policy class S IIs, expert policy æ1-H, suboptimality (0, 1), and confidence
8 e (0, 1).
2: Set Nbc 16/1 log((11/0)/e.
3: Set D - Ø.
4: for i= l..., Noc do
5: Generate trajectory (())))))...(= pa. (IH,
6: Update D + Du (T).
7: Compute xhC arg min (((rr,a))......maa)))) Ene[H] (TT(()) an).
8: Return bc
Proposition M.I. d (0, 1) be given and let 11 S Ils and HiZ be an expert policy such that
inf
(
TT (2x)) Enis-
(101)
well
Then, the policy be s, returned by Algorithm 10 satisfies, with probability at least 1- 1- 8.
J( - [ S 4HHmi + E/2.
Proof of Proposition M.1. First, by the performance difference lemma, we have
E[v)(( - E[V (x1))
E [
(æn, (x)))) 2 (æx, Th bh
(ax)));
H s H
Σ h=1
Th Th (.
(102)
We now bound the probability terms on the right-hand side. Fix h [H] and let D be the dataset in Algorithm 10, which consists of Nbc i.i.d. trajectories ( ((x a.)..... (I az)) generated by
rolling with THE By Lemma C.4 (with i.i.d. data, B = H. and Q II), we have that, with probability least 1 8,
VT IT,
Σ (TTT( # #(*))) 2 Σ 1 (a(x)) # (xx)) ((1.a)))--((=0000))) he[F)
Σ
he he[R]
2H log (2
(103)
Noc
and
YT e II,
PP(TA) + [x()))) 52 he[H]
Σ
Σ I(TA( *
4H 1og(2(11/8))
(104)
Noc
73

---

Taking the infimum over on both sides of (103) and using the definition of Th. in Algorithm 10 gives:
Σ ( + {xx))) s 2 inf Σ (T)T(( + (xn)) (t..
Σ
sell H]
2/1 log(2
Nbc
2H log (2
2ins
Nbc
where the last inequality follows from (101). Using this together with (104), instantiated with xhC, we get that with probability at least - 8:
8Hogg(21T1/))
Σ kr]
T ग.i be
(an) (xw)) s mins +
Noc
Plugging this into (102), we get that with probability at least 1 ó=ó:
([v - E (x1)) & mHsmis 8112 log(2 4HHmms + t/2,
Noc
where the last inequality follows by the fact that Noc 16// log(/////)11//66 This completes the proof.
74


Reviews:
[{"review_id": "XxMAJlb4gy", "reviewer": "Reviewer_DqGS", "summary": "The paper presents some theoretical results for new reinforcement learning algorithms with a sophisticated approach to a simulator environment.", "questions": "A clarification of the application of the algorithms and their implementation might improve the paper.", "limitations": "I don't think there's any negative societal impact.", "rating": 4, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "Paper presents an extensive theoretical study.", "weaknesses": "Practical applications of the algorithm remain questionable.\n\nThe modifications themselves might seem trivial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "h428BbJBob", "reviewer": "Reviewer_XHMe", "summary": "The paper introduces the SimGolf algorithm, which leverages local simulator access to reset to previously visited states and sample multiple trajectories. This approach enhances sample efficiency and accuracy in value function approximation, particularly in high-dimensional MDPs. The SimGolf algorithm uses local simulator access to achieve new statistical guarantees, allowing for efficient learning in environments with low coverability. Additionally, the paper presents RVFS (Recursive Value Function Search), a computationally efficient algorithm that achieves sample complexity guarantees under a strengthened statistical assumption known as pushforward coverability.", "questions": "- How does SimGolf perform in practical environments compared to regular RL and MCTS?\n- What specific types of environments are expected to benefit most from SimGolf?\n- Are there any preliminary empirical results or plans for validation in real-world applications?\n- The training process produces a final policy and set of Q functions. It should therefore be possible to use the presented algorithm for 'pre-training' in a simulator with reset capabilities, but then continue training with a SAC-like approach on real world data?\n\n- The paper lacks an explicit differentiation from existing methods. Is the following summary correct for contextualizing the work? (This is mostly just for my own understanding of the presented work)\n   - Regular RL requires only the ability to take actions and observe resulting new states, enabling linear rollouts. It performs single, uninterrupted rollouts without the ability to reset.\n   - MCTS (Monte Carlo Tree Search) requires a complete and known transition function, allowing iteration over all possible child nodes from each state. It builds and expands a search tree incrementally by iterating over all possible actions and simulating outcomes. This method utilizes comprehensive exploration through rollouts and backpropagation within the search tree, resulting in high accuracy of value estimation. However, it is computationally intensive and requires full knowledge of the transition dynamics.\n   - SimGolf strikes a balance between the simplicity of regular RL and the higher performance of MCTS. It requires the ability to reset to previously visited states and resample the next state under the same or different actions. This method does not necessitate complete iteration over all possible actions and transitions. Instead, it enhances sample efficiency by allowing targeted resampling after initial rollouts (under the same or different actions). The agent can reset to critical states identified during the initial exploration and simulate multiple future trajectories from those states, improving the accuracy of value function estimation. SimGolf uses the reset capability to gather multiple samples from key state-action pairs, updating a confidence set of value functions based on empirical Bellman error estimates, combining the benefits of comprehensive exploration with more modest demands on the environment.\n\nI was assigned to this paper after the regular review period so I did not have time to go through the presented math inn detail. Rely on the other reviews to check those.", "limitations": "- The lack of experimental validation means the practical benefits and real-world performance of the algorithm remain uncertain.\n- A discussion on future work and plans for empirical validation would be beneficial, detailing how the authors intend to demonstrate practical improvements.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Introduces a novel approach that uses reset capability in reinforcement learning to significantly improve sample efficiency.\n- Provides strong theoretical analysis and new statistical guarantees for reinforcement learning with local simulator access.\n- Proposes two innovative algorithms (SimGolf and RVFS) with clear theoretical benefits.\n- The paper is generally well-written and explains the new algorithms and their theoretical foundations clearly.\n- Addresses a significant problem in reinforcement learning by enhancing sample efficiency and providing robust theoretical guarantees.", "weaknesses": "- The paper breaks with the expected shape of a NeurIPS paper (numbered list in abstract, missing discussion or future work). While deviations are acceptable if justified, the current format lacks some important aspects.\n- The abstract includes references and attempts to serve as a conclusion, which is unconventional and detracts from its clarity. The abstract should be a short, plain summary of the paper It is also not the place to reference other works, as the abstract should be self contained.\n- The paper lacks a dedicated conclusion or discussion section, which would be crucial for contextualizing results and suggesting future work.\n- There is no experimental data provided (which is fine for a theory paper), but there should then at least be a discussion on expected practical benefits and an outline of plans for empirical validation as part of a future works section. In the area of RL we observe a significant gap between the theoretical understanding of performance guarantees and the actual observed performance of certain setups in practice. I would therefore regard the benefit of a paper, that restricts itself to only theoretical work itself as limited; actual experiments are needed to validate the practical applicability of the new findings. Please outline such in a future works section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Paper format:**\n\nThank you for your feedback. We understand the importance of adhering to a standard format; however, we chose to prioritize a detailed explanation of our novel and complex algorithm to ensure that its intricacies were fully conveyed. We believe this approach still aligns with the presentation style of other papers accepted at NeurIPS. With the additional page available for the camera-ready version, we will include a more detailed discussion section and suggestions for future work to further enhance the clarity and completeness of our paper.\n\n**Experimental results:**\n\nWhile we acknowledge the importance of empirical results, these are beyond the scope of the current paper. Our focus is to understand the sample and computational complexity of RL when a local simulator is available. In terms of understanding the theoretical limitations of RL, we believe the results presented here are significant on their own. However, our paper does pave the way for new empirical questions, which we are excited to explore in future works, as we will highlight in the future works section.\n\n**How does SimGolf perform in practical environments compared to regular RL and MCTS?**\n\nSimGolf was never intended to be a practical algorithm. Its primary purpose is to demonstrate that the coverability setting, which we argue is a general RL setting, is statistically tractable under resets—a fact that was not previously known. For practical applications, RVFS, which shares similarities with MCTS and Go-Explore, is the more viable algorithm. We discuss the similarities between RVFS and MCTS in detail on page 9, under the section ‘Connection to empirical algorithms.’\n\n**What specific types of environments are expected to benefit most from SimGolf?**\n\nSimGolf operates under the coverability assumption, an intrinsic structural property of the underlying MDP. Therefore, environments expected to benefit most from SimGolf include Low-Rank MDPs and (Exogenous) Block MDPs, both of which satisfy coverability. These environments exhibit high-dimensional state spaces and require nonlinear function approximation. Exogenous Block MDPs, described in Section 3.3, capture real-world RL settings where observations include a high-dimensional, time-correlated signal irrelevant to the RL task. Learning to ‘ignore’ this signal in a sample-efficient manner is extremely challenging, an issue explicitly left as an open problem in previous work. However, we demonstrate in this paper that SimGolf and RVFS make this possible when resets are available. Additionally, we expect RVFS to perform well even in settings that do not strictly satisfy coverability, including those where MCTS has been used. RVFS can be viewed as a more principled version of MCTS.\n\n**Using our algorithms for 'pre-training':**\n\nAs the cost of simulating real-world environments decreases, efficient algorithms like ours, which utilize a local simulator, will become extremely valuable for pretraining. One of the key points of our paper is to demonstrate that a local simulator enables the development of both statistically and computationally efficient algorithms for challenging RL settings, such as the Exogenous Block MDP setting.\n\n\n**Differentiation from existing methods:**\n\nWe would like to reiterate that the primary objective of our paper and the algorithms we present is not to propose a competitor to MCTS. The goal is to understand the sample and computational complexity of RL under coverability when a local simulator is available.\nThat said, your understanding of online RL and the workings of MCTS appears correct. We would like to add that MCTS has several major limitations compared to RVFS, including:\n- MCTS requires finite states to iterate over all possible child nodes of each state, making it inapplicable in environments with continuous states, unlike SimGolf and RVFS.\n- MCTS does not come with any provable sample-complexity guarantees and can fail even in simpler tabular RL settings. One reason for this is that MCTS (or some versions of it) uses rollouts with a fixed default policy (usually a policy that takes random actions), and the estimated value will correspond to this rollout policy. In contrast, our work reveals (through RVFS) that one needs to use the policy induced by the current estimated value function for rollouts. This approach is key for proving the sample complexity guarantees of RVFS. This simple idea can potentially be used to modify MCTS for better performance.\n\nWe will include a more detailed comparison between RVFS and MCTS in the camera-ready version.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iFmQwioHnt", "reviewer": "Reviewer_1avF", "summary": "The authors show that local simulator access removes Bellman completeness for MDPs with bounded coverability.  This generalizes the results of existing works that are limited to low-rank or linear structures. \n\nOn the statistical front, the authors analyze the sample complexity of SimGOLF using coverability, but the algorithm itself is computationally inefficient. \nTo resolve this they propose RVFS, which is computationally efficient with respect to (1) a regression oracle, and (2) a convex optimization oracle over the value function class $\\mathcal{V}$. In order to obtain sample complexity guarantees here, however, stronger assumptions such as pushforward coverability or $Q^\\star$ gap are required. \n\n(For some context behind the proceeding comments, I am familiar with the analysis of GOLF and its variants [4,31,61], but not with the local simulator literature [38,63,57] beyond a brief glance. )", "questions": "The questions below also include the specific ones from \"weaknesses\" that I would like to be answered. I would be happy to raise my score if my concerns are adequately addressed. \n\n1. Is it possible to analyze the complexity of oracle calls required to achieve the learning guarantee in Theorem 4.1? Will it be dependent on $\\mathcal{X}$? \n2. I imagine RVFS can be applied to the linear $V^\\star$ or $Q^\\star$ settings from [55,57,38]. Are the guarantees for RVFS comparable? I'm not necessarily looking for \"better\" performance because RVFS is more general, but just some sense of how big the gap might be (if there is one). Or just some discussion on the topic as I myself am not familiar.     \n3. Could you comment on the barriers to obtaining guarantees for RVFS under coverability, and/or why gap / pushforward helps? \n4. The definition of the confidence set in Algorithm 1 seems a little weird (maybe typo?), particularly the $\\sum_{h \\le t}$. Currently it seems like you throw samples from previous iterations away, is that intentional?", "limitations": "I believe the limitations of RVFS could benefit from greater discussion per my previous comments.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The motivation for the paper is clear, and generalizing RL in local simulators to structures beyond linear is a valuable contribution. \n\nSimGOLF/ Thm 3.1 are clean results, and I appreciate that the authors tackled the problem of computational efficiency in RVFS.", "weaknesses": "My impression is that the analysis of SimGOLF / Theorem 3.1 has limited technical novelty given [61]. That's not to say it's not a valuable contribution. \n\n**Oracle efficiency** \n\nMy biggest concern is that RVFS does not seem as \"oracle-efficient\" as claimed, and the discussion on this is somewhat lacking. For example, the authors could have stated more exactly what their definition of computational efficiency is (or is it just that it \"reduces to convex optimization\"?). They might have also provided an analysis on the # of calls to computational oracles before convergence. \n\nIn particular, it seems RVFS needs to solve the convex optimization in Line 8 for every $(x,a)$ in the core set, for $N_{test}$ times (which is like $\\varepsilon^{-1}$...?), and then for every possible action. Further, RVFS makes recursive calls to itself. Can this avoid $\\mathrm{poly}(\\mathcal{X}, \\mathcal{A}, \\varepsilon^{-1})$? \n\nMore minor, but it seems $\\mathcal{V}$ might need to be a convex set for efficient calculation of Line 8 (L355-358), which does not immediately gel with the \"holds for general function approximation\" or \"neural networks\" claims? In the grand scheme of things I'm sort of not that bothered by this. \n\n**Assumptions for RVFS**\n\nI am not opposed to make stronger assumptions for RVFS necessarily, but I would have liked to know more about why. For example, is it possible to give some intuition for why coverability alone is insufficient to analyze RVFS? And how do the gap or pushforward coverability assumptions help with this? \n\n**Comparison to existing work** \n\nThe authors mention that local simulator algorithms utilizing core sets exist for linear value function approximation exist, and I imagine that RVFS might also be applied to these settings. However, I find the consideration of previous literature to be quite limited, and I would have appreciated some discussion on how the sample/computational complexity of the algorithms compare (if they are comparable).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Technical novelty of SimGOLF in light of [1]**\n\n- We agree that the main technique behind our first result, SimGOLF, is quite simple, but we view this as a positive.\n- In particular, our result shows that the challenging coverability + realizability setting, which was explicitly left as an open problem in prior work and allows for nonlinear function approximation, is tractable under local simulator access.\n- Therefore, even though the proof for the fact that this result is tractable turns out to be remarkably simple, we think that the take-away message of the result is significant enough to merit publication. \n- Finally, we view the simplicity as a strength, since it will likely enable other researchers to build on this technique and explore whether it extends to other interesting settings. Notably, this is the starting point for our second main result, RVFS, which attacks the even more challenging problem of designing statistically and computationally efficient algorithms. Indeed, given the complexity of RVFS, it is very difficult to imagine directly proving such a result or designing such an algorithm without already being aware that the setting under consideration is tractable, which is precisely what SimGOLF provides.\n\n\n**Oracle type:**\n\nThe Oracle we require is precisely the one described on Line 356, which solves a convex optimization problem in function space. We note that similar Oracles have been used in prior works; see e.g. [3] (RegCB).\n\n**Number of Oracle calls:**\n\nAlthough not explicitly stated in Theorem 4.1, our analysis shows that the number of Oracle calls is polynomial in $C_{\\text{cov}}, H, A, \\log |\\mathcal{V}|$, and $1/\\epsilon$, with no dependence on $|\\mathcal{X}|$. This holds despite the recursion in RVFS. We would not consider the algorithm Oracle efficient if the number of Oracle calls depended on $|\\mathcal{X}|$. We will include the number of Oracle calls in Theorem 4.1.\n\n**Convexity of the function class:**\n\nThe optimization problem in Line 8 would have the same value if V is replaced by its convex hull. This is because the optimization problem, which is of the form $\\sup_{f \\in \\mathcal{V}_h} |\\mathrm{Objective}(f)|$, where $\\mathrm{Objective}(f)$ is linear if $f$, can be solved by considering the two subproblems (without the absolute value) \n\n$\\sup_{f \\in \\mathcal{V}_h} \\mathrm{Objective}(f)$ and \n\n$\\sup_{f \\in \\mathcal{V}_h} -\\mathrm{Objective}(f)$. \n\nSince the $\\mathrm{Objective}(f)$ is linear in $f$, the suprema in these subproblems will always be attained at vertecies of $\\mathcal{V}_h$, so the convex hull would not change the values of these objectives. We will provide more details on this.\n\n\n**Coverability alone for RVFS:**\n\nThe SimGolf algorithm uses the concept of global optimism, where the estimated value functions at each iteration are greater than the optimal value function in a pointwise sense; this greatly simplifies the analysis of the coverability setting using SimGolf. In contrast, RVFS does not employ global optimism.\n\nThere are RL settings that are only known to be statistically tractable using a global optimism approach; for example, the linear Bellman complete and the linear Q*/V* settings (see e.g. [3]). Our paper shows that a local simulator makes the coverability setting statistically tractable using global optimism (through SimGolf). It is unclear if the stronger pushforward-coverability assumption is necessary for algorithms that do not employ global optimism, like RVFS. We could not find a way to make the analysis of RVFS work with full coverability; the reasons for this are deeply rooted in the analysis of RVFS.\n\n\n**Handling the linear $Q^\\star/V^\\star$ settings:**\n\nRVFS can be slightly modified to handle the linear $V^\\star$ and $Q^\\star$ settings.\nSimilar to existing results for these settings, the corresponding sample complexity would be polynomial in $d$, $1/\\epsilon$, and $H$, without any dependence on $|A|$ or $|X|$. However, we have not worked out the exact exponents of $d$, $1/\\epsilon$, and $H$ in the sample complexity. We would be happy to include such an extension in the final version.\nWith the additional page available in the camera-ready version, we will provide a more detailed comparison to existing results.\n\n**Summation in the confidence set of Algorithm 1:**\n\nThe sum in the definition of the confidence set of simGolf contains a typo indeed. We will correct this in the camera-ready version.\n\n\n[1] Xie, Tengyang, Dylan J. Foster, Yu Bai, Nan Jiang, and Sham M. Kakade. \"The role of coverage in online reinforcement learning.\" arXiv preprint arXiv:2210.04157 (2022).\n\n[2] Foster, Dylan J., Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. \"Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement-based perspective.\" arXiv preprint arXiv:2010.03104 (2020).\n\n[3] Kane, Daniel, et al. \"Computational-statistical gap in reinforcement learning.\" Conference on Learning Theory. PMLR, 2022.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EkELBhEf7V", "reviewer": "Reviewer_bJ3L", "summary": "This paper study the online RL having access to a local simulator with general function approximation. Their results unclock new statistical guarantees. First, $Q^*$ realizability together with coverability assumption are enough for sample-efficient online RL under this setting. Second, their results further implies that the Exogenous Block MDP problem is tractable under this setting. Finally, they complement their theoretical finding with a computationally efficient algorithm.", "questions": "1. What is the double sampling problem mentioned on line 170?\n\n2. What is the distribution shift mentioned on line 313?\n\n3. What is the $v_h$ on line 16 of Alg 2?\n\nMinor issues:\n\n1. Definition of the confidence set in Alg 1, the summation $\\sum_{h\\leq t}$, is this a typo?\n2. Double such that on line 221, and the comma and period in the end.", "limitations": "Yes.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is in general clearly written. The idea of leveraging local simulator to facilitate online RL with general functionn approximation is novel and leads to several important observations that previous works are out of reach.", "weaknesses": "Maybe due to space limit, some terms lack of definition or discussion, see questions for details. \nThe algorithm in section 4 is highly technical and somewhat difficult to follow. Based on the current context, it appears that the role played by the local simulator is underexplained. One might question if most parts of the algorithm are adaptations of previous techniques to the general function approximation setting. It would be great if the novelty and insights can be highlighted.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Novelty relative to prior work:**\n\nThe algorithm presented in Section 4 is far from a simple adaptation of previous techniques. We now highlight some of the key algorithmic innovations:\n- RVFS builds on the DMQ algorithm by [1]. Unlike the latter, we use a core set of state-action pairs instead of policies. This is crucial for our algorithm to work without the strong hypercontractivity assumption made by [1].\n- One of the key algorithmic innovations is the use of Bellman backups (as in line 8 of Algorithm 2) to evaluate whether a new state-action pair should be added to the core set. This technique is unique to our paper and enables handling RL settings beyond linear function approximation. Incorporating Bellman backups in the test at line 8 is essential for proving that the algorithm converges under pushforward coverability.\n- Additionally, the modification of RVFS to the exogenous setting, which includes a randomized rounding, is also novel.\n\nBeyond these algorithmic innovations, the analysis of RVFS introduces new proof techniques, especially in the setting without a gap, that could be beneficial for broader applications beyond the settings studied in this paper.\n\n**What is double sampling?**\n\nWhat is the double sampling problem mentioned on line 170?\nThe double sampling problem refers to the challenge of estimating $T_h g_{h+1}(x_h,a_h)=\\mathbb{E}[g_{h+1}(x_{h+1}) \\mid x_h,a_h]$ in (1), which requires more than one next-state sample starting from the state $x_h$. Generating multiple samples from any given state is only possible with resets; in the online setting without resets, a state $x_h$ may only be observed once, allowing only a single next-state sample. See e.g. https://x.com/nanjiang_cs/status/1672702613744410624 for more details on the double sampling problem.\n\n**What is distribution shift?**\n\nThe distribution shift mentioned 313 is a well-known phenomenon the situation where for a new state action pair $(x_{\\ell-1},a_{\\ell-1})$, the distribution of the next state $x_{\\ell}$ puts mass on new regions of the state space where the estimated value function is inaccurate.\nSee e.g., sec 7.3 in https://arxiv.org/pdf/2312.16730 for more detail on the distribution shift phenomenon in RL.\n\n**What is the $v_h$ on line 16 of Alg 2?**\n\n$v_h$ represents an esitmate of $\\mathbb{E}^{\\hat\\pi}[\\sum_{\\ell= h}^H r_\\ell \\mid x_h]$---see how the set $\\mathcal{D}_h$ is constructed on line 15.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper presents a powerful use of local simulator access in online reinforcement learning with general function approximation. The authors introduce two new algorithms, SimGolf (inspired by a previous work) and RVFS. Both algorithms achieve sample efficient gaurantees in this setting. While the first uses global optimism and is not computational, the latter solves this problem by strengthening some of the underlying coverability and representation assumptions.

SimGolf leverages global optimism, augmented with local simulator access, to achieve sample-efficient learning while requiring only Q*-realizability and coverability. This significantly relaxes the representational constraints required by previous work. A key innovation lies in the direct estimation of squared Bellman error using local simulator access. This method is simple, and potentially very useful for practical applications.

The authors acknowledge the inherent computational complexities associated with global optimism, and introduce RVFS, a computationally efficient algorithm based on a refined recursive exploration scheme guided by core-sets.  RVFS offers provable guarantees under pushforward coverability, a new statistical assumption the authors introduce. The authors acknowledge that the high polynomial dependence on problem parameters in the sample complexity bounds necessitates further research of tighter bounds and their practical implications. 

Overall, this work makes a significant contribution to the theoretical understanding of RL with general function approximation and I strongly recommend to accept it.
Decision: Accept (spotlight)