Thompson Sampling for Unimodal Bandits

Zhao LiarXiv 2021 · arXiv

TL;DR

This paper introduces TS-UB, a novel Thompson Sampling algorithm for unimodal bandits that significantly improves exploration efficiency by focusing on the neighborhood of the current best-performing arm. This approach leads to asymptotically optimal regret for Bernoulli rewards and near-optimal O(log T) regret for Gaussian rewards, outperforming existing methods in both theoretical guarantees and empirical results.

What Problem Does This Paper Address?

The paper tackles the challenge of unimodal multi-arm bandits (MAB). In a standard MAB problem, an agent must repeatedly choose from a set of "arms" (options), each with an unknown reward distribution, to maximize its cumulative reward over time. The "unimodal" constraint adds a specific structure: there's a path leading to a single optimal arm, and along this path, expected rewards are monotonic. This structure should allow for more efficient learning than in a general MAB.

However, existing algorithms for unimodal bandits, while often asymptotically optimal, can be complex or still suffer from suboptimal exploration. Traditional Thompson Sampling, a popular Bayesian approach, is known for its practical effectiveness but typically explores the entire decision space, which can be inefficient when a unimodal structure is present. The authors aim to bridge this gap by developing a Thompson Sampling variant that explicitly leverages the unimodal structure to achieve faster learning and better regret bounds.

Methods

The core innovation is the TS-UB (Thompson Sampling for Unimodal Bandits) algorithm. Unlike standard Thompson Sampling, which samples from the posterior distribution of all arms to select the next action, TS-UB intelligently restricts its exploration.

Here's how it works:

  1. Maintain Posterior Distributions: Like standard Thompson Sampling, TS-UB maintains posterior distributions (e.g., Beta for Bernoulli rewards, Gaussian for Gaussian rewards) for each arm's expected reward.
  2. Identify the "Leader": At each step, TS-UB identifies the arm with the highest empirical mean estimate as the "leader." This is the arm that has performed best so far based on observed rewards.
  3. Neighborhood Exploration: Instead of sampling from all arms, TS-UB samples from the posterior distributions of arms that are in the neighborhood of the current leader, as defined by the unimodal graph structure. This is the key departure.
  4. Action Selection: The arm with the highest sampled posterior value within this restricted neighborhood is chosen for the next round.

This "local exploration" strategy is designed to exploit the unimodal property, assuming that the optimal arm is likely to be near the current best-performing arm. The authors provide theoretical proofs showing that this approach leads to improved regret bounds compared to standard Thompson Sampling and other existing unimodal bandit algorithms.

Datasets

The paper uses synthetic datasets for evaluation, generated with varying numbers of arms (e.g., 5, 17, 21, 37, 101, 103 arms) and different reward distributions (Bernoulli and Gaussian). These synthetic environments are designed to mimic unimodal structures, including line graphs and loopless graphs.

Additionally, the authors apply their method to a real-world e-commerce application focused on reducing impressions of potentially fraudulent sellers. This task is modeled as a unimodal bandit problem, where the "arms" represent different input percentages for fraud defense, and the "reward" is based on how closely the platform's actual defense percentage matches a target.

Key Insights and Ideas

  • Exploiting Structure is Key: The unimodal structure of the bandit problem is not just a theoretical curiosity; it can be actively exploited to design more efficient algorithms. TS-UB demonstrates that focusing exploration around the current best arm is a powerful strategy.
  • Neighborhood Exploration is Sufficient: For unimodal bandits, exploring the entire arm space is often unnecessary. Restricting exploration to the neighborhood of the current leader significantly speeds up convergence and reduces regret.
  • Bayesian Methods Shine: Thompson Sampling, with its inherent probabilistic approach, proves to be a robust framework for leveraging this structural information, outperforming even optimistic (UCB-style) algorithms in practice.
  • Practical Impact: The application to e-commerce fraud detection highlights the real-world utility of these algorithms, showing significant improvements over manual investigation.

Key Results

The paper presents both theoretical and empirical results:

  • Theoretical Guarantees:
    • For Bernoulli rewards, TS-UB achieves asymptotically optimal regret, matching the theoretical lower bound for unimodal bandits.
  • For Gaussian rewards, TS-UB achieves an expected regret of O(log T), which is significantly better than the O(√KT log K) regret of standard Thompson Sampling for general MABs.
  • Empirical Performance:
    • Figures in the paper consistently show TS-UB outperforming standard Thompson Sampling (TS) in terms of regret across various arm counts and reward distributions.
  • TS-UB also matches or outperforms other state-of-the-art unimodal bandit algorithms like UCB, UCB-MaxN, EXP3.G, OSUB, and UTS.
  • In the e-commerce fraud detection task, TS-UB achieved a significantly smaller gap (difference between actual and target defense percentage) compared to manual investigation, especially for challenging targets.

Limitations and Future Work

  • Graph Structure Assumption: The theoretical analysis relies on a known graph structure defining the unimodal property. In practice, this graph might be unknown or require estimation, which is a potential area for future work.
  • Generalization to Other Structures: While effective for unimodal bandits, the TS-UB approach might need adaptation for other types of structured bandit problems.
  • Real-world Complexity: The e-commerce application showed that performance can be affected by factors like "long-tail" queries, suggesting that more complex real-world scenarios might require further refinements.

The authors suggest future work could explore extending TS-UB to more complex graph structures and investigating its performance in scenarios where the unimodal structure is not perfectly known.

Summary updated

Abstract

In this paper, we propose a Thompson Sampling algorithm for \emph{unimodal} bandits, where the expected reward is unimodal over the partially ordered arms. To exploit the unimodal structure better, at each step, instead of exploration from the entire decision space, our algorithm makes decision according to posterior distribution only in the neighborhood of the arm that has the highest empirical mean estimate. We theoretically prove that, for Bernoulli rewards, the regret of our algorithm reaches the lower bound of unimodal bandits, thus it is asymptotically optimal. For Gaussian rewards, the regret of our algorithm is $\mathcal{O}(\log T)$, which is far better than standard Thompson Sampling algorithms. Extensive experiments demonstrate the effectiveness of the proposed algorithm on both synthetic data sets and the real-world applications.
BibTeX
@misc{li2021thompson,
  author = {Zhao Li},
  title = {{Thompson Sampling for Unimodal Bandits}},
  year = {2021},
  eprint = {2106.08187},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2106.08187},
}

Loading related content...

Figure