Research map / Bandits and online learning / Contextual bandits and Thompson sampling

Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits

ICLR 2025 · Bandits and online learning › Contextual bandits and Thompson sampling · approach: Linear and generalized linear bandits · 0 citations (OpenAlex)

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 a data-driven geometric bound on the frequentist regret of a family of linear bandit algorithms (POFUL), and uses it to course-correct Thompson sampling and Greedy into minimax-optimal TS-MR and Greedy-MR variants.

Problem

Linear Thompson sampling and Greedy perform well empirically but lack minimax-optimal frequentist regret guarantees; the paper asks whether problematic instances can be detected from data and corrected while keeping empirical performance and computational efficiency.

Approach

A real-time geometric analysis of the d-dimensional confidence ellipsoid yields a computable upper bound on an uncertainty ratio, giving a data-driven regret proxy for POFUL algorithms; when the proxy exceeds a threshold, the algorithm switches to OFUL actions.

Key results

• Course-corrected TS-MR and Greedy-MR achieve regret of order max{mu,2} d sqrt(T), i.e., minimax optimal up to a constant factor, under the stated bound.
• In the prior-mean-mismatch example, LinTS and Greedy incur linear regret while TS-MR and Greedy-MR switch to OFUL and achieve sublinear regret.
• On real OpenML datasets, TS-MR and Greedy-MR retain the empirical performance of LinTS and Greedy while OFUL and TS-Freq perform poorly.

Measured effects reported in the paper

Surprising findings

• Greedy-MR with a tuned threshold can outperform both Greedy and OFUL in the contextual embedding example, not merely interpolating between them.

Limitations

• Theoretical bound for the continuous case is derived for the unit hypersphere action set; the discrete case relies on comparing confidence interval lengths.
• Performance depends on the threshold mu, which is chosen heuristically (recommended range [8,12]).
• Results on the TS/Greedy-MR regret are up to constant factors and rely on high-probability events and sub-Gaussian noise assumptions.

Experimental setup

Datasets: Cardiotocography (OpenML 1466) JapaneseVowels (OpenML 375) Segment (OpenML 36)

Benchmarks: synthetic linear bandit examples (d=50, d=10 prior mismatch) Cardiotocography JapaneseVowels Segment

Metrics: cumulative regret fraction of OFUL actions

Baselines: OFUL LinTS TS-Freq Greedy

Builds on: OFUL linear Thompson sampling elliptical potential lemma TS-Freq

Closest papers by meaning

• Bayesian Regret Minimization in Offline Bandits (ICML 2024 · similarity 0.90)
• Constrained Linear Thompson Sampling (NeurIPS 2025 · similarity 0.90)
• Improved Regret Bounds for Linear Bandits with Heavy-Tailed Rewards (NeurIPS 2025 · similarity 0.89)
• Variance-Aware Feel-Good Thompson Sampling for Contextual Bandits (NeurIPS 2025 · similarity 0.89)
• Regret minimization in Linear Bandits with offline data via extended D-optimal exploration. (NeurIPS 2026 · similarity 0.89)
• Linear Bandits with Partially Observable Features (ICML 2025 · similarity 0.89)