Adversarial Bandit

An adversarial bandit is a stripped-down decision problem designed for situations where rewards are not generated by a stable, friendly pattern. Each round, an agent picks one option—an “arm”—and sees only the reward or loss from that choice. The unseen options remain a mystery.

In a standard stochastic bandit, each arm has a fixed but unknown reward distribution. In an adversarial bandit, the reward (or loss) for every arm can change arbitrarily from round to round. Think of choosing an online advertisement while competitors, user traffic, or a hostile environment shift in response. The sequence can be preselected by an oblivious adversary, or, under stricter rules, react to earlier actions.

The agent cannot identify a permanently “best” arm, because none need exist. Instead, it aims for low regret: after many rounds, its total loss should be close to that of the single best fixed arm in hindsight. Crucially, it receives bandit feedback: only the loss of the chosen action, not a full table of what every action would have produced.

• Choosing known-good actions reduces immediate loss.
• Trying alternatives gathers evidence against a changing or deceptive reward sequence.
• The comparison remains fair: the benchmark must commit to one arm, just as the learner must act without seeing the current losses.

EXP3 is the classic algorithm. It assigns probabilities to arms using exponential weights, samples an arm, and builds an importance-weighted estimate of that arm’s loss. It also preserves explicit exploration probability, so no arm becomes impossible to sample. If exploration becomes too small, these estimates become extremely noisy; if it is too large, the agent wastes reward on poor choices. This setting matters because it gives reinforcement learning a robustness lens: rewards can be nonstationary, strategic, or engineered to exploit a simplistic policy, rather than clean samples from a fixed distribution.