Two-Target Algorithms for Infinite-Armed Bandits with Bernoulli Rewards
TL;DR
This paper introduces a novel "two-target" algorithm for the infinite-armed bandit problem, a scenario where an agent must choose from an endless pool of options with unknown success rates. By employing a two-stage filtering process to identify high-performing arms, the authors achieve an optimal regret of $\sqrt{2n}$—effectively cutting the error rate of previous state-of-the-art algorithms by roughly 30% and reaching the theoretical lower bound.
The Challenge of Infinite-Armed Bandits
In a classic "multi-armed bandit" problem, an agent faces a fixed set of slot machines (arms) and must balance exploring new machines with exploiting the one that currently yields the best payout. However, in modern applications like online advertising or content recommendation (e.g., Netflix or YouTube), the catalogue of options is so vast it is practically infinite. It is impossible to try every arm even once.
The core challenge in infinite-armed bandits is knowing when to stop exploring new arms and start exploiting a promising one. Previous algorithms typically relied on a simple "1-failure" rule: play an arm until it fails, and if it lasted long enough without failing, stick with it. While simple to implement, these methods resulted in a regret (the difference between the total reward and the theoretical maximum) of $2\sqrt{n}$. The authors of this paper sought to close the gap between this performance and the theoretical lower bound.
The Two-Target Algorithm
To improve upon single-threshold methods, the authors propose the Two-Target Algorithm. Instead of using a single threshold to decide whether to keep an arm, they implement two successive targets:
- Target 1 ($\ell_1$): A quick, aggressive filter to discard "bad" arms. If the initial "run" (the number of consecutive successes before the very first failure) is shorter than $\ell_1$, the arm is immediately dropped.
- Target 2 ($\ell_2$): A deeper validation phase for "good" arms. If an arm passes the first filter, the algorithm observes it until it accumulates $m$ failures. If the total number of successes across those $m$ failures meets the second target $\ell_2$, the arm is "locked in" and exploited until the end of the time horizon.
The paper details two versions of this approach:
- Known Horizon: The total number of steps ($n$) is known in advance, allowing the algorithm to set fixed, optimized targets.
- Anytime Version: The targets grow dynamically over time ($\ell_1(t)$ and $\ell_2(t)$), allowing the algorithm to run indefinitely without knowing its stopping point.
Experimental Setup
As a theoretical machine learning paper, the authors evaluate their algorithm using synthetic simulations to ensure rigorous statistical testing. They test against two primary reward distributions:
- Uniform distribution: Mean rewards are spread evenly between 0 and 1.
- Beta(1, 2) distribution: A more challenging scenario where "good" arms are rarer, making the exploration phase significantly harder.
The simulations involved $10^5$ independent samples to ensure statistical significance, plotting the expected failure rate over varying time horizons.
Key Insights
- The Power of Two Stages: A single-stage filter is often too blunt. By using a small $\ell_1$ to weed out obvious losers quickly, the algorithm preserves its "time budget" to more carefully vet promising candidates with a larger $\ell_2$.
- Optimizing the Constant: While most bandit research focuses on the "order" of regret (e.g., $\sqrt{n}$), this paper dives into the constant factor. The authors prove that the optimal constant is $\sqrt{2} \approx 1.41$, whereas previous bests were stuck at $2$.
- Intrinsic Stopping Rules: Unlike standard algorithms (like UCB) that require mandatory exploration of all arms, this approach uses the observed rewards themselves to decide when to stop looking for new options. This makes it highly practical for shorter time horizons where exhaustive exploration is impossible.
Key Results
- Asymptotic Optimality: For a known horizon $n$, the algorithm achieves a regret of $\sqrt{2n}$ (for large $m$). The authors provide a mathematical proof that no algorithm can do better than this, establishing it as asymptotically optimal.
- Anytime Performance: The anytime version achieves a regret of $2\sqrt{n}$. While higher than the known-horizon version, the authors conjecture this is the best possible performance for an algorithm operating without a known end date.
- Numerical Superiority: In simulations, the two-target approach significantly outperformed traditional single-target policies. As shown in the figure above, the expected failure rate of the two-target algorithm closely tracks the asymptotic lower bound, particularly excelling in the more difficult Beta(1,2) distribution where finding a good arm is harder.
Limitations and Future Work
The current theoretical proof relies on the reward distribution's support containing 1 (meaning there must be a possibility, however small, of finding an "ideal" arm). While the authors mention extensions to other distributions in the appendix, developing fully "distribution-free" versions remains a promising future path. Additionally, while the lower bound for the known horizon is proven, the lower bound for the anytime case remains a conjecture. Finally, comparing this infinite-armed approach against state-of-the-art finite-armed algorithms (like Thompson Sampling) in massive but finite settings would provide valuable practical insights.
Summary updated