DBA: Dynamic Multi-Armed Bandit Algorithm

Sadegh NobariAAAI 2019 · DOI

Abstract

Standard Multi-Armed Bandit (MAB) algorithms often struggle to maintain performance when the optimal choice changes over time. This paper introduces the Dynamic Bandit Algorithm (DBA), which models reward trends as a continuous process (a Wiener process) to detect and adapt to shifting preferences. Experimental results demonstrate that DBA reacts to trend interchanges nearly three times faster than traditional bandit approaches, significantly improving Key Performance Indicators (KPIs) in dynamic environments.

Introduction

In the classic Multi-Armed Bandit problem, an algorithm seeks to maximize rewards by balancing the exploration of new options with the exploitation of known high-performers. However, traditional MAB frameworks typically assume that the underlying reward for an arm is relatively stable.

In real-world applications, such as e-commerce or digital advertising, popularity is inherently dynamic. For instance, a seasonal item may be unpopular for most of the year but become a high-performer during a specific holiday. Standard bandits are often heavily biased toward historical data (priors), taking significant time to "unlearn" old trends. By the time a traditional bandit adapts to a new trend, the opportunity may have passed. The DBA addresses this by providing a lightweight, production-ready algorithm sensitive enough to pivot as trends shift.

Methodology: Modeling Change as a State

The core innovation of the DBA is treating the performance of each arm as a dynamic state rather than a static value.

Wiener Process Modeling

DBA models the reward of each arm using a Wiener process (standard Brownian motion). This approach assumes that the mean reward of an arm evolves over time with Gaussian increments, allowing the model to "expect" and account for continuous change.

State-Space Representation

The algorithm utilizes a state-space model to track the evolution of rewards. It maintains a multivariate normal distribution where the mean of the reward follows another normal distribution, tracking past ($X_{i-1}$), present ($X_i$), and future ($X_{i+1}$) states.

The state-space representation of the DBA model, illustrating the relationship between sequential states and precision parameters.

To prevent overfitting to transient noise, the authors implement prior normal distributions and a precision parameter ($\tau$). This parameter acts as a control dial, determining how much the state is permitted to drift between steps. Despite this mathematical complexity, DBA is designed to be computationally efficient, making it suitable for real-time production environments like website layout optimization.

Experimental Evaluation

The authors evaluated DBA using synthetic datasets featuring "interchanging trends" (both linear and non-linear performance curves). This setup allowed for precise control over the timing and frequency of shifts in the "best" arm. Simulations involved 500 participants over 100 trials to ensure statistical significance.

Key Results and Discussion

The primary metric for success was the "lift" in a Key Performance Indicator (KPI) compared to a baseline of random selection (A/B testing).

  • Superior Adaptation: In a 3-arm scenario with interchanging linear trends, the original Bandit achieved a 9% lift over A/B testing. In contrast, the DBA achieved a 24% lift.
  • 3x Performance Improvement: DBA outperformed the standard bandit by nearly three times in its ability to capture profitable options during trend shifts.
  • Proximity to the Oracle: As shown in the performance comparisons, DBA's performance curve closely tracks the "Upper Bound" (the theoretical maximum profit), whereas standard bandits lag significantly.
KPI comparison across different methods, highlighting the 24% lift achieved by DBA compared to traditional approaches.

Conclusion and Future Work

The DBA represents a significant step forward in making reinforcement learning practical for volatile, real-world environments. By modeling the process of change rather than just the current state, it gains a "recency advantage" that allows for rapid adaptation.

Future research will focus on integrating Contextual Bandits—incorporating user-specific data like demographics—with the temporal dynamics of DBA. Additionally, the authors suggest that the DBA logic could be integrated into more complex recommendation frameworks, such as Collaborative Filtering or Cascading Bandits, to further enhance personalization in changing markets.

Summary updated

BibTeX
@inproceedings{nobari2019dba,
  author = {Sadegh Nobari},
  title = {{DBA: Dynamic Multi-Armed Bandit Algorithm}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33019869},
}
Figure