Research map / Probabilistic and scientific modeling / Bayesian optimization
Sparse Optimistic Information Directed Sampling
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.
Extends optimistic information directed sampling to sparse linear bandits with time- and history-dependent learning rates, yielding worst-case regret that is optimal in both data-rich and data-poor regimes.
Problem
Achieving optimal worst-case (frequentist) regret for stochastic sparse linear bandits simultaneously in the data-rich regime (sqrt(sdT)) and the data-poor regime ((sT)^{2/3}), where prior IDS guarantees were only Bayesian.
Approach
Replaces the Bayesian posterior in sparse IDS with an optimistic posterior whose exploration term uses the agent's own observed gaps and a time- or history-dependent learning rate lambda_t, with a new FTRL-based analysis that handles such rates, plus forerunner policies (FGTS and an exploration mixture) to bound the 2- and 3-information ratios.
Key results
- SOIDS attains worst-case regret min(O(sqrt(sdT log(edT/s))), O((sT)^{2/3} (log(edT/s))^{1/3})), matching the optimal rates in both data-rich and data-poor regimes.
- In synthetic experiments with d in {20,40,100}, T=1000, SOIDS performs competitively with the best baseline in each regime (OTCS for d=20, ESTC for d=100).
- An instance-dependent bound replaces T with cumulative surrogate information ratios, with learning rates that are history-dependent.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SOIDS with a learning rate tuned to adapt across data-rich and data-poor regimes | Sparse linear bandits · Data-rich and data-poor regimes | worst-case regret | Helped |
| Use SOIDS instead of regime-specialized baselines | Sparse linear bandits · d = 20, data-rich regime | cumulative regret | Mixed |
| Use SOIDS instead of regime-specialized baselines | Sparse linear bandits · d = 100, data-poor regime | cumulative regret | Mixed |
Limitations
- Theoretical analysis of the practical approximation to the optimistic posterior is not provided.
- Instance-dependent bound has a worse logarithmic factor power than the minimax bound because decreasing learning rates are required.
- Experiments are limited to a single synthetic setup with T=1000 and 10 repetitions.
Experimental setup
Benchmarks: synthetic sparse linear bandit environments
Metrics: cumulative regret
Baselines: OTCS (online-to-confidence-set) ESTC (Explore the Sparsity Then Commit) LinUCB
Builds on: Information Directed Sampling Optimistic Information Directed Sampling sparse IDS Feel-Good Thompson Sampling Explore the Sparsity Then Commit
Closest papers by meaning
- Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.88)
- Information-Directed Offline-to-Online Reinforcement Learning (NeurIPS 2026 · similarity 0.88)
- Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency (ICML 2024 · similarity 0.88)
- Noise-Adaptive Confidence Sets for Linear Bandits and Application to Bayesian Optimization (ICML 2024 · similarity 0.88)
- Regret minimization in Linear Bandits with offline data via extended D-optimal exploration. (NeurIPS 2026 · similarity 0.87)
- Online Nonsubmodular Optimization with Delayed Feedback in the Bandit Setting (AAAI 2025 · similarity 0.87)
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.