# The Impact of Batch Learning in Stochastic Linear Bandits

Danil Provodin  Pratik Gajane  Mykola Pechenizkiy  Maurits Kaptein

###### Abstract

We consider a special case of bandit problems, named batched bandits, in which
an agent observes batches of responses over a certain time period. Unlike
previous work, we consider a practically relevant batch-centric scenario of
batch learning. That is to say, we provide a policy-agnostic regret analysis
and demonstrate upper and lower bounds for the regret of a candidate policy.
Our main theoretical results show that the impact of batch learning can be
measured proportional to the regret of online behavior. Primarily, we study
two settings of the problem: instance-independent and instance-dependent.
While the upper bound is the same for both settings, the worst-case lower
bound is more comprehensive in the former case and more accurate in the latter
one. Also, we provide a more robust result for the 2-armed bandit problem as
an important insight. Finally, we demonstrate the consistency of theoretical
results by conducting empirical experiments and reflect on the optimal batch
size choice.

Machine Learning, ICML

##  1 Introduction

Background and motivation. The stochastic bandit problem is one of the central
topics of modern literature on sequential decision making, which aims to
determine policies that maximize the expected reward. These policies are often
learned either online (sequentially) (see, e.g., (Li et al., 2010; Jun et al.,
2017; Dimakopoulou et al., 2018)) or offline (statically) (see, e.g.,
(Swaminathan and Joachims, 2015; Zhou et al., 2018; Joachims et al., 2018;
Athey and Wager, 2020). In online problems, the agent learns through
sequential interaction with the environment, adjusting the behavior for every
single response. In offline learning, on the other hand, the agent learns from
fixed historical data without the possibility to interact with the
environment. Therefore, the agent’s goal is to maximally exploit the static
data to determine the best policy. However, in many application domains,
batched feedback is an intrinsic characteristic of the problem, and neither
setting provides a close approximation of the underlying reality (Bertsimas
and Mersereau, 2007; Chapelle and Li, 2011; Schwartz et al., 2013; Hill et
al., 2017). While the offline setting is not conducive to sequential learning,
online learning is often curtailed by the limitations of practical
applications. For example, in recommender systems and ad placement engines,
treating users one at a time can become a formidable computational and/or
engineering burden; in online marketing and clinical trials, environments
design (campaigns/trials) and the presence of delayed feedback result in
treating patients/customers organized into groups. In all of these applied
cases, it is infeasible to learn truly one by one due to computational
complexity or the impact of delay. In such cases, an online approach that acts
on groups of observations is much more appealing from a practical point of
view.

Because of the practical restrictions described above, we consider sequential
batch learning in bandit problems – sequential interaction with the
environment when responses are grouped in batches and observed by the agent
only at the end of each batch. Broadly speaking, sequential batch learning is
a more generalized way of learning which covers both offline and online
settings as special cases bringing together their advantages.

  * •

Unlike offline learning, sequential batch learning retains the sequential
nature of the problem.

  * •

Unlike online learning, it is often appealing to implement batch learning in
large-scale bandit problems as

    * –

it does not require much engineering effort and resources, as experimental
control over the system is unessential; and

    * –

it does not need resources to shorten the feedback loop in time-delayed bandit
problems.

Although the batch setting is not ubiquitous in the traditional stochastic
bandit formulation, there have been several attempts to extend that framework.
To the best of our knowledge, Anantharam et al. (1987) are the first who
introduced the batch problem, though a more restrictive version of it – when
the agent can choose each arm at most once in a single batch. Jun et al.
(2016) generalized that problem by introducing budget (how many times each arm
can be chosen). However, unlike our case, the authors considered the problem
of identifying top-$k$ arms with high probability. The origin of our problem
formulation can be traced back to Perchet et al. (2016), who proposed an
explicit batched algorithm based on explore-then-commit policy for a two-armed
batch bandit problem with a relatively small number of batches and explore its
upper and lower regret bounds, giving rise to a rich line of work Gao et al.
(2019); Han et al. (2020); Esfandiari et al. (2021); Kalkanli and Ozgur
(2021). The problem of batched bandits relates to learning from delayed or/and
aggregated feedback (see, e.g., (Joulani et al., 2013; Vernade et al., 2017;
Pike-Burke et al., 2018)), since the decision-maker is not able to observe
rewards in the interim of a batch. Although these are two similar problems,
learning from delayed feedback deals with exogenous delays, whereas feedback
delays in sequential batch learning are endogenous and arise as a consequence
of the batch constraints (Han et al., 2020).

Unfortunately, a comprehensive understanding of the effects of the batch
setting is still missing. Withdrawing the assumptions of online learning that
have dominated much of the bandit literature raises fundamental questions as
how to benchmark performance of candidate policies, and how one should choose
the batch size for a given policy in order to achieve the rate-optimal regret
bounds. As a consequence, it is now frequently a case in practice when the
batch size is chosen for the purpose of computational accessibility rather
than statistical evidence (Chapelle and Li, 2011; Hill et al., 2017).
Moreover, while the asymptotics of batched policies is known (see, e.g., Auer
and Ortner (2010); Cesa-Bianchi et al. (2013)), the relatively small horizon
performance of batch policies is much less understood while simultaneously
being much more practically relevant. Thus, in this work, we make a
significant step in these directions by providing a systematic study of the
sequential batch learning problem.

Main contribution 111Some preliminary results have been presented at NeurIPS
2021 Workshop on Ecological Theory of Reinforcement Learning (Provodin et al.,
2021).. First, we formulate a more practically relevant batch-centric
sequential learning problem. Second, we provide a refined theoretical analysis
and establish upper and lower bounds on the performance for an arbitrary
candidate policy. In particular, we start with a more restricted analysis of
the 2-armed problem, which allows us to derive a more robust result for the
exact regret. Then we show that this result is partly achievable in the
general setting – only for the upper bound. As for the lower bound, we provide
two results for the worst-case regret bound: more comprehensive instance-
independent and more accurate instance-dependent. On the modeling side, we
demonstrate the validity of the theoretical results experimentally and reflect
on the optimal batch size choice.

The rest of the paper is organized as follows: The problem of sequential batch
learning is defined in Section 2. The 2-armed problem, instance-independent
and instance-dependent analyses are given in Sections 3, 4.1, and 4.2
respectively. In Section 5, we provide empirical results and finally, we
conclude with Section 6.

##  2 Problem formulation

We consider a general model of sequential batch learning in which, unlike
classical online learning, we assume that the responses are grouped in batches
and observed only at the end of each batch. For building up the formal notion
of the batch learning setting in Section 2.2, we first introduce the basic
notions of the classical setting in Section 2.1.

###  2.1 Decision Procedure and Reward Structures

We consider a general setting of the stochastic linear bandit problem. In this
problem, the decision-maker (agent) has to make a sequence of decisions
(actions or arms), possibly based on some side information, and for each
decision it incurs a stochastic, although not necessarily immediately
observed, reward. 222We borrow notations as well as problem formulation for
online setting from Lattimore and Szepesvári (2020). More formally, given a
decision set $\mathcal{A}_{t}\subset\mathbb{R}^{d}$ (for $d<\infty$) and a
time horizon $n<\infty$, at each time step $t\in\\{1,2,\dots,n\\}$, the agent
chooses an action $A_{t}\in\mathcal{A}_{t}$ and reveals reward

$X_{t}=\langle\theta_{*},A_{t}\rangle+\eta_{t}$

where $\eta_{t}$ is the noise, and $\theta_{*}$ is the instance unknown for
the agent. For simplicity, we assume each $\eta_{t}$ is 1-subGaussian:
$\mathbb{E}[e^{\lambda\eta_{t}}]\leq e^{\lambda^{2}/2},\forall
t\in[n],\forall\lambda\in\mathbb{R}$. Although restrictive, this is a
classical assumption for bandit literature, as it covers most reasonable noise
distributions. Further, without loss of generality (since $d<\infty$), we
assume $\left\lVert\theta_{*}\right\rVert_{2}\leq 1$.

The goal of the agent is to maximize the total reward
$S_{n}=\sum_{t=1}^{n}X_{t}$. To assess the performance of a policy $\pi$, we
consider regret – difference between the agent’s total reward and cumulative
reward obtained by an optimal policy:

$R_{n}(\pi)=\mathbb{E}\left[\sum_{t=1}^{n}\max_{a\in\mathcal{A}_{t}}\langle\theta_{*},a\rangle-
S_{n}\right].$

The generality of this setting lies in the choice of the decision set
$\mathcal{A}_{t}$: different choices of $\mathcal{A}_{t}$ lead to different
settings.

#### Stochastic bandit.

If $(e)_{i}$ are the unit vectors and $\mathcal{A}_{t}=\\{e_{1},...,e_{K}\\}$
then the resulting stochastic linear bandit problem reduces to the finite-
armed stochastic setting. We can think of the problem as an interaction
between the agent and environment $\nu=(P_{a}:a\in\mathcal{A})$, where
$\mathcal{A}:=\\{1,...,K\\}$ and $P_{a}$ is the distribution of rewards for
action $a$. At each time step $t$, the agent chooses an action
$A_{t}\in\mathcal{A}$ and receives a reward $X_{t}\sim P_{A_{t}}$. In this
case $\theta_{*}=(\mu_{a})_{a}$, where $\mu_{a}=\int_{\mathbb{R}}xdP_{a}(x)$
is the expected reward of action $a\in\mathcal{A}$, and regret is the
difference between the agents’ total reward after $n$ rounds and the best
reward possible given the strategy of playing a single arm:

$R_{n}(\pi)=n\max_{a\in\mathcal{A}}\mu_{a}-\mathbb{E}\big{[}S_{n}\big{]}.$ (1)

#### Contextual linear bandit.

If $\mathcal{A}_{t}=\\{\psi(C_{t},i):i\in[K]\\}$, where
$\psi:\mathcal{C}\times[K]\xrightarrow{}\mathbb{R}$ is a feature map and
$C_{t}\in\mathcal{C}$ is a context observed by the agent at timestep $t$, then
we have a contextual linear bandit. To illustrate how the above quantities
arise in practice we give an example. Suppose, at the beginning of round $t$,
a customer characterized by context $C_{t}$ visits a website selling books.
When the agent applies action $A_{t}$ (recommends a book) to the customer, a
reward $r_{t}(C_{t},A_{t})$ is obtained. The contextual linear bandit settings
assumes that the expected reward $\mathbb{E}[r_{t}(c,a)]$ is a parametrized
mean reward function $g_{\theta}(\cdot)$ of feature vector
$\psi(\cdot,\cdot)$, formally, $\mathbb{E}[r_{t}(c,a)\text{ }|\text{
}C_{t},A_{t}]=g_{\theta}(\psi(C_{t},A_{t}))$. Note that the linear contextual
bandits setting then corresponds to
$g_{\theta}(\cdot)=\langle\theta,\cdot\rangle$.

###  2.2 Sequential batch learning

In the standard online learning setting, the decision maker immediately
observes the reward $X_{t}$ after selecting action $A_{t}$ at time step $t$.
Consequently, in selecting $A_{t+1}$, the decision maker can base his decision
on the on the current decision set $\mathcal{A}_{t+1}$ and past history. Here,
the past at time step $t>0$ is defined as

$H_{t}=(A_{1},X_{1},...,A_{t},X_{t})\in\mathbb{R}^{(d+1)t}\equiv\mathcal{H}_{t}$

which is the sequence of action-reward pairs leading up to the state of the
process at the previous time step $t$. Note that $H_{0}=\emptyset$. Let
$\mathcal{M}_{1}{(}X)$ be a set of all probability distributions over a set
$X$. As such, a policy is a finite sequence $\pi=(\pi_{t})_{1\leq t\leq n}$ of
maps of histories to distributions over actions (decision rules), formally,
$\pi_{t}:\mathcal{H}_{t-1}\xrightarrow{}\mathcal{M}_{1}{(}\mathcal{A}_{t})$.
Intuitively, following a policy $\pi$ means that in timestep $t$, the
distribution of the action $A_{t}$ to be chosen for that timestep is
$\pi_{t}(H_{t-1})$: the probability that $A_{t}=a$ is $\pi_{t}(a|H_{t-1})$.
Thus, when following a policy $\pi$, in timestep $t$ we get that

$\mathbb{P}(A_{t}=a|H_{t-1})=\pi_{t}(a|H_{t-1}).$

In contrast to conventional approaches that require the reward to be
observable after each choice of the action, our setting assumes only that
rewards are released at specific predefined timesteps. Denote by
$\mathcal{T}=t_{1},...,t_{M}$ a grid, which is a division of the time horizon
$n$ to $M$ batches of equal size $b$, $1=t_{1}<...<t_{M}=n,t_{j}-t_{j-1}=b$
for all $j=1,...,M$. Without loss of generality we assume that $n=bM$,
otherwise we can take $n:=\left\lfloor\frac{n}{b}\right\rfloor b$. Recall that
in the batch setting the agent receives the rewards after each batch ends,
meaning that the agent operates with the same amount of information within a
single batch. For simplicity, we assume that as long as the history remains
the same the decision rule does not change as well. Note that this assumption
does not impose any significant restrictions. Indeed, instead of applying a
policy once, one can always do it $b$ times until the history updates. Thus, a
batch policy is also a finite sequence of $\pi=(\pi_{t})_{1\leq t\leq n}$ of
decision rules:
$\pi_{t}:\mathcal{H}_{t-1}\xrightarrow{}\mathcal{M}_{1}{(}\mathcal{A}_{t})$.
However, not the whole past history is available for the agent in timestep
$t$, formally, $H_{t}=H_{t_{j}}$ for any $t_{j}<t\leq t_{j+1}$.

In practice, sequential batch learning is usually considered as a limitation
of the environment. However, for notation convenience, despite the batch
setting being a property of the environment, we consider this limitation from
a policy perspective. With this, we assume that it is not the online agent who
works with the batch environment, but the batch policy interacts with the
online environment. To distinguish between online and batch policies we will
denote the last as $\pi^{b}=(\pi^{b}_{t})_{1\leq t\leq n}$.

We now are ready to formulate the goal of the paper formally. That is, given a
policy $\pi$, we aim to establish upper and lower regret bounds of its batch
specification $\pi^{b}$.

###  2.3 Preliminaries

Before proceeding, we will need to distinguish between “good” and “bad”
policies on the basis of some properties. Accordingly, we first define a
binary relation on a set of policies. We say that the decision rule
$\pi_{t}=\pi_{t}(\cdot|H_{t-1})$ is not worse than the decision rule
$\pi_{t}^{\prime}=\pi_{t}^{\prime}(\cdot|H_{t-1})$ (and write
$\pi_{t}\geq\pi_{t}^{\prime}$) if the expected reward under $\pi_{t}$ is not
less than the expected reward under $\pi_{t}^{\prime}$:

$\sum_{a\in\mathcal{A}_{t}}\langle\theta_{*},a\rangle\pi_{t}(a|H_{t-1})\geq\sum_{a\in\mathcal{A}_{t}}\langle\theta_{*},a\rangle\pi_{t}^{\prime}(a|H_{t-1}).$
(2)

If $\geq$ can be replaced by $>$, we say that the decision rule $\pi_{t}$ is
better than the decision rule $\pi_{t}^{\prime}$ (and write
$\pi_{t}>\pi_{t}^{\prime}$).

Define the informativeness of history by the number of times the optimal
actions were chosen in it. Formally, let
$T_{a^{\ast}}(\pi,t)=\sum_{s=1}^{t}\mathbb{I}\\{A_{t}=A_{t}^{*}\\}$ be the
number of times policy $\pi$ made optimal decisions in history $H_{t}$. Then,
we require that the decision rule based on a more informative history is at
least as good as the decision rule based on a less informative history:

######  Assumption 2.1 (Informativeness).

Let $T_{a^{\ast}}(\pi,t)$ and $T^{\prime}_{a^{\ast}}(\pi,t)$ be numbers of
times the optimal actions were chosen in histories $H_{t}$ and
$H^{\prime}_{t}$, correspondingly. If $T_{a^{\ast}}(t)\geq
T^{\prime}_{a^{\ast}}(t)$, then
$\pi_{t+1}(\cdot|H_{t})\geq\pi_{t+1}(\cdot|H^{\prime}_{t})$.

Next, we assume that policy $\pi=(\pi_{t})_{1\leq t\leq n}$ improves over time
if the “rate” of increasing of the regret decreases.

######  Assumption 2.2 (Subliniarity).

$\frac{R_{n_{1}}(\pi)}{n_{1}}>\frac{R_{n_{2}}(\pi)}{n_{2}}$ for all
$n_{1},n_{2}$, $1\leq n_{1}<n_{2}\leq n$.

Finally, we impose a monotonic lower bound on the probability of choosing the
optimal arm at timestep $t$. Here we consider two assumptions: instance-
independent and instance-dependent monotonicity. That is, in the former case,
we assume the existence of the lower bound $f(t)$, no matter what instance
$\theta$ is given; while in the latter case – the existence of the lower bound
depends on a specific instance of actions $\theta$: $f:=f_{\theta}$. Like in
instance-independent regret analysis, this bound may imply a tighter worst-
case bound rather than in an instance-independent case.

######  Assumption 2.3 (Instance-independent monotonicity).

For any suboptimal action $a$, $a\in\mathcal{A}_{t}$ and
$a\notin\arg\max_{\mathcal{A}_{t}}\langle\theta_{*},a\rangle$, there exists a
function $f_{a}:[0,\infty)\xrightarrow{}[0,1]$ such that: (i) $f_{a}$ is
nonincreasing; (ii) $\pi_{t}(a|H_{t-1})\leq f_{a}(t)$ for all $t>0$; and (iii)
$f(t):=1-\sum_{a}f_{a}(t)$ is a strictly increasing function for all $t>0$
unless $f(t)=1$. 333Note that from (ii) and (iii) it follows that for all $t$,
$\pi_{t}(a^{\ast}|H_{t-1})\geq f(t)$.

######  Assumption 2.4 (Instance-dependent monotonicity).

For any suboptimal action $a$, $a\in\mathcal{A}_{t}$ and
$a\notin\arg\max_{\mathcal{A}_{t}}\langle\theta_{*},a\rangle$, there exists a
function $f_{\theta,a}:[0,\infty)\xrightarrow{}[0,1]$, depending on $\theta$,
such that: (i) $f_{\theta,a}$ is nonincreasing; (ii) $\pi_{t}(a|H_{t-1})\leq
f_{\theta,a}(t)$ for all $t>0$; (iii)
$f_{\theta}(t):=1-\sum_{a}f_{\theta,a}(t)$ is a strictly increasing function
for all $t>0$ unless $f_{\theta}(t)=1$; and (iv) $f_{\theta}(t)$ is
nondecreasing in its instance argument in the following sense:
$f_{\theta_{1}}(t)<f_{\theta_{2}}(t)$ for all $t>0$ if
$\langle\theta_{1},a\rangle<\langle\theta_{2},a\rangle$ for all suboptimal
action $a$.

The validity discussion of the imposed assumptions can be found in Appendix A.

So to conclude this section, we provide some properties of a policy with
sublinear regret that we will use further. The proof of the following lemma is
presented in Appendix B.1.

######  Lemma 2.5.

Let $\pi=(\pi_{t})_{1\leq t\leq n}$ be a policy such that Assumption 2.2
holds. Then,

  1. 1.

$\bar{\pi}_{n_{2}}>\bar{\pi}_{n_{1}}$, where
$\bar{\pi}_{t}=\frac{\sum_{s=1}^{t}\pi_{s}}{t}$ is an average decision rule;

  2. 2.

$\pi_{t}>\bar{\pi}_{t}$ $\forall t$ such that $1\leq t\leq n$,

where $\pi_{t}+\pi_{s}$ is an elementwise addition of two probability vectors
for some $t,s$.

##  3 Batch learning for 2-armed bandits

In this section, we provide lower and upper bounds on the best achievable
performance for 2-armed stochastic bandits. We start with a more restricted
analysis of 2-armed problem because, first, it allows to derive a stronger
result, and, second, it gives better insight into the analysis.

Intuitively, if policy $\pi$ is good enough, it should be better than policy
$\pi^{b}$ because it makes its decisions (“good decisions”) having the maximum
available information about the environment. Nevertheless, batch policy
$\pi^{b}$ is a batch specification of “good” policy $\pi$, and and we expect
it to perform relatively well. The following theorem formalizes the described
above intuition.

######  Theorem 3.1.

Let $\pi^{b}$ be a batch specification of a given policy $\pi$, $K=2$, and
$M=\frac{n}{b}$. Suppose that assumptions 2.1 and 2.2 hold. Then, for $b>1$,

$R_{n}(\pi)<R_{n}(\pi^{b})\leq bR_{M}(\pi).$ (3)

######  Remark 3.2.

We can consider the term $bR_{M}(\pi)$ as $b$ similar online independent
agents operating in the same environment by following policy $\pi$ but over a
shorter horizon $M$. However, we can also think of it as the performance of a
batch policy. Indeed, imagine a naïve agent that deliberately repeats each
step $b$ times instead of immediately updating its beliefs and proceeding to
the next round as in an online manner. Then, after $b$ repetitions (after a
batch ends), it updates its beliefs using only the first reward from the
previous batch. So, while this policy could perform as an online policy within
these repetitions, it pretends that rewards are not observable and acts using
the outdated history (just like a batch policy does). For notational
simplicity, we refer to this policy as online “short” policy and denote it by
$\pi^{\prime}$. Thus, the theorem allows benchmarking any batch policy in
terms of its online analogs. Note that there is no behavioral difference
between the original policy $\pi$ and the “short” policy $\pi^{\prime}$ (see
Appendix A.5 for more details).

###### Proof outline.

First, we analyze the performance of the three policies $\pi$, $\pi^{b}$, and
$\pi^{\prime}$ within a batch. We show that if at the beginning of a batch the
online policy $\pi$ is not worse than the batch policy $\pi^{b}$, which in
turn is not worse than the online “short” policy $\pi^{\prime}$, then, by the
end of the batch, we get the corresponding regrets being related reversely.
Next, exploiting the fact that $K=2$ and using Assumption 2.1, we establish
that the transition from the end of one batch to the beginning of the next
batch retains the relation between policies. Finally, we put both steps
together and verify that the total regret satisfies the inequality (3).

Within batch. Assume that in timestep $t_{j}$ the decision rule of the online
policy is not worse that than the decision rule of the batch policy, which is
not worse than the decision rule of the online “short” policy,
$\pi_{t_{j}}\geq\pi^{b}_{t_{j}}\geq\pi^{\prime}_{t_{j}}$. Since the online
policy $\pi$ improves within a batch (by Assumption 2.2) and both the batch
policy $\pi^{b}$ and online “short” policy $\pi^{\prime}$ remain the same
within a batch (by the definition of batch policy), by applying Lemma 2.5 we
have $\pi_{t}>\pi^{b}_{t}\geq\pi^{\prime}_{t}$ for any timestep
$t_{j}<t<t_{j+1}$. So, starting at the beginning of a batch with
$\pi_{t_{j}}\geq\pi^{b}_{t_{j}}\geq\pi^{\prime}_{t_{j}}$ leads us to
$\pi_{t_{j+1}-1}>\pi^{b}_{t_{j+1}-1}\geq\pi^{\prime}_{t_{j+1}-1}$ at the end
of the batch.

Between batches. Let $H_{t_{j}-1}$, $H^{b}_{t_{j}-1}$, $H^{\prime}_{t_{j}-1}$
be histories collected by policies $\pi$, $\pi^{b}$, $\pi^{\prime}$ by the
timestep $t_{j}$, correspondingly. Transiting from timestep $t_{j}-1$ to
timestep $t_{j}$ leads us to a new batch, and all policies are being updated
in this step. To show that the relation between batch policy and its bounds
holds, we need to analyze how much information was gained by three policies,
namely, we need to show that

$\mathbb{E}\left[T_{a^{\ast}}(\pi,t_{j})\right]\geq\mathbb{E}\left[T_{a^{\ast}}(\pi^{b},t_{j})\right]\geq\mathbb{E}\left[T_{a^{\ast}}(\pi^{\prime},t_{j})\right].$

This is where we make the use of the fact that $K=2$. Then, we just apply
Assumption 2.1. ∎

The full proof of Theorem 3.1 is presented in Appendix B.2.

##  4 Batch learning for stochastic linear bandits

So far, we have concentrated on the stochastic bandit problem with two
actions. We now conclude with an analysis of the general stochastic linear
bandit problem introduced in Section 2.1. As we mentioned in the proof of
Theorem 3.1, in the case of $K=2$, it immediately follows that the more often
a decision rule chooses the optimal action, the better it is. In contrast,
this is not generally true when $K>2$. Indeed, some decision rules might value
the optimal and the worst actions so that another decision rule that puts less
weight on optimal action is better (because it chooses interim actions more
often at the expense of worst action). Consequently, the case of $K>2$
introduces a new subtlety and requires a number of additional steps in the
analysis.

Because of the subtlety above, we split the main result into two separate
statements. First, we analyze batch and “short” online policies.

######  Theorem 4.1.

Let $\pi^{b}$ be a batch specification of a given policy $\pi$ and
$M=\frac{n}{b}$. Suppose that assumptions 2.1 and 2.2 hold. Then, for $b>1$,

$\displaystyle R_{n}(\pi^{b})\leq bR_{M}(\pi).$

###### Proof outline.

Both policies start off similarly, but “short” online policy starts lagging
behind after the first batch because it “throws away” a lot of information. As
a result, “short” online policy will never overtake batch policy. ∎

Next, we introduce two meta-algorithms that allow us to derive result similar
to Theorem 3.1 —specifically, utilizing Assumptions 2.3 and 2.4, we consider
the instance-independent and the instance-dependent cases separately (Theorem
4.2 and 4.4 correspondingly). While the instance-independent case has the
opportunity to forge a truly integrative result, providing a comprehensive
analysis of a worst-case regret, the instance-dependent case allows conducting
a more thorough analysis of stochastic bandits, offering potentially tighter
bounds.

###  4.1 Instance-independent analysis

Algorithm 1 Learning with delayed start

Input: horizon $n\geq 0$, candidate policy $\pi$, naïve policy $\pi^{0}$,
monotonic lower bound $f$

$t\leftarrow 1$

$H_{0}\leftarrow\emptyset$

$\tau=\min_{j}\\{t_{j}:f(t_{j})>0\\}$

repeat

$A_{t}\leftarrow\pi^{0}(\cdot)$

$H_{t}\leftarrow$ UpdateHistory

$t\leftarrow t+1$

until $t<min\\{\tau,n\\}$

repeat

$A_{t}\leftarrow\pi(\cdot|H_{t-1})$

$H_{t}\leftarrow$ UpdateHistory

$t\leftarrow t+1$

until $t\leq n$

#### Intuition.

From Assumption 2.3, it follows that after timestep $\tau:=\min\\{t:f(t)>0\\}$
policy $\pi$ in the worst-case: (i) chooses the optimal action with non-zero
probability; and (ii) acts more optimally within each consequent timestep. As
such, while batch and online “short” policies ($\pi^{b}$ and $\pi^{\prime}$)
remain the same, online policy $\pi$ gets better in the worst case and,
therefore, chooses optimal action more often, providing lower regret. Thus, to
get the desired result for the general case, it is enough to split the horizon
$n$ into two phases: before and after timestep $\tau$, and ensure that all
three policy specifications behave similarly during the first phase. That is
to say, some naïve policy $\pi^{0}$ operates independently of history $H_{t}$
during phase 1.

To capture the logic above, we adjust the learning process, which can be
represented as a meta-algorithm built upon a given policy $\pi$ (see Algorithm
1). As the name suggests, while performing naïvely during phase 1, Algorithm 1
keeps all three specifications’ regrets similar and, therefore, allows
formulating the following result. 444Note that UpdateHistory can be
implemented differently depending on a particular task or specification (see
Appendix A.5 for more details).

######  Theorem 4.2.

Let $\pi^{b}$ be a batch specification of a given policy $\pi$,
$M=\frac{n}{b}$. Suppose that assumptions 2.1, 2.2, and 2.3 hold. Also, assume
that policy $\tilde{\pi}$ represents a policy constructed following Algorithm
1 for a given candidate policy $\pi$. Then, for $b>1$,

$\displaystyle\underline{R_{n}(\tilde{\pi})}<$
$\displaystyle\underline{R_{n}(\tilde{\pi}^{b})}\leq
b\underline{R_{M}(\tilde{\pi})},$

where $\underline{R_{n}(\pi)}$ is the worst case-regret.

###### Proof outline.

First, we split the total regret into two terms and notice that the first term
is the same for all three regrets, as the same naïve policy $\pi^{0}$ operates
during the first phase:

$\displaystyle R_{n}(\tilde{\pi})$
$\displaystyle=R_{1:\tau-1}(\pi^{0})+R_{\tau:n}(\pi).$

Let $A_{t}^{*}=\arg\max_{\mathcal{A}_{t}}\langle\theta_{*},a\rangle$ be an
optimal action for round $t$. Next, we express the second term as a sum of
instantaneous regrets and exploit Assumption 2.3:

$\displaystyle R_{\tau:n}(\pi)$
$\displaystyle=\mathbb{E}\left(\sum_{t}\langle\theta_{*},A_{t}^{*}-A_{t}\rangle\right)$
$\displaystyle=\sum_{t}\sum_{a}\langle\theta_{*},A_{t}^{*}-a\rangle\pi_{t}\left(a\right)$
$\displaystyle\leq\sum_{t}\sum_{a\neq
A_{t}^{*}}\langle\theta_{*},A_{t}^{*}-a\rangle
f_{a}\left(t\right)=\underline{R_{\tau:n}(\pi)}.$

Finally, we reproduce Theorem 3.1 for $\underline{R_{\tau:n}(\pi)}$, changing
assumption $K=2$ on the properties of function $f(t)$. More precisely, instead
of using an assumption of $K=2$, we use: (i) $f_{a}$ is nonincreasing for any
suboptimal action $a$ and (ii) $f$ is increasing with high probability.
Because of these two facts,
$\bar{\pi}_{l}>\bar{\pi}^{b}_{l}\geq\bar{\pi}^{\prime}_{l}$ implies
$\bar{\pi}_{l}(A_{t}^{*})>\bar{\pi}^{b}_{l}(A_{t}^{*})\geq\bar{\pi}^{\prime}_{l}(A_{t}^{*})$
for $1\leq l<j$. Putting all the steps together, we get:

$\displaystyle\underline{R_{n}(\tilde{\pi})}$
$\displaystyle:=R_{1:\tau-1}(\pi^{0})+\underline{R_{\tau:n}(\pi)}$
$\displaystyle\leq
R_{1:\tau-1}(\pi^{0})+\underline{R_{\tau:n}(\pi^{b})}=:\underline{R_{n}(\tilde{\pi}^{b})}$
$\displaystyle\leq
R_{1:\tau-1}(\pi^{0})+b\underline{R_{\tau:n}(\pi)}=:b\underline{R_{M}(\tilde{\pi})}.$

∎

######  Remark 4.3.

Note that there are two critical differences between Theorems 3.1 and 4.2: the
presence of Algorithm 1 and the worst-case regret bounds in the latter. Both
differences have the same root – monotonic lower bound imposed on the
probability of choosing the optimal action (Assumption 2.3). In order to
provide the same result in Theorem 4.2 as in Theorem 3.1, one would need a
similar assumption imposed on the exact probability of choosing the optimal
action. However, this would be a very restrictive assumption.

###  4.2 Instance-dependent analysis

Algorithm 2 Approximate learning with delayed start

Input: horizon $n\geq 0$, candidate policy $\pi$, number of actions $K$,
monotonic lower bound $f_{\cdot}$, confidence level $\delta$

$\pi^{0}\leftarrow Unif(K)$

$phase1\leftarrow\texttt{False}$

$t\leftarrow 1$

$H_{0}\leftarrow\emptyset$

repeat

$A_{t}\leftarrow\pi^{0}(\cdot)$

$H_{t}\leftarrow$ UpdateHistory

$phase1\leftarrow$ CheckPhase($H_{t}$, $\delta$)

$t\leftarrow t+1$

until ($phase1$ is False and $t\notin\mathcal{T}$ ) or $t\leq n$

repeat

$A_{t}\leftarrow\pi(\cdot|H_{t-1})$

$H_{t}\leftarrow$ UpdateHistory

$t\leftarrow t+1$

until $t\leq n$

The instance-dependent analysis involves the concept of more or less
’difficult’ environments for the agent to learn in. Theoretically, this
concept makes no sense in linear bandits as it depends on actions at the
agent’s disposal. 555 Intuitively, if $|\mathcal{A}_{t}|=\infty$ (e.g.,
$\mathcal{A}_{t}=\\{a:\left\lVert a\right\rVert_{2}\leq t\\}$), each
environment would be the same for the agent as for each timestep $t$ and any
instance $\theta_{*}$ there is the unique optimal arm $A_{t}^{*}$, but no the
second best action. In contrast, if $|\mathcal{A}_{t}|<\infty$, changes in the
instance vector parameter $\theta_{*}$ would lead to other environments, but
whether those environments are more or less ’difficult’ depends on
$\mathcal{A}_{t}$. If $A_{t}^{*}$ varies over time, there also might be a case
that change in the instance parameter $\theta_{*}$ would lead to more
difficult environments for some timesteps but less difficult for others; and
the overall result would be incomparable.  Therefore, we consider the case of
stochastic bandits further. Recall that in this case
$\mathcal{A}_{t}=\\{e_{1},...,e_{K}\\}$ for all $t$,
$\mathcal{A}:=\mathcal{A}_{t}$, and the instance is presented by true rewards
$\theta_{*}=(\mu_{1},...,\mu_{K})$.

#### Intuition.

Similar to the previous section, by Assumption 2.4, after timestep
$\tau_{\theta_{*}}:=\min\\{t:f_{\theta_{*}}(t)>1/K\\}$ policy $\pi$ in the
worst-case scenario: (i) behaves better than the policy that acts uniformly at
random; and (ii) acts more optimally within each consequent timestep. However,
it now depends on vector of rewards $\theta_{*}$, which is unknown for policy
$\pi$, and, as a consequence, we do not know where we should stop phase 1 to
bring the previous reasoning to life. But what if one could find an estimate
$\hat{\tau}$ of true $\tau_{\theta_{*}}$ such that
$f_{\theta_{*}}(\hat{\tau})$ is greater than $1/K$ with high probability for
some confidence level $\delta$ (i.e.,
$\mathbb{P}(f_{\theta_{*}}(\hat{\tau})>1/K)>1-\delta$)? Then we could split
the original horizon $n$ into two parts (phases) and: (i) run a uniform random
policy in phase 1 (before timestep $\hat{\tau}$); and (ii) apply policy $\pi$
in phase 2 (after timestep $\hat{\tau}$). Algorithm 2 illustrates the logic
above. 666There is a slight difference between Algorithms 1 and 2 in the
definition of $\tau$ and naïve policies. The reason is that we take advantage
of knowing $K$ in the latter case. Therefore, we can assume that $\pi^{0}$ is
a uniform policy and define $\tau$ as timestep when a candidate policy $\pi$
is better than uniform policy in the worst-case. Note that procedure
CheckPhase plays a crucial role in the analysis and discussed separately after
the main result.

######  Theorem 4.4.

Let $\pi^{b}$ be a batch specification of a given policy $\pi$,
$M=\frac{n}{b}$, and CheckPhase be with the failure probability $\delta$
(Theorem 4.6). Suppose that assumptions 2.1, 2.2, and 2.4 hold. Also, assume
that policy $\tilde{\pi}$ represents a policy constructed following Algorithm
2 for a given candidate policy $\pi$. Then, for $b>1$,

$\displaystyle\underline{R_{n}(\tilde{\pi})}<$
$\displaystyle\underline{R_{n}(\tilde{\pi}^{b})}\leq
b\underline{R_{M}(\tilde{\pi})}$

with probability $1-\delta$, where $\underline{R_{n}(\pi)}$ is the worst-case
regret.

######  Remark 4.5.

It may seem that Theorem 4.4 provides a worse result than Theorem 4.2, whereas
it requires additional analysis of CheckPhase procedure. However, as mentioned
in Section 2.3, instance-dependent bounds are usually tighter than universal
ones. Therefore, even though Theorem 4.4 holds with probability $1-\delta$, it
can provide tighter bounds.

####  CheckPhase procedure

Since function $f_{\theta}$ decreases in its instance argument in a certain
sense (point (iv), Assumption 2.4), it suffices to find a more “difficult”
environment with instance $\hat{\theta}$ (and corresponding
$\hat{\tau}:=\min\\{t:f_{\hat{\theta}}(t)>1/K\\}$), such that
$\mathbb{P}(f_{\theta_{*}}(\hat{\tau})>1/K)>1-\delta$). Intuitively, the
smaller the difference between a suboptimal and the optimal actions
($\Delta_{a}:=\max_{a}\mu_{a}-\mu_{a}$), the more difficult it is to
distinguish the optimal action and, therefore, the probability of choosing the
optimal action should be smaller. Imagine now that after timestep $t$, we have
some estimate $\tilde{\theta}_{t}$ of the unknown parameter vector
$\theta_{*}$ and confidence set $\mathcal{C}_{t}$ that contains $\theta_{*}$
with high probability. Then, we can choose $\hat{\theta}$ that underestimates
the true reward along the current best action and overestimates the true
rewards along all other actions. Since the true rewards are independent of
each other in stochastic bandits, we are able to do it, whereas in the linear
bandit case, we would get a conflict among possible $\hat{\theta}$. Algorithm
3 formalize the logic above.

Algorithm 3 CheckPhase

Input: history $H_{t}$, confidence level $\delta$

$phase1=\texttt{True}$

$i=\arg\max_{j}\hat{\mu}_{j}(t)$

$LCB_{i,t}=\sqrt{\frac{\ln t}{T_{i}(t)}}$

$l=\arg\max_{j\neq i}\hat{\mu}_{j}(t)$

for $l\neq i$ do

$UCB_{l,t}=\sqrt{\frac{\ln t}{T_{l}(t)}}$

end for

$\hat{\theta}=\left(\hat{\mu}_{i}(t)-LCB_{i,t},\bigcup_{l\neq
i}\hat{\mu}_{l}(t)+UCB_{l,t}\right)$

if $f_{\hat{\theta}}(t)>1/K$ and $2K/t^{2}<\delta$ then

$phase1=\texttt{False}$

end if

return $phase1$

######  Theorem 4.6.

CheckPhase procedure presented in Algorithm 3 is with the failure probability
$\delta$.

The complete proofs of Theorems 4.1, 4.2, 4.4, and 4.6 can be found in
Appendices B.3, B.4, B.5, and B.6, respectively.

##  5 Empirical analysis

We perform experiments on two different applications: simulated stochastic
bandit environments; and a contextual bandit environment, learned from the
logged data in an online marketing campaign. We examine the effect of batch
learning on Thompson Sampling (TS) and Upper Confidence Bound (UCB) policies
for the stochastic problems, and linear Thompson Sampling (LinTS) (Chapelle
and Li, 2011) and linear Upper Confidence Bound (LinUCB) (Li et al., 2010) for
the contextual problem.

Simulated environments. We present some simulation results for the Bernoulli
bandit problem. We create three environments with different mean rewards for
each $K=2$ and $K=4$. Table 1 summarizes information about vectors of mean
rewards used in the environments.

Real data. We also consider batch learning in a marketing campaign on the KPN
777a dutch telecommunications provider logged dataset. KPN has recently used
three different campaigns to sell an extra broadband subscription to their
customers. In the current dataset, a randomly selected set of customers
received randomly one of the three campaigns. The data contains a sample of a
campaign selection from October 2019 until June 2020 combined with customer
information. We adopt an unbiased offline evaluation method (Li et al., 2011)
to compare various bandit algorithms and batch size values. We use conversion
rate (CR) as the metric of interest, defined as the ratio between the number
of successful interactions and the total number of interactions. To protect
business-sensitive information, we only report relative conversion rate;
therefore, Figure 2 demonstrates the CR returned by the off-policy evaluation
algorithm relatively to the online performance.

(a) 2-arm environments performance.

(b) 4-arm environments performance.

Figure 1: Empirical regret performance by batches. The plots are averaged over
500 repetitions.

Results. 888The source code of the experiments can be found in
https://github.com/danilprov/batch-bandits. Figure 1 shows the regret of two
algorithms in six environments across the batch size. As expected, the regret
has an upward trend as batch size increases. It can be seen that, for both
algorithms, the impact of batch learning depends on environment parameters:
the bigger a suboptimality gap, the stronger the impact of batching.

While the exact behavior of the batch learning is still not understood (and it
pretty much depends on an algorithm rather than the experiment design), we can
see a clear difference between a randomized policy and a deterministic one.
Indeed, TS turns out to be much more robust to the impact of batching, whereas
the UCB algorithm fluctuates considerably as batch size increases. The results
for the real data confirm this fact as well: from Figure 2 we observe that the
impact of batching is milder for randomized policy (LinTS) than for
deterministic policy (LinUCB) in contextual problem.

It is important to note that both experiments demonstrate results consistent
with the theoretical analysis conducted in Sections 3 and 4. As the upper
bound in Theorem 4.1 suggests, the performance metric reacts evenly to the
increasing/decreasing of the batch size. Finally, although it was not an
initial goal, we recommend resorting to randomized policies when it becomes
necessary to learn in batches.

Figure 2: Empirical conversion rate by batches. The plots are averaged over 20 repetitions. Table 1: Description of the environments. 2-arm environments | 4-arm environments
---|---
Name | Rewards | Name | Rewards
$env1$ | [0.7, 0.5] | $env4$ | [0.35, 0.18, 0.47, 0.61]
$env2$ | [0.7, 0.4] | $env5$ | [0.40, 0.75, 0.57, 0.49]
$env3$ | [0.7, 0.1] | $env6$ | [0.70, 0.50, 0.30, 0.10]

##  6 Conclusion

We have presented a systematic approach for batch learning in stochastic
linear bandits. The contribution of this paper is twofold. First, we have
introduced a new perspective of batched bandits emphasizing the importance of
the batch size effect. In contrast, most of the work on batched bandits
assumes that the batch size is a parameter to be optimized. Second, we have
shown the actual effect of batch learning by conducting a comprehensive
theoretical analysis, which is confirmed by our strong empirical results.
Practically speaking, we have investigated one component of the performance-
computational cost trade-off and demonstrated that it deteriorates gradually
depending on the batch size. Thus, to find a suitable batch size,
practitioners should take the necessary steps to estimate the second component
(engineering costs) based on computational capabilities.

An interesting direction concerning future work would be to consider batch
learning with varying decision rules within batches. That is, even though the
agent does not receive any information within a batch, it might leverage two
kinds of information to make more intelligent decisions. The first and natural
recourse of information is the actual experience from the past batches. The
second source of information is simulated experience: experience simulated by
a model of the environment and combined with the agent’s behavior in the
current batch. Studying how to integrate actual knowledge and simulated
experience to perform more optimally within a batch would potentially lead to
tighter bounds between batch and online learning.

##  7 Acknowledgements

This project is partially financed by the Dutch Research Council (NWO) and the
ICAI initiative in collaboration with KPN, the Netherlands.

## References

  * Agrawal et al. (2016) Shipra Agrawal, Karl Stratos, and Lee Jang Sun.  Lecture: Ucb algorithm.  https://ieor8100.github.io/mab/Lecture%203.pdf, 2016.
  * Anantharam et al. (1987) Venkat Anantharam, Pravin Varaiya, and Jean C. Walrand.  Asymptotically efficient allocation rules for the multiarmed bandit problem with multiple plays-part ii: Markovian rewards.  _IEEE Transactions on Automatic Control_ , 1987.
  * Athey and Wager (2020) Susan Athey and Stefan Wager.  Policy learning with observational data, 2020.
  * Auer and Ortner (2010) Peter Auer and Ronald Ortner.  Ucb revisited: Improved regret bounds for the stochastic multi-armed bandit problem.  _Periodica Mathematica Hungarica_ , 2010.
  * Bertsimas and Mersereau (2007) Dimitris Bertsimas and Adam Mersereau.  A learning approach for interactive marketing to a customer segment.  _Operations Research_ , 2007.
  * Cesa-Bianchi et al. (2013) Nicolò Cesa-Bianchi, Ofer Dekel, and Ohad Shamir.  Online learning with switching costs and other adaptive adversaries.  In _Advances in Neural Information Processing Systems_ , 2013.
  * Chapelle and Li (2011) Olivier Chapelle and Lihong Li.  An empirical evaluation of thompson sampling.  In J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , 2011.
  * Dimakopoulou et al. (2018) Maria Dimakopoulou, Zhengyuan Zhou, Susan Athey, and Guido Imbens.  Estimation considerations in contextual bandits, 2018.
  * Esfandiari et al. (2021) Hossein Esfandiari, Amin Karbasi, Abbas Mehrabian, and Vahab Mirrokni.  Regret bounds for batched bandits.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 2021\.
  * Gao et al. (2019) Zijun Gao, Yanjun Han, Zhimei Ren, and Zhengqing Zhou.  Batched multi-armed bandits problem.  In _Advances in Neural Information Processing Systems_ , 2019.
  * Han et al. (2020) Yanjun Han, Zhengqing Zhou, Zhengyuan Zhou, Jose Blanchet, Peter W. Glynn, and Yinyu Ye.  Sequential batch learning in finite-action linear contextual bandits, 2020\.
  * Hill et al. (2017) Daniel N. Hill, Houssam Nassif, Yi Liu, Anand Iyer, and S.V.N. Vishwanathan.  An efficient bandit algorithm for realtime multivariate optimization.  _Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_ , 2017.
  * Joachims et al. (2018) Thorsten Joachims, Adith Swaminathan, and Maarten de Rijke.  Deep learning with logged bandit feedback.  In _International Conference on Learning Representations_ , 2018.
  * Joulani et al. (2013) Pooria Joulani, András György, and Csaba Szepesvari.  Online learning under delayed feedback.  In _ICML_ , 2013.
  * Jun et al. (2016) Kwang-Sung Jun, Kevin Jamieson, Robert Nowak, and Xiaojin Zhu.  Top arm identification in multi-armed bandits with batch arm pulls.  In _Proceedings of the 19th International Conference on Artificial Intelligence and Statistics_ , 2016.
  * Jun et al. (2017) Kwang-Sung Jun, Aniruddha Bhargava, Robert Nowak, and Rebecca Willett.  Scalable generalized linear bandits: Online computation and hashing.  In _Advances in Neural Information Processing Systems_ , 2017.
  * Kalkanli and Ozgur (2021) Cem Kalkanli and Ayfer Ozgur.  Batched thompson sampling, 2021.
  * Lattimore and Szepesvári (2020) Tor Lattimore and Csaba Szepesvári.  _Bandit Algorithms_.  Cambridge University Press, 2020.
  * Li et al. (2010) Lihong Li, Wei Chu, John Langford, and Robert E. Schapire.  A contextual-bandit approach to personalized news article recommendation.  _Proceedings of the 19th international conference on World wide web - WWW ’10_ , 2010.
  * Li et al. (2011) Lihong Li, Wei Chu, John Langford, and Xuanhui Wang.  Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms.  _Proceedings of the fourth ACM international conference on Web search and data mining - WSDM ’11_ , 2011.
  * Perchet et al. (2016) Vianney Perchet, Philippe Rigollet, Sylvain Chassang, and Erik Snowberg.  Batched bandit problems.  _The Annals of Statistics_ , 2016.
  * Pike-Burke et al. (2018) Ciara Pike-Burke, Shipra Agrawal, Csaba Szepesvari, and Steffen Grünewälder.  Bandits with delayed, aggregated anonymous feedback.  In _ICML_ , 2018.
  * Provodin et al. (2021) Danil Provodin, Pratik Gajane, Mykola Pechenizkiy, and Maurits Kaptein.  The impact of batch learning in stochastic bandits.  in NeurIPS Workshop on Ecological Theory of Reinforcement Learning, 2021.
  * Schwartz et al. (2013) Eric Schwartz, Eric Bradlow, and Peter Fader.  Customer acquisition via display advertising using multi-armed bandit experiments.  _SSRN Electronic Journal_ , 2013.
  * Swaminathan and Joachims (2015) Adith Swaminathan and Thorsten Joachims.  Batch learning from logged bandit feedback through counterfactual risk minimization.  _Journal of Machine Learning Research_ , 2015.
  * Vernade et al. (2017) Claire Vernade, Olivier Cappé, and Vianney Perchet.  Stochastic Bandit Models for Delayed Conversions.  In _Conference on Uncertainty in Artificial Intelligence_ , 2017\.
  * Zhou et al. (2018) Zhengyuan Zhou, Susan Athey, and Stefan Wager.  Offline multi-action policy learning: Generalization and optimization, 2018.

##  Appendix A Supplementary Discussions

###  A.1 Intuition behind Assumption 2.1

The exploration-exploitation trade-off is a fundamental dilemma between
choosing an action that reveals the most information and provides the highest
immediate reward. In a nutshell, policies that satisfy Assumption 2.1 are good
in leveraging exploration and exploitation decisions in the following sense:

  * •

if the policy gets to a situation when the optimal action has a smaller
confidence interval on average (i.e., it chose the optimal action more often)
, and the past choices were reasonable (i.e., history $H_{t}$ brought either
the highest reward or the most information), then this policy will make a
better consequent decision;

  * •

if another history $H_{t}^{\prime}$ were fed to the policy, that would imply
not optimal leveraging of exploration and exploitation decisions and, as a
result, lead to (i) fewer choices of optimal actions (or higher uncertainty);
and (ii) worse subsequent decisions.

In other words, a policy with history $H_{t}$ will be ahead of any different
history $H_{t}^{\prime}$ from exploration-exploitation perspective. And in
combination with Assumption 2.2 that would lead to better subsequent
decisions.

###  A.2 Intuition behind Assumption 2.2

In what follows, we show that Assumption 2.2 is essential because if it does
not hold, then the lower bounds in Theorems 3.1, 4.2, and 4.4 is greater than
the upper bound: $R_{n}(\pi)>bR_{M}(\pi).$

######  Lemma A.1.

Suppose that the opposite to Assumption 2.2 holds for a given policy $\pi$.
Then

$R_{n}(\pi)>bR_{M}(\pi).$

###### Proof.

Suppose Assumption 2.2 does not hold for $\pi$ (e.g., it makes a lot of
suboptimal choices). In that case, an online “short” policy could perform
better as it omits these suboptimal choices. Indeed, using Assumption 2.2 for
horizons $M$ and $n$, we have

$\frac{R_{M}(\pi)}{M}\geq\frac{R_{n}(\pi)}{n},$

and, therefore, multiplying by $n$, and $M$ respectively and using $n=Mb$, we
get

$bMR_{M}(\pi)>MR_{n}(\pi).$

Finally, dividing by $M$, we get

$bR_{M}(\pi)>R_{n}(\pi).$

∎

###  A.3 Equivalence of Assumptions 2.2 and 2.3

Here, we discuss a link between Assumptions 2.2 and 2.3. Generally, neither of
the assumptions implies another. Nevertheless, there is a strong connection
between these assumptions.

On the one hand, Assumption 2.3 may seem more restrictive, as it imposes the
strictly increasing lower bound on the probability of choosing the optimal
arm, whereas Assumption 2.2 is satisfied as long as the ”rate” of increasing
of the total regret decreases (which does not necessarily require the strictly
increasing probability of choosing the optimal arm over time). In contrast,
Assumption 2.3 only requires increasing lower bound, while 2.2 requires the
decreasing rate of the actual total regret. In fact, the strictly increasing
lower bound on the probability of choosing the optimal arm (Assumption 2.3) is
equivalent to the decreasing rate of the worst-case total regret (adjusted
Assumption 2.2):

$\displaystyle f\text{ -- strictly increasing
}\Leftrightarrow\left(\underline{R_{n_{1}}(\pi)}\right)/n_{1}>\left(\underline{R_{n_{2}}(\pi)}\right)/n_{2}.$

Moreover, these assumptions are equivalent under certain conditions,
summarized in the following lemma.

######  Lemma A.2.

Consider a stochastic bandit problem with $K=2$ arms, then Assumptions 2.2 and
2.3 are equivalent.

###### Proof.

Recall that in 2-armed stochastic bandit $\theta_{*}=(\mu_{a})_{a\in[1,2]}$ \-
a vector of true rewards for each action (arm). Without loss of generality,
assume that arm 1 is optimal. Define a number of times policy $\pi$ has played
an arm $a$ by timestep $t$ as
$T_{a}(t)=\sum_{s=1}^{t}\mathbb{I}\\{A_{t}=a\\}$. Using the regret
decomposition lemma (Lemma 4.5, Lattimore and Szepesvári [2020]), we can
derive:

$\displaystyle\frac{R_{n_{1}}(\pi)}{n_{1}}>\frac{R_{n_{2}}(\pi)}{n_{2}}\Leftrightarrow\frac{\mathbb{E}\left[T_{2}(n_{1})\right]}{n_{1}}>\frac{\mathbb{E}\left[T_{2}(n_{2})\right]}{n_{2}}$

From frequentist probability perspective,
$\frac{\mathbb{E}\left[T_{2}(n_{1})\right]}{n_{1}}$ can be interpreted as
probability of choosing arm 2: $\mathbb{P}\left(A_{n_{1}}=2\right)$. As such,
$f_{2}(t):=\mathbb{P}\left(A_{t}=2\right)$ is an decreasing function and
$f(t):=1-f_{2}(t)$ is an increasing function. Clearly, $\pi_{t}(2|H_{t-1})\leq
f_{2}(t)$. Thus, all the conditions of Assumption 2.3 are satisfied. ∎

While everything we discussed here holds for Assumption 2.4 as well, we
provide a more concrete discussion of Assumption 2.4 in the next section.

###  A.4 Illustration of Assumptions 2.4

Here, we provide a specific example of a policy that satisfies Assumption 2.4.
We consider the stochastic multi-armed bandit problem and examine the UCB
family of algorithms.

######  Lemma A.3 (Lemma 1.2, [Agrawal et al., 2016]).

Let $T_{a}(t)$ be the number action $a$ is chosen by UCB algorithm run on
instance $\theta_{*}=(\mu_{1},...,\mu_{K})$ of the stochastic multi-armed
bandit problem. Then, for any action $a\neq\arg\max_{a}\mu_{a}$,

$\mathbb{E}\left[T_{a}(t)\right]\leq\frac{4\ln{t}}{\Delta^{2}_{a}}+8,$

where $\Delta_{a}=\max_{a}\mu_{a}-\mu_{a}$.

From frequentist probability perspective, we can think of
$\frac{\mathbb{E}\left[T_{a}(t)\right]}{t}$ as probability of choosing arm $a$
and, thus, we can set
$f_{\theta_{*},a}(t)=\frac{4\ln(t+1)}{t\Delta^{2}_{a}}+8/t$ which is a
nondecreasing upper bound of the probability of choosing suboptimal arm $a$
(i.e., points (i) and (ii) are satisfied). As Assumption 2.4 suggests, define
$f_{\theta_{*}}$ as
$f_{\theta_{*},a}(t)=1-\sum_{a\neq\arg\max\mu_{a}}f_{\theta_{*},a}(t)$. Note
that $f_{\theta_{*}}(t)$ satisfies points (iii) and (iv) of Assumption 2.4, as
(iii) $f_{\theta_{*},a}(t)$ is actually decreasing function for all $a$ and
all $t>0$; and (iv) $f_{\theta_{*},a}(t)$ is increasing in the instance
argument (as described in Assumption 2.4). Thus, we get a monotonical lower
bound of the probability of choosing the optimal arm.

###  A.5 Policy specifications and UpdateHistory procedure

Throughout the work, we refer to the three specifications of a given policy
$\pi$: online specification $\pi$ (policy $\pi$ itself), batch specification
$\pi^{b}$, and ”short” online specification $\pi^{\prime}$. Here, we discuss
those three specifications in more detail and provide specific examples of
UPDATEHISTORY procedure.

Recall that policy $\pi$ is a sequence of decision rules:
$\pi=\left(\pi_{t}\right)_{t=1}^{n}$. The online specification of policy $\pi$
is policy $\pi$ itself, i.e., policy that updates its decision rules after
each consecutive round (see Algorithm 4). The batch specification of policy
$\pi$ is policy $\pi^{b}$, i.e., policy that operates with the same decision
rule within each batch and updates it only after a batch ends (see Algorithm
5). As we mentioned in Remark 3.2, ”short” online specification $\pi^{\prime}$
is something between online and batch specifications in the following sense
(see Algorithm 6): it updates the history only once in a batch (as the batch
specification does) but only by one observation (as in the online
specification). Here we assume that two consecutive decision rules are equal
if history remains the same, i.e.,
$\pi_{t}(\cdot|H_{t-1})=\pi_{t+1}(\cdot|H_{t})$, if $H_{t}=H_{t-1}$.

Algorithms 4, 5, and 6 are valid examples of UPDATEHISTORY procedure.

Algorithm 4 Online specification of policy $\pi$

Input: policy $\pi$, horizon $n$

$H_{0}\xleftarrow{}\emptyset$

for $t=1...n$ do

$A_{t}\xleftarrow{}\pi_{t}(\cdot|H_{t-1})$

play arm $A_{t}$

observe $X_{t}$

update $H_{t}=H_{t-1}\bigcup\\{A_{t},X_{t}\\}$

end for

Algorithm 5 Batch specification of policy $\pi$

Input: policy $\pi$, horizon $n$

$H_{0}\xleftarrow{}\emptyset$

for $t=1...n$ do

$A_{t}\xleftarrow{}\pi_{t}(\cdot|H_{t-1})$

play arm $A_{t}$

if $t=t_{j}$ then

observe $X_{t_{j-1}+1},...,X_{t_{j}}$

update
$H_{t}=H_{t-1}\bigcup\\{A_{t_{j-1}+1},X_{t_{j-1}+1},...,A_{t_{j}},X_{t_{j}}\\}$

else

$H_{t}=H_{t-1}$

end if

end for

Algorithm 6 “Short” online specification of policy $\pi$

Input: policy $\pi$, horizon $n$

$H_{0}\xleftarrow{}\emptyset$

for $t=1...n$ do

$A_{t}\xleftarrow{}\pi_{t}(\cdot|H_{t-1})$

play arm $A_{t}$

if $t=t_{j}$ then

observe $X_{t_{j-1}+1}$

update $H_{t}=H_{t-1}\bigcup\\{A_{t_{j-1}+1},X_{t_{j-1}+1}\\}$

else

$H_{t}=H_{t-1}$

end if

end for

##  Appendix B Proofs

###  B.1 Proof of Lemma 2.5

1\. First, we need to show that $\bar{\pi}_{t}$ is a decision rule for some
$t$, i.e., $\sum_{a\in\mathcal{A}_{t}}\bar{\pi}_{t}(a)=1$ and
$\bar{\pi}_{t}(a)\geq 0$ for all $a\in\mathcal{A}_{t}$. Indeed,

$\displaystyle\sum_{a\in\mathcal{A}_{t}}\bar{\pi}_{t}(a)$
$\displaystyle=\sum_{a\in\mathcal{A}_{t}}\frac{\sum_{s=1}^{t}\pi_{s}(a)}{t}=\frac{\sum_{s=1}^{t}\sum_{a\in\mathcal{A}_{t}}\pi_{s}(a)}{t}=\frac{\sum_{s=1}^{t}1}{t}=1.$

Since $\pi_{s}(a)\geq 0$ for all $a\in\mathcal{A}_{t}$ and for all $1\leq
s\leq t$, $\bar{\pi}_{t}(a)\geq 0$ for all $a\in\mathcal{A}_{t}$.

Next, we convert $\mathbb{E}[S_{n}]$ into the sum over timesteps and actions:

$\displaystyle\mathbb{E}[S_{n}]$
$\displaystyle=\mathbb{E}\left[\sum_{t}X_{t}\right]=\mathbb{E}\left[\sum_{t}\sum_{a}X_{t}\mathbb{I}\\{A_{t}=a\\}\right]$
$\displaystyle=\mathbb{E}\left[\sum_{t}\sum_{a}\mathbb{E}[X_{t}\mathbb{I}\\{A_{t}=a\\}|A_{t}]\right]$
$\displaystyle=\mathbb{E}\left[\sum_{t}\sum_{a}\langle\theta_{*},a\rangle\mathbb{I}\\{A_{t}=a\\}\right]$
$\displaystyle=\sum_{t}\sum_{a}\langle\theta_{*},a\rangle\mathbb{P}_{\nu,\pi}(A_{t}=a)$
$\displaystyle=\sum_{t}\sum_{a}\langle\theta_{*},a\rangle\pi_{t}(a|H_{t-1}).$

Fix $n_{1},n_{2}:n_{1}<n_{2}$. From Assumption 2.2, we have
$\frac{R_{n_{1}}(\pi)}{n_{1}}>\frac{R_{n_{2}}(\pi)}{n_{2}}$. Expressing the
regret by its definition, one can get

$\frac{\mathbb{E}\left[\sum_{t=1}^{n_{1}}\max_{a\in\mathcal{A}_{t}}\langle\theta_{*},a\rangle-
S_{n_{1}}\right]}{n_{1}}>\frac{\mathbb{E}\left[\sum_{t=1}^{n_{2}}\max_{a\in\mathcal{A}_{t}}\langle\theta_{*},a\rangle-
S_{n_{2}}\right]}{n_{2}},$

and hence
$\frac{\mathbb{E}[S_{n_{2}}]}{n_{2}}-\frac{\mathbb{E}[S_{n_{1}}]}{n_{1}}>0$.

Finally,

$\displaystyle\frac{\mathbb{E}[S_{n_{2}}]}{n_{2}}-\frac{\mathbb{E}[S_{n_{1}}]}{n_{1}}=\frac{\sum_{t=1}^{n_{2}}\sum_{a}\langle\theta_{*},a\rangle\pi_{t}(a|H_{t-1})}{n_{2}}-\frac{\sum_{t=1}^{n_{1}}\sum_{a}\langle\theta_{*},a\rangle\pi_{t}(a|H_{t-1})}{n_{1}}>0.$

The result is completed by rearranging the sums and using the definition of
$\bar{\pi}_{n_{1}},\bar{\pi}_{n_{2}}$.

2\. For $t<n$ we have $\frac{R_{t}(\pi)}{t}>\frac{R_{t+1}(\pi)}{t+1}$. By
subtracting $\frac{R_{t+1}(\pi)}{t}$ from both sides we get:

$\displaystyle\frac{R_{t}(\pi)-R_{t+1}(\pi)}{t}$
$\displaystyle>\frac{tR_{t+1}(\pi)-(t+1)R_{t+1}(\pi)}{t(t+1)},$
$\displaystyle\frac{-(\max_{a\in\mathcal{A}_{t}}\langle\theta_{*},a\rangle-
X_{t+1})}{t}$ $\displaystyle>\frac{-R_{t+1}(\pi)}{(t+1)t},$
$\displaystyle\max_{a\in\mathcal{A}_{t}}\langle\theta_{*},a\rangle-X_{t+1}$
$\displaystyle<\frac{R_{t+1}(\pi)}{t+1},$
$\displaystyle\max_{a\in\mathcal{A}_{t}}\langle\theta_{*},a\rangle-\sum_{a}\langle\theta_{*},a\rangle\pi_{t+1}(a)$
$\displaystyle<\max_{a\in\mathcal{A}_{t}}\langle\theta_{*},a\rangle-\sum_{a}\langle\theta_{*},a\rangle\bar{\pi}_{t+1}(a),$
$\displaystyle\sum_{a}\langle\theta_{*},a\rangle\pi_{t+1}(a)$
$\displaystyle>\sum_{a}\langle\theta_{*},a\rangle\bar{\pi}_{t+1}(a).$

Here, in forth step we used that
$\frac{\sum_{a\in\mathcal{A}_{t}}\sum_{s=1}^{t+1}\pi_{s}(a)}{t+1}=\sum_{a\in\mathcal{A}_{t}}\bar{\pi}_{t+1}(a)$.

###  B.2 Proof of Theorem 3.1

Step 1 (Within batch). Fix $j\geq 1$. Let
$\pi_{t_{j}}\geq\pi^{b}_{t_{j}}\geq\pi^{\prime}_{t_{j}}$. Define an average
decision rule between timesteps $t_{1}$ and $t_{2}$ as
$\bar{\pi}_{t_{1},t_{2}}=\frac{\sum_{s=t_{1}}^{t_{2}-1}\pi_{s}}{t_{2}-1-t_{1}}$;
and an average decision rule in batch $j$ as
$\bar{\pi}_{j}=\frac{\sum_{s=t_{j}}^{t_{j+1}-1}\pi_{s}}{b}$. By the end of
batch $j$, we have:

$\displaystyle\bar{\pi}_{t_{j},t}\stackrel{{\scriptstyle(a)}}{{>}}\bar{\pi}_{t_{j},t_{j}+1}=\pi_{t_{j}}\geq$
$\displaystyle\pi^{b}_{t_{j}}\stackrel{{\scriptstyle(b)}}{{=}}\pi^{b}_{t}\text{,
and}$
$\displaystyle\pi^{b}_{t_{j}}\geq\pi^{\prime}_{t_{j}}\stackrel{{\scriptstyle(c)}}{{=}}\pi^{\prime}_{t},$

for any timestep $t_{j}<t<t_{j+1}$, where $(a)$ follows from Lemma 2.5 (1);
and $(b)$ and $(c)$ hold by the definition of batch policy. Thus, starting
with $\pi_{t_{j}}\geq\pi^{b}_{t_{j}}\geq\pi^{\prime}_{t_{j}}$ at the beginning
of batch $j$ leads us to
$\bar{\pi}_{j}>\bar{\pi}^{b}_{j}\geq\bar{\pi}^{\prime}_{j}$. Moreover, by
Lemma 2.5 (2), we have
$\pi_{t_{j+1}-1}>\pi^{b}_{t_{j+1}-1}\geq\pi^{\prime}_{t_{j+1}-1}$.

Step 2 (Between batches). Fix $j\geq 1$. Let
$\bar{\pi}_{l}>\bar{\pi}^{b}_{l}\geq\bar{\pi}^{\prime}_{l}$ for any batch
$1\leq l<j$. Let $H_{t_{j}-1}$, $H^{b}_{t_{j}-1}$, $H^{\prime}_{t_{j}-1}$ be
histories collected by policies $\pi$, $\pi^{b}$, $\pi^{\prime}$ by the
timestep $t_{j}$, correspondingly. Let
$a^{\ast}=\arg\max_{a}\langle\theta_{*},a\rangle$ be an optimal action.
999Since we have just 2 actions, we automatically assume that the optimal arm
is independent of $t$. Define a number of times we have received a reward from
arm $a$ 101010Usually, it is defined as a number of times action $a$ has been
played but, since the policy $\pi^{\prime}$ plays more arms than receives
rewards, we define it that way. in batch $j$ by policy $\pi$ as
$T_{a}(\pi,j)=\sum_{s=t_{j}}^{t_{j+1}-1}\mathbb{I}\\{A_{t}=a\\}$. Note that
$\mathbb{E}[T_{a}(\pi,j)]=b\cdot\bar{\pi}_{j}(a)$. Since $K=2$,
$\bar{\pi}_{l}>\bar{\pi}^{b}_{l}\geq\bar{\pi}^{\prime}_{l}$ implies
$\bar{\pi}_{l}(a^{\ast})>\bar{\pi}^{b}_{l}(a^{\ast})\geq\bar{\pi}^{\prime}_{l}(a^{\ast})$
for $1\leq l<j$. Hence,
$\mathbb{E}[T_{a^{\ast}}(\pi,l)]>\mathbb{E}[T_{a^{\ast}}(\pi^{b},l)]\geq\mathbb{E}[T_{a^{\ast}}(\pi^{\prime},l)]$
for $1\leq l<j$ and, therefore,
$\sum_{l}\mathbb{E}[T_{a^{\ast}}(\pi,l)]>\sum_{l}\mathbb{E}[T_{a^{\ast}}(\pi^{b},l)]\geq\sum_{l}\mathbb{E}[T_{a^{\ast}}(\pi^{\prime},l)]$.
By applying Assumption 2.1, we have that
$\pi_{t_{j}}>\pi^{b}_{t_{j}}\geq\pi^{\prime}_{t_{j}}$.

Step 3 (Regret throughout the horizon). We assume that the interaction begins
with the online policy, batch policy, and “short” online policy being equal to
each other: $\pi_{1}=\pi^{b}_{1}=\pi^{\prime}_{1}$. Then, from Step 1, by the
end of the first batch, we have
$\bar{\pi}_{1}>\bar{\pi}^{b}_{1}\geq\bar{\pi}^{\prime}_{1}$ and
$\pi_{t_{2}-1}>\pi^{b}_{t_{2}-1}\geq\pi^{\prime}_{t_{2}-1}$. Next, from Step
2, the transition to the second batch retains the relation between policies:
$\pi_{t_{2}}>\pi^{b}_{t_{2}}\geq\pi^{\prime}_{t_{2}}$; and so on. Finally,
summing over $M=\frac{n}{b}$ batches, we have:

$\displaystyle R_{n}(\pi)$
$\displaystyle=\mathbb{E}\left[\sum_{t=1}^{n}\langle\theta_{*},a^{*}\rangle-
S_{n}\right]=\mathbb{E}\left[\sum_{t}\langle\theta_{*},a^{*}-A_{t}\rangle\right]$
$\displaystyle=\sum_{t}\sum_{a}\langle\theta_{*},a^{*}-a\rangle\pi_{t}(a)$
$\displaystyle=b\sum_{j=1}^{M}\sum_{a}\langle\theta_{*},a^{*}-a\rangle\bar{\pi}_{j}(a)$
$\displaystyle<b\sum_{j=1}^{M}\sum_{a}\langle\theta_{*},a^{*}-a\rangle\bar{\pi}^{b}_{j}(a)=R_{n}(\pi^{b})$
$\displaystyle\leq
b\sum_{j=1}^{M}\sum_{a}\langle\theta_{*},a^{*}-a\rangle\bar{\pi}^{\prime}_{j}(a)=bR_{M}(\pi).$

This concludes the proof for the $K=2$ arm case.

###  B.3 Proof of Theorem 4.1

Let $A_{t}^{*}=\arg\max_{\mathcal{A}_{t}}\langle\theta_{*},a\rangle$ be an
optimal action for round $t$, and, unlike Theorem 3.1, denote
$T_{a^{\ast}}(\pi,j)=\sum_{s=t_{j}}^{t_{j+1}-1}\mathbb{I}\\{A_{t}=A_{t}^{*}\\}$
– number of times policy $\pi$ made optimal choice in batch $j$. As in Theorem
3.1, we assume that the interaction begins with the batch policy being equal
to the “short” online policy: $\pi^{b}_{1}=\pi^{\prime}_{1}$. Then, by the end
of the first batch, we have
$\pi^{b}_{1}=\bar{\pi}^{b}_{1}=\bar{\pi}^{\prime}_{1}=\pi^{\prime}_{1}$, as
neither policies receive any feedback within a batch. Next, by the
construction of the “short” online policy and Assumption 2.1, batch policy
must be at least as good as “short” online policy:
$\pi^{b}_{t_{2}}\geq\pi^{\prime}_{t_{2}}$. Indeed, by remark after Theorem
3.1, “short” online policy stores only the first reward from the previous
batch, while batch policy is provided with the information from the whole
batch: $H^{\prime}_{t_{2}-1}=(A_{1},X_{1})$ and
$H^{b}_{t_{2}-1}=(A_{1},X_{1},...,A_{b},X_{b})$. Clearly,
$\mathbb{E}[T_{a^{\ast}}(\pi^{b},b)]\geq\mathbb{E}[T_{a^{\ast}}(\pi^{\prime},b)]$
and, by Assumption 2.1, batch policy starts the second batch being at least as
good as “short” online policy: $\pi^{b}_{t_{2}}\geq\pi^{\prime}_{t_{2}}$.

Similarly, after the second batch, we have
$H^{\prime}_{t_{3}-1}=(A_{1},X_{1},A_{2},X_{2})$ and
$H^{b}_{t_{3}-1}=(A_{1},X_{1},...,A_{2b},X_{2b})$ and
$\mathbb{E}[T_{a^{\ast}}(\pi^{b},2b)]\geq\mathbb{E}[T_{a^{\ast}}(\pi^{\prime},2b)]$,
as $\pi^{b}_{t_{3}}\geq\pi^{\prime}_{t_{3}}$; and so on. In other words, both
policies start off similarly, but “short” online policy starts lagging behind
after the first batch and will never overtake batch policy.

Finally, summing over $M=\frac{n}{b}$ batches, we have:

$\displaystyle R_{n}(\pi^{b})$
$\displaystyle=\mathbb{E}\left(\sum_{t}\langle\theta_{*},A_{t}^{*}-A_{t}\rangle\right)$
$\displaystyle=\sum_{t}\sum_{a}\langle\theta_{*},A_{t}^{*}-a\rangle\pi^{b}_{t}(a)$
$\displaystyle=b\sum_{j=1}^{M}\sum_{a}\langle\theta_{*},A_{t}^{*}-a\rangle\pi^{b}_{t_{j}}(a)$
$\displaystyle\leq
b\sum_{j=1}^{M}\sum_{a}\langle\theta_{*},A_{t}^{*}-a\rangle\pi^{\prime}_{t_{j}}(a)=bR_{M}(\pi).$

###  B.4 Proof of Theorem 4.2

#### Part 1 (Preliminaries).

First, we split the total regret into two terms (representing phase 1 and
phase 2) and notice that the first term is the same for both policies
($\tilde{\pi}$ and $\tilde{\pi}^{b}$), as the same naïve policy $\pi^{0}$
operates during the first phase.

$\displaystyle R_{n}(\tilde{\pi})$
$\displaystyle=R_{1:\tau-1}(\pi^{0})+R_{\tau:n}(\pi),$ $\displaystyle
R_{n}(\tilde{\pi}^{b})$
$\displaystyle=R_{1:\tau-1}(\pi^{0})+R_{\tau:n}(\pi^{b}),$

where
$R_{1:s}(\pi)=\mathbb{E}\left[\sum_{t=1}^{s}\max_{a\in\mathcal{A}_{t}}\langle\theta_{*},a\rangle-
S_{n}\right]$. Note that Algorithm 1 is implemented in such a way that phase 1
can only be ended with the end of the batch and therefore:

$\displaystyle R_{n}(\tilde{\pi}^{\prime})$
$\displaystyle=R_{1:\tau-1}(\pi^{0})+R_{\tau:n}(\pi^{\prime})$
$\displaystyle=R_{1:\tau-1}(\pi^{0})+bR_{\tau:n}(\pi)=bR_{M}(\tilde{\pi}).$

Next, we express the second term as a sum of instantaneous regrets and exploit
Assumption 2.3:

$\displaystyle R_{\tau:n}(\pi)$
$\displaystyle=\mathbb{E}\left(\sum_{t}\langle\theta_{*},A_{t}^{*}-A_{t}\rangle\right)$
$\displaystyle=\mathbb{E}\left(\sum_{t}\sum_{a}\langle\theta_{*},A_{t}^{*}-a\rangle\mathbb{I}\\{A_{t}=a\\}\right)$
$\displaystyle=\sum_{t}\sum_{a}\langle\theta_{*},A_{t}^{*}-a\rangle\mathbb{P}\left(A_{t}=a\right|H_{t-1})$
$\displaystyle=\sum_{t}\sum_{a}\langle\theta_{*},A_{t}^{*}-a\rangle\pi_{t}\left(a\right|H_{t-1})$
$\displaystyle\leq\sum_{t}\sum_{a\neq
A_{t}^{*}}\langle\theta_{*},A_{t}^{*}-a\rangle
f_{\theta,a}\left(t\right)=\underline{R_{\tau:n}(\pi)}.$

The only thing left is to reproduce Theorem 3.1 for
$\underline{R_{\tau:n}(\pi)}$, $\underline{R_{\tau:n}(\pi^{b})}$, and
$\underline{R_{\tau:n}(\pi^{\prime})}$. Specifically, Step 1 remains the same,
as it only involves the general notion of decision rules. Step 3 retains the
same semantic and is only to be rewritten in a general setting; the only
semantic change is expected in Step 2, as we need to release the assumption of
2 actions.

#### Part 2 (Reproducing Theorem 3.1)

Note that in this part, we abuse notation a bit and by
$\pi_{t},\pi^{b}_{t},\pi^{\prime}_{t},\bar{\pi}_{j},\bar{\pi}^{b}_{j},\bar{\pi}^{\prime}_{j}$
we assume its lower and upper bounds provided by Assumption 2.3.

Step 1 (Within batch). Fix $j\geq 1$. Let
$\pi_{t_{j}}\geq\pi^{b}_{t_{j}}\geq\pi^{\prime}_{t_{j}}$. Define an average
decision rule between timesteps $t_{1}$ and $t_{2}$ as
$\bar{\pi}_{t_{1},t_{2}}=\frac{\sum_{s=t_{1}}^{t_{2}-1}\pi_{s}}{t_{2}-1-t_{1}}$;
and an average decision rule in batch $j$ as
$\bar{\pi}_{j}=\frac{\sum_{s=t_{j}}^{t_{j+1}-1}\pi_{s}}{b}$. By the end of
batch $j$, we have:

$\displaystyle\bar{\pi}_{t_{j},t}\stackrel{{\scriptstyle(a)}}{{>}}\bar{\pi}_{t_{j},t_{j}+1}=\pi_{t_{j}}\geq$
$\displaystyle\pi^{b}_{t_{j}}\stackrel{{\scriptstyle(b)}}{{=}}\pi^{b}_{t}\text{,
and}$
$\displaystyle\pi^{b}_{t_{j}}\geq\pi^{\prime}_{t_{j}}\stackrel{{\scriptstyle(c)}}{{=}}\pi^{\prime}_{t},$

for any timestep $t_{j}<t<t_{j+1}$, where $(a)$ follows from Lemma 2.5 (1);
and $(b)$ and $(c)$ hold by the definition of batch policy. Thus, starting
with $\pi_{t_{j}}\geq\pi^{b}_{t_{j}}\geq\pi^{\prime}_{t_{j}}$ at the beginning
of batch $j$ leads us to
$\bar{\pi}_{j}>\bar{\pi}^{b}_{j}\geq\bar{\pi}^{\prime}_{j}$. Moreover, by
Lemma 2.5 (2), we have
$\pi_{t_{j+1}-1}>\pi^{b}_{t_{j+1}-1}\geq\pi^{\prime}_{t_{j+1}-1}$.

Step 2 (Between batches). Fix $j\geq 1$. Let
$\bar{\pi}_{l}>\bar{\pi}^{b}_{l}\geq\bar{\pi}^{\prime}_{l}$ for any batch
$1\leq l<j$. Let $H_{t_{j}-1}$, $H^{b}_{t_{j}-1}$, $H^{\prime}_{t_{j}-1}$ be
histories collected by policies $\pi$, $\pi^{b}$, $\pi^{\prime}$ by the
timestep $t_{j}$, correspondingly. Let
$A_{t}^{*}=\arg\max_{\mathcal{A}_{t}}\langle\theta_{*},a\rangle$ be an optimal
action for round $t$, and, unlike Theorem 3.1, denote
$T_{a^{\ast}}(\pi,j)=\sum_{s=t_{j}}^{t_{j+1}-1}\mathbb{I}\\{A_{t}=A_{t}^{*}\\}$
– number of times policy $\pi$ made optimal choice in batch $j$.

Recall that $f(t)$ is strictly increasing with probability for all $t>\tau$.
As a consequence, using the fact that: (i) $f_{\theta,a}$ is nonincreasing for
any suboptimal action $a$ and (ii) $f_{\theta}$ is increasing with high
probability, $\bar{\pi}_{l}>\bar{\pi}^{b}_{l}\geq\bar{\pi}^{\prime}_{l}$
implies
$\bar{\pi}_{l}(A_{t}^{*})>\bar{\pi}^{b}_{l}(A_{t}^{*})\geq\bar{\pi}^{\prime}_{l}(A_{t}^{*})$
for $1\leq l<j$ and for $0<t<t_{j}$ with probability $1-\delta$. Hence,
$\mathbb{E}[T_{a^{\ast}}(\pi,l)]>\mathbb{E}[T_{a^{\ast}}(\pi^{b},l)]\geq\mathbb{E}[T_{a^{\ast}}(\pi^{\prime},l)]$
for $1\leq l<j$ and, therefore,
$\sum_{l}\mathbb{E}[T_{a^{\ast}}(\pi,l)]>\sum_{l}\mathbb{E}[T_{a^{\ast}}(\pi^{b},l)]\geq\sum_{l}\mathbb{E}[T_{a^{\ast}}(\pi^{\prime},l)]$.
By applying Assumption 2.1, we have that
$\pi_{t_{j}}>\pi^{b}_{t_{j}}\geq\pi^{\prime}_{t_{j}}$.

Step 3 (Regret throughout the horizon). We assume that the interaction begins
with the online policy, batch policy, and “short” online policy being equal to
each other: $\pi_{1}=\pi^{b}_{1}=\pi^{\prime}_{1}$. Then, from Step 1, by the
end of the first batch, we have
$\bar{\pi}_{1}>\bar{\pi}^{b}_{1}\geq\bar{\pi}^{\prime}_{1}$ and
$\pi_{t_{2}-1}>\pi^{b}_{t_{2}-1}\geq\pi^{\prime}_{t_{2}-1}$. Next, from Step
2, the transition to the second batch retains the relation between policies:
$\pi_{t_{2}}>\pi^{b}_{t_{2}}\geq\pi^{\prime}_{t_{2}}$; and so on. Finally,
summing over $M^{\prime}=\frac{n-\tau}{b}$ batches we have:

$\displaystyle\underline{R_{\tau:n}(\pi)}$ $\displaystyle=\sum_{t}\sum_{a\neq
A_{t}^{*}}\langle\theta_{*},A_{t}^{*}-a\rangle\pi_{t}(a)$
$\displaystyle=b\sum_{j=1}^{M^{\prime}}\sum_{a\neq
A_{t}^{*}}\langle\theta_{*},A_{t}^{*}-a\rangle\bar{\pi}_{j}(a)$
$\displaystyle<b\sum_{j=1}^{M^{\prime}}\sum_{a\neq
A_{t}^{*}}\langle\theta_{*},A_{t}^{*}-a\rangle\bar{\pi}^{b}_{j}(a)=\underline{R_{\tau:n}(\pi^{b})}$
$\displaystyle\leq b\sum_{j=1}^{M^{\prime}}\sum_{a\neq
A_{t}^{*}}\langle\theta_{*},A_{t}^{*}-a\rangle\bar{\pi}^{\prime}_{j}(a)=b\underline{R_{\tau:n}(\pi^{\prime})}.$

Putting both parts together, we get:

$\displaystyle\underline{R_{n}(\tilde{\pi})}$
$\displaystyle:=R_{1:\tau-1}(\pi^{0})+\underline{R_{\tau:n}(\pi)}$
$\displaystyle<R_{1:\tau-1}(\pi^{0})+\underline{R_{\tau:n}(\pi^{b})}=:\underline{R_{n}(\tilde{\pi}^{b})}$
$\displaystyle\leq
R_{1:\tau-1}(\pi^{0})+b\underline{R_{\tau:n}(\pi)}=:b\underline{R_{M}(\tilde{\pi})}.$

###  B.5 Proof of Theorem 4.4

The proof of this theorem follows relatively directly from the proof of
Theorem 4.2, taking into account the difference between Algorithm 1 and
Algorithm 2.

First, note that similarly to Algorithm 1, CheckPhase is implemented in such a
way that phase 1 can only be ended with the end of the batch. Secondly, in
contrast to Algorithm 1, phase 1 ends at random timestep $\hat{\tau}$. Finally
and most importantly, phase 1 leads to strictly increasing function
$f_{\hat{\theta}}$ with probability $1-\delta$.

Putting all these observations together, we have:

$\displaystyle\underline{R_{n}(\tilde{\pi})}=\underline{R_{n}(\tilde{\pi}^{b})}=b\underline{R_{M}(\tilde{\pi})}$

with probability $1-\delta$.

###  B.6 Proof of Theorem 4.6

For simplicity, we consider the case $K=2$ first. Recall that in this case
$\theta_{*}=(\mu_{a})_{a\in[1,2]}$ – a vector of true rewards for each action
(arm). Without loss of generality, assume that arm 1 is optimal. Following
Algorithm 3, at timestep $t$ the agent computes estimates $\hat{\mu}_{i}(t)$
and their confidence intervals $LCB_{i,t}$, $UCB_{i,t}$ for $i\in[1,2]$ and
then constructs a new instance

$\hat{\theta}=\left(\hat{\mu}_{1}(t)-LCB_{1,t},\hat{\mu}_{2}(t)+UCB_{2,t}\right).$

There may be three situations, that we will consider separately:

  1. 1.

Confidence intervals do not cover true rewards for arms $1$ or $2$:
$\mu_{1}\notin[\hat{\mu}_{1}(t)-LCB_{1,t},\hat{\mu}_{1}(t)+UCB_{1,t}]$ or
$\mu_{2}\notin[\hat{\mu}_{2}(t)-LCB_{2,t},\hat{\mu}_{2}(t)+UCB_{2,t}]$;

  2. 2.

Confidence intervals cover true rewards for arms $1$ and $2$:
$\mu_{1}\in[\hat{\mu}_{1}(t)-LCB_{1,t},\hat{\mu}_{1}(t)+UCB_{1,t}]$ and
$\mu_{2}\in[\hat{\mu}_{2}(t)-LCB_{2,t},\hat{\mu}_{2}(t)+UCB_{2,t}]$.

First note that

$\langle\hat{\theta},a^{\ast}_{\theta_{*}}-a\rangle<\langle\theta_{*},a^{\ast}_{\theta_{*}}-a\rangle$
(4)

for all $a\neq a^{\ast}_{\theta_{*}}$, where $a^{\ast}_{\theta_{*}}$ is the
best arm in the original environment,
$a^{\ast}_{\theta_{*}}=\max_{a\in\mathcal{A}}\langle\theta_{*},a\rangle$.
Indeed, in stochastic bandit, equation (4) means

$\hat{\mu}_{a^{\ast}_{\theta_{*}}}(t)-LCB_{a^{\ast}_{\theta_{*}},t}-\left(\hat{\mu}_{a}(t)+UCB_{a,t}\right)<\mu_{a^{\ast}_{\theta_{*}}}-\mu$
(5)

Clearly, equation (5) holds under option 2. Therefore, due to the point (iv)
of Assumption 2.4, $f_{\hat{\theta}}(t)<f_{\theta_{*}}(t)$ for all $t>0$. As
such, $\hat{\tau}:=\min\\{t:f_{\hat{\theta}}(t)>1/K\\}$ is greater than true
$\tau$ and, therefore, is a good estimate of the begging of $phase2$ in
Algorithm 2.

According to Hoeffding’s inequality, the first option arises with probability
at most $\delta:=4/t^{2}$. Thus,
$\mathbb{P}(f_{\theta_{*}}(\hat{\tau})>1/K)>1-\delta$.

To extend this result to the case $K>2$, one needs to note that we are
interested in pairwise comparisons of the best action $a^{\ast}$ and a
suboptimal action $a$. Thus, reproducing the logic above for each action
$a\neq a^{\ast}$ and assigning $\delta:=2K/t^{2}$, one can observe the same
result for an arbitrary number of actions $K$.