mlsanityData to 7 Oct 2026

First-order regret bounds for combinatorial semi-bandits

arXiv 1502.06354 ↗First posted 23 Feb 2015cs.LG stat.MLcited by 25

Not on the map. Why?

Abstract (arXiv)

We consider the problem of online combinatorial optimization under semi-bandit feedback, where a learner has to repeatedly pick actions from a combinatorial decision set in order to minimize the total losses associated with its decisions. After making each decision, the learner observes the losses associated with its action, but not other losses. For this problem, there are several learning algorithms that guarantee that the learner's expected regret grows as widetildeO(√T) with the number of rounds T. In this paper, we propose an algorithm that improves this scaling to widetildeO(√LT^*), where LT^* is the total loss of the best action. Our algorithm is among the first to achieve such guarantees in a partial-feedback scheme, and the first one to do so in a combinatorial setting.

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). First posted on arXiv 23 Feb 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 2; 2023: 3; 2024: 3; 2025: 8; 2026: 4.

25 papers.

Sort:

By area:

  1. 2021Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimizationcited by 66
  2. 2021Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discriminationcited by 53
  3. 2021First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approachcited by 38
  4. 2023The Benefits of Being Distributional: Small-Loss Bounds for Reinforcement Learningcited by 27
  5. 2023First- and Second-Order Bounds for Adversarial Linear Contextual Banditscited by 19
  6. 2021Nonstochastic Bandits and Experts with Arm-Dependent Delayscited by 18
  7. 2022Follow-the-Perturbed-Leader for Adversarial Markov Decision Processes with Bandit Feedbackcited by 16
  8. 2024Follow-the-Perturbed-Leader with Fr'echet-type Tail Distributions: Optimality in Adversarial Bandits and Best-of-Both-Worldscited by 9
  9. 2024Switching the Loss Reduces the Cost in Batch (Offline) Reinforcement Learningcited by 8
  10. 2023Banker Online Mirror Descent: A Universal Approach for Delayed Online Bandit Learningcited by 7
  11. 2025Offline Learning for Combinatorial Multi-armed Banditscited by 5
  12. 2024Information Capacity Regret Bounds for Bandits with Mediator Feedbackcited by 4
13 more
  1. 2025From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewardscited by 4
  2. 2022Simultaneously Learning Stochastic and Adversarial Bandits under the Position-Based Modelcited by 2
  3. 2025Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problemscited by 2
  4. 2025Data-Dependent Regret Bounds for Constrained MABscited by 2
  5. 2025Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Banditscited by 2
  6. 2026Eluder dimension: localise it!cited by 2
  7. 2021Scale-Free Adversarial Multi-Armed Bandit with Arbitrary Feedback Delayscited by 1
  8. 2025Stochastic Shortest Path with Sparse Adversarial Costscited by 1
  9. 2026The Sample Complexity of Multiclass and Sparse Contextual Banditscited by 1
  10. 2025Note on Follow-the-Perturbed-Leader in Combinatorial Semi-Bandit Problemscited by 0
  11. 2025Multi-Play Combinatorial Semi-Bandit Problemcited by 0
  12. 2026From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Modelcited by 0
  13. 2026Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Banditscited by 0