# A Lyapunov-Based Methodology for Constrained
Optimization with Bandit Feedback

Semih Cayci,1Yilin Zheng,2Atilla Eryilmaz2

###### Abstract

In a wide variety of applications including online advertising, contractual
hiring, and wireless scheduling, the controller is constrained by a stringent
budget constraint on the available resources, which are consumed in a random
amount by each action, and a stochastic feasibility constraint that may impose
important operational limitations on decision-making. In this work, we
consider a general model to address such problems, where each action returns a
random reward, cost, and penalty from an unknown joint distribution, and the
decision-maker aims to maximize the total reward under a budget constraint $B$
on the total cost and a stochastic constraint on the time-average penalty. We
propose a novel low-complexity algorithm based on Lyapunov optimization
methodology, named ${\tt LyOn}$, and prove that for $K$ arms it achieves
$O(\sqrt{{\color[rgb]{0,0,0}K}B\log B})$ regret and zero constraint-violation
when $B$ is sufficiently large. The low computational cost and sharp
performance bounds of ${\tt LyOn}$ suggest that Lyapunov-based algorithm
design methodology can be effective in solving constrained bandit optimization
problems.

##  1 Introduction

Multi-armed bandits (MAB) have been predominantly used to model exploration-
and-exploitation problems since its inception (Robbins 1952; Lai and Robbins
1985; Berry and Fristedt 1985). As a consequence of the universality of the
dilemma, bandit algorithms have found a broad range of applications from
medical trials and adaptive routing to server allocation (Bubeck, Cesa-Bianchi
et al. 2012). In many applications of interest, the controller is required to
satisfy multiple constraints while achieving the optimal expected total reward
under a given finite budget.

To take one example, in fair resource allocation problems, such as task
scheduling or contractual hiring, each arm (e.g., a user or a social group)
must receive at least a given fraction of the total budget (e.g., total time)
while maximizing the total reward. Other examples from diverse domains, such
as wireless resource allocation, online advertising, etc., also take this form
(see Section 2 for more discussion). In order to solve fundamental learning
applications such as these, a fast and effective constrained bandit
optimization framework is required.

This motivates us in this paper to formulate and solve the following budget-
constrained bandit problem in a stochastic setting. Each arm pull takes a
random and arm-dependent resource (e.g. time, energy, etc.) from the budget,
and the decision-making process continues until the total consumed resource
exceeds a given budget $B>0$. At the end of each arm pull, the controller
receives a random reward and a random penalty. The objective of the controller
is to maximize the expected total reward subject to an inequality constraint
on the average penalty per unit resource consumption.

###  1.1 Main Contributions

In this work, we tackle the aforementioned general constrained optimization
problem with bandit feedback, and propose a novel Lyapunov-based design
methodology to develop efficient algorithms that achieve sharp convergence
results. Our main contributions can be summarized as follows:

  * •

General model: We consider a generic constrained bandit optimization problem
(in Section 2), which: (i) incorporates random costs for each action; (ii) is
subject to a stringent budget (knapsack) constraint; and (iii) has stochastic
feasibility constraints as required by many applications.

  * •

Lyapunov methodology for bandit optimization: Based on a Lyapunov-drift
minimization technique from stochastic control, we design novel low-complexity
bandit algorithms with provably sharp convergence properties. This approach
suggests a general design methodology (outlined in Section 3) that can be
utilized in other constrained bandit optimization scenarios.

  * •

Analysis techniques: We also employ new analysis techniques (in Section 5) for
the reward maximization problem subject to stochastic and knapsack constraints
based on a combination of renewal theory, stochastic control, and bandit
optimization.

###  1.2 Related Work

Knapsack-constrained bandit problem was considered in (Badanidiyuru,
Kleinberg, and Slivkins 2013), where the objective of the controller is to
maximize the expected total reward under a stringent budget constraint. The
authors proposed a learning algorithm with $O(\sqrt{B})$ problem-independent
regret. Bandit algorithms with $O(\log(B))$ problem-dependent regret bounds
were proposed under various extensions of the knapsack-constrained bandit
models (Tran-Thanh et al. 2012; Flajolet and Jaillet 2015; Xia et al. 2015,
2016; Cayci, Eryilmaz, and Srikant 2019, 2020). These works differ from ours
in that, while the controller is constrained by stringent knapsack
constraints, stochastic feasibility constraints are not accommodated.

As an extension of (Badanidiyuru, Kleinberg, and Slivkins 2013), finite-armed
bandit problem with stochastic feasibility constraints was considered in
(Agrawal and Devanur 2014), and a UCB-type algorithm with $O(\sqrt{B})$ regret
and $O(1/\sqrt{B})$ constraint-violation was proposed. This setting was
extended to episodic Markov decision processes in (Qiu et al. 2020), and
similar order results for regret and constraint-violation were obtained. In
these models, each action incurs a unit cost. Furthermore, the proposed
algorithms in (Agrawal and Devanur 2014) require solving a convex optimization
/ linear programming problem at each stage. Our model accommodates random
cost, which is subject to a knapsack constraint, in addition to the stochastic
feasibility constraint. Based on Lyapunov optimization theory, we develop
computationally-efficient iterative algorithms .

Lyapunov optimization methods have been widely used in stochastic network
optimization and queueing systems (see (Neely 2012, 2010; Georgiadis, Neely,
and Tassiulas 2006) and references therein). This methodology was later used
in convex optimization problems (Yu and Neely 2020) with known gradients. In
these approaches, a predominant assumption is that the random system state is
known to the controller prior to its decision, therefore the existing methods
do not work for online learning setting where the controller does not have the
system state or the system statistics before making a decision.

Lyapunov optimization methods were first used in the context of online
learning in (Cayci, Gupta, and Eryilmaz 2020), where the goal of the
controller is to maximize the total utility as a function of each arm’s time-
average reward subject to a knapsack constraint under delayed experts
feedback. Our work extends (Cayci, Gupta, and Eryilmaz 2020) in that we
consider bandit feedback and also incorporate stochastic feasibility
constraints in this paper. Some recent works (Liu et al. 2020, 2021), which
utilized Lyapunov-drift methods for online learning, studied the online-
dispatching and linear bandits with cumulative constraints. Our work
substantially differs from these works in that we incorporate knapsack budget
constraints and random costs per arm selection.

##  2 Constrained Reward Maximization Problem with Bandit Feedback

We consider a finite-armed bandit problem with $K>1$ arms, and the set of arms
denoted by $\mathbb{K}=\\{1,2,\ldots,K\\}$. If arm $k$ is chosen at $n^{th}$
epoch, it incurs a cost of $X_{n,k}$, yields a reward of $R_{n,k}$, and
returns a penalty of $Y_{n,k}$, where the outcome of the joint random vector
$(X_{n,k},R_{n,k},{Y}_{n,k})$ is learned via bandit feedback at the end of
each arm decision. We assume that the random process
$\\{(X_{n,k},R_{n,k},Y_{n,k}):n\geq 1\\}$ is independent and identically
distributed over $n$, and independent across different arms for all
$k\in\mathbb{K}$. For simplicity, we assume that
$X_{n,k},R_{n,k},Y_{n,k}\in[0,1]$ for all $n,k$, which can be easily extended
to general sub-Gaussian random variables by using the same techniques used in
this paper. The controller has a total budget $B>0$ at the beginning of the
process, and tries to maximize the expected cumulative reward under time-
average constraints on the penalties by sampling the arms wisely under this
budget constraint.

Note that stochastic constraints and budget constraints imply completely
different system dynamics. Violation of a budget constraint immediately stops
the decision-making process. On the other hand, the stochastic constraints are
aimed to be satisfied asymptotically, while instantaneous violations do not
stop the decision-making process.

First, we introduce the causal policy space.

######  Definition 1 (Causal Policy).

Let $\pi$ be a policy that yields a sequence of arm pulls
$\\{I_{n}^{\pi}\in\mathbb{K}:n\geq 1\\}$. Under $\pi$, the history until epoch
$n$ is the following filtration:

$\mathcal{F}_{n}^{\pi}=\sigma(\\{(I_{j}^{\pi},X_{j,k},R_{j,k},{Y}_{j,k}):I_{j}^{\pi}=k,1\leq
j\leq n\\}),$ (1)

where $\sigma(Z)$ denotes the sigma-field of a random variable $Z$. We call an
algorithm $\pi$ causal if $\pi$ is non-anticipating, i.e.,
$\\{I_{n}^{\pi}=k\\}\in\mathcal{F}_{n-1}^{\pi}$ for all $k,n$.

The set of all causal policies is denoted as $\Pi$. We denote the variables at
epoch $n$ under policy $\pi$ as $X_{n}^{\pi}=X_{n,I_{n}^{\pi}}$,
$R_{n}^{\pi}=R_{n,I_{n}^{\pi}}$ and $Y_{n}^{\pi}=Y_{n,I_{n}^{\pi}}$. The total
cost incurred in $n$ epochs under an causal policy $\pi\in\Pi$ is a controlled
random walk which is defined as $S_{n}^{\pi}=\sum_{i=1}^{n}X_{i}^{\pi}.$ The
decision process under a policy $\pi$ continues until the budget $B$ is
depleted. We assume that the reward corresponding to the final epoch during
which the budget is depleted is gathered by the controller. Thus, the total
number of pulls under $\pi$ is a random variable that is defined as follows:

$N^{\pi}(B)=\inf\Big{\\{}n\geq 1:S_{n}^{\pi}>B\Big{\\}}.$ (2)

Note that the total number of pulls $N^{\pi}(B)$ is a stopping time adapted to
the filtration $\\{(\mathcal{F}_{n}^{\pi}):n\geq 0\\}$. Accordingly, the
cumulative reward under a policy $\pi$ can be written as follows:

${\tt REW}^{\pi}(B)=\sum_{n=1}^{N^{\pi}(B)}R_{n}^{\pi}.$ (3)

Then, we can write the generic problem formulation considered in this paper as
follows:

$\displaystyle\sup_{\pi\in\Pi}$ $\displaystyle\quad\mathbb{E}[{\tt
REW}^{\pi}(B)],$ subject to:
$\displaystyle\quad\mathbb{E}\Bigg{[}\frac{1}{B}\sum_{n=1}^{N^{\pi}(B)}Y_{n}^{\pi}\Bigg{]}\leq
c.$ (4)

######  Definition 2 ((Pseudo) Regret and constraint-violation).

Let ${\pi_{\tt Opt}}$ be the solution of (4) and ${\tt OPT}(B)=\mathbb{E}[{\tt
REW}^{{\pi_{\tt Opt}}}(B)]$. For any causal policy $\pi\in\Pi$ and a budget
$B>0$ level, the (pseudo) regret, ${\tt REG}^{\pi}(B),$ and constraint-
violation, $D^{\pi}(B)$, are defined as follows:

$\displaystyle{\tt REG}^{\pi}(B)={\tt OPT}(B)-\mathbb{E}[{\tt REW}^{\pi}(B)],$
(5) $\displaystyle
D^{\pi}(B)=\mathbb{E}\Bigg{[}\frac{1}{B}\sum_{n=1}^{N^{\pi}(B)}Y_{n}^{\pi}\Bigg{]}-c.$
(6)

The objective of this paper is to design low-complexity bandit algorithms that
are guaranteed to give a low regret and a vanishing constraint-violation level
that decays rapidly with the budget level $B$, in the absence of any
statistical knowledge on the costs, rewards, and penalties. The generic
problem (4) has numerous applications in communications, control, operations
research and management, whereby optimal decision-making under data scarcity
and uncertainty is common. Next, we provide a detailed application in wireless
scheduling in next generation networks, and refer the reader to Appendix A for
other example applications for contractual hiring, and online advertising.

#### Application to Next Generation Wireless Scheduling with Quality-of-
Service Guarantees:

Next-generation wireless technologies are required to serve a highly dynamic
population of users with stringent quality-of-service (QoS) guarantees (such
as low delay (Khalek, Caramanis, and Heath 2014)) over ultra-high frequency
bands with nontraditional statistical and temporal characteristics (Rappaport
et al. 2015). As such, existing estimation and allocation techniques that rely
strongly on persistent users and slowly-changing nature and known statistical
models of channel conditions are no longer suitable for use in this new ultra-
wideband communication paradigm. The controller is required to learn how to
optimize the throughput subject to QoS guarantees by using the ARQ (bandit)
feedback received after each transmission.

This calls for the design of time/energy-constrained point-to-point
communication solutions over $K$ parallel memoryless channels with unknown and
diverse statistical characteristics. In particular, each connection starts
with a total time or energy budget of $B$ units. The transmission of $n^{th}$
packet over the $k^{th}$ channel consumes a random amount of $X_{n,k}$
resource (e.g., transmission time or energy), yields a reward (e.g.,
throughput) $R_{n,k}$ and incurs a penalty $Y_{n,k}$ upon completion of
transmission. In this context, $Y_{n,k}$ is a generic penalty that will be
used in modeling time-average quality-of-service guarantees. As an example,
consider delay-constrained communication, where the arriving packets should be
transmitted in a timely manner. Then, for a given deadline level $d\in[0,1]$,
we let $Y_{n,k}=\mathbb{I}\\{X_{n,k}>d\\}$, which counts the number of packets
that are delayed for more than $d$ time units. For a given time or energy
budget $B$ and a quality-of-service constraint $c$, the optimization problem
(4) leads to throughput maximization subject to a guarantee on the time-
average number of delayed packets. Note that many other QoS criteria, such as
the fraction of dropped packets, can be modeled in a similar manner, which
implies the generality of this approach.

##  3 Outline of the Lyapunov-Based Design Methodology and Main Results

In this work, we develop a low-complexity online algorithm for solving the
generic constrained reward maximization problem (4) by employing a Lyapunov-
drift minimization methodology. Since this methodology may be of independent
value, in this section we provide an outline of its main steps along with an
informal discussion of the key results we obtained under them.

#### (i) Characterization of the Asymptotically-Optimal Stationary Randomized
Oracle:

The optimization problem described in Section 2 is a variant of the unbounded
knapsack problem, and it is known that similar stochastic control problems are
PSPACE-hard (Badanidiyuru, Kleinberg, and Slivkins 2013; Papadimitriou and
Tsitsiklis 1999). In Section 4 we propose a stationary randomized policy
$\pi^{*}$ in Definition 4 that achieves (see Proposition 1) $O(1)$ regret and
$O(1/B)$ constraint-violation gap. This proves that the stationary policy is
asymptotically optimal as the budget $B$ goes to infinity.

Our Lyapunov-based policy design, developed in Section 5, are broken into the
following two steps:

#### (ii) Offline Lyapunov-Drift-Minimizing Policy Design:

We first consider in Section 5.1 the ‘offline’ setting with known reward,
cost, and penalty statistics. There, we introduce a virtual queue
$\\{Q_{n}^{\pi}\\}$ that is updated as:
$Q_{n+1}^{\pi}=\max\\{0,Q_{n}^{\pi}+Y_{n}^{\pi}-(c-\delta)X_{n}^{\pi}\\},$
with a design choice $\delta\in[0,c)$, which keeps track of the constraint-
violation level under policy $\pi$ over decisions $n\geq 1$. Then, under this
queue dynamics, we propose a quadratic Lyapunov drift-minimizing policy
${\pi_{\tt LyOff}}$ in Definition 6 that achieves (cf. Proposition 2)
$O((\delta+1/V)B)$ regret and $O(V/B-\delta)$ constraint-violation gap, where
$V>0$ is a design parameter. With the particular selection of
$V=\Theta(\sqrt{B})$ and $\delta=\Theta(1/\sqrt{B}),$ we can guarantee
$O(\sqrt{B})$ regret and zero constraint-violation for $\pi_{\tt LyOff}$ with
sufficiently large $B$.

#### (iii) Online Lyapunov-Drift-Minimizing Policy Design:

Then, in Section 5.2, we return to the original ‘online’ setting with unknown
statistics, and develop a low-complexity empirical Lyapunov-drift minimizing
policy $\pi_{\tt LyOn}$ that integrates confidence bounds of proposed
empirical estimator with the queueing dynamics from the offline case. Then,
the main result of the paper (cf. Theorem 1) establishes that $\pi_{\tt LyOn}$
achieves $O(\sqrt{{\color[rgb]{0,0,0}K}B\log B}+B(1+\delta\log
B)/V+B\delta+K\log B)$ regret and $O(K\log B/B+V/B-\delta)$ constraint-
violation level. With the particular selection of design parameters as
$V=\Theta(\sqrt{B\log B})$ and $\delta=\Theta(\sqrt{\log B/B}),$ we guarantee
$O(\sqrt{{\color[rgb]{0,0,0}K}B\log B})$ regret and zero constraint-violation
for $\pi_{\tt LyOn}$ with sufficiently large $B$.

The online analysis is especially complicated by the fact that the cumulative
reward and penalty processes form stopped and controlled random walks. To
address the associated challenge, we combine techniques from renewal theory
and Martingale concentration inequalities (Wainwright 2019) to find a high
probability upper bound for $N^{\pi}(B)$. Additionally, for the online policy
with unknown statistics, we carefully integrate empirical concentration
inequalities (Cayci, Eryilmaz, and Srikant 2020) with hitting time analysis
for Martingales (Hajek 1982) as well as Lyapunov drift analysis (Neely 2012)
to bound ${\tt REW}^{\pi}(B)$ and $D^{\pi}(B)$.

##  4 Asymptotically-Optimal Stationary Randomized Oracle Design

As a tractable benchmark, in this section, we consider approximation
algorithms with provably good performance.

######  Definition 3 (Reward Rate and Penalty Rate).

Consider a stationary randomized policy $\pi=\pi(\mathbf{p})$ for a given
probability mass function $\mathbf{p}=(p_{1},p_{2},\ldots,p_{K})$, which takes
action $k$ with probability $p_{k}$ independent from the history. Then, under
$\pi(\mathbf{p})$, the reward rate and penalty rate are defined as:

$r(\mathbf{p})=\frac{\sum_{k\in\mathbb{K}}p_{k}\mathbb{E}[R_{1,k}]}{\sum_{k\in\mathbb{K}}p_{k}\mathbb{E}[X_{1,k}]},\quad
y(\mathbf{p})=\frac{\sum_{k\in\mathbb{K}}p_{k}\mathbb{E}[Y_{1,k}]}{\sum_{k\in\mathbb{K}}p_{k}\mathbb{E}[X_{1,k}]},$
(7)

Intuitively, if an arm is chosen persistently according to the stationary
randomized policy $\pi(\mathbf{p})$ until the budget $B>0$ is depleted, the
cumulative reward becomes $r(\mathbf{p})B+o(B)$ and cumulative penalty becomes
$y(\mathbf{p})B+o(B)$. Moreover, whenever $\mathbb{E}[R_{1,k}^{2}]<\infty$ and
$\mathbb{E}[Y_{1,k}^{2}]<\infty$ (trivially true for bounded random
variables), the additive $o(B)$ term is $O(1)$ in both cases by Lorden’s
inequality (Asmussen 2008).

In the following, we prove that a stationary randomized policy achieves $O(1)$
optimality gap with constraint-violation vanishing at a rate of $O(1/B)$.

######  Definition 4 (Optimal Stationary Randomized Policy, $\pi^{*}$).

Let $\mathbf{p}^{*}$ be the solution to the following optimization problem:

$\max_{\mathbf{p}\in\Delta_{K}}\left\\{r(\mathbf{p}),\quad\textrm{subject
to:}\quad y(\mathbf{p})\leq c\right\\}.$

where $\Delta_{K}$ is the $K$-dimensional probability simplex. The _optimal
stationary randomized policy_ , denoted by $\pi^{*}$, pulls arm $k$ with
probability $p_{k}^{*}$ independently at each epoch until the budget is
depleted: $\mathbb{P}(I_{n}^{\pi^{*}}=k)=p_{k}^{*}$, for all $n\leq
N^{\pi^{*}}(B)$.

The main result of this section is the following proposition, which implies
that $\pi^{*}$ is a good approximation algorithm for ${\pi_{\tt Opt}}$ for
$B>0$.

######  Proposition 1 (Optimality Gap for $\pi^{*}$).

For the optimal static policy $\pi^{*}$ for any given $B>0$, the following
regret and constraint-violation gap results hold:

${\tt REG}^{\pi^{*}}(B)=O(1),\quad D^{\pi^{*}}(B)=O\Big{(}\frac{1}{B}\Big{)}.$
(8)

Therefore, $\pi^{*}$ is asymptotically optimal, i.e. $\lim_{B\to\infty}{\tt
REG}^{\pi^{*}}(B)/B=0$ and $\lim_{B\to\infty}D^{\pi^{*}}(B)=0$.

The proof of Proposition 1 can be found in Appendix C. In the next section, we
will introduce a learning algorithm to achieve the performance of the optimal
stationary randomized policy with low regret and constraint-violation.

##  5 Algorithm Design Based on Empirical Lyapunov Drift Minimization

In the previous section, we proved that the stationary randomized policy
$\pi^{*}$ achieves the optimality in offline setting with small optimality gap
and constraint-violation, which implies it can be used as a benchmark for the
design and analysis of learning algorithms. By using this, we will develop a
dynamic learning algorithm based on the Lyapunov-drift-minimization approach.
For details about this dynamic optimization approach in offline setting, see
(Neely 2010, 2012).We refer to Section 1.2 for the detailed discussion of the
differences from related works in this space.

We make two mild assumptions that are needed for the development and analysis
of our design:

######  Assumption 1 ($\epsilon$-Slater Condition).

There exists an arm $k\in\mathbb{K}$ such that
$\mathbb{E}[Y_{n,k}-cX_{n,k}]\leq-\epsilon$ for some $\epsilon>0$. We only
need $\epsilon$ to be a positive lower-bound  of the actual value.

Assumption 1 is reasonable because for feasibility, either all arms should
satisfy $\mathbb{E}[Y_{n,k}-cX_{n,k}]=0$ for all $k$ or Assumption 1 should
hold, otherwise the constraint can never be satisfied once it is violated.
Since $\mathbb{E}[Y_{n,k}-cX_{n,k}]=0,~{}\forall k\in\mathbb{K}$ is a trivial
case, Assumption 1 is satisfied in almost all applications.

######  Assumption 2 (Bounded Moments).

For all arms $k\in\mathbb{K}$, assume
$\max_{k}\frac{\mathbb{E}[R_{1,k}]}{\mathbb{E}[X_{1,k}]}\leq r_{\tt
max}<\infty$ and $\max_{k}\frac{\mathbb{E}[Y_{1,k}]}{\mathbb{E}[X_{1,k}]}\leq
y_{\tt max}<\infty$. In addition, assume
$\sigma^{2}=\max_{k\in\mathbb{K}}\mathbb{E}\big{[}\big{(}Y_{1,k}-cX_{1,k}\big{)}^{2}\big{]}<1,$
and $\min_{k}\mathbb{E}[X_{1,k}]\geq\mu_{\tt min}>0$. We only need $\mu_{\tt
min}$ to be a lower bound and $r_{\tt max}$, $y_{\tt max}$ to be upper bounds
of the actual values.

This assumption is reasonable because otherwise the optimization problem in
(4) would become either trivial or unsolvable. For bounded rewards and penalty
between $[0,1]$, $r_{\tt max}$ and $y_{\tt max}$ can be upper bounded by
$1/\mu_{\tt min}$.

###  5.1 Offline Lyapunov-Drift Minimizing Policy LyOff Design

First, we consider the Lyapunov optimization methods in the offline setting
with known first-order statistics by closely following (Neely 2012), while
improving the results for finite-time performance by using the drift results
in (Hajek 1982). As a measure of constraint-violation under a causal policy
$\pi\in\Pi$, we define the variables $Q_{n}^{\pi}$ recursively as follows:

$Q_{n+1}^{\pi}=\max\Big{\\{}0,Q_{n}^{\pi}+Y_{n}^{\pi}-(c-\delta)X_{n}^{\pi}\Big{\\}},$
(9)

where $Q_{0}^{\pi}=0$ and $\delta\in[0,c)$ is a fixed parameter that controls
the tightness of the constraint. Note that
$Q_{n+1}^{\pi}\in\mathcal{F}_{n}^{\pi}$ for all $n$ since $\pi$ is causal.
Intuitively, the stability of $\\{Q_{n}^{\pi}\\}_{n}$ implies that the
constraint is satisfied. The key metric for decision-making is the Lyapunov
drift-plus-penalty ratio, which is defined in the following definition.

######  Definition 5 (Lyapunov Drift-plus-Penalty Ratio).

For any given $V>0$, under a causal policy $\pi$, the Lyapunov drift-plus-
penalty ratio is defined as follows:

$\displaystyle\Psi_{n}(Q_{n}^{\pi})$
$\displaystyle=-V\frac{\mathbb{E}[R_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}]}{\mathbb{E}[X_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}]}+Q_{n}^{\pi}\frac{\mathbb{E}[Y_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}]}{\mathbb{E}[X_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}]}.$
(10)

For any stationary randomized policy $\pi(\mathbf{p}_{n}),$ with
$\mathbf{p}_{n}\in\mathcal{F}_{n-1}$, the Lyapunov drift-plus-penalty ratio
becomes:

$\displaystyle\Psi_{n}(Q_{n}^{\pi(\mathbf{p}_{n})})$
$\displaystyle=-V\frac{\sum_{k=1}^{K}p_{n,k}\mathbb{E}[R_{n,k}]}{\sum_{k=1}^{K}p_{n,k}\mathbb{E}[X_{n,k}]}$
$\displaystyle\quad+Q_{n}^{\pi(\mathbf{p}_{n})}\frac{\sum_{k=1}^{K}p_{n,k}\mathbb{E}[Y_{n,k}]}{\sum_{k=1}^{K}p_{n,k}\mathbb{E}[X_{n,k}]}.$
(11)

Intuitively, in the offline setting where all first-order moments are known, a
stationary randomized policy $\pi(\mathbf{p}_{n})$ that minimizes (5.1) over
all probability distributions in every epoch $n$, achieves a near-optimal
trade-off between the cumulative reward and constraint-violation determined by
the parameter $V>0$ (Neely 2012). In the following, we outline this result in
the offline setting, which will guide us in developing the online algorithm in
Section 5.2.

######  Definition 6 (Offline Lyapunov-Drift-Minimizing Distribution).

For any $n$, let $\mathbf{q}_{n}^{*}$ be defined as follows:

$\mathbf{q}_{n}^{*}\in\arg\min_{\mathbf{p}\in\Delta_{K}}~{}\Psi_{n}(Q_{n}^{\pi(\mathbf{p})}).$
(12)

The problem in (12) is an optimization problem over $\Delta_{K}$, the
$K$-dimensional probability simplex, which is computationally complex and can
be solved by using algorithmic techniques in (Neely 2012). However, as it is
shown in Proposition 5 in Appendix D, the optimal solution in our $K$-armed
bandit setting is deterministic given the history $\mathcal{F}_{n-1}$. This
allows us to define the offline Lyapunov-Drift Minimizing Policy ${\pi_{\tt
LyOff}}$ as in Algorithm 1.

_Intuition:_ The policy ${\pi_{\tt LyOff}}$ makes a balanced choice between
the reward maximization and satisfying the constraints. For small $Q_{n}$, the
controller selects the arm $I_{n}$ with the highest drift-plus-penalty ratio
so as to maximize the expected total reward under the budget constraints. If
$Q_{n}$ is large, then it means the constraint has been violated considerably,
thus $I_{n}$ is selected so as to reduce the penalty rate and hence violation
level. Next, we prove finite-time performance bounds for ${\pi_{\tt LyOff}}$.

######  Proposition 2 (Performance Bounds for ${\pi_{\tt LyOff}}$).

Suppose that Assumption 1 and Assumption 2 hold with positive $\epsilon$,
$\sigma^{2}$, $r_{\tt max}$ and $\mu_{\tt min}$. Then, given the budget $B$,
for any $V>0$ and $\delta\in[0,c)$, the regret and constraint-violation levels
under ${\pi_{\tt LyOff}}$ satisfy:

$\displaystyle{\tt REG}^{{\pi_{\tt LyOff}}}(B)$
$\displaystyle=O\Bigg{(}\frac{\sigma^{2}B}{V\mu_{\tt min}^{2}}+\frac{\delta
r_{\tt max}B}{\epsilon\mu_{\tt min}^{2}}\Bigg{)},$ (13) $\displaystyle
D^{{\pi_{\tt LyOff}}}(B)$ $\displaystyle=O\Big{(}\frac{1}{B}+\frac{Vr_{\tt
max}}{B\mu_{\tt min}\epsilon}-\frac{\delta}{\mu_{\tt min}}\Big{)}.$ (14)

Specifically, let $V=v_{0}\sqrt{B}$ and $\delta={\delta_{0}}/{\sqrt{B}}$ with
some design parameters $\delta_{0}>0,v_{0}>0$. We can select
$\delta_{0}\in(\frac{r_{\tt max}}{\epsilon}v_{0},c\sqrt{B})$ such that for
sufficiently large $B$,

${\tt REG}^{{\pi_{\tt LyOff}}}(B)=O\Big{(}\sqrt{B}\Big{)},\quad D^{{\pi_{\tt
LyOff}}}(B)=O\Big{(}\frac{-1}{\sqrt{B}}\Big{)}.$ (15)

The proof of Proposition 2 can be found in Appendix D.1. Proposition 2
establishes the fact that ${\pi_{\tt LyOff}}$ policy achieves $O(\sqrt{B})$
regret and zero constraint-violation for sufficiently large $B$ given the
first-order statistics
$\mathbb{E}[X_{n,k}],\mathbb{E}[R_{n,k}],\mathbb{E}[{Y}_{n,k}]$ for all arms
$k\in\mathbb{K}$. The ${\pi_{\tt LyOff}}$ policy will serve as a guide for our
online learning algorithm, introduced next.

Algorithm 1 $\tt LyOff$ Algorithm

1:Input: $B,K,c,V,\delta$,

2: $\mathbb{E}[X_{1,k}],\mathbb{E}[R_{1,k}],\mathbb{E}[Y_{1,k}]$

3:Initialize $Q_{0}=0$, $\tt cost=0$, $n=1$

4:while $\tt cost\leq B$ do

5:
$\Psi_{n}(k,Q_{n})=-V\frac{\mathbb{E}[R_{1,k}]}{\mathbb{E}[X_{1,k}]}+Q_{n}\frac{\mathbb{E}[Y_{1,k}]}{\mathbb{E}[X_{1,k}]}$

6: $k_{n}=\arg\min_{k\in\mathbb{K}}~{}\Psi_{n}(k,Q_{n})$

7: Select arm $I_{n}=k_{n}$.

8: Observe $X_{n},R_{n},Y_{n}$.

9: $Q_{n+1}=\max\big{\\{}0,Q_{n}+Y_{n}-(c-\delta)X_{n}\big{\\}}$

10: $\tt cost=cost$ $+$ $X_{n}$.

11: $n=n+1$.

12:end while

###  5.2 Online Lyapunov-Drift Minimizing Policy LyOn Design

A strong assumption in ${\pi_{\tt LyOff}}$ was the a priori knowledge of the
first-order statistics for all variables. Recall that in the learning problem,
we do not have this knowledge. Instead, we must work with estimations by using
the observed outcomes from bandit type feedback to learn the optimal decision.
Furthermore, like all exploration-exploitation problems, the online
exploration is a crucial component of the learning problem here as well.
Optimizing this trade-off with low regret and constraint-violation is
particularly challenging in this setting due to the knapsack-type budget
constraints from random costs, as well as the random penalties in the
constraint. In this section, we will design and analyze the LyOn Algorithms by
combining tools from renewal theory, stochastic control, as well as bandit
optimization to address these challenges for optimal learning.

_Strategy:_ Our strategy will be to approximate the Lyapunov drift-plus-
penalty ratio $\Psi_{n}$ in equation (10) by using the empirical estimates for
the first-order statistics. In order to encourage online exploration, we will
use confidence bounds so that the index at the end will be a high-probability
lower bound for $\Psi_{n}$. The following definitions will be needed to define
the online algorithm.

######  Definition 7 (Confidence Radius).

For any $n\geq 1$ and arm $k\in\mathbb{K}$, let
$\mathcal{I}_{n}^{\pi}(k)=\\{t\in[1,n]:I_{t}^{\pi}=k\\}$,
$T_{k}^{\pi}(n)=|\mathcal{I}_{n}^{\pi}(k)|=\sum_{t=1}^{n}\mathbb{I}\\{I_{t}^{\pi}=k\\}$
be the number of pulls for arm $k$ under a policy $\pi$ in the first $n$
epochs. For a given $\alpha>0$, the confidence radius for arm $k$ is defined
as: ${\tt rad}_{k}(n,\alpha)=\sqrt{\frac{2\alpha\log(n)}{T_{k}(n)}}.$

To ensure the confidence radius is small enough, we have an initial
exploration phase that is controlled by a parameter $\beta_{0}$ which depends
on $\epsilon,y_{\tt max}$, and $\mu_{\tt min}$. Specifically, we set
$\beta_{0}=\frac{32\alpha(1+y_{\tt max})^{2}}{\mu_{\tt min}^{2}\epsilon^{2}}$
to guarantee the concentration event in Lemma 6 of Appendix D.

For a subset of indices $S\subset\mathbb{N}$ and a stochastic process
$\\{Z_{n}:n\in\mathbb{N}\\}$, let
$\widehat{\mathbb{E}}_{S}[Z]=\min\big{\\{}1,\frac{1}{|S|}\sum_{t\in
S}Z_{t}\big{\\}},$ be the empirical mean estimator. Then, the empirical reward
rate and empirical penalty rate under policy $\pi$ after $n$ epochs are
defined as:

$\displaystyle\widehat{r}_{n,k}^{\pi}=\frac{\widehat{\mathbb{E}}_{\mathcal{I}_{n}^{\pi}(k)}[R_{k}]}{\widehat{\mathbb{E}}_{\mathcal{I}_{n}^{\pi}(k)}[X_{k}]},\quad\widehat{y}_{n,k}^{\pi}=\frac{\widehat{\mathbb{E}}_{\mathcal{I}_{n}^{\pi}(k)}[Y_{k}]}{\widehat{\mathbb{E}}_{\mathcal{I}_{n}^{\pi}(k)}[X_{k}]},\quad
k\in\mathbb{K}.$ (16)

######  Definition 8 (Empirical Lyapunov Drift-Plus-Penalty Ratio).

Let $Q_{n}^{\pi}$ be the variable evolving under $\pi$ as in (9). Then, the
empirical Lyapunov drift-plus-penalty ratio at epoch $n$ is defined as
follows:

$\widehat{\Psi}_{n}(k,Q_{n}^{\pi})=-V\cdot\widehat{r}_{n-1,k}^{\pi}+Q_{n}^{\pi}\cdot\widehat{y}_{n-1,k}^{\pi},$
(17)

where $V>0$ is a design parameter. Define the empirical lower confidence bound
for $\widehat{\Psi}_{n}(k,Q_{n}^{\pi})$ as

$\displaystyle\widehat{\Gamma}_{n}(k,Q_{n}^{\pi})$
$\displaystyle=\widehat{\Psi}_{n}(k,Q_{n}^{\pi})-{\tt
rad}_{k}(n-1,\alpha)\frac{V(1+\widehat{r}_{n-1,k}^{\pi})}{\widehat{\mathbb{E}}_{\mathcal{I}_{n-1}^{\pi}(k)}[X_{k}]}$
$\displaystyle\quad+{\tt
rad}_{k}(n-1,\alpha)\frac{Q_{n}^{\pi}(1+\widehat{y}_{n-1,k}^{\pi})}{\widehat{\mathbb{E}}_{\mathcal{I}_{n-1}^{\pi}(k)}[X_{k}]}$
(18)

With these definitions, the online Lyapunov-Drift Minimizing Algorithm $\tt
LyOn$ is defined in Algorithm 2.

Algorithm 2 $\tt LyOn$ Algorithm

1:Input: $B,K,c,\alpha,V,\delta,\beta_{0},\mu_{\tt min}$

2:Initialize $Q_{0}=0$, $\tt cost=0$, $n=1$

3:Select each arm $\big{\lceil}\beta_{0}\log\big{(}\frac{2B}{\mu_{\tt
min}}\big{)}\big{\rceil}$ times.

4:Update $n$, $\tt cost$, $\widehat{\Gamma}_{n}(k,Q_{n})$ (eq. (8)).

5:while $\tt cost\leq B$ do

6:
$k_{n}={\arg\min}_{k\in\mathbb{K}}\big{\\{}\widehat{\Gamma}_{n}(k,Q_{n})\big{\\}}$

7: Select arm $I_{n}=k_{n}$. Observe $X_{n},R_{n},Y_{n}$.

8: $Q_{n+1}=\max\big{\\{}0,Q_{n}+Y_{n}-(c-\delta)X_{n}\big{\\}}$

9: $\tt cost=cost$ $+$ $X_{n}$.

10: Update $\widehat{\Gamma}_{n}(k,Q_{n})$ (eq. (8)).

11: $n=n+1$.

12:end while

######  Remark 1.

Before we analyze it, we make the following observations about the LyOn
Algorithm.

  1. 1.

Lyon is an extremely low-complexity, iterative algorithm, whereby in every
step a simple update is performed.

  2. 2.

The index to be minimized in (8) is a high-probability lower bound for
$\Psi_{n}(k,Q_{n}^{\pi_{\tt LyOn}})$. Thus, given the available data
$\mathcal{F}_{n-1}^{\pi_{\tt LyOn}}$, the algorithm makes an optimistic drift-
minimizing arm selection in the face of uncertainty.

  3. 3.

If $I_{n}^{\pi_{\tt LyOn}}=k$, then at least one of the following must be
true: a) High confidence for arm $k$, large $r_{k}$ and small $Q_{n}^{\pi_{\tt
LyOn}}$. b) High confidence for arm $k$, large $Q_{n}^{\pi_{\tt LyOn}}$ and
small $y_{k}$. c) Low confidence for arm $k$. As such, the LyOn Algorithm
incentivizes online exploration by choosing arms with very low confidence.

  4. 4.

The LyOn Algorithm extends the UCB-BwI Algorithm proposed in (Cayci, Eryilmaz,
and Srikant 2019) to the non-trivial and useful cases with stochastic
feasibility constraints. Note that $Q_{n}^{\pi_{\tt LyOn}}=0$ if there is no
constraint, thus the LyOn Algorithm reduces to the UCB-BwI Algorithm.

######  Theorem 1 (Performance Bounds for ${\pi_{\tt LyOn}}$).

Suppose that Assumption 1 and Assumption 2 hold with positive $\epsilon$,
$\sigma^{2}$, $r_{\tt max}$, $y_{\tt max}$, and $\mu_{\tt min}$. Then, for any
$V>0$ and $\delta\in[0,c)$, the regret and constraint-violation levels under
${\pi_{\tt LyOn}}$ satisfy:

$\displaystyle{\tt REG}^{{\pi_{\tt LyOn}}}(B)$
$\displaystyle=O\Bigg{(}\frac{r_{\tt max}\sqrt{{\color[rgb]{0,0,0}K}B\log
B}}{\mu_{\tt min}^{2}}+\frac{y_{\tt max}^{2}K\log B}{\epsilon^{2}\mu_{\tt
min}^{2}}$ $\displaystyle+\frac{\sigma^{2}+y_{\tt max}+\delta\log B}{V\mu_{\tt
min}^{2}}B+\frac{\delta r_{\tt max}}{\epsilon\mu_{\tt min}^{2}}B\Bigg{)},$
(19) $\displaystyle D^{{\pi_{\tt LyOn}}}(B)$
$\displaystyle=O\Bigg{(}\frac{y_{\tt max}^{2}K\log B}{\epsilon^{2}\mu_{\tt
min}^{2}B}+\frac{Vr_{\tt max}}{B\mu_{\tt min}\epsilon}-\frac{\delta}{\mu_{\tt
min}}\Bigg{)},$ (20)

Specifically, let $V=v_{0}\sqrt{B\log B}$ and $\delta={\delta_{0}}{\sqrt{\log
B/B}}$ with design parameters $\delta_{0}>0,v_{0}>0$. We can select
$\delta_{0}\in(\frac{r_{\tt max}}{\epsilon}v_{0},c\sqrt{B})$ such that for
sufficiently large $B$,

${\tt REG}^{{\pi_{\tt LyOn}}}(B)=O\Big{(}\sqrt{{\color[rgb]{0,0,0}K}B\log
B}\Big{)},\;D^{{\pi_{\tt LyOn}}}(B)=O\Big{(}\frac{-1}{\sqrt{B}}\Big{)}.$ (21)

The proof of Theorem 1 can be found in Appendix E. Theorem 1 implies that
${\pi_{\tt LyOn}}$ achieves $O(\sqrt{{\color[rgb]{0,0,0}K}B\log B})$ regret
and zero constraint-violation for sufficiently large $B$ while learning the
first order statistics under a bandit feedback.

In addition to the fact that cumulative reward and penalty processes form
stopped and controlled random walks, the main challenge in analyzing the $\tt
LyOn$ algorithm performance is that $Q_{n}$ is correlated with the sample
path. To address this, we prove a maximal inequality for $Q_{n}$ under a
concentration event (Lemma 7 in Appendix E), which can have its own value in
other queuing systems. Also note that, compared with $\tt LyOff$, the online
algorithm has a very small increase on the regret bounds by a factor of
$\sqrt{{\color[rgb]{0,0,0}K}\log B}$. This is a reasonable price to pay since
we are not assuming any known statistics. To the best of our knowledge, these
are the best results available on both regret and constraint-violation in the
current setup. In the special case of unit cost scenario, our algorithm
theoretically guarantees a similar regret performance to prior designs
(Agrawal and Devanur 2014) while providing a stronger constraint-violation
guarantee.

(a) Reward rate ($\tt REW(B)/B)$

(b) Constraint-violation

(c) Time allocation

(d) Reward rate ($\tt REW(B)/B)$

(e) Constraint-violation

(f) Time allocation

Figure 1: Performance of $\tt LyOff$ and $\tt LyOn$ for different parameters.
(a), (b), and (c) use $v_{0}=1$, $\delta_{0}=0.5$, (d), (e), and (f) use
$v_{0}=1$, $\delta_{0}=15$.

##  6 Simulations

We implement both $\tt LyOff$ and $\tt LyOn$ algorithms for $K=2$ arms with
Bernoulli distributed rewards, costs, and penalties. Assuming $c=0.8$, arm 1
is selected to have a high reward rate and a high penalty rate with
$\mathbb{E}[X_{1}]=0.4,\mathbb{E}[Y_{1}]=0.6$, and $\mathbb{E}[R_{1}]=0.8$.
Arm 2 is selected to have a low reward rate and a low penalty rate with
$\mathbb{E}[X_{2}]=0.6,\mathbb{E}[Y_{2}]=0.3$, and $\mathbb{E}[R_{2}]=0.6$.
These values are interesting in that, an optimal controller will have to make
a trade-off between the two arms, whereas any static policy selecting one of
the arms will result in either linear regret or linear constraint-violation.

Figure 1a, 1b, and 1c show the simulation results (averaged over $10^{4}$
runs) with $v_{0}=1$ and $\delta_{0}=0.5$ for $\tt LyOff$ and $\tt LyOn$
algorithms. To observe the reward rate behavior, in Figure 1a, we plot the
reward rates ${\tt REW}^{\pi}(B)/B$ of ${\pi_{\tt LyOff}}$ and ${\pi_{\tt
LyOn}}$ and the optimal randomized policy $\pi^{*}$, with varying budgets $B$.
This figure shows that both the offline and the online designs reach the rate
of the optimal design, as predicted by our analysis. Also, Figure 1b verifies
the fast decaying of constraint-violation with rate $\tilde{O}(1/B)$ as $B$
increases, which confirms the scaling behaviour revealed in our analyses.
Figure 1c further confirms the convergence of $\tt LyOff$ and $\tt LyOn$
towards $\pi^{*}$ by showing the proportion of time allocated to each arm. As
predicted by Theorem 1, Figure 1d, 1e, and 1f show that we can indeed select
specific $v_{0}$ and $\delta_{0}$ values such that the constraint-violation
becomes negative when $B$ is sufficiently large. At the same time, the reward
rate and proportion of time allocated to each arm still converge to the rate
of the optimal design.

In Appendix F, to check the performance of our algorithms for larger $K$, we
increase the number of arms by adding arms with the principle that high reward
rate arm also has high penalty rate (otherwise the arms are not competitive).
We also investigate the effect of design choices $V$ and $\delta$ to capture
the tradeoff between constraint-violation and regret under the $\tt LyOff$ and
$\tt LyOn$ algorithms.

##  7 Conclusion

In this paper, we proposed a broadly applicable computationally efficient
methodology based on Lyapunov-drift-minimization for solving a penalty-
constrained reward maximization problem with a limited budget, random costs,
and bandit feedback. Both offline and online algorithms are developed based on
this design methodology, which are also proven to have sharp regret and
constraint-violation performance. The approach and algorithms are applicable
in diverse domains whereby knapsack budget constraints and stochastic
feasibility constraints are required. An interesting future work that can
benefit from the same methodology would be to extend our setting to the
scenario of multiple constraints and infinitely many arms.

## Acknowledgments

This work is supported in part by the NSF grants: CNS-NeTS-1717045, CNS-
SpecEES-1824337, CNS-NeTS-2007231, CNS-NeTS-2106679, IIS-2112471, CCF-1934986;
and the ONR Grant N00014-19-1-2621.

## References

  * Agrawal and Devanur (2014) Agrawal, S.; and Devanur, N. R. 2014.  Bandits with concave rewards and convex knapsacks.  In _Proceedings of the fifteenth ACM conference on Economics and computation_ , 989–1006. ACM.
  * Asmussen (2008) Asmussen, S. 2008.  _Applied probability and queues_ , volume 51.  Springer Science & Business Media.
  * Badanidiyuru, Kleinberg, and Slivkins (2013) Badanidiyuru, A.; Kleinberg, R.; and Slivkins, A. 2013.  Bandits with knapsacks.  In _2013 IEEE 54th Annual Symposium on Foundations of Computer Science_ , 207–216. IEEE.
  * Balseiro and Gur (2019) Balseiro, S. R.; and Gur, Y. 2019.  Learning in repeated auctions with budgets: Regret minimization and equilibrium.  _Management Science_ , 65(9): 3952–3968.
  * Berry and Fristedt (1985) Berry, D. A.; and Fristedt, B. 1985.  Bandit problems: sequential allocation of experiments (Monographs on statistics and applied probability).  _London: Chapman and Hall_ , 5: 71–87.
  * Bitran and Magnanti (1976) Bitran, G. R.; and Magnanti, T. L. 1976.  Duality and sensitivity analysis for fractional programs.  _Operations Research_ , 24(4): 675–699.
  * Bonnans and Shapiro (2000) Bonnans, J. F.; and Shapiro, A. 2000.  Stability and Sensitivity Analysis.  In _Perturbation Analysis of Optimization Problems_ , 260–400. Springer.
  * Bubeck, Cesa-Bianchi et al. (2012) Bubeck, S.; Cesa-Bianchi, N.; et al. 2012.  Regret analysis of stochastic and nonstochastic multi-armed bandit problems.  _Foundations and Trends® in Machine Learning_ , 5(1): 1–122.
  * Cayci, Eryilmaz, and Srikant (2019) Cayci, S.; Eryilmaz, A.; and Srikant, R. 2019.  Learning to Control Renewal Processes with Bandit Feedback.  _Proceedings of the ACM on Measurement and Analysis of Computing Systems_ , 3(2): 43.
  * Cayci, Eryilmaz, and Srikant (2020) Cayci, S.; Eryilmaz, A.; and Srikant, R. 2020.  Budget-constrained bandits over general cost and reward distributions.  In _International Conference on Artificial Intelligence and Statistics_ , 4388–4398. PMLR.
  * Cayci, Gupta, and Eryilmaz (2020) Cayci, S.; Gupta, S.; and Eryilmaz, A. 2020.  Group-Fair Online Allocation in Continuous Time.  _Advances in Neural Information Processing Systems_ , 33.
  * Flajolet and Jaillet (2015) Flajolet, A.; and Jaillet, P. 2015.  Logarithmic regret bounds for bandits with knapsacks.  _arXiv preprint arXiv:1510.01800_.
  * Georgiadis, Neely, and Tassiulas (2006) Georgiadis, L.; Neely, M. J.; and Tassiulas, L. 2006.  _Resource allocation and cross-layer control in wireless networks_.  Now Publishers Inc.
  * Ghosh et al. (2009) Ghosh, A.; McAfee, P.; Papineni, K.; and Vassilvitskii, S. 2009.  Bidding for representative allocations for display advertising.  In _International workshop on internet and network economics_ , 208–219. Springer.
  * Hajek (1982) Hajek, B. 1982.  Hitting-time and occupation-time bounds implied by drift analysis with applications.  _Advances in Applied probability_ , 502–525.
  * Hannák et al. (2017) Hannák, A.; Wagner, C.; Garcia, D.; Mislove, A.; Strohmaier, M.; and Wilson, C. 2017.  Bias in online freelance marketplaces: Evidence from taskrabbit and fiverr.  In _Proceedings of the 2017 ACM conference on computer supported cooperative work and social computing_ , 1914–1933.
  * Harchol-Balter (2000) Harchol-Balter, M. 2000.  Task assignment with unknown duration.  In _Proceedings 20th IEEE International Conference on Distributed Computing Systems_ , 214–224. IEEE.
  * Ipeirotis (2010) Ipeirotis, P. G. 2010.  Analyzing the amazon mechanical turk marketplace.  _XRDS: Crossroads, The ACM Magazine for Students_ , 17(2): 16–21.
  * Khalek, Caramanis, and Heath (2014) Khalek, A. A.; Caramanis, C.; and Heath, R. W. 2014.  Delay-constrained video transmission: Quality-driven resource allocation and scheduling.  _IEEE Journal of Selected Topics in Signal Processing_ , 9(1): 60–75.
  * Lai and Robbins (1985) Lai, T. L.; and Robbins, H. 1985.  Asymptotically efficient adaptive allocation rules.  _Advances in applied mathematics_ , 6(1): 4–22.
  * Liu et al. (2020) Liu, X.; Li, B.; Shi, P.; and Ying, L. 2020.  POND: Pessimistic-Optimistic oNline Dispatch.  _arXiv preprint arXiv:2010.09995_.
  * Liu et al. (2021) Liu, X.; Li, B.; Shi, P.; and Ying, L. 2021.  An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints.  _arXiv preprint arXiv:2102.05295_.
  * Neely (2010) Neely, M. J. 2010.  Stochastic network optimization with application to communication and queueing systems.  _Synthesis Lectures on Communication Networks_ , 3(1): 1–211.
  * Neely (2012) Neely, M. J. 2012.  Dynamic optimization and learning for renewal systems.  _IEEE Transactions on Automatic Control_ , 58(1): 32–46.
  * Papadimitriou and Tsitsiklis (1999) Papadimitriou, C. H.; and Tsitsiklis, J. N. 1999.  The complexity of optimal queuing network control.  _Mathematics of Operations Research_ , 24(2): 293–305.
  * Qiu et al. (2020) Qiu, S.; Wei, X.; Yang, Z.; Ye, J.; and Wang, Z. 2020.  Upper confidence primal-dual optimization: Stochastically constrained Markov decision processes with adversarial losses and unknown transitions.  _arXiv preprint arXiv:2003.00660_.
  * Rappaport et al. (2015) Rappaport, T. S.; Heath Jr, R. W.; Daniels, R. C.; and Murdock, J. N. 2015.  _Millimeter wave wireless communications_.  Pearson Education.
  * Robbins (1952) Robbins, H. 1952.  Some aspects of the sequential design of experiments.  _Bulletin of the American Mathematical Society_ , 58(5): 527–535.
  * Tran-Thanh et al. (2012) Tran-Thanh, L.; Chapman, A.; Rogers, A.; and Jennings, N. R. 2012.  Knapsack based optimal policies for budget–limited multi–armed bandits.  In _Twenty-Sixth AAAI Conference on Artificial Intelligence_.
  * Wainwright (2019) Wainwright, M. J. 2019.  _High-dimensional statistics: A non-asymptotic viewpoint_ , volume 48.  Cambridge University Press.
  * Xia et al. (2016) Xia, Y.; Ding, W.; Zhang, X.-D.; Yu, N.; and Qin, T. 2016.  Budgeted bandit problems with continuous random costs.  In _Asian conference on machine learning_ , 317–332.
  * Xia et al. (2015) Xia, Y.; Li, H.; Qin, T.; Yu, N.; and Liu, T.-Y. 2015.  Thompson sampling for budgeted multi-armed bandits.  In _Twenty-Fourth International Joint Conference on Artificial Intelligence_.
  * Yu and Neely (2020) Yu, H.; and Neely, M. J. 2020.  A Low Complexity Algorithm with $O(\sqrt{T})$ Regret and $O(1)$ Constraint Violations for Online Convex Optimization with Long Term Constraints.  _Journal of Machine Learning Research_ , 21(1): 1–24.

##  Appendix A Applications

####  $\bullet$ Contractual Hiring

Our problem formulation also finds interesting applications in fair
contractual hiring (Hannák et al. 2017; Ipeirotis 2010) and server allocation
(Harchol-Balter 2000). Consider a task allocation problem, where tasks are
sequentially allocated to a worker/server who belongs to one of $K$ groups. If
$n^{th}$ task is allocated to a worker from group $k$, it takes $X_{n,k}$ time
to complete the task, and yields a reward $R_{n,k}$ upon completion. For
reward maximization objective, the tasks are allocated to the worker group
that maximizes the expected total reward, and the other groups do not receive
any tasks (see (Cayci, Gupta, and Eryilmaz 2020)). However, in many systems,
the ”fair” allocation of tasks are desired. One way to impose fairness is to
impose constraints on the total time budget $B$ allocated to user groups. Let
$A\subset\mathbb{K}$ be a class of user groups. By letting
$Y_{n,k}=\omega\cdot\mathbb{I}\\{k\notin A\\}$ for all $k$ and some
$\omega\geq 0$, the solution to the optimization problem (4) yields a fair
allocation rule where the fraction of the budget allocated to the worker
groups in $A$ should be at least proportional to $c$.

####  $\bullet$ Online Advertising

The same idea can be applied to online advertising. Consider an advertiser
with a budget $B$ and $K$ advertising spots (impressions) to select from. In
order to win an impression, the advertiser has to bid in an auction (Ghosh et
al. 2009; Balseiro and Gur 2019), which means the budget consumption $X_{n,k}$
is random. Winning an impression will generate a random return $R_{n,k}$ which
measures the value of that impression. The goal of an advertiser is to
maximize the expected total return under the budget constraint. In addition,
the advertiser may want to set a constraint on the number of bids for certain
type of impressions to balance between different demographic groups and
locations, which can be represented by $Y_{n,k}$ defined above.

##  Appendix B Preliminary Results

###  B.1 Results from Renewal Theory

In this section, we will prove results on the counting process $N^{\pi}(B)$
based on renewal theory, which will be used throughout the proofs in the
following sections. The proofs are based on (Cayci, Eryilmaz, and Srikant
2020).

######  Proposition 3 (High-probability upper bound for $N^{\pi}(B)$).

Consider an i.i.d. process $X_{n,k}\in[0,1]$ a.s. for each $k\in\mathbb{K}$,
and define $n_{0}(B)=\lceil 2B/\mu_{\tt min}\rceil$ for $\mu_{\tt
min}=\min_{k\in\mathbb{K}}~{}\mathbb{E}[X_{n,k}]$. Then, under any policy
$\pi\in\Pi$, we have the following inequality for all $B>1$:

$\mathbb{P}(N^{\pi}(B)\geq n)=\mathbb{P}\Big{(}\sum_{t=1}^{n}X_{t}^{\pi}\leq
B\Big{)}\leq e^{-n\mu_{\tt min}^{2}/8},$ (22)

for any $n\geq n_{0}(B)$.

###### Proof.

The equality in (22) is due to the renewal relation $\\{N^{\pi}(B)\geq
n\\}=\Big{\\{}\sum_{t=1}^{n}X_{t}^{\pi}\leq B\Big{\\}}.$ In order to prove the
inequality, first note that
$\mathbb{E}[X_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}]\geq\mu_{\tt min}$ for any
$n\geq 1$, and
$D_{n}=X_{n}^{\pi}-\mathbb{E}[X_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}]$ is a
martingale difference sequence with $|D_{n}|\leq 1$ almost surely. Then, we
have the following relation:

$\displaystyle\\{S_{n}^{\pi}\leq B\\}$
$\displaystyle=\Big{\\{}\sum_{t=1}^{n}D_{t}\leq
B-\sum_{t=1}^{n}\mathbb{E}[X_{t}^{\pi}|\mathcal{F}_{t-1}^{\pi}]\Big{\\}}\subset\\{\sum_{t=1}^{n}D_{t}\leq
B-n\mu_{\tt min}\\}.$

For any $n\geq n_{0}(B)$, we have $B-n\mu_{\tt min}\leq-n\mu_{\tt min}/2$.
Therefore, we have:

$\displaystyle\mathbb{P}(S_{n}^{\pi}\leq B)$
$\displaystyle\leq\mathbb{P}\Big{(}\sum_{t=1}^{n}D_{t}\leq-\frac{n\mu_{\tt
min}}{2}\Big{)},$ $\displaystyle\leq e^{-n\mu_{\tt min}^{2}/8},$

where the second inequality follows from concentration bounds for martingale
difference sequence (Corollary 2.20 in (Wainwright 2019)) with $|D_{n}|\leq 1$
and deviation $t=\mu_{\tt min}/2$ . ∎

In the following, we characterize the performance of a stationary randomized
policy $\pi=\pi(\mathbf{p})$ by proving tight bounds on the expected
cumulative reward and penalty under $\pi(\mathbf{p})$.

######  Proposition 4 (Performance of a Stationary Randomized Policy).

For any $\mathbf{p}\in\Delta_{K}$, let $\pi(\mathbf{p})$ be a stationary
randomized policy, and let
$r(\mathbf{p})=\frac{\sum_{k\in\mathbb{K}}p_{k}\mathbb{E}[R_{1,k}]}{\sum_{k\in\mathbb{K}}p_{k}\mathbb{E}[X_{1,k}]}$
and
$y(\mathbf{p})=\frac{\sum_{k\in\mathbb{K}}p_{k}\mathbb{E}[Y_{1,k}]}{\sum_{k\in\mathbb{K}}p_{k}\mathbb{E}[X_{1,k}]}$.
Then, we have the following inequalities:

$r(\mathbf{p})B\leq\mathbb{E}[{\tt REW}^{\pi(\mathbf{p})}(B)]\leq
r(\mathbf{p})\Big{(}B+\frac{1}{\mu_{\tt min}^{2}}\Big{)}.$ (23)

$y(\mathbf{p})B\leq\mathbb{E}\Bigg{[}\sum_{n=1}^{N^{\pi(\mathbf{p})}(B)}Y_{n}^{\pi(\mathbf{p})}\Bigg{]}\leq
y(\mathbf{p})\Big{(}B+\frac{1}{\mu_{\tt min}^{2}}\Big{)}.$ (24)

###### Proof.

The proof is based on Proposition 2 in (Cayci, Gupta, and Eryilmaz 2020).
Under $\pi(\mathbf{p})$, it can be shown that arm $k$ is pulled exactly once
in a regenerative cycle with total expected cost
$\big{(}\sum_{j}p_{j}\mathbb{E}[X_{1,j}]\big{)}/p_{k}$. Therefore, the reward
per unit cost from arm $k$ under $\pi(\mathbf{p})$ is
$r_{k}(\mathbf{p})=\frac{p_{k}\mathbb{E}[R_{1,k}]}{\sum_{j}p_{j}\mathbb{E}[X_{1,j}]}$,
which implies the reward per unit cost from all arms is
$r(\mathbf{p})=\sum_{k}r_{k}(\mathbf{p})$. Similarly, the penalty per unit
cost from arm $k$ under $\pi(\mathbf{p})$ is
$y_{k}(\mathbf{p})=\frac{p_{k}\mathbb{E}[Y_{1,k}]}{\sum_{j}p_{j}\mathbb{E}[X_{1,j}]}$,
which implies the penalty per unit cost from all arms is
$y(\mathbf{p})=\sum_{k}y_{k}(\mathbf{p})$. Hence, the upper and lower bounds
follow from Proposition 6.1 and Proposition 6.2 (Lorden’s inequality) in
section V of (Asmussen 2008), respectively. ∎

###  B.2 Decomposition of Regret and Constraint-violation

######  Lemma 1 (Regret Decomposition).

For any causal policy $\pi\in\Pi$, the regret with respect to the optimal
stationary policy $\pi^{*}$ can be decomposed as:

$\displaystyle\mathbb{E}[{\tt REW}^{\pi^{*}}(B)]-\mathbb{E}[{\tt
REW}^{\pi}(B)]$
$\displaystyle\leq\Big{(}r(\mathbf{p}^{*})-\frac{\mathbb{E}[\sum_{n=1}^{n_{0}(B)}R_{n}^{\pi}]}{\mathbb{E}[\sum_{n=1}^{n_{0}(B)}X_{n}^{\pi}]}\Big{)}\cdot\frac{2B}{\mu_{\tt
min}}+\frac{r_{\tt max}}{\mu_{\tt min}^{2}}\Big{(}1+8e^{-B\mu_{\tt
min}/4}\Big{)}$

where $\mathbf{p^{*}}=(p_{1}^{*},\ldots,p_{K}^{*})$ is the distribution of
budget under $\pi^{*}$ and $n_{0}(B)=\lceil 2B/\mu_{\tt min}\rceil$ is a high
probability upper bounds for $N^{\pi}(B)$.

###### Proof.

Take an arbitrary causal policy $\pi\in\Pi$. Since $\pi$ is causal, the
following holds for some
$\mathbf{p}_{n}^{\pi}=(p_{1,n}^{\pi},p_{2,n}^{\pi},\ldots,p_{K,n}^{\pi})\in\mathcal{F}_{n-1}^{\pi}$:

$\mathbb{E}[R_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}]=r(\mathbf{p}_{n}^{\pi})\mathbb{E}[X_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}]=r(\mathbf{p}_{n}^{\pi})\sum_{k\in\mathbb{K}}p_{k,n}^{\pi}\mathbb{E}[X_{n,k}|\mathcal{F}_{n-1}^{\pi}].$
(25)

We have the following inequality for the expected cumulative reward under
$\pi$:

$\displaystyle\mathbb{E}[{\tt REW}^{\pi}(B)]$
$\displaystyle=\mathbb{E}\Big{[}\sum_{n=1}^{\infty}\mathbb{I}\\{S_{n-1}^{\pi}\leq
B\\}R_{n}^{\pi}\Big{]},$
$\displaystyle=\mathbb{E}\Big{[}\sum_{n=1}^{\infty}\mathbb{E}\big{[}R_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}\big{]}\mathbb{I}\\{S_{n-1}^{\pi}\leq
B\\}\Big{]},$ (26)
$\displaystyle=\mathbb{E}\Big{[}\sum_{n=1}^{\infty}r(\mathbf{p}_{n}^{\pi})\mathbb{E}\big{[}X_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}\big{]}\mathbb{I}\\{S_{n-1}^{\pi}\leq
B\\}\Big{]},$ (27)

where (26) follows since $\pi$ is causal (i.e.,
$I_{n}^{\pi}\in\mathcal{F}_{n-1}^{\pi}$) and
$S_{n-1}^{\pi}\in\mathcal{F}_{n-1}$, and (27) follows from the relation (25).

For the optimal stationary randomized policy $\pi^{*}$, by Proposition 4, we
have the following inequalities:

$\displaystyle\mathbb{E}[{\tt REW}^{\pi^{*}}(B)]$ $\displaystyle\leq
r(\mathbf{p}^{*})\Big{(}B+\frac{1}{\mu_{\tt min}^{2}}\Big{)},$
$\displaystyle\leq
r(\mathbf{p}^{*})\Big{(}\mathbb{E}\Big{[}\sum_{n=1}^{N^{\pi}(B)}X_{n}^{\pi}\Big{]}+\frac{1}{\mu_{\tt
min}^{2}}\Big{)},$ (28)
$\displaystyle=\mathbb{E}\Big{[}\sum_{n=1}^{\infty}r(\mathbf{p}^{*})\mathbb{E}\big{[}X_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}\big{]}\mathbb{I}\\{S_{n-1}^{\pi}\leq
B\\}\Big{]}+\frac{r(\mathbf{p}^{*})}{\mu_{\tt min}^{2}},$ (29)

where (28) uses the fact that $B\leq\sum_{n=1}^{N^{\pi}(B)}X_{n}^{\pi}$.

Combining (27) and (29), we have

$\displaystyle\mathbb{E}[{\tt REW}^{\pi^{*}}(B)]-\mathbb{E}[{\tt
REW}^{\pi}(B)]$
$\displaystyle\leq\mathbb{E}\Big{[}\sum_{n=1}^{\infty}\big{(}r(\mathbf{p}^{*})-r(\mathbf{p}_{n}^{\pi})\big{)}\mathbb{E}\big{[}X_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}\big{]}\mathbb{I}\\{S_{n-1}^{\pi}\leq
B\\}\Big{]}+\frac{r(\mathbf{p}^{*})}{\mu_{\tt min}^{2}}$
$\displaystyle\leq\mathbb{E}\Big{[}\sum_{n=1}^{N}\big{(}r(\mathbf{p}^{*})-r(\mathbf{p}_{n}^{\pi})\big{)}\mathbb{E}\big{[}X_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}\big{]}\mathbb{I}\\{S_{n-1}^{\pi}\leq
B\\}\Big{]}$ $\displaystyle\quad+r_{\tt max}\Big{(}\frac{1}{\mu_{\tt
min}^{2}}+\sum_{n>N}\mathbb{P}(S_{n-1}^{\pi}\leq B)\Big{)}.$ (30)

where (30) uses the fact that $X_{n}^{\pi}\in[0,1]$ and $r(\mathbf{p}^{*})\leq
r_{\tt max}$.

Let $n_{0}(B)=\lceil 2B/\mu_{\tt min}\rceil$. By Proposition 3,
$\mathbb{P}(S_{n-1}^{\pi}\leq B)\leq e^{-n\mu_{\tt min}^{2}/8}$ for all
$n>n_{0}(B)$, which implies:

$\displaystyle\sum_{n>n_{0}(B)}\mathbb{P}(S_{n-1}^{\pi}\leq
B)\leq\frac{8e^{-B\mu_{\tt min}/4}}{\mu_{\tt min}^{2}}.$

Thus, setting $N=n_{0}(B)$, we have the following inequality:

$\displaystyle\mathbb{E}[{\tt REW}^{\pi^{*}}(B)]-\mathbb{E}[{\tt
REW}^{\pi}(B)]$ $\displaystyle\leq
r(p^{*})\mathbb{E}\Big{[}\sum_{n=1}^{n_{0}(B)}X_{n}^{\pi}\Big{]}-\mathbb{E}\Big{[}\sum_{n=1}^{n_{0}(B)}R_{n}^{\pi}\Big{]}+r_{\tt
max}\Big{(}\frac{1}{\mu_{\tt min}^{2}}+\frac{8e^{-B\mu_{\tt min}/4}}{\mu_{\tt
min}^{2}}\Big{)}$
$\displaystyle=\Big{(}r(p^{*})-\frac{\mathbb{E}[\sum_{n=1}^{n_{0}(B)}R_{n}^{\pi}]}{\mathbb{E}[\sum_{n=1}^{n_{0}(B)}X_{n}^{\pi}]}\Big{)}\cdot\mathbb{E}\Big{[}\sum_{n=1}^{n_{0}(B)}X_{n}^{\pi}\Big{]}$
$\displaystyle\quad+\frac{r_{\tt max}}{\mu_{\tt
min}^{2}}\Big{(}1+8e^{-B\mu_{\tt min}/4}\Big{)}$
$\displaystyle\leq\Big{(}r(p^{*})-\frac{\mathbb{E}[\sum_{n=1}^{n_{0}(B)}R_{n}^{\pi}]}{\mathbb{E}[\sum_{n=1}^{n_{0}(B)}X_{n}^{\pi}]}\Big{)}\cdot\frac{2B}{\mu_{\tt
min}}+\frac{r_{\tt max}}{\mu_{\tt min}^{2}}\Big{(}1+8e^{-B\mu_{\tt
min}/4}\Big{)}$

∎

######  Lemma 2 (Constraint-violation Decomposition).

For any causal policy $\pi\in\Pi$, the constraint-violation can be decomposed
as:

$\displaystyle D^{\pi}(B)$
$\displaystyle\leq\Bigg{(}\frac{\mathbb{E}\Big{[}\sum_{n=1}^{n_{0}(B)}(Y_{n}^{\pi})\Big{]}}{\mathbb{E}\Big{[}\sum_{n=1}^{n_{0}(B)}(X_{n}^{\pi})\Big{]}}-c\Bigg{)}\cdot\frac{2}{\mu_{\tt
min}}+\frac{8(y_{\tt max}-c)}{B\mu_{\tt min}^{2}}e^{-B\mu_{\tt
min}/4}+\frac{1}{B}$

###### Proof.

For any causal policy $\pi$, the following holds for some
$\mathbf{p}_{n}^{\pi}=(p_{1,n}^{\pi},p_{2,n}^{\pi},\ldots,p_{K,n}^{\pi})\in\mathcal{F}_{n-1}^{\pi}$:

$\mathbb{E}[Y_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}]=y(\mathbf{p}_{n}^{\pi})\mathbb{E}[X_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}]=y(\mathbf{p}_{n}^{\pi})\sum_{k\in\mathbb{K}}p_{k,n}^{\pi}\mathbb{E}[X_{n,k}|\mathcal{F}_{n-1}^{\pi}].$
(31)

Therefore, the constraint-violation satisfies

$\displaystyle B\cdot D^{\pi}(B)$
$\displaystyle=\mathbb{E}\Big{[}\sum_{n=1}^{N^{\pi}(B)}Y_{n}^{\pi}\Big{]}-Bc$
$\displaystyle\leq\mathbb{E}\Big{[}\sum_{n=1}^{N^{\pi}(B)-1}(Y_{n}^{\pi}-cX_{n}^{\pi})\Big{]}+1$
(32)
$\displaystyle=\mathbb{E}\Big{[}\sum_{n=1}^{\infty}\mathbb{E}\big{[}(Y_{n}^{\pi}-cX_{n}^{\pi})|\mathcal{F}_{n-1}^{\pi}\big{]}\mathbb{I}\\{S_{n-1}^{\pi}<B\\}\Big{]}+1$
$\displaystyle=\mathbb{E}\Big{[}\sum_{n=1}^{\infty}(y(\mathbf{p}_{n}^{\pi})-c)\mathbb{E}\big{[}X_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}\big{]}\mathbb{I}\\{S_{n-1}^{\pi}<B\\}\Big{]}+1$
(33)
$\displaystyle\leq\mathbb{E}\Big{[}\sum_{n=1}^{N}(y(\mathbf{p}_{n}^{\pi})-c)\mathbb{E}\big{[}X_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}\big{]}\mathbb{I}\\{S_{n-1}^{\pi}<B\\}\Big{]}$
$\displaystyle\quad+(y_{\tt max}-c)\sum_{n>N}\mathbb{P}(S_{n-1}^{\pi}\leq
B)+1$ (34)

where (32) uses the fact that $B\geq\sum_{n=1}^{N^{\pi}(B)-1}X_{n}^{\pi}$ and
$Y_{n}^{\pi}-cX_{n}^{\pi}\leq 1$; (33) uses the result in (31); (34) uses the
fact that $y(\mathbf{p}_{n}^{\pi})\leq y_{\tt max}$.

Let $n_{0}(B)=\lceil 2B/\mu_{\tt min}\rceil$. Then, by Proposition 3,

$\displaystyle B\cdot D^{\pi}(B)$
$\displaystyle\leq\mathbb{E}\Big{[}\sum_{n=1}^{n_{0}(B)}(Y_{n}^{\pi})\Big{]}-c\mathbb{E}\Big{[}\sum_{n=1}^{n_{0}(B)}(X_{n}^{\pi})\Big{]}+\frac{8(y_{\tt
max}-c)}{\mu_{\tt min}^{2}}e^{-B\mu_{\tt min}/4}+1$
$\displaystyle=\Big{(}\frac{\mathbb{E}\Big{[}\sum_{n=1}^{n_{0}(B)}(Y_{n}^{\pi})\Big{]}}{\mathbb{E}\Big{[}\sum_{n=1}^{n_{0}(B)}(X_{n}^{\pi})\Big{]}}-c\Big{)}\cdot\mathbb{E}\Big{[}\sum_{n=1}^{n_{0}(B)}(X_{n}^{\pi})\Big{]}+\frac{8(y_{\tt
max}-c)}{\mu_{\tt min}^{2}}e^{-B\mu_{\tt min}/4}+1$
$\displaystyle\leq\Big{(}\frac{\mathbb{E}\Big{[}\sum_{n=1}^{n_{0}(B)}(Y_{n}^{\pi})\Big{]}}{\mathbb{E}\Big{[}\sum_{n=1}^{n_{0}(B)}(X_{n}^{\pi})\Big{]}}-c\Big{)}\cdot\frac{2B}{\mu_{\tt
min}}+\frac{8(y_{\tt max}-c)}{\mu_{\tt min}^{2}}e^{-B\mu_{\tt min}/4}+1$

Therefore,

$\displaystyle D^{\pi}(B)$
$\displaystyle\leq\Big{(}\frac{\mathbb{E}\Big{[}\sum_{n=1}^{n_{0}(B)}(Y_{n}^{\pi})\Big{]}}{\mathbb{E}\Big{[}\sum_{n=1}^{n_{0}(B)}(X_{n}^{\pi})\Big{]}}-c\Big{)}\cdot\frac{2}{\mu_{\tt
min}}+\frac{8(y_{\tt max}-c)}{B\mu_{\tt min}^{2}}e^{-B\mu_{\tt
min}/4}+\frac{1}{B}$

∎

##  Appendix C Proof of Proposition 1

###### Proof.

The proof consists of two parts. In the first part, we will prove that the
regret under $\pi^{*}$ is $O(1)$. In the second part, we will prove that the
constraint-violation under $\pi^{*}$ vanishes at a rate $O(1/B)$.

#### (Bounding the regret)

Consider the optimal stationary randomized policy $\pi^{*}$ as defined in
Definition 4. By Proposition 4, for a causal policy $\pi$, we have the
following inequalities:

$\displaystyle\mathbb{E}[{\tt REW}^{\pi^{*}}(B)]$ $\displaystyle\geq
r(\mathbf{p}^{*})B,$ $\displaystyle\geq
r(\mathbf{p}^{*})\Big{(}\mathbb{E}\Big{[}\sum_{n=1}^{N^{\pi}(B)}X_{n}^{\pi}\Big{]}-1\Big{)},$
(35)
$\displaystyle=\mathbb{E}\Big{[}\sum_{n=1}^{\infty}r(\mathbf{p}^{*})\mathbb{E}\big{[}X_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}\big{]}\mathbb{I}\\{S_{n-1}^{\pi}\leq
B\\}\Big{]}-r(\mathbf{p}^{*}),$ (36)

where (35) follows since $\sum_{n=1}^{N^{\pi}(B)-1}X_{n}^{\pi}\leq
B\leq\sum_{n=1}^{N^{\pi}(B)}X_{n}^{\pi}$ and $X_{n,k}\in[0,1]$ almost surely.

Combining (27) and (36), we have:

$\mathbb{E}[{\tt REW}^{\pi}(B)]-\mathbb{E}[{\tt
REW}^{\pi^{*}}(B)]\leq\mathbb{E}\Big{[}\sum_{n=1}^{\infty}\big{(}r(\mathbf{p}_{n}^{\pi})-r(\mathbf{p}^{*})\big{)}\mathbb{E}\big{[}X_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}\big{]}\mathbb{I}\\{S_{n-1}^{\pi}\leq
B\\}\Big{]}+r(\mathbf{p}^{*}).$ (37)

Since $r(\mathbf{p})\leq r_{\tt max}$ for all $\mathbf{p}\in\Delta_{K}$, we
have the following inequality for all $n>1$:

$\displaystyle\mathbb{E}[{\tt REW}^{\pi}(B)]-\mathbb{E}[{\tt
REW}^{\pi^{*}}(B)]\leq\mathbb{E}\Big{[}\sum_{n=1}^{N}\big{(}r(\mathbf{p}_{n}^{\pi})-r(\mathbf{p}^{*})\big{)}\mathbb{E}\big{[}X_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}\big{]}\mathbb{I}\\{S_{n-1}^{\pi}\leq
B\\}\Big{]}$ $\displaystyle+r_{\tt
max}\Big{(}1+\sum_{n>N}\mathbb{P}(S_{n-1}^{\pi}\leq B)\Big{)}.$ (38)

Let $n_{0}(B)=\lceil 2B/\mu_{\tt min}\rceil$. Then, by Proposition 3,
$\mathbb{P}(S_{n-1}^{\pi}\leq B)\leq e^{-n\mu_{\tt min}^{2}/8}$ for all
$n>n_{0}(B)$, which implies:

$\displaystyle\sum_{n>n_{0}(B)}\mathbb{P}(S_{n-1}^{\pi}\leq
B)\leq\frac{8e^{-B\mu_{\tt min}/4}}{\mu_{\tt min}^{2}}.$ (39)

Thus, setting $N=n_{0}(B)$ in (38), we have the following inequality:

$\displaystyle\mathbb{E}[{\tt REW}^{\pi}(B)]-\mathbb{E}[{\tt
REW}^{\pi^{*}}(B)]$
$\displaystyle\leq\mathbb{E}\Big{[}\sum_{n=1}^{n_{0}(B)}R_{n}^{\pi}\Big{]}-r(\mathbf{p}^{*})\mathbb{E}\Big{[}\sum_{n=1}^{n_{0}(B)}X_{n}^{\pi}\Big{]}+r_{\tt
max}\Big{(}1+\frac{8e^{-B\mu_{\tt min}/4}}{\mu_{\tt min}^{2}}\Big{)},$
$\displaystyle\leq\Big{(}\frac{\mathbb{E}[\sum_{n=1}^{n_{0}(B)}R_{n}^{\pi}]}{\mathbb{E}[\sum_{n=1}^{n_{0}(B)}X_{n}^{\pi}]}-r(\mathbf{p}^{*})\Big{)}\cdot\mathbb{E}\Big{[}\sum_{n=1}^{n_{0}(B)}X_{n}^{\pi}\Big{]}$
$\displaystyle\quad+r_{\tt max}\Big{(}1+\frac{8e^{-B\mu_{\tt min}/4}}{\mu_{\tt
min}^{2}}\Big{)},$
$\displaystyle\leq\Big{(}\frac{\mathbb{E}[\sum_{n=1}^{n_{0}(B)}R_{n}^{\pi}]}{\mathbb{E}[\sum_{n=1}^{n_{0}(B)}X_{n}^{\pi}]}-r(\mathbf{p}^{*})\Big{)}\cdot\frac{2B}{\mu_{\tt
min}}+r_{\tt max}\Big{(}1+\frac{8e^{-B\mu_{\tt min}/4}}{\mu_{\tt
min}^{2}}\Big{)}.$ (40)

For a causal policy $\pi$ that satisfies the constraint, we have

$\displaystyle 0\geq B\cdot D^{\pi}(B)$
$\displaystyle=\mathbb{E}\Big{[}\sum_{n=1}^{N^{\pi}(B)}Y_{n}^{\pi}\Big{]}-Bc$
$\displaystyle\geq\mathbb{E}\Big{[}\sum_{n=1}^{N^{\pi}(B)}(Y_{n}^{\pi}-cX_{n}^{\pi})\Big{]}$

Then, using the fact that $|Y_{n}^{\pi}-cX_{n}^{\pi}|\leq 1$ and equation
(39), we can bound the constraint-violation as follows:

$\displaystyle\mathbb{E}\Big{[}\sum_{n=1}^{n_{0}(B)}(Y_{n}^{\pi}-cX_{n}^{\pi})\Big{]}\leq\frac{8e^{-B\mu_{\tt
min}/4}}{\mu_{\tt min}^{2}}.$

Reorganizing the terms and using the fact that
$\mathbb{E}[X_{n}^{\pi}]\geq\mu_{\tt min},\forall n$, we have,

$\displaystyle\frac{\mathbb{E}[\sum_{n=1}^{n_{0}(B)}Y_{n}^{\pi}]}{\mathbb{E}[\sum_{n=1}^{n_{0}(B)}X_{n}^{\pi}]}$
$\displaystyle\leq c+\frac{4e^{-B\mu_{\tt min}/4}}{B\mu_{\tt min}^{2}}.$ (41)

We will optimize the finite-time performance (i.e., maximize the RHS of (40))
over all $\pi\in\Pi$ subject to (41) to show that $\pi^{*}$ has a bounded
optimality gap.

Consider the following optimization problem: —s—
π∈ΠE[∑n=1n0(B)Rnπ]E[∑n=1n0(B)Xnπ] E[∑n=1n0(B)Ynπ]E[∑n=1n0(B)Xnπ]≤c+
4e-Bμmin/4Bμmin2.

It is shown in Lemma 1 in (Neely 2012) that there is an optimal stationary
randomized policy $\pi(\mathbf{p})$ for the optimization problem above. Thus,
by letting

$\displaystyle{\mathbf{p}}_{\tt
per}^{*}(B)\in\underset{\mathbf{p}\in\Delta_{K}}{\arg\max}~{}\Big{\\{}r(\mathbf{p}):y(\mathbf{p})\leq
c+\frac{4e^{-B\mu_{\tt min}/4}}{B\mu_{\tt min}^{2}}.\Big{\\}},$

$r\big{(}{\mathbf{p}}_{\tt per}^{*}(B)\big{)}$ is the optimum value of the
optimization problem above. From (40), the optimality gap grows linearly in
$B$ at a rate $r\big{(}{\mathbf{p}}_{\tt
per}^{*}(B)\big{)}-r(\mathbf{p}^{*})$. Using sensitivity analysis for Linear
Fractional Programming (Bitran and Magnanti 1976; Bonnans and Shapiro 2000)
with constraint perturbation $\epsilon=\frac{4e^{-B\mu_{\tt min}/4}}{B\mu_{\tt
min}^{2}}$, we have $r\big{(}\mathbf{p}^{*}_{\tt
per}(B)\big{)}-r(\mathbf{p}^{*})\leq O(c^{\prime}\epsilon)$ for some constant
$c^{\prime}$. Substituting this result into (40), we have:

$\mathbb{E}[{\tt REW}^{\pi}(B)]-\mathbb{E}[{\tt REW}^{\pi^{*}}(B)]\leq
O\Big{(}\frac{8c^{\prime}e^{-B\mu_{\tt min}/4}}{\mu_{\tt
min}^{3}}\Big{)}+r_{\tt max}\Big{(}1+\frac{8e^{-B\mu_{\tt min}/4}}{\mu_{\tt
min}^{2}}\Big{)},$ (42)

which implies ${\tt REG}^{\pi^{*}}(B)\leq r_{\tt max}+e^{-\Omega(B)}=O(1)$.

#### (Bounding the constraint-violation)

By the upper bound in Proposition 4, under any stationary randomized policy
$\pi(\mathbf{p})$, we have:

$\frac{1}{B}\mathbb{E}\Bigg{[}\sum_{n=1}^{N^{\pi(\mathbf{p})}(B)}Y_{n}^{\pi(\mathbf{p})}\Bigg{]}\leq
y(\mathbf{p})\Big{(}1+\frac{1}{B\mu_{\tt min}^{2}}\Big{)},$

By definition, we have $y(\mathbf{p}^{*})\leq c$. Substituting this into the
above inequality, we obtain:

$\displaystyle\frac{1}{B}\mathbb{E}\Bigg{[}\sum_{n=1}^{N^{\pi^{*}}(B)}Y_{n}^{\pi^{*}}\Bigg{]}\leq
c+\frac{c}{B\mu_{\tt min}^{2}},$

which implies $D^{\pi^{*}}(B)\leq\frac{c}{B\mu_{\tt min}^{2}}=O(\frac{1}{B})$.
∎

##  Appendix D Performance Bounds for Offline Lyapunov Policy

######  Proposition 5 (Drift-Minimizing Policy is Deterministic).

For any $n\geq 1$, under $\mathcal{F}_{n-1}$, let

$\displaystyle\Psi_{n}(k,Q_{n})$
$\displaystyle=-V\frac{\mathbb{E}[R_{n,k}]}{\mathbb{E}[X_{n,k}]}+Q_{n}\frac{\mathbb{E}[Y_{n,k}]}{\mathbb{E}[X_{n,k}]}$
(43) $\displaystyle k_{n}$
$\displaystyle=\arg\min_{k\in\mathbb{K}}~{}\Psi_{n}(k,Q_{n})$ (44)

Then, $\mathbf{q}_{n}^{{\pi_{\tt LyOff}}}=\mathbb{I}\\{k=k_{n}\\}$ is a
solution to (12), i.e., $\mathbf{q}_{n}^{{\pi_{\tt
LyOff}}}\in\arg\min_{\mathbf{q}\in\Delta_{K}}~{}\Psi_{n}(Q_{n}^{\pi(\mathbf{q})})$.
Thus, $I_{n}^{{\pi_{\tt LyOff}}}=k_{n}$ for all $n\geq 1$ and
$Q_{n}^{{\pi_{\tt LyOff}}}$ is updated according to (9) under ${\pi_{\tt
LyOff}}$.

###### Proof.

For $\mathbf{q}_{n}\in\mathcal{F}_{n-1}$, since $\mathbb{E}[X_{n,k}]>0,\forall
n,k$,

$\displaystyle\Psi_{n}(Q_{n}^{\pi(\mathbf{q_{n}})})$
$\displaystyle=\frac{\sum_{k=1}^{K}q_{n,k}\Big{(}-V\mathbb{E}[R_{n,k}]+Q_{n}\cdot\mathbb{E}[Y_{n,k}]\Big{)}}{\sum_{k=1}^{K}q_{n,k}\mathbb{E}[X_{n,k}]}$
$\displaystyle=\frac{\sum_{k=1}^{K}q_{n,k}\mathbb{E}[X_{n,k}]\frac{-V\mathbb{E}[R_{n,k}]+Q_{n}\cdot\mathbb{E}[Y_{n,k}]}{\mathbb{E}[X_{n,k}]}}{\sum_{k=1}^{K}q_{n,k}\mathbb{E}[X_{n,k}]}$
$\displaystyle\geq\frac{\min_{k\in\mathbb{K}}\Big{\\{}\frac{-V\mathbb{E}[R_{n,k}]+Q_{n}\cdot\mathbb{E}[Y_{n,k}]}{\mathbb{E}[X_{n,k}]}\Big{\\}}\cdot\sum_{k=1}^{K}q_{n,k}\mathbb{E}[X_{n,k}]}{\sum_{k=1}^{K}q_{n,k}\mathbb{E}[X_{n,k}]}$
$\displaystyle\geq\min_{k\in\mathbb{K}}\Big{\\{}\frac{(-V\mathbb{E}[R_{n,k}]+Q_{n}\cdot\mathbb{E}[Y_{n,k}])}{\mathbb{E}[X_{n,k}]}\Big{\\}}$

Therefore, $q_{n,k}^{{\pi_{\tt LyOff}}}=\mathbb{I}\\{k=k_{n}\\}$ is a solution
to (12). ∎

######  Lemma 3 (First-order drift bounds for $Q_{n}$).

Under Assumption 1, let there be an $\epsilon$-Slater arm for with
$\epsilon>0$. Let

$\displaystyle l^{*}=\frac{Vr_{\tt max}}{\epsilon}$

Then, under ${\pi_{\tt LyOff}}$, we have the following bound:

$\mathbb{E}\Bigg{[}\Big{(}Q_{n+1}^{\pi_{\tt LyOff}}-Q_{n}^{\pi_{\tt
LyOff}}\Big{)}\mathbb{I}\\{Q_{n}^{\pi_{\tt LyOff}}\geq
l^{*}\\}\Big{|}\mathcal{F}_{n-1}^{\pi_{\tt LyOff}}\Bigg{]}\leq-\epsilon.$ (45)

###### Proof.

We will skip the superscript ${\pi_{\tt LyOff}}$ for $Q_{n}$ in the proof. For
$\tt LyOff$ policy, the first order statistics for all random variables are
assumed to be known.

Assume arm $k$ satisfies $\epsilon$-Slater condition with $\epsilon>0$, i.e.
$\mathbb{E}[Y_{n,k}-cX_{n,k}]\leq-\epsilon$. Under $\mathcal{F}_{n-1}$,
$Q_{n}$ is given. We will show that if arm $k^{\prime}$ has
$\mathbb{E}[Y_{n,k^{\prime}}-cX_{n,k^{\prime}}]\geq 0$, then
$\Psi_{n}(k^{\prime},Q_{n})-\Psi_{n}(k,Q_{n})\geq 0$ for $Q_{n}\geq l^{*}$.

$\displaystyle\Psi_{n}(k^{\prime},Q_{n})-\Psi_{n}(k,Q_{n})$
$\displaystyle=-V\Big{(}\frac{\mathbb{E}[R_{n,k^{\prime}}]}{\mathbb{E}[X_{n,k^{\prime}}]}-\frac{\mathbb{E}[R_{n,k}]}{\mathbb{E}[X_{n,k}]}\Big{)}+Q_{n}\Big{(}\frac{\mathbb{E}[Y_{n,k^{\prime}}]}{\mathbb{E}[X_{n,k^{\prime}}]}-\frac{\mathbb{E}[Y_{n,k}]}{\mathbb{E}[X_{n,k}]}\Big{)}$

$\displaystyle
V\Big{(}\frac{\mathbb{E}[R_{n,k^{\prime}}]}{\mathbb{E}[X_{n,k^{\prime}}]}-\frac{\mathbb{E}[R_{n,k}]}{\mathbb{E}[X_{n,k}]}\Big{)}\leq
Vr_{\tt max}$

$\displaystyle
Q_{n}\Big{(}\frac{\mathbb{E}[Y_{n,k^{\prime}}]}{\mathbb{E}[X_{n,k^{\prime}}]}-\frac{\mathbb{E}[Y_{n,k}]}{\mathbb{E}[X_{n,k}]}\Big{)}\geq
Q_{n}\Big{(}c-c+\frac{\epsilon}{\mathbb{E}[X_{n,k}]}\Big{)}\geq Q_{n}\epsilon$

Therefore, when $Q_{n}\geq\frac{Vr_{\tt max}}{\epsilon}$,

$\displaystyle\Psi_{n}(k^{\prime},Q_{n})-\Psi_{n}(k,Q_{n})\geq\frac{Vr_{\tt
max}}{\epsilon}\cdot\epsilon-Vr_{\tt max}\geq 0$ (46)

From Proposition 5, the drift-minimizing policy is deterministic in the
offline setting. So $k_{n}=\arg\min_{k\in\mathbb{K}}\Psi_{n}(k,Q_{n})$ will
satisfy the $\epsilon-$Slater condition. Then

$\displaystyle\mathbb{E}\big{[}\big{(}Q_{n+1}-Q_{n}\big{)}\mathbb{I}\\{Q_{n}\geq
l^{*}\\}\big{|}\mathcal{F}_{n-1}\big{]}$
$\displaystyle=\mathbb{E}[Y_{n,k_{n}}-cX_{n,k_{n}}]\leq-\epsilon$ (47)

∎

######  Lemma 4 (Lyapunov Drift).

For a causal policy $\pi$, define the Lyapunov function
$L(q)=\frac{1}{2}q^{2}$ and the Lyapunov drift

$\displaystyle\Delta(Q_{n}^{\pi})=\mathbb{E}[L(Q_{n+1}^{\pi})-L(Q_{n}^{\pi})|\mathcal{F}_{n-1}^{\pi}].$

Then, under $\mathcal{F}_{n-1}^{\pi}$,

$\displaystyle\Delta(Q_{n}^{\pi})\leq
V\mathbb{E}[R_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}]+\frac{\sigma^{2}}{2}+\frac{\delta^{2}}{2}+\delta+\mathbb{E}\big{[}X_{n}^{\pi}\big{|}\mathcal{F}_{n-1}^{\pi}\big{]}\big{(}\Psi_{n}(Q_{n}^{\pi})-cQ_{n}^{\pi}+\delta
Q_{n}^{\pi}\big{)}$

where $\Psi_{n}(Q_{n}^{\pi})$ is defined in Definition 5.

###### Proof.

By definition,
$Q_{n+1}^{\pi}=\max\big{\\{}0,Q_{n}^{\pi}+Y_{n}^{\pi}-(c-\delta)X_{n}^{\pi}\big{\\}}$.
Under $\mathcal{F}_{n-1}^{\pi}$, $Q_{n}^{\pi}$ is given.

$\displaystyle(Q_{n+1}^{\pi})^{2}$
$\displaystyle\leq(Q_{n}^{\pi}+Y_{n}^{\pi}-(c-\delta)X_{n}^{\pi})^{2}$
$\displaystyle=(Q_{n}^{\pi})^{2}+(Y_{n}^{\pi}-(c-\delta)X_{n}^{\pi})^{2}+2Q_{n}^{\pi}(Y_{n}^{\pi}-(c-\delta)X_{n}^{\pi})$

Therefore,

$\displaystyle\Delta(Q_{n}^{\pi})$
$\displaystyle=\mathbb{E}[L(Q_{n+1}^{\pi})-L(Q_{n}^{\pi})|\mathcal{F}_{n-1}^{\pi}]$
$\displaystyle\leq\frac{1}{2}\big{(}\mathbb{E}[(Y_{n}^{\pi}-(c-\delta)X_{n}^{\pi})^{2}|\mathcal{F}_{n-1}^{\pi}]+2\mathbb{E}[Q_{n}^{\pi}(Y_{n}^{\pi}-(c-\delta)X_{n}^{\pi})|\mathcal{F}_{n-1}^{\pi}]\big{)}$
$\displaystyle\leq\frac{\sigma^{2}}{2}+\frac{\delta^{2}}{2}+\delta+\mathbb{E}[Q_{n}^{\pi}(Y_{n}^{\pi}-(c-\delta)X_{n}^{\pi})|\mathcal{F}_{n-1}^{\pi}]$

Subtracting $-V\mathbb{E}[R_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}]$ on both sides,

$\displaystyle\Delta(Q_{n}^{\pi})-V\mathbb{E}[R_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}]$
$\displaystyle\leq$
$\displaystyle\frac{\sigma^{2}}{2}+\frac{\delta^{2}}{2}+\delta+\mathbb{E}[-VR_{n}^{\pi}+Q_{n}^{\pi}Y_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}]-\mathbb{E}[Q_{n}^{\pi}(cX_{n}^{\pi})|\mathcal{F}_{n-1}]+\mathbb{E}[Q_{n}^{\pi}(\delta
X_{n}^{\pi})|\mathcal{F}_{n-1}^{\pi}]$ $\displaystyle=$
$\displaystyle\frac{\sigma^{2}}{2}+\frac{\delta^{2}}{2}+\delta+\mathbb{E}\big{[}X_{n}^{\pi}\big{|}\mathcal{F}_{n-1}^{\pi}\big{]}\Big{(}\frac{-V\mathbb{E}\big{[}R_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}]+Q_{n}^{\pi}\cdot\mathbb{E}[Y_{n}^{\pi}\big{|}\mathcal{F}_{n-1}^{\pi}\big{]}}{\mathbb{E}\big{[}X_{n}^{\pi}\big{|}\mathcal{F}_{n-1}^{\pi}\big{]}}-cQ_{n}^{\pi}+\delta
Q_{n}^{\pi}\Big{)}$ $\displaystyle=$
$\displaystyle\frac{\sigma^{2}}{2}+\frac{\delta^{2}}{2}+\delta+\mathbb{E}\big{[}X_{n}^{\pi}\big{|}\mathcal{F}_{n-1}^{\pi}\big{]}\big{(}\Psi_{n}(Q_{n}^{\pi})-cQ_{n}^{\pi}+\delta
Q_{n}^{\pi}\big{)}$

Moving $V\mathbb{E}[R_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}]$ to the right hand
side, we get the results. ∎

###  D.1 Proof of Proposition 2

###### Proof.

For notation simplicity, in the proof, we will use $\pi$ to represent
${\pi_{\tt LyOff}}$ and use $\pi^{*}$ and
$\mathbf{p}^{*}=(p_{1}^{*},p_{2}^{*},\ldots,p_{K}^{*})$ to represent the
optimal stationary randomized policy (Definition 4).

Under ${\pi_{\tt LyOff}}$, recall that
$\Psi_{n}(k,Q_{n}^{\pi})=-V\frac{\mathbb{E}[R_{n,k}]}{\mathbb{E}[X_{n,k}]}+Q_{n}^{\pi}\frac{\mathbb{E}[Y_{n,k}]}{\mathbb{E}[X_{n,k}]}$.
At each step $n$, $k_{n}=\arg\min_{k\in\mathbb{K}}\Psi_{n}(k,Q_{n}^{\pi})$.
From Lemma 4,

$\displaystyle\Delta(Q_{n}^{\pi})-V\mathbb{E}[R_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}]$
$\displaystyle\leq$
$\displaystyle\frac{\sigma^{2}}{2}+\frac{\delta^{2}}{2}+\delta+\mathbb{E}\big{[}X_{n}^{\pi}\big{|}\mathcal{F}_{n-1}^{\pi}\big{]}\big{(}\Psi_{n}(Q_{n}^{\pi})-cQ_{n}^{\pi}+\delta
Q_{n}^{\pi}\big{)}$ $\displaystyle=$
$\displaystyle\frac{\sigma^{2}}{2}+\frac{\delta^{2}}{2}+\delta+\mathbb{E}\big{[}X_{n}^{\pi}\big{|}\mathcal{F}_{n-1}^{\pi}\big{]}\big{(}\Psi_{n}(k_{n},Q_{n}^{\pi})-cQ_{n}^{\pi}+\delta
Q_{n}^{\pi}\big{)}$ $\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$
$\displaystyle\frac{\sigma^{2}}{2}+\frac{\delta^{2}}{2}+\delta+\mathbb{E}\big{[}X_{n}^{\pi}\big{|}\mathcal{F}_{n-1}^{\pi}\big{]}\big{(}\Psi_{n}(Q_{n}^{\pi(\mathbf{p}^{*})})-cQ_{n}^{\pi}+\delta
Q_{n}^{\pi}\big{)}$ $\displaystyle=$
$\displaystyle\frac{\sigma^{2}}{2}+\frac{\delta^{2}}{2}+\delta+\mathbb{E}\big{[}X_{n}^{\pi}\big{|}\mathcal{F}_{n-1}^{\pi}\big{]}\Big{(}\frac{-V\sum_{k=1}^{K}p_{k}^{*}\mathbb{E}[R_{n,k}]}{\sum_{k=1}^{K}p_{k}^{*}\mathbb{E}[X_{n,k}]}+\frac{Q_{n}^{\pi}\sum_{k=1}^{K}p_{k}^{*}\mathbb{E}[Y_{n,k}]}{\sum_{k=1}^{K}p_{k}^{*}\mathbb{E}[X_{n,k}]}-cQ_{n}^{\pi}+\delta
Q_{n}^{\pi}\Big{)}$ $\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}$
$\displaystyle\frac{\sigma^{2}}{2}+\frac{\delta^{2}}{2}+\delta+\mathbb{E}\big{[}X_{n}^{\pi}\big{|}\mathcal{F}_{n-1}^{\pi}\big{]}\big{(}-Vr(p^{*})+cQ_{n}^{\pi}-cQ_{n}^{\pi}+\delta
Q_{n}^{\pi}\big{)}$ $\displaystyle=$
$\displaystyle\frac{\sigma^{2}}{2}+\frac{\delta^{2}}{2}+\delta+\mathbb{E}\big{[}X_{n}^{\pi}\big{|}\mathcal{F}_{n-1}^{\pi}\big{]}\big{(}-Vr(p^{*})+\delta
Q_{n}^{\pi}\big{)}$

where (a) is using Proposition 5 and (b) is using the definition of $\pi^{*}$
(Definition 4).

Taking expectation on both sides, since $X_{n}^{\pi}\leq 1$,

$\displaystyle\mathbb{E}[L(Q_{n+1}^{\pi})]-\mathbb{E}[L(Q_{n}^{\pi})]$
$\displaystyle\leq\frac{\sigma^{2}}{2}+\frac{\delta^{2}}{2}+\delta+V\mathbb{E}[R_{n}^{\pi}]-V\mathbb{E}[X_{n}^{\pi}]r(p^{*})+\delta\mathbb{E}[Q_{n}^{\pi}]$

Taking telescoping sum from $N$ to $0$,

$\displaystyle\mathbb{E}[L(Q_{N}^{\pi})]-\mathbb{E}[L(Q_{0}^{\pi})]$
$\displaystyle\leq\frac{N\sigma^{2}}{2}+\frac{N\delta^{2}}{2}+N\delta+V\sum_{n=1}^{N}\mathbb{E}[R_{n}^{\pi}]$
$\displaystyle\quad-V\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}]r(p^{*})+\delta\sum_{n=1}^{N}\mathbb{E}[Q_{n}^{\pi}]$

Rearrange the terms, since
$\mathbb{E}[L(Q_{N}^{\pi})]-\mathbb{E}[L(Q_{0}^{\pi})]\geq 0$

$\displaystyle\frac{\sum_{n=1}^{N}\mathbb{E}[R_{n}^{\pi}]}{\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}]}\geq
r(p^{*})-\frac{N\sigma^{2}+N\delta^{2}}{2V\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}]}-\frac{N\delta}{V\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}]}-\frac{\delta\sum_{n=1}^{N}\mathbb{E}[Q_{n}^{\pi}]}{V\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}]}$

Let $N=n_{0}(B)=\lceil 2B/\mu_{\tt min}\rceil$,

$\displaystyle\frac{\mathbb{E}[\sum_{n=1}^{n_{0}(B)}R_{n}^{\pi}]}{\mathbb{E}[\sum_{n=1}^{n_{0}(B)}X_{n}^{\pi}]}$
$\displaystyle\geq
r(p^{*})-\frac{n_{0}(B)(\sigma^{2}+\delta^{2})}{2Vn_{0}(B)\mu_{\tt
min}}-\frac{n_{0}(B)\delta}{Vn_{0}(B)\mu_{\tt
min}}-\frac{\delta\sum_{n=1}^{n_{0}(B)}\mathbb{E}[Q_{n}^{\pi}]}{Vn_{0}(B)\mu_{\tt
min}}$ $\displaystyle\geq
r(p^{*})-\frac{\sigma^{2}+\delta^{2}+2\delta}{2V\mu_{\tt
min}}-\frac{\delta\sum_{n=1}^{n_{0}(B)}\mathbb{E}[Q_{n}^{\pi}]}{Vn_{0}(B)\mu_{\tt
min}}$

Using the decomposition for regret (Lemma 1),

$\displaystyle\mathbb{E}[{\tt REW}^{\pi^{*}}(B)]-\mathbb{E}[{\tt
REW}^{\pi}(B)]$
$\displaystyle\leq\Big{(}r(p^{*})-\frac{\mathbb{E}[\sum_{n=1}^{n_{0}(B)}R_{n}^{\pi}]}{\mathbb{E}[\sum_{n=1}^{n_{0}(B)}X_{n}^{\pi}]}\Big{)}\cdot\frac{2B}{\mu_{\tt
min}}+\frac{r_{\tt max}}{\mu_{\tt min}^{2}}\Big{(}1+8e^{-B\mu_{\tt
min}/4}\Big{)}$
$\displaystyle\leq\frac{B(\sigma^{2}+\delta^{2}+2\delta)}{2V\mu_{\tt
min}^{2}}+\frac{\delta\sum_{n=1}^{n_{0}(B)}\mathbb{E}[Q_{n}^{\pi}]}{V\mu_{\tt
min}}+\frac{r_{\tt max}}{\mu_{\tt min}^{2}}\Big{(}1+8e^{-B\mu_{\tt
min}/4}\Big{)}$ (48)

Using the definition
$Q_{n+1}=\max\big{\\{}0,Q_{n}+Y_{n}-(c-\delta)X_{n}\big{\\}}$,

$\displaystyle Q_{n+1}\geq Q_{n}+Y_{n}-(c-\delta)X_{n}$

Taking telescoping sum from $N$ to $0$,

$\displaystyle\sum_{n=1}^{N}Y_{n}-(c-\delta)\sum_{n=1}^{N}X_{n}\leq Q_{N}$

Taking expectation on both sides, under ${\pi_{\tt LyOff}}$

$\displaystyle\sum_{n=1}^{N}\mathbb{E}[Y_{n}^{\pi}]-(c-\delta)\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}]\leq\mathbb{E}[Q_{N}^{\pi}]$

Let $n=n_{0}(B)$,

$\displaystyle\frac{\mathbb{E}\Big{[}\sum_{n=1}^{n_{0}(B)}Y_{n}^{\pi}\Big{]}}{\mathbb{E}\Big{[}\sum_{n=1}^{n_{0}(B)}X_{n}^{\pi}\Big{]}}-c\leq\frac{\mathbb{E}[Q_{n_{0}(B)}^{\pi}]}{\sum_{n=1}^{n_{0}(B)}\mathbb{E}[X_{i}^{\pi}]}-\delta\leq\frac{\mathbb{E}[Q_{n_{0}(B)}^{\pi}]}{n_{0}(B)\mu_{\tt
min}}-\delta$

Using the decomposition for constraint-violation (Lemma 2),

$\displaystyle D^{\pi}(B)$
$\displaystyle\leq\frac{\mathbb{E}[Q_{n_{0}(B)}]}{n_{0}(B)\mu_{\tt
min}}\cdot\frac{2}{\mu_{\tt min}}-\frac{2\delta}{\mu_{\tt min}}+\frac{8(y_{\tt
max}-c)}{B\mu_{\tt min}^{2}}e^{-B\mu_{\tt min}/4}+\frac{1}{B}$
$\displaystyle\leq\frac{\mathbb{E}[Q_{n_{0}(B)}]}{B\mu_{\tt
min}}-\frac{2\delta}{\mu_{\tt min}}+\frac{8(y_{\tt max}-c)}{B\mu_{\tt
min}^{2}}e^{-B\mu_{\tt min}/4}+\frac{1}{B}$ (49)

Let $l^{*}=\frac{Vr_{\tt max}}{\epsilon}$, from Theorem 2.3 in (Hajek 1982)
and Lemma 3, for any $n$ and $z>l^{*}$, $\mathbb{P}[Q_{n}^{\pi}>z]\leq
ae^{-\eta z}$ with some $\eta>0$ . Therefore,

$\displaystyle\mathbb{E}[Q_{n}^{\pi}]$
$\displaystyle=\mathbb{E}[Q_{n}^{\pi}\mathbb{I}(Q_{n}^{\pi}<l^{*})]+\int_{l^{*}}^{\infty}\mathbb{P}(Q_{n}^{\pi}>z)dz+l^{*}\mathbb{P}(X>l^{*})$
$\displaystyle\leq l^{*}+\int_{z_{0}}^{\infty}ae^{-\eta z}dz+l^{*}ae^{-\eta
l^{*}}$ $\displaystyle=\frac{Vr_{\tt max}}{\epsilon}+\frac{Vr_{\tt
max}}{\eta\epsilon}ae^{-\eta l^{*}}+\frac{Vr_{\tt max}}{\epsilon}ae^{-\eta
l^{*}}$ $\displaystyle=O\Big{(}\frac{Vr_{\tt max}}{\epsilon}\Big{)}$ (50)

Therefore, combining (48), (49) and (50),

$\displaystyle\mathbb{E}[{\tt REW}^{\pi^{*}}(B)]-\mathbb{E}[{\tt
REW}^{\pi}(B)]=O\Bigg{(}\frac{\sigma^{2}B}{V\mu_{\tt min}^{2}}+\frac{\delta
r_{\tt max}B}{\epsilon\mu_{\tt min}^{2}}\Bigg{)}.$ (51)

$\displaystyle D^{\pi}(B)=O\Big{(}\frac{1}{B}+\frac{Vr_{\tt max}}{B\mu_{\tt
min}\epsilon}-\frac{\delta}{\mu_{\tt min}}\Big{)}.$ (52)

The results in Proposition 2 follows by the asymptotic optimality of $\pi^{*}$
(Proposition 1). ∎

##  Appendix E Performance Bounds for Online Lyapunov Policy

###  E.1 Preliminary Results

######  Lemma 5 (Bounds for $\Psi_{n}$ under ${\pi_{\tt LyOn}}$).

Let

$A_{n}^{\pi}=\bigcap_{t=1}^{n}\bigcap_{k\in\mathbb{K}}\Big{\\{}\big{|}\widehat{r}_{t,k}^{\pi}-r_{k}\big{|}\leq{\tt
rad}_{k}(n,\alpha)\frac{1+r_{k}}{\mathbb{E}[X_{1,k}]}\Big{\\}}\bigcap\Big{\\{}\big{|}\widehat{y}_{t,k}^{\pi}-y_{k}\big{|}\leq{\tt
rad}_{k}(n,\alpha)\frac{1+y_{k}}{\mathbb{E}[X_{1,k}]}\Big{\\}},$ (53)

be the high-probability event (Lemma 2 in (Cayci, Gupta, and Eryilmaz 2020))
under policy ${\pi_{\tt LyOn}}$. Then, given $Q_{n}$,

$\mathbb{I}_{A_{n-1}^{\pi_{\tt LyOn}}}\cdot\Big{(}\Psi_{n}({I_{n}^{\pi_{\tt
LyOn}}},Q_{n})-\Psi_{n}(k_{n},Q_{n})\Big{)}\leq 2{\tt rad}_{I_{n}^{\pi_{\tt
LyOn}}}(n,\alpha)\cdot\Big{(}\frac{V(1+r_{\tt max})}{\mu_{\tt
min}}+\frac{Q_{n}(1+y_{\tt max})}{\mu_{\tt min}}\Big{)},$ (54)

where $k_{n}=\arg\min_{k}\Psi_{n}(k,Q_{n})$. Moreover, we have the following
bound:

$\mathbb{I}_{\big{(}A_{n-1}^{\pi_{\tt
LyOn}}\big{)}^{c}}\Big{(}\Psi_{n}({I_{n}^{\pi_{\tt
LyOn}}},Q_{n})-\Psi_{n}(k_{n},Q_{n})\Big{)}\leq Vr_{\tt max}+n(1+y_{\tt
max}).$ (55)

###### Proof.

For simplicity, let

$\nu_{n}(V,Q_{n})=\Big{(}\frac{V(1+r_{\tt max})}{\mu_{\tt
min}}+\frac{Q_{n}(1+y_{\tt max})}{\mu_{\tt min}}\Big{)}.$

Assume that $A_{n-1}^{\pi_{\tt LyOn}}$ holds, and $I_{n}^{\pi_{\tt LyOn}}=k$
such that

$\Psi_{n}(k,Q_{n})>\Psi_{n}(k_{n},Q_{n})+2{\tt
rad}_{k}(n,\alpha)\cdot\nu_{n}(V,Q_{n}).$

Then, given $Q_{n}$, we have the following:

$\displaystyle\begin{aligned} \widehat{\Psi}_{n}(k_{n},Q_{n})-{\tt
rad}_{k_{n}}(n,\alpha)\cdot\nu_{n}(V,Q_{n})&\leq\Psi_{n}(k_{n},Q_{n}),\\\
&\leq\Psi_{n}(k,Q_{n})-2{\tt rad}_{k}(n,\alpha)\cdot\nu_{n}(V,Q_{n}),\\\
&\leq\widehat{\Psi}_{n}(k,Q_{n})-{\tt
rad}_{k}(n,\alpha)\cdot\nu_{n}(V,Q_{n}),\end{aligned}$ (56)

since $\widehat{r}_{n,k}$ and $\widehat{y}_{n,k,m}$ (thus
$\widehat{\Psi}_{n}(k,Q_{n}),\forall k\in\mathbb{K}$) are concentrated around
the true values in the event $A_{n-1}^{\pi_{\tt LyOn}}$. (56) is a
contradiction since we assumed $I_{n}^{\pi_{\tt LyOn}}=k$ but
$k_{n}=\arg\min_{k}\Psi_{n}(k,Q_{n})$ is a more favorable choice, which
concludes the proof of the first part.

For the second part, note that $Q_{n}\leq n$ for all $n$ since $Y_{n,k}\leq 1$
almost surely for all $n,k,m$. Therefore, pessimistic upper and lower bounds
on $\Psi_{n}(k,Q_{n})$ yield the result. ∎

######  Lemma 6 (First-order drift bounds for $Q_{n}$).

Under Assumption 1, let there be an $\epsilon$-Slater arm for some
$\epsilon>0$. Let

$\displaystyle l^{*}=\frac{2Vr_{\tt max}}{\epsilon}+\frac{V(1+r_{\tt
max})}{1+y_{\tt max}}.$

Then, under LyOn, we have the following bound for some $\epsilon_{0}>0$:

$\mathbb{E}\Bigg{[}\Big{(}Q_{n+1}^{\pi_{\tt LyOn}}-Q_{n}^{\pi_{\tt
LyOn}}\Big{)}\mathbb{I}_{A_{n-1}^{\pi_{\tt LyOn}}}\mathbb{I}\\{Q_{n}^{\pi_{\tt
LyOn}}\geq l^{*}\\}\Big{|}\mathcal{F}_{n-1}^{\pi_{\tt
LyOn}}\Bigg{]}\leq-\epsilon_{0}.$ (57)

###### Proof.

Since under $\mathcal{F}_{n-1}^{\pi_{\tt LyOn}}$, $Q_{n}^{\pi_{\tt LyOn}}$ is
given, we will skip the superscript for $Q_{n}$ in the proof.

From Lemma 5, if $A_{n-1}^{\pi_{\tt LyOn}}$ holds,

$\displaystyle\Big{(}\Psi_{n}(I_{n}^{\pi_{\tt
LyOn}},Q_{n})-\Psi_{n}(k_{n},Q_{n})\Big{)}\leq 2{\tt rad}_{I_{n}^{\pi_{\tt
LyOn}}}(n,\alpha)\cdot\Big{(}\frac{V(1+r_{\tt max})}{\mu_{\tt
min}}+\frac{Q_{n}(1+y_{\tt max})}{\mu_{\tt min}}\Big{)}$

Then using the definition of $\Psi_{n}$, if $Q_{n}\geq\frac{Vr_{\tt
max}}{\epsilon}$, we have

$\displaystyle Q_{n}\frac{\mathbb{E}[Y_{n,I_{n}^{\pi_{\tt
LyOn}}}]}{\mathbb{E}[X_{n,I_{n}^{\pi_{\tt LyOn}}}]}$ $\displaystyle\leq
V\frac{\mathbb{E}[R_{n,I_{n}^{\pi_{\tt
LyOn}}}]}{\mathbb{E}[X_{n,I_{n}^{\pi_{\tt
LyOn}}}]}-V\frac{\mathbb{E}[R_{n,k_{n}}]}{\mathbb{E}[X_{n,k_{n}}]}+Q_{n}\frac{\mathbb{E}[Y_{n,k_{n}}]}{\mathbb{E}[X_{n,k_{n}}]}$
$\displaystyle\quad+2{\tt rad}_{I_{n}^{\pi_{\tt
LyOn}}}(n,\alpha)\cdot\Big{(}\frac{V(1+r_{\tt max})}{\mu_{\tt
min}}+\frac{Q_{n}(1+y_{\tt max})}{\mu_{\tt min}}\Big{)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}Vr_{\tt
max}+Q_{n}c-Q_{n}\epsilon+2{\tt rad}_{I_{n}^{\pi_{\tt
LyOn}}}(n,\alpha)\cdot\Big{(}\frac{V(1+r_{\tt max})}{\mu_{\tt
min}}+\frac{Q_{n}(1+y_{\tt max})}{\mu_{\tt min}}\Big{)}$ $\displaystyle\leq
Vr_{\tt max}+Q_{n}c-Q_{n}\epsilon+\Big{(}\frac{V(1+r_{\tt max})}{1+y_{\tt
max}}+Q_{n}\Big{)}\frac{\epsilon}{2}$

where (a) is using Lemma 3 that $k_{n}$ satisfies $\epsilon$-Slater condition
when $Q_{n}\geq\frac{Vr_{\tt max}}{\epsilon}$; (b) is using the fact that
initial exploration makes $2{\tt rad}_{I_{n}^{\pi_{\tt
LyOn}}}(n,\alpha)\leq\frac{\epsilon}{2}$.

To satisfy $\mathbb{E}[Y_{n,I_{n}^{\pi_{\tt LyOn}}}]\leq
c\mathbb{E}[X_{n,I_{n}^{\pi_{\tt LyOn}}}]$, let the right-hand-side be less
than $Q_{n}c$, we have

$\displaystyle Q_{n}$ $\displaystyle\geq\frac{2Vr_{\tt
max}}{\epsilon}+\frac{V(1+r_{\tt max})}{1+y_{\tt max}}=l^{*}$ (58)

Therefore, if $A_{n-1}^{\pi_{\tt LyOn}}$ holds, $I_{n}^{\pi_{\tt LyOn}}$ will
satisfy the $\epsilon$-Slater condition when $Q_{n}\geq l^{*}$,

$\mathbb{E}\Big{[}\Big{(}Q_{n+1}^{\pi_{\tt LyOn}}-Q_{n}^{\pi_{\tt
LyOn}}\Big{)}\mathbb{I}_{A_{n-1}^{\pi_{\tt LyOn}}}\mathbb{I}\\{Q_{n}^{\pi_{\tt
LyOn}}\geq l^{*}\\}\Big{|}\mathcal{F}_{n-1}^{\pi_{\tt
LyOn}}\Big{]}\leq-\epsilon_{0}.$ (59)

∎

######  Lemma 7 (Maximal inequality for $Q_{n}^{\pi_{\tt LyOn}}$).

Under Assumption 1, if the problem satisfies the Slater condition with
$\epsilon>0$ and $l^{*}$ defined in Lemma 6, we have the following bound under
${\pi_{\tt LyOn}}$ for any $N>l^{*}$:

$\mathbb{E}\Big{[}\max\limits_{1\leq n\leq N}Q_{n}^{\pi_{\tt
LyOn}}\big{|}\mathcal{F}_{0}\Big{]}=O\big{(}\log(N)+l^{*}+1\big{)}.$ (60)

###### Proof.

This part of proof is inspired by (Hajek 1982) where they bound the hitting-
time with super-martingale properties satisfied at any time. We extend the
setup by allowing super-martingale property only when the queue length is
greater than a threshold. This requires additional effort to decompose the
event as we will see below.

For notation simplicity, we will skip the superscript ${\pi_{\tt LyOn}}$ in
the proof.

From Lemma 6,

$\mathbb{E}\Big{[}\Big{(}Q_{n+1}-Q_{n}\Big{)}\mathbb{I}_{A_{n-1}}\mathbb{I}\\{Q_{n}\geq
l^{*}\\}\Big{|}\mathcal{F}_{n-1}\Big{]}\leq-\epsilon_{0}$ (61)

From concentration inequalities in (Cayci, Eryilmaz, and Srikant 2019),
$\mathbb{P}\Big{(}\big{(}A_{n-1}\big{)}^{c}\Big{)}=O\big{(}\frac{1}{n^{2}}\big{)}$.
Also $\big{|}Q_{n+1}-Q_{n}\big{|}<1$ since we assume $X_{n}$ and $Y_{n}$ are
bounded in $(0,1]$.

For any $0<\eta<\lambda$, then if
$\mathbb{E}\big{[}Q_{n+1}-Q_{n}\big{|}\mathcal{F}_{n-1}\big{]}\leq-\epsilon_{0}$,
$\big{|}Q_{n+1}-Q_{n}\big{|}\leq 1$, we have

$\displaystyle\mathbb{E}\big{[}e^{\eta(Q_{n+1}-Q_{n})}\big{|}\mathcal{F}_{n-1}\big{]}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}1+\eta\mathbb{E}\big{[}Q_{n+1}-Q_{n}\big{|}\mathcal{F}_{n-1}\big{]}+\eta^{2}\sum_{m=2}^{\infty}\frac{\eta^{m-2}}{m!}\mathbb{E}\big{[}\big{|}Q_{n+1}-Q_{n}\big{|}^{m}\big{]}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}1-\epsilon_{0}\eta+\eta^{2}\sum_{m=2}^{\infty}\frac{\lambda^{m-2}}{m!}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{=}}1-\epsilon_{0}\eta+\eta^{2}\frac{e^{\lambda}-1-\lambda}{\lambda^{2}}.$
(62)

where (a) is using Taylor expansion on $e^{\eta(Q_{n+1}-Q_{n})}$ and linearity
of expectation; (b) is using the assumption
$\mathbb{E}[Q_{n+1}-Q_{n}|\mathcal{F}_{n-1}]\leq-\epsilon_{0}$,
$|Q_{n+1}-Q_{n}|\leq 1$ and $\eta<\lambda$; (c) is using Taylor expansion on
$e^{\lambda}$.

If
$0<\eta<\min(\lambda,\frac{\epsilon_{0}\lambda^{2}}{e^{\lambda}-1-\lambda})$,
then
$\rho=1-\epsilon_{0}\eta+\eta^{2}\frac{e^{\lambda}-1-\lambda}{\lambda^{2}}<1$.

We select $\lambda=1$, $\rho=1-\eta\epsilon_{0}+\eta^{2}(e-2)$, and $\eta$
satisfying

$\displaystyle\begin{cases}\eta=\min\big{\\{}1,\frac{\epsilon_{0}}{e-2},\eta^{\prime}\big{\\}}\\\
\eta^{\prime}>0,\;\frac{1}{4}(e^{3\eta^{\prime}}-e^{\eta^{\prime}})<1\end{cases}$
(63)

Using the definition of $\eta$ and $\rho$ above, from (62),

$\displaystyle\mathbb{E}[e^{\eta(Q_{n+1}-Q_{n})}\mathbb{I}\\{Q_{n}\geq
l^{*}\\}\mathbb{I}_{A_{n-1}}|\mathcal{F}_{n-1}]$ $\displaystyle\leq\rho<1$
(64)

Since $|Q_{n+1}-Q_{n}|\leq 1$,

$\displaystyle\mathbb{E}[e^{\eta(Q_{n+1}-Q_{n})}\mathbb{I}\\{Q_{n}<l^{*}\\}|\mathcal{F}_{n-1}]$
$\displaystyle\leq e^{\eta}$ (65)

Then, conditioning on $Q_{n}\geq l^{*}$ and $A_{n}$,

$\displaystyle\mathbb{E}[e^{\eta Q_{n+1}}|\mathcal{F}_{0}]$
$\displaystyle=\mathbb{E}[\mathbb{E}[e^{\eta
Q_{n+1}}|\mathcal{F}_{n-1}]|\mathcal{F}_{0}]$
$\displaystyle=\mathbb{E}[\mathbb{E}[e^{\eta Q_{n+1}}\mathbb{I}\\{Q_{n}\geq
l^{*}\\}+e^{\eta
Q_{n+1}}\mathbb{I}\\{Q_{n}<l^{*}\\}|\mathcal{F}_{n-1}]|\mathcal{F}_{0}]$
$\displaystyle=\mathbb{E}[\mathbb{E}[e^{\eta Q_{n+1}}\mathbb{I}\\{Q_{n}\geq
l^{*}\\}|\mathcal{F}_{n-1}]|\mathcal{F}_{0}]+\mathbb{E}[\mathbb{E}[e^{\eta
Q_{n+1}}\mathbb{I}\\{Q_{n}<l^{*}\\}|\mathcal{F}_{n-1}]|\mathcal{F}_{0}]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\mathbb{E}[\mathbb{E}[e^{\eta
Q_{n+1}}\mathbb{I}\\{Q_{n}\geq
l^{*}\\}\mathbb{I}_{A_{n-1}}|\mathcal{F}_{n-1}]|\mathcal{F}_{0}]$ (66)
$\displaystyle\quad+\mathbb{E}[\mathbb{E}[e^{\eta
Q_{n+1}}\mathbb{I}\\{Q_{n}\geq
l^{*}\\}\mathbb{I}_{(A_{n-1})^{c}}|\mathcal{F}_{n-1}]|\mathcal{F}_{0}]+e^{\eta(l^{*}+1)}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\rho\mathbb{E}[e^{\eta
Q_{n}}|\mathcal{F}_{0}]+\mathbb{E}[\mathbb{E}[e^{\eta
Q_{n+1}}\mathbb{I}\\{Q_{n}\geq
l^{*}\\}\mathbb{I}_{(A_{n-1})^{c}}|\mathcal{F}_{n-1}]|\mathcal{F}_{0}]+e^{\eta(l^{*}+1)}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\rho\mathbb{E}[e^{\eta
Q_{n}}|\mathcal{F}_{0}]+\mathbb{E}[e^{\eta
Q_{n+1}}\mathbb{I}_{(A_{n-1})^{c}}|\mathcal{F}_{0}]+e^{\eta(l^{*}+1)}$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}\rho\mathbb{E}[e^{\eta
Q_{n}}|\mathcal{F}_{0}]+\sqrt{\mathbb{E}[e^{2\eta
Q_{n+1}}|\mathcal{F}_{0}]\cdot\mathbb{E}[\mathbb{I}^{2}_{(A_{n-1})^{c}}|\mathcal{F}_{0}]}+e^{\eta(l^{*}+1)}$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{\leq}}\rho\mathbb{E}[e^{\eta
Q_{n}}|\mathcal{F}_{0}]+\frac{1}{n-1}\sqrt{\mathbb{E}[e^{2\eta
Q_{n+1}}|\mathcal{F}_{0}]}+e^{\eta(l^{*}+1)}$ (67)

where (a) is using inequality (65); (b) is using inequality (64); (c) is upper
bounding $\mathbb{I}\\{Q_{n}\geq l^{*}\\}$ by 1; (d) is using Cauchy-Schwarz
inequality; (e) is using
$\mathbb{E}[\mathbb{I}^{2}_{(A_{n-1})^{c}}|\mathcal{F}_{0}]\leq\frac{1}{(n-1)^{2}}$.

Next we will bound $\mathbb{E}[e^{2\eta Q_{n+1}}|\mathcal{F}_{0}]$. Let
$D=e^{\eta}$, $Z_{n}=e^{\eta Q_{n}}$, then $\mathbb{E}[e^{2\eta
Q_{n+1}}|\mathcal{F}_{0}]=\mathbb{E}[Z_{n+1}^{2}|\mathcal{F}_{0}]$.

Since $|Q_{n+1}-Q_{n}|\leq 1$,

$\displaystyle D^{-1}Z_{n}\leq Z_{n+1}\leq DZ_{n}$ (68)

Since
$Var(Z_{n+1}|\mathcal{F}_{0})=\mathbb{E}[Z_{n+1}^{2}|\mathcal{F}_{0}]-(\mathbb{E}[Z_{n+1}|\mathcal{F}_{0}])^{2}$,

$\displaystyle\frac{\mathbb{E}[Z_{n+1}^{2}|\mathcal{F}_{0}]}{(\mathbb{E}[Z_{n+1}|\mathcal{F}_{0}])^{2}}$
$\displaystyle=1+\frac{Var(Z_{n+1}|\mathcal{F}_{0})}{(\mathbb{E}[Z_{n+1}|\mathcal{F}_{0}])^{2}}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}1+\frac{\frac{1}{4}(D-D^{-1})\mathbb{E}[Z_{n}^{2}|\mathcal{F}_{0}]}{D^{-2}(\mathbb{E}[Z_{n}|\mathcal{F}_{0}])^{2}}$
$\displaystyle=1+\frac{\frac{1}{4}(D^{3}-D)\mathbb{E}[Z_{n}^{2}|\mathcal{F}_{0}]}{(\mathbb{E}[Z_{n}|\mathcal{F}_{0}])^{2}}$

where (a) is using the bounded condition of $Z_{n+1}$ in (68) and upper bound
of variance for bounded random variable (Popoviciu’s inequality).

From (63), let $B=\frac{1}{4}(D^{3}-D)<1$.

Then

$\displaystyle\frac{\mathbb{E}[Z_{n+1}^{2}|\mathcal{F}_{0}]}{(\mathbb{E}[Z_{n+1}|\mathcal{F}_{0}])^{2}}$
$\displaystyle\leq
1+B\frac{\mathbb{E}[Z_{n}^{2}|\mathcal{F}_{0}]}{(\mathbb{E}[Z_{n}|\mathcal{F}_{0}])^{2}}$

Taking telescoping sum on $n$,

$\displaystyle\frac{\mathbb{E}[Z_{n}^{2}|\mathcal{F}_{0}]}{(\mathbb{E}[Z_{n}|\mathcal{F}_{0}])^{2}}$
$\displaystyle\leq\frac{1-B^{n-1}}{1-B}+B^{n}$ (69)
$\displaystyle\leq\frac{1}{1-B}+1$ (70)

Therefore,

$\displaystyle\sqrt{\mathbb{E}[e^{2\eta Q_{n+1}}|\mathcal{F}_{0}]}$
$\displaystyle=\sqrt{\mathbb{E}[Z_{n+1}^{2}|\mathcal{F}_{0}]}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}D\sqrt{\mathbb{E}[Z_{n}^{2}|\mathcal{F}_{0}]}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}D\sqrt{\Big{(}\frac{1}{1-B}+1\Big{)}}\mathbb{E}[Z_{n}|\mathcal{F}_{0}]$
$\displaystyle=D\sqrt{\Big{(}\frac{1}{1-B}+1\Big{)}}\mathbb{E}[e^{\eta
Q_{n}}|\mathcal{F}_{0}]$ (71)

where (a) is using the bounded condition of $Z_{n+1}$ in (68) and (b) is using
the inequality in (70) .

Let $D^{\prime}=D\sqrt{\Big{(}\frac{1}{1-B}+1\Big{)}}$, from (67) and (71),

$\displaystyle\mathbb{E}[e^{\eta
Q_{n+1}}|\mathcal{F}_{0}]\leq\Big{(}\rho+\frac{D^{\prime}}{n-1}\Big{)}\mathbb{E}[e^{\eta
Q_{n}}|\mathcal{F}_{0}]+e^{\eta(l^{*}+1)}$

Taking telescoping sum over $n$,

$\displaystyle\mathbb{E}[e^{\eta Q_{n}}|\mathcal{F}_{0}]\leq\alpha_{n}e^{\eta
Q_{0}}+\beta_{n}e^{\eta(l^{*}+1)}$ (72)

where $\alpha_{1}=\alpha_{2}=\rho+D^{\prime},\beta_{1}=\beta_{2}=1$. For
$n>2$,

$\displaystyle\alpha_{n}$
$\displaystyle=\alpha_{1}\alpha_{2}\Big{(}\rho+\frac{D^{\prime}}{(n-2)}\Big{)}\Big{(}\rho+\frac{D^{\prime}}{(n-3)}\Big{)}\ldots\Big{(}\rho+D^{\prime}\Big{)}$
$\displaystyle=\alpha_{1}\alpha_{2}\prod_{m=1}^{n-2}\Big{(}\rho+\frac{D^{\prime}}{m}\Big{)}$
$\displaystyle\beta_{n}$
$\displaystyle=1+\Big{(}\rho+\frac{D^{\prime}}{(n-2)}\Big{)}+\Big{(}\rho+\frac{D^{\prime}}{(n-2)}\Big{)}\Big{(}\rho+\frac{D^{\prime}}{(n-3)}\Big{)}+\ldots$
$\displaystyle\quad+\Big{(}\rho+\frac{D^{\prime}}{(n-2)}\Big{)}\Big{(}\rho+\frac{D^{\prime}}{(n-3)}\Big{)}\ldots\Big{(}\rho+D^{\prime}\Big{)}$
$\displaystyle\quad+\Big{(}\rho+\frac{D^{\prime}}{(n-2)}\Big{)}\Big{(}\rho+\frac{D^{\prime}}{(n-3)}\Big{)}\ldots\Big{(}\rho+D^{\prime}\Big{)}^{2}$
$\displaystyle=1+\sum_{j=1}^{n-2}\prod_{m=1}^{j}\Big{(}\rho+\frac{D^{\prime}}{(n-m)}\Big{)}+\Big{(}\rho+\frac{D^{\prime}}{(n-2)}\Big{)}\Big{(}\rho+\frac{D^{\prime}}{(n-3)}\Big{)}\ldots\Big{(}\rho+D^{\prime}\Big{)}^{2}.$

Let $n_{0}=\min\\{n:\rho+\frac{D^{\prime}}{n}<1\\}$. Then let
$\gamma=\Big{(}\rho+\frac{D^{\prime}}{n_{0}}\Big{)}$,
$\xi=\Big{(}\frac{\rho+D^{\prime}}{\rho+\frac{D^{\prime}}{n_{0}}}\Big{)}^{n_{0}}$.
($0<\gamma<1$. $\xi$ is a constant.) Using the fact $\forall n>n_{0}$,
$\frac{1}{n}<\frac{1}{n_{0}}$, and $\forall 1\leq n\leq n_{0}$,
$\frac{1}{n}\leq 1$.

$\displaystyle\alpha_{n}$
$\displaystyle\leq(\rho+D^{\prime})^{n_{0}}\Big{(}\rho+\frac{D^{\prime}}{n_{0}}\Big{)}^{n-n_{0}}$
$\displaystyle=\xi\gamma^{n}$ (73) $\displaystyle\beta_{n}$
$\displaystyle\leq\sum_{m=0}^{n-n_{0}}\Big{(}\rho+\frac{D^{\prime}}{n_{0}}\Big{)}^{m}+\Big{(}\rho+\frac{D^{\prime}}{n_{0}}\Big{)}^{n-n_{0}}(\rho+D^{\prime})^{n_{0}-1}$
$\displaystyle=\frac{1-\gamma^{n-n_{0}+1}}{1-\gamma}+\xi\gamma^{n}$ (74)

From (72), (73), and $\eqref{bound_beta_n}$,

$\displaystyle\mathbb{E}[e^{\eta
Q_{n}}|\mathcal{F}_{0}]\leq\xi\gamma^{n}e^{\eta
Q_{0}}+\Big{(}\frac{1-\gamma^{n-n_{0}+1}}{1-\gamma}+\xi\gamma^{n}\Big{)}e^{\eta(l^{*}+1)}$
(75)

Define the fist hitting time $\tau=\inf\\{n:Q_{n}\geq z\\}$. Define event
$H^{N}(z)=\\{\max_{1\leq n\leq N}Q_{n}\geq z|\mathcal{F}_{0}\\}$ and a
disjoint set of events $H_{n}^{N}(z)=\mathbb{I}(\tau=n)$.
$H^{N}(z)=\cup_{n=1}^{N}H_{n}^{N}(z)$.

$\displaystyle e^{\eta z}\mathbb{P}(H^{N}(z))$
$\displaystyle=\sum_{n=1}^{N}e^{\eta z}\mathbb{P}(H_{n}^{N}(z))$
$\displaystyle=\sum_{n=1}^{N}\mathbb{E}[e^{\eta z}\mathbb{I}_{H_{n}^{N}(z)}]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sum_{n=1}^{N}\mathbb{E}[e^{\eta
Q_{n}}\mathbb{I}_{H_{n}^{N}(z)}]$

where (a) is using the fact $Q_{n}\geq z$ under event $H_{n}^{N}(z)$.

Assume $z>l^{*}+1$,

$\displaystyle\sum_{n=1}^{N}\mathbb{E}[e^{\eta
Q_{n}}\mathbb{I}_{H_{n}^{N}(z)}]$
$\displaystyle=\sum_{n=1}^{N}\mathbb{E}[\mathbb{E}[e^{\eta
Q_{n}}\mathbb{I}_{H_{n}^{N}(z)}\mathbb{I}\\{Q_{n-1}\geq
l^{*}\\}|\mathcal{F}_{n-1}]]$
$\displaystyle\quad+\sum_{n=1}^{N}\mathbb{E}[\mathbb{E}[e^{\eta
Q_{n}}\mathbb{I}_{H_{n}^{N}(z)}\mathbb{I}\\{Q_{n-1}<l^{*}\\}|\mathcal{F}_{n-1}]]$

Since $|Q_{n}-Q_{n-1}|\leq 1$, $Q_{n}>z>l^{*}+1$ is impossible when
$Q_{n-1}<l^{*}$,

$\displaystyle\sum_{n=1}^{N}\mathbb{E}[\mathbb{E}[e^{\eta
Q_{n}}\mathbb{I}_{H_{n}^{N}(z)}\mathbb{I}\\{Q_{n-1}<l^{*}\\}|\mathcal{F}_{n-1}]]=0$

Therefore,

$\displaystyle e^{\eta z}\mathbb{P}(H^{N}(z)|\mathcal{F}_{0})$
$\displaystyle\leq\sum_{n=1}^{N}\mathbb{E}[\mathbb{E}[e^{\eta
Q_{n}}\mathbb{I}_{H_{n}^{N}(z)}\mathbb{I}\\{Q_{n-1}\geq
l^{*}\\}|\mathcal{F}_{n-1}]|\mathcal{F}_{0}]\leq\sum_{n=1}^{N}\mathbb{E}[e^{\eta
Q_{n}}|\mathcal{F}_{0}]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\xi\frac{1-\gamma^{N}}{1-\gamma}e^{\eta
Q_{0}}+\Big{(}\frac{N}{1-\gamma}-\gamma^{-n_{0}+1}\frac{1-\gamma^{N}}{1-\gamma}+\xi\frac{1-\gamma^{N}}{1-\gamma}\Big{)}e^{\eta(l^{*}+1)}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{\xi}{1-\gamma}e^{\eta
Q_{0}}+\Big{(}\frac{N}{1-\gamma}+\frac{\xi}{1-\gamma}\Big{)}e^{\eta(l^{*}+1)}$

where (a) is using (75) and (b) is dropping the negative terms.

Therefore,

$\displaystyle\mathbb{P}(\max_{1\leq n\leq N}Q_{n}\geq z|\mathcal{F}_{0})$
$\displaystyle\leq\frac{\xi}{1-\gamma}e^{-\eta(z-Q_{0})}+\Big{(}\frac{N}{1-\gamma}+\frac{\xi}{1-\gamma}\Big{)}e^{-\eta(z-l^{*}-1)}$
(76) $\displaystyle=\Big{(}\frac{\xi}{1-\gamma}(e^{\eta
Q_{0}}+e^{\eta(l^{*}+1)})+\frac{e^{\eta(l^{*}+1)}}{1-\gamma}N\Big{)}e^{-\eta
z}$ (77)

Let $a=\frac{\xi}{1-\gamma}(e^{\eta Q_{0}}+e^{\eta(l^{*}+1)})$,
$b=\frac{e^{\eta(l^{*}+1)}}{1-\gamma}$ and
$z_{0}=\max\\{\frac{\log(a+bN)}{\eta},l^{*}\\}$.

Then, let $Q_{max}=\max_{1\leq n\leq N}Q_{n}$.

$\displaystyle\mathbb{E}[Q_{max}|\mathcal{F}_{0}]$
$\displaystyle=\mathbb{E}[Q_{max}\mathbb{I}(Q_{max}<z_{0})|\mathcal{F}_{0}]+\mathbb{E}[Q_{max}\mathbb{I}(Q_{max}\geq
z_{0})|\mathcal{F}_{0}]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\mathbb{E}[Q_{max}\mathbb{I}(Q_{max}<z_{0})|\mathcal{F}_{0}]+\int_{z_{0}}^{N}\mathbb{P}(Q_{max}>z)dz+z_{0}\mathbb{P}(Q_{max}>z_{0})$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}z_{0}+\int_{z_{0}}^{N}(a+bN)e^{-\eta
z}dz+z_{0}(a+bN)e^{-\eta z_{0}}$
$\displaystyle=\frac{\log(a+bN)}{\eta}+\frac{(a+bN)}{\eta}\Big{(}\frac{1}{(a+bN)}-e^{-\eta
N}\Big{)}+\frac{\log(a+bN)}{\eta}\frac{(a+bN)}{(a+bN)}$
$\displaystyle=\frac{2\log(a+bN)+1}{\eta}+\frac{(a+bN)e^{-\eta N}}{\eta}$

where (a) uses the fact that $\mathbb{E}[X\mathbb{I}(X\geq
z_{0})]=\int_{z_{0}}^{N}\mathbb{P}(X>z)dz+z_{0}\mathbb{P}(X>z_{0})$ for a
random variable $X\in[0,N]$; (b) uses the definition of $a$ and $b$ and the
inequality (77).

Therefore,

$\displaystyle\mathbb{E}\Big{[}\max_{1\leq n\leq
N}Q_{n}|\mathcal{F}_{0}\Big{]}$
$\displaystyle\leq\frac{2\log\Big{(}\frac{\xi}{1-\gamma}(e^{\eta
Q_{0}}+e^{\eta(l^{*}+1)})+\frac{e^{\eta(l^{*}+1)}}{1-\gamma}N\Big{)}+1}{\eta}$
$\displaystyle\quad+\frac{\Big{(}\frac{\xi}{1-\gamma}(e^{\eta
Q_{0}}+e^{\eta(l^{*}+1)})+\frac{e^{\eta(l^{*}+1)}}{1-\gamma}N\Big{)}e^{-\eta
N}}{\eta}$ $\displaystyle=O\big{(}\log(N)+l^{*}+1\big{)}$

∎

###  E.2 Proof of Theorem 1

###### Proof.

For notation simplicity, in the proof, we will use $\pi$ to represent
${\pi_{\tt LyOn}}$. From Lemma 4, under ${\pi_{\tt LyOn}}$,

$\displaystyle\mathbb{E}[L(Q_{n+1}^{\pi})|\mathcal{F}_{n-1}^{\pi}]-\mathbb{E}[L(Q_{n}^{\pi})|\mathcal{F}_{n-1}^{\pi}]-V\mathbb{E}[R_{n}^{\pi}|\mathcal{F}_{n-1}^{\pi}]$
$\displaystyle\leq$
$\displaystyle\frac{\sigma^{2}+\delta^{2}+2\delta}{2}+\mathbb{E}\big{[}X_{n}^{\pi}\big{|}\mathcal{F}_{n-1}^{\pi}\big{]}\Big{(}\Psi_{n}(Q_{n}^{\pi})-cQ_{n}^{\pi}+\delta
Q_{n}^{\pi}\Big{)}$ $\displaystyle=$
$\displaystyle\frac{\sigma^{2}+\delta^{2}+2\delta}{2}+\mathbb{E}\big{[}X_{n}^{\pi}\big{|}\mathcal{F}_{n-1}^{\pi}\big{]}\Big{(}\Psi_{n}(I_{n}^{\pi},Q_{n}^{\pi})-cQ_{n}^{\pi}+\delta
Q_{n}^{\pi}\Big{)}$ $\displaystyle=$
$\displaystyle\frac{\sigma^{2}+\delta^{2}+2\delta}{2}+\mathbb{E}\big{[}X_{n}^{\pi}\big{|}\mathcal{F}_{n-1}^{\pi}\big{]}\Big{(}\mathbb{I}_{A_{n-1}^{\pi}}\Psi_{n}(I_{n}^{\pi},Q_{n}^{\pi})+\mathbb{I}_{(A_{n-1}^{\pi})^{c}}\Psi_{n}(I_{n}^{\pi},Q_{n}^{\pi})-cQ_{n}^{\pi}+\delta
Q_{n}^{\pi}\Big{)}$ $\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$
$\displaystyle\frac{\sigma^{2}+\delta^{2}+2\delta}{2}+\mathbb{E}\big{[}X_{n}^{\pi}\big{|}\mathcal{F}_{n-1}^{\pi}\big{]}\Big{(}\mathbb{I}_{A_{n-1}^{\pi}}\Psi_{n}(k_{n},Q_{n}^{\pi})+\mathbb{I}_{(A_{n-1}^{\pi})^{c}}\Psi_{n}(k_{n},Q_{n}^{\pi})-cQ_{n}^{\pi}+\delta
Q_{n}^{\pi}$ $\displaystyle\quad+2{\tt
rad}_{I_{n}^{\pi}}(n,\alpha)\cdot\Big{(}\frac{V(1+r_{\tt max})}{\mu_{\tt
min}}+\frac{Q_{n}^{\pi}(1+y_{\tt max})}{\mu_{\tt
min}}\Big{)}+\mathbb{I}_{(A_{n-1}^{\pi})^{c}}(Vr_{\tt max}+n(1+y_{\tt
max}))\Big{)}$ $\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}$
$\displaystyle\frac{\sigma^{2}+\delta^{2}+2\delta}{2}+\mathbb{E}\big{[}X_{n}^{\pi}\big{|}\mathcal{F}_{n-1}^{\pi}\big{]}\Big{(}\frac{\sum_{k=1}^{K}p_{k}^{*}(-V\mathbb{E}[R_{n,k}]+Q_{n}^{\pi}\cdot\mathbb{E}[Y_{n,k}])}{\sum_{k=1}^{K}p_{k}^{*}\mathbb{E}[X_{n,k}]}-cQ_{n}^{\pi}+\delta
Q_{n}^{\pi}$ $\displaystyle\quad+2{\tt
rad}_{I_{n}^{\pi}}(n,\alpha)\cdot\Big{(}\frac{V(1+r_{\tt max})}{\mu_{\tt
min}}+\frac{Q_{n}^{\pi}(1+y_{\tt max})}{\mu_{\tt
min}}\Big{)}+\mathbb{I}_{(A_{n-1}^{\pi})^{c}}(Vr_{\tt max}+n(1+y_{\tt
max}))\Big{)}$ $\displaystyle=$
$\displaystyle\color[rgb]{0,0,0}{}\frac{\sigma^{2}+\delta^{2}+2\delta}{2}+\mathbb{E}\big{[}X_{n}^{\pi}\big{|}\mathcal{F}_{n-1}^{\pi}\big{]}\Big{(}-Vr(p^{*})+2{\tt
rad}_{I_{n}^{\pi}}(n,\alpha)\cdot\Big{(}\frac{V(1+r_{\tt max})}{\mu_{\tt
min}}+\frac{Q_{n}^{\pi}(1+y_{\tt max})}{\mu_{\tt min}}\Big{)}$
$\displaystyle\quad\color[rgb]{0,0,0}{}+\mathbb{I}_{(A_{n-1}^{\pi})^{c}}(Vr_{\tt
max}+n(1+y_{\tt max})\big{)}+y(p^{*})Q_{n}^{\pi}-cQ_{n}^{\pi}+\delta
Q_{n}^{\pi}\Big{)}$ $\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}$
$\displaystyle\frac{\sigma^{2}+\delta^{2}+2\delta}{2}+\mathbb{E}\big{[}X_{n}^{\pi}\big{|}\mathcal{F}_{n-1}^{\pi}\big{]}\Big{(}-Vr(p^{*})+2{\tt
rad}_{I_{n}^{\pi}}(n,\alpha)\cdot\Big{(}\frac{V(1+r_{\tt max})}{\mu_{\tt
min}}+\frac{Q_{n}^{\pi}(1+y_{\tt max})}{\mu_{\tt min}}\Big{)}$
$\displaystyle\quad+\mathbb{I}_{(A_{n-1}^{\pi})^{c}}(Vr_{\tt max}+n(1+y_{\tt
max})\big{)}+\delta Q_{n}^{\pi}\Big{)}$

where (a) is using Lemma 5; (b) is using Proposition 5; (c) is using is using
the definition of $\pi^{*}$ (Definition 4).

Taking expectation on both sides and summing from $N$ to $0$,

$\displaystyle\mathbb{E}[L(Q_{N}^{\pi})]-\mathbb{E}[L(Q_{0}^{\pi})]$
$\displaystyle\leq$
$\displaystyle\frac{N(\sigma^{2}+\delta^{2}+2\delta)}{2}+V\sum_{n=1}^{N}\mathbb{E}[R_{n}^{\pi}]-V\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}]r(p^{*})+\delta\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}Q_{n}^{\pi}]$
$\displaystyle+2V\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}{\tt
rad}_{I_{n}^{\pi}}(n,\alpha)]\frac{1+r_{\tt max}}{\mu_{\tt
min}}+2\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}{\tt
rad}_{I_{n}^{\pi}}(n,\alpha)Q_{n}^{\pi}]\frac{1+y_{\tt max}}{\mu_{\tt min}}$
$\displaystyle+V\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}\mathbb{I}_{(A_{n-1}^{\pi})^{c}}]r_{\tt
max}+\sum_{n=1}^{N}(\mathbb{E}[X_{n}^{\pi}\mathbb{I}_{(A_{n-1}^{\pi})^{c}}]\cdot
n(1+y_{\tt max}))$

Rearrange the terms, since
$\mathbb{E}[L(Q_{n}^{\pi})]-\mathbb{E}[L(Q_{0}^{\pi})]\geq 0$

$\displaystyle\frac{\sum_{n=1}^{N}\mathbb{E}[R_{n}^{\pi}]}{\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}]}$
$\displaystyle\geq
r(p^{*})-\frac{N(\sigma^{2}+\delta^{2}+2\delta)}{2V\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}]}-\delta\frac{\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}Q_{n}^{\pi}]}{V\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}]}$
$\displaystyle-\frac{2\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}{\tt
rad}_{I_{n}^{\pi}}(n,\alpha)]}{\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}]}\frac{1+r_{\tt
max}}{\mu_{\tt min}}-\frac{2\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}{\tt
rad}_{I_{n}^{\pi}}(n,\alpha)Q_{n}^{\pi}]}{V\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}]}\frac{1+y_{\tt
max}}{\mu_{\tt min}}$
$\displaystyle-\frac{\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}\mathbb{I}_{(A_{n-1}^{\pi})^{c}}]}{\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}]}r_{\tt
max}-\frac{\sum_{n=1}^{N}(\mathbb{E}[X_{n}^{\pi}\mathbb{I}_{(A_{n-1}^{\pi})^{c}}]\cdot
n)}{V\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}]}(1+y_{\tt max})$

$\mathbb{E}[X_{n}^{\pi}]\geq\mu_{\tt min}$ is true for any $n$, so
$\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}]\geq N\mu_{\tt min}$. Therefore,

$\displaystyle\frac{\sum_{n=1}^{N}\mathbb{E}[R_{n}^{\pi}]}{\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}]}$
$\displaystyle\geq r(p^{*})-\frac{(\sigma^{2}+\delta^{2}+2\delta)}{2V\mu_{\tt
min}}-\delta\frac{\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}Q_{n}^{\pi}]}{VN\mu_{\tt
min}}$ $\displaystyle-\frac{2\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}{\tt
rad}_{I_{n}^{\pi}}(n,\alpha)]}{N}\frac{1+r_{\tt max}}{\mu_{\tt
min}^{2}}-\frac{2\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}{\tt
rad}_{I_{n}^{\pi}}(n,\alpha)Q_{n}^{\pi}]}{VN}\frac{1+y_{\tt max}}{\mu_{\tt
min}^{2}}$
$\displaystyle-\frac{\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}\mathbb{I}_{(A_{n-1}^{\pi})^{c}}]}{N\mu_{\tt
min}}r_{\tt
max}-\frac{\sum_{n=1}^{N}(\mathbb{E}[X_{n}^{\pi}\mathbb{I}_{(A_{n-1}^{\pi})^{c}}]\cdot
n)}{VN\mu_{\tt min}}(1+y_{\tt max})$

For all $n\in[1,N]$, using the facts that
$\mathbb{E}[Q_{n}^{\pi}]\leq\mathbb{E}[\max_{n}Q_{n}^{\pi}]$ and
$X_{n}^{\pi}\in(0,1]$, we have
$\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}Q_{n}^{\pi}]\leq
N\cdot\mathbb{E}[\max_{n}Q_{n}^{\pi}]$ and $\mathbb{E}[X_{n}^{\pi}{\tt
rad}_{I_{n}^{\pi}}(n,\alpha)Q_{n}^{\pi}]\leq
N\cdot\mathbb{E}[\max_{n}Q_{n}^{\pi}]\cdot\mathbb{E}[X_{n}^{\pi}{\tt
rad}_{I_{n}^{\pi}}(n,\alpha)]$. Also, by definition of the confidence radius
(Definition 7),

$\displaystyle\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}{\tt
rad}_{I_{n}^{\pi}}(n,\alpha)]$
$\displaystyle\leq\sum_{n=1}^{N}\mathbb{E}\Big{[}\frac{\sqrt{2\alpha\log
n}}{\sqrt{T_{I_{n}^{\pi}}(n)}}\Big{]}\leq 2\sqrt{2\alpha KN\log N}$

Therefore,

$\displaystyle\frac{\sum_{n=1}^{N}\mathbb{E}[R_{n}^{\pi}]}{\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}]}$
$\displaystyle\geq r(p^{*})-\frac{(\sigma^{2}+\delta^{2}+2\delta)}{2V\mu_{\tt
min}}-\delta\frac{\mathbb{E}[\max_{n}Q_{n}^{\pi}]}{V\mu_{\tt min}}$
$\displaystyle-\frac{4\sqrt{2\alpha KN\log N}}{N}\frac{1+r_{\tt max}}{\mu_{\tt
min}^{2}}-\frac{4\sqrt{2\alpha KN\log
N}\mathbb{E}[\max_{n}Q_{n}^{\pi}]}{VN}\frac{1+y_{\tt max}}{\mu_{\tt min}^{2}}$
$\displaystyle-\frac{\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}\mathbb{I}_{(A_{n-1}^{\pi})^{c}}]}{N\mu_{\tt
min}}r_{\tt
max}-\frac{\sum_{n=1}^{N}(\mathbb{E}[X_{n}^{\pi}\mathbb{I}_{(A_{n-1}^{\pi})^{c}}]\cdot
n)}{VN\mu_{\tt min}}(1+y_{\tt max})$

Using the fact that
$\mathbb{E}[\mathbb{I}_{(A_{n-1}^{\pi})^{c}}]\leq\frac{1}{n^{2}}$ and
$X_{n}\in(0,1]$, we have
$\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}\mathbb{I}_{(A_{n-1}^{\pi})^{c}}]\leq\pi^{2}/6$
and
$\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}\mathbb{I}_{(A_{n-1}^{\pi})^{c}}n]\leq\log
N$. Therefore,

$\displaystyle\frac{\sum_{n=1}^{N}\mathbb{E}[R_{n}^{\pi}]}{\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}]}$
$\displaystyle\geq r(p^{*})-\frac{(\sigma^{2}+\delta^{2}+2\delta)}{2V\mu_{\tt
min}}-\delta\frac{\mathbb{E}[\max_{n}Q_{n}^{\pi}]}{V\mu_{\tt min}}$ (78)
$\displaystyle-\frac{4\sqrt{2\alpha KN\log N}}{N}\frac{1+r_{\tt max}}{\mu_{\tt
min}^{2}}-\frac{4\sqrt{2\alpha KN\log
N}\mathbb{E}[\max_{n}Q_{n}^{\pi}]}{VN}\frac{1+y_{\tt max}}{\mu_{\tt min}^{2}}$
(79) $\displaystyle-\frac{\pi^{2}/6}{N\mu_{\tt min}}r_{\tt max}-\frac{\log
N}{VN\mu_{\tt min}}(1+y_{\tt max})$ (80)

Using the expression for regret (Lemma 1),

$\displaystyle\mathbb{E}[{\tt REW}^{\pi^{*}}(B)]-\mathbb{E}[{\tt
REW}^{\pi}(B)]$ $\displaystyle\leq$
$\displaystyle\Big{(}r(p^{*})-\frac{\mathbb{E}[\sum_{n=1}^{n_{0}(B)}R_{n}^{\pi}]}{\mathbb{E}[\sum_{n=1}^{n_{0}(B)}X_{n}^{\pi}]}\Big{)}\cdot\frac{2B}{\mu_{\tt
min}}+\frac{r_{\tt max}}{\mu_{\tt min}^{2}}\Big{(}1+8e^{-B\mu_{\tt
min}/4}\Big{)}$ $\displaystyle\leq$
$\displaystyle\frac{B(\sigma^{2}+\delta^{2}+2\delta)}{V\mu_{\tt
min}^{2}}+\delta\cdot\frac{2B\cdot\mathbb{E}[\max_{n}Q_{n}^{\pi}]}{V\mu_{\tt
min}^{2}}+4\sqrt{2\alpha\cdot KB\log B}\frac{1+r_{\tt max}}{\mu_{\tt
min}^{2}}+\frac{\log B(1+y_{\tt max})}{V\mu_{\tt min}^{2}}$
$\displaystyle+\frac{4\sqrt{2\alpha\cdot KB\log
B}\mathbb{E}[\max_{n}Q_{n}^{\pi}]}{V}\frac{1+y_{\tt max}}{\mu_{\tt
min}^{2}}+\frac{\pi^{2}/6}{\mu_{\tt min}}r_{\tt max}+\frac{r_{\tt
max}}{\mu_{\tt min}^{2}}\Big{(}1+8e^{-B\mu_{\tt min}/4}\Big{)}$

From Lemma 7, $\mathbb{E}[\max_{1\leq n\leq
n_{0}(B)}Q_{n}^{\pi}]=O(\log(n_{0}(B))+l^{*}+1)$. Therefore,

$\displaystyle\mathbb{E}[{\tt REW}^{\pi^{*}}(B)]-\mathbb{E}[{\tt
REW}^{\pi}(B)]$ $\displaystyle=O\Bigg{(}\frac{r_{\tt max}\sqrt{KB\log
B}}{\mu_{\tt min}^{2}}+\Big{(}\frac{\sigma^{2}+y_{\tt max}+\delta\log
B}{V\mu_{\tt min}^{2}}+\frac{\delta r_{\tt max}}{\epsilon\mu_{\tt
min}^{2}}\Big{)}B\Bigg{)}$

The results in Theorem 1 follows by adding the maximal regret during initial
exploration $O\Big{(}\frac{y_{\tt max}^{2}K\log B}{\epsilon^{2}\mu_{\tt
min}^{2}}\Big{)}$ and the asymptotic optimality of $\pi^{*}$ (Proposition 1).

Using the definition
$Q_{n+1}=\max\big{\\{}0,Q_{n}+Y_{n}-(c-\delta)X_{n}\big{\\}}$,

$\displaystyle Q_{n+1}\geq Q_{n}+Y_{n}-(c-\delta)X_{n}$

Taking telescoping sum from $N$ to $0$,

$\displaystyle\sum_{n=1}^{N}Y_{n}-(c-\delta)\sum_{n=1}^{N}X_{n}\leq Q_{N}$

Taking expectation on both sides, under ${\pi_{\tt LyOn}}$

$\displaystyle\sum_{n=1}^{N}\mathbb{E}[Y_{n}^{\pi}]-c\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}]\leq\mathbb{E}[Q_{N}^{\pi}]-\delta\sum_{n=1}^{N}\mathbb{E}[X_{n}^{\pi}]$

Let $n=n_{0}(B)$,

$\displaystyle\frac{\mathbb{E}\Big{[}\sum_{n=1}^{n_{0}(B)}(Y_{n}^{\pi})\Big{]}}{\mathbb{E}\Big{[}\sum_{n=1}^{n_{0}(B)}(X_{n}^{\pi})\Big{]}}-c\leq\frac{\mathbb{E}[Q_{n_{0}(B)}^{\pi}]}{\sum_{i=1}^{n_{0}(B)}\mathbb{E}[X_{i}^{\pi}]}-\delta\leq\frac{\mathbb{E}[Q_{n_{0}(B)}^{\pi}]}{n_{0}(B)\mu_{\tt
min}}-\delta$

Using the decomposition for regret violation (Lemma 2),

$\displaystyle D^{\pi}(B)$
$\displaystyle\leq\frac{\mathbb{E}[Q_{n_{0}(B)}^{\pi}]}{n_{0}(B)\mu_{\tt
min}}\cdot\frac{n_{0}(B)}{B}-\frac{2\delta}{\mu_{\tt min}}+\frac{8(y_{\tt
max}-c)}{B\mu_{\tt min}^{2}}e^{-B\mu_{\tt min}/4}+\frac{1}{B}$
$\displaystyle=\frac{\mathbb{E}[Q_{n_{0}(B)}^{\pi}]}{B\mu_{\tt
min}}-\frac{2\delta}{\mu_{\tt min}}+\frac{8(y_{\tt max}-c)}{B\mu_{\tt
min}^{2}}e^{-B\mu_{\tt min}/4}+\frac{1}{B}$

From Lemma 7, $\mathbb{E}[Q_{n_{0}(B)}^{\pi}]=O(\log(n_{0}(B))+l^{*}+1)$.

$\displaystyle D^{\pi}(B)$ $\displaystyle=O\Bigg{(}\frac{\log B}{B\mu_{\tt
min}^{2}}+\frac{r_{\tt max}}{B\mu_{\tt min}\epsilon}-\frac{\delta}{\mu_{\tt
min}}\Bigg{)},$ (81)

The results in Theorem 1 follows by adding the maximal regret during initial
exploration $O\Big{(}\frac{y_{\tt max}^{2}K\log B}{\epsilon^{2}\mu_{\tt
min}^{2}B}\Big{)}$ and the asymptotic optimality of $\pi^{*}$ (Proposition 1).
∎

##  Appendix F Additional Simulation Results

Figure 2 shows the reward rate and constraint-violation of $\tt LyOn$ as $K$
increases ($v_{0}=1,\delta_{0}=0.5)$. New arms are added with the principle
that high reward rate arm also has high penalty rate. As predicted, as $K$
increases, the $\tt LyOn$ initially has larger constraint-violation and
correspondingly larger reward rate, but when budget is large enough they all
converge to the optimal rate for all $K$.

(a)

(b)

Figure 2:  Constraint-violation and reward rate as $B$ grows for different
number of arms. ($v_{0}=1,\delta_{0}=0.5$)

(a)

(b)

Figure 3:  Constraint-violation and reward rate as $B$ grows for different
number of arms. ($v_{0}=1,\delta_{0}=15$)

Figure 3 further confirms the result that selecting $v_{0}$ and $\delta_{0}$
properly, we can have zero constraint-violation for different number of arms
when $B$ is sufficiently large. At the same time, the reward rate still
converges to the optimal.

(a)

(b)

Figure 4:  Constraint-violation and reward rate as $B$ grows for different
$v_{0}$ and $\delta_{0}$ values. (a) $\tt LyOff$ reward rate. (b) $\tt LyOff$
constraint-violation.

(a)

(b)

Figure 5:  Constraint-violation and reward rate as $B$ grows for different
$v_{0}$ and $\delta_{0}$ values. (a) $\tt LyOn$ reward rate. (b) $\tt LyOn$
constraint-violation.

Figure 4 and Figure 5 show the reward rate and constraint-violation for $\tt
LyOff$ and $\tt LyOn$ algorithms with different $v_{0}$ and $\delta_{0}$
values for $K=2$ arms. Assuming $c=0.8$, arm 1 is selected to have a high
reward rate and a high penalty rate with
$\mathbb{E}[X_{1}]=0.4,\mathbb{E}[Y_{1}]=0.6$, and $\mathbb{E}[R_{1}]=0.6$.
Arm 2 is selected to have a low reward rate and a low penalty rate with
$\mathbb{E}[X_{2}]=0.6,\mathbb{E}[Y_{2}]=0.3$, and $\mathbb{E}[R_{2}]=0.3$.
The results confirm the trade-off between regret and constraint-violation when
changing the values of $V$ and $\delta$. Larger $V$ or smaller $\delta$ will
result in larger constraint-violation but smaller regret (higher reward rate).
On the other hand, smaller $V$ or larger $\delta$ will result in smaller
constraint-violation but larger regret (smaller reward rate).