A Finite Memory Automaton for Two-Armed Bernoulli Bandit Problems

Ariel RaoAAAI 2017 · DOI

Introduction

The Multi-Armed Bandit (MAB) problem is a fundamental challenge in decision theory, requiring an agent to balance the exploration of unknown options with the exploitation of known rewards. Traditional solutions often rely on two key assumptions: perfect recall of all past actions and rewards, and prior knowledge of whether the environment is static or dynamic. However, in resource-constrained or unpredictable real-world scenarios, these assumptions frequently fail. This paper proposes a Finite Memory Automaton (FMA) that operates under imperfect recall and maintains robustness across varying environmental stabilities.

Methodology: Ranking over Estimation

The core innovation of the FMA is the shift from reward probability estimation to relative ranking. Instead of calculating precise payoff probabilities, the FMA uses a finite state space where each state represents a pair of rankings for the two arms. This approach recognizes that to maximize reward, an agent only needs to know which arm is better, not the exact magnitude of the difference.

Key Components

  • Finite State Space: Rankings are constrained within a finite range (1 to $m$), representing the agent's "beliefs."
  • Confidence-Based Action: The agent's tendency to explore is inversely proportional to its confidence. Large differences in rankings lead to exploitation, while similar rankings trigger exploration.
  • Transition and Inertia: The FMA updates rankings based on recent rewards. To mitigate "recency bias"—the tendency of finite memory systems to overreact to single data points—the authors implement an "inertia" mechanism. Higher traversal scores require a consistent pattern of rewards before the automaton transitions to a new ranking state, effectively simulating memory without storing raw historical data.

Experimental Evaluation

The FMA was evaluated against standard baselines, including $\epsilon$-greedy, the Bayesian Learning Automaton (BLA), and Thompson Sampling, across simulated Two-Armed Bernoulli Bandit (TABB) environments ranging from static to highly dynamic.

Static and Short-Term Performance

In environments with constant payoff probabilities, the FMA demonstrates rapid convergence. As shown in the short-term analysis, the FMA variants achieve low regret quickly, performing comparably to specialized estimation-based models like the BLA within the initial 500 steps.

Regret performance over the first 500 steps, showing FMA's competitive convergence rates against standard baselines.

Long-Term Robustness in Mixed Environments

The true strength of the FMA lies in its flexibility. In mixed environments where payoff probabilities may shift, the FMA maintains a consistently low regret profile over long horizons. While specialized algorithms might perform better in the specific environment they were tuned for, the FMA maintains high performance across the board without requiring manual re-tuning or specialized mechanisms for detecting environmental shifts.

Regret performance over 10,000 steps. While standard algorithms like Thompson Sampling show increasing regret in complex environments, the FMA variants maintain stability.

Conclusion and Future Work

The Finite Memory Automaton provides a computationally efficient and robust alternative to traditional MAB algorithms. By prioritizing ranking over estimation, it achieves high performance in both static and dynamic settings with minimal memory requirements. Future research will focus on scaling the ranking logic to $N$-armed problems, where the state space may grow exponentially, and providing formal mathematical proofs for the observed regret bounds compared to traditional Upper Confidence Bound (UCB) strategies.

Summary updated

BibTeX
@inproceedings{rao2017finite,
  author = {Ariel Rao},
  title = {{A Finite Memory Automaton for Two-Armed Bernoulli Bandit Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.11115},
}
Figure