KL-UCB+ policy outperforms KL-UCB empirically in stochastic bandits.
problem Optimizing decisions in a stochastic bandit problem.
method Demonstrates a simple proof of asymptotic optimality for KL-UCB+ policy.
result KL-UCB+ policy achieves asymptotically optimal regret bound.
New algorithm outperforms existing ones in multi-player bandit problems without sensing.
problem Decentralized multi-player multi-armed bandit problem without collision or sensing info.
method Randomized Selfish KL-UCB, inspired by Selfish KL-UCB, with low complexity.
result Randomized Selfish KL-UCB outperforms state-of-the-art algorithms in almost all environments.
Adaptive KL-UCB algorithm for Markov and i.i.d. rewards.
problem Regret minimization for Markovian and i.i.d. rewards in MAB problems.
method Identifies Markovian vs. i.i.d. rewards, switches between KL-UCB variants.
result Logarithmic regret for both i.i.d. and Markovian settings.
UCBoost improves bandit algorithms to balance optimality and complexity.
problem Finding near-optimal multi-armed bandit algorithms with low complexity.
method Boosting approach to Upper Confidence Bound (UCB) algorithms.
result UCBoost algorithms achieve near-optimal regret guarantees with significantly reduced computational complexity.
New algorithm minimizes regret in stochastic bandits.
problem Minimizing regret in stochastic bandit models.
method Proposes kl-UCB ++ algorithm for exponential families.
result Proves asymptotic and minimax optimality.
This paper is about index policies for minimizing (frequentist) regret in a stochastic multi-armed bandit model, inspired by a Bayesian view on the problem. Our main contribution is to prove that the Bayes-UCB algorithm, which relies on quantiles of posterior distributions, is asymptotically optimal when the reward dis…
KL-UCB-switch optimizes bandit strategies for both distribution-dependent and distribution-free performance.
problem Optimizing regret bounds for stochastic bandits.
method Combining MOSS and KL-UCB strategies.
result Achieves both optimal distribution-dependent and distribution-free regret bounds.
Proposes k-NN UCB for multi-armed bandits with covariates.
problem Optimizing decisions in multi-armed bandits with covariates.
method k-Nearest Neighbour UCB algorithm for low-dimensional data.
result Minimax optimal regret bound and empirical advantage.
New findings show many popular bandit algorithms are unstable, contradicting minimax optimality.
problem Challenges in statistical inference from bandit algorithms due to adaptive, non-i.i.d. nature.
method Analysis of stability properties of optimism-based bandit algorithms.
result Widely used minimax-optimal UCB-style algorithms are unstable.
GLR-klUCB detects change-points in non-stationary bandits efficiently.
problem Non-stationary bandit problems with piecewise stationary behavior.
method Combines kl-UCB with a changepoint detector based on GLR.
result Achieves O ( T A Υ T log ( T ) ) O(\sqrt{TA Υ_T\log(T)}) O ( T A Υ T log ( T ) ) regret for some instances. The paper tackles best arm identification with minimal regret in experiments.
problem Identifying the best arm with minimal regret in experiments.
method Information-theoretic techniques and Double KL-UCB algorithm.
result Achieves asymptotic optimality in identifying the best arm with minimal regret.
We study a generalization of the multi-armed bandit problem with multiple plays where there is a cost associated with pulling each arm and the agent has a budget at each time that dictates how much she can expect to spend. We derive an asymptotic regret lower bound for any uniformly efficient algorithm in our setting. …
The paper analyzes the sliding regret of stochastic bandit algorithms.
problem Measuring the one-shot behavior of no-regret algorithms in stochastic bandits.
method Introducing sliding regret to measure the worst pseudo-regret over a time-window.
result Randomized methods have optimal sliding regret, while index policies have the worst possible sliding regret.
The profitable bandit problem aims to maximize earnings by choosing actions with uncertain rewards.
problem Maximizing earnings from uncertain rewards in a subset selection problem.
method Adapted and studied three strategies: kl-UCB, Bayes-UCB, and Thompson Sampling.
result Establishes asymptotic optimality for each strategy with finite time regret bounds.
A new algorithm for better decision-making in recommendation systems.
problem Stochastic multi-armed bandit problem and cold start problem in recommender systems.
method Proposes Hellinger-UCB, a variant of UCB algorithm using squared Hellinger distance.
result Hellinger-UCB reaches the theoretical lower bound and outperforms other algorithms in practical applications.
New algorithms improve privacy in bandit problems with partial information.
problem Privacy constraints in multi-armed bandit problems with partial reward information.
method Proposed a generic framework for designing ε ε ε -global DP extensions of UCB and KL-UCB algorithms. result AdaP-KLUCB algorithm achieves optimal regret bound under ε ε ε -global DP constraints. New method reduces multi-armed bandit regret to near-optimal levels.
problem Improving regret bounds for KL-regularized multi-armed bandits.
method Sharp analysis of KL-UCB with peeling argument.
result First high-probability regret bound with linear dependence on K.
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…