Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Matroid Semi-Bandits in Sublinear Time
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 FasterCUCB, a matroid semi-bandit algorithm whose sampling rule runs in time sublinear in the number of arms K by using a (1+epsilon)-approximate maximum-weight base oracle with dynamic data structures and lazy bin reconstruction.
Problem
Matroid semi-bandits require per-round time at least Omega(K) because each round solves a maximum-weight base problem over K arms, which is costly for large K.
Approach
Uses a (1+epsilon)-approximate maximum-weight base oracle whose maintenance is amortized sublinear in K by updating the sorted/binned structure only at sparse update times, with UCB bonuses computed using a slowly changing log-time term, trading off amortized time against regret.
Key results
- Amortized per-round time for uniform matroid with reconstruction at squares of integers is O(D log K + K/sqrt(T)), sublinear in K for T large.
- Choice of theta_t=1/ln t updated at powers of 2 gives amortized time O(ln^4 T + D ln^3 T) in the naive analysis of the bin-based approach.
- Regret analysis of the sampling rule with (1+epsilon)-approximate oracle yields a dependence on gap and the approximation factor via time-varying theta_t.
Limitations
- Provided text is fragmentary with many unfinished notes and TODOs, so the final algorithm and results are not fully specified.
- Analysis of the sublinear regime depends on specific schedules for theta_t and update times.
Experimental setup
Metrics: cumulative regret amortized per-round time complexity
Baselines: CUCB CombCascade CascadeUCB1 GLR-CUCB CUCB-SW
Builds on: CUCB ESCB LUCB
Closest papers by meaning
- Oracle-Efficient Combinatorial Semi-Bandits (NeurIPS 2025 · similarity 0.87)
- Optimal and Efficient Contextual Combinatorial Semi-bandits with General Function Approximation (NeurIPS 2026 · similarity 0.87)
- Adversarial Combinatorial Semi-bandits with Graph Feedback (ICML 2025 · similarity 0.87)
- On Interpolating Experts and Multi-Armed Bandits (ICML 2024 · similarity 0.87)
- Nash Social Welfare for Multi Armed Bandits: Trajectory-wise Expected and High Probability Regret (NeurIPS 2026 · similarity 0.86)
- Geometry-Aware Approaches for Balancing Performance and Theoretical Guarantees in Linear Bandits (ICLR 2025 · 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.