# Conservative Contextual Combinatorial Cascading Bandit

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 24 references that are in the map.
- First posted on arXiv 17 Apr 2021.

## Builds on (most cited first, 11 of 11)

- [Cascading Bandits: Learning to Rank in the Cascade Model](https://mlsanity.com/paper/1502.02763/) (2015)
- [Conservative Bandits](https://mlsanity.com/paper/1602.04282/) (2016)
- [Conservative Contextual Linear Bandits](https://mlsanity.com/paper/1611.06426/) (2016)
- [Combinatorial Multi-Armed Bandit with General Reward Functions](https://mlsanity.com/paper/1610.06603/) (2016)
- [SIC-MMAB: Synchronisation Involves Communication in Multiplayer Multi-Armed Bandits](https://mlsanity.com/paper/1809.08151/) (2018)
- [Combinatorial semi-bandit with known covariance](https://mlsanity.com/paper/1612.01859/) (2016)
- [Improved Algorithms for Conservative Exploration in Bandits](https://mlsanity.com/paper/2002.03221/) (2020)
- [Modeling Human Decision-making in Generalized Gaussian Multi-armed Bandits](https://mlsanity.com/paper/1307.6134/) (2013)
- [Cost-aware Cascading Bandits](https://mlsanity.com/paper/1805.08638/) (2018)
- [Contextual Combinatorial Conservative Bandits](https://mlsanity.com/paper/1911.11337/) (2019)
- [Online Learning with Diverse User Preferences](https://mlsanity.com/paper/1901.07924/) (2019)

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

- [A Reduction-Based Framework for Conservative Bandits and Reinforcement Learning](https://mlsanity.com/paper/2106.11692/) (2021)
- [Cascading Bandit under Differential Privacy](https://mlsanity.com/paper/2105.11126/) (2021)
- [Conservative Exploration for Policy Optimization via Off-Policy Policy Evaluation](https://mlsanity.com/paper/2312.15458/) (2023)

## Abstract (arXiv)

Conservative mechanism is a desirable property in decision-making problems which balance the tradeoff between the exploration and exploitation. We propose the novel conservative contextual combinatorial cascading bandit (C4-bandit), a cascading online learning game which incorporates the conservative mechanism. At each time step, the learning agent is given some contexts and has to recommend a list of items but not worse than the base strategy and then observes the reward by some stopping rules. We design the C4-UCB algorithm to solve the problem and prove its n-step upper regret bound for two situations: known baseline reward and unknown baseline reward. The regret in both situations can be decomposed into two terms: (a) the upper bound for the general contextual combinatorial cascading bandit; and (b) a constant term for the regret from the conservative mechanism. We also improve the bound of the conservative contextual combinatorial bandit as a by-product. Experiments on synthetic data demonstrate its advantages and validate our theoretical analysis.