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:
- 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.
- 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:
- Synthetic Data: 1D functions generated using Squared Exponential (SE) kernels to test fundamental convergence properties.
- 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.
- 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.
- 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
StageOptandSGP-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