Next-Token Prediction and Regret Minimization

Mehryar MohriClayton SanfordJon SchneiderKiran VodrahalliYifan Wu

article2026arXiv0 citations

Establishes when next-token predictors can achieve sublinear adversarial regret in online decision-making, proving that unbounded-context models require only negligible accuracy loss whereas bounded-context transformers face fundamental impossibility bounds.

Listen

Modern artificial intelligence increasingly relies on autoregressive sequence models—commonly known as next-token predictors—to guide operational decisions, ranging from algorithmic trading and dynamic pricing to inventory management. In standard settings, these models perform well by predicting the most likely next event based on historical data. However, real-world operational environments frequently face strategic shifts, unexpected disruptions, or adversarial conditions where past data distributions no longer hold. Standard models can fail severely under such distribution shifts, leaving decision-makers exposed to high cumulative losses and poor hindsight performance.

The article evaluates whether next-token prediction models can achieve low regret in adversarial environments without sacrificing their predictive accuracy on standard, expected data distributions. The authors seek to establish theoretical principles and practical methods to robustify sequential prediction models so that automated decision policies perform well under normal conditions while guaranteeing worst-case safety when conditions turn hostile.

To investigate this, the authors developed a mathematical framework connecting probabilistic sequence prediction with online adversarial decision-making. They introduced a robustification mechanism that monitors the historical performance gap of an existing predictive model and switches dynamically to an adaptive reference strategy based on a Polya urn process whenever performance degrades. The authors evaluated this mechanism across both unbounded and bounded context architectures, constructed a formal transformer design simulating the robustified policy, and performed empirical validation using compact transformer networks trained on synthetic binary prediction tasks.

The findings establish that robustification is achievable with minimal trade-offs under full context memory, but encounters structural barriers when context memory is restricted. First, for models with unbounded context windows, any standard prediction model can be converted into a low-regret model with an exponentially small statistical difference from the original distribution, preserving normal performance while bounding worst-case regret. Second, the authors proved that when models operate under a fixed, bounded context window of the same length, robustification is mathematically impossible because the model cannot distinguish between benign and adversarial sequences sharing identical short substrings. Third, expanding the bounded context window by a modest margin restores the ability to achieve vanishing regret. Finally, empirical experiments confirmed that standard transformer architectures can successfully learn this switching mechanism with minimal training overhead and retain superior accuracy alongside robustness across drifting and static data environments.

These results demonstrate that organizations do not have to choose between statistical predictive performance and worst-case risk guarantees. Operational risk can be systematically contained by incorporating adaptive fallback mechanisms directly into sequential AI workflows. Crucially, the analysis highlights that relying on fixed-memory transformer models without expanding context windows leaves automated systems fundamentally vulnerable to adversarial manipulation and out-of-distribution failure.

Organizations deploying transformer models in high-stakes online decision-making should implement runtime regret-monitoring layers that fall back to adaptive baseline policies during unexpected anomalies. Engineering teams should also ensure that models deployed in adversarial settings are allocated expanded context windows rather than tight, fixed-length buffers. Future work should pilot these robustification frameworks in live, complex operational domains—such as high-frequency order books and supply chain routing—to validate performance under multi-dimensional state spaces and real-world latency constraints.

Confidence in these theoretical findings and conceptual simulations is high, supported by rigorous mathematical proofs and controlled empirical replications. However, current empirical evaluations remain focused on synthetic and binary decision environments. Leaders should exercise caution before applying these exact switching thresholds to complex, continuous, or highly multi-agent environments without prior empirical calibration.

Google Microsoft encoder-decoder prediction modes distribution functions next-token prediction regret minimization adversarial regret guarantees

arXiv: 2603.28499

Paper: Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems, Sébastien Bubeck et al. (2012). It provides foundational theoretical regret bounds and exponential weighting mechanisms in adversarial online decision-making environments that underpin the study of low-regret distributions.
Paper: Introduction to Online Convex Optimization, Elad Hazan (2016). It establishes the core mathematical principles and regret minimization framework in online convex optimization against adversarial environments used throughout online decision theory.
Paper: A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting, Yoav Freund et al. (1997). It introduces seminal multiplicative weight update algorithms (Hedge) to achieve sublinear adversarial regret in repeated online decision games.
Paper: Supervised Pretraining Can Learn In-Context Reinforcement Learning, Jonathan Lee et al. (2023). It demonstrates how supervised sequence pretraining on transformers induces in-context decision-making capabilities without parameter updates, directly motivating the study of next-token prediction regret.
Paper: Decision Transformer: Reinforcement Learning via Sequence Modeling, Lili Chen et al. (2021). It introduces the paradigm of framing sequential decision-making and reinforcement learning as conditional next-token autoregressive sequence modeling.
Paper: A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning, Stephane Ross et al. (2010). It formalizes how sequential prediction and imitation learning reduce mathematically to no-regret online learning.

Paper: Multi-agent cooperation through in-context co-player inference, Rajai Nasser et al. (2026). It applies and analyzes in-context sequence model adaptation and best-response prediction to multi-agent game-theoretic environments such as the Iterated Prisoner's Dilemma.

Cover for Next-Token Prediction and Regret Minimization

Abstract

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 $\mathcal{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 $\mathcal{D}$ a \emph{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 $\mathcal{D}$ is a low-regret distribution, every distribution $\mathcal{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 $\mathcal{D}$ of opponent play that are $\Theta(1)$ -far from any low-regret distribution $\mathcal{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.

Topics

encoder-decoder prediction modes distribution functions

Keywords

next-token prediction regret minimization adversarial regret guarantees online prediction worst-case regret external regret sequence prediction Hedge algorithm length generalization large language models

1 Introduction
1.1 Our Results
1.2 Related Work
2 Model and Preliminaries
2.1 Next-Token Prediction
2.2 Adversarial Online Decision Making
2.3 Interplay between Next-Token Prediction and Regret Minimization
3 Robustification with Unbounded Context Length
4 Robustification with a Bounded Context Length
4.1 Impossibility with the Same Context Length
4.2 Robustification with a Longer Context Length
5 Training Low-Regret Transformer Models
5.1 Representing Robustified Models
5.2 Empirically Robustifying Simple Transformers
5.2.1 Regret Evaluation
5.2.2 TV-distance
References
6 Omitted Proofs
6.1 Proof of Lemma
6.2 Proof of Lemma
6.3 Proof of Lemma
6.4 Proof of
6.5 Proof of
6.6 Proof of
7 Transformer Robustification Construction
7.1 Transformer Preliminaries
7.2 Proof of
8 Generalization to Unknown Decision Problem
8.1 Setup and notation
8.2 V-shaped proper losses and discretization
8.3 Switching rule and algorithm
8.4 Technical Lemmas for V-shaped Decomposition
8.5 Proof of

Knowls

Knowl 1 — Robustification of Next-Token Prediction Models with Unbounded Context
theoretical result
Let $\Theta$ be a finite state/token alphabet, $A$ be a finite action set, and $U: A \times \Theta \to [-1, 1]$ be a known utility function. Let $\mathcal{D}_0 \in \Delta(\Theta^T)$ be an arbitrary distribution over state sequences of length $T$ , represented by a next-token prediction model $M_0$ where $M_0(\theta^{t-1}) \in \Delta(\Theta)$ gives the conditional distribution over the next state $\theta_t$ given prefix $\theta^{t-1} = (\theta_1, \dots, \theta_{t-1})$ .

For any parameter $\alpha > 0$ , there exists a robustified next-token prediction model $M$ inducing distribution $\mathcal{D} = \mathcal{D}(M)$ such that:
1. If a decision maker plays the quantal best response (QBR) mixed action $\pi_t = \text{QBR}(M(\theta^{t-1}), 1/\sqrt{T}) \in \Delta(A)$ at each round $t \in [T]$ , where $\pi_t(a) \propto \exp(\sqrt{T} \mathbb{E}_{\theta \sim M(\theta^{t-1})}[U(a, \theta)])$ , the worst-case external adversarial regret against any sequence of states $\boldsymbol{\theta} = (\theta_1, \dots, \theta_T) \in \Theta^T$ satisfies:
$\text{ExtReg}(\boldsymbol{\pi}, \boldsymbol{\theta}) = \max_{a^* \in A} \frac{1}{T} \sum_{t=1}^T \left[ U(a^*, \theta_t) - U(\pi_t, \theta_t) \right] = O\left( \frac{\log(|A| \cdot T) + \sqrt{(1+\alpha)\log T}}{\sqrt{T}} \right) = o(1).$
1. The total variation distance between the robustified distribution $\mathcal{D}$ and the original distribution $\mathcal{D}_0$ is bounded by:
$d_{\mathrm{TV}}(\mathcal{D}, \mathcal{D}_0) \le |A| T^{-\alpha}.$

Hence, sublinear worst-case adversarial regret can be achieved with negligible change to the original model's statistical distribution.
Knowl 2 — Robustification Procedure for Unbounded Context Next-Token Prediction Models
algorithm
The robustification procedure transforms a base next-token predictor $M_0$ into a low-regret next-token prediction model $M$ by monitoring the historical regret gap between the base model and a Polya urn model, switching permanently to the Polya urn model if the base model behaves out-of-distribution.
Input: Base next-token prediction model $M_0$ , observed prefix $\theta^{t-1} = (\theta_1, \dots, \theta_{t-1})$ , utility function $U: A \times \Theta \to [-1, 1]$ , sequence length $T$ , parameter $\alpha > 0$ .
Output: Predicted state distribution $M(\theta^{t-1}) \in \Delta(\Theta)$ .
for $s = 1$ to $t - 1$ do
     $\pi_s \leftarrow \text{QBR}(M_0(\theta^{s-1}), 1/\sqrt{T})$
     $\pi_{\text{Hedge}, s} \leftarrow \text{QBR}(M_{\text{Polya}}(\theta^{s-1}), 1/\sqrt{T})$
     $\text{Regret}_s \leftarrow \text{ExtReg}(\pi^{1:s}, \theta^{1:s})$
     $\text{Regret}_{\text{Hedge}, s} \leftarrow \text{ExtReg}(\pi_{\text{Hedge}}^{1:s}, \theta^{1:s})$
    if $\text{Regret}_s \ge \text{Regret}_{\text{Hedge}, s} + \frac{1}{\sqrt{T}} \log |A| + \sqrt{\frac{8(1+\alpha)\log T}{s}}$ then
        return $M_{\text{Polya}}(\theta^{t-1})$
    end if
end for
return $M_0(\theta^{t-1})$
Here, the Polya urn model $M_{\text{Polya}}$ is defined by:

$M_{\text{Polya}}(\theta \mid \theta^{s-1}) = \frac{1 + \sum_{i=1}^{s-1} \mathbb{I}[\theta_i = \theta]}{|\Theta| + (s - 1)}.$

The computational complexity to check the filtering condition across all prefixes of length $T$ is $O(T |A| |\Theta|)$ .
Knowl 3 — Adversarial Regret Minimization via Quantal Best Response to Polya Urn
theoretical result
Let $\Theta$ be a finite state space, $A$ be a finite action space, and $U: A \times \Theta \to [-1, 1]$ be a fixed utility function. Let $M_{\text{Polya}}$ be the Polya urn next-token prediction model defined at round $t \in [T]$ by:

$M_{\text{Polya}}(\theta \mid \theta^{t-1}) = \frac{1 + \sum_{s=1}^{t-1} \mathbb{I}[\theta_s = \theta]}{|\Theta| + (t - 1)}.$

If the decision maker chooses mixed actions via the quantal best response (QBR):

$\pi_t = \text{QBR}(M_{\text{Polya}}(\theta^{t-1}), \eta), \quad \text{where } \pi_t(a) \propto \exp\left( \frac{1}{\eta} \mathbb{E}_{\theta \sim M_{\text{Polya}}(\theta^{t-1})}[U(a, \theta)] \right),$

with temperature parameter $\eta = 1/\sqrt{T}$ , then for any adversarial sequence of states $\boldsymbol{\theta} = (\theta_1, \dots, \theta_T) \in \Theta^T$ , the external regret satisfies:

$\text{ExtReg}(\boldsymbol{\pi}, \boldsymbol{\theta}) = \max_{a^* \in A} \frac{1}{T} \sum_{t=1}^T \left[ U(a^*, \theta_t) - U(\pi_t, \theta_t) \right] = O\left( \frac{\log T + \log |A|}{\sqrt{T}} \right).$

This follows because $\pi_t$ corresponds to an exponential-weights (Hedge) update with time-varying learning rate $\lambda_t = \frac{\sqrt{T}}{|\Theta| + t - 1}$ applied to past realized utilities.
Knowl 4 — Impossibility of Robustification Under Identical Bounded Context Length
theoretical result
Let sequence length be $T$ , context window length be $L = T/2$ , action and state alphabets be binary $A = \Theta = \{0, 1\}$ , and utility function be $U(a, \theta) = \mathbb{I}[a = \theta]$ .

There exists an $L$ -bounded next-token prediction model $M_0$ (whose predictions at round $t > L$ depend only on $\theta_{(t-L):(t-1)}$ ), inducing distribution $\mathcal{D}_0 = \mathcal{D}(M_0)$ , such that for every other $L$ -bounded model $M$ (inducing distribution $\mathcal{D} = \mathcal{D}(M)$ ), at least one of the following two statements holds:
1. The distributions are bounded away in total variation distance:
$d_{\mathrm{TV}}(\mathcal{D}_0, \mathcal{D}) > \frac{1}{24}.$
1. There exists an adversarial sequence of states $\boldsymbol{\theta} \in \{0, 1\}^T$ such that playing quantal best responses $\pi_t = \text{QBR}(M(\theta^{t-1}), 1/\sqrt{L})$ incurs constant external regret:
$\text{ExtReg}(\boldsymbol{\pi}, \boldsymbol{\theta}) > \frac{1}{24}.$

This impossibility arises because two distinct $L$ -bounded Markov models generated via a binary de Bruijn sequence and its bitwise negation generate the same uniform marginal distribution over length- $L$ substrings, preventing an $L$ -bounded model from distinguishing in-distribution from out-of-distribution sequences.
Knowl 5 — Robustification of Bounded Context Models via Context Window Expansion
theoretical result
Let $M_0$ be an $L$ -bounded next-token prediction model over binary actions and states $|A| = |\Theta| = 2$ inducing distribution $\mathcal{D}_0 = \mathcal{D}(M_0)$ . Suppose the model is allowed an expanded context length $L' > L$ , with context gap $\Delta = L' - L$ .

Running the suffix-averaging robustification procedure (Algorithm 2) with parameter $\alpha > 0$ yields an $L'$ -bounded model $M$ inducing distribution $\mathcal{D} = \mathcal{D}(M)$ with the following guarantees:
1. For any adversarial state sequence $\boldsymbol{\theta} \in \Theta^T$ , playing $\pi_t = \text{QBR}(M(\theta^{t-1}), 1/\sqrt{\Delta})$ achieves worst-case external regret bounded by:
$\text{ExtReg}(\boldsymbol{\pi}, \boldsymbol{\theta}) \le \left(1 + \frac{\Delta}{T}\right) \left[ \frac{\sqrt{2}+1}{\sqrt{\Delta}} + \sqrt{\frac{8\log T + 8(\alpha+1)\log \Delta}{\Delta}} \right] = O\left( \frac{1}{\sqrt{L' - L}} \right).$
1. The total variation distance between $\mathcal{D}$ and $\mathcal{D}_0$ is bounded by:
$d_{\mathrm{TV}}(\mathcal{D}, \mathcal{D}_0) \le \Delta^{-\alpha} = (L' - L)^{-\alpha}.$

Thus, expanding the context window by $\Delta$ enables both statistical proximity and length-generalizing adversarial low regret.
Knowl 6 — Robustification Algorithm for Bounded Context Models with Expanded Context
algorithm
The algorithm robustifies an $L$ -bounded model $M_0$ by using an expanded context length $L' > L$ (with $\Delta = L' - L$ ) to evaluate $\Delta$ parallel copies of the unbounded robustification subroutine (Algorithm 1) over different suffix windows, averaging their quantal best responses.
Input: Base $L$ -bounded model $M_0$ , context length $L' > L$ , context gap $\Delta = L' - L$ , parameter $\alpha > 0$ , input sequence $\theta^{L'} = (\theta_1, \dots, \theta_{L'})$ .
Output: Predicted state distribution $M(\theta^{L'}) = \mu \in \Delta(\Theta)$ .
Run Algorithm 1 on $M_0$ with time horizon $\Delta$ to produce robustified model $M_\Delta$ .
for $m = L + 1$ to $L'$ do
$\mu_m \leftarrow M_\Delta(\theta^{m:L'})$ // output of $M_\Delta$ on suffix sequence $(\theta_m, \dots, \theta_{L'})$
end for
Choose $\mu \in \Delta(\Theta)$ such that:
$\text{QBR}(\mu, 1/\sqrt{\Delta}) = \frac{1}{\Delta} \sum_{m=L+1}^{L'} \text{QBR}(\mu_m, 1/\sqrt{\Delta})$
return $M(\theta^{L'}) = \mu$
For binary actions ( $|A| = 2$ ), the image of $\text{QBR}(\cdot, 1/\sqrt{\Delta})$ is convex, guaranteeing that a matching mixed strategy $\mu \in \Delta(\Theta)$ always exists.
Knowl 7 — Transformer Architecture Representation of Robustified Predictors
theoretical result
Suppose distribution $\mathcal{D}_0$ over sequences $\Theta^T$ is exactly computed by an autoregressive transformer $g_{M_0}$ with depth $L$ , attention heads $H$ , and embedding dimension $m$ (such that $g_{M_0}(\boldsymbol{\theta})_{t, i} = \mathbb{P}_{\mathcal{D}_0}[\theta_t = i \mid \theta^{t-1}]$ ). Suppose the utility function $U: A \times \Theta \to [-1, 1]$ is Lipschitz and representable by a fixed-width MLP independent of $T$ .

For any constant $c > 0$ , there exists an augmented transformer $g'$ with:
- Depth $L' = L + 4$ ,
- Attention heads $H' = O(|A|^2)$ ,
- Embedding dimension $m' = m + O(|A|^3 + |\Theta|)$ ,
which approximates the robustified predictor of Algorithm 1 within additive error $\delta \le T^{-c}$ . Specifically, for all $t \le T$ :
1. If there exists $s \le t - |A|$ such that $\text{Regret}_s \ge \text{Regret}_{\text{Hedge}, s} + \frac{1}{\sqrt{T}} \log |A| + \sqrt{\frac{8(1+\alpha)\log T}{s}} + \delta$ , then $g'(\boldsymbol{\theta})_t = M_{\text{Polya}}(\theta^{t-1})$ .
2. If for all $s \le t - |A|$ , $\text{Regret}_s < \text{Regret}_{\text{Hedge}, s} + \frac{1}{\sqrt{T}} \log |A| + \sqrt{\frac{8(1+\alpha)\log T}{s}} - \delta$ , then $g'(\boldsymbol{\theta})_t = M_0(\theta^{t-1}) = g_{M_0}(\boldsymbol{\theta})_t$ .
The 4 added layers implement: (1) Polya Urn rolling averages, (2) lookup of previous partial losses via position encodings, (3) parallel QBR softmax computation across actions, and (4) prefix regret thresholding and global OR switching.
Knowl 8 — Robustification for Unknown Decision Problems via V-Shaped Scoring Rules
theoretical result
In the binary state space setting $\Theta = \{0, 1\}$ , when the decision problem's utility function $U$ is unknown in advance, a predictor $M_0$ producing probabilities $p_t^0 = M_0(1 \mid \theta^{t-1})$ can be robustified using an $\varepsilon$ -grid of V-shaped proper scoring rules $\mathcal{L}_\varepsilon = \{\ell_v : v \in \mathcal{V}_\varepsilon\}$ , where $\mathcal{V}_\varepsilon = \{0, \varepsilon, 2\varepsilon, \dots, 1\}$ , $N_\varepsilon = |\mathcal{V}_\varepsilon| \le 1 + 1/\varepsilon$ , and $\ell_v(p) = -|p - v|$ .

Setting $\varepsilon = 1/T$ and confidence parameter $\delta = T^{-(1+\alpha)}$ , the algorithm monitors the empirical V-regret gap:

$\widehat{\Delta}_{t-1} = \max_{v \in \mathcal{V}_\varepsilon} \text{ExtReg}_{t-1}(\ell_v; p_{1:t-1}^0)$

and switches permanently to Polya Urn predictions $p_t^{\text{PU}}$ the first round $t$ where $\widehat{\Delta}_{t-1} > c \sqrt{\frac{\log(N_\varepsilon (t-1)^2 / \delta)}{t-1}}$ .

The resulting model $M$ guarantees that for any smooth best-responding decision maker:

$\text{ExtReg}_T(\boldsymbol{\pi}) = O\left( \frac{1}{\sqrt{T}} \log(|A| \cdot T) + \sqrt{\frac{(1+\alpha)\log T}{T}} \right)$

against any adversarial sequence, while maintaining $d_{\mathrm{TV}}(\mathcal{D}, \mathcal{D}_0) \le |A| T^{-\alpha}$ .
Knowl 9 — Linear Regret Lower Bound for Deterministic Best Responses to Next-Token Predictors
theoretical result
Let $M$ be any next-token prediction model over binary alphabet $\Theta = \{0, 1\}$ . Consider the binary state-matching task with action space $A = \{0, 1\}$ and utility function $U(a, \theta) = \mathbb{I}[a = \theta]$ .

If the decision maker employs the exact (deterministic) best response $\pi_t = \text{BR}(M(\theta^{t-1})) = \text{argmax}_{a \in \{0, 1\}} \mathbb{E}_{\theta \sim M(\theta^{t-1})}[U(a, \theta)]$ , there exists an adversarial sequence of states $\boldsymbol{\theta} \in \{0, 1\}^T$ that induces constant external regret:

$\text{ExtReg}(\boldsymbol{\pi}, \boldsymbol{\theta}) \ge \frac{1}{2} = \Omega(1).$

Specifically, an adversary setting $\theta_t = 1 - a_t$ forces cumulative learner utility $\sum_{t=1}^T U(a_t, \theta_t) = 0$ , while the majority action in hindsight achieves utility at least $T/2$ . This necessitates randomized or quantal best responses for adversarial regret minimization.

Knowl 10 — Empirical Regret and Total Variation Distance of Robustified Transformers

data/table

Decoder-only transformers (NanoDO: context $T=1024$ , embedding dimension 256, 4 heads, 3 layers, 1024 inner dimension) were trained on binary sequences under three configurations: BERNOULLI (non-robust, trained on $\text{Ber}(1/3)$ for $T/2$ steps then $\text{Ber}(2/3)$ for $T/2$ steps), POLYAURN (trained on Polya Urn sequences), and ROBUST_BERNOULLI (trained on BERNOULLI data supplemented with high-regret Polya Urn sequences with prefixes masked up to the regret threshold $\sqrt{1.5/t}$ ).

Across 8 ground truth distributions (static Bernoulli and periodic sinusoid drifts $\mathbb{P}[\theta_t = 1] = |\sin(\pi/6 + t\pi/\phi)|$ ), ROBUST_BERNOULLI matches the negative in-distribution regret of BERNOULLI (approx $-0.16$ ) while maintaining vanishing regret on out-of-distribution environments, unlike BERNOULLI which incurs high regret.

Full-sequence TV distance (Table 1) and average per-step next-token TV distance $d_{\text{NT}} = \mathbb{E}_{\boldsymbol{\theta} \sim \text{BERNOULLI}}[\frac{1}{T}\sum_{s=1}^T d_{\mathrm{TV}}(M_1(\cdot|\theta^s), M_2(\cdot|\theta^s))]$ (Table 2) between models (evaluated on 128 independent sequences with 95% confidence intervals) are:

Model Comparison	Full-Sequence $d_{\mathrm{TV}}$ vs $\text{BERNOULLI}_1$	Next-Token $d_{\text{NT}}$ vs $\text{BERNOULLI}_1$
$\text{BERNOULLI}_2$ (diff seed)	$0.4193 \pm 0.0232$	$0.0156$
$\text{ROBUST\_BERNOULLI}$	$0.7602 \pm 0.0267$	$0.0199 \pm 0.0001$
$\text{POLYAURN}$	$1.0000 \pm 0.0000$	$0.1529 \pm 0.0003$

ROBUST_BERNOULLI achieves next-token TV distance close to the random seed baseline ( $0.0199$ vs $0.0156$ ), while POLYAURN exhibits nearly an order of magnitude higher next-token TV distance ( $0.1529$ ).

Coverage note — Omitted only standard supporting technical lemmas (e.g., Azuma's inequality martingale concentration derivations, elementary regularized utility facts, and detailed individual ReLU gate definitions inside the transformer gadgets) as they are standard tools rather than novel standalone contributions.

References

1.E. Ben-porath. The complexity of computing a best response automaton in repeated games with mixed strategies. Games and Economic Behavior, 2(1):1–12, March 1990. doi: None. URL https://ideas.repec.org/a/eee/gamebe/v2y1990i1p1-12.html.
2.E. Candes and T. Tao. Decoding by linear programming, 2005. URL https://arxiv.org/abs/math/0502327.
3.L. Chen, K. Lu, A. Rajeswaran, K. Lee, A. Grover, M. Laskin, P. Abbeel, A. Srinivas, and I. Mordatch. Decision transformer: Reinforcement learning via sequence modeling, 2021. URL https://arxiv.org/abs/2106.01345.
4.Y. Freund and R. E. Schapire. A decision-theoretic generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 55(1):119–139, 1997.
5.L. Hu and Y. Wu. Predict to minimize swap regret for all payoff-bounded tasks. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 244–263. IEEE, 2024.
6.Kaggle. Two sigma: Using news to predict stock movements. Kaggle Competition, 2018. URL https://www.kaggle.com/c/two-sigma-financial-news. Competition host: Two Sigma. Accessed 2026-01-28.
7.B. Kleinberg, R. P. Leme, J. Schneider, and Y. Teng. U-calibration: Forecasting for an unknown agent. In The Thirty Sixth Annual Conference on Learning Theory, pages 5143–5145. PMLR, 2023.
8.A. Krishnamurthy, K. Harris, D. J. Foster, C. Zhang, and A. Slivkins. Can large language models explore in-context?, 2024. URL https://arxiv.org/abs/2403.15371.
9.E. Lehrer and E. Solan. Approachability with bounded memory. Games and Economic Behavior, 66(2):995–1004, July 2009. doi: None. URL https://ideas.repec.org/a/eee/gamebe/v66y2009i2p995-1004.html.
10.Y. Li, J. D. Hartline, L. Shan, and Y. Wu. Optimization of scoring rules. In Proceedings of the 23rd ACM Conference on Economics and Computation, pages 988–989, 2022.
11.P. J. Liu, R. Novak, J. Lee, M. Wortsman, L. Xiao, K. Everett, A. A. Alemi, M. Kurzeja, P. Marcenac, I. Gur, S. Kornblith, K. Xu, G. Elsayed, I. Fischer, J. Pennington, B. Adlam, and J.-S. Dickstein. Nanodo: A minimal transformer decoder-only language model implementation in JAX., 2024. URL http://github.com/google-deepmind/nanodo.
12.A. Marsden, E. Dogariu, N. Agarwal, X. Chen, D. Suo, and E. Hazan. Provable length generalization in sequence prediction via spectral filtering, 2024. URL https://arxiv.org/abs/2411.01035.
13.S. Mendelson, A. Pajor, and N. Tomczak-Jaegermann. Reconstruction and subgaussian operators in asymptotic geometric analysis. Geometric and Functional Analysis, 17:1248–1282, 11 2007. doi: 10.1007/s00039-007-0618-7.
14.A. Nie, Y. Su, B. Chang, J. N. Lee, E. H. Chi, Q. V. Le, and M. Chen. Evolve: Evaluating and optimizing llms for in-context exploration, 2025. URL https://arxiv.org/abs/2410.06238.
15.C. Park, X. Liu, A. Ozdaglar, and K. Zhang. Do llm agents have regret? a case study in online learning and games, 2025. URL https://arxiv.org/abs/2403.16843.
16.M. Piccione and A. Rubinstein. Finite automata play a repeated extensive game. Journal of Economic Theory, 61(1):160–168, 1993. ISSN 0022-0531. doi: https://doi.org/10.1006/jeth.1993.1063. URL https://www.sciencedirect.com/science/article/pii/S002205318371063X.
17.A. Rubinstein. Finite automata play the repeated prisoner’s dilemma. Journal of Economic Theory, 39(1):83–96, June 1986. doi: None. URL https://ideas.repec.org/a/eee/jetheo/v39y1986i1p83-96.html.
18.D. Salinas, V. Flunkert, J. Gasthaus, and T. Januschowski. Deepar: Probabilistic forecasting with autoregressive recurrent networks. International journal of forecasting, 36(3):1181–1191, 2020.
19.C. Sanford, D. J. Hsu, and M. Telgarsky. Representational strengths and limitations of transformers. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 36677–36707. Curran Associates, Inc., 2023.
20.C. Sanford, D. Hsu, and M. Telgarsky. Transformers, parallel computation, and logarithmic depth. In R. Salakhutdinov, Z. Kolter, K. Heller, A. Weller, N. Oliver, J. Scarlett, and F. Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 43276–43327. PMLR, 21–27 Jul 2024. URL https://proceedings.mlr.press/v235/sanford24a.html.
21.J. Schneider and K. Vodrahalli. Online learning with bounded recall. In Proceedings of the 41st International Conference on Machine Learning, pages 43791–43803, 2024.
22.A. Vallinder and E. Hughes. Cultural evolution of cooperation among llm agents, 2024. URL https://arxiv.org/abs/2412.10270.
23.Z. Zhang, S. Zohren, and S. Roberts. Deeplob: Deep convolutional neural networks for limit order books. IEEE Transactions on Signal Processing, 67(11):3001–3012, 2019.

Citation

MLA

Mohri, M., et al. “Next-Token Prediction and Regret Minimization”. arXiv, 2026, http://arxiv.org/abs/2603.28499v1.

APA

Mohri, M., Sanford, C., Schneider, J., Vodrahalli, K., & Wu, Y. (2026). Next-Token Prediction and Regret Minimization. arXiv. http://arxiv.org/abs/2603.28499v1

Chicago

Mohri, M., C. Sanford, J. Schneider, K. Vodrahalli, and Y. Wu. 2026. “Next-Token Prediction and Regret Minimization”. arXiv. http://arxiv.org/abs/2603.28499v1.

Harvard

Mohri, M. et al. (2026) “Next-Token Prediction and Regret Minimization”, arXiv [Preprint]. Available at: http://arxiv.org/abs/2603.28499v1.

Vancouver

1. Mohri M, Sanford C, Schneider J, Vodrahalli K, Wu Y (2026) Next-Token Prediction and Regret Minimization. arXiv

BibTeX

@article{mohri2026next,
  title = {Next-Token Prediction and Regret Minimization},
  author = {Mohri, Mehryar and Sanford, Clayton and Schneider, Jon and Vodrahalli, Kiran and Wu, Yifan},
  year = {2026},
  journal = {arXiv},
  url = {http://arxiv.org/abs/2603.28499v1},
  eprint = {2603.28499}
}

Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Next-Token Prediction and Regret Minimization

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Robustification of Next-Token Prediction Models with Unbounded Context

Knowl 2 — Robustification Procedure for Unbounded Context Next-Token Prediction Models

Knowl 3 — Adversarial Regret Minimization via Quantal Best Response to Polya Urn

Knowl 4 — Impossibility of Robustification Under Identical Bounded Context Length

Knowl 5 — Robustification of Bounded Context Models via Context Window Expansion

Knowl 6 — Robustification Algorithm for Bounded Context Models with Expanded Context

Knowl 7 — Transformer Architecture Representation of Robustified Predictors

Knowl 8 — Robustification for Unknown Decision Problems via V-Shaped Scoring Rules

Knowl 9 — Linear Regret Lower Bound for Deterministic Best Responses to Next-Token Predictors

Knowl 10 — Empirical Regret and Total Variation Distance of Robustified Transformers

References

Citation

BibTeX

Access the Paper