Continuous K-Max Bandits

Yu Chen, Siwei Wang, Longbo Huang, Wei Chen

Introduction

In many real-world decision-making scenarios, the utility of a set of choices is determined solely by the best-performing element. Consider an advertisement platform that displays a set of $K$ products to a user; the platform's success is often measured by whether the user clicks on the single most appealing item. Similarly, in distributed computing, a task might be replicated across $K$ servers, where the overall latency is determined by the fastest server to complete the job.

These scenarios are formally modeled as $K$-Max Bandits. While traditional multi-armed bandit (MAB) problems focus on selecting a single arm to maximize expected reward, $K$-Max bandits involve selecting a subset of $K$ arms. The agent then observes only the maximum reward among the selected subset and the identity (index) of the arm that produced it. This paper addresses the significant theoretical and practical challenges that arise when rewards are continuous and feedback is limited to this "value-index" signal.

The Challenge: Continuous Outcomes and Partial Observability

Existing research into $K$-Max bandits has largely focused on discrete or binary rewards. However, real-world signals like server latency or user ratings are inherently continuous. Transitioning from discrete to continuous rewards introduces two primary hurdles:

  1. Value-Index Feedback: Unlike "semi-bandit" feedback, where the agent observes the outcome of every selected arm, the agent here only sees the winner. The outcomes of the $K-1$ "losing" arms remain hidden.
  2. The Discretization Bias: A common strategy for handling continuous rewards is to group them into discrete bins. However, this creates a "nondeterministic tie-breaking" problem. If multiple arms produce rewards that fall into the same top-tier bin, the agent only observes one winner. This hidden data creates a systematic bias in standard estimation techniques, as the observed winner is not necessarily representative of the underlying distribution of all arms in that bin.

Combining these constraints makes learning difficult, as standard algorithms fail to account for the systematic negative bias introduced by these unobserved ties.

Algorithmic Frameworks

1. DCK-UCB: Handling General Distributions

To address general continuous distributions, the authors introduce DCK-UCB (Discretized Continuous K-Max with Upper Confidence Bounds). This algorithm employs several key techniques to overcome the discretization bias:

  • Adaptive Discretization: The continuous reward space $[0, 1]$ is partitioned into discrete bins that are refined over time.
  • Bias-Corrected Estimators: The core innovation of DCK-UCB is a novel concentration analysis that accounts for unobserved ties. By assuming the reward distributions are bi-Lipschitz continuous (meaning the probability density is relatively stable), the authors mathematically bound the maximum possible bias. They then incorporate a bias compensation term into the standard UCB exploration bonus, ensuring the agent remains optimistic despite the systematic underestimation caused by ties.
  • Oracle-Based Selection: To handle the combinatorial challenge of selecting $K$ arms, the algorithm utilizes an offline Polynomial-Time Approximation Scheme (PTAS) oracle to identify the optimal subset based on the bias-corrected estimates.

2. MLE-Exp: Exploiting Distributional Structure

The authors also explore a specialized case: $K$-Min bandits where rewards (such as latency) follow an exponential distribution. This setting allows for a more elegant solution called MLE-Exp.

Exponential distributions possess a unique property: the minimum of several independent exponential random variables is itself an exponential random variable. By leveraging this, the authors can bypass discretization entirely. Using Maximum Likelihood Estimation (MLE), the agent can directly estimate the parameters of the underlying distributions. Remarkably, this approach works even with "full-bandit" feedback, where the agent only observes the minimum value without knowing which specific arm achieved it.

Theoretical Results and Regret Analysis

The paper provides the first rigorous regret bounds for the continuous $K$-Max setting under value-index feedback:

  • General Case: DCK-UCB achieves a regret upper bound of $\tilde{\mathcal{O}}(T^{3/4})$. This represents a significant milestone, as it is the first computationally tractable algorithm to provide a sublinear regret guarantee for this specific problem.
  • Exponential Case: For the exponential $K$-Min setting, MLE-Exp achieves a much tighter regret bound of $\tilde{\mathcal{O}}(\sqrt{T})$. This result is nearly minimax optimal, demonstrating that specific knowledge of the reward distribution can significantly accelerate the learning process.

Conclusion and Future Directions

This research bridges the gap between theoretical bandit models and the continuous, partially observable nature of real-world extremal selection problems. By identifying and correcting the bias inherent in discretizing $K$-Max feedback, the authors provide a foundation for more robust decision-making systems.

While the $\tilde{\mathcal{O}}(T^{3/4})$ bound is a major step forward, a gap remains between this and the $\tilde{\mathcal{O}}(\sqrt{T})$ bound typical of simpler bandit problems. Future work may focus on "variance-aware" algorithms to further tighten these bounds, potentially reaching $\tilde{\mathcal{O}}(T^{2/3})$. Additionally, relaxing the bi-Lipschitz assumption would allow these algorithms to be applied to an even broader range of real-world reward distributions.

Summary updated

Abstract

We study the $K$-Max combinatorial multi-armed bandits problem with continuous outcome distributions and weak value-index feedback: each base arm has an unknown continuous outcome distribution, and in each round the learning agent selects $K$ arms, obtains the maximum value sampled from these $K$ arms as reward and observes this reward together with the corresponding arm index as feedback. This setting captures critical applications in recommendation systems, distributed computing, server scheduling, etc. The continuous $K$-Max bandits introduce unique challenges, including discretization error from continuous-to-discrete conversion, non-deterministic tie-breaking under limited feedback, and biased estimation due to partial observability. Our key contribution is the computationally efficient algorithm DCK-UCB, which combines adaptive discretization with bias-corrected confidence bounds to tackle these challenges. For general continuous distributions, we prove that DCK-UCB achieves a $\widetilde{\mathcal{O}}(T^{3/4})$ regret upper bound, establishing the first sublinear regret guarantee for this setting. Furthermore, we identify an important special case with exponential distributions under full-bandit feedback. In this case, our proposed algorithm MLE-Exp enables $\widetilde{\mathcal{O}}(\sqrt{T})$ regret upper bound through maximal log-likelihood estimation, achieving near-minimax optimality.
BibTeX
@misc{chen2025continuous,
  author = {Yu Chen and Siwei Wang and Longbo Huang and Wei Chen},
  title = {{Continuous K-Max Bandits}},
  year = {2025},
  eprint = {2502.13467},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2502.13467},
}
Figure