TL;DR
This paper tackles the challenge of online learning when the available actions change unpredictably over time. They introduce a novel "Counting Asleep Times" (CAT) method for estimating losses of unavailable actions and develop efficient algorithms with improved regret bounds for various feedback scenarios, outperforming existing methods in experiments.
What Problem Does This Paper Address?
In many real-world sequential decision-making problems, the set of available choices isn't fixed. Think about navigating with a GPS where roads can be unexpectedly blocked, or a recommender system where items go out of stock. Traditional online learning algorithms assume a constant action space, which breaks down in these dynamic scenarios. This paper addresses this gap by developing algorithms that can learn effectively even when the set of available actions is stochastic and unknown, aiming to minimize cumulative loss (regret) over time.
Methods
The core of the paper's contribution lies in two main areas:
- Counting Asleep Times (CAT): This is a novel loss estimation technique. Instead of trying to predict when an action will become available (which requires learning the underlying availability distribution, a difficult task), CAT cleverly estimates the loss of an unavailable action by using its last known loss value. This is justified by the idea that the "asleep-time" (time until an action is available again) can be modeled as a random variable, and this method provides an unbiased estimate of the true loss.
- Follow-The-Perturbed-Leader (FPL) Framework: The authors build their algorithms upon the well-established FPL framework. FPL works by maintaining an estimate of cumulative losses and then choosing the action that minimizes a perturbed version of this cumulative loss. The novelty here is how they adapt FPL to the stochastic availability setting by using their CAT loss estimates.
They propose algorithms for three feedback settings:
- Full Information: The learner sees the losses of all actions.
- Restricted Information: The learner sees losses only for available actions. This is a natural middle ground.
- Semi-Bandit: The learner only sees losses for the components of the action it actually chose.
Datasets
Not discussed in the paper. The experiments use simulated environments based on the shortest path problem on grids and multi-arm bandit settings.
Key Insights and Ideas
- The "sleeping" nature of actions is key: The paper frames the problem around actions that become unavailable ("sleep") and then reappear. This perspective allows for the development of specialized techniques.
- Estimating the unavailable is possible and efficient: The CAT method is a significant breakthrough. It avoids the computationally expensive step of learning the availability distribution, which was a bottleneck in prior work. This makes the algorithms more practical.
- FPL is a versatile backbone: The paper demonstrates that the FPL framework can be effectively adapted to handle stochastic action availability across different feedback scenarios, leading to strong theoretical guarantees.
- Implicit exploration is better: The authors' empirical results suggest that their CAT-based approach, which implicitly explores by using past information, outperforms methods that rely on explicit, separate exploration phases.
Key Results
The paper provides theoretical guarantees in the form of regret bounds for their proposed algorithms:
- Restricted Setting (SLEEPINGCAT): Achieves a regret bound of $O(\sqrt{T})$ in the restricted information setting, which is a significant improvement over previous results.
- Semi-Bandit Setting (SLEEPINGCATBANDIT): Achieves a regret bound of $O((dT)^{2/3} (\log d)^{1/3})$, which is a substantial improvement over prior work for the sleeping bandit problem, particularly for large action spaces.
- Empirical Validation: Experiments show that their algorithms (SLEEPINGCATBANDIT and a combinatorial extension) significantly outperform existing methods like BSFPL, especially in scenarios with low availability, demonstrating the practical benefits of their approach.
Limitations and Future Work
- Semi-Bandit Limitations: While their SLEEPINGCATBANDIT algorithm offers improved bounds, it still relies on estimating certain quantities that are difficult to compute without knowing the availability distribution. The paper notes that achieving a $\sqrt{T}$ regret bound in the semi-bandit setting, similar to the restricted case, remains an open challenge.
- Future Work: The authors suggest exploring if the CAT technique can be extended to estimate all relevant quantities of the availability distribution $P$, which could lead to further improvements. They also leave open the question of whether a $\sqrt{T}$ regret bound is achievable in the semi-bandit setting.
- Theoretical vs. Practical: The paper's theoretical analysis relies on certain assumptions (e.g., the availability distribution being fixed). While the CAT method is designed to avoid learning this distribution, further work could investigate performance under more dynamic availability patterns.
Summary updated