TL;DR
This paper tackles the Thresholding Bandit Problem (TBP), where the goal is to identify arms with means above a certain threshold. The authors introduce a "problem-dependent" perspective for structured TBPs (monotone and concave arm means), showing that the optimal error probability scales with the minimum gap to the threshold, surprisingly independent of the total number of arms. They also provide matching upper and lower bounds and algorithms for these structured settings.
What Problem Does This Paper Address?
The Thresholding Bandit Problem (TBP) is a classic scenario in reinforcement learning where an agent must sequentially sample from a set of "arms" (each with an unknown mean and distribution) to identify which arms have means exceeding a predefined threshold. While the "vanilla" TBP (without any structure on arm means) is well-studied, this paper focuses on the structured TBP, specifically when the arm means exhibit a monotone (increasing) or concave pattern.
The key challenge addressed is understanding how these structural constraints influence the optimal error probability in the problem-dependent regime. This regime considers the difficulty of a specific instance of the problem, characterized by the "gaps" (the difference between an arm's mean and the threshold). The authors aim to derive tight bounds on this error probability and develop algorithms that achieve these bounds, particularly in a fixed-budget setting. They want to understand if and how the number of arms ($K$) affects the problem's difficulty in these structured settings.
Methods
The paper introduces a "problem-dependent" view, focusing on the minimum gap ($\Delta_{min}$) between arm means and the threshold. For structured TBPs (monotone and concave), they derive matching upper and lower bounds on the probability of error.
- Monotone TBP (MTBP): The authors propose a parameter-free algorithm, PD-MTB, which uses a binary tree structure with an "infinite extension" to handle the monotone constraint. This algorithm performs a binary search with corrections, allowing it to backtrack if estimates are unreliable.
- Concave TBP (CTBP): For this setting, they develop the PD-CTB algorithm, which leverages a "Grad-Explore" subroutine. Grad-Explore uses estimated gradients to navigate a binary tree, aiming to identify arms above the threshold. Once an arm is identified, the problem is split into two simpler monotone subproblems, solved by PD-MTB and its non-increasing variant.
Both algorithms are designed to be parameter-free, adapting to the problem's specific gaps and the sub-Gaussian noise parameter ($\sigma^2$).
Datasets
Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic design, with experimental validation presented in Section E.
Key Insights and Ideas
- Problem-Dependent Difficulty: The core insight is that for structured TBPs (monotone and concave), the problem's difficulty in the problem-dependent regime is surprisingly determined by the minimum gap ($\Delta_{min}$) to the threshold, not the total number of arms ($K$). This is a significant departure from the unstructured case.
- "One-Armed Bandit" Equivalence: For large budgets ($T$), the optimal error probability in both the monotone and concave structured settings matches that of a single-arm bandit problem where the goal is to determine if that single arm is above or below the threshold, with a gap of $\Delta_{min}$. This suggests that the structure allows for efficient exploration, effectively reducing the problem to its hardest part.
- Binary Search with Corrections: The proposed algorithms (PD-MTB and PD-CTB) rely on binary search principles adapted to the bandit setting. The "corrections" or backtracking mechanisms are crucial for handling the uncertainty in arm mean estimates, especially when means are close to the threshold.
- Parameter-Free Algorithms: The developed algorithms are parameter-free, meaning they don't require prior knowledge of $\Delta_{min}$ or $\sigma^2$, making them more practical.
Key Results
- Matching Bounds: For both MTBP and CTBP in the problem-dependent regime, the authors provide upper and lower bounds on the probability of error that match up to universal constants in the exponential. These bounds are of the order $exp(-\frac{T \Delta_{min}^2}{\sigma^2})$.
- Algorithm Performance: The proposed algorithms, PD-MTB and PD-CTB, are shown to achieve these optimal bounds.
- Experimental Validation: Experiments show that PD-MTB outperforms naive and uniform algorithms, especially in settings where the minimum gap is small. The results suggest that the dependency on $K$ diminishes for larger budgets, aligning with theoretical predictions.
Limitations and Future Work
- Experimental Limitations: The authors note that achieving extremely low probabilities of error (as predicted by theory for large $T$) is difficult to detect accurately with Monte Carlo simulations due to the required number of samples.
- Unimodal Constraint: The paper suggests exploring the unimodal constraint for TBP in the problem-dependent regime, conjecturing that it might also lead to a rate dependent on $\Delta_{min}$ and potentially the number of arms above the threshold.
- Problem-Independent Optimality: While PD-MTB is optimal in the problem-dependent sense, the paper raises the question of whether it can also be optimal in the problem-independent sense (for simple regret), suggesting this as a direction for future work.
- Generalization of PD-CTB: The optimality of the CTB algorithm (from prior work) in the problem-dependent regime is conjectured but not formally proven in this paper.
Summary updated