The Power of Resets in Online Reinforcement Learning
Zakaria Mhammedi Dylan J. Foster Alexander Rakhlin
 






colt

colt





  
  








  

	
	plainnat
	();a,,



 
    


	
        
               
        
      
            
       
       
       
      

           



  dvipsnamesxcolor
  



































 





   lemmod[2]
  
   lemma
  


thmmod[2]
  
   theorem
  


bodythmmod[2]
  
   bodytheorem
  

    propmod[2]
  
   proposition
  

     defnmod[2]
  
   definition
  

   asmmod[2]
  
   assumption
  

  cormod[2]
  
   corollary
  
  
   condmod[2]
  
   condition
  




[name=Theorem,parent=section]theorem
[name=Lemma,parent=section]lemma
[name=Corollary,parent=section]corollary
[name=Claim,parent=section]claim
[name=Assumption, parent=section]assumption
[name=Condition, parent=section]condition
[qed=◃,name=Example,style=definition, parent=section]example
[name=Remark,parent=section]remark
[name=Proposition, parent=section]proposition
[name=Fact, parent=section]fact



    <Ref><ref>











plain
definition[theorem]Definition

















equation#2Eq. (#1)#3
equation#2Eq. (#1)#3

figure#2Figure #1#3
assumption#2Assumption #1#3

assumptionAssumptionAssumptions









#1#1#1
#1bb#1
ABCDEFGHIJKLMNOPQRSTUVWXYZ#1#1#1
#1b#1
ABCDEFGHIJKLMNOPQRSTUVWXYZ#1sf#1
ABCDEFGHIJKLMNOPQRSTUVWXYZ#1c#1
ABCDEFGHIJKLMNOPQRSTUVWXYZ#1h#1
ABCDEFGHIJKLMNOPQRSTUVWXYZ#1hc#1
ABCDEFGHIJKLMNOPQRSTUVWXYZ#1t#1
ABCDEFGHIJKLMNOPQRSTUVWXYZ#1tc#1
ABCDEFGHIJKLMNOPQRSTUVWXYZ#1#1#1
#1scr#1
ABCDEFGHIJKLMNOPQRSTUVWXYZ



    










 
             
 
 



#1b#1
abcdeghijklmnopqrstuvwxyz





|| 
[]
{}
()

⟨⟩


⌈⌉
⌊⌋



























@mathaccentsingle[3]
	0"0362#1^H
	2"03620pt#1^H
	0=2 #3#2
kern[1]#1@kerna


bar[2]@single#1@bar@#1#21@bar@#1#22
bar[2]@single#1@bar@#1#21@bar@#1#22
bar@[3]
	##1##2
		@mathaccent
		#32 @nucleus@char @@style@nucleus_
		@@style@nucleus_
		@@
		@-@
		@ 3
		tempdima@
		tempdima-tempdima 10
		@-tempdima
		@>@ @0pt@kern0.6-@
		#31
		@kern-0.6@@nucleus@kern0.4@
		@0.4@kerna
		@kern#2
		@<@ @kern1@kern1 -@@kern-0.6@#1
		
	@depthne
	@bgroupempty @egroup@set@skewchar
	@ @everymath@group
	@set@skewchar@nested@a
	#31
	@nested@a111#1
	@till@marker##1
	@char@till@marker#1@char A@char
	@nested@a111@char
	
bar@[3]
	##1##2
		@mathaccent
		#32 @nucleus@char @@style@nucleus_
		@@style@nucleus_
		@@
		@-@
		@ 3
		tempdima@
		tempdima-tempdima 10
		@-tempdima
		@>@ @0pt@kern0.6-@
		#31
		@kern-0.6@@nucleus@kern0.4@
		@0.4@kerna
		@kern#2
		@<@ @kern1@kern1 -@@kern-0.6@#1
		
	@depthne
	@bgroupempty @egroup@set@skewchar
	@ @everymath@group
	@set@skewchar@nested@a
	#31
	@nested@a111#1
	@till@marker##1
	@char@till@marker#1@char A@char
	@nested@a111@char
	




































 









  


















































inductHypothesis































































	


























        


















  

        


















 














































































 
 

 
  





























































































































































	

































































































































  








































































































 
line#2Line #1#3


















dfForestGreen
zmred
srmagenta















  
  
    The Power of Resets in Online Reinforcement Learning]The Power of Resets in Online Reinforcement
    Learning
  
  
  
  
  
  
  
  
  

  
 Author Name1 abc@sample.com

 Address 1
 Author Name2 xyz@sample.com

 Address 2

  
  


  
  





  toc




	
	The Power of Resets in Online Reinforcement Learning
    Zakaria Mhammed
 Dylan J. Foster
 Alexander Rakhlin


    
=========================================================


          
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 <cit.>—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 <cit.> 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, (Recursive Value Function Search), which achieves provable sample complexity guarantees under a strengthened statistical assumption known as pushforward coverability. can be viewed as a principled, provable counterpart to a successful empirical paradigm that combines recursive search (e.g., MCTS) with value function approximation.
  
  


  
  
  
  
  
  
  
  
  
  
  
  
  
  

























 	

        
          
            Reinforcement learning, learning theory, generative model,
            simulator, coverability.
          
        
        
	
	
	
	
	

§ INTRODUCTION

	
        






Simulators are a widely used tool in reinforcement learning. Many of the most
well-known benchmarks for reinforcement learning research make use of
simulators (Atari <cit.>, MuJoCo
<cit.>, OpenAI Gym <cit.>, 
DeepMind Control Suite <cit.>), and high-quality
simulators are available for a wide range of real-world control tasks,
including robotic control
<cit.>, autonomous vehicles
<cit.>, and game playing <cit.>. Simulators also provide a useful abstraction for planning with a known or learned model, an important building block for
many RL techniques
<cit.>. Yet, in spite of the ubiquity of simulators, almost all existing research into algorithm
design—empirical and theoretical—has focused on the 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 or
fundamental limits.












We explore the power of simulators through online reinforcement learning with local
  simulator access (for short), also known as local
  planning
<cit.>. Here,
the agent learns by repeatedly executing policies
and observing the resulting trajectories (as in online RL), but is
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 <cit.> uses local simulator access to achieve state-of-the-art performance for Montezuma's
Revenge (a difficult Atari game that requires systematic
exploration), beating the performance of the best agents
trained with online RL
<cit.> by a significant margin that has
yet to be closed. The successful line of research on AlphaGo and
successors
<cit.>
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
      <cit.>,
      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 function approximation that
                    provably benefit from local simulator access?
                    
                

                  Can we develop algorithms for reinforcement
                    learning with general 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 to understand which
              states are “informative” in the sense that we should
              prioritize revisiting them.
              
              
              
              
              Here, we are faced with a chicken-and-egg 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 a way to
              understand which states are informative. It is
              natural to let function approximation (valued-based,
              model-based, or otherwise) guide us; to this end, recent research
              <cit.>
              on linearly-parameterized RL with 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., <cit.>). Yet, for general function classes—particularly
              rich models like neural networks that do not readily
              support extrapolation—defining a suitable notion of
              core-set is challenging. Consequently, existing
              techniques have yet to meaningfully leverage local simulator access beyond the linear regime.


              





















              
              
              
              



   




 §.§ Contributions


We show that local simulator access unlocks new guarantees for online
reinforcement learningRL with general value function approximation—statistical and computational—that were
previously out of reach.


Sample-efficient learning We show that MDPs with low
  coverability <cit.>—a general structural condition that subsumes
  Block MDPs and Low-Rank MDPs—can be learned in a sample-efficient
  fashion with only Q^⋆-realizability (that is, realizability
  for the optimal state-action value function). This is achieved through a
  new algorithm, , 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
  <cit.> is tractable in its most
  general form under
  local simulator access.
  
  
  

  
  
  
  
  
  
  
  
  
  





  
  
  
Practical, computationally efficient learning Our results above are achieved
  through a computationally inefficient algorithm. We complement them
  with a practical and computationally efficient algorithm, (“Recursive Value
  Function Search”), which achieves sample-efficient learning
  guarantees with general value function approximation under a
  strengthened, yet novel, statistical assumption known as
  pushforward coverability
  <cit.><cit.>. Assuming either i)
  realizability of the optimal state-value function V^⋆ and a state-action gap or ii)
  realizability of V^π for all π, achieves
  polynomial sample complexity in a computationally efficient fashion,
  and leads to guarantees for a new class of
  Exogenous Block MDPs with weakly correlated exogenous noise.   explores by building core-sets with a novel
  value function-guided scheme, and can be viewed as a principled
  counterpart to algorithms including MCTS and AlphaZero
  <cit.>,
  that combine recursive search with value function
  approximation. Compared to these approaches, is designed to
  provably address stochastic environments and distribution shift.
  


  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  









  

  
  
  




  


  



  




































Paper organization
<ref> formally introduces our problem setting,
  including the local simulator framework. <ref>
presents our main sample complexity guarantees, and
               <ref> gives computationally
               efficient algorithms. We close with discussion in
               <ref>. All proofs are deferred to the appendix.




               




 	
	
	

§ SETUP: REINFORCEMENT LEARNING WITH LOCAL SIMULATOR ACCESS

	
        



We consider an episodic reinforcement learning setting. A Markov
Decision Process (MDP) is a tuple = ( , , T, R, H), where
 is a (large/potentially infinite) state space,  is the
action space (we abbreviate A=), H ∈ is the horizon, R = {R_h}_h=1^H is
the reward function (where R_h : ×→ [0,1])
and T = {T_h}_h=0^H is the transition distribution (where T_h
: ×→Δ()), with the convention that
T_0(·|∅) is the initial state distribution. A
policy is a sequence of functions π = {π_h: →Δ()}_h=1^H; we use  to denote the set of
all such functions. When a policy is executed, it
generates a trajectory (_1,_1,_1), …, (_H, _H,
_h) via the process _h ∼π_h(_h), _h ∼
R_h(_h,_h), _h+1∼ T_h(·|_h,_h),
initialized from _1 ∼ T_0(·|∅) (we use
_H+1 to denote a terminal state with zero
reward). We write ^π*· and ^π*·
to denote the law and expectation under this process. 

For a policy π, J(π) ^π[]∑_h=1^H _h denotes expected reward, and the value functions are given by V_h^π(x) ^π[]∑_h'=h^H _h'|_h=x, and Q_h^π(x,a) ^π[]∑_h'=h^H _h'|_h=x,_h=a.


    V_h^π(x) ^π*∑_h'=h^H _h'|_h=x,    and    Q_h^π(x,a) ^π*∑_h'=h^H _h'|_h=x,_h=a.

We denote by π^⋆ = {π^⋆_h}_h=1^H the optimal
deterministic policy that maximizes Q^ at all states, and
write Q^ and V^.
























 §.§ Online Reinforcement Learning with Local
    Simulator Access

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 τ∈N_, the learner
selects a policy πτ = {π_hτ}_h=1^H, executes it
in the underlying MDP ^⋆ and observes the trajectory
{(_hτ,_hτ,_hτ)}_h=1^H. After all N_
episodes conclude, the learner produces a policy ∈ with
the goal of minimizing the risk given by *J() -  J().







In online RL with local simulator access, or ,  <cit.>,
we augment the online RL protocol as follows:[We use the term
  “local simulator” instead of “local planning” because we find it
  to be slightly more descriptive.] At each episode
τ∈N, instead of starting from a random initial state _1∼T_0(·|∅), the
agent can reset the MDP to any layer h∈H and any state
_h previously encountered, and proceed with a new episode starting
from this point. As in the online RL protocol, the goal is to produce a policy ∈ such that *J() -  J()≤

    *J() -  J()≤

with as few episodes of interaction as possible; our main results take
N_=(C,^-1) for a suitable problem parameter C.



























acts as a happy medium between online RL, which is
  realistic but often intractable, and global simulator access (where the
  agent can query transitions for arbitrary
state-action pairs) <cit.>, which is
powerful, yet unrealistic.











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 at train time, but not test
            time). Some recent work using local simulators for
            RL with linear function approximation
            <cit.> 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.
            
            
            
            
            
            
  
We refer to a policy π for
which computing π(x)∈Δ() for any x∈ requires n local
simulator queries as a non-executable policy with
  sample complexity n.







  

  
Implications for planning
    RL 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
<cit.> and practice (e.g., <cit.>).
Since the model is known, computing an
optimal policy is a purely computational problem, not a statistical
problem. Nonetheless, 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, using the model
to simulate the environment the agent interacts with. Here, any
computationally efficient algorithm in our framework immediately yields an efficient
algorithm for planning. See <ref> for more discussion.
            
            
            





















    
    
    
    
          
          


                    

 §.§ Additional Notation

          Additional notation





                    For any m,n ∈ℕ, we denote by [mn]
 the integer interval {m,…, n}. We also let
 [n] [1n]. We refer to a scalar c>0 as an absolute constant to indicate
 that it is independent of all problem parameters and use
 (·) to denote a bound up to factors polylogarithmic in
 parameters appearing in the expression. We define ∈ as the random policy that
 selects actions in  uniformly at random at each layer. We define
 the occupancy measure for policy π via d_h^π(x,a) ^π[_h = x, _h=a]. For functions g:×→
 and f:→, we define Bellman backup operators by
 _hg(x,a)=*_h+ max_a'∈g(_h+1,a')|_h=x,_h=a and
 _hf(x,a)=*_h + f
   (_h+1)|_h=x,_h=a. For a stochastic policy
   π∈, we will occasionally use the bold notation
   π_h(x) as shorthand for the random variable _h∼π_h(x)∈Δ(). 
    For a function f→, we write a'∈_a∈ 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  are index from 1,…,||.

 





          
          
          
          
          
          
          
          
          
          
          
          
          
          







 
        

§ NEW SAMPLE-EFFICIENT LEARNING GUARANTEES VIA LOCAL
          SIMULATORS

        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        

        This section presents our most powerful results for
        
        . We
        present a new algorithm for learning with local simulator
        access,  (<ref>), and show that it enables sample-efficient RL for MDPs with low
        coverability <cit.> using only
        -realizability (<ref>). We then
        give implications for the Exogenous Block MDP problem (<ref>).

     
        
  Function approximation setup and coverability To achieve
  sample complexity guarantees for online reinforcement learning that are
  suitable for large, high-dimensional state spaces, we appeal to value function
    approximation.
  
  
  
  We assume access to a function class ⊂(××H→0,H) that contains the optimal
  state-action value function Q^⋆; we define
  _h=*Q_h|Q∈.
  
[Q^⋆-realizability]
	
	For all h∈ [H], we have Q^⋆_h∈_h.
      
-realizability is widely viewed as a minimal representation condition for
online RL <cit.>.
The class  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  and Π are finite, and aim for sample complexity guarantees scaling with
log and logΠ; extending our results to infinite
classes via standard uniform convergence arguments is straightforward.











Coverability
Beyond representation conditions like realizability, online
reinforcement learningRL algorithms require structural conditions
that limit the extent to which deliberately designed algorithms can be
surprised by substantially new state distributions. We focus on a
structural condition known as coverability
<cit.>, which is inspired by
connections between online and offline reinforcement learningRL.


	
	The coverability coefficient is 
        C_max_h∈Hinf_μ_h∈Δ(×)sup_π∈d_h^π/μ_h_∞.
      
      

[Coverability <cit.>]
	
	The coverability coefficient C_>0 is given by 
	
    C_max_h∈Hinf_μ_h∈Δ(×)sup_π∈d_h^π/μ_h_∞.

      
      
Coverability is an intrinsic strutural property of the underlying
MDP. Examples of MDP families with low coverability include
(Exogenous) Block MDPs, which have ≤**,
where  is the latent state space <cit.>, and Low-Rank MDPs, which
have ≤d*, where d is the feature dimension
<cit.>; importantly, these settings
exhibit high-dimensional state spaces and require nonlinear
function approximation. To the best of our knowledge,
coverability is the only structural parameter that is known to be
small for the Exogenous Block MDP problem, as other well-known
parameters like Bellman rank and Bellman-Eluder dimension can be
arbitrarily large <cit.>. We emphasize that asAs in prior work
<cit.>, our algorithms require
no prior knowledge of the distribution μ_h that
  minimizes <ref>.that achieves the minimum in <ref>.
      























        
        

 §.§ Algorithm



        
        
        
        
        
        
        
        
Our main algorithm, , is displayed in
<ref>. The algorithm is a variant of the method of <cit.> with novel adaptations to
exploit the availability of a local simulator. Like , explores using the principle of global optimisim: At each
iteration t∈N, it maintains
a confidence set (or, version space) t⊂ of
candidate value functions with low squared Bellman error under the
data collected so far, and chooses a new exploration policy πt 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 arises in the data
collection strategy and design of confidence sets. Like ,
algorithm constructs the confidence set
t⊂ such that all value functions g∈t
have small squared Bellman error:[<cit.> show
  that squared (versus average) Bellman error is essential to
  derive guarantees for coverability.]

    ∑_i<t^πi**g_h(_h, _h) - _h[g_h+1](_h,_h)^2log  ∀h∈H.

Due to the presence of the Bellman backup _hg_h+1 in
<ref>, naively estimating squared Bellman error leads to the
notorious double sampling problem. To avoid this, the approach
taken with and related work <cit.> is to adapt a certain de-biasing
technique to remove double sampling bias, but this requires access to
a value function class that satisfies Bellman completeness, a representation
significantly more restrictive than  realizability (e.g., <cit.>).

The idea behind is to use local simulator access to
directly produce high-quality estimates for the Bellman backup
function _hg_h+1 in <ref>. In particular, for a given state-action pair
(x,a)∈×, we can estimate the Bellman backup
_h[g_h+1](x,a) for all functions g∈ simultaneously by
collecting K next-state transitions _h+11,…,
 _h+1Ki.i.d.∼T_h(·|
 x,a)
 
 
 
 and
 K rewards _h1,…,
 _hKi.i.d.∼R_h(x,a), then taking
 the empirical mean: _h[g_h+1](x,a)≈1/K∑_k=1^K
 (_hk+max_a'∈g_h+1(_h+1k
 ,a')). <ref> of uses this technique to directly
 estimate the Bellman residual backup under a trajectory gathered with
 πt, sidestepping 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.We suspect that the idea of performing estimation
      with respect to squared Bellman error directly using local
      simulator access may find broader use.
      


 
 
 
 
      

      
  
   A general approach to removing the need for Bellman completeness is
   to estimate average Bellman error instead of squared Bellman
   error (e.g., <cit.>). However, <cit.> show that this is insufficient
   to obtain sample complexity guarantees under coverability.
 
 


 






  


      















      



 












 
 
 
 
 
 


 

 



  
  
  
  
  
  
  
          
          
          
          
          


          



        
        
        
          


          

          
          
          
          
          
          
          
          
          
          

            
            
            
            
            
            
            
            
            



               
               



 §.§ Main Result


We now state the main guarantee for  and discuss some of its implications.
    
   	
   	Let , δ∈(0,1) be given and suppose 
        <ref> (Q^⋆-realizability) and <ref>
        (coverability) hold with >0. Then the policy 
        produced by (, ,, δ) (<ref>) has
        J()-*J()≤
        with probability at least 1-δ. The total sample
        complexity in the framework is bounded by *H^5^2log(/δ)/^4.
        
        
    *H^5^2log(/δ)/^4.

        

          
        
        
   
      
      
      
      
      
      
      
      
        This result (whose proof is in <ref>) shows that under only Q^⋆-realizability and
        coverability,  learns an -optimal policy with
        polynomial sample complexity, significantly relaxing the
        representation assumptions (Bellman completeness, weight
        function realizability) required by prior algorithms for
        coverability <cit.>. This is the first instance we are aware of where
        local simulator 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 to combining global
        optimism with local simulator access, in
        contrast to greedy layer-by-layer schemes used in prior work
        on local simulators (with the exception of
        <cit.>). 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 is an
        interesting question for future work.




        A conjecture
        By analogy to results in offline
        reinforcement learning, where -realizability and
        concentrability (the offline counterpart to coverability)
        alone are
        known to be insufficient for sample-efficient learning
        <cit.>, we conjecture
        that Q^⋆-realizability and coverability alone
        are not sufficient for polynomial sample complexity in vanilla online RL. If true, this would imply a new
        separation between online RL with and without
        local simulators.
        
        
        
        

        
        

       


      
      
      
      
      
      



      


  
Proof sketch
  As described in <ref>, the main difference between
   and lies in the construction of the confidence
  sets. The most important new step in the proof of
  <ref> is to show that the local simulator-based confidence
  set construction in <ref> is valid in the sense that the
  property <ref> holds with high probability. From here,
  the sample complexity bound follows by adapting the
  change-of-measure argument based on coverability from
  <cit.>.
  

  
  
  

          
        

 §.§ Implications for Exogenous Block MDPs


        
        
We now apply and <ref> to the Exogenous Block
  MDP (ExBMDP) problem
<cit.>,
a challenging rich-observation reinforcement learning setting in which
the observed states _h 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 =(,,Ξ,,H,T,R,g) is defined by a latent
        	state space and an observation space. We begin by
        describing with the latent state space. Starting from an initial
        endogenous state _1∈ and exogenous state
        _1∈Ξ, the latent state _h=(_h,_h) evolves for
        h∈H via
    _h+1∼_h(·|_h,_h),_h+1∼_h(·|ξ_h),

        where _h∈ is the agent's action at layer h; we adopt the convention
        that _1∼_0(·|∅) and
        _1∼_0(·|∅). 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 _h∈ generated via[        	A more standard formulation of the observation process
        	<cit.>
        	assumes that observations are generated via
        	_h∼q_h(_h,_h), where q_h(·,·) is a
        	conditional distribution with the decodability property. This is
        	equivalent to <ref> under
        	mild measure-theoretic conditions, as randomness in the
                emission process can be included in the exogenous
                state without loss of generalityw.l.o.g., but the formulation in
        	<ref> makes our proofs slightly more compact.]
        
    _h = _h(_h,_h),

        where _h:×Ξ→ is the
        emission function. We assume the endogenous latent space  and action space  are
        finite, and define S and
        A. However, the exogenous state space Ξ and
        observation space  may be arbitrarily large or infinite, with
        *Ξ,≫.[To simplify
          presentation, we assume that Ξ and  are
        		countable; our results trivially extend to the case where the
        		corresponding variables are continuous with an
                        appropriate measure-theoretic treatment.]

                      The final property of the ExBMDP
        model is decodability,
        which asserts the existence of a decoder
        such that ϕ_⋆→ such that
        ϕ_⋆(_h)=_h a.s. for all h∈H under the
        process in <ref>. 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_h(_h,_h) only depends on the observations (_h)
        through the corresponding latent states
        ((_h)=_h).
        
        
        
        
        
        
        
        
        
        
        
        
        To enable sample-efficient learning, we assume access to a
        decoder class Φ that contains , as in
        prior work.

        [Decoder realizability]
        
        We have access to a decoder class Φ such that ∈Φ.
        
        
        
        	
        	
        	
        

        Applying and <ref>
        To apply <ref> to the ExBMDP problem, we need to
        verify that Q^⋆-realizability and coverability
        hold. Realizability is a straightforward consequence of
        decodability (<ref> in <ref> of
        the appendix).
        For coverability, <cit.> show that ExBMDPs
        have ≤SA under decodability, in spite of the time-correlated exogenous noise process (_h)
        and potentially infinite observation space
         (interestingly, coverability is essentially the only useful
        structural property that ExBMDPs are known to satisfy, which
        is our primary motivation for studying it). 
        Realizability is also a straightforward consequence of
        the decodability assumption. 
        
          
          For the ExBMDP setting, under <ref>, (i) the function class _h{x↦ g(ϕ(x),a) : g∈ [0,H]^SA, ϕ∈Φ}
        satisfies <ref>, and (ii) the
        policy class Π_h=*x↦π(ϕ(x)) :
          π∈^S, ϕ∈Φ satisfies
        <ref>. Both classes have 
        log_h=logΠ_h=(S+logΦ).[Formally,
          this requires a standard covering number argument; we omit
          the details.]
                








      This leads to the following corollary of <ref>.      
      
        
        Consider the ExBMDP setting. Suppose that
        <ref> holds, and let  be
        constructed as in <ref> of <ref>. Then for any , δ∈ (0,1), the policy = (, SA, ,
        δ) has J()- J()≤ with
        probability at least 1-δ. The total sample
        complexity in the framework is N = *H^5S^3A^3logΦ/^4.
        bounded by
        
    *H^5S^3A^3logΦ/^4.

        
        
           
           
        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
           <cit.>, or (ii) factored
           emission structure <cit.>.
           <cit.> observed that ExBMDPs admit low
           coverability, but their algorithm requires Bellman
           completeness, which is not satisfied by ExBMDPs (see
           <cit.>). See
           <ref> for more discussion.

        




         
        

§ COMPUTATIONALLY EFFICIENT LEARNING WITH LOCAL
          SIMULATORS

        
        









































































         
        
        
        
        
        
        
        
        
        
        
        
        
        
        

Our result in <ref> show that local simulator access
facilitates sample-efficient learning in MDPs with low coverability, a
challenging setting that was previously out of reach. However, our
algorithm is computationally-inefficient because it relies on
global optimism, a drawback found in most prior work on RL with
general function approximation
<cit.>. It
remains an open question whether any form of global optimism can be
implemented efficiently, and some variants have provable barriers to
efficient implementation <cit.>.
        
       

To address this drawback, in this section we present a new algorithm,
 (Recursive Value Function Search; <ref>), which requires stronger versions of the coverability and realizability
assumptions in <ref>, but is computationally efficient in
the sense that it reduces to convex optimization over the state-value
function class .





makes use of a sophisticated recursive exploration
scheme based on core-sets, sidestepping the need for global optimism.,
and can be applied to Exogenous Block MDPs with weakly
  correlated exogenous noise.






       


 §.§ Function Approximation and Statistical Assumptions



      
      
To begin, we require the following strengthening of the coverability assumption in <ref>. 
       [Pushforward coverability]
       	
       	The pushforward coverability coefficient >0 is given
        by =   max_h∈[H]inf_μ_h∈Δ()sup_(x_h-1 ,a_h-1 ,x_h)∈_h-1××T_h-1(x_h|x_h-1,a_h-1)/μ_h(x_h).
       	
    =   max_h∈[H]inf_μ_h∈Δ()sup_(x_h-1 ,a_h-1 ,x_h)∈_h-1××T_h-1(x_h|x_h-1,a_h-1)/μ_h(x_h).

               
      
      Pushforward coverability is inspired by the pushforward
        concentrability condition used in offline RL by
      <cit.>. Concrete examples
      include, (i) Block MDPs with latent space , which admit
      ≤, (ii) Low-Rank MDPs in dimension d,
      which admit ≤d <cit.>, and (iii)
      Exogenous Block MDPs for which the exogenous noise process
      satisfies a weak correlation condition that we introduce
      in <ref>. Note that ≤,
      but the converse is not true in general.
      






       

Instead of state-action value function approximation as in , in
this section we make use of a state value function class ⊂(×H→0,H), but require somewhat stronger
representation conditions than in <ref>. We
      consider two complementary setups, which can be summarized
      briefly as follows:
        
        
  * Setup : <ref>
          (/-realizability) and <ref> (Δ-gap) hold.
        
  * Setup : <ref>
          (V^π-realizability) and <ref>
          (π-realizability) hold.
        
We describe these assumptions in more detail below.


Function approximation setup  First, instead of
Q^⋆-realizability, we consider the weaker
V^⋆-realizability <cit.>.

[V^⋆-realizability]
	
	For all h∈ [H], we have V^⋆_h∈_h.
      

Under V^⋆-realizability, our algorithm learns a near-optimal
policy, but the policy is non-executable (cf. <ref>) in the sense of
<ref>; this property is shared by prior work on local
simulator access with value function realizability
<cit.>. To produce executable policies,
we additionally require access to a policy class Π⊂
containing ; we define Π_h=*π_h|π∈Π.

[-realizability]
	
	The policy class Π contains the optimal policy .
 

Note that V^⋆-realizability (<ref>) and
-realizability (<ref>) are both implied by -realizability, and hence are
weaker. However,


we also assume the
optimal Q-function admits constant suboptimality gap (this
makes the representation conditions for  incomparable to <ref>).



       
       
       [Δ-Gap]
         
         The optimal action _h(x) is unique, and
         there exists Δ>0 such that for all h∈[H], x∈, and a ∈∖{π^⋆_h(x)}, _h(x,_h(x))>_h(x,a) + Δ. 
         
    _h(x,_h(x))>_h(x,a) + Δ.

      
      This condition has been used in a many prior works on
      computationally efficient RL
with function approximation <cit.>.


















      Function approximation setup 
      As an alternative to assuming constant suboptimality gap,
        we We 
      also provide guarantees under the assumption that the value
      function class  satisfies all-policy realizability
      <cit.> in
      the sense that it contains the value functions V^π for all π∈.
              [V^π-realizability]
       	
       	The value function class =_1:H has V^π_h ∈_h for all π∈ and h∈[H].      
   
       
       
       
This assumption will be sufficient to learn a non-executable policy,
but to learn executable policies we require an analogous strengthening
of <ref>.
       	
       	
          [π-realizability]
       	
       	The policy class Π is such that forFor all
          π∈, we have that x↦_a∈_h[V^π_h+1](·, a)∈Π.  
      
      This assumption, also known as policy completeness has
      been used by a number of prior works on computationally
      efficient RL <cit.>. <ref> are both implied by the
      slightly simpler-to-state assumption of
      Q^π-realizability <cit.>, which asserts access to a class
       that contains Q^π for all π∈.

      
      

      
      
        <ref> can both be weakened to only
        require realizability for near-optimal policies; i.e.., we only
        need to assume that V^π_h ∈ for all h∈[H] and
        near-optimal policies π (instead of all policies). We will
        only use this weaker assumption in the analysis.
      
      
      
      

      
      
       	
        
        



        
  
        

 §.§ Algorithm

        
        






         















        For ease of exposition, we defer the full version of our
        algorithm, (<ref>), to
        <ref> and present a simplified version here
        (<ref>). 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.

maintains a value function estimator
=_1:H that aims to approximate the optimal value function
_1:H, as well as core sets _1,…,_H
of state-action pairs that are used to perform estimation and guide
exploration. At a high level,  alternates between (i)
fitting the value function _h for a given layer h∈H based on Monte-Carlo rollouts,
and (ii) using the core-sets to test whether the current value
function estimates _h+1:H  remain accurate as the
roll-in policy induced by _h changes.











In more detail, is based on recursion across the layers
h∈H. When invoked for layer h with value function
estimates _h+1:H and core-sets _h,…,_H,
_h performs two steps:

  

  *  For each state-action pair
  (x_h-1,a_h-1)∈_h,[Informally, _h represents a
    collection of state-action pairs (x_h-1,a_h-1) at layer h-1 for which we
    want
    **_h(_h)-_h(_h)|_h-1=x_h-1,_h-1=a_h-1≤
    for some small >0.]
    the algorithm gathers N_ trajectories by
    rolling out from (x_h-1,a_h-1) with the greedy policy
    _ℓ(x)∈_a∈_ℓ_ℓ+1(x,a) that
    optimizes the estimated value function; in the full version of
     (see <ref>), we estimate the
    bellman backup _ℓ_ℓ+1(x,a) using the local
    simulator. For all states
    x_ℓ-1∈_h,…,_H-1 encountered during this process, the
    algorithm checks whether
    **_ℓ(_ℓ)-_ℓ(_ℓ)|_ℓ-1=x_ℓ-1,_ℓ-1=a_ℓ-1
    for all a_ℓ-1∈
    using a test based on (implicitly maintained) confidence sets. If
    the test fails, this indicates that distribution shift has
    occurred, and the algorithm adds the pair
    (x_ℓ-1,a_ℓ-1) to the core-set _ℓ and
    recurses on layer ℓ via _ℓ.
  
  
  
  
  
  
  * 
If all tests above pass, this indicatesmeans that
_h+1,…,_H are accurate, and no distribution shift
has occurred. In this case, the algorithm fits _h by collecting
Monte-Carlo rollouts from all state-action pairs in the core-set _h with 
_ℓ(x)∈_a∈_ℓ_ℓ+1(x,a)
(cf. <ref>), and returns.
  	

When the tests in <ref> succeed for all layers h∈H, the
algorithm terminates and returns the estimated value functions
_1:H; in this case, the greedy policy
_ℓ(x)∈_a∈_ℓ_ℓ+1(x,a)
is guaranteed to be near optimal. The full version of  in <ref> uses local simulator access to estimate the Bellman backups _h[_h+1](x,a) for different state-action pairs (x,a) (see <ref> of <ref>). These backups are used to (i) compute actions
of the greedy policy that maximizes _1:H via (e.g.,
<ref>); (ii) generate trajectories by rolling out from
state-action pairs in the core-sets (<ref>); and (iii) perform the test in
<ref> (<ref>).

 is inspired by the  algorithm of
<cit.>, which was originally
introduced in the context of online reinforcement learning with
linearly realizable Q^⋆. incorporates local
simulator access (most critically, via core-set construction) to allow for more general nonlinear function
approximation without restrictive statistical assumptions. Prior
algorithms for RLLS have used core-sets of state-action pairs in a similar
fashion <cit.>, but
in a way that is tailored to linear function approximation.

  
  
  
  
  
  
  
  
  
  


In what follows, we discuss various features of the algorithm in
greater detail.














    
      

  
Bellman backup policies Since 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 _1:H∈ is as follows: for all h∈
      [H], define _h(x)∈_a∈_h[_h+1](x,a). In reality, we do not have access to
      _h[_h+1](x,a) directly, so the full version of
      (<ref>) estimates this quantity on the
      fly using the local
      simulator using the following scheme (<ref> in <ref>): Given a state x, for each a, we sample K rewards _h ∼
      R_h(x,a) and next-state transitions _h+1∼ T_h(·| x,a), then approximate _h[_h+1](x,a) by the
      empirical mean. We remark that the use of these Bellman backup
      policies is actually crucial in the analysis for ;
      even if we were to work with estimated state-action value
      functions _1:H instead, our analysis would require executing
      the Bellman backup policies _h(x)∈_a∈_h[_h+1](x,a) (instead of naively using _h(x)∈_a∈_h(x,a)).
   
      

        
   Invoking the algorithm
   
   
   
The base invocation of takes the form

    _1:H_0(_1:H=𝖺𝗋𝖻𝗂𝗍𝗋𝖺𝗋𝗒, _1:H=*_h_h=1^H,
      _0:H=*∅_h=0^H,
      ;, , δ).

Whenever this call returns, the greedy policy induced by _1:H
is guaranteed to be near-optimal. Naively, the approximate Bellman backup policy induced by
_1: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,  (<ref>, deferred to
<ref> for space), which invokes
_0, then extracts an executable policy from _1:H
using behavior cloning. Subsequent recursive calls to take the
form (_h:H,_h:H,
		_h:H)_h(_h+1:H,_h+1:H,_h:H;,,δ).

    (_h:H,_h:H,
    		_h:H)_h(_h+1:H,_h+1:H,_h:H;,,δ).





For such a call, the argumentsThe arguments here are: (i) _h+1:H: Value function estimates for subsequent layers;
(iii) _h+1:H: Value function confidence sets
  _h+1:H⊂_h+1:H, which are used in
  the test on <ref> to quantify
  uncertainty on new state-action pairs and decide
  whether to expand the core-sets; and (iii) _h:H: Core-sets for current and subsequent layers.



  * _h+1:H: Value function estimates for subsequent layers.

  * _h+1:H: Value function confidence sets
  _h+1:H⊂_h+1:H, which are used in
  the test on <ref> to quantify
  uncertainty on new state-action pairs and decide
  whether to expand the core-sets.

  * _h:H: Core-sets for current and subsequent layers.

Importantly, the confidence sets _h+1:H do not need
to be explicitly maintained, and can be used
implicitly whenever a regression oracle for the
value function class is available (discussed below). 


  
  
  
  
        






        






        
Oracle-efficiency
 is computationally efficient in the sense
  that: it reduces to convex optimization over the value
function class .









In particular,
the only computationally intensive steps in the algorithm are (i)
the regression step in <ref>,


and (ii) the test in
<ref> involving the confidence set _ℓ. For the
latter, we do not explicitly need to maintain _ℓ, as
the optimization problem over this set in <ref> (for
the full version of in <ref>) reduces to solving 
_V∈*±∑_i=1^nV(xi)|∑_i=1^n(V(xi)-yi)^2≤β^2
for a dataset
*(xi,xi,yi)_i=1^n. This is convex
optimization problem in function space, and in particular can be implemented in a
provably efficient fashion whenever  is linearly
parameterized. We expect that the problem can also be reduced to
a square loss regression by adapting the techniques in
<cit.>, but we do not
pursue this here.





































 §.§ Main Result

We present the main guarantee for  under the
function approximation assumptions in <ref>.
        
   
   	
   	Let ,δ∈(0,1) be given, and suppose that
        <ref> (pushforward coverability) holds with
        >0. Further, suppose that either Setup  (<ref>
          (/-realizability) and <ref>
          (Δ-gap)) with ≤ 8H^2Δ or  (<ref>
          (V^π-realizability) and <ref>
          (π-realizability)) holds.
         Further, suppose that one the following holds: 
          
                  
  * Setup : <ref>
          (/-realizability) and <ref>
          (Δ-gap) hold, and ≤  6 H·Δ. 
        
  * Setup : <ref>
          (V^π-realizability) and <ref>
          (π-realizability) hold.
   		
   		
   	
      
   	Then, (Π, , , δ) (<ref>) returns a policy
        _1:H such that J()-
        J(_1:H) ≤  2 with probability at least
        1-δ, and has total sample complexity bounded
        by
        O(^4 H^23A·^-7).[For Setup , note that the sample complexity
          implicitly depends on Δ^-1 through the constraint
          that ≤(H^2Δ).]
   	
    O(^8 H^23A·^-13).

             
   
   
  <ref> shows
  for the first time that sample- and computationally-efficient RL
  with local simulator access
  is possible under pushforward coverability. In particular,
  is the first computationally efficient algorithm for RL with
  local simulator access that supports nonlinear function
  approximation. The assumptions in
  <ref>, while stronger than those in
  <ref>, are not known to enable sample-efficient RL
  without simulator access. Nonetheless, understanding whether can be
  strengthened to support general coverability or weaker function
  approximation is an important open problem. See
    <ref> for an overview of the analysis; we remark (<ref>) that
    the result is actually proven under slightly weaker 
    assumptions than those in /.

  
  
  

  
  
  

  We mention in passing that  can be slightly modified to
  recover other existing sample complexity guarantees for RL with
  linear function approximation and local simulator access (which do not
  require pushforward coverability), including
  linear-Q^⋆ realizability with gap <cit.> and
  Q^π-realizability <cit.>; we leave a more
  general treatment for future work.  

Connection to empirical algorithms

 bears some similarity to Monte-Carlo Tree Search (MCTS)
<cit.> and AlphaZero
<cit.>, which perform planning with local simulator. Informally, MCTS can be viewed as a form of
breadth-first search over the state space (where each node represents a
state at a given layer), and AlphaZero is a particular instantiation of a MCTS
that leverages V-value function approximation (through a class  that
aims to approximate ) to accommodate stochastic
environments and allow for generalization across states.





Compared to , 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.  may be viewed as a provable
counterpart that uses function approximation to address distribution
shift in a principled fashion (in particular, through the use of confidence
sets and the test in <ref>).[We note in passing that in
the context of tree search, the pushforward coverability assumption (<ref>) may be viewed as the stochastic analogue of branching factor.]



 also has a resemblance to the Go-Explore algorithm
of <cit.>, which also uses core-sets of informative
state-action pairs to guide exploration (albeit in an ad-hoc,
domain-specific fashion) and uses imitation learning
to extract an executable policy after exploration completes. In light of these connections, we are optimistic that the techniques
in —in particular, using value function approximation
to guide systematic exploration—can help to inform the design of better practical algorithms for
learning and planning with local simulators.








 also has some resemblance to the Go-Explore algorithm
of <cit.> Like , Go-Explore makes use of core-sets of informative
state-action pairs to guide exploration, and uses imitation learning
to extract an executable policy after the exploration phase completes. However, Go-Explore uses an
ad-hoc, domain specific approach to building the core set, and does
not use function approximation in the exploration phase; such
a strategy is unlikely to succeed in more challenging environments
where the effective horizon is longer or less domain-specific
information is available a-priori.

In light of these connections, we are optimistic that the techniques
in —in particular, using value function approximation
to guide systematic exploration—can help to inform the design of practical algorithms for
learning and planning with local simulators.








                                
                                
                                
                                
                                
                                
                                





  
  


        









  
        
        
        
        
        
        
        
        

        
          Applying to Exogenous Block MDPs
          ExBMDPs satisfy coverability (<ref>),
          but do not satisfy the pushforward coverability assumption
          (<ref>) required by 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 to the weak correlation
            condition. In <ref> (<ref>), we give a variant
          of for ExBMDPs that succeeds under (i) weak
          correlation, and (ii) decoder realizability,
          sidestepping the need for the Δ-gap or
          V^π-realizability.
          
        
        
          

 §.§ Applying to Exogenous Block MDPs

          
          







We now apply to the Exogenous Block MDP (ExBMDP) model
introduced in
<ref>.
In this section, we apply to the Exogenous Block MDP (ExBMDP) model
introduced in
<ref>.
ExBMDPs satisfy coverability (<ref>),
but do not satisfy the pushforward coverability assumption
(<ref>) required by 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. 
[Weak correlation condition]
	 
For the underlying ExBMDP , there is a constant ≥ 1 such that for all h∈[H-1] and (ξ,ξ')∈Ξ_h-1×Ξ_h, we have[Throughout this paper, when
		considering the law for the exogenous variables
		_1,…,_H, we write *· instead of
		^π*· to emphasize that the law is independent of
		the agent's policy.]
	
    [_h =ξ,_h+1=ξ'] ≤·[_h =ξ] ·[_h+1=ξ'].


The weak correlation property asserts that the joint law for the
exogenous noise variables _h and _h+1 is at most a
multiplicative factor ≥1 larger than the corresponding product distribution obtained by sampling _h and _h+1 independently from their marginals. This setting strictly generalizes the (non-exogenous) Block MDP model
<cit.>, 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 underUnder <ref>, pushforward
coverability is satisfied with ≤·S A
(<ref> in <ref>). In addition,
V^⋆-realizability is implied by decoder realizability
(<ref>). Thus, by
applying <ref> (), we conclude that efficiently learns a near-optimal policy for any weakly correlated ExBMDP for
which the optimal value function has Δ-gap.







  
An improved algorithm for ExBMDPs: 
At first glance, removing the gap assumption for in ExBMDPs seems
difficult: The V^π-realizability assumption required to invoke
<ref> () is not satisfied by ExBMDPs, as
decoder realizability only implies V^π realizability for
endogenous policies π.[We say that a policy π is endogenous
  if it does not depend on exogenous noise, in the sense that
  π(_h) is a measurable function of (_h).]
In spite of this, we now show that with a slight modification,
can efficiently learn any weakly correlated ExBMDP under decoder
realizability alone (without gap or V^π-realizability).


Our new variant of , ^, is presented in
<ref> (deferred to <ref> for space). The
algorithm is almost identical to 
(<ref>), with the main difference being that we use
an additional randomized rounding step to compute the policies
_1:H from the learned value functions _1:H. In particular, instead
of directly defining the policies _1:H based on the bellman
backups _h[_h+1] as in <ref>,
^ targets a “rounded” version of the backup given by

    ·_h[_h+1](x,a)/ + _h,

where ∈(0,1) is a rounding parameter and _1, …, _H
are i.i.d. random variables sampled uniformly at random from the
interval [0,1/2] (at the beginning of the algorithm's
execution). Concretely, ^ estimates the bellman
backup _h[_h+1](x,a) in <ref> using the local
simulator (as in <ref> of <ref>), and defines its policies via

    _h(·) ∈_a∈_h[_h+1](·, a)/ + _h.


This rounding scheme, which quantizes the Bellman backup
into ^-1 bins with a random offset, is designed to emulate certain properties
implied by the Δ-gap assumption (<ref>). Specifically,
we show that with constant probability over the draw of
_1:H,and with high probability over the randomness in
, the policy  in (<ref>) “snaps” on to an
endogenous policy π. This means that for
^ to succeed (with constant probability), it
suffices to pass it a class  that realizes the value functions
(V^π_h) for endogenous policies π∈. Fortunately, such a function
class can be constructed explicitly under decoder realizability (<ref>).
   
	
	For the ExBMDP setting, under <ref>, the function class _h{x↦ f(ϕ(x)) : f∈ [0,H]^S, ϕ∈Φ}
	is such that V_h^π∈_h for all endogenous policies π. Furthermore, the policy class Π_h {π(·)∈_a∈ f(ϕ(·),a):f∈ [0,H]^S× A , ϕ∈Φ} contains all endogenous policies.
 

A 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 _1,…,_H. To address this, we
provide an outer-level algorithm, (<ref>, deferred to <ref> for space), which performs
confidence boosting by invoking multiple times
independently, and extracts a high-quality executable policy using
behavior cloning.




  
Main result

We now state the main guarantee for ^ (the proof is in <ref>).


  
  
  Consider the ExBMDP setting. Suppose the decoder class Φ
  satisfies <ref>, and that <ref> holds with >0.
  Let ,δ∈(0,1) be given, and let _h and
        Π_h be as in <ref>.
        
	
	
	
	
        Then (Π, _1:H, , ζ_1:H,δ)
        (<ref>) produces a policy _1:H
        such that J()- J(_1:H) ≤, and has
        total sample complexity 
	
    O(^8 S^8H^36A^9·^-26).


This result shows for the first time that sample- and
computationally-efficient learning is possible for ExBMDPs beyond
deterministic or factored settings <cit.>.

We mention in passing that our use of randomized rounding
to emulate certain consequences of the Δ-gap
assumption leverages the fact that ExBMDPs have a finite number of
(endogenous) latent states. It is unclear if this technique can be used when the (latent) state space is large or infinite.
          







           



          
          




 

        

§ CONCLUSION AND OPEN PROBLEMS

        
        
Our results show that online RL with local simulator access can enable powerful sample complexity guarantees for learning
with general value function approximation. Interesting open problems
and directions for future research include:
(i) Can we show that value function realizability and coverability
  are not sufficient for sample-efficient learning in the
  online RL framework, thereby separating this framework from ?
  (ii) Can we obtain computationally-efficient algorithms under the
  same assumptions as ? In addition, we are excited to explore the empirical performance of
exploration schemes inspired by in a large-scale evaluation.






  




















  * Is it true that value function realizability and coverability
  are not sufficient for sample-efficient learning in the
  online RL model? Combined with our results, this would imply a new
  separation between and online RL. More broadly, it would be interesting to develop a unified
  understanding for precisely when local simulator access can lead to
  statistical benefits over fully online RL, and to characterize the
  statistical complexity for this framework.


  * The algorithm is computationally efficient, but
  requires stronger statistical assumptions than our inefficient
  algorithms. Closing this gap with an efficient algorithm is an
  important but challenging open problem.
  
  
  
  

In addition, we are excited to explore the empirical performance of
exploration schemes inspired by .






 
        
        
        
        
        
        
        
        
        
        
        
        
        
        
	

  

 §.§ Acknowledgements

  Part of this work was done while ZM was at MIT. ZM and AR acknowledge support from the ONR through awards N00014-20-1-2336 and N00014-20-1-2394, and ARO through award W911NF-21-1-0328.
	
	
	
	
	
	
	
		
		
		toc
		
			
			
	
	
	
	
	
		
		
	
		
		
	
	
	
	

	

§ ADDITIONAL RELATED WORK

        
        


  
Local simulators: Theoretical research
RL with local simulators has received extensive interest in the context
of linear function approximation. Most notably, <cit.> show that
reinforcement learning with linear V^⋆ is tractable with local
simulator access, and <cit.> show that RL with
linear Q^⋆ and a state-action gap is tractable; online RL is
known to be intractable under the same assumptions
<cit.>. <cit.>
show that the gap assumption can be removed if a small number of
expert queries are available. Also of note are the
works of <cit.>, which give
computationally efficient algorithms under linear
Q^π-realizability for all π; this setting is known to be tractable in the
online RL model <cit.>, but computationally efficient algorithms are
currently only known for .




Global simulators—in which the agent can query arbitrary
state-action 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
<cit.>.



  
Local simulators: Empirical research
The Go-Explore
algorithm <cit.> uses local simulator
access to achieve state-of-the-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
<cit.> are roughly a factor of four
worse in terms of cumulative reward. Interestingly,
like , Go-Explore 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 <cit.> 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
<cit.>. 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 <cit.>, include <cit.>.



  
Planning
RL 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
<cit.> and practice (e.g., MuZero <cit.>).
Since the model is known, computing an
optimal policy is a purely computational problem, not a statistical
problem. Nonetheless, 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 algorithm immediately yields an efficient
algorithm for planning.

Empirically, Monte-Carlo Tree Search <cit.> is a successful paradigm for
planning, acting as a key component in AlphaGo
<cit.> and AlphaZero
<cit.>.[Compare to our work, a small
  difference is that these works are not concerned with producing
  executable policies, c.f. <ref>.] Viewed as a
planning algorithm, a potential advantage of is that it is
well suited to stochastic environments, and provides a principled way
to use estimated (neural) value function estimates to guide exploration.

  














  
Coverability
<cit.> introduced coverability as a structural parameter
for online reinforcement leanring, inspired by connections between
online and offline RL. Existing guarantees for the online RL framework
based on coverability require either Bellman completeness <cit.>, model-based
  realizability <cit.>, or weight
  function realizability
  <cit.>), and it is not
  currently known whether value function realizability is sufficient
  in this framework.

  

  
Exogenous Block MDPs
  Our results in <ref> (<ref>) show that
  general Exogenous Block MDPs are learnable with local simulator
  access. Prior work, on learning EXBMDPs in the online RL model requires additional assumptions:
       
       	
  * Deterministic ExBMDP
          <cit.>. In this setting, the latent transition
          distribution  is assumed to be deterministic. In
          this case, it suffices to learn open-loop policies
          (i.e., policies that play a deterministic sequence of actions). This avoids compounding errors due to learning imperfect decoders that depend on the exogenous noise, making this setting much less challenging than the general ExBMDP setting.
       	
  * Factored ExMDP <cit.>. This is
          an ExBMDP setting with a restrictive structure in which the
          observation is a d-dimensional vector and the latent state
          is a k-dimensional subset of the observed
          coordinates. This structure prevents the setting from
          subsuming the basic (non-exogenous) Block MDP framework, and makes it
          possible to learn decoders that act only on the endogenous
          state, preventing compounding errors.
          
          
          
       	
  * Bellman completeness.            <cit.> observed that ExBMDPs admit low
           coverability, but their algorithm requires Bellman
           completeness, which is not satisfied by ExBMDPs (see
           <cit.>).

          
          
       	   
  












 


          
	
	
	
	
	




  

PART: 
Additional Results

  This section of the appendix contains additional results omitted
  from the main body due to space constraints.
  
  

§ APPLYING TO EXOGENOUS BLOCK MDPS

          
          







We now apply to the Exogenous Block MDP (ExBMDP) model
introduced in
<ref>.
In this section, we apply to the Exogenous Block MDP (ExBMDP) model
introduced in
<ref>.
ExBMDPs satisfy coverability (<ref>),
but do not satisfy the pushforward coverability assumption
(<ref>) required by 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. 
[Weak correlation condition]
	 
For the underlying ExBMDP , there is a constant ≥ 1 such that for all h∈[H-1] and (ξ,ξ')∈Ξ_h-1×Ξ_h, we have[Throughout this paper, when
		considering the law for the exogenous variables
		_1,…,_H, we write *· instead of
		^π*· to emphasize that the law is independent of
		the agent's policy.]
	
    [_h =ξ,_h+1=ξ'] ≤·[_h =ξ] ·[_h+1=ξ'].


The weak correlation property asserts that the joint law for the
exogenous noise variables _h and _h+1 is at most a
multiplicative factor ≥1 larger than the corresponding product distribution obtained by sampling _h and _h+1 independently from their marginals. This setting strictly generalizes the (non-exogenous) Block MDP model
<cit.>, 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 underUnder <ref>, pushforward
coverability is satisfied with ≤·S A
(<ref> in <ref>). In addition,
V^⋆-realizability is implied by decoder realizability
(<ref>). Thus, by
applying <ref> (), we conclude that efficiently learns a near-optimal policy for any weakly correlated ExBMDP for
which the optimal value function has Δ-gap.







  
An improved algorithm for ExBMDPs: 
At first glance, removing the gap assumption for in ExBMDPs seems
difficult: The V^π-realizability assumption required to invoke
<ref> () is not satisfied by ExBMDPs, as
decoder realizability only implies V^π realizability for
endogenous policies π.[We say that a policy π is endogenous
  if it does not depend on exogenous noise, in the sense that
  π(_h) is a measurable function of (_h).]
In spite of this, we now show that with a slight modification,
can efficiently learn any weakly correlated ExBMDP under decoder
realizability alone (without gap or V^π-realizability).


Our new variant of , ^, is presented in
<ref> (deferred to <ref> for space). The
algorithm is almost identical to 
(<ref>), with the main difference being that we use
an additional randomized rounding step to compute the policies
_1:H from the learned value functions _1:H. In particular, instead
of directly defining the policies _1:H based on the bellman
backups _h[_h+1] as in <ref>,
^ targets a “rounded” version of the backup given by

    ·_h[_h+1](x,a)/ + _h,

where ∈(0,1) is a rounding parameter and _1, …, _H
are i.i.d. random variables sampled uniformly at random from the
interval [0,1/2] (at the beginning of the algorithm's
execution). Concretely, ^ estimates the bellman
backup _h[_h+1](x,a) in <ref> using the local
simulator (as in <ref> of <ref>), and defines its policies via

    _h(·) ∈_a∈_h[_h+1](·, a)/ + _h.


This rounding scheme, which quantizes the Bellman backup
into ^-1 bins with a random offset, is designed to emulate certain properties
implied by the Δ-gap assumption (<ref>). Specifically,
we show that with constant probability over the draw of
_1:H,and with high probability over the randomness in
, the policy  in (<ref>) “snaps” on to an
endogenous policy π. This means that for
^ to succeed (with constant probability), it
suffices to pass it a class  that realizes the value functions
(V^π_h) for endogenous policies π∈. Fortunately, such a function
class can be constructed explicitly under decoder realizability (<ref>).
   
	
	For the ExBMDP setting, under <ref>, the function class _h{x↦ f(ϕ(x)) : f∈ [0,H]^S, ϕ∈Φ}
	is such that V_h^π∈_h for all endogenous policies π. Furthermore, the policy class Π_h {π(·)∈_a∈ f(ϕ(·),a):f∈ [0,H]^S× A , ϕ∈Φ} contains all endogenous policies.
 

A 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 _1,…,_H. To address this, we
provide an outer-level algorithm, (<ref>, deferred to <ref> for space), which performs
confidence boosting by invoking multiple times
independently, and extracts a high-quality executable policy using
behavior cloning.




  
Main result

We now state the main guarantee for ^ (the proof is in <ref>).


  
  
  Consider the ExBMDP setting. Suppose the decoder class Φ
  satisfies <ref>, and that <ref> holds with >0.
  Let ,δ∈(0,1) be given, and let _h and
        Π_h be as in <ref>.
        
	
	
	
	
        Then (Π, _1:H, , ζ_1:H,δ)
        (<ref>) produces a policy _1:H
        such that J()- J(_1:H) ≤, and has
        total sample complexity 
	
    O(^8 S^8H^36A^9·^-26).


This result shows for the first time that sample- and
computationally-efficient learning is possible for ExBMDPs beyond
deterministic or factored settings <cit.>.

We mention in passing that our use of randomized rounding
to emulate certain consequences of the Δ-gap
assumption leverages the fact that ExBMDPs have a finite number of
(endogenous) latent states. It is unclear if this technique can be used when the (latent) state space is large or infinite.
          







           











































 









 








		

§ HELPER LEMMAS

		This section of the appendix contains supporting lemmas used within
the proofs of our main results. 
		
 	
 






 §.§ Concentration and Probability



	
	Let δ∈(0,1) and H≥ 1 be given. If a sequence of events _1,…,_H satisfies [_h|_1,…,_h-1]≥1-δ/H for all h∈[H], then 
    [_1:H]≥1-δ.



	By the chain rule, we have
	
    [_1:H] = ∏_h∈[H][_h|_1,…,_h-1] ≥∏_h∈[H] (1-δ/H) =(1-δ/H)^H ≥ 1-δ.



We make use of the following version of Freedman's inequality, due to <cit.>:

	
	Let R>0 be given and let _1,…_n be a sequence of
        real-valued random variables adapted to filtration
        _1,⋯, _n. Assume that for all t∈[n], _i ≤ R and [_i|_i-1]=0. Define S_n∑_t=1^n_i and V_n∑_t=1^n [_i^2|_i-1]. Then, for any δ∈(0,1) and λ∈[0,1/R], with probability at least 1-δ, 
	
    S_n ≤λ V_n + ln (1/δ)/λ.

      

We will also use the following lemma, which is a standard consequence
of Freedman's inequality.      

	
	Let (_t)_t≤T be a sequence of random
	variables adapted to a filtration _t_t≤T. If
	0≤_t≤R almost surely, then with probability at least
	1-δ,
	
    ∑_t=1^T_t ≤3/2∑_t=1^T_t-1*_t +
    		4Rlog(2δ^-1),
    		and   ∑_t=1^T_t-1*_t≤ 2∑_t=1^T_t + 8Rlog(2δ^-1).





 §.§ Regression

      
Using <ref>, we obtain the following concentration lemma, which will be
used to prove guarantees for square loss regression within our algorithms.
	
	
	Let B>0 and n∈ℕ be given, and let  be an
        abstract set. Further, let ⊆{g:→
        [0,B]} be a finite function class and _1,…, _n be
        a sequence of random variables in  adapted to filtration
        a _1, ⋯, _n. Then, for any δ∈(0,1), with probability at least 1-δ, we have 
	
    ∀ g∈,   1/2g^2 - 2 B^2log(2||/δ) ≤g_n^2 ≤ 2 g^2 + 2B^2 log(2||/δ),

		where g^2 ∑_i∈[n][g(_i)^2|_i-1] and g_n^2 ∑_i=1^n g(_i)^2.


Fix g∈. Applying <ref> with _i = g(_i)^2- [g(_i)^2|_i-1], for all i∈[n], and (R,λ) =(B^2,1/B^2), we get that with probability at least 1-δ/(2||):

    g_n^2 - g^2    ≤λ B^2 g^2 + log(2||/δ)/λ.

By substituting λ = B^-2 and rearranging, we get 

    g_n^2 ≤ 2 g^2 + B^2 log (2||/δ).

Similarly, applying <ref> with _i = [g(_i)^2|_i-1]-g(_i)^2, for all i∈[n], and (R,λ) =(B^2, 1/(2B^2)), we get that with probability at least 1-δ/(2||):

    g^2 - g_n^2     ≤λ B^2 g^2 + log(2||/δ)/λ.

By substituting λ = 2^-1B^-2 and rearranging, we get 

    g_n^2 ≥1/2g^2 -2B^2 log (2||/δ).

Combining this with (<ref>) and the union bound, we get the desired result.


With this lemma, we now prove the following key result for square loss regression.

		
		Let B>0 and n∈ℕ be given and  be an abstract set. Further, let ⊆{f:→ [0,B]} be a finite function class, and suppose that there is a function f_⋆∈ and a sequence of random variables (_1,_1),…, (_n,_n)∈× such that for all i∈[n]:
		
			
  * _i = f_⋆(_i) + _i + b_i; 
			
  * |b_i|≤ξ;
			
  * _i∈[-B,B]; and
			
  * [_i |𝔉_i]=0, where 𝔉_i σ(_1:i, _1:i-1, _1:i-1, b_1:i-1).
			
Then, for ∈_f∈∑_i=1^n(f(_i)- _i)^2 and any δ∈(0,1), with probability at least 1-δ/2,
		
    - f_⋆_n^2  ≤ 4B^2 log(2||/δ)+4 B ∑_i=1^n |b_i|,

	where - f_⋆^2_n  ∑_i=1^n ((_i)- f^⋆(_i))^2.
       
	
		Fix δ∈ (0,1) and let _n(f) ∑_i=1^n (f(_i)- _i)^2, for f∈, and note that since ∈_f∈_n(f), we have
		
    0 ≥_n()- _n(f_⋆) = ∇_n(f_⋆)[ - f_⋆] +  - f_⋆^2_n,

  where ∇ denotes directional derivative. Rearranging, we get that 
	
    - f_⋆^2_n 
    	   ≤ - 2 ∇_n(f_⋆)[ - f_⋆] -  - f_⋆_n^2, 
        = 4 ∑_i=1^n (_i - f_⋆(_i)) ((_i)- f_⋆(_i))-  - f_⋆^2_n, 
       ≤ 4 ∑_i=1^n (_i + b_i) ((_i)- f_⋆(_i))-  - f_⋆^2_n, 
       ≤4∑_i=1^n _i · ((_i)- f_⋆(_i))-  - f_⋆^2_n_I  +4 ∑_i=1^n  b_i·  ((_i)- f_⋆(_i))_II.

	Bounding Term I To bound Term I, we apply <ref> with _i = _i · ((_i)- f_⋆(_i)), R = B^2, λ = 1/(8B^2), and _i=𝔉_i+1^-, and use 
	
		
  * the union bound over f∈; and
		
  * the facts that [_i|𝔉_i^-]= _i and [_i|𝔉_i^-]= 0,
		
		to get that with probability at least 1-δ/2,
	
    4∑_i=1^n _i · ((_i)- f_⋆(_i)) ≤ -f_⋆^2_n + 4 B^2 log(2||/δ).

		By rearranging, we get that with probability at least 1-δ/2,  
		
    Term I≤ 4 B^2 log(2 ||/δ).

			Bounding Term II We now bound the
                        second term in (<ref>). For this, note that since - f_⋆_∞≤ B, we have 
			
    Term II≤ 4 B∑_i=1^n |b_i|.

				This completes the proof. 
	





 §.§ Reinforcement Learning


	
	For any two policies , π∈ and t ∈[H], we have
	
    ^π[ V^π_t(_t)- V^_t(_t)] = ^π[∑_h=t^H Q_h^(_h,π_h(_h)) - Q_h^(_h, _h(_h)) ].

	In particular, applying this for t = 1 gives
	
    J(π)-J() = ^π[∑_h=1^H Q_t^(_h,π_h(_h)) - Q_h^(_h, _h(_h)) ].







	
	Fix h∈H. Suppose we have a sequence of functions g1,…,gT∈0,B
	and policies π1,…,
	πT such that 
	
    ∀ t ∈[T],   ∑_i<t^πi*(gt(_h))^2≤β^2

        for some β≥0.
	Then under <ref>, we have
            
    ∑_t=1^T^πt*gt(_h)≤ 2√(β^2Tlog(2T)) + 2B,

            and consequently
	
    min_t∈[T]^πt*gt(_h)≤ 2√(β^2 log (2T)/T) + 2B/T.

      
      
       See proof of <cit.>.
	  

The following result is a variant of the coverability-based potential
argument given in <cit.>.

	
	
	Fix h∈H. Suppose we have a sequence of functions g1,…,gT∈0,B
	and state-action pairs (x1,a1),…,
	(xT,aT) such that 
	
    ∀ t ∈[T],   ∑_i<t*(gt(_h))^2|_h-1=xi,_h-1=ai≤β^2

        for some β≥0.
	Then under <ref>, we have
            
    ∑_t=1^T*gt(_h)|_h-1=xt,_h-1=at≤ 2√(β^2Tlog(2T)) + 2B,

            and consequently
	
    min_t∈[T]*gt(_h)|_h-1=xt,_h-1=at≤ 2√(β^2 log (2T)/T) + 2B/T.

      
      
        
  Define
  d_ht(x)[_h=x|_h-1=xt,_h-1=at],
  and let _ht∑_i<tdi. Let
  
    τ_h(x)min*t|_ht(x)≥·μ_h(x).

We have

    ∑_t=1^T*gt(_h)|_h-1=xt,_h-1=at
       = ∑_t=1^T∑_x∈dt_h(x)gt(x) 
       ≤∑_t=1^T∑_x∈dt_h(x)gt(x)t≥τ_h(x)
      + B∑_t=1^T∑_x∈dt_h(x)t<τ_h(x).

From the definition of pushforward coverability, we can bound

    ∑_t=1^T∑_x∈dt_h(x)t<τ_h(x)
      =   ∑_x∈τ_h(x)_h(x)
      ≤ 2∑_x∈μ_h(x)=2.

For the other term, we bound

    ∑_t=1^T∑_x∈dt_h(x)gt(x)t≥τ_h(x)
       ≤*∑_t=1^T∑_x∈(dt_h(x))^2/t_h(x)t≥τ_h(x)^1/2·*∑_t=1^T∑_x∈_ht(x)(g_ht(x))^2
        ^1/2
        = *∑_t=1^T∑_x∈(dt_h(x))^2/t_h(x)t≥τ_h(x)^1/2·*∑_t=1^T∑_i<t*(gt(_h))^2|_h-1=xi,_h-1=ai^1/2
       ≤*∑_t=1^T∑_x∈(dt_h(x))^2/t_h(x)t≥τ_h(x)^1/2·√(β^2T).

Finally, we have

    ∑_t=1^T∑_x∈(dt_h(x))^2/t_h(x)t≥τ_h(x)   ≤ 2
        ∑_t=1^T∑_x∈(dt_h(x))^2/t_h(x)+μ_h(x)
       ≤ 2∑_t=1^T∑_x∈μ_h(x)dt_h(x)/t_h(x)+μ_h(x)
         = 2∑_x∈μ_h(x)
        ∑_t=1^Tdt_h(x)/t_h(x)+μ_h(x)
         = 4log(T+1),

where the last line uses Lemma 4 of <cit.>.











  




PART: 
Proofs for (sec:sample)
	
	
        





  As described in <ref>, the main difference between
   and lies in the construction of the confidence
  sets. The most important new step in the proof of
  <ref> is to show that the local simulator-based confidence
  set construction in <ref> is valid in the sense that the
  property <ref> holds with high probability. From here,
  the sample complexity bound follows by adapting the
  change-of-measure argument based on coverability from
  <cit.>.

  To this end, this part of the appendix is organized as follows. We first state and prove technical lemmas
  concerning realizability (<ref>) and the confidence set
  construction 
  (<ref> and <ref>) in
  <ref>. Then, in <ref>, we prove
  <ref> as a consequence.

  
  



§ PRELIMINARY LEMMAS FOR PROOF OF THM:GOLF










  For this section, we define

    ℓ_ht(g)
    	(
    		g_h(_ht, _ht)
    		- 1/K∑_k=1^K( _ht,k+ max_a∈g_h+1(_h+1t,k,a) ) 
    	)^2

and

    _ht(g)
    	^πt**g_h(_h, _h)-_h[g_h+1](_h,_h)^2,

where (_ht, _ht,_ht,k,_h+1t,k) are as in <ref>.


  
  For the ExBMDP setting, under <ref>, the function class _h{(x,a)↦ g(ϕ(x),a) : g∈ [0,H]^S A, ϕ∈Φ}
  satisfies <ref> and has
  log_h=logΠ_h=(SA+logΦ).[Formally,
    this requires a standard covering number argument; we omit
    the details.]
 



	
	With probability at least 1-δ, for all h∈H, 
	t∈N, and g∈,
	
    ∑_i<t_hi(g) ≤
    		3∑_i<t^πi**
    				g_h(_h, _h) - _h[g_h+1](_h,_h)^2 +
    		8N/K
    		+ 
    		16log(2HN*δ^-1),
    		and   ∑_i<t^πi**
    				g_h(_h,_h) - _h[g_h+1](_h,_h)^2≤
    		4∑_i<t_hi(g) + 8N/K +64log(2HN*δ^-1).




	Let t∈N and h∈H be fixed. Let us denote
	_ht=*(_ht,k,_h+1t,k)_k∈K. Define a filtration 
	
    t
    		= σ(τ1,1_1,…,1_H,…,τt,t_1,…,t_H),

	where τi is the trajectory generated in the
        ith iteration of <ref> (see <ref>). Fix g∈. Observe that _hi(g)∈*0,4, so
	<ref> ensures that with probability at
	least 1-δ,
	
    ∑_i<t_hi(g) ≤3/2∑_i<t*_hi(g)|i-1 +
    		16log(2δ^-1),
    		and   ∑_i<t*_hi(g)|i-1≤
    		2∑_i<t_hi(g) + 32log(2δ^-1).

	By the AM-GM inequality, for all i<t, we can bound
		
    *_hi(g)|i-1
       =**
    				g_h(_hi, _hi)
    				- 1/K∑_k=1^K*_hi,k+max_a∈g_h+1(_h+1i,k, a)^2|i-1
       ≤
    		2  **
    				g_h(_hi, _hi) - _h[g_h+1](_hi,_hi)^2|i-1
          
    			+ 2**
    					
    					_h[g_h+1](_hi,_hi)
    						-1/K∑_k=1^K*_hi,k+max_a∈ g_h+1(_h+1i,k,a)^2|i-1.

		and
		
    *_hi(g)|i-1
       ≥1/2**
    					g_h(_hi, _hi) - _h[g_h+1](_hi,_hi)^2|i-1
          
    			-**
    					
    					_h[g_h+1](_hi,_hi)
    						-1/K∑_k=1^K*_hi,k+max_a∈ g_h+1(_h+1i,k, a)^2|i-1.

			We have
			
    **
    						g_h(_hi, _hi) -
    						_h[g_h+1](_hi,_hi)^2|i-1
    				= ^πi**
    						g_h(_h, _h) - _h[g_h+1](_h,_h)^2

			and 
			
    **
    						
    							_h[g_h+1](_hi,_hi)
    							-1/K∑_k=1^K*_hi,k+max_a∈g_h+1(_h+1i,k, a)^2|i-1
       =***
    								
    								_h[g_h+1](_h,_h)
    									-1/K∑_k=1^K*_hi,k+max_a∈g_h+1(_h+1i,k, a)^2|_h=_hi,_h =_hi|i-1.

						Since 
    *_hi,k+max_a∈g_h+1(_h+1i,k, a)|_h = _hi,_h  = _hi=_h[g_h+1](_hi,_hi)

						and *(_hi,k,_h+1i,k)_k∈K are
						conditioned on (_h,_h)=(_hi,_hi), we have, 
						
    **
    									
    										_h[g_h+1](_h,_h)
    										-1/K∑_k=1^K*_hi,k+max_a∈g_h+1(_h+1i,k, a)^2|_h = _hi,_h = _hi
       = 1/K**_h[g_h+1](_h,_h)
    											-*_hi,k+ max_a∈g_h+1(_hi,k, a)
    										^2|_h = _hi,_h = _hi
       ≤4/K,

								so that
								
    **
    											
    												_h[g_h+1](_hi,_hi)
    												-1/K∑_k=1^K*_hi,k+max_a∈g_h+1(_h+1i,k,a)^2|i-1≤4/K.

									Combining
                                                                        these
                                                                        bounds
                                                                        with
                                                                        (<ref>)
                                                                        and
                                                                        rearranging thus
									gives
									
    ∑_i<t_hi(g) ≤
    										3∑_i<t^πi**
    												g_h(_h,_h) - _h[g_h+1](_h,_h)^2 +
    										8N/K
    										+ 
    										16log(2δ^-1),
    										and   ∑_i<t^πi**
    												g_h(_h,_h) - _h[g_h+1](_h,_h)^2≤
    										4∑_i<t_hi(g) + 8N/K + 64log(2δ^-1).

									Taking a union bound yields the result.
								
								
								
									
									Define =16log(2HN*δ^-1).
									Suppose we set K≥8N/ and β≥2. Then with
									probability at least 1-δ, for all t∈N and
									h∈:
									
										
  * ∈t.
										
  * All g∈t satisfy
										
    ∑_i<t^πi**g_h(_h,_h)-_h[g_h+1](_h,_h)^2≤ 9β.

									
								
								
									Condition on the event in <ref>. For any
									fixed t∈N and h∈H, we have that
									
    ∑_i<t_hi()    ≤
    										3∑_i<t^πi**_h(_h,_h) - _h[_h+1](_h,_h)^2 +
    										8N/K
    										+ 
    										16log(2HN*δ^-1)
       ≤8N/K
    										+ 
    										16log(2HN*δ^-1)
    										≤2,

									where the first inequality uses that
									_h=_h[_h+1] and the second inequality uses
									our choice for K. It follows that ∈t as long as
									β≥2.
									
									To prove the second claim, we note that for all g∈t, by construction,
									
    ∑_i<t^πi**
    												g_h(_h) - _h[g_h+1](_h,_h)^2   ≤
    										4∑_i<t_hi(g) + 8N/K
    										+64log(2HN*δ^-1)
       ≤      4∑_i<t_hi(g) + 5≤ 9β.

									
								
								
								

§ PROOF OF THM:GOLF

								

								
									From <ref>, the parameter setting in the
									theorem
                                                                        statement
                                                                        ensures
                                                                        that
                                                                        with
                                                                        probability
                                                                        at
                                                                        least
                                                                        1-δ, 
                                                                        for
                                                                        all t∈ [2 N],
									∈t, and all g∈t satisfy
									
    ∑_i<t^πi**g_h(_h)-_h[g_h+1](_h,_h)^2≤ 9β.

									for
                                                                        all
                                                                        h.
                                                                        Let
                                                                        us
                                                                        condition
                                                                        on
                                                                        this
                                                                        event
                                                                        going
                                                                        forward. First,
                                                                        note
                                                                        that
                                                                        since
                                                                        ∈t
                                                                        for
                                                                        all
                                                                        t∈ [2  N],
                                                                        we
                                                                        have that
									
    J() ≤[max_a∈_1(_1,a)]≤sup_g∈t[max_a∈g_1(_1, a)].

									On
                                                                        the
                                                                        other
                                                                        hand,
                                                                        we
                                                                        have
                                                                        gt∈_g∈t∑_s<
                                                                          tmax_a∈g_1(s_1,
                                                                        a),
                                                                        and
                                                                        so
                                                                        since
                                                                        _11,_12,
                                                                        …
                                                                        are
                                                                        i.i.d. and
                                                                        any
                                                                        g∈t
                                                                        take
                                                                        values
                                                                        in
                                                                        [0,H],
                                                                        we
                                                                        have
                                                                        that
                                                                        by
                                                                        Hoeffding's inequality, there is an event  of probability at least 1- δ under which  
									
    ∀ t ∈[2  N], ∀ g∈,    |[max_a∈g_1(_1,a )]- 1/t-1∑_s < tmax_a∈g_1(_1s, a)| ≤√((t-1)^-1log(2N||/δ)).

									This implies that under , we have 
									
    ∀ t ∈ [2 N],   sup_g∈t[max_a∈g_1(_1,a)]    ≤sup_g∈t1/t-1∑_s< tmax_a∈g_1(_1s,a)+ √((t-1)^-1log(2N||/δ)), 
        = 1/t-1∑_s< tmax_a∈g_1t(_1s,a)+ √((t-1)^-1log(2N||/δ)), 
       ≤[max_a∈g_1t(_1,a)] + 2√((t-1)^-1log(2N||/δ)),

									where
                                                                        in
                                                                        the
                                                                        last
                                                                        inequality
                                                                        we
                                                                        have
                                                                        used
                                                                        (<ref>) with f= gt. Thus, summing (<ref>) for t=2,… N and using (<ref>) gives that under :
									
    ∑_t=2^N J() ≤∑_t=2^N [g_1t(_1,_1)] + 4√(Nlog(2N||/δ)),
    									and so since J()≤ H,∑_t=1^N J() ≤∑_t=1^N [g_1t(_1,_1)] + 4√(Nlog(2N||/δ)) + H.
			
									On the other hand, using that gt_H+1≡ 0, we get
									
    ∑_t=1^N([g_1t(_1, _1)]  - J(πt))
       ≤∑_t=1^N∑_h=1^H ^πt[gt_h (_h, _h) - _h - max_a∈gt_h+1(_h+1, a)], 
        = ∑_t=1^N∑_h=1^H ^πt[ gt_h (_h, _h) - [_h + max_a∈gt_h+1(_h+1, a)|_h,_h]],   (law of total expectation)
        = ∑_t=1^N∑_h=1^H ^πt[ gt_h (_h,_h) - _h[gt_h+1](_h,_h)]. and so, by the potential lemma (<ref>) and (<ref>), we have
    										   ≤  6H √(β  N log(2N))+ 2 H^2 .

								
									Combining
                                                                        this
                                                                        with
                                                                        (<ref>),
                                                                        we
                                                                        obtain
                                                                        that
                                                                        with
                                                                        probability
                                                                        at
                                                                        least 1-2δ,
									
    ∑_t=1^N( J() - J(πt))   ≤ 6H √(β  N  log(2N)) +4√(Nlog(2N||/δ))+ 3 H^2 .

 It follows that if  N=(H^2β/^2), then the policy 
    ∈(π1,…, πN)
 returned by  satisfies, with probability at least 1-δ:
									
    J() - [J( )] ≤.

									

  
Sample complexity
									We
                                                                        now
                                                                        bound
                                                                        the
                                                                        number
                                                                        of
                                                                        episodes. Note
                                                                        that
                                                                        that
                                                                        within
                                                                        an
                                                                        iteration
                                                                        t
                                                                        of
                                                                        ,
                                                                        the
                                                                        local
                                                                        simulator
                                                                        is
                                                                        called
                                                                        KH
                                                                        times
                                                                        to
                                                                        update
                                                                        the
                                                                        confidence
                                                                        set,
                                                                        where
                                                                        K
                                                                        ≤
                                                                        N/log(2HN||/δ)). Consequently,
                                                                        the
                                                                        total sample complexity is bounded by 
									
    H	N K ≤O(H^5 ^2 log(||/δ)/^4).

								




 


PART: 
Proofs for (sec:computation)
	

        

§ FULL VERSION OF 

        
        
<ref> displays the full version of . <ref> contains an “outer-level” wrapper for
, , which invokes
and extracts an executable policy with imitation learning,
and <ref> contains the subroutine used within
<ref> to approximate Bellman backups for value
functions using local simulator access. Additionally, we display the
variant of for Exogenous Block MDPs, described in
<ref>, in <ref>.
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.



  
Differences between full version (<ref>)
  and informal version (<ref>) of  The main difference between <ref> and its full version in <ref> is that in the former we simply assume access to quantities involving conditional expectations such as:
  
  	
  * The bellman backups _h[_h+1], which are required to evaluate the actions of 's policies (see (<ref>)), and to perform the tests in <ref>; and 
  	
  * The value functions ^_h+1:H[∑_ℓ=h^H _τ|_h =x,_h =a] in <ref>, which are needed in the regression problem in <ref>.
  	
 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  in <ref>.



	

  
Extracting policies from value functions
	
	Let us briefly comment in more detail on how
	<ref> extracts the policy πt from the
	optimistic value function ft∈ at iteration t. From the
	Bellman equation, the ideal
	choice would be to set
	π_ht(x)=_a∈_h*f_h+1t(x,a),
	but this requires knowledge of the transition distribution. Instead,
	given parameters ,δ∈(0,1), invokes
	<ref> via
	
	
        πt_h(x)∈_a∈_h,,δ
        [ft_h+1](x,a).
        
	
	
	
	
		
		
	The operator _h,,δ[f]
	(<ref>), when given input (x,a)∈×
	and f_h+1:→, uses the local simulator to generate N_≥ 1 next
	states _h+11, …,
	_h+1N_i.i.d.∼ T_h(·| x,a) to estimate the bellman back-up
	_h[f_h+1] via 1/N_∑_i=1^N_ (i_h+
	f_h+1(_h+1i)), where _h1,…,
	_hN_i.i.d.∼R_h
	(x,a). The number of samples N_ in <ref> is
	set as a function of (,δ) such that with probability at least 1-δ, |_h,,δ[f_h+1](x,a)-
	_h[f_h+1](x,a)|≤. 



  
Invoking the algorithm
The base invocation of takes the form

    _1:H_0(_1:H=𝖺𝗋𝖻𝗂𝗍𝗋𝖺𝗋𝗒, _1:H=*_h=1^H,
    	_0:H=*∅_h=0^H,
    	_0:H=*∅_h=0^H,t_1:H=*1_h=1^H;⋯).

Whenever this call returns, the greedy policy induced by _1:H
is guaranteed to be near-optimal. Naively, the policy induced by
_1:H is non-executable, and must be computed by invoking the
local simulator through <ref>. To provide an end-to-end
guarantee to learn an executable policy, the outer-level
algorithm,  (<ref>, invokes
_0, then extracts an executable policy from _1:H
using imitation learning.

Subsequent recursive calls take the
form

    (_h:H,_h:H,
    	_h:H,_h:H, t _h:H)_h(_h+1:H,_h+1:H,_h:H,_h:H, t_h:H;,,δ).

For such a call, the arguments above are: (i) _h+1:H: Value function estimates for subsequent layers;
	(ii) _h:H: Core-sets for current and subsequent layers;
	(iii) t_h:H: Counters that track the number of times
	<ref> is called in
	the test on <ref>, which facilitate
	tuning of confidence parameters;
	(iv) _h+1:H: Value function confidence sets
	_h+1:H⊂_h+1:H, which are used in
	the test on <ref> to quantify
	uncertainty on new state-action pairs and decide
	whether to expand the core-sets; and (v)
	_h:H: Buffers of tuples
	(x_h-1,a_h-1, _h ,_h, t_h), which
	record relevant features of the algorithm's state whenever the test on <ref>
	fails and a recursive call is performed.

		
  * _h+1:H: Value function estimates for
                  subsequent layers.
                  		
  * _h+1:H: Value function confidence sets
		_h+1:H⊂_h+1:H, which are used in
		the test on <ref> to quantify
		uncertainty on new state-action pairs and decide
		whether to expand the core-sets.
		
  * _h:H: Core-sets for current and subsequent layers.


		
		
  * _h:H: Buffers of tuples
		(x_h-1,a_h-1, _h ,_h, t_h), which
		record relevant features of the algorithm's state whenever the test on <ref>
		fails and a recursive call is performed.

                		
  * t_h:H: Counters that track the number of times
		<ref> is called in
		the test on <ref>, which facilitate
		tuning of confidence parameters.

Importantly, the confidence sets _h+1:H do not need
to be explicitly maintained, and can be invoked
implicitly whenever a regression oracle for the
value function class is available (cf. discussion in <ref>). Likewise, the buffers
_h:H are only used in our analysis, and do not
need to be explicitly maintained.

  
	
	
        
        
        
        

  



 §.§ Pseudocode














































































 





 













































































 






 




      
      




 




         
        

 §.§ ^ Pseudocode

          











































 









 

        


§ ORGANIZATION

        

§ ORGANIZATION

        
        










































































 



This remainder of <ref> of the appendix contains the proofs for the main
results concerning
the algorithm (<ref> and <ref>).

	
  * First, in <ref> we give a brief overview of
          the analysis and introduce a
	restricted set of benchmark policies which
	will be used throughout the proofs for
	<ref> and
	<ref>. The benchmark policy
	class is central to the regret decomposition for
	, and facilitates an analysis that does not
	require optimism.
	
  * In <ref>, we prove
	<ref> under 
	(V^π-realizability). This constitutes the main
	technical development for
	<ref>. The central technical
	results proven here are <ref>,
	<ref> and which generalize <ref>.
	
  * In <ref>, we prove
	<ref> under 
	(V^⋆-realizability), as a straightforward
	consequence of the tools developed in
	<ref> (<ref> and
	<ref>).
	
  * Finally, in <ref>, we prove
	<ref> (analysis of for the ExBMDP problem). This analysis has a
	similar structure to the proof of
	<ref> under  in
	<ref>, and builds on the same analysis
	techniques, but requires specialized arguments due
	to extra technical challenges in the ExBMDP setting.
	
  * <ref> gives a self-contained presentation of
the  algorithm for imitation learning, which is used within
 and .









 
	
	

§ OVERVIEW OF ANALYSIS AND PRELIMINARIES

	
	
In this section, we present some notation, technical tools, and
preliminary results we require for the analysis of  in
the settings we described in <ref>. We start by
defining a set of restricted benchmark policies used in the
regret decomposition for .


	

 §.§ Overview of Analysis

	
	In this section we give a brief overview of the
	analysis techniques behind
	<ref> and
	<ref>. We focus on
	<ref> to begin.
	
	
	
	Recall that  is recursive in the sense that whenever the
	test in <ref> fails for a layer h∈ [H], an recursive
	call _h is initiated. Throughout the recursion, via the
	steps in <ref> and <ref>,  maintains
	the following invariant: whenever a call to _h (an
	instance of  initiated at layer h) terminates, the
	confidence sets _h+1:H that it outputs satisfy, with high probability:
	
    ∀ℓ∈[h+1  H],   	V^⋆_ℓ∈_ℓ. Inv1

	
	In addition, _h can only return if the value function
	tests in <ref> (which involve the confidence sets
	_h+1:H) all succeed. From the invariant in (<ref>), it can be shown that the tests only succeed if the estimated value functions _h+1:H satisfy:
	
    ∀ℓ∈ [h+1 H],  ^[sup_a∈| (_ℓ[_ℓ+1]- _ℓ[V^⋆_ℓ+1])(_h,a)| ≥ 3 ]≤_, Inv2

	where _>0 is a parameter set by the algorithm. We
        use pushforward coverability to show that can only
        expand the core-sets _1:H a polynomial number of times
        before the algorithm terminates and (<ref>) is satisfied.
	
	The invariant in (<ref>) is useful because it ensures that
	the greedy policies
	
    _h(x)≈_a∈_h_h+1(x,a)

	induced by the learned value functions _1:H are
	near-optimal. To make this precise, recall that given parameters ,δ∈(0,1), the action _h(x) of 's policy at layer h and state x∈, is given by 
	
    _h(x)∈_a∈_h,,δ [_h+1](x,a),

	where
	_h+1 is the estimated value function at layer
	h+1.
	
		
		
	The operator _h,,δ[_h+1]
	(<ref>), when given input (x,a)∈×,
	
	
	
	
	
	
	
	
	
	
	ensures that probability at least 1-δ, |_h,,δ[_h+1](x,a)-
	_h[_h+1](x,a)|≤. Combining this with the
	invariant in (<ref>) and the fact that _h
	≡_h[_h+1], one can see that with high
	probability (over the randomness in _h∼^ and
	), we have: 
    max_a∈|_h,,δ[_h+1](_h,a) - V^⋆_h(_h,a) | ≤ 4 .



  
Analysis under 
	For <ref> (), <ref> together with the definition of _h in <ref> and the gap assumption (<ref>) implies that if ≤Δ/8, we have that with high probability (over the randomness in _h∼^ and ),
	
    _h(_h)  ∈_a∈_h,,δ[_h+1](_h,a)  =  _a∈V_h^⋆(x,a)= _h(_h).

	This suffices to show that  is near-optimal, since by the performance lemma <cit.>, the suboptimality of  can be bounded as 
	
    J()- J() ≤∑_h=1^H ^[	_h(_h)  ≠_h(_h)].

	This suffices to prove the performance bound in <ref> under .



  
Analysis under         
	For <ref> (), an immediate
        challenge in applying a similar analysis to  is the
        lack of suboptimality gap Δ, which makes it impossible
        to directly bound the probability that ≠ in
        <ref>. To address this, we introduce a
        restricted benchmark policy class Π_⊂ in
        <ref> below. The class
        Π_⊂ is constructed such that that there exists a policy
        π∈Π_ that (i) is ()-suboptimal, and
        (ii) emulates certain properties of a gap. Together, these properties
        facilitate analysis similar to . Overall, this argument is similar to the “virtual policy iteration”
        analysis in <cit.>.



  
Analysis of         
	The analysis of for ExBMDPs
        (<ref>) uses the same idea as the analysis for
        , except that we can only realize V^π for
        endogenous policies that act on (_h). To
        address this, we use the randomized rounding scheme in
        , and the crux of the proof is to show that with high
        probability, the rounded policies in “snap” onto
        endogenous policies, facilitating an argument similar to .
        
	




        


  
Generalizing the analysis	
  We mention in passing that  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 <cit.> and
		Q^π-realizability <cit.>; we leave a more
		general treatment for future work.	





 §.§ Benchmark Policy Class and Randomized Policies





As described above, central to our analysis is a set of
O()-suboptimal policies against which we benchmark the policies
returned , which emulate certain consequences of the
Δ-gap assumption (<ref>). 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 = (_h(x,a))_(h,x,a)∈ [H]××, we say that a policy π is induced by  if π satisfies 

    ∀ h ∈[H],∀ x ∈,   _h(x) ∈_a'∈_h(x,a'),

where we use the bold notation
   π_h(x) as shorthand for the random variable _h∼π_h(x)∈Δ(); in other words, for each x∈, π_h(x)∈Δ() is the distribution induced by sampling _h(x,·) and playing the action _h(x) ∈_a'∈_h(x,a'). If there are ties in (<ref>), we break them by picking the action with the smallest index; we assume without loss of generality that actions in  are index from 1,…,||.



































  
Benchmark policy class
  
  We now define the benchmark policy class as follows.


  For ∈ (0,1), let Π_⊆ be the set of stochastic
  policies such that π∈Π_ if and only if there exists a
  collection of independent random variables
  = (_h(x,a))_(h,x,a)∈ [H]×× in [0,H] such
  that:
  
  
  
  
  
  
  
  
  
  * π is induced by  (i.e. <ref> is
    satisfied); and
  
  * For all (h, x,a)∈ [H]××, we have
    |(_h- Q^π_h)(x,a)| ≤, almost
    surely under the draw of .
  

Intuitively, the set Π_ contains the set of all (stochastic)
policies corresponding to (randomized) state-action value functions
that are point-wise O() close to Q^⋆. We formalize this
claim in the next lemma.

	
	Let ∈ (0,1) be given. Let ∈Π_ be a stochastic policy induced by a collection of (independent) random state-action value functions
        (_h(x,a))_(h,x,a)∈[H]××⊂ [0,H] such that for all h∈[H] and all (x,a)∈×:
	
    |_h(x,a) - Q^_h(x,a)|≤   almost surely, and  π̃_h(x) ∈_a'∈_h(x,a').




        Then, for all h∈H,
	
    ∀ x∈,   _h(x)      ≤  V^_h(x) +   3 H .

      
	  
		Using backward induction over ℓ=H,…,1, we start by showing that all ℓ: 
		  
    ∀ (x,a)∈×,   _ℓ(x,a)     ≤_ℓ(x,a)  + 2 ·  (H-ℓ+1).
	
		  almost surely. We then instantiate this with ℓ=1 and use the fact that _h- Q^_h_∞≤ to get the desired result.
		  
		  

  
Base case [ℓ=H] By definition of the state-action value function, we have, for all π∈, Q^⋆_H ≡ Q^π_H. Thus, since sup_(x,a)∈×|(_H- Q^_H)(x,a)|  ≤ almost surely (by definition of _1:H), we get that 
		  
    ∀ (x,a)∈×,    |_H(x,a) - Q^⋆_H(x,a)| ≤,
 
		  almost surely. This implies (<ref>) for ℓ=H.
		  
		  

  
General case [ℓ <h]	Fix h∈[H-1] and suppose that (<ref>) holds for all ℓ∈ [h+1,…, H] almost surely. We show that it holds for ℓ=h almost surely. Fix (x,a)∈×. We have 
		  
    Q^⋆_h(x,a)- _h(x,a)      =_h [Q^⋆_h+1](x,a)  - _h [_h+1](x,a)+ _h [_h+1](x,a) - _h(x,a),
       ≤2· (H-h)+ _h [_h+1](x,a) - _h(x,a),

		  almost surely, where the last step follows by the induction hypothesis. We now bound _h [_h+1](x,a) - _h(x,a). We have, almost surely, that 
		  
    _h [_h+1](x,a) - _h(x,a)     = 	_h [_h+1](x,a) - _h [V^_h+1](x,a) + _h [V^_h+1](x,a) - _h(x,a), 
        = _h[_h+1](x,a) - _h [V^_h+1](x,a) + Q^_h(x,a) - _h(x,a), 
        = _h[_h+1](x,a) - _h [V^_h+1](x,a) + ,   (by the assumption on _h)
        = [max_a'∈_h+1(_h+1,a')-  Q^_h+1(_h+1,_h+1(_h+1)) |_h =x, _h =a ] + , 
        = [_h+1(_h+1,_h+1(_h+1))-  Q^_h+1(_h+1,_h+1(_h+1)) |_h =x, _h =a] + ,  
       ≤   2,

		  where the penultimate inequality follows by the definition of _h+1, and the last inequality follows by the fact that _h+1- Q^_h+1_∞≤ almost surely, by assumption. Plugging (<ref>) into (<ref>) completes the induction, and so we have that 
		  
    ∀ (x,a)∈×,   	Q^⋆_1(x,a) ≤_1(x,a) ≤ 2 H .

	In particular, taking the max over a on both sides and using the definition of , we get that 
	
    ∀ x∈,   	V^⋆_1(x) ≤_1(x,_1(x)) ≤ 2 H ,
	  
	almost surely. Combining this with the fact that _1(x,_1(x)) ≤ Q^_1(x,_1(x)) +, almost surely (since _1 - Q^_1_∞≤ almost surely by assumption) implies that
		
    V^⋆_1(x)    ≤ Q^π_1(x,_1(x)) + 2 H  + .

		Taking expectation over _1(x) and bounding 2 H  + by 3H leads to the desired result. 
	

	  




 §.§ Additional Preliminaries
      
The following lemma gives a guarantee for the Bellman backup
approximation algorithm  
(<ref>) that is tailored to the analysis of .

	
	Let , δ,δ' ∈(0,1), B>0, and h∈[H], be given and let  be a finite function class. For any sequence (x_i)_i≥ 1⊂ of state action pairs, the outputs (_h, , δ'[f](x_i,a))_i≥ 1, a∈ of <ref> satisfy, with probability at least 1-δ, 
	
    ∀ i≥ 1,  ∀ f ∈, ∀ a∈,    	|_h, , δ'[f](x_i,a)- _h[f](x_i,a)|≤·√(2log_1/δ'(2 A i^2||/δ)).



	By Hoeffding's inequality <cit.> and the
        union bound over a∈ and f∈, we have that for any i≥ 1, with probability at least 1 - δ/(2i^2),
		
    ∀ f ∈, ∀ a∈,    	|_h, , δ'[f](x_i,a)- _h[f](x_i,a)|≤·√(2log_1/δ'(2A i^2||/δ)).

		The desired result follows by the union bound over i≥ 1 and the fact that ∑_i≥ 11/i^2 = π^2/6 ≤ 2.
      

      




 	
	
	

§ GUARANTEE UNDER V^Π-REALIZABILITY (PROOF OF
          THM:VPIFORWARD_MAIN, )

	
	











































































 
In this section, we prove <ref> under . First, in <ref> we state a number of supporting technical lemmas, then use them to prove a more general version of <ref>, <ref>, which holds under a weaker realizability assumption (informally, V^π-realizability only for near-optimal policies π); <ref> follows as an immediate consequence. The remainder of the section (<ref> through to <ref>) contains the proofs for the intermediate results.




 §.§ Analysis: Proof of thm:vpiforward_main ()



We analyze  in the setting of <ref> (), where we have a function class  satisfying V^π-realizability (<ref>). We will actually show that the conclusion of <ref> holds under a weaker function approximation setup we refer to as relaxed V^π-realizability: instead of requiring V^π-realizability for all π∈, we only require it for policies π in the set of near-optimal policies corresponding to the benchmark policy class Π__ for some _>0 (Π_ is defined in <ref>).
[Relaxed V^π-realizability]
	
	For _>0 and all π∈Π__ and h∈ [H], we have V^π_h(x)∈⊆{f: → [0,H]}.
      
      

We will analyze  under <ref> and <ref>. However, it turns out that all of the main results for can be derived under this assumption: As we will see in <ref> in the sequel, when the Δ-gap assumption (<ref>) is satisfied, then Π__ ={} for all _<Δ, allowing us to prove <ref> under  as a special case of relaxed V^π-realizability. Our analysis for the ExBMDP setting in <ref> requires more work, but uses that for ExBMDPs, <ref> is satisfied for a subset of Π__ corresponding to endogenous policies. 

We begin with our analysis under  by bounding the number of times the test in <ref> fails. Since the sizes of the core sets _1:H in  are directly related to the number of test failures, the next result, which bounds |_h| for h∈[H], allows us to show that  terminates in polynomial iterations with high probability. The proof is in <ref>.


	
	Let δ,∈(0,1) be given, and suppose that <ref> (pushforward coverability) holds with parameter >0.
	Further, let f ∈, be given, where  is an arbitrary function class. Then there is an event  of probability at least 1-δ under which any call  _0(f,_1:H,∅,∅,0;,,δ) (<ref>) terminates, and throughout the execution of _0, we have 
	
    ∀ h ∈ [H],    |_h|≤.


In particular, <ref> ensures that with high probability, every call to  (made recursively via the call to _0) terminates in polynomial iterations. When  terminates, all the tests in <ref> must have passed for all ℓ>h. Using this and a standard concentration argument, we get the following guarantee for the estimated value functions and confidence sets returned by each call to . The proof is in <ref>. 

	
	Let h∈ [0  H] and ,δ∈(0,1) be given and consider a call to _0 in the setting of <ref>. Further, let  be the event of <ref>. There exists an event '_h of probability at least 1 -δ/H such that under ∩'_h, if a call to _h within the execution of _0 terminates and returns (_h:H, _h:H, _h:H, _h:H, t_h:H), then for any (x_h-1,a_h-1)∈_h and ℓ∈ [h+1 H+1]: 
	
    ^*sup_f∈ _ℓmax_a∈| _ℓ-1[_ℓ]- _ℓ-1[f_ℓ](_ℓ-1,a) |  > 3|_h-1=x_h-1,_h-1=a_h-1≤,

	where (_τ)_τ≥ h is the stochastic policy induced by _h:H and M and N_ are defined as in <ref>. 
 



We now give a guarantee for the estimated value functions _1:H computed within  in <ref> (the proof is in <ref>).

	
	Let h∈ [0  H] and δ, '∈ (0,1) be given, and consider a call to _0 in the setting of <ref>. Further, let Π'⊆ be a finite policy class such that the class  realizes the value functions V^π for π∈Π' (i.e.  satisfies <ref> with Π__ replaced by Π'). Then, there is an event _h” of probability at least 1 -δ/H under which for all k≥ 1, if 
	
		
  * _h gets called for the kth time during the execution of _0; and
		
  * this kth call terminates and returns (_h:H, _h:H, _h:H, _h:H, t_h:H),
	 
	then if (_τ)_τ≥ h is the policy induced by _h:H and N_ is set as in <ref>, we have that for all π∈Π', 
	
    ∑_(x_h-1,a_h-1)∈_h1/N_∑_(x_h,-)∈_h(x_h-1, a_h-1)( _h(x_h)-V^π_h(x_h))^2
       ≤9k H^2log(8k^2H|Π'|||/δ)/N_  +8 H^2∑_(x_h-1,a_h-1)∈_h∑_τ=h^H ^[_τ(_τ)π_τ(_τ)|_h-1=x_h-1,_h-1=a_h-1],

	where the datasets {_h(x, a): (x,a)∈_h} are as in the definition of _h in (<ref>).




Next, we use this result to show that the confidence sets _1:H returned by _0 are “valid” in the sense that they contain a value function (V^_h) corresponding to a near-optimal stochastic policy  in the benchmark class Π_4. In the sequel, we use this fact to substitute V^_ℓ for f_ℓ in <ref> and bound the suboptimality of the learned policy . 

	
	Let ,δ∈(0,1) be given and suppose that <ref> (pushforward coverability) holds with parameter >0 .
	Let f ∈ be arbitrary, and suppose that  satisfies <ref> with _ = 4. Then, there is an event ”' of probability at least 1-3δ under which a call to _0(f,,∅,∅,0;,,δ) (<ref>) terminates and returns tuple (_1:H, _1:H, _1:H, _1:H, t_1:H) such that 
	
    ∀ h ∈ [H],    V^_h ∈_h,

	where _1:H∈ is the stochastic policy defined recursively via
	
			
    ∀ x ∈,  _τ(x) ∈_a∈{[                            _τ(x,a), if _τ(x,·) -_τ [ V^_τ+1](x,·)_∞≤ 4,;                    _τ[V^_τ+1](x,a),                          otherwise, ].
 
	for τ = H,…,1, and _τ(x,a) _τ,, δ' [_τ+1](x,a) is a realization of the stochastic output of the  operator in <ref> given input (x,a), with δ' is as in <ref>.
	
	
	
    ∀ x ∈,  _τ(x) ∈_a∈{[                            _τ(x,a), if _τ(x,·) -_τ [ V^_τ+1](x,·)_∞≤ 4,;                    _τ[V^_τ+1](x,a),                          otherwise, ].   for τ = H,…,1,
 
	where _τ(x,a) _τ,, δ' [_τ+1](x,a) is a realization of the stochastic output of the  operator in <ref> given input (x,a), and δ' is as in <ref>. Furtherore, we have ∈Π_4.



The proof of the lemma is in <ref>.




Equipped with the preceding lemmas, we now state the main technical result of this section, <ref>, a generalization of <ref> which holds under relaxed V^π-realizability (<ref>). The proof is in <ref>.

	
	Let δ,∈(0,1) be given, and suppose that <ref> (pushforward coverability) holds with parameter >0.
	Let f ∈ be arbitrary, and assume that  that satisfies <ref> with _ = 4. Then, with probability at least 1-5δ, _0(f,,∅,∅,0;,,δ) (<ref>) terminates and returns value functions _1:H that satisfy
	
    ∀ h ∈ [H],   ^*_h(_h)_h(_h)≤/4H^3 ,

	where _h(x) ∈_a∈_h,,δ'[_h+1](x,a) for all h∈H, with ∈Π_4 defined as in <ref> and δ' defined as in <ref>. Furthermore, the number of episodes is bounded by 
    O(^8 H^10A·^-13).



Next, we state a guarantee for the outer-level algorithm, , under relaxed V^π-realizability. Recall that  invokes _0, then extracts an executable policy by applying the  algorithm (see <ref>), with the “expert” policy set to be the output of  . 

	
	Let δ, ∈(0,1) be given, and define _=. Suppose that 
		
  * <ref> (pushforward coverability) holds with parameter >0;
		
  * the function class  satisfies <ref> with _=1 (i.e. all π-realizability); and
		
  * the policy class Π satisfies <ref>.
	
	Then, with probability at least 1-δ, _1:H= (Π, , , δ) (<ref>) satisfies
	
    J()- J(_1:H) ≤.

	Furthermore, the total number sample complexity in the framework is bounded by
	
    O(^8 H^23  A ϵ^-13).

      
      The proof is in <ref>. Note that <ref> is a restatement of <ref> in  (restated for convenience). As a result, <ref> is an immediate corollary.

	The result follows from <ref>, since <ref> is stronger than <ref>.
	












 §.§ Proof of lem:testfailures (Number of Test Failures)



	Fix h∈[H]. We note that the size of _h corresponds to the number of times the test in <ref> fails for ℓ=h throughout the execution of _0(f,,∅,∅;,,δ). 
	
	Let M denote the desired upper bound on |_h|. Suppose that the test in <ref> fails at least twice for ℓ=h (if the test fails at most twice, then |_h|≤ 2 and so (<ref>) holds for ℓ=h trivially), 
	and let 
    (x1_h-1, a1_h-1,1_h, 1_h, t_h1), (x2_h-1, a2_h-1,2_h, 2_h, t_h2), …
 denote the elements of the set _h in the order at which they are added to the latter in <ref> of <ref>. Note that |_h|=|_h|. Note also that t_hi represents the number of times the subroutine _h-1,,δ' has been called in the test of <ref> throughout the execution of _0 and up to the time the test failed for (xi_h-1, ai_h-1). We will use this fact in a concentration argument in the sequel. 
	
	By definition of ( _hi) and <ref> (Freedman's inequality) instantiated with 
	
		
  * = {i_h - f_h  : f∈i_h };
		
  * _h = _h;
		
  * B = H; and 
		
  * n = N_· i;
	 
	and the union bound over i∈ [M ∧ | _h|], we get that there is an event _h of probability at least 1-δ/(2H) under which 
	
	
    ∀ i∈M ∧ |_h|,∀ f∈_hi,      ∑_j<i[]  (i_h(_h)-f_h(_h))^2 |xj_h-1,aj_h-1
       ≤_^2(i)  2_^2 + 4 H^2 log (4 MH||/δ)/N_.



	
    ∀ i∈M ∧ |_h|,∀ f∈_hi,      ∑_j<i[]  (i_h(_h)-f_h(_h))^2 |_h-1= xj_h-1, _h-1=aj_h-1   
       ≤_^2  2_^2 + 4 H^2 log (4 MH||/δ)/N_.


	
	
		
		
	Now, define fi_h ∈_f∈ _hi|[i_h(_h)-f_h(_h) |_h-1= xi_h-1,_h-1=ai_h-1]|. From (<ref>), we have that under _h:  
	
    ∀ i∈M∧ |_h|,   ∑_j<i[](i_h(_h)-fi_h(_h))^2 |_h-1=xj_h-1,_h-1=aj_h-1≤_^2.

	We now use this to bound the number of times the test in <ref> fails for ℓ=h. Suppose for the sake of contradiction that the test fails at least N times for some N≥ M (i.e. |_h|=N≥ M). Conditioned on _h, we have by <ref> and <ref>, 
		
    min_i∈[M]sup_f∈i_h|[i_h(_h)-f_h(_h) |_h-1=xi_h-1,_h-1=ai_h-1]|  
       	= min_i∈[M]|[i_h(_h)-fi_h(_h) |_h-1=xi_h-1,_h-1=ai_h-1]|,  
    
    		
    			   ≤ 2 ( /M^2M _^2 log(2M))^1/2+  2 H/M.
    Now, substituting the expression of _^2 in (<ref>) and using the definition of _^2 in <ref> of <ref>, we get     = 2(/M·(2_^2 + 4 M H^2 log (4MH||/δ)/N_))^1/2  + 2 H/M,  
       ≤  2(/M·(22 M H^2log(8M^2H||^2/δ)/N_  +  68 MH^3log(8M^6 N^2_  H^8/δ)/N_))^1/2  + 2 H/M,  
       ≤,
 
	where the last inequality uses that M = and 
    N_=    and   N_=   ;
 
	see <ref> of <ref>. 
	
	On the other hand, by <ref>, there is an event _h' of probability at least 1-δ/(2MH) under which for all f ∈, all i ∈ [M], and δ' as in <ref>: 
		
		
    *_h-1,,δ'[_hi](x_h-1i, a_h-1i)-	_h-1,,δ'[f_h](x_h-1i, a_h-1i)   ≤*(_h-1[_hi]-_h-1[f_h])(x_h-1i, a_h-1i)
           + ·√(2log_1/δ' (8MH||(ti_h)^2/δ)).

	
	
          
    *_h-1,,δ'[_hi](x_h-1i, a_h-1i)-	_h-1,,δ'[f_h](x_h-1i, a_h-1i)
    
                   ≤*_h-1[_hi-f_h](x_h-1i, a_h-1i) + ·√(2log_1/δ' (4M AH||(ti_h)^2/δ)), 
        =  *_h-1[_hi-f_h](x_h-1i, a_h-1i)  + ·β(t_hi),

	where β(t_hi) is as in <ref>. Thus, under '_h, the test in <ref> fails for ℓ=h at least M times only if 

	
    ∀ i ∈[M],   
    		    <  sup_f∈i_h|(_h-1, ,δ'[i_h]-_h-1, ,δ'[f_h])(x_h-1i, a_h-1i) | 
            - ·β(t_hi), 
       ≤sup_f∈i_h| [i_h(_h)-f_h(_h) |_h-1= xi_h-1,_h-1= ai_h-1]|     (by (<ref>)),
        <  sup_f∈i_h|[i_h(_h)-f_h(_h) |_h-1 =xi_h-1,_h-1=ai_h-1]|.

        Unless N<M, this is a contradiction to <ref>. We conclude that under the event _h∩_h', the test in <ref> fails at most N < M= times for ℓ=h, and so under _1∩_1'∩…∩_H∩_H, we have
	
    ∀ h ∈[H],   	|_h| ≤.

	By the union bound, we have [_1∩_1'∩…∩_H∩_H'] ≥ 1 -δ, which completes the proof.







 §.§ Proof of lem:confidence (Consequence of Passing the Tests)



  Let h∈H be given. Fix ℓ∈ [h+1  H] and let 1_ℓ-1,2_ℓ-1,… denote the sequence of states used in the tests of <ref> throughout the execution of _0; we assume that the sequence is ordered in the sense that if i<j, then i_ℓ-1 is used in the test of <ref> before j_ℓ-1. Let T_ℓ∈ℕ∪{+∞} be the random variable representing the total number of times the operator _ℓ-1,,δ' is invoked in <ref> throughout the execution of _0 (T_ℓ is also the random length of the sequence 1_ℓ-1,2_ℓ-1,…; if _0 terminates, then T_ℓ is finite. The first step of the proof will be to show that under the event  of <ref>, T_ℓ is no larger than M^3 N_ H^3 at any point during the execution of _0. This will help us establish key concentration results, leading to the desired inequality (<ref>).
	
	
	
	
	
	
	
	
	

  
Bounding T_ℓ under 
	First, note that under the event  of <ref>, we have that for any τ∈ [H], 
    |_τ|≤ M,
 and so _τ gets called at most M times throughout the execution of _0. For the rest of this paragraph, we condition on  and fix τ∈[0  H]. Within any given call to _τ (throughout the execution of _0), the operator _ℓ-1,,δ' is invoked at most 
    |_τ|  N_ H_Due to the for-loops in <ref>, <ref>, &<ref>×HM_Number of times _τ returns to <ref> (see below)≤ M^2 N_  H^2

	times. This is because the for-loop in <ref> of _τ resumes whenever a test in <ref> fails for one of the layers τ+1,…,H (see <ref>) once the recursive calls return, and the total number of test failures across all these layers is bounded by H M (by (<ref>)). Now, since _τ gets called at most M times throughout the execution of _0 (as argued in the prequel), the total number of times the operator _ℓ-1,,δ' is invoked in <ref> within _τ is at most 
	
    M^3 N_ H^2.
 
	Finally, the total number of times the operator _ℓ-1,,δ' is called in <ref> throughout the execution of _0 is at most H times larger (accounting for the contributions from _τ for all τ∈ [H]); that is, it is at most
        M^3 N_ H^3. We conclude that the random variable T_ℓ satisfies  
	
    T_ℓ≤ M^3 N_  H^3

        under .
	

  
Specifying '_h In this paragraph, we no longer condition on . We will specify the event '_h in the lemma statement. 	Let δ' be defined as in <ref>. By <ref>, we have that there is an event '_h,ℓ of probability at least 1-δ/(2 H^2) under which:
	
    ∀ i ∈[T_ℓ], ∀ a_ℓ-1∈ :    sup_f∈_ℓ |(_ℓ-1,, δ'[_ℓ]- _ℓ-1,, δ'[f_ℓ])( i_ℓ-1,a_ℓ-1)|  -  -  ·β(T_ℓ)
        = sup_f∈_ℓ |(_ℓ-1,, δ'[_ℓ]- _ℓ-1,, δ'[f_ℓ])( i_ℓ-1,a_ℓ-1)|  -  -  ·√(2log_1/δ'(8AH^2M||T_ℓ^2/δ)),
       ≥sup_f∈_ℓ |(_ℓ-1[_ℓ]- _ℓ-1[f_ℓ])( i_ℓ-1,a_ℓ-1)|  -  - ·√(2log_1/δ'(8AH^2M||T_ℓ^2/δ))
            - ·√(2log_1/δ'(4 A H^2M|| i^2/δ)),   (<ref>)
       ≥sup_f∈_ℓ |(_ℓ-1[_ℓ]- _ℓ-1[f_ℓ])( i_ℓ-1,	a_ℓ-1)|  -  - 2·√(2log_1/δ'(8 AH^2M||T_ℓ^2/δ)).

	
	
	On the other hand, for k∈ [T_ℓ-N_ +1], we have by <ref> (Freedman's inequality) instantiated with 
	
		
  * n = N_ and _i = 𝕀{sup_f∈ _ℓmax_a∈| (_ℓ-1[_ℓ]- _ℓ-1)[f_ℓ](k+i_ℓ-1,a) |> 3 }, for all i∈[N_];
		
  * = {id};
		
  * B=1; and
		
  * λ=1;
                
	that there is an event ”_h,ℓ,k of probability at least 1-δ/(4 k^2H^2) under which 
	
    ∑_0≤ i<N_*sup_f∈ _ℓmax_a∈| (_ℓ-1[_ℓ]- _ℓ-1[f_ℓ])(k+i_ℓ-1,a) |  > 3
       ≤  4 log(8H^2T^2_ℓ/δ) + ∑_0≤ i<N_𝕀{sup_f∈_ℓ,a ∈ |(_ℓ-1[_ℓ]-_ℓ-1[ f_ℓ])(k +i_ℓ-1,a)| >3}.

	Now, let ”_h,ℓ⋂_k∈  [T_ℓ - N_ +1]”_h,ℓ,k. By the union bound and the fact that ∑_k≥ 11/k^2 = π^2/6 ≤ 2, we have that [”_h,ℓ] ≥ 1 - δ/(2 H^2). Furthermore, under ”_h,ℓ, we have 
	
    ∀ k ∈ [T_ℓ- N_ +1],  
       ∑_0≤ i<N_*sup_f∈ _ℓmax_a∈| (_ℓ-1[_ℓ]- _ℓ-1[f_ℓ])(k+i_ℓ-1,a) |  > 3
       ≤  4 log(8H^2T^2_ℓ/δ) + ∑_0≤ i<N_𝕀{sup_f∈_ℓ,a ∈ |(_ℓ-1[_ℓ]-_ℓ-1[ f_ℓ])(k +i_ℓ-1,a)| >3}.

	We define '_h '_h,1∩_h,1”∩…∩_h,H'∩_h,H”. Note that by the union bound, we have ['_h] ≥ 1 - δ/H as desired.
        
	

  
Termination of _h under ∩'_h We now show that under ∩'_h, if _h terminates, its output satisfies (<ref>). For the rest of the proof, we condition on ∩'_h. Suppose that _h terminates and returns (_h:H, _h:H, _h:H, _h:H, t_h:H). In this case, the value function _ℓ must have passed the tests in <ref> for all (x_h-1,a_h-1)∈_h, n∈ N_, and a_ℓ-1∈. Fix (x_h-1, a_h-1)∈_h and let k ∈ [T_ℓ - N_· A+1] be such that (^k + j_ℓ-1)_j ∈ [0  N_ -1] represents a subsequence of states that pass the tests in <ref> at layer ℓ for (x_h-1, a_h-1) within the call to _h. The fact that the sequence (i_ℓ-1)_i≥ 1 is ordered (see definition in the first paragraph of this proof) and that (^k + j_ℓ-1)_j ∈ [0  N_ -1] pass the tests imply that
	
		
  * The states (k+i_ℓ-1)_i∈[0 N_-1] at layer ℓ-1 are i.i.d., and are obtained by rolling out with _h:H starting from (x_h-1,a_h-1); and 
		
  *  The test in <ref> succeeds for all (k+j_ℓ-1)_j∈ [0  N_ -1]; that is 
		
    ∀ j ∈ [0  N_-1], ∀ a_ℓ-1∈,     sup_f∈_ℓ  |(_ℓ-1,, δ'[_ℓ]- _ℓ-1,, δ'[f_ℓ])( k+j_ℓ-1,a_ℓ-1)| 
       ≤  + ·β(k+j), 
       ≤  + ·√(2log_1/δ'(8AM||(k+j)^2/δ)), 
       ≤  + ·√(2log_1/δ'(8AM||T_ℓ^2/δ)).

	
	This implies that
	
	
    ∀ i ∈ [0 N_-1], 	∀ a_ℓ-1∈
         sup_f∈_ℓ |(_ℓ-1[_ℓ]- [f_ℓ])( k+ i_ℓ-1,a_ℓ-1)| - 3 
         ≤sup_f∈_ℓ |(_ℓ-1[_ℓ]- _ℓ-1[f_ℓ])( k+i_ℓ-1,a_ℓ-1)|  -  - 2·√(2log_1/δ'(8MH^2||T_ℓ^2δ)),   
         ≤sup_f∈_ℓ |(_ℓ-1,, δ'[_ℓ]- _ℓ-1,, δ'[f_ℓ])( k+i_ℓ-1,a_ℓ-1)|  -  -  ·√(2log_1/δ'(8MH^2||T_ℓ^2/δ)),   (by (<ref>))
         ≤  0.  (by <ref>)


	
	
    ∀ i ∈ [0 N_-1], 	∀ a_ℓ-1∈ :  
       sup_f∈_ℓ |_ℓ-1[_ℓ- f_ℓ]( k+ i_ℓ-1,a_ℓ-1)| - 3 
       ≤sup_f∈_ℓ |_ℓ-1[_ℓ- f_ℓ]( k+i_ℓ-1,a_ℓ-1)|  -  - 2·√(2log_1/δ'(4AMH^2||T_ℓ^2δ)),   
       (<ref>)≤sup_f∈_ℓ |(_ℓ-1,, δ'[_ℓ]- _ℓ-1,, δ'[f_ℓ])( k+i_ℓ-1,a_ℓ-1)|
    -  -  ·√(2log_1/δ'(4AMH^2||T_ℓ^2/δ)),  
       ≤  0.  (by <ref>)


	where (<ref>) follows by (<ref>) and the choice of δ' in <ref>.

        Now, by <ref>, we have that _ℓ-1k+i has probability law ^_h:H[·|_h-1=x_h-1,_h-1=a_h-1] for all i ∈ [0  N_ -1], and so by (<ref>), we have: 
	
    ^*sup_f∈ _ℓmax_a∈| (_ℓ-1[_ℓ]- _ℓ-1[f_ℓ])(_ℓ-1,a) |  > 3|_h-1=x_h-1,_h-1=a_h-1
       ≤4 log(8H^2T^2_ℓ/δ)/N_ + 1/N_∑_0≤ i<N_𝕀{sup_f∈_ℓ,a ∈ |_ℓ-1[_ℓ]- _ℓ-1[f_ℓ])(k+ i _ℓ-1,a)| >3}, 
       ≤4 log(8M^6 N^2_  H^8/δ)/N_   (using (<ref>) and the fact that all the tests pass, i.e. (<ref>)).

	
	
	

  
Concluding We have established that under ∩'_h, we have for all ℓ∈[h+1 H] and all (x_h-1,a_h-1)∈_h:
	
    ^*sup_f∈ _ℓmax_a∈|( _ℓ-1[_ℓ]- _ℓ-1[f_ℓ])(_ℓ-1,a) |  > 3|_h-1=x_h-1,_h-1=a_h-1≤,

	Furthermore, we have ['_h] ≥ 1 - δ/H. This completes the proof.





 §.§ Proof of lem:confidencesets1 (Value Function Regression Guarantee)



	Fix π∈Π'⊆ and k≥ 1, and consider the kth call to _h as per the lemma statement, and let _k be the state of _0 during the k^th call to _h and immediately before <ref>, i.e. immediately before gathering data for the regression step in _h.

	

  
Relating the regression targets to V^_h Observe that _h is the least-squares solution of the objective in <ref>, where the targets are empirical estimates of V^_h. In particular, if we let {_h(x, a): (x,a)∈_h} be the datasets in the definition of _h in (<ref>), then for any (x_h-1,a_h-1)∈_h and (x_h,v_h)∈_h(x_h-1,a_h-1), the target v_h satisfies 
	
    v_h =  _h(x_h),

	where _h(x_h) is an empirical estimate of V^_h(x_h) obtained by sampling (|_h|)=(k) episodes (for (·) defined as in <ref>) by rolling out with  after starting from x_h and playing action a at layer h; note that |_h|= k because we are considering the kth call to _h. Thus, by Hoeffding's inequality and the union bound over (x_h-1,a_h-1)∈_h and (x_h,-)∈_h(x_h-1,a_h-1), there is an event ”_h,k(_k) of probability at least 1-δ/(8 k^2 H) under which 
	
    ∀ (x_h-1,a_h-1)∈_h,	∀ (x_h,-) ∈_h(x_h-1,a_h-1): 
       |V^_h(x_h) - _h(x_h)| ≤ H√(2 log (8 |_h| N_ H k^2 /δ)/(k))≤ H√(2 log (8  N_ H k^3 /δ)/(k)),

	where N_ is as in <ref>, and the last inequality follows by |_h|≤ k since we are considering the kth call to _h. Thus, under ”_h,k, we have 
	
    ∀ (x_h-1,a_h-1)∈_h,	∀ (x_h,v_h) ∈_h(x_h-1,a_h-1): 
        |V^_h(x_h) - v_h|
               = |V^_h(x_h) -_h(x_h)|  ≤ H√(2 log (8  N_ H k^3 /δ)/(k))
                                                                                                      ≤H/N_ ,

	where the second-to-last inequality is by (<ref>) and the last inequality follows by the choice of  in <ref>. 
        	

  
Bounding the discrepancy V^_h - V_h^π
	On the other hand, by the performance difference lemma, the value function V^_h satisfies:
	
    ∀ x ∈,    	|V^_h(x) - V^π_h(x)|    ≤∑_τ=h^H ^[*Q^π_τ(_τ, π_τ(_τ)) -  Q_τ^π(_τ, _τ(_τ))|_h = x],  
       ≤ H ∑_τ=h^H ^[ _τ(_τ)π_τ(_τ)|_h = x].
 
	Now, let (x_h-11,a_h-11), (x_h-12,a_h-12), … denote the elements of _h in the order in which they are added to the latter in <ref>. By <ref> (Freedman's inequality) instantiated with
	
		
  * n = N_· k.
		
  * _i = |V_h^π(i_h)- V^_h(i_h)|- [|V_h^π(_h)- V^_h(_h)||_h-1=x_h-1j,_h-1= a_h-1j], for all i∈[n] and j = i/N_+1, where _hN_·  j,…, _hN_· j + N_ -1i.i.d.∼T_h(·|_h-1=x_h-1j,_h-1= a_h-1j);
		
  * _i = σ(_h1, …_hi-1), for all i∈[n];
		
  * R = H; and 
		
  * λ = 1/H;
	 we get that there is an event ”_h,k,π(_k) of probability at least 1-δ/(8 k^2 H|Π'|) under which:
	
    ∑_(x_h-1,a_h-1)∈_h∑_(x_h,-)∈_h(x_h-1,a_h-1) |V_h^π(x_h)- V^_h(x_h)|  
        = 2	N_∑_(x_h-1,a_h-1)∈_h[|V_h^π(_h)- V^_h(_h)||_h-1=x_h-1, _h-1=a_h-1] + H log(8 k^2 |Π'|H/δ),
       ≤ 2H	N_∑_(x_h-1,a_h-1)∈_h∑_τ=h^H ^[ _τ(_τ)π_τ(_τ)|_h-1=x_h-1, _h-1=a_h-1] + H log(8 k^2|Π'| H/δ),

	where the last inequality follows by (<ref>) and the law of total expectation. 
	

  
Regression guarantee
	Since π∈Π' ⊆ and <ref> holds, <ref> (regression guarantee) instantiated with
	
		
  * f_⋆(x) = V^π_h(x);
		
  * B = H;
		
  * b_i=v_h-V^π_h(_h) (where v_h max_a∈_h(_h,a)); and
		
  * ξ = H;
	
	implies that there is an event ”_h,k,π(_k) of probability at least 1-δ/(4k^2 H|Π'|) under which we have:
	
    ∑_(x_h-1,a_h-1)∈_h1/N_∑_(x_h,-)∈_h(x_h-1, a_h-1)( _h(x_h)-V^π_h(x_h))^2
    
    		   ≤4 k H^2log(4k^2H|Π'|||/δ)/N_  +4 H/N_∑_(x_h-1,a_h-1)∈_h∑_(x_h, v_h)∈_h(x_h-1,a_h-1) |V_h^π(x_h)- v_h|, 
       ≤4 k H^2log(4k^2H|Π'|||/δ)/N_ +4 H/N_∑_(x_h-1,a_h-1)∈_h∑_(x_h, v_h)∈_h(x_h-1,a_h-1) |V_h^(x_h)- v_h| 
          +4 H/N_∑_(x_h-1,a_h-1)∈_h∑_(x_h, v_h)∈_h(x_h-1,a_h-1)  |V_h^π(x_h)- V^_h(x_h)|,

	where the last step follows by the triangle inequality. Thus, by plugging (<ref>) and (<ref>) into (<ref>), we get that under ”_h,k(_k) ∩”_h,k,π(_k)∩”_h,k,π(_k):
	
    ∑_(x_h-1,a_h-1)∈_h1/N_∑_(x_h,-)∈_h(x_h-1, a_h-1)( _h(x_h)-V^π_h(x_h))^2
    
    		   ≤9  k H^2log(8k^2H|Π'|||/δ)/N_  +8 H^2∑_(x_h-1,a_h-1)∈_h∑_τ=h^H ^[_τ(_τ)π_τ(_τ)|_h-1=x_h-1,_h-1=a_h-1].


	

  
Applying the union bound to conclude
	Let _k be the random state of _0 during the k^th call to _h and immediately before <ref>, i.e. immediately before gathering data for the regression step in _h. Further, let _k^+ be the random state of _0 during the k^th call to _h and immediately before <ref>, i.e. immediately before the regression step in _h. If _0 terminates before the k^th call to _h, we use the convention that _k= _k^+= 𝔱, where 𝔱 denotes a terminal state, and define _h,k”()=”_h,k,π()= ”_h,k, π() = {}. Further, we define 

    ”_h {∏_k∈ℕ, π∈Π'𝕀{^+_k∈”_h,k(_k) ∩”_h,k,π(_k)∩”_h,k, π(_k)} =1 }.
 
Note that by the argument in the sequel and the union bound, we have that

    ∀ k ≥ 1, ∀_k,  [^+_k∈”_h,k(_k) ∩”_h,k,π(_k)∩”_h,k, π(_k) ] ≥ 1 - δ/2k^2H,

where _k denotes the state of _0 during the k^th call to _h and immediately before <ref>. By letting _1',_2',… denote an identical, independent copy of the sequence _1,_2,…, we have by the chain rule: 

    [”_h]     = _'_1,_2',…[ ∏_k≥ 1[^+_k∈”_h,k(_k) ∩”_h,k,π(_k)∩”_h,k, π(_k) |_k=_k']], 
       ≥∏_k≥ 1(1-δ/2k^2H),   (by (<ref>))
       ≥ 1- δ/H,

where the last inequality follows from the fact that for any sequence x_1,x_2,…∈(0,1), we have ∏_k≥ 1(1-x_k) ≥ 1 - ∑_k≥ 1x_k. Combining (<ref>) with (<ref>) implies that ”_h gives the desired result. 




 §.§ Proof of lem:confidencesets (Guarantee for Confidence Sets)



To prove <ref>, we need one additional result pertaining to the order in which the instances (_h)_h∈[H] are called.



	
	Let h∈ [0 H] be given, and consider the setting of <ref>. Further, consider a call to _0(f,,∅,∅;,,δ) that terminates, and let h∈ [H] be any layer such that _h is called during the execution of _0. Then, after the last call to _h terminates, no instance of  in (_τ)_τ >h is called before _0 terminates.
 

	Suppose there is an instance of   in (_τ)_τ >h that is called after the last call to _h terminates. Let τ>h be the lowest layer where _τ is called after the last call to _h terminates. Let _τ^ denote the corresponding instance of _τ. Further, let ℓ <τ be such that _ℓ is the parent instance of _τ^ (i.e. the instance that called _τ^). Note that we cannot have ℓ=h as this would imply that an instance of _h terminates after _τ^, and we have assumed that _τ^ terminates after the last call _h. It is also not possible to have ℓ>h as this would imply that τ is not the lowest layer where _τ is called after the last call to _h terminates. Thus, we must have that ℓ< h. Now, the for-loop in <ref> ensures that that there is an instance of _h that is called after _τ^ terminates and before _ℓ does. This contradicts the assumption that _τ^ is called after the last call to _h.



We start by showing that ∈Π_4 by constructing the corresponding collection of random state-action value functions (_h(x,a))_(h,x,a)∈[H]××⊂ [0,H] in the definition of Π_4. In particular, for (h,x,a)∈[H]××, we define
	
    _h(x,a) = {[                          _h(x,a), if _h(x,·)- _h[V^_h+1](x,·)_∞≤ 4,;                  _h[V^_h+1](x,a),                        otherwise, ].    for h = H,…,1.

	where _τ(x,a)_τ,, δ' [_τ+1](x,a). Note that _h(x,a) only depends on the randomness of _h,, δ' [_h+1](x,a), and so (_h(x,a))_(h,x,a)∈ [H]×× are independent random variables. Furthermore, since _h[V^_h+1]≡ Q^_h, we have that  
	
    ∀ (x,a)∈×	,  _h(x,a)- Q^_h(x,a)≤ 4.

	Finally, since _h(·) ∈_a∈_h(·,a), we have that ∈Π_4.


	

  
We show V^_h ∈_h We prove that V^_h ∈_h, for all h∈[H], under the event ”'∩'_1∩_1”∩…∩_H' ∩_H”, where , (_h'), and (_h”) are the events defined in <ref>, <ref>, and <ref>, respectively. Throughout, we condition on ”'. First, note that by <ref>, _0 terminates. Let (_1:H, _1:H,
	_1:H,_1:H, t_1:H) be the tuple it returns.
	
	We will show via backwards induction over ℓ=H+1,…, 1, that
	
    V^_ℓ∈_ℓ,
 
	where _1:H is the stochastic policy defined recursively via
		
		
    _τ(x) ∈_a∈{[        _τ(x,a) _τ,, δ' [_τ+1](x,a), if _τ(x,·) -_τ [ V^_τ+1](x,·)_∞≤ 4,;                    _τ[V^_τ+1](x,a),                          otherwise, ].

		for τ = H,…,1,	where _τ(x,a) _τ,, δ' [_τ+1](x,a).
	
	
	
    _τ(x) ∈_a∈{[        _τ(x,a) _τ,, δ' [_τ+1](x,a), if _τ(x,·) -_τ [ V^_τ+1](x,·)_∞≤ 4,;                    _τ[V^_τ+1](x,a),                          otherwise, ].   for τ = H,…,1,
 	
		where _τ(x,a) _τ,, δ' [_τ+1](x,a).


	
	

  
Base case [ℓ=H+1] This holds trivially because V^π_H+1≡ 0 for any π∈ by convention. 
	
	

  
General case [ℓ≤ H] Fix h∈[H] and suppose that (<ref>) holds for all ℓ∈[h+1 H+1]. We show as a consequence that (<ref>) holds for ℓ=h. First, note that if _h is never called during the execution of _0, then _h =, and so (<ref>) trivially holds for ℓ=h under <ref> with _ = 4. 
	
	Now, suppose that _h is called at least once, and let (^+_h:H,^+_h:H,
	^+_h:H,^+_h:H,t^+_h:H) be the output of the last call to _h during the execution of _0. We claim that 
    (^+_h:H,^+_h:H,
    		^+_h:H) = (_h:H,_h:H,
    		_h:H).

	To see this, first note that the for-loop in <ref> ensures that no instance of (_τ)_τ>h can be called after the last call to _h (by <ref>). Thus, the estimated value functions, confidence sets, and core sets for layers h+1, …, H remain unchanged after the last call to _h; that is, (<ref>) holds. Thus, by <ref>, and since we are conditioning on _h+1:H', we have that for all (x_h-1,a_h-1) ∈_h and ℓ∈ [h+1  H+1]:
	
    ^*sup_f∈ _ℓmax_a∈| (_ℓ-1[_ℓ]- _ℓ-1[f_ℓ])(_ℓ-1,a) |  > 3|_h-1=x_h-1,_h-1=a_h-1≤,

	where M =. Now, by the induction hypothesis, we have V^_ℓ∈_ℓ, and so substituting V^_ℓ for f_ℓ in (<ref>), we get that for all (x_h-1,a_h-1) ∈_h and ℓ∈ [h+1  H+1]:
	
    ^*max_a∈|( _ℓ-1[_ℓ]- _ℓ-1[V^_ℓ])(_ℓ-1,a) |  > 3|_h-1= x_h-1,_h-1=a_h-1≤.

	Therefore, by <ref> (instantiated with μ[·] = ^[·|_h-1=x_h-1,_h-1=a_h-1], τ = ℓ-1, and V_τ+1 = V^_ℓ), we have that (x_h-1,a_h-1) ∈_h and ℓ∈ [h+1  H+1]: 
	
    ^*_ℓ-1(_ℓ-1)_ℓ-1(_ℓ-1)|_h-1=x_h-1,_h-1=a_h-1≤ + δ',

	where δ' is as in <ref>. 
	

  
Applying the regression guarantee to conclude the induction Note that ∈Π', where Π'⊂ is the set of stochastic policies such that π∈Π' if and only if there exists V_1:H∈ such that π is defined recursively as 
	
    π_τ(x) ∈_a∈{[        Q_τ(x,a) _τ,, δ' [V_τ+1](x,a), if Q_τ(x,·) -_τ [ V^π_τ+1](x,·)_∞≤ 4,;                     _τ[V^π_τ+1](x,a),                            otherwise, ].

	for τ = H,…,1,	where Q_τ(x,a) _τ,, δ' [V_τ+1](x,a). The policy class Π' is finite and |Π'|≤ ||. Furthermore, we have Π' ⊆Π_4 as shown at the beginning of this proof. Therefore, if we let {_h(x, a): (x,a)∈_h} be the datasets in the definition of _h in (<ref>), we have by <ref> (under <ref> with _ = 4) and the conditioning on _h+1:H” and :
	
    ∑_(x_h-1,a_h-1)∈_h1/N_∑_(x_h,-)∈_h(x_h-1, a_h-1)( _h(x_h)-V^_h(x_h))^2
       ≤9|_h| H^2log(8|_h|^2H||^2/δ)/N_  +8 H^2∑_(x_h-1,a_h-1)∈_h∑_τ=h^H ^[_τ(_τ)_τ(_τ)|_h-1=x_h-1,_h-1 a_h-1], 
       ≤9 M H^2log(8M^2H||^2/δ)/N_  +8 H^2  ∑_(x_h-1,a_h-1)∈_h∑_τ=h^H ^[_τ(_τ)_τ(_τ)|_h-1= x_h-1, _h-1=a_h-1],

	where the last inequality follows by the fact that |_h| ≤ M under . Combining (<ref>) with (<ref>), implies that  
	
    ∑_(x_h-1,a_h-1)∈_h1/N_∑_(x_h,-)∈_h(x_h-1, a_h-1)( _h(x_h)-V^_h(x_h))^2
       ≤9 M H^2log(8M^2H||^2/δ)/N_  + 8 M H^3·  + 8M H^3δ', 
        = 9 M H^2log(8M^2H||^2/δ)/N_  + 8 M H^3·  + 8M H^3δ/4M^7N_^2 H^8||,
       ≤_^2,

  where the last inequality follows by the fact that δ∈(0,1) and the definition of _^2 in <ref>.
	By the definition of _h in (<ref>), (<ref>) implies that V^_h ∈_h, which completes the induction.







 §.§ Proof of thm:lbc3 (Main Guarantee of )


 We condition on the event ∩”'∩'_1∩…∩_H', where , ”', and (_h') are the events in <ref>, <ref>, and <ref>, respectively. Note that by the union bound, we have [] ≥  1 - 5 δ. By <ref>, we have that 
	
    ∀ h ∈[H],  ^*sup_f∈ _hmax_a∈|(_h-1[_h]-_h-1[f_h])(_h-1,a) |>3≤,

	where M = and N_ =. On the other hand, by <ref>, we have 
	
    ∀ h ∈[H],    	V^_h∈_h.

	Thus, substituting V^_h for f_h in (<ref>) we get that for all h∈[H+1]. 
	
    ^*max_a∈|(_h-1[_h]- _h-1[V^_h])(_h-1,a)|   > 3≤.

	This together with <ref>, instantiated with μ[·] = ^[·]; τ = h-1; V_τ+1 = V^_h; and δ = δ' (with δ' as in <ref>), translates to:
	
    ∀ h∈[H],   ^*_h(_h)_h(_h)   ≤ + δ',  
       =  + δ/4 M^7 N_^2 H^8 ||, 
       ≤/4H^3 ,

	where the last step follows from the fact that N_ = (with M as in <ref>). 
	
	
	

  
Bounding the sample complexity
	We now bound the number of episodes used by <ref> under the event . First, we fix h∈[H], and focus on the number of episodes used within a to call _h, excluding any episodes used by any subsequent calls to _τ for τ >h. We start by counting the number of episodes used to test the fit of the estimated value functions _h+1:H. Starting from <ref>, there are for-loops over (x_h-1,a_h-1)∈_h, ℓ=H, …, h+1, and n ∈ [N_] to collect partial episodes using the learned policy  in <ref>, where N_ = and M =. Note that executing  requires the local simulator and uses N_= 2 log(4 M^7 N_^2 H^2 ||/δ)/^2 local simulator queries to output an action at each layer (since <ref> calls <ref> with confidence level δ'=). Also, note that whenever a test fails in <ref> and the recursive  calls return, the for-loop in <ref> resumes. We also know (by <ref>) that the number of times the test fails in <ref> is at most M. Thus, the number of times the for-loop in <ref> resumes is bounded by H M; here, H accounts for possible test failures across all layers τ∈[h+1 H]. Thus, the total sample complexity required to generate episodes between lines <ref> and <ref> is bounded by 
	
    # episodes for roll-outs≤MH_# of times <ref> resumes·MH^2 N_ N__Sample complexity  in case of no test failures.

	Note that the test in <ref> also uses episodes because it calls the operator  for every a∈. Thus, the number of episodes used for the test in <ref> is bounded by 
	
    # episodes for the tests≤MH_# of times <ref> resumes·M H A N_ N__Sample complexity for  <ref>.

	We now count the number of episodes used to re-fit the value function in <ref> and onwards. Note that starting from <ref>, there are for-loops over (x_h-1,a_h-1)∈_h and i∈ [N_] to generate A ·(|_h|)≤ A ·(M) partial episodes using , where (k)=2N_^2 log(8 A N_ H k^3/δ) is defined as in <ref>. Since  uses the local simulator and requires  samples (see <ref>) to output an action at each layer, the number of episodes used to refit the value function is bounded by 
	
    # episodes for V-refitting≤ M N_ A (M) H N_.

	Therefore, by (<ref>), (<ref>), and (<ref>), the number of episodes used within a single call to _h (not accounting for episodes used by recursive calls to _τ, for τ >h) is bounded by
	
    # episodes used locally within _h   ≤  M^2 H (H + A) N_ N_  +M N_ A (M) H N_.

	Finally, by <ref>, _h may be called at most M times throughout the execution of _0. Using this together with (<ref>) and accounting for the number of episodes from all layers h∈[H], we get that the total number of episodes is bounded by 
	
    M^3 H^2 (H + A) N_ N_   +M^2 H^2 N_ A (M) N_.
  
	Substituting the expressions of M, N_, , N_, and N_ from <ref> and <ref>, we obtain the desired number of episodes, which concludes the proof.








 §.§ Proof of thm:vpiforward (Guarantee of )




Let _1:H be the value function estimates produced by _0 within <ref>, and let ^_h(·) ∈_a∈_h,_,δ'[_h+1](·,a), for all h∈ [H] with _H+1≡ 0 with _ and δ' as in <ref>. Further, let and let _1:H∈ be the stochastic policy defined recursively via

    ∀ x ∈,  _τ(x) ∈_a∈{[                             _τ(x,a), if _τ(x,·) -_τ [ V^_τ+1](x,·)_∞≤ 4_,;                     _τ[V^_τ+1](x,a),                           otherwise, ].
 
for τ = H,…,1, where _τ(x,a) _τ,_, δ' [_τ+1](x,a). By <ref>, there is an event  of probability at least 1-δ/2 under which:

    ∈Π_4_, and∀ h ∈[H],   ^^*^_h(_h)_h(_h)≤_/4 H^3 ≤/4H^2,

where the last inequality follows by the choice of _ in <ref>.

For the rest of the proof, we condition on . By (<ref>), (<ref>), and <ref> instantiated with _=0 (due to all π-realizability), we have that there is an event ' of probability at least 1-δ/2 under which the policy _1:H produced by  ensures that
	
    J(^_1:H) -  J(_1:H) ≤/2.
	
	Now, by <ref> (the performance difference lemma), we have for  as in (<ref>):
	
    J()- J(^_1:H)     = ∑_h=1^H ^^[Q^_h(_h, _h(_h)) -  Q_h^(_h, ^_h(_h))],
       ≤ H∑_h=1^H ^^[ ^_h(_h)_h(_h)],

	and so by (<ref>), we have
	
    J()- J(^_1:H)     ≤/4.

	Finally, since ∈Π_4_ (see (<ref>)), we have by <ref>,  
	
    J() -J() 
    		   ≤ 12 H _≤/4,

	where the last inequality follows by the choice _ in <ref>. Combining this with (<ref>) and (<ref>), we conclude that under ∩':
	
    J()  - J(_1:H) ≤.

	By the union bound, we have [∩']≥ 1 - δ, and so the desired suboptimality guarantee in (<ref>) holds with probability at least 1-δ. 
	
	

  
Bounding the sample complexity The sample complexity is dominated by the call to _0 within  (<ref>). Since  calls _0 with = _ =  H^-1/48, we conclude from <ref> that the total sample complexity is bounded by 
	
    O(^8 H^23A ·^-13).







 	
	
        
        	

§ GUARANTEE UNDER V^⋆-REALIZABILITY
          (PROOF OF THM:VPIFORWARD_MAIN, )

	
	










































































 
In this section, we prove thm:vpiforward_main under
 (/-realizability (<ref>)
and Δ-gap (<ref>)). We prove this result as a
consequence of the more general results (<ref>) in
<ref> by appealing to the relaxed V^π-realizability
condition in <ref>.

	



 §.§ Analysis: Proof of thm:vpiforward_main ()

We begin by showing that <ref> and <ref>
together imply that <ref> holds for any _≤Δ/2; we prove this by showing that the benchmark policy class Π_' (<ref>) reduces to {π^⋆} when '  ≤Δ/2.

	
	Assume that  satisfies <ref> (V^⋆-realizability), and that <ref> (gap) holds with Δ>0. Then, for all '≤Δ/2, we have Π_' ={π^⋆} and  satisfies <ref> with _ = '.

Informally <ref>, whose proof is in <ref>,
states that under <ref>, <ref> with Δ>0, and
<ref> (pushforward coverability) with >0, we
are essentially in the setting of <ref> (guarantee of
 under relaxed V^π-realizability), as long as we
choose _≤Δ/2.  With this, we now state and prove a central guarantee for  under V^⋆-realizability with a gap.

	
	Let δ∈(0,1) be given, and suppose that:
	 
		
  * <ref> (pushforward
                  coverability) holds with parameter >0;
		
  * <ref> (gap) holds with parameter Δ>0;
		
  * The function class  satisfies <ref> (V^⋆-realizability).
	
	Then, for any f ∈ and ∈(0,Δ/8), with
        probability at least 1-δ,
        _0(f,,∅,∅;,,δ)
        (<ref>) terminates and returns value
        functions _1:H that satisfy 
	
    ∀ h ∈ [H],  ^*_h(_h)≠_h(_h) ≤/4 H^3  ,

	where _h(x) ∈_a∈_τ,,δ'[_h+1](x,a), for all
        h∈H, with δ' is defined as in <ref>.


  From <ref>, we have that Π_4=*,
  and so <ref> implies that with probability at least 1-δ,
	
    ∀ h ∈[H],   /4 H^3≥^*_h(_h)_h(_h = 	^*_h(_h)≠_h(_h) ,

	where the equality follows by the fact that  is deterministic.


From here, <ref> follows swiftly as a consequence.


	Let _1:H be the value function estimates produced by _0 within <ref>, and let ^_h(·) ∈_a∈_h,_,δ'[_h+1](·,a), for all h∈ [H] with _H+1≡ 0 with _ and δ' as in <ref>. By <ref>, there is an event  of probability at least 1-δ/2 under which:
	
    ^*_h(_h)≠_h(_h) ≤_/4 H^3 ≤/4H^2,

	where the last inequality follows by the choice of _ in <ref>.
	
	For the rest of the proof, we condition on . By (<ref>) and <ref> (-realizability), the
	policy ^_1:H returned by _0 satisfies
	the condition in <ref> with
	_ = /(4  H^3). Thus, by
	<ref>, there is an event ' of probability at
	least 1-δ/2 under which the policies _1:H produced by
	 satisfy
	
    J(^_1:H) -  J(_1:H) ≤/H +/2≤3/2.

	We now condition on ∩'. By <ref> (performance difference lemma), we have

    J()- J(^_1:H)     = ∑_h=1^H ^^[Q^_h(_h, _h(_h)) -  Q_h^(_h, ^_h(_h))],
       ≤ H∑_h=1^H ^*_h(_h)≠_h(_h) , 
       ≤/(4H),

where the last inequality follows by (<ref>).

Finally, by the union bound, we have [∩']≥ 1 - δ, and so the desired suboptimality guarantee in (<ref>) holds with probability at least 1-δ. 





  
Bounding the sample complexity The sample complexity
is dominated by the call to _0 within 
(<ref>). Since  calls _0 with
= _ =  H^-1/48, we conclude from <ref> that the total number of episodes is bounded by 

    O(^8 H^23A ·^-13).







 §.§ Proof of lem:reduce (Relaxed
  V^π-Realizability under Gap)






	Fix ' ∈ (0,1) and π∈Π_'. Let (_h(x,a))_(h,x,a) ∈ [H]×× be independent random variables such that 
	
    ∀ h ∈ [H],    π_h(·) ∈_a'∈_h(·,a')   and  _h - Q^π_h_∞≤',  almost surely.
 
	Such a collection of random state-action value functions
        (_h(x,a))_(h,x,a) ∈ [H]×× is
        guaranteed to exist for pi by the definition of Π_'. We will show via backward induction over ℓ= H+1,…, 1 that 
	
    ∀ x ∈_ℓ,   π_ℓ(x) = π^⋆_ℓ(x)

	almost surely,
	with the convention that π_H+1≡π^⋆_H+1≡π_. This convention makes the base case, ℓ=H+1, hold trivially. 
	
	Now, we consider the general case. Fix h ∈[H] and suppose that (<ref>) holds for all ℓ∈ [h+1 H+1]. We will show that it holds for ℓ=h. 
	
	Thanks to the induction hypothesis, we have for all x∈_h+1 and a∈:
	
    V^π_h+1(x)   = V^⋆_h+1(x), 
    		and so
    		Q^π_h ≡_h[V^π_h+1] ≡_h[V^⋆_h+1] = V^⋆_h.

	Fix x∈. We will show that π_h(x)=π^⋆_h(x) almost surely. Note that thanks to (<ref>), the fact that _h - _h[Q^π_h+1]_∞≤' almost surely, implies that 
	
    _h - Q^⋆_h_∞≤',
	
	almost surely. Using this, we have, almost surely
	
    Q^⋆_h(x,π_h(x))   ≥_h(x,π_h(x))- ',
       ≥_h(x,_h(x)) - ', 
       ≥  Q^⋆_h(x,π_h^⋆(x)) - 2' = Q^⋆_h(x,π_h^⋆(x)) - Δ .

	On the other hand, if π_h(x)≠π_h^⋆(x), then    
	
    Q^⋆_h(x,π_h(x)) < Q^⋆_h(x,π_h^⋆(x)) - Δ,

	which would contradict (<ref>). Thus, π_h(x)= π^⋆_h(x), which concludes the induction and shows that π≡π^⋆. We conclude that Π_'={π^⋆}.





 	
	

§ GUARANTEE FOR WEAKLY CORRELATED EXBMDPS (PROOF OF THM:EXBMDPFORWARD_MAIN)

	
  

		












































In this section, we prove <ref>, the main guarantee for . First, in <ref> we state a number of supporting technical lemmas and use them to prove <ref>. The remainder of the section (<ref> through <ref>) contains the proofs for the intermediate results.




 §.§ Analysis: Proof of thm:exbmdpforward_main





Recall that the the V^π-realizability assumption required by for <ref> is 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 , we address this issue by applying the randomized rounding technique in <ref> to the learned value functions. The crux of the analysis will be to show that for an appropriate choice of the rounding parameters ζ_1:H, the policies produced by are endogenous in the sense that we can write π(x)= π((x)) for all x∈. This will allow us to leverage the decoder realizability (<ref>), which implies that the function class = _1:H given by

    _h{x↦ f(ϕ(x)) : f∈ [0,H]^S, ϕ∈Φ},

        satisfies V^π-realizability for all endogenous policies π.

        

In what follows, we first motivate the randomized rounding approach in in detail and prove that it succeeds, then use this result to proceed with an analysis similar to that of <ref> (), re-using many of the technical tools developed for <ref>.
        


  §.§.§ Randomized Rounding for Endogeneity
 

 Naively, to ensure that the policies we execute are 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 , we apply a randomized rounding to the policies learned by  to ensure their endogeneity.

Let >0 be fixed going forward. Recall that compared to ,  (<ref>) takes an additional input ζ_1:H⊂ (0,1/2) and executes the following coarsened policies:

    _h(·) ∈_a∈_h,, δ [_h+1](·,a)/+ζ_h.

The rounding parameters ζ_1:H, which can be thought of as an offset, are chosen randomly; this will be elucidated in the sequel.

Following a similar analysis to <ref> (), we can associate a near-optimal benchmark policy ∈Π_2 with  in order to emulate certain properties of the Δ-gap assumption. In particular, generalizing the construction in <ref>, we define a near-optimal benchmark policy  recursively via:

	
    ∀ x ∈, 
       _τ(x; ζ_1:H, , δ) ∈_a∈{[                     _τ(x,a)/ + ζ_τ, if _τ(x,·)- _τ[V^_τ+1](x,·)_∞≤ 4^2,;             _τ[V^_τ+1](x,a)/ + ζ_τ,                          otherwise, ].
 



    ∀ x ∈,  _τ(x; ζ_1:H, , δ) ∈_a∈{[                     _τ(x,a)/ + ζ_τ, if _τ(x,·)- _τ[V^_τ+1](x,·)_∞≤ 4^2,;             _τ[V^_τ+1](x,a)/ + ζ_τ,                          otherwise, ].
 

for τ = H,…,1, where _τ(·,a) _τ,, δ [_τ+1](·,a).

Naively, to use the benchmark policy  within the analysis based on relaxed V^π-realizability (<ref>) in <ref> , we would require the function class  to realize (V^_h). However, as argued earlier, this is not feasible unless  is an endogenous policy. Fortunately, it turns out that if ζ_1:H (the additional input to ) 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 (_h) in (<ref>) uniformly,  “snaps” onto the stochastic endogenous policy (·;ζ_1:H, ) defined recursively as follows: 

    _h(·;ζ_1:H,) ∈_a∈_h[V^_h+1](x,a)/ + ζ_h,

for h = H,…, 1. Informally, this happens because, as long as ζ_1:H⊂(0,1/2) avoid certain pathological locations in 0,1/2, the coarsened state-action value functions ·_τ[V^_τ+1](x,a)/ + ζ_h defining  exhibit a “gap” of order Θ(^2) separating optimal actions from the rest. This “snapping” behavior is analogous to what happens in  with V^⋆-realizability and Δ-gap, where Π_ reduces to {} for all <Δ/2 (see <ref>). We formalize these claims in the next two lemmas. We start by showing that  is endogenous and that ∈Π_2. The proof is in <ref>.

	
	For any δ∈(0,1), ∈(0,1/2), and ζ_1:H⊂ (0,1/2), the stochastic policy (·; ζ_1:H,) defined in <ref> is endogenous, and we have (·; ζ_1:H,) ∈Π_2. 

Next, we show that  “snaps” onto  for the certain choices of ζ_1:H. The proof is in <ref>.

	
	Let δ∈ (0,1), ∈(0,1/2) be given, and ^ζ denote the probability law of _1, …, _H∼([0,1/2]). Then, there is an event _ of probability at least 1 - 24 S A H under _1:H∼^ζ such that for all V∈(×H→0,H) simultaneously,
        
	
    ∀ h ∈[H],   _h(·;V,_1:H,,δ) = 	_h(·; _1:H,),

	where _h(·;V,_1:H,,δ) is defined as in (<ref>) with = V, and  is defined as in (<ref>).

The lemma together, with <ref>, implies that with constant probability under ^ζ, the benchmark policies (_h) used in the analysis of  are endogenous and satisfy ∈Π_2.



  §.§.§ Pushforward Coverability


In order to proceed with the analysis strategy in <ref>, we need to verify that pushforward coverability is satisfied for ExBMDPs under the weak correlation assumption. We do so in the next lemma; see <ref> for a proof.

	
	A weakly correlated ExBMDP with constant  (see <ref>) satisfies -pushforward coverability (<ref>) with = · S A, where S∈ℕ is the number of endogenous states. 


Equipped with the preceding lemmas, we proceed with an analysis similar to the approach for <ref> () in <ref>. In what follows, we state a number of technical lemmas that apply the relevant results from <ref> to the ExBMDP setting we consider here.



  §.§.§ Bounding the Number of Test Failures


Since the size of the core sets _1:H in ^ is directly proportional to the number of test failures, the next result, which bounds |_h| for all h∈[H], allows us to show that ^ (<ref>) terminates in a polynomial number of iterations. 


	
	Let δ,∈(0,1) and ζ_1:H∈ [0,1/2] be given, and suppose that <ref> (weak correlation) holds with >0. Let f ∈, be given, where  is an arbitrary function class. Then, there is an event  of probability at least 1-δ under which the call to ^_0(f,^H,∅,∅,0;,, ζ_1:H,δ) (<ref>) terminates, and throughout the execution of ^_0, we have
	
    |_h|≤.



	The results follows from <ref> and <ref>.	




  §.§.§ Value Function Regression Guarantee


We next give a guarantee for the estimated value functions _1:H computed within ^ in <ref> of <ref>.

	
	Let h∈ [0  H], δ, ∈ (0,1), and ζ_1:H∈ [0,1/2] be given, and consider a call to ^_0 in the setting of <ref>. Further, let  be defined as in <ref>, and assume that Φ satisfies <ref>. Then, for any endogenous policy π in , there is an event _h” of probability at least 1 -δ/H under which for any k≥ 1, if 
	
		
  * ^_h gets called for the kth time during the execution of ^_0; and
		
  * this kth call terminates and returns (_h:H, _h:H, _h:H, _h:H, t_h:H),
                
                then if (_τ)_τ≥ h is the policy induced by _h:H and N_ is set as in <ref>, we have 
	
    ∑_(x_h-1,a_h-1)∈_h1/N_∑_(x_h,-)∈_h(x_h-1, a_h-1)( _h(x_h)-V^π_h(x_h))^2
       ≤9 k H^2log(8k^2H||/δ)/N_  +8 H^2∑_(x_h-1,a_h-1)∈_h∑_τ=h^H ^[_τ(_τ)π_τ(_τ)|_h-1=x_h-1,_h-1=a_h-1],

	where the datasets {_h(x, a): (x,a)∈_h} are as in the definition of _h in (<ref>).


  Since Φ satisfies <ref>, the function class = _1:H satisfies V^π-realizability for all endogenous policies π (see <ref>). Thus, the proof of <ref> follows from that of <ref> (see <ref>).





  §.§.§ Confidence Sets


We now state a version of the confidence set validity lemma (<ref>) that supports the ExBMDP setting. 

	
	Let ∈(0,1/2) and ζ_1:H⊂ [0,1/2] be given, and suppose that 
	 
		
  * <ref> holds with >0;
		
  * The decoder class Φ satisfies <ref>;
		
  * ζ_1:H∈_, where _ is the event in <ref>. 
	
	Let f ∈ be arbitrary. There is an event ”' of probability at least 1-3δ under which a call to ^_0(f,,∅,∅,0;,,ζ_1:H,δ) terminates and returns tuple (_1:H, _1:H, _1:H, _1:H, t_1:H) such that
	
    ∀ h ∈ [H],     V^_h ∈_h,

	where _1:H is the policy defined recursively via
	
    _τ(x) ∈_a∈_τ[V^_τ+1](x,a)/ + ζ_h ,  for τ = H,…,1.
 
 
While the proof of this lemma is very similar to that of <ref>, we need a dedicated treatment to handle the rounding in ^. The fully proof of <ref> is in <ref>.





  §.§.§ Main Guarantee for ^

We now state the central technical guarantee for , <ref>, which shows that the base invocation of the algorithm returns a set of value functions _1:H that induce a near-optimal policy , as long as the randomized rounding parameters ζ_1:H satisfy  ζ_1:H∈_, where _ is the success event in <ref>. The proof of the theorem is in <ref>. 


Let δ,∈ (0,1) and ζ_1:H⊂ [0,1/2] be given, and suppose that
 
	
  * <ref> holds with >0;
	
  * The decoder class Φ satisfies <ref>;
	
  * ζ_1:H∈_, where _ is the event in <ref>. 

Then, for any f ∈, with probability at least 1-5δ, a call to ^_0(f,^H,∅,∅,0;,,ζ_1:H,δ) (<ref>) terminates and returns value functions _1:H such that 

    ∀ h ∈ [H],   ^*_h(_h) ≠_h(_h)
    	≤^2/4H^3 S A ,

where _h(x) ∈_a∈_h,,δ'[_h+1](x,a)/ + ζ_h, for all h∈H,  is defined as in <ref>, and δ' is defined as in <ref>. Furthermore, the number of episodes used by ^_0 is bounded by 

    O(^8 S^8 H^10A^9·^-26).





  §.§.§ Concluding: Main Guarantee for 



To conclude, we prove <ref>, which shows that succeeds with high probability.
Recall that (i) invokes multiple times for random samples ζ_1:H to ensure that the success event for <ref> 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 <ref> can be boosted by sampling i.i.d. _1:H1,…, _1:Hn∼^ζ inputs to ^ for n≥ 1; as long as n is polynomially large, with high probability at least one of the inputs _1:H1,…, _1:Hn will satisfy the conclusion of <ref>. Thus, it suffices to pick the policy with the highest value function among the different calls to ^. Using this, we prove <ref>.


 







	Recall that <ref> picks the final policy i__1:H based on empirical value function estimates. In particular, for every i∈[N_] (with N_ as in <ref>), the estimate J(i_1:H) for J(i_1:H) is computed using N_ episodes. Thus, by Hoeffding's inequality and the union bound, we have that there is an event  of probability at least 1-δ/4 under which
	
    ∀ i ∈ [N_],    |J(i_1:H) - J(i_1:H)| ≤√(2log(2N_/δ)/N_).

	Therefore, by definition of i_ in <ref>, we have that under : 
	
    ∀ i ∈ [N_],   J(i_1:H)    ≤ J(i__1:H)  + √(2log(2N_/δ)/N_), 
       ≤  J(i__1:H) + /8,

	where the last inequality follows by the choice of N_ in <ref>. On the other hand, by <ref>, there is an event ^ of ^ζ-probability at least
        
    1-(24 S A H)^N_≥ 1- δ/4   (by the choice of N_ in <ref>)

	 under which there exists j ∈ [N_] such that j_1:H∈_, where _ is defined as in <ref>. In what follows, we condition on the event ^ and let j∈ [N_] be such that j_1:H∈_. Further, we use ^_1:H to denote the policy returned by the instance of ^ that is used by to learn j_1:H.
	
	By <ref> (instantiated with _=0), there is an event ' of probability at least 1-δ/4 under which the policy j produced by  satisfies
	
    J(^_1:H) -  J(j_1:H) ≤/2.
	
By <ref> and the fact that j_1:H∈_, there is an event  of probability at least 1-δ/2 under which: 
	
    ∀ h ∈[H],   ∀ h ∈ [H],   ^*_h(_h) ≠_h(_h)
    	≤^2_/4 H^3 S A≤/4H^2,

where (·) (·; _1:Hj, _) which is defined in (<ref>). 

Moving forward, we condition on ∩∩'. By <ref> (the performance difference lemma), we have
	
    J(π̅)- J(^_1:H)     = ∑_h=1^H ^^[Q^_h(_h, π̅_h(_h)) -  Q_h^π̅(_h, ^_h(_h))],
       ≤ H∑_h=1^H ^*_h(_h) ≠_h(_h)
    		 ,
       ≤/4,

	where the last inequality follows by (<ref>). Now, by <ref>, we have ∈Π_2 _, and so by <ref>,
	
    J() - J() ≤ 6 H _≤/8,

	where the last inequality follows by the choice of _ in <ref>. Combining (<ref>) with (<ref>), (<ref>), and (<ref>), we get that
	
    J()- J(_1:H)= J()- J(i__1:H)     ≤.

	Finally, by the union bound, we have [∩∩']≥ 1 - δ, and so the desired suboptimality guarantee holds with probability at least 1-δ. 
	
	

  
Bounding the sample complexity The sample complexity is dominated by the calls to ^_0 within (<ref>). Since calls ^_0 with suboptimality parameter _ =  H^-1/48, we get by <ref> that the total sample
        complexity is bounded by 
	
    O(^8 S^8H^36A^9·^-26).












 §.§ Proof of lem:endobench (Endogenous Benchmark Policies)



	Fix δ∈ (0,1), ∈ (0,1/2), and ζ_1:H' ⊂ [0,1/2]. We show via backward induction over ℓ = H+1, …, 1 that _τ(·; ζ'_1:H,) is endogenous for all τ∈[ℓ H+1], with the convention that _H+1 =. The base case holds trivially by convention.
	
	Fix h ∈ [H] and suppose that the induction hypothesis holds for all ℓ∈ [h+1 H+1]. We show that it holds for ℓ=h. First, by the induction hypothesis, _ℓ(·; ζ'_1:H,) is endogenous for all ℓ∈ [h+1 H]. Thus, there exists a function f_h+1: → [0, H-h] such that 
	
    V^_h+1(x') = f_h+1((x')),   ∀ x' ∈.

	Therefore, we have for all (x,a)∈×:
	
    _h[V^_h+1](x,a)     = r_h(x,a) +[f_h+1((_h+1)) |_h = x,_h = a], 
        =  r_h(x,a)  + [f_h+1(_h+1) |_h = x,_h = a], 
        =  r_h(x,a)  + [f_h+1(_h+1) |_h = (x),_h = a],

	where the last equality follows by the ExBMDP transition structure. <ref> together with the fact that the rewards are endogenous (by assumption) implies that there exists g_h:×→ [0,H-h+1] such that
	
    ∀ (x,a)∈×,  _h[V^_h+1](x,a) = g_h((x),a),

	which in turn implies that x↦_h[V^_h+1](x,a)/ + ζ_h' is only a function of x through (x) for all a∈. Thus, _h is an endogenous policy and the induction is completed.

        For the second claim, observe that for the functions Q_1, ⋯, Q_H ∈ [0,H]^× defined as
	
    ∀ h ∈[H], ∀ (x,a)∈×,   Q_h(x,a)  = ·_h[V^_h+1](x,a)/ + ζ_h',
    		we have∀ h ∈[H],   _h(·; ζ_1:H',) ∈_a∈Q_h(·,a)   and  Q_h- Q^_h_∞≤ 2 ,

	which implies that (·;ζ_1:H',)∈Π_2.






 §.§ Proof of lem:bench (Snapping Probability)



	Fix ∈ (0,1) and δ∈ (0,1/2). For τ≤ℓ∈ [H], let _τ:ℓ^ζ denote the probability law of _τ, …, _ℓ. We also use the shorthand _τ^ζ for _τ:τ^ζ, for all τ∈[H]. We show via backward induction over ℓ = H+1, …, 1 that there exists an event _ℓ of ^ζ_ℓ:H-probability at least 1- 24 S A (H-ℓ+1) under which for all V∈ (× [H] → [0,H]): 
	
    ∀τ∈ [ℓ H] ,  _τ(·; V, _1:H,, δ) = _τ(·; _1:H,),

	with the convention that _H+1≡_H+1≡π_. We then set _ = _1.
	
	The base case 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 ℓ=h. Throughout, we condition on _h+1. By definition of _h+1, we have for all V∈ (× [H]→ [0,H]):
	
    ∀ℓ∈ [h+1  H] ,  _ℓ(·; _1:H,)= _ℓ(·; V,_1:H,, δ).

	This implies that for all V∈ (× [H]→ [0,H]):
	
	
    ∀ x ∈,  
       _h(x;V, _1:H,, δ) ∈_a∈{[                       _h(x,a)/ + _h, if _h(x,·) -_h [V^_h+1](x,·)_∞≤ 4^2,;               _h[V^_h+1](x,a)/ + _h,                           otherwise, ].


	
	
    ∀ x ∈, _h(x; V,_1:H,, δ) ∈_a∈{[                       _h(x,a)/ + _h, if _h(x,·) -_h [V^_h+1](x,·)_∞≤ 4^2,;               _h[V^_h+1](x,a)/ + _h,                           otherwise, ].


	by the definition of _h in (<ref>), where _h(·,a) _h,, δ [V_h+1](·,a). From this, we see that to prove _h(·; V, _1:H,, δ) = _h(·; _1:H,) for all V, it suffices to show that for all x∈ and V,
	
	
    _a∈_h(x,a)/ + _h   = 	_a∈_h[V^_h+1](x,a)/ + _h,  
    whenever     | _h(x,a)-_h [V^_h+1](x,a)|    ≤ 4^2.

	A sufficient condition for this to hold (for all V simultaneously) is:
	
    ∀ 	x∈, ∀ a∈, ∀δ∈ [-4^2,4^2],
       *(_h [V^_h+1](x,a)+δ)·^-1 +_h =   *_h[V^_h+1](x,a) ·^-1+_h,


	
	
    _a∈_h(x,a)/ + _h = 	_a∈_h[V^_h+1](x,a)/ + _h,      whenever   | _h(x,a)-_h [V^_h+1](x,a)| ≤ 4^2.

	Observe that a sufficient condition for this to hold is that
	
    ∀ 	x∈, ∀ a∈, ∀δ∈ [-4^2,4^2],  *(_h [V^_h+1](x,a)+δ)·^-1 +_h =   *_h[V^_h+1](x,a) ·^-1+_h,


	where δ represents all the possible values that the difference _h(x,a)-_h [V^_h+1](x,a) is allowed to take. By <ref>, we know that  is endogenous, and so there exists a function g_h: ×→ [0,H-h+1] such that 
	
    ∀ x∈,a∈,   _h [V^_h+1](x,a) = g_h((x),a).

        Toward proving <ref>, observe that for any (s,a)∈∈, if _h is such that 
	
    g_h(s,a)/  + _h + 4   ≤g_h(s,a)/+_h, 
    and     		g_h(s,a)/  + _h - 4    >   	g_h(s,a)/+_h - 1,

	then, for all δ∈[-4^2,4^2] and all x∈ such that (x)=s, we have 
	
	
    (_h [V^_h+1](x,a)+δ) /+_h =	(g_h(s,a)+δ)/+_h   =g_h(s,a)/+_h, 
         = 	_h [V^_h+1](x,a) /+_h.


	
	
    (_h [V^_h+1](x,a)+δ) /+_h =	(g_h(s,a)+δ)/+_h  =g_h(s,a)/+_h = 	_h [V^_h+1](x,a) /+_h.


	Therefore, if we let _h(s,a) denote the event in (<ref>), then under ⋂_(s,a)∈×_h(s,a), the desired condition in (<ref>) holds. At this point, setting _h = (⋂_(s,a)∈×_h(s,a)) ∩_h+1 would complete the induction as long as ^ζ_h:H[_h] ≥ 1 - 24 SA(H-h+1). We now show that this is indeed the case by bounding the probability of the event ⋂_(s,a)∈×_h(s,a). By the union bound, we have 
	
    ^ζ_h:H[⋂_(s,a)∈×_h(s,a) |_h+1] ≥ 1 - ∑_(s,a)∈×^ζ_h:H[_h(s,a)^c |_h+1],

	where _h(s,a)^c denotes the complement of _h(s,a). We now bound the probability 
    ^ζ_h:H[_h(s,a)^c |_h+1].
 Fix (s,a)∈×. We have that _h ∈(s,a)^c if and only if 
	
    g_h(s,a)/  + _h + 4   > 	g_h(s,a)/+_h, 
    or     
    			g_h(s,a)/  + _h - 4   ≤g_h(s,a)/+_h - 1.

	Now, since _h ∈[0,1/2], <ref> (instantiated with (x,ζ, ν) =(g_h(s,a)/,_h,4)) implies that  (<ref>) holds only if 
	
    g_h(s,a)/ -4 ≤   g_h(s,a)/  + _h    ≤g_h(s,a)/  + 4  or     0  ≤_h  ≤  4 .

	Further, note that since _h is uniformly distributed over [0,1/2], the ^ζ_h-probability of the event in (<ref>) is at most the sum of the lengths of the intervals 
    [g_h(s,a)/- g_h(s,a)/-4, g_h(s,a)/- g_h(s,a)/+4]   and    [0,4],
 multiplied by 2, which is equal to 24. Therefore, we have 
	
    ^ζ_h:H[_h(s,a)^c |_h+1] 
       ≤^ζ_h[g_h(s,a)/ - 4≤   g_h(s,a)/  + _h    ≤g_h(s,a)/  + 4  or    0  ≤_h  ≤   4] ≤ 24 .

	Combining this with (<ref>), we obtain
	
    ^ζ_h:H[⋂_(s,a)∈×_h(s,a) |_h+1]  ≥ 1 - ∑_(s,a)∈×^ζ_h:H[_h(s,a)^c |_h+1]≥ 1 - 24 S A .

	Thus, by setting _h = (⋂_(s,a)∈×_h(s,a)) ∩_h+1, we get that 
	
    ^ζ_h:H[_h] ≥^ζ_h+1:H[_h+1] ·^ζ_h:H[_h|_h+1]     ≥ (1-24 S A (H-h)) (1-24 S A ), 
       ≥ 1 - 24 SA(H-h+1),
 
	which completes the induction.






 §.§ Proof of lem:pushforward (Coverability in Weakly Correlated ExBMDP)





	
	Fix h∈[2 H] and define the measure μ as
	
    μ(x) ∑_ξ' ∈Ξ q(x' | (_h(x'), ξ')) ·[_h = ξ'] ·[_h = _h(x')|_h-1=_h-1(x),_h-1=a],

	for all h ∈[H] and x ∈. We show that μ satisfies <ref> with = · S A. First, note that μ is indeed a probability measure over . Fix (x,a,x')∈××. We have
	
    [_h = x' |_h-1=x,_h-1=a] 
       =  [_h = x', _h-1=x|_h-1=a]/[_h-1=x|_h-1=a], 
       =  [_h = x', _h-1=x|_h-1=a]/[_h-1=x], 
       =  ∑_ξ,ξ'∈Ξ q(x' | (_h(x'), ξ'))· q(x | (_h-1(x), ξ))·[_h = _h(x'), _h=ξ',_h-1=_h-1(x), _h-1=ξ|_h-1=a]/∑_ξ∈Ξ q(x | (_h-1(x), ξ))·[_h-1=_h-1(x), _h-1=ξ], 
    and so by the ExBMDP structure:    = ∑_ξ, ξ' ∈Ξ q(x' | (_h(x'), ξ'))· q(x | (_h-1(x), ξ)) ·[_h = ξ',  _h-1 = ξ]  ·[_h = _h(x')|_h-1=_h-1(x),_h-1=a]/∑_ξ∈Ξ q(x | (_h(x), ξ)) ·[_h-1 = ξ], 
    and by <ref>   ≤∑_ξ, ξ' ∈Ξ q(x' | (_h(x'), ξ'))· q(x | (_h-1(x), ξ)) ·[_h = ξ']·[_h-1 = ξ]  ·[_h = _h(x')|_h-1=_h-1(x),_h-1=a]/∑_ξ∈Ξ q(x | (_h(x), ξ)) ·[_h-1 = ξ], 
        = ∑_ξ' ∈Ξ q(x' | (_h(x'), ξ')) ·[_h = ξ']  ·[_h = _h(x')|_h-1=_h-1(x),_h-1=a], 
        =  S A ·μ(x'),

 This completes the proof. 





 §.§ Proof of lem:confidencesets_ex (Confidence Sets)



To prove <ref>, we need the following consequence of tests in <ref> passing for all ℓ∈ [h+1 H]. 

	
	Let h∈ [0  H], >0, and ζ_1:H∈[0,1/2] be given and consider a call to ^_0 (<ref>) in the setting of  <ref>. Further, let  be the event of <ref>. There exists an event _h' of probability at least 1- δ/H such that under ∩'_h, if a call to ^_h during the execution of ^_0 terminates and returns (_h:H, _h:H, _h:H, _h:H, t_h:H), then for any (x_h-1,a_h-1) ∈_h and ℓ∈ [h+1  H+1]:  
	
    ^*sup_f∈ _ℓmax_a∈| (_ℓ-1[_ℓ]-_ℓ-1[f_ℓ])(_ℓ-1,a) |  > 3^2
    			|_h-1= x_h-1,_h-1=  a_h-1≤,
where (_τ)_τ≥ h⊂, M, and N_ are as in ^_h (<ref>).
	
 

	This is just a restatement of <ref>, and the proof is exactly the same as the latter.


We will also use <ref>; even though this result is stated in section for the V^π-realizable setting, it is also applicable to the ExBMDP variant of  as it merely says something about the order in which the (^_h) instances are called. With this, we now prove <ref>.



	The proof is very similar to that of <ref>, with differences to account for the “coarsening” of the learned and benchmark policies. 


	We prove the desired result for ”'∩'_1∩_1”∩…∩_H' ∩_H”, where , (_h'), and (_h”) are the events in <ref>, <ref>, and <ref>, respectively. Throughout, we condition on ”'. First, note that by <ref>, ^_0 terminates. Let (_1:H, _1:H,
	_1:H,_1:H, t_1:H) be its returned tuple.
	
	We show via backward induction over ℓ=H+1,…, 1, that
	
    V^_ℓ∈_ℓ,
 
	where _1:H is the stochastic policy defined recursively via
		
		
    ∀ x ∈, 
       _τ(x; ζ_1:H, , δ) ∈_a∈{[                     _τ(x,a)/ + ζ_τ, if _τ(x,·)- _τ[V^_τ+1](x,·)_∞≤ 4^2,;             _τ[V^_τ+1](x,a)/ + ζ_τ,                          otherwise, ].
 
	
	
	
    ∀ x ∈,  _τ(x; ζ_1:H, , δ) ∈_a∈{[                     _τ(x,a)/ + ζ_τ, if _τ(x,·)- _τ[V^_τ+1](x,·)_∞≤ 4^2,;             _τ[V^_τ+1](x,a)/ + ζ_τ,                          otherwise, ].
 

	for τ = H,…,1, where _τ(·,a) _τ,, δ [_τ+1](·,a). Note that since ζ_1:H∈_ (for _ is defined in <ref>), we have ≡, where  is as in (<ref>). Thus, instantiating the induction hypothesis with ℓ=h and using the definition of the confidence sets (_ℓ) in (<ref>) together with V^_h≡ V_h^ (since ≡) implies the desired result. 
	
	

  
Base case [ℓ=H+1] Holds trivially since V^π_H+1≡ 0 for any π∈ by convention. 
	
	

  
General case [ℓ≤ H] Fix h∈[H] and suppose that (<ref>) holds for all ℓ∈[h+1 H+1]. We show that this remains true for ℓ=h. First, note that if ^_h is never called during the execution of ^_0, then _h = _h, and so (<ref>) holds for ℓ=h, since = is endogenous under ζ_1:H∈_, where _ is the event in <ref>.
	
	Now, suppose that ^_h is called at least once, and let (^+_h:H,^+_h:H,
	^+_h:H,^+_h:H,t^+_h:H) be the output of the last call to ^_h throughout the execution of ^_0. Next, we show that 
    (^+_h:H,^+_h:H,
    		^+_h:H) = (_h:H,_h:H,
    		_h:H).

	The for-loop in <ref> ensures that no instance of (^_τ)_τ>h can be called after the last call to ^_h (see <ref>). Thus, the estimated value functions, confidence sets, and core sets for layers h+1, …, H remain unchanged after the last call to ^_h; that is, (<ref>) holds. Thus, by <ref>, and since we are conditioning on _h+1:H', we have that for all (x_h-1,a_h-1) ∈_h and ℓ∈ [h+1  H+1]:
	
    ^*sup_f∈ _ℓmax_a∈|( _ℓ-1[_ℓ]- _ℓ-1[f_ℓ])(_ℓ-1,a) |  > 3^2 |_h-1= x_h-1,_h-1= a_h-1≤.

	Now, by the induction hypothesis, we have V^_ℓ∈_ℓ, and so substituting V^_ℓ for f_ℓ in (<ref>), we get that for all (x_h-1,a_h-1) ∈_h and ℓ∈ [h+1  H+1]:
	
    ^*max_a∈| (_ℓ-1[_ℓ]-  _ℓ-1[V^_ℓ])(_ℓ-1,a) |  > 3^2 |_h-1= x_h-1,_h-1=  a_h-1≤.

	Therefore, by <ref> (instantiated with μ[·] = ^[·|_h-1= x_h-1,_h-1=a_h-1], τ = ℓ-1, '=^2, and V_τ+1 = V^_ℓ), we have that for all (x_h-1,a_h-1) ∈_h and ℓ∈ [h+1  H+1]: 
	
    ^*_ℓ-1(_ℓ-1)_ℓ-1(_ℓ-1)|_h-1=x_h-1,_h-1=a_h-1≤ + δ'.

	Now, since (·; ζ_1:H,) is endogenous and ≡ (thanks to ζ_1:H∈_), <ref> (applied with π=) and the conditioning on _h+1:H” imply that:
	
    ∑_(x_h-1,a_h-1)∈_h1/N_∑_(x_h,-)∈_h(x_h-1, a_h-1)( _h(x_h)-V^_h(x_h))^2
       ≤9 kH^2log(8k^2H||/δ)/N_  +8 H^2  ∑_(x_h-1,a_h-1)∈_h∑_τ=h^H ^[_τ(_τ)_τ(_τ)|_h-1= x_h-1,_h-1= a_h-1],

	where the datasets {_h(x, a): (x,a)∈_h} are as in the definition of _h in (<ref>). Combining (<ref>) with (<ref>), we conclude that 
	
    ∑_(x_h-1,a_h-1)∈_h1/N_∑_(x_h,-)∈_h(x_h-1, a_h-1)( _h(x_h)-V^_h(x_h))^2
       ≤9 M H^2log(8M^2H||/δ)/N_  + 8 M H^3·  + 8M H^3δ', 
        = 9M  H^2log(8M^2H||/δ)/N_  + 8 M H^3·  + 8M H^3  δ/4M^7N_^2 H^8||,
       ≤_^2,

        where we have used that _h≤M.
	By the definition of _h in (<ref>), (<ref>) implies that V^_h ∈_h, which completes the induction.




 §.§ Proof of thm:lbc2 (Main Guarantee of ^)


 We condition on the event ∩”'∩'_1∩…∩_H', where , ”', and (_h') are the events in <ref>, <ref>, and <ref>, respectively. Note that by the union bound, we have [] ≥  1 - 5 δ. By <ref>, we have that 
	
    ∀ h ∈[H],  ^*sup_f∈ _hmax_a∈|(_h-1[_h]-_h-1[f_h])(_h-1,a) |>3^2≤,

	where M = and N_=. On the other hand, by <ref>, we have 
	
    ∀ h ∈[H],    	V^_h∈_h.

	Thus, substituting V^_h for f_h in (<ref>) we get that for all h∈[H+1].
	
    ^*max_a∈|(_h-1[_h]- _h-1[V^_h])(_h-1,a)|   > 3^2≤.

	This together with <ref>, instantiated with μ[·] = ^[·]; τ = h-1; V_τ+1 = V^_h; and δ = δ' (with δ' as in <ref>), translates to:
	
    ∀ h∈[H],   ^*_h(_h)_h(_h)   ≤ + δ',  
       =  + δ/4 M^7 N_^2 H^8 ||, 
       ≤^2/4H^3 S A ,

		where the last step follows from the fact that N_ = (with M as in <ref>). Now, since ζ_1:H∈_ (by assumption), <ref> implies that ≡, where the latter is the deterministic policy defined in (<ref>). Thus, by (<ref>), we have 
		
    ∀ h ∈ [H],   ^[_h(_h)≠_h(_h)] = ^*_h(_h)_h(_h)≤^2/4 H^3 S A ,

		where the first equality follows by the fact that [_h(x)≠_h(x)] =  _h(x)_h(x), for all x∈, since _h is deterministic.
	
	

  
Bounding the sample complexity
	We now bound the number of episodes used by <ref> under . First, we fix h∈[H], and focus on the number of episodes used within a to call ^_h; excluding any episodes used by any recursive calls to ^_τ for τ >h. We start by counting the number of episodes used to test the fit of the estimated value functions _h+1:H. Starting from <ref>, there are for-loops over (x_h-1,a_h-1)∈_h, ℓ=H, …, h+1, and n ∈ [N_] to collected partial episodes using the learned policy  in <ref>, where N_ = and M =. Note that  uses the local simulator and requires N_= 2 log(4 M^7 N_^2 H^2 ||/δ)/^2 samples to output an action at each layer (since <ref> calls <ref> with confidence level δ'=). Also, note that whenever a test fails in <ref>, the for-loop in <ref> resumes. We also know (by <ref>) that the number of times the test fails in <ref> is at most M. Thus, the number of times the for-loop in <ref> resumes is bounded by H M; here, H accounts for test failures for all layers τ∈[h+1 H]. Thus, the number of episodes required to between lines <ref> and <ref> is bounded by 
	
    # episodes for roll-outs≤MH_# of times <ref> resumes·MH^2 N_ N__Number of episodes in case of no test failures.

	Note that the test in <ref> also uses local simulator access because it calls the operator  for every a∈. Thus, the number of episodes used for the test in <ref> is bounded by 
	
    # episodes for the tests≤MH_# of times <ref> resumes·M H A N_ N__Number of episodes used in <ref>.

	We now count the number of episodes used to re-fit the value function; <ref> onwards. Note that starting from <ref>, there are for-loops over (x_h-1,a_h-1)∈_h and i∈ [N_] to generate A ·(|_h|)≤ A ·(M) partial episodes using , where (k)=2N_^2 log(8 A N_ H k^3/δ) is as in <ref>. And, since  uses local simulator access and requires  samples (see <ref>) to output an action at each layer, the number of episodes used to refit the value function is bounded by 
	
    # episodes for V-refitting≤ M N_ A (M) H N_.

	Therefore, by (<ref>), (<ref>), and (<ref>), the number of episodes used within a single call to ^_h (not accounting for episodes used by recursive calls to ^_τ, for τ >h) is bounded by
	
    # episodes used locally within ^_h   ≤  M^2 H (H + A) N_ N_  +M N_ A (M) H N_.

	Finally, by <ref>, ^_h may be called at most M times throughout the execution of ^_0. Using this together with (<ref>) and accounting for the number of episodes from all layers h∈[H], we get that the total number of episodes is bounded by 
	
    M^3 H^2 (H + A) N_ N_   +M^2 H^2 N_ A (M) N_.
  
	Substituting the expressions of M, N_, , N_, and N_ from <ref> and <ref>, we obtain the desired number of episodes, which concludes the proof.










 	



§ ADDITIONAL TECHNICAL LEMMAS




	
	Let τ∈[H] and , δ, ν∈(0,1) be given. Consider two value functions V_τ+1, _τ+1∈ [0, H] and a measure μ∈Δ() such that 
	
    __τ∼μ*𝕀{max_a∈| (_τ[_τ+1]- _τ[V_τ+1])(_τ,a) |  > 3}≤ν.

	Further, for x∈, let _τ(x) ∈_a∈_τ(x,a) _τ,, δ[_τ+1](x,a) and
	inductively define a randomized policy  via
	
    _τ(x) ∈_a∈{[                          _τ(x,a) , if _τ(x,·) -_τ [ V_τ+1](x,·)_∞≤ 4,;                    _τ[V_τ+1](x,a),                         otherwise. ].


	Then, we have 
	
    __τ∼μ[_τ(_τ)_τ(_τ)] ≤ν +δ.



	In this proof, we let _μ denote the probability law of _τ and _ denote the probability law of _τ,, δ. Denote by  the _μ-measurable event that max_a∈|(_τ[_τ+1]-
	_τ[V_τ+1])(_τ,a) |  ≤ 3. Fix x∈, and let
	_x be the _-measurable event that max_a∈ |_τ,,
		δ [_τ+1](x,a)-
	_τ[V_τ+1](x,a)|≤ 4. 
	From the definition of _τ, we have that 
	
    _τ(x)_τ(x)
         = 1/2∑_a∈| _[_τ(x)=a] - _[_τ(x)=a]  |, 
         =1/2∑_a∈| _[_x]  _[_τ(x)=a|_x ] +  _[_x^c]  _[_τ(x)=a|_x^c ]  - _[_x] _[_τ(x)=a|_x] - _[_x^c] _[_τ(x)=a|_x^c] |,
       ≤1/2∑_a∈_[_x] ·| _[_τ(x)=a|_x ] - _[_τ(x)=a|_x]  |
            +∑_a∈_[_x^c]·| _[_τ(x)=a|_x^c ] - _[_τ(x)=a|_x^c] |,   (Jensen's inequality)
    and since _[_τ(x)=a|_x ]=_[_τ(x)=a|_x ]∀ a∈, we have that     =1/2∑_a∈_[_x^c]·| _[_τ(x)=a|_x^c ] - _[_τ(x)=a|_x^c] |,, 
       ≤_[_x^c], 
         = _[ max_a∈ |_τ,, δ [_τ+1](x,a)- _τ[V_τ+1](x,a)|  > 4 ], 
       ≤_[ max_a∈ |_τ,, δ [_τ+1](x,a)- _τ[_τ+1](x,a)|  >  ],   (see below)
       ≤δ,

	where (<ref>) follows from x∈ and the last inequality follows from <ref>. Therefore, we have  
	
    _μ[_τ(_τ)_τ(_τ)]    ≤_μ[] ·_μ[_τ(_τ)_τ(_τ)|] + _μ[^c],
       ≤δ +ν,

	where the first inequality follows by the fact that the total variation distance is bounded by 1, and the last inequality follows by (<ref>) and (<ref>).


	
	Let τ∈[H] and ', δ,ν∈(0,1), and ζ_1:H∈ [0,1/2] be given. Further, consider two value functions V_τ+1,_τ+1∈[0,H] and measure μ∈Δ() such that 
	
    __τ∼μ*𝕀{max_a∈| (_τ[_τ+1]-  _τ[V_τ+1])(_τ,a) |>3'}≤ν.

	Further, for x∈_τ, let _τ(x) ∈_a∈_τ(x,a)/' +ζ_τ,
	where _τ(x,a)_τ,',
		δ[_τ+1](x,a), and inductively define
	
    _τ(x) ∈_a∈{[                    _τ(x,a)/' + ζ_τ, if _τ(x,·) -_τ [ V_τ+1](x,·)_∞≤ 4',;             _τ[V_τ+1](x,a)/' + ζ_τ,                          otherwise. ].

	Then, we have 
	
    __τ∼μ[_τ(_τ)_τ(_τ)] ≤ν +δ.



	In this proof, we let _μ denote the probability law of _τ and _ denote the probability law of _τ,, δ.
	Denote by  be the _μ-measurable event that max_a∈|
	(_τ[_τ+1]-
	_τ[V_τ+1])(_τ,a) |  ≤ 3'. Fix x∈, and let _x be the _-measurable event that
	max_a∈ |_τ,', δ
	[_τ+1](x,a)- _τ[V_τ+1](x,a)|≤
	4'. From the definition of _τ, we have that
	
    _τ(x)_τ(x)
         = 1/2∑_a∈| _[_τ(x)=a] - _[_τ(x)=a] |, 
         =1/2∑_a∈| _[_x]  _[_τ(x)=a|_x ] +  _[_x^c]  _[_τ(x)=a|_x^c ]  - _[_x] _[_τ(x)=a|_x] - _[_x^c] _[_τ(x)=a|_x^c] |,
       ≤1/2∑_a∈_[_x] ·| _[_τ(x)=a|_x ] - _[_τ(x)=a|_x]  |
            +∑_a∈_[_x^c]·| _[_τ(x)=a|_x^c ] - _[_τ(x)=a|_x^c] |,   (Jensen's inequality)
    and since _[_τ(x)=a|_x ]=_[_τ(x)=a|_x ]∀ a∈,      =1/2∑_a∈_[_x^c]·| _[_τ(x)=a|_x^c ] - _[_τ(x)=a|_x^c] |, 
       ≤_[_x^c], 
         = _[ max_a∈ |_τ,', δ [_τ+1](x,a)- _τ[V_τ+1](x,a)|  > 4 '], 
       ≤_[ max_a∈ |_τ,', δ [_τ+1](x,a)- _τ[_τ+1](x,a)|  >  '],   (see below)
       ≤δ,

	where (<ref>) follows from x∈ and the last inequality follows from <ref>. Therefore, we have  
	
    __τ∼μ[_τ(_τ)_τ(_τ)]    ≤_μ[] ·__τ∼μ[_τ(_τ)_τ(_τ)|] + _μ[^c],
       ≤δ +ν,

	where the first inequality follows by the fact that the total variation is bounded by 1, and the last inequality follows by (<ref>) and (<ref>).



	
	Let x∈ and ν∈(0,1/2) be given. Further, let ζ∈ (0,1/2). Then, 
	
    x + ζ +ν > x+ζ  or   x + ζ -ν≤x+ζ-1,
    		only ifx-ν≤ x + ζ≤x + ν  or  ζ≤ν.



	To prove the claim, it suffices to show the following items:
	
		
  * x + ζ +ν > x+ζ only if x≥ x + ζ > x - ν; and 
		
  * x + ζ -ν≤x+ζ-1 only if x < x + ζ≤x+ν or ζ≤ν.
	 	
	We start by showing the first item. We proceed by showing the contrapositive; that is, we will show that if x+ζ≤x-ν or x+ζ> x, then x + ζ +ν≤x+ζ. Suppose that x+ζ≤x-ν. This, together with the fact that ζ≥ 0, implies that 
	
    x+ζ = x≥ x +ζ +ν.

	Now, suppose that x+ζ> x. Then, we have 
	
    x+ζ≥x+1 ≥x +ζ +ν≥ x + ζ +ν,

	where the penultimate inequality follows by ζ,ν∈ (0,1/2).
	
	We now prove the second claim. Again, we proceed by showing the contrapositive; that is, we will show that if x+ ν <  x + ζ or x≥ x+ζ and ζ> ν, then x + ζ -ν >  x+ζ-1.
	
	Suppose that x+ ν < x + ζ and ζ> ν. The first inequality together with ν≥ 0 implies that x + ζ > x. On the other hand, since ζ≤ 1/2, we have x+ζ≤x+1, and so  
	
    x+ζ -1 = x <  x + ζ- ν,

	where the last inequality follows by the current assumption that x+ ν < x + ζ. 
	
	Now, suppose that x≥ x+ζ and that ζ >ν. Then, we have 
	
    x+ζ≤x≤ x +1 < x + ζ - ν +1,

	where the last inequality follows by ζ>ν. Rearranging (<ref>) completes the proof. 
 
 			
                        
                        

§  ALGORITHM AND ANALYSIS
		
                        
                        


In this section, we give a self-contained presentation and analysis
for the standard behavior cloning algorithm for imitation learning
(e.g., <cit.>), displayed in
<ref>. Given access to trajectories from an expert policy
_1:H (which may be non-executable in the sense of
<ref>) the algorithm learns an executable policy
π^ with similar performance. We use this scheme within  and .









 


	
Let , δ∈(0,1) be given and let Π⊆ and _1:H be an expert policy such that 

    inf_π∈Π∑_h=1^H 	^[_h(_h)≠π_h(_h)]≤_.

Then, the policy π^_1:H = (Π, , _1:H, δ) returned by <ref> satisfies, with probability at least 1-δ,

    J()  - J(π^)  ≤ 4H _  + /2.



First, by the performance difference lemma, we have 

    [	V^_1(_1)]  - [V^π^_1(_1)]      = ∑_h=1^H ^[Q^π^_h(_h, _h(_h)) -  Q_h^π^(_h, π^_h(_h))],
       ≤H∑_h=1^H ^[ _h(_h) ≠π^_h(_h)].
	
We now bound the probability terms on the right-hand side. Fix h∈[H] and let  be the dataset in <ref>, which consists of N_ i.i.d. trajectories ((_1,_1),…,(_H,_H)) generated by rolling with _1:H. By <ref> (with i.i.d. data, B=
H, and = Π), we have that, with probability at least 1-δ,

    ∀π∈Π,   ∑_((x_1,a_H),…, (x_H,a_H) )∈∑_h∈[H]𝕀{π_h(x_h) ≠(x_h)}   ≤ 2   ∑_h∈[H]^[π_h(_h) ≠_h(_h)]
          + 2H log(2 |Π|/δ)/N_,

and

    ∀π∈Π,   ∑_h∈[H]^[π_h(_h) ≠_h(_h)]     ≤ 2 ∑_((x_1,a_H),…, (x_H,a_H) )∈∑_h∈[H]𝕀{π_h(x_h) ≠(x_h)}
          + 4H log(2 |Π|/δ)/N_.

Taking the infimum over π on both sides of (<ref>) and using the definition of π^_h in <ref> gives:

    ∑_((x_1,a_H),…, (x_H,a_H) )∈∑_h∈[H]𝕀{π^_h(x_h) ≠(x_h)}   ≤ 2 inf_π∈Π∑_h∈[H]^[π_h(_h) ≠_h(_h)]
          + 2H log(2 |Π|/δ)/N_, 
       ≤ 2_ + 2 H log(2 |Π|/δ)/N_,

where the last inequality follows from (<ref>). Using this together with (<ref>), instantiated with π≡π^, we get that with probability at least 1-δ:

    ∑_h∈[H]^[π^_h(_h) ≠_h(_h)]  ≤ 4 _ +  8H log(2 |Π|/δ)/N_.

Plugging this into (<ref>), we get that with probability at least 1-δ:

    [	V^_1(_1)]  - [V^π^_1(_1)] ≤ 4H _ +  8H^2 log(2 |Π|/δ)/N_≤ 4H _  + /2,

where the last inequality follows by the fact that N_ = 16H^2 log(2|Π|/δ)/. This completes the proof.






 
      
	
	
	
	

