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

Yiliu Wang, Wei Chen, Milan VojnovicICLR 2024 · OpenReview

TL;DR

This paper introduces a new "Value-Index" feedback model for combinatorial bandits, where an algorithm selects $k$ items but only learns which specific item was the "winner" (the maximum value) and what its value was. The authors propose a novel algorithm using "biased arm replacement" that achieves regret bounds nearly as good as much more informative feedback models. This effectively solves the exploration-exploitation trade-off even when the outcomes of the "losing" items remain hidden.

The Problem: Recommender Systems and Feedback Gaps

Imagine a platform like Netflix or Amazon. Every time a user visits, the system recommends a list of $k$ items. The "reward" for the platform is the value of the item the user actually interacts with—effectively, the maximum value among the recommended set.

In the realm of Multi-Armed Bandits (MAB), this is known as a $k$-MAX combinatorial problem. Historically, researchers have assumed one of two primary feedback structures:

  1. Semi-bandit feedback: The algorithm observes the outcome of every item it recommended.
  2. Full-bandit feedback: The algorithm only observes the final reward (the maximum value), but not which specific item produced it.

The authors identify a highly realistic middle ground: Value-Index feedback. Under this model, the system observes the maximum value and the identity (index) of the arm that achieved it. This is significantly weaker than semi-bandit feedback because the algorithm learns nothing about the $k-1$ items that didn't "win" that round. Did they lose because they are generally poor choices, or were they just unlucky in that specific instance? This lack of information makes estimating the true potential of every arm incredibly difficult.

Methodology: Biased Arm Replacement

The authors build upon the Combinatorial Upper Confidence Bound (CUCB) framework but introduce a clever algorithmic twist called Biased Arm Replacement.

The core challenge is that if an arm hasn't won yet, its true value remains entirely unknown. A conservative approach might ignore these unproven arms, but that leads to massive regret over time. Instead, the proposed algorithm takes a strategically optimistic approach:

  • Initializes with Bias: It treats unobserved arms as having a "biased" value of 1 (the maximum possible value in normalized settings).
  • Biased Replacement: In each round, the algorithm uses UCB indices to select arms. If an arm's value is unknown, it is replaced in the calculation by a "fictitious" version that is always triggered and has a biased estimate. This ensures the algorithm remains curious about arms it hasn't seen win yet, forcing exploration.
  • Binary Reduction: To handle complex, arbitrary discrete distributions, the authors prove a mathematical equivalence: any discrete distribution with finite support can be represented as a set of independent binary (0/1) variables. This allows their binary-focused algorithm to generalize to much broader real-world data.

Experimental Setup

The paper evaluates the algorithm using synthetic simulations designed to mimic challenging real-world scenarios. The experiments were conducted with $n=9$ total arms, selecting $k=3$ in each round over a horizon of $T=5000$ steps. The datasets included:

  • D1 (Base Case): A standard distribution of arm values.
  • D2 (Stable Arm): Includes a "safe" arm with a high probability of a decent outcome.
  • D3 (High-Risk/High-Reward): Includes an arm that rarely wins but provides a huge value when it does. This represents the "black swan" of bandit problems and is notoriously hard to learn.

Key Insights and Theoretical Guarantees

The primary "aha moment" of the paper is realizing that knowing who won is almost as valuable as seeing everything. While the algorithm doesn't see the losers' exact values, the fact that they lost reveals that their value was less than the winner's.

By assuming unobserved arms are perfect until proven otherwise (strategic optimism), the algorithm forces itself to explore until it has a clear picture of every arm's value.

Comparison of regret bounds and assumptions across different bandit feedback models.

Theoretically, the authors demonstrate that the regret bound for this limited Value-Index feedback is $O((nk/\Delta) \log T)$. As shown in the comparison table above, this is functionally the same rate as the much more informative semi-bandit setting. It proves that you don't actually need to see all the data to perform optimally.

Key Results

  • Regret Performance: In all three scenarios (D1, D2, D3), the proposed algorithm significantly outperformed standard UCB and DART (a full-bandit algorithm).
  • Efficiency: Most impressively, the regret curve of this algorithm closely tracked the curve of the "Semi-bandit CUCB"—an algorithm that has access to the outcomes of all $k$ arms. This suggests the "Value-Index" feedback is a highly efficient "sweet spot" for online learning.
  • Distribution Independence: The algorithm also achieves a distribution-independent regret bound of $\tilde{O}(\sqrt{nkT})$, ensuring robust performance even when the gaps between arm rewards are tiny.

Limitations and Future Work

  • Finite Support: The current theoretical proofs rely on arm outcomes having discrete, finite supports. While many real-world metrics (like 1-5 star ratings) fit this, extending the proofs to truly continuous distributions (like exact prices or continuous weights) remains an open challenge.
  • The "Full-Bandit" Jump: The authors note that moving from "Value-Index" to "Full-Bandit" (where you don't even know which arm won) is a much steeper mountain to climb. The "Biased Arm Replacement" trick fundamentally relies on knowing which arm's index to update.
  • Alternative Objectives: Future research could explore different reward functions, such as the "second-best" value or a "soft-max" of values, which might be highly relevant in different auction or recommendation settings.

Summary updated

Abstract

We investigate the combinatorial multi-armed bandit problem where an action is to select $k$ arms from a set of base arms, and its reward is the maximum of the sample values of these $k$ arms, under a weak feedback structure that only returns the value and index of the arm with the maximum value. This novel feedback structure is much weaker than the semi-bandit feedback previously studied and is only slightly stronger than the full-bandit feedback, and thus it presents a new challenge for the online learning task. We propose an algorithm and derive a regret bound for instances where arm outcomes follow distributions with finite supports. Our algorithm introduces a novel concept of biased arm replacement to address the weak feedback challenge, and it achieves a distribution-dependent regret bound of $O((k/\Delta)\log(T))$ and a distribution-independent regret bound of $\tilde{O}(\sqrt{T})$, where $\Delta$ is the reward gap and $T$ is the time horizon. Notably, our regret bound is comparable to the bounds obtained under the more informative semi-bandit feedback. We demonstrate the effectiveness of our algorithm through experimental results.
BibTeX
@inproceedings{wang2024combinatorial,
  author = {Yiliu Wang and Wei Chen and Milan Vojnovic},
  title = {{Combinatorial Bandits for Maximum Value Reward Function under Value-Index Feedback}},
  booktitle = {International Conference on Learning Representations},
  year = {2024},
  url = {https://openreview.net/forum?id=eMHn77ZKOp},
}
Figure