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.
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.
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