${\partial^{2}\varphi(\boldsymbol{\theta})\over\partial\boldsymbol{\theta}_{j}\partial\boldsymbol{\theta}_{i}}={1\over\eta}{\partial^{2}\varphi(\boldsymbol{\theta}/\eta)\over\partial\boldsymbol{\theta}_{j}\partial\boldsymbol{\theta}_{i}},$
for all $i,j=1,\ldots,N.$ Under this equivalence we note that the condition in
Assumption 2 can be rewritten as $2Tr(\varphi(\boldsymbol{\theta}/\eta))\leq
L$.

Define the function
$f(t)=\nabla\varphi(\boldsymbol{\theta}_{1}/\eta+t(\boldsymbol{\theta}_{2}/\eta-\boldsymbol{\theta}_{1}/\eta))$
with
$f^{\prime}(t)=\langle\nabla^{2}\varphi(\boldsymbol{\theta}_{1}/\eta+t(\boldsymbol{\theta}_{2}/\eta-\boldsymbol{\theta}_{1}/\eta)),\boldsymbol{\theta}_{2}/\eta-\boldsymbol{\theta}_{1}/\eta\rangle$.
Noticing that

$\displaystyle\nabla\varphi(\boldsymbol{\theta}_{2}/\eta)-\nabla\varphi(\boldsymbol{\theta}_{1}/\eta)=f(1)-f(0)$
$\displaystyle=$ $\displaystyle\int_{0}^{1}f^{\prime}(t)dt$ $\displaystyle=$
$\displaystyle\int_{0}^{1}\nabla^{2}\varphi(\boldsymbol{\theta}_{1}/\eta+t(\boldsymbol{\theta}_{2}/\eta-\boldsymbol{\theta}_{1}/\eta))(\boldsymbol{\theta}_{2}/\eta-\boldsymbol{\theta}_{1}/\eta)dt.$
$\displaystyle\|\nabla\varphi(\boldsymbol{\theta}_{2}/\eta)-\nabla\varphi(\boldsymbol{\theta}_{1}/\eta)\|_{1}$
$\displaystyle\leq$
$\displaystyle\int_{0}^{1}\|\nabla^{2}\varphi(\boldsymbol{\theta}_{1}/\eta+t(\boldsymbol{\theta}_{2}/\eta-\boldsymbol{\theta}_{1}/\eta))(\boldsymbol{\theta}_{2}/\eta-\boldsymbol{\theta}_{1}/\eta)\|_{1}dt$
$\displaystyle\leq$
$\displaystyle\int_{0}^{1}\|\nabla^{2}\varphi(\boldsymbol{\theta}_{1}/\eta+t(\boldsymbol{\theta}_{2}/\eta-\boldsymbol{\theta}_{1}/\eta))\|_{\infty,1}\|\boldsymbol{\theta}_{2}/\eta-\boldsymbol{\theta}_{1}/\eta\|_{1}$

To complete the proof we stress two properties of the Hessian. First, each row
(or columns) of $\nabla^{2}\varphi(\boldsymbol{\theta}_{t}/\eta)$ sums up to
$0$. To see this we note that
$\sum_{i=1}^{N}\nabla_{i}\varphi(\boldsymbol{\theta}_{t}/\eta)=1$. Then simple
differentiation yields
$\sum_{j=1}^{N}{1\over\eta}\nabla_{ij}\varphi(\boldsymbol{\theta}_{t}/\eta)=0$
for all $i=1,\ldots,N.$ Second, it is well known that the off-diagonal
elements of ${1\over\eta}\nabla^{2}\varphi(\boldsymbol{\theta}_{t}/\eta)$ are
nonnegative (McFadden [1981, Ch. 5]). To see why this is true, we recall that
for alternative $i$ the choice probability is given by:
$\nabla_{i}\varphi(\boldsymbol{\theta}_{t}/\eta)=\mathbb{P}(i=\arg\max_{j\in
A}\\{\boldsymbol{\theta}_{jt}+\eta\epsilon_{jt}\\})$. Then increasing the
terms $\boldsymbol{\theta}_{jt}$ for $j\neq i$ cannot increase the probability
of choosing $i$, which is formalized as
${1\over\eta}\nabla_{ij}\varphi(\boldsymbol{\theta}_{t}/\eta)\leq 0$.

Now, using previous observation, we have that for a convex combination
$\tilde{\boldsymbol{\theta}}/\eta=\boldsymbol{\theta}_{1}/\eta+t(\boldsymbol{\theta}_{2}/\eta-\boldsymbol{\theta}_{1}/\eta)$
we have

$\displaystyle{1\over\eta}\|\nabla^{2}\varphi(\tilde{\boldsymbol{\theta}}/\eta)\|_{\infty,1}$
$\displaystyle=$ $\displaystyle{1\over\eta}\max_{\|\mathbb{v}\|\leq
1}\\{\|\nabla^{2}\varphi(\tilde{\boldsymbol{\theta}}/\eta)\mathbb{v}\|_{1}\\}$
$\displaystyle\leq$
$\displaystyle{1\over\eta}\sum_{i=1}^{N}\sum_{j=1}^{N}|\nabla_{ij}^{2}\varphi(\tilde{\boldsymbol{\theta}})|$
$\displaystyle=$
$\displaystyle{1\over\eta}2Tr(\nabla^{2}\varphi(\tilde{\boldsymbol{\theta}}))\leq{L\over\eta},$

where the last inequality follows from Assumption 2. Plugging in, we arrive to
the conclusion

$\|\nabla\varphi(\boldsymbol{\theta}_{2}/\eta)-\nabla\varphi(\boldsymbol{\theta}_{1}/\eta)\|_{1}\leq{L}\|\boldsymbol{\theta}_{2}/\eta-\boldsymbol{\theta}_{1}/\eta\|_{1}\quad\forall\boldsymbol{\theta}_{1},\boldsymbol{\theta}_{2}.$

Finally, using the fact
$\nabla\varphi(\boldsymbol{\theta})=\nabla\varphi(\boldsymbol{\theta}/\eta)$
we get

$\|\nabla\varphi(\boldsymbol{\theta}_{2})-\nabla\varphi(\boldsymbol{\theta}_{1})\|_{1}\leq{L\over\eta}\|\boldsymbol{\theta}_{2}-\boldsymbol{\theta}_{1}\|_{1}\quad\forall\boldsymbol{\theta}_{1},\boldsymbol{\theta}_{2}.$

$\square$

######  Lemma 6.

Let Assumption 1 hold. Then $\mathcal{R}(\mathbb{x})\leq 0$ for all
$\mathbb{x}\in\Delta_{N}$.

Proof. First, we note that the Fenchel equality implies
$\mathcal{R}(\mathbb{x})=\langle\boldsymbol{\theta},\mathbb{x}\rangle-\varphi(\boldsymbol{\theta})=\langle\boldsymbol{\theta},\mathbb{x}\rangle-\eta\varphi(\boldsymbol{\theta}/\eta)$
with
$\mathbb{x}=\nabla\varphi(\boldsymbol{\theta})=\nabla\varphi(\boldsymbol{\theta}/\eta)$.
We recall that
$\varphi(\boldsymbol{\theta})=\mathbb{E}(\max_{j=1,\ldots,n}\\{\boldsymbol{\theta}_{j}+\eta\epsilon_{j}\\})$.
Given that $\max\\{\cdot\\}$ is a convex function, by Jensen’s inequality we
get
$\max_{j=1,\ldots,n}\mathbb{E}(\boldsymbol{\theta}_{j}+\eta\epsilon_{j})\leq\mathbb{E}(\max_{j=1,\ldots,n}\\{\boldsymbol{\theta}_{j}+\eta\epsilon_{j}\\}).$
Then it follows that

$\displaystyle\mathcal{R}(\mathbb{x})$ $\displaystyle=$
$\displaystyle\langle\boldsymbol{\theta},\mathbb{x}\rangle-\varphi(\boldsymbol{\theta}),$
$\displaystyle\leq$
$\displaystyle\langle\boldsymbol{\theta},\mathbb{x}\rangle-\max_{j=1,\ldots,n}\mathbb{E}(\boldsymbol{\theta}_{j}+\eta\epsilon_{j})$
$\displaystyle=$
$\displaystyle\langle\boldsymbol{\theta},\mathbb{x}\rangle-\max_{j=1,\ldots,n}\boldsymbol{\theta}_{j},$
$\displaystyle\mathcal{R}(\mathbb{x})$ $\displaystyle\leq$ $\displaystyle 0$

where the last inequality follows from the fact that
$\mathbb{x}\in\Delta_{N}$. $\square$

######  Lemma 7.

Let Assumptions 1 and 2 hold. Then

$D_{\varphi}(\boldsymbol{\theta}_{t}||\boldsymbol{\theta}_{t-1})\leq{L\over
2\eta}u^{2}_{max}.$

Proof. Using a second order Taylor expansion of
$\varphi(\boldsymbol{\theta}_{t})$ we get:

$\displaystyle\varphi(\boldsymbol{\theta}_{t+1})$ $\displaystyle=$
$\displaystyle\varphi(\boldsymbol{\theta}_{t})+\langle\nabla\varphi(\boldsymbol{\tilde{\theta}}),\mathbb{u}_{t}\rangle+{1\over
2}\langle\mathbb{u}_{t},\nabla^{2}\varphi(\tilde{\boldsymbol{\theta}})\mathbb{u}_{t}\rangle,$
$\displaystyle\varphi(\boldsymbol{\theta}_{t+1})-\varphi(\boldsymbol{\theta}_{t})-\langle\nabla\varphi(\boldsymbol{\tilde{\theta}}),\mathbb{u}_{t}\rangle$
$\displaystyle=$ $\displaystyle{1\over
2}\langle\mathbb{u}_{t},\nabla^{2}\varphi(\tilde{\boldsymbol{\theta}})\mathbb{u}_{t}\rangle,$
(39) $\displaystyle
D_{\varphi}(\boldsymbol{\theta}_{t+1}||\boldsymbol{\theta}_{t})$
$\displaystyle=$ $\displaystyle{1\over
2}\langle\mathbb{u}_{t},\nabla^{2}\varphi(\tilde{\boldsymbol{\theta}})\mathbb{u}_{t}\rangle,$

where $\tilde{\boldsymbol{\theta}}$ is some convex combination of
$\boldsymbol{\theta}_{t+1}$ and $\boldsymbol{\theta}_{t}$. From Eq.(39) it
follows that

(40)
$D_{\varphi}(\boldsymbol{\theta}_{t+1}||\boldsymbol{\theta}_{t})\leq{1\over
2}\|\nabla_{ij}^{2}\varphi(\tilde{\boldsymbol{\theta}})\|_{\infty,1}\|\mathbb{u}_{t}\|_{\infty}^{2}.$

Noting that

$\|\nabla^{2}\varphi(\tilde{\boldsymbol{\theta}})\|_{\infty,1}=\max_{\|\mathbb{v}\|\leq
1}\\{\|\nabla^{2}\varphi(\tilde{\boldsymbol{\theta}})\mathbb{v}\|_{1}\\}\leq\sum_{i=1}^{N}\sum_{j=1}^{N}|\nabla_{ij}^{2}\varphi(\tilde{\boldsymbol{\theta}})|=2Tr(\nabla^{2}\varphi(\tilde{\boldsymbol{\theta}}))\leq{L\over\eta},$

where the last inequality follows from Assumption 2.

Plugging the previous bound in (40) combined with
$\|\mathbb{u}_{t}\|^{2}_{\infty}\leq u_{max}^{2}$ we find that

$D_{\varphi}(\boldsymbol{\theta}_{t+1}||\boldsymbol{\theta}_{t})\leq{L\over
2\eta}u_{max}^{2}.$

$\square$

######  Lemma 8.

Let Assumptions 1 and 2 hold. Then in the SSA

(41) $\textsc{Regret}_{T}\leq\eta\varphi(\mathbb{0})+{L\over
2\eta}Tu^{2}_{max}.$

Proof. The proof of this lemma exploits the convex duality structure of the
RUM-ODP model. By the Fenchel-Young inequality we know that

$\forall\mathbb{x}\in\Delta_{N}:\quad\mathcal{R}(\mathbb{x})\geq\langle\boldsymbol{\theta}_{T},\mathbb{x}\rangle-\varphi(\boldsymbol{\theta}_{T}),$

where the equality holds when $\mathbb{x}$ maximizes
$\langle\boldsymbol{\theta}_{T},\mathbb{x}\rangle-\mathcal{R}(\mathbb{x})$.

The Fenchel-Young inequality implies

$\mathcal{R}(\mathbb{x})-\langle\boldsymbol{\theta}_{T},\mathbb{x}\rangle\geq-\varphi(\boldsymbol{\theta}_{T}).$

Noting that $-\varphi(\boldsymbol{\theta}_{T})$ can be equivalently expressed
as:

$-\varphi(\boldsymbol{\theta}_{T})=-\varphi(\boldsymbol{\mathbb{0}})-\sum_{t=1}^{T}\left(\varphi(\boldsymbol{\theta}_{t})-\varphi(\boldsymbol{\theta}_{t-1})\right).$

From the definition of Bregman divergence combined with
$\mathbb{x}_{t}=\nabla\varphi(\boldsymbol{\theta}_{t-1})$, it follows that

$\sum_{t=1}^{T}\left(\varphi(\boldsymbol{\theta}_{t})-\varphi(\boldsymbol{\theta}_{t-1})\right)=\sum_{t=1}^{T}\left(D_{\varphi}(\boldsymbol{\theta}_{t}||\boldsymbol{\theta}_{t-1})-\langle\mathbb{u}_{t},\mathbb{x}_{t}\rangle\right).$

Thus, it follows that

$\mathcal{R}(\mathbb{x})-\langle\boldsymbol{\theta}_{T},\mathbb{x}\rangle\geq-\eta\varphi(\mathbb{0})-\sum_{t=1}^{T}\left(D_{\varphi}(\boldsymbol{\theta}_{t}||\boldsymbol{\theta}_{t-1})-\langle\mathbb{u}_{t},\mathbb{x}_{t}\rangle\right).$

Combining Lemmas 6 and 7, the previous inequality can be rewritten as

$\sum_{t=1}^{T}\langle\mathbb{x}-\mathbb{x}_{t},\mathbb{u}_{t}\rangle\leq\mathcal{R}(\mathbb{x})+\eta\varphi(\mathbb{0})+\sum_{t=1}^{T}D_{\varphi}(\boldsymbol{\theta}_{t}||\boldsymbol{\theta}_{t-1})\leq\eta\varphi(\mathbb{0})+{L\over
2\eta}Tu^{2}_{max}.$

Because the previous inequality holds for all $\mathbb{x}\in\Delta_{N}$ we
conclude:

$\textsc{Regret}_{T}\leq\eta\varphi(\mathbb{0})+{L\over 2\eta}Tu^{2}_{max}.$

$\square$

###  A.3. Proof of Theorem 1

The bound (10) follows from Lemma 8. To derive Eq. (11), define the function
$\psi(\eta)=\eta\varphi(\mathbb{0})+\frac{L}{2\eta}Tu^{2}_{max}$. Given the
strict convexity of $\psi(\eta)$, the first order conditions are necessary and
sufficient for a minimum. In particular, we get

$\psi^{\prime}(\eta)=\varphi(\mathbb{0})-\frac{L}{2\eta^{2}}Tu^{2}_{max}=0$

The optimal $\eta$ is given by $\eta^{*}=\sqrt{{LTu^{2}_{max}\over
2\varphi(\mathbb{0})}}$. Then, it follows that
$\psi(\eta^{*})=u_{max}\sqrt{2\varphi(\mathbb{0})LT}$. Thus we conclude that

$\textsc{Regret}_{T}\leq\psi(\eta^{*})=2u_{max}\sqrt{\varphi(\mathbb{0})LT}.$

$\square$

###  A.4. Proof of Lemma 2

This follows from a direct application of Muller et al. [2022, Thm. 3].
$\square$

###  A.5. Proof of Theorem 3

Combining Lemma 2 with Lemma 8 we obtain the bound (19). Following the
argument used in proving Theorem 1 combined with $L={2M+1\over\eta}$ we obtain
the optimized regret bound (20). $\square$

######  Lemma 9.

In the GNL model the following statements hold:

  * i)

The Social Surplus function has a Lipschitz continuous gradient with constant
$({2\over\min_{k}\lambda_{k}}-1)/\eta.$

  * ii)

$\log
G(\mathbb{1})=\log\sum_{k=1}^{K}\left(\sum_{i=1}^{N}\alpha^{1/\lambda_{k}}_{ik}\right)^{\lambda_{k}}\leq\log
N,$

Proof. i) This follows from a direct application of Muller et al. [2022, Cor.
4]. ii) To prove this, we first show that for
$\lambda_{k}<\lambda_{k}^{\prime}$ we have:

$\left(\sum_{i=1}^{N}\alpha^{1/\lambda_{k}}_{ik}\right)^{\lambda_{k}}\leq\left(\sum_{i=1}^{N}\alpha^{1/\lambda^{\prime}_{k}}_{ik}\right)^{\lambda^{\prime}_{k}}\quad\mbox{for
$k=1,\ldots,K.$}$

Let $p_{k}={1\over\lambda_{k}}$ and
$p_{k^{\prime}}={1\over\lambda_{k^{\prime}}}$, noting that
$p^{\prime}_{k}<p_{k}$ whenever $\lambda_{k}<\lambda_{k}^{\prime}$. Using this
change of variable, we can write the following ratio

$\displaystyle{\left(\sum_{i=1}^{N}\alpha^{p_{k}}_{ik}\right)^{1/p_{k}}\over\left(\sum_{j=1}^{N}\alpha^{p^{\prime}_{k}}_{jk}\right)^{1/p^{\prime}_{k}}}$
$\displaystyle=$
$\displaystyle\left({\sum_{i=1}^{N}\alpha^{p_{k}}_{ik}\over\left(\sum_{j=1}^{N}\alpha^{p^{\prime}_{k}}_{jk}\right)^{p_{k}/p^{\prime}_{k}}}\right)^{1/p_{k}}$
$\displaystyle=$
$\displaystyle\left(\sum_{i=1}^{N}\left({\alpha^{p^{\prime}_{k}}_{ik}\over\sum_{j=1}^{N}\alpha^{p^{\prime}_{k}}_{jk}}\right)^{p_{k}/p_{k}^{\prime}}\right)^{1/p_{k}}$
$\displaystyle\leq$
$\displaystyle\left(\sum_{i=1}^{N}\left({\alpha^{p^{\prime}_{k}}_{ik}\over\sum_{j=1}^{N}\alpha^{p^{\prime}_{k}}_{jk}}\right)\right)^{1/p_{k}}=1.$

The last inequality implies that

$\left(\sum_{i=1}^{N}\alpha^{1/\lambda_{k}}_{ik}\right)^{\lambda_{k}}\leq\left(\sum_{i=1}^{N}\alpha^{1/\lambda^{\prime}_{k}}_{ik}\right)^{\lambda^{\prime}_{k}}\quad\mbox{for
$k=1,\ldots,K.$}$

Then for $\lambda_{k}=1$ for $k=1,\ldots,K$, we get

$\log\sum_{k=1}^{K}\left(\sum_{i=1}^{N}\alpha^{1/\lambda_{k}}_{ik}\right)^{\lambda_{k}}\leq\log\sum_{k=1}^{K}\sum_{i=1}^{N}\alpha_{ik}=\log
N.$

$\square$

###  A.6. Proof of Proposition 2

Combining Lemma 9 with Theorem 1, the conclusion follows at once. $\square$

###  A.7. Proof of Proposition 3

i) From the definition of $\mathcal{R}(\mathbb{x})$ we know that
$\mathcal{R}(\mathbb{x})=\eta\varphi^{\ast}(\mathbb{x};\eta)$ where
$\varphi^{\ast}(\mathbb{x};\eta)$ is the convex conjugate of the parametrized
social surplus function $\varphi(\boldsymbol{\theta}/\eta)$. By Lemma 1 it
follows that $\varphi(\boldsymbol{\theta}/\eta)$ is $L$-Lipschitz continuous.
Applying Lemma 4 it follows that $\varphi^{\ast}(\mathbb{x};\eta)$ is $1/L$
strongly convex. Then it follows that $\mathcal{R}(\mathbb{x})$ is ${\eta\over
L}$-strongly convex.
ii) This is a direct implication of Lemma 5.
iii) It is easy to see that
$\langle\boldsymbol{\theta},\mathbb{x}\rangle-\mathcal{R}(\mathbb{x})$ is a
${\eta\over L}$-strongly concave function on $\Delta_{N}$. This implies that
the optimization problem
$\max_{\mathbb{x}\in\Delta_{N}}\\{\langle\boldsymbol{\theta},\mathbb{x}\rangle-\mathcal{R}(\mathbb{x})\\}$
must have a unique solution. Let $\mathbb{x}^{*}$ be the unique optimal
solution. Using the differentiability of $\mathcal{R}(\mathbb{x})$ combined
with the Fenchel equality it follows that
$\mathbb{x}^{*}=\nabla\varphi(\boldsymbol{\theta})$ iff
$\nabla\varphi(\boldsymbol{\theta})=\arg\max_{\mathbb{x}\in\Delta_{N}}\\{\langle\boldsymbol{\theta},\mathbb{x}\rangle-\mathcal{R}(\mathbb{x})\\}$.
$\square$

###  A.8. Proof of Theorem 4

From Proposition 3iii) we know

$\mathbb{x}_{t+1}=\nabla\varphi(\boldsymbol{\theta}_{t})=\arg\max_{\mathbb{x}\in\Delta_{N}}\left\\{\langle\boldsymbol{\theta}_{t},\mathbb{x}\rangle-\mathcal{R}(\mathbb{x})\right\\}.$

This fact implies that the FRTL algorithm is equivalent to the SSA. Then the
argument used in proving Theorem 1 applies. Thus $\textsc{R}^{T}_{FTRL}$ is
bounded by the same term that bounds $\textsc{R}^{T}_{SSA}$. Similarly, the
same optimized bound achieved in $\textsc{R}^{T}_{SSA}$ applies to
$\textsc{R}^{T}_{FTRL}$.  $\square$

###  A.9. Proof of Theorem 5

From Proposition 3 we know
$\nabla\varphi(\boldsymbol{\theta}_{t})=\mathbb{x}_{t+1}=\arg\max_{\mathbb{x}\in\Delta_{N}}\\{\langle\boldsymbol{\theta}_{t},\mathbb{x}\rangle-\mathcal{R}(\mathbb{x})\\}$.
Plugging in this observation in the FTRL algorithm the equivalence follows at
once. $\square$

###  A.10. Proof of Proposition 4

Let us focus at period $t+1$. Accordingly, the associated Lagrangian is given
by:

$\mathcal{L}(\mathbb{x}_{t+1};\lambda)=\sum_{i=1}^{N}\boldsymbol{\theta}_{it}\mathbb{x}_{it+1}-{\eta}\sum_{i=1}^{N}\mathbb{x}_{it+1}\log\Phi_{i}(\mathbb{x}_{t+1})+\lambda\left(\sum_{i=1}^{N}\mathbb{x}_{it+1}-1\right).$

From [Fosgerau et al., 2020, Prop. A1ii)] we know that
$\Phi(\mathbb{x}_{t+1})$ is differentiable with

$\sum_{j=1}^{N}\mathbb{x}_{jt+1}{\partial\Phi_{j}(\mathbb{x}_{t+1})\over\partial\mathbb{x}_{it+1}}=1\quad\forall
i\in A.$

Using this fact, the set of first order conditions can be written as:

(42)
$\displaystyle{\partial\mathcal{L}(\mathbb{x}_{t+1};\lambda)\over\partial\mathbb{x}_{t+1}}$
$\displaystyle=$
$\displaystyle\boldsymbol{\theta}_{t}-{\eta}\log\Phi(\mathbb{x}_{t+1})-{\eta}+\lambda=0.$
(43)
$\displaystyle{\partial\mathcal{L}(\mathbb{x}_{t+1};\lambda)\over\partial\lambda}$
$\displaystyle=$ $\displaystyle\sum_{i=1}^{n}\mathbb{x}_{it+1}-1=0.$

Noting that
$\boldsymbol{\theta}_{t}=\mathbb{u}_{t}+\boldsymbol{\theta}_{t-1}$, Eq. (42)
can be expressed as

(44) $\displaystyle
e^{\mathbb{u}_{t}/\eta+\boldsymbol{\theta}_{t-1}/\eta}e^{\lambda/\eta-1}$
$\displaystyle=$ $\displaystyle\Phi(\mathbb{x}_{t+1})$

Recalling that $\Phi(\cdot)=H^{-1}(\cdot)$, from (44) we get:

$\displaystyle
H(e^{\mathbb{u}_{t}/\eta+\boldsymbol{\theta}_{t-1}/\eta}e^{\lambda/\eta-1})$
$\displaystyle=$ $\displaystyle\mathbb{x}_{t+1}.$

Noting that $H(\cdot)$ is homogeneous of degree 1, we get:

$\displaystyle
H(e^{\mathbb{u}_{t}/\eta+\boldsymbol{\theta}_{t-1}/\eta})e^{\lambda/\eta-1}$
$\displaystyle=$ $\displaystyle\mathbb{x}_{t+1}.$

Using (43) we find that

$\displaystyle e^{\lambda/\eta-1}$ $\displaystyle=$
$\displaystyle{1\over\sum_{j=1}^{N}H_{j}(e^{\mathbb{u}_{t}/\eta+\boldsymbol{\theta}_{t-1}/\eta})}.$

Then it is easy to see that

(45)
$\mathbb{x}_{it+1}={H_{i}(e^{\mathbb{u}_{t}/\eta+\boldsymbol{\theta}_{t-1}/\eta})\over\sum_{j=1}^{N}H_{j}(e^{\mathbb{u}_{t}/\eta+\boldsymbol{\theta}_{t-1}/\eta})}\quad\mbox{for
all $i\in A,t\geq 1.$}$

From (45), it is easy to see that at period $t$ we must have:

(46)
$\mathbb{x}_{it}={H_{i}(e^{\boldsymbol{\theta}_{t-1}/\eta})\over\sum_{j=1}^{N}H_{j}(e^{\boldsymbol{\theta}_{t-1}/\eta})}\quad\mbox{for
all $i\in A$.}$

Once again, using the fact that $\Phi(\cdot)$ is homogeneous of degree 1, in
(46) we find:

(47)
$\Phi(\mathbb{x}_{t})\sum_{j=1}^{N}H_{j}(e^{\boldsymbol{\theta}_{t-1}/\eta})=e^{\boldsymbol{\theta}_{t-1}/\eta}\quad\mbox{for
all $i\in A$.}$

Define
$w_{t-1}\triangleq\log\left(\sum_{j=1}^{N}H_{j}(e^{\boldsymbol{\theta}_{t-1}/\eta})\right)$.
Using this definition, combined with Eq. (45), we get:

$\mathbb{x}_{it+1}={H_{i}(\Phi(\mathbb{x}_{t})e^{\mathbb{u}_{t}/\eta+w_{t-1}})\over\sum_{j=1}^{N}H_{j}(\Phi(\mathbb{x}_{t})e^{\mathbb{u}_{t}/\eta+w_{t-1}})}.$

Finally, using the homogeneity of $H$, we conclude that

$\mathbb{x}_{it+1}={H_{i}(e^{\mathbb{u}_{t}/\eta+\alpha(\mathbb{x}_{t})})\over\sum_{j=1}^{N}H_{j}(e^{\mathbb{u}_{t}/\eta+\alpha(\mathbb{x}_{t})})},\quad\forall
i\in A,t\geq 1.$

$\square$

###  A.11. Proof of Lemma 3

This follows from Fosgerau et al. [2020]. $\square$

In proving the Proposition 5 we make use of the following technical lemma.

######  Lemma 10.

Consider the NL model. Define the vector valued function
$\Phi:\Delta_{N}\longrightarrow\mathbb{R}_{+}^{N}$ where the $i$-th component
is defined as:

(48)
$\Phi_{i}(\mathbb{x})=\mathbb{x}_{i}^{\lambda_{k}}\left(\sum_{j\in\mathcal{N}_{k}}\mathbb{x}_{j}\right)^{1-\lambda_{k}}\quad\mbox{for
all $i\in\mathcal{N}_{k},k=1,\ldots,K$},$

Then $\Phi(\mathbb{x})$ is invertible and homogeneous of degree 1.

Proof. This follows from Fosgerau et al. [2020, Prop. 8].  $\square$

###  A.12. Proof of Proposition 5

Noting that
$\mathcal{R}(\mathbb{x}_{t+1})=\langle\mathbb{x}_{t+1},\log\Phi(\mathbb{x}_{t+1})\rangle$,
we can write the associated Lagrangian as:

$\mathcal{L}(\mathbb{x}_{t+1};\boldsymbol{\theta}_{t},\mu,\eta)=\langle\boldsymbol{\theta}_{t},\mathbb{x}_{t+1}\rangle-{\eta}\langle\mathbb{x}_{t+1},\log\Phi(\mathbb{x}_{t+1})\rangle+\mu\left(\sum_{i=1}^{n}\mathbb{x}_{it+1}-1\right).$

Given that $\mathcal{R}(\mathbb{x})$ is ${1\over L}$-strongly convex, first
order conditions are necessary and sufficient for the existence and uniqueness
of a maximum. In particular, we find the maximizer $\mathbb{x}_{t+1}$ by
solving:

$\displaystyle{\partial\mathcal{L}(\mathbb{x}_{t+1};\boldsymbol{\theta}_{t},\mu,\eta)\over\partial\mathbb{x}_{t+1}}$
$\displaystyle=$
$\displaystyle\boldsymbol{\theta}_{t}-{\eta}\log\Phi(\mathbb{x}_{t+1})-{\eta}+\mu=0.$
$\displaystyle{\partial\mathcal{L}(\mathbb{x}_{t+1};\boldsymbol{\theta}_{t},\mu,\eta)\over\partial\lambda}$
$\displaystyle=$ $\displaystyle\sum_{i=1}^{n}\mathbb{x}_{it+1}-1=0.$

From the definition of the cumulative payoff vector, it follows that
$\boldsymbol{\theta}_{t}=\mathbb{u}_{t}+\boldsymbol{\theta}_{t-1}$. Using this
fact we get

$\displaystyle
e^{\mathbb{u}_{t}/\eta+\boldsymbol{\theta}_{t-1}/\eta}e^{\mu/\eta-1}$
$\displaystyle=$ $\displaystyle\Phi(\mathbb{x}_{t+1}).$

Using Lemma 10 we obtain:

$\displaystyle
H(e^{\mathbb{u}_{t}/\eta+\boldsymbol{\theta}_{t-1}/\eta}e^{\mu/\eta-1})$
$\displaystyle=$ $\displaystyle\mathbb{x}_{t+1},$

where $H(\cdot)\triangleq\Phi^{-1}(\cdot).$ Noting that $H(\cdot)$ is
homogeneous of degree 1, the previous expression can be rewritten as:

$\displaystyle
H(e^{\mathbb{u}_{t}/\eta+\boldsymbol{\theta}_{t-1}/\eta})e^{\mu/\eta-1}$
$\displaystyle=$ $\displaystyle\mathbb{x}_{t+1}.$

Now using the constraint $\sum_{i=1}^{N}\mathbb{x}_{it+1}=1$ we get

$\displaystyle e^{\mu/\eta-1}$
$\displaystyle={1\over\sum_{k=1}^{K}\sum_{j\in\mathcal{N}_{k}}H_{j}(e^{\mathbb{u}_{t}/\eta+\boldsymbol{\theta}_{t-1}/\eta})}$
.

Then we find that for all $t$

(49)
$\mathbb{x}_{it+1}={H_{i}(e^{\mathbb{u}_{t}/\eta+\boldsymbol{\theta}_{t-1}/\eta})\over\sum_{k=1}\sum_{j\in\mathcal{N}_{k}}H_{j}(e^{\mathbb{u}_{t}/\eta+\boldsymbol{\theta}_{t-1}/\eta})}\quad\mbox{for
$i\in\mathcal{N}_{k},k=1,\ldots,K$.}$

In the previous expression, we note that

$\displaystyle H_{i}(e^{\mathbb{u}_{t}/\eta+\boldsymbol{\theta}_{t-1}/\eta})$
$\displaystyle=$
$\displaystyle\left(\sum_{j\in\mathcal{N}_{k}}e^{(\mathbb{u}_{jt}+\boldsymbol{\theta}_{jt-1})/\eta\lambda_{k}}\right)^{\lambda_{k}-1}e^{(\mathbb{u}_{it}+\boldsymbol{\theta}_{it-1})/\eta\lambda_{k}},$
$\displaystyle\sum_{k=1}^{K}\sum_{j\in\mathcal{N}_{k}}H_{j}(e^{\mathbb{u}_{t}/\eta+\boldsymbol{\theta}_{t-1}/\eta})$
$\displaystyle=$
$\displaystyle\sum_{k=1}^{K}\left(\sum_{j\in\mathcal{N}_{k}}e^{(\mathbb{u}_{jt}+\boldsymbol{\theta}_{jt-1})/\eta\lambda_{k}}\right)^{\lambda_{k}}.$

From (49) it is easy to see that for period $t$ we must have:

$\mathbb{x}_{it}={H_{i}(e^{\boldsymbol{\theta}_{t-1}/\eta})\over\sum_{k=1}^{K}\sum_{j\in\mathcal{N}_{k}}H_{j}(e^{\boldsymbol{\theta}_{t-1}/\eta})}\quad\mbox{for
$i\in\mathcal{N}_{k},k=1,\ldots,K.$}$

Using once again using the fact that $\Phi(\cdot)$ is homogenous of degree 1,
we get

$\Phi(\mathbb{x}_{t})\sum_{k=1}^{K}\sum_{j\in\mathcal{N}_{k}}H_{j}(e^{\boldsymbol{\theta}_{t-1}/\eta})=e^{\boldsymbol{\theta}_{t-1}/\eta}\quad\mbox{for
$i\in\mathcal{N}_{k},k=1,\ldots,K.$}$

Taking log on both sides in the previous expression we obtain

$\log\Phi(\mathbb{x}_{t})+\log\left(\sum_{k=1}^{K}\sum_{j\in\mathcal{N}_{k}}H_{j}(e^{\boldsymbol{\theta}_{t-1}/\eta})\right)=\boldsymbol{\theta}_{t-1}/\eta\quad\mbox{for
$i\in\mathcal{N}_{k},k=1,\ldots,K.$}$

Define
$m_{t-1}\triangleq\log\left(\sum_{k=1}^{K}\sum_{j\in\mathcal{N}_{k}}H_{j}(e^{\boldsymbol{\theta}_{t-1}/\eta})\right)$.
Using this definition we get:

$\mathbb{x}_{it+1}={H_{i}(\Phi(\mathbb{x}_{t})e^{\mathbb{u}_{t}/\eta+m_{t-1}})\over\sum_{k=1}^{K}\sum_{j\in\mathcal{N}_{k}}H_{j}(\Phi(\mathbb{x}_{t})e^{\mathbb{u}_{t}/\eta+m_{t-1}})}.$

Using the homogeneity of $H$ one last time, we obtain:

$\mathbb{x}_{it+1}={H_{i}(\Phi_{i}(\mathbb{x}_{t})e^{\mathbb{u}_{t}/\eta})\over\sum_{k=1}^{K}\sum_{j\in\mathcal{N}_{k}}H_{j}(\Phi_{j}(\mathbb{x}_{t})e^{\mathbb{u}_{t}/\eta})}\quad\mbox{for
$i\in\mathcal{N}_{k},k=1,\ldots,K.$}$

Finally, replacing the expression for $H_{i}$ using the NL assumption, the
conclusion follows at once.  $\square$

###  A.13. Proof of Corollary

When $\lambda_{k}=1$ for all $k\in K$, we know that the NL boils to the MNL
model. Thus the conclusion follows at once. $\square$

##  Appendix B Online material not for publication

######  Lemma 11.

Let Assumptions 1 and 2 hold. Then in the OFTRL algorithm the following hold:

(50)
$\sum_{t=1}^{T}\langle\mathbb{x}^{*}-\mathbb{x}_{t},\mathbb{u}_{t}\rangle\leq\eta\varphi(\mathbb{0})+{L\over
2\eta}\sum_{t=1}^{T}\left\|\mathbf{u}_{t}-\boldsymbol{\beta}_{t}\right\|_{*}^{2}.$

Proof. The proof of this Lemma follows from a simple adaptation of [Rakhlin
and Sridharan, 2013, Lemma 2]. $\square$

######  Lemma 12.

In the OFTRL the following statements hold

  * i)

In the $S$-step recency bias:

$\sum_{t=1}^{T}\|\mathbb{u}_{t}-\boldsymbol{\beta}_{t}\|^{2}_{\ast}\leq
S^{2}\sum_{t=1}^{T}\|\mathbb{u}_{t}-\mathbb{u}_{t}\|^{2}_{\ast}$

  * ii)

In the geometrically discounted recency bias we have:

$\sum_{t=1}^{T}\|\mathbb{u}_{t}-\boldsymbol{\beta}_{t}\|^{2}_{\ast}\leq\frac{1}{(1-\delta)^{3}}\sum_{t=1}^{T}\left\|\mathbf{u}_{t}-\mathbf{u}_{t-1}\right\|_{*}^{2}$

Proof. In proving parts i) and ii) we follow the proof of Lemma 21 in
Syrgkanis et al. [2015]. Concretely, in proving part i) we have the following:

(51)
$\displaystyle\sum_{t=1}^{T}\|\mathbb{u}_{t}-\boldsymbol{\beta}_{t}\|^{2}_{\ast}$
$\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\left\|\mathbf{u}_{t}-\frac{1}{H}\sum_{\tau=t-H}^{t-1}\mathbf{u}_{\tau}\right\|_{*}^{2},$
$\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\left(\frac{1}{H}\sum_{\tau=t-H}^{t-1}\left\|\mathbf{u}_{t}-\mathbf{u}_{\tau}\right\|_{*}\right)^{2}.$

By the triangle inequality we get

$\displaystyle\frac{1}{H}\sum_{\tau=t-H}^{t-1}\left\|\mathbf{u}_{t}-\mathbf{u}_{\tau}\right\|_{\ast}$
$\displaystyle\leq$
$\displaystyle\frac{1}{H}\sum_{\tau=t-H}^{t-1}\sum_{q=\tau}^{t-1}\left\|\mathbf{u}_{q+1}-\mathbf{u}_{q}\right\|_{*}$
$\displaystyle=$
$\displaystyle\sum_{\tau=t-H}^{t-1}\frac{t-\tau}{H}\left\|\mathbf{u}_{\tau+1}-\mathbf{u}_{\tau}\right\|_{*}\leq\sum_{\tau=t-H}^{t-1}\left\|\mathbf{u}_{\tau+1}-\mathbf{u}_{\tau}\right\|_{*}$

By the Cauchy-Schwarz inequality, we get:

$\left(\sum_{\tau=t-H}^{t-1}\left\|\mathbf{u}_{\tau+1}-\mathbf{u}_{\tau}\right\|_{*}\right)^{2}\leq
H\sum_{\tau=t-H}^{t-1}\left\|\mathbf{u}_{\tau+1}-\mathbf{u}_{\tau}\right\|_{*}^{2}.$

Thus it follows that:

$\displaystyle\sum_{t=1}^{T}\|\mathbb{u}_{t}-\boldsymbol{\beta}_{t}\|^{2}_{\ast}$
$\displaystyle\leq$ $\displaystyle
H\sum_{t=1}^{T}\sum_{\tau=t-H}^{t-1}\left\|\mathbf{u}_{\tau+1}-\mathbf{u}_{\tau}\right\|_{*}^{2}$
$\displaystyle\leq$ $\displaystyle
H^{2}\sum_{t=1}^{T}\left\|\mathbf{u}_{t}-\mathbf{u}_{t-1}\right\|_{*}^{2}$

In proving part (ii) we follow the proof of Lemma 22 in Syrgkanis et al.
[2015]. We begin noting that

$\displaystyle\sum_{t=1}^{T}\left\|\mathbf{u}_{t}-\boldsymbol{\beta}_{t}\right\|_{*}^{2}$
$\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\left\|\mathbf{u}_{t}-\frac{1}{\sum_{\tau=0}^{t-1}\delta^{-\tau}}\sum_{\tau=0}^{t-1}\delta^{-\tau}\mathbf{u}_{\tau}\right\|_{\ast}^{2}$

We want to show that

$\sum_{t=1}^{T}\left\|\mathbf{u}_{t}-\frac{1}{\sum_{\tau=0}^{t-1}\delta^{-\tau}}\sum_{\tau=0}^{t-1}\delta^{-\tau}\mathbf{u}_{\tau}\right\|_{*}^{2}\leq\frac{1}{(1-\delta)^{3}}\sum_{t=1}^{T}\left\|\mathbf{u}_{t}-\mathbf{u}_{t-1}\right\|_{*}^{2}$

In proving this, we first note that

$\displaystyle\left\|\mathbf{u}_{t}-\frac{1}{\sum_{\tau=0}^{t-1}\delta^{-\tau}}\sum_{\tau=0}^{t-1}\delta^{-\tau}\mathbf{u}_{\tau}\right\|$
$\displaystyle=$
$\displaystyle\frac{1}{\sum_{\tau=0}^{t-1}\delta^{-\tau}}\sum_{\tau=0}^{t-1}\delta^{-\tau}\left\|\mathbf{u}_{t}-\mathbf{u}_{\tau}\right\|_{*}$
$\displaystyle\leq$
$\displaystyle\frac{1}{\sum_{\tau=0}^{t-1}\delta^{-\tau}}\sum_{\tau=0}^{t-1}\delta^{-\tau}\sum_{q=\tau}^{t-1}\left\|\mathbf{u}_{q+1}-\mathbf{u}_{q}\right\|_{*}$
$\displaystyle=$
$\displaystyle\frac{1}{\sum_{\tau=0}^{t-1}\delta^{-\tau}}\sum_{a=0}^{t-1}\left\|\mathbf{u}_{q+1}-\mathbf{u}_{q}\right\|_{*}\sum_{\tau=0}^{q}\delta^{-\tau}$
$\displaystyle=$
$\displaystyle\frac{1}{\sum_{\tau=0}^{t-1}\delta^{-\tau}}\sum_{q=0}^{t-1}\left\|\mathbf{u}_{q+1}-\mathbf{u}_{q}\right\|_{*}\delta^{-q}\frac{1-\delta^{q+1}}{1-\delta}$
$\displaystyle\leq$
$\displaystyle\frac{1}{1-\delta}\frac{1}{\sum_{\tau=0}^{t-1}\delta^{-\tau}}\sum_{q=0}^{t-1}\delta^{-q}\left\|\mathbf{u}_{q+1}-\mathbf{u}_{q}\right\|_{*}$

Second, by Cauchy-Schwartz we have

$\displaystyle\left(\frac{1}{1-\delta}\frac{1}{\sum_{\tau=0}^{t-1}\delta^{-\tau}}\sum_{q=0}^{t-1}\delta^{-q}\left\|\mathbf{u}_{q+1}-\mathbf{u}_{q}\right\|_{*}\right)^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{(1-\delta)^{2}}\frac{1}{\left(\sum_{\tau=0}^{t-1}\delta^{-\tau}\right)^{2}}\left(\sum_{q=0}^{t-1}\delta^{-q/2}\cdot\delta^{-q/2}\left\|\mathbf{u}_{q+1}-\mathbf{u}_{q}\right\|_{*}\right)^{2}$
$\displaystyle\leq$
$\displaystyle\frac{1}{(1-\delta)^{2}}\frac{1}{\left(\sum_{\tau=0}^{t-1}\delta^{-\tau}\right)^{2}}\sum_{q=0}^{t-1}\delta^{-q}\cdot\sum_{q=0}^{t-1}\delta^{-q}\left\|\mathbf{u}_{q+1}-\mathbf{u}_{q}\right\|_{*}^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{(1-\delta)^{2}}\frac{1}{\sum_{\tau=0}^{t-1}\delta^{-\tau}}\sum_{q=0}^{t-1}\delta^{-q}\left\|\mathbf{u}_{q+1}-\mathbf{u}_{q}\right\|_{*}^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{(1-\delta)^{2}}\frac{1}{\sum_{\tau=0}^{t-1}\delta^{t-\tau}}\sum_{q=0}^{t-1}\delta^{t-q}\left\|\mathbf{u}_{q+1}-\mathbf{u}_{q}\right\|_{*}^{2}$
$\displaystyle\leq$
$\displaystyle\frac{1}{\delta(1-\delta)^{2}}\sum_{q=0}^{t-1}\delta^{t-q}\left\|\mathbf{u}_{q+1}-\mathbf{u}_{q}\right\|_{*}^{2}$

Combining previous expressions we get:

$\left\|\mathbf{u}_{t}-\frac{1}{\sum_{\tau=0}^{t-1}\delta^{-\tau}}\sum_{\tau=0}^{t-1}\delta^{-\tau}\mathbf{u}_{\tau}\right\|_{*}^{2}\leq\frac{1}{\delta(1-\delta)^{2}}\sum_{q=0}^{t-1}\delta^{t-q}\left\|\mathbf{u}_{q+1}-\mathbf{u}_{q}\right\|_{*}^{2}$

Summing over all $t$ and re-arranging we get:

$\displaystyle\sum_{t=1}^{T}\left\|\mathbf{u}_{t}-\frac{1}{\sum_{\tau=0}^{t-1}\delta^{-\tau}}\sum_{\tau=0}^{t-1}\delta^{-\tau}\mathbf{u}_{\tau}\right\|^{2}$
$\displaystyle\leq$
$\displaystyle\frac{1}{\delta(1-\delta)^{2}}\sum_{t=1}^{T}\sum_{q=0}^{t-1}\delta^{t-q}\left\|\mathbf{u}_{q+1}-\mathbf{u}_{q}\right\|_{*}^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{\delta(1-\delta)^{2}}\sum_{q=0}^{T-1}\delta^{-q}\left\|\mathbf{u}_{q+1}-\mathbf{u}_{q}\right\|_{*}^{2}\sum_{t=q+1}^{T}\delta^{t}$
$\displaystyle=$
$\displaystyle\frac{1}{\delta(1-\delta)^{2}}\sum_{q=0}^{T-1}\delta^{-q}\left\|\mathbf{u}_{q+1}-\mathbf{u}_{q}\right\|_{*}^{2}\frac{\delta\left(\delta^{q}-\delta^{T}\right)}{1-\delta}$
$\displaystyle=$
$\displaystyle\frac{1}{(1-\delta)^{3}}\sum_{q=0}^{T-1}\left\|\mathbf{u}_{q+1}-\mathbf{u}_{q}\right\|_{*}^{2}\left(1-\delta^{T-q}\right)$
$\displaystyle\leq$
$\displaystyle\frac{1}{(1-\delta)^{3}}\sum_{q=0}^{T-1}\left\|\mathbf{u}_{q+1}-\mathbf{u}_{q}\right\|_{*}^{2}$

$\square$

###  B.1. Proof of Proposition 6

i) Combining Lemma 11 and Assumption (34) we know that

$\textsc{R}_{OFTRL}^{T}\leq\eta\varphi(\mathbb{0})+\frac{L}{2\eta}TB^{2}.$

Optimizing over $\eta$ we find that the regret is minimized at
$\eta=\sqrt{\frac{LTB^{2}}{2\varphi(\mathbb{0})}}$. Thus we obtain

$\textsc{R}_{OFTRL}^{T}\leq B\sqrt{2LT\varphi(\mathbb{0})}.$

ii) Combining Lemma 11 and Assumption (34) we know that

$\textsc{R}_{OFTRL}^{T}\leq\eta\varphi(\mathbb{0})+{L\over
2\eta}\sum_{t=1}^{T}\left\|\mathbf{u}_{t}-\boldsymbol{\beta}_{t}\right\|_{*}^{2}.$

Using Lemma 12i) combined with Eq. (34) we obtain that:

$\textsc{R}_{OFTRL}^{T}\leq\eta\varphi(\mathbb{0})+\frac{L}{2\eta}TS^{2}B^{2}$

Optimizing over $\eta$ we find that the regret is minimized at
$\eta=\sqrt{\frac{LTS^{2}B^{2}}{2\varphi(\mathbb{0})}}$. In particular, we
get:

$\textsc{R}_{OFTRL}^{T}\leq SB\sqrt{2LT\varphi(\mathbb{0})}.$

In showing part iii), we note that combining Lemma 11, Lemma 12ii), and
condition (34)

$\textsc{R}_{OFTRL}^{T}\leq\eta\varphi(\mathbb{0})+\frac{L}{2\eta(1-\delta)^{3}}TB^{2}$

Optimizing over $\eta$ we find that the regret is minimized at
$\eta=\sqrt{\frac{LTB^{2}}{2(1-\delta)^{3}\varphi(\mathbb{0})}}$. Thus, we
get:

$\textsc{R}_{OFTRL}^{T}\leq
B\sqrt{\frac{2LT\varphi(\mathbb{0})}{(1-\delta)^{3}}}.$

$\square$

###  B.2. Proof of Proposition 9

We proof this result using Theorem 6. Differentiability follows from the
Williams-Daly-Zachary theorem. Now let $\mathbb{q}$ and $\mathbb{q}^{\prime}$
with $\mathbb{q}^{\prime}\geq\mathbb{q}$. Note that
$\max_{i=1m\ldots,N}\\{\mathbb{q}^{\prime}_{i}+\epsilon_{i}\\}\geq\max_{i=1m\ldots,N}\\{\mathbb{q}_{i}+\epsilon_{i}\\}$.
Taking expectation with respect to $\epsilon$, it follows that
$\varphi(\mathbb{q}^{\prime})\geq\varphi(\mathbb{q})$, which implies the
increasing monotonicity of $\varphi$. Finally, positive translation invariance
follows from the fact that
$\varphi(\mathbb{q}+k\mathbb{1})=\mathbb{E}(\max_{i=1,\ldots,N}\\{\mathbb{q}_{i}+k+\epsilon_{i}\\})=\mathbb{E}(\max_{i=1,\ldots,N}\\{\mathbb{q}_{i}+\epsilon_{i}\\})+k=\varphi(\mathbb{q})+k$.
$\square$

###  B.3. Applications of the GNL model

####  B.3.1. The Cross Nested Logit (CNL) model

Vosha [1997] introduces the cross nested logit model. The main assumption of
this model is that $\lambda_{k}=\lambda$ for all $k=1,\ldots,K$. Thus, the
generator $G$ boils down to the expression:

$G(e^{\boldsymbol{\theta}_{t}/\eta})=\sum_{k=1}^{K}\left(\sum_{i=1}^{N}\left(\alpha_{ik}e^{\boldsymbol{\theta}_{it}/\eta}\right)^{1/\lambda}\right)^{\lambda}.$

In addition, in this case the constant $M$ is given by $M={2\over\lambda}-1$.
Accordingly, the Social Surplus function has Lipschitz continuous gradient
with constant $({2\over\lambda}-1)/\eta.$

####  B.3.2. The Paired Combinatorial Logit (PCL) model

In this model each pair of alternatives is represented by a nest. Formally,
the set of nests is defined as $\mathcal{N}=\left\\{(i,j)\in A\times A:i\neq
j\right\\}$. Accordingly, we define

$\alpha_{ik}=\begin{cases}{1\over 2(N-1)}&\mbox{if $k=(i,j),(j,i)$ with $j\neq
i$ }\\\ 0&\mbox{otherwise}\end{cases}.$

Using the previous expression, the generator $G$ can be written as:

$G(e^{\boldsymbol{\theta}_{t}/\eta})=\sum_{k=(i,j)\in\mathcal{N}}\left((\alpha_{ik}e^{\boldsymbol{\theta}_{it}/\eta})^{1/\lambda_{k}}+(\alpha_{jk}e^{\boldsymbol{\theta}_{jt}/\eta})^{1/\lambda_{k}}\right)^{\lambda_{k}}.$

In this case the Lipschitz constant is $({2\over\min\lambda_{k}}-1)/\eta.$

In addition, $\log G(\mathbb{1})\leq\log N$. Then the regret analysis follows
from Proposition 2.

####  B.3.3. The Ordered GEV (OGEV) model

Small [1987] studies a GEV model in which the alternatives are allocated to
nests based on their _proximity_ in an ordered set. Following Small [1987] we
define the set of overlapping nests to be

$\mathcal{N}=\\{1,\ldots,N+N^{\prime}\\},$

with $\alpha_{i\ell}>0$ for all $\ell\in\\{i,\ldots,N+N^{\prime}\\}$ and
$\alpha_{i\ell}=0$ for $i\in\mathcal{N}\setminus\\{i,\ldots,N+N^{\prime}\\}$,
and each alternative lies exactly in $N^{\prime}+1$ of these nests. In the
model there are $N+N^{\prime}$ overlapping nests. Each nest
$\ell\in\mathcal{N}$ is defined as $\mathcal{N}_{\ell}=\\{i\in A:l-m\leq
i\leq\ell\\}$ where $i\in\mathcal{N}_{l}$ for $\ell=i,\ldots,i+N^{\prime}$.
Despite this rather complex description, the generator function $G$ takes the
familiar form:

$G(e^{\boldsymbol{\theta}_{t}/\eta})=\sum_{k=1}^{N+N^{\prime}}\left(\sum_{i\in\mathcal{N}_{k}}(\alpha_{ik}e^{\boldsymbol{\theta}_{it}/\eta})^{1/\lambda_{k}}\right)^{\lambda_{k}}$

Thus in this case the Lipschitz constant is given by
$({2\over\min_{k=1,\ldots,K}\lambda_{k}}-1)/\eta$. Moreover, $\log
G(\mathbb{1})\leq\log N$. Thus Proposition 2 applies and we conclude that the
OGEV model is Hannan consistent.

####  B.3.4.  Principles of Differentiation GEV model (PDGEV)

Bresnahan et al. [1997] introduce the PDGEV model. This appproach is based on
the idea of markets for differentiated products. Using this idea, the set of
nests is defined in terms of the attributes that characterize the different
products (goods). For instance, in the context of transportation modeling, the
attributes can include mode to work, destination, number of cars, and
residential location. Accordingly, let $D$ be the set of attributes with
$\mathcal{N}=\bigcup_{d\in D}\mathcal{N}_{d}$ and
$\mathcal{N}_{d}=\\{k\in\mathcal{N}:\mbox{nest $k$ contains products with
attribute $d$}\\}$ be the nest that contains the alternatives with attribute
$d.$ Similarly, let $\mathcal{N}_{kd}$ denote the nest $k$ with attribute $d$.

$\alpha_{ik}=\left\\{\begin{array}[]{cl}\alpha_{d}&\text{ if }i\in
N_{kd}\text{ and }k\in\mathcal{N}_{d}\\\ 0&\text{
otherwise}\end{array}\right.$

In this case the generator $G$ takes the form:

$G(e^{\boldsymbol{\theta}_{t}/\eta})=\sum_{d\in
D}\alpha_{d}\sum_{k\in\mathcal{N}_{d}}\left(\sum_{i\in\mathcal{N}_{kd}}e^{\boldsymbol{\theta}_{it}/\eta\lambda_{d}}\right)^{\lambda_{d}}.$

It is easy to see that the previous generator is a particular case of the GNL
model. Furthermore, the Lipschitz constant is $({2\over
min_{d=1,\ldots,D}\lambda_{d}}-1)/\eta$ and $\log G(\mathbb{1})\leq\log N$.
Thus Proposition 2 applies in a direct way.

We close this appendix summarizing the regret bounds for the models described
in the main text and in this appendix. Table 1 below makes explicit our regret
analysis. The table displays how several GEV models shares the same optimized
regret bound.

Model | Optimal $\eta$ | Regret Bound
---|---|---
RUM | $\sqrt{{LTu_{max}^{2}\over 2\varphi(0)}}$ | $u_{max}\sqrt{2\varphi(0)LT}$
GEV | $\sqrt{{(2M+1)Tu_{max}^{2}\over 2\log G(1)}}$ | $u_{max}\sqrt{2\log G(\textbf{1})(2M+1)T}$
GNL | $\sqrt{\left({2\over\min_{k}\lambda_{k}}-1\right)Tu^{2}_{max}\over 2\log N}$ | $u_{max}\sqrt{2\log N\left({2\over\min_{k}\lambda_{k}}-1\right)T}$
PCL | $\sqrt{\left({2\over\min_{k}\lambda_{k}}-1\right)Tu^{2}_{max}\over 2\log N}$ | $u_{max}\sqrt{2\log N\left({2\over\min_{k}\lambda_{k}}-1\right)T}$
CNL | $\sqrt{\left({2\over\lambda}-1\right)Tu^{2}_{max}\over 2\log N}$ | $u_{max}\sqrt{2\log N\left({2\over\lambda}-1\right)T}$
OGEV | $\sqrt{\left({2\over\min_{k}\lambda_{k}}-1\right)Tu^{2}_{max}\over 2\log N}$ | $u_{max}\sqrt{2\log N\left({2\over\min_{k}\lambda_{k}}-1\right)T}$
PDGEV | $\sqrt{\left({2\over\min_{d}\lambda_{d}}-1\right)Tu^{2}_{max}\over 2\log N}$ | $u_{max}\sqrt{2\log N\left({2\over\min_{d}\lambda_{d}}-1\right)T}$
NL | $\sqrt{\left({2\over\min_{k}\lambda_{k}}-1\right)Tu^{2}_{max}\over 2\log N}$ | $u_{max}\sqrt{2\log N\left({2\over\min_{k}\lambda_{k}}-1\right)T}$
Logit | $\sqrt{Tu^{2}_{max}\over 2\log N}$ | $u_{max}\sqrt{2\log NT}$
Table 1. Summary of the optimized regret bound for the RUM and several GEV
models.