Reactive bandits with attitude

Pedro A. Ortega, Kee-Eung Kim, Daniel D. LeeAISTATS 2015 · OpenReview

Abstract

We consider a general class of K-armed bandits that adapt to the actions of the player. A single continuous parameter characterizes the “attitude” of the bandit, ranging from stochastic to cooperative or adversarial. We provide a Bayesian algorithm that can learn to play optimally against these reactive systems.

Introduction

In the classic multi-armed bandit (MAB) problem, a player seeks to maximize cumulative rewards by choosing between several arms with unknown reward distributions. Traditionally, these problems are categorized as either stochastic (fixed distributions) or adversarial (worst-case distributions). However, many real-world systems—from financial markets to personalized recommendation engines—are reactive: they change their behavior in response to the player's actions.

Standard algorithms like UCB1 or Thompson Sampling often fail in these environments because they assume the environment is static or oblivious. This paper introduces a unified framework for reactive bandits, characterized by a single "attitude" parameter $\beta$, and proposes a Bayesian approach to learn and exploit these dynamics.

The Reactive Framework: Modeling "Attitude"

The authors model a reactive bandit where the reward distribution $Q(r)$ shifts based on the player's estimated policy $\hat{p}$ (the frequency of pulling each arm). This shift is governed by the parameter $\beta$:

  • $\beta = 0$: A standard stochastic bandit with no reaction.
  • $\beta > 0$ (Cooperative): The bandit increases rewards for arms the player prefers.
  • $\beta < 0$ (Adversarial): The bandit decreases rewards for preferred arms, forcing the player to explore or diversify.

By interpreting the expected reward as the derivative of the system's "free energy," the authors derive analytical solutions for optimal play, particularly for Gaussian reward distributions.

Optimal Strategies and Phase Transitions

The optimal strategy for a player depends heavily on the bandit's attitude. In adversarial settings ($\beta < 0$), the player often adopts a mixed strategy, randomizing between arms to prevent the bandit from suppressing rewards on any single arm. This follows a "water-filling" logic: as the environment becomes more hostile, the player spreads their "probability mass" across more arms.

Conversely, in cooperative settings ($\beta > 0$), the optimal strategy is always deterministic. Interestingly, as $\beta$ increases, the player should eventually favor the arm with the highest variance rather than the highest mean, as the cooperative bandit will "push" the high-variance outcomes in the player's favor.

Optimal arm selection probabilities $p$ as a function of the attitude parameter $\beta$. As $\beta$ becomes more negative (adversarial), the strategy becomes more mixed; as $\beta$ becomes positive (cooperative), it becomes deterministic.

The Bayesian Reactive Bandit Algorithm

To play optimally, a player must estimate not only the mean and variance of each arm but also the hidden attitude $\beta$. The authors propose a Bayesian algorithm that uses a Normal-Gamma conjugate prior to track these parameters. By employing Thompson Sampling combined with Gibbs Sampling, the algorithm generates a posterior distribution of the bandit's state and selects the action that maximizes expected utility under the estimated reactive model.

Convergence of the estimated attitude parameter $\beta$ over time $T$ using the proposed Bayesian Reactive Bandit algorithm.

Key Results and Limitations

The study demonstrates that popular "optimistic" algorithms like UCB1 suffer from linear regret in reactive environments. Because UCB1 does not account for the bandit's reaction, it can converge to a sub-optimal "effective" mean, essentially being manipulated by the environment. In contrast, the proposed Bayesian algorithm successfully learns the true value of $\beta$ and converges to the optimal strategy.

While the framework is robust, current analytical solutions rely on Gaussian assumptions. Future work could extend these Bayesian updates to other distributions (e.g., Bernoulli) and explore scenarios where the bandit's attitude $\beta$ is non-stationary, potentially evolving as the interaction progresses.

Summary updated

Abstract

We consider a general class of K-armed bandits that adapt to the actions of the player. A single continuous parameter characterizes the “attitude” of the bandit, ranging from stochastic to cooperat...
BibTeX
@inproceedings{ortega2015reactive,
  author = {Pedro A. Ortega and Kee-Eung Kim and Daniel D. Lee},
  title = {{Reactive bandits with attitude}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2015},
  url = {https://openreview.net/forum?id=u-Qhdstf43},
}
Figure