# Discrete Choice Multi-Armed Bandits

Emerson Melo Department of Economics, Indiana University Bloomington; e-mail:
<EMAIL_ADDRESS>David Müller Department of Mathematics, Chemnitz University of
Technology; e-mail<EMAIL_ADDRESS>
###### Abstract

This paper establishes a connection between a category of discrete choice
models and the realms of online learning and multiarmed bandit algorithms. Our
contributions can be summarized in two key aspects. Firstly, we furnish
sublinear regret bounds for a comprehensive family of algorithms, encompassing
the Exp3 algorithm as a particular case. Secondly, we introduce a novel family
of adversarial multiarmed bandit algorithms, drawing inspiration from the
generalized nested logit models initially introduced by Wen and Koppelman
(2001). These algorithms offer users the flexibility to fine-tune the model
extensively, as they can be implemented efficiently due to their closed-form
sampling distribution probabilities. To demonstrate the practical
implementation of our algorithms, we present numerical experiments, focusing
on the stochastic bandit case.

Keywords— Discrete choice, convex potential, online algorithms, multiarmed
bandits, regret

##  1 Introduction

In this paper we analyze how discrete choice models can be utilized in order
to design online optimization and multiarmed bandit algorithms for the experts
setting. In doing so, we build upon the gradient based prediction algorithms
(GBPA) introduced by Abernethy et al. (2016), where the authors derive
algorithms based on convex potential functions. In their framework, the online
learning algorithm employs an update step that corresponds to the gradient of
a specified convex potential function. Other classes of algorithms like Follow
the Perturbed Leader and and Follow the Regularized leader can be analyzed in
the GBPA framework. In the first part of this paper we show how gradient based
prediction algorithms for the experts setting can be derived from surplus
functions of random utility models (RUM). This connection has recently been
made by Melo (2021). For that reason some of the presented results resemble
results from Melo (2021). However the focus of our paper lies on the
computational aspects of the new designed algorithms. More precisely, we
incorporate algorithmic aspects of discrete choice models examined by Müller
et al. (2021b) into the GBPA framework from Abernethy et al. (2016). This
provides sublinear regret bounds for a whole family of algorithms including
the Exp3 algorithm as special case. By presenting and reanalyzing the online
optimization case we are able to achieve a better regret bound than Abernethy
et al. (2016) for the Gumbel smoothing scenario. Additionally, we compare the
algorithmic aspects of the multinomial logit and the nested logit surplus
function.
The second part of our work finally discusses the multiarmed bandit scenario.
The results are partly build on the analysis of part 2 and the work by
Abernethy et al. (2016). In particular, we derive a new family of adverserial
multiarmed bandit algorithms based on generalized nested logit models
introduced by Wen and Koppelman (2001). This is a remarkable generalization of
the Exp3 algorithm, see for example Cesa-Bianchi and Lugosi (2006).
Furthermore, we prove sublinear expected regret bounds for the family of
algorithms relying on the loss-only setting. The new algorithms yield a non-
independent change of the sampling probabilities. Hence, these algorithms
provide the user with the possibility to tune the model more thoroughly. At
the same time, the presented algorithms can be implemented in a highly
efficient manner, as the probabilities of the sampling distribution are given
in closed form.
The third part of the paper presents numerical experiments of the stochastic
bandit case. On the contrary to adverserial bandits, the former are
characterized by distribution following rewards. Our numerical experiments
show closing regret for the nested logit bandit algorithms. Moreover, we
provide examples to show that the algorithm is able to outperform the
classical Exp3-Algorithm. In particular, a nested logit based algorithm
provides structures in the Exploration/Exploitation trade-off that can not be
achieved by the algorithm based on the multinomial logit model.
Notation Our notation is quite standard. By $\mathbb{R}^{n}$ we denote the
space of n-dimensional vectors, where the vectors
$x=\left(x^{(1)},x^{(2)},\ldots,x^{(n)}\right)^{T}$ are column vectors. For
$x\in\mathbb{R}^{n}$ we write $x^{-(i)}\in\mathbb{R}^{n-1}$ meaning that the
$i$-th component of $x$ is missing. Analogously, we write
$x^{-(i,j)}\in\mathbb{R}^{n-2}$ meaning that both $i$-th and $j$-th components
of $x$ are missing. Using the latter, we write with some abuse of notation:

$x=\left(x^{-(i,j)},x^{(j)},x^{(i)}\right).$

We denote by $e_{j}\in\mathbb{R}^{n}$ the $j$-th coordinate vector of
$\mathbb{R}^{n}$ and write $e$ for the vector of an appropriate dimension
whose components are equal to one. Similar we write $\mathbf{0}$ for the
vector of an appropriate dimension whose components are equal to zero. For a
vector $x\in\mathbb{R}^{n}$ we write $e^{x}$ for the exponential operation of
all the components, i. e.

$e^{x}=\left(e^{x{(1)}},e^{x{(2)}},\ldots,e^{x{(i)}},\ldots,e^{x{(n)}}\right)^{T}.$

With this convention the following holds:

$e^{\mathbf{0}}=\left(e^{0},\ldots,e^{0},\ldots,e^{0}\right)^{T}=\left(1,\ldots,1,\ldots,e^{1}\right)^{T}=e^{T}.$

By $\mathbb{R}^{n}_{+}$ we denote the set of all vectors with nonnegative
components. We introduce the standard inner product in $\mathbb{R}^{n}$:

$\left\langle x,y\right\rangle=\sum\limits_{i=1}^{n}x^{(i)}y^{(i)}.$

If $y>0$ we define the vector division:

$\frac{x}{y}=\left(\frac{x^{(1)}}{y^{(1)}},\ldots,\frac{x^{(n)}}{y^{(n)}}\right)^{T}.$

For $x\in\mathbb{R}^{n}$ we use the norms

$\|x\|_{1}=\sum\limits_{i=1}^{n}|x^{(i)}|,\quad\|x\|_{2}=\sqrt{\sum\limits_{i=1}^{n}\left(x^{(i)}\right)^{2}},\quad\|x\|_{\infty}=\underset{1\leq
i\leq n}{\max}|x^{(i)}|.$

Given a function $f$ we denote its domain by
$\mbox{dom}f=\\{x\in\mathbb{R}^{n}\,|\,f(x)<\infty\\}.$ Further, we recall the
definition of the convex conjugate of the function $f:$

$f^{\star}(x^{\star})=\underset{x\in\mathbb{R}^{n}}{\sup}\left\langle
x,x^{\star}\right\rangle-f(x),$

where $x^{\star}$ is a vector of dual variables. Finally, for the
$(n-1)$-dimensional simplex we write

$\Delta_{n}=\left\\{p\in\mathbb{R}^{n}\,\left|\,\sum\limits_{i=1}^{n}p^{(i)}=1,\;p^{(i)}\geq
0,\;i=1,\ldots,n\right.\right\\}.$

The Bregman divergence of a convex function $f$ is given by:

$D_{f}(y,x)=f(y)-f(x)-\langle\nabla f(x),y-x\rangle,\quad\mbox{for all}\quad
x,y\in\mbox{dom}f.$

A function $f:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is $L$-strongly smooth
w.r.t. $\|\cdot\|_{\|}$ norm if it is differentiable, and for all
$x,y\in\mathbb{R}^{n}$ we have:

$f(y)\leq f(x)+\langle\nabla f(x),y-x\rangle+\frac{L}{2}\|y-x\|^{2}.$

The positive constant $L$ is called the smoothness parameter of $f$.
Obviously, for a $L$-strongly smooth function $f$ it holds:

$D_{f}(y,x)\leq\frac{L}{2}\|y-x\|^{2}.$

##  2 Discrete Choice Review

In this section, we review discrete choice behavior given by additive random
utility models (ARUM). We argue why those models are a natural choice in order
to design online optimization algortihms for the experts setting. Moreover, we
present a summary of recent results concerning the algorithmic aspects of
discrete choice models. In particular we focus on the connection between
additive random utility models and online optimization. In online optimization
data becomes available in sequential order rather than in batches. Thus, at
each iteration a new data stream arrives and an update of the decision is
made. However, contrary to multiarmed bandit models, an agent is able to
observe the full vector of payoffs or losses.

###  2.1 Additive Random Utility Models

The additive decomposition of utility is motivated by psychological
experiments accomplished in the 1920’s Thurstone (1927). A formal description
of this framework has been first introduce in economic context McFadden
(1978), where rational decision-makers choose from a finite set of mutually
exclusive alternatives $\\{1,\ldots,n\\}$. Each alternative $i=1,\ldots,n$
provides the utility

$u^{(i)}+\epsilon^{(i)},$

where $u^{(i)}\in\mathbb{R}$ is the deterministic utility part of the $i$-th
alternative and $\epsilon^{(i)}$ is its stochastic error. For the sake of
clarity we use vector notation for the deterministic utilities and the random
utilities, respectively:

$u=\left(u^{(1)},\ldots,u^{(n)}\right)^{T},\quad\epsilon=\left(\epsilon^{(1)},\ldots,\epsilon^{(n)}\right)^{T}.$

The so called surplus function of additive random utility models (ARUM) takes
a central role in our work. It is the expected maximum overall utility:

$E(u)=\mathbb{E}_{\epsilon}\left(\max_{1\leq i\leq
n}u^{(i)}+\epsilon^{(i)}\right).$ (1)

The following assumption concerning random errors is standard, see e.g.
Anderson et al. (1992).

######  Assumption 1.

The random vector $\epsilon$ follows a joint distribution with zero mean that
is absolutely continuous with respect to the Lebesgue measure and fully
supported on $\mathbb{R}^{n}.$

Under Assumption 1, the surplus function is convex and differentiable Anderson
et al. (1992). The well-known Williams-Daly-Zachary theorem states that the
gradient of E corresponds to the vector of choice probabilities McFadden
(1978) which can be stated in terms of partial derivatives of $E$:

$\frac{\partial E(u)}{\partial
u^{(i)}}=\mathbb{P}\left(u^{(i)}+\epsilon^{(i)}=\underset{1\leq i\leq
n}{\max}u^{(i)}+\epsilon^{(i)}\right),\quad i=1,\ldots,n,$ (2)

We denote this probability by $\mathbb{P}^{(i)}$. This formula holds due to
Assumption 1 as ties in Equation (1) occur with probability zero. Let us now
focus on generalized extreme value models (GEV) introduced by McFadden et al.
(1978). GEV comprise a broad class of models such as the popular multinomial
logit model. The vector $\epsilon$ of random errors defines a generalized
extreme value model (GEV) if it follows the joint distribution given by the
probability density function

$f_{\epsilon}\left(y^{(1)},\ldots,y^{(n)}\right)=\frac{\partial^{n}\exp\left(-G\left(e^{-y^{(1)}},\ldots,e^{-y^{(n)}}\right)\right)}{\partial
y^{(1)}\cdots\partial y^{(n)}},$

where the generating function $G:\mathbb{R}^{n}_{+}\rightarrow\mathbb{R}_{+}$
has to satisfy the following properties:

  * (G1)

$G$ is homogeneous of degree $\nicefrac{{1}}{{\mu}}>0$.

  * (G2)

$G\left(x^{(1)},\ldots,x^{(i)},\ldots,x^{(n)}\right)\rightarrow\infty$ as
$x^{(i)}\rightarrow\infty$, $i=1,\ldots,n$.

  * (G3)

For the partial derivatives of $G$ w.r.t. $k$ distinct variables it holds:

$\frac{\partial^{k}G\left(x^{(1)},\ldots,x^{(n)}\right)}{\partial
x^{\left(i_{1}\right)}\cdots\partial x^{\left(i_{k}\right)}}\geq 0\mbox{ if
}k\mbox{ is
odd},\quad\frac{\partial^{k}G\left(x^{(1)},\ldots,x^{(n)}\right)}{\partial
x^{\left(i_{1}\right)}\cdots\partial x^{\left(i_{k}\right)}}\leq 0\mbox{ if
}k\mbox{ is even}.$

It is well known from McFadden et al. (1978) that the surplus function for GEV
is

$E(u)=\mu\ln G\left(e^{u}\right),$ (3)

where we neglect an additive constant. The choice probability of the $i$-th
alternative is given by the $i$-th partial derivative of the surplus function
$E$:

$\mathbb{P}^{(i)}=\frac{\partial E(u)}{\partial u^{(i)}}=\mu\frac{\partial
G\left(e^{u}\right)}{\partial
x^{(i)}}\cdot\frac{e^{u^{(i)}}}{G\left(e^{u}\right)},$ (4)

An important family of GEV are the generalized nested logit (GNL) models
introduced by Wen and Koppelman (2001). They are defined by the generating
function

$G(x)=\sum_{\ell\in L}\left(\sum_{i=1}^{n}\left(\sigma_{i\ell}\cdot
x^{(i)}\right)^{\nicefrac{{1}}{{\mu_{\ell}}}}\right)^{\nicefrac{{\mu_{\ell}}}{{\mu}}}.$
(5)

Here, $L$ is a generic set of nests. The parameters $\sigma_{i\ell}\geq 0$
denote the shares of the $i$-th alternative with which it is attached to the
$\ell$-th nest. For any fixed $i\in\\{1,\ldots,n\\}$ they sum up to one:

$\sum_{\ell\in L}\sigma_{i\ell}=1.$

$\sigma_{i\ell}=0$ means that the $\ell$-th nest does not contain the $i$-th
alternative. Hence, the set of alternatives within the $\ell$-th nest is

$N_{\ell}=\left\\{i\,|\,\sigma_{i\ell}>0\right\\}.$

The nest parameters $\mu_{\ell}>0$ describe the variance of the random errors
while choosing alternatives within the $\ell$-th nest. Analogously, $\mu>0$
describes the variance of the random errors while choosing among the nests.
For the function $G$ to fulfill (G1)-(G3) we require:

$\mu_{\ell}\leq\mu\quad\mbox{for all }\ell\in L.$

We illustrate the concept of the generating function based on the multinomial
logit model (MNL). Recall that in the (MNL) the random errors in (1) are
assumed to be IID Gumbel-distributed.

######  Example 2.1 (Multinomial logit).

The generating function

$G(x)=\sum_{i=1}^{n}\left(x^{(i)}\right)^{\nicefrac{{1}}{{\mu}}}$

leads to the multinomial logit, since The corresponding surplus function
becomes

$E(u)=\mu\ln\sum_{i=1}^{n}e^{\nicefrac{{u^{(i)}}}{{\mu}}},$

and the choice probabilities are

$\mathbb{P}\left(u^{(i)}+\epsilon^{(i)}=\max_{1\leq j\leq
n}u^{(j)}+\epsilon^{(j)}\right)=\frac{e^{\nicefrac{{u^{(i)}}}{{\mu}}}}{\displaystyle\sum_{i=1}^{n}e^{\nicefrac{{u^{(i)}}}{{\mu}}}},\quad
i=1,\ldots,n.$ (6)

The MNL model is very popular. However, it is not able to capture non-
independent substitution patterns due to the Independence of Irrelevant
Alternatives Axiom (IAA). This might be a drawback in designing an online
optimization algorithm for several scenarios. Another well-known instance of
the GNL family which violates the IAA and is thus be able to deal with
dependent alternatives is the nested logit model.

######  Example 2.2 (Nested logit).

Let in GNL for every alternative $i\in\\{1,\ldots,n\\}$ there be a unique nest
$\ell_{i}\in L$ with $\sigma_{i\ell_{i}}=1$, and $\mu=1$. Then, the nests
$N_{\ell}=\left\\{i\,|\,\ell_{i}=\ell\right\\}$ are mutually exclusive, and
the generating function

$G(x)=\sum_{\ell\in L}\left(\sum_{i\in
N_{\ell}}x^{(i)\nicefrac{{1}}{{\mu_{\ell}}}}\right)^{\mu_{\ell}}$

leads to the nested logit (NL). The corresponding surplus function is

$E(u)=\mu\ln\sum_{\ell\in L}\left(\sum_{i\in
N_{\ell}}e^{\nicefrac{{u^{(i)}}}{{\mu_{\ell}}}}\right)^{\mu_{\ell}},$

and the choice probabilities for $i\in N_{\ell}$, $\ell\in L$ are

$\mathbb{P}^{(i)}=\frac{e^{\mu_{\ell}\ln\sum_{i\in
N_{\ell}}e^{\nicefrac{{u^{(i)}}}{{\mu_{\ell}}}}}}{\displaystyle\sum_{\ell\in
L}e^{\mu_{\ell}\ln\sum_{i\in
N_{\ell}}e^{\nicefrac{{u^{(i)}}}{{\mu_{\ell}}}}}}\cdot\frac{e^{\nicefrac{{u^{(i)}}}{{\mu_{\ell}}}}}{\displaystyle\sum_{i\in
N_{\ell}}e^{\nicefrac{{u^{(i)}}}{{\mu_{\ell}}}}}.$

###  2.2 Algorithmic Aspects of ARUM and Online Optimization

Recently, discrete choice models have been connected to convex optimization
Müller et al. (2021b). More precisely, the authors incorporate prox-functions
derived from the convex conjugates of discrete choice surplus functions into
dual averaging schemes. These results have also been applied by Melo (2021) in
order to develop online optimization algorithms based on discrete choice
surplus functions.
Let us formally review the framework of online optimization in the $n$-experts
setting. At each iteration $t$ an agent or learner observes a vector of
rewards $u_{t}\in\mathcal{Y}$, which is revealed after the agent made a
decision $x_{t}\in\mathcal{X}$ for the $t$-th iteration. In the $n$-experts
setting where the decision space $\mathcal{X}\subset\mathbb{R}^{n}$ coincides
with the simplex $\Delta_{n}$. Moreover we analyze the regret in the context
of online linear optimization, where the rewards are linear. Note that
distributional assumption concerning the generated rewards is made. In fact,
the rewards could be chosen adversarily. Thus, the the regret analysis leads
to robust worst-case bounds. Online optimization could also be interpreted as
a repeated game between the agent and an adversarily environment. We write for
the vector of cumulative rewards $U_{t}=\sum_{h=1}^{t}u_{h}$. Then, online
linear optimization can be formulated as follows:
For $t=1,\ldots,T$:

  * •

Agent chooses $x_{t}\in\Delta_{n}$;

  * •

Adversary reveals $u_{t}\in\mathcal{Y}$;

  * •

Agent gains $\langle x_{t},u_{t}\rangle$.

In this paper we focus on scenarios where the vectors of rewards are bounded,
i. .e we set $\mathcal{Y}=\left\\{u:\|u\|_{\infty}\leq K\right\\}$. In order
to measure the quality of the decisions in online optimization, the notion of
regret has been introduced:

$R_{T}=\max_{x\in\Delta_{n}}\;\langle x,U_{T}\rangle-\sum_{t=1}^{T}\langle
x_{t},u_{t}\rangle.$ (7)

The algorithms of online optimization can be separated into two classes,
Follow the Regularized Leader (FTRL) and Follow the Perturbed Leader (FTPL),
see e. g. Abernethy et al. (2016). Follow the Regularized Leader algorithms
(FTRL) are based on regularization techniques, well known from optimization.
Hence, the regret analysis heavily relies on convex analysis tools. On the
other hand, FTPL algorithms perturb the cumulative gain vector by a random
variable. Abernethy et al. (2016) show that the decision variable of all
algorithms of these classes can be characterized by the gradient of a scalar-
valued convex potential function. Melo (2021) proves that the surplus function
of many GEV models lead to algorithms where the regret is growing by the order
$\mathcal{O}(\sqrt{T})$. Thus, the average regret tends to zero, which is
known as Hannan Consistency, see e. g. Cesa-Bianchi and Lugosi (2006). The key
aspect to create GBPA from discrete choice models is the convex perspective of
the surplus function (1):

$\tilde{E}(U;\eta):=\eta\cdot E\left(U/\eta\right),\quad\eta>0.$ (8)

Rewriting Equation (8) yields:

$\eta\cdot E\left(U/\eta\right)=\eta\cdot\mathbb{E}\left(\max_{1\leq i\leq
n}U^{(i)}/\eta+\epsilon^{(i)}\right)=\mathbb{E}\left(\max_{1\leq i\leq
n}U^{(i)}+\eta\cdot\epsilon^{(i)}\right),$

which is due to Assumption 1 a stochastic smoothing of the $\max$-function
defined by Abernethy et al. (2016). Such a surplus functions serves as
potential function. Hence, it remains to identify random utility models such
that algorithms are Hannan-consistent. Our algorithms and results are very
similar to Melo (2021), however we provide the result and a proof for several
reasons. First, we examine general discrete choice models. Additionally, since
we want to discuss the computational aspects of the different algorithms, a
derivation of the results regarding the regret bounds clarify the reading. In
order to analyze general ARUM we rely on the finite modes condition from
Müller et al. (2021b).

######  Definition 1.

Let $g_{k,m}$ denote the density function of differences
$\epsilon^{(m)}-\epsilon^{(k)}$, $k\not=m$ of random errors. Any point
$\bar{z}_{k,m}\in\mathbb{R}$ which maximizes the density function $g_{k,m}$ is
called a mode of the random variable $\epsilon^{(m)}-\epsilon^{(k)}$.

We restrict our analysis to ARUM satisfying this condition.

######  Assumption 2.

The differences $\epsilon^{(k)}-\epsilon^{(m)}$ of random errors have finite
modes for all $k\not=m$.

Let us state the blueprint for a GBPA based on random utility models
satisfying Assumptions 1 and 2:

######  Algorithm 1 (RUM-Algorithm for $n$-experts).

Input: Discrete choice surplus function E and set of parameters $\Theta$,
Stepsize $\eta>0$
Initalize: $U_{0}=\mathbf{0}$, $x_{0}=\frac{1}{n}\cdot e$
For $t=1,\ldots,T$ do: • Choose $x_{t}=\nabla\tilde{E}(U_{t-1};\eta)$ •
Observe $u_{t}\in\mathcal{Y}$ • Receive reward $\langle u_{t},x_{t}\rangle$ •
Update $U_{t}=U_{t-1}+u_{t}$.

######  Theorem 2.1.

Let expectation of the maximum of random errors be bounded above, i. e.
$\mathbb{E}(\max_{1\leq i\leq n}\epsilon^{(i)})\leq\alpha$. Then Algorithm 1
is Hannan-consistent, i. e.

$R(T)\leq\eta\cdot\alpha+\frac{L\cdot K^{2}\cdot T}{\eta}$

where $L=2\sum_{i=1}^{n}\sum_{j\neq i}g_{i,j}(\bar{z}_{i,j})$. Optimizing the
scaling parameter $\eta$ yields

$R(T)\leq 2\cdot\sqrt{\alpha\cdot LT}\cdot K.$

###### Proof.

Due to Assumption 1, it holds that $x_{t}\in\mbox{rint}(\Delta_{n})$ for all
$t$. Consequently, Algorithm 1 is an instance of the GPBA Abernethy et al.
(2016). Furthermore, under Assumption 2 the surplus function is $L$-strongly
smooth w.r.t. $\|\cdot\|_{\infty}$ Müller et al. (2021b). Thus, the
perspective $\tilde{E}$ is $\frac{L}{\eta}$-strongly smooth and the Bregman
Divergence between $U$ and $U+u$ is bounded above, i. e.

$\tilde{E}(U+u;\eta)-\tilde{E}(U;\eta)-\langle\nabla\tilde{E}(U;\eta),u\rangle\leq\frac{L}{2\eta}\cdot\|u\|^{2}_{\infty}.$

Therefore it is justified to apply Theorem $1.9$ of Abernethy et al. (2016)
which concludes the assertion. ∎

To the best of our knowledge, online optimization algorithms based on general
discrete choice surplus functions have not been analyzed in the literature
before.
The regret bound derived in Theorem 1 is strongly determined by the the
smoothness parameter of discrete choice models which depends on the number of
alternatives. In Müller et al. (2021b) dimension-independent estimates of the
smoothness parameter for several discrete choice models have been derived. In
particualar, GEV models whose generating function $G$ satisfy the following
inequality for all
$x=\left(x^{(1)},\ldots,x^{(n)}\right)^{T}\in\mathbb{R}^{n}_{+}$:

$\sum_{i=1}^{n}\frac{\partial^{2}G(x)}{\partial x^{(i)2}}\cdot x^{(i)2}\leq
M\cdot G(x),$ (9)

with some constant $M\in\mathbb{R}$. Then, the estimate of the smoothness
parameter is Müller et al. (2021b):

$\frac{1}{\mu}+2\left(\left(1-\frac{1}{\mu}\right)+\mu M\right).$ (10)

Moreover, the same authors prove that for the family of GNL models this
condition is satisfied. This fact leads to the Hannan-consistency of GNL based
online optimization algorithms as proved in Melo (2021). For the remaining
part of this section we want to focus on the computational aspects of GNL
based algorithms. Clearly, the updates of Algorithm 1 vary with the choice of
the GNL model. The well known exponentially weighted algorithms is based on
the multinomial logit model and therefore inherits IAA property which might be
not desirable in situations where some of the actions are dependent. As
mentioned in Section 2.1 other GNL models like the nested logit have the
possibility to incorporate such dependence structure in the updates. On the
same time the computational efficiency of the updates is remained due to the
closed form given in (4). The estimate of the smoothness parameter is given by
Müller et al. (2021b):

$\frac{2}{\min_{\ell\in L}\mu_{\ell}}-\frac{1}{\mu}.$ (11)

Let us further compare the nested logit to the multinomial based algorithm. It
follows from (11) for the MNL algorithm

$L_{\mbox{MNL}}=\frac{1}{\mu\cdot\eta}$

and for the nested logit111The smoothness parameter of the nested logit
surplus function can be improved by the factor $\frac{1}{2}$. This is shown by
the authors of Müller et al. (2021a) who derive the modulus of strong
smoothness.

$L_{\mbox{NL}}=\frac{2}{\min_{\ell\in L}\mu_{\ell}\cdot\eta}.$

Obviously, the smoothness parameter of the MNL surplus function is better than
the smoothness parameter of the NL surplus function.
Let us focus on the parameter $\alpha$. For that we can rely on the analysis
of the function $E$, since

$E(0)=\mathbb{E}(\max_{1\leq i\leq n}\epsilon^{(i)}).$

Due to Equation (3) we can rewrite this as

$E(\mathbf{0})=\mu\ln G\left(e^{\mathbf{0}}\right)=\mu\ln G\left(e\right).$

For the MNL generating function (see Example 2.1) we have:

$G(e)=\sum_{i=1}^{n}\left(1\right)^{\nicefrac{{1}}{{\mu}}}=n,$

from where it follows that

$E_{\mbox{MNL}}(\mathbf{0})=\mu\cdot\ln(n).$

In the case of $\eta=1$, we have $\alpha=\ln(n)$ which is remarkable better
than the $2\ln(2n)$ bound derived by the moment generating function trick in
Abernethy et al. (2016). Let us examine the nested logit case:

$G(e)=\sum_{\ell\in L}\left(\sum_{i\in
N_{\ell}}1^{\nicefrac{{1}}{{\mu_{\ell}}}}\right)^{\mu_{\ell}}=\sum_{\ell\in
L}\left(\left|N_{\ell}\right|^{\mu_{\ell}}\right)\overset{(\star)}{\leq}\sum_{\ell\in
L}|N_{\ell}|=n,$

where in the inequality we have used the facts that $\mu_{\ell}\leq 1$ for all
$\ell\in L$ and that every alternative belongs to a unique nest. We derive a
lower bound

$\displaystyle G(e)$ $\displaystyle=\sum_{\ell\in L}\left(\sum_{i\in
N_{\ell}}1^{\nicefrac{{1}}{{\mu_{\ell}}}}\right)^{\mu_{\ell}}=\sum_{\ell\in
L}\left(\left|N_{\ell}\right|^{\mu_{\ell}}\right)$
$\displaystyle\geq\sum_{\ell\in L}\left(\left|N_{\ell}\right|^{\min_{\ell\in
L}\mu_{\ell}}\right)\overset{(\star)}{\geq}\left(\sum_{\ell\in
L}\left|N_{\ell}\right|\right)^{\min_{\ell\in L}\mu_{\ell}}$
$\displaystyle\geq n^{\min_{\ell\in L}\mu_{\ell}}.$

Again, we have used the facts that $\mu_{\ell}\leq 1$ for all $\ell\in L$ and
that every alternative belongs to a unique nest. For inequality $(\star)$ we
applied the inequality

$|\sum_{i=1}^{n}x^{(i)}|^{p}\leq\sum_{i=1}^{n}|x^{(i)}|^{p},\quad
p\in\left(0,1\right]$

Altogether, this proves the following corollary:

######  Corollary 2.1.

For the MNL surplus function we have

$\alpha=\mu\cdot\ln(n).$

For the NL surplus function it holds:

${\min_{\ell\in L}\mu_{\ell}}\cdot\ln(n)\leq\alpha\leq\ln(n).$

##  3 GEV Mulitarmed Bandit Algorithms

In this section we address the adverserial multiarmed bandit setting. The goal
is to generalize the Exp3-algorithm Auer et al. (2002), which is mainly based
on the Gumbel distribution, to further GEV resp. GNL models presented in
Section 2.1. Therefore, we show that surplus functions from those models can
be incorporated in the GBPA algorithm for the multiarmed bandit setting from
Abernethy et al. (2016). In the online learning framework the learner gets at
the $t$\- round full feedback in terms of the vector $u_{t}$. This means an
agent is able to observe the reward of each action independent from the
selected action. In the multiarmed bandit setting however, the learner
receives limited feedback. Precisely, after choosing a probability
distribution over the n arms at the $t$-th iteration, one arm $i_{t}$ is
sampled according to the chosen distribution and only the reward
$u_{t}^{(i_{t})}$ of this sampled option is revealed. Thus, the agent has to
estimate the reward vector of round $t$. This leads to the popular
exploration/exploitation trade-off. Exploration means that the agent has to
pull an arm in order to get information regarding its rewards. On the other
hand, the learner wants to exploit the information received so far and
frequently pull the most promising arm. Clearly, the learner’s problem becomes
more evolved. In the adverserial multiarmed bandit setting no distributional
assumptions regarding the rewards are made, see for example Slivkins et al.
(2019).
Apart from the EXP3, there are many algorithms tackling the multiarmed bandit
such as Thompson sampling algorithms, the UCB algortihm, see Lattimore and
Szepesvári (2020) for an overview.
The gradients of such a potential function have to lie in the relative
interior of the simplex, i. e.
$\nabla\tilde{\Phi}\subset\mbox{rint}(\Delta_{n})$. Let a potential function
$\Phi$ and a potentially adversary sequence of negative rewards
$u_{1},u_{2},\ldots,u_{T}\in\left[-1,0\right]^{n}$ be given. Then the template
of the GBPA for Multi-Armed Bandits reads as (Abernethy et al. (2016)): For
$t=1,\ldots,T$:

  * •

Set $\hat{U}_{0}=0$;

  * •

Learner samples $i_{t}$ according to discrete distribution
$p(\hat{U}_{t-1})=\nabla\tilde{\Phi}(\hat{U}_{t-1})$;

  * •

Learner observes and gains $u^{(i_{t})}_{t}\in\left[-1,0\right]$;

  * •

Learner estimates $\hat{u}_{t}:=\frac{u^{(i_{t})}_{t}}{p(\hat{U}_{t-1})}\cdot
e_{i_{t}}$;

  * •

Update $\hat{U}_{t}=\hat{U}_{t-1}+\hat{u}_{t}$.

Due to the sampling process in each round, there is randomness in the
performance of any algorithm. Thus, a well performing algorithm is measured
w.r.t. the expected regret:

$\mathbb{E}\left[R_{T}\right]=\max_{1\leq i\leq
n}U^{(i)}_{T}-\mathbb{E}\left[\sum_{t=1}^{T}\langle\nabla\tilde{\Phi}(\hat{U}_{t}),u_{t}\rangle\right],$
(12)

where the expectation is taken over the agent’s actions and the randomness in
the environment. The ”loss only” setting is crucial in order to prove near-
optimal (expected) regret bounds, see Abernethy et al. (2016). In what
follows, we derive a class of new multi-armed bandit algorithms from ARUM. In
particular, we identify GEV models which are differential-consistent according
to Definition 2. This has several advantages. First, we provide an easy way to
implement family of bandit algorithms. By easy to implement, we mean that the
sampling probabilities are given in closed form solutions. Moreover, by
specifying a suitable ARUM, the learner is able take into account possible
correlations amongst the arms. Again, the key aspect is the surplus function
of GEV models.

######  Algorithm 2 (GEV-Algorithms for multiarmed bandits).

Input: Discrete choice surplus function E and set of parameters $\Theta$,
Stepsize $\eta>0$
Initalize: $\hat{U}_{0}=0$
For $t=1,\ldots,T$ do: • Sample an arm $i_{t}$ according to the distribution
$x_{t}=\nabla\tilde{E}(\hat{U}_{t-1};\eta)$ • Observe and gain reward
$u^{(i_{t})}_{t}\in\left[-1,0\,\right]^{n}$ • Estimate gain vector
$\hat{u}_{t}=\frac{u^{(i_{t})}_{t}}{x^{(i_{t})}_{t}}\cdot e^{(i_{t})}$ •
Update $\hat{U}_{t}=\hat{U}_{t-1}+\hat{u}_{t}$.

A few remarks in order. First, it is well known that the gradient of a GEV
surplus function lies in the relative interior of the probability simplex.
Hence, Algorithm 2 provide concrete specifications of the GBPA for the
multiarmed bandit problem by Abernethy et al. (2016). Second, Algorithm 2
summarizes a large class of algorithms in a surprisingly easy manner. In fact,
selecting specific GEV model yields different versions of Algorithm 2 with
different sampling probabilities. These versions obviously include the popular
EXP3-algorithm as special case ( Example 2.1). Finally, the numerical
implementation can be done efficiently. Recall that the surplus function and
the choice probabilities of any GEV model are given in closed forms. Hence, we
don’t have to rely on techniques like geometric resampling Neu and Bartók
(2013) and the sampling and estimation steps crucially simplify.

######  Lemma 3.1.

The expected regret of Algorithm 2 can be written as

$\mathbb{E}(R_{T})\leq\mathbb{E}_{i_{1},\ldots,i_{T}}\left[\sum_{t=1}^{T}\mathbb{E}_{i_{t}}\left[D_{\tilde{E}}\left(\hat{U_{t}},\hat{U_{t-1}}\right)|\hat{U_{t-1}}\right]\right]+\tilde{E}\left(0;\eta\right)$

###### Proof.

We invoke (Abernethy et al., 2016, Lemma 1.12) and use the fact that the
convex perspective of the surplus function is a potential function. ∎

The estimation of the vector $\hat{u}_{t}$ involves an inverse scaling by the
sampling probabilities $p(\hat{U}_{t-1})$ and hence the divergence
$D_{\tilde{E}}$ between $\hat{U}_{t}$ and $\hat{U}_{t-1}$ depends on the
sampling probabilities. Due to this reason, the divergence can become
arbitrarily large, which could lead to exploding regret bounds. Therefore,
Abernethy et al. (2016) introduce a condition for the potential function under
which this divergence can be bounded.

######  Definition 2 (Differential Consistency).

A convex function $f$ is $C$-differentially-consistent if there exists a
constant $C>0$ such that for all $U\in(-\infty,0)^{n}$ and $i=1,\ldots,n$ it
holds

$\nabla^{2}_{ii}f(U)\leq C\cdot\nabla_{i}f(U).$ (13)

For $C$-differentially-consistent potential functions an upper bound for the
divergence part of Lemma 3.1, can be proved (Abernethy et al., 2016, Theorem
1.13) i. e.

$\mathbb{E}_{i_{t}}\left[D_{\tilde{E}}\left(\hat{U_{t}},\hat{U_{t-1}}\right)|\hat{U_{t-1}}\right]\leq\frac{C\cdot
n}{2},\quad t=1,\ldots,T.$ (14)

As already explained, Algorithm 2 is able to capture possible dependencies of
action in the sampling process. Furthermore, sampling and estimation steps can
be processed in a numerically highly efficient manner. Therefore, we are
interested in finding GEV models such that the surplus function is
$C$-differentially consistent. The following Theorem characterizes GEV models
satisfying this property.

######  Theorem 3.1.

Let a generating function $G$ satisfy for all $i=1,\ldots,n$, and
$x=\left(x^{(1)},\ldots,x^{(n)}\right)^{T}\in\mathbb{R}^{n}_{+}$

$\frac{\partial^{2}G(x)}{\partial x^{(i)2}}\cdot
x^{(i)}\leq\tilde{C}\cdot\frac{\partial G(x)}{\partial x^{(i)}},$ (15)

for some constant $\tilde{C}\in\left(-1,\infty\right)$. Then, the
corresponding surplus function $E$ is $C$-differentially-consistent with
$C=\tilde{C}+1$.

###### Proof.

We have to show that Condition (13) holds true for the surplus function. Thus,
we need expressions for $\frac{\partial E(u)}{\partial u^{(i)}}$ and
$\frac{\partial^{2}E(u)}{\partial u^{(i)2}}$. The former has been stated in
Equation (4). An expression for the latter has been for example given by
Müller et al. (2021b). We present both terms:

$\begin{array}[]{rcl}\displaystyle\frac{\partial E(u)}{\partial
u^{(i)}}&=&\displaystyle\mathbb{P}^{(i)}=\displaystyle\mu\frac{\partial
G\left(e^{u}\right)}{\partial
x^{(i)}}\cdot\frac{e^{u^{(i)}}}{G\left(e^{u}\right)},\\\ \\\
\displaystyle\frac{\partial^{2}E(u)}{\partial
u^{(i)2}}&=&\displaystyle\frac{1}{\mu}\frac{\partial E(u)}{\partial
u^{(i)}}\left(1-\frac{\partial E(u)}{\partial
u^{(i)}}\right)+\left(1-\frac{1}{\mu}\right)\frac{\partial E(u)}{\partial
u^{(i)}}+\mu\frac{\partial^{2}G\left(e^{u}\right)}{\partial
x^{(i)2}}\cdot\frac{\left(e^{u^{(i)}}\right)^{2}}{G\left(e^{u}\right)}.\end{array}$

We compute

$\displaystyle\frac{\partial^{2}E(u)}{\partial u^{(i)2}}$
$\displaystyle=\displaystyle\frac{1}{\mu}\frac{\partial E(u)}{\partial
u^{(i)}}\left(1-\frac{\partial E(u)}{\partial
u^{(i)}}\right)+\left(1-\frac{1}{\mu}\right)\frac{\partial E(u)}{\partial
u^{(i)}}+\mu\frac{\partial^{2}G\left(e^{u}\right)}{\partial
x^{(i)2}}\cdot\frac{\left(e^{u^{(i)}}\right)^{2}}{G\left(e^{u}\right)}$
$\displaystyle=\frac{1}{\mu}\mathbb{P}^{(i)}\cdot\underbrace{\left(1-\mathbb{P}^{(i)}\right)}_{\leq
1}+\left(1-\frac{1}{\mu}\right)\mathbb{P}^{(i)}+\mu\frac{\partial^{2}G\left(e^{u}\right)}{\partial
x^{(i)2}}\cdot\frac{\left(e^{u^{(i)}}\right)^{2}}{G\left(e^{u}\right)}$
$\displaystyle\leq\left(\frac{1}{\mu}+1-\frac{1}{\mu}\right)\mathbb{P}^{(i)}+\mu\cdot\frac{e^{u^{(i)}}}{G\left(e^{u}\right)}\cdot\frac{\partial^{2}G\left(e^{u}\right)}{\partial
x^{(i)2}}\cdot e^{u^{(i)}}$
$\displaystyle\overset{\eqref{eq:diff_cons.condition.gev}}{\leq}\mathbb{P}^{(i)}+\tilde{C}\cdot\mu\cdot\frac{\partial
G\left(e^{u}\right)}{\partial
x^{(i)}}\cdot\frac{e^{u^{(i)}}}{G\left(e^{u}\right)}=\left(1+\tilde{C}\right)\cdot\frac{\partial
E(u)}{\partial u^{(i)}}.$

Altogether, we hence conclude that

$\frac{\partial^{2}E(u)}{\partial u^{(i)2}}\leq C\cdot\frac{\partial
E(u)}{\partial u^{(i)}},$

which shows the assertion. ∎

Theorem 3.1 yields a sufficient condition for GEV models to be
$C$-differential-consistent. A natural question is to ask how the strong
smoothness condition (9) is related to Condition (15).

######  Proposition 3.1.

Any generating function $G$ which satisifies Condition (15) also satisfies
Condition (9) with $M=\frac{\tilde{C}}{\mu}$.

###### Proof.

Let us fix any
$x=\left(x^{(1)},\ldots,x^{(n)}\right)^{T}\in\mathbb{R}^{n}_{+}$ and multiply
(15) by $x^{(i)}\in\mathbb{R}^{n}_{+}$ which yields for all $i=1,\ldots,n$

$\frac{\partial^{2}G(x)}{\partial x^{(i)2}}\cdot
x^{(i)2}\leq\tilde{C}\cdot\frac{\partial G(x)}{\partial x^{(i)}}\cdot\cdot
x^{(i)}.$

Therefore, summing up over all $i=1,\ldots,n$ does not change the inequality,
i. e.

$\sum_{i=1}^{n}\frac{\partial^{2}G(x)}{\partial x^{(i)2}}\cdot
x^{(i)2}\leq\tilde{C}\cdot\sum_{i=1}^{n}\frac{\partial G(x)}{\partial
x^{(i)}}\cdot x^{(i)}.$ (16)

Due to Property $G(1)$, any generating function is $\frac{1}{\mu}$\-
homogeneous. Applying Euler’s theorem on homogeneous functions to the right
side of (16), see for example in Pemberton and Rau (2015) provides

$\tilde{C}\cdot\sum_{i=1}^{n}\frac{\partial G(x)}{\partial x^{(i)}}\cdot
x^{(i)}=\tilde{C}\cdot\frac{1}{\mu}G(x).$

Altogether, we conclude that

$\sum_{i=1}^{n}\frac{\partial^{2}G(x)}{\partial x^{(i)2}}\cdot
x^{(i)2}\leq\frac{\tilde{C}}{\mu}G(x).$

Note that $x\in\mathbb{R}^{n}_{+}$ has been chose arbitrarily. ∎

Combined with the results from Melo (2021) and Abernethy et al. (2016)
Proposition 3.1 states the class of GEV models that can be used for full
information online optimization is at least as large as the class of GEV
models suitable for bandit algorithms.

Let us turn our attention to the generalized nested logit models introduced by
Wen and Koppelman (2001) and recall the generating function presented in
Equation (5):

$G(x)=\sum_{\ell\in L}\left(\sum_{i=1}^{n}\left(\sigma_{i\ell}\cdot
x^{(i)}\right)^{\nicefrac{{1}}{{\mu_{\ell}}}}\right)^{\nicefrac{{\mu_{\ell}}}{{\mu}}}.$

Let us analyze the $C$-differential-consistency of GNL models.

######  Theorem 3.2.

For GNL the corresponding surplus function is
$\frac{1}{\displaystyle\min_{\ell\in L}\mu_{\ell}}$\- differential-consistent.

###### Proof.

We review the following formulas, which were derived in the proof of Corollary
4 by Müller et al. (2021b):

$\frac{\partial G\left(x\right)}{\partial x^{(i)}}=\frac{1}{\mu}\sum_{\ell\in
L}\left(\sum_{i=1}^{n}\left(\sigma_{i\ell}\cdot
x^{(i)}\right)^{\nicefrac{{1}}{{\mu_{\ell}}}}\right)^{\nicefrac{{\mu_{\ell}}}{{\mu}}-1}\left(\sigma_{i\ell}\cdot
x^{(i)}\right)^{\nicefrac{{1}}{{\mu_{\ell}}}-1}\cdot\sigma_{i\ell},$

and

$\begin{array}[]{rcl}\displaystyle\frac{\partial^{2}G(x)}{\partial
x^{(i)2}}&=&\displaystyle\frac{1}{\mu}\sum_{\ell\in
L}\frac{1}{\mu_{\ell}}\left(\frac{\mu_{\ell}}{\mu}-1\right)\left(\sum_{i=1}^{n}\left(\sigma_{i\ell}\cdot
x^{(i)}\right)^{\nicefrac{{1}}{{\mu_{\ell}}}}\right)^{\nicefrac{{\mu_{\ell}}}{{\mu}}-2}\left(\left(\sigma_{i\ell}\cdot
x^{(i)}\right)^{\nicefrac{{1}}{{\mu_{\ell}}}-1}\cdot\sigma_{i\ell}\right)^{2}\\\
\\\ &+&\displaystyle\frac{1}{\mu}\sum_{\ell\in
L}\left(\frac{1}{\mu_{\ell}}-1\right)\left(\sum_{i=1}^{n}\left(\sigma_{i\ell}\cdot
x^{(i)}\right)^{\nicefrac{{1}}{{\mu_{\ell}}}}\right)^{\nicefrac{{\mu_{\ell}}}{{\mu}}-1}\left(\sigma_{i\ell}\cdot
x^{(i)}\right)^{\nicefrac{{1}}{{\mu_{\ell}}}-2}\cdot\sigma_{i\ell}^{2}.\end{array}$

Due to $\mu_{\ell}\leq\mu$, $\ell\in L$, it holds:

$\frac{\partial^{2}G(x)}{\partial x^{(i)2}}\leq\frac{1}{\mu}\sum_{\ell\in
L}\left(\frac{1}{\mu_{\ell}}-1\right)\left(\sum_{i=1}^{n}\left(\sigma_{i\ell}\cdot
x^{(i)}\right)^{\nicefrac{{1}}{{\mu_{\ell}}}}\right)^{\nicefrac{{\mu_{\ell}}}{{\mu}}-1}\left(\sigma_{i\ell}\cdot
x^{(i)}\right)^{\nicefrac{{1}}{{\mu_{\ell}}}-2}\cdot\sigma_{i\ell}^{2}.$

We multiply by $x^{(i)}$ and get

$\frac{\partial^{2}G(x)}{\partial x^{(i)2}}\cdot
x^{(i)}\leq\frac{1}{\mu}\sum_{\ell\in
L}\left(\frac{1}{\mu_{\ell}}-1\right)\left(\sum_{i=1}^{n}\left(\sigma_{i\ell}\cdot
x^{(i)}\right)^{\nicefrac{{1}}{{\mu_{\ell}}}}\right)^{\nicefrac{{\mu_{\ell}}}{{\mu}}-1}\left(\sigma_{i\ell}\cdot
x^{(i)}\right)^{\nicefrac{{1}}{{\mu_{\ell}}}-1}\cdot\sigma_{i\ell}.$

We follow similar considerations as Müller et al. (2021b) and conclude

$\displaystyle\frac{\partial^{2}G(x)}{\partial x^{(i)2}}\cdot x^{(i)}$
$\displaystyle\leq\frac{1}{\mu}\sum_{\ell\in
L}\left(\frac{1}{\mu_{\ell}}-1\right)\left(\sum_{i=1}^{n}\left(\sigma_{i\ell}\cdot
x^{(i)}\right)^{\nicefrac{{1}}{{\mu_{\ell}}}}\right)^{\nicefrac{{\mu_{\ell}}}{{\mu}}-1}\left(\sigma_{i\ell}\cdot
x^{(i)}\right)^{\nicefrac{{1}}{{\mu_{\ell}}}-1}\cdot\sigma_{i\ell}$
$\displaystyle\leq\displaystyle\max_{\ell\in
L}\left(\frac{1}{\mu_{\ell}}-1\right)\cdot\frac{1}{\mu}\sum_{\ell\in
L}\left(\sum_{i=1}^{n}\left(\sigma_{i\ell}\cdot
x^{(i)}\right)^{\nicefrac{{1}}{{\mu_{\ell}}}}\right)^{\nicefrac{{\mu_{\ell}}}{{\mu}}-1}\left(\sigma_{i\ell}\cdot
x^{(i)}\right)^{\nicefrac{{1}}{{\mu_{\ell}}}-1}\cdot\sigma_{i\ell}$
$\displaystyle=\left(\frac{1}{\displaystyle\min_{\ell\in
L}\mu_{\ell}}-1\right)\cdot\frac{\partial G\left(x\right)}{\partial x^{(i)}}.$

Consequently, we can set $\tilde{C}=\left(\frac{1}{\displaystyle\min_{\ell\in
L}\mu_{\ell}}-1\right)$. It remains to apply Theorem 3.1 which concludes the
assertion by yielding $C=\frac{1}{\displaystyle\min_{\ell\in L}\mu_{\ell}}$. ∎

Theorem 3.2 enables to apply the family of GNL models in the adverserial
bandit setting. Note that this family not only contains the multinomial logit
with independent arms but also several models which are able to incorporate
correlation structure such as nested logit, paired combinatorial logit ….
In Müller et al. (2021b) the constant $M$ from Condition (9) is derived for
GNL models, i. e. $M=\frac{1}{\mu}\left(\frac{1}{\displaystyle\min_{\ell\in
L}\mu_{\ell}}-1\right)$. Considering Proposition 3.1 we hence see that
$M=\frac{\tilde{C}}{\mu}$. Furthermore, the constant $C$ which enters the
(expected) regret bound, only depends on the smallest nest parameter. Let us
illustrate the constant $C$ based on the examples from Section 2.1.

######  Remark 1 (Differential-Consistency of MNL and NL).

Recall the MNL model and its generating function from Example 2.1. Note that
in this example we have $\tilde{C}=\left(\frac{1}{\mu}-1\right)$ and therefore
$C=\frac{1}{\mu}$.
For the NL model from Example 2.2 we have
$\tilde{C}=\left(\frac{1}{\displaystyle\min_{\ell\in L}\mu_{\ell}}-1\right)$
and therefore $C=\frac{1}{\displaystyle\min_{\ell\in L}\mu_{\ell}}$.

We can finally state the main result of this Section.

######  Theorem 3.3.

The Algorithm 2 with a surplus function following a Generalized Nested Logit
model is at most

$\eta\cdot E(\mathbf{0})+\frac{n\cdot T}{\displaystyle\min_{\ell\in
L\cdot\eta}\mu_{\ell}}.$

###### Proof.

We apply Lemma 3.1 and conclude that $\tilde{E}(\mathbf{0};\eta)=\eta\cdot
E(\mathbf{0})$. Furthermore, due to Theorem 3.2 the surplus function is
$\frac{1}{\mu}$\- differentiable consistent and thus, its convex perspective
is $\frac{1}{\eta\cdot\displaystyle\min_{\ell\in L}\mu_{\ell}}$\-
differentiable consistent. Together with Inequality (14) this provides an
upper bound of $\frac{n\cdot T}{\displaystyle\min_{\ell\in
L\cdot\eta}\mu_{\ell}}$ for the divergence part, which concludes the
assertion. ∎

GNL models can not only be used to design algorithms for online linear
optimization algorithms but also for adversarial multiarmed bandit problems.
This result enable the learner to design a large amount of computationally
efficient algorithms with vanishing average regret and with sampling
probabilities adjusted to the dependence structure of the arms.

##  4  Numerical Experiments for the Stochastic Multiarmed Bandits

In this section we want to compare the numerical performance of Algorithm 2 in
the stochastic bandit environment with nonnegative rewards. In particular, we
compare Algorithm 2 with a NL surplus function to the MNL suprlus function
which basically coincides with the EXP3-Algorithm. Recall that the proof of
Theorem 3.1 heavily rely on the concept of differential consistency introduced
by Abernethy et al. (2016). Hence, the vanishing average regret is guaranteed
in the loss only setting. Hence, the question arises if instances of Algorithm
2 apart from the EXP3-Algorithm can be applied to scenarios where the rewards
are nonnegative. For that we provide numerical results for a stochastic bandit
setting, which is a collection of distributions, see for example Lattimore and
Szepesvári (2020). The difference to the adversarial bandit setting lies in
the assumption concerning how the sequence of rewards is generated. In the
stochastic setting, after the agent has selected a distribution over the arms
and sampled one arm according to this distribution, the environment samples a
reward from the respective reward-generating distribution. In particular, we
focus on the Bernoulli-Bandit setting meaning there exists a vector $\pi$ with
elements $\pi^{(i)}\in[0,1]$, $i=1,\ldots,n$. The entries of this parameter
vector determine the probability with which the agent could expect to receive
a reward if playing the corresponding arm. Consequently, the reward of the
$i$-th arm $u^{(i)}_{t}$ in each round is either $1$ with probability
$\theta^{(i)}$ or $0$ with probability $1-\theta^{(i)}$. Note that in the
stochastic setting, the performance of the best arm is random. Clearly, a good
strategy for the learner is therefore to follow the arm with the highest
reward generating probability resp. mean. Thus, the learner has to balance
between exploiting the arm with the highest mean so far and exploiting other
arms to possibly find higher means. For our numerical simulations the average
(expected) regret is therefore computed by

$\mathbb{E}\left[\mbox{Regret}_{T}\right]=\max_{1\leq i\leq
n}\pi^{(i)}-\frac{1}{T}\mathbb{E}\left[\sum_{t=1}^{T}u^{(i_{t})}_{t}\right],$
(17)

where the expectation is taken over the randomness in the reward generating
and the sampling distribution. We compare results of the well known
Exp3-Algorithm to the algorithm based on Nested Logit probabilities. For the
comparison an environment of $K$-Bernoulli-arms is initialized with
corresponding parameters $\pi_{k}$, $k=1,\ldots,K$. Then, each algorithm runs
for $T=10000$ iterations, which is repeated $B=100$ times. The parameter
$\eta$ is set to $1$. We equivalently control the exploration-exploitation of
the MNL-Algorithm by the parameter $mu$.
The first environment is summarized in Table 1

Arm $k$ | $\pi_{k}$
---|---
$1$ | $0.2$
$2$ | $0.8$
$3$ | $0.87$
$4$ | $0.15$
Table 1: Environment 1

We run the MNL-Algorithm with $\mu=0.25$.For the NL-Algorithm we put
alternatives $1$ and $3$ in one nest with $\mu_{1}=0.05$ and the two other
arms in the second nest with $\mu_{2}=0.1$. The average (expected) regret is
quickly vanishing for both algorithms, see Figure 1.

Figure 1: Average Expected Regret on Environment 1

In fact, the NL-Algortihms outperforms the MNL-Algorithm on this environment
w.r.t. the average regret. This can also be seen by comparing the total
average reward of the algorithms on the $100$ runs. The NL-Algorithm gains in
average a reward $8337.86$ while the MNL-Algorithm receives $7962.24$ on
average. In terms of exploiting the former thus performs very well. Let us
inspect the exploration structure in Figures 2 and 3.

Figure 2: Learnt Reward Probabilities of Environment $1$ with
$\mu=0.25$,$\mu_{1}=0.05$, $\mu_{2}=0.1$ Figure 3: Played Arms of Environment
$1$

We see that the MNL-Algorithm learns all reward probabilities whereas the NL-
Algorithm neglects Arm $4$, due to the fact that this arm is hardly played.
This indicates a powerful feature of the NL-Algorithm compared to the MNL-
Algortithm. The latter is able to exploit more by adjusting the smoothness
parameter $\mu$, however, the exploration will suffer from this. We run a MNL-
Algorithm with $\mu=0.05$ on the same environment which gains an average
reward of $8413.37$, but only explored the reward probability of Arm $3$. This
means high exploitation but almost no exploration. On the contrary,
readjusting the parameters of the NL-Algorithm to $\mu_{1}=0.15$ and
$\mu_{2}=0.2$ yields an average reward of $8202.71$ while learning the reward
probabilities of all arms, see Figure 4.

Figure 4: Learnt Reward Probabilities of Environment $1$ with
$\mu=0.05,\mu_{1}=0.15,\mu_{2}=0.2$.

Hence, the NL-Algorithm provides the opportunity to attain a better
Exploration/Exploitation Trade-Off by fine-tuning the nest parameters.
Since the MNL model can be viewed as a special case of the NL model, we could
tune the NL-Algorithm in order to reflect the results of the MNL algorithm by
setting the nest parameters very close to $1$. This is displayed in Figures 5
and 6. Non surprisingly the average rewards of the $100$ simulations is almost
the same with $6112.89$ for NL and $6108.29$ for the MNL-Algorithm.

Figure 5: Learnt Reward Probabilities of Environment $1$,
$\mu=1,\mu_{1}=\mu_{2}=0.998$ Figure 6: Played Arms of Environment $1$,
$\mu=1,\mu_{1}=\mu_{2}=0.998$

In order to verify the results from the simulations on Environment $1$ we
compare the algorithms on a larger environment with $13$ Bernoulli arms. The
corresponding mean reward parameter are displayed in Table 2.

Arm $k$ | $\pi_{k}$
---|---
$1$ | $0.2$
$2$ | $0.3$
$3$ | $0.87$
$4$ | $0.15$
$5$ | $0.79$
$6$ | $0.12$
$7$ | $0.85$
$8$ | $0.1$
$9$ | $0.83$
$10$ | $0.75$
$11$ | $0.14$
$12$ | $0.9$
$13$ | $0.2$
Table 2: Environment $2$

Alternatives $1$ to $6$ are in the first nest with corresponding parameter
$\mu_{1}=0.16$. The second nest consists of arms $7$ and $8$ with
$\mu_{2}=0.09$. Nest § with parameter $\mu_{3}=0.21$ includes arms $9$ to
$11$. The last two arms are in the $4$-th nest with $\mu_{4}=0.12$. Again we
compare to a MNL-Algorithm with parameter $\mu=0.25$. The average (expected)
regret as well as the learnt reward probabilities can be seen in Figures 7 and
8.

Figure 7: Average Expected Regret on Environment $2$ Figure 8: Learnt Reward
Probabilities of Environment $2$

Again we see that the NL-Algorithm is exploring most of the arms and at the
same time an average reward of $8360.73$ has been gained compared to an
average reward of $7911.88$.
Our simulations show that the extension of multiarmed bandit algorithms from a
multinomial based algorithm to generalized nested logit algorithm can be of
high practical benefit. Indeed, the higher flexibility in tuning the
parameters of the algorithm provide more possibilities to outbalance the
exploration/exploitation trade-off. In particular, the algorithm could be used
in scenarios, where the learner wants to explore different product categories
and at the same time, wants to avoid exploring weaker products of each
category.

## References

  * Abernethy et al. [2016] Jacob Abernethy, Chansoo Lee, and Ambuj Tewari.  Perturbation techniques in online learning and optimization.  _Perturbations, Optimization, and Statistics_ , 233, 2016.
  * Anderson et al. [1992] S. P. Anderson, A. De Palma, and L.-F. Thisse.  _Discrete choice theory of product differentiation_.  MIT press, 1992.
  * Auer et al. [2002] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire.  The nonstochastic multiarmed bandit problem.  _SIAM journal on computing_ , 32(1):48–77, 2002\.
  * Cesa-Bianchi and Lugosi [2006] Nicolo Cesa-Bianchi and Gábor Lugosi.  _Prediction, learning, and games_.  Cambridge university press, 2006.
  * Lattimore and Szepesvári [2020] Tor Lattimore and Csaba Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * McFadden [1978] D. McFadden.  Modeling the choice of residential location.  _Transportation Research Record_ , (673):72–77, 1978.
  * McFadden et al. [1978] Daniel McFadden et al.  Modelling the choice of residential location.  1978\.
  * Melo [2021] Emerson Melo.  Learning in random utility models via online decision problems.  _arXiv preprint arXiv:2112.10993_ , 2021.
  * Müller et al. [2021a] David Müller, Yurii Nesterov, and Vladimir Shikhman.  Dynamic pricing under nested logit demand.  _Journal of Pure and Applied Functional Analysis_ , 6(6):1435–1451, 2021a.
  * Müller et al. [2021b] David Müller, Yurii Nesterov, and Vladimir Shikhman.  Discrete choice prox-functions on the simplex.  _Mathematics of Operations Research_ , 2021b.  doi: https://doi.org/10.1287/moor.2021.1136.
  * Neu and Bartók [2013] Gergely Neu and Gábor Bartók.  An efficient algorithm for learning with semi-bandit feedback.  In _International Conference on Algorithmic Learning Theory_ , pages 234–248. Springer, 2013.
  * Pemberton and Rau [2015] Malcolm Pemberton and Nicholas Rau.  _Mathematics for economists: an introductory textbook_.  Manchester University Press, 2015.
  * Slivkins et al. [2019] Aleksandrs Slivkins et al.  Introduction to multi-armed bandits.  _Foundations and Trends® in Machine Learning_ , 12(1-2):1–286, 2019.
  * Thurstone [1927] L. Thurstone.  A law of comparative judgment.  _Psychological Review_ , 34(4):273, 1927.
  * Wen and Koppelman [2001] Chieh-Hua Wen and Frank S Koppelman.  The generalized nested logit model.  _Transportation Research Part B: Methodological_ , 35(7):627–641, 2001.