Abstract
This paper introduces a new feedback model for combinatorial multi-armed bandits (CMAB) called max value-index feedback. In this setting, an agent selects a subset of $k$ arms but only observes the maximum reward and the identity of the winning arm. We propose algorithms within the Combinatorial Upper Confidence Bound (CUCB) framework that leverage this limited information. Our theoretical analysis shows that these algorithms achieve regret bounds of $O(\frac{nk}{\Delta} \log T)$, matching the performance of more informative semi-bandit settings. This work effectively bridges the gap between full-bandit and semi-bandit structures for maximum value reward functions.
Introduction
In a standard Combinatorial Multi-Armed Bandit (CMAB) problem, an agent selects a "slate" of $k$ arms from $n$ possibilities. Feedback typically falls into two categories: semi-bandit, where every selected arm's outcome is observed, and full-bandit, where only the total reward is seen. However, many real-world applications, such as recommendation systems on platforms like Netflix or Amazon, provide an intermediate level of feedback. When a user clicks on one of $k$ items, the platform learns which item was chosen (the index) and its value (e.g., a rating), but nothing about the unselected items.
The authors formalize this as the k-MAX bandit with max value-index feedback. The primary challenge lies in the non-linear reward function (the maximum value) and the censored nature of the feedback, which makes estimating the potential of "losing" arms difficult.
Methods
The proposed approach builds on the Combinatorial Upper Confidence Bound (CUCB) framework. A key innovation is the introduction of Relative Triggering Probability Modulated (RTPM) smoothness. This analytical tool allows the regret analysis to focus on arms that are likely to be the maximum value, effectively "underweighting" less competitive arms.
The paper presents several algorithmic variations:
- Known Ordering (Algorithm 1): When the relative values of arms are known, the problem simplifies to a variation of a cascading bandit.
- Unknown Ordering & Arm Equivalence (Algorithm 2): This core contribution addresses cases where arm values are unknown. It uses a "replacement" strategy, treating unobserved arms as equivalent binary arms to maintain optimistic estimates.
- General Discrete Distributions (Algorithm 3): This extends the approach to any discrete distribution with finite support by decomposing multi-valued arms into sets of imaginary binary arms.
Key Insights and Results
The research yields several significant insights:
- Information Efficiency: Knowing only the winner and its value is nearly as effective as seeing all $k$ values. Since "losers" are guaranteed to be less than or equal to the winner, this implicit information is sufficient for bounding regret.
- Regret Parity: The authors prove a distribution-dependent regret of $O(\frac{nk}{\Delta} \log T)$. This matches the order of bounds for semi-bandit feedback, suggesting that the additional information in semi-bandit settings does not improve the asymptotic learning rate for MAX rewards.
- Empirical Validation: Simulations on synthetic datasets (D1, D2, and D3) show that Algorithm 2 significantly outperforms standard MAB approaches and performs nearly as well as CUCB with full semi-bandit feedback.
Conclusion and Future Work
This paper demonstrates that max value-index feedback is a highly efficient structure for CMAB problems with maximum value rewards. While the current work focuses on discrete distributions with finite support and independent arms, future research could extend these findings to continuous distributions (e.g., Gaussian) and explore scenarios with correlated arm outcomes, which are common in practical recommendation systems.
Summary updated