5 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…
Batched Stochastic Linear Bandits with 1-Bit Communication Constraints
Ivan Lau, Daniel McMorrow, Kevin Jamieson +1
We study stochastic linear bandits under a natural combination of batching and communication constraints: the time horizon is partitioned into batches of equal size , and during…
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…
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…