Compound Returns Reduce Variance in Reinforcement Learning

Thank you for the review. We respond to each of your concerns below:

While a formal study on the variance reduction property is valuable, the theoretical contributions of this paper seem limited. The assumptions help abstract a lot of the difficulties and with the uniform variance/correlation assumptions, the derivation in this paper seems to be straightforward/follow standard arguments. As such, the technical depth is limited.

Our work is the first to make progress on this question in the last 12 years. Please see “Strength of Theoretical Contributions” in our general response for more details about the novelty of our theory.

One might expect a more comprehensive experimental evaluations, ablation studies and comparisons. The current manuscript unfortunately only evaluates on the Atari Freeway environment.

Thank you for this suggestion. We have added results for three more MinAtar games to the paper; please see “Additional Experiments” in our general response.

Thank you for the review. We would like to note that our theoretical analysis extends far beyond just TD($\lambda$) and $\lambda$-returns. Our analysis encompasses all arbitrary weighted averages of $n$-step returns, which is a vast family of return estimators used by all value-based RL methods. TD($\lambda$) and $\lambda$-returns are just one interesting example because of their widespread use in RL.

We also want to emphasize that, until now, no one has shown that TD($\lambda$) reduces variance compared to $n$-step TD. It was previously believed [1, ch. 12.1] that the main benefit of $\lambda$-returns was their convenient implementation using eligibility traces, and were otherwise equivalent to $n$-step returns.

We respond to each of your concerns below:

I think that most of the results are slightly incremental and not clearly novel. Assuming that all temporal difference errors have the same correlation is a strong assumption in my opinion.

Our work is the first to make progress on this question in the last 12 years. Please see “Strength of Theoretical Contributions” in our general response for more details about the novelty of our theory.

In general in RL it is not clear if minimizing the variance of the return estimators is helpful to improve the sample complexity of an algorithm. Check for example this paper investigating the role of the minimum variance baseline in policy gradient as in [1].

This is an excellent point. It is true that reducing the return variance is not guaranteed to improve the sample efficiency of policy gradient methods. The paper that you cited shows that the variance of the baseline can sometimes be beneficial because of its interaction with the exploration policy (what the authors call committal and non-committal baselines). Our value-based setting is fundamentally different because it does not rely on a critic to determine which actions should be reinforced. Instead, the policy is directly determined as a function of the value function (e.g., $\epsilon$-greedy) and so the main bottleneck for learning is how quickly the returns can be estimated accurately.

Furthermore, it is widely accepted that variance reduction is beneficial for learning value functions. This is why TD-based returns (e.g., n-step returns [2] or lambda-returns [3]) are almost always used in deep RL instead of Monte Carlo returns, as the latter have extremely high variance. To isolate the effects of return estimation itself, we chose to focus on DQN, a well-studied deep RL method that only learns a value function. The main benefit of our method, PiLaR, is to apply similar variance reduction in off-policy experience-replay settings where computing the full $\lambda$-return is infeasible.

The experiments in Deep RL are limited to only one environment. I think that a larger empirical evaluation is necessary.

Thank you for this suggestion. We have added results for more MinAtar games to the paper; please see “Additional Experiments” in our general response.

Is it possible to use the results in this paper to show more informative results regarding the performance of TD($\lambda$). For example that having a lower variance in the returns improves the sample complexity needed for either policy evaluation or for learning an $\epsilon$-optimal policy?

This is a great question. Please see “Why Variance Reduction Leads to Faster Learning” in our general response for a detailed discussion of how the contraction rate corresponds to expected policy improvement in Q-Learning methods. We have also added this discussion to our paper’s appendix.

References

[1] Reinforcement Learning: An Introduction. Sutton and Barto, 2018.

[2] Rainbow: Combining Improvements in Deep Reinforcement Learning. Matteo Hessel et al., AAAI 2018.

[3] High-Dimensional Continuous Control Using Generalized Advantage Estimation. John Schulman et al., ICLR 2016.

Thank you for the review and for pointing out the two typos in our equations. We have fixed them in the paper. We also respond to each of your concerns below:

It is unclear whether the uniform covariance assumption is reasonable in real-world problems, since the hardness to approximate the covariance between different steps should not be an evidence to support the validity of this assumption. Intuitively, the variance of TD errors at further steps should be larger since the entropy of state should increase along the diffusion over the MDP. Therefore, it is appreciated to verify this assumption empirically on synthetic examples.

Our work is the first to make progress on this question in the last 12 years. Please see “Strength of Theoretical Contributions” in our general response for a detailed discussion.

We think it is a great idea to measure how well our assumptions hold in practice. We added two experiments to the paper (Appendix B) that plots the actual variance of the n-step returns compared to the lower and upper bounds predicted by our model.

The contraction rate measures the contraction level of the policy evaluation process. It is not clear the effect of this rate in the policy optimization process, nor is it discussed in the paper. Therefore, it is still not clear whether the faster learning with DQN is a consequence of smaller variance of PiLaR or smaller contraction rate in the policy optimization process as $n2$ is generally larger than $n$.

Thank you for bringing up this point. Please see “Why Variance Reduction Leads to Faster Learning” in our general response for a detailed discussion of how the contraction rate corresponds to expected policy improvement in Q-Learning methods.

Furthermore, it can be seen from the MinAtar experiments (Figures 5 and 6) that a larger value of $n$ actually hurts performance due to the increased variance, so it is not true that a larger $n_2$ value for PiLaR is responsible for the faster learning. Since each pair of returns are chosen to have the same contraction rate, the only remaining explanation is the reduced variance, which is supported both by our theory and random walk experiments in Figure 1.

The theoretical results of the paper are mostly conceptual in the sense that it proves some variance reduction results but do not discuss how this lower variance accelerates the learning of optimal policies. The "equally fast" claim for two estimators with the same contraction rate is also conceptual without solid evidence. Does it correspond to smaller sample complexity in theory?

This is a great question. We would first like to point out that our random walk experiment in Figure 1 does provide solid evidence that two returns with the same contraction rate learn equally fast in expectation (small step size) but the one with lower variance learns faster with limited samples (large step size). Again, please see “Why Variance Reduction Leads to Faster Learning” in our general response for answers to your questions regarding contraction rate and sample complexity.

The insight of this paper is also limited in both practice and theory, since the baseline is the n-step TD learning and DQN, which is away from current SOTA algorithms used in RL. Is it possible to compare the PiLaR (or more refined compound error with even smaller variances) with some SOTA RL algorithms such PPO or CQL?

The principal contribution of our paper is the theory. The purpose of our experiments is to test how well our theory is reflected in practice when the assumptions required for the math do not always hold, as well as to demonstrate the feasibility of using variance-reducing compound returns in deep RL. We further discuss this in “Additional Experiments” in our general response, where we provide results for more MinAtar games.

Studying actor-critic methods such as PPO or CQL would add a confounding factor since they simultaneously train a stochastic policy (as you correctly noted above). To isolate the effects of return estimation itself, we chose to focus on DQN, a well-studied deep RL method that only learns a value function.

We also note that PPO is an on-policy method and commonly uses the $\lambda$-return with GAE [1] rather than the high-variance Monte Carlo return, which provides further evidence that variance reduction is beneficial in practice. Thus, the main benefit of PiLaR is to apply similar variance reduction in off-policy experience-replay settings where computing the full $\lambda$-return is infeasible.

References

[1] High-dimensional Continuous Control Using Generalized Advantage Estimation. John Schulman et al., ICLR 2016.

Why Variance Reduction Leads to Faster Learning

Some reviewers expressed doubt that reducing the variance of return estimates would lead to faster learning. To see why this is the case, value-based RL methods like DQN (which is based on Q-Learning) can be viewed as stochastic approximations to action-value iteration. For example, consider the proof of Proposition 4.5 in Neuro-Dynamic Programming [2, pp. 166-167]. All of the control methods in our work are equivalent to sample-based approximations of some operator $H \colon \mathbb{R}^m \to \mathbb{R}^m$ that transforms an action-value function $q \in \mathbb{R}^m$, where $m = {|\mathcal{S} \times \mathcal{A}|}$. By definition, the optimal action-value function $q_*$ is the unique fixed point of $H$. The greedy policy with respect to $q_*$ is guaranteed to be optimal, so converging to this fixed point faster means that the behavior policy improves faster on average, too. The methods considered in our paper are therefore equivalent to asynchronous versions of the following stochastic process:

$q_{t+1} \gets (1-\alpha_t) q_t + \alpha_t (H q_t + \omega_t)$,

where $\omega_t \in \mathbb{R}^m$ is zero-mean, finite-variance noise. If we remove the noise, we can set $\alpha_t = 1$ and converge to $q_*$ exponentially fast. Intuitively, each iterate $q_t$ remains in a shrinking hypercube whose side length decays by the contraction rate. With noise, the iterates no longer monotonically approach the fixed point, but annealing the step size $\alpha_t$ according to the Robbins-Monro conditions [3] does guarantee that they will eventually enter and then remain within each successively shrinking hypercube with probability 1. The number of iterations required to enter and stay inside a given hypercube depends on the magnitude of the conditional variance of $\omega_t$, which is the conditional variance of the return estimator in our case. It follows that if one return estimator has the same contraction rate but lower variance compared to another, it will require fewer samples on average to achieve the same proximity to $q_*$. This explains why $\lambda$-returns learn faster than $n$-step returns in our random walk experiment (Figure 1) when their contraction rates are equalized, since Theorem 1 guarantees the $\lambda$-returns have lower variance.

Additional Experiments

All of the reviewers recommended adding more experiments to the paper. We would like to remind the reviewers that our paper is theoretical in nature. Our theory is the main contribution and we believe it stands by itself given the depth of our analysis. We therefore have left a larger empirical study for future work. Our deep RL results are meant to be a proof of concept of the feasibility of the method and its applicability to nonlinear function approximation, where theoretical guarantees do not exist.

Nevertheless, we have added results for three additional MinAtar games (Breakout, Seaquest, and Space Invaders) that further demonstrate the utility of PiLaRs compared to $n$-step returns. They further support the claims we make in the paper.

References

[1] TDγ: Re-evaluating Complex Backups in Temporal Difference Learning. Konidaris et al., NeurIPS 2011.

[2] Neuro-Dynamic Programming. Bertsekas and Tsitsiklis, 1996.

[3] A Stochastic Approximation Method. Robbins and Monro, 1951.