Combinatorial Bandits without Total Order for Arms

Shuo Yang, Tongzheng Ren, Inderjit S. Dhillon, Sujay Sanghavi

Abstract

In online recommendation and advertising systems, items are typically presented in sets or "bundles." Traditional machine learning models often rely on the assumption of a "total order"—the transitive logic that if a user prefers item A to B and B to C, they must prefer A to C. However, human preferences are frequently non-transitive and context-dependent. This paper investigates combinatorial multi-armed bandits (CMAB) where rewards are set-dependent and no total order exists. By introducing a novel assumption called "weak optimal set consistency," the authors demonstrate that a standard Upper Confidence Bound (UCB) algorithm is remarkably robust, achieving near-optimal regret in these complex environments.

Introduction: Beyond the Total Order Crutch

Most combinatorial bandit algorithms assume that items have an intrinsic, fixed value regardless of the set they belong to. This "set-independence" allows for a linear ranking of items from best to worst. In reality, preferences shift based on context. A user might prefer a specific digital camera when paired with budget accessories but overlook it when professional-grade lenses are available. When these preferences form loops (e.g., A > B, B > C, C > A), traditional ranking-based algorithms fail to converge on the optimal set.

The Challenge of Set-Dependent Rewards

The core difficulty in set-dependent bandits is the exponential growth of the search space; without a total order, one might theoretically need to test every possible combination of $n$ items chosen $k$ at a time. The authors highlight the "Digital Camera Trap," where an item may appear to be the best individual choice in many sub-optimal sets but is actually excluded from the truly optimal bundle.

Figure 2: Set-dependent acceptance probabilities illustrating how an item's reward (e.g., Digital Camera) varies significantly across different bundles, potentially misleading standard algorithms.

Weak Optimal Set Consistency

To make the problem tractable without reverting to a total order, the researchers propose a realistic assumption: Weak Optimal Set Consistency (WOSC). This assumption posits that if an arm $a$ is part of the optimal set $s^*$, its expected reward in any sub-optimal set $s$ should be at least as high as its reward in $s^*$. Intuitively, this suggests that an "all-star" item faces its toughest competition within the optimal set; in any other context, its relative performance should remain high or even increase.

Algorithm and Theoretical Analysis

Surprisingly, the authors prove that the standard Upper Confidence Bound (UCB) algorithm—which selects the top $k$ arms based on individual UCB values—is sufficient to solve this problem. Because rewards are set-dependent, the authors developed a novel regret analysis technique that tracks the dynamics of UCB values over time rather than relying on fixed intrinsic expectations.

Figure 5: Comparison of the proposed algorithm with existing bandit frameworks, highlighting its unique ability to handle set-dependent rewards and non-transitive preferences simultaneously.

As shown in the comparison table, the proposed algorithm (Algorithm 1) is the only method that maintains a fixed set size $k$ while successfully navigating environments with set-dependent rewards and no total order. It achieves a gap-dependent regret bound of $O(\frac{k^2 n \log T}{\epsilon})$, which the authors show is near-optimal.

Empirical Performance and Conclusion

The algorithm was tested against synthetic environments including Multinomial Logit (MNL) models and preference matrices containing explicit loops. While specialized algorithms like "Stagewise Elimination" failed to converge due to false eliminations of optimal arms in non-transitive settings, the UCB-based approach demonstrated steady convergence and superior regret performance. This work suggests that simple, robust algorithms can often outperform complex models when the underlying assumptions of human logic—like transitivity—are relaxed.

Summary updated

Abstract

We consider the combinatorial bandits problem, where at each time step, the online learner selects a size-$k$ subset $s$ from the arms set $\mathcal{A}$, where $\left|\mathcal{A}\right| = 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 \textit{no total order} for the arms in $\mathcal{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 $O\left(\frac{k^2 n \log T}ε\right)$ gap-dependent regret bound as well as an $O\left(k^2\sqrt{n T \log T}\right)$ 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.
BibTeX
@misc{yang2021combinatorial,
  author = {Shuo Yang and Tongzheng Ren and Inderjit S. Dhillon and Sujay Sanghavi},
  title = {{Combinatorial Bandits without Total Order for Arms}},
  year = {2021},
  eprint = {2103.02741},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2103.02741},
}
Figure