# Pooling and Drift in Delayed Bandits

arXiv: https://arxiv.org/abs/2609.01761 · HTML: https://mlsanity.com/paper/2609.01761/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 15 references that are in the map.
- First posted on arXiv 1 Sep 2026.

## Builds on (most cited first, 12 of 12)

- [Online Learning with Feedback Graphs: Beyond Bandits](https://mlsanity.com/paper/1502.07617/) (2015)
- [Delay and Cooperation in Nonstochastic Bandits](https://mlsanity.com/paper/1602.04741/) (2016)
- [Nonstochastic Multiarmed Bandits with Unrestricted Delays](https://mlsanity.com/paper/1906.00670/) (2019)
- [Learning on the Edge: Online Learning with Stochastic Feedback Graphs](https://mlsanity.com/paper/2210.04229/) (2022)
- [Delayed Bandits: When Do Intermediate Observations Help?](https://mlsanity.com/paper/2305.19036/) (2023)
- [Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback](https://mlsanity.com/paper/2510.09127/) (2025)
- [Online Learning with Off-Policy Feedback](https://mlsanity.com/paper/2207.08956/) (2022)
- [Information Capacity Regret Bounds for Bandits with Mediator Feedback](https://mlsanity.com/paper/2402.10282/) (2024)
- [Non-stochastic Bandits With Evolving Observations](https://mlsanity.com/paper/2405.16843/) (2024)
- [Impatient Bandits: Optimizing for the Long-Term Without Delay](https://mlsanity.com/paper/2501.07761/) (2025)
- [Improved Best-of-Both-Worlds Regret for Bandits with Delayed Feedback](https://mlsanity.com/paper/2505.24193/) (2025)
- [Bandit Convex Optimization with Gradient Prediction Adaptivity](https://mlsanity.com/paper/2605.22191/) (2026)

## Abstract (arXiv)

A system often has to act long before it learns whether the act worked: a recommender sees a click in seconds and a purchase in days. With K actions and a delay of d rounds, the best rate known for this setting is widetildeO(√(K+d)T) over T rounds, so a longer menu is always more expensive to learn from. It need not be: if the outcome depends on the action only through the state it produced, then one late outcome informs every action that could have produced the observed state, and the price is set by how many genuinely different states the actions produce rather than by how many actions there are. We measure this using an effective dimension vt between 1 and the number of states, and prove widetildeO(√(d+1)Vlog K) for a rotating algorithm and widetildeO(√V-+√dT) for the single-copy algorithm used in practice, for any budget fixed in advance; merging similar states lowers the price further, at an explicit bias. Even when given the exact losses from d rounds ago, no algorithm escapes Omega(√dEmin1+log J,T/d), where J counts the drifting directions and E bounds how far losses move while the learner waits. On generated data, the state channel cuts regret by up to 79 percent against action-level weighting and, on the funnel family, by 32 to 68 percent against a tuned minimax-optimal method.