No-regret Algorithms for Fair Resource Allocation
Authors: Abhishek Sinha
Ativ Joshi
Rajarshi Bhattacharjee
Cameron N Musco
Mohammad Hajiesmaili
Venue: NeurIPS 2023 poster (2023)
Keywords: Online Learning
Bandit Algorithms
Learning Theory
TL;DR: We design an efficient online resource allocation policy to maximize the $\alpha$-fair utilities.

Abstract: We consider a fair resource allocation problem in the no-regret setting against an unrestricted adversary. The objective is to allocate resources equitably among several agents in an online fashion so that the difference of the aggregate $\alpha$-fair utilities of the agents achieved by an optimal static clairvoyant allocation and the online policy grows sublinearly with time. The problem inherits its difficulty from the non-separable nature of the global $\alpha$-fairness function. Previously, it was shown that no online policy could achieve a sublinear standard regret in this problem. In this paper, we propose an efficient online resource allocation policy, called Online Fair Allocation ($\texttt{OFA}$), that achieves sublinear $c_\alpha$-approximate regret with approximation factor $c_\alpha=(1-\alpha)^{-(1-\alpha)}\leq 1.445,$ for $0\leq \alpha < 1$. Our upper bound on the $c_\alpha$-regret for this problem exhibits a surprising \emph{phase transition} phenomenon -- transitioning from a power-law to a constant at the critical exponent $\alpha=\frac{1}{2}.$  Our result also resolves an open problem in designing an efficient no-regret policy for the online job scheduling problem in certain parameter regimes. Along the way, we introduce new algorithmic and analytical techniques, including greedy estimation of the future gradients for non-additive global reward functions and bootstrapping second-order regret bounds, which may be of independent interest.

No-regret Algorithms for Fair Resource Allocation
Abhishek Sinha, Ativ Joshi School of Technology and Computer Science Tata Institute of Fundamental Research Mumbai 400005, India abhishek. sinha@tifr www.etrrrrrrr...ieeeeeeeeeeeeeee .n ativ@cmi... ac
Rajarshi Bhattacharjee, Cameron Musco, Mohammad Hajiesmaili
Manning College of Information and Computer Sciences
University of Massachusetts Amherst (rbhattacharj,, cmusco, haj lajiesmaili)@cs umass. edu
Abstract
We consider fair resource allocation problem in the no-regret setting against an unrestricted adversary. The objective is to allocate resources equitably among several agents in online fashion so that the difference of the aggregate a-fair utilities of the agents achieved by an optimal static clairvoyant allocation and the online policy grows sublinearly with time. The problem inherits its difficulty from the non-separable nature of the global a- e--farness function. Previously, was shown that online policy could achieve sublinear standard regret in this problem. In this paper, we propose an efficient online resource allocation policy, called Online Fair Allocation (OFA), that achieves sublinear ca -pproxxxiee regret with approximation factor ca (1-a) a)--a)) S 1.445, for 0 a 1. The upper bound on the c, regret for this problem exhibits a surprising phase transition phenomenon constant the critical exponent 1/2. Our
transitioning from power-law result also resolves an open problem in designing an efficient no-regret policy for the online job scheduling problem in certain parameter regimes. Along the way, we introduce new algorithmic and analytical techniques, including greedy estimation of the future gradients for non-additive global reward functions and bootstrapping second-order regret bounds, which may be of independent interest.
Introduction
The notion of algorithmic fairness refers to learning algorithms that guarantee fair predictions when subjected to adversarially biased training data [Dwork et al., 2012]. Fairness has become a major criterion for designing and deploying large-scale learning algorithms that affect diverse user base. Since the training data could be highly skewed in practice, it is essential to make minimal assumptions about the data-generating process and design provably robust and fair learning policies. Guaranteeing fairness becomes even more challenging in the online learning setup as there is no distinction between the training and test data, and no assumption is made on the input data sequence. As an example. consider an online recruitment campaign where learning algorithm decides the target group (identified by, say, the tuple (race, gender, age)) to which an ad for a job vacancy is to be displayed. Suppose revenue-mane -axenne-mxximzzing recommendation algorithm concludes from past data that more revenue generated by showing the ad Group A compared to Group B. In that case, the ad-serving algorithm will eventually end up showing that ad exclusively to Group A while discriminating against Group users of a potential job opportunity [Hao, 2019]. One of the overarching goals of this paper to design efficient online learning policies that provably mitigate this algorithmic bias while maintaining efficiency irrespective of the past data seen so far (refer to Example B.I in the Appendix for closely-relates scheduling problem considered in this paper).
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Towards this goal, we consider generic online fair resouree allocation problem, which we call NOFRA (No- Regret Fair Resource Allocation). In this problem. a fixed set of resources needs to be equitably shared among agents over multiple rounds. Note that fairness is a complex, multidimensional, and essentially subjective concept. Several metrics have been introduced in the literature to quantify the degree of fairness in resource allocation, including ax-fainess [Lan et al., 2010], proportional fairness [Kelly, 1997, Mo and Walrand, 2000], max-min fairness [Radunovic and Le Boudec, 2007, Nace and Pióro. 2008], and Jain's fairness index [Jain et al., 1984]. In this paper, we consider the problem of maximizing the a-fairness function, in which the utility of each agent when allocated I units grows as R The parameter is restricted to the interval [0, 1). This same range of a has been studied earlier in game-theeretic set up by Altman et al. [2010].
On the hardness of the NOFRA problem: In the standard online learning setting, the cumulative reward accrued over a given time horizon is the sum of the rewards obtained at each round [Hazan, 2019]. In contrast, the objective in NOFRA is maximize the global a-fairmess function, which is equal to the sum of cumulative rewards of each agent raised to the power 1 - a, 0 s a < 1. Due to the power-law non-linearity, the objective function of NOFRA is non-separable with respect to time. Note that the non-separability of the objective function is essential to induce fairness in sequential allocations by incorporating the diminishing return property. However, this renders the NOFRA problem fundamentally different from standard online learning problems. In particular, Theorem 2 proves non-trivial lower bound to the approximation ratio achievable by any online learning policy for this problem. This lower bound does not hold in classic settings with additive rewards.
We show that despite its non-separable structure, the NOFRA problem can be approximately reduced to an online linear optimization problem with greedily defined sequence of reward vectors. The resulting problem can then be solved with an online convex optimization (OCO) policy with second-order regret bound. In particular, we make the following contributions:
Our contributions:
In Algorithm 1, we present an efficient online resource allocation policy, Online Fair Allocation (OFA), that approximately maximizes the aggregate a-fairesss function of the agents. We show that OFA achieves (1 -1-a)) < 1.445-aprooximate sublinear regret (Theorem 1). To the best of our knowledge, OFA is the first online policy that approximately maximizes the a-fairness against any adversary, which could even be adaptive.
In Theorem 2, we establish a lower bound to the approximation factor ca achievable by any online learning policy for the a-fair reward function. Our lower bound improves upon the prior best-known lower bound of Si Salem et al. [2022]. which established only that ca 1.
Technically, our proposed OFA policy optimizes the non-additive global reward function by greedily estimating the future gradients and using these estimates to construct an online linear optimization problem such that sublinear regret for this linear problem translates into sublinear approximate-regee regret for the global optimization problem. The linear optimization problem is then solved with online gradient ascent policy with adaptive step sizes. The resulting algorithm is simple and intuitive: we have weights on each user that decay as the user's 's cumulative reward increases.
On the analytical side, key challenge is that the online linear optimization problem has demand sequence (and hence, a gradient sequence) that depends on our past actions. We introduce new proof technique that controls the norm of the gradients in this setting that a tight second-order regret bound can be established. This technique applies generally to problems with states where the future gradients depend past actions.
We provide numerical simulation results supporting our theoretical conclusions and demon- strating the effectiveness of our approach in several applications of the NOFRA problem.
Related work: Several closely related works with non-additive reward functions appear in the online learning literature [Si Salem et al., 2022, Even-Dar et al., 2009, Rakhlin et al., 20. In the following, we explain why the NOFRA problem is fundamentally different from the existing studies. An extended literature review is given in Appendix A.
Closest to our work, Si Salem et al. [2022] considered the problem of designing fair online resource allocation policies. The authors showed that it is impossible to design a no-regret policy without restricting the set of admissible adversarial demand sequences. Given this negative result, the authors

---

proposed a no-regret policy using a primal-dual framework under the assumption of restricted adversary, which exhibits an essentially ii.d. stochastic-like fluctuation. In contrast, we design a robust policy with an approximate sublinear regret without restricting the adversary. Due to the significantly weaker assumption, our proposed policy and analysis are drastically different from that of Si Salem et al. [2022]. Even-Dar et al. [2009] considered maximizing a global concave objective function in the no-regret setup under the further assumption that the optimal offline reward is convex. They presented an approachabiltty-aseee policy in this setting and also proved the impossibility of achieving sublinear regret when the convexity condition is violated. Although the objective function in NOFRA is concave, we show that the optimal static offline reward function fails to be convex (see Appendix C.8). Hence, the policy of Even-Dee et al. [2009] does not apply to the NOFRA problem. Rakhlin et al. [2011] considered the problem of no-regret learnability for wide class of non-additive global functions. However, their results also do not apply to our setting as our problem is not no-regret learnable (see Theorem 2). Agrawal et al. [2016] considered the problem of maximizing concave utility function with the bandit information feedback and derived an efficient policy. However, their Õ(VT) regret bound holds only in the stochastic setting. Offline fair caching algorithms using the a fair utility function were proposed in Liu et al. [2020]. However, their policy cannot be used in the online setting due to the casually available information structure. Finally, the work by Paria and Sinha [2021], Bhattacharjee et al. [2020], Mukhopadhyay al. [2022] considered the online caching problem with the linear utility function. However, due to the non-linearity, extending their work to the a-fair utility function entails several technical challenges, which we resolve in this paper.
2 Problem Formulation
In this section, we give the general formulation of the NOFRA problem, along with examples of concrete resource allocation problems that fit into this framework.
Consider a set of agents among which a limited resource is to be fairly divided. Assume that the resource allocated to the 7h agent on the h round is represented by an N N-dimensional non-negative vector yi (t), where N is arbitrary. On every round f, the 1th agent requests an N-dimensional non-negative demand (or, reward) vector 2,, (t).). The demand vectors are revealed to an online allocation policy л at the end of each round. We make no assumption on the regularity of the demand vector sequence, which could be adversarial (c.f., Si Salem et al. [2022]). Before the N x m Fmm dimensional aggregate demand matrix xxt) = (z1 x2)) Tm. (t) ) for round t is revealed, the online resource allocation policy chooses non-negative N m dimensional allocation matrix v()) - (t). yt)),..... ..... yo (f) from the set of all feasible allocations A. The set of all feasible allocations is assumed to be convex (see Remark 2 below). The reward accrued by the agent i on round is given by the inner- inner-product (t), y1 (t)). which, without loss of generality, is assumed to be upper-bounded by one. The cumulative reward accrued by agent by the end of round is given by
Rt(t) = (t 1) (z:((), (x))), Vi,t,
(I)
where we set the initial condition (0) 1, vi. By iterating the above recursion, the cumulative reward (t) can be alternatively expressed as follows:
(t) 1+ v()()))))))))
(2)
1-1
We make two mild technical assumptions on the structure of the demand and allocation vectors.
Assumption 1. i (1)): 1 Vi,t, 1, for some constant 8 >>00 0. Assumption 2. Let 1 Nxm denote the N all-1 matrix. Then pl Nxm A for some constant μ > 0.
The above assumptions imply that it is possible to ensure non-zero reward for all agents all rounds. The assumptions are used in the regret analysis only (see Eq. (25)). Our proposed online policy is oblivious to the value of the parameters ó and p.
The utility of any user for a cumulative reward of R is given by the concave a-fair utility function 6: R. + R., defined as follows:
Rl-a
= (a) I-a'
R
(3)
'The rationale behind setting the initial cumulative rewards to nerozero values is to ensure that the utility function e remains continuously differentiable at any round t > 1.
3

---

for some constant 0 S a < 1.2 The faimess parameter a induces a trade-off between the desired efficiency and fairness by incorporating notion of diminishing return property in the global objective function. The static offline optimal allocation with larger leads to more equitable cumulative rewards [Bertsimas et al., 2012]. Setting a O reduces the problem to the "unfair" online linear optimization problem. Our objective is to design an online resource allocation policy æ = (v(()) that minimizes the regret for maximizing the aggregate utilities of all users compared to any fixed offline resource allocation strategy y" A. To be precise, assume that the offline, fixed resource allocation y yields a cumulative reward of R' (T) for a horizon of length T'ss 2 1. Then, our objective is design resource allocation policy which minimizes the c-approximate regret (which we refer to as c-regret for short) defined as:
Regret, ( - -C (R),
(4)
for some small constant e 2 1.3 In the case of standard regret (c 1), we drop the argument in the parenthesis. Note that, unlike the standard online convex optimization problem, in the NOFRA problem, the reward function global, in the sense that it is non separable across time [Even- Dar et al., 2009]. For this reason, it is necessary to consider the c-regret with 1, rather than the standard regret (i.e., with e= 1). This will become clear from Theorem 2, where we prove an explicit lower bound to the approximation factor achievable by any online policy for the global a-fair reward function. This lower bound implics a concrete lower bound on the achievable c. Our lower bound improves upon [Si Salem et al., 2022, Theorem 1], where it was shown that no online policy can achieve a sublinear standard regret for the NOFRA problem under an unrestricted adversary.
1, the offline benchmark ((R((T) itself becomes O(1), Vi. Hence, in this regime, a sublinear regret bound (4) becomes vacuous. Consequently, we restrict the fairness parameter a to the interval [0, 1).
Remark 1:
When
Remark 2: In the above problem definition, we assumed that the set of feasible allocations A is convex and thus that there are integrality constraints on the allocation, i.e., the components of the allocation matrix yt) are allowed to be fractional. However, in many combinatorial resource allocation problems, the allocation vector is required to be integral. In this case, the feasible action set A is naturally defined to be the convex hull of the integral actions. In Appendix C.6, we consider the setting with integrality constraints and extend our algorithm and analysis to design a randomized integral allocation policy with sublinear regret bound.
Motivating examples: The statement of NOFRA is fairly general, and by suitably choosing the reward and allocation vectors, many standard resource allocation problems can be reduced to NOFRA. In what follows, we highlight the example of fair shared caching [Bhattacharjee et al., 2020, Paria and Sinha, 2021]. We refer the readers to Appendix B for additional examples of online job scheduling and online matching.
(t)
User 1
y(t)
(t)
User 2
D D
IIII
Zm (t)
Shared cache of capacity
Library
User
Figure 1: The online shared caching problem
"Some authors define the a- fairaiesss function with an extra additive term, Le., (H) = R1---1 [Si Salem 1-a et al., 2022]. Note that, in the range 0 5 a 1, this alternative detinition changes the regret metric (4) only by an additive constant. We use the fairness function da (f) as it is positively homogeneous of degree (1 a) property that we exploit in our analysis.
'Our theoretical results and algorithms trivially extend to the w-weighted fairness function Σ, w. (T)) for some negative weight vector wi 0, Vi.

---

In the Online Shared Caching problem with a single shared cache, m users are connected to single cache of capacity & (see Figure I for a schematic). At each round, each user requests a file from library of size N. The file request sequence may be adversarial. At the beginning of each round i, an online caching policy prefetches at most lo files on the cache, denoted by the vector y() such that
N Σ Ew(()K os (1)( S 1 [N].
(5)
The set of all feasible caching configurations is denoted by A Immediately after the prefetching at round t, each user i reveals its file request, represented by the one-hot encoded demand vector x; (f), 1 S m. special case of the above caching model for single user (m 1) has been investigated in previous work [Bhattacharjee et al., 2020, Mhaisen et al., 2022, Joshi and Sinha, 2022].
Let (t) denote the cumulative (fractional) hits obtained by the 1th user up round 2 1. We have
R2(T) = 1+ Σ (a,)))))))) isism. m.
(6)
The online shared caching problem can be easily reduced to instance of the NOFRA problem by taking the demand matrix to be ax()) (ai (4), (1)...... ..... .. I' (1)) Since the allocation vector v(() common all users, the allocation matrix can be taken to y(t) (y(t), v(t).................. vt)) It can be observed that Assumption holds in this case with = k/ N by noting that 1/N1N N E A
3 Designing approximatel--mo-rerdd policy for NOFRA
In view of the difficulty outlined in Section 1, the design and analysis of the Online Fair Allocation (OFA) policy consists of two parts. First, in Lemma I, show that by greedily estimating the terminal gradient with the current gradients at each round, the (1 aa- (o)a-))((a__)))))) -1--) -1-a)--aproxxmate regret of the NOFRA problem can be upper bounded by the standard regret of surrogate online linear optimization problem with policy-dependent gradient sequence. Note that the regret of the surrogate problem depends on the norms of the gradients, which, in turn, depends on the policy. We use the online gradient ascent policy with adaptive step sizes to solve the surrogate problem while simultaneously controlling the norm of the gradients. The following section details our technique.
3.1 Reducing the NOFRA problem to Online Linear Optimization Problem with pelicy-dependent subgradients
Since the a-fairnsss function Φ R.o Ryo is concave and continuously differentiable, have that for any x, > 0:
(xx) ((v) s d' (x) -y) y)-
Let A be a constant, which will be fixed later. Taking x = (T) and y (T,(T) in the above inequality, have
(((((T)
(0)
((T -(3R))))()).C)))
(((B((T)(((((I))) -BR))B r Σ (1)( By,(t)),
(8)
where in (a), we have used the positive homogeneity property of the fairness function d(3x) (l-))(()) in (b), we have used the concavity of the fairness function s(.) from Eqn. (7), and, finally, in (c), we have used the definition of cumulative rewards (2), the fact that 2 1, and the homogeneity of the function Φ(-), which gives o' (Bx) x'x)),
'In the above, we allow fractional caching, which can be easily converted to a randomized integral caching policy (where (t( (0, 1), Vi,t) via sampling. See Section C.6 for details.
5

---

Summing up the bound (8) over all agents i é [m]] we obtain the following upper bound to the of any online policy for the NOFRA problem:
(egret,-(31m))) 5 Σ (()) -Ba(tt))
(9)
It is critical to note that each of the quantities d' (T)) depends the entire sequence of past actions {yr YEa- Hence, d' (T) in (9) is not known to the online policy when it takes its actions. More importantly, the value of the coefficient d' (T)) depends on the future actions and requests through (1). Hence, it is impossible know the value of this coefficient in online fashion. To get around this fundamental difficulty, we now consider a surrogate replacing the term &' (RR, by its causal counterpart o' (R,(L- at the beginning of round I. In other words, we now design an online learning policy that minimizes the regret of the following online linear optimization problem:
problem by
v((()))
RegRetrety in
(10)
To recapitulate the information structure, recall that at the beginning of round t, the cumulative reward vector R(t 1), and hence the coefficient 6' (R,(t- 1)). is known. Still, the current request vector ae(t) is unknown to the online learner before makes its allocation decision y/ on the tt round. We now establish the following key lemma that relates the original regret bound (9) to the regret bound (10) for the surrogate problem.
Lemma I. Consider any arbitrary online resource allocation policy and assume that the utility function of each user is given by the a-fair utility function (3). Then, for any horizon of length T 2 1, have
Regret, (ca) S (1-a)* L-Regret, + m.
(11)
where ca = (1- (1-a)-((-a) e < 1.445.
Proof outline: As discussed above, the surrogate problem greedily replaces the non-causal terminal gradient o' (T)) in Eqn. (9) by the current gradient o' (t 1)), Vi on round t. To prove Lemma 1, we show that this transformation can be done by incurring only a small penalty factor to the overall regret bound. To show this, we split the regret expression (9) into the difference between two terms- term (A) corresponding to the cumulative reward accrued by the static allocation (y"), and term (B) corresponding the reward accrued by the online policy. Next, compare these two terms separately with the corresponding terms (A') and (B') in the regret expression for the surrogate online linear optimization problem (10). By exploiting the non-decreasing nature of the cumulative rewards, we first show that (A) S (A') (Eq. (15)). Next, by using properties of the o-fair utility function, we show that (B') s (1-a) a) - + m) for any policy (Eq. (16)). Lemma I then follows by combining these two results. See Appendix C.2 for the proof.
3.2 Online Learning Policy for the Surrogate Problem and its Regret Analysis
Having established that the Ca regreg of the original problem is upper- bounded by the regret of the surrogate learning problem, we now proceed to upper bound the regret of the surrogate problem under the action of no-regret learner with second-order regret bound. In the sequel, projected Online Gradient Ascent (OGA) with adaptive step sizes [Orabona, 2020, Algorithm 2.2] for designing no-regret policy for the surrogate problem. We call the resulting online learning policy ONLINE FAIR ALLOCATION (OFA). The pseudocode of the OFA policy is given in Algorithm 1.
the
The Online Fair Allocation policy (OFA): Since d' (1))(( = 1/R2 1)",, at the end of round 1, each user i computes its gradient component 9i by dividing its current demand vector r1(()) with its current cumulative reward R, (t 1) raised to the power a (line 5 of Algorithm 1). This formalizes the intuition that a user with a larger current cumulative reward has a smaller gradient component. In line 8, we take a projected gradient ascent step. Depending on the problem, the projection can often be efficiently computed, e.g., using variants of the Frank- algorithm given access to an efficient LP
"See Appendix C.I for upper bounds the Euclidean diameter of the action sets for Examples 2.1-2.3.

---

Algorithm The Online Fair Allocation (OFA) Policy
1, Demand/Reward vectors from the agents ( Euclidean projection oracle (-)(-) onto the feasible set A, an upper-bound D to the Euclidean diameter of the feasible set².
Input: Fairness parameter
2: Output: Online resource allocation decisions 3
3: Rú < 1, Ví e [m])5 S
> Initialization
4: for each round 2: T: do
5:
9: 2,(t-1) Vi [m]
D Computing the gradient components for each agents
R
6:
+ (g), 99.m..9mmm
Computing the full gradient D Accumulating the norm of the grudients Updating the inclusion probabilities using OGA
7:
S < St
|
8:
y 11 11 9
9:
[Optional] Sample a randomized integral allocation Y s.t. E[ = y.
10: The agents reveal their demand/ reward vectors {z.(t) ie[m]] for the current round.
11: R² R4 (x.(()) Vi [m].
Updating cumulative rewards
12:
end for each
oracle. With additional structure, OFA can be simplified further with an even more efficient projection. For example, we give a simplified implementation for the online shared caching problem in Appendix C.5 by exploiting the fact that the action vector y(t) is the same for all users. Step 9 is an optional sampling step which executed only if an integral allocation required. We discuss this step in Appendix C.6. Finally, the cumulative rewards of all users are updated in Step 11. The following lemma gives an upper bound the regret of the OFA policy for the surrogate problem.
Lemma The Online Fair Allocation policy, described in Algorithm I achieves the following standard regret bound for the surrogate problem (10) for the o-fair function:
(2T if 0 O<a<< a<<<1 O( O(VlogT), if a== 1/2 0(1), if 1/2<a<11
L-Regret
Further, under this policy, the cumulative rewards of each user increase linearly with time, i.e., (T(T) = ((T), Vi,T.
One of the major challenges in the regret analysis of the surrogate problem (10) is that the coefficients the gradients (t-
Proof outline:
[m]] on round depends on the past actions {y(T))=_ of the policy itself. Since the second-order regret bound of any online linear optimization problem scales with the norm of the gradients, we now need to simultaneously control the regret and the norm of the gradients generated by the online policy. Surprisingly, the proof of Lemma 2 shows that the proposed OGA policy with adaptive step sizes not only provides a sublinear regret but also keeps the gradients small, which in turn helps keep the regret small. In fact, these two goals well-aligned to each other, and our proof exploits the reinforcing nature of these two objectives via a new bootstrapping technique. See Appendix C.4 for the proof.
Finally, combining Lemma I and Lemma 2, we obtain the main result of this paper.
Theorem The Online Fair Allocation OFA) policy, described in Algorithm achieves the following approximate regret bound for the NOFRA problem (4) with C, =(1 -1-a)-(1--)
((T 0< 1/2, O O(VlgT if 1/2 0(1) if </2<a<11
Regret, (c.))=1-00) a1 a1))))
(12)
For the job scheduling problem the reward maximization setting, Even-Da et al. [2009, Lemma 4] showed that if the cumulative reward is concave and the offline optimal reward convex, then their proposed approachability-base scales exponentially with the number of machines m, achieves sublinear regret. In Section 7 of the same paper, the authors posed an open problem of attaining a relaxed goal when the above sufficient condition is violated. In Appendix C.8, we show that for the a-fair utility function (3),
Remarks: 1.
recursive policy, whose complexity
7

---

the offline optimal cumulative reward is non-conver in the regime 0 < a < 1. Hence, Theorem 1 gives a resolution the above open problem by exhibiting simple online policy with a sublinear approximate regret when the given sufficient condition is violated. Furthermore, the computational complexity of our policy is linear in the number of machines m, which significantly lower than that of their approachability-basee -based policy, whose complexity scales exponentially fast in m.
Observe that the regret bound given by Theorem always remains non-vacuous, irrespective of the value of a and the sequence of adversarial reward vectors. This follows from the fact that irrespective of the demand vectors, by choosing the constant action y jul Nxm (which feasibly by Assumption 2), each user can achieve a cumulative reward of μōT.. Hence, the optimal offline value of the a-fair utility function is (2( On the other hand, by Theorem 1, the OFA policy achieves a regret bound of O(TV=a)) which is always dominated by the optimal static offline objective.
3. When a = 0, NOFRA corresponds to the cumulative reward maximization problem for all users. Hence, Theorem recovers the well-known O(VT) standard regret bound [Orabona, 2020].
The following converse result gives universal lower bound to the approximation factor for which it is possible to design an online policy for NOFRA with a sublinear c-regret.
Theorem 2 (Lower bound on approximation factor). Consider the online shared caching problem for the a--aiir reward function with m 2 users. Any online policy with sublinear rrgrrer must have
1 + (1-1) 1-a
Ca
05 (1 - 222 1-ax + (n/2) 1-a >1, 0<acl.
See Appendix C.9 for the proof of Theorem 2. A numerical comparison between the upper and lower bounds on the approximation factor is shown in Figure 7 in the Appendix. Observe that for a (0. 1) the above lower bound is strictly greater than 1, improving on the prior best known lower bound of (Si Salem et al., 2022], which showed just that sublinear standard regret (i.e., Ca 1) is unachievable.
Experimental results
In this section, we report experimental results using the fair caching problem as a case study". Addi- tional experiments on fair scheduling are provided in Appendix D.2. We compare the performance of our algorithms on two datasets against several baselines showing the effectiveness of our algorithm.
Setup and Dataset: We perform simulations on both synthetically generated data and on CDN traces from Berger [2018]. For our synthetic dataset, the request patterns of the users are highly homogeneous, letting us demonstrate the fairness behavior of different algorithms. In particular, we take time horizon T' 1000 rounds, number of users m cache size C' ===7 7, and library size N =30. At each time step: (1) users I and 2 request file from file numbers 0-29 uniformly at random; (2) user repeatedly requests file numbers 0-3; (3) user 4 repeatedly requests file numbers 18; (4) user 5 repeatedly requests file numbers 19-27. Intuitively, the difficulty comes in ensuring fair allocation of hits to users I and 2, who request files from larger space of possibilities than the other users.
The CDN dataset Berger [2018] contains a request ID for each request, corresponding to the timestamp and the file ID of the requested file. We set T 400 rounds, number of users m 4, cache size C'= 10 and, library size N = 50. For preprocessing, first, we sort the data according to the timestamp and discard all the files with an ID greater than N, and then only consider the first m T 1600 requests among the remaining requests. We then allocate files to users in decreasing order of their popularity, such that user tends to request common files, while user tends to request less common files. This makes ensuring a fair cache allocation difficult. See Appendix D.1 for details.
Comparison: We compare our algorithm with the Online Horizon- Fair (OHF) policy proposed by Si Salem et al. [2022]. Just like the OFA policy, OHF is also an online policy that ensures long-term fairness using the a-fairness utility, which makes it an ideal candidate for comparison. We also compare our algorithm with the commonly used Least- Reees-Recently-Sse Used (LFU) cache replacement policies. We compare our algorithm with the fixed offline optimal allocation and the maximin optimal allocation. Both policies have access to all the file requests ahead
(LRU) and Frequ-Fre
'The code is available at: https :/tg::/ggttttttt/ httpb//cco//.i..oss//oe....
8

---

Offiine Optimal
Maximin
1.0
Avergee Hirrates
0.3
0.6
Minimum
0.2
0.2
0.4
6.1
0.1
0.2
0.0
0.0
0.0
(a) Average Hitrate
(b) Minimum Hitrate
(c) Jain's Index
Figure 2: Synthetic Dataset
Optimal
0.4
1.0
Bawrage Haratee
0.6
0.9
0.3
0.5
Minimum
6.3
0.1
0.6
0.5
0.0
(a) Average Hitrate
(b) Minimum Hitrate
(c) Jain's Index
Figure 3: CDN Dataset
of time. The fixed optimal offline allocation is given by y² argmax yey Σ & (T)( where Y is the set feasible cache configurations (see Eqn. (5)) and (T( is defined in Eqn. (6). The maximin optimal allocation is the fixed offline caching configuration that maximizes the minimum hitrate among all users. can be computed via an LP. We compare these algorithms in terms of the average hit rate, minimum hit rate, and Jain's 's fairness index as the value of changes. Jain's faimess index is a common metric used to quantify if the users are receiving a fair share of network resources. In our case, the fairess index is given by
EE (T))) m M. RT(T)
(R) RS (T)
The index ranges from 1/m for minimum fairness to for maximum fairness.
The average hitrates of each policy are shown Figures 2a and 3a. For the synthetic dataset, despite being fair, the overall performance of the OFA policy is at par with the traditional caching algorithms like LRU and LFU policies. For the CDN dataset, the OFA policy initially performs close to the Si Salem et al. [2022] algorithm while for 2 1.5, the OFA thoroughly outperforms For a > 1, there is drop performance of OFA compared to the "unfair" LRU and LFU algorithms." 7 The minimum hitrates of each policy are shown in Figures 2b and 3b. For both datasets, the OFA policy outperforms Si Salem al. [2022], LRU, and LFU. We can also see minimum and average hitrates for the OFA policy come closer each other the algorithm becomes fairer the cost of total hitrate. Finally, from the plots in Figures 2c and 3c, can see that increases, OFA outperforms all other algorithms in terms of Jain's 's faimesss index. Also, Jain's index for OFA approaches the maximum value as we increase a.
Observations:
increase a. Lee.
Although regret guarantees for become vacuous, to clearly demonstrate the faimess characteristics of algorithms, simulations for [0,2].

---

Conclusion and open problems
In this paper, we propose an efficient online resource allocation policy, Online Fair Allocation (OFA), that achieves a -ppppooxiee sublinear regret bound for the o-fairness objective, where Ca (1 (1-a))(0aa)) < 1.445, for 0 a < 1. Our main technical contribution is to show that the non- additive a-fairness function can be efficiently learned by greedily estimating the terminal gradients. An important follow-up problem is to investigate the extent to which the algorithmic and analytical methodologies introduced in this paper can be generalized. Note that, for the online scheduling problem, only a recursive approachability-assee scales exponentially with the number of machines [Even-Dar et al., 2009]. The algorithm and analysis presented in this paper are specific to the a-fair utility function. It would be interesting to investigate whether these ideas can be extended to learning general concave utility functions. Another related problem is to design optimistic version of the proposed OFA policy that offers an improved regret bound by efficiently incorporating hints regarding the future demand sequence [Mhaisen et al., 2022, Bhaskara et al., 2020]. Finally, reducing the gap between the upper and lower bounds of the approximation factor Figure would of interest.
policy is known in the literature, whose complexity
10

---

Acknowledgement
This work is supported by US-India NSF-DST collaborative grant coordinated by IDEAS- Technology Innovation Hub (TIH) at the Indian Statistical Institute, Kolkata, and as a supplementary fund of NSF CAREER 2045641. A. Sinha was additionally supported by the Qualcomm Research Grant IND-417880. M. Hajiesmaili's 's work is supported by CNS- CNS-2100263,, CNS-2 CNS-2106299, and CPS-2136199. C. Musco was also partially supported by an Adobe Research grant.
References
Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Richard Zemel. Fairness through awareness. Proceedings of the 3rd Conference on Innovations Theoretical Computer Science (ITCS), ITCS 12, page 216-226, New York, NY, USA, 2012. Association for Computing Machinery. ISBN 9781450311151.
Karen Hao. Facebook's 's ad-serving algorithm discriminates by gender and race. MIT Technology Review, 2019.
Tian Lan, David Kao, Mung Chiang, and Ashutosh Sabharwal. An axiomatic theory of fairness in network resource allocation. IEEE, 2010.
Frank Kelly. Charging and rate control for elastic traffic. European Transactions on Telecommunica- lions,
1997.
Jeonghoon Mo and Jean Walrand. Fair end-to-end window-based congestion control. IEEE/ACM
Transactions on Nerworking, 8(5):556-56)) 2000.
Bozidar Radunovic and Yves Le Boudec. unified framework for max-min and min-max fairness with applications. /EEE/ACM Transactions on Networking, 15(5):1073-1083, 2007.
Dritan Nace and Michal Pióro. Max-min faimess and its applications to routing and hall-balancing in communication networks: tutorial. IEEE Communications Surveys & TTttorials 10(4):5-17, 2008.
Rajendra K Jain, Dah-Ming W Chiu, William R Hawe, et al. A quantitative measure of fairness and discrimination. Eastern Research Laboratory, Digital Equipment Corporation, Hudson, MA, 21, 1984.
Eitan Altman, Konstantin Avrachenkov, and Andrey Garnaev. Fair resource allocation in wireless networks in the presence of a jammer. Performance Evaluation, 67(4):338 -1888-39,,,0 2010. ISSN 0166- 5316. Performance Evaluation Methodologies and Tools: Selected Papers from VALUETOOLS 2008.
Elad Hazan. Introduction to online convex optimization. arXiv preprint arXiv:1909.05220 2019.
Tareq Si Salem, Georgios Iosifidis, and Giovanni Neglia. Enabling long-term fairness in dynamic resource allocation. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 6(3):1-36, 2022.
Eyal Even-Dar, Robert Kleinberg, Shie Mannor, and Yishay Mansour. Online learning for global cost functions. In Proceedings of the 22nd Annual Conference on Computational Learning Theory (COLT), 2009.
Alexander Rakhlin, Karthik Sridharan, and Ambuj Tewari. Online learning: Beyond regret. In Proceedings of the 24th Annual Conference on Learning Theory, pages 559-594. JMLR Workshop and Conference Proceedings, 2011.
Shipra Agrawal, Nikhil Devanur, and Lihong Li. efficient algorithm for contextual bandits with knapsacks, and extension to concave objectives. In Conference Learning Theory, pages 4-18, PMLR, 2016.
Yuezhou Liu, Yuanyuan Li, Qian Ma, Stratis loannidis, and Edmund Yeh. Fair caching networks. Performance Evaluation, 143: 2020. ISSN 0166-5316.

---

Debjit Paria and Abhishek Sinha. Leadcache: Regret-optimal caching in networks. Advances in Neural Information Processing Systems 34 (NIPS), 34:4435-4447, 2021.
Rajarshi Bhattacharjee, Subhankar Banerjee, and Abhishek Sinha. Fundamental limits on the regret of online network-caching. Proceedings the ACM on Meusurement and Analysis of Compuling Systems, 4(2), June 2020. doi: 10.1 10.1145/3392143.
Samrat Mukhopadhyay, Sourav Sahoo, and Abhishek Sinha. k-experts-onling policies and funda- mental limits. In International Conference on Artificial Intelligence and Statistics, pages 342-365.
PMLR, 2022.
Dimitris Bertsimas, Vivek F Farias, and Nikolaos Trichakis. On the efficiencc-fairmes trade-off. Management Science, 58(12):2234-2255 2012.
Naram Mhaisen, Abhishek Sinha, Georgios Paschos, and George Iosifidis. Optimistic no-regret algorithms for discrete caching. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 6(3), dec 2022. doi: 10.1145/3570608
Ativ Joshi and Abhishek Sinha. Universal caching. In 2022 IEEE Information Theory Workshop (ITW), pages 684-689, 2022. doi: 10.1109/TW54588 000.:/5555888222229966965
Francesco Orabona. A modern introduction to online learning, 2020. URL https::/pppe bu. edu/ handlle21444409000
Daniel Berger. CDN Traces. https://github. httphhhw..oooooaas.ooogggaaaaaee 2018.
Aditya Bhaskara, Ashok Cutkosky, Ravi Kumar, and Manish Purohit. Online learning with imperfect hints. In Proceedings of the 37th International Conference Machine Learning (ICML), pages 822-831. PMLR, 2020.
Moritz Hardt, Eric Price, and Nati Srebro. Equality of opportunity in supervised learning. Advances in Neural Information Processing Systems 29 (NIPS), 29, 2016.
Jon Kleinberg, Sendhil Mullainathan, and Manish Raghavan. Inherent trade-offs in the fair deter- mination risk scores. Christos H. Papadimitriou, editor, Proceedings of the 8th Conference on Innovations in Theoretical Computer Science (ITCS), volume 67 of Leibniz International Pro- ceedings in Informatics (LIPlcs), pages 43:1 43:223, Dagstuhl, Germany, 2017. Schloss Dagstuhl- Leibniz-Zentrum fuer Informatik. ISBN 978-3-95977-029-3 doi: 10.4230/LPPts..TCS.20001
Dimitris Bertsimas, Vivek F. Farias, and Nikolaos Trichakis. The price of faimesss. Operations Research, 59(1):17311, 2011.
Sam Corbett- and Sharad Goel. The measure and mismeasure of faimess: A critical review of fair machine learning. arXiv preprint 1808.000233 2016.
Alexandra Chouldechova. Fair prediction with disparate impact: A study of bias in recidivism prediction instruments. Big Data., 5(2):153-163, 2017.
Sean R. Sinclair, Siddhartha Banerjee, and Christina Lee Yu. Sequential fair allocation: Achieving the optimal envy-efficiency tradcoff curve. SIGMETRICS Perform. Eval. Rev., 50(1))95-96, jul 2022. ISSN 0163-5999. doi: 10. 10.1 00.1145//547333335255555
Siddhartha Banerjee, Vasilis Gkatzelis, Artur Gorokh, and Billy Jin. Online nash social welfare maximization with predictions. In Proceedings of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1-19, 2022. doi: 10.1137/197811611177033.
Makis Arsenis and Robert Kleinberg. Individual faimess in prophet inequalitics. In Proceedings of the 23rd ACM Conference on Economics and Computation, EC '22, page 245, New York, NY, USA, 2022. Association for Computing Machinery. ISBN 978 1781455 450391504.
Mohammad Sadegh Talebi and Alexandre Proutiere. Learning proportionally fair allocations with low regret. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 2(2): 1-31, 2018
12

---

Vishakha Patil, Ganesh Ghalme, Vineet Nair, and Y. Narahari. Achieving faimesss in the stochastic multi-armed bandit problem. J. Mach. Learn. Res., 22(1), ), jan 2021. ISSN 1532-4435.
Matthew Joseph, Michael Kearns, Jamie H Morgenstern, and Aaron Roth. Fairnsss in learning: Classic and contextual bandits. Advances in Neural Information Processing Systems 29 (NIPS), 29, 2016.
Fengjiao Li, Jia Liu, and Bo Ji. Combinatorial sleeping bandits with fairness constraints. IEEE Transactions Network Science and Engineering, 7(3):1799-1813, 2019.
Yifang Chen, Alex Cuellar, Haipeng Luo, Jignesh Modi, Heramb Nemlekar, and Stefanos Nikolaidis. Fair contextual mumti-armed bandits: theory and experiments. In Conference on Uncertainty in Artificial Intelligence, pages 181-190. PMLR, 2020.
Daniel Freund, Thodoris Lykouris, Elisabeth Paulson, Bradley Sturt, and Wentao Weng. Group fairness in dynamic refugee assignment. arXiv preprint arXiv:2301.10642y 2023.
Jackie Baek and Vivek Farias. Fair exploration via axiomatic bargaining. Advances in Neural Information Processing Systems 34 (NIPS), 14:22034-22045, 2021.
Avrim Blum and Carl Burch. On-line learning and the metrical task system problem. In Proceedings of the 10th Annual Conference on Computational Learning Theory (COLT), pages 45 45-53, 1997.
Avrim Blum, Carl Burch, and Adam Kalai. cimpeiicomeetitive paging. In Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 450 45500-47,,5 1999. doi: 10.1109/SFFCS. 1999.8 8 $14617.
Zhiyuan Wang, Jiancheng Ye, Dong Lin, and John C. S. Lui. Achieving efficiency via fairness in online resource allocation. In Proceedings of the 23rd International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing, MobiHoc '22, page 101-110, New York, NY, USA, 2022. Association for Computing Machinery. doi: 00.1145/34928663549777
ISBN
Alexander L Stolyar. On the asymptotic optimality of the gradient scheduling algorithm for multiuser throughput allocation. Operations research, 53(1):12-25, 2005a.
Harold J Kushner and Philip A Whiting. Asymptotic properties of proportional sharing algorithms. Technical report, Brown Univ Providence RI Div of Applied Mathematics, 2002.
Frank P Kelly, Aman Maulloo, and David Kim Hong Tan. Rate control for communication networks: shadow prices, proportional fairness and stability. Journal of the Operational Research Society, 4933)223--252, 1998.
Dimitri Bertsekas and Robert G. Gallager. Data Networks. Englewood Cliffs, NJ: Prentice Hall, 1991.
Jeffrey Jaffe. Bottleneck flow control. JEEE Transactions on Communications, 29(7):954 1981. doi: 19110//T.....9...00 109508....
MohammadHossein Bateni, Yiwei Chen, Dragos Florin Ciocan, and Vahab S. Mirrokni. Fair resource allocation in a volatile marketplace. Operations Research, 70(1):288-30) 2021.
Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. Regularized online allocation problems: Fairness and beyond. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning (ICML), volume 139, pages 630-639. PMLR, 18-24 Jul 2021,
Yuan Deng, Negin Golrezaei, Patrick Jaillet, Jason Cheuk Nam Liang, and Vahab Mirrokni. Fairness in the autobidding world with machine-learned advice. arXiv preprint urXiv:2209.04748:5 2023. doi: https://doi.org/ 10.
Will Ma, Pan Xu, and Yifan Xu. Fairness maximization among offline agents in online-matching markets. ACM Trans. Econ. Comput., 10(4), apr 2023. ISSN 2167-8375. doi: 145/5567556
Dimitris Bertsimas, Vivek F. Farias, and Nikolaos Trichakis. Flexibility organ allocation for kidney transplantation. Operations Research, 61(1), 2013. ISSN 73-87.
13

---

Günter M Ziegler. Lectures on polytopes, volume 152. Springer Science & Business Media, 2012.
Kun Tu, Bruno Ribeiro, David Jensen, Don Towsley, Benyuan Liu, Hua Jiang, and Xiaodong Wang. Online dating recommendations: matching markets and learning preferences. Proceedings of the 23rd international conference world wide web, pages 787-792, 2014.
Nicolo Assa-Bianchi and Gábor Lugosi. Prediction, learning, and games. Cambridge University Press, 2006.
Víctor Valls, George losifidis, and Leandros Tassiulas. Birkhoff's decomposition revisited: Sparse scheduling for high-speed eircuit switches. IEEE/ACM Transactions on Networking, 29(6):2399- 2412, 2021.
Alexander L Stolyar. On the asymptotic optimality of the gradient scheduling algorithm for multiuser throughput allocation. Operations Research, 53(1):11-25, 2005b.
14

---

Appendix
No-regret Algorithms for Fair Resource Allocation
A. Sinha, A. Joshi, R. Bhattacharjee, C. Musco, M. Hajiesmaili
A Related Work
We provide a more comprehensive review of the fair machine learning literature in this section. Multiple different definitions have been used quantify the faimesss of machine learning algorithms. Hardt et al. [2016] introduced equality of opportunity as a fairness criterion, which ensures that individuals have an equal chance of being correctly classified by machine learning algorithms, regardless of their protected attributes like race or gender. Kleinberg et al. [2017] formalized three different notions of fairness and showed that algorithm can satisfy these notions simultaneously, thus showing the inherent trade-offs in competing notions of faimess. Other prevalent fairness criteria include ffice-of-fairnes introduced by Bertsimas et al. [2011] which quantifies how much the aggregate utility is affected by enforcing fairesss Sarbett-Davies and Goel [2016] discussed the limitations of different notions of fairness widely used in the fair machine learning literature. There have been different works that examined the societal harm caused by unfair algorithms in critical domains. For example, Chouldechova [2017] investigated the disparate impact of recidivism prediction algorithms used in the criminal justice system on different demographic groups. Since our work on online fair resource allocation is closely related fairness in online algorithms, job scheduling, and matching, we provide a more detailed review of papers related to fair algorithms in each of these domains below.
Fairness in online algorithms: Several works have considered fairness specifically in the online set- ting using both regret and competitive ratio as performance metries. Sinclair al. [2022] considered the problem of allocating resources to individuals in an online setting, where the number and type of individuals arriving in each round are drawn from some fixed known distribution. The allocations must balance envy-freeness (requiring that each agent prefers the agent's 's own allocation over the other's allocation) and efficiency (the amount of consumed resources' budget). Banerjee et al. [2022] design competitive algorithms for the problem of allocating set of divisible goods to agents in an online manner while maximizing the Nash social welfare, which another metric that quantifies the trade-off between fairness and efficiency. They also study the setting when the algorithm is allowed to access some predictions related to the utility function of each agent over the goods. Arsenis and Kleinberg [2022] introduce notions of individual faireess in optimal stopping problems and provide competitive algorithms that satisfy these definitions of fairness.
There have been different works that consider fairness in terms of regret. Talebi and Proutiere [2018] studied a setting where tasks arriving dynamically need to be assigned to a set of servers where the probability of success of any job on any server is unknown. Using stochastic multi-armed bandit setting, the authors showed that it possible to achieve a proportionally fair allocation of jobs to servers in this setting. Multiple other works have studied the fairness problem in the stochastic multi-armed bandit setting [Patil et al., 2021, Joseph et al., 2016, Li et al., 2019, Chen et al., 2020]. There have also been some works recently that study algorithms with group fairness guarantees where we are concerned about being fair to a group of individuals (for example, a group might correspond to race) instead of single individual. [Freund et al., 2023] studies group faireess for algorithms used to assign refugees to different geographic locations. Back and Farias [202 l] studies the problem of sharing the cost of exploration in the stochastic multi-armed bandit model fairly among different groups
Several prior works exist that design no-regret policies for specific non-additive functions. Blum and Burch [1997]. Blum et al. [1999] used online learning techniques for solving the online paging and the Metrical Task System problem, which contains states. The notion of o-fairness in the online setting has been considered in a couple of works including Si Salem et al. [2022] as explained previously in the introduction. Wang et al. [2022] considered online resource allocation problem where the
15

---

objective is to guarantee a sublinear regret for the allocation efficiency and a sublinear minimum guarantee violation penalty. The authors proposed an online policy that achieves this goal by using a weighted a-fair allocation on each round while sequentially tuning the weights and the exponents of the a-fairness function. Although they use round-wise a-fair allocation as tool, their objective not to optimize the a-fairness of the cumulative allocation, which is the focus of our paper.
Fairness in job scheduling: Apart from the papers cited above, the fair resource allocation problem in the context of job scheduling has also been extensively investigated by the wireless communication community, predominantly under stochastic assumptions [Stolyar, 2005a, Kushner and Whiting, 2002]. Furthermore, contrary to the online learning setting. these works typically assume that the current reward vectors (e.g., the channel states) are available the scheduler before it makes scheduling decisions for each round. In this setting, the classic proportional fair scheduling algorithm emerges as a stochastic approximation-type gradient ascent algorithm for maximizing the logarithmic utility function [Stolyar, 2005a, Kelly et al., 1998]. Other notions of fair utility functions that have been studied the context of wireless communication include max-min utility [Bertsekas and Gallager, 1991, Jaffe, 1981] and a-fair utility [Mo and Walrand, 2000] (also called isoelastic utility function).
Fairness in matching: Fair matching algorithms have been studied in the context of resource allocation in online marketplaces Bateni et al. [2021]. In this setting. a platform must dynamically allocate goods arriving at a platform in an online manner to customers who have their own utility and budget for each of these goods. The allocation of goods to customers must fair to the customers while also maximizing the revenue for the platform. Different problems like online advertising where impressions must be served an online manner to advertisers on a platform can be modeled under this setting. A proportionally fair stochastic approximation scheme was proposed in this paper. An algorithm with sublinear regret in a similar setting was proposed in Balseiro et al. [2021] where the fairness criteria were modeled as regularizer for the objective function. Deng et al. [2023] studied how to incorporate machine-learned advice to improve fairness for bidders in the context of algorithmic bidding in online advertising. Competitive algorithms for optimizng both group and individual fairness in online matching markets which includes recommendation engines, crowdsoureing platforms etc. was proposed in Ma et al. [2023]. Fair matching algorithms for other domains like organ allocation Bertsimas et al. [2013] have also been proposed.
B
Additional Examples
Beyond online fair caching, the NOFRA problem capture fair version of several other problems in the literature. In the following, we concretely present online fair job scheduling and online fair matching problems.
Example B.1 (Online Job Scheduling [Even- et al., 2009].. In this problem, there
machines that play the role of agents. A single job arrives at each round. The reward accrued by assigning the incoming job at round č to the 3thh machine is given by (t) where 2t) E [8, 1]. Vi [m]. where 0 is small positive constant. Before the rewards for round t are revealed, an online allocation policy selects probability distribution y, on m machines such that
Σ Ev( -1, vi(t) 2 O, Vie [m].
The policy allocates a fraction (t) of the job to the hh machine Vi e [m]] As a result, the ghh machine accrues a reward of x; (1) (1) on round f. Hence, the cumulative reward accrued by the 7th machine in a time-horizon of length T is given by:
RT - (t))()(t), Vie [ie[m].
The objective of the online fair job scheduling problem is to design an online allocation policy that achieves sublinear regret with respect to the a-faimess of the cumulative rewards defined in (4). From the above description, is immediately clear that this problem a special case of the general NOFRA problem. The online job scheduling problem occurs in many practical settings, e,g. in the targeted ad-campaigning problem discussed the introduction, the ads can be modelled as jobs, and different groups of users can be modelled as machines. In OFDMA wireless systems, the
16

---

fair allocation of frequency resource blocks to different users where the wireless channels change dynamically can be straightforwardly modelled as an instance of the online job scheduling problem.
Agents
Resources
A Bipartite graph
A Matching in
Figure 4: Illustrating the Online Fair Matching (OFM) problem for zero-one demands. The existence of an edge denotes unit demand, and likewise, the absence of any edge implies zero demand.
m bipartite graph where the vertices the left denote the agents and the vertices on the right denote the resources. On every round, each agent can be matched with one resource only, where we allow fractional matchings. The 1 demand vector of the agent i on round / is denoted by x; (1). The j component of the demand vector x; (1) denotes the potential reward accrued by the jth agent had been completely matched with the j"h resource on round t. Let the binary action variable Vij (f) [O, 1] denote the amount by which the agent i is matched with resource j on round t. Hence, the reward accrued by the agent on time is given by (t) (t)).. Let A denote the convex hull of all matchings. It is well known that A can be succinctly represented by the set of all m m doubly stochastic matrices, a.k.a. the Birkhoff polytope [Ziegler, 2012]). In other words, in the OFM problem, the of all feasible actions A consists of all m matrices (Hy) satisfying the following constraints 8:
Example B.2 (Online Matching). Consider
m Σne j-1
Σ yky 1, Vj.
11 Vi, 0s viy $1 Vi,j.
(13)
Let the variable R&(1) denote the cumulative rewards accrued by the ,th agent up round f. Clearly,
(1(1) (a - 1) (xx(1), (()),, R2(0) = 1, Vie [m].
(14)
It can be verified that Assumption 2 holds in this problem with μı = m by noting that m- 1mxm A. The objective of the Online Fair Matching (DFM) problem is to design an online matching policy that minimizes the ceRegret (4). From the above formulation, it can be immediately seen that the Online Matching problem is an instance of the NOFRA problem. Furthermore, it also generalizes the online scheduling problem described in Example B.
The online matching problem arises in numerous practical settings. For example, in the problem of online Ad Allocation, there are m different advertisers whose ads need to be placed in m different display slots on webpage. Each slot can accommodate only one ad. On round f, new user arrives and presents a reward vector (t) for each advertiser. For example, the component æ.y (t) could denote potential revenue accrued by the advertiser if the ad is placed on the jth slot on round f. The objective of the allocation policy is to match the ads to the slots on each round so that the total earned revenue fairly distributed among the advertisers. Similar problems arise in designing recommendation systems for crowd-sourcing, online dating websites [Tu et al., 2014], and fair channel assignment in wireless networks [Altman et al., 2010].
As before the fractional matching can be converted to randomized integral matching via sampling. See Section C.6 for details
17

---

C Proofs
C.1 Upper bound on the diameter of the admissible sets
Lemma 3. For the online shared caching problem the diameter of the admissible action set can be bounded as follows:
Diam( A S vkk
Proof. Let y A We have
N
N Σ
||0 - 11o- = Σ i-1
s y:)²
Σ b kik - vol
Σ
x
yil
S
Vi
2k:
where, in (a), we have used the fact that 0 24, S 1, in (b), have used triangle inequality, and in (c), we have used the fact that the sum of the components of each feasible vector is k.
Lemma 4. For the online matching problem, the diameter of the admissible action set can be bounded as follows:
Diam( (A) S v2m.
Let v, E A, where A is the feasible set for the OFM problem. We have
| - v112 (E - yyr)
Σ aay Voyl s Σ Exs yiy 2m,
4
4
where the inequalities follow from similar arguments as in the proof of the previous lemma.
C.2 Proof of Lemma
Proof. The expression for Regret, (31-a) from Eqn. (9) can be split into the difference of two terms and as follows:
Regret, (Bt-a) =8-0
[2 2 (R(((T))) Σ (c,()) (T((R( Σ (0.00
(n)
Also, denote the corresponding terms in the regret expression (10) for the surrogate learning problem by A' and B'. We will separately bound each of the above terms in terms of the corresponding terms the regret expression (10) for the surrogate learning problem.
Proving s A': Recall that the utility function xt.)) is concave. Hence, its derivative non- increasing. Furthermore, under the action of any policy, the cumulative reward R2(-) is non-decreasing for each user [m]. Thus, we have ø' (Ra(t- 1)) 2 ø' (R)) for all t E [T]] i [m]] Hence,
T Σ Φ A
[ - 1)) A
(15)
18

---

Proving B' (1-a m): We have
B' = ΣΣ (B((t-
= (((((L- R(((-1))
(0)
Σl R((T)
5
d'(R)R
= [d(R((T)
(1-a)- (I- (EO(((TTR((
@ (1- [ ( (0)0)))))))))+++))))))))))))))))
< (B+a)
(16)
where, in (a), we have used the fact that the derivative e'(+) is non-increasing and R,(t) (t-
(z.(t), (t) s 1 (see Appendix C.3 below for proof by picture), in (b), we have used the explicit form of the a-fair utility function to substitute zΦ (a) (1 (z), and in (c), we have used (2).
Combining (15) and (16) and choosing 3 (1 a) we conclude that, letting L-Regrety be the surrogate regret defined as (10),
((1-et)(11a)-121))) a1 L-Regrety (1- (1-a)-(1-)) (1-0))
C.3 Graphical proof of the inequality:
R,((1)1 ((R((t-1))(R(()) (2(( (.((-1)-1 d'R)dR.
(17)
Proof. We use the fact that d'(.) is non-increasing function and 0 < R2(t) - Rt(t - 1) s 1. Then the inequality (17) follows straightforwardly from the schematic below.
0 R((1) R2(1 1)
R.(0-1 &(R)dR ((R)aR
('HH)
Translate the rectangle to the left by one unit
(H.(1 - -
1))
length s 1
Figure 5: Graphical proof of (17)
The final inequality (a) then follows by summing up the above inequalities.
C.4 Proof of Lemma 2
Proof. We will using the following adaptive regret bound for the online gradient descent policy with an appropriate adaptive step sizes sequence. We will see that the norm of the gradients diminishes
19

---

at steady rate under the action of the OFA policy. Hence, the data data-dependent regret bound plays central role in tight regret analysis of the OFA policy.
Theorem 3 (Theorem 4.14 of Orabona [2020]). Let A c R be a convex set with a diameter D. Let us consider a sequence of linear reward functtions with gradients (9e) Run the Online Gradient Ascent policy with step sizes U
D 1 t T. Then the standard regret
V2E;. 11
under the OGA policy can be upper-bounded as follows:
Regrety $ D
2 Σ 1g.1
(18)
1=1
Note that the gradient component g, corresponding to the 1th user for the surrogate problem (10) on round is given by the vector gt(t) o' (f)((t)) Using the above data-dependent static regret bound (18), the regret achieved by the OGA policy for the surrogate problem for any round 2
be hopereb as follows:
(
T ΣΣ C
L-Regret, =
ΣΣ I=1 F=
(19)
E Rt)
where we have used the fact that the demand vectors at each round are bounded.
Clearly, the regret bound (19) depends on the sequence of the cumulative rewards (R(t) ta which is implicitly controlled by the past actions of the online policy itself. By the definition of regret, for any fixed allocation y" A we have for any time step T:
T (R.(t
T ΣΣ(d(R ()) -LL-Reettt Legegrtt
(20)
where L.-Regrety denotes the worst-case cumulative regret of the adaptive OGD policy up time T. Since the cumulative reward of each user is monotonically non-decreasing, we have:
R₂ (T 2 1, Vi, VT.
(21)
Substituting this bound to the regret bound in (19), we obtain our first (loose) upper-bound for the regret of the fair allocation problem (10):
--Regrety=-( OVVT).
(22)
Note that this bound might be too loose as the offline benchmark itself could be smaller in magnitude than this regret bound. closer inspection reveals the root cause for this looseness the cumulative reward lower bound (21) too loose for our purpose, as cumulative rewards grow steadily with time, depending on the online policy. We now strengthen the above upper-bound using novel bootstrapping method, that simultaneously tightens the lower bound for the cumulative rewards (21) and, consequently, improves the regret upper bound (19).
Using the fact that (z,(t), y4 (t) = (t) R&(t - 1), and following the same calculations up to the fourth step of (16), have
ΣΣ d' (e((t-1))((;(())) (z) & [((R(TT)
(23)
Furthermore, lower bounding &'(R( 1)) by (B(((TT))(
we have
(R(((((( EI
(24)
where (T) = (z)() (1), vf) is the cumulative reward accrued by a fixed allocation y" e A up to time T. Using Assumptions and 2 and choosing of = ,ll,,, we have R2 (T) 2 JōT, Vi. Hence, combining (23), (24), and (20), we have
(T) JOT Σ &' (R((T) - L-Regrety.
(25)
20

---

Improve the uppeer bound to L-Regret
Ingrove the lower bound to Rt(1), Vi
Figure 6: Illustrating the new Bootstrapping technique used in the proof of Lemma 2
Since 0 < RT) T, Vi, and o(.) is monotone non-decreasing, for any user [m]] the above
inequality yields:
m
115
L- L-Regret,
(1 T
R (T)
T
i.e.
(T) 2 uō
L-Regret, T
m
a = = Vi [m],
(26)
1 a
where we have used our previous upper bound (22) the regret. Eqn. (26) is key equation for carrying out the bootstrapping process as it lower bounds the minimum cumulative reward of users in terms of the worst-case regret. Now consider two cases:
Case-I: 0 a $ 7/2
In this case, we immediately have R2(T) = ((T), Vi,T. Substituting this bound on (19), we have
(0(VlogT) if a= 1/2 O(T1/22-) if
L-Regret,
Case-ll: 1/2 a<1
In this case, using the bound (26), we have R2(T) /20), Vi,T. Using the regret bound (19), the regret be bounded
L-Regrety 0(
Σ
0( OVVloTT)
Substituting this bound again in (26), we have (T) 2 Q(T). This, in turn, yields the following regret bound:
L-Regret, = 0()
Σ
0(1)
21

---

0. C.5 Simplified Pseudocode for the Online Fair Allocation Policy for the Caching Problem
Algorithm 2 Online Fair Allocation Caching (OPFC)
Input: Fairness parameter 0 a 1. Online file request sequence (a:(t) from user i, [m]] Euclidean projection oracle 2T (+) onto the feasible convex set 4
2: Output: Sequence of file inclusion probabilities {vel and samples from this distribution
3: R, 1, Vi [m].5= S
D Initialization
4: for each round f - 2 T:
5:
g Σ (1-11)
Computing the gradient
R
6:
D Accumulating the norm of the gradients Updating the inclusion probabilities using OGA The users reveal their file requests for round & (x;(t), i [m]].
S S Igll
7:
y = A (y+ (59
8:
9:
R. R2 (1) v), Vie [m]]
> Updating cumulative hits
10: Sample a subset of k files by invoking Algorithm 3
11: end for each
C.6 High-probability regret bound for randomized integral allocations
Theorem 2 establishes c, = (1 a)) (11=) -regret guarantee for the Online Fair Allocation (OFA) policy for fractional allocations where the set of admissible actions A is the convex hull of integral allocations. In the following, we show that a sub-linear Ca -eeret guarantee holds with high probability when randomized integral actions are chosen according to the optional step (9) in the OFA policy. Recall that for integral allocation, on each round & we independently sample an integral allocation
Y e {0, 1)mA, that matches with the fractional allocation 1/1 expectation, i.e., [E[; ] = Y/ where is the fractional allocation vector recommended by the OFA policy. A fractional allocation vector Ye in the convex hull of integral allocations can be turned into a randomized integral allocation by expressing
convex combination of integral allocations and randomly sampling one of the integral allocations with appropriate probabilities. As Appendix C.7 shows, for many problems with structure, such a decomposition can be efficiently computed.
By appealing to [Cesa-Bianchi and Lugosi, 2006, Lemma 4.1], it is enough to consider an oblivious ad adversary that fixes the sequence demand vectors (æ(+) tx1 before the game commences. Let the random variable (T) denote the random cumulative reward obtained by the 7h user under the randomized integral allocation policy and the deterministic variable R: R;(T) is defined as in Eqn. (2). By construction, we have E (T) (T)... Furthermore, since (T) is the sum of I' independent random variables, each of magnitude at most one, from the standard Hoeffding's inequality, we have
Regret Analysis:
P(R: RR (()
<xp())2>x22p2)2p)pp Vi [m].
Hence, with probability least 1 polppoll)))) the aggregate a-fair utility (3) accrued by the randomized policy can be lower bounded as:
(1-a)-12 Σ R2(T) (((T)-O(())) (OVT)oo( 1-a
(1 -R- R
2 (1-a)-1 (T) ((((To)))()))
(27)
where in inequality (a), we have used the fact that (x y) < - Y0 a 1, 0. Combining the above with the approximate regret bound Theorem 1, and taking the dominant term, we conclude that the ca -regett for the randomized integral allocation policy is upper-bounded by O((Tlgg (og 7) 1 w.h.p. for all 0 $ 1. Unfortunately, unlike Theorem 1, the integral allocation policy incurs non-trivial (but sublinear) c, regret for the entire range of the fairness parameter 0 < 1.
22

---

C.7 Efficiently sampling an integral allocation from a mixed allocation in the convex hull
Online shared caching: For the online shared caching problem, the admissible set A given by Eq. (5). Clearly, incidence vectors of all k-sets, containing k I's and N k zeros, belong to A. Furthermore, given any vector y E A, a randomized integral allocation can be sampled in linear time using Madow's sampling scheme, described in Algorithm 3, which yiclds the vector y in expectation.
Algorithm 3 MADOW-SAMPLA (p)
1: Input: A universe [N] of size N, the cardinality of the sampled set k, and a marginal inclusion probability vector p E 4
2: Output: A random k-set S with |S| ls such that, P(i S) pi, vie V [N]
3: Define Il = 0, and II, = II:-1 + Pi, v is N.
4: Sample a uniformly distributed random variable U from the interval [0. 1].
5: S - Ø
6: for each 0 to k 1 do
7: Select the element j if 111-1 SU I1,
8: end for each
9: return S
2. Online job scheduling: In the online job scheduling problem, the admissible action set A is given by the N-simplex. Given any point on the N N-simplex, it is trivial to randomly sample a coordinate using single uniform random variable.
3. Online matching: In the online matching problem, the admissible action set A is given by the Birkhoff polytope (13). Given any point y in the Birkhoff polytope. it can be efficiently decomposed convex combination of small number of matchings using the Birkhofff Von-Neumann (BvN) decomposition algorithm [Valls et al., 2021]. Using the decomposition coefficients, a matching can be randomly sampled that exactly matches the point y in expectation.
C.8 Convexiiy of the optimal offline benchmark for the online job scheduling problem
Consider the job scheduling problem in the reward maximization setting described in Example B. Clearly, the a-fairness metric accumulated by the online policy is concave in the regime 0 s a s 1. However, the following proposition shows that the offline static benchmark for this problem is non-convex for the f-fair utility function in the regime 0 < a < 1.
Proposition 1. The offline optimal a-fair reward function for the job scheduling problem is non-conve.for for 0 < 1.
Proof. Let the probability distribution y² be an optimal static offline allocation vector for the reward sequence {xt) Also, let (1) Σ, (t) be the cumulative reward observed by the 2t machine, 1 siis S m. Then the optimal allocation y maximizes the following objective:
(1-a)-1 "((R
(28)
s.t. the constraints Σ, yt 1, y.y 2 0. Since 0 < < 1, the objective function is strongly concave and the optimal solution y² unique. Using the standard Hölder's incquality with the conjugate norms 1/1-o, q 1/a, we can upper bound the objective (28) as
(1 - a)- Σ
(1-a)-1 (2))) v:) 1- C =))
1=1
(1- Rr RT)
(29)
23

---

where we have used the constraint Σ, Us = in the last equality. The upper-bound is achieved by the following distribution
R
v Le
vie
[m].
(30)
Σ, R
Hence, the optimal offline reward (28) is given by
R (1- (1)
(31)
To show that R' is non-convex in the cumulative reward vector R in the regime 0 < 1, consider the case of two users. Letting x (r(1). y Ry (2) and ignoring the positive pre-factor, the function under consideration is given follows:
f(x,y) - (x + (y
(32)
Recall that function is convex if and only if the determinants of all leading principal minors of its Hessian matrix are non-negative. A straightforward computation yields the following expression for the determinant of the Hessian of the function f(r,y)
det(v² (2a - (a 2/- 1/-1 10010111//// (x1/a-1
10-11113 1)20
(yrl/o xy 2/)
The determinant becomes strictly negative in the regime 0 < < is non-convex for < On the other hand, have
1/2 This shows that the function (32)
0 fxx v) = (a- 1) (apla-2(x Or²
10 (aayy'// (a 200y - xy 1y)
alya zy)
In particular, at the point 11 the above second partial derivative evaluates to be
8² fxxx v)
20-2 (a² 2a-1),
Or
(a,))-(1,1)
which is strictly negative for /2- < a 1. Taking the above two results together, we conclude that the offline optimal reward function (32) is non-convex for 0 < 1.
C.9 Proof of Theorem 2 (lower bounding the approximation factor)
Consider the following instance of the online shared caching problem with m users and cache of unit capacity. Assume that the library's 's size (N) is sufficiently large. Let the total length of the request sequence T rounds and v) E [0, 1] be some constant fraction be fixed later. Consider two different file request sequences:
Instance 1: For the first 172' rounds, user always requests file I and user 2 always requests file 2. For the next (1 (1-n)) r) rounds, user always requests file 2 and user 2 requests file chosen uniformly at random from the library.
Instance For the first r/T rounds, as in Instance 1, user 1 always requests file and user always requests file 2. However, for the next (1 - 7) rounds, user 1 requests random file chosen uniformly at random from the library and user 2 always requests file 1.
now lower bound the approximation factor achievable by any online policy for the above two request sequences.
Optimal static offline policy: It easy see that the optimal offline strategy is to cache file 2 for all I' rounds. Hence, the total a-fairness objective accrued by the static offline policy is
Offline a-fairness (1 (1-ap -T-a)--T-- 1-a + (1 -)) 1-0].
Clearly, the same fairness objective achieved for the second instance by a static policy that always caches file 1.
24

---

1.45
Upper bound Lower bound
Bounds appro pimaton factor
1.35
(1-a)
(2 a)
1.25
1.15
1.05
0.2
0.4
0.6
0.8
Figure Comparison between the upper and lower bounds of the approximation ratio
Online Policy: Suppose that during the first 7/ rounds, the online policy caches file for y fraction of the time and file 2 for 1 1 fraction of the time. Since the policy is online, the fraction ry remains the same for both instances. Clearly, for the next (1 - T) time slots, optimal online policy caches file 2 for instance and file for instance 2. Taking the worst of the two instances, any online policy achieves the following fairness objective:
Online a-fairness (1-a)-1a11 min (g(7).
where g(7) (mm+ (1- +(1-7)m) 1-a From simple calculus, it follows that the function g(7) is non- non-increasing for 0 7 1/2,0 s a < 1. This implies that the online a- a-fairmess is maximized when 7 3. Hence, the a-fairness metric achieved by any online policy for the worst of the above two instances upper bounded by:
Online a-fairness s (1 n//2) 1-a + (n/2)²
Hence, the achievable approximation ratio ca for any online policy with sublinear ca regret is lower bounded as follows:
Offline a-fairness
1 (1-1) 1
Approx. ratio 2 Online a-fairness
1/22 1-a (n/2)1-a*
Taking the maximum of the RHS with respect to the parameter 1) yields the desired result.
D Additional Numerical Experiments
In this section, we provide more detailed description of how the CDN dataset was preprocessed and additional numerical experiments on fair scheduling.
D.1 Preprocessing the CDN dataset
We give additional details regarding preprocessing the CDN dataset for the experiments here. As explained in section 4 we set 7' 400 rounds, number of users m 4, cache size C' = 10 and, library size N 50. For preprocessing, first, sort the data according the timestamp and discard all the files with an ID greater than N, and then only consider the first m x T = 1600 requests among N descending order of the number of
the remaining requests. We then relabel the files from requests such that among these 1600 requests, file 1 is the most requested file, followed by the second file, and so on. We then assign the requests sequentially to users in decreasing order of priority from users 1-4, i.e., we first try to assign request to user 1, failing which we try to assign it to user 2, and then to users 3 and We can only assign a request to user if the total number of requests assigned to that user is less than equal to T = 400 and the following conditions met for users 1-3: (1)
25

---

user I: file ID between 1-6; (2) user 2: file ID between 1-9; (3) user 3: file ID between 1-12. User can be assigned any file. Thus, allocate files to users in decreasing order of their popularity, such that user 1 tends to request common files, while user 4 tends to request less common files. This skews the file request distribution, making fair cache allocation for all users difficult.
D.2 Fair Scheduling
The datasets are generated by simulating a wireless channel. For the first dataset (WLAN), the simulator generates channel gains and shadowing values for each user, computes the received power and noise for each user, adds Rayleigh fading to the signal-to-noise ratios (SNRs), and then normalizes the SNRs by the maximum value to generate rewards. We take the horizon T 5000 and number of users m 5. The second dataset (MCS) is generated using Modulation and Coding depending on the radio link quality. Here,
Dataset:
Scheme table which defines the data rates for each the number of users is m 2 and the horizon is at 7 2000. Although regret guarantees for 1 become vacuous, to clearly demonstrate the fairness characteristies of algorithms, we run simulations for a [0, 2].
1.0
GA Fair Scheduling
1.0
OFF Fair Scheduing
Fair Schhouligg
0.8
Brward Rates
Reward Rates
0.8
0.7
0.6
0.5
0.4
0.2
0.2
0.3
0.0
0.0
02
0.2
0.4
0.6
(a) Reward Rates: GA
(b) Reward Rates: OFA
(c) Jain's 's Index
Figure 8: Scheduling (WLAN)
1.0
GA Fair Scheduling
OFF Fair Scheduling
Far Scheduling
Brogard Retees
Reward Rates
0.75
0.70
0.66
0.2
0.2
0.58
6.0
0.0
0.50
0.4
(a) Reward Rates: GA
(b) Reward Rates: OFA
(c) Jain's Index
Figure 9: Scheduling (WLAN)
Comparison: We compare our policy with the Gradient Algorithm (GA) described by Stolyar [2005b]. The Gradient Algorithm is widely used in fairly scheduling transmission multiple users via time-varying wireless channel. Stolyar considers model where finite set of queues are served by a switch. The switch has a finite number of switch states M. The sequence of states at each time steps form irreducible Markov chain. At each state m, scheduling decision & e K (m) is made, where K (m) is a finite set of decisions. Each scheduling decision has a corresponding vector of service rates given by 11" (k-). Let V be the set of all long-term average service rate vectors. The goal to have a scheduling policy that gives an average service rate solving the maximization problem
max H (1),
(33)
WeV
26

---

The Gradient Algorithm converges an where H() is strictly concave smooth utility function. The Gradient Algorithm makes a scheduling decision
((t) aargmax(=H(x(()))
where X(f is updated as
X(+ + - (1-
for some initial value of (0) and a fixed parameter optimal u² that maximizes (33) as 3 0.
Figures 8a, 8b, 9a and 9b compares the average, minimum and maximum reward rates of both the policies as increases. The Jain's Index of both the policies shown in Figures 8c and 9c. be clearly observed that for [0, 1). the OFA policy performs better terms of fairness, but for larger a's, the GA outperforms the OFA policy by a small margin. Recall that Stolyar only provides theoretical guarantees for stochastic setting whereas we give stronger regret bound in an adversarial setting at the expense of slight performance degradation in practice.
27


Reviews:
[{"review_id": "ByMhOR5HAF", "reviewer": "Reviewer_jNhn", "summary": "The paper consider a fair resources allocation problem in the setting of unrestricted adversary, which is called a generic online fair resource allocation (NOFRA).  An OFA policy is proposed with reasonable theoretical guarantees.", "questions": "See weakness part. I feel like the main content of this paper is to formulate the problem via using a different regret objective. It is very loosely related to usual fairness bandit. The writing should be improved.  ", "limitations": "No.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper present an online fair allocation algorithm, which approximately maximizes the aggregate $\\alpha$-fairness function. The lower bound of approximation factor is established.", "weaknesses": "I have several concerns in the problem formulation.\n\n1. Why the initial condition $R_i(0) = 1$ instead of being 0? Maybe it is due to technical requirements? \n\n2. To me, the motivation of using concave $\\alpha$-fair utility function is not strong.\n\n3. $c$-regret is adopted in the paper. To me, I do not quite understand why it is a good metric to evaluate policy. It seems it is merely for technical purposes?\n\n4. Can author also highlight its technical novelty? Is Lemma 1 the most challenging?\n\n5. The topic is about fair resource allocation. But the paper seems  to be loosely connected with fairness bandit. The definition of fairness here is also not clearly specified. The related literature should be included.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments. In the following, we address each of the comments in the same order.\n\n1. [$\\textbf{Justification for counting cumulative rewards from 1}$]: The initial value of $R_i(0)$ is set to $1$ instead of zero to make sure that the derivative of the $\\alpha$-fair utility function $\\phi(\\cdot)$ remains finite at any round - a condition which is required by any online learning policy. Note that $\\phi'(R_i)= 1/R_i^\\alpha.$ Hence, the derivative of the utility function becomes infinite when $R_i=0.$ Thus, if we set the initial value of $R_i$ to one, and since R_i is a monotone nondecreasing function of time, this technical issue can be avoided. Another equivalent way to avoid this problem is to change the utility function to $\\phi(x)= \\frac{(1+x)^{(1-\\alpha)}}{1-\\alpha}$ and set $R_i(0)=0.$ However, we opted for the former option to avoid a more cumbersome expression for the utility function.\n\n2. [$\\textbf{Motivation for alpha-fair utility function}$]: We want to emphasize the $\\alpha$-fair utility function is a standard utility function that enjoys several interesting technical properties and is heavily used in network resource allocation (see for example [1-2]). We also refer the reviewer to [3], which gives an axiomatic characterization of a fair utility function and shows that the alpha-fair utility function comes out naturally from the axioms. Other utility functions, e.g., proportional fair and min-max utilities, can be shown to be a limiting form of alpha-fair utility. \n\n3. [$\\textbf{The c-regret metric}$]: Regret is a standard metric to evaluate the performance of any online policy. However, as we show in Theorem 2, no online policy can achieve a sublinear regret for the problem that we study in this paper. The metric c-Regret generalizes the usual regret metric where the online policy achieves a sublinear regret against $(1/c)$-fraction of the utility achieved by a static adversary. The smaller the value of c, the stronger becomes the performance guarantee of the online policy. The notion of c-regret has also been extensively used in the online learning literature (see, e.g., the papers [4-6]). This is why we chose c-regret as a performance metric in this paper. \n\n4. [$\\textbf{Technical Novelty}$]: Both Lemma 1 and Lemma 2 are non-trivial results. Lemma 2 introduces a new successive refinement argument to obtain a tight regret bound. \n\n5. [$\\textbf{Related work on fair bandits}$]: In our current related work, there is a paragraph that covers related work in the context of multi-arm bandits (Lines 510-521). We will expand this with additional recent results. \n\n[1] Mo, Jeonghoon, and Jean Walrand. \"Fair end-to-end window-based congestion control.\" IEEE/ACM Transactions on Networking 8.5 (2000): 556-567.\n\n[2] Li, Tian, Sanjabi, Maziar, Beirami, Ahmad, and Smith, Virginia. \"Fair Resource Allocation in Federated Learning.\" International Conference on Learning Representations (ICLR). 2019.\n\n[3] T. Lan, D. Kao, M. Chiang and A. Sabharwal, \"An Axiomatic Theory of Fairness in Network Resource Allocation,\" 2010 Proceedings IEEE INFOCOM, San Diego, CA, USA, 2010, pp. 1-9, doi: 10.1109/INFCOM.2010.5461911.\n\n[4] Azar, Yossi, Amos Fiat, and Federico Fusco. \"An $\\alpha $-regret analysis of Adversarial Bilateral Trade.\" Advances in Neural Information Processing Systems 35 (2022): 1685-1697.\n\n[5] Paria, Debjit, and Abhishek Sinha. \"$\\texttt {LeadCache} $: Regret-Optimal Caching in Networks.\" Advances in Neural Information Processing Systems 34 (2021): 4435-4447.\n\n[6] Emamjomeh-Zadeh, Ehsan, Chen-Yu Wei, Haipeng Luo, and David Kempe. \"Adversarial online learning with changing action sets: Efficient algorithms with approximate regret bounds.\" In Algorithmic Learning Theory, pp. 599-618. PMLR, 2021.\n\n"}, {"review_id": "22GUjWaORo", "reviewer": "Reviewer_DRz6", "summary": "This work studies an abstract fair resource allocation problem. It abstracts out problems such as cache and job scheduling. The notion of fairness considered is alpha-fairness (in the range of alpha between 0 and 1), which has been previously studied and is known to encapsulate many other fairness notions.\n\nThe paper provides sublinear approximate regret bounds for the abstract fair resource allocation problem through a clever reduction to online linear optimization, and analyzes it using prior work on online gradient descent in conjunction with a bootstrapping technique. The approximation constant is small (around 1.45) and they further show that the notion of approximate regret is necessary for this problem (i.e. that sublinear regret bounds require an approximation constant larger than 1). They also back up their theoretical results with experiments that compare to previous work and other standard benchmarks showing that their algorithms achieve good efficiency-fairness tradeoffs in comparison.\n", "questions": "1- In the proof of lemma 2, I’m not sure I understand what happens to the summation over i in equation 19. For example, when the regret is lower bounded by 1 for every user at every timestep (eqn 21), wouldn’t substituting in equation 19 give you O(sqrt(mT)) regret? Not sure if I’m missing something. Similar questions strike me in Case 1 and 2 in pages 18 and 19. I also don’t fully understand these cases and how they follow from equation 26, so would really appreciate more explanation.\n\n2- Some more discussion on alpha-fairness and exposition on why it’s a good notion of fairness for these problems would be good.\n", "limitations": "Limitations adequately addressed.\n\n", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1- The approach of replacing the problem of interest with a surrogate problem that can be solved via more standard regret minimization techniques and relating the regrets of the two problems is a nice and novel contribution, as is the bootstrapping technique used to prove regret bounds for the surrogate problem.\n\n2- It is nice that such results can be obtained without significantly restricting the adversary.\n", "weaknesses": "1- Assumption 2 seems reasonable for many problems, but Assumption 1 (that asks that demand vectors always be bounded away from 0) seems more restricting. Additionally, regret bounds seem to depend on the constants in these assumptions.\n\n2- The paper discusses alpha-fairness for alpha between 0 and 1, but for alpha-fairness to encompass more fairness notions, larger alpha is relevant as well, and is unaddressed by their results", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer very much for their review and their questions, which we address below.\n\n[$\\textbf{Assumption 1}$] We agree with the reviewer and believe that it might be possible to establish similar regret bounds without Assumption 1. Please keep in mind that, for many problems, e.g., the caching problem, where at least one file is requested per round, Assumption 1 is naturally satisfied with $\\delta=1$. \nOne possible way to remove Assumption 1 is to divide the entire horizon into two phases – a regular phase where Assumption 1 is satisfied and a special phase where the demand vectors are small and Assumption 1 is not satisfied. The regret analysis for the regular phase proceeds in the same way as given in the paper. Next, one could argue that since the demand vectors are small for the special phase, it contributes only a tiny amount to the overall regret. We reserve this extended analysis for future work. \n\n[$\\textbf{Larger alpha}$]: Note that in our formulation, $R_i(T)$ is defined as the total cumulative reward of agent $i$, which grows linearly with time T. As we mentioned in Remark 1 (page 4, line 146), a sublinear regret bound becomes vacuous for any $\\alpha >1$. Hence, we did not consider larger values of $\\alpha$ in this paper. We agree though that establishing theoretical guarantees in the $\\alpha > 1$ under some reasonable performance metric would be an interesting direction for future work.\n\n[$\\textbf{Response to Q1}$]: For the simplicity of exposition, the $O(\\cdot)$ notation hides dependencies on all parameters (including the number of users $m$) except the time horizon $T$. Also, please note that the variable $R_i(T)$ denotes the cumulative rewards accrued by $i$ th agent up to time T (not regret).\n\n[$\\textbf{Intuitive explanation for bounding the L-Regret}$]: In a nutshell, the bootstrapping technique used in the proof of Lemma 2 is an algebraic exercise of simultaneously bounding the order of growth of the dependent sequences $\\{R_i(t)\\}$ and ${L-Regret}_{T}$ under the action of the proposed online policy. We initially start with a crude bound for both sequences and then successively refine these bounds by exploiting their interrelations. \n\nTo be precise, we use Eq (19) for bounding the L-regret_T for any arbitrary round $T\\geq 1$. From Eq (19), it follows that ${L-Regret}_{T}$ depends on the value of the cumulative reward sequence $\\{R_i(t)\\}$ – the larger the values of these variables, the tighter becomes the regret bound. Hence, the proof proceeds by establishing tight lower bounds for the cumulative reward sequence $\\{R_i(t)\\}$. This is established via Eq (26) which gives a lower bound to the cumulative reward accrued up to any round T.\n\nLet us now consider Case -I $(0\\leq \\alpha \\leq 1/2)$. Since $L-Regret_T = O(\\sqrt(T))$ from Eqn (22), Eqn (26) implies that $R_i(t)$ increases linearly with $t$, substituting this bound in Eq (19), we conclude that $L-Regret_T= O(\\sqrt(\\sum_t (\\frac{1}{t^{2\\alpha}})))$. We finally arrive at the stated regret bound upon summing this series. A similar explanation holds for Case II as well.\n\n[$\\textbf{Response to Q2 - Motivation for alpha-fair utility function}$]: We thank the reviewer for the suggestion. In our response to Reviewer 1 above, we have provided a brief discussion on the Motivation for using the alpha-fair utility function. We will include this discussion in the revised version.\n\n\n\n\n"}, {"review_id": "TM6K3y5L7U", "reviewer": "Reviewer_q9U9", "summary": "The paper studies a general online resource allocation in which there are $m$ agents and a limited resource to be allocated over T rounds.  The goal is to achieve sublinear regret for the aggregate utilities of the agents when compared to the optimal fixed offline allocation policy. In the online problem, at each round an agent has a demand vector; first, the decision-maker decides on an allocation according to some policy, and then the aggregate demand vector is revealed. An unrestricted adversary fixes the demand vector (this assumption departs from previous works). The utility for any agent is given by a concave utility function controlled by a parameter $\\alpha$, which varies between 0 and 1 and expresses the trade-off between fairness and efficiency, going from a very equitable allocation to the classic problem of maximizing social welfare without looking at fairness.\n\nThe NOFRA problem is defined, along with mild assumptions on the demand and allocation vectors. A main challenge comes from the fact that the objective function, which is the sum of the agents’ utilities, is not additive and, thus, not separable across time. Instead, we have to optimize in a “global” way. The objective, as mentioned before, is to design an online resource allocation policy that minimizes regret.\n\nThe contributions of the paper include (1) an efficient online resource allocation policy called OFA (Online Fair Allocation) that achieves approximate sublinear regret for any given $\\alpha$ in the utility functions, (2) a (non-tight) lower bound (that also improves over previous work) on the approximate factor needed to attain sublinear regret for any online learning policy, and, (3) numerical simulation results with several baselines for the fair caching problem.", "questions": "- Why examine $\\alpha>1$? What does a utility function now mean?\n- Why at Jain’s index is your policy better than opt offline? Should that be interpreted in some way?\n- How do you think that your techniques could be generalized to other, more general concave utility functions? Can you give some extra reasoning of why you chose this particular form of utility function?\n\nMinor comments:\n-  In p.19 (p.7 of the appendix), erase the comment left there.\n- Maybe you want to define somewhere the hitrate notion used in the experiments?\n\n", "limitations": "The authors adequately addressed the limitations.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The treatment of the problem is fairly complete, and, despite not obtaining a tight bound, it is important that the authors establish that indeed some notion of approximate regret minimization is needed to achieve any sublinear bound over time.\n- Technical side: A key step is lemma 1, which introduces a surrogate problem, whose regret upper bounds the regret of the original one, and it can be solved as an online linear optimization problem. This is an elegant way to overcome the fact that the objective is not additive over rounds. The introduction of the technique to control the norm of gradients is also nice. \n- The comparison with previous work is clear, the improvements and technical innovations are also clear, so overall the authors do a good job in convincingly placing their work in the literature. I also find quite interesting the transitions in the regret bound for different values of $\\alpha$. It is also positive that it recovers the known regret bound when $\\alpha=0$.\n", "weaknesses": "- Some of the experiments are not very convincing to make the theory stand out more. For example, assuming that the average hitrate is what we would consider more important, there’s not any improvement (in the real-world dataset it’s actually performing worse) compared to the Si Salem et al. baseline. Something similar happens also with the fair scheduling dataset in the appendix. \n- It would make the results much stronger if there would be some indication that the techniques hold beyond the specific choice of $\\alpha$-fair utility function. How are these techniques going to be generalized? It’s good that the authors give some examples, but is the proposed utility function capturing, at least qualitatively, how agents evaluate their reward?\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and questions, which we respond to below.\n\n[$\\textbf{On the significance of the experimental results}$]: Although there is no major improvement in the average hit rate, the goal of our algorithm is to provide fairness (i.e., to ensure that the hit rates of all users are as close to each other as possible) without significantly sacrificing the average hit rate. To empirically show this fairness, we plot the minimum hit rate and Jain's Index (which is a standard notation of fairness that is maximized when all users have the same hit rate). It can be seen from the experiments that our algorithm has a higher Jain's Index and minimum hit rate than the baseline algorithms without sacrificing significantly in terms of average hit rate.\n\n[$\\textbf{The alpha >1 regime}$] To intuitively understand the implication of the utility function for $\\alpha > 1$, recall that the alpha-fairness function $\\phi$ is proportional to $\\sum_i \\frac{1}{R_i(T)^{\\alpha-1}}$. As $\\alpha$ grows very large (i.e., much larger than $1$), this sum is dominated by $\\frac{1}{\\min_i R_i(T)^{\\alpha-1}}$. Hence, maximizing this utility function for large $\\alpha$ becomes nearly equivalent to maximizing the minimum cumulative reward. This is a natural fairness objective. Generally, increasing $\\alpha$ from $0$ to $\\infty$ yields a continuum of objective functions that increasingly weight fairness as compared to total utility.\n\n[$\\textbf{Jain's Index}$] As described in line 315, Jain's Index is a metric that quantifies if the users are receiving a fair share of resources. In the context of fair caching, Jain's Index quantifies if the users are receiving similar hit rates, but it does not take into account whether the average hit rate is maximized. The Jain's Index of a policy can be high even when the average hit rate is low as long as the hit rates of individual users are close to each other. For example, in Figure 3, even though Jain's Index of our policy is higher than the optimal offline, the average hit rate is lower. Jain's Index does not capture the overall performance of a policy. The main reason we plot Jain's Index is to demonstrate that our policy (as well as the offline optimal) become \"fairer\" as the $\\alpha$ parameter is increased. Comparing Jain's Index of different policies might not necessarily lead to any concrete conclusion. \n\n[$\\textbf{Extension to General Concave Utility functions}$] The greedy policy can be extended straightforwardly for a general concave utility function $\\phi$ by replacing the quantity $\\frac{1}{R_i^\\alpha}$ by $\\phi' (R_i)$ in line 5 of Algorithm 1. However, with regards to the regret analysis, note that in Eq (10), we explicitly use the positive homogeneity property of the $\\alpha$-fair utility function. Hence, we do not see an immediate way to extend the analysis for a general concave utility function. Nevertheless, in the special case, when the utility function $\\phi$ is a sum of $\\alpha$-fair utilities for different constant $\\alpha$'s, the analysis goes through. It would be interesting to give even more general regret bounds for concave utilities.\n\n[$\\textbf{Minor Comments}$] Thanks for pointing these out. We will make the necessary changes in the revised version."}, {"review_id": "xAbBv6ZXVh", "reviewer": "Reviewer_wJNK", "summary": "The paper studies an online allocation problem where the goal is to find \\alpha-fair solutions. The authors provide an algorithm that provides a constant approximate regret to this problem, along with a non-tight lower bound that improves a previous known result. The suggested algorithm is compared with other approaches over synthetic and real data on the fair caching and  fair scheduling problems. ", "questions": "Something is inconsistent with respect to the line 5 of Algorithm 1 and the description in lines 230-23. In my understanding, in round t, the agent divides x_i(t-1) with R_i(t-1). In the algorithm it seems that indeed you do that, but in the description, you are saying that essentially x_i(t-1) is divided by R_i(t-2). Which one is the correct?\n\nCodes of the experiments are not included in the supplementary material!", "limitations": "Yes, the authors have adequately addressed the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- Well-written paper\n\n-Important problem with real life applications\n\n-Technically sound and strong submission. Nice techniques are used. ", "weaknesses": "-The upper and lower bounds are not tight. \n\n-The lower bound that is provided is a slight improvement from a previous known lower bound which indicates that c_{\\alpha} >1, as shown in Figure 7 in the appendix.\n\n-The experimental results are not very enlightening. It would be nice if the authors highlight what we really learn from them, provide an intuitive explanation why for smaller values of \\alpha their algorithm is outperformed from other algorithms with respect to the average case etc. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer very much for their feedback, which we address below.\n\n[$\\textbf{On the experimental results}$]: The goal of our algorithm is to provide fairness (i.e., to roughly ensure that hit rates of all users are as close to each other as possible) without significantly sacrificing the average hit rate. As $\\alpha$ is increased, the algorithm should tend towards prioritizing fairness over average hit rate. Our experiments demonstrate that the algorithm indeed succeeds in these goals. For both the synthetic dataset and CDN dataset, we see that our algorithm achieves comparable average hit rate to the algorithm of Si Salem et al. at small $\\alpha$, while somewhat significantly outperforming on average hit rate for larger $\\alpha$. At the same time, the algorithm outperforms on the fairness metrics for the full range of $\\alpha$ on the CDN dataset. On the synthetic dataset, the two algorithms are comparable in terms of fairness — neither one consistently outperforms the other.\n\nOur algorithm consistently performs within the range of the offline optimal allocation — which is a theoretical baseline that cannot be run in practice (as it would require knowing the full sequence of requests ahead of time). This offline optimal solution gives an upper bound on the performance of any online algorithm. Finally, our algorithm is comparable or better in terms of average hit rate, but, as expected, stronger in terms of fairness metrics, as compared to algorithms like LRU and LFU which do not try to ensure fairness.\n\nRegarding performance for small $\\alpha$: we disagree that our algorithm is consistently outperformed in this regime. It performs very similarly to the Si Salem et al. algorithm, and in fact outperforms the LRU and LFU baselines. It is only outperformed by the offline optimal solution, which as discussed is meant to give a theoretical upper bound on performance and cannot be implemented in the online setting.\n\n\n[$\\textbf{Question on Algorithm 1}$]: In line 5, we indeed divide $x_i(t-1)$ by $R_i(t-1)^\\alpha$. Thanks for pointing out this typo — we will correct the description in the revised version.\n\n[$\\textbf{Releasing Codes}$] We will release the code upon acceptance of the paper."}]

Author rebuttal:

Meta-review: this paper looks at a standard problem of resource allocation (job scheduling, caching..) with the catch of adding a type of fairness constraint. This is an interesting contributions to the field that all the reviewers - and myself -, enjoyed. I therefore recommend acceptance
Decision: Accept (poster)