# Do LLM Agents Have Regret?
A Case Study in Online Learning and Games

Chanwoo Park  Chanwoo Park‡‡‡Equal Contribution Xiangyu Liu††footnotemark:
Asuman Ozdaglar  Kaiqing Zhang ††C. Park and A. Ozdaglar are with
Massachusetts Institute of Technology, Cambridge, MA, 02139. X. Liu and K.
Zhang are with the University of Maryland, College Park, MD, 20742. E-mails:
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Large language models (LLMs) have been increasingly employed for (interactive)
decision-making, via the development of LLM-based autonomous agents. Despite
their emerging successes, the performance of LLM agents in decision-making has
not been fully investigated through quantitative metrics, especially in the
multi-agent setting when they interact with each other, a typical scenario in
real-world LLM-agent applications. To better understand the limits of LLM
agents in these interactive environments, we propose to study their
interactions in benchmark decision-making settings in online learning and game
theory, through the performance metric of _regret_. We first empirically study
the no-regret behaviors of LLMs in canonical (non-stationary) online learning
problems, as well as the emergence of equilibria when LLM agents interact
through playing repeated games. We then provide some theoretical insights into
the no-regret behaviors of LLM agents, under certain assumptions on the
supervised pre-training and the rationality model of human decision-makers who
generate the data. Notably, we also identify (simple) cases where advanced
LLMs such as GPT-4 fail to be no-regret. To promote the no-regret behaviors,
we propose a novel _unsupervised_ training loss of _regret-loss_ , which, in
contrast to the supervised pre-training loss, does not require the labels of
(optimal) actions. We then establish the statistical guarantee of
generalization bound for regret-loss minimization, followed by the
optimization guarantee that minimizing such a loss may automatically lead to
known no-regret learning algorithms. Our further experiments demonstrate the
effectiveness of our regret-loss, especially in addressing the above
“regrettable” cases.

##  1 Introduction

> Live Life with No Excuses. Travel with No Regret.

Large language models (LLMs) have recently exhibited remarkable reasoning
capabilities (Bubeck et al., 2023; Achiam et al., 2023; Wei et al., 2022b; Yao
et al., 2023a). As a consequence, a burgeoning body of work has been
investigating the employment of LLMs as central controllers for (interactive)
decision-making, through the construction of _LLM-based autonomous agents_
(Hao et al., 2023; Shen et al., 2023; Yao et al., 2023b; Shinn et al., 2023;
Wang et al., 2023c; Significant Gravitas, 2023). Specifically, the LLM agent
interacts with the (physical) world in a _dynamic/sequential_ way: it uses
LLMs as an oracle for reasoning, then acts in the environment based on the
reasoning and the feedback it perceives over time. LLM agent has achieved
impressive successes in embodied AI (Ahn et al., 2022; Huang et al., 2022a;
Wang et al., 2023a), natural science (Wu et al., 2023; Swan et al., 2023), and
social science (Park et al., 2022, 2023) applications.

Besides being _dynamic_ , another increasingly captivating feature of LLM-
based decision-making is the involvement of _strategic_ interactions,
oftentimes among multiple LLM agents. For example, it has been continually
reported that the reasoning capability of LLMs can be improved by interacting
with each other through negotiation and/or debate games (Fu et al., 2023; Du
et al., 2023); LLM agents have now been widely used to _simulate_ the
strategic behaviors for social and economic studies, to understand the
emerging behaviors in interactive social systems (Aher et al., 2023; Park et
al., 2023). Moreover, LLMs have also exhibited remarkable potential in solving
various games (Bakhtin et al., 2022; Mukobi et al., 2023), and in fact, a
rapidly expanding literature has employed _repeated games_ as a fundamental
benchmark to understand the strategic behaviors of LLMs (Brookins and
DeBacker, 2023; Akata et al., 2023; Fan et al., 2023). These exciting
empirical successes call for a rigorous examination and understanding through
a theoretical lens of decision-making.

_Regret_ , on the other hand, has been a core metric in (online) decision-
making. It measures how “sorry” the decision-maker is, in retrospect, not to
have followed the best prediction in hindsight (Shalev-Shwartz, 2012). It
provides not only a sensible way to _evaluate_ the intelligence level of
online decision-makers, but also a quantitative way to measure their
_robustness_ against arbitrary (and possibly adversarial) environments. More
importantly, it inherently offers a connection to modeling and analyzing
strategic behaviors: the long-run interaction of no-regret learners leads to
certain _equilibria_ when they repeatedly play games (Cesa-Bianchi and Lugosi,
2006). In fact, _no-regret_ learning has served as a natural model for
predicting and explaining human behaviors in strategic decision-making, with
experimental evidence (Erev and Roth, 1998; Nekipelov et al., 2015; Balseiro
and Gur, 2019). It has thus been posited as an important model of “rational
behavior” in playing games (Blum et al., 2008; Roughgarden, 2015; Roughgarden
et al., 2017). Thus, it is natural to ask:

_Can we examine and better understand the online and strategic decision-making
behaviors of LLMs through the lens of _regret_?_

Acknowledging that LLM(-agents) are extremely complicated to analyze, to gain
some insights into the question, we focus on benchmark decision-making
settings: online learning with convex (linear) loss functions, and playing
repeated games. We summarize our contributions as follows.

##### Contributions.

First, we carefully examine the performance of several representative pre-
trained LLMs in aforementioned benchmark online decision-making settings, in
terms of _regret_. We observe that oftentimes, LLM agents exhibit no-regret
behaviors in these (non-stationary) online learning settings, where the loss
functions change over time either arbitrarily (and even adversarially), or by
following some patterns with bounded variation, and in playing both
representative and randomly generated repeated games. For the latter,
equilibria will emerge as the long-term behavior of the interactions when all
LLM agents are no-regret. Second, we provide some theoretical insights into
the observed no-regret behaviors, based on some hypothetical model of the
human decision-makers who generate the data, and certain assumptions on the
_supervised pre-training_ procedure, a common practice in training large
models for decision-making. In particular, we make a connection of pre-trained
LLMs to the known no-regret algorithm of _follow-the-perturbed-leader_ (FTPL)
under such assumptions. Third, we also identify (simple) cases where advanced
LLMs as GPT-4 fail to be no-regret. We thus propose a novel _unsupervised_
training loss, _regret-loss_ , which, in contrast to the supervised pre-
training loss, does not require the _labels_ of (optimal) actions. We then
establish both statistical and optimization guarantees for regret-loss
minimization, showing that minimizing such a loss may automatically lead to
known no-regret learning algorithms. Our further experiments demonstrate the
effectiveness of regret-loss, especially in addressing the above “regrettable”
cases.

###  1.1 Related Work

##### LLM(-agent) for decision-making.

The impressive capability of LLMs for _reasoning_ (Bubeck et al., 2023; Achiam
et al., 2023; Wei et al., 2022b, a; Srivastava et al., 2023; Yao et al.,
2023a) has inspired a growing line of research on _LLM for (interactive)
decision-making_ , i.e., an LLM-based autonomous agent interacts with the
environment by taking actions repeatedly/sequentially, based on the feedback
it perceives. Some promises have been shown from a _planning_ perspective (Hao
et al., 2023; Valmeekam et al., 2023; Huang et al., 2022b; Shen et al., 2023).
In particular, for embodied AI applications, e.g., robotics, LLMs have
achieved impressive performance when used as the controller for decision-
making (Ahn et al., 2022; Yao et al., 2023b; Shinn et al., 2023; Wang et al.,
2023c; Driess et al., 2023; Significant Gravitas, 2023). However, the
performance of decision-making has not been rigorously characterized via the
regret metric in these works. Very recently, Liu et al. (2023c) has proposed a
principled architecture for LLM-agent, with provable regret guarantees in
stationary and stochastic decision-making environments, under the Bayesian
adaptive Markov decision processes framework. In contrast, our work focuses on
online learning and game-theoretic settings, in potentially adversarial and
non-stationary environments. Moreover, (first part of) our work focuses on
_evaluating_ the intelligence level of LLM per se in decision-making (in terms
of the regret metric), while Liu et al. (2023c) focused on _developing_ a new
architecture that uses LLM as an oracle for reasoning, together with memory
and specific planning/acting subroutines, _to achieve_ sublinear (Bayesian)
regret, in stationary and stochastic environments.

##### LLMs in multi-agent environments.

The interaction of multiple LLM agents has garnered significant attention
lately. For example, Fu et al. (2023) showed that LLMs can autonomously
improve each other in a negotiation game by playing and criticizing each
other. Similarly, (Du et al., 2023; Liang et al., 2023; Xiong et al., 2023;
Chan et al., 2024; Li et al., 2023c) showed that multi-LLM _debate_ can
improve the reasoning and evaluation capabilities of the LLMs. Qian et al.
(2023); Schick et al. (2023); Wu et al. (2023) demonstrated the potential of
multi-LLM interactions and collaboration in software development, writing, and
problem-solving, respectively. Zhang et al. (2024) exhibited a similar
potential in embodied cooperative environments. More formally, multi-LLM
interactions have also been investigated under a _game-theoretic_ framework,
to characterize the _strategic_ decision-making of LLM agents. Bakhtin et al.
(2022); Mukobi et al. (2023) and Xu et al. (2023b, a) have demonstrated the
promise of LLMs in playing Diplomacy and WereWolf games, respectively, which
are both language-based games with a mixture of competitive and cooperative
agents. Note that these works utilized LLM to solve a specific rather than a
general game. Related to our work, Brookins and DeBacker (2023); Akata et al.
(2023); Lorè and Heydari (2023); Brookins and DeBacker (2023); Fan et al.
(2023) have also used (repeated) matrix games as a benchmark to evaluate the
reasoning capability and rationality of LLM agents. In contrast to our work,
these empirical studies have not formally investigated LLM agents using the
metric of _regret_ , nor through the lenses of _online learning_ and
_equilibrium-computation_ , which are all fundamental in modeling and
analyzing strategic multi-agent interactions. Moreover, our work also provides
theoretical results to explain and further enhance the no-regret property of
LLM agents.

##### LLMs & Human/Social behavior.

LLMs have also been used to _simulate_ the behavior of human beings, for
social science and economics studies (Engel et al., 2023). The extent of LLMs
simulating human behavior has been claimed as a way to evaluate the level of
its intelligence in a controlled environment (Aher et al., 2023; Tsai et al.,
2023). For example, Li et al. (2023b); Hong et al. (2024); Zhao et al. (2023)
showed that by specifying different “roles” to LLM agents, certain
collaborative/competitive behaviors can emerge. Argyle et al. (2023) showed
that LLMs can emulate response distributions from diverse human subgroups,
illustrating their adaptability. Horton (2023) argued that an LLM, as a
computational model of humans, can be used as _homo economicus_ when given
endowments, information, preferences, etc., to gain new economic insights by
simulating its interaction with other LLMs. Park et al. (2022, 2023) proposed
scalable simulators that can generate realistic social behaviors emerging in
populated and interactive social systems, and the emerging behaviors of LLM
agents in society have also been consistently observed in Chen et al. (2024,
2023). Li et al. (2023d, a) studied the opinion/behavioral dynamics of LLM
agents on social networks. These empirical results have inspired our work,
which can be viewed as an initial attempt towards quantitatively understanding
the _emerging behavior_ of LLMs as computational human models, given the well-
known justification of _equilibrium_ being a long-run emerging behavior of
_learning dynamics_ (Fudenberg and Levine, 1998) and strategic interactions
(Young, 2004; Camerer, 2011).

##### Transformers & In-context-learning.

LLMs nowadays are predominantly built upon the architecture of Transformers
(Vaswani et al., 2017). Transformers have exhibited a remarkable capacity of
_in-context-learning_ (ICL), which can construct new predictors from sequences
of labeled examples as input, without further parameter updates. This has
enabled the _few-shot learning_ capability of Transformers (Brown et al.,
2020; Garg et al., 2022; Min et al., 2022). The empirical successes have
inspired burgeoning theoretical studies on ICL. Xie et al. (2022) used a
Bayesian inference framework to explain how ICL works, which has also been
adopted in Wang et al. (2023b); Jiang (2023). Akyürek et al. (2023); Von
Oswald et al. (2023); Dai et al. (2023); Giannou et al. (2023) showed (among
other results) that ICL comes from the fact that Transformers can implement
the gradient descent (GD) algorithm. Bai et al. (2023) further established
that Transformers can implement a broad class of machine learning algorithms
in context. Moreover, Ahn et al. (2023); Zhang et al. (2023a); Mahankali et
al. (2023) proved that a _minimizer_ of the certain training loss among
single-layer Transformers is equivalent to a single step of GD for linear
regression. Li et al. (2023e) established generalization bounds of ICL from a
multi-task learning perspective. Zhang et al. (2023b) argued that ICL
implicitly implements Bayesian model averaging, and can be approximated by the
attention mechanism. They also established a result on some _regret_ metric.
However, the regret notion is not defined for (online) decision-making, and is
fundamentally different from ours that is standard in online learning and
games. Also, we provide extensive experiments to validate the no-regret
behavior by our definition. More recently, the ICL property has also been
generalized to decision-making settings. Laskin et al. (2023); Lee et al.
(2023); Lin et al. (2024) investigated the in-context reinforcement learning
(RL) property of Transformers under supervised pre-training, for solving
stochastic bandits and Markov decision processes. In contrast, our work
focuses on online learning settings with an arbitrary and _potentially
adversarial_ nature, as well as _game-theoretic_ settings. We also provide a
new _unsupervised_ loss to promote the no-regret behavior in our settings.

##### Online learning and games.

Online learning has been extensively studied to model the decision-making of
an agent who interacts with the environment sequentially, with a potentially
arbitrary sequence of loss functions (Shalev-Shwartz, 2012; Hazan, 2016), and
has a deep connection to game theory (Cesa-Bianchi and Lugosi, 2006). In
particular, regret, the difference between the incurred accumulated loss and
the best-in-hindsight accumulated loss, has been the core performance metric,
and a good online learning algorithm should have regret at most sublinear in
time $T$ (i.e., of order $o(T)$), which is referred to as being _no-regret_.
Many well-known algorithms can achieve no-regret against _arbitrary_ loss
sequences, e.g., multiplicative weight updates (MWU)/Hedge (Freund and
Schapire, 1997; Arora et al., 2012), EXP3 (Auer et al., 2002), and more
generally follow-the-regularized-leader (FTRL) (Shalev-Shwartz and Singer,
2007) and follow-the-perturbed-leader (FTPL) (Kalai and Vempala, 2005). In the
bandit literature (Lattimore and Szepesvári, 2020; Bubeck et al., 2012), such
a setting without any statistical assumptions on the losses is also referred
to as the _adversarial/non-stochastic_ setting. Following the conventions in
this literature, the online settings we focus on shall not be confused with
the stationary and _stochastic_(-bandit)/(-reinforcement learning) settings
that have been explored in several other recent works on _Transformers for
decision-making_ (Lee et al., 2023; Lin et al., 2024). Centering around the
regret metric, our work has also explored the non-stationary bandit setting
(Besbes et al., 2014), as well as the repeated game setting where the
environment itself consists of strategic agents (Cesa-Bianchi and Lugosi,
2006).

##  2 Preliminaries

##### Notation.

We use $\mathbb{N}$ and $\mathbb{N}^{+}$ to denote the sets of non-negative
and positive integers, respectively. For a finite set ${\mathcal{S}}$, we use
$\Delta({\mathcal{S}})$ to denote the simplex over ${\mathcal{S}}$. For
$d\in\mathbb{N}^{+}$, we define $[d]:=\\{1,2,\dots,d\\}$. For two vectors
$x,y\in\mathbb{R}^{d}$, we use $\langle x,y\rangle$ to denote the inner
product of $x$ and $y$. We define $\boldsymbol{0}_{d}$ and
$\boldsymbol{1}_{d}$ as a $d$-dimensional zero or one vector, and
$\boldsymbol{O}_{d\times d}$ and $I_{d\times d}$ as a $d\times d$-dimensional
zero matrix and identity matrix, respectively. We omit $d$ when it is clear
from the context. We define $e_{i}$ as a unit vector (with proper dimension)
whose $i$-th coordinate equal to $1$. For $p\in\mathbb{R}^{d},R>0$ and
$C\subseteq\mathbb{R}^{d}$ is a convex set, define
$B(p,R,\|\cdot\|):=\\{x\in\mathbb{R}^{d}\mid\|x-p\|\leq R\\}$,
$\texttt{Proj}_{C,\|\cdot\|}(p)=\operatorname*{arg\,min}_{x\in C}\|x-p\|$
(which is well defined as $C$ is a convex set), and
$\texttt{clip}_{R}(x):=[\texttt{Proj}_{B(0,R,\|\cdot\|_{2}),\|\cdot\|_{2}}(x_{i})]_{i\in[d]}$.
Define
$\texttt{Softmax}(x):=\left(\frac{e^{x_{i}}}{\sum_{i\in[d]}e^{x_{i}}}\right)_{i\in[d]}$
and $\texttt{ReLU}(x)=\max(0,x)$ for $x\in\mathbb{R}^{d}$. For
$A\in\mathbb{R}^{m\times n}$ with $A_{i}$ denoting its $i$-th column, we
define $\|A\|_{\texttt{op}}:=\max_{\|x\|_{2}\leq 1}\|Ax\|_{2}$,
$\|A\|_{2,\infty}:=\sup_{i\in[n]}\|A_{i}\|_{2}$, $\|A\|_{F}$ as the Frobenius
norm, and $A_{-1}:=A_{n}$ to denote the last column vector of $A$. We define
$\mathbb{R}^{+}:=\\{x\mid x\geq 0\\}$. For a set $\Pi$, define
$\text{diam}(\Pi,\|\cdot\|):=\sup_{\pi_{1},\pi_{2}\in\Pi}\|\pi_{1}-\pi_{2}\|$.
We define $\mathbbm{1}(\mathcal{E}):=1$ if $\mathcal{E}$ is true, and
$\mathbbm{1}(\mathcal{E}):=0$ otherwise. For a random variable sequence
$(X_{n})_{n\in\mathbb{N}}$ and random variables $X,Y$, we denote $F_{X}$ as
the cumulative distribution function of a random variable $X$,
$X_{n}\overset{p}{\to}X$ if
$\forall\epsilon>0,\lim_{n\to\infty}\mathbb{P}(|X_{n}-X|>\epsilon)=0$,
$X_{n}\overset{d}{\to}X$ if $\lim_{n\to\infty}F_{X_{n}}(x)=F_{X}(x)$ for all
$x$ where $F_{X}(x)$ is continuous, $X\overset{d}{=}Y$ if $F_{X}(x)=F_{Y}(x)$
for all $x$, $X_{n}\overset{a.s.}{\to}X$ if
$\mathbb{P}(\lim_{n\to\infty}X_{n}=X)=1$, and
$\operatorname{esssup}(X):=\inf\\{M\in\mathbb{R}:\mathbb{P}(X>M)=0\\}$. For a
random variable $X$, we use $\text{supp}(X)$ to denote its support. For
functions $f,g:\mathbb{R}\to\mathbb{R}$, we define $g(x)=\mathcal{O}(f(x))$ if
there exist $x_{0},M<\infty$ such that $|g(x)|\leq M|f(x)|$ for all $x>x_{0}$.
We use $f^{\prime}$ to denote the derivative of $f$. Let
$F:\Omega\rightarrow\mathbb{R}$ be a continuously-differentiable, strictly
convex function defined on a convex set $\Omega$. The Bregman divergence
associated with $F$ for points $p$, $q$ is defined as
$D_{F}(p,q):=F(p)-F(q)-\langle\nabla F(q),p-q\rangle$. For a sequence
$(\ell_{t})_{t\in[T]}$ for some $T\in\mathbb{N}^{+}$, we define
$\ell_{a:b}:=(\ell_{a},\cdots,\ell_{b})$ for $1\leq a\leq b\leq T$. If $a>b$,
we define $\ell_{a:b}=\emptyset$.

###  2.1 Online Learning & Games

##### Online learning.

We first consider the online learning setting where an agent interacts with
the environment for $T$ rounds, by iteratively making decisions based on the
feedback she receives. Specifically, at each time step $t$, the agent chooses
her decision policy $\pi_{t}\in\Pi$ for some bounded domain $\Pi$, and after
her commitment to $\pi_{t}$, a bounded loss function $f_{t}:\Pi\to{[-B,B]}$
for some constant $B>0$ is chosen by the environment, potentially in an
adversarial fashion. The agent thus incurs a loss of $f_{t}(\pi_{t})$, and
will update her decision to $\pi_{t+1}$ using the feedback. We focus on the
most basic setting where the agent chooses actions from a finite set
$\mathcal{A}$ every round, which is also referred to as the _Experts Problem_
(Littlestone and Warmuth, 1994; Hazan, 2016), without loss of much generality
(c.f. Section A.4 for a discussion). In this case, $\Pi$ becomes the simplex
over $\mathcal{A}$, i.e., $\Pi=\Delta(\mathcal{A})$, and
$f_{t}(\pi_{t})=\langle{\ell}_{t},\pi_{t}\rangle$ for some loss _vector_
${\ell}_{t}\in\mathbb{R}^{d}$ that may change over time, where
$d:=|\mathcal{A}|$.

At time step $t\in[T]$, the agent may receive either the full vector
${\ell}_{t}$, or only the realized loss ${\ell}_{ta_{t}}$ (we sometimes also
interchangeably write it as $\ell_{t}(a_{t})$), the $a_{t}$th element of
$\ell_{t}$, for some $a_{t}\sim\pi_{t}(\cdot)$, as feedback, which will be
referred to as online learning with _full-information feedback_ , and that
with _bandit feedback_ , respectively. The latter is also referred to as the
_adversarial/non-stochastic bandit_ problem in the multi-armed bandit (MAB)
literature. Note that hereafter, we will by default refer to this setting that
does _not_ make any assumptions on the loss sequence $({\ell}_{t})_{t\in[T]}$
simply as _online learning_. Moreover, if the loss functions change over time
(usually with certain bounded variation), we will refer to it as _non-
stationary online learning_ for short, whose bandit-feedback version is also
referred to as the _non-stationary bandit_ problem.

##### Repeated games.

The online learning setting above has an intimate connection to game theory.
Consider a normal-form game $\mathcal{G}=\langle
N,\\{\mathcal{A}_{n}\\}_{n\in[N]},\\{r_{n}\\}_{n\in[N]}\rangle$, where $N$ is
the number of players, $\mathcal{A}_{n}$ and
$r_{n}:\mathcal{A}_{1}\times\dots\times\mathcal{A}_{N}\rightarrow{[-B,B]}$ are
the action set and the payoff function of player $n$, respectively. The $N$
players repeatedly play the game for $T$ rounds, each player $n$ maintains a
strategy $\pi_{n,t}\in\Delta(\mathcal{A}_{n})$ at time $t$, and takes action
$a_{n,t}\sim\pi_{n,t}(\cdot)$. The _joint_ action
$a_{t}=(a_{1,t},\cdots,a_{N,t})$ determines the payoff of each player at time
$t$, $\\{r_{n}(a_{t})\\}_{n\in[N]}$. From a single-player’s (e.g., player
$n$’s) perspective, she encounters an online learning problem with (expected)
loss function
${\ell}_{t}:=-\mathbb{E}_{a_{-n,t}\sim\pi_{-n,t}}[r_{n}(\cdot,a_{-n,t})]$ at
time $t$, where $-n$ denotes the index for all the players other than player
$n$. We will refer to it as the _game setting_ for short, and use the terms of
“agent” and “player” interchangeably hereafter. The key difference between
online learning and repeated games is in their interaction dynamics: online
learning involves an agent facing a potentially adversarial, changing
environment (or sequence of loss functions), while in repeated games, agents
interact by playing the same game repeatedly, which might be less adversarial
when they follow specific learning algorithms.

###  2.2 Performance Metric: Regret

We now introduce _regret_ , the core performance metric used in online
learning and games. For a given algorithm $\mathscr{A}$, let
$\pi_{\mathscr{A},t}$ denote the decision policy of the agent at time $t$
generated by $\mathscr{A}$. Then, the regret, which is the difference between
the accumulated (expected) loss incurred by implementing $\mathscr{A}$ and
that incurred by the best-in-hindsight fixed decision, can be defined as

$\displaystyle\text{Regret}_{\mathscr{A}}\left((f_{t})_{t\in[T]}\right):=\sum_{t=1}^{T}f_{t}(\pi_{\mathscr{A},t})-\inf_{\pi\in\Pi}\sum_{t=1}^{T}f_{t}(\pi).$

In the Experts Problem, the definition can be instantiated as
$\text{Regret}_{\mathscr{A}}(({\ell}_{t})_{t\in[T]}):=\sum_{t=1}^{T}\langle{\ell}_{t},\pi_{\mathscr{A},t}\rangle-\inf_{\pi\in\Pi}\sum_{t=1}^{T}\langle{\ell}_{t},\pi\rangle$.
With bandit-feedback, a commonly used metric may also take further expectation
for $\text{Regret}_{\mathscr{A}}$, over the randomness of the generated
policies $(\pi_{\mathscr{A},t})_{t\in[T]}$. An algorithm $\mathscr{A}$ is
referred to as being _no-regret_ , if
$\text{Regret}_{\mathscr{A}}((f_{t})_{t\in[T]})\sim o(T)$, i.e., the regret
grows sublinearly in $T$. Widely-known no-regret algorithms include follow-
the-regularized-leader (FTRL) (Shalev-Shwartz and Singer, 2007), follow-the-
perturbed-leader (Kalai and Vempala, 2005) (See Section A.3 for a detailed
introduction).

In non-stationary online learning, one also uses the metric of _dynamic
regret_ (Zinkevich, 2003), where the _comparator_ in the definition also
changes over time, as the best decision policy at each individual time $t$:
$\text{D-Regret}_{\mathscr{A}}((f_{t})_{t\in[T]}):=\sum_{t=1}^{T}f_{t}(\pi_{\mathscr{A},t})-\sum_{t=1}^{T}\inf_{\pi\in\Pi}f_{t}(\pi)$,
which is a stronger notion than
$\text{Regret}_{\mathscr{A}}((f_{t})_{t\in[T]})$ in that
$\text{Regret}_{\mathscr{A}}((f_{t})_{t\in[T]})\leq\text{D-Regret}_{\mathscr{A}}((f_{t})_{t\in[T]})$.

##  3 Do Pre-Trained LLMs Have Regret? Experimental Validation

In this section, we explore the no-regret behaviors of representative pre-
trained LLMs (i.e., GPT-4 Turbo, GPT-4, and GPT-3.5 Turbo), in the context of
online learning and games. All experiments with LLMs are conducted using the
public OpenAI Python API (Openai, 2023).

##### Intuition why pre-trained language models may exhibit no-regret
behavior.

Transformer-based LLMs have demonstrated impressive _in-context-learning_ and
few-/zero-shot learning capabilities (Brown et al., 2020; Garg et al., 2022;
Min et al., 2022). One theoretical explanation is that, trained Transformers
can implement the _gradient descent algorithm_ on the testing loss in certain
supervised learning problems (Akyürek et al., 2023; Von Oswald et al., 2023;
Dai et al., 2023; Ahn et al., 2023; Zhang et al., 2023a; Mahankali et al.,
2023), which is inherently _adaptive_ to the loss function used at test time.
On the other hand, it is known in online learning that the simple algorithm of
_online gradient descent_ (Zinkevich, 2003) can achieve no-regret. Hence, it
seems reasonable to envision the no-regret behavior of such meta-learners in
online learning, due to their fast adaptability. However, it is not
straightforward due to the fundamental difference between multi-task/meta-
learning and online learning settings, as well as the difference between
_stationary_ and _non-stationary/adversarial_ environments in decision-making.
Next, we provide both experimental and theoretical studies to validate this
intuition.

##### Interaction protocol.

To enable the sequential interactions with LLMs, we first describe the setup
and objective of our experimental study. At each round, we incorporate the
entire history of loss vectors of past interactions into our prompts, as
concatenated texts, and ask the LLM agent to determine a policy that guides
the decision-making for the next round. Note that since we hope to _evaluate_
the intelligence level of pre-trained LLMs through online learning or games,
we only provide simple prompts that she should utilize the history
information, without providing explicit rules of _how_ to make use of the
history information, nor asking her to _minimize regret_ (in any sense). A
detailed description and an ablation study of the prompts are deferred to
Section B.1, and an illustration of the protocol in playing repeated games is
given in Figure 3.

###  3.1 Framework for No-Regret Behavior Validation

Before delving into the results, we note that to the best of our knowledge, we
are not aware of any principled framework for validating no-regret behaviors
with finite-time experimental data. Therefore, we propose two frameworks to
rigorously validate the no-regret behavior of algorithms over a _finite_ $T$,
which might be of independent interest.

##### Trend-checking framework.

We propose the following hypothesis test:

$\displaystyle H_{0}$ $\displaystyle:\text{The sequence
}\left(\text{Regret}_{\mathscr{A}}\left((f_{\tau})_{\tau\in[t]}\right)/t\right)_{t=1}^{\infty}\text{
either diverges or converges to a positive constant}$ $\displaystyle H_{1}$
$\displaystyle:\text{The sequence
}\left(\text{Regret}_{\mathscr{A}}\left((f_{\tau})_{\tau\in[t]}\right)/t\right)_{t=1}^{\infty}\text{
converges to 0}$

with $H_{0}$ and $H_{1}$ denoting the null and alternative hypotheses,
respectively. The notion of convergence is related to $T\to\infty$ by
definition, making it challenging to verify directly. As an alternative, we
propose a more tractable hypothesis test, albeit a weaker one, that still
captures the essence of our objective:

$\displaystyle H_{0}$ $\displaystyle:\text{The sequence
}\left(\text{Regret}_{\mathscr{A}}\left((f_{\tau})_{\tau\in[t]}\right)/t\right)_{t\in[T]}\text{
does not exhibit a decreasing trend}$ $\displaystyle H_{1}$
$\displaystyle:\text{The sequence
}\left(\text{Regret}_{\mathscr{A}}\left((f_{\tau})_{\tau\in[t]}\right)/t\right)_{t\in[T]}\text{
shows a decreasing trend}.$

Ideally, one should check if
$\text{Regret}_{\mathscr{A}}\left((f_{\tau})_{\tau\in[t]}\right)/t$ approaches
zero as $t$ goes to infinity. With a finite $T$ value, testing these
hypotheses provides a method to quantify this – whether we reject $H_{0}$
offers a way to measure it. To this end, one needs to count the number of
$\text{Regret}_{\mathscr{A}}\left((f_{\tau})_{\tau\in[t]}\right)/t-\text{Regret}_{\mathscr{A}}\left((f_{\tau})_{\tau\in[t+1]}\right)/(t+1)>0$,
for which we use Proposition 1 below (whose proof is deferred to Section B.2)
to provide some understanding of (how small) the probability it happens under
various counts. For example, with the default choice of $T=25$ in our
experiments later, one can see from Proposition 1 that:
$\mathbb{P}_{H_{0}}(\mathcal{E}(17,25))<0.032,\mathbb{P}_{H_{0}}(\mathcal{E}(19,25))<0.0035,\mathbb{P}_{H_{0}}(\mathcal{E}(21,25))<0.00014$,
i.e., one can easily reject $H_{0}$ with high probability. We will report the
$p$-value of $H_{0}$, denoted as $p_{trend}$, as the output of this framework.

######  Proposition 1.

_( $p$-value of the null hypothesis)._ Define the event

$\displaystyle\mathcal{E}(s,T):=\left\\{\text{The~{}number~{}of~{}}\frac{\text{Regret}_{\mathscr{A}}\left((f_{\tau})_{\tau\in[t]}\right)}{t}-\frac{\text{Regret}_{\mathscr{A}}\left((f_{\tau})_{\tau\in[t+1]}\right)}{t+1}>0\text{~{}~{}for~{}~{}}t=1,\dots,T\text{~{}is~{}at~{}least~{}~{}}s\geq\frac{T-1}{2}\right\\}.$

Under the assumption that the null hypothesis $H_{0}$ holds, the probability
of this event happening is bounded as
$\mathbb{P}_{H_{0}}(\mathcal{E}(s,T))\leq\frac{1}{2^{T-1}}\sum_{t=s}^{T-1}\begin{pmatrix}T-1\\\
t\end{pmatrix}$.

##### Regression-based framework.

In complement to the statistical framework above, we propose an alternative
approach by fitting the data with regression. In particular, one can use the
data

$\displaystyle\left\\{\left(t,\log\text{Regret}_{\mathscr{A}}\left((f_{\tau})_{\tau\in[t]}\right)\right)\right\\}_{t\in[T]}$

to fit a linear function $g(t)=\beta_{0}\log t+\beta_{1}$, where the estimate
of $\beta_{0}$, i.e., $\widehat{\beta}_{0}$, satisfying
$\widehat{\beta}_{0}<1$ may be used to indicate the no-regret behavior, i.e.,
the _sublinear_ growth of
$\text{Regret}_{\mathscr{A}}\left((f_{\tau})_{\tau\in[t]}\right)$ over time.
While being simple, it cannot be directly used when
$\text{Regret}_{\mathscr{A}}\left((f_{\tau})_{\tau\in[t]}\right)<0$, so we set
$\log\text{Regret}_{\mathscr{A}}\left((f_{\tau})_{\tau\in[t]}\right)$ as $-10$
if this happens. We define $p_{reg}$ as the $p$-value of the regression
parameter $\widehat{\beta}_{0}$, and will report the pair of
$(\widehat{\beta}_{0},p_{reg})$ as the output of this framework.

###  3.2 Results: Online Learning

We now present the experimental results on the no-regret behavior of pre-
trained LLMs in online learning in: 1) arbitrarily changing environments, 2)
non-stationary environments, and 3) bandit-feedback environments.

##### Online learning in arbitrarily changing environment.

We first consider the setting with arbitrarily changing environments, which
are instantiated as follows: 1) _Randomly-generated loss sequences_. At every
timestep, we generate a random loss vector
${\ell}_{t}\sim\operatorname{Unif}([0,10]^{d})$ or
${\ell}_{t}\sim\mathcal{N}(5\boldsymbol{1}_{d},I)$ with clipping to $[0,10]$
to ensure the boundedness, such that the loss vectors of different timesteps
can be arbitrarily different; 2) _Loss sequences with a predictable trend._
Although many real-world environments may change, they often change following
certain patterns. Therefore, we consider two representative trends, a _linear_
trend and a _periodic_ (sinusoid) trend. For the linear trend, we sample
$a,b\sim\text{Unif}([0,10]^{d})$ and let $\ell_{t}=(b-a)\frac{t}{T}+a$ for
each $t\in[T]$. For the periodic trend, we sample
$a,b\sim\text{Unif}([0,10]^{d})$ and let $\ell_{t}=5(1+\sin(at+b))$ for each
$t\in[T]$. In the experiments, we choose $d=2$. The average regret (over
multiple randomly generated instances) performance is presented in Figure 1,
where we compare GPT-4 with well-known no-regret algorithms, FTRL with entropy
regularization and FTPL with Gaussian perturbations (with tuned parameters).
It is seen that these pre-trained LLMs can indeed achieve no-regret and often
have smaller regrets than these baselines.

##### Online learning (in non-stationary environment).

We then experiment on the setting where the losses are still changing over
time, but their total variations across time are bounded, more concretely,
sublinear in $T$. Correspondingly, we consider the stronger metric of _dynamic
regret_ here to measure the performance. Note that without constraining the
variation of the loss vectors, dynamic regret can be linear w.r.t. $T$ in the
worst case. Hence, we generate the loss vectors in two different ways: 1)
_Gradual variation._ We firstly sample
${\ell}_{1}\sim\text{Unif}([0,10]^{d})$. Then for each $t\geq 2$, we uniformly
and randomly generate ${\ell}_{t+1}$ under the constraint
$\|{\ell}_{t+1}-{\ell}_{t}\|_{\infty}\leq\frac{1}{\sqrt{t}}$, such that the
variations over time are guaranteed to satisfy
$\sum_{t=1}^{T-1}\|{\ell}_{t+1}-{\ell}_{t}\|_{\infty}={o(T)}$; 2) _Abrupt
variation._ We randomly generate ${\ell}_{1}\sim\text{Unif}([0,10]^{d})$ and
$m$ time indices $\\{t_{i}\\}_{i\in[m]}$ from $\\{1,2,\cdots,T\\}$. At each
time step $t_{i}$ for $i\in[m]$, the sign of the loss vector ${\ell}_{t_{i}}$
is flipped, i.e., we let ${\ell}_{t_{i}}\leftarrow
10\boldsymbol{1}_{d}-{\ell}_{t_{i}}$. For the specific choice of $T=25$ in our
experiments, we choose $m=3$. For both cases, the average dynamic regret
results are presented in Table 1. It can be seen that GPT-4 achieves sublinear
dynamic regret and outperforms _FTRL/FTPL with Restart_ , a standard variant
of FTRL/FTPL for non-stationary online learning (see e.g., Besbes et al.
(2014)). We refer to Section A.3 for a more detailed introduction of FTRL/FTPL
with Restart.

##### Extension to bandit-feedback settings.

Although pre-trained LLMs have achieved good performance in online learning
with full-information feedback, it is unclear whether they can still maintain
no-regret with only bandit feedback. For such problems, we modify the prompt
and protocol of interactions slightly, where we still ask the LLM agent to
provide a policy $\pi_{t}$ at time step $t$, then sample one
$a_{t}\sim\pi_{t}(\cdot)$. In the bandit setting, the LLM agent can only
access $(a_{t},\ell_{ta_{t}})$. Instead of directly feeding it to the agent,
we feed an estimate of the loss vector $\widehat{\ell}_{t}\in\mathbb{R}^{d}$,
where
$\widehat{\ell}_{t}(a)\leftarrow\frac{\ell_{t}(a)}{\pi_{t}(a)}\mathbbm{1}(a_{t}=a)$
for all $j\in[d]$. Note that such an operation of _re-weighting_ the loss by
the inverse of the probability is standard in online learning when adapting
full-information-feedback no-regret algorithms to the bandit-feedback ones
(Auer et al., 2002). Later, we will also show the benefits of such operations
(c.f. Section 4). We compare the performance of pre-trained LLMs with that of
the counterparts of FTRL with bandit feedback, e.g., EXP3 (Auer et al., 2002)
and the bandit-version of FTPL (Abernethy et al., 2015), in both Figure 2 and
Table 1, where GPT-4 consistently achieves lower regret.

Figure 1: Regret of GPT-3.5 Turbo/GPT-4 for online learning with full-
information feedback in $4$ different settings. It performs comparably and
sometimes even better than well-known no-regret learning algorithms, FTRL and
FTPL. Figure 2: Regret of GPT-3.5 Turbo/GPT-4 for online learning with bandit
feedback in $4$ different settings. It performs comparably and sometimes even
better than well-known no-regret learning algorithms, variants of FTRL and
FTPL with bandit-feedback. Figure 3: Demonstration of the prompts and
interaction protocol for multi-player repeated games. A human moderator does
not provide the game’s payoff matrices to the LLMs. Instead, at each round,
the human moderator provides each player’s own payoff vector history.

###  3.3 Results: Multi-Player Repeated Games

We now consider the setting when multiple LLMs make online strategic decisions
in a _shared_ environment repeatedly. Specifically, at each round, the loss
vectors each agent receives are determined by both her payoff matrix and the
strategies of all other agents. Note that the payoff matrix is not directly
revealed to the LLM agent, but she has to make decisions in a completely
online fashion based on the payoff vector marginalized by the opponents’
strategies (See Figure 3 for a prompt example). This is a typical scenario in
learning in (repeated) games (Fudenberg and Levine, 1998).

##### Representative games.

We first test the repeated play of pre-trained LLMs on $6$ representative
general-sum games (_win-win, prisoner’s dilemma, unfair, cyclic, biased,_ and
_second best_) studied in Robinson and Goforth (2005) (see a detailed
introduction of these games in Section A.5). For each type of the game, we
conduct $20$ repeated experiments.

##### Randomly generated games.

To further validate the no-regret behavior of LLMs, we also test on $50$
randomly generated three-player general-sum games, and $50$ randomly generated
four-player general-sum games, where each entry of the payoff matrix is
sampled randomly from $\operatorname{Unif}([0,10])$. These are larger and more
challenging settings than the structured and representative ones above.

We summarize the experimental results in Figure 4, which are similar to the
above in the online setting: for all types of games, GPT-4 achieves sublinear
regret, which is comparable with that obtained by FTRL for most games. We
provide six instances of three-player general-sum games and six instances of
four-player general-sum games in Figure 5 and Figure 6, respectively.
Occasionally, GPT-4 even provides a negative regret value.

Figure 4: Regret of GPT-3.5 Turbo/GPT-4 for repeated games of $3$ different
game sizes, where the sublinear regret is validated by both of our statistical
frameworks. Due to the symmetry of agents in randomly generated games, we
report the regret of one agent for ease of presentation. Figure 5: Regret of
GPT-4 and the FTRL algorithm in $6$ randomly generated three-player general-
sum games. GPT-4 has comparable (even better) no-regret properties when
compared with the FTRL algorithm. Figure 6: Regret of GPT-4 and the FTRL
algorithm in $6$ randomly generated four-player general-sum games. GPT-4 has
comparable (even better) no-regret properties when compared with the FTRL
algorithm, according to the frameworks in Section 3.1 and the graphic trends.

Figure 7: (left) Regret of both GPT-4 and GPT-4 Turbo under the canonical
counterexample for FTL (Hazan, 2016, Chapter 5). (mid, right) Failure of GPT-4
and GPT-4 Turbo on two scenarios for regrettable behavior of GPT, while
Transformers with regret-loss provide no-regret behaviors.

Dynamic regret | GPT-4 | GPT-3.5 Turbo | FTRL | FTPL
---|---|---|---|---
Full information | Gradual variation |  | $12.61\pm 7.01$
---
$(p_{trend},\widehat{\beta}_{0},p_{reg})=(0.0,0.58,0.0)$
| $19.09\pm 11.33$
---
$(p_{trend},\widehat{\beta}_{0},p_{reg})=(0.0,0.83,0.0)$
$36.58\pm 24.51$ | $35.19\pm 22.51$
Abrupt variation |  | $30.0\pm 19.91$
---
$(p_{trend},\widehat{\beta}_{0},p_{reg})=(0.01,0.87,0.0)$
| $33.65\pm 22.51$
---
$(p_{trend},\widehat{\beta}_{0},p_{reg})=(0.08,0.96,0.0)$
$36.52\pm 27.68$ | $36.24\pm 28.22$
Bandit | Gradual variation |  | $21.39\pm 10.86$
---
$(p_{trend},\widehat{\beta}_{0},p_{reg})=(0.0,0.78,0.0)$
| $28.42\pm 21.6$
---
$(p_{trend},\widehat{\beta}_{0},p_{reg})=(0.0,0.83,0.0)$
$37.64\pm 21.97$ | $36.37\pm 20.7$
Abrupt variation |  | $35.94\pm 28.93$
---
$(p_{trend},\widehat{\beta}_{0},p_{reg})=(0.42,0.95,0.0)$
| $30.76\pm 25.48$
---
$(p_{trend},\widehat{\beta}_{0},p_{reg})=(0.92,1.01,0.0)$
$36.52\pm 27.68$ | $38.82\pm 26.17$

Table 1:  Dynamic regret of GPT-3.5 Turbo/GPT-4 in a non-stationary
environment with either full-information or bandit feedback. Every experiment
is conducted with 25 rounds. No-regret behaviors of GPT-3.5 Turbo/GPT-4 are
validated by both of our frameworks (low $p$-values and
$\widehat{\beta}_{0}<1$). The only exception is GPT-3.5 Turbo on loss sequence
with abrupt variations under bandit feedback. This indicates that GPT-3.5
Turbo may not be capable of dealing with an abruptly changing environment with
limited feedback, although the average regret achieved eventually is still
lower than that of other baselines.

###  3.4 Pre-Trained LLM Agents May Still Have Regret

It seems tempting to conclude that pre-trained LLMs can achieve no-regret in
both online learning and playing repeated games. However, is this capability
_universal_? We show that the no-regret property might break for LLM agents if
the loss vectors are generated in a more adversarial way.

##### Canonical counterexample for follow-the-leader.

To begin with, we consider a well-known example that _follow-the-leader_ (FTL)
algorithm (Shalev-Shwartz, 2012) suffers from linear regret (Hazan, 2016,
Chapter 5), where $\ell_{1}(1)=5,\ell_{1}(2)=0$ and
$\ell_{t}(2-t\%2)=10,\ell_{t}(1+t\%2)=0$ for $t\geq 2$, where $\%$ is the
modulo operation. Interestingly, GPT-4 agent can easily identify the pattern
for the loss sequence that the optimal action _alternates_ , thus accurately
predicting the loss it will receive and achieving nearly zero regret in Figure
7. In other words, GPT-4 agent seems to not fail in the same way as FTL, which
is known to be due to the lack of randomness in prediction.

##### Less predictable loss sequence.

Inspired by the counterexample above, we design a new loss sequence that is
_similar but less predictable_. Specifically, we construct the following
(simple) loss sequence with $2$ actions such that
${\ell}_{t}(1+t\%2)=\min(25/t,10),{\ell}_{t}(2-t\%2)\sim\text{Unif}([9,10])$
for $t\in[25]$.

##### Adaptive loss sequence.

We also develop a simpler but more _adaptive_ loss sequence that takes the
full power of the adversary in the online learning setup. After the GPT-4
agent provides $\pi_{t}$, we choose ${\ell}_{t}$ such that
${\ell}_{t}(\operatorname*{arg\,max}_{i}\pi_{ti})=10$ and
${\ell}_{t}(3-\operatorname*{arg\,max}_{i}\pi_{ti})=0$. We report the average
regret over $20$ repeated experiments for the later two settings using GPT-4
and more advanced GPT-4 Turbo in Figure 7, where we cannot reject the
hypothesis that GPT-4 (Turbo) has linear-regret by either our trend-checking
or regression-based framework.

These observations have thus motivated us to design new approaches to better
promote the no-regret property of LLM agents, with additional training, as to
be detailed in Section 5. Before delving into the design of such a _stronger_
LLM agent, we first provide some theoretical insights into why pre-trained
LLMs have already exhibited good no-regret behaviors oftentimes.

##  4 Why Are Pre-Trained LLMs (No-)Regret? A Hypothetical Model and Some
Theoretical Insights

We now provide some plausible explanations about the no-regret behavior of
pre-trained LLMs, as observed in Sections 3.2 and 3.3. Note that our
explanations have to be _hypothetical_ by nature, since to the best of our
knowledge, the details of pre-training these popular LLMs (e.g., GPT-3.5 Turbo
and GPT-4), regarding data distribution, training algorithm, etc., have not
been revealed. We instead make the explanations based on some common
assumptions and arguments in the literature for modeling human behaviors, and
the recent literature on understanding LLMs/Transformers.

###  4.1 Pre-Trained LLMs Have Similar Regret as Humans (Who Generate Data)

We first provide a direct observation based on some existing speculation on
the capability of Transformer-based LLMs. Recently, a growing literature has
evidenced that the intelligence level of LLM agents are determined by, and in
fact mimic, those of human beings who generate the data for pre-training the
models (Park et al., 2022; Argyle et al., 2023; Horton, 2023). The key
rationale was that, LLMs (with Transformer parameterization) can approximate
the _pre-training data distribution_ very well (Xie et al., 2022; Zhang et
al., 2023b; Lee et al., 2023). In such a context, one can expect that LLM
agents can achieve similar regret as human decision-makers who generate the
pre-training data, as we formally state below.

######  Observation 1.

An LLM agent is said to be pre-trained with an _$\epsilon$ -decision error_
if, for any arbitrary $t$ and loss sequences $({\ell}_{i})_{i\in[t]}$, the
following condition holds:

$\displaystyle\sup_{\pi\in\Pi}\quad\big{|}P_{\text{data}}(\pi{\,|\,}({\ell}_{i})_{i\in[t]})-P_{\text{LLM}}(\pi{\,|\,}({\ell}_{i})_{i\in[t]})\big{|}\leq\epsilon,$

where $P_{\text{data}}$ and $P_{\text{LLM}}$ are the pre-training data
distribution and the decision policy distribution of the pre-trained LLM,
respectively. Then, the regret of an LLM agent with $\epsilon$-decision error
is bounded as:

$\displaystyle\text{(D-)Regret}_{\text{LLM}}\left(({\ell}_{t})_{t\in[T]}\right)\in\left[\text{(D-)Regret}_{\text{data}}\left(({\ell}_{t})_{t\in[T]}\right)\pm\epsilon\|{\ell}_{t}\|\sup_{\pi\in\Pi}\|\pi\|\right],$

where $[a\pm b]:=[a-b,a+b]$.

1 shows that the pre-trained LLM-agent’s regret can be controlled by that of
the pre-training dataset and the decision error $\epsilon$. A small $\epsilon$
can be achieved if LLM is constructed by a rich function class, e.g., the
Transformer architecture (Zhang et al., 2023b; Lin et al., 2024). We defer a
proof of the result to Appendix C.

Note that the above observation does not provide the full picture – the
$\text{(D-)Regret}_{\text{data}}\left(({\ell}_{t})_{t\in[T]}\right)$, which
denotes the (dynamic-)regret of using
$P_{\text{data}}\left(\pi{\,\big{|}\,}({\ell}_{i})_{i\in[t]}\right)$ for
online learning, is not necessarily sublinear in $T$. We discuss next under
what (natural) models and pre-training processes, the no-regret behavior of
pre-trained LLMs may emerge.

###  4.2 A Human Decision-Making Model: Quantal Response

A seminal model for human decision-making behavior is the _quantal response_
model, which assumes that humans are often _imperfect_ decision-makers, and
their bounded rationality can be modeled through unseen latent variables that
influence the decision-making process (McFadden, 1976; McKelvey and Palfrey,
1995). Formally, the quantal response is defined as follows:

######  Definition 1 (Quantal response).

Given a loss vector $\ell\in\mathbb{R}^{d}$, a noise distribution
$\epsilon\sim P_{\text{noise}}$, and $\eta>0$, the quantal response is defined
as

$\displaystyle
P_{\text{quantal}}^{\eta}\big{(}a{\,\big{|}\,}\ell\big{)}=\mathbb{P}\left(a\in\operatorname*{arg\,min}_{a^{\prime}\in\mathcal{A}}~{}~{}z(a^{\prime})\right),\qquad\text{where~{}~{}
$z=\ell+\eta\epsilon$.}$

In essence, this implies that humans are rational but with respect to (w.r.t.)
the latent variable $z$, a perturbed version of $\ell$, instead of $\ell$ per
se. This addition of noise to the actual loss vector characterizes the bounded
rationality of humans in decision-making.

The traditional quantal response formulation primarily focused on scenarios
with a single loss vector. In online decision-making, given the _history_
information, the human at each time $t$ is faced with _multiple_ loss vectors.
Hence, we adopt the following generalization to model the decision-making
behavior in this setting.

######  Definition 2 (Quantal response against multiple losses).

Given a set of loss vectors $({\ell}_{i})_{i\in[t]}$, a noise distribution
$P_{\text{noise}}$, and $\eta_{t}>0$, the generalized quantal response against
$({\ell}_{i})_{i\in[t]}$ is defined as

$P_{\text{quantal}}^{\eta_{t}}\left(a{\,\big{|}\,}({\ell}_{i})_{i\in[t]}\right):=P_{\text{quantal}}^{\eta_{t}}\left(a{\,\bigg{|}\,}\sum_{i=1}^{t}{\ell}_{i}\right).$

For $t=0$, we define
$P_{\text{quantal}}^{\eta_{t}}\left(a{\,\big{|}\,}({\ell}_{i})_{i\in[t]}\right):=P_{\text{quantal}}^{\eta_{0}}\left(a{\,\big{|}\,}\emptyset\right)=\frac{1}{d}$.

In simpler terms, the generalized quantal response is defined as the standard
quantal response against some scaled summation of the losses. Note that such a
_dynamic_ version of quantal response also has implications from behavior
economics, and has been recently used to model human behaviors in sequential
decision-making (Ding et al., 2022) (in stochastic and stationary
environments). Indeed, such a response against multiple loss vectors is
believed to be natural, and has also been widely adopted in well-known no-
regret learning algorithms of _smooth/stochastic fictitious play_ (Fudenberg
and Kreps, 1993) and _follow-the-perturbed-leader_ (Kalai and Vempala, 2005),
whose formal definitions can be found in Section A.3. Finally, note that the
response model in Definition 2 does not necessarily involve a _sequential_
decision-making process, i.e., the set of losses may not come from the history
of an online learning process. With this (natural) human response model in
hand, we hypothesize that powerful pre-trained LLMs also behave similarly as
such a model. To illustrate how Definition 2 can potentially capture also the
behavior of LLMs instead of only humans, we have also provided examples of
LLMs _explaining_ how they output their policies in Section B.4. It can be
observed that the LLM agent tends to use the history of the reward vectors by
looking at the “sum/average of the accumulated rewards”, and tends to
introduce “randomization” in decision-making, in order to be “less predictable
and exploitable”. These are known to be key to achieving no-regret behaviors
in online learning and games (Cesa-Bianchi and Lugosi, 2006). Hence, we
analyze a case where pre-training under certain canonical data assumptions can
provably lead to the quantal response behaviors and further yield no-regret
guarantees, to gain some insights into the empirical observations in Sections
3.2 and 3.3.

###  4.3 Case Study: Pre-Training under Canonical Data Distribution

Pre-training of LLMs often involves the approach of _next-token prediction_.
When applying LLMs to sequential decision-making, the model receives the
context of the decision-making sequence and then generates the _action_. This
process can be conceptualized as _predicting the optimal action_ in the form
of the next token prediction. For instance, Yao et al. (2023b); Shinn et al.
(2023); Liu et al. (2023a, c) demonstrated how decision-making may be framed
in this way. Concretely, LLM receives the context as
$(x_{1},x_{2},\cdots,x_{N_{1}})$ and output $(x_{N_{1}+1},\cdots,x_{N_{2}})$
for some $N_{1},N_{2}\in\mathbb{N}^{+}$ and $N_{1}<N_{2}$, where each
$x_{i}\in\mathcal{V}$ represents one _natural language token_ for
$i\in[N_{2}]$, and $\mathcal{V}$ is the finite token set. Afterwards, the
human user extracts the corresponding decision action $a$ from the text
$(x_{N_{1}+1},\cdots,x_{N_{2}})$.

Meanwhile, in these cases, large models such as Transformers are often
(pre-)trained for (sequential) decision-making under several
_fixed/stationary_ environments (Laskin et al., 2023; Lin et al., 2024; Lee et
al., 2023; Reed et al., 2022), which may limit their ability to handle
_arbitrary/non-stationary/adversarial_ loss sequences in our online learning
setup. Thus, it is natural to ask: _Is it possible to have no-regret behaviors
emerging as a consequence of this (optimal) action prediction, under only a
fixed pre-training distribution of stationary environments?_

Here we analyze a standard pre-training objective on a token sequence
distribution $x_{1:N_{t+1}}\sim P^{text}_{t}$ for given $t\in[T]$, which is
the expected log-likelihood maximization for next-token prediction:

$\displaystyle\max_{\theta\in\Theta}\quad\mathbb{E}_{x_{1:N_{t+1}}\sim
P^{text}_{t}}\sum_{j=1}^{N_{t+1}}\log\text{LLM}_{\theta}\left(x_{j}{\,|\,}x_{1:j-1}\right),$
(1)

where we define
$\text{LLM}_{\theta}\left(x_{1}{\,|\,}x_{1:0}\right)=\text{LLM}_{\theta}\left(x_{1}\right)$,
and $\Theta$ denotes the parameter space of the LLM.

For the pre-training data distribution, intuitively, we model it as follows:
there exists a latent variable $z$, representing the loss of the underlying
_static_ decision-making problem. The pre-training dataset, however, only
contains _partial observations_ $x_{1:N_{t}}$ (a natural language
representation of ${\ell}_{1:t}$) of $z$ due to imperfect data collection. The
presence of partial observations could be attributed to the fact that $z$ is
only _privately_ known by the data-generator (human), representing the
intentions of a human being/data-generator. Hence, LLM will only be pre-
trained with partial and noisy information about $z$. Meanwhile, we assume
that the optimal action $x_{N_{t}+1:N_{t+1}}$ (a natural language
representation of $a$) w.r.t. the underlying loss vector $z$ is available in
the pre-training dataset as the _label_ , which could come from user surveys,
personal blogs, or explicit data annotation. We formalize such a scenario in
the assumption below:

######  Assumption 1.

Given $T\in\mathbb{N}^{+}$, $t\in[T]$, and $N_{t+1}\in\mathbb{N}^{+}$, there
is a latent variable $z$, $\ell_{1:t}$, $N_{1},\cdots N_{t}\in[N_{t+1}]$, and
$N_{0}=0$, such that
$\mathbb{P}(z,\ell_{1:t},x_{1:N_{t+1}})=\mathbb{P}(z,\ell_{1:t})\mathbb{P}(x_{1:N_{t}}{\,|\,}\ell_{1:t})\mathbb{P}(x_{N_{t}+1:N_{t+1}}{\,|\,}z),$
and

$\displaystyle
P^{text}_{t}(x_{1:N_{t+1}})=\mathbb{P}(x_{1:N_{t+1}})=\int_{z}\int_{\ell_{1:t}}\mathbb{P}(z,\ell_{1:t},x_{1:N_{t+1}})d\ell_{1:t}dz,$

where we assume tokens $x_{1:N_{t}}$ encode the context information, i.e.,
information for $\ell_{1:t}$, and the user will decode action $a$ from
$x_{N_{t}+1:N_{t+1}}$. More formally, we denote the mappings that decode such
semantic information into numeric values as $f$, $g$, such that
$f(x_{N_{i-1}+1:N_{i}})=\ell_{i}\in\mathbb{R}^{d}$ for each $i\in[t]$ and
$g(x_{N_{t}+1:N_{t+1}})=a\in\mathcal{A}$.

To further understand our assumption, we provide the following example and
lemma, which recovers the prominent human behavior model introduced in Section
4.2, quantal response, under some canonical data distributions.

######  Example 1 (An example instantiating 1).

We consider a common decision-making task that may generate the training data,
_recommender systems_. An instance of the text data could be: “On September
29, 2023, user X clicked movie A three times, movie B eight times, and movie C
five times”. This sentence corresponds to $x_{N_{i-1}+1:N_{i}}$ for some
$i\in[t]$ and serves as a natural language depiction of the numerical
$\ell_{i}$. The corresponding label $x_{N_{t}+1:N_{t+1}}$ can be obtained by
some user survey: “User X’s favorite movie is movie B”. Meanwhile, $z$
represents user X’s latent, genuine preference for each movie – information
that is private to the user, and cannot be observed or collected in the pre-
training dataset. In this example, 1 suggests that $x_{1:N_{t}}$, which
records the frequency of interactions with each movie, serves as an _imperfect
estimate_ of the user’s latent, genuine preference for the movies, while the
text $x_{N_{t}+1:N_{t+1}}$ depicts the user’s favorite movie only based on her
latent $z$.

######  Lemma 1.

_(Alignment of 1 with quantal response)._ Fix $t\in[T]$, $\sigma>0$. If we
model the noise of data collection to be i.i.d. Gaussian distribution in the
numeric value space, i.e.,

$\mathbb{P}\left(\left\\{f(x_{N_{i-1}+1:N_{i}})\right\\}_{i\in[t]}{\,\big{|}\,}z\right)=\prod_{i=1}^{t}\mathbb{P}\left(f(x_{N_{i-1}+1:N_{i}}){\,\big{|}\,}z\right)\propto\prod_{i=1}^{t}\exp\left(-\frac{\|f(x_{N_{i-1}+1:N_{i}})-z\|_{2}^{2}}{2\sigma^{2}}\right),$

the prior distribution of the latent variable $z$ is also Gaussian, i.e.,
$z\sim\mathcal{N}(\boldsymbol{0}_{d},\sigma^{2}I)$, and the text labels
satisfy that
$\mathbb{P}(g(x_{N_{t}+1:N_{t+1}}){\,|\,}z)=\mathbbm{1}\left(g(x_{N_{t}+1:N_{t+1}})\in\operatorname*{arg\,min}_{a\in\mathcal{A}}z_{a}\right)$,
then we have

$\mathbb{P}\left(g(x_{N_{t}+1:N_{t+1}}){\,\big{|}\,}x_{1:N_{t}}\right)=P_{quantal}^{\sigma\sqrt{t+1}}\left(g(x_{N_{t}+1:N_{t+1}}){\,\big{|}\,}\left\\{f(x_{N_{i-1}+1:N_{i}})\right\\}_{i\in[t]}\right),$

with $P_{noise}=\mathcal{N}(\boldsymbol{0}_{d},I)$ in Definition 2, i.e., the
action $a=g(x_{N_{t}+1:N_{t+1}})$ extracted from the text
$x_{N_{t}+1:N_{t+1}}$ is a quantal response w.r.t. the loss vectors
$\left(f(x_{N_{i-1}+1:N_{i}})\right)_{i\in[t]}$.

We defer the proof of the lemma to Section C.2. Now based on this lemma, we
provide the no-regret guarantees of the corresponding pre-trained LLM.

######  Theorem 1.

_(Emergence of no-regret behavior)._ Under the assumptions of Lemma 1, suppose
the function class of $\text{LLM}_{\theta}$ is expressive enough such that for
all $t\in[T]$, $\max_{\theta\in\Theta}\mathbb{E}_{x_{1:N_{t+1}}\sim
P^{text}_{t}}\sum_{j=1}^{N_{t+1}}\log\text{LLM}_{\theta}\left(x_{j}{\,|\,}x_{1:j-1}\right)=\max_{\left\\{q_{j}\in\left\\{\mathcal{V}^{j-1}\rightarrow\Delta(\mathcal{V})\right\\}\right\\}_{j\in[N_{t+1}]}}\mathbb{E}_{x_{1:N_{t+1}}\sim
P^{text}_{t}}\sum_{j=1}^{N_{t+1}}\log
q_{j}\left(x_{j}{\,|\,}x_{1:j-1}\right)$, where we define
$q_{1}(x_{1}{\,|\,}x_{1:0}):=q_{1}(x_{1})$, and $\theta^{\star}$ maximizes
Equation 1. Then, there exist (simple) algorithms using
$\text{LLM}_{\theta^{\star}}$ to achieve no (dynamic) regret for (non-
stationary) online learning with full-information/bandit feedback. To be
specific, for (2) and (4), by defining the variation bound
$\sum_{t=1}^{T-1}\|\ell_{t+1}-\ell_{t}\|_{\infty}\leq V_{T}$ such that
$V_{T}\leq T$ and $V_{T}=\Theta(T^{\rho})$ for some $\rho\in(0,1)$, it holds
that for large enough $T$, $d$:

(1) For online learning with full-information feedback,
$\text{Regret}_{\text{LLM}{{}_{\theta^{\star}}}}\left(({\ell}_{t})_{t\in[T]}\right)\leq\mathcal{O}\left(\sqrt{T\log
d}\right)$;

(2) For non-stationary online learning with full-information feedback,

$\text{D-Regret}_{\text{LLM}{{}_{\theta^{\star}}}}\left(({\ell}_{t})_{t\in[T]}\right)\leq\mathcal{O}\left((\log
d\ V_{T})^{1/3}T^{2/3}\right);$

(3) For online learning with bandit feedback,

$\mathbb{E}\left[\text{Regret}_{\text{LLM}{{}_{\theta^{\star}}}}\left(({\ell}_{t})_{t\in[T]}\right)\right]\leq\mathcal{O}\left((\log
d)^{1/2}dT^{1/2+1/\log T}\log T\right);$

(4) For non-stationary online learning with bandit feedback,

$\mathbb{E}\left[\text{D-Regret}_{\text{LLM}{{}_{\theta^{\star}}}}\left(({\ell}_{t})_{t\in[T]}\right)\right]\leq\mathcal{O}\left((T^{2}d^{2}V_{T})^{1/3}(\log
d)^{1/2}T^{1/\log T}\log T\right).$

######  Remark 1 (Implication for playing repeated games).

First, we note that the no-regret guarantee in the online setting is stronger
than and thus implies that in the game setting, since regret by definition
handles arbitrary/adversarial environments, while in playing games the
opponents are not necessarily as adversarial. Second, it is folklore that if
all players in the repeated game follow no-regret learning algorithms, then
the time-average policies of all players during learning constitute an
approximate _coarse correlated equilibrium_ of the game (Cesa-Bianchi and
Lugosi, 2006). Hence, the results (1) and (2) in Theorem 1 imply that a coarse
correlated equilibrium will emerge in the long run from the interactions of
the LLM agents (under certain assumptions as in the theorem).

We present proofs of the non-asymptotic bounds for (dynamic) regret in Section
C.4. Furthermore, we demonstrate that the prior distribution of $z$ could also
be replaced by a general distribution (c.f. Theorem 5), in order to obtain the
above results. We also point out that 1 may be further relaxed to better match
the actual LLMs’ pre-training data distributions from diverse sources (c.f.
Section C.5).

It is important to observe that even when pre-training is conducted solely
with _stationary_ loss vector generation ($\ell_{1:t}$ are i.i.d. conditioned
on $z$), it can still lead to the emergence of no-regret behavior in online
learning with potentially adversarial losses. Key in the proof is a connection
of pre-trained LLM models to the online learning algorithm of FTPL.

##### Comparison to Lee et al. (2023); Lin et al. (2024).

Intriguingly, similar assumptions and pre-training objectives have also been
considered in the very recent work of Lee et al. (2023); Lin et al. (2024) for
studying in-context reinforcement learning property of Transformers under
supervised pre-training. Lee et al. (2023) established its equivalence to
_posterior sampling_ (Osband et al., 2013), an important RL algorithm with
provable regret guarantees when the environments are _stationary_ , and Lin et
al. (2024) generalized the study to the setting of algorithm distillation as
in Laskin et al. (2023). However, their results cannot directly imply the no-
regret guarantee in our online learning setting, due to the fact that
posterior sampling can perform poorly under potentially _adversarial_ or _non-
stationary_ environments (Zimmert and Seldin, 2021; Liu et al., 2023b). In
contrast, we here establish the equivalence of the pre-trained LLM to the FTPL
algorithm (under different pre-training distribution specifications), with the
ability to handle arbitrary loss sequences, even though the LLMs are only
trained on a fixed distribution of texts (tasks).

##### Calibrating the degree of bounded rationality of actual LLMs.

To further validate our model and data distribution assumptions, we also
propose to _calibrate_ the parameter $\\{\eta_{t}\\}_{t\in[T-1]}$ in
Definition 2, the degree of bounded rationality, by estimating the parameters
of $\\{\eta_{t}\\}_{t\in[T-1]}$ using data from interacting with LLMs
(following the same protocol as before), with $P_{{noise}}$ being a standard
normal distribution (note that we do not need to calibrate $\eta_{0}$ by
Definition 2). Specifically, given $n$ episodes of the LLM agent’s behavior
$\\{({\ell}_{t}^{(j)},\pi_{t}^{(j)})_{t\in[T]}\\}_{j\in[n]}$, motivated by our
Lemma 1 and Theorem 1, we calibrate $\\{\eta_{t}\\}_{t\in[T-1]}$ by solving
the following problem

$\displaystyle\sigma^{\star}\in\arg\min_{\sigma>0}\quad\sum_{t\in[T-1]}\sum_{j\in[n]}\Big{\|}\pi_{t+1}^{(j)}-P^{\sigma\sqrt{t+1}}_{quantal}\Big{(}\cdot{\,\bigg{|}\,}{\ell}_{1:t}^{(j)}\Big{)}\Big{\|}_{1},\qquad\quad\eta_{t}^{\star}=\sigma^{\star}\sqrt{t+1},\quad\forall
t\in[T-1].$

We solve this single-variable optimization problem by grid search over
$[0,10]$. We then run the generalized quantal response model with the
calibrated $\\{\eta_{t}^{\star}\\}_{t\in[T-1]}$ on another _unseen test set_ ,
and compare it with the behavior of the actual LLM agents. We use all the
interaction data from Section 3.2 and split it in half for training and
testing. In Figure 8, we show the averaged regret for the LLM agent and the
calibrated generalized quantal response. It can be seen that calibrated
generalized quantal response can _very well capture_ the behavior of the LLM
agent for all problem instances in Section 3.2, justifying the applicability
of our hypothetical model and assumptions.

Figure 8:  (left) Comparison of GPT-4 with a calibrated agent on the test set,
where the calibrated quantal response can perfectly capture the behavior of
the GPT-4 agent. (mid, right) The calibrated agent on the less predictable and
adaptive loss sequences failed to make accurate predictions for the GPT-4
anymore.

We also use the same framework to understand the regrettable behaviors in
Section 3.4. This analysis uses all the data from Section 3.4. We first find
that such fitting procedures do not yield good predictions for LLMs on those
counter-examples. Therefore, we resort to a more expressive model by directly
fitting each $\eta_{t}$ as
$\eta_{t}^{\star}\in\arg\min_{\eta_{t}>0}\sum_{j\in[n]}\Big{\|}\pi_{t+1}^{(j)}-P^{\eta_{t}}_{quantal}\Big{(}\cdot{\,\bigg{|}\,}{\ell}_{1:t}^{(j)}\Big{)}\Big{\|}_{1}$
separately for each $t\in[T-1]$. Even under the expressive model, LLMs fail to
follow the generalized quantal response for the counter-examples with less
predictable or adaptive loss sequences, as Figure 8 shows the gap between
GPT-4 (dynamic) regret and the calibrated agent (dynamic) regret.

Finally, we acknowledge that for most existing pre-trained LLMs like GPT-4,
the canonical assumptions above, though may be further relaxed (c.f. Remark
4), may not hold in general. More importantly, the _supervision labels_ ,
i.e., the optimal action given $z$, may be sometimes imperfect or unavailable
during the dataset collection. Hence, it is completely possible to observe
regrettable behaviors (c.f. LABEL:{sec:yes_regret_example}). Motivated by
these caveats, we next propose a new training loss that is _unsupervised_ ,
and can promote no-regret behavior provably.

##  5 Provably Promoting No-Regret Behavior by an Unsupervised Loss

In light of the observations in Section 3, we ask the question:

_Is there a way to further enhance the no-regret property of LLM agents,
hopefully without (optimal) action labels?_

To address this question, we propose to train LLMs with a new _unsupervised
learning_ loss that naturally provides no-regret behaviors. This approach is
akin to the process of “instruction tuning” (Wei et al., 2021), which was
shown to have enhanced LLMs’ ability when learning from context, with both
theoretical (Ahn et al., 2023; Mahankali et al., 2023; Zhang et al., 2023a)
and empirical (Lu et al., 2023) evidence.

###  5.1 A New Unsupervised Training Loss: Regret-Loss

Intuitively, our new training loss is designed to enforce the trained LLM to
minimize the regret under an arbitrary sequence of loss vectors. Specifically,
we define the training loss as

$\displaystyle{\mathcal{L}(\theta)}:=\max_{\ell_{1},\dots,\ell_{T}}~{}~{}~{}\text{Regret}_{\text{LLM}_{\theta}}\left((\ell_{t})_{t\in[T]}\right)$
(2)

where $\|\ell_{t}\|_{\infty}\leq B$ for $t\in[T]$. As discussed in Kirschner
et al. (2023), directly minimizing the max regret can be computationally
challenging, except for superficially simple problems. Hence, in practice, one
may parameterize the LLM and resort to differentiable programming to solve it
approximately. However, Equation 2 is not necessarily differentiable with
respect to parameter $\theta$, if it does not satisfy the condition of
Danskin’s Theorem (Danskin, 1966); or even if it is differentiable (i.e., the
maximizer of $(\ell_{t})_{t\in[T]}$ is unique), computation of derivatives can
be challenging since we need to calculate
$\operatorname*{arg\,max}_{(\ell_{t})_{t\in[T]}}\text{Regret}_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]})$
while we have $\inf$ in the definition of regret. Therefore, we provide a
general framework so that we can approximate Equation 2 by the following
surrogate:

$\displaystyle\mathcal{L}(\theta,k,N):=\mathbb{E}\left[\frac{\sum_{j\in[N]}h(\text{Regret}_{\text{LLM}_{\theta}}((\ell_{t}^{(j)})_{t\in[T]}))f(\text{Regret}_{\text{LLM}_{\theta}}((\ell_{t}^{(j)})_{t\in[T]}),k)}{\sum_{j\in[N]}f(\text{Regret}_{\text{LLM}_{\theta}}((\ell_{t}^{(j)})_{t\in[T]}),k)}\right],$
(3)

where $k\in\mathbb{N}^{+}$, $N\in\mathbb{N}^{+}$,
$h:\mathbb{R}\to\mathbb{R}^{+}$ is a continuous function, with continuous
derivative $h^{\prime}$, and $f(\cdot,k):\mathbb{R}\to\mathbb{R}^{+}$ is a
continuous function for each $k\in\mathbb{N}^{+}$, satisfying
$\lim_{k\to\infty}\frac{f(R_{1},k)}{f(R_{2},k)}=\infty\cdot\mathbbm{1}(R_{1}>R_{2})+\mathbbm{1}(R_{1}=R_{2})$,
where we use the convention of $\infty\cdot 0=0$. These conditions on $h,f$
will be assumed throughout the paper. Examples of such an $f$ include
$f(x,k)=x^{k}$ and $\exp(kx)$. We will sample $N$ trajectories of loss
sequences $(\ell_{t}^{(j)})_{t\in[T],j\in[N]}$ from some continuous
probability distribution supported on $[-B,B]^{T\times N}$, and the
expectation in Equation 3 is thus taken with respect to this distribution.
Note that we do not have any statistical assumption on
$(\ell_{t}^{(j)})_{t\in[T],j\in[N]}$ (except being continuous and supported on
$[-B,B]^{T\times N}$), in contrast to those in Section 4 to _justify_ the no-
regret property of pre-trained LLMs.

In Section D.2, we prove that under certain regularity conditions of $f$ and
$h$, we have

$\lim_{N,k\to\infty}\mathcal{L}(\theta,k,N)=h\left(\max_{\ell_{1},\dots,\ell_{T}}\text{Regret}_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]})\right),$

as well as the uniform convergence of $\mathcal{L}(\theta,k,N)$:
$\lim_{N,k\to\infty}\sup_{\theta\in\Theta}\Big{|}h(\max_{\ell_{1},\dots,\ell_{T}}\text{Regret}_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]}))-\mathcal{L}(\theta,k,N)\Big{|}=0,$
where $\Theta$ is some compact set of the LLM parameter. Hence, one can expect
that minimizing the loss function in Equation 3 with large enough $k$ and $N$
may promote the trained LLM to have a small regret value. We will hereafter
refer to Equation 3 as the regret-loss. Similarly, we can also define dynamic-
regret-loss, and the results to be presented next can also generalize to this
case (c.f. Remark 5 in Section D.3).

###  5.2 Guarantees via Regret-Loss Minimization

We first establish a _statistical_ guarantee under general parameterizations
of $\text{LLM}_{\theta}$ that is Lipschitz with respect to $\theta$, including
the Transformer-based models as used in GPT-4 and most existing LLMs (see
Proposition 2 for an example with formal statement). This guarantee focuses on
their _generalization ability_ when trained to minimize the empirical regret
loss, which is defined as follows:

######  Definition 3 (Empirical loss function).

We define the empirical loss $\widehat{\mathcal{L}}$ computed with $N_{T}$
samples as follows:

$\displaystyle\widehat{\mathcal{L}}(\theta,k,N,N_{T}):=\frac{1}{N_{T}}\sum_{s=1}^{N_{T}}\left[\frac{\sum_{j\in[N]}h\left(\emph{Regret}_{\emph{LLM}_{\theta}}((\ell_{s,t}^{(j)})_{t\in[T]})\right)f\left(\emph{Regret}_{\emph{LLM}_{\theta}}((\ell_{s,t}^{(j)})_{t\in[T]}),k\right)}{\sum_{j\in[N]}f\left(\emph{Regret}_{\emph{LLM}_{\theta}}((\ell_{s,t}^{(j)})_{t\in[T]}),k\right)}\right]$
(4)

where $(\ell_{s,t}^{(j)})_{j\in[N],t\in[T]}$ denotes the $s$-th sample of
$(\ell_{t}^{(j)})_{j\in[N],t\in[T]}$ for estimating $\mathcal{L}(\theta,k,N)$.

We denote
$\widehat{\theta}_{k,N,N_{T}}\in\operatorname*{arg\,min}_{\theta\in\Theta}~{}\widehat{\mathcal{L}}(\theta,k,N,N_{T})$,
and present the generalization guarantee below.

######  Theorem 2.

_(Generalization gap)._ Suppose $\emph{LLM}_{\theta}$ is Lipschitz-continuous
with respect to the model parameter $\theta$, then for any $0<\epsilon<1/2$,
with probability at least $1-\epsilon$, we have

$\displaystyle\mathcal{L}\left(\widehat{\theta}_{k,N,N_{T}},k,N\right)$
$\displaystyle-\inf_{\theta\in\Theta}\mathcal{L}(\theta,k,N)\leq\widetilde{\mathcal{O}}\left(\sqrt{\frac{d_{\theta}+\log(1/\epsilon)}{N_{T}}}\right),$
(5)

for any $N$ and sufficiently large $k$, where $d_{\theta}$ is the dimension of
the parameter $\theta$.

Through a careful use of Berge’s Maximum Theorem (Berge, 1877), we prove that
the right-hand side of Equation 5 does _not_ depend on $k$ and $N$, which
allows us to take the limit of $\lim_{N\to\infty}\lim_{k\to\infty}$ without
affecting the generalization bound. Thanks to the uniform convergence of
$\mathcal{L}(\theta,k,N)$ (c.f. Section D.2), we further obtain the following
corollary on the regret guarantee:

######  Corollary 1.

_(Regret)._ Suppose§§§Note that these conditions on $h,f$ are in addition to
those specified after Equation 3. for any $k\in\mathbb{N}^{+}$, $h,f(\cdot,k)$
are non-decreasing, and $\log f$ is a supermodular function (i.e., $\log
f(R_{1},k_{1})-\log f(R_{1},k_{2})\geq\log f(R_{2},k_{1})-\log f(R_{2},k_{2})$
for $R_{1}\geq R_{2}$ and $k_{1}\geq k_{2}$). Then, with high probably, we
have

$\displaystyle
h\left(\lim_{N\to\infty}\lim_{k\to\infty}\max_{\|\ell_{t}\|_{\infty}\leq
B}\emph{Regret}_{\emph{LLM}_{\widehat{\theta}_{k,N,N_{T}}}}\left((\ell_{t})_{t\in[T]}\right)\right)\leq
h\left(\inf_{{\theta\in\Theta}}\max_{\|\ell_{t}\|_{\infty}\leq
B}\emph{Regret}_{\emph{LLM}_{{\theta}}}\left((\ell_{t})_{t\in[T]}\right)\right)+\widetilde{\mathcal{O}}\left(\sqrt{\frac{d_{\theta}}{{N_{T}}}}\right).$
(6)

######  Corollary 2.

_(Emerging behavior: Coarse correlated equilibrium)_. For a sufficiently large
$N_{T}$, if each agent in the matrix game plays according to
$\text{LLM}_{\widehat{\theta}_{k,N,N_{T}}}$, then the time-averaged policy for
each agent will constitute an approximate coarse correlated equilibrium of the
game.

Proofs of Theorem 2 and Corollary 1 are deferred to Section D.3, and Corollary
2 follows from the folklore result discussed in Remark 1. Therefore, if
additionally, the LLM parameterization (i.e., Transformers) can realize a no-
regret algorithm (for example, the single-layer self-attention model can
construct FTRL, as to be shown next in Section 5.3), then Corollary 1 means
that with a large enough number of samples $N_{T}$, the learned
$\text{LLM}_{\widehat{\theta}_{k,N,N_{T}}}$ becomes a _no-regret_ learner,
i.e.,
$\text{Regret}_{\text{LLM}_{\widehat{\theta}_{k,N,N_{T}}}}\left((\ell_{t})_{t\in[T]}\right)=o(T)$,
since the first term on the right-hand-side of Equation 6 would directly be
$o(T)$ under the choice of $h(x)=\max\\{0,x\\}$. For other choices of $h$, one
can use the inverse function of $h$, i.e., $h^{-1}$ (which always exists by
our requirement of $h$), to ensure
$\text{Regret}_{\text{LLM}_{\widehat{\theta}_{k,N,N_{T}}}}((\ell_{t})_{t\in[T]})$
is of order $o(T)$.

Despite the power and generality of the previous results, one cannot use an
_infinitely large_ $N$ and $k$ in practical training. Hence, in the next
subsection, we provide results when $N$ is finite, for the specific
parameterization of the LLMs using Transformers.

###  5.3 Minimizing Regret-Loss Can Automatically Produce Known Online
Learning Algorithms

We now study the setting of minimizing Equation 3 when $\text{LLM}_{\theta}$
is specifically parameterized by Transformers. As an initial step, we focus on
single-layer (linear) self-attention models, as in most recent theoretical
studies of Transformers (Ahn et al., 2023; Zhang et al., 2023a; Mahankali et
al., 2023), and the more practical setting with a finite $N=1$. Note that in
this case, the choice of $f$ (and thus $k$) is not relevant. Thus, throughout
this section, we drop superscript $(j)$ in Equation 3 for notational
convenience. We sample $\ell_{t}$ for $t\in[T]$ as realizations of some random
variable $Z$. Here, we assume $Z$ is symmetric about zero (i.e.,
$Z\overset{d}{=}-Z$), $\text{Var}(Z)=\Sigma$ is positive definite. We also
assume that the support of $Z$ has an interior such that it contains a ball
centered at $\boldsymbol{0}_{d}$.

Firstly, we consider the following structure of single-layer self-attention
model $g$ (see a formal introduction in Section A.1):

$\displaystyle
g(Z_{t};V,K,Q,v_{c},k_{c},q_{c}):=(V\ell_{1:t}+v_{c}\boldsymbol{1}_{t}^{\intercal})\texttt{Softmax}\left((K\ell_{1:t}+k_{c}\boldsymbol{1}_{t}^{\intercal})^{\intercal}\cdot(Qc+q_{c})\right),$
(7)

where $Z_{t}=(\ell_{1},\dots,\ell_{t},c)$, $\ell_{1:t}\in\mathbb{R}^{d\times
t}$ denotes a matrix with each column corresponding to each $\ell_{i}$, and
$V,K,Q\in\mathbb{R}^{d\times d}$ correspond to the value, key, and query
matrices, respectively, $v_{c},k_{c},q_{c}\in\mathbb{R}^{d}$ correspond to the
bias terms associated with $V,K,Q$, and $c\neq\boldsymbol{0}_{d}$ is a
constant vector. We then have the following result.

######  Theorem 3.

Consider the policy space $\Pi=B(0,R_{\Pi},\|\cdot\|)$ for some $R_{\Pi}>0$.
The configuration of a single-layer self-attention model in Equation 7
$(V,K,Q,v_{c},k_{c},q_{c})$ such that
$K^{\intercal}(Qc+q_{c})=v_{c}=\boldsymbol{0}_{d}$ and

$V=-R_{\Pi}\frac{T}{\sum_{t=1}^{T-1}1/t}\Sigma^{-1}\mathbb{E}\left[\bigg{\|}{\sum_{t=1}^{T}\ell_{t}}\bigg{\|}\ell_{1}\ell_{2}^{\intercal}\right]\Sigma^{-1}$

is a first-order stationary point of Equation 3 with $N=1$, $h(x)=x^{2}$.
Moreover, if $\Sigma$ is a diagonal matrix, then plugging this configuration
into Equation 7, and projecting the output with
$\texttt{Proj}_{\Pi,\|\cdot\|}$ would perform FTRL with an $L_{2}$-regularizer
for the loss vectors $(\ell_{t})_{t\in[T]}$.

In practical training, such stationary points of the loss may be attained by
first-order optimization algorithms of (stochastic) gradient descent, the
workhorse in machine learning. Moreover, we also consider the single-layer
_linear_ self-attention model as follows, for which we can strengthen the
results above from a stationary-point to an _optimal-solution_ argument:

$\displaystyle
g(Z_{t};V,K,Q,v_{c},k_{c},q_{c})=\sum_{i=1}^{t}(V\ell_{i}+v_{c})\left((K\ell_{i}+k_{c})^{\intercal}\cdot(Qc+q_{c})\right).$
(8)

######  Theorem 4.

Consider the policy space $\Pi=B(0,R_{\Pi},\|\cdot\|)$ for some $R_{\Pi}>0$.
The configuration of a single-layer linear self-attention model in Equation 8
$(V,K,Q,v_{c},k_{c},q_{c})$ such that
$K^{\intercal}(Qc+q_{c})=v_{c}=\boldsymbol{0}_{d}$ and
$V=-2R_{\Pi}\Sigma^{-1}\mathbb{E}\left(\|\sum_{t=1}^{T}\ell_{t}\|\ell_{1}\ell_{2}^{\intercal}\right)\Sigma^{-1}$
is a global optimal solution of Equation 3 with $N=1$, $h(x)=x^{2}$. Moreover,
every global optimal configuration of Equation 3 within the parameterization
class of Equation 8 has the same output function $g$. Additionally, if
$\Sigma$ is a diagonal matrix, then plugging any global optimal configuration
into Equation 8, and projecting the output with
$\texttt{Proj}_{\Pi,\|\cdot\|}$ would perform FTRL with an $L_{2}$-regularizer
for the loss vectors $(\ell_{t})_{t\in[T]}$.

Theorem 4 shows the capacity of self-attention Transformer models to realize
online learning algorithms, thanks to the regret-loss we proposed. In
particular, this can be achieved automatically by optimizing the new loss,
_without_ hard-coding the parameters of the Transformer.

The above results are for the case of FTRL with an $L_{2}$-regularizer, and it
is possible to consider FTRL with an _entropy regularizer_ , leading to the
well-known Hedge algorithm (Freund and Schapire, 1997) that is more compatible
with the simplex constraint on $\pi$ in the Experts Problem. We defer the
discussion of this case to Section D.7. Through these results, we can also
guarantee in the repeated game setting that approximate coarse correlated
equilibria would emerge in the long run, since each player will exhibit no-
regret behavior, using a similar argument as that for Corollary 2.

######  Remark 2.

The very recent studies by (Ahn et al., 2023; Zhang et al., 2023a; Mahankali
et al., 2023) have demonstrated that if
$Z_{t}=((x_{1},y_{1}),\dots,(x_{t},y_{t}),(x_{t+1},0))$ and the “instruction
tuning” loss (i.e., $\mathbb{E}[\|{\widehat{y}_{t+1}-y_{t+1}}\|^{2}]$) is
being minimized with a single-layer linear self-attention model, then a global
optimizer among single-layer linear self-attention models yields the output
$\widehat{y}_{n+1}=\eta\sum_{i=1}^{n}y_{i}x_{i}^{\intercal}x_{n+1}$. This
output can be interpreted as a _gradient descent_ algorithm, indicating that a
single-layer linear self-attention model implicitly performs gradient descent.
However, in the online learning setting where there are no $y$-labels, such an
implicit gradient descent update-rule is hard to define. Compared to the
previous studies, our global optimizer among single-layer linear self-
attention models is an _explicit_ and _online_ gradient descent update for
online learning. With a different loss (regret-loss v.s. instruction-tuning-
loss), the techniques to obtain the seemingly similar results are also
fundamentally different.

###  5.4 Experimental Results for Minimizing Regret-Loss

We now provide experimental results for minimizing our _regret-loss_ , and
evaluate in the following environments: 1) randomly-generated loss sequences
(Figure 9); 2) loss sequences with a predictable trend (Figure 10); 3)
repeated games (Figure 11); and 4) counterexamples for pre-trained LLMs to be
regrettable (Figure 7). Details of the training setup can be found in Section
D.8. We also provide an ablation study for the training of the loss Equation 3
in Section D.9.

##### Randomly generated loss sequences.

We use the same loss vectors as those in Section 3.2 for randomly generated
loss functions, and compare the results with that using GPT-4. The results
show that with regret-loss, both the trained single-layer self-attention model
and the trained Transformers with multi-layer self-attention structures can
achieve comparable regrets as FTRL and GPT-4. The results can be found in
Figure 9.

Figure 9: Regret performance for the randomly generated loss sequences that
are generated by Gaussian with truncation and uniform distribution. No-regret
behaviors of single-layer and multi-layer self-attention models are validated
by both of our frameworks (low $p$-values and $\widehat{\beta}_{0}<1$).

Figure 10: Regret performance for the randomly generated loss sequences that
are generated by linear-trend and sine-trend. No-regret behaviors of single-
layer and multi-layer self-attention models are validated by both of our
frameworks (low $p$-values and $\widehat{\beta}_{0}<1$).

##### Loss sequences with a predictable trend.

We investigate the case where the loss sequences have predictable trends such
as linear-trend or sine-trend. One might expect that the performance of the
trained Transformer would surpass the performance of traditional no-regret
learning algorithms such as FTRL, since they may not be an optimal algorithm
for the loss sequence with a predictable trend. We modify the training
distribution by changing the distribution of random variable $Z$ (which
generates the loss vectors $\ell_{t}$) to follow two kinds of trends: linear
and sine functions. The results, as illustrated in Figure 10, show that the
trained single-layer self-attention model and the trained Transformer with
multi-layer self-attention structures with regret-loss outperformed GPT-4 and
FTRL in terms of regret, when the loss sequence is a linear trend. Similarly,
Figure 10 shows that the trained Transformer with multi-layer self-attention
structures with regret-loss is comparable to GPT-4 and outperformed FTRL in
terms of regret, when the loss sequence is a sine-trend. Note that the
training dataset does not contain the sequence of losses. Nonetheless, by
focusing on the overall trend during training, we can attain performance that
is either superior to or on par with that of FTRL and GPT-4.

##### Repeated games.

We then investigate the case of multi-player repeated games. We study 2x2,
3x3x3, 3x3x3x3 games, where each entry of the payoff matrix is sampled
randomly from $\operatorname{Unif}([0,10])$. The results, as illustrated in
Figure 11, show that the trained single-layer self-attention model and the
trained Transformer with multi-layer self-attention structures with regret-
loss have a similar performance as that of FTRL. However, GPT-4 still
outperforms the trained single-layer self-attention model and the trained
Transformer with multi-layer self-attention structures in terms of regret.
Since for repeated games (in which the environment faced by the agent can be
less adversarial than that in the online setting), there might be a better
algorithm than FTRL (see e.g., Daskalakis et al. (2021)), while our self-
attention models have a similar structure as FTRL (Theorem 3 or Theorem 4).
Also, in practical training (with the empirical loss in Equation 4), we
possibly did not find the exact global minimum or stationary point of the
_expected_ loss in Equation 3. Hence, it is possible that GPT-4 may have lower
regret than our trained models with the regret-loss.

Figure 11: Regret performance for the game with two players, three players,
and four players general-sum games. No-regret behaviors of single-layer and
multi-layer self-attention models are validated by both of our frameworks (low
$p$-values and $\widehat{\beta}_{0}<1$).

##### Two scenarios that caused regrettable behaviors of GPT-4.

Finally, we investigate the cases that have caused GPT-4 to have regrettable
performance in Section 3.2. The results, which can be found in Figure 7, show
that both the trained single-layer self-attention model and the trained
Transformer with regret-loss can achieve comparable no-regret performance as
FTRL, and outperforms that of GPT-4. This validates that our new unsupervised
training loss can address the regrettable cases, as our theory in Sections 5.2
and 5.3 has predicted.

##  6 Concluding Remarks

In this paper, we studied the online decision-making and strategic behaviors
of LLMs quantitatively, through the metric of regret. We first examined and
validated the no-regret behavior of several representative pre-trained LLMs in
benchmark settings of online learning and games. As a consequence, (coarse
correlated) equilibrium can oftentimes emerge as the long-term outcome of
multiple LLMs playing repeated games. We then provide some theoretical
insights into the no-regret behavior, by connecting pre-trained LLMs to the
follow-the-perturbed-leader algorithm in online learning, under certain
assumptions. We also identified (simple) cases where pre-trained LLMs fail to
be no-regret, and thus proposed a new unsupervised training loss, _regret-
loss_ , to provably promote the no-regret behavior of Transformers without the
labels of (optimal) actions. We established both experimental and theoretical
evidence for the effectiveness of our regret-loss.

As a first attempt toward rigorously understanding the online and strategic
decision-making behaviors of LLMs through the metric of regret, our work has
opened up fruitful directions for future research:

  * •

There are more than one definitions of (dynamic-)regret in the online learning
literature, and we mainly focused on the so-called _external-regret_ in the
literature. It would be interesting to study the no-regret behavior of LLMs in
terms of other regret metrics, e.g., swap-regret (Blum and Mansour, 2007),
which may lead to stronger equilibrium notions in playing repeated games.

  * •

Our new regret-loss has exhibited promises in our experiments for training
modest-scale Transformers. We are currently generalizing it to training other
larger-scale models, such as Foundation Models, for decision-making.

  * •

No-regret behavior can sometimes lead to better outcomes in terms of social
efficiency (Blum et al., 2008; Roughgarden, 2015; Nekipelov et al., 2015). It
would thus be interesting to further validate the efficiency of no-regret LLM
agents in these scenarios, as well as identifying new prompts and training
losses for LLMs to promote the efficiency of the outcomes.

  * •

To evaluate the performance quantitatively, we focused on online learning and
games with _numeric valued_ payoffs. It would be interesting to connect our
no-regret-based and game-theoretic framework with existing multi-LLM
frameworks, e.g., debate, collaborative problem-solving, and human/social
behavior simulation, with potentially new notions of regret (defined in
different spaces) as performance metrics.

## Acknowledgement

The authors thank Dingwen Kong for discussing the truncation idea in proving
Lemma 8. Also, the authors thank Kristian Georgiev and Aleksander Madry for
the helpful feedback.

## References

  * Abernethy et al. (2014) Abernethy, J., Lee, C., Sinha, A. and Tewari, A. (2014).  Online linear optimization via smoothing.  In Conference on Learning Theory. PMLR.
  * Abernethy et al. (2015) Abernethy, J. D., Lee, C. and Tewari, A. (2015).  Fighting bandits with a new kind of smoothness.  Advances in Neural Information Processing Systems, 28.
  * Achiam et al. (2023) Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S. et al. (2023).  Gpt-4 technical report.  arXiv preprint arXiv:2303.08774.
  * Aher et al. (2023) Aher, G. V., Arriaga, R. I. and Kalai, A. T. (2023).  Using large language models to simulate multiple humans and replicate human subject studies.  In International Conference on Machine Learning. PMLR.
  * Ahn et al. (2023) Ahn, K., Cheng, X., Daneshmand, H. and Sra, S. (2023).  Transformers learn to implement preconditioned gradient descent for in-context learning.  Advanced in Neural Information Processing Systems.
  * Ahn et al. (2022) Ahn, M., Brohan, A., Brown, N., Chebotar, Y., Cortes, O., David, B., Finn, C., Fu, C., Gopalakrishnan, K., Hausman, K. et al. (2022).  Do as i can, not as i say: Grounding language in robotic affordances.  arXiv preprint arXiv:2204.01691.
  * Ahsanullah et al. (2013) Ahsanullah, M., Nevzorov, V. B. and Shakil, M. (2013).  An introduction to order statistics, vol. 8.  Springer.
  * Akata et al. (2023) Akata, E., Schulz, L., Coda-Forno, J., Oh, S. J., Bethge, M. and Schulz, E. (2023).  Playing repeated games with large language models.  arXiv preprint arXiv:2305.16867.
  * Akyürek et al. (2023) Akyürek, E., Schuurmans, D., Andreas, J., Ma, T. and Zhou, D. (2023).  What learning algorithm is in-context learning? investigations with linear models.  International Conference on Learning Representations.
  * Argyle et al. (2023) Argyle, L. P., Busby, E. C., Fulda, N., Gubler, J. R., Rytting, C. and Wingate, D. (2023).  Out of one, many: Using language models to simulate human samples.  Political Analysis, 31 337–351.
  * Arora et al. (2012) Arora, S., Hazan, E. and Kale, S. (2012).  The multiplicative weights update method: a meta-algorithm and applications.  Theory of computing, 8 121–164.
  * Auer et al. (2002) Auer, P., Cesa-Bianchi, N., Freund, Y. and Schapire, R. E. (2002).  The nonstochastic multiarmed bandit problem.  SIAM journal on computing, 32 48–77.
  * Bai et al. (2023) Bai, Y., Chen, F., Wang, H., Xiong, C. and Mei, S. (2023).  Transformers as statisticians: Provable in-context learning with in-context algorithm selection.  Advanced in Neural Information Processing Systems.
  * Bakhtin et al. (2022) Bakhtin, A., Brown, N., Dinan, E., Farina, G., Flaherty, C., Fried, D., Goff, A., Gray, J., Hu, H. et al. (2022).  Human-level play in the game of diplomacy by combining language models with strategic reasoning.  Science, 378 1067–1074.
  * Balseiro and Gur (2019) Balseiro, S. R. and Gur, Y. (2019).  Learning in repeated auctions with budgets: Regret minimization and equilibrium.  Management Science, 65 3952–3968.
  * Berge (1877) Berge, C. (1877).  Topological spaces: Including a treatment of multi-valued functions, vector spaces and convexity.  Oliver & Boyd.
  * Besbes et al. (2014) Besbes, O., Gur, Y. and Zeevi, A. (2014).  Stochastic multi-armed-bandit problem with non-stationary rewards.  Advances in neural information processing systems, 27.
  * Blum et al. (2008) Blum, A., Hajiaghayi, M., Ligett, K. and Roth, A. (2008).  Regret minimization and the price of total anarchy.  In Proceedings of the fortieth annual ACM symposium on Theory of computing.
  * Blum and Mansour (2007) Blum, A. and Mansour, Y. (2007).  From external to internal regret.  Journal of Machine Learning Research, 8.
  * Brookins and DeBacker (2023) Brookins, P. and DeBacker, J. M. (2023).  Playing games with GPT: What can we learn about a large language model from canonical strategic games?  Available at SSRN 4493398.
  * Brown et al. (2020) Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A. et al. (2020).  Language models are few-shot learners.  Advances in neural information processing systems, 33 1877–1901.
  * Bubeck et al. (2012) Bubeck, S., Cesa-Bianchi, N. et al. (2012).  Regret analysis of stochastic and nonstochastic multi-armed bandit problems.  Foundations and Trends® in Machine Learning, 5 1–122.
  * Bubeck et al. (2023) Bubeck, S., Chandrasekaran, V., Eldan, R., Gehrke, J., Horvitz, E., Kamar, E., Lee, P., Lee, Y. T., Li, Y., Lundberg, S. et al. (2023).  Sparks of artificial general intelligence: Early experiments with gpt-4.  arXiv preprint arXiv:2303.12712.
  * Camerer (2011) Camerer, C. F. (2011).  Behavioral game theory: Experiments in strategic interaction.  Princeton University Press.
  * Cesa-Bianchi et al. (1996) Cesa-Bianchi, N., Long, P. M. and Warmuth, M. K. (1996).  Worst-case quadratic loss bounds for prediction using linear functions and gradient descent.  IEEE Transactions on Neural Networks, 7 604–619.
  * Cesa-Bianchi and Lugosi (2006) Cesa-Bianchi, N. and Lugosi, G. (2006).  Prediction, Learning, and Games.  Cambridge University Press.
  * Chan et al. (2024) Chan, C.-M., Chen, W., Su, Y., Yu, J., Xue, W., Zhang, S., Fu, J. and Liu, Z. (2024).  Chateval: Towards better llm-based evaluators through multi-agent debate.  International Conference on Learning Representations.
  * Chen et al. (2024) Chen, W., Su, Y., Zuo, J., Yang, C., Yuan, C., Qian, C., Chan, C.-M., Qin, Y., Lu, Y., Xie, R. et al. (2024).  Agentverse: Facilitating multi-agent collaboration and exploring emergent behaviors in agents.  International Conference on Learning Representations.
  * Chen et al. (2023) Chen, Y., Liu, T. X., Shan, Y. and Zhong, S. (2023).  The emergence of economic rationality of gpt.  Proceedings of the National Academy of Sciences, 120 e2316205120.
  * Dai et al. (2023) Dai, D., Sun, Y., Dong, L., Hao, Y., Ma, S., Sui, Z. and Wei, F. (2023).  Why can GPT learn in-context? language models secretly perform gradient descent as meta-optimizers.  In Findings of the Association for Computational Linguistics: ACL 2023 (A. Rogers, J. Boyd-Graber and N. Okazaki, eds.). Association for Computational Linguistics, Toronto, Canada.
https://aclanthology.org/2023.findings-acl.247

  * Danskin (1966) Danskin, J. M. (1966).  The theory of max-min, with applications.  SIAM Journal on Applied Mathematics, 14 641–664.
  * Daskalakis et al. (2021) Daskalakis, C., Fishelson, M. and Golowich, N. (2021).  Near-optimal no-regret learning in general games.  Advances in Neural Information Processing Systems, 34 27604–27616.
  * Ding et al. (2022) Ding, J., Feng, Y. and Rong, Y. (2022).  Myopic quantal response policy: Thompson sampling meets behavioral economics.  arXiv preprint arXiv:2207.01028.
  * Driess et al. (2023) Driess, D., Xia, F., Sajjadi, M. S., Lynch, C., Chowdhery, A., Ichter, B., Wahid, A., Tompson, J., Vuong, Q., Yu, T. et al. (2023).  Palm-e: An embodied multimodal language model.  International Conference on Machine Learning.
  * Du et al. (2023) Du, Y., Li, S., Torralba, A., Tenenbaum, J. B. and Mordatch, I. (2023).  Improving factuality and reasoning in language models through multiagent debate.  arXiv preprint arXiv:2305.14325.
  * Engel et al. (2023) Engel, C., Grossmann, M. R. and Ockenfels, A. (2023).  Integrating machine behavior into human subject experiments: A user-friendly toolkit and illustrations.  Available at SSRN.
  * Erev and Roth (1998) Erev, I. and Roth, A. E. (1998).  Predicting how people play games: Reinforcement learning in experimental games with unique, mixed strategy equilibria.  American Economic Review 848–881.
  * Fan et al. (2023) Fan, C., Chen, J., Jin, Y. and He, H. (2023).  Can large language models serve as rational players in game theory? a systematic analysis.  arXiv preprint arXiv:2312.05488.
  * Freund and Schapire (1997) Freund, Y. and Schapire, R. E. (1997).  A decision-theoretic generalization of on-line learning and an application to boosting.  Journal of computer and system sciences, 55 119–139.
  * Fu et al. (2023) Fu, Y., Peng, H., Khot, T. and Lapata, M. (2023).  Improving language model negotiation with self-play and in-context learning from ai feedback.  arXiv preprint arXiv:2305.10142.
  * Fudenberg and Kreps (1993) Fudenberg, D. and Kreps, D. M. (1993).  Learning mixed equilibria.  Games and Economic Behavior, 5 320–367.
  * Fudenberg and Levine (1998) Fudenberg, D. and Levine, D. K. (1998).  The theory of learning in games, vol. 2.  MIT Press.
  * Gao and Pavel (2017) Gao, B. and Pavel, L. (2017).  On the properties of the softmax function with application in game theory and reinforcement learning.  arXiv preprint arXiv:1704.00805.
  * Garg et al. (2022) Garg, S., Tsipras, D., Liang, P. S. and Valiant, G. (2022).  What can transformers learn in-context? a case study of simple function classes.  Advances in Neural Information Processing Systems, 35 30583–30598.
  * Giannou et al. (2023) Giannou, A., Rajput, S., Sohn, J.-y., Lee, K., Lee, J. D. and Papailiopoulos, D. (2023).  Looped transformers as programmable computers.  International Conference on Machine Learning.
  * Hao et al. (2023) Hao, S., Gu, Y., Ma, H., Hong, J., Wang, Z., Wang, D. and Hu, Z. (2023).  Reasoning with language model is planning with world model.  In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing (H. Bouamor, J. Pino and K. Bali, eds.). Association for Computational Linguistics, Singapore.
https://aclanthology.org/2023.emnlp-main.507

  * Hazan (2016) Hazan, E. (2016).  Introduction to online convex optimization.  Foundations and Trends® in Optimization, 2 157–325.
  * Hofbauer and Sandholm (2002) Hofbauer, J. and Sandholm, W. H. (2002).  On the global convergence of stochastic fictitious play.  Econometrica, 70 2265–2294.
  * Hong et al. (2024) Hong, S., Zheng, X., Chen, J., Cheng, Y., Zhang, C., Wang, Z., Yau, S. K. S., Lin, Z., Zhou, L., Ran, C. et al. (2024).  Metagpt: Meta programming for multi-agent collaborative framework.  nternational Conference on Learning Representations.
  * Horton (2023) Horton, J. J. (2023).  Large language models as simulated economic agents: What can we learn from homo silicus?  Tech. rep., National Bureau of Economic Research.
  * Huang et al. (2022a) Huang, W., Abbeel, P., Pathak, D. and Mordatch, I. (2022a).  Language models as zero-shot planners: Extracting actionable knowledge for embodied agents.  In International Conference on Machine Learning. PMLR.
  * Huang et al. (2022b) Huang, W., Xia, F., Xiao, T., Chan, H., Liang, J., Florence, P., Zeng, A., Tompson, J., Mordatch, I., Chebotar, Y. et al. (2022b).  Inner monologue: Embodied reasoning through planning with language models.  arXiv preprint arXiv:2207.05608.
  * Jiang (2023) Jiang, H. (2023).  A latent space theory for emergent abilities in large language models.  arXiv preprint arXiv:2304.09960.
  * Kalai and Vempala (2005) Kalai, A. and Vempala, S. (2005).  Efficient algorithms for online decision problems.  Journal of Computer and System Sciences, 71 291–307.
  * Kasprzak et al. (2022) Kasprzak, M. J., Giordano, R. and Broderick, T. (2022).  How good is your gaussian approximation of the posterior? finite-sample computable error bounds for a variety of useful divergences.  arXiv preprint arXiv:2209.14992.
  * Kirschner et al. (2023) Kirschner, J., Bakhtiari, A., Chandak, K., Tkachuk, V. and Szepesvari, C. (2023).  Regret minimization via saddle point optimization.  In Thirty-seventh Conference on Neural Information Processing Systems.
  * Laskin et al. (2023) Laskin, M., Wang, L., Oh, J., Parisotto, E., Spencer, S., Steigerwald, R., Strouse, D., Hansen, S., Filos, A., Brooks, E. et al. (2023).  In-context reinforcement learning with algorithm distillation.  International Conference on Learning Representations.
  * Lattimore and Szepesvári (2020) Lattimore, T. and Szepesvári, C. (2020).  Bandit algorithms.  Cambridge University Press.
  * Lee et al. (2023) Lee, J. N., Xie, A., Pacchiano, A., Chandak, Y., Finn, C., Nachum, O. and Brunskill, E. (2023).  Supervised pretraining can learn in-context reinforcement learning.  Neural Information Processing Systems.
  * Li et al. (2023a) Li, C., Su, X., Fan, C., Han, H., Xue, C. and Zheng, C. (2023a).  Quantifying the impact of large language models on collective opinion dynamics.  arXiv preprint arXiv:2308.03313.
  * Li et al. (2023b) Li, G., Hammoud, H. A. A. K., Itani, H., Khizbullin, D. and Ghanem, B. (2023b).  Camel: Communicative agents for” mind” exploration of large scale language model society.  Neural Information Processing Systems.
  * Li et al. (2023c) Li, R., Patel, T. and Du, X. (2023c).  Prd: Peer rank and discussion improve large language model based evaluations.  arXiv preprint arXiv:2307.02762.
  * Li et al. (2023d) Li, S., Yang, J. and Zhao, K. (2023d).  Are you in a masquerade? exploring the behavior and impact of large language model driven social bots in online social networks.  arXiv preprint arXiv:2307.10337.
  * Li et al. (2023e) Li, Y., Ildiz, M. E., Papailiopoulos, D. and Oymak, S. (2023e).  Transformers as algorithms: Generalization and stability in in-context learning.  International Conference on Machine Learning.
  * Li and Tewari (2017) Li, Z. and Tewari, A. (2017).  Beyond the hazard rate: More perturbation algorithms for adversarial multi-armed bandits.  J. Mach. Learn. Res., 18 183–1.
  * Liang et al. (2023) Liang, T., He, Z., Jiao, W., Wang, X., Wang, Y., Wang, R., Yang, Y., Tu, Z. and Shi, S. (2023).  Encouraging divergent thinking in large language models through multi-agent debate.  arXiv preprint arXiv:2305.19118.
  * Lin et al. (2024) Lin, L., Bai, Y. and Mei, S. (2024).  Transformers as decision makers: Provable in-context reinforcement learning via supervised pretraining.  International Conference on Learning Representations.
  * Littlestone and Warmuth (1994) Littlestone, N. and Warmuth, M. K. (1994).  The weighted majority algorithm.  Information and computation, 108 212–261.
  * Liu et al. (2023a) Liu, H., Sferrazza, C. and Abbeel, P. (2023a).  Chain of hindsight aligns language models with feedback.  arXiv preprint arXiv:2302.02676, 3.
  * Liu et al. (2023b) Liu, Y., Van Roy, B. and Xu, K. (2023b).  Nonstationary bandit learning via predictive sampling.  In International Conference on Artificial Intelligence and Statistics. PMLR.
  * Liu et al. (2023c) Liu, Z., Hu, H., Zhang, S., Guo, H., Ke, S., Liu, B. and Wang, Z. (2023c).  Reason for future, act for now: A principled architecture for autonomous llm agents.  In NeurIPS 2023 Foundation Models for Decision Making Workshop.
  * Lorè and Heydari (2023) Lorè, N. and Heydari, B. (2023).  Strategic behavior of large language models: Game structure vs. contextual framing.  arXiv preprint arXiv:2309.05898.
  * Lu et al. (2023) Lu, S., Bigoulaeva, I., Sachdeva, R., Madabushi, H. T. and Gurevych, I. (2023).  Are emergent abilities in large language models just in-context learning?  arXiv preprint arXiv:2309.01809.
  * Mahankali et al. (2023) Mahankali, A., Hashimoto, T. B. and Ma, T. (2023).  One step of gradient descent is provably the optimal in-context learner with one layer of linear self-attention.  International Conference on Learning Representations.
  * Mao et al. (2020) Mao, W., Zhang, K., Zhu, R., Simchi-Levi, D. and Başar, T. (2020).  Model-free non-stationary RL: Near-optimal regret and applications in multi-agent RL and inventory control.  arXiv preprint arXiv:2010.03161.
  * McFadden (1976) McFadden, D. L. (1976).  Quantal choice analaysis: A survey.  Annals of Economic and Social Measurement, Volume 5, number 4 363–390.
  * McKelvey and Palfrey (1995) McKelvey, R. D. and Palfrey, T. R. (1995).  Quantal response equilibria for normal form games.  Games and economic behavior, 10 6–38.
  * Min et al. (2022) Min, S., Lyu, X., Holtzman, A., Artetxe, M., Lewis, M., Hajishirzi, H. and Zettlemoyer, L. (2022).  Rethinking the role of demonstrations: What makes in-context learning work?  In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing (Y. Goldberg, Z. Kozareva and Y. Zhang, eds.). Association for Computational Linguistics, Abu Dhabi, United Arab Emirates.
https://aclanthology.org/2022.emnlp-main.759

  * Mukobi et al. (2023) Mukobi, G., Erlebach, H., Lauffer, N., Hammond, L., Chan, A. and Clifton, J. (2023).  Welfare diplomacy: Benchmarking language model cooperation.  arXiv preprint arXiv:2310.08901.
  * Nekipelov et al. (2015) Nekipelov, D., Syrgkanis, V. and Tardos, E. (2015).  Econometrics for learning agents.  In ACM Conference on Economics and Computation.
  * Openai (2023) Openai (2023).  Gpt-4 technical report.
  * Osband et al. (2013) Osband, I., Russo, D. and Van Roy, B. (2013).  (more) efficient reinforcement learning via posterior sampling.  Advances in Neural Information Processing Systems, 26.
  * Park et al. (2023) Park, J. S., O’Brien, J., Cai, C. J., Morris, M. R., Liang, P. and Bernstein, M. S. (2023).  Generative agents: Interactive simulacra of human behavior.  In Proceedings of the 36th Annual ACM Symposium on User Interface Software and Technology. UIST ’23, Association for Computing Machinery, New York, NY, USA.
https://doi.org/10.1145/3586183.3606763

  * Park et al. (2022) Park, J. S., Popowski, L., Cai, C., Morris, M. R., Liang, P. and Bernstein, M. S. (2022).  Social simulacra: Creating populated prototypes for social computing systems.  In Proceedings of the 35th Annual ACM Symposium on User Interface Software and Technology.
  * Qian et al. (2023) Qian, C., Cong, X., Yang, C., Chen, W., Su, Y., Xu, J., Liu, Z. and Sun, M. (2023).  Communicative agents for software development.  arXiv preprint arXiv:2307.07924.
  * Reed et al. (2022) Reed, S., Zolna, K., Parisotto, E., Colmenarejo, S. G., Novikov, A., Barth-maron, G., Giménez, M., Sulsky, Y., Kay, J., Springenberg, J. T., Eccles, T., Bruce, J., Razavi, A., Edwards, A., Heess, N., Chen, Y., Hadsell, R., Vinyals, O., Bordbar, M. and de Freitas, N. (2022).  A generalist agent.  Transactions on Machine Learning Research.  Featured Certification, Outstanding Certification.
https://openreview.net/forum?id=1ikK0kHjvj

  * Robinson and Goforth (2005) Robinson, D. and Goforth, D. (2005).  The topology of the 2x2 games: a new periodic table, vol. 3.  Psychology Press.
  * Roughgarden (2015) Roughgarden, T. (2015).  Intrinsic robustness of the price of anarchy.  Journal of the ACM (JACM), 62 1–42.
  * Roughgarden et al. (2017) Roughgarden, T., Syrgkanis, V. and Tardos, E. (2017).  The price of anarchy in auctions.  Journal of Artificial Intelligence Research, 59 59–101.
  * Schick et al. (2023) Schick, T., Dwivedi-Yu, J., Jiang, Z., Petroni, F., Lewis, P., Izacard, G., You, Q., Nalmpantis, C., Grave, E. and Riedel, S. (2023).  Peer: A collaborative language model.  International Conference on Learning Representations.
  * Shalev-Shwartz (2007) Shalev-Shwartz, S. (2007).  Online learning: Theory, algorithms, and applications.  Hebrew University.
  * Shalev-Shwartz (2012) Shalev-Shwartz, S. (2012).  Online learning and online convex optimization.  Foundations and Trends® in Machine Learning, 4 107–194.
  * Shalev-Shwartz and Singer (2007) Shalev-Shwartz, S. and Singer, Y. (2007).  A primal-dual perspective of online learning algorithms.  Machine Learning, 69 115–142.
  * Shen et al. (2023) Shen, Y., Song, K., Tan, X., Li, D., Lu, W. and Zhuang, Y. (2023).  Hugginggpt: Solving AI tasks with chatgpt and its friends in huggingface.  Neural Information Processing Systems.
  * Shinn et al. (2023) Shinn, N., Cassano, F., Gopinath, A., Narasimhan, K. R. and Yao, S. (2023).  Reflexion: Language agents with verbal reinforcement learning.  In Thirty-seventh Conference on Neural Information Processing Systems.
  * Significant Gravitas (2023) Significant Gravitas (2023).  Autogpt.
https://github.com/Significant-Gravitas/AutoGPT

  * Srivastava et al. (2023) Srivastava, A., Rastogi, A., Rao, A., Shoeb, A. A. M., Abid, A., Fisch, A., Brown, A. R., Santoro, A., Gupta, A., Garriga-Alonso, A. et al. (2023).  Beyond the imitation game: Quantifying and extrapolating the capabilities of language models.  Transactions on Machine Learning Research.
  * Swan et al. (2023) Swan, M., Kido, T., Roland, E. and Santos, R. P. d. (2023).  Math agents: Computational infrastructure, mathematical embedding, and genomics.  arXiv preprint arXiv:2307.02502.
  * Tsai et al. (2023) Tsai, C. F., Zhou, X., Liu, S. S., Li, J., Yu, M. and Mei, H. (2023).  Can large language models play text games well? current state-of-the-art and open questions.  arXiv preprint arXiv:2304.02868.
  * Valmeekam et al. (2023) Valmeekam, K., Marquez, M., Olmo, A., Sreedharan, S. and Kambhampati, S. (2023).  Planbench: An extensible benchmark for evaluating large language models on planning and reasoning about change.  In Thirty-seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track.
  * Van der Vaart (2000) Van der Vaart, A. W. (2000).  Asymptotic statistics, vol. 3.  Cambridge university press.
  * Vaswani et al. (2017) Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł. and Polosukhin, I. (2017).  Attention is all you need.  Advances in neural information processing systems, 30.
  * Von Oswald et al. (2023) Von Oswald, J., Niklasson, E., Randazzo, E., Sacramento, J., Mordvintsev, A., Zhmoginov, A. and Vladymyrov, M. (2023).  Transformers learn in-context by gradient descent.  In International Conference on Machine Learning. PMLR.
  * Wainwright (2019) Wainwright, M. J. (2019).  High-dimensional statistics: A non-asymptotic viewpoint, vol. 48.  Cambridge university press.
  * Wang et al. (2023a) Wang, G., Xie, Y., Jiang, Y., Mandlekar, A., Xiao, C., Zhu, Y., Fan, L. and Anandkumar, A. (2023a).  Voyager: An open-ended embodied agent with large language models.  arXiv preprint arXiv:2305.16291.
  * Wang et al. (2023b) Wang, X., Zhu, W. and Wang, W. Y. (2023b).  Large language models are implicitly topic models: Explaining and finding good demonstrations for in-context learning.  International Conference on Machine Learning 2023 Workshop ES-FoMO.
  * Wang et al. (2023c) Wang, Z., Cai, S., Liu, A., Ma, X. and Liang, Y. (2023c).  Describe, explain, plan and select: Interactive planning with large language models enables open-world multi-task agents.  Advances in neural information processing systems.
  * Wei and Luo (2021) Wei, C.-Y. and Luo, H. (2021).  Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach.  In Conference on learning theory. PMLR.
  * Wei et al. (2021) Wei, J., Bosma, M., Zhao, V. Y., Guu, K., Yu, A. W., Lester, B., Du, N., Dai, A. M. and Le, Q. V. (2021).  Finetuned language models are zero-shot learners.  International Conference on Learning Representations.
  * Wei et al. (2022a) Wei, J., Tay, Y., Bommasani, R., Raffel, C., Zoph, B., Borgeaud, S., Yogatama, D., Bosma, M., Zhou, D., Metzler, D. et al. (2022a).  Emergent abilities of large language models.  Transactions on Machine Learning Research.
  * Wei et al. (2022b) Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., Le, Q. V., Zhou, D. et al. (2022b).  Chain-of-thought prompting elicits reasoning in large language models.  Advances in Neural Information Processing Systems, 35 24824–24837.
  * Wu et al. (2023) Wu, Q., Bansal, G., Zhang, J., Wu, Y., Zhang, S., Zhu, E., Li, B., Jiang, L., Zhang, X. and Wang, C. (2023).  Autogen: Enabling next-gen llm applications via multi-agent conversation framework.  arXiv preprint arXiv:2308.08155.
  * Xie et al. (2022) Xie, S. M., Raghunathan, A., Liang, P. and Ma, T. (2022).  An explanation of in-context learning as implicit bayesian inference.  International Conference on Learning Representations.
  * Xiong et al. (2023) Xiong, K., Ding, X., Cao, Y., Liu, T. and Qin, B. (2023).  Examining inter-consistency of large language models collaboration: An in-depth analysis via debate.  In Findings of the Association for Computational Linguistics: EMNLP 2023 (H. Bouamor, J. Pino and K. Bali, eds.). Association for Computational Linguistics, Singapore.
https://aclanthology.org/2023.findings-emnlp.508

  * Xu et al. (2023a) Xu, Y., Wang, S., Li, P., Luo, F., Wang, X., Liu, W. and Liu, Y. (2023a).  Exploring large language models for communication games: An empirical study on werewolf.  arXiv preprint arXiv:2309.04658.
  * Xu et al. (2023b) Xu, Z., Yu, C., Fang, F., Wang, Y. and Wu, Y. (2023b).  Language agents with reinforcement learning for strategic play in the werewolf game.  arXiv preprint arXiv:2310.18940.
  * Yao et al. (2023a) Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T. L., Cao, Y. and Narasimhan, K. (2023a).  Tree of thoughts: Deliberate problem solving with large language models.  Advances in Neural Information Processing Systems.
  * Yao et al. (2023b) Yao, S., Zhao, J., Yu, D., Du, N., Shafran, I., Narasimhan, K. and Cao, Y. (2023b).  React: Synergizing reasoning and acting in language models.  International Conference on Learning Representations.
  * Young (2004) Young, H. P. (2004).  Strategic learning and its limits.  OUP Oxford.
  * Zhang et al. (2024) Zhang, H., Du, W., Shan, J., Zhou, Q., Du, Y., Tenenbaum, J. B., Shu, T. and Gan, C. (2024).  Building cooperative embodied agents modularly with large language models.  International Conference on Learning Representations.
  * Zhang et al. (2023a) Zhang, R., Frei, S. and Bartlett, P. L. (2023a).  Trained transformers learn linear models in-context.  arXiv preprint arXiv:2306.09927.
  * Zhang et al. (2023b) Zhang, Y., Zhang, F., Yang, Z. and Wang, Z. (2023b).  What and how does in-context learning learn? bayesian model averaging, parameterization, and generalization.  arXiv preprint arXiv:2305.19420.
  * Zhao et al. (2023) Zhao, Q., Wang, J., Zhang, Y., Jin, Y., Zhu, K., Chen, H. and Xie, X. (2023).  Competeai: Understanding the competition behaviors in large language model-based agents.  arXiv preprint arXiv:2310.17512.
  * Zimmert and Seldin (2021) Zimmert, J. and Seldin, Y. (2021).  Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits.  The Journal of Machine Learning Research, 22 1310–1358.
  * Zinkevich (2003) Zinkevich, M. (2003).  Online convex programming and generalized infinitesimal gradient ascent.  In International Conference on Machine Learning.

Supplementary Materials for

“Do LLM Agents Have Regret? A Case Study in Online Learning and Games”

###### Contents

  1. 1 Introduction
    1. 1.1 Related Work
  2. 2 Preliminaries
    1. 2.1 Online Learning & Games
    2. 2.2 Performance Metric: Regret
  3. 3 Do Pre-Trained LLMs Have Regret? Experimental Validation
    1. 3.1 Framework for No-Regret Behavior Validation
    2. 3.2 Results: Online Learning
    3. 3.3 Results: Multi-Player Repeated Games
    4. 3.4 Pre-Trained LLM Agents May Still Have Regret
  4. 4 Why Are Pre-Trained LLMs (No-)Regret? A Hypothetical Model and Some Theoretical Insights
    1. 4.1 Pre-Trained LLMs Have Similar Regret as Humans (Who Generate Data)
    2. 4.2 A Human Decision-Making Model: Quantal Response
    3. 4.3 Case Study: Pre-Training under Canonical Data Distribution
  5. 5 Provably Promoting No-Regret Behavior by an Unsupervised Loss
    1. 5.1 A New Unsupervised Training Loss: Regret-Loss
    2. 5.2 Guarantees via Regret-Loss Minimization
    3. 5.3 Minimizing Regret-Loss Can Automatically Produce Known Online Learning Algorithms
    4. 5.4 Experimental Results for Minimizing Regret-Loss
  6. 6 Concluding Remarks
  7. A Deferred Background
    1. A.1 Additional Definitions for Appendix
    2. A.2 In-Context Learning
    3. A.3 Online Learning Algorithms
    4. A.4 Why Focusing on Linear Loss Function?
    5. A.5 Six Representative General-Sum Games
  8. B Deferred Results and Proofs in Section 3
    1. B.1 Ablation Study on Prompts
    2. B.2 Proof for Proposition 1
    3. B.3 Results of GPT-4 Turbo
    4. B.4 LLM Agents’ Explanation on Their Output Policies
  9. C Deferred Results and Proofs in Section 4
    1. C.1 Deferred Proof of Observation 1
    2. C.2 Deferred Proof of Lemma 1
    3. C.3 Relationship between FTPL and Definition 2
    4. C.4 Deferred Proof of Theorem 1
    5. C.5 Extending Theorem 1 with Relaxed Assumptions
      1. C.5.1 Relaxation under More General Data Distributions
      2. C.5.2 Relaxation under Decision-Irrelevant Pre-Training Data
  10. D Deferred Results and Proofs in Section 5
    1. D.1 Basic Lemmas
    2. D.2 Deferred Proof for the Arguments in Section 5.1
    3. D.3 Deferred Proofs of Theorem 2 and Corollary 1
    4. D.4 Deferred Proof of Theorem 3
    5. D.5 Deferred Proof of Theorem 4
    6. D.6 Empirical Validation of Theorem 3 and Theorem 4
      1. D.6.1 Empirical Validation of Theorem 3
      2. D.6.2 Empirical Validation of Theorem 4
    7. D.7 Discussions on the Production of FTRL with Entropy Regularization
      1. D.7.1 Numerical Analysis of Step 2 and Step 4
      2. D.7.2 Empirical Validation
    8. D.8 Training Details of Section 5.4
    9. D.9 Ablation Study on Training Equation 3

##  Appendix A Deferred Background

###  A.1 Additional Definitions for Appendix

##### (Linear) Self-attention.

One key component in Transformers (Vaswani et al., 2017), the backbone of
modern language models, is the _(self-)attention_ mechanism. For simplicity,
we here focus on introducing the _single-layer_ self-attention architecture.
The mechanism takes a sequence of vectors
$Z=[z_{1},\dots,z_{t}]\in\mathbb{R}^{d\times t}$ as input, and outputs some
sequence of $[\widehat{z}_{1},\dots,\widehat{z}_{t}]\in\mathbb{R}^{d\times
t}$. For each $i\in[t]$ where $i>1$, the output is generated by
$\widehat{z}_{i}=(Vz_{1:{i-1}})\sigma((Kz_{1:i-1})^{\intercal}(Qz_{i}))$,
where $z_{1:{i-1}}$ denotes the $1$ to $i-1$ columns of $Z$, $\sigma$ is
either the Softmax or ReLU activation function, and for the initial output,
$\widehat{z}_{1}=\boldsymbol{0}_{d}$. Here, $V,Q,K\in\mathbb{R}^{d\times d}$
are referred to as the _Value_ , _Query_ , and _Key_ matrices, respectively.
Following the theoretical framework in Von Oswald et al. (2023); Mahankali et
al. (2023), we exclude the attention score for a token $z_{i}$ in relation to
itself. For theoretical analysis, we also consider the _linear_ self-attention
model, where
$\widehat{z}_{i}=(Vz_{1:{i-1}})((Kz_{1:i-1})^{\intercal}(Qz_{i}))$. We write
this (linear) self-attention layer’s output as $\texttt{(L)SA}_{(V,Q,K)}(Z)$.
We define an $M$-head self-attention layer with
$\theta=\\{(V_{m},Q_{m},K_{m})\\}_{m\in[M]}$ as
$\texttt{M-(L)SA}_{\theta}(Z):=\sum_{m=1}^{M}\texttt{(L)SA}_{(V_{m},Q_{m},K_{m})}(Z)$.
We define $\|\cdot\|_{\texttt{M-(L)SA}}$ as
$\|\theta\|_{\texttt{M-(L)SA}}:=\max_{m\in[M]}\left\\{\|Q_{m}\|_{\texttt{op}},\|K_{m}\|_{\texttt{op}}\right\\}+\sum_{m=1}^{M}\|V_{m}\|_{\texttt{op}}$.

##### Transformers.

For a multi-layer perceptron (MLP) layer, it takes
$Z=[z_{1},\dots,z_{t}]\in\mathbb{R}^{d\times t}$ as input, with parameter
$\theta=(W_{1},W_{2})\in\mathbb{R}^{d^{\prime}\times
d}\times\mathbb{R}^{d\times d^{\prime}}$ such that for each $i\in[t]$, the
output is $\widehat{z_{i}}:=W_{2}\sigma(W_{1}z_{i})$ where $\sigma$ is either
Softmax or ReLU. We write the output of an MLP layer with parameter $\theta$
as $\texttt{MLP}_{\theta}(Z)$. Defining $\|\cdot\|_{\texttt{MLP}}$ as
$\|\theta\|_{\texttt{MLP}}:=\|W_{1}\|_{\texttt{op}}+\|W_{2}\|_{\texttt{op}}$
and $\texttt{ResNet}(f,Z):=Z+f(Z)$, we can define an $L$-layer Transformer
with parameter $\theta=(\theta^{(lm)},\theta^{(la)})_{l\in[L]}$ as

$\displaystyle\texttt{TF}_{\theta}(Z):=Z^{(L)},$

where the output $Z^{(L)}$ is defined iteratively from
$Z^{(0)}=\texttt{clip}_{R}(Z):=\min(-R,\max(R,Z))$ and

$\displaystyle
Z^{(l)}=\texttt{clip}_{R}\left(\texttt{ResNet}\left(\texttt{MLP}_{\theta^{(la)}},\texttt{ResNet}\left(\texttt{M-(L)SA}_{\theta^{(lm)}},Z^{(l-1)}\right)\right)\right),$

for some $R>0$. We define a class of Transformers with certain parameters as
$\Theta_{d,L,M,d^{\prime},B_{\texttt{TF}}}:=\\{\theta=(\theta^{(lm)},\theta^{(la)})_{l\in[L],m\in[M]}:\|\theta\|_{\texttt{TF}}\leq
B_{\texttt{TF}}\\}$, where $M$ is the number of heads of self-attention,

$\displaystyle\|\theta\|_{\texttt{TF}}:=\max_{l\in[L]}\left\\{\|\theta^{(la)}\|_{\texttt{M-(L)SA}}+\|\theta^{(lm)}\|_{\texttt{MLP}}\right\\},$
(9)

and $B_{\texttt{TF}}>0$ is some constant. When it is clear from the context,
we may omit the subscripts and write it as $\Theta$ for simplicity. We assume
$R$ to be sufficiently large such that clip does not take effect on any of our
approximation results.

###  A.2 In-Context Learning

In-context learning is an emergent behavior of LLMs (Brown et al., 2020),
which means that these models can adapt and learn from a limited number of
examples provided within their immediate input context. In in-context
learning, the prompt is usually constituted by a length of $T$ in-context
(independent) examples $(x_{t},y_{t})_{t\in[T]}$ and $(T+1)$-th input
$x_{T+1}$, so the $\text{LLM}((z_{t})_{t\in[T]},x_{T+1})$ provides the
inference of $y_{T+1}$, where $z_{t}=(x_{t},y_{t})$.

###  A.3 Online Learning Algorithms

##### Follow-the-regularized-leader (FTRL).

The Follow-the-Regularized-Leader (FTRL) algorithm (Shalev-Shwartz, 2007) is
an iterative method that updates policy based on the observed data and a
regularization term. The idea is to choose the next policy that minimizes the
sum of the past losses and a regularization term.

Mathematically, given a sequence of loss vectors
${\ell}_{1},{\ell}_{2},\dots,{\ell}_{t}$, the FTRL algorithm updates the
policy $\pi$ at each time step $t$ as follows:

$\pi_{t+1}=\arg\min_{\pi\in\Pi}\left(\sum_{i=1}^{t}\langle{\ell}_{i},\pi\rangle+R(\pi)\right),$

where $R(\pi)$ is a regularization term. The regularization term $R(\pi)$ is
introduced to prevent overfitting and can be any function that penalizes the
complexity of the model. A function $R(\pi)$ is said to be $\lambda$-strongly
convex with respect to a norm $\|\cdot\|$ if for all $\pi,\pi^{\prime}\in\Pi$:

$R(\pi)\geq R(\pi^{\prime})+\langle\nabla
R(\pi^{\prime}),\pi-\pi^{\prime}\rangle+\frac{\lambda}{2}\|\pi-\pi^{\prime}\|_{2}^{2}.$

A key property that ensures the convergence and stability of the FTRL
algorithm is the strong convexity of the regularization term $R(\pi)$. Strong
convexity of $R(\pi)$ ensures that the optimization problem in FTRL has a
unique solution. The FTRL algorithm’s flexibility allows it to encompass a
wide range of online learning algorithms, from gradient-based methods like
online gradient descent to decision-making algorithms like Hedge (Freund and
Schapire, 1997).

##### Connection to online gradient descent (OGD).

The Online Gradient Descent (OGD) (Cesa-Bianchi et al., 1996) algorithm is a
special case of the FTRL algorithm when the regularization term is the
$L_{2}$-norm square, i.e., $R(\pi)=\frac{1}{2}\|\pi\|_{2}^{2}$ and
$\Pi=\mathbb{R}^{d}$. In OGD, at each time step $t$, the policy $\pi$ is
updated using the gradient of the loss function:

$\pi_{t+1}=\pi_{t}-{\ell}_{t}.$

Therefore, the connection between FTRL and OGD can be seen by observing that
the update rule for FTRL with $L_{2}$ regularization can be derived from the
OGD update rule.

##### Connection to the Hedge algorithm.

The Hedge algorithm (Freund and Schapire, 1997) (also referred to as the
Multiplicative Weight Update algorithm (Arora et al., 2012)) is an online
learning algorithm designed for problems where the learner has to choose from
a set of actions (denoted as $\mathcal{A}$) at each time step and suffers a
loss based on the chosen action. The FTRL framework can be used to derive the
Hedge algorithm by considering an entropy regularization term. Specifically,
the regularization term is the negative entropy
$R(\pi)=\sum_{j\in[d]}\pi_{j}\log\pi_{j}$ (where $d$ is the dimension of
policy $\pi$), then the FTRL update rule yields the Hedge algorithm as

$\displaystyle\pi_{(t+1)j}=\pi_{tj}\frac{\exp(-{\ell}_{tj}\pi_{tj})}{\sum_{i\in[d]}\exp(-{\ell}_{ti}\pi_{ti})}$

for $j\in[d]$.

##### Follow-the-perturbed-leader (FTPL).

Given a sequence of loss vectors ${\ell}_{1},{\ell}_{2},\dots,{\ell}_{t-1}$,
the Follow-the-Perturbed-Leader algorithm (Kalai and Vempala, 2005) updates
the policy $\pi$ at each time step $t$ by incorporating a perturbation vector
$\epsilon_{t}$. This perturbation is _sampled_ from a pre-defined
distribution. The policy $\pi_{t}$ for the next time step is chosen by solving
the following optimization problem:

$\displaystyle\pi_{t}=\mathbb{E}\left[\arg\min_{\pi\in\Pi}\langle\epsilon_{t},\pi\rangle+\sum_{i=1}^{t-1}\langle{\ell}_{i},\pi\rangle\right].$
(10)

Here $\epsilon_{t}$ introduces randomness to the decision-making.

##### Relationship between FTRL and FTPL.

The FTRL and FTPL algorithms are deeply related. For example, FTPL with
perturbations of Gumbel distribution and FTRL with Entropy Regularization
(i.e., Hedge) are equivalent. In general, for the FTPL algorithm with any
perturbation distribution, one can always find an FTRL algorithm with a
particular regularization such that their update rule is equivalent. However,
this relationship does not hold vice versa. For example, Hofbauer and Sandholm
(2002) shows that for FTRL with log barrier regularization, there does not
exist an equivalent perturbation distribution for FTPL.

##### Restarting techniques for non-stationary online learning.

For non-stationary online learning problems, one common technique is
_restarting_ : one restarts the standard online learning algorithm
periodically (Besbes et al., 2014) (see also e.g., Wei and Luo (2021); Mao et
al. (2020)). After each restarting operation, the algorithm will ignore the
previous history and execute as if it is the beginning of the interaction with
the environment. Since the variation of the loss sequences is bounded, loss
sequences between two consecutive restarting operations can be regarded as
being _almost stationary_ , which makes achieving an overall sublinear dynamic
regret guarantee possible.

###  A.4 Why Focusing on Linear Loss Function?

We note that focusing on the linear loss function
$f_{t}(\pi):=\langle{\ell}_{t},\pi\rangle$ does not lose much of generality.