Multiscale Buffered Interleaving: Constant-Gap Planning and Online Learning for Recovering Rewards

Motivated by the need to keep large collections of AI-agent memories up to date, we study a recovering-reward bandit problem. In each round, at most $K$ of $n$ arms can be pulled, and each arm's expected reward is a bounded, nondecreasing function of the time since its last pull. We develop Multiscale Buffered Interleaving (MBI), which aggregates compatible periodic plans without reward loss and coordinates the remaining requests through multiscale buffering. For the offline problem with known reward curves, MBI achieves a long-run average reward within $L$ of the renewal upper bound, where $L$ bounds the reward of a single pull. This system-wide loss bound is independent of $n$, $K$, and the recovery horizon, improving previous $O(L\sqrt{K})$ guarantees, and a constant-order loss is necessary. For the online problem with unknown reward curves, the proposed policy achieves $\tilde{O}(nL\sqrt{T})$ regret against our offline planning benchmark. A lower bound on growing instance families matches this learning order up to logarithmic factors. Experiments show lower losses than previous purely periodic and randomize-then-interleave methods in both offline and online settings.