Combinatorial Bandits for Maximum Value Reward Function under Max Value-Index Feedback

Yiliu Wang, Wei Chen, Milan VojnovicarXiv 2023 · DOI · arXiv

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.

Comparison of the proposed work with existing literature in terms of feedback, reward types, and regret bounds.

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:

  1. Known Ordering (Algorithm 1): When the relative values of arms are known, the problem simplifies to a variation of a cascading bandit.
  2. 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.
  3. 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.
Algorithm 1: CUCB algorithm for known ordering of values.

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

Abstract

We consider a combinatorial multi-armed bandit problem for maximum value reward function under maximum value and index feedback. This is a new feedback structure that lies in between commonly studied semi-bandit and full-bandit feedback structures. We propose an algorithm and provide a regret bound for problem instances with stochastic arm outcomes according to arbitrary distributions with finite supports. The regret analysis rests on considering an extended set of arms, associated with values and probabilities of arm outcomes, and applying a smoothness condition. Our algorithm achieves a $O((k/Δ)\log(T))$ distribution-dependent and a $\tilde{O}(\sqrt{T})$ distribution-independent regret where $k$ is the number of arms selected in each round, $Δ$ is a distribution-dependent reward gap and $T$ is the horizon time. Perhaps surprisingly, the regret bound is comparable to previously-known bound under more informative semi-bandit feedback. We demonstrate the effectiveness of our algorithm through experimental results.
BibTeX
@misc{wang2023combinatorial,
  author = {Yiliu Wang and Wei Chen and Milan Vojnovic},
  title = {{Combinatorial Bandits for Maximum Value Reward Function under Max Value-Index Feedback}},
  year = {2023},
  eprint = {2305.16074},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2305.16074},
}
Figure