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.
Figures & tables
Figure 1: Mean cumulative regret for contextual bandit methods on benchmark functions across T , with ± 1 standard error bars.
Figure 2: Cumulative regret for numerical simulation study. The proposed methods, CSGP-Thompson and CSGP-UCB, obtain markedly lower regret than competing methods across a range of problem dimensions and scalings.
Figure 3: Mean ratio between maximum confidence parameter selected by CSGP-UCB up to time TαT∗ , and default GP-UCB time T confidence parameter χT .
Figure 4: Cumulative regret for the Warfarin test function experiment with ± 1 SE bars.
Figure 5: Example draws of the LCTMVN variable. The distribution is very skewed.
CSGP-UCB with relaxed coefficient upper bound
Perturbation scale ρ
Coefficient upper bound c
0
0.05
0.10
0.25
0
101(±7)
124(±8)
181(±9)
539(±42)
0.1
104(±7)
120(±8)
167(±8)
479(±40)
0.2
111(±8)
115(±8)
143(±8)
424(±37)
Table 1: Final cumulative regret after T=500 rounds under perturbations that violate concavity. Columns denote the perturbation scale ρ=sd(gρ)/sd(f0) . Parentheses give ±1 standard error. Lower is better.
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.
We study Bayesian optimization in a time-varying environment where the unknown reward function evolves according to a Gaussian process drift model. Existing GP-UCB analyses in this setting typically require the exploration parameter to grow with the horizon to maintain uniform confidence bounds. Using per-round local confidence events, we show that GP-UCB can instead be run with a constant exploration parameter and obtain an expected-regret bound whose coefficient depends on the drift rate. We also derive a sharper time-varying maximum-information-gain bound. For the squared exponential kernel, it yields γ~T/T=O(ε1/2) and expected average regret O(ε1/4) in the persistent-drift regime. The same constant-exploration analysis also yields realized-regret guarantees. Simulations support the predicted logarithmic dependence of the bound-suggested exploration parameter on 1/ε.
Matthias Mandl, Hanne Kekkonen
Delft Institute of Applied Mathematics Delft University of Technology Mekelweg 4, 2628 CD, Delft
We study new algorithms for Contextual Bandits with Knapsack. In these problems, there are finitely many types of customers, products, and resources. Each product is made from a fixed combination of resources, and resources have finite capacity. A decision maker must assign each arriving customer one out of a set of multiple possible products. Every assignment of a customer to a product will generate a random reward, which equals an unknown linear function of customer and product features, plus a noise term. The objective is to jointly learn the mean reward function, and to make online assignments to minimize the expected revenue loss relative to an optimal policy that knows the reward function. We propose a natural and simple extension of the Upper-Confidence-Bound (UCB) family of algorithms and apply re-optimization techniques. We show that by taking advantage of re-optimization, our algorithm achieves an average regret of O(T(lnT)3) where T is the horizon length. Our bound significantly reduces the O(T1) bound in the literature for closely related dynamic-pricing problems that are based on re-optimization.
Zhen Xu
Management School, University of Liverpool, Liverpool, United Kingdom