Source-linked AI summary
Pooling and Drift in Delayed Bandits
Melika Baghi
TL;DR
Delayed bandits ask how to learn when outcomes arrive after actions are chosen, and whether intermediate states can reduce the cost imposed by many actions. The paper develops effective-dimension pooling under state sufficiency, proves matching limits for temporal drift, and reports substantial regret reductions in generated experiments. Its scope assumes known state structure and leaves simultaneous adaptation to overlap and drift open.
Problem
The paper asks whether intermediate states can lower delayed-bandit learning costs below what the action count K alone forces.
Method
The paper pools each delayed outcome across actions capable of producing its observed state and analyzes effective dimension separately from drift during waiting.
Results
Theorem 1 replaces leading action-count dependence with V¯, while Theorem 2 gives Ω(√(dE min{1 + log J, T/d})) even with stale losses supplied.
Takeaways & Limitations
Under state sufficiency, a large catalogue can avoid the leading action-count learning cost through pooling, but stale-information costs remain.
Takeaways & Limitations
The upper bound captures overlap while the lower bound characterizes drift separately, and simultaneous adaptation remains open.
Abstract
from arXiv · showhide
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 $\widetilde{O}(\sqrt{(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 $v_t$ between $1$ and the number of states, and prove $\widetilde{O}(\sqrt{(d+1)V\log K})$ for a rotating algorithm and $\widetilde{O}(\sqrt{V^{-}}+\sqrt{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 $Ω(\sqrt{dE\min\{1+\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.
1 Introduction
Delayed decisions are costly because outcomes arrive after commitment, but intermediate states can pool evidence across actions. The paper measures this advantage with effective dimension while separating pooling gains from irreducible waiting costs.
- Motivation: Delayed outcomes constrain operations even when faster signals arrive first.The decision is committed before the quantity used for evaluation resolves.
- Problem: The learning cost can depend on the genuinely different regimes induced by actions rather than catalogue size.Thousands of actions may funnel users through only a few engagement patterns.
- Mechanism: State sufficiency enables one delayed outcome to update every action that could have produced the observed state.This is the pooling mechanism behind replacing action-level learning costs.
- Contribution: The effective dimension measures how distinguishable action-induced state distributions are and can be far below K.Theorem 1 uses it in place of the action count.
- Boundary: Waiting remains costly because losses from d rounds earlier become inaccurate as state-specific predictions drift.Theorem 2 isolates this temporal cost even with stale losses supplied to the learner.
2 Problem formulation
The model combines known action-to-state structure with delayed stochastic losses whose conditional mean depends on actions only through observed states. It distinguishes information available immediately, information delayed by d rounds, and optional stale-loss information used for the lower bound.
- Setting: The learner chooses among K actions, observes a state immediately, and receives a loss only d rounds later.The state is sampled from known matrix P, and losses lie in [0,1].
- Assumption: State sufficiency requires the conditional mean loss to depend on the action only through the produced state.An outcome-relevant direct action effect outside the state would invalidate the pooling argument.
- Feedback: STATE-EXP3 changes its play distribution only when delayed outcomes arrive, so its current distribution is measurable before the latest feedback window.The learner can use observed states sooner, but only sufficiently old outcomes have been delivered.
- Objective: Action losses are Pθt, with oblivious state-loss means and static pseudo-regret measured against the best fixed action in hindsight.The environment chooses θt in advance and outcomes are conditionally independent given states.
- Lower-bound oracle: The lower-bound oracle supplies the exact action-loss vector from d rounds earlier, making its resulting regret guarantee stronger.This information is unavailable to STATE-EXP3 and is used only for Theorem 2.
3 Pooling through the state
Pooling replaces action-count dependence with effective dimension, while delay creates a separate cost that sharing cannot remove. The theorems formalize both effects and experiments test them through controlled overlap and catalogue-size comparisons.
- Core result: Pooling replaces the leading action-count dependence by an effective dimension, while waiting retains a separate cost.The two sources of difficulty are treated separately in the analysis.
- Pooling through the state: STATE-EXP3 assigns delayed outcomes across actions according to their likelihood of producing the observed state.The resulting estimator is unbiased, and its noise is governed by vt between 1 and |S|.
- Lower bound: Theorem 2 lower-bounds regret by Ω(√(dE min{1 + log J, T/d})) even when exact losses from d rounds earlier are supplied.Here J counts drifting directions and E bounds movement during the wait.
- Interpretation: The exploration and delay terms arise from different hard instances, so adding them overstates the truth by at most a factor of two.The delay cost grows with the wait, drift during waiting, and the number of drifting directions.
- Experiments: In Figure 2, regret savings increase as effective dimension falls at fixed difficulty, while catalogue size grows thirty-twofold with estimated dimension remaining 1.4–1.8.The figure separates action count from effective dimension.
4 Experiments
Experiments test whether state-based pooling reduces regret when many actions funnel into few engagement states. Across generated families, STATE-EXP3 benefits from low effective dimension and remains sublinear where a best-state assumption fails.
- 79.3%, 63.6% and 38.9%: STATE-EXP3 cut regret against action-level weighting at d = 10, 50, 200.The experiment uses K = 200 generated items and six engagement levels, with estimated dimension 1.97.
- The effective dimension remains nearly constant as the catalogue grows, while gains rise as dimension falls at fixed task difficulty.Figure 2 separates action count from state-induced behavioural complexity in both directions.
- A best-state rule leads seven of nine settings, but its regret grows linearly in T where its assumption fails, whereas STATE-EXP3 stays sublinear.These runs use the algorithm covered by Theorem 1.
5 Discussion
The discussion separates exploitable overlap from unavoidable delay. State sufficiency can remove the leading action-count cost, but stale-information costs persist, and a unified treatment of overlap and drift remains open.
- Known P and low estimated ¯v indicate that delayed outcomes can be pooled across actions, reducing the large-catalogue learning cost.The discussion contrasts this exploitable overlap with the separate cost created by waiting.
- Theorem 2 shows that waiting uncertainty persists even when exact losses from d rounds ago are supplied for free.This isolates temporal cost from the action-level information problem.
- The upper bound captures overlap while the lower bound characterizes drift on a separate axis; one algorithm and guarantee for both remains open.The discussion also notes that ¯v is estimated rather than computed exactly.
A The state-pooled estimator
The state-pooled estimator uses the observed state and its induced probability to update every compatible action. Its weighted second moment is governed by effective dimension, which reflects overlap among action-to-state distributions.
- Algorithm: STATE-EXP3 stores delayed observations and, when outcomes arrive, updates every action using P(Sr | a)Xr/qr(Sr), not only the action played.With m = 1, this is the algorithm used in the experiments; each round costs O(K) once delayed records are stored.
- Worked example: In the three-action example, one observed state produces pooled estimates (1.6, 0.8, 0) versus action-level estimates (2, 0, 0).The pooled estimate charges actions according to their probability of producing the observed state and remains unbiased.
- Estimator properties: The estimator is unbiased for every action, nonnegative, and bounded above by 1/xt(a) under full-support play.The state distribution qt normalizes the action-to-state contribution, with zero-probability states omitted.
- Effective dimension: The effective dimension vt is the pooled estimator’s play-weighted second moment and satisfies 1 ≤ vt ≤ |S|.It replaces the action-level second-moment cost K in the analysis.
- Effective dimension: vt = 1 when all played actions induce the same state distribution, while deterministic onto mappings give vt = |S|.Disjoint private state supports instead yield vt = K, so vt measures overlap rather than row length.
B Proofs: pooling and grouping
The proofs establish delayed regret bounds for interleaved copies and extend them to state grouping. Grouping lowers effective dimension but introduces bias when merged states have different losses.
- Grouping: Grouping states with map g never raises effective dimension, but the grouped estimator tracks group-average losses rather than necessarily the original action losses.The within-group spread δt(g) measures the approximation error introduced by merging.
- Grouping: Merging trades fidelity for sharing: keeping states separate preserves differences that matter but learns more slowly, while merging pays bias bounded by within-group loss spread.Merging need not preserve state sufficiency, so the estimate is correct for a stand-in loss rather than necessarily ct.
- Grouping: The best grouping in the reported experiment was the true four-group structure: regret was lowest at 754 among group sizes 1, 2, 4, 8, and 16.The grouping map was fixed in advance; learning it from data remains open.
- Interleaving: With d + 1 copies, delayed feedback becomes undelayed within each copy, enabling ordinary exponential-weights potential inequalities.Summing copy-wise inequalities produces the delay factor, while pooled second moments contribute V.
- Interleaving: The m = 1 algorithm shares estimates across rounds and avoids the interleaved variant’s additive delay penalty.This is the single-copy algorithm covered by Theorem 1 and used in the experiments.
C Relation to other inaccuracy measures
The paper distinguishes its delayed-outcome inaccuracy measure from neighboring measures by charging only the worst action’s prediction error. This makes its bound potentially stronger when errors are spread across many actions.
- Unlike related feedback-graph settings, the state’s loss must still be estimated from the single outcome that arrives.
- E2 charges only the worst action’s prediction error, whereas Λ2 grows with the number of wrongly predicted actions.
- A bound in E2 can be J times stronger than one using Λ2, with equality when prediction error is concentrated on one action.
D Proofs: the lower bound
The lower-bound proof constructs delayed, drifting instances whose current signs remain unpredictable, while relating the delay-window error E2 to state-loss variation W. It establishes the unavoidable drift scale even with exact stale losses and identifies unresolved adaptivity to overlap and drift.
- E2 ≤ d^2W, so accumulated squared prediction error is bounded by state-loss variation inflated by the delay squared.
- The ratio E2/(d^2W) can approach one when increments share magnitude, sign, and active coordinate, but can be zero when drift lies in P’s kernel.
- The lower-bound construction partitions time into d-length blocks and uses independent Rademacher perturbations that current actions cannot predict.
- The comparator gains from the maximum of J independent random walks, while every algorithm has expected loss T/2 under the randomized current block.
- Every algorithm, even with exact losses from d rounds earlier, incurs Ω(√(dE min{1 + log J, T/d})) on some fixed instance.
- Adapting simultaneously to overlap and drift remains open, and the oracle-assisted result need not retain bandit exploration complexity.
E Numerical detail
The experiments test whether pooling gains track effective dimension rather than action count, and whether the drift lower-bound scale matches observed regret. Generated funnel data shows large state-channel gains, while the drift experiment supports the predicted scaling but leaves some regimes untested.
- Experimental design: All sixteen studies use shared environment parameters and common random-number streams; Experiments 1–3 report the main controlled tests.Experiment 1 uses Dirichlet maps, Experiment 2 a hand-structured funnel, and Experiment 3 the deterministic hard-instance map.
- Experiment 1: 11.7% to 19.3%: matched-difficulty pooling gains rise as effective dimension falls, while the unmatched sweep’s 34.5% to 3.1% decline is confounded.Across 20 paired seeds, the matched gains correlate −0.929 with effective dimension; the apparent contradiction is attributed to changing comparator difficulty.
- Experiment 2: 79.3%, 63.6%, and 38.9%: state-pooled weighting saves these percentages against action-level weighting at d = 10, 50, and 200.The effective dimension is 1.97 versus K = 200 and remains 1.41–1.81 as the catalogue grows from 25 to 800 items.
- Experiment 2: 31.5% to 67.9%: STATE-EXP3 cuts regret against the tuned Zimmert–Seldin baseline in all three funnel cells.With only the baseline grid-tuned, STATE-EXP3 wins at d = 10 and 50 but loses at d = 200; both grid-best comparisons favor STATE-EXP3.
- Limitations: The experiments use generated environments without real data, and the drift study exercises only the 1 + log J branch because every cell has T/d > 1 + log J.The funnel’s protocol also uses eight paired seeds, finite unequal tuning grids, and no adversarial component.
- Experiment 3: 38 to 377: the predicted d E2 min{1 + log J, T/d} scale spans this range, while measured normalized regret ratios remain within a spread below 1.9.The collapse holds across sweeps of d, E2, and J; greedy play with exact stale losses sits at the top of the observed band.
F Proof of Theorem 1: additive delay without interleaving
Theorem 1’s single-copy algorithm obtains an additive delay cost by controlling delayed pooled estimates through state-marginal ratios rather than interleaving independent copies. The proof combines exponential-weights potential analysis with a drift lemma that keeps action weights from changing too quickly.
- Additive delay bound: A single copy is necessary for an additive bound: interleaving d + 1 copies incurs a √m factor through Cauchy–Schwarz.Copy i contributes √(2Vi log K), and summing across m copies gives √(2mV log K).
- Drift lemma: η ≤ 1/(e(d + 1)) implies xt+1(a) ≤ (1 + 1/d)xt(a) and therefore xt+d(a) ≤ e xt(a) for every action and path.Strong induction composes the one-step bound over d rounds; the resulting control lower-bounds the update normalizer.
- Drift lemma: The pooled estimate’s key control is ⟨xt, ˆct−d⟩ = Xt−d qt(St−d)/qt−d(St−d), a state-marginal ratio rather than an uncontrolled normalizer reciprocal.This controls the xt-weighted mass even though individual action estimates may remain unbounded.
- Potential analysis: Centering ζt = ˆct − Xt1 leaves exponential-weights iterates unchanged while simplifying the variance analysis.The shift is constant across actions, so it changes only the proof representation, not the algorithm.
- Potential analysis: The delayed-analysis shift cancels in expectation because xt is measurable before the relevant feedback, while the d undelivered outcomes contribute at most d.The proof uses measurability under the timing convention rather than independence.
- Bound comparison: On the funnel, the additive and interleaved bounds are numerically close near effective dimension 2, but the additive form improves as effective dimension approaches |S|.The additive expression is 3.3(v̄ − 1) + 2d, versus (d + 1)v̄ for the interleaved form.