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.
New bandit algorithms focus on extreme values, outperforming existing methods.
problem Optimizing decisions based on extreme values rather than expected values.
method Robust statistics-based algorithms with vanishing extremal regret.
result The proposed algorithms achieve superior performance compared to existing methods.
Bandit algorithms struggle with consistent performance and robustness.
problem Achieving consistent and robust performance in stochastic multi-armed bandit settings.
method Analyzing regret minimization trade-offs and proposing distribution-oblivious algorithms.
result Logarithmic regret is inconsistent and super-logarithmic regret is necessary for consistent learning.
A new algorithm reduces regret in cooperative multi-agent bandits with heavy-tailed data.
problem Cooperative multi-agent bandits with heavy-tailed data.
method MP-UCB algorithm incorporating robust estimation with message-passing protocol.
result Optimal regret bounds for MP-UCB in various settings.
Paper addresses robust federated linear bandits against Byzantine attacks.
problem Byzantine attacks on a small fraction of agents in federated learning.
method Proposes a geometric median-based robust aggregation oracle.
result Achieves sublinear regret bound of i l d e O ( T 3 / 4 ) ilde{\mathcal{O}}({T^{3/4}}) i l d e O ( T 3/4 ) robust to fewer than half Byzantine agents. The paper tackles misspecification in contextual bandits by incorporating arm-specific variables.
problem Misspecification in contextual bandits due to unexplained inter-arm heterogeneity.
method Develops robust contextual bandit algorithms (RoLinUCB and RoLinTS) that incorporate arm-specific variables to address misspecification.
result The developed algorithms bound the n n n -round Bayes regret and show superior performance in various misspecification scenarios. Study robust best-arm identification in linear bandits with lower bounds and algorithms.
problem Identify a near-optimal robust arm in linear bandits with adversarial actions.
method Propose instance-dependent lower bounds and both static and adaptive bandit algorithms.
result Sample complexity matches the lower bound and algorithms effectively identify robust arms.
Robust algorithm optimizes corrupted Gaussian process bandits.
problem Sequential optimization of corrupted, expensive reward functions.
method Robust GP Phased Elimination (RGP-PE) algorithm.
result Algorithm balances robustness to corruptions with exploration and exploitation.
RoME optimizes mobile health interventions by modeling user and time-specific effects.
problem Challenges in optimizing mobile health interventions due to participant heterogeneity, nonstationarity, and nonlinear relationships.
method RoME uses a Robust Mixed-Effects contextual bandit algorithm with random effects, network cohesion penalties, and debiased machine learning.
result RoME achieves robust regret bounds even with complex baseline rewards, demonstrating superior performance in simulations and studies.
Paper addresses privacy and robustness in stochastic linear bandits.
problem Stochastic linear bandits with differential privacy and adversarial robustness.
method Logarithmic batch queries, arm elimination algorithm, two privacy models.
result First algorithms providing differential privacy and adversarial robustness.
Paper tackles robust batched bandits for heavy-tailed rewards.
problem Clinical trials and other applications with heavy-tailed rewards.
method Proposes robust batched bandit algorithms for heavy-tailed rewards in finite-arm and Lipschitz-continuous settings.
result Heavier-tailed rewards require fewer batches for near-optimal regret in the instance-independent regime and Lipschitz setting.
Improved ε ε ε -greedy handles strategic bidding in PPC auctions.
problem Strategic bidding in PPC auctions with personalization and corruptions.
method Extended ε ε ε -greedy to handle strategic arms in contextual multi-arm bandit. result ε ε ε -greedy is robust to adversarial corruptions and degrades linearly with corruption. 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.
Bayesian optimization improved for biased data.
problem Adversarial bias in observations, especially hidden confounders.
method Reduction to dueling bandits, information-directed sampling (IDS).
result First efficient kernelized algorithm with regret guarantees.
Motivated by applications of bandit algorithms in education, we consider a stochastic multi-armed bandit problem with ε \varepsilon ε -contaminated rewards. We allow an adversary to give arbitrary unbounded contaminated rewards with full knowledge of the past and future. We impose the constraint that for each time t t t the…
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 combat adversarial attacks in stochastic linear bandits.
problem Adversarial attacks on stochastic linear bandit rewards.
method Two variants of Robust Phased Elimination algorithms, one knowing C C C and one not. result Near-optimal regret in non-corrupted case and additive terms dependent on C C C . New bandit problem for finding best group of arms with worst mean reward.
problem Finding the best group of arms with the worst mean reward in overlapping groups.
method Two algorithms based on successive elimination and robust optimization.
result Upper bounds on the number of samples to find max-min optimal or near-optimal group.
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 develops a robust algorithm for contextual bandits with heavy-tailed rewards.
problem Contextual bandits with heavy-tailed rewards.
method Develops an algorithm based on Catoni's estimator for robust statistics, applying it to contextual bandits with general function approximation.
result Establishes regret bounds that depend on cumulative reward variance and logarithmically on the reward range and number of rounds.
New algorithm reduces regret in GLM bandits with tighter bounds.
problem Reducing regret in generalized linear contextual bandits.
method Double Doubly Robust (DDR) estimator for independence.
result First d \sqrt{d} d regret bound for GLM bandits. A robust bandit algorithm uses Dirichlet sampling to minimize regret under various distributional assumptions.
problem Robustness of bandit algorithms to model misspecification.
method Dirichlet Sampling (DS) algorithm based on pairwise comparisons and re-sampling of arm observations.
result Different DS variants achieve optimal regret guarantees for bounded distributions and logarithmic regret for semi-bounded distributions.
Contextual multi-armed bandit algorithms are widely used in sequential decision tasks such as news article recommendation systems, web page ad placement algorithms, and mobile health. Most of the existing algorithms have regret proportional to a polynomial function of the context dimension, d d d . In many applications ho…
New algorithms for best arm identification in bandits robust to misspecified parameters.
problem Inconsistent learning performance of traditional MAB algorithms when parameters are misspecified.
method Proposes two classes of asymptotically near-optimal algorithms for statistically robust MAB under fixed-budget pure exploration.
result Establishes fundamental performance limits and proposes algorithms that are asymptotically near-optimal.
Adapts to misspecification in contextual bandits using offline regression.
problem Unexpected regret due to misspecified reward models.
method Adapts to misspecification by reverting to a safe policy when necessary.
result Regret guarantees degrade gracefully with misspecification level.
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.
New algorithms robust to adversarial data achieve optimal performance.
problem Adversarial robustness in high-dimensional online learning problems.
method Alternating minimization scheme combining least-squares and convex reweighting.
result Achieves optimal robustness guarantees without distributional assumptions.
Study on private and robust multi-armed bandits with contaminated heavy-tailed rewards.
problem Private and robust multi-armed bandits with contaminated heavy-tailed rewards.
method Proposed a meta-algorithm with a private and robust mean estimation sub-routine exttt{PRM}.
result Achieved nearly-optimal regret for two heavy-tailed settings.
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.
New attack manipulates UCB algorithm, new defense algorithm reduces pseudo-regret.
problem Adversarial attacks on stochastic bandit algorithms.
method Introducing action-manipulation attacks and proposing a robust defense algorithm.
result Proposed defense algorithm reduces pseudo-regret to O(max{log T, A}).
A TS algorithm improves performance in multi-task bandits with transfer.
problem Improving performance across multiple related bandit tasks.
method A TS-type algorithm for online multi-task learning with a novel concentration inequality.
result The TS-type algorithm achieves nearly-optimal performance guarantees.
We tackle linear bandits with partially observable features, achieving sublinear regret.
problem Linear regret due to unobserved features in partially observable linear bandits.
method Feature augmentation with orthogonal basis vectors and a doubly robust estimator.
result Sublinear regret bound of i l d e O ( ( d + d h ) T ) ilde{O}(\sqrt{(d + d_h)T}) i l d e O ( ( d + d h ) T ) . Paper tackles stochastic k k k -submodular bandits with full feedback, achieving sublinear regret.
problem Online optimization of k k k -submodular functions with full-bandit feedback. method Proposes online algorithms for various k k k -submodular stochastic combinatorial multi-armed bandit problems. result Achieves sublinear α α α -regret bounds for multiple k k k -submodular stochastic combinatorial multi-armed bandit problems. A new algorithm improves regret bounds for contextual bandits.
problem Complexity of missing data in multi-armed bandits.
method Doubly Robust (DR) Thompson Sampling with contexts.
result Improved regret bound with i l d e O ( d T ) ilde{O}(d\sqrt{T}) i l d e O ( d T ) . New testing method for robust actor-critic bandit algorithms.
problem Balancing data collection for app performance and user adherence.
method Modified actor-critic algorithm and novel testing procedure.
result Testing procedure is robust to critic misspecification.
Unified framework for corruption-robust linear bandits with optimal gap-dependent misspecification bounds.
problem Effective learning in linear bandits with corrupted rewards across different corruption models.
method Unified framework for analyzing strong and weak corruption, connection to gap-dependent misspecification, and specialized algorithm.
result Optimal bounds for gap-dependent misspecification in linear bandits.
The paper tackles learning from imperfect human feedback, especially in dueling bandit problems.
problem Learning from human feedback that can be irrational or imperfect.
method Developed a Robustified Stochastic Mirror Descent for Imperfect Dueling (RoSMID) algorithm.
result Achieved nearly optimal regret for dueling bandit problems under imperfect human feedback.
Motivated by economic applications such as recommender systems, we study the behavior of stochastic bandits algorithms under \emph{strategic behavior} conducted by rational actors, i.e., the arms. Each arm is a \emph{self-interested} strategic player who can modify its own reward whenever pulled, subject to a cross-per…
New framework uses user feedback in CB problems for better decision-making.
problem Improving decision-making in contextual bandit problems with user-triggered feedback.
method Developed a new framework to leverage user-triggered feedback in CB problems, robust to feedback bias.
result Improved regret guarantees for CB algorithms using user feedback.
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. New algorithm robust to probabilistic unbounded adversarial attacks in bandit problems.
problem Powerful adversaries that can catastrophically perturb the revealed reward in bandit problems.
method Proposes med-E-UCB and med- ε ε ε -greedy algorithms based on sample median for robustness. result Achieves O ( log T ) \mathcal{O}(\log T) O ( log T ) pseudo-regret under arbitrary and unbounded reward perturbation. New algorithm reduces worst-case regret for heavy-tailed bandits.
problem Stochastic Multi-Armed Bandit problem with heavy-tailed rewards.
method Modified minimax policy MOSS with saturated empirical mean.
result Worst-case regret matching lower bound for heavy-tailed distributions.
New algorithm reduces regret in multi-agent bandits with malicious agents.
problem Collaboration between honest and malicious agents in multi-armed bandits.
method Dynamic reduction of communication with malicious agents, learning who is malicious.
result Algorithm reduces regret even with a single malicious agent, assuming m m m is small compared to K K K . Develops methods for reliable inference on batched bandit data.
problem Need for reliable inference methods based on adaptively-collected data from bandit algorithms.
method Introduces Batched OLS (BOLS) estimator for reliable inference on bandit data.
result BOLS is asymptotically normal and robust to non-stationarity in the baseline reward.
Algorithm identifies Pareto set in bandits with contaminated feedback.
problem Identifying Pareto set in multi-objective bandits with adversarial contamination.
method Sample median-based multi-objective adaptive elimination algorithm.
result Sample complexity bound that depends on contamination probability.
We investigate the feasibility of learning from a mix of both fully-labeled supervised data and contextual bandit data. We specifically consider settings in which the underlying learning signal may be different between these two data sources. Theoretically, we state and prove no-regret algorithms for learning that is r…
Efficient bandit exploration for various distributions without distribution-specific tuning.
problem Optimizing exploration in multi-armed bandit models for different distributions.
method Sub-sampling Duelling Algorithms (SDA) with Random Block sampling for efficient exploration.
result Achieves asymptotically optimal regret for Bernoulli, Gaussian, and Poisson distributions.
The paper refines and extends batched kernelized bandits, improving regret bounds and introducing a robust setting.
problem Optimizing black-box functions with noisy batches in Reproducing Kernel Hilbert Space.
method Refined and extended existing regret bounds, including adaptive batch sizes and robust optimization.
result Improved regret bounds for batched kernelized bandits, showing optimal number of batches and adaptive batch sizes.