TL;DR
This paper tackles the challenge of identifying the best arm in a "semiparametric bandit" setting, where rewards have a linear component influenced by arm features, plus an unpredictable baseline shift. The authors introduce a novel algorithm that achieves near-optimal performance by adapting techniques from linear bandits to this more complex scenario, providing a theoretical guarantee and demonstrating practical gains on real-world data.
What Problem Does This Paper Address?
In the realm of multi-armed bandits, the goal is often to find the "best arm" – the one that yields the highest reward. While standard bandit problems assume rewards are directly related to arm features (linear bandits), many real-world scenarios involve an additional, unmodeled baseline. Think of a medical trial where a patient's inherent health status (the baseline) affects their response to a treatment, independent of the treatment's specific effect. This is the "semiparametric bandit" problem. Identifying the best arm in this setting is harder because the baseline shift can obscure the true treatment effect. Existing methods for linear bandits don't directly apply, and the optimal sample complexity (how many pulls are needed to be confident) for this semiparametric setting was an open question. This paper aims to close that gap by providing both a theoretical lower bound on the required samples and an algorithm that nearly achieves it.
Methods
The core of the paper's contribution lies in two main areas:
- Theoretical Lower Bound: The authors establish a fundamental limit on how many samples are needed for fixed-confidence best arm identification in semiparametric bandits. Crucially, this lower bound is shown to be equivalent to the complexity of a shifted linear bandit problem, meaning the problem's difficulty is dictated by how well we can distinguish arms based on their linear effects after accounting for a specific baseline.
- Novel Algorithm (SP-BAI): They propose a phase-elimination algorithm, a common strategy in bandit problems. The key innovation is a new "$\mathcal{X}\mathcal{Y}$-design" tailored for orthogonalized regression. Orthogonalized regression is a technique used to estimate the linear effect while mitigating the influence of the unknown baseline. The $\mathcal{X}\mathcal{Y}$-design is designed to efficiently control the variance of pairwise comparisons between arms, which is critical for identification. This design is then integrated into a phase-elimination framework, with a mixture policy that balances the need for efficient contrast estimation with stability against the baseline.
Datasets
- Synthetic Datasets: The authors generate synthetic data using two families of instances: a "small-gap instance" and a "uniform-feature instance." These are used to test the algorithm's performance under controlled conditions, particularly for evaluating its stopping time and error probability.
- Jester Dataset: This real-world dataset, consisting of user ratings for jokes, is used to demonstrate the practical utility of the semiparametric model and the proposed algorithm. The dataset exhibits significant user-specific baseline variation, making it a suitable testbed for methods that account for such shifts.
Key Insights and Ideas
- The "Shifted Linear Bandit" Benchmark: The most significant theoretical insight is that the instance-dependent complexity of semiparametric BAI is fundamentally governed by the complexity of a shifted linear bandit problem. This provides a clear target for algorithm design and a way to understand the problem's inherent difficulty.
- Orthogonalized Regression is Key: The paper reinforces the importance of orthogonalized regression for semiparametric bandits. It's not just about estimating the linear parameters but doing so in a way that is robust to arbitrary baseline shifts.
- $\mathcal{X}\mathcal{Y}$-Design for Orthogonalized Regression: The development of a new $\mathcal{X}\mathcal{Y}$-design specifically for orthogonalized regression is a major technical contribution. This design is crucial for achieving near-optimality by efficiently controlling the variance of arm comparisons.
- Phase Elimination with a Twist: The algorithm cleverly adapts the standard phase-elimination approach by incorporating the new $\mathcal{X}\mathcal{Y}$-design. This allows it to efficiently narrow down the set of candidate arms while still being robust to the baseline.
Key Results
- Near-Optimal Sample Complexity: The proposed algorithm (SP-BAI) achieves a high-probability sample complexity upper bound that is nearly optimal, matching the theoretical lower bound up to logarithmic factors and an additive $d^2$ term (where $d$ is the feature dimension). This means the algorithm is as sample-efficient as theoretically possible for this problem.
- Empirical Gains: Experiments on synthetic data and the Jester dataset show that SP-BAI significantly outperforms prior semiparametric methods (like SBE) in terms of average stopping time while maintaining high success rates. For instance, on the Jester dataset, SP-BAI achieved a 97% success rate with about 4.3 times fewer samples than SBE.
- Robustness to Baseline: The Jester dataset experiments also highlight the importance of accounting for the baseline shift. A simple ranking task showed that methods correcting for the baseline (like DEO) performed better than naive approaches.
Limitations and Future Work
- Additive $d^2$ Term: While the algorithm is nearly optimal, the upper bound includes an additive $d^2$ term. The authors note this term arises from stability requirements for orthogonalized regression and is independent of instance-specific gaps. Future work might explore ways to reduce or eliminate this term.
- Fixed-Confidence vs. Fixed-Budget: The current work focuses on the fixed-confidence setting. The authors suggest that extending these results to the fixed-budget setting is a natural direction for future research.
- Top-m Identification: Another avenue for future work is extending the framework to the "top-m identification" problem, where the goal is to identify the $m$ best arms, rather than just the single best arm.
Summary updated