Optimizing discrete allocation weights across competing segments of a shared budget is a fundamental challenge in resource-constrained, sequential decision-making environments. In practice, this optimization is often hindered by delayed, noisy, and aggregate feedback, alongside strict operational constraints on how frequently weights can be adjusted. Because of the resulting combinatorial action space and extreme data sparsity, classical multi-armed bandit algorithms that evaluate arms independently are rendered highly inefficient. To overcome these limitations, we propose a segmentation-agnostic approach utilizing Gaussian Process Upper Confidence Bound (GP-UCB) algorithms. By placing a Gaussian Process prior on the reward function, our method effectively shares information across neighboring configurations, drastically reducing the necessary exploration horizon. In this paper, we bridge the gap between theoretical bandit research and production-scale deployment. We first introduce a high-fidelity synthetic simulator to evaluate various kernel configurations under stationary, drifting, and reactive environments, identifying a composite Matérn + Linear kernel as the most robust choice for overcoming local noise and global shifts. Finally, we validate our findings through a large-scale Randomized Controlled Trial (RCT) in a live production environment. Our empirical results demonstrate that the GP-UCB approach delivers a statistically significant efficiency lift compared to a standard ε-greedy baseline, offering a highly practical solution for real-world black-box lever optimization.
Figures & tables
Figure 1. Reward landscapes are constructed using gaussian inflection points as shown (a) and (b). These inflection points represent the derivatives of the reward landscape and result into a non-linear function, which could be either monotonically increasing/decreasing (c) or cause pockets of incrementality where additional allocation results in incremental rewards.
Figure 2. When segments share a budget (proportional allocation), the combined reward surface can have local optima even if individual segment curves are monotonic, because shifting weight between segments creates interaction effects. The top row shows a set of segment without pockets of incrementality , and the bottom row shows landscapes with multiple segments. We have marked the optimal points for each segment and their combined landscape with a star. Our goal is to find these points.
Figure 3. Cumulative regret over T=52 weeks. The black diagonal represents the regret when the reward is consistently zero.
BASE
NOISE
DRIFT
REACT.
Constant
39.8±2.0
42.7±2.4
51.1±3.1
42.3±2.0
Optimal
06.8±0.4
07.4±0.5
07.8±0.7
09.9±0.7
ε -greedy
30.2±1.8
40.4±2.2
50.3±3.1
38.8±1.9
RBF
19.1±1.6
42.0±2.3
50.2±3.1
41.9±2.0
step 4
—
—
↓
Matérn
10.6±0.8
41.3±2.3
50.8±3.0
41.5±2.0
Table 1. Final cumulative regret at T=52 (mean ± SEM) and first step with significant improvement over ε -greedy ( p<0.05 , one-sided paired t -test). “—”: not significant; “ ↓ ”: significantly worse.
The contextual bandit models sequential decision-making problems in which rewards depend on both the chosen action and observed context. In many domains such as medicine, business, and engineering, prior knowledge provides structural information about the reward function that can be exploited to improve optimization efficiency. This paper studies settings where, for each observable context, the conditional mean reward is known to be concave with respect to the action variable. To leverage this structure, we develop a contextual bandit algorithm that conditions a Bayesian Gaussian Process posterior on concavity constraints. We propose a novel reward model that combines a concavity-preserving regression spline basis with a constrained GP posterior, yielding a tractable shape-constrained estimator. Building on this model, we construct a UCB algorithm and establish new posterior concentration inequalities for the constrained posterior, leading to regret guarantees that are never worse than applying standard GP-UCB without concavity information and can be strictly tighter when concavity is informative. Experiments on benchmark problems and a Warfarin dosing test application demonstrate substantial reductions in cumulative regret relative to state-of-the-art baselines.
This paper studies the regret analysis for parallel Gaussian process (GP) bandit optimization. The known regret upper bounds for the widely used GP batched upper confidence bound and GP batched Thompson sampling (GP-BTS) suffer from a multiplicative factor with respect to the batch size Q. To avoid this degradation, existing analyses require a polynomial number of uncertainty sampling (US) for Q at the beginning of optimization. However, this initial US phase is often ineffective in practice. This paper shows that the regret upper bound without the multiplicative factor on Q can be achieved without the initial US phase, using GP-BTS as an example. Furthermore, we show much better regret upper bounds in the noiseless setting than in the noisy setting, as in the sequential GP bandit setting.
This paper addresses the Bayesian optimization problem (also referred to as the Bayesian setting of the Gaussian process bandit), where the learner seeks to minimize the regret under a function drawn from a known Gaussian process (GP). Under a Matérn kernel with a certain degree of smoothness, we show that the Gaussian process upper confidence bound (GP-UCB) algorithm achieves O~(T) cumulative regret with high probability. Furthermore, our analysis yields O(Tln2T) regret under a squared exponential kernel. These results fill the gap between the existing regret upper bound for GP-UCB and the best-known bound provided by Scarlett (2018). The key idea in our proof is to capture the concentration behavior of the input sequence realized by GP-UCB, enabling a more refined analysis of the GP's information gain.