6 papers
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…
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…
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…
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…