Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies using bonus for guiding exploration in reinforcement learning with large action spaces. The paper focuses on RL algorithms using LinUCB-style exploration bonuses. LinUCB, developed originally for stochastic linear bandits, has been a theoretically successful algorithm for problems admitting a linear reward structure. However, using such bonuses entails computing a matrix inversion, which may not be tractable in high dimensional problems. 

The main contribution of the paper is to propose Anti-concentrated Confidence Bounds (ACB) with the aim of efficiently approximating the LinUCB bonus without matrix inversions. The main idea of ACB is that it maintains $M$ linear regressors trained to predict i.i.d. noise drawn from $\mathcal N(0,1)$. The algorithm then set the bonus proportional to the maximum deviation over the regressors from the mean. Two versions are considered: one for linear bandits and one for deep RL. For linear bandits, the authors prove a regret of $\tilde O(d\sqrt{T\log A})$ with high probability under mild assumptions (e.g., logarithmically in $T$ many regressors). The variant for deep RL, however, is examined through numerical experiments where the algorithm is shown to be competitive with state-of-the-art. 


main_review: The paper investigates an interesting problem, which is highly relevant for the ICLR community. The paper is very well-written and straightforward to follow. It also presents the algorithms and results clearly and precisely. Moreover, most relevant works I am aware of are properly cited. 

Although the main contribution of the paper is empirical, the variants of the ACB algorithm admit a solid and novel design. Another positive feature is that the sound empirical performance of ACB when compared to state-of-the-art. All these support ACB as a viable exploration bonus for deep reinforcement learning. 

Due to limited time, I was unable to check the proofs. Nonetheless, the results appear correct to me. 

Besides some minor, easily-fixable comments listed below, I have the following comment. The reported regret bounds for the ACB variant for linear bandits all match the minimax regret for linear bandits, up to logarithmic factors, assuming that the number of actions grows polynomially with $d$. In my opinion, it would be informative if the paper compares the reported bounds with the best available bound considering $\log(T)$ factors. My quick check reveals that ACB’s regret is worse than the best available regret bound by a multiplicative factor of $O(\log^{3/2}(T))$. Please comment on whether this is correct and whether this is improvable. 

Minor: 

- As far as I understood, all norms used in the paper are Euclidean norms. If so, stating this explicitly could be helpful. 

- p. 5: that that => than that

- p. 7: one reference is inappropriately inserted (see “?”)

- Both $L_2$ and $\ell_2$ are used to indicate the same notion.  

- p. 4: In the formula $r_t(a)\le \hat r_t(a) + bonus_t(a)$, unless I am missing something, I think $r_t(a)$ in the left-hand side should be $\langle x_{t,a_t},\theta^*\rangle$. 

- p. 13: The value of $\gamma_E$ is missing. 

summary_of_the_review: This paper presents a novel exploration bonus, called ACB, that can be used to design viable exploration strategies for linear bandits and deep reinforcement learning. ACB admits a solid and novel design, and shows competitive performance with state-of-the-art. Finally, the paper is well-written and well-executed.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a new intrinsic reward method for continuous-action-space deep RL algorithms. The proposed algorithm is inspired by the bonus term of LinUCB. The proposed algorithm improves the efficiency of its reward bound’s computation by using a randomized variant of the original reward bonus. The authors theoretically justified the optimality of this ACB bonus term in the linear case, showing that this is a reasonable replacement of the LinUCB reward bonus. Finally, the authors add the ACB bound to deep RL algorithms. Although this algorithm comes with no theoretical guarantee, experiments show that the ACB intrinsic reward is competitive compared to adopted baselines.
main_review: Overall, the paper is well-motivated and clear in presentation. The logic flow of the paper is also good: after showing the efficiency problem of LinUCB, the authors provide a theoretically-grounded algorithm for linear bandits with much less computation overhead. Then this algorithm is applied to deep RL algorithms. Although the proposed ACB is not completely novel (as also mentioned in the related work section), the paper is well-motivated and the resultant algorithm is effective. Therefore, I vote for acceptance.

While I’m mostly happy with the paper, I have the following questions/suggestions:

To me, the reason why Alg. 2 works are the following: if we have seen a specific $g$ many times, then $y$s corresponding to this similar $g$s will be normally distributed, hence these are approximately zero-centered. And then while minimizing the loss function, $w$ is incentivized to be orthogonal to such $g$s, making the intrinsic reward small. Given this intuition, I could imagine different ways of setting $y$s could influence the performance significantly. Therefore, although the current experiments are sufficient, it would be nice for the authors to show how different ways of setting $y$ influence the performance.
summary_of_the_review: Overall, I tend to vote for acceptance. Although the proposed method shares some similarities with existing approaches, the theoretical part is well-motivated and clearly explained, and the empirical part demonstrates the effectiveness of the proposed algorithm.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a novel exploration method called anti-concentrated confidence bounds (ACB) that provably approximates the elliptical exploration bonus of LinUCB by using an ensemble of least-squares regressors. ACB computes elliptical confidence intervals for each action by taking a maximum over the predictions of the ensemble. While doing this, ACB bypasses costly covariance matrix inversion, which can be problematic, especially for high-dimensional problems. It is shown that ACB enjoys near-optimal performance in linear stochastic bandits when the cardinality of the action set is polynomial in the action feature dimension. However, the main contribution of this work comes from extending ACB principle for computing exploration bonuses in deep RL. Comparison of ACB with state-of-the-art deep RL exploration methods on Atari benchmarks demonstrates the competitiveness of the proposed approach.

main_review: Strengths: 

This paper provides a rigorous analysis of how generalized exploration bonuses for deep RL can be derived from fundamental exploration bonuses from linear stochastic bandits. Tackling the scalability issue via bypassing covariance matrix inversion by taking a maximum over an ensemble of regressors is a novel contribution. 

The proposed algorithms come with different update frequencies ranging from always re-randomizing to incremental updates. Regret bounds that are analogous to that of LinUCB are derived for different update frequencies for the case of linear stochastic bandits. Having a theoretical foundation based on linear stochastic bandits supports the practical contribution on the deep RL side.  

The main contribution of this paper comes from applying ACB principle for exploration in deep RL where high-dimensionality of the policy network prohibits efficient covariance matrix inversion.   

Weaknesses: 

The main selling point of this paper is a computationally efficient procedure for exploration bonus calculation that does not require costly covariance matrix inversion. A major concern related to this is that the computational efficiency of the proposed approach is not analyzed rigorously. The advantage of the proposed method compared to performing rank-1 updates in the implementation of LinUCB is not articulated well. The paper does not provide any empirical evidence that supports such a performance gain. 

It is also not clear how the current work improves upon exploration schemes proposed in Kveton et al. (2019a) and Ishfaq et al. (2021). While it is claimed that they resemble the always re-randomizing variant of ACB, it is not clear why can’t they be turned into something in line with lazily-rerandomizing and never-rerandomizing variants with simple algorithmic tweaks as done in this paper. It will also be good to provide an empirical comparison of Algorithm 1 with these algorithms for the multi-armed bandit setting.   

Algorithm 1 requires recursive least-squares optimization oracles. The per-iteration computational cost of implementing should also be discussed in the main paper. 

Simulations do not show a clear advantage for ACB over RND in terms of visiting new states and maximizing extrinsic rewards. It is not clear why one would not resort to other state-of-the-art methods for exploration in deep RL. In addition, simulations do not demonstrate the computational savings induced by ACB. The paper claims that its main contribution is a novel exploration bonus for deep RL. But it does not provide enough evidence about why one would prefer ACB over other deep RL exploration bonuses. 

Kveton et al. 2019 – double citation. 

Synthetic bandit experiments should involve comparisons with other benchmarks as well as LinUCB.  

summary_of_the_review: Overall, this paper proposes an interesting way to scale exploration bonuses from linear stochastic bandits for deep RL. However, the paper does not provide convincing evidence that supports the advantages of using ACB both in bandit and deep RL setups. In particular, computational and performance improvements pertaining ACB are not explained well.
review_title: null

Meta-review: This paper tackles the problem of exploration in Deep RL in settings with a large action space. To this end, the authors introduce an intrinsic reward inspired by the exploration bonus of LinUCB. This novel exploration method called anti-concentrated confidence bounds (ACB) provably approximates the elliptical exploration bonus of LinUCB by using an ensemble of least-squares regressors. This allows ACB to bypass costly covariance matrix inversion, which can be problematic for high-dimensional problems (hence allowing it to be used in large state spaces). Empirical experiments show that ACB enjoys near-optimal performance in linear stochastic bandits. However, experiments on Atari benchmark fail to show any practical advantage of ACB over current methods, neither computation nor performance-wise. That being said, the proposed ACB approach is theoretically transparent, which contributes to advancing our theoretical understanding of usable intrinsic rewards in deep RL and can inform theoretically motivated directions for improvement and further research, while being on par with SOTA. I believe that this makes the contribution of this work strong enough for acceptance.
Decision: Accept (Poster)