A PTAS for the Bayesian Thresholding Bandit Problem

Yue Qin, Jian Peng, Yuan ZhouAISTATS 2020

Abstract

The Bayesian Thresholding Bandit Problem (BTBP) involves identifying which arms in a multi-armed bandit setup have a mean reward exceeding a specific threshold, given a fixed query budget and prior beliefs. While finding an optimal policy is computationally intractable (PSPACE-hard), this paper introduces the first Polynomial Time Approximation Scheme (PTAS) for the problem. By utilizing bounded query policies and a novel "pretended observation" simulation technique, the authors demonstrate that an agent can achieve performance within an $\epsilon$-margin of the optimal policy in polynomial time.

1. Introduction

In sequential decision-making, the Thresholding Bandit Problem requires an agent to classify arms as being above or below a predefined mean value (typically 0.5). In the Bayesian setting, the agent begins with prior distributions for each arm—often Beta distributions—and must decide which arms to sample to maximize the expected number of correct classifications within a budget of $Q$ queries.

Due to the "curse of dimensionality," the state space for an optimal policy grows exponentially with the number of arms and the budget, making exact solutions impossible for practical applications. This research addresses this gap by asking whether a policy exists that is nearly as effective as the optimal one but remains computationally feasible. The authors answer in the affirmative by providing a Polynomial Time Approximation Scheme (PTAS).

2. Methodology

The authors bridge the gap between theoretical optimality and computational tractability through several key technical maneuvers designed to reduce the search space and simplify policy execution.

2.1 Bounded Query Policies ($\epsilon^{-2}$-BQP)

The search space is first restricted to policies that do not query any single arm an excessive number of times. The authors prove that these bounded policies can still approximate the global optimum effectively, as the marginal utility of querying a single arm diminishes after a certain point.

2.2 Simulated Queries and Pretended Observations

A central innovation of the paper is the use of "pretended observations." The authors construct a policy $g$ that simulates the behavior of a more complex, computationally expensive policy $\tilde{f}$. For a subset of arms, $g$ performs real queries; for others, it "pretends" to query by sampling from the prior distribution. This coupling technique allows the agent to maintain the logical structure of a complex policy while operating within a reduced real-world query budget.

2.3 Concentration and Error Bounds

To ensure the reliability of these simulations, the authors employ Hoeffding’s and Chernoff’s inequalities alongside Stirling’s approximation. These tools bound the probability that simulated runs deviate significantly from actual rewards. They demonstrate that the error in identifying an arm decays exponentially once the difference between observed successes ($a_i$) and failures ($b_i$) exceeds a threshold proportional to the square root of the total queries.

2.4 Batching

The framework converts query-by-query policies into batched policies. By making multiple queries to an arm simultaneously, the authors further reduce the decision-making complexity without incurring a significant loss in classification accuracy.

3. Theoretical Results

The paper provides a rigorous mathematical proof for the existence of the PTAS. The primary result shows that for any $\epsilon > 0$, there exists a policy $g$ such that its value satisfies:

$$val(g) \geq val(\tilde{f}) - 3\epsilon$$

where $\tilde{f}$ is the optimal policy.

3.1 Quantitative Thresholds

The authors establish specific thresholds for error reduction. For instance, when the gap between successes and failures $|a_i - b_i| > \sqrt{a_i + b_i} \cdot 3 \ln M$, the probability of misclassification drops below $\frac{1}{2\sqrt{M}}$.

3.2 Budget Robustness

Through Lemma 19, the authors prove that the approximation scheme is robust to budget constraints. If the total budget $Q$ is sufficiently large—specifically $Q \geq 1200\epsilon^{-4} \ln^3 \epsilon^{-1}$—the probability that the approximate policy exceeds the budget and fails to provide a classification is at most $\epsilon$.

4. Discussion and Limitations

While the paper marks a significant theoretical milestone, it notes several limitations regarding practical implementation. The constants involved in the polynomial bounds (e.g., $1200\epsilon^{-4}$) are theoretically polynomial but practically very large, meaning that for very high precision (small $\epsilon$), the computation time may still be substantial.

Furthermore, the results are currently confined to the Bayesian setting with known priors. Future work is required to extend these approximation schemes to frequentist settings where priors are unknown, or to scenarios involving dynamic thresholds and multi-objective identification tasks.

5. Conclusion

By proving the existence of a PTAS for the Bayesian Thresholding Bandit Problem, this work provides a roadmap for moving from PSPACE-hard optimal policies to tractable, near-optimal approximations. The introduction of "pretended observations" offers a powerful tool for policy simulation that may find applications in other areas of sequential resource allocation.

Summary updated

BibTeX
@inproceedings{qin2020ptas,
  author = {Yue Qin and Jian Peng and Yuan Zhou},
  title = {{A PTAS for the Bayesian Thresholding Bandit Problem}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
}
Figure