# Categorized Bandits

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

## Key facts

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

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

- [Hierarchical Conversational Preference Elicitation with Bandit Feedback](https://mlsanity.com/paper/2209.06129/) (2022)
- [Max-Min Grouped Bandits](https://mlsanity.com/paper/2111.08862/) (2021)
- [Thompson Sampling for Bandits with Clustered Arms](https://mlsanity.com/paper/2109.01656/) (2021)
- [Simultaneously Achieving Group Exposure Fairness and Within-Group Meritocracy in Stochastic Bandits](https://mlsanity.com/paper/2402.05575/) (2024)
- [Adversarial Online Collaborative Filtering](https://mlsanity.com/paper/2302.05765/) (2023)
- [Fast Online Learning with Gaussian Prior-Driven Hierarchical Unimodal Thompson Sampling](https://mlsanity.com/paper/2602.15972/) (2026)

## Abstract (arXiv)

We introduce a new stochastic multi-armed bandit setting where arms are grouped inside ``ordered'' categories. The motivating example comes from e-commerce, where a customer typically has a greater appetence for items of a specific well-identified but unknown category than any other one. We introduce three concepts of ordering between categories, inspired by stochastic dominance between random variables, which are gradually weaker so that more and more bandit scenarios satisfy at least one of them. We first prove instance-dependent lower bounds on the cumulative regret for each of these models, indicating how the complexity of the bandit problems increases with the generality of the ordering concept considered. We also provide algorithms that fully leverage the structure of the model with their associated theoretical guarantees. Finally, we have conducted an analysis on real data to highlight that those ordered categories actually exist in practice.