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.
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.
New algorithm tackles adversarial corruption in Lipschitz bandits with sub-linear regret.
problem Adversarial corruption in Lipschitz bandits.
method Developed robust Lipschitz bandit algorithms for weak and strong adversaries.
result Achieved sub-linear regret under both weak and strong adversaries.
Improved regret bounds for Tsallis-INF in adversarial bandits and corruptions.
problem Adversarial bandits and corruptions in multiarmed bandit problems.
method Improved regret bounds for Tsallis-INF algorithm.
result Achieves $\mathcal{O}\left(\left(\sum_{i
eq i^*} \frac{1}{Δ_i}
ight)\log_+\left(\frac{(K-1)T}{\left(\sum_{i
eq i^*} \frac{1}{Δ_i}
ight)^2}
ight)+\sqrt{C\left(\sum_{i
eq i^*}\frac{1}{Δ_i}
ight)\log_+\left(\frac{(K-1)T}{C\sum_{i
eq i^*}\frac{1}{Δ_i}}
ight)}
ight)$ regret bound.
Study non-linear combinatorial bandits with polynomial rewards, finding significant differences from linear cases.
problem Adversarial combinatorial bandits with general non-linear reward functions.
method Extending existing work on adversarial linear combinatorial bandits, analyzing minimax optimal regret for polynomial and non-polynomial reward functions.
result Minimax optimal regret bounds for adversarial combinatorial bandits with general non-linear reward functions.
New model for display advertising with stochastic and adversarial components.
problem Display advertising with stochastic and adversarial click-through-rates.
method Adversarial scaling model; two algorithms tested: action elimination and mirror descent.
result Two algorithms are robust to adversarial scaling.
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.
Improved regret bound for adversarial bandit convex optimisation.
problem Minimizing regret in zeroth-order adversarial bandit convex optimisation.
method Identifying an improved exploratory distribution for convex functions.
result Proved minimax regret bound of O ( d 2.5 n log ( n ) ) O(d^{2.5} \sqrt{n} \log(n)) O ( d 2.5 n log ( n )) . 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.
Study non-oblivious adversarial bandits with delayed feedback and propose algorithms with improved regret bounds.
problem Adversarial bandit problem with delayed, composite anonymous feedback.
method Propose wrapper algorithm for non-oblivious delay setting, achieving o ( T ) o(T) o ( T ) policy regret. result Achieve o ( T ) o(T) o ( T ) policy regret for many adversarial bandit problems with bounded memory loss sequences. New findings on universal learning in contextual bandits with adversarial rewards.
problem Learning in contextual bandits with time-varying, adversarial rewards.
method Characterization of learnable processes and necessary/sufficient conditions for universal learning.
result Optimistic universal learning for contextual bandits with adversarial rewards is impossible in general.
New algorithm for minimizing regret in adversarial dueling bandits.
problem Minimizing regret in dueling bandits with adversarial feedback.
method Introduced an algorithm with T T T -round regret of i l d e O ( K 1 / 3 T 2 / 3 ) ilde{O}(K^{1/3}T^{2/3}) i l d e O ( K 1/3 T 2/3 ) . result Algorithm achieves Ω ( K 1 / 3 T 2 / 3 ) Ω(K^{1/3}T^{2/3}) Ω ( K 1/3 T 2/3 ) regret lower bound. Study on reward poisoning attacks on CMAB, revealing attackability depends on adversary's knowledge.
problem Reward poisoning attacks on Combinatorial Multi-Armed Bandits (CMAB).
method Provided a sufficient and necessary condition for attackability, devised an attack algorithm.
result Attackability of CMAB depends on adversary's knowledge of the bandit instance.
This paper studies adversarial attacks on Gaussian process bandits.
problem Adversarial attacks on Gaussian process bandits to manipulate optimal function regions.
method Proposes various adversarial attack methods on GP bandits, including white-box and black-box attacks.
result Adversarial attacks can force GP bandits to optima in target regions even with low attack budgets.
New RL algorithm tackles adversarial RMAB with unknown transitions and bandit feedback.
problem Learning in episodic RMAB with unknown transition functions and adversarial rewards.
method Developed a novel RL algorithm with a biased reward estimator and an index policy.
result Achieved i l d e O ( H T ) ilde{\mathcal{O}}(H\sqrt{T}) i l d e O ( H T ) regret bound for adversarial RMAB. A new federated bandit problem with multiple adversaries, solved with a near-optimal algorithm.
problem Non-stochastic federated multi-armed bandit problem with multiple adversaries.
method Proposed a near-optimal federated bandit algorithm called FEDEXP3.
result Guaranteed sub-linear regret without exchanging sequences of selected arm identities or loss sequences among agents.
Algorithm improves online learning in adversarial bandits.
problem Online learning in adversarial multi-armed bandits with non-uniform best arm distribution.
method Online-within-online setup, inner and outer learners, leveraging non-uniform empirical distribution of best arms.
result Improves regret bounds for non-uniform best arm distributions.
Algorithm tackles adaptive discretization in adversarial Lipschitz bandits for dynamic pricing and auctions.
problem Adaptive discretization in adversarial Lipschitz bandits.
method Adversarial Zooming algorithm for adaptive discretization.
result First algorithm for adversarial Lipschitz bandits with instance-dependent regret bounds.
New algorithms balance collaboration and adversarial behavior in linear bandits.
problem Minimizing regret in a collaborative linear bandit problem with adversarial agents.
method Robust collaborative phased elimination algorithm with tight analyses.
result Achieves near-optimal regret bounds of $O\left(α+ 1/\sqrt{M}
ight) \sqrt{dT}$ for good agents.
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.
New algorithms reduce private bandit regret to nearly non-private levels.
problem Differentially private adversarial bandits and expert advice.
method Conversion of non-private algorithms to private, new algorithms for bandits and expert advice.
result Improved regret bounds for private bandits, sublinear for small ε.
First robust bandit algorithm for contextual bandits with sub-linear regret.
problem Vulnerability of linear contextual bandit algorithms to adversarial attacks.
method Proposes a robust bandit algorithm for stochastic linear contextual bandits under fully adaptive and omniscient attacks.
result Sub-linear regret under various attacks without requiring attack information.
A new algorithm reduces regret in bandit problems with adversarial corruptions.
problem Optimizing decision-making in bandit problems with variable uncertainties and adversarial interference.
method Proposes HCW-GLB-OMD, an OMD-based estimator with Hessian-based confidence weights for robustness.
result Achieves instance-wise minimax optimality with a κ κ κ -factor in the corruption term. New action poisoning attacks improve LinUCB's performance by changing action signals.
problem Improving understanding of adversarial attacks on contextual bandit algorithms.
method Proposed action poisoning attacks in white-box and black-box settings.
result Action poisoning attacks can force LinUCB to pull a target arm frequently with low cost.
New algorithm optimizes dueling bandits for both stochastic and adversarial preferences.
problem Optimizing decision-making in environments where only relative preferences are observed.
method Proposed a reduction from dueling bandits to multi-armed bandits, achieving optimal regret bounds.
result First best-of-both-world result for dueling bandits, optimal regret bound for Condorcet-winner benchmark.
New algorithms tackle adversarial combinatorial bandits with switching costs.
problem Adversarial combinatorial bandits with switching costs.
method Design algorithms operating in batches to restrict switches, proving lower bounds and achieving upper bounds on regret.
result Achieved upper bounds on regret for both bandit and semi-bandit feedback settings.
New algorithm tackles adversarial bandits with arbitrary strategies.
problem Adversarial bandit problem against arbitrary strategies.
method Adopted master-base framework using online mirror descent method (OMD). Proposed adaptive learning rates for OMD.
result Achieved improved regret bounds compared to previous methods.
Online learning algorithms are designed to learn even when their input is generated by an adversary. The widely-accepted formal definition of an online algorithm's ability to learn is the game-theoretic notion of regret. We argue that the standard definition of regret becomes inadequate if the adversary is allowed to a…
ABoB optimizes online configuration tuning by clustering parameters and accelerating learning.
problem Online optimization in large, dynamic parameter spaces.
method Hierarchical adversarial bandit framework.
result Significant performance gains in adversarial metric scenarios.
Unified meta-algorithm improves average performance across similar tasks in adversarial bandits.
problem Improving performance across multiple similar tasks in adversarial bandit settings.
method Unified meta-algorithm for multi-armed bandits and bandit linear optimization, tuning initialization, step-size, and entropy parameters.
result Unified meta-algorithm yields setting-specific guarantees for MAB and BLO, improving task-averaged regret.
Proposes online conformal prediction method with adversarial semi-bandit feedback.
problem Online uncertainty quantification with adversarial semi-bandit feedback.
method Formulates online conformal prediction as an adversarial bandit problem and uses regret minimization.
result Achieves long-run coverage guarantee with adversarial semi-bandit feedback.
We study the stochastic multi-armed bandits problem in the presence of adversarial corruption. We present a new algorithm for this problem whose regret is nearly optimal, substantially improving upon previous work. Our algorithm is agnostic to the level of adversarial contamination and can tolerate a significant amount…
Algorithm maximizes total reward in multi-agent bandits with adversarial corruptions.
problem Maximizing total reward in multi-agent bandits with adversarial corruptions.
method Proposes a cooperative learning algorithm robust to adversarial corruptions.
result Demonstrates an additive O ( ( L / L min ) C ) O((L / L_{\min}) C) O (( L / L m i n ) C ) regret term for an adversary with unknown corruption budget. We study adversarial attacks that manipulate the reward signals to control the actions chosen by a stochastic multi-armed bandit algorithm. We propose the first attack against two popular bandit algorithms: ε ε ε -greedy and UCB, \emph{without} knowledge of the mean rewards. The attacker is able to spend only logarithmic …
New algorithm reduces policy regret in tallying bandits.
problem Measuring online learning performance against adaptive adversaries.
method Tallying bandit model, efficient algorithm with complete policy regret guarantee.
result Achieves a complete policy regret guarantee of i l d e O ( m K T ) ilde{\mathcal{O}}(mK\sqrt{T}) i l d e O ( m K T ) . This paper optimizes attacks on stochastic bandits and proposes defenses against them.
problem Optimizing adversarial attacks on stochastic bandit algorithms.
method Designs optimal attack strategies and proposes defense algorithms.
result Optimal attack strategies and defense algorithms achieve near perfect performance.
Develops a strategy to minimize loss in both stochastic and adversarial environments for linear contextual bandits.
problem Linear contextual bandits with adversarial corruption.
method Proposes a novel strategy called Best-of-Both-Worlds (BoBW) RealFTRL, extending RealLinExp3 and FTRL.
result Regret upper bound of $O\left(\min\left\{\frac{(\log(T))^3}{Δ_{*}} + \sqrt{\frac{C(\log(T))^3}{Δ_{*}}},\ \ \sqrt{T}(\log(T))^2
ight\}
ight)$ , showing effectiveness in both stochastic and adversarial environments.
Two new algorithms improve performance in adversarial bandits with unbounded losses.
problem Adversarial Multi-Armed Bandits with unbounded losses.
method Developed UMAB-NN and UMAB-G for non-negative and general unbounded losses respectively.
result UMAB-NN achieves the first adaptive and scale-free regret bound for non-negative unbounded losses.
Unified framework for analyzing online convex optimization across various settings.
problem Analyzing online convex optimization in different settings and feedback types.
method Unified framework allowing systematic proposal and analysis of meta-algorithms.
result Comparable regret bounds for various feedback types and adversary types.
New algorithms tackle adversarial multi-player bandits with forced-collision communication.
problem No-sensing adversarial multi-player multi-armed bandits (MP-MAB) problem.
method Adversary-Adaptive Collision-Communication (A2C2) algorithms, attackability-aware and unaware settings, information-theoretic tools, error-correction coding.
result Asymptotic attackability-dependent sublinear regret achieved, with or without knowing attackability.
Meta-learning improves performance across similar tasks in adversarial bandit settings.
problem Improving performance across multiple similar tasks in adversarial bandit scenarios.
method Designing meta-algorithms that combine outer learners to tune hyperparameters of inner learners for MAB and BLO.
result Meta-algorithms improve task-averaged regret for MAB and BLO, showing direct relationship with action space-dependent measures.
Develops model selection for bandits balancing adversarial and stochastic guarantees.
problem Model selection in bandit scenarios with simultaneous adversarial and stochastic high-probability regret.
method Nested policy classes, balanced candidate regret bounds, mis-specification tests.
result Best of both world guarantees in linear bandits with simultaneous adversarial and stochastic environments.
Paper optimizes FTPL for adversarial and stochastic bandits with specific tail distributions.
problem Optimizing Follow-the-Perturbed-Leader (FTPL) policy for bandit problems.
method Analyzes FTPL with Fréchet-type tail distributions in adversarial and stochastic settings.
result FTPL with certain Fréchet-type tail distributions achieves O ( K T ) \mathcal{O}(\sqrt{KT}) O ( K T ) regrets in adversarial bandits. A federated learning algorithm tackles linear bandits with adversarial actions, achieving optimal regret bounds.
problem Federated linear bandits with finite adversarial action sets.
method FedSupLinUCB algorithm, extending SupLinUCB and OFUL principles.
result Achieves a total regret of i l d e O ( d T ) ilde{O}(\sqrt{d T}) i l d e O ( d T ) , matching minimax lower bound and being order-optimal. Multi-armed bandits a simple but very powerful framework for algorithms that make decisions over time under uncertainty. An enormous body of work has accumulated over the years, covered in several books and surveys. This book provides a more introductory, textbook-like treatment of the subject. Each chapter tackles a p…
Banker-OMD improves online learning with delayed feedback.
problem Handling delayed feedback in online learning.
method Generalized Online Mirror Descent (OMD) framework.
result Achieves nearly-optimal performance in three bandit scenarios.
Improved algorithm for contextual bandits with reduced regret.
problem Adversarial contextual bandits with i.i.d. contexts.
method Oracle-efficient relaxation with O ( T 2 3 ( K log ( ∣ Π ∣ ) ) 1 3 ) O(T^{\frac{2}{3}}(K\log(|Π|))^{\frac{1}{3}}) O ( T 3 2 ( K log ( ∣Π∣ ) ) 3 1 ) regret bound. result First to improve regret bound and match original bound for stochastic case.
Improved regret bounds for adversarial linear contextual bandits.
problem Adversarial linear contextual bandits with changing loss functions.
method Truncated continuous exponential weights algorithm over the probability simplex, analyzing with linear bandit setting without contexts.
result Second-order bound of i l d e O ( K d V T ) ilde O(K\sqrt{d V_T}) i l d e O ( K d V T ) and first-order bound of i l d e O ( K d L T ∗ ) ilde O(K\sqrt{d L_T^*}) i l d e O ( K d L T ∗ ) .