Bridging RL Theory and Practice with the Effective Horizon
Authors: Cassidy Laidlaw
Stuart Russell
Anca Dragan
Venue: NeurIPS 2023 oral (2023)
Keywords: reinforcement learning
RL theory
theory of reinforcement learning
instance-dependent bounds
empirical validation of theory
TL;DR: We prove new sample complexity bounds for reinforcement learning (RL) and demonstrate they closely reflect the performance of deep RL algorithms.

Abstract: Deep reinforcement learning (RL) works impressively in some environments and fails catastrophically in others. Ideally, RL theory should be able to provide an understanding of why this is, i.e. bounds predictive of practical performance. Unfortunately, current theory does not quite have this ability. We compare standard deep RL algorithms to prior sample complexity bounds by introducing a new dataset, BRIDGE. It consists of 155 MDPs from common deep RL benchmarks, along with their corresponding tabular representations, which enables us to exactly compute instance-dependent bounds. We find that prior bounds do not correlate well with when deep RL succeeds vs. fails, but discover a surprising property that does. When actions with the highest Q-values under the *random* policy also have the highest Q-values under the *optimal* policy—i.e., when it is optimal to act greedily with respect to the random's policy Q function—deep RL tends to succeed; when they don't, deep RL tends to fail. We generalize this property into a new complexity measure of an MDP that we call the *effective horizon*, which roughly corresponds to how many steps of lookahead search would be needed in that MDP in order to identify the next optimal action, when leaf nodes are evaluated with random rollouts. Using BRIDGE, we show that the effective horizon-based bounds are more closely reflective of the empirical performance of PPO and DQN than prior sample complexity bounds across four metrics. We also show that, unlike existing bounds, the effective horizon can predict the effects of using reward shaping or a pre-trained exploration policy. Our code and data are available at https://github.com/cassidylaidlaw/effective-horizon.

Bridging Reinforcement Learning Theory and Practice with the Effective Horizon
Cassidy Laidlaw
Stuart Russell Anca Dragan
Unversity of California, Berkeley laassidy_laidlaa,, russell, anca) berkeley edu
Abstract
Deep reinforcement learning (RL) works impressively in some environments and fails catastrophically others. Ideally, RL theory should be able to provide an understanding of why this is, i.e. bounds predictive of practical performance. Unfortunately, current theory does not quite have this ability. We compare standard deep RL algorithms to prior sample complexity bounds by introducing new dataset, BRIDGE. consists of 155 deterministic MDPs from common deep RL benchmarks, along with their corresponding tabular representations, which enables us to exactly compute instance-dependent bounds. We choose to focus deterministic environments because they share many interesting properties of stochastic environments, but are easier to analyze. Using BRIDGE, we find that prior bounds do not correlate well with when deep RL succeeds vs. fails, but discover surprising property that does. When actions with the highest Q-values under the random policy also have the highest Q-values under the optimal policy (i.e. when it is optimal to be greedy on the random policy's 's Q function), deep RL tends to succeed; when they don't, tt deep RL tends fail. We generalize this property into new complexity measure of an MDP that we call the effective horizon, which roughly corresponds how many steps of lookahead search would be needed in that MDP in order to identify the next optimal action, when leaf nodes are evaluated with random rollouts. Using BRIDGE, we show that the effective horizon- based bounds are more closely reflective of the empirical performance of PPO and DQN than prior sample complexity bounds across four metrics. We also find that, unlike existing bounds, the effective horizon can predict the effects of using reward shaping or a pre-trained exploration policy. Our code and data are available https: //gi com/ cotp///ssiiyyaaaaaaa//eeeeeeiiio horizo
Introduction
Deep reinforcement learning (RL) has produced impressive results in robotics (I, strategic games 21. and control 3 However, the same deep RL algorithms that achieve superhuman performance in some environments completely fail to learn in others. Sometimes, using techniques like reward shaping or pre-training help RL. and in other cases they don't. Our goal is provide a theoretical understanding of why this is a theoretical analysis that is predictive of practical RL performance.
Unfortunately, there large gap between the current theory and practice of RI. Despite RI theorists often focusing on algorithms using strategic exploration (e.g., UCB exploration bonuses; Azar et al. deep RL algorithms, which explore randomly, resist
4. Jin et al. (5)), the most commonly-use such analysis. In fact, theory suggests that RL with random exploration is exponentially hard in the worst case (6). but this is not predictive of practical performance. Some theoretical research has explored instance-dependent bounds, identifying properties of MDPs when random exploration should perform better than this worst case 7 8) However, is not clear whether these properties correlate with when RL algorithms work vs. fail and our results will reveal that they tend not to.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Current state
PPO sample complexity
p 0.81
10"
If the current theory literature cannot ex- plain the empirical performance of deep RI, what can? Ideally, theory of RI. should provably show why deep RI. suc- ceeds while using random exploration. It should also be able to predict which envi- ronments are harder easier to solve empir- ically. Finally, it should be able to explain when and why tools like reward shaping or initializing with a pre-trained policy help make RL perform better.
A: dtinessd
10a
10a
m random rollouts from each leaf node
10a
10
10"
Our bounds
We introduce the effective horizon, a property of MDPs that controls how difficult RL is. Our analysis is mo- tivated by Greedy Over Random Policy (GORP), a simple Monte Carlo planning algorithm (left) that exhaustively ex- plores action sequences
Figure I:
We present a new theoretical complexity measure for MDPs called the effective hori- zon that satisfies all of the above criteria. Intuitively, the effective horizon measures approximately how far ahead an algorithm must exhaustively plan in an environment before evaluating leaf nodes with random rollouts.
length and then uses m random rollouts to evaluate each leaf node. The effective horizon combines both & and into a single measure. We prove sample complexity bounds based on the effective horizon that correlate closely with the real performance of PPO, a deep RL algorithm, on our BRIDGE dataset of 155 deterministic MDPs (right).
In order to assess previous bounds and eventually arrive such property, we start by creating new dataset, BRIDGE, of deterministic MDPs from common deep RI. benchmarks. A major difficulty with evaluating instance-dependent bounds is that they can't 't be calculated without tabular representations, so prior work work has typically relied on small toy environments for justification. To get a more realistic picture, we choose 155 MDPs across different benchmarks and compute their tabular representations- stored, This is a massive engineeering challenge, but it enables connecting theoretical and empirical results at an unprecedented scale. We focus on deterministic MDPs in BRIDGE and in this paper because they are simpler to analyze but still have many of the interesting properties of stochastic MDPs, like reward sparsity and credit assignment challenges. Many deep RL benchmarks are (nearly) deterministic, so we believe our analysis is highly relevent to practical RL.
with over 100 million states which must be exhaustively explored and
Our journey to the effective horizon began with identifying a surprising property that holds in many of the environments BRIDGE: one can learn to act optimally by acting randomly. More specifically, actions with the highest Q-values under the uniformly random policy also have the highest Q-values under the optimal policy. The random policy is about as far as one can get from the optimal policy, so this property may seem unlikely to hold. However, about two-thirds of the environments in BRIDGE satisfy the property. This proportion rises to four-fifths among environments that PPO ( a popular deep RL algorithm, PPO is more likely to fail than succeed-and and when it does succeed, so does simply applying a few steps of lookahead on the Q-function of the random policy (Figure (p. We found it remarkable that, at least in the environments in BRIDGE, modern algorithms seem to boil down to not much more than acting greedily on the random policy Q-values.
solve efficiently (Table DT. Conversely, when this property does not hold,
The property that it is optimal to act greedily with respect to the random policy's Q-function has important implications for RL theory and practice. Practically, it suggests that very simple algorithms designed to estimate the random policy's s Q-function could efficiently find an optimal policy. We introduce such an algorithm, Greedy Over Random Policy (GORP), which also works in the case where one may need to apply a few steps of value iteration to the random policy's 's Q-function before acting greedily. Empirically, GORP finds optimal policy in fewer timesteps than DQN (another deep RL algorithm) in more than half the environments in BRIDGE. Theoretically, it is simple to analyze GORP, which consists almost entirely of estimating the random policy's 's Q-function via sample average over i..d. random rollouts. Since GORP works well empirically and can be easily understood theoretically, thoroughly analyze it in the hopes of finding sample complexity bounds that can explain the performance of deep RL.
Our analysis of Greedy Over Random Policy leads to single metric, the effective horizon, that measures the complexity of model-free RL in an MDP. As shown in Figure GORP is an adaptation of Monte Carlo planning algorithm to the reinforcement learning setup (where the transitions are unknown): it mimics exhaustively planning ahead l steps and then sampling m random rollouts from
2

---

each leaf node. The effective horizon H combines the depth k and number of rollouts m. We call the effective horizon because worst-case sample complexity bounds for random exploration are exponential in the horizon T, while we prove sample complexity bounds exponential only in the effective horizon H. For most BRIDGE environments, H < T, explaining the efficiency of RL in these MDPs.
In the environments in BRIDGE, we find that the effective Norizon-based sample complexity bounds satisfy all our desiderata above for a theory of RL. They are more predictive of the empirical sample complexities of PPO and DQN than several other bounds from the literature across four metries, including measures of correlation, tightness, and accuracy (Table 2). Furthermore, the effective horizon can predict the effects of both reward shaping (Table Ba) and initializing using a pre- trained policy learned from human data or transferred from a similar environment (Table In contrast, none of the existing bounds we compare to depend on both the reward function and initial policy; thus, they are unable to explain why reward shaping, human data, and transfer learning can help RL. Although our results focus on deterministic MDPs, we plan to extend our work to stochastic environments in the future and already have some promising results in that direction.
2 Preliminaries
We begin by presenting the reinforcement learning (RL) setting we consider. An RL algorithm acts in deterministie, tabular, episodic Markov decision process (MDP) with finite horizon. The N and optional discount factor [0, 1]. a start state 81, transition function S x A + S, and reward function R: S A + R. Throughout the paper we use = but all our theory applies equally when y < 1.
MDP comprises a set of states S, set of actions A, a horizon
An RL agent interacts with the MDP for number of episodes, starting at a fixed start state s1. At each step E [T] of an episode (using the notation [n]
n)), the agent observes the state 8t,
picks an action 0g, receives reward R(st, ae), and transitions to the next state 8t+1 [( az). A
policy ı a set functions I1, कe S + (AA), which defines for each state and timestep a
distribution (a s) over actions. If policy is deterministic at some state, then with slight abuse of notation we denote a = (T()) to be the action taken by My in state
We denote a policy's s Q-function QF S x A + R and value function V S - R for each & E [T]. In this paper. we also use a Q-function which is generalized to sequences of actions. We use the shorthand axæ++* to denote the sequence a...... aetk, and define the action-sequence Q-function as
T
QT (St, (0.++)))) = Ex
rt R(se, St: Grit+
The objective of an RL algorithm is to find an optimal policy x", which maximizes J(T) (s1). the expected discounted sum of rewards over episode, also known as the return of the policy
Generally, an RL algorithm can be run for any number of timesteps n (i.e., counting one episode as T timesteps). returning a policy x". We define the sample complexity N of an RL algorithm as the minimum number of timesteps needed such that the algorithm has least 50-50 chance of returning an optimal policy:
min (n E N (J((") = JJ) 22)21/2) 1/2)
Here, the probability is with respect any randomness the algorithm itself. One can estimate the sample complexity N empirically by running an algorithm several times, calculating the number of samples n needed to reach the optimal policy during each run, and then taking the median.
The following simple theorem gives upper and lower bounds for the worst-case sample complexity in a deterministic MDP, depending on A and T.
Theorem 2.1. There is an RL algorithm which can solve any deterministic MDP with sample complexity < ST A /2). Conversely, for any RL algorithun and any values of and A, there must be some deterministic MDP for which its sample complexity N 2 T([AT) / 1).
All proofs are deferred to Appendix A
this case, the idea of the proof is quite simple, and will later be useful to motivate our idea of the effective horizon: in MDP where exactly one sequence of actions leads to a reward, an RI algorithm may have to try almost every sequence of actions to find the optimal policy; there are AT such sequences. As develop sample complexity bounds based on
3

---

the effective horizon in Section 5 we can compare them to the worst-case bounds in Theorem 2.1
Why deterministic MDPs? We focus deterministic (as opposed to stochastic) MDPs in this study for several reasons. First, analyzing deterministic MDPs avoids the need to consider general- ization within RL. algorithms. In common stochastic MDPSs, one often needs neural-network based policies, whereas in a deterministic MDP one can simply learn a sequence of actions. Since neural network generalization is not well understood even in supervised learning, analyzing generalization in RL is an especially difficult task. Second, deterministic MDPs still display many of the interesting properties of stochastic MDPs. For instance, deterministic MDPs have worst case exponential sample complexity when using naive exploration; environments with dense rewards are easier to solve empirically than those with sparse rewards; credit assignment can be challenging; and there is a wide range of how tractable environments are for deep RL, even for environments with similar horizons, state spaces, and action spaces.
Finally, many common RL. benchmark environments are deterministic or nearly-deterministii. For instance, the ALE Atari games used evaluate DQN [3], Rainbow (IO), and MuZero [Н]] are all deterministic after the first state, which is selected randomly from one of only 30 start states. The widely used DeepMind Control Suite 12 based on the MuJoCo simulator [S3, which is also deterministic given the initial state (some of the environments do use a randomized start state). MiniGrid environments [14], which are commonly used for evaluating exploration [I5], environment design [16]. and language understanding [17], are also deterministic after the initial state. Thus, our investigation of deterministic environments is highly relevant to common deep RL practice.
3 Related Work
Before delving into our contributions, we briefly summarize existing work in theoretical RL and prior sample complexity bounds. Our novel bounds are contrasted with existing ones in Sections 5.1 and 6 for a detailed comparison with full definitions and proofs, please see Appendix
Recent RL theoretical results largely focus on strategic exploration using techniques like UCB exploration bonuses [18 4. 19 5 20 21 (2]. Such bounds suggest RL is tractable for smaller or low-dimensional state spaces. In deterministic MDPs, the UCB-based R- MAX algorithm [23 [8] has sample complexity bounded by SAT.
Some prior work has focused on sample complexity bounds for random exploration. Liu and Brunskill 7 give bounds based on the covering length L of an MDP, which is the number of episodes needed to visit all ataten pairs at least once with probability at least 1/2 while taking actions at random. This yields a sample complexity bound of L for deterministic MDPs. Other work suggests that may not be necessary to consider rewards all the way to the end of the episode to select an optimal One can define a "effective planning window" of W timesteps ahead that must be considered, resulting in sample complexity bound of T for deterministic MDPs. Finally, Dann et al. [6] detine a "myopic exploration gap" that controls the sample complexity of using e-greedy exploration, a form of naive exploration. However, in Appendix D.4 we demonstrate why their bounds are impractical and often vacuous.
action 24 25 g.
There have been few prior attempts to bridge the RL theory-practice gap. bsuite 126. MDP playground [27], and SEGAR (28) are collections of environments that are designed empirically evaluate deep RL algorithms across various axes of environment difficulty. However, they do not provide theoretical explanations for why environments with varying properties are actually easier or harder. Furthermore, their environments are artificially constructed to have understandable properties. In contrast, we aim to find the mathematical reasons that deep RL succeeds or fails in "in-the-wild" environments like Atari and Procgen. Conserva and Rauber (29 calculate two regret bounds and compare the bounds to the empirical performance of RL algorithms. However, they consider tabular RL algorithms in simple artificial environments with less than a thousand states, while we experiment with deep RL algorithms on real benchmark environments with tens of millions of states.
Our GORP algorithm and the effective horizon are inspired by rollout and Monte Carlo planning algorithms, which have long history (30
31
32
33 24
35 36) These algorithms were used
effectively in Backgammon (2), Go [37], and real- time strategy games (38 before the start of deep RI. GORP and related Monte Carlo rollout algorithms are sometimes referred to as "one-step" or
"multi-step" lookahead. Bertsekas [39 40 suggests that one-step lookahead, possibly after a few

---

steps of value iteration, often leads to fast convergence to optimal policies because it is equivalent to step of Newton's 's method for finding fixed-point of the Bellman equation 41 42 Our analysis suggests the success of deep RI. is due to similar properties. However, we go beyond previous work by introducing GORP, which approximates step of policy iteration in model-free RI.-a setting where on-line planning approaches are not applicable. Furthermore, unlike previous work in Monte-Carlo planning, we combine our theoretical contributions with extensive empirical analysis to verify that our assumptions hold in common environments.
4 The BRIDGE Dataset
In order to assess how well existing bounds pre- diet practical performance, and gain insight about novel properties of MDPs that could be predictive, we constructed BRIDGE (Bridging the RL Interdis- ciplinary Divide with Grounded Environments), a dataset of 155 popular deep RL benchmark environ- ments with full tabular representations. One might assume that the ability to calculate the instance- dependent bounds we just presented in Section 3 already exists; however, it turns out that for many real environments even the number states is unknown! This is because significant engineering effort is required to analyze large-scale environments and calculate their properties.
Acting greedily with respect Q is optimal?
PPO finds optimal policy in S 5M timesteps?
Yes
No
Yes No
80 MDPs
24 MDPs
15 MDPs
36 MDPs
Table 1: The distribution the MDPs in our BRIDGE dataset according to two criteria: first, whether PPO empirically converges to optimal policy in 5 million timesteps, and second, whether acting greedily with respect to the Q-function of the random policy is optimal. We find that a surprising number of environments satisfy the latter property, especially when only considering those where PPO succeeds.
In BRIDGE, we tackle this problem by computing tabular representations for all the environments using a program that exhaustively enumerates all states, calculating the reward and transition functions at every state-action pair. We do this for 67 Atari
games from the Arcade Learning Enivornment [4), 55 levels from the Procgen Benchmark 44 and 33 gridworlds from MiniGrid [1] (Figure 5). The MDPs have state space sizes S ranging across 7 orders of magnitude from tens to tens millions, 3 to 18 discrete actions, and horizons 7 ranging from 10 to 200, which are limited in some cases to avoid the state space becoming too large. See Appendix B for the full details of the BRIDGE dataset.
A surprisingly common property To motivate the effective horizon, which is introduced in the next section, we describe a property that we find holds in many of the MDPs in BRIDGE. Consider the random policy rand which assigns equal probability to every action in every state. i.c., araand (a 8) = 1/A. We can use dynamic programming on a tabular MDP to calculate the random policy's Q-function Q=""! We denote by I[Q=""") the set of policies which act greedily with respect to this Q-function; that is,
(Q²T -
(s(s) arg max Q7 "7" (s.
a
Perhaps surprisingly, we find that all the policies in II(Q""") are optimal in about two-thirds of the MDPs in BRIDGE. This proportion is even higher when considering only the environments where PPO empirically succeeds in finding an optimal policy (Table Thus, it seems that this property may be the key to what makes many of these environments tractable for deep RL.
5 The Effective Horizon
We now theoretically analyze why RL should be tractable in environments where, as we observe in BRIDGE, it is optimal to act greedily with respect to the random policy's Q-function. This leads to more general measure of an environment's complexity for model-free RL: the effective horizon.
Our analysis centers around a simple algorithm, GORP (Greedy Over Random Policy), shown in GORP constructs an optimal policy iteratively; each iteration aims to calculate an optimal policy æ; for timestep / = i. In the case where we set k- = 1 and expl Λ rand GORP can solve environments which have the property we observe in BRIDGE. does this at each iteration by simulating random rollouts for each action from the state reached at timestep = i. Then, it
Algorithm| I
5

---

averages the m rollouts' returns to obtain Monte Carlo estimate of QTTn! for each action. Finally, it greedily picks the action with the highest estimated Q-value.
Besides taking advantage the surprising property found in BRIDGE, GORP has other properties which help us bridge the theory-practice gap in RL. It explores ran- domly, like common deep RL algorithms, meaning that can give us insight into why random exploration works much better than the worst-case given Theorem 2.1 Also, unlike other RI. algorithms, it has cleanly separated exploration and learning stages, making it much easier to analyze than al- gorithms in which exploration and learning entangled.
Algorithm 1 algorithm, used to motivate the effective horizon.
The Greedy Over Random Policy (GORP)
1: procedure GORP(K, m, )
2:
for i = 1,-.., do
3:
for d E .A* do
4:
sample episodes following TI.... TT-1, then actions din+h-1. and finally x -
5:
Qi(8i, a1ith-1) EE= E "R((,,
6:
end for
7:
(s()) + arg Ea
max n Qi 0111444--))
Furthermore, GORP extensible beyond environments satisfying the property we found in BRIDGE. First, it can solve MDPs where one may have to apply few steps of value iteration the random policy's function before acting randomly. Second, it can use an "exploration policy" xp different from the random policy nund These two generalizations are captured in the following definition. In the definition, we use the notation that a step of Q-value iteration transforms a Q-function Q to Q' = QVI(Q), where
end for 9: return π
8:
10:
end procedure
(s(s = Rr(s, a) + max Q4+1 (f(s,a),
a'EA
Definition 5.1
rand unless otherwise Given an exploration policy n (x
noted), let Q² QT"" and Q++1 (Q)(("))) =i.i=1,,.... T We say an MDP k-QVI-solvablee for some l E [T] if every policy in II(@*) is optimal.
We will see that running GORP with & > will allow it to find an optimal policy in MDPs that are k-QVI-solvable. Although the sample complexity of GORP scales with A&, we find that nearly all of the environments in BRIDGE are k- k-QVI-solvable for very small values of i (Figure 6
We now GORP to define the effective horizon of an MDP. Note that the total number of timesteps sampled by GORP with parameters and m is A = A aog Thus, analogously to how the horizon T appears in the exponent of the worst-case sample complexity bound O(TA²), define the effective horizon as the exponent of in the sample complexity of GORP:
Definition 5.2 (Effective horizon). Given E [T), let H₃ = + log ma, where my is the minimum value of m needed for Algorithm with parameter k to return the optimal policy with probability at least 1/2, or oo if no value of m suffices. The effective horizon is H ming Hy.
By definition, the sample complexity of GORP can given using the effective horizon: Lemma 5.3. The sample complexity of GORP with optimal choices of k and m is 2 AH.
As we noted in the introduction, when H < T. as we find is often true in practice, this is far better than the worst-case bound given in Theorem 2.1 which scales with AT.
Definition 5.2 does not give method for actually calculating the effective horizon. It turns out can bound the effective horizon using a generalized gap notion like those found throughout the RI. theory literature. We denote by A the gap of the Q-function Q* from Definition 5.1 where
A (s) = max (s,
(s,
max a' Earr max, Q (8.a)
aeAA
The following theorem gives bounds on the effective horizon in terms of this gap.
Theorem 5.4. Suppose that an MDP k-QVI-solvable and that all rewards are nonnegative, i.e. R(s, a) 2 for all Let A denote the gap of the Q-function Q² as defined in Definition 5.1

---

Cio(s, Noop) .118
R
R
R
Cio(s, UP) 1196
R O
Cio Dowx) = .16
io Noor)
Pio(s, Ur)
Piots, Dowx) =
(a) Spans rewards: when sequence actions gives reward of and all others give the effective botizon H = (TT).
(b) Dense rewards: when ev- ery optimal action gives ward of I and suboptimal ac- tiens give no reward, the of- lective horizon H = O().
(e) Delayed rewards: when the rewards (b) delayed to the end of the episode. effective hori- zon remains (()).
(d) For the first 50 timesteps the Atari
game Freeway, we can bound H & 10.2. which much lower than horizon 50.
Figure 2: Examples of calculating the effective horizon H using Theorem 5.4 Section 5.1 for the details.
Then
( (+)
Hy S k +
max sE(T],sEST .aEAA
loga
log 6 6log (2T
where 8,Th is the of states visited by some optimal policy at timestep i and Vf (s) mmax, VT((s is the optimal value function.
A full proof of Theorem 5.4 is given in Appendix A Intuitively, the smaller the gap (s)s,, the more precisely we must estimate the Q-values in GORP in order to pick an optimal action.
The GORP algorithm is very amenable to theoretical analysis because it reduces the problem of finding an optimal policy the problem of estimating several k--step Q-values, each of which is a simple mean of i.i.d. random variables. There are endless tail bounds that can be applied to analysis of GORP; we use some of these to obtain even tighter bounds on the effective horizon in Appendix C
Why should the effective horizon, which is defined in terms of our GORP algorithm, also explain the performance of deep RL algorithms like PPO and DQN which are very different from GORP? In Appendix B we present two algorithms, PG-GORP and FQI-GORP, which are more similar to PPO and DQN but whose sample complexities can still be bounded with the effective horizon. We also give additional bounds on the effective horizon and lower bounds on sample complexity.
5.1 Examples of the effective horizon
To gain some intuition for the bound in Theorem consider the examples in Figure MDP (a) has extremely sparse rewards, with a reward of only given for a single optimal action sequence. However, note that this MDP is still 1-QVI-solvable by Definition in Theorem 5.4 is at = 1 with the optimal action, where 1 a) = 1/AT-1 V*)s) = 1, and (s(ss 1 A
[.1 The maximum of the bound
Ignoring logarithmic factors and constants gives S 1 log A T.. That is, in the case of MDP (a), the effective horizon is no better than the horizon.
Next, consider MDP (b), which has dense rewards of 1 for every optimal action. Again, this MDP I-QVI-solvable. The maximum in the bound obtained at t = 1 and the optimal action with (s, < 2, Vs) T, and the gap A (s, a) 2 1. Again ignoring logarithmic factors gives in this H < 1 log T Ó(1). In this case, the effective horizon is much shorter than the horizon, and barely depends on it! This again reflects our intuition that in this case, finding the optimal policy via RL should be much easier.
MDP (c) is similar to MDP (b) except that all rewards are delayed to the end of the episode. this
case, the Q function is the same as in MDP (b) so the effective horizon remains Ō(1). This may seem counterintuitive since needs to consider rewards T timesteps ahead to act optimally. However, the way GORP uses random rollouts to evaluate leaf nodes means that it can implicitly consider rewards quite far in the future even without needing to exhaustively plan that many timesteps ahead.
Finally, consider MDP (d), the first 50 timesteps of the Atari game Freeway, which included in the BRIDGE dataset. This MDP is also I-QVI-solvable and the maximum in the bound is obtained in the state shown Figure 2d]at timestep = 10. Plugging in the Q values shown the figure gives H < 10.2, which is far lower than the horizon T = 50. The low effective horizon reflects how this MDP much easier than the worst case practice. Both PPO and DQN are able to solve with a sample complexity of less than 1.5 million timesteps, while the worst case bound would suggest
7

---

sample complexity greater than 50 x /20/2 ~ 10a6 timesteps!
Comparison to other bounds Intuitively, why might the effective horizon give better sample complexity bounds than previous works presented in Section 33 The MDP in Figure 2b preseentss a problem for the covering length and UCB-based bounds, both of which are (2(AT) ). The exponential sample complexity arises because these bounds depend on visiting every state in the MDP during training. contrast, GORP doesn't need visit every state find an optimal policy. The effective horizon of Ō(1) for MDP (b) reflects this, showing that our effective horizon-based bounds can actually be much smaller than the state space size, which is on the order of A for MDP (b).
The effective planning window (EPW) does manage to capture the same intuition as the effective horizon in the MDP in Figure in this case, W = 1. However, the analysis based on the EPW is unsatisfactory because it entirely ignores rewards beyond the planning window. Thus, in MDP (c) the EPW W = T, making EPW-based bounds no better than the worst case. In contrast, the effective horizon-basedd bound remains the same between MDPs (b) and (c), showing that it can account for the ability of RL algorithms to use rewards beyond the window where exhaustive planning is possible.
6 Experiments
We now show that sample complexity bounds based on the effective horizon predict the empirical performance of deep RL algorithms far better than other bounds in the literature. For each MDP in the BRIDGE dataset, we run deep RL algorithms to determine their empirical sample complexity. We also use the tabular representations of the MDPs to calculate the effective horizon and other sample complexity bounds for comparison.
Deep RL algorithms We run both PPO and DQN for five million timesteps for each MDP in BRIDGE, and record the empirical sample complexity (see Appendix forr hyperparameters and experiment details). PPO converges to the optimal policy in 95 of the 155 MDPs, and DQN does in 117 of 155. At least one of the two finds the optimal policy 119 MDPs.
Sample complexity bounds We also compute sample complexity bounds for each MDP in BRIDGE. These include the worst-case bound of T TA"" from Theorem 2.1 the Effective-horizon-basee bound of A from Lemma 5.3 as well as three other bounds from the literature, introduced in Section and proved in Appendix D the UCB-based bound SAT' the wwvering-length-aaeee bound TL, and the effective planning window (EPW)-based bound of 2
Evaluation metrics To determine which sample complexity bounds best reflect the empirical
performance of PPO and DQN, we compute a few summary metrics for each bound. First, we measure the Spearman (rank) correlation between the sample complexity bounds and the empirical sample complexity over environments where the algorithm converged to the optimal policy. The correlation (higher is better) is useful for measuring how well the bounds can rank the relative difficulty of RL in different MDPs.
Second, we compute the median ratio between the sample complexity bound and the empirical sample complexity for environments where the algorithm converged. The ratio between the bound Nuound and empirical value Nump is calculated as max max/NNoumdl Moooonn//eeppp Nemp / /Nound) median ratio of 10 indicates that half the sample complexity bounds were within a factor of 10 of the empirical sample complexity. Lower values indicate a better bound; this metric is useful for determining whether the sample complexity bounds are vacuous or tight.
). For instance,
Finally, we consider the binary classification task of predicting whether the algorithm will converge at all within five million steps using the sample complexity bounds. That is, we consider simply thresholding each sample complexity bound and predicting that only environments with bounds below the threshold will converge. We compute the area under the ROC curve (AUROC) for this prediction task as well as the accuracy with the optimal threshold. Higher AUROC and accuracy both indicate a better bound.
Results The results of our experiments are shown in Table 2 The effective horizon-based bounds have higher correlation with the empirical sample complexity than the other bounds for both PPO and DQN. While the EPW-based bounds are also reasonably correlated, they are significantly off in absolute terms: the typical bound based on the EPW is 3-4 orders of magnitude off, while the effective horizon yields bounds that are typically within 1-2 orders of magnitude. The SCB-based
8

---

PPO
DQN
Bound
Correl.
Median ratio
AUROC
Acc.
Correl.
Median ratio
AUROC
Acc.
Worst-case (T A4' /2)
0.24
7.2
10
0.57
0.63
0.15
5.5 10
0.67
0.76
Covering length (TL)
0.35
6.3
10
0.78
0.72
0.27
3.9 10
0.86
0.85
EPW (T
0.69
10
0.78
0.75
0.58
8.0
10
0.88
0.85
UCB (SAT)
0.26
20
0.68
0.67
0.31
31
0.67
0.77
Effective horizon (T
0.81
0.92
0.86
0.74
0.92
0.86
Other deep RI. algorition GORP empirical
0.77
2.3
0.84
0.85
0.77
2.3
0.86
0.99
0.79
7.3
0.77
0.82
0.65
0.80
0,94
Table 2: Effective horizon-based sample complexity bounds are the most predictive of the real performance of PPO and DQN according to the four metrics describe in Section The effective horizon bounds about as good at predicting the sample complexity of PPO and DQN as one algorithm's 's sample complexity at predicting the other's.
PPO
DQN
PPO
Bound EPW
Correl.
Ratio
Correl.
Ratio
Bound
Correl.
Ratio
0.20
2.1
0.70
12
Covering length
-0.36
2.5
10*
Effective horizon
0.48
2.4
0.35
12
Effective horizon
0.57
2.7
Other bounds
0.00
1.3
0.00
1.9
Other bounds
0.00
2.2
(a) Reward shaping.
(b) Initializing with policy trained on human data or transferred from similar environments.
Table 3: The effective horizon explains the effects of reward shaping and initializing with a pretrained policy by accurately predicting their effects on the empirical sample complexity of PPO and DQN. Correlation and median ratio are measured between the predicted change in sample complexity and the empirical change. See Section for further discussion.
bounds are somewhat closer to the empirical sample complexity, but are not well correlated; this makes sense since the UCB bounds depend on strategic exploration, while PPO and DQN use random exploration. Finally, the effective horizon bounds are able to more accurately predict whether PPO or DQN will find an optimal policy, as evidenced by the AUROC and accuracy metrics.
As an additional baseline, we also calculate the four evaluation metrics when using the empirical sample complexity of PPO predict the empirical sample complexity of DQN, vice-versa, and when using the empirical sample complexity of GORP to predict PPO or DQN's performance (bottom two rows of Table 2). While these are not provable bounds, they provide another point of comparison bounds correlate about as well with PPO and DQN's sample complexities as they do with each other's. The empirical performance of GORP is typically even closer to that of PPO and DQN than the effective horizon-based bounds.
for each metric. The effective horizon-basse
Reward shaping, human data, and transfer learning In order for RL theory to be useful practically, should help practitioners make decisions about which techniques to apply in order to improve their algorithms' performance. We show how the effective horizon can be used to explain the effect of three such techniques: reward shaping, using human data, and transfer learning.
Potential- reward shaping [45] is classic technique which can speed up the convergence of RL algorithms. It is generally used transform sparse-reward MDP like the one in Figure 2a to
dense-reward MDP like in Figure 2b without changing the optimal policy. If the effective horizon is good measure of the difficulty RL an environment, then should be able to predict whether (and by how much) the sample complexity of practical algorithms changes when reward shaping is applied. We develop 77 weward-shaper versions of the original 33 Minigrid environments and run PPO and DQN. Results in Table Bal show the effective horizon accurately captures the change in sample complexity from using reward shaping. We use similar metrics to those in Table the correlation between the predicted and empirical ratio of the shaped sample complexity to the unshaped sample complexity, and the median ratio between the predicted change and the actual change.
case, covering length, and UCB don't it even depend on the reward function. The EPW does depend on the reward function and captures some of the effect of reward shaping for DQN, but does worse at predicting the effect on PPO. In comparison, the effective horizon does well for both algorithms, showing that can accurately capture how reward shaping affects RL performance.
Out of the five bounds we consider,

---

Beam Rider
Breakout
Enduro
Pong
Qbert
Seaquest
Space Invaders
3k
20
20k
2k
2k
2
250
lk
-20
50M 0
50M
50M
0
50M
50M
0
50M
50M
GORP
PPO
DQN
Figure 3: Learning curves for PPO, DQN, and GORP on full-horizon Atari games. We use 5 random seeds for all algorithms. The solid line shows the median return throughout training while the shaded region shows the range of returns over random seeds.
Another tool used to speed up RL is initializing with pre-trained policy, which is used practically to make RL work on otherwise intractable tasks. Can the effective horizon also predict whether initializing RL with a pre-trained policy will help? We initialize PPO with pre-trained policies for 82 of the MDPs in BRIDGE, then calculate new sample complexity bounds based on using the pre-tru pre-trained policies
exploration policy . Table 3b shows that the effective horizon accurately predicts the change in sample complexity due to using a pre-trained policy. Again, three bounds-worss case, EPW, and UCB-do not depend on the exploration policy all, while the covering length gives wildly inaccurate predictions for its effect. In contrast, the effective horizon is accurate at predicting the changes in sample complexities when using pre-trained policies.
Long-horizon environments We also perform experiments on full-length Atari games to evaluate the predictive power of the effective horizon in longer-horizon environments. It is intractable to con- struct tabular representations of these environments and thus we cannot compute instance-dependee sample complexity bounds. However, it is still possible to compare the empirical performance of PPO. DQN, and GORP. the performance of GORP is close to that of PPO and DQN, then this suggests that the effective horizon, which is defined in terms of GORP, in these environments as well. Figure 3 compares the learning curves PPO, DQN, and GORP in deterministic versions of the seven Atari games from Mnih et al. 446 (see Appendix [F. for details). GORP performs better than both PPO and DQN in two games and hetter than at least one deep RL. algorithm in an additional three games. This provides evidence that the effective horizon is also predictive of RL performance in mog-hooizoon environments.
explain RL performance
Discussion
Overall, our results suggest the effective horizon a key measure of the difficulty of solving an MDP via reinforcement learning. The intuition behind the effective horizon presented in Section 5 and the empirical evidence in Section support its importance for better understanding RL.
Limitations While we have presented thorough theoretical and empirical justification of the effective horizon, there are still some limitations our analysis. First, we focus on deterministic MDPs with discrete action spaces, leaving the extension to stochastic environments and those with continuous action spaces an open question. Furthermore, the effective horizon is not easily calculable without full access to the MDP's tabular representation. Despite this, it serves as a useful perspective for understanding RL's effectiveness and potential improvement areas. An additional limitation that the effective horizon cannot capture the performance effects of generalization the ability to use actions that work well at some states for other similar states. For an example where the effective horizon fails to predict generalization, Appendix G.1 However, the effective horizon is still quite predictive of deep RL performance even without modeling generalization.
Implications and future work We hope that this paper helps to bring the theoretical and empirical RL communities closer together in pursuit of shared understanding. Theorists can extend our analysis of the effective horizon to new algorithms or explore related properties, using our BRIDGE dataset to ground their investigations by testing assumptions in real environments. Empirical RL researchers can use the effective horizon as a foundation for new algorithms. For instance, Brandfonbrener et al. 47 present an offline RI algorithm similar GORP with 1; our theoretical understanding of GORP might provide insights for improving it developing related algorithms.
10

---

Acknowledgments and Disclosure of Funding
We would like thank Jacob Steinhardt, Kush Bhatia, Lawrence Chan, Paria Rashidinejad, Ruiqi Zhong, and Yaodong Yu for feedback on drafts as well as Jiantao Jiao and Banghua Zhu for helpful discussions.
This work was partially supported by the Open Philanthropy Project, the Office of Naval Researcher's Young Investigator Program (YIP), and Weill Neurohub. Cassidy Laidlaw is supported by an Open Philanthropy AI Fellowship and a National Defense Science and Engineering Graduate (NDSEG) Fellowship. Stuart Russell is supported by AI 2050 Senior Fellowship from Schmidt Futures.
References
[1] Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel. End-to-end training of deep visuomotor policies. The Journal of Machine Learning Research, 17(1):1334-133 January 2016. ISSN 1532-4435.
[2] David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, loannis Antonoglou, Veda Panneershelvam, Marc Lanctot, Sander Dieleman, Dominík Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Tim- othy Lillicrap, Madeleine Leach, Koray Kavukcuoglu, Thore Graepel, and Demis Hass- abis. Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587):484 489. January 2016. ISSN 1476-4687. doi: 10. 10.1008/nature1690 Bandiera abtest: a @g_type: Na- ture Research Journals Number: 7587 Primary atype: Research Publisher: Nature Publish- ing Group Subject_termi Computational science,Computer science:Reward Subject_tenn id:
URL
hnttps://ww http:://wwwnaauue.em.mmem nature. com/ artiictsticceeeeeeeeeeeeeaeeeeet www.eeeeeeaaneeeneeeeeeee
[3] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, loannis Antonoglou. Helen King. Dharshan Ku- maran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):22-5533 February 2015. ISSN 1476-4687.
doi: 11008/nature1122/0 Bandiera_abien aabtast a Cg_type: Nature Research Journals Number: 7540 Primary_atype Re- search Publisher: Nature Publishing Group Subject_ term: Computer science Subject_term id: computer-science.
URL hhttps://wwt http///wwwwtt.t..ttttttteete nature com/ artiicees/. wtw.aaattttattatteeeeeeeeeaeaaee wwwpe//atttteeeeee..
[4] Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. Minimax Regret Bounds for Reinforcement Learning. arXiv:/703: 703.05449 [cs, stat), July 2017. URL htth::ttp///xii/ org/ abs/1703. 05449)
arXiv: 1703.05449.
[5] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I. Jordan. Is Q-learning Provably Efficient? arXiv: 0006500 [cs, math, stat), July 2018. URL htttp://axxii.rrrr /bs/ arXiv:
[6] Chris Dann, Yishay Mansour, Mehryar Mohri, Ayush Sekhari, and Karthik Sridharan. Guaran- tees for Epsilon- Greedy Reinforcement Learning with Function Approximation. In Proceedings of the 39th International Conference on Machine Learning, pages 4666-4689 PMLR, June 2022. URL
.ttml
ISSN: 2640-3498.
[7] 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 hww.vooggaaaae abs// 1805. 09045 arXiv:1805.009. 09045 [cs, stat].
[8] Dhruv Malik, Aldo Pacchiano, 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, pages 7412-7422. PMLR, July 2021. mlr. wwtpss//v133/malak222..... httt:httt://ooooooo httpooeedinnnnl..ppprrrr////////
html
ISSN: 2640-3498.
[9] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal Policy Optimization Algorithms. arXiv: 1707.06347 [cs], August 2017. URI, htRI. httt::://rxiiyy
org/abs/1707.oes arXiv: 7737.06347.

---

[10] Matteo Hessel, Joseph Modayil, Hado van Hasselt, Tom Schaul, Georg Ostrovski. Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining Improve- ments in Deep Reinforcement Learning, October 2017. htRp:t/tt:/// pttttp://axxv..oot org/ abs///b///// 1710 02298 arXiv:1710.02298 [es].
[11] Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy Lillicrap, and David Silver. Mastering Atari, Go, Chess and Shogi by Planning with Learned Model. Nature, (88(783))6604-666 December 2020. ISSN 0028-0836, 1476-4687. doi: 10. 0038//41586-020-9555 [cs, stat].
URL httt:://aaratt org/ /ttb//911..t.. 08265
arXiv:1911.0226,
[12] Yuval Tassa, Yotam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden, Abbas Abdolmaleki, Josh Merel, Andrew Lefrancq, Timothy Lillicrap, and Martin Riedmiller. Deep.Mind Control Suite, January 2018. URL/http://// /ttp::/t///xtt /ttp///aavvvv/// werxiv.org/ro htgg/bbs/8811 00690 1rXi:1100.00690 [cs].
[13] Emanuel Todorov, Tom Erez, and Yuval Tassa. MuJoCo: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5023, October 2012. doi:
ISSN: 2153-0866.
[14] Maxime Chevalier-Boisee Boisvert, Lucas Willems, and Suman Pal. Minimalistic Gridworld Envi- romment for OpenAl Gym, 2018. URL htttps///githii www.ooooommc....aecacc.oc.o. htap///ggmmminiigi.. Publication Title: GitHub repository.
[15] Younggyo Seo, Lili Chen, Jinwoo Shin, Honglak Lee, Pieter Abbeel, and Kimin Lee. State Entropy Maximization with Random Encoders for Efficient Exploration. In Proceedings of the 38th International Conference on Machine Learning, pages 9443-94499 -9444. PMLR, July 2021.
mlr. httppa/g.........s..eeeeeeeeeeee
wwwpprressvv.eee v139/ seo21a. http://119////e.leee
html html
ISSN: 2640-3498.
[16] Michael Dennis, Natasha Jaques, Eugene Vinitsky, Alexandre Bayen, Stuart Russell, Andrew Critch, and Sergey Levine. Emergent Complexity and Zero-shot Transfer via Unsupervised Environment Design. In Advances in Neural Information Processing Systems, volume 33, pages 13049-13061. Curran Associates, Inc., 2020. URL https: wwwpiiinnnnnnnuppp.e. www. ips..ps.. cc/ html
[17] Maxime Boisser, Dzmitry Bahdanau, Salem Lahlou, Lucas Willems, Chitwan Saharia, Thien Huu Nguyen, and Yoshua Bengio. BabyAI: A Platform to Study the Sample Efficiency of Grounded Language Learning, December 2019, URL http:::///aaxi org/abs/ 1810. 1810.08272 arXiv: 181.082222 [cs].
[18) Sham Machandranath Kakade. On the sample complexity of reinforcement learning. PhD thesis, University of London, University College London (United Kingdom), 2003.
[19] Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, John Langford, and Robert E. Schapire. Contextual Decision Processes with low Bellman rank are PAC-Learnable. In Proceedings of the 34th International Conference Machine Learning, pages 1 1704-1713 PMLR. July 2017. URL hattps::/proceee
mlr, prress/v7o/jji wwtp://////nn..///// html
ISSN: 2640-3498.
[20] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael Jordan. Provably Efficient Reinforcement Learning with Linear Function Approximation. arXiv:1907, 7907.05388 [cs, math, stat], August
2019. UR..tttp: /ttp:ii//axiv....// org/ /9w.b///////..... 05388
arViv: 903.805388
[21] Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear Classes: A Structural Framework for Provable Generalization in RL. In Proceedings of the 38th International Conference on Machine Learning, pages 2826-2836. PMLR, July 2021. URL. 2640-3498.
.mw.iiss....................m..m h....ppres//v13//uues (1w.13///dd11.... html ISSN:
[22] 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, pages 13406-13418. Curran As- sociates, Inc., 2021. URL. 4tfe4680887220055111aa2222113333 htg.aaadde..aaaaoooooooe---ereed Abstract.html
12

---

[23] Ronen I. Brafman and Moshe Tennenholtz. R-MAX- A General Polynomial Time Algorithm for Wear-Optimi Reinforeement Learning. Journal of Machine Learning Research, 3(Oct):213-
231, 2002. ISSN ISSN 1533-7928. URRLhttps:/// //www jmlr hwt..r.or//pppprr////braaaaaaaaa
html
[24] Michael Kearns, Yishay Mansour, and Andrew Y. Ng. A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes. Machine Learning, 49(2): 193-
208, November 2002. ISSN 1573-0563. doi: 10. N0.1023/A:10079932497771 URL. https
//doi.org/10 1023 A: 1017932429737
[25] Nan Jiang, Satinder Singh, and Ambuj Tewari. On structural properties of MDPs that bound loss due to shallow planning. In Proceedings of the Twenty-Fite Fifth International Joint Conference on Artificial Intelligence, IJCAI' 16, pages 1640-1647, New York, New York, USA. July 2016.
AAAI Press. ISBN 178-1-57735-770-4
[26] Ian Osband, Yotam Doron, Matteo Hessel, John Aslanides, Eren Sezener, Andre Saraiva, Katrina McKinney, Tor Lattimore, Csaba Szepesvari, Satinder Singh, Benjamin Van Roy, Richard Sutton, David Silver, and Hado Van Hasselt. Behaviour Suite for Reinforcement Learning, February 2020. URL http:://tt:::tt org/ httg/abs/19000 03568 WrXiv:1908.053 [cs, stat].
[27] Raghu Rajan, Jessica Lizeth Borja Diaz, Suresh Guttikonda, Fabio Ferreira, André Biedenkapp, Jan Ole von Hartz, and Frank Hutter. MDP Playground: A Design and Debug Testbed for Reinforcement Learning, June 2021. arXiv:1909.07755 [cs, stat].
URL
orgooogg/a.. 07750
[28] R. Devon Hjelm, Bogdan Mazoure, Florian Golemo, Felipe Frujeri, Mihai Jalobeanu, and Andrey Kolobov. The Sandbox Environment for Generalizable Agent Research (SEGAR), March 2022. http:://///xii.. httt:::/aaxxv.org/aa////2222
10351 arXiv:2203. [cs].
[29] Michelangelo Conserva and Paulo Rauber. Hardness in Markov Decision Processes: Theory and Practice, October 2022. BttLhhttp///rxiiie org abs/ 2210 13075 arXiv:2210.13075 [cs].
[30] B. Abramson. Expected-outcome: general model of static evaluation.
IEEE
Transactions
Pattern Analysis and Machine Intelligence,
12(2):182-195
February 1990. ISSN 1939-3539. doi: 10. 10.1109/34.44404
URL https://
ieeexplore ieee /ttp:///ottacc//aaa/a///////oooo woa.a//eraaaaaaaauauuuuaaaa Saw.uujsaaaaaaaAaAAAAA
d7LSY9mmr www.mrriNNghhhhhhh
Conference Name: IEEE Transactions on Pattern Analysis and Machine Intelligence.
Bernd Brügmann. [31]
Monte
Carlo
Go.
1993.
URL https://
www. www.semntiiccchhlaaae.ttttt Sea.an/r..cccllaaaoorrooopp//oap -a-aaailoo---M--alaaaal 1T21BD66668807766777733622288883
[32]
Gerald Tesauro and Gregory Galperin. On-line Policy Improvement using Monte-
Carlo Search. In Advances in Neural Information Processing Systems, volume 9.
MIT Press, 1996. URL https: attps://proceedinng wtwp:occeedinng.nuerieeeeeeeee www.nneuurccceepeeeeee /eerrpps.cc/pppe//19///aaaal htw.://0w0000.ooofaaaaaaaaaaaaaa
html
[33] Dimitri P. Bertsekas, John N. Tsitsiklis, and Cynara Wu. Rollout Algorithms for Combinatorial
Optimization. Journal of Heuristics, 3(3):245-262. December 1997. ISSN 1572-9397. doi: 10.1023/A:1000963228666
URL httpttttt://ooil. 100 1
[34] Hyeong Soo Chang, Michael C. Fu, Jiaqiao Hu, and Steven I. Marcus. An Adaptive Sampling Algorithm for Solving Markov Decision Processes. Operations Research, 53(1):126-139, February 2005. ISSN 00300-64X, doi: 10.
htL/hhtts://ppbooon
inf orforrs..oo wwtp:////////.....o./ 10/228/oprr 1040. 0145, Publisher: INFORMS.
[35] Levente Koesis and Csaba Szepesvári. Bandit Based Monte-Carlo Planning. In Johannes Fümkrann, Tobias Scheffer, and Myra Spiliopoulou, editors, Machine Learning: ECML 2006, Lecture Notes Computer Science, pages 282-293, Berlin, Heidelberg, 2006. Springer. ISBN 978-3-540-46056-5 doi: 10.1007/118718422 29.
13

---

[36] Rémi Coulom. Efficient Selectivity and Backup Operators in Monte-Cate Tree Search. In H. Jaap van den Herik, Paolo Ciancarini, and H. L. M. (Jeroen) Donkers, editors, Computers and Games, Lecture Notes in Computer Science, pages 72-83. Berlin, Heidelberg, 2007. Springer. ISBN 978-3-540-75538- doi: 00000779778--54--5555555-
[37] B. Bouzy and B. Helmstetter. Monte-Carlo Go Developments. In H. Jaap Van Den Herik, Hiroyuki lida, and Ernst Heinz, editors, Advances in Computer Games: Many Games, Many Challenges, IFIP - The International Federation for Information Processing, pages 179. Springer US, Boston, MA, 2004. ISBN 978-0-387-33706-53 doi: 10. 100100079778-0038---55666
11. URL http:: org/ 10.
[38] Michael Chung, Michael Buro, and Jonathan Schaeffer. Monte Carlo Planning in RTS Games. January 2005.
[39] Dimitri Bertsekas. Rollout, Policy Iteration, and Distributed Reinforcement Learning- Athena Scientific, Belmont, Massachusetts, first edition edition, August 2020. ISBN 978-1-886529-077
6.
[40] Dimitri P. Bertsekas. Lessons from AlphaZero for Optimal, Model Predictive, and Adaptive Control. Athena Scientific, March 2022. ISBN 978-1-886529-177
[41] D. Kleinman.
an iterative technique for Riccati equation computa-
tions. IEEE ary 1968.
Automatic Control, 13(1):114-115, Febru- doi: 10.1109/AAC.1988.009908 ieeee..eeeee.eeeeoeeoooeeeeeeeee leee org
Transactions
ISSN 2523.
URL
1otp//e/na./00002277c7a.a. token=
4rW.:Smmngg44AAAAAAASESSSoooeee- Haggggggggaaaanniiaoyaaaaaaaaeaa PKOqZng
VV9ss77gcyyy/WudFr113 Conference Name: IEEE Transactions Automatic Control.
[42] Martin L. Puterman and Shelby Brumelle. On the Convergence of Policy Iteration in Station- ary Dynamic Programming. Mathematics of Operations Research, 4(1):60-69, 1979. ISSN 0364-765X. URL http::tt///// //www jstorr org hrg/sttabbee36889235 Publisher: INFORMS.
[43] M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling. The Arcade Learning Environment: An Evaluation Platform for General Agents. Journal of Artificial Intelligence Research, 47: 253-279, June 2013. ISSN 1076-9757. doi: 10.161 org/ hww.ee//ppp//airrraattlee/eeeeee
URL httph: //ww: jair
[44] Karl Cobbe, Christopher Hesse, Jacob Hilton, and John Schulman. Leveraging Procedural Generation Benchmark Reinforcement Learning, July 2020. URL httt:///axiiv org/
abs/1912. 01588, arXiv:1912.01555 [cs, stat].
[45] Andrew Y. Ng, Daishi Harada, and Stuart Russell. Policy invariance under reward transforma- tions: Theory and application to reward shaping. In In Proceedings of the Sixteenth International Conference Machine Learning, pages 278-287. Morgan Kaufmann, 1999.
[46] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing Atari with Deep Reinforcement Learning, December 2013. URL http::/ /ttp:///aaxvvvv/ wrg.iv.oorrgeeee hwtp://ass//31...m http:///aaxi...orraa///111222 5602 arXiv:1312.5602 [cs].
[47] David Brandfonbrener, William F. Whimey, Rajesh Ranganath, and Joan Bruna. Offline RL Without Off-Policy Evaluation, December 2021. URL http::/tta/trt wwwg/bs/////e/eo/////..oooee arXiv:2106.0890 000999 [cs, stat].
[48] Ronald J. Williams. Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning. In Richard S. Sutton, editor, Reinforcement Learning, The Springer International Series in Engineering and Computer Science, pages 5-32. Springer US, Boston, MA, 1992. ISBN 978- 1 188-1-4465-36111 361-5. doi: 10. 1001007777 161-446111-1888 URL https
//doi 100 1007 10000007777770 4615 3618-5_2
[49] Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-Based Batch Mode Reinforcement Learning. Journal of Machine Learning Research, 6( 6(18)5503,556, 2005. ISSN 1533-7928. URLhttp: pesttp://jml.. org/ hatp/apprs//vve ww/vve/teeaaa..m html
14

---

[50] Martin Riedmiller. Neural Fitted Q Iteration First Experiences with a Data Efficient Neural Reinforcement Learning Method. In João Gama, Rui Camacho, Pavel Brazdil, Alípio M Jorge, and Luís Torgo, editors, Machine Learning: ECMI. 2005, Lecture Notes in Computer Science, pages 317-328, Berlin, Heidelberg, 2005. Springer. ISBN 978-3-540-31692-3 doi: 10. 10.1007/11564096
[51] Irina Shevtsova. On the absolute constants in the Berry-Esseen type inequalities for identi- cally distributed summands, November 2011. URL BUKLlattp///arii..or//bb//// arXiv:111 1.6554 [math].
6554
[52] Eyal Even-Dar and Yishay Mansour. Learning Rates for Q-learning. Journal of Machine Learming Research, S(Dec):1-25. 2003. ISSN ISSN 1533-7928. URL BRL.https:// / /ttpps://ww.r /wwww/www/..k jmlr
org/ httg/paprs///eeeee v/v/ eveddarra.daaa....mm html
[53] Nan Jiang, Alex Kulesza, Satinder Singh, and Richard Lewis. The Dependence Effective Planning Horizon on Model Accuracy. In Proceedings of the 2015 International Conference on Autonomous Agents and Mulliagent Systems, AAMAS 115, pages 1181-1189, Richland, SC, May 2015. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 978- 778-1-4503-341--1
[54] Alex Braylan, Mark Hollenbeck, Elliot Meyerson, and Risto Mikkullanenn. Frame skip is a powerful parameter for learning to play Atari. In Workshops the twenty-ninth AAAI conference on artificial intelligence, 2015.
[55] Timnit Gebru, Jamie Morgenstern, Briana Vecchione, Jennifer Wortman Vaughan, Hanna Wallach, Hal Daumé III, and Kate Crawford. Datasheets for Datasets, December 2021. URL
www.xiv..rg//bbb. 19000 1 [cs].
[56] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang. and Wojciech Zaremba. OpenAl Gym, June 2016. URL htttp://arxiv http:/awwwvi.rr.araaae..aa/oosrt abs/ 01540 arXiv:1606.01540 [cs].
[57] Ruohan Zhang, Calen Walshe, Zhuode Liu, Lin Guan, Karl S. Muller, Jake A. Whritner, Luxin Zhang, Mary M. Hayhoe, and Dana H. Ballard. Atari-HEAD: Atari Human Eye-Tracking and Demonstration Dataset, September 2019. URL http:///// org/abs/ /90b///99..oo. 1903.06754 arXiv:1903.0675: [cs, stat].
[58] Antonin Rafin,, Ashley Hill, Adam Gleave, Anssi Kanervisto, Maximilian Ernestus, and Noah Dormann. Stable-baselines:: Reliable reinforcement learning implementations. The Journal of
Machine Learning Research, 22(1):12348 1348-12335, 2021. URL sttpps///dl. acm. org/doi.
abs/10. 5555/35462555 3546526
Publisher: JMLRORG.
[59] Antonin Raffin.
RL Baselines3 Zoo, 2020, URL htttp://gitthb. com/ RM/
rl --baselinesss 200 Publication Title: GitHub repository.
15

---

Appendix
A Proofs of main results
A.1 Proof of Theorem 2.1
Theorem 2.1, There is an RL algorithm which can solve any deterministic MDP with sample complexity N S TT A² /2). Conversely, for any RL algorithm and any values of T and A, there must be some deterministic MDP for which its sample complexity N 2 T([A") /2) - 1).
Proof. Consider the following RL algorithm:
procedure EXHAUSTIVESEARCH
T 4 Shuffle((A")
T is an array of size [AT/2] for i
1..... " /2| do
run one episode, taking the actions in T[*]
Jh. - - R((s; 0t) end for
8- f- arg max, [i]
return the policy which takes the actions in T[t*]
end procedure
Since the MDP is deterministic, an RL algorithm only needs to find an optimal sequence of ac- tions. Clearly, there is least a 1/2 chance that some optimal sequence of actions in the first [AT /2] elements of T. If this is the case, then ExHAUSTIVESEARCH will return an optimal pol- icy corresponding to that optimal sequence. Since the number of environment timesteps taken by ExHAUSTIVESEERCH is equal to T[A*/2], /2], we have that N < TTA""/2]
For the converse, fix A and T along with any RL algorithm. Consider of states indexed by sequences of actions of length 0 to T:
S (SaLi | O...... T,a,, E A'}.
Then, define a transition function
[(Saye: a) 801150
Now consider AT different MDPs which share the state space S and transition function f. differing only in their reward functions:
[Marr a1.T E 3 where the MDP Maie has R(so.. a)
{
01:6; a = 01:7
otherwise.
That is, each MDP has single optimal sequence of actions that gives reward the final timestep; all other rewards are 0.
Let the RL algorithm in question take in some source of randomness and output policy n. (a 8; 2, M) after n timesteps MDP M. Now suppose by way of contradiction the sample complexity of the algorithm is less than T([A* / -1) in all MDPs in M. By our definition of sample complexity, this means that
P. (
T(A" /21 (s), =1) 2 1/2.
WM M
(Te
deterministic, so let M22 be the sequence of actions that म. /2[Aa//2129 (a s; s; 2, .M) takes if it is optimal, and let it be any suboptimal sequence of actions if the policy is suboptimal. We can rewrite ① as
Clearly a policy can only be optimal in these MDPs
VMair M P. (T(2,, (ar.r) air) 2 1/2.
Letting Unif(AA)) define a uniform distribution over action sequences of length T, this implies
P Unit (7(2.
a1.)) 1/2
which means that there must be some particular such that
P PaIT)UM((AA))) (T(2, Maier) = 01.1
2 1/2
Karr E AT 7(2, Manor) = a1.71
2 AT
(2)
16

---

Given that the RL algorithm is now deterministic due to the fixed 2, we will prove that the LHS of (2) must be less than or equal to [A" /2] This can be shown via induction. For the first episode. the algorithm must take the same actions in every MDP since all MDPs give zero reward until the final action (so there no way to distinguish them). After the first episode, only one MDP can be distinguished from the others: the one corresponding to the action sequence taken in the first episode, which has reward instead of O. Thus in the remaining A 1 MDPs the algorithm must take the same actions in the second episode. Continuing this argument shows that after episode TA//2 [ 2. the algorithm must still be unable to distinguish between A ([A") /2 2) [A] + 2 of the MDPs, and so MM must be the same for all MDPs in this set. Since all of these MDPs have different optimal action sequences, 7 (z, (M) can only be optimal in one of them. Thus ((z, must be suboptimal in at least AA" /2] + MDPs, which means the LHS of (2) must be at most A" (LA4 +
TA /2
( gives [AT/2] - 2 /2/2, which is contradiction. Thus, the sample complexity of the RL algorithm must be at least [([A"/2) 1).
Combining this with
A.2 Proof that k = ' in the worst case
Lemma A.1. Let Q' Q= Qi+1 _ Section 4 Then,orr any horizon T and number of actions A 2 2 there is an MDP such that no policy in I1(Q")) is optimal for T.
QVI(Q") for i 2....,T, and II( be defined as in
Proof. As in the proof of Theorem 2.1 define an MDP where every action sequence leads to a different state. Pick an arbitrary action sequence a1.T, and let the reward of taking the final action in that sequence be 1:
R(s R( QT) =
Now take some action di # 01 and let the reward for taking that action at the beginning of an episode be 3/4:
R(s1, d1) = 3/4.
Let the rewards for all other state-action pairs be O. We will show by induction that
Qi( (4) Amax
and (11,,a1) = 3/4.
The left half of (3) is clearly true for = 1, since the random policy will take all action sequences following the 1-th optimal action with probability 1/A"-tt and exactly one of those gives reward The right half also clear since following di gives immediate reward 3/4 and then no reward afterwards.
For the inductive step, we begin with the left half of assume it holds for some i. By the definition of Q-value iteration, we have for / <T
Q (8mm-11: az)
R(sara 1: 1: + max 0841(8011900
-0+
Amax(T (mmxx(T((++1))) (6+1))11++)
and for t = T,
Q (Sair-1, (T) R(Sa) aT) =1 4 -mx(TT((+1)-+11000
1
(i) because only one action timestep f can have Q-value greater than 0, since only one action sequence leads to reward after taking 0₁. For the right half of 3 we have
"st a1) = R(s1, ai) max (5 a) 3/4 - 3/4. which is due to no reward being possible after taking af at the first timestep.
Given that 3 holds for i = 1, , T, it is easy to see that for i < T, any π E II(2") will take di on the first timestep, since
3 (s1, A ス
(1 01) A Amax (T
This means that will be suboptimal, since a is the only optimal action at 1.
17

---

A.3 Proof of Lemma 5.3
Lemma 5.3. The sample complexity of GORP with optimal choices of k and is T A.
Proof. Recall the definition of effective horizon:
Definition 5.2 (Effective horizon). Given [T') let 11, k log my, where my is the minimum value of m needed for Algorithm 2 with parameter k to return the optimal policy with probability ar least 1/2, or oo no value of m suffices. The effective horizon H ming H3.
Let E arg ming Hx- Then by Definition 5.2 GORP (Algorithm I with parameters k my will converge to optimal policy with probability at least 1/2. Clearly, Algorithm interrcts with the environment for 7'' iterations, each of which require evaluating A action sequences with my episodes of T timesteps each, for a total of
A my = A = A
timesteps. Thus the sample complexity of GORP satisfies NGORP S A
Now, suppose by way of contradiction that NGORP < A² Then this must mean that there are parameters W', m' such running GORP with these parameters converges optimal policy with probability at least 1/2, and
K' + logg m' < k + loga mk-
By Definition 5.2 this means that my I m', and thus
H min H log my S k log my < log my H
which is clearly contradiction. Thus, it must be that NGORP A
A.4 Proof of Theorem 5.4
Theorem 5.4. Suppose that an MDP k-QVi-solvable and that all rewards are nonnegative, i.e. R(s, a) 2 for all Let A denote the gap of the Q-function Q as defined in Definition 5.1 Then
(O) (s)
H& k
max SEST) .EEA
log
(-)
log 6 log (2TA*),
where S. is the set of states visited by some optimal policy at timestep i and V7 max V77 the optimal value function.
Proof. Let
(8, ()
m log A2
max
I (ET)) .aE
We will show that GORP (Algorithm I converges the optimal policy with probability at least 1/2 given parameters & and m. By Definition 5.2 this means the effective horizon must be at most + log m, which gives the bound in the theorem. More precisely, we will show that GORP converges to policy in IT(Q)) with probability at least 1/2, which must be optimal because of the assumption that the MDP k-O v-Qalesolvable.
First, we will show the following relationship between the k-action Q² values and @+:
max Qf (st, 0.pin 1EAt-1
Q ai, 0:41:++-11..
(4)
We prove that holds inductively. For k 1, is obviously true. Supposing it holds for k; then
Q ++1 (8i, au) QVI(O)) ax)
R(si, a4) max ( ai). amliA
@ R(si, az) + max (141))(ss (s)
= max Qf ai a+41444)
18

---

which shows holds for k + 1. (i) holds due to the inductive hypothesis.
Recall that Algorithm we use (%6% d+i+R-1) to denote the estimated Q-value of the k-action
sequence d-1 Analogously ④4. define
( 04) d
Qi(si, 0i (4115-k1)
to be the maximum estimated Q-value of any action sequence that starts with a,. We can rewrite line 7 of Algorithm T as
(8())) arg max (51, a:).
a'EA
That is, the action that GORP selects for timestep i is chosen from those with the highest values of Q (8s; 0z). Suppose we can show that
P
arg max (s,, a;) S arg max Of (st, 21 2T a,EA
(5)
a,EA
holds for each i [T]. Then by union bound,
a,EA (T(s;) E arg max Q5 (s).
Vi E [T]
(6)
This implies that x e II())), which is the desired result.
It remains show that 55) holds. We will actually prove the bound assuming that s; S This is
still sufficient to imply (6) since one can inductively assume that previous actions are optimal. We
write (5) equivalently
3a, E arg max Q (8s as & arg max ( a.) S IP
(7)
a.EA
a.E.
21
Let - arg max. Ea Q (s 1x)+h-1) be chosen arbitrarily. By (4). this implies that at E arg maxa,ed EA Q (si, Then
Da; E arg max Q (si, ai) at $ arg max () (+)..)) aEE
aEE
<
P
Ioi & arg max Qf (8t, (si, Q (8i; at)
aEA
$ P Doy & arg max Q (st, at), a441+t4-1 A Qi(sh, ai 0411-111)) 2 Qi (istb-1)) aEA
P (Q((s)) a, 0411--1 (4LR-1) 2 (0s,
(8)
a, aagg maxa, a (.
Consider single term of the sum in arg ma Q az), we know that
8
By the definition of the gap and the fact that as
Q+ a.) S Q7 az) - (s.).
Combining this with implies that
Q7 (si, a S Q7 C (s
(s,, ( - Q (8;, dxstk-1) 2 (s,).
(9)
Now, consider the random variables Q1(s;, aj 0:41:-11) and Qi(s,, of.4411) Let X, 2t at) be the discounted reward from timestep in the jth episode used to estimate Qi(s), 0,, a(t1:+k-1): let Y3 be the equivalent for estimating Qu(sta) 1). Then we can write
1
m X,
m Σ Y
Qi(8i, at a ((41444-1))
((0t,) m
m
By the definition the optimal value function V* and the assumption that all rewards are nonnegative, we have that X,, Y3 E [o, V (s:)). I. We also know that the expectations of the X; and Y, are bounded:
E[X,] = Q (ss, dx)+h-1) < Q (Si, as) S max (s,, az).
E Y = Q7 (s, 0h Q (st a;) S max Q (s;, a;).
a;
19

---

The variance of a random variable with mean bounded on an interval (a, 3] is at most This means we can bound the variance of X, and Y, as well:
Var(X,) I max Q7 (8;, a,) (s;))
Var(Y;) I max (s) (si).
Now define
m
m B3
= Qi (st, 0hs44k1) 1) Qi (si, ai a14 0.+1448-1)
Σ Yj X,
m
m j=1
j=1
where 2j = Yj - Xj. Since Xj and Yj are independent,
Var(Z,) Var (X,) + Var(Y,) - 2 max Q (s,, 0,) (s.))
Also define centered versions 2 Zj E Z and 7 a,
Z By 9 E| 2 (s:).
Furthermore, since Y, E [0, V," (s:)]. we also know that [Zyl - V (s,) and [Z] S (7,
Z|Z] < 2V (s:).
We now finally apply Bernstein's inequality to bound the probability of one term in
P (Qi(s,, ai (i,1-)111)) 2 Qi(8i, ((st2-1))
= PZZ 0)
= P < -[(Z)
< <P < (s.))
Var (1) + 3 3 (s;))
g exp
(s:)
(
m (s:)2
S exp
2 maxa, a; + V
(s)2
exp
6max. (s
exp (-log(2TA4))
(10)
2T
Here, (i) is a direct application of Bernstein's 's inequality to the sum 2 = 1 ΣØ= Zy. (ii) uses the m
bound on Var(Z,) = Var 22) and (iii) uses the fact that A (s:) S max., Q. (s,, as) by definition of the gap A/.. Finally, (iv) uses the definition of m; since 8; E 5STT by assumption,
6Q (s;,,,V) Vz)(((()))
m log A*
max G.EA
(+)))
Applying (10 to gives
Ja, E arg max Q (s,, az) a arg max Q (sts (st,ai) a.) P
a.EA
a.E
Σ
A
Earg maxe, eΛ (oe
Σ 2T
which is the only thing left that is needed to complete the proof.
B Additional theoretical results concerning the effective horizon
In this appendix, we present some additional theoretical results concerning the effective horizon. First, we explore two algorithms-one in the style of policy gradient and one similar to fitted Q-iteration- whose sample complexities can also be bounded by a quantity related to the effective horizon. Then we show conditions under which the effective horizon small, as well as information-theoree lower bounds for the sample complexity of RL in terms of the effective horizon.
20

---

B.1 PG-GORP and FQI-GORP
The two algorithms we introduce in this section, PG-GORP and FQI-GORP, can be viewed bridge between GORP, which we use define the effective horizon, and PPO and DQN, the deep RI algorithms whose performance we predict using the effective horizon in Section They help to explain why the effective horizon is not only useful for understanding the performance of GORP, but also other RL algorithms.
We will actually give sample complexity bounds on PG-GORP and FQI-GORP in terms of the bound Theorem 5.4 rather than the effective horizon itself. Supposing that the MDP is k-QVI-solvalle,, define
(Q)(s logg 6 log (2TA*). (+(3)
max H sESS) .aAA
loga
Our bounds will also depend on quantity measuring how far the exploration policy n is from the uniformly random policy tand
rand
π
expl
max (t.s.a)e X T.
eexpl ())
1 in the case when expl
π rund
and increases as the smallest probabilities "xpl assigns
rigil
to actions becomes smaller.
We now introduce the first algorithm, PG-GORP.
Algorithm 2 The PG-GORP algorithm.
1: procedure PG-GORP(m)
2: < expl.
3:
for fori= 1, .,..,, . do
4: Sample m episodes following π.
5: for E A do
6:
oaz (.(a s;) t Σラ= T.(a end for
Ete 7- RR()
7:
8: (8:)) < arg max Vi(a 8i).
9: end for
10: return π
end procedure
PG-GORP resembles the REINFORCE algorithm 48 which gave rise to other policy gradient-based algorithms like PPO. At each iteration, Algorithm first samples number of episodes following its
current policy (line(4). Then, it computes a an approximate gradient over the policy parameters- this case, just the action probabilities ग. 8:) via the so-called "policy gradient theorem," which states
m
T
V (1) x
(e)) log (ag (i)
Σ
2
R(SE,a)) of)
m
1=1
7, Ti 8i) Σ
t((a 8;)
V. 8t).
Then, in line 8 Algorithm 2 applies optimization based its estimate of the gradient. In this case, optimizes until n; assigns all probability to only one action (8())) at s,.
Theorem B.1 (Sample complexity PG-GORP). Suppose that an MDP is 1-QVI-solvable and that all rewards are nonnegative. Then the sample complexity of PG-GORP is at most
rund
27 A 8
21

---

Proof. Let
π mid
Q (s) (s)
rand
m =
A
expl
12A log (2T
max (E[T] aEEA
exppl
We will show that Algorithm 2 converges with probability least 1/2 with this choice of parameter, giving the sample complexity bound in the theorem since the algorithm clearly samples 7 total timesteps from the environment.
Similarly to the proof of Theorem 5.4 we will prove this by showing that with probability at least
1 - 122)2 at each iteration (8;) E arg max.e,A Q7 (st, a). This gives л E (T()"), which by
I-QVI-solvability means æ must be optimal.
Consider the ith iteration of Algorithm
2
Define for each a E A and j E [m]] the random variable
1 o//=0
(,(a) Ti(a 8i)
af)
First, can see that
(s;(s)
(stss)
rand
0 0s 5 (a 8,)
S A (+))
n, (a 8,)
expl
since n. x expl until line 8
Second, have
T
[[)((a]]= = (a st)
P
aa)=
=
E
Σ
R(s
at) 1 =a = Qi (si,a). a).
t=
Finally, using same the reasoning as in the proof of Theorem
we can bound the variance of (a(a):
rand
π rad
Var (X,) S (s)
[X,,]
A Q (st, (s),
nexpi
We now apply Bernstein's 's inequality
m Σ (1(a)
vi(a (t) = m j=1
for each E A. If E arg max.EA Q7 (si, a), we apply lower tail bound:
P V, si) S 2, (s), -
m (A/ 2 2/8 (QTT00) (st, a) + 4/ (s:)
S exp
m (s:))
< exp
12Q (st, VV
nind
< 2TA
If & arg m Q (st, a), we apply an identical upper tail bound:
Vi(a 8:) 2 Q. (s;, a) + ( S
2TA
These tail bounds hold simultancously for all actions with probability at least 1 27 Furthermore, assuming they hold and using the definition of the gap (}(s)), it must be that
arg max Vi st) C arg max Q cpp. (s;, aEA
aEA
which is enough to show that n: (s;) E arg max Q thus prove the theorem.
(si, a) with probability at least 27 and
22

---

Now that we have seen that PG-GORP enjoys similar sample complexity bounds to GORP in the common case that an MDP I-QVI-solvable, we introduce FQI-GORP. FQI-GORP derives its name from fitted Q-iteration (FQI), which was originally proposed by Ernst et al. [49] DQN was inspired by neural FQI 50 so FQI-GORP provides a natural connection DQN.
Algorithm 3 The FQI-GORP algorithm.
1: procedure FQI-GORP(I;
2: for ...... do
3: Sample A episodes, following æ for timesteps to 1 and then expl
Qi+k-1 arg min 442-1 7T Σド m (Qi+
(6(+8-11 d2+x (
Ei=ith-1 R(5),
4:
5:
for t i + 2, 2 do
Qi t- arg min 1ith x.m Ej=1" (st, - R(sl, at) maxx'e Qi+1 1ith-1-1 (0411)
6:
7:
end for (8,))) <- arg maX O ())
8:
9: end for
10: return
11: end procedure
FQI-GORP iteratively constructs series of Q-functions at each iteration by minimizing a mean- squared temporal difference error loss, similar to FQI and DQN.
Theorem B.2 (Sample complexity of FQI-GORP). Suppose that an MDP k-QVi-solvable and that all rewards are nonnegative. Then the sample complexity of FQI-GORP is at most
π nand
2
max
AAHh, 100lgg44
eppl
Proof. Let
rand
as (s)2
10 10 1og((47 (7 4*) A
m
max
24 log (2T'))
max LE .aEAA
expl
We will show that FQI-GORP with parameters l and m will return an optimal policy with probability least 1/2. Since FQI-GORP samples number of timesteps from the environment equal to 2 A this will prove the bound the theorem.
Consider the ith iteration of Algorithm 2 We will show that with probability least 1 1/(2T), for every 8-4k-1 reachable at timestep
starting from 8i, and for every action d;44-1
A)
@ (0 x ( )( <
(11)
2
To prove [1]. it is first helpful to write explicit formula fitted Q- Q-value, assuming that the loss in line 4 Algorithm B]is minimized:
En"n" 1 of 6 -
El R(s(,a))
(s.
Σ
That is. the Q-value is simple average of several reward-to-go values, each of which has expectation
Q (s, a). The probability of reaching some reachable state-action pair (s, a) at timestep i k-1 must be at least - inequality for binomial random variables:
Thus, we can bound the sample size below via a concentration
A m
(s1, Vi) (s,))2
< eepp (110log(4TA4
1 Li =aag
log (2TA) max
a.E.A
28
47'
23

---

the sample size is least log (27 A) ma (((s,aaVV7).. applied in the proofs of Theorems 5.4 and B.I gives
then Bernstein's 's inequality (as
(s,)))
( (01+ 1 ----)) Q'+ 1+h
(. 4T
2
Thus, taking a union bound, we have that the probability 11 does not hold for some reachable state-action pair at timestep i + k- 1 must be at most (27), since there can be at most A such
pairs.
We will now show by induction that given that (II holds for all reachable state-action pairs,
(s.)))
@ (0) (6/ G:
1ith
'it 1005-1(s44,0 R-)
(12)
2
holds for = 1 h - ,....,? i for all reachable state-action pairs at t. The base case of = i i h already taken care of,
only need to show the inductive step.
Assume 12) holds for all reachable state-action pairs at + We can write an explicit formula for the fitted values at timestep i, given that the loss function on line Algorithm 3is minimized:
(s.a) 5= M= [R(s a3) + max.ed @if1 Qitk-t-11 (s)+),
Σラ=1 Atm
1. 1z=
= R((s a) + max
e'EA Given that 12) holds for each pair (f(s, a), d'), it now easy to see that 12 must hold for / as well.
By induction 12 must hold for f = with probability at least 1 1/ 12T). Given that it holds, and by definition of the gap, this implies that n; (s;) E arg maxae Q (s; a). Thus with probability at least 1/2, E IT()). By the assumption that the MDP k-QVI solvable, æ must be optimal with probability least 1 1/2.
B.2 Goal MDPs
Now, we will prove bounds on the effective horizon in one particular class of MDPs: goal MDPs. Definition B.3 (Goal MDP). An MDP considered goal MDP if there is some of goal states Sgout which are absorbing, i.e., f(s, a) = s for every E Spoot, and furthermore the reward function of the form
R(s,a) - =(0
$ Syeat ((, &Sond otherwise.
That is, in goal MDP reward is only received for reaching some of goal states; the total episode reward is a goal state reached and 0 otherwise. As an example, all of the Minigrid environments in BRIDGE are goal MDPs. We can show the following bound the effective horizon in goal MDPs.
Theorem B.4 (The effective horizon in goal MDPs). Suppose that ne (a 8) > 0 for all s E and E A. Then any goal MDP is 1 I-QVI-solvable. Furthermore, suppose that there is some p >> 0 such that, for all timesteps E [T] and all state state-action pairs st, ag at that timestep from which a goal state can be reached,
Pgeut (ST Sgont | Stc ax) 2
Then the effective horizon can be bounded as
l2g(2T)
H log
(13)
Before we see the proof, note that Theorem B.4 agrees with our intuition that it should harder to find an optimal policy for goal MDP when it is less likely that the exploration policy reaches the goal, i.e., when is smaller.
For instance, consider the MDP in Figure 2a In this MDP, the minimum probability of reaching the goal with the random exploration policy after taking some action is exponentially small: p = T Applying Theorem B.4 gives bound of H < T log log(2T).
24

---

Figure 4: Empty-5x5, one of the Minigrid MDPs from BRIDGE and an example of a goal MDP (Definition B.3 The agent (red triangle) can turn left, turn right, or go forward, and its goal is to reach the green square, which gives a reward of 1.
In contrast, consider the Minigrid gridworld in Figure from BRIDGE. Here we can bound p R
0.00137, which gives I 1+ (og/(1/p) + log, (2T) 1+ logs 729 log, log(200) <
7 + 1.52 = 8.52 < T = 100. The techniques in Appendix C give a much tighter bound of
H 1.64.
Proof. We can assume that (81) =, since otherwise every trajectory in the MDP gives reward 0 and thus the effective horizon trivially bounded. First, we will show that
Q
(8, > O
a1
(14)
This is enough to imply the MDP 1-QVI-solvable, since any policy in IT(Q""") must take only actions with Q7 (s > 0, which must be optimal according to (14).
To show that 14 holds, first consider the = implication. Assume Q (s, a) > 0 and by way of contradiction suppose that Q7 (s, a) 1 1, which means that Q7 (s, a) Clearly this cannot happen since this would imply QF (s, a) < O. Now, consider the < direction. If Qi (s, a) = 1, then there must be some sequence of actions starting with which leads from to goal state. By assumption, expll assigns positive probability each action in this sequence. Thus Q7 (s, a)
P. ne (sT
Sgoat s, a) > O.
Next, will prove the bound H from 13
From (4),
that Algorithm D (GORP)
will return an optimal policy for the MDP as long as at each iteration ø picks some action ag
with O7 (si, ax) > 0. In turn, this will happen as long as (s;, a:) >> 0 for some such a,, since Q! (si, a) must be 0 for any suboptimal
Thus, we need only show that
P (Ia EA (+s, 2
>
(15)
2T
holds for each when m 2 log(2T)/p Algorithm [ will find an optimal policy with probability at least 1/2 in this case, which gives the desired bound on the effective horizon.
/p. This will allow us to conclude via a union bound that
To show 15). consider iteration i of Algorithm and let E A such that Q,"h (8i, a:) > 0. We can assume that such an action exists as long as Algorithm T has succeeded in iterations previous af) be the reward-to-go from the jth episode sampled to evaluate Q (st, a,). By the definition of goal MDP, each (a,) {0, 1}. Furthermore, since Q (s,,a,) a.)
to i. Let X, =
25

---

1 E== X,, then (s,,a) > 0 as long as some X, = 1. This implies
P [a, E A () as) 0)
2 P (s), a;) > 0)
P (3j E [m]]
Xj x;=1) =1 1 P (vj E [m]]
X3 0)
F F(X; 0) m
@
2 (1 p)
2 exp (mp
2T
the bound previously proposed
[5 which we argued gives the desired bound. ii) uses the
assumption that Q (s;,a:) = P(X, = 1) 2p
B.3 Lower bounds
Next, we will show that there are MDPs which exponential dependence on the effective horizon is unavoidable. That is, in some cases there is an information-theorett lower bound on the sample complexity of RL proportional to A..
Theorem B.5. Fix T 1, A A2 and H E [T]. Then for any RL algorithm, there an MDP with A actions, horizon T, and effective horizon at most H for which the algoritim'' sample complexity is at least
T (TA" /2] 1) A /H).
Note that this matches the upper bound on the sample complexity of GORP given in Lemma 5.3 up to factor of roughly 2H. When H T, it exactly agrees with the lower bound given Theorem 2.1
Proof. The proof uses MDPs with the same state space and transition function as in Theorem Define AT such MDPs which differ only in their reward functions:
{
df a' 01æ41 and l = 0 (mod H)
M {Mar 01.7 E A²' where the MDP Ma has R(s a')
otherwise.
That is, each MDP has a single optimal sequence of actions that gives reward every H timesteps.
By the same argument in the proof of Theorem for any RL algorithm there must be some MDP M. such that after interacting with the environment for less than [A /1 /2] - episodes, the algorithm cannot with probability at least 1 1/2 identify the optimal actions for timesteps t 1 to H + 1 to t = 2H, and so on for
t H. We can repeat this line of reasoning for timesteps total of [ steps, to show that with less than [T/H] (lA 1) episodes, there must be some MDP in M whose optimal action sequence cannot be identified with probability greater than (1/2) [/ < 1/2. Thus, the sample complexity of the RL algorithm on this MDP must at least
T T (IA /21 - 1).
which is the desired bound.
only remains to be shown that the effective horizon of the MDPs in MI is actually H. To see why, consider running Algorithm [ with & = H and m = 1. That is, at each iteration i, GORP will try all H Henghh action sequences followed by actions from -xp! Then, will pick the action sequence with the highest empirical reward-to-ge From the definition of the MDPs in M, all action sequences starting with a suboptimal action must have empirical reward-to-go of Furthermore, at least one H-llngth action sequence starting with an optimal action must get reward-to-go of at least 1. Thus, GORP will with probability I choose an optimal action each timestep. This means that the effective horizon must be at most H + log H.
26

---

C Tighter bounds on the effective horizon
In Theorem 5.4 we obtained bounds on the effective horizon and thus on the sample complexity of GORP. However, we find that the bounds given by Theorem 5.4 are often very loose compared to the empirical performance of GORP due two factors. First, Theorem 5.4 requires considering the worst case of Of a VV (s) (s)² over all optimal states. However, in many MDPs in our dataset, there are optimal states with extremely small gaps that in practice are almost never reached by GORP. When Theorem 5.4 is applied, these states make the sample complexity bounds very large despite GORP working well empirically. Second, Theorem 5.4 uses asymptotically tight techniques for bounding the sample complexity that can be quite loose for small sample sizes. Below, we describe the algorithm we use to provably bound the sample complexity of GORP (and thus the effective horizon) that gives much tighter results.
Consider the GORP algorithm given in Algorithm [T Let a, denote the random variable correspond- ing to the action ultimately chosen by the algorithm for timestep t. Let s denote the state reached by actions 01 ... .. Denote by P... the probability measure given by rumning the algorithm with parameter m. We would like to bound the probability that the algorithm does not achieve the optimal
return in the MDP. Let this event by denoted as
E
Σ Relsr, at) < Vii
3t Oe E (s:);
where (s) denotes the set of optimal actions in state at timestep t, i...
(s arg max (s). aEA
is straightforward to see from Algorithm I that requires T Am timesteps of interaction the environment. Thus the sample complexity of the algorithm is
T A where min N P.) 1/2].
Clearly, we can upper bound the sample complexity using any such that the probability of failure bounded as P,, (E) < 1/2. To do so, for each value of we perform a binary search over values of m from 1 to 10 For each possible m, we calculate an upper bound on Pm (E). If the upper bound is below 1/2, we then search below m: if greater, we search above m. When the search has converged
relative precision of 1/100, we output A² as the sample complexity and Hy = k + log m as the effective horizon for that particular value of k.
C.1 Upper bounding Pm (8)
We upper bound the failure probability P.,. (E) recursively. Let O denote the event that all actions taken before t have been optimal, i.c.,
O V <t at (s:).
To begin the recursion, note that at the final timestep.
P( Or, ST. ar) = 1 (t)))
will use two recursion rules: one from next states to state-action pairs and one from state-action pairs to states. The first rule is
PP 0c, = Σ TPEE| O1, 0z) P() \&t)
(16)
arEA
and the second (for t < T')
{1 [P(E O141,
0t $ A7()))
P(E Or, 8r, a.)
(17)
a, A7
We apply these results recursively from T..... ... finally obtain PE 01. P(E).
The remaining difficulty is calculating IP(a, st). Recall from Algorithm ] that a is chosen as the first action of a k-action sequence
Ott+k-1 E arg
max Qe(Se, 01:4+k-1), Bucth-1EAk
27

---

where (st. 0c:t+k-1) is the empirical mean return-to toonn-tt-gg go from m episodes starting in state and taking actions a....., Ot+k-1 followed by actions sampled from the exploration policy. To simplify notation, let ae denote dt.+--1. We use various inequalities, described in detail below, to bound the probability that a particular k-action sequence chosen:
p(a+)) S IP m
(Q((t). (e)
max ((as)
(88, at)
S Pm
Qu(se,
max (at)
(ss, ot,)
S p(ae).
Letting p(ā:) denote the actual probability an action sequence is chosen, we can rewrite (16 to
P(E O 81) = Σ
IPEE O 4t)
E
p(ā.).
(18)
aLEA
Given the bounds on p(z)) (i.e., p and p). we formulate a linear program with the bounds as constraints, plus the constraint that Σ At (().) = 1, with the objective of maximizing (18). Solving this gives an upper bound on P(E O, st). We can then propagate this bound recursively using 17 to bound P(E).
Calculating p and
We use up to four methods to bound p(ā.), and pick the one which gives the lowest conditional failure probability after solving the linear program described above. As previously, let Dz( (7)) denote the distribution of the reward-to-go starting in and taking actions de. .... 0-+k-1 followed by actions sampled from the exploration policy. Thus we can write
Qr(s;, a.)
ΣX X2
where X1
Xm (1L,
1=1
Most of the following methods use the following decomposition:
F
Qe(s), R.)
max aEAMMa.
((5,,
i
Pm
(Q(se, 0y) < (1)) dpm (Q.()))
N
m (4-1 < (1(5) S.:)
II Pm (Q(s), S 91-1)
(19)
1=1
8, (a
for some sequence -00 = 90 S S variables (s(s,, à.) across all action sequences â; E l are independent. (ii) is lower bound on the integral via Riemann sum.
I gN = co. Here, (i) uses the fact that the random
Alternatively, suppose know that the CDF of Q, (z) is bounded by
P m Qc(s,, ā.) < x 2 Fx)
where F2(x) is the continuous CDF of some random variable Z. Then
(Qi(5en
Pm
>
max NEA")(E)
Q(si, at))
> P m
Z
max ((EA"((E))
Q(5r, (7)
II
P. (Q(s), 4t) < Qi(ss, ur) dPm (Z)
II
Pm (((x.. s Fzl
i-1
(20)
N
N
1=1 (())
28

---

by a similar argument. We also have equivalent bounds in the other direction:
Pm (Q(())))))
Q(s1.
P m
9i-1 < (x1, Sa:)
II
Pm
(Ô(s), a.)) S 4b)
8, Mart
==1
(21)
P.m (Qi(s)) 2
Σ i=
Pm
(Q(s)) S F
i
N
N
a
(22)
where the CDF of Z is greater than or equal to that of (s,, dz). We use N = 100 when using these bounds.
Binomial bounds In the case where for all az AA, the distribution Dr(s,, a.) has mass on only 0 and some other value C, we have
1 (((on)))))) Binom (mh (
Qu(s,, Ft)
This case occurs in many environments that are goal-based, i.e. where the agent gets reward only for reaching some goal and then the episode ends. We find that it significantly improves the sample complexity bounds in those environments. Without loss of generality, we may assume C 1. We then apply 19) and (2I) to obtain p(ā²) and p(āe). We let .u..... . be set such that
1
P m2 (/-1 Qc(s,, de) S 46
N
normal approximation using either the exact inverse CDF of the binomial distribution for small for large m. Then, we can calculate all terms in the bounds (99) and (2T) using the binomial CDR
Since the CDF is
expensive calculate for larger m, only use the binomial-based bounds
when m < 10t and k =.
Berry-Essees bounds For this type of bound, we calculate the variance o² Var(Di(s;, (.)) and third absolute moment
p D ([xx)
for each a. E AA.. Then by the Berry-Esseen theorem [5T] we have that
S u) min(0.3328(pfo' + 0.4299, 0.33554(p/o' + 0.415))
P. (s,, T.) < u) Px-NNiq(er.)))00///
vm
The resulting upper and lower bounds on the CDFs of Qi āe) for all â E A can be used in 20 and (22) calculate p(ā;) and p(ā:). Since this bound requires order N evaluations of the normal
CDF and inverse CDF, which is somewhat expensive, we only use when A < 100.
Bernstein bounds Similarly to the Berry- Berry-Esseen bounds, Bernstein's 's inequality can be used to bound the CDF of Q.(s), ā,), and is sometimes superior Berry-Esseen Esseen for large m due to giving tail bounds that decay exponentially rather than quadratically. In particular, suppose (r a,) is supported the interval [a, 0]: we can compute these bounds via value iteration. Then
Var(D, ā.)) < V = (3 - (s,,, ā.)) (Qr(st. ā,) - -a).
Bernstein's 's inequality gives the following bounds on the CDF of Qe(s,, dt):
u S 0 otherwise
Pm (Qi(s), ā.) < Qi(s,, de) + +u) 2 11-exy exp {
mu² /2
V+(3-a)uu))))
Pm (t) Q2 ãe) + <
exp
mua 1/2
otherwise.
V+(3 +++33-a)//' u/3
Similarly to the Berry-Esseen bounds, we use these in 20 and when 4 100.
22
to calculate p(ā.) and p(ā.)
Bennett bounds than the others,
The final method we use to calculate p(ā)) and ((ae) is computationally cheaper use it no matter the size of A As in the Bernstein bounds, we calculate
29

---

the interval support and bound the variance of each (st, āe). We then let be the arithematic mean of the highest action sequence Q value and the second highest, i.c.
1 max Qr(se,ae) d.EAt
& darg max e Qe(or.ãe) Qe(st,
2
Then, we for each action sequence with arg Ea Qe(st, (t), we calculate the upper bound
Q-values, i.c. for each ā. $
Pm
(1)()))0)) 2
max ((s,, d.p)
< P
(1(5) ox)
max ai Earg e. Qe(s), Q(s,, at)
Pm
Eay E arg max
Qe(se, Ty) EEEAA
Qr(sn) 0i) ((5))
< 1 Pm
((())) <u
A
Va, E arg max Qr(s;, Q(s,, o.) > =u)
1 Pm
(e((s,)a)) <
II
Pm (Q()), ccy >u)
E/Earg max of cak ((sc))))
=1 -1-(1-P5 (1-Pm
(1)()),a))22) (I
II
(1-Pm (Q(())))) (23)
o Earg df (()),()))
Each of the tail bounds in (3) can be upper bounded using Bennett's inequality to obtain p(āe). We let ((ā)) 1 if az E arg maxa, eAt Qe(s,, ãe) and we set p(ā) for all ã A
D Previously proposed sample complexity bounds
In this appendix. we give proofs of sample complexity bounds based on properties previously proposed in the RL theory literature. We also compare these bounds to our effective borizon-based bounds in examples that showcase their failure modes.
D.1 Upper confidence bounds (UCB) and strategic exploration
central problem in RL exploration: how to efficiently reach enough states an MDP in order to identify the optimal policy. One common way of approaching exploration with upper-confidence bounds (UCB), which originated in the bandit literature. Algorithms using UCBs generally choose actions based on the current best estimate of that action's value plus an exploration "bonus" that incentivizes exploration of little-seen states. Examples in the RL literature include Kakade [18], Azar et al. [4) Jiang et al. [19], Jin et al. (5] 20). Du et al. [21). Jin et al. [22]. Generally, these UCB algorithms achieve minimax sample complexity in terms of some measure of the "size" of the state
space Space-either either the number of states S 4.. quantities like the Bellden-Eluder dimension (2
very simple UCB-type algorithm, R-MAX 23 18 achieves sample complexity bounded by
SAT in deterministic, tabular MDPs. depends on knowing the maximum reward at any state-action pair in the MDP, Rmax (a. R(s, a). It also requires access computational oracle that can calculate an optimal policy for any transition function f and reward function R, for instance via value iteration.
procedure R-MAX
2: initialize ī(s, a) +- for all (s, a) E S
3: initialize R(s, a) +- Rmix for all (s, a) S
4: for
S.A do
5: for t= 1,.,, do
6: take an action a in the current state & according to the optimal policy for f and î
7: R(s,, a) + the observed reward
8:
fs, a) <- the observed next state s'
30

---

9:
end for end for
11: return an optimal policy for and ft
end procedure
This is the version of R-MAX for deterministic MDPs; there is a more complex version for stochastic MDPs. The exploration bonuses in R-MAX are simply the initialization of R to the maximum possible reward. This ensures that an optimal value function computed from ff and ft is always an upper bound on the true optimal value function. The following result shows that R- R-MAX finds the optimal policy, and thus proves that its sample complexity is at most SAT.
Theorem D.I. R-MAX returns an optimal policy.
Proof. Let V and Q" be the optimal value function and Q-function under f and R. We will begin by showing that at any point in the algorithm, (s) S (s) and Q7 (x, S Qi(s, a) for all (1,8,a) a) E [T] x S x A.
The proof is via induction bound holds for Q7- Now, suppose that some Then
from 7 to 1. To begin, clearly (7, a) E (s) a), Rmac J. so the
[T] and all (s, E 8 A, (s, a) I (s)
(s) = max (s, 2 maxQi (s. = (s), aEA
aEA
so the bound holds for V/+ as well. Finally, say that at some t E [ 1] and for all E S. forany Vi+i(s) < V (s). To show this implies Qi (1, a) S (s, for any (8,a) E S x A. consider two cases. First, (8, a) has been seen by the algorithm, then
(s) = R(s, a) Vit (f a) = R(s, a) + +V Viti(f(s,, 2 a(s,a)++1 (f(s, ( (s)
Otherwise, if (s, a) has not been seen, then R(ss, a) Ramx and f(s, a) = s. In this case,
( a) = (T + 1) 2 (s,
By induction we that Vi* s (s) and Q7 a) s Q5 a) for all (t, [T] S x A.
Next, we will prove that any optimal policy x for f and A must either (a) be optimal for f and or (b) reach previously unseen state-action pair. In particular, we will show that if VT (s1) < Vs1 then æ must reach a previously unseen state-action pair. Otherwise, (T((s) 2 Vi((s) 2 Vi((s)). showing that π is optimal for f and R.
We will again work inductively starting from the last timestep. First, suppose that ( a) < (s, a) for some (s, a) E S A. This is equivalent R(s, a) R(s, a). which clearly means that (s, a) cannot have been explored.
Now, suppose that at some timestep t E [T], we know that for any (s,a) E 8 x A, QF as) Q2 a) implies that π must explore some new state-action pair at or after timestep starting in (s, a). If (s) < (s) for some E S, then
(s, (s))) < max (s, = ((,(((((ss).. aEA
By assumption this means must explore some new state-action pair at after timestep t, since it takes action satisfying QT
(s, a) < (s.
Finally, suppose that for some E [T'. know that for any E S, (s) < (s) implies that ा must explore some new state-action pair at or after timestep + starting in s. Suppose for some (s, a) E S x A that Q. (s, a) < (s, Then
R(s, a) + (((,)()) < M((s + V2
which implies that either R(s, a) < A(ss a) or (f a)) < V (f(s (s, a) must be unexplored. In the second case, either (8,a) is unexplored, or
a)). In the first case,
((,(((s, < (f(,
In any of these cases, x must explore new state-action pair either in this timestep or in the future starting from (s,
31

---

Inductively, this shows that (s1) < (s(ss) implies that v must reach a previously unseen state-action pair. We will show that this property implies that R- R-MAX must return an optimal policy.
In particular, note that after the jth loop iteration in R-MAX, it must either have an optimal policy have explored at least of the state-action pairs in the MDP. This is simple consequence of the above property: at each iteration, either the policy used by R-MAX must be optimal or it must explore least one additional state-action pair. This means that after all the SA loop iterations, R-MAX will either have an optimal policy or have explored all the state-action pairs, in which case it will also have an optimal policy.
D.2 Covering length
The covering length of an MDP was originally proposed by Even-Dar and Mansour [22 and later used by Liu and Brunskill ( to prove sample complexity bounds on RL algorithms which random exploration. Liu and Brunskill [7] show various bounds on the covering length using graph-theoretic notions. While they focus on discounted infinite-horizon MDPs, we use version of covering length adapted to finite-horizon MDPs, similar to that used by Dann et al. [6]
Definition D.2 (Covering length). The covering length of an MDP under an exploration policy
n is the number of episodes needed until all state-action pairs have been visited with probability at least 1/2.
One can easily show sample complexity bounds based on the covering length.
Theorem D.3 (Covering length sample complexity bound). There is an RL algorithm which can solve any MDP with sample complexity T given an exploration policy π Te where L is the covering length of npl
Proof. Consider the following RL algorithm:
1: procedure COVERINGLENTTRRL
2: collect a dataset of L episodes, sampling actions according mpxpl
3: record R(s, a) and fs, a) for all state-action pairs seen the dataset
4: define R(s, a) and f(s, a) arbitrarily for state-action pairs not seen in the dataset
5: run value iteration using R and f to obtain a policy
6: return
7:
end procedure
By the definition of covering length. with probability at least 1/2 the algorithm should produce R(s,a) = M[ss a) and f(s,a) a) = f(s,a) for all (8,a) a) E 8 x A. In this case, will be an optimal policy. Thus, COVERINGLENGTHRL. returns an optimal policy with probability at least 1/2 while interacting with the environment for TL timesteps. This means the sample complexity of COVERINGLENGTHRL. is at most TL.
To bound the covering length for MDPs in the BRIDGE dataset, make of the following result. Lemma D.4 (Bounds the covering length). Define the occupancy measure μ. of cxp!
(r a) = (s = 8 A = =a).
Suppose that for every state-action pair (s, a), there is some timestep when (4 a) > O. Then
(2g
log(2SA)
S
2 min Exerry (s(
min (M.)EEEA m (s()s
We calculate Mmin min a max
Me(s, a) for each MDP in BRIDGE and use the upper bound from Lemma D.4 to obtain sample complexity bound of T log(25AT)) /min- Since Everry (s, a) Σ T maxxe(T] (s,s a) the upper and lower bounds in Lemma D.4 agree up to factor of 7 (2S A)/ log(2), so this is reasonably tight. In fact, in 122 of the 155 MDPs in BRIDGE, aa) Eierry Me a) (ia)sxX max,e(T) (4,8, a), making the upper and lower bounds tight up to only logarithmic factors.
Proof. Let Pm be probability measure corresponding to sampling m episodes following TPl Let
32

---

El (s, a) denote the event that the jth episode has (st, (s, Let E((s,a) be the event that
Eg (s, a) occurs in at least one one of those episodes, i.c.
(() = V (s,
f=1
Finally, let C be the event defined by
C
A V E(s,a). (x.))ExxA LE[T]
That is, C when every state-action pair has been seen at some timestep in least one episode. We can thus equivalently define L min(m Pm (C) 2 1/2].
We will now start by showing the upper bound of L s [log(2SA)/p)- Let flog(2SA)/p). We can write
P m (-C) Pm
(J(s,))
8 E
A W [T], [m] -E((),)))
Σ
Pm (vt [T.je [m] (s,
(x,0)ESxA
Pm (vje [ml
(8,)))
min (E(T)
(x
Σ
P. m ( (8, a))) m m
EE[T]
(sa))SxA
Σ
min (sxx)))SSA SE(T]
P m (3) (s', a'))
(s,0)ESxA
Σ
min (x'A
max Me(s', a') m [E[]]
(x,0)ESxA
exp
m
min (S)
max EE|T
(=(5',a')
(8,0)ESx
Σ
25A
(x.0)ESxA
2'
which proves the upper bound.
To show the lower bound, take any (s, arg min Exeryy Me(s, a). First, suppose that Exeryy Pels, a) 2 log(2). Then the lower bound in the lemma must be at most 1/2, which is clearly true. Thus, we may subsequently assume Σrem (e(s, a) log(2).
33

---

Suppose m < <C/ ///is //EiE(T) [E( He((s,) a) Then
Pm (-C) = I'm (3(s ((ss,a'ESxx We (eeieee [m] -E((s',(')
M Pm Vt E [T]. [m] (s,
Pm
(3t [T] (s,,a)
m
1- Σ
Pm (s)
(E[T]
m
Σ a)(s,a)
LE[T]
exp
-2m
Σ (e(s,a) TE(T]
2
where (i) uses the fact that 1 - x: 2 exp(- 2x) for E [0, log(2)). This shows that with probability greater than 1 1/2, not all state-action pairs will be seen in m episodes, and thus establishes that L >> m, which is the desired bound.
D.3 Effective planning window (EPW)
Perhaps the closest existing concepts to our effective horizon are various notions of "effective planning window." This generally refers to tree-based planning algorithms which only consider action sequences of some length W from the current state, rather than considering action sequences all the way until the end of the MDP. For instance, Kearns et al. (24) show that in discounted MDPs, one need only plan to some e-horizon obtain an e-optimal policy. Jiang et [53] build on this and show that one may want to use a different discount factor for planning than the one that is used for evaluation. Malik al. [8] also introduce notion of effective planning window based on the number of timesteps one must look ahead in an MDP to avoid terminal states.
We do not directly apply any of these previous results with anite-horizon undiscounted MDPs, it does not make much sense to apply a discount factor as in Kearns et al. [24] and Jiang al. [53 We find that the assumptions in Malik al. (8) are quite unusual and do not really hold in any of the environments in BRIDGE. In particular, the analysis in Malik et al. { requires that trajectory through an MDP is either optimal ends early in terminal
setting. Since we concerned primarily
state.
Instead of directly using these results, define a notion of effective planning window based on the length of action sequences one must consider in an MDP while ignoring any rewards after the sequence.
Definition D.5 (Effeective planning window). Define Q a) = R(s, for all (1, 8, E xSS and let Qi QVI(Q'--)) = =2..... T. The effective planning window of an MDP is the minimum W E [T] such that all policies in I1(Q") are optimal.
Note that the effective planning window bears significant similarity to the k-QVI-solvabillity property from Definition 5.1 However, Q' is defined equal to the reward function for the EPW, while in Definition 5.1 it is equal to QTT"
The EPW also results in sample complexity bounds of T very similar to those of T AH for the effective horizon. However, find empirically that H W in 82% of the MDPs in BRIDGE, making the effective norizon-based bounds generally tighter.
Theorem D.6. For any MDP with effective planning window W, there is an RL algorithm whose sample complexity is at most 2 AW
Proof. We will use the following algorithm:
34

---

1: procedure PLANOVERWINDOW for I...., T do
2:
3:
for d1 E A do
4:
Sample an episode following #1,.... 11 then actions ---+ and then arbitrary
actions.
5:
Ra(s;, (()+--1) + Eisi R(s;, at).
6: end for
7:
(:( f arg maxa;EA maxa waw 1EA (o amitwi)).
8: end for
9: return и
10: end procedure
Again, this algorithm is quite similar to GORP (Algorithm except that it only samples a single episode per action sequence and it ignores rewards beyond the planning window. Clearly, PLANOVER- WINDOW will take A AW steps in the environment. Thus, bound the sample complexity, we only need to show it returns an optimal policy with probability at least 1/2.
To prove this, we will show that
max E.
(s ae++w-1) = Q. (s;,a:).
(24)
Based on line of the algorithm, this is enough to show that E II( and thus that must be optimal by Definition D.5
To prove
24
we will first show by induction that Q1(s, ar)
max 11413- JEA-1 Erst" R(se, ar). where s4+1 = fly, for i...,, i W - 2. The
base case when j = is by definition: Q1 at) = H(s,, ar). For the inductive step, assume the formula holds for and note that
Qf (st, a.) = (VL(
R(st, + max aftiEA
az),
R(8 + max actiEA an asp EAi
max
R(s,,ae)
M=+1
max ACTLCHEAA
R(se, oir).
v=t
Next, note that by the way is constructed, R(s, d1)4 = - S R(se, az), where 8t+ f(t,, az) for / ,,, + W Thus combining this with the formula proved by induction. (4 clearly holds and the proof is complete.
D.4 Other bounds
One other work that derives sample complexity bounds for RL with random exploration is Dann et al. (6.
They define an algorithm which maintains at all times a current best policy æ, and acts according this policy but with some exploration noise, e.g., via an e-greedy policy expl,(T). They introduce the notion of "myopic exploration gap," which is defined as
a = sup (J(x') - J(T))
such that for all (1,8,a) E [T] x S x A
" - cut expl, (rt) (s,a)
p. < c/ (x) (s)
(s)
This gap is shown generalize the notion of covering length well as various others from the literature. However, we find that it not so useful in many environments in BRIDGE.
The problem find is illustrated in the MDP below:
35

---

91
R =1
82
22
0
R
0
04
T
ST
ST
ST
ST
In this MDP, one need simply follow the actions which give rewards of I to achieve the optimal return T. One can show H W = 1 in this MDP, which give identical sample complexities of T
However, the difficulty with the myopic exploration gap is that the analysis Dann al. c cannot rule out the policy which takes all actions to the right (achieving return T - 1) from being chosen some point while running their RL algorithm. this happens, then the only way to find better policy is to completely switch to the policy x which takes all left actions (achieving return T). This implies that is maximized when e = A", leading to = (1/A)7/2 7/2, Since the sample complexity bounds Dann al. [6] are O(1/a²). this gives a bound proportional A", which is better than the worst case.
Thus, whenever there are "distracting" rewards, matter how distant, in this case, the theory from Dann et al. [6] cannot give good sample complexity bounds. There is also no easy way calculate directly for arbitrary environment. For these reasons, do not include their bounds in our experiments.
E
Dataset details
In this appendix, we give a detailed explanation of how we chose the MDPs in BRIDGE and how we constructed their tabular representations. See Figure 5 for an overview of BRIDGE.
The BRIDGE dataset
upau
E.1 Environments
67 Atari games
55 Proegen levels
Minigrid gridworlds
We limited the horizon of environments for BRIDGE to some T' E {10, 15, 20, 30, 50, 70, 100, 200}, de- pending on the environment, in order avoid the state space becoming intractably large. We use sub- scripts denote the horizon which an environment is limited. For instance, PONG30 refers to the Atari game Pong limited to 50 timesteps.
Num. MDPs
50
50
102 10 10
1015
10
100 200
Num. states S Num. actions A Horizon T
Figure Our BRIDGE dataset consists of 155 de- terministic MDPs with full tabular representations. We include MDPs from three popular RL bench- marks which cover range of state space sizes, action sizes, and horizons.
Frameskip We carefully used frameskip for each environment. Frameskip is standard practice in Atari (54 in which each action taken in the envi- ronment played for a certain number of frames: the agent only receives the next state after all these frames have completed. We use unusually high frameskips in order to capture episodes with longer wall-clock times in a small number of environment timesteps. The frameskip values we use are listed in Table 4 For most Atari games, we use a frameskip 30, corresponding to taking 2 actions per second. The frameskips for Procgen environments vary; we chose ones that tended to align with how long it took the agent to perform various low-level tasks in the environment like moving one space. We did not use frameskip for Minigrid.
36

---

Environment
Frameskip
MONTEZUMAREVENT
24
All other Atari games
30
BIGFISH
8
CHASER
2
CLIMBER
6
COINRUN
8
DODGEBALL
8
FRUITBOT
8
HRIST
2
JUMPER
8
LEAPER
6
MAZE
1
MINER
NINJA
8
PLUNDER
8
STARPILOT
8
All Minigrid gridworlds
1
Table 4: Frameskip values used the MDPs BRIDGE.
Atari games For each of the 57 Atari games in the Arcade Learning Environment (ALE) benchmark [43]. we attempted to construct tabular representations for each horizon E {10,20 20, 30, 50, 70, 100, 200). However, excluded environments once the state space exceeded 100 million states. We kept multiple horizon-limited versions of games, i.e., BRIDGE contains PONG10. PONG2o, PONG30- For some games, even T = 10 produced too many states, not include these at all. We use the minimal action sets for each MDP rather than all 18 possible Atari actions.
did
We made one exception to these procedures for Montezuma's Revenge, as an environment well-known for being diffieult to explore, found that with T = 10, there was not enough time to get any reward, and with T = 20 there were too many states. We found that using T = 15 and frameskip of 24 did allow agent to receive reward, so we used this version in BRIDGE.
wanted to make sure include it in BRIDGE. We
We made couple other modifications to the standard Atari setup. First, we limited agents to one life: as soon as a life is lost, the episode ends. Second, in SKIING10- we added an additional 200 frames of NoOP actions after the 10 timesteps (= 300 frames) in each episode. This is necessary correctly reflect the reward incentives SKIING with longer horizons.
Finally, we scaled the rewards for many Atari games to make the reward scale more uniform across different games. Often, when deep RL applied to Atari, rewards are clipped to [-1, to avoid instability. However, the MDP with clipped rewards may have different optimal policy than the unclipped MDP. Thus, instead of clipping, we use scaling. We generally choose the scale factor based on the multiples of points received in the game: for instance, in ATLANTIS, rewards are always received multiples of 100 so we scale by 1/100. Table lists the reward scaling factors for all games where we apply scaling.
37

---

Game
Reward scaling factor
ALIEN
1/10
AMIDAR
1/10
ASSAULT
1/21
ASTERIX
1/50
ASTEROIDS
1/10
ATLANTIS
1/100
BANKHEIST
1/10
BATTLEZONE
1/1000
BEAMRIDER
1/44
CENTIPEDE
1/100
CHOPPERCOMMAND
1/100
CRAZYCLIMBER
1/100
DEMONATTACK
1/10
FROSTBITE
1/10
GOPHER
1/20
HERO
1/25
KANGAROO
1/100
MONTEZUMAREVENGE
1/ 1/100
MSPACMAN
1/10
NAMETHISGAME
1/10
PHOENIX
1/20
PRIVATEEYE
1/100
QBERT
1/25
ROADRUNNER
1/100
QEAQUEST
1/20
SKINGG
1/100
SPACEINVADERS
1/5
TIMEPIL.O
1/100
VIDEOPINBALL
1/100
WIZARDOFWOR
1/100
Table 5: Factors by which Atari games rewards are scaled by in BRIDGE, for those where we apply reward scaling.
consists of 16 games. For each game, one can generate an arbitrary number random levels, each of which identified by seed. Furthermore, each game has an "easy" and "hard" difficulty, each with different levels, and some have additional "exploration" level which presents a particularly difficult exploration challenge.
Procgen levels The Procgen benchmark 44
While the benchmark is designed to measure generalization of RL agents trained on some number of levels to unseen levels, we use each level as a separate MDP. For each game, we attempted to construct an MDP for the easy levels with seeds 0, 1, and 2, the hard level with seed 0, and the exploration level if it exists for that environment. We denote MAZE to be the easy level with seed 1 for the MAZE game limited to T = 30 timesteps; MAZE is the analogous hard level with seed 0 EX the exploration level.
and MAZF 30
We generally increased the horizon for each game to the highest value in {10, 20, 30, 50, 70, 100, 200} before the number of states was greater than 100 million. The horizon values ultimately chose can be seen in the table in Appendix G.3
Minigrid gridworlds Minigrid [4] is an extensible framework for building gridworlds. We considered all the pre-built gridworlds included in Minigrid for inclusion in BRIDGE except for those requiring natural language observations for specifying the task to be completed. We also excluded gridworlds with more than 1 million states, since for technical reasons we were unable to parallelize the construction of tabular MDPs for Minigrid, For gridworlds with randomized start states, we chose the start state with seed O. We use T 100 for all the gridworlds.
38

---

E.2 Constructing tabular representations
For each of the environments described above, we wrote a program to compute full tabular representation of the transition function f and reward function R. Our program uses a search procedure to iteratively explore every state-action pair. We keep a queue of states that need to be explored, which at first is just the initial state. In parallei, a number of worker threads take states from this queue. After popping a state, a worker thread sets the environment to that state and then takes a previously unexplored action, storing the resulting next state and reward. If there are still unexplored actions in the current state, it adds back the queue. If the next state is not terminal and has not had all its actions, it can continue this process.
While the search procedure for exhaustively enumerating states conceptually simple, we expe- rienced difficulties implementing it efficiently due to the massive scale of some of the MDPs in BRIDGE. For instance, the full state of the Atari simulator used in the ALE about 10-12 KB of data. Storing 100 million states by themselves would thus require over one terabye of memory! We avoided this problem by aggressively compressing state data using dictionary compression. Other challenges included efficiently parallelizing the data structures we used to store the queue of states, the transition function, and the reward function. Our final implementation able to explore more than 20,000 state acttnnctiion pairs per second in PONG while running on 64 cores.
Once we have enumerated all states and actions that can be reached in the given horizon, we also apply a consolidation step to reduce the number of states. Often, the internal representation of states in the Atari and Procgen environments includes extra or superfluous data, which leads to duplicate states in our tabular representation. We repeatedly consolidate states that (a) have the same screen, (b) have the same rewards for each action, and (c) lead to the same next states for each action. When no more states can be consolidated, we store the resulting transition and reward functions.
We excluded any MDPs for which every sequence of actions results in the same total reward, since these are uninteresting from an RL perspective.
F,3 Reward shaping
For each Minigrid environment, we constructed one more versions with shaped rewards for our experiments on the effects of reward shaping. We used three potential functions for shaping:
1. o aisc (s): the negative distance from the state to the nearest goal. Distance is measured as the minimum number of moves needed to reach the goal, assuming there are obstacles in the way.
2. 4 dooms (s): the number of doors that are open.
3. 4 piickup(s) (s): the number of objects that have been picked up at least once.
For one or more potential functions 4, we augment each reward R(s, a) with (f{(s, (s))) The potential functions chosen incentivize useful behavior in the environments: moving towards goals, picking up objects like keys that could be helpful, and opening doors to reach more parts the gridworld.
For each Minigrid MDP, we use all potential functions that apply to that MDP. For instance, an MDP does not have any doors, we do not use &oooss We also apply the combination of & and pickkup if both are applicable to an MDP.
When analy sing the reward shaping results, we only include MDPs for which PPO/DQN converged on both the unshaped and shaped versions.
E.4 Datasheet for BRIDGE
We provide a datasheet, as proposed by Gebru et al. (55), for the BRIDGE dataset.
E.4.1 Motivation
For what purpose was the dataset created? We have described the purpose extensively in the paper: we aim to bridge the tabular representations of popular deep RL benchmarks such that instance-dependent bounds can be
gap in RI. BRIDGE allows this by providing
39

---

calculated and compared to empirical RL performance.
Who ereated the dataset (e.g,, which team, research group) and behalf of which entity (e.g., company, institution, organization)? Not specified for the double-blind reviewing process.
Who funded the creation of the dataset? process.
Also not specified for the double-blind reviewing
Any other comments? No.
E.4.2 Composition
What do the instances that comprise the dataset represent (e.g., documents, photos, people, countries)? The instances Markov Decision Processes (MDPs).
How many instances are there in total (of each type, if appropriate)? There are 155 MDPs in BRIDGE. They include 67 MDPs based on Atari games from the Arcade Learning Environment [43.
55 MDPs based on Procgen games 44), and 33 MDPs based on MiniGrid gridworlds [1].
Does the dataset contain all possible instances or is it a sample (not necessarily random) of instances from a larger set? The MDPs in BRIDGE are based on small subset of the many environments that are used for empirically evaluating RL algorithms. We aimed to cover range of the most popular environments. To make our analysis possible, we excluded environments that were not deterministic or did not have discrete action spaces. We also reduced the horizon of many of the environments to make tractable compute their tabular representations.
W What data does each instance consist of?? For each MDP, we provide the following data:
A transition function and a reward function, which are represented as a matrix with an entry for each state-action pair in the MDP.
A corresponding gym environment [56] that can be used to train policies for the MDP with various RL algorithms.
Properties of the MDP that are calculated from its tabular representation, including the effective planning window, bounds on the effective horizon, bounds on the covering length, etc.
Results of running RL algorithms (PPO, DQN, and GORP) on the MDP. This includes the empirical sample complexity as well various metrics logged during training.
For MiniGrid MDPs, there are additional versions of the MDP with shaped reward functions (see Appendix F.3) which also include all of the above data.
For Atari and Procgen MDPs, there is additionally non-uniform exploration policy (see Appendix For Atari games, this is trained via behavior cloning from the Atari-HEAA [57] dataset; for Procgen games, it is trained on other Procgen levels. We include the above data recalculated using the non-uniform exploration policy in place of the uniformly random exploration policy.
Is there label or target associated with each instance? In this paper, we aim to bound and/or estimate the empirical sample complexity of RL algorithms, these could be considered targets for each instance.
Is any information missing from individual instances? There is information missing.
Are relationships between individual instances made explicit (e-g., users' movie ratings, social network links)? No.
Are there recommended data splits (e.g., training, development//allidttion, testing)? No.
Are there any errors, sources of noise, or redundancies in the dataset? We do not believe there are emrrr sources of noise in the dataset. The tabular representations of the MDPs have been carefully tested for correspondence with the environments they are based on. There some redundancy, as many Atari games represented more than once with varying horizons.
Is the dataset self-contained, or does it link to or otherwise rely on external resources (e.g., websites, tweets, other datasets)? The dataset is mostly self-contained, except that the gym
40

---

environments rely on external libraries. There are archival versions of these available through package managers like PyPI.
Does the dataset contain data that might be considered confidential (e.g., data that is pro- tected by legal privilege by doctor- patient confidentiality, data that includes the content of individuals" non-public communications)?
No.
Does the dataset contain data that, if viewed directly, might be offensive, insulting, threatening, or might otherwise cause anxiety? No.
E,4.3 Collection process
How was the data associated with each instance acquired? The data was collected using open-source implementations of each environment.
What mechanisms or procedures were used to collect the data (e.g., hardware apparatuses or sensors, manual human curation, software programs, software APIs)? As described in Appendix F.2 we developed a software tool to construct the tabular representations of the MDPs in BRIDGE. validated the correctness of the tabular MDPs through extensive testing to ensure they corresponded exactly with the gym implementations of the environments.
If the dataset is a sample from a larger set, what was the sampling strategy (e.g., deterministic, probabilistic with specific sampling probabilities)? The MDPs in BRIDGE were selected from three collections of commonly used RL environments: the Arcade Learning Environment, ProcGen, and MiniGrid. We chose these three collections to represent a broad set of deterministic environments with discrete action spaces. Within each collection, the environments were further filtered based on the criteria described in Appendix E.T
Who was involved in the data collection process (e.g., students, crowdworkers, contractors) and how were they compensated (e.g,, how much were crowdworkers paid)? Only the authors were involved in the data collection process.
Over what timeframe was the data collected? The dataset was assembled between February 2022 and January 2023. The RL environments from which the MDPs in BRIDGE were constructed were created prior to this; see the cited works for each collection of environments for more details.
Were any ethical review processes conducted (e.g., by an institutional review board)? No.
E.4.4 Pegrocesing/ceaning/ablling
Was any preproeesinggddennnn/llbiiii of the data done (e-g., discretization or bucketing. tokenization, part-of-speech tagging, SIFT feature extraction, removal of instances, processing of missing values)? Yes, various preprocessing and analysis was done. See Appendix E.2 for details.
Was the "raw" data saved in addition to the preproesseellllenedlabeee data (e.g., to support unanticipated future uses)? Yes. this is included with the dataset.
Is the software that was used to preprocees/cdean/lbbel the data available? with the rest our code.
Yes, this is available
Any other comments? No.
E.4.5
Uses
Has the dataset been used for any tasks already? The dataset has thus far only been used to validate our theory of the effective horizon in this paper.
Is there repository that links to any or all papers systems that use the dataset? There is not. However, we will require that any uses of the dataset cite this paper, allowing one to use tools like Semantic Scholar or Google Scholar to find other papers which use the BRIDGE dataset.
What (other) tasks could the dataset be used for? We hope that the BRIDGE dataset is used for further efforts to bridge the theory-practice gap in RI. The dataset could be used to identify other properties or assumptions that hold in common environments, or to calculate instance-dependent sample complexity bounds and compare them to the empirical sample complexity of RL algorithms.
41

---

Is there anything about the composition of the dataset or the way it was collected and pre- poooessee/cleaned/abbbeee that might impact future uses? BRIDGE is restricted to deterministic MDPs with discrete action spaces and relatively short horizons. This could mean that analyses of the dataset like ours do not generalize to the broader space of RI. environments that may have continuous action spaces, stochastic transitions, and/or long horizons. We have included some experiments, like those in Appendix [.I to show that our theory of the effective horizon generalizes beyond the MDPs in BRIDGE. We encourage others to do the same and we hope to address some of these limitations in the future with extensions to BRIDGE.
we have already mentioned,
Are there tasks for which the dataset should not be used? tasks for which the dataset should not be used.
We do not foresee any particular
Any other comments? No.
E.4.6 Distribution
Will the dataset be distributed to third parties outside of the entity (e.g., company, institution, organization) on behalf of which the dataset was created? Yes, we will distribute the dataset publicly.
How will the dataset will be distributed (e.g., tarball on website, API, GitHub)? We are still finalizing the method through which the dataset will be distributed.
When will the dataset be distributed? We plan to make the dataset public in May or June 2023.
Will the dataset be distributed under a copyright other intellectual property (IP) license, and/or under applicable terms of use (ToU)? will be distributed under CC-BY-4.0.
Have any third parties imposed IP-based or other restrictions on the data associated with the instances? The Atari ROMs used to construct the Atari MDPs in BRIDGE are copyrighted by the original creators of the games. However, they are widely used throughout the reinforcement learning literature and to our knowledge the copyright holders have not complained about this. Since we are not legal experts, we do not know if releasing believe that we are harming them since the tabular representations in BRIDGE are only useful for research purposes and cannot be used to play the games in any meaningful way.
dataset violates their copyright, but we do not
Do any export controls or other regulatory restrictions apply to the dataset or to individual instances? No.
Any other comments?
No.
E.4.7 Maintenance
Who will be supportinghhsttignnaanttiningiin the dataset? We (the authors) will support and maintain the dataset.
How can the owner/curatorrmanage of the dataset be contacted (e.g., email address)? Redacted for double-blind review.
Is there an erratum? We will record reports of any errors in the dataset and release new versions with descriptions of what was fixed as necessary.
Will the dataset be updated (c.g., to correct labeling errors, add new instances, delete instances)? We will release new versions of the dataset correct any reported errors as described above. We may also expand the dataset in the future with more MDPs or new kinds of MDPs, such as stochastic or continuous-actio wwtaaacttnnsppaa space MDPs. Any updates will be communicated through the service we use to host the dataset (TBD).
If the dataset relates to people, are there applicable limits the retention of the data associated with the instances (e.g., were the individuals in question told that their data would be retained for a fixed period of time and then deleted)? No.
Will older versions of the dataset continue to suppored/hstedmmintaieel If so, please describe how. If not, please describe how its obsolescence will be communicated to dataset consumers. We hope find host for the dataset that will retain older versions of the dataset. We only plan to maintain the latest version of the dataset, however. We will note this policy in the
42

---

dataset's description.
If others want to extend/augmment/uild on/contribute to the dataset, is there mechanism for them to do so? 'here is no predefined mechanism to contribute to the dataset, but we will consider external contributions case-by-case basis. We encourage others to extend and build on the dataset.
Any other comments? No.
F Experiment details
In this appendix, we describe details of the experiments from Section In particular, we describe how calculate the empirical sample complexity of PPO and DQN.
We use the implementations of PPO and DQN from 3abbleBasslliee33 (SB3) archictures, we use convolutional neural nets (CNNs) for Atari and Procgen and fully-connected network for Minigrid. The network architectures are the default CNN and fully-connected architec- tures chosen by SB3. We used the below hyperparameters for PPO and DQN, which are mainly taken from the tuned Atari hyperparameters in the RL Baselines3 Zoo
For the network
[59 repository.
We used a discount rate of for all environments and algorithms except for PPO and DQN in MiniGrid environments, where used 7 0.99. We found that the performance of PPO and DQN significantly degraded when we used = for MiniGrid.
PPO
We use the following hyperparameters for PPO:
Hyperparameter
Value
Training timesteps
5,000,000
Number of environments
8
Number of steps per rollout
{128, 1280]
Clipping parameter (e) Value function coefficient
0.1
0.5
Entropy coefficient Optimizer
0.01
Adam
Learning rate
2.5 x 10
Number of epochs per training batch
4
Minibatch size
256
GAE coefficient (A)
0.95
Advantage normalization
Yes
Gradient clipping
0.5
Table 6: Hyperparameters we use for PPO.
For each environment, try rollout lengths of 128 and 1,280, as find this is the most sensitive hyperparameter to tune.
DQN We use the following hyperparameters for DQN:
43

---

Hyperparameter
Value
Training timesteps
5,000,000
Timesteps before learning starts
Replay buffer size
100,000
Target network update interval
1,000
Training frequency
Gradient steps per training step
Optimizer
Adam 10
Learning rate
Exploration fraction
10.1.1)
Final
0.01
Learning rate
10-3
Gradient clipping
10
Table 7: Hyperparameters we use for DQN.
We try decaying the 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.
Calculating the empirical sample complexity In order to compute the empirical sample com- plexities of PPO and DQN, throughout training we run evaluation episodes and if the algorithms have discovered an optimal policy yet. During the evaluation, PPO policies take actions according to the argmax over the probabilities they assign to each action, rather than sampling as during training episodes. DQN takes actions greedily with respect its current Q-function (i.e., with = 0). If the total episode reward during the evaluation is the optimal return, then we terminate the training run and record the total number of timesteps interacted with the environment the empirical sample complexity. We take the median sample complexity over 5 random seeds and then the minimum over all hyperparameter settings to get the final empirical sample complexity.
We found that in some environments PPO achieved optimal reward during almost all the training episodes but none of the evaluation episodes. This can happen if a policy does not assign the highest probability an optimal action in some states but can make up for this by being very likely overall to obtain the highest possible total reward. Thus, if more than half of the training episodes during an iteration achieve the optimal return, we also count this as converging to an optimal policy for the purposes of calculating the empirical sample complexity.
F1 GORP vs. deep RL algorithms over longer horizons
To show that GORP is not just effective short horizons, ran additional experiments comparing GORP, PPO, and DQN in more typical Atari benchmark environments with frameskip 4 and horizon of T 27, 000 (corresponding to maximum of 30 minutes of gameplay). Similarly to the environments in BRIDGE, we limit agents to single life and make the environments entirely deterministic. The hyperparameters for PPO and DQN are identical to those given in Tables and 7 exxeep for the following changes: we train for 50 million timesteps; we use a discount rate of 7 0.99; and, we set an entropy coefficient of 0.01 for PPO.
We use a training batch size of 1 for PPO and decay e for DQN over the course of the first 5 million timesteps. For GORP, we
1 and tune m for each environment.
F.2 Exploration policies
For the experiments in Section we needed pre-trained policies to initialize PPO with; here, we describe the details of how we trained them. We used two different training methods: one for Atari environments and one for Procgen environments.
In the Atari environments, we trained policies via behavior cloning (BC), i.e., supervised learning. from human data the Atari-HEAD dataset (57]. We resampled the actions and processed the screen images from the dataset to align with the frameskip and observation preprocessing of our Atari
environments. We trained BC policy on each environment for 400 batches of 500 timesteps each.
We used Adam with a learning rate of 10-3 We also added entropy bonus to the loss function with
44

---

weight of 0.1 to avoid the BC policy assigning very little weight to some actions. Our theoretical results in Section B.I suggest that this should improve the sample complexity. Since not all Atari games are included in Atari-HEAD, we only used a subset for the experiments in Section 6
In the Proegen environments, pre-trained policies particular, we trained policy with PPO on 500 easy levels for 25 million timesteps, which in very similar the methodology in Cobbe al. [44). We also use an entropy bonus in PPO with weight 0.1 for the same reason as above.
set of levels not included in BRIDGE. In
Once have the pre-trained policies, compute tabular representations of them the correspond- ing MDPs in BRIDGE. To do so, we feed the observations for every state in the MDP through the pre-trained policy network and record the resulting action distribution. This allows to compute Q=""" and thus obtain bounds on the effective horizon when using the pre-trained exploration policy.
F.3
Computational resources
For deep RL experiments, we used a mix of A100, A4000, and A6000 GPUs from Nvidia. We ran the algorithms either on separate GPUs sometimes ran multiple random seeds simultaneously the same hardware. We used 1-8 CPU threads to run the RL environments. Using this setup, PPO and DQN generally took 2-8 hours complete 5 million timesteps of training. We used early stopping when the algorithmss found an optimal policy before 5 million timesteps, so the amount of compute per experiment was often less than this.
For constructing and analyzing the tabular MDPs in BRIDGE, we used up to 128 CPU threads and 500 GB of memory. The amount of time necessary to construct and analyze the MDPs ranged from less than a minute to around 5 days.
G Additional experiment results
Here, we present additional results from the experiments in Section 6
G.1 Example of the effective horizon failing to predict generalization
As we described the discussion, the effective horizon cannot model generalization across different states. For instance, in PONG-30 (Pong limited to 30 timesteps/ 15 seconds), the effective horizon gives sample complexity of roughly 5 billion timesteps and empirically GORP takes over 80 million timesteps to converge to an optimal policy (Appendix G.3). However, both PPO and DQN converge in under 500,000 environment steps. We hypothesize this because they are able to generalize the skill of hitting the ball across the multiple rounds of the Pong game, which the effective horizon cannot capture because it considers learning separately at every timestep.
G.2 Additional plots
100
PPO sample complexity >> 5M
Number of MDPs
PPO sample complexity 5M
75
50
0
1
2
3
4
6
7
8
9
> 10
Minimum value of ls for which MDP is I-QVVlsolvable
Figure 6: The distribution the minimum values of for which MDPs BRIDGE are k-QVI solvable.
About two thirds are I-QVI-solvable, meaning they can be solved by simply acting greedily with respect to the Q-function of the random policy. The MDPs are split into those which PPO can and cannot solve in million steps; among those that can be solved efficiently, the values of k are even lower.
45

---

Atari
Procgen
Minigrid
5M
Empirical sample complexity
10
PPO
10
10
8 690
10
10
10
1076
10
10
10
10a
10
10
10
10
10th
10
10?
>
10
5M
10"
10
DQN
10
10ah 1 10?s
10
10 10
10 10
10
10
102 2 o0
10
10" > 10
Worst-case (T[A" /2]
Covering length (TL)
EPW
UCB (SATT)
Effective horizon
(1 A**
Sample complexity bounds
Figure 7: A comparison of sample complexity bounds and the empirical sample complexities of PPO and DQN across the MDPs in BRIDGE. In each plot, every dot represents one MDP and its color indicates which benchmark it comes from. Our effective horizon-based bound most closely correlates with empirical sample complexity. See for quantitative comparison of the bounds.
Minigrid
Change empirical samp. complex. (ratio)
10
PPO
10-1
10
10
10-2
2 10
< 10-1
10
10
10
000
DQN
10
10
<
10
10 2
2 10
< 10
10"
>
10
EPW
Effective horizon
Change in sample complexity bounds (ratio)
Figure 8: A comparison between the empirical change in sample complexity and the change predicted by sample complexity bounds due to reward shaping. See Table 3a for quantitative comparison.
46

---

Atari
Procgen
Change in empirical samp, complex. (ratio)
10
PPO
10"
ooo
10
S 10
10
2 10
- 10
10
> 10
Covering length
Effective horizon
Change in sample complexity bounds (ratio)
Figure 9: A comparison between the empirical change the sample complexity of PPO and the change predicted by sample complexity bounds due initializing with pre-trained policy. The initial policies for Atari are trained from human data and those for Procgen are trained on other procedurally generated levels. See Table 3b for a quantitative comparison.
G.3 List of MDPs in BRIDGE with statistics
The following table lists all the MDPs in BRIDGE, along with various properties: the number of states S, number of actions A. horizon T', minimum for which the MDP is k-QVI-solvblle, a bound on the effective horizon using the techniques in Appendix C bound the covering length L using
Lemma D.4 and the effective planning window W.
MDP
S
A
T
Min A
Bound on H
Bound on L
W
ALIEN10
7.97 x 10
18
10
3.5
2.27 x 10
6
AMIDAR20
1.00 x 10
20
x 10
1SSAULT
7.21 x 10
7
10
3
9.8
4.56 x 10"
8
ASTERIX10
9.03 10a
10
3.5
4.99
1010
ASTEROIDS
5.11 x 10
14
10
7
10
2.72 x 10
9
ATLANTIS00
10
1.5
6.12 10
ATLANTIS20
471
4
20
4.7
5.53 x 10
3
ATLANTIS30
4.56 x 10a
30
19
23
2.89 x 10
23
ATIAANTSS
2.06 x 10a
40
27.7
9.62 x 10
ATLANTISS0
5.63 x 10
4
50
12
43
4.27 10
38
ATLANTIS70
x 10
70
47
5.11 10
50
BANKHEISTIO
4.24 x 10
18
10
3.5
6.73 X 1043
9
BATTLEZONE10
x 10a
10
2.3
5.01 10
4
BEAMRIDERg0
2.39 x 10a
9
20
3.3
1.10 x 1013
10
BOWLING30
2.50 10
30
18.5
1.73 x 10
28
BREAKOUT10
238
10
4.1
7,92 x 10
5
BREAKOUTZ0
1.27 x 10
20
5.4
1.01 10
13
BREAKOUT30
2.80 x 10
30
13
1.15 x 19
29
BREAKOUTA
6.12 x 103
4
40
15.7
1.31 x 1025
29
BREAKOUTS
x 10a
50
x 10
20
BREAKOUT7u
7.83 x 10a
4
70
40
48.5
1.86 x 10
61
BREAKOUT100
1.31 10
100
74
87.0
2.23 10
75
BREAKOUT220
1.39 x 10
4
200
105
114.9
3.60 x 10
108
CENTIPEDE:0
1.32 x 107
18
10
10
7.13 1043
7
CHOPPERCOMMANDIO
1.39 x 10
18
10
3.9
1.95 x 10T1
7
CRAZYCLIMBERg0
1.77 x 10
9
20
3.1
4.02 x 109
8
CRAZYCLIMBER30
4.63 x 10
30
3.9
2.15 x 10
18
DEMONATTACKIn
6.32 x 10a
6
10
5
9
8.19 x 10
9
ENDURÔ10
x 107
10
x 10S0
FISHINGDERBY10
2,80 x 10
18
10
6
9
3.60 x 10
9
1REEWAY
198
3
10
4.3
1.39 x 10
6
FREEWAY20
3.16 x 10
3
20
7.4
1.14 X 10td
13
FREEWAY
1.02 x 10a
3
30
7.8
1.26 x 10
26
47

---

FREEWAY
2.08 x 10
3
40
7.9
2.64 x 10'7
35
50
x 10a
8.1
x 10a1
FREEWAY70
7.02 x 10
3
70
9.1
3.89 x 1029
66
FREEWAY
1.51 10
100
39
55.4
2.82 1041
67
FREEWAY200
6.33 x 10
3
200
30.3
1.26 x 10
150
FROSTBITE10
5.73 x 10
18
10
2.9
8.01 10th
3
GOPHER30
778
8
30
1.9
7.62 x 10
5
GOPHER40
8.18 x 10
8
40
9.7
4.86 x 10
13
HEROJO
x 10
10
1
1.85 10
ICEHOCKEY10
2.53 x 10"
18
10
3.2
1.01 X 10th
5
KANGAROOg5
10
3.7
10
KANGAROOS0
5.84 X 10
18
30
21
24
1.07 x 10
23
MONTEZZMARRVENGEEI
8.47 10a
15
8.2
1.08 X 10
15
MsPACMAN20
1.85 X 10
9
20
11
11
8.15 x 10S1
11
NAMETHISGAMELu
6.04 X 10s
6
20
8
9.40 X 10
5
PHOENIX10
4.64 X 10
10
1.45 x 10
8
PONG20
255
6
20
3.2
5.60 X 10
5
PONG30
x 10
30
4.15 10
PONG40
1.60 X 10a
6
40
6
14.3
2.96 X 10a0
23
PONGs0
1.25 105
50
13
19.6
2.04 1025
25
PONG70
2.89 x 10
6
70
20
28.1
8.69 x 10
25
PONG100
3.46 x 107
6
100
42
70.1
2.05 x 10
25
PRIVATEEYE:0
1.29 x 10a
18
10
4.1
8.64 10th
8
QBERT
289
6
10
5
3.80 10S
QBERT
3.75 x 10
20
1.18 x 10
ROADRUNNER10
2.37 X 107
18
10
3
9.9
7.34 10TH
9
SEAQUEST
10a
10
1.2
4.15 10"
SKIING10
1.75 X 10
3
10
8
10
6.83 X 10
10
SPACELNVADERSIO
994
10
3.0
4.38 10
TENNIS
3.79 x 10
18
10
8.2
2.29 X 10
6
TIMEPILOT1U
5.03 x 10
10
3.9
5.76 x 10
6
TUTANKHAM1u
1.66 x 10a
10
7.7
1.68 x 10
9
VIDEOPINBALLI
1.25 x 10
9
10
9.5
5.10 x 10
8
WIZARDOFWORG0
x 10
20
x 10
BIGHISHTO
2.31 x 10a
9
10
9
2.26 x 1020
BIGHISH
2.74 x 10
10
2.8
4.57 x 1010
4
BIGFISH E2
1.96 x 10
9
10
5.26 x 10
10
BIGHIS
9.26 x 10
9
10
4.3
4.19 x 10Th
7
CHASER
8.13 x 10
9
20
12.1
1.16 x 10
15
CHASER
3.98 10
20
4.4
1.62 x 10
CHASER
5.03 x 10
9
20
15.2
1.34 X 10
10
CHASER
8.75 x 10
20
18
20
1.4 10
19
CLIMBER P0
2.42 x 10
9
10
3.4
2.67 x 10
7
CLIMBER
1.18 x 105
10
4.0
8.46 x 10
CLIMBER F2
1.12 x 10
9
10
2.8
8.43 x 10a
6
CLIMBER
2.33 10
10
6.6
2.66 x T0
COINRUN
2.23 x 10
9
10
4.2
1.77 10
COINRUN
6.23 10
10
3.6
4.05 x 10a
COINRUN E2
1.74 x 10
9
10
5.0
1.30 X 10
9
COINRUN TO
2.72 105
10
2.3
1.34 X 10
DODGEBALL EO0
1.19 x 10
10
10
4.2
1,77 x 10t1
7
DODGEBALL
1.95 x 104
10
9.1
1.29 x 10
10
DODGEBALL
3.42 x 10a
10
10
3.7
1.34 x 10
6
DODGEBALL
7.24 10a
10
1.42 10
8
FRUITBOT
230
9
40
13
18.6
2.32 x 107
10
FRUITBOT
379
40
18
24.1
6.00 10"1
18
ERUITBOT
161
9
40
3.1
1.12 x 10
2
FRUITBOT!!
620
40
18.7
6.56 x 1013
24
HEISTEL
8.28 x 10
10
6.3
4.96 x 10
10
48

---

JUMPER
1.30 x 10 9
10
8.5
5.11 x 10
10
JUMPERS
x 10
x 10
JUMPER
8.29 x 10
9
20
1.3
2.01 X 1020
2
JUMPER
1.38 x 10
9
20
2.4
1.29 x 10
5
JUMPER
3.40 x 10
9
20
13.1
1.09 x 1020
17
LEAPER
x 10
11.2
1.48 X 1000
LEAPER
2.20 x 10
9
20
4.3
1.85 x 10a0
8
LEAPERSE 30
1.71 x 10
20
13.1
1.54 x 10ad
15
LEAPER
3.31 x 10
9
20
12.8
1.62 x 10a0
16
MAZE
244
30
1.3
1.65 10a
MAZE KI
1.46 X 10
9
30
14.2
9.02 x 10
23
MAZE 30
655
30
1.3
4.48 107
MAZE HB
1.75 X 10a
9
30
7.9
8.26 x 10
15
MAZE 100
X 10a
40.3
4.27 10
MINER D
5.96 X 10a
9
10
3.8
4.84 10th
8
MINER
X 10a
10
5.2
x 10tH
MINER E2
5.56 X 10a
9
10
1.3
4.82 10
3
MINER
X 10º
10
3.4
5.04 10tH
NINJATO MD
2.02 X 10
13
10
4.4
2.67 x 10th
9
NINIA TU
4.87 X 10
10
3.9
x 10SH
NINJATO MN
2.11 X 10
13
10
7.0
2.67 x 10TH
9
NINJA
X 10a
10
6.8
2.47 10Th
PLUNDER BO
1.55 X 10a
10
10
1.3
1.26 x 10th
5
PLUNDER
x 10a
10
1.29 x 10th
PLUNDER 1D
9.99 x 10
10
10
3.3
1.22 x 10th
7
PLUNDER
x 10a
10
1.3
1.20 10"1
STARPILOT
3.24 x 10
11
10
2
8.0
4.09 x 10th
9
STARPILOT
1.76 x 10
10
3.7
3.93 x 10
STARPILOT
9.50 x 10
11
10
9
3.77 x 10th
7
STARPILOT
x 10"
10
9.2
4.02 x 10S
EMPTY-5X5
3
100
1.6
1.76 x 10
5
EMPTY-6X6
65
3
100
2.3
3.47 x 10
7
EMPTY-8X8
145
100
3.0
9.28 103
EMPTY-16X16
785
3
100
7.9
1.22 x 10
27
DOORKEY-5X5
265
100
3.6
3.85 107
DooRKEY-6XC
1.30 x 10
6
100
5.0
5.00 x 10
14
DOORKEY-8X8
9.24 x 10
100
6.6
2.27 x 10
17
1
3.58 x 10
6
100
14.1
L04 x 10
29
MULTIRoOM-N2-S4
61
6
100
2.4
3.27 X 10
7
MULTTROOM-NN4SS
5.70 x 10a
100
17.2
x 10
36
MUL.TRROOM-N6
1.12 x 10
6
100
21.8
3.81 x 10
46
KEYCORRIDORS3RI
169
100
4.1
2.10
KEYCORRIDORS3R2
4.90 x 10a
6
100
4.7
2.48 x 10
15
KEYCORRIDORS3R3
x 10
100
5.5
6.27 20
KEYCORRIDOR$4R3
6.03 x 105
6
100
9.1
1.66 x 10
20
UNLOCK
1.08 x 10
100
4.6
1.36 x 107
15
UNLOCKPICKUP
1.72 x 10a
100
5.3
6.26 x 10S7
16
BLOCKEDDUNLOOKKPCCUUP
5.10 x 10
6
100
10.4
5.85 x 10
24
OBSTRUCCTEDMAZZ--IDDL
x 10
100
4.9
1.92 x 10
OBSTRUCTEEDMAZZEIIDDDA IDLH
4.35 x 10
6
100
5.5
7.25 x 1000
15
OBSTRUCTEDDMAZE-IIULEE
X 1
100
9.1
x 10T6
21
FOURROOMS
1.04 x 10a
6
100
5.1
7.25 x 10t1
15
LAVACROSSINGSSONI
173
100
3.7
3.19 10
LAVACROSSINGG59N2
133
6
100
4.1
3.65 x 10a
14
LAVACROSSINGS9N3
53
6
100
4.5
9.99 x 10
13
LAVACROSSINGSIINS
6
100
10.4
1.74 10
21
SIMPLLCCROSSINNGS9N
173
6
100
3.6
1.84 X 105
14
SIMPLECROSSSINGSSNN2
133
100
3.9
10
14
SIMPLECROSSINGSSNN
53
6
100
3.9
1.04 X 10
13
49

---

SIMPLECROSSINGS INS
85
6
100
1
6.9
2.71 X 10
21
LAVAGAPSS
100
1.8
1.19 x 10
6
LAVAGAPS6
53
6
100
3.0
1.15
x 10
9
LAVAGAPS7
85
6
100
3.6
4.03
10
11
G.4 Table of bounds and empirical sample complexities
This table lists all the sample complexity bounds we calculate for each MDP in BRIDGE along with the empirical sample complexities of PPO, DQN, and GORP.
Sumple complexity bounds
Empirical sample complexities
Wont-case
Covering length
EPW
UCB (S.47)
Eflective
(TT /2])
(T
(T
(f2
PPO
DQN
GORP
ALIENTO
1.79 1618
2:27 10
3.40
10
1.43 x 10
2.78 10
5 10
6.30 x 10
2.70 104
AMIDAR20
1.00 x 1021
8.08 x 1012
4.00
10
2.01 x 107
4.00 x 1044
> 5
x 10
2.21 X 106
100
ASSAULT10
1.41 16
4.56 10
3.76
10
5.04 x 107
1,95 10
2.68
10
3.26 x 10
3.35
10
ASTERIX1O
1.74 x 1040
4.99 x 1641
7.29
x 109
8.13 x 10e
2:20 x 10
6.20 x 10
7.00 x 10
4.50 x 10
15
1.45 1012
2.72 10
10
7.16 10
1013
10
108
10
ATLANTI510
6.24 16
6.11 104
6,40
10
1.9G x 10
800
1.10 x 10
1.40
10
800
ATLANTIS20
1.10 1013
1.11 10
2.56
10
10d
2,80 10
1.65 10
2.05
10
1.90 10*
ATLANTIS30
1,73 1619
8.66 x 16th
6,33
10
5.48 x 10a
6.33 x 16
>> 2 10
> 5 10
>
10
ATLANTIS
2.42 1025
3.85 10
4.19
10
10
3.14 10
10
9.39
10
1.56 107
ATLANTIS30
3.17 x 16th
2.13 16
1.89
10
1.13 X 10
1.93 x 16a9
> 28 10
>. 5 10
10
ATLANTISTO
4.88 1043
3.38 20
30
x 10
104 10
>> x 10
10c
108
D
1.79 16t3
6.73 x 16
1.98
10
7.63 X 10a
2.16 X 10
9.90 X 10
2.06 X 10
3.78
X 10
BATTLEZONE1O
1.79 1018
5.01 10
1.05
107
10
6.84 10
5.70 10
8.70
10
3.60
1
BEAMRUDERg0
1.22 x 1620
2.20 x 1644
1.39 x 16
4.30 X 10
6.22 x 10
3.20 X 10
9.50
10
2.62
104
RowinNGio
3.32 10
3.18 10
5.53
10
4.51 X 10
9.72
1.26 X 10
1.39 X 10
6.48
10
BRUAKDUTIO
5.24 10
7.92 x 107
1.02 x 16
9.52 X 10
2.24 X 10
6,80 X 10
3.00 X 10
2.62
1
RREARDIT20
1.10 10
2.03 x 10
2.68 10
1.02 X 10
6.83
4.80 10
1.23 X 10
9.07
10
BREAKOUTS0
1.73 1619
3.46 x 16
2.59 X 20
3.36 X 10a
6.01 X 16
2 10
5 10
2.50
X 10
RRFARDIT40
2.42 1025
5.22 20
4.61 X 20
9.80 X 10
4.35 X 10
> X 10
> X 10
5.22
10
BREAKOUTSO
3.17 16
7.46 x 16
2.75 X 10
3.24 X 10
158 X 10
2 10
5 10
5.68
10
BREAKOUT70
4.88 1043
1.30 1045
2.61 10
2.19 X 10
7.87 X 10
>5 10
> 5 10
10
BREAKOUT100
8.03 16t1
2.23 16Th
1.43 X 10
5.25 X 10
2.33 10
25 10
25 10
10
BREAKOUT200
2.58 x 22
7.19 20
4.21 X 10
1.12 X 1
6.26 X 1078
>5X 10
> 5 10
10
1.79 1643
7.13 1014
1q
2.38 10
3.67 1614
> 10
16
10
CHOPPRCoMMANND00
1.79 1613
1.95 x 16
6.12 10
2,49 X 10
8.87 X 10
> 5 108
1.85 10
6.45
104
1.22 1020
8.03 1040
1040
10S
3.35 10
10
3,00
10
1.08
104
CRAZYCoMMMRgg
6.36 x 20
6.46 x 1020
1.35 X 20
1.25 X 10
5.11 X 10
6.50 X 10a
6.00 X 10
1.04
10
DEMONATTACK
3.02 10
6.19 10
10a
10S
1.01 10
10
3.05 X 10
1.53
10
ENDUR010
1.74 1640
6.95 x 16
3.87 x 10
2.29 X 10
3.49 X 16
3.49 X 10
4.57 X 10
9.57 X 10
FISHINGDERBY
1,79 1013
10
10
10
196 10
10
X 10
2.10
107
FREEWAY
2.95 x 10
1.39 10
7.29 x 10
5.94 X 10a
1.11 104
2.00 X 10
4.00 X 10
8.70
10a
FREEWAY20
10
2.29 10
10
10a
1,40 10
10
X 10
1.67
10
FREEWAY30
3.09 x 1615
3.78 x 16
2.29 x 10
9.21 X 10
4.87 x 10
1.50 X 10
5,60 X 10
1.09
10
PHuzWAY
2.43 1020
1.06 1019
8.01 10
2,50 X 10S
9.36 10
2.83 X 10
8.20
10
2.84
100
FREEWAYGO
1.79 x 1625
2.97 x 1623
2.46 X 1024
5.10 X 10S
1.81 X 10
3.29 X 10
4.00
X 10
5.35
X 10
PHLzWAY7O
8.70 10
2.73 10
1.51 X 10
X 107
1.11 10
1.14 X 10
1.85
10
4.63
107
PRIZWAN100
2.58 x 1649
2.82 X 1643
9.27 X 10
4.54 X 10
2.71 X 10
25x4 10
5 10
10
FREEWAY200
2.66 x 10
2.52 90
1.48 1078
3.80 X 10
2.00 X 10
>3 10
2.88
108
10
PRosTorug0
1.79 x 1613
8.01 1641
5.83 X 10
1.03 X 10
3.80 X 10
4.50 X 10
2.17
10
5.40
10a
GoPHERg0
1.86 x 1028
2.29 10
2.95
1.87 X 10
4.32
2.30 X 10a
3.20
10a
1.44
10
GopHER40
2.66 16
1.91 1014
6.80 10
2.62 X 105
8,30 10
> 10
5 10
1.31
107
HERO
1.79 x 1013
1.85 x 10
5.63
8,80 X 10a
1,80 X 1
1,20 X 10a
7.00
X 10
3.60
10
IcEllocKEY10
1.79 1013
1.01 10
1.69 10
4.56 X 10a
1.18 10
9,00 10
2.00
10
7.20
10
KANGAR0020
1.27 x 1026
4.80 x 1018
2.57
x 19
4.69 x 107
1.37 x 10
2.62 X 19
8.00
10
3.60
104
KANGAR0030
8.83 16
3.21 10
6.69
10
3.16 X 10
1.2 1033
3 10
10
10
MONIEZUMARRIVENCE
5.06 x 1049
1.62 x 1046
1.52
16
2.29 x 106
4.22 10
> 3 10
> 10
5
> 108
MsPAEMAN2O
1.22 1020
1.63 10
1043
10
1,25 1018
>> 10
4.43
108
10
NAMITHISGAMAag
3.66 x 1616
1.88 x 10"
3.11 10
7.25 10
3.80 X 10?
5.08 x 10
9.60
10
2.30
X 10
PUOENIX10
6.37 16
1.45 1041
10
3.72 10
1.7 10
10
3.37
10
6.55
10
PoNG20
3.66 x 1616
1.12 1612
3.11 10
3.06 x 10a
8.64 X 10
5.50 X 10a
1.00
X 10a
4.60
x 10a
PoNGs0
10
1.25 10
10
10a
4.66 10
10
9.70
10S
6.40
107
PoNGap
2.67 x 16
1.18 X 20
1.26
1
3.85 10
2.35 X 16'4
4.93 X 10
3.38
10
2.49
X 107
PoNGse
2.02 t0
1.22 20
20
107
4.71 10
> 10
10
10
PONG70
1.03 x 1066
6.08 10
1,39 x 20
1.21 x 10
3.66 X 1025
> 3 106
>
5 106
108
PoNG1no
3.27 7079
2.05 10
20
10
3.60 10
> 10
10
10a
PRIVATEBBE10
1.79 x 1018
8.64 x 10
1.10
16
2.32 x 106
1.39 107
4.20 X 10
2,50
1
7.74
104
Qвιктдо
3.02 10
3.80 108
7.78
10a
1.78 10
7.78 10
3.39 X 10
1.30
10
2.41
10
QsaKign
3.66 x 1016
2.36 x 10th
4.03 X 10
4.51 x 10
4.99 X 1613
5.75 X 10
2.95
10
1.71
107
ROADRUNNERIO
1.79 1045
7.34 10
1.98
10
x 10
2.62 X 10
8,10 X 10
1.32
10
2.24
10
SEagunsT;
1.79 1013
4.15 169
1.69 x 10
9.84 x 10
3.60 10
4.00 X 10a
1000
3.58
10
SKBNGGO
2.95 x 10
6.83 x
5.90
5.25 10a
5.90
> 3 10
3.58 X 10
8.53
1
SPACEINVADRB550
3.02 10
4.38 10"
2.16 10a
5.96 x 10a
2,28 10
4.40 X 10a
1.30 X 1
1.20
10
T
1.79 x 10
2.29 x 1
3.40
6.82 x 107
1.01 x 10
> 5 X 10
5.94 x 10a
1.17
1
TIXEPiLOTO
5,00 1010
5.76 107
1.00 10
5.03 x 10a
8.83 10
3.30 10
2.06 x 10
7.00 10
50

---

6.37 10
1.68 10
1.34 x 10
1.33 10
8.40 10
3.19 10
4.98 10
2.04 10
1.74 x 1940
5.10 x 1644
4.30 x 10"
1.13 x 10?
1.38 x 10
> x 10
1.58 x 10
6.64
104
WiZARDOrWoaan
1.00 10
3.78 10
4.00 10
10
10's
10
10
-00
BIGmSH AP
1.74 1040
1.74 x 1619
4.57 16
2:26 1041
6.56 10
4.30 10
2.47 x 10
2.08 x 10
3.87 10
4.68 x 10
5.30 x 10
> 2.5xx0
1.21 x 10
1.10 10a
1.14
1.79
107
16
BaausI
1.74 x 10
5.26
1041
3.49
10
1.76 x 10?
3.49 10
> x 10
1.58
16
> 108
BIGmsI
1.74 1010
4.19 10
4.78
10
10
1.30 10
10
3.10
10
3.99
104
CRASER
1.22 x 16t0
2.32 16
6.24
10"6
1.46 x 10
6.89 10
4.42 10
2.03
10
2.38
10
CHASER
1.22 1020
3.23 10
10
T.16 10
6.27 10
> 233x3 10
3.33
10
2.30
10
CHASES
1.22 1620
2.67 1648
1.39 x 16
9.05 x 10"
4.95 x 16
2.42 10
8.17
10
7.87
109
CHASER
1.22 1020
2.07 10
6.40
10
1.58 10
4.86 10
> >3x 10
>.
10
CLIMBER
1.74 1610
2.67 1611
4.78
10a
2.18 X 107
1.59 109
2.50 104
1.43
10
4.50
103
CLIMIn
1.74 1640
8.46
1646
3.87
10
1.06 X 10"
6.89 X 10
7,30
10
3.03
10
3.21 X 104
CLIMBER
1.74 16
8.43 10
10 5.31
10
5.04 10
10
10
5.67
10
CLIMBER
1.74 x 16th
2.68 16
3.49
x
2.09 X 10
2.09 X 10
2 10
>
5 10
1.94 X 107
COINRUN
x 1040
1.77 10
4.30
10
x 10
9.33 10
1.14
10
2.03
10
8.35
10
COINRUN A
1.74 1649
4.05 1640
4.78
16
6.61 x 10
2.88 10
5.40 X 10
8.60
X 10
1.72
10
COINRUN
1.74 10
1.30 10
3.87
10
1.57 x 10
5.88
9.32 X 10
4.91
10
5.08
10
COIMUN
1.74 1640
1.34 16
4.78
10
107
1.44 X 10
10
6.00
10
10
DODGIBAL 5B
5.00 x 16
1.47 16
1.00 16"
1.19 10
1.51 X 10
1.31 10
9.80
10
1.76
10
DODGERALL
16
1.29 10
10
10
2.99 10
10
10
5.08
10
DODGEBALL
5.00 x 16
1.31 1612
1.00 x 10
3.42 X 10
4,98 10
1.74 10
1.26
X 10
1.59
X 104
DoDUBBALL
5.00 x 1040
1.42 10
1.00
10
7.24 X 10
1UD
10
> 3
4.88
10
8.16
10
2.96 x 16
9.28 x 10
5.58
10
8.28 X 10a
9.80
16
5 10
1.44
10
4.00
107
2.96 x 10
2.40 10
2.40
20
1,36 x 10
1.74 1026
> 5 10
3.61
16
> 108
FRUITIOT
10
4.47 10
1.30 10
10
1.43 10
10
2.00
10
1.01
104
FRUITBOT MM
2.96 x 16
2.62 X 16t5
1.28
10
2.23 x 10
1.17 X 2
> 5 10
> 5 168
> 10
1.74 x 1010
10
10
10
1,06 10
10
10
7.09
107
JUMPER ko
1.74 x 1640
5.11 X 16
3.49 x 10
1.17 x 107
1.41 X 1040
3 10
5
10
10
JUMPUn
1.22 10
1.77 10
3.60 10
2.15 x 10
3.60 10
20
374
JUMPER
1.22 10
4.02 16
3.21 10
1.49 X 10
7,20 103
4.96
1
JuMPuE
1.22 x 10
2.59 X 10
2.36 10
2.48 10
8.64 x 10
2.56 X 19
7.00 X 10
3.42 x 104
JUMPER
1.22 1020
2.18 1021
6.67
10
6.13 X 10
121 1018
5 10
5 10
10
LEAPER
1.22 x 16
2.96 x 10
7.41
10
1.90 105
2.16 16t3
> 10
> 55X 10
> 10
LEAPER
1.22 20
10
10
107
4.90 10
1.27 10a
2.34 X 10
2.94
10
LEAFUR
1.22 1620
3.U7 1621
8.24 x 16
3,08 x 10
1,2 X 1646
> 23x10 10
5 10
10
1.22 20
3.23 10
7.41
5.96 X
7.04 1044
> 23X11 10
2.61 X 108
108
Maze
6.36 16
4,95 10th
8.10 10
6.59 10a
1.62 10a
1000
66
4.57 10
MAZE
6.36 x 29
2.71 x 20
7.98
10
3.95 10
3.41 1016
> 10
>. 5 10
1
Maz
6.36 1629
1.35 10
6.66 105
10
1.62 10
1000
411
1.36
104
Mazi
6.36 x 20
2.48 x 1025
1.85
10
4.73 X 10
3.01 X 1040
>> x5x 10
> 5 16
> 10
Maza
10
4.27 16
1078
10
10
>5 10
10
10
MINER
1.74 16
4.81 16
4.30 10a
5.37 X 10S
4.58 X 10
9.40 10
7.40
10S
4.69
10
MINar
1.74 1010
10
10
10S
9.34
3.77
X 10
1.74
10
MINER
1.74 16
4.82 10
7.29 10a
5.00 10S
1,80 10a
1.02 X 10
2.00
10
1.79
x 10
MINEr
1.74 x 1010
5.04 X 10
4.78
10
9.35 X 10c
1.92 x 10
4,90 X 19
4.03
X 10
4.50
3
N
1641
2.67 1012
1.06
10
10
10
10
>
10
6.32
100
NISIA 19
NixIa
6.89 x 16
10
2.82 16
10
8.16
10
10
6.33 X 10
10
2.43 x 10
5,97 10
4.45 10
> 10
4.23 10
5 10
1.85 X 10
10
NEsIATO
6.89 x 16
2.47 10
1.38
10
8.60 X 10
3.57 X 10
> 55X 106
>
5 106
10
PLUNDER
5.00 x 1010
1.26 10
1.00
1.55
2.00
1.15 10a
1.00
10a
5.00
10
PLUNDER
5.00 1010
1.29 10
1.00 x 10
2.06 X 105
1000
2.00 X 10
3.00
10
2.00
10
PLUNDER
5.00 x
1 x 12
1.00
102
9.99 10
1.96 X 10
6,40 X 19
1.13
16
2.10
104
PLUNDER
5.00 1010
1.20 10
1.00 10
10
2.00 10
10
6.00
10
4.00
10
STARPHLT
1.30 10t2
4.09 1 16
2.36
10
3.56 0 107
1.99 X 10
>> 5 10
6.36 X 10
7.02 x 10
STARPILOr
1,30 x 1
3.93 10
2.14 10
107
6.90 1
10
X 10
6.24
STaRpH
1.30 1612
3.77 x 1612
1.95 x 10"
1.05 x 107
2.36 16
9.90 X 10
2.67 X 10
2.61 10
STARPILOT
1.30 x 1
4.02 x 1
2.14 X 10
2.71 X 10"
1.04 x 10
> 5 10
5.12 X 10
2.15 107
FMPMT-5X5
2.58 x 19
1.76 x 10
2.43 x 10
1.11 x 10a
6.00 10
1.02 x 10
252
3.86
104
EMPпу-6X6
19
3.47 10a
10
10"
1
10a
4.50
1
EMPTT888
2.58 x 10
9.28 X 10
1.77 10"
4.35 x 10a
2.70 x 10
1.57 x 104
7.90 x 16
8.49 X 104
EMPTY-16X16
2.58 10
L.2 10
10
10a
5.93 107
10a
3.81
10a
3.02
107
Do0RKEY-5XL5
3.27 x 1079
3.85 x 10
3.63
10
1.59 x 10a
6.30 10
7.01 X 104
1.45
x 10
8.17
10
DooRKEV-626
3.27 7079
10
10
10a
7,51 10
10
2.85
10
6.79
10
DoORKEY-SXS Sxx
3.27 x 1679
2.27 x 17
1.69
10
5.53 10
1.34 10
8.35 X 10
7.23
10
10
DuokKev-16x16
3.27 1979
1.04 X 1044
3.68
1028
2.15 10a
LU1 x 10
>> 3 10
> 5 10
108
MULTIROOM N4
3.27 x 1079
3.27 x 107
2.80
x 109
3.66 X 10a
7,80 10
3.63 X 10
1.23
10
9.98
X 104
MULTIRooM-N4-55
3.27 1979
1.29 10
3.42 10
1.33 1047
> 5 10
> 10
108
MUrTIRoOM-N6
3.27 1679
3.81 X 1074
6.24
10
6.72 10
1.84 1023
2 10
> 10
10
XEYCOSRIDORS3RI
3.27 7079
2.10 x.10x110
4.70
10
1.01 X 10a
1.46 x
3.31 10
1.72 10a
2.62
10
KnYCoRRinoE5382
3.27 1079
2.48 x 1646
4.70
10
2.94 x 10
4.21 X 107
6.32 X 10
3.40
10
6.59
X
10
KEYCORRIDOES3RS
3.27 x 7079
6.27 x 2T
1.69
10
6.48 10"
1.80
1.01 X 10
1.33 X 108
3.01
107
KEYCORRIDOBS-IR
3.27 1079
1.68 10
3.66
X 10
3.62 X 1
1.77 10
> 10
5 106
10
UNLOCK
3.27 x 7979
1.36
4.70
10
6.51 X 10a
3.76 x 107
1.79 X 10
2.70
10a
5.36
10
UNLOCKPICKUP
3.27 1079
6.26 1019
2.82
10
1.03 107
1.31 10
6,00 10
3.58
10
1.37
107
BLOC BLLCKKEDUNLOEPPICKK
3.27 x 1979
5.85 10
4.74
10
3.06 108
1 x 10
1.81 X 10
>
5 16
> 108
OBSTRUCTEDMAAZE IDL
3.27 7079
1.92 10
7.84
10
1.92 106
6.09 x 107
4,31 X 10
4.05
10
6.09
106
Obstrue Maw-
3.27 x 7979
7.25 x 1012
4.70
x 10
2.61 x 106
1.77 x
7.32 x 19
1.96
10
2.12
107
OusTrue Mam
3.27 1979
6.05 10
1020
4.04 107
1.25 10
10
108
10
FOURROOMS
3.27 x 7979
7.25 x 16t0
4.70
15
6.22 10
9.54 x 107
> 5 105
3,26 x 10
1.00 107
51

---

10
10
10
10
10
10
1.80
10
10
LAWCROSSINGSON
3.27 X 1079
3.66 x
7.84 10
7.98 x 10
1.63 x 10"
2.93 x 16
1.53
16
2.09
10
1679
107
10
10
107
10
10
10
LAVCROSSINGSINS
3.27 x 1079
1.74 10
2.19
10
5.10 10*
1.19 16
> 5
16
>
16
10a
10
10a
10
10
10
1.02
10
SIMPLECROS 2
3.27 x 1079
1.41 10
7.84
10
7.96
10
1.01 10
9.63
10
2.15
10
1.55
10
1079
1.04 102
10
104
1.16 107
10
10
2.64
10
INPLECROSSINGSIIS
3.27 x 1679
2.71 10
2.19
10
5.10 10
2.49 x 10
5.42 X 10
1.26
106
10
1079
10
10
104
2:40
10
10
4,33
104
LAYAGAPS6
3.27 x 1679
1.15 10
1.01
10
3.18 10
2.28 x 10
1.49 X 10
2.35 X 10
1.96
10
7079
10
10
10
6.78
10
10
8,20
10
G.5
Table of returns
This table lists the returns for the random and optimal policies in each MDP as well as the final returns achieved by PPO, DQN, and GORP. We ran PPO and DQN for 5 million timesteps in each environment, and GORP for both 5 million and 100 million timesteps.
Returns
MDP
Random policy
Optimal policy
PPO
DQN
GORP (5M)
(100M)
ALIEN10
74.74
160
160
160
160
160
AMIDAR20
6.77
109
68
68
65
68
1SSAULT
8.66
126
126
126
126
126
ASTERIX16
99.24
100
400
100
ASTEROIDS10
15.08
320
170
190
220
220
ATLANTIS10
24.22
200
200
200
200
200
ATLANTIS20
124.25
1,0
1,200
200
1, 200
200
ATIAANTIS30
1 145.46
4,300
1,600
600
1,700
4, 000
ATIAANTSS
146.68
5, 500
5, 500
5, 400
5, 400
5, 500
ATLANTIS50
1 146.84
7,800
7, 600
5, 500
5, 600
7, 700
ATLANTIS20
146.86
100
8, 2..00
8, 9000
8, 200
10, 900
BANKHEESTTO
0.36
30
30
30
30
30
BATTLEZONE
115.32
2,000
2, 000
2, 000
2,
BEAMRIDER20
23.77
132
132
132
132
132
BOWLING
1.82
9
9
9
9
BREAKOUT10
0.13
2
2
2
2
BREAKOUT20
0.17
4
4
BREAKOUT30
0.18
9
7
BREAKOUT
0.18
11
9
9
11
BREAKOUT:0
0.18
13
10
10
10
13
BREAKOUTTO
0.18
22
13
14
17
BREAKOUTI00
0.18
14
19
BRFAKOUT200
0.18
14
17
CENTIPEDE
141.37
1,923
922
632
1,511
1.
621
CHOPPERCOMMANDI
117.25
600
600
600
600
600
CRAZYCLIMBER30
125
400
400
400
CRAZYCLIMBERS0
248.16
900
900
900
900
DEMONÁTTACKI0
8.31
50
50
50
50
50
ENDURO10
0.04
6
6
4
6
FISHINGDERBY1e
0.16
8
8
6
8
1REEWAY
0.01
1
FREEWAY20
0.02
2
2
2
2
FREEWAY30
0.07
4
4
4
4
4REEWAY
0.1
5
5
5
5
FREEWAY50
0.14
6
FREEWAY70
0.23
9
FREEWAY
0.33
13
12
12
9
12
FREEWAY200
0.72
25
24
25
12
20
FROSTBITE
9.13
70
70
70
70
70
30
1.43
20
20
20
GOPHER40
10.05
180
100
100
100
180
HERO
8.18
75
75
75
75
75
JCEHOCKEY
0.01
1
1
1
KANGAROO2
1.02
200
200
200
200
200
52

---

KANGAROOSO
3.84
500
200
200
400
400
MONTEZUMAREVENGER
0
100
0
0
MSPACMAN
148.91
480
460
470
470
NAMETHISGAMEzu
11.22
180
180
180
180
180
PHOENIX10
23.43
260
260
260
260
260
PONG20
-2.71
PONGs0
-4.25
PONG40
-5.99
0
PONGso
-7.85
1
0
0
PONG70
- -11.47
2
0
1
0
PONG100
16.91
PRIVATEEYE10
0.11
100
100
100
QBERT
50.95
425
425
425
425
425
QBERT
87.21
675
675
675
650
675
ROADRUNNERIo
0.05
600
600
600
600
600
1E
0.78
20
20
20
20
20
SKINGG10
12,
652.16
-7, -66666
8, 149
078
7, 069
7,
066
SPACEINVADERSjU
3.46
40
40
40
40
40
TENNIS10
-0.75
1
1
1
TIMEPILOT1O
8,17
200
200
200
200
200
TUTANKHAM10
0.07
23
23
VIDEOPINBALL
108.99
4, 100
3, 000
4, 100
4, 1,10
4, 100
WIZARDOFWOR30
11.5
500
100
100
300
400
BIGFISH B0
0.37
4
4
4
4
BIGFISI
0.73
3
3
BIGFISHID
2.98
8
8
7
7
BIGHSHI
0.03
3
3
CHASER F6
0.38
0.88
0.88
0.88
1
CHASER
0.33
0.88
0.88
CHASER
0.37
0.88
0.88
0.88
CHASER
0.39
0.88
0.88
0.84
CLIMBER
0.14
2
2
2
2
CLIMBER
0.02
2
CLIMBER
0.03
11
11
11
11
11
CLIMBER
0.31
1
COINRUN
0
10
10
10
10
10
COINRUN
10
0
10
COINRUN
0
10
10
0
10
10
COINRUN
0.08
10
10
10
10
DODGEBALL FO
0.08
16
16
16
16
16
DODGEBALLI
0.24
8
8
DODGERALL1
0.1
8
8
8
8
DODGEBALI
0.04
6
FRUITBOT Eo
4.04
5
5
2
5
FRUITBOT
22099
7
7
5
FRUITBOT 40
F3
5.88
1
FRUITBOT
-0.42
10
9
HEIST Fl
0
10
0
10
JuMPER
0
JUMPER
4.99
10
10
10
10
10
JUMPER
4.96
10
10
10
JUMPER
0.06
10
10
10
JUMPER
0
LEAPER
0
10
0
0
LEAPER
0
10
10
10
10
LEAPER
0
10
0
LEAPER
0
MAZE BD
30
6.1
10
10
10
10
10
MAZE 30
0
MAZE
F3
5.65
10
10
10
10
10
MAZE
0
53

---

MAZE100 FX
0
10
0
0
0
MINERTO
1
MINER F]
0.05
2
2
2
2
2
MINER
0.11
1
MINER HD
0.04
3
3
3
3
3
NINJA
10
0
10
NINIA KI
0
10
10
0
10
10
NINJA
0
0
NINJA HD
0
10
0
0
0
PLUNDER
0.06
PLUNDER
0.17
PLUNDER
PLUNDER 1D
NO
0.07
1
STARPII
0.23
10
10
STARPILOT
0.14
5
5
5
5
STARPILOT
0.08
5
5
STARPILOT f80
0.17
5
5
4
EMPTY-5X5
0.76
1
EMPTY-6X6
0.5
EMPTY-8X8
0.18
EMPTY-16X16
0
0
DOORKEY-5X5
0.01
DOORKEY-6X6
DOORKEY-8X8
D
MULTIROOM-N2-S4
0.09
MULTIROOM-N4-S5
MULTIROOM-N6
KEYCORRIDORS3RI
KEYCORRIDORS3R2
KEYCORRiDOR$3R3
KFYCORRiDORS4R3
0
1
UNLOCK
0
UNLOCKPICKUP
BLOCKEDUUNLOCKPICKUPP
OBSTRUCTTEDMAZZE-IDD
OBSTRUCCTEDMAAZE-IDDI.
OBSTRUCTEDDAAZE-ID..S
FOURROOMS
LAVACROSSINGS5NI
LAVACROSSINGS99N
LAVACROSSINGS99N3
LAVACROSSINGSIIIN
SIMPLECROSSIIGSSNNI
0.01
SIMPLECROSSSINSSNN2
0
SIMPLECCROSSINGSS9N3
0
0
SIMPLECRRSSINGGSI INS
LAVAGAPS5
0.07
1
1
1
LAVAGAPS6
0.02
LAVAGAPS7
0.01
1
54

---

G.6 Learning curves for BRIDGE MDPs
Bouteat
Comp
Co
Temmm
Gera
Kasrote
635
Modd
Mov
Nosdi
Moa
A
Shoun
Dariiso
Daristel
Daekendd
Daakeddd
22
15V
Figure 10: Learning curves for PPO, DQN, and GORP all the MDPs in BRIDGE. Solid lines show the median return (over multiple random seeds) of the policies learned by each algorithm throughout training. We random seeds for PPO and DQN and 101 random seeds for GORP. The shaded region shows the range returns over all random seeds for PPO and DQN, and shows the range from the 10th to 90th percentile over random seeds for GORP. The optimal return in each environment is shown the dashed black line.
55


Reviews:
[{"review_id": "Bfe540W8K9", "reviewer": "Reviewer_rChU", "summary": "The paper aims at addressing the gap between RL theory and deep RL practice. \nThe central finding of the paper is a property that correlates well with the performance of PPO and DQN algorithms on a set of 155 environments (such as Atari, Procgen, and MiniGrid).\nThe property looks at whether the argmax action of the action-value function under the random policy coincides with the argmax action of the optimal action-value function. \nInspired by the property, the authors propose a complexity measure called the effective horizon that corresponds to the number of lookahead search steps needed to identify an optimal action, given that the leaf nodes are evaluated under the random policy.\nBounds that utilize the measure correlate with empirical sample complexity of PPO on the collection of 155 games (r = 0.79 for PPO and r = 0.65 for DQN).\nLastly, the paper demonstrates the predictive power of the effective horizon when using reward shaping and pre-training.\n", "questions": "Could you quantify the agreement between the (exact) action-value function corresponding to a random policy and a Q-network with randomly initialized parameters? If the agreement is high, it'd somewhat imply that for many domains the weights are initialized at a point that is almost an optimal solution; such a finding would be even more surprising.\n\nThe reviewer would suggest to take a look at the Policy Churn paper [1] that observes that the argmax of the learned action-value function in DQN-based methods changes in 10% of the states after each parameter update. The observation might be related to the high predictive power of the measure the authors observe.\n\n[1] Schaul, Tom, André Barreto, John Quan, and Georg Ostrovski. \"The phenomenon of policy churn.\" Advances in Neural Information Processing Systems 35 (2022): 2537-2549.\n\n\n", "limitations": "\nPerhaps the main limitation is that the effective horizon could be used for analysis purposes only; from the practical viewpoint, it is unclear how for a large MDP estimate efficiently the effective horizon (and thus obtain the sample complexity for the MDP).\n", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is well-written and easy to follow.\n- Motivation is solid: the paper makes a step certainly in the right direction as the gap between RL theory and practice is tremendous.\n- The personal experience of the reviewer with the submission started from \"That's surprising\", followed by \"It can't be true\", finally reaching \"Ah, it makes sense\", implying that the paper offers an interesting and non-trivial way to think about RL. One of the take-aways for the reviewer is that if the policy evaluation is done perfectly, there might be a need only for just a few (sometimes zero) policy improvement steps.\n\nThe reviewer is inclined to recommend the paper for acceptance because it is likely to generate a fruitful discussion in the community.\n", "weaknesses": "There might be certain weaknesses that the reviewer didn't notice but as of now there are none that feel worthwhile mentioning; having said that, the reviewer has limited experience with complexity bounds in RL and maybe more experienced RL theory person will be able to identify the limitations of the analysis.\nThe reviewer is looking forward for the discussion phase.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful and thoughtful review. We appreciate that the reviewer found that our work offered “an interesting and non-trivial way to think about RL.”\n\n**Difference between random policy’s Q-function and randomly initialized Q network:** In this work, we only focus on the Q-function of the random policy; we never analyze the Q function corresponding to a Q network with randomly initialized parameters. We would not expect a randomly initialized Q network to provide any useful information about which actions to take. We will clarify this point in the paper.\n\nThe Policy Churn paper is quite interesting and could help explain properties of deep RL algorithms related to their use of neural networks. However, in this paper we show that (in deterministic environments) deep RL performs quite similarly to GORP, an algorithm which does not use neural networks at all. This suggests that one can gain significant understanding of deep RL without understanding its neural network components. We hope that future work like the Policy Churn paper will further explore how neural networks interact with deep RL.\n\n**Limitations on the practical use of the effective horizon:** We agree that in many cases it is intractable to explicitly calculate the effective horizon. We argue in the Limitations section on line 408 that “despite this, [the effective horizon] serves as a useful perspective for understanding RL’s effectiveness and potential improvement areas.” We hope that practitioners can gain an intuitive understanding of the effective horizon from our paper that helps them use deep RL more effectively.\n"}, {"review_id": "zURkHH2bWJ", "reviewer": "Reviewer_GiSj", "summary": "The paper investigates the question of what finding an explanation for the performance of deep RL algorithms. To accomplish this, the authors propose the notion of effective horizon. It is found that this notion is better able to answer questions about sample complexity and effect of reward shaping or policy initialization in RL than all prior theoretical bounds.", "questions": "1. Does GORP with a particular effective horizon outperform DQN/PPO? This experiment seem to be missing in Figure 5 and figure 10 where k is fixed to be 1.\n2. How is line 7 in Algorithm 1 performed in practice? Is the whole list of possible actions enumerated to find the best one? If so, does the method assume known model of the environment? In that case, why does comparing to only model-free methods make sense for sample complexity bounds?\n", "limitations": "Authors address the limitation in Section 7 of the paper.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Strengths:\n1. The first great part about the paper is the writing. Reading the paper is easy and flows well. \n2. The authors present a surprising finding - on a large fraction of environment just evaluating random policy with one step of policy improvement leads to optimal policy. For the rest if the environments, a few steps of value iteration usually leads to optimal policy. This is in contrast to previous ideas and theory in RL which are unable to explain when RL fails in certain environments and when it will work. \n3. Authors propose a new method GORP (Greedy over random policies), which performs a few step of policy improvements over a random policy and is shown to be a competitor to PPO and DQN algorithms even for long horizon.\n4. The experiments demonstrate that the theoretical bounds for GORP neatly explains empirical bounds obtained by DQN/PPO on complex environments by measuring quantities like correlation, medium ratio, etc. \n5. The analysis in the paper is also the first to explain the effect of reward shaping and initializing RL with a policy using the GORP bound.  The effective horizon bound has a correlation of around 0.4 in both of these settings (reward shaping and policy initialization) which is more than other bounds which are agnostic to reward or do not consider the effect of policy past the horizon.\n", "weaknesses": "Weaknesses:\n1. Unlike prior bounds using UCB and EPW, GORP seems to require oracle information to compute the effective horizon. Can the authors comment on the implication of this in the paper? For example, we can’t use GORP bounds to compute sample efficiency without having an algorithm that solves the task first. \n2. It is claimed that GORP achieves an optimal policy in almost all the environment when a effective horizon > 1 is used (Line 77), but the experiments for this seem to be missing. Learning curves and final performance along with effective horizon used would be important to support this claim.\n3. Novelty of GORP: It would be important to do a more thorough literature review with prior works in the area which proposed an algorithm very similar to GORP in order to clarify the novelty there:\na. MCTS\nb. Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm, Silver et al\nc. Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model, Schrittwieser et al\nd. Plan Online, Learn Offline: Efficient Learning and Exploration via Model-Based Control, Lowrey et al\ne. Learning Off-Policy with Online Planning, Sikchi et al\nf. Model-Based Offline Planning, Argenson et al", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thorough and thoughtful review. Below are responses to questions and comments raised in the review.\n\n**Effective horizon vs $k$:** First, we noticed that there may have been some confusion between the value of $k$ for which an MDP is $k$-QVI-solvable versus the effective horizon $H$. $k$ relates to the number of steps of value iteration that need to be applied to the random policy’s Q-function before one can act greedily to solve the MDP (Definition 5.1). The effective horizon (Definition 5.2) combines $k$ with $m_k$, which is the number of random rollouts collected for each action sequence in GORP (see Figure 1 or Algorithm 1). We will clarify the difference between these two values in the paper.\n\n**Requiring oracle information to compute the effective horizon:** While it is true that one needs access to the tabular representation of the MDP to compute the effective horizon, in practice this is true for UCB and EPW bounds too. UCB bounds depend on the number of states in an environment, which is often unknown. The number of states can sometimes be upper-bounded, but so can the effective horizon (since $H \\leq T$ always). Exploring every state to count them may be as hard or harder than solving the MDP. EPW bounds also require access to the optimal policies for an MDP, since one needs to know which actions are optimal to know if those actions can be found by only considering rewards in the planning window. We will clarify this in the paper.\n\n**Claim that GORP achieves an optimal policy in many environments:** We refer the reviewer to Appendix H in the supplementary material for the full results of our experiments on GORP. Appendix H.5 lists the effective horizon for each environment; Appendix H.7 lists the final reward achieved by each algorithm, including GORP; and Appendix H.8 has learning curves for PPO, DQN, and GORP in all environments.\n\n**Novelty of GORP:** We thank the reviewer for the references to related work on Monte Carlo planning. We note that GORP may be similar to Monte Carlo planning algorithms, but is novel because it is actually *not* a planning algorithm—instead, it is a model-free RL algorithm. It does not use a learned or specified world model, unlike all the given references. One of our key contributions with GORP is to show that model-free RL algorithms like PPO and DQN may implicitly be doing something similar to Monte Carlo planning despite appearing quite different.\n\n**Does GORP with a particular effective horizon outperform PPO/DQN:** Again, we note that $k$ is different from the effective horizon $H$. However, we will include results for GORP constrained to $k=1$ in the final paper. For instance, GORP with $k=1$ has a lower sample complexity than DQN in 67 of the 99 environments in BRIDGE where DQN converges; with any $k$, this rises to 81 of 99. GORP with $k = 1$ also outperforms PPO in 39 of 98 environments where PPO converges, compared to 56 with any value of $k$. Finally, note that we compared GORP against PPO and DQN on long-horizon Atari games in Figure 5; we used only $k = 1$ for those experiments (see Line 1571).\n\n**Line 7 in Algorithm 1:** In Line 7 of the GORP algorithm, the argmax action is chosen based on the estimated Q values for each $k$-action sequence, which are calculated inside the loop on Line 5. Each loop consists of several rollouts following the existing learned policy up to timestep $i - 1$, then following a particular action sequence $a_{i : i + k - 1}$ for timesteps $i$ to $i + k - 1$, and then acting randomly; the mean of the rewards across rollouts is computed and saved as the approximate Q-value $\\\\hat{Q}\\_i(s\\_i, a\\_{i : i + k - 1})$  for that action sequence. On Line 7, the sequence with the highest estimated Q-value is found and its first action is selected as the policy’s action for timestep $i$. None of these steps uses a model, so the algorithm is model-free."}, {"review_id": "iTK2EHEp8u", "reviewer": "Reviewer_iUUZ", "summary": "This paper proposes a new complexity metric, denoted as effective horizon, for deterministic MDPs. It is defined as the number of full value iteration updates starting from an initial policy, plus a logarithmic factor for concentration bounds, needed to reach an optimal policy. A corresponding algorithm, GORP, is also suitably defined. The bound is calculated for a set of 155 deterministic MDPs, and compared with empirical sample complexity of PPO and DQN, and is shown to correlate decently well compared to other sample complexity bounds. It is also shown how the effective horizon can be applied to shaped rewards or different initial policies to get a better problem-dependent estimate of sample complexity.", "questions": "How do you define optimal policy across your environments since your episodes are relatively short? Many Atari games go on for thousands if not hundreds of thousands of timesteps, so what does it mean to reach optimality?\n\nFor the empirical GORP results in table 2, what value of k and m were used? Did you sweep over k to find the best k? Or use the smallest k that reaches optimal?\n\nFor table 2, for the horizon T, were you using the horizon of the tabular representation (i.e. after frameskip)? If so, there is a degree of arbitrary choice here, as many of the Atari environments had large frameskips of 30, which greatly reduces the T needed to see reward. If frameskips were smaller, such as 4, and horizon increased accordingly to accommodate, then all theoretical bounds would be even more orders of magnitude off from empirical sample complexity.\n", "limitations": "Are addressed in the paper.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "There are extensive results and analyses in the paper and appendix, with good comparisons to other sample complexity measures. The task of converting many large MDPs to tabular representations and computing bounds can be very useful for future research on tighter theoretical bounds.\n\nThe proposed measure of effective horizon does seem to have good correlation with empirical algorithms, and intuitively makes sense, as the number of value iteration steps can correlate with the number of gradient updates to a value network.\n\nThe biggest strength of effective horizon is that it is policy and reward dependent, which makes it much easier to apply (as the paper points out) to shaped rewards and better initialized policies.\n", "weaknesses": "There are many references to tables or figures in the appendix without marking them as being in the appendix, which can be confusing.\n\nAs mentioned in the paper, there are several limitations such as being only for deterministic MDPs, and hard to compute in general for large MDPs. Nevertheless, the initial results do demonstrate the viability of this type of bound, which future work can take and build upon.\n\nAnother downside is that the effective horizon can be hard to apply to algorithms with additional exploration built-in, such as using an intrinsic reward. This is due to the fact that the intrinsic reward is non-stationary and changes over time, so the effective horizon would only give a bound for a specific snapshot of intrinsic reward, rather than the entire training process. How to handle non-stationarity could be an interesting future direction.\n\nSome concerns about the experiments are brought up in the questions section below.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comprehensive review. We appreciate that they found our results “extensive” and that they think the tabular representations in our BRIDGE dataset “can be very useful for future research on tighter theoretical bounds.” Below are responses to individual comments and questions.\n\n**Optimal policy in short-horizon environments:** As the reviewer noted, the environments in the BRIDGE dataset have relatively short horizons compared to many typical RL benchmarks. We found that it was intractable to compute the tabular representations for long-horizon environments since the number of states reachable over long horizons was too large. Thus, we use horizon-limited environments for most of the results in the paper. We define the optimal policy as the policy which achieves the highest return over the limited horizon $T$ of the environment.\n\nNote that we run the deep RL algorithms and GORP in the horizon-limited environments too such that they are exactly equivalent to the tabular representations. Thus, the maximum possible return achievable by PPO, DQN, and GORP is exactly the same as the return of the optimal policy in the tabular representation. We only use the normal Atari settings (frameskip=4, horizon=27,000) for the experiments in Appendix H.1. We will clarify this in the paper.\n\n**Values of $k$ for empirical GORP sample complexity:** For the results in Table 2, we swept over values of $k$ and chose the value with the smallest sample complexity. However, even if we restrict GORP to using $k = 1$, we find a Spearman correlation of 0.69 for PPO and 0.69 for DQN between the GORP sample complexity and the deep RL sample complexity. This is still about as well as PPO or DQN correlate with each other, indicating that GORP is quite similar to PPO/DQN even when $k$ is not tuned. We will include these results in the final version of the paper if accepted.\n\n**Values of horizon $T$ in Table 2:** We use the horizons for the horizon-limited versions of these environments. As described above, these are the versions that PPO, DQN, and GORP are trained in as well, so there is no arbitrary selection of horizon—it is based on the environment that the RL algorithms are interacting with. If we made the frameskip smaller, it might change the theoretical bounds, but it could also significantly change the empirical sample complexity of PPO and DQN since they will also need to interact with the environment for more timesteps to see rewards.\n\nOur results in Appendix H.1 show that GORP is also quite similar to PPO/DQN over much longer horizons like those normally used for benchmarking deep RL algorithms. Since the effective horizon is based on GORP, we also expect that the effective horizon-based bounds would closely reflect deep RL performance with longer horizons and smaller frameskip (although we can’t test this exactly since it is intractable to compute tabular representations of the long-horizon environments).\n\n**References to tables and figures in the appendix:** We thank the reviewer for pointing out that these references are confusing as they are now. We will make it more clear when references are made to the appendix.\n\n**Application to algorithms with additional exploration strategies:** We agree that this is a limitation of our analysis and will mention it in the paper as a direction for future work."}, {"review_id": "WYf3sNcWpZ", "reviewer": "Reviewer_KSUv", "summary": "The authors aim to improve the theoretical understanding of RL. The contributions of the paper are as follows:\n1. The authors curated a dataset called BRIDGE consisting of 155 deterministic MDPs along with their tabular representations\n1. The authors found that, for a given deterministic MDP, deep RL is more likely to succeed **if the policy acting greedily w.r.t to the random policy's Q function (which can be obtained via dynamic programming) is optimal**.\n1. Motivated by the property in the last bullet point, the authors propose a complexity measurement metric called **effective horizon** that roughly measures the number of steps of look-ahead search needed to identify the next optimal action.\n   * The authors show effective horizon is more reflective of PPO and DQN's empirical performance than prior complexity bound metrics\n", "questions": "The finding on the \"surprisingly common property\" is very interesting to me. I would be interested in more content on it. For example, how did you find this property? What is the motivation for finding the Q values of the random policy? Is there an example of how $\\prod(Q^{\\pi^{rand}})$ is constructed for a simple MDP?", "limitations": "Yes.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The paper proposes a highly useful benchmark of deterministic MDPs, which is helpful for more theoretical analysis instead of relying merely on results on black-box algorithms. The finding that deep RL is more likely to succeed if the policy acting greedily w.r.t to the random policy's Q function (which can be obtained via dynamic programming) is optimal is extraordinary and quantitatively verified. Furthermore, the effective horizon bound is highly efficient and predictive of the agent's performance, which is useful for future theoretical studies. Last but not least, the paper is well written. ", "weaknesses": "The paper is well-written, and it is good to see that the authors have released the training code. However, I do have a concern about the PPO training results with Atari. \n\nFigure 5 on page 44 shows the training results of Atari with 50M steps (200M frames). However, the scores obtained by PPO are considerably lower than those from popular RL libraries. Below is a table summarizing the performance difference between the results reported in this paper compared to the results reported for `openai/baselines` in the [openrlbenchmark project](https://github.com/openrlbenchmark/openrlbenchmark/blob/8a1248b63daef6b4bab78467a2d7356038b87042/README.md#compare-cleanrls-ppo-with-openaibaseliness-ppo2-on-atari-games). **The PPO in this paper used 5x more samples and produced only 1/3 to 1/15 of the scores of  `openai/baselines`.** While the settings are clearly different in some ways (e.g., I noticed the authors did not use frame stacking in the Atari preprocessing), the performance discrepancy is large enough that I think warrants further investigation. \n\n| Environment | this paper's RLLib PPO @ 50M steps | `openai/baselines`' PPO @ 10M steps |\n| --- | --- | --- |\n| Beam Rider | ~700 | 2835.71 ± 387.92 |\n| Breakout | ~30 | 405.73 ± 11.47 |\n| Enduro | ~200 | 986.69 ± 25.28 |\n| Pong | 20 | 20.45 ± 0.81 |\n| Qbert | ~1000 | 15228.25 ± 920.95 |\n| Seaquest | ~400 | 1518.33 ± 400.35 |\n| Space Invaders | ~200 | 1019.75 ± 49.08  |\n\nPPO has many implementation details ([Engstrom, Ilyas, et al., 2020](https://openreview.net/forum?id=r1etN1rtPB); [Andrychowicz, et al., 2021](https://openreview.net/forum?id=nIAxjsniDzg); [Huang et al., 2022](https://iclr-blog-track.github.io/2022/03/25/ppo-implementation-details/)) which may cause subtle issues. For sanity checks, maybe it's worthwhile conducting a PPO RLLib experiment with SB3's [Atari wrappers](https://github.com/DLR-RM/stable-baselines3/blob/master/stable_baselines3/common/atari_wrappers.py) for 10M steps. \n\nIf the performance is on par with  `openai/baselines` PPO results, then the PPO results of this paper can be attributed to different environment preprocessing. If PPO RLLib significantly underperforms, it could mean that PPO RLLib is not a proper PPO implementation, and the PPO results of this paper should be re-done with SB3's PPO, `openai/baselines`' PPO, or CleanRL's PPO, all of which are more well-benchmarked. \n\n\n\n\nP.S. According to https://github.com/openrlbenchmark/openrlbenchmark's documentation, you can retrieve the data above by running \n\n\n```bash\npip install openrlbenchmark==0.2.0\nwandb login\npython -m openrlbenchmark.rlops \\\n    --filters '?we=openrlbenchmark&wpn=baselines&ceik=env&cen=exp_name&metric=charts/episodic_return' \\\n        'baselines-ppo2-cnn?cl=openai/baselines PPO' \\\n    --filters '?we=openrlbenchmark&wpn=sb3&ceik=env&cen=algo&metric=rollout/ep_rew_mean' \\\n        'ppo?cl=SB3 ppo' \\\n        'dqn?cl=SB3 dqn' \\\n    --filters '?we=openrlbenchmark&wpn=envpool-atari&ceik=env_id&cen=exp_name&metric=charts/avg_episodic_return' \\\n        'ppo_atari_envpool_xla_jax_truncation?cl=CleanRL PPO (JAX)' \\\n    --env-ids BeamRiderNoFrameskip-v4 BreakoutNoFrameskip-v4  EnduroNoFrameskip-v4 PongNoFrameskip-v4  QbertNoFrameskip-v4 SeaquestNoFrameskip-v4 SpaceInvadersNoFrameskip-v4 \\\n    --env-ids BeamRiderNoFrameskip-v4 BreakoutNoFrameskip-v4  EnduroNoFrameskip-v4 PongNoFrameskip-v4  QbertNoFrameskip-v4 SeaquestNoFrameskip-v4 SpaceInvadersNoFrameskip-v4 \\\n    --env-ids BeamRider-v5 Breakout-v5  Enduro-v5 Pong-v5  Qbert-v5 Seaquest-v5 SpaceInvaders-v5  \\\n    --no-check-empty-runs \\\n    --pc.ncols 4 \\\n    --pc.ncols-legend 4 \\\n    --rliable \\\n    --rc.score_normalization_method atari \\\n    --rc.normalized_score_threshold 8.0 \\\n    --rc.sample_efficiency_plots \\\n    --rc.sample_efficiency_and_walltime_efficiency_method Median \\\n    --rc.performance_profile_plots  \\\n    --rc.aggregate_metrics_plots  \\\n    --output-filename figures/0compare \\\n    --scan-history\n```\n\n\n|                             | openai/baselines PPO   | SB3 ppo            | SB3 dqn           | CleanRL PPO (JAX)   |\n|:----------------------------|:-----------------------|:-------------------|:------------------|:--------------------|\n| BeamRiderNoFrameskip-v4     | 2835.71 ± 387.92       | 3844.13 ± 266.71   | 5774.61 ± 408.73  | 3133.78 ± 293.02    |\n| BreakoutNoFrameskip-v4      | 405.73 ± 11.47         | 307.39 ± 118.27    | 251.67 ± 15.92    | 465.90 ± 14.30      |\n| EnduroNoFrameskip-v4        | 986.69 ± 25.28         | 745.19 ± 139.98    | 493.08 ± 69.14    | 1178.37 ± 90.34     |\n| PongNoFrameskip-v4          | 20.45 ± 0.81           | 20.69 ± 0.33       | 20.44 ± 0.17      | 20.62 ± 0.18        |\n| QbertNoFrameskip-v4         | 15228.25 ± 920.95      | 13167.47 ± 1066.11 | 11502.93 ± 487.54 | 17318.50 ± 385.80   |\n| SeaquestNoFrameskip-v4      | 1518.33 ± 400.35       | 1538.04 ± 389.55   | 2936.30 ± 941.92  | 1203.30 ± 364.07    |\n| SpaceInvadersNoFrameskip-v4 | 1019.75 ± 49.08        | 911.16 ± 96.51     | 778.57 ± 46.76    | 1164.26 ± 176.96    |", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their careful and comprehensive review. We are glad that they found our results on acting greedily with respect to the random policy’s Q-function “extraordinary and quantitatively verified.” Below are responses to questions and comments.\n\n**Our PPO results vs. benchmarks:** We appreciate the reviewer’s thorough comparison of our PPO results in Appendix H.1 to previous benchmarks. We believe that the difference in returns is because *we limit agents to a single life* in the Atari games, as described in Appendix F.1. We do this in order to align the Atari games more precisely with the theoretical framework for episodic RL, where episodes always start in states drawn from the same distribution. In typical Atari training, episodes are truncated when a life is lost but then a new episode is started in the state following the lost life. This actually makes the starting state distribution policy-dependent, which is quite different from the theoretical RL setting. Note that this also introduces a difference between training, when Atari agents’ episodes are truncated on loss of life, versus testing, when the agents’ rewards are summed over all lives. To avoid these problems, we simply end episodes entirely after one life during both training and testing.\n\nWe believe that this accounts for the difference between our results and those from other RL libraries. RLlib’s PPO implementation has been benchmarked [here](https://docs.ray.io/en/latest/rllib/rllib-algorithms.html#ppo) in several Atari environments and performs quite similarly to SB3, so we do not think that the RLlib implementation is the reason for the difference in results. Most of these environments have 3-5 lives, which could explain why the reward is often 3-5x lower for our setting.\n\nWe also plan to rerun our experiments with the SB3 implementations of PPO and DQN to make sure that they are robust to the exact implementations of the RL algorithms. We will include these results in the final paper if accepted.\n\n**More information about the surprisingly common property:** One of the motivations for examining the Q-values of the random policy was an analysis of policy gradient algorithms. When initialized with the random policy, the policy gradient can be exactly expressed in terms of the Q-values of the random policy:\n\n$$\\\\nabla\\_\\\\theta J(\\\\theta) = \\\\mathbb{E}\\_{\\\\pi^\\\\text{rand}}\\\\left[ Q^{\\\\pi^\\\\text{rand}}(s, a) \\\\nabla\\_\\\\theta \\\\pi\\_\\\\theta(a \\\\mid s) \\\\right]$$\n\nThus, one might expect policy gradient algorithms to (at least initially) move towards a policy which chooses actions with the highest Q-values under the random policy. This motivated us to examine the performance of simply acting greedily with respect to the random policy’s Q-function.\n\nTo calculate $\\\\Pi(Q^{\\\\pi^\\\\text{rand}})$ for an environment, we first run value iteration on the tabular representation to precisely calculate the Q-function $Q^{\\\\pi^\\\\text{rand}}$ at every state-action pair. Then, we can easily compute the set of policies which are greedy according to that Q-function as policies which take one of the actions with the highest Q-value at each state. For instance, suppose at the first state there are three actions with Q-values of 1, 1, and ½. Then a policy which takes either of the first two actions is greedy with respect to the Q-function. Often, there are multiple actions with the highest Q-value, since in many environments multiple actions may have the same effect."}]

Author rebuttal:

Meta-review: The reviewers unanimously agree that this is a very interesting work that takes a refreshing perspective on how and why deep RL works, and combines strong empirical evidence with theoretical explanation.
Decision: Accept (oral)