Value Directed Exploration in Multi-Armed Bandits with Structured Priors

Bence Cserna, Marek Petrik, Reazul Hasan Russel, Wheeler Ruml

Introduction

The Multi-Armed Bandit (MAB) problem represents the fundamental exploration-exploitation trade-off. While standard algorithms like Upper Confidence Bound (UCB) and Thompson Sampling are theoretically robust, they often fail to leverage structured priors—domain knowledge about the relationships between different options. For instance, in pricing experiments, one can reasonably assume that a higher discount will yield a higher conversion rate than a lower one. Standard independent-arm models discard this information.

This paper introduces ELSV (Exploration via Linearly Separable Value Functions), a framework that bridges the gap between simple index policies and complex lookahead planning. By transforming bandit indices into value functions, ELSV enables efficient lookahead search that incorporates complex constraints, significantly improving short-term performance.

Methodology: From Indices to Value Functions

The core of ELSV is the decomposition of a global value function into linearly separable components.

1. Index-to-Value Translation

The authors demonstrate that the "exploration bonus" in policies like UCB or the Gittins Index can be mapped to a value function. An arm's value is defined as the sum of its expected immediate reward and the expected increase in the value of the knowledge state (information gain).

2. Lookahead Search and Decomposition

Instead of navigating an exponentially growing state space, ELSV decomposes the value function into a sum of individual functions for each arm. This allows for a lookahead search of limited depth. When the search reaches its horizon, the ELSV value function estimates the remaining reward.

Decision tree illustrating the lookahead search and state updates for multi-armed bandits.

3. Incorporating Constraints

To handle structured priors (e.g., $\mu_1 \ge \mu_2$), ELSV employs rejection sampling during lookahead. By only considering future scenarios that satisfy known constraints, the agent can update its knowledge of multiple arms from a single observation, effectively "pruning" suboptimal paths.

Evaluation and Results

The framework was evaluated using Bernoulli bandit simulations, including a "Constrained Bernoulli Bandit" scenario designed to mimic personalized discount offers.

Key Performance Metrics

The primary metric for evaluation is Bayesian Regret. The results indicate that while lookahead depth provides marginal gains in simple independent settings, it is transformative when arms are correlated.

Bayesian regret comparison across different lookahead depths and index policies.

In constrained tasks, ELSV-Gittins significantly outperformed standard benchmarks like Bayes-UCB and Thompson Sampling. By leveraging the structured prior, the agent quickly identified and discarded arms that were logically inferior based on the outcomes of related arms.

Insights and Future Directions

A key insight from this work is that the exploration bonus is essentially a proxy for value change. While standard indices are highly optimized for independent arms, their performance plateaus. The "killer app" for lookahead search is the presence of structure; it allows the agent to reason that failure in one arm implies failure in another, more restrictive arm.

Limitations: - Computational Complexity: Although $O(t^3)$ is efficient, deeper lookahead remains expensive. - Heuristics: Rejection sampling for constraints currently lacks formal regret bounds. - Generalization: Future work will explore extending ELSV to contextual bandits and more complex reward distributions beyond the Bernoulli case.

Summary updated

Abstract

Multi-armed bandits are a quintessential machine learning problem requiring the balancing of exploration and exploitation. While there has been progress in developing algorithms with strong theoretical guarantees, there has been less focus on practical near-optimal finite-time performance. In this paper, we propose an algorithm for Bayesian multi-armed bandits that utilizes value-function-driven online planning techniques. Building on previous work on UCB and Gittins index, we introduce linearly-separable value functions that take both the expected return and the benefit of exploration into consideration to perform n-step lookahead. The algorithm enjoys a sub-linear performance guarantee and we present simulation results that confirm its strength in problems with structured priors. The simplicity and generality of our approach makes it a strong candidate for analyzing more complex multi-armed bandit problems.
BibTeX
@inproceedings{cserna2017value,
  author = {Bence Cserna and Marek Petrik and Reazul Hasan Russel and Wheeler Ruml},
  title = {{Value Directed Exploration in Multi-Armed Bandits with Structured Priors}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2017},
  url = {https://openreview.net/forum?id=8uNsrGoiEt},
}
Figure