Specifically, for the general convex loss function $(f_{t})_{t\in[T]}$, we
have $f_{t}(\pi_{\mathscr{A},t})-f_{t}(\pi)\leq\langle\nabla
f_{t}(\pi_{\mathscr{A},t}),\pi_{\mathscr{A},t}-\pi\rangle$ for any
$\pi\in\Pi$, which indicates

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

Therefore, one can regard the loss vector $({\ell}_{t})_{t\in[T]}$ as
${\ell}_{t}:=\nabla f_{t}(\pi_{\mathscr{A},t})$ for $t\in[T]$, and control the
actual regret by studying the linear loss function (Hazan, 2016). The same
argument on the general convex $f_{t}$ can be applied to the dynamic-regret
metric as well. In sum, an algorithm designed for online _linear_ optimization
can be adapted to solve online _convex_ optimization, with the understanding
that the instance received at round $t$ corresponds to the gradient of the
convex function evaluated at the policy at that round.

###  A.5 Six Representative General-Sum Games

In game theory, there are six representative two-player general-sum games
(Robinson and Goforth, 2005). Firstly, consider the win-win game represented
by matrices $A=\begin{pmatrix}1&4\\\ 1&2\end{pmatrix}$ and
$B=\begin{pmatrix}1&4\\\ 1&2\end{pmatrix}$ for players A and B, respectively.
This setup fosters a cooperative dynamic, as both players receive identical
payoffs, encouraging strategies that benefit both parties equally.

In contrast, the prisoner’s dilemma, depicted by payoff matrices
$A=\begin{pmatrix}1&3\\\ 2&4\end{pmatrix}$ and $B=\begin{pmatrix}4&3\\\
2&1\end{pmatrix}$, illustrates the conflict between individual and collective
rationality, where players are tempted to pursue individual gain at the
collective’s expense, often resulting in suboptimal outcomes for both.

In the unfair game, represented by $A=\begin{pmatrix}2&1\\\ 3&4\end{pmatrix}$
and $B=\begin{pmatrix}4&3\\\ 1&2\end{pmatrix}$, the asymmetry in the payoff
structure places one player at a disadvantage, regardless of the chosen
strategy. This imbalance often reflects real-world scenarios where power or
information asymmetry affects decision-making.

The cyclic game, with matrices $A=\begin{pmatrix}3&1\\\ 2&4\end{pmatrix}$ and
$B=\begin{pmatrix}3&4\\\ 2&1\end{pmatrix}$, presents a scenario where no
stable equilibrium exists. The best strategy for each player changes in
response to the other’s actions, leading to a continuous cycle of strategy
adaptation without a clear resolution.

The biased game, depicted by $A=\begin{pmatrix}3&2\\\ 1&4\end{pmatrix}$ and
$B=\begin{pmatrix}4&2\\\ 1&3\end{pmatrix}$, inherently favors one player,
often reflecting situations where external factors or inherent advantages
influence outcomes, leading to consistently unequal payoffs.

Finally, the second-best game, with payoff matrices $A=\begin{pmatrix}1&2\\\
3&4\end{pmatrix}$ and $B=\begin{pmatrix}1&4\\\ 3&2\end{pmatrix}$, encapsulates
scenarios where players settle for less-than-optimal outcomes due to
constraints like risk aversion or limited options. This often results in
players choosing safer, albeit less rewarding, strategies.

Each of these games exemplifies distinct aspects of strategic decision-making
and interactions. From cooperative to competitive and fair to biased
scenarios, these matrices provide a rich landscape for exploring the nuances
of decision-making behavior in game theory.

##  Appendix B Deferred Results and Proofs in Section 3

###  B.1 Ablation Study on Prompts

##### Ablation study on online learning.

To systematically understand the effects of our prompt on the final
performance of the LLM agent, we create three different variants of our prompt
and report the regret by using different prompts in Figure 12. Specifically,
for Ablation1, we remove examples to illustrate the game rules. For Ablation2,
we remove the number of iterations. For Ablation3, we incorporate some _hints_
for the LLM for decision-making, including the hints to suggest it to pay
attention to the loss history, to behave more greedily at the end of an
episode, and also to explain the reason of its decision step-by-step. The
latter hint is a popular technique in prompt engineering known as the _Chain-
of-Thought_ prompting (Wei et al., 2022b). Finally, we recall that $d$ is the
number of actions in all prompts.

Figure 12: Ablation study on our prompt design.

Original prompt

You are solving a decision-making problem for 25 rounds.

There are $d$ number of action (which is 0 to $d-1$).

At each round, you need to choose a policy, it specifies your probability to
choose each action.

This policy should be $d$-dimensional, and the sum of its components should
equal 1.

After that, you will be shown the reward vector for choosing each action.

Remember that this reward vector is decided by the external system and can be
potentially

different for different rounds.

It is not decided by what policies you have chosen. The reward vector is also
$d$-dimensional.

It represents the reward of choosing action from 0 to $d-1$.

For example, a reward vector of [0.8, 3.2] means reward for action_0 is 0.8

and the reward for action_1 is 3.2.

Then your reward for this round will be calculated according to the reward of
each action and

your probability of choosing each action.

For example, if you choose the policy [0.2, 0.8] and get the reward vector [1,
2],

then your expected reward is 0.2*1 + 0.8*2=1.8

Your goal is to maximize your accumulative expected reward.

You can adjust your policy based on the reward vectors for all previous
rounds.

You’re required to provide your policy in numeric format.

Your response’s last line should be formatted as ’Policy: [your
$d$-dimensional policy]’.

Ablation1: no examples

You are solving a decision-making problem for 25 rounds.

There are $d$ number of action (which is 0 to $d-1$).

At each round, you need to choose a policy, it specifies your probability to
choose each action.

This policy should be $d$-dimensional, and the sum of its components should
equal 1.

After that, you will be shown the reward vector for choosing each action.

Remember that this reward vector is decided by the external system and can be
potentially

different for different rounds.

It is not decided by what policies you have chosen. The reward vector is also
$d$-dimensional.

It represents the reward of choosing action from 0 to $d-1$.

Then your reward for this round will be calculated according to the reward of
each action and

your probability of choosing each action.

Your goal is to maximize your accumulative expected reward.

You can adjust your policy based on the reward vectors for all previous
rounds.

You’re required to provide your policy in numeric format.

Your response’s last line should be formatted as ’Policy: [your
$d$-dimensional policy]’.

Ablation2: no round information

You are solving a decision-making problem.

There are $d$ number of action (which is 0 to $d-1$).

At each round, you need to choose a policy, it specifies your probability to
choose each action.

This policy should be $d$-dimensional, and the sum of its components should
equal 1.

After that, you will be shown the reward vector for choosing each action.

Remember that this reward vector is decided by the external system and can be
potentially

different for different rounds.

It is not decided by what policies you have chosen. The reward vector is also
$d$-dimensional.

It represents the reward of choosing action from 0 to $d-1$.

For example, a reward vector of [0.8, 3.2] means reward for action_0 is 0.8

and the reward for action_1 is 3.2.

Then your reward for this round will be calculated according to the reward of
each action and

your probability of choosing each action.

For example, if you choose the policy [0.2, 0.8] and get the reward vector [1,
2],

then your expected reward is 0.2*1 + 0.8*2=1.8

Your goal is to maximize your accumulative expected reward.

You can adjust your policy based on the reward vectors for all previous
rounds.

You’re required to provide your policy in numeric format.

Your response’s last line should be formatted as ’Policy: [your
$d$-dimensional policy]’.

Ablation3: adding hints

You are solving a decision-making problem for 25 rounds.

There are $d$ number of action (which is 0 to $d-1$).

At each round, you need to choose a policy, it specifies your probability to
choose each action.

This policy should be $d$-dimensional, and the sum of its components should
equal 1.

After that, you will be shown the reward vector for choosing each action.

Remember that this reward vector is decided by the external system and can be
potentially

different for different rounds.

It is not decided by what policies you have chosen. The reward vector is also
$d$-dimensional.

It represents the reward of choosing action from 0 to $d-1$.

For example, a reward vector of [0.8, 3.2] means reward for action_0 is 0.8

and the reward for action_1 is 3.2.

Then your reward for this round will be calculated according to the reward of
each action and

your probability of choosing each action.

For example, if you choose the policy [0.2, 0.8] and get the reward vector [1,
2],

then your expected reward is 0.2*1 + 0.8*2=1.8

Your goal is to maximize your accumulative expected reward.

You can adjust your policy based on the reward vectors for all previous
rounds.

You’re required to provide your policy in numeric format.

Your response’s last line should be formatted as ’Policy: [your
$d$-dimensional policy]’.

Let’s think step by step. Explicitly examining history is important.

Please explain how you chose the policy by guessing what reward you might
receive

for each action according to the history.

You should explore for first several rounds and behave greedily for later
rounds, for example,

choosing one action with probability more than 0.99.

Please also explain whether you are behaving more greedily and less greedily

by explicitly considering the policy you just used for last round.

We can see in Figure 12 that the performances of LLM agents are consistent
under different variants of the prompts.

##### Ablation study on repeated games.

For the game setting, we also investigate whether explicitly informing LLM
agents that they are ‘‘playing a repeated matrix game with some other
opponents’’ would affect the performance. Therefore, we evaluate three
different prompts by informing LLM agents that they are playing a matrix game,
solving multi-arm bandit, or solving general decision-making problems, in the
first line of the prompt. We show the performance of such three prompts in
Figure 13, where it is seen that LLM agents’ performance on repeated games is
consistent among these variants of the prompts.

Figure 13: Regret of GPT-4 for repeated games under $3$ different prompt
ablations. Its performance is consistent among three different prompts.

###  B.2 Proof for Proposition 1

###### Proof.

Under the null hypothesis $H_{0}$, the probability $p$ that
$\text{Regret}_{\mathscr{A}}\left((f_{\tau})_{\tau\in[t]}\right)/t-\text{Regret}_{\mathscr{A}}\left((f_{\tau})_{\tau\in[t+1]}\right)/(t+1)>0$
is less than $\frac{1}{2}$. Therefore, if we consider the event
$\mathcal{E}(s,T)$, we have

$\displaystyle\mathbb{P}_{H_{0}}(\mathcal{E}(s,T))=\sum_{k=s}^{T-1}p^{s}(1-p)^{T-1-s}\begin{pmatrix}T-1\\\
k\end{pmatrix}\leq\frac{1}{2^{T-1}}\sum_{k=s}^{T-1}\begin{pmatrix}T-1\\\
k\end{pmatrix}$

since $s\geq\frac{T-1}{2}$. ∎

###  B.3 Results of GPT-4 Turbo

When preparing our draft, we are aware of a more advanced version of GPT-4,
GPT-4 Turbo. Although GPT-4 has successfully exhibited no-regret behaviors in
most problems, we also evaluate and report the performance of its more
advanced version here. Specifically, we compare GPT-4 and GPT-4 Turbo for the
repeated game scenario in Figure 14, where we validate that GPT-4 Turbo
performs either comparably with or better than GPT-4.

Figure 14: Comparisons of GPT-4 Turbo with GPT-4 and GPT-3.5 Turbo. Due to the
symmetry of agents in randomly generated games, we report the regret of one
agent for ease of presentation. We can see that GPT-4 Turbo performs on par
with or better than GPT-4.

###  B.4 LLM Agents’ Explanation on Their Output Policies

We here present two examples of LLMs’ explanations of their output policies,
showing how they _reason_ in their decision-making.

Output Example 1

Looking at the history of the reward vectors, it is clear to see that the
reward for choosing

action 0 is consistently higher than that for choosing action 1. This pattern
is evident across

all 5 rounds of the game.

In the first round, the difference in rewards is 3.52, this remained
relatively stable with

the difference in the last round being 3.52 as well. It’s indicative that
action 0 consistently

brings a higher return than action 1.

Therefore, I’ll lean more towards selecting action 0 in my policy.

However, acting deterministically, that is always choosing action 0, would
introduce the risk

of becoming too predictable and letting the opponent exploit this
predictability

So, in order to maintain some unpredictability while still capitalizing on the
higher average

return of action 0, I’ll set my policy as follows: select action 0 with a
probability of 0.8

and action 1 with a probability of 0.2.

This way, the majority of the time I’m choosing the action that gives a higher
reward, but I’m

also occasionally choosing the other action to keep the opponent guessing, and
avoid

any predictable patterns that can be exploited

So, my policy is as follows: Policy: [0.8, 0.2]

Output Example 2

The total reward from action_1 is 130.92 and the average reward is around
10.07.

On the other hand, the total reward from action_0 is 33.418 and the average
reward is around 8.354.

Although action_0 has a less average reward, its highest reward is 26.977,

which is considerably high and shows its potential.

For this round, I want to continue to explore action_0 but also significantly
exploit action 1

as it reliably gives higher reward.

So, I’d like to decrease the probability of selecting action_0 compared to
last time

but still keep it in the policy as a possible option.

The policy for the previous round was not provided but assuming it was more
balanced,

I’m now going to lean more towards action_1.

So, the policy will be: [0.3, 0.7]. Here, I’m behaving more greedily compared
to earlier rounds,

as we are choosing the action which has been giving us higher rewards with
more probability.

As observed from the output, the LLM agent tends to use the history of the
reward vectors by looking at the “sum/average of the accumulated rewards”, and
tends to introduce randomization in decision-making, in order to be “less
predictable and exploitable”. These are several key components in achieving
no-regret in online learning and games (Cesa-Bianchi and Lugosi, 2006),
explaining the empirical evidence we had in Section 3.

##  Appendix C Deferred Results and Proofs in Section 4

###  C.1 Deferred Proof of Observation 1

###### Proof of 1.

For given $(\ell_{t})_{t\in[T]}$,

$\displaystyle\sum_{t=1}^{T}\int_{\pi_{t}\in\Pi}P_{\text{LLM}}(\pi_{t}\mid(\ell_{i})_{i\in[t-1]})\langle\ell_{t},\pi_{t}\rangle
d\pi_{t}\leq\sum_{t=1}^{T}\int_{\pi_{t}\in\Pi}\left(P_{\text{data}}(\pi_{t}\mid(\ell_{i})_{i\in[t-1]})+\epsilon\right)\langle\ell_{t},\pi_{t}\rangle
d\pi_{t}$

holds, where we use the convention of
$P_{\text{LLM}}(\pi_{t}\mid(\ell_{0})):=P_{\text{LLM}}(\pi_{t})$ and
$P_{\text{data}}(\pi_{t}\mid(\ell_{0})):=P_{\text{data}}(\pi_{t})$. Hence,

$\displaystyle\text{Regret}_{\text{LLM}}((\ell_{t})_{t\in[T]})$
$\displaystyle=\sum_{t=1}^{T}\int_{\pi_{t}\in\Pi}P_{\text{LLM}}(\pi_{t}\mid(\ell_{i})_{i\in[t-1]})\langle\ell_{t},\pi_{t}\rangle
d\pi_{t}-\inf_{\pi\in\Pi}\sum_{t=1}^{T}\langle\ell_{t},\pi\rangle$
$\displaystyle\leq\sum_{t=1}^{T}\int_{\pi_{t}\in\Pi}\left(P_{\text{data}}(\pi_{t}\mid(\ell_{i})_{i\in[t-1]})+\epsilon\right)\langle\ell_{t},\pi_{t}\rangle
d\pi_{t}-\inf_{\pi\in\Pi}\sum_{t=1}^{T}\langle\ell_{t},\pi\rangle$
$\displaystyle=\sum_{t=1}^{T}\int_{\pi_{t}\in\Pi}\left(P_{\text{data}}(\pi_{t}\mid(\ell_{i})_{i\in[t-1]})\right)\langle\ell_{t},\pi_{t}\rangle
d\pi_{t}-\inf_{\pi\in\Pi}\sum_{t=1}^{T}\langle\ell_{t},\pi\rangle+\sum_{t=1}^{T}\int_{\pi_{t}\in\Pi}\langle\ell_{t},\epsilon\pi_{t}\rangle
d\pi_{t}$
$\displaystyle\leq\text{Regret}_{\text{data}}((\ell_{t})_{t\in[T]})+\epsilon\|\ell\|_{p}\|\pi\|_{q}T$

where $\frac{1}{p}+\frac{1}{q}=1$ and $p,q\geq 1$. Similarly, we can establish
the lower bound for $\text{Regret}_{\text{LLM}}((\ell_{t})_{t\in[T]})$. To
prove the result for the dynamic-regret case, we can simply change the term
$\inf_{\pi\in\Pi}\sum_{t=1}^{T}\langle\ell_{t},\pi\rangle$ in the above
derivation to $\sum_{t=1}^{T}\inf_{\pi\in\Pi}\langle\ell_{t},\pi\rangle$. ∎

###  C.2 Deferred Proof of Lemma 1

See 1

###### Proof.

Note that

$\displaystyle\mathbb{P}(z{\,|\,}x_{1:N_{t}})=\int_{\ell_{1:t}}\mathbb{P}(z,\ell_{1:t}{\,|\,}x_{1:N_{t}})d{\ell_{1:t}}=\int_{\ell_{1:t}}\mathbb{P}(\ell_{1:t}{\,|\,}x_{1:N_{t}})\mathbb{P}(z{\,|\,}x_{1:N_{t}},\ell_{1:t})d\ell_{1:t}.$

For $\mathbb{P}(\ell_{1:t}{\,|\,}x_{1:N_{t}})$, since we have assumed the
existence of function $f$ to decode $\ell_{1:t}$ from $x_{1:N_{t}}$, it holds
that

$\displaystyle\mathbb{P}(\ell_{1:t}{\,|\,}x_{1:N_{t}})=\prod_{i=1}^{t}\delta\left(\ell_{i}-f(x_{N_{i-1}+1:N_{i}})\right),$

where we use $\delta$ to denote the $d$-dimensional Dirac-delta function. For
$\mathbb{P}(z{\,|\,}x_{1:N_{t}},\ell_{1:t})$, by 1, it holds that

$\displaystyle\mathbb{P}(z,x_{1:N_{t}},\ell_{1:t})=\mathbb{P}(z,\ell_{1:t})\mathbb{P}(x_{1:N_{t}}{\,|\,}\ell_{1:t}),$

which leads to
$\mathbb{P}(x_{1:N_{t}}{\,|\,}\ell_{1:t})=\mathbb{P}(x_{1:N_{t}}{\,|\,}\ell_{1:t},z)$
by Bayes rule. This implies that the random variable $x_{1:N_{t}}$ and $z$ are
independent conditioned on $\ell_{1:t}$. Therefore, it holds that
$\mathbb{P}(z{\,|\,}x_{1:N_{t}},\ell_{1:t})=\mathbb{P}(z{\,|\,}\ell_{1:t})$.
Finally, we can compute

$\displaystyle\mathbb{P}(z{\,|\,}x_{1:N_{t}})$
$\displaystyle=\int_{\ell_{1:t}}\mathbb{P}(z,\ell_{1:t}{\,|\,}x_{1:N_{t}})d{\ell_{1:t}}=\int_{\ell_{1:t}}\prod_{i=1}^{t}\delta(\ell_{i}-f(x_{N_{i-1}+1:N_{i}}))\mathbb{P}(z{\,|\,}\ell_{1:t})d\ell_{1:t}$
$\displaystyle=\mathbb{P}\left(z{\,|\,}\left(\ell_{i}=f(x_{N_{i-1}+1:N_{i}})\right)_{i\in[t]}\right).$

Based on this, we conclude that

$\displaystyle\mathbb{P}(g(x_{N_{t}+1:N_{t+1}}){\,|\,}x_{1:N_{t}})$
$\displaystyle=\int_{z}\mathbb{P}(g(x_{N_{t}+1:N_{t+1}}){\,|\,}z,x_{1:N_{t}})\mathbb{P}(z{\,|\,}x_{1:N_{t}})dz$
$\displaystyle=\int_{z}\mathbb{P}(g(x_{N_{t}+1:N_{t+1}}){\,|\,}z)\mathbb{P}(z{\,|\,}\\{\ell_{i}=f(x_{N_{i-1}+1:N_{i}})\\}_{i\in[t]})dz$
$\displaystyle=\mathbb{P}\left(g(x_{N_{t}+1:N_{t+1}}){\,|\,}\left(\ell_{i}=f(x_{N_{i-1}+1:N_{i}})\right)_{i\in[t]}\right)$

where the first equality is by the independence between $x_{N_{t}+1:N_{t+1}}$
and $x_{1:N_{t}}$ conditioned on $z$, due to 1. Therefore, it suffices to
consider the probability of $\mathbb{P}(a{\,|\,}\ell_{1:t})$ only, in order to
analyze $\mathbb{P}(g(x_{N_{t}+1:N_{t+1}}){\,|\,}x_{1:N_{t}})$, where we
recall the definition that $a=g(x_{N_{t}+1:N_{t+1}})$. Since
$z\sim\mathcal{N}(\boldsymbol{0}_{d},\sigma^{2}I)$, and ${\ell}_{i}\mid
z\sim\mathcal{N}(z,\sigma^{2}I)$, we have

$\displaystyle
z\mid\ell_{1:t}\sim\mathcal{N}\left(\frac{1}{t+1}\sum_{i\in[t]}{\ell}_{i},\frac{\sigma^{2}}{t+1}I\right),$
(11)

by the posterior distribution of Gaussian distribution. Now we conclude that

$\displaystyle\mathbb{P}(a{\,|\,}\ell_{1:t})$
$\displaystyle=\int_{z}\mathbb{P}(a{\,|\,}z,\ell_{1:t})\mathbb{P}(z{\,|\,}\ell_{1:t})dz=\int_{z}\mathbb{P}(a{\,|\,}z)\mathbb{P}(z{\,|\,}\ell_{1:t})dz$
$\displaystyle=\int_{z}\mathbbm{1}(a\in\operatorname*{arg\,min}_{a^{\prime}\in\mathcal{A}}z_{a^{\prime}})\mathbb{P}(z{\,|\,}\ell_{1:t})dz=\int_{z}\mathbbm{1}\left(a\in\operatorname*{arg\,min}_{a^{\prime}\in\mathcal{A}}\left(\frac{\sigma}{\sqrt{t+1}}\epsilon+\frac{1}{t+1}\sum_{i\in[t]}\ell_{i}\right)_{a^{\prime}}\right)\mathbb{P}(\epsilon)d\epsilon$
$\displaystyle=\int_{z}\mathbbm{1}\left(a\in\operatorname*{arg\,min}_{a^{\prime}\in\mathcal{A}}\left(\sigma\sqrt{t+1}\epsilon+\sum_{i\in[t]}\ell_{i}\right)_{a^{\prime}}\right)\mathbb{P}(\epsilon)d\epsilon=\mathbb{P}\left(a\in\operatorname*{arg\,min}_{a^{\prime}\in\mathcal{A}}\left(\sigma\sqrt{t+1}\epsilon+\sum_{i\in[t]}\ell_{i}\right)_{a^{\prime}}\right)$
$\displaystyle=P_{quantal}^{\sigma\sqrt{t+1}}(a{\,|\,}\ell_{1:t}),$

where $\mathbb{P}(\epsilon)=\mathcal{N}(\boldsymbol{0}_{d},I)$. This completes
the proof. ∎

###  C.3 Relationship between FTPL and Definition 2

######  Fact 1.

Performing generalized quantal response of Definition 2 at every iteration
$t\in[T]$ w.r.t. history loss vectors $\ell_{1:t-1}$ is essentially executing
an FTPL algorithm.

###### Proof.

Before we move to the proof, we will define the random variable which has
distribution $P_{\text{noise}}$ as $Z_{\text{noise}}$. Note that at round
$t\geq 2$ (as the policy at round $t=1$ is fixed), we have

$\displaystyle
P_{\text{quantal}}^{\eta_{t-1}}(a{\,|\,}\ell_{1:t-1}):=\mathbb{P}\left(a\in\operatorname*{arg\,min}_{a^{\prime}\in\mathcal{A}}~{}\left(\sum_{i=1}^{t-1}{\ell}_{i}+\eta_{t-1}\epsilon\right)(a^{\prime})\right)$
(12)

which is exactly the case when $\epsilon_{t}$ in Equation 10 satisfies
$\epsilon_{t}\overset{d}{=}\eta_{t-1}\epsilon$. ∎

###  C.4 Deferred Proof of Theorem 1

See 1

###### Proof.

Note that

$\displaystyle\max_{\left\\{q_{j}\in\left\\{\mathcal{V}^{j-1}\rightarrow\Delta(\mathcal{V})\right\\}\right\\}_{j\in[N_{t+1}]}}\mathbb{E}_{x_{1:N_{t+1}}\sim
P^{text}_{t}}\sum_{j=1}^{N_{t+1}}\log q_{j}\left(x_{j}{\,|\,}x_{1:j-1}\right)$
$\displaystyle=\max_{q\in\Delta(\mathcal{V}^{N_{t+1}})}\mathbb{E}_{x_{1:N_{t+1}}\sim
P^{text}_{t}}\log q(x_{1:N_{t+1}})$
$\displaystyle=\max_{q\in\Delta(\mathcal{V}^{N_{t+1}})}-\text{KL}(P_{t}^{text}{\,|\,}{\,|\,}q)+\mathbb{E}_{x_{1:N_{t+1}}\sim
P^{text}_{t}}[P_{t}^{text}(x_{1:N_{t+1}})],$

where $\text{KL}(q{\,|\,}{\,|\,}p)$ denotes the Kullback–Leibler divergence
between two distributions $p,q$. Now we define
$\text{LLM}_{\theta}(x_{1:N_{t+1}})=\prod_{t=1}^{N_{t+1}}\text{LLM}_{\theta}(x_{j}{\,|\,}x_{1:j-1})$.
It is easy to verify that
$\text{LLM}_{\theta}(x_{1:N_{t+1}})\in\Delta(\mathcal{V}^{N_{t+1}})$, i.e., it
also defines a valid joint distribution over tokens. Therefore, we have

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

Now, due to our assumption that

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

we conclude that

$\displaystyle\min_{\theta\in\Theta}\text{KL}(P_{t}^{text}{\,|\,}{\,|\,}\text{LLM}_{\theta})=\min_{q\in\Delta(\mathcal{V}^{N_{t+1}})}\text{KL}(P_{t}^{text}{\,|\,}{\,|\,}q)=0,$

which implies that $\text{LLM}_{\theta^{\star}}=P_{t}^{text}$.
Correspondingly, if we define
$\text{LLM}_{\theta^{\star}}(x_{N_{t}+1:N_{t+1}}{\,|\,}x_{1:N_{t}})$ to be the
distribution induced by the joint distribution
$\text{LLM}_{\theta^{\star}}(x_{1:N_{t+1}})$, it holds that

$\displaystyle\text{LLM}_{\theta^{\star}}(x_{N_{t}+1:N_{t+1}}{\,|\,}x_{1:N_{t}})=\mathbb{P}(x_{N_{t}+1:N_{t+1}}{\,|\,}x_{1:N_{t}}).$

In other words, intuitively, $\text{LLM}_{\theta^{\star}}$ has learned the
corresponding _pre-training_ distribution perfectly. Note that this has been a
common assumption in the Bayesian perspective of ICL (Xie et al., 2022; Lee et
al., 2023; Zhang et al., 2023b). Therefore, to analyze the actions taken by
$\text{LLM}_{\theta^{\star}}$, it suffices to consider
$\mathbb{P}(g(x_{N_{t}+1:N_{t+1}}){\,|\,}x_{1:N_{t}})$, which is equal to
$P_{quantal}^{\sigma\sqrt{t+1}}\left(g(x_{N_{t}+1:N_{t+1}}){\,\big{|}\,}\left\\{f(x_{N_{i-1}+1:N_{i}})\right\\}_{i\in[t]}\right)$
by Lemma 1. Therefore, we proved that $\text{LLM}_{\theta^{\star}}$ is
essentially mimicking the well-known no-regret algorithm, FTPL with
perturbation distribution as $\mathcal{N}(\boldsymbol{0}_{d},\sigma^{2}tI)$
for round $t\in[T]$, according to Equation 12 of 1, for which we can establish
the corresponding regret guarantee for each case:

(1) Combining the above result with Lemma 2, we can derive the regret bound
for online learning with full-information feedback.

(2) Combining the above result with Lemma 2 and Lemma 4, we get that

$\displaystyle\text{D-Regret}_{\text{LLM}{{}_{\theta^{\star}}}}(({\ell}_{i})_{i\in[T]})\leq\min_{\Delta_{T}\in[T]}\frac{2T}{\Delta_{T}}C\sqrt{\Delta_{T}\log
d}+2\Delta_{T}V_{T},$

for some constant $C$. We firstly consider the following problem

$\displaystyle\min_{u>0}\frac{2T}{u}C\sqrt{u\log d}+2uV_{T},$

where the optimal solution is $u^{\star}=\left(\frac{C^{2}T^{2}\log
d}{4V_{T}^{2}}\right)^{1/3}$. Therefore, if we have $u^{\star}\in[1,T]$, we
can choose $\Delta_{T}=\lceil u^{\star}\rceil$, which results in a regret
bound of

$\displaystyle\text{D-Regret}_{\text{LLM}{{}_{\theta^{\star}}}}(({\ell}_{i})_{i\in[T]})\leq\frac{2T}{\sqrt{u^{\star}}}C\sqrt{\log
d}+4u^{\star}V_{T}=\mathcal{O}\left((\log d\ V_{T})^{1/3}T^{2/3}\right).$

Now we check the conditions for $u^{\star}\in[1,T]$. It is direct to see that
since $V_{T}\leq T$, $u^{\star}\geq 1$ holds as long as $d$ is sufficiently
large. To ensure $u^{\star}\leq T$, we get the condition $V_{T}\geq
C\sqrt{\frac{\log d}{4T}}$, which holds as long as $T$ is large enough.

(3) Combining the above result with Lemma 3, we can prove a regret guarantee
for online learning with bandit feedback.

(4) Combining this result with Lemma 3 and Lemma 4, it holds that

$\displaystyle\mathbb{E}[\text{D-Regret}_{\text{LLM}{{}_{\theta^{\star}}}}(({\ell}_{i})_{i\in[T]})]\leq\min_{\Delta_{T}\in[T]}\frac{2T}{\Delta_{T}}C(\log
d)^{\frac{1}{2}}d\Delta_{T}^{\frac{1}{2}+\frac{1}{\log
T}}\log\Delta_{T}+2\Delta_{T}V_{T},$

for some constant $C$. By adopting a similar analysis as that of (2), we
choose $u^{\star}=\left(\frac{C^{\prime}T^{2}d^{2}}{V_{T}^{2}}\right)^{1/3}$
for some constant $C^{\prime}$. If $u^{\star}\in[1,T]$, we choose
$\Delta_{T}=\lceil u^{\star}\rceil$ and derive the following regret:

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

Now we check the condition of $u^{\star}\in[1,T]$. Note that since $V_{T}\leq
T$, $u^{\star}\geq 1$ holds as long as $d$ is sufficiently large. For
$u^{\star}\leq T$, we have $V_{T}\geq\sqrt{\frac{C^{\prime}d^{2}}{T}}$, which
holds as long as $T$ is large enough.

Now, we present Lemma 2 \- Lemma 4. Before proceeding, we assume
$\|\ell_{t}\|_{\infty}\leq B=1$ for simplicity of presentations hereafter. The
results and proof are not affected by the constant bound $B$.

######  Lemma 2 (Regret guarantee of FTPL with full-information feedback).

Suppose the noise distribution of FTPL satisfies that
$\epsilon_{t}\sim\mathcal{N}(\boldsymbol{0}_{d},\zeta_{t}^{2}I)$ in Equation
10 and $\zeta_{t}=\sigma\sqrt{t}$, then for online learning with full-
information feedback,

$\displaystyle\text{Regret}_{\text{FTPL}}(({\ell}_{i})_{i\in[T]})\leq
4\left(\sigma+\frac{1}{\sigma}\right)\sqrt{T\log d}=\mathcal{O}(\sqrt{T\log
d}).$

###### Proof.

By Theorem 8 of Abernethy et al. (2014), we have

$\displaystyle\text{Regret}_{\text{FTPL}}(({\ell}_{i})_{i\in[T]})\leq\sqrt{2\log
d}\left(\eta_{T}+\sum_{t=1}^{T}\frac{1}{\eta_{t}}\|\ell_{t}\|_{\infty}^{2}\right).$

Therefore, plugging $\zeta_{t}=\sigma\sqrt{t}$ and
$\|\ell_{t}\|_{\infty}^{2}\leq 1$ provides

$\displaystyle\text{Regret}_{\text{FTPL}}(({\ell}_{i})_{i\in[T]})\leq\sqrt{2\log
d}\left(\sigma\sqrt{T}+\sum_{t=1}^{T}\frac{1}{\sigma\sqrt{t}}\right)\leq
4\left(\sigma+\frac{1}{\sigma}\right)\sqrt{T\log d},$

completing the proof. ∎

######  Lemma 3 (Regret guarantee of FTPL with bandit feedback).

Suppose the noise distribution of FTPL satisfies that
$\epsilon_{t}\sim\mathcal{N}(\boldsymbol{0}_{d},\zeta_{t}^{2}I)$ in Equation
10 and $\zeta_{t}=\sigma\sqrt{t}$, then for online learning with bandit
feedback,

$\displaystyle\mathbb{E}[\text{Regret}_{\text{FTPL}}(({\ell}_{i})_{i\in[T]})]\leq\mathcal{O}((\log
d)^{\frac{1}{2}}dT^{\frac{1}{2}+\frac{1}{\log T}}\log T).$

###### Proof.

The proof of the bandit problem is more complex. We first define the following
notation. We denote $G_{t}=\sum_{t^{\prime}=1}^{t}-\ell_{t^{\prime}}$,
$\widehat{G}_{t}=\sum_{t^{\prime}=1}^{t}-\widehat{\ell}_{t^{\prime}}$,
$\Phi(G)=\max_{\pi}\langle\pi,G\rangle$,
$\Phi_{t}(G)=\mathbb{E}_{\epsilon\sim\mathcal{N}(\boldsymbol{0}_{d},I)}\Phi(G+\zeta_{t}\epsilon)$,
and $D_{\Phi_{t}}$ to be the Bregman divergence with respect to $\Phi_{t}$,
where we recall the construction of the empirical estimator
$\widehat{\ell}_{t^{\prime}}$ of $\ell_{t^{\prime}}$ in Section 3.2. By Li and
Tewari (2017), $\pi_{t}=\nabla\Phi_{t}(\widehat{G}_{t})$. Now due to the
convexity of $\Phi$,

$\displaystyle\Phi(G_{T})=\Phi(\mathbb{E}[\widehat{G}_{T}])\leq\mathbb{E}[\Phi(\widehat{G}_{T})].$

Therefore,

$\displaystyle\mathbb{E}[\text{Regret}_{\text{FTPL}}(({\ell}_{i})_{i\in[T]})]$
$\displaystyle=\Phi(G_{T})-\mathbb{E}\left[\sum_{t=1}^{T}\langle\pi_{t},-\widehat{\ell}_{t}\rangle\right]\leq\mathbb{E}\left[\Phi(\widehat{G}_{T})-\sum_{t=1}^{T}\langle\pi_{t},-\widehat{\ell}_{t}\rangle\right].$

By recalling the definition of the Bregman divergence, we have

$\displaystyle-\sum_{t=1}^{T}\langle\pi_{t},-\widehat{\ell}_{t}\rangle$
$\displaystyle=-\sum_{t=1}^{T}\langle\nabla\Phi_{t}(\widehat{G}_{t}),-\widehat{\ell}_{t}\rangle=-\sum_{t=1}^{T}\langle\nabla\Phi_{t}(\widehat{G}_{t}),\widehat{G}_{t}-\widehat{G}_{t-1}\rangle$
$\displaystyle=\sum_{t=1}^{T}D_{\Phi_{t}}(\widehat{G}_{t},\widehat{G}_{t-1})+\Phi_{t}(\widehat{G}_{t-1})-\Phi_{t}(\widehat{G}_{t}).$

Therefore,

$\displaystyle\mathbb{E}\left[\text{Regret}_{\text{FTPL}}(({\ell}_{i})_{i\in[T]})\right]$
$\displaystyle\leq\underbrace{\mathbb{E}\left[\sum_{t=1}^{T}D_{\Phi_{t}}(\widehat{G}_{t},\widehat{G}_{t-1})\right]}_{(i)}+\underbrace{\mathbb{E}\left[\sum_{t=1}^{T}\Phi_{t}(\widehat{G}_{t-1})-\Phi_{t-1}(\widehat{G}_{t-1})\right]}_{(ii)}+\underbrace{\mathbb{E}\left[\Phi(\widehat{G}_{T})-\Phi_{T}(\widehat{G}_{T})\right]}_{(iii)}.$

$(iii)\leq 0$ due to the convexity of $\Phi$. For $(ii)$, we use Lemma 10 of
Abernethy et al. (2014) to obtain

$\mathbb{E}\left[\sum_{t=1}^{T}\Phi_{t}(\widehat{G}_{t-1})-\Phi_{t-1}(\widehat{G}_{t-1})\right]\leq\zeta_{T}\mathbb{E}_{\epsilon}[\Phi(\epsilon)]\leq\mathcal{O}(\sqrt{2T\log
d}).$

For $(i)$, by Theorem 8 of Li and Tewari (2017), for any $\alpha\in(0,1)$, the
following holds:

$\displaystyle\mathbb{E}\left[\sum_{t=1}^{T}D_{\Phi_{t}}(\widehat{G}_{t},\widehat{G}_{t-1})\right]\leq\sum_{t=1}^{T}\zeta_{t}^{\alpha-1}\frac{4d}{\alpha(1-\alpha)}\leq\frac{4d}{\alpha(1-\alpha)}\mathcal{O}(T^{\frac{1+\alpha}{2}}).$

By tuning $\alpha=\frac{2}{\log T}$, we proved that
$\mathbb{E}[\text{Regret}_{\text{FTPL}}(({\ell}_{i})_{i\in[T]})]\leq\mathcal{O}((\log
d)^{\frac{1}{2}}dT^{\frac{1}{2}+\frac{1}{\log T}}\log T)$. ∎

######  Lemma 4.

Denote the variation of loss vectors as
$L_{T}=\sum_{t=1}^{T-1}\|\ell_{t+1}-\ell_{t}\|_{\infty}$. Suppose there exists
an algorithm $\mathscr{A}$ for online learning with full-information feedback
with regret guarantee that
$\text{Regret}_{\mathscr{A}}((\ell_{i})_{i\in[T]})\leq f(T,d)$ for some
function $f$, where $T$ denotes the horizon and $d$ denotes the policy
dimension. Then, there exists another algorithm $\mathscr{A}^{\prime}$ that
can achieve

$\displaystyle\text{D-Regret}_{\mathscr{A}^{\prime}}(({\ell}_{i})_{i\in[T]})\leq\min_{\Delta_{T}\in[T]}\left(\frac{T}{\Delta_{T}}+1\right)f(\Delta_{T},d)+2\Delta_{T}L_{T}.$

Similarly, suppose there exists an algorithm $\mathscr{B}$ for online learning
with bandit feedback with regret guarantee that
$\mathbb{E}\left[\text{Regret}_{\mathscr{B}}((\ell_{i})_{i\in[T]})\right]\leq
g(T,d)$ for some function $g$; then there exists another algorithm
$\mathscr{B}^{\prime}$ that can achieve

$\displaystyle\mathbb{E}[\text{D-Regret}_{\mathscr{B}^{\prime}}(({\ell}_{i})_{i\in[T]})]\leq\min_{\Delta_{T}\in[T]}\left(\frac{T}{\Delta_{T}}+1\right)g(\Delta_{T},d)+2\Delta_{T}L_{T}.$

###### Proof.

We denote $\mathscr{A}^{\prime}$ as the algorithm that restarts $\mathscr{A}$
every $\Delta_{T}$ iterations. We break the time index $[T]$ into $m$ batches
${\mathcal{T}}_{1:m}$ of size $\Delta_{T}$ (except for, possibly the last
batch). Denote $\ell_{i}^{\star}:=\min_{j\in[d]}\ell_{ij}$. By Equation (6) of
Besbes et al. (2014), it holds that for each $k\in[m]$

$\displaystyle\min_{j\in[d]}\left(\sum_{t\in{\mathcal{T}}_{k}}\ell_{t}\right)_{j}-\sum_{t\in{\mathcal{T}}_{k}}\ell^{\star}_{t}\leq
2\Delta_{T}L_{k},$

where we define
$L_{k}=\sum_{t\in{\mathcal{T}}_{k}}\|\ell_{t+1}-\ell_{t}\|_{\infty}$.
Therefore, we have

$\displaystyle\text{D-Regret}_{\mathscr{A}^{\prime}}(({\ell}_{i})_{i\in[T]})$
$\displaystyle\leq\min_{j\in[d]}\left(\sum_{t\in[T]}\ell_{t}\right)_{j}-\sum_{t\in[T]}\ell^{\star}_{t}+\sum_{k\in[m]}\text{Regret}_{\mathscr{A}}((\ell_{i})_{i\in[{\mathcal{T}}_{k}]})$
(13) $\displaystyle\leq
2\Delta_{T}(\sum_{k\in[m]}L_{k})+(T/\Delta_{T}+1)g(\Delta_{T},d).$

By Equation (4) of Besbes et al. (2014) that $\sum_{k\in[m]}L_{k}\leq L_{T}$
and this inequality holds for any $\Delta_{T}\in[T]$, we proved
$\text{D-Regret}_{\mathscr{A}^{\prime}}(({\ell}_{i})_{i\in[T]})\leq\min_{\Delta_{T}\in[T]}\left(\frac{T}{\Delta_{T}}+1\right)f(\Delta_{T},d)+2\Delta_{T}L_{T}$.

Similarly, if we take the expectation for Equation 13, it holds that

$\displaystyle\mathbb{E}[\text{D-Regret}_{\mathscr{B}^{\prime}}(({\ell}_{i})_{i\in[T]})]$
$\displaystyle\leq\min_{j\in[d]}\left(\sum_{t\in[T]}\ell_{t}\right)_{j}-\sum_{t\in[T]}\ell^{\star}_{t}+\sum_{k\in[m]}\mathbb{E}[\text{Regret}_{\mathscr{B}}((\ell_{i})_{i\in[{\mathcal{T}}_{k}]})]$
$\displaystyle\leq\min_{\Delta_{T}\in[T]}\left(\frac{T}{\Delta_{T}}+1\right)g(\Delta_{T},d)+2\Delta_{T}L_{T},$

thus completing the proof. ∎

Combining the results above completes the proof for Theorem 1. ∎

###  C.5 Extending Theorem 1 with Relaxed Assumptions

####  C.5.1 Relaxation under More General Data Distributions

We first remark on the possibility of relaxing the Gaussian assumptions on the
data distributions.

######  Remark 3 (Relaxing the Gaussian distribution assumption).

In the proof of Lemma 1, to obtain the result that the action is a quantal
response w.r.t. $\ell_{1:T}$, one does not necessarily require _both_ the
prior distribution of $z$ and the conditional distribution of ${\ell}_{i}$
given $z$ to be Gaussian. Instead, for _any_ joint distribution
$\mathbb{P}(z,\ell_{1:T})$, as long as its posterior distribution satisfies
Equation 11, it would suffice. It is a combined effect of both the prior and
the conditional distributions.

More formally, we can extend Theorem 1 to the case with a much more general
prior task distribution than the Gaussian one, where the key is that Equation
11 only needs to hold approximately.

######  Theorem 5.

In Theorem 1, we can relax the assumption on $\mathbb{P}(z)$ to one where we
only require $\mathbb{P}(z)$ to be i.i.d for each coordinate of $z$ and
$0<\mathbb{P}(z_{j})<\infty$, $|\nabla\mathbb{P}(z_{j})|<\infty$ for any
$j\in[d]$, $z_{j}\in\mathbb{R}$, and the bounds for (1) and (2) of Theorem 1
still hold, with only a degradation of $\mathcal{O}(d^{2}\log T)$.

The key idea of the proof is that when $t$ is large enough, the prior
distribution does not affect the posterior distribution, which is also
referred to as the _Bernstein–von Mises theorem_ (Van der Vaart, 2000).

###### Proof.

Since we extend Theorem 1 to settings with general task prior distribution
only requiring the coordinates to be i.i.d, from now on, we consider the
$j$-th coordinate only. To begin with, fix $t\in[T]$, we define the log-
likelihood of the posterior as

$\displaystyle
L_{t}(z_{j}):=\log\prod_{i=1}^{t}\frac{1}{\sigma^{d}(2\pi)^{d/2}}e^{-\frac{1}{2\sigma^{2}}(\ell_{ij}-z_{j})^{2}}=-t\log\sigma-\frac{t}{2}\log
2\pi-\sum_{i=1}^{t}\frac{1}{2\sigma^{2}}(\ell_{ij}-z_{j})^{2}.$

Then, the MLE estimator $\widehat{z}_{j,t}$ is defined as

$\displaystyle\widehat{z}_{j,t}:=\arg\max_{z_{j}\in\mathbb{R}}L_{t}(z_{j})=\frac{1}{t}\sum_{i=1}^{t}\ell_{ij}.$

We also define $\widehat{J}_{t}:\mathbb{R}\to\mathbb{R}$ as:

$\displaystyle\widehat{J}_{t}(z_{j}):=-\frac{\nabla^{2}L_{t}(z_{j})}{t}=\frac{1}{\sigma^{2}}.$

For Assumption 1 of Kasprzak et al. (2022) to hold, any $\delta>0$, $M_{2}>0$
suffices.

For Assumption 2 of Kasprzak et al. (2022) to hold, we can choose
$\widehat{M}_{1}=\max_{z_{j}\in[-\delta,1+\delta]}\frac{1}{\mathbb{P}(z_{j})}$

For Assumption 7 of Kasprzak et al. (2022) to hold, we choose $\delta$ to be
$\sigma$.

For Assumption 8 of Kasprzak et al. (2022) to hold, one can choose
$M_{2}=\frac{\sigma}{2}$.

For Assumption 9 of Kasprzak et al. (2022) to hold, we have

$\displaystyle\kappa\leq-\sup_{(z_{j}-\widehat{z}_{j})^{2}\geq\delta}\frac{L_{t}(z_{j})-L_{t}(\widehat{z}_{j,t})}{t}=-\frac{1}{2\sigma^{2}t}\sup_{(z_{j}-\widehat{z}_{j,t})^{2}\geq\delta}\sum_{i=1}^{t}(\ell_{ij}-\widehat{z}_{j,t})^{2}-(\ell_{ij}-z_{j})^{2}=\frac{1}{4\sigma}.$

For Assumption 10 of Kasprzak et al. (2022) to hold, we choose
$M_{1}=\sup_{z_{j}\in[-\delta,1+\delta]}\left|\frac{\nabla\mathbb{P}(z_{j})}{\mathbb{P}(z_{j})}\right|$,
$\widetilde{M}_{1}=\sup_{z_{j}\in[-\delta,1+\delta]}|\mathbb{P}(z_{j})|$ since
we have assumed that $0<\mathbb{P}(z_{j})<\infty$,
$|\nabla\mathbb{P}(z_{j})|<\infty$.

By Theorem 6.1 of Kasprzak et al. (2022), we have

$\displaystyle\int_{z_{j}}|$
$\displaystyle\mathbb{P}(z_{j}/\sqrt{t}+\widehat{z}_{j}{\,|\,}(\ell_{ij})_{i\in[t]})-Ce^{-\frac{1}{2\sigma^{2}}z_{j}^{2}}|dz_{j}$
$\displaystyle=\sqrt{t}\int_{z_{j}}|\mathbb{P}(z_{j}{\,|\,}(\ell_{ij})_{i\in[t]})-\mathcal{N}(\widehat{z}_{j},\frac{\sigma^{2}}{t})|dz_{j}\leq
D_{1}t^{-1/2}+D_{2}t^{1/2}e^{-t\kappa}+2\widehat{\mathcal{D}}(t,\delta),$

where $C$ is the normalization constant and

$\displaystyle D_{1}$
$\displaystyle=\frac{\sqrt{\widetilde{M}_{1}\widehat{M}_{1}}}{\sigma}\left(\frac{\sqrt{3}\sigma^{2}}{2\left(1-\sqrt{\widehat{\mathcal{D}}(t,\delta)}\right)}M_{2}+M_{1}\right)$
$\displaystyle D_{2}$
$\displaystyle=\frac{2\widehat{M_{1}}\widehat{J}_{t}^{p}(\widehat{z}_{j},\delta)}{(2\pi)^{1/2}(1-\widehat{\mathcal{D}}^{p}(t,\delta))}$
$\displaystyle\widehat{\mathcal{D}}(t,\delta)$
$\displaystyle=e^{-\frac{1}{2}(\sqrt{t}-1)^{2}}$
$\displaystyle\widehat{J}_{t}^{p}(\widehat{z}_{j},\delta)$
$\displaystyle=\frac{1}{\sigma^{2}}+\frac{\delta M_{2}}{3}.$

Therefore, we conclude that the TV distance between $z$ (conditioned on
$(\ell_{i})_{i\in[t]}$) and
$\mathcal{N}\left(\widehat{z},\frac{\sigma^{2}}{t}\right)$ satisfies that

$\displaystyle\int_{z}\bigg{|}\mathbb{P}(z{\,|\,}(\ell_{i})_{i\in[t]})-\mathcal{N}\left(\widehat{z},\frac{\sigma^{2}}{t}\right)\bigg{|}dz\leq\sum_{j=1}^{d}\int_{z_{j}}\bigg{|}\mathbb{P}(z_{j}{\,|\,}(\ell_{ij})_{i\in[t]})-\mathcal{N}\left(\widehat{z}_{j},\frac{\sigma^{2}}{t}\right)\bigg{|}dz_{j}\leq\mathcal{O}(d/t),$

due to the independence of $(z_{j})_{j\in[d]}$ conditioned on $\ell_{1:t}$.
Now we denote algorithm $\widehat{\text{FTPL}}$ to be the FTPL algorithm
w.r.t. the noise distribution $\mathbb{P}(z{\,|\,}(\ell_{i})_{i\in[t]})$, and
FTPL to be the algorithm w.r.t. the noise distribution
$\mathcal{N}(\widehat{z},\frac{\sigma^{2}}{t})$. Therefore, we have

$\displaystyle\big{|}\text{Regret}_{\text{FTPL}}((\ell)_{i\in[T]})-\text{Regret}_{\widehat{\text{FTPL}}}((\ell)_{i\in[T]})\big{|}\leq\sum_{t=1}^{T}d\|\pi_{t}-\widehat{\pi}_{t}\|_{\infty}$
$\displaystyle\quad\leq
d\sum_{t=1}^{T}\int_{z}\big{|}\mathbb{P}(z{\,|\,}(\ell_{i})_{i\in[t]})-\mathcal{N}(\widehat{z},\frac{\sigma^{2}}{t})\big{|}dz=\mathcal{O}(d^{2}\log
T).$

In other words, using $\mathbb{P}(z{\,|\,}(\ell_{i})_{i\in[t]})$ as the noise
distribution only increases the regret by $\mathcal{O}(d^{2}\log T)$.
Similarly, it is easy to see that

$\displaystyle\big{|}\text{D-Regret}_{\text{FTPL}}((\ell)_{i\in[T]})-\text{D-Regret}_{\widehat{\text{FTPL}}}((\ell)_{i\in[T]})\big{|}\leq\mathcal{O}(d^{2}\log
T),$

which completes the proof. ∎

####  C.5.2 Relaxation under Decision-Irrelevant Pre-Training Data

We then remark on the possible relaxation when the training data may not all
come from decision-making tasks.

######  Remark 4 (Pre-training with relaxed data assumptions).

Note that the pre-training (text) data are so far assumed to be related to
_decision-making_ problems (though not necessarily _sequential ones_), see 1
and Example 1 for instance. It can also be generalized to the text datasets
involving _Question-Answering_ (Q-A), a typical task in natural language
processing, where the _true/fact_ answer, sampled answers from different human
users (with possibly wrong or biased answers), correspond to the latent $z$
(and associated maximizer $a$) and $\ell_{1:t}$, respectively. Moreover, in
practice, the pre-training data may also involve _non-decision-making/Q-A_
texts, given the diversity of the datasets. For such scenarios, we will make
the assumptions on the data distribution _conditioned on the prompt for
decision-making_. Specifically, when interacting with the LLM, human users
will provide prompts (see e.g., our Figure 3), to induce it to make decisions.
This will query the _conditional_ distribution of

$\mathbb{P}\left(g(x_{N_{t}+1:N_{t+1}}){\,\big{|}\,}x_{1:N_{t}},\text{decision-
making prompt}\right)$

to generate the control action. Correspondingly, 1 will thus only need to be
made on

$\mathbb{P}\left(z,\ell_{1:t},x_{1:N_{t+1}},\text{decision-making
prompt}\right),$

while we do not need to make such assumptions on other prompts, e.g., corpora
that are not related to decision-making.

##  Appendix D Deferred Results and Proofs in Section 5

###  D.1 Basic Lemmas

######  Lemma 5 (Double iterated limit).

For a sequence $(a_{mn})_{m,n\in\mathbb{N}^{+}}$, suppose that
$\lim_{m,n\to\infty}a_{mn}=L$. Then the following are equivalent:

  * •

For each $m$, $\lim_{n\to\infty}a_{mn}$ exists;

  * •

$\lim_{m\to\infty}\lim_{n\to\infty}a_{mn}=L$.

######  Lemma 6 (Hoeffding’s inequality).

Let $X_{1},X_{2},\ldots,X_{n}$ be independent random variables bounded by the
intervals $[a_{i},b_{i}]$, respectively. Define
$\bar{X}=\frac{1}{n}\sum_{i=1}^{n}X_{i}$ and let $\mu=\mathbb{E}[\bar{X}]$ be
the expected value of $\bar{X}$. Then, for any $t>0$,

$\mathbb{P}(|\bar{X}-\mu|\geq t)\leq
2\exp\left(-\frac{2n^{2}t^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right).$

######  Lemma 7 (Uniform convergence $\Longrightarrow$ Interchanging limit and
infimum).

If $(f_{n}:X\to\mathbb{R})_{n\in\mathbb{N}^{+}}$ is a sequence of continuous
functions that uniformly converge to a function $f:X\to\mathbb{R}$ on the
domain $X$, then $\lim_{n\to\infty}\inf_{x\in X}f_{n}(x)=\inf_{x\in X}f(x)$
holds.

###  D.2 Deferred Proof for the Arguments in Section 5.1

In this section, we prove some properties of $\mathcal{L}(\theta,k,N)$ under
certain regularity conditions of $f,h$. Throughout this subsection, we will
assume the following condition holds.

######  Condition 1.

For $h:\mathbb{R}\to\mathbb{R}^{+}$ and
$f:\mathbb{R}\times\mathbb{N}^{+}\to\mathbb{R}^{+}$, suppose $h(\cdot)$ and
$f(\cdot,k)$ are both continuous and non-decreasing functions for any
$k\in\mathbb{N}^{+}$. The derivative $h^{\prime}:\mathbb{R}\to\mathbb{R}$ is
also a continuous function. Moreover, $f$ satisfies that $\log
f(R_{1},k_{1})-\log f(R_{1},k_{2})\geq\log f(R_{2},k_{1})-\log f(R_{2},k_{2})$
for $R_{1}\geq R_{2}$ and $k_{1}\geq k_{2}$, i.e., $\log f$ is supermodular.
Lastly, $f$ is a function such that
$\lim_{k\to\infty}\frac{f(R_{1},k)}{f(R_{2},k)}=\infty\cdot\mathbbm{1}(R_{1}>R_{2})+\mathbbm{1}(R_{1}=R_{2})$,
with the convention of $\infty\cdot 0=0$. Lastly,
$(\ell_{t}^{(j)})_{t\in[T],j\in[N]}$ are continuous random variables supported
on $[-B,B]^{T\times N}$.

######  Claim 1 (Iterated limit of $\mathcal{L}(\theta,k,N)$ is the same as
double limit of $\mathcal{L}(\theta,k,N)$).

It holds that:

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

###### Proof.

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

Firstly, as both $h$ and $f$ are non-negative (1), and
$\mathbb{E}_{(\ell_{t}^{(j)})_{t\in[T],j\in[N]}}\left[h(\max_{j\in[N]}\text{Regret}_{\text{LLM}_{\theta}}((\ell_{t}^{(j)})_{t\in[T]}))\right]$
exists, we have by dominated convergence theorem that

$\displaystyle\lim_{k\to\infty}\mathcal{L}(\theta,k,N)$
$\displaystyle=\mathbb{E}\lim_{k\to\infty}\left[\frac{\sum_{j\in[N]}h(R_{\text{LLM}_{\theta}}((\ell_{t}^{(j)})_{t\in[T]}))f(R_{\text{LLM}_{\theta}}((\ell_{t}^{(j)})_{t\in[T]}),k)}{\sum_{j\in[N]}f(R_{\text{LLM}_{\theta}}((\ell_{i}^{(j)})_{t\in[T]}),k)}\right]$
$\displaystyle=\mathbb{E}_{(\ell_{t}^{(j)})_{t\in[T],j\in[N]}}\left[h(\max_{j\in[N]}R_{\text{LLM}_{\theta}}((\ell_{t}^{(j)})_{t\in[T]}))\right]$

where $R_{\text{LLM}_{\theta}}$ denotes an abbreviation of
$\text{Regret}_{\text{LLM}_{\theta}}$. By (Ahsanullah et al., 2013, Chapter
11), we have
$h(\max_{j\in[N]}\text{Regret}_{\text{LLM}_{\theta}}((\ell_{t}^{(j)})_{t\in[T]}))\overset{p}{\to}h(\max_{\ell_{1},\dots,\ell_{T}}\text{Regret}_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]}))$
when $N\to\infty$. Hence, we have
$\lim_{N\to\infty}\lim_{k\to\infty}\mathcal{L}(\theta,k,N)=h(\max_{\ell_{1},\dots,\ell_{T}}\text{Regret}_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]}))$
holds.

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

Now, we will calculate $\lim_{N,k\to\infty}\mathcal{L}(\theta,k,N)$.

######  Lemma 8.

For any $0<\epsilon<1$, it follows that

$\lim_{N,k\to\infty}\frac{\sum_{i=1}^{N}f(X_{i},k)H(X_{i})\mathbbm{1}(H(X_{i})<1-\epsilon)}{\sum_{i=1}^{N}f(X_{i},k)H(X_{i})\mathbbm{1}(H(X_{i})>1-\epsilon/2)}=0$

and

$\lim_{N,k\to\infty}\frac{\sum_{i=1}^{N}f(X_{i},k)\mathbbm{1}(H(X_{i})<1-\epsilon)}{\sum_{i=1}^{N}f(X_{i},k)\mathbbm{1}(H(X_{i})>1-\epsilon/2)}=0$

hold with probability $1$, where $X_{i}$’s are i.i.d. random variables,
$\operatorname{esssup}(H(X_{i}))=1$, and $H:\mathbb{R}\to\mathbb{R}^{+}$ is a
continuous non-decreasing function.

###### Proof of Lemma 8.

Since $f(\cdot,k),H$ are non-negative and non-decreasing functions, we have

$\displaystyle\frac{\sum_{i=1}^{N}f(X_{i},k)H(X_{i})\mathbbm{1}(H(X_{i})<1-\epsilon)}{\sum_{i=1}^{N}f(X_{i},k)H(X_{i})\mathbbm{1}(H(X_{i})>1-\epsilon/2)}\leq\frac{(1-\epsilon)f(H^{-1}(1-\epsilon),k)|\\{i\in[N]\mid(H(X_{i})<1-\epsilon)\\}|}{(1-\epsilon/2)f(H^{-1}(1-\epsilon/2),k)|\\{i\in[N]\mid(H(X_{i})>1-\epsilon/2)\\}|}$

and we know that

$\displaystyle\frac{|\\{i\in[N]\mid(H(X_{i})<1-\epsilon)\\}|}{|\\{i\in[N]\mid(H(X_{i})>1-\epsilon/2)\\}|}\overset{a.s.}{\to}\frac{F(1-\epsilon)}{1-F(1-\epsilon/2)}$

as $N\to\infty$, where $F$ is the cumulative distribution function of random
variable $H(X)$. Therefore, we have

$\displaystyle
0\leq\lim_{N,k\to\infty}\frac{\sum_{i=1}^{N}f(X_{i},k)H(X_{i})\mathbbm{1}(H(X_{i})<1-\epsilon)}{\sum_{i=1}^{N}f(X_{i},k)H(X_{i})\mathbbm{1}(H(X_{i})>1-\epsilon/2)}$
$\displaystyle\leq\lim_{N,k\to\infty}\frac{(1-\epsilon)f(H^{-1}(1-\epsilon),k))|\\{i\in[N]\mid(H(X_{i})<1-\epsilon)\\}|}{(1-\epsilon/2)f(H^{-1}(1-\epsilon/2),k))|\\{i\in[N]\mid(H(X_{i})>1-\epsilon/2)\\}|}$
$\displaystyle\underset{a.s.}{\leq}\lim_{N,k\to\infty}\frac{(1-\epsilon)f(H^{-1}(1-\epsilon),k))}{(1-\epsilon/2)f(H^{-1}(1-\epsilon/2),k))}\frac{F(1-\epsilon)}{1-F(1-\epsilon/2)}=0.$

By a similar argument, we have

$\lim_{N,k\to\infty}\frac{\sum_{i=1}^{N}f(X_{i},k)\mathbbm{1}(H(X_{i})<1-\epsilon)}{\sum_{i=1}^{N}f(X_{i},k)\mathbbm{1}(H(X_{i})>1-\epsilon/2)}=0$

with probability 1. ∎

One key idea in the proof above is the use of some _truncation_ level
$\epsilon$ for $H(X)$ with $\text{esssup}(H(X))=1$. By Lemma 8, we have

$\lim_{N,k\to\infty}\frac{\sum_{i=1}^{N}f(X_{i},k)H(X_{i})\mathbbm{1}(H(X_{i})>1-\epsilon)}{\sum_{i=1}^{N}f(X_{i},k)H(X_{i})}=\lim_{N,k\to\infty}\frac{\sum_{i=1}^{N}f(X_{i},k)\mathbbm{1}(H(X_{i})>1-\epsilon)}{\sum_{i=1}^{N}f(X_{i},k)}=1,$

since

$\displaystyle
0\leq\frac{\sum_{i=1}^{N}f(X_{i},k)\mathbbm{1}(H(X_{i})<1-\epsilon)}{\sum_{i=1}^{N}f(X_{i},k)}\leq\frac{\sum_{i=1}^{N}f(X_{i},k)\mathbbm{1}(H(X_{i})<1-\epsilon)}{\sum_{i=1}^{N}f(X_{i},k)\mathbbm{1}(H(X_{i})>1-\epsilon/2)}$

holds with probability 1. Therefore, for any $0<\epsilon<1$, we have

$\displaystyle\lim_{N,k\to\infty}\mathcal{L}(\theta,k,N)=\mathbb{E}\lim_{N,k\to\infty}\left[\frac{\sum_{j\in[N]}h(R_{\text{LLM}_{\theta}}((\ell_{t}^{(j)})_{t\in[T]}))f(R_{\text{LLM}_{\theta}}((\ell_{t}^{(j)})_{t\in[T]}),k)}{\sum_{j\in[N]}f(R_{\text{LLM}_{\theta}}((\ell_{i}^{(j)})_{t\in[T]}),k)}\right]$
$\displaystyle=h\left(\max_{\ell_{1},\dots,\ell_{T}}R_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]})\right)$
$\displaystyle\,\,\quad\times\mathbb{E}\lim_{N,k\to\infty}\left[\frac{\sum_{j\in[N]}\frac{h(R_{\text{LLM}_{\theta}}((\ell_{t}^{(j)})_{t\in[T]}))}{h(\max_{\ell_{1},\dots,\ell_{T}}R_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]}))}f(R_{\text{LLM}_{\theta}}((\ell_{t}^{(j)})_{t\in[T]}),k)\mathbbm{1}(\frac{h(R_{\text{LLM}_{\theta}}((\ell_{t}^{(j)})_{t\in[T]}))}{h(\max_{\ell_{1},\dots,\ell_{T}}R_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]}))}>1-\epsilon)}{\sum_{j\in[N]}f(R_{\text{LLM}_{\theta}}((\ell_{i}^{(j)})_{t\in[T]}),k)\mathbbm{1}(\frac{h(R_{\text{LLM}_{\theta}}((\ell_{t}^{(j)})_{t\in[T]}))}{h(\max_{\ell_{1},\dots,\ell_{T}}R_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]}))}>1-\epsilon)}\right]$
$\displaystyle\geq(1-\epsilon)h(\max_{\ell_{1},\dots,\ell_{T}}R_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]}))$

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

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

by definition of $\mathcal{L}$, the fact that $h$ is non-decreasing, and by
setting $\epsilon\to 0$ to obtain

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

Here, we used the fact that $(\ell_{t})_{t\in[T]}$ has a continuous
distribution, $\text{Regret}_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]})$ is a
continuous function, and the non-decreasing property and continuity of $h$
(1), which lead to:

$\displaystyle\text{esssup}\left(h\left(\text{Regret}_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]})\right)\right)=\max_{\ell_{1},\dots,\ell_{T}}h\left(\text{Regret}_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]})\right)=h\left(\max_{\ell_{1},\dots,\ell_{T}}\text{Regret}_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]})\right).$
(14)

Equation 14 will be used frequently in the overall proof in Section D.2.

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

Lastly, if $N\to\infty$, similarly by dominated convergence theorem we have

$\displaystyle\lim_{N\to\infty}\mathcal{L}(\theta,k,N)$
$\displaystyle=\mathbb{E}\lim_{N\to\infty}\left[\frac{\sum_{j\in[N]}h\left(R_{\text{LLM}_{\theta}}\left((\ell_{t}^{(j)})_{t\in[T]}\right)\right)f(R_{\text{LLM}_{\theta}}((\ell_{t}^{(j)})_{t\in[T]}),k)}{\sum_{j\in[N]}f\left(R_{\text{LLM}_{\theta}}\left((\ell_{i}^{(j)})_{t\in[T]}\right),k\right)}\right]$
$\displaystyle=\frac{\mathbb{E}\left[h\left(R_{\text{LLM}_{\theta}}\left((\ell_{t}^{(j)})_{t\in[T]}\right)\right)f\left(R_{\text{LLM}_{\theta}}\left((\ell_{t}^{(j)})_{t\in[T]}\right),k\right)\right]}{\mathbb{E}\left[f\left(R_{\text{LLM}_{\theta}}\left((\ell_{i}^{(j)})_{t\in[T]}\right),k\right)\right]}.$

Thus, $\lim_{N\to\infty}\mathcal{L}(\theta,k,N)$ always exists for every $k$.
Now, we use the known property of double iterated limit (Lemma 5), and obtain
that
$\lim_{k\to\infty}\lim_{N\to\infty}\mathcal{L}(\theta,k,N)=h(\max_{\ell_{1},\dots,\ell_{T}}\text{Regret}_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]}))$.
∎

######  Claim 2 (Uniform convergence of $\mathcal{L}(\theta,k,N)$ (with
respect to $k$ and $N$)).

$\mathcal{L}(\theta,k,N)$ uniformly converges to
$h(\max_{\ell_{1},\dots,\ell_{T}}\emph{Regret}_{\emph{LLM}_{\theta}}((\ell_{t})_{t\in[T]}))$
on the domain $\Theta$.

###### Proof.

We will provide a similar analysis as Lemma 8 as follows:

######  Lemma 9.

For any $0<\epsilon<1$, $0<\delta<1$, and $k\in\mathbb{N}^{+}$, we have

$\frac{\sum_{i=1}^{N}f(X_{i},k)\mathbbm{1}(H(X_{i})<1-\epsilon)}{\sum_{i=1}^{N}f(X_{i},k)\mathbbm{1}(H(X_{i})>1-\epsilon)}=\widetilde{\mathcal{O}}\left(A(k,H,\epsilon)\left(\frac{1}{1-F_{H,X}(1-\epsilon/2)}+\frac{1}{\sqrt{N}}\right)\right)$

with probability at least $1-\delta$, where $X_{i}$’s are i.i.d. random
variables, $\operatorname{esssup}(H(X_{i}))=1$,
$H:\mathbb{R}\to\mathbb{R}^{+}$ is a continuous non-decreasing function,
$A(k,t,\epsilon):=\frac{(1-\epsilon)f((t/\operatorname{esssup}(t(X)))^{-1}(1-\epsilon),k)}{(1-\epsilon/2)f((t/\operatorname{esssup}(t(X)))^{-1}(1-\epsilon/2),k)}$,
for any non-decreasing function $t:\mathbb{R}\to\mathbb{R}^{+}$, and $F_{t,X}$
is a cumulative distribution function of random variable
$t(X)/\text{esssup}(t(X))$.

###### Proof of Lemma 9.

With the same argument as the proof of Lemma 8, we have

$\displaystyle\frac{\sum_{i=1}^{N}f(X_{i},k)\mathbbm{1}(H(X_{i})<1-\epsilon)}{\sum_{i=1}^{N}f(X_{i},k)\mathbbm{1}(H(X_{i})>1-\epsilon/2)}\leq\frac{f(H^{-1}(1-\epsilon),k)|\\{i\in[N]\mid(H(X_{i})<1-\epsilon)\\}|}{f(H^{-1}(1-\epsilon/2),k)|\\{i\in[N]\mid(H(X_{i})>1-\epsilon/2)\\}|}.$

It holds that
$\frac{1}{N}|\\{i\in[N]\mid(H(X_{i})<1-\epsilon)\\}|=F_{H,X}(1-\epsilon)+\widetilde{\mathcal{O}}(1/\sqrt{N})$
with probability at least $1-\delta/2$ due to Hoeffding’s inequality (Lemma
6). Similarly, we have
$\frac{1}{N}|\\{i\in[N]\mid(H(X_{i})>1-\epsilon/2)\\}|=1-F_{H,X}(1-\epsilon/2)+\widetilde{\mathcal{O}}(1/\sqrt{N})$
with probability at least $1-\delta/2$. Therefore,

$\displaystyle\frac{|\\{i\in[N]\mid(H(X_{i})<1-\epsilon)\\}|}{|\\{i\in[N]\mid(H(X_{i})>1-\epsilon/2)\\}|}=\frac{F_{H,X}(1-\epsilon)}{1-F_{H,X}(1-\epsilon/2)}+\widetilde{\mathcal{O}}(\sqrt{1/N})\leq\frac{1}{1-F_{H,X}(1-\epsilon/2)}+\widetilde{\mathcal{O}}(\sqrt{1/N}),$

with probability at least $1-\delta$. Finally, we have

$\displaystyle\frac{\sum_{i=1}^{N}f(X_{i},k)\mathbbm{1}(H(X_{i})<1-\epsilon)}{\sum_{i=1}^{N}f(X_{i},k)\mathbbm{1}(H(X_{i})>1-\epsilon)}<\frac{\sum_{i=1}^{N}f(X_{i},k)\mathbbm{1}(H(X_{i})<1-\epsilon)}{\sum_{i=1}^{N}f(X_{i},k)\mathbbm{1}(H(X_{i})>1-\epsilon/2)}$
$\displaystyle\leq
A(k,H,\epsilon)\left(\frac{1}{1-F_{H,X}(1-\epsilon/2)}+\widetilde{\mathcal{O}}(\frac{1}{\sqrt{N}})\right).$

∎

Note that $\lim_{k\to\infty}A(k,H,\epsilon)=0$, since
$\lim_{k\to\infty}\frac{f(R_{1},k)}{f(R_{2},k)}=\infty\cdot\mathbbm{1}(R_{1}>R_{2})+\mathbbm{1}(R_{1}=R_{2})$.
By Lemma 9 with
$H(R_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]}))=\frac{h(R_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]}))}{h(\max_{\ell_{1},\dots,\ell_{T}}R_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]}))}$,
we have

$\displaystyle\frac{\sum_{i=1}^{N}f(R_{\text{LLM}_{\theta}}((\ell_{t}^{(i)})_{t\in[T]}),k)\mathbbm{1}\left(\frac{h(R_{\text{LLM}_{\theta}}((\ell_{t}^{(i)})_{t\in[T]}))}{h(\max_{\ell_{1},\dots,\ell_{T}}R_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]}))}\geq
1-\epsilon\right)}{\sum_{i=1}^{N}f(R_{\text{LLM}_{\theta}}((\ell_{t}^{(i)})_{t\in[T]}),k)}$
$\displaystyle\quad=\frac{1}{1+\frac{\sum_{i=1}^{N}f(R_{\text{LLM}_{\theta}}((\ell_{t}^{(i)})_{t\in[T]}),k)\mathbbm{1}\left(\frac{h(R_{\text{LLM}_{\theta}}((\ell_{t}^{(i)})_{t\in[T]}))}{h(\max_{\ell_{1},\dots,\ell_{T}}R_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]}))}<1-\epsilon\right)}{\sum_{i=1}^{N}f(R_{\text{LLM}_{\theta}}((\ell_{t}^{(i)})_{t\in[T]}),k)\mathbbm{1}\left(\frac{h(R_{\text{LLM}_{\theta}}((\ell_{t}^{(i)})_{t\in[T]}))}{h(\max_{\ell_{1},\dots,\ell_{T}}R_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]}))}\geq
1-\epsilon\right)}}\geq\frac{1}{1+A(k,H,\epsilon)(\frac{1}{1-F_{H,R_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]})}(1-\epsilon/2)}+\widetilde{\mathcal{O}}(\sqrt{1/N}))},$

where we recall the shorthand notation of
$R_{\text{LLM}_{\theta}}=\text{Regret}_{\text{LLM}_{\theta}}$. Note that
$A(k,H,\epsilon)=A(k,h,\epsilon)$ and
$F_{H,R_{\text{LLM}_{\theta}}}=F_{h,R_{\text{LLM}_{\theta}}}$ hold by the
definitions of $F_{t,X}$ and $A(k,t,\epsilon)$ in Lemma 9. Therefore,

$\displaystyle 1$
$\displaystyle\geq\frac{\sum_{i=1}^{N}f(R_{\text{LLM}_{\theta}}((\ell_{t}^{(i)})_{t\in[T]}),k)\frac{h(R_{\text{LLM}_{\theta}}((\ell_{t}^{(i)})_{t\in[T]}))}{h(\max_{\ell_{1},\dots,\ell_{T}}R_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]}))}}{\sum_{i=1}^{N}f(R_{\text{LLM}_{\theta}}((\ell_{t}^{(i)})_{t\in[T]}),k)}$
$\displaystyle\geq\frac{\sum_{i=1}^{N}f(R_{\text{LLM}_{\theta}}((\ell_{t}^{(i)})_{t\in[T]}),k)\frac{h(R_{\text{LLM}_{\theta}}((\ell_{t}^{(i)})_{t\in[T]}))}{h(\max_{\ell_{1},\dots,\ell_{T}}R_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]}))}\mathbbm{1}(\frac{h(R_{\text{LLM}_{\theta}}((\ell_{t}^{(i)})_{t\in[T]}))}{h(\max_{\ell_{1},\dots,\ell_{T}}R_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]}))}\geq
1-\epsilon)}{\sum_{i=1}^{N}f(R_{\text{LLM}_{\theta}}((\ell_{t}^{(i)})_{t\in[T]}),k)\mathbbm{1}(\frac{h(R_{\text{LLM}_{\theta}}((\ell_{t}^{(i)})_{t\in[T]}))}{h(\max_{\ell_{1},\dots,\ell_{T}}R_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]}))}\geq
1-\epsilon)}$
$\displaystyle\qquad\times\frac{1}{1+A(k,h,\epsilon)(\frac{1}{1-F_{h,R_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]})}(1-\epsilon/2)}+\widetilde{\mathcal{O}}(\sqrt{1/N}))}$
$\displaystyle\geq\frac{1-\epsilon}{1+A(k,h,\epsilon)(\frac{1}{1-F_{h,R_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]})}(1-\epsilon/2)}+\widetilde{\mathcal{O}}(\sqrt{1/N}))}$

with probability at least $1-\delta$.

Now, for any $\epsilon>0$ and $\delta>0$, we have

$\displaystyle 0$ $\displaystyle\leq
h\left(\max_{\ell_{1},\dots,\ell_{T}}R_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]})\right)-\mathcal{L}(\theta,k,N)$
$\displaystyle\leq
h\left(\max_{\ell_{1},\dots,\ell_{T}}R_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]})\right)\left(1-\frac{(1-\delta)(1-\epsilon)}{1+A(k,h,\epsilon)(\frac{1}{1-F_{h,R_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]})}(1-\epsilon/2)}+\widetilde{\mathcal{O}}(\sqrt{1/N}))}\right).$

Note that

$1-F_{h,R_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]})}(1-\epsilon/2)=\mathbb{P}\left(h\left(\text{Regret}_{\text{LLM}_{\theta}}\left((\ell_{t})_{t\in[T]}\right)\right)>(1-\epsilon/2)h\left(\max_{\ell_{1},\dots,\ell_{T}}\text{Regret}_{\text{LLM}_{\theta}}\left((\ell_{t})_{t\in[T]}\right)\right)\right)$

is a continuous function of $\theta$, since we assume $\text{LLM}_{\theta}$ is
a continuous function of $\theta$, $(\ell_{t})_{t\in[T]}$ has a continuous
distribution, and $\text{Regret}_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]})$
is a continuous function of $\text{LLM}_{\theta}$ and $(\ell_{t})_{t\in[T]}$.
Since we consider a compact $\Theta$ (as several recent works on analyzing
Transformers (Bai et al., 2023; Lin et al., 2024)), we have
$p(\epsilon):=\min_{\theta\in\Theta}1-F_{h,R_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]})}(1-\epsilon/2)>0$.
Therefore,

$\displaystyle\left(1-\frac{(1-\delta)(1-\epsilon)}{1+A(k,h,\epsilon)(\frac{1}{1-F_{h,R_{\text{LLM}_{\theta}}}(1-\epsilon/2)}+\widetilde{\mathcal{O}}(\sqrt{1/N}))}\right)\leq\left(1-\frac{(1-\delta)(1-\epsilon)}{1+A(k,h,\epsilon)(\frac{1}{p(\epsilon)}+\widetilde{\mathcal{O}}(\sqrt{1/N}))}\right),$
(15)

and we know that
$\lim_{N,k\to\infty}1+A(k,h,\epsilon)(\frac{1}{p(\epsilon)}+\widetilde{\mathcal{O}}(\sqrt{1/N}))=1$,
which is not dependent on $\theta$. Thus, we can conclude that
$\lim_{N,k\to\infty}\sup_{\theta\in\Theta}|h(\max_{\ell_{1},\dots,\ell_{T}}\text{Regret}_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]}))-\mathcal{L}(\theta,k,N)|=0$,
as we can choose arbitrarily small $\epsilon,\delta$. ∎

######  Claim 3 (Double iterated limit of supremum).

It holds that:

$\lim_{N\to\infty}\lim_{k\to\infty}\sup_{\theta\in\Theta}~{}~{}\Big{|}\mathcal{L}(\theta,k,N)-h\left(\max_{\ell_{1},\dots,\ell_{T}}\emph{Regret}_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]})\right)\Big{|}=0.$

###### Proof.

Since
$h(\max_{\ell_{1},\dots,\ell_{T}}\text{Regret}_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]}))\geq\mathcal{L}(\theta,k,N)$,
we will prove

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

######  Lemma 10.

$\frac{\sum_{i=1}^{N}f(X_{i},k_{1})h(X_{i})}{\sum_{i=1}^{N}f(X_{i},k_{1})}\leq\frac{\sum_{i=1}^{N}f(X_{i},k_{2})h(X_{i})}{\sum_{i=1}^{N}f(X_{i},k_{2})}$
holds if ${0<}k_{1}\leq k_{2}$ for any real-valued $(X_{i})_{i\in[N]}$.

###### Proof.

By multiplying
$({\sum_{i=1}^{N}f(X_{i},k_{1})})({\sum_{i=1}^{N}f(X_{i},k_{2})})$ on both
sides of the formula, we know that it is equivalent to $\sum_{1\leq i\neq
j\leq N}f(X_{i},k_{1})h(X_{i})f(X_{j},k_{2})\leq\sum_{1\leq i\neq j\leq
N}f(X_{i},k_{1})h(X_{j})f(X_{j},k_{2})$. This is equivalent to

$\displaystyle\sum_{1\leq i\neq j\leq
N}(f(X_{i},k_{1})f(X_{j},k_{2})-f(X_{j},k_{1})f(X_{i},k_{2}))(h(X_{i})-h(X_{j}))\leq
0,$

which is true since if $X_{i}\geq X_{j}$,
$(f(X_{i},k_{1})f(X_{j},k_{2})-f(X_{j},k_{1})f(X_{i},k_{2}))\leq 0$ due to the
log-increasing difference of $f$ (1), as $\log f(X_{j},k_{1})-\log
f(X_{j},k_{2})\geq\log f(X_{i},k_{1})-\log f(X_{i},k_{2})$ if $X_{i}\geq
X_{j}$. ∎

Therefore, $\mathcal{L}(\theta,k,N)$ is a non-decreasing function of $k$ if
$N$ is fixed, which indicates that

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

exists, as $\mathcal{L}(\theta,k,N)$ is also bounded. Therefore, by Lemma 5
and 2, we know that

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

exists and this value should be 0. ∎

######  Claim 4.

It holds that

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

###### Proof.

Firstly, by Lemma 7, we have
$\lim_{N,k\to\infty}\inf_{\theta\in\Theta}\mathcal{L}(\theta,k,N)=\inf_{\theta\in\Theta}h(\max_{\ell_{1},\dots,\ell_{T}}\text{Regret}_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]}))$.
Plus, we already know that $\mathcal{L}(\theta,k,N)$ is a monotonically non-
decreasing function of $k$ for any fixed $N$ (Lemma 10), and it is bounded,
$\lim_{k\to\infty}\inf_{\theta\in\Theta}\mathcal{L}(\theta,k,N)$ always
exists. Therefore, by Lemma 5 , we also have
$\lim_{N\to\infty}\lim_{k\to\infty}\inf_{\theta\in\Theta}\mathcal{L}(\theta,k,N)=\inf_{\theta\in\Theta}h(\max_{\ell_{1},\dots,\ell_{T}}\text{Regret}_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]}))$.
∎

###  D.3 Deferred Proofs of Theorem 2 and Corollary 1

See 2

Before proving the theorem, we remark on what LLM structure enjoys the
Lipschitz-continuity. We provide two auxiliary results in the following
proposition. The first result is from (Bai et al., 2023, Section J.1), which
is about the Lipschitzness of Transformers. The second result is regarding
processing the output of Transformers. In particular, the output of
Transformers is usually not directly used, but passed through some matrix
multiplication (by some matrix $A$), followed by some projection Operator (to
be specified later).

######  Proposition 2.

The $L$-layer Transformer $\texttt{TF}_{\theta}$ as defined in Section A.1 is
$C_{\texttt{TF}}$-Lipschitz continuous with respect to $\theta$ with
$C_{\texttt{TF}}:=L\left((1+B_{\texttt{TF}}^{2})(1+B_{\texttt{TF}}^{2}R^{3})\right)^{L}B_{\texttt{TF}}R(1+B_{\texttt{TF}}R^{2}+B_{\texttt{TF}}^{3}R^{2})$,
i.e.,

$\displaystyle\|\texttt{TF}_{\theta_{1}}(Z)-\texttt{TF}_{\theta_{2}}(Z)\|_{2,\infty}\leq
C_{\texttt{TF}}\|\theta_{1}-\theta_{2}\|_{\texttt{TF}}$

where $\|\cdot\|_{\texttt{TF}}$ is as defined in Equation 9, and
$R,Z,B_{\texttt{TF}}$ are as introduced in Section A.1. Moreover, the function
$\texttt{Operator}(A\cdot\texttt{TF}_{\theta}(\cdot)_{-1})$ is
$\|A\|_{\texttt{op}}C_{\texttt{TF}}$-Lipschitz continuous with respect to
$\theta$, i.e.,

$\displaystyle\|\texttt{Operator}(A\cdot\texttt{TF}_{\theta_{1}}(Z)_{-1})-\texttt{Operator}(A\cdot\texttt{TF}_{\theta_{2}}(Z)_{-1})\|_{2}\leq\|A\|_{\texttt{op}}C_{\texttt{TF}}\|\theta_{1}-\theta_{2}\|_{\texttt{TF}}.$

Here, Operator is either the projection operator onto some convex set, or the
Softmax function.

###### Proof.

The first result is from (Bai et al., 2023, Section J.1). The second result
comes from

  * •

If Operator is a projection onto the convex set, then
$\|\texttt{Operator}(x)-\texttt{Operator}(y)\|_{2}\leq\|x-y\|_{2}$;

  * •

If Operator is Softmax, then
$\|\texttt{Softmax}(x)-\texttt{Softmax}(y)\|_{2}\leq\|x-y\|_{2}$ (Gao and
Pavel, 2017, Corollary 3).

Note that the only condition that we require for Operator is its non-
expansiveness. ∎

###### Proof of Theorem 2.

Let $C_{\text{LLM}}$ denote the Lipschitz-continuity constant for
$\text{LLM}_{\theta}$ with respect to some norm $\|\cdot\|_{\text{LLM}}$,
where $\|\cdot\|_{\text{LLM}}$ denotes any norm defined on the parameter space
of LLM (e.g., the norm $\|\cdot\|_{\texttt{TF}}$ above in Proposition 2). Now,
we prove that regret is also a Lipschitz-continuous function with respect to
the LLM’s parameter.

######  Lemma 11 (Lipschitzness of regret).

The function $\text{Regret}_{\text{LLM}_{\theta}}$ is
$C_{\texttt{Reg}}:=BC_{\text{LLM}}T$-Lipschitz continuous with respect to
$\theta$, i.e.,

$\displaystyle\Big{|}\emph{Regret}_{\text{LLM}_{\theta_{1}}}$
$\displaystyle((\ell_{t})_{t\in[T]})-\emph{Regret}_{\text{LLM}_{\theta_{2}}}((\ell_{t})_{t\in[T]})\Big{|}\leq
C_{\texttt{Reg}}\|\theta_{1}-\theta_{2}\|_{\text{LLM}}.$

###### Proof.

By definition, we have

$\displaystyle\Big{|}\text{Regret}_{\text{LLM}_{\theta_{1}}}$
$\displaystyle((\ell_{t})_{t\in[T]})-\text{Regret}_{\text{LLM}_{\theta_{2}}}((\ell_{t})_{t\in[T]})\Big{|}=\left|\sum_{t=1}^{T}\langle\ell_{t},\text{LLM}_{\theta_{1}}(Z_{t-1})-\text{LLM}_{\theta_{2}}(Z_{t-1})\rangle\right|$
$\displaystyle=B\sum_{t=1}^{T}\|\text{LLM}_{\theta_{1}}(Z_{t-1})-\text{LLM}_{\theta_{2}}(Z_{t-1})\|$
$\displaystyle\leq BC_{\text{LLM}}T\|\theta_{1}-\theta_{2}\|_{\text{LLM}}$

where $Z_{t}:=(\ell_{1},\dots,\ell_{t},c)$ for all $t\in[T]$ and $Z_{0}=(c)$
where $c$ is a $d$-dimensional vector. ∎

Now, we will prove the Lipschitzness of

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

with respect to the model parameter $\theta$.

######  Claim 5.

For any $R>0$, there exists $\beta_{R}>0$ such that if $\beta>\beta_{R}$, we
have

$\displaystyle\left|\frac{\sum_{n\in[N]}x_{n}f(x_{n},\beta)}{\sum_{n\in[N]}f(x_{n},\beta)}-\frac{\sum_{n\in[N]}y_{n}f(y_{n},\beta)}{\sum_{n\in[N]}f(y_{n},\beta)}\right|\leq
2\|x-y\|_{\infty}$

for every $x,y\in\mathbb{R}^{n}$ such that $|x_{i}|\leq R,|y_{i}|\leq R$ for
all $i\in[N]$.

###### Proof.

If $\beta=\infty$, we have

$\displaystyle\lim_{\beta\to\infty}$
$\displaystyle\left(\left|\frac{\sum_{n\in[N]}x_{n}f(x_{n},\beta)}{\sum_{n\in[N]}f(x_{n},\beta)}-\frac{\sum_{n\in[N]}y_{n}f(y_{n},\beta)}{\sum_{n\in[N]}f(y_{n},\beta)}\right|\Big{/}\|x-y\|_{\infty}\right)=\frac{|\max_{n\in[N]}x_{n}-\max_{n\in[N]}y_{n}|}{\|x-y\|_{\infty}}\leq
1$

holds. Moreover, consider the following constrained optimization problem:

$\displaystyle\max_{{x,y\in\mathbb{R}^{n}}}\quad\left(\left|\frac{\sum_{n\in[N]}x_{n}f(x_{n},\beta)}{\sum_{n\in[N]}f(x_{n},\beta)}-\frac{\sum_{n\in[N]}y_{n}f(y_{n},\beta)}{\sum_{n\in[N]}f(y_{n},\beta)}\right|\Big{/}\|x-y\|_{\infty}\right)$
$\displaystyle\qquad\text{subject to }\qquad|x_{i}|\leq R,~{}~{}~{}|y_{i}|\leq
R~{}~{}~{}\text{ for all }i\in[N],$

whose optimum is denoted as $F(R,\beta)$. Then, since $\|x\|_{\infty}\leq R$
and $\|y\|_{\infty}\leq R$ is a compact set, by Berge’s Maximum Theorem
(Berge, 1877), we have that $F(R,\beta)$ is a continuous function for $\beta$.
Moreover, we know that $F(R,\infty)\leq 1$, which indicates that we can find a
large enough $\beta_{R}$ such that if $\beta>\beta_{R}$, $F(R,\beta)\leq 2$. ∎

Note that 5 does not hold if either $x_{i}$ or $y_{i}$ is unbounded. Now, we
will apply 5 to Equation 16. We can guarantee that
$\left|\text{Regret}_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]})\right|\leq\text{diam}(\Pi,\|\cdot\|_{2})TB$.

Also, note that the domain of $h:\mathbb{R}\to\mathbb{R}^{+}$ is effectively
_constrained_ to the range that
$\text{Regret}_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]})$ can achieve, which
means that we can regard $h$ as
$h:[-\text{diam}(\Pi,\|\cdot\|_{2})TB,\text{diam}(\Pi,\|\cdot\|_{2})TB]\to\mathbb{R}^{+}$.
Due to the continuity of $h^{\prime}$, and the fact that $h$ has a compact
domain, we know that $h(\cdot)$ is $C_{h}$-Lipschitz continuous for some
$C_{h}>0$ on this interval of
$[-\text{diam}(\Pi,\|\cdot\|_{2})TB,\text{diam}(\Pi,\|\cdot\|_{2})TB]$.

######  Lemma 12 (Lipschitzness of $C$ in Equation 16).

The function $C$ in Equation 16 is
$C_{\texttt{cost}}:=2C_{h}C_{\text{Reg}}$-Lipschitz continuous with respect to
$\theta$, if $k>k_{\text{diam}(\Pi,\|\cdot\|_{2})TB}$ for some
$k_{\text{diam}(\Pi,\|\cdot\|_{2})TB}>0$, i.e.,

$\displaystyle\Big{|}C\left((\ell_{t}^{(j)})_{t\in[T],j\in[N]},k,\theta_{1}\right)-C\left((\ell_{t}^{(j)})_{t\in[T],j\in[N]},k,\theta_{2}\right)\Big{|}\leq
C_{\texttt{cost}}\|\theta_{1}-\theta_{2}\|_{\text{LLM}}.$

###### Proof.

$\displaystyle\big{|}C(($
$\displaystyle\ell_{t}^{(j)})_{t\in[T],j\in[N]},k,\theta_{1})-C((\ell_{t}^{(j)})_{t\in[T],j\in[N]},k,\theta_{2})\big{|}$
$\displaystyle\underset{(i)}{\leq}2\|h(\text{Regret}_{\text{LLM}_{\theta_{1}}}((\ell_{t}^{(j)})_{t\in[T]}))-h(\text{Regret}_{\text{LLM}_{\theta_{2}}}((\ell_{t}^{(j)})_{t\in[T]}))\|_{\infty}$
$\displaystyle\underset{(ii)}{\leq}2C_{h}\|\text{Regret}_{\text{LLM}_{\theta_{1}}}((\ell_{t}^{(j)})_{t\in[T]})-\text{Regret}_{\text{LLM}_{\theta_{2}}}((\ell_{t}^{(j)})_{t\in[T]})\|_{\infty}$
$\displaystyle\underset{(iii)}{\leq}2C_{h}C_{\text{Reg}}\|\theta_{1}-\theta_{2}\|_{\text{LLM}}=C_{\texttt{cost}}\|\theta_{1}-\theta_{2}\|_{\text{LLM}}.$

Here, (i) holds due to 5, (ii) holds since $h$ is $C_{h}$-Lipschitz continuous
on the range of $\text{Regret}_{\text{LLM}_{\theta}}((\ell_{t})_{t\in[T]})$,
and (iii) holds due to Lemma 11. ∎

For completeness of the paper, we provide the definition of covering set and
covering number.

######  Definition 4 (Covering set and covering number).

For $\delta>0$, a metric space $(X,\|\cdot\|)$, and subset $Y\subseteq X$, set
$C\subset Y$ is a $\delta$-covering of $Y$ when $Y\subseteq\cup_{c\in
C}B(c,\delta,\|\cdot\|)$ holds. $\delta$-covering number
$N(\delta;Y,\|\cdot\|)$ is defined as the minimum cardinality of any covering
set.

By (Wainwright, 2019, Example 5.8), for any $r>0$, we can verify that the
$\delta$-covering number
$N(\delta;B(0,r,\|\cdot\|_{\text{LLM}}),\|\cdot\|_{\text{LLM}})$ can be
bounded by

$\displaystyle\log
N(\delta;B(0,r,\|\cdot\|_{\text{LLM}}),\|\cdot\|_{\text{LLM}})\leq
d_{\theta}\log(1+2r/\delta),$

where $d_{\theta}$ is the dimension of the LLM’s whole parameter. For example,
if we use the $\|\cdot\|_{\texttt{TF}}$ and consider the Transformer model as
defined in Section A.1, for any $r>0$,

$\displaystyle\log
N(\delta;B(0,r,\|\cdot\|_{\text{LLM}}),\|\cdot\|_{\text{LLM}})\leq
L(3Md^{2}+2d(dd^{\prime}+3md^{2}))\log(1+2r/\delta).$

Since we consider a compact $\Theta$ (as several recent works on analyzing
Transformers (Bai et al., 2023; Lin et al., 2024)), let
$R_{\Theta}:=\text{diam}(\Theta,\|\cdot\|_{\text{LLM}})$ (which corresponds to
$B_{\texttt{TF}}$ for the Transformer models as defined in Section A.1, with
$\|\cdot\|_{\text{LLM}}=\|\cdot\|_{\texttt{TF}}$), then there exists a set
$\Theta_{0}$ with $\log|\Theta_{0}|=d_{\theta}\log(1+2R_{\Theta}/\delta)$ such
that for any $\theta\in\Theta$, there exists a $\theta_{0}\in\Theta_{0}$ with

$\displaystyle\Big{|}C\left((\ell_{t}^{(j)})_{t\in[T],j\in[N]},k,\theta\right)-C\left((\ell_{t}^{(j)})_{t\in[T],j\in[N]},k,\theta_{0}\right)\Big{|}\leq
C_{\texttt{cost}}\delta.$

Then, by the standard result from statistical learning theory (Wainwright,
2019, Chapter 5), when trained with $N_{T}$ samples, for every
$0<\epsilon<1/2$, with probability at least $1-\epsilon$, we have

$\displaystyle\mathcal{L}(\widehat{\theta}_{k,N,N_{T}},k,N)$
$\displaystyle-\inf_{\theta\in\Theta}\mathcal{L}(\theta,k,N)\leq\sqrt{\frac{2(\log|\Theta_{0}|+\log(2/\epsilon))}{N_{T}}}+2C_{\texttt{cost}}\delta.$

Setting $\delta=\Omega(\sqrt{\log(\epsilon)/N_{T}})$, we further obtain

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

with probability at least $1-\epsilon$, completing the proof. ∎

See 1

###### Proof.

The limit on the right-hand side of Equation 5 remains as
$\widetilde{\mathcal{O}}\left(\sqrt{\frac{d_{\theta}+\log(1/\epsilon)}{N_{T}}}\right)$,
since we firstly take $\lim_{k\to\infty}$ and then take $\lim_{N\to\infty}$,
thanks to the fact that Theorem 2 holds for large enough $k$ and any $N$.
Next, we have

$\displaystyle\lim_{N\to\infty}\lim_{k\to\infty}\bigg{|}\mathcal{L}(\widehat{\theta}_{k,N,N_{T}},k,N)-h\left(\lim_{N\to\infty}\lim_{k\to\infty}\max_{\|\ell_{t}\|_{\infty}\leq
B}\text{Regret}_{\text{LLM}_{\widehat{\theta}_{k,N,N_{T}}}}((\ell_{t})_{t\in[T]})\right)\bigg{|}$
$\displaystyle\quad\leq\lim_{N\to\infty}\lim_{k\to\infty}\bigg{|}\mathcal{L}(\widehat{\theta}_{k,N,N_{T}},k,N)-h\left(\max_{\|\ell_{t}\|_{\infty}\leq
B}\text{Regret}_{\text{LLM}_{\widehat{\theta}_{k,N,N_{T}}}}((\ell_{t})_{t\in[T]})\right)\bigg{|}+$
$\displaystyle\quad\qquad\lim_{N\to\infty}\lim_{k\to\infty}\bigg{|}h\left(\max_{\|\ell_{t}\|_{\infty}\leq
B}\text{Regret}_{\text{LLM}_{\widehat{\theta}_{k,N,N_{T}}}}((\ell_{t})_{t\in[T]})\right)-h\left(\lim_{N\to\infty}\lim_{k\to\infty}\max_{\|\ell_{t}\|_{\infty}\leq
B}\text{Regret}_{\text{LLM}_{\widehat{\theta}_{k,N,N_{T}}}}((\ell_{t})_{t\in[T]})\right)\bigg{|}$
$\displaystyle\quad\leq\lim_{N\to\infty}\lim_{k\to\infty}\sup_{\theta\in\Theta}\bigg{|}\mathcal{L}({\theta},k,N)-h\left(\max_{\|\ell_{t}\|_{\infty}\leq
B}\text{Regret}_{\text{LLM}_{{\theta}}}((\ell_{t})_{t\in[T]})\right)\bigg{|}+0=0,$

due to the continuity of $h$ and 3. Finally, we have

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

due to 4, which, combined with the fact that $h$ is non-decreasing, completes
the proof. ∎

######  Remark 5 (Dynamic-regret loss).

So far, we have focused on the canonical online learning setting with regret
being the metric. One can also generalize the results to the non-stationary
setting, with dynamic regret being the metric. Specifically, one can define
the _dynamic-regret-loss_ function as follows:

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

Then, one can also establish similar results as before, since the analysis
does not utilize other properties of the regret except its boundedness, and
the Lipschitz-continuity of LLM with respect to $\theta$. To be specific,
Lemma 11 holds due to the reason that we can bound the difference of the
regret with the term

$\left|\sum_{t=1}^{T}\langle\ell_{t},(\text{LLM}_{\theta_{1}}(Z_{t-1})-\text{LLM}_{\theta_{2}}(Z_{t-1}))\rangle\right|,$

as well as the fact that $\inf_{\pi_{i}\in\Pi}\langle\ell_{i},\pi_{i}\rangle$
will be canceled. One can verify that all the arguments in Section D.2 also
hold for similar reasons.

###  D.4 Deferred Proof of Theorem 3

See 3

###### Proof.

We will locally use $\mathcal{A}=[d]$ without losing generality as
$\mathcal{A}$ is finite with $|\mathcal{A}|=d$, and will interchangeably use
$\ell_{i}(j)$ and $\ell_{ij}$ for notational convenience. Define
$a:=K^{\intercal}(Qc+q_{c})\in\mathbb{R}^{d}$ and
$b_{t-1}:=\beta\boldsymbol{1}_{t-1}:=k_{c}^{\intercal}(Qc+q_{c})\boldsymbol{1}_{t-1}\in\mathbb{R}^{t-1}$.
With $N=1$, $h(x)=x^{2}$, and the choice of $\Pi$, the loss function (Equation
3) can be written as follows:

$\displaystyle
f(V,a,(b_{t})_{t\in[T-1]},v_{c}):=\mathbb{E}\left(\sum_{t=1}^{T}\ell_{t}^{\intercal}(V\ell_{1:t-1}+v_{c}\boldsymbol{1}_{t-1}^{\intercal})\texttt{Softmax}(\ell_{1:t-1}^{\intercal}a+b_{t-1})+R_{\Pi}\|\sum_{t=1}^{T}\ell_{t}\|_{2}\right)^{2},$

where for $t=1$, we use the output of the single-layer self-attention as
$v_{c}$ and we will write it as
$(V\ell_{1:0}+v_{c}\boldsymbol{1}_{0}^{\intercal})\texttt{Softmax}(\ell_{1:0}^{\intercal}a+b_{0})$
for notational consistency with $t\geq 2$. Also, we will define empty sum
$\sum_{i=1}^{0}a_{i}=0$ for any sequence $(a_{i})_{i\in\mathbb{N}^{+}}$.

Step 1. Calculating $\frac{\partial f}{\partial a}$.

For $x\in[d]$, we calculate the corresponding directional derivative with the
following equation for $t\geq 2$:

$\displaystyle\frac{\partial}{\partial
a_{x}}\ell_{t}^{\intercal}(V\ell_{1:t-1}+v_{c}\boldsymbol{1}_{t-1}^{\intercal})\texttt{Softmax}(\ell_{1:t-1}^{\intercal}a+b_{t-1})$
$\displaystyle=\frac{\partial}{\partial
a_{x}}\sum_{i=1}^{t-1}\ell_{t}^{\intercal}(V\ell_{1:t-1}+v_{c}\boldsymbol{1}_{t-1}^{\intercal})e_{i}\frac{\exp(e_{i}^{\intercal}(\ell_{1:t-1}^{\intercal}a+b_{t-1}))}{\sum_{s=1}^{t-1}\exp(e_{s}^{\intercal}(\ell_{1:t-1}^{\intercal}a+b_{t-1}))}$
$\displaystyle=\frac{\sum_{i=1}^{t-1}\ell_{t}^{\intercal}(V\ell_{1:t-1}+v_{c}\boldsymbol{1}_{t-1}^{\intercal})e_{i}\exp(e_{i}^{\intercal}(\ell_{1:t-1}^{\intercal}a+b_{t-1}))\frac{\partial
e_{i}^{\intercal}(\ell_{1:t-1}^{\intercal}a+b_{t-1})}{\partial
a_{x}}(\sum_{s=1}^{t-1}\exp(e_{s}^{\intercal}(\ell_{1:t-1}^{\intercal}a+b_{t-1})))}{(\sum_{s=1}^{t-1}\exp(e_{s}^{\intercal}(\ell_{1:t-1}^{\intercal}a+b_{t-1})))^{2}}$
$\displaystyle\qquad-\frac{\sum_{i=1}^{t-1}\ell_{t}^{\intercal}(V\ell_{1:t-1}+v_{c}\boldsymbol{1}_{t-1}^{\intercal})e_{i}\exp(e_{i}^{\intercal}(\ell_{1:t-1}^{\intercal}a+b_{t-1}))\left(\sum_{s=1}^{t-1}\exp(e_{s}^{\intercal}(\ell_{1:t-1}^{\intercal}a+b_{t-1}))\frac{\partial
e_{s}^{\intercal}(\ell_{1:t-1}^{\intercal}a+b_{t-1})}{\partial
a_{x}}\right)}{(\sum_{s=1}^{t-1}\exp(e_{s}^{\intercal}(\ell_{1:t-1}^{\intercal}a+b_{t-1})))^{2}}.$

Plugging $a=\boldsymbol{0}_{d}$ and $v_{c}=\boldsymbol{0}_{d}$, and
$(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]}$ provides

$\displaystyle\frac{\partial}{\partial a_{x}}$
$\displaystyle\ell_{t}^{\intercal}(V\ell_{1:t-1}+v_{c}\boldsymbol{1}_{t-1}^{\intercal})\texttt{Softmax}(\ell_{1:t-1}^{\intercal}a+b_{t-1})\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=\boldsymbol{0}_{d},(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]}}$
$\displaystyle=\sum_{i=1}^{t-1}\frac{\ell_{t}^{\intercal}V\ell_{i}\ell_{ix}}{(t-1)}-\sum_{i=1}^{t-1}\frac{\ell_{t}^{\intercal}V\ell_{i}\left(\sum_{s=1}^{t-1}\ell_{sx}\right)}{(t-1)^{2}}.$

For $t=1$, as
$\ell_{t}^{\intercal}(V\ell_{1:t-1}+v_{c}\boldsymbol{1}_{t-1}^{\intercal})\texttt{Softmax}(\ell_{1:t-1}^{\intercal}a+b_{t-1})=\ell_{1}^{\intercal}v_{c}$,
$\frac{\partial}{\partial
a_{x}}\ell_{t}^{\intercal}(V\ell_{1:t-1}+v_{c}\boldsymbol{1}_{t-1}^{\intercal})\texttt{Softmax}(\ell_{1:t-1}^{\intercal}a+b_{t-1})\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=\boldsymbol{0}_{d},(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]}}=0$,
so we can use the same formula as $t\geq 2$ with empty sum $\sum_{i=1}^{t-1}$.
Using the above calculation, we can further compute $\frac{\partial
f}{\partial
a_{x}}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=\boldsymbol{0}_{d},(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]}}$
as follows:

$\displaystyle\frac{\partial f(V,a,(b_{t})_{t\in[T-1]},v_{c})}{\partial
a_{x}}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=\boldsymbol{0}_{d},(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]}}$
$\displaystyle=\mathbb{E}\frac{\partial}{\partial
a_{x}}\left(\sum_{t=1}^{T}\ell_{t}^{\intercal}(V\ell_{1:t-1}+v_{c}\boldsymbol{1}_{t-1}^{\intercal})\texttt{Softmax}(\ell_{1:t-1}^{\intercal}a+b_{t-1})+R_{\Pi}\|\sum_{t=1}^{T}\ell_{t}\|_{2}\right)^{2}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=\boldsymbol{0}_{d},(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]}}$
$\displaystyle=\mathbb{E}\Bigg{[}\left(\sum_{t=1}^{T}\ell_{t}^{\intercal}(V\ell_{1:t-1}+v_{c}\boldsymbol{1}_{t-1}^{\intercal})\texttt{Softmax}(\ell_{1:t-1}^{\intercal}a+b_{t-1})+R_{\Pi}\|\sum_{t=1}^{T}\ell_{t}\|_{2}\right)\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=\boldsymbol{0}_{d},(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]}}$
$\displaystyle\qquad\qquad\frac{\partial}{\partial
a_{x}}\left(\sum_{t=1}^{T}\ell_{t}^{\intercal}(V\ell_{1:t-1}+v_{c}\boldsymbol{1}_{t-1}^{\intercal})\texttt{Softmax}(\ell_{1:t-1}^{\intercal}a+b_{t-1})+R_{\Pi}\|\sum_{t=1}^{T}\ell_{t}\|_{2}\right)\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=\boldsymbol{0}_{d},(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]}}\Bigg{]}$
$\displaystyle=\mathbb{E}\Bigg{[}\left(\sum_{t=1}^{T}\ell_{t}^{\intercal}V\sum_{i=1}^{t-1}\frac{1}{t-1}\ell_{i}+R_{\Pi}\|\sum_{t=1}^{T}\ell_{t}\|_{2}\right)\sum_{t=1}^{T}\left(\sum_{i=1}^{t-1}\frac{\ell_{t}^{\intercal}V\ell_{i}\ell_{ix}}{(t-1)}-\sum_{i=1}^{t-1}\frac{\ell_{t}^{\intercal}V\ell_{i}\left(\sum_{s=1}^{t-1}\ell_{sx}\right)}{(t-1)^{2}}\right)\Bigg{]}$
(17) $\displaystyle=0,$

where we used the fact that $\ell_{i}$ is drawn from a symmetric distribution,
and flipping the sign of the variable as $-\ell_{i}$ yields the same
distribution, which leads to the following:

$\displaystyle\mathbb{E}\Bigg{[}\left(\sum_{t=1}^{T}\ell_{t}^{\intercal}V\sum_{i=1}^{t-1}\frac{1}{t-1}\ell_{i}+R_{\Pi}\|\sum_{t=1}^{T}\ell_{t}\|_{2}\right)\sum_{t=1}^{T}\left(\sum_{i=1}^{t-1}\frac{\ell_{t}^{\intercal}V\ell_{i}\ell_{ix}}{(t-1)}-\sum_{i=1}^{t-1}\frac{\ell_{t}^{\intercal}V\ell_{i}\left(\sum_{s=1}^{t-1}\ell_{sx}\right)}{(t-1)^{2}}\right)\Bigg{]}$
$\displaystyle\quad=\mathbb{E}\Bigg{[}\left(\sum_{t=1}^{T}\ell_{t}^{\intercal}V\sum_{i=1}^{t-1}\frac{1}{t-1}\ell_{i}+R_{\Pi}\|\sum_{t=1}^{T}\ell_{t}\|_{2}\right)\sum_{t=1}^{T}\left(-\sum_{i=1}^{t-1}\frac{\ell_{t}^{\intercal}V\ell_{i}\ell_{ix}}{(t-1)}+\sum_{i=1}^{t-1}\frac{\ell_{t}^{\intercal}V\ell_{i}\left(\sum_{s=1}^{t-1}\ell_{sx}\right)}{(t-1)^{2}}\right)\Bigg{]}.$

This yields Equation 17=0.

Step 2. Calculating $\frac{\partial f}{\partial v_{c}}$.

We will use the following equation for $t\geq 2$:

$\displaystyle\frac{\partial}{\partial v_{c}}$
$\displaystyle\ell_{t}^{\intercal}(V\ell_{1:t-1}+v_{c}\boldsymbol{1}_{t-1}^{\intercal})\texttt{Softmax}(\ell_{1:t-1}^{\intercal}a+b_{t-1})$
$\displaystyle=\frac{\partial}{\partial
v_{c}}\sum_{i=1}^{t-1}\ell_{t}^{\intercal}(V\ell_{1:t-1}+v_{c}\boldsymbol{1}_{t-1}^{\intercal})e_{i}\frac{\exp(e_{i}^{\intercal}(\ell_{1:t-1}^{\intercal}a+b_{t-1}))}{\sum_{s=1}^{t-1}\exp(e_{s}^{\intercal}(\ell_{1:t-1}^{\intercal}a+b_{t-1}))}=\ell_{t}.$

For $t=1$, we define $\frac{\partial}{\partial
v_{c}}\ell_{1}^{\intercal}(V\ell_{1:0}+v_{c}\boldsymbol{1}_{0}^{\intercal})\texttt{Softmax}(\ell_{1:0}^{\intercal}a+b_{0})=\ell_{1}$,
so that we can use the same formula as $t\geq 2$. Therefore, we can calculate
$\frac{\partial f}{\partial
v_{c}}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=\boldsymbol{0}_{d},(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]}}$
as follows:

$\displaystyle\frac{\partial f(V,a,(b_{t})_{t\in[T-1]},v_{c})}{\partial
v_{c}}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=\boldsymbol{0}_{d},(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]}}$
$\displaystyle=\mathbb{E}\frac{\partial}{\partial
v_{c}}\left(\sum_{t=1}^{T}\ell_{t}^{\intercal}(V\ell_{1:t-1}+v_{c}\boldsymbol{1}_{t-1}^{\intercal})\texttt{Softmax}(\ell_{1:t-1}^{\intercal}a+b_{t-1})+R_{\Pi}\|\sum_{t=1}^{T}\ell_{t}\|_{2}\right)^{2}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=\boldsymbol{0}_{d},(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]}}$
$\displaystyle=\mathbb{E}\Bigg{[}\left(\sum_{t=1}^{T}\ell_{t}^{\intercal}(V\ell_{1:t-1}+v_{c}\boldsymbol{1}_{t-1}^{\intercal})\texttt{Softmax}(\ell_{1:t-1}^{\intercal}a+b_{t-1})+R_{\Pi}\|\sum_{t=1}^{T}\ell_{t}\|_{2}\right)\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=\boldsymbol{0}_{d},(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]}}$
$\displaystyle\qquad\qquad\frac{\partial}{\partial
v_{c}}\left(\sum_{t=1}^{T}\ell_{t}^{\intercal}(V\ell_{1:t-1}+v_{c}\boldsymbol{1}_{t-1}^{\intercal})\texttt{Softmax}(\ell_{1:t-1}^{\intercal}a+b_{t-1})+R_{\Pi}\|\sum_{t=1}^{T}\ell_{t}\|_{2}\right)\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=\boldsymbol{0}_{d},(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]}}\Bigg{]}$
$\displaystyle=\mathbb{E}\Bigg{[}\left(\sum_{t=2}^{T}\ell_{t}^{\intercal}V\sum_{i=1}^{t-1}\frac{1}{t-1}\ell_{i}+R_{\Pi}\|\sum_{t=1}^{T}\ell_{t}\|_{2}\right)\sum_{t=1}^{T}\ell_{t}\Bigg{]}=0.$

The last line is due to the same reason as the last part of Step 1.

Step 3. Calculating $\frac{\partial f}{\partial V}$.

We calculate the following equation, which will be used to calculate
$\frac{\partial f}{\partial
V}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=\boldsymbol{0}_{d},(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]}}$
for $t\geq 2$:

$\displaystyle\frac{\partial}{\partial V}$
$\displaystyle\ell_{t}^{\intercal}(V\ell_{1:t-1}+v_{c}\boldsymbol{1}_{t-1}^{\intercal})\texttt{Softmax}(\ell_{1:t-1}^{\intercal}a+b_{t-1})\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=\boldsymbol{0}_{d},(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]}}$
$\displaystyle=\frac{\partial}{\partial
V}\sum_{i=1}^{t-1}\ell_{t}^{\intercal}(V\ell_{1:t-1}+v_{c}\boldsymbol{1}_{t-1}^{\intercal})e_{i}\frac{\exp(e_{i}^{\intercal}(\ell_{1:t-1}^{\intercal}a+b_{t-1}))}{\sum_{s=1}^{t-1}\exp(e_{s}^{\intercal}(\ell_{1:t-1}^{\intercal}a+b_{t-1}))}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=\boldsymbol{0}_{d},(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]}}$
$\displaystyle=\sum_{i=1}^{t-1}\ell_{t}\ell_{i}^{\intercal}\frac{\exp(e_{i}^{\intercal}(\ell_{1:t-1}^{\intercal}a+b_{t-1}))}{\sum_{s=1}^{t-1}\exp(e_{s}^{\intercal}(\ell_{1:t-1}^{\intercal}a+b_{t-1}))}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=\boldsymbol{0}_{d},(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]}}=\sum_{i=1}^{t-1}\frac{1}{t-1}\ell_{t}\ell_{i}^{\intercal}.$

For $t=1$, note that $\frac{\partial}{\partial
V}\ell_{t}^{\intercal}v_{c}=\boldsymbol{O}_{d\times d}$, so we can use the
same formula as $t\geq 2$ with empty sum $\sum_{i=1}^{t-1}$.

Therefore, we have

$\displaystyle\frac{\partial f(V,a,(b_{t})_{t\in[T-1]},v_{c})}{\partial
V}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=\boldsymbol{0}_{d},(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]}}$
$\displaystyle=\mathbb{E}\frac{\partial}{\partial
V}\left(\sum_{t=1}^{T}\ell_{t}^{\intercal}(V\ell_{1:t-1}+v_{c}\boldsymbol{1}_{t-1}^{\intercal})\texttt{Softmax}(\ell_{1:t-1}^{\intercal}a+b_{t-1})+R_{\Pi}\|\sum_{t=1}^{T}\ell_{t}\|_{2}\right)^{2}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=\boldsymbol{0}_{d},(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]}}$
$\displaystyle=\mathbb{E}\Bigg{[}\left(\sum_{t=1}^{T}\ell_{t}^{\intercal}(V\ell_{1:t-1}+v_{c}\boldsymbol{1}_{t-1}^{\intercal})\texttt{Softmax}(\ell_{1:t-1}^{\intercal}a+b_{t-1})+R_{\Pi}\|\sum_{t=1}^{T}\ell_{t}\|_{2}\right)\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=\boldsymbol{0}_{d},(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]}}$
$\displaystyle\qquad\qquad\frac{\partial}{\partial
V}\left(\sum_{t=1}^{T}\ell_{t}^{\intercal}(V\ell_{1:t-1}+v_{c}\boldsymbol{1}_{t-1}^{\intercal})\texttt{Softmax}(\ell_{1:t-1}^{\intercal}a+b_{t-1})+R_{\Pi}\|\sum_{t=1}^{T}\ell_{t}\|_{2}\right)\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=\boldsymbol{0}_{d},(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]}}\Bigg{]}$
$\displaystyle=\mathbb{E}\Bigg{[}\left(\sum_{t=1}^{T}\ell_{t}^{\intercal}V\sum_{i=1}^{t-1}\frac{1}{t-1}\ell_{i}+R_{\Pi}\|\sum_{t=1}^{T}\ell_{t}\|_{2}\right)\sum_{t=1}^{T}\sum_{i=1}^{t-1}\frac{1}{t-1}\ell_{t}\ell_{i}^{\intercal}\Bigg{]}$
$\displaystyle=\mathbb{E}\Bigg{[}\left(\sum_{t=1}^{T}\sum_{i=1}^{t-1}\left(\frac{1}{t-1}\ell_{t}^{\intercal}V\ell_{i}\right)\left(\frac{1}{t-1}\ell_{t}\ell_{i}^{\intercal}\right)+R_{\Pi}T\|\sum_{t^{\prime}=1}^{T}\ell_{t^{\prime}}\|_{2}\ell_{t}\ell_{i}^{\intercal}\right)\Bigg{]}$
$\displaystyle=\mathbb{E}\Bigg{[}\left(\sum_{t=1}^{T}\sum_{i=1}^{t-1}\sum_{x=1}^{d}\sum_{y=1}^{d}v_{xy}\ell_{tx}\ell_{iy}\left(\frac{1}{t-1}\right)^{2}[\ell_{tz}\ell_{iw}]_{(z,w)}+R_{\Pi}T\|\sum_{t^{\prime}=1}^{T}\ell_{t^{\prime}}\|_{2}\ell_{t}\ell_{i}^{\intercal}\right)\Bigg{]}$
$\displaystyle=\sum_{t=1}^{T}\sum_{i=1}^{t-1}\sum_{x=1}^{d}\sum_{y=1}^{d}\frac{1}{(t-1)^{2}}[\sigma_{xz}v_{xy}\sigma_{yw}]_{(z,w)}+\mathbb{E}\Bigg{[}R_{\Pi}T\|\sum_{t^{\prime}=1}^{T}\ell_{t^{\prime}}\|_{2}\ell_{t}\ell_{i}^{\intercal}\Bigg{]}$
$\displaystyle=\left(\sum_{t=1}^{T-1}\frac{1}{t}\right)\Sigma
V\Sigma+\mathbb{E}\Bigg{[}R_{\Pi}T\|\sum_{t^{\prime}=1}^{T}\ell_{t^{\prime}}\|_{2}\ell_{t}\ell_{i}^{\intercal}\Bigg{]}.$

Therefore, if
$V^{\star}=R_{\Pi}\frac{T}{\sum_{t=1}^{T-1}1/t}\Sigma^{-1}\mathbb{E}\Bigg{[}\|\sum_{t=1}^{T}\ell_{t}\|_{2}\ell_{t}\ell_{i}^{\intercal}\Bigg{]}\Sigma^{-1}$,
then $\frac{\partial f}{\partial
V}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=\boldsymbol{0}_{d},(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]},V=V^{\star}}=\bm{O}_{d\times
d}$. Lastly, we have

$\displaystyle\frac{\partial f}{\partial
K}\big{|}_{K^{\intercal}(Qc+q_{c})=v_{c}=\boldsymbol{0}_{d},V=V^{\star}}=\left(\frac{\partial
f}{\partial a}\frac{\partial a}{\partial
K}\right)\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=\boldsymbol{0}_{d},(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]},V=V^{\star}}=\boldsymbol{O}_{d\times
d}$ $\displaystyle\frac{\partial f}{\partial
Q}\big{|}_{K^{\intercal}(Qc+q_{c})=v_{c}=\boldsymbol{0}_{d},V=V^{\star}}=\left(\frac{\partial
f}{\partial a}\frac{\partial a}{\partial
Q}\right)\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=\boldsymbol{0}_{d},(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]},V=V^{\star}}=\boldsymbol{O}_{d\times
d}$ $\displaystyle\frac{\partial f}{\partial
q_{c}}\big{|}_{K^{\intercal}(Qc+q_{c})=v_{c}=\boldsymbol{0}_{d},V=V^{\star}}=\left(\frac{\partial
f}{\partial a}\frac{\partial a}{\partial
q_{c}}\right)\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=\boldsymbol{0}_{d},(b_{t}=\beta\boldsymbol{1}_{t})_{t\in[T-1]},V=V^{\star}}=\boldsymbol{0}_{d}$

which means that such configurations are first-order stationary points of
Equation 3 with $N=1$, $h(x)=x^{2}$, and $\Pi=B(0,R_{\Pi},\|\cdot\|)$. ∎

###  D.5 Deferred Proof of Theorem 4

See 4

###### Proof.

The output of the single-layer linear self-attention structure is as follows:

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

which can be expressed with a larger class

$\displaystyle
g(Z_{t},\mathbb{A},\beta,\mathbb{C},\delta):=\sum_{i=1}^{t}(\mathbb{A}\ell_{i}\ell_{i}^{\intercal}\beta+\mathbb{C}\ell_{i}+\delta),$
(19)

where $\mathbb{A}\in\mathbb{R}^{d\times d}$,
$\beta,\mathbb{C},\delta\in\mathbb{R}^{d}$. Then, if a minimizer of

$\displaystyle f(\mathbb{A},\beta,\mathbb{C},\delta):$
$\displaystyle=\mathbb{E}\left(\sum_{t=1}^{T}\langle\ell_{t},\sum_{i=1}^{t-1}\left(\mathbb{A}\ell_{i}\ell_{i}^{\intercal}\beta+\mathbb{C}\ell_{i}+\delta\right)\rangle-\inf_{\pi\in\Pi}\left\langle\sum_{t=1}^{T}\ell_{t},\pi\right\rangle\right)^{2}$

can be expressed as
$\mathbb{A}=V,\beta=K^{\intercal}(Qc+q_{c}),\mathbb{C}=Vk_{c}^{\intercal}(Qc+q_{c})+v_{c}(Qc+q_{c})^{\intercal}K,\beta=v_{c}k_{c}^{\intercal}(Qc+q_{c})$,
then we can conclude that the corresponding $V,Q,K,v_{c},q_{c},k_{c}$ are also
a minimizer of

$\displaystyle\mathbb{E}\left(\sum_{t=1}^{T}\langle\ell_{t},g(Z_{t-1})\rangle-\inf_{\pi\in\Pi}\left\langle\sum_{t=1}^{T}\ell_{i},\pi\right\rangle\right)^{2},$

since the corresponding $V,Q,K,v_{c},q_{c},k_{c}$ constitute a minimizer among
a larger class. Now, since $\Pi=B(\boldsymbol{0}_{d},R_{\Pi},\|\cdot\|)$, we
can rewrite $f$ as

$\displaystyle
f(\mathbb{A},\beta,\mathbb{C},\delta)=\mathbb{E}\left(\sum_{t=1}^{T}\langle\ell_{t},\sum_{i=1}^{t-1}\left(\mathbb{A}\ell_{i}\ell_{i}^{\intercal}\beta+\mathbb{C}\ell_{i}+\delta\right)\rangle+R_{\Pi}\bigg{\|}\sum_{t=1}^{T}\ell_{i}\bigg{\|}_{2}\right)^{2}.$
(20)

Step 1. Finding condition for $\frac{\partial f}{\partial\delta}=0$.

Due to the Leibniz rule, if we calculate the partial derivative of Equation 20
w.r.t. $\delta$, we have

$\displaystyle\frac{\partial
f(\mathbb{A},\beta,\mathbb{C},\delta)}{\partial\delta}=\frac{\partial}{\partial\delta}\mathbb{E}\left(\sum_{t=1}^{T}\langle\ell_{t},\sum_{i=1}^{t-1}\left(\mathbb{A}\ell_{i}\ell_{i}^{\intercal}\beta+\mathbb{C}\ell_{i}+\delta\right)\rangle+R_{\Pi}\|\sum_{t=1}^{T}\ell_{t}\|_{2}\right)^{2}$
$\displaystyle\qquad=\mathbb{E}\frac{\partial}{\partial\delta}\left(\sum_{t=1}^{T}\langle\ell_{t},\sum_{i=1}^{t-1}\left(\mathbb{A}\ell_{i}\ell_{i}^{\intercal}\beta+\mathbb{C}\ell_{i}+\delta\right)\rangle+R_{\Pi}\|\sum_{t=1}^{T}\ell_{t}\|_{2}\right)^{2}$
$\displaystyle\qquad=\mathbb{E}\sum_{t=1}^{T}\ell_{t}\left(\sum_{t=1}^{T}\sum_{i=1}^{t-1}(t-1)\ell_{t}^{\intercal}\left(\mathbb{A}\ell_{i}\ell_{i}^{\intercal}\beta+\mathbb{C}\ell_{i}+\delta\right)+R_{\Pi}\|\sum_{t=1}^{T}\ell_{t}\|\right).$
(21)

Since the expectation of either odd-order polynomial or even-order polynomial
times $\|\cdot\|_{2}$ is 0, due to that $\ell_{t}$ follows a symmetric
distribution, we have

$\displaystyle\mathbb{E}\sum_{t=1}^{T}(t-1)\ell_{t}R_{\Pi}\Big{\|}\sum_{t=1}^{T}\ell_{t}\Big{\|}_{2}=0,\qquad\mathbb{E}\sum_{t=1}^{T}(t-1)\ell_{t}\sum_{t=1}^{T}\sum_{i=1}^{t-1}\ell_{t}^{\intercal}\mathbb{C}\ell_{i}=0.$

Now, we calculate

$\displaystyle\mathbb{E}\sum_{t=1}^{T}$
$\displaystyle(t-1)\ell_{t}\sum_{t=1}^{T}\sum_{i=1}^{t-1}\ell_{t}^{\intercal}\mathbb{A}\ell_{i}\ell_{i}^{\intercal}\beta=\mathbb{E}\sum_{t_{1}=1}^{T}\sum_{t=1}^{T}\sum_{i=1}^{t-1}(t_{1}-1)\ell_{t_{1}}\ell_{t}^{\intercal}\mathbb{A}\ell_{i}\ell_{i}^{\intercal}\beta$
$\displaystyle\underset{(i)}{=}\mathbb{E}\sum_{t=1}^{T}\sum_{i=1}^{t-1}(t-1)\ell_{t}\ell_{t}^{\intercal}\mathbb{A}\ell_{i}\ell_{i}^{\intercal}\beta=\mathbb{E}\sum_{t=1}^{T}(t-1)^{2}\ell_{t}\ell_{t}^{\intercal}\mathbb{A}\Sigma\beta=\frac{1}{6}T(2T^{2}-3T+1)\Sigma\mathbb{A}\Sigma\beta,$

where $(i)$ holds since if $t_{1}\neq t$, due to the independence of
$\ell_{t}$, $\ell_{t_{1}}$, we can use $\mathbb{E}\ell_{t}=0$. Lastly,

$\displaystyle\mathbb{E}\sum_{t=1}^{T}$
$\displaystyle(t-1)\ell_{t}\sum_{t=1}^{T}\sum_{i=1}^{t-1}\ell_{t}^{\intercal}\delta=\mathbb{E}\sum_{t_{1}=1}^{T}\sum_{t=1}^{T}(t_{1}-1)(t-1)\ell_{t_{1}}\ell_{t}^{\intercal}\delta=\frac{1}{6}T(2T^{2}-3T+1)\Sigma\delta.$

Plugging the above equations into Equation 21, we have

$\displaystyle\frac{\partial
f(\mathbb{A},\beta,\mathbb{C},\delta)}{\partial\delta}=\frac{1}{6}T(2T^{2}-3T+1)(\Sigma\mathbb{A}\Sigma\beta+\Sigma\delta).$

Due to the optimality condition, we have

$\displaystyle\mathbb{A}\Sigma\beta+\delta=0.$ (22)

Step 2. Plugging the optimality condition for $\frac{\partial
f}{\partial\delta}$ into Equation 20.

Plugging Equation 22 to Equation 20, $f$ can be written as

$\displaystyle f(\mathbb{A},$
$\displaystyle\beta,\mathbb{C},-\mathbb{A}\Sigma\beta)=\mathbb{E}\left(\sum_{t=1}^{T}\sum_{i=1}^{t-1}\ell_{t}^{\intercal}\left(\mathbb{A}(\ell_{i}\ell_{i}^{\intercal}-\Sigma)\beta+\mathbb{C}\ell_{i}\right)+R_{\Pi}\bigg{\|}\sum_{t=1}^{T}\ell_{t}\bigg{\|}_{2}\right)^{2}$
$\displaystyle=\underbrace{\mathbb{E}\left(\sum_{t=1}^{T}\sum_{i=1}^{t-1}\ell_{t}^{\intercal}\mathbb{A}(\ell_{i}\ell_{i}^{\intercal}-\Sigma)\beta\right)^{2}}_{(i)}+\mathbb{E}\left(\sum_{t=1}^{T}\sum_{i=1}^{t-1}\ell_{t}^{\intercal}\mathbb{C}\ell_{i}\right)^{2}+\mathbb{E}\left(R_{\Pi}\bigg{\|}\sum_{t=1}^{T}\ell_{t}\bigg{\|}_{2}\right)^{2}$
$\displaystyle\quad+\underbrace{2\mathbb{E}\left(\sum_{t=1}^{T}\sum_{i=1}^{t-1}\ell_{t}^{\intercal}\mathbb{A}(\ell_{i}\ell_{i}^{\intercal}-\Sigma)\beta\right)\left(\sum_{t=1}^{T}\sum_{i=1}^{t-1}\ell_{t}^{\intercal}\mathbb{C}\ell_{i}\right)}_{(ii)}$
$\displaystyle\qquad+\underbrace{2\mathbb{E}\left(\sum_{t=1}^{T}\sum_{i=1}^{t-1}\ell_{t}^{\intercal}\mathbb{A}(\ell_{i}\ell_{i}^{\intercal}-\Sigma)\beta\right)\left(R_{\Pi}\bigg{\|}\sum_{t=1}^{T}\ell_{t}\bigg{\|}_{2}\right)}_{(iii)}$
$\displaystyle\qquad\quad+2\mathbb{E}\left(\sum_{t=1}^{T}\sum_{i=1}^{t-1}\ell_{t}^{\intercal}\mathbb{C}\ell_{i}\right)\left(R_{\Pi}\bigg{\|}\sum_{t=1}^{T}\ell_{t}\bigg{\|}_{2}\right).$

For the part $(i)$, we have

$\displaystyle\mathbb{E}$
$\displaystyle\left(\sum_{t=1}^{T}\sum_{i=1}^{t-1}\ell_{t}^{\intercal}\mathbb{A}(\ell_{i}\ell_{i}^{\intercal}-\Sigma)\beta\right)^{2}=\mathbb{E}\left[\sum_{t_{1}=1}^{T}\sum_{i_{1}=1}^{t_{1}-1}\sum_{t=1}^{T}\sum_{i=1}^{t-1}\beta^{\intercal}(\ell_{i_{1}}\ell_{i_{1}}^{\intercal}-\Sigma)\mathbb{A}^{\intercal}\ell_{t_{1}}\ell_{t}^{\intercal}\mathbb{A}(\ell_{i}\ell_{i}^{\intercal}-\Sigma)\beta\right]$
$\displaystyle\qquad\underset{(1)}{=}\mathbb{E}\left[\sum_{t=1}^{T}\sum_{i_{1}=1}^{t-1}\sum_{i=1}^{t-1}\beta^{\intercal}(\ell_{i_{1}}\ell_{i_{1}}^{\intercal}-\Sigma)\mathbb{A}^{\intercal}\ell_{t}\ell_{t}^{\intercal}\mathbb{A}(\ell_{i}\ell_{i}^{\intercal}-\Sigma)\beta\right]$
$\displaystyle\qquad\underset{(2)}{=}\mathbb{E}\left[\sum_{t=1}^{T}\sum_{i=1}^{t-1}\beta^{\intercal}(\ell_{i}\ell_{i}^{\intercal}-\Sigma)\mathbb{A}^{\intercal}\ell_{i}\ell_{i}^{\intercal}\mathbb{A}(\ell_{i}\ell_{i}^{\intercal}-\Sigma)\beta\right]$
$\displaystyle\qquad=\frac{(T-1)T}{2}\beta^{\intercal}\mathbb{E}\left[(\ell_{i}\ell_{i}^{\intercal}-\Sigma)\mathbb{A}^{\intercal}\Sigma\mathbb{A}(\ell_{i}\ell_{i}^{\intercal}-\Sigma)\right]\beta$
(23)
$\displaystyle\qquad=\frac{(T-1)T}{2}\beta^{\intercal}\mathbb{E}\left[(\sqrt{\Sigma}A(\ell_{i}\ell_{i}^{\intercal}-\Sigma))^{\intercal}(\sqrt{\Sigma}A(\ell_{i}\ell_{i}^{\intercal}-\Sigma))\right]\beta.$

Here, $(1)$ holds because if $t_{1}\neq t$, we know that
$\mathbb{E}\ell_{t_{1}}=\mathbb{E}\ell_{t}=0$, and they are independent, and
$(2)$ holds because if $i_{1}\neq i$, we can calculate
$\mathbb{E}(\ell_{i_{1}}\ell_{i_{1}}^{\intercal}-\Sigma)=\bm{O}_{d\times d}$.
In addition, we can easily check that $(ii)$ and $(iii)$ are $0$ as they are
polynomials of odd degrees and we have $Z\overset{d}{=}-Z$. Note that Equation
23 is minimized when
$\mathbb{P}(\sqrt{\Sigma}\mathbb{A}(\ell_{i}\ell_{i}^{\intercal}-\Sigma)\beta=\boldsymbol{0}_{d})=1$.

If $\mathbb{A}\neq\bm{O}_{d\times d}$, suppose that the singular value
decomposition of $A=U\Lambda V$ yields that $\Lambda$ is a diagonal matrix
whose first diagonal element is non-zero, and $U,V$ are orthogonal matrices.
Then, we want to find $\beta$ that $\sqrt{\Sigma}U\Lambda
V(\ell_{i}\ell_{i}^{\intercal}-\Sigma)\beta=\boldsymbol{0}_{d}$ for any
$\ell_{i}$ such that $p(\ell_{i})\neq 0$, where $p$ indicates the probability
density function of loss vectors. Since $\Sigma$ and $U$ are invertible, we
only need to consider $\Lambda
V(\ell_{i}\ell_{i}^{\intercal}-\Sigma)\beta=\boldsymbol{0}_{d}$. Since
$\Lambda$’s first diagonal component is non-zero, we will consider equation
$e_{1}^{\intercal}\Lambda V(\ell_{i}\ell_{i}^{\intercal}-\Sigma)\beta=0$. This
is equivalent to $V_{1}(\ell_{i}\ell_{i}^{\intercal}-\Sigma)\beta=0$, where
$V_{1}$ is the first row of $V$, and is a non-zero vector.

Now, we will generally consider $a_{x,y}(v):=vv^{\intercal}x-y$ where
$x,y,v\in\mathbb{R}^{d}$ and
$a_{x,y}:B(\boldsymbol{0}_{d},2\epsilon_{1},\|\cdot\|)\to\mathbb{R}^{d}$
function. Then, we can check that the Jacobian of $a_{x,y}(v)$ is
$vx^{\intercal}+(v\cdot x)I$, and we can find that the determinant of the
Jacobian is nonzero when $v=\epsilon_{1}x$ if $x\neq\boldsymbol{0}_{d}$.
Therefore, the volume of $(V_{1}(\ell_{i}\ell_{i}^{\intercal}-\Sigma))$ for
$\ell_{i}\in B(\boldsymbol{0}_{d},c_{z},\|\cdot\|)$ is greater than the volume
of $(V_{1}(vv^{\intercal}-\Sigma))$ for $v\in
B(\epsilon_{1}V_{1}^{\intercal},\epsilon_{2},\|\cdot\|)$, where $c_{z}$ is a
constant such that
$B(\boldsymbol{0}_{d},c_{z},\|\cdot\|)\subseteq\text{supp}(Z)$, and
$\epsilon_{1},\epsilon_{2}>0$ satisfy that
$\epsilon_{1}|V_{1}|+\epsilon_{2}<c_{z}$. Here, we define $\epsilon_{2}>0$
sufficiently small so that the determinant of
$\text{Jacobian}(vv^{\intercal}V_{1}^{\intercal}-\Sigma V_{1}^{\intercal})>0$
for $v\in B(\epsilon_{1}V_{1}^{\intercal},\epsilon_{2},\|\cdot\|)$, and $v\to
vv^{\intercal}V_{1}^{\intercal}-\Sigma V_{1}^{\intercal}$ is a one-to-one
correspondence, by inverse function theorem. Therefore, the volume of
$(V_{1}(vv^{\intercal}-\Sigma))$ for $v\in
B(\epsilon_{1}V_{1}^{\intercal},\epsilon_{2},\|\cdot\|)$ can be calculated as

$\displaystyle[\text{Volume $(V_{1}(vv^{\intercal}-\Sigma))$ for $v\in
B(\epsilon_{1}V_{1}^{\intercal},\epsilon_{2},\|\cdot\|)$}]=\int_{v\in
B(\epsilon_{1}V_{1}^{\intercal},\epsilon_{2},\|\cdot\|)}\big{|}\text{det(Jacobian}(V_{1}(vv^{\intercal}-\Sigma)))\big{|}dv>0.$

Therefore, $\text{Volume}(V_{1}(vv^{\intercal}-\Sigma))$ where $v\in
B(\epsilon_{1}V_{1}^{\intercal},\epsilon_{2},\|\cdot\|)$ is non-zero, so that
we can find $d$ loss vectors $\\{\ell_{i}\\}_{i\in[d]}$ such that the vectors
$\\{V_{1}(\ell_{i}\ell_{i}^{\intercal}-\Sigma)\\}_{i\in[d]}$ are linearly
independent. Hence, if we want to minimize Equation 23, either
$A=\bm{O}_{d\times d}$ or $\beta=\boldsymbol{0}_{d}$ should hold. In both
cases, Equation 19 can be re-written as

$\displaystyle
g(Z_{t};\mathbb{A},\beta,\mathbb{C},\delta):=\sum_{i=1}^{t}\mathbb{C}\ell_{i},$

and this is covered by the original parametrization (Equation 18) with
$K^{\intercal}(Qc+q_{c})=v_{c}=\boldsymbol{0}_{d}$.

Step 3. Calculating $\frac{\partial f}{\partial\mathbb{C}}$.

Now, we optimize over $\mathbb{C}$, by minimizing the following objective:

$\displaystyle f(\mathbb{C}):$
$\displaystyle=\mathbb{E}\left(\sum_{t=1}^{T}\sum_{i=1}^{t-1}\ell_{t}^{\intercal}\mathbb{C}\ell_{i}+R_{\Pi}\|\sum_{t=1}^{T}\ell_{t}\|\right)^{2}$
$\displaystyle=\underbrace{\mathbb{E}\left(\sum_{t=1}^{T}\sum_{i=1}^{t-1}\ell_{t}^{\intercal}\mathbb{C}\ell_{i}\right)^{2}}_{(i)}+{2\mathbb{E}\left(\left(\sum_{t=1}^{T}\sum_{i=1}^{t-1}\ell_{t}^{\intercal}\mathbb{C}\ell_{i}\right)R_{\Pi}\|\sum_{t=1}^{T}\ell_{t}\|\right)}+\mathbb{E}\left(R_{\Pi}\|\sum_{t=1}^{T}\ell_{t}\|\right)^{2}$
$\displaystyle=\frac{T(T-1)}{2}\mathop{\mathrm{Tr}}\left(\mathbb{C}^{\intercal}\Sigma\mathbb{C}\Sigma\right)+{2\mathbb{E}\left(B\sum_{t=1}^{T}\sum_{i=1}^{t-1}\ell_{t}^{\intercal}\mathbb{C}\ell_{i}\|\sum_{j=1}^{T}\ell_{j}\|\right)}+\mathbb{E}\left(R_{\Pi}\|\sum_{t=1}^{T}\ell_{t}\|\right)^{2}.$

Here, $(i)$ can be calculated as follows:

$\displaystyle\mathbb{E}$
$\displaystyle\left(\sum_{t=1}^{T}\sum_{i=1}^{t-1}\ell_{t}^{\intercal}\mathbb{C}\ell_{i}\right)^{2}=\mathbb{E}\left(\sum_{t_{1}=1}^{T}\sum_{i_{1}=1}^{t_{1}-1}\sum_{t=1}^{T}\sum_{i=1}^{t-1}\ell_{i_{1}}^{\intercal}\mathbb{C}^{\intercal}\ell_{t_{1}}\ell_{i}^{\intercal}\mathbb{C}\ell_{i}\right)$
$\displaystyle\underset{(1)}{=}\mathbb{E}\left(\sum_{t=1}^{T}\sum_{i_{1}=1}^{i-1}\sum_{i=1}^{t-1}\ell_{i_{1}}^{\intercal}\mathbb{C}^{\intercal}\ell_{i}\ell_{i}^{\intercal}\mathbb{C}\ell_{i}\right)=\mathbb{E}\left(\sum_{t=1}^{T}\sum_{i_{1}=1}^{i-1}\sum_{i=1}^{t-1}\ell_{i_{1}}^{\intercal}\mathbb{C}^{\intercal}\Sigma\mathbb{C}\ell_{i}\right)$
$\displaystyle\underset{(2)}{=}\mathbb{E}\left(\sum_{t=1}^{T}\sum_{i=1}^{t-1}\ell_{k}^{\intercal}\mathbb{C}^{\intercal}\Sigma\mathbb{C}\ell_{i}\right)\underset{(3)}{=}\mathbb{E}\mathop{\mathrm{Tr}}\left(\sum_{t=1}^{T}\sum_{i=1}^{t-1}\mathbb{C}^{\intercal}\Sigma\mathbb{C}\ell_{i}\ell_{k}^{\intercal}\right)=\frac{T(T-1)}{2}\mathop{\mathrm{Tr}}\left(\mathbb{C}^{\intercal}\Sigma\mathbb{C}\Sigma\right),$

since (1) holds because if $t_{1}\neq t$, we already know that
$\mathbb{E}\ell_{t}=\mathbb{E}\ell_{t_{1}}=0$, (2) holds due to a similar
reason, and (3) comes from
$\mathop{\mathrm{Tr}}(AB)=\mathop{\mathrm{Tr}}(BA)$.

We calculate $\frac{\partial f(\mathbb{C})}{\partial\mathbb{C}}$:

$\displaystyle\frac{\partial
f(\mathbb{C})}{\partial\mathbb{C}}=T(T-1)\Sigma\mathbb{C}\Sigma+2R_{\Pi}\mathbb{E}\left(\|\sum_{j=1}^{T}\ell_{j}\|\sum_{t=1}^{T}\sum_{i=1}^{t-1}\ell_{t}\ell_{i}^{\intercal}\right).$

Hence, the optimal
$\mathbb{C}=-\frac{2R_{\Pi}}{T(T-1)}\Sigma^{-1}\mathbb{E}\left(\|\sum_{j=1}^{T}\ell_{j}\|\sum_{t=1}^{T}\sum_{i=1}^{t-1}\ell_{t}\ell_{i}^{\intercal}\right)\Sigma^{-1}.$

Now, we see that for the special case of $\Sigma=I$, we have
$\mathbb{C}=-R_{\Pi}\mathbb{E}\left(\|\sum_{j=1}^{T}\ell_{j}\|\ell_{t}\ell_{i}^{\intercal}\right)$.
If we calculate the $(a,b)$-coordinate of $\mathbb{C}$, we need to calculate

$\displaystyle\mathbb{E}_{\ell}\left[\sqrt{\sum_{o=1}^{d}(\sum_{s=1}^{T}\ell_{so})^{2}}\ell_{ia}\ell_{kb}\right].$

If $a\neq b$, then since $Z$ is symmetric, the term above becomes zero.
Therefore, we only need to consider the case when $a=b$, which is
$\mathbb{E}_{\ell}\left[\sqrt{\sum_{o=1}^{d}(\sum_{s=1}^{T}\ell_{so})^{2}}\ell_{ia}\ell_{ka}\right]$,
and it will be the same value for all $a\in[d]$ since $\ell_{i}$’s coordinates
are independent.

Now, we calculate the scale of
$\mathbb{E}_{\ell}\left[\sqrt{\sum_{o=1}^{d}(\sum_{s=1}^{T}\ell_{so})^{2}}\ell_{i1}\ell_{k1}\right]$.
We have
$Z:=\frac{\sum_{o=1}^{d-1}(\sum_{s=1}^{T}\ell_{so})^{2}}{T(d-1)}\overset{a.s.}{\to}1$
as $d\to\infty$ (by the law of large numbers) and we define $W:=\sum_{s\neq
i,k}\ell_{s1}/\sqrt{T}$ which is independent of $\ell_{i1}$ and $\ell_{k1}$.

$\displaystyle\mathbb{E}_{\ell}$
$\displaystyle\left[\sqrt{\sum_{o=1}^{d}(\sum_{s=1}^{T}\ell_{so})^{2}}\ell_{i1}\ell_{k1}\right]=\mathbb{E}_{Z,W,\ell_{i1},\ell_{k1}}\left[\sqrt{T(d-1)Z+(\sqrt{T}W+\ell_{i1}+\ell_{k1})^{2}}\ell_{i1}\ell_{k1}\right]$
$\displaystyle=\mathbb{E}_{Z,W,\ell_{i1},\ell_{k1}\geq
0}\left[\sqrt{T(d-1)Z+(\sqrt{T}W+\ell_{i1}+\ell_{k1})^{2}}\ell_{i1}\ell_{k1}-\sqrt{T(d-1)Z+(\sqrt{T}W+\ell_{i1}-\ell_{k1})^{2}}\ell_{i1}\ell_{k1}\right]$
$\displaystyle=\mathbb{E}_{Z,W,\ell_{i1},\ell_{k1}\geq
0}\left[\frac{4(\sqrt{T}W+\ell_{i1})\ell_{k1}}{\sqrt{T(d-1)Z+(\sqrt{T}W+\ell_{i1}+\ell_{k1})^{2}}+\sqrt{T(d-1)Z+(\sqrt{T}W+\ell_{i1}-\ell_{k1})^{2}}}\ell_{i1}\ell_{k1}\right].$

Taking $d\to\infty$, we have

$\displaystyle\frac{\sqrt{T(d-1)Z+(\sqrt{T}W+\ell_{i1}+\ell_{k1})^{2}}+\sqrt{T(d-1)Z+(\sqrt{T}W+\ell_{i1}-\ell_{k1})^{2}}}{2\sqrt{Td}}\overset{d}{\to}1,$

which further implies

$\displaystyle\sqrt{Td}\frac{4(\sqrt{T}W+\ell_{i1})\ell_{k1}}{\sqrt{T(d-1)Z+(\sqrt{T}W+\ell_{i1}+\ell_{k1})^{2}}+\sqrt{T(d-1)Z+(\sqrt{T}W+\ell_{i1}-\ell_{k1})^{2}}}\ell_{i1}\ell_{k1}$
$\displaystyle\qquad\overset{d}{\to}\sqrt{Td}\frac{4(\sqrt{T}W+\ell_{i1})\ell_{k1}}{2\sqrt{Td}}\ell_{i1}\ell_{k1}=2(\sqrt{T}W+\ell_{i1})\ell_{i1}\ell_{k1}$

as $d\to\infty$. Therefore,

$\displaystyle\lim_{d\to\infty}\mathbb{E}_{Z,W,\ell_{i1},\ell_{k1}\geq
0}\left[{\sqrt{Td}}\frac{4(\sqrt{T}W+\ell_{i1})\ell_{k1}}{\sqrt{T(d-1)Z+(\sqrt{T}W+\ell_{i1}+\ell_{k1})^{2}}+\sqrt{T(d-1)Z+(\sqrt{T}W+\ell_{i1}-\ell_{k1})^{2}}}\ell_{i1}\ell_{k1}\right]$
$\displaystyle=\mathbb{E}_{Z,W,\ell_{i1},\ell_{k1}\geq
0}\left[2(\sqrt{T}W+\ell_{i1})\ell_{i1}\ell_{k1}\right]=\mathbb{E}_{\ell_{i1},\ell_{k1}\geq
0}\left[\ell_{i1}^{2}\ell_{k1}\right]$

which is a constant. The last equality came from the fact that $W$,
$\ell_{i1}$, $\ell_{k1}$ are independent random variables, and expectation of
$\ell_{i1}$ is zero. Therefore, the output of the single-layer linear self-
attention provides us with online gradient descent with step-size
$\Theta(R_{\Pi}/\sqrt{Td})$. In the online learning literature, we usually set
the gradient step size as $\Theta(R_{\Pi}/\sqrt{Td})$ (Hazan, 2016, Theorem
3.1), which is consistent with the result above. ∎

###  D.6 Empirical Validation of Theorem 3 and Theorem 4

We now provide empirical validations for Theorem 3 and Theorem 4. We provide
the training details and the results as follows.

####  D.6.1 Empirical Validation of Theorem 3

Our model architecture is defined as follows: the number of layers $T$ is set
to 30 and the dimensionality $d$ to 32, with the loss vector $\ell_{i}$’s
distribution $Z$ following a standard normal distribution $\mathcal{N}(0,1)$.
During training, we conducted 40,000 epochs with a batch size of 512. We
employed the Adam optimizer, setting the learning rate to 0.001. We
initialized the value, query, and key vectors ($v_{c},q_{c},k_{c}$) as zero
vectors.

Our empirical analysis aims to demonstrate that the optimized model inherently
emulates online gradient descent. To illustrate this, we will focus on two key
convergence properties: $K^{\intercal}Q$ approaching the zero matrix
$\boldsymbol{O}_{d\times d}$ and $V$ converging to
$a\boldsymbol{1}_{d}\boldsymbol{1}^{\intercal}_{d}+bI_{d\times d}$, where $a$
and $b$ are constants in $\mathbb{R}$. The conditions
$K^{\intercal}Q=\boldsymbol{O}_{d\times d}$ and
$V=a\boldsymbol{1}_{d}\boldsymbol{1}^{\intercal}_{d}+bI_{d\times d}$ imply
that the function $g(Z_{t};V,Q,K)=\sum_{i=1}^{t}(b-a)\ell_{i}$, effectively
emulating the process of an online gradient descent method. We repeated 10
times of the experiments. For verifying
$K^{\intercal}Q=\boldsymbol{O}_{d\times d}$, we will measure Frobenius norm
($\|\cdot\|_{F}$) of $K^{\intercal}Q$. Also for measuring the closeness of $V$
and $a\boldsymbol{1}_{d}\boldsymbol{1}^{\intercal}_{d}+bI_{d\times d}$, we
will measure
$\min_{a,b\in\mathbb{R}}\|V-(a\boldsymbol{1}_{d}\boldsymbol{1}^{\intercal}_{d}+bI_{d\times
d})\|_{F}/b$. The results are demonstrated in the first plot of Figure 15.

####  D.6.2 Empirical Validation of Theorem 4

We now focus on two key convergence properties:
$K^{\intercal}(Q\boldsymbol{1}_{d}+q_{c})$ approaching the zero vector
$\boldsymbol{0}_{d}$ and $V$ converging to
$a\boldsymbol{1}_{d}\boldsymbol{1}^{\intercal}_{d}+bI_{d\times d}$, where $a$
and $b$ are constants in $\mathbb{R}$. The conditions
$K^{\intercal}(Q\boldsymbol{1}_{d}+q_{c})=\boldsymbol{0}_{d}$ and
$V=a\boldsymbol{1}_{d}\boldsymbol{1}^{\intercal}_{d}+bI_{d\times d}$ imply
that the function $g(Z_{t};V,Q,K)=\sum_{i=1}^{t}(b-a)\ell_{i}$, effectively
emulating the process of an online gradient descent method. We repeated 10
times. For verifying
$K^{\intercal}(Q\boldsymbol{1}_{d}+q_{c})=\boldsymbol{0}_{d}$, we will measure
2-norm of $K^{\intercal}(Q\boldsymbol{1}_{d}+q_{c})$. Also for measuring the
closeness of $V$ and
$a\boldsymbol{1}_{d}\boldsymbol{1}^{\intercal}_{d}+bI_{d\times d}$, we will
measure
$\min_{a,b\in\mathbb{R}}\|V-(a\boldsymbol{1}_{d}\boldsymbol{1}^{\intercal}_{d}+bI_{d\times
d})\|_{F}/b$. The results are demonstrated in the second plot of Figure 15.

Figure 15: Empirical validation of Theorem 3 (top), Theorem 4 (middle), and 6
(bottom). The observed convergence in Theorem 3 and 6’s result suggests that
configuration in Theorem 3 and 6 are not only the local optimal point, but it
has the potential as being the global optimizer.

###  D.7 Discussions on the Production of FTRL with Entropy Regularization

Now, we will consider projecting a single-layer linear self-attention model
into a constrained domain such as a simplex, which is more amenable to the
Experts Problem setting. To this end, we consider the following
parameterization by adding an additional _non-linear_ structure for the
single-layer linear self-attention:

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

where the Operator denotes projection to the convex set.

######  Conjecture 6.

Assume $\Sigma=I$. Then, the configuration that
$K^{\intercal}(Qc+q_{c})=v_{c}=\boldsymbol{0}_{d}$ and
$V=\widetilde{\Omega}\left(-\frac{1}{\sqrt{nd}}\right)I_{d\times d}$ is a
first-order stationary point of Equation 3 with $N=1$ and $h(x)=x^{2}$ when
$\text{LLM}_{\theta}$ is parameterized with Equation 24,
$\texttt{Operator}=\texttt{Softmax}$, and $\Pi=\Delta(\mathcal{A})$. This
configuration performs FTRL with an entropy regularizer which is a no-regret
algorithm.

We provide an idea for proving the conjecture, together with its numerical
validation. Also, we have observed in Figure 15 that Theorem 3 and 6 might
also be a global optimizer, as training results have provided the
configuration that Theorem 3 and 6 have suggested.

To be specific, we will consider

$\displaystyle f(V,a,\beta,v_{c})$
$\displaystyle=\mathbb{E}\left(\sum_{t=1}^{T}\sum_{s=1}^{d}\ell_{ts}\frac{\exp\left(e_{s}^{\intercal}\sum_{j=1}^{t-1}(V\ell_{j}\ell_{j}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{j}+v_{c}\beta)\right)}{\sum_{y=1}^{d}\exp\left(e_{y}^{\intercal}\sum_{j=1}^{t-1}(V\ell_{j}\ell_{j}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{j}+v_{c}\beta)\right)}-\min_{s}\sum_{t=1}^{T}\ell_{ts}\right)^{2}$

and will try to prove that
$a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI$ is a first-order
stationary point.

Step 1. Calculating $\frac{\partial f}{\partial v_{c}}$.

We use the following formula: for $x\in[d]$ and $t\geq 2$, we have

$\displaystyle\frac{\partial}{\partial
v_{cx}}\exp\left(e_{y}^{\intercal}\sum_{i=1}^{t}(V\ell_{i}\ell_{i}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{i}+v_{c}\beta)\right)\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}$
$\displaystyle=\exp\left(e_{y}^{\intercal}\sum_{i=1}^{t}(V\ell_{i}\ell_{i}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{i}+v_{c}\beta)\right)\frac{\partial}{\partial
v_{cx}}\left(e_{y}^{\intercal}\sum_{i=1}^{t}(V\ell_{i}\ell_{i}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{i}+v_{c}\beta)\right)\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}$
$\displaystyle=\exp\left(e_{y}^{\intercal}\sum_{i=1}^{t}(V\ell_{i}\ell_{i}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{i}+v_{c}\beta)\right)\sum_{i=1}^{t}\left(a^{\intercal}\ell_{i}\ell_{i}^{\intercal}e_{x}+\beta\right)\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}$
$\displaystyle=t\beta\exp(v\beta)\exp(\beta k\sum_{i=1}^{t}\ell_{iy}),$

and for $t=1$, $\frac{\partial}{\partial
v_{cx}}\exp\left(e_{y}^{\intercal}\sum_{i=1}^{t}(V\ell_{i}\ell_{i}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{i}+v_{c}\beta)\right)\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}=0$,
so we can use the same formula with $t\geq 2$. Thus, we have

$\displaystyle\frac{\partial}{\partial
v_{cx}}\left(\sum_{t=1}^{T}\sum_{s=1}^{d}\ell_{ts}\frac{\exp\left(e_{s}^{\intercal}\sum_{j=1}^{t-1}(V\ell_{j}\ell_{j}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{j}+v_{c}\beta)\right)}{\sum_{y=1}^{d}\exp\left(e_{y}^{\intercal}\sum_{j=1}^{t-1}(V\ell_{j}\ell_{j}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{j}+v_{c}\beta)\right)}-\min_{s}\sum_{t=1}^{T}\ell_{ts}\right)\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}$
$\displaystyle=\beta\exp(v\beta)$
$\displaystyle\qquad\sum_{t=1}^{T}t\sum_{s=1}^{d}\ell_{ts}\frac{\sum_{y=1}^{d}\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{jy}\right)\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{js}\right)-\sum_{y=1}^{d}\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{js}\right)\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{jy}\right)}{\left(\sum_{y=1}^{d}\exp\left(e_{y}^{\intercal}\sum_{j=1}^{t-1}\beta
V\ell_{j}\right)\right)^{2}}$ $\displaystyle=0.$

Therefore,

$\displaystyle\frac{\partial f(V,a,\beta,v_{c})}{\partial
v_{cx}}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}$
$\displaystyle=\mathbb{E}\Bigg{[}\left(\sum_{t=1}^{T}\sum_{s=1}^{d}\ell_{ts}\frac{\exp\left(e_{s}^{\intercal}\sum_{j=1}^{t-1}(V\ell_{j}\ell_{j}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{j}+v_{c}\beta)\right)}{\sum_{y=1}^{d}\exp\left(e_{y}^{\intercal}\sum_{j=1}^{t-1}(V\ell_{j}\ell_{j}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{j}+v_{c}\beta)\right)}-\min_{s}\sum_{t=1}^{T}\ell_{ts}\right)$
$\displaystyle\qquad\frac{\partial}{\partial
v_{cx}}\left(\sum_{t=1}^{T}\sum_{s=1}^{d}\ell_{ts}\frac{\exp\left(e_{s}^{\intercal}\sum_{j=1}^{t-1}(V\ell_{j}\ell_{j}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{j}+v_{c}\beta)\right)}{\sum_{y=1}^{d}\exp\left(e_{y}^{\intercal}\sum_{j=1}^{t-1}(V\ell_{j}\ell_{j}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{j}+v_{c}\beta)\right)}-\min_{s}\sum_{t=1}^{T}\ell_{ts}\right)\Bigg{]}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}$
$\displaystyle=0.$

Step 2. Calculating $\frac{\partial f}{\partial V}$.

The following formula will be used for calculating $\frac{\partial f}{\partial
V}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}$: for
$r,c\in[d]$, we have

$\displaystyle\frac{\partial}{\partial V_{rc}}$
$\displaystyle\exp\left(e_{y}^{\intercal}\sum_{i=1}^{t}(V\ell_{i}\ell_{i}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{i}+v_{c}\beta)\right)\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}$
$\displaystyle=\exp\left(e_{y}^{\intercal}\sum_{i=1}^{t}(V\ell_{i}\ell_{i}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{i}+v_{c}\beta)\right)\frac{\partial}{\partial
V_{rc}}\left(e_{y}^{\intercal}\sum_{i=1}^{t}(V\ell_{i}\ell_{i}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{i}+v_{c}\beta)\right)\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}$
$\displaystyle=\exp\left(\sum_{i=1}^{t}k\beta\ell_{iy}+v\beta\right)\sum_{i=1}^{t}\beta\boldsymbol{1}(y=r)\ell_{ic}.$

Therefore,

$\displaystyle\frac{\partial f(V,a,\beta,v_{c})}{\partial
V_{rc}}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}$
$\displaystyle=\mathbb{E}\Bigg{[}\left(\sum_{t=1}^{T}\sum_{s=1}^{d}\ell_{ts}\frac{\exp\left(e_{s}^{\intercal}\sum_{j=1}^{t-1}(V\ell_{j}\ell_{j}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{j}+v_{c}\beta)\right)}{\sum_{y=1}^{d}\exp\left(e_{y}^{\intercal}\sum_{j=1}^{t-1}(V\ell_{j}\ell_{j}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{j}+v_{c}\beta)\right)}-\min_{s}\sum_{t=1}^{T}\ell_{ts}\right)$
$\displaystyle\qquad\frac{\partial}{\partial
V_{rc}}\left(\sum_{t=1}^{T}\sum_{s=1}^{d}\ell_{ts}\frac{\exp\left(e_{s}^{\intercal}\sum_{j=1}^{t-1}(V\ell_{j}\ell_{j}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{j}+v_{c}\beta)\right)}{\sum_{y=1}^{d}\exp\left(e_{y}^{\intercal}\sum_{j=1}^{t-1}(V\ell_{j}\ell_{j}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{j}+v_{c}\beta)\right)}-\min_{s}\sum_{t=1}^{T}\ell_{ts}\right)\Bigg{]}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}$
$\displaystyle=\mathbb{E}\Bigg{[}\left(\sum_{t=1}^{T}\sum_{s=1}^{d}\ell_{ts}\frac{\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{js}+v\beta\right)}{\sum_{y=1}^{d}\exp\left(\sum_{j=1}^{t-1}\beta
V\ell_{jy}+v\beta\right)}-\min_{s}\sum_{t=1}^{T}\ell_{ts}\right)$
$\displaystyle\qquad\Biggl{(}\sum_{t=1}^{T}\sum_{s=1}^{d}\ell_{ts}\frac{\sum_{j=1}^{t-1}\beta\boldsymbol{1}(s=r)\ell_{jc}\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{js}+v\beta\right)\sum_{y=1}^{d}\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{jy}+v\beta\right)}{\left(\sum_{y=1}^{d}\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{jy}+v\beta\right)\right)^{2}}$
$\displaystyle\qquad\qquad-\sum_{t=1}^{T}\sum_{s=1}^{d}\ell_{ts}\frac{\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{js}+v\beta\right)\sum_{y=1}^{d}\left(\sum_{j=1}^{t-1}\beta\boldsymbol{1}(y=r)\ell_{jc}\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{jy}+v\beta\right)\right)}{\left(\sum_{y=1}^{d}\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{jy}+v\beta\right)\right)^{2}}\Biggr{)}\Bigg{]}$
$\displaystyle=\beta\mathbb{E}\Bigg{[}\left(\sum_{t=1}^{T}\sum_{s=1}^{d}\ell_{ts}\frac{\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{js}\right)}{\sum_{y=1}^{d}\exp\left(\sum_{j=1}^{t-1}\beta
V\ell_{jy}\right)}-\min_{s}\sum_{t=1}^{T}\ell_{ts}\right)$
$\displaystyle\qquad\qquad\qquad\Biggl{(}\underbrace{\frac{\sum_{t=1}^{T}\sum_{j=1}^{t-1}\sum_{y=1}^{d}\ell_{tr}\ell_{jc}\exp\left(\beta
k\sum_{j=1}^{t-1}\ell_{jr}\right)\exp\left(\beta
k\sum_{j=1}^{t-1}\ell_{jy}\right)}{\left(\sum_{y=1}^{d}\exp\left(\beta
k\sum_{j=1}^{t-1}\ell_{jy}\right)\right)^{2}}}_{(i)}$
$\displaystyle\qquad\qquad\qquad\qquad-\underbrace{\frac{\sum_{t=1}^{T}\sum_{j=1}^{t-1}\sum_{y=1}^{d}\ell_{ty}\ell_{jc}\exp\left(\beta
k\sum_{j=1}^{t-1}\ell_{jr}\right)\exp\left(\beta
k\sum_{j=1}^{t-1}\ell_{jy}\right)}{\left(\sum_{y=1}^{d}\exp\left(\beta
k\sum_{j=1}^{t-1}\ell_{jy}\right)\right)^{2}}}_{(ii)}\Biggr{)}\Bigg{]}.$

We can observe the followings: 1) if $r_{1}\neq c_{1}$ and $r_{2}\neq c_{2}$,
$\frac{\partial f}{\partial
V_{r_{1}c_{1}}}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}=\frac{\partial
f}{\partial
V_{r_{2}c_{2}}}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}$
holds, and 2) $\frac{\partial f}{\partial
V_{r_{1}r_{1}}}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}=\frac{\partial
f}{\partial
V_{r_{2}r_{2}}}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}$.

Step 3. Calculating $\frac{\partial f}{\partial\beta}$.

The following formula will be used for calculating $\frac{\partial
f}{\partial\beta}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}$:

$\displaystyle\frac{\partial}{\partial\beta}$
$\displaystyle\exp\left(e_{y}^{\intercal}\sum_{i=1}^{t}(V\ell_{i}\ell_{i}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{i}+v_{c}\beta)\right)\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}$
$\displaystyle=\exp\left(e_{y}^{\intercal}\sum_{i=1}^{t}(V\ell_{i}\ell_{i}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{i}+v_{c}\beta)\right)\frac{\partial}{\partial\beta}\left(e_{y}^{\intercal}\sum_{i=1}^{t}(V\ell_{i}\ell_{i}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{i}+v_{c}\beta)\right)\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}$
$\displaystyle=tv\beta\exp\left(\sum_{i=1}^{t}k\beta\ell_{iy}+v\beta\right).$

Further, we have

$\displaystyle\frac{\partial}{\partial\beta}\left(\sum_{t=1}^{T}\sum_{s=1}^{d}\ell_{ts}\frac{\exp\left(e_{s}^{\intercal}\sum_{j=1}^{t-1}(V\ell_{j}\ell_{j}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{j}+v_{c}\beta)\right)}{\sum_{y=1}^{d}\exp\left(e_{y}^{\intercal}\sum_{j=1}^{t-1}(V\ell_{j}\ell_{j}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{j}+v_{c}\beta)\right)}-\min_{s}\sum_{t=1}^{T}\ell_{ts}\right)\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}$
$\displaystyle=v\beta\exp(v\beta)$
$\displaystyle\qquad\sum_{t=1}^{T}t\sum_{s=1}^{d}\ell_{ts}\frac{\sum_{y=1}^{d}\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{jy}\right)\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{js}\right)-\sum_{y=1}^{d}\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{js}\right)\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{jy}\right)}{\left(\sum_{y=1}^{d}\exp\left(e_{y}^{\intercal}\sum_{j=1}^{t-1}\beta
V\ell_{j}\right)\right)^{2}}$ $\displaystyle=0.$

Step 4. Calculating $\frac{\partial f}{\partial a}$.

Note that

$\displaystyle\frac{\partial}{\partial a_{x}}$
$\displaystyle\exp\left(e_{y}^{\intercal}\sum_{i=1}^{t}(V\ell_{i}\ell_{i}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{i}+v_{c}\beta)\right)\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}$
$\displaystyle=\exp\left(e_{y}^{\intercal}\sum_{i=1}^{t}(V\ell_{i}\ell_{i}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{i}+v_{c}\beta)\right)\frac{\partial}{\partial
a_{x}}\left(e_{y}^{\intercal}\sum_{i=1}^{t}(V\ell_{i}\ell_{i}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{i}+v_{c}\beta)\right)\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}$
$\displaystyle=\exp\left(e_{y}^{\intercal}\sum_{i=1}^{t}(V\ell_{i}\ell_{i}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{i}+v_{c}\beta)\right)\sum_{i=1}^{t}\left(e_{y}^{\intercal}V\ell_{i}\ell_{i}^{\intercal}e_{x}+e_{y}^{\intercal}v_{c}\ell_{i}^{\intercal}e_{x}\right)\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}$
$\displaystyle=\exp\left(\sum_{i=1}^{t}\beta
k\ell_{iy}+v\beta\right)\sum_{i=1}^{t}(k\ell_{iy}\ell_{ix}+v\ell_{ix}).$

Therefore,

$\displaystyle\frac{\partial f(V,a,\beta,v_{c})}{\partial
a_{x}}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}$
$\displaystyle=\mathbb{E}\Bigg{[}\left(\sum_{t=1}^{T}\sum_{s=1}^{d}\ell_{ts}\frac{\exp\left(e_{s}^{\intercal}\sum_{j=1}^{t-1}(V\ell_{j}\ell_{j}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{j}+v_{c}\beta)\right)}{\sum_{y=1}^{d}\exp\left(e_{y}^{\intercal}\sum_{j=1}^{t-1}(V\ell_{j}\ell_{j}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{j}+v_{c}\beta)\right)}-\min_{s}\sum_{t=1}^{T}\ell_{ts}\right)$
$\displaystyle\qquad\frac{\partial}{\partial
a_{x}}\left(\sum_{t=1}^{T}\sum_{s=1}^{d}\ell_{ts}\frac{\exp\left(e_{s}^{\intercal}\sum_{j=1}^{t-1}(V\ell_{j}\ell_{j}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{j}+v_{c}\beta)\right)}{\sum_{y=1}^{d}\exp\left(e_{y}^{\intercal}\sum_{j=1}^{t-1}(V\ell_{j}\ell_{j}^{\intercal}a+(\beta
V+v_{c}a^{\intercal})\ell_{j}+v_{c}\beta)\right)}-\min_{s}\sum_{t=1}^{T}\ell_{ts}\right)\Bigg{]}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}$
$\displaystyle=\mathbb{E}\Bigg{[}\left(\sum_{t=1}^{T}\sum_{s=1}^{d}\ell_{ts}\frac{\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{js}\right)}{\sum_{y=1}^{d}\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{jy}\right)}-\min_{s}\sum_{t=1}^{T}\ell_{ts}\right)$
$\displaystyle\qquad\Biggl{(}\sum_{t=1}^{T}\sum_{s=1}^{d}\ell_{ts}\frac{\sum_{j=1}^{t-1}(k\ell_{js}\ell_{jx}+v\ell_{jx})\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{js}\right)\sum_{y=1}^{d}\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{jy}\right)}{\left(\sum_{y=1}^{d}\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{jy}\right)\right)^{2}}$
$\displaystyle\qquad\qquad-\sum_{t=1}^{T}\sum_{s=1}^{d}\ell_{ts}\frac{\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{js}\right)\sum_{y=1}^{d}\left(\sum_{j=1}^{t-1}(k\ell_{jy}\ell_{jx}+v\ell_{jx})\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{jy}\right)\right)}{\left(\sum_{y=1}^{d}\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{jy}\right)\right)^{2}}\Biggr{)}\Bigg{]}$
$\displaystyle=\mathbb{E}\Bigg{[}k\left(\sum_{t=1}^{T}\sum_{s=1}^{d}\ell_{ts}\frac{\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{js}\right)}{\sum_{y=1}^{d}\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{jy}\right)}-\min_{s}\sum_{t=1}^{T}\ell_{ts}\right)$
$\displaystyle\qquad\Biggl{(}\sum_{t=1}^{T}\sum_{s=1}^{d}\ell_{ts}\frac{\sum_{j=1}^{t-1}\ell_{js}\ell_{jx}\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{js}\right)\sum_{y=1}^{d}\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{jy}\right)}{\left(\sum_{y=1}^{d}\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{jy}\right)\right)^{2}}$
$\displaystyle\qquad\qquad-\sum_{t=1}^{T}\sum_{s=1}^{d}\ell_{ts}\frac{\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{js}\right)\sum_{y=1}^{d}\left(\sum_{j=1}^{t-1}\ell_{jy}\ell_{jx}\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{jy}\right)\right)}{\left(\sum_{y=1}^{d}\exp\left(\sum_{j=1}^{t-1}\beta
k\ell_{jy}\right)\right)^{2}}\Biggr{)}\Bigg{]}$

Note that the value does not depend on $x$, which means that $\frac{\partial
f}{\partial
a}\bigg{|}_{a=\boldsymbol{0}_{d},v_{c}=v\boldsymbol{1}_{d},V=kI}=\widetilde{c}\boldsymbol{1}_{d}$
for some constant $\widetilde{c}$.

####  D.7.1 Numerical Analysis of Step 2 and Step 4

In Steps 2 and 4 above, we were not able to show that a $k$ whose value