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.
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-armed bandit and the linearly parameterized bandit…
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.
A multi-player bandit system resists adversarial attacks with near-optimal regret.
problem Adversaries attempt to manipulate rewards in a multi-player multi-armed bandit game.
method Players communicate a single bit to resist attacks, achieving near-optimal regret.
result Achieves near-optimal regret of O(log1+δT+W), where W is the total time of adversarial attacks. We consider a class of restless multi-armed bandit (RMAB) problems with unknown arm dynamics. At each time, a player chooses an arm out of N arms to play, referred to as an active arm, and receives a random reward from a finite set of reward states. The reward state of the active arm transits according to an unknown Ma…
We consider a fully decentralized multi-player stochastic multi-armed bandit setting where the players cannot communicate with each other and can observe only their own actions and rewards. The environment may appear differently to different players, i.e., the reward distributions for a given arm are heterog…
New study shows feedback doesn't improve MAB performance over erasure channels.
problem Distributed multi-armed bandit problem with arm erasure channels.
method Analyzed MAB with feedback and erasure channels, proving no improvement in regret.
result Regret lower bound of Ω(√KT + K / (1 - ε)) matches no-feedback upper bounds.
We consider stochastic multi-armed bandits where the expected reward is a unimodal function over partially ordered arms. This important class of problems has been recently investigated in (Cope 2009, Yu 2011). The set of arms is either discrete, in which case arms correspond to the vertices of a finite graph whose stru…
New bandit model for e-commerce with ordered categories.
problem Optimizing customer experience in e-commerce with unknown preferences.
method Introducing three types of ordering between categories and proving lower bounds on cumulative regret.
result Proved that algorithms can fully leverage the structure of the model with theoretical guarantees.
COF algorithm minimizes cost in multi-armed bandits with known costs and reward constraints.
problem Minimizing cost while meeting a minimum reward requirement in uncertain environments.
method COF algorithm that intelligently combines samples from all arms to gauge feasibility and minimize cost.
result COF achieves instance-dependent upper bounds on cumulative cost and quality regret.
Consider a nonparametric contextual multi-arm bandit problem where each arm a∈[K] is associated to a nonparametric reward function fa:[0,1]→R mapping from contexts to the expected reward. Suppose that there is a large set of arms, yet there is a simple but unknown structure amongst the arm reward…
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…
We introduce in this paper a new algorithm for Multi-Armed Bandit (MAB) problems. A machine learning paradigm popular within Cognitive Network related topics (e.g., Spectrum Sensing and Allocation). We focus on the case where the rewards are exponentially distributed, which is common when dealing with Rayleigh fading c…
We study the multi-armed bandit problem with multiple plays and a budget constraint for both the stochastic and the adversarial setting. At each round, exactly K out of N possible arms have to be played (with 1≤K≤N). In addition to observing the individual rewards for each arm played, the player also lea…
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.
BAICS identifies best arm with fairness constraints on subpopulations.
problem Identify the best arm while ensuring fairness across subpopulations.
method Formulated and solved BAICS problem, analyzed complexity, designed algorithm.
result Algorithm's sample complexity matches theoretical lower bound.
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.
We consider a multi-armed bandit framework where the rewards obtained by pulling different arms are correlated. We develop a unified approach to leverage these reward correlations and present fundamental generalizations of classic bandit algorithms to the correlated setting. We present a unified proof technique to anal…
New algorithm for countable bandits with optimal regret.
problem Stochastic bandit problem with countably many arms.
method Fully adaptive online learning algorithm with O(log n) expected cumulative regret.
result Achieves optimal regret of O(log n) after any number of plays n.
The paper tackles resource allocation for arms with unknown and random rewards, achieving optimal regret bounds.
problem Allocating resources on arms with unknown and random rewards.
method Developed two algorithms with optimal regret bounds for b∈[0,1], demonstrating a phase transition at b=1/2. result Achieved optimal gap-dependent and gap-independent regret bounds for b∈[0,1]. PAC best arm identification with a deadline, improving efficiency over sequential methods.
problem Identifying an optimal arm under a fixed time constraint.
method Elastic Batch Racing (EBR) algorithm for (ε,δ)-PAC best arm identification under a deadline. result EBR is optimal with respect to two hardness results and outperforms sequential methods.
We develop a novel and generic algorithm for the adversarial multi-armed bandit problem (or more generally the combinatorial semi-bandit problem). When instantiated differently, our algorithm achieves various new data-dependent regret bounds improving previous work. Examples include: 1) a regret bound depending on the …
Improves sampling speed of ARM models without losing accuracy.
problem Slow sampling from ARMs.
method Predictive sampling algorithm using ARM fixed-point iteration and learned forecasting modules.
result Significant improvements in sampling speed and efficiency.
We propose and study the known-compensation multi-arm bandit (KCMAB) problem, where a system controller offers a set of arms to many short-term players for T steps. In each step, one short-term player arrives to the system. Upon arrival, the player aims to select an arm with the current best average reward and receiv…
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.
We study the stochastic multi-armed bandit problem when one knows the value μ(⋆) of an optimal arm, as a well as a positive lower bound on the smallest positive gap Δ. We propose a new randomized policy that attains a regret {\em uniformly bounded over time} in this setting. We also prove several lower bound…
Motivated by the task of hyperparameter optimization, we introduce the non-stochastic best-arm identification problem. Within the multi-armed bandit literature, the cumulative regret objective enjoys algorithms and analyses for both the non-stochastic and stochastic settings while to the best of our knowledge, the best…
A new algorithm for competing agents in a two-sided market setting.
problem Decentralized competition between agents in a two-sided market with unknown valuations.
method UCB-D3 algorithm for UCB with Decentralized Dominant-arm Deletion.
result UCB-D3 is order optimal and achieves a new regret lower bound.
Study on bandit problem with fixed number of arm types, achieving optimal regret bounds.
problem Stochastic multi-armed bandit problem with a fixed number of arm types.
method Proposes algorithms achieving optimal regret bounds for the problem.
result Achieves $\mathcal{O}\left( \log n
ight)$ instance-dependent regret and $ ilde{\mathcal{O}}\left( \sqrt{n}
ight)$ instance-independent regret.
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.
Algorithm learns optimal arm selection in unsupervised sequential selection with contextual information.
problem Learning optimal arm selection in unsupervised sequential selection with contextual information.
method Proposes an algorithm for the contextual USS problem under the CWD property, demonstrating sub-linear regret.
result Demonstrates sub-linear regret for the proposed algorithm.
Algorithm identifies the best arm in linear bandits with high probability.
problem Best arm identification in linear multi-armed bandits with noisy measurements.
method Phased Elimination Linear Exploration Game (PELEG) using no-regret learners.
result PELEG achieves sample complexity matching lower bounds.
A new algorithm RESYNC for defenders against malicious attackers in multi-player bandits.
problem Malicious players colliding with cooperative players to prevent rewards.
method Decentralized and robust algorithm RESYNC for defenders.
result RESYNC algorithm is order-optimal, performing gracefully as the number of collisions increases.
We consider a decentralized multi-agent Multi Armed Bandit (MAB) setup consisting of N agents, solving the same MAB instance to minimize individual cumulative regret. In our model, agents collaborate by exchanging messages through pairwise gossip style communications on an arbitrary connected graph. We develop two no…
Memory-limited learning tackles adversarial bandits with reduced storage.
problem Adversarial bandit problem with limited memory storage.
method Hierarchical learning policy with sublinear memory requirement.
result Established sublinear regret bounds for weak and shifting regrets.
Study best arm identification with safety constraints in bandit problems.
problem Real-world decision-making with safety constraints.
method Analyzed linear and monotonic reward and safety constraints, proposed algorithms.
result Guaranteed safe learning in both linear and general reward/safety constraint settings.
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.
PyXAB is a Python library for X-armed bandits and online optimization.
problem Efficiently solving X-armed bandit problems and online blackbox optimization.
method Implementation of 10+ X-armed bandit algorithms and synthetic objectives.
result Evaluation of different algorithms' performance on various synthetic objectives.
This paper studies continuum-armed bandits under Besov smoothness conditions and derives minimax rates.
problem Optimizing an unknown function with limited evaluations.
method Studies continuum-armed bandits under Besov smoothness conditions and derives minimax rates.
result Minimax rates over Besov spaces are identical to those over the smallest Hölder space into which Besov spaces embed.
This paper studies the Best-of-K Bandit game: At each time the player chooses a subset S among all N-choose-K possible options and observes reward max(X(i) : i in S) where X is a random vector drawn from a joint distribution. The objective is to identify the subset that achieves the highest expected reward with high pr…
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.
New algorithm for collaborative bandit learning reduces sample complexity and regret.
problem Optimal arm identification in a multi-agent bandit model with communication.
method Phased elimination with data-dependent sampling schemes.
result Near-optimal algorithm for pure exploration in collaborative bandit learning.
Algorithm optimizes two objectives in bandits: minimizing regret and identifying best arm.
problem Balancing exploration and exploitation for optimal performance in multi-armed bandits.
method Design and analysis of BoBW-lil'UCB(γ) algorithm, establishing lower bounds. result BoBW-lil'UCB(γ) achieves optimal performance for RM or BAI under different γ values. For the stochastic multi-armed bandit (MAB) problem from a constrained model that generalizes the classical one, we show that an asymptotic optimality is achievable by a simple strategy extended from the εt-greedy strategy. We provide a finite-time lower bound on the probability of correct selection of an optimal ne…
Paper proposes Adaptive Pareto Exploration for identifying Pareto optimal arms in multi-objective scenarios.
problem Identifying Pareto optimal arms in multi-objective scenarios with relaxed constraints.
method Adaptive Pareto Exploration strategy for different relaxations of Pareto Set Identification.
result Reduction in sample complexity when identifying at most k Pareto optimal arms.
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.
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.
In this paper we propose the multi-objective contextual bandit problem with similarity information. This problem extends the classical contextual bandit problem with similarity information by introducing multiple and possibly conflicting objectives. Since the best arm in each objective can be different given the contex…