Optimal algorithm for identifying best arm in stochastic linear bandits with fixed confidence.
problem Identifying the best arm in stochastic linear bandits with fixed confidence.
method Extending an algorithm designed for Best Arm Identification to the ε ε ε -Thresholding Bandit Problem (TBP). result Asymptotically optimal algorithm for TBP.
LSA minimizes aggregate regret in thresholding bandit with optimal performance.
problem Finding arms with mean rewards above a threshold within a fixed budget.
method LSA, a simple and anytime algorithm aiming to minimize aggregate regret.
result LSA is instance-wise asymptotically optimal in minimizing aggregate regret.
GrAPL identifies arms above a threshold using graph similarity.
problem Efficiently identifying arms with means above a threshold in a graph-structured bandit problem.
method Thresholding Graph Bandits with GrAPL algorithm exploiting graph structure and reward homophily.
result GrAPL effectively identifies arms above a threshold using graph structure and reward homophily.
Study on resource allocation with unknown thresholds in semi-bandit problems.
problem Learning optimal allocation of resources to arms with unknown threshold values.
method Established equivalence to MP-MAB and Combinatorial Semi-Bandits, derived optimal algorithms.
result Developed algorithms validated by experiments on synthetic data.
LinearAPT optimizes decision-making under resource constraints for a linear threshold problem.
problem Optimizing sequential decisions with a linear threshold under resource limitations.
method LinearAPT, an adaptive algorithm for fixed-budget TLB problem.
result LinearAPT achieves theoretical upper bounds and robust performance on various datasets.
Optimal resource allocation in censored semi-bandits with unknown thresholds.
problem Sequential resource allocation with unknown thresholds and hidden parameters.
method Established equivalence to MP-MAB and Combinatorial Semi-Bandits, derived optimal algorithms.
result Validated performance of proposed algorithms on synthetic data.
Thresholded Lasso bandit minimizes regret in sparse linear bandits.
problem Sparse stochastic contextual linear bandits with large feature vectors.
method Uses Lasso framework with thresholding to estimate reward function and its sparse support.
result Non-asymptotic regret upper bounds scaling as O ( log d + T ) \mathcal{O}( \log d + \sqrt{T}) O ( log d + T ) . Solves a new bandit problem with duels and pulls for crowdsourcing.
problem Finding the best arms with mean rewards above a threshold.
method Alternates between ranking and binary search to solve TBP-DC.
result Proves optimality of the Rank-Search algorithm.
Investigates probability of error in structured thresholding bandit problems.
problem Probability of misclassifying arms in structured thresholding bandit problems.
method Analyzes two shape constraints: monotonic increasing and concave sequences of arm means.
result Upper and lower bounds for the probability of error match up to constants in the problem dependent regime.
A privacy-preserving algorithm for high-dimensional bandits.
problem High-dimensional stochastic contextual linear bandits with sparse parameters under privacy constraints.
method PrivateLASSO algorithm based on sparse hard-thresholding and episodic thresholding.
result Minimax private lower bounds and utility guarantees for PrivateLASSO.
Study lenient regret and good-action identification in Gaussian process bandits.
problem Optimizing function values above a certain threshold in Gaussian process bandits.
method Study lenient regret notions and introduce algorithms for finding good actions.
result Upper and lower bounds on lenient regret for GP-UCB and elimination algorithms.
Optimal algorithm for high-dimensional stochastic linear bandits with sparse parameters.
problem High-dimensional stochastic linear bandits with sparse parameters.
method Three-stage arm selection algorithm using thresholded Lasso for estimation.
result Achieves exact minimax optimality in cumulative regret.
Adaptive algorithm for outlier detection by balancing arm exploration and threshold estimation.
problem Identifying outliers in a set of rewards where the threshold is a function of all rewards.
method Adaptively updated confidence interval for the threshold based on previous rounds' estimates, balancing exploration of individual arms and the outlier threshold.
result Efficient algorithm with reduced sample complexity for outlier detection.
The paper studies how arm selection in a bandit problem changes with shape constraints.
problem Stochastic Thresholding Bandit Problem under shape constraints.
method Investigation of TBP under four shape constraints: monotonic increasing, unimodal, concave, and fixed.
result Minimax rates for regret vary significantly depending on the shape constraint.
Paper tackles good arm identification in stochastic bandits.
problem Identifying good arms with minimal samples.
method Proposes DGAI, a differentiable algorithm to improve sample complexity.
result DGAI outperforms baseline algorithms in synthetic and real-world datasets.
New algorithm tackles unknown utility network resource allocation.
problem Maximizing network utility with unknown agent utilities.
method Modeling as a bandit problem, proposing algorithms for resource allocation.
result Proposed algorithms are optimal when all agents have the same utility.
New algorithm identifies good arms with fewer samples when thresholds are close.
problem Good arm identification in bandit problems with small threshold gaps.
method Proposes lil'HDoC algorithm to improve GAI under small threshold gaps.
result Sample complexity of first λ output arm is nearly identical to HDoC algorithm when thresholds are close.
Safe linear stochastic bandits ensure safe exploration with optimal regret.
problem Ensuring safe exploration in stochastic bandits while minimizing regret.
method Combining known safe arms with exploratory arms to safely expand the set of safe arms over time.
result The algorithm achieves an expected regret of O ( T log ( T ) ) O(\sqrt{T}\log (T)) O ( T log ( T )) . Study personalizes user experience to maximize rewards with patience budget.
problem Maximizing rewards for a platform while respecting user patience.
method Proposes bandit algorithms for sequential choice with feedback models.
result Upper and lower bounds on regret of order O ( N 2 / 3 ) O(N^{2/3}) O ( N 2/3 ) and Ω ( N 2 / 3 ) Ω(N^{2/3}) Ω ( N 2/3 ) . An algorithm for maximizing rewards under linear cost constraints.
problem Maximizing rewards while adhering to cost constraints in a linear bandit problem.
method Proposes an upper-confidence bound algorithm called optimistic pessimistic linear bandit (OPLB) for constrained contextual linear bandits.
result Proves an O ~ ( d T τ − c 0 ) \widetilde{\mathcal{O}}(\frac{d\sqrt{T}}{τ-c_0}) O ( τ − c 0 d T ) bound on regret for the proposed algorithm. An optimal algorithm for multi-armed bandits with constraints.
problem Optimizing decisions in constrained multi-armed bandit problems.
method An index-based deterministic algorithm using Locatelli's anytime thresholding under known optimal value assumption.
result The algorithm achieves asymptotic optimality with probability approaching 1.
New algorithm for active exploration in bandit problems.
problem Active exploration in bandit problems.
method Gradient ascent with online lazy mirror ascent sampling rule.
result Asymptotically optimal and computationally efficient.
New method reduces GP bandit complexity while maintaining good performance.
problem Computational burden in Bayesian optimization with Gaussian processes.
method Information thresholding to compress GP posterior and reduce complexity.
result Sublinear regret bounds with sublinear posterior complexity.
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 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…
The paper studies early stopping methods in linear contextual bandits.
problem Minimizing in-experiment regret and conducting robust post-experiment inferences in contextual bandits.
method The study proposes early stopping rules based on the Opportunity Cost and Threshold Method, using variances of estimators to quantify upper regret bounds.
result The proposed method provides a systematic approach to minimize in-experiment regret and conduct robust post-experiment inferences.
New bandit model for healthcare intervention planning.
problem Maximizing patient health with limited monitoring resources.
method Developed Collapsing Bandits model and derived optimal policies.
result 3-order-of-magnitude speedup in algorithm performance.
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.
problem Estimating points where an unknown function exceeds a given threshold.
method Relates to adaptive experimental design methods for linear bandits in RKHS.
result Proves nearly optimal sample complexity bounds for level set estimation.
New algorithm reduces regret in infinitely many-armed bandits with decreasing rewards.
problem Infinitely many-armed bandits with rotting rewards.
method UCB index and adaptive threshold for unknown rotting rate, UCB index alone for known rotting rate.
result Matching upper bounds on regret achieved for different scenarios.
This work optimizes identifying good arms in nonparametric multi-armed bandits.
problem Efficiently identifying arms with high means in nonparametric settings.
method Combining reward-maximizing sampling with a nonparametric sequential test for anytime-valid labeling.
result Achieves minimax optimal stopping times for identifying arms above a threshold.
The study analyzes batched methods for early stopping in stochastic multi-armed bandits.
problem Early stopping in stochastic multi-armed bandits with fixed confidence.
method Instance-dependent lower bounds and a general batched algorithm with upper bounds.
result Upper and lower bounds on the number of batches and sample complexity.
New algorithm finds best feasible arm in grouped bandits.
problem Finding the best arm with all attributes above a threshold.
method Feasibility Constrained Successive Rejects (FCSR) algorithm.
result FCSR identifies the best feasible arm with optimal dependence on problem parameters.
Rarely switch policies to optimize treatment effects, reducing harmful changes.
problem Difficult to change policies frequently in real-world scenarios.
method Developed a conservative policy updating procedure for rarely-switching linear bandits.
result The procedure optimizes policies with fewer changes and fewer detrimental changes.
New algorithm SELECT minimizes satisficing regret in bandits.
problem Minimizing regret in bandit optimization with satisficing arms.
method SELECT algorithm for satisficing regret minimization.
result SELECT achieves constant expected satisficing regret.
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 p_{c} 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…
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…
Agents collaborate to minimize regret while keeping costs under a threshold.
problem Collaborative multi-agent stochastic linear bandits with cost constraints.
method Safe distributed upper confidence bound algorithm (MA-OPLB) with accelerated consensus.
result Regret bound of order $ \mathcal{O}\left(\frac{d}{τ-c_0}\frac{\log(NT)^2}{\sqrt{N}}\sqrt{\frac{T}{\log(1/|λ_2|)}}
ight)$ .
Paper tackles adaptive sampling for identifying largest gaps between distributions.
problem Adaptive sampling from K distributions to identify the largest gap between any two adjacent means.
method Proposes elimination and UCB-style algorithms, showing minimax optimality.
result UCB-style algorithms require 6-8x fewer samples than non-adaptive sampling.
Paper addresses regret minimization and inference in high-dimensional online decision-making.
problem Regret minimization and statistical inference in high-dimensional online decision-making.
method Integrates ε-greedy bandit algorithm with hard thresholding for sparse bandit parameters and debiasing method for inference.
result Achieves either O ( T 1 / 2 ) O(T^{1/2}) O ( T 1/2 ) regret or O ( T 1 / 2 ) O(T^{1/2}) O ( T 1/2 ) -consistent inference, with trade-off between exploration and exploitation. DE is a new exploration method that limits resource usage based on expected improvement and surprise.
problem Limited exploration in large action spaces when resources are scarce.
method Delight-gated exploration (DE) that limits exploration actions based on a gate price set by the product of expected improvement and surprise.
result DE outperforms ε \varepsilon ε -greedy and Thompson Sampling in terms of regret across various bandit and MDP settings. New algorithm optimizes beam and rate allocation in mmWave systems for multiple users.
problem Optimizing beam and rate allocation in mmWave systems for multiple users with limited feedback.
method Introducing SAT-CTS, a combinatorial semi-bandit policy with satisficing objective.
result SAT-CTS achieves finite-time regret bounds and reduces satisficing regret in mmWave systems.
FLIPHAT addresses joint differential privacy for high-dimensional sparse linear bandits.
problem Efficient sequential decision-making with high-dimensional sparse features and privacy concerns.
method FLIPHAT combines iterative forgetting and N-IHT for sparse linear regression, achieving optimal regret.
result FLIPHAT achieves optimal regret in terms of privacy parameters, context dimension, and time horizon.
New insights into balancing reward and fairness in stochastic MAB.
problem Balancing reward and fairness in stochastic multi-armed bandits.
method Formulated a penalization framework and proposed a hard-threshold UCB-like algorithm.
result Asymptotic fairness, nearly optimal regret, better reward-fairness tradeoff.
EBUCB framework achieves optimal regret with bounded approximate inference error.
problem Theoretical gap between practical performance and theoretical justification of Bayesian bandit algorithms with approximate inference.
method Enhanced Bayesian Upper Confidence Bound (EBUCB) framework that accommodates bandit problems with approximate inference.
result EBUCB achieves optimal regret order O ( log T ) O(\log T) O ( log T ) under certain conditions on 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…