Robust Learning for Smoothed Online Convex Optimization with Feedback Delay
Authors: Pengfei Li
Jianyi Yang
Adam Wierman
Shaolei Ren
Venue: NeurIPS 2023 poster (2023)
Keywords: Online optimization
competitive algorithm
switching cost
TL;DR: This paper proposes a robust learning approach to smoothed online convex optimization with multi-step switching costs and feedback delay.

Abstract: We study a general form of Smoothed Online Convex Optimization, a.k.a. SOCO, including multi-step switching costs and feedback delay. We propose a novel machine learning (ML) augmented online algorithm, Robustness-Constrained Learning (RCL), which combines untrusted ML predictions with a trusted expert online algorithm via constrained projection to robustify the ML prediction. Specifically, we prove that RCL is able to guarantee $(1+\lambda)$-competitiveness against any given expert for any $\lambda>0$, while also explicitly training the ML model in a robustification-aware manner to improve the average-case performance. Importantly, RCL is the first ML-augmented algorithm with a provable robustness guarantee in the case of multi-step switching cost and feedback delay. We demonstrate the improvement of RCL in both robustness and average performance using battery management as a case study.

Robust Learning for Smoothed Online Convex Optimization with Feedback Delay
Pengfei Li University of California Riverside Riverside, CA, USA pli081 @ucr.edu
Jianyi Yang University of California Riverside Riverside, CA, USA jyang239@ @ uur.edu
Adam Wierman
Shaolei Ren University of California Riverside Riverside, CA, USA shaolei @uc..edu
California Institute of Technology Pasadena, CA, USA adamw @caltech.edu
Abstract
We study challenging form of Smoothed Online Convex Optimization, a.k.a. SOCO, including multi-step nonlinear switching costs and feedback delay. We propose a novel machine learning (MI.) augmented online algorithm, Robustness- Constrained Learning (RCL), which combines untrusted ML predictions with a trusted expert online algorithm via constrained projection robustify the ML. pre- diction. Specifically, prove that RCL is able to guarantee (1 -competiiiis against any given expert for any À > O, while also explicitly training the ML model in a robustiiiationn-ware manner to improve the average-case performance. Im- portantly, RCL is the first ML-augmented algorithm with a provable robustness guarantee in the case of multi-step switching cost and feedback delay. We demon- strate the improvement of RCL in both robustness and average performance using study.
battery management for electrifying transportation
Introduction
This paper studies Smoothed Online Convex Optimization (SOCO), a model that has seen application a wide variety settings. The goal of SOCO is to minimize the sum of per-round hitting cost and switching cost that penalizes temporal changes in actions. The added (even single-step) switching cost creates substantial algorithmic challenges, and has received more than decade attention 4
10, [1] [12] and the references therein). While there have been various competitive online algorithms, e.g., ROBD, to guarantee the worst-case performance robustness for SOCO conservativeness needed to address potentially adversarial instances. In contrast, machine learning (ML) based optimizers
(see [
3
5
6 7
8 9
13
5 2
g 13), their average performance is typically far from optimal due to the
improve the average performance by exploiting rich historical data and statistical information [14] I [2 7 15), but they sacrifice the strong robustness in terms of provable competitive bounds needed by safety-critical applications, especially when there is distributional shift 16 17). the MI. model capacity is limited, and/or inputs are adversarial [8 19
More recently, ML-angmented online algorithms have emerged as potential game changers in classic online problems such as ski rental and caching systems (20 21
22 23 24). The goal is to obtain
the best of both worlds by utilizing good ML predictions improve the average performance while ensuring bounded competitive ratios even when ML predictions are arbitrarily bad. In the context of SOCO, there has been initial progress ML-augmented algorithms in the past year [I] [4] 25). However, these studies target the simplest case SOCO where there no feedback delay and the
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

switching costs are linear. Crucially, their specific designs make it difficult, if not impossible, to apply more general and practical settings where there is hitting cost feedback delay and multi-step nonlinear memory in the switching cost. In addition, with few exceptions [12 25 a common assumption in the existing SOCO studies is that the MI. model is pre-trained as a black box without awareness of the downstream operation, which creates a mismatch between training and testing and degrades the average performance.
Even without ML predictions, addressing the hitting cost feedback delay and multi-step nonlinear memory is already challenging, as the agent must make decisions semi coni-blindly without receiving the immediate hitting cost feedback and the decision at each step can affect multiple future decisions in a complex manner due multi-step nonlinear switching costs 66, 26). Incorporating ML predictions into the decision process adds substantial challenges, requiring novel algorithmic techniques beyond those used in the simple SOCO setting with single-step memory and no feedback delay [14 7
Contributions. We propose novel ML--augmented algorithm, called ing (RCL) that, for the first time, provides both robustness guarantees and good average performance for SOCO in general settings with hitting cost feedback delay and multi-step nonlinear memory in the switching cost, The foundation of RCL is to utilize an existing online algorithm (referred as expert) as well as a novel reservation cost to hedge against future risks while closely following the ML predictions. Without having the immediate hitting cost feedback, RCL robustifies untrusted ML predictions at each step by judiciously accounting for the hitting cost uncertainties and the non-lineas impact of the current decision on future switching costs. Importantly, by design, the resulting cost of RCL is no greater than (1 + >) times the expert's 's cost for any À > 0 and any problem instance, while a larger À allows RCL to better explore the potential of good MI. predictions.
Conisttees--onsttaiineee Learn-
Our main technical results provide bounds on both the worst-case and average-case performance of RCL. In particular, we prove a novel worst-case cost bound on RCL in Theorem 441 and bound on the average-case performance in Theorem 4.2 Our cost bound is proven by utilizing a new reservation cost as the core of RCL. The form of the reservation cost allows us develop a new proof approach (potentially of independent interest) that decouples the dependency of the online action on the history and constructs new sufficient robustness constraint bound the distance between the actions and ML predictions. Importantly, this approach enables us to account for multi-step non-linear memory in the switching cost and arbitrarily delayed hitting cost feedback in SOCO, which cannot be We also provide a first-of-its-kind condition for simultaneously achieving both finite robustness and I-consistency, which has been shown to be impossible in general [1]. Finally, we evaluate the performance of RCL using case study focused on battery management in electric vehicle (EV) charging stations. Our results highlight the advantage of RCL in terms of robustness guarantees compared to pure ML-based methods, as well as the benefit of training robustification-avee
addressed by the existing algorithms [1 [4| 12 25
ML model.
In summary, our work makes significant contributions to the growing SOCO literature. First, we propose a novel ML-augmented algorithm that provides the first worst-case cost bounds in general SOCO setting with hitting cost feedback delay and multi-step non-linear switching costs. Our algorithm design and analysis (Theorem 4.1p are new and significantly differ from those used in 7
12, 25 Second, we provide a first sufficient condition under which finite robustness and 1 I-consistency are simultaneously achieved (Corollary 1....) Finally, we introduce and analyze the first algorithm that allows robustification-aww -wwae training. highlighting its advantage over the commonly-assumer robusiifiattonn-biiviss training in terms of the average cost.
simple SOCO settings [1 14
2 Related Work
SOCO has been actively studied for over a decade under a wide variety of settings 2 7 g
10 [2] For example, designed based on classic algorithmic frameworks, expert online algorithms include online gradient descent (OGD) (77, online balanced descent (OBD) [9]. regularized OBD (ROBD) [3]] [5, among many others. These algorithms are judiciously designed to have bounded competitive ratios and/or regrets, but they may not perform well on typical instances due to the conservative choices necessary to optimize the worst-case performance. Assuming the knowledge of (possibly imperfect) future inputs, algorithms include standard receding horizon control (RHC) 100 committed horizon control (CHC) 28), and receding horizon gradient descent (RHGD) 22] Nonetheless, the worst-case performance is still unbounded when the inputs have large errors.

---

By tapping into historical data, pure ML-based online optimizers, e.g., recurrent neural networks, have been studied for online problems [3 31 32 Nonetheless, even with (heuristic) techniques such as distributionally robust training and/or addition of hard training instances (e.g., adversarial samples) [7 they cannot provide formal worst-case guarantees as their expert counterparts.
By combining potentially untrusted ML predictions with robust experts, ML-augmented algorithms have emerged as a promising approach [22] 24 33 20 The existing ML-augmented algorithms for
SOCO (25
14 7 13 12 only focus on simple SOCO settings where the hitting cost is known
without delays and the switching cost is linear. Extending these algorithms 25 14 7 TS] to
the general SOCO setting requires substantially new designs and analysis. For example, [25 utilizes the simple triangle inequality for linear switching costs in the metric space to achieve robustness,
whereas this inequality does not hold given (multi-step) non- non-linear memory in terms of squared switching costs [14] even when there no feedback delay. In fact, even without considering MI. predictions, the general SOCO setting with feedback delays and multi-step non-linear switching costs presents significant challenges that need new techniques [26] beyond those for the simple SOCO setting. Thus, RCL makes novel contributions to the growing ML-augmented SOCO literature. Customizing ML to better suit the downstream operation to achieve lower cost has been considered for a few online problems (34
In RCL, however, we need implicit differentiation through time to customize ML by considering our novel algorithm designs in our general SOCO setting.
35 25]
In online learning with expert predictions [6 37 38) experts are dynamically chosen with time- varying probabilities achieve a low regret compared the best expert in hindsight. By contrast, RCL considers different problem setting with feedback delay and multi-step non-linear memory, and focuses on constrained learning by bounding the total cost below (1 + X) times of the expert's cost for any instance and any X >> 0. Finally, RCL is also broadly relevant to conservative bandits and reinforcement learning (39] Specifically, conservative exploration focuses on unknown cost functions (and, when applicable, transition models) and uses baseline policy to guide the exploration process. But, its design is fundamentally different in that it does not hedge against future uncertainties when choosing action for each step. Additionally, constrained policy optimization 40, 41 focuses on constraining the average cost, whereas RCL focuses on the worst-case cost constraint.
3 Model and Preliminaries
In a SOCO problem, an agent, a.k.a., decision maker, must select an irrevocable action 2, from an action space X' C Rn with size |.|| at each of time t = 1,...,77 T. Given the selected action, the agent incurs the sum of (i) a non-negative hitting cost f(x, yt) 2 0 parameterized by the context Ve E Y C Rmm where f(-) R Rzo- and (ii) a non-negative switching cost d(I,, Tz-p:t-1) is the 12 norm by default, and 5(.) : Rxxn_ -> Ra is (possibly non-linear) function of Tt-po-11 (It-p: ... 11. We make the following standard assumptions.
||,22 5(zx-pt-11]] where the constant 1 is added for the convenience of derivation,
Assumption 1. At each t, the hitting cost fzz, 4t) is non a₁ -nr-stoyylyy convex, and Bn- smooth in 24 E X. It is also Lipschitz continuous with respect to y1 E y.
Assumption 2. In the switching cost d(I It-pit-1) 5(11- (stt-pt-1) is L,-Lisschitz continuous in Zi-i for i = 1 ... i.e. for any xt x/_s E X, we have [0(02-p) ... Ti-ii ... 14-1) - 5(01-p: ... ".. x1-1) S 1
111=1= 8(0t-p:t-1)113 the function
The convexity of the hitting cost is standard in the literature and needed for competitive analysis, while smoothness (i.e., Lipschitz-continuous gradients) guarantees that bounded action differences also result in bounded cost differences (26). A common example of the hitting cost is f(z, Ur
||2; - 2 as motivated by object tracking applications, where yt is the online moving target 16 26 In the switching cost term, the previous p-step actions It-p:t-1 are essentially encoded by 6(xt-ptt-)
[6. Let us take drone tracking
an example. The switching cost can be written as di (( x1-1)
211z,- - + C1 + C2 | 1 222 and hence 5(2,-1) = Æz-1 - C1 - C2 |x,-1| 2 is nonlinear, where Ie is the drone's 's speed at time and the constants of C1 and C2 account for gravity and the aerodynamic drag [42]. For additional examples of switching costs in other applications,
readers further referred to (66)
For the convenience of presentation, we use y = (y),".. "..."""""" WV) E yI to denote a problem instance, while noting that the initial actions x-p+1.0 (0-p+1," 20) are also provided as an additional
3

---

input. Further, for S 4 S t2 S T, we also rewrite Σ fær, M+) + d( as cost where we suppress the context yt without ambiguity.
For online optimization, the key challenge is that the switching cost couples online actions and the hitting costs are revealed online. As in the recent literature on SOCO [26]. we assume that the agent knows the switching cost, because it is determined endogenously by the problem itself and the agent's previous actions. The agent also knows the smoothness constant Sr. although the hitting cost function itself is revealed online subject to a delay as defined below.
3.1 Feedback Delay
There may be feedback delay that prevents immediate observation of the context Y1 (which is equivalent to delayed hitting cost function) [43 () For example, in assisted drone landing, the context parameter y/ can represent the target velocity at time sent to the drone by control center, but the communications between the drone and control center can experience delays due to wireless channels and/or
packet losses due to adversarial jamming [26 42).
To model the delay, we refer to q 2 0 as the maximum feedback delay (i.e., context ye can be delayed for up to q 2 0 steps), and define g-delayed time set of arrival contexts.
Definition 1 (q-delayed time set of arrival contexts). Given the maximum feedback delay of 2 0, for each time ...... T, the q-delayed time set of arrival contexts contains the time indexes whose contexts are newly revealed to the agent at time t and is defined as DJ S {T E N | T t} ..)))
such that (T E T S 1t--t--1 9)
Naturally, given the maximum delay of q 2 O, we must have (T E |T < t (- S (D. ie., at time t, the agent must have already known the contexts y, for any T = ,t...... 4. 9.
It is worth highlighting that our definition of Dj is flexible and applies to various delay models. Specifically, the no-delay setting corresponds to q 0 and D {t}, while q T captures the case in which the agent may potentially have to choose actions without knowing any of the contexts V1. , yT throughout entire problem instance. Given the maximum delay O, the delayed contexts can be revealed to the agent various orders different from their actual time steps, i.e., the agent may receive Yt, earlier than Vt, for t t2- Also, the agent can receive batch of contexts Y1-g:- .. y/t simultancously at time f, and receive no new contexts some other time steps.
In online optimization, handling delayed cost functions, even for single step, is challenging 44 26 Adding MI. predictions into online optimization creates further algorithmic difficulties.
3.2 Performance Metrics
Our goal is to minimize the sum of the total hitting costs and switching costs over T time steps: min.....er DT fI1, Mt) + d(Ie; We formally define our two measures of interest.
Definition 2 (Competitiveness)) An algorithm ALG, is said be CR-competitiive against another baseline algorithm ALG2 if cost cost(ALG1,,) < CR cost(ALG2, v) is satisfied for any problem instance y y", where cost(ALG), and cost(ALG2, y) denote the total costs of ALG, and ALG2, respectively.
Definition 3 (Average cost). The average cost of an algorithm ALG is (ALG) Eyer, [cost(ALG, v)]. where cos((ALG, denotes the cost of ALG for problem instance y. and IP,, the exogenous probability distribution of y- (y.. E yr.
Our definition of competitiveness, against general baseline algorithm is commonly considered in the literature, c.g., 77. The two metrics measure an online algorithm's 's robustness in the worst case and expected performance in the average case, which are both important in practice.
We consider an expert (online) algorithm π which chooses 2; at time and an ML model hw which, parameterized by W, produces 2, hw (#t-p:t-1, furlT E DTT) at time t. As in the existing ML- augmented online algorithms 14], RCL chooses an actual online action x; by using the two actions ot and 7. as advice. In general, it is extremely challenging, if not impossible, to simultaneously optimize for both the average cost and the competitiveness. Here, given robustness requirement
A O, we focus minimizing the average cost while ensuring (1 + 2) ccompttitivennes against

---

the expert т. Crucially, the optimal expert for our setting is iROBD, which has the best-known competitiveness against the offline optimal OPT with complete information [26]. Thus. by using
iROBD as the expert (1 + A)-competitiveness of RCL against immediately translates into scaled competitive ratio of (1 + X) CDRROBD against OPT, where CRaROBD is iROBD's competitive
ratio against OPT.
4 RCL: The Design and Analysis
In this section, we present RCL, novel ML-augmented that combines ML predictions (i.e., online actions produced by an ML model [1 45 12 15 with robust expert online algorithm to the worst-case cost while leveraging the benefit of ML predictions for average performance.
4.1 Robustness-Constraaiin Online Algorithm
Our goal is to "robustify" ML predictions, by which we mean that we want to ensure a robustness bound on the cost of no greater than + A) times of the expert's cost, i.e., for any problem instance y, we have (31.())::)) S (1 + () where X > 0 is hyperparameter indicating the level of robustness we would like to achieve. Meanwhile, we would like to utilize the benefits of MI. predictions to improve the average performance.
Because of the potential feedback delays, RCL needs to choose an online action 2, without necessarily knowing the hitting costs of the expert's 's action zi and ML prediction é, Additionally, the action Ia affect multiple future switching costs due to multi-step non non-linear memory. Thus, it is very challenging to robustify ML predictions for the SOCO settings we consider. simple approach one might consider is to constrain 2, such that the cumulative cost up each time is always greater than (1 + A) times of the expert's cumulative cost, i.e., cost(211)) I (1 + (xT, However, even without feedback delays, such approach may not even produce feasible actions for We explain this by considering a single-step switching cost case. Suppose that satisfied a time < T', and we choose an action 2; o x different from the expert. Then, at time ++ 1, let us consider a case in which the expert algorithm has such low cost that even choosing I x7+1 will result in cost(x + f( Ut+1) + d(a xx) >> (1 X) [cost (xF f(x 3/++1) + ((=7+1.==]) This because the actual switching cost d(x;71, 24. can be significantly higher than the expert's 's switching cost d(xī+1, 27) due to It * x7. As result, at time + 1, it is possible that there exist no feasible actions that satisfy cost(21:4+1 S
some / = 1, ..... ,,..... T. cost(x1:1) S (1+ A)cost((
(1 + A)oost(22T..2) Moreover, when choosing an online action close to the ML prediction, extra caution must be exercised as the hitting costs can be revealed with delays of up to q steps.
To address these challenges, RCL introduces novel reservation costs to hedge against any possible uncertainties due to hitting cost feedback delays and multi-step non-linear memory in the switching costs. Concretely, given both the expert action 2. and MI prediction ã. at time I, choose It arg min 2 1 |az - lell2 2 by solving a constrained convex problem to project the MI. prediction H, into a robustified action set x E X2 where Ie satisfies:
Σ TEAt
(aT, U+) + Σ d(x, By -a----p--- 1))
Σ H(I, + G(ae, 2t- Tt-p:t (8 TEB,
S(1 A)
Σ ((TT, TEAL
Σ dl p: (f
in which A > is the robustness hyperparameter, A are the sets of time indexes for which the agent knows and does not know the context parame- ters up to time f, respectively. Most importantly, the two novel reservation costs H Hx (x7,,;7)) and G(I,, Zt-qut x- qz)g are defined
and
By = (1, ... Ve
9h (1+ +
1 1|,,--,71 - x711
H(I,, x7))
(2)
2 Ag
(1+ + An
)) (1 -E Lk)
p-k k
=
Lallxr- - x;11? +
Σ
L D4-
xT_,112)
2
(3)
5

---

Algorithm 1 Online Optimization with RCL
Require: À Ag E (0, A), initial actions I p expert algorithm 9, and ML model hw
I: for f =- 1...- ,T
2: Receive a set of contexts {y-IT E D
3: Get the expert's is action x² given its own history
4: Get ãn = hw ( (y-
D)
5:
Choose 24 = arg minzex, 2 r lzll subject to the constraint TT /RRobustification
where 3, is the smoothness constant of the hitting cost in Assumption 1 L is the Lipschitz constant of 6( pptt-1 in Assumption (2) and λ E (0, A) with the optimum being λn v1+
(Theorem The computational complexity for projection into T is tolerable due to convexity.
The interpretation of H x²}) and G(z, 21-q:-11 g=t- is as follows. If RCL's 's action deviates from the expert's ''s action x. time T and the hitting cost is not known yet due delayed yr. then is possible that RCL actually experiences a high but unknown hitting cost. In this case, to guarantee the worst-case robustness, we include an upper bound of the cost difference as the reservation cost such that f(x,, V-) (1 +1+1 (x." U+) I H (x+, x;;)) regardless of the delayed V- V If yr has been revealed at time t (i.e., r AA)., then we use the actual costs instead of the reservation cost. Likewise, by considering the expert's future actions
feasible backup plan in the worst case, the reservation cost Gix, 2t-p:t-1; 27 x?-p:t) upper bounds the maximum possible difference in the future switching costs (up to future p steps) due to deviating from the expert's action at time I.
With (I,,, . and G(z, -(- 27 ga)) as reservation costs in II RCL achieves robustness by ensuring that following the expert's 's actions in the future is always feasible, regardless of the delayed yt. The online algorithm is described in Algorithm [I] where both the expert and ML model have the same online information (V~lT E DJ) } at time ł and produce their own actions as advice to RCL.
4.2 Analysis
We now present main results on the cost bound of RCL, showing that RCL indeed maintain the desired (1 + X)-competitiveness against the expert π while exploiting the potential of MI. predictions.
Theorem 4.1 (Cost bound). Consider a memory length p 2 1 and the maximum feedback delay of 2 0. Given a context sequence y (y1, .yr), lel cost(ār;)) and cost(x")r) be the costs of pure ML predictions ë1. and expert actions zū.r. respectively. For any X 0, by optimally setting
Ap = /1 X 1, the cost of RCL is upper bounded by
cost(11:7) S min (1 (1++)Co(((TTT))
( (Vcos((ner)) +
Bh + a²
2 A(1))
2) )(a))))
(4)
where A(A) =(A==I-il (1 2( 2(11+-1112
(Bi+a²)) ( in which cost. = (EreDe f (.)))))))))))))
d(x;, --) is the total of revealed hitting costs and switching cost for the expert at time t, Br. is the smoothness constant of the hitting cost (Assumption [], and = 11 Li with L1
Lp
being the Lipschitz constants in the switching cost (Assumption)
Theorem 4.1 is the first worst-case cost analysis for ML-augmented algorithms in a general SOCO setting with delayed hitting costs and multi-step switching costs. Its proof is available in the appendix and outlined here. We prove the competitiveness against the expert æ based on our novel reservation cost (I,, x²7) and G( Zt-g:t-1, ..)) by induction. It is more challenging to prove the competitiveness against the ML prediction, because 2, implicitly depends actions of ML predictions and expert actions up to time t. To address this challenge, we utilize a novel technique by first removing the dependency of x, on the history. Then, we construct new sufficient robustness constraint that allows an explicit expression of another robustified action, whose distance to the ML prediction Z; is an upper bound by the distance between P; and o due to the projection of ă; into (T). Finally, due to the smoothness of the hitting cost function and the switching cost, the distance bound translates into the competitiveness of RCL against ML predictions.
all the previous
The two terms inside the min operator in Theorem 4.T show the tradeoff between achieving better competitiveness and more closely following ML predictions. To interpret this, we note that the first

---

tern inside min operator shows +1+ X) competitiveeess of RCL against the expert R while the second
term inside min operator shows RCL can also exploit the potential of good ML predictions. A smaller
À >> O means that we want to be closer to the expert for better competitiveness, while a larger À > 0
decreases the term A() = - ||
2; 3(v++>11)* cost." and hence makes RCL follow
(Bi+a2)
the ML predictions more closely.
The term (A) in 4 essentially bounds the total squared distance between the actual online action and ML predictions. Intuitively, RCL should follow the MI. predictions more aggressively when the expert does not perform well. This insight is also reflected in A()) in Theorem 4.1 Concretely, when the expert x's total revealed cost, is higher, A()) also becomes smaller, pushing RCL closer to ML. On the other hand, when the expert's ' cost is lower, RCL stays closer to the better-performing expert for guaranteed competitiveness.
When || = I is larger (i.e., greater discrepancy between the expert's action and ML prediction), it is naturally more difficult to follow both the expert and ML prediction simultancously. Thus, given a robustness requirement of À > O, we see from (AA) that a larger || 2 I| also increases the second term in the min operator in Theorem 4.1 making it more difficult for RCL to exploit the potential of ML predictions. Moreover, deviating from the expert's ' action one step can have impacts on the switching costs in future p steps. Thus, the memory length p creates some additional friction for RCL to achieve low cost bound with respect to ML predictions: the greater p, the greater a=1+ Di
Li, and hence the greater the second term in
Robustness and consistency. It remains to show the worst-case competitiveness against the offline optimal algorithm OPT, which is typically performed for two extreme cases - when ML predictions extremely bad and perfect- - which are respectively referred to robustness and consistency in the literature 20, 22) and formally defined below.
Definition 4 (Robustness and consistency). The robustness of RCL is CR((x) if RCL is CR()o)- competitive against OPT when the ML's competifiveness against OPT is arbitrarily large (denoted as CR + oo); and the consistency of RCL is C1) if RCL is Coompectteeeiiive against OPT when the MI''s competitiveness against OPT is CR=1.
Robustness indicates the worst-case performance of RCL for any possible ML predictions, whereas consistency measures the capability of RCL to retain the performance of perfect ML predictions. In general, the tradeoff between robustness and consistency is unavoidable for online algorithms 20 46 The state-of- thettherrtt expert algorithm iROBD recently proposed in [26] has the best- known competitive ratio under the assumption of identical delays for each context (i.e., Dj- = {t 4} each context is delayed by q steps). The identical-der delay model essentially ignores any other contexts y/- for E (T N [(-q q < (). Thus, it is the worst case of general q-step delay setting, whose competitive ratio is upper bounded by that of iROBD. Consequently, due to (1 + X)- competitiveness against any expert in Theorem 4. we immediately obtain finite robustness bound for RCL by considering iROBD as the expert.
Nonetheless, even for the simplest SOCO setting with feedback delay and switching cost of d(x,, =,-1) = ] ||ا x a recent study [14] has shown that it is impossible to simultaneously achieve 1-consistency and finite robustness. Consequently, in general SOCO settings, the finite robustness of RCL given any À > O means the impossibility of achieving 1-consistency by following perfect ML predictions without further assumptions.
Despite this pessimistic result due to the fundamental challenge of SOCO, we find a sufficient condition that can overcome the impossibility, which is formalized as follows.
Corollary 4.1.1 (I-consistency and finite robustness). Consider iROBD the exert whose competitive ratio against OPT is denoted as CRRROBD (26]. If the expert's switching cost always satisfies d(x;7 2x pit-1) 2 0 for any time t 1.... .T then by setting X (x2
2
/ (2 O(?) and optimally using Xo v1 + X 1, RCL achieves (1 ++X) A). CR
robustness and 1-consistency simultaneously.
Corollary 4.1.1 complements the impossibility result for SOCO 14 by providing the first condition
under which finite robustness and 1-consistency are simultaneously achievable. The intuition that if the expert has strictly positive switching cost no less than > 0 at each time, then its per-step
7

---

cost is also no less than which provides RCL with the flexibility to choose a different action than the expert's action za due the (1 + X) cost slackness in the competitiveness requirement. Therefore. by choosing sufficiently large but still finite À ( we can show that ( 0 in (4) in Theorem 4.1 which means RCL can completely follow the MI. predictions. Without this condition, is possible that the expert's is cost is zero in the first few steps, and hence RCL must follow the expert's actions at the beginning to guarantee (1 + Al-competitiveness in case the expert continues to have a zero cost in the future even though ML predictions are perfect and offline optimal, RCL cannot follow them at the beginning because of the online process and (1 + X) commetiiiiieeesss requirement.
Importantly, our sufficient condition is not unrealistic in practice. For example, in moving object- tracking applications. the condition d(=,, 2 - 2 6 0 is satisfied if the expert's action ž, keeps changing to follow the moving object over time or alternatively, we ignore the dummy time steps with no movement.
4.3 ML Model Training in RCL
We present the training details and highlight the advantage of training the ML model in a robustifictiion-aware manner to reduce the average cost.
4.3.1 Architecture, loss, and dataset
Because of the recursive nature of SOCO and the strong representation power of neural networks, we use a recurrent neural network with each base model parameterized by W E W (illustrated in Fig. in the appendix). Such architectures are also common in ML-based optimizers for other online problems [1). With historical data available, we can construct training dataset S that contains a fimite number of problem instances. The dataset can also be enlarged using data augmentation techniques (e.g.. adding adversarial samples) [16 17).
Robustifiaatoonobbiivouss The existing literature on ML-augmeened algorithms 22 commonly assumed that the ML model hw is separately trained in a robustifcattion-olivioo manner without being aware the downstream algorithm used online. Concretely, the parameter W of robusificationn-oliiioss ML model is optimized for the following loss
has
W = arg min WEW
Σ cost(Ti:T),
(5)
S
where é; hw (B.-pt-1, E D2)) is the ML prediction at time t.
Robustification-aware There is mismatch between the actual objective cost((1177 and the training objective cost (ā..r) of robustifiatioo-ollivin the ML model in a robustification aware manner by explicitly considering the robustification step in Algorithm|
MI. model. To reconcile this, we propose to train
For notational convenience, we denote the actual action Robx (āz). which emphasizes the projection of īe into the robust action set 2 Thus, the parameter W of a robustification-awaal ML model is optimized to minimize the following loss
Robx(hw)
W arg
min WEW
(Robx((1.))))
(6)
which is different from 5 that only minimizes the cost of pre-robustification ML predictions.
4.3.2 Average cost
We bound the average cost of RCL given an ML model kw.
Theorem 4.2 (Average cost). Assume that the ML model is trained over dataset S drawn from the training distribution Py, With probability at least 1- 5, 5 E (0, 1), the average cost E, (cost(x1.T) of RCL over the testing distribution y ~ Py is upper bounded by
log 3) [
cost(RCL) (RCL) < min (1 A)cost(x), costs (Rob. o Rads (Robs (W)) +
where costs (Robx((Rw)))) = |sl Es co is the empirical average cost of robustified ML predictions in S, Rads(Robx(W)) defined in Definition 5 in the appendix is the Rademacher
8

---

complexity with respect to the ML model space parameterized by W with robustification on the training dataset S, the scaling coefficient inside O for Radg(Rob, (W)) is T, -111-- L.) with {x| being the size of the action space X and 3r. Li, and p as the smoothness constant, Lipschitz constant of the nonlinear term in the switching
X [3,, + +1+
cost, and the memory length defined in Assumptions I
and and the coefficient for v
log 2
is 3
13]
with being the upper bound of the total cost for an episode.
Theorem 4.2 bounds the average cost of RCL by the minimum of two bounds. The first bound
(1 + X) Acoost æt) further highlights the guaranteed (1 + -)-oopeetiiiveness of RCL with respect to the expert's average cost (T)( The second bound includes a term costs (Robx (hw))
Es cos(( which is the empirical average cost of RCL given an ML model hw and decreases when À > 0 increases. The reason is that with a larger À O, the robust action set (T) is enlarged and RCL has more freedom to follow MI. predictions due to the less stringent competitiveness constraint. Given ML model hw, Theorem shows how the upper bound on cost. (Rob,, (hw)) varies with A. Note that hw- in (5) and hw- in (6) minimize costs (/ww) ) and cost (Robx (hw-)) )). respectively, while the post-robustication cost (i.e., cost. (Rob (hig: ))) is the actual cost of RCL. Thus, we can further reduce the average cost by using the optimal robustification-an to robustification ionesiiiiiaaiooooliviiiuu oblivious model hw..
ML model hiy.. compared
The other terms inside the second bound in 7 are related to the training dataset: the larger dataset, the smaller Rademacher complexity Rads (Rads(Roo(W))) and [og(1/88
S Note that the Rademacher complexity Rads (oolsR))))W)) of RCL is no greater than that of using the MI model alone (i.e. Rads (Rob(W)) S Rads (W), shown in the appendix). The intuition is that RCL limits the ac- tion space for robustness. Thus, Theorem 4. provides the insight that, given À > 0, robustification in RCL is more valuable in terms of bounding the average cost when the ML model hw is not well trained (e.g., due to inadequate training data). In practice, the hyperparameter À > 0 can be set to improve the empirical average performance subject to the robustness constraint based on a held-out validation dataset along with the tuning of other hyperparameters (e.g., learning rates).
4.3.3 Robustification-awaa training and experimental verification
Despite the advantage in terms of the average cost, it is non-trivial to train a robustification -aware ML model using standard back-propngttion. This is because the operator of projecting ML predictions into a robust set T is a recursive implicit layer that cannot be easily differentiated as typical neural network layers. Due to space limitations, we defer to the appendix the the differentiation of the loss function with respect to ML model weights W.
We validate the theoretical analysis by exploring the empirical performance of RCL using a case study of battery management electric vehicle (EV) charging stations [47). Our results are presented in the appendix. The results highlight the advantage of RCL in terms of robustness compared to pure MIL models, as well as the benefit of using a robustification-awe MI. model terms of the average cost.
5 Experiments
We now explore the performance of RCL using a case study focused on battery management in electric vehicle (EV) charging stations [48]. We first formulate the problem as an instance of SOCO. More details can be found at Appendix B. Then, we test RCL on public dataset provided by ElaadNL, compared with several baseline algorithms including ROBD (26], EC-L22 [12], and HitMin (details in Appendix B.2)). Our results highlight the advantage of RCL in terms of robustness guarantees compared to pure ML models, as well as the benefit of training robustification-aaal ML model in terms of the average cost.
5.1 Results
We now present some results for the case in which the hitting cost function (parameterized by y+) immediately known without feedback delay. The results for the case with feedback delay are presented in Appendix B.4 Throughout the discussion, the reported values are normalized with

---

A-0.6
A-1
RCT.
Aw3
A-5
A-0.6
A=1
RCT-O
A-3
Awd
ML
EC-L20
ROBD
HimtMin
AVG CR
14704
LO551
L4780
1,2022
10065
1.1277
L,00S
1.672
1.2905
1,405
1.3014
22105
2,22
24200
30322
3,2506
20014
1.7291
2,0003
Table I: Competitive ratio and average cost comparison of different algorithms.
respect to those of the respective OPT. The average cost (AVG) and competitive ratio (CR) are all empirical results reported on the testing dataset.
By Theorem 4.1 there a trade-off (governed by À > 0) between exploiting ML predictions for good average performance and following the expert for robustness. Here, we focus on the default setting of == and discuss the impact of different choices of À on both RCL and RCL-0 in Appendix [.3.2 As shown in Table [ with À 1. both RCL and RCL-0 have a good average cost, but RCL has lower average cost than RCL-0 and is outperformed only by ML in terms of the average cost. RCL and RCL-0 have the same competitive ratio (i.e., (1 + A) times the competitive ratio of ROBD). Empirically, RCL has the lowest competitive ratio among all the other algorithms, demonstrating the practical power of RCL for robustifying, potentially untrusted, ML predictions. In this experiment, RCL outperforms ROBD in terms of the empirical competitive ratio because it exploits the good ML predictions for those problem instances that are adversarial to ROBD. This result complements Theorem 4.1] where we show theoretically that RCL can outperform ROBD in terms of the average cost by properly setting A. By comparison, ML performs well on average by exploiting the historical data, but has the highest competitive ratio due to its expected lack of robustness. The two alternative baselines, EC-L220 and HitMin, are empirically good on average and also the worst case, but they do not have guaranteed robustness. On the other hand, ROBD is very robust, but its average cost is also the worst among all the algorithms under consideration.
More results, including using HitMin as the expert and large distributional shifts, are available in Appendix B.3
6 Conclusion
We have considered a general SOCO setting (including multi-step switching costs and delayed hitting costs) and proposed RCL, which ensures a worst-case performance bound by utilizing an expert algorithm to robustify untrusted ML predictions. We prove that RCL is able to guarantee (1 + >)-competitive against any given expert for any >> O. Additionally, we provide a sufficient condition that achieves finite robustness and 1-consistency simultancously. To improve the average performance, we explicitly train the ML model in a sobustification-awall aware manner by differentiating the robustification step, and provide an explicit average cost bound. Finally, we evaluate RCL using a case study of battery management for EV stations, which highlights the improvement in both robustness and average performance compared to existing algorithms.
Limitations and future work. We discuss two limitations of our work. First, we make a few assumptions (e.g., convexity and smoothness) on the hitting costs and switching costs. While they are common in the SOCO literature, these assumptions may not always hold in practice, and relaxing them will be interesting and challenging. Second, for online optimization, we only consider the MI. prediction for the current step, whereas predictions for future steps can also be available in practice and may be explored for performance improvement. There are also number of interesting open questions that follow from this work. For example, it interesting to study alternative reservation costs and the optimality in terms of the tradeoff between bi-competitiveness. Additionally, it would also be interesting to extend RCL to other related problems such as convex body chasing and metrical task systems.
Acknowledgement. We would like to thank the anonymous reviewers for their helpful comments. Pengfei Li, Jianyi Yang and Shaolei Ren were supported in part by the U.S. NSF under the grant CN1-190 Adam Wierman was supported in part by the U.S. NSF under grants CNS-2146814 CPS-2136197 CNS-2106400 NGSDI-2105648.
10

---

References
[1] Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, and Bertrand Simon. Online metric algorithms with untrusted predictions. In ICML, 2020.
[2] M. Lin, A. Wierman, L. L. Н. Andrew, and E. Thereska. Dynamic right-sizing for power- proportional data centers. In INFOCOM, 2011.
[3] Daan Rutten and Debankur Mukherjee. Capacity scaling augmented with unreliable machine learning predictions. SIGMETRICS Perform. Eval. Rev. 49(2):24 26, jan 2022.
[4] 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.
[5] 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.
[6] Guanya Shi, Yiheng Lin, Soon-Jo Chung, Yisong Yue, and Adam Wierman. Online optimization with memory and competitive control. In NeurlPS, volume 33. Curran Associates, Inc., 2020.
[7] Nicolas Christianson, Tinashe Handina, and Adam Wierman. Chasing convex bodies and functions with black-box advice. In COLT, 2022.
[8] 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.
[9] Niangjun Chen, Gautam Goel, and Adam Wierman. Smoothed online convex optimization in high dimensions via online balanced descent. In COLT, 2018.
[10] Joshua Comden, Sijie Yao, Niangjun Chen, Haipeng Xing, and Zhenhua Liu. Online optimiza- tion in cloud resource provisioning: Predictions, regrets, and algorithms. Proc. ACM Meas. Anal. Comput. Syst., 3(1), March 2019.
[11] Ming Shi, Xiaojun Lin, and Lei Jiao. Combining regularization with look-ahead for competitive online convex optimization. In INFOCOM, 2021.
[12] Pengfei Li, Jianyi Yang, and Shaolei Ren. Expert-calibrated learning for online optimization with switching costs. Proc. ACM Meas. Anal. Comput. Syst., 6(2), Jun 2022.
[13] Gautam Goel, Yiheng Lin, Haoyuan Sun, and Adam Wierman. Beyond online balanced descent: An optimal algorithm for smoothed online optimization. In NewrlPS, volume 32, 2019.
[14] 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.
[15] Nicolas Christianson, Junxuan Shen, and Adam Wierman. Optimal robustness-consistenny tradeoff's for
metrical task systems. In AI STATS, 2023.
[16] Goran Zuzic, Di Wang, Aranyak Mehta, and D. Sivakumar. Learning robust algorithms for online allocation problems using adversarial training. In hnttps:: // arziv. org/ abs/ 2010. 08418 2020.
[17] Bingqian Du, Zhiyi Huang, and Chuan Wu. Adversarial deep learning for online resource allocation. ACM Trans. Model. Perform. Eval. Comput. Syst., 6(4), feb 2022.
[18] Brandon Amos. Tutorial on amortized optimization for learning to optimize continuous domains. CoRR, abs/2202.00666 00000,,..06...22200 2022.
[19] Tianlong Chen, Xiaohan Chen, Wuyang Chen, Howard Heaton, Jialin Liu, Zhangyang Wang, and Wotao Yin. Learning to optimize: A primer and a benchmark, 2021.
[20] Jakub Chlędowski, Adam Polak, Bartosz Szabucki, and Konrad Tomasz Zoina. Robust learning- augmented caching: An experimental study. In /CML, 2021.
[21] Elbert Du, Franklyn Wang, and Michael Mitzenmacher. Putting the "learning" into learning- augmented algorithms for frequency estimation. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Pro- ceedings of Machine Learning Research, pages 2860-2869. PMLR, 18-24 Jul 2021.
[22] Alexander Wei and Fred Zhang. Optimal rohustness-consiitengg trade-offs for learning- augmented online algorithms. In NeurIPS, 2020.

---

[23] Rishi Gupta and Tim Roughgarden. Data-driven algorithm design. Commun. ACM, 63(6):87-94.
May 2020.
[24] Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Kim S. Larsen, and Jesper W. Mikkelsen. Online algorithms with advice: A survey. SIGACT News, 47(3):93-129, August 2016.
[25] Pengfei Li, Jianyi Yang, and Shaolei Ren. Robustified learning for online optimization with memory costs. In INFOCOM, 2023.
[26] 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.
[27] 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.
[28] Niangjun Chen, Joshua Comden, Zhenhua Liu, Anshul Gandhi, and Adam Wierman. Using predictions in online optimization: Looking forward with an eye on the past. SIGMETRICS Perform, Eval. Rev,, 44(1):193-200 June 2016.
[29]
Yingying Li, Guannan Qu, and Na Li. Online optimization with predictions and switching costs: Fast algorithms and the fundamental limit. IEEE Transactions on Automatic Control, 2020.
[30] Weiwei Kong, Christopher Liaw, Aranyak Mehta, and D. Sivakumar. A new dog learns old tricks: RL finds classic optimization algorithms. In ICLR, 2019.
[31] Mohammad Ali Alomrani, Reza Moravej, and Elias Boutros Khalil. Deep policies for online bipartite matching: A reinforcement learning approach. Transactions on Machine Learning Research, 2022.
[32] Binggian Du, Chuan Wu, and Zhiyi Huang. Learning resource allocation and pricing for cloud profit maximization. In Proceedings of the Thirty-Third AAAI Conference on Ar- rificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Con- ference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, AAAI' 19/AAA' 19/EAAT 19. AAAI Press, 2019.
[33] Thodoris Lykouris and Sergei Vassilvitskii. Competitive caching with machine learned advice.
J. ACM, 68(4), July 2021.
[34] Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. A regression approach to leamiig--ugmeetted online algorithms. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
[35] Pengfei Li, Jianyi Yang, and Shaolei Ren. Expert-calibrated learning for online optimization with switching costs. In SIGMETRICS, 2022.
[36] Sascha Geulen, Berthold Vöcking, and Melanie Winkler. Regret minimization for online buffering problems using the weighted majority algorithm. In COLT, pages 132-143. Citeseer, 2010.
[37] Amir Sani, Gergely Neu, and Alessandro Lazaric. Exploiting easy data in online optimization. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
[38] Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, and Samson Zhou. Memory bounds for the experts problem. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory New York, NY, USA, 2022. Association for
of Computing, STOC 2022, page Computing Machinery.
[39] Yunchang Yang, Tianhao Wa, Han Zhong, Evrard Garcelon, Matteo Pirotta, Alessandro Lazaric, Liwei Wang. and Simon Shaolei Du. A reduction beduedion-based framework for conservative bandits and reinforcement learning. In International Conference on Learning Representations, 2022.
[40] Tsung- Yen Yang. Justinian Rosca, Karthik Narasimhan, and Peter J. Ramadge. Projection-basee constrained policy optimization. In International Conference on Learning Representations, 2020.
[41] Yecheng Jason Ma, Dinesh Jayaraman, and Osbert Bastani. Conservative offline distributional reinforcement learning. In A. Beygelzimer, Y. Dauphin, Liang, and Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
12

---

[42] Guanya Shi, Xichen Shi. Michael O' O'Coneell, Rose Yu, Kamyar Azizzadenesheli, Animashree Anandkumar, Yisong Yue, and Soon-Jo Chung. Neural lander: Stable drone landing control using learned dynamics. In International Conference on Robotics and Automation (ICRA), pages 9784-9790. IEFF, 2019.
[43] Guanya Shi. Competitive control via online optimization with memory, delayed feedback, and inexact predictions. In 2021 55th Annual Conference on Information Sciences and Systems (CISS), pages 1-1. IEEE, 2021.
[44] Ohad Shamir and Liran Szlak. Online learning with local permutations and delayed feedback. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML'17, page 3086-3094. JoLR.org. 2017.
[45] Daan Rutten, Nico Christianson, Debankur Mukherjee, and Adam Wierman. Online optimiza- tion with untrusted predictions. CoRR, abs/2202.03519, 2022.
[46] Tongxin Li, Ruixiao Yang. Guannan Qu Guanya Shi, Chenkai Yu, Adam Wierman, and Steven Low. Robustness and consistency in linear quadratic control with untrusted predictions. Proc. ACM Meas. Anal. Comput. Syst. 6(1), feb 2022.
[47] W. Tang, S. Bi, and Y. Zhang. Online coordinated charging decision algorithm for electric vehicles without future information. IEEE Trans. Smart Grid, 5:2810-2882 May 2014.
13

---

A Illustration of RCL
We illustrate the online optimization process of RCL in Fig.
Modul
Medi
Sy--
Robustfcction
Robustfisttion
Robusifistion
Fy-1
honal
Tand
Expert
Expert Te (C9))
Expert
Figure I: Robustness-constrrine online optimization using RCL. The expert algorithm and ML model run independently. At each time = 1, RCL projects the ML prediction ïn into a robustified action set.
B
Case Study: Battery Management for EV Charging Stations
B.1 Problem Formulation
Batteries are routinely used in EV charging stations to handle the rapidly fluctuating charging demands and protect the connected grid. Thus, properly managing battery charging/discharging decisions crucial for reliability, lifespan, and safety of batteries and grids.
We consider the management of N batteries. At each time step suppose that He R represents the dishhariinn schedule, depending dynamics can be written as 1++1 = Ax; + Bu, Wes where the deff-derrddation of the N-battery system, B is N x N matrix which represents the charging efficiency of each battery unit, Wy is a N 1 vector which denotes the current demand terms of the charging rate (kW) of all the EVs connected to the charging stations. Assuming that the initial SoC as Zo, the goal is to control the batteries to minimize the difference between the current SoC of all batteries and nominal value E. plus baagging/dsccargingg cost to account for battery usage
State of Charge (SoC) and u, R represents the battery
on the sign of (i.e., positive means charging, and vice versa). The canonical form of the battery
a N x N matrix which models
49 50]
which can be expressed mathematically min ur Et+ ||, = 2 + bllu, 1|2.
This problem falls into SOCO based on the reduction framework described in [49]. Specifi- cally, at time step t + 1, we can expand I4+1 based the battery dynamics as I++1 A'zi
Σj=1 A Bu,- ンド= A' We define the context parameter as y E A'zz - A ' and the action as a, = Ei= Bu; Then, assuming an identity matrix B (ignoring charging loss), the optimization problem becomes minlr.... ||x - 21| + 6 |ur|| 1| + Σ ||a. yr I| blla; Aa,- Given an initial value of æ1, this problem be further simplified and reformulated as
Σ la. vill2 I|a: 1
mim
01.0g.
which is in a standard SOCO form by considering Y: as the context and ag as the action at time 4.
To validate the effectiveness of RCL, charging infrastructure company. We collect a dataset containing transaction records from ElaadNL charging stations in the Netherlands from January to June of 2019. Each transaction record contains the energy demand, transaction start time and charging time. As the data does not specify the details of battery units, consider the battery units single combine battery by summing up the energy demand within each hour to obtain the hourly energy demand.
public dataset (51) provided by ElaadNL, a Dutch EV
We use the January to February data as the training dataset, March to April data as the validation dataset for tuning the hyperparameters such as learning rate, and May to June as the testing dataset. We consider each problem instance one day (T = 24 hours, plus initial action). Thus, sliding
14

---

window of 25 is applied, moving one hour ahead each time, on the raw data to generate 1416 problem instances, where the first demand of each instance used the initial action of all the algorithms. We set b = 10 and A = T for the cost function in Eqn. (7).
the same MI. architecture, when applicable, with the same initialized weights in our experiments for fair comparison. To be consistent with the literature [52] [5], all the ML models are trained offline. Specifically, we use a recurrent neural network (RNN) model that contains 2 hidden layers, each with 8 neurons, and implement the model using PyTorch. We train the RNN for 140 epochs with a batch size of 50. When the RNN model is trained as a standalone optimizer in a ceusstiicaaiionobliviiie
All the algorithms
o manner, the training process takes around I minute on 2020 MacBook Air with 8GB memory and MI chipset. When RNN is trained robustification aware manner, takes around 2 minutes. The testing process is almost instant and takes less than 1 second.
B.2 Baseline Algorithms
By default, RCL uses robustification-tt aware ML model due to the advantage of average cost perfor- mance compared robustification-oliiy baseline algorithms as summarized below.
model. We compare RCL with several representative
Offline Optimal Oracle (OPT): This is the optimal offline algorithm that has all the contextual information and optimally solves the problem.
Regularized Online Balanced Descent (ROBD): ROBD is the state-of-the-ard order-optimal online algorithm with the best-known competitive ratio for our SOCO setting [54] (9). The parameters of ROBD are all optimally set according to 49). By default, RCL uses ROBD as its expert for robustness.
Hitting Cost Minimizer (HitMin): HitMin special instance of ROBD by setting the parameters such that it greedily minimizing the hitting cost at each time. This minimizer can be empirically effective and hence also used in ROBD as a regularizer.
Machine Learning Only (ML): ML is trained as a standalone optimizer in a robustification-oblivii manner. It does not robustification during online optimization.
Expert-Calibrated Learning (EC-L20): It an ML-augmented algorithm that applies to our SOCO setting by using ML model to regularize online actions without robustness guarantees [55]. We set its parameters based on the validation dataset to have the optimal average performance with an empirical competitive ratio less than + A)CRT.
RCL with a pobustiicatiion-olivvi use RCL to refer to RCL with a robustification-avei awaree MI. model and RCL-O for the robustification- oblivious MI model, where "-0" represents
ML model (RCL-O): To differentiate the two forms of RCL, we
To highlight our key contribution to the SOCO literature, the baseline algorithms we choose are representative of the state-of-the-arr expert algorithms, effective heuristics, and ML-augmented algorithms for the SOCO setting we consider. While there are a few other ML-augmented algorithms for SOCO [56] 57 58). they do not apply to our problem as they consider unsquared switching costs in metric space and exploit the natural triangular inequality. Adapting them to the squared switching costs is non-trivial.
B.3 Additional Empirical Results
In Section 5 we have evaluated RCL using ROBD the expert online algorithm with 1. Here we provide additional experiment results to further evaluate the effectiveness of RCL, and the results are organized follows. First, we change the expert online algorithm from ROBD HitMin to show the flexibility of RCL. Second, we quantitatively present the effect of parameter À in RCL. Third, we introduce additional out-of dfittiiibbuii samples to test the robustness of RCL and baselines, in terms setting, which is a more
of competitive ratio. Finally, we experiment under the challenging problem setup.
B.3.1 Utilizing HitMin as the expert
RCL flexible and can work with any expert online algorithm, even an expert that does not have good or bounded competitive ratios. Thus, it is interesting to see how RCL performs given alternative
15

---

ROL-
N.
1
ML
$5.20
05420
R0.0
REL 2nd
HONO
NO.0 arto
1.5
2.5
2.5 Cost Ratio
Cost Ratio
Cost Ratio
Cost Ratio
(a) ROBD as the expert
(b) HitMin as the expert (c) RCL-D w/ different
(d) RCL w/ different À
Figure 2: Cost ratio distributions (A by default).
expert. For example, in Table [ HitMin empirically outperforms ROBD in terms of the average, although it is not robust as ROBD. Thus, using À 1, we leverage HitMin as the expert for RCL and RCL-0, and show the cost ratio distributions in Fig. 2 Comparing Fig. 2b] with Fig. 2(a] see that RCL and RCL-0 both have many low cost ratios by using HitMin the expert, but the worst case for RCL is not as good as when using ROBD) as the expert. For example, the average cost and competitive ratio are 1.0515 and 1. 1.603,, respectively, for RCL. This result is not surprising, as the new expert HitMin has a better average performance but worse competitive ratio than the default expert ROBD.
B.3.2 Impact of X
Theorem 4.1 shows the point that we need to set large enough À in order to provide enough flexibility for RCL to exploit good ML predictions. With small X >> O, despite the stronger competitiveness against the expert,
possible that RCL may even empirically perform worse than both the ML model and the expert. Thus, we now investigate the impact of A.
We see from Table that the empirical average cost and competitive ratio of RCL are both worse with A 0.6 than with the default A = 1. More interestingly, by setting À = 5, the average cost of RCL is even lower than that of ML. This is because ML in our experiment performs fairly well on average. Thus, by setting large À 5, RCL is able to exploit the benefits of good ML predictions for many typical cases, while using the expert ROBD as a safeguard handle few bad problem instances for which ML cannot perform well. Also, the empirical competitive ratio of RCL is better with À = 5 than with À= = 3, supporting Theorem pe.oremm4.Tjhhe that a larger may not necessarily increase the competitive ratio as RCL can exploit good ML predictions. In addition, given each X, RCL outperforms RCL-0, which highlights the importance of training the MI model in a robustification-wwai manner to avoid the mismatch between training and testing objectives.
We also show in Fig. 2(c) an Fig. 2(d) the cost ratio distributions for RCL-O and RCL, respectively, under different A. The results reaffirm our main Theorem 4.1 as well as the importance of training the ML model in a robustification-an aware manner.
Next, we show the bi-competitive cost ratios of RCL-O against both the expert ROBD and the ML pre- dictions. We focus RCL-O its ML model is trained standalone optimizer, whereas RCL uses a robustification-awarr ML model that is not specifically trained to produce good pre-robustification predictions. According Theorem 4.1 RCL-0 obtains a potentially better competitiveness against MI. but a worse competitive against the expert ROBD when À increases, and vice versa. To further validate the theoretical analysis, we test RCL-O with different À and obtain the 2D histogram of its bi-competitive cost ratios against ROBD and ML, respectively. The results are shown in Fig. 3 In agreement with our analysis, the cost ratio of R against ROBD never exceeds (1 + A) for any > 0. Also, with a small À = 0.6, the cost ratio of RCL-O against ROBD concentrates around 1, while does not exploit the benefits of ML predictions very well. On the other hand, with a large
5, the cost ratio of RCL-O against ROBD can be quite high, although it follows (good) ML predictions more closely for better average performance. Most importantly, by increasing > 0, we can see the general trend that RCL-0 follows the MI predictions more closely while still being able to guarantee competitiveness against ROBD. Again, this confirms the key point of our main insights in Theorem 4.1
16

---

12
RCL-O ML Cont Rutio
RCL-O ML Cost Ratio
RCL- ML Cost Ruato
RCL-D Cort Retto
67
RCL-O ROED Cost Ratio
RCL-O ROED Cost Ratio
RCL-O / /ROBD Cost Ratio
RCL-D /ROOD Cost Ratio
(d) À (i.e., ML) Figure 3: Histogram of bi-competitive cost ratios of RCL-0 (against ROBD and ML) under different
(a) À 0.6
(b) À 1.0
(c) A 5.0
A. For better visualization, the color map represents logarithmic values the cost ratio histogram with base of 10.
P==0.05
P.=0LI
P==0.2
= 0,06
00.08
=0.1
00.06
00,8
=0.1
0.06
0,08
0.1
RCL.
L1331
1.1444
1,1556
1.1487
1,1693
1.1904
1.1827
1.2254
1.2697
RCL-D
T.2455
1,2436
1,2622
1,2416
12444
T2478
1,2770
1,2344
1,2499
MLL
1.0722
1,0778
L0855
1.0770
1,0874
1,1018
L,838
L,1033
1.1325
AVG
EC-L20
1.1731
ROBD
L6048
L6048
L6148
1.6488
L6049
L66399
16048
L.0488
1.0099
HitMia
12112
1,2195
1.2302
1,2202
1.2357
1,2557
1.2410
1.2724
1.3127
RCI.
2.5038
2,9697
3,2347
2,6553
3,0233
3.2711
2.5714
3.0123
3.1653
RCL-0
24209
24209
24209
2,4209
2.4209
2,4209
2.4209
2,4009
2,2099
MII.
6.5159
K3245
162627
4,4025
6.5090
9,4168
5.5798
7.3956
9.3901
CR
3.4639
4.6034
5.9006
2,6545
3,6740
5.1129
2.966
3.2713
4.6985
ROBD 1.7291
1.7291
1.7291
1.7291
1,7291
1.7291
1.7291
1.7296
1.7298
HilMia
4.8573
6.7746
83383
3.1492
4.8253
7.0005
3.0632
6.9699
8.9246
Table Average cost and competitive ratio comparison different algorithms. We study the effect
of introducing out-of- out-of-distribution (OOD) samples. Within the testing dataset, we randomly select
fraction of pe of samples and add some random noise following (00 or) to contaminate these data samples (whose input values are all normalized within [0, IJ..
B.3.3 Larger distributional shifts
In dataset, ML performs very well average as the testing distribution matches well with its training distribution. To consider more challenging cases as a stress test, we manually increase the testing distributional shifts by adding random noise following AO00, o) certain faction pe of the testing samples. Note that, as we intentionally stress test RCL and RCL-O under a larger distributional shift, their MIL models remain unchanged as in the default setting and are not re-trained by adding noisy data to the training dataset.
With the default À 1, show the average cost and competitive ratio results in Table 2 We see that ROBD is very robust and little affected by the distributional shifts. terms of the competitive ratio, ML, HitMin and EC-L20 are not robust, resulting in a large competitive ratio when we add more noisy samples. The average cost performance RCL empirically better than that of RCL-O in almost all cases, except for slight increase the practically very case where 20% samples are contaminated with large noise. On the other hand, as expected, the competitive ratios of RCL and RCL-O both increase empirically in the experiment, they both have the same guaranteed (1 + A) competitiveness against ROBD regardless of how their ML models are trained. Also, their competitive ratios are both better than other algorithms, showing the effectiveness of our novel robustification process.
add more noise. While RCL has higher competitive ratio than RCL-0
B.4 Results with Feedback Delay
We now turn the case when there one-step feedback delay, i.e., the context parameter y4 not known to the agent until time f + 1. For this setting, we consider the knotn online algorithm iROBD 449 the expert that handles the feedback delay with guaranteed competitive ratio with respect to OPT. The other baseline online algorithms ROBD, EC-L20, and HitMin- presented in Section B.2 require the immediate revelation of yr without feedback delay and hence not directly apply to this case. Thus, for comparison, we use the predicted context, denoted by it. with up to 15% prediction errors the baseline online algorithms, and reuse the algorithm names (e.g., EC-L20 uses predicted ÿt as if it were the true context for decision making). We train ML using the same
17

---

A-0.6
A=1
RCL
Aw3
Aw5
Aw0.6
A=1
5CL-0
Awa
Aw5
ML
BC-L20
IROBD
IiitMiin
ROBD
1,999
CK
19797
2
32049
398677
29097
2.4892
3.3367
4,3050
8.4000
15.1928
4,7632
26,2244
2.878
Table 3: Competitive ratio and average cost comparison of different algorithms with feedback delay.
RC5D
ROLO i 30
2-0.
RELOA- 05
Ratio
Ratio
(a) iROBD as the expert
(b) RCL w/ different À
(c) RCL-O w/ different À
Figure 4: Cost ratio distributions with feedback delay (A by default)
B.3 with the exception that only delayed context provided as input for both training and testing. The reported values are normalized with respect those of the respective offline optimal algorithm OPT. The average cost (AVG) and competitive ratio (CR) are all empirical results reported the testing dataset.
architecture as in Section
We show the results in Table and Fig. 4 We see that with the default 1, both RCL and RCL-O have good average cost. but RCL has lower average cost than RCL-O and is outperformed only by ML in terms of the average cost. RCL and RCL-O have the same competitive ratio guarantee (i.c., (1 + X) times the competitive ratio of iROBD). Nonetheless, RCL has the lowest competitive ratio than all the other algorithms, demonstrating the power of RCL to leverage both ML prediction and the robust expert. In this experiment, both RCL and RCL-O outperform iROBD in terms of the empirical competitive ratio because they are able to exploit the good ML predictions for those problem instances that are difficult for iROBD.
By comparison, ML performs well on average by exploiting the historical data, but has a high competitive ratio. The alternative baselines - ROBD, EC-L2O and HitMin- predicted context Jt as the true context. Except for the good empirical competitive ratio of ROBD, they do not have good average performance or guaranteed robustness due to their naively trusting the predicted context (that can potentially have large prediction errors). Note that the empirical competitive ratio of ROBD with predicted context still much higher than that with the true context in Table These results reinforce the point that blindly using ML predictions (i.e., predicted context in this example) without additional robustification cost ratio.
lead to poor performance in terms of both average cost and worst-case
We further show in Fig. the box plots for cost ratios of different algorithms, providing detailed view of the algorithmss' performance. The key message that RCL obtains the best of both worlds good average cost and a good competitive ratio. Moreover, enough freedom to RCL to exploit the benefits of ML predictions while also ensuring worst-case robustness. Thus, like in the no-delay case in Table and Fig. 2 the empirical competitive ratio of RCL with À = even lower than that with = 0.6.
that by setting À = 1, we provide
C Proof of Theorems and Corollaries in Section
C.1 Proof of Theorem 4.1
(Cost Ratio)
To prove Theorem 4.1 we first give some technical lemmas about the smoothness of cost functions from Lemma C.I to Lemma C3
Lemma C.1 (Lemma
(59
Assume (xx) B3. smooth, for any X > O, we have
f(x) < (1 A)f(() +1 1 2 1e v1l Yz,yES X
Lemma C.2. Assume fz) is 31 smooth and d(x) is B2 smooth. then f(z) + d(xx) is B1 + B2 smooth.
18

---

Lemma C.3. Suppose that the hitting cost fzz f Vi) where 5(-) is L L--ischhitz with respect to It-5- Then
is 31-smooth with respect to z, The switching
cost d(I1, 2 I|[ ((It-ptt-1) for any two action sequences 21T and 11.11 we must have
3 - (1 Σ Lx)² (1 -
1
cost((11:)) (1 A)cos((F1.T)) -
YA > 0 (8)
Proof. The objective to be bounded can be decomposed as cost(2111)) (1 A)cost(r(..))
T
f(m ve) -
(1 (1+ 1) v1)
+
Σ
1
8(x 8(11-pt-1)11- (1 +1+ A)llaa - 5(0%/ pot 111
2
Since hitting cost is 3n -smoothh then
T
3n (1
T
Σ f(r, v.) ()) (1+ 31) -
x Σ
|| x''1?
(10)
2
Besides, based on the Lipschitz assumption of function 5()), we have
| ((x1-p:t-1)1 (1 + A) 6(0k
<(1 )|((21 x/{) + ([ 8 pst p 1)
<(1 + z) (1|x4 - =z'1l + 110 1 1) - 8 pit 2)))
put
(II)
S(1 + } || - 2411 + Σ
La 1x|1= - 2/-
k=1
<(1 + 1 1 +
LR)
|| - ||,p-<f[""
+
La -
1=1
k=1
Summing up the switching costs of all time steps together, we have
Σ aa 5(11 ((11-p=-1)]1= (1 2)(loa 5(0/-p:tt ((11-p=t-1)1
1
p L 2/-xx12
<(1+
(1
|| - xx(l
h=1
k=1
(12)
T
<(1 +
LB)
La Lu)l x'(11
k=1
T
-(1 1
Lx)
||,
21/11
Substituting Eqn.
12 and Eqn. (10)
into Eqn.
9 we finish the proof.
Now we propose Lemma C.4 based on these above lemmas, which ensures the feasibility of robustness constraint in Eqn.
Lemma C.4. Let w be any expert algorithm for the SOCO problem with multi-step feedback delays and multi-step switching costs, for any X 2 0 and X 2 A 2 0, the total cost by the projected actions It must satisfy cost(x1:r) I + {)cost(2
Proof. We prove by induction that the constraints in Eqn. (1) are satisfied for each 1. For /. = 1, since we assume the initial actions are the same (x-p+1:0 T" -+0)) it is obvious that 2 satisfies the robustness constraints Eqn. (
19

---

Then for any time step t 2 2, suppose it holds at t that
Σ TEAL-1
U+)+
Σ
d(I 2t - +
E
((x,, + G(o, It pt----------- 1,
TEAL-1UBe-1
TEB:-1
A1)+
Σ
Σ
d(a By 0-pp-11-))1)
TEAL-1
(13)
Now the robustness constraints Eqn. 1 is satisfied if prove 2s x. satisfies the constraints in Eqn.
① at time step f. Since for the sets A and B, we have
( = {th. A S
(14)
so it holds that
Σ
d (T
Σ
d(cr, dl It- xt-p:t1)
(15)
TEA,UB,
TEAL-1UBL-1
By Lemma C.1
we have
(t-ptt-) (1 A)d(2 It 2-ppt-1l pat- 1)
1
1 (10(100-0022) -(17p-p--11) 1|
S 2 x
(16)
$ 2
1 2
Σ Li Lillati-- - xX--il
Denote = 1+ 1== Ly. For the reservation cost, we have
1::-p-1:--2::0 12-1) G(x7 Ft-p:t pct)
a(l )
p-h -
k
L 10 - 26
Latill00-1 - 20
2
pp-1 1=0
k=1 1=1
a(1 + Xo
p-k
Lu 1 1 x7-111
L || - x2/-11?
(17)
a(1 + )
p-1 p-
p-k
- 11,11
L -
2
00 1=1
km
a(1 + )
L | 11?
2
1=1
Continuing with Eqn.
17
we have
a(1 + 1
G( 21 1-p- -(xT, 21-p
L 8 - x7=111
(1+ Ay (2P) 12)
P
Li
| x11111 2
2
P
Lij
i=1
(1+ 1
bg
ME I2)²
Σ
Li
2
P
I
1 = - Ao
1
Σ
-
Li
f111z111
-
(1+ +
p
-
2
(18)
where the second inequality holds by Jensen's 's incquality. Therefore, combining with (6). we have
-t ((x,,
+Gr It sp)p S G(x+- 3t Ft-p 1a x7 (1--) a 1p
(19)
20

---

By Equ. 19 we have
G( Te- 21 +
Σ
d(I, Ty (T-P-1)
Σ
d(I,; (T-pr-1)
TEALUB
TEAL-jUBi-1
10 11 (1+
Σ
d(
Σ
dis -
TEA,UB
TEAL-1UB,-1
(20)
Now define a new set Ar Ac-1, which denotes the timestep set for the newly received context parameters at L.
Case 1: Ift Dr, then BI Di then we have
Σ f(xr, Ur) Σ H(Tr, 277)
E
f( +
Σ HIIr,
TEA:
TEB:
TEAL-1
TEBi-1
Σ f(EriBr)- -
Σ (1,,, x., = U1) +
Σ
f(1,,8r)- - Σ
H (ITr,
TED:
TEDM())
TEDM()
TED((()
(21)
Since hitting cost f(., U1) is -moothhhh, we have
Σ
f(z+
Σ (1+ ()f(2
rED+(())
TEDMM
(22)
Br +
Σ
1 - x
S Σ H(I,,
2
TED
TEDA((1)
Substituting Eqn. (22 back to Equ.
have
Σ ((Tr +
Σ >
Σ
f(r,
E
(((r)
TEB:
rEAL-1
TEB
(23)
5(1+A)
Σ
f(Ir.V))
Σ f(Irs8r)
TEA:
TEAL-1
Case 2: If & D., then (Bi-1 = Dr and we have
Σ f(x,, + Σ H(zT,
Σ
f(r,
Σ
H(xT,
TEA.
TEB,
TEAL-1
TEB
Σ
f(rri (ar)vr) Σ H(2,, + xx77
(24)
TED
TED:
Σ ((rry7)) Σ H(Tr,T)))
TED,
TED:
Since hitting cost f(.311) is -mosmohhh, have
1n(1 1)
Σ [(x, - Σ (1+)))((, <
Σ
|, - x
15 Σ
H H( x77)
2
TED
TED
TED:
TED,
(25)
Since À 2 0, we substitute Eqn.
25 back to Eqn.
24 have the same conclusion as Eqn
23
21

---

Adding Eqn. 13 Eqn. 20 and Eqn. 23 Eqn.
together, we can prove I xx satisfies the constraints in
①
At time step have
Σ (+): + Σ
I Ir p-T-
Σ
(f(r,, - (1 A)
TEAT
rEATUBT
TEBy
- Σ f(zT, Ur) +
Σ (T-
Σ
(
(26)
TEAT
TEATUBT
TEBr
+(1+A)
Σ
f(z
E
d(I d(ot,a4-p--0 -pp--pp-))))
TEAT
TEArUBT
In other words
Σ
(f(er, p)) (1+A))
Σ
(f(=),0+) + d(
rEAPUBr
TEATUBr
(27)
In the next lemma, we bound the difference between the projected action and the ML predictions. Lemma C.S. Suppose hitting cost is Bx- 3x-smooth, given the expert policy ML predictions TT for any X > 0 and X O, the total distance between actual actions EuT and ML predictions u1T are bounded,
T
T
Σ
Ze 1
Σ
xill
K
d(x) d(x),
27
pil +
Σ
f(17, Br)
(28)
TEDr
where [-] is the ReLU function and K
2(A-Ap) Ao)
= 1 1 2im1 Li
Dr. 25 to (1+
Proof. Suppose we at t - have the following inequality:
Σ [(T: +
Σ
d(I,, Ty ------pp---) +
Σ
H(T,, + G(I, It pet-ppp---a- 1, pppp))
TEAc-1
TEAt-1UB,-1
rEB.-1
+(1+A)
Σ
f(
v+)
Σ
d( x
TEAL-1
1EA--1U81-1
(29)
Remember that D, AA\,A,1 is the set of the time steps for the newly received context parameters The robustness constraint in Eqn. (1 is satisfied if x4 satisfies the following inequality.
Σ (ar.V7)) Σ 2(),, TEB.
Σ (Z)) 7EB--1
+ d(xe, Z(-p-11) G(I p1-p---1:
G(I
(1 A)
(d(T, + Σ ((77,1))
TED.
(30)
For the switching cost, have
d(0, Ft
pit- Dt-
(1+ An)d(x x.
1
(1
+
[|x - x;² + 18(xt=ptt-1) 1) 5(1;7- -6(x;-pt=11))
2
20
$5 (1 +
1 1
|| x ||
+
L fe|1a0= -xt--l
(31)
Au
1=1
a(1 + Aeo
|| -
xe 1
Li -
2
22

---

The first inequality comes from Lemma C.I the second inequality comes from the Li-Liscchizz assumption, and the third inequality because 1. Besides, from Eqn (T7) we have
a(1 + Ao
210--11-----1-----0 p-1 ----- G( Ft-pt-1,,
L
La
-
2
(32)
Thus we have
G( pa) -
1:0-2
-G p2) - G( Io- 1--t-pp-11:-- I l-pa)) + G 11- 11-
a +
Tt pa) - G(o Ir pt-
2
(33)
Combining with inequality 31 we have
G( 2t-p:t11,111111 ppt) G
p- d( Ft Dt-ptt1)))) (1 + 2o)d( +7-
a(1 + do
<G(T,, 21 21- 27 p(t)
Gz It -t--pt--tii 21 pit)
1| xz?
2
a(1 + 1
Ek= La
a(1 + Ao
Ag
100 11? 1|
100 xz 11
2
km
(1 X
| 11
2
(34)
Substituting Eqn.
34 back to Eqn. 300, we have
Σ
(f(z,) - (1 Ao) v=)) + Σ [((T, Σ
Hl (x,,
TED
TEB.
TEB.-1
(35)
a
(1 +
Ag
| < (A -
d(aT, x0 pet +
Σ
f(z7 Urr
2
TED,
Case 1: Ift E Dr, then B,- BB DeVet), then Eqn. becomes
a² + No
f(x,, - (1 + (x7 M1) +
1 x:51
2
Σ
Ao) H x.) s (A -o)
[d + Σ f(1T,
TEDAV))
TED.
(36)
Since hitting cost is -mmsohth,, the sufficient condition for Eqn. 335
becomes
(3h + a² a²) ) | . < (A -o)) (d(s (dlss "T +
(37)
TED,
Since the hitting cost neg-tega,ive the sufficient condition can be further simplified, which is (Bh + a1 + 2
| x; 12 (A Ao) (f(17, v6) + d(x; xT--p--1)
(38)
Case 2: If / & Dr, then (B. (())) = Dr, then Eqn. 35 becomes
a1 1)
2 | x7 +1
H(I,
+ Σ (f(zr, ()) (1 + 20) (x,,
TED:
(39)
$ (A- - 2o)
[d(x, x
Σ
faz Vr)
rED.
23

---

Since hitting cost is -mooooohh, the sufficient condition for Equ.
39 becomes
(3h, + (1 + )
2 1| - x (A - do) 2p
1)+ +
Σ
f(a
(40)
TED,
Now define
2(1 2o) (3n + a²) (1 + )
K
At time step t, if o is the solution to this alternative optimization problem
af = arg min 1
2 1/ #rl1?
(41)
8.l. | . 11 S K (
Σ ((77,8+))
TED.
The solution to this problem can calculated asd
2 Ox. (1 - 0)
K (d(a7 27 11-pt-1) + ETED. f(27,
(42)
100 -it-10 -x77
Then |0
2,
|| 2; v K (d(æ) 27 xT-pe-1) ΣTED, f 8+))
Since of also
satisfies the original robustness constraint, we have ||,e Trll S 1|ar Te and we finish the proof.
Proof of Theorem 4.1
Now summing up the distance through 1 to T, we have
+)
T
T
1
10t
2:11
d(x), xT
Σ
f(x7 Ur)
(43)
i=1
TED,
Based Lemma C.3
we have Via O.
3 a+ (1
1
T I
cost(21r)) (1 + )2)cost(E1:7) <
=2.12
(44)
2
A2
1=1
Suppose the offline optimal action sequence is æ/:r: the optimal cost is cost(ai.T). Then we divide both sides of Eqn. (44) by cost(zi..). and get V\2 >
8 a
1 1
cost(():)) 5(1 + >2 )2))ost(f1:r)
+
(1+
2
A2
")
(45)
| xt
K ((cl00
x
Σ f(x7,
FED.
By substituting K (8, +1+ 20)
Ao)
back to Eqn (46
we have
1
T
3
a
cost(r1:T) S(1 + A2) (ZI.T) + (1
|| - x 2:5
A
2
i=1
(46)
A No
d(x
Σ ((FF
24

---

By defining single step cost of the expert cost." = d( 27 pet pt-1) + +ETED f(2 U+) and the
auxiliary cost as ( T
|| x 2 (8xta))1+ x0
2(A-An] cOSt
/
+ a² A(A) 2
cost(21.T)
(cost(211))
(47)
Combined with Lemma C.4 we obtain the following bound, which finished this proof.
(Vcost(ELT) +
+ a² A(1))
2)
cost(x1:T) I min (1 A)cost(rTT))
(48)
2
C.2 Proof of Theorem 4.2
Proof. We first give the formal definition of Rademacher complexity of the ML model space with robustification.
Definition (Rademacher Complexity). Let Robx(W) = XRob,, (hw) W E W] be the ML model
space with robustification constrained by 2}. Given the dataset S, the Rademacher complexity with respect to Robx(W)
Rads (Robx())))W))
E,
sup
LuRoob (hw (w')((
[S]
WeW
where y is the i-th sample in S, and v1,, ... Vn are independently drawn from Rademacher distribu- tion.
Since the cost functions are smooth, they are locally Lipschitz continuous for the bounded action space, and apply the generalization bound based Rademacher complexity [60] for the space of robustified ML model Rob, (hw). Given any ML model hw trained on dataset S, with probability least 1 5, 5 E 1),
log log (2/6) |S]
BFg (oostsst1:] I costs (Roby (hw)) + 21 (raaaasssoooa (MV)) + 32,
(49)
where r2 = - +
411+E L:) with | being the size of the action space X' and 3r. Li, and p as the smoothness constant, Lipsehitz constant of the nonlinear term in the switching cost, and the memory length as defined in Assumptions aand] [ and č is the upper bound of the total cost for an episode. We can get the average cost bound Proposition 4.2
Next, we prove that the Rademacher complexity of the ML model space with robustification is no larger than the Rademacher complexity of the ML model space without robustification expressed as {hw, W E WW, L.e. we need to prove Radg (Rob, (W)) I Radg (W). The Rademacher complexity can be expressed by Dudley's entropy integral 61 as
(Robs(Ro)(W))) = (
Vlog N(e. Rob, (Mb) (2())d (2
(50)
VIS
where N(c, Rob, (W), (2)) is the covering number [61 with respect to radius c and the function distance metric || h22l2z. (12) = (s] Eies ( ) h2 (2:)) where h and h2 are two functions defined on the space including dataset S. We can find that for any two different weights W1 and W2, Rob, (lw=)ll22(s is larger than their pre-robustification distance [|fw, /ww, L2(S)) To see this, we discuss three cases given any input sample y. If both Aw, (v) and hw, (v) lie in the projection set, then Robx (hw, (v)) hws (v) and Rob, (hw, (y)
their corresponding post-rohustification distance ||Roby (hw:)
Iw; (3)) hw; (y) lies the projection set while hw, (v) out of the projection set, the projection operation based on the closed convex projection set will make ||Rob, (hw, (r) - Rob, (hw, (z))l to less than |/ (v) hws (v) If both lww, (v) and hw, (y) lic out of the projection set, still have |Rob (fww, (v) Robx (v) < [lAw; (2) kw,(v)) (v)
25

---

since the projection set at each round is a closed convex set [62]. Therefore, after robusti- fication, the distance between two models with different weights will not become larger, i.. ||obbx (Aw,) - Robx (hw; Ml S ||Aw; hw, (s), which means RCL has covering number N(e, (MW, (S)) no larger than that of the individual ML model N(e, W, L2()) for any e. Thus the Rademacher complexity with the robustification procedure does not increase.
By 66). the upper bound of Rademacher complexity with respect to the space of ML model Rads (Robx (W)) is in the order of O []]]_ Since the Rademacher complexity with the robustifica-
Visi
tion procedure satisfies Rads x (W)) I Rads (W), also decreases with the dataset size in the order of (
V Vis
D Robustifictiinn-ware Training
Theorem 4.2
aware manner. Specifically, by comparing the losses in (5) and (6), we see that using (6) as the robustification-s aware loss for training W can reduce the term costs (RŌB(hw) )) in the average cost bound, which matches exactly with the training objective in (6). The robustification-wwa
also shows the benefits of training the ML model in a robustification-avye -aware
approach is only beginning to be explored in the Ml--augmented algorithm literature and non-trivial (e.g., unconstrained downstream optimization in (55) especially considering that ( is constrained optimization problem with no explicit gradients.
Gradient-based optimizers such as Adam 66 are the de facto state-of-the-art algorithms for training ML models, offering better optimization results, convergence, and stability compared to those non- gradient- based alternatives [65]. Thus, is crucial to derive the gradients of the loss function with respect to the ML model weight W given the added robustification step.
Next, derive the gradients of x; with respect J.. For the convenience of presentation, the basic SOCO setting with a single-step switching cost and no hitting cost delay as an example, while noting that the same technique can be extended to derive gradients in more general settings. Specifically, for this setting, the pre-robustification prediction is given by .. = hw (#,-1 Ve), where W denotes the ML model weight. Then, the actual post-robustification action H, is obtained by projection in (I) by setting = 0 and p = 1. given the ML prediction T. the expert's ' action æद and cumulative cost (xI.)) up and the actual cumulative cost(r up to
The gradient of the loss function cost( = -' (f(Ee, 31) + d(x,, 11) with respect to the ML model weight W is given by Σ Vw (w(f(z;,v) ve) + d(Ir, Next, we write the gradient of per-step cost with with respect to W as follows:
Vw (f(ze, + ((12,21-1)
=v,, (f(x,, + (( VWIt + V F v.) + d(o,, VWI-1
(51)
-V., (f( vi) + d(x,, V W + Vz._, d(Fr, xt-1) V
where the gradients V.,, (J (1),, yt) ((-)) and Va, d(F,, x1) trivial given the hitting and switching cost functions, and the gradient Vw is obtained at time - in the same way as VwE, To derive V VW,, by the chain rule, we have:
Vwz, = V Vw + Veosten. 2. V Wcoos((21x-)),
(52)
where Vw Et is the gradient of the ML output (following a recurrent architecture illustrated in Fig. I in the appendix) with respect the weight W and can be obtained recursively by using off-the off-the-shelf BPTT optimizers [64], and Viycost(xr:t-1)) = Σt=1 Vw (f Ur) ) + x1x);: can also be recursively calculated once we have the gradient in Eqn. (51). Nonetheless, is non-trivial to calculate the two gradient terms Eqn. (52). i.e., Va, and V Vous(211--
where x, itself the
solution to the constrained optimization problem (1) unlike in the simpler unconstrained case (55)] As we cannot explicitly write x; in a closed form in terms of on and cost(#1:0-1). we leverage the KKT conditions [66] 67 68 to implicitly derive Va, and V Vonst(aia I) in the next proposition.
Proposition D.I (Gradients by KKT conditions). Let x E X and μ 2 0 be the primal and dual solutions to the problem I respectively. The gradients of vx with respect to Ta and cost((1:t-1) ie--1) are
V Va Ani + AI2Se(A,,An)
An'),
26

---

V contari 1)2t = Ali A12SAA, An) An)
where An1 I + (a(V. V an (zz, ye) + (1 (1+ (1+ ) + Ln) 1). A12 V.. Vz.f
(x, - 8(1x-1)) (1+ (1) + L1) (x+ -;,), A21 / D22 f yc)
d(a,,T=-1) + + - the cohrr-complement of A11 in the blocked matrix = [[A11 A12), [A21, A2a]].
and Se( A A1) = - - 22 A1 A12
If the ML prediction F. happens to lie the boundary such that the inequality in (I) becomes equality for æ = Tt, then the gradient does not exist in this case and Se( A, An) may not be full- rank. Nonetheless, to calculate the subgradient. Such approximation is actually a common practice to address non- differentiable points for training ML models, c.g., using 0 the subgradient of ReLu(-) at the zero point [64].
can still calculate the pseudo-inverse of Sc(A, A11) and use Proposition D.I
27

---

Reference
[48] W. Tang, S. Bi, and Y. Zhang. Online coordinated charging decision algorithm for electric vehicles without future information. IEEE Trans. Smarl Grid, 5:281 10-2824, May 2014.
[49] 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.
[50] Tongxin Li, Ruixiao Yang, Guannan Qu, Yiheng Lin, Steven Low, and Adam Wierman. Equipping black-box policies with model-based advice for stable nonlinear control. In https: // arziv. org/ abs/22066 01341 2022.
[51] Chris Develder, Nasrin Sadeghiannoourhammni, Matthias Strobbe, and Nazir Refa. Quantifying flexibility in ev charging as dr potential: Analysis of two real-world data sets. In 2016 IEEE International Conference on Smart Grid Communications (SmarGGidCommm) pages 600-605.
IEEE, 2016.
[52] Mohammad Ali Alomrani, Reza Moravej, and Elias B. Khalil. Deep policies for online bipartite matching: A reinforcement learning approach. CoRR, abs/2109. 100000 2021.
[53] Bingqian Du, Zhiyi Huang, and Chuan Wu. Adversarial deep learning for online resource allocation. ACM Trans. Model. Perform. Eval. Comput. Syst. 6(4), feb 2022.
[54] Gautam Goel, Yiheng Lin, Haoyuan Sun, and Adam Wierman. Beyond online balanced descent:
An optimal algorithm for smoothed online optimization. In NeurlPS, volume 32, 2019.
[55] Pengfei Li, Jianyi Yang, and Shaolei Ren. Expert-calibrated learning for online optimization with switching costs. Proc. ACM Meas. Anal. Comput. Syst. 6(2), Jun 2022.
[56] Antonios Antoniadis, Christian Coester, Marek Elias, Adam Polak, and Bertrand Simon. Online
metric algorithms with untrusted predictions. In ICML,, 2020.
[57] Nicolas Christianson, Tinashe Handina, and Adam Wierman. Chasing convex bodies and functions with black-box advice. In COLT, 2022.
[58] Daan Rutten, Nico Christianson, Debankur Mukherjee, and Adam Wierman. Online optimiza- tion with untrusted predictions. CoRR, abs/2202.03519, 2022.
[59] Guanya Shi, Yiheng Lin, Soon-Jo Chung, Yisong Yue, and Adam Wierman. Online optimization with memory and competitive control. In NeurlPS, volume 33. Curran Associates, Inc., 2020.
[60] Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities: Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463 482, 2002.
[61]
Martin Wainwright. Rademacher and empirical covering. htttss:/ppepple.i berkee
/ wwainwrig/stat2411//eeee
pdf) 2009.
[62]
Constantine Caramanis and Sujay Sanghavi. Projection onto a convex set. https:///see final. pdf
ecee www.ut..ee... www.eedmcaaaaanneeaee cmcaracc EE381V http://araa//3111112222222222222 Bttp://eeeeuueee_rreeeeeeeeee_ee 2012.
[63] Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally margin bounds for neural networks. Advances in neural information processing systems, 30, 2017.
[64] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. MIT Press, 2016.
[65] Hyung Ju Suh, Max Simchowitz, Kaiqing Zhang, and Russ Tedrake. Do differentiable simulators give better policy gradients? In Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages PMLR, 17-23 Jul 2022.
[66] S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
[67] Brandon Amos. Tutorial on amortized optimization for learning to optimize over continuous domains. CoRR, abs/2202.00665. 2022.
[68] Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and J. Zico Kolter. Differentiable convex optimization layers. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Bus Buc, E. Fox. and R. Gamett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
28


Reviews:
[{"review_id": "rWDFWDHcyX", "reviewer": "Reviewer_6WgB", "summary": "This paper studies Smoothed Online Convex Optimization with multi-step nonlinear switching costs and feedback delay. They propose an ML-augmented online algorithm named RCL that combines ML predictions with an expert online algorithm. The authors show that RCL can guarantee $(1 + \\lambda)$ competitive ratio against any expert while improving the average-case performance. They show the effectiveness of RCL using battery management as a case study.", "questions": "Is it possible for the reservation cost design to be overly conservative, resulting in the constrained optimization problem yielding an empty solution set?", "limitations": "n/a", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Learning augmented algorithms is an important paradigm for designing more practical algorithms. Incorporating ML-augmented algorithms with multi-step nonlinear switching costs and feedback delay is a new and challenging problem.\n2. The algorithm is simple and intuitive to understand. The authors provide a detailed analysis of the algorithm and the proof is rigorous.\n3. This paper is well-written and easy to follow. The authors provide a detailed literature review and a clear introduction to the problem setting. The authors also provide a detailed discussion of the experimental results.", "weaknesses": "1. The algorithmic contributions of the paper are a bit weak. The idea of constructing reservation costs to hedge against any possible uncertainties and then solving a constrained convex problem to project the ML prediction into a robust action set is quite standard in ML-augmented algorithms. \n2. There lacks a lower bound on the trade-offs between robustness and average performance in ML-augmented algorithms.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your efforts and time in reviewing our paper. \n\n`Algorithm design and novelty:` It’s essential to construct a robust action set to hedge against future uncertainties for guaranteed robustness in learning-augmented online algorithms. Nonetheless, how to achieve so is very challenging. In our problem, the feedback delays introduce additional uncertainties, and multi-step memory in the switching cost means the current action can affect future costs in multiple steps. Both make it substantially challenging to construct a robust action set. In fact, even without ML predictions, addressing the hitting cost feedback delay and multi-step nonlinear memory is already challenging and an independent study. For the first time, our carefully-desgined reservation cost guarantees competitiveness of unreliable ML predictions in this challenging SOCO setting. To our best knowledge, this is a novel and significant contribution to the SOCO literature.  \n\n`Empty solution set:` An improperly-constructed robust action set can result in empty solution sets (example in Lines 207-217). This also further reinforces our previous point \"how to achieve so (i.e., constructing a robust action set) is very challenging\". Therefore, we make contributions by designing a reservation cost that ensures there always exists a **non-empty** solution set regardless of future uncertainties. This is also stated in Lines 241-242 and proved in Lemma C.4 in the appendix.\n\n`Lower bound:` The performance analysis for learning-augmented online algorithms involves a tradeoff between following the ML predictions for average performance improvement and following the expert for robustness (as governed by $\\lambda>0$ in our paper). To our best knowledge, the optimal (or \"lower bound\") tradeoff still remains an open challenge in learning-augmented algorithms, except for a small number of simple online problems. Our learning-augmented algorithm is the first and makes contributions to the general SOCO setting with delayed feedback and multi-step memory. Our result in Theorem 4.1 bounds the performance of RCL, and shows the clear insight that the robustness parameter $\\lambda>0$ governs the tradeoff between following ML predictions and the expert's actions. While it's important to characterize the Pareto-optimal tradeoff curve, we leave it as future work that the learning-augmented algorithm community can explore (Line 415).\n\n\n"}, {"review_id": "eGhv8jLxoh", "reviewer": "Reviewer_axLK", "summary": "This paper studies a problem, namely, Smoothed Online Convex Optimization (SOCO) with feedback delay and multi-step nonlinear memory, proposing a machine learning augmented online algorithm (RCL) with certain theoretical guarantees. This algorithm considers to implicitly hedge the decisions made by online and offline predictors, using a new constraint action set onto which the algorithm projects its decisions. This constraint set requires the decisions within it to achieve a trade-off between the hitting cost and the switching cost. By this design, this work achieves the first worst-case type cost bound for machine learning augmented algorithm under the given setting, and proposes a sufficient condition for the proposed algorithm to attain finite robustness and 1-consistency simultaneously. Moreover, the paper demonstrates that the algorithm RCL benefits from robustification-aware training and offers an average cost guarantee. Comprehensive experiments are executed to support these results.", "questions": "1.\tThis paper claims that it provides a sufficient condition to achieve the finite robustness and 1-consistency simultaneously (line 63). But Corollary 4.1.1 suggests that this condition might be applicable for the proposed specific algorithm only. Moreover, this condition requires a per round lower bound for the switching cost of the expert algorithm. Does this condition hold for a broad class of expert algorithms? Could the sufficient condition proposed in Corollary 4.1.1 be suitable for a more general ML-augmented algorithm to realize the best-of-both-world guarantee? \n2.\tI am confused about the term \"worst-case\" used in the discussion about Theorem 4.1. Based on my understanding, the worst-case bound should account for the upper bound of the minimax ratio. It would be beneficial if the authors could discuss about the relationship between the minimax bound and the bound in Theorem 4.1.\n3.\tThere are concerns regarding the existence and convexity of $\\mathcal{X}_t$. Does the solution of Eq. (1) below line 223 always exist? It appears from Corollary 4.1.1 that the action set $\\mathcal{X}$ is finite. If that is the case, then the \"robustified\" action set defined at line 223 may not exhibit convexity due to its discrete nature. Can the authors answer the above two questions?\n4.\tWould the authors be able to provide further discussion concerning the technical contributions made in addressing the issues related to feedback delay, especially in comparison with previous works?", "limitations": "Not much.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "The writing of this paper is good with detailed explanations of the achieved results and the motivation is well substantiated by the experiments. The proposed algorithm is clear and easy to understand. The inherent nature of delayed feedback in the considered problem might pose an obstacle for algorithm design and analysis, and this paper proposes a solution for it.", "weaknesses": "I harbor some reservations regarding the applicability and scalability of the theoretical findings presented in this paper. Please refer to the \"Questions\" section below for further details.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your efforts and time in reviewing our paper.\n\n`Sufficient condition:` The prior study [1] proves an \"impossibility\" result: 1-consistency and finite robustness are not achievable simultaneously without further assumptions due to the fundamental hardness of the SOCO problem (even without delay feedback or multi-step memory). Our result in Corollary 4.1.1 shows a sufficient condition for our algorithm (RCL) to achieve 1-consistency and finite robustness simultaneously. There might exist other conditions under which alternative algorithms proposed in the future may also achieve 1-consistency and finite robustness simultaneously, but our work provides the first condition in the field and advances the result in [1]. \n\nOur sufficient condition is not unrealistic in practice (Line 329-332). In fact, the condition is violated by an expert (not necessarily the best-known competitive expert iROBD) only in dummy cases (i.e., its action that results in zero switching cost also has zero hitting cost). Even when the condition is not satisfied, our main result in Theorem 4.1 still bounds the cost of RCL and is consistent with the \"impossibility\" result in [1].\n\n`Minimax and Theorem 4.1:` In online optimization, the competitive ratio is typically defined as the maximum cost ratio of one algorithm to another (Definition 2). Thus, the \"worst case\" means the case that results in the maximum cost ratio. \"Minimax\" arises when minimizing the competitive ratio (i.e., minimizing the maximum cost ratio). The \"worst case\" in Line 256 means that our bound in Theorem 4.1 applies for any possible problem instances, including those worst-case instances that have the maximum cost ratios. \n\n`Existence and convexity of` $\\mathcal{X}_t$: An improperly-constructed robust action set can result in empty solution sets (example in Lines 207-217). Thus, we make contributions by designing a reservation cost that ensures there always exists a non-empty solution set regardless of future uncertainties. This is also stated in Lines 241-242 and proved in Lemma C.4 in the appendix.\n\nAs in the standard SOCO literature (e.g., [1]), the action set $\\mathcal{X}$ is assumed to be a subset of $R^n$ (Line 116), and its size $|\\mathcal{X}|$ can be measured by the maximum norm distance between two points in $\\mathcal{X}$ (e.g., [3,4]). Thus, along with convex costs, the set $\\mathcal{X}_t$ is also convex. We'll clarify this point in our revision.\n\n`Feedback delay`: The feedback delays introduce significant uncertainties for robustness guarantees, as we cannot immediately evaluate the costs of our algorithm and the expert. Thus, for robustness guarantees, we have to consider additional risks due to not following the expert's action and bound the maximum cost difference in Eq. (2) by exploiting the cost structures. The prior study [2] also considers multi-step feedback delays, but it has a more restrictive model where all the feedbacks have the same delay (whereas we allow different delays of up to $q$ steps in Definition 1 in Line 154-157). Most importantly, [2] is a purely expert algorithm and does not consider an ML prediction. To our knowledge, our work is the first to consider learning-augmented algorithms for the challenging setting SOCO with feedback delays.\n\n\n**References:**\n\n[1] Daan Rutten, Nicolas Christianson, Debankur Mukherjee, and Adam Wierman. 2023. Smoothed Online Optimization with Unreliable Predictions. Proc. ACM Meas. Anal. Comput. Syst. 7, 1, Article 12 (March 2023).\n\n[2] Weici Pan, Guanya Shi, Yiheng Lin, and Adam Wierman. 2022. Online Optimization with Feedback Delay and Nonlinear Switching Cost. Proc. ACM Meas. Anal. Comput. Syst. 6, 1, Article 17 (March 2022).\n\n[3] Marek Bukáček, Pavel Hrabák, Milan Krbálek. 2018. Microscopic Travel Time Analysis of Bottleneck Experiments. Transportmetrica A Transport Science.\n\n[4] https://engineering.purdue.edu/ChanGroup/ECE302/files/Slide_4_01.pdf "}, {"review_id": "c0KpDW1nC1", "reviewer": "Reviewer_rcGc", "summary": "This paper studies the  Smoothed Online Convex Optimization with  multi-step nonlinear switching costs and feedback delay. In this setting, they propose Robustness-Constrained Learning (RCL), which  combines  existing online algorithm with a novel reservation cost to robustify untrusted ML predictions. Theoretically, they provide both  worst-case and average-case guarantees  for RCL. Finally, they provide some experiments to evaluate RCL.", "questions": "See Weakness", "limitations": "There are no limitations with regards to negative societal impacts.\n", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well written and organized. The paper thoroughly explains the challenges of incorporating ML predictions in their setting and emphasizes the importance of developing novel algorithmic techniques to overcome these difficulties.\n\n2. The theoretical results are sound and look rigorous. The worst-case bound of RCL is novel.\n", "weaknesses": "1. The weakness of the paper lies in the design of reservation costs, which may seem somewhat technical for analysis purposes. Additionally, the discussion on the optimization complexity for solving the constrained convex problem is missing, leaving a gap in understanding the practical implications of the proposed approach.\n\n2. The paper's experimental results should be included in the main part to enhance confidence in the efficiency of RCL. Presenting empirical comparisons of RCL with other methods would demonstrate its advantages and substantiate the claims made in the paper. This would provide valuable evidence of the proposed algorithm's performance and practical benefits.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your efforts and time in reviewing our paper. \n\n`Reservation cost and complexity:` If we choose an action different from the expert without a reservation cost, it’s possible that the competitiveness against the expert is violated (an example is provided in Lines 210-217). Thus, for guaranteed competitiveness, our novel reservation costs are designed to hedge against any possible uncertainties due to hitting cost feedback delays and multi-step non-linear memory in the switching costs. It bounds the maximum future cost difference in terms of the difference between our actual action and the expert's action. We’ll revise the presentation for the reservation cost to improve its readability.\n\nThe constrained problem in (1) for computing the robust action set is convex, and hence it can be efficiently solved using standard convex solvers without a significant computational burden at runtime. For example, in our experiment, each testing process (including 1400+ inferences) takes less than a second on a laptop (Line 586 in the appendix).\n\n`Simulation results:` Our experimental results for EV charging station management can be found in Appendix B. Our results highlight the advantage of RCL in terms of robustness guarantees compared to pure ML models, as well as the empirical benefit of training a robustification-aware ML model in terms of the average cost. Per the reviewer’s suggestion, we’ll include some of the key results in the main body of the paper for better understanding.\n"}, {"review_id": "dwsZM2gTr8", "reviewer": "Reviewer_WzoZ", "summary": "This paper considers the smoothed online convex optimization problem, in which, in addition to the standard hitting cost incurred per step, the algorithm also incurs a switching cost which relates to changes in its chosen action. The paper considers switching costs which are multi-step (relate to the previous p time steps). \n\nThe paper presents an ML-augmented algorithm for the problem, which given a possibly-inaccurate predictor and a robust expert, is able to utilize the predictions from the predictor to the degree to which they are accurate, while not exceeding the cost of the expert times some small factor. This is done by taking the predictions and projecting them onto a space of possible actions dictated by the expert. \n\nThe paper also discusses how to adjust the training of an ML model to take into account the fact that the model's predictions are then projected onto the actions allowed by the expert.", "questions": "none", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The model, and the concept underlying the algorithm, are natural. \nI liked the figure in Appendix A, perhaps it should be part of the main body of the paper. ", "weaknesses": "In my opinion, the writing of the paper makes it hard to gain an intuitive understanding of the contributions of the paper within the scope of reasonable reviewing. For example, consider Theorem 4.1; excluding the robustness term, it is very hard to understand the significance of this theorem. Perhaps this bound seems simple and intuitive to experts more familiar with this problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your efforts and time in reviewing our paper. \n\n`Significance:` We’ll revise the paper to improve its presentation. Our contribution is a novel ML-augmented algorithm that exploits ML predictions to improve the average performance while bounding the worst-case performance in a general SOCO setting with hitting cost feedback delay and multi-step non-linear switching costs. The feedback delays introduce additional uncertainties, and multi-step memory in the switching cost means the current action can affect future costs in multiple steps. Both make it substantially challenging to construct a robust action set. In fact, even without ML predictions, addressing the hitting cost feedback delay and multi-step nonlinear memory is already challenging and an independent study [26].\n\nOur algorithm design and analysis (Theorem 4.1) are substantially new and differ from those used in simple SOCO settings. More specifically, the proof of Theorem 4.1 relies on a novel and crucial techniques that removes the dependency of $x_t$ on the history in the online decision process. \n\nThe second term in the bound in Theorem 4.1 shows how well RCL follows the ML predictions given $\\lambda>0$. Specifically, when $\\lambda$ increases, RCL will be closer to ML (see the definition of $\\Delta(\\lambda)$ in Line 252). Moreover, it shows that RCL stays closer to the better-performing expert for guaranteed competitiveness when the expert’s cost is lower, and vice versa. \n\n**To summarize, our work is the first learning-augmented algorithm for the challenging SOCO setting with feedback delay and multi-step switching costs. It makes a novel and significant contribution to the growing SOCO literature.**\n"}, {"review_id": "oKqdwp0FHO", "reviewer": "Reviewer_6vwR", "summary": "This paper considers the SOCO problem with multi-step nonlinear switching costs and feedback delay. The authors propose the RCL algorithm, which projects the ML predictions on to a robust action set determined by the expert’s predictions. They show that RCL maintain the $(1+\\lambda)$-competitiveness against the expert while exploiting the potential of ML predictions. Moreover, they identify a sufficient condition under which the RCL achieves finite robustness and 1-consistency simultaneously. They also give an upper bound of the average cost of RCL, which reveals the advantage of training the ML model in a robustification-aware manner. Finally, they validate the theoretical results using a case study of battery management.", "questions": "- Few lines explaining why the cost difference and the switching cost difference can be upper bounded by $H$ and $G$ respectively would help understanding.\n- How to efficiently compute the robustified action set? If it cannot be efficiently computed, how you learn that set in your experiment?\n", "limitations": "The authors have already mentioned in the paper (line 408-417).", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "- Challenging setup. This paper considers SOCO with hitting cost feedback delay and multi-step nonlinear memory in the switching cost, which is very hard to deal with.\n- New algorithm design and new proof approach. The intuition behind their algorithm is clearly explained in line 232-240. Theorem 4.1 is proven by considering a new reservation cost, which decouples the dependency of the online action on the history.\n- Good theorems with adequate explanation. The paragraphs following Theorem 4.1, Corollary 4.1.1 and Theorem 4.2 give comprehensive analysis of the results.\n", "weaknesses": "- Assume known switching cost and smoothness constant. Convexity and smoothness assumptions on the hitting costs and switching costs.\n- The robustification-aware ML model is hard to be trained using standard back-propagation.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your efforts and time in reviewing our paper. \n\n`Explanation of costs difference bounds:` The smoothness of the cost functions implies that, given a bounded difference in two actions, their cost difference is also bounded (formally stated shown in Lemma C.1 in the appendix). Thus, when RCL chooses a different action than the expert, the future cost difference can be bounded in terms of the action difference shown in $H$ and $G$ in Section 4.1.\n\n`Computing the robust action set:` The constrained problem in (1) for the robust action set is convex, and hence it can be efficiently solved using standard convex solvers without a significant computational burden at runtime. For example, in our experiment, each testing process (including 1400+ inferences) takes less than a second on a laptop (Line 586 in the appendix).\n\n`Assumptions:` Along with known switching costs and constants, the convexity and smoothness assumptions on the costs are standard in the SOCO literature. These assumptions are needed for theoretical analysis and can be good approximations of realistic scenarios in practice.\n\n`Training using back-propagation:` The robustification step in Line 5 of Algorithm 1 can be viewed as an implicit layer, which can also be differentiated. Specifically, to facilitate standard training using back-propagation, we have derived the gradients in Appendix D. Note also that differentiating the implicit layer is also commonly considered in the literature (e.g., the reference at the bottom of this response).\n\n**Reference:**\n\nAkshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and J. Zico 560 Kolter. Differentiable convex optimization layers. NeurIPS 2019.\n\n"}, {"review_id": "ZWiGqSoso6", "reviewer": "Reviewer_atug", "summary": "This paper studies Smoothed Online Convex Optimization (SOCO) problems where the target is to minimize the sum of a per-round hitting cost and a switching cost that penalizes temporal changes in actions.\n\nThe most significant difference from previous studies is that they assume a delayed hitting cost and a nonlinear multi-step switching cost, which is quite more general than before and thus brings technical difficulties to provide theoretically guaranteed methods.\nFurthermore, they also want to use ML-based online optimizers to enhance performance.\n\nTo that end,  they developed a meta-algorithm that robustifies a given online optimizer by projecting its suggested action onto a robustified action set computed from a given expert method and historical observations. \nThey provide a worst-case analysis for the cost of the resulting algorithm, based on which, they further establish a robustness guarantee and consistency result in the language of $CR$-competitive (see Definition 4) once a condition is satisfied.\nIn the appendix, they explore the empirical performance of the proposed algorithm using a case study of battery management and validate its robustness.", "questions": "1. Intuitively, once establishing the worst-case bound uniformly in Theorem 4.1, one could easily get an average version (because the average case is always no worse than the worst case). Hence, it is unclear to me why the author bothered to introduce another result to bound the average cost in Theorem 4.2. \n\n2. In Appendix D, the author spent much space explaining how to compute $\\nabla_W \\mathrm{cost}(x_{1:T})$. The reason is that the operator of projecting ML predictions into a robust set cannot be easily differentiated as typical neural network layers. So why bother to use this projection method? Why not use a primal-dual method that provides a projection-free alternative?", "limitations": "See the weakness part and questions.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The studied setting is general enough and can incorporate popular neural networks as its part. \n2. The worst-case theoretical analysis seems new and the proof seems correct.\n3. Though put in the appendix, the experiments are well conducted with detailed descriptions of the experiment setup and chosen parameters, and a careful analysis of the experiment results. I appreciate the experiments a lot.\n4. The paper is well-written mostly and the analysis is always to the point.\n", "weaknesses": "However, there are some parts not clear enough.\n\n1. The term ``multi-step nonlinear memory’’ appears abruptly in line 38. I think several additional explanations would help readers to digest this concept better for the first time.\n\n2. In line 200, the author didn’t explain the meaning of $\\text{cost}(x_{1:T})$.\n\n3. Line 353, it is unclear to me what the notation $\\text{Rob}_{\\lambda} \\left(\\tilde{x}_{1: T} \\right)$ means.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your efforts and time in reviewing our paper. \n\n`Average cost bound:` The reviewer is correct that an average cost bound can be established based on the worst cost bound. We provide Theorem 4.2 to confirm that it’s beneficial to train the ML model in a robustification-aware manner according to Eqn. (6). Additionally, it implies that the robustification step is more valuable in terms of bounding the average cost when the ML model is not well trained (e.g., due to inadequate training data). More explanations of the average cost analysis are available in Line 368-387.\n\n`Differentiable robustification:` While adding a regularizer is an alternative to differentiating the constrained optimization (i.e., the robustification step in Line 5 of Algorithm 1), we need to properly tune the weight (i.e., Lagrangian multiplier or dual variable) to meet the constraint. Thus, we directly consider differentiating the robustfication step to be consistent with our algorithm design. The robustification step can be viewed as an implicit layer, which is also differentiatiable. Specifically, to facilitate standard training using back-propagation, we have derived the gradients in Appendix D. Note also that differentiating the implicit layer is also commonly considered in the literature (e.g., the reference at the bottom of this response).\n\n`Multi-step nonlinear memory:` It means the current action appears in the future switching costs for multiple steps, and hence penalizes temporal changes in actions over multiple steps. For example, given the position of a robot as the action for motion planning, a two-step memory captures the acceleration (see details in Ref [2] at the bottom of this response). We’ll explain this in the revised paper.\n\n`Notation:` $cost(x_{1:T})$ means the total cost given a sequence of actions $x_{1:T}$. The notation in Line 353 means the training loss is defined directly in terms of the robustified actions, rather than pre-robustification ML predictions $\\tilde{x}_{1:T}$. Hence, we refer to training using this loss as robustification-aware training (Line 348).\n\n\n\n**Reference:**\n\n[1] Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and J. Zico 560 Kolter. Differentiable convex optimization layers. NeurIPS 2019.\n\n[2] Shi, Guanya, Yiheng Lin, Soon-Jo Chung, Yisong Yue, and Adam Wierman. Online optimization with memory and competitive control. NeurIPS 2020.\n"}]

Author rebuttal:

Meta-review: In this paper, the authors investigate a variant of smoothed online convex optimization (SOCO) which includes multi-step nonlinear switching costs and feedback delay. To this end, they propose a machine learning (ML) augmented online algorithm, namely RCL, which utilizes an expert algorithm to robustify untrusted ML prediction. They prove that RCL is able to guarantee (1+$\lambda$)-competitiveness against any expert while improving the average-case performance.

This paper is easy to follow, and the algorithm is well-motivated. RCL is the first ML-augmented algorithm with a provable robustness guarantee under the setting of this paper. This constitutes a significant contribution to the field of SOCO.
Decision: Accept (poster)