# Output-Weighted Sampling for Multi-Armed Bandits with Extreme Payoffs

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 55 references that are in the map.
- First posted on arXiv 19 Feb 2021.

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

- [Prioritized Experience Replay](https://mlsanity.com/paper/1511.05952/) (2015)
- [Automatic differentiation in machine learning: a survey](https://mlsanity.com/paper/1502.05767/) (2015)
- [Deep Exploration via Bootstrapped DQN](https://mlsanity.com/paper/1602.04621/) (2016)
- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Deep Bayesian Bandits Showdown: An Empirical Comparison of Bayesian Deep Networks for Thompson Sampling](https://mlsanity.com/paper/1802.09127/) (2018)
- [Efficiently Sampling Functions from Gaussian Process Posteriors](https://mlsanity.com/paper/2002.09309/) (2020)
- [Efficient Exploration through Bayesian Deep Q-Networks](https://mlsanity.com/paper/1802.04412/) (2018)
- [Improving the Expected Improvement Algorithm](https://mlsanity.com/paper/1705.10033/) (2017)
- [A sequential sampling strategy for extreme event statistics in nonlinear dynamical systems](https://mlsanity.com/paper/1804.07240/) (2018)
- [Multi-fidelity classification using Gaussian processes: accelerating the prediction of large-scale computational models](https://mlsanity.com/paper/1905.03406/) (2019)
- [Thompson Sampling is Asymptotically Optimal in General Environments](https://mlsanity.com/paper/1602.07905/) (2016)
- [Output-weighted optimal sampling for Bayesian regression and rare event statistics using few samples](https://mlsanity.com/paper/1907.07552/) (2019)
- [Informative Path Planning for Extreme Anomaly Detection in Environment Exploration and Monitoring](https://mlsanity.com/paper/2005.10040/) (2020)
- [Adversarial Learning of a Sampler Based on an Unnormalized Distribution](https://mlsanity.com/paper/1901.00612/) (2019)
- [Output-Weighted Optimal Sampling for Bayesian Experimental Design and Uncertainty Quantification](https://mlsanity.com/paper/2006.12394/) (2020)
- [Bayesian Optimization with Output-Weighted Optimal Sampling](https://mlsanity.com/paper/2004.10599/) (2020)

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

- [Scalable Uncertainty Quantification for Deep Operator Networks using Randomized Priors](https://mlsanity.com/paper/2203.03048/) (2022)
- [Discovering and forecasting extreme events via active learning in neural operators](https://mlsanity.com/paper/2204.02488/) (2022)
- [Evaluation of machine learning architectures on the quantification of epistemic and aleatoric uncertainties in complex dynamical systems](https://mlsanity.com/paper/2306.15159/) (2023)
- [Active search for Bifurcations](https://mlsanity.com/paper/2406.11141/) (2024)
- [A generalized likelihood-weighted optimal sampling algorithm for rare-event probability quantification](https://mlsanity.com/paper/2310.14457/) (2023)

## Abstract (arXiv)

We present a new type of acquisition functions for online decision making in multi-armed and contextual bandit problems with extreme payoffs. Specifically, we model the payoff function as a Gaussian process and formulate a novel type of upper confidence bound (UCB) acquisition function that guides exploration towards the bandits that are deemed most relevant according to the variability of the observed rewards. This is achieved by computing a tractable likelihood ratio that quantifies the importance of the output relative to the inputs and essentially acts as an textitattention mechanism that promotes exploration of extreme rewards. We demonstrate the benefits of the proposed methodology across several synthetic benchmarks, as well as a realistic example involving noisy sensor network data. Finally, we provide a JAX library for efficient bandit optimization using Gaussian processes.