# Anti-Concentrated Confidence Bonuses for Scalable Exploration

arXiv: https://arxiv.org/abs/2110.11202 · HTML: https://mlsanity.com/paper/2110.11202/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 56 references that are in the map.
- First posted on arXiv 21 Oct 2021.

## Builds on (most cited first, 30 of 30)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Continuous control with deep reinforcement learning](https://mlsanity.com/paper/1509.02971/) (2015)
- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [Deep Bayesian Active Learning with Image Data](https://mlsanity.com/paper/1703.02910/) (2017)
- [Unifying Count-Based Exploration and Intrinsic Motivation](https://mlsanity.com/paper/1606.01868/) (2016)
- [Deep Batch Active Learning by Diverse, Uncertain Gradient Lower Bounds](https://mlsanity.com/paper/1906.03671/) (2019)
- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [Introduction to Multi-Armed Bandits](https://mlsanity.com/paper/1904.07272/) (2019)
- [#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/1611.04717/) (2016)
- [Large-Scale Study of Curiosity-Driven Learning](https://mlsanity.com/paper/1808.04355/) (2018)
- [Variational Intrinsic Control](https://mlsanity.com/paper/1611.07507/) (2016)
- [Self-Supervised Exploration via Disagreement](https://mlsanity.com/paper/1906.04161/) (2019)
- [Count-Based Exploration with Neural Density Models](https://mlsanity.com/paper/1703.01310/) (2017)
- [(More) Efficient Reinforcement Learning via Posterior Sampling](https://mlsanity.com/paper/1306.0940/) (2013)
- [Incentivizing Exploration In Reinforcement Learning With Deep Predictive Models](https://mlsanity.com/paper/1507.00814/) (2015)
- [Gone Fishing: Neural Active Learning with Fisher Embeddings](https://mlsanity.com/paper/2106.09675/) (2021)
- [Scalable Generalized Linear Bandits: Online Computation and Hashing](https://mlsanity.com/paper/1706.00136/) (2017)
- [Ensemble Sampling](https://mlsanity.com/paper/1705.07347/) (2017)
- [Model-Predictive Policy Learning with Uncertainty Regularization for Driving in Dense Traffic](https://mlsanity.com/paper/1901.02705/) (2019)
- [Count-Based Exploration in Feature Space for Reinforcement Learning](https://mlsanity.com/paper/1706.08090/) (2017)
- [Randomized Exploration for Reinforcement Learning with General Value Function Approximation](https://mlsanity.com/paper/2106.07841/) (2021)
- [An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling](https://mlsanity.com/paper/2006.04012/) (2020)
- [Perturbed-History Exploration in Stochastic Linear Bandits](https://mlsanity.com/paper/1903.09132/) (2019)
- [Principled Exploration via Optimistic Bootstrapping and Backward Induction](https://mlsanity.com/paper/2105.06022/) (2021)
- [Convergence Rates of Active Learning for Maximum Likelihood Estimation](https://mlsanity.com/paper/1506.02348/) (2015)
- [The Elliptical Potential Lemma Revisited](https://mlsanity.com/paper/2010.10182/) (2020)
- [Deep Neural Linear Bandits: Overcoming Catastrophic Forgetting through Likelihood Matching](https://mlsanity.com/paper/1901.08612/) (2019)
- [Perturbed-History Exploration in Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/1902.10089/) (2019)
- [Online Limited Memory Neural-Linear Bandits with Likelihood Matching](https://mlsanity.com/paper/2102.03799/) (2021)

## Built on by (most cited first, 7 of 7)

- [Exploration via Elliptical Episodic Bonuses](https://mlsanity.com/paper/2210.05805/) (2022)
- [An Analysis of Ensemble Sampling](https://mlsanity.com/paper/2203.01303/) (2022)
- [Sampling-based inference for large linear models, with application to linearised Laplace](https://mlsanity.com/paper/2210.04994/) (2022)
- [Representation-Based Exploration for Language Models: From Test-Time to Post-Training](https://mlsanity.com/paper/2510.11686/) (2025)
- [Exploration via Planning for Information about the Optimal Trajectory](https://mlsanity.com/paper/2210.04642/) (2022)
- [CAE: Repurposing the Critic as an Explorer in Deep Reinforcement Learning](https://mlsanity.com/paper/2503.18980/) (2025)
- [Value Bonuses using Ensemble Errors for Exploration in Reinforcement Learning](https://mlsanity.com/paper/2602.12375/) (2026)

## Abstract (arXiv)

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 tilde O(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.