Online combinatorial optimization with stochastic decision sets and adversarial losses

Gergely Neu, Michal Valko

TL;DR

This paper introduces a novel technique called Counting Asleep Times (CAT) to solve online learning problems where actions (like road segments or sensor readings) randomly become unavailable. By replacing wasteful exploration phases with a clever temporal estimation trick, the authors achieve significantly better performance and theoretical "regret" bounds for complex, combinatorial decision-making tasks.

What Problem Does This Paper Address?

In standard online learning, a "learner" repeatedly chooses an action and tries to minimize their total loss (like travel time or cost). Most models assume every action is available every single day. In reality, things break: a road is closed for construction, a sensor runs out of battery, or a product goes out of stock. This is known as the "sleeping experts" or "sleeping bandit" problem.

The challenge is twofold:

  1. Stochastic Availability: You don't know which actions will be "awake" until the round starts.
  2. Combinatorial Complexity: In many cases, you aren't just picking one item; you’re picking a set of items (like a path through a network). The number of possible paths is astronomical, making it impossible to track each one individually.

Previous solutions required a "warm-up" phase to estimate how often each action was available. This was incredibly wasteful—if you spend the first 5,000 rounds just watching which roads are open, you’ve already lost the game.

Methods

The authors build their approach on the Follow-the-Perturbed-Leader (FPL) algorithm. FPL works by adding a bit of random "noise" to the historical losses of each action and then picking the one that looks best.

The "secret sauce" of this paper is the Counting Asleep Times (CAT) loss estimation technique.

  • The Old Way: To estimate the true loss of an unavailable item, you’d need to know the probability ($a_i$) that it is available.
  • The CAT Way: The authors realized that the time an item spends "asleep" (the number of rounds until it wakes up again) is a geometric random variable that perfectly encodes that missing probability.

By using the "asleep time" to scale their loss estimates, the learner can create an unbiased picture of the world without ever explicitly calculating the availability distribution. They apply this to three feedback levels:

  • Full Information: You see all losses.
  • Restricted Information: You only see losses for items that were "awake."
  • Semi-bandit: You only see losses for the items you actually chose.

Datasets

The paper uses simulated environments to rigorously test the algorithms against adversarial (worst-case) losses:

  1. Multi-arm Bandits: A 5-arm setup where each arm has a different probability of being available.
  2. Shortest Path on Grids: The learner must find the best path through $3 \times 3$ and $10 \times 10$ grids (representing 12 and 180 individual edges, respectively). Losses were generated using random walks to simulate fluctuating traffic or costs.
Cumulative regret for 5-arm sleeping bandits

Key Insights and Ideas

  • Time is a Proxy for Probability: The most elegant insight is that you don't need to "learn" a distribution if you simply track how long you've been waiting for an action to reappear. This eliminates the need for a separate exploration phase.
  • Efficiency in Complexity: By focusing on the components (the edges of a graph) rather than the combinations (the full paths), the algorithm remains computationally efficient even when the number of possible actions is huge.
  • Removing Explicit Exploration: Unlike previous state-of-the-art algorithms (like BSFPL), the CAT-based algorithms don't need to force "exploration rounds" where they pick random actions just to see what happens. The natural randomness of the "sleeping" sets provides enough information.

Key Results

  • Theoretical Leap: In the sleeping bandit setting, they improved the "regret" bound (the gap between the learner and the best possible strategy) from $O(T^{4/5})$ to $O(T^{2/3})$. In the restricted information setting, they hit the gold standard of $O(\sqrt{T})$.
  • Empirical Dominance: In the $10 \times 10$ grid experiment, the previous best algorithm (COMBBSFPL) spent nearly 9,000 out of 10,000 rounds just exploring the map. In contrast, the SLEEPINGCATBANDIT algorithm started optimizing almost immediately, resulting in drastically lower cumulative loss.
Regret per step for 10x10 grid shortest path

Limitations and Future Work

The authors note that while they've made a massive leap, there is still a gap in the semi-bandit setting. They achieved a regret of $O(T^{2/3})$, but they suspect that with even more sophisticated knowledge of the availability distribution, it might be possible to reach $O(\sqrt{T})$.

Additionally, the current CAT technique assumes that the "sleeping" patterns are independent of the losses. If a road only closes because it's congested (a non-stochastic relationship), the current model might need further refinement. Exploring whether CAT can be extended to estimate more complex dependencies in the availability set remains an open research question.

Summary updated

Abstract

Most work on sequential learning assumes a fixed set of actions that are available all the time. However, in practice, actions can consist of picking subsets of readings from sensors that may break from time to time, road segments that can be blocked or goods that are out of stock. In this paper we study learning algorithms that are able to deal with stochastic availability of such unreliable composite actions. We propose and analyze algorithms based on the Follow-The-Perturbed-Leader prediction method for several learning settings differing in the feedback provided to the learner. Our algorithms rely on a novel loss estimation technique that we call Counting Asleep Times. We deliver regret bounds for our algorithms for the previously studied full information and (semi-)bandit settings, as well as a natural middle point between the two that we call the restricted information setting. A special consequence of our results is a significant improvement of the best known performance guarantees achieved by an efficient algorithm for the sleeping bandit problem with stochastic availability. Finally, we evaluate our algorithms empirically and show their improvement over the known approaches.
BibTeX
@inproceedings{neu2014online,
  author = {Gergely Neu and Michal Valko},
  title = {{Online combinatorial optimization with stochastic decision sets and adversarial losses}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=rkbMrdZd-S},
}
Figure