Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Infrequent Exploration in Linear 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.
Proposes INFEX, a linear bandit framework that runs a base fully-adaptive policy (LinUCB or LinTS) only on a predetermined schedule and acts greedily otherwise, proving polylogarithmic instance-dependent regret when exploration count grows faster than log t.
Problem
Linear bandits with fixed arm features: fully adaptive exploration (UCB, TS) explores every step, which is costly or unsafe, while greedy policies incur linear regret without contextual diversity. The question is how infrequent exploration affects regret.
Approach
Interleave a scheduled base exploratory algorithm with ridge-greedy actions; show that if the number of exploratory steps is omega(log t), the regret matches the base algorithm's instance-dependent order, via the argument that optimal-arm selection frequency makes greedy estimation of x* accurate. A matching lower bound shows omega(log t) is necessary for predetermined schedules.
Key results
- INFEX with LinTS base and fixed period m in {5,20,100} reduces regret significantly relative to LinTS in simulations, and reduces computation time for any m.
- Theorem gives regret of INFEX(Alg, T_e) as Rcal_Alg(f(T)) + constant + O((log T + d log log T + d log(d/Delta))^2/Delta) when f(t)=omega(log t).
- A new instance-dependent regret bound for LinTS of order min{d log(dT/delta), log(KT/delta)}(alpha_T+log(1/delta))^2/Delta is derived.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use INFEX with LinTS exploration every 5, 20, or 100 steps instead of fully adaptive LinTS | LinTS · Linear bandit simulations (d=10, T=10000; K=10, 100, 1000) | cumulative regret | Helped |
| Use INFEX with LinUCB exploration every 5 steps instead of fully adaptive LinUCB | LinUCB · Linear bandit simulations (d=10, T=10000; K=10, 100, 1000) | cumulative regret | Helped |
| Use INFEX with LinTS exploration every 5, 20, or 100 steps | LinTS · Linear bandit simulations (d=10, T=10000; K=10, 100, 1000) | computation time | Helped |
| Use INFEX with LinUCB exploration every 5, 20, or 100 steps | LinUCB · Linear bandit simulations (d=10, T=10000; K=10, 100, 1000) | computation time | Helped |
| Reduce predetermined exploration below the ω(log t) frequency threshold | INFEX · Linear bandits | expected cumulative regret: T^{1 - ε} | Hurt |
Surprising findings
- Certain exploration schedules improve total regret over the fully adaptive base algorithm, particularly for LinTS.
- Exploring with period 5 (80% greedy) for LinUCB also improves regret in the experiments.
Limitations
- Analysis is for instance-dependent bounds with fixed finite arm sets and a unique optimal arm; minimax O(sqrt(T)) guarantees are conjectured but not shown.
- Lower bound applies only to predetermined schedules; adaptive schedules may avoid the omega(log t) requirement.
- Constant term depends exponentially on d/Delta for very sparse schedules, hurting finite-time performance.
Experimental setup
Benchmarks: synthetic linear bandit instances (d=10, T=10000, K in {10,100,1000})
Metrics: cumulative regret computation time
Baselines: LinUCB LinTS greedy OLSBandit epsilon-greedy
Builds on: LinUCB LinTS OFUL OLSBandit
Closest papers by meaning
- Greedy Algorithms for Structured Bandits: A Sharp Characterization of Asymptotic Success / Failure (NeurIPS 2025 · similarity 0.90)
- Feasible Action Search for Bandit Linear Programs via Thompson Sampling (ICML 2025 · similarity 0.89)
- Geometry Meets Incentives: Sample-Efficient Incentivized Exploration with Linear Contexts (NeurIPS 2025 · similarity 0.89)
- Active Context Selection Improves Simple Regret in Contextual Bandits (NeurIPS 2026 · similarity 0.88)
- Forced Exploration in Bandit Problems (AAAI 2024 · similarity 0.88)
- FraPPE: Fast and Efficient Preference-Based Pure Exploration (NeurIPS 2025 · similarity 0.88)
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.