Anti-Concentrated Confidence Bonuses For Scalable Exploration
Authors: Jordan T. Ash
Cyril Zhang
Surbhi Goel
Akshay Krishnamurthy
Sham M. Kakade
Venue: ICLR 2022 Poster (2022)
Keywords: deep reinforcement learning
reinforcement learning
bandits
exploration

Abstract: Intrinsic rewards play a central role in handling the exploration-exploitation tradeoff when designing sequential decision-making algorithms, in both foundational theory and state-of-the-art deep reinforcement learning. The LinUCB algorithm, a centerpiece of the stochastic linear bandits literature, prescribes an elliptical bonus which addresses the challenge of leveraging shared information in large action spaces. This bonus scheme cannot be directly transferred to high-dimensional exploration problems, however, due to the computational cost of maintaining the inverse covariance matrix of action features. We introduce anti-concentrated confidence bounds for efficiently approximating the elliptical bonus, using an ensemble of regressors trained to predict random noise from policy network-derived features. Using this approximation, we obtain stochastic linear bandit algorithms which obtain $\tilde O(d \sqrt{T})$ regret bounds for $\mathsf{poly}(d)$ fixed actions. We develop a practical variant that is competitive with contemporary intrinsic reward heuristics on Atari benchmarks.

Published as a conference paper at ICLR 2022
ANTI-CONCENTRATED CONFIDENCE BONUSES FOR SCALABLE EXPLORATION
Jordan T. Ash Microsoft Research NYC
Cyril Zhang Microsoft Research NYC
Surbhi Goel
Microsoft Research NYC
Akshay Krishnamurthy Microsoft Research NYC
Sham Kakade
Microsoft Research NYC
Harvard University
ABSTRACT
Intrinsic rewards play a central role in handling the exploration-explotttion trade-off when designing sequential decision-making algorithms, in both foundational theory and state-of-the algorithm, centerpiece of the stochastic linear bandits literature, prescribes an elliptical bonus which addresses the challenge of leveraging shared information in large action spaces. This bonus scheme cannot be directly transferred high-dimensional exploration problems, however, due to the computational cost of maintaining the inverse covariance matrix of action features. We introduce anti-concentrated confidence bounds for efficiently approximating the elliptical bonus, using an ensemble of regressors trained to predict random noise from policy network-deriver features. Using this approximation, we obtain stochastic linear bandit algorithms which obtain (dvTT) regret bounds for poly(c) fixed actions. We develop practical variant for deep reinforcement learning that is competitive with contemporary intrinsic reward heuristics on Atari benchmarks.
deep reinforcement learning. The LinUCB
INTRODUCTION
Optimism in the face of uncertainty (OFU) is a ubiquitous algorithmic principle for online decision- making bandit and reinforcement learning problems. Broadly, optimistic decision-making al- gorithms augment their reward models with bonus (or intrinsic reward) proportional to their uncertainty about an action's ' outcome, ideally balancing exploration and exploitation. A vast litera- ture is dedicated to developing and analyzing the theoretical guarantees of these algorithms (Lattimore & Szepesvári 2020). In fundamental settings such as stochastic multi-armed and linear bandits, optimistic algorithms are known to enjoy minimax-opiie optimal regret bounds.
In modern deep reinforcement learning, many approaches to exploration have been developed with the same principle of optimism, with most empirical successes coming from uncertainty-basee intrinsic reward modules (Burda et al. 20188) Pathak et al., 2017] Osband et al. 2016). Such bonuses can be very useful, with prior work demonstrating impressive results on wide array of challenging exploration problems. Several of these methods draw inspiration from theoretical work on multi- armed bandits, using ideas like count-based exploration bonuses. However, related body of work on linear bandits provides tools for extending exploration bonuses to large but structured action spaces, a paradigm which may be appropriate for deep reinforcement learning.
The Linear UCB (LinUCB) algorithm (Auer 2002 Dani et al. 2008 Li ct al. 2010 Abbasi- Yadkori
al., (011) is attractive in this setting because enjoys minimax -optimal statistical guarantees. To obtain these, LinUCB leverages a so-called elliptical bonus, the computation of which requires maintaining an inverse covariance matrix over action features. The principal challenge in generalizing the elliptical potential used in bandits to the deep setting lies in computing and storing this object. Due to the moving internal representation of the policy network, and the number of parameters used to compose it, naive implementation of the LinUCB algorithm would require remembering all of the agent's 's experience and constantly recomputing and inverting this matrix, which is likely extremely large. Clearly, such an approach is too computationally intensive be useful. As discuss in the

---

Published as a conference paper at ICLR 2022
B10
D00 5
081
80355
1m-3
1e-3
-mmmm y VMM
Bonus
Myn m
Relative Timestep
Relative Timestep
Figure 1: visualization of the ACB bonus for Atari games Breakout and Q*bert. Large bonuses often correspond to the visitation of states the periphery of the agent's ' current experience, for example upon breaking a novel combination of blocks in Breakout or immediately before Q*bert arrives unlit platform. When the agent dies, and the game is reset familiar state, intrinsic reward drops precipitously.
next section, several works have used neural features for LinUCB-styy bonuses, but all require inversion of this sort, limiting their ability to scale to high dimensions.
Towards bridging foundational algorithms with empirical frontiers, develop scalable strategy for computing LinUCB's s elliptical bonus, enabling us to investigate effectiveness as an intrinsic reward in deep reinforcement learning. We use an ensemble of least-squares regressors approximate these bonuses without explicitly maintaining the covariance matrix or its inverse. Our algorithm is both theoretically principled and computationally tractable, and we demonstrate that its empirical performance on Atari games is often competitive with popular baselines.
1.1 OUR CONTRIBUTIONS
We propose the of anti-concentrated confidence bounds (ACB) efficiently approximate the LinUCB bonus. ACB estimates per-action elliptical confidence intervals by regressing random targets on policy features. It anti-concentrates these bonuses by taking maximum over the predictions from an ensemble of these regressors.
First, we introduce ACB in the basic stochastic linear bandit setting. We show that these bonuses provably approximate LinUCB's 's elliptical potential; thus, optimistic exploration with ACB directly inherits standard analysis techniques for LinUCB. We derive near-optimal high- gigh-probability regret bounds for ACB, when the size of the action space is polynomial in the action feature dimension. We derive sufficient ensemble sizes for special cases multi-armed bandits and fixed actions, as well as the general case of changing actions. These follow from lower tail bounds for the maximum of inde- pendent Gaussians; we conjecture that they are improvable using more sophisticated analytical tools.
The main contribution of this work is empirical: find that ACB provides viable exploration bonus for deep reinforcement learning. After defining suitable nonlinear analogue using action features from the policy network, we demonstrate that the intrinsic rewards produced by ACB competitive with those from state-of-ther oftth-----hh-rr art algorithms in deep RL on a variety Atari benchmarks (Figure D.. To the best of our knowledge, our work is the first scalably study bonuses from the linear bandits literature in these deep reinforcement learning settings.
1.2 RELATED WORK
Linear bandits. Stochastic linear bandits were first introduced by Abe & Long 1999). Optimistic
algorithms are fundamental in this setting (Auer] 2002 Dani et al. 2008) Li et al. 2010 Rusmevichien tong & Tsitsiklis. 2010: Abbasi- Yadkori et al. 2011) and provide min minimax-optimal regret bounds.
2

---

Published as a conference paper at ICLR 2022
Several works are concerned with designing more scalable optimism-basee based algorithms, with a focus on empirical bandit settings (as opposed to deep RL).Jun et al. (2017) consider streaming confidence bound estimates (obtaining per-iteration update costs independent of t) in the generalized linear bandits model, but still incur the cost of maintaining the inverse covariance matrix via online Newton step updates. Ding et al. (202T) give strong regret guarantees for spoch-batched SGD with Thompson sampling, under more stringent assumptions (i.i.d. action features, and a "diversity" condition to induce strong convexity), Korda et al. (2013) demonstrate that variance-reduced algorithms succeed in practice for estimating the LinUCB bonus.
Most closely related to our work, Kveton et al. (2019); ; Ishfaq et al. (202I) study perturbed regressions for exploration, obtaining similar regret bounds to ours (including the suboptimal vlog A factor in the regret bounds). The LinPHE algorithm in (Kveton al. 2019) uses a single random regressor's constant-pree ptstant-probbbblity anti-concentration to approximate the elliptical bonus. In work concurrent to ours, the main algorithm proposed by [Ishfaq et al. (202T) also takes a maximum over random regressors, and plugs their analysis into downstream end-to-end results for linear MDPs. The algorithms presented in these works resemble the "always-errandomizingg" variant of ACB (Algorithm (T], which is still not suitable for large-scale deep RL. Our work introduces the "lazily-rerandominee and geover-rerandomizing variants in an effort to close this gap, and presents corresponding open theoretical problems.
Unlike the aforementioned works, we consider our primary contribution as empirical, with the deep learning variant of ACB (Algorithm [ offering performance comparable commonly used deep RL bonuses on wide array of Atari benchmarks without sacrificing theoretical transparency. The resulting algorithmic choices deviate somewhat from the bandit version (as well as LinPHE/LSVI- PHE), towards making ACB a viable drop-in replacement for typical bonuses used in deep RL.
The use of ensembles in this work bears a resemblance Monte Carlo techniques for posterior sampling [Thompson] 1933; Agrawal & Goyal (013). This is starting point for many empirically- motivated exploration algorithms, including for deep RL (see below), but theory is limited. (Lu & Van Roy] 2017) analyze an sieemble-based approximation of Thompson sampling (without considering a max over the ensemble), and obtain a suboptimal regret bound scaling with Alog A.
Exploration in deep reinforcement learning. In deep reinforcement learning, most popular ap- proaches use predictability as a surrogate for familiarity. The Intrinsic Curiosity Module (ICM), for example, does this by training various neural machinery to predict proceeding states from current state-action pairs (Pathak et al. 2017). The L2 error of this prediction is used as a bonus signal for the agent. The approach can be viewed on a representation that is trained to encourage retaining only causal information transition dynam- ies (Oudeyer al., 2007). (tadie et al. (2015) instead use representation learned by autoencoder. A large-scale study of these "curiosity-basse approaches can be found in Burda et al. (2018a).
modification to Intelligent Adaptive Curiosity, but relying
Similar to these algorithms, Random Network Distillation (RND) relies on the inductive bias of random and fixed network, where the exploration bonus is computed as the prediction error between this random network and a separate model trained to mimic its outputs (Burda et al. 2018b).
In tabular settings, count-based bonuses are often used to encourage exploration (Strchl & Littman 2008). This general approach has been extended to the deep setting as well, where states might be high-dimensional and infrequently visited (Bellemare et al. 2016). Algorithms of this type usually rely on some notion of density estimation to group similar states (Ostrovski et al. 2017 Tang et al.. 2016 Martin et al. 2017).
Other work proposes more traditional uncertainty metrics to guide the exploration process. For exam- ple, Variational Intrinsic Control (Gregor et al.) 2016) uses variational notion of uncertainty while Exploration via Disagreement (Pathak et al. 2019) and Bootstrapped DQN (Osband et al.) 2016) model uncertainty over the predictive variance of ensemble. More broadly, various approximations
of Thompson sampling (Thompson 1933) have been used to encourage exploration in deep rein- forcement learning (Osband et al.) 2013] Guez et al., 2012 Zhang et al. 2020 Strens 2000 Henaff et al. (019). These methods have analogues in the related space of active learning. where ensemble and variational estimates of uncertainty are widely used (Gal et al. 2017 Beluch al., 2018).
Separate from these, there has been some work intended to more- cooredirretly deliver UCB-inspired bonuses reinforcement learning (Zhou al. 2020 Nabati et al. 2021 Zahaay & Mannor
3

---

Published as a conference paper at ICLR 2022
2019; Bai et al. 2021). These efforts have various drawbacks, however, with many requiring matrix inversions, limiting their ability to scale, or simply not being competitive with more conventional deep RL approaches. ACB removes the covariance matrix inversion requirement, and as we demonstrate in Section A.2 is competitive with RND and ICM on several Atari benchmarks.
2 PRELIMINARIES
In this section, we provide brief review and establish notation for the stochastic linear bandit setting and the LinUCB algorithm. For more comprehensive treatment, see al. (2019); Lattimore & Szepesvári (2020). At round = .., T, the learner is given action set Ar A with features
{2 E R" TaEA, chooses an action ae E A,, and receives reward ry ra(a)) := (0i,a, 8*) + Et. where is a martingale difference sequence. We use A to denote max, [As.- The performance of the learner is quantified by its regret,
T
R(T)- Σ (Ft.a;,0)) ('),0)0") of == arg max (1 0*) asA,
This setting encompasses two commonly-considere, special cases:
Fixed actions: the action sets Ar are the same for all t.
Multi-armed bandits: fixed actions, with A₃ [d] and Fz,a ea. Here, 0 is the vector of per-arm means.
An OFU-based algorithm plays at round
a₂ arg max (a) + (a)us .E.A.
where (a) is an estimate for the reward ra(a), and bonus, (a) is selected to be valid upper confi- dence bound for Fe()), such that [a)) S (a) bonusy with high probability. The LinUCB
algorithm uses fr (a) [zt.a: B.). where A arg mingeR Σ ((Ir,a, 6) rr((,))) |lellk
is the 2-regularized least-squares regressor for the reward, and sets bonus, (a) 8 xT Tt,a 1-1
where Σ, AI E It.e, at... In online learning context, this is known the elliptical potential (Cesa- Bisaa-Bincchii & Lugosi 2006; Carpentier et al. (020). We will quantify the theoretical performance of ACB by comparing it to LinUCB. Theorem [gives high-probability regret bound for LinUCB, which optimal up to logarithmic factors:
Theorem (LinUCB regret bound; Theorem 5.3, (Agarwal et al. 2019)). If 110011, [10-11.||=a,.01 s O(1), and each et O11)-uuggaussinn, then there are choices of X, 13 such that, with probability at least 1 - 8, the regret of the LinUCB algorithm satisfies
R(T) < Ō 2 (dvT).
The Ō(-) facto polynomial log(1/5) and T.
LinUCB can be implemented in O(d])Ar)) time per iteration, by maintaining Σn1 using rank-1 updates, and using this compute the least-squares estimator 0, 5: Et=1 Fr,a, rr (a,) well as bonus((a).
3 ANTI-CONCENTRATED CONFIDENCE BOUNDS FOR LINEAR BANDITS
We begin by presenting the ACB intrinsic reward for the stochastic linear bandit setting. It is well-known that the weights of a least-squares regressor trained to predict i.i.d. noise will capture information about about the precision matrix of the data. Our key idea is to amplify the deviation in the predictions an ensemble of such regressors by taking a maximum over their outputs, allowing construct upper confidence bounds for (a). ACB maintains M linear regressors trained to
4

---

Published as a conference paper at ICLR 2022
1e2
ensemble updates
102
ensemble updates
Figure 2: The cumulative regret for ACB (incremental sampling) with different ensemble sizes. We show a multi-armed bandit set- ting with 50 actions, comparing exact ordinary least squares (left) with SGD using Polyak averaging (right). Up to point, increasing ensemble size improves cumula- tive regret in both cases.
5-
M=2
M-64
M-122 128
4-
M=8
M-256
4-
Cumulstive
M-16
LinUCC
3-
3-
1.
Timesteps
le3
Timesteps
le3
Algorithm 1 ACB for linear bandits
Parameters: ensemble size M; 3, X
1: For all = 1,..., d, set warm-start features 2-141 = Vλe; and corresponding warm-stal targets (3)
8-1+1 NO, 1) for each E [M]]
T: 2: for t 1,...,, do
3: Observe action features fæt,a JaEA,
4: Update reward estimator:
0. = arg min (KTa,, rr+(a=)) + 2l1lk
5: Sample new random ensemble targets: (re-randomized)
y ~ NO, 1) for each j [M], E (-d d 1,,1,, I,..., -
(incremental)
Vi-1 (0, 1) for each j E [M]
(
6: Update bonus ensembles for each j [M],
w == arg min
Σ
(Ir,er, w) - y6-ي)
7 d+1
( for each a E A,
7: Compute per-arm bonuses bonus; (a) = B maxselan|
8: Choose action 0; := arg maxae.A, (Ti,a: Ae) (anus;(a)
9: Observe reward r: (az) = (Ir,as: 8¹) t
predict i.i.d. standard Gaussian noise, and sets the bonus be proportional the maximum deviation over this ensemble from its mean (which is 0). This procedure formally provided in Algorithm [
With the correct choice ensemble size, the concentration of the maximum independent Gaussians implies that each bonus, (a) is large enough to be valid upper confidence bound, yet small enough inherit the regret bound of LinUCB. ACB can be instantiated with freshly resampled history; in this case, the theoretical guarantees on the sufficient ensemble size are strongest. A more computationally efficient variant, which is the one we scale up to deep RL, samples random targets only once, enabling the use of streaming algorithms to estimate regression weight w:/ For these two variants, the following regret bounds result from straightforward modifications to the analysis of LinUCB (Abbasi-Yadkori ct al. 2011), which are deferred (along with more precise statements) to Appendix
Proposition 2 (ACB regret bound with re-randomized history). Then, Algorithm with re- randomized history and ensemble size M O(log(T (8)), obtains regret bound of O A), with probability at least
For A < (ppoyydd), regret bound matches that of LinUCB up logarithmic factors. We note that the expected regret guarantee of the LinPHE algorithm in Kveton et al. (2019) also has the same dependence
lAg( Our lower-tail analysis on the number of regressors required for the maximum deviation to be optimistic slightly sharper than that found in Ishfaq et al. (202T). by factor of log A; this is due requiring optimism only a" in Lemma
5

---

Published as a conference paper at ICLR 2022
Algorithm 2 ACB exploration for reinforcement learning
Parameters: ensemble M, lail-average constant 7,, policy network function parameterized by
update frequency r
1: Initialize auxiliary weights wi E Rd Vj e [
2: Initialize auxiliary policy network parameters 0aux t- 0
3: for t ..:
4: Observe state
5: Compute gradient features using auxiliary policy network 9r := g( f. 0aux)
6: Evaluate bonus b max,(((w) (((((((()))) T gx)²)
7:
Select action from policy network softmax distribution f( 0) if t is multiple of r then
8:
9:
Update policy network parameters with PPO on intrinsic rewards (b--r41...., b,} For all j E [M), draw random targets vt -0 1) and compute loss
10:
T = ((w, (1)
)T 9: Vi )² + \lllkk -wo w
11:
For j E [M], update wi1 using L,) Update auxillary network parameters 0aux al + (1 a)0aux
//using RMSProp
12:
Proposition (ACB regret bound with incremental updates). Algorithm ! with incrementally randomized history and an ensemble size of M (T)log(T/)),, obtains a regret bound of ((AVT) in the multi-armed bandit setting, with probability at least - 5.
We conjecture that the incrementalll-uupaaee version guarantees can be extended to linear bandits beyond MAB for reasonable ensemble sizes. In between the extremes of always vs. re- randomizing history. it is possible to analyze a "rarely re-randomizing variant of the algorithm. which obtains the smaller sufficient ensemble size of Proposition while only re-randomizing Od log T' times:
Theorem 4 (Lazy re-randomization). Algorithmp 3 with lazy re-randomized history, obtains regret bound of Ö(d (og((A//5)) in the case of linear bandits with fixed actions, while resampling the random targets yf only (oglog(AT) (5) log(T)) times.
We defer the modified algorithm and analysis Appendix C We note that the lazy version is computationally more efficient than the bonus approximation procedures in LinPHE (Kveton et al. 2019) and LSVI-PHE (Ishtaq al. 202T). and the expected regret guarantees obtained by LinPHE are not sufficient to successfully implement a lazy strategy.
Like other works proposing more scalable algorithms in the same setting (Korda et al. 2015 Ding et al. (021). with theoretically sound hyperparameter choices, we do not exhibit end-to-end theoretical improvements over the (dd2) (A.l) per-iteration cost of rank-1 updates for implementing LinUCB, Both lines 4 and in Algorithm depend on recursive least squares optimization oracles. For our main empirical results (as well as Figure 2 (right), we implement this oracle using Polyak-averaged SGD updates to each regressor, requiring O A(M) time per iteration to compute all the bonuses.
Synthetic bandit experiments. As a simple empirical validation of our method, we demonstrate the performance of Algorithm (with incremental sampling) in simulated multi-armed bandit setting with A = 50 actions. One arm has a mean reward 0.75 while the others' are set to 0.25; the noise E, for each arm sampled independently from (o0,, 0.13). As predicted by the theory, the ensemble size M must be chosen to be large enough for the bonuses to be sufficiently optimistic, small enough avoid too many upper-tail events. Further details are provided in Appendix A.I
EXTENDING ACB TO DEEP REINTORCEMENT LEARNING
Outlined Algorithm 2 the RL version of ACB deviates from the version mentioned earlier in several ways. First, like other work assigning exploratory bonuses deep reinforcement learning, we assign intrinsic rewards states, rather than state-action pairs (Pathak et al. 2017 Burda al. 2018b).

---

Published as a conference paper at ICLR 2022
167
Pitrall
lel
Seaquest
Broakout
Orbert
Visited
1.5
ACB (gradient features)
Extrimsic Reward
12.5
M- 128
500
ACB (outout features
Unique
400-
0.5
5.0
2.5
0.25
0.50
0.75
1.00
2
4
Episodes
Episodes
Timesteps
Timesteps
Figure 3: ACB with features using either penulti- mate layer or gradient features. Overall, gradient features seem to offer improved exploration, as measured by the number of unique states visited by an agent trained exclusively on these bonuses.
Figure 4: Larger ACB ensembles are generally more stable, resulting better exploration. An agent trained exclusively on large-ensemble ACB bonuses will tend observe more extrinsic re- ward than those with fewer regressors.
Breakout
Qrbert
Gravitar
Seaquest
Extrinsic Reward
20
300
100
15-
600
250
10-
400
200
300
150
200
200
100
100
Privale Eye
Pitfall
Beamrider
Space Invaders
Extrinsic Reward
500
-50
2000
400
ACB
000
RND
100
ICM
800
-500-
600
200
200
400
-1000
250
100
0.0
0.5
1.0 Timesteps
2.0
0.0
1.0
1.5
2.0
0.0
0.5
1.0
2.0
0.0
1.0
1.5
2.0
1e7
Timesteps
1e7
Timesteps
1e7
Timesteps
1e7
Figure 5: Extrinsic reward in Atari games as function of the number of times the agent interacts with the environment. Each plot corresponds to a different intrinsic reward scheme, and PPO being trained only to maximize this intrinsic reward.
Second, to help deal with non-stationarity, we compute gradient features with respect to a tail-averaged set of policy weights, rather than on the policy weights being used interact with the environment.
Because neural networks learn their own internal feature representation, extending ACB to the neural setting gives us some flexibility in the way we choose to represent data. One option to use the penultimate layer representation of the network, an approach that has seen success in the closely related active learning setting (Sener & Savarese 2018). In the deep active learning classification setting, more recent approach is to instead represent data using hallucinated gradient, embedding data as the gradient that would be induced by the sample the most likely label according to the model were the true label (Ash et al. 2020). Treating the policy network as classifier, we find that this representation tends to perform better than using just the penultimate layer. Specifically, this gradient is computed
g0.; (,0) de lo (1,50)) ÿ -= argmax [(x; 0),
where f is the policy network, 0 is its current parameters, (ū. 9) is the log loss of the pre- diction i/ given true label ÿ. and ÿ is the action to which the most probability mass is assigned. Using this representation, each seen state contributes Ix to the ACB covariance matrix, quantity that can viewed as a sort of rank-one approximation of the pointwise Fisher information, (xx 0) Eyy-j(=.0) Ve(((x, 0), (V(( (xx 0), v)) (Ash et al. 2021). This connection draws parallel between ACB with gradient features and well understodd, Fisher-based objectives in the active learning literature (Zhang& & Oles 2000 Gu et al. | Chaudhuri et al. 2015).. The ability to use such a gradient representation highlights the scalability of ACB ACB-policy networks used in RL are typically composed of over million parameters, and explicitly maintaining and inverting covariance
7

---

Published as a conference paper at ICLR 2022
1e7
Breakout
167
O*bert
1e7
Gravitar
167
Seaquest
2.0
States Visited
1.5
2.0
1.5
Unique
1.0
0.5
0.5
4
0.3
1.0
1.5
167
Private Eye
167
Pitfall
1e7
Beamrider
1o4
1e7
Space Invaders
States Visited
1.5
ACB
Unique
1.5
RND
1.0
1.0
0.5
0.5
0.25
0,50
0.75
1.00 1c4
0.25
0.50
0.75
1.00
2 Episodes
Episodes 1c3
Episodes
Episodes
1o4
164
Figure 6: The number of unique states visited (measured by hashing) in Atari games function of the number of game episodes. Each plot corresponds to a different intrinsic reward scheme, and PPO is being trained only maximize this intrinsic reward.
matrix of this size not feasible. ACB circumvents this need and handles high-dimensional features without issue. Figure 3 shows examples of environments for which the gradient representation produces better exploration than the penultimate-layy representation, according to the number of unique states encountered by the agent (using hash). In both cases, representations are computed on a averaage version of the policy with a = 10-6, which we also use in Section 5 below.
EXPERIMENTS
This section compares ACB with state-of-thh-ar approaches to exploration bonuses in deep rein- forcement learning Atari benchmarks. We inherit hyperparameters from RND, including the convolutional policy network architecture, which can be found in Appendix Section A.2 Policy optimization is done with PPO (Schulman al., 2017). In all experiments, we use 128 parallel agents and rollouts of 128 timesteps, making T in Algorithm 2 1282. Like other work on intrinsic bonuses, we consider the non-episodic setting, so the agent unaware of when it the episode is terminated. Consequently, even in games for which merely learning to survive is equivalent to learning to play well, random constant rewards will not elicit good performance. All experiments are run for five replicates, and plots show mean behavior and standard error.
In our investigation, we identified several tricks that seem help mitigate the domain shift in the gradient representation. Among these, mentioned above, we tail-average auxiliary policy network parameters, slowly moving them towards the deployment policy. This approach has been used to increase stability in both reinforcement learning and generative adversarial networks (Lilicrap et al.) 2015 Bell 1934.. In experiments shown here, a is fixed at 10-6, We additionally normalize intrinsic bonuses by running estimate of their standard deviation, found in both RND and ICM. Batch normalization is applied to gradient features before passing them to the auxiliary weight ensemble, and, like in the bandit setting, we compute bonuses using a average version of the ensemble rather than the ensemble itself. We use the RMSprop variant of SGD in optimizing auxiliary weights.
implementation detail that is also
We use an ensemble of 128 auxiliary weights and regularize aggressively towards their initialization with À= 10 As with the bandit setting, larger ensembles tend to produce bonuses that both are more stable and elicit more favorable behavior from the agent (Figure 4p. Experiments here consider eight different Atari games. Environments were chosen to include both games that are known be challenging in the way of exploration (Private Eye, Pitfall! and Gravitar (Burda et al.) (018b)) and games that are nom-remaining environments overlap with those from Table 1 of Mnih et al. (2015)
Intrinsic rewards only. In our first set of experiments, train agents exclusively on bonuses generated by ACB, rather than on any extrinsic reward signal. In Figure I we visualize some of these bonuses gameplay progresses in two Atari games. In both, large intrinsic bonuses obtained when the agent reaches the periphery of its experience. Correspondingly. when the agent dies, and the game state is reset something familiar, the ACB bonus typically drops by significant margin.
8

---

Published as a conference paper at ICLR 2022
Breakout
O*bert
Gravitar
Seaquest
Extrinsic Reward Extrinsic Reward
1000
600
800
30
3000
20
2000
400
700
200
0.0
0.5
1.0
1e7
0.00
0.25
0.50
0.75
1.00
1
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
Private Eye
Pitfall
1e7
Beamrider
1e7
Space Invaders 1e7
2500
400
0-
200
0000
1500
-200
ACB RND
4400
500
1.5
1e7 2.0
0.5
1.5
0.5
1.
Timesteps
Timesteps
1e7
Timesteps le7
Timesteps 1e7
Figure 7: Extrinsic reward in Atari games function of the number of frames seen by the agent. Each plot corresponds to a different intrinsic reward scheme. and PPO is being trained to jointly maximize these bonuses and the observed extrinsie reward. ACB is competitive with RND this setting, and for some environments and experience budgets, even obtains higher reward.
These intrinsic bonuses encourage the agent to avoid the start state, and to continually push the bound- ary of what has been observed far. by agents trained only on intrinsic rewards across eight popular Atari games and three different bonus schemes. Even though extrinsic reward is observed, many of these agents obtain non-trivial performance on the game, suggesting that the pursuit of novelty is often enough to play well. Extrinsic reward does not necessarily correlate with exploration quality, but ACB is clearly competitive with other intrinsic reward methods along this axis. In Figure 6 we measure the number of unique states en- countered, measured by a hash, as exploration progresses. ACB is competitive from this perspective as well, visiting as many or more states than baselines in most of the environments considered.
the per-episode extrinsic rewards collected
Intrinsic and extrinsic rewards. Next, while still in the non-episodic setting. we experiment with training PPO jointly on intrinsic and extrinsic rewards. Following the PPO modification proposed by Burda al. (20T8b), we use value heads, for intrinsic and another for extrinsic rewards. total reward is computed as the sum of intrinsic and extrinsic returns. Figure compares RND and ACB agents trained with both intrinsic and extrinsic rewards on eight Atari games, which shows ACB again performing competitively in comparison to RND. We find that ACB performs at least as well as RND most of the games considered, and sometimes, for particular timesteps and environments, even offers an improvement.
CONCLUSION
This article introduced ACB, scalable and camputationalllyttrccabbb algorithm for estimating the elliptical potential in both bandit and deep reinforcement learning scenarios. ACB avoids the need to invert large covariance matrix by instead storing this information an ensemble of weight vectors trained to predict random noise.
This work aims to bridge the gap between the empirical successes of deep reinforcement learning and the theoretical transparency of bandit algorithms. We believe ACB is big step along this direction, but there still more work to done to further this effort. For one, ACB still not able to perform well RND on Montezuma'ss 's Revenge, Atari benchmark for which exploration is notoriously difficult, and for which RND performs exceptionally well.
Our experiments indicate that our proposed technique of anti-concentrating optimism can improve empirical performance well beyond our current theoretical understanding. We leave improving our regret guarantees (such eliminating dependences on log(A), matching the optimal rate in all regimes), as well as extending our analysis to more difficult settings (such as the incremental case) as exciting open problems.

---

Published as a conference paper at ICLR 2022
REFERENCES
Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Neural Information Processing Systems, volume 11, pp. 2312-2320, 2011.
Naoki Abe and Philip M Long. Associative reinforcement learning using linear probabilistic concepts. In ICML, pp. 3-11. Citeseer, 1999.
Alekh Agarwal, Nan Jiang, and Sham M Kakade. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 2019.
Shipra Agrawal and Navin Goyal. Thompson sampling for contextual bandits with linear payoff's. In International Conference on Machine Learning, pp. 127-135. PMLR, 2013.
Jordan T Ash, Chicheng Zhang, Akshay Krishnamurthy, John Langford, and Alekh Agarwal. Deep batch active learning by diverse, uncertain gradient lower bounds. International Conference on Learning Representations, 2020.
Jordan T Ash, Surbhi Goel, Akshay Krishnamurthy, and Sham Kakade. Gone fishing: Neural active learning with fisher embeddings. Neural Information Processing Systems, 2021.
Peter Auer. Using confidence bounds for exploitaiion-exxloraaion trade-offs. Journal of Machine Learning Research, 3(Nov):397-422, 2002.
Chenjia Bai, Lingxiao Wang, Zhaoran Wang, Lei Han, Jianye Hao, Animesh Garg, and Peng Liu. Principled exploration via optimistic bootstrapping and backward induction. arXiv preprint 1rXiv:2005.06022, 2021.
Eric Temple Bell. Exponential polynomials. Annals of Mathematics, pp. 258-277, 1934.
Mare G Bellemare, Sriram Srinivasan, Georg Ostrovski, Tom Schaul, David Saxton, and Remi Munos. Unifying count-based exploration and intrinsic motivation. arXiv preprint arXiv:1606.00 01668, 2016.
William Beluch, Tim Genewein, Andreas Nürnberger, and Jan M Köhler. The power of ensembles for active learning in image classification. In IEEE Conference on Computer Vision and Puttern Recognition, 2018
Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexei A Efros. Large-scale study of curiosity-driven learning. arXiv preprint a8Xiv: 1808.04555 04355, 2018a.
Yuri Burda, Harrison Edwards, Amos Storkey, and Oleg Klimov. Exploration by random network distillation. arXiv preprint 1rXhv:1810.1284. 2018b.
Alexandra Carpentier, Claire Vernade, and Yasin Yadkori. The elliptical potential lemma revisited, arXiv preprint arXiv:2010.10183 2020.
Nicolo Cesa-Bias Dssa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
Kamalika Chaudhuri, Sham Kakade, Praneeth Netrapalli, and Sujay Sanghavi. Convergence rates of active learning for maximum likelihood estimation. arXiv preprint a5Xiv: 02348, 2015.
Varsha Dani, Thomas Hayes, and Sham M Kakade. Stochastic linear optimization under bandit.
feedback. In Conference on Learning Theory, 2008
Qin Ding, Cho-Jui Hsieh, and James Sharpnack. An efficient algorithm for generalized linear bandit: Online stochastic gradient descent and thompson sampling. In International Conference on Artificial Intelligence and Statistics, pp. 1585-1593. PMLR, 2021.
Yarin Gal, Riashat Islam, and Zoubin Ghahramani. Deep bayesian active learning with image data, In International Conference on Machine Learning. 2017.
Karol Gregor, Danilo Jimenez Rezende, and Daan Wierstra. Variational intrinsic control. arXiv preprint ar 161 007507, 2016.
10

---

Published as a conference paper at ICLR 2022
Quanquan Gu, Tong Zhang. and Jiawei Han. Batch-mode active learning via enror bound minimization. In UAI, pp. 300-309. Citeseer, 2014.
Arthur Guez, David Silver, and Peter Dayan. Efficient bayes- reinforcement learning using sample-based search. Advances in neural information processing systems, 25:1025-1033, 2012.
Mikael Henaff, Alfredo Canziani, and Yann LeCun. -oeel-predeeetie policc learning with uncertainty regularization for driving in dense traffic. arXiv preprini arXiv:900.002005. 2019.
Haque Ishfaq, Qiwen Cui, Viet Nguyen, Alex Ayoub, Zhuoran Yang. Zhaoran Wang, Doina Precup, and Lin Yang. Randomized exploration for reinforcement learning with general value function approximation. arXiv preprini arXiv:2106.0755 2021.
Kwang-Sung Jun, Aniruddha Bhargava, Robert Nowak, and Rebecca Willett. Scalable generalized linear bandits: Online computation and hashing. arXiv preprint arXiv:1706.001.6 2017.
Nathaniel Korda, LA Prashanth, and Rémi Munos. Fast gradient descent for drifting least squares regression, with application to bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
Branislav Kveton, Csaba Szepesvari, Mohammad Ghavamzadeh, and Craig Boutilier. Perturbed- history exploration in stochastic linear bandits. arXiv preprint 1rXiv:/90300910 2019.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandit approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web, pp. 661-670, 2010.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint arXiv:1509.0299 02971, 2015.
Xiuyuan Lu and Benjamin Van Roy. Ensemble sampling. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Asso- ciates, Inc., 2017. URL htttps://proceeddmmg http::/ppeeeeo.......oeooco/ccep
wwt.:nnneuuupppppeeeeeeeeeee httpps.ccpppppee pttpcc/ap/e///////eeeee (padd3ddeccffaaodddd/aaaaaaa Paap Paper.
Jarryd Martin, Suraj Narayanan Sasikumar, Tom Everitt, and Marcus Hutter. Count-based exploration in feature space for reinforcement learning. arXiv preprint arXiv: 080900, 2017.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas Fidjeland, Georg Ostrovski, al. Human-level control through deep reinforcement learning. nature, 518(7540):529-55 533-33,,993,3 2015.
Ofir Nabati, Tom Zahavy, and Shie Mannor. Online limited memory neural-linear bandits with likelihood matching. arXiv preprint 1rXiv:2102.03399, 2021.
Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. arXiv preprini 1rXiv:1306.0944 2013.
Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped dqn, arXiv preprint 10Xiv:160..04621, 2016.
Georg Ostrovski, Mare G Bellemare, Aäron Oord, and Rémi Munos. Count-based exploration with neural density models. In International conference machine learning, pp. 2721-2730. PMLR, 2017.
Pierre Yves Oudeyer, Frdric Kaplan, and Verena V Hafner. Intrinsic motivation systems for tonomous mental development. IEEE transactions on evolutionary computation, 11(2):265-28 2007.
11

---

Published as a conference paper at ICLR 2022
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driver exploration by self-supervised prediction. In International Conference on Machine Learning, pp- 2778-2787. PMLR, 2017.
Deepak Pathak, Dhiraj Gandhi, and Abhinav Gupta. Self-supervised exploration via disagreement. In International Conference on Machine Learning, pp. 5062-5071. PMLR, 2019.
Paat Rusmevichientongg and John N Tsitsiklis. Linearly parameterized bandits. Mathematics of Operations Research, 35(2):395 411, 2010.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.000 2017.
Ozan Sener and Silvio Savarese. Active learning for convolutional neural networks: A core-set
approach. In International Conference on Learning Representations, 2018.
Aleksandrs Slivkins. Introduction to multi-armed bandits. arXiv preprint arXiv: 1904.07272. 2019.
Bradly C Stadie, Sergey Levine, and Pieter Abbeel. Incentivizing exploration in reinforcement learning with deep predictive models. arXiv preprint 150,00157 2015.
Alexander I.
Strehl and Michael Littman. An analysis of model-based interval estimation for markov decision processes. Journal of Computer and System Sciences, 74(8):1309-1333 2008.
Malcolm Strens. A bayesian framework for reinforcement learning. In ICML, volume 2000, pp. 943-950, 2000.
Haoran Tang, Rein Houthooft, Davis Foote, Adam Stooke, Xi Chen, Yan Duan, John Schulman, Filip De Turck, and Pieter Abbeel. exploration: study of count-based exploration for deep reinforcement learning. arXiv preprint arXiv:1611.04711 2016.
William R Thompson. On the likelihood that unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25(3/4):285-294, 1933.
Stephen Tu.
Upper and lower tails of gaussian maxima.
https:/ /7
html 2017.
Tom Zahavy and Shie Mannor. Deep neural linear bandits: Overcoming catastrophic forgetting
through likelihood matching. arXiv preprint 1XXi:19901.08//1 2019.
Tong Zhang and F Oles. The value of unlabeled data for classification problems. In Proceedings of the Seventeenth International Conference Machine (aaniing.(Lanlle, P., ed.), volume 20, pp. 0. Citeseer, 2000.
Weitong Zhang, Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural thompson sampling. arXiv preprint arXiv:2010. 008877, 2020.
Dongruo Zhou, Lihong Li, and Quanquan Gu. Neural contextual bandits with ucb-based exploration. In International Conference on Machine Learning, pp. 11492-115511 11502. PMLR, 2020.
12

---

Published as a conference paper at ICLR 2022
A EXPERIMENTAL DETAILS
A.1 BANDIT EXPERIMENTS
Figure 2 shows the cumulative regret of Algorithm [ (with incremental sampling) in a simulated multi-armed bandit setting with A 50 actions, for different values of M (powers from 1 to 256). One randomly sampled arm is chosen to have mean reward of 0.75, with the others 0.25; the noise & for each arm is sampled independently from (0, 0.1²). Standard deviations are shown over 100 independent trials. The bonus scaling factor B was selected in each run by grid search over (0.01, 0.05, 0.1, 0.5, 1.0, 5.0, 10.0): the learning rate for SGD was selected by grid search over the same values. Each batch of experiments (one choice of algorithm and M;; all replicas and hyperparameter sweeps) took around CPU hour on an internal cluster.
A.2 ATARI EXPERIMENTS
All policy network architectures used, for ICM, RND, and ACB, have the convolutional architecture described in [Brdda et al. (20T8b), consisting three convolutional layers followed by two linear layers, and leaky ReLU activations. For ACB and RND, we use PPO hyperparameters also from Burda ct al. (2018b). including update epochs, an entropy coefficient of 0.001, 7E 0.999 and " =0.99. Our ICM implementation update epochs. We use a learning rate of 0.0001 and 128 simultaneous agents universally. All model updates performed via Adam except for the ACB auxiliary weights, which use RMSprop. See attached code for more details.
the default parameters of Pathak et al. (2017), which instead use
Compute resources per job included single CPU and either P100 of V100 NVIDIA GPU, with experiments each taking between three and five days.
B PROOFS OF REGRET BOUNDS
In this section, we prove Propositions
2 and 3 We use the following notation the analysis:
c denotes XI
Σ Sttay
regret, denotes the instantaneous regret (It,a- (zee 0-).
log (-) denotes (og((xx(1,)))
Furthermore, assume that || B for all t, a, ||0*|| S W. and that the T) are martingale difference sequence independent of the decisions made by the algorithm. Assume that the the are x² oL-subgaussian, with 0.
B.1
USEFUL LEMMAS
Lemma (Tail bounds for maximum of Gaussians; Tu 2017
Let 2()).... ...)...,(())))). (() be i..dd N(. 1)
random variables. Let Z denote maxj=1....MM |2 (2 Then, for all 0 < 5 < 1, each of these inequalities holds with probability least -8: 8:
Z 2
π 2
log(M//)) log log(1/8)
2 < V2
(
Mlg(2MM) + (oll))+++oo((/// 1og(1/8))
Lemma 6 (Proposition 5.5, Agarwal et al. (019 ). At any time E [T], for all a E Ao. with probability 6..
(0.00 0.) s Bollalss,'
for B, V2|00-1 + 20 (og(det(E,))_4//// 4/8,).
13

---

Published as a conference paper at ICLR 2022
Lemma (Sufficient conditions for the bonus). Suppose that for all t T, the bonuses satisfy
bonus, (a) S 72 "aal,t, bonus, (ariuss(aa"))) 2 7/1 1 lss.
Va A,
where a" is the optimal action. If we choose actions according to this bonus at every time step t, then with probability 1 8,
TB
R(T) S (12 + 5) dT log 1+
Ad
for 3 VXW + V20 dlog (1 + Xd + log(T/6), as long as 7 3.
Proof. Using the assumptions on the bonus and Lemma 6 with 6, = 5/TT. with probability for all t < T
regret, = (Etra- 00) (0t,ae: 0*)
Fe,a0 8: + Bellxe,a- lls,- - (Fe, Q*)
at 0.) + bonus;(a:) - bonus:(a") + Be Rell lls," (Ee 0*)
bonus, (at) bonus;(a") + +.llkee,a lss + Bell Fel lls,
2a a ||,,' 7 1 lls + Bell Ils." + Bell
< (72 + 1|
Summing up, we have
R(T)=
regret, Σ (12 + (1) (1)]l
T 122 + B,)2
| 1
2 log det(
(2 + B,)3
det(AI)
TB 1
< (12 + B
2dT 2dT log
Xd
The above follows from Cauchy-Schware and observing that B, S B for S T.
B.2 REGRET BOUNDS
Proposition (ACB regret bound with re-randomized history). Algorithm with randomized history, ensemble size M [log(2T/8)), X a² //2 and B VXW
V20 / log (1+ Adl + log(T/8), as long as n 2 B, obtains a regret bound of R(T) S O (ad A log(T/5) (8) log* (TBK)) with probability at least
Proof. At time since re-sample all the noisy targets, have,
Σ Tr.a. v(.)
w
If we want to hold for all f can choose 8 up constants.
35 -...
This would give essentially the same bound
14

---

Published as a conference paper at ICLR 2022
( 21,a/ is therefore distributed as N (o, ||= ( Thus by Lemma 5 for all a E A, with probability 1 6,
(wl) (uf) o2l|ztallss Vlog M + lolll(()))))
max
JE[M]
and for a",
c1 Tt lls. log M log (T/6)
max JE[M]
m zt.a.)
where C2 are fixed constants. Since ba =B maxje[M]
(5) K (w)) xt,aa) >) get
a lower and upper bound on the bonus in terms of the LinUCB bonus. Lastly, by the choice of M, with probability - 6, we satisfy conditions of Lemma with ei 2og vAW - + loo((T6). This gives us Xd
22 y log (1 + TB
R(T) 1
202 202/log/ (AT/))
+1) (VAW- 22 dog
TB 1+
+ log(T/0)
I1
TB Ad
C1
Ad
(TBW)) ad
=0 ody Tlog A Aoo log*
Proposition 3 (ACB regret bound with incremental updates), Assume further that the ne are i.i.d. sL-subgaussian random variables. Algorithm [ with incrementally randomized history, ensemble
size M [log(T/8)], X o² //2, and B VXW 22 Alog (1
TB
log(T/8), long XA
as 71 2 3, obtains regret bound of
R(T) R(T) so ( AAA log(T/8) log
TBW aA
the multi-armed bandit setting, with probability at least
Proof. Recall that the action set A is fixed, and d = A; will use Ta to denote Zt,a- We follow a "reward tape" argument (see, e.g., Slivkins (2019), Section 1.3.1) to show that the conditions of Lemma 7 hold. Notice that in the incremental version of Algorithm [ bonus;(a) depends only on the targets yن for -d + 1 S T < t, the number of times a (call this Nı(a)) has been selected up time 1, and the reward noise variables e for Wi
I, such that a, a. This is because (j) in the case where all the Va are orthogonal.
Σt=-de) d+1 1e,=a8r"
La
N.(a)
Consider the following procedure: sample T T'(11 + M) independent random variables ahead of time: TT.a. an i.i.d copy of 7/. for each T E [T], E [A], and v ~N(00 1) for each which at time t uses the random regression targets to compute bonus:(a), and observes
[T', a E [ E [M]] Then, run a deterministic version of Algorithm [ these (i) : 1, reward (Ia,, 8r) + (N,(a))LLaa Then, for any 8*, the distribution action sequences taken by this procedure identical to that of Algorithm with sequentially sampled ne and v. and Lemma holds. By Lemma with probability at least
8', we have that for any / E (T), E [A].
max SE(M]
( .2.. Soz 1 x Ne(a)
Vlog M log(AT/8'),
and for a",
a + N((a) V log M log log (T/8)
< max JE[M]
(
(1) (w))
for absolute constants C1, C2 0. so that the conditions of Lemma 7 hold with the same choice of B. Selecting 8' (2AT), we have by the union bound that this condition holds for all t [T]. a e [A].
and the proof reduces to that of Proposition 2 with identical regret bound of
TBW o
R(T) S ( Plog A (oo((T/5) log
15

---

Published as a conference paper at ICLR 2022
Note here that A d, and that T A is necessary for non-vacuous regret bound, that log A I (log I) factors in the main paper suppressed by the O(+) notation.
C LAZILY RE-RANDOMIZED ACB
Algorithm 3 Lazy-ACB for fixed action linear bandits
Parameters: ensemble size M; B, 7, A, fixed action set A
1: For all i 1, ,,..,, d, set warm-start features a-i+1 Vλe
2: Set
3: Set 0
4: for = 1,... T: do
5: if' w 0 then
6: Update parameters:
0, :- arg min
(la;, rr;(a)) + Al101s
0
7: Sample new targets Up NO, 1) for each j E [M],e' E 1..,+
8:
Update bonus ensemble for each j [M].
( wi = arg min
Σ
(aar w) w1
d+1
(a, w for each A
9:
Compute per-arm bonuses bonus, (a) B max
10:
Set 8 == arg max (a, 0e) + bonus, (a)
11:
Set w
bouuss
13:
Choose action ar Observe reward ri (at) (*) + Ex
15:
Decrease w by
In this section, we present the algorithm (see Algorithm 3 and regret analysis of a lazy-version of ACB which only rarely re-randoizzes history.
C.1 USEFUL LEMMAS
Lemma (Ensemble Bounds), For M = log(2AT/5), at all updates t, with probability for all E A.
π log 2
2.T 8 Slog
< bonus, $ 81lallss
2
Proof. Follows by applying Lemma5aam and taking union bound over A and < T.
Lemma 9. Let be the time of an update and 3² log Then, for 7' = T + bone??
det(Eip))
log 2
det(E,)
16 log (8)
16

---

Published as a conference paper at ICLR 2022
Proof. Note that from to r', the action taken remains the same. For the upper bound, using Lemma 11 from Abbasi- Yadkori et al. (2011) and some elementary calculus:
dot (E (Et(
2og
| ||
a7
[E + (i- 1-1)aaa²
-1
at
|| 5-1
Σ ||a 13.1 11(6 1) + 1| 14
||a,113.
1+ (i
1))la>11?
1/1|a=| 5. - (((--r)
du
1/
11
21
log
1 1+ (T' a 112--11
?
2 log
1 8,32 1og((A77 (2AT 15)
t log 2
log
1+
16 (2AT)(())))))
Lemma 10. Let be the largest index $ when the update happened and oy 8² log then
det (Ste) del(E.,)
S 2e.
Proof. Suppose t = Te. then the bound trivially holds, thus WLOG, assume Tb. By algorithm, we know that, 0 < t S Lemma 11 from Abbasi- Yadkori et al. 2011) and some elementary calculus:
bonus (o,) This implies, bonus?(a,) S 7. Now, using
(ct(Ex) (E.,)
log
|| -+1-1
t-r
a, x
1 + (i 1) 1))(ar 12
1=1
1/1la., 112
< ||ar, 1 +
du
///la, x
||a |س5m
+ log
11 - la
11
2bonus? (aT.)
2x
+ +log
1+
p7 log2
3
log
27
2"
+ +
1+
BeT log2
f2
log
2c.
17

---

Published as a conference paper at ICLR 2022
C.2 REGRET BOUND
Theorem (ACB regret bound with lazy updates), Algorithm with lazy re- randomized history, ensemble size M [ X
AT A
W2, and B
VAW v20 V d (1+ TB bound of
nd + log(TT))) V log and 7
8² log? 2
obtains a regret
TBW od 6. The algorithm re-randomizes
R(T) S Ó(ody Fog A) log(T/6) log*
in the fixed action linear bandit setting, with probability at least most Oddlog" BW/od) log(AT/6) times.
Proof. Let Te be the largest index < t when the update happened, then regret, = (a) (a7,, 0-))
a" 0r.) + Brlla" "t.lla"|s=;] (aT, 0*)
:re Or. + bonus; (ar.) - bonus, (a") ) + Bella Ils., (ar, 0-)
bonus, (ar.) bomus, (a*) + 3r, |1aa I1s.,, + Sr. 1t..1az.11 Iss.!
2AT
TT log
3 8 log
+
Brc
|a latells + Br - B/
||a" || Is
8
2
(2AT)
del(St)
llog 2
8 log
Pr.
|aalls. det(Cig))
||" !
8
2
(2AT
||aels,11 + 3V log
S 2e
B
log
+ By
||a !|5.
2
where the first inequality comes from the validity of the confidence bound for a", the second from the fact that a,, arg max, (a (a. 8.. + bonus,, (a), the third from the validity of the confidence bound for Oz the fourth follows from Lemma 8 the fifth follows from Lemma 12 Abbasi- Yadkori et al. (2 and lastly the sixth follows from Lemma 10
Setting 8/T we have By, S 3y
log therefore,
2AT
a log 2
regret, S 2e
1log
+
31 B||ae|ss.
2
Using the above, we have
T
2AT
log 2
R
Σ mm1
5
T
Σ
r <
2e
8logg
+
B 2T log(det(Ez)) -a)
8
2
t=l
2AT
π log
< 2e
8 log
+
B 22 +B/AAd).
8
2
Lastly, we need to bound the number of times we refresh randomness.
By Lemma 9 each time
log 2 we refresh, we increase det(E..) by factor of / + 1o log((2 A7788) Since det (E.)) det(AT) is
bounded by (1 B/ddd the number of times we refresh is = Od (TBW((d/ log AT /8))
Formally, must satisfy (1 16 16log(2AT/5)
4/2
θ ((1 + TB/Ad)
18


Reviews:
[{"review_id": "Hvhn3fjge6L", "reviewer": "Reviewer_1PxN", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n\nAlthough 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. \n\nDue to limited time, I was unable to check the proofs. Nonetheless, the results appear correct to me. \n\nBesides 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. \n\nMinor: \n\n- As far as I understood, all norms used in the paper are Euclidean norms. If so, stating this explicitly could be helpful. \n\n- p. 5: that that => than that\n\n- p. 7: one reference is inappropriately inserted (see “?”)\n\n- Both $L_2$ and $\\ell_2$ are used to indicate the same notion.  \n\n- 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$. \n\n- p. 13: The value of $\\gamma_E$ is missing. \n", "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. \n\nThe 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. \n\n", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "2c2fZINK7WX", "reviewer": "Reviewer_Ezvk", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\nWhile I’m mostly happy with the paper, I have the following questions/suggestions:\n\nTo 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_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.", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-Knf-U3yhXE", "reviewer": "Reviewer_AKDp", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n\nThis 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. \n\nThe 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.  \n\nThe 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.   \n\nWeaknesses: \n\nThe 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. \n\nIt 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.   \n\nAlgorithm 1 requires recursive least-squares optimization oracles. The per-iteration computational cost of implementing should also be discussed in the main paper. \n\nSimulations 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. \n\nKveton et al. 2019 – double citation. \n\nSynthetic bandit experiments should involve comparisons with other benchmarks as well as LinUCB.  \n", "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.\n", "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. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

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)