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.
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.
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