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.
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.
Study analyzes symmetric two-armed Bernoulli bandit problem with zero mean gap.
problem Analyzing symmetric two-armed Bernoulli bandit problem with zero mean gap.
method Associated with a solution of a linear heat equation, compute leading order terms of minmax optimal regret and pseudoregret.
result Explicitly compute leading order terms in three scaling regimes for the gap.
Improves A/B testing by detecting minor treatment effects.
problem Challenges in identifying small average treatment effects.
method Maximum probability-driven two-armed bandit (TAB) process with weighted mean volatility statistic.
result Significant improvement in A/B testing with reduced experimental costs.
Optimal strategy found for identifying best arm in bandits with small gap.
problem Best arm identification in two-armed bandits with a fixed budget and small gap.
method Neyman allocation rule augmented with inverse probability weighting.
result Proposed strategy is asymptotically optimal when gap is small.
New strategy optimally identifies best arm in unknown variance Gaussian bandits.
problem Identifying the best arm in two-armed Gaussian bandits with unknown variances.
method Proposes a Neyman Allocation (NA)-Augmented Inverse Probability weighting (AIPW) strategy to estimate variances and draw arms adaptively.
result Demonstrates asymptotic optimality of the proposed strategy in the small-gap regime.
Advances FTPL results for bandit problems with unbounded perturbations.
problem Improving analytical foundations of FTPL in bandit problems.
method Revisiting classical FTRL-FTPL duality for unbounded perturbations.
result Establishes Best-of-Both-Worlds (BOBW) results for FTPL under a broad family of asymmetric unbounded perturbations.
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…
Gamblers lose in long bets despite casino claims, study shows.
problem Gamblers losing in seemingly fair gambling scenarios.
method Theoretical and experimental analysis of two-armed Futurity slot machines.
result Casinos have a win rate greater than 50% in long bets, making them unfair.
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. In this paper, we study the multi-armed bandit problem in the batched setting where the employed policy must split data into a small number of batches. While the minimax regret for the two-armed stochastic bandits has been completely characterized in \cite{perchet2016batched}, the effect of the number of arms on the re…
Algorithm identifies Copeland winners in dueling bandits with ternary feedback.
problem Identifying Copeland winners in dueling bandits with indifferences.
method Proposed POCOWISTA algorithm with a sample complexity close to lower bound.
result Algorithm shows excellent performance, even for conventional dueling bandits.
Characterizes UCB algorithm performance in bandit problems.
problem Optimizing UCB algorithm performance in stochastic bandit environments.
method Novel perturbation analysis to characterize CLT of pulls and means.
result Smooth interpolation of pseudo-regret between large and small gap regimes.
New findings on complexity limits in fixed budget bandit identification.
problem Determining the best possible error rate for fixed budget bandit identification.
method Analyzing the best non-adaptive sampling procedures and showing the existence of complexities.
result No fixed complexity for certain bandit identification tasks.
Study links cognitive effort to thermodynamic principles, optimizing decision-making.
problem Understanding the energy cost of decision-making in living systems.
method Applied Landauer's principle to analyze belief dynamics in a two-armed bandit game.
result Cognitive energy cost correlates with optimal decision-making outcomes.
Narendra-Shapiro (NS) algorithms are bandit-type algorithms that have been introduced in the sixties (with a view to applications in Psychology or learning automata), whose convergence has been intensively studied in the stochastic algorithm literature. In this paper, we adress the following question: are the Narendra-…
New bandit algorithm maximizes information gain.
problem Optimizing decision-making in uncertain environments.
method Approximates information maximization using entropy and free energy principles.
result Asymptotic optimality proven for two-armed bandit problem.
No algorithm outperforms uniform sampling in A/B testing.
problem Identifying the best arm in A/B testing with fixed budget.
method Introducing consistent and stable algorithms, deriving lower bounds, and proving optimality of uniform sampling.
result No algorithm performs better than uniform sampling in A/B testing.
Regularization-induced exploration improves contextual bandit performance.
problem Complex reward models in real-world contextual bandits are hard to explore effectively.
method Regularization-induced exploration using stochasticity in cross-validation.
result Regularization-induced exploration leads to reliable exploration in large-scale business environments.
Proposes a new TS algorithm for non-stationary bandits using KS tests.
problem Non-stationary multi-armed bandit problems.
method Active detection of change points using KS tests and adaptive Thompson Sampling.
result Sub-linear regret demonstrated for the two-armed bandit case.
We propose the first contextual bandit algorithm that is parameter-free, efficient, and optimal in terms of dynamic regret. Specifically, our algorithm achieves dynamic regret O ( min { S T , Δ 1 3 T 2 3 } ) \mathcal{O}(\min\{\sqrt{ST}, Δ^{\frac{1}{3}}T^{\frac{2}{3}}\}) O ( min { S T , Δ 3 1 T 3 2 }) for a contextual bandit problem with T T T rounds, S S S switches and Δ Δ Δ total var…
The contextual bandit literature has traditionally focused on algorithms that address the exploration-exploitation tradeoff. In particular, greedy algorithms that exploit current estimates without any exploration may be sub-optimal in general. However, exploration-free greedy algorithms are desirable in practical setti…
Most contextual bandit algorithms minimize regret against the best fixed policy, a questionable benchmark for non-stationary environments that are ubiquitous in applications. In this work, we develop several efficient contextual bandit algorithms for non-stationary environments by equipping existing methods for i.i.d. …
The stochastic multi-armed bandit model is a simple abstraction that has proven useful in many different contexts in statistics and machine learning. Whereas the achievable limit in terms of regret minimization is now well known, our aim is to contribute to a better understanding of the performance in terms of identify…
Algorithm optimizes a single attribute in multi-armed bandits with constraints.
problem Optimizing a single attribute under multiple constraints in multi-armed bandits.
method Successive Rejects framework, information theoretic lower bound.
result Upper bound on probability of error decays exponentially with budget, nearly optimal in certain cases.
Study examines impact of missing data on multi-armed bandit algorithms.
problem Impact of missing data on performance of multi-armed bandit algorithms.
method Extensive simulation study of two-armed bandit algorithms with binary outcomes, considering different probabilities of missingness.
result Impact on performance varies depending on the balance between exploration and exploitation.
New method clusters items with bandit feedback without parametric assumptions.
problem Clustering with noisy observations from unknown distributions.
method Kernel-based approach to nonparametric clustering with bandit feedback.
result Adaptive algorithm with theoretical guarantees for unknown signal-to-noise ratio.
New policy combines Thompson sampling with best challenger rule for best arm identification.
problem Best arm identification in bandit framework with fixed confidence.
method Combines Thompson sampling with best challenger rule.
result Asymptotically optimal for any two-armed bandit problems, near optimal for general K-armed bandit problems.
Human decision-making deviates from the optimal solution, that maximizes cumulative rewards, in many situations. Here we approach this discrepancy from the perspective of bounded rationality and our goal is to provide a justification for such seemingly sub-optimal strategies. More specifically we investigate the hypoth…
Optimized Sharpe Ratio for better risk-adjusted decision-making in multi-armed bandits.
problem Challenging to optimize Sharpe Ratio (SR) in multi-armed bandits (MAB) due to constant regret.
method Proposed UCB-RSSR algorithm for RSSR maximization, derived path-dependent concentration bound and regret guarantees.
result UCB-RSSR outperforms existing algorithms and finds applications in risk-aware portfolio management.
UCB algorithm's arm-sampling behavior is revealed, leading to new insights and proofs.
problem Optimizing multi-armed bandit algorithms for worst-case scenarios.
method Analysis of UCB algorithm's arm-sampling behavior and process-level characterization.
result UCB's arm-sampling rates are asymptotically deterministic, regardless of problem complexity.
New algorithm for multi-player bandits in decentralized, asynchronous systems.
problem Challenges in decentralized, asynchronous multi-player bandits, including coordination and player detection.
method Adaptive exploration-exploitation algorithm that reduces collisions and detects player presence.
result Achieves regret of O ( T log T + log T / Δ 2 ) \mathcal{O}(\sqrt{T \log T} + {\log T}/{Δ^2}) O ( T log T + log T / Δ 2 ) . The exploration/exploitation (E/E) dilemma arises naturally in many subfields of Science. Multi-armed bandit problems formalize this dilemma in its canonical form. Most current research in this field focuses on generic solutions that can be applied to a wide range of problems. However, in practice, it is often the case…
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.
We propose a policy improvement algorithm for Reinforcement Learning (RL) which is called Rerouted Behavior Improvement (RBI). RBI is designed to take into account the evaluation errors of the Q-function. Such errors are common in RL when learning the Q Q Q -value from finite past experience data. Greedy policies or even …
Unified framework for response-adaptive targeting in multi-treatment experiments
problem Improving ethical and statistical efficiency in multi-treatment clinical trials
method Response-adaptive targeting strategies
result Unified framework for α α α -Rebalancing Targeting Strategies ( α α α RTS) New algorithm balances user reward and statistical inference by mixing TS with UR based on difference size.
problem Combining statistical inference with user reward in adaptive experiments.
method TS-PostDiff algorithm that uses UR when differences are small and TS when large.
result TS-PostDiff reduces false positives and increases statistical power for small differences, while maximizing reward for large ones.
Optimal algorithm for identifying best-arm with minimal regret.
problem Identifying the best arm in two treatments with limited budget.
method Neyman allocation based on outcome standard deviations.
result Neyman allocation is minimax optimal for simple regret.
New algorithms tackle RKHS bandits with reduced complexity and improved performance.
problem Adversarial and stochastic RKHS bandit problems with high computational complexity.
method Combining approximation theory with misspecified linear bandit methods.
result First general algorithm for adversarial RKHS bandit problem.
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.
Paper tackles LDP bandits learning with improved results and sub-linear regret.
problem Contextual bandits learning with LDP privacy constraints.
method Simple black-box reduction frameworks for context-free bandits, extended to GLB.
result First result for BCO with multi-point feedback under LDP, sub-linear regret for GLB.
Paper solves stochastic contextual linear bandits using linear bandit algorithms.
problem Stochastic contextual linear bandits with unknown context distribution.
method Establishes a reduction framework to convert to linear bandit problems.
result Achieves nearly optimal regret bound of O ( d T log T ) O(d\sqrt{T\log T}) O ( d T log T ) . 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 definition resolves ambiguity in non-stationary bandit classification.
problem Ambiguity in classifying non-stationary bandits using existing definitions.
method Introducing a formal definition that resolves ambiguity and provides a unified approach.
result Unified approach applicable to both Bayesian and frequentist formulations, resolves classification issues.
Unified approach for non-stationary and clustered bandits.
problem Solving non-stationary and clustered bandits with overlapping solutions.
method Test of homogeneity for seamless integration of non-stationary and clustered bandits.
result Unified solution framework for change detection and cluster identification.
A framework for auto-tuning hyper-parameters in contextual bandit algorithms.
problem Auto-tuning hyper-parameters in real-time for contextual bandit algorithms.
method Proposes a Syndicated Bandits framework to learn multiple hyper-parameters dynamically.
result Achieves optimal regret bounds under certain scenarios and handles multiple contextual bandit algorithms.
Stochastic multi-armed bandits form a class of online learning problems that have important applications in online recommendation systems, adaptive medical treatment, and many others. Even though potential attacks against these learning algorithms may hijack their behavior, causing catastrophic loss in real-world appli…
New algorithm learns optimal exploration parameters for contextual bandits.
problem Learning optimal exploration in contextual bandits.
method Proposes two algorithms that learn optimal exploration parameters online based on context and reward.
result Demonstrates improved performance in learning optimal exploration compared to traditional methods.