# Group-Fair Online Allocation in Continuous Time

Semih Cayci
<EMAIL_ADDRESS>&Swati Gupta
<EMAIL_ADDRESS>&Atilla Eryilmaz11footnotemark: 1
<EMAIL_ADDRESS>
Department of Electrical and Computer Engineering, The Ohio State University,
Columbus, OH 43210H. Milton Stewart School of Industrial and Systems
Engineering, Georgia Institute of Technology, Atlanta, GA 30332

###### Abstract

The theory of discrete-time online learning has been successfully applied in
many problems that involve sequential decision-making under uncertainty.
However, in many applications including contractual hiring in online
freelancing platforms and server allocation in cloud computing systems, the
outcome of each action is observed only after a random and action-dependent
time. Furthermore, as a consequence of certain ethical and economic concerns,
the controller may impose deadlines on the completion of each task, and
require fairness across different groups in the allocation of total time
budget $B$. In order to address these applications, we consider continuous-
time online learning problem with fairness considerations, and present a novel
framework based on continuous-time utility maximization. We show that this
formulation recovers reward-maximizing, max-min fair and proportionally fair
allocation rules across different groups as special cases. We characterize the
optimal offline policy, which allocates the total time between different
actions in an optimally fair way (as defined by the utility function), and
impose deadlines to maximize time-efficiency. In the absence of any
statistical knowledge, we propose a novel online learning algorithm based on
dual ascent optimization for time averages, and prove that it achieves
$\tilde{O}(B^{-1/2})$ regret bound.

##  1 Introduction

With the prevalence of automated decision methods and machine learning
methods, it is important to analyze the impact of learning and evaluate models
not only with respect to traditional objectives such as reward or model
accuracy, but also to account for the impact on individuals that interact with
the system. Indeed, there are many studies highlighting algorithmic
discrimination due to problems in the machine learning pipeline: imbalance in
data [1], learnt representations [2, 3], choice of model proxies [4],
demographic group-dependent difference in error rates of the learned models
[5, 6, 7], to name a few. With rising ethical and legal concerns, addressing
such issues has become urgent, specially as these impact critical societal
decisions involving job opportunities and hiring. In 2014, it was estimated
that 25% of the total workforce in the US was involved in some form of
freelancing, and this number was predicted to grow to 40% by 2020 [8]. In
reality, this percentage might be much higher, due to COVID-19 restrictions
leading to increased work-from-home and changes in job opportunities [9, 10].
In online platforms however, there has been a strong evidence of bias observed
in number of user reviews and user ratings111The mean (median) normalized
rating score for White workers was 0.98 (1), while it is 0.97 (1) for Black
workers on TaskRabbit. The mean (median) rating of White workers was found to
be 3.3 (4.8), 3.0 (4.6) for Black workers, 3.3 (4.8) for Asian workers, 3.6
(4.8) for workers with a picture that does not depict a person, and 1.7 (0.0)
for workers with no image on Fiverr [11]. on completing jobs with significant
correlations with race, gender, location of work and length of profiles222Mean
(median) number of reviews: for women 33 (11), 59 (15) for men on TaskRabbit.
Mean (median) number of reviews: for Black workers was found to be 65 (4), 104
(6) for White workers, 101 (8) for Asian workers, 94 (10) for non-human
pictures and 18 (0) for users with no image on Fiverr [11]. [11]. Motivated by
these problems in online contractual hiring, we study a theoretical framework
for sequential resource allocation to workers, where the controller (decision
maker) can enforce deadlines for each task’s completion. Our key contribution
is to quantify impact of reward maximization in terms of equality of
opportunity for jobs and develop algorithms that can achieve a meaningful
trade-off between these via online utility maximization. The challenge is to
maximize total reward within a given time budget, while accounting for random
completion times by workers from different groups and fairness in allocation.

Formally, we consider $K$ groups of individuals who can be hired sequentially
for each task, i.e., at any point, exactly one individual can be hired. If an
individual from group $k\in[K]$ is chosen for the $n$-th task and given a
contractual deadline $t$ by the controller, he/she generates a random reward
of $R_{k,n}$ if the task is completed by (random) time $X_{k,n}$ within
deadline $t$. If the task is not completed by the deadline, the reward
obtained by the controller is zero and the time until the deadline is wasted
(i.e., yields 0 reward for the controller). Completion times and reward
distributions are assumed group-dependent and i.i.d. across tasks. The
objective of the controller is to maximize utility (trade-off between total
reward and fair allocation) in the offline (known distributions) and online
settings (unknown distributions) under a budget constraint on time. As we will
show in this paper, controlled deadlines set are essential for optimal time-
efficiency under the budget constraint.

Figure 1: Freelancer profiles on Upwork with their past performance and
corresponding reviews for “fixed-price" contracts. Contractors can access
these profiles and allocate fixed-timed contracts with deadlines.

The ethical problems we are concerned with involve the rate of jobs allocated
to different demographic groups and the deadlines imposed on these under
reward maximization regimes [11]. Our sequential framework would also apply to
other settings, for e.g., comparative clinical trials with varying follow-up
durations as well as to server allocation in cloud computing where jobs are
drawn from different application groups and must commit computational
resources until a specific amount of time due to service level agreements
(Section 2). We will often focus on the first application involving online
contractual hiring, since fairness concerns are most naturally motivated in
this domain.

Given a time budget constraint $B$ and the diverse random nature of completion
time and reward pairs, the main question we consider is how to decide
distribution of tasks and deadlines between different groups of people. Two
potential extreme allocations are: (i) Reward-maximizing task allocation: The
controller assigns all tasks to the most rewarding group to maximize the total
reward within the given time budget. The other groups do not get any chance to
receive tasks. (ii) Proportional task allocation: The controller completely
ignores the reward distributions, and attempts to give equal time share to
each group. In other words, each group receives a fraction of the tasks
inversely proportional to their mean completion times. There is clearly a
trade-off between the reward maximization and equal time-share considerations
in continuous-time sequential task allocation, and well-chosen utility
functions [12] can be helpful in modeling this in a unified way. In this
paper, we consider a very general class of utility functions, which recovers
broadly used fairness criteria such as proportional fairness, max-min
fairness, reward maximization among many others [13, 14, 12]. The controller
can determine her priorities in terms of notions of fairness and model the
task allocation problem by choosing the utility function accordingly.

The main contributions of this paper are summarized as follows:

  1. 1.

Incorporation of random completion time dynamics and fairness in allocation:
In discrete-time online learning models, each action is assumed to take a unit
completion time, thus the random and diverse nature of task completion times,
as required in many fundamental real-life applications, is ignored. In this
work, we incorporate this aspect and develop a sequential learning framework
in continuous time using tools from the theory of renewal processes and
stochastic control. We show how controlled deadlines improve the time-
efficiency in continuous-time decision processes. Moreover, this is the first
work, to the best of our knowledge, that analyzes fair distribution policies
in online contractual hiring.

  2. 2.

Characterization of Approximately Optimal Offline Policies: As a consequence
of the random and controlled task completion times, the optimal policy for
fair resource allocation is PSPACE-hard akin to unbounded stochastic knapsack
problems. For tractability in design and analysis, we propose an approximation
to the optimal offline policy based on Lagrange duality and renewal theory,
and prove that it is asymptotically optimal. These approximate policies
allocate tasks independently with respect to a fixed probability distribution.

  3. 3.

Online learning for utility maximization: For utility maximization in an
online setting with full information feedback, we develop a novel and low-
computational-complexity online learning algorithm based on dynamic stochastic
optimization methods for time averages, and show that it achieves
$\tilde{O}(B^{-1/2})$ regret for a time budget $B$. The optimal offline
control policy in this paper is time-dependent, randomized and attempts to
optimize time averages unlike the reward maximization problems in discrete-
time problems. Despite these, the online learning algorithm we developed
adapts to the randomness in completion time-reward pairs, and achieves optimal
performance with vanishing regret at a fast rate.

Related Work: The problem of fair resource allocation via utility maximization
has been widely considered in economics and network management [15, 16, 17,
18]. The utility maximization approach to fair resource allocation in these
papers predominantly deals with discrete-time systems, therefore the
randomness and diversity in task completion times is completely ignored.
Furthermore, these works either assume perfect knowledge of rewards and
completion times prior to decision-making, or they assume the knowledge of
statistics, therefore they do not incorporate online learning. The only
continuous-time utility maximization approach to fair resource allocation is
[19], which assumes the knowledge of first-order statistics. Our work utilizes
the offline optimization results in [19] for developing online learning
algorithms.

Online learning under budget constraints has been considered under the scope
of bandits with knapsacks [20, 21, 22]. In the classical bandits with
knapsacks model, the objective is to maximize expected total reward under
knapsack constraints in a stochastic setting. In [23], an interrupt mechanism
is employed to incorporate the continuous-time dynamics into the budget-
constrained online learning model. Note that these works focus solely on
reward maximization, therefore do not address the fair resource allocation
problem. The bandits with knapsacks setting was extended to concave rewards
and convex constraints in [24], which assumes bounded cost and reward, and the
deadline mechanism is not involved in decision-making, thus optimal time-
efficiency in continuous time is not achieved. Our paper deviates from this
line of work as it proposes a versatile and comprehensive framework for
fairness, and incorporates continuous-time dynamics into the decision-making
for time-efficiency. We include an extended discussion of related work in
Appendix A.

##  2 Online Learning Framework for Group Fairness

We consider the sequential and fair allocation of tasks to individuals from
different groups, whose completion times and rewards randomly vary. This goal
differs significantly from traditional online learning models that aim to
maximize the expected total reward with unit completion times. Under this
traditional setting, the controller’s goal is to find and persistently select
the reward-maximizing groups to allocate its tasks. As a consequence, the
reward-maximization objective leads to the starvation of suboptimal groups,
which causes unfairness amongst the groups with different statistical
characteristics. Next, we provide a few motivating examples with group
fairness requirements:

  * •

Contractual Hiring in Online Freelancing Platforms: Online freelancing sites
like Upwork host contractual workers (freelancers) that can be hired by
“contractors" who require specific tasks to be completed. Each freelancer has
a profile and performance on past tasks that can be learned by the contractors
via ratings and reviews (see, typical profile in Figure 1). Fixed-timed
contracts are popular on Upwork, wherein contractors enforce a deadline by
which the task must be completed otherwise the contract is terminated (i.e.,
there is no payment). Contractors can browse profiles and post a job to a
selected set of freelancers with a deadline. However, there is a large
literature documenting bias in online rating systems, which in turn impact job
opportunities disparately [11, 25, 26], thus making it critical to develop
theory of online learning for such settings.

  * •

Server Allocation in Cloud Computing: An important application of our
framework is online learning for fair resource allocation in cloud computing
systems. In a very basic setting, a single server is sequentially allocated to
tasks from one of $K$ user groups, which exhibit similar execution time
statistics and priority levels within each group. In many practical scenarios,
the execution time of a task is unknown at the time decision [27, 28], and
exhibits a power-law behavior [29], which necessitates a deadline mechanism
for optimal time-efficiency [23]. In this setting, the objective of the
controller is to allocate the server in an optimally fair way across the
groups in a given time interval $[0,B]$, depending on the completion time
statistics and priority levels. Our work proposes a versatile framework to
model fairness for this problem based on the concept of continuous-time
utility maximization, and develops online learning algorithms to achieve the
optimal performance with low regret in the absence of any statistical
knowledge.

More examples can be found in other domains, including multi-user wireless
communication over fading channels (e.g., see [23]), comparative clinical
trials with optimal follow-up duration (e.g., see [30, 31]), whereby the goal
is to fairly share the limited resources between groups of users.

Motivated by these examples, next we introduce an online learning framework
that expands the traditional setting substantially to incorporate group
fairness characteristics into its formulation. Suppose that there are $K\geq
1$ groups of individuals that are available for serving tasks with different
(and unknown) statistics. Specifically, if an individual from group
$k\in[K]=\\{1,2,\ldots,K\\}$ is chosen for the $n$-th task, he/she takes
$X_{k,n}$ units of completion time for successful completion, and a reward of
$R_{k,n}(t)=\overline{R}_{k,n}\mathbb{I}\\{X_{k,n}\leq t\\}$ is obtained $t$
time units after the initiation where $\overline{R}_{k,n}$ is a positive
random variable and $R_{k,n}(t)\in[0,R_{max}(t)]$ a.s. for some finite
constant $R_{max}(t)>0$. Thus, the random reward $\overline{R}_{k,n}$ is
gathered only if the task is completed. For example, in the server allocation
application, a group-$k$ task of random size $\overline{R}_{k,n}$ yields a
reward (throughput) $R_{k,n}(t)=\overline{R}_{k,n}\mathbb{I}\\{X_{k,n}\leq
t\\}$ only upon successful completion. We assume that $(X_{k,n},R_{k,n}(t))$
is independent and identically distributed (iid) over $n$, and independent
across different groups $k$. Note that the completion time $X_{k,n}$ and
reward $\overline{R}_{k,n}$ can be correlated, for example, in the server
allocation example, the completion time $X_{k,n}$ and size
$\overline{R}_{k,n}$ of a task are positively correlated [32]. We assume that
each task has a positive completion time, i.e., $X_{k,n}>0$ almost surely for
all $k,n$.

Before the $n$-th task begins, the controller makes two decisions: the group
$G_{n}\in[K]$ of the individual that will be assigned the task, and a deadline
$T_{n}\in\mathbb{T}$, where $\mathbb{T}\subset\mathbb{R}_{+}$ is the decision
set. If the task is not completed by the selected deadline, the service is
interrupted without collecting any reward. In many applications, the deadlines
are chosen within a discrete set (e.g., days/months in contractual hiring or
time-slots in server allocation), thus we assume a finite decision set
$\mathbb{T}=\\{t_{1},t_{2},\ldots,t_{L}\\}$ with $t_{l}<\infty$ for all $l$ in
this paper. The sequential task allocation continues until a given time budget
$B>0$ is exceeded, therefore, the completion time of a task is as important as
the reward.

To describe this process mathematically, let $\mathcal{H}_{k,n-1}$ denote the
available feedback for group $k$, and
$\mathcal{H}_{n-1}=\cup_{k\in[K]}\mathcal{H}_{k,n-1}$ denote the history
before making a decision for task $n$. For a given time budget $B>0$, a causal
policy $\pi=\\{\pi_{1},\pi_{2},\ldots\\}$ sequentially makes two decisions
$\pi_{n}=(G_{n},T_{n})\in[K]\times\mathbb{T}$ for each task $n$ based on the
history $\mathcal{H}_{k-1}$, where $G_{n}$ is the chosen group and $T_{n}$ is
the assigned deadline. Under a policy $\pi$, the number of initiated tasks is
the following first-passage time:

$N^{\pi}(B)=\inf\Big{\\{}n:\sum_{i=1}^{n}\min\\{X_{G_{i},i},T_{i}\\}>B\Big{\\}},$
(1)

which is a random and controlled stopping time. Moreover, the reward rate of
any user type $k$ is:

$\overline{r}^{\pi}_{k}(B)=\mathbb{E}\Big{[}\frac{1}{B}\sum_{n=1}^{N_{\pi}(B)}\mathbb{I}\\{G_{n}=k\\}R_{k,n}(T_{n})\Big{]},\text{
under policy }\pi.$ (2)

If $R_{k,n}(t)=\mathbb{I}\\{X_{k,n}\leq t\\}$, i.e., each task completion
yields a unit reward, then $\overline{r}_{k}^{\pi}(B)$ simply denotes the task
completion rate (i.e., throughput) of group $k$ individuals in the time
interval $[0,B]$.

Note that designing strategies that aim to maximize the total reward rate in
(2) will lead to the persistent selection of the group with the highest reward
rate at the cost of starvation of all the rest (see [23]). In order to address
group fairness considerations, we propose a continuous-time online learning
framework based on the utility maximization concept that is used effectively
in the fair resource allocation domain (e.g., see [16]). Specifically, for a
given continuously-differentiable, concave and monotonically increasing
utility function $U_{k}:\mathbb{R}\rightarrow\mathbb{R}$, we let the utility
of group $k$ under a policy $\pi$ be given by
$U_{k}\big{(}\overline{r}_{k}^{\pi}(B)\big{)}$. Then, the total utility under
a policy $\pi$ is defined as:

$U^{\pi}(B)=\sum_{k=1}^{K}U_{k}\big{(}\overline{r}^{\pi}_{k}(B)\big{)},\text{
for time interval }[0,B].$

The optimum utility over a class of policies $\Pi$, and the regret for a given
$\pi\in\Pi$ are, respectively:

${\tt
OPT}_{\Pi}(B)=\max_{\pi\in\Pi}~{}\sum_{k=1}^{K}U_{k}\big{(}\overline{r}^{\pi}_{k}(B)\big{)}\quad\text{
and }\quad{\tt REG}_{\Pi}^{\pi}(B)={\tt OPT}_{\Pi}(B)-U^{\pi}(B),\text{
for}~{}B>0.$ (3)

Note that, due to the monotonically increasing and concave nature of utility
functions, allocating the tasks always to the most rewarding group is not a
good choice, because the same amount of time could yield a higher utility for
another group because of the diminishing return property of concave functions.
A particularly important set of utility functions is captured by the
$\alpha$-fair class, given next.

######  Definition 1 ($\alpha$-Fair Allocation).

For any given $\alpha>0$ and weight $w_{k}>0$, let
$U_{k}(x)=w_{k}\frac{x^{1-\alpha}}{1-\alpha},$ for all $k$. Resource
allocation by using these utility functions is called $\alpha$-fair resource
allocation.

This class is attractive since it includes as special cases proportional
fairness, minimum potential delay fairness, reward maximization and max-min
fairness [12].

##  3 Approximation of the Optimal Offline Policy

Note that a simpler version of the sequential maximization problem in (3) with
linear utility functions over all causal policies is called an unbounded
knapsack problem, and it is PSPACE-hard even in the case of known statistics
[33, 20]. Therefore, the optimal causal policy for the problem in (3) has a
very high computational complexity even in the offline setting, which makes it
intractable for online learning. For tractability in design and analysis, we
consider a class of simple policies that allocate tasks in an i.i.d.
randomized way according to a fixed probability distribution over groups, and
show its efficiency in this section.

######  Definition 2 (Stationary Randomized Policies).

Let $P$ be a fixed probability distribution over $[K]\times\mathbb{T}$. A
stationary randomized policy (SRP) $\pi=\pi(P)$ makes a randomized decision
independently according to $P$ for every task until the time budget $B$ is
depleted. In other words, under the SRP $\pi(P)$, we have
$\mathbb{P}\big{(}\pi_{n}=(k,t)\big{)}=P(k,t),~{}\forall n\leq N_{\pi}(B),$
for all $(k,t)\in[K]\times\mathbb{T}$. We denote the class of all stationary
randomized policies as $\Pi_{S}$.

######  Proposition 1 (Asymptotic optimality of SRP).

There exists a probability distribution $P^{\star}$ such that the stationary
randomized policy $\pi(P^{\star})$ is asymptotically optimal over all causal
policies as $B\rightarrow\infty$.

The proof of Proposition 1 can be found in Appendix B. In the following, we
characterize the total utility under $\pi(P)$ by providing tight bounds.

######  Proposition 2.

Let $P$ be any given probability distribution over $[K]\times\mathbb{T}$.
Then, the reward per unit time for group $k$ under the stationary randomized
policy $\pi(P)$ is as follows:

$\rho_{k}(P)=\frac{\sum_{t\in\mathbb{T}}P(k,t)\mathbb{E}[R_{k,1}(t)]}{\sum_{(i,t)\in[K]\times\mathbb{T}}P(i,t)\mathbb{E}[\min\\{X_{i,1},t\\}]},\forall
k\in[K].$

Consequently, the total utility under the stationary randomized policy
$\pi(P)$ is bounded as follows:

$\sum_{k\in[K]}U_{k}\Big{(}\rho_{k}(P)\Big{)}\leq\sum_{k\in[K]}U_{k}\big{(}\overline{r}_{k}^{\pi(P)}(B)\big{)}\leq\sum_{k\in[K]}U_{k}\Big{(}\rho_{k}(P)\Big{)}+O\Big{(}\frac{1}{B}\Big{)}.$

We include the complete proof of Proposition 2 in Appendix B. The key idea is
that under an SRP, the total reward of a group $k$ is a regenerative process.
Then, by using the theory of stopped random walks for regenerative processes,
the reward per unit time under $\pi(P)$ is found as $\rho_{k}(P)$, and the
upper bound for the total utility is found by using Lorden’s inequality [34]
and concavity of $U_{k}$.

Proposition 2 emphasizes the significance of the reward per unit time
$\rho_{k}(P)$. In conjunction with Proposition 1, this suggests that using a
probability distribution that maximizes the limiting total utility would be an
effective offline approximation.

######  Definition 3 (Optimal Stationary Randomized Policy).

Let $P^{\star}$ be a probability distribution defined as
$P^{\star}\in\arg\max_{P}\sum_{k\in[K]}U_{k}\Big{(}\rho_{k}(P)\Big{)}$. Then,
the optimal SRP $\pi^{\star}$ makes a selection independently for every task
according to $P^{\star}$:
$\mathbb{P}\Big{(}\pi^{\star}_{n}=(k,t)\Big{)}=P^{\star}(k,t)$ for all
$(k,t)\in[K]\times\mathbb{T}$ and $n\leq N_{\pi}(B)$.

An interesting question regarding $P^{\star}$ is the choice of deadline policy
for each group. The following proposition characterizes the optimal deadline
policy under $\pi^{\star}$, and yields a significant simplification in finding
the optimal policy by reducing the size of the search space.

######  Proposition 3 (Optimal Deadline Policy).

For any $k$, the optimal probability distribution $P^{\star}$ makes a
deterministic deadline decision for group $k$, that is,
$|\\{t\in\mathbb{T}:P^{\star}(k,t)>0\\}|\leq 1$. For any $k$, we denote
$t_{k}^{*}\in\mathbb{T}$ as the (unique) optimal deadline for group $k$ such
that $P^{\star}(k,t_{k}^{*})>0$.

The detailed proof of Prop. 3 can be found in Appendix C. As we will see
later, we can explicitly characterize the optimal deadline for a broad class
of utility functions used for the so-called $\alpha$-fair allocations. In the
following, we use Prop. 2 to characterize the performance of the optimal SRP.

######  Proposition 4 (Optimal Total Utility).

For any group $k$, let $t_{k}^{*}\in\mathbb{T}$ be the (unique) optimal
deadline by Prop. 3;
$r_{k}^{*}=\mathbb{E}[R_{k,1}(t_{k}^{*})]/\mathbb{E}[\min\\{X_{k,1},t_{k}^{*}\\}]$
be the reward per processing time for group $k$; and

$\displaystyle\varphi_{k}=\frac{P^{\star}(k,t_{k}^{*})\cdot\mathbb{E}[\min\\{X_{k,1},t_{k}^{*}\\}]}{\sum_{j\in[K]}P^{\star}(j,t_{j}^{*})\cdot\mathbb{E}[\min\\{X_{j,1},t_{j}^{*}\\}]},$
(4)

be the fraction of time budget allocated to group $k$ under $\pi(P^{\star})$.
Then, for any SRP $\pi(P)$, the total utility is bounded as
$\sum_{k}U_{k}\Big{(}\rho_{k}(P)\Big{)}\leq\sum_{k}U_{k}\Big{(}(U_{k}^{\prime})^{-1}\big{(}\frac{\lambda}{r_{k}^{*}}\big{)}\Big{)},$
where the upper bound is achieved by the probability distribution that
satisfies
$\varphi_{k}=\frac{1}{r_{k}^{*}}(U_{k}^{\prime})^{-1}\big{(}\frac{\lambda}{r_{k}^{*}}\big{)}$
for $\lambda$ such that $\sum_{k}\varphi_{k}=1$.

The proof of Proposition 4 follows from Lagrange duality and Prop. 3, and can
be found in Appendix D. Note that the above analysis is very general in the
sense that it holds for any set of utility functions
$\\{U_{k}:\mathbb{R}\rightarrow\mathbb{R}:k\in[K]\\}$ that are continuously
differentiable and concave. In the following, we apply the results to the
class of $\alpha$-fair allocations (cf. Definition 1) and discuss their
implications.

######  Proposition 5 ($\alpha$-Fair Resource Allocation in Continuous Time).

For any group $k$, the optimal deadline is
$t_{k}^{*}=\displaystyle\arg\max_{t\in\mathbb{T}}~{}\frac{\mathbb{E}[R_{k,1}(t)]}{\mathbb{E}[\min\\{X_{k,1},t\\}]}.$
Also, let
$r_{k}^{*}=\max_{t\in\mathbb{T}}~{}\frac{\mathbb{E}[R_{k,1}(t)]}{\mathbb{E}[\min\\{X_{k,1},t\\}]}$
be the reward per processing time and
$\mu_{k}=\mathbb{E}[\min\\{X_{k,1},t_{k}^{*}\\}]$ be the mean processing time
for group $k$. Then, for any $\alpha>0$, we have the following results for
$\alpha$-fair utility functions:

$\displaystyle\max_{P}~{}U^{\pi(P)}(B)=\frac{1}{1-\alpha}\Big{(}\sum_{k\in[K]}(r_{k}^{*})^{\frac{1}{\alpha}-1}w_{k}^{\frac{1}{\alpha}}\Big{)}^{\alpha},$
(5)

where the optimum probability distribution $P_{k}^{*}$ and the optimum
fraction of time budget $\varphi_{k}$ allocated to group $k$ are,
respectively, given by:

$P^{\star}(k,t)=\mathbb{I}\\{t=t_{k}^{*}\\}\frac{w_{k}^{\frac{1}{\alpha}}(r_{k}^{*})^{\frac{1}{\alpha}-1}/\mu_{k}}{\sum_{j\in[K]}w_{j}^{\frac{1}{\alpha}}(r_{j}^{*})^{\frac{1}{\alpha}-1}/\mu_{j}},\quad\varphi_{k}=\frac{(r_{k}^{*})^{\frac{1}{\alpha}-1}w_{k}^{\frac{1}{\alpha}}}{\sum_{j\in[K]}(r_{j}^{*})^{\frac{1}{\alpha}-1}w_{j}^{\frac{1}{\alpha}}},\forall
k\in[K].$

To gain a clear understanding of the notion of $\alpha$-fairness, we consider
the following special cases.

######  Corollary 1.

For any given set of parameters $\\{w_{k}>0:k\in[K]\\}$, we have the following
results for continuous-time $\alpha$-fair resource allocation problem for
various $\alpha>0$ values.

  1. (i)

Proportional fairness: In this case, we have $\lim_{\alpha\rightarrow
1}U_{k}(x)=w_{k}\log(x)$ for all $k$. Let
$\mu_{k}=\mathbb{E}[\min\\{X_{k,1},t_{k}^{*}\\}]$ be the mean processing time
for group $k$. Then, the optimum utility is achieved by the probability
distribution
$P^{\star}(k,t)=\mathbb{I}\\{t=t_{k}^{*}\\}\frac{w_{k}/\mu_{k}}{\sum_{j\in[K]}w_{j}/\mu_{j}},~{}(k,t)\in[K]\times\mathbb{T},$
thus we have $\varphi_{k}=\frac{w_{k}}{\sum_{j\in[K]}w_{j}}$ for all $k$ and
${\tt
OPT}_{\Pi_{S}}(B)=\sum_{k}\log\Big{(}\frac{r_{k}^{*}w_{k}}{\sum_{k^{\prime}\in[K]}w_{k^{\prime}}}\Big{)}+O(\frac{1}{B})$.

  2. (ii)

Reward maximization: If $\alpha=0$, we have $U_{k}(x)=\omega_{k}x$ for all
$k$. Let $k^{*}=\arg\max_{k\in[K]}~{}w_{k}r_{k}^{*}$ be the group with highest
weighted reward rate. Then, the optimal probability distribution is
$P^{\star}(k,t)=\mathbb{I}\\{k=k^{*},~{}t=t_{k}^{*}\\},$ for all $(k,t)$.
Thus, ${\tt OPT}_{\Pi_{S}}(B)=\max_{k\in[K]}w_{k}r_{k}^{*}+O(1/B)$.

######  Remark 1.

Note that optimal deadline $t_{k}^{*}$ for any group $k$ is chosen so as to
maximize the reward per processing time of group $k$. Under proportional
fairness ($\alpha\rightarrow 1$), the controller distributes the time budget
proportional to group weights, i.e., $\varphi_{k}=w_{k}/\sum_{j}w_{k}$, which
reduces to equal time-sharing under uniform weights. To achieve this, the
controller allocates tasks with probability inversely proportional to the mean
processing time $\mu_{k}$. Under reward maximization ($\alpha=0$), the
controller allocates the entire time budget $B$ to a single group that yields
the highest reward per processing time to maximize the expected total reward,
i.e., $\varphi_{k}=\mathbb{I}\\{k=k^{*}\\}$. As such, the trade-off between
reward maximization and equal (i.e., reward-insensitive) time-sharing is
modeled by $\alpha$-fairness for any $\alpha\in[0,1)$. Further, the
$\alpha$-fair utility maximization framework includes max-min fairness
$(\alpha\rightarrow\infty)$ and minimum potential delay fairness $(\alpha=2)$
as subcases.

##  4 Online Learning for Utility Maximization (OLUM)

In the previous section, we provided key results on the asymptotically optimal
approximations to the offline utility maximization problem. In this section,
we will build on these to attack the online learning problem for continuous-
time fair allocation. In particular, we will propose a novel light-weight
online learning algorithm for the fair resource allocation problem based on
Lagrangian duality, and show that it achieves vanishing regret at rate
$\tilde{O}(B^{-1/2})$.

Feedback model: We assume a delayed full-information feedback model where the
completion time and reward of all groups for task $n$ are revealed to the
controller at stage $n+\tau$ for some delay $\tau\geq 1$.

This assumption holds approximately for our target applications. In
freelancing platforms, there are often multiple contractors that hire
freelancers for various tasks. It is often possible to get full information on
various freelancers due to employment by other companies and their reviews can
serve as the feedback for the controller. Competitions hosting websites like
Topcoder have also recently been catering to businesses who need fast-
prototyping using freelancers. In their business model, a controller might
invest in a few topcoders at a time, however, she can potentially get access
to updated rankings (quality and time to complete tasks) via topcoder
competitions over time. In server applications such as Amazon AWS and
Microsoft Azure as well, although a controller might be optimizing operations
on a local set of servers, they can request task performance data from a
centralized server or a scheduler after a delay in time [35]. This feedback
model already presents with technical challenges due to random completion
times, as we discuss next.

In order to design the online learning algorithm, let us define, for any
$(k,t)\in[K]\times\mathbb{T}$, the empirical estimates of the mean completion
time and reward after $n$ stages, respectively, as

$\displaystyle\widehat{\mu}_{k,n}(t)\>=\>\frac{1}{n}\sum_{i=1}^{n}\min\\{t,X_{k,i}\\},\qquad\text{and}\quad\widehat{\theta}_{k,n}(t)\>=\>\frac{1}{n}\sum_{i=1}^{n}R_{k,i}(t).$

######  Definition 4 (OLUM Algorithm).

For any $k$, let $Q_{k,0}=1$ and $Q_{k,i}$ be defined recursively as follows:

$Q_{k,i+1}=\Big{(}Q_{k,i}+\gamma_{k}(i)\min\\{X_{G_{i},i},T_{i}\\}-R_{k,i}(T_{i})\mathbb{I}\\{G_{i}=k\\}\Big{)}^{+},\qquad{i>0}$
(6)

where the auxiliary variable
$\gamma_{k}({i})=\big{(}U_{k}^{\prime}\big{)}^{-1}\Big{(}Q_{k,{i}}/V\Big{)},$
where $V>0$ is a design choice. Then, for the task $n$, the OLUM Algorithm,
denoted by $\pi^{\tt OLUM}$, makes the following decision:

$(G_{n},T_{n})\in\underset{(k,t)\in[K]\times\mathbb{T}}{\arg\max}~{}\frac{\widehat{\theta}_{k,n-\tau}(t)Q_{k,n}}{\widehat{\mu}_{k,n-\tau}(t)}.$

Upon observing the corresponding feedback, the controller updates $Q_{k,n+1}$
via (6).

Interpretation: The OLUM Algorithm aims to maximize the time-average reward
weighted with $Q_{k,n}$ at each round. Note that for any $k\in[K]$, if the
sequence $Q_{k,n}$ gets very big, then its reward rate is much smaller than
the optimal value, thus the controller tends to select that group. In other
words, the magnitude of $Q_{k,n}$ is a measure of the unfairness that group
$k$ has endured by stage $n$. The algorithm is designed so as to balance the
weights $Q_{k,n}$ to maximize the total utility.

In the following theorem, we prove regret bounds for the OLUM Algorithm.

######  Theorem 1 (Regret bounds for OLUM).

For any $V>0$ and constant delay $\tau$, the regret under $\pi^{\tt OLUM}$ is
bounded as ${\tt REG}_{\Pi_{S}}{{}^{\pi^{\tt
OLUM}}}(B)=O\Big{(}\sqrt{\frac{\log(B)}{B}}+\frac{V}{B}+\frac{1}{V}\Big{)}.$
By choosing $V=\Theta(\sqrt{B/\log(B)})$, we obtain ${\tt
REG}_{\Pi_{S}}{{}^{\pi^{\tt
OLUM}}}(B)=O(\sqrt{\log(B)/B})=\tilde{O}(1/\sqrt{B})$.

The proof is based on PAC bounds and stochastic dual optimization, and can be
found in Appendix E.

##  5 Simulations

We implemented the OLUM Algorithm on a fair resource allocation problem with
$K=2$ groups. In the application domains that we considered in Section 2, the
task completion times naturally follow a power-law distribution. For example,
in the server allocation example, empirical studies indicate that the
distribution of job execution times can be accurately approximated by a
Pareto(1, $\gamma)$ distribution with exponent $\gamma\in(0,2)$ [36].
Similarly, for the contractual online hiring setting, creativity of
individuals has been shown to follow a Pareto(1, $\gamma$) distribution with
exponent $\gamma>1$, where $\gamma$ is dependent on the field of expertise
[37]. Motivated by these applications, we consider the following group
statistics:

• Group 1: $X_{k,n}\sim\mbox{Pareto}(1,1.2)$ and
$R_{k,n}(t)=X_{k,n}^{0.6}\cdot\mathbb{I}\\{X_{k,n}\leq t\\}$ • Group 2:
$X_{k,n}\sim\mbox{Pareto}(1,1.4)$ and
$R_{k,n}(t)=X_{k,n}^{0.2}\cdot\mathbb{I}\\{X_{k,n}\leq t\\}$ The reward per
processing time as a function of the deadline is shown in Figure 2. Note that
the optimal deadline improves the reward per unit processing time.

Figure 2: (Left) Reward per processing time for each group. (Right) Fraction
of time budget assigned to Group-2 individuals under the OLUM Algorithm for
various fairness criteria.

For this setting, we implemented the OLUM Algorithm with parameter $V=20$, and
considered $\alpha$-fair resource allocation problems with various $\alpha$
values. In Figure 2, we present the simulation results for $\varphi_{2}$,
i.e., the average fraction of time budget $B$ allocated to Group-2
individuals, under the OLUM Algorithm. For these experiments, we chose
$w_{k}=1$ for $k=1,2$ and ran the OLUM Algorithm for 1000 trials for each set.
Note that the optimal reward per processing time of Group-1 individuals is
higher than that of Group-2 individuals, thus Group-1 is chosen for reward
maximization. Under proportional fairness, the time budget is equally
distributed between Group-1 and Group-2 individuals. We observe from Figure 2
that the OLUM Algorithm converges to the optimal operating points very fast,
which verifies the theoretical results we presented.

##  6 Conclusion

In this paper, we proposed a versatile and comprehensive framework for
continuous-time online resource allocation with fairness considerations, and
proposed a no-regret learning algorithm for this problem in a delayed full-
information feedback model. Note that although the full-information feedback
is available in many application scenarios, there are cases in which the
controller does not have an access to full feedback, thus a mechanism that
incorporates bandit feedback is required. The online learning framework
introduced in this paper can be extended to bandit feedback. One way to
achieve this might be to replace the empirical estimates with upper confidence
bounds in the OLUM Algorithm, which makes the analysis even more complicated.
We leave the design and analysis of bandit algorithms in this setting as a
future work.

## Broader Impact

Our work develops the theory of fair online learning, specifically analyzing
the impact of reward-maximizing allocation policies on opportunities for
different groups of people. Our proposal analyzes the trade-offs across
various allocation policies (ranging from profit maximizing to equal
opportunity for all), thus highlighting the choice of objectives that the
controllers should carefully consider. This work does not have any foreseeable
negative ethical or societal impact.

## References

  * [1] J. Zhao, T. Wang, M. Yatskar, V. Ordonez, and K.-W. Chang, “Men also like shopping: Reducing gender bias amplification using corpus-level constraints,” _arXiv preprint arXiv:1707.09457_ , 2017.
  * [2] T. Bolukbasi, K.-W. Chang, J. Y. Zou, V. Saligrama, and A. T. Kalai, “Man is to computer programmer as woman is to homemaker? debiasing word embeddings,” in _Advances in Neural Information Processing Systems_ , 2016, pp. 4349–4357.
  * [3] A. Caliskan, J. J. Bryson, and A. Narayanan, “Semantics derived automatically from language corpora contain human-like biases,” _Science_ , vol. 356, no. 6334, pp. 183–186, 2017.
  * [4] K. Lum and W. Isaac, “To predict and serve?” _Significance_ , vol. 13, no. 5, pp. 14–19, 2016.
  * [5] A. L. Washington, “How to argue with an algorithm: Lessons from the compas-propublica debate,” _Colo. Tech. LJ_ , vol. 17, p. 131, 2018.
  * [6] J. Kleinberg, “Inherent trade-offs in algorithmic fairness,” in _Abstracts of the 2018 ACM International Conference on Measurement and Modeling of Computer Systems_ , 2018, pp. 40–40.
  * [7] A. Chouldechova, “Fair prediction with disparate impact: A study of bias in recidivism prediction instruments,” _Big data_ , vol. 5, no. 2, pp. 153–163, 2017.
  * [8] G. Laumeister, “The next big thing in e-commerce: Online labor marketplaces,” _Forbes (Online)_ , 2014.
  * [9] H. Torry, “Coronavirus pandemic deepens labor divide between online, offline workers,” _Wall Street Journal_ , 2020.
  * [10] A. Teeley, “There are 57 million u.s. independent professionals — upwork wants them all to succeed,” _Built In Chicago_ , 2020.
  * [11] A. Hannák, C. Wagner, D. Garcia, A. Mislove, M. Strohmaier, and C. Wilson, “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_ , 2017, pp. 1914–1933.
  * [12] R. Srikant and L. Ying, _Communication networks: an optimization, control, and stochastic networks perspective_. Cambridge University Press, 2013.
  * [13] D. Bertsimas, V. F. Farias, and N. Trichakis, “On the efficiency-fairness trade-off,” _Management Science_ , vol. 58, no. 12, pp. 2234–2250, 2012\.
  * [14] K. Jain and V. V. Vazirani, “Eisenberg-gale markets: Algorithms and structural properties,” in _Proceedings of the thirty-ninth annual ACM symposium on Theory of computing_ , 2007, pp. 364–373.
  * [15] D. P. Palomar and M. Chiang, “A tutorial on decomposition methods for network utility maximization,” _IEEE Journal on Selected Areas in Communications_ , vol. 24, no. 8, pp. 1439–1451, 2006.
  * [16] A. Eryilmaz and R. Srikant, “Fair resource allocation in wireless networks using queue-length-based scheduling and congestion control,” _IEEE/ACM transactions on networking_ , vol. 15, no. 6, pp. 1333–1344, 2007.
  * [17] H. J. Kushner and P. A. Whiting, “Convergence of proportional-fair sharing algorithms under general conditions,” _IEEE Transactions on Wireless Communications_ , vol. 3, no. 4, pp. 1250–1259, 2004.
  * [18] D. Kahneman and R. H. Thaler, “Anomalies: Utility maximization and experienced utility,” _Journal of economic perspectives_ , vol. 20, no. 1, pp. 221–234, 2006.
  * [19] M. J. Neely, “Dynamic optimization and learning for renewal systems,” _IEEE Transactions on Automatic Control_ , vol. 58, no. 1, pp. 32–46, 2012\.
  * [20] A. Badanidiyuru, R. Kleinberg, and A. Slivkins, “Bandits with knapsacks,” _Journal of the ACM (JACM)_ , vol. 65, no. 3, pp. 1–55, 2018.
  * [21] L. Tran-Thanh, A. Chapman, A. Rogers, and N. R. Jennings, “Knapsack based optimal policies for budget–limited multi–armed bandits,” in _Twenty-Sixth AAAI Conference on Artificial Intelligence_ , 2012.
  * [22] A. Slivkins, “Introduction to multi-armed bandits,” _arXiv preprint arXiv:1904.07272_ , 2019.
  * [23] S. Cayci, A. Eryilmaz, and R. Srikant, “Learning to control renewal processes with bandit feedback,” _Proceedings of the ACM on Measurement and Analysis of Computing Systems_ , vol. 3, no. 2, pp. 1–32, 2019.
  * [24] S. Agrawal and N. R. Devanur, “Bandits with concave rewards and convex knapsacks,” in _Proceedings of the fifteenth ACM conference on Economics and computation_ , 2014, pp. 989–1006.
  * [25] A. Rosenblat, K. E. Levy, S. Barocas, and T. Hwang, “Discriminating tastes: Customer ratings as vehicles for bias,” _Available at SSRN 2858946_ , 2016\.
  * [26] A. Chakraborty, A. Hannak, A. J. Biega, and K. P. Gummadi, “Fair sharing for sharing economy platforms,” 2017.
  * [27] M. Harchol-Balter, “Task assignment with unknown duration,” in _Proceedings 20th IEEE International Conference on Distributed Computing Systems_. IEEE, 2000, pp. 214–224.
  * [28] R. Motwani, S. Phillips, and E. Torng, “Nonclairvoyant scheduling,” _Theoretical computer science_ , vol. 130, no. 1, pp. 17–47, 1994.
  * [29] M. Harchol-Balter and A. B. Downey, “Exploiting process lifetime distributions for dynamic load balancing,” _ACM Transactions on Computer Systems (TOCS)_ , vol. 15, no. 3, pp. 253–285, 1997.
  * [30] K. Kim and A. A. Tsiatis, “Study duration for clinical trials with survival response and early stopping rule,” _Biometrics_ , pp. 81–92, 1990.
  * [31] P. F. Thall, R. Simon, and S. S. Ellenberg, “Two-stage selection and testing designs for comparative clinical trials,” _Biometrika_ , vol. 75, no. 2, pp. 303–310, 1988.
  * [32] P. R. Jelenković and J. Tan, “Characterizing heavy-tailed distributions induced by retransmissions,” _Advances in Applied Probability_ , vol. 45, no. 1, pp. 106–138, 2013.
  * [33] C. H. Papadimitriou and J. N. Tsitsiklis, “The complexity of optimal queuing network control,” _Mathematics of Operations Research_ , vol. 24, no. 2, pp. 293–305, 1999.
  * [34] S. Asmussen, _Applied probability and queues_. Springer Science & Business Media, 2008, vol. 51.
  * [35] R. Zabolotnyi, P. Leitner, and S. Dustdar, “Profiling-based task scheduling for factory-worker applications in infrastructure-as-a-service clouds,” in _2014 40th EUROMICRO Conference on Software Engineering and Advanced Applications_. IEEE, 2014, pp. 119–126.
  * [36] M. Harchol-Balter, “The effect of heavy-tailed job size distributions on computer system design.” in _Proc. of ASA-IMS Conf. on Applications of Heavy Tailed Distributions in Economics, Engineering and Statistics_ , 1999.
  * [37] J. Kleinberg and M. Raghavan, “Selection problems in the presence of implicit bias,” _arXiv preprint arXiv:1801.03533_ , 2018.
  * [38] J. F. Nash Jr, “The bargaining problem,” _Econometrica: Journal of the Econometric Society_ , pp. 155–162, 1950.
  * [39] J. W. Pratt, “Risk aversion in the small and in the large,” in _Uncertainty in Economics_. Elsevier, 1978, pp. 59–79.
  * [40] N. Nisan and A. Ronen, “Computationally feasible vcg mechanisms,” _Journal of Artificial Intelligence Research_ , vol. 29, pp. 19–47, 2007\.
  * [41] J. Mo and J. Walrand, “Fair end-to-end window-based congestion control,” _IEEE/ACM Transactions on networking_ , vol. 8, no. 5, pp. 556–567, 2000\.
  * [42] F. Kelly, “Charging and rate control for elastic traffic,” _European transactions on Telecommunications_ , vol. 8, no. 1, pp. 33–37, 1997.
  * [43] L. Tassiulas and A. Ephremides, “Jointly optimal routing and scheduling in packet ratio networks,” _IEEE Transactions on Information Theory_ , vol. 38, no. 1, pp. 165–168, 1992.
  * [44] ——, “Dynamic server allocation to parallel queues with randomly varying connectivity,” _IEEE Transactions on Information Theory_ , vol. 39, no. 2, pp. 466–478, 1993.
  * [45] M. J. Neely, “A lyapunov optimization approach to repeated stochastic games,” in _2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton)_. IEEE, 2013, pp. 1082–1089.
  * [46] M. Neely, _Stochastic network optimization with application to communication and queueing systems_. Morgan & Claypool Publishers, 2010.
  * [47] S. Agrawal and N. Devanur, “Linear contextual bandits with knapsacks,” in _Advances in Neural Information Processing Systems_ , 2016, pp. 3450–3458.
  * [48] K. A. Sankararaman and A. Slivkins, “Combinatorial semi-bandits with knapsacks,” _arXiv preprint arXiv:1705.08110_ , 2017.
  * [49] A. Gut, _Stopped random walks_. Springer, 2009.
  * [50] S. Cayci, A. Eryilmaz, and R. Srikant, “Budget-constrained bandits over general cost and reward distributions,” _arXiv preprint arXiv:2003.00365_ , 2020.
  * [51] M. J. Wainwright, _High-dimensional statistics: A non-asymptotic viewpoint_. Cambridge University Press, 2019, vol. 48.
  * [52] B. Hajek, “Hitting-time and occupation-time bounds implied by drift analysis with applications,” _Advances in Applied probability_ , vol. 14, no. 3, pp. 502–525, 1982.

##  Appendix A Related Work

Fair resource allocation via utility maximization has been widely studied in
economics [38, 39, 18], mechanism design [40], network management [15, 41, 16,
12, 42] among many other fields. Particularly, logarithmic utility
maximization was introduced in [38] for the "Nash bargaining solution" to a
bargaining game among multiple players over the allocation of a shared
resource, and it was used in the management of communication networks in [41].
As a unifying framework, the class of $\alpha$-fair (also known as
"isoelastic") utility functions was proposed for fair allocation in economics
in [39]. The main methodology for fair resource allocation in time-varying
dynamical systems, akin to the system considered here, is Lyapunov drift
analysis. Lyapunov drift has been used as a fundamental design and analysis
tool in many problems including the wireless scheduling problem [43, 44], fair
resource allocation among competing users [16, 12], stochastic game theory
[45]. Based on Lyapunov-drift methods, stochastic dynamic optimization
algorithms by using the so-called drift-plus-penalty method were widely used
in queueing and networking problems (see [46] and references therein). The
existing Lyapunov optimization methods are predominantly opportunistic, which
means that the random quantities (such as completion time, reward, system
state) arrive prior to the decision-making at each stage, or they assume the
knowledge of the first- and second-order statistics of these random
quantities. These assumptions are not satisfied in many applications as we
discussed in Section 1, therefore the controller must learn the statistics so
as to maximize the objective function, such as the total utility. To the best
of our knowledge, our paper is the first learning theory approach to the fair
resource allocation problem based on Lyapunov drift. Even in the offline
optimization setting, the Lyapunov optimization methods are predominantly in
discrete-time setting, i.e., each action takes a unit time. The only
continuous-time utility maximization approach to fair resource allocation is
[19], which assumes the knowledge of first-order statistics. Our paper
improves some of the results of this paper in the offline optimization
scenario (e.g., simplified decision rules, finite-time performance bounds),
and extends these results for the online learning problem.

The online learning problem under budget constraints has been considered in
the bandits with knapsacks (BwK) framework [20]. In this extension of the
classical stochastic bandit model, each action consumes a random amount of a
resource from a common budget and yields a random reward, where the controller
aims to maximize the expected total reward by until a resource is completely
depleted. BwK model has been considered under various dynamics [20, 47, 48,
21]. In [23], an interrupt/deadline mechanism is employed to incorporate the
continuous-time dynamics into the budget-constrained online learning model.
For a detailed discussion of the BwK and its extensions, please refer to [22].
The original BwK models study the reward maximization problem. In [24], the
authors consider an online learning setting where the objective is to maximize
a concave function subject to convex constraints. In [24], the decision-making
process continues for a fixed number of stages, and the constraints are not
always satisfied unlike our model. Instead, the distance to the constraint
set, as well as the regret, is shown to vanish in expectation under the
proposed learning algorithms, which require solving linear programs at each
stage. Another crucial difference is that the deadline mechanism for improving
time-efficiency is not incorporated into the decision in [24]. Our paper
deviates from this line of work as it proposes a versatile and comprehensive
framework for fairness, and incorporates continuous-time dynamics into the
decision-making for time-efficiency under strict time constraints. To solve
this problem, we propose a learning algorithm with low computational
complexity, and prove its efficiency. The design and analysis methodology we
followed in this paper based on Lyapunov optimization can be used in many
other problem models.

##  Appendix B Proofs of Proposition 1 and Proposition 2

###### Proof of Proposition 2.

Fix any (group, deadline) decision $(k,t)\in[K]\times\mathbb{T}$, and consider
the stationary policy $\pi=\pi(P)$ with an arbitrary probability distribution
$P$. Let the number of $(k,t)$ decisions in $[0,B]$ be defined as

$N^{(k,t)}_{\pi}(B)=\sum_{n=1}^{N_{\pi(P)}(B)}\mathbb{I}\\{\pi_{n}=(k,t)\\}.$

Since each decision is made independently according to the same probability
distribution, the number of tasks between two consecutive tasks for which the
decision is $(k,t)$ is iid, which implies that $N^{(k,t)}_{\pi}(B)$ is a
regenerative process [34]. Therefore, we can compute the total reward gathered
from tasks for which the decision-pair is $(k,t)$ by using renewal theory. In
order to accomplish this, we will compute the mean length of a regenerative
cycle for each decision $(k,t)$, and then use the renewal theory for tight
bounds.

Without loss of generality, consider a regenerative cycle from the beginning
(time 0) to the completion of the first task where the decision-pair is
$(k,t)$, thus each regenerative cycle contains exactly one task for which the
decision-pair is $(k,t)$. Then, for the random variable $M=\sup\\{n\geq
0:\pi_{n}(P)\neq(k,t)\\}$, the number of tasks in a regenerative cycle is
$M+1\sim Geo\big{(}P(k,t)\big{)}$. This construction implies that
$\\{M=0\\}=\\{\pi_{1}(P)=(k,t)\\}$ and
$\\{M=m\\}=\bigcap_{i=1}^{m}\\{\pi_{i}(P)\neq(k,t)\\}\cap\\{\pi_{M+1}(P)=(k,t)\\}$
for $m>1$ under the stationary randomized policy $\pi(P)$. Therefore, the
length of the regenerative cycle (i.e., the time interval in which there is
exactly one completed task with decision-pair $(k,t)$) is as follows:

$Y=\sum_{n=1}^{M}\sum_{(k^{\prime},t^{\prime})\neq(k,t)}\mathbb{I}\\{\pi_{n}=(k^{\prime},t^{\prime})\\}(X_{k^{\prime},n}\wedge
t^{\prime})+(X_{k,M}\wedge t),$

where $x\wedge y=\min\\{x,y\\}$ for any two real numbers $x,y$. Note that $Y$
is a stopped random walk with non-i.i.d. increments and a controlled stopping
time $M+1$. We will compute the expectation of this quantity first. By
iterated expectation, we have the following equality:

$\mathbb{E}[Y]=\sum_{n_{0}=0}^{\infty}\mathbb{P}(M=n_{0})\mathbb{E}[Y|M=n_{0}].$
(7)

Note that for any $n_{0}\geq 0$, we have:

$\mathbb{E}[\mathbb{I}\\{\pi_{n}=(k^{\prime},t^{\prime})\\}|M=n_{0}]=\mathbb{P}(\pi_{n}=(k^{\prime},t^{\prime})|\pi_{n}\neq(k,t))=\frac{P(k^{\prime},t^{\prime})}{1-P(k,t)},$

for all $n\leq n_{0}$. Therefore, we have the following identity:

$\mathbb{E}[Y|M=n_{0}]=n_{0}\sum_{(k^{\prime},t^{\prime})\neq(k,t)}\frac{P(k^{\prime},t^{\prime})\mu(k^{\prime},t^{\prime})}{1-P(k,t)}+\mu(k,t),~{}~{}\forall
n_{0}\leq 0,$ (8)

where $\mu(k,t)=\mathbb{E}[X_{k,1}\wedge t]$. Thus, we have the following:

$\displaystyle\mathbb{E}[Y]$
$\displaystyle=\sum_{n_{0}=0}^{\infty}\mathbb{P}(M=n_{0})n_{0}\sum_{(k^{\prime},t^{\prime})\neq(k,t)}\frac{p(k^{\prime},t^{\prime})\mu(k^{\prime},t^{\prime})}{1-p(k,t)}+\mu(k,t),$
$\displaystyle=\mathbb{E}[M]\sum_{(k^{\prime},t^{\prime})\neq(k,t)}\frac{p(k^{\prime},t^{\prime})\mu(k^{\prime},t^{\prime})}{1-p(k,t)}+\mu(k,t).$

from (7). Since $M+1\sim Geo(P(k,t))$, we have
$\mathbb{E}[M]=\frac{1}{p(k,t)}-1$. Substituting this into the above identity,
we find the expected length of a regenerative cycle under $\pi(P)$ as follows:

$\mathbb{E}[Y]=\frac{\sum_{k^{\prime},t^{\prime})\neq(k,t)}P(k^{\prime},t^{\prime})\mu(k^{\prime},t^{\prime})}{P(k,t)}.$

In summary, a decision-pair $(k,t)$ is chosen once in a cycle of $Y$ time
units, and yields a reward $R_{k,n}(t)$ under the stationary randomized policy
$\pi(P)$. Having specificed mean length of a regenerative cycle and mean
reward, we can now compute the reward rate (i.e., reward per unit time) for a
decision-pair $(k,t)$ under $\pi(P)$ as follows:

$\displaystyle
r_{k}(t)=\frac{\mathbb{E}[R_{k,1}(t)]}{\mathbb{E}[Y]}=\frac{P(k,t)\mathbb{E}[R_{k,1}(t)]}{\sum_{(i,t^{\prime})\in[K]\times\mathbb{T}}P(i,t^{\prime})\mathbb{E}[\min\\{X_{i,1},t^{\prime}\\}]}.$

As an immediate consequence, the reward per unit time for group $k$ under
$\pi(P)$ is as follows:

$\rho_{k}(P)=\sum_{t\in\mathbb{T}}r_{k}(t).$

As a consequence of the elementary renewal theorem [49], the total reward for
group $k$ under $\pi(P)$ in $[0,B]$ is $B\rho_{k}(P)+o(B)$. In order to get
tight bounds, we use Lorden’s inequality to obtain the following inequalities:

$B\rho_{k}(P)\leq\sum_{n=1}^{N_{\pi}(B)}\sum_{t\in\mathbb{T}}\mathbb{I}\\{\pi_{n}=(k,t)\\}R_{k,n}(t)\leq
B\rho_{k}(P)+C(k,t),$

for a constant $C(k,t)<\infty$ since $Var(X_{k,n}\wedge t)<\infty$ and
$Var(R_{k,n}(t))<\infty$ for all $t\in\mathbb{T}$ [34]. Therefore,

$\rho_{k}(P)\leq\overline{r}_{k}^{\pi}(B)\leq\rho_{k}(P)+\frac{C(k,t)}{B}.$

Since $U_{k}$ is continuously differentiable and concave, we have the
following result:

$U_{k}(\rho_{k}(P))\leq U_{k}(\overline{r}_{k}^{\pi}(B))\leq
U_{k}(\rho_{k}(P))+U_{k}^{\prime}\Big{(}\rho_{k}(P)\Big{)}\frac{C(k,t)}{B},$

which concludes the proof. ∎

###### Proof of Proposition 1.

First, we will show an approximation to the optimization problem in (3) based
on Jensen’s inequality as in [19].

######  Lemma 1.

For any $k\in[K]$, $n\geq 1$ and a causal policy $\pi$ for choosing
$(G_{n},T_{n},(\gamma_{k,n})_{k\in[K]})$, let

$\displaystyle\widetilde{X}_{\pi_{n},n}$
$\displaystyle=\min\\{X_{G_{n},n},T_{n}\\},$ (9) $\displaystyle Z_{\pi_{n},n}$
$\displaystyle=\min\\{X_{G_{n},n},T_{n}\\}\sum_{m=1}^{K}U_{m}(\gamma_{m,n}),$
(10) $\displaystyle Y_{\pi_{n},m,n}$
$\displaystyle=\min\\{X_{G_{n},n},T_{n}\\}\gamma_{m,n}-R_{m,n}(T_{n})\mathbb{I}\\{G_{n}=m\\},~{}\forall
m\in[K].$ (11)

Let $U^{*}$ be the solution to the following optimization problem:

$\displaystyle\max_{\pi\in\Pi_{A}}\quad\lim_{N\rightarrow\infty}\frac{\sum_{n=1}^{N}\mathbb{E}[Z_{\pi_{n},n}]}{\sum_{n=1}^{N}\mathbb{E}[\widetilde{X}_{\pi_{n},n}]}\quad\mbox{s.t.}\quad\lim_{N\rightarrow\infty}\frac{\sum_{n=1}^{N}\mathbb{E}[Y_{\pi_{n},m,n}]}{\sum_{n=1}^{N}\mathbb{E}[\widetilde{X}_{\pi_{n},n}]}\leq
0,~{}\forall m=1,2,\ldots,K.$ (12)

where the maximization is over $\Pi_{A}$, the set of all causal policies.
Then, we have the following result:

$\lim_{B\rightarrow\infty}{\tt OPT}_{\Pi_{A}}(B)=U^{*}.$

###### Proof.

First, under any policy $\pi\in\Pi_{A}$, the following holds by the definition
of $N^{\pi}(B)$:

$\sum_{n=1}^{N^{\pi}(B)-1}\widetilde{X}_{\pi_{n},n}<B\leq\sum_{n=1}^{N^{\pi}(B)}\widetilde{X}_{\pi_{n},n}.$

Since $\widetilde{X}_{\pi_{n},n}$ is bounded for all $n$, we have the
following:

$\lim_{B\rightarrow\infty}\overline{r}_{k}^{\pi}(B)=\lim_{B\rightarrow\infty}\frac{\mathbb{E}\Big{[}\sum_{n=1}^{N_{\pi}(B)}\mathbb{I}\\{G_{n}=k\\}R_{k,n}(T_{n})\Big{]}}{\mathbb{E}\Big{[}\sum_{n=1}^{N_{\pi}(B)}\widetilde{X}_{\pi_{n},n}\Big{]}}$
(13)

By using the asymptotic equality in (13), continuity of $U_{k}$, and a direct
application of the extended Jensen’s inequality (see Lemma 7.6 in [46]), we
have $\lim_{B\rightarrow\infty}{\tt OPT}_{\Pi_{A}}(B)=U^{*}$. This enables us
to convert the utility maximization problem into a constrained optimization
for time-averages. ∎

Now, we will prove the following:

$\max_{P}\sum_{k\in[K]}U_{k}\big{(}\rho_{k}(P)\big{)}=U^{*}.$

Since $U^{*}$ is optimal asymptotic total utility over
$\Pi_{A}\supset\Pi_{S}$, we have the following inequality:

$\max_{P}\sum_{k\in[K]}U_{k}\big{(}\rho_{k}(P)\big{)}\leq U^{*}.$

By using (13), a direct application of Lemma 1 in [19] implies that there
exists an SRP $\pi(P_{0})$ that achieves $U^{*}$. Proposition 2 implies that

$\sum_{k}U_{k}(\overline{r}_{k}^{\pi(P^{\prime})}(B))\leq\max_{P}~{}\sum_{k}U_{k}(\rho_{k}(P))+O(1/B),$

for any $P^{\prime}$ and $B>0$. Thus, we have:

$U^{*}=\lim_{B\rightarrow\infty}\sum_{k}U_{k}\Big{(}\overline{r}_{k}^{\pi(P_{0})}(B)\Big{)}\leq\max_{P}~{}\sum_{k}U_{k}(\rho_{k}(P)),$

which implies $U^{*}=\max_{P}~{}\sum_{k}U_{k}(\rho_{k}(P))$. ∎

##  Appendix C Proof of Proposition 3

Let $\mu(k,t)=\mathbb{E}[\min\\{X_{k,1},t\\}]$ and
$\theta(k,t)=\mathbb{E}[R_{k,1}(t)]$. For the optimal distribution
$P^{\star}$, let

$C_{k}=\sum_{k^{\prime}\neq
k}\sum_{t\in\mathbb{T}}P^{\star}(k^{\prime},t)\mu(k^{\prime},t),$

$P^{\star}_{k}=[P^{\star}(k,t)]_{t\in\mathbb{T}}$ and
$p_{k}=\sum_{t\in\mathbb{T}}P^{\star}(k,t)$. Then, since $U_{k}(x)$ is an
increasing function of $x$, $P^{\star}_{k}$ is the solution to the following
optimization problem:

$\displaystyle\begin{aligned}
\max\limits_{P_{k}}~{}~{}\frac{\sum_{t}P_{k}(t)\theta(k,t)}{\sum_{t}P_{k}(t)\mu(k,t)+C_{k}}~{}~{}~{}\mbox{
subject to }~{}~{}~{}&P_{k}(t)\geq 0,\forall t,\\\
&\sum_{t}P_{k}(t)=p_{k}.\end{aligned}$ (14)

Let $V^{*}$ be the optimum solution of (14), and
$V(P_{k})=\sum_{t}P_{k}(t)\theta(k,t)-V^{*}\Big{(}\sum_{t}P_{k}(t)\mu(k,t)+C_{k}\Big{)}$.
Then, the following optimization problem is equivalent to (3):

$\displaystyle\begin{aligned} \max\limits_{P_{k}}~{}~{}V(P_{k})~{}~{}~{}\mbox{
subject to }~{}~{}~{}&P_{k}(t)\geq 0,\forall t,\\\
&\sum_{t}P_{k}(t)=p_{k},\end{aligned}$ (15)

which, in turn, yields $P_{k}^{\star}$. For any $t\in\mathbb{T}$, we have
$\frac{\partial V}{\partial P_{k}(t)}=\theta(k,t)-V^{*}\mu(k,t)$. Let

$d^{*}=\max_{t}~{}\frac{\partial V(P_{k})}{\partial
P_{k}(t)}\Big{|}_{P_{k}=P_{k}^{\star}}.$

By the optimality of $P_{k}^{\star}$, if $P_{k}^{\star}(t)>0$, then we must
have $\partial V(P_{k}^{\star})/\partial P_{k}(t)=d^{*}$, which further
implies that

$P_{k}^{\star}(t)>0\Rightarrow\theta(k,t)=d^{*}+V^{*}\mu(k,t).$ (16)

Let $t_{1}\leq t_{2}\leq\ldots\leq t_{m}$ be the set of deadlines such that
$P_{k}^{\star}(t_{i})>0$. There exists a $\beta\in[0,1]$ such that the
following holds:

$\sum_{t}P_{k}^{\star}(t)\theta(k,t)=p_{k}\Big{(}\beta\theta(k,t_{1})+(1-\beta)\theta(k,t_{m})\Big{)}.$

In conjunction with (16), this implies that:

$\sum_{t}P_{k}^{\star}(t)\mu(k,t)=p_{k}\Big{(}\beta\mu(k,t_{1})+(1-\beta)\mu(k,t_{m})\Big{)}.$

Hence, we have shown that $P_{k}^{\star}$ makes a randomization between at
most two deadlines, which simplifies (15) considerably as a function of a
single variable $\beta\in[0,1]$. Rewriting (15) in terms of $\beta$ and taking
the derivative with respect to $\beta\in[0,1]$, we observe that the objective
function is either monotonically decreasing or increasing with $\beta$.
Therefore, $P_{k}^{\star}$ has only one non-zero element, i.e., the deadline
decision is made deterministically for group $k$.

##  Appendix D Proof of Proposition 4

By Proposition 3, for each group $k$, there is a unique optimal deadline
$t_{k}^{*}$. Let

$r_{k}^{*}=\frac{\mathbb{E}[R_{k,n}(t_{k}^{*})]}{\mathbb{E}[\min\\{X_{k,n},t_{k}^{*}\\}]},$

be the reward per processing time for group $k$ under the optimal deadline
selection. Then, by Proposition 2, we can express the reward per unit time as
follows:

$\rho_{k}(P)=r_{k}^{*}\widehat{\varphi}_{k}(P),$

where

$\widehat{\varphi}_{k}(P)=\frac{P(k,t_{k}^{*})\mathbb{E}[\min\\{X_{k,n},t_{k}^{*}\\}]}{\sum_{j\in[K]}P(j,t_{j}^{*})\mathbb{E}[\min\\{X_{j,n},t_{j}^{*}\\}]},$

is the fraction of time allocated to group $k$ under $\pi(P)$. Note that for
any $P$, $\\{\widehat{\varphi}_{k}(P):k\in[K]\\}$ defines a probability
distribution in the $K$-dimensional simplex. Therefore, by Proposition 2, the
asymptotically optimal utility is the solution to the following optimization
problem:

$\displaystyle\begin{aligned}
\max_{\varphi\in\mathbb{R}_{+}^{K}}~{}\sum_{k\in[K]}U_{k}(r_{k}^{*}\widehat{\varphi}_{k})~{}~{}~{}\mbox{s.t.}~{}~{}~{}&\sum_{k\in[K]}\widehat{\varphi}_{k}=1,\\\
&\widehat{\varphi}_{k}\geq 0,~{}\forall k\in[K].\end{aligned}$ (17)

The Lagrangian function associated with (17) is as follows:

$\mathcal{L}(\widehat{\varphi},\lambda)=\sum_{k\in[K]}U_{k}(r_{k}^{*}\widehat{\varphi}_{k})-\lambda\Big{(}\sum_{k\in[K]}\widehat{\varphi}_{k}-1\Big{)}.$

Since $U_{k}$ is a monotonically increasing and continuously differentiable
function for all $k$, by solving
$\frac{\partial\mathcal{L}}{\partial\widehat{\varphi}_{k}}=0,$ we obtain
$\widehat{\varphi}_{k}=(U_{k}^{\prime})^{-1}(\lambda/r_{k}^{*})$. As $U_{k}$
is concave for all $k$, the proof follows by applying KKT conditions.

##  Appendix E Proof of Theorem 1

The proof of Theorem 1 consists of two steps. In the first step, we analyze
the performance of the OLUM Algorithm for the constrained optimization of time
averages for any number of trials $N$ by using a drift-based dual ascent
optimization methodology [19, 46, 45]. In the second step, we show that the
number of tasks processed in $[0,B]$ is $O(B)$ with high probability to prove
the regret result.

The following concentration inequality will be used extensively throughout the
proof.

######  Lemma 2 ([50, 23]).

Let $X_{n}$ and $R_{n}$ be two sub-Gaussian random processes with means
$\mathbb{E}[X]>0$, $\mathbb{E}[R]$, and parameters $\sigma_{X}^{2}$ and
$\sigma_{R}^{2}$, respectively. Then, for any $\epsilon\in(0,\mathbb{E}[X])$,
we have the following:

$\mathbb{P}\Big{(}\Big{|}\frac{\sum_{i=1}^{n}R_{i}}{\sum_{i=1}^{n}X_{i}}-\frac{{E}[R]}{{E}[X]}\Big{|}>\frac{\epsilon(1+r)}{\mu}\Big{)}\leq
2\big{(}e^{-n\epsilon^{2}/\sigma_{X}^{2}}+e^{-n\epsilon^{2}/\sigma_{R}^{2}}\big{)},$
(18)

for any $r>\frac{\mathbb{E}[R]}{\mathbb{E}[X]}$ and
$\mu\leq\mathbb{E}[X]-\epsilon$.

Note that any bounded random variable $Z\in[0,a]$ is sub-Gaussian with
parameter $\sigma^{2}=a^{2}/4$ [51]. As we are dealing with bounded
$\min\\{X_{k,n},t\\}$ and $R_{k,n}(t)$, Lemma 2 is an essential result for the
proofs in this section.

In the second lemma, we provide an upper bound for the expectation of the dual
variables $Q_{n}=(Q_{1,n},Q_{2,n},\ldots,Q_{K,n})$.

######  Lemma 3.

Consider the dual variables defined in (6) under the OLUM Algorithm, and
without loss of generality assume $Q_{k,0}=1$ for all $k$. Then, we have the
following bound for any $n\geq 1$:

$\mathbb{E}[\sum_{k=1}^{K}Q_{k,n}]\leq
V\sum_{k\in[K]}U_{k}^{\prime}\Big{(}\frac{\min_{k,t}\mathbb{E}[R_{k,n}(t)]-\epsilon}{\max_{k\in[K]}\mathbb{E}[X_{k,n}]}\Big{)}+O(1/\epsilon),$
(19)

for any $V>0$ and
$\epsilon\in\big{(}0,\min_{k,t}\mathbb{E}[R_{k,n}(t)\big{)}$.

###### Proof.

For any $\epsilon\in\big{(}0,\min_{k,t}\mathbb{E}[R_{k,n}(t)\big{)}$, let

$A=\\{q:\sum_{k}q_{k}\geq
V\sum_{k\in[K]}U_{k}^{\prime}\Big{(}\frac{\min_{k,t}\mathbb{E}[R_{k,n}(t)]-\epsilon}{\max_{k\in[K]}\mathbb{E}[X_{k,n}]}\Big{)}+\max_{t}\overline{R}_{max}(t)\\}.$

Then, we have $\mathbb{E}[\sum_{k}Q_{k,n+1}-\sum_{k}Q_{k,n}|Q_{n}\in
A]\leq-\epsilon$. Also, note that $Q_{k,n+1}-Q_{k,n}$ is bounded almost
surely, i.e., sub-Gaussian. Thus, Theorem 2.3 in [52] implies the tail bounds
for $\sum_{k}Q_{k,n}$, which implies the result via
$\mathbb{E}[X\mathbb{I}\\{X>a\\}]=a\mathbb{P}(X>a)+\int_{a}^{\infty}\mathbb{P}(X>x)dx.$
∎

Step 1: Recall the equivalent form of the utility maximization problem in
Lemma 1. In this step, we will prove the following result under the OLUM
Algorithm:

$\displaystyle\frac{\mathbb{E}[\sum_{n=1}^{N}Z_{\pi_{n},n}]}{\mathbb{E}[\sum_{n=1}^{N}\widetilde{X}_{\pi_{n},n}]}$
$\displaystyle\geq U^{*}-O\Big{(}\sqrt{\frac{\log(N)}{N}}+\frac{1}{V}\Big{)},$
$\displaystyle\frac{\mathbb{E}[\sum_{n=1}^{N}Y_{\pi_{n},m,n}]}{\mathbb{E}[\sum_{n=1}^{N}\widetilde{X}_{\pi_{n},n}]}$
$\displaystyle\leq O(V/N),~{}m=1,2,\ldots,K.$

for any $N$. This will be done by showing that the OLUM Algorithm achieves
$\epsilon$-optimal Lyapunov drift with high probability for each decision,
thus achieves optimality fast as a result of the Lyapunov drift methodology.
For details on Lyapunov optimization, refer to [46].

For any group $k\in[K]$, let

$\displaystyle X_{k,n}^{*}$ $\displaystyle=\min\\{X_{G_{n},n},t_{k}^{*}\\},$
$\displaystyle Z_{k,n}^{*}$
$\displaystyle=\min\\{X_{k,n},t_{k}^{*}\\}\sum_{m=1}^{K}U_{m}(\gamma_{m,n}),$
$\displaystyle Y_{k,m,n}^{*}$
$\displaystyle=\min\\{X_{k,n},t_{k}^{*}\\}\gamma_{m,n}-R_{m,n}(t_{m}^{*})\mathbb{I}\\{k=m\\},~{}\forall
m\in[K].$

Note that these are the random variables in Lemma 1 under the optimal deadline
$t_{k}^{*}$ for each group $k$.

The proof relies on a novel online learning approach based on drift-based
optimization techniques. In this methodology, the dual variables $Q_{n}$ as
defined in (6) summarize how much the constraint is violated in the past. At
stage $n$, given the vector of dual variables $Q_{n}$, we have the drift-plus-
penalty ratio (DPPR), which is defined as follows:

$\Psi_{n}(k,Q_{n})=-V\frac{\mathbb{E}[Z_{k,n}^{*}]}{\mathbb{E}[\min\\{X_{k,n},t_{k}^{*}\\}]}+\sum_{m}Q_{m,n}\frac{\mathbb{E}[Y_{k,m,n}^{*}]}{\mathbb{E}[\min\\{X_{k,n},t_{k}^{*}\\}]}.$
(20)

The optimal algorithm therefore, aims to minimize the DPPR to achieve
optimality. Let the terms in DPPR related to the auxiliary variables
$\gamma_{m,n}$ be denoted as:

$\psi_{n}(\gamma_{n},Q_{n})=\sum_{m=1}^{K}\big{(}-VU_{m}(\gamma_{m,n})+Q_{m,n}\gamma_{m,n}\big{)}.$
(21)

Therefore, the DPPR can be written as follows:

$\Psi_{n}(k,Q_{n})=\psi_{n}(\gamma_{n},Q_{n})-Q_{k,n}\frac{\mathbb{E}[R_{k,n}(t_{k}^{*})]}{\mathbb{E}[\min\\{X_{k,n},t_{k}^{*}\\}]}.$
(22)

The classical drift-based stochastic optimization techniques either assume the
knowledge of the first-order moments in $\Psi_{n}(k,G_{n})$, or they observe
the outcomes for the completion of task $n$ prior to the decision. However, in
online learning, since we have no prior knowledge of the mean values
$\mathbb{E}[R_{m,n}(t_{m}^{*})]$ and
$\mathbb{E}[\min\\{X_{k,n},t_{k}^{*}\\}]$, we define the empirical reward-per-
processing-time as follows:

$\widehat{r}_{k,n}(t)=\frac{\sum_{i=1}^{n-\tau}R_{k,i}(t)}{\sum_{i=1}^{n-\tau}\min\\{X_{k,i},t\\}}.$
(23)

where $n-\tau$ is the number of samples available. Similarly, let

${r}_{k}(t)=\frac{\mathbb{E}[R_{k,i}(t)]}{\mathbb{E}[\min\\{X_{k,i},t\\}]}.$
(24)

The deadline is chosen so as to maximize the reward per processing time:

$\widehat{r}_{k,n}=\max_{t\in\mathbb{T}}~{}\widehat{r}_{k,n}(t).$

Let $\delta_{k}(t)=\max_{t^{\prime}}~{}r_{k}(t^{\prime})-r_{k}(t)$ and
$\delta(t)=\min_{(k,t):\delta_{k}(t)>0}~{}\delta_{k}(t)$. By using Lemma 2, it
can be shown that $T_{n}=t_{G_{n}}^{*}$ with probability at least
$1-e^{-n\Omega\big{(}\delta^{2}(t)\big{)}}$, i.e., the optimal deadline for
the chosen group $G_{n}$ is selected with high probability. With this
deadline-selection policy, the empirical drift-plus-penalty ratio (e-DPPR) is
defined as follows:

$\widehat{\Psi}_{n}(k,Q_{n})=\psi_{n}(\gamma_{n},Q_{n})-Q_{k,n}\widehat{r}_{k,n}.$
(25)

The OLUM Algorithm as defined in Definition 4 is based on minimizing the
e-DPPR in (25). The auxiliary variables in the OLUM Algorithm is chosen to
maximize $\psi_{n}(\gamma_{n},Q_{n})$ over $\gamma_{n}$, and the group
decision is independent of the choice of the auxiliary variables given
$Q_{n}$.

The following proposition quantifies the approximation error for using the
e-DPPR in the decision-making as a surrogate for the DPPR in the optimization.

######  Proposition 6.

For any given $\epsilon\in(0,\mu_{*})$, we have the following inequality for
the DPPR under the OLUM Algorithm:

$\Psi_{n}(G_{n},Q_{n})\leq\min_{k\in[K]}~{}\Psi_{n}(k,Q_{n})+\frac{2\epsilon(1+r^{*})}{\mu_{*}-\epsilon}\sum_{k}Q_{k,n}+h(Q_{n})O(n),$
(26)

where $\mathbb{E}[h(Q_{n})]=c_{1}e^{-c_{2}n\epsilon^{2}}$ for some constants
$c_{1},c_{2}>0$ and

$r^{*}=\max_{(k,t)}~{}\frac{\mathbb{E}[R_{k,n}(t)]}{\mathbb{E}[\min\\{X_{k,n}t\\}]}.$

The proof of Proposition 6 relies on the concentration result presented in
Lemma 2 and a PAC-type bound: let $k$ be a group such that
$\Psi_{n}(k,Q_{n})>\min_{j}\Psi_{n}(j,Q_{n})+\delta$ for any $\delta>0$ given
$Q_{n}$. Then,

$\mathbb{P}\big{(}G_{n}=k\big{|}Q_{n}\big{)}\leq\mathbb{P}\big{(}\big{|}\widehat{\Psi}_{n}(k,Q_{n})-{\Psi}_{n}(k,Q_{n})\big{|}>\delta/2\big{|}Q_{n}\big{)}\\\
+\mathbb{P}\big{(}\big{|}\widehat{\Psi}_{n}(k_{n},Q_{n})-{\Psi}_{n}(k_{n},Q_{n})\big{|}>\delta/2\big{|}Q_{n}\big{)},$

where $k_{n}=\arg\min_{j}\Psi_{n}(j,Q_{n})$. Then, a straightforward
application of Lemma 2 and union bound (over suboptimal groups) with
$\delta=\epsilon\cdot O(\sum_{k}Q_{k,n})$ for $\epsilon>0$ yield the result.

We have the following lemma, which will be key in the analysis of the learning
algorithm.

######  Lemma 4 ([46]).

Let $L(q)=\frac{1}{2}\sum_{m=1}^{K}q_{m}^{2}$ be the quadratic Lyapunov
function, and

$\Delta(Q_{n})=\mathbb{E}[L(Q_{n+1})-L(Q_{n})|Q_{n}],$

be the Lyapunov drift. Then, we have the following bound on the Lyapunov drift
for the problem (12):

$\Delta(Q_{n})\leq
D+\mathbb{E}[\sum_{k\in[K]}Q_{k,n}Y_{G_{n},k,n}\big{|}Q_{n}],$ (27)

for some constant $D>0$ under the OLUM Algorithm.

From Proposition 6 and Lemma 4 with
$\epsilon=\epsilon_{n}=\frac{2(1+r^{*})}{\mu_{*}}\sqrt{\frac{\beta\log(n)}{n}}$
for $\beta>2$, we have the following result:

$\Delta(Q_{n})-V\mathbb{E}[\min\\{X_{G_{n},n},T_{n}\\}\sum_{k}U_{k}(\gamma_{k,n})|Q_{n}]\leq
D\\\
+\mathbb{E}[\min\\{X_{G_{n},n},T_{n}\\}|Q_{n}]\Big{(}-VU^{*}+\epsilon_{n}\sum_{k}Q_{k,n}+\mathbb{E}[h(Q_{n})|Q_{n}]O(K\cdot
n)\Big{)}.$ (28)

where $D>0$ is a constant, and the RHS holds since there exists an optimal
stationary randomized policy for (12) which satisfies:

$\min_{k}\Psi(k,Q_{n})\leq\Psi(\tilde{G}_{n},Q_{n})=-VU^{*}.$

Following the methodology in [19] by taking the expectation in (28), we have:

$\mathbb{E}[L(Q_{n+1})-L(Q_{n})]-V\mathbb{E}[\min\\{X_{G_{n},n},T_{n}\\}\sum_{k}U_{k}(\gamma_{k,n})]\leq
B-VU^{*}\mathbb{E}[\min\\{X_{G_{n},n},T_{n}\\}]\\\
+\epsilon_{n}\max_{k\in[K]}\mathbb{E}[X_{k,n}]\sum_{k\in[K]}\mathbb{E}[Q_{k,n}]+O(K)n^{1-\beta},$
(29)

Summing the above over $n=0,1,\ldots,N-1$, dividing by $N$, and rearranging
terms, we have the following inequality:

$\frac{\mathbb{E}[\sum_{n=1}^{N}Z_{\pi_{n},n}]}{\mathbb{E}[\sum_{n=1}^{N}\widetilde{X}_{\pi_{n},n}]}\geq
U^{*}-\frac{2(1+r^{*})}{\mu_{*}}O\Big{(}\sqrt{\frac{\beta\log(N)}{N}}\Big{)}+\frac{D/\mu_{*}+O(N^{\beta-2})}{V}+\frac{\mathbb{E}[L(Q_{0})]}{V\mu_{*}N}.$
(30)

The second question we had was how much the constraint in (12) is violated.
From the update of the dual variables (6), we have the following:

$Q_{k,n+1}\geq Q_{k,n}+Y_{\pi_{n},k,n},$ (31)

Summing the above over all $n=0,1,\ldots,N-1$, we have:

$Q_{k,N}\geq Q_{k,0}+\sum_{n=1}^{N}Y_{G_{n},k,n}.$

Thus, we have:

$\frac{\mathbb{E}[Q_{k,N}]}{N\mu_{*}}\geq\frac{\mathbb{E}[\sum_{n=1}^{N}Y_{\pi_{n},k,n}]}{\mathbb{E}[\sum_{n=1}^{N}\min\\{X_{G_{n},n},T_{n}\\}]}.$
(32)

By Lemma 3, the following inequality holds:

$\frac{\mathbb{E}[Q_{k,N}]}{N}\leq O\Big{(}\frac{V}{N}\Big{)}.$

Hence, by choosing $V=\Theta(\sqrt{N/\log(N)})$, we show that the objective is
achieved with $O(\sqrt{\log(N)/N})$ gap, and the constraint is satisfied at a
rate $O(1/\sqrt{N\log(N)})$.

Step 2. In this step, we will show that the decision-making process continues
for $N^{\pi}(B)=\Theta(B)$ stages with high probability, which will conclude
the proof.

For any $B>0$, let $n_{0}(B)=\lceil 2B/\mu_{min}\rceil$. Then, under any
causal policy $\pi$, we have the following bound:

$\displaystyle{\tt REG}_{\Pi_{S}}^{\pi}(B)$
$\displaystyle=U^{*}-\frac{\mathbb{E}[\sum_{n=1}^{N^{\pi}(B)}Z_{\pi_{n},n}]}{B},$
$\displaystyle\leq
U^{*}-\frac{\mathbb{E}[\sum_{n=1}^{N^{\pi}(B)}Z_{\pi_{n},n}]}{\mathbb{E}[\sum_{n=1}^{N^{\pi}(B)}\widetilde{X}_{\pi_{n},n}]},$
(33) $\displaystyle\leq\frac{\mu^{*}\cdot
n_{0}(B)}{B}\Big{(}U^{*}-\frac{\mathbb{E}[\sum_{n=1}^{n_{0}(B)}Z_{\pi_{n},n}]}{\mathbb{E}[\sum_{n=1}^{n_{0}(B)}\widetilde{X}_{\pi_{n},n}]}+o(1)\Big{)},$
(34)

where $U^{*}={\tt OPT}_{\Pi_{S}}(B)+O(1/B)$ is the optimal utility in Lemma 1,
$\mu^{*}=\max_{k}\mathbb{E}[X_{k,n}]$, and (33) holds since
$\sum_{n=1}^{N^{\pi}(B)}X_{G_{n},n}\geq B$ by definition. In order to prove
(34), first note that

$\displaystyle\mathbb{E}\Big{[}\sum_{n=1}^{N^{\pi}(B)}\big{(}U^{*}\widetilde{X}_{\pi_{n},n}-Z_{\pi_{n},n}\big{)}\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}\sum_{n=1}^{\infty}\big{(}U^{*}\widetilde{X}_{\pi_{n},n}-Z_{\pi_{n},n}\big{)}\mathbb{I}\\{N^{\pi}(B)>n\\}\Big{]},$
$\displaystyle\leq\mathbb{E}\Big{[}\sum_{n=1}^{n_{0}(B)}\big{(}U^{*}\widetilde{X}_{\pi_{n},n}-Z_{\pi_{n},n}\big{)}\Big{]}+U^{*}\hskip-7.11317pt\sum_{n>n_{0}(B)}\mathbb{P}(N^{\pi}(B)>n)$
(35)

Since
$\\{N^{\pi}(B)>n\\}\subset\\{\sum_{i=1}^{n}\widetilde{X}_{\pi_{i},i}<B\\}$ by
definition and
$\mathbb{E}[\widetilde{X}_{\pi_{i},i}|\mathcal{H}_{i}]\geq\mu_{*}>0$ for all
$i$, we have:

$\mathbb{P}(N^{\pi}(B)>n)=\mathbb{P}(\sum_{i=1}^{n}\widetilde{X}_{\pi_{i},i}<B)\leq
e^{-n\Omega(1)},$

for all $n>n_{0}(B)$ by Azuma-Hoeffding inequality [51], which implies that
$n_{0}(B)$ is a high-probability upper bound for $N^{\pi}(B)$ under any causal
policy $\pi$. In other words, the decision-making process continues for at
most $n_{0}(B)$ turns with high probability since each action depletes a
positive amount from the time budget $B$. Consequently, we have

$\sum_{n>n_{0}(B)}\mathbb{P}(N^{\pi}(B)>n)\leq e^{-\Omega(B)}=o(1).$

Using this result and rearranging the terms in (35), we obtain the inequality
in (34). Furthermore, the constraints are satisfied at rate $O(V/B)$ for all
groups. Therefore, by using the result of Step 1 with $N=n_{0}(B)$ and noting
that $n_{0}(B)/B=\Theta(1)$, we conclude that ${\tt
REG}_{\Pi_{S}}^{\pi}(B)=O(\sqrt{\log(B)/B})$.