# Next-Token Prediction and Regret Minimization

arXiv: https://arxiv.org/abs/2603.28499 · HTML: https://mlsanity.com/paper/2603.28499/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 24 references that are in the map.
- First posted on arXiv 30 Mar 2026.

## Builds on (most cited first, 10 of 10)

- [Decision Transformer: Reinforcement Learning via Sequence Modeling](https://mlsanity.com/paper/2106.01345/) (2021)
- [DeepAR: Probabilistic Forecasting with Autoregressive Recurrent Networks](https://mlsanity.com/paper/1704.04110/) (2017)
- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [Transformers, parallel computation, and logarithmic depth](https://mlsanity.com/paper/2402.09268/) (2024)
- [Can large language models explore in-context?](https://mlsanity.com/paper/2403.15371/) (2024)
- [U-Calibration: Forecasting for an Unknown Agent](https://mlsanity.com/paper/2307.00168/) (2023)
- [Cultural Evolution of Cooperation among LLM Agents](https://mlsanity.com/paper/2412.10270/) (2024)
- [Optimization of Scoring Rules](https://mlsanity.com/paper/2007.02905/) (2020)
- [Provable Length Generalization in Sequence Prediction via Spectral Filtering](https://mlsanity.com/paper/2411.01035/) (2024)
- [Online Learning with Bounded Recall](https://mlsanity.com/paper/2205.14519/) (2022)

## Abstract (arXiv)

We consider the question of how to employ next-token prediction algorithms in adversarial online decision-making environments. Specifically, if we train a next-token prediction model on a distribution D over sequences of opponent actions, when is it the case that the induced online decision-making algorithm (by approximately best responding to the model's predictions) has low adversarial regret (i.e., when is D a low-regret distribution)? For unbounded context windows (where the prediction made by the model can depend on all the actions taken by the adversary thus far), we show that although not every distribution D is a low-regret distribution, every distribution D is exponentially close (in TV distance) to one low-regret distribution, and hence sublinear regret can always be achieved at negligible cost to the accuracy of the original next-token prediction model. In contrast to this, for bounded context windows (where the prediction made by the model can depend only on the past w actions taken by the adversary, as may be the case in modern transformer architectures), we show that there are some distributions D of opponent play that are Theta(1)-far from any low-regret distribution D' (even when w = Omega(T) and such distributions exist). Finally, we complement these results by showing that the unbounded context robustification procedure can be implemented by layers of a standard transformer architecture, and provide empirical evidence that transformer models can be efficiently trained to represent these new low-regret distributions.