# Combinatorial Bandits without Total Order for Arms

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 23 references that are in the map.
- First posted on arXiv 3 Mar 2021.

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

- [Reducing Dueling Bandits to Cardinal Bandits](https://mlsanity.com/paper/1405.3396/) (2014)
- [MNL-Bandit: A Dynamic Learning Approach to Assortment Selection](https://mlsanity.com/paper/1706.03880/) (2017)
- [Multi-dueling Bandits with Dependent Arms](https://mlsanity.com/paper/1705.00253/) (2017)
- [Thompson Sampling for the MNL-Bandit](https://mlsanity.com/paper/1706.00977/) (2017)
- [Combinatorial Bandits with Relative Feedback](https://mlsanity.com/paper/1903.00543/) (2019)
- [Multi-Dueling Bandits and Their Application to Online Ranker Evaluation](https://mlsanity.com/paper/1608.06253/) (2016)
- [Best-of-K Bandits](https://mlsanity.com/paper/1603.02752/) (2016)
- [A Note on a Tight Lower Bound for MNL-Bandit Assortment Selection Models](https://mlsanity.com/paper/1709.06109/) (2017)
- [Optimizing Expected Utility in a Multinomial Logit Model with Position Bias and Social Influence](https://mlsanity.com/paper/1411.0279/) (2014)

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

- [Finding Optimal Arms in Non-stochastic Combinatorial Bandits with Semi-bandit Feedback and Finite Budget](https://mlsanity.com/paper/2202.04487/) (2022)

## Abstract (arXiv)

We consider the combinatorial bandits problem, where at each time step, the online learner selects a size-k subset s from the arms set A, where left|Aright| = n, and observes a stochastic reward of each arm in the selected set s. The goal of the online learner is to minimize the regret, induced by not selecting s^* which maximizes the expected total reward. Specifically, we focus on a challenging setting where 1) the reward distribution of an arm depends on the set s it is part of, and crucially 2) there is textitno total order for the arms in A. In this paper, we formally present a reward model that captures set-dependent reward distribution and assumes no total order for arms. Correspondingly, we propose an Upper Confidence Bound (UCB) algorithm that maintains UCB for each individual arm and selects the arms with top-k UCB. We develop a novel regret analysis and show an Oleft(frack2 n log Tεright) gap-dependent regret bound as well as an Oleft(k2√n T log Tright) gap-independent regret bound. We also provide a lower bound for the proposed reward model, which shows our proposed algorithm is near-optimal for any constant k. Empirical results on various reward models demonstrate the broad applicability of our algorithm.