Graphical Models for Bandit Problems

Kareem Amin, Michael J. Kearns, Umar Syed

TL;DR

This paper introduces a framework for Multi-Armed Bandit (MAB) problems where both the context and action spaces are exponentially large. By assuming the payoff function decomposes according to a graphical model, the authors provide a "no-regret" algorithm whose computational complexity scales with the treewidth of the action space rather than the total number of possible actions.

What Problem Does This Paper Address?

In a standard Multi-Armed Bandit problem, an agent chooses an action and receives a reward. In "contextual" bandits, the reward also depends on external state (the context). The "curse of dimensionality" hits hard here: if your actions and contexts are defined by multiple variables (e.g., choosing 10 different settings for an ad campaign), the number of possible combinations explodes exponentially.

Existing algorithms usually require the number of actions to be small or assume a simple linear relationship. This paper tackles settings where the relationship is complex but structured. For example, in sponsored search, the payoff (click-through rate) depends on a query (context) and an ad (action). While there are billions of query-ad pairs, the payoff might only depend on local interactions—like how well the "destination city" in the query matches the "hotel location" in the ad.

Methods

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

  1. BestAct (Optimization): This is the "exploitation" engine. Given an estimate of the payoff function, it finds the best joint action. It uses distributed dynamic programming (similar to the Viterbi algorithm or MAP inference in MRFs). Crucially, its runtime is efficient if the "action subgraph" has low treewidth—a measure of how "tree-like" the graph of variable dependencies is.
  2. PayEst (Estimation): This is the "exploration" engine. It treats the payoff function as a linear combination of local potential functions. It uses a "Knows What It Knows" (KWIK) linear regression framework. If the algorithm is confident about the payoff for a context-action pair, it provides an estimate; if not, it signals a need for exploration (outputting $\perp$), forcing the agent to take an action that provides new information.

The "secret sauce" is the linearization trick: even though the payoff function is a sum of arbitrary non-linear functions over subsets of variables, it can be represented as a linear product in a high-dimensional (but still manageable) vector space defined by the graph's parameters.

Datasets

Not discussed in the paper. This is a theoretical paper focused on providing mathematical proofs for regret bounds and computational complexity. No empirical experiments on real-world or synthetic datasets were conducted.

Key Insights and Ideas

  • Decoupling Context and Action Complexity: A major "aha moment" is that the computational bottleneck is only the action variables. The dependencies between context variables can be arbitrarily complex without hurting the algorithm's runtime, because the context is observed for free at the start of each round.
  • Global Payoffs from Local Structures: Unlike standard graphical model inference where you might observe local nodes, here you only see the total sum (the global payoff). The algorithm successfully learns the underlying local "potential functions" using only this global signal.
  • Linearity is Hidden in the Graph: By recognizing that any decomposed payoff function is technically a linear function of its parameters, the authors bridge the gap between complex graphical models and well-understood linear bandit theory.
  • Treewidth as the Complexity Metric: The paper formalizes that the difficulty of a bandit problem isn't the number of actions, but the interconnectivity of the choices you have to make.

Key Results

  • Regret Bounds: The algorithm achieves a regret of $O(T^{2/3})$, where $T$ is the number of rounds. While this is higher than the $O(\sqrt{T})$ typical of simpler bandit problems, it is "no-regret," meaning the average regret goes to zero as $T$ grows.
  • Sublinear Parameter Dependence: The total regret is bounded by the number of parameters in the graphical model (the "rank" of the system), which is much smaller than the total number of actions or contexts.
  • Computational Efficiency: If the treewidth of the action subgraph is constant, the algorithm runs in polynomial time per round, even if the action space is exponential.

Limitations and Future Work

  • Known Structure: The biggest limitation is that the algorithm requires the graphical structure to be known in advance. In many real-world scenarios, we don't know which variables interact; we have to learn the graph itself. The authors note that "structure learning" is often NP-hard and suggest this as a difficult but necessary next step.
  • Regret Rate: The $O(T^{2/3})$ regret is slightly worse than the $O(T^{1/2})$ achieved by some computationally inefficient algorithms. The authors leave it as an open question whether a polynomial-time algorithm can reach the $O(\sqrt{T})$ bound.
  • Discrete Variables: The current model assumes discrete variables for actions and contexts. Extending this to continuous spaces would require different functional approximations.

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},
}

Loading related content...

Figure