The Effective Horizon Explains Deep RL Performance in Stochastic Environments

We thank the reviewer for their insightful comments. We appreciate they found our results to be a significant contribution and our paper to be "well-written and easy-to-follow." The weaknesses and questions in the review are addressed below:

• Comparing the theoretical and empirical performance of SQIRL: we agree that it would be ideal to compare our theoretical bounds on SQIRL's sample complexity to its empirical performance. However, this is actually quite difficult because our practical implementation of SQIRL uses neural networks and neural network generalization is not well understood. In the bound on SQIRL's sample complexity in equation (1), we can easily calculate the effective horizon $\bar{H}_k$, but the $D$ term depends on how well the regression oracle—neural networks in our practical implementation—can generalize given a certain number of training samples. Since there are few or no bounds on neural network generalization error that reflect their empirical performance, we cannot provide a tight bound on SQIRL's sample complexity using neural networks. However, an advantage of our work is that any advances in understanding neural network generalization can immediately result in better bounds on SQIRL's sample complexity. Furthermore, we believe that the fact that SQIRL performs well empirically suggests our assumptions are met in practice and that our theory is a valuable tool for analyzing model-free RL with random exploration.

• Computing the effective horizon is not much easier than solving the environment: this is a valid point, and we agree that it is intractable to compute the effective horizon for many problems. However, we still think that it can provide useful insights to theorists and practitioners. There may be ways of bounding the effective horizon using simpler quantities. For instance, Theorem B.4 of Laidlaw et al. (2023) shows that for any deterministic goal-based environment, the effective horizon can be bounded based on the probability of reaching the goal under the random policy from various states; their analysis translates easily to the stochastic setting. It is often easy to reason about the probability of reaching a goal, making the effective horizon a useful tool for analysis in goal-based environments. Besides precise bounds like this theorem, the effective horizon also has an intuitive interpretation—when the Q-values of optimal actions under the random policy are easier to distinguish from those of suboptimal actions (i.e., the $k$-gap is larger), then it will be easier to learn an optimal policy. This type of intuitive insight can help practitioners design better environments and reward functions such that RL will easily succeed.

• How does the performance of SQIRL change based on $k$? In the table below, we show how many environments can be solved by SQIRL as we allow just $k = 1$, $k \leq 2$, or $k \leq 3$. We find that even with $k = 1$, SQIRL can solve many of the sticky-action BRIDGE environments.

  	Number of environments solved
  $k = 1$	48
  $k \leq 2$	64
  $k \leq 3$	68

  We also found that the ideal value of $k$ for SQIRL varied depending on the environment (see the table below), and was not always the same as the minimum value of $k$ for which the MDP is approximately $k$-QVI-solvable (which for most environments was $k = 1$—see Figure 2). The reason for this is that while increasing $k$ increases the first term in the definition of the stochastic effective horizon (Definition 3.3), it might decrease the second term by making the $k$-gap larger, thus making the stochastic effective horizon $\bar{H}_k$ smaller as $k$ increases.

  Optimal value of $k$ for SQIRL	Number of environments
  1	19
  2	22
  3	27

  We will include these tables and analysis in the final paper if accepted.

• Is the small effective horizon just a product of sticky actions? We believe that the low effective horizon in our environments is more of an intrinsic property that does not just result from using sticky actions, since Laidlaw et al. (2023) also found that the (deterministic) effective horizon was low in the BRIDGE environments even without sticky actions. Furthermore, sticky actions are a standard method for making environments stochastic and widely used as a way of evaluating RL algorithms [1]. Thus, the fact that the stochastic effective horizon is low in these environments suggests that it underlies the success of many deep RL algorithms in this common evaluation paradigm of sticky actions.

• Is there a typo in the legend of Figure 2? Yes, this is a typo, and we have fixed it in an updated revision of the paper.

[1] Machado et al. Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents. Journal of Artificial Intelligence Research, 2018.

We thank the reviewer for their detailed comments. We appreciate that they found our submission addresses an important problem and that it is "overall well-written and easy to understand." Below, we have responded to the weaknesses raised by the reviewer:

• Novelty: while our paper builds on Laidlaw et al. (2023), we argue that it is a significant contribution in its own right. Since the GORP algorithm introduced in the prior paper relies heavily on the environment being deterministic, it was not clear to us at first how to extend it to stochastic environments. While the novelty of our submission may seem "limited" in hindsight, we found that in discussions with other researchers and among ourselves, it was quite difficult to think of a stochastic analog of GORP. Furthermore, our theoretical analysis requires quite different tools than Laidlaw et al. They need to only analyze mean estimation-type problems for the deterministic case, which is quite simple. In contrast, we analyze the statistical generalization of complex function approximators across distributions of state-action pairs. Thus, we believe that our submission represents a significant advancement beyond prior work.

• Correctness of theoretical claims: we address the specific concerns of the reviewer regarding the theoretical claims of the submission below.

  • Sample complexity bound (Equation 1): the instance-dependent $1/\Delta_k^2$ term is contained within the $A^{\bar{H}_k}$ term of the sample complexity bound presented in Equation 1, since $\bar{H}_k = k+ \log_A ( 1 / \Delta_k^2 )$ according to Definition 3.3. Thus, since the sample complexity bound is always higher than $1/\Delta_k^2$, it does not contradict lower bounds for the bandit case.
  • Last step of proof of Lemma B.1: we do assume that the total rewards over an episode are bounded almost surely in $[0, 1]$, as we note in the second paragraph of Section 2 (page 3): "We assume that the total reward $\sum_{t=1}^T R_t(s_t, a_t)$ is bounded almost surely in $[0, 1]$; any bounded reward function can be normalized to satisfy this assumption."
  • Assumptions in Lemma B.1: we should have been more explicit about how $k$-QVI-solvability is used in the proof of Lemma B.1. It is used to show that $\pi^* \in \Pi(Q^k)$ is an optimal policy (by the definition of $k$-QVI-solvability), and thus that $J(\pi^*) = \max_\pi J(\pi)$. Thank you for pointing this out—we will make it explicit in the final version of the paper.

  Overall, we do believe that any of these concerns affect the formal correctness of the paper. If the reviewer still believes there are issues with any of our theoretical claims, we invite them to let us know in a follow-up comment.

• Weaknesses of the proposed algorithm: we agree with the reviewer's assessment that, while SQIRL has hyperparameters that must be carefully tuned for a particular environment, the algorithm is still useful for theoretically understanding when and why deep RL works in practice. As we wrote at the top of page 9, "we do not claim that SQIRL is as practical as PPO or DQN, since it requires much more hyperparameter tuning; instead, we mainly see SQIRL as a tool for understanding deep RL."

• Figure 2 colors: the reviewer is correct that we accidentally swapped the colors in Figure 2. We have corrected the problem in an updated submission.

We thank the reviewer for their insightful comments. We are glad they found that our paper “addresses the key limitation of prior work” and that our experiments are “extensive.” Below we have responded to the weaknesses raised in their review.

• Novelty compared to previous work: we acknowledge that tree search and FQI have been extensively used and analyzed in prior works, including those the reviewer cited. However, the papers mentioned in the review use a model for planning. Unlike these works, our focus is on learning an optimal policy within a model-free setting, where no access to a pre-existing model is available. This introduces a higher level of complexity as we are constrained to sample episodes from a fixed initial state distribution and cannot reset to arbitrary states for further planning. This means that it is not possible to apply standard tree search procedures—instead, one of our key contributions is constructing an RL algorithm, SQIRL, which behaves in some ways like tree search but is actually completely model-free. We will clarify this point and compare to the work cited by the reviewer in the final version of the paper if accepted.

• Claim of in-distribution generalization: the reviewer notes that in many Q-learning-like RL algorithms, the Q values of states which are rarely seen or actions which are rarely taken or may be significantly mis-estimated. However, our theoretical analysis shows that this is provably not the case for SQIRL. Since SQIRL explores by taking actions uniformly at random before running FQI, no actions are sampled more often than others in expectation, meaning that no actions are any more "out-of-distribution" than others. According to Lemma B.2, this means that the mean-squared error of the Q-function can blow up by a factor of $A$ (the number of actions) at each step of FQI, but no more. We then combine this error bound with Markov's inequality in Lemma B.3 to show that the probability of any action's Q-value being off by too much is bounded. This allows us to give the bounds on sample complexity of SQIRL in Theorem 3.6.

• Whole set of stochastic environments is not explained by SQIRL: we will revise our language in the introduction to indicate that we do not provide a complete explanation for deep RL performance in all possible environments. Instead, our analysis is aimed at generally understanding when and why deep RL works across a broad range of environments. We note that in Laidlaw et al. (2023), GORP also does not solve all the deterministic BRIDGE environments—is there another way in which you are claiming that GORP "explains" all the environments?

• Other types of stochasticity: we agree that there are other ways of adding stochasticity to environments besides sticky actions. We primarily focus on sticky actions based on the evidence provided by Machado et al. [1], who explore a number of ways of inducing stochasticity in Atari games. They conclude that sticky actions are the best way to introduce stochastic transitions:

  Sticky actions [leverages] some of the main benefits of other [stochasticity] approaches without most of their drawbacks. It is free from researcher bias, it does not interfere with agent action selection, and it discourages agents from relying on memorization. The new environment is stochastic for the whole episode, generated results are reproducible, and our approach interacts naturally with frame skipping and discounting.

  Thus, following their conclusions, we decided to focus on creating stochastic environments using sticky actions.

[1] Machado et al. Revisiting the arcade learning environment: Evaluation protocols and open problems for general agents. Journal of Artificial Intelligence Research, 2018.

We thank the reviewer for their comments. We have addressed the weaknesses and questions they mentioned below:

• ”The theory is simple and straightforward… [since] exploration is not needed.” Just to clarify, in any RL problem exploration is needed. However, in the setting we consider, random exploration seems to be enough, i.e., strategic exploration is not necessary. One of our central points in the paper is that many common RL benchmarks can be solved with random exploration, as shown by the success of deep RL algorithms that explore randomly. Our contribution is to explain—both theoretically and empirically—how random exploration works well in practice with complex function approximators like neural networks, since existing theory suggests that random exploration can result in exponentially bad sample complexity.

  Furthermore, we argue that our theory is not simple or straightforward, since very few previous works in the RL theory literature have been able to explain why random exploration is sample efficient in practice despite being exponentially inefficient in the worst case. The few papers that have focused on random exploration either rely on assumptions that do not seem to hold in realistic environments or they do not consider generalization with complex function approximators. In contrast, our theory both rests on assumptions that are verified in common RL benchmarks and is very general, as it can be applied to even quite complex function approximators like neural networks.

• ”Figure 2 shows that PPO fails in most tasks with k=1.” This was actually a typo on our part; the labels should have been reversed. We have updated the figure accordingly and it now correctly shows that PPO succeeds in most of the MDPs with k = 1.

• ”Apart from the tasks in Bridge, can you verify Def 3.1 for other tasks, including go and robotic?” In this paper, our focus is on model-free RL in environments with discrete action spaces. Model-free RL does not work very well for Chess or Go—the best RL algorithms for solving these games have consistently been model-based, like AlphaZero and MuZero. Furthermore, they are two-player games, while we consider single-agent environments. Most robotics tasks are also outside of the scope of our analysis since they have continuous action spaces. While we hope to extend our work from discrete actions to continuous action spaces in the future, our current submission already covers a large number of common RL benchmarks, like Atari games, Procgen, and MiniGrid. Thus, we believe that verifying Definition 3.1 ($k$-QVI-solvability) in these environments is already enough to show that this property holds in a large proportion of the types of environments where model-free RL works in practice.