New method for identifying nearly-optimal arms in bandit models with fixed confidence.
problem Near-optimal arm identification in infinitely armed bandit models with limited prior knowledge.
method PAC-like framework, sample complexity lower bound, algorithm with upper bound on sample complexity.
result Proposed algorithm identifies nearly-optimal arm with high probability and within log factor of lower bound.
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.
Infinite arms bandit problem solved with confidence bounds.
problem Optimizing allocation in an infinite arms bandit problem with bounded rewards.
method Constructs confidence bounds for each arm and compares them against a target value to determine sampling.
result Achieves optimality for rewards with bounded means.
The paper tackles infinite-armed bandits with general reservoirs, providing necessary and sufficient conditions for ε-good arm selection.
problem Characterizing conditions for selecting ε-good arms with high probability in infinite-armed bandits.
method The approach is based on successive halving with early discarding of arms after a single pull, analyzing the reservoir distribution without assuming its form.
result The algorithm provably returns an ε-good arm with high probability, explaining the effectiveness of Hyperband's aggressive bracketing.
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 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.
We consider a stochastic bandit problem with infinitely many arms. In this setting, the learner has no chance of trying all the arms even once and has to dedicate its limited number of samples only to a certain number of arms. All previous algorithms for this setting were designed for minimizing the cumulative regret o…
The paper tackles linear bandits with projections, achieving optimal regret.
problem Learning the best arm in a linear bandit model with unobservable projection rewards.
method Developed strategies for both finite and infinite arms, achieving optimal regret bounds.
result Achieved optimal regret bounds for both finite and infinite arms.
Optimal algorithm for selecting high-quality arms from infinite bandit arms.
problem Efficiently choosing the best arm from an infinite set of options.
method Developed algorithms for both fixed confidence and fixed budget settings, achieving optimal or near-optimal sample complexities.
result Optimal sample complexity results for both fixed confidence and fixed budget settings, resolving open questions in the field.
New method tracks shifts in infinite-armed bandits without prior knowledge.
problem Tracking shifts in non-stationary infinite-armed bandits.
method Blackbox conversion of finite-armed MAB to infinite-armed non-stationary, randomized elimination.
result First parameter-free optimal regret bounds for all reservoir regularity regimes.
RandUCB combines UCB and TS for optimal bandit performance.
problem Optimizing decision-making in uncertain environments with limited feedback.
method Randomized UCB algorithm using confidence intervals.
result Achieves minimax-optimal regret in various bandit settings.
Study tackles infinitely many-armed bandits with rotting rewards, achieving tight regret bounds.
problem Infinitely many-armed bandits with rotting rewards.
method Adaptive sliding window UCB algorithm for slow and abrupt rotting scenarios.
result Achieves tight regret bounds for both slow and abrupt rotting scenarios.
The paper provides robustness guarantees for mode estimation in bandits.
problem Understanding robustness in mode estimation under adversarial data contamination.
method Simple randomization and theoretical analysis of multi-armed bandits.
result Regret guarantees for various modal bandit problems.
Study on indexability of restless multi-armed bandits and rollout policy performance.
problem Maximizing discounted rewards in finite state restless multi-armed bandit problems.
method Decouple the problem into single-armed restless bandits, analyze using value iteration, and compare with Whittle index policy.
result Demonstrates conditions for indexability and compares performance of index policy and rollout policy.
Analyze nonparametric contextual bandits with improved UCB algorithm.
problem Optimizing decisions based on noisy context signals.
method Modified UCB algorithm with k k k NN-UCB, global intrinsic dimension dependent and ambient dimension independent regret bounds. result 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 ) for top-arm identification. The paper optimizes identifying top k k k arms from a fraction of ρ ρ ρ arms in stochastic bandits.
problem Identifying k k k distinct arms among the top ρ ρ ρ fraction of arms in stochastic bandits with a PAC tolerance. method The paper considers two cases: known and unknown threshold of top arms' expected rewards. It proves lower bounds and proposes algorithms for each case, showing sample complexity optimality for two algorithms.
result Two algorithms are sample complexity optimal (up to constant factors) and the other two are optimal up to a log factor.
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.
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.
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. The paper tackles identifying multiple best arms in stochastic bandits, improving sample efficiency.
problem Identifying multiple best arms in stochastic multi-armed bandits.
method Developed a fully sequential PAC algorithm, GLUCB, and presented lower and upper bounds.
result Improved sample efficiency for identifying multiple best arms.
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.
Paper tackles contaminated bandits, identifying best true distribution with high probability.
problem Identifying the best true distribution in contaminated bandits.
method Developed tight sample complexity bounds for estimating robust moments from contaminated samples, adapting classical algorithms.
result Derived matching information-theoretic lower bounds for sample complexity.
Paper tackles infinite action linear bandits with tight regret bounds.
problem Linear contextual bandit with infinite action sets.
method Proves a regret upper bound of O ( d 2 T log T ) i m e s e x t p o l y ( log log T ) O(\sqrt{d^2T\log T}) imes ext{poly}(\log\log T) O ( d 2 T log T ) im ese x t p o l y ( log log T ) . result Upper bound matches previous lower bound of Ω ( d 2 T log T ) Ω(\sqrt{d^2 T\log T}) Ω ( d 2 T log T ) up to iterated logarithmic terms. 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.
New algorithms for risk-averse bandits minimize regret in finite time.
problem Minimizing regret in finite time for bandit problems.
method Proposes two algorithms for selecting the most probable arm with a good risk-return trade-off.
result Upper bound for the minimum number of experiments before commitment to guarantee a bound on regret.
New framework improves restless bandit policies for large numbers of arms.
problem Efficiently compute policies for large numbers of arms in restless bandit problems.
method Follow-the-Virtual-Advice framework, converting single-armed policies to N-armed policies.
result Achieves an O(1/\sqrt{N}) optimality gap in both discrete and continuous settings.
Investigates sequential problems on graph structures and large action spaces.
problem Sequential decision-making on graph structures and large action spaces.
method Spectral bandits, side observations, influence maximization, kernel bandits, polymatroid bandits, function optimization, infinitely many-arms bandits.
result Contributions to graph and structured bandits.
Algorithm identifies best arm in linked bandits with reduced feedback.
problem Best arm identification in linked bandits with reduced feedback.
method Combines uniform sampling with regular bandit algorithm.
result Almost matching upper and lower bounds on sample complexity.
The paper proposes a novel upper confidence bound (UCB) procedure for identifying the arm with the largest mean in a multi-armed bandit game in the fixed confidence setting using a small number of total samples. The procedure cannot be improved in the sense that the number of samples required to identify the best arm i…
Study sparsity benefits in infinite feature contextual bandits.
problem Minimizing regret in infinite feature contextual bandits.
method Novel reduction to multi-armed bandits, Feel-Good Thompson Sampling algorithm.
result Regret bounds match lower bounds up to logarithmic factors, logarithmic dependence on effective features.
A new algorithm solves a regional multi-armed bandit problem with group information.
problem Optimizing decisions with unknown parameters across groups.
method UCB-g algorithm combining UCB and greedy principles.
result Proves the order-optimality of UCB-g and establishes a matching lower bound.
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.
CTS reduces regret in probabilistically triggered combinatorial bandits.
problem Optimizing decisions with probabilistically triggered arms in combinatorial multi-armed bandits.
method Combinatorial Thompson Sampling (CTS) with a regret bound analysis.
result Derives an O ( ∑ i = 1 m log T / ( p i Δ i ) ) O(\sum_{i =1}^m \log T / (p_i Δ_i)) O ( ∑ i = 1 m log T / ( p i Δ i )) regret bound for CTS. 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 dynamic allocation methods for multi-armed bandit models.
problem Dynamic allocation problems in multi-armed bandit models.
method New types of dynamic allocation problems and proofs for Gittins index decomposition.
result New proofs for Gittins index decomposition and related results.
A new bandit framework reduces K-armed to C+1-armed, achieving lower regret.
problem Designing efficient algorithms for correlated multi-armed bandits.
method Generalized UCB algorithm exploiting latent random source correlation.
result Achieves O ( 1 ) \mathcal{O}(1) O ( 1 ) regret for certain regimes, reducing from logarithmic. Unified approach to correlated multi-armed bandits reduces regret significantly.
problem Correlated rewards in multi-armed bandits.
method Developed a unified approach to leverage reward correlations and presented algorithms with rigorous analysis.
result C-UCB algorithm pulls non-competitive arms only O(1) times, improving over classic algorithms.
BaSE policy optimizes multi-armed bandits with batched data.
problem Optimizing multi-armed bandits with batched data.
method BaSE (batched successive elimination) policy for batched multi-armed bandits.
result Achieves rate-optimal regrets with adaptive batch sizes.
Graph-Triggered Bandits unify rested and restless bandits with graph-defined arm interactions.
problem Modeling sequential decision-making problems with evolving arm rewards.
method Graph-Triggered Bandits (GTBs) framework that generalizes rested and restless bandits using a graph.
result Rested and restless bandits are special cases of GTBs for suitable graphs.
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.
PAC-Bayesian analysis improves lifelong learning in multi-armed bandits.
problem Improving lifelong learning in multi-armed bandits.
method PAC-Bayesian analysis for deriving lower bounds and proposing lifelong learning algorithms.
result Proposed algorithms outperform baseline methods in lifelong multi-armed bandit problems.
Paper confirms Feldman's conjecture on two-armed bandit problem.
problem Two-armed bandit problem with general distributions and utility functions.
method Obtained necessary and sufficient condition for myopic strategy optimality.
result Myopic strategy stochastically maximizes wins in Bernoulli bandit problems.
New algorithm eliminates arms to minimize regret in complex bandit problems.
problem Minimizing regret in combinatorial bandit problems with explicit exploration.
method Introduces a novel arm elimination scheme that partitions arms into three categories and incorporates explicit exploration.
result Achieves near-optimal regret in combinatorial multi-armed and linear contextual bandit problems.
Quantum algorithms for multi-armed bandits are explored with limited reward access.
problem Exploring quantum speed-ups in multi-armed bandit problems with limited reward information.
method Introduced new bandit models and showed query complexity equivalence with classical algorithms.
result No quadratic speed-up is possible for multi-armed bandits with limited reward access.
Motivated by models of human decision making proposed to explain commonly observed deviations from conventional expected value preferences, we formulate two stochastic multi-armed bandit problems with distorted probabilities on the reward distributions: the classic K K K -armed bandit and the linearly parameterized bandit…
Study uses randomized allocation for delayed rewards in multi-armed bandits.
problem Delayed rewards in contextual multi-armed bandits.
method Randomized allocation with nonparametric estimation.
result Strongly consistent strategy for delayed rewards.
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.
Unified formulation bridges adversarial and nonstationary bandits.
problem Handling time-varying reward distributions in multi-armed bandit problems.
method Unified oracle that switches between adversarial and nonstationary bandit oracles based on window size.
result Optimal regret achieved with matching lower bound.