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.
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.
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.
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.
Study on Pareto optimality in multi-objective bandit problems.
problem Pareto optimality in multi-objective multi-armed bandit problems.
method Formulated adversarial multi-objective multi-armed bandit, defined Pareto regrets, presented algorithms, established upper and lower bounds.
result New algorithms are optimal in adversarial settings and nearly optimal in stochastic settings.
Algorithm improves multi-armed bandit performance by transferring reward samples.
problem Sequential multi-armed bandit problem with changing reward distributions.
method UCB algorithm with reward sample transfer.
result Significant improvement in cumulative regret over standard UCB.
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.
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.
Paper uses subjective logic to estimate uncertainty in multi-armed bandit problems.
problem Estimating uncertainty in multi-armed bandit problems.
method Formalism of subjective logic applied to multi-armed bandits, proposing new algorithms.
result Subjective logic quantities enable useful assessment of uncertainty.
Study collaborative learning among multi-agents in multi-armed bandits.
problem Minimizing group cumulative regret in a heterogeneous multi-agent setting.
method Developed decentralized algorithms for collaboration between N N N agents learning M M M stochastic multi-armed bandits. result Proved near-optimal behavior of proposed algorithms for group regret.
Study finds optimal regret bound for multi-armed bandit problem with expert advice.
problem Optimizing decision-making in a multi-armed bandit problem with expert advice.
method Proved a tight lower bound matching the upper bound of Kale (2014) for minimax expected regret.
result The minimax optimal expected regret is Θ(√(T K log (N/K))) for the 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.
New algorithm tackles multi-player bandit problems with limited access to arms.
problem Limited access to dynamic local subsets of arms in multi-player multi-armed bandit problems.
method Adopted Upper Confidence Bound (UCB) for exploration-exploitation and distributed optimization for collisions.
result Proposes a decentralized algorithm with near-optimal regret guarantee.
We study the problem of identifying the top m m m arms in a multi-armed bandit game. Our proposed solution relies on a new algorithm based on successive rejects of the seemingly bad arms, and successive accepts of the good ones. This algorithmic contribution allows to tackle other multiple identifications settings that w…
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…
New algorithm prevents strategic replication in multi-armed bandit problems.
problem Strategic replication by agents can exploit bandit algorithms' balance.
method Designs Hierarchical UCB (H-UCB) and Robust Hierarchical UCB (RH-UCB) algorithms.
result Achieves O ( ln T ) O(\ln T) O ( ln T ) -regret and sublinear regret in realistic scenarios. The paper explores sampling problems and shows minimal exploration is needed.
problem Exploration-exploitation trade-off in sampling.
method Systematic definition of regret, proposal of a simple algorithm.
result Near-optimal regret bounds achieved with minimal exploration.
In this paper we propose a multi-armed bandit inspired, pool based active learning algorithm for the problem of binary classification. By carefully constructing an analogy between active learning and multi-armed bandits, we utilize ideas such as lower confidence bounds, and self-concordant regularization from the multi…
We present a formal model of human decision-making in explore-exploit tasks using the context of multi-armed bandit problems, where the decision-maker must choose among multiple options with uncertain rewards. We address the standard multi-armed bandit problem, the multi-armed bandit problem with transition costs, and …
Optimal algorithm found for collaborative learning in bandits with optimal regret bounds.
problem Minimizing regret in collaborative multi-agent bandit problems.
method Proposed an algorithm with optimal regret bounds for collaborative multi-agent multi-armed bandit model.
result First algorithm with order optimal regret bounds for collaborative bandit model.
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 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.
Simple greedy algorithms can excel in multi-objective bandits with multiple good arms.
problem Optimizing multiple objectives in bandits is traditionally harder.
method Introduced greedy algorithms that exploit multiple good arms for multiple objectives.
result Simple greedy algorithms achieve strong performance in multi-objective bandits.
New method for contextual bandits with corrupted context.
problem Contextual bandits with corrupted context in online settings.
method Combining contextual bandit and multi-armed bandit approaches.
result Improved learning from all iterations, including corrupted ones.
A new multi-armed bandit framework with credal sets for uncertain outcomes.
problem Optimizing decisions under uncertainty with unknown outcomes.
method Introduces a novel multi-armed bandit framework with credal sets and defines regret as lower prevision.
result Upper bounds on regret for certain hypothesis classes and lower bounds for special cases.
We consider the stochastic linear (multi-armed) contextual bandit problem with the possibility of hidden simple multi-armed bandit structure in which the rewards are independent of the contextual information. Algorithms that are designed solely for one of the regimes are known to be sub-optimal for the alternate regime…
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
The study analyzes batched methods for early stopping in stochastic multi-armed bandits.
problem Early stopping in stochastic multi-armed bandits with fixed confidence.
method Instance-dependent lower bounds and a general batched algorithm with upper bounds.
result Upper and lower bounds on the number of batches and sample complexity.
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. The paper tackles lifelong learning in multi-armed bandits, aiming to minimize average regret over multiple tasks.
problem Minimizing average regret in multi-armed bandits over multiple tasks.
method Confidence interval tuning of UCB algorithms and greedy algorithms applied to a bandit over bandit approach.
result Empirical improvement over previous work in the mortal bandit problem.
New algorithms improve multi-task bandit performance by transferring reward samples.
problem Sequential multi-task bandit problems with adjacent similar tasks.
method Two UCB-based algorithms that transfer reward samples between tasks.
result Transfer of reward samples reduces overall regret compared to no transfer.
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…
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.
Sequential portfolio selection has attracted increasing interests in the machine learning and quantitative finance communities in recent years. As a mathematical framework for reinforcement learning policies, the stochastic multi-armed bandit problem addresses the primary difficulty in sequential decision making under …
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.
DPPS uses DP priors for Bayesian non-parametric multi-arm bandits.
problem Optimizing multi-arm bandit environments with prior beliefs.
method Bayesian non-parametric algorithm based on Dirichlet Process priors.
result DPPS provides principled incorporation of prior beliefs and is optimal in Bayesian regret setup.
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.
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.
A new algorithm for resource-aware multi-armed bandits minimizes regret.
problem Optimizing resource usage in a multi-armed bandit problem with censored observations.
method UCB-inspired online learning algorithm with theoretical regret analysis.
result The proposed algorithm outperforms standard multi-armed bandit algorithms in simulations.
Paper tackles transfer learning for contextual multi-armed bandits under covariate shift.
problem Nonparametric contextual multi-armed bandits with covariate shift.
method Established minimax rate of convergence, proposed transfer learning algorithm.
result Achieved near-optimal statistical guarantees for learning in target domain.
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.
Proposes Genetic Thompson Sampling for multi-armed bandits, improving performance in nonstationary settings.
problem Improving sequential decision making tasks of online learning agents using multi-armed bandits.
method Integrates genetic principles into Thompson Sampling for multi-armed bandits.
result Significantly outperforms baselines in nonstationary settings.
New algorithms improve performance guarantees for multi-armed bandits problems.
problem Allocating effort under uncertainty in scenarios like investing research effort.
method Proposed two new families of bandit algorithms with stronger guarantees.
result Achieved optimal dependence on k with additional properties of arm reward curves.
Contextual bandits are a form of multi-armed bandit in which the agent has access to predictive side information (known as the context) for each arm at each time step, and have been used to model personalized news recommendation, ad placement, and other applications. In this work, we propose a multi-task learning frame…
We consider a variant of the classic multi-armed bandit problem where the expected reward of each arm is a function of an unknown parameter. The arms are divided into different groups, each of which has a common parameter. Therefore, when the player selects an arm at each time slot, information of other arms in the sam…
Algorithm minimizes regret in multi-criteria bandits with constraints.
problem Optimize primary attribute while respecting secondary constraints.
method Con-LCB algorithm that guarantees logarithmic regret and feasibility identification.
result Logarithmic regret and feasibility identification with high probability.
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…
New algorithm for multi-fidelity bandits reduces costs and improves regret.
problem Optimizing decisions with varying costs and accuracy in multi-fidelity bandits.
method Cost complexity bounds, algorithmic framework, elimination-based algorithm.
result New regret definition and matching upper and lower bounds for elimination-based algorithm.