Finite Continuum-Armed Bandits

Solenne GaucherNeurIPS 2020 · OpenReview

Abstract In classical multi-armed bandit problems, an agent can repeatedly pull the most rewarding arm to maximize cumulative returns. But what happens when each action can only be taken exactly once? This paper introduces the Finite Continuum-Armed Bandit (F-CAB) model to address scenarios where resources are strictly limited and unique. The authors demonstrate that when the budget is proportional to the number of available actions, the optimal regret scales as $O(T^{1/3})$—surprisingly faster than the $O(T^{1/2})$ rate typical of standard continuum-armed bandits.

The Challenge of Scarcity and Uniqueness

In the standard Multi-Armed Bandit (MAB) framework, an agent learns an arm's reward distribution through repeated pulls. In Continuum-Armed Bandits (CAB), arms are indexed by a continuous variable (such as dosage or price), and the agent can sample any point in that continuous space indefinitely.

However, many real-world applications are defined by scarcity and uniqueness:

  • Medical Trials: A specific patient can only receive a given treatment once.
  • Targeted Advertising: A user may only be receptive to an ad the first time they see it; subsequent impressions lead to "ad fatigue."
  • Crisis Resource Allocation: An organization may have $T$ units of medicine for $N$ potential patients, where each patient is described by unique health covariates.

In these settings, the agent cannot exploit a single optimal arm forever. Once the best arm is used, it is depleted. The agent must instead identify a region of high-quality arms and systematically exhaust them.

Methodology: The UCBF Algorithm

To solve the F-CAB problem, the authors propose the Upper Confidence Bound for Finite continuum-armed bandits (UCBF) algorithm. The approach relies on strategically discretizing the continuous action space:

  1. Discretization: The algorithm divides the continuous covariate space (e.g., the interval $[0, 1]$) into $K$ smaller intervals, or "bins."
  2. Bin Selection: Each bin is treated as a "super-arm" in a traditional bandit problem. The algorithm calculates a UCB score for each bin based on the average reward of the arms previously pulled from it.
  3. Arm Depletion: Upon selecting a bin, the agent pulls an available arm at random from within that bin. Crucially, that arm is then removed. If a bin is entirely depleted, it is no longer considered "alive."
  4. Optimal Binning: The algorithm's success hinges on choosing the right number of bins, $K$. The authors demonstrate that the optimal $K$ scales with $T^{1/3}$. This balances the discretization error (the loss incurred by treating slightly different arms in the same bin as identical) against the estimation error (the cost of exploring to learn which bins are optimal).

Key Insights and Theoretical Guarantees

Because this is a theoretical paper, the authors rely on rigorous mathematical proofs rather than empirical datasets. They operate under natural assumptions, including a uniform distribution of arms across the covariate space and a weak Lipschitz condition (smoothness) on the reward function.

Their analysis yields several profound insights:

  • The "Oracle" Also Suffers: In standard bandits, an omniscient oracle pulls the single best arm $T$ times. In the F-CAB setting, the oracle is forced to pull the $T$ best unique arms. Because the oracle must resort to increasingly "worse" arms as it exhausts the top tier, the performance gap between the learning agent and the oracle (the regret) actually grows more slowly than in infinite-pull scenarios.
  • Faster Convergence: The UCBF algorithm achieves an upper regret bound of $O(T^{1/3} \log(T)^{4/3})$ when the budget $T$ is a fixed proportion of the total arms $N$. The authors also prove a minimax lower bound of $\Omega(T^{1/3})$, confirming that UCBF is essentially optimal. This $O(T^{1/3})$ rate is significantly faster than the $O(T^{1/2})$ rate of standard CAB, suggesting that the "finite" constraint paradoxically makes the regret scaling "easier."
  • A Smooth Phase Transition: The paper identifies a fascinating phase transition based on the ratio of budget to available arms. If there is a massive surplus of arms ($N \gg T$), the problem behaves like a standard CAB because the agent never runs out of near-optimal arms, resulting in $O(T^{1/2})$ regret. As the budget $T$ becomes a larger fraction of $N$, the regret smoothly improves toward $O(T^{1/3})$.
  • Multi-dimensional Extension: While primarily focused on 1D covariates, the authors extend their analysis to $d$ dimensions, showing that the regret scales as $O(T^{d/(d+2)})$.

Limitations and Future Directions

While F-CAB provides a robust framework for non-replacement resource allocation, the current theoretical model has limitations that invite future research:

  • Known, Uniform Distribution: The analysis assumes arms are uniformly distributed and that the total number of arms $N$ is known upfront. In reality, arm density fluctuates, which would require an adaptive discretization strategy. Furthermore, a "streaming" setting where new arms arrive dynamically over time would be highly applicable to real-world systems.
  • Smoothness Assumptions: The theoretical guarantees rely on the reward function being relatively smooth (Lipschitz). If the reward function is highly discontinuous, the uniform binning approach would likely struggle, necessitating more complex boundary-detection methods.

Ultimately, Finite Continuum-Armed Bandits formalizes a highly practical constraint in sequential decision-making, offering both an optimal algorithm and a surprising theoretical result: that forced exploration through depletion can actually lead to more favorable regret scaling.

Summary updated

Abstract

We consider a situation where an agent has $T$ ressources to be allocated to a larger number $N$ of actions. Each action can be completed at most once and results in a stochastic reward with unknown mean. The goal of the agent is to maximize her cumulative reward. Non trivial strategies are possible when side information on the actions is available, for example in the form of covariates. Focusing on a nonparametric setting, where the mean reward is an unknown function of a one-dimensional covariate, we propose an optimal strategy for this problem. Under natural assumptions on the reward function, we prove that the optimal regret scales as $O(T^{1/3})$ up to poly-logarithmic factors when the budget $T$ is proportional to the number of actions $N$. When $T$ becomes small compared to $N$, a smooth transition occurs. When the ratio $T/N$ decreases from a constant to $N^{-1/3}$, the regret increases progressively up to the $O(T^{1/2})$ rate encountered in continuum-armed bandits.
BibTeX
@inproceedings{gaucher2020finite,
  author = {Solenne Gaucher},
  title = {{Finite Continuum-Armed Bandits}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=-zSBoQZhuqf},
}
Figure