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