PaperlayerView exact revision on arXiv

Source-linked AI summary

Misspecified Gaussian Process Bandit Optimization

Ilija Bogunovic, Andreas Krause

arXiv:2111.05008v1cs.LGcs.AIstat.ML

TL;DR

Kernelized bandit methods often assume the objective is well-specified in a bounded-norm RKHS, although practical objectives may only be approximated by that class. This paper develops GP-bandit algorithms for known and unknown misspecification, with regret bounds that depend on its magnitude. It also extends the approach to stochastic contextual settings with unknown misspecification.

  • Problem

    Kernelized bandit analyses typically assume exact realizability in a known RKHS, while practical objectives may only be approximately represented by the assumed class.

    Source: §1 · p. 1

  • Method

    The paper develops EC-GP-UCB for known misspecification and Phased GP Uncertainty Sampling for unknown misspecification, plus a regret-bound-balancing extension for stochastic contextual settings.

    Source: §1 · pp. 2–3

  • Results

    The algorithms achieve regret bounds depending on misspecification, horizon, and kernel; the unknown-error method attains misspecified rates up to polylogarithmic factors and standard guarantees when ε = 0.

    Source: §1 · pp. 2–3

  • Takeaways & Limitations

    Phased GP Uncertainty Sampling adapts to unknown misspecification, while the contextual combination attains previous regret bounds up to additive lower-order terms.

    Source: §1 · p. 3

    EC-GP-UCB requires the misspecification error ε as input, and the passage leaves adaptation for unknown ε to a separate algorithm.

    Source: §3.2 · p. 6

Abstract

from arXiv · show

We consider the problem of optimizing a black-box function based on noisy bandit feedback. Kernelized bandit algorithms have shown strong empirical and theoretical performance for this problem. They heavily rely on the assumption that the model is well-specified, however, and can fail without it. Instead, we introduce a \emph{misspecified} kernelized bandit setting where the unknown function can be $\epsilon$--uniformly approximated by a function with a bounded norm in some Reproducing Kernel Hilbert Space (RKHS). We design efficient and practical algorithms whose performance degrades minimally in the presence of model misspecification. Specifically, we present two algorithms based on Gaussian process (GP) methods: an optimistic EC-GP-UCB algorithm that requires knowing the misspecification error, and Phased GP Uncertainty Sampling, an elimination-type algorithm that can adapt to unknown model misspecification. We provide upper bounds on their cumulative regret in terms of $\epsilon$, the time horizon, and the underlying kernel, and we show that our algorithm achieves optimal dependence on $\epsilon$ with no prior knowledge of misspecification. In addition, in a stochastic contextual setting, we show that EC-GP-UCB can be effectively combined with the regret bound balancing strategy and attain similar regret bounds despite not knowing $\epsilon$.

1 Introduction

Kernelized bandits exploit reward correlations by assuming the objective is well-specified in a bounded-norm RKHS, but real applications may violate that assumption. This paper studies misspecified GP bandits and proposes algorithms for known and unknown misspecification, including a stochastic contextual extension.

1 Introduction

  • Kernelized bandits use smooth, low-norm RKHS functions to model reward correlations, but standard analyses often assume exact realizability despite practical sources of misspecification.Incorrect kernel choice, an overly smooth function class, and hyperparameter estimation errors are cited as possible sources.Source: §1 · p. 1
  • The paper studies objectives that are uniformly within ε of a bounded-norm RKHS function and proposes GP-bandit regret bounds depending on ε, the horizon, and the kernel.Its main uncertainty-sampling algorithm does not require knowing ε and recovers standard regret rates when ε = 0.Source: §1 · p. 2
  • The approach uses standard closed-form GP posterior or kernelized ridge-regression mean and variance estimators, and supports infinite action sets with off-the-shelf global optimization solvers.Unlike related misspecified-kernel work [8], it does not require robust estimators.Source: §1 · pp. 2–3
  • For known ε, EC-GP-UCB enlarges confidence bounds and achieves cumulative regret O(B√γT), while a lower bound shows Ω(Tε) regret is unavoidable in the general kernelized setting.The supplied passage gives the bound in this form; it does not specify additional factors.Source: §1 · p. 3
  • For unknown ε, Phased GP Uncertainty Sampling uses uncertainty sampling and phased exploration to attain the misspecified regret rates up to polylogarithmic factors, and standard guarantees when ε = 0.The method is described as an elimination-type algorithm that adapts to unknown misspecification.Source: §1 · p. 3
  • In stochastic contextual settings, EC-GP-UCB combined with regret-bound balancing attains previous regret bounds up to additive lower-order terms, despite unknown ε.The balancing strategy is from [33].Source: §1 · pp. 2–3

2 Problem statement

The problem is sequential maximization of a black-box objective over a known compact action set using noisy feedback. The learner assumes the objective is uniformly approximable by a bounded-norm RKHS function, and seeks to minimize cumulative regret even when that approximation is imperfect.

2 Problem statement

  • At each round, the learner chooses an action from a known compact set and receives a noisy observation of the black-box objective.The objective is defined over D ⊂ R^d, with independent σ-sub-Gaussian noise assumed in the supplied passage.Source: §2 · p. 3
  • The learner knows the kernel and norm bound B and assumes the objective is within ε in max norm of a function in the bounded-norm RKHS class.The true function need not itself belong to the RKHS and may have a substantially larger RKHS norm.Source: §2 · p. 3
  • With a continuous universal kernel, any continuous objective on D satisfies the approximation assumption for ε > 0 when the RKHS norm bound is suitably large.This is identified as a difference from the previously studied misspecified linear setting.Source: §2 · p. 3
  • In the most general variant, ε is unknown, and the desired algorithm must adapt to any ε > 0, including the realizable case ε = 0.The learner is provided the domain, kernel, and norm bound as inputs.Source: §2 · p. 4
  • The learner minimizes cumulative regret against the true objective’s best action, while the model permits an unknown fixed misspecification function bounded in magnitude by ε.The passage states that the regret definitions differ by at most 2εT, with no significant impact on the main-bound scaling because R*_T = Ω(εT).Source: §2 · p. 4

3 Algorithms for misspecified kernelized bandits

The section develops GP-bandit methods for functions that are only uniformly approximated by the assumed RKHS class. It presents optimistic confidence-bound and phased uncertainty-sampling approaches, with the latter adapting to unknown misspecification.

3.1 Learning with Gaussian Processes

  • Standard GP-UCB confidence bounds can fail under misspecification, while maximum information gain characterizes kernel-dependent regret and scales sublinearly for common kernels.The GP posterior mean and variance yield confidence bounds in the realizable setting; those bounds are no longer valid in the misspecified setting.Source: §3.1 · p. 5

3.2 Known misspecification error and optimistic approaches

  • With known ε, EC-GP-UCB enlarges confidence bounds to account for the biased mean estimator, adding an exploration bonus to standard GP-UCB.Its regret bound contains the standard GP-UCB term and an εT dependence, which is unavoidable in general for misspecified kernelized bandits.Source: §3.2 · p. 6

3.3 Unknown misspecification error: Phased GP Uncertainty Sampling

  • Phased GP Uncertainty Sampling doubles episode lengths, samples actions by posterior uncertainty, and eliminates actions whose hallucinated bounds appear suboptimal.Although the optimal action may be eliminated, the analysis shows a near-optimal action remains after each episode.Source: §3.3 · pp. 6–7
  • Its sequential kernel-ridge-regression acquisition rule maximizes GP posterior variance without finite-dimensional kernel-feature approximations or per-episode near-optimal design computation.The rule supports infinite-dimensional RKHS settings and admits efficient iterative posterior-variance updates.Source: §3.3 · p. 7
  • Phased GP Uncertainty Sampling matches the EC-GP-UCB regret guarantee without knowing ε and applies to infinite action sets.For a linear kernel, it recovers the misspecification regret rate of [24].Source: §3.3 · p. 8

4 Algorithm for the contextual misspecified kernelized bandit setting

For stochastic contextual action sets, the section combines EC-GP-UCB base algorithms with regret-bound balancing. This obtains a contextual regret bound close to the known-ε EC-GP-UCB bound without requiring the true misspecification parameter.

4 Algorithm for the contextual misspecified kernelized bandit setting

  • At each round, the learner observes an i.i.d. stochastic context defining an action set that may differ across rounds.The reward is the unknown function value plus independent 1-sub-Gaussian noise.Source: §4 · p. 8
  • The base algorithms are EC-GP-UCB instances with different candidate misspecification values, trading greater robustness against excessive exploration.The candidates are chosen on a geometric grid; smaller indices use larger, more conservative misspecification values.Source: §4 · p. 8
  • The master balances candidate regret bounds across active base algorithms and eliminates an algorithm only when observations indicate its bound is inconsistent.The elimination condition is designed so that no consistent algorithm is eliminated with high probability.Source: §4 · p. 9
  • The contextual regret bound recovers the known-ε EC-GP-UCB bound up to polylogarithmic factors and an additive lower-order term.The result is for the misspecified contextual setting with stochastic action sets.Source: §4 · pp. 9–10

5 Conclusion

The paper addresses GP-bandit optimization with a misspecified hypothesis class and presents algorithms for standard and contextual settings. It identifies misspecified GP priors as a direction for future work.

5 Conclusion

  • The paper develops algorithms for GP-bandit optimization with a misspecified hypothesis class.The conclusion highlights enlarged confidence bounds, phased epistemic uncertainty sampling, and regret bound balancing.Source: §5 · p. 10
  • The proposed ideas address standard settings with known or unknown misspecification error and contextual settings.Source: §5 · p. 10
  • Developing algorithms and regret bounds for misspecified GP priors remains a future research direction.Source: §5 · p. 10

Supplementary Material Misspecified GP Bandit Optimization

The supplementary material is attributed to Ilija Bogunovic and Andreas Krause and identifies NeurIPS 2021.

Supplementary Material Misspecified GP Bandit Optimization

A GP bandits: Useful definitions and auxiliary results (Realizable setting)

This section sets out definitions and auxiliary results for the realizable GP-bandit setting, including the RKHS hypothesis class, observation noise, and maximum information gain.

A GP bandits: Useful definitions and auxiliary results (Realizable setting)

B.1 EC-GP-UCB with known misspecification

The theorem gives a high-probability regret guarantee for EC-GP-UCB under bounded uniform approximation error, using enlarged confidence bounds when the error is known.

B.1 EC-GP-UCB with known misspecification

  • With probability at least 1 − δ, EC-GP-UCB achieves the stated regret bound when the function is within ε in max norm of the assumed class and ε is known.Source: §B.1 · p. 15
  • The theorem applies to a hypothesis class Fk(D; B) with fixed B > 0 and an unknown function defined on D.Source: §B.1 · p. 15
  • The proof uses enlarged confidence bounds and EC-GP-UCB’s selection rule to bound cumulative regret.Source: §B.1 · p. 15

B.2 EC-GP-UCB and unknown misspecification

The analysis explains why EC-GP-UCB’s known-misspecification analysis cannot be repeated when ε is unknown. A separate lower-bound construction shows that Ω(εT) regret is unavoidable in the general kernelized setting.

B.2 EC-GP-UCB and unknown misspecification

  • When ε is unknown, the learner cannot choose the parameter needed to repeat the preceding EC-GP-UCB analysis.The section identifies this as the obstacle to applying the known-ε analysis.Source: §B.2 · p. 15
  • The analysis controls the first two terms of its bound, but identifies the final term as the remaining obstacle.The passage introduces that term as a sum over T, but does not provide its full expression here.Source: §B.2 · p. 16

C Optimal dependence on misspecification parameter

  • Ω(εT) regret is unavoidable: a function that is zero almost everywhere can hide an ε-sized optimum at a single point.In the noiseless construction, sampling that point is a zero-probability event, despite an ε-close bounded-RKHS function.Source: C Optimal dependence on… · p. 16

D Proofs from Section 3.3 (Phased GP Uncertainty Sampling)

The proof establishes a high-probability regret bound for Phased GP Uncertainty Sampling when the objective is uniformly approximable by a bounded-norm RKHS function. It proceeds through estimator control, episode-wise elimination, and cumulative regret accounting.

D Proofs from Section 3.3 (Phased GP Uncertainty Sampling)

  • Under uniform ε-approximation by a function in the bounded-norm RKHS class, Theorem 2 gives Phased GP Uncertainty Sampling a regret bound with probability at least 1 − δ.The supplied passage does not include the bound’s expression.Source: D Proofs from Section 3.3 (Phased GP… · p. 17
  • The proof first controls the misspecified posterior mean against the best-in-class function at episode ends, using estimator-comparison lemmas and information gain.The episode-wise control applies to points remaining in the active set.Source: D Proofs from Section 3.3 (Phased GP… · pp. 17–18
  • Elimination may discard the episode’s optimal point, but the retention rule keeps a point whose function value is close to that optimum.The proof tracks the retained point against the point that may be eliminated.Source: D Proofs from Section 3.3 (Phased GP… · p. 18
  • Cumulative regret accounting combines episode regrets and bounds regret against the true objective using R*_T ≤ R_T + 2εT.The proof considers at most ⌈log2 T⌉ episodes and completes the bound by upper-bounding β_T.Source: D Proofs from Section 3.3 (Phased GP… · pp. 19–20

E Contextual misspecified setting results

The contextual analysis combines EC-GP-UCB with a regret-bound balancing master algorithm, using candidate bounds for its base learners. The resulting guarantee preserves a constant-factor relation to the realizable-case bound for a consistent candidate.

E Contextual misspecified setting results

  • The balancing master plays base algorithms according to candidate regret bounds and eliminates algorithms whose bounds cease to be valid.The cited theorem requires the base regret bounds to have a specified form and identifies a consistent base algorithm.Source: E Contextual misspecified setting… · p. 20
  • For EC-GP-UCB, the contextual analysis uses a candidate upper bound that replaces γ_Ni(t) with γ_T because γ_T ≥ γ_Ni(t).The proof also chooses constants independent of the number of times a base algorithm has been played.Source: E Contextual misspecified setting… · p. 20
  • The consistent candidate’s regret bound is only a constant factor away from the bound when ε = 0.The result is stated after applying the balancing theorem and taking a union bound.Source: E Contextual misspecified setting… · p. 20

Related papers

Loading 2111.05008v1…