Overview

In adversarial bandits, a learner chooses among actions but observes feedback only for selected actions, while rewards or losses may vary arbitrarily or respond to past choices. The central goal is low regret against a comparator, using methods such as importance-weighted estimates, EXP3, online mirror descent, and follow-the-perturbed-leader. These ideas extend to contextual, linear, kernel, and combinatorial action spaces, as well as settings with delays, constraints, side observations, or switching comparators. A key tension is achieving strong guarantees against adversaries while adapting to stochastic structure, richer feedback, or practical computational limits.

Latest papers

62 papers8 papers in the last four weeks, up 60% on the four weeks before. 0.1% of all new papers.

May 28, 2025

Practical Adversarial Attacks on Stochastic Bandits via Fake Data Injection

Adversarial attacks on stochastic bandits have traditionally relied on some unrealistic assumptions, such as per-round reward manipulation and unbounded perturbations, limiting their relevance to real-world systems. We propose a more practical threat model, Fake Data Injection, which reflects realistic adversarial constraints: the attacker can inject only a limited number of bounded fake feedback samples into the learner's history, simulating legitimate interactions. We design effective attack strategies under this model, explicitly addressing both magnitude constraints (on reward values) and temporal constraints (on when and how often data can be injected). Our theoretical analysis shows that these attacks can mislead a class of bandit algorithms into selecting a target arm in nearly all rounds while incurring only sublinear attack cost. Experiments on synthetic and real-world datasets validate the effectiveness of our strategies, revealing vulnerabilities in stochastic bandit algorithms under practical adversarial scenarios.
Mar 3, 2024

Bandit Profit-maximization for Targeted Marketing

We study a sequential profit-maximization problem, optimizing for both price and ancillary variables like marketing expenditures. Specifically, we aim to maximize profit over an arbitrary sequence of multiple demand curves, each dependent on a distinct ancillary variable, but sharing the same price. A prototypical example is targeted marketing, where a firm (seller) wishes to sell a product over multiple markets. The firm may invest different marketing expenditures for different markets to optimize customer acquisition, but must maintain the same price across all markets. Moreover, markets may have heterogeneous demand curves, each responding to prices and marketing expenditures differently. The firm's objective is to maximize its gross profit, the total revenue minus marketing costs. Our results are near-optimal algorithms for this class of problems in an adversarial bandit setting, where demand curves are arbitrary non-adaptive sequences, and the firm observes only noisy evaluations of chosen points on the demand curves. For nn demand curves (markets), we prove a regret upper bound of O~(nT3/4)\tilde{O}(nT^{3/4}) and a lower bound of Ω((nT)3/4)Ω((nT)^{3/4}) for monotonic demand curves, and a regret bound of Θ~(nT2/3)\tildeΘ(nT^{2/3}) for demand curves that are monotonic in price and concave in the ancillary variables.