# Online Optimization for Randomized Network Resource Allocation with Long-
Term Constraints ††thanks: This work was supported by a grant from the Natural
Sciences and Engineering Research Council of Canada and Ericsson Canada.

Ahmed Sid-Ali1, Ioannis Lambadaris2, Yiqiang Q. Zhao1, Gennady Shaikhet1, and
Shima Kheradmand2  1School of Mathematics and Statistics
2Department of Systems and Computer Engineering
Carleton University, Ottawa, Ontario
Emails<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
and<EMAIL_ADDRESS>
###### Abstract

This paper studies an online optimal resource reservation problem in
communication networks. A typical network is composed of compute nodes linked
by communication links. The system operates in discrete time and at each time
slot, the administrator reserves server resources to meet future client
requests. A cost is incurred for the made reservations. Then, after the
reception of the job requests, some may be transferred from one server to
another to be best accommodated at an additional transport cost. In
particular, if certain job requests cannot be satisfied, a violation engenders
a cost to pay for each blocked job. The goal is to minimize the overall
reservation cost over finite horizons while maintaining the cumulative
violation and transport costs under a certain budget limit. To tackle this
problem, we propose a randomized procedure where the reservations are drawn
randomly according to a sequence of probability distributions over the space
of allowable reservations. The distributions are derived from an online
saddle-point algorithm. For this proposed algorithm we analyze its performance
by first establishing an upper bound for the associated $K$-benchmark regret.
We then develop an upper bound for the cumulative constraint violations.
Finally, we present numerical experiments where we compare the performance of
our algorithm with those of some basic deterministic resource allocation
policies.

###### Index Terms:

Online optimization; Resource allocation; Communication networks; Saddle point
method

##  I Introduction

Online (convex) optimization (OCO) is a machine learning framework where a
decision maker sequentially chooses a sequence of decision variables over time
to minimize the sum of a sequence of (convex) loss functions. In OCO, the
decision maker does not have full access to the data at once, but instead
receives it incrementally over time. Thus, the decisions are made sequentially
in an incomplete information environment. Moreover, in OCO, the data source is
viewed as arbitrary, and thus no assumptions on the statistics of data sources
are made. This radically differs from classical statistical approaches such as
Bayesian decision theory or Markov decision processes. Thus, only the observed
data sequence’s empirical properties matter, allowing us to address the
dynamic variability of the traffic requests at modern communication networks.
OCO has further applications in a wide range of fields, including control
theory, game theory, economics, and signal processing, and has been
extensively studied in the last decade; see, e.g. [b12, b13, b14, b15] and the
references therein for an overview. Moreover, given that the decision maker
has only access to limited/partial information, globally optimal solutions are
generally not realizable. Instead, one searches for algorithms that perform
relatively well in comparison to the overall ideal best solution in hindsight
which has full access to the data. This performance metric is referred to as
regret in the literature. In particular, if an algorithm incurs regret that
increases sub-linearly with time, then one says that it achieves no regret.

One important application of online optimization, as in the problem presented
in our work, is in resource reservations that arise in situations where
resources must be allocated in advance to meet future unknown demands. Typical
examples arise in transportation systems, hotel reservations, or healthcare
services handling systems. In this paper, we tackle a specific online resource
reservation problem in a simple communication network topology. The network is
composed of $N$ linked servers and the network administrator reserves
resources at each server to meet future job requests. The specificity of this
system is that one is allowed to transfer jobs from one server to another
after receiving the job requests to better meet the demands. This couples the
servers by creating dependencies between them. The reservation and transfer
steps come with a cost that is proportional to the amount of resources
involved. Moreover, if the job requests are not fully satisfied, a violation
cost is incurred. The goal is then to minimize the reservation cost while
maintaining the transfer and violation costs under a given budget threshold
which leads to an online combinatorial optimization problem with long-term
constraints.

To tackle the above-mentioned problem, we propose a randomized control policy
that minimizes the cumulative reservation cost while maintaining the long-term
average of the cumulative expected violation and transfer costs under the
budget threshold. This transforms the online combinatorial optimization
problem into an online continuous optimization problem on the space of
probability distributions over the set of reservations. In particular, we
propose an online saddle-point algorithm tailored to our model for which we
derive an explicit upper bound for the incurred regret against $K$-Benchmark,
a concept introduced in [b18] which allows us to examine the trade-offs
between regret minimization and long-term budget constraint violations.

The rest of the paper is organized as follows: in Section II we introduce the
problem; in Section III, we formalize the problem as a constrained online
optimization problem on the simplex of probability distributions over the
space of reservations; section IV contains our proposed online saddle point
algorithm; then, in Section V, we present an upper bound for the $K$-benchmark
regret together with the cumulative constraint violations upper bound, and
finally, we present in Section LABEL:num-sec some numerical results where we
compare the performance of our algorithm with some deterministic online
reservation policies.

##  II Online resource reservation in communication networks

Consider a network of $N$ servers connected by communication links. The system
provides access to computing resources for clients. For simplicity, we suppose
that there is a single type of resource (e.g. memory, CPU, etc.). Denote by
$m_{n}$ the total number of resources available at the $n$-th server. Let
$\mathcal{R}_{n}=\\{1,\ldots,m_{n}\\}$ be the set of possible reservations at
the $n$-th server, and $\mathcal{R}=\prod_{n=1}^{N}\mathcal{R}_{n}$ be the set
of possible reservations in the entire network. In particular, the system
operates in discrete time slots $t=1,2,\ldots$ and, at each time slot $t$, the
following processes take place chronologically:

  * •

Resource reservation: the network administrator selects the resources
$A^{t}=(A^{t}_{1},\ldots,A^{t}_{N})\in\mathcal{R}$ to make available at each
server.

  * •

Job requests: the network receives job requests
$B^{t}=(B^{t}_{1},\ldots,B^{t}_{N})\in\mathcal{R}$ from its clients to each of
its servers.

  * •

Job transfer: the network administrator can shift jobs between the servers to
best accommodate the demand.

Let $\delta^{t}_{n,m}$ be the number of jobs transferred from server $n$ to
server $m$ at time slot $t$ after receiving the job requests $B^{t}$. Notice
that the coefficients $\delta^{t}_{n,m}$ depend on both $A^{t}$ and $B^{t}$.
However, to keep the notation simple, we suppress this dependency in the
sequel.

Suppose that the reservations, the job transfers, and the violations incur
costs defined as follows:

#### -Reservation cost

given by the function

$\displaystyle C_{R}(A^{t})=\sum_{n=1}^{N}f^{R}_{n}(A^{t}_{n}).$

#### -Violation cost

incurred when the job requests cannot be satisfied

$\displaystyle
C_{V}(A^{t},B^{t})=\sum_{n=1}^{N}f^{V}_{n}\big{(}B_{n}^{t}-A_{n}^{t}-\sum_{m=1}^{N}\delta^{t}_{n,m}\big{)}.$

#### -Transfer cost

incurred by the transfer of jobs between the different servers

$\displaystyle C_{T}(A^{t},B^{t})=\sum_{n=1}^{N}\sum_{m\neq
n}f^{T}_{n}\big{(}\delta^{t}_{n,m}\big{)}.$

Here, $f^{R}_{n},f^{V}_{n},f^{T}_{n}$, for $1\leq n\leq N$ are some given
positive functions. Therefore, at each time slot $t$, and after receiving the
job requests $B^{t}$, the job transfer coefficients $\\{\delta^{t}_{n,m},1\leq
n\leq N\\}$ are solutions to the following offline minimization problem:

$\begin{split}\left\\{\begin{tabular}[]{l}$\min\sum\limits_{n=1}^{N}\big{(}\sum\limits_{m\neq
n}f^{T}_{n}(\delta^{t}_{n,m})+f^{V}_{n}\big{(}B_{n}^{t}-A_{n}^{t}-\sum\limits_{m\neq
n}\delta^{t}_{n,m}\big{)}\big{)},$\\\ s.t.
$\delta^{t}_{n,m}\leq\min\big{\\{}(B^{t}_{n}-A_{n}^{t})^{+},(A^{t}_{m}-B^{t}_{m})^{+}\big{\\}},\forall
n\neq m$.\end{tabular}\right.\end{split}$ (1)

The goal is then to minimize the reservation cost $C_{R}(A^{t})$ while
maintaining the sum $C_{V}(A^{t},B^{t})+C_{T}(A^{t},B^{t})$ of the violation
and transport costs under a given threshold $v>0$. Nevertheless, since at each
slot $t$, the reservations $A^{t}$ are selected before the job request $B^{t}$
are received, this problem is of online optimization kind for which the
optimal solution is out of reach. In particular, one cannot guarantee that the
constraint is satisfied. Instead, one searches for online control policies
that satisfy the constraints on average over large time horizons. More
precisely, we consider the following online combinatorial constrained
optimization problem with a long-term constraint:

$\begin{split}\left\\{\begin{tabular}[]{l}$\min\limits_{\\{A^{t}\\}}\sum\limits_{t=1}^{T}C_{R}(A^{t})$,\\\
s.t.:
$\frac{1}{T}\sum\limits_{t=1}^{T}(C_{V}(A^{t},B^{t})+C_{T}(A^{t},B^{t}))\leq
v$,\end{tabular}\right.\end{split}$ (2)

over finite time horizons $T\geq 1$. Notice that the sequence of job arrivals
$\\{B^{t}\\}_{t\geq 1}$ is arbitrary, in the sense that we make no assumptions
on its statistical properties which make the classical statistical inference
methods unsuitable. Therefore, one searches for an online control policy that
uses the cumulative information available so far to make the reservations at
the next time slot. Of course, the goal is not to reach the optimal solution
to $(\ref{opt-pb-on})$, and instead to obtain a total loss
$\sum\limits_{t=1}^{T}C_{R}(A^{t})$ that is not too large compared to some
benchmark that knows the job requests in advance, and meanwhile, to ensure
that the constraint is asymptotically satisfied on average over large time
horizons.

###### Remark 1

One can consider a different formulation of the problem by minimizing the
total cost of reservation, violation, and transfer thus obtaining an
unconstrained online optimization problem. This alternative formulation has
been studied in [b24] and a randomized exponentially weighted algorithm was
proposed and analyzed.

Figure 1: The network model for three nodes at time $t$

##  III Online randomized reservations

Notice that the action set $\mathcal{R}=\prod_{n=1}^{N}\mathcal{R}_{n}$ is
finite. Therefore, the classical online gradient type algorithms (see e.g.
[b17]) cannot be applied since no convexity assumption is possible. To
overcome this issue, one possibility is to introduce randomization in the
decision process. More precisely at every time step, the network administrator
chooses a probability distribution $P^{t}$ over the set $\mathcal{R}$ of
reservations, based on the past, and then draws his reservation $A^{t}$ at
random according to $P^{t}$. In particular, denote by
$\mathcal{P}(\mathcal{R})$ the space of probability distributions over the
reservation set $\mathcal{R}$, and write $P=(p_{a})_{a\in\mathcal{R}}$, then

$\displaystyle\mathcal{P}(\mathcal{R})=\bigg{\\{}P\in\mathbb{R}^{|\mathcal{R}|}_{+}:\mbox{
$\sum\limits_{a\in\mathcal{R}}p_{a}=1$}\bigg{\\}},$

which is a convex, closed, bounded, and non-empty set. Define the expected
reservation cost by

$\displaystyle\mathbb{E}_{P^{t}}[C_{R}(A^{t})]=\sum_{a\in\mathcal{R}}p^{t}_{a}C_{R}(a).$

Similarly, define the conditional expected transfer and violation costs given
that the job request $B^{t}=b^{t}$, respectively, by

$\displaystyle\mathbb{E}_{P^{t}}[C_{T}(A^{t},b^{t})]=\sum_{a\in\mathcal{R}}p^{t}_{a}C_{T}(a,b^{t})$

and

$\displaystyle\mathbb{E}_{P^{t}}[C_{V}(A^{t},b^{t})]=\sum_{a\in\mathcal{R}}p^{t}_{a}C_{V}(a,b^{t}).$

The goal is then to find a randomized control policy that behaves relatively
well in comparison to the best solutions in hindsight. In particular, let
$A_{K}^{*}$ be the optimal static solution to the constrained combinatorial
optimization problem

$\begin{split}\left\\{\begin{tabular}[]{l}$\min\limits_{A\in\mathcal{R}}C_{R}(A)$,\\\
s.t.: $\sum\limits_{k=t}^{t+K-1}(C_{V}(A,b^{k})+C_{T}(A,b^{k}))\leq Kv,$\\\
$\qquad\qquad\qquad\qquad\qquad\forall
t=1,\ldots,T-K+1$,\end{tabular}\right.\end{split}$ (3)

if the values of job requests $\\{B^{t}\\}_{t=1}^{T}=\\{b^{t}\\}_{t=1}^{T}$
were known in advance. Moreover, let $\\{A_{t}\\}_{t=1}^{T}$ be the sequence
of random reservations generated according to the sequence
$\\{P^{t}\\}_{t=1}^{T}$ of probability distributions. Therefore, the regret of
not playing $A^{*}_{K}$ over the horizon $T$ is given by

$\displaystyle\tilde{R}^{K}_{T}=\sum_{t=1}^{T}\big{(}C_{R}(A^{t})-C_{R}(A_{K}^{*})\big{)}.$
(4)

The definition in $(\ref{reg-non-rand})$ is known in the literature as the
“regret against $K$-benchmark”; see, e.g. [b18, b20]. The idea is that by
varying $K$, this metric provides sufficient flexibility to study the question
of adversarial long-term constraints. It is well known from [b21] that for
$K=T$, sub-linear regret is not attainable in a general adversarial setting.
In counterpart, for $K=1$, a sub-linear regret is achievable under some
reasonable assumptions as we will see in the sequel. Therefore, we present in
this paper a general upper bound for the $K$-benchmark regret which is sub-
linear in $T$ when $K=o(\sqrt{T})$. Furthermore, the regret
$\tilde{R}^{K}_{T}$ in $(\ref{reg-non-rand})$ is a random variable since the
reservations $\\{A_{t}\\}_{t=1}^{T}$ are generated randomly. Alternatively,
one can introduce the deterministic regret $R^{K}_{T}$ defined in terms of
expected costs. More precisely, let the probability distribution
$P^{K}_{*}\in\mathcal{P}(\mathcal{R})$ be the optimal solution to the
following optimization problem:

$\begin{split}\left\\{\begin{tabular}[]{l}$\min\limits_{P\in\mathcal{P}(\mathcal{R})}\sum\limits_{t=1}^{T}\mathbb{E}_{P}[C_{R}(A^{t})]$,\\\
s.t.:
$\sum\limits_{k=t}^{t+K-1}\mathbb{E}_{P}[C_{V}(A^{k},b^{k})+C_{T}(A^{k},b^{k})]\leq
Kv,$\\\ $\qquad\qquad\qquad\qquad\qquad\forall
t=1,\ldots,T-K+1$,\end{tabular}\right.\end{split}$ (5)

for finite $1\leq K\leq T$, if the values of job requests
$\\{B^{t}\\}_{t=1}^{T}=\\{b^{t}\\}_{t=1}^{T}$ were known in advance. Then, one
defines the deterministic regret of not playing according to $P^{K}_{*}$ over
the horizon $T$ as

$\begin{split}&R^{K}_{T}=\sum\limits_{t=1}^{T}\big{(}\mathbb{E}_{P^{t}}[C_{R}(A^{t})]-\mathbb{E}_{P_{*}^{K}}[C_{R}(A^{t})]\big{)}.\end{split}$
(6)

In Section V, we establish upper-bounds for $R^{K}_{T}$ and
$\tilde{R}^{K}_{T}$. In addition to the regret, we analyze the expected
cumulative constraint violations over finite horizons $T>0$,

$\displaystyle\Upsilon_{T}=\sum_{t=1}^{T}\big{(}\mathbb{E}_{P^{t}}[C_{V}(A^{t},b^{t})+C_{T}(A^{t},b^{t})]-v\big{)}.$
(7)

Let us suppose the following assumptions:

###### Assumptions 1

  1. 1.

Suppose that there exists a constant $\Theta>0$ such that, for all
$a,b\in\mathcal{R}$,

$\displaystyle\big{|}C_{R}(a)\big{|}\leq\Theta,\big{|}C_{T}(a,b)\big{|}\leq\Theta,\mbox{
and }\big{|}C_{V}(a,b)\big{|}\leq\Theta.$

  2. 2.

There exists a subspace $\mathcal{E}\subset\mathcal{P}(\mathcal{R})$ such
that, for all $P\in\mathcal{E}$,

$\displaystyle\mathbb{E}_{P}[C_{V}(A,b)+C_{T}(A,b)]-v\leq 0,\mbox{ for all
$b\in\mathcal{R}$}.$

  3. 3.

There exist a probability distribution $\tilde{P}\in\mathcal{E}$, called a
Slater distribution, and a constant $\eta>0$ such that,

$\displaystyle\mathbb{E}_{\tilde{P}}[C_{V}(A,b)+C_{T}(A,b)]-v\leq-\eta,\mbox{
for all $b\in\mathcal{R}$}.$

###### Remark 2

The subspace $\mathcal{E}$ represents the feasible set in which the
constraints are satisfied at all slots $t\geq 1$. The Slater vector
$\tilde{P}$ is an interior point for $\mathcal{E}$ and its existence is a
classical sufficient condition for strong duality to hold for a convex
optimization problem; see, e.g. [b12][Prop. 3.3.9].

##  IV Online Lagrange multipliers approach

A classical approach for solving constrained convex optimization problems is
the Lagrange multipliers method. This relies in particular on the Karush-Kuhn-
Tucker theorem which states that finding an optimal point for the constrained
optimization problem is akin to finding a saddle point of the Lagrangian
function (cf. [b3, Section I.5]). Popular saddle-point methods are the Arrow-
Hurwicz-Uzawa algorithms introduced in [b2] and widely used in the literature;
see, e.g. [b5, b6, b7] for an overview. These methods alternate a minimization
of the Lagrangian function with respect to the primal variable and a gradient
ascent with respect to the dual variable given the primal variable. Online
versions of these methods have also been proposed recently (see, e.g., [b8,
b9, b16]). In the same spirit as the aforementioned references, we develop
here an online saddle-point algorithm to solve the problem detailed in Section
III. To this end, let us first introduce the sequence of per slot optimization
problem

$\begin{split}\left\\{\begin{tabular}[]{l}$\min\limits_{P^{t}\in\mathcal{P}(\mathcal{R})}\mathbb{E}_{P^{t}}[C_{R}(A^{t})]$,\\\
s.t.: $\mathbb{E}_{P^{t}}[C_{V}(A^{t},b^{t})+C_{T}(A^{t},b^{t})]-v\leq
0$,\end{tabular}\right.\end{split}$ (8)

and the corresponding instantaneous online Lagrangian functions

$\begin{split}\mathcal{L}^{t}(P^{t},\lambda_{t})&=\mathbb{E}_{P^{t}}[C_{R}(A^{t})]\\\
&\qquad+\lambda_{t}\big{(}\mathbb{E}_{P^{t}}\big{[}C_{V}(A^{t},b^{t})+C_{T}(A^{t},b^{t})\big{]}-v\big{)},\end{split}$
(9)

where $\\{\lambda_{t}\\}_{t\geq 1}$ is a sequence of Lagrange multipliers and
$P^{t}\in\mathcal{P}(\mathcal{R})$ for all $t\geq 1$. Now, since at each time
slot $t$, the probability distribution $P^{t}$ is selected before the job
request $b^{t}$ is observed, $\mathcal{L}^{t}(P^{t},\lambda_{t})$ cannot be
computed beforehand. Nonetheless, one uses the most recent information
$B^{t-1}=b^{t-1}$ available to build the following sequence of approximate
Lagrangian functions:

$\begin{split}\tilde{\mathcal{L}}^{t}(P^{t},\lambda_{t})&=\mathbb{E}_{P^{t}}[C_{R}(A^{t})]\\\
&\quad+\lambda_{t}\big{(}\mathbb{E}_{P^{t}}[C_{V}(A^{t},b^{t-1})+C_{T}(A^{t},b^{t-1})\big{]}-v\big{)}.\end{split}$
(10)

By noticing that the function $\mathcal{L}^{t}$ is linear in $P^{t}$, it is
easy to see that our approximation is equivalent to the ones proposed in [b8]
and [b17]. Note that the authors in [b17] weight the objective function by an
additional penalty parameter.

Observe that the minimization of $(\ref{appr-lag})$ at each slot $t$ could
result in an oscillatory behavior for $P^{t}$, especially if the job requests
are not smooth. To overcome this, one introduces an additional proximal term
and then, at each time slot $t$, selects $P^{t}$ that solves the following
minimization problem:

$\begin{split}\min_{P\in\mathcal{P}(\mathcal{R})}\bigg{(}\tilde{\mathcal{L}}^{t}(P,\lambda_{t})+\frac{1}{2\alpha}\big{\|}P-P^{t-1}\big{\|}^{2}\bigg{)},\end{split}$
(11)

with $\alpha>0$ is a positive scalar and $\|\cdot\|$ stands for the Euclidean
distance, thus obtaining a proximal point approach. In particular, the
proximal methods are well-known in the classical optimization literature where
their main advantage is to transform the original objective function into a
strongly convex one. Therefore, the convergence of these methods does not
require strict convexity; see, e.g. [b4, b10, b11] and the references therein
for more details. For online optimization algorithms, the proximal term
$\big{\|}P-P^{t-1}\big{\|}^{2}$ acts as a learning term that accumulates
knowledge from the past allowing to improve the performance of the algorithms
in terms of regret. Thus many authors used a similar term in their algorithms;
see, e.g. [b8, b17, b19]. Finally, the Lagrange multiplier $\lambda_{t}$ is in
turn updated at each step $t$ using a projected gradient ascent step. Namely,

$\displaystyle\lambda_{t+1}$
$\displaystyle=\bigg{(}\lambda_{t}+\mu\big{(}\mathbb{E}_{P^{t}}\big{[}C_{V}(A^{t},b^{t-1})+C_{T}(A^{t},b^{t-1})\big{]}-v\big{)}\bigg{)}^{+},$
(12)

where $\mu>0$ is the step-size, and, for any $x\in\mathbb{R}$,
$(x)^{+}=\max\\{0,x\\}$. Notice that the update in $(\ref{lambd-update})$ is
based on the gradient of the approximate Lagrangian function
$\tilde{\mathcal{L}}^{t}$ with respect to $\lambda_{t}$ instead of the
gradient of the Lagrangian function $\mathcal{L}^{t}$ as proposed in [b8] and
[b19]. More precisely, we update $\lambda_{t+1}$ using $b^{t-1}$ even though
$b^{t}$ is available after the reservation is made. The reason for that is to
use the same function in the primal and dual update equations which allows us
to obtain an upper bound for the regret independent of the sequence of job
arrivals. Moreover, by the linearity of $\tilde{\mathcal{L}}^{t}$ with respect
to $P^{t}$, the update in $(\ref{lambd-update})$ amounts to the virtual queue
update proposed in [b17, b18] with the difference that we include a step-size
parameter $\mu$.

We summarize our approach in Algorithm 1.

Algorithm 1 Randomized Saddle-Point Algorithm for Online Resource Reservation

  * •

Initialize the values of $P^{0}\in\mathcal{P}(\mathcal{R})$,
$b^{0}\in\mathcal{R}$, and $\lambda_{1}\geq 0$

  * •

At each step $t=1,2,\ldots$

    * –

Observe $b^{t-1}$ and chose $P^{t}$ such that:

$\displaystyle
P^{t}=\operatorname*{arg\,min}_{P\in\mathcal{P}(\mathcal{R})}\big{(}\tilde{\mathcal{L}}^{t}(P,\lambda_{t})+\frac{1}{2\alpha}\|P-P^{t-1}\|^{2}\big{)}$

    * –

Update $\lambda_{t}$ by:

$\displaystyle\lambda_{t+1}$
$\displaystyle=\big{(}\lambda_{t}+\mu\big{(}\mathbb{E}_{P^{t}}\big{[}C_{V}(A^{t},b^{t-1})+C_{T}(A^{t},b^{t-1})\big{]}-v\big{)}\big{)}^{+}$

##  V Performance analysis

We analyze here the performance of Algorithm 1 over finite time horizons
$T>0$, first in terms of cumulative constraint violations and then in terms of
regret. To facilitate the reading, all proofs are postponed to the appendices.

###  V-A Violation constraint bound

We start by establishing an upper bound for the cumulative constraint
violations $\Upsilon_{T}$ defined in $(\ref{cumul-const})$.

###### Theorem V.1

Let $\lambda_{1}=0$. Then, for any positive integer $\aleph\in\mathbb{N}$, the
Lagrange multiplier $\lambda_{t}$ given by the update equation in
$(\ref{lambd-update})$ is bounded as:
$\lambda_{t}\leq\bar{\lambda}:=\theta\aleph,\mbox{ for all
$t\in\\{1,2,\ldots\\}$}$, where $\theta=\max\big{\\{}\varrho,\chi\big{\\}}$,
with

$\displaystyle\chi$
$\displaystyle=\frac{1}{\eta\aleph}\bigg{(}\frac{\mu\big{(}4\Theta^{2}+v^{2}\big{)}}{2}+\frac{\alpha\Theta^{2}}{4}+\frac{1}{2\alpha(\aleph+1)}+\Theta\bigg{)}$
$\displaystyle\qquad+\frac{\varrho(\aleph+2)}{2\aleph},$

and $\varrho=\mu(2\Theta-v)$, $\alpha,\mu$ are the step sizes, $\Theta,\eta$
are defined as previously, and $v$ is the violation and transport cost
threshold. Moreover, for any $T>0$, the cumulative violations related to
Algorithm 1 satisfies: $\Upsilon_{T}\leq\frac{\theta\aleph}{\mu}$.

###### Proof:

See Appendix LABEL:proof_theo_1.

###  V-B Regret against $K$ benchmark

We first establish an upper bound for the deterministic regret $R^{K}_{T}$
defined in $(\ref{stat-reg-K})$ associated with the sequence
$\\{P^{t}\\}_{t=1}^{T}$ of probability distributions drawn from Algorithm 1.

###### Theorem V.2

Let $\lambda_{1}=0$. Then, the deterministic regret associated with the
sequence of probability distributions generated by Algorithm 1 satisfies, for
any $T>0$ and $1\leq K\leq T$,

$\displaystyle R^{K}_{T}$
$\displaystyle\leq\mu(2\Theta+v)^{2}\frac{(K-1)(2K-1)}{6}$
$\displaystyle\quad+(T-K)\bigg{(}\frac{1}{2}K\big{(}4\Theta^{2}+v^{2}\big{)}\mu+\frac{\Theta^{2}}{4}\alpha\bigg{)}$
$\displaystyle\quad+K(K-1)\Theta+\frac{1}{\alpha}.$