# Rectified Pessimistic-Optimistic Learning for Stochastic Continuum-armed Bandit with Constraints

arXiv: https://arxiv.org/abs/2211.14720 · HTML: https://mlsanity.com/paper/2211.14720/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 37 references that are in the map.
- First posted on arXiv 27 Nov 2022.

## Builds on (most cited first, 23 of 23)

- [On Kernelized Multi-armed Bandits](https://mlsanity.com/paper/1704.00445/) (2017)
- [BANANAS: Bayesian Optimization with Neural Architectures for Neural Architecture Search](https://mlsanity.com/paper/1910.11858/) (2019)
- [Bayesian Optimization with Safety Constraints: Safe and Automatic Parameter Tuning in Robotics](https://mlsanity.com/paper/1602.04450/) (2016)
- [Adaptive Online Learning in Dynamic Environments](https://mlsanity.com/paper/1810.10815/) (2018)
- [Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach](https://mlsanity.com/paper/2102.05406/) (2021)
- [Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1810.03024/) (2018)
- [Stagewise Safe Bayesian Optimization with Gaussian Processes](https://mlsanity.com/paper/1806.07555/) (2018)
- [Online Convex Optimization with Time-Varying Constraints](https://mlsanity.com/paper/1702.04783/) (2017)
- [Linear Bandits with Stochastic Delayed Feedback](https://mlsanity.com/paper/1807.02089/) (2018)
- [A Simple Approach for Non-stationary Linear Bandits](https://mlsanity.com/paper/2103.05324/) (2021)
- [Constrained Efficient Global Optimization of Expensive Black-box Functions](https://mlsanity.com/paper/2211.00162/) (2022)
- [Online convex optimization for cumulative constraints](https://mlsanity.com/paper/1802.06472/) (2018)
- [Hedging the Drift: Learning to Optimize under Non-Stationarity](https://mlsanity.com/paper/1903.01461/) (2019)
- [Dynamical Models and Tracking Regret in Online Convex Programming](https://mlsanity.com/paper/1301.1254/) (2013)
- [Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints](https://mlsanity.com/paper/2106.05135/) (2021)
- [Non-stationary Bandits with Knapsacks](https://mlsanity.com/paper/2205.12427/) (2022)
- [On Kernelized Multi-Armed Bandits with Constraints](https://mlsanity.com/paper/2203.15589/) (2022)
- [Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization](https://mlsanity.com/paper/2105.00321/) (2021)
- [No-Regret Algorithms for Time-Varying Bayesian Optimization](https://mlsanity.com/paper/2102.06296/) (2021)
- [Bayesian Optimization under Stochastic Delayed Feedback](https://mlsanity.com/paper/2206.09341/) (2022)
- [Learning-NUM: Network Utility Maximization with Unknown Utility Functions and Queueing Delay](https://mlsanity.com/paper/2012.09222/) (2020)
- [Regret Bounds for Safe Gaussian Process Bandit Optimization](https://mlsanity.com/paper/2005.01936/) (2020)
- [Interference Constrained Beam Alignment for Time-Varying Channels via Kernelized Bandits](https://mlsanity.com/paper/2207.00908/) (2022)

## Built on by (most cited first, 9 of 9)

- [Safe Reinforcement Learning with Instantaneous Constraints: The Role of Aggressive Exploration](https://mlsanity.com/paper/2312.14470/) (2023)
- [Constrained Multi-objective Bayesian Optimization through Optimistic Constraints Estimation](https://mlsanity.com/paper/2411.03641/) (2024)
- [Safe Bayesian Optimization for the Control of High-Dimensional Embodied Systems](https://mlsanity.com/paper/2412.20350/) (2024)
- [On the Low-Complexity of Fair Learning for Combinatorial Multi-Armed Bandit](https://mlsanity.com/paper/2501.00924/) (2025)
- [Multi-Agent Bayesian Optimization with Coupled Black-Box and Affine Constraints](https://mlsanity.com/paper/2310.00962/) (2023)
- [Multi-point Feedback of Bandit Convex Optimization with Hard Constraints](https://mlsanity.com/paper/2310.10946/) (2023)
- [On the Regularity and Fairness of Combinatorial Multi-Armed Bandit](https://mlsanity.com/paper/2509.12457/) (2025)
- [On the Robustness of Age for Learning-Based Wireless Scheduling in Unknown Environments](https://mlsanity.com/paper/2601.05956/) (2026)
- [Local Constrained Bayesian Optimization](https://mlsanity.com/paper/2603.07965/) (2026)

## Abstract (arXiv)

This paper studies the problem of stochastic continuum-armed bandit with constraints (SCBwC), where we optimize a black-box reward function f(x) subject to a black-box constraint function g(x)≤ 0 over a continuous space mathcal X. We model reward and constraint functions via Gaussian processes (GPs) and propose a Rectified Pessimistic-Optimistic Learning framework (RPOL), a penalty-based method incorporating optimistic and pessimistic GP bandit learning for reward and constraint functions, respectively. We consider the metric of cumulative constraint violation sumt=1T(g(xt))+, which is strictly stronger than the traditional long-term constraint violation sumt=1Tg(xt). The rectified design for the penalty update and the pessimistic learning for the constraint function in RPOL guarantee the cumulative constraint violation is minimal. RPOL can achieve sublinear regret and cumulative constraint violation for SCBwC and its variants (e.g., under delayed feedback and non-stationary environment). These theoretical results match their unconstrained counterparts. Our experiments justify RPOL outperforms several existing baseline algorithms.