Combinatorial Cascading Bandits

Abstract

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.

Advances in Neural Information Processing Systems 28

References in corpus (2)

• Cascading Bandits: Learning to Rank in the Cascade Model
• An Adaptive Algorithm for Finite Stochastic Partial Monitoring

Cited by in corpus (23)

• Combinatorial Multi-Armed Bandit with General Reward Functions
• DCM Bandits: Learning to Rank with Multiple Clicks
• Online Learning to Rank in Stochastic Click Models
• Thompson Sampling for Combinatorial Semi-Bandits
• Reinforcement Learning to Rank in E-Commerce Search Engine: Formalization, Analysis, and Application
• PairRank: Online Pairwise Learning to Rank by Divide-and-Conquer
• BubbleRank: Safe Online Learning to Re-Rank via Implicit Click Feedback
• Thompson Sampling for Combinatorial Network Optimization in Unknown Environments
• Combinatorial Semi-Bandit in the Non-Stationary Environment
• Tight Lower Bounds for Combinatorial Multi-Armed Bandits
• Contextual User Browsing Bandits for Large-Scale Online Mobile Recommendation
• Meta-Learning Bandit Policies by Gradient Ascent
• Online Learning of Independent Cascade Models with Node-level Feedback
• Combinatorial Blocking Bandits with Stochastic Delays
• Recurrent Submodular Welfare and Matroid Blocking Bandits
• Waterfall Bandits: Learning to Sell Ads Online
• No Regrets for Learning the Prior in Bandits
• Observe Before Play: Multi-armed Bandit with Pre-observations
• Thompson Sampling Algorithms for Cascading Bandits
• Sleeping Combinatorial Bandits
• Fatigue-aware Bandits for Dependent Click Models
• Sequential ranking under random semi-bandit feedback
• Batch-Size Independent Regret Bounds for the Combinatorial Multi-Armed Bandit Problem