Abstract: We consider algorithms for selecting actions in order to maximize rewards chosen by an adversary, where the set of actions available on any given round is selected stochastically. We present the first polynomial-time, "no-regret" algorithms for this problem, providing efficient tools for decision-making in volatile environments like online ad auctions or network routing.
The Sleeping Bandit Problem
In standard online learning, an algorithm chooses from a fixed set of $n$ actions every round to maximize a reward. However, in real-world scenarios—such as an advertiser's budget being depleted or a server going down—actions often become unavailable. These are known as "sleeping" actions.
Previous research has largely addressed two extremes: stochastic rewards (relatively simple) and fully adversarial settings where an opponent controls both rewards and availability. The latter is typically solved using the EXP4 algorithm, which is computationally prohibitive ($O(n!)$) as it tracks every possible ranking of actions. This paper targets the critical middle ground: Adversarial rewards combined with Stochastic availability.
Efficient Algorithms for Volatile Environments
The authors introduce two main algorithms to bridge this gap:
- SFPL (Sleeping Follow the Perturbed Leader): Designed for the "full information" setting, it adds random perturbations to cumulative rewards and selects the highest-ranked available action.
- BSFPL (Bandit SFPL): Tailored for the "bandit" setting where only the reward of the chosen action is observed. It utilizes an initial estimation phase to learn action availability and employs a clever unbiased estimator to update its model without needing to see rewards for sleeping actions.
At the core of these methods is a geometric interpretation. The authors prove that choosing the best ranking (action list) is equivalent to solving a linear optimization problem over a specific polytope in high-dimensional space. This transformation allows the use of efficient "Follow the Perturbed Leader" techniques, reducing the computational complexity from exponential to polynomial.
Empirical Evaluation and Results
The algorithms were tested using a synthetic dataset of 5 actions with a 50% independent probability of being available each round. Rewards were generated via a random walk to simulate an oblivious adversary.
In simulations, BSFPL outperformed EXP4 in terms of per-round regret. While EXP4 has a tighter theoretical bound for fully adversarial availability, BSFPL’s specialized approach for stochastic availability allowed it to converge significantly faster on the test data.
Discussion and Future Directions
While the paper achieves a major breakthrough in polynomial efficiency, a gap remains in the bandit setting's regret bound, currently proved at $O(T^{4/5})$. The authors suggest that more sophisticated analysis might yield a tighter bound, such as $O(T^{2/3})$. Additionally, future work may explore relaxing the independence assumption between action availability and reward, which could be critical in highly correlated adversarial environments like financial markets.
Summary updated