# SequenceMatch: Imitation Learning for Autoregressive Sequence Modelling with
Backtracking

Chris Cundy1 Stefano Ermon1
1Department of Computer Science, Stanford University
{cundy<EMAIL_ADDRESS>

###### Abstract

In many domains, autoregressive models can attain high likelihood on the task
of predicting the next observation. However, this maximum-likelihood (MLE)
objective does not necessarily match a downstream use-case of autoregressively
generating high-quality sequences. The MLE objective weights sequences
proportionally to their frequency under the data distribution, with no
guidance for the model’s behaviour out of distribution (OOD): leading to
compounding error during autoregressive generation. In order to address this
compounding error problem, we formulate sequence generation as an imitation
learning (IL) problem. This allows us to minimize a variety of divergences
between the distribution of sequences generated by an autoregressive model and
sequences from a dataset, including divergences with weight on OOD generated
sequences. The IL framework also allows us to incorporate backtracking by
introducing a backspace action into the generation process. This further
mitigates the compounding error problem by allowing the model to revert a
sampled token if it takes the sequence OOD. Our resulting method,
SequenceMatch, can be implemented without adversarial training or
architectural changes. We identify the SequenceMatch-$\chi^{2}$ divergence as
a more suitable training objective for autoregressive models which are used
for generation. We show that empirically, SequenceMatch training leads to
improvements over MLE on text generation with language models.

##  1 Introduction

Autoregressive models such as the GPT series of causally masked transformers
[7, 25] are able to perform a variety of downstream tasks such as question-
answering, translation, and summarization, after simply training on a large
corpus of text with the objective of predicting the next token given the
previous tokens. However, autoregressive language models suffer from a variety
of pathological behavior when deployed on the task of free-form text
generation [15, 37], particularly at lower generation temperatures or with
smaller models. These include generating the same token or series of token
repeatedly, or generating gibberish outputs. This phenomenon of degeneration
for longer continuations has also been observed in autoregressive models for
video [36]. This problem of neural text degeneration has been linked to the
training objective for LLMs, which trains a conditional distribution for the
next token given a (partial) sentence [10]. When deployed in an autoregressive
fashion, the model has its own outputs as inputs, resulting in a compounding
error problem that rapidly takes the model out of distribution (OOD). This
compounding error problem is also a key issue in the imitation learning
subfield of reinforcement learning, where the goal is to learn a policy (a
distribution over next actions given the past) which results in trajectories
similar to a set of provided expert trajectories. The approach of directly
matching the expert’s actions leads to a compounding error [27], which has led
to several works proposing to address this problem by minimizing alternative
divergences [3, 28]. These alternative divergences encourage the policy to
return to expert states if the generated trajectory starts to diverge from
them. We argue that two key issues can prevent autoregressive models trained
with maximum-likelihood from generating fluent sequences at evaluation time.
First is the divergence measure used to evaluate the difference between the
model and the data distribution. Because the MLE loss does not have any
contribution from OOD sequences, the behavior of the model on OOD sequences
(such as those generated autoregressively) is not constrained. We address this
by minimizing the $\chi^{2}$-divergence between a mixture of the data and
autoregressively generated sequences. This divergence is known to perform much
better than MLE in imitiation learning [11, 1].

Secondly, if a model generates an OOD token, there may be no natural
continuation which is similar to sequences from the data distribution, and so
the model may be unable to return to the data distribution even if our
$\chi^{2}$-divergence encourages this. To address this, we augment the
generation process with a <backspace> action, which deletes the previous
token, and allows the model to correct for erroneous generations. By
incorporating recent work in non-adversarial imitation learning [11], our
method, _SequenceMatch_ , is able to train autoregressive models against
alternative divergences such as the $\chi^{2}$-mixture divergence while
augmenting the policy with a <backspace> action. The SequenceMatch loss is a
fully supervised loss without adversarial training, and can be applied on top
of pretrained models as a finetuning step. To summarize our contributions:

  * •

We formulate the sequence generation problem as an imitation learning (IL)
problem, and formulate a general non-adverarial objective for minimizing
divergences between occupancy measures based on [11], handling (among others)
the forward and reverse KL-divergence, JS-divergence, and $\chi^{2}$
divergence.

  * •

We develop a novel masking scheme allowing training of a transformer-based
autoregressive model with a <backspace> action with no additional overhead vs
MLE.

  * •

Finally we evaluate the empirical performance of SequenceMatch-trained models,
showing improved performance over the maximum likelihood objective in general
text generation.

Figure 1: A toy model of an autoregressive generation problem, such as
language modelling. Our task is to learn a set of conditional distributions
that continue the sequence similarly to those sequences in the dataset (green
arrows), and avoid incorrect next tokens (red arrows). Our method trains
against divergences that more heavily punish out-of-distribution sequences. We
additionally introduce a <backspace> action which can backtrack from an
erroneous token (dashed purple arrows).

##  2 Preliminaries: Training Objectives for Autoregressive Models

###  2.1 KL-Divergence

Typically, autoregressive models are trained against a maximum-likelihood
objective. This objective can be motivated by treating our dataset as
consisting of sequences of random variables $(x_{1},\ldots,x_{N})$, with a
corresponding probability distribution $P_{\text{data}}(x_{1},\ldots,x_{N})$,
with a fixed length $N$. The goal is to learn a parameterized model
$P_{\theta}(x_{1},\ldots,x_{N})$ that is close to $P_{\text{data}}$. The KL-
divergence between the data distribution and the model has a useful
decomposition:

$\displaystyle D_{\text{KL}}(P_{\text{data}}\|P_{\theta})$
$\displaystyle=\mathbb{E}_{x_{1:N}\sim P_{\text{data}}}\left[\log
P_{\text{data}}(x_{1:N})-\log P_{\theta}(x_{1:N})\right]$ (1)
$\displaystyle=-\mathbb{E}_{x_{1:N}\sim P_{\text{data}}}\left[\sum_{i}^{N}\log
P_{\theta}(x_{i}|x_{<i})\right]+C,$ (2)

where $C$ is a constant that does not depend on $\theta$. For a dataset
$\mathcal{D}=\\{x_{1:N}^{j}\\}_{j=0}^{N_{\text{data}}}$ of sequences drawn
i.i.d. from $P_{\text{data}}$, this can be approximated with an estimator
${\hat{D}_{\text{KL}}}(P_{\text{data}}\|P_{\theta})=\tfrac{1}{N_{\text{data}}}\sum_{j}\sum_{i}^{N}\log
P_{\theta}(x_{i}^{j}|x_{<i}^{j})+C^{\prime}$. Hence, minimizing the KL-
divergence is equivalent to maximizing the model’s (log-) likelihood of the
next element in the sequence given the previous elements. This formulation is
statistically well-motivated and particularly convenient for architectures
such as the transformer [35], where all conditionals over a sequence can be
computed in parallel. The density under the data distribution
$P_{\text{data}}$ is not required, which is convenient as it is typically
unknown. In some domains, the length of the sequences $n_{j}$ differs in each
example $j$, which can be incorporated by choosing an effective length $N=\max
n_{i}$, and treating all sequences shorter than $N$ as having a sequence of
padding tokens appended111Some care is required here, as each averaging the
loss of each example over its length leads to an inconsistent estimator.. In
the sequel with some abuse of notation we will write $P_{\text{data}}(s_{n})$
for $\sum_{i}^{n}\log P_{\theta}(x_{i}|x_{<i})$, for partial sequences that
may not terminate until after $n$, and $P_{\text{data}}(x|s_{n})$ to signify
the conditional probability of the next token given a partial sequence.

####  2.1.1 Limitations of the KL-divergence

However, while it is clear that minimizing the KL-divergence in equation (1)
will result in $P_{\theta}=P_{\text{data}}$ (for a sufficiently flexible
parameterization $P_{\theta}$), it is not obvious what the behaviour is of
models which _approximately_ minimize the KL-divergence. In figure 1, a chain
distribution is shown, with sequences of length $N$. The model $P_{\theta}$
has an $\epsilon$ error on each conditional, where an error leads to an OOD
sequence which has no support under the data distribution. This leads to an
error in the KL metric of order $n\epsilon$. However, the probability of
getting to the end of the chain before an incorrect token is picked is
$1-(1-\epsilon)^{n}$, and so the value of the KL-divergence is not a good
metric if our main quantity of interest is how often generated sequences are
in-distribution. Furthermore, the KL-divergence weights the loss by the
frequency under the data distribution, so if sequences are rarely seen under
the data distribution they are not very important in the total loss. One
particular implication is that the model’s behavior out-of-distribution from
the data is essentially undetermined. In other words, there is no optimization
pressure on the model to learn how to ‘recover’ from mistakes.

In non-autoregressive generative modelling, a wide variety of different
divergences are commonly used, such as the Wasserstein distance [2] and Fisher
divergence [30]. Particularly interesting is the $\chi^{2}$ divergence
$D_{\chi^{2}}(P_{\theta},P_{\text{data}})=\mathbb{E}_{x\sim
P_{\text{data}}}\left[(P_{\theta}(x)/P_{\text{data}}(x)-1)^{2}\right]$. Indeed
we see in figure 1 that the $\chi^{2}$-divergence in this case is equal to the
squared probability of staying in the data distribution of sequences. We can
further penalize out-of-distribution behavior by considering the divergence
between mixtures $D_{\chi^{2}}(P_{\theta},(P_{\text{data}}+P_{\theta})/2)$, as
we do in our practical algorithm. However, it is generally difficult in
practice to compute any divergence involving the density of the data, which
must be substituted for with an approximation from a discriminator.

In the field of reinforcement learning, several methods have been discovered
which can minimize divergences such as Wasserstein and JS between the
distribution of trajectories from an expert and a learned policy. The
approaches are non-adversarial, even though the expert density is not known
[11, 32, 4, 1]. A key feature of these methods is that they operate on
_occupancy measures_ instead of joint distributions, a concept which we
introduce in the next section 3.

##  3 Method

###  3.1 Sequence Modelling as a Markov Decision Process

We consider a sequence model represented as a Markov decision process (MDP),
defined by a tuple ($\mathcal{S},\mathcal{A},\mathcal{P},r,\gamma)$.
$\mathcal{S},\mathcal{A}$ represent state and action spaces,
$\mathcal{P}(s^{\prime}|s,a)$ represents the dynamics, $r(s,a)$ represents the
reward function, and $\gamma\in(0,1)$ represents the discount factor. In our
case, the state space $\mathcal{S}$ is the set of all sequences (of all
lengths) with elements in a finite set $X$ (the vocabulary plus a <begin-
sentence> token if not already present in the vocabulary). The set of actions
$\mathcal{A}$ is a finite set. For concreteness, we can assume that
$X\subseteq\mathcal{A}$ (i.e. we have an insert-token action for each token),
as well as additional editing actions (<backspace>, etc). In our case, we will
assume that the initial state is deterministically given by a special <begin-
sentence> token, while the dynamics for an insert-token action in a state
(sequence) $s$ leads deterministically to the sequence $s^{\prime}$ consisting
of $s$ with the given token appended to the end.

Combined with a policy $p_{\theta}(a|s)$, the MDP defines a distribution over
(possibly infinite-length) sequences, following the generative process of
sampling an action $a\sim p_{\theta}(\cdot|s)$, then sampling the next state
$s^{\prime}\sim\mathcal{P}(s^{\prime}|s,a)$, etc. Finally, we assume that a
special end of sequence token <end-of-sentence> induces a terminal state: in
any state $s$ with <end-of-sentence> as the final element, all actions cause a
self-transition to $s$ with probability 1. We note that this probabilistic
process reduces exactly to the autoregressive formulation of sequence
modelling when the action set is the same as the vocabulary, but is different
when editing actions are introduced. We incorporate a single editing action,
<backspace>. A backspace action in a state $s$ deterministically transitions
to a state $s^{\prime}$ with the final token in the sequence $s$ removed.222In
the case of $s$ = <begin-sentence> and <backspace> is used, $s^{\prime}$ =
<begin-sentence> also An example of the states and actions can be seen in
figure 2. As an additional example, the actions [a; <backspace>] have
corresponding states [<begin-sentence>; <begin-sentence> a; <begin-sentence>].
The MDP framework formalizes the intuitive picture in figure 1: the task of
language modelling can be viewed as the traversal of a tree where the nodes
are (partial) sequences.

A central quantity of interest is the occupancy measure. We denote by $s_{t}$
the random variable consisting of the state at time $t$ under a policy
$p(a|s)$ and the MDP defined above. Then, the occupancy measure
$\rho(s,a):\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ is the (discounted)
probability of observing a particular sentence $s$ at time $t$ and taking
action $a$ given that sentence:

$\displaystyle\rho(s,a)=(1-\gamma)p(a|s)\sum_{t}\gamma^{t}P(s_{t}=s)$ (3)

In other words, the occupancy measure is proportional to the observed
frequency of a particular (sentence, next-action) pair occurring, with
occurrances discounted in time by a factor of $\gamma$. In the absence of
editing actions, $\mathcal{A}=X$ and the occupancy measure is a discounted
probability over (partial) sequences: for a sequence $s_{n}$ of length $n$,
$\rho_{\text{data}}(s_{n},x)=(1-\gamma)\gamma^{n}P_{\text{data}}(s^{\prime})$,
where $s^{\prime}$ is the sequence obtained by appending $x$ to $s$. Given
editing actions which can reduce the length of a sequence, the occupancy
measure becomes more complicated, as the same sequence can occur at multiple
times. For instance, if a sequence has length $n$ at time $n$ and the
<backspace> action is used, the sequence at time $n+1$ will have length $n-1$.
We note that the occupancy measure is a normalized probability distribution,
even if editing actions are included. For a function $r$, the expectation with
respect to $\rho$ has the usual meaning:
$\mathbb{E}_{(s,a)\sim\rho}\left[r(s,a)=\sum_{\mathcal{S},\mathcal{A}}\rho(s,a)r(s,a)\right]$,
where the sum is over the discrete action space and (countably infinite) state
space. Occupancy measures provide an alternative way of modelling sequences,
allowing us to impose a measure over all sequences, even in the presence of
editing actions. As such, we avoid the somewhat artificial treatment with a
maximum length cut-off discussed in section 2.1, and can handle infinite
sequences in a natural manner. Furthermore, the next section illustrates that
we can non-adversarially minimize a large variety of divergences between
occupancy measures, compared to only the KL divergence in the typical joint
probability formulation.

###  3.2 Minimizing Occupancy Divergences

Our aim is to learn a policy $p_{\theta}(a|s)$ which induces an occupancy
measure $p_{\theta}$ such that it is close to the data occupancy measure
$p_{\text{data}}$. We define the data occupancy measure by forming the data
policy $p_{\text{data}}(a|s)$ corresponding to the conditionals
$P_{\text{data}}(x|s_{n})$ and setting the probability of editing actions to
zero. It is known that matching occupancy measures implies matching policies:
if $\rho_{\theta}=\rho_{\text{data}}$ for a valid occupancy $\rho_{\theta}$,
then the corresponding $p_{\theta}(a|s)=P_{\text{data}}(a|s)$ [33]. Therefore,
it is reasonable to minimize divergences between occupancy measures. We extend
the derivations in Garg et al. [11] to the case with infinite-dimensional
state space. We consider distances between occupancy divergences parameterized
by the following form:

$\displaystyle
d_{\psi}(\rho_{\theta},\rho_{\text{data}})=\sup_{r\in\mathcal{R}}\mathbb{E}_{(s,a)\sim\rho_{\theta}}\left[r(s,a)\right]-\mathbb{E}_{(s,a)\sim\rho_{\text{data}}}\left[r(s,a)\right]-\psi(r),$

where $\psi$ is a convex regularizer. The critic $r$ picks out any differences
between the occupancies, while if $\rho_{\theta}=\rho_{\text{data}}$, the
difference in expectations will be zero for any $r$. This family of
divergences might seem restrictive, but show in the appendix that it includes
all $f$-divergences such as the KL and JS-divergence, as well as the
Wasserstein distance and MMD. The divergence minimization problem can be made
tractable by adding an entropy term:

$\displaystyle\inf_{\theta}d_{\psi}(\rho_{\theta},\rho_{\text{data}})-\alpha
H[\rho_{\theta}],$ (4)

with the entropy
$H[\rho_{\theta}]=-\mathbb{E}_{(s,a)\sim\log\rho_{\theta}}\left[\log\rho_{\theta}(s,a)\right]$,
and $\alpha$ a chosen regularization strength. Substituting in the definition
of $d_{\psi}$, we obtain the min-max problem
$\inf_{\rho_{\theta}}\sup_{r}L(\theta,r)=\inf_{\rho_{\theta}}\sup_{r}r\cdot(\rho_{\theta}-\rho_{\text{data}})-\psi(r)-\alpha
H\left[\rho_{\theta}\right]$. We prove in the appendix that the saddle-point
property in [14] extends to our infinite-dimensional case, so
$\inf_{\rho_{\theta}}\sup_{r}L(\theta,r)=\sup_{r}\inf_{\rho_{\theta}}L(\theta,r)$.
We can interpret the outer maximization as finding a critic [20] $r$ for
sequences and actions $s,a$ such that the model has high values on examples
from the dataset and low values on the examples from the learned model: i.e.
it is a discriminator. The inner minimization over $\theta$ is an entropy-
regularized minimization of the KL-divergence between $\rho_{\theta}$ and $r$.
If we were to approach this directly by explicitly learning $r$ and
$\rho_{\theta}$, we would have an objective similar to a GAN [12]. This is
known to be difficult to train [16]. Instead, we are able to solve the problem
with optimization over a single variable by a transformation of variables. In
the following section, we recover an objective $\mathcal{J}$ which is
equivalent to the objective in equation (4), but only involves optimization
over the logits of a policy. We will set $\alpha=1$ in the next section, with
the understanding that we can recover the original objective by scaling $r$
and $\psi$ by $1/\alpha$.

####  3.2.1 Reformulating the Occupancy Divergence Minimization Problem

We first introduce the $Q$-function, corresponding to the discounted rewards
obtained in state $s$ by taking action $a$. Formally we define it as the
unique fixed point of the soft Bellman operator $\mathcal{B}_{r}^{\theta}$,
where
$\mathcal{B}_{r}^{\theta}Q(s,a)=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathcal{P}(s,a)}\left[V^{\theta}(s^{\prime})\right]$,
for the value function $V^{\theta}(s)=\mathbb{E}_{a\sim
p_{\theta}(\cdot|s)}\left[Q(s,a)-\log p_{\theta}(a|s)\right]$. The inverse
Bellman operator $\mathcal{T}^{\theta}$ is the inverse of this operator, given
by
$(\mathcal{T}^{\theta}Q)(s,a)=Q(s,a)-\gamma\mathbb{E}_{s^{\prime}\sim\mathcal{P}(s,a)}\left[V^{\theta}(s^{\prime})\right]$.
For a fixed policy $\theta$, there is a one-to-one correspondence between $r$
and $Q$ via the Bellman and inverse Bellman operators (proved in the
appendix). Crucially, for the unique occupancy $\rho^{*}$ which solves
$\max_{\theta}\mathbb{E}_{s,a\sim\rho_{\theta}}\left[r(s,a)\right]-H[\rho_{\theta}]$,
the optimal policy $p^{*}(a|s)$ corresponding to $\rho^{*}$ is proportional to
the corresponding $Q$-values $Q^{*}$: $\log
p^{*}(a|s)=Q^{*}(s,a)-V^{\theta^{*}}(s)=Q^{*}(s,a)-\log\sum_{a^{\prime}\in\mathcal{A}}\exp
Q^{*}(s,a^{\prime})$. The key idea of the following derivations is that the
optimal policy is uniquely determined by the optimal $Q$-values, while the
reward has a one-to-one correspondence with the $Q$-values. This allows us to
optimize solely over $Q$-values. We can now write a chain of equalities
involving our loss.

######  Proposition 3.1.

The following equalities hold for the loss:

$\displaystyle\inf_{\theta}d_{\psi}(\rho_{\theta},\rho_{\text{data}})-H[\rho_{\theta}]$
$\displaystyle=\sup_{r}\inf_{\theta}\mathbb{E}_{s,a\sim\rho_{\text{data}}}\left[r(s,a)\right]-\mathbb{E}_{s,a\sim\rho_{\theta}}\left[r(s,a)\right]-H[\rho_{\theta}]-\psi(r),$
$\displaystyle=\sup_{Q}\inf_{\theta}\mathbb{E}_{s,a\sim\rho_{\text{data}}}\left[(\mathcal{T}^{\theta}Q)(s,a)\right]-\mathbb{E}_{s,a\sim\rho_{\theta}}\left[(\mathcal{T}^{\theta}Q)(s,a)\right]-H[\rho_{\theta}]-\psi(\mathcal{T}^{\theta}Q),$
$\displaystyle=\sup_{Q}\inf_{\theta}\mathbb{E}_{s,a\sim\rho_{\text{data}}}\left[(\mathcal{T}^{\theta}Q)(s,a)\right]-(1-\gamma)\mathbb{E}_{s_{0}\sim\mathcal{P}_{0}}\left[V^{\theta}(s_{0})\right]-\psi(\mathcal{T}^{\theta}Q),$
$\displaystyle=\sup_{Q}\inf_{\theta}\mathbb{E}_{s,a\sim\rho_{\text{data}}}\left[\phi(Q(s,a)-\gamma\mathbb{E}_{s^{\prime}\sim\mathcal{P}(\cdot|s,a)}\left[V^{\theta}(s^{\prime})\right])\right]-(1-\gamma)\mathbb{E}_{s_{0}\sim\mathcal{P}_{0}}\left[V^{\theta}\left(s_{0}\right)\right],$
$\displaystyle=\sup_{Q}\inf_{\theta}\mathbb{E}_{s,a\sim\rho_{\text{data}}}\left[\phi(Q(s,a)-\gamma\mathbb{E}_{s^{\prime}\sim\mathcal{P}(\cdot|s,a)}\left[V^{\theta}(s^{\prime})\right])\right]-\mathbb{E}_{s,s^{\prime}\sim\rho}\left[V^{\theta}(s)-\gamma
V^{\theta}(s^{\prime})\right],$
$\displaystyle=\sup_{Q}\mathcal{J}(Q)=\sup_{Q}\mathbb{E}_{s,a\sim\rho_{\text{data}}}\left[\phi(Q(s,a)-\gamma\mathbb{E}_{s^{\prime}\sim\mathcal{P}(\cdot|s,a)}\left[V(s^{\prime})\right])\right]-\mathbb{E}_{s,s^{\prime}\sim\rho}\left[V(s)-\gamma
V(s^{\prime})\right],$

where $\phi$ is a concave function and $\mathbb{E}_{s,s^{\prime}\sim\rho}$
denotes an expectation over sampled states $s$ and successor states
$s^{\prime}$, for any occupancy $\rho$. $V(s)$ (without $\theta$) is given by
$V(s)=\log\sum_{a^{\prime}\in\mathcal{A}}\exp Q(s,a^{\prime})$

###### Proof.

The full proof is given in detail in the appendix. As a sketch, the first
equality holds from the previous section. The second is obtained by replacing
$r$ with $\mathcal{T}^{\theta}Q$ and verifying that the two optimization
problems are equal. The third line is via a telescoping sum argument first
described in [18]. In the fourth line we replace $\psi(r)$ with a simpler
regularizer $\mathbb{E}_{s,a\sim\rho_{\text{data}}}\left[g(r(s,a))\right]$,
where $g(r)=r-\phi(r)$ if $r\in\Omega$, and infinity otherwise. In the fifth
line we expand the telescoping sum in a different way, allowing us to
incorporate samples from any policy. In the final line we parameterize the
policy from the $Q$-values, setting $\log
p_{Q}(a|s)=Q(s,a)-\log\sum_{a^{\prime}\in\mathcal{A}}\exp Q(s,a^{\prime})$. We
then show that the optimization problem over $(Q,p_{Q})$ has the same optimum
as the optimization over $Q,\theta$, allowing us to eliminate $\theta$ from
the optimization entirely. ∎

Because the $Q$-value directly gives the logits of the optimal policy via
$\log p_{Q}(a|s)=Q(s,a)-\log\sum_{a^{\prime}\in\mathcal{A}}\exp
Q(s,a^{\prime})$, we relabel $Q$ as $\ell_{\theta}$ to make the connection to
logits more clear. This results in the fully supervised objective over the
logits of a policy $\ell_{\theta}$

$\displaystyle\mathcal{J}(\ell_{\theta})=$
$\displaystyle\frac{1}{\alpha}\mathbb{E}_{s,a,s^{\prime}\sim\rho_{\text{data}}}\left[\phi(\alpha\ell_{\theta}(a|s)-\alpha\gamma
V(s^{\prime})\right]-\frac{1}{2}\mathbb{E}_{s,s^{\prime}\sim\rho_{\text{data}}}\left[V(s)-\gamma
V(s^{\prime})\right]$ (6)
$\displaystyle-\frac{1}{2}\mathbb{E}_{s,s^{\prime}\sim\rho_{\theta}}\left[V(s)-\gamma
V(s^{\prime})\right],$

where $(s,a,s^{\prime})\sim\rho$ corresponds to sampling $s,a$ from $\rho$ and
$s^{\prime}$ from $\mathcal{P}(\cdot|s,a)$. The value function is
$V(s)=\log\sum_{a^{\prime}\in\mathcal{A}}\exp\ell_{\theta}(a^{\prime}|s)$.

Minimizing this objective is the same as solving
$\min_{\theta}d_{\psi}(\rho_{\theta},\rho_{\text{data}})-\alpha
H[\rho_{\theta}]$, where $d_{\psi}(P,Q)=\sup_{r\in\Omega}\mathbb{E}_{x\sim
P}\left[\phi(r(x))\right]-\mathbb{E}_{x\sim Q}\left[r(x)\right]$. By choosing
$\Omega$ and $\phi$, we can recover $f$-divergences by referencing equation
(1), including KL, JS and $\chi^{2}$ divergences, and the Wasserstein and MMD
distances. The corresponding choices are given in the appendix.

##  4 Practical Occupancy Matching with Autoregressive Sequence Models

Figure 2: Attention masks, position IDs, inputs and labels for states and
actions. Transforming states and actions to single-pass inputs allows parallel
computation of logits for all (state, action) pairs.

In practice, we wish to train a parameterized model $p_{\theta}(a|s)$ which
can serve as a policy, emitting a probability distribution over the next
action given a partially completed sequence $s$. In domains such as language,
a common choice is a transformer [35]. The transformer architecture with
parameters $\theta$ gives a probability distribution over the next token
$x_{i}$ given the previous tokens $x_{<i}$, parameterized as a set of logits
$\ell_{\theta}$. This is converted to a probability distribution as $\log
p_{\theta}(x_{i})=\ell_{\theta}(x_{i}|x_{<i})-\log\sum_{x^{\prime}\in
X}\exp\ell_{\theta}(x^{\prime}|x_{<i})$. Thus the typical MLE loss, given a
sample from the dataset of a complete sequence $x_{1:N}$, can be written as
$\mathcal{\hat{L}}_{\text{MLE}}(\ell_{\theta})=\sum_{i=1}^{N}\ell(x_{i}|x_{<i})-\log\sum_{x^{\prime}\in
X}\exp\ell(x^{\prime}|x_{<i})$. We can write this using the value function
notation as
$\mathcal{\hat{L}}_{\text{MLE}}(\ell_{\theta})=\sum_{i=1}^{N}\ell(x_{i}|x_{<i})-V(x_{<i})$.

We now wish to equivalently form an estimator for the loss in equation (6). To
do this, samples from $\rho_{\theta}$ are required. We obtain these samples by
sampling complete sequences from the policy autoregressively and weighting the
partial sequence at time $t$ by a factor of $\gamma^{t}$. We similarly sample
sequences from $\rho_{\text{data}}$ by sampling complete sequences from
$P_{\text{data}}$ and weighting. We must take some care with the terminal
states, which we discuss below.

Then, given a length-N sequence of states $s_{1:N}$ from a dataset of
sequences, corresponding actions $a_{1:N}$and a generated length-$M$ sequence
$u_{1:M}$ of states from the model, we can form an estimator for the loss in
equation (6):

$\displaystyle\mathcal{\hat{J}}(\ell_{\theta})=$
$\displaystyle\underbrace{\sum_{i}^{N}\gamma^{i}\frac{1}{\alpha}\phi\left(\alpha\ell_{\theta}(a_{i}|s_{i})-\gamma\alpha
V(s_{i+1})\right)}_{\text{Penalized difference from action logit to next state
value}}-\underbrace{\sum_{i}^{N}\frac{\gamma^{i}}{2}\left[V(s_{i})-\gamma
V(s_{i+1})\right]}_{\text{State, next state value difference under data}}$
$\displaystyle-\underbrace{\sum_{i}^{M}\frac{\gamma^{i}}{2}\left[V(u_{i})-\gamma
V(u_{i+1})\right]}_{\text{State, next state value difference under
model}}+\underbrace{{\hat{\cal J}}_{\text{eos}}(\ell_{\theta})}_{\text{Loss
from completed sequences}},$ (7)

with

$\displaystyle{\hat{\cal
J}}_{\text{eos}}(\ell_{\theta})=\frac{\gamma^{N}}{\alpha(1-\gamma)}\phi\left(\alpha(1-\gamma)V(s_{N})\right)-\frac{\gamma^{N}}{2}V(s_{N})-\frac{\gamma^{M}}{2}V(u_{M}),$
(8)

and $V(s)=\log\sum_{a^{\prime}\in\mathcal{A}}\exp\ell_{\theta}(a^{\prime}|s)$.
The separate treatment of the <eos> tokens arises because we must take a sum
over the infinite timesteps in equation (3) in the terminal states with <eos>
tokens. Analytically computing this infinite sum results in the terms in
${\hat{\cal J}}_{\text{eos}}(\ell_{\theta})$. It has also been shown [1] that
minimizing the the divergence of mixtures
$D_{\chi^{2}}(\rho_{\text{data}},(\rho_{\text{data}}+\rho_{\theta})/2)$ is
more effective than simply minimizing the $\chi^{2}$-divergence between model
and data. This can be implemented by calculating the loss for the
$\chi^{2}$-divergence (with $\phi(x)=x-\tfrac{1}{4\alpha}x^{2}$) and adding an
additional regularization term
$\mathbb{E}_{s,a,s^{\prime}\sim\rho_{\theta}}\left[(\alpha\ell_{\theta}(a|s)-\gamma\alpha
V(s^{\prime}))^{2}\right]$.

While the overall objective $\mathcal{\hat{J}}(\ell_{\theta})$ may look
similar to the MLE estimator due to the $\ell_{\theta}(a|s)-\gamma
V(s)=\ell_{\theta}(a|s)-\gamma\log\sum_{a^{\prime}\in\mathcal{A}}\exp\ell_{\theta}(a^{\prime}|s^{\prime})$
term, it should be stressed that the normalization is with respect to the next
sequence state, as opposed to the MLE loss which normalizes according to the
current sequence state.

While the loss $\mathcal{J}(\ell_{\theta})$ may look obscure, it is
instructive to take the limit as $\alpha\to 0$ for the $\phi$ corresponding to
the KL-divergence. We show in the appendix that we do indeed have
$\lim_{\alpha\to
0}\mathcal{J}_{\ell_{\theta}}=\operatorname{D_{\text{KL}}}(\rho_{\text{data}}\|\rho_{\theta})$.
The equality follows by approximating $\frac{1}{\alpha}\phi(\alpha
x)=x\phi^{\prime}(0)+\mathcal{O}(\alpha)$ if $\phi$ has a Taylor expansion at
0, which allows a linearization of $\phi$ and simplifications. We also show
that in the absence of editing actions,
$\operatorname{D_{\text{KL}}}(\rho_{\text{data}}\|\rho_{\theta})$ reduces to a
$\gamma$-reweighted MLE objective.

###  4.1 Relative Efficiency of Generating During Training

Our loss as presented requires sampling from the model during training.
Sampling is generally much slower than computing the logits. Even when using
caching to reduce unnecessary recomputations, the time taken to sample from
the model will scale with the expected length of the sequence. However, the
sequences do not need to be exactly sampled from the current policy. Since any
policy can be used, we can keep sequences generated from the policy at
previous training steps, stored in a replay buffer [22]. We give an empirical
analysis of the overhead when using SequenceMatch in the appendix.

###  4.2 Efficient Implementation of Backspace with Editing Actions

Editing actions which can delete previous parts of the input are challenging
to implement while retaining the fast training of transformer-based
autoregressive models. For instance, the sequence of actions [a; b;
<backspace>] cannot be fed directly into a policy network $p_{\theta}(a|s)$,
since it contains actions, not states. The sequence [a; b; <backspace>] is not
a valid state: the corresponding state is [<begin-sentence> a].

In order to convert this into a form where we can compute the relevant logits
using masked attention, we must pre-process the sequence of actions into
corresponding inputs, labels, masks and position IDs using algorithm A in the
appendix. The preprocessing is illustrated in figure 2. On the other hand,
generation with <backspace> actions is straightforward: we already keep
previous key-value cached values for generation with transformers. When
<backspace> is sampled, we simply roll back the state of the key-value cache
and position id with negligible overhead.

###  4.3 Augmenting Expert Sequences with Backspace

To provide the policy with examples of how the <backspace> token should be
used, we augment the data sequences as follows: with (small) probability
$\eta$, we replace a sequence $\ldots,x_{i-1},x_{i},x_{i+1},\ldots$ with
$x_{i-1},x_{i},x_{i}^{\prime},$ <backspace>$,x_{i+1},\ldots$, where
$x_{i}^{\prime}$ is chosen randomly from the vocabulary. However, we keep the
action at position $i$ as $x_{i+1}$, with the result that the overall MDP is
augmented with a stochastic dynamics: with probability $\eta$ a random token
is inserted, instead of the chosen action. We also apply this to sequences
which exceed the context length: the action is kept the same but the next
token is forced to be the <eos> token. This introduces bias, as the policy
learns to match the data distribution under a slightly different MDP than
generation takes place in. In practice however, it leads to improved
performance compared to the policy learning with no examples of <backspace>.

Input : Dataset $\mathcal{D}$ of data sequences, gradient-based optimizer
step, number of train steps $n_{\text{train}}$, parameters
$\alpha,\beta,\gamma,\phi$, sampling interval $k_{\text{sample}}$, fixed
context length $T$

Add noise and process data sequences with algorithm A to form new effective
trajectories

Initialize buffer $\mathcal{B}$ of model sequences; Initialize autoregressive
policy $\ell_{\theta}(\cdot|s)$

for  _$k$ in $n_{\text{train}}$_ do

if  _$k\mod k_{\text{sample}}=0$_ then

Populate $\mathcal{B}$ with trajectories $\mathcal{T}\sim\ell_{\theta}$;
Process added sequences with algorithm A

Remove oldest model sequences from $\mathcal{B}$

end if

Sample dataset trajectories $\mathcal{T}_{\text{data}}\sim\mathcal{D}$ and
model trajectories $\mathcal{T}_{\text{model}}\sim\mathcal{B}$

Compute $g=\nabla_{\theta}{\hat{\cal
J}}(\ell_{\theta},\alpha,\gamma,\mathcal{T}_{\text{data}},\mathcal{T}_{\text{model}})$
and update $\theta$ via step using gradient $g$

end for

Algorithm 1 Training an autoregressive model against a SequenceMatch objective

##  5 Related Work

##### Text Degeneration in Large Language Models

In natural language processing (NLP) the phenomenon of _text degeneration_ can
occur, when a language model produces repetitive or nonsensical sequences
[15]. Many explanations have been proposed to explain this phenomenon [10,
37]; a leading theory is that the large vocabulary size induces the model to
over-estimate the probability of out-of-distribution (OOD) tokens. Once these
tokens are sampled, the model’s context is now out-of-distribution.

Measures to mitigate this problem include top-$k$ sampling [9], restricting
generations to the $k$ most likely tokens, and top-$p$ sampling [15], an
adaptive variant of top-$k$ sampling. In addition, several alternative
training measures have been proposed to reduce the probability of the model
producing OOD tokens. Unlikelihood training [37] is discussed in detail in the
appendix, while contrastive methods have also been proposed [17], which force
the representations of repetitive text to be far from the representations of
correct text.

##### Matching Divergences in Imitation Learning

In the imitation learning[23] subfield of RL, the objective is to learn a
policy giving a distribution over actions in each state, such that the
distribution over trajectories is close to distribution of a set of provided
expert trajectories. A simple approach is behavioural cloning [8], which
maximizes the likelihood of the expert’s chosen actions, on average over the
states that the expert encounters. However, it has been shown [27] that this
simple behaviour cloning approach results in a _compounding error_ problem,
where the further the trained model gets from the typical expert states, the
worse the model performs, incurring increasing error. Ho and Ermon [14] show
that minimizing the occupancy divergence between the expert and a learned
policy could be written as a two-variable saddle-point optimization problem.
This more sophisticated method is able to take the dynamics of the problem
into account, learning a policy which can return to the typical expert states
if it erroneously leaves them. In Garg et al. [11], this was further developed
via a change of variables to only require a non-adversarial optimization over
one variable. We can view our approach as a specialization of the IQ-Learn
algorithm in Garg et al. [11] to autoregressive sequence models.

##  6 Experiments

Figure 3: MAUVE score when fine-tuning GPT2 of various sizes on the
openwebtext dataset with context length 512. Higher is better. Full and LM
Head refer to which parts of the pretrained model are trained. We see that
SequenceMatch outperforms behavioral cloning and MLE. The fully trained models
achieve much higher MAUVE scores than the variant only training the head.

We experimentally verify that SequenceMatch can lead to better generation of
sequences compared to the typical maximum-likelihood objective, when evaluated
on a language modelling task [5, 7]. Many more experimental details, code and
additional analyses are provided in the supplementary material.

##### Experimental Setup

We use the GPT-2 [25] causally-masked transformer architecture through
Huggingface [38] and Flax/Jax [13, 6]. We finetune on sequences from the
openwebtext dataset333https://github.com/jcpeterson/openwebtext, an open-
sourced dataset similar to the original GPT-2 training set. To ensure the data
was well-specified under our data generating process, we subsampled the
dataset to remove sequences that did not terminate before the end of the
context window (512 for experiments in figure 3 and 1024 for results in table
1), and padded sequences that terminated before the context length. We
consider two training regimes: Full, where all model parameters are trained,
and LM Head, where the model parameters are frozen and the final linear layer
is trained. In both cases we add an additional head depending on the
positional encodings to the model which generates an offset to the logits,
allowing a position-dependent offset to be learned. We compare a
SequenceMatch-trained model against two baselines: MLE is a model trained
against the typical MLE objective. Behavioral Cloning is a model trained with
injected noise and <backspace> labels, but the MLE objective. Due to
computational constraints we were unable to train on multiple seeds to obtain
error bars. We train for 50,000 gradient steps with the AdamW optimizer [21],
taking hyperparameters from the nanoGPT
implementation444https://github.com/karpathy/nanoGPT. We set $\alpha=0.01$,
$\eta=0.001$ and $\gamma=N/(N+1)$ for a length-$N$ context window (i.e. 0.998,
0.999 respectively). Our metric for quality of generations is the MAUVE score
[24], a non-parametric method for evaluating the quality of a generative
model. The MAUVE score is formed by taking a low-dimensional PCA of an
embedding of the generated sequences (here, a GPT2-XL encoder). The score is a
mixture of forward and reverse KLs between the data and model-generated
sequences, between zero and one (higher is better). We also report a diversity
metric [17], given by $\prod_{n=2}^{4}\left(1.0-\frac{\text{ rep
}-\mathrm{n}}{100}\right)$, where
$\text{rep-n}=100\times\left[1.0-\frac{\mid\text{ unique }\text{ n-grams
}(\hat{\boldsymbol{x}})\mid}{\mid\operatorname{total}\text{ n-grams
}(\hat{\boldsymbol{x}})\mid}\right]$ for a continuation
$\hat{\boldsymbol{x}}$.

##### Results

The results are shown in figure 3 and table 1. We observe that, as measured by
the MAUVE score, the SequenceMatch-trained models generate text that is closer
to the dataset. The SequenceMatch-trained models also outperform MLE and BC on
the diversity metric (shown in the appendix). Furthermore, the samples from
the SequenceMatch-trained model appear more fluent (random samples and
additional statistics are shown in the appendix). In table 1, we show the
result of training a GPT2-small model on the full 1024 context length case. We
observe that the SequenceMatch-trained model is outperformed on the perplexity
metric by the BC and MLE-trained methods. This is expected, as the training
objective for BC and MLE is exactly equal to the perplexity. However, on the
measures of generation quality (MAUVE score and diversity), the SM-trained
model far outperforms the baselines.

| Mauve Score ($\boldsymbol{\uparrow}$) | Perplexity ($\boldsymbol{\downarrow}$) | Diversity ($\boldsymbol{\uparrow}$) |
---|---|---|---|---
SM-$\chi^{2}$ | 0.97 | 4.69 | 0.58 |
BC | 0.55 | 4.52 | 0.44 |
MLE | 0.51 | 4.51 | 0.55 |
Table 1: A GPT-2-small model finetuned against different losses, with context
length 1024. The maximum-likelihood methods (BC and MLE) achieve good
perplexity, which measures the probability of the next token being chosen
correctly. However, they do much worse on the mauve score and diversity,
measuring quality of the generated text when sampled autoregressively.

###  6.1 Limitations and Conclusion

We address the compounding error problem in autoregressive sequence generation
by formulating the problem in the imitation learning (IL) framework, deriving
a general non-adversarial objective for minimizing divergences between
occupancy measures induced by a learned model and the data distribution. We
develop a novel masking scheme allowing training of a transformer-based
autoregressive model with a <backspace> action with small overhead vs MLE,
further reducing compounding error by facilitating backtracking. Empirically,
the SequenceMatch objective leads to improvements over MLE at text generation.
The main limitation with our method is the requirement to generate samples
autoregressively while training, which can be expensive for long contexts. We
give an empirical examination of this training overhead in the appendix. A
secondary limitation is a more complex loss and requirement to process
sequences to mask backspaces during training. Future work can investigate the
effect of training larger models against SequenceMatch objectives, as well as
how the qualities of generations change with choice of divergence.

## References

  * Al-Hafez et al. [2023] Firas Al-Hafez, Davide Tateo, Oleg Arenz, Guoping Zhao, and Jan Peters.  LS-IQ: Implicit reward regularization for inverse reinforcement learning.  In _The Eleventh International Conference on Learning Representations_ , 2023.
  * Arjovsky et al. [2017] Martin Arjovsky, Soumith Chintala, and Léon Bottou.  Wasserstein generative adversarial networks.  In _International Conference on Machine Learning_ , pages 214–223. PMLR, 2017.
  * Arora et al. [2022] Kushal Arora, Layla El Asri, Hareesh Bahuleyan, and Jackie Chi Kit Cheung.  Why Exposure Bias Matters: An Imitation Learning Perspective of Error Accumulation in Language Generation.  In _Findings of the Association for Computational Linguistics: ACL 2022_ , pages 700–710, 2022.
  * Barde et al. [2020] Paul Barde, Julien Roy, Wonseok Jeon, Joelle Pineau, Chris Pal, and Derek Nowrouzezahrai.  Adversarial soft advantage fitting: Imitation learning without policy optimization.  In _Advances in Neural Information Processing Systems_ , volume 33, pages 12334–12344, 2020.
  * Bommasani et al. [2021] Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al.  On the opportunities and risks of foundation models.  _arXiv preprint arXiv:2108.07258_ , 2021.
  * Bradbury et al. [2020] James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, and Skye Wanderman-Milne.  JAX: Composable transformations of Python+NumPy programs{}, 2020.
  * Brown et al. [2020] Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language Models are Few-Shot Learners.  _arXiv:2005.14165 [cs]_ , July 2020.
  * Esmaili et al. [1995] Nasser Esmaili, Claude Sammut, and GM Shirazi.  Behavioural cloning in control of a dynamic system.  In _1995 IEEE International Conference on Systems, Man and Cybernetics. Intelligent Systems for the 21st Century_ , volume 3, pages 2904–2909. IEEE, 1995.
  * Fan et al. [2018] Angela Fan, Mike Lewis, and Yann Dauphin.  Hierarchical neural story generation.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 889–898, 2018\.
  * Fu et al. [2021] Zihao Fu, Wai Lam, Anthony Man-Cho So, and Bei Shi.  A theoretical analysis of the repetition problem in text generation.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 35, pages 12848–12856, 2021.
  * Garg et al. [2021] Divyansh Garg, Shuvam Chakraborty, Chris Cundy, Jiaming Song, and Stefano Ermon.  IQ-Learn: Inverse soft-Q learning for imitation.  In _NeurIPS_ , 2021.
  * Goodfellow et al. [2014] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial networks.  _Neural Information Processing Systems (NeurIPS)_ , 2014.
  * Heek et al. [2020] Jonathan Heek, Anselm Levskaya, Avital Oliver, Marvin Ritter, Bertrand Rondepierre, Andreas Steiner, and Marc van Zee.  Flax: A neural network library and ecosystem for JAX, 2020.
  * Ho and Ermon [2016] Jonathan Ho and Stefano Ermon.  Generative adversarial imitation learning.  _Advances in neural information processing systems_ , 29, 2016.
  * Holtzman et al. [2019] Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi.  The curious case of neural text degeneration.  In _International Conference on Learning Representations_ , 2019.
  * Jabbar et al. [2020] Abdul Jabbar, Xi Li, and Bourahla Omar.  A Survey on Generative Adversarial Networks: Variants, Applications, and Training.  _arXiv:2006.05132 [cs]_ , June 2020.
  * Jiang et al. [2022] Shaojie Jiang, Ruqing Zhang, Svitlana Vakulenko, and Maarten de Rijke.  A simple contrastive learning objective for alleviating neural text degeneration.  _arXiv preprint arXiv:2205.02517_ , 2022.
  * Kostrikov et al. [2019] Ilya Kostrikov, Ofir Nachum, and Jonathan Tompson.  Imitation learning via off-policy distribution matching.  In _International Conference on Learning Representations_ , 2019.
  * Kwon et al. [2021] Dohyun Kwon, Yeoneung Kim, Guido Montúfar, and Insoon Yang.  Training Wasserstein GANs without gradient penalties.  _arXiv:2110.14150 [cs, math]_ , October 2021.
  * LeCun et al. [2006] Yann LeCun, Sumit Chopra, Raia Hadsell, Marc’Aurelio Ranzato, and Fu Jie Huang.  A Tutorial on Energy-Based Learning, 2006.
  * Loshchilov and Hutter [2019] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  In _International Conference on Learning Representations_ , 2019.
  * Mnih et al. [2013] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller.  Playing Atari with Deep Reinforcement Learning, 2013.
  * Ng and Russell [2000] Andrew Y Ng and Stuart Russell.  Algorithms for inverse reinforcement learning.  In _In Proc. 17th International Conf. on Machine Learning_. Citeseer, 2000.
  * Pillutla et al. [2022] Krishna Pillutla, Lang Liu, John Thickstun, Sean Welleck, Swabha Swayamdipta, Rowan Zellers, Sewoong Oh, Yejin Choi, and Zaid Harchaoui.  MAUVE scores for generative models: Theory and practice.  _arXiv preprint arXiv:2212.14578_ , 2022.
  * Radford et al. [2018] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever.  Language models are unsupervised multitask learners, 2018.
  * Rizzolo and Su [2007] Douglas Rizzolo and Francis Edward Su.  A fixed point theorem for the infinite-dimensional simplex.  _Journal of mathematical analysis and applications_ , 332(2):1063–1070, 2007.
  * Ross et al. [2011] Stéphane Ross, Geoffrey Gordon, and Drew Bagnell.  A reduction of imitation learning and structured prediction to no-regret online learning.  In _AISTATS_ , pages 627–635, 2011.
  * Shi et al. [2018] Zhan Shi, Xinchi Chen, Xipeng Qiu, and Xuanjing Huang.  Toward Diverse Text Generation with Inverse Reinforcement Learning.  _arXiv:1804.11258 [cs, stat]_ , June 2018.
  * Sion [1958] Maurice Sion.  On general minimax theorems.  _Pacific Journal of Mathematics_ , 8(4):171–176, 1958.
  * Song and Ermon [2019] Yang Song and Stefano Ermon.  Generative modeling by estimating gradients of the data distribution.  In _Advances in Neural Information Processing Systems_ , volume 32, 2019.
  * Song et al. [2021] Yang Song, Jascha Sohl-Dickstein, Diederik P. Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole.  Score-Based Generative Modeling through Stochastic Differential Equations.  _arXiv:2011.13456 [cs, stat]_ , February 2021.
  * Swamy et al. [2021] Gokul Swamy, Sanjiban Choudhury, Zhiwei Steven Wu, and J. Andrew Bagnell.  Of Moments and Matching: Trade-offs and Treatments in Imitation Learning.  _arXiv:2103.03236 [cs, stat]_ , March 2021.
  * Syed et al. [2008] Umar Syed, Michael Bowling, and Robert E Schapire.  Apprenticeship learning using linear programming.  In _Proceedings of the 25th International Conference on Machine Learning_ , pages 1032–1039, 2008.
  * Tang [2020] Shichang Tang.  Lessons Learned from the Training of GANs on Artificial Datasets.  _arXiv:2007.06418 [cs, stat]_ , July 2020.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In _Advances in Neural Information Processing Systems_ , volume 30, 2017.
  * Weissenborn et al. [2020] Dirk Weissenborn, Oscar Täckström, and Jakob Uszkoreit.  Scaling autoregressive video models.  In _International Conference on Learning Representations_ , 2020.
  * Welleck et al. [2019] Sean Welleck, Ilia Kulikov, Stephen Roller, Emily Dinan, Kyunghyun Cho, and Jason Weston.  Neural text generation with unlikelihood training.  In _International Conference on Learning Representations_ , 2019.
  * Wolf et al. [2019] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al.  Huggingface’s transformers: State-of-the-art natural language processing.  _arXiv preprint arXiv:1910.03771_ , 2019.

##  Appendix A Algorithm A

Input : Sequence of action inputs $a_{1:L}$

output : Sequence of labels, inputs, masks, position ids
$y\in|V|^{L},x\in|V|^{L},m\in\\{0,1\\}^{L\times L},p\in[L]^{L}$

Initialize $y,m,p$ to zero.

Initialize $x$ to $a$.

Initialize $c=0$

// Copy Pointer

Initialize $d=0$

// Deletion Pointer

for  _$i=0,\ldots L$_ do

$m[i]\leftarrow m[\max{(i-1,0)}]$

if  _$a[i]=$ <backspace>_ then

$m[i,c]\leftarrow 0$

$m[i,d]\leftarrow 0$

$m[i,i]\leftarrow 1$

$x[i]\leftarrow x[c]$

$p[i]\leftarrow p[c]$

$d\leftarrow i$

$c\leftarrow$ element of last nonzero element in $m[i,0:c]$, else 0.

end if

else

$m[i,i]\leftarrow 1$

$d\leftarrow d+1$

$c\leftarrow$ element of first nonzero element in $m[i,c+1:L]$, else 0.

$p[i]\leftarrow p[d-1]+1$

end if

if  _$i=0$_ then

$c\leftarrow 0$

// Special cases for initial steps

$d\leftarrow 0$

end if

if  _$i=1$_ then

$c\leftarrow 0$

$d\leftarrow 1$

end if

end for

Algorithm 2 Algorithm A: Pseudocode for converting action sequences to masked
inputs

In algorithm A we give a method to convert a sequence of actions into a masked
sequence of inputs and corresponding labels, masks and position ids. Although
it can also be implemented in a stack-based fashion, we write it as an
imperative algorithm so it can be compiled with the jit operation in JAX or
the compile operation in PyTorch. Recall that the idea is to replace a
sequence of actions with a sequence of inputs and corresponding labels, masks
and position ids. The input sequence at position $t$ should correspond to the
state at position $t$ (when the corresponding mask is applied) and the label
at position $t+1$ is the action taken at position $t$. A consequence of this
is that the inputs should never include a <backspace> token. The main idea is
that if we have a sequence of actions [..., a, b, <backspace>, ...], the
corresponding inputs are [..., a, b, a, ...], while the masks for the second a
onwards mask out the first a, b. However, the possibility of multiple
backspaces introduces some complexity.

The approach of the algorithm is to keep a running copy pointer and deletion
pointer. The deletion pointer points to the cell of the mask that must be
zeroed out for subsequent positions in the sequence, while the copy pointer
points to the position that must be copied to the current cell of the input
(and also zeroed out in the mask). When a backspace occurs, the deletion
pointer is set to the current index, and the copy pointer is sent backwards to
the last non-deleted position. When a backspace doesn’t occur, the deletion
pointer is incremented by 1 and the copy pointer is moved forwards to the
first non-deleted position.

##  Appendix B Motivating Example Algebra

We consider the case of a length- $n$ Markov chain with an additional node
coming from each node. These nodes correspond to the dashed nodes in figure 1.
We write the dashed nodes as $x_{\text{term}}$. As in the figure, we have
$P_{\text{data}}(x_{\text{term}})=0$,
$P_{\text{model}}(x_{\text{term}})=\epsilon$. We wish to compute the
divergence between the two distributions.

###  B.1 KL-Divergence

We have

$\displaystyle\operatorname{D_{\text{KL}}}(P\|Q)=\mathbb{E}_{x\sim
P}\left[\log P(x)-\log Q(x)\right]=-n\log Q(1-\epsilon).$

###  B.2 Reverse KL-Divergence

We have

$\displaystyle\operatorname{D_{\text{KL}}}(Q\|P)=\mathbb{E}_{x\sim
Q}\left[\log Q(x)-\log P(x)\right]=\infty,$

since $P(x_{\text{term}}=0)$ and $Q(x_{\text{term}})\neq 0$.

###  B.3 $\chi^{2}$-Divergence

We have

$\displaystyle\operatorname{D_{\chi^{2}}}(Q,P)=\mathbb{E}_{x\sim
Q}\left[\left(\frac{P(x)}{Q(x)}-1\right)^{2}\right]$

##  Appendix C Proofs for section 3.2

###  C.1 Proof for Saddle Point Theorem

We wish to show that

$\inf_{\rho_{\theta}}\sup_{r}L(\theta,r)=\sup_{r}\inf_{\rho_{\theta}}L(\theta,r).$

Now, the set $\mathcal{D}$ of occupancy measures stemming from conditionals is
compact and convex, since it is formed from linear constraints: firstly
$\rho\geq 0$, and secondly
$\sum_{a}\rho(s,a)=\gamma\sum_{s^{\prime}}\rho(s^{\prime},a)P(s|s^{\prime},a),\forall
s,s^{\prime}$. Because $\mathcal{D}$ is a closed subset of the infinite-
dimensional simplex $\Delta^{\infty}_{0}$, which is compact [26],
$\mathcal{D}$ is also compact. The set $\mathcal{R}$ is convex, since it
consists of all sequences. Since the inner function is convex in
$\rho_{\theta}$ and concave in $r$, we can apply Sion’s minimax theorem [29]
to swap the inner inf and sup.

###  C.2 Proof for Bijection between $r$ and $Q$

Recall that we define the Bellman operator as $\mathcal{B}_{r}^{\theta}$,
where
$\mathcal{B}_{r}^{\theta}Q(s,a)=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim\mathcal{P}(s,a)}\left[V^{\theta}(s^{\prime})\right]$,
for the value function $V^{\theta}(s)=\mathbb{E}_{a\sim
p_{\theta}(\cdot|s)}\left[Q(s,a)-\log p_{\theta}(a|s)\right]$. The inverse
Bellman operator $\mathcal{T}^{\theta}$ is defined as
$(\mathcal{T}^{\theta}Q)(s,a)=Q(s,a)-\gamma\mathbb{E}_{s^{\prime}\sim\mathcal{P}(s,a)}\left[V^{\theta}(s^{\prime})\right]$.

######  Theorem C.1.

For a fixed policy $\theta$, the inverse soft Bellman operator
$\mathcal{T}^{\theta}$ is bijective, and for any $r\in\mathcal{R}$,
$Q=(\mathcal{T}^{\theta})^{-1}r$ is the unique fixed point of the Bellman
operator $\mathcal{B}_{r}^{\theta}$.

###### Proof.

The proof is very similar to the proof of lemma 3.2 in Garg et al. [11]. We
construct an infinite matrix
$P^{\theta}\in\mathbb{R}^{(\mathcal{S}\times\mathcal{A})\times(\mathcal{S}\times\mathcal{A})}$,
where
$(P^{\theta}f)(s,a)=\mathbb{E}_{s^{\prime}\sim\mathcal{P}(\cdot|s,a),a^{\prime}\sim
p_{\theta}(\cdot|s^{\prime})}\left[f(s^{\prime},a^{\prime})\right]$. The
matrix $P^{\theta}$ corresponds to the transition matrix for the given MDP and
the policy $\theta$. We then have $r=\mathcal{T}^{\theta}Q$, for any $Q$.
Then, $\boldsymbol{r}=\boldsymbol{Q}-\gamma
P^{\theta}(\boldsymbol{Q}-\log\boldsymbol{p_{\theta}})$. Rearranging, we get
$\boldsymbol{Q}=(I-\gamma
P^{\theta})^{-1}(\boldsymbol{r}-\log\boldsymbol{p_{\theta}})+\log\boldsymbol{p_{\theta}}$.
We can do this since $|\gamma P^{\theta}|_{\infty}<1$ if $\gamma<1$, and so
$I-\gamma P^{\theta}$ is invertible, even in this infinite-dimensional
setting. We also see that $\boldsymbol{Q}$ has a unique vector expansion
$\boldsymbol{Q}=\boldsymbol{r}+\gamma
P^{\theta}(\boldsymbol{Q}-\log\boldsymbol{p_{\theta}})$. Since this is the
(unique) vector expansion of $\mathcal{B}_{r}^{\theta}$, we have
$Q=(\mathcal{T}^{\theta})r=\mathcal{B}_{r}^{\theta}Q$ ∎

###  C.3 Telescoping Sum Proofs

In this section we prove various theorems related to telescoping sums and
value functions. These mostly follow from Kostrikov et al. [18] and [11].

######  Proposition C.2.

For a policy $p_{\theta}$, initial state distribution $\mathcal{P}_{0}$, value
function $V^{\theta}(s)=\mathbb{E}_{a\sim
p_{\theta}(\cdot|s)}\left[Q(s,a)-\log p_{\theta}(a|s)\right]$, the following
identities hold:

$\displaystyle\mathbb{E}_{s,a\sim\rho_{\theta}}\left[(\mathcal{T}^{\theta}Q)(s,a)\right]+H[\rho_{\theta}]$
$\displaystyle=(1-\gamma)\mathbb{E}_{s_{0}\sim\mathcal{P}_{0}}\left[V^{\theta}(s_{0})\right]$
(9) $\displaystyle=\mathbb{E}_{s,s^{\prime}\sim\rho}\left[V^{\theta}(s)-\gamma
V^{\theta}(s^{\prime})\right],$ (10)

where $\rho$ is any occupancy measure, and $s,s^{\prime}\sim\rho$ denotes
sampling $s,a$ from $\rho$ and $s^{\prime}$ from $\mathcal{P}(a,s)$.

###### Proof.

We have

$\displaystyle\mathbb{E}_{s,a\sim\rho_{\theta}}\left[(\mathcal{T}^{\theta})Q(s,a)\right]+H\left[p_{\theta}\right]$
$\displaystyle=\mathbb{E}_{s,a\sim\rho_{\theta}}\left[Q(a,s)-\gamma\mathbb{E}_{s^{\prime}\sim\mathcal{P}(s,a)}\left[V^{\theta}(s^{\prime})\right]-\log
p_{\theta}(a|s)\right]$ (11)
$\displaystyle=\mathbb{E}_{s,s^{\prime}\sim\rho_{\theta}}\left[V^{\theta}(s)-\gamma
V^{\theta}(s^{\prime})\right].$ (12)

By the definition of the occupancy measure and expanding, we have

$\displaystyle\mathbb{E}_{s,s^{\prime}\sim\rho_{\theta}}\left[V^{\theta}(s)-\gamma
V^{\theta}(s^{\prime})\right]$
$\displaystyle=(1-\gamma)\left[\left[\mathbb{E}[V^{\theta}(s_{0})]-\gamma\mathbb{E}[V^{\theta}(s_{1})]\right]+\gamma\left[\mathbb{E}[V^{\theta}(s_{1})]-\gamma\mathbb{E}[V^{\theta}(s_{2})]+\ldots\right]\right]$
(13) $\displaystyle=(1-\gamma)\mathbb{E}[V^{\theta}(s_{0})].$ (14)

Because $s_{0}$ does not depend on $\rho$, we can expand the sum in the
opposite direction to show that
$\mathbb{E}_{s,a\sim\rho_{\theta}}\left[(\mathcal{T}^{\theta})Q(s,a)\right]+H\left[p_{\theta}\right]=\mathbb{E}_{s,s^{\prime}\sim\rho}\left[V^{\theta}(s)-\gamma
V^{\theta}(s^{\prime})\right]$ for any occupancy $\rho$. ∎

###  C.4 Proof of equivalence of solutions of $\mathcal{J}$ and $L$

We now reproduce a proposition from Garg et al. [11],

######  Proposition C.3.

In the $Q$-policy space, there exists a unique saddle point
$(p_{\theta}^{*},Q^{*})$, that optimizes $\mathcal{J}$. That is,
$Q^{*}=\operatorname*{arg\,max}_{Q\in\Omega}\min_{p_{\theta}}\mathcal{J}(p_{\theta},Q)$
and
$p_{\theta}^{*}=\operatorname*{arg\,min}_{p_{\theta}}\max_{Q\in\mathcal{O}}\mathcal{J}(p_{\theta},Q)$.
Furthermore, $p_{\theta}^{*}$ and $r^{*}=\mathcal{T}^{p_{\theta}^{*}}Q^{*}$
are the solution to the inverse RL objective $L(p_{\theta},r)$. This is
proposition 3.4 in Garg et al. [11].

###### Proof.

See Garg et al. [11] for the complete proof. The proof given applies directly
to our case. ∎

###  C.5 Proof for Theorem 3.1

We can now prove our main result

######  Proposition C.4.

With quantities defined in the main text, the following equalities hold for
the loss:

$\displaystyle\inf_{\theta}d_{\psi}(\rho_{\theta},\rho_{\text{data}})-H[\rho_{\theta}]$
$\displaystyle=\sup_{r}\inf_{\theta}\mathbb{E}_{s,a\sim\rho_{\text{data}}}\left[r(s,a)\right]-\mathbb{E}_{s,a\sim\rho_{\theta}}\left[r(s,a)\right]-H[\rho_{\theta}]-\psi(r),$
$\displaystyle=\sup_{Q}\inf_{\theta}\mathbb{E}_{s,a\sim\rho_{\text{data}}}\left[(\mathcal{T}^{\theta}Q)(s,a)\right]-\mathbb{E}_{s,a\sim\rho_{\theta}}\left[(\mathcal{T}^{\theta}Q)(s,a)\right]-H[\rho_{\theta}]-\psi(\mathcal{T}^{\theta}Q),$
$\displaystyle=\sup_{Q}\inf_{\theta}\mathbb{E}_{s,a\sim\rho_{\text{data}}}\left[(\mathcal{T}^{\theta}Q)(s,a)\right]-(1-\gamma)\mathbb{E}_{s_{0}\sim\mathcal{P}_{0}}\left[V^{\theta}(s_{0})\right]-\psi(\mathcal{T}^{\theta}Q),$
$\displaystyle=\sup_{Q}\inf_{\theta}\mathbb{E}_{s,a\sim\rho_{\text{data}}}\left[\phi(Q(s,a)-\gamma\mathbb{E}_{s^{\prime}\sim\mathcal{P}(\cdot|s,a)}\left[V^{\theta}(s^{\prime})\right])\right]-(1-\gamma)\mathbb{E}_{s_{0}\sim\mathcal{P}_{0}}\left[V^{\theta}\left(s_{0}\right)\right],$
$\displaystyle=\sup_{Q}\inf_{\theta}\mathbb{E}_{s,a\sim\rho_{\text{data}}}\left[\phi(Q(s,a)-\gamma\mathbb{E}_{s^{\prime}\sim\mathcal{P}(\cdot|s,a)}\left[V^{\theta}(s^{\prime})\right])\right]-\mathbb{E}_{s,s^{\prime}\sim\rho}\left[V^{\theta}(s)-\gamma
V^{\theta}(s^{\prime})\right],$
$\displaystyle=\sup_{Q}\mathcal{J}(Q)=\sup_{Q}\mathbb{E}_{s,a\sim\rho_{\text{data}}}\left[\phi(Q(s,a)-\gamma\mathbb{E}_{s^{\prime}\sim\mathcal{P}(\cdot|s,a)}\left[V(s^{\prime})\right])\right]-\mathbb{E}_{s,s^{\prime}\sim\rho}\left[V(s)-\gamma
V(s^{\prime})\right],$

###### Proof.

The first equality is proven in section C.1. The second line follows from
sections C.2 and C.4. The first section shows that the objectives
$\mathcal{J}(Q,\theta)$ and $L(\theta,r)$ are the same, by the bijective
property of $\mathcal{T}$. The second section proves that the (unique) saddle
points of the objectives correspond to the same solutions.

The third line follows from the telescoping sum given in section C.3. The
fourth line follows from the substitution of a general $\psi(r)$ with a
simpler regularizer
$\mathbb{E}_{s,a\sim\rho_{\text{data}}}\left[g(r(s,a))\right]$, where
$g(r)=r-\phi(r)$ if $r\in\Omega$, and infinity otherwise. This allows us to
ground out the divergence minimization directly to concrete divergences such
as the KL-divergence, JS-divergence, $\chi^{2}$-divergence, etc. We discuss
this more extensively in section D.1. In the fifth line we expand the
telescoping sum in a different way using the result in section C.3. This
allows us to incorporate samples from any policy, with the hope that it will
decrease variance.

In the final line we parameterize the policy from the $Q$-values, setting
$\log p_{Q}(a|s)=Q(s,a)-\log\sum_{a^{\prime}\in\mathcal{A}}\exp
Q(s,a^{\prime})$. The fact that
$\sup_{Q}\inf_{\theta}\mathcal{J}(p_{\theta},Q)=\sup_{Q}\mathcal{J}(p_{Q},Q)$
follows from the fact that there is a unique saddle point for
$\mathcal{J}(p_{\theta},Q)$, the fact that $\mathcal{J}(p_{Q},Q)$ is concave
in $Q$, and that the saddle point for $\mathcal{J}(p_{Q},Q)$ has a supremum in
$Q$ where $\theta=\theta^{*}$, with $\log
p_{\theta}^{*}(a|s)=Q^{*}(s,a)-\log\sum_{a^{\prime}\in\mathcal{A}}\exp
Q^{*}(s,a^{\prime})$ and $Q^{*}$ the corresponding supremum in $Q$. This
allows elimination of $\theta$ from the optimization process entirely, and
completes the proof. ∎

##  Appendix D Choices of divergence measures

###  D.1 $f$-divergences

We recall that for any $f$-divergence with $D_{f}(P,Q)=\mathbb{E}_{x\sim
Q}\left[f(P(x)/Q(x))\right]$, we have the variational form

$D_{f}(P,Q)=\sup_{\phi}\left\\{\mathbb{E}_{x\sim
P}\left[\phi(x)\right]-\mathbb{E}_{x\sim
Q}\left[f^{*}(\phi(x)\right]\right\\},$

with the convex conjugate $f^{*}(y)=\sup_{x}\left\\{x\cdot y-f(x)\right\\}$)
and a discriminator $\phi:\mathcal{X}\to\mathbb{R}$. Optimizing a model
against an $f$-divergence other than the KL-divergence typically involves a
difficult min-max optimization problem where we simultaneously improve the
model and improve the discriminator $\phi$. This is subject to unstable
training [19, 16, 34, 12].

In the main paper, we explain that we require a divergence

$\displaystyle
d_{\psi}(\rho_{\theta},\rho_{\text{data}})=\psi^{*}(\rho_{\theta}-\rho_{\text{data}}).$

With our choice of $\psi$, we get that

$\displaystyle
d_{\psi}\left(\rho,\rho_{\text{data}}\right)=\max_{r\in\mathcal{R}_{\psi}}\mathbb{E}_{s,a\sim\rho_{\text{data}}}[\phi(r(s,a))]-\mathbb{E}_{s,a\sim\rho_{\theta}}[r(s,a)]$

We can readily connect these to $f$-divergences. Recall that the variational
formulation of the $f$-divergence is

$\displaystyle D_{f}(P,Q)=\sup_{g}\left\\{\mathbb{E}_{x\sim
P}\left[g(x)\right]-\mathbb{E}_{x\sim Q}\left[f^{*}(g(x)\right]\right\\},$
(16)

so we can see that the function $\phi$ we need is simply $-f^{*}(-x)$.

###  D.2 KL-divergence

Note that we define our divergence in the reverse fashion to the usual
convention, so to obtain the typical forward KL under the expectation of the
data, we must use the reverse-KL $f$-divergence, with $f(x)=x\log x$. This
gives $\phi(x)=-e^{-(x+1)}$. However, since we can always shift an
f-divergence’s $f$ by a constant multiple of $(x-1)$ without changing the
divergence (which should be clear from observing cancellations in the
definition of the $f$ divergence), we shift by -1 and (after working through
the derivations) have a simpler $\phi(x)=-e^{-x}$.

###  D.3 Jenson-Shannon Divergence

The Jenson-Shannon divergence has $f(x)=-(x+1)\log(\frac{x+1}{2})+x\log x$.
This leads to $\phi(x)=\log(2-e^{-x})$. This is an interesting $\phi$ because
it is equal to $-\infty$ for $x<-\log 2$. Since the $x$ in this case is the
value of $r$ obtained from the model’s logits, it is certainly possible that
the value may be less than $-\log 2$. In practice, we could replace $\phi$
with a sharply descending quadratic for all $x$ close to $-\log 2$ and below.
This gives a penalizing effect on small $r$, while not causing (too many)
numerical issues.

###  D.4 $\chi^{2}$-Divergence and $\chi^{2}$-Mixture Divergence

For the $\chi^{2}$-divergence, we have $f(x)=((t-1)^{2})$, leading to
$\phi(x)=(x-x^{2}/4)$.

As described in Al-Hafez et al. [1], we can add a regularization term by
computing $\psi_{\rho}(r)=\beta
c\mathbb{E}_{\rho_{\text{data}}}\left[r(s,a)^{2}\right]+(1-\beta)c\mathbb{E}_{\rho_{\theta}}\left[r(s,a)^{2}\right]$.
In other words, instead of computing the $r^{2}/4$ term on the expert
trajectories only, we also compute this for the policy trajectories as well.
We set $c=0.5$ and $\beta=0.5$. This results in an even mixture of
regularization contributions from the expert and policy. Although this was
introduced in Garg et al. [11] heuristically, it was shown in Al-Hafez et al.
[1] that this has a well-motivated derivation as a result of the divergence
between the data occupancy and the mixture between the data occupancy and the
policy occupancy:

$\displaystyle\begin{aligned}
2\chi^{2}(\rho_{\text{data}}\|\underbrace{\frac{\rho_{\text{data}}+\rho_{\theta}}{2}}_{\rho_{\text{mix
}}})&=\sup_{r}2\left(\mathbb{E}_{\rho_{\text{data}}}[r(s,a)]-\mathbb{E}_{\rho_{\text{mix}}}\left[r(s,a)+\frac{r(s,a)^{2}}{4}\right]\right)\\\
&=\sup_{r}\mathbb{E}_{\rho_{\text{data}}}[r(s,a)]-\mathbb{E}_{\rho_{\theta}}[r(s,a)]-c\alpha\mathbb{E}_{\rho_{\text{data}}}\left[r(s,a)^{2}\right]-c(1-\alpha)\mathbb{E}_{\rho_{\theta}}\left[r(s,a)^{2}\right].\end{aligned}$

In practice, we find this method leads to better quality generations.

##  Appendix E Additional Training Details

###  E.1 Hardware

We train each model on four A4000 GPUs with 16GB VRAM each. We keep the batch
size at 128 for all models, although we have to reduce the batch size per
device and use gradient accumulation for the larger models (GPT2-medium and
large). As mentioned in the main text, we keep training parameters the same as
the nanoGPT implementation. For the behavioral cloning and SequenceMatch
models, we add a new column to the output embedding corresponding to the
<backspace> output. For the fully trained models, we add a <BOS> token to the
start of the sequences and add a new column to the input embedding
corresponding to the <BOS> token. For the SequenceMatch models, we first train
against the BC objective for 5,000 gradient steps, and then train against a
convex combination of the SM loss:
$\mathcal{L}_{\text{total}}=\beta\mathcal{L}_{\text{BC}}+(1-\beta)\mathcal{L}_{\text{SM}}$,
where $\beta$ is annealed from $1$ to $0.2$ linearly from 5,000 to 10,000
gradient steps. For the full training, we freeze all layers of the model
except the output embedding for training steps 0 to 1000, then linearly
unfreeze them for steps 1000 to 2000. We use a learning rate scheme consisting
of a linear warmup from 0 to 2000 steps, followed by cosine decay. For the
extra logits offset head, we use a two-layer MLP with ReLU nonlinearities and
hidden size equal to one-quarter of the embedding size. The inputs to the
layer are the position embeddings, the hidden values at the current position,
the position id as an integer, and a Fourier embedding of the input position
[31]. The output of the layer is added directly to the logits.

For SequenceMatch, we keep a replay buffer of past generated sequences. The
replay buffer is first-in-last-out, with the oldest sequences being replaced
once the size of the buffer is reached. The size of the replay buffer is
10,000. We specify how many times each sequence in the replay buffer will
appear in the training data before it is replaced (on average), and from that
calculate how frequently a generation step must take place during training. We
set the times each sequence will be seen in training to 8. The lengths of the
prompts for the generated sequences used in training are randomized, chosen
randomly from zero to half the context length. The completion is always set to
continue up to the context length or <EOS> token.

For the evaluation, we set the prompt length to be half the context length. We
then generate sequences of length 256, for both the context length 512 and
1024. For the generation, we set the temperature to 1 and the top-p sampling
to 1. However, for the increased length of the 1024 context length, we set the
top-p parameter to 0.95. We use the default settings to evaluate the mauve
score with 512 samples.

##  Appendix F Additional Plots

Figure 4: Diversity score [17] when fine-tuning GPT2 of various sizes on the
openwebtext dataset with context length 512. Higher is better. Full and LM
Head refer to which parts of the pretrained model are trained. We see that
SequenceMatch outperforms behavioral cloning and MLE for a fixed model size.
However, the fully trained models obtain lower scores than the variant only
training the head.

In figure 4 we show the results for the diversity metric from [17]. We see
that for a fixed model size and type, the SequenceMatch models outperform the
behavioral cloning and MLE baselines. A somewhat anomalous result is that the
diversity is higher for the LM Head models, and fairly uniformly decreases as
we increase the size of the models. This might indicate undertraining of the
full models.

##  Appendix G Overhead

In this section we discuss the relative overhead of using the SequenceMatch
training objective. We have additional overhead due to the necessity of
sampling completions from the model. In addition, the actual loss has some
additional complexity compared to the typical MLE loss, as we must extract the
terminal values and compute a telescoping sum. Additionally, due to the fact
that we use a batch of masks with a complex masking patterns, some GPU kernels
that are specialized for causal masking cannot be utilized. However, we note
that it’s not necessary to sample at every gradient step, since we can
accumulate old trajectories in a replay buffer and re-use them. Furthermore,
we can typically sample using a higher batch size than the gradient step batch
size, so requiring fewer sampling steps per gradient step. In table 2 we show
the breakdown of times necessary for a gradient step for each method. We see
that the loss computation and gradient step typically takes around twice as
long for the SequenceMatch objective than the MLE objective, due to the
additional computation specified above. The sampling adds additional overhead.
We note that the bottleneck from sampling could in principle be completely
removed by adding a separate set of GPUs which independently generate
sequences given the latest parameters and write to a buffer which is polled by
the main training thread. Due to time constraints and the additional
complexity of synchronizing separate processes, we did not implement this
additional distributed training approach.

| Fetch, Process Batch | Grad. Step | Sample Raw | Grad. steps per Sample | Total
---|---|---|---|---|---
SM-(Small, Full) |  0.3$\pm$0.05 |  2.2$\pm$0.02 |  10 $\pm$ 2 | 16 |  3.1 $\pm$ 0.5
MLE-(Small, Full) |  0.25$\pm$ 0.05 |  1.2 $\pm$ 0.1 | N/A | N/A |  1.45 $\pm$ 0.15
SM-(Large, LM Head) |  0.3$\pm$0.05 |  4.9$\pm$0.1 |  33 $\pm$ 5 | 12 |  7.95 $\pm$ 0.7
MLE-(Large, LM Head) |  0.25$\pm$0.05 |  2.2$\pm$0.1 | N/A | N/A |  2.45 $\pm$ 0.15
Table 2: Execution time of various parts of the training loop for the
different models for the 512 context length, $\chi^{2}$ objective with model
rollouts regularization. We show the raw time to sample a batch of
trajectories, as well as the time for sampling once amortized due to the fact
that we do not sample every training step.

##  Appendix H Additional Related Work

###  H.1 Regularization Terms

Due to the disadvantages of the KL-divergence discussed above, several
additional training objectives have been proposed which take into account the
model’s generated sequences. Particularly popular is the (sequence-level)
unlikelihood loss [37]. At step $t$, this is given by

$\mathcal{L}_{\text{ULS}}^{t}(P_{\theta}(\cdot|x_{1:t}))=\mathbb{E}_{s_{t+N}\sim
P_{\theta}(\cdot|s_{t})}\left[-\sum_{k=t+1}^{t+N}\sum_{c\in\mathcal{C}^{k}}P_{\theta}(c|s_{k})\right],$

where $\mathcal{C}^{k}$ is a set of problematic outputs, such as repeated
$n$-grams. The loss considers an $N$-step sequence generated from the model
from $s_{t}$ and penalizes repetitions. Although this regularization term
performs well in practice, it relies on a heuristic that repetitive text is
unnatural, which does not necessarily hold universally.

However, the idea of sampling a sequence from the model and including that
sequence in the loss is incorporated in SequenceMatch.

##  Appendix I Examples

In this section we give the first few samples from the evaluation set, with no
cherry-picking, for the 1024-context dataset and the SequenceMatch and MLE
objectives. Note that we strip newlines in the examples and generations in
order to present them on one page. At one point an unprintable character
(btyes U+FFFD) was produced, which we write as (U+FFFD). We have two settings
for the examples.

In the first setting, we take the prompt sequence and change the last token to
a random token drawn from the dataset. We see that the SequenceMatch model is
able to utilize the <backspace> token immediately to remove the spurious
token. The only case where this does not happen is for the prompt ... Clements
disagreed particula, where the random token does make some semantic sense. In
comparison, the MLE model cannot use the backspace and has a tendency to
degenerate after a random token (particularly evident in the Toyota example).

In the second setting, we give continuations on the evaluation dataset. We see
that the SequenceMatch model uses the backspace token in the Toyota example
with the generation skeptical of any measure<BKSPC> possible future
partnerships. Therefore, we can see that the SequenceMatch model is able to
learn to correct itself if it makes a generation that leads out of the
distribution of typical sequences.

Table 3: Model Prompts and Completions for the 1024 SequenceMatch trained model. In this setting we add a random token at the end of the prompt and observe the behavior of the generated sequences. Prompt |  Completion
---|---
<BOS>WHAT?!??! I know. That’s what you’re saying right now. "WHAT?! DISNEY HAS A DONUT SUNDAE AND I DIDN’T KNOW ABOUT IT?!" How do I know you’re saying that? Because that’s exactly what I was saying when Tina (<\- amazing DFB photographer who’s frigging awesome) spotted this at the Plaza Ice Cream Parlor in the Magic Kingdom this week! But it’s OK. It’s brand new — not even on the menu yet — so we didn’t miss out on too much of the Donut Sundae lifespan. And we’re hoping that lifespan is a nice, long one! The Main Street Plaza Ice Cream Parlor can be found at the intersection of Main Street USA and Tomorrowland, just before you get to Cinderella Castle. And the sundae joins a few other must-have treats on the Ice Cream Parlor’s menu, including the house-made ice cream sandwich (preferably ordered with a drizzled sauce!), the "kids’ cone" (it’s totally OK to order this as a dysph |  <BKSPC> souvenir or fruit-eating piece of cake), and the Chesapeake Bay Memorial Park curmudgeonly ice cream truck (though don’t take our word for it). Just as some of the other ice cream parlor attractions on the internet can help (hopefully), you can visit the Ice Cream Parlor to find even more delicious fried Oreo sandwiches, the "glass ice cream truck" teddy bear (can’t have it either), the skipjack pooping "free" soda fountain, and the pyrotechnically gourmet ice cream fountain! Here’s the video of the Wrecking Ball, the Oreo pod dunk, and me having a little short squeeze last night. This also happened: the Lake Clark Brewery’s Donut Ice Cream Factory opened the new location back in 2015 and they’re rumored to be in the final phases of redevelopment. We hope you enjoy getting ahead of the news of their transition to the big comeback we expect to see in April.<|endoftext|>
<BOS>A notorious protester convicted of wilfully promoting hatred against Muslims and criminally harassing a Muslim man and his family was sentenced Tuesday to nine months in jail. Eric Brazau handed out a flyer that "vilified Muslims and disparages their religion," Ontario court Judge S. Ford Clements said in February, when he found Brazau guilty. Eric Brazau was convicted of willful promotion of hatred against Muslims and criminally harassing a Muslim family. ( CARLOS OSORIO / TORONTO STAR FILE PHOTO ) The case was far from being on the borderline between "rough and tumble debate" and hate speech, as Brazau had argued, Clements said in a College Park courtroom. Brazau handed out the flyer, which contained many offensive references to Islam and Muslims, in August and September 2012. While distributing it, Brazau sometimes yelled obscenities about Islam "in a tone of voice that suggested he was very angry and had little interest in debate," Clements said. Brazau had argued that he did not intend to promote hate speech; instead he wanted to stimulate debate about censorship, "blasphemy laws" and Sharia law, Clements said. Article Continued Below Clements disagreed particula |  with Brazau’s argument that people should not be allowed to speak in a respectful manner about public information and even the workings of mosques under the guise of religion. He said that parties to these principles must have their act out with civility training — in other words, someone is responsible to their location. Clements also agreed with Brazau’s counsel that these are disagreements within the boundaries of the courtroom. "Based on the details in his core prosecution, the Attorney General has established that a search warrant was issued to his home located in the Brampton area of Greater Toronto prior to this arrest which led to a search warrant being executed," Clements wrote in his ruling. Clements added that prosecutors obtained emergency caution letters sent to him last week noting the violence in the community. Quebec Court Justice C. David Jones wrote for Clements that "treat of hatred on members of a religion is a systematic part of a larger system of religious policing and a serious mistake." Jones said after Brazau’s conviction that his conviction would only worsen if a further trial was to be opened. A judge in the Woodin Regional Court recently recommended Brazau be held without bail to avoid a conviction or to avoid detention pending a potential appeal. Read more about:<|endoftext|>
<BOS>× Some Seattle businesses closed for ’A Day Without Immigrants’, but others decided against it SEATTLE — While there is no official list of local businesses participating in this movement, "A Day Without Immigrants", we did find some businesses that had closed their doors and posted signs up saying they were participating. In fact, one business owner says he’s doing things a little bit differently. Instead of shutting down, he says he is choosing to pay it forward. Please enable Javascript to watch this video Edward Moran moved from Mexico to the United States in 1984. He opened El Norte Lounge in Lake City about seven years ago. And instead of closing up shop along with many other immigrant small business owners across the nation, Eduardo was open for business Thursday. "I don’t believe in closing a place just to protest," says Eduardo. Instead, he says he’s paying it forward. Eduardo is asking customers to pay in cash to avoid bank fees from credit card machines. He says he plans to donate a portion of his proceeds to a nonprofit that focuses on helping immigrants here in the Pacific Northwest. And he’s callingtotal |  <BKSPC> for a dialogue at least inside the city to try to bring pressure on the city to have equal access to immigrants. Steve Williams and Benjamin Romero noticed his business doors briefly ran out on Christmas and weekdays between Christmas and New Year’s. They say an important message is for businesses to consider the recent wave of protests that have erupted in Portland. From Mexico to the world with both women and children, signs are popping up throughout North America. The woman who shares an apartment with a family in Tacoma says all they want is a neighborly home and looks forward to a great life. Vincent French said when he first moved to Portland for work, people said he had been called in by the government and his mother. "When I moved here in Tacoma, they said to me, ’You can help people who are a threat and you can help your neighbors help other people out,’ " French said. However, after receiving death threats online, he says his business was able to avoid those calls. "I think they’ve finally decided, that’s great," he said. "I want people to be there to keep order." However, Ani Hernandez said she hopes only business owners can address negative feelings in the community. "When they start like this and start shutting down, people have to feel uncomfortable," she said. And just as there is no good news, some businesses are taking steps to control the negative emotions in the community. State of Washington state is going to hold a memorial service for anti-immigrant protesters at the Tenth Avenue and Aroznik Bridge. Click here to book a reservation.<|endoftext|>
<BOS>Today, Toyota announced changes in executives’ areas of responsibility, as well as personnel changes at the sub-executive managerial level. The most important change by far is the appointment of Akio Toyoda, the company’s CEO and grandson of founder Kiichiro Toyoda, as President of a new ’EV Business Planning’ department. Earlier this month, we reported-admittedly a little tongue-in-cheek-about Toyota announcing the creation of an electric vehicle division and putting only 4 engineers on the project with the goal to bring EVs to market by 2020. The move seems a lot more serious now that Akio Toyoda is leading the effort, and several other executives, managers, and engineers have been assigned new responsibilities in the electric vehicle planning department, including the chief engineer of the Prius. At the executive level, the changes will be effective today, while the managers were apparently put on the program throughout the month. You can see the full list of changes below. It appears to be a clear sign that Toyota is more serious than ever about electric vehicles and it is not simply investing in fuel cell hydrogen to comply to new fuel consumption standards. Changes to executives’ areas of 113 |  <BKSPC> responsibility require that Toyota - and its competitors - disclose further changes to their policies and practices as the larger EV business evolves. Toyota’s own EV business environment will be different from other companies which have recently been embracing a hybrid fleet. The company has not had a hybrid supply chain for years, and hybrid research research is not allowed inside its laboratories. That change will only come with the launch of this new integrated EV product division as the deal has not been finalized. The "Reuturistic and Singular Communication Systems" at Toyota are the industry’s most ambitious "big guy" partnerships. With that title and that vision first put to me, Toyota’s goal is to use a higher volume of vehicles and systems to market what’s best for consumers and the environment, rather than market what’s worst for them. For that reason, the company is opening the first car dealerships in the United States, and is doing so as the name suggests. There is no plan to extend out its RAV4 EV program beyond the University of Arizona system in Reno. While some groups like the Australian Automobile Club consider this as an important move, any EV owners who will be conclining to a hybrid infrastructure ought to be aware the company recognizes the average demand and needs of those vehicles and systems: With more than 300,000 vehicles on the road now, a few hundred more - including "Prix Super Super 500 Hybrid" - are being phased out. Consumers are more willing to hop on the electric car bandwagon than at any time in history. The shift to EV mandates has become what almost everyone has been dying to do for decades; shake off the bad habits of all regulatory agencies, deal with this as a new and necessary trend and transform the EV industry. Japan is still a new market after over 100 years of hard-charging and combustion engines. Now, we’ve seen the biggest transformation in our world - a future where EVs are sold by taxis, where vehicles are tracked and traded for cash. Existing customers, policy makers, and private sector know the EV space is big and we want to help. The new EV environment provides great opportunities and more rules, policies, and practices. Top 10 Reuturistic Energy Hybrid Designs Current LEAF motor vehicles are sold by Volkswagen, Toyota and Jaguar Land Rover, but very few cars contain or come close to this level of use. Over <|endoftext|>
<BOS>North Korean leader Kim Jong Un. AP Images / Business Insider North Korea attempted to fire a missile Sunday, but it blew up within seconds. It happened one day after the anniversary of the country’s founding. While North Korea’s missile program may be the shadowiest on earth, it’s possible that US cyber warriors were the reason for the failed launch. A recent New York Times report uncovered a Kham secret operation to derail North Korea’s nuclear-missile program that has been raging for at least three years. Essentially, the report attributes North Korea’s high rate of failure with Russian-designed missiles to the US meddling in the country’s missile software and networks. Although North Korea’s missile infrastructure lacks the competence of Russia’s, the Soviet-era missile on which North Korea based its missile had a 13 rotten% failure rate, and the North Korean version failed a whopping 88% of the time, according to the report. While the missile failure on Sunday could have just been due to poor workmanship, US Deputy National Security Adviser K.T. McFarland seemed to leave room for speculation about espionage, telling Fox News, ""We can’t talk about secret intelligence and things that might have been done ${} |  <BKSPC> to try to secure a foreign adversary or cause a serious injury or insurrection in North Korea. We could just slip the word ""secrecy"" into the Cold War."" Kham has published an outline of the failed missile call, with an attack message from an unknown country (the United States) that says, ""Kim Jong Un was able to detonate over as many as 30 interceptor missiles in just a single second."" The most realistic hypothesis seems to be that the North was firing missile-defence missiles somewhere north of the DMZ, and that North Korea detonated one and possibly two ""missiles."" Also buried on the NPA resume is part of the chart above, which suggests that North Korea was supposed to have advanced its satellite, but that it wasn’t actually meant to attack, and that Kim Jong Un deployed his forces through the DMZ in preparation for its full-scale invasion of the United States. The NPA suggestion that Kim Jong Un was behind the North Korean missile launch has been a theme in numerous US policy meetings over the past year. President Donald Trump hosted President Kim Jong Un, who has since spoken with South Korea’s President Moon Jae-in on the importance of dialogue. The face-to-face talks between Trump and Trump have so far resulted in multiple calls for ""constructive, constructive joint action.""On the campaign trail, Trump promised to ramp up efforts to tackle Pyongyang’s nuclear program, and claimed that North Korean leader Kim Jong Un was behind the misdeeds of his country. In response, Trump’s new administration has shown itself to be actively talking about North Korean diplomacy, telling the American community last month that ""North Korea is a wonderful, great nation. It has turned several dangerous institutions into havens of radicalism and terrorism, and I am confident that North Korea is also prepared to launch a strike and destroy any attempts to stop and shut down its programme. We must put forward options and seek a comprehensive, comprehensive, and comprehensive response."" North Korea had clearly misreported the strategic consequences of its ballistic missile launch Sunday. A missile does not threaten the US or the South; it appears to have fallen from the sky. In fact, North Korea has already launched about 95,000 missiles in less than a month.<|endoftext|>
Table 4: Model Prompts and Completions for the 1024 MLE trained model. In this setting we add a random token at the end of the prompt and observe the behavior of the generated sequences. Continued on next page Prompt |  Completion
---|---
WHAT?!??! I know. That’s what you’re saying right now. "WHAT?! DISNEY HAS A DONUT SUNDAE AND I DIDN’T KNOW ABOUT IT?!" How do I know you’re saying that? Because that’s exactly what I was saying when Tina (<\- amazing DFB photographer who’s frigging awesome) spotted this at the Plaza Ice Cream Parlor in the Magic Kingdom this week! But it’s OK. It’s brand new — not even on the menu yet — so we didn’t miss out on too much of the Donut Sundae lifespan. And we’re hoping that lifespan is a nice, long one! The Main Street Plaza Ice Cream Parlor can be found at the intersection of Main Street USA and Tomorrowland, just before you get to Cinderella Castle. And the sundae joins a few other must-have treats on the Ice Cream Parlor’s menu, including the house-made ice cream sandwich (preferably ordered with a drizzled sauce!), the "kids’ cone" (it’s totally OK to order this as a grown Cold |  Onion Roll, since kids eat cake too!), and good ol’ Oldman’s Sweet Ice Cream based Mini Six Peanut Butter Cups, as well as brand new Oreos Made from Oakwood. Anyway, we digress. So basically, we did a little code-changing this afternoon, and it turns out that we’ll be doing the full-on "YIMBA" package once again. Nope, nobody added New Master Cake (we’ll have to share your images), and you’re walking back your welcome to Polynesian macen as much as possible! Also, just to reiterate, all 10 of our Frozen Shorts! You see, we received one gift from Disney with a date of March 20. No luck deciding to use another date. No silly excuse, just a sense of nostalgia. See ya all next time! (This pattern has been gifted to us by Original Couture Forestes, which are mostly adorable because they totally turned out their own thing!) Please feel free to tell us what you think in the comments below…we’ll see you all on. But if you have any other ideas, let us know and we’ll try to make them a reality in the future, too! (C) Original Couture Forestes & Haircutters, YAMAHA Haircutters, and Innovative Mesh, all of whom deserve the award for this awesome Wild Forest creativity. For more casual fan-inspired pixel-art, check out these indie-design throwback images from the Splendour Of Sound booth! Look around at this awesome hidden gem. You’re never going to be alone with these work done by YOU! Other [And This Has When You’re on a Mission?!] samples from above or click the INVERSELEads button below to explore [Colourful Imagery]. [Colourful Imagery samples] by Chloe Yee. Quite a handful of amazing Red Solo was shown at the Smithsonian in June 2009. Have some of your favorite characters and locations be inspired by their design and art! [Colourful Imagery samples] by Karen Moore. This series uses heart modeled Granny Smith cruelly, deformed words, and her favorite turquoise character Digby Pie. It’s set in these specially designed Styrofoam turquoise silks, assembled by the construction company at
A notorious protester convicted of wilfully promoting hatred against Muslims and criminally harassing a Muslim man and his family was sentenced Tuesday to nine months in jail. Eric Brazau handed out a flyer that "vilified Muslims and disparages their religion," Ontario court Judge S. Ford Clements said in February, when he found Brazau guilty. Eric Brazau was convicted of willful promotion of hatred against Muslims and criminally harassing a Muslim family. ( CARLOS OSORIO / TORONTO STAR FILE PHOTO ) The case was far from being on the borderline between "rough and tumble debate" and hate speech, as Brazau had argued, Clements said in a College Park courtroom. Brazau handed out the flyer, which contained many offensive references to Islam and Muslims, in August and September 2012. While distributing it, Brazau sometimes yelled obscenities about Islam "in a tone of voice that suggested he was very angry and had little interest in debate," Clements said. Brazau had argued that he did not intend to promote hate speech; instead he wanted to stimulate debate about censorship, "blasphemy laws" and Sharia law, Clements said. Article Continued Below Clements disagreed.agos |  : It wasn’t only when an anti-Muslim protester was convicted. Clements said 2017 was unique because his term gives Brazau the opportunity to answer: "Qaads ben Yehudi: Where are the ’deplorables’ and who are the ’parallel struggles?’" after the jihad. Clements also said he found Bansaris and Jolyon Friesen guilty of helping incite hatred and hate. Zean Korah, a Supreme Court of Canada judge and former face of hate speech at the Toronto detention centre, will hold a preliminary hearing at Wednesday’s district court, Clements said. Article Continued Below Zean Joeberg will be heading up an "anti-fascist group"; as Ziya Janette Sharma will be in charge of the prosecution, Clements agreed. He said he didn’t anticipate Clements making such a verdict in the light of events in Ferguson, Mo., and that findings "are not to be taken lightly," Clements said. "It’s the judge’s job to look like we’ve done well in addressing this issue," Clements said. The judge sentenced Brazau to nine months in prison, awarding him $500,000 for fighting the charges. The sentence came after a two-day trial in Toronto where he stood with fellow protesters in front of Chief of Staff at the Toronto Police Service, then endorsed the suspect in the flagrant breach of secrecy. He was scheduled to appear in St. John’s Superior Court on Monday. During the trial, meanwhile, some of his accusers sat in on the most contentious and contested event of his life, the lawyer arguing that the judge should have subjected Brazau to such an intense chilling procedure that could have been triggered by his admission of hate speech. He also called the reality of being falsely accused by the St. John’s Residents Association of mistreating his client a "victory" instead of "a blow to his reputation." Clements said the judge was aware of so many anti-jihadary developments as he had been studying the case on a trip to the New York area last month. But he rejected allegations of political bias, saying that Brazau’s remarks were "symbolic and ironic." Clements took issue with allegations of the judge condoning violence, saying: "There’s some type!
× Some Seattle businesses closed for ’A Day Without Immigrants’, but others decided against it SEATTLE — While there is no official list of local businesses participating in this movement, "A Day Without Immigrants", we did find some businesses that had closed their doors and posted signs up saying they were participating. In fact, one business owner says he’s doing things a little bit differently. Instead of shutting down, he says he is choosing to pay it forward. Please enable Javascript to watch this video Edward Moran moved from Mexico to the United States in 1984. He opened El Norte Lounge in Lake City about seven years ago. And instead of closing up shop along with many other immigrant small business owners across the nation, Eduardo was open for business Thursday. "I don’t believe in closing a place just to protest," says Eduardo. Instead, he says he’s paying it forward. Eduardo is asking customers to pay in cash to avoid bank fees from credit card machines. He says he plans to donate a portion of his proceeds to a nonprofit that focuses on helping immigrants here in the Pacific Northwest. And he’s calling on finalists |  in the project to pay back what he’s paid on every purchase. Do you believe Eduardo’s message to businesses — donate, pay their employees back and help other immigrants live in dignity? How about more "A Day Without Immigrants"? Is it possible you could help encourage the nation to do something like Eduardo’s? Helping immigrants live in dignity isn’t the goal of the group: To give free tuition to illegal aliens. But Eduardo believes immigrants can be welcome here as long as they pay taxes. "Do we need any more illegals in our country? No. We don’t," says Eduardo. District Judge Lucy Kohls says school district officials should remove the "A Day Without Immigrants" sign from their annual accreditation program, which requires every high school student to teach English. But according to Korea-based Senator Hillary Schakowsky, this group has started competing. "They seem to be suffering from stigma," says Schakowsky. "I’m hoping the courts will find them to be ashamed of themselves for what they’ve done and to cast them in the negative light, if not as a group who would be well served to get on the national stage." Lynn Horcher says she hopes that Eduardo’s message can inspire parents and businesses to break down the walls around immigrants, without fear for their safety and to break out of fear that those still working for immigrants will be jailed, beaten and deported. "I’m so sorry," says Lynch. "Those who truly want to do this were always called ’Daddy Minjies.’ I say that as a parent who thinks that when your parents leave you need to do something that they really, really feel guilty about because you were born here." Witness the violence, burning and pickings, and watch the protesters packing tents for three days. Could immigrants be shut down for protest or collect your money? Photo Credit: SimplePhotographer.com Follow @ChrisBreaux on Twitter. This article was originally published on The Conversation. Read the original story. [h/t: Trevor Wright] Download our NEW Occupy Democrats app for your iPhone by clicking here or for your Android by clicking here. Add your name to millions demanding that!
Today, Toyota announced changes in executives’ areas of responsibility, as well as personnel changes at the sub-executive managerial level. The most important change by far is the appointment of Akio Toyoda, the company’s CEO and grandson of founder Kiichiro Toyoda, as President of a new ’EV Business Planning’ department. Earlier this month, we reported-admittedly a little tongue-in-cheek-about Toyota announcing the creation of an electric vehicle division and putting only 4 engineers on the project with the goal to bring EVs to market by 2020. The move seems a lot more serious now that Akio Toyoda is leading the effort, and several other executives, managers, and engineers have been assigned new responsibilities in the electric vehicle planning department, including the chief engineer of the Prius. At the executive level, the changes will be effective today, while the managers were apparently put on the program throughout the month. You can see the full list of changes below. It appears to be a clear sign that Toyota is more serious than ever about electric vehicles and it is not simply investing in fuel cell hydrogen to comply to new fuel consumption standards. Changes to executives’ areas of responsibilityJohn |  Schmitt, Managing Director of Toyota Chris Koscarino, EV Business Planner Michelle Swahira, EV Executive Manager, New York Mark Page, Assistant Managing Director, Toyota Mathew Kennedy, EV Business Planner David Gustavsson, EV Manager, New York Leigh Munro, EV Manager, San Jose Ruthen Friedrich, EV Executive President, Califasto Matt Keysbury, EV Managing Director, Toyota Rahla Baldus, EV Management, Nippon Professional Grooming Club, Tokyo Let’s keep it human for a minute. Just kidding, Toyota wasn’t kidding about the new gig, when they announced that the first 100,000 electric vehicles will be hitting stores across the country in two years, and that the car maker wants to serve as "the world’s largest car retailer." See also. Ah yes, the EV is finally relevant and the rest is history. Toyota President Michio Kaku and CEO Akio Toyoda are turning heads and actively promoting the sport-class EV during the various global celebrations, and even this week, unveiling the new 2018 Plug-In Hybrid Transit (EV.SE), which will have a new 4.0-liter,EV powertrain, a plug-in hybrid. It will arrive on the market in September, and will be the first-ever plug-in hybrid with a highway-compliant full-size sedan in Japan. The new sedan will offer "bump-in" emissions-calming technology, making the EV more efficient than its rivals. The fleet should start rolling out in 2017, and even here at EV Trade, we encourage most prospective car buyers to take the time to check our website for what exactly is coming to market. You don’t want your Sonata on the road for only a short week, in the European market? Source: iSupermarket [Source: iSupermarket ]] Source: Quora Source: Quora Source: Google+ Source: Google+ Source: Quora Source: Google+ Source: Quora Source: Quora Source: Google+ Source: Google+ Source: Quora Source: Google+ Source: Quora Source: Quora Source: Quora Source:
Table 5: Last Model Prompt and Completion for the 1024 MLE trained model. In this setting we add a random token at the end of the prompt and observe the behavior of the generated sequences. Continued from previous page Prompt |  Completion
---|---
North Korean leader Kim Jong Un. AP Images / Business Insider North Korea attempted to fire a missile Sunday, but it blew up within seconds. It happened one day after the anniversary of the country’s founding. While North Korea’s missile program may be the shadowiest on earth, it’s possible that US cyber warriors were the reason for the failed launch. A recent New York Times report uncovered a secret operation to derail North Korea’s nuclear-missile program that has been raging for at least three years. Essentially, the report attributes North Korea’s high rate of failure with Russian-designed missiles to the US meddling in the country’s missile software and networks. Although North Korea’s missile infrastructure lacks the competence of Russia’s, the Soviet-era missile on which North Korea based its missile had a 13% failure rate, and the North Korean version failed a whopping 88% of the time, according to the report. While the missile failure on Sunday could have just been due to poor workmanship, US Deputy National Security Adviser K.T. McFarland seemed to leave room for speculation about espionage, telling Fox News, "We can’t talk about secret intelligence and things that might have been done, covert operations scen |  ically." The revelation of the secrets follow months of effort to downplay hacking and sabotage that has divided the country, in which North Korean cyber warriors fought militarily against regime change. By overthrowing the leadership of Kim Jong Un, North Korea has breached the territory of the United States and other big nations, as well as a vital diplomatic facility in Shanghai, a large regional hub, Reuters reported. North Korea’s attempts to sabotage Pyongyang first came to light on April 1, when it carried out a missile test. But even North Korea’s leaders were quick to pinpoint the launch as the likely result of cyber-attacks. An overwhelming majority of Pyongyang’s elite are U.S. intelligence, with Kim deriding Washington’s cyber security arrangements and blaming the country’s Soviet enemies. On Sunday’s anniversary, a cyberwarfare specialist named Kim Hyon Hyon conducted a test firing of the Terminal High Altitude Area Defense interceptor that was his main target. US intelligence officials have told Fox News that Kim Kim planned to enter South Korea last Friday to try and reset relations, Yonhap reported. [And Trump is the North’s top diplomat now] The cyber attack also likely broke out at a door for Kim Jong Un’s brother, Ri Yong Ho, who seems to be a devoted leader. The South Korean leader responded by comparing the attack on the research institute to the attacks on the USS Cole airbase in Yemen that killed 9 sailors during the attack. Kim is the country’s previous leader from 1990- 1994. Kim Jong Un’s brother, Ri Jong Il, passed away in 1994, but North Korea remains very close to Ri’s family and maintains a high ranking. By Sunday, Jong Il had tweeted, "A war hell war!" North Korea test fired at Ichiwa port. Pesatime (New York/New York) — Ri Jong Il (@ RiJi) December 10, 2016 Later, some of North Korea’s scientists released a book about Ri, promising to "break his nuclear arms" and help their country prevent a nuclear war. In March, Sony Hackings Interview Kim Jong Un and Other Executives Are Separating Their Values From Their Intelligence Perceptions. They are just now getting their heads around the Kim Jong Un decision. — Sputnik News (@SputnikNews) December 13, 2016 Before that, North Korea had been largely on alert, determined to achieve a nuclear war. Kim launched!
Table 6: Model Prompts and Completions for the 1024 SequenceMatch trained model. In this setting we simply generate sequences based on the prompt Prompt |  Completion
---|---
<BOS>WHAT?!??! I know. That’s what you’re saying right now. "WHAT?! DISNEY HAS A DONUT SUNDAE AND I DIDN’T KNOW ABOUT IT?!" How do I know you’re saying that? Because that’s exactly what I was saying when Tina (<\- amazing DFB photographer who’s frigging awesome) spotted this at the Plaza Ice Cream Parlor in the Magic Kingdom this week!But it’s OK. It’s brand new — not even on the menu yet — so we didn’t miss out on too much of the Donut Sundae lifespan. And we’re hoping that lifespan is a nice, long one! The Main Street Plaza Ice Cream Parlor can be found at the intersection of Main Street USA and Tomorrowland, just before you get to Cinderella Castle. And the sundae joins a few other must-have treats on the Ice Cream Parlor’s menu, including the house-made ice cream sandwich (preferably ordered with a drizzled sauce!), the "kids’ cone" (it’s totally OK to order this as a grown |  " adult adult! But NOT on a Snickers bar, too!), the kikos and curries (unless you use all the glaze from other frozen items in the store), and absolutely everything — as well as the desserts and ice cream itself. Guests can share their undie sundae or a gummy mummy figurine with the kiosk. Happy Butterfingers, and thanks for checking out the best all summer online.<|endoftext|>
<BOS>A notorious protester convicted of wilfully promoting hatred against Muslims and criminally harassing a Muslim man and his family was sentenced Tuesday to nine months in jail. Eric Brazau handed out a flyer that "vilified Muslims and disparages their religion," Ontario court Judge S. Ford Clements said in February, when he found Brazau guilty. Eric Brazau was convicted of willful promotion of hatred against Muslims and criminally harassing a Muslim family. ( CARLOS OSORIO / TORONTO STAR FILE PHOTO ) The case was far from being on the borderline between "rough and tumble debate" and hate speech, as Brazau had argued, Clements said in a College Park courtroom. Brazau handed out the flyer, which contained many offensive references to Islam and Muslims, in August and September 2012. While distributing it, Brazau sometimes yelled obscenities about Islam "in a tone of voice that suggested he was very angry and had little interest in debate," Clements said. Brazau had argued that he did not intend to promote hate speech; instead he wanted to stimulate debate about censorship, "blasphemy laws" and Sharia law, Clements said. Article Continued Below Clements disagreed. |  ""He presented that he could not create the views or arguments required in terms of hatred which I thought would promote even greater debate," Clements said of Brazau. Brazau’s lawyers have accused him of lying to get away with distributing offensive flyers to delegitimize a mosque location. Clements said Brazau wasn’t guilty of participating in the defacement of mosque equipment. He said because of his alleged victimization in an anti-Muslim message for months, the flyer has become an "internal crusade against the fundamental rights of our Muslim community." He said, although Brazau received laments for his actions, police did not find any unlawful activity during the June 2012 incident. "They could not seem to distinguish that the flyer has done anything illegal," Clements said. "We did find up-close images of the flyer at a nearby parking lot on June 12, which is a stunning part of what happened." The flyer said he had been planning to post an editorial about the case on his website in January. He wrote a memo outlining how his comments to his prior remarks had affected his views on Islam. He told a friend at one point that "I was trying to add as much drama as possible" to Muslim accusations he had received about his recent conduct, Clements said, but Brazau’s actions attracted too much attention. Article Continued Below He denied defacing the apartment they shared with his brother. He was sentenced to 15 months’ probation and ordered to pay $10,000 in restitution to his victims. Mesher Lalaini, the lawyer who represented Brazau on Tuesday, said he was appalled that police had failed to bring him to trial. However, he said his client told the judge he couldn’t believe that police were complicit in the attack.<|endoftext|>
<BOS>× Some Seattle businesses closed for ’A Day Without Immigrants’, but others decided against it SEATTLE — While there is no official list of local businesses participating in this movement, "A Day Without Immigrants", we did find some businesses that had closed their doors and posted signs up saying they were participating. In fact, one business owner says he’s doing things a little bit differently. Instead of shutting down, he says he is choosing to pay it forward. Please enable Javascript to watch this video Edward Moran moved from Mexico to the United States in 1984. He opened El Norte Lounge in Lake City about seven years ago. And instead of closing up shop along with many other immigrant small business owners across the nation, Eduardo was open for business Thursday."I don’t believe in closing a place just to protest," says Eduardo. Instead, he says he’s paying it forward. Eduardo is asking customers to pay in cash to avoid bank fees from credit card machines. He says he plans to donate a portion of his proceeds to a nonprofit that focuses on helping immigrants here in the Pacific Northwest. And he’s calling on |  Seattle to take steps to address this injustice. "As some of these things have happened … I would like to do something a little different," says Eduardo. Eduardo took the day off from work Thursday. "I believe an important moment is for us to really make this what we are," says Ed. From Mexico to the United States, there are dozens of signs supporting immigrants who live here. Eduardo doesn’t fear that his business is destroyed because his business is shutting down due to currency restrictions. "I didn’t just start out as a business - I just made it money," says Eduardo. Eduardo says a lot of people here in the U.S. are immigrants to this country. He says there is people who have a much larger family standing by as they help other immigrants out.<|endoftext|>
<BOS>Today, Toyota announced changes in executives’ areas of responsibility, as well as personnel changes at the sub-executive managerial level. The most important change by far is the appointment of Akio Toyoda, the company’s CEO and grandson of founder Kiichiro Toyoda, as President of a new ’EV Business Planning’ department. Earlier this month, we reported-admittedly a little tongue-in-cheek-about Toyota announcing the creation of an electric vehicle division and putting only 4 engineers on the project with the goal to bring EVs to market by 2020. The move seems a lot more serious now that Akio Toyoda is leading the effort, and several other executives, managers, and engineers have been assigned new responsibilities in the electric vehicle planning department, including the chief engineer of the Prius. At the executive level, the changes will be effective today, while the managers were apparently put on the program throughout the month. You can see the full list of changes below. It appears to be a clear sign that Toyota is more serious than ever about electric vehicles and it is not simply investing in fuel cell hydrogen to comply to new fuel consumption standards. Changes to executives’ areas of responsibility |  "(top image): Geneshiro Toyoda as President Akio Toyoda as CEO The company is stepping into a new era within the industry. Toyota will be taking a significant step forward moving forward with the program, along with all of the veteran EV experts who will be on board. Toyota will invest in another budget program with Nissan, and will also spend close to 2 percent more in this effort. Late last week, Toyota said the automaker is seeking federal money to launch and develop a Phase I funding program to support the Toyota SSP. While many people are skeptical of any measure<BKSPC> possible future partnerships, Toyota was confident that the group will be determined to get the program off the ground by 2020, and that a program would be here before too long. Toyota’s current projections indicate it will acquire Mitsubishi A-brand engines to support its No. 2 seat car, which will supply approximately 220,000 electric vehicles in 2020. The company is expected to have expanded the name in 2017, by launching a new hydrogen fuel cell vehicle between 2021 and 2023. Ralph Hisefner as CEO New initiatives on Toyota’s Level 3 Vision Vision Future Systems Competition have been revealed today, but they are being designed to launch new development capabilities in this rapidly approaching market. By doing so, Toyota will be taking a step closer to the promise of wide-mileage electric vehicles, a goal already put to the ’Pim Super Super 500 Hybrid’ and the Toyota Vision Future technologies for the Toyota platform. Hyundai Tribute Pack Member (subsequently name changed): BMW i3 BMW i3 Gran Coupe SSI Kortis Accordingly, Toyota is assembling the brand S6, and with that said, even the really big crossover may be made by this new entrant. As stated in a Japanese blog: The KC-BY is forecast to surpass the 2012 ’Konami HD’ as the global hybrid vehicle market continues to grow. Toyota aims for the 2020 model to be able to extend global road segment recognition and hybrid vehicle capabilities to the top tier of the vehicle. The new vehicle that utilizes self-driving technology developed jointly in Toyota and BMW technology is expected to be available at the Tokyo Motor Show in March. The vehicle’s high-volume powertrain and low-land temperature drive technology combined with industry leading regenerative braking technology will enable use in some"
<BOS>North Korean leader Kim Jong Un. AP Images / Business Insider North Korea attempted to fire a missile Sunday, but it blew up within seconds. It happened one day after the anniversary of the country’s founding. While North Korea’s missile program may be the shadowiest on earth, it’s possible that US cyber warriors were the reason for the failed launch. A recent New York Times report uncovered a Kham secret operation to derail North Korea’s nuclear-missile program that has been raging for at least three years. Essentially, the report attributes North Korea’s high rate of failure with Russian-designed missiles to the US meddling in the country’s missile software and networks. Although North Korea’s missile infrastructure lacks the competence of Russia’s, the Soviet-era missile on which North Korea based its missile had a 13 rotten% failure rate, and the North Korean version failed a whopping 88% of the time, according to the report. While the missile failure on Sunday could have just been due to poor workmanship, US Deputy National Security Adviser K.T. McFarland seemed to leave room for speculation about espionage, telling Fox News, "We can’t talk about secret intelligence and things that might have been done |  " yet what’s indisputable is that Russia has this capability." Experts in weapons of mass destruction, nor hobbyists, are all having it the way Washington does, so any possible moves must have been made based on failed missile maintenance. "You know what they’re doing," McFarland told Fox, "we’re not going to send the whole team along." Which is a strange thing for a reclusive state, not just because of North Korea’s weight, but also because its government boasted that it didn’t last long. These days, it appears to be a formula for luck and luck for the elites who once thought maybe they were doing something about the North Korean missile crisis. We’re supposed to give our president some credit for doing what he did and getting some information, but every year, late changes happen to stifle the executive in power. Madhya Pradesh, India and Bangladesh will always have to tighten security structures to ensure the integrity of North Korea’s defense, foreign affairs, and militaries. The Obama administration, concerned with other threatened nuclear war with China or the U.S., has been getting pretty wild about Kim Jong Il. President Obama only added to the tensions by denouncing Kim Jong Un’s activities as "evil." The latest episode in North Korea’s long downward spiral began with the sinking of a fifth submarine into the Korean Sea late last year, U.S. Pacific Command announced on its blog. In response to such concern, Obama pledged "recovery activities" against North Korea. In the same post, National Intelligence Director James Clapper said the administration will fight the North’s nuclear threats and leverage the means to get countries to do more. Meanwhile, Washington has recently raised concerns about Russia’s involvement in the crisis, and says sanctions imposed against Russia for its role in the conflict aren’t working.The president also told The Associated Press, "We urge President Putin to ensure that Russia does its business in international law and accountability."Listen to the full report from Business Insider, obtained by CNBC via a government-backed channel, here:<|endoftext|>
Table 7: Model Prompts and Completions for the 1024 MLE trained model. In this setting we simply generate sequences based on the prompt. Continued on the next page. Prompt |  Completion
---|---
WHAT?!??! I know. That’s what you’re saying right now. "WHAT?! DISNEY HAS A DONUT SUNDAE AND I DIDN’T KNOW ABOUT IT?!" How do I know you’re saying that? Because that’s exactly what I was saying when Tina (<\- amazing DFB photographer who’s frigging awesome) spotted this at the Plaza Ice Cream Parlor in the Magic Kingdom this week!But it’s OK. It’s brand new — not even on the menu yet — so we didn’t miss out on too much of the Donut Sundae lifespan. And we’re hoping that lifespan is a nice, long one! The Main Street Plaza Ice Cream Parlor can be found at the intersection of Main Street USA and Tomorrowland, just before you get to Cinderella Castle. And the sundae joins a few other must-have treats on the Ice Cream Parlor’s menu, including the house-made ice cream sandwich (preferably ordered with a drizzled sauce!), the "kids’ cone" (it’s totally OK to order this as a grown |  up treat, since kids eat cake too!), and good ol’ fashioned vanilla ice cream! Following the Donut Sundae today, you can order, pre-order, and shop the entire deliciously designed sundae at the Ice Cream Parlor at DFB. Don’t miss anything out of the box, besides the usual fine-dining fries and your favorite spreads! You can also pick up your order through Amalgamated Beverage Box, which is located right next door on the corner of Tamar Observatory and Tomorrowland Drive. To snag one of the vendors like the crazy-large beanies-and-donuts lunch-and-dinner, grab a tin from the shop, sneak in to talk at a meeting (we take great care around door 24) as the chefs sit down to work on the sundae, or walk out into the lobby to enjoy the hospitality before they head in to the cooling room. Also, come enjoy the serenity. I know, yes, there is a switch in the light switch, but let’s not forget about the steam simmering during cooling, and the popcorn-like pokey boy-ness under the table! Especially when you have other items. And the floor plan, by the way, is the most open dining room in Chicago. No kidding. View the Artists Competing for Banned Comics! Happy First Wednesdays! We really enjoyed seeing you and talking to you and getting to work on the designs! Find more details about this contest here. And please continue on to our Facebook Page for more comment and suggestions about amazing artwork on a single page. Thanks! Do you like chocolate platters in work? No problem! You’ll love every second of this delicious, decadent dessert! You can learn more about the winner here! Like our Banned Comports on Facebook or follow us on Pinterest! PS: Your promo code your favorite comic writer or artist to be featured in our Facebook and Twitter sets. It only goes to the sable (B&F) fans that pledge at their design size instead of the Super Furry ones. Don’t worry, we’ll give you a link to the cruella, so make sure to check back soon when we have another awesome one! Have a cool day! -Lisa More from Eup’s Beach Café The Other Circular
A notorious protester convicted of wilfully promoting hatred against Muslims and criminally harassing a Muslim man and his family was sentenced Tuesday to nine months in jail. Eric Brazau handed out a flyer that "vilified Muslims and disparages their religion," Ontario court Judge S. Ford Clements said in February, when he found Brazau guilty. Eric Brazau was convicted of willful promotion of hatred against Muslims and criminally harassing a Muslim family. ( CARLOS OSORIO / TORONTO STAR FILE PHOTO ) The case was far from being on the borderline between "rough and tumble debate" and hate speech, as Brazau had argued, Clements said in a College Park courtroom. Brazau handed out the flyer, which contained many offensive references to Islam and Muslims, in August and September 2012. While distributing it, Brazau sometimes yelled obscenities about Islam "in a tone of voice that suggested he was very angry and had little interest in debate," Clements said. Brazau had argued that he did not intend to promote hate speech; instead he wanted to stimulate debate about censorship, "blasphemy laws" and Sharia law, Clements said. Article Continued Below Clements disagreed. |  (U+FFFD) The defendant clearly is guilty," Clements said. "It is not a state where you can engage with a matter as legitimate." David Holt, Brazau’s lawyer, said in a brief that his client’s lawyer wanted more evidence. Holt said anything he found "seriously offensive," including white, male and Hispanic B-list and middle-class millennial controversy, "needs more serious and substantial exculpatory evidence." Supreme Court Justice Viviane Dawson added that her "courtesy orders order" for trial, ordering him to send the flyer, "was a ’badity order’ which demonstrates the attorney general — not himself — has failed to act in an appropriately proportionate fashion to the malicious impulses he states in his charges’ aggravation motion. Crown attorney Sarah Walcott warned that lack of evidence was likely to result in a lengthy jail sentence for Brazau and his attorneys. But prosecutors also vowed to pursue additional charges at a sentencing hearing in mid-June, when a trial, if it progresses, will take place. Walcott said the judge showed "[He] showed extraordinary competency, and delivered on his word." A hearing for the man in last July’s trial is set for Dec. 15. Facing charges of criminal harassment and incitement to hatred and incitement to hatred of others, Brazau refused to come out of his lawyer’s office before the trial began on March 1, but was found to be a witness at the first witness stand, a guilty plea hearing set for June 18. During the first stand, Brazau was accused of giving contradictory and false information about Islam and Muslims that could back up a reference to Islam being "genocidal," "indecent and ultimately un-Islamic," and "not innocent." Brazau’s lawyer went on to state: "It doesn’t matter if you’re in the community, church, synagogue, anywhere, I’m not a threat to anyone. Not a threat to God, nor the communities in the city of College Park, I’m a threat to others, because I care deeply about the faith of these people." The city of College Park is the home of the University of Toronto and the University of Ottawa, as well as the Little Ethiopia Peek Park in southern Ontario. The court ordered that the flyer stop promoting hate