Pooling and Drift in Delayed Bandits

In many operational settings, decisions must be made long before their outcomes are known. While intermediate signals (like clicks) arrive quickly, the final outcome (like a purchase) is delayed. This paper asks whether these intermediate states can be used to pool information across multiple actions, effectively reducing the learning cost from the number of actions (K) to the number of genuinely different state-based regimes (the effective dimension, v).

The author proposes a state-pooled version of the EXP3 algorithm, called STATE-EXP3. By leveraging the assumption that the outcome depends on the action only through an intermediate state, the algorithm updates the estimates for all actions that could have produced the observed state, rather than just the action that was played. The paper derives regret bounds for this approach and provides a lower bound to characterize the unavoidable cost of delay and information drift, even when stale loss information is provided for free.

The study demonstrates that the leading term of the regret bound is governed by the effective dimension v, which can be much smaller than the total number of actions K. On generated data, this state-channel approach cuts regret by up to 79 percent compared to action-level weighting. However, the paper also proves that pooling cannot eliminate the temporal cost of waiting; even with perfect knowledge of stale losses, there is a lower bound on regret that scales with the delay and the rate at which losses drift over time.

This work provides a theoretical framework for understanding when and why intermediate observations help in delayed bandit problems. It suggests that for large catalogues (such as recommendation systems) where many items funnel users through a small number of engagement patterns, the complexity of learning is determined by the structure of the funnel rather than the size of the catalogue. This offers a path to more efficient learning in systems where feedback is inherently slow.