# Fast online inference for nonlinear contextual bandit based on Generative Adversarial Network

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 53 references that are in the map.
- First posted on arXiv 17 Feb 2022.

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

- [Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning](https://mlsanity.com/paper/1506.02142/) (2015)
- [Deep Learning Face Attributes in the Wild](https://mlsanity.com/paper/1411.7766/) (2014)
- [Variational Inference: A Review for Statisticians](https://mlsanity.com/paper/1601.00670/) (2016)
- [Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs](https://mlsanity.com/paper/1603.09320/) (2016)
- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [Stochastic Gradient Descent as Approximate Bayesian Inference](https://mlsanity.com/paper/1704.04289/) (2017)
- [Concrete Dropout](https://mlsanity.com/paper/1705.07832/) (2017)
- [An Information-Theoretic Analysis of Thompson Sampling](https://mlsanity.com/paper/1403.5341/) (2014)
- [Finite-Time Analysis of Kernelised Contextual Bandits](https://mlsanity.com/paper/1309.6869/) (2013)
- [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)
- [The Parallel Knowledge Gradient Method for Batch Bayesian Optimization](https://mlsanity.com/paper/1606.04414/) (2016)
- [Efficient Exploration through Bayesian Deep Q-Networks](https://mlsanity.com/paper/1802.04412/) (2018)
- [Scalable Generalized Linear Bandits: Online Computation and Hashing](https://mlsanity.com/paper/1706.00136/) (2017)
- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [Minimal Exploration in Structured Stochastic Bandits](https://mlsanity.com/paper/1711.00400/) (2017)
- [BBQ-Networks: Efficient Exploration in Deep Reinforcement Learning for Task-Oriented Dialogue Systems](https://mlsanity.com/paper/1711.05715/) (2017)
- [Volumetric Spanners: an Efficient Exploration Basis for Learning](https://mlsanity.com/paper/1312.6214/) (2013)
- [A Neural Networks Committee for the Contextual Bandit Problem](https://mlsanity.com/paper/1409.8191/) (2014)
- [Deep Bayesian Bandits: Exploring in Online Personalized Recommendations](https://mlsanity.com/paper/2008.00727/) (2020)
- [Deep Neural Linear Bandits: Overcoming Catastrophic Forgetting through Likelihood Matching](https://mlsanity.com/paper/1901.08612/) (2019)
- [Variational inference for the multi-armed contextual bandit](https://mlsanity.com/paper/1709.03163/) (2017)
- [Thompson Sampling with Approximate Inference](https://mlsanity.com/paper/1908.04970/) (2019)

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

- [Code Less, Align More: Efficient LLM Fine-tuning for Code Generation with Data Pruning](https://mlsanity.com/paper/2407.05040/) (2024)
- [lil'HDoC: An Algorithm for Good Arm Identification under Small Threshold Gap](https://mlsanity.com/paper/2401.15879/) (2024)
- [Enhance the Robustness of Text-Centric Multimodal Alignments](https://mlsanity.com/paper/2407.05036/) (2024)
- [Uncertainty Profiles for LLMs: Uncertainty Source Decomposition and Adaptive Model-Metric Selection](https://mlsanity.com/paper/2505.07309/) (2025)
- [LinearAPT: An Adaptive Algorithm for the Fixed-Budget Thresholding Linear Bandit Problem](https://mlsanity.com/paper/2403.06230/) (2024)
- [Multimodal Chip Physical Design Engineer Assistant](https://mlsanity.com/paper/2510.15872/) (2025)
- [PARWiS: Winner determination under shoestring budgets using active pairwise comparisons](https://mlsanity.com/paper/2603.01171/) (2026)

## Abstract (arXiv)

This work addresses the efficiency concern on inferring a nonlinear contextual bandit when the number of arms n is very large. We propose a neural bandit model with an end-to-end training process to efficiently perform bandit algorithms such as Thompson Sampling and UCB during inference. We advance state-of-the-art time complexity to O(log n) with approximate Bayesian inference, neural random feature mapping, approximate global maxima and approximate nearest neighbor search. We further propose a generative adversarial network to shift the bottleneck of maximizing the objective for selecting optimal arms from inference time to training time, enjoying significant speedup with additional advantage of enabling batch and parallel processing. %The generative model can inference an approximate argmax of the posterior sampling in logarithmic time complexity with the help of approximate nearest neighbor search. Extensive experiments on classification and recommendation tasks demonstrate order-of-magnitude improvement in inference time no significant degradation on the performance.