# CORe: Capitalizing On Rewards in Bandit Exploration

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

## Key facts

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

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

- [Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling](https://mlsanity.com/paper/1802.09127/) (2018)
- [Cascading Bandits: Learning to Rank in the Cascade Model](https://mlsanity.com/paper/1502.02763/) (2015)
- [Ensemble Sampling](https://mlsanity.com/paper/1705.07347/) (2017)
- [Bootstrapped Thompson Sampling and Deep Exploration](https://mlsanity.com/paper/1507.00300/) (2015)
- [Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits](https://mlsanity.com/paper/1811.05154/) (2018)
- [TopRank: A practical algorithm for online stochastic ranking](https://mlsanity.com/paper/1806.02248/) (2018)
- [Perturbed-History Exploration in Stochastic Linear Bandits](https://mlsanity.com/paper/1903.09132/) (2019)
- [Online Stochastic Linear Optimization under One-bit Feedback](https://mlsanity.com/paper/1509.07728/) (2015)
- [Online Learning to Rank in Stochastic Click Models](https://mlsanity.com/paper/1703.02527/) (2017)
- [Old Dog Learns New Tricks: Randomized UCB for Bandit Problems](https://mlsanity.com/paper/1910.04928/) (2019)
- [Thompson sampling with the online bootstrap](https://mlsanity.com/paper/1410.4009/) (2014)
- [Perturbed-History Exploration in Stochastic Multi-Armed Bandits](https://mlsanity.com/paper/1902.10089/) (2019)
- [On the Optimality of Perturbations in Stochastic and Adversarial Multi-armed Bandit Problems](https://mlsanity.com/paper/1902.00610/) (2019)
- [New Insights into Bootstrapping for Bandits](https://mlsanity.com/paper/1805.09793/) (2018)

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

- [IMO3: Interactive Multi-Objective Off-Policy Optimization](https://mlsanity.com/paper/2201.09798/) (2022)

## Abstract (arXiv)

We propose a bandit algorithm that explores purely by randomizing its past observations. In particular, the sufficient optimism in the mean reward estimates is achieved by exploiting the variance in the past observed rewards. We name the algorithm Capitalizing On Rewards (CORe). The algorithm is general and can be easily applied to different bandit settings. The main benefit of CORe is that its exploration is fully data-dependent. It does not rely on any external noise and adapts to different problems without parameter tuning. We derive a tilde O(d√nlog K) gap-free bound on the n-round regret of CORe in a stochastic linear bandit, where d is the number of features and K is the number of arms. Extensive empirical evaluation on multiple synthetic and real-world problems demonstrates the effectiveness of CORe.