Next-Token Prediction and Regret Minimization
By Mehryar Mohri, Clayton Sanford, Jon Schneider, Kiran Vodrahalli, Yifan Wu
Studies when next-token prediction models trained on a distribution can yield low adversarial regret in online decision-making. Shows that with unbounded context, any distribution is exponentially close to a low-regret distribution, but bounded context introduces fundamental limitations.