No-Regret Algorithms for Safe Bayesian Optimization with Monotonicity Constraints
<|reference_start|>No-Regret Algorithms for Safe Bayesian Optimization with Monotonicity Constraints: We consider the problem of sequentially maximizing an unknown function $f$ over a set of actions of the form $(s,\mathbf{x})$, where the selected actions must satisfy a safety constraint with respect to an unknown safety function $g$. We model $f$ and $g$ as lying in a reproducing kernel Hilbert space (RKHS), which facilitates the use of Gaussian process methods. While existing works for this setting have provided algorithms that are guaranteed to identify a near-optimal safe action, the problem of attaining low cumulative regret has remained largely unexplored, with a key challenge being that expanding the safe region can incur high regret. To address this challenge, we show that if $g$ is monotone with respect to just the single variable $s$ (with no such constraint on $f$), sublinear regret becomes achievable with our proposed algorithm. In addition, we show that a modified version of our algorithm is able to attain sublinear regret (for suitably defined notions of regret) for the task of finding a near-optimal $s$ corresponding to every $\mathbf{x}$, as opposed to only finding the global safe optimum. Our findings are supported with empirical evaluations on various objective and safety functions.<|reference_end|>
@article{losalka2024no-regret,
    title={No-Regret Algorithms for Safe Bayesian Optimization with Monotonicity
  Constraints},
    author={Arpan Losalka, Jonathan Scarlett},
    journal={Proceedings of The 27th International Conference on Artificial
  Intelligence and Statistics, PMLR 238:3232-3240, 2024},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.03264},
    primaryClass={stat.ML cs.LG}
}