# Non-Stationary Bandits with Knapsack Problems with Advice

Lixing Lyu  Wang Chi Cheung

###### Abstract

We consider a non-stationary Bandits with Knapsack problem. The outcome
distribution at each time is scaled by a non-stationary quantity that
signifies changing demand volumes. Instead of studying settings with limited
non-stationarity, we investigate how online predictions on the total demand
volume $Q$ allows us to improve our performance guarantees. We show that,
without any prediction, any online algorithm incurs a linear-in-$T$ regret. In
contrast, with online predictions on $Q$, we propose an online algorithm that
judiciously incorporates the predictions, and achieve regret bounds that
depends on the accuracy of the predictions. These bounds are shown to be tight
in settings when prediction accuracy improves across time. Our theoretical
results are corroborated by our numerical findings.

##  1 Introduction

The multi-armed bandit problem (MAB) is a classical model on sequential
decision making. The MAB problem features the trade-off between exploration
and exploitation, i.e., between exploring for new information about the
underlying system and exploiting the potentially optimal solution based on
current information. MAB problems have been studied extensively over many
decades, with diverse applications such as recommendation systems, ad
allocation, resource allocation, revenue management and network
routing/scheduling.

Many of these mentioned applications involve resource constraints. For
example, a seller experimenting with product prices may have limited product
inventory. This motivates the formulation of the bandits with knapsack (BwK)
problem, an online knapsack problem involving model uncertainty introduced by
Badanidiyuru et al. [2013]. The agent has $d\geq 1$ types of resources. At
each time step $t$, the agent pulls an arm, which generates an array of
outcomes consisting of the random reward the amounts of the $d$ resources
consumed. If some resource(s) are exhausted, then the agent stops pulling any
arm. The objective is to maximize the expected total reward over a known
horizon $T$, subject to the budget constraints on the $d$ resources.

The BwK problem was first studied in a stationary stochastic setting, dubbed
_stochastic BwK_ , where the outcome of an arm follows a stationary but latent
probability distribution. Badanidiyuru et al. [2013], Agrawal and Devanur
[2014] provide online algorithms for stochastic BwK with regret sub-linear in
$T$. The regret is the difference between the optimum and the expected
cumulative reward earned by the algorithm, and a sub-linear-in-$T$ regret
implies the convergence to opimality as $T$ grows. An alternative setting,
adversarial BwK, is introduced by Immorlica et al. [2019]. Each arm’s outcome
distribution can change arbitrarily over time. Contrary to stochastic BwK, it
is impossible to achieve a regret sub-linear in $T$, even when the outcome
distribution is changed only once during the horizon [Liu et al., 2022]. It
begs a question: could a non-stationary BwK problem be more tractable under a
less adversarial model than Immorlica et al. [2019], Liu et al. [2022]?

Practically, while stationary models could be a strong assumption, it could be
too pessimistic to assume the underlying model to be adversarily changing and
completely latent. Consider the example of ad allocation. On one hand, the
internet traffic is constantly changing, leading to a non-stationary model. On
the other hand, forecast information is often available. Some advertisements
are intrinsically more attractive than others, regardless of the internet
traffic, meaning that the click probability of an ad can be regarded as
stationary. How could the platform harness the probem structure? Can the
allocator utilize forecast information on the internet traffic to improve
his/her decisions?

Motivated by the discussions above, we consider the Non-Stationary BwK with
Online Advice problem (NS-BwK-OA). An outcome involve an adversarial and a
stochastic component. The mean reward and mean type-$i$ resource consumption
of pulling arm $a$ at time $t$ are equal to $q_{t}\cdot r(a)$ and $q_{t}\cdot
c(a,i)$ respectively. The quantity $q_{t}\in\mathbb{R}_{>0}$ is a seasonal
term that represents the demand volume at time $t$, while the stationary
quantities $r(a),c(a,i)$ are the mean reward earned and resource consumed per
demand unit under arm $a$. In a dynamic pricing setting, $q_{t}$ counts the
customers arrivals at time $t$. The quantities $r(a),c(a,i)$ respectively
represent the revenue earned and type-$i$ resource consumed per customer under
arm $a$, which could represent a pricing scheme. Our proposed outcome model
generalizes the unconstrained settings in [Tracà et al., 2021, Lykouris et
al., 2020]. We make the following novel contributions:

Model. We incoporate a prediction oracle in NS-BwK-OA, a non-stationary BwK
problem. Such an incorporation is novel compared to existing BwK works, which
always assume full model uncertainty. In NS-BwK-OA, we identify the total
demand volume $Q=\sum^{T}_{t=1}q_{t}$ as a crucial (but latent) parameter. The
oracle provides a prediction $\hat{Q}_{t}$ to $Q$ at every time step $t$. The
oracle corresponds to how a firm constantly acquires updated information about
$Q$, and a variety of existing time series prediciton tools can be used to
construct such an oracle.

Regret Lower Bounds.  We derive two regret lower bounds on NS-BwK-OA. First,
without the access to a prediction oracle, we show that any online algorithm
suffers a linear-in-$T$ regret, even when $r,c$ are known and $q_{t}$ is known
before the arm at time $t$ is to be chosen. Second, with the access of a
prediction oracle, we establish regret lower bounds that depend on the
accuracy of the estimations. When the estimates are equal to the groundtruth,
the regret lower bounds reduce to that of the stochastic BwK problem.

Algorithms and Regret Upper Bounds.  We design an online algorithm OA-UCB to
utilize the predictions judiciously. OA-UCB is novel in its incorporation of
the prediction $\hat{Q}_{t}$ and demand volume $q_{t}$ into the estimated
opportunity costs of the resources, in relation to the predicted demand
volumes. We derive a regret upper bound on OA-UCB that depends on the accuracy
of the predictions, even though the accuracy of each prediction is not known
to the algorithm. OA-UCB is shown to achieve near optimal regret bounds when
the accuracy of the predictions improves across time.

Numerical Validations. We perform numerical experiments when
$\\{q_{t}\\}_{t=1}^{T}$ is governed by a time series model. The experiment
highlights the benefit of predicitons. We show that an online algorithm, such
as OA-UCB, that harnesses predictions judiciously can perform empirically
better than existing baselines, which only has access to the bandit feedback
from the latent environment.

###  1.1 Related Work

The Bandits with Knapsacks (BwK) problem has been extensively studied.
Badanidiyuru et al. [2013] first introduced the stochastic BwK problem, which
bears applications in dynamic pricing Besbes and Zeevi [2009, 2012] and ad
allocation Mehta et al. [2007]. The BwK problem is generalized by Agrawal and
Devanur [2014] to incorporate convex constraints and concave reweards. Several
variants are studied, such as the settings of contextual bandits Agrawal et
al. [2016], Badanidiyuru et al. [2014], combinatorial semi-bandits
Sankararaman and Slivkins [2018].

Non-stationary BwK problems, where the outcome distribution of each arm is
changing over time, are studied recently. Immorlica et al. [2019] achieves a
$O(\log T)$ competitive ratio against the best fixed distribution benchmark in
an adversarial setting. Rangi et al. [2018] consider both stochastic and
adversarial BwK problems in the single resource case. Liu et al. [2022] design
a sliding window learning algorithm with sub-linear-in-$T$ regret, assuming
the amount of non-stationarity is upper bounded and known. A sub-linear-in-$T$
regret non-stationary BwK is only possible in restrictive settings. For
example, as shown in Immorlica et al. [2019], Liu et al. [2022] and our
forthcoming Lemma 2, for any online algorithm, there exists a non-stationary
BwK instance where the outcome distribution only changes oncee during the
horizon, for which the algorihtm incurs a linear-in-$T$ regret. Non-stationary
stochastic bandits with no resource constraints are studied in [Besbes et al.,
2014, Cheung et al., 2019, Zhu and Zheng, 2020], who provide sub-linear-in-$T$
regret bounds in less restrictive non-stationary settings than Liu et al.
[2022], while the amount of non-stationariety, quantified as the variational
budget or the number of change points, has to be sub-linear in $T$. Our work
goes in an orthogonal direction. Instead of studying settings with limited
non-stationariety, we seek an improved regret bound when the decision maker is
endowed with information additional (in the form of prediction oracle) to the
online observations.

Our work is related to an active stream of research works on online algorithm
design with machine learned advice Piotr et al. [2019], Mitzenmacher and
Vassilvitskii [2022]. While traditional online algorithm research focuses on
worst case performance guarantee in full model uncertainty setting, this
stream of works focuses on enhancing the performance guarantee when the
decision maker (DM) is provided with a machine learned advice at the start of
the online dynamics. A variety of results are derived in different settings,
such as online caching Lykouris and Vassilvitskii [2021], rent-or-buy Purohit
et al. [2018], scheduling Mitzenmacher [2019], Lattanzi et al. [2020], online
set cover problems Bamas et al. [2020], Almanza et al. [2021], online matching
Antoniadis et al. [2020]. Our research seeks to take a further step, by
investigating the case when the DM receives pregressively updated predictions
across the horizon, instead of being given a fixed prediction at the
beginning.

Lastly, our prediction model is also related to a line of works online
optimization with predictions, which concerns improving the performance
guarantee with the help of predictions. These predictions are provided to the
DM at the beginning of each round sequentially. A variety of full feedback
settings are studied in Rakhlin and Sridharan [2013a, b], Steinhardt and Liang
[2014], Jadbabaie et al. [2015], and the contextual bandit setting is studied
in Wei et al. [2020]. We remark that the abovementioned works do not involve
resource constraints, and they are fundamental different from ours, as shown
in the forthcoming Lemma 2.

Notation. For a positive integer $d$, we denote $[d]=\\{1,\ldots,d\\}$. We
adopt the $O(\cdot),o(\cdot),\Omega(\cdot)$ notation in Cormen et al. [2009].

##  2 Problem Setup

We consider the Non-Stationary Bandit with Knapsack problem with Online Advice
(NS-BwK-OA). The nature specifies an NS-BwK-OA problem instance, represented
by the tuple $({\cal A},B,T,\\{q_{t}\\}^{T}_{t=1},\\{P_{a}\\}_{a\in{\cal
A}})$. We denote ${\cal A}$ as the set of $K$ arms. There are $d$ types of
resources, and the decision maker (DM) is endowed with $B_{i}\geq 0$ units of
resource $i$ for each $i\in[d]$. The planning horizon consists of $T$ discrete
time steps. Following the convention in [Badanidiyuru et al., 2013], we assume
for all $i\in[d]$ that $B_{i}=B=bT$, where $b$ is the normalized budget. At
time $t$, there are $q_{t}$ units of demands arriving at the DM’s platform.
For example, $q_{t}$ can be the number of customers visiting an online shop at
time step $t$, and a time step can be a fifteen minute interval. We assume
$q_{t}\in[\underline{q},\overline{q}]$, where $0<\underline{q}<\overline{q}$.
The sequence $\\{q_{t}\\}^{T}_{t=1}$ is an arbitrary element of
$[\underline{q},\overline{q}]^{T}$ fixed by the nature before the online
dynamics. The arbitrariness represents the exogenous nature of the demands.

When the DM pulls arm $a\in{\cal A}$, the nature samples a vector
$(R(a),C(a,1),\ldots,C(a,d))\sim P_{a}$ of random outcomes. The quantity
$R(a)$ is the reward earned per demand unit, and $C(a,i)$ is the amount of
type $i$ resource consumed per demand unit. The random variables
$R(a),C(a,1),\ldots,C(a,d)$ are supported in $[0,1]$, and they can be
arbitrarily correlated. We denote
$r(a)=\mathbb{E}[R(a)],c(a,i)=\mathbb{E}[C(a,i)]$, and
$\boldsymbol{r}=(r(a))_{a\in\mathcal{A}}$,
$\boldsymbol{c}=(c(a,i))_{a\in\mathcal{A},i\in[d]}$. To ensure feasiblity, we
assume there is a null arm $a_{0}\in{\cal A}$ such that
$R(a_{0})=C(a_{0},i)=0$ with certainty for all $i\in[d]$.

At each time $t$, the DM is provided with a _prediction oracle_ ${\cal
F}_{t}$. The oracle is a function ${\cal
F}_{t}:[\underline{q},\overline{q}]^{t-1}\rightarrow[\underline{q}T,\overline{q}T]$
that provides an estimation $\hat{Q}_{t}={\cal F}_{t}(q_{1},\ldots,q_{t-1})$
on $Q=\sum_{t=1}^{T}q_{t}$ with the past observations
$\\{q_{s}\\}^{t-1}_{s=1}$. The DM knows ${\cal A},B,T$, and has the access to
${\cal F}_{t}$ in a sequential manner. In contrast, the DM does not know
$\\{P_{a}\\}_{a\in{\cal A}},\\{q_{t}\\}^{T}_{t=1}$, while the upper bound
$\overline{q}$ is known to the DM.

Dynamics. At each time $t$, three events happen. Firstly, the DM receives a
prediction $\hat{Q}_{t}=\mathcal{F}_{t}(q_{1},\ldots,q_{t-1})$ on $Q$.
Secondly, based on $\hat{Q}_{t}$ and the history observation, the DM selects
arm $A_{t}\in\mathcal{A}$. Thirdly, the DM observes the feedback consisting of
(i) demand volume $q_{t}$, (ii) reward earned $q_{t}R_{t}$, (iii) resources
consumed $\\{q_{t}C_{t,i}\\}_{i\in[d]}$. Recall that
$(R_{t},C_{t,1},\ldots,C_{t,d})\sim P_{A_{t}}$. Then, the DM proceeds to time
$t+1$. If some resource is depleted, _i.e._ $\exists j\in[d]$ such that
$\sum_{s=1}^{t}q_{s}C_{s,j}>B_{j}$, then the null arm $a_{0}$ is to be pulled
in the remaining horizon $t+1,\ldots,T$. We denote the stopping time here as
$\tau$. The DM aims to maximize the total reward
$\mathbb{E}[\sum_{t=1}^{\tau-1}q_{t}R_{t}]$, subject to the resource
constraints and model uncertainty.

On $q_{t}$. Our feedback model on $q_{t}$ is more informative than Lykouris et
al. [2020], where none of $q_{1},\ldots,q_{T}$ is observed during the horizon.
In contrast, ours is less informative than Tracà et al. [2021], where
$q_{1},\ldots,q_{T}$ are all observed at time 1. Our assumption of observing
$q_{t}$ at the end of time $t$ is mild in online retail settings. For example,
the number of visitors to a website within a time interval can be extracted
from the electronic records when the interval ends.

While the nature sets $\\{q_{t}\\}^{T}_{t=1}$ to be fixed but arbitrary, the
sequence is set without knowing the DM’s online algorithm and prediciton
oracle ${\cal F}=\\{{\cal F}_{t}\\}^{T}_{t=1}$. Our model is milder than the
_oblivious adversary_ model, where the nature sets a latent quantity (in this
case $\\{q_{t}\\}^{T}_{t=1}$) _with_ the knowledge of the DM’s algorithm
before the online dynamics. Our milder model allows the possibility of
$\hat{Q}_{t}=\mathcal{F}_{t}(q_{1},\ldots,q_{t-1})$ being a sufficiently
accurate (to be quantified in our main results) estimate to $Q$ for each $t$,
for example when $\\{q_{t}\\}^{T}_{t=1}$ is govenred by a latent time series
model. In contrary, an oblivious adversary can set $Q$ to be far away from the
predictions $\hat{Q}_{1},\ldots,\hat{Q}_{T}$ in response to the information on
${\cal F}$.

On ${\cal F}$. Our prediction oracle is a general Black-Box model. We do not
impose any structural or parameteric assumption on ${\cal F}$ or
$\\{q_{t}\\}^{T}_{t=1}$. It is instructive to understand ${\cal F}$ as a side
information provided to the DM by an external source. In the dynamic pricing
example, $\hat{Q}_{t}$ could be an estimate on the customer base population
provided by an external marketing research firm. A prime candidate of ${\cal
F}$ is the cornucopia of time series prediction models proposed in decades of
research works on time series [Shumway and Stoffer, 2017, Hyndman and
Athanasopoulos, 2021, Lim and Zohren, 2021]. These prediction models allow
_one step prediction_ , where for any $t$, the predictor ${\cal P}$ inputs
$\\{q_{s}\\}^{t-1}_{s=1}$ and outputs an estimate $\hat{q}_{t}$ on $q_{t}$.
The prediction $\hat{Q}_{t}$ can be constructed by (1) iteratively applying
${\cal P}$ on $\\{q_{s}\\}^{t-1}_{s=1}\cup\\{\hat{q}\\}^{t+\rho-1}_{t}$ to
output $\hat{q}_{t+\rho}$, for $\rho\in\\{0,\ldots,T-t\\}$, (2) summing over
$q_{1},\ldots,q_{t-1},\hat{q}_{t},\ldots,\hat{q}_{T}$ and return
$\hat{Q}_{t}$. We provide an example in the forthcoming Section 5.

Regret. To measure the performance of an algorithm, we define the regret of an
algorithm as

$\displaystyle\text{Regret}_{T}=\text{OPT}-\mathbb{E}\left[\sum_{t=1}^{\tau-1}q_{t}R_{t}\right],$
(1)

where OPT denotes the expected cumulative reward of an offline optimal dynamic
policy given all latent information and all adversarial terms. For analytical
tractabililty in our regret upper bound, we consider an alternative benchmark

$\displaystyle\text{OPT}_{\text{LP}}=\max_{\boldsymbol{u}\in\Delta_{|\mathcal{A}|}}$
$\displaystyle\left(\sum_{t=1}^{T}q_{t}\right)\boldsymbol{r}^{\top}\boldsymbol{u}\qquad$
(2) s.t.
$\displaystyle\left(\sum_{t=1}^{T}q_{t}\right)\boldsymbol{c}^{\top}\boldsymbol{u}\leq
B\boldsymbol{1}_{d},$

where
$\Delta_{|\mathcal{A}|}=\\{\boldsymbol{w}\in[0,1]^{d}:\sum_{a\in\mathcal{A}}w_{a}=1\\}$.
The benchmark (2) is justified by the following Lemma:

######  Lemma 1.

$\text{OPT}_{\text{LP}}\geq\text{OPT}.$

The proof of Lemma 1 is in Appendix.

##  3 Regret Lower Bounds

In this section, we provide impossibility results on the NS-BwK-OA in the form
of regret lower bounds. Firstly, we show that a linear-in-$T$ regret is
inevitable in the absence of the prediction oracle ${\cal F}$.

######  Lemma 2.

Consider a fixed but arbitrary online algorithm that knows
$\\{P_{a}\\}_{a\in{\cal A}}$, $\\{(q_{s},q_{s}R_{s},q_{s}C_{s,1},\ldots
q_{s}C_{s,d})\\}^{t-1}_{s=1}$ and $q_{t}$, but does not have any access to a
prediction oracle when the action $A_{t}$ is to be chosen at each time $t$.
There exists an instance such that the online algorithm suffers
$\text{Regret}_{T}=\Omega(T).$

Lemma 2 is proved in Appednix B.1. Lemma 2 shows that even when all model
information on time steps $1,\ldots,t$ are revealed when $A_{t}$ is to be
chosen, the DM still suffers $\text{Regret}_{T}=\Omega(T).$ Thus, NS-BwK-OA is
fundamentally different from non-stationary bandits without resource
constraints such as Besbes et al. [2015], and online optimization with
predictions problems such as Rakhlin and Sridharan [2013a]. In these settings,
we can achieve $\text{Regret}_{T}=0$ if all model information on time steps
$1,\ldots,t$ are available at the time point of choosing $A_{t}$ or the action
at time $t$. Indeed, given all model information at time $t$, the DM achieve
the optimum by choosing an arm or an action that maximizes the reward function
of time $t$ for every $t\in[T]$.

In view of Lemma 2, we seek to understand if the DM can avoid
$\text{Regret}_{T}=\Omega(T)$ when s/he is endowed with an accurate prediction
on $Q$. Certainly, if the DM only recieves an uninformative prediction, such
as a worst case prediction $\overline{q}T$, at every time step,
$\text{Regret}_{T}=\Omega(T)$ still cannot be avoided. In contrast, if the DM
received an _accurate_ prediction at a time step, we demonstrate our first
step for deriving a better regret bound, in the form of a more benign regret
lower bound compared to Lemma 2. We formalize the notion of being _accurate_
by the two notions below.

For $T_{0}\in[T-1]$ and $\epsilon_{T_{0}+1}\geq 0$, an instance is said to be
_$(T_{0}+1,\epsilon_{T_{0}+1})$ -well estimated by oracle ${\cal F}$_, if the
prediction $\hat{Q}_{T_{0}+1}={\cal F}_{T_{0}+1}(q_{1},\ldots,Q_{T_{0}})$
returned by the oracle at time $T_{0}+1$ satisfies
$|Q-\hat{Q}_{T_{0}+1}|\leq\epsilon_{T_{0}+1}$. For $T_{0}\in[T-1]$ and a
prediction oracle ${\cal F}_{T_{0}+1}$, we say that $\epsilon_{T_{0}+1}$ is
_$(T_{0}+1,{\cal F}_{T_{0}+1})$ -sound_ if there exists
$\\{q_{t}\\}^{T_{0}}_{t=1}\in[\underline{q},\overline{q}]^{T_{0}}$ such that
$\epsilon_{T_{0}+1}\leq\min\\{\hat{Q}_{T_{0}+1}-\sum^{T_{0}}_{s=1}q_{s}-\underline{q}(T-T_{0}),\overline{q}(T-T_{0})-(\hat{Q}_{T_{0}+1}-\sum^{T_{0}}_{t=1}q_{t}),\hat{Q}_{T_{0}+1}/2\\}$,
where $\hat{Q}_{T_{0}+1}={\cal F}_{T_{0}+1}(q_{1},\ldots,q_{T_{0}})$. The
soundness notion imposes an upper bound on $\epsilon_{T_{0}+1}$, which ensures
a non-trivial bounding condition in
$|Q-\hat{Q}_{T_{0}+1}|\leq\epsilon_{T_{0}+1}$ for the “well estimated” notion.

######  Theorem 1.

Consider the NS-BwK-OA setting, and consider a fixed but arbitrary online
algorithm and prediciton oracle ${\cal F}=\\{{\cal F}_{t}\\}^{T}_{t=1}$. For
any $T_{0}\in[T-1]$ and any $\epsilon_{T_{0}+1}>0$ that is $(T_{0}+1,{\cal
F}_{T_{0}+1})$-sound, there exists a $(T_{0}+1,\epsilon_{T_{0}+1})$-well
estimated instance $I$ such that

$\text{Regret}_{T}=\Omega\left(\max\left\\{\frac{1}{Q}\sum^{T_{0}}_{t=1}q_{t}\epsilon_{T_{0}+1}~{},~{}\Lambda\right\\}\right),$
(3)

where $\\{q_{t}\\}^{T}_{t=1}$ is the underlying demand seqeunce of $I$, and
$Q=\sum^{T}_{t=1}q_{t},$ and

$\Lambda=\min\left\\{\text{OPT},\text{OPT}\sqrt{\frac{\overline{q}K}{B}}+\sqrt{\overline{q}K\text{OPT}}\right\\}.$

Theorem 1 is proved in Appendix B.2. In (3), the regret lower bound $\Lambda$
is due to the uncertainty on $\\{P_{a}\\}_{a\in\mathcal{A}}$, and $\Lambda$ is
derived directly from Badanidiyuru et al. [2013]. The regret lower bound
$\frac{1}{Q}\sum^{T_{0}}_{t=1}q_{t}\epsilon_{T_{0}+1}$ is due to the oracle’s
estimation error on $\hat{Q}_{T_{0}+1}$. Theorem 1 demonstrates a more benign
regret lower bound than $\Omega(T)$, under the condition that the prediction
on $Q$ is sufficiently accurate (as formalized as
$(T_{0}+1,\epsilon_{T_{0}+1})$-well estimated).

More specifically, let us consider the following _accurate prediction
condition_ at time $T_{0}$:

$\frac{\epsilon_{T_{0}+1}}{Q}=O(T^{-\alpha}_{0})\quad\text{for some
$\alpha>0$}.$ (4)

The condition implies that, for the prediction $\hat{Q}_{T_{0}+1}$ made using
$T_{0}$ data points $q_{1},\ldots,q_{T_{0}}$, it holds that
$|1-(\hat{Q}_{T_{0}+1}/Q)|=O(T^{-\alpha}_{0})$, which in turn implies that
$\hat{Q}_{t}$ converges to $Q$ as $t$ grows. For example, when
$\\{q_{t}\\}^{T}_{t=1}$ are i.i.d. generated, the accurate prediction
condition holds with $\alpha=1/2$.

######  Corollary 1.

Consider the setting of Theorem 1. Suppose the accurate prediction condition
(4) holds at $T_{0}$, then the refined regret lower bound
$\text{Regret}_{T}=\Omega(\max\\{\underline{q}T^{1-\alpha}_{0},\Lambda\\})$
holds.

Altogether, under the accurate prediction condition, the corollary presents a
strictly smaller regret lower bound than that in Lemma 2, which has no
prediction oracle available. In complement, we design and analyze an online
algorithm in the next section that reaps the benefits of predictions, and in
particular nearly matches the regret lower bound in Corollary 1 under the
accurate prediction condition. Thus, a $o(T)$-regret is possible in a non-
stationary environment given accurate predictions as prescribed above, even
though the amount of non-stationarity in the underlying model is not bounded
in general.

##  4 Algorithm and Analysis

We propose the Online-Advice-UCB (OA-UCB) algorithm, displayed in Algorithm 1,
for solving NS-BwK-OA. The algorithm design involve constructing confidence
bounds to address the model uncertainty on $\boldsymbol{r},\boldsymbol{c}$, as
discussed in Section 4.1. In Section 4.2, we elaborate on OA-UCB, which uses
Online Convex Optimization (OCO) tools to balance the trade-off among rewards
and resources. Crucially, at each time $t$, we incorporate the prediction
$\hat{Q}_{t}$ to scale the opportunity costs of the resources. In addition,
both $q_{t}$ and $\hat{Q}_{t}$ are judiciously integrated into the OCO tools
to factor the demand volumes into the consideration of the abovemention trade-
off. In Section 4.3, we provide a regret upper bound to OA-UCB, and
demonstrate its near-optimality when the accurate prediction condition (4)
holds and when capacity is large. In Section 4.4 we provide a sketch proof of
the regret upper bound, where the complete proof is in Appendix C.

###  4.1 Confidence Bounds

We consider the following confidence radius function:

$\text{rad}(v,N,\delta)=\sqrt{\frac{2v\log\left(\frac{1}{\delta}\right)}{N}}+\frac{4\log\left(\frac{1}{\delta}\right)}{N}.$
(5)

The function (5) satisfies the following property:

######  Lemma 3 (Babaioff et al. [2015], Agrawal and Devanur [2014]).

Let random variables $\\{V_{i}\\}^{N}_{i=1}$ be independently distributed with
support in $[0,1]$. Denote $\hat{V}=\frac{1}{N}\sum_{i=1}^{N}V_{i}$, then with
probability $\geq 1-3\delta$, we have

$\left|\hat{V}-\mathbb{E}[\hat{V}]\right|\leq\text{rad}(\hat{V},N,\delta)\leq
3\text{rad}(\mathbb{E}[\hat{V}],N,\delta).$

We prove Lemma 3 in Appendix D.1 by following the line of argument in Babaioff
et al. [2015] for the purpose of extracting the values of the coefficients in
(5), which are implicit in Babaioff et al. [2015], Agrawal and Devanur [2014].
Based on the observation $\\{R_{s},\\{C_{s,i}\\}_{i\in[d]}\\}_{s\in[t-1]}$, we
compute the sample means

$\hat{R}_{t}(a)=\frac{1}{N_{t-1}^{+}(a)}\sum_{s=1}^{t-1}R_{s}\textbf{1}_{\\{A_{s}=a\\}},\quad\forall
a\in\mathcal{A},$
$\hat{C}_{t}(a,i)=\frac{1}{N_{t-1}^{+}(a)}\sum_{s=1}^{t-1}C_{s,i}\textbf{1}_{\\{A_{s}=a\\}},~{}\forall
a\in\mathcal{A},\ i\in[d],$

where $N_{t-1}^{+}(a)=\max\\{\sum_{s=1}^{t-1}\textbf{1}_{\\{A_{s}=a\\}},1\\}$.
In line with the principle of Optimism in Face of Uncertatinty, we construct
upper confidence bounds (UCBs) for the rewards and lower confidence bounds
(LCBs) for resource consumption ammounts. For each $a\in\mathcal{A}$, we set
$\text{UCB}_{r,t}(a)=$

$\min\left\\{\hat{R}_{t}(a)+\text{rad}(\hat{R}_{t}(a),N_{t-1}^{+}(a),\delta),1\right\\}.$
(6)

For each $a\in\mathcal{A},i\in[d]$, we set $\text{LCB}_{c,t}(a,i)=$

$\max\left\\{\hat{C}_{t}(a,i)-\text{rad}(\hat{C}_{t}(a,i),N_{t-1}^{+}(a),\delta),0\right\\}.$
(7)

The design of the UCBs and LCBs are justified by Lemma 3 and the model
assumption that $r(a),c(a,i)\in[0,1]$ for all $a\in{\cal A},i\in[d]$:

######  Lemma 4.

With probability $\geq 1-3KTd\delta$, we have

$\text{UCB}_{r,t}(a)\geq r(a),\ \ \text{LCB}_{c,t}(a,i)\leq c(a,i)$

for all $a\in\mathcal{A},i\in[d]$.

Lemma 4 is proved in Appendix D.2.

###  4.2 Details on OA-UCB

OA-UCB is presented in Algorithm 1. At each time step $t$, the algorithm first
computes a composite reward term

$\text{UCB}_{r,t}(a)-\frac{\hat{Q}_{t}}{B}\cdot\boldsymbol{\mu}_{t}^{\top}\textbf{LCB}_{c,t}(a),$
(8)

where $\text{UCB}_{r,t}(a),\hat{Q}_{t}$ and $\textbf{LCB}_{c,t}(a)$ are the
surrogates for the latent $r(a),Q,\textbf{c}(a)$ respectively. The term
$\frac{\hat{Q}_{t}}{B}\cdot\boldsymbol{\mu}_{t}^{\top}\textbf{LCB}_{c,t}(a)$
can be interpreted as the opportunity cost of the resources. The scalarization

$\boldsymbol{\mu}_{t}\in S=\\{\boldsymbol{\mu}:\|\boldsymbol{\mu}\|_{1}\leq
1,\boldsymbol{\mu}\geq\boldsymbol{0}_{d}\\}$ (9)

weighs the relative importance of the resources. The factor $\hat{Q}_{t}/B$
reflects that the opportunity cost increases with $\hat{Q}_{t}$, since with a
higher total demand volume, the DM is more likely to exhaust some of the
resources during the horizon, and similar reasoning holds for $B$. Altogether,
(8) balances the trade-off between the reward of an arm and the opportunity
cost of that arm’s resource consumption. We select an arm that maximizes (8)
at time $t$.

After receiving the feedback, We update the scalarization
$\boldsymbol{\mu}_{t}$ via the Online Gradient Descent (OGD) Agrawal and
Devanur [2014], Hazan et al. [2016] on the sequence of functions
$\\{f_{t}\\}^{T}_{t=1}$, where

$f_{t}(\boldsymbol{x})=\frac{q_{t}\hat{Q}_{t}}{B}\left(\frac{B}{\hat{Q}_{t}}\boldsymbol{1}_{d}-\textbf{LCB}_{c,t}(A_{t})\right)^{\top}\boldsymbol{x}.$
(10)

While $f_{t}$ incorporates the prediction $\hat{Q}_{t}$ for the purpose of
accounting for the estimated opportunity cost similar to (8), $f_{t}$ also
incoporates the actual demand $q_{t}$ for accounting the actual amounts of
resources consumed. In the OGD update in (11), for a resource type $i$, the
coefficient $\mu_{t+1}(i)$ increases with $q_{t}\text{LCB}_{c,t}(A_{t},i)$,
meaning that a higher amount of resource $i$ consumption at time $t$ leads to
a higher weightage of resource $i$’s opportunity cost at time $t+1$.

Algorithm 1 Online-advice-UCB (OA-UCB)

1:Initialize $\boldsymbol{\mu}_{1}=\frac{1}{d}\boldsymbol{1}_{d}$,
$M=\left(\overline{q}+\frac{\overline{q}^{2}}{b}\right)\sqrt{d}$,
$\eta_{t}=\frac{\sqrt{2}}{M\sqrt{t}}$.

2:for $t=1,2,...,T$ do

3: Receive $\hat{Q}_{t}={\cal F}_{t}(q_{1},\ldots,q_{t-1})$.

4: Compute $\text{UCB}_{r,t}(a)$, $\textbf{LCB}_{c,t}(a)$ for all
$a\in\mathcal{A}$ by (6), (7), where
$\textbf{LCB}_{c,t}(a)=(\text{LCB}_{c,t}(a,i))_{i\in[d]}$.

5: Select
$A_{t}\in\underset{a\in\mathcal{A}}{\text{argmax}}\left\\{\text{UCB}_{t}^{(r)}(a)-\frac{\hat{Q}_{t}}{B}\cdot\boldsymbol{\mu}_{t}^{\top}\textbf{LCB}_{c,t}(a)\right\\}.$

6: if $\exists j\in[d]$ such that $\sum_{s=1}^{t}q_{s}C_{t,j}>B$ then

7: Break, and pull the null arm $a_{0}$ all the way.

8: Observe $q_{t}$, receive reward $q_{t}R_{t}$, and consume $q_{t}C_{t,i}$
for each resource $i\in[d]$.

9: Update $\boldsymbol{\mu}_{t+1}$ with OGD. $\boldsymbol{\mu}_{t+1}$ is set
to be
$\Pi_{S}\left(\boldsymbol{\mu}_{t}-\eta_{t}\frac{q_{t}\hat{Q}_{t}}{B}\left(\frac{B}{\hat{Q}_{t}}\boldsymbol{1}_{d}-\textbf{LCB}_{c,t}(A_{t})\right)\right),$
(11) where $S$ is defined in (9).

###  4.3 Performance Guarantees of OA-UCB

The following theorem provides a high-probability regret upper bound for
Algorithm 1:

######  Theorem 2.

Consider the OA-UCB algorithm, that is provided with predictions that satisfy
$|\hat{Q}_{t}-Q|\leq\epsilon_{t}$ for all $t\in[T]$. With probability $\geq
1-3KTd\delta$,

$\displaystyle\text{OPT}_{\text{LP}}-\sum_{t=1}^{\tau-1}q_{t}R_{t}$
$\displaystyle\leq
O\left(\left(\text{OPT}_{\text{LP}}\sqrt{\frac{\overline{q}K}{B}}+\sqrt{\overline{q}K\text{OPT}_{\text{LP}}}\right)\log\left(\frac{1}{\delta}\right)\right.$
(12)
$\displaystyle+\left.\left(\frac{1}{Q}+\frac{1}{B}\right)\sum_{t=1}^{\tau-1}q_{t}\epsilon_{t}+M\sqrt{T}\right).$
(13)

Theorem 2 is proved in the Appendix, and we provide a sketch proof in Section
4.4. The Theorem holds in the special case when we set
$\epsilon_{t}=|\hat{Q}_{t}-Q|$, and $\epsilon_{t}$ represents an upper bound
on the estimation error of $\hat{Q}_{t}$ on $Q$, for example by certain
theoretical guarantees. The term (12) represents the regret due to the
learning on $r(a),c(a,i)$. The first term in (13) represents the regret due to
the prediction error of the prediction oracle, and the second term in (13)
represents the regret due to the application of OGD.

Comparison between regret lower and upper bounds. The regret term (12) matches
the lower bound term $\Lambda$ in Theorem 1 within a logarithmic factor. Next,
we compare the regret upper bound term
$(\frac{1}{Q}+\frac{1}{B})\sum_{t=1}^{\tau-1}q_{t}\epsilon_{t}$ and the lower
bound term $\frac{1}{Q}\sum^{T_{0}}_{t=1}q_{t}\epsilon_{T_{0}+1}$ in Theorem
1. We first assure that the lower and upper bound results are consistent, in
the sense that our regret upper bound is indeed in
$\Omega(\frac{1}{Q}\sum^{T_{0}}_{t=1}q_{t}\epsilon_{T_{0}+1})$ on the lower
bounding instances constructed for the proof of Theorem 1. In those instances,
$T_{0}$ is set in a way that the resource is not fully exhausted at time
$T_{0}$ under any policy, thus the stopping time $\tau$ of OA-UCB satisfies
$\tau>T_{0}$ with certainty. More details are provided in Appendix B.3.

Next, we highlight that the regret upper and lower bounds are nearly matching
(modulo multiplicative factors of $\log(1/\delta)$ and
$\overline{q}/\underline{q}$, as well as the additive $O(M\sqrt{T})$ term),
under the high capacity condition $B=\Theta(Q)$ and the accurate prediction
condition (4) for each $t\in[T]$. The first condition is similar to the large
capacity assumption in the literature Besbes and Zeevi [2009, 2012], Liu et
al. [2022], while the second condition is a natural conditon that signfies a
non-trivial estimation by the prediciton oracle, as discussed in Section 3. On
one hand, by setting $T_{0}=\Theta(T)$ for the highest possible lower bound in
Corollary 1, we yield the regret lower bound
$\Omega(\max\\{\underline{q}T^{1-\alpha},\Lambda\\})$. On the other hand, the
second term in (13) is upper bounded as

$\displaystyle\left(\frac{1}{Q}+\frac{1}{B}\right)\sum_{t=1}^{\tau-1}q_{t}\epsilon_{t}=O\left(\sum_{t=1}^{\tau-1}q_{t}\frac{\epsilon_{t}}{Q}\right)=O\left(\sum_{t=1}^{\tau-1}q_{t}t^{-\alpha}\right)=O(\overline{q}T^{1-\alpha}).$

Altogether, our claim on the nearly matching bounds is established.

###  4.4 Proof Sketch of Theorem 2

We provide an overview on the proof of Theorem 2, which is fully proved in
Appendix C. We first provide bounds on the regret induced by the estimation
errors of the UCBs and LCBs. Now, with probability $\geq 1-3KTd\delta$, the
inequalities

$\displaystyle\left|\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{r,t}(A_{t})-\sum_{t=1}^{\tau-1}q_{t}R_{t}\right|$
$\displaystyle\leq
O\left(\log\left(\frac{1}{\delta}\right)\left(\sqrt{\overline{q}K\sum_{t=1}^{\tau-1}q_{t}R_{t}}+\overline{q}K\log\left(\frac{T}{K}\right)\right)\right),$
(14)
$\displaystyle\left|\sum_{t=1}^{\tau-1}q_{t}\text{LCB}_{c,t}(A_{t},i)-\sum_{t=1}^{\tau-1}q_{t}C_{t,i}\right|$
$\displaystyle\leq
O\left(\log\left(\frac{1}{\delta}\right)\left(\sqrt{\overline{q}KB}+\overline{q}K\log\left(\frac{T}{K}\right)\right)\right)~{}\forall
i\in[d]$ (15)

hold. Inequalities (14, 15) are proved in Appendix D.3. Next, by the
optimality of $A_{t}$ in Line 5 in Algorithm 1,

$\displaystyle\text{UCB}_{r,t}(A_{t})-\frac{\hat{Q}_{t}}{B}\cdot\boldsymbol{\mu}_{t}^{\top}\textbf{LCB}_{c,t}(A_{t})$
$\displaystyle\geq$
$\displaystyle\textbf{UCB}_{r,t}^{\top}\boldsymbol{u}^{*}-\frac{\hat{Q}_{t}}{B}\cdot\boldsymbol{\mu}_{t}^{\top}\textbf{LCB}_{c,t}\boldsymbol{u}^{*},$

which is equivalent to

$\displaystyle\textbf{UCB}_{r,t}^{\top}\boldsymbol{u}^{*}-\text{UCB}_{r,t}(A_{t})+\frac{\hat{Q}_{t}}{B}\boldsymbol{\mu}_{t}^{\top}\left(\frac{B}{\hat{Q}_{t}}\boldsymbol{1}_{d}-\textbf{LCB}_{c,t}^{\top}\boldsymbol{u}^{*}\right)$
$\displaystyle\leq\frac{\hat{Q}_{t}}{B}\cdot\boldsymbol{\mu}_{t}^{\top}\left(\frac{B}{\hat{Q}_{t}}\boldsymbol{1}_{d}-\textbf{LCB}_{c,t}(A_{t})\right).$

Multiply $q_{t}$ on both side, and sum over $t$ from 1 to $\tau-1$. By
applying the OGD performance guarantee in Hazan et al. [2016] with
$\\{f_{t}\\}^{T}_{t=1},S$ defined in (10, 9) respectively, we argue that, for
all $\boldsymbol{\mu}\in S$,

$\displaystyle\sum_{t=1}^{\tau-1}q_{t}\textbf{UCB}_{r,t}^{\top}\boldsymbol{u}^{*}-\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{r,t}(A_{t})$
$\displaystyle+$
$\displaystyle\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\cdot\boldsymbol{\mu}_{t}^{\top}\left(\frac{B}{\hat{Q}_{t}}\boldsymbol{1}_{d}-\textbf{LCB}_{c,t}^{\top}\boldsymbol{u}^{*}\right)$
$\displaystyle\leq$
$\displaystyle\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\cdot\left(\frac{B}{\hat{Q}_{t}}\boldsymbol{1}_{d}-\textbf{LCB}_{c,t}(A_{t})\right)^{\top}\boldsymbol{\mu}+O\left(M\sqrt{T}\right).$

If $\tau\leq T$, then there exists $j_{0}\in[d]$ such that
$\sum_{t=1}^{\tau}q_{t}C_{t,j_{0}}>B$. Take
$\boldsymbol{\mu}=\frac{\text{OPT}_{\text{LP}}}{Q}\boldsymbol{e}_{j_{0}}\in S$
(This is because
$\text{OPT}_{\text{LP}}=Q\boldsymbol{r}^{\top}\boldsymbol{u}^{*}\leq Q$).
Analysis yields

$\displaystyle\text{OPT}_{\text{LP}}-\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{r,t}(A_{t})\leq
O\left(\log\left(\frac{1}{\delta}\right)\text{OPT}_{\text{LP}}\sqrt{\frac{\overline{q}K}{B}}\right.$
$\displaystyle\left.+\left(\frac{1}{Q}+\frac{1}{B}\right)\sum_{t=1}^{\tau-1}q_{t}\epsilon_{t}+M\sqrt{T}\right).$
(16)

If $\tau>T$, it is the case that $\tau-1=T$, and no resource is exhausted at
the end of the horizon. Take $\boldsymbol{\mu}=\boldsymbol{0}$. Similar
analaysis to the previous case shows that
$\text{OPT}_{\text{LP}}-\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{r,t}(A_{t})\leq$

$O\left(\frac{1}{Q}\sum_{t=1}^{\tau}q_{t}\epsilon_{t}+M\sqrt{T}\right).$ (17)

Combine (14), (16), (17) and the fact that
$\text{OPT}_{\text{LP}}\geq\sum_{t=1}^{\tau-1}q_{t}R_{t}$, the theorem holds.

##  5 Numerical Experiments

We present numerical results, and compare our algorithm with several existing
algorithms on BwK.

Demand sequence $\\{q_{t}\\}^{T}_{t=1}$: We apply an AR(1) model to generate
$\\{q_{t}\\}$:

$q_{t}=\alpha+\beta q_{t-1}+\varepsilon_{t},$

where $\varepsilon_{1},\ldots\varepsilon_{T}\sim N(0,\sigma^{2})$ are
independent.

Estimations $\\{\hat{Q}_{t}\\}^{T}_{t=1}$: At round $t$, given history
observation $\\{q_{s}\\}_{s=1}^{t-1}$, there are many time series prediction
tools in Python, MatLab or R that perform predictions to yield
$\\{\hat{q}_{s}\\}_{s=t}^{T}$, where $\hat{q}_{s}$ is a estimate on $q_{s}$.
We define the estimation $\hat{Q}_{t}$ as
$\sum_{s=1}^{t-1}q_{s}+\sum_{s=t}^{T}\hat{q}_{s}$. To achieve time-efficiency,
we consider a ”power-of-two” policy for updating the $\hat{Q}_{t}$ on $Q$, as
shown in Algorithm 2. That is, we only recompute $\hat{Q}_{t}$ when $t=2^{k}$
for some $k\in\mathbb{N}^{+}$. The estimation error of Algorithm 2 in terms of
additive gap is plotted in Figure 1.

Algorithm 2 Estimation Generation Policy

Input: Time step $t$, history observation $\\{q_{s}\\}_{s=1}^{t-1}$, previous
estimation $\hat{Q}_{t-1}$.

1:if $t=2^{k}$ for some $k\in\mathbb{N}^{+}$ then

2: Compute predictions $\\{\hat{q}_{s}\\}_{s=t}^{T}$ , and update
$\hat{Q}_{t}=\sum_{s=1}^{t-1}q_{s}+\sum_{s=t}^{T}\hat{q}_{s}$.

3:else

4: Set $\hat{Q}_{t}=\hat{Q}_{t-1}$.

5:return $\hat{Q}_{t}$.

Figure 1: Estimation error

Benchmarks: We compare OA-UCB with three existing online algorithms for BwK.
The first algorithm is the PrimalDualBwK algorithm in Badanidiyuru et al.
[2013], which we call “PDB” in the following. The second algorithm is the UCB
algorithm presented in Agrawal and Devanur [2014], which we call “AD-UCB”. The
third algorithm is the Sliding-Window UCB in Liu et al. [2022], which we call
“SW-UCB”. In implementing SW-UCB, we set the sliding window size according to
the suggestion in Liu et al. [2022], and we input the required non-
stationarity measures by computing them from the ground truth
$\\{q_{t}\\}^{15000}_{t=1}$.

In the experiment, we simulate our algorithm and the benchmarks on a family of
instances, with $K=10$, $d=3$, $b=3$, $\alpha=2$, $\beta=0.5$, $\sigma=0.5$,
and $T$ varies from 5000 to 15000. Each arms’s per-unit-demand outcome
$(R(a),\\{C_{i}(a)\\}^{d}_{i=1})$ follows the standard Gaussian distribution
truncated in $[0,1]^{d+1}$, which has mean denoted as
$(r(a),\boldsymbol{c}(a))$. We perform two groups of the experiment. In each
group, we first generate a sample of
$(\boldsymbol{r},\boldsymbol{c},\\{q_{t}\\}^{15000}_{t=1})$. Then, for each
fixed $T$, we simulate each algorithm ten times with demand volume sequence
$\\{q_{t}\\}_{t=1}^{T}$, and compute the regret based on the sample average.

Figures 2(a) and 2(b) plots the regret of each algorithm on different horizon
lengths, in each of the two groups. The superiority in numerical performance
for OA-UCB does not mean that our algorithm is strictly superior to the
baselines. Indeed, our algorithm OA-UCB receives online advice by Algorithm 2,
while the benchmarks do not. The numerical results instead indicate the
benefit of prediciting the underlying non-stationary demand sequence, and
showcase how a suitably designed algoirhtm such as OA-UCB could reap the
benefit of predictions. In addition, we remark that the sliding window UCB
algorithm proposed by Liu et al. [2022] is designed to handle arbitrarily
changing mean outcome distributions, subject to constraints on the amount of
temporal variations. On the one hand, the sliding window UCB algorithm has
been shown to outperform the stationary BwK benchmarks in piece-wise
stationary models where the mean outcome distributions change abruptly [Liu et
al., 2022]. On the other hand, in our non-stationary scaling setting, the per-
demand-unit mean outcomes $r(a),c(a,1),\ldots,c(a,d)$ are time stationary for
each arm $a$. Hence, historical data are useful for estimating these mean
outcomes, which explain why the stationary benchmark could appear to out-
perform sliding window UCB.

(a) Regret on Experiment Group 1

(b) Regret on Experiment Group 2

Figure 2: Regret

Figure 3 depict the trend of the accumulated rewards as time progresses, with
horizon $T=10000$. The black dotted lines indicate the stopping times of each
algorithm respectively. Compared with our algorithm OA-UCB, PDB and SW-UCB
could appear conservative, meaning that they focus too much on not exhausting
resources. In contrast, AD-UCB seems a little aggressive, meaning that it
prefers to choose the arm with high reward and resource consumption.

Figure 3: Cumulative Reward growing.

##  6 Conclusion

We study a non-stationary bandit with knapsack problem, in the presense of a
prediction oracle on the latent total demand volume $Q$. Our oracle is novel
compared to existing models in online optimization with machine-learned advice
(such as Lykouris and Vassilvitskii [2021]), in that ours returns a (possibly
refined) prediction on $Q$ every time step. There are many interesting future
directions, such as investigating the models Bamas et al. [2020], Lykouris and
Vassilvitskii [2021], Purohit et al. [2018], Mitzenmacher [2019] in the
presense of sequential prediction oracles similar to ours. It is also
interesting to invenstigate other forms of predictions, such as confidence
intervals containing $Q$ in the spirit robust optimization Bertsimas and Sim
[2004], or prediction with distributional information Diakonikolas et al.
[2021]. Customizing prediction oracles for NS-BwK-OA is also an interesting
direction to pursuse Anand et al. [2020].

## References

  * Agrawal and Devanur [2014] Shipra Agrawal and Nikhil R Devanur.  Bandits with concave rewards and convex knapsacks.  In _Proceedings of the fifteenth ACM conference on Economics and computation_ , pages 989–1006, 2014.
  * Agrawal et al. [2016] Shipra Agrawal, Nikhil R Devanur, and Lihong Li.  An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives.  In _Conference on Learning Theory_ , pages 4–18. PMLR, 2016.
  * Almanza et al. [2021] Matteo Almanza, Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi, and Giuseppe Re.  Online facility location with multiple advice.  _Advances in Neural Information Processing Systems_ , 34:4661–4673, 2021.
  * Anand et al. [2020] Keerti Anand, Rong Ge, and Debmalya Panigrahi.  Customizing ML predictions for online algorithms.  In _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 303–313. PMLR, 13–18 Jul 2020.
  * Antoniadis et al. [2020] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev.  Secretary and online matching problems with machine learned advice.  _Advances in Neural Information Processing Systems_ , 33:7933–7944, 2020.
  * Audibert et al. [2009] Jean-Yves Audibert, Rémi Munos, and Csaba Szepesvári.  Exploration–exploitation tradeoff using variance estimates in multi-armed bandits.  _Theoretical Computer Science_ , 410(19):1876–1902, 2009.
  * Babaioff et al. [2015] Moshe Babaioff, Shaddin Dughmi, Robert Kleinberg, and Aleksandrs Slivkins.  Dynamic pricing with limited supply, 2015.
  * Badanidiyuru et al. [2013] Ashwinkumar Badanidiyuru, Robert Kleinberg, and Aleksandrs Slivkins.  Bandits with knapsacks.  In _2013 IEEE 54th Annual Symposium on Foundations of Computer Science_ , pages 207–216. IEEE, 2013.
  * Badanidiyuru et al. [2014] Ashwinkumar Badanidiyuru, John Langford, and Aleksandrs Slivkins.  Resourceful contextual bandits.  In _Conference on Learning Theory_ , pages 1109–1134. PMLR, 2014\.
  * Bamas et al. [2020] Étienne Bamas, Andreas Maggiori, and Ola Svensson.  The primal-dual method for learning augmented algorithms.  _Advances in Neural Information Processing Systems_ , 33:20083–20094, 2020.
  * Bertsimas and Sim [2004] Dimitris Bertsimas and Melvyn Sim.  The price of robustness.  _Operations Research_ , 52(1):35–53, 2004.
  * Besbes and Zeevi [2009] Omar Besbes and Assaf Zeevi.  Dynamic pricing without knowing the demand function: Risk bounds and near-optimal algorithms.  _Operations Research_ , 57(6):1407–1420, 2009\.
  * Besbes and Zeevi [2012] Omar Besbes and Assaf Zeevi.  Blind network revenue management.  _Operations research_ , 60(6):1537–1550, 2012\.
  * Besbes et al. [2014] Omar Besbes, Yonatan Gur, and Assaf Zeevi.  Stochastic multi-armed-bandit problem with non-stationary rewards.  _Advances in neural information processing systems_ , 27, 2014.
  * Besbes et al. [2015] Omar Besbes, Yonatan Gur, and Assaf Zeevi.  Non-stationary stochastic optimization.  _Operations research_ , 63(5):1227–1244, 2015\.
  * Cheung et al. [2019] Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu.  Learning to optimize under non-stationarity.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 1079–1087. PMLR, 2019.
  * Chung and Lu [2006] Fan Chung and Linyuan Lu.  Concentration inequalities and martingale inequalities: a survey.  _Internet mathematics_ , 3(1):79–127, 2006.
  * Cormen et al. [2009] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.  _Introduction to Algorithms, 3rd Edition_.  MIT Press, 2009.  ISBN 978-0-262-03384-8.
  * Diakonikolas et al. [2021] Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian, and Nikos Zarifis.  Learning online algorithms with distributional advice.  In _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , pages 2687–2696. PMLR, 18–24 Jul 2021.
  * Dubhashi and Panconesi [2009] Devdatt P Dubhashi and Alessandro Panconesi.  _Concentration of measure for the analysis of randomized algorithms_.  Cambridge University Press, 2009.
  * Freedman [1975] David A Freedman.  On tail probabilities for martingales.  _the Annals of Probability_ , pages 100–118, 1975.
  * Hazan et al. [2016] Elad Hazan et al.  Introduction to online convex optimization.  _Foundations and Trends® in Optimization_ , 2(3-4):157–325, 2016.
  * Hyndman and Athanasopoulos [2021] R.J. Hyndman and G. Athanasopoulos.  _Forecasting: principles and practice_.  OTexts, 2021.  URL https://otexts.com/fpp3/.
  * Immorlica et al. [2019] Nicole Immorlica, Karthik Abinav Sankararaman, Robert Schapire, and Aleksandrs Slivkins.  Adversarial bandits with knapsacks.  In _2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)_ , pages 202–219. IEEE, 2019.
  * Jadbabaie et al. [2015] Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan.  Online optimization: Competing with dynamic comparators.  In _Artificial Intelligence and Statistics_ , pages 398–406. PMLR, 2015.
  * Lattanzi et al. [2020] Silvio Lattanzi, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii.  Online scheduling via learned weights.  In _Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms_ , pages 1859–1877. SIAM, 2020.
  * Lim and Zohren [2021] Bryan Lim and Stefan Zohren.  Time-series forecasting with deep learning: a survey.  _Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences_ , 379(2194), 2021.
  * Liu et al. [2022] Shang Liu, Jiashuo Jiang, and Xiaocheng Li.  Non-stationary bandits with knapsacks.  _arXiv preprint arXiv:2205.12427_ , 2022.
  * Lykouris and Vassilvitskii [2021] Thodoris Lykouris and Sergei Vassilvitskii.  Competitive caching with machine learned advice.  _Journal of the ACM (JACM)_ , 68(4):1–25, 2021\.
  * Lykouris et al. [2020] Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme.  Bandits with adversarial scaling.  In Hal Daumé III and Aarti Singh, editors, _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 6511–6521, 2020.
  * Mehta et al. [2007] Aranyak Mehta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani.  Adwords and generalized online matching.  _Journal of the ACM (JACM)_ , 54(5):22–es, 2007\.
  * Mitzenmacher [2019] Michael Mitzenmacher.  Scheduling with predictions and the price of misprediction.  _arXiv preprint arXiv:1902.00732_ , 2019.
  * Mitzenmacher and Vassilvitskii [2022] Michael Mitzenmacher and Sergei Vassilvitskii.  Algorithms with predictions.  _Commun. ACM_ , 65(7):33–35, jun 2022.
  * Piotr et al. [2019] Indyk Piotr, Singer Yaron, Vakilian Ali, and Vassilvitskii Sergei.  Summer workshop on learning-based algorithms.  2019\.  URL http://www.mit.edu/ vakilian/ttic-workshop.html.
  * Purohit et al. [2018] Manish Purohit, Zoya Svitkina, and Ravi Kumar.  Improving online algorithms via ml predictions.  In _Advances in Neural Information Processing Systems_ , volume 31, 2018.
  * Rakhlin and Sridharan [2013a] Alexander Rakhlin and Karthik Sridharan.  Online learning with predictable sequences.  In _Conference on Learning Theory_ , pages 993–1019. PMLR, 2013a.
  * Rakhlin and Sridharan [2013b] Sasha Rakhlin and Karthik Sridharan.  Optimization, learning, and games with predictable sequences.  _Advances in Neural Information Processing Systems_ , 26, 2013b.
  * Rangi et al. [2018] Anshuka Rangi, Massimo Franceschetti, and Long Tran-Thanh.  Unifying the stochastic and the adversarial bandits with knapsack.  _arXiv preprint arXiv:1811.12253_ , 2018.
  * Sankararaman and Slivkins [2018] Karthik Abinav Sankararaman and Aleksandrs Slivkins.  Combinatorial semi-bandits with knapsacks.  In _International Conference on Artificial Intelligence and Statistics_ , pages 1760–1770. PMLR, 2018.
  * Shumway and Stoffer [2017] R.H. Shumway and D.S. Stoffer.  _Time Series Analysis and Its Applications: With R Examples_.  Springer texts in statistics. Springer, 2017.  URL https://github.com/nickpoison/tsa4/blob/master/textRcode.md.
  * Steinhardt and Liang [2014] Jacob Steinhardt and Percy Liang.  Adaptivity and optimism: An improved exponentiated gradient algorithm.  In _International Conference on Machine Learning_ , pages 1593–1601. PMLR, 2014.
  * Tracà et al. [2021] Stefano Tracà, Cynthia Rudin, and Weiyu Yan.  Regulating greed over time in multi-armed bandits.  _J. Mach. Learn. Res._ , 22:3–1, 2021.
  * Wei et al. [2020] Chen-Yu Wei, Haipeng Luo, and Alekh Agarwal.  Taking a hint: How to leverage loss predictors in contextual bandits?  In _Conference on Learning Theory_ , pages 3583–3634. PMLR, 2020\.
  * Zhu and Zheng [2020] Feng Zhu and Zeyu Zheng.  When demands evolve larger and noisier: Learning and earning in a growing environment.  In _International Conference on Machine Learning_ , pages 11629–11638. PMLR, 2020.

##  Appendix A Proof for Section 2

###  A.1 Proof for Lemma 1

Let’s first consider

$\text{OPT}^{\prime}_{\text{LP}}=\max_{\boldsymbol{x}_{t}\in\Delta_{|\mathcal{A}|},\
\forall t\in[T]}\
\sum_{t=1}^{T}q_{t}\boldsymbol{r}^{\top}\boldsymbol{x}_{t}\qquad\text{s.t.}\quad\sum_{t=1}^{T}q_{t}\boldsymbol{c}^{\top}\boldsymbol{x}_{t}\leq
B\boldsymbol{1}_{d},$ (18)

where
$\Delta_{|\mathcal{A}|}=\\{\boldsymbol{w}:\sum_{a\in\mathcal{A}}w_{a}=1\\}$ is
the probability simplex across all arms. It is evident that
$\text{OPT}^{\prime}_{\text{LP}}\geq\text{OPT}$, since for a fixed policy
$\pi$ that achieves OPT, the solution
$\bar{\boldsymbol{x}}=\\{\bar{x}_{t,a}\\}_{t\in[T],a\in\mathcal{A}}$ defined
as

$\bar{x}_{t,a}=\mathbb{E}[\mathbf{1}(\text{action $a$ is chosen at $t$ under
$\pi$})]$

is feasible to $\text{OPT}^{\prime}$, and the objective value of
$\bar{\boldsymbol{x}}$ in $\text{OPT}^{\prime}_{\text{LP}}$ is equal to the
expected revenue earned in the online process.

Next, we claim that $\text{OPT}_{\text{LP}}=\text{OPT}^{\prime}_{\text{LP}}$.
Indeed, for each feasible solution $(\boldsymbol{x}_{t})_{t\in[T]}$ to
$\text{OPT}^{\prime}_{\text{LP}}$, the solution

$\boldsymbol{u}=\frac{\sum_{t=1}^{T}q_{t}\boldsymbol{x}_{t}}{\sum_{t=1}^{T}q_{t}},$

is feasible to $\text{LP}_{\text{OPT}}$ and has the same objective value as
$(\boldsymbol{x}_{t})_{t\in[T]}$. Altogether, the Lemma is proved.

##  Appendix B Proofs for Section 3, and Consistency Remarks

In this section, we provide proofs to the lower bound results. In both proofs,
we consider an arbitrary but fixed deterministic online algorithm, that is,
conditioned on the realization of the history in $1,\ldots,t-1$ and $q_{t}$,
$\hat{Q}_{t}$, the chosen arm $A_{t}$ is deterministic. This is without loss
of generality, since the case of random online algorithm can be similarly
handled by replace the chosen arm $A_{t}$ with a probability distribution over
the arms, but we focus on deterministic case to ease the exposition. Lastly,
in Section B.3 we demonstrate that our regret upper and lower bounds are
consistent on the lower bounding instances we constructed in Section B.2.

###  B.1 Proof for Lemma 2

Our lower bound example involve two instances $I^{(1)},I^{(2)}$ with
determinstic rewards and deterministic consumption amounts. Both instances
involve two non-dummy arms $1,2$ in addition to the null arm $a_{0}$, and
there is $d=1$ resource type. Instances $I^{(1)},I^{(2)}$ differ in their
respective seqeunces of demand volumes
$\\{q_{t}^{(1)}\\}_{t=1}^{T},\\{q_{t}^{(2)}\\}_{t=1}^{T}$, but for other
parameters are the same in the two instances.

In both $I^{(1)},I^{(2)}$, arm 1 is associated with (deterministc) reward
$r(1)=1$ and (deterministic) consumption amount $c(1,1)=1$, while arm 2 is
associated with (deterministc) reward $r(2)=3/4$ and (deterministic)
consumption amount $c(2,1)=1/2$. Both instances share the same horizon $T$, a
positive even integer, and the same capacity $B=T/2$. The sequences of demand
volumes $\\{q_{t}^{(1)}\\}_{t=1}^{T},\\{q_{t}^{(2)}\\}_{t=1}^{T}$ of instances
$I^{(1)},I^{(2)}$ are respectively defined as

$\displaystyle q_{t}^{(1)}$ $\displaystyle=\begin{cases}1&~{}\text{if
}t\in\\{1,\ldots,T/2\\},\\\ 1/16&~{}\text{if
}t\in\\{T/2+1,\ldots,T\\},\end{cases}$ $\displaystyle q_{t}^{(2)}$
$\displaystyle=1,\quad\text{for all }t\in\\{1,\ldots,T\\}.$

Then the optimal reward for $I^{(1)}$ is at least $\frac{T}{2}$ (always select
the arm 1 until the resource is fully consumed), and the optimal reward for
$I^{(2)}$ is $\frac{3T}{4}$ (always select arm 2 until the resource is fully
consumed).

Consider the first $T/2$ rounds, and consider an arbitrary online algorithm
that knows $\\{P_{a}\\}_{a\in{\cal A}}$, the sequence
$\\{(q_{s},q_{s}R_{s},q_{s}C_{s,1},\ldots q_{s}C_{s,d})\\}^{t-1}_{s=1}$ and
the time $t$ demand $q_{t}$ when the action $A_{t}$ is to be chosen at each
time $t$. Under this setting, the DM recieves the same set of observations in
the first $T/2$ time steps in each of instances $I^{(1)},I^{(2)}$.
Consequently, the sequence of arm pulls in the first $T/2$ time steps are the
same. Now, we denote $N_{a}=\sum^{T/2}_{t=1}\mathbf{1}(A_{t}=a)$ for
$a\in\\{1,2\\}$. By the previous remark, $N_{a}$ is the number of times arm
$a$ is pulled during time steps $1,\ldots,T/2$ in each of the two instances.
Observe that $N_{1}+N_{2}\leq\frac{T}{2}$, which implies
$N_{1}\leq\frac{T}{4}$ or $N_{2}\leq\frac{T}{4}$. We denote
$\text{Reward}_{T}(I^{(i)}),\text{Regret}_{T}(I^{(i)})$ as the expected reward
and the expected regret of the policy in instance $I^{(i)}$. In what follows,
we demonstrate that

$\max_{i\in\\{1,2\\}}\text{Regret}_{T}(I^{(i)})\geq\frac{T}{32},$ (19)

which proves the Lemma.

Case 1: $N_{1}\leq\frac{T}{4}$. We consider the algorithm on $I^{(1)}$, which
earns

$\text{Reward}_{T}(I^{(1)})\leq\frac{T}{4}\cdot
1+\frac{T}{4}\cdot\frac{3}{4}+\frac{T}{2}\frac{1}{16}=\frac{15}{32}T.$

Hence,

$\text{Regret}_{T}(I^{(1)})\geq\frac{T}{2}-\text{Reward}_{T}(I^{(1)})\geq\frac{1}{32}T.$

Case 2: $N_{2}\leq\frac{T}{4}$. We consider the algorithm on $I^{(2)}$, which
earns

$\text{Reward}_{T}(I^{(2)})=\left(\frac{T}{2}-N_{2}\right)\cdot
1+N_{2}\cdot\frac{3}{4}+\left(\frac{T}{2}-\left(\frac{T}{2}-N_{2}\right)\cdot
1-N_{2}\cdot\frac{1}{2}\right)\cdot\frac{\frac{3}{4}}{\frac{1}{2}}=\frac{T}{2}+\frac{N_{2}}{4}\leq\frac{9}{16}T.$

Hence,

$\text{Regret}_{T}(I^{(2)})\geq\frac{3}{4}T-\text{Reward}_{T}(I^{(2)})\geq\frac{3}{16}T.$

Altogether, the inequality (19) is shown.

###  B.2 Proof for Theorem 1

By the Theorem’s assumption that $\epsilon_{T_{0}+1}>0$ is _$(T_{0}+1,{\cal
F}_{T_{0}+1})$ -sound_, we know that there exists
$\\{q_{t}\\}^{T_{0}}_{t=1}\in[\underline{q},\overline{q}]^{T_{0}}$ such that

$0<\epsilon_{T_{0}+1}\leq\min\left\\{\hat{Q}_{T_{0}+1}-\sum^{T_{0}}_{s=1}q_{s}-\underline{q}(T-T_{0}),\overline{q}(T-T_{0})-\hat{Q}_{T_{0}+1}-\sum^{T_{0}}_{t=1}q_{t},\frac{\hat{Q}_{T_{0}+1}}{2}\right\\},$
(20)

where $\hat{Q}_{T_{0}+1}={\cal F}_{T_{0}+1}(q_{1},\ldots,q_{T_{0}})$. To
proceed, we take a demand volume seqeunce
$\\{q_{t}\\}^{T_{0}}_{t=1}\in[\underline{q},\overline{q}]^{T_{0}}$ that
satisfies the assumption. In what follows, we first construct two
deterministic instances $I^{(1)},I^{(2)}$ which only differ in their
respective seqeunces of demand volumes
$\\{q_{t}^{(1)}\\}_{t=T_{0}+1}^{T},\\{q_{t}^{(2)}\\}_{t=T_{0}+1}^{T}$, but the
two instances are the same on other parameters, and that
$q^{(1)}_{t}=q^{(2)}_{t}=q_{t}$ for $t\in\\{1,\ldots,T_{0}\\}$. Both
$I^{(1)},I^{(2)}$ only involve one resource constraint. We estbalish the
Theorem by showing three claims:

  1. 1.

Both $I^{(1)},I^{(2)}$ are $(T_{0}+1,\epsilon_{T_{0}+1})$-well-estimated by
${\cal F}$, and the underlying online algorithm and prediction oracle (which
are assumed to be fixed but arbitrary in the Theorem statement) suffer

$\text{Regret}_{T}(I^{(i)})\geq\frac{\sum^{T_{0}}_{t=1}q_{t}\epsilon_{T_{0}+1}}{6Q^{(i)}}\;\text{
for some }i\in\\{1,2\\}.$ (21)

In (21), we define $\text{Regret}_{T}(I^{(i)})$ as the regret of the algorithm
on instance $I^{(i)}$, and $Q^{(i)}=\sum^{T}_{t=1}q^{(i)}_{t}$.

  2. 2.

Among the set of instances $\\{J^{(i)}_{c}\\}_{i\in[K]}$ (see Instances
$\\{J^{(i)}_{c}\\}_{i\in[K]}$), the online algorithm suffers

$\text{Regret}_{T}(J^{(i)}_{c})\geq\frac{1}{128}\min\left\\{1,\sqrt{\frac{K\bar{q}}{B}}\right\\}\text{opt}(J^{(i)}_{c})\;\text{
for some }i\in[K],$ (22)

where $\text{opt}(I)$ denote the optimum of instance $I$, even when the DM has
complete knowledge on $q_{1},\ldots,q_{T}$, and $\hat{Q}_{t}$ is equal to the
ground truth $Q$ in each of the instances in $\\{J^{(i)}_{c}\\}_{i\in[K]}$.

  3. 3.

Among the set of instances $\\{J^{(i)}_{r}\\}_{i\in[K]}$ (see Instances
$\\{J^{(i)}_{r}\\}_{i\in[K]}$), the online algorithm suffers

$\text{Regret}_{T}(J^{(i)}_{r})\geq\frac{1}{20}\sqrt{\bar{q}K\text{opt}(J^{(i)}_{r})}\;\text{
for some }i\in[K],$ (23)

even when the DM has complete knowledge on $q_{1},\ldots,q_{T}$, and
$\hat{Q}_{t}$ is equal to the ground truth $Q$ in each of the instances in
$\\{J^{(i)}_{r}\\}_{i\in[K]}$.

Once we establish inequalities (21, 22, 23), the Theorem is shown. We remark
that (22, 23) are direct consequences of Badanidiyuru et al. [2013]. We first
extract the instances $\\{J^{(i)}_{c}\\}_{i\in[K]}$,
$\\{J^{(i)}_{r}\\}_{i\in[K]}$ that are constructed in Badanidiyuru et al.
[2013], then we construct the instances $I^{(1)},I^{(2)}$. After that, we
prove (21), which establish the Theorem.

Instances $\\{J^{(i)}_{c}\\}_{i\in[K]}$. These instances are single resource
instances, with determinsitic rewards but stochastic consumption. According to
Badanidiyuru et al. [2013], we first set parameters

$\eta=\frac{1}{32}\min\left\\{1,\sqrt{\frac{K}{B}}\right\\},\quad
T=\frac{16B}{\eta(1/2-\eta)},$

and set $q_{t}=\overline{q}$ for all $t\in[T]$. The instances
$J^{(1)}_{c},\ldots,J^{(K)}_{c}$ share the same $B,T,\\{q_{t}\\}^{T}_{t=1}$,
and the instances share the same (deterministic) reward function:

$R(a)=r(a)=\begin{cases}1&\quad\text{if }a\in[K]\setminus\\{a_{0}\\}\\\
0&\quad\text{if }a=a_{0}\end{cases}.$

In contrast, instances $J^{(1)}_{c},\ldots,J^{(K)}_{c}$ differ in the resource
consumption model. We denote $C^{(i)}(a)$ as the random consumption of arm $a$
in instance $J^{(i)}_{c}$. The probability distribution of $C^{(i)}(a)$ for
each $a,i\in[K]$ is defined as follow:

$C^{(i)}(a)\sim\begin{cases}\text{Bern}(1/2)&\quad\text{if
}a\in[K]\setminus\\{a_{0},i\\}\\\ \text{Bern}(1/2-\eta)&\quad\text{if }a=i\\\
\text{Bern}(0)&\quad\text{if }a=a_{0}\end{cases},$

where $\text{Bern}(p)$ denotes the Bernoulli distribution with mean $d$. The
regret lower bound (22) is a direct consequence of Lemma 6.10 in Badanidiyuru
et al. [2013], by incorporating the scaling factor $\bar{q}$ into the rewards
earned by the DM and the optimal reward.

Instances $\\{J^{(i)}_{r}\\}_{i\in[K]}$. These instances are single resource
instances, with random rewards but deterministic consumption. These instances
share the same $B,T>K$ (set arbitrarily), the same demand volume seqeunce,
which is $q_{t}=\overline{q}$ for all $t\in[T]$, and the same resource
consumption model, in that $c(a)=0$ for all $a\in{\cal A}$. These instances
only differ in the reward distributions. We denote $R^{(i)}(a)$ as the random
reward of arm $a$ in instance $J^{(i)}_{r}$. The probability distribution of
$R^{(i)}(a)$ for each $a,i\in[K]$ is defined as follow:

$R^{(i)}(a)\sim\begin{cases}\text{Bern}\left(\frac{1}{2}-\frac{1}{4}\sqrt{\frac{K}{T}}\right)&\quad\text{if
}a\in[K]\setminus\\{a_{0},i\\}\\\ \text{Bern}(1/2)&\quad\text{if }a=i\\\
\text{Bern}(0)&\quad\text{if }a=a_{0}\end{cases}.$

The regret lower bound (23) is a direct consequence of Claim 6.2a in
Badanidiyuru et al. [2013], by incorporating the scaling factor $\bar{q}$ into
the rewards earned by the DM and the optimal reward.

Construct $I^{(1)},I^{(2)}$.  We first describe
$\\{q_{t}^{(1)}\\}_{t=1}^{T},\\{q_{t}^{(2)}\\}_{t=1}^{T}$. As previously
mentioned, for $t\in\\{1,\ldots,T_{0}\\}$, we have
$q_{t}^{(1)}=q_{t}^{(2)}=q_{t}$. To define $q^{(1)}_{t},q^{(2)}_{t}$ for
$t\in\\{T_{0}+1,\ldots,T\\}$, first recall that
$|\hat{Q}_{T_{0}+1}-Q|\leq\epsilon_{T_{0}+1}$, where $\epsilon_{T_{0}+1}$
satisfies (20). By (20), we know that
$\hat{Q}_{T_{0}+1}-\epsilon_{T_{0}+1}-\sum^{T_{0}}_{t=1}q_{t}\geq\underline{q}(T-T_{0})$,
and that
$\hat{Q}_{T_{0}+1}+\epsilon_{T_{0}+1}-\sum^{T_{0}}_{t=1}q_{t}\leq\overline{q}(T-T_{0})$.
We set $q^{(1)}_{T_{0}+1}=\ldots=q^{(1)}_{T}\in[\underline{q},\overline{q}]$
and $q^{(2)}_{T_{0}+1}=\ldots=q^{(2)}_{T}\in[\underline{q},\overline{q}]$ such
that

$Q^{(1)}=\sum_{t=1}^{T}q_{t}^{(1)}=\hat{Q}_{T_{0}+1}-\epsilon_{T_{0}+1},\quad
Q^{(2)}=\sum_{t=1}^{T}q_{t}^{(2)}=\hat{Q}_{T_{0}+1}+\epsilon_{T_{0}+1},$

which is valid by the stated inequalities.

Next, we define the parameters
$\\{r(a)\\}_{a\in\mathcal{A}},\\{c(a,1)\\}_{a},B$. (recall $d=1$) Similar to
the proof for Lemma 2, we only consider deterministic instances, so it is
sufficient to define the mean rewards and consumption amounts. To facilitate
our discussion, we specify ${\cal A}=[K]=\\{1,2,\ldots,K\\}$, with $K\geq 3$
and arm $K$ being the null arm. The parameters
$\\{r(a)\\}_{a\in\mathcal{A}},\\{c(a,1)\\}_{a},B$ shared between instances
$I^{(1)},I^{(2)}$ are defined as follows:

$r(a)=\begin{cases}1&\quad\text{if }a=1,\\\ (1+c)/2&\quad\text{if }a=2,\\\
0&\quad\text{if }a\in\\{3,\ldots,K\\},\end{cases}$

and

$c(a,1)=\begin{cases}1&\quad\text{if }a=1,\\\ c&\quad\text{if }a=2,\\\
0&\quad\text{if }a\in\\{3,\ldots,K\\},\end{cases}$

where

$c=\frac{\hat{Q}_{T_{0}+1}-\epsilon_{T_{0}+1}}{\hat{Q}_{T_{0}+1}+\epsilon_{T_{0}+1}}.$

Finally, we set

$B=\hat{Q}_{T_{0}+1}-\epsilon_{T_{0}+1}.$

Inequality (20) ensures that $c,B>0$.

Proving (21). To evaluate the regrets in the two instances, we start with the
optimal reawrds. The optimal reward in $I^{(1)}$ is
$\hat{Q}_{T_{0}+1}-\epsilon_{T_{0}+1}$, which is achieved by pulling arm 1
until the resource is exhasuted. The optimal reward for $I^{(2)}$ is
$\hat{Q}_{T_{0}+1}$, which is achieved by pulling arm 2 until the resource is
exhasuted.

Consider the execution of the fixed but arbitrary online algorithm during time
steps $1,\ldots,T_{0}$ in each of the instances. The prediction oracle returns
the same prediction $\hat{Q}_{t}$ for $t\in\\{1,\ldots,T_{0}\\}$ in both
instances, since both instances share the same $r,c,B,T$ and
$q^{(1)}_{t}=q^{(2)}_{t}$ for $t\in\\{1,\ldots,T_{0}\\}$. Consequently, the
fixed but arbitrary online algorithm has the same sequence of arm pulls
$A_{1},\ldots,A_{T_{0}}$ during time steps $1,\ldots,T_{0}$ in both instances
$I^{(1)},I^{(2)}$. Now, for each arm $i\in\\{1,2\\}$, we define
$N_{i}=\\{t\in\\{1,\ldots,T_{0}\\}:A_{t}=i\\}$, which has the same realization
in instances $I^{(1)},I^{(2)}$. Since $N_{1}\cup N_{2}\subseteq[T_{0}]$, at
least one of the cases $\sum_{t\in
N_{1}}q_{t}\leq\frac{1}{2}\sum_{s=1}^{T_{0}}q_{s}$ or $\sum_{t\in
N_{2}}q_{t}\leq\frac{1}{2}\sum_{s=1}^{T_{0}}q_{s}$ holds.

We denote $\text{Reward}_{T}(I^{(i)})$ as the expected reward of the online
algorithm in instance $I^{(i)}$. We proceed with the following case
consideration:

Case 1: $\sum_{t\in N_{1}}q_{t}\leq\frac{1}{2}\sum_{s=1}^{T_{0}}q_{s}$. We
consider the online algorithm’s execution on $I^{(1)}$, which yields

$\displaystyle\text{Reward}_{T}(I^{(1)})$
$\displaystyle\leq\frac{\sum_{s=1}^{T_{0}}q_{s}}{2}\cdot
1+\frac{\sum_{s=1}^{T_{0}}q_{s}}{2}\cdot\frac{1}{2}(1+c)+\left(\hat{Q}_{T_{0}+1}-\epsilon_{T_{0}+1}-\sum_{s=1}^{T_{0}}q_{s}\right)\cdot
1$
$\displaystyle=\left(\sum_{s=1}^{T_{0}}q_{s}\right)\left(-\frac{1}{4}+\frac{1}{4}c\right)+\hat{Q}_{T_{0}+1}-\epsilon_{T_{0}+1}.$

Hence,

$\text{Regret}_{T}(I^{(1)})\geq\left(\sum_{s=1}^{T_{0}}q_{s}\right)\cdot\frac{1}{4}(1-c)=\frac{\sum_{s=1}^{T_{0}}q_{s}\epsilon_{T_{0}+1}}{2(\hat{Q}_{T_{0}+1}+\epsilon_{T_{0}+1})}\geq\frac{\sum_{s=1}^{T_{0}}q_{s}\epsilon_{T_{0}+1}}{6(\hat{Q}_{T_{0}+1}-\epsilon_{T_{0}+1})}=\frac{\sum_{s=1}^{T_{0}}q_{s}\epsilon_{T_{0}+1}}{6Q^{(1)}},$

where the last inequality is by item (1) in property $(\dagger)$. To this end,
recall $\hat{Q}_{T_{0}+1}-\epsilon_{T_{0}+1}=\sum^{T}_{t=1}q^{(1)}_{t}$.

Case 2: $\sum_{t\in N_{2}}q_{t}\leq\frac{1}{2}\sum_{s=1}^{T_{0}}q_{s}$. We
consider the online algorithm’s execution on $I^{(2)}$, which yields

$\displaystyle\text{Reward}_{T}(I^{(2)})$
$\displaystyle\leq\left(\sum_{s=1}^{T_{0}}q_{s}-\sum_{t\in
N_{2}}q_{t}\right)\cdot 1+\sum_{t\in
N_{2}}q_{t}\cdot\frac{1}{2}(1+c)+\left(B-\left(\sum_{s=1}^{T_{0}}q_{s}-\sum_{t\in
N_{2}}q_{t}\right)-\sum_{t\in N_{2}}q_{t}\cdot
c\right)\cdot\frac{\frac{1}{2}(1+c)}{c}$
$\displaystyle=\sum_{s=1}^{T_{0}}q_{s}\left(1-\frac{1+c}{2c}\right)+\left(\sum_{s\in
N_{2}}q_{s}\right)\left[-1+\frac{1+c}{2}+\frac{1+c}{2c}-\frac{1+c}{2}\right]+B\cdot\frac{1+c}{2c}$
$\displaystyle=-\frac{\sum_{s=1}^{T_{0}}q_{s}\epsilon_{T_{0}+1}}{\hat{Q}_{T_{0}+1}-\epsilon_{T_{0}+1}}+\left(\sum_{s\in
N_{2}}q_{s}\right)\cdot\frac{\epsilon_{T_{0}+1}}{\hat{Q}_{T_{0}+1}-\epsilon_{T_{0}+1}}+\hat{Q}_{T_{0}}$
$\displaystyle\leq-\frac{\sum_{s=1}^{T_{0}}q_{s}\epsilon_{T_{0}+1}}{2(\hat{Q}_{T_{0}+1}-\epsilon_{T_{0}+1})}+\hat{Q}_{T_{0}+1}.$

Hence,

$\text{Regret}_{T}(I^{(2)})\geq\frac{\sum_{s=1}^{T_{0}}q_{s}\epsilon_{T_{0}+1}}{2(\hat{Q}_{T_{0}+1}-\epsilon_{T_{0}+1})}\geq\frac{\sum_{s=1}^{T_{0}}q_{s}\epsilon_{T_{0}+1}}{2(\hat{Q}_{T_{0}+1}+\epsilon_{T_{0}+1})}=\frac{\sum_{s=1}^{T_{0}}q_{s}\epsilon_{T_{0}+1}}{2Q^{(2)}}.$

Altogether, the Theorem is proved.

###  B.3 Consistency Between Regret Upper and Lower Bounds

Recall that in the proof of Theorem 1, we constructed two instances
$I^{(1)},I^{(2)}$ such that (see (21):

$\text{Regret}_{T}(I^{(i)})\geq\frac{\sum^{T_{0}}_{t=1}q_{t}\epsilon_{T_{0}+1}}{6Q^{(i)}}\;\text{
for some }i\in\\{1,2\\},$ (24)

where $\text{Regret}_{T}(I^{(i)})$ is the regret of an arbitrary but fixed
online algorithm on $I^{(i)}$, with its prediction oracle satisfying that

$|Q^{(i)}-\hat{Q}_{t}|\leq\epsilon_{T_{0}+1}\quad\text{ for each
$i\in\\{1,2\\}$.}$ (25)

In the lower bound analysis on $I^{(1)},I^{(2)}$, we establish the regret
lower bound (24) solely hinging on the model uncertainty on $Q^{(1)},Q^{(2)}$,
and the bound (24) still holds when the DM knows
$\\{P_{a}\\}_{a\in\mathcal{A}}$.

In particular, we can set the online algorihtm to be OA-UCB, with an oracle
that satisfies the property (25) above. Now, also recall in our construction
that $q^{(1)}_{t}=q^{(2)}_{t}=q_{t}$ for all $t\in[T_{0}]$, thus the
predictions $\hat{Q}_{t}$ for $t\in[T_{0}]$ are the same in the two instances,
whereas $Q^{(1)}=\hat{Q}_{T_{0}+1}-\epsilon_{T_{0}+1}$ but
$Q^{(2)}=\hat{Q}_{T_{0}+1}+\epsilon_{T_{0}+1}$, while we still have
$Q^{(2)}\leq 3Q^{(1)}$, so that $Q^{(1)}=\Theta(Q^{(2)})$. Therefore, (24) is
equivalent to

$\max_{i\in\\{1,2\\}}\\{\text{Regret}_{T}(I^{(i)})\\}\geq\Omega\left(\frac{\sum^{T_{0}}_{t=1}q_{t}\epsilon_{T_{0}+1}}{Q^{(1)}}\right).$
(26)

To demonstrate the consistency, it suffices to show

$\max_{i\in\\{1,2\\}}\left\\{\frac{1}{Q^{(1)}}\sum_{t=1}^{\tau-1}q_{t}\epsilon^{(i)}_{t}\right\\}=\Omega\left(\frac{\sum^{T_{0}}_{t=1}q_{t}\epsilon_{T_{0}+1}}{Q^{(1)}}\right).$
(27)

where $\epsilon^{(i)}_{t}=|\hat{Q}_{t}-Q^{(i)}|$ is the prediction error on
instance $I^{(i)}$ at time $t$. Indeed, to be consistent, we should have
Theorem 2 holds true for both instances, while (26) still holds true. We
establish (27) as follows:

$\displaystyle\max_{i\in\\{1,2\\}}\left\\{\sum_{t=1}^{\tau-1}q_{t}\epsilon^{(i)}_{t}\right\\}$
$\displaystyle\geq\sum_{t=1}^{\tau-1}q_{t}\frac{\epsilon^{(1)}_{t}+\epsilon^{(2)}_{t}}{2}$
$\displaystyle=\sum_{t=1}^{\tau-1}q_{t}\frac{|\hat{Q}_{t}-\hat{Q}_{T_{0}+1}+\epsilon_{T_{0}+1}|+|\hat{Q}_{t}-\hat{Q}_{T_{0}+1}-\epsilon_{T_{0}+1}|}{2}$
$\displaystyle\geq\sum_{t=1}^{\tau-1}q_{t}\frac{2\epsilon_{T_{0}+1}}{2}$ (28)
$\displaystyle\geq\sum_{t=1}^{T_{0}}q_{t}\epsilon_{T_{0}+1}.$ (29)

Step (28) is by the triangle inequality, and step (29) is by the fact that for
any algorithm that fully exhausts the resource, its stopping time $\tau>T_{0}$
(In the case when OA-UCB does not fully consume all the resource at the end of
time $T$, by definition we have $\tau=T+1>T_{0}$). By construction, the common
budget $B$ in both instances is strictly larger than
$\sum^{T_{0}}_{t=1}q_{t}$, thus the resource is always not exhasuted at
$T_{0}$, since at time $t\in[T_{0}]$ the DM consumes at most $q_{t}$ units of
resource. Altogether, (27) is shown and consistency is verified.

##  Appendix C Proof of Theorem 2

Before we embark on the proof, we first state a well known result on online
gradient descent:

######  Lemma 5 (Theorem 3.1 in Hazan et al. [2016]).

Suppose $\\{f_{t}\\}$ are convex functions, then Online Gradient Descent
presented in Algorithm 3 applied on $\\{f_{t}\\}$ with step sizes
$\\{\eta_{t}=\frac{D}{G\sqrt{t}}\\}$ guarantees the following for all $T\geq
1$:

$\sum_{t=1}^{T}f_{t}(\boldsymbol{x}_{t})-\min_{\boldsymbol{x}^{*}\in
S}\sum_{t=1}^{T}f_{t}(\boldsymbol{x}^{*})\leq\frac{3}{2}GD\sqrt{T},$

where $D=\text{diam}(S)$ and $G=\max_{t}\|\nabla f_{t}\|$.

Algorithm 3 Online Gradient Descent

1:Initialize convex set $S$, $\boldsymbol{x}_{1}\in\mathcal{K}$, step sizes
$\\{\eta_{t}\\}_{t=1}^{T}$.

2:for $t=1,2,...,T$ do

3: Play $\boldsymbol{x}_{t}$ and observe cost $f_{t}(\boldsymbol{x}_{t})$.

4: Update
$\boldsymbol{x}_{t+1}=\Pi_{S}\left(\boldsymbol{x}_{t}-\eta_{t}\nabla
f_{t}(\boldsymbol{x}_{t})\right).$

Now we begin the proof of Theorem 2. Denote
$\textbf{UCB}_{r,t}=(\text{UCB}_{r,t}(a))_{a\in\mathcal{A}}$,
$\textbf{LCB}_{c,t}=(\textbf{LCB}_{c,t}(a,i))_{a\in\mathcal{A},i\in[d]}$. We
first claim that, at a time step $t\leq\tau$,

$\boldsymbol{e}_{A_{t}}\in\mathop{\arg\max}_{\boldsymbol{u}\in\Delta_{|\mathcal{A}|}}\
\textbf{UCB}_{c,t}^{\top}\boldsymbol{u}-\frac{\hat{Q}_{t}}{B}\cdot\boldsymbol{\mu}_{t}^{\top}\textbf{LCB}_{c,t}^{\top}\boldsymbol{u}.$
(30)

In fact, the following linear optimization problem

$\displaystyle\max$
$\displaystyle\textbf{UCB}_{r,t}^{\top}\boldsymbol{u}-\frac{\hat{Q}_{t}}{B}\cdot\boldsymbol{\mu}_{t}^{\top}\textbf{LCB}_{c,t}^{\top}\boldsymbol{u}$
s.t. $\displaystyle\boldsymbol{u}\in\Delta_{|\mathcal{A}|}$

has an extreme point solution such that
$\boldsymbol{u}^{*}=\boldsymbol{e}_{a}$ for some $a\in\mathcal{A}$. According
to the definition of $A_{t}$, we know that
$\boldsymbol{u}^{*}=\boldsymbol{e}_{A_{t}}$. Then the claim holds. Suppose
$\boldsymbol{u}^{*}$ is an optimal solution of (2), then we have
$\text{OPT}_{\text{LP}}=Q\boldsymbol{r}^{\top}\boldsymbol{u}^{*}$,
$Q\boldsymbol{c}^{\top}\boldsymbol{u}^{*}\leq B\boldsymbol{1}$ and
$\boldsymbol{u}^{*}\in\Delta_{|\mathcal{A}|}$. By the optimality of (30), we
have

$\text{UCB}_{r,t}(A_{t})-\frac{\hat{Q}_{t}}{B}\cdot\boldsymbol{\mu}_{t}^{\top}\textbf{LCB}_{c,t}(A_{t})=\textbf{UCB}_{r,t}^{\top}\boldsymbol{e}_{A_{t}}-\frac{\hat{Q}_{t}}{B}\cdot\boldsymbol{\mu}_{t}^{\top}\textbf{LCB}_{c,t}^{\top}\boldsymbol{e}_{A_{t}}\geq\textbf{UCB}_{r,t}^{\top}\boldsymbol{u}^{*}-\frac{\hat{Q}_{t}}{B}\cdot\boldsymbol{\mu}_{t}^{\top}\textbf{LCB}_{c,t}\boldsymbol{u}^{*},$

which is equivalent to

$\textbf{UCB}_{r,t}^{\top}\boldsymbol{u}^{*}-\text{UCB}_{r,t}(A_{t})+\frac{\hat{Q}_{t}}{B}\cdot\boldsymbol{\mu}_{t}^{\top}\left(\frac{B}{\hat{Q}_{t}}\boldsymbol{1}_{d}-\textbf{LCB}_{c,t}^{\top}\boldsymbol{u}^{*}\right)\leq\frac{\hat{Q}_{t}}{B}\cdot\boldsymbol{\mu}_{t}^{\top}\left(\frac{B}{\hat{Q}_{t}}\boldsymbol{1}_{d}-\textbf{LCB}_{c,t}(A_{t})\right).$

Times $q_{t}$ on both side and sum all $t$ from 1 to $\tau-1$ and apply Lemma
5 with
$f_{t}(\boldsymbol{x})=\frac{q_{t}\hat{Q}_{t}}{B}\left(\frac{B}{\hat{Q}_{t}}\boldsymbol{1}_{d}-\textbf{LCB}_{c,t}(A_{t})\right)^{\top}\boldsymbol{x}$,
$S=\\{\boldsymbol{\mu}:\|\boldsymbol{\mu}\|_{1}\leq
1,\boldsymbol{\mu}\geq\boldsymbol{0}_{d}\\}$, $D=\text{diam}(S)=\sqrt{2}$,
$G=\max_{t}\|\nabla f_{t}\|=M$, then we obtain

$\displaystyle\sum_{t=1}^{\tau-1}q_{t}\textbf{UCB}_{r,t}^{\top}\boldsymbol{u}^{*}-\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{r,t}(A_{t})+\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\cdot\boldsymbol{\mu}_{t}^{\top}\left(\frac{B}{\hat{Q}_{t}}\boldsymbol{1}_{d}-\textbf{LCB}_{c,t}^{\top}\boldsymbol{u}^{*}\right)$
(31) $\displaystyle\leq$
$\displaystyle\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\cdot\boldsymbol{\mu}_{t}^{\top}\left(\frac{B}{\hat{Q}_{t}}\boldsymbol{1}_{d}-\textbf{LCB}_{c,t}(A_{t})\right)$
$\displaystyle\leq$ $\displaystyle\min_{\boldsymbol{\mu}^{*}\in
S}\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\cdot\left(\frac{B}{\hat{Q}_{t}}\boldsymbol{1}_{d}-\textbf{LCB}_{c,t}(A_{t})\right)^{\top}\boldsymbol{\mu}^{*}+O\left(M\sqrt{T}\right)$
$\displaystyle\leq$
$\displaystyle\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\cdot\left(\frac{B}{\hat{Q}_{t}}\boldsymbol{1}_{d}-\textbf{LCB}_{c,t}(A_{t})\right)^{\top}\boldsymbol{\mu}+O\left(M\sqrt{T}\right),\quad\forall\boldsymbol{\mu}\in
S.$

Recap by lemma 4 that with probability $\geq 1-3KTd\delta$, we have

$\textbf{LCB}_{c,t}\leq\boldsymbol{c}.$

Hence, with probability $\geq 1-3KTd\delta$,

$\displaystyle\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\cdot\boldsymbol{\mu}_{t}^{\top}\left(\frac{B}{\hat{Q}_{t}}\boldsymbol{1}_{d}-\textbf{LCB}_{c,t}^{\top}\boldsymbol{u}^{*}\right)$
$\displaystyle\geq\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\cdot\boldsymbol{\mu}_{t}^{\top}\left(\frac{B}{\hat{Q}_{t}}\boldsymbol{1}_{d}-\boldsymbol{c}^{\top}\boldsymbol{u}^{*}\right)$
(32a)
$\displaystyle=\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\cdot\boldsymbol{\mu}_{t}^{\top}\left(\frac{B}{\hat{Q}_{t}}\boldsymbol{1}_{d}-\frac{B}{Q}\boldsymbol{1}_{d}\right)+\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\cdot\boldsymbol{\mu}_{t}^{\top}\left(\frac{B}{Q}\boldsymbol{1}_{d}-\boldsymbol{c}^{\top}\boldsymbol{u}^{*}\right)$
(32b)
$\displaystyle\geq\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\cdot\boldsymbol{\mu}_{t}^{\top}\left(\frac{B}{\hat{Q}_{t}}\boldsymbol{1}_{d}-\frac{B}{Q}\boldsymbol{1}_{d}\right)$
(32c)
$\displaystyle=\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\left(\frac{B}{\hat{Q}_{t}}-\frac{B}{Q}\right)\|\boldsymbol{\mu}_{t}\|_{1},$
(32d)

where (32a) comes from Lemma 4, (32b) comes from rearranging the sum, and
(32c) comes from the fact the definition of $\boldsymbol{u}^{*}$. We first
consider the case $\tau\leq T$, which implies that there exists $j_{0}\in[d]$
such that

$\sum_{t=1}^{\tau}q_{t}C_{t,j_{0}}>B\quad\Rightarrow\quad\sum_{t=1}^{\tau-1}q_{t}C_{t,j_{0}}>B-\overline{q}.$
(33)

Take $\boldsymbol{\mu}=\lambda\boldsymbol{e}_{j_{0}}$, where $\lambda\in[0,1]$
is a constant that we tune later. In this case, with probability $\geq
1-3KT\delta$,

$\sum_{t=1}^{\tau-1}q_{t}\textbf{UCB}_{r,t}^{\top}\boldsymbol{u}^{*}\geq\sum_{t=1}^{\tau-1}q_{t}\boldsymbol{r}_{t}^{\top}\boldsymbol{u}^{*}=\text{OPT}_{\text{LP}}\frac{Q_{\tau-1}}{Q},$
(34)

and

$\displaystyle\lambda\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\left(\frac{B}{\hat{Q}_{t}}\boldsymbol{1}_{d}-\textbf{LCB}_{c,t}(A_{t})\right)^{\top}\boldsymbol{e}_{j_{0}}$
$\displaystyle=\lambda\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\left(\frac{B}{\hat{Q}_{t}}-\text{LCB}_{c,t}(A_{t},j_{0})\right)$
(35)
$\displaystyle=\lambda\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\left(\frac{B}{\hat{Q}_{t}}-\frac{B}{Q}\right)+\lambda\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\left(\frac{B}{Q}-C_{t,j_{0}}\right)$
$\displaystyle+\lambda\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\left(C_{t,j_{0}}-\text{LCB}_{c,t}(A_{t},j_{0})\right).$

Then we deal with each term respectively:

$\displaystyle\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\left(\frac{B}{Q}-C_{t,j_{0}}\right)$
$\displaystyle=\sum_{t=1}^{\tau-1}q_{t}\frac{Q}{B}\left(\frac{B}{Q}-C_{t,j_{0}}\right)+\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}-Q}{B}\left(\frac{B}{Q}-C_{t,j_{0}}\right)$
(36a) $\displaystyle\leq
Q_{\tau-1}-\frac{Q}{B}\sum_{t=1}^{\tau-1}q_{t}C_{t,j_{0}}+\frac{1}{B}\sum_{t=1}^{\tau-1}q_{t}\epsilon_{t}\left|\frac{B}{Q}-C_{t,j_{0}}\right|$
(36b)
$\displaystyle<Q_{\tau-1}-Q+\frac{Q}{B}\overline{q}+\frac{1}{B}\sum_{t=1}^{\tau-1}q_{t}\epsilon_{t}\frac{B}{Q}+\frac{1}{B}\sum_{t=1}^{\tau-1}q_{t}\epsilon_{t}C_{t,j_{0}}$
(36c) $\displaystyle\leq
Q_{\tau-1}-Q+\frac{Q}{B}\overline{q}+\left(\frac{1}{Q}+\frac{1}{B}\right)\sum_{t=1}^{\tau-1}q_{t}\epsilon_{t},$
(36d)

where (36a) comes from rearranging the sum, (36c) comes from the (33), and
(36d) comes from the assumption that $C_{t,j_{0}}$ is supported in $[0,1]$.
Similarly,

$\begin{aligned}
\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\left(C_{t,j_{0}}-\text{LCB}_{c,t}(A_{t},j_{0})\right)&=\sum_{t=1}^{\tau-1}q_{t}\frac{Q}{B}\left(C_{t,j_{0}}-\text{LCB}_{c,t}(A_{t},j_{0})\right)+\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}-Q}{B}\left(C_{t,j_{0}}-\text{LCB}_{c,t}(A_{t},j_{0})\right)\\\
&\leq\frac{Q}{B}\left|\sum_{t=1}^{\tau-1}q_{t}\left(C_{t,j_{0}}-\text{LCB}_{c,t}(A_{t},j_{0})\right)\right|+\frac{1}{B}\sum_{t=1}^{\tau-1}q_{t}\epsilon_{t},\end{aligned}$

(37)

where the equality comes from rearranging the sum, and the inequality comes
from the assuption that $|\hat{Q}_{t}-Q|\leq\epsilon_{t}$,
$0\leq\text{LCB}_{c,t}(A_{t},j_{0}),C_{t,j_{0}}\leq 1$. Combine (35), (36) and
(37), we obtain

$\begin{aligned}
\lambda\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\left(\frac{B}{\hat{Q}_{t}}\boldsymbol{1}_{d}-\textbf{LCB}_{c,t}(A_{t})\right)^{\top}\boldsymbol{e}_{j_{0}}&\leq\lambda\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\left(\frac{B}{\hat{Q}_{t}}-\frac{B}{Q}\right)+\lambda\left(Q_{\tau-1}-Q+\frac{Q}{B}\overline{q}+\left(\frac{1}{Q}+\frac{1}{B}\right)\sum_{t=1}^{\tau-1}q_{t}\epsilon_{t}\right)\\\
&+\lambda\left(\frac{Q}{B}\left|\sum_{t=1}^{\tau-1}q_{t}\left(C_{t,j_{0}}-\text{LCB}_{c,t}(A_{t},j_{0})\right)\right|+\frac{1}{B}\sum_{t=1}^{\tau-1}q_{t}\epsilon_{t}\right)\\\
&\leq\lambda\left(Q_{\tau-1}-Q+\frac{Q}{B}\overline{q}+\frac{Q}{B}\left|\sum_{t=1}^{\tau-1}q_{t}\left(C_{t,j_{0}}-\text{LCB}_{c,t}(A_{t},j_{0})\right)\right|\right)\\\
&+\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\left(\frac{B}{\hat{Q}_{t}}-\frac{B}{Q}\right)+O\left(\left(\frac{1}{Q}+\frac{1}{B}\right)\sum_{t=1}^{\tau-1}q_{t}\epsilon_{t}\right),\end{aligned}$

(38)

where the second inequality comes from the assumption that $\lambda\in[0,1]$.
Finally, combine (31), (32), (34), (38), we obtain

$\displaystyle\text{OPT}_{\text{LP}}\frac{Q_{\tau-1}}{Q}-\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{r,t}(A_{t})+\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\left(\frac{B}{\hat{Q}_{t}}-\frac{B}{Q}\right)\|\boldsymbol{\mu}_{t}\|_{1}$
$\displaystyle\leq$
$\displaystyle\lambda\left(Q_{\tau-1}-Q+\frac{Q}{B}\overline{q}+\frac{Q}{B}\left|\sum_{t=1}^{\tau-1}q_{t}\left(C_{t,j_{0}}-\text{LCB}_{c,t}(A_{t},j_{0})\right)\right|\right)+\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\left(\frac{B}{\hat{Q}_{t}}-\frac{B}{Q}\right)+O\left(\left(\frac{1}{Q}+\frac{1}{B}\right)\sum_{t=1}^{\tau-1}q_{t}\epsilon_{t}\right),$

which is equivalent to

$\displaystyle\text{OPT}_{\text{LP}}-\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{r,t}(A_{t})$
$\displaystyle\leq\text{OPT}_{\text{LP}}\left(1-\frac{Q_{\tau-1}}{Q}\right)+\lambda\left(Q_{\tau-1}-Q+\frac{Q}{B}\overline{q}+\frac{Q}{B}\left|\sum_{t=1}^{\tau-1}q_{t}\left(C_{t,j_{0}}-\text{LCB}_{c,t}(A_{t},j_{0})\right)\right|\right)$
$\displaystyle+\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\left(\frac{B}{\hat{Q}_{t}}-\frac{B}{Q}\right)(1-\|\boldsymbol{\mu}_{t}\|_{1})+O\left(\left(\frac{1}{Q}+\frac{1}{B}\right)\sum_{t=1}^{\tau-1}q_{t}\epsilon_{t}\right)+O\left(M\sqrt{T}\right).$

Let $\lambda=\frac{\text{OPT}_{\text{LP}}}{Q}\leq 1$ (This is because
$\text{OPT}_{\text{LP}}=Q\boldsymbol{r}^{\top}\boldsymbol{u}^{*}\leq Q$), then
we can further derive with probability $\geq 1-3KTd\delta$,

$\begin{aligned}
\text{OPT}_{\text{LP}}-\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{r,t}(A_{t})&\leq\text{OPT}_{\text{LP}}\left(1-\frac{Q_{\tau-1}}{Q}\right)+\frac{\text{OPT}_{\text{LP}}}{Q}\left(Q_{\tau-1}-Q+\frac{Q}{B}\overline{q}+\frac{Q}{B}\left|\sum_{t=1}^{\tau-1}q_{t}\left(C_{t,j_{0}}-\text{LCB}_{c,t}(A_{t},j_{0})\right)\right|\right)\\\
&+\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\left(\frac{B}{\hat{Q}_{t}}-\frac{B}{Q}\right)(1-\|\boldsymbol{\mu}_{t}\|_{1})+O\left(\left(\frac{1}{Q}+\frac{1}{B}\right)\sum_{t=1}^{\tau-1}q_{t}\epsilon_{t}\right)+O\left(M\sqrt{T}\right)\\\
&=\frac{\text{OPT}_{\text{LP}}}{B}\overline{q}+\frac{\text{OPT}_{\text{LP}}}{B}\left|\sum_{t=1}^{\tau-1}q_{t}\left(C_{t,j_{0}}-\text{LCB}_{c,t}(A_{t},j_{0})\right)\right|+\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\left(\frac{B}{\hat{Q}_{t}}-\frac{B}{Q}\right)(1-\|\boldsymbol{\mu}_{t}\|_{1})\\\
&+O\left(\left(\frac{1}{Q}+\frac{1}{B}\right)\sum_{t=1}^{\tau-1}q_{t}\epsilon_{t}\right)+O\left(M\sqrt{T}\right)\\\
&\leq
O\left(\log\left(\frac{1}{\delta}\right)\text{OPT}_{\text{LP}}\left(\sqrt{\frac{\overline{q}K}{B}}+\frac{\overline{q}K}{B}\log\left(\frac{T}{K}\right)\right)+\left(\frac{1}{Q}+\frac{1}{B}\right)\sum_{t=1}^{\tau-1}q_{t}\epsilon_{t}+M\sqrt{T}\right)\\\
&=O\left(\log\left(\frac{1}{\delta}\right)\text{OPT}_{\text{LP}}\sqrt{\frac{\overline{q}K}{B}}+\left(\frac{1}{Q}+\frac{1}{B}\right)\sum_{t=1}^{\tau-1}q_{t}\epsilon_{t}+M\sqrt{T}\right),\end{aligned}$

(39)

where the second inequality comes from Lemma 15 and the following

$\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\left(\frac{B}{\hat{Q}_{t}}-\frac{B}{Q}\right)(1-\|\boldsymbol{\mu}_{t}\|_{1})\leq\sum_{t=1}^{\tau}q_{t}\frac{\hat{Q}_{t}}{B}\left|\frac{B}{Q}-\frac{B}{\hat{Q}_{t}}\right|=\frac{1}{Q}\sum_{t=1}^{\tau}q_{t}\left|\hat{Q}_{t}-Q\right|\leq\frac{1}{Q}\sum_{t=1}^{\tau}q_{t}\epsilon_{t}.$

The above concludes our arguments for the case $\tau\leq T$. In complement, we
then consider the case $\tau>T$, which means that $\tau=T+1$, and no resource
is fully exhausted during the horizon. With probability $\geq 1-3KT\delta$, we
have

$\sum_{t=1}^{T}q_{t}\textbf{UCB}_{r,t}^{\top}\boldsymbol{u}^{*}\geq\sum_{t=1}^{T}q_{t}\boldsymbol{r}_{t}^{\top}\boldsymbol{u}^{*}=\text{OPT}_{\text{LP}}.$
(40)

Take $\boldsymbol{\mu}=0$ and combine (31), (32), (40), with probablity $\geq
1-3KT\delta$, we have

$\displaystyle\text{OPT}_{\text{LP}}-\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{r,t}(A_{t})$
$\displaystyle\leq-\sum_{t=1}^{\tau-1}q_{t}\frac{\hat{Q}_{t}}{B}\left(\frac{B}{\hat{Q}_{t}}-\frac{B}{Q}\right)\|\boldsymbol{\mu}_{t}\|_{1}+O\left(M\sqrt{T}\right)$
(41) $\displaystyle\leq
O\left(\frac{1}{Q}\sum_{t=1}^{\tau-1}q_{t}\epsilon_{t}+M\sqrt{T}\right).$

Combine (41) and (39), for any stopping time $\tau$, with probability $\geq
1-3KTd\delta$, we have

$\text{OPT}_{\text{LP}}-\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{r,t}(A_{t})\leq
O\left(\log\left(\frac{1}{\delta}\right)\text{OPT}_{\text{LP}}\sqrt{\frac{\overline{q}K}{B}}+\left(\frac{1}{Q}+\frac{1}{B}\right)\sum_{t=1}^{\tau-1}q_{t}\epsilon_{t}+M\sqrt{T}\right).$

By Lemma 14, we can further derive it to the high probability bound, that with
probability $\geq 1-3KTd\delta$,

$\begin{aligned} \text{OPT}_{\text{LP}}-\sum_{t=1}^{\tau-1}q_{t}R_{t}&\leq
O\left(\log\left(\frac{1}{\delta}\right)\left(\text{OPT}_{\text{LP}}\sqrt{\frac{\overline{q}K}{B}}+\sqrt{\overline{q}K\sum_{t=1}^{\tau-1}q_{t}R_{t}}+\overline{q}K\log\left(\frac{T}{K}\right)\right)+\left(\frac{1}{Q}+\frac{1}{B}\right)\sum_{t=1}^{\tau-1}q_{t}\epsilon_{t}+M\sqrt{T}\right)\\\
&\leq
O\left(\log\left(\frac{1}{\delta}\right)\left(\text{OPT}_{\text{LP}}\sqrt{\frac{\overline{q}K}{B}}+\sqrt{\overline{q}K\text{OPT}_{\text{LP}}}\right)+\left(\frac{1}{Q}+\frac{1}{B}\right)\sum_{t=1}^{\tau-1}q_{t}\epsilon_{t}+M\sqrt{T}\right),\end{aligned}$

where the second inequality comes from the fact that
$\text{OPT}_{\text{LP}}\geq\sum_{t=1}^{\tau-1}q_{t}R_{t}$. Now we finish the
proof of Theorem 2.

##  Appendix D Proofs for Confidence Radii

This section contains proofs for the confidence radius results, which largely
follow the literature, but we provide complete proofs since we are in a non-
stationary setting. Section D.1 provides the proof for Lemma 3, which allows
us to extract the implicit constants in existing proofs in Babaioff et al.
[2015], Agrawal and Devanur [2014]. Section D.2 provides the proof for Lemma
4. Finally, section D.3, we prove inequalities (14, 15).

###  D.1 Proof for Lemma 3, due to Babaioff et al. [2015], Agrawal and Devanur
[2014]

In this subsection, we prove Lemma 3 by following the line of arguments in
Babaioff et al. [2015]. We emphasize that a version of the Lemma has been
proved in Babaioff et al. [2015]. We dervie the Lemma for the purpose of
extracting the values of the constant coefficients. We first extract some
relevant concentration inequalities in the following two Lemmas.

######  Lemma 6 (Theorem 8 in Chung and Lu [2006]).

Suppose $\\{U_{i}\\}^{n}_{i=1}$ are independent random variables satisfying
$U_{i}\leq M$, for $1\leq i\leq n$ almost surely. Let $U=\sum_{i=1}^{n}U_{i}$,
$\|U\|^{2}=\sum_{i=1}^{n}\mathbb{E}[U_{i}^{2}]$. With probability $\geq
1-e^{-x}$, we have

$U-\mathbb{E}[U]\leq\sqrt{2\|U\|^{2}x}+\frac{2x}{3}\max\\{M,0\\}.$

######  Lemma 7 (Theorem 6 in Chung and Lu [2006]).

Suppose $U_{i}$ are independent random variables satisfying
$U_{i}-\mathbb{E}[U_{i}]\leq M$, $M>0$, for $1\leq i\leq n$. Let
$U=\sum_{i=1}^{n}U_{i}$, $\text{Var}(U)=\sum_{i=1}^{n}\text{Var}(U_{i})$, then
with probability $\geq 1-e^{-x}$, we have

$U-\mathbb{E}[U]\leq\sqrt{2\text{Var}(U)x}+\frac{2Mx}{3}.$

Using Lemma 7, we first derive the following Lemma that bounds the empirical
mean:

######  Lemma 8.

Let $\\{X_{i}\\}^{n}_{i=1}$ be independent random variables supported in
$[0,1]$. Let $X=\sum_{i=1}^{n}X_{i}$ and
$\text{Var}(X)=\sum_{i=1}^{n}\text{Var}(X_{i})$. For any fixed $x>0$, With
probability $\geq 1-2e^{-x}$, we have

$\left|X-\mathbb{E}[X]\right|\leq\sqrt{2\text{Var}(X)x}+\frac{2x}{3}.$

###### Proof of Lemma 8.

Apply Lemma 7 with $U_{i}=X_{i}$, $U_{i}=-X_{i}$, respectively, and $M=1$,
then with probability $\geq 1-2e^{-x}$, we have

$\left|X-\mathbb{E}[X]\right|\leq\sqrt{2\text{Var}(X)x}+\frac{2x}{3}.$

∎

Next, we bound the difference between the ground truth variance and its
empirical counterpart using Lemma 6:

######  Lemma 9.

Suppose $X_{i}$ are independent random variables supported in $[0,1]$. Let
$X=\sum_{i=1}^{n}X_{i}$, $\text{Var}(X)=\sum_{i=1}^{n}\text{Var}(X_{i})$,
$V_{n}=\sum_{i=1}^{n}\left(X_{i}-\mathbb{E}[X_{i}]\right)^{2}$then with
probability $\geq 1-3e^{-x}$, we have

$\sqrt{\text{Var}(X)}\leq\sqrt{V_{n}}+2\sqrt{x}.$

###### Proof of Lemma 9.

The proof follows the line of argument in Audibert et al. [2009]. First, we
apply Lemma 6 with $U_{i}=-(X_{i}-\mathbb{E}[X_{i}])^{2}$ and $M=0$. With
probability $\geq 1-e^{-x}$, we have

$\text{Var}(X)\leq
V_{n}+\sqrt{2\left(\sum_{i=1}^{n}\mathbb{E}\left[\left(X_{i}-\mathbb{E}[X_{i}]\right)^{4}\right]\right)x}\leq
V_{n}+\sqrt{2\left(\sum_{i=1}^{n}\mathbb{E}\left[\left(X_{i}-\mathbb{E}[X_{i}]\right)^{2}\right]\right)x}=V_{n}+\sqrt{2\text{Var}(X)x}.$
(42)

Since $X_{i}\in[0,1]$ almost surely for all $i\in[n]$, we have

$\text{Var}(X_{i})=\mathbb{E}[X_{i}^{2}]-\mathbb{E}[X_{i}]^{2}\leq\mathbb{E}[X_{i}]-\mathbb{E}[X_{i}]^{2}\leq\frac{1}{4}.$

Now, observe that

$\text{Var}(X)=\sum_{i=1}\text{Var}(X_{i})\leq\sum_{i=1}^{n}\frac{1}{4}=\frac{n}{4}\quad\Rightarrow\sqrt{\text{Var}(X)}\leq\frac{\sqrt{n}}{2}.$

If $2\sqrt{x}\geq\frac{\sqrt{n}}{2}$, then the Lemma evidently holds.
Otherwise, we assume $2\sqrt{x}\leq\frac{\sqrt{n}}{2}$, which is equivalent to
$x\leq\frac{n}{16}$. Combining Lemma 8 and (42), with probability $\geq
1-3e^{-x}$, we have,

$\displaystyle\text{Var}(X)$ $\displaystyle\leq
V_{n}+\sqrt{2\text{Var}(X)x}+\frac{\left(X-\mathbb{E}[X]\right)^{2}}{n}$
$\displaystyle\leq
V_{n}+\sqrt{2\text{Var}(X)x}+\frac{1}{n}\left(2\text{Var}(X)x+\frac{4}{3}x\sqrt{2\text{Var}(X)x}+\frac{4x^{2}}{9}\right)$
$\displaystyle\leq
V_{n}+\sqrt{2\text{Var}(X)x}+\frac{1}{n}\left(2\sqrt{\text{Var}(X)x}\cdot\frac{\sqrt{n}}{2}\frac{\sqrt{n}}{4}+\frac{4}{3}\sqrt{2\text{Var}(X)x}\cdot\frac{n}{16}+\frac{4x}{9}\cdot\frac{n}{16}\right)$
$\displaystyle=\sqrt{\text{Var}(X)x}\left(\frac{13}{12}\sqrt{2}+\frac{1}{4}\right)+\left(V_{n}+\frac{x}{36}\right).$

Consequently, we can derive an upper bound for $\sqrt{\text{Var}(X)}$:

$\sqrt{\text{Var}(X)}\leq\frac{\sqrt{x}}{2}\left(\frac{13}{12}\sqrt{2}+\frac{1}{4}\right)+\frac{1}{2}\sqrt{x\left(\frac{13}{12}\sqrt{2}+\frac{1}{4}\right)^{2}+4\left(V_{n}+\frac{x}{36}\right)}\leq\sqrt{V_{n}}+2\sqrt{x},$

which proves the Lemma. ∎

######  Lemma 10.

Suppose $X_{i}$ are independent random variables supported in $[0,1]$. Let
$X=\sum_{i=1}^{n}X_{i}$, then with probability $\geq 1-3e^{-x}$, we have

$\left|X-\mathbb{E}[X]\right|\leq\sqrt{2Xx}+4x.$

###### Proof of Lemma 10.

Apply Lemma 8 and Lemma 9, we directly derive that with probability $\geq
1-3e^{-x}$

$\left|X-\mathbb{E}[X]\right|\leq\sqrt{2\text{Var}(X)x}+\frac{2x}{3}\leq\sqrt{2V_{n}x}+\left(2\sqrt{2}+\frac{2}{3}\right)x<\sqrt{2V_{n}x}+4x\leq\sqrt{2Xx}+4x,$

where the last inequality comes from the fact that for random variable whose
support is $[0,1]$, then its variance is always smaller than its mean. ∎

######  Lemma 11 (Theorem 1.1 in Dubhashi and Panconesi [2009]).

Suppose $X_{i}$ are independent random variables supported in $[0,1]$. Let
$X=\sum_{i=1}^{n}X_{i}$, then for any $R>2e\mathbb{E}[X]$, we have

$\mathbb{P}(X>R)\leq 2^{-R}.$

Now we turn back to the proof of Lemma 3. Denote $\delta=e^{-x}$. Apply Lemma
10 then with probability $\geq 1-3\delta$, we have,

$N\left|\hat{V}-\mathbb{E}\left[\hat{V}\right]\right|\leq\sqrt{2N\hat{V}\log\left(\frac{1}{\delta}\right)}+4\log\left(\frac{1}{\delta}\right),$

which is equivalent to ,

$\left|\hat{V}-\mathbb{E}\left[\hat{V}\right]\right|\leq\text{rad}\left(\hat{V},N,\delta\right).$
(43)

Besides,

$\displaystyle\mathbb{P}\left(\text{rad}\left(\hat{V},N,\delta\right)>3\text{rad}\left(\mathbb{E}\left[\hat{V}\right],N,\delta\right)\right)$
$\displaystyle\leq\mathbb{P}\left(\hat{V}>9\mathbb{E}\left[\hat{V}\right]+32\log\left(\frac{1}{\delta}\right)\right)$
(44) $\displaystyle\leq
2^{-9\mathbb{E}\left[\hat{V}\right]-32\log\left(\frac{1}{\delta}\right)}$
$\displaystyle\leq\delta.$

Therefore, combining (43) and (44), the lemma holds.

###  D.2 Proof for Lemma 4

By Lemma 3, with probability $\geq 1-3KT\delta$, we have

$|r(a)-\hat{R}_{t}(a)|\leq\text{rad}(\hat{R}_{t}(a),N_{t-1}^{+}(a),\delta).$

Hence with probability $\geq 1-3KT\delta$,

$\begin{cases}r(a)\leq\hat{R}_{t}(a)+\text{rad}(\hat{R}_{t}(a),N_{t-1}^{+}(a),\delta)\\\
r(a)\leq 1\end{cases}\qquad\Rightarrow\qquad\begin{aligned}
r(a)&\leq\min\left\\{\hat{R}_{t}(a)+\text{rad}(\hat{R}_{t}(a),N_{t-1}^{+}(a),\delta),1\right\\}\\\
&=\text{UCB}_{r,t}(a).\end{aligned}$

Similarly, with probability $\geq 1-3KTd\delta$,

$\textbf{LCB}_{c,t}(a)\preceq\boldsymbol{c}(a).$

###  D.3 Proof for Inequalities 14, 15

We first provide the two lemmas:

######  Lemma 12 (Theorem 1.6 in Freedman [1975]).

Suppose $\\{U_{i}\\}_{i=1}^{n}$ is a martingale difference sequence supported
in $[0,1]$ with respect to the filtration $\\{{\cal F}_{i}\\}^{n}_{i=1}$. Let
$U=\sum_{i=1}^{n}U_{i}$, and $V=\sum_{i=1}^{n}\text{Var}(U_{i}|{\cal
F}_{i-1})$. Then for any $a>0$, $b>0$, we have

$\mathbb{P}\left(|U|\geq a,V\leq b\right)\leq 2e^{-\frac{a^{2}}{2(a+b)}}.$

######  Lemma 13.

Suppose $\\{X_{i}\\}_{i=1}^{n}$ are random variables supported in $[0,1]$,
where $X_{i}$ is ${\cal F}_{i}$-measurable and $\\{{\cal F}_{i}\\}^{n}_{i=1}$
is a filtration. Let $M_{i}=\mathbb{E}[X_{i}|{\cal F}_{i-1}]$ for each
$i\in\\{1,\ldots,n\\}$, and $M=\sum_{i=1}^{n}M_{i}$. Then with probability
$\geq 1-2n\delta$, we have

$\left|\sum_{i=1}^{n}(X_{i}-M_{i})\right|\leq
O\left(\sqrt{M\log\left(\frac{1}{\delta}\right)}+\log\left(\frac{1}{\delta}\right)\right).$

###### Proof of Lemma 13.

The proof follows the line of Theorem 4.10 in Babaioff et al. [2015]. Let
$U_{i}=X_{i}-M_{i}$ for each $i\in\\{1,\ldots,n\\}$. Clearly,
$\\{U_{i}\\}_{i=1}^{n}$ is a martingale difference sequence with respect to
the filtration $\\{{\cal F}_{i}\\}^{n}_{i=1}$. Since

$\text{Var}(U_{i}|\mathcal{F}_{i-1})=\text{Var}(X_{i}|\mathcal{F}_{i-1})=\mathbb{E}[X_{i}^{2}|\mathcal{F}_{i-1}]-\mathbb{E}[X_{i}|\mathcal{F}_{i-1}]^{2}\leq\mathbb{E}[X_{i}|\mathcal{F}_{i-1}]=M_{i}\text{
almost surely},$

we have
$V=\sum_{i=1}^{n}\text{Var}(U_{i}|\mathcal{F}_{i-1})\leq\sum_{i=1}^{n}M_{i}=M$
almost surely. Apply Lemma 12 with
$a=\sqrt{2b\log\left(\frac{1}{\delta}\right)}+2\log\left(\frac{1}{\delta}\right)$
for any $b\geq 1$, it follows that with probability $\leq 2\delta$,

$|U|=\left|\sum_{i=1}^{n}U_{i}\right|\geq
O\left(\sqrt{b\log\left(\frac{1}{\delta}\right)}+\log\left(\frac{1}{\delta}\right)\right)\quad\&\quad
V\leq b,$

Take the union bound over all integer $b$ from $1$ to $n$, noting that $V\leq
M$ and $b-1\leq M\leq b$ for some $b\in\\{1,\ldots,n\\}$ almost surely, with
probability $\geq 1-2n\delta$ we have

$\left|\sum_{i=1}^{n}(X_{i}-M_{i})\right|\leq
O\left(\sqrt{M\log\left(\frac{1}{\delta}\right)}+\log\left(\frac{1}{\delta}\right)\right).$

Altogether, the lemma holds.

∎

Now, we paraphrase inequalities 14, 15 as Lemmas 14, 15, and provide their
proofs.

######  Lemma 14.

With probability $\geq 1-3KT\delta$, we have

$\left|\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{r,t}(A_{t})-\sum_{t=1}^{\tau-1}q_{t}R_{t}\right|\leq
O\left(\log\left(\frac{1}{\delta}\right)\left(\sqrt{\overline{q}K\sum_{t=1}^{\tau-1}q_{t}R_{t}}+\overline{q}K\log\left(\frac{T}{K}\right)\right)\right).$

######  Lemma 15.

With probability $\geq 1-3KTd\delta$, we have

$\left|\sum_{t=1}^{\tau-1}q_{t}\text{LCB}_{c,t}(A_{t},i)-\sum_{t=1}^{\tau-1}q_{t}C_{t,i}\right|\leq
O\left(\log\left(\frac{1}{\delta}\right)\left(\sqrt{\overline{q}KB}+\overline{q}K\log\left(\frac{T}{K}\right)\right)\right),\quad\forall
i\in[d].$

###### Proof of Lemma 14.

First with probability $\geq 1-2T\delta$, we have

$\displaystyle\left|\sum_{t=1}^{\tau-1}q_{t}r(A_{t})-\sum_{t=1}^{\tau-1}q_{t}R_{t}\right|$
$\displaystyle=\overline{q}\left|\sum_{t=1}^{\tau-1}\frac{q_{t}}{\overline{q}}(r(A_{t})-R_{t})\right|$
(45a) $\displaystyle\leq
O\left(\sqrt{\overline{q}\log\left(\frac{1}{\delta}\right)\sum_{t=1}^{\tau-1}q_{t}r(A_{t})}+\overline{q}\log\left(\frac{1}{\delta}\right)\right)$
(45b) $\displaystyle\leq
O\left(\sqrt{\overline{q}\log\left(\frac{1}{\delta}\right)\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{r,t}(A_{t})}+\overline{q}\log\left(\frac{1}{\delta}\right)\right),$
(45c)

where (45c) comes from Lemma 4. Inequality (45b) comes from Lemma 13, where we
apply $X_{t}=\frac{q_{t}R_{t}}{\overline{q}}$ and ${\cal
F}_{t-1}=\sigma(\\{A_{s},q_{s},R_{s},\\{C_{s,i}\\}^{d}_{i=1},\hat{Q}_{s}\\}^{t-1}_{s=1}\cup\\{q_{t}\\})$.
Then with probability $\geq 1-3KT\delta$, we also have

$\displaystyle\left|\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{r,t}(A_{t})-\sum_{t=1}^{\tau-1}q_{t}r(A_{t})\right|$
$\displaystyle\leq
6\sum_{t=1}^{\tau-1}q_{t}\text{rad}(r(A_{t}),N_{t-1}^{+}(A_{t}),\delta)$ (46a)
$\displaystyle\leq
6\sum_{a\in\mathcal{A}:N_{\tau-1}(a)>0}\sum_{n=1}^{N_{\tau-1}(a)}q_{n}(a)\text{rad}\left(r(a),n,\delta\right)$
(46b)
$\displaystyle=6\overline{q}\sum_{a\in\mathcal{A}:N_{\tau-1}(a)>0}\sum_{n=1}^{N_{\tau-1}(a)}\frac{q_{n}(a)}{\overline{q}}\left(\sqrt{\frac{2r(a)\log\left(\frac{1}{\delta}\right)}{n}}+\frac{4}{n}\log\left(\frac{1}{\delta}\right)\right)$
(46c) $\displaystyle\leq
6\overline{q}\sum_{a\in\mathcal{A}:N_{\tau-1}(a)>0}\left(2\sqrt{2r(a)\frac{Q_{\tau-1}(a)}{\overline{q}}\log\left(\frac{1}{\delta}\right)}+4\left(1+\log(N_{\tau-1}(a))\right)\log\left(\frac{1}{\delta}\right)\right)$
(46d) $\displaystyle\leq
12\left(\sqrt{2\overline{q}K\log\left(\frac{1}{\delta}\right)\sum_{a\in\mathcal{A}}r(a)Q_{\tau-1}(a)}+2\overline{q}K\log\left(\frac{T}{K}\right)\log\left(\frac{1}{\delta}\right)+2\overline{q}K\log\left(\frac{1}{\delta}\right)\right)$
(46e)
$\displaystyle=12\left(\sqrt{2\overline{q}K\log\left(\frac{1}{\delta}\right)\sum_{t=1}^{\tau-1}q_{t}r(A_{t})}+2\overline{q}K\log\left(\frac{T}{K}\right)\log\left(\frac{1}{\delta}\right)+2\overline{q}K\log\left(\frac{1}{\delta}\right)\right)$
(46f) $\displaystyle\leq
12\left(\sqrt{2\overline{q}K\log\left(\frac{1}{\delta}\right)\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{r,t}(A_{t})}+2\overline{q}K\log\left(\frac{T}{K}\right)\log\left(\frac{1}{\delta}\right)+2\overline{q}K\log\left(\frac{1}{\delta}\right)\right),$
(46g)

where

  * •

(46a) comes from the following, with probability $\geq 1-3KT\delta$,

$\displaystyle\left|\text{UCB}_{r,t}(A_{t})-r(A_{t})\right|$
$\displaystyle\leq\left|\hat{R}_{t-1}(A_{t})-r(A_{t})\right|+\text{rad}(\hat{R}_{t-1}(A_{t}),N_{t-1}^{+}(A_{t}),\delta)$
$\displaystyle\leq 2\text{rad}(\hat{R}_{t-1}(A_{t}),N_{t-1}(A_{t}),\delta)$
$\displaystyle\leq 6\text{rad}(r(A_{t}),N_{t-1}(A_{t}),\delta).$

  * •

(46b) comes from rearranging the sum. $q_{n}(a)$ means the $n$-th adversarial
term that the algorithm selects $a$.

  * •

(46c) comes from the definition of $\text{rad}(\cdot,\cdot,\cdot)$.

  * •

(46d) comes from the following

$\sum_{i=1}^{n}\frac{w_{i}}{\sqrt{i}}=\sum_{i=1}^{n}\frac{2w_{i}}{2\sqrt{i}}\leq\sum_{i=1}^{n}\frac{2w_{i}}{\sqrt{\sum_{j=1}^{i}w_{j}}+\sqrt{\sum_{j=1}^{i-1}w_{j}}}=\sum_{i=1}^{n}2\left(\sqrt{\sum_{j=1}^{i}w_{j}}-\sqrt{\sum_{j=1}^{i-1}w_{j}}\right)=2\sqrt{\sum_{i=1}^{n}w_{i}},$

and

$\sum_{i=1}^{n}\frac{w_{i}}{i}\leq\sum_{i=1}^{n}\frac{1}{i}\leq(1+\log(n)).$

where $w_{i}\in(0,1]$.

  * •

In (46d) and (46e) $Q_{t}(a)=\sum_{s\in[t],A_{s}=a}q_{s}$.

  * •

(46e) comes from Jansen inequality.

Combine (45) and (46), we have

$\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{r,t}(A_{t})\leq\sum_{t=1}^{\tau-1}q_{t}r_{t}+O\left(\sqrt{\overline{q}K\log\left(\frac{1}{\delta}\right)\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{r,t}(A_{t})}+\overline{q}K\log\left(\frac{T}{K}\right)\log\left(\frac{1}{\delta}\right)+\overline{q}K\log\left(\frac{1}{\delta}\right)\right),$

which is equivalent to

$\left(\sqrt{\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{r,t}(A_{t})}-O\left(\sqrt{\overline{q}K\log\left(\frac{1}{\delta}\right)}\right)\right)^{2}\leq\sum_{t=1}^{\tau-1}q_{t}r_{t}+O\left(\overline{q}K\log\left(\frac{T}{K}\right)\log\left(\frac{1}{\delta}\right)+\overline{q}K\log\left(\frac{1}{\delta}\right)\right),$

Hence,

$\displaystyle\sqrt{\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{r,t}(A_{t})}$
$\displaystyle\leq
O\left(\sqrt{\overline{q}K\log\left(\frac{1}{\delta}\right)}\right)+\sqrt{\sum_{t=1}^{\tau-1}q_{t}r_{t}+O\left(\overline{q}K\log\left(\frac{T}{K}\right)\log\left(\frac{1}{\delta}\right)+\overline{q}K\log\left(\frac{1}{\delta}\right)\right)}$
(47)
$\displaystyle\leq\sqrt{\sum_{t=1}^{\tau-1}q_{t}r_{t}}+O\left(\sqrt{\overline{q}K\log\left(\frac{T}{K}\right)\log\left(\frac{1}{\delta}\right)}+\sqrt{\overline{q}K\log\left(\frac{1}{\delta}\right)}\right).$

Combine (45) and (46), (47), we finish the proof. ∎

###### Proof of Lemma 15.

The proof is quite similar to Lemma 14, so we omit the descriptive details.
Similarly, with probability $\geq 1-2Td\delta$, we have

$\displaystyle\left|\sum_{t=1}^{\tau-1}q_{t}c(A_{t},i)-\sum_{t=1}^{\tau-1}q_{t}C_{t,i}\right|$
$\displaystyle=\overline{q}\left|\sum_{t=1}^{\tau-1}\frac{q_{t}}{\overline{q}}(c(A_{t})-C_{t,i})\right|$
(48) $\displaystyle\leq
O\left(\sqrt{\overline{q}\log\left(\frac{1}{\delta}\right)\sum_{t=1}^{\tau-1}q_{t}c(A_{t},i)}+\overline{q}\log\left(\frac{1}{\delta}\right)\right)$
$\displaystyle\leq
O\left(\sqrt{\overline{q}\log\left(\frac{1}{\delta}\right)\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{c,t}(A_{t},i)}+\overline{q}\log\left(\frac{1}{\delta}\right)\right),$

Then with probability $\geq 1-3KTd\delta$, we also have

$\begin{aligned}
\left|\sum_{t=1}^{\tau-1}q_{t}\text{LCB}_{c,t}(A_{t},i)-\sum_{t=1}^{\tau-1}q_{t}c(A_{t},i)\right|&\leq
6\sum_{t=1}^{\tau-1}q_{t}\text{rad}(c(A_{t},i),N_{t-1}^{+}(A_{t}),\delta)\\\
&\leq
6\sum_{a\in\mathcal{A}:N_{\tau-1}(a)>0}\sum_{n=1}^{N_{\tau-1}(a)}q_{n}(a)\text{rad}\left(c(a,i),n,\delta\right)\\\
&=6\overline{q}\sum_{a\in\mathcal{A}:N_{\tau-1}(a)>0}\sum_{n=1}^{N_{\tau-1}(a)}\frac{q_{n}(a)}{\overline{q}}\left(\sqrt{\frac{2c(a,i)\log\left(\frac{1}{\delta}\right)}{n}}+\frac{4}{n}\log\left(\frac{1}{\delta}\right)\right)\\\
&\leq
6\overline{q}\sum_{a\in\mathcal{A}:N_{\tau-1}(a)>0}\left(2\sqrt{2c(a,i)\frac{Q_{\tau-1}(a)}{\overline{q}}\log\left(\frac{1}{\delta}\right)}+4\left(1+\log(N_{\tau-1}(a))\right)\log\left(\frac{1}{\delta}\right)\right)\\\
&\leq
12\left(\sqrt{2\overline{q}K\log\left(\frac{1}{\delta}\right)\sum_{a\in\mathcal{A}}c(a,i)Q_{\tau-1}(a)}+2\overline{q}K\log\left(\frac{T}{K}\right)\log\left(\frac{1}{\delta}\right)+2\overline{q}K\log\left(\frac{1}{\delta}\right)\right)\\\
&\leq
12\left(\sqrt{2\overline{q}K\log\left(\frac{1}{\delta}\right)\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{c,t}(A_{t},i)}+2\overline{q}K\log\left(\frac{T}{K}\right)\log\left(\frac{1}{\delta}\right)+2\overline{q}K\log\left(\frac{1}{\delta}\right)\right).\\\
\end{aligned}$

(49)

Similarly,

$\begin{aligned}
\left|\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{c,t}(A_{t},i)-\sum_{t=1}^{\tau-1}q_{t}c(A_{t},i)\right|&\leq
6\sum_{t=1}^{\tau-1}q_{t}\text{rad}(c(A_{t},i),N_{t-1}^{+}(A_{t}),\delta)\\\
&\leq
O\left(\sqrt{\overline{q}K\log\left(\frac{1}{\delta}\right)\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{c,t}(A_{t},i)}+\overline{q}K\log\left(\frac{T}{K}\right)\log\left(\frac{1}{\delta}\right)+\overline{q}K\log\left(\frac{1}{\delta}\right)\right).\end{aligned}$

(50)

Combine (48) and (50), we have

$\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{c,t}(A_{t},i)\leq\sum_{t=1}^{\tau-1}q_{t}C_{t,i}+O\left(\sqrt{\overline{q}K\log\left(\frac{1}{\delta}\right)\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{c,t}(A_{t},i)}+\overline{q}K\log\left(\frac{T}{K}\right)\log\left(\frac{1}{\delta}\right)+\overline{q}K\log\left(\frac{1}{\delta}\right)\right),$

which is equivalent to

$\left(\sqrt{\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{c,t}(A_{t},i)}-O\left(\sqrt{\overline{q}K\log\left(\frac{1}{\delta}\right)}\right)\right)^{2}\leq\sum_{t=1}^{\tau-1}q_{t}C_{t,i}+O\left(\overline{q}K\log\left(\frac{T}{K}\right)\log\left(\frac{1}{\delta}\right)+\overline{q}K\log\left(\frac{1}{\delta}\right)\right),$

Hence,

$\displaystyle\sqrt{\sum_{t=1}^{\tau-1}q_{t}\text{UCB}_{c,t}(A_{t},i)}$
$\displaystyle\leq
O\left(\sqrt{\overline{q}K\log\left(\frac{1}{\delta}\right)}\right)+\sqrt{\sum_{t=1}^{\tau-1}q_{t}C_{t,i}+O\left(\overline{q}K\log\left(\frac{T}{K}\right)\log\left(\frac{1}{\delta}\right)+\overline{q}K\log\left(\frac{1}{\delta}\right)\right)}$
(51)
$\displaystyle\leq\sqrt{\sum_{t=1}^{\tau-1}q_{t}C_{t,i}}+O\left(\sqrt{\overline{q}K\log\left(\frac{T}{K}\right)\log\left(\frac{1}{\delta}\right)}+\sqrt{\overline{q}K\log\left(\frac{1}{\delta}\right)}\right)$
$\displaystyle\leq\sqrt{B}+O\left(\sqrt{\overline{q}K\log\left(\frac{T}{K}\right)\log\left(\frac{1}{\delta}\right)}+\sqrt{\overline{q}K\log\left(\frac{1}{\delta}\right)}\right),$

where the last inequality comes from the definition of the stopping time
$\tau$. Combine (48) and (49), (51), we finish the proof. ∎