Abstract
We introduce the thresholded linear bandit problem, a novel sequential decision making problem at the interface of structured stochastic multi-armed bandits and learning halfspaces. The set of arms is a subset of $\mathbb{R}^d$, and the reward of an arm $x$ is $\Delta \cdot \mathbb{I}(\langle \theta^*, x \rangle \ge \tau) + \eta$, where $\theta^* \in \mathbb{R}^d$ is an unknown vector, $\tau$ is a known threshold, $\Delta > 0$ is the reward jump, and $\eta$ is zero-mean noise.
Introduction
Standard linear bandit models typically assume a smooth, often linear, relationship between an action's features and its resulting reward. However, many real-world scenarios—such as consumer purchasing decisions or biological responses—exhibit inherent discontinuities. In these cases, a reward "jump" occurs only after a linear combination of features exceeds a specific threshold.
This paper formalizes the thresholded linear bandit problem. Unlike Generalized Linear Bandits (GLBs), which require differentiable and invertible link functions, our model deals with a non-differentiable step function. A critical challenge here is the "cost of quality": higher-utility arms are generally more expensive to pull. The learner must navigate this trade-off, identifying the threshold without incurring excessive regret from high-cost exploration.
The 1D Case: The Leftist Algorithm
In the one-dimensional setting, the problem reduces to finding a threshold $\tau$ on a single feature axis. The authors propose the Leftist algorithm, which employs an epoch-based strategy. It starts by testing "cheaper" (leftmost) arms and only progresses toward more expensive ones if the potential reward jump $\Delta$ justifies the exploration cost.
Once the algorithm identifies the scale of $\Delta$, it utilizes a Noisy Binary Search to pinpoint the threshold's location. This cautious "left-to-right" movement ensures that the algorithm doesn't overspend on expensive arms if a cheaper, zero-reward arm is more regret-efficient.
Multi-Dimensional Generalization
In $d$ dimensions, the threshold becomes a hyperplane. Finding the optimal arm requires identifying the minimum-cost point on this hyperplane, which the authors show is equivalent to a dual formulation of the fractional knapsack problem.
To solve this, the MD-Leftist algorithm uses two key components:
- PAC-MergeSort: A modified sorting algorithm that uses a "PAC comparison oracle" to rank features by their utility-to-cost ratio based on 1-bit noisy feedback.
- MultiGreedy: A greedy strategy that selects coordinates to find the optimal arm once feature rankings are established.
Key Insights and Results
A major contribution of this work is the realization that if the reward jump $\Delta$ is sufficiently small, the optimal strategy is to avoid exploration entirely and commit to a zero-cost arm. The Leftist algorithm is designed to "give up" exploration when the cost-benefit analysis favors the baseline, leading to $O(\sqrt{T})$ worst-case robustness.
Theoretical Bounds
- Problem-Dependent Regret: $O(\log^2 T)$ in favorable settings.
- Worst-Case Regret: $O(\sqrt{T} \log T)$, which is proven to be minimax optimal.
- Dimensionality: Regret scales polynomially with $d$ (e.g., $d^{1.5} \log d$ in the worst case).
Empirical Performance
Synthetic simulations using Monte Carlo trials demonstrate that Leftist consistently outperforms standard baselines like Grid-UCB. While UCB-style algorithms often continue expensive exploration indefinitely, Leftist correctly identifies when to commit to the zero-cost arm, significantly reducing total regret.
Conclusion and Future Work
The thresholded linear bandit framework bridges the gap between bandit optimization and active learning. While the current model assumes a single linear hyperplane and requires certain regularity assumptions on features, it opens the door for more complex models, such as "jump-plus-slope" reward functions or non-linear thresholds, which could further refine economic and behavioral modeling.
Summary updated