arXiv research

Proposes a new semi-parametric framework for batched bandits with covariates.

In this paper, we study the multi-armed bandit problem in the batched setting where the employed policy must split data into a small number of batches. While the minimax regret for the two-armed stochastic bandits has been completely characterized in \cite{perchet2016batched}, the effect of the number of arms on the re…

New study shows non-adaptive trials can be outperformed by adaptive designs in treatment selection.

BLAE solves batched linear bandits with optimal regret and practical performance.

Opt-BBAI identifies the best arm with minimal batches and pulls, optimizing both sample and batch complexity.

New algorithm eliminates arms to minimize regret in complex bandit problems.

New method for identifying best arm in batched multi-armed bandit problems.

The study analyzes batched methods for early stopping in stochastic multi-armed bandits.

We consider the best-arm identification problem in multi-armed bandits, which focuses purely on exploration. A player is given a fixed budget to explore a finite set of arms, and the rewards of each arm are drawn independently from a fixed, unknown distribution. The player aims to identify the arm with the largest expe…

Study quantile multi-armed bandits for identifying the best arm with a specified quantile level.

Paper addresses privacy and robustness in stochastic linear bandits.

Improved batched SH algorithm maintains original performance.

New algorithm tackles batched stochastic linear bandits with 1-bit communication constraints.

The paper tackles best arm identification in contaminated bandits with optimal error guarantees and sample complexity.

Bayesian algorithm improves best-arm identification within fixed budget.

We consider the combinatorial multi-armed bandit (CMAB) problem, where the reward function is nonlinear. In this setting, the agent chooses a batch of arms on each round and receives feedback from each arm of the batch. The reward that the agent aims to maximize is a function of the selected arms and their expectations…

New bandit problem for finding best group of arms with worst mean reward.

Paper tackles robust batched bandits for heavy-tailed rewards.

Paper improves CMAB regret bounds by reducing batch-size dependency.

New algorithm identifies best arm in rested bandit setting.

We present a provably optimal differentially private algorithm for the stochastic multi-arm bandit problem, as opposed to the private analogue of the UCB-algorithm [Mishra and Thakurta, 2015; Tossou and Dimitrakakis, 2016] which doesn't meet the recently discovered lower-bound of $Ω\left(\frac{K\log(T)}ε \right)$ [Shar…

New algorithm improves best arm identification in Bayesian settings.

Batch Thompson Sampling reduces exploration-exploitation trade-off in online decision making.

New algorithms tackle adversarial combinatorial bandits with switching costs.

We consider a multi-armed bandit problem in a setting where each arm produces a noisy reward realization which depends on an observable random covariate. As opposed to the traditional static multi-armed bandit problem, this setting allows for dynamically changing rewards that better describe applications where side inf…

Determining the appropriate batch size for mini-batch gradient descent is always time consuming as it often relies on grid search. This paper considers a resizable mini-batch gradient descent (RMGD) algorithm based on a multi-armed bandit for achieving best performance in grid search by selecting an appropriate batch s…

DETC algorithm achieves asymptotic optimality in multi-armed bandit problems.

New algorithms identify Pareto optimal sets in multi-objective bandit problems.

In this paper, we study the stochastic version of the one-sided full information bandit problem, where we have $K$ arms $[K] = \{1, 2, \ldots, K\}$, and playing arm $i$ would gain reward from an unknown distribution for arm $i$ while obtaining reward feedback for all arms $j \ge i$. One-sided full information bandit ca…

Can one parallelize complex exploration exploitation tradeoffs? As an example, consider the problem of optimal high-throughput experimental design, where we wish to sequentially design batches of experiments in order to simultaneously learn a surrogate function mapping stimulus to response and identify the maximum of t…

Batch Normalization (BN) uses mini-batch statistics to normalize the activations during training, introducing dependence between mini-batch elements. This dependency can hurt the performance if the mini-batch size is too small, or if the elements are correlated. Several alternatives, such as Batch Renormalization and G…

Algorithm identifies best arm in bandit game with variance consideration.

A new algorithm optimizes local objectives in federated learning with heterogeneous clients.

New algorithms for batched dueling bandits with improved regret bounds.

New algorithm finds high-reward combinatorial sets with fewest pulls.

E$^4$ algorithm optimizes batched linear bandits with minimal regret and batches.

A novel algorithm reduces communication costs in federated best arm identification.

We introduce the functional bandit problem, where the objective is to find an arm that optimises a known functional of the unknown arm-reward distributions. These problems arise in many settings such as maximum entropy methods in natural language processing, and risk-averse decision-making, but current best-arm identif…

New algorithm reduces worst-case sample complexity for learning best arm.

In the Best-$k$-Arm problem, we are given $n$ stochastic bandit arms, each associated with an unknown reward distribution. We are required to identify the $k$ arms with the largest means by taking as few samples as possible. In this paper, we make progress towards a complete characterization of the instance-wise sample…

Develops methods for reliable inference on batched bandit data.

New constraints on space and adaptivity in bandits force more batches and memory use.

We study stochastic multi-armed bandits with many players. The players do not know the number of players, cannot communicate with each other and if multiple players select a common arm they collide and none of them receive any reward. We consider the static scenario, where the number of players remains fixed, and the d…

Sequential screening and dynamic regret in multi-armed bandits with arriving arms

A scheme robust to action erasures improves MAB performance.

Algorithm identifies the best arm in linear bandits with high probability.

We study a multiplayer stochastic multi-armed bandit problem in which players cannot communicate, and if two or more players pull the same arm, a collision occurs and the involved players receive zero reward. We consider the challenging heterogeneous setting, in which different arms may have different means for differe…

This work deals with parallel optimization of expensive objective functions which are modeled as sample realizations of Gaussian processes. The study is formalized as a Bayesian optimization problem, or continuous multi-armed bandit problem, where a batch of q > 0 arms is pulled in parallel at each iteration. Several a…