Study on a bad arm existence checking problem to minimize arm draws.
problem Judging the existence of a positive arm among K given arms.
method Proposes an algorithm with arm selection policy and stopping condition.
result Proves the effectiveness of the proposed algorithm theoretically and empirically.
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.
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 v a v_a v a and can choose an amount x a x_a x a to pass on to the principal (keeping v a − x a v_a-x_a v a − x a for itself). All non-pulle…
We consider the problem of \textit{best arm identification} with a \textit{fixed budget T T T }, in the K K K -armed stochastic bandit setting, with arms distribution defined on [ 0 , 1 ] [0,1] [ 0 , 1 ] . We prove that any bandit strategy, for at least one bandit problem characterized by a complexity H H H , will misidentify the best arm with pr…
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 O ( T ln T ) O(\sqrt{T\ln T}) O ( T ln T ) in single pull case. 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 identifies best arm with optimal budget usage.
problem Identifying the arm with the highest mean reward from multiple options.
method Proposes Almost Tracking, a closed-form algorithm for anytime best arm identification.
result Proven to be rate-optimal and outperforms existing algorithms.
New algorithm for efficiently identifying the best arm in stochastic bandits.
problem Best arm identification in stochastic multi-armed bandits with fixed confidence.
method Sequential probability ratio tests for arm selection.
result Asymptotically optimal sample complexity and guaranteed δ − δ- δ − PAC performance. Improved adaptive algorithms for identifying the best arm in MABs with fixed budget.
problem Identifying the best arm in stochastic Multi-Armed Bandits with a fixed sampling budget.
method Established a connection between Large Deviation Principles and adaptive algorithms, improving error probability bounds and devising new algorithms.
result The \sred algorithm outperforms existing algorithms in identifying the best arm.
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.
New MAB model for online caching costs.
problem Learning costs of cached items online.
method Synchronization bandits, MirrorSync algorithm.
result Adversarial regret of O ( T 2 / 3 ) O(T^{2/3}) O ( T 2/3 ) for MirrorSync. New algorithm ensures replicable results in multi-armed bandits with minimal extra regret.
problem Ensuring consistent results in multi-armed bandit studies.
method Incorporates randomness into decision-making to ensure replicability while maintaining minimal extra regret.
result For large time horizons, proposed algorithm suffers only K 2 / ρ 2 K^2/ρ^2 K 2 / ρ 2 times smaller amount of exploration than existing algorithms. Box Thirding identifies the best arm efficiently under limited samples.
problem Efficiently identifying the best arm with limited sampling.
method Iterative ternary comparison of arms, discarding the weakest and exploring the best.
result Achieves comparable performance to Successive Halving with less predefined parameters.
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.
Survey on risk-aware multi-armed bandits for better decision-making.
problem Risk measures in multi-armed bandits for better decision-making.
method Review of existing research, definition of risk-aware bandit problems, and algorithms for minimizing regret and identifying best arms.
result Consolidation and summarization of existing research on risk measures in multi-armed bandits.
New algorithms improve combinatorial linear semi-bandits for clustered feature vectors.
problem Poor performance of existing algorithms in clustered feature vector cases.
method Arm-wise randomization technique to address the shortcoming.
result Proposed algorithms (PC 2 {}^2 2 UCB and TS) outperform existing algorithms in clustered feature vector cases. A new algorithm reduces suboptimal arm selection in correlated bandits.
problem Structured bandits with correlated rewards.
method Confidence-based phased algorithm.
result Regret is uniformly bounded in certain structures.
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 multi-fidelity best-arm identification reduces cost with better accuracy.
problem Finding the best arm with highest mean reward at minimum cost.
method Gradient-based approach with asymptotically optimal cost complexity.
result Asymptotically optimal cost complexity compared to existing methods.
The paper develops a theory for identifying the best arm in non-parametric multi-armed bandits with a fixed budget.
problem Identifying the best arm in non-parametric multi-armed bandits with a limited number of trials.
method The paper proposes upper and lower bounds on the average log-probability of misidentification using information-theoretic quantities and a refined analysis of the successive-rejects strategy.
result The paper provides new upper and lower bounds on the average log-probability of misidentification, which generalize existing bounds.
Improves A/B testing power using a two-armed bandit framework.
problem Comparing outcomes under a new policy to a control.
method Doubly robust estimation, two-armed bandit framework, permutation-based method.
result Superior performance in A/B testing compared to existing methods.
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.
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.
Develops a framework for clustering and distribution matching with bandit feedback.
problem Clustering and distribution matching problems with limited feedback.
method General framework using K K K -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.
Proposes an interpretable machine learning framework for multi-arm HTE estimation.
problem Challenges in estimating heterogeneous treatment effects in multi-arm settings.
method Rule-based ensemble approach for HTE estimation in multi-arm trials.
result Achieved lower bias and higher estimation accuracy compared to existing methods.
The paper provides tight bounds for improving multi-armed bandits problem.
problem Improving multi-armed bandits problem with concave reward functions.
method Upper and lower bounds for randomized online algorithms, providing an O ( k log k ) O(\sqrt{k} \log k) O ( k log k ) approximation. result Achieved nearly-tight approximation guarantees for the improving multi-armed bandits problem.
Unified meta algorithms estimate various distribution functionals in infinite-armed bandits.
problem Estimating various distribution functionals in infinite-armed bandits.
method Unified meta algorithms for offline and online settings, achieving optimal sample complexities.
result Online estimation offers significant advantage for certain distribution functionals.
New definitions and algorithms improve sample complexity for identifying good arms in multi-armed bandits.
problem Identifying arms with means close to the maximum or larger than a threshold.
method Formalized definitions, lower bounds, and practical algorithms.
result Achieved nearly matching upper bounds with sample complexities of Θ( rac{n}{m}) and Θ( rac{n}{m}k).
Optimal best arm identification for multi-objective bandits with fixed error probability.
problem Identifying the best arm for each of multiple objectives with fixed confidence.
method Surrogate proportions to sample arms at each time step, eliminating max-min optimisation.
result Asymptotically optimal algorithm for multi-objective best arm identification.
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.
We analyze the K K K -armed bandit problem where the reward for each arm is a noisy realization based on an observed context under mild nonparametric assumptions. We attain tight results for top-arm identification and a sublinear regret of O ~ ( T 1 + D 2 + D ) \widetilde{O}\Big(T^{\frac{1+D}{2+D}}\Big) O ( T 2 + D 1 + D ) , where D D D is the context dimension, f…
Optimal policy for multi-armed multi-action bandits with unknown parameters.
problem Optimal sequential action selection for multi-armed multi-action bandits with unknown parameters.
method Occupancy-Measured-Reward Index Policy (OMRIP) and R(MA)^2B-UCB algorithm.
result Asymptotically optimal policy with sub-linear regret and low computational complexity.
New insights on bias in multi-armed bandits under conditional sampling.
problem Understanding bias in multi-armed bandits under conditional sampling.
method Characterized the sign of conditional bias of monotone functions of rewards.
result Sign of conditional bias can differ from marginal bias, depending on conditioning events.
New algorithm identifies best arm efficiently in stochastic bandits.
problem Efficiently identifying the best arm in stochastic bandits with optimal performance.
method Develops a computationally efficient algorithm for optimal best arm identification.
result Achieves optimal performance with minimal computational complexity.
Proposes DEXP3.M for unknown delay in multi-arm bandit with multiple play.
problem Unknown delays in adversarial multi-armed bandit with multiple play.
method DEXP3.M algorithm addressing the challenge of associating feedback losses to arms.
result Regret bound is only slightly worse than single play setting.
Adaptive MAB algorithms handle composite, anonymous feedback without reward interval knowledge.
problem Multi-armed bandit with composite and anonymous feedback, especially without reward interval size knowledge.
method Proposed adaptive algorithms for stochastic and adversarial cases, without reward interval knowledge.
result First algorithm for adversarial case handling non-oblivious adversary and unknown reward interval size.
GNA optimally identifies the best arm with small gaps.
problem Best arm identification in fixed-budget settings.
method Generalized Neyman Allocation (GNA) for asymptotically locally minimax optimal BAI.
result GNA's worst-case bounds match the lower and upper bounds in the small-gap regime.
New algorithm achieves near optimal sample complexity for 1-identification problem.
problem Determining if an arm's mean reward is at least a known threshold with high probability.
method Design of Sequential-Exploration-Exploitation (SEE) algorithm with non-asymptotic analysis.
result Achieves near optimality in sample complexity, matching upper and lower bounds up to a polynomial logarithmic factor.
We propose the first fully-adaptive algorithm for pure exploration in linear bandits---the task to find the arm with the largest expected reward, which depends on an unknown parameter linearly. While existing methods partially or entirely fix sequences of arm selections before observing rewards, our method adaptively c…
Paper introduces risk-sensitive bandits with optimal arm mixtures.
problem Designing algorithms for risk-sensitive multi-armed bandits.
method Formalizes risk-sensitive bandits framework, identifies optimal arm mixtures, designs regret-efficient algorithms.
result Regret-efficient algorithms track optimal arm mixtures or solitary arms.
New algorithm for nonstationary multi-armed bandits with optimal performance.
problem Nonstationary multi-armed bandits with changing model parameters over time.
method Adaptive Resetting Bandit (ADR-bandit) algorithm using adaptive windowing techniques.
result ADR-bandit achieves nearly optimal performance in both abrupt and gradual changes.
Study optimal arms in combinatorial bandits with semi-bandit feedback and finite budget.
problem Finding optimal arms in combinatorial bandits with semi-bandit feedback and finite budget constraints.
method Proposes a generic algorithm covering various arm elimination strategies and derives lower bounds.
result Demonstrates sufficient and necessary budget requirements for finding the best arm.
New method balances performance and cost in identifying best arm.
problem Identifying the best arm in multi-armed bandit models.
method Minimizes a risk functional that balances performance and cost.
result Proposes DBCARE algorithm that matches theoretical lower bounds.
Optimal top-2 method improves best arm identification with reduced error.
problem Identifying the arm with the highest mean in a set of arms.
method A novel top-2 algorithm that pulls the empirical best arm with probability β and the challenger arm otherwise.
result The proposed algorithm matches the information theoretic lower bound on sample complexity as δ approaches 0.
A new method optimizes in nonstationary environments with many arms efficiently.
problem Optimizing in nonstationary environments with a large number of arms.
method Gaussian interpolation to learn continuous Lipschitz reward functions in nonstationary environments.
result Efficiently learns continuous Lipschitz reward functions with O ∗ ( T ) \mathcal{O}^*(\sqrt{T}) O ∗ ( T ) cumulative regret. Efficiently clusters data sequences with varying distributions.
problem Sequentially grouping data sequences with fixed error probability.
method Proposes Efficient Bandit Clustering (EBC) algorithm for asymptotic optimality and computational efficiency.
result EBC and EBC-H achieve better performance and computational efficiency compared to existing methods.
The paper tackles best arm identification in contaminated bandits with optimal error guarantees and sample complexity.
problem Best arm identification in stochastic bandits with adversarial reward contamination.
method Proposes two algorithms: a gap-based algorithm and a successive elimination-based algorithm for sub-Gaussian bandits.
result Asymptotically optimal sample complexity for both algorithms.
This work introduces CAET, an algorithm for cost-aware pairwise pure exploration.
problem Identifying optimal arm pairs with varying costs in multi-armed bandits.
method Introduces a framework for pairwise pure exploration with arm-specific costs, derives a lower bound, and proposes CAET algorithm.
result CAET optimizes cumulative cost and approaches the lower bound asymptotically.