On Kernelized Multi-Armed Bandits with Constraints

Xingyu Zhou, Bo Ji

In many real-world decision-making scenarios—such as optimizing cloud resource configurations or wireless power control—agents must navigate unknown, complex reward functions while adhering to strict operational limits. This paper, presented at NeurIPS 2022, introduces a unified primal-dual framework for Kernelized Multi-Armed Bandits (KB) that must satisfy unknown constraints.

Unlike previous "safe" bandit approaches that require every single action to be strictly safe, this work focuses on soft constraints. By allowing short-term constraint violations as long as the long-term cumulative violation remains low, the proposed framework enables much higher rewards and more flexible exploration.

The Challenge: Soft vs. Hard Constraints

Existing research in this domain typically falls into two camps:

  1. Unconstrained Kernelized Bandits: These methods excel at handling complex, non-linear functions using Gaussian Processes (GPs) or Reproducing Kernel Hilbert Space (RKHS) models, but they completely ignore operational constraints.
  2. Safe Bandits: These focus on "hard" constraints, demanding that every action be safe with high probability. This approach is often overly conservative, leading to suboptimal rewards, and is computationally expensive because it requires constructing a "safe set" at every step.

This paper addresses the critical gap for soft constraints. In many applications, it is acceptable to occasionally exceed a limit (e.g., an average energy budget) if the agent "compensates" by staying well under the limit later. The core challenge lies in designing an algorithm that simultaneously learns the reward and constraint functions while balancing exploration and exploitation.

Methodology: The CKB Framework

The authors propose CKB (Constrained Kernelized Bandits), a primal-dual framework that handles non-linear rewards and constraints in an RKHS. The algorithm operates through several key mechanisms:

  • Surrogate Models: CKB uses Gaussian Process regression to maintain estimates of both the unknown reward function ($f$) and the constraint function ($g$).
  • Primal Step: In each round, the algorithm selects an action that maximizes a "pseudo-acquisition function." This acts as a Lagrangian, subtracting the estimated constraint (weighted by a dual variable $\lambda$) from the estimated reward.
  • Dual Step: The dual variable $\lambda$—acting as the "penalty" for violating the constraint—is updated using projected gradient descent. If a constraint is violated, $\lambda$ increases, forcing the algorithm to be more conservative in subsequent rounds.
  • Unified Analysis via Sufficient Condition: The authors introduce a novel "Sufficient Condition." If an exploration strategy (like Upper Confidence Bound (UCB) or Thompson Sampling (TS)) meets this condition, it is guaranteed to achieve sublinear regret and sublinear constraint violation.
  • Slackness for Zero Violation: By introducing a small "slackness" constant ($\epsilon$) to the dual update, the algorithm can be tuned to achieve zero total constraint violation over the long run, with only a minor trade-off in reward regret.

Experimental Setup

The algorithms were evaluated across three distinct data environments:

  1. Synthetic Data: 1D functions generated using Squared Exponential (SE) kernels to test fundamental convergence properties.
  2. Light-Tailed Real-World Data: A dataset from the CMU Intelligent Workplace containing light sensor readings. The objective was to maximize the average reading subject to a threshold constraint.
  3. Heavy-Tailed Real-World Data: A finance dataset used to test algorithmic robustness. While the theoretical guarantees assume sub-Gaussian noise, real-world data is often heavy-tailed, providing a rigorous stress test for CKB.

Key Insights and Results

By decoupling the exploration strategy from constraint handling, the primal-dual approach makes the CKB framework highly adaptable. The authors demonstrate that strict optimism (like standard UCB) is not strictly necessary to handle constraints; as long as the strategy is "optimistic enough" probabilistically, the primal-dual balance corrects for over-exploration.

Cumulative regret and constraint violations across synthetic and real-world datasets.
  • Sublinear Performance: The CKB framework theoretically guarantees $O(\sqrt{T})$ regret and constraint violation.
  • Superior Rewards: In empirical tests, variants like CKB-UCB, CKB-TS, and CKB-Rand significantly outperformed existing safe-bandit algorithms (such as StageOpt and SGP-UCB) in cumulative reward.
  • Zero Violation in Practice: Utilizing the slackness modification, CKB-UCB achieved exactly zero constraint violations on the CMU sensor dataset while maintaining high rewards.
  • Robustness: Even in the heavy-tailed finance dataset—where theoretical noise assumptions were broken—the CKB algorithms remained stable and continued to outperform baselines.

Limitations and Future Directions

While powerful, the framework has a few limitations. The theoretical analysis relies on Slater's Condition, meaning there must exist at least one strictly feasible policy that stays safely away from the constraint boundary. If optimal points lie exactly on the boundary and the interior is difficult to locate, the algorithm may struggle.

Additionally, like most frequentist kernelized bandit approaches, CKB assumes the agent knows (or can upper-bound) the RKHS norm of the underlying functions. Finally, while more efficient than safe-set methods, CKB relies on GP posterior updates, which scale poorly as the number of rounds ($T$) grows. Future work could integrate sparse GP approximations to enhance scalability for massive, long-horizon deployments.

Summary updated

Abstract

We study a stochastic bandit problem with a general unknown reward function and a general unknown constraint function. Both functions can be non-linear (even non-convex) and are assumed to lie in a reproducing kernel Hilbert space (RKHS) with a bounded norm. This kernelized bandit setup strictly generalizes standard multi-armed bandits and linear bandits. In contrast to safety-type hard constraints studied in prior works, we consider soft constraints that may be violated in any round as long as the cumulative violations are small, which is motivated by various practical applications. Our ultimate goal is to study how to utilize the nature of soft constraints to attain a finer complexity-regret-constraint trade-off in the kernelized bandit setting. To this end, leveraging primal-dual optimization, we propose a general framework for both algorithm design and performance analysis. This framework builds upon a novel sufficient condition, which not only is satisfied under general exploration strategies, including \emph{upper confidence bound} (UCB), \emph{Thompson sampling} (TS), and new ones based on \emph{random exploration}, but also enables a unified analysis for showing both sublinear regret and sublinear or even zero constraint violation. We demonstrate the superior performance of our proposed algorithms via numerical experiments based on both synthetic and real-world datasets. Along the way, we also make the first detailed comparison between two popular methods for analyzing constrained bandits and Markov decision processes (MDPs) by discussing the key difference and some subtleties in the analysis, which could be of independent interest to the communities.
BibTeX
@inproceedings{zhou2022kernelized,
  author = {Xingyu Zhou and Bo Ji},
  title = {{On Kernelized Multi-Armed Bandits with Constraints}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=wgRQ1IM4g_w},
}
Figure