8 papers
A General Lower Bound for Kernel Bandits
Chenkai Ma, Jonathan Scarlett
The kernel bandit problem consists of sequentially optimizing an unknown function with noisy feedback, where the function has bounded norm in a given Reproducing Kernel Hilbert Spa…
Non-Adaptive 1-Bit Mean Estimation: Minimax Rates and the Sample-Interval Tradeoff
Ivan Lau, Jonathan Scarlett
We study distributed one-dimensional mean estimation under a 1-bit communication constraint. Each agent observes one sample, drawn independently from an unknown distribution, and r…
Open Problem: Is Interaction Necessary for Order-Optimal 1-bit Mean Estimation?
Ivan Lau, Jonathan Scarlett
We ask whether interaction is necessary for order-optimal 1-bit mean estimation over nonparametric finite-moment classes. Adaptive threshold-query protocols achieve the order-optim…
Near-Optimal Regret in Adversarial Kernel Bandits
Yu-Jie Zhang, Hao Qiu, Jonathan Scarlett +1
We study the adversarial kernel bandit problem, in which the loss at each round is induced by an arbitrary bounded element of a reproducing kernel Hilbert space (RKHS). We propose…
Order-Optimal Sequential 1-Bit Mean Estimation in General Tail Regimes
Ivan Lau, Jonathan Scarlett
In this paper, we study the problem of mean estimation under 1-bit communication constraints. We propose a novel adaptive mean estimator based solely on randomized threshold querie…
Batched Kernelized Bandits: Refinements and Extensions
Chenkai Ma, Keqin Chen, Jonathan Scarlett
In this paper, we consider the problem of black-box optimization with noisy feedback revealed in batches, where the unknown function to optimize has a bounded norm in some Reproduc…
Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity
Ivan Lau, Jonathan Scarlett
In this paper, we study the problem of distributed mean estimation with 1-bit communication constraints. We propose a mean estimator that is based on (randomized and sequentially-c…
Quantile Multi-Armed Bandits with 1-bit Feedback
Ivan Lau, Jonathan Scarlett
In this paper, we study a variant of best-arm identification involving elements of risk sensitivity and communication constraints. Specifically, the goal of the learner is to ident…