BelMan: Bayesian Bandits on the Belief-Reward Manifold

Debabrota Basu, Pierre Senellart, Stéphane BressanarXiv 2018 · arXiv

Abstract

The multi-armed bandit (MAB) problem represents the fundamental challenge of balancing exploration and exploitation. While frequentist and Bayesian methods are well-established, they often lack a unified framework capable of handling diverse reward distributions and complex learning objectives. This paper introduces BelMan, a novel Bayesian bandit algorithm grounded in information geometry. By representing beliefs and rewards as points on a statistical manifold, BelMan utilizes alternating projections to achieve asymptotic optimality. Empirical evaluations across Bernoulli, exponential, and queueing bandit scenarios demonstrate that BelMan consistently outperforms state-of-the-art methods like Thompson Sampling and KL-UCB.

Introduction

The multi-armed bandit (MAB) problem is the quintessential model for the exploration-exploitation trade-off: an agent must decide whether to stick with the best-performing known option (exploitation) or explore new options to gather information (exploration). Traditional frequentist algorithms, such as Upper Confidence Bound (UCB), and Bayesian methods, such as Thompson Sampling, are effective but often struggle to incorporate prior knowledge seamlessly or generalize across different reward distributions and learning modes (e.g., pure exploration vs. regret minimization).

BelMan addresses these limitations by shifting the problem into the domain of Information Geometry. Instead of treating reward parameters in isolation, BelMan treats the joint distribution of rewards and beliefs for each arm as a point on a "statistical manifold," providing a robust geometric framework for decision-making.

The BelMan Framework

The Belief-Reward Manifold

The core innovation of BelMan is the Belief-Reward Manifold, a geometric space where every point represents a possible state of knowledge regarding an arm's reward distribution. This allows the algorithm to use the "distance" between distributions—specifically KL-divergence—to guide its choices, which is often more robust than simple comparisons of mean values.

Pseudobelief and Focal Distributions

To manage collective knowledge, the algorithm maintains a Pseudobelief-Reward. This acts as the geometric barycenter (mean) of all arms on the manifold, providing a succinct summary of the agent's total information. To induce exploitation, the authors introduce a Focal Distribution, which biases the pseudobelief toward higher rewards. This bias is controlled by a time-dependent parameter called exposure ($\tau$), allowing the agent to transition from exploration to exploitation dynamically.

Alternating Projections

BelMan operates through a two-step process of alternating projections:

  1. I-projection: The agent selects the arm whose distribution is closest to the biased pseudobelief in terms of KL-divergence.
  2. rI-projection (Reverse I-projection): Upon receiving a reward, the agent updates the specific arm's belief via Bayes' rule and then updates the global pseudobelief to incorporate this new information.

Experimental Evaluation

The authors evaluated BelMan against several baselines, including UCB, KL-UCB, Thompson Sampling, and the Gittins index, across various benchmarks:

  • Bernoulli Bandits: Tested in both 2-arm and 20-arm configurations with discrete rewards.
  • Exponential Bandits: Evaluated using 5-arm setups with continuous rewards to test generalization beyond discrete data.
  • Queueing Bandits: A real-world-inspired application involving job scheduling in a multi-server system with unknown service rates.

Key Results and Insights

Theoretical and Empirical Performance

BelMan is proven to be asymptotically optimal, meaning its regret—the difference between its performance and an ideal strategy—grows sublinearly over time. In empirical trials, BelMan consistently showed lower regret and fewer suboptimal draws than KL-UCB and Thompson Sampling, particularly in the 20-arm Bernoulli and 5-arm Exponential tests.

Stability in Dynamic Systems

In the queueing bandit task, BelMan demonstrated superior stability. While traditional exploration strategies can sometimes "over-explore" inefficient servers—leading to exploding queue lengths—BelMan’s geometric approach effectively dampens this instability, minimizing total queue lengths more effectively than Q-UCB or Q-Thompson Sampling.

Tunability

The geometric framework provides a unique advantage in its flexibility. By adjusting the exposure parameter $\tau$, BelMan can be tuned to prioritize pure exploration (mapping the reward landscape) or aggressive exploitation (maximizing immediate returns) within the same mathematical structure.

Conclusion and Future Work

BelMan offers a powerful unification of Bayesian bandits through the lens of information geometry. While currently optimized for reward distributions within the exponential family (e.g., Gaussian, Bernoulli, Poisson), the framework provides a foundation for several future research directions:

  • Dependent Arms: Extending the manifold to account for correlations between different arms.
  • Non-parametric Distributions: Moving beyond the exponential family to handle more complex, real-world data distributions.
  • Continuous Arm Spaces: Adapting the geometric projection method for scenarios with an infinite number of possible actions.

Summary updated

Abstract

We propose a generic, Bayesian, information geometric approach to the exploration--exploitation trade-off in multi-armed bandit problems. Our approach, BelMan, uniformly supports pure exploration, exploration--exploitation, and two-phase bandit problems. The knowledge on bandit arms and their reward distributions is summarised by the barycentre of the joint distributions of beliefs and rewards of the arms, the \emph{pseudobelief-reward}, within the beliefs-rewards manifold. BelMan alternates \emph{information projection} and \emph{reverse information projection}, i.e., projection of the pseudobelief-reward onto beliefs-rewards to choose the arm to play, and projection of the resulting beliefs-rewards onto the pseudobelief-reward. It introduces a mechanism that infuses an exploitative bias by means of a \emph{focal distribution}, i.e., a reward distribution that gradually concentrates on higher rewards. Comparative performance evaluation with state-of-the-art algorithms shows that BelMan is not only competitive but can also outperform other approaches in specific setups, for instance involving many arms and continuous rewards.
BibTeX
@misc{basu2018belman,
  author = {Debabrota Basu and Pierre Senellart and Stéphane Bressan},
  title = {{BelMan: Bayesian Bandits on the Belief-Reward Manifold}},
  year = {2018},
  eprint = {1805.01627},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1805.01627},
}
Figure