There is a rising interest in industrial online applications where data becomes available sequentially.

Inspired by the recommendation of playlists to users where their preferences can be collected during the listening of the entire playlist, we study a novel bandit setting, namely Multi-Armed Bandit with Temporally-Partitioned Rewards (TP-MAB), in which the stochastic reward associated with the pull of an arm is partitioned over a finite number of consecutive rounds following the pull.

This setting, unexplored so far to the best of our knowledge, is a natural extension of delayed-feedback bandits to the case in which rewards may be dilated over a finite-time span after the pull instead of being fully disclosed in a single, potentially delayed round.

We provide two algorithms to address TP-MAB problems, namely,  and , which exploit the partial information disclosed by the reward collected over time.

We show that our algorithms provide better asymptotical regret upper bounds than delayed-feedback bandit algorithms when a property characterizing a broad set of reward structures of practical interest, namely $\alpha$-smoothness, holds.

We also empirically evaluate their performance across a wide range of settings, both synthetically generated and from a real-world media recommendation problem.

§ INTRODUCTION

Sequential decision-making occurs in many real-world scenarios such as clinical trials, recommender systems, web advertising, and e-commerce.

Inspired by these applications, many different flavours of the multi-armed bandit (MAB) setting have been investigated.

A crucial role is played by the time the reward is observed.

In many cases, the reward is subject to a delay, and such a delay, if not sufficiently short, can prevent the design of algorithms that are effective in practice.

Online learning with delayed feedback has received considerable attention in recent years, and several results are available in the literature, e.g., see the seminal work by [12] [[12]].

A major distinction in MABs with delayed feedback concerns the nature of the rewards, which may be stochastic [13, 8] or adversarial [3, 19, 21].

Our work focuses on a special class of bandit problems with stochastic and delayed rewards, in which we can get partial feedback over time.

More precisely, we study a novel setting, namely MAB with Temporally-Partitioned Rewards (TP-MAB), in which the reward associated with an action, a.k.a. arm, chosen at a given round is collected during a finite number of rounds following the choice, according to an unknown probability distribution.

In classical delayed-feedback bandits (see, e.g., [12] [[12]]), the reward is concentrated in a single round that is (stochastically) delayed w.r.t. the round in which the learner pulled the corresponding arm.

TP-MABs naturally extend this setting by allowing the reward to be partitioned into multiple elements that are collected with different delays.

We call arm's per-round reward the partial reward observed by the learner in a single round, which is assumed to be the realization of a random variable with an unknown probability distribution.

We call arm's cumulative reward the random variable given by the sum of all the per-round rewards obtained by pulling an arm.

While the per-round reward can be observed round by round, the cumulative reward is revealed only at the end.

Notice that, in a single round, the learner observes a per-round reward for each previously pulled arm whose cumulative reward is not terminated yet.

Our goal is to find a policy to maximize the cumulative reward, exploiting the per-round rewards as intermediate signals on the arm performance.

Motivating applications.

A motivating example for TP-MABs is recommending media content and, in particular, song playlists to a class of users (i.e., users sharing similar characteristics).

In this setting, each arm corresponds to a playlist.

The reward is measured in listening time (proportional to the user's appreciation).

The goal is to find the playlist that maximizes the reward.

The recommendation system suggests a playlist to a new user at each round, whose appreciation is revealed through multiple steps.

In particular, every partial observation corresponds to a song in the playlist, and the associated reward is positive if the user listens to that song and non-positive otherwise.

The cumulative reward provided by recommending a playlist to a single user corresponds to the sum of the reward terms from all the playlist songs.

Notice that the playlist cannot be trivially modeled as a collection of independent songs, as their order in the playlist affects the user's behavior.

In the classical delayed-feedback bandit setting, the feedback on the recommended playlist is obtained only once the user finishes listening to the entire playlist.

However, the platform monitors whether every song is listened to or skipped by the user.

Therefore, clues on the performances of the recommended arm can be exploited before the user finishes the playlist.

Another scenario captured by the TP-MAB framework is the evaluation of medical treatments taking place over a long period of time.

In this setting, the per-round reward corresponds to the patient's state of health at each daily/weekly medical check, and the goal is to find the treatment providing the greatest overall benefit to the patient.

In the case of severe pathologies, such as cancer, this type of partial information would span several months if not years, providing valuable insights that would be otherwise ignored.

Applying a standard delayed-MAB approach to this scenario, i.e., taking decisions only at the end of each treatment cycle, could negatively affect the time required to select an effective medical treatment.

In this type of setting, we argue that the partial information provided by patients in periodic medical checks should be used to speed up the learning process.

Original Contributions.

Initially, we focus on the lower bound of TP-MABs, showing that the TP-MAB setting has the same regret lower bound of the standard delayed MAB setting when there is no further assumption about how the rewards are partitioned over time.

Since in many practical applications of interest the cumulative reward of each arm does not concentrate excessively in a short sub-range of rounds, we introduce a property describing how the maximum per-round reward distributes.

We call this property $\alpha$-smoothness where $\alpha \geq 1$.

In particular, the minimum value of $\alpha=1$ corresponds to the case in which there is no structure and, therefore, the maximum per-round reward can be the entire cumulative reward.

On the other hand, the maximum value of $\alpha$ is equal to the maximum delay and corresponds to the case in which the cumulative reward distributes evenly over time.

Thus, the maximum per-round reward decreases as the value of $\alpha$ increases.

We show that the lower bound of this setting is of a factor $1 / \alpha$ smaller than that when $\alpha$-smoothness does not hold.

Then, we design two novel algorithms, namely  and , suited for the TP-MAB setting, which exploit partial feedback and the $\alpha$-smoothness property.

We show that the regret of  is $\mathcal{O}(\ln T/\alpha)$, where $T$ is the time horizon of the learning process, and the regret of  is $\mathcal{O}(\ln T)$.
A comprehensive analysis the regret bounds of our and state-of-the-art algorithms  in various settings can be found in Table 3 (in Appendix A for reasons of space).

Finally, we experimentally show that our algorithms outperform the state of the art over synthetically generated and a real-world playlist recommendation scenario.

Related Works.

To the best of our knowledge, ours is the first work addressing a bandit problem in which the reward from a pull is partitioned across multiple rounds.

The most related works concern the Delayed-MAB setting, such as the seminal paper by [12] [[12]], which summarizes the known results on the regret upper bounds of online learning algorithms.

They also provide a modification of the well-known UCB1 algorithm from [2] [[2]] for the delayed-feedback setting, called Delayed-UCB1.

More recently, a variety of delayed-feedback scenarios were studied investigating directions different from ours, such as linear and contextual ([1] [[1]], [23] [[23]], [25] [[25]]), non-stationary ([24] [[24]]) bandits under delayed feedback.

[18] [[18]] and [9] [[9]] also analyze the case of delayed, aggregated, and anonymous feedback.

For clarity, we remark that, in our work, per-round rewards corresponding to different pulls can be received in the same round, and it is known from which arm they were generated.

Many works apply bandits to practical scenarios, e.g., scheduling [7], advertising [16, 6, 17], pricing [20], and delayed feedback settings [22].

Works from the bandit literature, such as the ones by [11] [[11]], [10] [[10]], [15] [[15]], rely on known constant delays or maximum delay values.

Similarly, in our work, we assume a maximum finite delay equal to $\Tmax$, which is compliant with the real-world scenarios we aim at modeling, e.g., in the above example of playlist recommendations, an infinite $\Tmax$ would correspond to a playlist of an infinite number of songs.

According to the terminology used in the delayed-MAB literature, our setting is uncensored, meaning that the reward provided by a given action is eventually observed after a finite maximum delay.

Conversely, many works in the field, such as, e.g., [14] [[14]] and [22] [[22]], deals with random delays from an unbounded distribution with finite expectation.

§ PROBLEM FORMULATION

Consider a MAB problem with $K \in \mathbb{N}^*$ arms, over a time horizon of $T \in \mathbb{N}^*$ rounds.

At every round $t \in [T]$, the learner pulls an arm $i \in \mathcal{A} = [K]$ and, from the pull of that arm, gets a per-round reward $x_{t,m-t+1}^i$ at every round $m \in \{t, \ldots, t + \Tmax - 1\}$, where $\Tmax \in \mathbb{N}^*$ is the time span over which the reward is partitioned.[We denote by $[n]$ the set $\{1, \ldots, n \}$]

In particular, $\Tmax - 1$ is the maximum delay affecting the observation of a per-round reward, whose value is known to the learner.

Therefore, at round $t + \Tmax - 1$, the cumulative reward from pulling arm $i$ at round $t$ is completely collected by the learner.

Furthermore, we denote by $\bm{x}^i_t = [x_{t,1}^i, \ldots, x_{t,\Tmax}^i]$ the vector of per-round rewards collected from pulling arm $i$ at round $t$.

For every $j \in [\Tmax]$, the per-round reward $x_{t,j}^i$ is a realization of a random variable $X_{t,j}^i$ with support $[\underline{X}_{j}^i, \overline{X}_{j}^i]$.

The cumulative reward collected from pulling arm $i$ at round $t$ is denoted by $r_{t}^i$, and it is the realization of the random variable $R_t^i := \sum_{j=1}^{\Tmax}{X_{t,j}^i}$, with support $[\underline{R}^i, \overline{R}^i]$, where $\underline{R}^i := \sum_{j=1}^{\Tmax}\underline{X}_{j}^i$, and $\overline{R}^i := \sum_{j=1}^{\Tmax}\overline{X}_{j}^i$.

For every $i \in \mathcal{A}$ and $t \in [T]$, we assume that the variables $R^i_t$ are independent with mean $\mu_i := \mathbb{E}[R^i_t]$.[

W.l.o.g., we assume $\underline{X}_{j}^i = 0, \forall i \in [K], \forall j \in [\Tmax]$.

A policy $\mathfrak{U}$ is an algorithm that at each round $t$ chooses an arm $i_t \in [K]$ .

The performance of a policy $\mathfrak{U}$ is evaluated in terms of pseudo-regret, defined as the cumulative loss due to playing suboptimal arms during the time horizon $T$, formally:

\begin{equation*}
\mathcal{R}_T(\mathfrak{U}) = T \mu^* - \mathbb{E} \left[\sum_{t=1}^{T} \mu_{i_t} \right],
\end{equation*}

where $\mu^* = \max_{i \in \mathcal{A}} \{\mu_i\}$ is the expected reward of the optimal arm $i^*$, and the expectation is taken w.r.t. the stochasticity of the policy $\mathfrak{U}$.

Notice that we adopt the concept of pseudo-regret as for standard bandits, unlike what is done by [22] [[22]], since our choice allows for a direct comparison with the vast prior work on delayed bandits.

In what follows, we cast the playlist recommendation problem, described in the introduction, in the TP-MAB setting.
[Playlist Recommendation]
At each round $t$, a new user enters the platform, which provides a playlist suggestion.

The different arms $i$ are the available playlists to suggest, each composed of $N$ songs.

Songs are characterized by $4$ listening levels (from “skipped” to “complete”), each associated with a different Bernoulli random variable representing the corresponding per-round reward.

The vector of realized per-round rewards of song $k \in [N]$ is $[x^i_{t,4(k-1)+1}, x^i_{t,4(k-1)+2}, x^i_{t,4(k-1)+3}, x^i_{t,4(k-1)+4}]$.

Each variable assumes a value of $1$ if the user reaches the corresponding level, and a value of $0$ if the user stops listening to the song before that level.

The cumulative reward $R^i_t$ for pulling arm $i$ at round $t$ is the sum of the rewards from the songs in the playlist, and the time span over which the platform observes the reward is $\Tmax = 4 N$.

We show that the TP-MAB problem has a lower-bound on the regret of the same order of the delayed-feedback bandit problem.

The rationale is that no better lower bound is possible as delayed-feedback MABs with a finite delay are a subclass of TP-MABs whose reward vector $\bm{x}^i_t$ has a single non-zero element for each $i \in \mathcal{A}$ and $t \in [T]$.

Most interestingly, the worst-case instance for the regret lower bound in the TP-MAB setting is the delayed-feedback bandit.[

All the proofs are deferred to Appendix B for space reasons. See <https://trovo.faculty.polimi.it/01papers/romano2022multi.pdf>.]
The regret of any uniformly efficient policy $\mathfrak{U}$ applied to the TP-MAB problem is bounded from below by:

\begin{equation}
\lim \inf_{T \rightarrow +\infty} \frac{\mathcal{R}_T(\mathfrak{U})}{\ln T} \geq \sum_{i:\mu_i < \mu^*} \frac{\Delta_i}{KL\left( \frac{\mu_i}{\overline{R}_{\max}}, \frac{\mu^*}{\overline{R}_{\max}} \right)},
\end{equation}

where $\Delta_i := \mu^* - \mu_i$ is the expected loss suffered by the learner if the arm $i$ is chosen instead of the optimal one $i^*$, $\overline{R}_{\max} := \max_{i \in [K]} \overline{R}^i$, and $KL(p,q)$ is the Kullback-Leibler divergence between Bernoulli r.v. with means $p$ and $q$.[
An uniformly efficient policy chooses the suboptimal arms on average $o(t^a)$ times ($0 < a < 1$) over $t$ rounds.]

Notice that the lower bound holds for general TP-MAB problems.

In the following section, we show that focusing on a broad subset of instances of practical interest, we can design algorithms with a better regret upper bound.

§ $\ALPHA$-SMOOTHNESS PROPERTY

From Theorem <ref>, we know that we cannot design algorithms with regret upper bounds better than those of the algorithms for the delayed-feedback bandit setting.

Nonetheless, in practice, collecting per-round rewards can provide useful information on the cumulative reward of an arm.

However, as already pointed out by [14] [[14]] for the standard delayed-feedback setting, zero rewards are ambiguous since they do not give any information on future rewards.

In the general setting, small per-round rewards observed in the first rounds after the pull are not much informative to bound the values of future ones.

To avoid this, we focus on those problems in which the maximum reward realized over a few rounds cannot exceed a fraction of the maximum reward $\overline{R}^i$.

Example of $\alpha$-smooth reward with $\step = 3$.

Let us consider $\alpha \in [\Tmax]$ s.t. $\alpha$ is a factor of $\Tmax$, i.e., $\frac{\Tmax}{\alpha} =: \step$ and $\step \in \mathbb{N}$.[
We assume $\alpha$ is a factor of $\Tmax$ for the sake of presentation.

The following results also hold for generic $\alpha \in [\Tmax]$.]

Let us define the vector $\bm{Z}^i_{t,\alpha} := \left[Z^i_{t,1}, \ldots , Z^i_{t,\alpha} \right]$ whose element $Z^i_{t,k}$ is the random variable corresponding to the sum of a set of consecutive per-round rewards of cardinality $\step$.

Formally, for every $k \in [\alpha]$:

\begin{equation}
Z^i_{t,k} := \sum_{j=(k-1)\step + 1}^{k \step} X^i_{t,j}.
\end{equation}

The support of $Z^i_{t,k}$ is denoted by $[\underline{Z}^i_{\alpha,k}, \overline{Z}^i_{\alpha,k}]$,
where $\underline{Z}^i_{\alpha,k} := \sum_{j=(k-1)\step + 1}^{k \step} \underline{X}_{j}^i$, and $\overline{Z}^i_{\alpha,k} := \sum_{j=(k-1)\step + 1}^{k \step} \overline{X}_{j}^i$.

Intuitively, the $\alpha$-smoothness property states that the elements in $\bm{Z}^i_{t,\alpha}$ are independent and that, when $\alpha > 1$, the maximum reward $\overline{R}^i$ of a pull cannot be realized in a single time span corresponding to a $Z^i_{t,k}$ element.

In the TP-MAB setting, for $\alpha \in [\Tmax]$, we say that the reward is $\alpha$-smooth if and only if $\frac{\Tmax}{\alpha} = \step$, with $\step \in \mathbb{N}$, and, for each $k \in [\alpha]$, the random variables $Z^i_{t,k}$ are independent and s.t. $\overline{Z}^i_{\alpha,k}=\overline{Z}^i_{\alpha} = \frac{\overline{R}^i}{\alpha}$.

An example of $\alpha$-smooth environment with $\phi = 3$ is presented in Figure <ref>, where colors denote the elements $z^i_{t,k}$ that are the realizations of the variables $Z^i_{t,k}$.

Consider the extreme values of parameter $\alpha$.

When $\alpha = 1$, the reward has no constraint on how it distributes over time.

This scenario includes the delayed-feedback bandit setting in which the cumulative reward provided by the arm pulled at $t$ is entirely collected at a single round (including the last possible round $t + \Tmax - 1$).

Note that, in this case, at each round before $t + \Tmax - 1$, the sum of the future per-round rewards is in the range $[0, \overline{R}^i]$.

Conversely, when $\alpha = \Tmax$, the vector of aggregated rewards coincides with the vector of per-round rewards, i.e., $\bm{Z}^i_{t,\Tmax} = \bm{X}^i_t$, and each per-round reward is at most $\overline{X}^i_j = \overline{R}^i / \Tmax$.

Thus, observing low rewards in the first rounds after the pull provides useful information on the actual cumulative reward.

In particular, after observing the first $n < \Tmax$ per-round rewards, we know that the cumulative reward achievable in the following rounds is in the range $[0, \frac{\Tmax-n}{\Tmax} \overline{R}^i]$.

This information dramatically reduces the uncertainty on the future rewards w.r.t. a setting without smooth rewards (e.g., $\alpha = 1$).

The $\alpha$-smoothness property characterizes those setting where not gaining much in the first rounds precludes the possibility of achieving the maximum possible reward over the entire interval.

Consider the playlist recommendation problem in Example <ref>.

Since the reward corresponding to a song is composed of $4$ Bernoulli variables and has a maximum of $\overline{Z}^i_{\alpha} = 4$, $\alpha$-smoothness holds with $\alpha = \frac{\overline{R}^i}{\overline{Z}^i_{\alpha}} = \frac{4N}{4} = N$.

Assuming $\alpha$-smoothness, we have a lower bound of:
The regret of any uniformly efficient policy $\mathfrak{U}$ applied to the TP-MAB problem with the $\alpha$-smoothness property is bounded from below by:

\begin{equation}
\lim \inf_{T \rightarrow +\infty} \frac{\mathcal{R}_T(\mathfrak{U})}{\ln T} \geq \sum_{i:\mu_i < \mu^*} \frac{\Delta_i}{\alpha KL\left( \frac{ \mu_i}{\overline{R}_{\max}}, \frac{\mu^*}{\overline{R}_{\max}} \right)}.
\end{equation}

We remark that this bound is tighter than the one provided in Theorem <ref> by a multiplicative factor of $1/\alpha$.

§ ALGORITHMS FOR THE TP-MAB SETTING

We propose two novel algorithms, namely Temporally-Partitioned rewards UCB with Fictitious Realizations () and Temporally-Partitioned rewards Element-Wise UCB (), for the TP-MAB problem, which aim at maximizing the cumulative reward and exploit the $\alpha$-smoothness property to do that.

From now on, we denote the two corresponding policies by $\mathfrak{U}_{\texttt{FR}}$ and $\mathfrak{U}_{\texttt{EW}}$, respectively.

§.§ The  Algorithm

[1]
$\textbf{Input}$: $\alpha \in [\Tmax]$, $\Tmax \in \mathbb{N}^*$
$t \in  \{1, \ldots, K \}$ init phase

Pull arm $i_t = t$
$t \in  \{K+1, \ldots, T \}$ loop phase
$i \in  \{1, \ldots, K \}$
Compute $\hat{R}^{i}_{t-1}$ and $c^i_{t-1}$ as in Eq.s (<ref>)-(<ref>)

$u^i_{t-1} \gets \hat{R}^{i}_{t-1} + c^i_{t-1} $
Pull arm $i_t = \arg \max_{i \in [K]}$ $u^i_{t-1}$
Observe $x^{i_h}_{h,t-h+1}$ for  $h \in \{t-\Tmax + 1, \ldots, t\}$

The pseudo-code of  is provided in Algorithm <ref>.

The rationale is to use the rewards coming from not fully-realized reward vectors by replacing the missing elements with fictitious realizations.

At round $t$, fictitious reward vectors are associated to each arm pulled in the time span $H:=\{t-\Tmax+1, \ldots, t-1\}$.

We denote them by $\tilde{\bm{x}}^i_h = [\tilde{x}^i_{h,1}, \ldots, \tilde{x}^i_{h,\Tmax}]$ with $h \in H$, where $\tilde{x}^i_{h,j} := x^i_{h,j}$, if $h + j \leq t$, and $\tilde{x}^i_{h,j} = 0$, if $h + j > t$.

The corresponding fictitious cumulative reward is $\tilde{r}^i_h := \sum_{j=1}^{\Tmax}\tilde{x}^i_{h,j}$.

The algorithm takes as input the smoothness $\alpha \in [\Tmax]$, and the maximum delay $\Tmax$.[

If these information are not available one should use $\alpha = 1$, meaning we are not assuming any structure over the reward, and use as $\Tmax$ the largest delay observed so far.]

During the initialization phase, all arms are pulled once (Line <ref>).

After that, at each round $t$, it computes the estimated expected reward for each arm $i$:

\begin{align} \label{eq:exprew1}
\hat{R}^{i}_{t-1} := \frac{1}{n^i_{t-1}} \left( \sum_{h=1}^{t-\Tmax} \hspace{-0.2cm} r^i_h \mathds{1}_{\{i_h = i\}} + \sum_{h \in H} \tilde{r}^i_h \mathds{1}_{\{i_h = i\}} \right),
\end{align}

where $n^i_{t-1} := \sum_{h=1}^{t-1} \mathds{1}_{\{i_h = i\}}$ is the number of times arm $i$ has been pulled by the policy up to round $t-1$, and the confidence interval:

\begin{equation} \label{eq:bound1}
c^i_{t-1} := \overline{R}^i \sqrt{\frac{2 \ln (t-1)}{\alpha n^i_{t-1}}} + \frac{\step(\alpha+1) \overline{R}^i}{2 n^i_{t-1}}.
\end{equation}

Finally, it pulls the arm with the largest upper confidence bound $u^i_{t-1}$ (Line <ref>), and observes its reward (Line <ref>).

We provide the following upper bound on the regret:
In the TP-MAB setting with $\alpha$-smooth reward, the pseudo-regret of  after $T$ rounds is:

\begin{align*}
\mathcal{R}_T(\mathfrak{U}_{\emph{\texttt{FR}}})  \leq &\sum_{i:\mu_i<\mu^*} \frac{4(\overline{R}^i)^2 \ln T}{\alpha \Delta_i} \mleft( 1 + \sqrt{1 + \frac{\alpha(\alpha + 1) \phi \Delta_i}{2 \overline{R}^i \ln T}} \mright) \\
&+  (\alpha+1) \step \sum_{i:\mu_i<\mu^*} \overline{R}^i + \mleft( 1 + \frac{\pi^2}{3} \mright) \sum_{i : \mu_i < \mu^*} \Delta_i.
\end{align*}

We observe that the dominant term in $T$ has the order of $\mathcal{O} \left( \sum_{i:\mu_i < \mu^*} \frac{ \overline{R}_{\max}^2 \ln T}{\alpha \Delta_i} \right)$, where $\overline{R}_{\max} = \max_i \overline{R}^i$.

When $\alpha = 1$, the upper bound scales as the one of classical MAB algorithms in stochastic settings.

Notice that the pseudo-regret indirectly depends on $\Tmax$ since $\overline{R}^i$ represents the cumulative reward obtained over $\Tmax$ rounds.

Let us compare this result with the one provided in Theorem <ref> for general TP-MAB problems.

Applying to Theorem <ref> the inequality
$KL(p,q) \leq \frac{(p-q)^2}{q(1-q)}$,
where for $p, q \in [0,1]$, derived using the fact that $\ln x \leq x - 1$, we get:

\begin{equation}
\lim \inf_{T \rightarrow +\infty} \frac{\mathcal{R}_T(\mathfrak{U})}{\ln T} \geq \sum_{i:\mu_i < \mu^*} \frac{\beta}{\Delta_i},
\end{equation}

where $\beta = \frac{\mu^*}{\overline{R}_{\max}} \mleft(1 - \frac{\mu^*}{\overline{R}_{\max}}\mright)$.

For $\alpha > 4(\overline{R}^i)^2/\beta$, the multiplicative factor in the dominant term of the upper bound provided in Theorem <ref> is better than that in the lower bound in Theorem <ref>.

This suggests that exploiting the $\alpha$-smoothness provides an improvement over the classical and delayed-feedback MABs.

§.§ The  Algorithm

[1]
$\textbf{Input}$: $\alpha \in [\Tmax]$, $\Tmax \in \mathbb{N}^*$
$t \in  \{1, \ldots, K \}$ init phase
Pull arm $i_t = t$
$t \in  \{K+1, \ldots, T\}$ loop phase
$i \in  \{1, \ldots, K\}$
$k \in  \{1, \ldots, \alpha\}$
Compute $\hat{Z}^{i}_{t-1, k}$ and $c^i_{t-1, k}$ as in Eq.s (<ref>)-(<ref>)

$u^i_{t-1} \gets \sum_{k=1}^{\alpha} \mleft(\hat{Z}^{i}_{t-1,k} + c^i_{t-1,k} \mright) $
Pull arm $i_t \in \arg \max_{i \in [K]}$ $u^i_{t-1}$
Observe $x^{i_h}_{h,t-h+1}$ for $h \in \{t-\Tmax + 1, \ldots, t\}$

The pseudo-code of  is provided in Algorithm <ref>.

The key idea is to compute an upper confidence bound for the average of each set of $k$-th realized aggregated rewards $z^i_{t,k}$ from arm $i$ and use them to build an upper bound on the overall average reward $R^i_t$.

It takes as input the smoothness parameter $\alpha$, and the maximum delay parameter $\Tmax$.

At first, it pulls each arm once (Line <ref>), while, in the following rounds, it computes the empirical mean:

\begin{equation} \label{eq:exprew2}
\hat{Z}^{i}_{t-1,k} := \frac{\sum_{h=1}^{t - k \step  } z^{i}_{h,k} \mathds{1}_{\{i_h = i\}}}{n^i_{t-1,k}},
\end{equation}

where $n^i_{t-1,k} := \sum_{h=1}^{t - k \step} \mathds{1}_{\{i_h = i\}}$ is the cardinality of the rewards observed up to round $t-1$ for the $k$-th element of $\bm{Z}^i_{t-1,\alpha}$, and the confidence bound:

\begin{equation} \label{eq:bound2}
c^i_{t-1,k} := \frac{\overline{R}^i}{\alpha}\sqrt{\frac{2 \ln (t-1)}{n^i_{t-1,k}}}.
\end{equation}

We remark that $\hat{Z}^{i}_{t-1, k} + c^i_{t-1, k}$ is an upper confidence bound for the $k$-th element of $\bm{Z}^i_{t-1,\alpha}$.

Finally, the algorithm computes the upper bound $u^i_{t-1}$, summing the bounds above (Line <ref>), selects the arm $i$ choosing the largest $u^i_{t-1}$ (Line <ref>), and observes its reward (Line <ref>).

We provide the following upper bound on the regret:
In the TP-MAB setting with $\alpha$-smooth reward, the pseudo-regret of  after $T$ rounds is:

\begin{align*}
\R_T(\mathfrak{U}_{\emph{\texttt{EW}}}) & \leq \hspace{-0.3cm} \sum_{i:\mu_i<\mu^*}
\frac{8(\overline{R}^i)^2\ln T}{\Delta_i} \hspace{-0.05cm} + \hspace{-0.05cm} \alpha\mleft(\step +\frac{\pi^2}{3}\mright) \hspace{-0.2cm} \sum_{i : \mu_i < \mu^*} \hspace{-0.3cm} \Delta_i.
\end{align*}

Focusing on the dominant term in $T$ of the regret bound, we do not have an explicit improvement over the classical and delayed-feedback MAB algorithms.

Therefore, in this case, the structure provided by the $\alpha$-smoothness seems not to affect the regret bound.

Hence, from an asymptotic point of view, there is not a clear advantage from having $\alpha$-smooth rewards.

However, the constant term is significantly smaller than that of  and allows  to be much more effective than  to tackle TP-MAB problems with a short time horizon.

§ EMPIRICAL EVALUATION

We compare  and  algorithms with the  algorithm by [2] [[2]] and the  algorithm by [12] [[12]] in $\alpha$-smooth TP-MAB environments.

Appendix A provides details on the adaptation of these two  state-of-the-art algorithms to the TP-MAB problem.

Notice that, for , we assume to immediately get the cumulative reward of a pull. Therefore, it represents a clairvoyant algorithm observing $R^i_t$ at round $t$.

We compare the algorithms in three settings: two synthetically-generated environments and a real-world playlist recommendation scenario.[

More details about the experiments are deferred to Appendix C.]

Setting #1.
At first, we evaluate the influence of the parameter $\alpha$.

We model $K = 10$ arms, whose maximum reward is s.t. $\overline{R}^i = 100 i$.

The reward is collected over $\Tmax = 100$ rounds, the smoothness parameter is $\alpha = 20$, and the aggregated rewards are s.t. $Z^i_{t,k} \sim \frac{\overline{R}^i}{\alpha} \textnormal{U}([0, 1])$, for each $k \in [\alpha]$.

We run the algorithms over a time horizon of $T = 10^5$ and average the results over $50$ independent runs.

In the results, ($\eta$) and ($\eta$) are s.t. the value of $\alpha$ taken as input is $\eta$, with $\eta \in \{5, 10, 20, 25, 50\}$.

Pseudo-regret over time for Experimental Setting #1.

Figure <ref> shows the pseudo-regret $\mathcal{R}_t(\mathfrak{U})$ over the time horizon and the vertical bars represent the $95\%$ confidence intervals for the mean value.

Let us focus on ($20$) and ($20$), for which $\eta$ is equal to the $\alpha$ of the environment.

($20$) provides better results than  over the entire time horizon, while ($20$) is better than  for $t > 10^4$ and better than ($20$) for $t > 2 \cdot 10^4$.

This suggests that ($20$) is more suitable for longer time horizons, and this behavior is confirmed by the asymptotic order of Theorem <ref>.

Notice that  obtains the reward as soon as an arm has been pulled, but it does not exploit the $\alpha$-smoothness property.

Vice versa, our algorithms incorporates this information that, in some specific situations, allows us to beat even the non-delayed baseline.

During rounds $t \in [1, 7000]$, the  algorithm outperforms , since, during the initial rounds, incomplete samples may be far different from the corresponding unseen realizations, and, therefore,  initially pulls the suboptimal arms more often than .

Nonetheless,  outperforms  over longer time horizons, as expected given the result in Theorem <ref>.

has a similar asymptotic behavior of those of  and , i.e., the regret curves becomes parallel after $\approx 4000$ rounds.

This is because the overall exploration term of the three algorithms is of the same order in $t$ and $\alpha$, and therefore the advantages of  are mainly experienced in the early stages of the learning process.

Summarily, for short-time horizons,  is preferable to , while  shows better performance over long periods.

Let us focus on the results obtained with ($\eta$).

Setting $\eta < \alpha$, i.e., underestimating the value of $\alpha$, provides worse results in terms of regret, while $\eta > \alpha$ seems to improve the performance of the algorithm without compromising the convergence properties.

This suggests that if the $\alpha$ parameter is unknown, one should use an optimistic (large) value in the algorithm.

Notice that the regret varies of $\approx 40\%$ w.r.t. the different versions of  changing the value of $\eta$, which suggests that  is strongly influenced by a mis-specification of the parameter $\eta$.

Focusing on ($\eta$), we have a behaviour similar to the one observed for ($\eta$), showing how larger values for $\eta$ provide better results.

Conversely, the performance of  present a lower variability by changing the parameter $\eta$, and the gap in terms of regret among the different versions of  is of $\approx 3\%$.

$\Tmax$     $\alpha$     $\mathcal{R}_T^{(\%)}(\mathfrak{U}_{\texttt{FR}})$     $\mathcal{R}_T^{(\%)}(\mathfrak{U}_{\texttt{EW}})$

100     10      68.06$\%$ (0.26$\%$)     86.03$\%$ (0.59$\%$)

200     20      95.42$\%$ (0.15$\%$)     80.38$\%$ (0.34$\%$)

100     50      50.84$\%$ (0.11$\%$)     85.36$\%$ (0.33$\%$)

200     100     81.55$\%$ (0.10$\%$)     78.70$\%$ (0.24$\%$)

$\mathcal{R}_T^{(\%)}(\mathfrak{U})$ for Experimental Setting #2.

Setting #2.
We study the behavior of our algorithms in settings with different maximum delay $\Tmax$ and smoothness $\alpha$.

The scenario is the same presented in Setting #$1$ except that the maximum reward for the arm $i$ is $\overline{R}^i = \Tmax \cdot i$.[

In Appendix C, we also report experiments in scenarios differing in how the aggregated rewards are distributed over the $\phi$ elements composing $Z^i_{t,k}$, which confirm what is shown in this section.

We evaluate the algorithms in terms of percentage of the regret w.r.t. the one provided by , whose policy is denoted by $\mathfrak{U}_{\texttt{D}}$, formally $\mathcal{R}_T^{(\%)}(\mathfrak{U}) := \mathcal{R}_T(\mathfrak{U}) / \mathcal{R}_T(\mathfrak{U}_{\texttt{D}}) \cdot 100$.

We average the results over $50$ independent experiments.

Table <ref> provides the values of $\mathcal{R}_T^{(\%)}(\mathfrak{U})$ for our algorithms ($95\%$ CI in brackets).

In all the scenarios, the proposed algorithms outperform the  algorithm, providing a regret smaller than $95.5\%$ of the  one.

Comparing the results with the same maximum delay $\Tmax$ we notice that a larger value for $\alpha$ provides better performance.

This was expected since larger values for $\alpha$ imply that the  and  algorithms can better exploit the reward structure.

By comparing the settings with maximum delay $\Tmax = 100$ and $\Tmax = 200$, the two algorithms behave in opposite ways: the performance of  improves by more than $6\%$, while the regret of  increases of more than $30\%$.

This is due to the fact that, with larger $\Tmax$,  shows its better behaviour for larger time horizons.

Spotify Setting.
We apply the TP-MAB approach to solve the user recommendation problem presented in Example <ref>, using a dataset by Spotify [4].

We select the $K = 6$ most played playlist as the arms to be recommended, and each time a playlist $i$ is selected, the corresponding reward realizations $\bm{x}^i_t$ for the first $N = 20$ songs is sampled from the listening sessions of that playlist contained in the dataset.

We recall that, in this setting, the maximum delay is $\Tmax = 4N = 80$, and the smoothness parameter is $\alpha = 20$.

More details on the setting and the distributions of the reward for each playlist are provided in Appendix C.

We average the results over $50$ independent runs.

56473 (805)

25367 (369)

55000 (951)

47368	(1289)

Pseudo-regret for the Spotify experimental setting.

Pseudo-regret over time for the Spotify setting.

Table <ref> shows that the  algorithm provides the best performance among the analysed algorithms, outperforming  thanks to the exploitation of the $\alpha$-smoothness property.

The regret over time in Figure <ref> shows that the  provides worse performance than  only for a limited amount of rounds ($t < 4000$).

This suggests that, in this specific scenario, the  algorithm represents a good candidate to provide playlist recommendations.

§ CONCLUSION AND FUTURE WORKS

This paper introduces the novel TP-MAB setting, which generalizes the delayed-feedback bandit setting with bounded delay.

First, we show that the lower bound of the TP-MAB problem is the same of that of the standard delayed MAB problem.

Then, we characterize a broad set of reward structures, by defining the $\alpha$-smoothness property, for which we provide a tighter lower bound.

We design the  and the  algorithms, suited for the TP-MAB setting, which exploit the partial rewards collected over time and the $\alpha$-smoothness property.

We show that the upper bounds on the regret for these algorithms are $\mathcal{O}(\ln T/\alpha)$ and $\mathcal{O}(\ln T)$, respectively.

Finally, we empirically show that our algorithms outperforms the state of the art over a wide range of settings generated from synthetic and real-world data.

An interesting future extension would be to consider generic functions regulating the relationship between the cumulative and delayed rewards.

[1]
Sakshi Arya and Yuhong Yang.
Randomized allocation with nonparametric estimation for contextual
multi-armed bandits with delayed rewards.
Statistics & Probability Letters, 164:108818, 2020.

[2]
Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.
Finite-time analysis of the multiarmed bandit problem.
Machine learning, 47(2-3):235–256, 2002.

[3]
Ilai Bistritz, Zhengyuan Zhou, Xi Chen, Nicholas Bambos, and Jose Blanchet.
Exp3 learning in adversarial bandits with delayed feedback.
NeurIPS, 2019.

[4]
Brian Brost, Rishabh Mehrotra, and Tristan Jehan.
The music streaming sessions dataset.
In WWW. ACM, 2019.

[5]
Sébastien Bubeck and Nicolò Cesa-Bianchi.
Regret analysis of stochastic and nonstochastic multi-armed bandit
Foundations and Trends in Machine Learning, 5(1):1–122, 2012.

[6]
Matteo Castiglioni, Alessandro Nuara, Giulia Romano, Giorgio Spadaro, Francesco
Trovò, and Nicola Gatti.
Safe online bid optimization with return-on-investment and budget
constraints subject to uncertainty.
arXiv preprint arXiv:2201.07139, 2022.

[7]
Semih Cayci, Atilla Eryilmaz, and Rayadurgam Srikant.
Learning to control renewal processes with bandit feedback.
Proceedings of the ACM on Measurement and Analysis of Computing
Systems, 3(2):1–32, 2019.

[8]
Leonardo Cella and Nicolò Cesa-Bianchi.
Stochastic bandits with delay-dependent payoffs.
In AISTATS, pages 1168–1177, 2020.

[9]
Nicolo Cesa-Bianchi, Claudio Gentile, and Yishay Mansour.
Nonstochastic bandits with composite anonymous feedback.
In COLT, pages 750–773, 2018.

[10]
Thomas Desautels, Andreas Krause, and Joel W. Burdick.
Parallelizing exploration-exploitation tradeoffs in gaussian process
bandit optimization.
Journal of Machine Learning Research, 15(119):4053–4103, 2014.

[11]
Miroslav Dudik, Daniel Hsu, Satyen Kale, Nikos Karampatziakis, John Langford,
Lev Reyzin, and Tong Zhang.
Efficient optimal learning for contextual bandits.
arXiv preprint arXiv:1106.2369, 2011.

[12]
Pooria Joulani, Andras Gyorgy, and Csaba Szepesvári.
Online learning under delayed feedback.
In ICML, pages 1453–1461, 2013.

[13]
Travis Mandel, Yun-En Liu, Emma Brunskill, and Zoran Popović.
The queue method: Handling delay, heuristics, prior data, and
evaluation in bandits.
In AAAI, volume 29, 2015.

[14]
Anne Gael Manegueu, Claire Vernade, Alexandra Carpentier, and Michal Valko.
Stochastic bandits with arm-dependent delays.
In ICML, pages 3348–3356, 2020.

[15]
Gergely Neu, András György, Csaba Szepesvari, and Andras Antos.
Online markov decision processes under bandit feedback.
IEEE Transactions on Automatic Control, 59(3):676–691, 2013.

[16]
Alessandro Nuara, Francesco Trovò, Nicola Gatti, and Marcello Restelli.
A combinatorial-bandit algorithm for the online joint bid/budget
optimization of pay-per-click advertising campaigns.
In AAAI, volume 32, 2018.

[17]
Alessandro Nuara, Francesco Trovò, Nicola Gatti, and Marcello Restelli.
Online joint bid/daily budget optimization of internet advertising
Artificial Intelligence, page 103663, 2022.

[18]
Ciara Pike-Burke, Shipra Agrawal, Csaba Szepesvari, and Steffen Grunewalder.
Bandits with delayed, aggregated anonymous feedback.
In ICML, pages 4105–4113, 2018.

[19]
Tobias Sommer Thune, Nicolò Cesa-Bianchi, and Yevgeny Seldin.
Nonstochastic multiarmed bandits with unrestricted delays.
In NeurIPS, 2019.

[20]
Francesco Trovò, Stefano Paladino, Marcello Restelli, and Nicola Gatti.
Improving multi-armed bandit algorithms in online pricing settings.
International Journal of Approximate Reasoning, 98:196–235,

[21]
Dirk van der Hoeven and Nicolò Cesa-Bianchi.
Nonstochastic bandits and experts with arm-dependent delays.
arXiv preprint arXiv:2111.01589, 2021.

[22]
Claire Vernade, Olivier Cappé, and Vianney Perchet.
Stochastic bandit models for delayed conversions.
In UAI, 2017.

[23]
Claire Vernade, Alexandra Carpentier, Tor Lattimore, Giovanni Zappella, Beyza
Ermis, and Michael Brueckner.
Linear bandits with stochastic delayed feedback.
In ICML, pages 9712–9721, 2020.

[24]
Claire Vernade, Andras Gyorgy, and Timothy Mann.
Non-stationary delayed bandits with intermediate observations.
In ICML, pages 9722–9732, 2020.

[25]
Zhengyuan Zhou, Renyuan Xu, and Jose Blanchet.
Learning in generalized linear contextual bandits with stochastic
In NeurIPS, volume 32, 2019.

Appendix of the Paper “Multi-Armed Bandit Problem with Temporally-Partitioned Rewards: When Partial Feedback Counts”

[1]
$t \in  \{1, \ldots, K\}$ init phase
Pull arm $i_t = t$
Observe the reward $r^{i_t}_t$ of the arm pulled at round $t$
$t \in  \{K+1, \ldots, T\}$ loop phase
$i \in  \{1, \ldots, K\}$
$\hat{R}^{i}_{t-1} \gets \frac{1}{n^i_{t-1}} \sum_{h=1}^{t-1}r^i_h \mathbbm{1}_{\{i_h = i\}}$
$c_{t-1}^i \gets \overline{R}^i\sqrt{\frac{2\ln t}{n^i_{t-1}}}$
$u^i_{t-1} \gets \hat{R}^{i}_{t-1} + c_{t-1}^i $
Pull arm $i_t = \argmax_{i \in [K]}$ $u^i_{t-1}$
Observe the reward $r^{i_t}_t$ of the arm pulled at round $t$

§ BASELINE ALGORITHMS DESCRIPTION

In this section, we report the details about the algorithms from the literature which we use as baselines in the experiments of Section <ref>.

In particular, we compare the performances of the proposed  and the  with those of the baselines , assuming to obtain all the rewards corresponding to the pull of arm $i_t$ at time $t$, and , which uses the realization of the pulls only when they are complete, i.e., with a constant delay of $\Tmax-1$.

§.§ Non-Delayed Feedback

We describe the version of the  algorithm, designed by [2] [[2]], in which the reward $r^{i_t}_t$ provided by pulling arm $i_t$ at round $t$ is observed by the learner at time $t$.

We recall that this algorithm cannot be run in a TP-MAB setting, unless we are in the degenerate case $\Tmax = 1$. It rather represents a clairvoyant algorithm having the information of the rewards $r^i_t$ without any delay.

We denote its policy by $\mathfrak{U}_{{\texttt{UCB1}}}$.

The pseudo-code of the  algorithm is reported in Algorithm <ref>.

During the initialization phase, all the arms are pulled once (Line <ref>).

Subsequently, at each round $t$, the learner computes the empirical mean of the cumulative rewards $\hat{R}^{i}_{t-1}$ collected up to round $t - 1$ (Line <ref>), where we denote by $n^i_{t-1} := \frac{1}{n_i}\sum_{h=1}^{t-1} \mathbbm{1}_{\{i_h = i\}}$ the number of times the arm $i$ has been pulled up to round $t - 1$, and the the confidence interval $c^i_{t-1}$ (Line <ref>).

Finally, the learner pulls the arm with the largest upper confidence bound $u^i_{t-1}$ (Line <ref>), and observes the reward $r^{i_t}_t$ (Line <ref>).

We provide the following upper bound on the regret of the  algorithm (see the proof by [2]):
The pseudo-regret of  after $T \in \mathbb{N}^*$ rounds on a MAB problem with $r^i_t$ rewards is:

\begin{equation*}
\mathcal{R}_T(\mathfrak{U}_{\emph{\texttt{UCB1}}}) \leq \sum_{i:\mu_i<\mu^*} \frac{8 ( \overline{R}^i)^2 \ln{T}}{\Delta_i} + \mleft(1 + \frac{\pi^2}{3}\mright)\sum_{i:\mu_i<\mu^*} \Delta_i.
\end{equation*}

§.§ Delayed Feedback

We show how to apply the  algorithm, provided by [12] [[12]] and originally designed for the Delayed-MAB setting, to the TP-MAB setting.

In the TP-MAB problem, the realization of the cumulative reward $r^i_t$ is observed after $\Tmax - 1$ rounds from the pull of the arm.

As a consequence, one always waits for $\Tmax - 1$ rounds before collecting the reward from a pull.

This approach, corresponds to a delayed-feedback MAB setting in which the delay is known and deterministic.

After such a delay, the learner updates the policy $\mathfrak{U}_{{\texttt{D-UCB1}}}$ of  with the value of the cumulative reward.

The pseudo-code of the  algorithm applied to a generic TP-MAB setting is reported in Algorithm <ref>.

During the initialization phase, all arms are pulled in a round robin fashion until at least one reward is collected (Line <ref>).

Subsequently, at each round $t$, the learner computes the empirical mean $\hat{R}^{i}_{t-1}$ of the cumulative rewards collected up to round $t-1$ (Line <ref>), where $s^i_{t-1} := \sum_{h=1}^{t-\Tmax} \mathbbm{1}_{\{i_h = i\}}$ is the number of complete reward observed so far for arm $i$, and the confidence interval $c^i_{t-1}$ (Line <ref>).

Finally, the learner pulls the arm with the largest upper confidence bound $u^i_{t-1}$ (Line <ref>), and observes the reward corresponding to the pull occurred at round $t - \Tmax + 1$ (Line <ref>).

When no sample is available for an arm $i$ its upper bound is set to $+\infty$.

[1]
$t \in  \{1, \ldots, \Tmax\}$ init phase
Pull arm $i_t = ((t-1)\mod{K})+1$

$t \in  \{\Tmax+1, \ldots, T\}$ loop phase
$i \in  \{1, \ldots, K\}$
$\hat{R}^i_{t-1} \gets \frac{1}{s^i_{t-1}}\sum_{h=1}^{t-\Tmax} r^i_{h} \mathbbm{1}_{\{i_h = i\}}$
$c^i_{t-1} \gets \overline{R}^i\sqrt{\frac{2 \ln (t-1)}{s^i_{t-1}}}$
$u^i_{t-1} \gets \hat{R}^i_{t-1} + c^i_{t-1} $
Pull arm $i_t = \argmax_{i \in [K]}$ $u^i_{t-1}$
Observe reward $r^{i_{t-\Tmax+1}}_{t-\Tmax+1}$ of the arms pulled at round ${t-\Tmax+1}$

We provide the following upper bound on the regret of the  algorithm (see [12] [[12]]).

The pseudo-regret of  after $T \in \mathbb{N}^*$ rounds in the TP-MAB setting is:

\begin{equation}
\mathcal{R}_T(\mathfrak{U}_{\emph{\texttt{D-UCB1}}}) \le \sum_{i:\mu_i<\mu^*} \frac{8(\overline{R}^i)^2\ln{T}}{\Delta_i} + \mleft(1 + \frac{\pi^2}{3} + \Tmax \mright)\sum_{i:\mu_i < \mu^*} \Delta_i.
\end{equation}

The theorem follows from Theorem $7$ by [12], where the expected value of the maximum number of missing feedback of arm $i$ during the first $t$ time steps is $\mathbb{E}[G^*_{i,t}] < \Tmax$, where $G^*_{i,t}$ is the maximum number of missing feedbacks during the first $t$ rounds for arm $i$.

§.§ Theoretical Results Summary

Finally, we provide a table summarizing the results known in the literature and provided in this paper.
Table <ref> reports the lower and upper bounds on the regret for different algorithms and settings. Notice that the lower bound results hold for $T \rightarrow +\infty$. Moreover, in Table <ref>, we denote $\frac{8 ( \overline{R}^i)^2}{\Delta_i}$ by $C_i$ and $\sum_{i:\mu_i<\mu^*}$ by $\sum_{i}$.

The assumption is that the instantaneous (for the MAB and Delayed-MAB settings) and cumulative (for the TP-MAB setting) rewards have support in $[0, \overline{R}^i]$. Moreover, in the Delayed-MAB setting, the maximum stochastic delay is $\tau_{\max}$
The novel results have been highlighted in blue.
does not have guarantees in the Delayed-MAB and TP-MAB settings since it has been developed for a more restrictive scenario, i.e., $\tau_{\max} = 1$.

The results related to the proposed algorithms, i.e.,  and , for the MAB setting have been derived fixing $\tau_{\max} = 1$ and $\alpha = 1$ in the corresponding theorems. The results of the Delayed-MAB setting have been derived fixing $\alpha = 1$.

We remark that  in the MAB setting has the same asymptotic order of upper bound of , while the upper bound of  reduces exactly to the one of  in this setting.

Summary of the known theoretical results (in black) and original contributions provided in this paper (in blue).

MAB     Delayed-MAB      TP-MAB with $\alpha$-smoothness

Lower bound      $\sum_{i} \frac{\Delta_i \ln T }{KL\left( \frac{\mu_i}{\overline{R}_{\max}}, \frac{\mu^*}{\overline{R}_{\max}} \right)}$       $\sum_{i} \frac{\Delta_i \ln T }{KL\left( \frac{\mu_i}{\overline{R}_{\max}}, \frac{\mu^*}{\overline{R}_{\max}} \right)}$      $\sum_{i} \frac{\Delta_i \ln T}{ \alpha KL\left( \frac{\mu_i}{\overline{R}_{\max}}, \frac{\mu^*}{\overline{R}_{\max}} \right)}$

$\sum_{i} C_i \ln{T} + \mleft(1 + \frac{\pi^2}{3}\mright)\sum_{i} \Delta_i$     N.a.     N.a.

$\sum_{i} C_i \ln{T} + \mleft(1 + \frac{\pi^2}{3} \mright)\sum_{i} \Delta_i$      $\sum_{i} C_i \ln{T} + \mleft(1 + \frac{\pi^2}{3} + \Tmax \mright)\sum_{i} \Delta_i$      $\sum_{i} C_i \ln{T} + \mleft(1 + \frac{\pi^2}{3} + \Tmax \mright)\sum_{i} \Delta_i$

$\sum_{i} \frac{C_i}{2} \ln T \mleft( 1 + \sqrt{1 + \frac{2\Delta_i}{\overline{R}^i \ln T}} \mright) +  2 \sum_{i} \overline{R}^i + \mleft( 1 + \frac{\pi^2}{3} \mright) \sum_{i} \Delta_i$      $\sum_{i} \frac{C_i}{2}  \ln T \mleft( 1 + \sqrt{1 + \frac{2\Delta_i}{\overline{R}^i \ln T}} \mright) +  2 \tau_{\max} \sum_{i} \overline{R}^i + \mleft( 1 + \frac{\pi^2}{3} \mright) \sum_{i} \Delta_i$      $\sum_{i} \frac{C_i}{2\alpha} \ln T \mleft( 1 + \sqrt{1 + \frac{\alpha(\alpha + 1) \Delta_i}{2 \overline{R}^i \ln T}} \mright) +  (\alpha+1) \step \sum_{i} \overline{R}^i + \mleft( 1 + \frac{\pi^2}{3} \mright) \sum_{i} \Delta_i$

$\sum_{i} C_i  \ln T + \mleft(1 + \frac{\pi^2}{3}\mright) \sum_{i} \Delta_i$      $ \sum_{i} C_i  \ln T + \mleft(\tau_{\max} +\frac{\pi^2}{3}\mright) \sum_{i} \Delta_i$      $\sum_{i} C_i  \ln T + \alpha \mleft(\step +\frac{\pi^2}{3}\mright) \sum_{i} \Delta_i$

§ OMITTED PROOFS

At first, notice that learning the optimal arm in a TP-MAB problem $\mathcal{P}$ for rewards $R^i_t$ taking values over a generic finite domain $[0, \overline{R}^i]$, having range $\overline{R}^i$, is equivalent to the problem of learning in a TP-MAB problem $\mathcal{P}'$ with reward $\frac{R^i_t}{\overline{R}_{\max}}$ having domain $[0, 1]$.

Indeed, from a learning perspective, distinguish between two arms in the first setting requires the same sample complexity of distinguish between two arms in the second one.

The expected reward of the $i$-th arm of the $\mathcal{P}'$ problem is $(\mu_i)' = \frac{\mu_i}{\overline{R}_{\max}}$ and the one corresponding to the optimal arm is $(\mu^*)' = \frac{\mu^*}{\overline{R}_{\max}}$.

Let us consider for each problem $\mathcal{P}$ in the class of TP-MAB problems, its corresponding $\mathcal{P}'$ one.

For each $\mathcal{P}'$, we build a corresponding Delayed-MAB equivalent problem, by delaying all the intermediate rewards corresponding to a pull at round $t$ to the round $t+\Tmax-1$.

Therefore, using the results on the lower bound of the Delayed-MAB problems provided by [22] [[22]] (Lemma $15$) we have that:

\begin{equation}
\lim \inf_{T \rightarrow +\infty} \frac{\mathbb{E}[N_i(T)]}{\log(T)} \geq \frac{1}{KL\left( \frac{\mu_i}{\overline{R}_{\max}}, \frac{\mu^*}{\overline{R}_{\max}} \right)},
\end{equation}

where $\mathbb{E}[N_i(T)]$ is the expected number of times an arm $i$ is selected over a time horizon of $T$ by the policy $\mathfrak{U}$.

Due to the equivalence depicted above, this result holds also for the original problems $\mathcal{P}$ in the class of TP-MAB problems.

From the fact that $\mathcal{R}_T(\mathfrak{U}) = \Delta_i \mathbb{E}[N_i(T)]$ and summing over the suboptimal arms, i.e., $i \neq i^*$, we get the theorem statement.

The proof follows the steps provided for Theorem $2.2$ in the work by [5] [[5]] and generalize them to the setting in which multiple rewards, i.e., $\alpha$, are earned by a single arm pull.

Let us define an auxiliary MAB setting in which:

* only two arms with expected value $\mu_1$ and $\mu_2$, with $\mu_2 < \mu_1 <1$;

* all the arm have maximum reward equal to $R^i_t = \overline{R}_{\max}$;

* the reward $Z^i_{t,k}$ are i.i.d. over $k \in \{1, \ldots, \alpha\}$, meaning that the expected value of each of the element is $\frac{\mu_i}{\alpha}$;

* the reward are $Z^i_{t,k} \in \{0, \frac{\overline{R}_{\max}}{\alpha} \}$, i.e., the reward are Bernoulli scaled by a factor $\frac{\overline{R}_{\max}}{\alpha}$;

* pulling an arm at time $t$ provides $\alpha$ reward for the arm $\{Z^i_{t,1}, \ldots, Z^i_{t,\alpha}\}$, all observed by the learner at the time of the pull.

Let us remark that determining the optimality of an arm in this problem is no harder than the one in which the reward is spread over the period $\{t, \ldots, t + \Tmax -1\}$.
Therefore, the derivation of a lower bound for this problem would also provide a lower bound for the original TP-MAB setting with $\alpha$-smoothness.
Moreover, let us recall that learning in a problem where the reward are scaled by a factor $\frac{\overline{R}_{\max}}{\alpha}$, similarly to what has been done in Theorem <ref>, does not change the complexity of learning.
From now on, we will consider as expected value of the two arms $\mu_{Z_1} := \frac{\mu_1}{\overline{R}_{\max}}$ and $\mu_{Z_2} := \frac{\mu_2}{\overline{R}_{\max}}$.
Therefore, to compute the expected value of number of times an algorithm pulls the suboptimal arm $\mathbb{E}[N_2(T)]$ we can also use the scaled rewards.
In what follows, we prove that the lower bound for the auxiliary problem for any uniformly efficient policy $\mathfrak{U}$.

Overall proof idea

Let us consider a second instance of the above defined MAB such that arm $2$ is optimal and $\mu_{Z_1} < \mu'_{Z_2} < 1$.
We refer to it as the modified bandit.
Let $\varepsilon > 0$, since $x \mapsto KL(\mu_{Z_2},x)$ is continuous one can find $\mu'_{Z_2} \in (\mu_{Z_1},1)$ such that:

\begin{align}
KL\mleft( \mu_{Z_2}, \mu'_{Z_2} \mright) \leq (1 + \varepsilon) KL(\mu_{Z_2},\mu_{Z_1}). \label{link}
\end{align}

In what follows, we use the notation $\mathbb{E}'$, $\mathbb{P}'$ to denote the expected value and probability computed in the second bandit instance. The goal is to compare the behavior of the forecaster on the initial and modified bandits.
The idea of the proof is to show that, with a big enough probability, the forecaster is not able to distinguish between the two problems.
Then, using the fact that the forecaster is uniformly efficient by hypothesis, we show that the algorithm does not make too many mistake on the modified bandit and, in particular, provide a lower bound on the number of times the optimal arm is played.
This reasoning implies a lower bound on the number of times the suboptimal arm $2$ is played in the initial problem.

First step: $\mathbb{P}(C_t) = o(1)$

Let us define, for $s \in \{1, \ldots, t\}$, the empirical estimate of $KL\mleft( \mu_{Z_2}, \mu'_{Z_2} \mright)$ at round $t$ when the arm $2$ is pulled $s$ times:

\begin{align}
\widehat{KL}_{\alpha s} := \sum_{n = 1}^{s} \sum_{k=1}^\alpha \ln \frac{\mu_{Z_2} Z^2_{n,k} + (1-\mu_{Z_2})(1-Z^2_{n,k})}{\mu'_{Z_2} Z^2_{n,k} + (1-\mu'_{Z_2})(1-Z^2_{n,k})}.
\end{align}

We introduce the following event linking the behavior of the forecaster on the initial and modified bandits:

\begin{align}
C_t := \mleft\{ \alpha N_2(t) < f_t \quad \textnormal{and} \quad  \widehat{KL}_{\alpha N_2(t)} \leq \mleft( 1 - \varepsilon/2 \mright) \ln t \mright\},
\end{align}

where $f_t = \frac{1- \varepsilon}{KL(\mu_{Z_2},\mu'_{Z_2})} \ln t$.
Following the proof of Theorem $2.2$ from [5] [[5]], we have:

\begin{equation} \label{eq:measurechange}
\mathbb{P}'(C_t) = \mathbb{E}[ 1_{C_t} \exp{\mleft(- \widehat{KL}_{\alpha N_2(t)}\mright)  } ] \geq e^{- (1 - \varepsilon/2) \ln t} \mathbb{P}(C_t),
\end{equation}

where we used the change of measure identity for the first equality and use the fact that $\widehat{KL}_{\alpha N_2(t)} \leq \mleft( 1 - \varepsilon/2 \mright) \ln t$ in $C_t$.[For any event $A$ in the $\sigma$-algebra generated by $\{Z^2_{n,k} \}_{n \in \{1, \ldots, s\}, k \in \{1, \ldots, \alpha\}}$ holds that $\mathbb{P}'(A) =  \mathbb{E} \mleft[ 1_{A} \exp{\mleft(- \widehat{KL}_{\alpha N_2(t)}\mright)} \mright]$.]
Combining Equation (<ref>), the definition of $C_t$, and using the Markov's inequality, we have:

\begin{align}
\mathbb{P}(C_t) \leq t^{(1-\varepsilon/2)} \mathbb{P}'(C_t) \leq t^{(1-\varepsilon/2)} \mathbb{P}'(\alpha N_2(t) < f_t) \leq t^{(1-\varepsilon/2)} \frac{\mathbb{E}' \left[t-N_2(t)\right]}{t-f_t/\alpha} = o(1),
\end{align}

where with $o(1)$ we denote a quantity whose limit for $t \rightarrow +\infty$ is $0$ and we used the fact that the policy $\mathfrak{U}$ is uniformly efficient, i.e., $\mathbb{E}'[T_2(t)] = o(t^\beta)$ with $\beta < 1$.

Second step: $\mathbb{P}(\alpha N_2(t) \leq f_t) = o(1)$

Using the Third step of the proof of Theorem $2.2$ from [5] [[5]], we get:

\begin{equation}
o(1) = \mathbb{P}(C_t) \leq \mathbb{P} \left( \underbrace{\alpha T_2(t) < f_t}_{E_1} \wedge \underbrace{\frac{KL(\mu_{Z_2}, \mu'_{Z_2})}{(1 - \varepsilon) \ln t} \max_{s < f_t/\alpha} \widehat{KL}_{\alpha s} \leq \frac{1 - \varepsilon/2}{1 - \varepsilon} KL(\mu_{Z_2}, \mu'_{Z_2})}_{E_2} \right).
\end{equation}

Using the strong law of large numbers the event $E_2$ is s.t. $\lim_{t \rightarrow +\infty} \mathbb{P}(E_2) =1$, we infer that $\mathbb{P}(E_1) = \mathbb{P}(\alpha N_2(t) < f_t) = o(1)$, and that for $t \rightarrow + \infty$ we have $\mathbb{E}[N_2(t)] > f_t/\alpha$.

Final step

Using Equation (<ref>) we have that, for $t \rightarrow + \infty$:

\begin{align}
\mathbb{E}[N_2(t)] > f_t / \alpha = \frac{1- \varepsilon}{\alpha KL(\mu_{Z_2},\mu'_{Z_2})} \ln t \geq \frac{1- \varepsilon}{\alpha (1 + \varepsilon) KL(\mu_{Z_2},\mu_{Z_1})} \ln t,
\end{align}

where the theorem statement follows from the arbitrarity of the value of $\varepsilon$, substituting $\mu_{Z_1}$ with $\frac{\mu^*}{\overline{R}_{\max}}$ and $\mu_{Z_2}$ with $\frac{\mu_2}{\overline{R}_{\max}}$, and summing over all the suboptimal arms.

Let us define the true empirical mean of the cumulative reward of arm $i$ computed over $n^i_{t}$ samples as follows:

\begin{equation*}
\hat{R}^{i,\textnormal{true}}_{t} := \frac{1}{n^i_{t}} \sum_{h=1}^{t} r^i_h \mathbbm{1}_{\{i_h = i\}}.
\end{equation*}

We aim to bound the difference between $\hat{R}^{i,\textnormal{true}}_{t}$ and the approximated empirical mean of the cumulative reward $\hat{R}^i_{t}$ from arm $i$ computed over $n^i_{t}$ samples as in the  algorithm.

Formally, we have:

\begin{align}
\hat{R}^{i,\textnormal{true}}_{t} - \hat{R}^{i}_{t} &= \frac{1}{n^i_{t}} \sum_{h=1}^{t} \sum_{j=1}^{\Tmax} \mleft(x^i_{h,j} - \tilde{x}^i_{h,j}\mright) \mathbbm{1}_{\{i_h = i\}} \leq \frac{1}{n^i_{t}} \sum_{h=1}^{t} \sum_{j=1}^{\Tmax} \mleft(x^i_{h,j} - \tilde{x}^i_{h,j}\mright) \\
& = \frac{1}{n^i_{t}} \sum_{h=\max\{1,t-\Tmax+2\}}^{t} \sum_{j=t-h+2}^{\Tmax} x^i_{h,j} \label{eq:pos}\\
& \leq \frac{1}{n^i_{t}} \sum_{j=1}^\alpha \step j \frac{\overline{R}^i}{\alpha} \label{eq:bousmo}\\
& = \frac{\phi}{n^i_{t}} \frac{\overline{R}^i}{\alpha} \sum_{j=1}^{\alpha} j = \frac{\phi}{n^i_{t}} \frac{\overline{R}^i}{\alpha} \frac{\alpha(\alpha+1)}{2} =
\frac{\overline{R}^i(\alpha+1) \step}{2 n^i_{t}},
\end{align}

where, Equation (<ref>) is due to the fact that $\underline{R}^i = 0$ for each $i \in [K]$, and the inequality in Equation (<ref>) is due to the $\alpha$-smoothness of the environment.

Following the proof of Theorem $1$ by [2] [[2]], we bound the expected number of time a suboptimal arm is pulled as follows:

\begin{equation} \label{eq:subopt}
\mathbb{E}[N_i(t)] \le \ell + \sum_{t=1}^{\infty}\sum_{s=1}^{t-1}\sum_{s_i=\ell}^{t-1} \mathbb{P} \mleft\{\mleft(\hat{R}^{*}_{t,s} + c_{t,s}^*\mright) \le \mleft(\hat{R}^{i}_{t,s_i} + c_{t,s_i}^i\mright) \mright\},
\end{equation}

where $\hat{R}^{*}_{t,s}$ and $c_{t,s}^*$ are the empirical mean computed as in the  algorithm and the confidence bound, respectively, of the optimal arm $i^*$ in the case $s$ pulls occurred in the first $t$ rounds, and, $\hat{R}^{i}_{t,s_i}$ and $c_{t,s_i}^i$ are the empirical mean computed as in the  algorithm and the confidence bound, respectively, of the arm $i$ in the case $s_i$ pulls occurred in the first $t$ rounds.

Equation (<ref>) implies that at least one of the following holds:

\begin{align}
&\hat{R}^{*}_{t,s} \leq \mu^* - c_{t,s}^*, \label{eq:optisub}\\
&\hat{R}^{i}_{t,s_i} \geq \mu_i + c_{t,s_i}^i, \label{eq:suboptover}\\
&\mu^* < \mu_i + 2c_{t,s_i}^i. \label{eq:ineq_false}
\end{align}

Let us focus on Equation (<ref>).

We have that:

\begin{align}
&\mathbb{P} \mleft(\hat{R}^{*}_{t,s} - \mu^{*} \leq - c_{t,s}^* \mright)  = \mathbb{P}\mleft(\hat{R}^{*,\textnormal{true}}_{t,s} - \mu^* \leq - c_{t,s}^* + \hat{R}^{*,\textnormal{true}}_{t,s} - \hat{R}^{*}_{t,s} \mright) \\
& \leq \mathbb{P}\mleft(\hat{R}^{*,\textnormal{true}}_{t,s} - \mu^* \leq - c_{t,s}^* + \frac{\overline{R}^i(\alpha+1) \step}{2 s} \mright) = \mathbb{P}\mleft(\hat{R}^{*,\textnormal{true}}_{t,s} - \mu^* \leq -\overline{R}^* \sqrt{\frac{2\ln t}{\alpha s}} \mright) \\
& \leq \exp \left\{ \frac{ 2 \mleft( \overline{R}^* \sqrt{\frac{2\ln t}{\alpha s}} \mright)^2 s^2}{\sum_{l = 1}^{\alpha s} \mleft(\frac{\overline{R}^*}{\alpha}\mright)^2} \right\} \leq e^{- 4 \ln t} \leq t^{-4}, \label{eq:hoe1}
\end{align}

where $c^*_{t,s} := \overline{R}^* \sqrt{\frac{2 \ln (t)}{\alpha s}} + \frac{ \overline{R}^i(\alpha+1)\step}{2 s}$, $\overline{R}^* := \overline{R}^{i^*}$, $\hat{R}^{*,\textnormal{true}}_{t,s}$ is the empirical mean of the optimal arm $i^*$ in the case $s$ pulls occurred in the first $t$ rounds, and we use the Hoeffding inequality in Equation (<ref>).

Similarly, Equation (<ref>) is bounded by:

\begin{align}
&\mathbb{P} \mleft(\hat{R}^{i}_{t,s_i} - \mu_{i} \geq c_{t,s_i}^i \mright) \leq \mathbb{P}\mleft(\hat{R}^{i,\textnormal{true}}_{t,s} - \mu_{i} \geq \overline{R}^i \sqrt{\frac{2\ln t}{\alpha s_i}} \mright) \\
& \leq e^{-4\ln t}=t^{-4}, \label{eq:hoe2}
\end{align}

where we used the fact that $\hat{R}^{i,\textnormal{true}}_{t,s_i} \geq \hat{R}^{i}_{t,s}$ by construction of the latter, and we used the Hoeffding inequality to derive Equation (<ref>).

\begin{equation} \label{eq:ell}
\ell := \mleft \lceil \frac{\overline{R}^i(\alpha+1)\phi}{\Delta_i} + \frac{4(\overline{R}^i)^2 \ln t}{\alpha \Delta_i^2} \mleft(1 + \sqrt{1+\frac{\alpha(\alpha+1)\phi\Delta_i}{2\overline{R}^i \ln t}}\mright) \mright\rceil.
\end{equation}

We have that the following holds:

\begin{align*}
&\mu^* \geq \mu_i + 2c_{t,s}^i \\
&\Delta_i \geq 2 \mleft(\overline{R}^i\sqrt{\frac{2 \ln t}{\alpha s_i}} + \step \frac{\overline{R}^i (\alpha+1)}{2 s_i} \mright) \\
&s_i^2 \mleft(\frac{\Delta_i^2}{4}\mright) - 2s_i \mleft(\frac{\Delta_i\overline{R}^i(\alpha+1)}{4} \step + \frac{(\overline{R}^i)^2 \ln t}{\alpha}\mright) + \step^2 \frac{(\overline{R}^i)^2 (\alpha+1)^2}{4} \geq 0 \\
& s_i \geq \frac{4}{\Delta_i^2} \mleft(\frac{\Delta_i\overline{R}^i(\alpha+1)}{4}\step + \frac{(\overline{R}^i)^2\ln t}{\alpha} + \sqrt{ \frac{(\overline{R}^i)^4 \ln^2 t}{\alpha^2} + \frac{\Delta_i (\overline{R}^i)^3 (\alpha+1)\phi \ln t}{2 \alpha}} \mright)\\
& s_i \geq \frac{\overline{R}^i(\alpha+1)}{\Delta_i}\step + \frac{4(\overline{R}^i)^2 \ln t}{\Delta_i^2\alpha} \mleft(1 + \sqrt{1+ \frac{\Delta_i \alpha(\alpha+1)\phi}{2\overline{R}^i \ln t}}\mright),
\end{align*}

and, therefore, for $s_i \ge \ell$ the inequality in Equation (<ref>) is always false.

Finally, summing up the results derived above and using $\ell$ as defined in Equation (<ref>), we have:

\begin{align}
& \mathbb{E}[N_i(t)] \leq \mleft\lceil \frac{\overline{R}^i(\alpha+1)}{\Delta_i} \step + \frac{4(\overline{R}^i)^2 \ln t}{\alpha \Delta_i^2} \mleft(1 + \sqrt{1+\frac{\alpha(\alpha+1)\phi\Delta_i}{2\overline{R}^i \ln t}}\mright) \mright\rceil \\
& + \sum_{t=1}^{\infty}\sum_{s=1}^{t-1}\sum_{s_i=\ell}^{t-1} \left[ \mathbb{P} \left( \hat{R}^{*}_{t,s} - \mu^* \leq - c_{t,s}^* \right) + \mathbb{P} \left( \hat{R}^{i}_{t,s_i} -\mu_i \geq c_{t,s_i}^i \right) \right]\\
& \leq 1 + \frac{\overline{R}^i(\alpha+1)}{\Delta_i} \step + \frac{4(\overline{R}^i)^2 \ln t}{\alpha \Delta_i^2} \mleft(1 + \sqrt{1+\frac{\alpha(\alpha+1)\phi\Delta_i}{2\overline{R}^i \ln t}}\mright) + 1 + \sum_{t=1}^{\infty}\sum_{s=1}^{t-1}\sum_{s_i=\ell}^{t-1} 2 t^{-4} \\
& \leq \frac{\overline{R}^i(\alpha+1)}{\Delta_i}\step + \frac{4(\overline{R}^i)^2 \ln t}{\alpha \Delta_i^2} \mleft(1 + \sqrt{1+\frac{\alpha(\alpha+1)\phi\Delta_i}{2\overline{R}^i \ln t}}\mright) + 1 + \frac{\pi^2}{3}.
\end{align}

The theorem statement follows by the fact that $\mathcal{R}_T(\mathfrak{U}_{{\texttt{FR}}}) = \sum_{i : \mu_i < \mu^*} \Delta_i \mathbb{E}[N_i(T)]$.

Following the same proof strategy of Theorem <ref>, we want to bound the expected value of the number of pulls of suboptimal arms:

\begin{equation} \label{eq:probtot}
\mathbb{E}[N_i(t)] \leq l + \sum_{t=1}^{\infty}\sum_{s=1}^{t-1} \sum_{s_i=l}^{t-1} \mathbb{P} \mleft( \sum_{k=1}^{\alpha}(\hat{Z}^*_{t,k,s} + c^*_{t,k,s}) \leq \sum_{k=1}^{\alpha}(\hat{Z}^i_{t,k,s_i} + c^i_{t,k,s_i}) \mright),
\end{equation}

where $\hat{Z}^*_{t,k,s}$ and $c^*_{t,k,s}$ are the empirical mean computed as in the  algorithm and the confidence bound, respectively, of the optimal arm $i^*$ in the case $s$ pulls occurred in the first $t$ rounds, and, $\hat{Z}^i_{t,k,s_i}$ and $c^i_{t,k,s_i}$ are the empirical mean computed as in the  algorithm and the confidence bound, respectively, of the arm $i$ in the case $s_i$ pulls occurred in the first $t$ rounds.

Notice that in this case the number of samples collected from each one of the $\alpha$ aggregated rewards are $\leq s$ and $\leq s_i$, respectively.

Moreover, for values of $l > \Tmax$ the quantities regarding the suboptimal arm are estimated using at least one sample, e.g., $0 < n^i_{t,k,s} < s_i$.

Conversely, for $s \leq \Tmax$ the optimal arm might have no sample available to estimate the expected value and the bound.

However, since the values of the upper confidence bound is set $+\infty$ if no sample is collected, the probability that it is smaller than the one of a suboptimal arm is $0$, (i.e., $\mathbb{P} \mleft( \sum_{k=1}^{\alpha}(\hat{Z}^*_{t,k,s} + c^*_{t,k,s}) \leq \sum_{k=1}^{\alpha}(\hat{Z}^i_{t,k,s_i} + c^i_{t,k,s_i}) \mright) = 0$). As a consequence, the cases in which no sample is available for the optimal bound can be disregarded.

The condition above is satisfied if at least one of the following $2\alpha+1$ inequalities holds:

\begin{align}
&\hat{Z}^*_{t,k,s}-\mu^*_k \leq -c^*_{t,k,s}, & \forall k \in \{1, \ldots, \alpha\} \label{eq:opt2}\\
&\hat{Z}^i_{t,k,s_i}-\mu_{i,k} \ge c^i_{t,k,s_i}, &\forall k \in \{1, \ldots, \alpha\} \label{eq:arm2} \\
&\sum_{k=1}^{\alpha} \mu_{k}^* - \mu_{i,k} - 2c^i_{t,k,s_i} < 0 , \label{c:false}
\end{align}

where $\mu_{i,k} := \mathbb{E}[Z^i_{t,k,s_i}]$ and $\mu^*_k : = \mathbb{E}[Z^{*}_{t,k,s}]$ are the expected value of the aggregated reward $Z^i_{t,k,s_i}$ from arm $i$, and $Z^{i^*}_{t,k,s}$ from the optimal arm, respectively.

Let us focus on the $k$-th inequality in Equation (<ref>).

We have:

\begin{align}
&\mathbb{P}(\hat{Z}^*_{t,k,s} - \mu^*_k \leq -c^*_{t,k,s}) \leq \exp \left\{ -\frac{2 (n^*_{t,k,s})^2 (c^*_{t,k,s})^2}{\sum_{l=1}^{n^*_{t,k,s}} \left( \frac{\overline{R}^*}{\alpha} \right)^2} \right\} \\
&\leq \exp \mleft\{ -\frac{2n^*_{t,k,s} (c^*_{t,k,s})^2 \alpha^2}{(\overline{R}^*)^2} \mright\} \leq e^{-4\ln{t}} \le t^{-4}, \nonumber
\end{align}

where $n^*_{t,k,s}$ is the number of samples available for the estimation of the expected value of $Z^{*}_{t,k,s}$ if we pulled $s$ times the arm $i^*$ at round $t$.

Here, we assume that the estimates have at least one sample.

If no samples are available, the original probability in Equation (<ref>) is bounded by $0$.

Similarly, for the inequalities in Equation (<ref>), we have:

\begin{align}
&\mathbb{P}(\hat{Z}^i_{t,k,s_i} - \mu_{i,k} \ge c^i_{t,k,s_i}) \leq \exp\mleft\{ -\frac{2(n^i_{t,k,s_i})^2(c^i_{t,k,s_i})^2}{\sum_{l=1}^{n^i_{t,k,s_i}}(\frac{\overline{R}^i}{\alpha})^2}\mright\}\\
&\leq \exp \mleft\{ -\frac{2n^i_{t,k,s_i} (c^i_{t,k,s_i})^2 \alpha^2}{(\overline{R}^i)^2} \mright\} \leq e^{-4\ln{t}} \le t^{-4}.
\end{align}

where $n^i_{t,k,s_i}$ is the number of samples available for the estimation of the expected value of $Z^{i}_{t,k,s_i}$ if we pulled $s_i$ times the arm $i$ at round $t$.

Define $ l = \mleft \lceil \alpha\step - 1 + \frac{8(\overline{R}^i)^2\ln{t}}{\Delta_i^2} \mright \rceil$.

Notice that $l \geq \Tmax$.

We have that the inequality in Equation (<ref>) is false.
Indeed, we have that:

\begin{align}
& \sum_{k=1}^{\alpha} \mleft(\mu_{k}^* - \mu_{i,k} - 2 \frac{\overline{R}^i}{\alpha}\sqrt{\frac{2\ln t}{n^i_{t,k,s_i}}} \mright)
\geq \Delta_i - 2\frac{\overline{R}^i}{\alpha} \sum_{k=1}^{\alpha} \sqrt{\frac{2\ln t}{s_i - k \step + 1}} \nonumber \\
&  \geq \Delta_i - 2\alpha\frac{\overline{R}^i}{\alpha} \sqrt{\frac{2\ln t}{s_i - \alpha \step + 1}} =  \Delta_i - 2\overline{R}^i \sqrt{\frac{2\ln{t}}{s_i - \alpha \step + 1}}, \label{c:zero}
\end{align}

where we used that $\sum_{k=1}^{\alpha} \mu_{k}^* - \mu_{i,k} = \mu^*-\mu_i= \Delta_i$.

If $s_i \geq \alpha \step - 1 + \frac{8(\overline{R}^i)^2\ln t}{\Delta_i^2}$, we have that:

\begin{align}
&s_i \geq \alpha \step - 1 + \frac{8 (\overline{R}^i)^2 \ln(t)}{\Delta^2_i}\\
& \frac{\Delta_i^2}{4(\overline{R}^i)^2} \geq \frac{2\ln(t)}{s_i - \alpha \step + 1} \\
&\Delta_i - 2\overline{R}^i \sqrt{\frac{2\ln(t)}{s_i - \alpha \step + 1}} \ge 0,
\end{align}

which implies that the inequality in Equation (<ref>) is false.

Finally, summing the above results we have that:

\begin{align}
& \mathbb{E}[N_i(t)] \leq \mleft \lceil \alpha \step - 1 + \frac{8(\overline{R}^i)^2 \ln(t)}{\Delta_i^2} \mright \rceil \nonumber\\
& + \sum_{t=1}^{\infty}\sum_{s=1}^{t-1}\sum_{s_i=l}^{t-1}\sum_{k=1}^{\alpha}
\left[ \mathbb{P}(\hat{Z}^*_{t,k,s} - \mu^*_k \leq - c^*_{t,k,s}) +
\mathbb{P}(\hat{Z}^i_{t,k,s_i} - \mu_{i,k} \geq c^i_{t,k,s_i}) \right]\\
& \le \alpha \step + \frac{8(\overline{R}^i)^2\ln(t)}{\Delta_i^2} + \sum_{t=1}^{\infty}\sum_{s=1}^{t-1}\sum_{s_i=l}^{t-1} 2\alpha t^{-4} \nonumber \\
& \le \frac{8(\overline{R}^i)^2\ln t}{\Delta_i^2} + \alpha \mleft(\step +\frac{\pi^2}{3}\mright).
\end{align}

Recalling that $\mathcal{R}_T(\mathfrak{U}_{{\texttt{EW}}}) = \sum_{i : \mu_i < \mu^*} \Delta_i \mathbb{E}[N_i(T)]$, concludes the proof.

§ EXPERIMENTAL SETTINGS DESCRIPTION AND ADDITIONAL EXPERIMENTS

§.§ Technical Details

The code has been run on a server equipped with Intel(R) Xeon(R) CPU $E5-4610$ v2 @ $2.30GHz$ and $126$ GiB of memory.

The operating system was Ubuntu $16.04.3$ LTS, and the experiments have been run on Python $3.5.2$.

The libraries used in the experiments, with the corresponding version were:

For the experiments the total time spent was $\approx 468$ hours, where the generation of the parameters of the synthetic datasest took $\approx 27$ hours, the execution of the algorithms for Setting #1 $\approx 50$ hours, the execution of the algorithms for Setting #2 $\approx 320$ hours, the execution of the algorithms for Spotify Setting $\approx 5$ hours (considering the data preprocessing operations), the execution of the algorithms for Setting #4, presented in what follows, $\approx 66$ hours.

§.§ Experimental Settings

In what follows, we provide a detailed description of those setting which have been presented in Section <ref> and further experiments confirming what has been showed in the main paper.

Setting #2 (main paper scenario)
In this setting, each arm is described  by a maximum reward $\overline{R}^i$ and two vectors $\bm{a}^i := \mleft[a^i_{1},\ldots,a^i_{\alpha}\mright]$ and $\bm{b}^i := \mleft[b^i_{1},\ldots,b^i_{\alpha}\mright]$ of length $\alpha$.

The aggregated reward $Z^i_{t,k}$ are distributed as $\mathcal{D}_k^i = \frac{\overline{R}^i}{\alpha}Beta(a_k^i,b_k^i)$, $\forall k \in [\alpha]$.

The results presented in the main paper are those corresponding to $\bm{a}^i := \bm{1}_{\alpha}$ and $\bm{b}^i := \bm{1}_{\alpha}$, where $\bm{1}_{\alpha}$ is a vector of length $\alpha$ whose elements are all $1$.

This setting corresponds to a uniform distribution over $\frac{\overline{R}^i}{\alpha}$ for each variable $Z^i_{t,k}$.

The corresponding results are presented in Section <ref>.

The regret over the entire time horizon is presented in Figure <ref>.

Experiments for Setting #2 and uniform reward distribution: (a) $\Tmax = 100$, $\alpha = 10$, (b) $\Tmax = 200$, $\alpha = 20$.

Spotify Setting

The original Spotify dataset [4] consists of listening sessions with levels of appreciation for each song associated to a user on the Spotify service.

Each listening session is truncated to $20$ tracks (songs).

Each row corresponds to the playback of one track pertaining to a specific listening session.

The dataset describes how users sequentially interact with the streamed content they are presented with.

More precisely, it contains information about when a user skips the playback of a track.

We preprocessed the available data as follows.

At first, for computational reasons we analysed only a fraction of the Spotify dataset.

Since we are interested in the listening sessions linked to a playlist, from that initial dataset we drop all the data associated with a  field context which is different from editorial playlist.

Moreover, we discarded all the listening sessions with less than $20$ songs and/or the user changed playlist during a single listening session ().

This way, each listening sessions is composed of $20$ song coming from a single playlist.

We selected the $6$ most listened playlists having no overlapping songs, and extracted from the dataset the listening sessions corresponding to them.

The final dataset is available in the file  in the code provided in the supplementary material.

The process of recommending the playlists is modeled as follows.
[Playlist Recommendation Problem - Reprise]

When a new user accesses the system, a playlist is proposed.

This action corresponds to the selection of an arm $i$ by the recommendation algorithm.

The user will start the reproduction of the playlist, composed of exactly $N = 20$ songs.

For each song, at any time, the agent could decide to skip to the next song until the end of the playlist.

We aim at finding the playlist that maximizes the overall listening time.

Each song has a reward equal to , , , and , representing increasing level of interest from the user.

These levels corresponds to the the realization of instantaneous reward $X^i_{t,j}$ of Bernoulli r.v. that takes the value of $1$ if the user has reached at least the corresponding level and $0$ otherwise;

The vector $\bm{X}^i_{t}$ has size equal to the number of songs of a playlist (i.e., aggregated rewards) times the number instant rewards returned by a song (i.e., $\phi$), and in this case $\Tmax = 20 \times 4 = 80$.
A summary of the expected rewards of the different playlists is provided in Table <ref>.

Figure <ref> shows an example of the reproduction of part of $5$ songs of a playlist.

Songs $1$ and $3$ were listened completely, while Song $2$ was listened up to level the .

Song $4$ and Song $5$ were entirely skipped.

1|c1     1     1     1c|1     1     1     0     1c|0     1     1     1     1c|1     0     0     0     1c|0     0     0     0     1c|0
4cSong 1                                  4cSong 2             4cSong 3             4cSong 4             4cSong 5

Example of a realization of an a subset of a playlist in the Spotify Setting.

Description of the arms in the Spotify Setting.

$i=1$     $i=2$     $i=3$     $i=4$     $i=5$     $i=6$

$\mu^i$        38.59     52.35      38.44     43.89     23.48    36.20

$\sigma^i$     21.83     20.11     23.09      23.14     23.48     23.8

§.§ Additional Experiments

Setting #2.1
In this experiment, the setting is the same as the one in Setting #2, except that we designed the rewards s.t. the first aggregated rewards after the pull are smaller than the last ones.

Specifically, the distribution are defined by the following vectors:

* $\Tmax = 100$, $\alpha = 10$:

\begin{align*}
&\bm{a}^i=[2,4,6,8,10,10,10,10,10,10]; \\ &\bm{b}^i=[10,10,10,10,10,10,8,6,4,2];
\end{align*}

* $\Tmax = 200$, $\alpha = 20$:

\begin{align*}
&\bm{a}^i=[2,4, \ldots, 18, 20, \ldots, 20]; \\
&\bm{b}^i=[20, \ldots, 20, 18, \ldots, 4, 2];
\end{align*}

* $\Tmax = 100$, $\alpha = 50$:

\begin{align*}
\bm{a}^i=[&2,4, \ldots, 48,50, \ldots, 50]; \\
\bm{b}^i=[&50, \ldots, 50,48, \ldots, 4, 2];
\end{align*}

* $\Tmax = 200$, $\alpha = 100$:

\begin{align*}
\bm{a}^i=[&2, 4, \ldots, 98, 100, \ldots, 100]; \\
\bm{b}^i=[&100, \ldots, 100, 98, \ldots, 4, 2].
\end{align*}

The corresponding results are provided in Figure <ref>.

They are in line with the ones of Setting #2.

Experiments for Setting #2.1: (a) $\Tmax = 100$, $\alpha = 10$, (b) $\Tmax = 200$, $\alpha = 20$.

Setting #2.2
In this experiment, the setting is the same as the one in Setting #2, except that we designed the rewards s.t. the first aggregated rewards after the pull are larger than the last ones.

Specifically, the distribution are defined by the following vectors:

* $\Tmax = 100$, $\alpha = 10$:

\begin{align*}
&\bm{a}^i=[10,10,10,10,10,10,8,6,4,2,]; \\ &\bm{b}^i=[2,4,6,8,10,10,10,10,10,10];
\end{align*}

* $\Tmax = 200$, $\alpha = 20$:

\begin{align*}
&\bm{a}^i=[20, \ldots, 20, 18, \ldots, 4, 2];\\
&\bm{b}^i=[2,4, \ldots, 18, 20, \ldots, 20];
\end{align*}

* $\Tmax = 100$, $\alpha = 50$:

\begin{align*}
\bm{a}^i=[&50, \ldots, 50,48, \ldots, 4, 2];\\
\bm{b}^i=[&2, 4, \ldots, 48,50, \ldots, 50];
\end{align*}

* $\Tmax = 200$, $\alpha = 100$:

\begin{align*}
\bm{b}^i=[&100, \ldots, 100, 98, \ldots, 4, 2];\\
\bm{a}^i=[&2, 4, \ldots, 98, 100, \ldots, 100].
\end{align*}

The corresponding results are provided in Figure <ref>.

They are in line with the ones of Setting #2.

Experiments for Setting #2.2: (a) $\Tmax = 100$, $\alpha = 10$, (b) $\Tmax = 200$, $\alpha = 20$.

Setting #2.3
Finally, in this experiment, the setting is the same as the one in Setting #2, except that the reward distributions are randomly chosen.

Specifically, the distribution sampled used in the experiments are:

* $\Tmax = 100$, $\alpha = 10$:

\begin{align*}
&\bm{a}^i=[7,7,1,5,9,8,7,5,8,6]; \\ &\bm{b}^i=[10,4,9,3,5,3,2,10,5,9];
\end{align*}

* $\Tmax = 200$, $\alpha = 20$:

\begin{align*}
&\bm{a}^i=[10,3,5,2,2,6,8,9,2,6,7,6,10,4,9,8,8,9,5,1]; \\ &\bm{b}^i=[9,1,2,7,1,10,8,6,4,6,2,4,10,4,4,3,9,8,2,2];
\end{align*}

* $\Tmax = 100$, $\alpha = 50$:

\begin{align*}
\bm{a}^i=[&6,9,8,2,5,9,5,2,9,6,9,4,10,9,10,5,8,2,10,7,6,10,4,5,3,4,3,1,10,5,8,2,2,3,3,\\
&1,2,9,7,9,5,9,4,4,10,7,10,5,8,8]; \\
\bm{b}^i=[&6,2,6,10,2,8,10,6,4,4,1,5,2,4,6,3,6,7,1,2,3,4,1,10,9,10,2,1,2,4,10,10,2,7,2,\\
\end{align*}

* $\Tmax = 200$, $\alpha = 100$:

\begin{align*}
\bm{a}^i=[&2,5,2,4,2,5,6,7,3,1,9,8,1,10,2,7,4,5,6,8,10,3,4,1,3,3,6,9,5,2,10,8,3,1,8,7,\\
&4,8,7,10,7,1,7,10,7,1,3,8,2,5,3,8,9,8,9,10,1,1,8,6,5,8,1,7,4]; \\
\bm{b}^i=[&9,2,3,1,7,7,6,1,4,1,1,9,10,2,4,2,10,4,5,5,3,2,8,7,2,1,5,8,2,5,3,9,6,2,3,5,1,\\
\end{align*}

The corresponding results are provided in Figure <ref>.

They are in line with the ones of Setting #2.

Experiments for Setting #2.3: (a) $\Tmax = 100$, $\alpha = 10$, (b) $\Tmax = 200$, $\alpha = 20$.

Summary for Setting #2
The overall results for the previous setting #2, #2.1, #2.2, and #2.3 are reported in Table <ref>, <ref>, <ref>, <ref>.

Summary of result for setting #2, $\Tmax = 100$, $\alpha = 10$.

$\Tmax$     $\alpha$     Scenario     Learner     Regret     Confidence Interval

100     10      1          379407.7536     641.3890868

100     10      1          476211.7734     1379.593546

100     10      1          550020.3093     3383.218936

100     10      1          461295.3133     1198.377002

100     10      2         	378590.4996	    1444.810301

100     10      2        	478543.3454    	3282.169025

100     10      2          556264.2577     4563.491842

100     10      2          464045.2915	    3127.506071

100     10      3         	377928.2537	    550.2470147

100     10      3        	477050.7314	    1370.65113

100     10      3          552254.3013    	2871.253395

100     10      3          462051.9847    	1022.873814

100     10      4          376004.9497    	713.1333679

100     10      4          461523.0728    	1159.826331

100     10      4          546401.0207	    3116.186928

100     10      4          445761.5334	    1160.681727

Summary of result for setting #2, $\Tmax = 200$, $\alpha = 20$.

$\Tmax$     $\alpha$     Scenario     Learner     Regret     Confidence Interval

200     20      1          1161392.507     653.9898656

200     20      1          969119.3579     2376.133933

200     20      1          1215396.1     11238.84718

200     20      1          921857.7185	    1262.074342

200     20      2          1159038.888     	1855.393219

200     20      2        976387.8607	   4103.793005

200     20      2          1214717.526	    12958.26024

200     20      2         922123.0453    3911.196296

200     20      3          1158406.886     719.1511692

200     20      3         971023.1429    2128.831649

200     20      3          1225998.654	    12586.53841

200     20      3          922097.5566	    1084.342302

200     20      4          1150596.776     1373.38433

200     20      4          919231.1795     2971.38115

200     20      4          1224143.761     6816.6797

200     20      4          863043.4276     2568.233259

Summary of result for setting #2, $\Tmax = 100$, $\alpha = 50$.

$\Tmax$     $\alpha$     Scenario     Learner     Regret     Confidence Interval

100     50      1           280850.7628     200.0363298

100     50      1          470206.8356    	610.8394845

100     50      1          555004.3727     3611.482174

100     50      1          461125.7678     433.1909748

100     50      2          280469.8885     600.1158378

100     50      2        	470948.6985	    1810.491059

100     50      2          551713.5918     3167.855141

100     50      2          460454.4842   	1535.465475

100     50      3          	280432.6875	    194.6246275

100     50      3        	470851.5341   	678.1378134

100     50      3          552354.8852   	2784.797814

100     50      3          461262.8902   	406.9041603

100     50      4          277350.6683      357.2049513

100     50      4          431428.2109    	845.9105653

100     50      4          533550.167    	6134.964191

100     50      4          419308.3464	    840.25097

Summary of result for setting #2, $\Tmax = 200$, $\alpha = 100$.

$\Tmax$     $\alpha$     Scenario     Learner     Regret     Confidence Interval

200     100      1          998723.9102     348.3923308

200     100      1          962166.9976     1574.53646

200     100      1          1217054.205     13791.12121

200     100      1          922801.461	    681.1463488

200     100      2          997866.0232     1163.306506

200     100      2        962888.2947	   2886.588981

200     100      2          1223555.271	    13076.51935

200     100      2          924666.3352    	1936.282782

200     100      3          995734.719     386.1528975

200     100      3         962419.0355    	1671.591765

200     100      3          1224181.588	    14560.25523

200     100      3          923018.9128	    593.7216922

200     100      4          996058.5901    	681.2301995

200     100      4          937032.8774    	1815.90584

200     100      4          1214671.825    	12459.63383

200     100      4          893569.8466    	1098.403796

Setting #4

In this setting, each arm is described by a maximum reward $\overline{R}^i = \Tmax \cdot i$, and two vectors $\bm{a}^i=\mleft[a^i_{1},\ldots,a^i_{\alpha}\mright]$ and $\bm{b}^i=\mleft[b^i_{1},\ldots,b^i_{\alpha}\mright]$ of length $\alpha$.

The aggregated rewards $Z^i_{t,k}$ are distributed as $\mathcal{D}_k^i = \frac{\overline{R}^i}{\alpha}Beta(a_k^i,b_k^i)$, $\forall k \in [\alpha]$.

In this experiment, we fix $\Tmax = 100$, $\alpha = 10$, $T = 10^5$, and we design ten scenarios differing in the vectors $\bm{a}^i$ and $\bm{b}^i$.

The parameters characterizing such randomly generated scenarios are reported in Table <ref>.

The results for each scenario are averaged over $50$ independent runs.

In Figure <ref>, we provide the average result over the $10$ scenarios, with whiskers corresponding to $95\%$ confidence intervals.

Parameters used in Setting #4.

$\bm{a}^i$     $\bm{b}^i$

Scenario 1     [8, 2, 8, 7, 1, 5, 6, 3, 3, 10]     [7, 2, 2, 2, 4, 4, 1, 7, 1, 2]

Scenario 2     [7, 9, 9, 5, 8, 8, 10, 4, 7, 2]     [6, 4, 5, 10, 3, 7, 4, 6, 2, 2]

Scenario 3     [1, 9, 8, 4, 2, 8, 7, 5, 4, 1]     [4, 10, 3, 2, 4, 8, 7, 6, 9, 3]

Scenario 4     [2, 10, 8, 3, 10, 7, 7, 9, 8, 6]     [8, 8, 4, 9, 10, 4, 1, 6, 6, 6]

Scenario 5     [1, 9, 3, 5, 10, 3, 7, 10, 5, 8]     [2, 2, 9, 1, 2, 4, 3, 1, 5, 1]

Scenario 6     [8, 6, 3, 3, 8, 6, 9, 7, 9, 9]     [1, 10, 2, 9, 10, 2, 7, 4, 5, 9]

Scenario 7     [10, 7, 8, 7, 10, 10, 4, 1, 1, 3]     [5, 9, 10, 5, 6, 2, 8, 5, 5, 7]

Scenario 8     [7, 7, 1, 3, 3, 4, 5, 6, 1, 1]     [8, 7, 3, 8, 10, 2, 3, 6, 7, 1]

Scenario 9     [10, 8, 7, 8, 1, 2, 8, 3, 1, 1]     [10, 10, 3, 6, 2, 9, 6, 4, 7, 8]

Scenario 10     [2, 1, 10, 8, 10, 6, 2, 10, 5, 3]     [7, 5, 2, 9, 4, 1, 7, 8, 6, 4]

Experiments for Setting # 4: $\Tmax = 100$, $\alpha = 10$

Figure <ref> shows an aggregated result on the pseudo-regret $\mathcal{R}_t(\mathfrak{U})$ for the analysed algorithms.

Even over randomly generated scenarios we see that the proposed method are able to provide a significant improvement over the  algorithm.

Moreover, consistently the  algorithm result to be the best one at the end of the analysed time horizon $T = 10^5$.

Conversely, for shorter time horizon ($T \leq 0.35 \cdot 10^5$) the algorithm performing the best among the ones for the TP-MAB setting is the , which strengthen the idea that this algorithm is better suited for shorter time horizons.

Setting #5
Finally, we provide an experiment over a longer time horizon of $T = 10^6$ in the same configuration depicted by Setting #1.
The pseudo-regret over time for this experiment is provided in Figure <ref>.
Let us focus on the regret of (20), i.e., the  algorithm where parameter $\alpha$ corresponds to the one of the environment, and compare it with the regret of .
The regret of (20) (red line) has a slower growth w.r.t.  (purple line), and, consequently, the difference in terms of regret increases (logarithmically) over time.
The parameter influencing the regret of  is $\alpha$, which characterizes the specific setting we are tackling.
More specifically, if we fix the other parameters (e.g., $\tau_{\max}$) and increase the value of alpha, we have a proportional improvement in the upper bound of the regret of .
Therefore, we expect to have an even larger improvement of our algorithm when the value of $\alpha$ is large.

Experiments for Setting # 5: $\Tmax = 100$, $\alpha = 20$

§ REAL-WORLD APPLICATIONS OF THE TP-MAB FRAMEWORK

In this section, we report some additional real-world examples which can be modeled through the TP-MAB setting. The following scenarios are characterized by the $\alpha$-smoothness property with different values of the $\alpha$ parameters.

An agent periodically receives a batch of identical items to sell on an e-commerce platform.

Every time a slot of $N$ items arrives, the agent decides a price $p_i$ to post on a website, which corresponds to the arm $i_t$ chosen for the round $t$.

The selected time horizon to sell the items, which are perishable, is one month.

Each day, the seller checks how many items have been ordered and collects the payments (i.e., rewards).

In this example, the maximum delay is $\Tmax = 30$ days, and one round is equal to $1$ day.

The upper bound on the cumulative reward is $\overline{R}^i = p_i N$.

Notice that the partial reward of each round is also upper bounded by $p_i N$.

This implies that the reward has no structure, and consequently the $\alpha$-smoothness in this setting holds with $\alpha = 1$.

[Lottery Ticket]
There are $K$ different lotteries to choose from.

Lottery $i \in [K]$ has $N$ winning scratch cards, each with a prize of $M$.

The probability to extract a winning ticket in lottery $i$ is $p_i$.

The player has to choose a lottery at each time step.

At each round, the player buys $n$ tickets and sequentially scratches them and observes the reward.

If $N = 1$ the total amount the player can win is $M$ and the reward is $1$-smooth.

Indeed, suppose that the first $n-1$ tickets are not winning.

This does not precludes the possibility of still gaining the maximum cumulative reward with the last ticket.

Conversely, if $N = n$ the total amount the player can win is $\overline{R}^i = N M$, and the reward is $n$-smooth.

More specifically, by scratching the first ticket, the player can get useful information on the cumulative reward if the reward is either zero or $M$.

If the player observed a zero reward so far, the maximum achievable cumulative reward becomes $(N-1) M$.

Conversely if the player observed a positive reward, the overall reward is in the interval $[M, N M]$.