# An efficient algorithm for learning with semi-bandit feedback

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 May 2013.

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

- [Optimistic Whittle Index Policy: Online Learning for Restless Bandits](https://mlsanity.com/paper/2205.15372/) (2022)
- [Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedback](https://mlsanity.com/paper/2205.13451/) (2022)
- [Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Games](https://mlsanity.com/paper/2103.04546/) (2021)
- [Best-of-Both-Worlds Algorithms for Linear Contextual Bandits](https://mlsanity.com/paper/2312.15433/) (2023)
- [Outcome-Based Online Reinforcement Learning: Algorithms and Fundamental Limits](https://mlsanity.com/paper/2505.20268/) (2025)
- [Individually Fair Learning with One-Sided Feedback](https://mlsanity.com/paper/2206.04475/) (2022)
- [Efficient learning by implicit exploration in bandit problems with side observations](https://mlsanity.com/paper/2604.24555/) (2026)
- [Optimism in the Face of Ambiguity Principle for Multi-Armed Bandits](https://mlsanity.com/paper/2409.20440/) (2024)
- [Simultaneously Learning Stochastic and Adversarial Bandits under the Position-Based Model](https://mlsanity.com/paper/2207.05437/) (2022)
- [Learning from Snapshots of Discrete and Continuous Data Streams](https://mlsanity.com/paper/2412.06079/) (2024)
- [Online combinatorial optimization with stochastic decision sets and adversarial losses](https://mlsanity.com/paper/2604.25269/) (2026)
- [Discrete Choice Multi-Armed Bandits](https://mlsanity.com/paper/2310.00562/) (2023)
- [Online learning with ErdHos-R'enyi side-observation graphs](https://mlsanity.com/paper/2604.25271/) (2026)
- [Adversaries in Online Learning Revisited: with applications in Robust Optimization and Adversarial training](https://mlsanity.com/paper/2101.11443/) (2021)
- [Harnessing Heterogeneity: Learning from Decomposed Feedback in Bayesian Modeling](https://mlsanity.com/paper/2107.03003/) (2021)
- [Trading Off Resource Budgets for Improved Regret Bounds](https://mlsanity.com/paper/2210.05789/) (2022)
- [BORA: Bayesian Optimization for Resource Allocation](https://mlsanity.com/paper/2210.05977/) (2022)
- [Beyond Softmax: A New Perspective on Gradient Bandits](https://mlsanity.com/paper/2510.03979/) (2025)
- [Best-of-Both Worlds for linear contextual bandits with paid observations](https://mlsanity.com/paper/2510.07424/) (2025)
- [Oracle-Efficient Combinatorial Semi-Bandits](https://mlsanity.com/paper/2510.21431/) (2025)
- [Bandits on graphs and structures](https://mlsanity.com/paper/2605.03493/) (2026)

## Abstract (arXiv)

We consider the problem of online combinatorial optimization under semi-bandit feedback. The goal of the learner is to sequentially select its actions from a combinatorial decision set so as to minimize its cumulative loss. We propose a learning algorithm for this problem based on combining the Follow-the-Perturbed-Leader (FPL) prediction method with a novel loss estimation procedure called Geometric Resampling (GR). Contrary to previous solutions, the resulting algorithm can be efficiently implemented for any decision set where efficient offline combinatorial optimization is possible at all. Assuming that the elements of the decision set can be described with d-dimensional binary vectors with at most m non-zero entries, we show that the expected regret of our algorithm after T rounds is O(m sqrt(dT log d)). As a side result, we also improve the best known regret bounds for FPL in the full information setting to O(m^(3/2) sqrt(T log d)), gaining a factor of sqrt(d/m) over previous bounds for this algorithm.