mlsanityData to 14 Oct 2026

On Kernelized Multi-Armed Bandits with Constraints

arXiv 2203.15589 ↗First posted 29 Mar 2022cs.LGcited by 23

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 23 papers in the map (data through 14 Oct 2026). Builds on 37 of its 49 references that are in the map. First posted on arXiv 29 Mar 2022.

Builds on

37 of 49 references.

References · 37

  1. 2017On Kernelized Multi-armed Banditscited by 352
  2. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  3. 2013Bandits with Knapsackscited by 164
  4. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 158
  5. 2020Exploration-Exploitation in Constrained MDPscited by 149
  6. 2016Bayesian Optimization with Safety Constraints: Safe and Automatic Parameter Tuning in Roboticscited by 134
  7. 2020Provably Efficient Safe Exploration via Primal-Dual Policy Optimizationcited by 134
  8. 2014Bayesian Optimization with Unknown Constraintscited by 109
  9. 2017Online Convex Optimization with Stochastic Constraintscited by 95
  10. 2019Linear Stochastic Bandits Under Safety Constraintscited by 90
  11. 2020Scalable Constrained Bayesian Optimizationcited by 84
  12. 2015Linear Contextual Bandits with Knapsackscited by 82
25 more
  1. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 80
  2. 2018Stagewise Safe Bayesian Optimization with Gaussian Processescited by 79
  3. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 78
  4. 2019Combinatorial Sleeping Bandits with Fairness Constraintscited by 68
  5. 2020Stochastic Bandits with Linear Constraintscited by 68
  6. 2016Conservative Banditscited by 59
  7. 2016Conservative Contextual Linear Banditscited by 57
  8. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  9. 2021High-Dimensional Experimental Design and Kernel Banditscited by 56
  10. 2015A General Framework for Constrained Bayesian Optimization using Information-based Searchcited by 50
  11. 2019Fair Contextual Multi-Armed Bandits: Theory and Experimentscited by 42
  12. 2020A Domain-Shrinking based Bayesian Optimization Algorithm with Order-Optimal Regret Performancecited by 39
  13. 2019Safe Linear Thompson Sampling with Side Informationcited by 37
  14. 2020On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimizationcited by 31
  15. 2015Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Banditscited by 29
  16. 2019Perturbed-History Exploration in Stochastic Linear Banditscited by 29
  17. 2021An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraintscited by 29
  18. 2019Bayesian Optimization under Heavy-tailed Payoffscited by 21
  19. 2019Old Dog Learns New Tricks: Randomized UCB for Bandit Problemscited by 21
  20. 2019Randomized Exploration for Non-Stationary Stochastic Linear Banditscited by 18
  21. 2022Improved Convergence Rates for Sparse Approximation Methods in Kernel-Based Learningcited by 18
  22. 2021A Provably-Efficient Model-Free Algorithm for Constrained Markov Decision Processescited by 17
  23. 2020Improved Algorithms for Conservative Exploration in Banditscited by 16
  24. 2020POND: Pessimistic-Optimistic oNline Dispatchingcited by 7
  25. 2021PAC Best Arm Identification Under a Deadlinecited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2022: 3; 2023: 4; 2024: 5; 2025: 6; 2026: 5.

23 papers.

Sort:

By area:

  1. 2022Contextual Bandits with Packing and Covering Constraints: A Modular Lagrangian Approach via Regressioncited by 30
  2. 2024Principled Preferential Bayesian Optimizationcited by 16
  3. 2022Rectified Pessimistic-Optimistic Learning for Stochastic Continuum-armed Bandit with Constraintscited by 9
  4. 2025Provably Efficient RL for Linear MDPs under Instantaneous Safety Constraints in Non-Convex Feature Spacescited by 7
  5. 2024Constrained Multi-objective Bayesian Optimization through Optimistic Constraints Estimationcited by 6
  6. 2024Principled Bayesian Optimisation in Collaboration with Human Expertscited by 5
  7. 2024Safe Bayesian Optimization for the Control of High-Dimensional Embodied Systemscited by 4
  8. 2022CONFIG: Constrained Efficient Global Optimization for Closed-Loop Control System Optimization with Unmodeled Constraintscited by 3
  9. 2023(Private) Kernelized Bandits with Distributed Biased Feedbackcited by 3
  10. 2023Primal-Dual Contextual Bayesian Optimization for Control System Online Optimization with Time-Average Constraintscited by 3
  11. 2023Data-driven adaptive building thermal controller tuning with constraints: A primal-dual contextual Bayesian optimization approachcited by 3
  12. 2025On the Low-Complexity of Fair Learning for Combinatorial Multi-Armed Banditcited by 3
11 more
  1. 2024Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budgetcited by 2
  2. 2025Convergence Rates of Constrained Expected Improvementcited by 2
  3. 2025Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budgetcited by 1
  4. 2026Laplacian Kernelized Banditcited by 1
  5. 2023Multi-Agent Bayesian Optimization with Coupled Black-Box and Affine Constraintscited by 0
  6. 2025On the Regularity and Fairness of Combinatorial Multi-Armed Banditcited by 0
  7. 2025A Constrained Multi-Fidelity Bayesian Optimization Methodcited by 0
  8. 2026Bandits in Flux: Adversarial Constraints in Dynamic Environmentscited by 0
  9. 2026Local Constrained Bayesian Optimizationcited by 0
  10. 2026Multi-Task Representation Learning for Conservative Linear Banditscited by 0
  11. 2026Minimax Optimal Regret for Causal Logistic Bandits with Counterfactual Fairnesscited by 0