Decoding Game: On Minimax Optimality of Heuristic Text Generation Strategies

## Abstract

Abstract Decoding strategies play a pivotal role in text generation for modern language models, yet a puzzling gap divides theory and practice. Surprisingly, strategies that should intuitively be optimal, such as Maximum a Posteriori (MAP), often perform poorly in practice. Meanwhile, popular heuristic approaches like Top- k 𝑘 k italic_k and Nucleus sampling, which employ truncation and normalization of the conditional next-token probabilities, have achieved great empirical success but lack theoretical justifications. In this paper, we propose Decoding Game, a comprehensive theoretical framework which reimagines text generation as a two-player zero-sum game between Strategist, who seeks to produce text credible in the true distribution, and Nature, who distorts the true distribution adversarially. After discussing the decomposibility of multi-step generation, we derive the optimal strategy in closed form for one-step Decoding Game. It is shown that the adversarial Nature imposes an implicit regularization on likelihood maximization, and truncation-normalization methods are first-order approximations to the optimal strategy under this regularization. Additionally, by generalizing the objective and parameters of Decoding Game, near-optimal strategies encompass diverse methods such as greedy search, temperature scaling, and hybrids thereof. Numerical experiments are conducted to complement our theoretical analysis.

## 1 Introduction

Decoding strategies underpin the mechanism of generating a text sequence from a given language model, and therefore become an essential component of modern Large Language Models (OpenAI, ). Specifically, given an autoregressive language model $\widehat{\mathbb{P}}$ which encodes the conditional next-token probability $\widehat{\mathbb{P}}(X_{t}|X_{<t})$, one aims to generate a high-quality sequence $(X_{1},\dots,X_{T})$ by some strategy based on $\widehat{\mathbb{P}}$. Perhaps one of the most straightforward strategies is Maximum a Posteriori (MAP), looking for the most probable sequence, i.e., the one with the maximum predicted likelihood $\widehat{\mathbb{P}}(X_{1},\dots,X_{T})$. Considering the computation cost of an exact MAP, one would naturally turn to some heuristic surrogates such as greedy search and beam search (Graves, ; Sutskever et al., ).

Counter-intuitively, numerous empirical studies have reported that such likelihood maximization strategies usually lead to low-quality, degenerate texts, even with heavily trained state-of-the-art language models (Hashimoto et al., ; Holtzman et al., ). Instead, sampling methods that randomly select the next token are observed to yield better outputs. Popular strategies include Top-$k$ sampling (Fan et al., ), Nucleus (Top-$p$) sampling (Holtzman et al., ), $\eta$ sampling (Hewitt et al., ), and Mirostat sampling (Basu et al., ), among others. They follow a truncation-normalization design, sampling the next token from a truncated distribution by removing the tail probabilities and rescaling the remaining probabilities by a normalizing constant. Some other methods (Finlayson et al., ; Meister et al., ) also rely on truncation but may discard high-probability tokens besides the tail; see Section 2 for details. Formally, if $(\widehat{p}_{1},\dots,\widehat{p}_{d})$ is the vector of the predicted probability of all candidate next-tokens $\{1,\dots,d\}$, these methods decide an index set $\mathcal{S}$ and sample a token $i$ with probability

$$ $q_{i}\propto\widehat{p}_{i}\mathds{1}_{(i\in\mathcal{S})}.$ $$

Depending on the desired effect, the truncation threshold or $\mathcal{S}$ may be determined from various quantities like the truncated vocabulary size, truncated probability weight, entropy, and so on.

Regarding decoding strategies, there is an interesting dichotomy between theory and practice. From a statistical perspective, From a statistical perspective, likelihood maximization approaches are desired to succeed by seeking or approximating the posterior mode of $\widehat{\mathbb{P}}$, but usually underperform in practice on language tasks. On the contrary, despite their empirical superiority over likelihood maximization, the design of randomized sampling strategies remains mostly heuristic and the theory behind is poorly understood. To resolve this dichotomy, this paper aims to propose a comprehensive theoretical framework of text generation, where heuristic sampling strategies, rather than likelihood maximization, are proved to be (near-)optimal.

Now, we shall introduce the motivations behind our framework before presenting it formally.

### 1.1 Motivation and our framework

First thought. At first sight, a statistician may naturally relate these truncation methods with the concept of sparsity and regularization, and further attempt to handcraft a constrained or penalized optimization problem where they are optimal strategies. This is easier than it may sound: for example, we can design a distance metric so that Top-$k$ sampling is the best sparse approximation to the original distribution according to this metric, such as $\ell_{0}$ distance that directly controls sparsity. The major flaw of such approaches is that their objectives and constraints mostly come from non-principled, reverse engineering and lack statistical motivations. Therefore, they may not be able to provide theoretical insight into questions like why sparse solutions are favored, and why we should adopt a specific regularization term and distance metric.

Second thought. Let us restart from the most significant observation that likelihood-maximization approaches fail in practice. What does this imply? If $\mathbb{P}$ is the true distribution of natural language, it is reasonable to expect that the trained language model $\widehat{\mathbb{P}}$ is away from $\mathbb{P}$. This makes $\widehat{\mathbb{P}}$-likelihood an unreliable criterion of a generated text, and hence leads to the failure of likelihood maximization. On the other hand, the appropriate criterion a strategy would like to maximize is the $\mathbb{P}$-likelihood of a generated sequence.

However, note that for generality, we restrict ourselves from assuming too many structures on the true distribution $\mathbb{P}$, except for its bounded deviation from $\widehat{\mathbb{P}}$. This “model-free” setup brings an adversarial nature to text generation: in the worst case, $\mathbb{P}$ can try its best to degrade the quality of our generated text within its distance budget.

Decoding Game. These ideas lead to our proposal, Decoding Game, a two-player zero-sum game between Strategist (S) and Nature (N). In this game, player S chooses a (randomized) decoding strategy to generate a text sequence that, in expectation, achieves good log-likelihood in the true distribution. On the other hand, player N is always able to shift the true distribution adversarially to reduce the text quality. Knowing the decoding strategy beforehand, player N chooses the worst-case true distribution $\mathbb{P}$. Formally, a $T$-step Decoding Game is represented by

$$ $\displaystyle\max_{\phantom{\widehat{\mathbb{P}}}\mathbb{Q}\phantom{\widehat{ \mathbb{P}}}}\min_{\mathbb{P}\in N(\widehat{\mathbb{P}})}\mathbb{E}_{\mathbb{Q }}\log\mathbb{P}(X_{1},\dots,X_{T}|X_{0}),$ $$

where, conditioned on a given prompt $X_{0}$, $\mathbb{Q}$ is the probability measure on $(X_{1},\dots,X_{T})$ induced by the decoding strategy of player S, and $N(\widehat{\mathbb{P}})$ refers to a neighborhood of $\widehat{\mathbb{P}}$. The objective of the game is the true log-likelihood of a length-$T$ sequence generated from strategy $\mathbb{Q}$, in expectation.

If there is no adversary ($\mathbb{P}=\widehat{\mathbb{P}}$ always holds), then the game reduces to $\widehat{\mathbb{P}}$-likelihood maximization, and naive MAP is exactly the solution. However, when an adversary is present, MAP becomes sub-optimal and the game invites more interesting consequences.

### 1.2 Contribution

In the rest of this paper, we conduct in-depth investigations into Decoding Game. The main results include:

- •
Decomposibility of multi-step Decoding Game. In Section 3, we identify a recursive structure of the multi-step Decoding Game, and argue the computational intractability of obtaining a global solution in modern LLMs. Instead, we construct an inductive decision process that involves solving an one-step Decoding Game at each timestep.
- •
Optimality of heuristic strategies under implicit regularization. Under total variation (TV) distance, we provide closed-form solutions to the one-step Decoding Game for both players. In Section 4.1, we show that the optimal strategy of player N imposes an $\ell_{\infty}$-type regularization on the log-likelihood. As a result, truncation-normalization sampling strategies emerge as first-order approximations to the optimal strategy of player S; see Section 4.2.
- •
Generalizability of the framework. In Section 4.3, we further discuss the consequences of using different objectives for Decoding Game, recovering other types of strategies such as temperature-based methods. The exclusive advantage of log-likelihood, in contrast to other objectives, is also highlighted under the general framework.
- •
Empirical evidence. Building on the general theory, in Section 5, we propose Game sampling (Algorithm 1) and empirically evaluate its performance in open-ended text generation with GPT-2 models. The experiments suggest that Game sampling is able to outperform other strategies, which corroborates our optimality results.

Decoding Game provides a comprehensive theoretical framework that rigorously establishes optimality results for heuristic sampling strategies. It largely differs from existing interpretations which, to different extents, provide some theoretical viewpoints as partial justifications for their design. We will briefly review them in Section 2.

At the same time, we believe that the statistically meaningful motivations and minimal assumptions behind Decoding Game open up its potential for future research on decoding strategies; see discussions in Section 6.

## 2 Related works

### 2.1 Existing theoretical interpretations

Theoretical explanations for decoding methods have been very sparse and existing works are relatively limited. Known perspectives presented in literature include (1) overestimation of token probabilities, (2) surprisal and perplexity of generated text, and (3) implicit regularization on MAP.

Following the long-held intuition (Holtzman et al., ) that language models tend to assign excessive probability to the unreliable tail, Finlayson et al. () explained truncation as a remedy for this problem, showing that it can correctly discard the tokens out of the support of the true distribution when overestimation is upper-bounded. They further credited overestimation to the Softmax Bottleneck (Yang et al., ) brought by the language model architecture, motivating a new truncation mechanism that may remove high-probability tokens besides the tail. However, this structural assumption may not well account for the broadness of the source of overestimation. Additionally, it is unclear why rescaling all the remaining probabilities by the same constant is considered the best approach after truncation.

A similar idea of identifying the correct support has also driven prior works such as Hewitt et al. () and Meister et al. (). Hewitt et al. () modeled the predictions as a mixture of true distribution and uniform-like smoothing distribution, and viewed truncation as a way to desmooth the output. Meister et al. () proposed to compute the support that better aligns with the information-theoretic metrics of human text measured by token surprisal and entropy, under assumptions on the behavior of human speakers. In this method, high-probabilty tokens may be discarded as well.

Basu et al. () theoretically derived the perplexity of various sampling methods under the statistical assumption that next-token probabilities follow a Zipf distribution, comparing how the hyperpamameter of each method influences the order of perplexity. This particular Zipfian assumption may not fully capture the complicated probability distributions encoded by modern language models.

An earlier work (Meister et al., ) attempted to explain heuristic methods such as beam search as an implicit regularization imposed on MAP. However, the design of regularization term seems to lack statistical motivations. They also suggest a qualitative relationship between the regularization term and the uniformity of surprisal of generated sequences, but the detailed mechanism is not well understood mathematically.

Overall, each of them motivates the design of heuristic decoding methods to a certain extent, but to the best of our knowledge, we are not aware of any comprehensive theoretical framework that establishes optimality results.

### 2.2 Text generation as decision making

Another line of work, though not directly working on the theory of heuristic decoding schemes, views the problem of text generation as optimizing the policy of a decision-making agent working in an environment with or without adversary. This perspective resonates with our rationale behind the Decoding Game. For example, Jacob et al. () proposed a game between a generation strategy and a text quality discriminator, and empirically demonstrated the advantage of the decoding strategy at the Nash equilibrium of this game in multiple tasks. Other recent works such as Snell et al. (); Kim et al. (); Mudgal et al. () modeled next-token generation as (token-level) Markov decision processes, and applied reinforcement learning techniques for controlled decoding.

### 2.3 Robust optimization and regularization

Our framework also draws a connection to robust optimization (Ben-Tal et al., ), which aims to find solutions with stable performance under data uncertainty or perturbations. Given the adversarial nature of uncertainty, robust optimization is typically formulated as a minimax problem that seek the best response to the worst-case data realizations. Interestingly, while the sparsity brought by truncation sampling can be seen as regularization, it is known that regularization and robustness are strongly correlated in various machine learning problems (Derman et al., ; Shaham et al., ; Bertsimas et al., ), as solving an optimization problem with regularization is equivalent to solving its non-regularized robust counterpart. The theory developed in this paper also confirms such an equivalence between robustness and regularization.

## 3 Formulation

### 3.1 Basic notations

Throughout, we use boldface letters to represent vectors and vector-valued mappings, and use blackboard bold letters to represent probability measures and expectations. For a sequence $(x_{0},x_{1},\dots,x_{T})$, we define $x_{<t}=(x_{0},\dots,x_{t-1})$. For a vector $\bm{a}=(a_{1},\dots,a_{d})$, $\bm{a}_{1:i}=(a_{1},\dots,a_{i})$ is the vector extracting its first $i$ components. The $\ell_{p}$ norm ($p\geq 1$) of $\bm{a}$ is defined as $\left\|{\bm{a}}\right\|_{p}=(\sum_{i=1}^{d}|a_{i}|^{p})^{1/p}$, with $\ell_{\infty}$ norm $\left\|{\bm{a}}\right\|_{\infty}=\max_{i\leq d}|a_{i}|$. The total variation (TV) distance between two probability vectors $\bm{p},\bm{q}$ is defined as $d_{\text{TV}}(\bm{p},\bm{q})=\frac{1}{2}\left\|{\bm{p}-\bm{q}}\right\|_{1}$. For a function $f:\mathbb{R}\to\mathbb{R}$, $f(\bm{a})$ represents the elementwise application of $f$ to the vector $\bm{a}$, and $\bm{a}/\bm{b}$ represents the elementwise division of $\bm{a}$ by $\bm{b}$. For a finite set $\mathcal{V}$, $\Delta(\mathcal{V})$ denotes the probability simplex of dimension $|\mathcal{V}|$, and $\mathcal{V}^{t}$ denotes the Cartesian product $\mathcal{V}\times...\times\mathcal{V}$ ($t$ times). We always assume that optimization variables have to satisfy probability constraints (e.g. lying in the probability simplex, or the space of probability measures), and will not specify them explicitly for conciseness.

### 3.2 Probability structure of text generation

Suppose $\mathcal{V}=\{1,2,\dots,d\}$ is the vocabulary of all $d$ tokens, and we are interested in generating $T$ tokens beginning with the prescribed context $X_{0}=x_{0}=(\text{prompt},\left<{\textsc{bos}}\right>)$. For a random variable sequence $(X_{1},\dots,X_{T})$ taking values in $\mathcal{V}$, its joint law under a measure $\mathbb{Q}$ can be decomposed into a collection of vector-valued mappings based on conditional probability rules. Specifically, for any $t\leq T$, let $\bm{q}_{t}:\mathcal{V}^{t-1}\to\Delta(\mathcal{V})$ that maps a length-$(t-1)$ sequence $x_{<t}$ to the vector $\bm{q}_{t}(x_{<t})$ describing next-token probabilities, which is defined elementwise by

$$ $\displaystyle\bm{q}_{t}(x_{<t})_{x_{t}}=\mathbb{Q}(X_{t}=x_{t}|X_{<t}=x_{<t}), \quad\forall x_{<t}\in\mathcal{V}^{t-1}.$ $$

Note that the subscript $x_{t}$ refers to the $x_{t}$-th coordinate of the vector, and specially $x_{<1}=x_{0}$. Then, the vector-valued mappings $\bm{q}_{1},\dots,\bm{q}_{T}$ constitute an exact representation of $\mathbb{Q}$, since for any $(x_{1},\dots,x_{T})\in\mathcal{V}^{T}$,

$$ $\displaystyle\mathbb{Q}(X_{1}=x_{1},\dots,X_{T}=x_{T}|X_{0}=x_{0})=\bm{q}_{1}( x_{<1})_{x_{1}}\bm{q}_{2}(x_{<2})_{x_{2}}\dots\bm{q}_{T}(x_{<T})_{x_{T}}.$ $$

Similarly, for $t<T$, $\bm{q}_{1},\dots,\bm{q}_{t}$ represents the marginal law $\mathbb{Q}(X_{1},\dots,X_{t}|X_{0})$.

Determining such a mapping $\bm{q}_{t}:\mathcal{V}^{t-1}\to\Delta(\mathcal{V})$ is equivalent to assigning a probability vector to each $\bm{q}_{t}(x_{<t})$ for each $x_{<t}\in\mathcal{V}^{t-1}$. From a graph-theoretic perspective, by designating all the mappings, we are assigning probability weights to all the edges of a uniform $d$-aray tree of depth $T$.

From now on, we use the notation $\mathbb{Q}$ and $(\bm{q}_{1},\dots,\bm{q}_{T})$ interchangeably, and likewise for other probability measures such as $\mathbb{P}\leftrightarrow(\bm{p}_{1},\dots,\bm{p}_{T})$ and $\widehat{\mathbb{P}}\leftrightarrow(\widehat{\bm{p}}_{1},\dots,\widehat{\bm{p}
}_{T})$.

### 3.3 Multi-step Decoding Game

We describe the $T$-step Decoding Game in full detail. Suppose the natural language follows a true distribution $\mathbb{P}$. Upon training, we obtain a language model $\widehat{\mathbb{P}}$ that approximates the true $\mathbb{P}$. Beginning with a prescribed context $X_{0}=(\text{prompt},\left<{\textsc{bos}}\right>)$, we generate a sequence $(X_{1},\dots,X_{T})$ with a possibly randomized decoding strategy, which is represented by another measure $\mathbb{Q}$ such that next tokens are selected with probability $\mathbb{Q}(X_{t}|X_{<t})$. We can then evaluate the quality of the generated sequence by testing whether the true distribution $\mathbb{P}$ is also likely to yield such a sequence. Specifically, for a typical sequence generated from $\mathbb{Q}$, we use its log-likelihood in $\mathbb{P}$-measure as the criterion

$$ $\displaystyle\mathcal{L}^{T}(\mathbb{Q},\mathbb{P})$ $\displaystyle=\mathbb{E}_{\mathbb{Q}}\log\mathbb{P}(X_{1},\dots,X_{T}|X_{0}),$ $$

which is also the negative cross-entropy between $\mathbb{Q}$ and $\mathbb{P}$ when viewed as distributions on $\mathcal{V}^{T}$.

The $T$-step Decoding Game is a two-player zero-sum game on this criterion between Strategist (S) and Nature (N), where player S chooses $\mathbb{Q}$ (by choosing a decoding strategy) to maximize the criterion of the generation, while player N chooses $\mathbb{P}$ within a neighborhood of $\widehat{\mathbb{P}}$ to minimize it. This gives rise to the following formulation:

$$ $\displaystyle\max_{\phantom{\widehat{\mathbb{P}}}\mathbb{Q}\phantom{\widehat{ \mathbb{P}}}}\min_{\mathbb{P}\in N(\widehat{\mathbb{P}})}\mathcal{L}^{T}( \mathbb{Q},\mathbb{P})=\max_{\phantom{\widehat{\mathbb{P}}}\mathbb{Q}\phantom{ \widehat{\mathbb{P}}}}\min_{\mathbb{P}\in N(\widehat{\mathbb{P}})}\mathbb{E}_{ \mathbb{Q}}\log\mathbb{P}(X_{1},\dots,X_{T}|X_{0}).$ (MDG) $$

We define $N(\widehat{\mathbb{P}})$ to be $\widehat{\mathbb{P}}$ $\{\mathbb{P}:d(\mathbb{P},\widehat{\mathbb{P}})\leq\epsilon\}$, the $\epsilon$-ball around $\widehat{\mathbb{P}}$ in the sense of the following TV-sup norm:(^1^11This can also be thought of as one-half of the $(1,\infty)$ mixed norm of the matrix concatinating all the probability vectors as its columns, which is of dimension $d\times\sum_{t=1}^{T}d^{t-1}$.)

$$ $\displaystyle d(\mathbb{P},\widehat{\mathbb{P}})=\|{\mathbb{P}-\widehat{ \mathbb{P}}}\|_{\text{TV},\infty}\coloneq\max\{d_{\text{TV}}(\bm{p}_{t}(x_{<t} ),\widehat{\bm{p}}_{t}(x_{<t})):x_{<t}\in\mathcal{V}^{t-1},t\leq T\}.$ $$

Likewise, we can define the distance between two mappings

$$ $d(\bm{p}_{t},\widehat{\bm{p}}_{t})=\left\|{\bm{p}_{t}-\widehat{\bm{p}}_{t}} \right\|_{\text{TV},\infty}\coloneq\max\{d_{\text{TV}}(\bm{p}_{t}(x_{<t}), \widehat{\bm{p}}_{t}(x_{<t})):x_{<t}\in\mathcal{V}^{t-1}\}.$ $$

Then immediately, $N(\widehat{\mathbb{P}})$ is a direct product of $\epsilon$-balls around $\widehat{\bm{p}}_{t}$, namely

$$ $\displaystyle N(\widehat{\mathbb{P}})=N(\widehat{\bm{p}}_{1})\times N(\widehat {\bm{p}}_{2})\times\dots\times N(\widehat{\bm{p}}_{T}),\quad N(\widehat{\bm{p} }_{t})=\{\bm{p}_{t}:d(\bm{p}_{t},\widehat{\bm{p}}_{t})\leq\epsilon\}.$ (1) $$

Based on the vector-valued mapping notations, we can recast the original game (MDG) as

$$ $\displaystyle\max_{\phantom{\widehat{\mathbb{P}}}\mathbb{Q}\phantom{\widehat{ \mathbb{P}}}}\min_{\mathbb{P}\in N(\widehat{\mathbb{P}})}\mathbb{E}_{\mathbb{Q }}\log\mathbb{P}(X_{1},\dots,X_{T}|X_{0})=\max_{\phantom{\widehat{\mathbb{P}}} \mathbb{Q}\phantom{\widehat{\mathbb{P}}}}\min_{\mathbb{P}\in N(\widehat{ \mathbb{P}})}\sum_{t=1}^{T}\mathbb{E}_{\mathbb{Q}}\log\mathbb{P}(X_{t}|X_{<t})$ $\displaystyle\qquad=\max_{\phantom{\widehat{\mathbb{P}}}\mathbb{Q}\phantom{ \widehat{\mathbb{P}}}}\min_{\mathbb{P}\in N(\widehat{\mathbb{P}})}\sum_{t=1}^{ T}\mathbb{E}_{\mathbb{Q}}[\mathbb{E}_{\mathbb{Q}}[\log\mathbb{P}(X_{t}|X_{<t}) |X_{<t}]]$ $\displaystyle\qquad=\max_{\bm{q}_{1},\dots,\bm{q}_{T}}\;\min_{\bm{p}_{1}\in N( \widehat{\bm{p}}_{1}),\dots,\bm{p}_{T}\in N(\widehat{\bm{p}}_{1})}\sum_{t=1}^{ T}\mathbb{E}_{\bm{q}_{1},\dots,\bm{q}_{t-1}}\bm{q}_{t}(X_{<t})^{\top}\log\bm{p }_{t}(X_{<t})$ (2) $\displaystyle\qquad=\max_{\bm{q}_{1},\dots,\bm{q}_{T}}\sum_{t=1}^{T}\mathbb{E} _{\bm{q}_{1},\dots,\bm{q}_{t-1}}\min_{\bm{p}_{t}\in N(\widehat{\bm{p}}_{t})} \bm{q}_{t}(X_{<t})^{\top}\log\bm{p}_{t}(X_{<t}).$ (3) $$

Here, (2) is due to the neighborhood definition in (1), and (3) uses the fact that the minimization problem is inherently separable in each $\bm{p}_{t}$.

### 3.4 Reduction to one-step Decoding Game

Directly solving (MDG) or (3) is computationally intractable. Theoretically, one can exploit the recursive structure in (3) and apply dynamic programming, but the scale of the problem grows as $\Omega(d^{T})$, and such an approach would take $\mathrm{poly}(d^{T})$ time. Considering the computational cost of working on a modern LLM, in this paper we turn to local solutions that do not probe into the global structure of the problem.

Technically, the hardness of (3) lies in the fact that the problem is non-separable in $\bm{q}_{t}$: the expectation intertwines $\bm{q}_{1},\dots,\bm{q}_{t-1}$ with $\bm{q}_{t}$. To avoid this problem, instead of globally solving it beforehand, we can consider a sequential decision process that builds up $\bm{q}_{t}$ step by step. Such a decision process $(\widetilde{\bm{q}}_{1},..,\widetilde{\bm{q}}_{T})$ is inductively given by a locally optimal mechanism

$$ $\displaystyle\widetilde{\bm{q}}_{t}$ $\displaystyle=\operatorname*{argmax}_{\bm{q}_{t}}\sum_{s=1}^{t}\mathbb{E}_{ \widetilde{\bm{q}}_{1},\dots,\widetilde{\bm{q}}_{s-1}}\min_{\bm{p}_{s}\in N( \widehat{\bm{p}}_{s})}\bm{q}_{s}(X_{<s})^{\top}\log\bm{p}_{s}(X_{<s}),$ $$

which leads to

$$ $\displaystyle\widetilde{\bm{q}}_{t}(x_{<t})$ $\displaystyle=\operatorname*{argmax}_{\bm{q}_{t}(x_{<t})}\min_{\bm{p}_{t}\in N (\widehat{\bm{p}}_{t})}\bm{q}_{t}(x_{<t})^{\top}\log\bm{p}_{t}(x_{<t})\quad \forall x_{<t}\in\mathcal{V}^{t-1},$ (4) $$

as $\widetilde{\bm{q}}_{1},\dots,\widetilde{\bm{q}}_{t-1}$ have been fixed. It turns out that such a mechanism already provides the optimal worst-case performance over all decision processes that do not exploit future information of $\widehat{\mathbb{P}}$.

###### Proposition 3.1 .

Given arbitrary $\widehat{\mathbb{P}}$ from the space of probability measures on $\mathcal{V}^{T}$, let $\mathbb{Q}=\mathbb{Q}(\widehat{\mathbb{P}})$ be any strategy of player S induced by some no-foresight decision process $(\bm{q}_{1}(\widehat{\mathbb{P}}),...,\bm{q}_{T}(\widehat{\mathbb{P}}))$, or equivalently, satisfying $\bm{q}_{t}(\widehat{\mathbb{P}})=\bm{q}_{t}(\widehat{\bm{p}}_{1},...,\widehat{
\bm{p}}_{t})$ for all $t\leq T$. Moreover, let $\mathbb{P}^{*}=\mathbb{P}^{*}(\widehat{\mathbb{P}},\mathbb{Q})$ be the optimal strategy of player N against $\mathbb{Q}$. If $\widetilde{\mathbb{Q}}=\widetilde{\mathbb{Q}}(\widehat{\mathbb{P}})$ is the strategy induced by $\eqref{eq:reduction-1}$, and $\epsilon<\|\widehat{\bm{p}}_{t}(x_{<t})\|_{\infty}$ for all $t\leq T$ and $x_{<t}\in\mathcal{V}^{t-1}$, then it holds that

$$ $\displaystyle\inf_{\widehat{\mathbb{P}}}\mathcal{L}^{T}(\widetilde{\mathbb{Q}} ,\mathbb{P}^{*})\geq\inf_{\widehat{\mathbb{P}}}\mathcal{L}^{T}(\mathbb{Q}, \mathbb{P}^{*}).$ $$

Now, the problem boils down to optimizing the imminent one-step reward of the game at time $t$. Equation (4) represents a collection of independent one-step Decoding Games between $d$-dimensional probability vectors, taking the general form

$$ $\displaystyle\max_{\phantom{\widehat{\bm{p}}}\bm{q}\phantom{\widehat{\bm{p}}}} \min_{\bm{p}:d_{\text{TV}}(\bm{p},\widehat{\bm{p}})\leq\epsilon}\bm{q}^{\top} \log\bm{p}$ (ODG) $$

for each conditional next-token probability vector $\widehat{\bm{p}}$ taking place in $\widehat{\mathbb{P}}$. In what follows, we will be devoted to the one-step game for further analysis.

###### Proposition 3.1 .

## 4 Theoretical analysis

In this section, we study the optimal strategies for both $\bm{p}$ and $\bm{q}$ in (ODG). We will show that the optimal $\bm{q}$ imposes an $\ell_{\infty}$-type regularization to likelihood maximization, and the optimal $\bm{p}$ solving the regularized maximization yields truncation-normalization sampling methods. Finally, we extend our analysis from log-likelihood to a general type of objectives, which recovers other heuristic methods and also highlights an exclusive advantage of log-likelihood.

For (ODG), we make the following assumptions.

###### Assumption 4.1 .

The probabilities are strictly positive and, without loss of generality, sorted in decreasing order, i.e., $\widehat{p}_{1}\geq\widehat{p}_{2}\geq\dots\geq\widehat{p}_{d}>0$.

###### Assumption 4.2 .

The distance budget $\epsilon$ satisfies $\widehat{p}_{d}\leq\epsilon<\widehat{p}_{1}$.

###### Assumption 4.1 .

###### Assumption 4.2 .

### 4.1 p 𝑝 p italic_p -strategy: implicit regularization

For a given $\bm{q}$, we have the following characterization for the optimal strategy of $\bm{p}$.

###### Theorem 4.3 .

Under Assumption 4.1 and 4.2, let $\hat{\imath}=\max\{i:\widehat{p}_{i}>\epsilon\}$. Define $\widehat{\bm{w}}\in\mathbb{R}^{\hat{\imath}}$ elementwise by $\widehat{w}_{i}=\frac{\epsilon}{\log\widehat{p}_{i}/(\widehat{p}_{i}-\epsilon)}$. Then, for a given $\bm{q}$, the optimal $\widetilde{\bm{p}}$ for (ODG) satisfies

$$ $\displaystyle\bm{q}^{\top}\log\widetilde{\bm{p}}=\min_{\bm{p}:d_{\text{TV}}( \bm{p},\widehat{\bm{p}})\leq\epsilon}\bm{q}^{\top}\log\bm{p}=\begin{cases}\bm{ q}^{\top}\log\widehat{\bm{p}}-\epsilon\left\|{\bm{q}_{1:\hat{\imath}}/\widehat {\bm{w}}}\right\|_{\infty},&\text{ if }q_{i}=0,\;\forall i>\hat{\imath};\\ -\infty,&\text{ otherwise}.\end{cases}$ $$

We give two remarks on Theorem 4.3. First, due to the fact that $\lim_{x\downarrow 0}\log(x)=-\infty$, any $\bm{q}$ possessing a non-zero tail in the index set $\{i:\widehat{p}_{i}\leq\epsilon\}$ will lead to a $-\infty$ objective value, because setting the corresponding $p_{i}$ to zero is within the reach of the adversary. This implies a hard truncation constraint on $\bm{q}$, namely the optimal $\bm{q}$ must come without such a tail.

Second, with optimal $\widetilde{\bm{p}}$, the remaining part of the game is a regularized log-likelihood maximization

$$ $\displaystyle\max_{\bm{q}}\bm{q}^{\top}\log\widehat{\bm{p}}-\epsilon\left\|{ \bm{q}_{1:\hat{\imath}}/\widehat{\bm{w}}}\right\|_{\infty},\quad\text{s.t. }q_ {i}=0,\;\forall i>\hat{\imath}$ $$

with an $\ell_{\infty}$-type regularization term $\left\|{\bm{q}_{1:\hat{\imath}}/\widehat{\bm{w}}}\right\|_{\infty}$. Note that we have $\widehat{\bm{w}}\approx\widehat{\bm{p}}_{1:\hat{\imath}}$ by applying first-order approximation to the function $\log(1+x)$. If no adversary is present ($\epsilon=0$), there is no regularization effect and trivially, greedy sampling solves the one-step log-likelihood maximization. This establishes an equivalence between regularization and robustness against an adversary, which has been observed in the robust optimization literature; see Section 2.3.

###### Theorem 4.3 .

### 4.2 q 𝑞 q italic_q -strategy: heuristic sampling methods

Now we present the optimal solution to the regularized maximization problem.

###### Theorem 4.4 .

Under Assumption 4.1 and 4.2, let $\hat{\imath}=\max\{i:\widehat{p}_{i}>\epsilon\}$, and $\widehat{w}_{i}=\frac{\epsilon}{\log(\widehat{p}_{i}/(\widehat{p}_{i}-\epsilon
))}$ for all $i\leq\hat{\imath}$. Define the threshold

$$ $I^{*}=\max\left\{I:\sum_{i=1}^{I-1}\widehat{w}_{i}\log(\widehat{p}_{i}/ \widehat{p}_{I})\leq\epsilon,\;\widehat{p}_{I}>\epsilon\right\}.$ $$

Then, the optimal $\widetilde{\bm{q}}$ for $\eqref{eq:one-step-game}$ is given elementwise by

$$ $\widetilde{q}_{i}\propto\widehat{w}_{i}\mathds{1}_{(1\leq i\leq I^{*})}.$ $$

###### Corollary 4.5 .

By first-order approximation, $\widehat{w}_{i}\approx\widehat{p}_{i}$, and hence $\widetilde{q}_{i}\propto\widehat{p}_{i}\mathds{1}_{(1\leq i\leq I^{*})}$, where

$$ $I^{*}=\max\left\{I:\sum_{i=1}^{I-1}\widehat{p}_{i}\log(\widehat{p}_{i}/ \widehat{p}_{I})\leq\epsilon,\;\widehat{p}_{I}>\epsilon\right\}.$ $$

Thus, up to first-order approximation, a truncation-normalization sampling strategy is optimal.

Clearly, Theorem 4.4 describes a sampling strategy that truncates tail probabilities and keeps only the subset $\{1,\dots,I^{*}\}$ as the support. Note that $I^{*}\leq\hat{\imath}$ always holds. The new distribution on the support $\widetilde{\bm{q}}_{1:I^{*}}$ is not a simple rescaling of the original weights $\widehat{\bm{p}}_{1:I^{*}}$ by a normalization constant, which is different from past heuristic designs. However, according to Corollary 4.5, rescaling emerges as a first-order approximation to the optimal strategy.

Under first-order approximation, the truncation threshold of $\widetilde{\bm{q}}$ has an information-theoretic interpretation. Note that if $I$ belongs to the support $\{1,\dots,I^{*}\}$, then $\sum_{i=1}^{I-1}\widehat{p}_{i}\log(\widehat{p}_{i}/\widehat{p}_{I})\leq\epsilon$, which is equivalent to

$$ $\log(1/\widehat{p}_{I})\leq H(\widehat{\bm{p}}_{1:I-1})+C_{I-1},$ $$

where $H(\widehat{\bm{p}}_{1:I-1})$ is the entropy of $\widehat{\bm{p}}_{1:I-1}$, and $C_{I-1}\coloneq-\log(\sum_{i=1}^{I-1}\widehat{p}_{i})+\epsilon/(\sum_{i=1}^{I-
1}\widehat{p}_{i})\geq\epsilon$. Thus, when constructing the support, we grow the existing support $\{1,\dots,I-1\}$ by adding $I$ if its self-information (surprisal) $\log(1/\widehat{p}_{I})$ is small compared to the existing entropy. This token selection mechanism modulates the total number of surprisals.

###### Theorem 4.4 .

###### Corollary 4.5 .

### 4.3 Generalization from log-likelihood

Beyond the log-likelihood, our analysis can be extended to games with more general objectives, taking the form

$$ $\max_{\phantom{\widehat{\bm{p}}}\bm{q}\phantom{\widehat{\bm{p}}}}\min_{\bm{p}: d_{\text{TV}}(\bm{p},\widehat{\bm{p}})\leq\epsilon}\bm{q}^{\top}f(\bm{p}),$ ( $f$ -ODG) $$

where $f:\mathbb{R}\to\mathbb{R}$ is applied elementwise on $\bm{p}$. We assume the following for ($f$-ODG).

###### Assumption 4.6 .

$f$ is non-decreasing and concave. Moreover, $(\epsilon,f)$ satisfies either of the following conditions:

- (i)
$\widehat{p}_{d}\leq\epsilon<\widehat{p}_{1}$, and $\lim_{x\downarrow 0}f(x)=-\infty;$
- (ii)
$0<\epsilon<\widehat{p}_{d}$, and $\sum_{i=1}^{d-1}\frac{f(\widehat{p}_{i})-f(\widehat{p}_{d}+\epsilon)}{f(
\widehat{p}_{i})-f(\widehat{p}_{i}-\epsilon)}\geq 1$.

Clearly, our previous log-likelihood game (ODG) satisfies this assumption. The following result establishes the solution to the general game ($f$-ODG), and encompasses Theorem 4.4 as a special case.

###### Theorem 4.7 .

Under Assumption 4.1 and 4.6, let

$$ $S_{I}=\sum_{i=1}^{I-1}\frac{f(\widehat{p}_{i})-f(\widehat{p}_{I})}{f(\widehat{ p}_{i})-f\left(\widehat{p}_{i}-\epsilon\right)},$ $$

and define the threshold $I^{*}=\max\left\{I:S_{I}\leq 1,\;\widehat{p}_{I}>\epsilon\right\}$. Then, the optimal $\widetilde{\bm{q}}$ for ($f$-ODG) is given elementwise by

$$ $\tilde{q}_{i}\propto\frac{\epsilon}{f(\widehat{p}_{i})-f\left(\widehat{p}_{i}- \epsilon\right)}\mathds{1}_{(1\leq i\leq I^{*})}.$ (5) $$

###### Corollary 4.8 .

Suppose $f$ is also differentiable. By first-order approximation on $f$, we have $\tilde{q}_{i}\propto\frac{1}{f^{\prime}(\widehat{p}_{i})}\mathds{1}_{(1\leq i
\leq I^{*})}$, where

$$ $I^{*}=\max\left\{I:\sum_{i=1}^{I-1}\frac{f(\widehat{p}_{i})-f(\widehat{p}_{I}) }{f^{\prime}(\widehat{p}_{i})}\leq\epsilon,\;\widehat{p}_{I}>\epsilon\right\}.$ $$

There are two interesting consequences of this general result. First, log-likelihood is the only objective that makes it optimal to rescale the remaining probabilities by a normalization constant. This is because enforcing $\frac{1}{f^{\prime}(x)}=x$ in Corollary 4.8 leads to $f(x)=\log x$ (up to a constant). Therefore, an exclusive connection between log-likelihood and rescaling is highlighted.

Second, since rescaling is not necessarily optimal, it is worth understanding how we treat the remaining probabilities under another $f$. One example is $f(x)=\frac{x^{1-1/\tau}-1}{1-1/\tau}$, where $\tau\neq 1$.(^2^22Note that $\lim_{\tau\to 1}\frac{x^{1-1/\tau}-1}{1-1/\tau}=\log x$.) Taking the derivative, we have $\frac{1}{f^{\prime}(\widehat{p}_{i})}=\exp(\frac{\log\widehat{p}_{i}}{\tau})=
\widehat{p}_{i}^{\;1/\tau}$, hence recovering temperature sampling (Hinton, ) where the temperature is controlled by $\tau$. This shows the general game $\eqref{pb:objective}$ is able to express a variety of sampling strategies.

###### Assumption 4.6 .

###### Theorem 4.7 .

###### Corollary 4.8 .

## 5 Experiments

Building on the truncation and normalization mechanism given in the general theory, we propose Game sampling as outlined in Algorithm 1, and empirically evaluate its performance in text generation. Regarding the algorithm design, the objectives to our concern are $f(x)=\frac{x^{1-1/\tau}-1}{1-1/\tau}$ and $f(x)=\log x$, as a special case of $\tau=1$. For better practical results, we relax the restrictions on the value of $\epsilon$ in Assumption 4.6.

Figure: Algorithm 1 Game sampling

We conduct an open-ended text generation task using web text from the [GPT-2 output dataset](https://github.com/openai/gpt-2-output-dataset). For each of the 5,000 articles in the Webtext test set, we use the first 35 tokens as prompts, with a maximum generation length of 256 tokens. For each type of GPT-2 model (Small, Medium, Large, XL), we evaluate the following metrics:

- 1.
Perplexity: The perplexity of the generated text under the corresponding GPT-2 model.
- 2.
Repetition frequency: The fraction of generations with repetitions. A generation is considered repetitive if it contains at least two contiguous copies of the same phrase, of any length, at the token level.
- 3.
MAUVE score (Pillutla et al., ): for comparison with human-written text, we use the corresponding human continuations from the test set, up to a maximum of 256 tokens.

A good performance is characterized by a high MAUVE score and close-to-human perplexity and repetition.

We compare four decoding strategies: the proposed Game sampling (Algorithm 1), Nucleus sampling, Greedy sampling (using $\operatorname*{argmax}_{i}\widehat{p}_{i}$), and Pure sampling (sampling $i$ with probability $\widehat{p}_{i}$). For Game sampling and Nucleus sampling, we report results under their respective best-performing hyperparameters as determined by MAUVE score.

The results are presented in Table 1, with a more detailed breakdown in Appendix B. Game sampling achieves the best performance for GPT-2 XL, Medium, and Small models, while underperforms Nucleus sampling for GPT-2 Large model.

**GPT-2 Small**
| Method | Perplexity | Repetition | MAUVE |
| --- | --- | --- | --- |
| Game ($\epsilon=0.95,\tau=2$) | 23.590 | 0.002 | 0.926 |
| Nucleus ($p=0.9$) | 25.116 | 0.004 | 0.923 |
| Greedy | 2.163 | 0.886 | 0.0155 |
| Pure | 62.001 | 0.0002 | 0.845 |
| Human | 21.559 | 0.002 | $-$ |

We also experiment with different values of $\epsilon$ and $\tau$, with details in Appendix B. In general, larger values of $\epsilon$ tend to produce better results in terms of higher MAUVE score, lower repetition frequency, and human-level perplexity. Smaller $\epsilon$ values reduce perplexity, but lead to more repetitions and lower MAUVE scores. In terms of $\tau$, the best performance for each $\epsilon$ choice was achieved at $\tau\approx 2$, yielding the highest MAUVE score. Similar to $\epsilon$, smaller $\tau$ values tend to reduce perplexity, but produce more repetitions with lower MAUVE scores. MAUVE score begins to decline when $\tau$ exceeds $2$.

## 6 Conclusion

In this paper, we propose Decoding Game, a two-player zero-sum game where a Strategist aims to maximize the log-likelihood of the generated text under the true probability measure, while an adversarial Nature seeks to distort the true measure within an $\epsilon$-error budget to degrade the text. After discussing the decomposibility of multi-step generation, we study the optimal strategies for both players of the typical one-step Decoding Game. We prove that, as Nature enforces its optimal strategy, it imposes an $\ell_{\infty}$-type regularization on the log-likelihood maximization problem. By solving this regularized maximization in closed form, we identify truncation-normalization sampling as a first-order approximation to the optimal strategy.

We also generalize our theoretical studies from log-likelihood to a broader class of objectives. Deriving the general solution, we observe that log-likelihood is the only objective that makes it optimal to rescale the remaining probabilities by a normalizing constant. Selecting other types of objectives leads to different ways of treating the remaining probabilities, including temperature sampling. Moreover, we empirically evaluate the performance of Game sampling, a sampling strategy built upon the general theory, in open-ended text generation with GPT-2 models.

We believe that Decoding Game provides a comprehensive theoretical understanding of the heuristic design of popular sampling strategies, by rigorously establishing regularization effect and optimality results. The statistically meaningful motivations and minimal assumptions behind Decoding Game open up its potential for future research, both theoretical and practical, on text generation strategies. For example, it can be interesting to study the game where the probability measures come from a structured space, such as the space expressed by transformer-based models, and understand its implications on the derived strategy. Also, our formulation of multi-step Decoding Game shares similarities with token-level Markov decision processes, and efficiently tackling multi-step strategy via reinforcement learning can be another direction.

## Appendix A Proofs

### A.1 Proof of Proposition 3.1

For probability vectors $\bm{q},\bm{p},\widehat{\bm{p}}\in\Delta(\mathcal{V})$, define $\mathcal{M}(\bm{q},\widehat{\bm{p}})=\min_{\bm{p}\in N(\widehat{\bm{p}})}\bm{q
}^{\top}\log\bm{p}$, and $\overline{\mathcal{M}}(\widehat{\bm{p}})=\max_{\bm{q}}\min_{\bm{p}\in N(
\widehat{\bm{p}})}\bm{q}^{\top}\log\bm{p}$. Then, the $t$-step total rewards of no-foresight strategy $\mathbb{Q}(\widehat{\mathbb{P}})$ and locally optimal strategy $\widetilde{\mathbb{Q}}(\widehat{\mathbb{P}})$ are respectively given by

$$ $\displaystyle\mathcal{L}^{t}(\mathbb{Q}(\widehat{\mathbb{P}}),\mathbb{P}^{*}( \widehat{\mathbb{P}},\mathbb{Q}))=\sum_{s=1}^{t}\mathbb{E}_{\bm{q}_{1}(\mathbb {P}),...,\bm{q}_{s-1}(\mathbb{P})}\mathcal{M}(\bm{q}_{s}(X_{<s}),\widehat{\bm{ p}}_{s}(X_{<s}))\coloneq\mathcal{R}^{t}(\mathbb{Q}(\widehat{\mathbb{P}}), \widehat{\mathbb{P}}),$ $\displaystyle\mathcal{L}^{t}(\widetilde{\mathbb{Q}}(\widehat{\mathbb{P}}), \mathbb{P}^{*}(\widehat{\mathbb{P}},\widetilde{\mathbb{Q}}))=\sum_{s=1}^{t} \mathbb{E}_{\widetilde{\bm{q}}_{1}(\widehat{\bm{p}}_{1}),...,\widetilde{\bm{q} }_{s-1}(\widehat{\bm{p}}_{s-1})}\overline{\mathcal{M}}(\widehat{\bm{p}}_{s}(X_ {<s}))\coloneq\widetilde{\mathcal{R}}^{t}(\widehat{\mathbb{P}}).$ $$

Since $\epsilon<\max_{i}\widehat{p}_{i}$, $\overline{\mathcal{M}}(\widehat{\bm{p}})$ is always bounded from below. Moreover, as the set-valued mapping $\widehat{\bm{p}}\mapsto N(\widehat{\bm{p}})$ satisfies upper and lower hemicontinuity and $N(\widehat{\bm{p}})$ is compact, $\overline{\mathcal{M}}$ is continuous in $\widehat{\bm{p}}$ by Berge’s Maximum Theorem (Aliprantis & Border, ), which further implies the continuity of $\widetilde{\mathcal{R}}^{t}$. Since the space of $\widehat{\mathbb{P}}$ is compact, we conclude that infimum of $\widetilde{\mathcal{R}}^{t}$ can be attained at some $\widehat{\mathbb{P}}^{*}$, namely $\inf\widetilde{\mathcal{R}}^{t}(\widehat{\mathbb{P}})=\widetilde{\mathcal{R}}^
{t}(\widehat{\mathbb{P}}^{*})$.

Now, if $\bm{q}_{t}(\widehat{\mathbb{P}}^{*})=\widetilde{\bm{q}}_{t}(\widehat{\bm{p}}_{
t}^{*})\;\forall t$, we are done. Otherwise, let $t_{0}$ be the first step such that $\bm{q}_{t_{0}}(\widehat{\mathbb{P}}^{*})\neq\widetilde{\bm{q}}_{t_{0}}(
\widehat{\bm{p}}_{t_{0}}^{*})$. We have

$$ $\displaystyle\sum_{s=1}^{t_{0}-1}\mathbb{E}_{\bm{q}_{1}(\widehat{\mathbb{P}}^{ *}),\dots,\bm{q}_{s-1}(\widehat{\mathbb{P}}^{*})}\mathcal{M}(\bm{q}_{s}(X_{<s} ),\widehat{\bm{p}}_{s}^{*}(X_{<s}))$ $\displaystyle=\sum_{s=1}^{t_{0}-1}\mathbb{E}_{\widetilde{\bm{q}}_{1}(\widehat{ \bm{p}}_{1}^{*}),\dots,\widetilde{\bm{q}}_{s-1}(\widehat{\bm{p}}_{s-1}^{*})} \mathcal{M}(\widetilde{\bm{q}}_{s}(X_{<s}),\widehat{\bm{p}}_{s}^{*}(X_{<s})),$ $\displaystyle\mathbb{E}_{\bm{q}_{1}(\widehat{\mathbb{P}}^{*}),\dots,\bm{q}_{t_ {0}-1}(\widehat{\mathbb{P}}^{*})}\mathcal{M}(\bm{q}_{t_{0}}(X_{<{t_{0}}}), \widehat{\bm{p}}_{t_{0}}^{*}(X_{<{t_{0}}}))$ $\displaystyle\leq\mathbb{E}_{\widetilde{\bm{q}}_{1}(\widehat{\bm{p}}_{1}^{*}), \dots,\widetilde{\bm{q}}_{t_{0}-1}(\widehat{\bm{p}}_{t_{0}-1}^{*})}\mathcal{M} (\widetilde{\bm{q}}_{t_{0}}(X_{<t_{0}}),\widehat{\bm{p}}_{t_{0}}^{*}(X_{<t_{0} })),$ $$

which implies $\mathcal{R}^{t_{0}}(\mathbb{Q}(\widehat{\mathbb{P}}^{*}),\widehat{\mathbb{P}}^
{*})\leq\widetilde{\mathcal{R}}^{t_{0}}(\widehat{\mathbb{P}}^{*})$.
Consider $\widehat{\mathbb{P}}^{**}$ defined as follows. For each $x_{<s}\in\mathcal{V}^{s-1}$,

$$ $\displaystyle\widehat{\bm{p}}_{s}^{**}(x_{<s})=\begin{cases}\widehat{\bm{p}}_{ s}^{*}(x_{<s}),&s\leq t_{0},\\ \widehat{\bm{p}}_{s}^{*}(x_{<s}^{*})\text{ where }x_{<s}^{*}=\operatorname*{ argmin}_{x\in\mathcal{V}^{s-1}}\mathcal{M}(\widetilde{\bm{q}}_{s}(x),\widehat{ \bm{p}}^{*}_{s}(x)),&s>t_{0}.\end{cases}$ $$

In words, $\widehat{\mathbb{P}}^{**}$ can be understood as shifting the future structure of $\widehat{\mathbb{P}}^{*}$ after $t_{0}$. Since the strategy $\mathbb{Q}(\widehat{\mathbb{P}})$ is defined to be sequential without foresight, we have $\bm{q}_{s}(\widehat{\mathbb{P}}^{**})=\bm{q}_{s}(\widehat{\mathbb{P}}^{*})$ for $s\leq t_{0}$. Hence,

$$ $\displaystyle\mathcal{R}^{t_{0}}(\mathbb{Q}(\widehat{\mathbb{P}}^{**}), \widehat{\mathbb{P}}^{**})\leq\widetilde{\mathcal{R}}^{t_{0}}(\widehat{\mathbb {P}}^{*})$ (6) $$

holds as well.

Due to our construction of $\widehat{\mathbb{P}}^{**}$, the future rewards after $t_{0}$ satisfy

$$ $\displaystyle\sum_{s=t_{0}+1}^{T}\mathbb{E}_{\bm{q}_{1}(\widehat{\mathbb{P}}^{ **}),\dots,\bm{q}_{s-1}(\widehat{\mathbb{P}}^{**})}\mathcal{M}(\bm{q}_{s}(X_{< s}),\widehat{\bm{p}}_{s}^{**}(X_{<s}))$ $\displaystyle\leq\sum_{s=t_{0}+1}^{T}\max_{x_{<s}\in\mathcal{V}^{s-1}}\mathcal {M}(\bm{q}_{s}(x_{<s}),\widehat{\bm{p}}_{s}^{**}(x_{<s}))$ $\displaystyle\leq\sum_{s=t_{0}+1}^{T}\max_{x_{<s}\in\mathcal{V}^{s-1}}\mathcal {M}(\widetilde{\bm{q}}_{s}(x_{<s}),\widehat{\bm{p}}_{s}^{**}(x_{<s}))$ $\displaystyle\leq\sum_{s=t_{0}+1}^{T}\mathbb{E}_{\widehat{\bm{q}}_{1},\dots, \widehat{\bm{q}}_{s-1}}\mathcal{M}(\widetilde{\bm{q}}_{s}(X_{<s}),\widehat{\bm {p}}_{s}^{*}(X_{<s})),$ $$

namely

$$ $\displaystyle\mathcal{R}^{T}(\mathbb{Q}(\widehat{\mathbb{P}}^{**}),\widehat{ \mathbb{P}}^{**})-\mathcal{R}^{t_{0}}(\mathbb{Q}(\widehat{\mathbb{P}}^{**}), \widehat{\mathbb{P}}^{**})\leq\widetilde{\mathcal{R}}^{T}(\widehat{\mathbb{P}} ^{*})-\widetilde{\mathcal{R}}^{t_{0}}(\widehat{\mathbb{P}}^{*}).$ (7) $$

With (6) and (7), we conclude that

$$ $\inf_{\widehat{\mathbb{P}}}\mathcal{R}^{T}(\mathbb{Q}(\widehat{\mathbb{P}}), \widehat{\mathbb{P}})\leq\mathcal{R}^{T}(\mathbb{Q}(\widehat{\mathbb{P}}^{**}) ,\widehat{\mathbb{P}}^{**})\leq\widetilde{\mathcal{R}}^{T}(\widehat{\mathbb{P} }^{*})=\inf_{\widehat{\mathbb{P}}}\widetilde{\mathcal{R}}^{T}(\widehat{\mathbb {P}}),$ $$

which proves the result.

### A.2 Proof of Theorem 4.7

We shall only prove the general theorem, as Theorem 4.3 and 4.4 are direct consequences.

Consider the minimization problem

$$ $\min_{\bm{p}\in N(\widehat{\bm{p}})}\bm{q}^{\top}f(\bm{p}),$ $$

where $N(\widehat{\bm{p}})=\{\bm{p}\in\Delta(\mathcal{V}):d_{\text{TV}}(\bm{p},\bm{q}
)\leq\epsilon\}.$

Since $f$ is a concave function, it is easy to show that $\bm{q}^{\top}f(\bm{p})$ is concave in $\bm{p}$. Moreover, the set $N(\widehat{\bm{p}})$ is a convex polytope since it is the intersection of two convex polytopes—the simplex $\Delta(\mathcal{V})$ and the set $\mathcal{F}\coloneq\{\bm{p}:\frac{1}{2}\left\|{\bm{p}-\widehat{\bm{p}}}\right
\|_{1}\leq\epsilon\}.$ Since we are looking for the minimum of $\bm{q}^{\top}f(\bm{p})$, a concave function, over $N(\widehat{\bm{p}})$ a convex polytope with a finite number of vertices, the minimum is achieved at one of the vertices (Horst, ). Next we will consider the two cases of the theorem separately.

Case 1 : $\epsilon<\widehat{p}_{d},$ and $\sum_{i=1}^{d-1}\frac{f(\widehat{p}_{i})-f(\widehat{p}_{d}+\epsilon)}{f(
\widehat{p}_{i})-f(\widehat{p}_{i}-\epsilon)}\geq 1$.

Let $V$ be the set of vertices of $N(\widehat{\bm{p}})$. Since $\epsilon<\widehat{p}_{d},$ the set $V$ is nothing but the points of intersection of the simplex $\Delta_{d}$ and the set $\mathcal{F}$ ,hence it can be written as
$V=\{\widehat{\bm{p}}-\epsilon\bm{e}_{i}+\epsilon\bm{e}_{j},\ \textit{for}\ i
\neq j\}.$ Hence, we have

$$ $\displaystyle\min_{\bm{p}\in N(\widehat{\bm{p}})}\bm{q}^{\top}f(\bm{p})$ $\displaystyle=\min_{\bm{p}\in V}\bm{q}^{\top}f(\bm{p})$ $\displaystyle=\bm{q}^{\top}f(\widehat{\bm{p}})+\min_{i\neq j}\left\{q_{i}\left (f(\widehat{p}_{i}-\epsilon)-f(\widehat{p}_{i})\right)+q_{j}\left(f(\widehat{p }_{j}+\epsilon)-f(\widehat{p}_{j})\right)\right\}$ $\displaystyle=\bm{q}^{\top}f(\widehat{\bm{p}})-\max_{i\neq j}\left\{q_{i}g^{-} (\widehat{p}_{i})-q_{j}g^{+}(\widehat{p}_{i})\right\},$ $$

where $g^{-}(x)\coloneq f(x)-f(x-\epsilon),$ and $g^{+}(x)\coloneq f(x+\epsilon)-f(x).$

Thus, the problem of interest is equivalent to

$$ $\min_{\bm{q}\in\Delta(\mathcal{V})}\left\{-\bm{q}^{\top}f(\widehat{\bm{p}})+ \max_{i\neq j}\left\{q_{i}g^{-}(\widehat{p}_{i})-q_{j}g^{+}(\widehat{p}_{i}) \right\}\right\}.$ $$

Observe that since $f$ is a concave, non-decreasing function, both $g^{+}$ and $g^{-}$ are non-increasing. Given any non-ordered $\bm{q}$, if we reorder it in a way that mirrors $\widehat{\bm{p}}$, it is clear with an application of the rearrangement inequality (Hardy et al., ) that the term $-\bm{q}^{\top}f(\widehat{\bm{p}})$ will decrease, since $f(\widehat{\bm{p}})$ is non-decreasing, and $\bm{q}^{\top}f(\widehat{\bm{p}})$ will increase.

Moreover, by reordering, the term $\max_{i\neq j}\left\{q_{i}g^{-}(\widehat{p}_{i})-q_{j}g^{+}(\widehat{p}_{i})\right\}$ will also decrease. Specifically, observe that

$$ $\displaystyle\max_{i\neq j}\left\{q_{i}g^{-}(\widehat{p}_{i})-q_{j}g^{+}( \widehat{p}_{j})\right\}$ $\displaystyle=\max_{i}\left\{q_{i}g^{-}(\widehat{p}_{i})-\min_{j\neq i}q_{j}g^ {+}(\widehat{p}_{j})\right\}$ $\displaystyle=\max_{j}\left\{\max_{i\neq j}q_{i}g^{-}(\widehat{p}_{i})-q_{j}g^ {+}(\widehat{p}_{j})\right\}.$ $$

Thus, for any fixed $i$, if we reorder the rest of the elements, $\min_{j\neq i}q_{j}g^{+}(\widehat{p}_{j})$ will increase, making the entire term smaller. Further, by fixing $j$ and reordering by placing $q_{i}$ in the correct position, $\max_{i\neq j}q_{i}g^{-}(\widehat{p}_{i})$ will decrease. Therefore, reordering $\bm{q}$ similar to $\widehat{\bm{p}}$ will decrease both terms, resulting in a lower overall objective.

Observe that problem ($f$-ODG) can be equivalently written as

$$ $\displaystyle\min_{\bm{q}}\quad$ $\displaystyle h(\bm{q})$ subject to $\displaystyle\bm{1}^{\top}\bm{q}=1,$ $\displaystyle\bm{q}\geq 0,$ $$

where $h(\bm{q})=-\min_{\bm{p}\in V}\bm{q}^{\top}f(\bm{p})$. Since $V$ is a finite set, $\min_{\bm{p}\in V}\bm{q}^{\top}f(\bm{p})$ is concave in $\bm{q}$, as it is the element-wise minimum of affine functions over a finite collection of elements in $V$. Thus, $h(\bm{q})$ is convex. Since there exists $\tilde{\bm{q}}\in\mathrm{relint}(\Delta_{d})$ with $\tilde{\bm{q}}>0$, strong duality holds. Therefore, from the Karush–Kuhn–Tucker (KKT) theorem (Boyd & Vandenberghe, ), the KKT conditions are both sufficient and necessary for any optimal $\bm{q}$.

Define the Lagrangian function:

$$ $\displaystyle L(\bm{q},\bm{\lambda},\nu)\coloneq-\bm{q}^{\top}f(\widehat{p})+ \max_{i\neq j}\left\{q_{i}g^{-}(\widehat{p}_{i})-q_{j}g^{+}(\widehat{p}_{j}) \right\}-\bm{\lambda}^{\top}\bm{q}+\nu\left(\sum_{i}q_{i}-1\right).$ $$

By the strong duality of the problem, it is sufficient to show that the KKT conditions for $L$ are satisfied by some solution $(\bm{q}^{*},\bm{\lambda}^{*},\nu^{*})$, with $\bm{q}^{*}$ as defined in (5).

The KKT conditions can be stated as:

$$ $\displaystyle\bm{0}\in-f(\widehat{\bm{p}})+\partial\left(\max_{i\neq j}\left\{ q_{i}g^{-}(\widehat{p}_{i})-q_{j}g^{+}(\widehat{p}_{j})\right\}\right)-\bm{ \lambda}^{*}+\nu^{*}\bm{1},$ (First-order stationarity) $\displaystyle\bm{q}^{*}\in Q,\quad\bm{\lambda}^{*}\geq 0,$ (Primal-dual feasibility) $\displaystyle\lambda_{i}^{*}q_{i}^{*}=0\quad\forall i,$ (Complementary slackness) $$

where the subdifferential $\partial$ (Rockafellar, ) represents the convex hull of the subgradients of the individual components, i.e., the pairs $(i,j)$ that achieve the maximum. It is defined as

$$ $\displaystyle\partial\left(\max_{i\neq j}\left\{q_{i}g^{-}(\widehat{p}_{i})-q_ {j}g^{+}(\widehat{p}_{j})\right\}\right)$ $\displaystyle\qquad\coloneq\mathrm{conv}\left(\left\{g^{-}(\widehat{p}_{i})\bm {e}_{i}-g^{+}(\widehat{p}_{j})\bm{e}_{j}:i\neq j\ \text{and}\ q^{*}_{i}g^{-}( \widehat{p}_{i})-q_{j}^{*}g^{+}(\widehat{p}_{j})=c\right\}\right),$ $$

where $c\coloneq\max_{i\neq j}\left\{q_{i}g^{-}(\widehat{p}_{i})-q_{j}g^{+}(\widehat{
p}_{j})\right\}$.

Next we will show that $\bm{q}^{*}$ defined by $q^{*}_{i}=\frac{c}{g^{-}(\widehat{p}_{i})}\mathds{1}_{(1\leq i\leq I^{*})}$ satisfies KKT conditions for some $\nu^{*}$ and $\bm{\lambda}^{*}$. Let

$$ $\mathcal{J}\coloneq\{i:q^{*}_{i}g^{-}(\widehat{p}_{i})=c\}=\{1\leq i\leq I^{*}\},$ $$

$$ $\mathcal{N}\coloneq\{i:q^{*}_{i}g^{+}(\widehat{p}_{i})=0\}=\{I^{*}<i\leq d\}.$ $$

Note that $S_{I}$ is non-decreasing in $I$ since $f(\widehat{p}_{1})\geq f(\widehat{p}_{2})\dots\geq f(\widehat{p}_{d}),$ thus

$$ $\sum_{k=1}^{I^{*}-1}\frac{f(\widehat{p}_{k})-f(\widehat{p}_{i})}{g^{-}( \widehat{p}_{k})}\leq 1,\quad\textit{for any }\ i\in\mathcal{J},$ (8) $$

and

$$ $\sum_{k=1}^{I^{*}-1}\frac{f(\widehat{p}_{k})-f(\widehat{p}_{i})}{g^{-}( \widehat{p}_{k})}>1,\quad\textit{for any }\ i\in\mathcal{N}.$ (9) $$

Moreover,

$$ $\displaystyle S_{d}=\sum_{k=1}^{d-1}\frac{f(\widehat{p}_{k})-f(\widehat{p}_{d} )}{g^{-}(\widehat{p}_{k})}>\sum_{k=1}^{d-1}\frac{f(\widehat{p}_{k})-f(\widehat {p}_{d}+\epsilon)}{g^{-}(\widehat{p}_{k})}\geq 1,$ $$

thus $I^{*}<d$, and $\mathcal{N}$ is non-empty.

To show that the KKT conditions are satisfied, it is equivalent to showing that there exist $\nu^{*}$, $\bm{\lambda}^{*}\geq 0$, with $\lambda_{i}^{*}=0$ for $i\in\mathcal{J}$, and coefficients $\gamma_{ij}\geq 0$ for $(i,j)\in\mathcal{J}\times\mathcal{N}$, with $\sum_{i\in\mathcal{J}}\sum_{j\in\mathcal{N}}\gamma_{ij}=1$ such that

$$ $\displaystyle-f(\widehat{p}_{i})+g^{-}(\widehat{p}_{i})\left(\sum_{j\in \mathcal{N}}\gamma_{ij}\right)\mathds{1}_{(i\in\mathcal{J})}-g^{+}(\widehat{p} _{i})\left(\sum_{j\in\mathcal{J}}\gamma_{ji}\right)\mathds{1}_{(i\in\mathcal{N })}-\lambda^{*}_{i}\mathds{1}_{(i\in\mathcal{N})}+\nu^{*}=0,$ $$

which is equivalent to

$$ $\displaystyle-f(\widehat{p}_{i})+g^{-}(\widehat{p}_{i})\left(\sum_{j\in \mathcal{N}}\gamma_{ij}\right)+\nu^{*}$ $\displaystyle=0\quad\ \textit{for}\ i\in\mathcal{J},$ (10) $\displaystyle-f(\widehat{p}_{i})-g^{+}(\widehat{p}_{i})\left(\sum_{j\in \mathcal{J}}\gamma_{ji}\right)+\nu^{*}$ $\displaystyle=\lambda_{i}^{*}\geq 0\quad\ \textit{for}\ i\in\mathcal{N}$ (11) $$

The above linear system is satisfied for

$$ $\nu^{*}=\left(\sum_{k\in\mathcal{J}}\frac{1}{g^{-}(\widehat{p}_{k})}\right)^{- 1}\left(\sum_{k\in\mathcal{J}}\frac{f(\widehat{p}_{k})}{g^{-}(\widehat{p}_{k}) }-1\right),$ $$

$$ $\gamma_{ij}=\frac{f(\widehat{p}_{i})-\nu^{*}}{g^{-}(\widehat{p}_{i})}\mathds{1 }_{(j=d)},$ $$

and

$$ $\lambda^{*}_{i}=\left(-f(\widehat{p}_{i})-g^{+}(\widehat{p}_{d})\mathds{1}_{(i =d)}+\nu^{*}\right)\mathds{1}_{(i\in\mathcal{N})}.$ $$

It is easy to verify that the above choices of $\nu^{*}$, $\gamma_{ij}$, and $\lambda^{*}$ satisfy the equalities in (10) and (11), as well as the condition $\sum_{i\in\mathcal{J}}\sum_{j\in\mathcal{N}}\gamma_{ij}=1$. Thus, it remains to verify that $\gamma_{ij}\geq 0$ and $\lambda^{*}_{i}\geq 0$.

From (8), we conclude that $\gamma_{ij}\geq 0$, and from (9), we have $\lambda^{*}_{i}\geq 0$ for all $I^{*}<i<d$. Additionally, the condition

$$ $\sum_{k=1}^{d-1}\frac{f(\widehat{p}_{k})-f(\widehat{p}_{d})-g^{+}(\widehat{p}_ {d})}{g^{-}(\widehat{p}_{k})}=\sum_{k=1}^{d-1}\frac{f(\widehat{p}_{k})-f( \widehat{p}_{d}+\epsilon)}{g^{-}(\widehat{p}_{k})}\geq 1$ $$

implies that $\lambda^{*}_{d}\geq 0$.

Therefore, the above choices of $\nu^{*}$, $\gamma_{ij}$, and $\lambda^{*}$ satisfy the linear system and all constraints. Thus, $(\bm{q}^{*},\bm{\lambda}^{*},\nu^{*})$ satisfy the KKT conditions, and hence $\bm{q}^{*}$ is the optimal solution to problem ($f$-ODG).

Case 2: $\widehat{p}_{d}\leq\epsilon<\widehat{p}_{1},$ and $\lim_{x\downarrow 0}f(x)=-\infty$.

Let $A=\{i:\widehat{p}_{i}\leq\epsilon\}$ and $Q=\{\bm{q}\in\Delta(\mathcal{V}):q_{i}=0\ \text{for all}\ i\in A\}$. Suppose $\tilde{\bm{q}}\notin Q$, i.e., there is some $j\in A$ such that $q_{j}\neq 0$. Since $\lim_{x\downarrow 0}f(x)=-\infty$, we can find $\tilde{\bm{p}}=\widehat{\bm{p}}-\widehat{p}_{j}\bm{e}_{j}$ such that $\tilde{\bm{q}}^{\top}f(\tilde{\bm{p}})=-\infty$. Thus, we can only consider $\bm{q}\in Q$. Similar to Case *(i)*, the minimization problem can be written in terms of the vertices of $N(\widehat{\bm{p}})$ as follows:

$$ $\displaystyle\min_{\bm{p}\in N(\widehat{\bm{p}})}\bm{q}^{\top}f(\bm{p})$ $\displaystyle=\min_{\bm{p}\in V}\bm{q}^{\top}f(\bm{p})$ (12) $\displaystyle=\min_{\bm{p}\in\tilde{V}}\bm{q}^{\top}f(\bm{p})$ (13) $\displaystyle=\bm{q}^{\top}f(\widehat{\bm{p}})+\min_{(i,j)\in C}\left\{q_{i} \left(f(\widehat{p}_{i}-\epsilon)-f(\widehat{p}_{i})\right)+q_{j}\left(f( \widehat{p}_{j}+\epsilon)-f(\widehat{p}_{j})\right)\right\}$ $\displaystyle=\bm{q}^{\top}f(\widehat{\bm{p}})-\max_{(i,j)\in C}\left\{q_{i}g^ {-}(\widehat{p}_{i})-q_{j}g^{+}(\widehat{p}_{i})\right\}$ $\displaystyle=\bm{q}^{\top}f(\widehat{\bm{p}})-\max_{i\notin A}q_{i}g^{-}( \widehat{p}_{i}),$ (14) $$

where $V$ is the set of vertices of $N(\widehat{\bm{p}})$, $\tilde{V}=\{\bm{p}\in V:\bm{p}=\widehat{\bm{p}}-\epsilon\bm{e}_{i}+\epsilon\bm
{e}_{j},\ \text{for}\ i\notin A,\ j\neq i\}$, and $C=\{(i,j):i\neq j,\ i\notin A\}$. (12) holds since we are minimizing a concave function over a convex polytope, and (13) holds since we are only considering $\bm{q}\in Q$. (14) follows because $q_{j}=0$ for any $j\in A$, which must include at least one element since $\widehat{p}_{d}\leq\epsilon$.

Thus, the problem of interest is equivalent to

$$ $\min_{\bm{q}\in Q}\left\{-\bm{q}^{\top}f(\widehat{\bm{p}})+\max_{i\notin A}q_{ i}g^{-}(\widehat{p}_{i})\right\}.$ $$

Then similar to the argument in Case *(i)*, $\bm{q}$ should be ordered similarly to $\widehat{\bm{p}}$, i.e., $q_{1}\geq q_{2}\geq\dots\geq q_{d}$.

Since $q_{i}=0$ for all $i\in A$, the problem can be reduced to the following lower-dimensional problem:

$$ $\min_{\bm{q}\in\Delta(\mathcal{\tilde{V}})}\left\{-\bm{q}^{\top}f(\widehat{\bm {p}})+\max_{i}q_{i}g^{-}(\widehat{p}_{i})\right\},$ $$

where $|\mathcal{\tilde{V}}|=d-|A|=\tilde{d}$. Define the Lagrangian function:

$$ $\displaystyle L(\bm{q},\bm{\lambda},\nu)\coloneq-\bm{q}^{\top}f(\widehat{p})+ \max_{i}q_{i}g^{-}(\widehat{p}_{i})-\bm{\lambda}^{\top}\bm{q}+\nu\left(\sum_{i }q_{i}-1\right).$ $$

By strong duality of problem ($f$-ODG), it is sufficient to show that the KKT conditions for $L$ are satisfied by some solution $(\bm{q}^{*},\bm{\lambda}^{*},\nu^{*})$, with $\bm{q}^{*}$ as defined in (5).

The KKT conditions are:

$$ $\displaystyle\bm{0}\in-f(\widehat{\bm{p}})+\partial\left(\max_{i}q_{i}g^{-}( \widehat{p}_{i})\right)-\bm{\lambda}^{*}+\nu^{*}\bm{1},$ (first-order stationarity) $\displaystyle\bm{q}^{*}\in Q,\quad\bm{\lambda}^{*}\geq 0,$ (primal-dual feasibility) $\displaystyle\lambda_{i}^{*}q_{i}^{*}=0\quad\forall i,$ (complementary slackness) $$

where $\partial\left(\max_{i}q_{i}g^{-}(\widehat{p}_{i})\right)\coloneq\mathrm{conv}
\left(\{g^{-}(\widehat{p}_{i})\bm{e}_{i}:q^{*}_{i}g^{-}(\widehat{p}_{i})=c\}\right)$.

Let

$$ $\mathcal{J}=\{i:q^{*}_{i}g^{-}(\widehat{p}_{i})=c\}=\{1\leq i\leq I^{*}\}, \quad\mathcal{N}=\{i:q^{*}_{i}g^{-}(\widehat{p}_{i})=0\}=\{I^{*}<i\leq\tilde{d }\},$ $$

where $c\coloneq\max_{i}q^{*}_{i}g^{-}(\widehat{p}_{i})$. It is sufficient to show that there exist $\nu^{*}$ and $\bm{\lambda}^{*}\geq 0$, with $\lambda_{i}^{*}=0$ for $i\in\mathcal{J}$, and coefficients $\gamma_{i}\geq 0$ for $i\in\mathcal{J}$, with $\sum_{i\in\mathcal{J}}\gamma_{i}=1$ such that:

$$ $-f(\widehat{p}_{i})+\gamma_{i}g^{-}(\widehat{p}_{i})\mathds{1}_{\{i\in\mathcal {J}\}}-\lambda^{*}_{i}\mathds{1}_{\{i\in\mathcal{N}\}}+\nu^{*}=0,$ $$

which is achieved by setting:

$$ $\nu^{*}=\left(\sum_{k\in\mathcal{J}}\frac{1}{g^{-}(\widehat{p}_{k})}\right)^{- 1}\left(\sum_{k\in\mathcal{J}}\frac{f(\widehat{p}_{k})}{g^{-}(\widehat{p}_{k}) }-1\right),$ $$

$$ $\gamma_{i}=\frac{f(\widehat{p}_{i})-\nu^{*}}{g^{-}(\widehat{p}_{i})}\geq 0, \quad\text{for}\ i\in\mathcal{J},$ $$

and

$$ $\lambda^{*}_{i}=\left(\nu^{*}-f(\widehat{p}_{i})\right)\mathds{1}_{(i\in \mathcal{N})}\geq 0,$ $$

where $\gamma_{i}\geq 0$ and $\lambda^{*}_{i}\geq 0$, follow using $S_{I}\leq 1$ for all $I\in\mathcal{J}$, and $S_{I}>1$ for all $I\in\mathcal{N}$, respectively.

## Appendix B Additional experiments

In Table 2, we present additional experimental results obtained using various choices of $\epsilon$ and $\tau$ in Game sampling algorithm. These experiments provide further insights into the performance and sensitivity of the model under different parameter settings. We also explored different values of $\epsilon\in\{0.1,0.3,0.5,0.8,0.9\}$ alongside different $\tau$ values. However, since the best performance was consistently achieved with $\epsilon=0.95$ or $\epsilon=0.99$, we report only those values here to highlight the effect of changing $\tau$.

As part of this evaluation, we also analyzed the point at which probabilities are truncated and renormalized in Game sampling and Nucleus sampling for a randomly selected article from the WebText test set, using the GPT-2 XL model. The GPT-2 model has a total vocabulary size of 50,000 tokens, so truncating the probability distribution can significantly reduce the set of candidate words for the next token. Figures 1(a) and 1(b) illustrate how these sampling strategies truncate the probability distribution. Figure 1(a) shows the distribution for the next word when using only 1 token as context, along with the index where probabilities are truncated and set to zero. In contrast, Figure 1(b) presents the distribution for the next word when using the first 35 tokens as context, providing more information for the model to generate the next word. With more context, the model is expected to be more certain about the next word, and the figure highlights the corresponding truncation points. Notably, Game sampling truncates a substantial portion of the 50,000-token distribution and dynamically adjusts the cutoff point based on the shape of the distribution (see Algorithm 1).

**GPT-2 Small**
| $\epsilon$ | $\tau$ | Perplexity | Repetition | MAUVE |
| --- | --- | --- | --- | --- |
| 0.95 | 1.0 | 6.874 | 0.087 | 0.739 |
| 0.95 | 1.1 | 7.96 | 0.058 | 0.809 |
| 0.95 | 1.5 | 13.336 | 0.015 | 0.898 |
| 0.95 | 2.0 | 23.592 | 0.003 | 0.926 |
| 0.95 | 2.5 | 40.129 | 0.002 | 0.908 |
| 0.95 | 3.0 | 66.481 | 0.001 | 0.815 |
| 0.95 | 3.5 | 107.544 | 0.001 | 0.699 |
| 0.95 | 4.0 | 172.822 | 0.001 | 0.474 |
| 0.99 | 1.0 | 7.067 | 0.081 | 0.746 |
| 0.99 | 1.1 | 8.275 | 0.055 | 0.82 |
| 0.99 | 1.5 | 14.231 | 0.012 | 0.897 |
| 0.99 | 2.0 | 26.783 | 0.002 | 0.917 |
| 0.99 | 2.5 | 48.508 | 0.002 | 0.864 |
| 0.99 | 3.0 | 89.308 | 0.001 | 0.745 |
| 0.99 | 3.5 | 161.402 | 0.001 | 0.529 |
| 0.99 | 4.0 | 296.453 | 0.001 | 0.273 |

Figure: (a) context: 1 token
Refer to caption: extracted/5903028/probabilities_zero_point_4000_tokens_1prefix.png

## Peer Reviews

confidence: 2
contribution: 2
initial_rating: 5
presentation: 2
questions: My main concerns and questions are outlined in Weaknesses.
There is a typo in the introduction section:
* (line 55-56) "From a statistical perspective" is repeated.
soundness: 2
strengths: * The problem is appropriately motivated. Considering decoding strategies from a theoretical standpoint is essential for the research community.
* The algorithm proposed to solve the suggested minimax optimization problem appears to be easily implementable in practice.
summary: This paper primarily focuses on text generation for language models.
Firstly, the author presents a novel minimax optimization problem for text generation tasks, where the min-player aims to minimize the worst-case negative cross-entropy.
Subsequently, it is demonstrated that the proposed minimax optimization problem can be interpreted as a likelihood maximization problem with implicit regularization.
Finally, the algorithm for solving the minimax optimization problem is introduced and its performance is empirically evaluated through experiments using GPT-2 models.
weaknesses: I'm wondering to what extent this study provides new insights for existing decoding strategies that have achieved empirical success.
The author states "To resolve this dichotomy, this paper aims to propose a comprehensive theoretical framework of text generation" in the introduction section, meaning that one of the main goals of this paper is to theoretically explain the success of these existing strategies.
However, I'm not convinced that the proposed framework can replicate the widely recognized Nucleus sampling and Top-k sampling strategies simply by selecting an objective function $f$.
While it's demonstrated that temperature sampling can be recovered by appropriately choosing the function $f$, I'm interested in knowing if other strategies can also be replicated.

Moreover, since I'm not an expert in this research field, I'm not sure whether experiments using only GPT-2 models are sufficient for validating the proposed framework.
At the very least, it should be discussed whether the scale of the experiments conducted in this study is not insufficient compared to the current standards.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: “Depending on the desired effect, the truncation threshold or S may be determined from various quantities like the truncated vocabulary size, truncated probability weight, entropy, and so on. ” - this is confusing since the truncated vocabulary size, probability weight etc are themselves a function of S. What did you mean here?
Regarding the experiments, have you tried any of the methods that drop non-tail elements? (such as truncation sampling by Finlayson et al. (2024)). It would be interesting to see how a different-pattern sampling compares.
Is there any reason in the remark around line 376 for $C_{I-1}$ to not dominate the entropy? It’s not obvious how to interpret that.
Can your method be adapted to deal with other sorts of measure distances? The most natural one would be bounded cross entropy since this is what training usually optimizes
soundness: 4
strengths: The theoretical framework is well justified and rigorously supported by proofs
Statements are accurate and notation is consistent. Assumptions are clearly stated and natural.
The problem that is addressed is practically significant.
The framework generalizes previous decoding schemes opening the door to new, theoretically-grounded, heuristics.
summary: The paper proposes a theoretical framework that captures various decoding strategies used in practice, as well as provides a generalized form of such a technique and some experiments to support it.
weaknesses: In Prop 3.1, the authors could mention why we need the $\epsilon < max \hat{p}$ - that if we assign non-zero measure to $x_{<t}$, we’d get a cost of $-\infty$.
Theorem 4.3 doesn’t say anything about how the $p$ that yields the optimal solution looks like, nor what role $\hat{w}$ plays (in the min problem; the max one is clear). Does that lack structure or could it be added to the Theorem statement?
While the game approach to it is intuitive to some, it might be worth emphasizing the perspective of optimizing the worst case scenario: there are a couple of places where you phrase the framework, but don’t necessarily argue why nature “should” be adversarial. Optimizing the worst case scenario makes it more clear to people that are not used to thinking about games (since after all you just choose the approach that has the best guarantees under the TV assumption).
It’d be helpful to present the more general case secondary to what you get when you use a greedy local approach (which is done in section 3.4 and then used throughout). Once you decide to do local optimization rather than global, you can jump straight to Equation (4) and while Section 3.3 is well-written and objectively accurate, it is the hardest part to read of the whole paper and people may lose the important take-aways because of getting confused there.

Minor:
Remark at line 339 seems to be more relevant right before Corollary 4.5.
Line 54-55 repeats “From a statistical perspective”
It is worth making explicit that X_0 is a multidimensional object (as opposed to X_{t>0})
Line 243: $N (\hat{P})$ to be $\hat{P}$.. - an extra $\hat{P}$.

---

confidence: 3
contribution: 3
initial_rating: 5
presentation: 3
questions: N/A
soundness: 3
strengths: - The analysis of the decoding process of LLMs is thoroughly considered. 
- The proposed decoding is backed up theoretically
- The experimental results show somewhat better performance than baselines.
summary: The paper explores the gap between theoretical and practical decoding strategies in text generation for language models.The authors introduce a new framework, Decoding Game, which models text generation as a two-player game. They derive the optimal one-step strategy, showing adversarial regularization on likelihood maximization, with popular methods as first-order approximations. The framework also generalizes to include strategies like greedy search and temperature scaling. Numerical experiments support their theoretical findings.
weaknesses: - What is the motivation for choosing the TV-sup norm to compute the difference between the true distribution and the approximated one by LLMs? Is there any theoretical justification behind this selection? If not, at least an ablation study showing the effectiveness of this norm is necessary.
- It is still ambiguous why the authors define the distance between the two mappings by the way around Line 248.
- The result in the Equation (1) is non-trivial. Detailed transformation of it is necessary. At first glance, I questioned the equivalence of the two sides.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: See weaknesses.
soundness: 3
strengths: * It is valuable to have a proper theoretical derivation of heuristic decoding methods that have long been around in practice, and the paper provides this.
* the paper is well-written and neat
* the connection to robust optimization is interesting
summary: The paper derives stochastic decoding methods as the optimal strategy in an adversarial two-player game. Due to tractability issues, a one-step version of this game and a first order approximation for the resulting strategy is used. An explicit expression for the resulting regularization term added to the maximum likelihood objective is derived.
weaknesses: * The empirical comparison is not state-of-the-art. For example, there are newer variants of greedy designed to overcome issues with repetitiveness, see contrastive search (see: https://huggingface.co/blog/introducing-csearch).
* The introduction sounds a bit like stochastic sampling strategies would always be preferable over deterministic optimization strategies like greedy search or beam search in practice. While there definitely is evidence that they perform better in some settings as given by the citations in the paper, there is also counter-evidence in other settings, e.g. [1], in particular in closed-end tasks. (Btw, the experiments in the paper are also limited to open-end text generation.) I understand that the authors preliminarily want to motivate stochastic decoding strategies in this paper and I do not want to diminish the motivation for them, but I still think it is important to at least acknowledge that the situation is more nuanced. For a recent empirical comparison, also see [2].

[1] "On Decoding Strategies for Neural Text Generators" [Wiher et al, 2022]

[2] "A Thorough Examination of Decoding Methods in the Era of LLMs" [Shi et al., 2024]

Meta-review: The paper introduces a game-theoretic framework, coined "Decoding Game", which models text generation as a two-player zero-sum game. The framework is used to explain methods such as Top-k and Nucleus sampling as approximations to the optimal strategy in the decoding game, giving a common theoretical grounding to these approaches. Empirical evaluation on several language models, including GPT-2, GPT-J-6B, and Llama-2-7B, and showing competitive performance according to various metrics, complements the submission.

Some reviewers seemed initially skeptical regarding the potential for practical relevance of the results and certain details of the experimental setup. However, these concerns seem to have been largely resolved through author rebuttals and updates to the submission. The addition of experiments with larger models/baselines was particularly well-received. There appears to be positive consensus towards the value of the paper.

For that, an acceptance decision is recommended.

Decision: Accept (Poster)