ICML paper: finite context windows impose impossibility results for adversarial regret
burny_tech · x · 2026-11-02
An arXiv paper by Mehryar Mohri, Clayton Sanford, Jon Schneider, Kiran Vodrahalli and Yifan Wu formally connects next-token prediction to regret minimization against adaptive adversaries.
Key results:
- With unbounded context, every opponent-action distribution is exponentially close (in TV distance) to a low-regret one, so sublinear adversarial regret is always achievable at negligible cost to prediction accuracy.
- With bounded context windows (as in modern Transformers), some distributions remain Θ(1)-far from any low-regret distribution — an impossibility result.
- Modest context expansion restores near-optimal regret guarantees, and the full-history construction can be implemented by adding a constant number of Transformer layers, backed by preliminary small-model experiments.
More from Models
- OpenAI merges ChatGPT's chat and Work tabs; Codex now shares the same usage pool — TechCrunch AI · 2026-11-02
- Reddit users report Gemini Argon underperforming Gemini 3.1 Pro on instructions and audio — PreparationOdd430 · 2026-11-02
- Dev warning: avoid yearly prepaid LLM plans as labs quietly cut quotas — HankYeomans · 2026-11-02
- KVARK Sparkle 1.0 open-weights: Qwen3.8-27B derivative cuts thinking tokens by up to 67% — dzulajla98 · 2026-11-02
- 129 Cyber Incidents in 10 Days: Open Models Already Causing "Billions per Day" in Damages — Afinetheorem · 2026-11-02
- Rumor: Qwen 4 will be Alibaba's last open-weight model release — Chemical_Hawk_6307 · 2026-11-02