Source-linked AI summary
Gaussian Process Bandits for Constraint Black Box Lever Optimization
Bram van den Akker, Hidde Fokkema, Anastasiia Kornilova
TL;DR
Discrete budget allocation is difficult when segments are coupled and feedback is sparse, delayed, and aggregate. The paper applies GP-UCB with a simulation-to-deployment workflow, and reports statistically significant efficiency gains over ε-greedy in a live RCT. Its directional reporting reflects commercial sensitivity.
Problem
Discrete allocation across coupled segments combines a large action space with sparse, delayed aggregate feedback and infrequent adjustment opportunities.
Source: §1 · p. 1Method
The paper uses GP-UCB to share information across neighboring allocation configurations and evaluates kernel choices through simulation before live deployment.
Source: §1 · p. 1, §3.1 · p. 2Results
The live RCT found a statistically significant primary-efficiency lift over standard ε-greedy, while composite kernels reduced regret by 15–20% over ε-greedy in every challenging synthetic setting.
Source: §1 · p. 1, §5.1 · p. 4Takeaways & Limitations
The simulation-first approach supported deployment of GP-UCB in a live RCT, where it delivered a statistically significant efficiency gain over standard ε-greedy.
Source: §6 · p. 6Because of commercial sensitivity, the real-world results report directional findings rather than absolute metrics.
Source: §5.2 · p. 5
Abstract
from arXiv · showhide
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\'ern + 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 $\varepsilon$-greedy baseline, offering a highly practical solution for real-world black-box lever optimization.
1 Introduction
The paper addresses discrete budget allocation with coupled segments, sparse delayed aggregate feedback, and infrequent adjustment constraints. It applies GP-UCB and a simulation-to-deployment pipeline to this production setting.
1 Introduction
- With thousands of configurations but only tens of aggregate observations, independent-arm bandits requiring repeated per-arm sampling are unsuitable.The paper describes this mismatch as making classical bandit algorithms fundamentally unsuitable.Source: §1 · p. 1
- Shared-budget coupling, delayed aggregate feedback, and infrequent weight changes make allocation a combinatorial, high-noise, low-frequency problem.An incorrect weight in one segment degrades the performance of others.Source: §1 · p. 1
- The paper applies segmentation-agnostic GP-UCB [20] to budget allocation under strict real-world operating constraints.The approach is presented as bridging theoretical bandit research and production-scale deployment.Source: §1 · p. 1
- The contributions include a simulator for noisy, drifting, and reactive allocation environments, kernel-selection methodology, and a live production RCT.The RCT reports a statistically significant lift in the primary efficiency metric relative to standard ε-greedy.Source: §1 · p. 1
2 Related Work
Related work situates GP-UCB among methods for structured bandit optimization and notes applications to marketing. The authors also discuss convex bandits but do not pursue them in this study.
Gaussian Process bandits
- GP-UCB [20] shares information across nearby arms through GP dependencies and posterior uncertainty, and subsequent work extended its regret bounds and contextual and dynamic settings [3] [6].The related work notes applications to online bid optimization and budget allocation.Source: §2 · pp. 1–2
3 Methodology
The method models discrete segment weights as actions with periodic, noisy aggregate rewards, then uses GP-UCB to exploit similarity between configurations. Kernel selection compares local smoothness assumptions and composite kernels that add a global linear trend.
3 Methodology
- Discrete segment weights are adjusted periodically, with one aggregate reward observed after each adjustment and an optional step-size limit.Weights are discretized within a fixed range, for example [0.10, 1.0] in 0.05 increments.Source: §3 · p. 2
- With three segments and 0.05 increments from 0.10 to 1.0, the action space has 6,859 configurations, requiring 131 years to test weekly.Only a single reward summed across segments may be observed each week, preventing attribution to individual weights.Source: §3 · p. 2
3.1 Gaussian Process Bandits
- GP-UCB places a GP prior on the reward function and uses observed rewards from neighboring actions to estimate unexplored configurations.The algorithm selects the arm maximizing the predictive posterior upper confidence bound; its exploration parameter maintains exploration.Source: §3.1 · p. 2
3.1.1 Kernel Selection.
- Kernel choice encodes assumptions about reward smoothness and shape; the paper considers RBF, Matérn, and linear kernels.The Matérn kernel is evaluated with varying ν values for rougher, less predictable landscapes.Source: §3.1.1 · p. 2
- Adding a linear component to RBF or Matérn kernels combines nonlinear expressiveness with a global trend and is described as regularizing predictions and improving convergence.The motivation includes presumed diminishing marginal ROI as audience saturation increases.Source: §3.1.1 · p. 2
4 Experimental Setup
The study evaluates GP-UCB in a controlled budget-allocation simulator that varies reward dynamics and measures regret against an oracle.
4.1 Simulated Allocation Environment
- Weights control proportional spend, and fixing scale at λ_i = 1.0 prevents scalar-multiple configurations with identical allocations from appearing as distinct arms.For example, [0.1, 0.1, 0.1] and [0.2, 0.2, 0.2] yield identical allocations.Source: §4.1 · p. 3
- Segment rewards are smooth, non-monotone curves built by integrating Gaussian-inflection-point derivatives, producing varied slopes and local optima across combined allocations.Observations include additive Gaussian noise with a per-experiment scale sampled from [0.2, 0.5].Source: §4.1 · p. 3, Figure 1 · p. 3
- The 19-value-per-segment multiplier grid is constrained by a 0.10 step-size limit and an anchor constraint.The step-size limit permits at most two discrete increments per segment per step.Source: §4.1 · p. 3
4.2 Environment Variants
- The simulator includes a noiseless fixed landscape, a fixed landscape with observation noise, and gradual drift that invalidates earlier observations.For drift, inflection-point parameters are perturbed every 10 steps with σ_shift = 0.1.Source: §4.2 · p. 3
- The reactive environment serves as a mild robustness stress-test, not a fully adversarial game: it assesses whether a kernel’s advantage degrades gracefully when the environment partially counteracts the agent’s strategy.Source: §4.2 · p. 3
4.3 Algorithms
- Five GP-UCB kernel configurations are tested; the composite Matérn + Linear kernel combines smooth local structure with a global linear trend.The comparison also includes RBF, Matérn, Linear, and RBF + Linear kernels.Source: §4.3 · p. 4
- The baselines include ε-greedy, Constant, and an oracle; independent-arm UCB and Thompson Sampling are omitted given 6,859 feasible arms and a 52-week horizon.The paper argues GP-UCB generalizes across arms via its kernel, requiring fewer observations to identify high-reward regions.Source: §4.3 · p. 4
4.4 Evaluation Methodology
- Each configuration is evaluated over 100 experiments and 52 weekly decisions across three segments, with means and standard errors reported for cumulative and difference regret.Difference regret compares model regret with Constant-baseline regret and is negative when the model outperforms that baseline; the authors describe cross-shift kernel comparison as not systematically explored in prior GP-bandit work.Source: §4.4 · p. 4
5 Results
Synthetic tests found composite kernels robust across challenging environments, with Matérn + Linear selected for live evaluation. In the production RCT, GP-UCB showed positive performance lift across tested segments.
5.1 Offline Synthetic Results
- Pure Matérn led in the noiseless base environment with regret 10.6, a 65% reduction versus ε-greedy, but pure kernels lost their advantage under complexity.Under mild adversarial pressure, pure kernels were significantly worse than ε-greedy (p < 0.001).Source: §5.1 · p. 4, Table 1 · p. 5
- RBF + Linear and Matérn + Linear reduced regret by 15–20% versus ε-greedy in every challenging setting (all p<10^-3 at T=52).The linear term captures a coarse global trend and anchors exploration when local estimates are degraded by noise or distributional shift.Source: §5.1 · p. 4, Table 1 · p. 5
- Matérn + Linear reached significance earliest across environments (steps 4, 24, 19, 23) and was selected for the real-world experiment.It delivered the largest or near-largest improvement in every setting; the finite-smoothness Matérn component and linear trend balance local adaptability with global structure.Source: §5.1 · pp. 4–5, Table 1 · p. 5
- Shared-budget interactions can create local optima in the combined reward surface even when individual segment curves are monotonic.Figure 2 marks the optimal points for individual segments and the combined landscape.Source: Figure 2 · p. 5
5.2 Real world results
- The production RCT compared ε-greedy control with Matérn + Linear GP-UCB treatment over six weeks, using parameters optimized from about 52 weeks of historical data.Newly collected data were not shared between control and treatment; absolute performance metrics were withheld for commercial sensitivity.Source: §5.2 · p. 5
- The live treatment showed positive performance lift across all tested segments at the 90% confidence level.The authors report directional findings rather than absolute metrics due to commercial sensitivity.Source: §5.2 · p. 5
6 Conclusion & future work
The study reports a statistically significant efficiency gain for GP-UCB over ε-greedy in a live RCT and identifies Matérn + Linear as a superior alternative to traditional exploration strategies. Future work explores contextual and temporal modeling, while noting that contextualization increases the parameter space exponentially.
Conclusion
- The GP-UCB framework delivered a statistically significant efficiency gain over the standard ε-greedy baseline in a live RCT.The study also identifies Matérn + Linear as a superior alternative to traditional exploration strategies.Source: §6 · p. 6
Future Work
- Simulator results suggest that temporal non-stationarity modeling and contextual features could further reduce regret, but contextual bandits exponentially increase the parameter space.The authors identify this increased complexity as requiring further research.Source: §6 · p. 6
High-Dimensional Hyperparameter Optimization
- Future work will use the simulator to test which contextual variables provide the greatest information gain relative to added computational and statistical complexity.Source: §6 · p. 6
Dynamic Contextual Modeling; Automated Kernel Selection
- Future work explores spatio-temporal kernels for rapid distribution shifts and adaptive weighting of linear and nonlinear kernel components as volatility changes.Source: §6 · pp. 6–7