Fairness-Regularized Online Optimization with Switching Costs
Authors: Pengfei Li
Yuelin Han
Adam Wierman
Shaolei Ren
Venue: NeurIPS 2025 poster ()
Keywords: Online optimization
long-term cost
health-informed decision making
Primary area: optimization

Abstract: Fairness and action smoothness are two crucial considerations in many online optimization problems, but they have yet to be addressed simultaneously. In this paper, we study a new and challenging setting of fairness-regularized smoothed online convex optimization with switching costs. First, to highlight the fundamental challenges introduced by the long-term fairness regularizer evaluated based on the entire sequence of actions, we prove that even without switching costs, no online algorithms can possibly achieve a sublinear regret or finite competitive ratio compared to the offline optimal algorithm as the problem episode length $T$ increases. Then, we propose **FairOBD** (Fairness-regularized Online Balanced Descent), which reconciles the tension between minimizing the hitting cost, switching cost, and fairness cost. Concretely, **FairOBD** decomposes the long-term fairness cost into a sequence of online costs by introducing an auxiliary variable and then leverages the auxiliary variable to regularize the online actions for fair outcomes. Based on a new approach to account for switching costs, we prove that **FairOBD** offers a worst-case asymptotic competitive ratio against a novel benchmark---the optimal offline algorithm with parameterized constraints---by considering $T\to\infty$. Finally, we run trace-driven experiments of dynamic computing resource provisioning for socially responsible AI inference to empirically evaluate **FairOBD**, showing that **FairOBD** can effectively reduce the total fairness-regularized cost and better promote fair outcomes compared to existing baseline solutions.

Fairness-Regularized Online Optimization with Switching Costs
Pengfei Li
Yuelin Han Electrical and Computer Engineering University of California, Riverside
School of Information Rochester Institute of Technology pflicstrit.ed edu
Seanc1 edu
Adam Wierman
Shaolei Ren
Computing & Mathematical Sciences
Electrical and Computer Engincering University of California, Riverside shaolei@ucr.eet
California Institute of Technology adam=@cal tech edu
Abstract
Fairness and action smoothness are two crucial considerations in many online optimization problems, but they have yet to be addressed simultaneously. In this paper, we study new and challenging setting of feirness-reullarized smoothed online convex optimization with switching costs. First, to highlight the fundamen- challenges introduced by the long-term fairness regularizer evaluated based on the entire sequence of actions, we prove that even without switching costs, no online algorithms can possibly achieve a sublinear regret or finite competitive ratio compared to the offline optimal algorithm as the problem episode length T increases. Then, we propose FairOBD (Fairness ceirnnss-regularizeed Online Balanced De- scent), which reconciles the tension between minimizing the hitting cost, switching cost, and fairness cost. Concretely, FairOBD decomposes the long-term fairness cost into sequence of online costs by introducing auxiliary variable and then leverages the auxiliary variable to regularize the online actions for fair outcomes. Based
approach to account for switching costs, prove that FairOBD offers a worst-case asymptotic competitive ratio against a novel benchmark- the optimal offline algorithm with parameterized constraints- by considering T Finally, we run trace-driven experiments of dynamic computing resource provision- ing for socially responsible AI inference empirically evaluate FairOBD, showing that FairOBD can effectively reduce the total fairnes--reullaizeed cost and better promote fair outcomes compared existing baseline solutions.
Introduction
Smoothed decision decision-making is critical to reducing abrupt and even potentially dangerous large action changes in many online optimization problems, e.g., energy production scheduling in power grids, object tracking, motion planning, and server capacity provisioning in data centers, among others 47 55 2 Mathematically. action smoothness can be effectively achieved by including into the optimization objective a switching switching cost essentially equips the online optimization objective with a (finite) memory of the previous actions and also creates substantial algorithmic challenges. As such, has received huge amount of attention in the last decade, with a quickly growing list of algorithms developed under and the references therein).
that penalizes temporal changes actions. The added
various settings (see [50
30
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Additionally, (ong-term) faimess is crucial consideration that must be carefully addressed in variety of online optimization problems, especially those that can profoundly impact individuals' well-being and social welfare. For example, sequential allocation of social goods to different individuals/groups must be fair without discrimination [6] [4)), the surging environmental costs of geographically distributed Al data centers must be fairly distributed across different regions as mirrored in recent repeated calls by various organizations and government agencies [22] I0 228 231, and Al model performance and resource provisioning must promote social fairness without adversely impacting certain disadvantaged individualssgroups [43. If not designed with fairness in mind, online algorithms further perpetuate or even exacerbate societal biases, which can disproportionately affect certain groups/individuals and amplify the already widening socioeconomic disparities. Therefore, fairness in online optimization is not just matter of ethical concern but also necessity for ensuring broader social responsibility.
The incorporation of a long-term fairesss regularizer into the objective function can effectively achieve fairness in online optimization by mitigating implicit or explicit biases that could otherwise Despite its effectiveness in promoting fairness, the added fairness regularizer presents significant challenges for online optimization 6 40). This arises from the lack of complete future information, which is required to evaluate the fairness regularizer. Intuitively, online meakeion-makers prioritize immediate cost reduction, reacting to sequentially revealed information, potentially neglecting the long-term consequences of the decision sequence.
be reinforced 16, 40
39
28
Recent research has started to explore fairness in various online problems, such as online resource allocation, using primal-dual techniques 339 G K5
However, a major limitation of current fair online algorithms lies in their reliance on the assumption that per-round objective functions are independent of historical actions. This assumption plays a pivotal role in both algorithm design and theoretical analysis (e.g., 66 77). For instance, in a simple resource allocation scenario, while the maximum allowable action at time i and its corresponding reward may depend past allocation decisions through the remaining budget, the revenue or reward function at time is assumed to depend only on the current allocation decision and remain independent of these historical decisions. However, these methods fall short in addressing online problems where the per-round objective function is directly impacted by historical actions, such as those involving switching costs, as detailed in Section 2
Contributions. In this paper, we study fairness-regularized smoothed online optimization with switching costs, a new and challenging setting that has not been considered in the literature to our knowledge. More specifically, we incorporate a fairness regularizer that captures the long-term impacts of online actions, and aim to minimize the sum of a per-round hitting cost, switching cost, and long-term fairness cost. To simultaneously address the tension between minimizing the hitting cost, switching cost, and faireess cost, we propose FairOBD (Failies-reguularized Online Balanced Descent).
Optimizing the long-term cost with a sequentially revealed context sequence is widely recognized as a challenging problem (e.g.. [3
7 12 38 26)). common strategy to address this challenge involves decomposing the long-tern fairness cost into a sequence of online costs by introducing an 35), which effectively converts the fairness cost into an equivalent long- term constraint. However, the key limitation of existing methods is the requirement of independence between per-round objective functions, which is violated by the switching cost. Specifically, given the updated Lagrangian multiplier, the per-round online objective depends action due to the switching cost. This dependency is not permitted in prior fairness- firress--egullarized online problems 66 [39]. As a result, due to the differing action sequences, both FairOBD and the benchmark algorithm ( (R.& 8) OPT (Definition 4.3) have distinct objective functions at each round, complicating a direct comparison of their costs.
6
auxiliary variable (e-g.
the previous irrevocable
In this work, we rigorously analyze the inherent hardness of incorporating long-term fairness regular- ization into online optimization. We establish fundamental lower bounds in the dynamic benchmark under two standard performance metrics: regret and competitive ratio. Unlike the static benchmark, where the offline optimal action is constrained to single fixed action, the dynamic benchmark allows the offline optimal action sequence to adapt over time with full knowledge of the context. While a finite competitive ratio is attainable in online optimization with switching costs, whether a similar finite competitive ratio can be achieved in presence of long-term fairness regularization remains an open question. Intuitively, this is because long-term regularizer depend on the entire trajectory and can only be evaluated at the end of an episode, whereas switching costs can be assessed step by step.
2

---

Although prior work has made conjectures about the impossibility of achieving finite performance in similar settings [6] our results provide the first rigorous proof. Our results show that in the adversarial setting, all online algorithms inevitably incur a constant regret gap (leading to linear total regret) and an unbounded competitive ratio that grows at least línearly with the horizon length. This demonstrates that the unconstrained dynamic benchmark is unsuitable for analyzing such problems. Motivated by real-world applications and guided by insights from our proofs, we propose the (R, 5) bbbehnhhm, in which the deviation between piece-wise and episode-wise function averages is bounded.
By developing a novel proof technique that explicitly accounts for the dependency of online objectives on previous actions, we show that FairOED offers a worst-case asymptotic competitive ratio against a (R. connttriid optimal offline algorithm (Theorem 5.2 in (.22ion/5.2, where R and ó specify the total allowed variations of the optimal actions. Importantly, our analysis quantifies the impact of the long-term fairness regularizer on the convergence speed of FairOBD's 's total cost, which asymptotically matches the best-known results for two existing setrings smoothed online optimization without fairness and hhirness-regularizes online optimization without switching costs- as special cases. This demonstrates the power and generality of FairOBD.
Finally, empirically evaluate the performance of FairOBD, we conduct trace-driven experiments for AI workload shifting with a focus on geographically balanced distribution of public health risks. Our results demonstrate that FairOBD can effectively reduce the total fairness- rainaess-egullrrized cost, highlighting the empirical advantages of FairOBD compared to existing baseline solutions.
In summary, our impossibility results and the proposed ( (R, 5) benchmark lay solid foundation for studying online optimization with long-term fairness. We further advance the literature on smoothed online optimization by introducing a novel faimess regularizer that promotes equitable outcomes. Most importantly, we overcome the key technical challenges of entangling switching costs as type of action memory into the mirror descent update process, which is not allowed by the prior fairness-regulariize online algorithms 6 39 or smoothed online algorithms [8].
2
Related Works
Smoothed online optimization. Smoothed online optimization is challenging problem for which a growing list of algorithms have been designed to offer the worst-case performance guarantees in both adversarial and stochastic settings [3
47 20
11. Recently, it has also been extended in various
directions, including decentralized networked systems
(33, hitting cost feedback delays 42 bandit
cost feedback [2 50, 14, switching cost constraints [46 [1], future cost predictions [1 30]. and
machine learning advice augmentation 13 3 44
27 among others.
By considering a dynamic (constrained) offline optimal algorithm as the benchmark, our work focuses on the worst-case competitive ratio and considers the classic smoothed online convex optimization setting [18, but adds a long-term horizon fairness regularizer. This addition presents significant challenges to our algorithm design and is the key novelty that separates our work from the rich literature on smoothed online optimization. Another study (25 considers smoothed online conversion with a simple metric switching cost and a long-term constraint Σ 24 = 1 where Iq. E R is the scalar action time t (irrelevant to fairness). Besides different hitting and switching costs, our work is substantially separated from [25] as we consider a general and challenging fairness cost that regularizes the long-term faireess of online actions and necessitates new algorithm FairOBD.
Online optimization with fairness and long-term constraints. Our work broadly relevant to One key idea is to properly choose the Lagrangian multipliers that correspond to long-term constraints or fairness. For example, some earlier works [15 17 study online allocation problems by estimating a fixed Lagrangian multiplier using offline data, while other works design online algorithms by updating (or learning to predict) the Lagrangian multiplier in an online manner [16 56 4 54]. More recently, reinforcement learning has been applied to solve online problems with long-term constraints 24]. but it may not provide any worst-case performance guarantees in adversarial settings.
online optimization with fairness and long-term constraints 49 36 40).
Importantly, some recent studies 53 7 investigate online allocation problems in which the agent first fully observes the reward or cost function before selecting an action. In contrast, other recent work considers settings where certain components of the reward function are not revealed in advance 38 12). providing only bandit feedback requiring additional cost for revelation. Such limitations
3

---

preclude direct optimization of the reward via gradient- methods. Despite these differences, both types of settings can be addressed using dual mirror descent (DMD) or its variants, which update the Lagrangian multipliers based on the available context and the observed action sequence. DMD) can recover a family of classic online algorithms, including projected gradient descent [56] 40) and
multiplicative weight [ Similar algorithms are proposed for online stochastic optimization with distribution information in [2I]. While fairness can converted into long-term constraints with the introduction of auxiliary variable, it also substantially alters the algorithm designs and is known to be difficult to address, as exemplified in the context of online budget allocation [6. More crucially, given the updated dual variable at each round, the objective function in these studies is independent of the previous actions, but our objective function naturally has a memory due to switching costs and hence requires novel design of FairOBD.
3 Problem Formulation
Consider smoothed online optimization problem spanning episode of T time rounds denoted by [T]] = [1..... .T). At each time t E [T]. the agent observes a (potentially adversarially chosen) cost function f((-): :R - R+ and matrix A, A R M and chooses irrevocable action Ie E C IR without knowing the future information. The agent incurs two costs at time l: a hitting cost (1xx) and a switching cost (t-1) which captures how well the current cost f+(-) and penalizes temporal changes in actions, respectively. For notational convenience, we define Z [Ax|A E A, x X}. At each round t, the matrix A, maps the agent's action I; into an M-dimension cost vector, with each dimension corresponding to an entity for which fairness needs be taken into account. Thus, to regularize the online actions Ie for fairness, define long-term horizon fairness cost g(-) : RRM + IR+ in terms of T Σ Arxx.
fhichfairness
The overall cost is denoted by cost(21.T) and written as
T (
cost((1:T) = T Σ fe(ar) + Σ d(ai, x1-)) +
Σ Arot
(I)
3.1 Assumptions
We make the following standard assumptions as in the prior literature
18
40
47
55
Assumption 3.1. For each time t E [T'], the hitting cost fe( switching cost d(ær, 22-1) and long-term fairness cost 5( Σ'= Arai) satisfy the following properties
The hitting cost (z; is continuous and non non-negative within the action set X.
The switching cost d(x,, _x-1) 11) is the scaled squared Lz-norm, i.e., d(z,, It-1)) = O 11, Fe- 113 where is the initial action before the start of the episode.
The diameter the vector set Z = {Ar|A A E A, E X} bounded by Z, i.e., is the 12-norm unless otherwise noted.
A A'-''l < Z, where || The fairness cost gvy) is convex and I.-Lipschitz, i.e., ggy) 9(5") s L. Ily Ily-='ll - for any y. V 2.
These assumptions, e.g., non-negativity, are needed for theoretical analysis and widely considered in the literature 18 39 Additionally, it is common to consider a convex L-Lipschitz fairness cost. For example, well-known fairness cost that prioritizes the minimization of higher costs for disadvantaged entities is the lp norm, i.c., g(y) [lvlp p for p 2 1, as considered in a variety of applications including fair federated learning [29]. budget allocation [6], server scheduling 9. and geographical load balancing (88) among many others. As a special case when - co, the loc -nom fairness cost addresses the classic minimax faimesss.
In numerous online problems, including energy scheduling in power grids, object tracking in robotic-
human interactions, server capacity provisioning in data centers, and more in [7 long-term cost and smoothness are crucial considerations. To better motivate the consideration and make our model more concrete, we provide several application examples in Appendix
55 [3] both

---

4 The Hardness of Long-term Fairness Regularizer
Compared with switching cost which can be calculated with the action in the subsequent step, the long-term regularizer can be only evaluated at the end of the episode of T, with the complete action and context sequence. Thus, even intuitively, handling the long-term regularizer is considerably more challenging than managing switching costs. In this subsection, we will provide rigorous analysis on the impact of this inherent difficulty on two commonly considered performance metries: regret and competitive ratio.
sequence
Our theoretical results establish fundamental lower bounds on the performance gap between online and offline algorithms in the presence of such long-term dependencies, highlighting the hardness of the long-term fairness regularizer for online optimization even (in the absence of the switching cost).
Theorem 4.1. Assume that there is no switching cost (i.e., 31 O). Let uंr denote the optimal offline action sequence. For any online algorithm that produces an online sequence of aler the worst- case regret, defined as max (ur.Arr))))))) cost(rl:)) - -ost(fti))) is lower-bounded by a positive constant, i.e. (1()).
The proof idea of Theorem 4.1 is to construct adversarial future context sequence based the historical actions of the online algorithm, which can be found in Appendix C.I Notably, as the hitting and long-term costs are already averaged by the length of episode T. the constant performance gap in Theorem 4.1 can be translated to a linear regret when evaluating the total cost. Furthermore, with the switching cost eliminated (B = 0), this linear regret is solely attributed to the long- cost. The lower bound on the cost gap depends on the size of the action and context spaces, specifically quantified by the maximum norms of the action and context matrices (their diameters). Our proof establishes this lower bound by constructing an adversarial context sequence and identifying an offline optimal solution, both within a unit /2 ball. If the diameters of these spaces further increase, the lower bound on the regret would also increase accordingly through simple scaling of the adversarial sequence. Thus, if this diameter grows with the episode length T, the cost gap will similarly increase with T, potentially leading to superlinear regret in terms of the total cost.
To conclude, the findings in Theorem 4.1 highlight the fundamental limitation imposed by the lack of future context information, preventing any online algorithm from asymptotically matching the offline optimal cost.
Theorem 4.2. Assume that there is no switching cost (i.e., 31 = 0). Let uier denote the optimal offline action sequence. For any online algorithu that produces an online sequence of "| the competitive is lower-bounded by Q(T)), i.e., C 2 Q(T).
con(s]ir)
ratio, defined as C+ (ax(ffsr,Aar))) cost
In addition to regret, the competitive ratio is a widely used metric for evaluating online algorithms, particularly against dynamic benchmark. Unlike a static benchmark, the dynamic setting allows the offline optimal action to vary over time, potentially achieving significantly lower costs. In such dynamic scenarios, achieving sublinear regret may be impossible, making the competitive ratio more suitable performance measure. A finite competitive ratio guarantees that an online algorithm's 's cost is bounded by constant multiple of the offline optimal cost. For problems with only switching and hitting costs, [99 achieved the state-of-the-arr finite competitive ratio. Given that our problem setting also employs similar dynamic benchmark, competitive ratio appears to be an appropriate evaluation metric. However, the inclusion of a long-term regularizer fundamentally alters this landscape.
The inherent difficulty introduced by such regularization is a long-standing research question. For example, [6] considers a related online optimization problem focused on maximizing total reward under constraints on both the context sequence and the offline optimal benchmark. They conjecture that no online algorithm could achieve vanishing regret or a finite competitive ratio. Based on our Theorem 4.2 and |nd|4.]] 4.1 we rigorously confirm that in this setting, neither a finite competitive ratio nor vanishing regret is attainable, even in the absence of switching costs. These theorems highlight the fundamental challenge introduced by the long-term regularizer. To enable meaningful performance comparisons despite this challenge, we slightly constrain the offline optimal benchmark and establish an asymptotic competitive ratio under this modified benchmark.
5

---

Definition 4.3 ((R, -pptimal algorithm). An action sequence Fi.r is (R, 8)-otimal if it satisfies:
RR
T
R T
Fi. arg min cost((11)) s.t., Zur
Σ
Σ
A
A
S
6,
(2)
(H-11))++
where It represents the frame size and K is positive integer denoting the number of frames in an episode such that Rt K = T, and 5 2 0 measures the allowable total deviation between the frame-wise (1=(k-1)R+1 A,rī and episode-wiss average E ArZī scaled by R.
RR
The constrained benchmark, denoted 8),0))PPT imposes restriction on the offline optimal solution or the adversarial context sequence. Specifically, the parameter 8 limits the total deviation between the frame-wise average fairness vector, A,æz, and its episode-wise counterpart, scaled by the frame length R. The stringency of this (R2 6) constraint is inversely related to the values of R and ö; increasing either parameter makes the constraint less restrictive, and vice versa. This benchmark effectively limits the power of the offline optimum by assuming its total variance is sublinear with respect to the episode length T'. If the total variance of the offline optimal action sequence were permitted to grow linearly with T', the environment can continuously shift the average of the optimal long-term cost. other words, the offline optimal long-term cost is able to maintain a constant distance from the online algorithm's cost, thus explaining the constant cost gap observed in Theorem 4.1 Therefore, we assume 5 in the offline optimal benchmark is always sublinear with respect to the episode length T. Moreover, similar constrained offline optimal benchmarks have also been widely considered in the literature, such as the pritching-constrained OPT in smoothed online optimization
Notably, in many practical applications such as data center scheduling, this is a very natural assumption, where the context A, exhibits some periodicity evidenced by the diurnal workloads. In this case even the actions chosen by the unconstrained offline algorithm can exhibit periodic pattern, thus resulting in sufficiently small ó for a certain large R.
18 and frame-wise OPT with limited future information
40 39
In the following, we interchangeably refer to (R, 5) as OPT whenever applicable without ambiguity. Next, define the asymptotic competitive ratio (7 by considering T oo follows. Definition 4.4 (Asymptotic competitive ratio). Given offline (R, 8)-otimaal algorithm OPT, an algorithm ALG is asymptotically C-competitive against OPT for any problem instance y =
{fr, A ..... T), it satisfies sup, limy-
cost(ALG) C cost(O
5 FairOBD: Fairness- Online Balanced Descent
We propose novel online algorithm FairOBD for faimnes--regulaizzed smoothed online optimization detined Eqn. (I. Compared to the existing smoothed online optimization literature without fairness consideration [4
18 42 27], the crux of FairOBD is to decompose the horizon fairness cost o( 7 Σ'= A into online costs by introducing new regularizer and an auxiliary variable that carefully balances the hitting cost, switching cost, and fairness cost.
5.1 Algorithm Design
Even in the absence of the fairness cost, the problem of smoothed online optimization is already challenging due to the potential conflicts between minimizing the current hitting cost fe(x,) and staying closer to the previous action to reduce the switching cost d(x,, ((-1). The fairness cost g( DT,, Arz,) is defined in terms the long-term average of + DT= A,x, and hence cannot be determined until the end of time T,, further creating substantial challenges. FairOBD addresses these challenges by introducing auxiliary variable and decomposing 9( Σ/= A,2s)) into online version, and by balancing the hitting cost, switching cost, and fairness cost.
5.1.1 Decomposing the fairness cost
To address the challenges stemming from the horizon faimess cost o ΣT. Aaxi), we introduce an auxiliary variable E Z {a Ar|A A, X}. J. In the long run, we aim to choose the actions

---

Algorithm FairOBD:
Fairness-regularizee Online Balanced Descent 1: Input: Initial K1, reference function k(()), and learning rate
2: for [= to 7 do
3: Receive f((.) and A,
4: Obtain the action æy and auxiliary variable 2t by solving the following:
(fe(or)) + Aid( IT-1) 21ER
X2 1 vell² + Riz Arx + g(zx) ReRs):
min
(5)
2
where 2, arg m fz(z).
5: Obtain stochastic subgradient of Ae: de = 24 A 2t
6: Update the dual variable by mirror descent: K4+1 arg min ar (d,, k)) + (K,, K4), where
Va (z. y) = h(x) h(y) Vh(y) y) is the Bregman divergence.
7: end for
that approximately satisfy the condition Σx= A,x - average of the auxiliary variable can serve as an effective estimator for the horizon fairness cost. Altematively, we can view as dynamic "budget" that is allocated to the agent guide its online actions. Thus, we reformulate the problem (T as follows:
-t=1
This ensures that the horizon- wise
T Σ dlar, (
1 I
T s.t. Σ
T
min #LTT PI.T
Σ fE(T))
+ 7
L E=1
A
(3)
1=1
whose optimal actions are denoted by (R1,T, 2. Importantly, the offline optimal cost of is the same as that the original problem in (I). This point can be seen by considering &1
3
T E A, and f = Lं.r where vi.r is the offline optimal solution to ①
While the reformulated problem (3) decomposes the horizon faimess cost g( + E -1=1 A,x)) by the introduction of 21:7 and has the same optimal cost as (I). it presents new challenge due to the long-term constraint Σ ArT; = Σ 2t where itself is also an online action. To address this challenge, we note that unlike real budget constraint that cannot be violated any round (7). the long-term constraint in (3) only needs to be approximately satisfied. Therefore, we relax the constraint and instead minimize the Lagrangian form of 3 as follows:
T
T
T
T
T
min Fur,
Σ (x() + Ed
+ - :=1
g + Ky
Σ
A
Σ
(4)
T
where K2 E R.M is the estimated Lagrangian multiplier at round [T].
Had all the future information (firr(-), ALT) been provided in advance, we could easily determine KT = x". But, for online optimization, need to update 2, based on the currently available information without knowing the future. Morcover, interestingly, given Ke at round f, 2, and 2; can be independently solved in 4 Thus, propose employ mirror descent to update K2 online, based on which we subsequently optimize x, and 2 at each round E [T].
the optimal 81
While 7 6 40 use mirror descent to update the Lagrangian multiplier for online allocation of fixed given budget, our work has crucial difference: given K2 at each round t, our objective includes
memory in the form of switching cost d(x,, .T-1), whereas the objective in 7 6 40 only depends on the current action 2t. This difference voids the key steps in the proof techniques of requires additional care to the switching cost.
and
5.1.2 Balancing the hitting cost, switching cost, and fairness cost
To further reconcile conflicts between minimizing the current hitting cost fx(2;) and staying closer the previous action reduce the switching cost d(x,, æt-1), we propose FairOBD that uses the term A,æ, as fairesss regularizer while optimizing online. The fairness regularization effect of
Ke A,a; comes from the fact that is intended to meet the long-term constraint Σ AçA, =Σ z1 for fairness, while "balanced" is due to two new hyperparameters X₁ (0, and X2 [0,00] to balance the hitting cost f(();) and switching cost ((x1, The hyperparameters \ (0.
7

---

and d2 E [0, oo) can be optimally set to optimize the asymptotic competitive ratio in Theorem 5.2 Furthermore, given Kg. the auxiliary variable 2, can be easily optimized by solving g(2+) 2t
Before completing the design of FairOBD, we introduce a reference function h(.) RM- - IR to define the Bregman divergence in our update of K; using mirror descent. Specifically,
choose f(-)) : R + IR that is (-strongly convex and 32-smooth [48]. For example, Line 7 of Algorithm follows the classic additive update rule K(+1 |Kv 7d.]** where > 0 is the learning rate when
h(k)= = 2 whereas it becomes the multiplicative update when h(k) = T: log(R) 77. The specific
In]l
choice h--) does not affect performance analysis in Theorem 5.1 and 5.2
Next, we formally describe FairOBD in Algorithm [T] In Line 4, we optimize z, to balance the hitting cost, switching cost, and fairness cost. In Line 5, we optimize as fairness budget for guiding the optimization of s4 in the future. Lines and 7, we update K++1 using mirror descent.
5.2 Performance Analysis
We present the analysis of FairOBD in terms of the asymptotic competitive ratio as follows.
Theorem 5.1. Suppose that zi,r is the action produced by the (R, -optimal algorithm OPT. Assume
that there no switching cost (i.e., 31 0). By setting the learning rate as rj ( 3) and ||]] 2 ). the cost of
parameters A1= X22 0, and initializing FairOBD is upper bounded by
(++) (or K1 = 0 if l(())
1
6 p2
LU 2 ny
L8
cost(xirr) Scost(ai.r) +
2² R 2|| 32Lg
_
+
+
+ T
21
T
1pl
=cost(riar) + O(T L T
(6)
and I and 32 are the strong where the parameters m, and L are specified in Assumption 3.1
convexity and smoothness parameters of the reference function h(-), respectively.
In Theorem 5.1 FairOBD achieves an asymptotic competitive ratio of I when the total deviation 8 is sublinear in T. The total deviation ô quantifies the fundamental difficulty of the online problem itself, independent of the algorithm design. As discussed regarding the hardness of the long-term regularizer, if 5 grows linearly with T, no online algorithm can attain sublinear regret. Therefore, [5. demonstaats that FairOBD achieves vanishing regret as the episode length approaches infinity, even in worst-case scenarios. This vanishing regret highlights the effectiveness of FairOBD in addressing the long-term regularizer, which is achieved by decomposing the long-term cost with a set of auxiliary variables. Furthermore, the dual variable within FairORD dynamically adapts through continuous online updates, which drives the cost of FairOBD to eventually converge to the onfline optimal benchmark.
Theorem 5.2. Suppose that ui. is the action produced by the (R, 8) -optimal algorithm OPT and that the hyperparameters X E (0, and X2 E [0, oc). Assume further the hitting cost f((-) is m-strongly convex for any t = 1,... T. By initializing K1 = ( (or 11 = 0 if h(())) 2 and setting the learning rate 1 (T ). the cost of FairOBD is upper bounded by
cost(x1.)) SC cost (F
17 n2 + Z|1n 11 + B2L
1
Z
+2
LZ
+
2 n7at
Z 7|
+
Lg T
A 21
T
1
n
L8
=C =Coco(((zirr)) + OT +) +
XTT'
}. The parameters m, Z and L are specified in Assumption 3.1 and I and B2 are the strong convexity and smoothness parameters of the reference function h(-). respectively. In addition. by considering ö in any sublinear forms in T and optimally setting
where C max{ m= 1 X131 m+
md1
A1 E (0, 1] and A2 E (0) such that m + A22
Aam
+
/
48
FairOBD achieves an
asymptotic competitive ratio of 1 (1+ v1+ 1+
4.g
against (R, (2,,)--PT when T + co.
8

---

As demonstrated in Equation 77. by properly setting the learning rate and initial Lagrange multiplier, FairOBD's cost asymptotically converges to within a constant factor of the (R, consttraid offline optimal cost. This convergence guarantees the stability of both the auxiliary variable and multiplier, ensuring robust performance irrespective of the context sequence. In our algorithm, the dual update is conducted using mirror descent, which generalizes the standard gradient descent as special case when the reference function is chosen as h(x)) = =|1=||?. Consequently, Theorem 5.2 and Theorem 5.1 also cover the performance analysis of dual updates with gradient descent by setting / B2 1. In addition, a comparison of these two theorems reveals that the constant C' in Theorem 5.2 arises solely from the inclusion of the switching cost. Furthermore, by optimally setting (A1, ^2) to minimize
C' in Equation 77 FairOBD asymptotically achieves the competitive ratio of 1 { [ + V 491
m
This ratio matches the best-known competitive ratio lower bound [18] for the problem without a fairness cost. This observation highlights the superior performance of FairOBD and confirms that C is inevitable due to the switching cost.
Unlike standard online smoothed optimization 19]. the long-term fairness cost impacts the total cost of FairOBD in two-fold, primarily due to the L-Lipschitz property of the long-term fairness constraint. Generally speaking, larger L implies faster change speed of fairness function, which introduces additional uncertainties when optimizing the auxiliary variables in g(z)). This imprecise estimation slows down the convergence speed of the dual variable, as reflected in the second last term in Eqn 77. Moreover, since 5 represents the discrepancy between the frame-wis and episode-wisg wise averages of Aga4 in the offline optimal benchmark, a larger L amplifies this difference in FairOBD's final faimess cost, as demonstrated by the last term in Equation (7). Thus, the overall performance of FairOBD is significantly influenced by the Lipschitz constant L, which bounds the first-order smoothness of the fairness cost.
The additive gap observed in Theorem 5.1 and Theorem 5.2 is directly influenced by the inherent difficulty associated with the long-term cost. This difficulty is captured by R and ò: as R and/or d increase, the potential for adversarial context sequences in the long-term cost becomes greater. which is a fundamental challenge for any online algorithm. Thus, It and d quantify the maximum level of adversarialness in the context sequence. However, many real-world applications are less adversarial, exhibiting predictable periodic patterns (such as the diurnal cycles in AI workload distributions). These patterns significantly reduce 8, the long-ter long-term deviations. Consequently, for a reasonably large yet finite Rt the total deviation between the online performance and the unconstrained offline optimal benchmark can remain constant or grow sublinearly with T.
In addition to the rigorous insights provided by Theorem 5.2 our proof technique also represents a novel technical contribution. Unlike existing proof techniques that typically rely on the assumption of independence between per-round objective functions, our approach does not require such an as- sumption. Removing the assumption of temporal independence is crucial in our fairness-regularized smoothed online optimization problem, as the switching cost functions inherently violate this assump- tion by incorporating historical actions. Consequently, comparing the costs of per-round objective functions between FairOBD and the offline optimal benchmark becomes highly challenging, as their cost functions are no longer identical under these conditions. To address this limitation, Lemma DD. and D.4] establiss a theoretical foundation for such comparison by introducing an intermediate benchmark with per-round objective functions aligned with those of FairOBD. This intermediate benchmark effectively bridges the gap between the two policies, each associated with distinct sets of cost functions, enabling meaningful and rigorous comparison. Though the current result relies on the properties of squared (2-norm in switching cost, it is promising to relax this assumption to accommodate more general strongly convex and smooth functions. Specifically, in Lemma D.3 and Lemma D.4 the results can be directly extended under strong convexity, since the squared 12-norm is a special case where convexity and smoothness coincide. Furthermore, when converting the intermediate benchmark to the offline optimal benchmark, the gap between the two can also be bounded by the strong convexity of the switching cost. It is interesting future work to study this more general setting. More broadly, the proof techniques in our approach represent substantial development in addressing states influenced by past actions, extending beyond the limitations of existing approaches that are restricted to handling memoryless functions.

---

Empirical Results
Our empirical study investigates the problem fair resource provisioning for Al inference services in geographically separated data centers, where decisions incur instantaneous hitting costs (energy consumption and long-term fairness cost quantifying regional public-health impacts from electricity generation pollution. FairOBD decomposes and dynamically optimizes all three cost components via auxiliary variables and mirror-descent updates improve cost efficiency, action smoothness, and long- term fairness simultancously. In our simulation, we use the one-week trace of normalized LLM inference requests from (37,. and route demand across seven selected data centers (Arizona, Iowa, Illinois, Texas, Virginia, Washington, Wyoming) with publicly available electricity prices, PUE values, and health-damage rates from Wat'Time [52] We compare FairOED against five benchmarks: the offline optimal (OPT), offline fairness-only (FairOPT), hitting-cost minimizer (HITMIN), Regularized Online Balanced Descent (ROBD), and Dual Mirror Descent (DMD).
penalties), switching costs (reconfiguration overhead), and
We also test FairOBD with different learning rates and different weights for the fairness cost to test its robustness under different settings, with more details in Appendix B Our numerical results (Table in Appendix B demonstrate that FairOBD achieves the lowest total cost among online methods, with the minimal cost gap to the offline optimal. Moreover, FairOBD attains the smallest fairness cost among online baselines, while maintaining low switching overhead. These results confirm that explicit incorporation and dynamic optimization of long-term fairness in FairOBD yields superior performance across all cost dimensions.
7 Conclusion
We study a novel and challenging problem of fairness-reullarized smoothed online convex optimiza- tion. Our main contribution is the proposal of FairOBD to reconcile the tension between minimizing the hitting cost, switching cost, and fairness cost. Importantly, FairOBD offers a guaranteed worst- case asymptotic competitive ratio against 5)-OPT for finite R and sublinearly growing by considering the problem episode length + co. Moreover, our analysis can recover the best-known results for two existing settings (i.e., smoothed online optimization without faimess and fairness- regularized online optimization without switching costs) as special cases. Finally, we run trace-driven experiments of dynamic computing resource provisioning for socially responsible AI inference demonstrate the empirical advantages of FairOBD over existing baseline solutions.
8 Limitation and Impact Statements
While simultancously addressing fairness and action smoothness in online optimization, FairOBD is designed based on of assumptions, including non-negative hitting costs and squared 12-morm switching costs. Therefore, it is interesting future work to overcome these limitations by, e.g., relaxing the strong convexity assumption, considering more general forms of switching costs, and/or incorporating potentially untrusted predictions of future information to further reduce the overall cost. Although work can potentially increase awareness of fairness in online optimization, do not foresee negative societal impacts or the need for safeguards due to the theoretical nature our work.
Acknowledgment
Pengfei Li, Yuelin Han, and Shaolei Ren were supported in part by the NSF under grants CNS- 2007115 and CCF-2324941. Adam Wierman was supported by NSF grants CCF-2326609, CNS- 2146814, CPS-2136197, CNS-2106403, and NGSDI-2105648 as well as funding from the Resnick Sustainability Institute.
References
[1] Shipra Agrawal and Nikhil R Devanur. Fast algorithms for online stochastic convex program- ming. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 1405-1424, 2014.
10

---

[2] Idan Amir, Guy Azov, Tomer Koren, and Roi Livni. Better best of both worlds bounds for bandits with switching costs. In S. Koyejo, Mohamed, Agarwal. D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 15800-15810. Curran Associates, Inc., 2022.
[3] Antonios Antoniadis, Christian Coester. Marek Elias, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. In ICML, 2020.
[4] Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing, 8 811::211164, 2012.
[5] Kamiar Asgari and Michael J. Necly. Bregman-style online convex optimization with energy harvesting constraints. Proc. ACM Meas. Anal. Comput. Syst., 4(3), nov 2020.
[6] Santiago Balseiro, Haihao Lu, and Vahab Mirrokni. Regularized online allocation problems: Fairness and beyond, 2021.
[7] Santiago R. Balsciro, Haihao Lu, and Vahab Mirrokni. The best of many worlds: Dual mirror descent for online allocation problems. Operations Research, 0(0): May 2022.
[8] Santiago R Balseiro. Haihao Lu, and Vahab Mirrokni. The best of many worlds: Dual mirror descent for online allocation problems. Operations Research, 71(1):00-119 2023.
[9] N. Bansal and K. Pruhs. Server scheduling the Ip norm: a rising tide lifts all boat. In STOC,
2003.
[10] California Government Operations Agency. Benefits and risks of generative artificial intelligence report. State of California Report, November 2023.
[11] Niangjun Chen, Gautam Goel, and Adam Wierman. Smoothed online convex optimization in high dimensions via online balanced descent. In COLT, 2018.
[12] Xi Chen, Jiameng Lyu, Yining Wang, and Yuan Zhou. Network revenue management with demand learning and fair essurcc--onsumppien balancing. Production and Operations Man- agement, 33(2):494-511, 2024.
[13] Nicolas Christianson, Tinashe Handina, and Adam Wierman. Chasing convex bodies and functions with black-box advice. In COLT, 2022.
[14] Ofer Dekel, Jian Ding, Tomer Koren, and Yuval Peres. Bandits with switching costs: f2/3 regret. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC '4, page 459-467, New York, NY, USA, 2014. Association for Computing Machinery.
[15] Nikhil R Devanur and Thomas P Hayes. The adwords problem: online keyword matching with budgeted bidders under random permutations. In Proceedings of the 10th ACM conference on Electronic commerce, pages 71 71-78, 2009.
[16] Nikhil R Devanur, Kamal Jain, Balasubramanian Sivan, and Christopher A Wilkens. Near optimal online algorithms and fast approximation algorithms for resource allocation problems. Journal of the ACM (JACM), 66(1):1-41 2019.
[17] Jon Feldman, Monika Henzinger, Nitish Korula, Vahab Mirrokni, and Cliff Stein. Online stochastic packing applied to display ad allocation. In European Symposium Algorithms, pages 182-194, 2010.
[18] Gautam Goel, Yiheng Lin, Haoyuan Sun, and Adam Wierman. Beyond online balanced descent: an optimal algorithm for smoothed online optimization. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, Red Hook, NY, USA, 2019. Curran Associates Inc.
[19] Gautam Goel, Yiheng Lin, Haoyuan Sun, and Adam Wierman. Beyond online balanced descent: An optimal algorithm for smoothed online optimization. Advances in Neural Information Processing Systems, 32: 1 1811-187588... 2019.
[20] Gautam Goel and Adam Wierman. An online algorithm for smoothed online convex optimiza- tion. SIGMETRICS Perform. Eval. Rev., 47(2),6-8, December 2019.
[21] Jiashuo Jiang, Xiaocheng Li, and Jiawei Zhang. Online stochastic optimization with wasserstein based non-stationarity. arXiv preprint arXiv:20/2.0696. 2020.
[22] Amba Kak and Sarah Myers West. Al Now 2023 landscape: Confronting tech power, Al Now Institute, April 2023.

---

[23]
Joseph B. Keller, Manann Donoghoe, and Andre M. Perry. The U.S. must balance climate justice challenges in the era of artificial intelligence. Brookings Institution, January 2024.
[24]
Weiwei Kong. Christopher Liaw, Aranyak Mehta, and D. Sivakumar. A new dog learns old tricks: RL finds classic optimization algorithms. In ICLR, 2019.
[25]
Adam Lechowicz, Nicolas Christianson, Bo Sun, Noman Bashir, Mohammad Hajiesmaili, Adam Wierman, and Prashant Shenoy. Online conversion with switching costs: Robust and Seariing-uggmente algorithms. In SIGMETRICS, 2024.
[26] Pengfei LI, Nicolas Christianson, Jianyi Yang, Adam Wierman, and Shaolei Ren. Learning for sustainable online scheduling with competitive fairness guarantees. In Proceedings of the 16th ACM International Conference on Future and Sustainable Energy Systems, pages 63-79, 2025.
[27] Pengfei Li, Jianyi Yang, Adam Wierman, and Shaolei Ren. Robust learning for smoothed online convex optimization with feedback delay. In NeurIPS, 2023.
[28] Pengfei Li, Jianyi Yang, Adam Wierman, and Shaolei Ren. Towards environmentally equitable ai via geographical load balancing. In e-Energy, 2024.
[29] Tian Li, Maziar Sanjabi, Ahmad Beirami, and Virginia Smith. Fair resource allocation in federated learning. In International Conference on Learning Representations, 2020.
[30] Yingying Li, Xin Chen, and Na Li. Online optimal control with linear dynamics and predictions: Algorithms and regret analysis. In NeurlPS, Red Hook, NY, USA, 2019. Curran Associates Inc.
[31] Yingying Li and Na Li. Leveraging predictions in smoothed online convex optimization via gradient-based algorithms. In NeurlPS, volume 33, 2020.
[32] M. Lin, A. Wierman, L. L. H. Andrew, and E. Thereska. Dynamic right-sizing for power- proportional data centers. In INFOCOM, 2011.
[33] Yiheng Lin, Judy Gan, Guannan Qu Yash Kanoria, and Adam Wierman. Decentralized online convex optimization in networked systems. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 13356-133923 PMLR, 17-23 Jul 2022.
[34] Yiheng Lin, Gautam Goel, and Adam Wierman. Online optimization with predictions and non-convex losses. Proc. ACM Meas. Anal. Comput. Syst., 4(1), May 2020.
[35] Wanteng Ma, Ying Cao, Danny HK Tsang, and Dong Xia. Optimal regularized online allocation by adaptive re-solving. Operations Research, 73(4):0079-2996, 2025.
[36] Mehrdad Mahdavi, Rong Jin, and Tianbao Yang. Trading regret for efficiency: Online convex optimization with long term constraints. J. Mach. Learn. Res., 13(1):2503-25233 sep 2012.
[37] Microsoft Azure
Azure Public Dataset.
https:///ithub... Azure/
CaurePublicDatasee 2024.
[38] Mathicu Molina, Nicolas Gast, Patrick Loiseau, and Vianney Perchet. Trading-off price for data quality achieve fair online allocation. Advances in Neural Information Processing Systems, 36:40096-400 40139, 2023.
[39] M. J. Neely. Universal scheduling for networks with arbitrary traffic, channels, and mobility, http:/ sttp://aaztr wwwp://.wrrr/bb/////ooae 0960
[40] M. Neely. Stochastic Network Optimization with Application to Communication and Queueing Systems. Morgan & Claypool, 2010.
[41] Michael J. Neely. Stochastic Network Optimization with Application to Communication and Queueing Systems. Morgan and Claypool Publishers, 2010.
[42] Weici Pan, Guanya Shi, Yiheng Lin, and Adam Wierman. Online optimization with feedback delay and nonlinear switching cost. Proc. ACM Meas. Anal. Comput. Syst., 6(1), Feb 2022.
[43] Dana Pessach and Erez Shmueli. A review on fairness machine learning. ACM Comput. Surv, 55(3), feb 2022.
[44] Daan Rutten, Nicolas Christianson, Debankur Mukherjee, and Adam Wierman. Smoothed online optimization with unreliable predictions. Proc. ACM Meas. Anal. Comput. Syst., 7(1),
mar 2023.
12

---

[45] Daan Rutten and Debankur Mukherjee. Capacity scaling augmented with unreliable machine learning predictions. SIGMETRICS Perform. Eval. Rev., 40(..242224422 26, jan 2022.
[46] Uri Sherman and Tomer Koren. Lazy oco: Online convex optimization
switching budget. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 3972-3988.
PMLR, 15-19 Aug 2021.
[47] Guanya Shi, Yiheng Lin, Soon-Jo Chung. Yisong Yue, and Adam Wierman. Online optimization with memory and competitive control. In NeurIPS, volume 33. Curran Associates, Inc., 2020.
[48] Zhan Shi, Xinhua Zhang, and Yaoliang Yu. Bregman divergence for stochastic variance re- duction: maddle-point and adversarial prediction.
Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Informa- tion Processing Systems, volume 30. Curran Associates, 2017.
[49] Sean Sinclair, Gauri Jain, Siddhartha Banerjee, and Christina Lee Yu. Sequential fair allocation: Achieving the optimal envy-efficiency trade-off curve. Oper. Res., 7165):6689-175. sep 2023.
[50] Juaren Steiger, Bin Li, Bo Ji, and Ning Lu. Constrained bandit learning with switching costs for wireless networks. In IEEE INFOCOM 2023 IEEE Conference on Computer Communications, pages 1-10, 2023.
[51] Guanghui Wang, Yuanyu Wan, Tianbao Yang, and Lijun Zhang. Online convex optimization with continuous switching constraint. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[52]
WattTime. Data signals for WattTime dataset, 2024.
[53] Jianyi Yang, Pengfei Li, Mohammad Islam, and Shaolei Ren. Online allocation with replen- ishable budgets: Worst case and beyond. In SIGMETRICS, 2024.
[54] Jianyi Yang and Shaolei Ren. Learning-assisted algorithm unrolling for online optimization with budget constraints. In AAAI, 2023.
[55] Lijun Zhang, Wei Jiang, Shiyin Lu, and Tianbao Yang. Revisiting smoothed online learning. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[56] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pages 928-936, 2003.
13

---

Appendix
A Real-world Applications with Long-term Costs
In this section, we present several real-world application that emphasizes long-term fairness along with the switching cost. We provide concrete modeling for these applications and demonstrate how these two applications align closely with our problem formulation.
A.1 Geographical Load Balancing with Balanced Public Health Costs
The exponentially growing demand for AI has been driving the recent surge of data centers around the globe, which are notoriously energy-consuming and thus have huge environmental impacts in terms of the local air pollution and carbon emissions (e.g. for fossil-fuel based power plants). The escalating air pollution resulting from AI computing significantly contributes to various health issues, including lung cancer, heart discase, and cardiovascular problems. Thus, the rise in ambient air pollution leads substantial public health costs, encompassing lost workdays, increased medication usage, and increased hospitalization rates. More critically, the public health costs of data centers are becoming increasingly unevenly distributed across different regions, disproportionately affecting marginalized communities. To mitigate the uneven distribution of public health impacts from Al computation, an effective approach to leverage fairness-awar aware geographical load balancing to fairly distribute the environmental costs across different data center locations (2 and, consequently,
public health risks across diverse data center locations.
Specifically, let 24 E R be the number of active servers or computing capacity to process incoming workloads in N different data centers at time t. With a provisioning capacity of Ir, there is an operational cost that includes the energy cost and a penalty term for workload imbalance, which can be modeled as the hitting cost f(,) [32] When adjusting computing capacities, a switching cost d(z;, 2t-1) arises due to server reallocation, workload migration, or wear wear-and and-tear. Additionally, health cost A, incurred across N locations due to air pollution from electricity generation [59], influenced by the local grid's 's real-time fossil fuel intensity. Further modeling details can be found in Appendix B.
A.2 Socially-fair AI Resource Provisioning
Large AI models often have multiple sizes, each with distinct performance and resource usage tradeoff. For example, the GPT-3 model family has eight different sizes, ranging from the smallest one with 125 million parameters to the largest one with 175 billion parameters [58). As a result, the amount of computing resources can directly affect the model selection and inference quality during inference, and needs to be carefully determined based on the number of user requests from different regions. As we become increasingly reliant on AI for acquiring knowledge, insufficient resource provisioning can lead to subpar Al model performance and could disproportionately jeopardize the prospects of users/individuals from certain disadvantaged regions. Thus, the computing resource provisioning for users from different regions must be fair in the long run. In addition, there is switching cost when adjusting the computing resource capacity (e.g.. by activating otherwise hibernating servers).
We consider a discrete-time model for the Al server provisioning problem, where E RRM represents the user demand from M different regions time and x; E [Tmin Fmax] denotes the amount of provisioned Al servers to meet the demand. The hitting cost fxz, Vt) encompasses both the electricity expenses of the AI servers and penalty term for any dropped workload demand. The switching cost d(z,, 1))1) models the cost incurred by hardware and software reconfiguration, particularly when server provisioning undergoes frequent or substantial changes. At each time slot, we assume the provisioned AI servers are shared by each region in proportion to their user workload demand. To promote fair distribution of AI resources among the M regions within the horizon, we account for each region's s dynamic resource share, which varies based on its fluctuating workload demands. Specifically, we employ min-max fairness function over the total amount of allocated Al resources for the M regions.
14

---

B Experiment
In this section, experiments of fair computing resource provisioning for Al inference services. Our results demonstrate that FairOBD can effectively reduce the total fairness-regularizee cost, highlighting the empirical advantages of FairOBD compared existing baseline solutions.
B.1 Simulation Setup
We investigate the challenge of fair resource provisioning for Al data centers that deliver inference services to dynamically routed Al workloads. At each time step, we dynamically route incoming user demand across geographically dispersed Al data centers and provision server/GPU resources accordingly. This provisioning process incurs a hitting cost (e.g., energy cost, carbon emissions, and penalties for imbalanced workload distribution), as well as a switching cost representing the reconfiguration overhead associated with changes in provisioning decisions. Furthermore, electricity consumption contributes to public health risks within the local community due to air pollution generated during electricity production. We incorporate long-term faimesss cost that quantifies the degree of public health impacts on the most affected region across all Al data centers.
B.1.1
Model
We consider discrete-time model where each round (or time slot) is one hour. As each round has the same duration, we interchangeably use power and energy wherever applicable without ambiguity. To fulfill the demand for Al inference service at time I, denoted as Ws, we need to determine Al server/GPU provisioning action Fz. The resource provisioning decision defined as I [T1,,,' ... .NN,). where Ii, denotes the provisioned server/GPU capacity for data center i e [MV] subject to constraint F₁ S. MM; where M, is its maximum capacity. Additionally, to guarantee the optimal quality of experience for users, we consider all the AI workloads are instantancously
served without further delays, where Σ Tiat Wy. The provisioning decision incurs a hitting cost (e.g., energy cost and penalty for imbalanced workload distribution), and a switching cost due to changing the provisioning decisions. Furthermore, electricity consumption contributes to public health risks within the local community due to air pollution generated during electricity production. We incorporate a long-term fairness cost that quantifies the degree of public health impacts on the most affected region across all AI data centers. We model these three costs as follows.
The hitting cost encompasses the cost of energy consumption and penalties for imbalanced workload scheduling. Specifically, we model server power consumption as a linear function of provisioned computing resources, q Ti And the non-IT power consumption (e.g., cooling systems) is modeled by multiplying the power usage efficiency (PUE) "/ over the power consumption at data center i E [N].
Thus, the total electricity expenses of AI computing can be expressed as Σx" Pê, " q Ti.t. where pf, denotes the time-varying electricity price at location i. Additionally, given the fluctuating AI workload, it's highly imperative to achieve balanced workload distribution, both spatially and temporally. Within time slot t. as the entire Al workload must be fulfilled collaboratively by N data centers, imbalanced workload distribution can overload several data centers and result in low utilization rate for some data centers. The low utilization may leads to wasted reserved capacity and potentially increased idle power consumption. Additionally, from the perspective of whole horizon T, a smaller temporal variation in the provisioned server capacities is also preferred, considering the same amount of total workload. To this end, incorporate regularizer in ||l² into the hitting cost of data center i. When it's summed over the entire planning horizon T, this term represents the squared L2-norm of the provisioned server capacity vector, [Ti,1," "...... ,T,T].
To sum up, the hitting cost at time is defined as
N ph. 76 q- Viet U1 1=1
fe(
Σ
||cel|
Besides, the switching cost d(z,, 21-1) between consecutive actions. Here, U2 is a hyperparameter that reflects the overhead associated with hardware reconfiguration and communication arising from dynamically routed workloads.
92 11, - x penalizes the frequent large changes
Scaling laws are observed in large Al services [60, such as large language models, demonstrating an exponential increase in computational requirementss to achieve continuous performance improvements.
15

---

Average Health Price (S/MWh)
Average Electricity Price (S/MWh)
Location
PUE (ri)
Arizona
17.29
77.7
1.18
lowa
62.81
62.6
1.16
Illinois
49.93
82.6
1.35
Texas
48. 19
63.0
1.28
Virginia
52.68
87.0
1.14
Washington
17.55
62.0
1.15
Wyoming 34.79
76.1
1.11
Table 1: Information for selected data centers
This rapid escalation in computation translates to substantial energy consumption. Due to the air pollution generated during electricity production, the increased electricity consumption associated with these models contributes public health risks within local communities. Following the methodology in [52], we denote the health damage rate as A, [AI,t,... AN,I]. which reflects the associated air pollution and consequent health risks resulting from the electricity consumption. By strategically aligning AI computation with time periods and locations that are abundant with cleaner energy sources (e.g., solar, wind), the health damage rate can be significantly minimized. At the same time, ensuring fair distribution of public health risks is crucial when dynamically routing Al workloads. We incorporate long-term fairness cost that quantifies the degree of public health impacts on the most affected region across all Al data centers, formulated as below
T
q
9
F1:
U3
A
It
T
where the norm can recover the infinity. By regularizing the overall public health risk in the long term,t we can not only promote social fairness and mitigate widening socioeconomic gaps, while maintaining sufficient flexibility for dynamic AI workload routing.
min-max fairness function as p approaches
By summing up the hitting, switching and long-term fairness cost, the objective function is defined as below
arg min
1 T
Σ fe(ar)
1 T
Σ d(x,, + o (11:))
(
(10)
s.l.
Σ Li. = Whs E [1,
24,1 S M, Vi E NJ. We [1,T]
B.1.2 Datasets and parameter settings
We employ a publicly available inference trace dataset for LLM services on Azure 37 a sample of coding- These traces are collected between May 10th and May 16th, 2024. The dataset provides user demand patterns across different times of week.
We normalize
inference requests processed by multiple LLM services within Azure.
Specifically, we aggregate the number of requests received hourly to simulate the total computational workload across different times of the day.
To meet this workload, we assumed that the total computing demand could be distributed across seven selected data centers located in Arizona, Iowa, Illinois, Texas, Virginia, Washington, and Wyoming (N = 7). The data center information obtained from [6I] We use the average state industrial electricity price [63], denoted pf,, to calculate the electricity cost for each data center. For %, use the values reported by (62) to conduct our experiment.
For health impact analysis, air pollutant emissions resulting from electricity consumption contribute to various adverse effects, such as increased hospitalizations, higher medication usage, more frequent emergency room visits, and additional lost school days. These impacts can be quantified in economic
16

---

Metries
OPT
FaixOPT
HITMIN
ROBD
FairOBD
10
10
10
Hitting Cost
171.30
173.20
139.75
163.63
169.46
170.06
167.80
167.47
Switching Cost
23.27
351.48
23.16
93.53
25.65
27.52
28.17
Cost
36.36
33.33
$2.68
Total Cost
230.93
562.00
343.62
298.64
317.15
237.07
246.36
248.31
Table 2: The average costs of different algorithms in the default setting (i.e. u1 2g = 3.5). Minimum costs for the online algorithms are highlighted in bold.
10, 22
1000 and
300
500
200
900
Hitlng Cost
200
Faimaaa Cost
Total Coat
600
Switching
300
100
200
OPT
FakOPT
Hullin
Roan
DMD
FaROBD
tpD
FRROPT
Hollin
RozD
bal
FatrOB
opt
PatoPy
Nitlln
ROBO
balo
Opt
FaROPT
kuttin
RozD
talp
Parosp
Figure 1: Cost distributions of different algorithms in the default setting (i.e. #1 10, U2 and Viy = 3.5)
1000
terms using epidemiological and economic research the associated health outcomes, collectively referred to as health costs. WattTime (52) divides the United States into distinct regions and provides real-time health prices (S/MWh), representing the health cost (S) per unit of energy consumption (MWh) across different regions and time periods. To determine the region in which each data center is located, we utilize the information from [6]]. We use the health damage rate to estimate the health cost of energy consumption for each data center. Specifically, we set A, = [7: p p(. where v², represents the hourly average of WattTime's 's health price. Our online algorithm's 's ability to dynamically update its dual variable and learn from the online context sequence eliminates the need for prior training on separate dataset. Therefore, algorithms. This testing dataset consists of 97 three-day (72-hour) context sequences, created by applying sliding window across one-week (168-hour) context sequence.
only build testing dataset for all baseline
To provide readers with high-level overview of the data centers' operational characteristics, Table [ summarizes several key metrics including the average electricity price and average health price observed from May 10th to May 16th, 2024, as well as the Power Usage Effectiveness (PUE) and geographic location for each facility.
In the default setting, set g = 1 map the provisioned computing resource energy consumption. The weights are #1 10 for the regularizer in hitting cost, 1000 for switching cost and u3 = 3.5 for the long-teny tengteemm fairness cost. We choose the identical maximum capacity for each data center with M, = 1 and normalize maximum workload traces according to the maximum capacity. We use p oo for the 4p norm. These values are chosen ensure that the hitting cost, switching cost, and fairness cost have comparable magnitudes. We set the initial dual variable X [3] ò A 30 for DMD and FairOBD.
The hyperparameters Aı and À for ROBD optimally selected based Theorem 4 in [18]. For DMD, we use the same set of hyperparameter as FairOBD, such as the default learning rate 77 = 10 except that DMD ignores the switching cost. Regardless of the algorithm. The total costs of all the baseline algorithms are calculated with Eqn (T)..
Our experiments are conducted on MacBook Air with an M3 chip and 16 GB of memory. The average execution time per online algorithm over 72 time slots is approximately second.
B.1.3 Baseline Algorithms
We consider the following baseline algorithms for comparison.
Optimal Fairness Offline (FairOPT): the offline optimal policy solely minimizing long- term faimesss cost.
17

---

FairOBD
Metrics
DPT
FairOPT
HITHIX
ROBD
DMD
1) 10
=
= 10
Hitring Cost
168.88
177.20
189.75
169.46
167.47
Swilching Cost
22.92
351,49
43.75
23.16
93.53
25.67
27.52
28.17
Fainesss Cost
20.33
16.67
70.06
53.93
27.08
21.35
25.52
26.34
Total Cost
212.13
545.35
273.56
242.71
290.07
216.41
220.84
221.97
Table 3: Cost comparison of different algorithms with the fairness weight Uy
1.75.
FairOBD
Metrics
DPT
FairOPT
HITHIX
RCBD
DMD
1/ 10
10-1
10
Thiting Cost
171.81
177.20
189.75
163.63
169.46
170.52
167.80
167.47
Switching Cost
23.97
351.49
43.75
23.16
93.53
25.70
27.52
28.17
Faimess Cost
70.82
66.66
280.24
223.70
108.32
82.40
102.10
105.35
Total Cost
266.60
595.35
483.75
410.49
371.31
278.62
297.41
300.99
Table 4: Cost comparison of different algorithms with the fairness weight Ug 7.
Hitting Cost Minimizer (HITMIN): the online algorithm chasing the minimizer of the hitting cost.
Regularized Online Balanced Descent (ROBD): the state-of-the-art online algorithm without accounting the long-term fairness cost.
Dual Mirror Descent (DMD): the online algorithm solely optimizing long-term fairness.
Optimal Offline (OPT): the strongest optimal offline benchmark, corresponding to (T, 0)- OPT in our analysis. No online algorithms can possibly outperform OPT.
Among these algorithms, ROBD achieves the lowest competitive ratio for smoothed online convex optimization [18]. which is an adapted version of Eqn (1) by removing the fairness cost. Besides, DMD proposed for online allocation problems without switching costs (6], [57] (39,, which updates the dual variable K, based on mirror descent techniques. We adapt DMD with reference function
x|
h(x)= =
in our experiment.
2
B.2
Results
We summarize the average costs of the online algorithms and their offline optimal benchmark under the default setting in Table[2] The proposed algorithm, FairOBD, maintains robust performance across different learning rates and consistently outperforms other online baseline algorithms (HITMIN, ROBD, and DMD) terms of total cost. Moreover, FairOBD attains the minimum fairness cost among all online baselines, demonstrating its effectiveness in minimizing the long-term fairness cost.
To illustrate the minimal achievable long-term fairness cost, we incorporate FairOPT as the offline fairness-opting optimal baseline, considering access to the complete context sequence. Due to the inherent trade-off between operational cost and fairness cost, the locations with the lowest health impact do not necessarily align with those offering lower electricity prices. Furthermore, exclusively targeting such locations would exacerbate fluctuations in server provisioning across different regions. These two factors explain why FairOPT achieves the lowest fairness cost, despite its hitting and switching Conversely, HITMIN operates in the opposite direction, focusing exclusively minimizing hitting cost while significantly increasing the other two costs. To address this challenge, DMD resolves the tension between long-term fairness cost and instantaneous operational cost by decomposing the long-term costs and optimizing them using mirror descent techniques. This approach enables an effective balance between these two competing metrics.
costs being among the highest observed, as shown in Figure [
Without explicitly accounting for smoothness during the load balancing process, the aforementioned three methods minimize fairess and/or hitting costs by aggressively targeting locations with the lowest operational costs. These approach inevitably incur significantly higher switching cost. For instance, the average switching cost of FairOPT is still around 15 times that of the offline optimal benchmark. In extreme cases, this ratio could even higher, indicating considerable fluctuations in server provisioning-40 undesirable strategy for data centers. It highlights the critical need to explicitly incorporate switching costs into the optimization framework. ROBD strategically balances between the minimizer of the hitting cost and the previous action, achieving the lowest switching
18

---

cost while maintaining a reasonably low hitting cost. However, due to the non-separable nature of the long-tent ten-term cost, ROBD fails minimize the faimesss cost as result of its algorithm design. By decomposing the long-term cost using auxiliary variables and dynamically optimizing these variables with mirror descent techniques, FairOBD achieves the best trade-off between hitting, switchnng and fairness costs. This approach results in the lowest fairness and total costs among all the online algorithms.
To compare the impact of fairness cost, we present additional results by considering W3 = 1.75 and Us = 7 on the performance of FairOBD, summarized in Tables and respectively. Similar as in Table 2 we see that under three different learning rates FairOED is very close to OPT in terms of the total cost regardless of the hyperparameters, which demonstrates the superior performance of FairOBD. The other baselines (i.e.. FairOPT, HITMIN, ROBD, and DMD) all have substantially higher total costs. The other online baseline algorithms (ROBD and HITMIN), which do not explicitly account for long-term fairness cost, consistently exhibit poor fairness performance across different values of the fairness cost parameter U3- In contrast, FairOBD consistently maintains relatively low fairness cost while simultaneously minimizing hitting cost and ensuring action smoothness. These results demonstrate that incorporating long-term fairness cost into our algorithm design is not only effective but also robust.
In summary, FairOBD effectively balances action smoothness while maintaining low hitting cost and outperforms all other online baselines in fairness cost. These results validate the superiority of FairOBD 's explicit incorporation of long-term fairness in fostering socially responsible decision- making.
C Proof of the Lower Bounds
C.1 Proof of Theorem
Proof. In this proof, we consider hitting, switching and long-term cost as following,
T
cost(x1:T)
mu 12-- c.12 + Σ
1 T Σ Acrellp:
(11)
where the horizon length known in advance. For the hitting cost, we choose the constant value mo satisfying mo > 1. For online policy, the context c and A, are revealed sequentially, and the future context can be chosen adversarially based on the actions from the online optimal policy. The offline policy has the complete information about the context.
Now we construct two selections for the online context sequence
Gr = 11 I,.,,...
0, 0,
T/2
T/2
Option 1: Airr 1, 1.0,0, 1.O.O.....
(12)
T/2
G.. = |.I,,...11
Option
(13)
Ai.r
[1, 11,,,...11
T/2
T/2
Let ~|. denote the action sequence generated by the online algorithm. For the first half of the horizon, t E [1, 7/2,, the two context sequences (ci.r, Airr) and (ci Airr) are identical. The decision of which context sequence to choose made at time T/2 + 1. Before revealing the context at this time, we examine the historical actions =/ir/2 of the expert policy.
For the online algorithm, we define the sum of action sequence as
7/2
Σ
T
(st + <(T))
(14)
19

---

where St is constant value and c(T) is a vanishing term satisfying limy- c(T) = 0. We consider
two cases about St.
Case 1: |
2mp-1 mo
In this case, we choose the second context trace (ci:T, Air)). And the offline optimal action sequence can be obtained as
zi.r G.T
(15)
And the total cost is calculated as
(ost( 0
A& =
(16)
In this case, for any action sequence 2/ 1//221111 chosen by the online algorithm, the cost of the expert algorithm is lower bounded by
T a1l1 +
(ost(1)11))
1
Σ
mo
||
11 Σ A lpp
T
2
T/2
1
mo
|
1|1
T
2
(17)
t=1
mg T
カ= x/ T/2
2T
2
T/2
st - + (()) 2
4
where the first inequality is due to the non-negativity of the hitting and long-term costs, the second inequality is based on RMS-AM inequality. Given eTT) is vanishing term, the regret is lower bounded by
cost(x1..) cost()).)) 2
mo ||st 1112
10
(
)²
1
(18)
4
4 m
16mB
Case 2: |S|| 2mp=1
mm
In this case, choose the first context trace (ci.) Air) And feasible action sequence is defined as
1700
F1.7
CiT
(19)
mo
We don't 't need to prove the optimality of this feasible action sequence, any the offline optimal cost be upper bounded by the cost this feasible action sequence, which
T
mg 1| - ca11 + |
cost(xi.r)
<
Agrelpp
T
2
1=1
1 mg
T
T mo -
(20)
T 2
mg
T
m1
1
mg
2mo 1
+
4mo
2mg
4mo
20

---

For the online algorithm, we have
7/2
T/2
cost(x)).r)
mg
[
c 12 + T
A
T
2
t=1
7/2
1
mg
|2|
11 + 2
1
11st <(T)]lp
T
2
mo T
L1=1 x. - T/2
T/2
1
(21)
2 |s
<(T)Ilp
2T
T/2
mo
||st - + <(T)1| +
2 11st + +
4
2
me (st 1)² + +
Then the regret of the online algorithm is lower bounded by
1 |st
2mo
cost(1lar) cost(1r 2 (S 11)a +
(22)
4mn
Based condition on S if St <
2mm-1 it's obvious that 2mo
mo
(st 1)2 211s
2mg
2
mo
(1 +
2 mg
- 1
(23)
4
4mo
4
2 mo
On the other hand, if S > 0, the minimizer of (st 1)² =11s 2ma-1 is achieved at the critical point St = monotonically increases as S > 0. So the lower bound in this case can be expressed
2
4mn
Therefore, St = 1 2 mg
is the minimizer for the bound the bound
cost(al.r) cost(ritr) 2
mg
)2 + 2 2 m
2mo
(24)
4 2 mu
4mo
16 mo
3 the lower bounded for cost gap is obtained by combining the bounds for these two Given my 2. conditions for St, which is
cost(x cost(aï:r) Z
(25)
16mro
To sum up, compared with the offline optimal action, the regret of any online algorithm is lower bounded by (2)
C.2 Proof of Theorem 4.2
Proof. In this proof, we construct the hitting, switching and long-term cost as following,
1 T T 11,-- c2 + - Σ A.rellp
cost(EITT)
Σ
(26)
t=1
where the horizon length is known in advance and mg 1. For online policy, the context c and A, are revealed sequentially, and the future context can be chosen adversarially based on the actions from the online policy. The offline policy has the complete information about the context. Our goal to derive lower bound for the competitive ratio between online and offline policies under this information asymmetry.
We construct two selections for the online context sequence
ci.r a..... 0,
0
T/2
T/2
Option 1:
(27)
Air
1. 1.
0
T/2
T T/2-1
21

---

GiT a. .,....
T
Option 2:
(28)
Ai.r = 11 1. I.......1
1.
1,,
T/2
T/2
Let a/tr denote the action sequence generated by the online algorithm. For the first half of the horizon, t E T/2], the two context sequences (ci.r, Air)) and (ci.r, Air)) are identical. The decision of which context sequence to choose made at time T/2 + 1. Before revealing the context at this time, we examine the historical actions </-r/2 of the online policy.
there exists a time E [1] such that z # a, we select (9 as the context sequence. In this scenario, the offline optimal action is consistently a, resulting in zero total cost. However, the expert's cost will non-zero, leading to an infinite competitive ratio.
Conversely, if the online action sequence is <l:r/2 (a, a, ... .]. we will choose (ci.r: Airr) as the context sequence. The best an online algorithm can do is to only optimize the action . T/241 and set all subsequent actions as zero. We define the objective for action at s/ 4///241 as
mo (1 = 2 (x)² +
T 1/20 +
(29)
In our current setting, x is scalar and the gradient of 91 (2:) is defined as
mG + 1 mar undefined
Ta I Ta
(x)
(30)
In our following proof, we will choose the constant a 2 mo T (e.g. T To preserve generality,
2
we will work with a symbolically. Given that mág > 0 and T > 2, for x < 2
Ta we can derive
upper bound of the gradient as follows, o' (x) m - < - T < -1 This implies that
Te
(a) is monotonically decreasing approaches Ta from the left. Since di (x) is continuous, 2
the minimizer cannot be located in the region
Ta
On the other hand, approaches 2/2 from the right (a -T,, the gradient (x) mgg + 1 approaches - -mg 2 < -1 < 0. Given (x) is continuous, this suggests that the minimizer of Φi (ir must lie in the region x 2 - Te for > -1, which is max
-2 To find the critical point in this region, we set g (Ir = 0
Solving for obtain the potential minimizer:
T//2+11 mo
(31)
And the minimum value of gi (x) becomes
91 (1
1
mo
(z)²
+
T
2 a
x
T
2
1
T +
a
(32)
T
2 m
2
2m
T
where the second equality due to our choice of in this case is lower bounded by
The total cost of any online algorithm
mo T
1
cost(xi/r) >
(33)
2
2mg T
22

---

Next, we aim to derive the upper bound for the offline policy with complete context sequence. As we only focus on the scale the competitive ratio's lower bound. it's not necessary explicitly solve the true offline optimal trace, which could be very messy. Instead, we choose the following action sequence to serve as a feasible action sequence "'.rr which is
0
LE [1, 11
1
t= ++
(34)
0
LE +1,
Then the total cost of the true offline optimal cost is bounded by
1 mo
T
cost(ai:r) S cost((i..)) = T 2
+ 1)a²
(35)
Here we choose T The lower bound for the cost of any online algorithm and the upper bound for the offline optimal cost is given by
cost(alirr 1
2
2m
2m
(36)
cost(xi:r) <
T
mg
2
2
+
1)
a²
+
a
mg
m7 T
2
T
The competitive ratio is lower bounded by
cost(zi.T)
T
T
CR
2nno
(37)
cost(xt..)
+
6
mag
T
T
In other words, the competitive ratio of any online algorithm is lower bounded by ??TT).
D Proof of Asymptotic Competitive Ratio for FairOBD
For the ease of presentation, we define the drift of Bregman divergence for the dual variable x at time t as
(t) V (11, 1(++) (K1,
(38)
To facilitate the proof of the asymptotic competitive ratio for FairOBD in different settings, we first present several technical lemmas.
Lemma D.1. Suppose Ke-1 the solution the following equation
1
K+41 = arg min (de, k:) + (1 Kt) RER
(39)
Then for any K E IR,, we have
(K11), di) Va(ket1, (n', de) - Va me)
1
Vn (2411
(40)
17
Proof. For simplicity, we define
e(x) (di, k) + 1 (n,
(41)
The gradient of e(s)) with respect to i is defined as
1 (Vh(s)) (h(k))
Vee(K) de + 11
(42)
Since 1e+1 the minimizer of e(H), then for any n E R must have
(K' - Ket1, do + 1
- (Vh((r-))) vh(x))) 0
(43)
23

---

We prove this by contradiction. Suppose there exist k', such that (n' - -1++1, V V.e(K)) < 0. then we construct function y(E) e(Ke+1 + 5((m' k2+1)), where & E [0, 1]. The gradient of y is
Veu(E)= = n¹' kett, de 1 Vh((ke) - vh Vi( + E(n' net1)))
(44)
1)
Then Vev(() (n' -K41,, d ( of u({) in other words, K4++1 is not the minimizer of el (tt), which is contradictory to our assumption.
< O. Therefore ç = 0 is not the minimizer
So the inequality in Eqn (43) must hold for any x E IR By organizing the inequality, we have
(ke+1, d4) S/n', d,) + (w', Vh(Ket1) - Vh((k)) - (1++1, Vh((e+1) - Vh(ne))
(45)
1 =(n', dz) (w' KK41, Vh(Ki+1) - vh(Kk))
"1
According to the definition of Bregman Divergence, we have (K' KE+1, Vh(Ks+1) Vh(kx))
=(n' - KE+1, Vh(Ks++)) (N' Ket1, Vh((sr)
-K41, Vh([s++1)) (1' (6'-Nr, -Ne, Vh(Ke)) + (16441 nie Vh(ne))
(46)
-h(W' h(((+1)) + (K' -Kt41, Vh((k++1)) - h((k)))))))))))())) +h(x') KKe, Vh(re))
h(((+1) + h(ke) + (Re+1 Kr, Vh(Ke))
= Ví (x', k++1) + Vn (Ke))))))) - (1((F+1,,K))
Then we finish the proof.
Lemma D.2. If the reference I h(.)) is I-strongly convex and Kn is the initial dual variable, then the dual variable K4 bounded by
722 LLLZ) xT
T A
VR1,,,T44 S T()
21)
(47)
21
1=1
where the constant = sup Rc.AA 1| Artzll.
Proof. According to the Line 7 of Algorithm I and Lemma
D.1
for any n² E RN we have
1 ( S (n', de) Vn (w.. Kc)
(Ke+1, de) By setting n' Ni and add (ree, di) to both sides of Equ (48 we have
(48)
1)
"
?
(Kt K1, K1) s (nt Ket1,dd;
Vn (Ke+1,
17
(49)
+ Vri Vn (1i, (5411)
Since the reference function h((a) is I-strongly convex. then
h(a) h(b) (a b)bb()) _ -|a b1l?
(50)
In other words
1 (K(41,, 2 / |116443 - kell
(51)
2
Therefore, we have
Vn (K(+11,,8 (K: - 1 de)
=(re+1 - Kt, de) + -V((5et1, kit)
1
2 || kelllldell
| 12
(52)
2n
2 21
||1841 - kell2
27
|d
11
+
1
|| - Fell
21
2m
!7
11d >
17 Zz
21
21
24

---

The first inequality holds by the definition of inner product and the l-strongly convexity assumption of reference function h(-), the second inequality is derived with the AM-GM inequality, and the last inequality is obtained with the assumption ||del s Z. According to the definition of A(!), Eqn (49) becomes
A())
" 7:2 (11, 2t A
(Rt, 2t A.TA) +
S
(53)
21
According to Line 4 and Line 5 of algorithm
I then for any 2 E Xr and 24 E Z, we have
X2
f((2)) + \1d(2z, 11-1 +
- - 22 + g (2)) + k (Arte 21)
2
(54)
A2
Sf((a)) + Xid(2/ x1-1) +
|| - v1l1? + g((z) + kT (Art) z
2
All) - -ko (Arae - -zi) to both sides of the inequality, we have
By adding
7f
(tt) + [e(x)) + XId( 1)) +
A2
2 || - vz
2
(t) Ni (Ari'e - 21) + f((a)) + X1d(z1e. xx- 1) +
A2 || vell + g(4/) + tne (Apt' - 241
2
11 z² Ki (Artr - -2)) f((z)) \id(
d2 || vel12 + g( + + (Arx) -41)
21
(55)
Now we choose x/. = It and 2 = Art/, then we have
xoT 11 - (A 21) + =(((() g(2x) S
1
2 LZ -xT (ALiee - 2x)
(56)
7
21
By summing up the difference over the episode T, we have
- Vi(Ki,, (((())T44))
S 1/T( 7 z2 + LZ) - -1/ii
Σ A - zx)
(57)
21
D.1 Proof of Theorem 5.1
In the problem setting without switching cost, we define the optimization objective as
T Σ
G(ILT) - T
[((
1 gl
T
Σ ArT2).
(58)
Proof. Since Te, 2 is the optimal solution for Equ (5), so we have the following equation for any x/ x E 2:
fe(x2)) + Kit A S fe (xr) + lit A.a
(59)
g( Kezz S (( K
(60)
By combining the inequalities in Eqn (33) and (6 we have
(tt) + f((xx) + g(x)) < 2 z² fe(2)) ((1)) + K (Asa' z)) - NoT (Art - 2x) (61)
27
"
For the last term of Eqn have
61 since ke+1 is the minimizer of e(K)), then for any ne' E R we must
(K' K441, de + 1 (Vh(se-)) vh(n)))) 2 0
(62)
17
This condition is satisfied only if the gradient zero, which
de + (Vh(Ke+1) - -h((k)) = O.
(63)
25

---

Since the reference function is I-strongly convex, we can bound the dual update by the gradient distance in the following way
| kIll (1((((()))))) Vh(re)) 7 ?|dell
(64)
Thus, we can have the following inequality for the last term of Eqn 66 by summing it up over the frame R. which is
(Retk Ke, ACt 24xx 1
(KJ+1 -1)) mz)]|
|| 2141
j=t
(65)
1
|| - =;1) -5 (k- - 1). 172
j=t
Then within the frame of size R, we have
RR+
RR+R
R(R 1)
Σ
Re RE-
S kkR+1
Σ
(Art) 2//
n
(66)
21
Le
Then by substituting Eqn (66) to Eqn 66 and summing up over the whole episode T, we have:
(xz)) + o(2))
Σ f((x)) + +0(2))
1
1
T
T Apa
KR Σ
(1l + s(t)) Σ
+ 2
+
Σ
K(k-
(Avt's
zt)
27
t=1
k=1
(=(k-1)R+1
(67)
Now suppose oi.r is the (R, 0)-ottmmll action sequence, then within the k-th frame we manually construct 27 as
RR+R
2 =
Σ k=
A Vt
(68)
R
Based on the L-Lipschitz assumption on function g(-), we have:
T
K
&R
Σ
g
g
Σ
R
g(
Σ
Acxi)
R
k=1
Rk+1))++1
K
T
K
kR
1 T
<R
g
A
+
L
A
Σ
A
R
T t=1
k=1
1=1
k=1
t=
1k+11)++1
(69)
K
T
< Σ
R g( T
Axtt))
+ LS5
k=1
1=1
T
1
=T g
A,z;) + L8
T
Substituting it back to Eqn 667 we have
T
Σ
fe(x)) g(())
$ Σ
f((z))
1 +T g(
Σ Axxs) + Z2TR
21
(70)
Vn(Ks,ATT+))
T Σ
+ L8
A =t.
17
[=1
26

---

where the Bregman divergence (K1, Kr+1) is non-negative since the reference function is convex, which can be eliminated later. The last step is to upper bound g Σi=1 A(x:)) with 1 Ei=1 g(1)) which is
T 0
Agrz)
Σ
g(x))
T
1=1
t=1
T
STI|
1
Σ
AgT2
1
zell
T
g
1
2))
Σ g(x)
(71)
T
T
T
1=1
1=1
S1I
Σ
Act
zx
Since R4+1 is the minimizer of e(x), we have
+
(111e411-vh(M)))) O.
(72)
7
In other words
[Vh(kT+1) Vh(ai)]
|>
AAxx 21)
(73)
"
Since the reference function f(-) is I-strongly convex and 32-smooth, have
$2 B -ill
32 V VV (2((NITTT)))
(74)
")
"
"
By substituting the inequality to Equ
7I.
we have
T T
T
V 2 3zL V (V((NINTHH))
g( T
A,t.)
Σ
g(()) S
(75)
1=1
By substituting Lemmal D.2 into the inequality, we have
T A₁Z: 2)
Z 12
12LZ
2
T. g
A
Σ g(2) 32h,
T
R1
(76)
T
11
1721
According to our assumption, we have above inequality into Eqn (70), we have
(E Acts - -n)
STZ. ||x||| By substituting the
T
T
T
[e( + +T g( T
Σ
A <
Se(xz)
+ T -
Σ
AstT))
+ 2
21
1=1
1=1
1=1
Z
12LZ
2
TZ|
L8 B2Ln T
2 mm|ml)]
1
1721
(77)
By dividing both sides by T, we finish the proof.
D.2 Proof of Theorem 5.2
For the case of presentation, define the optimization objective G(I1.T, 11) as
T
X2 20 - well2
T Σ Axxi)
G(ILT, 11) = T Σ f((z)) + Aıd( +
+ g(
(78)
2
To facilitate the proof of the asymptotic competitive ratio for FairOBD when the hitting cost m-strongly convex, we first present several technical lemmas.
27

---

Lemma D.3. Suppose the switching cost is defined as as d(z,, 21-1)
81 || x111l? and the
2
action sequence {(1,, 2)) E [1, is the solution using Algorithm
then for any ælty E X.
z(t) Z, we have
T
(t)
T
T
22
f((xz) + A1d(xt, + g(2))
21
vel1
T
2
1=1
1=1
T
kR
f((z
+ (id(a1101111
+ d2 1 - 0el2 + g(+))
2
+
Σ
K(kk 1)8+1
Σ
(Art's - zi)
(k--1)+++
m + 11
A2
| - x2 Σ
T
" Z ni] 21
Σ
T
A
2t
2
(79)
Proof. Since the function fx(r) is m-strongly convex and switching cost d( ze- iis also 31 -ttrongyy convex with respect to x by definition, then we have
A2
ALT. + m. + A1,31 + A2
fe( + Aid(a Fr 1)) +
|1= rell2
+ Ks
|| xell
2
2
(80)
A2
Sf((z() + A1d(2 21-1) +
||
- 1 + Aea
Kg
2
where H, is the optimal solution for Eqn (5). Then similarly, for 2t, we have
g (c))
Ke S g((2) K2
(81)
By combining the inequalities in Eqn
(53). (80) and (8T we have
A(t) + fe(x)) + (1d(
A2
ar Uy 12 =((()) m A1 + d2 ||, x:e1
17
2
2
< 21
2² + fe(x)) + Aid(2', x1-1 +
A2
| - v2ll2 g(x))) + ki (Ara' x1) =x] (Arit zt)
2
(82)
For the last term of Eqn 82 since ki+1 is the minimizer of e(x), then for any re' R2 we must have
(K' K de (Vh(He-1) Vh(+e)) 2
(83)
17
This condition is satisfied only if the gradient is zero, which is
de + (V)((++1) Vh(ss)) = 0.
(84)
Since the reference function is I-strongly convex, we can bound the dual update by the gradient distance in the following way
|| - Kxll < (VV((())))) - vh(+s)) 7 Iddlll
(85)
Thus, we can have the following inequality for the last term of Eqn 82 by summing it up over the frame R. which is
(Retk Ke, Ac4 2(4x S
Σ
(k5+1
Alt 2/4x011
j=t
(86)
|| -2,l) =ill) 2 (k 1) nza
J=t
Then within the frame of size R, we have
RR+R R
kR+R
R(R 1) 21
Σ Fe (A,T' +
KKR+1
Σ
(Art - 2()
(87)
LEERR+1
L
Then we finish the proof by substituting Eqn (87) to Eqn T.
82 and summing up over the whole episode
28

---

Lemma D.4. Given any context sequence
E [I,T]} 21T and Tie are the action sequence of FairOBD and the (R. opptimal benchmark, respectively. Suppose the switching cost d(z,, It-1) = & a| 0z-1ll, then the optimization objective of FairOBD is bounded by
+ 11 + X2
G(LLI,ZOTT-) (((01,1000T-1)
xz
2
(88)
+ L 7 + 2 m1 + 21
+
82T.
2²
+
2
LZ
7 ([111) 17
2
T
T 12
nl
Proof. With Lemma D.2 and Lemma D.3 we are ready to prove the Lemma D.4 Now suppose ii.r is the (R, -optimal action sequence, then within the k-th frame we manually construct oj
AR+R
Σ
A
EE [RR 1 I
(89)
R
kR++
Then according to Lemma D.3
we have
(1(11,T44)
T Σ
T A2
f(( + )id((a,, + g((1)
Σ
20, vell
2
1=1
T
f((z)) + And(aj,z=11) + A2 ||ا - -0e12 + +(2()
(90)
2
m + 11.3
X2
1 xel12 + 7 122TH -xi
Σ Apai 2t
2
21
Besides, based on the L-Lipschitz assumption on function g(.), we have
51
Σ
R
g
1
Σ
Axz))
R
x=1
t=
t=
R+11
K
R
9
Arot)
+ L
Σ
A
1
Σ
A
R
T
k=1
k=1
Em 1|+1
(91)
K
1
R g
Axx;))
L8
T
-Tg
A, + L8
Substituting it back to Eqn (90), we have
X2 | v1112 + g(zi)
f((zz) Aid(z
T + da || vell2] +T g T Σ Axxz)
<
f((z;) + Xnd((; x1-1)
2
m A1
+ A2
Σ
T
||
12l12
+
1 2 + L8 (I(1I,
KT
Σ
T
A - 21
2
21
(92)
where the Bregman divergence Vn (Ki, KT+1) ) is non-negative since the reference function is convex, which can be climinated later. The last step is to upper bound g ΣT, A,x)) with # ΣT= g(x)).
29

---

which is
T g(
1
A(te)
Σ
g(x))
T
T
STL|
ArTt
1
Σ
zell
9
Σ 2
Σ
g(t))
(93)
T
[=1
1=1
T
T
<1|
A
a1
t=1
1=1
Since ke+1 is the minimizer of e(K),, we have
d +
= O.
(94)
In other words
T
T =
[Vh(#T+1) vh(K1)]
Σ
[Ax2s 21)
(95)
t=1
Since the reference function h(-) is I-strongly convex and 3m-smh,th, we have
[ Vh(xi]]
32 [T - -KIl S
32 V (
V
(96)
7
By substituting the inequality Eqn 933. have
T g((e)
v B2L V v
T g( Arx:)
(97)
By substituting Lemma D.2 into the inequality, we have
T A,x,) -g(2)) S 32L,
2 2
1 12LZ
2
T A
T g T
T
11
T
2,)
(98)
1
1721
tml
According to our assumption, we have above inequality into Eqn (92), we have
ki
EE 1== Apt, - 2))
STZ ||x1|| By substituting the
T
f((1)) + d1 x._1) 1) +
da ||,,, - -0,12
+ TT.gi o( T
Σ
AADz))
2
1=1
[x(x)) + (dd(ff, + X2
|| - vil2
+T g(
AADT))
1] 7²TR
2
21
1=1
+ k1 + L5 + 31 A2
Σ ||at - - + B2I., /
T
72
+
21.7
2
7
12
1721
(99)
By dividing both sides by T, we finish the proof.
Now we are ready to prove Theorem 5.2 as the following.
Proof. According to Lemma D.4, the switching cost right hand side in Eqn 88 actual action sequence, while the ultimate goal is to bound it with the switching cost of offline optimal action sequence. In other words, the final step to convert C( to ((x),,;; More specifically,
is evaluated on the
30

---

11
_ x 21-1 11?
2
11
T
| - xz-11 11 + |,|_1 - 28--111 2
2
1=1
(100)
1
m + X2 + X1,31
T
|| -x7-1 11-111 + m X1 + A2
T
|| x1-1/1
2
X2
2
1=1
m + 22 + 11 11
m + 11 + A2 1
Σ ||
x 11
Σ
|| 1e
2
m
A2
t=1
Substitute Eqn (T00) into Eqn 88 we have
T
T
fx(2,) + X,d(E,, xx-1) +
X2
12z - vell?
+ + T Σ 1,
T
2
t=1
f<(zt) + A1 m + X2 + A1
22
T
, -r +
|| - 12l1?
=(( T
Σ
Axaz) + +0+A
m + A/
2
Σ
X2 ){((z)) A1 (1
m + A2 + B1
) (0 x1-1) 1)
+ g(
1
A A
m
m X2
T
(101)
where
n z B2L FairOBD is bounded by
( 22 +2 + 7
11
+ 21 + 4. Then the overall cost of
[((rr) + 2()
g(
1
Σ
A
T
T
t=1
T
T
1
[a(x)) + Ai 21-))
+
1
g(
A + A1
A1
1=1
(102)
m + Xz
m + A2 A1
1 T
1
[f( +
)
+ Xi
9(
Σ
Azt))
+
A
T
mdi
m + A2
T
X
t=1
<C
1 Σ
f((zt) + a[x;;
1 + 9
Σ
Axzz)
1 + A1
A
t=1
where C max
m+da mA1
m m+
is the competitive ratio.
31

---

Reference
[57] 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 Inter- national Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 630-639. PMLR, 18-24 Jul 2021.
[58] Tom Brown, Benjamin Mann. Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, llya Sutskever, and Dario Amodei. Language models are few-shot learner. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 1877-1901. Curran Associates, Inc., 2020.
[59] Yuelin Han, Zhifeng Wu, Pengfei Li, Adam Wierman, and Shaolei Ren. The unpaid toll: Quantifying the public health impact of ai. arXiv preprint arXiv:2412.06288, 2024.
[60] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint arXiv:2001.0883
2020.
[61]
Microsoft.
Microsoft
Local Communities.
https://local.miccoofff.cc
communities/
[62] Microsoft. Microsoft Data Centers Sustainability Efficiency.
https://datacenteers
microsoft. com/ wwrosoff.ccom/uusttaateaoot http:///usaaaabllll//////cccco// 2023.
[63] U.S. Energy Information Administration (EIA). EIA OPEN DATA.
gov
opendata/ 2024.
32

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The main claims made in the abstract and introduction accurately reflect the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We include some discussion about the limitations of the work in our paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
33

---

All the assumptions are clearly listed in the main paper. A complete and correct proof attached in the appendix and ready for review.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We fully disclose all the information needed to reproduce the main experimen- tal results of the paper. Due to the page limit, the detailed information can be found in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
34

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: our empirical study, all information is based on publicly available data. We will make the data and code public upon acceptance of the paper.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.. cc/
olicy) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips.ccppblle ccc/pbblicgguiccccc wwtpc//ggieeeeeeee http:///uuiiees/deeuuuubiiis
(CodeSubiisss wwtaaabmmsssoono ssiiiissiicccy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: As don't need to train We provide all the information about the test details
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We provide the error bars for our experiment in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for
example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
35

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide sufficient information on the computer resources.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make it into the paper).
9. Code ethics
Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Question:
Answer: [Yes]
Justification: The research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: Due to the theoretical nature of our work, we do not foresee too much negative societal impacts or the need for safeguards. Our discussion mainly focuses on the positive broader impacts.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
36

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: Due to the theoretical nature of this work, it doesn't 't have such risks for data or model misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
Due to the theoretical nature of this work, the paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
37

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Due to the theoretical nature of this work, the paper does not release assets.
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Due to the theoretical nature of this work, the paper does not involve crowd- sourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Due to the theoretical nature of this work, the paper does not involve crowd- sourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
38

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if' applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMS as any important, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy hatt:p//eearrrppcc//oooeeeeeeee/ /ct/////oeeeeeccc///2/////. for what should or should not be described.
39


Reviews:
[{"review_id": "52LVE7SPxn", "reviewer": "Reviewer_ekFV", "summary": "This paper introduces FairOBD, an online algorithm designed to address the challenge of incorporating both long-term fairness and smoothness (via switching costs) in online convex optimization (OCO). The work formalizes a new problem setting that jointly penalizes hitting costs, action changes, and fairness violations over time. The approach decomposes the long-term fairness regularizer using auxiliary variables and dynamically updates dual multipliers through mirror descent. Theoretical analysis demonstrates an asymptotic competitive ratio guarantee against a constrained offline oracle, while empirical experiments on AI inference workload balancing across real data center traces show meaningful improvements in both fairness and overall cost compared to established baselines.", "questions": "Have you considered your problem in the stochastic setting where { (f_t, A_t) }_t are i.i.d.? Would it be possible to achieve sublinear regret in this case?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The paper tackles an important gap in the literature by studying online optimization with both switching (smoothness) costs and long-term fairness, providing a model relevant for a variety of impactful applications, such as energy-efficient and socially equitable resource allocation.\n\n2. The introduction of FairOBD represents a meaningful algorithmic contribution. It reformulates long-term fairness regularizer as long-term constraint, which is then addressed through the use of auxiliary variables and dual updates via mirror descent.  The theoretical analysis is also carefully done, clearly establishing the competitive ratio and explicitly accounting for the complexities introduced by switching costs and fairness costs. \n\n3. The paper validates FairOBD on a realistic setting: trace-driven experiments for AI inference load balancing across several Microsoft data centers using real-world traces. The results demonstrate that FairOBD achieves improved fairness and overall cost compared to five baselines, including the offline optimum and established algorithms.\n\nWeaknesses:\n\n\n1. The transformation from long-term fairness regularizer to long-term fairness constraints in equation (3) is interesting. However, the subsequent treatment largely follows standard techniques, combining a conventional primal-dual framework with Online Balanced Descent [10,16].\n\n2. The model assumes a convexity assumption on fairness cost and squared l2-norm switching costs. While justified by the need for theoretical tractability, this restricts applicability to a lot of problems. Although the limitations section briefly mentions that relaxing the convexity assumption or generalizing the form of switching costs is left for future work, a more concrete discussion of how the algorithm might be adapted under such cases would significantly strengthen the contribution.\n\n3. Some relevant works [Li et al., 2025, Chen et al., 2024, Ma et al., 20204] are missing and should be cited.\n\n[Li et al., 2025] Learning for Sustainable Online Scheduling with Competitive Fairness Guarantees.\n[Chen et al., 2024] Network Revenue Management with Demand Learning and Fair Resource-Consumption Balancing.\n[Ma et al., 20204] Optimal Regularized Online Allocation by Adaptive Re-Solving.", "was_revised": true, "final_justification": "Having reviewed the rebuttal, I believe the paper is suitable for acceptance at NeurIPS.", "rebuttal": "We sincerely appreciate the reviewer's thorough review and the valuable points raised. We are pleased to offer clarifications regarding our technical contributions.\n\n\n**`Technical Contribution for Long-term Regularizer`**:\nThough decoupling the long-term fairness cost into a sequence of online costs and optimizing the primal and dual variables with online mirror descent has been considered, our algorithm is significantly different from the existing works due to the switching costs. Specifically, for the cost objectives apart from the long-term fairness cost, ***existing methods (e.g. [6], [7]) require them to be temporally independent***. \nThis is a key requirement for the weak duality and the existing proof technique (e.g. [6], [7]), as the inequalities in the proof heavily rely on the optimal solution to a temporally-independent modified objective function at each time slot. \nIn contrast, our objective after the fairness cost decomposition is significantly more challenging than [6] as it does not meet the requirement due to the added switching cost. ***Our novel proof eliminates the need for such independence*** by focusing on frame-wise optimal action sequences, enabling comparison between different action sequences. Technically speaking, due to the added switching cost, our proof fundamentally differs from the general proofs in [6], which require the per-step cost to be independent of the previous actions once $\\kappa_t$ is decided. On the other hand, the proof in [16] only allows a difference in $x_{t-1}$ between the online algorithm and optimal offline solution, but cannot allow another decision variable $\\kappa_t$ in the per-step objective. Simply combining the proofs for SOCO (e.g. [10],[16]) and fairness regularization (e.g. [6], [7]) does not yield provable bounds. \n\nMoreover, we also make other technical contributions such as the hardness analysis by lower bounds on both regret and competitive ratio (***Theorem 4.1*** and ***Theorem 4.2***), which are the first in the literature to our knowledge.\n\n**`Relaxed Assumptions For Switching Cost`**: For the switching cost, though we are considering the L-2 norm for the ease of presentation, it’s technically tractable to consider a more general distance function for the switching cost, such as the Bregman Divergence. The Bregman Divergence is more general than the L-2 norm and it’s also commonly considered [10,16]. When the reference function of Bregman Divergence is the squared function, the switching cost is reduced to the L-2 norm. \nBy making some common assumptions on the reference function of Bregman Divergence (e.g. strong convexity and smoothness), our proof technique can be applied to handle this more general distance function. At the high level, our proof can still convert the action differences between our online algorithm and offline optimal policy to the upper bound of the switching costs. Though technically tractable, due to the space limit, we will explore this direction in our future works. \n\n**`Relaxed Assumptions For Fairness Cost`**: For the long-term fairness cost, depending on if we are minimizing costs or maximizing rewards, convexity or concavity is a commonly adopted assumption in existing literature (e.g. [6], [34]). The convexity for fairness cost is commonly observed in many real world applications, such as the min-max fairness consideration in cloud resource provisioning. This is intuitive because the reward or cost doesn’t increase linearly with respect to the actions. Instead, for the rewards, following the law of diminishing marginal utility, the more resource we allocate, the fewer marginal improvements will be, which directly implies concavity. Similarly, the health risks become more and more severe as the air pollution in a certain region increases. \n\nIn addition, this convexity is technically essential to our analysis and other related studies (e.g., [6]) that deal with similar long-term fairness regularizers. At a high level, we decouple the long-term fairness costs in Eq(1) to the temporally decoupled costs in Eq(3) using the auxiliary variable $z_t$. During this conversion, it is important to ensure the optimal solutions $x_{1:T}$ in Eq(3) and Eq(1) are identical. If the fairness function $g(\\cdot)$ is not convex, when we substitute the optimal solution of Eq(1) into Eq(3), there may existing some sequences of $z_{1:T}$ that further minimizes the $\\frac{1}{T} \\sum_{t=1}^T g(z_t)$. By rebalancing the fairness costs, hitting costs and switching costs, it’s very likely that the optimal solution of Eq(3) is different from Eq(1), which invalidates this essential conversion step. To ensure there is no $z_{1:T}$ sequence that can further minimize the last term in Eq(3), we need to guarantee the average of functions ($\\frac{1}{T} \\sum_{t=1}^T g(z_t)$) is always larger than the function of the average ($g(\\frac{1}{T} \\sum_{t=1}^T z_t)$), which directly implies the convexity property. \nTo sum up, convexity for the fairness cost is fundamental in our design as well as other related studies (e.g., [6]) that deal with similar fairness regularizers. \n\n**`The I.I.D Setting`**: In the stochastic setting where the context $\\{(f_t, A_t)\\}_t$ are sampled from an I.I.D distribution, it’s interesting to analyze the performance of an online algorithm. When there is only a long-term cost without the switching cost, it’s generally possible to obtain a sublinear regret. As Theorem 1 in [6] implies, by carefully choosing the learning rate, the regret can be sublinear. However, as we discussed above, their technique requires the objective functions to be temporally independent. This fundamental limitation restricts their applicability to our problem setting. On the other hand, when there is only a switching cost without long-term cost, additional assumptions or considerations are required to achieve sublinear regret. For instance, we need to consider static benchmarks, where the online algorithm can choose any action but the offline optimal can only choose a static action across the whole horizon. In addition to the static benchmark, another relaxation is constraining the total distance between the subsequent optimal actions, which is also known as the path length in [16]. To sum up, when combining the switching cost and long-term cost altogether, it’s challenging to achieve a sublinear regret even if we consider the I.I.D setting, and further assumptions are required to obtain meaningful results.\n\n**`Related works`**: We appreciate the reviewers for complementing the related works and will add them to our related works in our revision."}, {"review_id": "lHdsKUUIKM", "reviewer": "Reviewer_MB9t", "summary": "In this work, the authors model an online learning setting. A decision-maker is tasked with selecting an $N$-dimensional decision at each step. They observe a complete cost function that maps this chosen decision to a non-negative cost. Furthermore, an $M\\times N$ weighting matrix transforms the decision into an $M$-dimensional utility vector, upon which a long-term fairness objective is imposed, yielding a scalar fairness value. The decision-maker also incurs a switching cost, which captures the expense associated with changing decisions over time. The core objective is to devise a policy that guarantees a worst-case asymptotic competitive ratio compared to the offline optimum as the time horizon tends towards infinity.", "questions": "* Given that fairness objectives often inherently account for efficiency (e.g., Pareto optimality), could you clarify the system designer's intended secondary goal when combining these objectives additively?\n* The algorithmic complexity of Algorithm 1 remains unclear. Since the cost function has no specified structure beyond being continuous and non-negative, could you justify how the crucial step in Equation (5) can be solved in polynomial time? If approximations are necessary for practical efficiency, how might this impact the theoretical guarantees presented in the paper?\n* You state that mirror descent is integral to the algorithm's design. Could you please elaborate on the specific advantages or efficiency gains it provides over simpler optimization methods like standard gradient descent?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths.**\n\nThe paper is well-written, and its results are clearly presented. The authors' contributions are distinct, technically sound, and easily understood. They begin by establishing significant negative results in Theorems 4.1 and 4.2, demonstrating the impossibility of deriving meaningful guarantees for both regret and competitive ratio against an unrestricted adversary, like the one typically assumed in Online Convex Optimization (OCO). The authors then address this by relaxing their objective, introducing the concept of an $(R,\\delta)$-optimal algorithm, and deriving guarantees against this new benchmark. Their main result is presented as a competitive ratio guarantee for the proposed algorithm.\n\n**Weaknesses.**\n\n* The *significance of the results and the problem statement's motivation remain unclear*. It is not evident how an additive combination of a fairness criterion with a cost objective is meaningful. Fairness goals, such as min-max or proportional fairness (as exemplified by the authors), typically incorporate notions of efficiency, like Pareto optimality. Therefore, the system designer's secondary objective is ambiguous, especially given that efficiency is already implicitly accounted for in the fairness metric's definition. For instance, providing zero allocation to involved parties, while potentially fair, may not represent an efficient solution.\n\n* The *algorithmic complexity of Algorithm 1 is not transparent*. The cost function is defined only as continuous and non-negative over the action set, providing no inherent structure. Consequently, there is no clear justification that the crucial step in Equation (5) can be solved in polynomial time, rendering the algorithm impractical in real-world applications. If solving Equation (5) requires approximation for efficiency, this could potentially compromise the theoretical guarantees proposed by the authors.\n\n* The authors claim to use *mirror descent* as an integral part of their algorithm's design. However, the specific advantages or efficiencies that mirror descent, particularly the choice of its associated mirror map (regularizer), offers are unclear, as no apparent link to the obtained results is provided. It is not evident why standard gradient descent would not suffice.", "was_revised": true, "final_justification": "The reviewer believes that concerns 1 and 2 were not satisfactorily addressed by the authors during the discussion phase, so he is maintaining his original score.", "rebuttal": "We sincerely appreciate the reviewer’s valuable feedbacks on our paper and we are happy to address the reviewer’s concerns.\n\n**`Implication of Fairness Objectives`**: We acknowledge that, in certain scenarios, optimizing for efficiency can naturally enhance fairness, and some fairness objectives may implicitly incorporate efficiency considerations. However, this alignment does not hold universally—particularly for fairness costs evaluated over longer horizons. Solely prioritizing efficiency can inadvertently lead to inequitable outcomes over time.\nFor example, in our empirical study on fair resource provisioning for AI inference across geographically distributed data centers, the hitting and switching costs capture instantaneous system performance. While minimizing these costs motivates selecting the most cost-efficient data center at each time slot, this approach overlooks localized environmental impact, such as air pollution from electricity generation. These public health risks primarily affect nearby communities. Focusing exclusively on efficiency may potentially concentrate workloads in specific locations, thereby imposing disproportionate public health burdens. Consequently, beyond immediate efficiency metrics, it is essential to explicitly incorporate long-term fairness costs to ensure sustainable and equitable system behavior.\n\n*Beyond our application*, the need to explicitly incorporate fairness regularizers has been recognoized in other contexts such as online resource allocation [6].\n\n**`Algorithmic Complexity`**: Our Assumption 3.1 indicates that both hitting and fairness costs are convex, and the switching cost is the standard L2 norm. (See Section 3.1 for discussions on these assumptions.) This ensures that the objective in Eq(5) is convex with respect to $x_t$ and $z_t$. Furthermore, inspired by practical applications, the action sets $\\mathcal{X}$ and $\\mathcal{Z}$ for $x_t$ and $z_t$, respectively, are bounded (and convex). Consequently, while the specific complexity depends largely on the solvers, our problem at each step in Algorithm 1 is convex optimization, which can be efficiently solved by many established solvers in a polynomial time.\n\n**`The Advantage of Mirror Descent`**: Mirror Descent (MD) can be viewed as a generalized form of standard Gradient Descent (GD). At a high level, MD augments GD by introducing a carefully chosen potential, or reference, function (e.g. $h(\\cdot)$ in our paper). The algorithm maps the primal variable into a dual space via $\\nabla h$, performs a gradient step in the dual space, and then maps back to the primal space through $\\nabla h^{-1}$. When $h(x) = \\tfrac{1}{2}x^2$, the primal and dual spaces are identical, recovering the standard GD update. By selecting different reference functions, MD adapts the geometry of the optimization problem to improve efficiency. For example, using negative entropy yields the multiplicative weights update (MWU) algorithm, which is particularly well-suited for simplex constraints in probabilities. More broadly, in high-dimensional settings, an appropriate choice of $h$ can substantially accelerate convergence. Thus, while GD remains widely applicable, MD offers a more flexible framework that tailors optimization to the problem’s geometry. For this reason, we adopt the generalized MD in our analysis, which reduces to GD by using $h(x) = \\tfrac{1}{2}x^2$.\n\n**`Related works`**: We're grateful to the reviewers for highlighting relevant works; we'll be sure to include them in the related works section of our camera-ready version."}, {"review_id": "nOTJ0b84sN", "reviewer": "Reviewer_HqJt", "summary": "The paper works on a smoothed online optimization problem with a long-term horizon fairness regularizer. In the problem, the agent obtains a cost function at each time slot and a matrix. Then the agent will select an action, incurring three costs: hitting cost by the cost function, switching cost induced from changing to a different action from the last time slot, and horizon fairness cost. The problem aims to minimize the total cost. In this paper, the authors first analyze the worst-case regret and the competitive ratio of the problem, using the offline setting as a benchmark. Then the authors provide an algorithm and analyze its performance.", "questions": "In Theorem 5.1 and 5.2, the (R,\\delta)-optimal algorithm is online or offline? Or they are the same? Please clarify.", "limitations": "NA", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strength:\n\nThe paper studies an interesting and challenging problem, which is well-motivated by several real world applications.\n\nThe paper is well organized.\n \nWeakness\n\nThe lower bound and upper bound does not match. That is, the lower bound is the comparison of the optimal online algorithm and the optimal offline algorithm, while the upper bound is the comparison of the proposed algorithm and so-called (R,\\delta)-optimal algorithm. These are two different stories.\n\nThe technique is standard.", "was_revised": true, "final_justification": "The reviewer's major concern is the mismatch between the upper bound and lower bound (using different offline benchmarks). The authors also acknowledge that difference in their rebuttal and explicitly mentioned that they are not able to derive bounds using the same adapted offline benchmark. Being a theory person, I would consider this mismatch affects the quality of the paper a lot. Although the reviewer does consider the upper bound and the lower bound nicely proved, since they are compared to different benchmarks, the story of the paper is not complete. Hence, the reviewer decides to maintain the score.", "rebuttal": "We're very thankful for the reviewer's careful review and for acknowledging the technical strengths of our work. We're happy to address any concerns and offer additional insights into our motivation and technical approaches.\n\n**`$(R,\\delta)$-Optimal Algorithm`**: This provides the offline optimal action sequence for minimizing the total cost (e.g., hitting, switching, and fairness) and subject to the $(R,\\delta)$ constraint in **Line 209**. Both Theorem 5.1 and Theorem 5.2 use this benchmark but differ in the specific objectives. Theorem 5.1 highlights the impact of the long-term regularizer on our online algorithm's regret by considering a zero switching cost. We demonstrate that our algorithm achieves sublinear regret even with adversarial context sequences. Theorem 5.2 considers a more general case by incorporating both long-term and switching costs. We establish our algorithm's asymptotic competitive ratio and show its ***tightness*** by comparison to the optimally competitive algorithm when there is no fairness cost. Notably, Theorem 5.2 can also recover Theorem 5.1 by setting hyperparameters (e.g., $\\lambda_1=1, \\lambda_2=0$) appropriately when the switching cost is absent. The comparison of these theorems reveals that the asymptotic competitive ratio $C$ primarily stems from the switching cost, which is inevitable even without the long-term fairness cost (as indicated by Theorem 1 in [16]).\n\n**`Lower Bound vs Upper Bound`**: For regret analysis in online algorithms, selecting an appropriate benchmark is crucial, as it defines the strength of the offline optimal comparator. A common choice is the *static benchmark*, where the offline policy must commit to a single action throughout the entire horizon. This constraint enables meaningful theoretical results, such as sublinear regret bounds in online convex optimization (OCO).\n\nIn our setting, we initially considered a stronger benchmark in which the offline policy is unconstrained and may choose arbitrary actions over time. However, we found this infeasible: without knowledge of future contexts, an offline adversary could force any online algorithm to incur unbounded regret. This ***impossibility*** is formally shown through our hardness analysis in Theorems 4.1 and 4.2, where we prove that the total regret and competitive ratio of any online algorithm grow linearly (or become infinite) as $T \\to \\infty$.\n\nThe impossibility and hardness analysis (with respect to the unconstrained offline policy) motivates our introduction of the $(R,\\delta)$-constrained offline algorithm, which adds some restrictions to the offline policy benchmark. With this new constrained offline benchmark, we derive upper bounds (**Theorem 5.1** and **Theorem 5.2**) for our algorithm under adversarial contexts. Therefore, the upper bounds and lower bounds consider different benchmarks and cannot be directly compared: the upper bounds in Theorem 5.1 and Theorem 5.2 consider $(R,\\delta)$-constrained offline algorithm, whereas the lower bounds in Theorem 4.1 and Theorem 4.2 consider the unconstrained offline policy benchmark. Determining whether matching lower bounds exist for the $(R,\\delta)$ benchmark is an open problem and a promising avenue for future research.\n \n\n**`Technical Contributions`**: \nOur work offers four key technical contributions.\n\n**First**, our ***hardness analysis*** of the long-term regularizer provides crucial lower bounds for the unconstrained offline optimal benchmark. As demonstrated in Theorems 4.1 and 4.2, we prove that any online algorithm's total regret and competitive ratio will grow linearly (or become infinite) as $T \\to \\infty$. While some related works (e.g., [6]) consider no swithcing costs and **conjectured** that no online algorithm could achieve vanishing regret or a finite competitive ratio, our theorems are the first to ***rigorously*** prove this inherent difficulty in this setting to the best of our knowledge.\n\n**Second**, building on our lower bounds showing the problem hardness, we establish an important ***offline benchmark*** where the offline optimal algorithm is constrained by $(R,\\delta)$ constraint. Just as constraining the offline optimal action is needed for online algorithm analysis in other contexts, this constraint is essential for meaningful analysis in our problem. It is also practical, especially in applications like data center scheduling, where contextual information often exhibits natural periodicity, such as diurnal workloads.\n\n**Third**, we address the significant challenges in generalizing algorithms designed for standard smooth online convex optimization (SOCO) problems to incorporate long-term fairness costs. This difficulty arises because fairness costs couple all actions within the horizon, unlike SOCO's typical one-step dependence. Specifically, SOCO's per-step objective relies only on the previous action, whereas our per-step objective (Equation 5 in Algorithm 1 in FairOBD) depends on a variable influenced by all prior actions, highlighting the non-trivial nature of integrating fairness into SOCO.\n\n**Finally**, in the presence of switching costs, our algorithm significantly differs from existing methods dealing with long-term fairness. Existing works (e.g., [6], [7]) require the cost objectives (except the long-term cost) to be temporally independent, which is a crucial requirement for their weak duality proofs. In contrast, our objective, after fairness decomposition, is more challenging than [6] due to the switching cost. Specifically, the switching cost breaks the temporal independence, thereby voiding the direct use of existing techniques in [6]. Our novel proof eliminates the need for such independence by focusing on frame-wise optimal action sequences, enabling comparison between different action sequences. Therefore, due to the added switching cost, our proof fundamentally differs from the proofs in [6], which require the per-step cost to be independent of the previous actions once $\\kappa_t$ is decided. On the other hand, the proof in [16] for SOCO only allows a difference in $x_{t-1}$ between the online algorithm and optimal offline solution, but cannot allow another decision variable $\\kappa_t$ in the per-step objective. Simply combining the proofs for SOCO (e.g. [10],[16]) and fairness regularization (e.g. [6]) does not yield provable bounds."}, {"review_id": "CHHldqu9zB", "reviewer": "Reviewer_cu92", "summary": "The paper studies an online optimization problem, where an algorithm must make an irrevocable decision in every round\nwithout knowing future costs. The authors study an objective that is composed of three parts: the cost of the chosen action\nin each round (hitting cost), the cost of switching the action from the previous round (switching cost), and a cost that measure\nthe fairness of the solution. Importantly, the fairness regularization can only be evaluated at the end of the instance.\nThis smooth fairness regularized setting thus generalizes previously studied smoothed online optimization without fairness and fairness-regularized online optimization without switching cost (smoothness). \n\nThe authors present an online algorithm and prove regret and competitive ratio bounds, which recover the results of the previous settings.\nA crucial component of the author's approach is to decompose the fairness cost into online costs via a new regularizer and auxiliary variables, and to maintain approximate fairness through a Lagrangian‐multiplier mirror‐descent update, while balancing hitting cost, switching cost, and fairness cost in each round.", "questions": "- What can be done if the fairness cost is non-convex and Lipschitz?   \n- How should the different hyperparameters (e.g. \\lambda) be chosen for a good performance in practice?", "limitations": "All limitations have been addressed.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- Formulation and motivation of the problem\n- Asymptotically tight guarantees; good model of resource augmentation (restricted optimum)\n- The algorith is neat; it uses mirror descent with an additional auxiliary variable. \n- Empirical evaluation that confirms the theoretical findings.\n\nWeaknesses:\n- Requires strong assumptions on fairness cost: convex and Lipschitz.\n- The result is somewhat incremental (given that different subsets of the problem have been studied before)", "was_revised": true, "final_justification": "The authors sufficiently addressed my concerns. I think the paper has sufficient content and results to be accepted at NeurIPS.", "rebuttal": "We sincerely appreciate the reviewer’s valuable feedbacks on our paper and we are happy to address the reviewer’s concerns.\n\n**`Assumptions for Fairness Cost`**: For the long-term fairness cost, depending if we are minimizing costs or maximizing rewards, convexity or concavity is a commonly adopted assumption in existing literature (e.g. [6], [34]). The convexity for fairness cost is commonly observed in real world applications, such as the min-max fairness consideration in cloud resource provisioning. This is intuitive because the reward or cost doesn’t increase linearly with respect to the actions. Instead, for the rewards, as the law of diminishing marginal utility indicates, the more resource we allocate, the fewer marginal improvements will be, which directly implies concavity. Similarly, the health risks become more and more severe as the air pollution in a certain region increases.\n\nIn addition, this convexity is technically essential to our analysis and other related studies (e.g., [6]) that deal with similar long-term fairness regularizers. At a high level, we decouple the long-term fairness cost in Eq(1) to the temporally decoupled costs in Eq(3) using the auxiliary variable $z_t$. During this conversion, it is important to ensure the optimal solutions $x_{1:T}$ in Eq(3) and Eq(1) are identical. If the fairness function $g(\\cdot)$ is not convex, when we substitute the optimal solution of Eq(1) into Eq(3), there may existing some sequences of $z_{1:T}$ that further minimizes the $\\frac{1}{T} \\sum_{t=1}^T g(z_t)$. By rebalancing the fairness costs, hitting costs and switching costs, it’s likely that the optimal solution of Eq(3) is different from Eq(1), which invalidates this essential conversion step. To ensure there is no $z_{1:T}$ sequence that can further minimize the last term in Eq(3), we need to guarantee the average of functions ($\\frac{1}{T} \\sum_{t=1}^T g(z_t)$) is always larger than the function of the average ($g(\\frac{1}{T} \\sum_{t=1}^T z_t)$), which directly implies the convexity property. To sum up, convexity for the fairness cost is fundamental in our design as well as other related studies (e.g., [6]) that deal with similar fairness regularizers. \n\nThe **Lipschitz assumption** further bounds the impact of variations in the frame-wise average action across the horizon (denoted by $\\delta$) on the overall cost. It's also used to constrain the step-wise cost differences in our proofs. If fairness costs are naturally bounded over their domain, these effects remain controlled. Alternatively, enforcing a stricter benchmark constraint ($\\delta=0$) could obviate the need for Lipschitz continuity when bounding the impact of variations. In summary, while relaxing these assumptions would require alternative proof techniques and potentially different results, removing Lipschitz continuity remains technically feasible.\n\n**`Technical Contributions`:** \nFirst of all, in the presence of switching costs, our algorithm significantly differs from existing methods dealing with long-term fairness. Existing works (e.g., [6], [7]) require the cost objectives (except the long-term cost) to be temporally independent, which is a crucial requirement for their weak duality proofs. In contrast, our objective, after fairness decomposition, is more challenging than [6] due to the switching cost. Specifically, the switching cost breaks the temporal independence, thereby voiding the direct use of existing techniques in [6]. Our novel proof eliminates the need for such independence by focusing on frame-wise optimal action sequences, enabling comparison between different action sequences. Therfore, due to the added switching cost, our proof fundamentally differs from the proofs in [6], which require the per-step cost to be independent of the previous actions once $\\kappa_t$ is decided. On the other hand, the proof in [16] for SOCO only allows a difference in $x_{t-1}$ between the online algorithm and optimal offline solution, but cannot allow another decision variable $\\kappa_t$ in the per-step objective. Simply combining the proofs for SOCO (e.g. [10],[16]) and fairness regularization (e.g. [6]) does not yield provable bounds.\n\nSecondly, we address the significant challenges in generalizing algorithms designed for standard smooth online convex optimization (SOCO) problems to incorporate long-term fairness costs. This difficulty arises because ***fairness costs couple all actions within the horizon***, unlike SOCO's typical one-step dependence. Specifically, SOCO's per-step objective relies only on the previous action, whereas our per-step objective (Equation 5 in Algorithm 1 in FairOBD) depends on a variable influenced by all prior actions, highlighting the non-trivial nature of integrating fairness into SOCO.\n\nLast but not least, our ***hardness analysis*** of the long-term regularizer provides crucial lower bounds for the unconstrained offline optimal benchmark. As demonstrated in Theorems 4.1 and 4.2, we prove that any online algorithm's total regret and competitive ratio will grow linearly (or become infinite) as $T \\to \\infty$. While some related works (e.g., [6]) consider no swithcing costs and **conjectured** that no online algorithm could achieve vanishing regret or a finite competitive ratio, our theorems are the first to ***rigorously*** prove this inherent difficulty in this setting to the best of our knowledge. Then, building on our lower bounds showing the problem hardness, we establish an important offline benchmark where the offline optimal algorithm is constrained by $(R,\\delta)$ constraint. Just as constraining the offline optimal action is needed for online algorithm analysis in other contexts, this constraint is essential for meaningful analysis in our problem. It is also practical, especially in applications like data center scheduling, where contextual information often exhibits natural periodicity, such as diurnal workloads.\n\n**`The Choice of Hyperparameter`**: The hyperparameters in FairOBD, such as $(\\lambda_1, \\lambda_2)$, serve to balance the contributions of hitting cost, switching cost, and long-term fairness cost in determining each per-step action. For example, selecting a larger $\\lambda_1$ drives the solution toward maintaining proximity to the previous configuration, thereby reducing switching cost. In practice, these weights can be tuned to reflect the relative importance of the three cost components, depending on the requirements of different applications. Moreover, Theorem 5.2 offers theoretically optimal choices for $\\lambda_1$ and $\\lambda_2$, providing a principled guideline for parameter selection. The learning rate $\\eta$ requires similar consideration: it should be neither too large (leading to instability) nor too small (causing slow convergence), and our theory suggests scaling it inversely with the horizon length. Generally speaking, while our analysis provides important guidance for parameter selection, fine-tuning based on empirical observations remains important for achieving optimal performance in practice and can be of independent interest."}]

Author rebuttal:

Meta-review: This paper presents FairOBD, a novel algorithm addressing online convex optimization with both switching and long-term fairness costs, motivated by compelling applications such as fair and efficient AI resource allocation. The paper's contributions are significant, providing the first rigorous hardness results, a meaningful new constrained offline benchmark, and competitive empirical validation. Reviewers agree the problem is important and the work is technically solid, especially in extending the theoretical frontier and highlighting practical challenges in unifying fairness and efficiency. However, weak points remain: key steps leverage standard primal-dual and mirror descent techniques, and the theoretical analysis does not tightly close the gap between upper and lower bounds, instead using different offline benchmarks for each, which some reviewers consider a major limitation. Additionally, open questions persist about the necessity of combining efficiency and fairness cost objectives, and about practical tractability for non-convex settings. While not all reviewers are fully satisfied with the current form, the consensus supports a borderline accept: the work makes clear progress, despite technical incompleteness, and is likely to inspire follow-up work on tackling the identified limitations.
Decision: Accept (poster)