Minimax Lower Bounds for the Two-Armed Bandit Problem

Sanjeev R. Kulkarni, Gábor LugosiSSRN 1997 · DOI

TL;DR

This paper establishes finite-sample minimax lower bounds for the classic two-armed bandit problem, providing a tighter bound than previously known asymptotic results. Crucially, it demonstrates that for many configurations, the optimal regret is surprisingly close to that of random guessing, implying that sophisticated strategies offer little advantage in these scenarios.

What Problem Does This Paper Address?

The two-armed bandit problem is a fundamental challenge in sequential decision-making. Imagine you have two slot machines (arms), each with a different, unknown probability of paying out. At each step, you must choose which arm to pull, aiming to maximize your total winnings over a fixed number of pulls. The "regret" is the difference between the total reward you achieve and the reward you would have gotten if you had known the best arm from the start and always pulled it.

While asymptotic results (what happens as the number of pulls goes to infinity) have shown that the optimal regret grows logarithmically with the number of pulls (specifically, proportional to $\log n$), this paper tackles the question of finite-sample bounds. They ask: what is the guaranteed worst-case regret for any strategy, given a specific number of pulls $n$? Furthermore, they investigate the minimax regret, which is the maximum regret achievable by any strategy, minimized over all possible configurations of the two arms.

Methods

The authors derive their minimax lower bounds using a combination of information-theoretic tools and a clever change-of-measure lemma.

  • Information Divergence (Kullback-Leibler Divergence): This measures how one probability distribution differs from another. It's a key component in quantifying the difficulty of distinguishing between the two arms.
  • Variance-like Quantity (V): This term, related to the information divergence, captures another aspect of the difference between the arm distributions.
  • Change-of-Measure Lemma: This is the core technical contribution. It's a generalization of a lemma by Lai and Robbins and allows them to relate probabilities under different configurations of the bandit problem. Essentially, it provides a way to bound the probability of certain outcomes under one distribution by using probabilities from another, scaled by a likelihood ratio. This lemma is crucial for proving the lower bounds on regret.
  • Minimax Approach: The paper focuses on finding bounds that hold for any adaptive allocation rule (strategy) and then considers the worst-case scenario across different possible configurations of the bandit problem.

Datasets

Not discussed in the paper. The problem is theoretical and deals with abstract probability distributions rather than specific datasets.

Key Insights and Ideas

  • Finite-Sample Bounds are Crucial: Asymptotic results are useful, but for practical applications, understanding the guaranteed regret for a fixed number of trials is essential. This paper provides that.
  • Random Guessing is Surprisingly Optimal (in a minimax sense): Perhaps the most striking finding is that for many configurations, the minimax regret is very close to $n\Delta/2$, which is the regret achieved by simply flipping a coin at each step. This implies that for these "hard" configurations, no sophisticated strategy can guarantee significantly better performance than random selection.
  • The "Bad" Arm is Pulled Often: The result about random guessing implies that in the worst case, the suboptimal arm is pulled about half the time. This challenges the intuition that clever algorithms can always significantly reduce the number of suboptimal pulls.
  • Information Divergence and Variance Matter: The bounds derived depend on the Kullback-Leibler divergence and a related variance term, highlighting their importance in characterizing the difficulty of the bandit problem.

Key Results

The paper establishes several key lower bounds on the minimax regret.

  • Theorem 1: Provides a finite-sample minimax lower bound that depends on $n$, the difference in means $\Delta$, and parameters related to the information divergence and variance.
  • Corollary 5: Shows that for a specific setup (one arm Gaussian, the other with known mean zero), the minimax regret is at least $(1-\epsilon)n\Delta/2$ for any $\epsilon > 0$ and $n$. This strongly supports the idea that random guessing is near-optimal in such cases.
  • Corollary 6: Extends this to Bernoulli distributions, showing that for any adaptive allocation rule, the supremum of the regret over all such configurations is at least $(1-\epsilon)n\Delta/2$.

Limitations and Future Work

  • Focus on Lower Bounds: The paper primarily establishes lower bounds, meaning it shows what the worst possible regret can be. It doesn't necessarily provide strategies that achieve this regret, although the results suggest that simple strategies might be close to optimal in minimax terms.
  • "Mild Conditions" on Configurations: While the paper mentions "fairly mild conditions" for the random guessing result, the exact nature and generality of these conditions could be further explored.
  • Specific Distributions: While Corollaries 5 and 6 explore specific distribution families (Gaussian, Bernoulli), investigating the minimax regret for a broader range of distributions could be a future direction.
  • Practical Implications: While theoretically significant, translating these minimax bounds into practical algorithm design for situations where "hard" configurations are likely might require further research.

Summary updated

BibTeX
@misc{kulkarni1997minimax,
  author = {Sanjeev R. Kulkarni and Gábor Lugosi},
  title = {{Minimax Lower Bounds for the Two-Armed Bandit Problem}},
  year = {1997},
  doi = {10.2139/ssrn.42920},
  howpublished = {SSRN},
}
Figure