mlsanityData to 14 Oct 2026

Volumetric Spanners: an Efficient Exploration Basis for Learning

arXiv 1312.6214 ↗First posted 21 Dec 2013cs.LG cs.AI cs.DScited by 24

Not on the map. Why?

Abstract (arXiv)

Numerous machine learning problems require an exploration basis - a mechanism to explore the action space. We define a novel geometric notion of exploration basis with low variance, called volumetric spanners, and give efficient algorithms to construct such a basis. We show how efficient volumetric spanners give rise to the first efficient and optimal regret algorithm for bandit linear optimization over general convex sets. Previously such results were known only for specific convex sets, or under special conditions such as the existence of an efficient self-concordant barrier for the underlying set.

Key facts. Cited by 24 papers in the map (data through 14 Oct 2026). First posted on arXiv 21 Dec 2013.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 3; 2022: 4; 2023: 4; 2024: 2; 2025: 5; 2026: 6.

24 papers.

Sort:

  1. 2021Online Learning via Offline Greedy Algorithms: Applications in Market Design and Optimizationcited by 40
  2. 2022Contextual Bandits with Large Action Spaces: Made Practicalcited by 33
  3. 2022Contexts can be Cheap: Solving Stochastic Contextual Bandits with Linear Bandit Algorithmscited by 19
  4. 2023Bayesian Design Principles for Frequentist Sequential Learningcited by 18
  5. 2023A Unified Analysis of Nonstochastic Delayed Feedback for Combinatorial Semi-Bandits, Linear Bandits, and MDPscited by 15
  6. 2023Exploration via linearly perturbed loss minimisationcited by 13
  7. 2021Online Markov Decision Processes with Aggregate Bandit Feedbackcited by 10
  8. 2022Fast online inference for nonlinear contextual bandit based on Generative Adversarial Networkcited by 7
  9. 2024Fast John Ellipsoid Computation with Differential Privacy Optimizationcited by 7
  10. 2025Contextual Linear Bandits with Delay as Payoffcited by 7
  11. 2025Efficient Near-Optimal Algorithm for Online Shortest Paths in Directed Acyclic Graphs with Bandit Feedback Against Adaptive Adversariescited by 6
  12. 2022Contextual Pandora's Boxcited by 5
12 more
  1. 2023Tight Bounds for Volumetric Spanners and Applicationscited by 4
  2. 2025From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewardscited by 4
  3. 2026Efficient Uncoupled Learning Dynamics with tildeO!left(T-1/4right) Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedbackcited by 4
  4. 2026Swap Regret Minimization Through Response-Based Approachabilitycited by 2
  5. 2025Self-Concordant Perturbations for Linear Banditscited by 1
  6. 2021Towards the D-Optimal Online Experiment Design for Recommender Selectioncited by 0
  7. 2024Is Offline Decision Making Possible with Only Few Samples? Reliable Decisions in Data-Starved Bandits via Trust Region Enhancementcited by 0
  8. 2025Bayesian Optimization for Dynamic Pricing and Learningcited by 0
  9. 2026Efficient Swap Regret Minimization in Combinatorial Banditscited by 0
  10. 2026Near-Optimal Regret for Distributed Adversarial Bandits: A Black-Box Approachcited by 0
  11. 2026A Complete Characterization of Learnability for Adversarial Noisy Banditscited by 0
  12. 2026Follow the Perturbed Leader for Linear Bandits: √T Regret over General Convex Setscited by 0