ANTI-CONCENTRATED CONFIDENCE BONUSES
Year: 2021

Abstract:
Intrinsic rewards play a central role in handling the exploration-exploitation trade-off 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 Õ(d √ T ) regret bounds for poly(d) fixed actions. We develop a practical variant for deep reinforcement learning that is competitive with contemporary intrinsic reward heuristics on Atari benchmarks.

text: √ T ) regret bounds for poly(d) fixed actions.
We develop a practical variant for deep reinforcement learning that is competitive with contemporary intrinsic reward heuristics on Atari benchmarks.

heading: 1 INTRODUCTION
text: Optimism in the face of uncertainty (OFU) is a ubiquitous algorithmic principle for online decisionmaking in bandit and reinforcement learning problems. Broadly, optimistic decision-making algorithms augment their reward models with a bonus (or intrinsic reward) proportional to their uncertainty about an action’s outcome, ideally balancing exploration and exploitation. A vast literature 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-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-based intrinsic reward modules (Burda et al., 2018b; Pathak et al., 2017; Osband et al., 2016). Such bonuses can be very useful, with prior work demonstrating impressive results on a wide array of challenging exploration problems. Several of these methods draw inspiration from theoretical work on multiarmed bandits, using ideas like count-based exploration bonuses. However, a 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 et al., 2010; Abbasi-Yadkori et al., 2011) is attractive in this setting because it 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, a naive implementation of the LinUCB algorithm would require remembering all of the agent’s experience and constantly recomputing and inverting this matrix, which is likely extremely large. Clearly, such an approach is too computationally intensive to be useful. As we discuss in the next section, several works have used neural features for LinUCB-style bonuses, but all require an inversion of this sort, limiting their ability to scale to high dimensions.
Towards bridging foundational algorithms with empirical frontiers, we develop a scalable strategy for computing LinUCB’s elliptical bonus, enabling us to investigate its effectiveness as an intrinsic
reward in deep reinforcement learning. We use an ensemble of least-squares regressors to 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.

heading: 1.1 OUR CONTRIBUTIONS
text: We propose the use of anti-concentrated confidence bounds (ACB) to 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 a 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 elliptical potential; thus, optimistic exploration with ACB directly inherits standard analysis techniques for LinUCB. We derive near-optimal high-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 the special cases of 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 independent Gaussians; we conjecture that they are improvable using more sophisticated analytical tools.
The main contribution of this work is empirical: we find that ACB provides a viable exploration bonus for deep reinforcement learning. After defining a suitable nonlinear analogue using action features from the policy network, we demonstrate that the intrinsic rewards produced by ACB are competitive with those from state-of-the-art algorithms in deep RL on a variety of Atari benchmarks (Figure 1). To the best of our knowledge, our work is the first to scalably study bonuses from the linear bandits literature in these deep reinforcement learning settings.

heading: 1.2 RELATED WORK
text: 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; Rusmevichientong & Tsitsiklis, 2010; Abbasi-Yadkori et al., 2011), and provide minimax-optimal regret bounds.
Several works are concerned with designing more scalable optimism-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. (2021) give strong regret guarantees for epoch-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. (2015) 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. (2021) study perturbed regressions for exploration, obtaining similar regret bounds to ours (including the suboptimal √ logA factor in the regret bounds). The LinPHE algorithm in (Kveton et al., 2019) uses a single random regressor’s constant-probability anti-concentration to approximate the elliptical bonus. In work concurrent to ours, the main algorithm proposed by Ishfaq et al. (2021) 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-rerandomizing” variant of ACB (Algorithm 1), which is still not suitable for large-scale deep RL. Our work introduces the “lazily-rerandomizing” and “never-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 2) offering performance comparable to commonly used deep RL bonuses on a wide array of Atari benchmarks without sacrificing theoretical transparency. The resulting algorithmic choices deviate somewhat from the bandit version (as well as LinPHE/LSVIPHE), 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 to Monte Carlo techniques for posterior sampling (Thompson, 1933; Agrawal & Goyal, 2013). This is a starting point for many empiricallymotivated exploration algorithms, including for deep RL (see below), but theory is limited. (Lu & Van Roy, 2017) analyze an ensemble-based approximation of Thompson sampling (without considering a max over the ensemble), and obtain a suboptimal regret bound scaling with A logA.
Exploration in deep reinforcement learning. In deep reinforcement learning, most popular approaches 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 as a modification to Intelligent Adaptive Curiosity, but relying on a representation that is trained to encourage retaining only causal information in transition dynamics (Oudeyer et al., 2007). Stadie et al. (2015) instead use a representation learned by an autoencoder. A large-scale study of these “curiosity-based” approaches can be found in Burda et al. (2018a).
Similar to these algorithms, Random Network Distillation (RND) relies on the inductive bias of a 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 (Strehl & 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 example, Variational Intrinsic Control (Gregor et al., 2016) uses a 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 an ensemble. More broadly, various approximations of Thompson sampling (Thompson, 1933) have been used to encourage exploration in deep reinforcement learning (Osband et al., 2013; Guez et al., 2012; Zhang et al., 2020; Strens, 2000; Henaff et al., 2019). 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 et al., 2018).
Separate from these, there has been some work intended to more-directly deliver UCB-inspired bonuses to reinforcement learning (Zhou et al., 2020; Nabati et al., 2021; Zahavy & Mannor, 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.
0 1 2 3 4 5 Timesteps 1e3
0
1
2
3
4
5
6
Cu m
ul at
iv e
Re gr
et 1e2 OLS ensemble updates M=1 M=2 M=4 M=8 M=16 M=32 M=64 M=128 M=256 LinUCB
0 1 2 3 4 5 Timesteps 1e3
0
1
2
3
4
5
6 1e2 SGD ensemble updates Figure 2: The cumulative regret
for ACB (incremental sampling) with different ensemble sizes. We show a multi-armed bandit setting with 50 actions, comparing exact ordinary least squares (left) with SGD using Polyak averaging (right). Up to a point, increasing ensemble size improves cumulative regret in both cases.

heading: 2 PRELIMINARIES
text: In this section, we provide a brief review and establish notation for the stochastic linear bandit setting and the LinUCB algorithm. For a more comprehensive treatment, see Agarwal et al. (2019); Lattimore & Szepesvári (2020). At round t = 1, . . . , T , the learner is given an action set At ⊆ A with features {xt,a ∈ Rd}a∈At , chooses an action at ∈ At, and receives reward rt(at) := 〈xt,at , θ∗〉+ εt, where εt is a martingale difference sequence. We use A to denote maxt |At|. The performance of the learner is quantified by its regret,
R(T ) = T∑ t=1 〈 xt,a∗t , θ ∗〉− 〈xt,at , θ∗〉 , a∗t := arg max a∈At 〈xt,a, θ∗〉 .
This setting encompasses two commonly-considered special cases:
• Fixed actions: the action sets At are the same for all t.
• Multi-armed bandits: fixed actions, with At = [d] and xt,a = ea. Here, θ∗ is the vector of per-arm means.
An OFU-based algorithm plays at round t
at := arg max a∈At
{r̂t(a) + bonust(a)} ,
where r̂t(a) is an estimate for the reward rt(a), and bonust(a) is selected to be a valid upper confidence bound for r̂t(a), such that E[rt(a)] ≤ r̂t(a) + bonust(a) with high probability. The LinUCB algorithm uses r̂t(a) := 〈 xt,a, θ̂t 〉 , where θ̂t = arg minθ∈Rd ∑t−1 τ=1 (〈xτ,aτ , θ〉 − ri(ai)) 2 + λ‖θ‖2
is the 2-regularized least-squares regressor for the reward, and sets bonust(a) = β √ x>t,aΣ̃ −1 t xt,a,
where Σ̃t := λI + ∑t−1 τ=1 xt,atx > t,at . In an online learning context, this is known as the elliptical potential (Cesa-Bianchi & Lugosi, 2006; Carpentier et al., 2020). We will quantify the theoretical performance of ACB by comparing it to LinUCB. Theorem 1 gives a high-probability regret bound for LinUCB, which is optimal up to logarithmic factors:
Theorem 1 (LinUCB regret bound; Theorem 5.3, (Agarwal et al., 2019)). If ||θ∗||, ||xt,a|| ≤ O(1), and each εt is O(1)-subgaussian, then there are choices of λ, β such that, with probability at least 1− δ, the regret of the LinUCB algorithm satisfies
R(T ) ≤ Õ ( d √ T ) .
The Õ(·) suppresses factors polynomial in log(1/δ) and log T .
LinUCB can be implemented in O(d2|At|) time per iteration, by maintaining Σ̃−1t using rank-1 updates, and using this to compute the least-squares estimator θ̂t = Σ̃−1t ∑t−1 τ=1 xτ,aτ rτ (aτ ) as well as bonust(a).
Algorithm 1 ACB for linear bandits Parameters: ensemble size M ; β, λ
1: For all i = 1, . . . , d, set warm-start features x−i+1 = √ λei and corresponding warm-start targets
y (j) −i+1 ∼ N (0, 1) for each j ∈ [M ]
2: for t = 1, . . . , T : do 3: Observe action features {xt,a}a∈At 4: Update reward estimator:
θ̂t := arg min θ t−1∑ τ=1 (〈xτ,aτ , θ〉 − rτ (aτ )) 2 + λ‖θ‖2
5: Sample new random ensemble targets: (re-randomized) y(j)τ ∼ N (0, 1) for each j ∈ [M ], τ ∈ {−d+ 1, . . . , t− 1}
(incremental) y(j)t−1 ∼ N (0, 1) for each j ∈ [M ]
6: Update bonus ensembles for each j ∈ [M ],
w (j) t := arg min
w t−1∑ τ=−d+1 ( 〈xτ,aτ , w〉 − y(j)τ )2 7: Compute per-arm bonuses bonust(a) := β ·maxj∈[M ]
∣∣∣〈xt,a, w(j)t 〉∣∣∣ for each a ∈ At 8: Choose action at := arg maxa∈At〈xt,a, θ̂t〉+ bonust(a) 9: Observe reward rt(at) = 〈xt,at , θ∗〉+ εt

heading: 3 ANTI-CONCENTRATED CONFIDENCE BOUNDS FOR LINEAR BANDITS
text: 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 of an ensemble of such regressors by taking a maximum over their outputs, allowing us to construct upper confidence bounds for r̂t(a). ACB maintains M linear regressors trained to predict i.i.d. standard Gaussian noise, and sets the bonus to be proportional to the maximum deviation over this ensemble from its mean (which is 0). This procedure is formally provided in Algorithm 1.
With the correct choice of ensemble size, the concentration of the maximum of independent Gaussians implies that each bonust(a) is large enough to be a valid upper confidence bound, yet small enough to 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 weightwjt . For these two variants, the following regret bounds result from straightforward modifications to the analysis of LinUCB (Abbasi-Yadkori et al., 2011), which are deferred (along with more precise statements) to Appendix B: Proposition 2 (ACB regret bound with re-randomized history). Then, Algorithm 1, with rerandomized history and ensemble size M = Θ(log(T/δ)), obtains a regret bound of Õ(d √ T logA), with probability at least 1− δ.
For A ≤ O(poly(d)), our regret bound matches that of LinUCB up to logarithmic factors. We note that the expected regret guarantee of the LinPHE algorithm in Kveton et al. (2019) also has the same dependence on log(AT ). Our lower-tail analysis on the number of regressors required for the maximum deviation to be optimistic is slightly sharper than that found in Ishfaq et al. (2021), by a factor of logA; this is due to requiring optimism only on a∗ in Lemma 2. Proposition 3 (ACB regret bound with incremental updates). Algorithm 1, with incrementally randomized history and an ensemble size of M = Θ(log(T/δ)), obtains a regret bound of Õ(A √ T ) in the multi-armed bandit setting, with probability at least 1− δ.
We conjecture that the incrementally-updated version guarantees can be extended to linear bandits beyond MAB for reasonable ensemble sizes. In between the extremes of always vs. never re-
Algorithm 2 ACB exploration for reinforcement learning Parameters: ensemble M , tail-average constant γ, policy network function f parameterized by θ,
update frequency τ 1: Initialize auxiliary weights w(j)0 ∈ Rd, ∀j ∈ [M ] 2: Initialize auxiliary policy network parameters θaux ← θ 3: for t = 1, . . . , T : do 4: Observe state xt 5: Compute gradient features using auxiliary policy network gt := g(xt; f, θaux) 6: Evaluate bonus bt = maxj(((w (j) t ) >gt)
2) 7: Select action from policy network softmax distribution f(xt; θ) 8: if t is a multiple of τ then 9: Update policy network parameters θ with PPO on intrinsic rewards {bt−τ+1, . . . , bt}
10: For all j ∈ [M ], draw random targets y(j)t ∼ N (0, 1) and compute loss
L (j) t = ((w (j) t ) >gt − y(j)t )2 + λ||w (j) t − w (j) 0 ||22
11: For all j ∈ [M ], update w(j)t+1 using L (j) t //using RMSProp 12: Update auxillary network parameters θaux ← αθ + (1− α)θaux
randomizing history, it is possible to analyze a “rarely re-randomizing” variant of the algorithm, which obtains the smaller sufficient ensemble size of Proposition 2 while only re-randomizing Õ(d log T ) times:
Theorem 4 (Lazy re-randomization). Algorithm 3, with lazy re-randomized history, obtains a regret bound of Õ(d √ log(AT/δ)T ) in the case of linear bandits with fixed actions, while resampling the
random targets y(j)τ only Õ(d log(AT/δ) log(T )) times.
We defer the modified algorithm and analysis to 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 (Ishfaq et al., 2021), 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., 2021), with theoretically sound hyperparameter choices, we do not exhibit end-to-end theoretical improvements over the O(d2|At|) per-iteration cost of rank-1 updates for implementing LinUCB. Both lines 4 and 6 in Algorithm 1 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(Md|At|) 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 1 (with incremental sampling) in a 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 εt for each arm is sampled independently from N (0, 0.12). 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 to avoid too many upper-tail events. Further details are provided in Appendix A.1.

heading: 4 EXTENDING ACB TO DEEP REINFORCEMENT LEARNING
text: Outlined as Algorithm 2, the RL version of ACB deviates from the version mentioned earlier in several ways. First, like other work assigning exploratory bonuses in deep reinforcement learning, we assign intrinsic rewards on states, rather than on state-action pairs (Pathak et al., 2017; Burda et al., 2018b). 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 to 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 is 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, a more recent approach is to instead represent data using a hallucinated gradient, embedding data as the gradient that would be induced by the sample if the most likely label according to the model were the true label (Ash et al., 2020). Treating the policy network as a classifier, we find that this representation tends to perform better than using just the penultimate layer. Specifically, this gradient is computed as
g(x; f, θ) = ∂
∂θ `ce(f(x; θ), ŷ), ŷ = argmax f(x; θ), (1)
where f is the policy network, θ is its current parameters, `ce(ỹ, ŷ) is the log loss of the prediction ỹ given true label ŷ, and ŷ is the action to which the most probability mass is assigned. Using this representation, each seen state x contributes gxg>x to the ACB covariance matrix, a quantity that can viewed as a sort of rank-one approximation of the pointwise Fisher information, I(x, θ) = Ey∼f(x,θ)∇`(f(x, θ), y)(∇`(f(x, θ), y))> (Ash et al., 2021). This connection draws a parallel between ACB with gradient features and well-understood, Fisher-based objectives in the active learning literature (Zhang & Oles, 2000; Gu et al., 2014; Chaudhuri et al., 2015). The ability to use such a gradient representation highlights the scalability of ACB—policy networks used in RL are typically composed of over a million parameters, and explicitly maintaining and inverting a covariance matrix of this size is 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-layer representation, according to the number of unique states encountered by the agent (using a hash). In both cases, representations are computed on a Polyak-averaged version of the policy with α = 10−6, which we also use in Section 5 below.

heading: 5 EXPERIMENTS
text: This section compares ACB with state-of-the-art approaches to exploration bonuses in deep reinforcement learning on 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 et al., 2017). In all experiments, we use 128 parallel agents and rollouts of 128 timesteps, making τ in Algorithm 2 1282. Like other work on intrinsic bonuses, we consider the non-episodic setting, so the agent is 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 or 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 to help mitigate the domain shift in the gradient representation. Among these, as 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 (Lillicrap et al., 2015; Bell, 1934). In experiments shown here, α is fixed at 10−6. We additionally normalize intrinsic bonuses by a running estimate of their standard deviation, an implementation detail that is also 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 Polyak-averaged version of the ensemble rather than the ensemble itself. We use the RMSprop variant of SGD in optimizing auxiliary weights.
We use an ensemble of 128 auxiliary weights and regularize aggressively towards their initialization with λ = 103. 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 4). Experiments here consider eight different Atari games. Environments were chosen to include both games that are known to be challenging in the way of exploration (Private Eye, Pitfall! and Gravitar (Burda et al., 2018b)), and games that are not—remaining environments overlap with those from Table 1 of Mnih et al. (2015))
Intrinsic rewards only. In our first set of experiments, we train agents exclusively on bonuses generated by ACB, rather than on any extrinsic reward signal. In Figure 1, we visualize some of these bonuses as gameplay progresses in two Atari games. In both, large intrinsic bonuses are obtained when the agent reaches the periphery of its experience. Correspondingly, when the agent dies, and the game state is reset to something familiar, the ACB bonus typically drops by a significant margin.
These intrinsic bonuses encourage the agent to avoid the start state, and to continually push the boundary of what has been observed so far. Figure 5 compares the per-episode extrinsic rewards collected by agents trained only on intrinsic rewards across eight popular Atari games and three different bonus schemes. Even though extrinsic reward is not 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 encountered, as 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.
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 et al. (2018b), we use two value heads, one for intrinsic and another for extrinsic rewards. total reward is computed as the sum of intrinsic and extrinsic returns. Figure 7 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 on most of the games we considered, and sometimes, for particular timesteps and environments, even offers an improvement.

heading: 6 CONCLUSION
text: This article introduced ACB, a scalable and computationally-tractable algorithm for estimating the elliptical potential in both bandit and deep reinforcement learning scenarios. ACB avoids the need to invert a large covariance matrix by instead storing this information in 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 a big step along this direction, but there is still more work to be done to further this effort. For one, ACB is still not able to perform as well as RND on Montezuma’s Revenge, an 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 as 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.

heading: A EXPERIMENTAL DETAILS

heading: A.1 BANDIT EXPERIMENTS
text: Figure 2 shows the cumulative regret of Algorithm 1 (with incremental sampling) in a simulated multi-armed bandit setting with A = 50 actions, for different values of M (powers of 2 from 1 to 256). One randomly sampled arm is chosen to have a mean reward of 0.75, with the others 0.25; the noise εt for each arm is sampled independently from N (0, 0.12). Standard deviations are shown over 100 independent trials. The bonus scaling factor β 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 1 CPU hour on an internal cluster.

heading: A.2 ATARI EXPERIMENTS
text: All policy network architectures used, for ICM, RND, and ACB, have the convolutional architecture described in Burda et al. (2018b), consisting of three convolutional layers followed by two linear layers, and leaky ReLU activations. For ACB and RND, we use PPO hyperparameters also from Burda et al. (2018b), including 4 update epochs, an entropy coefficient of 0.001, γE = 0.999 and γI =0.99. Our ICM implementation uses the default parameters of Pathak et al. (2017), which instead use 3 update epochs. We use a learning rate of 0.0001 and 128 simultaneous agents universally. All model updates are performed via Adam except for the ACB auxiliary weights, which use RMSprop. See attached code for more details.
Compute resources per job included a single CPU and either a P100 of V100 NVIDIA GPU, with experiments each taking between three and five days.

heading: B PROOFS OF REGRET BOUNDS
text: In this section, we prove Propositions 2 and 3. We use the following notation in the analysis:
• Σ̃t denotes λI + ∑t−1 τ=1 xt,atx > t,at .
• regrett denotes the instantaneous regret 〈xt,a∗ , θ∗〉 − 〈xt,at , θ∗〉.
• log+(·) denotes log(max(1, ·)).
Furthermore, we assume that ||xt,a|| ≤ B for all t, a, ||θ∗|| ≤ W , and that the ηt are a martingale difference sequence independent of the decisions made by the algorithm. Assume that the ηt are σ2-subgaussian, with σ > 0.

heading: B.1 USEFUL LEMMAS
text: Lemma 5 (Tail bounds for a maximum of Gaussians; Tu (2017)). Let z(1), . . . , z(M) be i.i.d. N (0, 1) random variables. Let Z denote maxj=1,...,M |z(j)|. Then, for all 0 < δ < 1, each of these inequalities holds with probability at least 1− δ:
Z ≥ √ π
2
√ log(M/2)− log log(1/δ).
Z ≤ √ 2 (√ log(2M) + √ log(1/δ) ) .
Lemma 6 (Proposition 5.5, Agarwal et al. (2019)). At any time t ∈ [T ], for all a ∈ At, with probability 1− δt, 〈 a, θ∗ − θ̂t 〉 ≤ βt‖a‖Σ̃−1t
for βt = √ λ‖θ∗‖+ √ 2σ2 log(det(Σ̃t)λ−d/δt).
Lemma 7 (Sufficient conditions for the bonus). Suppose that for all t ≤ T , the bonuses satisfy
bonust(a) ≤ γ2‖xt,a‖Σ̃−1t ∀ a ∈ At bonust(a
∗) ≥ γ1‖xt,a∗‖Σ̃−1t where a∗ is the optimal action. If we choose actions according to this bonus at every time step t, then with probability 1− δ,
R(T ) ≤ (γ2 + β̄) √ dT log ( 1 + TB
λd ) for β̄ = √ λW + √ 2σ √ d log ( 1 + TBλd ) + log(T/δ), as long as γ1 ≥ β̄.
Proof. Using the assumptions on the bonus and Lemma 6 with δt = δ/T , 1 with probability 1− δ, for all t ≤ T
regrett = 〈xt,a∗ , θ∗〉 − 〈xt,at , θ∗〉 ≤ 〈 xt,a∗ , θ̂t 〉 + βt‖xt,a∗‖Σ̃−1t − 〈xt,at , θ ∗〉
≤ 〈 xt,at , θ̂t 〉 + bonust(at)− bonust(a∗) + βt‖xt,a∗‖Σ̃−1t − 〈xt,at , θ ∗〉 ≤ bonust(at)− bonust(a∗) + βt‖xt,a∗‖Σ̃−1t + βt‖xt,at‖Σ̃−1t ≤ γ2‖xt,at‖Σ̃−1t − γ1‖xt,a∗‖Σ̃−1t + βt‖xt,a∗‖Σ̃−1t + βt‖xt,at‖Σ̃−1t ≤ (γ2 + βt)‖xt,at‖Σ̃−1t .
Summing up, we have
R(T ) = T∑ t=1 regrett ≤ T∑ t=1 (γ2 + βt)‖xt,at‖Σ̃−1t
≤ √√√√ T∑ t=1 (γ2 + βt)2 √√√√ T∑ t=1 ‖xt,at‖2Σ̃−1t
≤ √√√√ T∑ t=1 (γ2 + βt)2 √ 2 log det(Σ̃T ) det(λI)
≤ (γ2 + β̄) √ 2dT log ( 1 + TB
λd
) .
The above follows from Cauchy-Schwarz and observing that βt ≤ β̄ for all t ≤ T .

heading: B.2 REGRET BOUNDS
text: Proposition 2 (ACB regret bound with re-randomized history). Algorithm 1, with rerandomized history, ensemble size M = dlog(2T/δ)e, λ = σ2/W 2, and β = √ λW +
√ 2σ √ d log ( 1 + TBλd ) + log(T/δ), as long as γ1 ≥ β̄, obtains a regret bound of R(T ) ≤
O ( σd √ T logA log(T/δ) log+ ( TBW σd )) , with probability at least 1− δ.
Proof. At time t, since we re-sample all the noisy targets, we have,
w (j) t = Σ̃ −1 t t−1∑ τ=−d+1 xτ,aτ y (j) τ .
1If we want it to hold for all t <∞, we can choose δt = 3δπ2t2 . This would give essentially the same bound up to constants.
〈 w
(j) t , xt,a
〉 is therefore distributed as N ( 0, ‖xt,a‖2Σ̃−1t ) . Thus by Lemma 5, for all a ∈ At with
probability 1− δ,
max j∈[M ] ∣∣∣〈w(j)t , xt,a〉∣∣∣ ≤ c2‖xt,a‖Σ̃−1t √logM + log(AT/δ), and for a∗,
c1‖xt,a∗‖Σ̃−1t √ logM − log log(T/δ) ≤ max j∈[M ] ∣∣∣〈w(j)t , xt,a∗〉∣∣∣ where c1, c2 > 0 are fixed constants. Since bonust(a) = βmaxj∈[M ]
∣∣∣〈w(j)t , xt,a〉∣∣∣, we get a lower and upper bound on the bonus in terms of the LinUCB bonus. Lastly, by the choice of M , with probability 1 − δ, we satisfy conditions of Lemma 7 with c1 √ log 2β = √ λW +
√ 2σ √ d log ( 1 + TBλd ) + log(T/δ). This gives us
R(T ) ≤
( 2c2 √ log(AT/δ)
c1 + 1
)( √ λW + √ 2σ √ d log ( 1 + TB
λd
) + log(T/δ) )√ dT log ( 1 + TB
λd ) = O ( σd √ T logA log(T/δ) log+ ( TBW
σd
)) .
Proposition 3 (ACB regret bound with incremental updates). Assume further that the ηt are i.i.d. σ2-subgaussian random variables. Algorithm 1, with incrementally randomized history, ensemble size M = dlog(T/δ)e, λ = σ2/W 2, and β = √ λW + √ 2σ √ A log ( 1 + TBλA ) + log(T/δ), as long as γ1 ≥ β̄, obtains a regret bound of
R(T ) ≤ O ( σA √ T logA log(T/δ) log+ ( TBW
σA )) in the multi-armed bandit setting, with probability at least 1− δ.
Proof. Recall that the action set A is fixed, and d = A; we will use xa to denote xt,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 1, bonust(a) depends only on the targets y(j)τ for −d + 1 ≤ τ < t, the number of times a (call this Nt(a)) has been selected up to time t − 1, and the reward noise variables ετ for 1 ≤ τ < t, such that aτ = a. This is because〈 w
(j) t , xa 〉 = 1Nt(a) ∑t−1 τ=−d+1 1aτ=ay (j) τ in the case where all the xa are orthogonal.
Consider the following procedure: sample TA(1 + M) independent random variables ahead of time: ητ,a, an i.i.d copy of ηt for each τ ∈ [T ], a ∈ [A], and y(j)τ,a ∼ N (0, 1) for each τ ∈ [T ], a ∈ [A], j ∈ [M ]. Then, run a deterministic version of Algorithm 1, which at time t uses these y(j)τ,a : τ = 1, . . . , Nt(a) as the random regression targets to compute bonust(a), and observes reward 〈xat , θ?〉+ ηNt(at)+1,at . Then, for any θ∗, the distribution of action sequences taken by this procedure is identical to that of Algorithm 1 with sequentially sampled ηt and y (j) t , and Lemma 6 holds. By Lemma 5, with probability at least 1− δ′, we have that for any t ∈ [T ], a ∈ [A],
max j∈[M ]
∣∣∣〈w(j)t , xt,a〉∣∣∣ ≤ c2 √
1
λ+Nt(a)
√ logM + log(AT/δ′),
and for a∗,
c1
√ 1
λ+Nt(a)
√ logM − log log(T/δ′) ≤ max
j∈[M ] ∣∣∣〈w(j)t , xt,a∗〉∣∣∣ , for absolute constants c1, c2 > 0, so that the conditions of Lemma 7 hold with the same choice of β̄. Selecting δ′ = δ/(2AT ), we have by the union bound that this condition holds for all t ∈ [T ], a ∈ [A], and the proof reduces to that of Proposition 2, with an identical regret bound of
R(T ) ≤ O ( σA √ T logA log(T/δ) log+ ( TBW
σA
)) .
Note here that A = d, and that T ≥ A is necessary for a non-vacuous regret bound, so that logA ≤ O(log T ) factors in the main paper are suppressed by the Õ(·) notation.

heading: C LAZILY RE-RANDOMIZED ACB
text: Algorithm 3 Lazy-ACB for fixed action linear bandits Parameters: ensemble size M ; β, γ, λ, fixed action set A
1: For all i = 1, . . . , d, set warm-start features a−i+1 = √ λei 2: Set τ = 1 3: Set ω = 0 4: for t = 1, · · · , T : do 5: if ω = 0 then 6: Update parameters:
θ̂t := arg min θ t−1∑ i=1 (〈ai, θ〉 − ri(ai))2 + λ‖θ‖2
7: Sample new targets y(j)t′ ∼ N (0, 1) for each j ∈ [M ], t′ ∈ {−d+ 1, . . . , t− 1} 8: Update bonus ensemble for each j ∈ [M ],
w (j) t := arg min
w t−1∑ t′=−d+1 ( 〈at′ , w〉 − y(j)t′ )2 9: Compute per-arm bonuses bonust(a) := β ·maxj∈[M ]
∣∣∣〈a,w(j)τ 〉∣∣∣ for each a ∈ A 10: Set st := arg maxa∈[A]〈a, θ̂t〉+ bonust(a) 11: Set ω = ⌈ γ
bonus2(st) ⌉ 12: τ = t 13: Choose action at = aτ 14: Observe reward rt(at) = 〈st, θ∗〉+ εt 15: Decrease ω by 1
In this section, we present the algorithm (see Algorithm 3) and regret analysis of a lazy-version of ACB which only rarely re-randomizes history.

heading: C.1 USEFUL LEMMAS
text: Lemma 8 (Ensemble Bounds). For M = log(2AT/δ), at all updates τ , with probability 1− δ, for all a ∈ A,
β‖a‖Σ̃−1t
√ π log 2
2 ≤ bonusτ (a) ≤ β‖a‖Σ̃−1t
√ 8 log ( 2AT
δ
) .
Proof. Follows by applying Lemma 5 and taking union bound over A and t ≤ T .
Lemma 9. Let τ be the time of an update and γ = β 2π log 2 2 . Then, for τ ′ = τ +
⌈ γ
bonus2τ (aτ )
⌉ ,
det(Σ̃τ ′) det(Σ̃τ ) ≥
√ 1 +
π log 2
16 log(2AT/δ) .
Proof. Note that from τ to τ ′, the action taken remains the same. For the upper bound, using Lemma 11 from Abbasi-Yadkori et al. (2011) and some elementary calculus:
2 log
( det(Σ̃τ ′)
det(Σ̃τ ) ) ≥ τ ′−τ∑ i=1 ‖aτ‖2Σ̃−1τ+i−1
= τ ′−τ∑ i=1 aTτ ( Σ̃τ + (i− 1)aτaTτ )−1 aτ
= τ ′−τ∑ i=1 ‖aτ‖2Σ̃−1τ − ‖aτ‖4Σ̃−1τ 1/(i− 1) + ‖aτ‖2Σ̃−1τ
= τ ′−τ∑ i=1 ‖aτ‖2Σ̃−1τ 1 + (i− 1)‖aτ‖2Σ̃−1τ
≥ ∫ 1/‖aτ‖2 Σ̃ −1 τ +(τ ′−τ)
1/‖aτ‖2 Σ̃ −1 τ
1 u du
≥ log ( 1 + (τ ′ − τ)‖aτ‖2Σ̃−1τ )
≥ log ( 1 + γ
8β2 log(2AT/δ) ) = log ( 1 + π log 2
16 log(2AT/δ)
) .
Lemma 10. Let τt be the largest index ≤ t when the update happened and γ = β 2π log 2
2 , then
det(Σ̃t) det(Σ̃τt) ≤ 2e.
Proof. Suppose t = τt, then the bound trivially holds, thus WLOG, we assume t > τt. By our algorithm, we know that, 0 < t− τt ≤
⌈ γ
bonus2τt (aτ )
⌉ . This implies, bonus2τ (aτ ) ≤ γ. Now, using
Lemma 11 from Abbasi-Yadkori et al. (2011) and some elementary calculus:
log
( det(Σ̃t)
det(Σ̃τt) ) ≤ t−τt∑ i=1 ‖aτt‖2Σ̃−1τ+i−1
= t−τ∑ i=1 ‖aτt‖2Σ̃−1τt 1 + (i− 1)‖aτt‖2Σ̃−1τt
≤ ‖aτt‖2Σ̃−1τt + ∫ 1/‖aτt‖2Σ̃−1τt +t−τ−1
1/‖aτt‖2Σ̃−1τt
1 u du
≤ ‖aτt‖2Σ̃−1τt + log ( 1 + (t− τ − 1)‖aτt‖2Σ̃−1τt ) ≤ 2bonus2τt(aτt)
β2π log 2 + log
( 1 +
2γ
β2π log 2 ) ≤ 2γ β2π log 2 + log ( 1 + 2γ β2π log 2
) = 2e.

heading: C.2 REGRET BOUND
text: Theorem 4 (ACB regret bound with lazy updates). Algorithm 3, with lazy rerandomized history, ensemble size M = dlog(AT/δ)e, λ = σ2/W 2, and β =(√
λW + √ 2σ √ d log ( 1 + TBλd ) + log(T/δ) )√ 2 π log 2 , and γ = β2π log 2
2 , obtains a regret bound of
R(T ) ≤ Õ(σd √ T logA) log(T/δ) log+ ( TBW
σd ) in the fixed action linear bandit setting, with probability at least 1− δ. The algorithm re-randomizes at most O(d log+(TBW/σd) log(AT/δ)) times.
Proof. Let τt be the largest index ≤ t when the update happened, then
regrett = 〈a∗, θ∗〉 − 〈aτt , θ∗〉 ≤ 〈 a∗, θ̂τt 〉 + βτt‖a∗‖Σ̃−1τt − 〈aτt , θ ∗〉
≤ 〈 aτt , θ̂τt 〉 + bonusτt(aτt)− bonusτt(a∗) + βt‖a∗‖Σ̃−1τt − 〈aτt , θ ∗〉 ≤ bonusτt(aτt)− bonusτt(a∗) + βτt‖a∗‖Σ̃−1τt + βτt‖aτt‖Σ̃−1τt
≤ ( β √ 8 log ( 2AT
δ
) + βτt ) ‖aτt‖Σ̃−1τt + ( βt − β √ π log 2
2
) ‖a∗‖Σ̃−1τt
≤ ( β √ 8 log ( 2AT
δ
) + βτt ) ‖at‖Σ̃−1t det(Σ̃t)
det(Σ̃τt) +
( βt − β √ π log 2
2
) ‖a∗‖Σ̃−1τt
≤ 2e ( β √ 8 log ( 2AT
δ
) + βτt ) ‖at‖Σ̃−1t + ( βt − β √ π log 2
2
) ‖a∗‖Σ̃−1τt
where the first inequality comes from the validity of the confidence bound for a∗, the second from the fact that aτt = arg maxa 〈 a, θ̂τt 〉 + bonusτt(a), the third from the validity of the confidence bound
for aτt , the fourth follows from Lemma 8, the fifth follows from Lemma 12 Abbasi-Yadkori et al. (2011) and lastly the sixth follows from Lemma 10.
Setting δt = δ/T we have βτt ≤ β √ π log 2 2 , therefore,
regrett ≤ 2e
(√ 8 log ( 2AT
δ
) + √ π log 2
2
) β‖at‖Σ̃−1t .
Using the above, we have
R = T∑ t=1 rt ≤ √√√√T T∑ t=1 r2t ≤ 2e (√ 8 log ( 2AT δ ) + √ π log 2 2 ) β √ 2T log(det(Σ̃T )λ−d)
≤ 2e (√ 8 log ( 2AT
δ
) + √ π log 2
2
) β √ 2Td log(1 + TB/λd).
Lastly, we need to bound the number of times we refresh randomness. By Lemma 9, each time we refresh, we increase det(Σ̃t) by a factor of √ 1 + π log 216 log(2AT/δ) . Since det(Σ̃t)/det(λI) is bounded by (1+TB/λd)d, the number of times we refresh is k = O(d log+(TBW/σd) log(AT/δ)).
Formally, k must satisfy (
1 + π log 216 log(2AT/δ)
)k/2 = Θ ( (1 + TB/λd)d ) .

Review summaries:
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.   

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.

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.