Regret Bounds for Noise-Free Kernel-Based Bandits

• URL: http://arxiv.org/abs/2002.05096v2
• Date: Fri, 24 Jun 2022 12:50:28 GMT
• Title: Regret Bounds for Noise-Free Kernel-Based Bandits
• Authors: Sattar Vakili
• Abstract summary: Kernel-based bandit is an extensively studied black-box optimization problem. We discuss several upper bounds on regret; none of which seem order optimal, and provide a conjecture on the order optimal regret bound.
• Score: 4.924126492174802
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Kernel-based bandit is an extensively studied black-box optimization problem, in which the objective function is assumed to live in a known reproducing kernel Hilbert space. While nearly optimal regret bounds (up to logarithmic factors) are established in the noisy setting, surprisingly, less is known about the noise-free setting (when the exact values of the underlying function is accessible without observation noise). We discuss several upper bounds on regret; none of which seem order optimal, and provide a conjecture on the order optimal regret bound.

Related papers

• Lower Bounds for Time-Varying Kernelized Bandits [43.62161925881489]
  optimization of black-box functions with noisy observations is a fundamental problem with widespread applications. We consider non-stationary scenarios, which are crucial for certain applications but are currently less well-understood. Under $ell_infty$-norm variations, our bounds are found to be close to the state-of-the-art upper bound.
  arXiv  Detail & Related papers  (2024-10-22T04:45:47Z)
• Stochastic Zeroth-Order Optimization under Strongly Convexity and Lipschitz Hessian: Minimax Sample Complexity [59.75300530380427]
  We consider the problem of optimizing second-order smooth and strongly convex functions where the algorithm is only accessible to noisy evaluations of the objective function it queries. We provide the first tight characterization for the rate of the minimax simple regret by developing matching upper and lower bounds.
  arXiv  Detail & Related papers  (2024-06-28T02:56:22Z)
• Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiency [18.17090625880964]
  We study the methodology of exploring the domain using random samples drawn from a distribution. We show that this random exploration approach achieves the optimal error rates.
  arXiv  Detail & Related papers  (2023-10-23T20:30:44Z)
• On the Sublinear Regret of GP-UCB [58.25014663727544]
  We show that the Gaussian Process Upper Confidence Bound (GP-UCB) algorithm enjoys nearly optimal regret rates. Our improvements rely on a key technical contribution -- regularizing kernel ridge estimators in proportion to the smoothness of the underlying kernel.
  arXiv  Detail & Related papers  (2023-07-14T13:56:11Z)
• Misspecified Gaussian Process Bandit Optimization [59.30399661155574]
  Kernelized bandit algorithms have shown strong empirical and theoretical performance for this problem. We introduce a emphmisspecified 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 show that our algorithm achieves optimal dependence on $epsilon$ with no prior knowledge of misspecification.
  arXiv  Detail & Related papers  (2021-11-09T09:00:02Z)
• Optimal Order Simple Regret for Gaussian Process Bandits [6.84224661918159]
  We show that a pure exploration algorithm is significantly tighter than the existing bounds. We show that this regret is optimal up to logarithmically for cases where a lower bound on a kernel is known.
  arXiv  Detail & Related papers  (2021-08-20T16:49:32Z)
• On Information Gain and Regret Bounds in Gaussian Process Bandits [8.499604625449907]
  Consider the optimization of an expensive to evaluate and possibly non- sequential objective function $f$ from noisy feedback observations. For the Matern family of kernels, lower bounds on $gamma_T$, and regret under the frequentist setting, are known.
  arXiv  Detail & Related papers  (2020-09-15T10:15:29Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  We consider algorithm-independent lower bounds for the problem of black-box optimization of functions having a bounded norm. We provide a novel proof technique for deriving lower bounds on the regret, with benefits including simplicity, versatility, and an improved dependence on the error probability.
  arXiv  Detail & Related papers  (2020-08-20T03:48:14Z)
• Corruption-Tolerant Gaussian Process Bandit Optimization [130.60115798580136]
  We consider the problem of optimizing an unknown (typically non-producing) function with a bounded norm. We introduce an algorithm based on Fast-Slow GP-UCB based on "fast but non-robust" and "slow" We argue that certain dependencies cannot be required depending on the corruption level.
  arXiv  Detail & Related papers  (2020-03-04T09:46:58Z)
• Contextual Linear Bandits under Noisy Features: Towards Bayesian Oracles [65.9694455739978]
  We study contextual linear bandit problems under feature uncertainty, where the features are noisy and have missing entries. Our analysis reveals that the optimal hypothesis can significantly deviate from the underlying realizability function, depending on the noise characteristics. This implies that classical approaches cannot guarantee a non-trivial regret bound.
  arXiv  Detail & Related papers  (2017-03-03T21:39:56Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.