Do LLM Agents  Have Regret? A Case Study in Online Learning and Games
Authors: Chanwoo Park
Xiangyu Liu
Asuman E. Ozdaglar
Kaiqing Zhang
Venue: ICLR 2025 Poster (2025)
Keywords: LLM agents
online learning
repeated games
Primary area: foundation or frontier models, including LLMs

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-stochastic 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 further 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. Finally, we establish the statistical guarantee of generalization bound for regret-loss minimization, and more importantly, the optimization guarantee that minimizing such a loss may automatically lead to known no-regret learning algorithms, when single-layer self-attention models are used. Our further experiments demonstrate the effectiveness of our regret-loss, especially in addressing the above “regrettable” cases.

Published as a conference paper at ICLR 2025
Do LLM AGENTS HAVE REGRET? A CASE STUDY IN ONLINE LEARNING AND GAMES
Chanwoo Park*1, Xiangyu Liu"?, Asuman Ozdaglar', Kaiqing Zhang 1 MIT, University of Maryland, College Park
ABSTRACT
Large language models (LLMs) have been increasingly employed for (interac- tive) 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, typical scenario in real-world LLM--geet applications. To better understand the limits of LLM agents in these interactive environments, we propose to study their interactions in benchmark decision-making settings of online learning and game theory, through the performance metric of regret. We first empirically study the no-regret behav- iors of LLMs in canonical non-stochastic online learning problems, as well as the emergence of equilibria when multiple of them interact through playing repeated games. We then provide some theoretical insights into the sublinear regret growth the cases we observed, under certain assumptions on (supervised) pre-training and the data generation model. Notably, we also identify (simple) cases where advanced LLMs such as GPT-4 fail to be no-regret. To further promote the no- regret behaviors, propose novel unsupervised training loss, the regret-loss, which, in contrast to the supervised pre- trainini loss, does not require the labels of (optimal) actions. Finally, we establish the statistical guarantee of generaliza- tion bound for regret-loss minimization, and more importantly, the optimization guarantee that minimizing such loss can lead known no-regret learning algo- rithms, when single-layer self-attention models are used, Our further experiments demonstrate the effectiveness of our regret-loss, especially in addressing the above "regrettable" cases.
INTRODUCTION
Large language models (LLMs) have recently exhibited remarkable emerging capabilities (Bubeck et al., 2023; Achiam et al., 2023; Wei et al., 2022b; Yao et al., 2023a). As consequence, bur- geoning body of work has been investigating the employment of LLMs as central controllers for (in- teractive) decision-making, through the construction of LLM-based autonomous agents (Hao al., 2023; Shen et al., 2023; Yao et al., 2023b; Shinn et al., 2023; Wang et al., 2023d; Significant Gravi- tas, 2023). Specifically. the LLM agent interacts with the (physical) world in dynamic/seueential way: it uses LLMs as an oracle for reasoning and planning, then acts in the environment based on the geasoning/planningg and the feedback it perceives over time. L.LM agent has achieved impressive successes in embodied AT (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 al., 2022; 2023) applications.
Besides being dynamic, another increasingly captivating feature of LLMM-asee decision-mald making is the involvement of strategic interactions, oftentimes among multiple LLM agents. For example, it has been reported that the reasoning capability of L.MMS can be improved by interacting with each other through negotiation and/or debate games (Fu et al., 2023; Du et al., 2023); L.MM 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 al., 2022: Mukobi et al., 2023), and in fact, a rapidly expanding literature has employed repeated games as fundamental benchmark to understand the strategic behaviors of LLMs (Brookins & DeBacker,
A Equal contribution.

---

Published as a conference paper at ICLR 2025
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 sophistication level of online decision-makee 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 equilibrium when they repeatedly play games (Cesa-Bianchi & 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 & Roth, 1998; Nekipelov et al., 2015; Balseiro & Gur, 2019). It has thus been posited as an important model of "rational behaviors" in playing games (Blum et al., 2008; Roughgarden, 2015). Hence, it is natural to ask:
Can we examine and better understand the online and strategic decision-muking 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 defer a detailed literature review to Appendix A, and summarize our contributions as follows.
Contributions. First, we carefully examine the performance of several representative pre-trained LLMs in the aforementioned benchmark online makiing settings, in terms of regret. We observe that LLM agents can achieve regret sublinear in time in (non-stochastic) online learning settings, where the loss functions change over time either arbitrarily, or by following some pat- terns 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 multi-LLM, interac- tions. Second, we provide some theoretical insights into the observed sublinear regret behaviors, based on certain assumptions on the supervised pre-training procedure, common practice in train- ing large models for decision-makee In particular, we make a connection of the pre-trained LLMs to the known no-regret algorithm of (FTPL) under these assumptions. Third, we also identify (simple) cases where advanced LLMs such as GPT-4 fail to be no-regret. We thus propose a novel unsupervised training loss, regret-loss, which, in contrast the supervised pre pre- rre-traiiing loss, does not require the labels of (optimal) actions. We then establish both statistical and optimization guarantees for regret- loss minimization, which, in particular, show that minimizing such loss can automatically lead to the known no-regret learning algorithm of follow-the -eeul-rrrrrree leader (FTRL), under single-layer self-attention parameterization. Our further experiments demonstrate the effectiveness of our new loss, especially in addressing the above "regrettable" cases. With the fast development of LLMs, we emphasize that our goal is not to assert whether (current) LLMS are no-regret learners or not, espe- cially given both the positive and negative observations above. Instead, our hope is to introduce and inspire more rigorous metrics and principles into the current evaluation and development of LLM agents, for online and multi-agent strategic decision-making.
and some hypothetical models for training data generation.
2 PRELIMINARIES
Notation. For finite set S, we use A(S) to denote the simplex over S. We denote R+ := fo e || 2 0}. We define 0.2 and 1. as the d-dimensional all-zero and all-one vector, respectively, and Oaxd and Taxa as the d x d-dimensional zero matrix and identity matrix, respectively. For a positive integer d. we define [d] {1,2, .2, d]. For p E Rdd R > and C' Rd being a convex set, define B(p, R, || II) = fi E Rd || pll < R} and Projc.1l1 (p) = arg mingec ||x pll- For any
E Rdd define (x))
For vector E R", we use ||v||p to denote its
iE[d]
I.p no-nnomm with ||o|| denoting the I-z-norm by default. We define 1( = if some event & is true, and 1(8)= otherwise. For random variable X, we use supp(X) to denote its support.
2.1 ONLINE LEARNING & GAMES
Online learning. We consider the online learning setting where an agent interacts with the envi- ronment for T rounds, by iteratively making decisions based on the feedback she receives. Specif- ically, at each time step t, the agent chooses her decision policy N. E II for some bounded domain II, and after her commitment to ,e, a bounded loss function f. : II + [- B, B] for some constant B > is chosen by the environment, potentially in adversarial fashion. The agent thus incurs
2

---

Published as a conference paper at ICLR 2025
loss of (Tt). and will update her decision to π++1 using the feedback. We focus the most basic setting where the agent chooses actions from a finite set A every round, which is also referred to as the Experts Problem (Cover, 1966; Vovk, 1990; Littlestone & Warmuth, 1994; Hazan, 2016), with- out loss of much generality (c.f. Appendix B.5 for a detailed discussion). In this case, II becomes the simplex over A, i.e., π A(A), and (x+)) (fe; mt) for some loss vector & E Rdd that may change over time, where d := [A].
At time step E [T], the agent may receive either the full vector l, or only the realized loss lea, (we sometimes also interchangeably write as (a())), the a,th element of t,, for some at ~ ot()), as feedback, which will be referred to as online learning with full- dall-information feedback, and that with bandit feedback, respectively. The latter is also referred to as the problem in the multi-armed bandit (MAB) literature. Note that hereafter, will by default refer to this setting that does not make any assumptions on the loss sequence (44))T(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 as the non-stationary bandit problem.
wrwrriaaoooonstchssttt bandit
Repeated games. The online learning setting above has an intimate connection to game the- ory. Consider normal-form game G (N, (An Ine[N]: (raIne(N]) where N is the number of players, An and In : Ai of player n. respectively. The N players repeatedly play the game for T rounds, each player maintains a strategy Tn. E A(An) at time t, and takes action on ~ xn,((-). The joint action a, - (ui,,,. .uN.)) determines the payoff of each player at time I, (ra(ae) IneNy. From single- player's (e.g., player n's) perspective, she encounters an online learning problem with (expected) loss function & == -Baa -..0UT n. ...,rx(s (rx(;,_...)) at time I, 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 re- peated 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.
X AN + [-B, BJ] are the action set and the payoff' function
2.2 PERFORMANCE METRIC: REGRET
We now introduce regret, the core performance metric used in online learning and games. For a given algorithm sd, let a denote the decision policy of the agent at time f generated by at. Then, the regret, which the difference between the accumulated (expected) loss incurred by implementing of and that incurred by the best-in- hiindsshi fixed decision, can be defined as 7
Regret, of ((fr)xe(T)) = > fi(TT)) - inf > f(()). FETI
( ((T))e()))) : =f Tar
In the Experts Problem, the definition is instantiated as Regret inf Ei (l,, T). With
a common metric may also take further expectation for Regret over the randomness of the policies (N An algorithm sf is referred to as being no-regret, if max (egret_,(([{))eee in T. Known no-regret algorithms include whwlowthh-regullrizeedddde 2007), follow-the- wew.eeeeeureedd-eeeee leader (Kalai & Vempala, 2005) (see Appendix B.4 for more details). In non-stationary online learning, one may also use the metric of dynamic regrer (Zinkevich, 2003), where the comparator in the definition also changes over time, as the best decision policy at each time t: D-Regret, ((ft)eerr) := I than Regret, bf ((ft)ee)) in that Regret bf (egreet>((frreet))) ((fr)e((T)) I D-Regret of ((fr)
~ ((T), i.e., the worse-case regret grows sublinearly
(Shalev-Shward & Singer,
fi(TTr ()) ET
Σt=1 inf fe(TT) which is stronger notion
Do PRE-TRAINED LLMS HAVE REGRET? EXPERIMENTAL VALIDATION
In this section, we explore the no-regret behaviors of representative LLMs (i.e., mainly GPT-4 Turbo and GPT-4, together with GPT-3.5 Turbo,
and Bama-3-70B-instruue context of online learning and games. All experiments with LLMs are conducted using the public OpenAl (Openai, 2023) or LLM Engine (LLM Engine, 2023) Python API. We provide some hy- pothetical intuitions as to why pre-trained L.M might be no-regret in Appendix C.I, which will be made concrete next.
in the
Interaction protocol. To enable the sequential interaction with LLMs, we first describe the setup and objective of our experimental study. At each round, we incorporate the entire history of loss vec- tors of past interactions into our prompts, as concatenated texts, and ask the L.M agent determine
3

---

Published as a conference paper at ICLR 2025
policy that guides the pociiion-makingg for the next round. Note that since we hope to evaluate the sophistication 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 ablation study of the prompts are deferred to Appendix C.8, and an illustration of the protocol for playing repeated games is given in Figure C.I.
3.1 FRAMEWORK FOR SUBLINEAR REGRET BEIIAVIOR 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 sublinear growth of the regret with finite-time experimental data. Therefore, we propose two frameworks below to rigorously validate the no-regret behaviors of algorithms over a finite T, which might be of independent interest. More details can be found in Appendix C.3.
framework. We propose a statistical hypothesis test aligned with our objectives: Ho The sequence (Regret ((f-)re(1) /t) EEm does not exhibit decreasing pattern
H1 The sequence (Regret s ((f+)ret4) /0) (E(T) shows decreasing pattern.
Ideally, one should check if Regret ((f4) /t approaches zero (or a negative value) as & goes to infinity. With a finite 7 value, testing these hypotheses provides a method to quantify this whether we reject Hy offers a way to measure it. To this end, one needs count the number of of ((fr) ((f))=Et) /t Regret of ((f>)r((++1) /(t + 1) > 0. for which we use Proposition below. We will report the p-value of Ho. denoted as Ptrends as the output of this framework. Proposition 1. (p-value of the null hypothesis). Define the event
T(a,T)= The number of Regres of ((F))ett) Regin ((5.)e(t-1)) >0 for t 1 is least
I+1
Under the assumption that the null hypothesis Ho holds, the probability of this event happening is bounded as FH, (E(s,T)) < سों Et= Regression- framework. We propose an alternative approach by fitting the data with re- gression. In particular, one can use the data [f,, Regret ((f=))r he((r) to fit a function
T 1 t
g() = 30 log t + B1, where the estimate of Bo, i.e., Po. satisfying 3o 1 may be used to indicate the no-regret behavior, i.e., the sublinear growth of Regret ((fr)rej:)) over time. While being simple, cannot be directly used when Regret, ((f))re()
0. Hence, we set log Regret, ((f+)re(a) as 10 if this happens. We define Preg as the p-value of the regression parameter So, and will report the pair of (3u. Preg) as the output of this framework.
3.2 RESULTS: ONLINE LEARNING
We now present the experimental results of pre-trained LLMs in online learning in: 1) (arbitrar- ily) changing environments, 2) non-stationary environments, and 3) bandit-feedback environments. Results for 2) and 3) are deferred to Appendices C.4 and C.5. Changing environments. We first consider the setting with (arbitrarily) changing environments, which are instantiated as follows: 1) Randomly-generated loss sequences. At every timestep, 91 9:)l) for {I,, Vs ~ (0, 10) or le ~ (( I) with clipping to [0, 10) to ensure boundedness of the loss, where Ma ~ Unif ((0, 10)a). Note that we use this as a way to systematically generate potentially arbitrary loss sequences, and also note that our regret was defined for each realization of the random loss vec- tors (instead of their expectations as in the definition of regret in stochustic bandit problems), which can be arbitrarily different across timesteps. 2) Loss sequences with certain trends. Although many real-world environments may change, they often change by following certain patterns. Therefore, we consider two representative trends, the linear trend and the periodic (sinusoid) trend. We sample a. b Unif([0, ) and let & (b a) + for the lincar trend and 4, 5(1 + sin(at + b)) for the periodic trend. In the experiments, we choose d = 2. The average regret (over multiple randomly generated instances) performance is presented in Figure 3.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 achieve sublinear regret in large portion of the instances, and have sometimes even lower regret values than baselines.
generate random loss vector E ~ Unif x [min(x;, 34 ), max(#;,
We emphasize that the error bars in the figures are not associated with the randomness/variane of the algorithms//IJ. M.t.:////MMMMM----- M-agents, but with the randomness/variance of the generation of environment instances.
4

---

Published as a conference paper at ICLR 2025
Uniform
Gaussian
Linear- trend
Sine- -rend
GPI4
GPT4
GPP-
GPE-
(Prema Aog DA5, d:
Ae, L015, D6S,
I/heet As (aa (udt
Bo Poy 11.35 0105
Regret
Regret
Regret
(Prwn
Misrra-RaTs RaTh-
Micrra-Re7b
Micrakaechh
(Piear A.ru /000
IAuw As (iyty)):tuus (07)
(Proe Bo
Ltara-3770n.
Liare-3-118
UPoee f L00 ber.0 0.
Moua de Roel -013 891 m.
Moaut Peglallin a bm
(Prw 8. Pry n 0.55
FTAI.
FTRI:
FTRI.
Iterations
Iterations
Iterations
Iterations
Figure 3.1: Regret of pre-trained LLMs for online learning with full-information feedback. Notably, both commercial and open-source LLMs can achieve sublinear regret as validated by our frameworks and the comparison with FTRL/FTPL, though the performances of weaker models of GPT-3.5 and
open-source ones are worse. Interestingly, the GPT-4 model can even outperform well-known no- regret learning algorithms, FTRL and FTPL.
Uniform
Gaussian
Linear-trnnd
Sine-trend
iphand Bu Roy Mug 0.41,
[Poeut As Mo...0D0..... 6th
30
(hows Aud..imtd 0& (2))
GPT-3 Talho
GPT33 Terler
GPT33 Tulle
GP7-3 Talle
Regret
//oushf Ao (... (.5.50)
Regret
a.97, wa
Rogret
Dewarde pask (d))
Regret
(suea wan.uniirglttt.... us
FIRL
FIRL
FIRL
FIRL
FTH..
FTM.
23
120
30
130
Iterations
Iterations
Iterations
Iterations
Figure 3.2: Regret of pre-trained LLMs for online learning with full-information feedback, with longer horizons of T = 100 and 7 = 200. In most cases, the LLMs can achieve sublinear regret as validated by our frameworks and the comparison with FTRL/FTPL, though the performances of the weaker model of GPT-3.5 is worse.
Behavioral patterns of LLMs. To understand how LLMs make decisions at each time step, we provided example outputs of LLMs reasoning how they generate their policies in Appendix 10 We find that LLMs tend to use the history of the reward vectors by looking at their sum/average, and tend to introduce randomization in decision-making. These are known to be the keys to achieving no-regret behaviors in online learning (Hazan, 2016; Cesa-Bianchi & Lugosi, 2006).
Longer-horizon results. We also test the robustness and scalability of our empirical findings in more challenging environments. We extend the problem horizon T' 100 for the two settings where loss vectors are generated in a stationary way (i.e., Uniform and Gaussian), and T = 200 for the other two non-stationary settings (i.e.. Linear-trend and Sine-trend), Note that since in each round, we need to feed all the previous history to the LLMs, the API costs in fact scale quadratically with respect to the horizon T. Therefore, we replace GPT-4 by cheaper (and more recent) version of GPT-4o. To further scale to even longer-horizon cases with T = 500, we summarize the history to reduce the prompt length by providing L.LMs with the summation of the history loss associated with each action. Similar summary-based input was also used in the concurrent work Krishnamurthy et al. (2024), where both the averaged reward and the action selection count of each action were summarized for the (i.id.) stochastic bandit setting. The corresponding results are provided in Fig- ure 3.2 and Table 1, where the LLMs can exhibit no-regret behaviors as validated by our frameworks and the comparison with FTRL/FTPL.
(Ptrends Bor Preg)
GPT-40
FTRL
FTPL
Uniform
(0.0, 0.85, 0.0)
(0.0, 0.6, 0.0)
(0.0, 0.52, 0.0)
Gaussian
(0.0, 0.86, 0.0)
(0.0, 0.64, 0.0)
(0.0, 0.68, 0.0)
Linear-trend
(0.02, 0.83, 0.5)
(0.02, 0.76, 0.1)
(0.01, 0.79, 0.0)
Sine-trend
(0.09, 0.28, 0.0)
(0.01, 0.24, 0.0)
(0.01, 0.26, 0.0)
Table 1: Longer-horizon (T = 500). GPT-4o model can still exhibit sublinear regret behaviors as validated by our frameworks and the comparison with FTRL/FTPL.
3.3 RESULTS: MULTI-PLAYER REPEATED GAMES
We now consider the setting when multiple LLMs make online decisions in 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
5

---

Published as a conference paper at ICLR 2025
Two- wlayyr games
Three- plecepplaerrgee games
Four- Sour-playrrra games
30
GPPE-
CPPT-
R.. P-y.-- U.G3,
fu P-U.. U.69.
(/hund Pae 0.0,
GPT-355 Tutoo
20
3.T.3.5 Tarbo
GPT 3.5 Tulbo:
Regret
(freee Ao Poy) 0.D)
Regrel
(Powes fo Poy)-100 09,
Regret
(Phead P 0.93,
FIRI.
25
PIRI.
PTRI.
FIFL.
FTPL.
FTN..
Iterations
Iterations
Iterations
Figure 3.3: Regret of pre-trained LLMs for repeated games of different sizes, most cases, both commercial and open-source LLMs can achieve sublinear regret as validated by our frameworks and the comparison with FTRL/FTPL. We report the regret of one agent for ease of presentation.
Alternating loss
Noisy alternating loss
Adaptive loss
Singlokayer
200
Singloslayer
(itros Bo 300.0. 289, 0.0 Girt---tebe
Uyhvor (ott 27, 0.75 0.09
(thewr l6, 100.27.0.7 27, 0.75, 0.1
Malts-lger:
Malli-lyer:
Regret
(shroe So P010- 3.96
Regret
(Dveat (Jieer.Be.Pra Pe.Pra/-00 (.55.0.0 0.09
Regrer
(thowr Rs (R.,,,)4000000000 (.60)
FTRL:
FTRL:
(Phcne Rr. Preeeetll (998..00
100
(Phew f 102_po2000--2000111 0.
CPTF-
-12
UPhan Ao. 1.96 0.0)
50
(Shers A.P. 1m110, 1.13, 0.0)
20
4PT4 Tubbo
GPF4 Turbo
(noo de Pag 1m0007, 0.0)
-30
Iterations
Iterations
Iterations
Figure 3.4: (left) Regret of GPT-4 (Turbo) under the canonical counterexample for FTL (Hazan, 2016, Chapter 5). (mid, right) Failure of GPT-4 (Turbo) on two scenarios with regrettable behaviors, while Transformers trained by our new regret-loss (N- = 1) in Section 5 can achieve sublinear regret.
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 C.1 for example of the prompt). This is a typical scenario in learning in (repeated) games (Cesa-Bianchi & Lugosi, 2006).
Representative games. We first test LLMs on representative general-sum games (win-win, pris- oner's dilemma, unfair eyclic, biased, and second best) studied in Robinson & Goforth (2005) (c.f. Appendix B.6). For each type of the game, we conduct 20 repeated experiments.
Randomly generated games. To further validate the no-regret behaviors 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 Uni 10)). These are larger and more challenging settings than the structured and representative ones above.
We summarize the experimental results in Figure 3.3, which are similar to the above in the online set- ting: for all types of games, pre-trained I.LMs can achieve sublinear regret, which is often lower than that obtained by FTRL/FTPL for most games. We provide six instances of three-player general-sum games and six instances of four-player general-sum games in Figure C.4 and Figure C.5, respec- tively. Occasionally, GPT-4 even provides a negative regret value.
3.4 PRE-TRAINED LLM AGENTS CAN STILL HAVE REGRET
The experiments above may suggest the no-regret behaviors of LLMs in online learning and game playing. However, is this capability universal? We show that the no-regret property can break for LLM agents if the loss vectors are generated in more adversarial way.
Canonical counterexamples for -eleedr. First, consider two well-known examples 2012) suffers from linear regret.
that the follow-the-
(FTL) algorithm
Example 1: (1) 5, e (2) 0 and ( - +%2) 10, (,
0 for t > 2 (Hazan, 2016).
Example 2: (2 - 1%2) = 10, (1 + 1%2) = 0 for 1 < t < c and (1 = 10, (2( = 0 for c+1 T 500), for some integer satisfying 0 < c T (Feder et al., 1992).
Here, % denotes the modulo operation. Interestingly, for Example 1, GPT-4 agent can easily iden- tify the pattern for the loss sequence that the optimal action alternates, thus accurately predicting the loss will receive and achieving low regret in Figure 3.4. For Example 2, the GPT-4 agent with raw history input also provides an impressively lower (negative) regret than FTRL and FTPL.

---

Published as a conference paper at ICLR 2025
(Figure C.6). The GPT-4 agent with summarized history imput, in contrast, suffers from much larger regret than FTRL and FTPL. We defer the detailed comparison between using raw history and sum- marized history to Figure C.6, and an explanation of LLMs' behaviors via predicting the trend of the loss instances to Appendix C.7. In summary, the GPT-4 agent may predict such worst-case se- quences well, and does not fail in the same way as FTI., which is known to suffer from lack of randomness in decisions.
Additionally, the results on Example 2 also imply that summary-based history input can perform worse than the www-history-baser one in the adversarial setting we consider, while the former was claimed be the key in succeeding in the i.i.d. stochastic bandit setting (Krishnamurthy et al., 2024). The regret values with these two types of input differ significantly, with p-value of 1.2 x 10 157 under a one-sided independent t-test. These results further illustrate the fundamental differences between the settings considered in Krishnamurthy et al. (2024) and ours.
Noisy alternating loss sequence. Inspired by the above, we design new loss sequence that is similar but less predictable, by adding some noise to the canonical counterexample. Specifi- cally. we construct the following (simple) loss sequence with 2 actions such that ( + +%2) min(25/4 I, 10), (2 1%2) ~ Unif([9, 10)) for / E [25].
Adaptive loss sequence. We also develop simpler but more adaptive loss sequence that takes the full power of the adversary in our online learning setup. After the GPT-4 agent provides Te, we choose le with (arg max; TTs) = 10 and (3 arg max; (T)) O.
We also report the average regret over 20 repeated experiments for the later two settings using GPT-4 and more advanced GPT-4 Turbo Figure 3.4, where we cannot reject the hypothesis that GPT-4 (Turbo) has linear regret by either our trend-checking observations have thus motivated us to design new approaches to further promote the no-regret behaviors of the models, with additional training, as to be detailed in Section 5. Before it, we first provide some theoretical insights into the observed sublinear regret behaviors.
regression-baset framework. These
4
WHY DO PRE-TRAINED LLMs (NOT) HAVE REGRET? A HYPOTHETICAL MODEL AND SOME THEORETICAL INSIGHTS
We now provide some plausible explanations about the observed no-regret behaviors of pre-trained LLMs, which are highly hypothetical by nature, since to the best of our knowledge, the details of pre-training these popular L.MMs (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 existing assumptions in the literature for modeling human behaviors, and the recent literature on understanding LLMs and Transformers.
4.1 (HUMAN) DECISION-MAKIN MODEL: QUANTAL RESPONSE
A seminal model for human decision-making behaviors is the quantal response model, which sumes that humans are often imperfect decision-makers and their bounded rationality can be mod- eled through unseen latent variables that influence the decision-making process (McFadden, 1976; McKelvey & Palfrey, 1995), for which we defer the formal definition and introduction to Ap- pendix D.2. In online decision-make making. given the history information with multiple loss vectors, we adopt the following generalization of the quantal response model.
Definition 4.1 (Quantal response against multiple losses). Given set of losses (Es)ie(t). noise distribution ~ Proises and 1/2 > 0, the generalized quantal response against (fi)etq is defined as
a (a)
quounee (a|(e))e((a) = 1P guassta!
Σ
P
E arg min argmin s(a)) where T + Σ
a'EA
In simpler terms, the generalized quantal response is defined as the standard quantal response against the summation of the losses. Such a model has been investigated in the earning-in-gamed and be- havioral economics literature (see Appendix D.2 for more details). Such a definition is also aligned with our empirical findings on LLMs behavioral patterns in Section 3.2: i) evaluating the summa- tion/average; ii) introducing randomization in decision-nie makiing. To gain more insights into these empirical findings, we next analyze case where pre- training under certain assumptions provably leads to the quantal response behaviors and further yields no-regret guarantees.
4.2 CASE STUDY: TRE-NIINN UNDER CANONICAL DATA DISTRIBUTION
Pre-training of LLMs is predominantly based on next-token prediction. When applying LLMs to sequential decision-making, the model receives the context of the mecision task as
7

---

Published as a conference paper at ICLR 2025
(I1, F2. ,2N) and then generates (IN+1,-.. .TM) encoding the action for some N, . N+ and N < M. where each 2, E V represents one natural language token for i E [M], and V is the finite token set. This process can be conceptualized form of the next token prediction (Yao et al., 2023b; Shinn et al., 2023; Liu et al., 2023ate). Note that this training procedure may also appear in the form of supervised fine-tuning (SFT) for down- stream tasks of decision-making or mmestion-answeriig to obtain (Cobbe et al., 2021; Li et al., 2022: Lewkowyez et al., 2022). Meanwhile, large models are often (pre- (reenttraindd 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- stutionary/udversaate
predicting the optimal action in the
where optimal action labels may be easier
loss sequences in online learning. Thus, it is natural to ask: Iy it possible to have no-regret behaviors emerging as a consequence of this (optimal) action prediction, under only a fixed pre-training distribution of the environments?
Examples in Sec. 3.2
Here we analyze a standard pre-training objective on token sequence distribution F1:N++1 ~ Pleat for given t E (T], which is the expected log-likelihood maximization for next- token prediction over θ, the parameter space of the LLM:
regie.
(Draat So So H-L. 0-46, (.D)
Degree/Dynamic
GPPE-4 dytamic
Gasciaized QR regret.
1
Uvvet P-y 0.51, D.0)
max BE
E E PlAZE
Σ ==1
log LLM, (Iy (=)))-), (4.1)
(Dower Pay 10000. 0.92,
where we define LLMo, (x1 11:0) = LLMs (I1).
15 Iterations
For the pre-training distribution, we model it as follows: there exists a latent variable 2, representing the loss for the underly- ing static decision-making problem. The pre-training dataset, however, only contains partial observations FI:N, (a natural language representation of f1:)) of z due to imperfect data col- lection, which could be attributed to the fact that & is private to the data-generator (human), representing the actual intention Hence, LLM will only be pre-
Comparison of GPT- 4 with the generalized QR model, where the model can very well capture the behavior of the GPT-4 agent for examples in Section 3.2.
Figure 4.1:
of the human/data-generatoo trained with partial and noisy information about 2. Meanwhile, we assume that some high-quality action label IN I:N,1, (a natural language representation of a) with respect to the underlying loss vector z is also available in the dataset, which could come from user surveys, personal blogs, or data annotation. We formalize such an assumption:
Assumption (Pre-training distribution). Given T E N+, t E [T.. No-1 E N+, there are latent variables (2, NI,..., No E [Ne4t). No that P(z,1a,, TI:N 1) = ((2,(1))P(1IIN) (1N))((N F(Z1NN))) = -J P((z, (2,,1,,,1NN ddlzd Intuitively, tokens 14NN Jrete encode the context, i.e., information for lu and the user will decode action a frrmmm XN, +1NN
0, such
and Pleut(r1-N111
To further understand our assumption, we provide an example in Appendix D.3, showing how a natural text corpus may satisfy it. Similar assumptions that suppose the existence of such latent variables in generating the pre-training datasets have also been made recently in Lee et al. (2023); Lin et al. (2024); Liu et al. (2023e), for understanding the in-context decision-making behaviors of LLMssTransformenss through posterior sampling, for which we defer detailed comparison to Appendix D.8. In particular, we show in Theorem 4.1 that if the noise, i.e., l - = is modeled as Gaussian distributions and 2N,+1:N+4: encodes the optimal action for 2, the pre- trained LLM provably recovers the prominent human behavior model in Section 1. the quantal response model.
Theorem 4.1 (Informal: Emergence of no-regret behavior). Suppose Assumption I holds with both the prior distribution of z and the conditional distribution of {& hhee being Gaussian, and &N++1.N.41 encodes the optimal action for 2. Then, with the function class of LLMg being expressive enough, and 0* being a maximizer of Equation (4.1), the behavior of L- follows Definition 4. I. Furthermore, the use of L. can achieve no (dynamic) regret for (non-stationary online learning with fillfull-infoon null-information/bandi feedback for arbitrary loss vectors (with bounded variation).
The formal statement and proof are deferred to Appendix D.6. The results show that even when pre-training is conducted solely with loss vectors generated from stationary distributions (f1:1 are ii.d. conditioned 2), it can still enable the emergence of no-regret behaviors in online learning against potentially adversarial losses. Key in the proof is the connection of pre- trained LLM models to the online learning algorithm of FTPL. Furthermore, Assumption can be relaxed to better match
8

---

Published as a conference paper at ICLR 2025
the actual LLMs' pre-training data distributions from diverse sources (c.f. Appendix D.7), and the prior distribution of & could also be replaced by a general distribution (c.f. Theorem D.2). Finally, point out its implications for playing games in Appendix D.6.1.
How well can our hypothetical model class predict actual LLMs' behaviors? To further verify our theo model in Theorem 4.1, we propose to estimate the parameters of {1 ) in Definition 4.1 using the interaction data with actual LLMs, and use the estimated model predict LLMs' behaviors on some test set. In Figure 4.1, we show the averaged regret for the LLMs and our estimated model, where the generalized quantal response can very well capture the behavior of the L.M agent for all problem instances in Section 3.2, on which the LLMs oftentimes achieve sublinear regret, justifying the applicability of our hypothetical model and assumptions.
Finally, we acknowledge that for existing pre-trained LLMs like GPT-4, the canonical assumptions above, though may be further relaxed (c.f. Remark D.3), may not hold in general. More importantly, the supervision labels, i.e., the optimal action given may be sometimes imperfect unavailable in the dataset. These caveats motivate the study our next section.
5 PROVABLY PROMOTING NO-REGRER BEHAVIOR BY A NEW LOss
In light of the observations in Section 3, we ask the question:
Is there a way to enhance the no-regret property of the models without (optimal) action labels?
To address this question, we propose to train models with a new unsupervised learning loss that naturally provides no-regret behaviors. We will particularly focus the Transformer architecture (Vaswani et al., 2017) under this new loss, a common architecture used in most existing LLMS.
5.1 A NEW UNSUPERVISED TRAINING Loss:
Regret-Loss
Intuitively, our new training loss is designed to enforce the trained models to minimize regret under an arbitrary sequence of loss vectors. Specifically, we define the training loss as
((0) = max E.....
RegrefLLMO ((C))uetz))
(5.1)
where |/ S B for t E [T]. As discussed Kirschner et al. (2023). directly minimizing the max regret can be computationally challenging, except for superficially simple problems. More- over, Equation (5.1) not necessarily differentiable with respect to the parameter if it does not satisfy the condition of Danskin's Theorem (Danskin, 1966); or even if it is differentiable (i.e., the maximizer of (4)eefz) is unique), computation of derivatives can challenging since we need to calculate arg max (fe)cctry Regret,IMM, ((f)))e(r)) while there is an inf in the definition of regret. Therefore, we provide general class of surrogate losses approximate Equation (5.1):
Σ JjE[N] h(Regret (f ((el (E(()))))))))))))
1(0,k, = E
(5.2)
ΣjENN (igini/RRee [(Regret ((e()) )(e(T)))))
where E N+, N E N+, R R+ continuous function, with continuous derivative
W. and [(, k) : R R+ is continuous function for each k E N+, satisfying limg- ((R.
T(R2.k)
co. 1(R > +1)+ R2), where we use the convention of cc-0 = 0. These conditions on h, will be assumed throughout the paper. Examples of such an f include f(x k) x² and exp (kr).
We will sample N trajectories of loss sequences (e(²) )[E[TT.JE[[] from some continuous probability distribution supported on 1-B,B TxN (without other additional statistical assumptions), and the expectation Equation (5.2) is thus taken with respect to this distribution. In Appendix E.2, we
prove that under certain regularity conditions of f and h, we have
lim C(O, k, N) = max Regret ((())Em)) N.
(1...er
and the uniform convergence of L(0, N): lim supeee max Regret,IM, ((()))))) t....er
N.k
N)) O, where θ is compact set of the model parameters. Hence, can expect that minimizing the loss function in Equation (5.2) with large enough k and N may promote the trained models to have small regret value. We will hereafter refer to Equation (5.2) as the regret-loss.

---

Published as a conference paper at ICLR 2025
5.2 GENERALIZATION AND REGRET GUARANTEES OF REGRET-LOSS MINIMIZATION
We first establish a statistical guarantee under general parameterizations of LLM,, that are Lipschitz with respect to 0, including the Transformer-basee models used in GPT-4 and most existing LLMs (see Proposition 2 for an example with a formal statement). This guarantee focuses on their gener- alization ability when trained to minimize the empirical regret loss (c.f. Equation (E.3)), denoted as C(0, k, N, Nr), by replacing the expectation E in Equation (5.2) with the empirical mean using NT samples. We denote NN. E arg mingge Σ(0, k. N, Nr), and present the generalization guarantee in Theorem E.I. Thanks to the uniform convergence of C(0, k, NN (c.f. Appendix E.2), we further obtain the following theorem on the regret guarantee of ay.
Theorem 5.1. (Regret), Suppose" for any K E N+, (-,k) are non-decreasing, and log ʃ is supermodular function (i.e., log f(R,, k1) log f(R,, 2 log f( k1) - log I (R2, k2) for Ri 2 R2 and ki 2 k2). Then, with high probability, we have
lim No k-000
max lee
RMgr N.
inf max [EE
Regro ((()))))) 5
NT
de
We defer the proof of the theorem to Appendix E.4. Therefore, if additionally, the model parameteri- zation (e.g.. Transformers) can realize no-regret algorithm (as to be shown next), then Theorem 5.1 means that with a large enough Nr, the learned LLM M. becomes a no-regret learner, i.c.,
Regref $..NNN ((())e)))) = o(T). Finally, as a consequence, it is folklore that when multiple such LLMs interact, a coarse correlated equilibrium will emerge in the long-term (c.f. Corollary 1).
5.3 REGRET-LOSS TRAINED TRANSFORMERS CAN BE ONLINE LEARNING ALGOIIHTM
Despite the generality of the previous results, one cannot use an infinitely large N and k in prac- tice. Hence, now provide results when N is finite, for the architecture of Transformer models (Vaswani et al., 2017). We focus on single-layer (linear) self-attention models, as in most recent theoretical studies of Transformers (Ahn al., 2023; Zhang et al., 2023a; Mahankali et al., 2023), and N = 1. Note that in this case. the choice of f (and thus k) is not relevant. Thus, throughout this subsection, we drop superscript (j) in Equation (5.2). We sample 4, for t E [Z'] as realizations of some random variable Z, where we assume that Z is symmetric about zero, and Var(Z) Σ > O. We consider the single-layer linear self- celf-attention model as follows, for which we can show that the global optimizer of our regret-loss can automatically lead to no-regret learning algorithm:
g(Z,; V, K, Q, Ves kic 9c)= Σ (vV, + u.) ((K&, + Ke)T (Qc qc))
(5.3)
Theorem 5.2. Consider the policy space II = B(0, Rn, |l II) for some Ri > 0. The configu- ration of a single-layer linear self-attention model in Equation (5.3) (V, K, Q, Ver kes 9c) such that (IEle1e Σ-1 a global optimal solu-
KT + 9c) = Ve Og and V 2n 'E ( tion of Equation (5.2) with N 1, h(x)) x²2 Moreover, every global optimal configuration of Equation (5.2) within the parameterization class of Equation (5.3) has the same output function g. Additionally, if is a diagonal matrix, then plugging any global optimal configuration into Equa- tion (5.3), and projecting the output with Pro In1 is equivalent to FTRL with an Le-regularizer.
Theorem 5.2 not only shows the capacity of self-attention models: it can realize online learning algorithms, but also shows, more importantly, that minimizing cally produce it. In particular, one does not need to hard-code the parameters of the Transformer to implement no-regret algorithms. Under single-layer self-attention parameterization (with softmax), we can also show that a stationary point of the loss function (Equation (5.2)) can lead to FTRL (c.f. Appendix E.5). Some potential generalizations of the results are also discussed in Appendix E.9.
new regret-loss may automati-
5.4 EXPERIMENTAL RESULTS FOR REGRET-LOSS TRAINED TRANSFORMERS
We now provide experimental results for minimizing our regret-loss with the Transformer models, and evaluate in the following environments: 1) randomly-generatee loss sequences (Figure E.3); 2) loss sequences with certain trends (Figure E.4); 3) repeated games (Figure E.5); and 4) counterex- amples for pre-trained LLMs to be regrettable (Figure 3.4). Training setup can be found in Ap- pendix 1.1. We also provide an ablation study for optimizing Equation (5.2) in Appendix E. 12
Finally, we provide discussions on the limitations and future directions in Appendix F.
Note that these conditions on h, f in addition those specified after Equation (5.2).
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENT
The authors thank Constantinos Daskalakis, Kristian Georgiev, Noah Golowich, Dingwen Kong, Akshay Krishnamurthy, and Aleksander Madry for their helpful feedback. In particular, the authors thank Dingwen Kong for discussing the truncation idea in proving Lemma 8, and thank Akshay Kr- ishnamurthy for bringing up a concurrent work that inspired our new experiments for the stochastic bandit setting that strengthened our paper. X.L. and K.Z. acknowledge the support from the U.S. Army Research Laboratory and the U.S. Army Research Office under grant number W911NFF24-1- 0085 and NSF CAREER Award-2443704.
REFERENCES
Jacob Abernethy, Chansoo Lee, Abhinav Sinha, and Ambuj Tewari. Online linear optimization via smoothing. In Conference on Learning Theory, pp. 807-823. PMLR, 2014.
Jacob Abernethy, Chansoo Lee, and Ambuj Tewari. Fighting bandits with new kind of smoothness. Advances in Neural Information Processing Systems, 28, 2015.
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Iige Akkaya, Florencia Leoni Ale- man, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint arXiv:2303.0877 2023.
Gati V Aher, Rosa Arriaga, and Adam Tauman Kalai. Using large language models to simulate multiple humans and replicate human subject studies. In International Conference on Machine Learning, pp. 337-371. PMLR, 2023.
Kwangjun Ahn, Xiang Cheng, Hadi Daneshmand, and Suvrit Sra. Transformers learn to imple- ment preconditioned gradient descent for in-context learning. Advanced in Neural Information Processing Systems, 2023.
Michael Ahn, Anthony Brohan, Noah Brown, Yevgen Chebotar, Omar Cortes, Byron David, Chelsea Finn, Chuyuan Fu, Keerthana Gopalakrishnan, Karol Hausman, et Do as can, not as say: Grounding language in robotic affordances. arXiv preprint arXiv:2204.01691, 2022.
Mohammad Ahsanullah, Valery Nevzorov, and Mohammad Shakil. An introduction to order statistics, volume 8. Springer, 2013.
Elif Akata, Lion Schulz, Julian Coda-Forno, Seong Joon Oh, Matthias Bethge, and Eric Schulz. Playing repeated games with large language models. arXiv preprint arXhv:2305.16867 2023.
Ekin Akyürek, Dale Schuurmans, Jacob Andreas, Tengyu Ma, and Denny Zhou. What learning algorithm is in in-context learning? investigations with linear models. International Conference Learning Representations, 2023.
Lisa P Argyle, Ethan C Busby, Nancy Fulda, Joshua R Gubler, Christopher Rytting, and David Wingate. Out of one, many: Using language models to simulate human samples. Political Anal- ysis, 31(33333773355 2023.
Raman Arora, Ofer Dekel, and Ambuj Tewari. Online bandit learning against an adaptive adversary: from regret to policy regret. In Proceedings of the 29th International Coference on International Conference on Machine Learning, pp. 1747-1754, 2012a
Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: meta- algorithm and applications. Theory of computing, 811):21 2012b.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multi- armed bandit problem. SIAM journal on computing, 32(1):48-77, 2002.
Yu Bai, Fan Chen, Huan Wang, Caiming Xiong, and Song Mei. Transformers statisticians: Provable in-context learning with in-context algorithm selection. Advanced Neural Information Processing Systems, 2023.
11

---

Published as a conference paper at ICLR 2025
Anton Bakhtin, Noam Brown, Emily Dinan, Gabriele Farina, Colin Flaherty, Daniel Fried, Andrew Goff, Jonathan Gray, Hengyuan Hu, et al. Human-level play in the game of diplomacy by com- bining language models with strategic reasoning. Science, 37866624::0077-00744 2022.
Santiago R Balseiro and Yonatan Gur. Learning in repeated auctions with budgets: Regret mini-
mization and equilibrium. Management Science, 65(9):3952-3988, 2019.
Claude Berge. Topological spuces: Including a treatment of mulli-valued functions, vector spaces and convexity. Oliver & Boyd, 1877.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi-armed-bandit problem with non- stationary rewards. Advances in neural information processing systems, 27, 2014.
Avrim Blum and Yishay Mansour. From external to internal regret. Journal of Machine Learning Research, 8(6). 2007.
Avrim Blum. Mohammad Taghi Hajiaghayi, Katrina Ligett, and Aaron Roth. Regret minimization and the price of total anarchy. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pp. 373-382 2008
Philip Brookins and Jason Matthew DeBacker. Playing games with GPT: What can we learn about large language model from canonical strategic games? Available at SSRN 4493398, 2023.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in Neural Information Processing Systems, 33:1877-1901, 2020.
Sébastien Bubeck, Nicolo Cesa Cesa-Bianchi, et al. Regret analysis of stochastic and nonstochastic multi- armed bandit problems. Foundations and Trends@ in Machine Learning, 5(1):1-122, 2012.
Sébastien Bubeck, Varun Chandrasckaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Ka- mar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et al. Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint arXiv:2303. 2023.
Colin Camerer. Behavioral game theory: Experiments in strategic interaction. Princeton Univer- sity Press, 2011.
Nicolo Bisa-Bianchi and Gábor Lugosi. Prediction, Learning, and Games. Cambridge University Press, 2006.
Nicolo
Philip M Long, and Manfred K Warmuth. Worst-case quadratic loss bounds for prediction using linear functions and gradient descent. IEEE Transactions on Neural Net- works, 7(3):604-619, 1996.
Chi-Min Chan, Weize Chen, Yusheng Su, Jianxuan Yu, Wei Xue, Shanghang Zhang, Jie Fu, and Zhiyuan Liu. Chateval: Towards better llm-based evaluators through multi-agent debate. Inter- national Conference on Learning Representations, 2024.
Weize Chen, Yusheng Su, Jingwei Zuo, Cheng Yang. Chenfei Yuan, Chen Qian, Chi-Min Chan, Yujia Qin, Yaxi Lu, Ruobing Xie, et al. Agentverse: Facilitating multi-agent collaboration and exploring emergent behaviors in agents. International Conference on Learning Representations, 2024.
Yiting Chen, Tracy Xiao Liu, You Shan, and Songta Zhong. The emergence of economic rationality of gpt. Proceedings of the National Academy of Sciences, 120(51):e2316205112, 2023.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Rejichir Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:21 14.141...4... 168, 2021.
Thomas M Cover. Behavior of sequential predictors of binary sequences. Number 7002. Stanford University, Stanford Electronics Laboratories, Systems Theory ... 1966.
12

---

Published as a conference paper at ICLR 2025
Damai Dai, Yutao Sun, Li Dong, Yaru Hao, Shuming Ma, Zhifang Sui, and Furu Wei. Why can GPT learn in-context? language models secretly perform gradient descent as meta-optimizers. In Anna Rogers, Jordan Boyd-Graber, and Naoaki Okazaki (eds.), Findings of the Associa- fion for Computational Linguistics: ACI. 2023, pp. 4005-4019, Toronto, Canada, July 2023. URL
Association for Computational Linguistics. doi: 10. 10.18653/w1/0033
http://ww//.....ngggnnnl.ll. org/ 2023. findings-aclinn. ac1.
John M Danskin. The theory of max-min, with applicatioos. SIAM Journal on Applied Mathematics, 14(4):641-664, 1966.
Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich. Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 14-27604-27614 2021.
Jingying Ding, Yifan Feng, and Ying Rong. Myopic quantal response policy: Thompson sampling meets behavioral economics. arXiv preprint arXiv:2207.01028 2022.
Danny Driess, Fei Xia, Mehdi SM Sajadi, Corey Lynch, Aakanksha Chowdhery, Brian Ichter, Ayzaan Wahid, Jonathan Tompson, Quan Vuong, Tianhe Yu, et al. Palm-e: An embodied multi- modal language model. International Conference on Machine Learning, 2023.
Yilun Du, Shuang Li, Antonio Torralba, Joshua B Tenenbaum, and Igor Mordatch. Improv- ing factuality and reasoning in language models through multiagent debate. arXiv preprint arXiv:2305. 14325, 2023.
Christoph Engel, Max RP Grossmann, and Axel Ockenfels. Integrating machine behavior into human subject experiments: A user-friendly toolkit and illustrations. Available at SSRN, 2023.
Ido Erev and Alvin E Roth. Predicting how people play games: Reinforcement learning in experi- mental games with unique, mixed strategy equilibria. American Economic Review, pp. 848-881, 1998.
Caoyun Fan, Jindou Chen, Yaohui Jin, and Hao He. Can large language models rational players in game theory? a systematic analysis. arXiv preprini arXiv:23/2.054888 2023.
Meir Feder, Neri Merhav, and Michael Gutman. Universal prediction of individual sequences. IEEE Transactions Information Theoory (2(4)):258-122) 1992.
Yoav Freund and Robert E Schapire. A decision-theoretio generalization of on-line learning and an application to boosting. Journal of computer and system sciences, 19-119 1997.
Yao Fu, Hao Peng. Tushar Khot, and Mirella Lapata. Improving language model negotiation with self-play and in-context learning from ai feedback. arXiv preprint 3:X.::2305.10142. 2023.
Drew Fudenberg and David M Kreps. Learning mixed equilibria. Games and Economic Behavior, 5(3):320-365 -077200377711 1993.
Drew Fudenberg and David K Levine. The theory of learning in games, volume 2. MIT Press, 1998.
Bolin Gao and Lacra Pavel. On the properties of the softmax function with application in game theory and reinforcement learning. arXiv preprint arXiv: 170.0000000 2017.
Shivam Garg, Dimitris Tsipras, Percy S Liang, and Gregory Valiant. What can transformers learn in-context? a case study of simple function classes. Advances in Neural Information Processing Systems, 35:30583-30598, 2022.
Angeliki Giannou, Shashank Rajput, Jy-yong Sohn, Kangwook Lee, Jason Lee, and Dimitris Papailiopoulos. Looped transformers programmable computers. International Conference Machine Learning. 2023.
Shibo Hao, Yi Gu, Haodi Ma, Joshua Hong, Zhen Wang, Daisy Wang, and Zhiting Hu. Reasoning with language model is planning with world model. In Houda Bouamor, Juan Pino, and Ka- lika Bali (eds.), Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 8154-8173 Singapore, December 2023. Association for Computational Linguis- tics. doi: 18.18653/v 1000003emllpmmaiie emnlp-ma in. 507.
URL ht attps: / /acaaannntooooooo org/2023.
13

---

Published as a conference paper at ICLR 2025
Elad Hazan. Introduction to online convex optimization. Foundations and Trends@ in Optinization, 2(3-4):157-322 2016.
Josef Hofbauer and William H Sandholm. On the global convergence of stochastic fictitious play. Econometrica, 70(6):2665-2294, 2002.
Sirui Hong, Xiawu Zheng, Jonathan Chen, Yuheng Cheng, Ceyao Zhang, Zili Wang, Steven Ka Shing Yau, Zijuan Lin, Liyang Zhou, Chenyu Ran, et al. Metagpt: Meta programming for multi-agent collaborative framework. International Conference on Learning Representations, 2024.
John J Horton. Large language models simulated economic agents: What can learn from homo silicus? Technical report, National Bureau of Economic Research, 2023.
Arnijot Hoyland and Marvin Rausand. System reliability theory: Models and statistical methods. John Wiley & Sons, 2009.
Wenlong Huang, Pieter Abbeel, Deepak Pathak, and Igor Mordatch. Language models as zero-shot planners: Extracting actionable knowledge for embodied agents. In International Conference on Machine Learning. pp. 9118-9147, PMLR, 2022a.
Wenlong Huang, Fei Xia, Ted Xiao, Harris Chan, Jacky Liang, Pete Florence, Andy Zeng, Jonathan Tompson, Igor Mordatch, Yevgen Chebotar, et al. Inner monologue: Embodied reasoning through 2022b.
planning with language models. arXiv preprint arXiv:2207.0566
Hui Jiang. A latent space theory for emergent abilities in large language models. arXiv preprint arXiv:2304.00 09960, 2023.
Adam Kalai and Santosh Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 71(3):291-37,, 2005.
Mikotaj J Kasprzak, Ryan Giordano, and Tamara Broderick. How good is your gaussian approxima- tion of the posterior? finite-sample computable error bounds for variety useful divergences. arXiv preprint arXiv:2209. /4992, 2022.
Johannes Kirschner, Alireza Bakhtiari, Kushagra Chandak, Volodymyr Tkachuk, and Csaba Szepes- vari. Regret minimization via saddle point optimization. Thirty-seventh Conference on Neural Information Processing Systems, 2023.
Akshay Krishnamurthy, Keegan Harris, Dylan Foster, Cyril Zhang, and Aleksandrs Slivkins. Can large language models explore in-context? arXiv preprint arXiv:2403. 15371, 2024.
Michael Laskin, Luyu Wang, Junhyuk Oh, Emilio Parisotto, Stephen Spencer, Richie Steigerwald, DJ Strouse, Steven Hansen, Angelos Filos, Ethan Brooks, et In-context reinforcement learning with algorithm distillation. International Conference on Learning Representations, 2023.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Jonathan N Lee, Annie Xie, Aldo Pacchiano, Yash Chandak, Chelsea Finn, Ofir Nachum, and Emma Brunskill. Supervised pretraining can learn in-context reinforcement learning. Neural Information Processing Systems, 2023.
Aitor Lewkowyez, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Ra- masesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo et al. Solving quantitative reasoning problems with language models. Advances Neural Information Processing Systems, 35:3843-3857, 2022.
Chao Li, Xing Su, Chao Fan, Haoying Han, Cong Xue, and Chunmo Zheng. Quantifying the impact of large language models on collective opinion dynamics. arXiv preprint arXiv:2308.033: 2023a.
Guohao Li, Hasan Abed Al Kader Hammoud, Hani Itani, Dmitrii Khizbullin, and Bernard Ghanem. Camel: Communicative agents for" mind" exploration of large scale language model society. Neural Information Processing Systems, 2023b.
14

---

Published as a conference paper at ICLR 2025
Ruosen Li, Teerth Patel, and Xinya Du. Prd: Peer rank and discussion improve large language model based evaluations. arXiv preprint arXiv:2307.02262. 2023c.
Shuang Li, Xavier Puig, Chris Paxton, Yilun Du, Clinton Wang, Linxi Fan, Tao Chen, De-An Huang, Ekin Akyürek, Anima Anandkumar, et al. Pre-trained language models for interactive decision- making. Advances in Neural Information Processing Systems, 35:31 199--1991122 2022.
Siyu Li, Jin Yang, and Kui Zhao. Are you in masquerade? exploring the behavior and im- pact of large language model driven social bots in online social networks. arXiv preprint arXiv:2307. 100337777.137,, 2023d.
Yingcong Li, Muhammed Emrullah Ildiz, Dimitris Papailiopoulos, and Samet Oymak. Transformers as algorithms: Generalization and stability in in-context learning, International Conference on Machine Learning, 2023e.
Zifan Li and Ambuj Tewari. Beyond the hazard rate: More perturbation algorithms for adversarial multi-armed bandits. J. Mach. Learn. Res., 18:183-1, 2017.
Tian Liang, Zhiwei He, Wenxiang Jiao, Xing Wang, Yan Wang, Rui Wang. Yujiu Yang, Zhaopeng Tu, and Shuming Shi. Encouraging divergent thinking in large language models through multi- agent debate. arXiv preprint arXiv:2305. 19//8 2023.
Licong Lin, Yu Bai, and Song Mei. Transformers as decision makers: Provable in-context reinforce- ment learning via supervised pretraining. International Conference on Learning Representations, 2024.
Nick Littlestone and Manfred Warmuth. The weighted majority algorithm. Information and computation, 108(2):212-2)) 261, 1994.
Hao Liu, Carmelo Sferrazza, and Pieter Abbeel. Chain of hindsight aligns language models with feedback. arXiv preprint arXiv:2302.026777 2202.02676, 3, 2023a.
Junling Liu, Chao Liu, Peilin Zhou, Renjie Lv, Kang Zhou, and Yan Zhang. Is chatgpt a good recommender? preliminary study. arXiv preprint wxXv:2304.10019, 2023b.
Yang Liu, Dan Iter, Yichong Xu, Shuohang Wang, Ruochen Xu, and Chenguang Zhu, G-eval: Nlg evaluation using gpt-4 with better human alignment. arXiv preprint arXiv:2303. 16634, 2023c.
Yueyang Liu, Benjamin Van Roy, and Kuang Xu. Nonstationary bandit learning via predictive sampling. In International Conference on Artificial Intelligence and Statistics, pp. 6215-6244.
PMLR, 2023d.
Zhihan Liu, Hao Hu, Shenao Zhang, Hongyi Guo, Shuqi Ke, Boyi Liu, and Zhaoran Wang. Reason for future, act for now: A principled architecture for autonomous Ilm agents. In NeurIPS 2023 Foundation Models for Decision Making Workshop, 2023c.
LLM Engine. LLM Engine, 2023. URL http:: / /ttp///lmmmm. 1ell1mmeenn -im---nniinee ne. sca le com.
Nunzio Lorè and Babak Heydari. Strategic behavior of large language models: Game structure vs. contextual framing. arXiv preprint arXiv:2309.05898 2023.
Arvind Mahankali, Tatsunori B Hashimoto, and Tengyu Ma. One step of gradient descent is provably the optimal in in-context learner with one layer of linear self-attention. International Conference Learning Representations, 2023.
Weichao Mao, Kaiging Zhang, Ruihao Zhu, David Simchi-Levi, and Tamer Başar. Model-free non-stationary RL: Near-optimal regret and applications in multi-agent RL and inventory control. arXiv preprint arXiv:2010.0316,, 2020.
Daniel I. McFadden. Quantal choice analaysis: A survey. Annals of Economic and Social Measure- ment, Volume 5, number 4, pp. 363-390, 1976.
Richard D McKelvey and Thomas R Palfrey. Quantal response equilibria for normal form games. Games and economic behavior, 10(1):6-38, 1995.
15

---

Published as a conference paper at ICLR 2025
Sewon Min, Xinxi Lyu, Ari Holtzman, Mikel Artetxe, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer. Rethinking the role of demonstrations: What makes in-context learning work? In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang (eds.). Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pp. 11048- 1064, Abu Dhabi, United Arab Emirates, December 2022. Association for Computational Linguistics. doi: 10.18653/v1/ 2022.emnlp-main.755 URL https: hataa/aaaannttooooooooo org//022/ emnlp main. 759.
Gabriel Mukobi, Hannah Erlebach, Niklas Lauffer, Lewis Hammond, Alan Chan, and Jesse Clifton. Welfare diplomacy: Benchmarking language model cooperation. arXiv preprint arXiv:2310.08901, 2023.
Denis Nekipelov, Vasilis Syrgkanis, and Eva Tardos. Econometrics for learning agents. In ACM Conference on Economics and Computation, pp. 1-18, 2015.
Openai. Gpt-4 technical report. 2023.
Ian Osband, Daniel Russo, and Benjamin Van Roy. (more) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013.
Joon Sung Park, Lindsay Popowski, Carrie Cai, Meredith Ringel Morris, Percy Liang, and Michael S Bernstein. Social simulacra: Creating populated prototypes for social computing systems. In Proceedings of the 35th Annual ACM Symposium on User Interface Software and Technology, pp- 1-18, 2022.
Joon Sung Park, Joseph O'Brien, Carrie Jun Cai, Meredith Ringel Morris, Percy Liang, and Michael S. Bernstein. Generative agents:
Interactive simulacra of human behavior. In Proceed- ings of the 36th Annual ACM Symposium on User Interface Software and Technology, UIST '23, New York, NY, USA, 2023. Association for Computing Machinery. ISBN 9798400701320. doi: 011145//5861833366670
URL https::////... /oo.. org/10..//... 11111111//11133111311 3606766...
Chen Qian, Xin Cong, Cheng Yang. Weize Chen, Yusheng Su, Juyuan Xu, Zhiyuan Liu, and Maosong Sun. Communicative agents for software development. arXiv preprint arXiv:2307.07924, 2023.
Scott Reed, Konrad Zolna, Emilio Parisotto, Sergio Gómez Colmenarejo, Alexander Novikov, Gabriel Barth-maron, Mai Giménez, Yury Sulsky, Jackie Kay, Tobias Springenberg, Tom Ec- cles, Jake Bruce, Ali Razavi, Ashley Edwards, Nicolas Heess, Yutian Chen, Raia Hadsell, Oriol Vinyals, Mahyar Bordbar, and Nando de Freitas. A generalist agent. Transactions Machine Learning Research, 2022. ISSN 2835-8856. URL https: htttts:://opereeee/ http///pperrveiieeeeeeeee net forum? id=1i id=likKOkHjvz Featured Certification, Outstanding Certification.
David Robinson and David Goforth. The topology of the 2x2 games: a new periodic table, volume 3. Psychology Press, 2005.
Tim Roughgarden. Intrinsic robustness of the price of anarchy. Journal of the ACM (JACM), 62(5):
1-42, 2015.
Timo Schick, Jane Dwivedi- Yu, Zhengbao Jiang, Fabio Petroni, Patrick Lewis, Gautier Izacard, Qingfei You, Christoforos Nalmpantis, Edouard Grave, and Sebastian Riedel. Peer: A collabora- tive language model. International Conference on Learning Representations, 2023.
Shai Shalev-Shward Online learning: Theory, algorithms, and applications. Hebrew University, 2007.
Shai Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine Learning, 4(2):107-194, 2012.
Shai Shalev-Shwartz and Yoram Singer. A primal-dual perspective of online learning algorithms. Machine Learning, 69: 142, 2007.
Yongliang Shen, Kaitao Song, Xu Tan, Dongsheng Li, Weiming Lu, and Yueting Zhuang. Hugging- gpt: Solving AI tasks with chatgpt and its friends huggingface. Neural Information Processing Systems, 2023.
16

---

Published as a conference paper at ICLR 2025
Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik R Narasimhan, and Shunyu Yao. Re- flexion: Language agents with verbal reinforcement learning. In Thirty-sevnnth Conference on Neural Information Processing Systems, 2023.
Significant Gravitas.
Autogpt. 2023.
URL https://githhi com/
Significant- Setiti--aavttttsAaaaaaa
Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. Transactions Machine Learning Research, 2023.
Melanie Swan, Takashi Kido, Eric Roland, and Renato dos Santos. Math agents: Computational infrastructure, mathematical embedding, and genomies. arXiv preprint arXiv:2307.02502, 2023.
Chen Feng Tsai, Xiaochen Zhou, Sierra S Liu, Jing Li, Mo Yu, and Hongyuan Mei. Can large language models play text games well? current state-of-the-art and open questions. arXiv preprini arXiv:2304.02868, 2023.
Karthik Valmeekam, Matthew Marquez, Alberto Olmo, Sarath Sreedharan, and Subbarao Kamb- hampati. 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, 2023.
Aad W Van der Vaart. Asymptotic statistics, volume Cambridge university press, 2000.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural informa- fion processing systems, 30, 2017.
Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordy- intsev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient descent. International Conference on Machine Learning, pp. 35151-35174 PMLR, 2023.
Volodimir G Vovk. Aggregating strategies. In Proceedings of the third Annual Workshop on Com-
putational Learning Theory, pp. 371-386, 1990.
Martin J Wainwright. High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cam- bridge university press, 2019.
Guanzhi Wang, Yugi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar. Voyager: An open-ended embodied agent with large language models. arXiv preprint arXiv:2305.1629) 2023a.
Xinyi Wang, Wanrong Zhu, and William Yang Wang. Large language models are implicitly topic models: Explaining and finding good demonstrations for in-context learning. International Con- ference on Machine Leurning 2023 Workshop ES-FoMO, 2023b.
Yancheng Wang. Ziyan Jiang, Zheng Chen, Fan Yang, Yingxue Zhou, Eunah Cho, Xing Fan, Xiao- jiang Huang, Yanbin Lu, and Yingzhen Yang. Recmind: Large language model powered agent for recommendation. arXiv preprint arXiv:2308.1 14296,2266666 2023c.
Zihao Wang, Shaofei Cai, Anji Liu, Xiaojian Ma. and Yitao Liang. Describe, explain, plan and select: Interactive planning with large language models enables open- spen-world multi-task agents. Advances in neural information processing systems, 2023d.
Chen- Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach. In Conference on learning theory, pp. 4300-4354. PMLR, 2021.
Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yo- gatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al. Emergent abilities of large language models. Transactions on Machine Learning Research, 2022a.
17

---

Published as a conference paper at ICLR 2025
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe V Le, Denny Zhou, et al. thain-of-thoughtt prompting elicits reasoning in large language models. Advances in Neural Information Processing Systems, 35:24824- 24837, 2022b.
Likang Wu, Zhi Zheng, Zhaopeng Qiu, Hao Wang, Hongchao Gu, Tingjia Shen, Chuan Qin, Chen Zhu, Hengshu Zhu, Qi Liu, Hui Xiong, and Enhong Chen. survey on large language models for recommendation, 2024a. URL https: www.v. www.aasa0000 19860.
Qingyun Wu, Gagan Bansal, Jieyu Zhang, Yiran Wu, Shaokun Zhang, Erkang Zhu, Beibin Li,
Li Jiang, Xiaoyun Zhang, and Chi Wang. Autogen: Enabling next-gen Ilm applications via multi- agent conversation framework. arXiv preprint arXiv:2308.081 155, 2023.
Yue Wu, Xuan Tang, Tom Mitchell, and Yuanzhi Li. Smartplay: A benchmark for Ilms as intelligent agents. In The Twelfth International Conference on Learning Representations, 2024b.
Fanzeng Xia, Hao Liu, Yisong Yue, and Tongxin Li. Beyond numeric awards: In-context ducling bandits with Ilm agents. arXiv preprint arXiv:2407.01887, 2024.
Sang Michael Xie, Aditi Raghunathan, Percy Liang, and Tengyu Ma. An explanation of in-context learning implicit bayesian inference. International Conference on Learning Representations, 2022.
Kai Xiong, Xiao Ding, Yixin Cao, Ting Liu, and Bing Qin. Examining inter-consistency of large language models collaboration: An in-depth analysis via debate. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Findings of the Association for Computational Linguistics: EMNLP 2023, pp. 7572-7590, Singapore, December 2023. Association for Computational Linguistics. doi: 10. 10011863//112023 1tt.:://111222...nnnnnmmmmmm finings-emmll.500. URL findings- emn p.508.
orgg/023.
Yuzhuang Xu, Shuo Wang, Peng Li, Fuwen Luo, Xiaolong Wang, Weidong Liu, and Yang Liu. Exploring large language models for communication games: An empirical study on werewolf. arXiv preprint wrXiv:2309.04655 2023a.
Zelai Xu, Chao Yu, Fei Fang, Yu Wang, and Yi Wu. Language agents with reinforcement learning for strategic play in the werewolf game. arXiv preprint arXiv:2310.1880 2023b.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Thomas L Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 2023a.
Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du Izhak Shafran, Karthik Narasimhan, and Yuan Cao. React: Synergizing reasoning and acting in language models. International Conference on Learn- ing Representations, 2023b.
H Peyton Young. Strategic learning and its limits. OUP Oxford, 2004.
Hongxin Zhang, Weihua Du, Jiaming Shan, Qinhong Zhou, Yilun Du, Joshua B Tenenbaum, Tian- min Shu, and Chuang Gan. Building cooperative embodied agents modularly with large language models. International Conference on Learning Representations, 2024.
Ruiqi Zhang, Spencer Frei, and Peter L Bartlett. Trained transformers learn linear models in-context. arXiv preprini arXiv:2306.0999 09927, 2023a.
Yufeng Zhang, Fengzhuo Zhang, Zhuoran Yang, and Zhaoran Wang. What and how does in-context learning learn? bayesian model averaging, parameterization, and generalization. arXiv preprint 2wX5::2305.19420, 2023b.
Qinlin Zhao, Jindong Wang, Yixuan Zhang, Yiqiao Jin, Kaijie Zhu, Hao Chen, and Xing Xie. Com- peteai: Understanding the competition behaviors in large language model-based agents. arXiv preprint arXiv:2310.17512 2023.
Julian Zimmert and Yevgeny Seldin. Tsallis-inf: An optimal algorithm for stochastic and adversarial bandits. The Journal of Machine Learning Research, 22(1):1310-133 2021.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In International Conference Machine Learning, pp. 928 928-936,720 2003.
18

---

Published as a conference paper at ICLR 2025
Supplementary Materials for "Do LLM Agents Have Regret? A Case Study in Online Learning and Games"
CONTENTS
Introduction
2 Preliminaries
2.1 Online Learning & Games
2.2 Performance Metric: Regret
3 Do Pre-Trained LLMs Have Regret? Experimental Validation
3.1 Framework for Sublinear Regret Behavior Validation
3.2 Results: Online Learning
3.3 Results: Multi-Player Repeated Games
3.4
Pre-Trained LLM Agents Can Still Have Regret
6
4 Why Do Tre-Trained LLMs (Not) Have Regret? A Hypothetical Model and Some The- oretical Insights
4.1
A (Human) Docision-Making Model: Quantal Response
4.2
Case Study; Pre-Training under Canonical Data Distribution
5
Provably Promoting No-Regret Behavior by a New Loss
5.1
A New Unsupervised Training Loss: Regret-Loss
5.2
Generalization and Regret Guarantees of Regret-Loss Minimization
10
5.3
Regret-Loss Trained Transformers Can be Online Leaminng Algorithms
10
5.4
Experimental Results for Regret-Loss Trained Transformers
10
A Related Work
22
A.I Comparison with Concurrent Work Krishnamurthy al. (2024)
23
Deferred Background
25
B.1 Notation
25
B.2 Additional Definitions
26
B.3
In-Context Learning
26
................................
B.4 Online Learning Algorithms
................................
26
B.5 Why Focusing on Linear Loss Function?
28
B.6 Six Representative General-Sum Games
28
Deferred Results and Proofs in Section 3
29
C.1 Intuition Why Pre- Tee-Trained Language Models Might Exhibit No-Regret Behavior
29
19

---

Published as a conference paper at ICLR 2025
C.2 Visualization of Interaction Protocols
29
C.3 Frameworks for No-Regret Behavior Validation
29
C.4 Deferred Experiments for Non-stationary Environments in Section 3.2
31
C.5 Deferred Experiments for Bandit-feedback Environments in Section 3.2
32
C.6 Additional Figures for Section 3.3
33
C.7 Additional Results for Section 3.4
34
C.8 Ablation Study on the Prompt
35
C.9 Results for GPT-4 Turbo
38
C.10 LLM Agents' Explanation on Their Output Policies
C.11 Case Studies Real-world Applications
C.11.1 Sequential Recommendation
40
C.11.2 Interactive Negotiation
40
Deferred Results and Proofs in Section 4
43
D.I Pre-Trained LLMs Have Similar Regret as Humans (Who Generate Data)
43
D.2 Background and Motivations for (Generalized) Quantal Response
44
D.3 The Example Instantiating Assumption
D.4
Aligmment of Assumption I with Quantal Response
45
D.5
Relationship between FTPL and Definition 4.1
46
D.6
Formal Statement and Proof of Theorem 4.1
46
D.6.1 Implications of Theorem 4.1 for Repeated Games
50
D.7 Extending Theorem 4.1 with Relaxed Assumptions
50
D.7.1 Relaxation under More General Data Distributions
50
D.7.2 Relaxation under Decision-Irrelevan Pre-Training Data
52
D.8 Comparison with Lee al. (2023); Lin et al. (2024); Liu et al. (2023e)
52
D.9 Details of Estimating the Parameters of Our Hypothetical Model
53
E
Deferred Results and Proofs in Section 5
53
E.1
Basic Lemmas
E.2 Deferred Proof for the Arguments in Section 5.1
53
E.3
Definition of the Empirical Loss Function
58
E.4
Deferred Proofs of Theorem E.1 and Theorem 5.1
58
E.5
Detailed Explanation of Optimizing Equation (5.2) with Single-layer Self-attention Model
62
E.6
Deferred Proof of Theorem E.2
62
E.7
Deferred Proof of Theorem 5.2
65
E.8
Empirical Validation of Theorem E.2 and Theorem 5.2
70
E.8.1
Empirical Validation of Theorem E.2
70
E.8.2
Empirical Validation of Theorem 5.2.
70
20

---

Published as a conference paper at ICLR 2025
E.9
Discussions the Production of FTRL with Entropy Regularization
70
E.9.1
Numerical Analysis of Step 2 and Step
74
E.9.2
Empirical Validation
75
E.10
Comparison with In-Contett-Learning Analyses in Supervised Learning
75
E.11
Details of Section 5.4
75
E.11.1 Training Details of Section 5.4
78
E,12 Ablation Study on Training Equation (5.2)..
78
Limitations and Concluding Remarks
21


Reviews:
[{"review_id": "SxSqqWT1eR", "reviewer": "Reviewer_qXHf", "summary": "This paper studies large language models from a game-theoretic perspective. Observing that LLM-agents are becoming prevalent, they investigate the performance of such LLM agents in terms of regret.\n\nEmpirical findings include:\n\n- LLMs exhibit sublinear regret in certain online learning problems\n- equilibria emerge when LLM agents interact through repeated games\n\nThe authors also develop theory that is consistent with the empirical observations. Finally, the authors propose a new loss function tailored towards regret minimization. They study models optimized under this loss function both theoretically and empirically.", "questions": "The authors study instruction-tuned models. These typically undergo multiple training stages: a pre-training stage consisting of next-token prediction, and multiple fine-tuning stages that align models with desired behavior.\n\nHave the authors considered comparing the behavior of LLMs at various stages of the training process? This question strikes me as relevant in the context of the discussion in Section 4.2, which makes assumption on the pre-training stage specifically.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- Given the amount of information conveyed, overall the paper is relatively well written, with a sound structure that helps guiding the reader through the large number of findings.\n- The contributions appear to be quite substantial. Not being a domain expert, I cannot make a confident judgment as to originality and significance.\n- There is a good combination of theory and experiments. The experiments are comprehensive, and the theory appears to be relevant & meaningfully complement the empirical findings.", "weaknesses": "- There is a case to be made that the authors are trying to describe too many findings in the main paper. Some figures are hard to read (Figure 3 is a good example of this). The paper ends rather abruptly, with what is essentially a list of pointers to the supplementary material. It appears to me that the layout is deliberately compressed to gain space (e.g., page 10: space above header of Sec. 5.4, space around Eq. 5.3, math fontsize in Thm 5.1).\n    - I am genuinely impressed by how comprehensive the study is (there are 77 pages when including the supplementary material). However, I think the main text would benefit from being simplified by omitting certain results. Remember that this is a conference submission with limited space.\n    - Again, _conditioned on the set of results presented in the main text_, I don't see many opportunities to improve the organization and presentation, which I find rather good.\n- Proposition 1 is problematic. As far as I understand, this proposition rests on an unwritten assumption that the indicators for _difference of regrets is > 0_ are independent. I don't see why this would hold?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Q7yo3ueBcd", "reviewer": "Reviewer_d5nu", "summary": "The authors investigate whether LLMs can exhibit no-regret behavior in online learning scenarios. Their main contributions include:\n\n- **Empirical Validation:** The authors empirically show that both commercial and open-source LLMs can achieve no-regret learning in various environments, including dynamic settings and multi-agent games. They demonstrate that LLMs often outperform traditional no-regret algorithms like FTRL and FTPL, with the models effectively incorporating randomization in decision-making.\n- **Limitations in Adversarial Scenarios:** The study identifies cases where advanced LLMs, such as GPT models, struggle to achieve sublinear regret, particularly in highly adaptive or adversarial environments. \n- **Theoretical Insights and Enhancements:** The authors provide a theoretical framework explaining how next-token prediction during pretraining enables LLMs to develop capabilities aligned with no-regret algorithms. They also introduce a novel \"regret-loss\" training objective designed to further strengthen the no-regret properties of LLMs, even in the absence of optimal action labels.", "questions": "1. Could the authors clarify the use of the term \"no-regret\" in this context?\n2. In structured, non-adversarial environments (such as linear or sine-trend losses), GPT-4 appears to outperform traditional no-regret algorithms like FTRL/FTPL. Does this suggest that the model may be doing more than no-regret learning, possibly adapting to or fitting the specific trends in the loss sequences through in-context learning?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The strengths of the paper include: \n\n- **Comprehensive Empirical Analysis:** The authors conduct a thorough empirical study across diverse environment setups and various LLM models. They evaluate LLM performance in both standard online learning scenarios and multi-agent games, identifying cases where LLMs exhibit no-regret behaviors and outperform classical algorithms like FTRL and FTPL. Importantly, the authors also examine situations where LLMs, such as GPT, fail to achieve sublinear regret in highly adaptive or adversarial environments. This balanced examination provides valuable insights into the conditions under which LLMs succeed or struggle, helping us better understand the decision-making processes and strategic adaptations LLMs employ in online game contexts. \n\n- **Conduct Ablation Study:** The authors conduct an ablation study to systematically examine the contributions of various components in their proposed framework.\n\n- **Theoretical Justification for No-Regret Behaviors:** The authors offer a theoretical explanation on how next-token prediction pretraining enables LLMs to develop no-regret behaviors in online learning. Under certain structured noise assumption, the optimal behaviors of the LLM under the next-token prediction loss can be related to FTPL.\n\n- The no-regret loss seems to be novel, and enhances the model's performance.", "weaknesses": "I found the following weakness points: \n\n- **Ambiguity in No-Regret Definition and Experimental Setup:** The standard definition of \"no-regret\" in online learning typically requires that an algorithm achieves sublinear regret for all possible loss sequences, including adversarial ones. However, the authors claim that the LLM behaves as a no-regret algorithm based primarily on experiments involving uniform or Gaussian losses and losses with specific trends, which are not adversarial. This raises some confusion, as these setups do not fully reflect the robustness expected in no-regret algorithms. In fact, the experiments on the \"Adaptive loss sequence\" seem more directly relevant to evaluating this claim.\n\n- **Lack of Explanation for Model Performance:** Following the previous point, while the authors show that the LLM outperforms traditional no-regret algorithms like FTRL and FTPL, there is limited insight into why this occurs. For instance, the model may be learning the underlying distribution of the loss or fitting specific loss trends, but this is not explicitly demonstrated. Additional analysis on how GPT models achieve superior performance would provide a more comprehensive understanding of these results.\n\n- **Theoretical Limitation**: In Theorem 5.2, you only show the results for $N=1$. If my understanding is correct, this basically means that there is no maximum taken across the input loss sequence $\\ell_{1:t}$. Is this also the setup for training the single/multi-layer transformer model under the noisy alternating/adaptive loss as you show in Figure 3.4, or did you use larger $N$ to produce the results? I didn't find the experiment setup for these results in Figure 3.4.\n\n- Building on the previous point, there is one minor thing. I feel that Theorem 4.1 may not fully capture the behavior of LLMs. The empirical results show that GPT models outperform standard no-regret algorithms in more structured tasks but perform significantly worse in adversarial settings. However, what this theorem suggests is that the model after pretraining performs something similar to FTPL. This discrepancy suggests that the theoretical framework might not align with the model's observed strengths and weaknesses across different environments.\n\nHowever, I still find the contributions to be significant. Hence, I'm open to raising my scores upon the concerns being addressed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jAmIf7sSlk", "reviewer": "Reviewer_Q6rC", "summary": "The paper discusses the use of LLMs for decision-making in both single and multi-agent settings. Their study focuses on understanding the limitations of LLM agents in interactive environments by using regret as a performance metric. Initial empirical investigations assess no-regret behaviors in non-stochastic online learning and the emergence of equilibria in repeated game scenarios. The paper provides theoretical insights into these behaviors based on assumptions about the data’s origin and the rationality of human decision-makers involved in pre-training.", "questions": "1. When using GPT4 Turbo and GPT o1 for online decision-making, could the assumption on optimal action labels be relaxed?\n\n2. Why is the regret performance of GPT4 better than single/multi-layer models in the single agent setting, yet vice versa in the multi-agent setting? What factors contribute to this discrepancy in its effectiveness across different settings?\n\n3. What is the technical challenge in the proof of Theorem 5.2? If the result goes beyond simply applying standard learning theory arguments, it's worth highlighting the proof techniques used or created.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "1. The paper explores an interesting aspect of using LLM in decision-making tasks. Experimental results are provided.\n\n2. It is interesting that Theorem 5.2 shows a single-layer (linear) self-attention transformer is enough to model no-regret learning algorithms.\n\n3. The paper provides an extensive appendix. The appendix is rich with additional proofs, experimental details, and supplementary discussions. I didn't read all the experimental results and proofs.", "weaknesses": "1. It seems not that natural to apply LLMs to solve online decision-making problems, given the existence of classic and well-established algorithms. What are the potential applications? The paper needs to be better motivated to help readers understand the contributions. While the application of LLMs in online decision-making presents intriguing possibilities, the practical implications are not immediately clear. To better engage readers and clarify the significance of this research, the paper could benefit from a more compelling motivation. Specifically, detailing potential real-world applications and explicitly connecting these to the experimental findings would enhance the paper’s relevance and impact.\n\nIt's worth considering providing specific examples of potential real-world applications where using LLMs for online decision-making could offer advantages over classical algorithms such as FTPL.\n\n2. The paper does not address the capabilities of state-of-the-art LLM APIs like GPT4 Turbo and o1. Discussing their performance might also offer valuable insights into the scalability and applicability of the proposed methods to more complex decision-making tasks. More detailed analysis of this discrepancy are needed.\n\n\n\nOverall, I'd like to raise my score if case studies on real-world application can be provided, with both GPT-4 Turbo and o1 evaluated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "RpdQ5qBnCu", "reviewer": "Reviewer_KLuz", "summary": "This paper investigates the performance of llm agents in online learning and game-theoretic scenarios. It empirically evaluates no-regret behaviors in pre-trained LLMs like GPT-4 across various online learning settings and repeated games, comparing them with classical no-regret algorithms. The authors introduce a new unsupervised training loss called \"regret-loss,\" designed to enhance no-regret behavior without requiring action labels. It provides theoretical insights connecting pre-training to no-regret algorithms, and presents experimental results validating the proposed approaches.", "questions": "1. How sensitive are the findings to the choice of synthetic games (win-win, prisoner’s dilemma, unfair, cyclic, biased, and second best) used for experiments?\n2. How do the authors validate the importance of the research problem:\n    \n    \"Can we examine and better understand the online and strategic decision-making behaviors of LLMs through the lens of regret\"?\n\n    The theoretical results, while rigorous, may feel detached from practical applications. The paper's findings on regret behavior might not translate into concrete benefits for LLM-based systems in the real world, potentially rendering the problem it addresses less relevant. This could make the work feel more like a theoretical exercise than a practical contribution to improving LLM capabilities.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. It offers a theoretical framework for understanding no-regret behaviors in LLMs and introduces a novel training objective (regret-loss) with provable guarantees.\n2. It includes a wide range of experiments with different synthetic & toy-case settings (arbitrary, non-stationary, and bandit feedback environments), comparing LLMs with established no-regret algorithms.", "weaknesses": "1. Misalignment of Framework and Problem: The application of online learning and game theory to evaluate LLM agents seems like over-engineering. LLMs are not explicitly designed for decision-making in the classical sense that these fields address (e.g., making repeated decisions based on feedback from an adversarial environment). Using regret minimization as a benchmark for LLM behavior could be seen as an attempt to impose a theoretical construct that may not provide meaningful insights into the actual strengths and weaknesses of LLMs.\n2. Lack of Practical Relevance: If the focus is on understanding LLMs' interactive capabilities, other evaluation metrics might be more meaningful. For instance, metrics derived from natural language understanding or task-specific performance might offer more concrete insights into how LLMs perform as interactive agents. The notion of regret, which is central to online learning and game theory, may not be as intuitive or impactful in the context of LLMs used for dialogue, or other applications. There could be alternative frameworks that align better with evaluating and enhancing LLMs. For example, reinforcement learning, interactive learning environments, or even human-in-the-loop evaluations might offer more practical insights than regret-based analysis.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)