mlsanityData to 14 Oct 2026

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

arXiv 2506.01250 ↗First posted 2 Jun 2025cs.LG stat.MLcited by 2

Not on the map. Why?

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.

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

24 of 39 references.

References · 24

  1. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,621
  2. 2019Generalization Bounds of Stochastic Gradient Descent for Wide and Deep Neural Networkscited by 222
  3. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  4. 2020Neural Thompson Samplingcited by 128
  5. 2020Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mappingcited by 102
  6. 2015Contextual Dueling Banditscited by 101
  7. 2020Neural Contextual Bandits with Deep Representation and Shallow Explorationcited by 71
  8. 2019Randomized Exploration in Generalized Linear Banditscited by 70
  9. 2022Computationally Efficient Horizon-Free Reinforcement Learning for Linear Mixture MDPscited by 52
  10. 2021Improved Variance-Aware Confidence Sets for Linear Bandits and Linear Mixture MDPcited by 45
  11. 2021EE-Net: Exploitation-Exploration Neural Networks in Contextual Banditscited by 44
  12. 2021Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPscited by 44
12 more
  1. 2023Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiencycited by 40
  2. 2022Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Modelscited by 37
  3. 2020Adversarial Dueling Banditscited by 33
  4. 2022Horizon-Free Reinforcement Learning in Polynomial Time: the Power of Stationary Policiescited by 27
  5. 2024Feel-Good Thompson Sampling for Contextual Dueling Banditscited by 27
  6. 2023Variance-Aware Regret Bounds for Stochastic Contextual Dueling Banditscited by 22
  7. 2019Old Dog Learns New Tricks: Randomized UCB for Bandit Problemscited by 21
  8. 2022Federated Neural Banditscited by 17
  9. 2023Combinatorial Neural Banditscited by 16
  10. 2023Contextual Bandits with Online Neural Regressioncited by 7
  11. 2024Variance-Aware Linear UCB with Deep Representation for Neural Contextual Banditscited by 3
  12. 2016Regret Bounds for Non-decomposable Metrics with Missing Labelscited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Learning to Attack: A Bandit Approach to Adversarial Context Poisoningcited by 0
  2. 2026Robust Linear Dueling Bandits with Post-serving Context under Unknown Delays and Adversarial Corruptionscited by 0