Graphical Models for Bandit Problems

Kareem Amin, Michael J. Kearns, Umar Syed

Abstract

We introduce a rich class of graphical models for multi-armed bandit problems that permit both the state or context space and the action space to be very large, yet succinctly specify the payoffs for any context-action pair. Our main result is an algorithm for such models whose regret is bounded by the number of parameters and whose running time depends only on the treewidth of the graph substructure induced by the action space.

Introduction

In the standard Multi-Armed Bandit (MAB) setting, an agent must repeatedly choose an action to maximize a cumulative reward. In "contextual" bandits, this reward also depends on an observed state or context. As the number of variables defining these actions and contexts increases, the problem suffers from the "curse of dimensionality"—the number of possible combinations explodes exponentially.

Traditional approaches often assume a small number of actions or a simple linear relationship between context and reward. This paper introduces a framework for MAB problems where both context and action spaces are exponentially large, but the payoff function decomposes according to a structured graphical model. By exploiting this structure, we can achieve efficient learning and decision-making.

The Graphical Model Framework

The core idea is to represent the payoff function as a sum of local potential functions over a graph. This allows for complex global relationships to be modeled as a collection of simpler, local interactions. For example, in a sponsored search application, the payoff (such as click-through rate) might depend on a query (context) and an ad (action). While the total number of query-ad pairs is astronomical, the payoff may only depend on specific matches, such as whether the "destination city" in the query aligns with the "hotel location" in the ad.

Figure 1: An example graphical model for a travel-related bandit problem. Context variables (x) and action variables (y) interact to determine the total payoff.

As illustrated in Figure 1, the dependencies between context variables ($x$) and action variables ($y$) are explicitly mapped. By assuming this graphical structure is known, the problem of learning the payoff for every possible combination is reduced to learning the parameters of the local potential functions.

Methodology: The GraphicalBandits Algorithm

The authors propose the GraphicalBandits algorithm, which decomposes the bandit problem into two interacting subroutines:

1. BestAct (Optimization)

This is the exploitation engine. Given the current estimates of the payoff function, BestAct identifies the optimal joint action. It utilizes distributed dynamic programming techniques, similar to the Viterbi algorithm or MAP inference in Markov Random Fields (MRFs). The computational efficiency of this step is determined by the treewidth of the action subgraph—a metric indicating how "tree-like" the dependencies between action variables are. If the treewidth is low, the optimization remains tractable even in exponential action spaces.

2. PayEst (Estimation)

This is the exploration engine. It treats the payoff function as a linear combination of local potentials and employs a "Knows What It Knows" (KWIK) linear regression framework. If the algorithm is confident about the payoff for a given context-action pair, it provides an estimate; otherwise, it outputs a symbol ($\perp$) signaling the need for exploration. This forces the agent to select actions that yield the most informative data about the underlying parameters.

Key Insights

  • Decoupling Context and Action Complexity: A significant theoretical contribution is the observation that the computational bottleneck resides solely in the action variables. Because context is observed at the start of each round, dependencies between context variables can be arbitrarily complex without impacting the per-round runtime.
  • Learning Local Potentials from Global Signals: Unlike standard graphical model inference where local nodes might be observed, here only the total sum (the global payoff) is visible. The algorithm successfully reconstructs the local "potential functions" using only this aggregate signal.
  • Treewidth as the Fundamental Complexity Metric: The paper formalizes that the difficulty of a bandit problem is not the raw number of actions, but the interconnectivity of the choices available to the agent.

Results and Performance

The GraphicalBandits algorithm achieves a regret bound of $O(T^{2/3})$, where $T$ is the number of rounds. While this is slightly higher than the $O(\sqrt{T})$ typical of simpler bandit problems, it is a "no-regret" result, meaning the average regret approaches zero as $T$ increases.

Furthermore, the total regret is bounded by the number of parameters in the graphical model (the "rank" of the system), which is significantly smaller than the total number of actions or contexts. In terms of complexity, if the treewidth of the action subgraph is constant, the algorithm runs in polynomial time per round.

Limitations and Future Work

The primary limitation of this framework is the assumption that the graphical structure is known a priori. In practice, identifying which variables interact is a difficult task, and structure learning is often NP-hard. Additionally, the $O(T^{2/3})$ regret rate leaves room for improvement; it remains an open question whether a polynomial-time algorithm can achieve the optimal $O(\sqrt{T})$ bound. Finally, the current model is designed for discrete variables; extending these graphical bandit models to continuous action and context spaces represents a promising direction for future research.

Summary updated

Abstract

We introduce a rich class of graphical models for multi-armed bandit problems that permit both the state or context space and the action space to be very large, yet succinctly specify the payoffs for any context-action pair. Our main result is an algorithm for such models whose regret is bounded by the number of parameters and whose running time depends only on the treewidth of the graph substructure induced by the action space.
BibTeX
@inproceedings{amin2011graphical,
  author = {Kareem Amin and Michael J. Kearns and Umar Syed},
  title = {{Graphical Models for Bandit Problems}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2011},
  url = {https://openreview.net/forum?id=RWvy4y7U_B},
}
Figure