Metraipolis › archive › dc_b8cea925ecda

Pooling and Drift in Delayed Bandits — arXiv:2609.01761

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.01761
License (as archived)
CC0-1.0
Archived
2026-10-17T05:01:02.696Z
SHA-256 of the archived text
ead90a85cf3506252ca5cf567e274578c16fde219db412ff0d6cdf49fd8c947a
Stable URL of this page
https://metraipolis.com/documento/dc_b8cea925ecda

How to cite

Pooling and Drift in Delayed Bandits — arXiv:2609.01761 — arXiv (en), https://arxiv.org/abs/2609.01761 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b8cea925ecda (Metraipolis archive dc_b8cea925ecda, sha256 ead90a85cf3506252ca5cf567e274578c16fde219db412ff0d6cdf49fd8c947a)
BibTeX
@misc{dcb8cea925ecda,
  title = {Pooling and Drift in Delayed Bandits — arXiv:2609.01761},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.01761},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b8cea925ecda; sha256 ead90a85cf3506252ca5cf567e274578c16fde219db412ff0d6cdf49fd8c947a},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.01761. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\Omega(\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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-03 in cs.LG).
Categorie arXiv: Machine Learning (stat.ML) ; Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.01761 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T04:09:43.351Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-03?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).