mlsanityData to 7 Oct 2026

Kernel ε-Greedy for Multi-Armed Bandits with Covariates

arXiv 2306.17329 ↗First posted 29 Jun 2023stat.ML cs.LG math.STcited by 0

Not on the map. Why?

Abstract (arXiv)

We consider the ε-greedy strategy for the multi-arm bandit with covariates (MABC) problem, where the mean reward functions are assumed to lie in a reproducing kernel Hilbert space (RKHS). We propose to estimate the unknown mean reward functions using an online weighted kernel ridge regression estimator, and show the resultant estimator to be consistent under appropriate decay rates of the exploration probability sequence, εtt, and regularization parameter, λtt. Moreover, we show that for any choice of kernel and the corresponding RKHS, we achieve a sub-linear regret rate depending on the intrinsic dimensionality of the RKHS. Furthermore, we achieve the optimal regret rate of √T under a margin condition for finite-dimensional RKHS.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 21 of its 53 references that are in the map. First posted on arXiv 29 Jun 2023.

Builds on

21 of 53 references.

References · 21

  1. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  2. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 156
  3. 2015Multi-armed Bandit Models for the Optimal Design of Clinical Trials: Benefits and Challengescited by 113
  4. 2017Mostly Exploration-Free Algorithms for Contextual Banditscited by 85
  5. 2017Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimizationcited by 77
  6. 2018A Contextual Bandit Bake-offcited by 64
  7. 2014Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithmscited by 59
  8. 2021High-Dimensional Experimental Design and Kernel Banditscited by 55
  9. 2021Misspecified Gaussian Process Bandit Optimizationcited by 52
  10. 2013Thompson Sampling for Complex Bandit Problemscited by 43
  11. 2020Bandit optimisation of functions in the Mat'ern kernel RKHScited by 40
  12. 2018Balanced Linear Contextual Banditscited by 30
9 more
  1. 2020On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimizationcited by 29
  2. 2022Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximationcited by 29
  3. 2019Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimescited by 25
  4. 2020Statistical Inference for Online Decision-Making: In a Contextual Bandit Settingcited by 17
  5. 2019Randomized Allocation with Nonparametric Estimation for Contextual Multi-Armed Bandits with Delayed Rewardscited by 15
  6. 2021Pure Exploration in Kernel and Neural Banditscited by 13
  7. 2021Open Problem: Tight Online Confidence Intervals for RKHS Elementscited by 13
  8. 2023Delayed Feedback in Kernel Banditscited by 10
  9. 2023Adaptation to Misspecified Kernel Regularity in Kernelised Banditscited by 5

Built on by

Not cited yet.