Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Offline-to-Online Hyperparameter Transfer for Stochastic Bandits
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that offline bandit runs on tasks drawn from an unknown distribution can be used to learn near-optimal exploration hyperparameters (UCB, LinUCB) and GP-UCB noise parameters, with inter-task and intra-task sample complexity bounds via derandomized dual complexity.
Problem
Choosing hyperparameters such as UCB's exploration parameter or GP-UCB's noise variance is critical but hard; per-instance optimal tuning online is information-theoretically impossible, so the paper asks how to transfer hyperparameters from offline data on similar bandit tasks.
Approach
Frames hyperparameter tuning as data-driven algorithm configuration over a task distribution; defines a derandomized dual complexity (number of piecewise-constant pieces of the loss in the hyperparameter) that yields uniform-convergence sample complexity, and shows it scales as O(n log T) for UCB, O(T log n) for LinUCB and GP-UCB, enabling ERM over offline tasks with critical-point computation.
Key results
- Learned-hyperparameter UCB significantly outperforms Corral and Corral-stochastic on CIFAR-10 and CIFAR-100 learning-rate tuning over 10^6 steps.
- On the challenging synthetic Bernoulli two-armed task (means 0.5 vs ~0.51), the approach beats corralling over a 2x10^6 step horizon.
- Theory gives log Q_D = O(n log T) for UCB, O(T log n) for LinUCB and GP-UCB noise tuning, implying inter-task sample complexity Õ(n log T / ε^2) and intra-task complexity O(nT) for UCB.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| transfer the UCB exploration parameter using offline tasks instead of using corralling | UCB · CIFAR-10 | regret | Helped |
| transfer the UCB exploration parameter using offline tasks instead of using corralling | UCB · CIFAR-100 | regret | Helped |
| transfer the UCB exploration parameter using offline tasks instead of using corralling | UCB · Synthetic two-armed Bernoulli bandits | regret | Helped |
| transfer the UCB exploration parameter using offline tasks instead of using corralling | UCB · Two-armed uniform-reward bandits | regret | Helped |
| transfer the UCB exploration parameter using offline tasks instead of using corralling | UCB · Two-armed Gaussian-reward bandits | regret | Helped |
| use a data-dependent exploration parameter rather than the theory-suggested α=1 | UCB · Synthetic bandits and CIFAR-10/CIFAR-100 | regret | Helped |
Surprising findings
- Information-theoretically, consistent per-instance tuning of the UCB exploration parameter is impossible: any meta-algorithm suffers a strictly suboptimal regret ratio on some Gaussian bandit instance.
- The best UCB exploration parameter on typical data is often below 1, where classic analysis does not give regret guarantees and theory-suggested alpha=1 is suboptimal.
Limitations
- Intra-task complexity bounds may be improvable with more careful arguments.
- Offline data collection policy is not optimized; how to strategically collect offline data is left open.
- Analysis restricted to UCB-style algorithms (UCB, LinUCB, GP-UCB).
Experimental setup
Datasets: CIFAR-10 CIFAR-100 synthetic two-armed Bernoulli, uniform and Gaussian bandits
Benchmarks: CIFAR-10 learning-rate bandit CIFAR-100 learning-rate bandit synthetic two-armed bandits
Metrics: cumulative regret standard deviation over 5 runs
Baselines: Corral Corral-stochastic
Builds on: UCB LinUCB GP-UCB Corral Corral-stochastic
Closest papers by meaning
- Leveraging (Biased) Information: Multi-armed Bandits with Offline Data (ICML 2024 · similarity 0.88)
- Direction-Aware Offline-to-Online Learning in Linear Contextual Bandits (NeurIPS 2026 · similarity 0.88)
- Leveraging Offline Data in Linear Latent Contextual Bandits (ICML 2025 · similarity 0.86)
- Robustly Improving Bandit Algorithms with Confounded and Selection Biased Offline Data: A Causal Approach (AAAI 2024 · similarity 0.86)
- Small steps no more: Global convergence of stochastic gradient bandits for arbitrary learning rates (NeurIPS 2024 · similarity 0.86)
- Regret minimization in Linear Bandits with offline data via extended D-optimal exploration. (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.