The Effective Horizon Explains Deep RL Performance in Stochastic Environments
Authors: Cassidy Laidlaw
Banghua Zhu
Stuart Russell
Anca Dragan
Venue: ICLR 2024 spotlight (2024)
Keywords: reinforcement learning
effective horizon
RL theory
theory of reinforcement learning
instance-dependent bounds
empirical validation of theory
Primary area: reinforcement learning
TL;DR: We extend the recently proposed "effective horizon" property to stochastic MDPs and show theoretically and empirically that it can explain the performance of deep RL algorithms.

Abstract: Reinforcement learning (RL) theory has largely focused on proving minimax sample complexity bounds. These require strategic exploration algorithms that use relatively limited function classes for representing the policy or value function. Our goal is to explain why deep RL algorithms often perform well in practice, despite using random exploration and much more expressive function classes like neural networks. Our work arrives at an explanation by showing that many stochastic MDPs can be solved by performing only a few steps of value iteration on the random policy’s Q function and then acting greedily. When this is true, we find that it is possible to separate the exploration and learning components of RL, making it much easier to analyze. We introduce a new RL algorithm, SQIRL, that iteratively learns a near-optimal policy by exploring randomly to collect rollouts and then performing a limited number of steps of fitted-Q iteration over those roll- outs. We find that any regression algorithm that satisfies basic in-distribution generalization properties can be used in SQIRL to efficiently solve common MDPs. This can explain why deep RL works with complex function approximators like neural networks, since it is empirically established that neural networks generalize well in-distribution. Furthermore, SQIRL explains why random exploration works well in practice, since we show many environments can be solved by effectively estimating the random policy’s Q-function and then applying zero or a few steps of value iteration. We leverage SQIRL to derive instance-dependent sample complexity bounds for RL that are exponential only in an “effective horizon” of lookahead—which is typically much smaller than the full horizon—and on the complexity of the class used for function approximation. Empirically, we also find that SQIRL performance strongly correlates with PPO and DQN performance in a variety of stochastic environments, supporting that our theoretical analysis is predictive of practical performance. Our code and data are available at https://github.com/cassidylaidlaw/effective-horizon.

Published as a conference paper at ICLR 2024
THE EFFECTIVE HORIZON EXPLAINS DEEP RL PERFORMANCE IN STOCHASTIC ENVIRONMENTS
Banghua Zhu University California, Berkeley fcassidy laa.aaii
Cassidy Laidlaw
Stuart Russell
Anca Dragan
wiciddyylliiie biidlaw, banghua, russell, anca |ecs www.eley..ee....e..............e .ddu
ABSTRACT
Reinforcement learning (RL) theory has largely focused on proving minimax sam- ple complexity bounds. These require strategic exploration algorithms that use relatively limited function classes for representing the policy or value function. Our goal is to explain why deep RL algorithms often perform well in practice, despite using random exploration and much more expressive function classes like neural networks. Our work arrives at an explanation by showing that many stochastic MDPs can be solved by performing only a few steps of value iteration the random policy's 's function and then acting greedily. When this is true, we find that is possible to separate the exploration and learning components of RL, making it much easier analyze. We introduce new RL algorithm, SQIRL, that iteratively learns a near-optimal policy by exploring randomly to collect rollouts and then performing limited number of steps of fitted-Q iteration over those roll- outs. We find that any regression algorithm that satisfies basic in nn-distribution gen- eralization properties can be used in SQIRL efficiently solve common MDPs. This can explain why deep RL works with complex function approximators like neural networks, since it is empirically established that neural networks general- ize well in-distribution. Furthermore, SQIRI. explains why random exploration works well in practice, since we show many environments can be solved by ef- fectively estimating the random policy's Q-function and then applying zero or few steps of value iteration. We leverage SQIRL to derive instance deeenddn sample complexity bounds for RL that exponential only in an "effective hori- is typically much smaller than the full horizon-and and the complexity of the class used for function approximation. Empirically, we also find that SQIRL performance strongly correlates with PPO and DQN per- formance in variety of stochastic environments, supporting that our theoretical analysis is predictive of practical performance. Our code and data are available at httt:s///ggttoococcc///rreeeaaaa
zon" bookahead-whinn
INTRODUCTION
The theory of reinforcement learning (RL) does not quite predict the practical successes (and fail- ures) of deep RL. Specifically, there are two gaps between theory and practice. First, whereas RL theory emphasizes strategic exploration, practical deep RL algorithms often resort to random explo- ration, such as e-greedy strategies. This divergence difficult to resolve since theory predicts ex- ponential worst-case sample complexity for random exploration. Most recent progress in the theory of RL has focused on strategic exploration algorithms, which use upper confidence bound (UCB) bonuses to effectively explore the state space of an environment. Second, RI. theory struggles to incorporate complex function approximators like the neural networks used in deep RI.. UCB-type algorithms only work in highly-structured environments where they use simple function classes to represent value functions and policies.
Our goal is to bridge these two gaps: to explain why random exploration works despite being expo- nentially bad in the worst-case, and to understand why deep RL succeeds despite using deep neural networks for function approximation. Some recent progress has been made the former prob- lem by Laidlaw et al. (2023), who analyze when random exploration will succeed in deterministic environments. Their analysis begins by demonstrating surprising property: in many determinis-

---

Published as a conference paper at ICLR 2024
tic environments, it is optimal to act greedily according to the Q-function of the policy that takes actions uniformly at random. This inspires their definition of property of deterministic environ- ments called the "effective horizon," which is roughly the number of lookahead steps Monte Carlo planning algorithm needs to solve the environment when relying on random rollouts to evaluate leaf nodes. They then show that randomly exploring RI algorithm called Greedy Over Random Policy (GORP) has sample complexity exponential only in the effective horizon rather than the full horizon. While the effective horizon sometimes equal to the full horizon, they show it is much smaller for many benchmark environments where deep RL succeeds; conversely, when the effective horizon is high, deep RL rarely works.
In this work, we take inspiration from the effective horizon to analyze RL in stochastic environments with funetion approximation. major challenge of understanding RI. in this setting the complex interplay between exploration and function approximation. This has made strategic exploration algorithms based on upper confidence bound (UCB) bonuses difficult to analyze because the bonuses must be carefully propagated through the function approximators. The same issue makes it hard to understand deep RL algorithms, in which the current exploration policy affects the data the function approximators are trained on, which in turn affects future exploration. Our idea is to leverage the effective horizon assumption that limited lookahead followed by random rollouts is enough to arrive at the optimal action-to separate exploration and learning in RL.
We introduce a new RL. algorithm, SQIRL (shallow Q-iteration via reinforcement learning), that generalizes GORP stochastic environments. SQIRL iteratively learns a policy by alternating between collecting data through purely random exploration and then training function approximators on the collected data. During the training phase, SQIRL uses regression to estimate the random policy's 's Q-function and then fitted Q-iteration to approximate a few steps of value iteration. The advantage of this algorithm is that it only relies on access to regression oracle that can generalize in-distribution from i.i.d. samples-a a property that is empirically true of neural networks. Thus, unlike strategic exploration algorithms which work for only limited function classes, SQIRL helps explain why RI. can work with expressive function classes. Furthermore, the way SQIRI. leverages the effective horizon property helps explain why RL works in practice using random exploration.
Theoretically, we prove instance-dependent sample complexity bounds for SQIRL that depend on a stochastic version of the effective horizon as well as properties of the regression oracle used. We demonstrate empirically that the effective horizon assumptions are satisfied in many stochastic benchmark environments. Furthermore, we show that a wide variety of function approximators can be used within SQIRI.. For instance, our bounds hold for least-squares regression with function classes of finite pseudo-dimension, including linear functions, neural networks, and many others.
To strengthen our claim that SQIRL often explain why deep RL succeeds while using random exploration and neural networks, we compare its performance to PPO (Schulman et al.) 2017) and DQN (Mnih al., 2015) in over 150 stochastic environments. We implement SQIRL using least- squares neural network regression and evaluate its empirical sample complexity, along with that of PPO and DQN, in sticky-action versions of the BRIDGE environments from Laidlaw et al. (2023). We find that in environments where both PPO and DQN converge to an optimal policy. SQIRL does as well 85% of the time; when both PPO and DQN fail, SQIRL never succeeds. The strong performance of SQIRL in these stochastic environments implies both that the effective horizon of most of the environments is low and that our regression oracle assumption is met by the neural networks used in SQIRL. Furthermore, the strong relationship between the performance of SQIRL and that of deep RL algorithms suggests that deep RL generally succeeds using the same properties.
These empirical results, combined with our theoretical contributions, show that the effective horizon and the SQIRL algorithm can help explain when and why deep RL works even in stochastic environ- ments. There are still some environments in experiments where SQIRL fails while PPO DQN succeeds, suggesting lines of inquiry for future research to address. However, we find that SQIRL's performance is as similar to PPO and DQN as their performance is each other's, suggesting that SQIRL and the effective horizon explain a significant amount of deep RL's performance.
2

---

Published as a conference paper at ICLR 2024
T f arg max Q1
81
81
81
R1 arg max, Q1
Q Ri + 1/2
Q1
(1
[1
Q1
Q REGRESS V2)
1/2 + max. Q2
1/2 + max. Q2
Q2 AvG(y')
Q2
02
22
42
Q2 REGRESS(Y")
y' T R
R
(a) The GORP algorithm.
(h) The
Figure We introduce shallow Q-iteration via reinforcement learning (SQIRL) algorithm, which uses random exploration and function approximation to efficiently solve environments with low stochastic effective horizon. SQIRL is generalization of the GORP algorithm (Liddlaw el al. 2023) to stochastic environments. In the figure, both algorithms are shown solving the first timestep of TQVI-solvabl MDP. The GORP algorithm (left) uses random rollouts estimate the random policy's Q-values at the leaf nodes "search tree" and then backs up these values to the root node. It is challenging to generalize this algorithm to stochastic environments because both the initial state and transition dynamics are random. This makes it impossible to perform the steps of GORP where it averages over random rollouts and backs up values along deterministic transitions. SQIRL replaces these steps with regression of the random policy's 's Q-values at leaf nodes and fitted Q-iteration (FQI) for backing up values, allowing to efficiently learn in stochastic environments.
SETUP AND RELATED WORK
We consider the setting of episodic Markov decision process (MDP) with finite horizon. The MDP comprises horizon T E N, states E S, actions E A. initial state distribution (s1),,, transitions Pr ( | St, at), and reward (s(s,, ae) for [T], where [n] denotes the set {L...., n... We assume that A = |A| 2 2 is finite. While we do not explicitly consider discounted MDPs, our analysis easily extendable to incorporate a discount rate.
An RL agent interacts with the MDP for number of episodes, starting from a state 81 ~ p(s1)- At each step & E [T] of an episode, the agent observes the state 8t, picks an action de, receives reward R(st, at), and transitions to the next state S1+1 p( 1 St, 0z). A policy æ is a set of functions T1,
Te : S + A(A), which defines for each state and timestep a distribution x.(a s) over actions. If policy is deterministic at some state, then with slight abuse of notation we denote (s)) to be the action taken by Ne in state We assume that the total reward E (s a)) bounded almost surely in [o, 1]; any bounded reward function can be normalized to satisfy this assumption.
Using a policy to select actions in an MDP induces a distribution over states and actions with at ~ Te(: 8.). We use Px and F.z to refer the probability measure and expectation with respect to this distribution for particular policy æ. We denote a policy's Q-function Q S x A - IR and value function V S - R for each [T']. defined as:
I (s,(s, a) Ex ET=r (sv, ar)
(T) ET= Re ar) st
s,
Let J(x) = Fsg~p((s)) (VT denote the expected return of policy π. The objective of an RI. algorithm is to find an e-optimal policy, i.e., one such that ((T) 2 J - where J = max, [[T").
Suppose that after interacting with the environment for n timesteps (i.e., counting one episode as T' timesteps), an RL algorithm returns policy π". We define the (c, sample complexity Ne.5 of RI. algorithm as the minimum number of timesteps needed to return an c-optimal policy with probability at least 1 - 8, where the randomness is over the environment and the RL. algorithm:
No.5 = min {n E N P(((T 2 J - 2 1- 5).
2.1 RELATED WORK
As discussed in the introduction, most prior work in RL theory has focused finding strategic exploration- based RL algorithms which have minimax regret or sample complexity bounds (Jiang
et al. 2017 Azar al. 2017 Jin et al. 2018 2019 Sun et al. 2019 Yang al. 2020 Dong al.
3

---

Published as a conference paper at ICLR 2024
2020
Domingues al. 2021p, i.e., they perform well in worst-case environments. However, since the worst-case bounds for random exploration are exponential in the horizon (Koenig & Simmons,
1993 Jin et al. 2018), minimax analysis cannot explain why random exploration works well in prac- tice. Furthermore, while strategic exploration has been extended to broader and broader classes of
function approximators (Jin al. 2021 Du et al. 202T Foster al.] 2021 Chen et al.. 2022), even the broadest of these still requires significant linear or low-rank structure in the environment. This also limits the ability of strategic exploration analysis to explain or improve on practical deep RL algorithms that use neural networks to succeed in unstructured environments, While some work has theoretically analyzed random exploration (Liu & Brunskill [019 Dann et al. 2022) and more gen- eral function approximators (Malik et al., 2021) in RI. Laidlaw et al. (2023) show that the sample complexity bounds these papers fail to explain empirical RL performance even in deterministic environments.
The SQIRL algorithm is partially inspired by fitted Q-iteration (FQI) (Ernst et al. 2005) and previ-
ous analyses of error propagation in FQI (Antos et al. 2007 Munos& & Szepesvári 2008). While FQI has been analyzed for planning (Hallak et al. (023) or model-based RL (Argenson & Dulac-Armodd
2021), our analysis is novel because it uses FQI in model-free RL algorithm which leverages the
effective horizon assumption to perform well in realistic environments. SQIRL is also related to lookaheud, which [Bertsekas] (2020) 2022) suggests often quickly converges to optimal policy be- cause it is equivalent to a step of Newton's 's method for finding a fixed-point of the Bellman equation Kleinman 1968) Puterman & Brumelle 1979). However, lookahead is mainly used in model-based settings and/or deterministic environments, By showing that a model-free algorithm (SQIRL) can approximate lookahead, we find that similar principles underly the success of model-free deep RL.
THE STOCHASTIC EFFECTIVE HORIZON AND SQIRL
We now present our main theoretical findings extending the effective horizon and GORP algorithm to stochastic environ- ments. The effective horizon was motivated in Laidlaw al.] (2023) by surprising property that holds in many determin- istic MDPs: acting greedily with respect to the Q-function of the random policy, i.e. n gand {a x) = 1/A Vs, a, i,, gives an optimal policy. Even when this property doesn't 't hold, the authors find that applying few steps of value iteration to the random policy's Q-function and then acting greedily is often optimal; they call this property s-QVl-solvbiility We be- gin by investigating whether this property holds in common stochastic environments.
PPO fails
Number of MDPs
75
PPO succeeds
50
25
26
Min. value of & s.t. acting greedily on Q² achieves 295% optimal return
To define A-QVi-solvabillity we introduce some notation. One step of Q-value iteration transforms Q-function Q to Q' = =QI((Q). where
Figure 2: Among sticky-action versions of the MDPs in the BRIDGE dataset, more than half can be approximately solved by acting greedily with respect to the random policy's 's Q-function (k 1): many more can be by applying just a few steps of Q-value iteration before acting greedily (2 < k S 5). When k is low, observe that deep RI. algorithms like PPO are much more likely solve the environment.
(se,, a+) Re(St, (e))t),a)= + Fasty [maxas.A Q++1 (S141, a)]
We also denote by II()) the set of policies which act greedily with respect to the Q-function Q; that is,
(Q) = Vs,t (s) E arg max (c(ssa)) }
Furthermore, we define a sequence of Q-functions Q!.....''' Q" by letting Q1 = QTe be the Q-function of the random policy and Qi+1 QVI(Q)).
Definition 3.1 (k-QVI-solvable). We say an MDP is h-QVI-solvable for some k E [T] if every policy in (I())) optimal.
If acting greedily the random policy's 's Q-values is optimal, then an MDP is I-QVI-solvable; k- t-QVI-solvabillit extends this to cases where value iteration must be applied to the Q-function first.
To see if stochastic environments are commonly k-QVi-solvable for small values of k, we structed sticky-action versions of the 155 deterministic MDPs in the BRIDGE dataset (Laidlaw et all] 2023). Sticky actions are common and effective method for turning deterministic MDPs into
4

---

Published as a conference paper at ICLR 2024
stochastic ones (Machado et al. 2018) by introducing 25% chance at each timestep of repeating the action from the previous timestep. We analyzed the minimum values of & for which these MDPs approximately 6-QVI-solvable, i.c., where one can achieve at least 95% of the optimal return (measured from the minimum return) by acting greedily with respect to Q*. The results are shown in Figure 2 Many environments approximately k-QVI-solvable for very low values of k;; more than half are approximately I-QVI-solvable. Furthermore, these are the environments where deep RL algorithms like PPO are most likely find an optimal policy, suggesting that k-QVi-solvbbility is key to deep RL's success in stochastic environments.
While many of the sticky-action stochastic MDPs created from the BRIDGE dataset are k- --QVI- solvable for small k, this alone is not enough to guarantee that random exploration can lead to efficient RI.. Laidlaw al. (2023) define the effective horizon by combining & with a measure of how precisely Q" needs to be estimated to act optimally.
Definition 3.2 (k-gap). If an MDP k- t-QVI-solvable. we define its k-gap as A = inf (T))) mmaxa EA Q (2, a²) - mgagagarmax max, Q+ (s.
Intuitively, the smaller the k-gap, the precisely algorithm must estimate Q* in order act optimally in an MDP which is k-QVI-solvable. We can now define the stochastic effective horizon, which we show is closely related to the effective horizon in deterministic environments:
Definition 3.3 (Stochastic effective horizon). Given & [T). define HA = k + 1 if an MDP is k- M--VV--solvable and otherwise H₁ = xc. The stochastic effective horizon is H = ming Hg.
Lemma 3.4. The deterministic effective horizon H bounded
H S ming [Ak + log O (log (T [=]]
Furthermore, if an MDP is k--QVI ----vllllvaaee, then with probability least 1 - 6, GORP will return an optimal policy with sample complexity at most O A fh. log (TA/))).
We defer all proofs to the appendix. Lemma 3.4 shows that our definition of the stochastic effective horizon is closely related the deterministic effective horizon definition: it is upper-bound up to logarithmic factors. Furthermore, it can bound the sample complexity of the GORP algorithm in deterministic environments. The advantage of the stochastic effective horizon definition is that does not rely on the GORP algorithm, but is rather defined based on basic properties of the MDP; thus, equally applies to stochastic environments. However, it still unclear how a low effective horizon can lead to provably efficient RL in stochastic MDPs.
3.1 SQIRL
Algorithm The greedy over random policy (GORP) algorithm, used define the effective horizon in de- terministic environments.
To show that the stochastic effective hori- zon can provide insight into when and why deep RL succeeds, we introduce the shal- low Q-iteration via reinforcement learn- ing (SQIRL) algorithm. Recall the two theory-practice divides aim to bridge: first, understanding why random explo- ration works in practice despite being ex- ponentially inefficient in theory; and sec- ond, explaining why using deep neural net- works for function approximation is fea- sible in practice despite having little the- oretical justification. SQIRL. is designed to address both of these. generalizes the GORP algorithm to stochastic environ- ments, giving sample complexity exponen- tial only in the stochastic effective horizon H rather than the full horizon T. It also allows the use of a wide variety of function approximators that only need to satisfy relatively mild conditions; these satisfied by neural networks and many other function classes.
1:
procedure GORP(K, m) for 1....., do
2:
3:
for amstk-1 A
4:
sample m episodes following Ti,..., ,. then actions a1n+k-1. and finally grmnd
5:
Qi(8,, 11) + + Ei ((((()))
6:
end for
7:
(s <- arg max.;Ed
max 1a EAt--
Qi(s,, as a a141148-1).
8:
end for return
9:
end procedure
The GORP algorithm (Algorithm and Figure Ia] is difficult to generalize to the stochas- tic case because many of its components specific deterministic environments. GORP learns
GORP
5

---

Published as a conference paper at ICLR 2024
Algorithm 2 The shallow Q-iteration via reinforcement learning (SQIRL) algorithm.
1:
procedure SQIRL(K, m, REGRESS)
2:
for 1,.... do
3:
Collect m episodes by following m. for t < i and क rand thereafter to obtain ((s), vd)
4:
Qi++-1 <- RECRESS( (( (( 1. Ei=ith-1 (s a())
Σ
5: for 1 = + 2..... i do
6:
Q Qitk-r t REGRESS(((S) di Re(s), a.)) m 1:41-
7: end for
8: Define my by Ti(s) +- arg max, Q.
9: end for
10: return Ti....;77?
11: end procedure
a sequence of actions that solve a deterministic MDP by simulating a Monte Carlo planning al- gorithm. At each iteration, it collects m episodes for each k-long action sequence by playing the previous learned actions, the k-long action sequence, and then sampling from π rand Then, it picks the action sequence with the highest mean return across the episodes and adds its first action to the sequence of learned actions.
At first, it seems very difficult to translate GORP the stochastic setting. It learns open-loop sequence of actions, while stochastic environments can only be solved by closed-loop policy. also relies on being able repeatedly reach the same states estimate their Q-values, which in stochastic MDP is often impossible due to randomness in the transitions.
Regressing the random policy's Q-function To understand how overcome these challenges, start by considering the first iteration of GORP (i = 1) when k = 1. In this case, GORP simply estimates the Q-function of the random policy (Q' QT""") the fixed initial state 81 for each action as an empirical average over random rollouts. The difficulty in stochastic environments is that the initial state $1 is sampled from distribution p(s1) instead of being fixed. How can we precisely estimate Q' (s1, a) over variety of states and actions when we may never sample the same initial state twice? Our key insight to replace an average over random, rollouts with regression of the Q-function from samples of the form ($1, 41, V). where y >'=> Rs(s,, at). Standard regression algorithms attempt to estimate the conditional mean Ely $1, aI, Since this case Flyy 81, a1] = (i 01), if our regression algorithm works well then it should output Q x Q].
(t).
If we can precisely regress Q ~ QJ then for most states 81 we should have arg max. (s (a)),,))=)))) C arg max, Q a). This, combined with the MDP being 1-QVI-solvable, means that by setting Ti (s1) E arg max, Q (s1, a). æj should take optimal actions most of the time. If we fix x for the remainder of training, then this means there is a fixed distribution over 82, meaning we can also regress Q3 Q2 and thus learn T2, and so on for TT...., TT-
Extending to & - steps of Q iteration While this explains how to extend GORP to stochastic environments when & = 1, what about when & >> 1? In this case, GORP follows the first action of the k-action sequence with the highest estimated return. However, in stochastic environments, it rarely makes sense to consider fixed k-action sequence, since generally after taking one action the agent must choose its next action the specific state it reached. Thus, again it is unclear how to extend this part of GORP to the stochastic case. To overcome this challenge, we combine two insights. First, we can reformulate picking the (first action of the) action sequence with the highest estimated return as a series of Bellman backups, shown in Figure la
Approximating backups with fitted Q iteration Our second insight is that we can imple- ment these backups in stochastic environments via fitted-Q iteration (Ernst et al. 2005). which estimates Q by regressing from samples of the form (st, ae y,,y). where y (s a;) + maxa, EA Q (St+1, d++1). Thus, we can implement the - backups of GORP by perform- ing k steps of fitted-Q iteration. This allows to extend GORP to stochastic environments when k > 1. Putting together these insights gives the shallow Q-iteration via reinforcement learning (SQIRL) algorithm, which is presented in full Algorithm 2
Regression assumptions
To implement the regression and FQI steps, SQIRL uses a regression
oracle (( a aa. y )))) which takes as input dataset of tuples (s), a² yy) for j E [m]

---

Published as a conference paper at ICLR 2024
Setting
Sample complexity bounds
Strategic exploration
SQIRL
Tabular MDP
O(TSA/22 ((T)812)
SA SA /c)
Linear MDP
O(ETS O(
Q-functions with finite pscudo -iuudd-i
Table I: A comparison of our bounds for the sample complexity of SQIRL with bounds from the literature on
strategic exploration (Azar al. [011 Jin et al. [0018] [02T] CChen al. 2022). SQIRL can solve stochastic MDPs with a sample complexity that exponential only the effective horizon Hx- Since SQIRL only requires a regression oracle that can estimate Q-functions, it can be used with a broader range function classes, including any with finite pseudo-dimension.
and outputs function Q S A - (0, 1] that aims to predict Ely s, a]. In order to analyze the sample complexity of SQIRL, we require the regression oracle to satisfy some basic properties, which we formalize in the following assumption.
Assumption 3.5 (Regression oracle conditions). Suppose the codomain of the regression oracle REGRESS(-) is H. Define V = (V(s) = maxae Q(s, a) Q E H} as the class of possible value functions induced by outputs of REGRESS. We assume there are functions F (0. 1] (0, o0) and
G: (o) x (0, 1] (0, oo) such that the following conditions hold.
(Regression) Let Q = Qi for any t. E [T]. Suppose a dataset {(s a. ()) sampled i.i.d. from a distribution such that y E [0, 1] almost surely and Eply s,a] Q(s, a). Then with probability greater thun 1 - 8 over the sample,
ED (i(((0s.)) Q(+ ((s)a))² a < 0 logg F(5))
where =RRGGRESS( (((s) a ,,,,") ()))
m
(Fitted Q-iteration) Let Q = Qi for any t E [T- and E [k: - 1]; define (s) = maxacA (8,)), Suppose a datasel {(8,a, a, (a,8))) 8)) is sampled i.ddd from distribution D such that 8' ~ Pel- 8,a). Then with probability greater than 1 - 5 over the sample, we have for all V. E V uniformly,
Ed[(((s,a) ((5, saLD -(6))) +0(v log m
G(a, 8))
where Q ((AREESS(((()))))))) (s(s), + (s'))))
While the conditions in Assumption 3.5 may seem complex, they are relatively mild. The first con- dition simply says that the regression oracle can take i.i.d. unbiased samples of the random policy's 's Q-function and accurately estimate it in-distribution. The error must decrease as ((F(5)/m) as the sample size increases for some F()) which depends on the regression oracle. The second condi- tion is a bit more unusual. It controls how error propagates from an approximate value function at timestep t + 1 Q-function estimated via FQI from the value function at timestep t. In particular, the assumption requires that the root mean square (RMS) error in the Q-function be at most a times the RMS error in the value function, plus an additional term of O( VG(a, 8)/m) where G(a, 8) can again depend on the regression oracle used.
In Appendix A show that broad class of regression oracles satisfy Assumption 3.5 including least-squares regression in tabular MDPs, linear MDPs, and MDPs whose Q-functions are contained in hypothesis class of finite pseudo-dimension. The latter case even includes MDPs whose Q- functions are representable by neural networks. For example, in linear MDPs, both conditions are satisfied with a and F(8) G(L, 6) O(d + log(1/8)).
Given a regression oracle that satisfies Assumption 3.5 we can prove our main theoretical result: the following upper bound on the sample complexity of SQIRL.
Theorem 3.6 (SQIRL sample complexity). Fix a 2 1, 8 (0, and c (0. 1]. Suppose REGRESS satisfies Assumption 3.5 and let D F( F(g)) + G(a, kT). Then if the MDP is k- X-QVl-solvablle for some k E [T), there is a univeral constant C such that SQIRL (Algorithm 2 will return an e- optimal policy with probability least 1 if 2T A² complexity of SQIRL is
log
ATAD
Thus, the sample Are
A
N SQIRL. Ö 0KTT5 AAt AAaD log log(aD)//e) 6,8
(1)
7

---

Published as a conference paper at ICLR 2024
Algorithm
Envs. solved
Algorithms
Sample complexity comparison
Correl.
Median ratio
PPO
96
DQN
76
SQIRL SQIRL PPO
PPO
0.83
1.38
SQIRL
69
DQN
0,56
1.00
GORP
26
DQN
0.48
0,59
Table 2: The number of sticky-action BRIDGE environments (out 155) solved by four RL algorithms. Our SQIRL algo- rithm solves more than 2/3 of the environ- ments that PPO does and nearly as many DQN. Meanwhile, GORP (Laidlaw al. 2023) fails most because it not designed for stochastic anvironments.
Table 3: A comparison of the empirical sample complexi- ties SQIRL, PPO, and DQN in the sticky- action BRIDGE environments. SQIRL's 's sample complexity has higher Spearman correlation with PPO and DQN than they do with each other. Furthermore, SQIRL. tends to have just slightly worse sample complexity then PPO and bit het- ter sample complexity than DQN.
To understand this bound on the sample complexity of SQIRL, compare it to GORP's sample com- plexity (Lemma 3.4). Like GORP, SQIRL has sample complexity exponential in only the effective horizon. As shown Appendix A in many cases is the pseudo-dimension of the hypothesis class used by the regression oracle. Then, SQIRL's 's sam- ple complexity of SQIRL is (KT'S d/e) log factors, just 7 d// factor more than the sample complexity of GORP. The factor of d is necessary because SQIRL must learn Q-function that generalizes over many states, while GORP can estimate the Q-values at single state in deter- ministic environments. The dependence on the desired suboptimality is standard for stochastic environments, e.g., see the strategic exploration bounds in Table I While our sample complexity bounds are exponential in k. in practice & is quite small. Figure 2 shows many environments can be approximately solved with k and we run all experiments in Section 4 with k S 5.
set 1 and D x d- (T /8), where d
4 EXPERIMENTS
While theoretical results strongly suggest that SQIRL and the stochastic effective horizon can explain deep RL performance, we also want to validate these insights empirically. To do so, we implement SQIRL using deep neural networks for the regression oracle and compare its performance to two common deep RL. algorithms, PPO (Schulman et af.] 2017) and DQN (Mnih et al.) 2015). We evaluate the algorithms in sticky-action versions of the BRIDGE environments from Laidlaw et al. (2023). These environments are a challenging benchmark for RL algorithms because they are stochastic and have high- nigh-dimensional states that necessitate neural network function approximation.
In practice, we slightly modify Algorithm for use with deep neural networks. Following standard practice in deep RL, we use single neural network to regress the Q-function across all timesteps, rather than using separate Q-network for each timestep. However, we still "freeze" the greedy policy at each iteration (line 8 in Algorithm [ by storing a copy of the network's weights from future iterations. Second, we stabilize training by using a replay buffer to store the data collected from the environment and then sampling batches from implementation is still entirely based around iteratively estimating Q* by using regression and fitted-Q iteration.
iteration and using it for acting on timestep
it to train the Q-network. Note that neither of these changes the core algorithm:
In each environment, we PPO, DQN, SQIRL, and GORP for 5 million timesteps. We use the Haale-Baseelies33 implementations of PPO and DQN (Raffin et al. 202T). During training, we evaluate the latest policy every 10,000 training timesteps for 100 episodes. We also calculate the exact optimal return of the sticky-action environments using the tabular representations from the BRIDGE dataset. If the mean evaluation return of the algorithm reaches the optimal return, we consider the algorithm to have solved the environment. We say the empirical sample complexity of the algorithm in the environment the number of timesteps needed reach that optimal return.
Since SQIRL and GORP take parameters k and m. we need to tune these parameters for each en- vironment. For each E 2,, 4,4,5, 5). we perform a binary search over values of m to find the smallest value for which the algorithm solves the environment. We also slightly tune the hyperpa- rameters of PPO and DQN; see Appendices C and D for all experiment details and results. We do not claim that SQIRL is as practical as PPO or DQN, since it requires much more hyperparameter tuning; instead, we mainly see SQIRL as a tool for understanding deep RL.
8

---

Published as a conference paper at ICLR 2024
Beam Rider
Breakout
Pong
Qbert
Seaquest
Space Invaders
5k
20
10k
lk
100
5k
-20
0
0
10M
10M
10M
10M
10M
10M
SQIRL
PPO
DQN
GORP
Figure 4: The performance of SQIRL standard full-length Atari environments is comparable to PPO and DQN. This suggests that PPO and DQN succeed in standard benchmarks for similar reasons that SQIRL suc- ceeds. Thus, our theoretical analysis of SQIRL based on the effective horizon can help explain deep RL performance in these environments.
PPO samp. complex.
The results of our experiments are shown in Tables 2 and and Figure 3 Table lists the number of environments solved by each algorithm. GORP barely solves any of the sticky-action BRIDGE environments, validating that our evaluation environments are stochastic enough that function approximation is necessary solve them. In contrast, we find
10a
10a
10
that SQIRI solves about two-thirds as many environments as PPO and nearly as many as DQN. This shows that SQIRL is not simply a useful algorithm in theory-it can solve wide variety of stochastic environ- ments in practice. It also suggests that the assumptions we introduce in Section hold for RL in realistic environments with neural network function approximation. If the effective horizon was actually high, or if neural networks could not effectively regression the random policy's Q-function, we would not expect SQIRL to work as well as it does.
10
10
10
samp, complex.
10
10s
DQN DQNsamp
10
Table 2 and Figure 3 compare the empirical sample complexities of PPO, DQN, and SQIRL. In Table [ we report the Spearman corre- lation between the sample complexities of each pair of algorithms in the environments they both solve. We find that SQIRL's sample com- plexity correlates better with that of PPO and DQN than they correlate with each other. We also report the median ratio of the sample com- plexities of each pair of algorithms to see if they agree in absolute scale. We find that SQIRI. tends to have similar sample complexity to both PPO and DQN; typically performs about the same as DQN and slightly worse than PPO. The fact that there is close match between the performance of SQIRL and deep RL algorithms- has low sample complexity, so does SQIRL, and vice versa suggests that our theoretical explanation for why SQIRL succeeds is also a good explanation for why deep RL succeeds.
10a
10
10
SQIRL samp. complex.
Figure 3: The empirical sam- ple complexity of SQIRL cor- relates closely with that of PPO and DQN, suggesting that our theoretical analysis of SQIRL is powerful tool for understanding when and why deep RL works stochastic environments.
deep RL
Full-length Atari games Besides the BRIDGE environments, which have relatively short horizons, also compared SQIRL to deep RL algorithms in full-length Atari games. We the standard Atari evaluation setup from as this does not fit into our RL formalism. A comparison of the learning curves for SQIRL, GORP, PPO, and DQN shown in Figure 4 GORP performs poorly, but SQIRL performs comparably to PPO and DQN: it achieves higher reward than both PPO and DQN in three of the six games and worse reward than both in only two. This implies that our conclusions from the experiments in the BRIDGE environments also applicable more typical RL benchmark environments.
except that we disable episode restart on loss of life
5 CONCLUSION
We have presented theoretical and empirical evidence that SQIRL and the effective horizon can help explain why deep RL succeeds in stochastic environments. Previous theoretical work has not sat- isfactorily explained why random exploration and complex function approximators should enable efficient RL. However, sumption to close the leverage regression, fitted Q-iteration, and the low effective horizon gap. We hope this paves the way for work that further advances understanding of deep RL performance builds improved algorithms based our analysis.

---

Published as a conference paper at ICLR 2024
ETHICS STATEMENT
The main goal of our research is to better understand theoretically when and why deep reinforcement learning succeeds and fails in practice. Since our work is not immediately useful for applications and instead aimed at scientific understanding, we do not believe there are immediate ethics concerns.
REPRODUCIBILITY STATEMENT
We include details throughout the paper that can be used reproduce results. In particular, Section 4 and Appendix C contain the details of our empirical experiments. Section B contains the proofs of our theoretic results.
ACKNOWLEDGMENTS
We would like to thank Sam Toyer for feedback on drafts as well as Jiantao Jiao for helpful discus- sions.
This work was supported by grant from Open Philanthropy to the Center for Human-Compatinn Artificial Intelligence UC Berkeley. Cassidy Laidlaw supported by an Open Philanthropy Al Fellowship.
REFERENCES
András Antos, Csaba Szepesvári, and Rémi Munos. Fitted Q-iteration in continuous action- space MDPs. Advances Neural Information Processing Systems, volume Curran As- sociates, Inc., 2007. URL https: http::/:se/pppprss.oooooc.ooaaaa nips wwtpppppp..ppppr...ecccepppeaeee
files/paper/2007/ iat///4c11122dd4432660008881-1-1 Awt.aaattttttttaaaaaa........a.t
Arthur Argenson and Gabriel Dulac-Aroodd. Model-Based Offline Planning, March 2021. URL
http://arxiv. org/ abt///aas/20000 05556 #rXiv:2008.05556 [es, eess, stat].
Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax Regret Bounds for Rein- forcement Learning. arXiv:/703.0544 [cs, stat], July 2017. URL http::/aaxiv..o arXiv: 1703.05449.
abs/ 1703. 05449
Peter L. Bartlett, Nick Harvey, Chris Liaw, and Abbas Mchrabian. Nearly-tight VC-dimension and pscudodimension bounds for piecewise linear neural networks, October 2017. URL http:
/100/1173.0000 02930 arXiv:1703.02930 [cs].
Dimitri Bertsekas. Rollout, Policy Iteration, and Distributed Reinforcement Learning. Athena Sci-
entific, Belmont, Massachusetts, first edition edition, August 2020. ISBN 178-1-886629-077
Dimitri P. Bertsekas. Lessons from AlphaiZero for Optimal, Model Predictive, and Adaptive Control. Athena Scientific, March 2022. ISBN 978-1-886529-17-55
Zixiang Chen, Chris Junchi Li, Huizhuo Yuan, Quanquan Gu and Michael Jordan. A General Framework for Sample-Efficcien Function Approximation Reinforcement Learning. September 2022. URL
Chris Dann, Yishay Mansour, Mehryar Mohri, Ayush Sekhari, and Karthik Sridharan. Guarantees for Epsilon- Reinforcement Learning with Function Approximation. In Proceedings of the 39th International Conference on Machine Learning, pp. 4666-4689, PMLR, June 2022. URL https: ftttps://proceedingge mlr wrw.sresspeee.... / vv da/nnn2 html ISSN: 2640-3498.
Omar Darwiche Domingues, Pierre Ménard, Emilie Kaufmann, and Michal Valko. Episodic Re- inforcement Learning in Finite MDPs: Minimax Lower Bounds Revisited. In Proceedings of the 32nd International Conference Algorithmic Learning Theory, pp. 578-598, PMLR, March 2021. URL Intpps://proceecingg mlr. press./e////ee.. / vv13// domingues22a.
html ISSN: 2490-3498.
10

---

Published as a conference paper at ICLR 2024
Kefan Dong, Jian Peng, Yining Wang, and Yuan Zhou. Root-n-Regre for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank. In Proceedings of
Thirty Third Conference Learning Theory, pp. 1554-1557. PMLR, July 2020. http::s:
//proceedingg ngs...... ml www.m...........mmmmmm. 220g220a/ html
ISSN: 2640-3498.
Simon Du, Sham Kakade, Jason Lee, Shachar Lovetr, Gaurav Mahajan, Wen Sun, and Ruosong
Wang. Bilinear Classes: A Structural Framework for Provable Generalization in RI.. Proceed- ings of the 38th International Conference Machine Learning, pp. 2021. URL 3498.
PMLR, July ISSN: 2640-
mlr. http://ws.......aa..eeeee.eeeeee press/v139/du2less
Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-Based Batch Mode Reinforcement Learn- ing. Journal of Machine Learning Research, 6(18)50035556 2005. ISSN 1533-7928. URL
http://
html
Lasse Espeholt, Hubert Soyer, Remi Munos, Karen Simonyan, Volodymir Mnih, Tom Ward, Yotam Doron, Vlad Firoiu, Tim Harley, Tain Dunning, Shane Legg, and Koray Kavukcuoglu. IM- PALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Leamer Architectures, June 2018. Uttp://://aaaet wrw.vv.rrr//aae
01561 arXiv:1802.01561 [cs].
Dylan J. Foster, Sham M. Kakade, Jian Qian, and Alexander Rakhlin. The Statistical Complexity of Interactive Decision Making, December 2021. URL http:://axxitii org/ wtwpw//w.rr/a//////uee abt///bs//111 13487 arXiv:21 12.11322778777 [cs, math, stat].
Assaf Hallak, Gal Dalal, Steven Dalton, luri Frosio, Shie Mannor, and Gal Chechik. Improve Agents without Retraining: Parallel Tree Search with Off-Policy Correction, February 2023. URL http: /ttpg//bbb.a.. 2217 .07115 arXiv:2107.01715 [es].
Nan Jiang. Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. Con- textual Decision Processes with low Bellman rank are PAC-Lcarnable. In Proceedings of the 34th International Conference on Machine Learning, pp. 1704-1715 PMLR, July 2017. URL ISSN: 2640-3498.
mlr. prwpsreesssseee /v70 Langl 1 7 html
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. Is Q-learnngg Provably Ef- ficient? /807.0000 [cs, math, stat), July 2018. URL /
1807. 03765
arXiv: 1807.03765.
Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably Efficient Reinforcement Learning with Linear Function Approximation. arXiv:1907.05333 [cs, math, stat], August 2019. org/ abs//b07..11 05388
URL htthhttp//aaat
arXiv: 1907.05388.
Chi Jin, Qinghua Liu, and Sobhan Miryoosefi. Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms. In Advances in Neural Information Processing Systems, volume 34, pp. 13406-13418. Curran Asso-
ciates, Inc., 2021. URL http///ttpps/pppcceddg....oot http://ceeeang.eeeriiree...er//p wttp:eewwrrrppepppeeeeeeeee pc/paper//02////att ( Abst:eeeebbbbb-tttttttttetc
Abst html
D. Kleinman. On an iterative technique for Riccati equation computations. Transactions on Automatic Control, (3(1):114-115
IEEE February 1968. ISSN 1558-
2523. doi: 10.1109/TAC.1968.I 1098822.
URL hatps::/eeexxxorre leee.
org htt.a//cccccccceee////0//aaaaaae
-wFFs77qpcyyyyVooFFFFr Conference Name: IEEE Transactions on Automatic
Control.
Sven Koenig and Reid G. Simmons. Complexity analysis of real-time reinforcement learning. In Proceedings of the eleventh national conference on Artificial intelligence, AAAI'93, pp. 99-105, Washington, D.C., July 1993. AAAI Press. ISBN 978-0-262-51077
Vladimir Koltchinskii. Local Rademacher Complexities and Oracle Inequalities in Risk Mini- mization. The Annals of Statistics, 34(6):2533-266 -2556 2006. ISSN 5364. URL h
7/www. - jstor, htt.orrrrrr//tolee/e55ee5
Publisher: Institute of Mathematical Statisties.

---

Published as a conference paper at ICLR 2024
Cassidy Laidlaw, Stuart Russell, and Anca Dragan. Bridging RL Theory and Practice with the Effective Horizon. In Advances in Neural Information Processing Systems, 2023. URL http:
// //axxi..rr/aabb..............//a abs/ 2004. 09853 arXiv:2304.09853 [cs, stat].
Yao Liu and Emma Brunskill. When Simple Exploration is Sample Efficient: Identifying Sufficient Conditions for Random Exploration to Yield PAC RL Algorithms, April 2019. URL http:
//arxiv.org/aallib.. /00.. 09045 arXiv:1805.0900 [cs, stat].
Marlos C. Machado, Marc G. Bellemare, Erik Talvitie, Joel Veness, Matthew Hausknecht, and
Michael Bowling. Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents. Journal of Artificial Intelligence Research, 61:523-562, 2018. URL
https: //ww:. jair org/ index http://alrr/rrticl/////////////a
Dhruv Malik, Aldo Pacehiano, Vishwak Srinivasan, and Yuanzhi Li. Sample Efficient Reinforce- ment Learning In Continuous State Spaces: A Perspective Beyond Linearity. In Proceedings of the 38th International Conference on Machine Learning, pp. 7412 7422. PMLR, July 2021. URL ISSN: 2640-3498.
ml wtt.://.www....ss...mmm wwwppeesssvii...
1ikllc html
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Belle- mare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wier- stra, Shane Legg, and Demis Hassabis. -lvell control through deep reinforcement learning. Nature, 518(554)))55995533 February 2015. ISSN 1476-4687. doi: 10. n0.1038/nature1420
URL
https:: //ww:::/wwww... www.uatuuuee.em com/ a rt i ceceleeeeec eesnaatureeeeeeeeeeeeeeeeeaaeaas e 12336
mandiera_abtesse Cg_type: Nature Research Journals Number: 7540 hiiarryatypps Research Publisher: Nature Publish-
ing Group Subject.term: Computer science Subject.term.id computer-science.
Rémi Munos and Csaba Szepesvári. Finite-Time Bounds for Fitted Value Iteration. Journal of Machine Learning Research, 9(77):15-857, 2008. ISSN 1533-7928. URL http: jmlr.
ptg/ppapers////mmnoss.
html
Martin L. Puterman and Shelby Brumelle. On the Convergence of Policy Iteration in Stationary
Dynamic Programming. Mathematics of Operations Research, 4(1):60-65 69, 1979. ISSN 0364-
765X. URL / http://ww...ttooorrrraaaaaaaaa//
Publisher: INFORMS.
Antonin Raffin, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dor- mann. Stable-baselines:; Reliable reinforcement learning implementations. The Journal of Ma- chine Learning Research, (231):12348-122
2021. URL /ttt:s::/dd.cooo org/doi/
abs/100 /te./1.55550 555.555533546225 35455883555555 3546526
Publisher: JMLRORG.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal Policy Optimization Algorithms. /70 067.0664777111 [cs], August 2017. URL aatt:://aaxaiiii o
arXiv: 1707.06347.
Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based RL in Contextual Decision Processes: PAC bounds and Exponential Improvements Model-free Approaches. In Proceedings of the Seirny-Second Conference on Learning Theory, pp. 2898- 2933. PMLR, June 2019, URL https: htttps://proceecinng html ISSN: 2640-3498.
www.mmrrr.sss....mmmmmmmmmmmmmee wtw...press//////uee sun///snlgg 19..
Aad W. van der Vaart and Jon A. Wellner. Uniform Entropy Numbers. In Aad W. van der Vaart and Jon A. Wellner (eds.), Weak Convergence and Empirical Processes: With Applications to Statistics, Springer Series in Statisties, pp. 133-153. Springer, New York, NY. 1996. ISBN 978- URL ctttps://cc..org/10000
14757-2545-2. doi: 10.
978 10-11-4552 2545-225222 18
Roman Vershynin. tions in Data Science. Cambridge Series in Statistical and Probabilistic Mathemat- ics. Cambridge University Press. Cambridge, 2018. ISBN 978-1-108-41519944 doi:
High-Dimensional Probability: An Introduction with Applica-
10.1017/9781 108223559.
URL Btighdiensiioo htt.://paaaaa.///4444/aaaaaaaaa0
12

---

Published as a conference paper at ICLR 2024
Zhuoran Yang, Chi Jin, Zhaoran Wang. Mengdi Wang. and Michael I. Jordan. On Function Ap- proximation in Reinforcement Learning: Optimism in the Face of Large State Spaces, December 2020. URLbttp: / /wtpvv.ivvvvv.////v//e..//.aa www. wwwgg//b///lls 04622 arXiv:201 1.04622 [cs, math, stat].
13

---

Published as a conference paper at ICLR 2024
APPENDIX
A LEAST-SQUARES REGRESSION ORACLES
In this appendix, we prove that many least-squares regression oracles satisfy Assumption 3.5 and thus can be used in SQIRL. These regression oracles minimize the empirical least-squares loss on the training data over some hypothesis class H::
REGRESS([(s", d.)"")) = arg min
Σ (Q(s),a)) - 8¹)² QER
Proving that Assumption 3.5 is satisfied for such an oracle depends on some basic properties of H. First, we require that H of bounded complexity, since otherwise it is impossible to learn Q-function that generalizes well. We formalize this by requiring simple bound on the covering number H::
Definition A.1. Suppose H is hypothesis class of functions Q : x A + [0. We say H is VC-type hypothesis class if for any probability measure P over S A, the (P) covering number of is bounded NHH e)) s (=)", where IQ Q'Ili,(P) Er((Q(s,a) - Q'(s,
Many hypothesis classes are VC-type. For instance, if H has finite pseudo-dimension d, then it is VC-type with d d and B O(1) If H parameterized by 0 in a bounded subset of Rd and Q" is Lipschitz in its parameters, then H. is also VC-type with d = d and B = (llog(pL)), where ||0]|2 S p and L is the Lipschitz constant. See Appendix A. for more information.
Besides bounding the complexity of H. we also need it to be rich enough to fit the Q-functions in the MDP. We formalize this in the following two conditions.
Definition A.2. We say H. is k-realizable for all i E [k] and E [T]. Qi E H.
Definition A.3. We say H is closed under QVI if for any (2....,T}. Q implies that @VI(Q:) E H.
Assuming that H is k-realizable is very mild: we would expect that function approximation-based RL would not work at all if the function approximators cannot fit Q-functions in the MDP. The second assumption, that H is closed under QVI, is more restrictive. However, it turns out this is necessary for proving that Assumption 3.5 is satisfied; if H not closed under QVI, then it just results in slightly worse sample complexity bounds.
Theorem A.4. Suppose H is k-realizable and of VC-type for constants B and d. Then least squares regression over H. satisfies Assumption 3.5 with
F(6) O (dlog( (Bolog(BBrrrr + (o///)
G(a, 8) O (ABd/(a 2)) log(L/))) /(a 2)))
Furthermore, H is also closed under QVI, then can remove all (a 2) factors in G.
Theorem (proved Appendix B.3 allows us immediately bound the sample complexity bounds of SQIRL in number of settings. For instance, consider linear MDP with state-action features Φ(x, a) E Rd. We can let H = {Ô(s, a) w Φ(s, a) w TT(s,, a) E [0. V(s,a) x A). This hypothesis class is realizable for any k. closed under QVI, and of VC-type, meaning
SQIRL's sample complexity is at most ( /e). Since tabular MDPs are a special case of linear MDPs with d SA, this gives bounds for the tabular case well. Table [ shows comparison between these bounds and previously known bounds for strategic exploration.
However, our analysis can also handle much more general cases than any strategic exploration bounds in the literature. For instance, suppose H. consists of neural networks with n parameters and é layers, and say that H is k-realizable, but not necessarily closed under QVI. Then has neeudo-dimension of d = Onl O(nllog(n) (Bartlett et al. 2017) and we can bound the sample com- plexity of SQIRL by 0 /e), where we use V5.
14

---

Published as a conference paper at ICLR 2024
A.1 VC-TYPE HYPOTHESIS CLASSES
We now describe two cases when hypothesis classes are of VC-type; thus, by Theorem A.4 these hypothesis classes satisfy Assumption a.d can be used part of SQIRL.
Example A.S. We say H has pseudo-dimension d if the collection of all subgraphs of the functions H forms a class of sets with VC dimension Then by Theorem 2.6.7 of van der Vaart Wellner 1996). H. is a VC-rype class with
2(2-11 ( -0
(0((20))
2d
N(H, (2(P);) Cd(16e)
Example A.6. Suppose H. is parameterized by 0 E E Rd with 10112 S B vo. and Qa(s, a) is Lipschitz in 0, i.e.,
(s, [Q((s.a) (s- a)l - 40.0' E E.
By Corollary 4.2.13 Vershynin (018)), the e-covering number of (0 TRd 100 S B) bounded
as (1+ 2B/e 1B)22 Therefore, the e-packing number of H. is bounded as 4B/e)* (Lemma 4.2.8 of Vershynin 2018 ): this in turn implies that the packing number of is bounded identically, since any e-packing of θ is also an e-packing H, which means that the e-covering number of is also bounded as (1+ 4B/e/ AC)c). If we take Ne/t. fT. to be an L-L-vvriing of Q. then for any Qo, there must which implies for any probability measure that
be some 8' Nee such that || 11122 S e/
Ep [Qo(s, a) (s, 1/2
[[Qo(s,a) - (s, (s,aa)ll a)ll((()))
s Ep L L 0' 1/2
= -I1 0' 2| e.
Thus (Qs 0 Ne/r3 is e-covering H, H. which implies that the Lz(P) covering number of H is bounded as
(0 d)
2 (1440//)
4BL/C)==0
B PROOFS
B.1 PROOF OF LEMMA 3.4
Lemma 3.4. The deterministic effective horizon H is bounded as
H S ming [Hs + log O (log (TA*))]
Furthermore, if an MDP k-QVl-solvable, then with probability least 1 6, GORP will return an optimal policy with sample complexity at most 2 A A log (T))))).
Proof. The bound on H follows immediately from Theorem 5.4 of Laidlaw et al. (2033) by noticing that in our setting, Q and value functions are always upper- boundeduddddddd by 1. The bound the sample complexity of GORP then follows from Lemma 5.3 of Laidlaw et al. (2023).
B.2 PROOF OF THEOREM 3.6
To prove our bounds on the sample complexity of SQIRL, we first introduce a series of auxiliary lemmas.
Lemma B.1. Suppose that MDP is k-QVI solvable and we iteratively find deterministic policies Ti...., oT such that for each t. Pa (TT & arg max, Q (st, as) S e/T, where states 8t are sampled by following policies T....., Te-1 for timesteps 1 to t 1. Then n is e-optimal in the overall MDP, i.e.
((m) max J(TT)
Proof. Let E denote the event that there is some t E [T] when a, & arg max, Qf (st, a). By a union bound, we have (x) e. Now, let n= be policy in (T())) that agrees with all states and
15

---

Published as a conference paper at ICLR 2024
timesteps where (s))) arg max, (s, a). We can write & as the event that 3t [T). T(s)) * x (st), which is equivalent to under the distribution induced by т. We can now decompose ((T)
J(T)= F.xe
Re(St, an)
2 Fx
Re(se, ar)
1 P=(-E)
Ex-
Re(Se, (x)
_ P=(-E)
T
Ex
(s))
-
Pa(-E)+ Ex
Σ Re(sn E -
T a((s) Px(
Fag.
(1)
Σ
2 J(x')
Lemma B.2. Let D be a distribution over states and actions such that Po(a | 8) 1/A for all S, a E A. Then for any Q and Q S + [0, 1}. defining V(s) max Q(s, a) and V analogously, we have
ED (V(()) AED -(s,,)))((),)))
Proof. We have
Ep (V(s))v(s))
= EEp
max ((s,)((s))))))) max Q(s, aEd
aEd
(Q(s.0) - Q(5, 27
S Ep
max aEA
(Q(s,a) Q(s, 2
S ED
Σ
LaEd
Σ (0(s,a) - Q(s,aa)² 27
=AED
A
aEA
((015,a) - Q(,0((()))) (Q((s,)-Q((sa))) Q(s,a)))
= AE
where the final equality follows from the fact that Po(a 8) = 1/A.
Lemma B.3. Suppose the MDP k-QVI solvable and let n, the policy constructed by stochastic GORP at timestep i. Then with probubility at least 1 - -
Pr (s)) & arg max Of (s, so 2x A (F
(TT
+ G(a, 4) log
mA
Proof. Let all expectations and probabilities E and P be with respect the distribution of states and actions induced by following Ti..... TT- for t < i and radd thereafter. To simplify notation, write for any Q,, Q/: S x A + -00, [0, V V/
[0,
I|Q:
Q112 E (Qr(sr, ar) C1(s,, a.))))
|[V VV (Vi(s)) (=(
16

---

Published as a conference paper at ICLR 2024
Let (s) m (s, and (s) maX.e Qi (s,a) Consider the following three facts:
1. By Assumption 3.5 part I, with probability least 1 1 8/((K)),
F( (TT
log m
Qitk-1- - Qitk-11
S S
2. By Lemma B.2 for E k2,...,k}.
Vithhe-
- vittheel | 0ith 2
3. By Assumption 3.5 part 2, for any t E {I...., k 1}. with probability at least 1 - 6/(KT)
1 Qith-i| |1 S vell - 441 - |1, + V C2
G(a, RT log m
m
Note that it is key that this bound is uniform over all Vittk E V, since 6+1 estimated based on the same data used to regress Q
Vitk-t-1
Via union bound all of the above facts hold with probability at least them to recursively show for {1....,k).
- 8/T. We will combine
- 2ith0101 s (4(aVA))+ / log m
where
D = C
+
C2G(a, KT
KT
(2)
The base case i. l is true by fact 1. Now let 1e and assume the above holds for t + By facts 2 and 3,
G(a,,
4
logm
-
<a
Witk-1-1 1
E41
C2
FT
2
m
G(a, RT
4
log m
S av
1 Qc+ 1
2 V
C2
m
D log m
Diog m
I avA
m
m
D log
(A(aVA))* - 3av A +
m
< (4(aVA)*+
Dlogm
m
where the last inequality follows from A 2 and a 2 Thus, by setting 1 in 2 we see that with probability at least - 5/T.
| -02 5 30|==00
(22-2AA-1 (T) + G(a, x log m
(3)
17

---

Published as a conference paper at ICLR 2024
(T())) mrg (s;,
I Pr arg aaggmax Qf (st, a) I max Qf (s;; a)
$ Pr
la E EA s.t. ( Q (8s, a) 2 Ax/2)
Σ
Pa (109(6)))) - - 2 4x/2)
aEA
A
1
Σ
Pr ()) Qf 2 Aa/2))
A
.EA
((ot(s))s)) - () ai) 4x/2)
AP,
(
A
F.T (0)((s) - (8). 27 }
(A//2)2
A
Q Q. |
(Ax/2)2
22- Ah (F(TT) m
+ G(a, ) logmi
Here, (i) follows from Definition 3.2 of the k-gap and (ii) follows from Markov's inequality.
Theorem 3.6 (SQIRL sample complexity). Fix 2 1, 8 (0, 1). and e (0, 1]. Suppose REGRESS satisfies Assumption 3.5 and let D F( + G(a, 4). Then if the MDP is k- k-QVI-solvable for
some le E [T), there is a univeral constant C such that SQIRL (Algorithm 2 will return an c- optimal policy with probability least 1 ō if ((t A Aie
log KTaAD Thus, the sample Acc
complexity of SQIRL is
N SOIRL = = (KT 11-11)
(M A Ae D log log(aD)/c).
(1)
Proof. Given the lower bound on m, bound
log m
A 2k A
O
m
Combining this with Lemma B.3 we see that with probability at least 1 6, for all i e [T]
Pa (T((s)) & arg max Q (st, a)) S E/TT.
Thus, by Lemma B.1 is e-optimal in the overall MDP M.
B.3 PROOF OF THEOREM A.4
Theorem A.4. Suppose H is k-realizable and of VC-type for constants B and d. Then least squares regression over H. satisfies Assumption 3.5 with
F(8) (dlog( Bd) + log(1/5))
G(a, 8) = (ldlog(ABd/fl 2)) + (())))
Furthermore, H is also closed under QVI, then we can remove all (a - 2) factors in G.
Proof. Throughout the proof, we will use the notation that ||Q and V V Ev((V - V)
Q' || Epl(Q(s, Q'(ss
To do so, results least-squares regression from Koltchinskii (2006). Note that our definition VC-type classes coincides with condition (2.1) in Koltchinskii (2006). By combining Example 3 from Section 2.5 and Theorem
First, will prove the regression part of Assumption 3.5
18

---

Published as a conference paper at ICLR 2024
13 of Koltchinskil 2006), we have that for any Q(s,a) a) with Ely E (0,1),
8, Q(s,a). and for any
0- 0
2 S (1+ A) inf 100 112-00 -Ql2 +0 0 mm log
Bdm
u =+1 1
))
em
log
e "
QEH
Am
where
Q - REGRESS(((<>) a², (1)))1))
we set
c log
u == log
2 1,
then the right-hand side of is bounded as
em v I log(em)e " log(em)
log
< 6.
e + log m
Thus, plugging this value of into
we have that with probability at least 6,
- -
| - oI +0 d log
Bdm
+ log
(1+
inf QEH
(5)
m2²
For the regression condition of Assumption 0, and we can set À in 5 to obtain
3.5 have Q Qt H. Thus, inf QEH 11 - Q112
0 - 0:11 0
dllog( (Bdm) + log
m
leading to the desired bound of
(dlog((Bd) log 1
F(6) O
To the fitted Q-iteration condition of Assumption 3.5 we begin by defining norm p on V H. by
p( p ()V,Q),( (V', Q') max [IIV V2 ||Q 2'
Note that since showed in Lemma B. that
Ep (V(s)) - (s)))) S
[Q(s' d') - -''ss' (ss'''''))"
where ((s') max Q(s ((ss'aa)), V' = max e'EAA
Q''s'' d'), d'EAA
this implies that any c-over of H is also an cv A-cover of V with respect to L2(P) for any distribu- tion over s'. Thus, by the definition of VC-type classes, we have
BVA
N(V, L
(
N(H, I2()))) S
BVA
d
B
d
BvA
2d
N(V x H.p:c)s
e
Now define W [ V x H
W (v. H
Q = REGRESS ((()) R (²) [(6))))
}
By properties of packing and covering numbers, since any c-packing of W is also an e-packing of
V x H, we have
2d
2B A
N(W,pte S M(W.pee/2) M(V H. < N(V H,pp5/2)
6
Thus, let Nyy.m be 1 mcccorrinn of W with size most (2B Am Am)2d. 2d
19

---

Published as a conference paper at ICLR 2024
Fix any (V, Q Ni//m and define ((. = ([ a) + V((s) s.a]. Then by an identical
argument to with probability at least 1 - 8, for any À (0, 1/.
(1+ inf QEH s (1+
|| - +0
d log
Bdm
+ log &
mx²
We can extend this to bound on all (V, Q) E N11/m mm by dividing d by / and applying union bound. Thus, with probability at least 6, for all (V, Q) E Nisumm and any E (0, 1),
10 1 1 =
(1 (1+
inf
Q Q +0
dlog ( () + dlog( (AAm) + log 5
QEH
md²
+0 dlog BAdm
+ log 5
=(1+
inf
Q
Q
QEH
mx
Finally, we extend this to bound over all (V. Q) E W. For any (V. Q) E W. there must be some (V' Q') Nayym such that p((V, Q), (V', Q')) 1//m. Let ('(s, a) E[R((s, + V'(6))
8, a). Then
- -01 ED (Q(s,a) ('sss
ED ((s') ('()1) )) )
= ED
(V(6) - ('6)) / m
ED
where the second-to- -o-sas inequality follows from Jensen's 's inequality. Thus, by the triangle inequal- ity,
- s 0 0 +00--0// + +110' -Ql1
$ Q' - Q' | + vm
(1 |dlog
s V inf
| - -0122- +o
10'-Q'1
BBAmm)
+ log
Q'EH!
m2
for all (V, Q) E W and any x E (0, 1] with probability at least
We now consider the two possible conditions in the theorem. If H. is both k-realizable and closed under QVI, then this implies Q' E H for all (V", Q') E //1/ meaning inf @ee I1 Q'll2 0. Thus, can set x in the above bound to obtain
0 o 11@
211 0-- @/
v|] +0 d ( (BAdm)) + log mx2
showing that the FQI condition of Assumption 3.5 holds with
G(a, 5) O (dlog 0
(Bdd) log(1 log(1/8))
Otherwise, H is only k-realizable, then this implies Q H. Thus,
inf d'EH @'' - --01, < 11Q Q'll2 < V -v v/1 + vm
20

---

Published as a conference paper at ICLR 2024
This implies that
0 - - 11
0112 + Q 0112
v v/1 + + v -vl12
/dlog
BAddm
+ log m
vm
mn2
s 5 12+vAi/li v/[ +0
(1
BAdm dlog
+ log m
m2²
Setting + v1 shows that the FQI condition of Assumption 3.5 holds with
ddlog
BAd a-
+ log 1
G(a, 8) =0
(a - 2)
C EXPERIMENT DETAILS
In this appendix, describe details of the experiments from Section We the implementations of PPO and DQN from Stable-Baselines3 (Raffin et al. 2021), and in general use their hyperparam- which have been optimized for Atari games. For network archictures, we use convolutional 1 for the
neural nets similar to those used by Mnih et al. (2015). We use discount rate of Atari and Procgen environments in BRIDGE but y 0.99 for the MiniGrid environments, as oth- erwise we found that RL completely failed. We run 5 random seeds of each RL algorithm for each hyperparameter setting, recording the median reward and sample complexity.
PPO
We use the following hyperparameters for PPO:
Hyperparameter
Value
Training timesteps
5,000,000 (128, 1, 280)
Rollout length
SGD minibatch size
256
SGD epochs per iteration
Optimizer
Adam
Learning rate
2.5
10
GAE cocfficient (A)
0.95
Entropy coefficient
0.01
Clipping parameter
0.1
Value function coefficient
0.5
Table 4: Hyperparameters we for PPO.
For each environment, take the rollout length from {128, 1280), found this was the most important parameter to tune.
DQN We the following hyperparameters for DQN:
21

---

Published as a conference paper at ICLR 2024
Hyperparameter
Value
Training timesteps
5,000,000
Timesteps before learning starts
Replay buffer size
100,000
Target network update frequency
8,000
Final
0.01
SGD minibatch size Env. steps per gradient step
32
Optimizer
Adam
Learning rate
10
Table Hyperparameters we use DQN.
We try decaying the e value for e-greedy over the course of either 500 thousand or 5 million timesteps, as we found this was the most sensitive hyperparameter to tune for DQN.
SQIRL
We use the following hyperparameters for SQIRL:
Hyperparameter
Value
Training timesteps
5,000,000
Replay buffer size
1,000,000
k:
{1, 2, 3, 4, 5)
SGD minibatch size
128
SGD epochs per iteration
10
Optimizer
Adam 10-4
Learning
Loss weighting exponential smoothing
0.99
Table 6: Hyperparameters we use for SQIRL.
As we describe in the main text, we run SQIRL, with E (1,2,3,4, 3,5,) and tune m via binary search. As also described in the main text, we slightly modify SQIRI from Algorithm 2 for use with neural networks. We use a single Q-network with k A outputs to represent Q² ....... Q after collecting episodes according to Algorithm? 2, we store tuples of the form (s, s'; T, y) in replay buffer, where s and a are the action taken at some timestep, s' is the next observed state (or L if the end of the episode was reached), r is the reward received, and y is the observed reward-to-ge summed over the remainder of the episode. The replay buffer keeps one million of the most recently observed transitions. Then, we sample nm? transitions from the replay buffer in minibatches, where n is the number of epochs (10 in our experiments).
At each iteration,
For each minibatch take gradient step the mean squared errors for Q!....,Q* We find that the loss magnitudes can vary greatly between Qi for various j. since Q² has much higher- variance targets (the Monte Carlo reward-to-go) while Q², "5, Q".... have lower-variance targets (the bootstrapped Q-value estimates). Thus, we divide each loss by an exponentially weighted average of its past values so that they all have roughly equal magnitude before averaging them and taking gradient step with Adam.
Q
After completing n epochs of optimization for iteration i, we freeze the current Q-network weights and store them so that we can recall the greedy policy (x(s) arg max, Q (s, a).
GORP Similarly to SQIRL, to tune GORP on the sticky-action BRIDGE environments we con- sider (1,2,3,4,5) and determine the optimal m for each via binary search.
Full-horizon Atari games For the full-horizon Atari experiments, we run 5 random seeds and plot the median and range of evaluation returns-thal is, returns from running the current greedy policy for 20 episodes every 100,000 training steps. We use the standard Stable-Basllines3 Atari environments with sticky actions except that we do not truncate episodes on loss-of-life. Truncating like this causes the initial state distribution for the next episode to be dependent on the policy used for the previous episode, which nonstandard in RL and does not fit into our formalism. We train for 10 million steps and discount of 7 0.99. While for the sticky-action BRIDGE environments
22

---

Published as a conference paper at ICLR 2024
Gtable-Baseling CnnPolicy, for full-horizon Atari games the Impala CNN architecture (Espeoolt et al. 2018).
For PPO and DQN,
the hyperparameters above except for the following changes: for PPO, we use rollout length 128 and for DQN, we decay over the first one million timesteps. For SQIRL,
m 10 for all the games, except for Qbert, where we use m = 20. For GORP, we tune E (1,2,3) and m E {1,3, 10). We find
again tune k E 21, 3, 4,5). For SQIRL.,
that the following parameters are optimal for each game:
Game
Optimal parameters for GORP
m
Beam Rider
Breakout
Pong
Qhert
10
Seaquest
Space Invaders
D FULL RESULTS
D.1 TABLE EMPIRICAL SAMPLE COMPLEXITIES
This table lists the empirical sample complexities of PPO, DQN, SQIRL, and GORP.
PPO
DQN
SQIRL
GORP
ALIEN
> x 106
> 5 106
> X 106
5 106
AMIDAR20
>> 5 106
> 5 106
106
x 106
ASSAULT10
1.00 x 104
2.90 x 10a
1.00 x 10a
4.00 x 10a
1STERIX
2.00 105
1.90 x 10a
3.60 x 105
5 106
ASTEROIDS10
> 5 106
5 106
5 106
106
ATLANTIS
3.00 10a
1.00 X 10a
1.00 X 10a
1.40 105
ATLANTIS20
4.50 10S
> 5 10
1.61 10s
X 106
ATLANTIS30
> 5 10t
> 106
5 10s
106
ATLANTIS
> 5 106
> 5 106
5 X 106
5 X 10s
ATLANTIS50
> x 10
> 5 X 10
X 106
> X 106
ATLANTIS70
> 5 10s
5 10t
5 10"
106
BANKHEISTI0
8.90 x 10S
2.92 X 106
3.08 10S
10B
BATTLEZONE
1.40 105
2.29 x 106
6.40 X 10
X 106
BEAMRIDER
> >5x
4.34 10
106
106
BOWLING30
6.10 105
>> 5 106
5 10S
X 106
BREAKOUT
1.40 10
2.50 X 10
7.00 X 10a
1.00 X 10t
BRFAKOUT
x
1.01 X 106
4.00 10
1.56 10
BREAKOUT
1.63 106
5 106
2.83 10S
X 10
BREAKOUT
2.27 x 106
> 5 X 106
> 5 106
5 X 106
BREAKOUT
2.06 x 106
> 5 10
> 5 X 106
10s
BREAKOUTTO
2.52 106
X 10
10
10B
BREAKOUT100
3.62 x 106
> 5 X 10a
5 X 10sh
5 X 106
BREAKOUT200
3.69 x 10S
> 5 X 10S
X 10s
106
CENTIPEDE
> x 106
> 5 X 10
106
106
CHOPPERCOMIMANDIO
> 5 106
3.61 X 10S
> 5 X 106
5 X 106
CRAZYCLIMBER
4.00 x 10*
3.00 x 104
3.00 X 10a
> X 106
CRAZYCLIMBER
3.70 105
9.80 x 10S
1.30 105
5 X 106
DEMONATTACK10
1.75 x 106
5.80 X 10
3.19 x 106
5 106
ENDURO10
4.60 x 105
5.00 x 10
>5 106
> X 106
FISHINGDERBY
3.30 10s
2.05 x 106
5 106
106
FREEWAY
1.00 x 10a
2.00 x 10a
1.00 x 10a
1.00 10a
23

---

Published as a conference paper at ICLR 2024
FREEWAY20
1.00 10*
1.00 x 104
1.00 10
5.80 10
FREEWAY
2.10 x 109
4.90 x 10
1.08 x 106
>> 5 106
FREEWAY
3.20 x 105
6.10 x 10
> X 10c
10
5REEWAY
4.80 105
7.40 x 10t
5 X 106
X 106
FREEWAY70
> 5 10t
3.63 X 10c
> 5 X 106
> 5 X 106
FREEWAY
> 106
>. 10
> X 106
106
FREEWAY200
>> x 106
> 5 10
10
106
FROSTBITE
6.00 X 104
5.50 x 10a
5.50 X 10a
6,80 X 1OaT
GO
1.10 10S
1.80 x 10a
9.00 X 10t
1.49 10
GPPHER40
> 5x 10
x 10
5 10
5 10
HERO10
3.00 10a
3.00 X 104
2.00 X 10
1.56 X 10
ICEHOCKEY
8.00 10*
1.99 X 10
1.08 X 10
X 10P
KANGARO020
> 5x 106
5 106
106
106
KANGAROO30
x 106
> 5 106
> 5 X I06
5 X 106
MONTEZUMAREVENGER,
> x 10
> 5 10
> X 10
X 106
MSPACMAN20
> x 10
> x 106
106
106
NAMETHISGAMMF2
2.90 x 10
8.30 X 10a
1.37 X 106
5 X 106
PHOENIX
8.20 10
> 5 10
> 5 X 106
5 X 106
PONG20
9.30 10S
2.00 X 10S
5.60 10S
106
PONG30
4.70 10S
6.40 X 10a
5 106
5 X 10
PONG40
> x 106
> 5 106 > 10th
> 5 106
> 5 X 106
PONG50
> 5 10
5 10a
106
PONG70
> X 10t
> 5 X 106
5 X 10e
5 10P
PONG
> X 106
> 5 X 106
> 5 X 106
> 5 X 106
PRIVATEEYE
1.30 105
1.00 X 10S
2.20 10T
2.76 10
1BERT
1.60 x 10
5 106
1.40 10S
X 106
QBERT
1,25 x 106
> 5 10
>5 10B
> 5 106
ROADRUNNER
1.70 105
7.70 x 10
9.90 10
5.22 10
SEAQUEST
1.00 10a
5.00 x 10a
1.00 10t
5 106
SKIING10
> 55x 106
> >5x 10t
5 10"
> 5 106
SPACEINVADERSIO
3.00 105
2.60 x 10
1.50 105
1.01 106
TENNIS
> >5x 106
1.48 106
5 106
55x 106
TIMEPILOT10
6.00 10
5.90 X 10a
1.50 x 105
4.79 x 106
TUTANKHAM
2.70 105
3.81 x 106
2.08 x 106
>5 106
VIDEOPINBALLIO
> >5x 105
1.70 106
1.04 106
6.90 10S
WIZARDOFWORan
> 5 106
> 5 106
5 106
5 106
BIGFISH
>5x 106
4.60 x 10
5 106
106
BIGFISH
4.00 105
2.80 x 10
2.70 105
106
BIGFISH
1.37 106
5.90 x 10S
2.36 10"
106
BIGFISH
>5x 106
4.30 x 10S
1.71 10S
106
CHASER
1.90 10
5 106
5 106
106
CHASER
>5x 108
5 10t
5 10s
106
CHASER
3.80 10S
5 106
10s
106
CHASER HO
1.60 10
> 5 106
106
106
CLIMBER 80
1.00 10S
4.70 X 10S
8.00 10S
106
CLIMBER
8.00 104
5 106
2.00 10S
1.20 10s
CLIMBER
4.40 10
> 5 106
1.37 x 106
5 106
CLIMBER
>5x 1
5 106
>5 106
5 10c
COINRUN
> 5 106
55X 106
X 106
5 106
COINRUN
3.21 106
> 5 106
1.58 106
5 106
COINRUN
> 5 106
> 55x10 106
5 106
5 106
COINRUN
1.00 10a
2.00 x 10a
2.00 10a
2.80 105
DODGEBALL
80
3.70 105
2.40 x 10a
1.57 106
5 106
DODGEBALL
6.50 x 105
1.42 x 106
2.29 x 106
5 106
DODGEBAL.L.
2.70 x 105
2.57 x 106
1.60 x 105
6.10 x 105
24

---

Published as a conference paper at ICLR 2024
DODGEBALLTD
1.03 10
2.68 x 10
2.65 10
5 X 106
FRUITBOT 40
> x 106
4.80 x 10a
> X 106
5 X 106
FRUITBOT
1.98 x 106
1.03 x 106
> 5 10"
5 X 106
FRUITBOT
6.10 x 105
4.00 x 104
5.00 X 10*
> 5 X 106
FRUITBOT
> x 10t
>> 5 x 10
> 5 10th
> 5 X 106
HEIST
8.10 10a
1.65 x 106
> 5 X 106
> X 106
JUMPER
> 5 106
>. 5 X 10
> 5 X 106
>> X 106
JUMPER
1.00 10a
> 5 X 106
1.00 X 10t
1.00 X 10t
JUMPER
1.00 x 10*
> X 10
1.00 X 10
1.00 X 10
JUMPER
1.90 x 10a
> x 10
2.60 X 10
X 10P
JUMPER
> x 106
> x 10
5 106
10
LEAPER
>5x 10
> x 10
10"
106
LEAPER
1.07 10
> x 10th
10"
106
LEAPER
> x 10
x 10
10S
106
LEAPER 20
> x 10t
5 10
10t
106
MAZF
1.00 10a
> 5 10
1.00 10S
1.00 10t
MAZE
> x 10
> 5 X 10t
5 106
X 10
MAZE 30
1.00 x 10a
4.65 X 10
1.00 X 10a
1.00 10"
MAZF
4.28 x 106
> 5 106
5 X TO6
5 x 106
30
MAZE R0
EX
> x 106
> 5 10
5 X 10"
5 X 106
00
MINER 10
2.40 x 10
5.30 X 10a
2.30 X 10T
> 5 X 106
MINER
1.30 x 10a
4.70 X 10a
1.20 X 10s
> 5 X 106
MINER TO
4.00 x 104
2.87 X 106
1.00 X 10t
5.20 X 10S
MINER 10
HO
3.60 x 10
4.90 x 10
4.00 X 10
> 5 106
NINJA TO
9.70 x 10ah
> 5 10
5 10
106
NINJA TO
2.03 106
> 106
X 106
106
NINJA
> 5 106
> 106
106
106
NINJA
x 106
> >5x 106
106
10
PLUNDER
3.00 10*
2.00 x 104
1.00 10*
1.30 105
PLUNDER
1.00 10*
2.00 x 104
1.00 10t
6.00 10a
PLUNDER
1.20 10S
3.80 10S
4.07 106
2.25 106
PLUNDER HD
1.00 10a
3.00 10a
1.00 10a
1.00 10
STARPILOTT
2.65 x 106
6.70 10a
2.22 106
5 106
STARPILOT
6.00 x 105
8.30 x 105
1.14 106
X 106
STARPILOTT
8.40 105
1.43 106
3.97 106
106
STARPILOT 10
> 5 106
2.52 x 106
5 x 106
106
EMPTY-5X5
1.40 x 105
3.90 x 10
3.90 x 10S
1.99 106
EMPTY-6X6
4.00 x 105
3.10 x 10S
5.50 105
5 x 106
EMPTY-8X8
3,40 x 105
3.60 x 10S
9.10 x 10"
5 X 106
EMPTY-16X16
1.01 10
> 55x 106
>5x 10t
X 10c
DOORKEY-5X5
5.90 105
7.90 x 10
3.22 106
106
DoORKEY-6X6
1.67 x 106
> 5 106
> >5X 106
5 X 106
DOORKEY-8X8
> > 105
> 5 106
> >5X 10
X 106
DoORKEY-16X16
> 5 106
5 106
5 106
106
MULTTROOM-NN-SA
6.10 x 105
9.80 X 10
3.81 X 106
5 X 106
MULTIROOM-N44SS
> 10s
> 5 X 10
X 10s
10P
MULTIRooM-N6
> 5 106
5 X 106
106
106
KBYCORRIDORS3RI
1.40 106
> 5 X 106
> X 106
5 X 106
KEYCORRIDORS3R2
> 5 10
> X 10
X 10ch
> X 106
KEYCORRIDORS3R3
> 5 10s
> 10
10s
10P
KEYCORRIDORS4R3
> 5 106
> 5 106
X 10s
5 106
UNLOCK
1.23 x 106
> 5 X 10c
> X 106
> X 106
UNLOCKPICKUP
> 5 10s
5 X 10a
10e
106
BLOCKEDUNLOCKKPCKK
> X 10s
> 5 X 106
> 10c
5 106
25

---

Published as a conference paper at ICLR 2024
OBSTRUCTEDMAZE-IDDA
> 5 X 10
5 X 10
10
X 10
OBSTRUCCTEDMAZE-IDDI
> 5 X 106
> 5 X 106
> X 106
> X 106
OBSTRUCCTEDMA7E-IDD..R
> 10
> x 106
10
10
FOURROOMS
> 5 106
> 5 106
5 106
106
LAVACROSSINGIS9NI
7.10 x 10a
4.60 x 10
2.78 X 106
5 X 106
LAVACROSSINGS992
2.38 10
4.60 x 10a
3.17 X 10c
10
LAVACROSSINGS9N3
6.20 10
6.40 10
2.02 X 10
106
LAVACROSSINGS!IINS
>5x 10t
>5 10
>5x 10"h
5 X 10P
SIMPLECROSSINGS9NI
4.50 x 10S
8.70 x 10a
>5 10c
10
SIMPLECROSSINGSSN
5.10 10
1.94 10
5 X 10
10
SIMPLECROSSSIGGS9N3
3.60 x 10
5.00 x 10a
1.18 X 10"
5 X 10
SIMPLECROSSINGSSIING
> 5 10
55x 10
> >5 X 10a
X 10
LAVAGAPS5
2.70 105
2.80 x 10t
7.10 105
106
LAVAGAP$6
9.70 x 105
6.30 x 10a
2.44 X 106
5 X 106
LAVAGAPS7
1.26 x 10
1.25 x 10c
> 5 106
X 106
D.2 TABLE OF RETURNS
This table lists the optimal returns in each sticky-action MDP as well as the highest returns achieved by PPO, DQN, SQIRL. and GORP. The achieved returns may be higher than the optimal return because they are measured by Monte Carlo average over 100 episodes during evaluation.
Returns
MDP
Optimal policy
PPO
DQN
SQIRL
ALIEN
158.13
158.1
157.2
155.7
AMIDAR20
76.49
63.54
71.44
60.07
ASSAULT 10
105.0
105.0
105.0
105.0
ASTERIX1U
327.53
330.0
334.5
332.5
ASTEROIDS10
170.81
138.1
115.3
130.1
ATLANTIS
187.5
190.0
190.0
192.0
ATLANTIS20
740.91
752.0
726.0
754.0
ATLANTIS
1, 829.52
1, 13230.0
995.0
1, 117.0
ATLANTIS
2, 620.35
1, 1,849.0
1,218.0
1, 677.0
ATLANTIS50
4, 856.81
3, 683.0
2,959.0
3, 140.0
ATLANTISç0
932.88
6, 6,051.0
3, 2,220.0
5, 456.0
BANKHEIST10
26.15
26.6
26.4
26.2
BATTLEZONE
497.07
1, 5,0000
1,520.0
1, 560.0
BEAMRIDER20
129.23
125.4
129.36
124.08
BOWLING30
8.8
8.81
5.75
7.69
BREAKOUT
1.17
1.26
1.21
1.25
BREAKOUT20
1.93
1.97
1.99
2.02
BREAKOUT30
2.5
2.55
2.25
2.49
BREAKOUT
2.61
2.7
2.34
2.49
BREAKOUTS0
2.69
2.84
2.42
2.47
BREAKOUT70
2.9
3.01
2.38
2.53
BREAKOUT100
3.08
3.12
0.81
2.44
BREAKOUT
3.08
3.08
0.78
2.5
CENTIPEDE
1, 1,3.1.17
900.0
1,150.5 150.5
186.61
CHOPPERCOMMANE
553.42
469.0
560.0
495.0
CRAZYCIIMBBR
324.9
328.0
327-0
333.0
CRAZYCLIMBER
698.07
701.0
704.0
707.0
DEMONATTACK
37.07
37.1
38.3
37.3
ENDURO10
4.27
4.33
4.34
3.95
FISHINGDERBY11
7.5
7.56
7.5
6.79
FREEWAY
1.0
1.0
1.0
1.0
FREEWAY
2.0
2.0
2.0
2.0
FREEWAY 30
3.75
3.77
3.77
3.79
26

---

Published as a conference paper at ICLR 2024
FREEWAY 10
4.75
4.78
4.76
4.69
5REEWAY
5.75
5.78
5.76
5.67
FREEWAY70
8.49
7.84
8.5
8.03
FREEWAY
11.83
10.85
11.47
10.86
2REEWAY
23.84
21.53
22.05
20.88
FROSTBITE
66.72
67.5
67.2
67.5
GO
18.75
19.2
19.0
19.4
GOPHER
112.93
83.4
72.6
72.8
HERO1O
74.71
75.0
75.0
75.0
ICEHOCKEY 10
1.0
1.0
1.0
1.0
KANGAROO20
186.32
174.0
180.0
168.0
KANGAROO30
444.7
200.0
298.0
207.0
MONTEZUMAREVENGEIS
22.53
0.0
0.0
0.0
MSPACMAN20
460.6
282.9
435.5
420.0
NAMETHISGAME22
94.02
95.7
96.3
94.8
PHOENIX10
179.89
180.8
173.8
169.2
PONG20
-1.01
-1.0
-1.0
-1.0
PONG30
-1.61
-159
-1.59
-185
PONG40
-1.11
-1.26
-1.26
-2.0
PONG50
-1.36
-1.96
-1.52
-3.35
PONG70
-1.48
-3.43
-2.32
-5.23
PONG100
-1.41
-5.11
-4.18
99.55
PRIVATREYE1O
98.44
99.0
99.0
99.0
IO
350.0
351.75
339.75
361.75
QBERT
579.71
582.75
565.0
547.0
ROADRUNNER10
474.71
489.0
486.0
486.0
SEAQUEST
20.0
20.0
20.0
20.0
SKIINGJO
-8, 011.57
9, 013.0
8, 353.5
8, 341.18
SPACEINVADERS10
33.91
34.3
34.8
34.8
TENNIS
0.8
0.0
0.81
0.59
TIMEPILOT
131.25
136.0
135.0
138.0
1
16.51
16.79
16.54
16.83
VIDEOPINBALL10
1, 744.95
1, 1,8.8.09
1, 1.816.01
1, 825.03
WIZARDOFWOR30
260.35
100.0
100.0
100.0
BIGFISH
3.53
2.26
3.56
2.78
BIGFISH
2.97
2.98
2.98
2.99
BIGFISH
6.86
6.87
6.89
6.87
BIGFISH 0
H0
2.59
1.84
2.62
2.64
CHASER
0.88
0.88
0.4168
0.8052
CHASER
0.88
0.84
0.8
0.8628
CHASER 20
0.88
0.8748
0.5304
0.8424
CHASERR HD
0.88
0.8792
0.8572
0.84
CLIMBER 80
1.93
1.94
1.94
1.95
CLIMBER
1.75
1.78
1.62
1.78
CLIMBER
10.92
11.0
10.89
11.0
CLIMBER HO
1.22
1.0
1.0
1.0
COINRUN 80
8.82
8.8
7.0
8.8
COINRUN 10
51
8.36
8.4
7.3
8.6
COINRUN E2
6.94
6.9
6.0
0.0
COINRUN 10
HO
10.0
10.0
10.0
10.0
DODGEBALL E0
7.81
8.08
8.12
8.16
DODGEBALL
5.3
5.32
5.36
5.3
DODGEBALL
5.71
5.82
5.78
5.88
DODGEBALI
4.13
4.28
4.16
4.2
FRUITBOT
1.99
1.33
2.24
1.35
FRUITBOT
3.6
3.64
3.66
2.47
27

---

Published as a conference paper at ICLR 2024
FRUITBOT F2
0.89
0.91
0.89
0.91
30
FRUITBOT El
HH0
1.85
0.0
0.11
0.04
40
HEIST To
9.38
9.5
9.4
0.0
JUMPER HD
1.33
0.0
0.0
0.0
JUMPER
10.0
10.0
7.5
10.0
JUMPER
10.0
10.0
6.0
10.0
JUMPER
10.0
10.0
6.8
10.0
JUMPER
2.77
0.0
0.0
0.0
LEAPER
4.92
0.0
0.0
0.0
LEAPER
9.92
10.0
9.9
9.5
LEAPER
6.42
0.0
0.0
0.0
LEAPER
5.7
0.0
0.0
0.0
MAZE
10.0
10.0
0.0
10.0
MAZE
7.42
0.0
0.0
0.0
MAZE 30
10.0
10.0
10.0
10.0
MAZF 30
9.99
10.0
0.0
0.1
MAZE 100
EX
9.76
0.0
0.0
0.0
MINER
0.91
0.92
0.91
0.92
MINER
1.63
1.69
1.66
1.68
MINER
1.0
1.0
1.0
1.0
MINER HO
2.97
2.97
2.98
2.99
0
NINJA
6.53
6.6
0.0
3.3
NINJA
6.08
6.3
0.0
0.0
NINJA
2.0
0.0
0.0
0.0
NINJA
2.22
0.0
0.0
0.0
PLUNDER
1.0
1.0
1.0
1.0
PLUNDER
1.0
1.0
1.0
1.0
PLUNDER
0.56
0.62
0.57
0.56
PLUNDER 10
1.0
1.0
1.0
1.0
STARPILOT ED
7.02
7.09
7.11
7.04
STARPILOT
4.33
4.37
4.37
4.37
STARPILOT
3.58
3.62
3.62
3.63
STARPILOT
3.38
3.33
3.42
3.27
EMPTY-5X5
1.0
1.0
1.0
1.0
EMPTY-6X6
1.0
1.0
1.0
1.0
EMPTY-8X8
1.0
1.0
1.0
1.0
EMPTY-16X16
1.0
1.
0.0
0.1
DOOKKE
1.0
1.0
1.0
1.0
DO0RKEY-6X6
1.0
1.0
0.0
0.03
DOORKEY-8X8
1.0
0.0
0.0
0.0
1
1.0
0.0
0.0
0.0
MULTIROOM-N2-S4
1.0
1.0
10
1.0
MULTIROOM-N44SS
1.0
0.0
0.0
0.0
MULTIROOM-N6
1.0
0.0
0.0
0.0
KEYCORRIDORS3RI
1.0
1.0
0.0
0.03
KEYCORRIDORS3R2
1.0
0.0
0.0
0.01
KEYCORRIDORS3R3
1.0
0.0
0.0
0.0
KEYCORRIDORS4R3
1.0
0.0
0.0
0.0
UNLOCK
1.0
1.0
0.0
0.06
UNLOCKKPCCKUP
1.0
0.0
0.0
0.01
BLOCKEDDUX..CKPPCKUP
1.0
0.0
0.0
0.0
OUSTRUCTEDM..ZE-IDD
1.0
0.0
0.0
0.01
OBSTRUCTEDMAAZE-IDDE
1.0
0.0
0.0
0.01
OBSTRUCTEDM.ZZ-IIDum
1.0
0.0
0.0
0.0
FOURROOMS
1.0
0.0
0.0
0.08
28

---

Published as a conference paper at ICLR 2024
LAVACROSSINGS9N
1.0
1.0
1.0
1.0
LAVACROSSINGS992
1.0
1.0
1.0
1.0
LAVACROSSINGS9N3
1.
1.0
1.0
1.0
LAVACROSSINGS1 5
0.41
0.0
0.0
0.0
SIMPLECROSSIINGS9N
1.0
1.0
1.0
0.86
SIMPLECROSSINGGS9N2
1.0
1.0
1.0
0.52
SIMPLECROSSIIGGS9N3
1.0
1.0
1.0
1.0
SIMPLECROSSINGSIING
1.0
0.0
0.0
0.01
LAVAGAPS5
1.0
1.0
1.0
1.0
LAVAGAPS6
1.0
1.0
1.0
1.0
LAVAGAPS7
1.0
1.0
1.0
0.92
29

---

Published as a conference paper at ICLR 2024
D.3 LEARNING CURVES FOR STICKY-ACTION BRIDGE MDPs
15
Hab
Kassvat
Coppat
M
36
bonkmi
Jon 050
Ko M0
055
San Comomiii Straacaosdiii
SwaGust
Lwokes?
Learning curves for PPO, DQN, SQIRL, and SQIRL on the sticky-action BRIDGE MDPs. Solid lines show the median return (over random seeds) of the policies learned by each algorithm throughout training. The shaded region shows the range of returns over random seeds. The optimal return in each environment shown as the dashed black line.
Figure 5:
30


Reviews:
[{"review_id": "1LMmEcM4Nt", "reviewer": "Reviewer_kbuB", "summary": "This paper considers a setting where exploration is not needed. They formalize the setting in Def 3.1. They also design an algorithm and show that the algorithm is sample-efficient in the setting they consider. They also conduct experiment to validate their idea.", "questions": "1. See the 'Weakness' section.\n\n2. Figure 2 shows that PPO fails in most tasks with k=1, which contradicts the claim 'Furthermore, these are the environments where deep RL algorithms like PPO are most likely to find an optimal policy' on Page 5. Can you provide an explanation?\n\n3. Apart from the tasks in Bridge, can you verify Def 3.1 for other tasks, including go and robotic?", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The setting they consider is closely related to the tasks in the application.", "weaknesses": "1. The theory is simple and straightforward. In fact, in the setting they considered, exploration is not needed. \n\n2. It is unclear whether their algorithm can be adapted to the scenario where exploration is needed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5zeWMB8Qhz", "reviewer": "Reviewer_yWoc", "summary": "The paper extends the previous work GORP which studied the explanation of RL in deterministic environments by proposing and studying a new method under stochastic environments under function approximation. GORP shows that the success of both PPO and DQN can simply be explained by a simple procedure of greedily improving a few steps over a value function of random policy. SQIRL extends the algorithm and analysis for stochastic environments. The results demonstrate that the performance of the proposed method SQIRL correlates with the performance of PPO and DQN in stochastic environments.", "questions": "None", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper addresses the key limitation of prior work: GORP which showed that performance of deepRL can be explained by just acting greedily with respect to value function of a random policy in deterministic environments. GORP does not extend to stochastic environments directly and the authors propose one way to extend the algorithm to stochastic environments by using function approximation.\n2. The authors theoretically explain the sample complexity of their proposed algorithm in terms of psuedo-dimension of the function class along with a combination of concentration and FQI analysis.  The authors also demonstrate that this sample complexity is closely related to sample complexity of Deep RL algorithms used in practice.\n3. The method SQIRL is tested extensively over a set of 150 environments from previous work GORP. The environments are made stochastic by using sticky actions and show that whenever PPO or DQN does well, SQIRL does well 78% of the time too.", "weaknesses": "1. My major concern is around the novelty of the proposed approach:\na. To address stochasticity an open loop trajectory optimization is replaced by FQI. This is not new in my opinion:\nPrior works:\n[1] Considers a tree search with the FQI procedure along with analysis to account for stochastic environments.\n[2] Considers a FQI analysis of H-step lookahead under empirical distributions for a more general setting of learned models (A.3) \n[3] Considers a similar FQI setting with learned models where exploratory policy is the dataset policy\nA proper discussion on the novelty of using FQI to replace open-loop trajectory optimization along with a comparison with these prior works is warranted.\n2. The strong claim of in-distribution generalization: On page 6 the authors claim that if we can properly regress for approximate-Q then we can also estimate the maximum action properly. The claim seems to be too strong without evidence: With finite data, the Q will almost always have errors. These errors will lead to perhaps suggesting actions OOD and lead to overestimation bias commonly observed in deep RL. This analysis seems to be missing in analysis of FQI for SQIRL.\n3. A minor nitpick: Unlike GORP, the whole set of stochastic environments are not explained by SQIRL - I think the title and introduction implying something more stronger that it should?\n4. Sticky action is a particular kind of stochasticity - More ways of inducing stochasticity and varying the noise std can make the empirical experiments stronger.\n[1]: https://arxiv.org/pdf/2107.01715.pdf\n[2]: https://arxiv.org/pdf/2107.01715.pdf\n[3]: https://arxiv.org/pdf/2008.05556.pdf", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jJcDNXB0sz", "reviewer": "Reviewer_1dWJ", "summary": "In this work, the authors aim to provide theoretical explanations, supported by an empirical analysis, of the practical success of Deep-RL algorithms. In recent work, Laidlaw et al., 2023, \"Bridging RL Theory and Practice with the Effective Horizon\", the authors have shown that deep-RL methods succeed in (deterministic) MDPs, especially in cases in which it is sufficient to take few \"greedyfication\" steps from the Q-function of the random policy (i.e., the effective horizon). In this work, the authors show that these claims can be extended to stochastic MDPs by introducing the \"stochastic effective horizon\". More specifically, the paper is articulated in the following points:\n1. The authors provide a formal definition of the \"stochastic effective horizon\" notion that presents itself as the natural extension of the effective horizon introduced by Laidlaw et al., 2023. \n2. Secondly, the authors propose a simple algorithm (SQIRL) whose sample complexity scales exponentially with the stochastic effective horizon (which is typically much smaller than the optimization horizon of the underlying problem).  \n3. On a stochastic extension of the benchmark Bridge (Laidlaw et al., 2023), the authors show that modern deep-RL algorithms performance significantly correlates with the empirical success of SQIRL. This empirical phenomenon suggests that the concept of stochastic effective horizon can explain some of the reasons behind the success/failure of modern deep-RL methods.", "questions": "See weakness section above.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. Comprehending the factors contributing to the successes and shortcomings of deep reinforcement learning (Deep-RL) algorithms is of utmost importance. Analyzing the environments in which current methods excel provides insight into both their capabilities and constraints. This understanding serves as a foundation for inspiring and creating innovative approaches that address the limitations of current technologies. In this sense, the work done by the authors goes in this direction, as the problem deserves attention from the community (both practitioners and theoreticians).\n2. The paper takes large inspiration from the recent work of Laidlaw et al., 2023, \"Bridging RL Theory and Practice with the Effective Horizon\". Nevertheless, in Laidlaw et al., 2023, the authors consider a deterministic setting. In this work, instead, the authors propose an extension to the more general (and challenging) stochastic environments. Although, in this sense, the novelty of the underlying idea is incremental, the challenges that are introduced from stochastic environments do not allow for a direct extension. \n3. The main text is overall well-written and easy to understand.", "weaknesses": "**1. Novelty**\n\nFirst, I remark that the main contribution done by the authors goes into the direction of providing explanations behind the success of deep-RL algorithms. Although these explanations are highly appreciated, it has to be remarked that the main idea on which the work is built has been already proposed in Laidlaw et al., 2023. Indeed, in Laidlaw et al., 2023, the authors have shown that deep-RL succeed in (deterministic) MDPs especially in cases in which it is sufficient to take few \"greedyfication\" steps from the Q-function of the random policy. In this sense, the novelty, in terms of new explanations that are given to the success of deep-RL algorithms is somehow limited. The contributions of the authors, in this sense, is limited to to the extension to stochastic environments.\n\n**2. Theoretical claims and analysis**\n\nI have concerns regarding the theoretical claims done by the authors, especially regarding the main Theorem (i.e., Theorem 3.6). Specifically, I checked the proofs behind Theorem 3.6, and there are some steps that are unclear/unprecise/uncorrect (p.s., I haven't had a look in details to the other sections of the appendix, so I am unaware if there mistakes in those parts). \n\nFirst, I begin with the result on the sample complexity (Eq. 1). Using standard tools from the bandit community, it is possible to show that, for $\\epsilon$-best arm identification with 2 arms, the Lower bound is given by $\\widetilde{\\Omega}[ \\max \\left( \\Delta^{-2}, \\epsilon^{-2} \\right) ]$ (RL with 1 state, depth 1, and 2 actions). In Eq. 1, instead, the authors claim a complexity of $\\widetilde{\\mathcal{O}}(\\epsilon^{-1})$, which is clearly impossible. It seems to me that the main problem is that the authors masked inside the $\\widetilde{\\mathcal{O}}$ instant dependent quantities such as $\\Delta^{-2}$. \n\nSecondly, I invite the authors to provide details on the last step behind the proof of Lemma B.1. To me, it seems that they upper-bound $P_\\pi(\\mathcal{E}) \\le \\epsilon$, but, then it is unclear how they upper bound the cumulative sum of rewards to $1$.\n\n(minor) some assumptions in Lemma B.1 are not used. For instance, k-solvability seems to be not used within the proof.\n\nOverall, I currently believe that all these issues could be solved, leading to results comparable (or maybe, slightly worse) to the one presented in Theorem 3.6. Nevertheless, the paper, at its current status, seems to be lacking in formal correctness.\n\n**3. Weaknesses of the proposed algorithm (minor)**.\n\nIt has to highlighted that the algorithm proposed by the authors needs to be aware of the k parameter of K-QVI-solvability property. This parameter is often unknown in practice. I consider this to be a minor weakness, as the purpose of this work is not to propose an algorithm (with theoretical guarantees) that can be applied in practice, but rather it focuses on explaining why deep RL algorithms succed in practice. \n\n**4. Minor comments:**\n- Colors in Figure 2 seems to be swapped. I currently read the Figure as follows: PPO fails most likely with small values of k (however, I guess the opposite claim should be the correct one).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dgfg2QZeLa", "reviewer": "Reviewer_UBNV", "summary": "This paper proposed a new explanation of the success of deep RL algorithms that use random exploration strategies for stochastic environments. The key observation is that many environments can be solved by a few steps of value iteration starting with the uniformly random policy, meaning that sophisticated exploration is unnecessary. Based on the observation, this paper designs a novel provable RL algorithm called SQIRL that runs a few steps of fitted-Q iteration, and the sample complexity of SQIRL is only exponential in (roughly) the number of value iteration steps needed to solve the environment. This paper also shows empirically that the sample complexity of SQIRL correlates with the sample complexity of standard deep RL algorithms such as DQN and PPO.", "questions": "-\tHow does the performance of SQIRL change with the hyperparameter k? Is the best performance always achieved by choosing the smallest k such that the environment is k-QVI-solvable?\n-\tIs there a typo in the legend of Figure 2? Currently the figure shows that PPO succeeds less often when k=1.\n-\tIt would be intriguing to see whether the sample complexity of the empirical version of SQIRL is still upper bounded by Theorem 3.6. For example, for all the environments with k=1, does SQIRL always solve the environment after $N^{SQIRL}$ steps?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "-\tThis paper extends the effective horizon definition in Laidlaw et al. (2023) to stochastic environments, and consequently designs a novel provable algorithm SQIRL that depends exponentially only on the effective horizon. This paper also empirically verifies that the effective horizon is small for many realistic environments including Atari games. Hence, the SQIRL algorithm is the first algorithm that (a) has provable sample complexity upper bound on realistic environments, and (b) achieves non-trivial performance empirically.\n-\tAlthough the algorithm is very similar to the classic FQI algorithm, the sample complexity upper bound in Theorem 3.6 is novel. In addition, the assumptions on the oracle are mild and potentially can be satisfied by realistic neural networks.  \n-\tThis paper is well-written and easy-to-follow.", "weaknesses": "-\tGiven that SQIRL has a provable and also computable sample complexity bound, this paper could benefit from more analysis on the comparison between the theoretical and empirical performance of SQIRL. For example, how does the percentage of environments that SQIRL can solve change with k? Is there a strong correlation between the actual sample complexity SQIRL and the sample complexity upper bound in Theorem 3.6?\n-\tFor an unknown environment, computing the effective horizon or the sample complexity bound requires running a few steps of value iteration, which is not much easier than running the algorithm since we must iterate through the entire state space. This makes the instance-dependent complexity upper bound less helpful in determining the hardness of an environment / predicting the performance of deep RL algorithms on new environments. The bound could be more impactful if there is an efficient algorithm to estimate the effective horizon.\n-\tIt is unclear whether the small effective horizon is an artifact of the sticky actions modification to the environment. A 25% chance of sticky action could potentially make long-term planning impossible, hence decreasing the effective horizon. Hence the conclusion of Figure 2 needs further justification.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)