10 papers
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…
Revisiting the Bertrand Paradox via Equilibrium Analysis of No-regret Learners
Arnab Maiti, Junyan Liu, Kevin Jamieson +1
We study the discrete Bertrand pricing game with a non-increasing demand function. The game has players who simultaneously choose prices from the set $\{1/k, 2/k, \ldots,…
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…
On the Power of Adaptivity for -Best Arm Identification in Linear Bandits
Arnab Maiti, Yunbei Xu, Kevin Jamieson
We study the minimax sample complexity of -best arm identification in linear bandits. Given a compact action set that spans and an unknown…
On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits
Leo Maynard-Zhang, Zhihan Xiong, Kevin Jamieson +1
We study the fixed-budget best-arm identification (BAI) problem in non-stationary linear bandits. Concretely, given a fixed time budget , finite arm set $\mathcal{…
Efficient Uncoupled Learning Dynamics with Last-Iterate Convergence in Bilinear Saddle-Point Problems over Convex Sets under Bandit Feedback
Arnab Maiti, Claire Jie Zhang, Kevin Jamieson +3
In this paper, we study last-iterate convergence of learning algorithms in bilinear saddle-point problems, a preferable notion of convergence that captures the day-to-day behavior…