Adaptive Bandits: Towards the best history-dependent strategy

Odalric-Ambrym Maillard, Rémi MunosAISTATS 2011 · OpenReview

Introduction

Standard multi-armed bandit (MAB) algorithms, such as UCB or EXP3, are designed to minimize "external regret"—the difference between the player's total reward and the reward of the best constant action in hindsight. While effective in stochastic or oblivious adversarial settings, these algorithms often fail in adaptive environments where the opponent reacts to the player's history. Examples include viral mutations in response to drug treatments or strategic shifts in financial markets. In such cases, the optimal strategy is not a fixed action but a history-dependent sequence.

The $\Phi$-Constrained Framework

To address this, we introduce a framework for $\Phi$-constrained opponents. We assume the environment's behavior depends on an equivalence class of the history, defined by a mapping function $\Phi$. This allows us to model opponents with finite memory (e.g., Markovian memory of length $m$) or periodic behaviors.

Crucially, we redefine the performance metric from external regret to $\Phi$-regret. $\Phi$-regret compares the algorithm's performance against the best strategy that maps each history class to a specific action. This shift provides a realistic and achievable target in reactive environments.

Algorithmic Approach

We propose two primary algorithmic strategies:

  1. Known Model ($\Phi$-UCB / $\Phi$-EXP3): If the memory structure $\Phi$ is known, the agent maintains a separate bandit instance for each equivalence class.
  2. Pool of Models ($\Theta$): When the true structure is unknown, we consider a pool of potential models. We frame this as a "Sleeping Bandits" problem, where only one equivalence class per model is "awake" at any time. We utilize the EXP4 meta-algorithm to aggregate recommendations from these different $\Phi$-experts.

To handle the fact that the meta-algorithm plays a mixture of expert recommendations—preventing individual experts from playing their specific choices—we introduce the "Rebel-Bandit" analysis. This allows for proper weight updates via importance sampling despite the action mismatch.

Results and Empirical Evaluation

Theoretically, we establish that for a known model $\Phi$, our algorithms achieve a tight regret bound of $\tilde{O}(\sqrt{TAC})$. For an unknown pool $\Theta$, the bound is $O(T^{2/3} C^{1/3} \log(|\Theta|)^{1/2})$. Notably, the logarithmic dependence on the pool size $|\Theta|$ ensures computational tractability even for large hypothesis sets.

Empirical comparison of External Regret (red) and $\Phi$-Regret (cyan) for various bandit algorithms in an adaptive environment.

Empirical simulations against an opponent that rewards switching (memory $m=1$) demonstrate the limitations of standard approaches. As shown in Figure 1, standard UCB and EXP3 suffer high external regret. In contrast, our proposed meta-algorithms (e.g., Exp4U, Exp4E) successfully adapt to the opponent's reactive nature, minimizing $\Phi$-regret and identifying optimal alternating strategies, often achieving negative $\Phi$-regret values which indicate performance superior to the best fixed-strategy benchmark.

Conclusion

By moving beyond the "best constant action" paradigm, this work provides a robust framework for learning in reactive environments. While a gap remains between the $T^{1/2}$ bound for known models and the $T^{2/3}$ bound for unknown pools, the proposed methods offer a computationally feasible path toward truly adaptive bandit strategies.

Summary updated

BibTeX
@inproceedings{maillard2011adaptive,
  author = {Odalric-Ambrym Maillard and Rémi Munos},
  title = {{Adaptive Bandits: Towards the best history-dependent strategy}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2011},
  url = {https://openreview.net/forum?id=m6o7PZRIfM},
}
Figure