# Cost-aware Cascading Bandits

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 May 2018.

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

- [Conservative Contextual Combinatorial Cascading Bandit](https://mlsanity.com/paper/2104.08615/) (2021)
- [Fast Change Identification in Multi-Play Bandits and its Applications in Wireless Networks](https://mlsanity.com/paper/2205.10366/) (2022)
- [Optimal Stochastic Nonconvex Optimization with Bandit Feedback](https://mlsanity.com/paper/2103.16082/) (2021)
- [On Learning to Rank Long Sequences with Contextual Bandits](https://mlsanity.com/paper/2106.03546/) (2021)
- [Continuous Time Bandits With Sampling Costs](https://mlsanity.com/paper/2107.05289/) (2021)
- [Cascading Bandits With Feedback](https://mlsanity.com/paper/2511.10938/) (2025)

## Abstract (arXiv)

In this paper, we propose a cost-aware cascading bandits model, a new variant of multi-armed ban- dits with cascading feedback, by considering the random cost of pulling arms. In each step, the learning agent chooses an ordered list of items and examines them sequentially, until certain stopping condition is satisfied. Our objective is then to max- imize the expected net reward in each step, i.e., the reward obtained in each step minus the total cost in- curred in examining the items, by deciding the or- dered list of items, as well as when to stop examina- tion. We study both the offline and online settings, depending on whether the state and cost statistics of the items are known beforehand. For the of- fline setting, we show that the Unit Cost Ranking with Threshold 1 (UCR-T1) policy is optimal. For the online setting, we propose a Cost-aware Cas- cading Upper Confidence Bound (CC-UCB) algo- rithm, and show that the cumulative regret scales in O(log T ). We also provide a lower bound for all α-consistent policies, which scales in Omega(log T ) and matches our upper bound. The performance of the CC-UCB algorithm is evaluated with both synthetic and real-world data.