On Kernelized Multi-Armed Bandits with Constraints

Xingyu Zhou, Bo Ji

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 upper confidence bound (UCB), Thompson sampling (TS), and new ones based on 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.

Introduction

In many real-world sequential decision-making scenarios—ranging from tuning cloud resource configurations to managing wireless power—an agent must maximize an unknown reward function $f$ while satisfying an unknown constraint function $g$. Traditional "safe" bandit algorithms typically focus on hard constraints, where the agent must remain within safe bounds in every single round. However, this approach is often overly conservative, computationally expensive (requiring the construction of complex "safe sets"), and necessitates a known "safe seed" to begin exploration.

This research shifts the focus to soft constraints, where the objective is to ensure that cumulative violations remain small over time. This paradigm is significantly more practical for applications like budget management or latency thresholds, where occasional spikes are acceptable if the long-term average is maintained. The primary challenge lies in handling these constraints when both $f$ and $g$ are non-linear, non-convex functions residing in a Reproducing Kernel Hilbert Space (RKHS).

The CKB Framework

We introduce a unified framework called Constrained Kernelized Bandits (CKB). At its core, CKB utilizes primal-dual optimization to balance exploration and constraint satisfaction. The algorithm operates through four key stages:

  1. Estimation: The algorithm maintains Gaussian Process (GP) models for both the reward and the constraint functions, updating its beliefs as new data arrives.
  2. Primal Step: It selects an action that maximizes a "pseudo-acquisition function." This is essentially a Lagrangian that balances the estimated reward against the estimated constraint violation, weighted by a dual variable $\phi_t$.
  3. Dual Step: The dual variable $\phi_t$ is updated based on the observed constraint violation. If a violation occurs, $\phi_t$ increases, effectively making the algorithm more "cautious" in subsequent rounds.
  4. Exploration Flexibility: Unlike prior work tied strictly to Upper Confidence Bound (UCB) strategies, CKB is compatible with any strategy meeting a newly defined "sufficient condition." This allows for the integration of various exploration methods, including GP-UCB, GP-Thompson Sampling (TS), and a new randomized strategy, RandGP-UCB.

Key Insights and Theoretical Contributions

Complexity Parity

A striking finding of this work is that CKB maintains the same computational complexity as unconstrained bandits. By avoiding the geometric complexity of building and maintaining "safe sets," CKB scales linearly with the number of actions, whereas hard-constraint algorithms often scale quadratically.

The Power of Slackness

By incorporating a small "slack" term ($\epsilon$) into the dual update, the framework can trade a negligible amount of reward regret to achieve zero cumulative constraint violation in the long run. This provides a powerful tool for practitioners who require strict long-term adherence to constraints.

Decoupling Analysis

The introduction of the "sufficient condition" is a major theoretical contribution. It provides a modular recipe for researchers to prove that new exploration strategies will work within the CKB framework without re-deriving the entire regret analysis from scratch.

Convex-Opt vs. Lyapunov-Drift

The paper provides a detailed comparison between two popular analysis techniques. We argue that the "convex-optimization" approach used here is more flexible for general exploration strategies than the "Lyapunov-drift" method, which is often tightly coupled to UCB-style optimism.

Experimental Evaluation

The framework was evaluated across three distinct data regimes:

  • Synthetic Data: Functions sampled from kernels over a discretized [0, 1] domain.
  • Light-Tailed Real-World Data: Light sensor data from the CMU Intelligent Workplace, used to find maximum average readings under a specific threshold.
  • Heavy-Tailed Real-World Data: Adjusted closing prices of 29 stocks (2016–2019). This tested the robustness of the algorithms against non-Gaussian, "heavy-tailed" noise common in financial markets.

In all simulations, CKB-UCB, CKB-TS, and CKB-Rand consistently outperformed state-of-the-art safe Bayesian Optimization algorithms such as StageOpt and SGP-UCB. Notably, even in the heavy-tailed finance dataset—where underlying noise violates standard sub-Gaussian assumptions—the CKB algorithms remained stable and achieved significant performance gains.

Conclusion and Future Work

CKB offers a robust, flexible, and computationally efficient framework for kernelized bandits with soft constraints. While the current theory relies on sub-Gaussian noise assumptions, empirical results suggest robustness to heavy-tailed distributions, marking a clear path for future theoretical expansion. Additionally, extending this primal-dual framework to Kernelized Markov Decision Processes (MDPs) and continuous action spaces remains a promising direction for future research in reinforcement learning and robotics.

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