PaperlayerView exact revision on arXiv

Source-linked AI summary

On Kernelized Multi-armed Bandits

Sayak Ray Chowdhury, Aditya Gopalan

arXiv:1704.00445v2cs.LG

TL;DR

The paper studies stochastic bandit optimization with continuous arms and a fixed, unknown reward function. It develops IGP-UCB and GP-TS using GP-based uncertainty machinery, together with a new infinite-dimensional self-normalized concentration inequality. The algorithms receive regret guarantees under bounded-RKHS-norm assumptions and show favorable empirical performance in synthetic and real-world environments, while GP-TS analysis retains a discretization-dependent logarithmic term.

  • Problem

    The paper addresses sequentially maximizing a fixed but unknown reward function over a potentially infinite decision set using noisy, partial observations.

  • Method

    It develops IGP-UCB and nonparametric GP-TS, supported by GP posterior modeling and a new self-normalized concentration inequality for possibly infinite-dimensional vector-valued martingales.

  • Results

    The proposed algorithms have regret bounds for bounded-RKHS-norm reward functions and show favorable performance in many synthetic and real-world evaluations.

  • Takeaways & Limitations

    The work improves GP-UCB for continuous bandit optimization and provides a regret analysis for nonparametric Thompson sampling in the agnostic setting.

  • Takeaways & Limitations

    The GP-TS regret bound contains an extra logarithmic dependency from discretization, whose removal remains open.

Abstract

from arXiv · show

We consider the stochastic bandit problem with a continuous set of arms, with the expected reward function over the arms assumed to be fixed but unknown. We provide two new Gaussian process-based algorithms for continuous bandit optimization-Improved GP-UCB (IGP-UCB) and GP-Thomson sampling (GP-TS), and derive corresponding regret bounds. Specifically, the bounds hold when the expected reward function belongs to the reproducing kernel Hilbert space (RKHS) that naturally corresponds to a Gaussian process kernel used as input by the algorithms. Along the way, we derive a new self-normalized concentration inequality for vector- valued martingales of arbitrary, possibly infinite, dimension. Finally, experimental evaluation and comparisons to existing algorithms on synthetic and real-world environments are carried out that highlight the favorable gains of the proposed strategies in many cases.

1. Introduction

The paper addresses continuous-arm bandit optimization, where noisy feedback and potentially infinite decision sets make exploration difficult. It introduces IGP-UCB, GP-TS, and an infinite-dimensional concentration inequality, with experiments reporting favorable performance in many settings.

  • Motivation: Continuous-arm optimization must transfer information from finitely many noisy observations to potentially infinitely many decisions.The motivation spans dynamic pricing, continuous-state reinforcement learning, and wireless power control.
  • Problem setting: The reward function is assumed to lie in an RKHS with bounded norm, imposing smoothness on the continuous-arm problem.This structure enables learning about many arms from observations at selected arms.
  • Contributions: IGP-UCB is a GP-UCB variant with a reduced confidence interval width and an order-wise regret improvement over GP-UCB.The paper also reports markedly improved numerical performance over GP-UCB.
  • Contributions: GP-TS is a nonparametric Thompson-sampling algorithm with a regret bound for the agnostic nonparametric setting.The authors describe this as the first known regret bound for Thompson sampling in that setting.
  • Contributions: A new self-normalized concentration inequality for possibly infinite-dimensional vector-valued martingales supports the design and analysis of both algorithms.The inequality generalizes a corresponding finite-dimensional martingale bound.
  • Evaluation: Empirical comparisons on synthetic and real-world setups report performance improvements for the proposed algorithms, including under misspecification.The conclusion likewise states that the algorithms perform well in practice.

2. Problem Statement

The problem is sequentially maximizing a fixed but unknown reward function over a potentially infinite continuous decision set using noisy, causally observed rewards. Sublinear cumulative regret requires compactness and RKHS-based smoothness and boundedness assumptions.

  • Problem formulation: At each round, the algorithm selects an action from D and observes a noisy reward f(x_t) + ε_t based on prior history.The objective is to maximize the fixed unknown function f over the decision set.
  • Noise and modeling: The framework permits conditionally R-sub-Gaussian martingale-difference noise, rather than requiring the Gaussian noise model used for algorithm design.This distinguishes the fixed RKHS reward function from the misspecified GP prior and likelihood.
  • Regret: Cumulative regret sums the instantaneous losses f(x⋆) − f(x_t), and sublinear growth implies vanishing per-round regret.The maximum point x⋆ is assumed to be attained.
  • Regularity assumptions: The analysis assumes a compact domain and a reward function with finite norm in the RKHS induced by a positive semidefinite kernel.The RKHS norm measures smoothness relative to the kernel.
  • Regularity assumptions: The unknown function has known RKHS-norm bound ∥f∥_k ≤ B, while the kernel satisfies k(x,x) ≤ 1.Squared Exponential and Matérn kernels are given as examples satisfying the bounded-variance property.

3. Algorithms

The algorithms use GP posterior quantities as uncertainty estimates while analyzing fixed RKHS reward functions under potentially misspecified noise models. IGP-UCB selects optimistic actions, whereas GP-TS samples posterior functions and optimizes them over decision sets.

  • Design philosophy: The design uses Gaussian likelihoods and GP priors to represent uncertainty over reward functions.These models provide posterior means and covariance information for the algorithms.
  • GP posterior: Conditioning on observed history yields a GP posterior with mean μ_t and variance scaled by v^2σ_t^2(x) at each arm.The posterior is computed from the observed rewards and kernel matrix.
  • Model relationship: The GP model is only an algorithm-design aid; the true reward function is a fixed RKHS member and the noise may be non-Gaussian sub-Gaussian.Thus the analysis operates in an agnostic or misspecified setting.
  • IGP-UCB: IGP-UCB combines posterior mean and standard deviation to construct an upper confidence envelope and chooses the action maximizing it.Its confidence parameter uses the RKHS bound, noise parameter, confidence level, and information gain.
  • IGP-UCB: The information-gain quantity γ_t is the maximum mutual information between observations and function values over t-point subsets of D.For compact subsets of R^d, the paper gives kernel-dependent growth rates for Squared Exponential and Matérn kernels.
  • IGP-UCB: IGP-UCB reduces the GP-UCB confidence width by roughly O(ln^3/2 t) at each round.The paper presents this adjustment as producing better theoretical and empirical performance than GP-UCB.
  • GP-TS: GP-TS samples a random function from a time-varying GP posterior and selects the arm maximizing that sample over a decision set D_t.The decision set may be a suitable discretization of D for the stated regret analysis.

4. Main Results

The paper develops concentration tools and regret analyses for kernelized bandit algorithms in potentially infinite-dimensional RKHS settings. Its results characterize IGP-UCB and GP-TS, compare them with prior methods, and identify discretization and dimensionality trade-offs.

  • Concentration inequalities: A new self-normalized concentration inequality handles vector-valued martingales in possibly infinite-dimensional RKHSs.It generalizes the finite-dimensional result of Abbasi-Yadkori et al. and normalizes martingale differences using a sequence-dependent operator.
  • Concentration inequalities: The double-mixture construction over Gaussian-process function space and real sequences overcomes the failure of finite-dimensional mixture arguments in infinite dimensions.The finite-dimensional argument has growing dependence on feature dimension and cannot directly accommodate the time-varying self-normalizing factor.
  • IGP-UCB analysis: IGP-UCB improves GP-UCB's regret by a multiplicative O(ln3/2 T) factor and shows significantly better numerical performance on synthetic and real-world sensor data.The improvement follows from reducing the confidence-interval width by roughly O(ln3/2 t) at each round while allowing conditionally sub-Gaussian noise.
  • GP-TS analysis: GP-TS has a regret bound based on discretized decision sets, with an additional multiplicative dimension-dependent factor compared with IGP-UCB.The discretization uses compact convex domains and sets Dt chosen so that nearby points approximate function values within 1/t2.
  • GP-TS analysis: Removing GP-TS's extra logarithmic dependence on discretization remains an open question.The additional d ln(BdT) term in the regret bound is attributed essentially to discretization.
  • GP-TS analysis: GP-TS provides the first known frequentist regret guarantee for Thompson sampling in the agnostic, nonparametric setting with infinite action spaces.Its bound is inferior to IGP-UCB in its dependence on dimension d, while KernelUCB's guarantee requires finitely many actions.

5. Overview of Techniques

The paper’s proofs combine self-normalized concentration, Gaussian-process mixture martingales, stopping-time arguments, and information-gain bounds to control regret for IGP-UCB and GP-TS.

  • Concentration inequality: The proof overview derives a self-normalized concentration result using super-martingales, mixture martingales, Markov’s inequality, and stopping-time constructions.The mixture integrates over functions drawn from an independent GP, inducing a Gaussian distribution over observed function values.
  • Technical assumptions: Theorem 1’s proof assumes invertible induced kernel matrices at its core, while a related construction handles the zero-noise case when matrices remain positive definite.The argument begins from sub-Gaussian noise and constructs a GP-based mixture over function space.
  • Concentration inequality: The mixture martingale remains a non-negative super-martingale with expectation at most one, including at stopping times.This property enables uniform-in-time control through a stopping-time argument.
  • IGP-UCB: The IGP-UCB proof bounds instantaneous regret by 2β_tσ_t−1(x_t), then controls cumulative uncertainty through information gain.The analysis uses the RKHS norm bound and the relation between log-determinants and γ_t.
  • GP-TS: The GP-TS proof separates saturated and unsaturated arms, showing that unsaturated-arm regret can be bounded through posterior standard deviations.The cumulative uncertainty term is controlled by O(√Tγ_T).

6. Experiments

Experiments compare GP-UCB, IGP-UCB, GP-TS, GP-EI, and GP-PI across synthetic, benchmark, and sensor-data settings, with performance varying by environment and kernel specification.

  • Experimental setup: The experiments compare GP-UCB, IGP-UCB, GP-TS, GP-EI, and GP-PI on synthetic and real-world environments.The synthetic tests include RKHS-generated functions, GP-sampled functions, Rosenbrock, and Hartman3; real-world tests use temperature and light-sensor data.
  • Synthetic functions: The fixed unknown-target-function experiment is described as the harder agnostic setting, and its relative method performance is similar to the preceding RKHS experiment.A separate GP-sampled-function experiment uses 25 random functions for both Squared Exponential and Matérn kernels.
  • Benchmark functions: On Rosenbrock and Hartman3, GP-EI/PI perform better than the remaining methods.The comparison uses cumulative regret over 25 independent trials with a Squared Exponential kernel.
  • Robustness: The authors conjecture that UCB- and TS-based algorithms are less robust to kernel choice than EI/PI.This is presented as a conjecture based on the benchmark-function results, not as a proved conclusion.
  • Real-world data: GP-TS performs better than the other methods on the light-sensor data, while IGP-UCB performs better than GP-EI/PI.The light-sensor dataset contains 41 sensor locations, 601 training samples, and 192 test samples.

7. Conclusion

The conclusion presents IGP-UCB and GP-TS as improved methods for bandit optimization, reports good empirical performance, and identifies adaptive kernels, time variation, reinforcement learning, and computation as open directions.

  • Contributions: The paper improves GP-UCB for bandit optimization and introduces GP-TS.These are the two central algorithmic contributions stated in the conclusion.
  • Empirical findings: The proposed algorithms perform well in practice on synthetic and real-world data.The conclusion summarizes the empirical findings without specifying a single benchmark or metric.
  • Future directions: The conclusion identifies learning an initially unknown kernel adaptively as an interesting case for future work.It also points to time-varying RKHS functions and general reinforcement learning with GP techniques.
  • Open questions: Computational questions remain for optimizing functions drawn from Gaussian processes.The conclusion explicitly lists computational aspects among the open questions.

A. Proof of Theorem 1

Theorem 1 is proved by constructing exponential super-martingales, mixing them over a Gaussian process, and extending fixed-time control to all times through stopping times.

  • Super-martingale construction: For a fixed function and noise sequence, the proof constructs a non-negative super-martingale using sub-Gaussian noise.Its expectation is controlled through conditional sub-Gaussianity and measurability.
  • Stopping times: The proof handles random stopping times because quantities such as ε_1:t become random at the stopping time.The stopping-time expectation remains bounded by one.
  • GP mixture: A GP mixture over functions in R^D induces a multivariate Gaussian distribution with covariance K_t over sampled function values.The noisy observation vector has distribution N(0, K_t + ηI), which remains invertible with η>0.
  • Uniform control: Markov’s inequality and a stopping-time construction convert the martingale expectation bound into a simultaneous high-probability result over time.The argument first bounds the bad event at a stopping time, then lifts the control to all t.
  • Kernel representation: The feature-space representation defines Φ_t and V_t, connecting the infinite-dimensional formulation to kernel-matrix expressions.The proof also notes that positive-definite K_t permits the η=0 construction.

B. Information Theoretic Results

The analysis relates information gain to posterior predictive uncertainty for points selected by the algorithms, using mutual information and entropy calculations. These relationships support bounds on cumulative predictive standard deviations.

  • Information gain: Lemma 3 establishes an almost-sure information-gain bound for the points selected by Algorithms 1 and 2.This lemma supplies the algorithm-specific control used in subsequent results.
  • Information gain: The maximum information gain γt bounds the mutual information between observed rewards and the unknown function for any t selected points.The information gain is defined through mutual information and maximized over subsets of the decision domain.
  • Information gain: The mutual information decomposes through the entropy chain rule into per-round terms involving posterior predictive variance σ^2_t−1(xs).Conditionally, the reward at round s has Gaussian variance proportional to λ + σ^2_s−1(xs).
  • Predictive uncertainty: Lemma 4 expresses the sum of predictive standard deviations at selected points in terms of maximum information gain.The proof uses Cauchy–Schwarz, the variance bound σ^2_t−1(x) ≤ 1, λ = 1 + η, and η = 2/T.

C. Proof of Theorem 2

The proof represents the RKHS reward function through kernel feature maps and decomposes posterior estimation error into function and noise terms. A self-normalized concentration result then yields a high-probability confidence bound.

  • RKHS representation: The RKHS reproducing property represents f(x) as an inner product with the kernel feature map ϕ(x), while kernel evaluations become feature-map inner products.The same representation yields Kt = ΦtΦT_t and f1:t = Φtf.
  • Error decomposition: The posterior variance satisfies σ^2_t(x) = k(x,x) − kt(x)^T(Kt + λI)^−1kt(x), linking uncertainty to the kernel matrix.This identity follows from the feature-space matrix expression and the kernel definitions.
  • Error decomposition: The posterior mean error is decomposed into an RKHS function term and a noise term involving kt(x)^T(Kt + λI)^−1ε1:t.The posterior mean is written using y1:t = f1:t + ε1:t.
  • Confidence bound: With probability at least 1 − δ, the concentration argument yields |µt(x) − f(x)| ≤ σt(x) after choosing η = 2/T.The proof uses λ = 1 + η and determinant identities to control the noise contribution through information gain.

D. Analysis of IGP-UCB (Theorem 3)

The IGP-UCB analysis uses optimistic action selection together with confidence bounds to relate the chosen action's performance to the optimum and posterior uncertainty.

  • IGP-UCB action selection: At each round, IGP-UCB selects an action whose upper confidence value is at least that of the optimal action.The confidence inequalities bound the optimal reward above and the selected action's estimation error below.
  • IGP-UCB regret: With high probability, the instantaneous regret is controlled by the confidence width at the selected action.The result follows by combining the selection inequality with the confidence bounds for f.

E. Analysis of GP-TS (Theorem 4)

The GP-TS analysis combines discretization, saturated-point arguments, Gaussian anti-concentration, and martingale concentration to control sampling regret. The proof also develops recursive posterior updates for implementation.

  • Posterior sampling: Gaussian anti-concentration ensures that, conditional on the history, posterior samples can exceed confidence thresholds with a fixed positive probability.The sampled function at each point is Gaussian with posterior mean µt−1(x) and standard deviation vtσt−1(x).
  • Discretization and saturation: The analysis defines confidence events and saturated points within a round-dependent discretization of the decision domain.The closest discretized point to the optimum is unsaturated, while saturated points have regret exceeding a variance-scaled threshold.
  • Posterior sampling: When the relevant confidence events hold, GP-TS either selects an unsaturated point or incurs a controlled instantaneous regret.The argument compares sampled values on saturated points with the sampled value at the discretized point nearest the optimum.
  • Cumulative regret: A super-martingale construction and Azuma–Hoeffding inequality convert conditional regret bounds into a high-probability cumulative-regret statement.The proof uses a union bound to combine the confidence-event probability with the martingale concentration event.
  • Cumulative regret: The theorem-level result holds with probability at least 1 − δ over a horizon T and includes terms involving B, cT, and T.The supplied result passages state the probability and component terms but do not display the complete bound in one passage.
  • Implementation: Recursive Schur-complement updates compute posterior means and covariances from previous quantities, making the algorithms easier to implement.The update identities use A = Kt−1 + λI and the new point xt to update kernel quantities without recomputing the full expressions.
Loading 1704.00445v2…