# Neural Variance-aware Dueling Bandits with Deep Representation and Shallow Exploration

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 39 references that are in the map.
- First posted on arXiv 2 Jun 2025.

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

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networks](https://mlsanity.com/paper/1905.13210/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Neural Thompson Sampling](https://mlsanity.com/paper/2010.00827/) (2020)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Contextual Dueling Bandits](https://mlsanity.com/paper/1502.06362/) (2015)
- [Neural Contextual Bandits with Deep Representation and Shallow Exploration](https://mlsanity.com/paper/2012.01780/) (2020)
- [Randomized Exploration in Generalized Linear Bandits](https://mlsanity.com/paper/1906.08947/) (2019)
- [Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPs](https://mlsanity.com/paper/2205.11507/) (2022)
- [Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDP](https://mlsanity.com/paper/2101.12745/) (2021)
- [EE-Net: Exploitation-Exploration Neural Networks in Contextual Bandits](https://mlsanity.com/paper/2110.03177/) (2021)
- [Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPs](https://mlsanity.com/paper/2111.03289/) (2021)
- [Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency](https://mlsanity.com/paper/2302.10371/) (2023)
- [Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Models](https://mlsanity.com/paper/2202.04593/) (2022)
- [Adversarial Dueling Bandits](https://mlsanity.com/paper/2010.14563/) (2020)
- [Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policies](https://mlsanity.com/paper/2203.12922/) (2022)
- [Feel-Good Thompson Sampling for Contextual Dueling Bandits](https://mlsanity.com/paper/2404.06013/) (2024)
- [Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits](https://mlsanity.com/paper/2310.00968/) (2023)
- [Old Dog Learns New Tricks: Randomized UCB for Bandit Problems](https://mlsanity.com/paper/1910.04928/) (2019)
- [Federated Neural Bandits](https://mlsanity.com/paper/2205.14309/) (2022)
- [Combinatorial Neural Bandits](https://mlsanity.com/paper/2306.00242/) (2023)
- [Contextual Bandits with Online Neural Regression](https://mlsanity.com/paper/2312.07145/) (2023)
- [Variance-Aware Linear UCB with Deep Representation for Neural Contextual Bandits](https://mlsanity.com/paper/2411.05979/) (2024)
- [Regret Bounds for Non-decomposable Metrics with Missing Labels](https://mlsanity.com/paper/1606.02077/) (2016)

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

- [Learning to Attack: A Bandit Approach to Adversarial Context Poisoning](https://mlsanity.com/paper/2603.00567/) (2026)
- [Robust Linear Dueling Bandits with Post-serving Context under Unknown Delays and Adversarial Corruptions](https://mlsanity.com/paper/2605.01752/) (2026)

## Abstract (arXiv)

We introduce the first variance-aware algorithms for contextual dueling bandits that leverage shallow exploration strategies with neural networks for nonlinear utility approximation. A key theoretical challenge is the absence of a closed-form estimator, which led prior work to require an extremely large network width m (i.e., m = widetildeOmega(T14)). We address this constraint with a novel analytical approach that combines iterative self-improvement with spectral analysis. Our analysis significantly reduces the network width requirement to m = widetildeOmega(T6), and shows that our algorithms achieve a sublinear regret of widetildeO(d√sumt=1T σt2 + √dT) under both UCB and TS frameworks. Empirical results show that the proposed algorithms are not only computationally efficient and exhibit sublinear regret in practical settings, but also achieve state-of-the-art performance on both synthetic and real-world tasks.