Barely Random Algorithms and Collective Metrical Task Systems
Authors: Romain Cosson
Laurent Massoulié
Venue: NeurIPS 2024 spotlight (2024)
Keywords: online algorithms
learning-augmented algorithms
barely random
advice complexity
metrical task systems
competitive ratio
online learning
randomness
hysteresis
transaction costs.
Primary area: online_learning

Abstract: We consider metrical task systems on general metric spaces with $n$ points, and show that any fully randomized algorithm can be turned into a randomized algorithm that uses only $2\log n$ random bits, and achieves the same competitive ratio up to a factor $2$. This provides the first order-optimal barely random algorithms for metrical task systems, i.e. which use a number of random bits that does not depend on the number of requests addressed to the system. We discuss implications on various aspects of online decision making such as: distributed systems, advice complexity and transaction costs, suggesting broad applicability. We put forward an equivalent view that we call collective metrical task systems where $k$ agents in a metrical task system team up, and suffer the average cost paid by each agent. Our results imply that such team can be $O(\log^2 n)$-competitive as soon as $k\geq n^2$. In comparison, a single agent is always $\Omega(n)$-competitive.

Barely Random Algorithms and Collective Metrical Task Systems
Romain Cosson Inria, Paris romain. wwssonoiniia....ooo.
Laurent Massoulié Inria, Paris
Iaurent.nassulleebmri...
Abstract
We consider metrical task systems on general metric spaces with n points, and show that any fully randomized algorithm can be turned into a randomized algorithm that uses only 2 log random bits, and achieves the same competitive ratio up to a factor This provides first order-optimal barely random algorithms for metrical task systems, i.e. which use number of random bits that does not depend on the number of requests addressed the system. We discuss implications on various aspects of online decision making such distributed systems, advice complexity and transaction costs, suggesting broad applicability. We put forward equivalent view that call collective metrical task systems where k agents in metrical task system team up, and suffer the average cost paid by each agent. Our results imply that such team can be Ologg n) competiiiee as soon as k 2 n², comparison, single agent is always ((mn--comettitive
1 Introduction
Recent progress the competitive analysis of important online problems, such as the k-server problem, metrical service systems and metrical task systems have relied on introduction of continuous optimization methods, such as the online primal-dual framework (see e.g. the book of [17),, and more recently, the online mirror descent framework 153 [5] By design, these methods assume that the online algorithm is provided with an infinite number of random bits. In this paper, address the question of whether this requirement is inherent to the online problem. or specific to the methods at hand, by focusing on the influential example of metrical task systems [46
10
33
22
To answer this question, we study the notion of barely random algorithm, introduced by 44 in the early days of competitive analysis of online algorithms: "We call an algorithm that uses bounded number random bits regardless of the number requests barely random". In the case of metrical task systems, we will observe that this notion is particularly fruitful, as it connects various aspects of online decision making such as collective systems, switching costs, and advice complexity.
Metrical Task Systems (MTS) is a central problem in online algorithms and online learning [43 19 26 which recently attracted the interest the community working on
28 35
18
4 In essence, the problem is similar to the classical learning setting of 'prediction with expert advice' [4]] with the key difference that there a cost associated to switching between experts. We now describe the setting of metrical task systems [22 in a way that highlights role played by the source of randomness.
algorithms [
20
Metrical Task Systems. The problem is defined on metric space X' = (X, d) where X is a finite set of cardinality |X| = n. The input is a sequence of cost vectors c(-) = (e(t)) E (R.) ) and the output a sequence of states p(-) = (p(1))teN E X The cost associated to each time / E is the sum of the movement cost d(p(l 1), p()) and the service cost (() The cost all time steps
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

The participants therefore writes as follows:
(ost(p())),(()))) Σ 11,tt-1),p(h) + (pco)(t). 121
The offline benchmark, denoted by (PT(c(-)). )), is defined as the smallest achievable cost over all possible sequences of states, i.e. (PT(c(-)) = inf p()) Cost(p(-), e(-)). An online algorithm A is a method to define a túme-consistent trajectory, i.e. such that the state at some time depends only on current and past information. It may use some source of randomness (seed) which sampled from known probability distribution s ~ D. Formally, the sequence of states P.((-) defined by algorithm can be computed by Vt pa(t)
A(c(1). c(t), s). The algorithm A said to be a-competitive, for some E I. if it satisfies E (Coss(Coossaall e(-)) I x OPT(c(-)) + B for some fixed 3 E R and for any c(-) E ( In this paper, we are interested in the way the competitive ratio scales with the source of randomness D. When D = U({0, 1)²), or equivalently when D = (1 2), we say that the algorithm is provided with b random bits. More generally, consider the case where D = =M((1--.. k)) for arbitrary l N. In extreme, the case of k = 1 is known as the deterministic variant of the problem and is well understood since the inception of metrical task systems. In the other extreme, the case of k +00 (more formally, = ([(0, 1)x)) is known as the randomized variant of the problem and was solved more recently. Any other value of N defines the k-barely random variant, which is the focus of this paper. For reasons that will now become apparent, we will also refer to this setting as the k-collective variant.
Collective algorithu for metrical task systems. Consider team of & N agents that are collectively confronted to a metrical task system. We can denote the positions of the agents by p1 (4),..., Pk (1) E X and their trajectory is given by k deterministic online algorithms AI.... Ag. are collaborating, in the sense that the cost paid by team is the average cost paid by its members. It is immediate to observe that k-collective setting of metrical task systems is exactly the same problem as the k-barely random setting defined above. This is because, given k-collective strategy, one can define a k- bareell random algorithm by using the seed s ~ (((1,..... .......,, k}}) to sample uniformly at random one strategy to imitate. In the rest of the paper, will thus the terms collective and barely random indistinctively. The collective presentation reflects a variety of real-world situations, where finite team of agent is confronted to adversarial environment, A simple biological illustration is in foraging, e.g. when a colony of & ants is tasked to collectively gather a large amount of food (modeled by the service costs) from n locations, while limiting the collective energy spent (modeled by the movement costs) [32] 36).
1.1 Main contributions
Our main technical result is the following.
Theorem 1.1 (Section 3. For any metric space X with n points, for any 6 >> 0, for any integer k 2 n² if there exists a (fully) randomized MTS algorithm that is a-competitive, then there exists a k-barely random MTS algorithm that is (1 + cc-coeptiie
The factor announced in the abstract can be readily recovered from this theorem by letting which we can assume in the rest of this section for ease of presentation. Theorem [.] relies on two techniques: new equivalence between barely random algorithms and barely fractional strategies for metrical task systems that is presented in Section and new discrete first-order method that is developed in Section 3
In light of the Ollog
2 n) -competitive randomized algorithm of Bubeck et al. [1] for metrical task
systems, Theorem 1.I has the following consequence:
Corollary 1.2 (of Theorem 1.1b. There is Olog" -))competitiiv algorithm for MTS that requires on [2 log n] random bits on any n point metric.
We provide in Section 4 a simple lower- bound that almost matches this result. We also provide tight guarantee in the case of the uniform metric space.
Proposition 1.3 (Section 4p. Any Ologg n) -omooppetteevee algorithm for MTS on an point metric requires at least log n mlog log n) random bits. In the uniform metric space, there is Olog n)- competitive algorithm that only requires [log n random bits.
2

---

Finally, we observe that the notion of barely random algorithm is closely connected to the notion of advice complexity. Advice complexity was introduced by [29] to measure the information content of online problems. In our context, one could ask the following question: What amount of information about the cost sequence suffices to improve over the 2n lower-bound on the deterministic competitive ratio of metrical task systems? Since bits of advice are at least as useful as random bits (see [37 for more details), we have:
Corollary 1.4 (of Theorem I. For any n point metric, there exists a deterministic MTS algorithm that is Olog n) -coopetiieee,,, using only [2 log n. bits of advice
This is a clear improvement over the result of 34 which requires an advice of size that scales with the length of the cost sequence.
1.2 Other applications
Our method is helpful in any setting where acquiring random bits is costly. In concrete implemen- tations and real-world systems, we also expect that barely fractional configurations (which are the discrete objects manipulated in this paper) are generally much more practical to handle than fully fractional distributions (which are arbitrary real numbers).
Our results also imply that a finite team of deterministic agents can be competitive in a way no single deterministic agent could be. This echoes of the study of intelligence in multi-agent system, with concrete applications, such as dynamic power management 33 Consider for example a computer with three power modes (on, sleep, off) with a switching cost of between on and sleep and another switching cost of, say, 5 between sleep and off. At each time f the request is either that the computer used and e(t) = (1, +oo) i.e. the computer must be in state on or the computer is not used and c(() (1, 0.5, 0) i.e. the computer would rather be off than sleep, and sleep than on. Consider the variant of the problem, where the computer in fact composed of k
components (e.g. screen, CPU cores, etc.) that can each individually switch between one of the three modes (on, sleep, off). The energy spent by the computer is the sum of energy spent by its constituents. Since n 3 and k > n², our results imply that such system can enjoy the randomized competitive ratio, even if the cost sequence e(-) depends on the state of the system (deterministic adversary).
We also note that our work has a flavor that is similar to learning-augmentn algorithms. Learning- augmented algorithms use predictions coming from black-box algorithm in the hope improve over the performance of competitive algorithms when predictions are accurate. In the same spirit, our method in Section 3 Jses fully fractional distribution coming from black-box algorithm, and tracks it via a proximal method.
1.3 Related works
Metrical task systems is a problem introduced by BBroddn et al. (1922) 12
This initial work resolved
the deterministic competitive ratio, which is of 2n 1 for any metric space with n points; well as the randomized competitive ratio for the uniform metric space, which is in Oloog n). The randomized competitive ratio for general point metries remained open until Bubeck al. (2021) proposed a
Olog² 2 n) competiiive algorithm and [16] obtained matching lower-bound. These breakthroughs
followed a long line of research (see e.g. [46 10 33 22
and references therein).
Metrical task systems is deeply connected (both, in results and methods) to the classical online setting of "learning with expert advice", as observed by [9]. The differences are (I) there is a (movement) cost associated to switching from one expert to another (2) the offline benchmark is the best moving strategy as opposed to the best fixed strategy (3) the goal is to obtain a multiplicative guarantee (competitive ratio) rather than an additive guarantee (regret).
The notion of barely random algorithms was introduced by [4 for the list update problem. this paper, they present an algorithm that is 1.75 1.75-competitiv for the list update problem, using exactly random bits, where n is the length of the list. Such algorithms are further studied in the celebrated book of [I]. Barely random algorithms were later investigated for paging [37]. The notion also had some echo in the literature on scheduling (see (31] and references therein) but it was not applied before to metrical task systems related problems.
3

---

Advice complexity was first studied in the context of metrical task systems in [30]. In this paper, the authors study the setting where b bits of advice are provided at each time-step to a deterministic metrical task systems algorithm, for b of order log n. The total amount of advice they require is therefore of order B Tlog n, where T is the number of time-steps. One surprising consequence of our results (Corollary [.44 is that we present deterministic algorithm that has a competitive ratio of Ologg n) using a single advice of total size B = 2 log i.e. which is independent of the number of time-steps T. We note that advice complexity is connected to the advice is untrusted [2].
algorithms, when
Collective algorithms originate from the literature on distributed algorithms. For example, in the problem of collective tree exploration, a team of k agents is tasked to go through all edges of some unknown tree as fast as possible (34). The connections observed in [24] between this problem and randomized algorithms for metrical service systems provided some inspiration for the present paper. We note that the interpretation of probability distribution as a continuous swarm of infinitesimally small agents is not novel, see e.g. [6] and is directly connected to the so-called fractional formulation of metrical task systems. The novelty of our methods lies in the rigorous discretization of this fractional view, and leads to applications in collective and barely random algorithms. A surprising aspect of our method is that does not rely on a tree-embedding of the metric space, but seems naturally adapted to the general setting, thanks to the very general properties coming from optimal transport, such as the Birkhoff-von Neuman theorem. The discretization also relies on a non-trivial (though concise) first-order method, and which could be of interest for future works.
Finally, Section of this paper is reminiscent of first-order optimization methods. Gradient descent of a function f(-) is also known as the explicit Euler method, where one can write its t-th iterate as the minimizer of the sum of first order approximation of f(-) at the t 1-th iterate and a quadratic cost. A closely related first-order method is the implicit Euler method where the t-th iterate is defined by,
xx{)= = arg min [ax) + ||2- x0t - 1)11?
x
which is also known as the proximal operator 42 Our Equation 11 is reminiscent of this operator. One key difference is that replace the squared norm by an optimal transport cost, and that the offline objective function f(-) is replaced by an online potential, like in the work function algorithm Note that quite recently, the notion of Wasserstein proximal operator has appeared as a central object of study in the context of partial differential equations (see e.g. (55). A key difference with our Equation ( that we consider the Wasserstein-1 metric (aka, the earthmover distance) and not the W metric.
38
1.4 Notations, definitions and preliminaries
In the following, X =(x d) is a finite metric space, i.e. X is finite set and the distance d is positive, symmetric and satisfies the triangle inequality. We denote by n the cardinality of X.
We denote by P(X)) the set of all distributions on X. For any two such distributions æ, x' E P())), we call the optimal transport cost from x to x' and we denote by OT æ') the quantity,
OT x') =El("
inf
[ P.d
where T(x, x)) = {-r E [0, 1 Vp, EpEx (p, p¹) T. and Vpl T(, x/p) is the set of couplings from æ to x'. Classically, I(x, can be viewed as the probability distributions on X' x X' with their marginals respectively equal to x and x'. The optimal transport cost (also known as the Wasserstein distance) defines a distance between probability distributions on X. In particular, it satisfies positivity, symmetry and the triangle inequality.
For some point p E X, we denote by e, E P((X)) the probability distribution on X' that has all of its mass on p. Note that ep can alternatively be seen vector of R Denoting by @ the Kronecker product (aka the outer product) between vectors of V. we have, for any p. pf E X' that ep @ ep is an optimal coupling from Ep to Ep'
For an arbitrary constant l E N we denote by (x) the set of all distributions on X' that only take their values (0. 1/k,..., 1). Such distributions will sometimes be called 'configurations' to distinguish them from their continuous counterparts. For any two configurations x, x' (x().

---

there exists an associated optimal coupling π that only takes its values in 10,1/k..... 1,, i.e. which follows the discrete formulation of optimal transport by Monge. We call such a (discrete) coupling. an optimal transport plan. The existence of this optimal transport plan be seen as a consequence of the Birkhoff-von Neumann theorem which states that the extreme points of the polytope of doubly stochastic matrices are permutation matrices [8]. Indeed k x & doubly stochastic matrix naturally induces a coupling between two k-barely fractional configurations, with values {0, 10., if it is permutation matrix. The result then follows from the linearity of the objective.
For an integer k E N. we denote by u1(1..... k}) the uniform probability distribution over fl....,kl, k). For an arbitrary distribution D, we denote by Eewp(.) the expectation when the variable is sampled following D. All logarithms, denoted by log(-), are base 2.
Paper outline Section provides an equivalence between k-collective strategies and k-barely fractional strategies, which is used in Section to prove Theorem 1.]] Section providdes additional discussions, including the lower-boune bound as well as refined guarantees for the uniform metric space. The conclusion highlights some open directions towards making further connections between online algorithms and distributeed/clllctiis systems.
2 Barely fractional strategies for metrical task systems
In the introduction, we gave the classical definition of metrical task systems [1), while highlighting the role played by the source of randomness D. In the literature, variant called the fractional formulation is known to be equivalent to the problem when the algorithm is allowed an infinite number of random bits (i.e. when D U({0, 1). We start by recalling this fractional formulation and the equivalence in Section 1.1 We then introduce the notion of k-barely fractional strategies and we show their relevance to the atorementioned k-barely random setting in Section 2.2 In contrast with previous results, this equivalence relies on the Birkhoff-voo von Neumann theorem.
2.1 (Fully) fractional strategies for metrical task systems
Fractional Metrical Task System. In the fractional variant of metrical task systems, at any instant t, a fractional strategy denoted by xx-) maintains a distribution over the states, that only depends on the information available before time f, i.e. =<c(1),... c(t)) E P(X), which shall be denoted by (t) hereafter. The cost paid by the strategy at time is defined as the sum of a transport cost We denote by Cost(ax()), c(-)) the total
(z(t(t 1), at)) and service cost Epex Ep (t)t))p(t).
cost associated to the strategy, i.e.
Cost(a (z (a)((zz()) (())
Σ OT(a(1 - 1), + Exp(D)pp))
121
PEX
The interest of this fractional formulation comes from the following reduction, which is classical in the literature (see e.g. (14).
Proposition 2.1. For any fractional strategy for metrical task systems, there is a (fully) randomized algorithm that achieves the same cost, and reciprocally.
Proof. Consider randomized algorithm A(, with 8 ~ 1((0,1}*)) for metrical task systems and define x(-) at time by setting Vp E (t) = PA((((()) c(t), = p). It is clear from this definition that the service cost of the fractional strategy equals the expected service cost of the randomized algorithm. Also observe that the movement cost of the fractional strategy, which equals (= 1), =x))) at time t, must be less than the expected movement cost of the randomized algorithm which uses (possibly sub-optimal) coupling between the two consecutive distributions.
Reciprocally, assume that we are given fractional strategy xx-) E P(Z)). We can design randomized algorithm A(: 8) which relies on the random seed s ~ (((0,))))) Observe that we can make the seemingly stronger (but in fact equivalent, because {0, 1) is uncountable) assumption that D = ((, 1) This reformulation allows to have access to one fresh (independent) real sampled uniformly at random from [0. 1] at each time-step / E N, which we denote by s(l) E [0, 1]. We assume that at time L. - 1, the algorithm is in some state A(e(1)...... .(())....,,(.-.......... 1), 8) p(t p(t-1) -1). time
t, the algorithm considers the optimal transport plan π associated to OT(x(t 1), xt)) and samples
5

---

the state p(t) following the probability distribution proportinnal to (T(p(t - 1). p))))ex This can be done by inversion sampling using only the random sample s(t) E (1, 1)). It is clear by induction that the distribution of A(c(1):..- ...... c(t), s) = =((t) with this randomized algorithm follows exactly at)). Further, its expected movement cost E3 (d(((t - 1); p(t)) is exactly equal (by definition) to
the transport cost (z - x())).
L
2.2 Barely fractional strategies for metrical task systems
Barely Fractional Metrical Task System. We now introduce a discretization of the fractional formula- tion of metrical task systems. This will define a k-barely fractional strategy æx-). The definitions are the same as in the fully fractional variant above, except that at all times, the distribution ae()) E (2)) is constrained to belong to the set (.t) of distributions taking values in {0. 1 1/k,..., 1} (see the notations section). We now show that this formulation enjoys an equivalence with the barely random variant of metrical task systems, when the source of randomness is limited to D = (((1........ k}).
Proposition 2.2. For any k-barely fractional strategy for metrical task system, there is a k-barely random algorithm that acheives the same cost, and reciprocally.
Proof. We assume that we are given k-barely random algorithm A and define as above the fractional strategy (-)) at time t by Vp E Xx= xt(t) = P (A(c(I)..... c(t), 8) = p). It remains true (see the argument of Section 2.I that this fractional strategy has a smaller service and movement cost than the randomized algorithm. We also observe that since 8 ~ D = (4(0 1/k...., we have xxt)= E (x). Therefore, xx.) is a valid k-barely fractional strategy with a smaller cost than A.
The reverse reduction uses an ingredient from the theory of optimal transport: the Birkhoff- von Neumann theorem, which states that the optimal transport between ar, x' E (X) always admits an optimal coupling π taking its values in {0, 1/k,..., 1). that we call an optimal transport plan (see notations and preliminaries section). Given barely fractional strategy az(-), we define k- collective algorithm for which the population distribution will always match (t) E Px)) The result then follows from the equivalence between collective and barely random algorithms discussed in the introduction. We initially distribute the k agents following (0). Now, we assume as our induction hypothesis that the team at time 1 distributed exactly following x(t- - 1) and we show that we can deterministically redistribute the members of the team to follow xtt), while paying a moment cost of (z(xxtt - 1), (t)). Using the aforementioned Birkhoff- Neumann theorem, there exists an optimal coupling between ztt - 1) E (x') and (t) E (x)) that takes its values in {0, 1/k. 1). Concretely, from the collective point of view, this means that we can move the agents from distribution att 1) to distribution sn() using this coupling, without having to split any agent. We use this coupling to reassign the agents deterministically to their new destination (we assume that agents have arbitrary identifiers and the ability to communicate, in order to break the possible ties). Clearly, since the coupling is optimal, the average movement cost in the collective strategy will equal the transport cost of the fractional strategy, and since the population distribution of the agents is consistent with the barely fractional configuration, the service costs are equal.
Remark 2.3 (Fractional metrical task systems, with fixed transaction costs), A straightforward illus- tration of the fractional variant of metrical task systems is in asset management. Consider an investor distributing its stakes on several assets via sx()) E P(X') where X is a set of financial products such as stocks. The distance between two products is defined by the transaction cost associated to exchanging a unit value between two product (i.e. the liquidity of the products varies). The service cost corresponds to the cost of holding a poorly performing asset. The movement cost is a variable cost which is proportional to the mass that is exchanged at any round. Another type of cost that could naturally arise is a fixed transaction cost that the player should pay for converting any amount of stock p into stock p'. We propose to set this cost equal to Td(p. p²) for some real constant 7 >> O. In this setting, it becomes relevant for the player to perform transactions only if they involve a fructional mass greater than T. A direct consequence of our results (Theorem [.] and Proposition 2.2 is that adding fixed transaction cost T to the fractional variant of metrical task systems has little effect on its competitive ratio, provided that S 1/n2.

---

3 Potential function method for barely fractional strategies
In this section we provide the proof of the main result of the paper, Theorem 1.1 The core of our method is in Algorithm| [ which provides way to transform (black-box) fully fractional strategy ( in a k-barely fractional strategy zx-), while only loosing factor 2 in the competitive ratio provided that 2 n² (it then generalised arbitrary factor + e in the proof below). Following the reductions from Section 2
this method also allows to transform fully random algorithm into k-barely random algorithm with similar competitive guarantees.
Note that the cost of (x-) must be bounded by a constant times the cost of y-) if we hope to preserve the competitiveness of the latter. The informal reason why such guarantee difficult to obtain is that the adversary knows exactly the discretization method used by the team (by adversary, we mean the designer of the cost sequence e(-), and by the team, we mean the swarm constituting xx))). For instance, the naive rounding strategy which would be xxt) E arg min (x( (T(y(f),z) x) does not preserve competitiveness. This is because infinitesimal movements of y()) could induce large (order 1 1/k) movements of (x))) A good discretization strategy must therefore display a hysteresis phenomenon, in the sense that it does not undo a move right after that move was decided. This is precisely the idea behind our strategy in Equation (T) that employs a potential function D(..) to insure that a=() remains sufficiently close to yt) and an additional term in OT(æ(t 1), x+)) to limit the movement cost of x()). We note that the technique presents some similarities with first order optimization methods, which have been successful in several areas of online decision making. One key novelty is that is applied to a discrete space (x)
Algorithm 1: Barely fractional strategy for k 2 n²²
Input: at - 1): Previous barely fractional configuration
Input: (t): Next fully fractional distribution
Output: (t): Next barely fractional configuration
Solve for x E (2)()))
x E arg min D(x, y(t) OT(x(t x), xEPx(X)
(I)
where D(x, y) = 20T (a/2 + 1/(m breaking ties by maximizing OT(x(t - 1), x).
Theorem 3.1. Consider an abritrary n point metric X, some real > O and an integer k 2 n² /c. For any fractional MTS strategy yy-) on X which is a-competitive, Algorithm with with potential defined in provides a k-barely fractional MTS strategy x()) on X' which is (1 + cja-competitive.
Proof. We fix an integer k 2 n²² /e. Consider some a-competitive fractional strategy y(-). We shall
define (in an online manner) a (1 + coa-competitive k- d-barely fractional strategy x(-). by performing an appropriate discretization of (-))
For any pair of distributions x. y P(X)) we call the potential between x and y and denote by D(x, y) the quantity
D(a,y) = +1+ T+ x + n(1 + 11
where 1 denotes the vector of x with all its values equal to 1. The correctness of this definition stems from the fact that we will always have ar/(1 + e) + e/n(1 + +ejll E P(x)), because P()))
Upon arrival of request e(t) E RÆ the (fully) fractional distribution y(t) is computed from black-box algorithm, and the barely fractional configuration æxt) is defined via Equation (I.
(+) E arg mig Dax, (()) + OT(x(t - 1),
=EP+(X)
where ties are broken in favor of the configuration æ which maximizes OT(xr( 1), æ). We now aim to bound the movement and service costs of the aforedefined strategy ar-)) in terms of the movement and service costs of the black-box strategy y()).
7

---

Movement Costs. We start with the movement cost of æ(-). We decompose the change of the potential P(t) ((x((),, y(t)) as follows,
P(() P(t 1) (xx(t), v()) ()) -t-
= ((x(t), - D(x(t- ( (). + D(x(t -0)((((t11)10000000 v(() - D(x(t v)t - 1)),
S = (1
where the first inequality ((x(t),, -()= m(t) -OT x))) comes from 1), y(t 1)) <
the optimality of (t) in (I) and the other inequality (()
(1+e)OT(yl)) 1), 2()) a direct application of the triangle inequality for optimal transport. We
therefore have the at all times / 2 1,
OT(x(t- - 1), (t)) S P(t - 1) P(t) + (1 + ()TT(((( - 1). (())-
(3)
Taking the (telescopic) sum with (3). we obtain the desired bound on the movement cost of xx-).
EoT(x(t - ()) <
Σ
P(t - 1) - P(t) + c))(yyt - y())
- P(0) + (1 E)) Σ
(21
where P(O)= = ((x( (()) is constant bounded by the diameter X.
Service costs. We shall now show that at all times f 2 1,
vp E X (1) < (1 + ()),
This equation clearly implies that the service cost of xx)) is at most (1 + c) that of y(-). We shall use the following equation from Lemma 3.2 which states that at any time t, and for any configuration x' E P&((')) such that x' * (l))
D(x(t), < D(x', v()) + (t),))),
(5)
> a(I+)) 1 and ((), with 6 M[+e S लांन we obtain that there exists some p' E X such that z' = = o(e,/ ep) and satisfying O2 ut)) OT z') + OT(z', (()), where OT(z, x') = 5d(p. p'). We then consider the configuration x'' = xx)) E (ep ep), which will provide the contradiction by forming
Assume by contradiction that (4) is not satisfied. For some p E X, we have xp() + m(I+e)
(1) + mítto.- By applying Lemma 3.3 to the distributions - a=
violation of (5). First note that x' E Px( because xt(()= 2 1/k since (t) > (1 +1++1 (t), > 0. Also, by definition x' 7 (t). Finally, ((),)((())) (1+e)0T(z, y({)) (1 (1+e)OT(z) y()) + (1 + c))d(p p') = D( (t)) + d() = D(x', y()) + OT(x(t), x'), which provides the contradiction.
Overall, the movement and service costs of xx-) are bounded by (1++) those of y(-) (plus a constant), thus, the o-competitiveness of y()) implies the (1 <)aecomppeiiiveness of ax(-).
Lemma 3.2. At any time t. the configuration xxt) that selected by Equation I and the associated
lie-breaking rule satisfies that for any x'' E PPl(X) such that x' + x(l),
D(x(t), vt)) < D(x', vv()) + OT(x(t),
Proof. Recall that att - 1) is the configuration which immediately preceded st)). Consider and
some arbitrary configuration x' E (2)) Since (t) achieves the minimum of (.. we have
D(x(t), y(t) OT(x(t x(t) < D( y()) OT(x(t 1),x'),
Using the triangle inequality of optimal transport, we also have
OT(x(1 x') < OT(x(1 - 1), a()) (T a1),
The combination of both inequalities, proves non-strict version of Equation 5 D(x(t).v(t)) < D(w', v(t) + (T((t))
(6)
8

---

We now explain why this inequality is in fact strict for any x' * xt).. We note that equality can be met in O only if equality is also met in both of the aforementioned components of the inequality. We assume that is the case for some x' and will now show that x' = ax()). We have that,
OT 1), - Da'' v()) OT((((1 1),
+T
By the tie- neebbraking rule of [ the first inequality implies that OT - 1), x²) S (() which allows to conclude, using the second equality that (z(((t), x') O, and thus that æ' = xtt). This relies on the positivity of the optimal transport distance, which follows from the positivity of the distance in the original metric space X.
metric space X with points. Assume that for some real > and some point p E X one has Zp 2 tp++nd nò. Then, there is another distribution z' E P22), taking the form v = 2 + ó(ep'' e,,)) for some other point pl E X, which satisfies OT z. 3) = OT z') + OT y), where OT(z,z') = =.((p.pp)
Lemma 3.3. Let z E P(X) and y E P(X) be two distributions
Proof. By the triangle inequality of the transport distance, for any three distributions z', E P(X), we have (z y) & OT z') + OT(z', y). therefore will suffice to show the converse inequality. We consider an optimal coupling from z to y denoted by π (T(p1, p2)) p1.)px E2.. By definition, -p Upp = E (p, pi) - т (P1, p) 2 no. this sum of terms, at least one term has to exceed This allows to define one point/ p' E X' such that T(p, 2 8.
Next we consider the distribution z' z + 5(ep -e). First, observe that this distribution is well-defined, since 2p 2 Then, we note that n' = π + B(ep @ ew ep 2 epr) defines a coupling from z' to y and thus,
OT(z',8) .y) S Σ Pe)
OT y) OT(zz'),
P1.82
which finishes the proof.
Discussion, lower-bound and open directions
4.1 Uniform metric space
The uniform metric space is is a notoriously simple special case of metrical task systems. It is the metric space where all pairs of nodes are at the same distance Vp, p' E X, p & p' = d(p, p') 1. The (fully) randomized competitive ratio of metrical task systems on the uniform metric space is known to lie between H, and 2H, [1]. where H,, is the n-th harmonic number.
In this section, we show that [log n bits of randomness are sufficient to achieve constant factor optimal competitive ratio the uniform metric space. The proof can be seen as a direct discretization of the algorithm [2), and as an application of the 'game of balls and urns' in 225.
Proposition 4.1. There is n-barely random and 2H,, + 6-competitive algorithm for metrical task systems on the uniform metric space of cardinality n.
Proof. Following [1]. we decompose the time discrete phases, in order to obtain lower bound on OPT(c(-)). The (-thh phase starts at to 0 and for E N. the r-th phase begins at time &; and ends right before f++1 which is defined as the first instant satisfying that V/p X Euggteu cp(t) 2 1. Without loss of generality we can assume for simplicity that there always exist a state pt such that (see the continuous-time variant of metrical task systems, as in [14], for justification). We denote by i" the total number of phases, which only depends the cost sequence c(-). We observe that (PT(c(-)) 2 i", because the cost incurred by any fixed trajectory is at least one during given phase, and the cost of any mobile trajectory is also at least one.
Enstect: (c)
The idea of 12 to define a randomized algorithm that incurs cost of at most 2H, in each phase, and which is thus compettee In a given phase i, for any I E [4, (4), the strategy consists in assigning a+) to be the uniform probability distribution over the states in (p X' Ensree (T) < 1}. which are the non-saturated states. This strategy suffers movement cost of

---

at most 1 + 1/n 1/(n1 -122- Ha. where Hn denotes the n-th harmonic number. Note that the service cost of this strategy less or equal to its movement cost, so is 2H, competitive. Ufortunately, the strategy is not n-barely fractional, because it takes values in [1/n, (n .).....1) which are not all multiples of 1/n.
We consider simple discretization of this strategy, which does not suffers from the caveat described in Section This descritization relies on the decomposition in phases which is specific the uniform metric space. It can be seen as an application of the analysis of the 'game of balls and urns' which was used to design a collective tree exploration algorithm in [25] We recall the definition of the game. The game starts with n balls each located in one of n urns. In discrete rounds, an adversary picks an umn which contains ball and the player has to move one ball in that um any other urn. The game ends when all urns have been chosen at least once by the adversary. and the cost of the player is the number of rounds before the end of the game, re-normalized by 1 1/n. The simple strategy for the player that consists in relocating selected balls to the least loaded urn is known to induce cost of at most In(n) + I H,, + 3. Observe that this game models exactly the movement cost a corresponding n-barely fractional strategy in a given phase (where each ball represents a probability mass of I/n and each urn represents a point of the uniform metric space), Also, since the service cost is (again) bounded by the movement cost in given phase, the strategy is 2H + 6-competitive. D
4.2 Lower-bound on the number of random bits
We now explain why 2(log n) random bits are required to obtain an asymptotically optimal competi- tive ratio. We show the stronger result that a k-barely random algorithm for metrical task systems is at most (2n - 1) c-competiiive. Thus, Olog" n) -competiiievee strategy must have & 2 cst n/ log" 2 - corresponding to a lower-bound of log k 2 log n - Oloo log n) in the number of random bits.
Proposition 4.2. The competitive ratio of k-burely random algorithms for metrical task systems is at least (2n- 1)/k.
Proof. Consider a barely random algorithm A(., s). with s ~ D = algorithm A(.,1) 1) is sampled with probability 1/k. By the 2n - lower-bound of [12] on the competitive ratio of deterministic algorithms for metrical task systems, there exists sequence (2n 1)OPT(((-)). Integrating over the seed 2n- 20-1 OPT(e()).
k}). The deterministic
c(-) E EN such that (()) (([I,.... k:)). we get E, (Cost((pAs)))
The question of whether an order-optimal randomized competitive ratio can be achieved with k (nn) instead of & 2 n² remains open on general metric spaces. This seems plausible for weighted star metrics, which admit Ollog n) competitive strategies via an algorithm working in phases [17]. It is also possible that some metric spaces do require k- = ?(n2). Demonstrating such cutoff for barely random algorithms would nicely echo the cutoff between (loggn) and Ø(log? n) that seems to appear in the competitive ratio.
4.3 Conclusion and open directions for collective algorithms
The term 'collective algorithm' used in this paper is borrowed from the literature distributed algorithms [3 24 We believe that highlighting situations in which a team of agent can be competitive/intelligenn in a way that no single agent could be is interesting research direction. As presented in this paper, such situations echo the well-studied competitive gap between randomized and deterministic algorithms for online problems [7]. But collective algorithms come with considerations that go beyond their analogy with barely-randon
algorithms. For instance, one can study the competitiveness of collective algorithms under: restricted communications (such as the write-read model of (34] or the local model of (27)). synchronous movements (as discussed in (23). ), capacity
constraints (where the amount of agents a position is limited (6 (5)) or even with agents having
some degree of selfishness or maliciousness (then involving price of anarchy [39] for selfish agents, or some degree of robustness to byzantine faults 44 for malicious agents).
The authors thank the anonymous reviewers for their helpful comments. RC thanks Spyros Angelopoulos, Nikhil Bansal, Christian Coester and Christoph Dürr for discussions. This work was supported by PRAIRIE ANR-19- 19--311-0001.
Acknowledgements
10

---

References
[1] Keerti Anand, Rong Ge, Amit Kumar, and Debmalya Panigrahi. A regression approach to learning-augmented online algorithms. Advances in Neural Information Processing Systems, 34:30504-30517, 2021.
[2] Spyros Angelopoulos, Christoph Dürr, Shendan Jin, Shahin Kamali, and Marc Renault. Online computation with untrusted advice. In 11th Innovations Theoretical Computer Science Conference (ITCS 2020).
Zentrum für Informatik, 2020.
[3] Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon. Leamning-augmented dynamic power management with multiple states via new ski rental bounds. Advances in Neural Information Processing Systems, 34:167 14-1661441676,, 2021.
[4] Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, and Bertrand Simon. Mixing predictions for online metric algorithms. In International Conference on Machine Learning, pages 969-9833 PMLR, 2023.
[5] Xingjian Bai, Christian Coester, and Romain Cosson. Unweighted layered graph traversal: Passing crown via entropy maximization. Proceedings of the 2025 Anmual ACM-SIAN Symposium on Discrete Algorithms (SODA), 2025.
[6] Nikhil Bansal and Christian Coester. Online metric allocation and time-varying regularization. In 30th Annual European Symposium on Algorithms (ESA 2022). Schloss Dagstuhl-Leibniz- Zentrum für Informatik, 2022.
[7] Shai Ben-David, Allan Borodin, Richard Karp, Gabor Tardos, and Avi Wigderson. On the power of randomization in on-line algorithms. Algorithmica, 11:2-14, 1994.
[8] Garrett Birkhoff. Tres observaciones sobre el algebra lineal. Univ. Nac. Tucuman, Ser. A, 147-154, 1946.
[9] Avrim Blum and Carl Burch. On-line learning and the metrical task system problem. In Proceedings of the tenth anmual conference on Computational learning theory, pages 45-53, 1997.
[10] Avrim Blum, Howard Karloff, Yuval Rabani, and Michael Saks. A decomposition theorem for task systems and bounds for randomized server problems. SIAM Journal on Computing, 30(5): 1624-1661, 2000.
[11] Allan Borodin and Ran EI- El-ia..v. Online computation and competitive analysis. cambridge university press, 2005.
[12] Allan Borodin, Nathan Linial, and Michael E Saks. An optimal on-line algorithm for metrical task system. Journal of the ACM (JACM), 39(4):745 -633,,5--7677-7 1992.
[13] Sébastien Bubeck, Michael B Cohen, Yin Tat Lee, James R Lee, and Aleksander Madry. K- server via multiscale entropic regularization. In Proceedings of the 50th annual ACM SIGACT symposium on theory of computing, pages 3-16, 2018.
[14] Sébastien Bubeck, Michael B Cohen, James R Lee, and Yin Tat Lee. Metrical task systems on trees via mirror descent and unfair gluing. SIAM Journal on Computing. 50(3):909-92) 2021.
[15] Sébastien Bubeck, Christian Coester, and Yuval Rabani. Shortest paths without a map, but with an entropic regularizer. In 2022 IEEE 63rd Annual Symposium Foundations of Computer Science (FOCS), pages 1102-1113, IEEE, 2022.
[16] Sébastien Bubeck, Christian Coester, and Yuval Rabani. The randomized k-server conjecture false! In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pages 581-594, 2023.
[17] Niv Buchbinder, Joseph Seffi Naor, et al. The design of competitive online algorithms via primal-dual approach. Foundations and Trends in Theoretical Computer Science, 3(2-3): 93-263, 2009.
11

---

[18] Niv Buchbinder, Shahar Chen, Joshep Seffi Naor, and Ohad Shamir. Unified algorithms for online learning and competitive analysis. In Conference on Learning Theory, pages 5-1. JMLR Workshop and Conference Proceedings, 2012.
[19] Lin Chen, Qian Yu, Hannah Lawrence, and Amin Karbasi. Minimax regret of switching- constrained online convex optimization: No phase transition. Advances in Neural Information Processing Systems, 33:3477-3444 2020.
[20] Jakub Chledowski, Adam Polak, Bartosz Szabucki, and Konrad Tomasz Zolna. Robust learning- augmented caching: An experimental study. In International Conference on Machine Learning, pages 1920-1930. PMLR, 2021.
[21] Nicolas Christianson, Junxuan Shen, and Adam Wierman. Optimal robustness-consistennyy tradcoff's for Gaaming-augmmett metrical task systems. In International Conference on Artificial Intelligence and Statistics, pages 9377-9399. PMLR, 2023.
[22] Christian Coester and James R Lee. Pure entropic regularization for metrical task systems, In Conference on Learning Theory, pages 835-848. PMLR, 2019.
[23] Romain Cosson. Breaking the k/log barrier in collective exploration via tree-mining. In Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithmss (SODA), pages 4264 4282. SIAM, 2024.
[24] Romain Cosson and Laurent Massoulié. Collective tree exploration via potential function method. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Schloss- Dagstuhl-Leibnizz Zentrum für Informatik, 2024.
[25] Romain Cosson, Laurent Massoulié, and Laurent Viennot. Efficient collaborative tree explo- ration with breadth-fing first depth-next. In 37th International Symposium on Distributed Computing (DISC 2023). Schloss Schloss-Dagstuhl- Shgsstull-Leibizz Zentrum für Informatik, 2023.
[26] Amit Daniely and Yishay Mansour. Competitive ratio regret minimization: achieving the best of both worlds. Algorithmic Learning Theory, pages 333-368. PMLR, 2019.
[27] Dariusz Dereniowski, Yann Disser, Adrian Kosowski, Dominik Pajak, and Przemystaw Uz- nański. Fast collaborative graph exploration. Information and Computation, 243:37-49 2015.
[28] Michael Dinitz. Sungjin Im, Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Algorithms with prediction portfolios. Advances in neural information processing systems, 35: 20273-20286, 2022.
[29] Stefan Dobrev, Rastislav Královič, and Dana Pardubská. How much information about the future is needed? In International Conference on Current Trends in Theory and Practice of Computer Science, pages 247-258. Springer, 2008.
[30] Yuval Emek, Pierre Fraigniaud, Amos Korman, and Adi Rosén. Online computation with advice. Theoretical Computer Science, 412(24):642-2666 2011.
[31] Leah Epstein, John Noga, Steve Seiden, Jifí Sgall, and Gerhard Woeginger. Randomized on-line scheduling on two uniform machines. Journal of Scheduling, 4(2):71-92, 2001.
[32] Ofer Feinerman, Amos Korman, Zvi Lotker, and Cen--Sébsttien Sereni. Collaborative search on the plane without communication. In Proceedings of the 2012 ACM symposium Principles of distributed computing, pages 77-86, 2012.
[33] Amos Fiat and Manor Mendel. Better algorithms for unfair metrical task systems and applica- tions. In Proceedings of the thirty-second annual ACM symposium on Theory of computing. pages 725-734, 2000.
[34] Pierre Fraigniaud, Leszek Gasieniec, Dariusz R Kowalski, and Andrzej Pelc. Collective tree exploration. Networks: An International Journal, 48(3):166-177 2006.
[35] Gautam Goel, Yiheng Lin, Haoyuan Sun, and Adam Wierman. Beyond online balanced descent: An optimal algorithm for smoothed online optimization. Advances in Neural Information Processing Systems, 32, 2019.
12

---

[36] Brieuc Guinard and Amos Korman. Intermittent inverse-square lévy walks are optimal for finding targets of all sizes. Science advances, 7(15)xabe8211, 2021.
[37] Dennis Komm and Richard Královič. Advice complexity and barely random algorithms. RAIRO-Theoretical Informatics and Applications, 45(2):249-267, 2011.
[38] Elias Koutsoupias. The k-server problem. Computer Science Review, 3(2):105-118, 2009.
[39] Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. In Annual symposium theoretical aspects of computer science, pages 404-413. Springer, 1999.
[40] Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382 4011, 1982.
[41] Nick Littlestone and Manfred Warmuth. The weighted majority algorithm. Information and computation, 108(2):212-26) 1994.
[42] Neal Parikh, Stephen Boyd, et al. Proximal algorithms. Foundations and trends@ in Optimiza- tion, 1()):127-239, 2014.
[43] Shyam Sundhar Ramesh, Pier Giuseppe Sessa, Andreas Krause, and Ilija Bogunovic. Movement penalized bayesian optimization with application wind energy systems. Advances Neural Information Processing Systems, 35:27036-27048, 2022.
[44] Nick Reingold, Jeffery Westbrook, and Daniel D Sleator. Randomized competitive algorithms for the list update problem. Algorithmica, 11(1):15-22, 1994.
[45] Filippo Santambrogio. (Euclidean, metric, and Wasserstein) gradient flows: an overview. Bulletin of Mathematical Sciences, 7:87-154, 2017.
[46] Steve Seiden. Unfair problems and randomized algorithms for metrical task systems. Informa- tion and Computation, 148(2):219-244 1999.
13

---

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

---

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

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /otee//guudddeeeedSuuuubmiibii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
16

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpp:////arrpps..coooooo///hhht
Answer: [Yes]
Justification: The results of the paper are of theoretical nature, and the NeurlPS Code of Ethics was respected.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
The paper discusses possible applications of our methods to dynamic power management.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
17

---

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

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
19


Reviews:
[{"review_id": "AHKP8XGOgk", "reviewer": "Reviewer_DDub", "summary": "The paper bounds the randomness required to achieve the asymptotically tight randomized competitive ratio for metrical task systems, a fundamental model of online computing (essentially, prediction with expert advice endowed with a metric cost function for switching among experts). It shows that $2\\log n$ random bits (where $n$ is the number of states/experts of the system) are sufficient to achieve a competitive ratio that is within a factor of $2$ of the optimal ratio (which is known in general to be $\\Theta(\\log^2 n)$, though for some metrics $O(\\log n)$ is achievable). It also shows a nearly matching lower bound of $\\log n$ bits. The main result, the upper bound, is a rather simple and elegant reduction that transforms any randomized competitive algorithm to a ``barely fractional\" algorithm (which uses a finite set of probabilities that are all multiples of $1/n^2$), which in turn implies a ``barely randomized\" algorithm. The reduction is not trivial as simple rounding to the nearest multiple of $1/n^2$ probability vector gives very poor performance. Hence, a more sophisticated rounding scheme is employed, where instead of optimizing the distance between the fully randomized algorithm's probabilistic position to the rounded position, one factors in a smoothed version of the rounded position (averaging between it and a uniform distribution), and the switching cost of the rounded algorithm.", "questions": "None.", "limitations": "None.", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Metrical task systems are a widely acknowledged fundamental model of online computing. The question is a fundamental question in online computing. The result answers a fundamental question in online computing. It show in particular that the amount of randomness needed is independent of the input sequence length. This has implications to advise assisted online computing, and to multi agent online computing.", "weaknesses": "It's a simple idea and a simple proof, though that's not necessarily a weakness.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their encouraging review!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "98Nq46tjQ9", "reviewer": "Reviewer_stvh", "summary": "Authors study randomized algorithms for Metrical Task Systems (MTS)\nwhich need only a small number of random bits which, in particular,\ndoes not depend on the length of the time horizon.\nThey also interpret this in terms of an average performance of\na cooperating group of several deterministic algorithms\nand in terms of advice complexity of reaching the performance\nof the best randomized algorithms for MTS using a deterministic algorithm.\nTheir main result is a reduction which can turn any alpha-competitive\nrandomized algorithm for MTS into a 2alpha-competitive algorithm\nwhich uses only 2*log n random bits.", "questions": "* advice complexity of MTS was already studied, you may want to add missing references,\ne.g. Emek et al. Would be helpful for the reader to compare the regime of their results to yours.\n\n* at lines 82,83, there is a repeated word \"tight\"\n\n* Acquiring random bits sometimes limits usability of randomized algorithms. Caching would be one\nexample. Can you give an example of a concrete MTS where your method could ease\nimplementation of randomized algorithms?", "limitations": "Explained well in statements of the results.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* Proposed results are very interesting. I even find them surprising.\n\n* MTS is one of the central problems in online algorithms. It is extensively\nstudied in terms of randomized and deterministic algrithms as well as advice\ncomplexity. The paper brings interesting and novel point to the literature on MTS.\n\n* The proposed result connects several distinct views of the problem:\ncollective algorithms, barely random algorith, advice complexity.\nI appreciate the way authors explain this context.\n\n* presentation of the results is clean and elegant.", "weaknesses": "* No upper bounds for $k < n^2$. This is a mild weakness, I consider the\npresented results strong enough.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their constructive feedback and suggestions. We answer the reviewer's questions below.\n\n* The reference \"Online Computation with Advice\" by Emek et al. pointed out by the reviewer is very relevant and will be added to the paper: Emek et al. study the situation where $b$ bits of advice are provided at each time-step to a deterministic MTS algorithm, for $b$ of order $\\log n$. The total amount of advice in this reference is therefore of order $B = \\Theta(\\log n*T)$, where $T$ is the number of time-steps. One surprising consequence of our results (Corollary 1.4) is that we present a deterministic MTS algorithm that has a competitive ratio of $O(\\log^2 n)$ using a *single* advice of total size $B = 2\\log n$, i.e. $B$ is now independent of the number of time-steps $T$. As suggested by the reviewer, we will add a brief discussion on this matter in the revised version of the paper.\n\n* As the reviewer points out, we also provide a randomized algorithm which requires very few random bits (again, $B= 2\\log n$, independently of the input size). The method is therefore helpful in any setting where acquiring random bits is costly. In concrete implementations, we also expect that barely fractional configurations (which are discrete objects) are generally much more practical to handle for computers than fully fractional configurations (which are arbitrary real numbers). But perhaps the most applied consequence of our results is that a deterministic team of k agents can be competitive in a way that no single agent could be (provided that $k\\geq n^2$). This has for instance a very direct implication in energy management [2]. Consider a computer with three energy modes (*on*, *sleep*, *off*) with a switching cost of $1$ between *on* and *sleep* and another switching cost of (say) $5$ between *sleep* and *off*. At each time $t$ the request is either that \n   * the computer is used: in which case $c(t) = (1, +\\infty, +\\infty)$ so the computer must be in state *on* ; or \n   * the computer is not used: in which case $c(t) = (1, 0.5, 0)$ so the computer would rather be *off* than *sleep*, and *sleep* than *on*. \n  \n  This simple setting was presented by S. Bubeck to motivate the relevance of MTS in a series of lectures in 2019 (Five miracles of mirror descents, available on Youtube). Consider the variant of the problem, where the computer is in fact composed of $k = 9$ components (e.g. screen, CPU cores, etc.) that can each individually switch between one of the three modes (*on*, *sleep*, *off*). The energy spent by the computer is the sum of energy spent by its constituents. Since $n=3$ and $k > n^2$, our results imply that this system can enjoy the randomized competitive ratio (up to a factor 2) against a deterministic adversary! \n\n* Typos will be corrected.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Fx30o3P80e", "reviewer": "Reviewer_Kc9y", "summary": "The current paper addresses the problem of metrical task systems on a general space with $n$ points and proposes a technique to reduce the amount of randomness used by any random algorithm. More precisely, the authors prove that any \"fully random\" algorithm, which uses an unlimited number of random bits, can be transformed into a \"barely random\" algorithm that uses only $\\lceil 2 \\log n \\rceil$ random bits, with a competitive ratio at most twice as large. An immediate consequence of this result, using previous works, is the existence of an $O((\\log n)^2)$-competitive algorithm that uses only $\\lceil 2 \\log n \\rceil$ random bits. The authors also show that any $O((\\log n)^2)$-competitive algorithm requires at least $\\log n - O(\\log \\log n)$ random bits, essentially proving the tightness of their main result.", "questions": "Do the authors think that some arguments and techniques from the paper can be used to prove similar results on barely random algorithms in other problems in competitive analysis?", "limitations": "The assumptions of the theoretical results are clearly stated.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "* The results of the paper are interesting and may inspire future work in similar directions.\n* Viewing the problem as a collaborative MTS with $k$ deterministic agents provides better insights and understanding of the problem.\n* The paper introduces new analysis techniques that could have broader applications.", "weaknesses": "I don't see any major weaknesses in the presented results or the proofs.\n\nHowever, I find that the paper is not a good fit for NeurIPS at all. A conference or journal focused on theoretical computer science would be a much better venue for this work and would provide it with greater visibility among researchers who are more likely to benefit from it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their interest and their careful reading. We note that the reviewer's appreciation of our results seems very positive, and that their only concern is whether the paper is a good fit for NeurIPS. We attempt to convince the reviewer that this is indeed the case, in the hope that they would increase their rating in a way that reflects their appreciation of the paper's inherent quality.\n\nWhile metrical task systems (MTS) is a problem that originated in the 1990s from the community of theoretical computer science (TCS), we observe that in the last 5 years the problem has gained a strong interest in the machine learning community, with many contributions on *learning augmented algorithms* [1,17,2,18,3] and on *concrete applications* of MTS [37, 25]. Most of these papers were published at NeurIPS.\n\nWe note that our work has a flavor that is very similar to *learning-augmented algorithms*. Learning-augmented algorithms use predictions coming from a black-box algorithm, in the hope to improve over the performance of competitive algorithms when predictions are accurate. In a similar fashion, our method tracks a fully fractional configuration seen as coming from a black-box algorithm, and makes it barely fractional in a competitive way. We therefore expect our methods could be relevant to researchers working on learning-augmented algorithms, for instance when they need to interpolate smoothly between black-box configurations coming from one or many predictors. \n\nOur work is also motivated by *concrete applications*. The method we propose is very easy to implement and can be applied to concrete problems such as dynamic power management [2], distributed systems [30,21] or asset management (Remark 2.3). For a very immediate example of an application of our work to a power management problem, we encourage the reviewer to read the second item of our response to **Reviewer stvh**. \n\nThe result on the existence of a barely random algorithm for MTS has indeed a theoretical flavor. But it is only one of the consequences of our analysis. Our results also imply for e.g. that a deterministic (finite) team of agents can be competitive in a way no single agent can be – which echoes of the study of intelligence in multi-agent systems. A totally different interpretation of our results is in advice complexity (Corollary 1.4) a subject which is very connected to learning-augmented algorithms. For more details on this aspect of the paper, we encourage the reviewer to read the first item of our response to **Reviewer stvh**. \n\nBefore submitting this paper to NeurIPS, we carefully verified the \"NeurIPS 2024 Call for Paper\" which lists the topics in the scope of the conference. We felt that our paper falls entirely within the scope described by this document (specifically, at the intersection of Theory, Optimization and Online Machine Learning). We encourage the reviewer to check these guidelines when finalizing their rating.\n\nFinally, we understand and truly appreciate the intent of the Reviewer to make the results of the paper known to the TCS community. We will not miss other opportunities (workshops, seminars or other submissions) to engage with this community as well, in the hope to develop application-driven and theoretically-grounded works for online settings.\n\n* Regarding the reviewer’s question, we believe that our techniques could help to prove new results for other online problems (such as k-servers or metrical service systems), even though there is no immediate reduction.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "3q0hyvhAUh", "reviewer": "Reviewer_1Eyx", "summary": "This paper introduces and studies the problem of designing and analyzing randomized algorithms for Metrical Task Systems (MTS) using only limited randomness, that is, a number of random bits that only depends on $n$ (the number of states in the MTS), rather than the length of the sequence, as in the case of the known SOTA randomized algorithms. The main result of the paper shows that $2\\log n$ random bits suffice to achieve the same competitive ratio as the best fully randomized algorithms, up to a factor of 2. This is near-optimal, as shown, in the sense that $\\log n-O(\\log \\log n)$ bits are necessary to this end. The barely-random setting with $k$ random bits also yields directly a solution to a {\\em collective} MTS setting, in which, informally, $k$ algorithms are run in parallel, and the cost paid is the average of the cost of the $k$ algorithms. This collective setting is motivated by similar in spirit works on graph exploration in distributed settings, with $k$ parallel agents.  The approach builds on a fractional formulation of the online problem, and techniques from optimal transport theory, such as the Birkhoff-von Neuman theorem, instead of the standard tree embedding techniques.", "questions": "Is the use of optimal transport theorem novel in the competitive analysis of MTS problems?\n\nFor the setting of Remark 2.3, is this application known in the literature, or you define it? \n\nIn Section 3 it would be good to have the statement of the algorithm in rough pseudocode.\n\nline 400: Can you expand on these similarities with descent methods?\n\n\nOther comments:\n\nlines 141-148: please add appropriate citations throughout. \n\nI assume the reason behind the proof of Proposition 2.1 is to give intuition about the more complex setting? If yes please make this clear. \n\nline 203: typo \"achieves\". \n\nline 280: This is the potential function, but it is hidden, please make it more prominent.", "limitations": "No issues in regards to limitations.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper is very well written. All results are rigorously proven, but there is also a lot of intuition and high-level guiding of the reader.\nThe solution is non-trivial and builds on fairly complex ideas.  Furthermore, even though the work is theoretical, it is connected to concrete applications. \n\nThe idea of using concepts from optimal transport theory looks novel, although I am not familiar with its application to other online problems via competitive analysis.", "weaknesses": "There is no experimental analysis. It is understandable that the work is mainly theoretical, but one suggestion would be to expand on the application discussed in Remark 2.3 and include an experimental evaluation of this problem.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for their interest and their thoughtful questions.\n\n* To the best of our knowledge, the use of the Birkhoff-von Neumann theorem in the context of competitive analysis is new. We build upon this theorem in Proposition 2.2 of Section 2.2. As the reviewer points out, the purpose of Proposition 2.1 (which is well-known in the literature) is just to give more intuition on the more complex setting. We will highlight this in the revised version of the paper. The other key novel technical part of our analysis is in Section 3 where we develop a first-order method that displays a *hysteresis phenomenon* to track a fully fractional configuration with a barely fractional configuration. This shows the existence of $O(\\log^2 n)$-competitive barely fractional configurations, which in turn has implications for randomized algorithms, collective algorithms and advice complexity. \n\n* The application suggested in Remark 2.3 is quite natural: since our algorithm only moves significant amounts of mass, it is not sensitive to (small) fixed transaction costs ; this comes in contrast with fully fractional algorithms, because they move arbitrarily small amounts of mass. We believe that this application is also new and was out of reach for previous methods. \n\n* As suggested by the reviewer, we will add a (very short) pseudocode to highlight the simplicity of our method.\n\n* Section 3 is reminiscent of offline first order optimization in many ways. Gradient descent of a function $f(\\cdot)$ is also known as the explicit Euler method, where one can write the $t+1$-th iterate of the method as the minimizer of the sum of the first order approximation of $f(\\cdot)$ at the previous iterate and a quadratic cost, i.e.\n\\begin{align} x(t+1) = \\arg\\min_x \\nabla f(x(t))(x-x(t)) + ||x-x(t)||^2.\n\\end{align}\nA very closely related method is the implicit Euler method where the $t+1$-th iterate is the minimizer of the sum of $f(\\cdot)$ and a quadratic cost, \n\\begin{align}\nx(t+1) = \\arg\\min_x f(x) +||x-x(t)||^2, \n\\end{align}\nwhich is also known as the Proximal operator. Our Equation (2) is reminiscent of this Proximal operator, which has important stability properties. One key difference is that we replace the squared norm by an optimal transport cost, and that the offline objective function $f(\\cdot)$ is replaced by a potential which is defined online. Note that quite recently, the notion of Wasserstein proximal operator has also appeared as a central object of study in the context of diffusion and partial differential equations (see e.g. the review of Santambrogio on Gradient Flows). A key difference with our Equation (2) is that we consider the Wasserstein-1 metric (aka, the earthmover distance) and not the Wasserstein-2 metric. We will add a discussion on the reviewer's question in the final version of the paper.  \n\n* If the reviewer is satisfied with the novelty of our method, and with the proposed revisions, we kindly encourage them to positively reassess their rating of the submission. \n\n* We will correct all typos, put more emphasis on the potential function and add citations in lines 141-148.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their interest, their careful reading, and their feedback to improve the paper.

We quote all four reviewers who unanimously appreciated the content and the presentation of the paper:
* **Reviewer Ddub**: "The result answers a fundamental question in online computing." 
* **Reviewer stvh**: "Proposed results are very interesting. I even find them surprising." "Presentation of the results is clean and elegant." 
* **Reviewer 1Eyx**:  "The paper is very well written." "The solution is non-trivial and builds on fairly complex ideas."
* **Reviewer Kc9cy**: "The paper introduces new analysis techniques that could have broader applications."

**Reviewer Kc9cy**, whom we thank for their valuable point of view, suggested borderline rejection not on the foundation of the paper’s merits, but because they question its relevance to the publishing venue. Specifically, the reviewer says that the paper would have more impact if it were published in the computer science community. We reply in detail to **Reviewer Kc9cy**, explaining why the present paper can appeal to many researchers attending NeurIPS 2024 and, more broadly, to the online machine learning community.

We also answer the questions of **Reviewer stvh** and **Reviewer 1Eyx** in the hope of alleviating any remaining doubts.

Meta-review: This paper presents fundamentally new ideas for an important and well-studied problem.  The reviewers particularly found the ideas to be accessible and understandable.  Together, this makes for a paper with good deep results that are accessible to the community, despite their technical depth.
Decision: Accept (spotlight)