Adversarial Blocking Bandits

Nick Bishop, Hau Chan, Debmalya Mandal, Long Tran-ThanhNeurIPS 2020 · OpenReview

In standard multi-armed bandit (MAB) problems, an agent can pull any arm at any given time. However, many real-world scenarios—such as routing tasks to servers or allocating projects to freelancers—involve blocking. Once a resource is utilized, it enters a "cooldown" period and becomes unavailable for a specific duration.

While previous research has explored stochastic blocking bandits (where rewards follow a fixed probability distribution), this paper tackles the significantly more challenging adversarial setting. In this environment, rewards fluctuate unpredictably over time and can be chosen by an adversary to thwart the player.

The Hardness of Blocking

The simple addition of a cooldown period transforms a standard bandit problem into a complex scheduling nightmare. The authors prove that even in an offline optimization setting—where all rewards and blocking durations are known in advance—finding an optimal strategy is strongly NP-hard. This eliminates the possibility of a fully polynomial-time approximation scheme (FPTAS) unless P=NP.

Furthermore, the authors demonstrate that if rewards can change arbitrarily or if arms can be blocked indefinitely, achieving "sub-linear regret" (performing comparably to the optimal strategy over time) is impossible. To make the problem tractable, the authors introduce a path variation budget ($B_T$), which bounds how much the total reward values can fluctuate over the entire time horizon.

Algorithmic Framework

The paper analyzes the problem across different levels of information availability, proposing specific algorithms for each:

1. Online Optimization (Full Information Before Pull)

When the current round's rewards and durations for all arms are visible before making a choice, the authors propose Greedy-BAA (Greedy Best Available Arm). This algorithm simply selects the highest-reward arm that is not currently blocked. Greedy-BAA provides a provable approximation guarantee that depends on the ratio of maximum to minimum blocking durations and the path variance of the rewards.

2. The Bandit Setting (Partial Information)

In the true bandit setting, the agent only observes the reward and duration of the arm they actually pull. To address this, the authors introduce the Repeating Greedy Algorithm (RGA). RGA operates in batches using a clever "Explore-Wait-Exploit" cycle:

  • Explore: Pull every arm once to sample the current rewards.
  • Wait: Allow all blocking periods to expire so all arms are fresh.
  • Exploit: Apply the Greedy-BAA logic for the remainder of the batch, using the data gathered during exploration.
  • Wait Again: Ensure no blocking carries over to disrupt the next batch.

3. RGA-META for Unknown Budgets

RGA requires prior knowledge of the variation budget ($B_T$) to properly size its batches. For scenarios where $B_T$ is unknown, the authors design RGA-META. This variant uses the Exp3 algorithm as a "master" routine to dynamically test different budget guesses and learn the optimal one on the fly.

Key Results and Regret Bounds

The paper establishes rigorous mathematical guarantees for their proposed algorithms:

  • Known Variation Budget: RGA achieves a dynamic approximate regret of $O(\sqrt{T(2\tilde{D} + K)B_T})$, where $\tilde{D}$ is the maximum blocking duration, $K$ is the number of arms, and $T$ is the time horizon.
  • Tightness: If the blocking durations are small ($O(1)$), the regret bound for RGA is tight, matching known lower bounds for standard adversarial bandits and suggesting the approach is near-optimal for those cases.
  • Unknown Variation Budget: RGA-META achieves a regret bound of $O((K+\tilde{D})^{1/4}\tilde{B}^{1/2}T^{3/4})$, where $\tilde{B}$ is the maximal path variation budget within each batch.

Limitations and Future Directions

As a theoretical work focused on algorithmic complexity and mathematical proofs, the paper does not include empirical evaluations on datasets.

A notable open question is the performance gap in the unknown budget setting. RGA-META achieves an $O(T^{3/4})$ regret bound, and the authors leave it open whether this can be tightened to the ideal $O(\sqrt{T})$ regret. Additionally, the current model assumes that once an arm is pulled, its blocking duration is deterministic (though it can change over time). Future research could explore stochastic or fully adversarial blocking durations, as well as delve deeper into the full-information feedback model.

Summary updated

Abstract

We consider a general adversarial multi-armed blocking bandit setting where each played arm can be blocked (unavailable) for some time periods and the reward per arm is given at each time period adversarially without obeying any distribution. The setting models scenarios of allocating scarce limited supplies (e.g., arms) where the supplies replenish and can be reused only after certain time periods. We first show that, in the optimization setting, when the blocking durations and rewards are known in advance, finding an optimal policy (e.g., determining which arm per round) that maximises the cumulative reward is strongly NP-hard, eliminating the possibility of a fully polynomial-time approximation scheme (FPTAS) for the problem unless P = NP. To complement our result, we show that a greedy algorithm that plays the best available arm at each round provides an approximation guarantee that depends on the blocking durations and the path variance of the rewards. In the bandit setting, when the blocking durations and rewards are not known, we design two algorithms, RGA and RGA-META, for the case of bounded duration an path variation. In particular, when the variation budget B<em>T is known in advance, RGA can achieve O(\sqrt{T(2\tilde{D}+K)B</em>{T}}) dynamic approximate regret. On the other hand, when B_T is not known, we show that the dynamic approximate regret of RGA-META is at most O((K+\tilde{D})^{1/4}\tilde{B}^{1/2}T^{3/4}) where \tilde{B} is the maximal path variation budget within each batch of RGA-META (which is provably in order of o(\sqrt{T}). We also prove that if either the variation budget or the maximal blocking duration is unbounded, the approximate regret will be at least Theta(T). We also show that the regret upper bound of RGA is tight if the blocking durations are bounded above by an order of O(1).
BibTeX
@inproceedings{bishop2020adversarial,
  author = {Nick Bishop and Hau Chan and Debmalya Mandal and Long Tran-Thanh},
  title = {{Adversarial Blocking Bandits}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=j68MWwq0OJG},
}
Figure