Value Directed Exploration in Multi-Armed Bandits with Structured Priors

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

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.

Introduction

The Multi-Armed Bandit (MAB) problem represents the classic "explore vs. exploit" dilemma: should an agent stick with the best-performing option found so far, or try something new that might be even better? While algorithms like Upper Confidence Bound (UCB) and Thompson Sampling have strong theoretical guarantees, they are often "blind" to external structure. For instance, when testing discount levels, a human knows that a 15% discount will likely lead to more sales than a 5% one. Standard algorithms treat these as independent options, wasting "pulls" to learn relationships that are already known.

This paper introduces ELSV (Exploration via Linearly Separable Value Functions), a framework that bridges the gap between simple index-based algorithms and complex online planning. By decomposing the value of exploration into additive components for each arm, the authors create a lookahead search that can easily incorporate "structured priors" to significantly outperform standard methods.

Methodology: The ELSV Framework

The core innovation of ELSV is an n-step lookahead search (online planning) guided by a novel type of value function. The challenge with optimal solutions in this space is that the state space explodes as arms are added. ELSV addresses this through three key mechanisms:

  1. Linearly Separable Value Functions: The algorithm computes a value function $v(s)$ as the sum of independent values for each arm: $v(s) = \sum \upsilon^i(s^i)$. This decomposition allows the algorithm to scale efficiently to many arms.
  2. Index-to-Value Mapping: The authors provide a method to take existing index policies (like UCB or the Gittins Index) and back-calculate the implicit value function they use, allowing ELSV to inherit their proven exploration benefits.
  3. Constrained Lookahead: When prior knowledge is available (e.g., monotonic conversion rates), ELSV uses rejection sampling during its lookahead search. It simulates future outcomes but discards scenarios that violate known constraints, steering exploration toward more plausible, high-value states.
A decision tree illustrating the n-step lookahead process for a 2-arm bandit, showing state transitions based on rewards.

Experimental Setup

The paper evaluates ELSV using simulated environments:

  • Standard Bernoulli Bandits: A baseline where arms provide binary rewards based on hidden probabilities.
  • Constrained Bernoulli Bandits: A more complex scenario simulating personalized discount offers. Here, rewards are constrained such that higher discounts must result in equal or higher conversion probabilities than lower ones, testing the algorithm's ability to leverage domain knowledge.

Insights and Key Results

A significant insight from the paper involves the "shape" of exploration. By visualizing value functions, the authors found that the Gittins Index is "curious"—its value increases for both very high and very low success probabilities. Learning that an arm is "bad" is valuable because it allows the agent to stop wasting resources on it.

Contour plots of the Gittins Index value function at different time horizons (t=10 and t=200), showing how exploration incentives evolve.

Performance Highlights

  • Theoretical Guarantee: ELSV using a UCB-derived value function maintains a sub-linear regret bound, ensuring it eventually identifies the optimal arm.
  • Superiority with Constraints: In "Constrained Bernoulli" tests, ELSV-Gittins significantly outperformed state-of-the-art methods, including Thompson Sampling and the standard Gittins Index, by effectively utilizing the structured priors.
  • The Role of Structure: Surprisingly, in plain bandit problems, increasing lookahead depth didn't always improve performance. The real power of lookahead search is providing a "hook" for prior knowledge, allowing the agent to simulate how beliefs change under specific constraints.

Limitations and Future Work

While ELSV is efficient, the state space still grows exponentially with lookahead depth. The authors suggest that more focused search methods, such as Monte Carlo Tree Search, might be necessary for deeper horizons. Additionally, extending this approach to more complex reward distributions (e.g., Gaussian) and contextual bandits—where the best arm depends on user data—remains a promising direction for future research.

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