mlsanityData to 7 Oct 2026

Combinatorial Cascading Bandits

arXiv 1507.04208 ↗First posted 15 Jul 2015cs.LG stat.MLcited by 40

Not on the map. Why?

Abstract (arXiv)

We propose combinatorial cascading bandits, a class of partial monitoring problems where at each step a learning agent chooses a tuple of ground items subject to constraints and receives a reward if and only if the weights of all chosen items are one. The weights of the items are binary, stochastic, and drawn independently of each other. The agent observes the index of the first chosen item whose weight is zero. This observation model arises in network routing, for instance, where the learning agent may only observe the first link in the routing path which is down, and blocks the path. We propose a UCB-like algorithm for solving our problems, CombCascade; and prove gap-dependent and gap-free upper bounds on its n-step regret. Our proofs build on recent work in stochastic combinatorial semi-bandits but also address two novel challenges of our setting, a non-linear reward function and partial observability. We evaluate CombCascade on two real-world problems and show that it performs well even when our modeling assumptions are violated. We also demonstrate that our setting requires a new learning algorithm.

Key facts. Cited by 40 papers in the map (data through 7 Oct 2026). First posted on arXiv 15 Jul 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 11; 2022: 6; 2023: 6; 2024: 8; 2025: 7; 2026: 2.

40 papers.

Sort:

By area:

  1. 2024Cost-Effective Online Multi-LLM Selection with Versatile Reward Modelscited by 36
  2. 2021No Regrets for Learning the Prior in Banditscited by 29
  3. 2021Heterogeneous Multi-player Multi-armed Bandits: Closing the Gap and Generalizationcited by 18
  4. 2023Contextual Combinatorial Bandits with Probabilistically Triggered Armscited by 18
  5. 2022Batch-Size Independent Regret Bounds for Combinatorial Semi-Bandits with Probabilistically Triggered Arms or Independent Armscited by 15
  6. 2021Contextual Recommendations and Low-Regret Cutting-Plane Algorithmscited by 14
  7. 2022Minimax Regret for Cascading Banditscited by 10
  8. 2024Multi-Armed Bandits with Interferencecited by 10
  9. 2024Online Experimental Design With Estimation-Regret Trade-off Under Network Interferencecited by 9
  10. 2024Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyondcited by 7
  11. 2021PairRank: Online Pairwise Learning to Rank by Divide-and-Conquercited by 6
  12. 2022Multiple-Play Stochastic Bandits with Shareable Finite-Capacity Armscited by 6
28 more
  1. 2023Adversarial Attacks on Online Learning to Rank with Click Feedbackcited by 6
  2. 2023Adversarial Attacks on Online Learning to Rank with Stochastic Click Modelscited by 6
  3. 2024Federated Contextual Cascading Bandits with Asynchronous Communication and Heterogeneous Userscited by 6
  4. 2025Offline Learning for Combinatorial Multi-armed Banditscited by 5
  5. 2025Graph-Dependent Regret Bounds in Multi-Armed Bandits with Interferencecited by 5
  6. 2024Cascading Reinforcement Learningcited by 4
  7. 2024Stochastic Bandits for Egalitarian Assignmentcited by 4
  8. 2021Combinatorial Blocking Bandits with Stochastic Delayscited by 3
  9. 2023Combinatorial Bandits for Maximum Value Reward Function under Max Value-Index Feedbackcited by 3
  10. 2021Recurrent Submodular Welfare and Matroid Blocking Banditscited by 2
  11. 2021Contextual Combinatorial Bandits with Changing Action Sets via Gaussian Processescited by 2
  12. 2023Bandit Learning to Rank with Position-Based Click Models: Personalized and Equal Treatmentscited by 2
  13. 2021Cascading Bandit under Differential Privacycited by 1
  14. 2021Online Learning of Independent Cascade Models with Node-level Feedbackcited by 1
  15. 2022Learning Neural Ranking Models Online from Implicit User Feedbackcited by 1
  16. 2024No-Regret Mnatural-Concave Function Maximization: Stochastic Bandit Algorithms and Hardness of Adversarial Full-Information Settingcited by 1
  17. 2025Design-Based Bandits Under Network Interference: Trade-Off Between Regret and Statistical Inferencecited by 1
  18. 2021Sleeping Combinatorial Banditscited by 0
  19. 2021On Learning to Rank Long Sequences with Contextual Banditscited by 0
  20. 2022Learning to Sell a Focal-ancillary Combinationcited by 0
  21. 2022UniRank: Unimodal Bandit Algorithm for Online Rankingcited by 0
  22. 2023Exploration of Unranked Items in Safe Online Learning to Re-Rankcited by 0
  23. 2025On the Sublinear Regret of Continuous K-Max Banditscited by 0
  24. 2025Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Banditscited by 0
  25. 2025Observation-Free Attacks on Online Learning to Rankcited by 0
  26. 2025Multiple-play Stochastic Bandits with Prioritized Arm Capacity Sharingcited by 0
  27. 2026Stochastic Reset Pathfinding: Path-Level Regret for Cascading Bandits over Graph Pathscited by 0
  28. 2026DCM Bandits: Multiplayer Information Asymmetric Cascading Bandits for Multiple Clickscited by 0