# Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits

arXiv: https://arxiv.org/abs/1503.05087 · HTML: https://mlsanity.com/paper/1503.05087/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Mar 2015.

## Built on by (most cited first, 16 of 16)

- [Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedback](https://mlsanity.com/paper/2205.13451/) (2022)
- [Best-of-Both-Worlds Algorithms for Linear Contextual Bandits](https://mlsanity.com/paper/2312.15433/) (2023)
- [Matroid Semi-Bandits in Sublinear Time](https://mlsanity.com/paper/2405.17968/) (2024)
- [Optimism in the Face of Ambiguity Principle for Multi-Armed Bandits](https://mlsanity.com/paper/2409.20440/) (2024)
- [Revisiting Follow-the-Perturbed-Leader with Unbounded Perturbations in Bandit Problems](https://mlsanity.com/paper/2508.18604/) (2025)
- [Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problems](https://mlsanity.com/paper/2504.07307/) (2025)
- [Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Bandits](https://mlsanity.com/paper/2508.18768/) (2025)
- [Bandit-Driven Batch Selection for Robust Learning under Label Noise](https://mlsanity.com/paper/2311.00096/) (2023)
- [Efficient and Optimal No-Regret Caching under Partial Observation](https://mlsanity.com/paper/2503.02758/) (2025)
- [Faster Rates for Private Adversarial Bandits](https://mlsanity.com/paper/2505.21790/) (2025)
- [Note on Follow-the-Perturbed-Leader in Combinatorial Semi-Bandit Problems](https://mlsanity.com/paper/2506.12490/) (2025)
- [Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicality](https://mlsanity.com/paper/2510.12152/) (2025)
- [Adaptive Learning Rates with Surrogate Probability for Follow-the-Perturbed-Leader](https://mlsanity.com/paper/2606.06043/) (2026)
- [Bandits with Single-Peaked Preferences and Limited Resources](https://mlsanity.com/paper/2510.09425/) (2025)
- [Offline Local Search for Online Stochastic Bandits](https://mlsanity.com/paper/2604.09423/) (2026)
- [Follow the Perturbed Leader for Linear Bandits: √T Regret over General Convex Sets](https://mlsanity.com/paper/2610.17818/) (2026)

## Abstract (arXiv)

We propose a sample-efficient alternative for importance weighting for situations where one only has sample access to the probability distribution that generates the observations. Our new method, called Geometric Resampling (GR), is described and analyzed in the context of online combinatorial optimization under semi-bandit feedback, where a learner sequentially selects its actions from a combinatorial decision set so as to minimize its cumulative loss. In particular, we show that the well-known Follow-the-Perturbed-Leader (FPL) prediction method coupled with Geometric Resampling yields the first computationally efficient reduction from offline to online optimization in this setting. We provide a thorough theoretical analysis for the resulting algorithm, showing that its performance is on par with previous, inefficient solutions. Our main contribution is showing that, despite the relatively large variance induced by the GR procedure, our performance guarantees hold with high probability rather than only in expectation. As a side result, we also improve the best known regret bounds for FPL in online combinatorial optimization with full feedback, closing the perceived performance gap between FPL and exponential weights in this setting.