Abstract
This paper revisits the classic one-armed bandit problem introduced by Woodroofe (1979), characterized by sequential sampling from two populations where one reward distribution depends on an unknown parameter and an observable covariate. Moving beyond traditional Bayesian analysis, we investigate the problem through a minimax lens. We demonstrate that the optimal regret—the loss incurred due to uncertainty—is fundamentally determined by the "local" behavior of the covariate distribution near the decision boundary. We propose two rate-optimal policies: a modified nearly-myopic rule and a forced sampling strategy. Our results reveal three distinct regret regimes—finite, logarithmic, and power-law—depending on the margin conditions of the covariate.
Introduction
The "one-armed bandit" problem is a foundational model for sequential decision-making under uncertainty. In its simplest form, an agent chooses between a "safe" arm with a known reward and a "risky" arm with an unknown distribution. Woodroofe (1979) extended this by introducing covariates ($X$), which provide side information that influences the reward of the risky arm. A classic example is a clinical trial where a physician must choose between a standard treatment (known efficacy) and a new treatment whose success may vary based on patient-specific factors like age or disease severity.
The central challenge is the exploration-exploitation trade-off: the agent must sample the unknown arm to learn its parameters (exploration) while simultaneously attempting to maximize immediate rewards (exploitation). While Woodroofe’s original work utilized a Bayesian framework, this study adopts a minimax perspective, seeking to identify policies that perform well against the worst-case scenario for the unknown parameter $\theta$.
The Decision Model and Regret
We consider a model where the reward of the unknown arm is given by $Y = X - \theta + \epsilon$, where $X$ is the covariate and $\epsilon$ is random noise. The goal is to maximize the cumulative expected reward over a time horizon $n$. The performance of a sampling policy is measured by "regret"—the difference between the reward obtained by an oracle who knows $\theta$ and the reward obtained by the policy.
In the minimax setting, we aim to minimize the maximum possible regret over a range of potential values for $\theta$. This paper identifies that the difficulty of this task is not uniform; it depends heavily on the distribution of the covariate $X$.
The Tsybakov Margin Condition
A key contribution of this research is the application of the Tsybakov margin condition to the bandit problem. This condition describes the density of the covariate distribution near the decision boundary—the point where the expected rewards of both arms are equal.
The "margin" determines how often the decision-maker faces "hard" choices where the two arms are nearly indistinguishable. The authors parameterize this using a value $\alpha$:
- Large $\alpha$: The covariate rarely falls near the boundary, making the optimal choice clearer. In the extreme case ($\alpha = \infty$), the distribution is discrete and separated from the boundary.
- Small $\alpha$: The covariate frequently clusters near the boundary, making it difficult to distinguish which arm is superior without extensive sampling (e.g., a uniform distribution where $\alpha = 1$).
Proposed Sampling Policies
The study analyzes two primary algorithmic approaches to address the minimax problem:
- Nearly-Myopic Policy: A purely myopic (greedy) policy always chooses the arm that appears best based on current data. However, in a minimax setting, greed can lead to "locking in" on a sub-optimal arm. The authors propose a "nearly-myopic" rule that adds a vanishing exploration bonus $\delta_t$. This bonus encourages the agent to keep exploring the unknown arm early on, gradually decreasing as confidence in the estimate of $\theta$ grows.
- Forced Sampling Policy: This policy ignores immediate rewards at specific, pre-determined intervals to pull the unknown arm. By forcing exploration, the policy ensures that the estimate of $\theta$ improves at a consistent rate, regardless of early noise in the data.
Three Regimes of Regret
The analysis proves that the maximum regret follows one of three mathematical trajectories based on the covariate distribution:
- Finite Regret: In "easy" cases where the distribution is thin near the boundary (high $\alpha$), the total regret remains bounded by a constant, even as the number of trials $n$ goes to infinity.
- Logarithmic Regret: In intermediate cases, regret grows at a rate of $\ln(n)$ or $(\ln n)^2$.
- Power-law Regret: In "hard" cases where the covariate density is high near the boundary (low $\alpha$), regret grows as $n^\gamma$ (where $0 < \gamma < 1$), indicating that the cost of uncertainty remains high throughout the process.
Conclusion and Future Directions
This work establishes the theoretical "speed limits" (lower bounds) for Woodroofe’s bandit problem and demonstrates that the proposed policies are rate-optimal, meaning they achieve these limits. Numerical simulations confirm that while myopic rules are often sufficient in Bayesian contexts, intentional exploration is required to achieve minimax optimality.
Future research may focus on unifying these policies into a single algorithm that adapts to an unknown $\alpha$. Additionally, relaxing the assumptions that the covariate distribution is known and that the reward relationship is strictly linear would bring this theoretical framework closer to complex, real-world machine learning applications.
Summary updated