Matthieu Jedor<EMAIL_ADDRESS>
Centre Borelli, ENS Paris-Saclay & Cdiscount and Jonathan Louëdec
<EMAIL_ADDRESS>
Cdiscount and Vianney Perchet<EMAIL_ADDRESS>
CREST, ENSAE Paris & Criteo AI Lab

# Be Greedy in Multi-Armed Bandits

###### Abstract

The Greedy algorithm is the simplest heuristic in sequential decision problem
that carelessly takes the locally optimal choice at each round, disregarding
any advantages of exploring and/or information gathering. Theoretically, it is
known to sometimes have poor performances, for instance even a linear regret
(with respect to the time horizon) in the standard multi-armed bandit problem.
On the other hand, this heuristic performs reasonably well in practice and it
even has sublinear, and even near-optimal, regret bounds in some very specific
linear contextual and Bayesian bandit models.

We build on a recent line of work and investigate bandit settings where the
number of arms is relatively large and where simple greedy algorithms enjoy
highly competitive performance, both in theory and in practice. We first
provide a generic worst-case bound on the regret of the Greedy algorithm. When
combined with some arms subsampling, we prove that it verifies near-optimal
worst-case regret bounds in continuous, infinite and many-armed bandit
problems. Moreover, for shorter time spans, the theoretical relative
suboptimality of Greedy is even reduced.

As a consequence, we subversively claim that for many interesting problems and
associated horizons, the best compromise between theoretical guarantees,
practical performances and computational burden is definitely to follow the
greedy heuristic. We support our claim by many numerical experiments that show
significant improvements compared to the state-of-the-art, even for moderately
long time horizon.

###### keywords:

Multi-armed bandits, greedy algorithm, continuous-armed bandits, infinite-
armed bandits, many-armed bandits

##  1 Introduction

Multi-armed bandits are basic instances of online learning problems with
partial feedback (Bubeck and Cesa-Bianchi, 2012; Lattimore and Szepesvári,
2020; Slivkins, 2019). In the standard stochastic bandit problem, a learning
agent sequentially pulls among a finite set of actions, or “arms”, and
observes a stochastic reward accordingly. The goal of the agent is then to
maximize its cumulative reward, or equivalently, to minimize its regret,
defined as the difference between the cumulative reward of an oracle (that
knows the mean rewards of arms) and the one of the agent. This problem
requires to trade-off between exploitation (leveraging the information
obtained so far) and exploration (gathering information on uncertain arms).

The exploration, although detrimental in the short term, is usually needed in
the worst-case as it ensures that the learning algorithm “converges” to the
optimal arm in the long run. On the other hand, the Greedy algorithm, an
exploration-free strategy, focuses on pure exploitation and pulls the
apparently best arm according to the information gathered thus far, at the
risk of only sampling once the true optimal arm. This typically happens with
Bernoulli rewards where only arms whose first reward is a 1 will be pulled
again (and the others discarded forever). As a consequence, with some non-zero
probability, the regret grows linearly with time as illustrated in the
following example.

######  Example 1.1.

Consider a relatively simple Bernoulli bandit problem consisting of $K=2$ arms
with expected rewards $0.9$ and $0.1$ respectively. With probability at least
0.01, Greedy fails to find the optimal arm. On the other hand, with
probability $0.9^{2}$ it suffers no regret after the initial pulls. This
results in a linear regret with a large variance. This typical behavior is
illustrated in Appendix A.1.

Two solutions have been proposed to overcome this issue. The first one is to
force the exploration; for example with an initial round-robin exploration
phase (Even-Dar et al., 2002), or by spreading the exploration uniformly over
time à la Epsilon-Greedy (Auer et al., 2002). However, both these algorithms
need to know the different parameters of the problem to perform optimally
(either to set the length of the round-robin phase or the value of
$\varepsilon$), which represents a barrier to their use in practice. The
second solution is to have a data-driven and adaptive exploration; for
example, by adding an exploration term à la UCB (Auer et al., 2002), by using
a Bayesian update à la Thompson Sampling (Thompson, 1933; Perrault et al.,
2020a), by using data- and arm-dependent stopping times for exploring à la
Explore-Then-Commit (Perchet and Rigollet, 2013; Perchet et al., 2016) or by
tracking the number of pulls of suboptimal arms (Baransi et al., 2014; Honda
and Takemura, 2010, 2015). With careful tuning, these algorithms are
asymptotically optimal for specific reward distributions. Yet this asymptotic
regime can occur after a long period of time (Garivier et al., 2019) and thus
simpler heuristics might be preferable for relatively short time horizon
(Vermorel and Mohri, 2005; Kuleshov and Precup, 2014).

Conversely, the simple Greedy algorithm has recently been proved to satisfy
near-optimal regret bounds in some linear contextual model (Bastani et al.,
2017; Kannan et al., 2018; Raghavan et al., 2020) and a sublinear regret bound
in some Bayesian many-armed setting (Bayati et al., 2020). In particular, this
was possible because the Greedy algorithm benefits from “free” exploration
when the number of arms is large enough. We illustrate this behavior in the
following example.

######  Example 1.2.

Consider bandit problems where rewards are Gaussian distributions with unit
variance and mean rewards are drawn i.i.d. from a uniform distribution over
$[0,1]$. In Figure 1, we compare the regret of Greedy with the UCB algorithm
for different number of arms and time horizon. For both algorithms, we observe
a clear transition phase between problems with higher average regret (with
darker colors) and problems with lower regret (with lighter colors). In this
example, this transition takes the form of a diagonal.

This diagonal is much lower for Greedy compared to UCB, meaning that Greedy
performs better in the problems in-between, and this in spite of UCB being
optimal in the problem-dependent sense (on the other hand, that is when the
horizon is large, UCB outperforms Greedy). The intuition is that, when the
number of near-optimal arms is large enough, Greedy rapidly converges to one
of them while UCB is still in its initial exploration phase. The key argument
here is the short time horizon relatively to the difficulty of the problem; we
emphasis on the “relatively” as in practice the “turning point”, that is the
time horizon for which UCB performs better, can be extremely large.

Figure 1: Bayesian regret divided by the horizon for UCB (left) and Greedy
(right) as a function of the number of arms and the horizon in Gaussian bandit
problems.

Numerous interesting problems actually lie in the bottom left corner of Figure
1, i.e., bandit problems with a large number of arms and a relatively short
time horizon and, as a consequence, the Greedy algorithm should be considered
as a valid baseline.

#### Our results

We first provide a generic regret bound on Greedy, and we illustrate how to
derive worst-case regret bounds. We will then instantiate this regret bound to
a uniformly sampled subset of arms and prove this satisfies near-optimal
worst-case regret bounds in the continuous-armed, infinite-armed and many-
armed bandit models. As a byproduct of our analysis, we get that the problem
of unknown smoothness parameters can be overcome by a simple discretization
depending only on the time horizon in the first of these models. In all these
settings, we repeat the experiments of previous papers and show that the
Greedy algorithm outmatches the state-of-the-art.

#### Detailed comparison with prior work on Greedy

Greedy recently regained some attention in Bayesian bandit problems with a
large but finite number of arms (Bayati et al., 2020). It performs extremely
well empirically when the number of arms is large, sometimes better than
“optimal” algorithms; in that case, the regret of Greedy is sublinear, though
not optimal. In the following, we get rid of the strong Bayesian assumptions
and we consider many different bandit models, where a subsampling technique is
required and considered in the following.

Another recent success of Greedy is in linear contextual bandit problems, as
it is asymptotically optimal for a two-armed contextual bandit with linear
rewards when a covariate diversity condition holds (Bastani et al., 2017).
This idea can be extended to rewards given by generalized linear models. If
observed contexts are selected by an adversary, but perturbed by white noise,
then Greedy can again have optimal regret guarantees (Kannan et al., 2018).
Additional assumptions can even improved those results (Raghavan et al., 2018,
2020). Those results hold because exploration is not needed thanks to the
diversity in the contexts. We do not believe this assumption is satisfied in
many practical scenarios and we are therefore rather interested in the
implicit exploration of Greedy. As a consequence, we shall no further consider
the contextual framework (even if admittedly, our results could be generated
via careful binning (Perchet and Rigollet, 2013)). Interestingly, an extensive
empirical study of contextual bandit algorithms found that Greedy is actually
the second most efficient algorithm and is extremely close to the first one
(Bietti et al., 2018).

The Greedy algorithm has already been shown to enjoy great empirical
performance in the continuous-armed bandit model (Jedor et al., 2020). In this
paper, we make formal this insight. Finally, we mention that in the one-
dimensional linear bandit problem with a known prior distribution, the
cumulative regret of a greedy algorithm (under additional structural
assumptions) admits an $\mathcal{O}(\sqrt{T})$ upper bound and its Bayes risk
admits an $\mathcal{O}(\log T)$ upper bound (Mersereau et al., 2009). Linear
bandits are only considered empirically in this paper (see Appendix G.1).

#### Related work on bandit models

We also provide a short literature review on the different bandit settings
studied in this paper.

##### Continuous-armed bandits

In the continuous-armed bandit problem with nonparametric regularity
assumptions (Agrawal, 1995), lower and upper bounds are matching up to sub-
logarithmic factors (Kleinberg, 2005). Additional structural assumptions can
be considered to lower regret, such as margin condition (Auer et al., 2007),
Lipschitz (w.r.t. some fixed metric) mean-payoff function (Kleinberg et al.,
2008), local Lipschitzness (w.r.t. some dissimilarity function) (Bubeck et
al., 2010). Adaptivity to smoothness parameters is also a crucial task (Bubeck
et al., 2011; Locatelli and Carpentier, 2018; Hadiji, 2019).

##### Infinite-armed bandits

The original infinite-armed bandit problem (Berry et al., 1997) consists in a
sequence of $n$ choices from an infinite number of Bernoulli arms, with
$n\rightarrow\infty$. The objective was to minimize the long-run failure rate.
The Bernoulli parameters are independent observations from a known
distribution. With a uniform prior distribution, it is possible to control the
cumulative regret (Bonald and Proutiere, 2013). A more general model has been
considered (Wang et al., 2009). In particular, rewards are usually assumed to
be uniformly bounded in $[0,1]$ and the mean reward of a randomly drawn arm is
$\varepsilon$-optimal with probability
$\mathcal{O}\left(\varepsilon^{\beta}\right)$ for some $\beta>0$.

##### Many-armed bandits

Models in many-armed bandit problems are more varied, but the main idea is
that the number of arms is large comparatively to the number of rounds
(Teytaud et al., 2007). The exploration can be enhanced with a focus on a
small subset of arms (using a cross-entropy based algorithm without
theoretical guarantees thought) (Wang et al., 2017). The definition of regret
can also be altered; by considering a given quantile fraction of the
probability distribution over the mean rewards of arms (Chaudhuri and
Kalyanakrishnan, 2018) or with respect to a “satisfing” action (the definition
of a satisficing action is set by the learner) (Russo and Van Roy, 2018). Mean
rewards can also be formulate with a semi-parametric model (Ou et al., 2019).
A setting with multiple best/near-optimal arms without any assumptions about
the structure of the bandit instance has also been considered (Zhu and Nowak,
2020). The objective there is to design algorithms that can automatically
adapt to the unknown hardness of the problem.

##  2 Preliminaries

In the stochastic multi-armed bandit model, a learning agent interacts
sequentially with a finite set of $K$ distributions
$\mathcal{V}_{1},\dots,\mathcal{V}_{K}$, called arms. At round
$t\in\mathds{N}$, the agent chooses an arm $A_{t}$, which yields a stochastic
reward $X_{t}$ drawn from the associated probability distribution
$\mathcal{V}_{A_{t}}$. The objective is to design a sequential strategy
maximizing the expected cumulative reward up to some time horizon $T$. Let
$\mu_{1},\dots,\mu_{K}$ denote the mean rewards of arms, and
$\mu^{\star}\coloneqq\max_{k\in[K]}\mu_{k}$ be the best mean reward. The goal
is equivalent to minimizing the regret, defined as the difference between the
expected reward accumulated by the oracle strategy always playing the best arm
at each round, and the one accumulated by the strategy of the agent,

$R_{T}=\mathbb{E}\left[\sum_{t=1}^{T}\left(\mu^{\star}-X_{t}\right)\right]=T\mu^{\star}-\mathbb{E}\left[\sum_{t=1}^{T}\mu_{A_{t}}\right]$

where the expectation is taken with respect to the randomness in the sequence
of successive rewards from each arm and the possible randomization in the
strategy of the agent. Let $N_{k}(T)$ be the number of pulls of arm $k$ at the
end of round $T$ and define the suboptimality gap of an arm
$k\in[K]\coloneqq\\{1,\ldots,K\\}$ as $\Delta_{k}=\mu^{\star}-\mu_{k}$. The
expected regret is equivalently written as

$R_{T}=\sum_{k=1}^{K}\Delta_{k}\mathbb{E}\left[N_{k}(T)\right]\,.$

[H] Set of $K$ arms

$t\leftarrow 1$ $T$ Pull arm $\displaystyle
A_{t}\in\operatorname*{argmax}_{k\in[K]}\widehat{\mu}_{k}(t-1)$

Figure 2: Greedy

#### The Greedy algorithm

Summarized in Algorithm 2, Greedy is probably the simplest and the most
obvious algorithm. Given a set of $K$ arms, at each round $t$, it pulls the
arm with the highest average reward
$\displaystyle\widehat{\mu}_{k}(t-1)=\frac{1}{N_{k}(t-1)}\sum_{s=1}^{t-1}X_{s}\mathbf{1}\left\\{A_{s}=k\right\\}$111With
the convention that $0/0=\infty$, so that the first $K$ pulls initialize each
counter.. Thus, it constantly exploits the best empirical arm.

In the rest of the paper, we assume that the stochastic reward $X_{t}$ takes
the form $X_{t}=\mu_{A_{t}}+\eta_{t}$ where $\\{\eta_{t}\\}_{t=1}^{T}$ are
i.i.d. 1-subgaussian white noise and that $\mu_{k}$ are bounded for all
$k\in[K]$, $\mu_{k}\in[0,1]$ without loss of generality. We further assume the
knowledge of the time horizon $T$, unknown time horizon can be handled as
usual in bandit problems (Besson and Kaufmann, 2018). Finally, we say that arm
$k$ is $\varepsilon$-optimal for some $\varepsilon>0$ if
$\mu_{k}\geq\mu^{\star}-\varepsilon$.

##  3 Generic bound on Greedy

We now present the generic worst-case regret bound on Greedy that we will use
to derive near-optimal bounds in several bandit models. The proof is provided
in Appendix B.1.

######  Theorem 3.1.

The regret of Greedy verifies for all $\varepsilon>0$

$R_{T}\leq
T\exp\left(-N_{\varepsilon}\frac{\varepsilon^{2}}{2}\right)+3\varepsilon
T+\frac{6K}{\varepsilon}+\sum_{k=1}^{K}\Delta_{k}$

where $N_{\varepsilon}$ denotes the number of $\varepsilon$-optimal arms.

######  Remark 3.2.

This bound generalizes a Bayesian analysis (Bayati et al., 2020). It is
slightly looser; indeed the Bayesian assumption can be used to bound
$N_{\varepsilon}$ and further improve the third term by bounding the number of
suboptimal arms. Those techniques usually do not work in the stochastic
setting.

It is easy to see that this bound is meaningless when $N_{\varepsilon}$ is
independent of $T$ as one of the first two terms will, at least, be linear
with respect to $T$. On the other hand, $N_{\varepsilon}$ has no reason to
depend on the time horizon. The trick to obtain sublinear regret will be to
lower bound $N_{\varepsilon}$ by a function of the number of arms $K$, then to
optimize $K$ with respect to the time horizon $T$. To motivate this, consider
the following example.

######  Example 3.3.

Consider a problem with a huge number of arms $n$ with mean rewards drawn
i.i.d. from a uniform distribution over $[0,1]$. In that specific case, we
roughly have $N_{\varepsilon}\approx\varepsilon K$ for some subset of arms,
chosen uniformly at random, with cardinality $K$. Taking
$\varepsilon=\left(\frac{\log T}{K}\right)^{1/3}$, so that the first term in
the generic bound is sublinear, yields a
$\mathcal{O}\left(\max\left\\{T\left(\frac{\log
T}{K}\right)^{1/3},K\left(\frac{K}{\log T}\right)^{1/3}\right\\}\right)$
regret bound, which comes from the second and third terms respectively. If we
sub-sampled $K=T^{3/5}\left(\log T\right)^{2/5}$ arms, so that the maximum is
minimized, the regret bound becomes $\mathcal{O}\left(T^{4/5}\left(\log
T\right)^{1/5}\right)$; in particular it is sublinear.

This argument motivates this paper and will be made formal in subsequent
sections. Though this does not lead to optimal bounds – as expected by the
essence of the greedy heuristic in the multi-armed bandit model –, it will
nonetheless be highly competitive for short time span in many practical bandit
problems.

It is possible to theoretically improve the previous result by using a
chaining/peeling type of argument. Unfortunately, it is not practical to
derive better explicit guarantees as it involves an integral without close
form expressions; its proof is postponed to Appendix B.2.

######  Corollary 3.4.

The regret of Greedy verifies

$R_{T}\leq\min_{\varepsilon}\Big{\\{}3\varepsilon
T+\frac{6K}{\varepsilon}+\int_{\varepsilon}^{1}\left(3T+\frac{6K}{x^{2}}\right)\exp\left(-N_{x}\frac{x^{2}}{2}\right)dx\Big{\\}}+T\exp\left(-\frac{K}{2}\right)+\sum_{k=1}^{K}\Delta_{k}\,.$

##  4 Continuous-armed bandits

We first study Greedy in the continuous-armed bandit problem. We recall that
in this model, the number of actions is infinitely large. Formally, let
$\mathcal{A}$ be an arbitrary set and $\mathcal{F}$ a set of functions from
$\mathcal{A}\rightarrow\mathbb{R}$. The learner is given access to the action
set $\mathcal{A}$ and function class $\mathcal{F}$. In each round $t$, the
learner chooses an action $A_{t}\in\mathcal{A}$ and receives reward
$X_{t}=f(A_{t})+\eta_{t}$, where $\eta_{t}$ is some noise and
$f\in\mathcal{F}$ is fixed, but unknown. As usual in the literature
(Kleinberg, 2005; Auer et al., 2007; Hadiji, 2019), we restrict ourselves to
the case $\mathcal{A}=[0,1]$, $\eta_{t}$ is 1-subgaussian, $f$ takes values in
$[0,1]$ and $\mathcal{F}$ is the set of all functions that satisfy an Hölder
condition around the maxima. Formally,

###### Assumption 4.1

There exist constants $L\geq 0$ and $\alpha>0$ such that for all $x\in[0,1]$,

$f(x^{\star})-f(x)\leq L\cdot|x^{\star}-x|^{\alpha}$

where $x^{\star}$ denotes the optimal arm.

This assumption captures the degree of continuity at the maxima and it is
needed to ensure that this maxima is not reached at a sharp peak.

Similarly to CAB1 (Kleinberg, 2005), the Greedy algorithm will work on a
discretization of the action set into a finite set of $K$ equally spaced
points $\\{1/K,2/K,\dots,1\\}$. Each point is then considered as an arm and we
can apply the standard version of Greedy on them.

######  Remark 4.2.

The same analysis holds if it chooses a point uniformly at random from the
chosen interval $\left[\frac{k-1}{K},\frac{k}{K}\right]$ for $1\leq k\leq K$,
see also Auer et al. (2007).

The problem is thus to set the number of points $K$. The first regret bound on
the Greedy algorithm assumes that the smoothness parameters are known. The
proof is provided in Appendix C.

######  Theorem 4.3.

If $f:[0,1]\rightarrow[0,1]$ satisfies Assumption 4.1, then for all
$\varepsilon>0$ and a discretization of
$K\geq\left(\frac{L}{\varepsilon}\right)^{1/\alpha}$ arms, the regret of
Greedy verifies

$R_{T}\leq
T\exp\left(-\frac{K}{2L^{1/\alpha}}\varepsilon^{2+1/\alpha}\right)+4\varepsilon
T+\frac{6K}{\varepsilon}+K\,.$

In particular, the choice

$K=\left(32/27\right)^{\alpha/(4\alpha+1)}L^{2/(4\alpha+1)}T^{(2\alpha+1)/(4\alpha+1)}\left(\log
T\right)^{2\alpha/(4\alpha+1)}$

yields for $L\leq\sqrt{\frac{3}{2T}}K^{\alpha+1/2}$,

$R_{T}\leq 13L^{2/(4\alpha+1)}T^{(3\alpha+1)/(4\alpha+1)}\left(\log
T\right)^{2\alpha/(4\alpha+1)}+1\,.$

This bound is sublinear with respect to the time horizon $T$, yet suboptimal.
Indeed, the lower bound in this setting is
$\Omega\left(T^{(\alpha+1)/(2\alpha+1)}\right)$ and the MOSS algorithm run on
a optimal discretization attains it since its regret scales, up to constant
factor, as
$\mathcal{O}\left(L^{1/(2\alpha+1)}T^{(\alpha+1)/(2\alpha+1)}\right)$ (Hadiji,
2019). Yet, as mentioned previously, Greedy is theoretically competitive for
short time horizon due to small constant factors. In Figure 3, we displayed
regret upper bounds of MOSS and Greedy as a function of time for functions
that satisfy Assumption 4.1 with smoothness parameters $L=1$ and $\alpha=1$.
We see that the bound on Greedy is stronger up until a moderate time horizon
$T\approx 12000$.

Of course, assuming that the learner knows smoothness parameters $\alpha$ and
$L$ is often unrealistic. If we want to ensure a low regret on very regular
functions, by taking $\alpha\rightarrow\infty$, we have the following
corollary.

######  Corollary 4.4.

If $f:[0,1]\rightarrow[0,1]$ satisfies Assumption 4.1, then for a
discretization of $K=\sqrt{\frac{4}{3}T\log T}$ arms, the regret of the Greedy
algorithm verifies for $L\leq
3^{1/4}\left(4/3\right)^{(2\alpha+1)/4}T^{2\alpha}\left(\log
T\right)^{(\alpha+1)/2}$,

$R_{T}\leq
15\max\\{L^{1/(2\alpha+1)},L^{-1/(2\alpha+1)}\\}T^{(3\alpha+2)/(4\alpha+2)}\sqrt{\log
T}+1\,.$

######  Proof 4.5.

It is a direct consequence of Theorem 4.3 with the choice of
$\varepsilon=\left(L^{1/\alpha}\sqrt{\frac{3\log
T}{T}}\right)^{\alpha/(2\alpha+1)}$.

Once again, Greedy attains a sublinear, yet suboptimal, regret bound. In the
case of unknown smoothness parameters, the regret lower bound is
$\Omega\left(L^{1/(1+\alpha)}T^{(\alpha+2)/(2\alpha+2)}\right)$ (Locatelli and
Carpentier, 2018), which is attained by MeDZO with a
$\mathcal{O}\left(L^{1/(\alpha+1)}T^{(\alpha+2)/(2\alpha+2)}\left(\log_{2}T\right)^{3/2}\right)$
regret bound (Hadiji, 2019). This time, Greedy also has a lower polynomial
dependency which makes it even more competitive theoretically. In Figure 3, we
displayed regret upper bounds of MeDZO and Greedy (with unknown smoothness
parameters) as a function of time for functions that satisfy Assumption 4.1
with smoothness parameters $L=1$ and $\alpha=1$. Here we cannot see the
turning point since Greedy is stronger up until an extremely large time
horizon $T\approx 1,9\cdot 10^{46}$. Our numerical simulations will further
support this theoretical advantage.

fig:bounds_continuous [Known smoothness][Unknown smoothness]

Figure 3: Regret upper bound of various algorithms as a function of time in
the continuous-armed bandit model with smothness parameters $L=1$ and
$\alpha=1$.

##  5 Infinite-armed bandits

We now study the infinite-armed bandit problem. In this setting, we consider
the general model of Wang et al. (2009). In particular they assume a margin
condition on the mean reward of a randomly drawn arm. Formally,

###### Assumption 5.1

There exist $\mu^{\star}\in(0,1]$ and $\beta>0$ such that the mean reward
$\mu$ of a randomly drawn arm satisfies

$\mathbb{P}\left(\mu>\mu^{\star}-\varepsilon\right)=\mathcal{O}\left(\varepsilon^{\beta}\right)\text{,
for }\varepsilon\rightarrow 0\,.$

Equivalently, there exist $c_{1}>0$ and $c_{2}>0$ such that

$c_{1}\varepsilon^{\beta}\leq\mathbb{P}\left(\mu>\mu^{\star}-\varepsilon\right)\leq
c_{2}\varepsilon^{\beta}\,.$

Similarly to UCB-F (Wang et al., 2009), Greedy will consist of randomly
choosing $K$ arms at first and then running Greedy on those arms. The problem
is then to choose the optimal number of arms $K$. The following bound on
Greedy assumes the knowledge of the parameter $\beta$ and $c_{1}$. Its proof
is deferred in Appendix D.

######  Theorem 5.2.

Assume Assumption 5.1 of the model. The regret of Greedy verifies for any
subsampling of $K>0$ arms and for all $\varepsilon>0$

$R_{T}\leq
T\left[\exp\left(-\frac{c_{1}}{4}K\varepsilon^{2+\beta}\right)+\exp\left(-\frac{c_{1}}{8}K\varepsilon^{\beta}\right)\right]+4\varepsilon
T+\frac{6K}{\varepsilon}+K\,.$

In particular, the choice

$K=\left(2/3\right)^{(2+\beta)/(4+\beta)}\left(\frac{8}{c_{1}(4+\beta)}\right)^{2/(4+\beta)}T^{(2+\beta)/(4+\beta)}\left(\log
T\right)^{2/(4+\beta)}$

yields

$R_{T}\leq
20\left(c_{1}(4+\beta)\right)^{-2/(4+\beta)}T^{(3+\beta)/(4+\beta)}\left(\log
T\right)^{2/(4+\beta)}\,.$

In comparison, the lower bound is this model is
$\Omega\left(T^{\beta/(1+\beta)}\right)$ for any $\beta>0$ and
$\mu^{\star}\leq 1$ and UCB-F obtained a
$\mathcal{O}\left(T^{\beta/(\beta+1)}\log T\right)$ regret bound in the case
$\mu^{\star}=1$ or $\beta>1$ and a
$\widetilde{\mathcal{O}}\left(T^{1/2}\right)$ bound otherwise (Wang et al.,
2009). The regret of Greedy is once again sublinear, though suboptimal, with a
lower logarithmic dependency. Our numerical simulations will further emphasis
its competitive performance.

The case of unknown parameters is more complicated to handle compared to the
continuous-armed model and is furthermore not the main focus of this paper. A
solution proposed by Carpentier and Valko (2015) nonetheless, is to perform an
initial phase to estimate the parameter $\beta$.

##  6 Many-armed bandits

We now consider the particular model of many-armed bandit problem of Zhu and
Nowak (2020). It is somehow related to the previous two except it also takes
into account the time horizon. In particular, it focuses on the case where
multiple best arms are present. Formally, let $T$ be the time horizon, $n$ be
the total number of arms and $m$ be the number of best arms. We emphasis that
$n$ can be arbitrary large and $m$ is usually unknown. The following
assumption will lower bound the number of best arms.

###### Assumption 6.1

There exists $\gamma\in[0,1]$ such that the number of best arms satisfies

$\frac{n}{m}\leq T^{\gamma}\,.$

We assume that the value $\gamma$ (or at least some upper-bound) is known in
our case, even though adaptivity to it is possible (Zhu and Nowak, 2020). The
following Theorem bounds the regret of a Greedy algorithm that initially
subsamples a set of arms. Its proof is provided in Appendix E.

######  Theorem 6.2.

Assume Assumption 6.1 of the model and that the number of arms $n$ is large
enough for the following subsampling schemes to be possible. Depending on the
value of $\gamma$ and the time horizon $T$, it holds:

  * •

If $T^{1-3\gamma}\leq\log T$, in particular for $\gamma\geq\frac{1}{3}$ and
$T\geq 2$, choosing $K=2T^{2\gamma}\log T$ leads to

$R_{T}\leq 14T^{\gamma+1/2}\log T+2\,.$

  * •

Otherwise, the choice of $K=2\sqrt{T^{1+\gamma}\log T}$ yields

$R_{T}\leq 14T^{(3+\gamma)/4}\sqrt{\log T}+2\,.$

The previous bounds indicate that Greedy realizes a sublinear worst-case
regret on the standard multi-armed bandit problem at the condition that the
number of arms is large and the proportion of near-optimal arms is high
enough. To compare, the MOSS algorithm run on an optimal subsampling achieves
a $\mathcal{O}\left(T^{(1+\gamma)/2}\log T\right)$ regret bound for all
$\gamma\in[0,1]$, which is optimal up to logarithmic factors (Zhu and Nowak,
2020). In this case, our numerical simulation will show that Greedy is
competitive even when the setup is close to the limit of the theoretical
guarantee of Greedy.

##  7 Experiments

We now evaluate Greedy in the previously studied bandit models to highlight
its practical competitive performance. For fairness reasons with respect to
the other algorithms, and in the idea of reproducibility, we will not create
new experiment setups but reproduce experiments that can be found in the
literature (and compare the performances of Greedy w.r.t. state of the art
algorithms).

###  7.1 Continuous-armed bandits

In the continuous-armed bandit setting, we repeat the experiments of Hadiji
(2019). We consider three functions that are gradually sharper at the maxima
and thus technically harder to optimize:

$\displaystyle f_{1}:x$ $\displaystyle\mapsto 0.5\sin(13x)\sin(27x)+0.5$
$\displaystyle f_{2}:x$
$\displaystyle\mapsto\max\left(3.6x(1-x),1-|x-0.05|/0.05\right)$
$\displaystyle f_{3}:x$ $\displaystyle\mapsto
x(1-x)\left(4-\sqrt{|\sin{60x}|}\right)$

These functions verify Assumption 4.1 with $\alpha=2,1,0.5$ and $L\approx
221,20,2$, respectively, and are plotted for convenience in Appendix A.2.
Noises are drawn i.i.d. from a standard Gaussian distribution and we consider
a time horizon $T=100000$. We compare the Greedy algorithm with MeDZO (Hadiji,
2019), CAB1 (Kleinberg, 2005) with MOSS (Audibert and Bubeck, 2009; Degenne
and Perchet, 2016b) as the underlying algorithm and Zooming (Kleinberg et al.,
2008). For Greedy, we use the discretization of Corollary 4.4 while for
CAB.MOSS we choose the optimal discretization $K=\left\lceil
L^{2/(2\alpha+1)}T^{1/(2\alpha+1)}\right\rceil$. For MeDZO, we choose the
parameter suggested by authors $B=\sqrt{T}$. We emphasis here that CAB.MOSS
and Zooming require the smoothness parameters contrary to MeDZO and Greedy.
Results are averaged over $1000$ iterations and are presented on Figure
LABEL:fig:exp_continuous. Shaded area represents 5 standard deviation for each
algorithm.

fig:exp_continuous [$f_{1}$][$f_{2}$] [$f_{3}$]

Figure 4: Regret of various algorithms as a function of time in continuous-
armed bandit problems.

We see that Greedy outperforms the other algorithms in all scenarios. We can
clearly observe that the slope of the cumulative regret of Greedy is stepper
than the one of CAB.MOSS, yet it manages to obtain a lower regret by quickly
concentrating on near-optimal arms. Moreover, the difference is striking for
the relatively large time horizon considered here. Interestingly, the slope of
Greedy is more pronounced in the second scenario; this may be due to the low
number of local maxima which negatively affects the number of
$\varepsilon$-optimal arms for Greedy.

###  7.2 Infinite-armed bandits

In the infinite-armed bandit setting, we repeat the experiments of Bonald and
Proutiere (2013). We consider two Bernoulli bandit problems with a time
horizon $T=10000$. In the first scenario, mean rewards are drawn i.i.d. from
the uniform distribution over $[0,1]$, while in the second scenario, they are
drawn from a Beta(1, 2) distribution. We assume the knowledge of the
parameters. We compare Greedy with UCB-F (Wang et al., 2009), a
straightforward extension of MeDZO (analyzed by Zhu and Nowak (2020) in this
model) and TwoTarget (Bonald and Proutiere, 2013) that further assumes
Bernoulli rewards and the knowledge of the underlying distribution of mean
rewards. For Greedy, we use the subsampling suggested in Theorem 5.2. Results,
averaged over 1000 iterations, are displayed on Figure LABEL:fig:exp_infinite
and the shaded area represents 0.5 standard deviation for each algorithm.

fig:exp_infinite [Uniform prior][Beta(1, 2) prior]

Figure 5: Regret of various algorithms as a function of time in infinite-armed
bandit problems.

Once again, we see the excellent empirical performances of Greedy. It is
actually outperformed by TwoTarget in the uniform case since the latter has
been specifically optimize for that case (and is asymptotically optimal) but
Greedy is more robust as the second scenario points out; furthermore,
TwoTarget works only for Bernoulli rewards contrary to Greedy.

###  7.3 Many-armed bandits

In the many-armed bandit setting, we repeat the experiment of Zhu and Nowak
(2020). We consider a Bernoulli bandit problem where best arms have an mean
reward of $0.9$ while for suboptimal arms they are evenly distributed among
$\\{0.1,0.2,0.3,0.4,0.5\\}$. The time horizon is $T=5000$ and the total number
of arms $n=2000$. We set the hardness level at $\gamma=0.4$ resulting in a
number of best arms $m=\left\lceil\frac{n}{T^{\gamma}}\right\rceil=64$. In
this setup, Greedy is near its limit in terms of theoretical guarantee. We
compare OracleGreedy, the greedy algorithm run on an subsampling of arms
analyzed previously, with MOSS (Audibert and Bubeck, 2009), OracleMOSS (Zhu
and Nowak, 2020) (which consider an optimal subsampling for MOSS), MeDZO
(Hadiji, 2019; Zhu and Nowak, 2020) and the standard Greedy algorithm that
consider all arms. For OracleGreedy, we consider a subsampling of
$K=(1-2\gamma)T^{2\gamma}\log T/4$ arms, which corresponds to the value of a
more careful analysis of the regret in the bad events in Theorem 6.2 for
1/4-subgaussian random variables. Results are averaged over 5000 iterations
and displayed on Figure 6. Shaded area represents 0.5 standard deviation for
each algorithm.

Figure 6: Regret of various algorithms on a many-armed bandit problem with
hardness $\gamma=0.4$.

Once again we observe the excellent performance of Greedy on a subsampling of
arms; it outperforms OracleMOSS, its closest competitor, since both assume the
knowledge of the hardness parameter $\gamma$ and subsample. It is also
interesting to notice that the variance of OracleGreedy is much smaller than
OracleMOSS.

##  8 Conclusion

In this paper, we have refined the standard version of Greedy by considering a
subsampling of arms and proved sublinear worst-case regret bounds in several
bandit models. We also carried out an extensive experimental evaluation which
reveals that it outperforms the state-of-the-art for relatively short time
horizon. Besides, since its indexes are usually computed by most algorithms,
it is trivial to implement and fast to run. Consequently, the Greedy algorithm
should be considered as a standard baseline when multiple near-optimal arms
are present, which is the case in many models as we saw.

#### Interesting Direction

We leave open the question of adaptivity. Adaptivity here could refer to
adaptive subsampling or adaptivity to unknown parameters. In particular in the
continuous-armed bandit problem, previous work showed that the learner pays a
polynomial cost to adapt (Hadiji, 2019). Knowing that Greedy works best for
relatively short time horizon, it might be interesting to study this cost for
a greedy strategy and for what time horizon it might be worth it.

Another interesting, and relevant in practical problems, direction is to
analyze the performance of Greedy in combinatorial bandits (with a large
number of arms and thus a non-tractable number of actions), but with some
structure on the rewards on arms (Degenne and Perchet, 2016a; Perrault et al.,
2019, 2020b).

The research presented was supported by the French National Research Agency,
under the project BOLD (ANR19-CE23-0026-04) and it was also supported in part
by a public grant as part of the Investissement d’avenir project, reference
ANR-11-LABX-0056-LMH, LabEx LMH, in a joint call with Gaspard Monge Program
for optimization, operations research and their interactions with data
sciences.

## References

  * Abbasi-Yadkori et al. (2011) Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  In _Advances in Neural Information Processing Systems_ , pages 2312–2320, 2011.
  * Agrawal (1995) Rajeev Agrawal.  The continuum-armed bandit problem.  _SIAM journal on control and optimization_ , 33(6):1926–1951, 1995.
  * Agrawal and Goyal (2012) Shipra Agrawal and Navin Goyal.  Analysis of thompson sampling for the multi-armed bandit problem.  In _Conference on learning theory_ , pages 39–1, 2012.
  * Audibert and Bubeck (2009) Jean-Yves Audibert and Sébastien Bubeck.  Minimax policies for adversarial and stochastic bandits.  2009\.
  * Auer et al. (2002) Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  _Machine learning_ , 47(2-3):235–256, 2002.
  * Auer et al. (2007) Peter Auer, Ronald Ortner, and Csaba Szepesvári.  Improved rates for the stochastic continuum-armed bandit problem.  In _International Conference on Computational Learning Theory_ , pages 454–468. Springer, 2007.
  * Baransi et al. (2014) Akram Baransi, Odalric-Ambrym Maillard, and Shie Mannor.  Sub-sampling for multi-armed bandits.  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , pages 115–131. Springer, 2014.
  * Bastani et al. (2017) Hamsa Bastani, Mohsen Bayati, and Khashayar Khosravi.  Mostly exploration-free algorithms for contextual bandits.  _arXiv preprint arXiv:1704.09011_ , 2017.
  * Bayati et al. (2020) Mohsen Bayati, Nima Hamidi, Ramesh Johari, and Khashayar Khosravi.  Unreasonable effectiveness of greedy algorithms in multi-armed bandit with many arms.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Berry et al. (1997) Donald A Berry, Robert W Chen, Alan Zame, David C Heath, and Larry A Shepp.  Bandit problems with infinitely many arms.  _The Annals of Statistics_ , pages 2103–2116, 1997.
  * Besson and Kaufmann (2018) Lilian Besson and Emilie Kaufmann.  What doubling tricks can and can’t do for multi-armed bandits.  _arXiv preprint arXiv:1803.06971_ , 2018.
  * Bietti et al. (2018) Alberto Bietti, Alekh Agarwal, and John Langford.  A contextual bandit bake-off.  _arXiv preprint arXiv:1802.04064_ , 2018.
  * Bonald and Proutiere (2013) Thomas Bonald and Alexandre Proutiere.  Two-target algorithms for infinite-armed bandits with bernoulli rewards.  In _Advances in Neural Information Processing Systems_ , pages 2184–2192, 2013.
  * Bubeck and Cesa-Bianchi (2012) Sébastien Bubeck and Nicolo Cesa-Bianchi.  Regret analysis of stochastic and nonstochastic multi-armed bandit problems.  _arXiv preprint arXiv:1204.5721_ , 2012.
  * Bubeck et al. (2010) Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvari.  X-armed bandits.  _arXiv preprint arXiv:1001.4475_ , 2010.
  * Bubeck et al. (2011) Sébastien Bubeck, Gilles Stoltz, and Jia Yuan Yu.  Lipschitz bandits without the lipschitz constant.  In _International Conference on Algorithmic Learning Theory_ , pages 144–158. Springer, 2011.
  * Carpentier and Valko (2015) Alexandra Carpentier and Michal Valko.  Simple regret for infinitely many armed bandits.  In _International Conference on Machine Learning_ , pages 1133–1141, 2015.
  * Chakrabarti et al. (2009) Deepayan Chakrabarti, Ravi Kumar, Filip Radlinski, and Eli Upfal.  Mortal multi-armed bandits.  In _Advances in neural information processing systems_ , pages 273–280, 2009.
  * Chaudhuri and Kalyanakrishnan (2018) Arghya Roy Chaudhuri and Shivaram Kalyanakrishnan.  Quantile-regret minimisation in infinitely many-armed bandits.  In _UAI_ , pages 425–434, 2018.
  * Cheung et al. (2019) Wang Chi Cheung, Vincent Tan, and Zixin Zhong.  A thompson sampling algorithm for cascading bandits.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 438–447, 2019.
  * Degenne and Perchet (2016a) Rémy Degenne and Vianney Perchet.  Combinatorial semi-bandit with known covariance.  In _Advances in Neural Information Processing Systems_ , pages 2972–2980, 2016a.
  * Degenne and Perchet (2016b) Rémy Degenne and Vianney Perchet.  Anytime optimal algorithms in stochastic multi-armed bandits.  In Maria Florina Balcan and Kilian Q. Weinberger, editors, _Proceedings of The 33rd International Conference on Machine Learning_ , volume 48 of _Proceedings of Machine Learning Research_ , pages 1587–1595, New York, New York, USA, 20–22 Jun 2016b. PMLR.  URL http://proceedings.mlr.press/v48/degenne16.html.
  * Deshpande and Montanari (2012) Yash Deshpande and Andrea Montanari.  Linear bandits in high dimension and recommendation systems.  In _2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_ , pages 1750–1754. IEEE, 2012.
  * Even-Dar et al. (2002) Eyal Even-Dar, Shie Mannor, and Yishay Mansour.  Pac bounds for multi-armed bandit and markov decision processes.  In _International Conference on Computational Learning Theory_ , pages 255–270. Springer, 2002.
  * Garivier et al. (2019) Aurélien Garivier, Pierre Ménard, and Gilles Stoltz.  Explore first, exploit next: The true shape of regret in bandit problems.  _Mathematics of Operations Research_ , 44(2):377–399, 2019.
  * Hadiji (2019) Hédi Hadiji.  Polynomial cost of adaptation for x-armed bandits.  In _Advances in Neural Information Processing Systems_ , pages 1029–1038, 2019.
  * Honda and Takemura (2010) Junya Honda and Akimichi Takemura.  An asymptotically optimal bandit algorithm for bounded support models.  In _COLT_ , pages 67–79. Citeseer, 2010.
  * Honda and Takemura (2015) Junya Honda and Akimichi Takemura.  Non-asymptotic analysis of a new bandit algorithm for semi-bounded rewards.  _The Journal of Machine Learning Research_ , 16(1):3721–3756, 2015.
  * Jedor et al. (2020) Matthieu Jedor, Jonathan Louëdec, and Vianney Perchet.  Lifelong learning in multi-armed bandits.  _arXiv preprint arXiv:2012.14264_ , 2020.
  * Kannan et al. (2018) Sampath Kannan, Jamie H Morgenstern, Aaron Roth, Bo Waggoner, and Zhiwei Steven Wu.  A smoothed analysis of the greedy algorithm for the linear contextual bandit problem.  In _Advances in Neural Information Processing Systems_ , pages 2227–2236, 2018.
  * Kleinberg et al. (2008) Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal.  Multi-armed bandits in metric spaces.  In _Proceedings of the fortieth annual ACM symposium on Theory of computing_ , pages 681–690, 2008.
  * Kleinberg (2005) Robert D Kleinberg.  Nearly tight bounds for the continuum-armed bandit problem.  In _Advances in Neural Information Processing Systems_ , pages 697–704, 2005.
  * Kuleshov and Precup (2014) Volodymyr Kuleshov and Doina Precup.  Algorithms for multi-armed bandit problems.  _arXiv preprint arXiv:1402.6028_ , 2014.
  * Kveton et al. (2015) Branislav Kveton, Csaba Szepesvari, Zheng Wen, and Azin Ashkan.  Cascading bandits: Learning to rank in the cascade model.  In _International Conference on Machine Learning_ , pages 767–776, 2015.
  * Lattimore and Szepesvári (2020) Tor Lattimore and Csaba Szepesvári.  _Bandit algorithms_.  Cambridge University Press, 2020.
  * Locatelli and Carpentier (2018) Andrea Locatelli and Alexandra Carpentier.  Adaptivity to smoothness in x-armed bandits.  In _Conference on Learning Theory_ , pages 1463–1492, 2018.
  * Mersereau et al. (2009) Adam J Mersereau, Paat Rusmevichientong, and John N Tsitsiklis.  A structured multiarmed bandit problem and the greedy policy.  _IEEE Transactions on Automatic Control_ , 54(12):2787–2802, 2009.
  * Ou et al. (2019) Mingdong Ou, Nan Li, Cheng Yang, Shenghuo Zhu, and Rong Jin.  Semi-parametric sampling for stochastic bandits with many arms.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 7933–7940, 2019.
  * Perchet and Rigollet (2013) Vianney Perchet and Philippe Rigollet.  The multi-armed bandit problem with covariates.  _Ann. Statist._ , 41(2):693–721, 04 2013.  10.1214/13-AOS1101.  URL https://doi.org/10.1214/13-AOS1101.
  * Perchet et al. (2016) Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg.  Batched bandit problems.  _Ann. Statist._ , 44(2):660–681, 04 2016.  10.1214/15-AOS1381.  URL https://doi.org/10.1214/15-AOS1381.
  * Perrault et al. (2019) Pierre Perrault, Vianney Perchet, and Michal Valko.  Exploiting structure of uncertainty for efficient matroid semi-bandits.  _arXiv preprint arXiv:1902.03794_ , 2019.
  * Perrault et al. (2020a) Pierre Perrault, Etienne Boursier, Michal Valko, and Vianney Perchet.  Statistical efficiency of thompson sampling for combinatorial semi-bandits.  _Advances in Neural Information Processing Systems_ , 33, 2020a.
  * Perrault et al. (2020b) Pierre Perrault, Michal Valko, and Vianney Perchet.  Covariance-adapting algorithm for semi-bandits with application to sparse outcomes.  In _Conference on Learning Theory_ , pages 3152–3184. PMLR, 2020b.
  * Raghavan et al. (2018) Manish Raghavan, Aleksandrs Slivkins, Jennifer Wortman Vaughan, and Zhiwei Steven Wu.  The externalities of exploration and how data diversity helps exploitation.  _arXiv preprint arXiv:1806.00543_ , 2018.
  * Raghavan et al. (2020) Manish Raghavan, Aleksandrs Slivkins, Jennifer Wortman Vaughan, and Zhiwei Steven Wu.  Greedy algorithm almost dominates in smoothed contextual bandits.  _arXiv preprint arXiv:2005.10624_ , 2020.
  * Russo and Van Roy (2018) Daniel Russo and Benjamin Van Roy.  Satisficing in time-sensitive bandit learning.  _arXiv preprint arXiv:1803.02855_ , 2018.
  * Slivkins (2019) Aleksandrs Slivkins.  Introduction to multi-armed bandits.  _arXiv preprint arXiv:1904.07272_ , 2019.
  * Teytaud et al. (2007) Olivier Teytaud, Sylvain Gelly, and Michele Sebag.  Anytime many-armed bandits.  2007\.
  * Thompson (1933) William R Thompson.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  _Biometrika_ , 25(3/4):285–294, 1933.
  * Vermorel and Mohri (2005) Joannes Vermorel and Mehryar Mohri.  Multi-armed bandit algorithms and empirical evaluation.  In _European conference on machine learning_ , pages 437–448. Springer, 2005.
  * Wang et al. (2017) Erli Wang, Hanna Kurniawati, and Dirk P Kroese.  Cemab: A cross-entropy-based method for large-scale multi-armed bandits.  In _Australasian Conference on Artificial Life and Computational Intelligence_ , pages 353–365. Springer, 2017.
  * Wang et al. (2009) Yizao Wang, Jean-Yves Audibert, and Rémi Munos.  Algorithms for infinitely many-armed bandits.  In _Advances in Neural Information Processing Systems_ , pages 1729–1736, 2009.
  * Xia et al. (2015) Yingce Xia, Haifang Li, Tao Qin, Nenghai Yu, and Tie-Yan Liu.  Thompson sampling for budgeted multi-armed bandits.  In _Twenty-Fourth International Joint Conference on Artificial Intelligence_ , 2015.
  * Xia et al. (2016) Yingce Xia, Wenkui Ding, Xu-Dong Zhang, Nenghai Yu, and Tao Qin.  Budgeted bandit problems with continuous random costs.  In _Asian conference on machine learning_ , pages 317–332, 2016.
  * Zhu and Nowak (2020) Yinglun Zhu and Robert Nowak.  On regret with multiple best arms.  _Advances in Neural Information Processing Systems_ , 33, 2020.

##  Appendix A Additional figures

This section provides illustrations that we did not include in the article in
order to not overload it.

###  A.1 Failure of Greedy

Here, we illustrate Example 1.1, that is the failure of Greedy. We recall that
we considered a Bernoulli bandit problem consisting of $K=2$ arms with mean
rewards $0.9$ and $0.1$ respectively. In Figure 7, we compare the regret of
Greedy with the Thompson Sampling algorithm (Thompson, 1933).

Figure 7: Regret of various algorithms as a function of time in a Bernoulli
bandit problem. Results are averaged over $1000$ runs and the shaded area
represents $0.1$ standard deviation.

###  A.2 Continuous functions studied

This section provides the plots of the studied functions in Subsection 7.1.
These functions, displayed on Figure LABEL:fig:continuous_functions, are
recalled below for convenience.

$\displaystyle f_{1}:x$ $\displaystyle\mapsto 0.5\sin(13x)\sin(27x)+0.5,$
$\displaystyle f_{2}:x$
$\displaystyle\mapsto\max\left(3.6x(1-x),1-|x-0.05|/0.05\right)$
$\displaystyle f_{3}:x$ $\displaystyle\mapsto
x(1-x)\left(4-\sqrt{|\sin{60x}|}\right)$

fig:continuous_functions [$f_{1}$][$f_{2}$] [$f_{3}$]

Figure 8: Functions considered in the continuous-armed bandit experiments.

##  Appendix B Proofs of Section 3

###  B.1 Proof of Theorem 3.1

The proof combines two techniques standard in the literature: creating a
“good” event in order to distinguish the randomness of the distributions from
the behavior of the algorithm and decomposing the arms into near-optimal and
suboptimal ones. Fix some $\varepsilon>0$.

#### Good event

Define the event $\mathfrak{E}$, through its complement, by

$\mathfrak{E}^{c}=\bigcap_{k:\Delta_{k}\leq\varepsilon}\mathbb{P}\left(\exists
t\,|\,\widehat{\mu}_{k}(t)\leq\mu_{k}-\varepsilon\right)\,.$

In words, $\mathfrak{E}$ is the event that at least one $\varepsilon$-optimal
arm is never underestimated by more than $\varepsilon$ below its mean reward.
Using the independence of the events along with the concentration bound of
Bayati et al. (2020), see Lemma F.2, we obtain

$\mathbb{P}\left(\mathfrak{E}^{c}\right)\leq\exp\left(-N_{\varepsilon}\frac{\varepsilon^{2}}{2}\right)\,.$
(1)

#### Bound on the number of pulls of suboptimal arms

On the event $\mathfrak{E}$, let $k\in[K]$ be an arm such that
$\Delta_{k}>3\varepsilon$. With a slight abuse of notation, we denote by
$\widehat{\mu}_{k}^{t}$ the average reward of arm $k$ after $t$ samples. The
expected number of pulls of arm $k$ is then bounded by

$\displaystyle\mathbb{E}\left[N_{k}(T)\,|\,\mathfrak{E}\right]$
$\displaystyle\leq
1+\sum_{t=1}^{\infty}\mathbb{P}\left(\widehat{\mu}_{k}^{t}\geq\mu^{\star}-2\varepsilon\right)$
$\displaystyle=1+\sum_{t=1}^{\infty}\mathbb{P}\left(\widehat{\mu}_{k}^{t}-\mu_{k}\geq\Delta_{k}-2\varepsilon\right)$
$\displaystyle\leq
1+\sum_{t=1}^{\infty}\exp\left(-t\frac{(\Delta_{k}-2\varepsilon)^{2}}{2}\right)$
$\displaystyle=1+\frac{1}{\exp\left(\frac{(\Delta_{k}-2\varepsilon)^{2}}{2}\right)-1}$
$\displaystyle\leq 1+\frac{2}{(\Delta_{k}-2\varepsilon)^{2}}$ (2)

where in second inequality we use Lemma F.1 since $\widehat{\mu}_{k}^{t}$ is
$1/t$-subgaussian and in the last inequality we used that $e^{x}\geq 1+x$ for
all $x\in\mathbb{R}$.

#### Putting things together

We first decompose the regret according to the event $\mathfrak{E}$

$R_{T}\leq\mathbb{E}\left[R_{T}|\mathfrak{E}^{c}\right]\mathbb{P}\left(\mathfrak{E}^{c}\right)+\mathbb{E}\left[R_{T}|\mathfrak{E}\right]\,.$
(3)

As mean rewards are bounded in $[0,1]$, the regret on the bad event is bounded
by $T$ and by Equation (1) we have

$\mathbb{E}\left[R_{T}|\mathfrak{E}^{c}\right]\mathbb{P}\left(\mathfrak{E}^{c}\right)\leq
T\exp\left(-N_{\varepsilon}\frac{\varepsilon^{2}}{2}\right)\,.$

We further decompose the second term on the right-hand side of Equation (3),

$\mathbb{E}\left[R_{T}|\mathfrak{E}\right]\leq\sum_{k:\Delta_{k}\leq
3\varepsilon}\Delta_{k}\mathbb{E}\left[N_{k}(T)|\mathfrak{E}\right]+\sum_{k:\Delta_{k}>3\varepsilon}\Delta_{k}\mathbb{E}\left[N_{k}(T)|\mathfrak{E}\right]\,.$

The first term is trivially bounded by $3\varepsilon T$, while for the second
term we have by Equation (2),

$\displaystyle\sum_{k:\Delta_{k}>3\varepsilon}\Delta_{k}\mathbb{E}\left[N_{k}(T)|\mathfrak{E}\right]$
$\displaystyle\leq\sum_{k:\Delta_{k}>3\varepsilon}\frac{2\Delta_{k}}{(\Delta_{k}-2\varepsilon)^{2}}+\sum_{k=1}^{K}\Delta_{k}$
$\displaystyle\leq\sum_{k:\Delta_{k}>3\varepsilon}\frac{6}{(\Delta_{k}-2\varepsilon)}+\sum_{k=1}^{K}\Delta_{k}$
$\displaystyle\leq\sum_{k:\Delta_{k}>3\varepsilon}\frac{6}{\varepsilon}+\sum_{k=1}^{K}\Delta_{k}\leq\frac{6K}{\varepsilon}+\sum_{k=1}^{K}\Delta_{k}$

where in the second inequality we used that $\Delta_{k}\leq
3(\Delta_{k}-2\varepsilon)$, which holds true since $\Delta_{k}\geq
3\varepsilon$. Hence the result.

###  B.2 Proof of Corollary 3.4

We recall the definition of the event $\mathfrak{E}_{\varepsilon}$, through
its complement $\mathfrak{E}^{c}_{\varepsilon}$,

$\mathfrak{E}^{c}_{\varepsilon}=\bigcap_{k:\Delta_{k}\leq\varepsilon}\mathbb{P}\left(\exists
t\,|\,\widehat{\mu}_{k}(t)\leq\mu_{k}-\varepsilon\right)\,.$

Consider any increasing sequence $\left\\{\varepsilon_{m}\right\\}_{m=0}^{M}$
and denote $\mathfrak{E}_{m}$ the good event associated with $\varepsilon_{m}$
for $m\in\\{0,\ldots,M\\}$. By the chain rule and the previous computation of
the regret on the good event (see proof of Theorem 3.1), we have

$\displaystyle R_{T}$
$\displaystyle\leq\left(3\varepsilon_{0}T+\frac{6K}{\varepsilon_{0}}\right)\mathbb{P}\left(\mathfrak{E}_{0}\right)+\left(3\varepsilon_{1}T+\frac{6K}{\varepsilon_{1}}\right)\mathbb{P}(\mathfrak{E}_{1}\cap\mathfrak{E}_{0}^{c})+\ldots$
$\displaystyle\quad+\left(3\varepsilon_{M}T+\frac{6K}{\varepsilon_{M}}\right)\mathbb{P}(\mathfrak{E}_{M}\cap\mathfrak{E}_{M-1}^{c})+T\mathbb{P}(\mathfrak{E}_{M-1}^{c})+\sum_{k=1}^{K}\Delta_{k}$
$\displaystyle\leq\left[\left(3\varepsilon_{0}T+\frac{6K}{\varepsilon_{0}}\right)-\left(3\varepsilon_{1}T+\frac{6K}{\varepsilon_{1}}\right)\right]\mathbb{P}\left(\mathfrak{E}_{0}\right)+\ldots$
$\displaystyle\quad+\left[\left(3\varepsilon_{M-1}T+\frac{6K}{\varepsilon_{M-1}}\right)-\left(3\varepsilon_{M}T+\frac{6K}{\varepsilon_{M}}\right)\right]\mathbb{P}\left(\mathfrak{E}_{M-1}\right)$
$\displaystyle\quad+\left(3\varepsilon_{M}T+\frac{6K}{\varepsilon_{M}}\right)\mathbb{P}\left(\mathfrak{E}_{M}\right)+T\mathbb{P}(\mathfrak{E}_{M}^{c})+\sum_{k=1}^{K}\Delta_{k}$

where in the second inequality we used that
$\mathbf{1}\\{\mathfrak{A}\cap\mathfrak{B}^{c}\\}=\mathbf{1}\\{\mathfrak{A}\\}-\mathbf{1}\\{\mathfrak{B}\\}$
if $\mathfrak{B}\subset\mathfrak{A}$. In the proof of Theorem 3.1, we show
that

$\mathbb{P}(\mathfrak{E}_{m}^{c})\leq\exp\left(-N_{\varepsilon_{m}}\frac{\varepsilon^{2}_{m}}{2}\right)$

for $m\in\\{0,\ldots,M\\}$. Hence we obtain

$\displaystyle R(T)$
$\displaystyle\leq\left(3\varepsilon_{0}T+\frac{6K}{\varepsilon_{0}}\right)$
$\displaystyle\quad+\sum_{m=0}^{M-1}\left[\left(3\varepsilon_{m+1}T+\frac{6K}{\varepsilon_{m+1}}\right)-\left(3\varepsilon_{m}T+\frac{6K}{\varepsilon_{m}}\right)\right]\exp\left(-N_{\varepsilon_{m}}\frac{\varepsilon^{2}_{m}}{2}\right)$
$\displaystyle\quad+T\exp\left(-\frac{K}{2}\right)+\sum_{k=1}^{K}\Delta_{k}$

The middle term is upper-bounded by

$\sum_{m=0}^{M-1}(\varepsilon_{m+1}-\varepsilon_{m})\left[3T+\frac{6K}{\varepsilon^{2}_{m}}\right]\exp\left(-N_{\varepsilon_{m}}\frac{\varepsilon^{2}_{m}}{2}\right),$

which converges, as the mesh of the sequence $\varepsilon_{m}$ goes to zero,
towards

$\int_{\varepsilon}^{1}\left(3T+\frac{6K}{x^{2}}\right)\exp\left(-N_{x}\frac{x^{2}}{2}\right)dx$

Hence the result.

##  Appendix C Proof of Theorem 4.3

Let $\varepsilon>0$. The regret can be decomposed into an approximation and an
estimation term,

$Tf(x^{\star})-\sum_{t=1}^{T}f(x_{t})=T\left(f(x^{\star})-\max_{k\in[K]}f\left(\frac{k}{K}\right)\right)+\left(T\max_{k\in[K]}f\left(\frac{k}{K}\right)-\sum_{t=1}^{T}f(x_{t})\right)\,.$

By Assumption 4.1, the first term is bounded by $\varepsilon T$ when
$K\geq\left(\frac{L}{\varepsilon}\right)^{1/\alpha}$. Then, according to
Theorem 3.1, we just have to lower bound $N_{\varepsilon}$ to conclude. To do
so, we prove a lower bound on the number of arms that are
$\varepsilon$-optimal with respect to the best arm overall. Let
$N_{\varepsilon}^{C}$ denotes this quantity.

#### Bound on $N_{\varepsilon}^{C}$

By Assumption 4.1, an $\varepsilon$-optimal arm $k$ may verify (there can be
$\varepsilon$-optimal that are not around the maxima)

$L\left|x^{\star}-k/K\right|^{\alpha}\leq\varepsilon\,.$

Knowing that $k$ is an integer, we obtain

$\left\lceil
K\left(x^{\star}-\left(\frac{\varepsilon}{L}\right)^{1/\alpha}\right)\right\rceil\leq
k\leq\left\lfloor
K\left(x^{\star}+\left(\frac{\varepsilon}{L}\right)^{1/\alpha}\right)\right\rfloor\,.$

This means that we have the following lower bound on $N_{\varepsilon}^{C}$

$N_{\varepsilon}^{C}\geq\left\lfloor
K\left(x^{\star}+\left(\frac{\varepsilon}{L}\right)^{1/\alpha}\right)\right\rfloor-\left\lceil
K\left(x^{\star}-\left(\frac{\varepsilon}{L}\right)^{1/\alpha}\right)\right\rceil+1\,.$

Thanks to Lemma F.4, we obtain

$N_{\varepsilon}^{C}\geq\left\lfloor
2K\left(\varepsilon/L\right)^{1/\alpha}\right\rfloor\,.$

Finally, using that $\left\lfloor 2x\right\rfloor\geq x$ for $x\geq 1$ (easily
verify with the assumption on $K$), we obtain the following lower bound

$N_{\varepsilon}^{C}\geq K\left(\varepsilon/L\right)^{1/\alpha}\,.$

#### Conclusion

We trivially have that $N_{\varepsilon}\geq N_{\varepsilon}^{C}$. The first
part of the Theorem then results from the fact that
$\sum_{k=1}^{K}\Delta_{k}\leq K$ since $\mu_{k}\in[0,1]$ for all $k\in[K]$. On
the other hand, the second part comes from taking $\varepsilon^{2}=3K/(2T)$
which is the value of $\varepsilon$ that minimizes the term $4\varepsilon
T+6K/\varepsilon$.

##  Appendix D Proof of Theorem 5.2

Let $\varepsilon>0$. Once again, thanks to Theorem 3.1 we just have to bound
$N_{\varepsilon}$ and the result will follow by adding the approximation cost
$\varepsilon T$. We construct a good event on the expected rewards of sampled
arms. Let $I_{\varepsilon}=[\mu^{\star}-\varepsilon,\mu^{\star}]$ and
$N_{\varepsilon}^{I}=\sum_{k=1}^{K}\mathbf{1}\\{k\in I_{\varepsilon}\\}$ be
the number of $\varepsilon$-optimal arms with respect to all arms. Assumption
5.1 implies that

$p=\mathbb{E}\left[\mathbf{1}\\{k\in I_{\varepsilon}\\}\right]=\mathbb{P}(k\in
I_{\varepsilon})\in[c_{1}\varepsilon^{\beta},c_{2}\varepsilon^{\beta}]\,.$

Let $\delta\in[0,1)$. By Chernoff inequality we have

$\mathbb{P}\left(N_{\varepsilon}^{I}<(1-\delta)Kp\right)\leq\exp\left(-Kp\delta^{2}/2\right)\,.$

In particular, taking $\delta=\frac{1}{2}$ yields

$\mathbb{P}\left(N_{\varepsilon}^{I}<c_{1}\varepsilon^{\beta}K/2\right)\leq\exp\left(-c_{1}\varepsilon^{\beta}K/8\right)\,.$

Now we trivially have that $N_{\varepsilon}\geq N_{\varepsilon}^{I}$, and
hence we obtain

$\mathbb{P}\left(N_{\varepsilon}<c_{1}\varepsilon^{\beta}K/2\right)\leq\exp\left(-c_{1}\varepsilon^{\beta}K/8\right)\,.$

By constructing a good event based on the previous concentration bound and
using that $\sum_{k=1}^{K}\Delta_{k}\leq K$, we obtain the first part of the
Theorem. The second part results from (i) the first exponential term dominates
since $\varepsilon^{2+\beta}\leq\varepsilon^{\beta}$ for all
$\varepsilon\in[0,1]$ and $\beta>0$ and (ii) the choice of
$\varepsilon=\sqrt{3K/(2T)}$ which is the value that minimizes $4\varepsilon
T+6K/\varepsilon$.

##  Appendix E Proof of Theorem 6.2

Once again, we just need a lower bound on the number of optimal arms in the
subsampling and we construct a good event to do so. We reuse the previous
notation $N_{\varepsilon}$ to denote this value ($\varepsilon=0$ here). Let
$N_{\varepsilon}^{S}$ be the number of optimal arms with respect to all arms.
In the case of a subsampling of $K$ arms done without replacement,
$N_{\varepsilon}^{S}$ is distributed according to a hypergeometric
distribution. By Hoeffding’s inequality, see Lemma F.3, we have for $0<t<pK$,

$\mathbb{P}\left(N_{\varepsilon}^{S}\leq(p-t)K\right)\leq\exp\left(-2t^{2}K\right)$

where $p=m/n$. We want to choose $t$ such $p-t>0$, otherwise the bound is
meaningless. In particular, the choice of $t=p/2$ yields

$\mathbb{P}\left(N_{\varepsilon}^{S}\leq
pK/2\right)\leq\exp\left(-p^{2}K/2\right)\,.$

We then trivially have that $N_{\varepsilon}\geq N_{\varepsilon}^{S}$. The
regret on the bad events is then given by

$T\left[\exp\left(-pK\varepsilon^{2}/4\right)+\exp\left(-p^{2}K/2\right)\right]$

For this regret to be $\mathcal{O}(1)$, the two following inequalities must be
verify:

$\displaystyle pK\varepsilon^{2}/4$ $\displaystyle\geq\log T$ $\displaystyle
p^{2}K/2$ $\displaystyle\geq\log T$

Now the term $3\varepsilon T+\frac{6K}{\varepsilon}$ of Theorem 3.1 is
minimized for $\varepsilon^{2}=2K/T$. This leads to

$\displaystyle pK^{2}/2$ $\displaystyle\geq T\log T$ $\displaystyle p^{2}K/2$
$\displaystyle\geq\log T$

Using that $p=T^{-\alpha}$, we obtain

$K\geq 2\max\left\\{\sqrt{T^{1+\alpha}},T^{2\alpha}\sqrt{\log
T}\right\\}\sqrt{\log T}\,.$

The proof is concluded by decomposing according to the value inside the max
term.

##  Appendix F Useful Results

In this section, for the sake of completeness, we provide previous results
used in our analysis together with a small lemma.

######  Lemma F.1 (Corollary 5.5 of Lattimore and Szepesvári (2020)).

Let $X_{1},\ldots,X_{n}$ be $n$ independent $\sigma^{2}$-subgaussian random
variables. Then for any $\varepsilon\geq 0$, it holds that

$\mathbb{P}\left(\overline{X}\geq\varepsilon\right)\leq\exp\left(-\frac{n\varepsilon^{2}}{2\sigma^{2}}\right)$

where $\overline{X}=\frac{1}{n}\sum_{i=1}^{n}X_{i}$.

######  Lemma F.2 (Lemma 2 of Bayati et al. (2020)).

Let $Q$ be a distribution with mean $\mu$ such that $Q-\mu$ is 1-subgaussian.
Let $\\{X_{i}\\}_{i=1}^{n}$ be i.i.d. samples from distribution $Q$,
$S_{n}=\sum_{i=1}^{n}X_{i}$ and $M_{n}=S_{n}/n$. Then for any $\delta>0$, we
have

$\mathbb{P}\left(\exists
n:M_{n}<\mu-\delta\right)\leq\exp\left(-\delta^{2}/2\right)\,.$

######  Lemma F.3 (Hoeffding’s inequality).

Let $X_{1},\ldots,X_{n}$ be independent bounded random variables supported in
$[0,1]$. For all $t\geq 0$, we have

$\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}\left(X_{i}-\mathbb{E}[X_{i}]\right)\geq
t\right)\leq\exp\left(-2nt^{2}\right)$

and

$\mathbb{P}\left(\frac{1}{n}\sum_{i=1}^{n}\left(X_{i}-\mathbb{E}[X_{i}]\right)\leq-t\right)\leq\exp\left(-2nt^{2}\right)\,.$

######  Lemma F.4.

Let a and b be two real numbers. Then the following holds true

$\left\lfloor a+b\right\rfloor-\left\lceil a-b\right\rceil\geq\left\lfloor
2b\right\rfloor-1\,.$

######  Proof F.5.

We have

$\displaystyle\left\lfloor a+b\right\rfloor-\left\lceil a-b\right\rceil$
$\displaystyle=\left\lfloor a+b\right\rfloor+\left\lfloor b-a\right\rfloor$
$\displaystyle\geq\left\lfloor a+b+b-a\right\rfloor-1$
$\displaystyle=\left\lfloor 2b\right\rfloor-1$

where we used respectively that, $\left\lceil
x\right\rceil=-\left\lfloor-x\right\rfloor$ and $\left\lfloor
x+y\right\rfloor\leq\left\lfloor x\right\rfloor+\left\lfloor
y\right\rfloor+1$.

##  Appendix G Further experiments

In this section, we evaluate the standard Greedy algorithm, that considers all
arms, in several bandit models to once again highlight its competitive
performance in some cases compared to the state-of-the-art.

###  G.1 Linear bandits

In the linear bandit model, for each round $t$, the learner is given the
decision set $\mathcal{A}_{t}\subset\mathbb{R}^{d}$, from which she chooses an
action $A_{t}\in\mathcal{A}_{t}$ and receives reward
$X_{t}=\langle\theta_{\star},A_{t}\rangle+\eta_{t}$, where
$\theta_{\star}\in\mathbb{R}^{d}$ is an unknown parameter vector and
$\eta_{t}$ is some i.i.d. white noise, usually assume 1-subgaussian. In this
model, the Greedy algorithm consists of two phases: firstly, it computes the
regularized least-square estimator of $\theta$; then, it plays the arm in the
action set that maximizes the linear product with the estimator of $\theta$.

Here we consider a problem with a large dimension relatively to the time
horizon. Precisely, we fix $d=50$, a time horizon $T=2500$ and the noise is a
standard Gaussian distribution. The set of arms consists of the unit ball and
the parameter $\theta$ is randomly generated on the unit sphere. We compare
Greedy with LinUCB (Abbasi-Yadkori et al., 2011) and BallExplore (Deshpande
and Montanari, 2012), an algorithm specifically designed for such a setting.
The regularization term $\lambda$ is set at 1 for Greedy and LinUCB, the
confidence term $\delta=\frac{1}{T}$ for LinUCB and the parameter $\Delta=d$
for BallExplore. Results, displayed on Figure 9, are averaged over 50
iterations. Shaded area represents 2 times the standard deviation for each
algorithm.

Figure 9: Bayesian regret of various algorithms as a function of time in a
linear bandit problem.

We see that Greedy outperforms both LinUCB and BallExplore; in particular the
regret of Greedy is sublinear. Another point that we have not emphasized so
far is the computational complexity. Until now, the difference in terms of
computation was rather insignificant. This is no longer the case for
algorithms designed for linear bandits as they must solve an optimization
problem at each round. For example, in this simulation, the iteration time on
a single-core processor is 70 seconds for Greedy, 678 sec. for LinUCB and 1031
sec. for BallExplore. In words, Greedy is roughly ten times faster than LinUCB
and fifteen times faster than BallExplore.

###  G.2 Cascading bandits

We now consider a special, but popular, case of stochastic combinatorial
optimization under semi-bandit feedback called the cascading bandit problem.
Formally, there are $L\in\mathbb{N}$ ground items and at each round $t$, the
agent recommends a list $\left(a_{1}^{t},\dots,a_{K}^{t}\right)$ of $K\leq L$
items to the user. The user examines the list, from the first item to the
last, and clicks on the first attractive item, if any. A weight $w(l)\in[0,1]$
is associated to each item $l\in[L]$, which denotes the click probability of
the item. The reward of the agent at round $t$ is given by
$1-\prod_{K=1}^{K}\left(1-w(a_{k}^{t})\right)\in\\{0,1\\}$ and she receives
feedback for each $k\in[K]$ such that $k\leq c_{t}=\min\left\\{1\leq k\leq
K:w_{t}(a_{k}^{t})=1\right\\}$ where
$w_{t}(a_{k}^{t})\sim\text{Bernoulli}(w(a_{k}^{t}))$ and we assume that the
minimum over an empty set is $\infty$. In this setting, the Greedy algorithm
outputs a list consisting of the $K$ best empirical arms. The goal of these
experiments is to study in which regimes, as a function of $L$ and $K$, the
Greedy algorithm might be preferable to the state-of-the-art.

We reproduce the experiments of Kveton et al. (2015) in the Bayesian setting.
We compare Greedy with CascadeKL-UCB (Kveton et al., 2015) and TS-Cascade
(Cheung et al., 2019). Greedy and CascadeKL-UCB share the same initialization
which is to select each item once as the first item on the list. For each
algorithm, the list is ordered from the largest index to the smallest one. We
consider two scenarios: on the first one, the prior on the mean rewards is a
uniform distribution over $[0,1]$ while on the second scenario, we consider a
more realistic Beta(1, 3) distribution so that most arms have low mean
rewards. The time horizon is set at $T=10000$. The regret and standard
deviation of each algorithm, averaged over 100 iterations, are reported in
Table 1 and 2 for different values of $L$ and $K$.

Table 1: Bayesian regret of various algorithms in cascading bandit problems with a uniform prior. L | K | Greedy | CascadeKL-UCB | TS-Cascade
---|---|---|---|---
16 | 2 | 176.1 $\pm$ 26.4 | 48.1 $\pm$ 2.7 | 109.7 $\pm$ 1.8
16 | 4 | 10.2 $\pm$ 1.9 | 9.9 $\pm$ 1.0 | 28.4 $\pm$ 0.9
16 | 8 | 0.7 $\pm$ 0.2 | 0.7 $\pm$ 0.1 | 3.6 $\pm$ 0.3
32 | 2 | 166.1 $\pm$ 22.8 | 58.7 $\pm$ 3.5 | 178.7 $\pm$ 2.5
32 | 4 | 6.7 $\pm$ 0.9 | 10.1 $\pm$ 0.8 | 47.0 $\pm$ 1.0
32 | 8 | 0.2 $\pm$ 0.03 | 0.7 $\pm$ 0.08 | 8.3 $\pm$ 0.4
64 | 2 | 135.5 $\pm$ 15.6 | 76.6 $\pm$ 3.7 | 288.6 $\pm$ 2.6
64 | 4 | 6.5 $\pm$ 0.5 | 12.5 $\pm$ 0.6 | 80.3 $\pm$ 1.3
64 | 8 | 0.3 $\pm$ 0.02 | 0.9 $\pm$ 0.07 | 16.6 $\pm$ 0.5
128 | 2 | 133.1 $\pm$ 12.4 | 107.4 $\pm$ 4.8 | 442.6 $\pm$ 3.4
128 | 4 | 9.4 $\pm$ 0.3 | 18.0 $\pm$ 0.8 | 127.4 $\pm$ 1.5
128 | 8 | 0.5 $\pm$ 0.02 | 1.5 $\pm$ 0.1 | 27.9 $\pm$ 0.6
256 | 2 | 137.2 $\pm$ 10.6 | 151.0 $\pm$ 5.6 | 605.7 $\pm$ 3.1
256 | 4 | 16.6 $\pm$ 0.2 | 26.9 $\pm$ 1.0 | 179.5 $\pm$ 1.4
256 | 8 | 1.0 $\pm$ 0.03 | 1.8 $\pm$ 0.1 | 39.9 $\pm$ 0.5
Table 2: Bayesian regret of various algorithms in cascading bandit problems with a Beta(1, 3) prior. L | K | Greedy | CascadeKL-UCB | TS-Cascade
---|---|---|---|---
16 | 2 | 590.4 $\pm$ 83.5 | 207.9 $\pm$ 5.2 | 199.5 $\pm$ 3.6
16 | 4 | 304.8 $\pm$ 35.7 | 116.4 $\pm$ 4.2 | 103.2 $\pm$ 2.9
16 | 8 | 97.9 $\pm$ 11.7 | 39.6 $\pm$ 2.1 | 34.4 $\pm$ 1.6
32 | 2 | 433.1 $\pm$ 49.1 | 330.7 $\pm$ 8.3 | 333.7 $\pm$ 3.8
32 | 4 | 192.2 $\pm$ 23.1 | 166.2 $\pm$ 6.0 | 163.3 $\pm$ 3.7
32 | 8 | 38.7 $\pm$ 5.3 | 50.1 $\pm$ 2.9 | 54.6 $\pm$ 1.9
64 | 2 | 576.2 $\pm$ 55.8 | 485.8 $\pm$ 11.2 | 540.1 $\pm$ 4.8
64 | 4 | 144.2 $\pm$ 12.3 | 207.5 $\pm$ 6.8 | 246.1 $\pm$ 4.1
64 | 8 | 20.3 $\pm$ 1.8 | 49.2 $\pm$ 2.2 | 76.4 $\pm$ 1.6
128 | 2 | 575.2 $\pm$ 40.1 | 710.9 $\pm$ 16.3 | 843.4 $\pm$ 4.7
128 | 4 | 100.8 $\pm$ 5.5 | 270.6 $\pm$ 7.4 | 372.9 $\pm$ 3.7
128 | 8 | 18.0 $\pm$ 0.6 | 60.7 $\pm$ 2.0 | 115.7 $\pm$ 1.4
256 | 2 | 522.5 $\pm$ 32.4 | 1068.3 $\pm$ 26.1 | 1235.1 $\pm$ 6.3
256 | 4 | 125.1 $\pm$ 3.8 | 380.0 $\pm$ 10.3 | 551.1 $\pm$ 3.85
256 | 8 | 27.3 $\pm$ 0.4 | 86.4 $\pm$ 2.6 | 174.8 $\pm$ 1.5

As expected by the Bayesian setting, Greedy outplays the state-of-the-art when
the number of arms $L$ is large. Even more interesting is that, as the number
of recommended items $K$ gets larger the regret of Greedy decreases at a
faster rate than the other algorithms. Our intuition is that the conservatism
of standard bandit algorithms is amplified as $K$ increases and this is
further exacerbated by the cascade model where items at the bottom of the list
may not get a feedback. On the contrary, the Greedy algorithm quickly
converges to a solution that uniquely depends on past individual performances
of arms. In addition, the contrast between the performance of Greedy and the
state-of-the-art is even more striking in the second scenario. This is not
particularly surprising as the Beta(1, 3) distribution gives rise to harder
problems for the considered time horizon.

###  G.3 Mortal bandits

We now consider the mortal bandit problem where arms die and new ones appear
regularly (in particular, an arm is not always available contrary to the
standard model). In this setting, the Greedy algorithm pulls the best
empirical arm available. As previous work considered a large number of arms,
state-of-the-art algorithms in this setting, e.g. AdaptiveGreedy (Chakrabarti
et al., 2009), emphasis an hidden subsampling of arms due to their
initialization. They further required a careful (manual) tuning of their
parameter for optimal performance. Consequently, we compare Greedy to a
standard bandit algorithm extended to this model and we consider a small
number of arms. Similarly to the last setting, the goal is to observe in which
regimes, as a function of the mean lifetime of arms, Greedy might be
preferable.

We repeat the experiments of Chakrabarti et al. (2009) with $K=100$ arms. The
number of arms remains fixed throughout the time horizon $T$, that is when an
arm dies, it is immediately replaced by another one. The time horizon $T$ is
set at 10 times the mean lifetime of the arms. The lifetime of arm $k$,
denoted $L_{k}$, is drawn i.i.d. from a geometric distribution with mean
lifetime $L$; this arm dies after being available for $L_{k}$ rounds. We
consider logarithmically spaced values of mean lifetimes. We also assume that
arms are Bernoulli random variables. We consider two scenarios: in the first
one, mean rewards of arms are drawn i.i.d. from a uniform distribution over
[0, 1], while in the second scenario they are drawn from a Beta(1, 3)
distribution. We compare the Greedy algorithm with Thompson Sampling (Agrawal
and Goyal, 2012). Results are averaged over 100 iterations and are reported on
Figure LABEL:fig:exp_mortal. Shaded area represents 0.5 standard deviation for
each algorithm.

fig:exp_mortal [Uniform prior][Beta(1, 3) prior]

Figure 10: Bayesian regret of various algorithms as a function of the expected
lifetime of arms in mortal bandit problems.

As expected, Greedy outperforms Thompson Sampling for intermediate expected
lifetime and vice versa for long lifetime. And for short lifetime, as we
previously saw, a sub-sampling of arms could have considerably improve the
performance of both algorithms.

###  G.4 Budgeted bandits

We now consider the budgeted bandit problem. In this model, the pull of arm
$k$ at round $t$ entails a random cost $c_{k}(t)$. Moreover, the learner has a
budget $B$, which is a known parameter, that will constrain the total number
of pulls. In this setting, the index of an arm in the Greedy algorithm is the
average reward divided by the average cost. Like before, the objective is to
evaluate in which regimes with respect to the budget $B$, Greedy might be
preferable to a state-of-the-art algorithm.

We reproduce the experiments of Xia et al. (2016). Specifically, we study two
scenarios with $K=100$ arms in each. The first scenario considers discrete
costs; both the reward and the cost are sampled from Bernoulli distributions
with parameters randomly sampled from $(0,1)$. The second scenario considers
continuous costs; the reward and cost of an arm is sampled from two different
Beta distributions, the two parameters of each distribution are uniformly
sampled from $[1,5]$. The budget is chosen from the set
$\\{100,500,1000,5000,10000\\}$. We compare Greedy to Budget-UCB (Xia et al.,
2016) and BTS (Xia et al., 2015). The results of simulations are displayed in
Figure LABEL:fig:exp_budgeted and are averaged over 500 runs. Shaded area
represents 0.5 standard deviation for each algorithm.

fig:exp_budgeted [Discrete costs][Continuous costs]

Figure 11: Regret of various algorithms as a function of the budget in
budgeted bandit problems.

Interestingly, in this setting the interval of budgets for which Greedy
outperforms baseline algorithms is extremely small for discrete costs and
large for continuous costs. In the latter case, even for large budget Greedy
has a lower expected regret than BTS. Nonetheless it suffers from a huge
variance which makes its use risky in practice.