arXiv research

Optimal algorithm for identifying best arm in stochastic linear bandits with fixed confidence.

LinearAPT optimizes decision-making under resource constraints for a linear threshold problem.

Optimal resource allocation in censored semi-bandits with unknown thresholds.

Thresholded Lasso bandit minimizes regret in sparse linear bandits.

Investigates probability of error in structured thresholding bandit problems.

A privacy-preserving algorithm for high-dimensional bandits.

Study lenient regret and good-action identification in Gaussian process bandits.

In this paper, we introduce a new online decision making paradigm that we call Thresholding Graph Bandits. The main goal is to efficiently identify a subset of arms in a multi-armed bandit problem whose means are above a specified threshold. While traditionally in such problems, the arms are assumed to be independent, …

We consider the thresholding bandit problem, whose goal is to find arms of mean rewards above a given threshold $θ$, with a fixed budget of $T$ trials. We introduce LSA, a new, simple and anytime algorithm that aims to minimize the aggregate regret (or the expected number of mis-classified arms). We prove that our algo…

Optimal algorithm for high-dimensional stochastic linear bandits with sparse parameters.

Adaptive algorithm for outlier detection by balancing arm exploration and threshold estimation.

The paper studies how arm selection in a bandit problem changes with shape constraints.

Paper tackles good arm identification in stochastic bandits.

New algorithm tackles unknown utility network resource allocation.

In this paper, we study censored Semi-Bandits, a novel variant of the semi-bandits problem. The learner is assumed to have a fixed amount of resources, which it allocates to the arms at each time step. The loss observed from an arm is random and depends on the amount of resources allocated to it. More specifically, the…

New algorithm identifies good arms with fewer samples when thresholds are close.

Study personalizes user experience to maximize rewards with patience budget.

An algorithm for maximizing rewards under linear cost constraints.

An optimal algorithm for multi-armed bandits with constraints.

New method reduces GP bandit complexity while maintaining good performance.

We analyze the sample complexity of the thresholding bandit problem, with and without the assumption that the mean values of the arms are increasing. In each case, we provide a lower bound valid for any risk $δ$ and any $δ$-correct algorithm; in addition, we propose an algorithm whose sample complexity is of the same o…

We study a specific \textit{combinatorial pure exploration stochastic bandit problem} where the learner aims at finding the set of arms whose means are above a given threshold, up to a given precision, and \textit{for a fixed time horizon}. We propose a parameter-free algorithm based on an original heuristic, and prove…

This paper considers the multi-armed thresholding bandit problem -- identifying all arms whose expected rewards are above a predefined threshold via as few pulls (or rounds) as possible -- proposed by Locatelli et al. [2016] recently. Although the proposed algorithm in Locatelli et al. [2016] achieves the optimal round…

We present a new algorithm based on an gradient ascent for a general Active Exploration bandit problem in the fixed confidence setting. This problem encompasses several well studied problems such that the Best Arm Identification or Thresholding Bandits. It consists of a new sampling rule based on an online lazy mirror …

The paper studies early stopping methods in linear contextual bandits.

The Thresholding Bandit Problem (TBP) aims to find the set of arms with mean rewards greater than a given threshold. We consider a new setting of TBP, where in addition to pulling arms, one can also \emph{duel} two arms and get the arm with a greater mean. In our motivating application from crowdsourcing, dueling two a…

New bandit model for healthcare intervention planning.

We present a novel distribution-free approach, the data-driven threshold machine (DTM), for a fundamental problem at the core of many learning tasks: choose a threshold for a given pre-specified level that bounds the tail probability of the maximum of a (possibly dependent but stationary) random sequence. We do not ass…

New algorithms estimate function levels with near-optimal efficiency.

New algorithm reduces regret in infinitely many-armed bandits with decreasing rewards.

This work optimizes identifying good arms in nonparametric multi-armed bandits.

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

New algorithm finds best feasible arm in grouped bandits.

New algorithm SELECT minimizes satisficing regret in bandits.

We obtain the conditions for the emergence of the swarm intelligence effect in an interactive game of restless multi-armed bandit (rMAB). A player competes with multiple agents. Each bandit has a payoff that changes with a probability $p_{c}$ per round. The agents and player choose one of three options: (1) Exploit (a …

The trade-off between the cost of acquiring and processing data, and uncertainty due to a lack of data is fundamental in machine learning. A basic instance of this trade-off is the problem of deciding when to make noisy and costly observations of a discrete-time Gaussian random walk, so as to minimise the posterior var…

Excessively changing policies in many real world scenarios is difficult, unethical, or expensive. After all, doctor guidelines, tax codes, and price lists can only be reprinted so often. We may thus want to only change a policy when it is probable that the change is beneficial. In cases that a policy is a threshold on …

In this paper, we propose and study opportunistic bandits - a new variant of bandits where the regret of pulling a suboptimal arm varies under different environmental conditions, such as network load or produce price. When the load/price is low, so is the cost/regret of pulling a suboptimal arm (e.g., trying a suboptim…

We introduce the safe linear stochastic bandit framework---a generalization of linear stochastic bandits---where, in each stage, the learner is required to select an arm with an expected reward that is no less than a predetermined (safe) threshold with high probability. We assume that the learner initially has knowledg…

Agents collaborate to minimize regret while keeping costs under a threshold.

This paper studies the problem of adaptively sampling from K distributions (arms) in order to identify the largest gap between any two adjacent means. We call this the MaxGap-bandit problem. This problem arises naturally in approximate ranking, noisy sorting, outlier detection, and top-arm identification in bandits. Th…

Paper addresses regret minimization and inference in high-dimensional online decision-making.

DE is a new exploration method that limits resource usage based on expected improvement and surprise.

New algorithm optimizes beam and rate allocation in mmWave systems for multiple users.

FLIPHAT addresses joint differential privacy for high-dimensional sparse linear bandits.

New insights into balancing reward and fairness in stochastic MAB.

EBUCB framework achieves optimal regret with bounded approximate inference error.

Satisficing is a relaxation of maximizing and allows for less risky decision making in the face of uncertainty. We propose two sets of satisficing objectives for the multi-armed bandit problem, where the objective is to achieve reward-based decision-making performance above a given threshold. We show that these new pro…