A Mean-Field Game Approach to Cloud Resource Management with Function Approximation
Authors: Weichao Mao
Haoran Qiu
Chen Wang
Hubertus Franke
Zbigniew Kalbarczyk
Ravi Iyer
Tamer Basar
Venue: NeurIPS 2022 Accept (2022)
Keywords: Mean-field game
reinforcement learning
serverless computing
resource management

Abstract: Reinforcement learning (RL) has gained increasing popularity for resource management in cloud services such as serverless computing. As self-interested users compete for shared resources in a cluster, the multi-tenancy nature of serverless platforms necessitates multi-agent reinforcement learning (MARL) solutions, which often suffer from severe scalability issues. In this paper, we propose a mean-field game (MFG) approach to cloud resource management that is scalable to a large number of users and applications and incorporates function approximation to deal with the large state-action spaces in real-world serverless platforms. Specifically, we present an online natural actor-critic algorithm for learning in MFGs compatible with various forms of function approximation. We theoretically establish its finite-time convergence to the regularized Nash equilibrium under linear function approximation and softmax parameterization. We further implement our algorithm using both linear and neural-network function approximations, and evaluate our solution on an open-source serverless platform, OpenWhisk, with real-world workloads from production traces. Experimental results demonstrate that our approach is scalable to a large number of users and significantly outperforms various baselines in terms of function latency and resource utilization efficiency.

A Mean-Field Game Approach to Cloud Resource Management with Function Approximation
Weichao Mao
Haoran Qiu
University of Illinois Urhmna-Champaign weichao2011linoi. edu
University of Illinois Arbana-Champar haorang48illinos edu
Chen Wang
Hubertus Franke
Zbigniew Kalbarezyk University of Illinois Srbana-Champae
IBM Research chen. wang1 10ibm. bm. com
IBM Research frankeh@us imm. com
kalbarcz0illinois edu
Ravishankar K. Iyer
Tamer Başar
University of Illinois Urbana-Champaigg rkiyer@illing edu
University of Illinois Urbana-Chann Chaan--Champaign basar @illinois inois.edu
Abstract
Reinforcement learning (RL) has gained increasing popularity for resource man- agement in cloud services such as serverless computing. As self-interested users compete for shared resources a cluster, the multi-tenancy nature serverless plat- forms necessitates multi-agent reinforcement learning (MARL) solutions, which often suffer from severe scalability issues. In this paper, we propose a mean mean-field game (MFG) approach cloud resource management that is scalable large number of users and applications and incorporates function approximation to deal with the large state-action spaces in real-world serverless platforms. Specifically, we present an online natural actor-critic algorithm for learning in MFGs compati- ble with various forms of function approximation. We theoretically establish its finite-time convergence to the regularized Nash equilibrium under linear function approximation and sofumax parameterization. We further implement our algorithm using both linear and neural-network function approximations and evaluate our solution on an open-soure source serverless platform, Open Whisk, with real-worke work- loads from production traces. Experimental results demonstrate that our approach is scalable a large number users and significantly outperforms various baselines in terms of function latency and resource utilization efficiency.
Introduction
Serverless computing is an emerging cloud computing paradigm that allows users to develop and run their applications without worrying about the configurations of the infrastructure (containers or virtual machines) 33). In contrast to traditional cloud computing, serverless users only charged by the function execution time and their operational cost is reduced since the cloud provider takes care of the resource management (e.g., serverless function provisioning and scheduling) their behalf. The tension between cloud providers and users incurs a more complex resource management problem: The platform needs to meet various user-defined serverless function quality-of-sae of-service (QoS) guarantees while the provider aims to keep the cluster resource utilization at a high level in the face of elastic have been
and bursty function requests. Numerous heuristics-based solutions (e.g.. (64 67 69
We focus on Function-as aasioon--s----eeee as-----vic-- (FaaS), which is the most common serverless service in cloud computing.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

utilized, yet they inevitably rely on extensive system- seeeefi-ecccficccco domain knowledge and painstaking tuning for specific workloads.
Recently, reinforcement learning (RL) based approaches have attracted increasing attention for dynamic resource management RL helps automatically adapt to a specific user workload. Each function is managed by an RL agent, leaving human operators out of the loop. The fact that large- scale cloud computing platforms have many users with independent (and sometimes conflicting) requirements adds another layer of complication for serverless function resource management. Since functions from multiple self-interested users coexist and compete for shared resources in a cluster, cloud providers further need to take into account the potential strategic behavior of the users. The aggent reinforcement learning (MARL) paradigm [39] especially well-suited here, as naturally integrates game-theoree theoreettat thinking into the sequential decision- decision-making problems of multi- agent systems. However, well-known challenge in multi-agent reinforcement learning is scalability, as many MARI. algorithms suffer from exponential computation & sample complexity in the number of agents, a phenomenon known as "the curse of multiagents"
32 65 19 42 18] The scalability
bottleneck needs to be properly addressed before applying MARL to real-world cloud serverless
platforms, which typically involve a large number of users and functions in a cluster M.
To circumvent the scalability challenge, we resort to the mean-field approximation 37 30 and
propose scalable mean-field game (MFG) approach to cloud resource management. The under- lying principle of MFGs is to approximate the finite-agent game with an anfinite-popllati where each agent's influence on the overall system becomes infinitesimal. In an MFG with infinite homogeneous agents, the collective behavior of all the agents can be effectively summarized as population distribution, which is usually specified as the empirical distribution of the agents' states. Such an approximation leads to tractable solution to the otherwise challenging MARL problem, as each agent no longer needs to keep track of the historical behavior of every other agent to reason about their internal information, which typically incurs prohibitive combinatorial complexity. Exist- ing theory [54] also shows that the approximation scheme does not lose much of optimality when applying the policies learned from the infinite-agent game back to the original finite-population game.
limit,
However, the convergence of learning algorithms in MFGs has been chiefly established either in the tabular setting with small state & action spaces 66 28], or in the linear-quadrate case with structural assumptions on the system dynamics 23
73 Few results have considered function approximation in mean-field games with large (and even infinite) state & action spaces, which is the typical case for many real-world application scenarios including cloud computing. In this paper, motivated by the large state & action spaces in cloud resource management problems, we make initial attempt to understand the effects of function approximation in MFGs with generic system dynamics. While we believe that our proposed methodology is general enough to be applicable to a wide range of scenarios, we demonstrate the effectiveness of our approach in a real-world cloud resource management problem as important application domain.
Contributions. Our contribution is threefold: (1) Algorithmically, we propose a natural actor-critic (NAC) learning paradigm for MFGs that is compatible with various forms of function approximations. Our method is particularly practical due to an online property 78., in the sense that need not fix the mean-field state to calculate the best response at each iteration, but instead let the mean-field naturally evolve as the agents learn. (2) Theoretically, we establish the finite-time convergence of NAC with linear function approximation and softmax parameterization as a critical stepping stone. We prove that the resulting algorithm converges to the regularized Nash equilibrium (NE) of the MFG at an ((7-1/5) rate. (3) Empirically, we evaluate NAC on classic MFG benchmarks and demonstrate its convergence behavior. As important motivating example and test bench, also incorporate a practical variant of NAC (with both linear and neural-network function approximations) into the resource management module of an open-source serverless platform, Open Whisk [22]. Our experimental results on real-world production workloads show that NAC is scalable to a large number of agents in serverless resource management and significantly outperforms various baselines in terms of both function latency and resource utilization.
Related Work. Mean-field games have been introduced by 37 and 30 to study continuous-tim differential games with infinite identical agents. For discrete- time MFGs, the existence and/or uniqueness of the Nash equilibrium have been studied in 26 70, 45 54] The mean-field regime has been investigated under various settings, including games with quadraii structures (2, major and minor agents [77) partial observability [55], risk-sensitivity [56]. and so When

---

the environment dynamics are unknown, learning based algorithms are commonly used to learn [6], but most of these works rely on "double- loop" fixed-point iterative process that can lead to heavy reward fluctuations and are less practical.
the NE from data 80
73 23
28 20
74). , but they do not consider function approximation to deal with large state and action spaces, and [66] and [48] only yield asymptotic convergence guarantees. On the application side, learning algorithms in MFGs have been applied to economics [6] and animal behavior simulation [50), among others, while in this paper, we identify that large-scale cloud resource management is also an ideal application domain.
Our "single-loop" algorithm is most related to 78 66 48
Our work is also related to policy optimization in single-agent RL, especially natural policy gradient (NPG) methods [35]. For the tabular setting, the (global) convergence of NPG has been established in [1]. In particular, [2] has proved that unregularized NPG with softmax parameterization achieves an (1/TT) convergence rate, while [1] has further strengthened the result by showing linear convergence of NPG when equipped with entropy regularization. In the regime of function approximation, 22 has shown that NPG with linear function approximation and softmax parameterization attains a O(I/VT) convergence rate subject to some function approximation error. Our results are largely built upon [13], which has established a linear convergence when further exploiting entropy regularization. In particular, a standard "double-loop" mean-field approach will lead to setting very similar to that of [13] in the inner loop, because by fixing the population distribution, the learning agent effectively faces a single-agent problem. However, since such double- loop solutions are hardly practical, we instead consider online setting where the environment simultaneously evolves as the agents update their policies. The environmental non-stationarity adds another layer of complexity and makes [I3] not directly applicable. Going beyond linear function approximation, [76] has investigated NPG with over over-vvramenn parameterizeed two-layer neural networks, more powerful approximation scheme that is not theoretically pursued but only empirically evaluated in our work. It is also worth mentioning that many successful empirical algorithms, such as TRPO (58) and PPO 59 can be considered as natural variants of NPG.
a series of works 663 2 43 (79
RL-based resource management approaches 8 36 40 51 57 82 have been recently proposed to achieve efficient resource utilization and application quality service (QoS), which outperform base- line rulc-based methods. For instance, FIRM [5T] is an RL-based resource management framework for cloud microservices to tackle the under-utilization issue and QoS violations.
[57] has proposed a O-learning-basee autoscaler that decides the horizontal concurrency for a serverless function. FaaSRank (82) is RL-based serverless function scheduler that uses PPO [59] to assign function requests to available servers, yet both [57] and (82 only consider the objective of minimizing the function latency. Finally, existing works only consider single-agent RL approaches being trained and evaluated in an isolated environment, while the cloud is multi-tenant environment by nature.
2 Preliminaries
We first consider a classic Markov game with N agents. Each agent has a state space S and an action space A. At each time step f, the state of agent i [N] is denoted by st S, and the agent takes an action oj E A according to a certain policy. Given the current state profile 8; = (si..... s(") ), agent i receives reward determined by a reward function ('s,, a)), and transitions to a new state s441 ~ (- 8t, at)) according to a transition funetion P.. The goal of each agent is to find a policy that maximizes its expected cumulative reward over time. When N is large, learning in such an N-aaent Markov game with generic reward structure is known to be notoriously hard [55 18] Mean-field games [37 30, on the other hand, can be viewed as an infinite- population limit (N + oo)
of the finite-agent game, and provide a tractable approximation to the otherwise challenging problem.
A discrete-time mean-field game (MFG) considers an infinite-number of identical agents 30 The collective behavior of all the agents described by population distributon μ4 ASS), also termed a mean-field state, which in practice can be interpreted as the limit of the empirical state distribution,
i.., = = lim N Ei deg, where d, E A(S) is the Dirac measure at Due to the homogeneity of the agents. we focus on a single representative agent. At each time t, the (representative) agent's state denoted by 8, E S, and the mean-field state jrr describes the probability distribution of st. Upon taking an action a, E A at 8t, the agent receives reward r(st, (e: Mt), and transitions to new state 81+1 P(- St: 0t, (t), where r : Sx x A x A(S) - [0. 1] is the reward function and P. S AX A(S) A(S) is the state transition function. A (Markov) policy x S + A(A)
3

---

for the agent is mapping from the state space to a distribution over the action space, and we use to denote the set of all Markov policies. Given a population distribution flow μ (H))120-
E 7'r(st, at f&) so s] where a TT- st), S1+1 P(- St, Se, Me), and y (0, 1) is the discount factor. In the special case of a time-invariant mean-field, i.c., M4 = μ. Vt 2 0, we slightly abuse the notation and write V (s) as (s). For an initial state distribution p E (SS). we define the (discounted) state visitation
we define the value function of policy as V (s) E
distribution as d=(s) def (1 (1-3) Ei PP = & 8o ~ p), where P(s; s|su ~ p) is the probability that the state is visited at the t-th time step under policy л and mean-field j..
Entropy Regularization: We further consider an entropy-rese regularized value function by augmenting the standard reward objective with an entropy term of the policy. For a fixed mean-field state define
(T)A(s)
(8) def (s) + AH - E T' (r(se, Or. p)) - A log π (ae 8c)) 80 =
where A > 0 is a parameter that controls the level of regularization, H (s)
(-(ss=)) so s), and M((T(-|s)) - -aa <{ass) log I (a]s) is the Shannon en- E 1=== y tropy. Entropy regularization has been commonly used encourage exploration and avoid premature convergence to sub- sub-optimal near-deterministie policies (2 3]. In mean-field games, [5] has also shown that with regularization, the uniqueness of NE guaranteed under milder assumptions than the unregularized case. We define the soft Q-function and shifted Q-function, respectively, as
2% (s, a) del r(s, a. (u) + ((ea))()) [VA [V (s')], and (s, (s.a) = ( a) - A log (als))
which are related to V in the sense that (s) = Ba-n(-11) (110)1)01111 (s, a)]. For distribution P E ASS), with slight abuse of notation, we write (p) =.es P(s)
Policy Parameterization: We consider parametric policy classes. For each state-action pair (s, a). suppose there exists a d-dimensional feature mapping 6s.a E IR,, such that || S 1, Vs E S.a A. A commonly used policy class is softmax parameterization of the form
exp (fe(s. a))
ï To(a|s) = En'E exp (fo(s, :0 Rd
where 0 is a d-dimensional vector that parameterizes the policy, and fo is differentiable function that can be typically instantiated as a linear function or neural network. In Sections and we focus on "log-lineate linear form of (s(s, a) = 0 Φs.a; V(2 a) E S x A. We will also instantiate sa using neural networks later in Section [S] Function approximation helps deal with large state and action spaces, as the feature dimension is usually much smaller, i.e., d < [S]|_A, where [S| can even be infinite in practice. It is worth noting that a parametric policy class may not contain all Markov policies, i.e., II IL. Hence, we seek to do as well as the best policy in this class and obtain agnostic results.
policies that use linear function approximation, where fo takes the specific
Single-agent Policy Optimization. Given fixed mean- -held state μ4, the representative agent faces a single-agent policy optimization problem: max (s). which is equivalent to finding the (entropy-regularized) optimal policy for a single-agent Markov decision process (MDP) induced by μ.. It has been shown that the optimal policy is unique whenever X >> 0 25). Hence, we can use x denote the (unique) optimal solution the optimization problem, and define mapping
r ASS) + such that T3 (n) = T We refer to T as the policy optimization operator, which maps a mean-field state to the optimal policy z of the induced MDP.
Mean-field Dynamics. Since all agents follow the same policy π, can define another mapping T2 : X A(S) - A(S) to describe the evolution of the mean-field. Specifically, the mean-field dynamics operator 12 is defined by T2( ()) 4²t, where
p (.) = [ P( a, ()((s))(((()) da
Intuitively, I2 characterizes the next mean-field state, given the current mean-fiee state and the current policy adopted by all the agents. For notational convenience, we further introduce a composite mapping A A(S) - A(S) as (p) = (2)) n), which simply combines N and To.
Mean-field Equilibrium. In the following, we introduce the main learning objective of the paper.

---

For variance reduction purposes, Algorithm further subtracts bascline from the Q-function and Algorithm 1: Natural Actor-Critic for MFGs with Linear Function Approximation
Input: Initial mean-field state No, and regularization level parameter X; Initialize 0g <- 0;
3 for iteration 4- 0 to I do
que Tr. that satisfies Equation Policy evaluation: Calculate an Euntur-accurae estimate of of
using, e.g. Algorithm 2
5 Gradient estimation: Use de to calculate an Eactor accurate estimate we of the gradient
(using, e.g. Algorithm 3 such that || 2|2 S R for some R > 0, and Equation (3) holds;
Mean-field update: μ(++1 (1 3,)j + ( (t),, where 3r O
7 Policy update: 0e+1 + 02 Tr9t. where 9r = ih A0,, and 1). = O 2/6)///
Definition 1. A policy-population pair (T* n²)) II x A(S) is stationary (time-independer) entropy-regularized Nash equilibrium for the mean-field game if it satisfies: (1) Rationality: x (""",, and (2) consistency: p² =22 )
When À= = O, the above definition reduces to that of the standard (unregularized) NE in MFGs S4 28 For 0, the regularized NE (I* ,²") also serves as good approximation of the unregularized one, as characterized by the following error bound [4] (established using the fact that H (s)
< log LAI
(p) S / (p) + Alog AA]
Vi (p) S max VT Tell
When the composite mapping A is contraction, theorem) that the regularized NE exists and is unique (5]. Accordingly, the policy-population pairs
can show (using standard Banach-fixed point
{(Te, (4) :t 2 0} given by the simple iterates ग. <- (p)) and M4+11 <- T2( mt) converge the regularized NE at linear rate, assuming that the exact optimal policy can be computed for rt.
3 Natural Actor-Critic for MFGs with Function Approximation
In this section, present an online natural actor-critic (NAC) algorithm with function approximation learn the regularized NE of a mean-field game (Algorithm[I) [p. Four major steps are involved: policy evaluation, gradient estimation, mean-field update, and policy update.
For the policy update step, policy gradient methods improve the policy parameter by ascending along the direction of the gradient of the policy, i.e., VoV A direct extension of the policy gradient theorem 688 shows that the policy gradient with antropy-regularizatin can be expressed as
1 VaV I-7 Ea (awr(( V log
(s,a))
Compared with the "vanilla" policy gradient method that follows the steepest direction in the parameter space, the natural policy gradient (NPG) approach [35] proceeds along the steepest direction with respect to the Fisher metric. NPG has the advantage of being invariant to the parameterization of the policy
follows more direct path to the optimal solution. For policy No parameterized by 8, NPG (35 defines a Fisher information matrix under policy To as:
4 and enjoys faster convergence
Vo log (a]s) s) (V log no (als)) ]] NPG then performs gradient updates along the steepest direction induced by this matrix: 0 + 0 + V (p), where is the learning rate, and (F*)t denotes the Peoorse pseudoinverse of F.. Leveraging the notion of compatible function approximation, it can shown that the above update rule can be equivalently expressed as (see (35 for proof of the unregularized case and [13] for the regularized counterpart) 0 < f + 1- S. where w is a minimizer of the following regression problem:
F = -E -E
w E argmin L(w, 0), where T(w,0) 0) def Bedd (a)m)(-11s) (w Vo log mo(als) - -
(s, ())
wERd
5

---

solves a variant of the regression problem at the t-th iteration instead:
We E argmin L(w,68 01), where L(w, 0) E B a-)))()))) (w Ve Ve log - A., a))
WER+:|lull2
= 2f as) Ea' - 10 (s, I'),, and R >> 0 is the gradient clipping radius. Since the target function may not be perfectly represented by a linear function, we use the function approximation error Fapprox to denote the minimal possible error for our parametric class
where A (s. (
Eapprox
sup (20 WE -|]ll,,
min L(w, Oe).
In practice, the values of A and wi in the above regression problem cannot be calculated precisely and need to be computed from a finite number of samples, which further introduce statistical errors (or excess risk). In particular, we use the policy evaluation step 4f Algorithm I to compute def an approximation qi of the shifted Q-function oT. where T. nT, denotes the policy at the t-th iteration of Algorithm I and we apply the gradient estimation step (Line 5 to further use g to calculate a gradient estimate viy, For ease of presentation, in this section, we will assume that we can obtain the estimated values e/² and tiy from two black-box oracles. Appendix C] we show that such oracles can be accomplished by standard sample-based estimation techniques. Specifically, we assume for now the existence of policy evaluation oracle that returns an estimate o such that
E Bendit awm..
(a (s,4) - Upee Re.d (0, a))²} S Ecritics
(2)
for some critic enror Eaiii 2 O. Let (s, (s,, a) + A log (als), and A) = -/ (s, ( 1Q, a')]. We further assume that a gradient estimation oracle provides an estimate dh
Eg (1.
that satisfies:
E
(nt V Vlogm, (/ -min
min E (w0 (logm((ass) - S Eatoors
(3)
for some actor error Eactor 2 O, where the expectation is over di and a (T(-)s). Ecritic and Eactor together represent the statistical error that can be driven to 0 when we have more samples, while Eupprox accounts for the inherent modeling error due to the potential lack of expressiveness of the parametric policy class. We further use Gooaal
Eapprox + cactor + Caitic to sum up all sources of errors.
final remark on the policy update step is that we adopt the idea of gradient averaging from 13 to encourage exploration. Specifically, the parameter update in Line T is effectively 0.+1 + (1 Te, + TıA 2x, which can be viewed as a convex combination of 0, and w,/A. Since our gradient estimation step "clips" the gradient estimate ensure that || I R for some R > 0 (Line 5), we can show by induction that the policy parameter is uniformly bounded, i.c., |00:112 S R/ X, vt 2 Together with the softmax parameterization of the policy, this condition ensures that our policy always explores the action space with some positive probability; that is, there exists Pmiin > O, such that Te (als) Z Punin: Vt 2 0, (s, a) E S A. Such a property is essential in establishing the convergence of the policy. See Lemma in Appendix for formal treatment.
In each iteration of the algorithm, we update the mean-field state (Line 6 as Pr-1 (1 -1-13 3.) 3.T2(T,, Mt). which can be considered as a "soft" step of mean-field evolution along the direction of T2( (4) with step size 3.. Similar existing works [66] 28 73 78 this step assumes access to a simulator that returns the new population distribution given the current mean-field and policy. In practice, one can approximate the simulator by estimating the new population distribution through randomly sampling the actual states of a large number N of agents, which incurs an estimation error O(1/VN) that decays as more agents are sampled [78].
Following (78), our algorithm enjoys the additional advantage of being online (also termed "learning while playing" in (78). in the sense that it lets the mean-fiel simultancously evolve as the agents play. Specifically, we perform only single step of policy update for each iteration of mean-field evolution, instead of computing the exact optimal policy with respect to the current mean-field. This achieved by carefully tuning the step sizes of the policy update (ne s T 225)) and mean-field
II has been shown that the approximation error is 0 for the realizable cases such as tabular (finite state-action)
MDPs or linear MDPs (3I) where the value functions are linear in the given features.

---

update (3₁ = 4/6) so as to let the policy converge at faster timescale than the mean- field does.
Our online approach in sharp contrast the "double-loop" methods [23 28 5 have to fix the mean-field state as an outer loop and use an iterative process as the inner loop to learn an optimal policy with respect to each fixed population distribution, which can be more time consuming and incurs oscillations in the learned policies (as evidenced by our simulations).
20
49
27 that
4 Convergence Analysis
In this section, we theoretically establish the convergence the natural actor-critic algorithm with linear function approximation to the regularized Nash equilibrium (л* ,x*) of the mean-field game. Our analysis follows the analytical framework of [78] for the tabular case. We start by introducing few notations. For any & 2 O, we use nī to denote the optimal policy of the representative agent with respect to the mean-field state (4,, i.e., क = (14)) Let di def dic be the visitation distribution of मे under yt,, and d' def di. be the one induced by the NE (r"",")), Our first result establishes the improvement of the policy under natural actor-critic updates in terms of the KL divergence. All missing proof's are deferred to Appendix B
Lemma 1. (Policy improvement). For any time L. 2 O. the policy update 0c+1 1 = 02 negh with softmax parameterization and linear function approximation leads to the following policy improvement:
Ex-dy [KL(z] (+15))](++ (+1))] S(1 neA)lEs-d; [KL (+s))]] [+[ss] Ty. n1:la-d; [V [V (s)]
1 amm (-1a) [9] T V lals.(als) - (s, (x,a)) + zn 11
The proof follows from the performance difference lemma 34 in the regularized case and the smoothness of log na (als). Similar results have also been shown in [3 78). To proceed further, we impose the following regularity assumptions on the visitation distribution.
Assumption 1. There exists constant de > O, such that for any mean-field states j and μl, the state visitation distributions under their corresponding optimal policies "t and n²' satisfy
||d - d=." 1|a S do [oy-11 -
Assumption 2. (Finite concentrability coefficients). There exist constants C1, Cz, C3 > O, such that for any t 2 0 and any encountered mean-field state Pb.
(s) .ss d' (s)
(s) (7(
27
d di
sup
< C1.
EE Eo-d;
<
C2 and EE grdd
S CG.
Assumption D states that the visitation distributions are smooth w.r. the mean fields, which is consistent with (78) and is reminiscent of the smooth visitation assumption for RL in non-stationary environments 211. Assumption 2 is standard assumption in policy optimization [34 63 2
78
I3
that captures the difficulty of strategic exploration by requiring the visitation distributions of certain policies to adequately cover that of optimal policy. Together with Lemma] [ these assumptions allow us to establish a recursive relationship of (L(TT (T))) over time (Lemma in Appendix B
To characterize the convergence of T., we use D(TT, x') 1 Esna [-|x(-|s) x' x((1s)]hk] as measure of distance between two policies. The following assumption is standard in the literature 28 73 78 16 that imposes the Lipschitzness of the two operators [ and I2 with respect to the D(..) metric.
Assumption 3. (Lipschitz Operators). There exist constants d, d2, da > O, such that for any policies म. n' and mean-field states p.p,, it holds that: (1) D (TT()), ( (x²)) di l| J Il1. [[ - I'2 (T', S d2D (T, r'), and (2) (TT (1) I'2 (IT, / I11 S da || 1'll
The first condition states that (1) and third conditions stipulate that I (T (1) is Lipschitz in each of its arguments when fixing the other. Assumption 3 immediately implies that the composite operator A is contractive when the Lipschitz constants are small enough (Lemma in Appendix(A) (A). We are now ready to state our main theoretical guarantees on the convergence of the policy-populatio sequence ((Te: (t) Je20 to the NE (T*, ,,²).
(u) is Lipschitz with respect to the mean-field state, and the second
Theorem Suppose that Assumptions
did2 - d3 > O, and the policy evaluation and gradient estimation oracles satisfy and (3) respectively. The policy-population
3 hold with d

---

302
Exphitabilty
Expattabllty
200
NAC
-200
4.00
100
100
1.50
200
7500
1250
Iterations
Iterations
Figure 1: SIS Exploitability
Figure 2: LQ Exploitability
Figure 3: LQ Evolution
sequence {TTE: Pe) generated by Algorithm D
satisfies
T T
oō
A exxepp(11 ( 2//3 total
D
Tt
+
14
XT1/5 +
T
A
Theorem establishes the finite-time convergence of Algorithm [ After T iterations, the averaged volicy-population pair ( Σi=o Te. T E j4) constitutes an O ('T=-//)-approximiii NE, subject to the approximation and statistical errors. As we collect more samples, the statistical errors can be driven to O. However, the approximation error Eapprox is an inherent mis-modeling cost due to using a (potentially not expressive enough) linear function approximate the policy, which might not diminish to 0 regardless of the number of iterations we run. While this seems to imply that linear function approximation can be restrictive, our experimental results (Section 55) instead suggest that linear functions are already satisfactory in most application scenarios that we are interested in.
The convergence rate Ô remains the same the tabular case 778., indicating that linear function approximation does not introduce intractability in terms of the dependence on T. The convergence rate in Theorem 1 is independent of the size of the state space |8], implying that our approach is applicable to MFGs with large state spaces. The dependence on the action space |A|| is also mild, [4] The convergence rate is also inverse proportional to the regularization parameter A. This indicates that higher regularization level can accelerate the convergence of the algorithm while introducing larger regularization error according to ① on the other hand. In practice, one can choose a regularization level that balances the convergence rate and accuracy.
and in mostly RL-related tasks the action space is adequately small
5
Experimental Results
5.1 Simulations on Classic MFGs
We first evaluate our natural actor-critic algorithm on two classic miea--iield games considered in the literature, including an SIS epidemics model [16 38), and linear-quadratic MFG [49] 38 [2 45). We refer to these two tasks as SIS and LQ, respectively. Detailed descriptions of the tasks and the simulation setups are deferred to Appendix D We implement Algorithm I with linear function approximation ("NAC" for short) and use temporal difference (TD) learning also with linear function approximation as the critic for policy evaluation. We utilize the standard notion of exploitability [84] a policy. Intuitively, a higher degree of exploitability suggests
16) to measure the sub-optimality that individual agent can be much better off by deviating from the given policy. As a comparison baseline, we also implement a "double-loop" version of natural actor-critic ("DL-NAC") that uses a fixed point iteration in similar fashion existing works 288
5 27
Simulation results on SIS and LQ are given in Figures | and respectively. All results are averaged over 10 runs. For both tasks, we can observe that the exploitability of NAC converges to 0, indicating that NAC can efficiently learn the NE. DL-NAC also converges in general, but it suffers "zigzag" fluctuations due to the fact that double-loop methods update the mean-field abruptly and hence nullify the policies learned from the past. See Appendix for detailed discussion of this phenomenon. Similar patterns have also been observed in the literature [16]. Hence, our online method enjoys faster convergence and more smooth learning behavior than the fixed-point iteration. In Figure 3, we further plot the evolution of the state distribution over time when applying NAC to LQ The population starts from a uniform distribution over the state space, and as time goes by, it quickly concentrates a small neighborhood of the state space, desired behavior for dinear-quadratic tracking- -type problems [72).
8

---

Master Node
Client
API
FeaS
Auth
Galleway
Data
Function Request
Function Requests
Fundion Code
Agent(s)
Container
Function Cantainer
Worker Node #1
Worker Node #2
Container
Worker Node #3
color and requests color are from the same lunctoon.
Nole: Conteiners
Container
Worker Noda
Monttoring
Container
Telemnery
Docker Control Groups (cgroups)
Figure 4: OpenWhisk cluster architecture and function container resource management with rein- forcement learning. Each RL agent assigned one function.
Total Rowed Epiends
1.50
NAC
Better
1.00
Latancy
2000
ENSURE
Openitiik
2000
NANG-Linar
NAC-NN kpp)
2.0
503
.003
Pwonle
AE51
Image Reates
HTM.
Compenstion
inferees
Page-tank
Gaph ISF
GradhASST
RL Training Ephocies
Figure 5: Policy Training
Figure 6: Policy Serving.
5.2 Experiments on a Serverless Platform
We apply our approach (with both linear and neural-network function approximations) a resource management problem in a serverless computing environment. Here, we directly consider a finite-agent game and collect the empirical average of the local states as the mean-field.
Serverless Platform and Workload. We use production-gran grrdd open-souree serverless platform, Open OpenWhisk [22]. and deploy it on IBM Cloud with 22 VMs. The Open Whisk cluster consists of one master node (that runs the serverless controller) and 21 worker nodes (each of which runs the function containers). Figure shows the architecture of distributed Open Whisk cluster and how RL agents work with the Open Whisk cluster to manage resources of each function. The master node runs the API gateway (labeled as FaaS controller ), data store
and other management modules. Each of the worker nodes (labeled as runs the function containers. We deploy the workload generator and RL agents from two separate nodes in the same cluster and use FaaSProfiler [60] to trace requests for function latency measurements, We select diverse function benchmarks from widely used open-source FaaS benchmark suites (15] 60 83], including web applications (c.g., HTML-Gen), multimedia application (e.g., Image-Resize Re)ize), scientific functions (e.g.. PageRank), and ML-model serving (e.g., invocations from Azure function traces [1]. Unlike [5T], however, we do not explicitly consider function dependencies, but we believe that our approach is orthogonal to [51] and can be potentially integrated with the critical component localization of [51 to model function dependencies. More detailed descriptions of the OpenWhisk setup are relegated to Appendix E
To drive the benchmarks, we sample and replay the function
RL Pipeline in Open Whisk. We model the resource management for each serverless function as sequential decision-maker RL agent (labeled as in Figure 4b monitors the system and application conditions from both the OpenWhist data store and the Linux cgroups. The collected measurements include function-level performance statistics (i.e., tail latencies on execution time, waiting time, and cold-start time for serving function requests) and system-leve resource utilization statistics (e.g., CPU utilization of function containers). These measured telemetry data are pre-processed and used to define RL states and rewards, which is then mapped to resource management decision by the RI. agent. The decision finally executed by FaaS controller and takes effect on the Open Whisk platform. After applying the action, the RL agent receives another state and reward in the next time step.
problem that can be captured by RL. At each step in the sequence, an

---

MARL Formulation. We formulate the function resource management problem on a multi-tenan serverless platform as Markov game where each function is assigned one agent. At each step. the agent perceives available system and application conditions (e.g., resource utilization and function latencies) from the platform monitor as the state. The action space includes both horizontal scaling (i.e., scaling the number of function containers) and vertical scaling (i.e., scaling the container size). Since the objective is to meet QoS objectives while keeping the resource utilization at a high level, we consider reward function T2 a ( (1- (t)
(RU RRU' (4) + penaltyy where QP(() and RU (t) are the QoS preservation ratio and resource utilization at time 6, and penalty is set to 11 (and 0 otherwise) for illegal or undesired actions (e.g.. dangling decisions). We implement and evaluate two variants of our method: one exploits linear function approximation for both the actor and the critic ("NAC-Linear" for short), and the other one leverages two-layer fully celneceddd neural network as function approximation (i.e., "NAC-NN"). Since serverless functions usually have diverse resource requirements and behaviors, we resort to multi-type formulation of MFGs (see 48 75 24
for more extensive discussions) to allow for heterogeneous agents.
Policy Training. For training, we create 50 functions on OpenWhisk, each of which is randomly selected from the function benchmarks. Figure 5 shows the total reward achieved by NAC-Linear and NAC-NN at each training iteration. We observe that NAC-NN takes about 300 fewer episodes to converge and achieves an 18.8% higher reward after convergence compared to NAC-Linear, We attribute this to the fact that linear function approximation cannot fully capture the complex system dynamics and decision- decision-making policies compared to neural networks.
Policy Serving. We measure the policy-serving performance using two metrics: the 99th percentile function latency (commonly used user-defined QoS objectives) and the number of function contain- ers in use. We take the model checkpoints of NAC agents after convergence and leverage the learned policies to manage resources for each function. Figure shows the function performance managed by NAC-Linear and NAC-NN compared with two heuristics-based approaches ENSURE [67] and Open- Whisk's 's original resource manager (Appendix D As shown in Figure NAC-NN achieves the best performance and has 33.6% to 67.3% (for Regizee lower latency compared to OpenWhisk's original algorithm. NAC-NN also has 14.8% to 29.6% (for Sentiment ieriimmeettnnlaiiss Analysis) lower latency compared to ENSURE. Additionally, NAC-NN uses 29% fewer function containers than ENSURE and 37% fewer than OpenWin Whisk's ' design, indicating a higher resource utilization level. NAC-Linear also outperforms ENSURE regarding function tail latency (by up 25.5%, for Uploader) and resource utilization (by up to 24% fewer function containers overall), which suggests that the simple linear function approximation can already lead to reasonable performances in practice.
6 Concluding Remarks
In this paper, we have proposed a mean-field game approach to large-scale cloud resource man- agement. We have presented an online natural actor-critic algorithm and proved its finite-time convergence to the regularized Nash equilibrium with linear function approximation. We have evaluated our solution on serverless platform using both linear and neural-network function ap- proximations, which has demonstrated superior performances in terms of scalability, latency, and resource utilization. Interesting future directions include further tightening the convergence rate and investigating alternative forms of function approximations for other application scenarios.
Acknowledgmente and Disclosure of Funding
This work was partially supported by the National Science Foundation (NSF) under grant CCF 20-29049; by the IBM-ILLINOIS Center for Cognitive Computing Systems Research (C3SR), a research collaboration that is part of the IBM AI Horizon Network, by the IBM-ILLINOIS Discovery Accelerator Institute (IIDAI;; and by the Air Force Office of Scientific Research (AFOSR) under grant FA9550- 19-5000191--0 1-0553.. Any opinions, findings recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the NSF or IBM or AFOSR.
'We do not experiment with even more functions because the serverless platform architecture is centralized model where the central manager usually becomes the bottleneck for scalability. To scale beyond thousands of functions in the production environment, cloud datacenters can use a two-tier model where a large cluster is divided into couple of sub-clusters [17] In this case, our method can be applied to each system sub-cluse sub-cluster to address the scalability issue.
10

---

References
[1] A. Agache, M. Brooker, A. lordache, A. Liguori, R. Neugebauer, P. Piwonka, and D.-M. Popa. Firecracker: Lightweight virtualization for serverless applications. In /7th USENIX Symposium on Networked Systems Design and Implementation (NSDI 20), pages 419-434, 2020.
[2] A. Agarwal, S. M. Kakade, J. D. Lee, and G. Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22 (98):1-76, 2021.
[3] Z. Ahmed, N. Le Roux, M. Norouzi, and D. Schuurmans. Understanding the impact of entropy on policy optimization. In International Conference Machine Learning, pages 151-166 PMLR, 2019.
[4] S.-I. Amari. Natural gradient works efficiently in learning. Neural computation, 10(2):251-276. 1998.
[5] B. Anahtarci, C. D. Kariksiz, and N. Saldi. Q-learning in regularized mean-field games. arXiv preprint arXiv:2003. 121.:1110..111,,, 2020.
[6] A. Angiuli, J.-P. Fouque, and M. Lauriere. Reinforcement learning for mean field games, with applications to economics. arXiv preprint arXiv:2106. 13755, 2021.
[7] I. Baldini, P. Castro, K. Chang, P. Cheng, S. Fink, V. Ishakian, N. Mitchell, V. Muthusamy, R. Rabbah, al. Serverless Computing: Current Trends and Open Problems, pages 1-20. 2017.
[8] S. Banerjee, S. Jha, Z. T. Kalbarezyk, and R. K. lyer. Inductive-bias-driven reinforcement learn- ing for efficient scheduling in heterogeneous clusters. In Proceedings of the 37th International Conference on Machine Learning, pages 629-641, 2020.
[9] A. Bensoussan, K. Sung, S. C. P. Yam, and S.-P. Yung. Lincar-guadratic mean field games. Journal of Optimization Theory and Applications, 169()):496-52) 2016.
[10] J. Bhandari, D. Russo, and R. Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference on Learning Theory, pages 1691-1692, 2018.
[11] S. Bubeck et al. Convex optimization: Algorithms and complexity. Foundations and Trends Machine Learning, 8(3-4):231-357, 2015.
[12] R. Carmona, J.-P. Fouque, and L.-H. Sun. Mean field games and systemic risk. Commumications Mathematical Sciences, (3():91 1-933, 2015.
[13] S. Cayci, N. He, and R. Srikant. Linear convergence of entropy-regularized natural policy gradient with linear function approximation. arXiv preprint arXiv:2106. 1et.:20006.4096,,. 2021.
[14] S. Cen, C. Cheng, Y. Chen, Y. Wei, and Y. Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 2021.
[15] M. Copik, G. Kwasniewski, M. Besta, M. Podstawski, and T. Hoefler. SeBS: A serverless benchmark suite for sumetion-as-a-Seree computing. In Proceedings of the 22nd International Middleware Conference (Middleware 202/), ), page 64-78, 2021.
[16] K. Cui and H. Koeppl. Approximately solving mean field games via entropy reguulazee deep reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 1909-1917. PMLR, 2021.
[17) C. Curino, S. Krishnan, K. Karanasos, Rao, G. M. Fumarola, B. Huang, K. Chaliparambil, A. Suresh, Y. Chen, S. Heddaya, al. Hydra: federated resource manager for data-center scale analytics. In 16th USENIX Symposium on Networked Systems Design and Implementation (NSDI 19), pages 177-192, 2019.
[18) C. Daskalakis, N. Golowich, and K. Zhang. The complexity of Markov equilibrium in stochastic games. arXiv preprint arXiv:2204. 039991, 2022.

---

[19] D. Ding, C.-Y. Wei, K. Zhang, and M. R. Jovanović. Independent policy gradient for large- scale Markov potential games: Sharper rates, function approximation, and game-agnostic convergence. arXiv preprini arXiv:2202.041222 2022.
[20] R. Elie, J. Perolat, M. Laurière, M. Geist, and O. Pietquin. On the convergence of model free learning in mean field games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 7143-7150, 2020.
[21] Y. Fei, Z. Yang, Z. Wang, and Q. Xie. Dynamic regret of policy optimization in non-stationary environments. Advances in Neural Information Processing Systems, 0136743-67544 2020.
[22] A. S. Foundation. OpenWhisk. httpp:///gghuub..cc///pppppppppp 2022-05-10.
2022. Accessed:
[23] Z. Fu, Z. Yang, Y. Chen, and Z. Wang. Actor-critic provably finds Nash equilibria of linear- quadratic mean-field games. In International Conference Learning Representations, 2020.
[24] S. Ganapathi Subramanian, P. Poupart, M. E. Taylor, and N. Hegde. Multi type mean field reinforcement learning. In International Conference on Autonomous Agents and Multiagent Systems, pages 411-419, 2020.
[25] M. Geist, B. Scherrer, and O. Pietquin. A theory of regularized Markov decision processes. In International Conference Machine Learning, pages 2160-2169, PMLR, 2019.
[26] D. A. Gomes, J. Mohr, and R. R. Souza. Discrete time, finite state space mean field games. Journal de mathématiques pures et appliquées, 93(3):308-328, 2010.
[27] H. Gu, X. Guo, X. Wei, and R. Xu. Mean-field controls with Q-learning for cooperative MARL: convergence and complexity analysis. SIAM Journal on Mathematics of Data Science, 3(4): 1168-1196, 2021.
[28] X. Guo, A. Hu, R. Xu, and J. Zhang. A general framework for learning mean-field games. arXiv preprint arXiv:2003.0600 06066, 2020.
[29] T. Haarnoja, A. Zhou, P. Abbeel, and S. Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International Conference on Machine Learning, pages 1861-1870. PMLR, 2018.
[30] M. Huang, R. P. Malhamé, and P. E. Caines. Large population stochastic dynamic games: closed- loop McKean-Vlasov systems and the Nash certainty equivalence principle. Communications in Information & Systems,
2006.
[31] C. Jin, Yang, Z. Wang. and M. Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143, PMLR, 2020.
[32] C. Jin, Q Liu, Y. Wang, and T. Yu. V-learnin-a simple, efficient, decentralized algorithm for multiagent RL. urXiv preprint arXiv:21 10. 14555, 2021.
[33] E. Jonas, J. Schleier-Smith
Sreekanti, C.-C. Tsai, A. Khandelwal, Q. Pu, V. Shankar, J. Carreira, K. Krauth, N. Yadwadkar, et al. Cloud programming simplified: A berkeley view on serverless computing, arXiv preprint arXiv: 10XXxv:9902.03300 2019.
[34] S. Kakade and J. Langford. Approximately optimal approximate reinforcement learning. In International Conference on Machine Learning. 2002.
[35] M. Kakade. A natural policy gradient. Advances in Neural Information Processing Systems, 14, 2001.
[36] S. Kardani-Mons Matdaai--Mggaadlmm, R. Buyya, and K. Ramamohanarao, ADRL: A hybrid anomaly-aware deep reinforcement learning- based resource scaling in clouds. IEEE Transactions on Parallel and Distributed Systems, 32(3)511-552, 2020.
[37] J.-M. Lasry and P.-L.. Lions. Mean field games. Japanese Journal of Mathematics, 2(1):229-260, 2007.
12

---

[38] M. Laurière, S. Perrin, S. Girgin, P. Muller, A. Jain, T. Cabannes, G. Piliouras, J. Pérolat, R. Élie, O. Pietquin, al. Scalable deep reinforcement learning algorithms for mean field games. arXiv preprini arXiv:2203. 11733, 2022.
[39] M. Littman. Markov games as framework for multi -agett reinforcement learning. In Machine Learning, pages 157-163. Elsevier, 1994.
[40] H. Mao, M. Alizadeh, I. Menache. and S. Kandula. Resource management with deep reinforee- ment learning. In Proceedings of the 15th ACM Workshop on Hot Topics in Networks (HotNet 2016), pages 50-56, 2016.
[41] W. Mao and T. Başar. Provably efficient reinforcement learning in decentralized general-sum Markov games. Dynamic Games and Applications, pages 1-22, 2022.
[42] W. Mao, L. Yang, K. Zhang, and T. Başar. On improving model-free algorithms for decentralized multi-agent reinforcement learning. In International Conference on Machine Learning, pages 1 15007-15049. PMLR, 2022.
[43] Mei, C. Xiao, C. Szepesvari, and D. Schuurmans. On the global convergence rates of softmax policy gradient methods. In International Conference on Machine Learning, pages 6820-6829. PMLR, 2020.
[44] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller. Playing Atari with deep reinforcement learning. arXiv preprint arXiv: 1312.5602, 2013.
[45] J. Moon and T. Başar. Discrete-time LQG mean field games with unreliable communication. In 53rd IEEE Conference on Decision and Control, pages 2697-2702. IEEE, 2014.
[46] O. Nachum, M. Norouzi, K. Xu, and D. Schuurmans. Bridging the gap between value and policy based reinforcement learning. Advances Neural Information Processing Systems, 2017.
[47] M. Nourian and P. E. Caines. e-Nash mean field game theory for nonlinear stochastic dynamical systems with major and minor agents. SIAM Journal on Control and Optimization, 51): 3302-3331, 2013.
[48] Perolat, S. Perrin, R. Elie, M. Laurière, G. Piliouras, M. Geist, K. Tuyls, and O. Pietquin. Scaling up mean field games with online mirror descent. arXiv preprint arXiv:2103.0066 2021.
[49] S. Perrin, J. Pérolat, M. Laurière, M. Geist, R. Elie, and O. Pietquin. Fictitious play for mean field games: Continuous time analysis and applications. Advances in Neural Information Processing Systems, 33:13199-13213 2020.
[50] S. Perrin, M. Laurière, J. Pérolat, M. Geist, R. Élie, and O. Pietquin. Mean field games flock! The reinforcement learning way. arXiv preprint arXiv:2 079337 2021.
[51] H. Qiu, S. S. Banerjee, S. Jha, Z. T. Kalbarezyk, and R. K. Iyer. FIRM: An intelligent fine- grained resource management framework for SLO-oriented microservices. In Proceedings of the 14th USENIX Symposiun on Operating Systems Design and Implementation (OSDI 2020), pages 805-825, Berkeley, CA, USA, Nov. 2020. USENIX Association.
[52] H. Qiu, W. Mao, A. Patke, C. Wang. H. Franke, Z. T. Kalbarezyk, T. Başar, and R. K. Iyer. SIMPPO: A scalable and incremental online learning framework for serverless resource man- agement. In Proceedings of the 13th ACM Symposium on Cloud Computing, 2022.
[53] H. Qiu, W. Mao, A. Patke, C. Wang, H. Franke, Z. T. Kalbarczyk, T. Başar, and R. K. Iyer. Reinforcement learning for resource management in multi-tenant serverless platforms. In Proceedings of the 2nd European Workshop on Machine Learning and Systems, pages 20-28, 2022.
[54] N. Saldi, T. Başar, and M. Raginsky. Markov-Nash equilibria in mean-field games with discounted cost. SIAM Journal on Control and Optimization, 56(6):4256-4283 2018.
13

---

[55] N. Saldi, T. Başar, and M. Raginsky. Approximate Nash equilibria in partially observed stochastic games with mean-field interactions. Mathematics of Operations Research, 44(3): 1006-1033, 2019.
[56] N. Saldi, T. Başar, and M. Raginsky. Approximate Markov-Nash equilibria for discrete-time risk-sensitive mean-field games. Mathemalics of Operations Research, 45(4):1596-1620, 2020.
[57] L. Schuler, S. Jamil, and N. Kühl. Al-based resource allocation: Reinforcement learning for adaptive auto-scaling in serverless environments. In 2021 IEEE/ACM 2 International Symposium Cluster, Cloud and Internet Computing (CCGrid 2021), pages 804-811, 2021.
[58] Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz. Trust region policy optimization. In International Conference on Machine Learning, pages 1889-1897. PMLR, 2015.
[59] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint 1rXXiv:707.06347 2017.
[60] M. Shahrad, J. Balkind, and D. Wentzlaff. Architectural implications of Function-as-a-Servicc computing. In Proceedings of the 52nd International Symposium on Microarchitecture (MICRO 2019), pages 1063 1075, 2019.
[61] M. Shahrad, R. Fonseca, f. Goiri, G. Chaudhry, Batum, Cooke, E. Laureano, C. Tresness, M. Russinovich, and R. Bianchini. Serverless in the wild: Characterizing and optimizing the serverless workload at a large cloud provider. In Proceedings of the USENIX 2020 Annual Technical Conference (ATC 2020), pages 205-218, 2020.
[62] S. Shalev-Shwartz and S. Ben-David. Understanding machine learning: From theory to algorithmss Cambridge university press, 2014.
[63] L. Shani, Y. Efroni, and S. Mannor. Adaptive trust region policy optimization: Global con- vergence and faster rates for regularized MDPs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5668 0008-5675.220 2025,
[64] A. Singhvi, A. Balasubramanian, Houck, M. Shaikh, S. Venkataraman, and A. Akella. Atoll: A scalable low-latency serverless platform. In Proceedings of the 12th ACM Symposium on Cloud Computing (SoCC 2021), pages 152, 2021.
[65] Z. Song, S. Mei, and Y. Bai. When can we learn general-sum Markov games with a large number of players sample-efficiently) arXiv preprint arXiv:2110.041844 2021.
[66] Subramanian and A. Mahajan. Reinforcement learning in stationary mean-field games. In Proceedings of the 18th International Conference on Autonomous Agents and MulriAgent Systems, pages 251-259, 2019.
[67] A. Suresh, G. Somashekar, A. Varadarajan, V. R. Kakarla, H. Upadhyay, and A. Gandhi. EN- SURE: Efficient scheduling and autonomous resource management serverless environments. In International Conference on Autonomic Computing and felf-Organizing Systems (ACSOS 2020), pages 1-10, 2020.
[68] R. S. Sutton, D. McAllester, S. Singh, and Y. Mansour. Policy gradient methods for rein- forcement learning with function approximation. Advances in Neural Information Processing Systems, 12, 1999.
[69] A. Tariq, A. Pahl, S. Nimmagadda, E. Rozner, and S. Lanka. Sequoia: Enabling Quality- of-Service in serverless computing. Proceedings of the 11th ACM Symposium on Cloud Computing (SoCC 2020), pages 311 311-327, 2020.
[70] H. Tembine and M. Huang. Mean field difference games: Mckean-Vlase dynamics. In 50th IEEE Conference on Decision and Control and European Control Conference, pages 1006-1011. IEEE, 2011.
[71] Tsitsiklis and B. Van Roy. Analysis of cemporal-difffereen learning with function approxi- mation. Advances in Neural Information Processing Systems, 9, 1996.
14

---

[72] M. A. uz Zaman, K. Zhang, E. Miehling, and T. Başar. Approximate equilibrium computation for time queara-u mean-field games. In 2020 American Control Conference (ACC), pages 333-339. IEEE, 2020.
[73] M. A. uz Zaman, K. Zhang, E. Miehling, and T. Basar. Reinforcement learning in non-stationary discrete-time uuear-quadratic mean-field games. In 2020 59th IEEE Conference on Decision and Control, pages 2278-2221 22844. IEEE, 2020.
[74] M. A. uz Zaman, A. Koppel, S. Bhatt, and T. Başar. Oracle-free reinforcement learning in mean-field games along a single sample path. arXiv preprint arXiv:2208. 1639, 2022.
[75] M. A. uz Zaman, E. Michling, and T. Başar. Reinforcement learning for non-stationary discrete-time linear-quadratic mean-fiell games in multiple populations. Dynamic Games and Applications, pages 1-47, 2022.
[76] I.. Wang, Q Cai, Z. Yang, and Z. Wang. Neural policy gradient methods: Global optimality and rates of convergence. In International Conference on Learning Representations, 2020.
[77] Z. Wen, Y. Wang, and F. Liu. StepConf: SLO-aware dynamic resource configuration for serverless function workflows. In IEEE Conference on Computer Communications (INFOCOM 2022), pages 1-10, Washington, DC, USA, 2022. IEEE Computer Society.
[78] Q. Xie, Z. Yang, Z. Wang, and A. Minca. Learning while playing in mean-field games: Convergence and optimality. In International Conference Machine Learning, pages 11436- 11447. PMLR, 2021.
[79] T. Xu, Z. Wang, and Y. Liang. Improving sample complexity bounds for (natural) actor-critic algorithms. Advances Neural Information Processing Systems, 33:4358 4369, 2020.
[80] Y. Yang, R. Luo, M. Li, M. Zhou, W. Zhang, and Wang. Mean field multi-agent reinforcement learning. In International Conference on Machine Learning, pages
PMLR, 2018.
[81] Z. Yang, P. Nguyen, H. Jin, and K. Nahrstedt. MIRAS: Model-based reinforcement learning for microservice resource allocation over scientific workflows. In IEEE 39th International Conference Distributed Computing Systems, pages 122-132, 2019.
[82] H. Yu, A. A. Irissappane, H. Wang, and W. J. Lloyd. FaaSRank: Learning to schedule functions in serverless platforms. In Proceedings of the 2nd IEFE International Conference on Autonomic Computing and Self- fefl--Orgniiing Systems (ACSOS 202/), ), pages 31 31-40, 2021.
[83] T. Yu, Q. Liu, D. Du, Y. Xia, B. Zang, Z. Lu, P. Yang, C. Qin, and H. Chen. ServerlessBench (soce 2020). /trps://githi
com wwm/SomT/ SJTU- - IPADS/ SeaDD/Seerereesseenneee 2020.
[84] M. Zinkevich, M. Johanson, M. Bowling, and C. Piccione. Regret minimization in games with incomplete information. Advances in neural Information Processing Systems, 20, 2007.
Checklist
For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We have discussed the potential
lack of expressiveness of linear function approximation in Sections and 4 We have
also pointed few directions for improvement in our concluding remarks.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] Applying our resource management solution to real-world serverless platforms might lead to privacy concerns as relies on collecting behavior data of the user functions. Neverthe- less, as discussed in Section our simulations themselves are evaluated on anonymized open-source function traces and should not raise such concerns.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
15

---

2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Assump- tions HHB 3 in Section 4
(b) Did you include complete proofs of all theoretical results?
[Yes] See Appendices
and B
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes]
(b) Did you specify all the training details (e.g.. data splits. hyperparameters, how they were chosen)? [Yes] See Appendices D
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Figures [ and
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Section 5 and Appendix
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? Yes] We have properly Section
cited the creators of the datasets [6]] and benchmarks [T5
60
(b) Did you mention the license of the assets? [Yes] The dataset 66 uses the Creative
Commons Attribution 4.0 International Public License. The benchmark FaaSProfiler
uses MIT License;
[15] uses BSD 3-Clause License;
83
uses Mulan Permissive
Software License.
(c) Did you include any assets either in the supplemental material
URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you't 're using/curating? [Yes] The dataset [61] and benchmarks [[5] 60 83 that we use have been open-sourced by their corresponding creators on GitHub.
(c) Did you discuss whether the data you are using/curating contains personally identifiable using does not contain personally identifiable information or offensive content.
information offensive content? [Yes] The data
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A] No crowdsourcing research has been involved in this work.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
16


Reviews:
[{"review_id": "wrxrVmFBlL", "reviewer": "Reviewer_CQL5", "summary": "This paper aims to solve the problem of improving latency and resource utilization in serverless platforms. The paper proposes a mean-field game approach where they design a natural actor-critic (NAC) learning paradigm for MFGs with function approximation.  The evaluation shows the convergence of their approach, and shows some latency and resource efficiency improvement on the OpenWhisk platform.\n\nNote: I am not an expert on the mean-field game theory side so I am not sure about the theoretical contribution, but I am confident in my evaluation of the serverless system side. I appreciate the authors’ effort to try to formalize the resource allocation problem in serverless.\n", "questions": "1. The majority of the paper assumes homogeneous agents, and the theorems and proofs are all based on this assumption. However, the evaluation on OpenWhisk assumes heterogeneous agents. Could you provide more details on how did you adapt the algorithms for real deployment? And are those proofs still valid for heterogeneous agents? Please clarify.\n2. It is unclear in the paper why this MFG approach is uniquely tailored for serverless. The theorems did not include any assumptions from the serverless system.\n3. This paper only considers a very coarse-grained resource allocation type – vertically adding CPUs or memory, or horizontally adding containers. How does it scale to many different resource allocation knobs such as CPU frequency, memory bandwidth, I/O bandwidth, etc? \n4. The reward function in Line 332 seems to be constructed naively by averaging CPU and memory utilizations, could you clarify that?\n5. How does the resource allocation part interact with the scheduler? Do you use round-robin or least loaded worker? How do you decide which functions are co-located in one worker (function placement issue)? Those are unclear in the paper.\n6. Usually resource allocation needs some time (seconds to minutes) to take effect, so the reward would only be observed after a certain delay. Therefore, resource allocation needs to be proactive, predicting what will happen next. However, the algorithm does not seem to consider such delay.\n7. In prior work such as FIRM, they consider a workflow of serverless functions and incorporate dependencies between functions. How does MFG work considering dependencies?\n8. Though the authors claim that scalability is the main issue of resource allocation in the cloud the paper does not provide proof or evaluate the scalability of their approach. In the evaluation, only 50 functions are tested which indicates only 50 agents are running concurrently. But the production environment usually serves thousands of different functions simultaneously.\n", "limitations": "The authors discussed some limitations and potential social network impacts in the paper. I found some limitations after reading the paper (mentioned in the above Questions section). ", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. Interesting approach to map resource allocation (or autoscaling) problem in serverless to MFGs, and the authors try to solve the system challenge in a theoretica way.\n2. The paper applies their approach to a real system (OpenWhisk).\n\nWeaknesses\n1. The mapping between the idealized theoretical setup and the real system is a bit vague. E.g., the major part considers homogeneous agents and only the OpenWhisk experiments consider heterogeneous agents.\n2. The paper does not evaluate or prove the scalability of the proposed algorithm.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "dgUbSxAFuKG", "reviewer": "Reviewer_BAei", "summary": "The paper proposes a scalable mean-field game (MFG) approach to the problem of cloud resource management. It introduces an online natural actor-critic (NAC) algorithm for MFGs, which uses function approximation and lets the mean-field state naturally evolve as the agents learn. The authors establish finite-time convergence of NAC with linear function approximation and softmax parameterization, but also implement neural-net based function approximation. Experimental results on open-source serverless platform OpenWhisk with real-world workloads from production traces demonstrate that NAC is scalable to a large number of agents and significantly outperforms other common baselines.", "questions": "1. In terms of theory, what are the main differences of this work with the NAC setting with linear function approximation by (Cayci, He, and Srikant, 2021)? I understand that the setting is a bit different, because this work focuses on mean-field approximation for a multi-agent setting, whereas the cited work is purely single-agent. On the other hand, the mean-field approach effectively transforms the problem into a single-agent one. What are the additional innovations/challenges (particularly in terms of theory and proofs) of this work compared to the work by (Cayci, He, and Srikant, 2021)?\n2. Why have the authors not included any RL-based baseline (except for the double-loop version of NAC)? Multi-agent RL-based approaches without the mean-field assumption may suffer from limited scalability, so the authors could show the benefit of MFG NAC in a rather basic setting. Is it also possible to compare single-agent RL-based approaches (e.g., FIRM) to the proposed framework, e.g., by looking at the problem from the perspective of the single agent?\n3. In Equation (1), right in the middle do the authors perhaps mean V^{\\pi,\\lambda}_{\\mu^*}(\\rho) instead of V^{\\pi}_{\\mu^*}(\\rho)? Shouldn't the \\lambda appear somewhere?\n\n---AFTER REBUTTAL---\nThe authors addressed my concerns; I am therefore willing to raise my recommendation to Weak Accept.", "limitations": "The authors have addressed the limitations of their work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. The paper is well written. Even the theory parts that are more involved are not hard to follow and the authors provide adequate refences and clarifications to explain the different concepts. I found this very helpful, because the NAC algorithm contains a number of steps such as policy evaluation, gradient estimation, mean-field update and policy update.\n2. The problem that motivates this work is an important real-world problem. Furthermore, a MFG approach is a quite reasonable design choice for this problem, in particular for large numbers of users where collective user behavior can be summarized by a population distribution, and a common policy can be applied to all agents.\n3. I was unable to check the proofs in detail, but the proposed algorithm and the ingredients therein make sense, as they follow faithfully various prior works.\n4. The related work is concise but seems to cover a lot of important and relevant prior works.\n5. The experiments show that the proposed NAC does not suffer from the zigzag fluctuations of the double-loop version of NAC that uses a fixed point iteration. Furthermore, experiments with real-world workloads from production traces show that NAC significantly outperforms other common baselines such as ENSURE and OpenWhisk's original resource manager. \n\nWeaknesses\n1. The novelty is not strong. Convergence of entropy-regularized natural policy gradient with linear function approximation has been already studied by (Cayci, He, and Srikant, 2021). And indeed this work builds very heavily upon this specific work (which, incidentally, is a pre-print and has not been accepted to peer-reviewed venues yet). The main difference is that NAC is now applied to a MFG setting, where the main solution concept is that of a Nash Equilibrium. Still, due to the mean-field approximation, the agent essentially faces a single-agent policy optimization problem, and the game-theoretic setting roughly becomes equivalent to a single-agent Markov decision process. That said, I do not claim that the two works are identical, since the deal with a different setting; however, they do overlap significantly.\n2. In the experimental evaluation, NAC is only compared to two other heuristic-based baselines. It would have made much more sense to also compare against other RL-based schemes. As the authors point out in the related work, there are various RL-based frameworks for scheduling or resource management (e.g., FIRM, FaaSRank, etc.). I feel that the authors would have made a much stronger point is they were able to show that the NAC algorithm can outperform other RL-based competitors (even by focusing on a simpler objective such as minimizing latency only). Even if some approaches are single-agent, the authors could also experiment multi-agent RL-based baselines to showcase the benefits of their framework (even in a basic setup to demonstrate the scalability challenges with traditional multi-agent approaches).", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9aQuAoHcu9R", "reviewer": "Reviewer_fRko", "summary": "The competition and scheduling of cloud service resources is a significant research problem with economic value. Due to the emergence of new cloud service paradigms such as serverless computing, we consider the aid of multi-agent reinforcement learning (MARL) to address new management challenges. To this end, the authors design a mean-field game (MFG) approach that can efficiently manage large-scale cloud users and applications. They propose an online natural actor-critic algorithm for approximating functions in mean-field games and demonstrate the finite-time convergence of the algorithm theoretically. The study evaluates the solution's effectiveness on OpenWhisk using workloads captured from real production systems, showing advantages in scalability, latency, and resource utilization.", "questions": "Overall, this paper constructs a comprehensive multi-agent reinforcement learning system and demonstrates the properties of online natural actor-critic algorithms in detail. Still, the most prominent weakness is the lack of necessary problem formulation (i.e., cloud resource management). Therefore, at the very beginning of the paper, it is suggested to supplement the problem case study and formalization to formalize the resource scheduling problem into a multi-agent reinforcement learning process in the context of a serverless computing scenario. This issue involves a lot of real details and needs to be explained. For example, cloud users do not need to manage the computing resources in a serverless computing scenario, so how can self-interested users compete for resources.", "limitations": "Not applicable.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The cloud resource competition and scheduling problem has real research significance and economic value\n- Comprehensive theoretical basis and proof of properties\n- The efficiency advantage of the proposed solution makes it adaptable to real system scenarios\n\nWeaknesses：\n- The background and problem formalization are insufficient, resulting in the disjointed problem background and methodology\n- Validation in large-scale system scenarios/cases", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4cqXLWViweC", "reviewer": "Reviewer_6cfc", "summary": "The paper presents a mean field game approach to the many selfish agent problem. The paper contextualises this around the resource management problem for FaaS before moving on to a theoretical evaluation of the problem and finishes with experimental results.", "questions": "The paper is in general well written. No small questions.", "limitations": "This was not discussed.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper presents a clear introduction to the FaaS problem along with a detailed mathematical analysis of the MFG solution. \n\nHowever, the paper is very dense and feels like two papers rammed into one. The introduction is all about the Cloud and the FaaS problem. The next section of the paper is a dense mathematical work on the MFG problem - with no mention of the FaaS problem. The FaaS only returns as one of the examples in the results section. It would have probably been better to have couched this paper as a fully theoretical paper and just keep the FaaS as one of the results examples. This would have given more space for covering the 'middle paper'. This could have helped in making it clear what the 'NeurIPS' element of this work was.", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept