We study a bad arm existing checking problem in which a player's task is to judge whether a positive arm exists or not among given K arms by drawing as small number of arms as possible. Here, an arm is positive if its expected loss suffered by drawing the arm is at least a given threshold. This problem is a formalizati…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,932 papers · 148 categories
Trend · papers per month
48 results for “arms”
New algorithms for streaming bandits with limited memory.
problem Optimizing decisions in a stream of uncertain outcomes with limited memory.
method Developed algorithms for minimizing regret and identifying the best arm under bounded memory constraints.
result Upper and lower bounds on sample complexity for best-arm identification algorithms.
Study best arm identification in restless Markov multi-armed bandits with state-dependent transitions.
problem Identify the best arm in a multi-armed bandit with time-varying states.
method Propose a sequential policy to select arms without knowing their exact TPMs.
result Upper and lower bounds on expected time to find the best arm match in a special case.
Paper tackles identifying an odd arm in a multi-armed bandit with restless Markov processes and trembling hand.
problem Identifying an odd arm in a multi-armed bandit with restless Markov processes and trembling hand.
method Derive asymptotic lower bound on expected time to identify the odd arm, stitch together parameterised solutions to MDPs.
result First known asymptotic lower bound on expected time to identify the odd arm, with vanishing error probability.
Top Two Algorithms Revisitedstat.ML
Improved theoretical guarantees for Top Two algorithms.
problem Theoretical support for best arm identification with bounded distributions.
method General analysis of Top Two methods, identifying desirable properties and replacing sampling step.
result Theoretical support for Top Two algorithms with bounded distributions.
Nonlinear Sequential Accepts and Rejects for Identification of Top Arms in Stochastic Banditsstat.ML
We address the M-best-arm identification problem in multi-armed bandits. A player has a limited budget to explore K arms (M<K), and once pulled, each arm yields a reward drawn (independently) from a fixed, unknown distribution. The goal is to find the top M arms in the sense of expected reward. We develop an algorithm …
Sequential screening and dynamic regret in multi-armed bandits with arriving arms
problem Sequential experimentation with expanding arm set
method UCB-AA with preliminary screening
result Regret bounds depend on arrival process
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.
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…
A novel algorithm reduces communication costs in federated best arm identification.
problem Identifying the best arm in a federated multi-armed bandit setup with minimal communication cost.
method Proposes a novel algorithm called FedElim that communicates only in exponential time steps.
result Demonstrates that communication is almost cost-free in FedElim, with a total cost at most 3 times the maximum under its variant.
New algorithms identify best arm with less pulls, adapting to arm covariances.
problem Best arm identification under dependent and correlated arm distributions.
method Adaptive algorithms estimating arm covariances to minimize pulls.
result Substantial improvement in best arm identification over standard setting.
Study best arm identification in restless bandits with unknown TPMs.
problem Identify the best arm with fixed confidence in restless bandits with unknown TPMs.
method Proposed a policy for best arm identification and proved its expected stopping time matches the lower bound.
result The state-action visitation proportions match the optimal proportions under any asymptotically optimal policy.
New method for identifying best arm in batched multi-armed bandit problems.
problem Identifying the best arm in multi-armed bandit problems where arms are sampled in batches.
method General linear programming framework for best arm identification in batched multi-armed bandit problems.
result Demonstrated good performance in numerical studies compared to UCB-type or Thompson sampling methods.
Optimal best-arm identification with known number of optimal arms.
problem Identifying the best arm in a multi-armed bandit with multiple optimal arms under fixed confidence.
method Deriving a new information-theoretic lower bound and proposing a modified stopping rule.
result Achieving asymptotic instance-optimality with a new lower bound and new stopping rule.
We consider a novel multi-armed bandit framework where the rewards obtained by pulling the arms are functions of a common latent random variable. The correlation between arms due to the common random source can be used to design a generalized upper-confidence-bound (UCB) algorithm that identifies certain arms as $non-c…
Paper tackles outlier detection in multi-armed bandits, achieving high accuracy with reduced exploration costs.
problem Detecting outlier arms in multi-armed bandit settings.
method Proposes GOLD algorithm based on upper confidence bounds to identify generic outlier arms.
result Achieves 98% accuracy with 83% reduction in exploration cost compared to state-of-the-art techniques.
We study a strategic version of the multi-armed bandit problem, where each arm is an individual strategic agent and we, the principal, pull one arm each round. When pulled, the arm receives some private reward and can choose an amount to pass on to the principal (keeping for itself). All non-pulle…
Improved best-arm identification in correlated multi-armed bandits.
problem Best-arm identification in multi-armed bandits with correlated rewards.
method Proposed C-LUCB algorithm that exploits upper bounds on conditional rewards.
result Significant reduction in sample complexity for best-arm identification.
Optimal best-arm identification in linear bandits reduces sampling budget.
problem Identifying the best arm with fixed confidence in stochastic linear bandits.
method A simple algorithm that tracks an optimal proportion of arm draws, updated as rarely as desired.
result The algorithm's sampling complexity matches known lower bounds, asymptotically almost surely and in expectation.
Algorithm reduces regret in restless multi-armed bandits by adaptively sequencing arm choices.
problem Minimizing regret in restless multi-armed bandits with unknown dynamics.
method Adaptive Sequencing Rules (ASR) algorithm that selects arms in a consecutive manner.
result Achieves logarithmic regret order with time and finite-sample bound.
New algorithm for identifying best drug arm in generalized linear bandits.
problem Identifying the best drug arm in drug design with minimal trials.
method Proposes an algorithm for best-arm identification in generalized linear bandits, providing theoretical guarantees and simulations.
result First algorithm for best-arm identification in generalized linear bandits with theoretical guarantees.
New model for multi-armed bandits with growing arms.
problem Balancing exploration and exploitation in a growing set of arms.
method Introduces Ballooning Multi-Armed Bandits (BL-MAB) and analyzes existing algorithms.
result Achieves sub-linear regret under certain conditions.
Study optimizes identifying the best arm with fixed rounds and Gaussian outcomes.
problem Designing efficient experiments to identify the best arm with fixed rounds and Gaussian outcomes.
method Developed worst-case lower bounds and the GNA-EBA strategy for optimal identification.
result GNA-EBA strategy is asymptotically worst-case optimal.
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.
We analyze the regret of combinatorial Thompson sampling (CTS) for the combinatorial multi-armed bandit with probabilistically triggered arms under the semi-bandit feedback setting. We assume that the learner has access to an exact optimization oracle but does not know the expected base arm outcomes beforehand. When th…
Develops a framework for clustering and distribution matching with bandit feedback.
problem Clustering and distribution matching problems with limited feedback.
method General framework using -armed bandit model, Track-and-Stop method, and Frank--Wolfe algorithm.
result Average number of arm pulls matches lower bound, with asymptotic convergence to fundamental limit.
New algorithm reduces super-arm selection complexity exponentially.
problem Combinatorial multi-armed bandits with cardinality constraint.
method Combination of group-testing and quantized Thompson sampling.
result Achieves same regret order as state-of-the-art algorithms with perfect oracle, but with reduced complexity.
New algorithm identifies best target arm with known additive relationship between source and target MAB instances.
problem Identifying the best arm in a target MAB instance when only source arms can be pulled and there's a known additive relationship between the two.
method Proposes an LUCB-style algorithm to identify an ε-optimal target arm with high probability.
result Theoretical analysis highlights aspects of the transfer learning problem and recovers the LUCB algorithm for single domain BAI as a special case.
This paper studies Thompson sampling's arm-pull dynamics and inference, revealing key differences from UCB algorithms.
problem Understanding the precise arm-pull dynamics in Thompson sampling algorithms.
method Developed new approaches to analyze the arm-pull count process and noise processes, including inverse process and reparametrization methods.
result Arm-pull count is asymptotically deterministic only for suboptimal or unique optimal arms, revealing a unifying principle of stability.
Study best arm identification with limited precision sampling in bandits.
problem Limited precision sampling in multi-armed bandit problems.
method Proposed a modified tracking-based algorithm to handle non-unique optimal allocations and presented non-asymptotic bounds.
result Asymptotically optimal tracking-based algorithm for best arm identification.
The paper tackles a bandit problem with infinitely many arms per group, aiming to identify the group with the highest quantile reward.
problem Max-quantile group bandit problem with infinitely many arms per group.
method Two-step algorithm: first request arms from each group, then apply a finite-arm max-quantile bandit algorithm.
result Characterization of instance-dependent and worst-case regret, with matching lower bounds.
New algorithm reduces worst-case sample complexity for learning best arm.
problem Identifying a best arm with confidence in multi-armed bandit settings.
method Proposed a new -PAC learning algorithm for multi-armed bandits.
result Algorithm achieves optimal sample complexity for -learning.
Greedy algorithms outperform UCB in many-armed bandit problems.
problem Optimizing multi-armed bandit problems with many arms.
method Subsampled UCB and greedy algorithms comparison.
result Greedy algorithms achieve optimal regret in many-armed bandit problems.
New strategies for identifying the best arm in bandits with decreasing variances.
problem Best arm identification in bandits with time-varying variances.
method Two policies: initial wait followed by continuous sampling, and periodic sampling with weighted average.
result Analytical guarantees and simulations show improved performance over existing methods.
We consider the Max -Armed Bandit problem, where a learning agent is faced with several sources (arms) of items (rewards), and interested in finding the best item overall. At each time step the agent chooses an arm, and obtains a random real valued reward. The rewards of each arm are assumed to be i.i.d., with an un…
New methods optimize personalized treatment assignment in trials with many arms.
problem Poor performance of standard methods in trials with many treatment arms.
method Regularized and clustered joint assignment forest algorithm.
result Gains in predicting arm-wise outcomes and utility gains from personalization.
Sampling from distributions to find the one with the largest mean arises in a broad range of applications, and it can be mathematically modeled as a multi-armed bandit problem in which each distribution is associated with an arm. This paper studies the sample complexity of identifying the best arm (largest mean) in a m…
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.
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.
New algorithm for identifying optimal arms in stochastic bandit problems.
problem Optimal arm identification in stochastic bandit problems with many arms.
method Characterized optimal learning rates and provided algorithms with matching bounds.
result Lower bounds and matching upper bounds for cumulative regret and best-arm identification.
In the Best- identification problem (Best--Arm), we are given stochastic bandit arms with unknown reward distributions. Our goal is to identify the arms with the largest means with high confidence, by drawing samples from the arms adaptively. This problem is motivated by various practical applications and…
New algorithms find all ε-good arms in stochastic bandits.
problem Finding all arms with means above a specified threshold in stochastic bandits.
method Two algorithms introduced to identify all ε-good arms.
result Demonstrated great empirical performance on large datasets.
Thompson Sampling tackles USS, a sequential selection problem without feedback.
problem Unsupervised Sequential Selection (USS) problem with fixed costs and ordered arms.
method Thompson Sampling algorithm for USS problem.
result Thompson Sampling achieves near optimal regret and better performance than existing algorithms.
Proposes a fair RMAB framework ensuring equal exposure to arms.
problem Fairness in RMABs where arms are not equally exposed.
method Defines merit of each arm based on stationary reward distribution and ensures equal exposure in proportion to merit.
result Achieves sublinear fairness regret of in single pull case.
New MAB model for online caching costs.
problem Learning costs of cached items online.
method Synchronization bandits, MirrorSync algorithm.
result Adversarial regret of for MirrorSync.
New algorithm optimizes best arm identification with minimal regret.
problem Best arm identification in multi-armed bandit problems.
method Characterized Bayesian simple regret with continuity conditions of prior, proposed a simple algorithm.
result Proposed algorithm achieves rate-optimal Bayesian simple regret.
Paper tackles anomaly detection in restless Markov arms with unknown TPMs.
problem Detecting an anomalous arm in a multi-armed bandit with unknown transition probability matrices.
method Developed a policy based on the principle of certainty equivalence, achieving the lower bound arbitrarily closely under specific assumptions.
result Achieved the lower bound on expected time required to find the odd arm index, demonstrating the policy's effectiveness.
Quantile Multi-Armed Bandits: Optimal Best-Arm Identification and a Differentially Private Schemestat.ML
Study quantile multi-armed bandits for identifying the best arm with a specified quantile level.
problem Identifying the arm with the highest quantile in multi-armed bandits with private rewards.
method Proposed a (non-private) and differentially private successive elimination algorithms for best-arm identification.
result The proposed algorithms are essentially optimal for quantile bandit problems, with finite sample complexity even for distributions with infinite support-size.