Mean Field Equilibrium in Multi-Armed Bandit Game with Continuous Reward

1 Introduction

Great efforts have been devoted to multi-armed bandit (MAB) for sequential decision making, where agents can only observe limited information when pulling arms [Bubeck et al., 2012]. Though principled, these techniques are mostly suitable for the single-agent scenario. As multiple agents may coexist, multi-agent learning is proposed to investigate agent interactions [Panait and Luke, 2005], and particularly Markov game serves as the main tool to characterize the learning equilibrium in multi-agent systems [Littman, 1994]. Perfect information is usually needed in Markov game to determine the learning strategy, which makes it inefficient to analyze the equilibrium when the number of agents scales or when

Corresponding author: Riheng Jia

dealing with MAB problems. To accommodate this bandit feedback, Hart and Mas-Colell propose a no-regret learning method [Hart and Mas-Colell, 2000], yet only the coarse correlated equilibrium can be derived for a handful of agents.

Mean field game is an effective model to approximate complex interactions among large populations [Lasry and Lions, 2007; Huang et al., 2006], where the approximation error is O(1/√N) with N the number of agents [Ying, 2016]. Combined with online learning framework, mean field model is applied to multi-agent systems for deciding agents' strategic actions and characterizing system's stable state [Cardaliaguet and Hadikhanloo, 2017; Iyer et al., 2014]. Existing mean field analysis often requires complete knowledge of not only the reward function, but also the historical information to obtain the mean field equilibrium (MFE), which is not applicable in scenarios with merely limited feedback available.

The problem of analyzing bandit feedback for many agents remains open until Gummadi et al. use the mean field model to study multi-agent MAB in a repeated game [Gummadi et al., 2013], where they derive a unique MFE based on assumptions of binary reward and state regeneration. Following works have adopted their model in cellular network [Maghsudi and Hossain, 2017] and smart grid [Zhao and Liu, 2017]. However, the binary reward setting is too restricted for realworld multi-agent systems. Like in a resource competition game, agents usually share the resource with each other instead of occupying exclusively, thus the reward is a continuous value in [0, 1] rather than only 0 or 1 [Yang et al., 2018a; Hanif et al., 2015]. Besides, agent state is assumed to regenerate with a certain probability to deduce an equilibrium in these works, whereas typical repeated games mostly entail iterative plays of each agent with no regeneration [Panait and Luke, 2005]. One critical question then is how to achieve the equilibrium for the non-regenerated bandit game involving a large number of agents with a generalized continuous reward.

In this paper, we propose a mean field model to tackle the bandit game in large-population multi-agent systems with a continuous reward function. We aim to resolve the existence and uniqueness issues of MFE, and hence are faced with the following challenges. First, characterizing the learning equilibrium is inconsistent with minimizing the regret since a nonregenerated bandit game is unstable under classical MAB algorithms. Therefore, one needs to model the agent state cautiously to strike a balance between system stability and tightbounded regret. Second, existing Markov game is ineffective to track the state evolution, which is identified in a continuous regime instead of a discrete value due to the generalized reward function. Third, existence and uniqueness of MFE is hard to derive as we only observe a bandit feedback.

To handle these challenges, we encode and update an agent state using observed rewards, and devise a stationary policy to map the state to stochastic arm playing strategy in turn. We show that the state evolution satisfies a fixed point condition, thus proving the convergence of states to an existing MFE. Then, we develop a stochastic approximation to transform the stochastic state evolution into a deterministic ordinary differential equation (ODE), so that we can derive a contraction mapping for the ODE to obtain the unique MFE. Finally, we deduce a regret related cumulative state change, and extend the mean field model. Our contributions are summarized:

• We propose a new framework of mean field analysis to explore the multi-agent bandit game with a continuous reward. Our framework can generalize the previous binary reward function to a more universal scenario.
• We characterize the stable state for a large-population stochastic system with only limited information by deriving the existence and uniqueness of MFE. Specifically, we show there exists a MFE via Kakutani fixed-point theorem, and further devise both rigorous and relaxed conditions for || · ||∞-contraction to obtain the unique MFE, thereby providing a tractable and guaranteed system performance.
• We encode the learned reward into agent state, which can both ensure the system stability and yield a tight empirical regret. Model extensions also reveal the robustness of our mean field analysis in different variants of MAB problems.

2 Model and Setup

We study a repeated multi-agent bandit game, where there are a large number of agents N = {1, 2, ..., N} and a set of arms (actions) M = {1, 2, ..., M}. Time is slotted {0, 1, ..., n, ...}.

2.1 State and Playing Policy

The state of each agent i encodes its learned reward based on the observations realized so far, which is denoted as sin = [sin (1), sin (2), ..., sin (M)] ∈ RM with sin (j) being the learned reward of arm j upon to time slot n.

Agents are assumed to follow a stationary policy when solving MAB problems in the repeated bandit game [Cohen et al., 2017]. Denote a simplex ∆M-1 = {z ∈ [0, 1]M : ∑Mj=1 z(j) = 1} as the probability distribution over M arms. An arm playing policy is a mapping from the state space to the simplex σ : RM → ∆M-1 , i.e., σ(sin , j) means the probability that agent i would choose arm j with ∑Mj=1 σ(sin , j) = 1. In particular, we focus on a Hedge stationary policy below:

where Exp(·) represents the exponential function and β > 0 is the smoothing parameter. The value σ(sin , j) consists of two parts balanced by parameter η ∈ [0, 1], in which the first part is a logit policy and the second is a random selection.

2.2 Mean Field Reward

Let ain be the played arm of agent i following policy σ(sin ). Population profile fn = [fn(1), fn(2), ..., fn(M)] indicates the proportion of agents playing the various arms in time slot n. Denote 1{·} as the indicator function, and then fn(j) is defined:

Each agent's reward of playing an arm is determined by the actions of all agents due to their interactions. For instance, in a resource competition game, the reward will decrease if more competitors (agents) simultaneously compete for the same resource (arm). As directly characterizing the influence of agents' actions is difficult for large populations owing to the curse of dimensionality, we employ the mean field model to approximate interactions among agents, and accordingly their rewards will depend on the population profile fn [Yang et al., 2018b; Gummadi et al., 2013]. Denote r(fn, ain ) as the realized reward of agent i when pulling arm ain in time slot n, where r(·) is the reward function. With the bandit feedback, any agent only observes its realized reward without knowing the reward function and the population profile. Formally, r(·) is a continuous function rather than a discrete binary value as in [Gummadi et al., 2013; Maghsudi and Hossain, 2017]. Apparently, continuous reward is more general, also widely adopted in both the single-agent MAB [Auer et al., 2002a; Auer et al., 2002b] and the multi-agent learning [Yang et al., 2018b; Cohen et al., 2017]. By convention, we assume that the reward r(fn, ain ) is in the range [0, 1] which can be easily extended to other arbitrary intervals.

The state is updated after an agent obtains a realized reward. If agent i observes r(fn, ain ), we update its state as:

where:

The updating rule implies that only the state to the played arm is renewed while others remain unchanged. Moreover, the stepsize γn satisfies the following condition:

2.3 Objective

Define sn = [s1n , s2n , ..., sNn ] as the state profile, i.e., the states of all agents, thus sn ∈ [0, 1]N×M since r(fn, j) ∈ [0, 1]. Our objective is to analyze the convergence of sn, particularly to derive the existence and uniqueness of MFE. Meanwhile, we will also deduce the cumulative state change, which entails the regret information of the MAB problem.

3 Existence and Uniqueness of MFE

Characterizing the MFE is critical to a multi-agent system, because it can provide a guaranteed and predictable system performance [Adlakha et al., 2015]. To achieve this goal, we need to answer two fundamental questions: 1) Does MFE exist? 2) If so, does there exist only one MFE?

The evolution of state profile sn can be decomposed into playing and evolving processes. The playing process is the stationary policy of Eq. (1), mapping states to population profile Γ1 : sn → fn; the evolving process amounts to the state updating of Eq. (3), mapping population profile to states in turn Γ2 : fn → sn+1. Let Γ = Γ2◦Γ1 be the compound mapping, so the state evolution is interpreted as Γ : sn → sn+1. The definition of MFE under mapping Γ is now presented.

Definition 1. State profile s is a MFE if s = Γ(s).

3.1 Existence of MFE

Definition 1 indicates that a MFE is indeed a fixed point under mapping Γ. Since agents stochastically play actions based on Eq. (1), we obtain that Γ is a set mapping. Suppose the reward r(fn, j) is continuous in the population profile fn.

Theorem 1. There exists a MFE s satisfying s ∈ Γ(s).

Proof. The state profile sn is in a nonempty, compact, and convex set [0, 1]N×M . The mapping Γ maps sn to sn+1 ∈ [0, 1]N×M which is a nonempty, closed, convex subset of [0, 1]N×M . We next prove Γ is upper semi-continuous.

Let P be the set of the population profile fn. For any state profile sn, we have Γ1(sn) ∈ P according to the playing process. From Eq. (3), if agent i plays arm j, then its state corresponding to this arm after updating satisfies:

Suppose there are arbitrary sequences xn, yn ∈ [0, 1]N×M such that limn→∞xn → x, limn→∞yn → y, and yn ∈ Γ(xn). Given a state profile, the set P is determined. Since r(fn, j) is continuous in fn, we can claim that y ∈ Γ(x) from Eq. (6), i.e., Γ is upper semi-continuous. By applying the Kakutani fixed-point theorem [Glicksberg, 1952], there exists a fixed point s, or MFE, under the mapping Γ.

Theorem 1 ensures the existence of MFE, to which the states will ultimately converge. Since there may exist multiple MFEs, it is hard to determine which MFE the states will eventually approach. Therefore, we need to further derive a unique MFE so as to achieve a more guaranteed performance.

3.2 Uniqueness of MFE

Unique MFE implies there is only one fixed point. For mean field game, Lasry and Lions show that if the reward is a monotone function known by any agent, one will obtain a unique MFE [Lasry and Lions, 2007], which however is inconsistent with the MAB problem. To handle the bandit feedback, we use the stochastic approximation [Bena¨ım, 1999] to transform the discrete-time bandit game into a continuous-time ODE, and derive the unique MFE by proving that the ODE will only converge to one fixed point. Therefore, we can resort to the deterministic ODE to figure out the stochastic bandit game.

Stochastic Approximation

The state evolution is a stochastic process in that each agent plays arms randomly according to the stationary policy. Considering this fact, we rewrite the state updating of Eq. (3):

where uin (j) = win (j) - E[win (j)]. Denote st = [s1t , s2t , ..., sNt ] as the state profile at continuous time t. In the following, we show that the state profile sn at discrete time will asymptotically converge to st, which is characterized by a deterministic ODE. Hereinafter, we use t to index continuous time, and n to index discrete time slot.

Lemma 1. When n → ∞ and t → ∞, the state sin = [sin (1), sin (2), ..., sin (M)] of agent i will asymptotically converge to sit specified by the following ODE:

See Appendix A in the technical report [Wang and Jia, 2021] for the proof. With this lemma, if the ODE Eq. (8) of st solely converges to one fixed point, then there is a unique MFE for sn. Note that the mapping Γ for the continuous-time state evolution now corresponds to the ODE Eq. (8). Specifically, using Eqs. (3) and (4), the ODE of sit (j) is obtained:

We emphasize that r(ft, j) in Eq. (9) is the expected reward over the state profile st as the population profile ft is mapped from st by the stochastic stationary policy.

Convergence to Unique MFE

Consistent with Lemma 1, we first assume the reward function is a contraction mapping to obtain the unique fixed point, and then derive the conditions for this contraction mapping. We express the reward r(ft, j) of playing arm j as r(f(st), j) to explicitly indicate its dependence on st. Also denote s as the fixed point for ODE Eq. (9) at which the derivative is 0.

Theorem 2. Suppose that the reward function r(f(st), j) is a ||·||∞-contraction in the state profile st, then the fixed point s is the unique MFE for the bandit game. s is also the global attractor for the ODE Eq. (9), and st converges to s with exponential rate.

Proof. Because r(f(st), j) is a contraction mapping in st, r(f(st), j) - sit (j) = 0 in Eq. (9) will have only one fixed point s. From Lemma 1, we obtain that s is also the unique MFE for the bandit game.

Construct Lyapunov function V (st) = ||st -s||∞, and assume V (st) gets its maxima at sit (j), that is V (st) = |sit (j)- si (j)|. If sit (j) > si (j), we have V (st) = sit (j)-si (j). Take derivative over time t and use r(f(s), j) = si (j):

where C1 < 1 because of the || · ||∞-contraction mapping. As a result, dV (st) dt ≤ 0 and dV (st) dt = 0 only at s. If sit (j) ≤ si (j), following the same approach, we can also obtain dV (st) dt ≤ σ(sit , j)(C1 - 1)V (st). Therefore, the fixed point s is a global attractor for the ODE.

As Lyapunov function satisfies dV (st) dt ≤ σ(sit , j)(C1 - 1)V (st), which implies dV (st) V (st) ≤ σ(sit , j)(C1 - 1)dt, we have V (st) ≤ C2Exp [σ(sit , j)(C1 - 1)t] where C2 is a constant. Therefore, st converges to s exponentially fast.

According to Lemma 1 and Theorem 2, we know that sn → s when n → ∞. Next, we discuss the convergence rate of the discrete-time sn. Recall from the stepsize γn in Eq. (5), we can set γn = 1/(n + 1)α, α ∈ (1/2, 1].

Theorem 3. Suppose that the reward function r(f(sn), j) is a || · ||∞-contraction in the state profile sn. Denote the distance en = ||sn - s||∞:

Proof. Based on Theorems 2 and 3 in [Even-Dar and Mansour, 2003], we only need to prove ||E[wn(sn)] - s||∞ ≤ C||sn - s||∞ with C ∈ [0, 1), to draw the two conclusions. Assume ||E[wn] - s||∞ = |E[win (j)] - si (j)|. According to Eq. (4) and the fact s satisfies r(f(s), j) = si (j), we have:

The second inequality holds as r(f(sn), j) is a contraction, and the third inequality is from || · ||∞-definition.

Contraction Mapping Condition

The foundation of the unique MFE lies in that the reward function r(f(st), j) is a contraction mapping in the state profile st. Suppose the reward function r(fn, j) is θ-Lipschitz continuous in the population profile fn with regard to || · ||1norm: |r(fn, j)-r(f ′n , j)| ≤ θ||fn -f ′n ||1. Combining with the idea in [Cominetti et al., 2010] and the mean field model, we now characterize the contraction mapping condition.

Theorem 4. If parameters β, η in Eq. (1) and θ satisfy the condition 4θ(1 - η)β < 1, then the reward function r(f(st), j) is a || · ||∞-contraction in the state profile st.

Proof. Let sa and sb be two state profiles, and define a sequence Ak = [s1a , s2a , ..., ska , sk+1 b , ..., sNb ] , k = 1, 2, ...,N with the first k elements from sa and the rest from sb. Denote Aik as the i-th state in Ak, and ak as the played arms following the stationary policy σ(Aik ). Let a-i k be the armset except agent i, and f(ak) or f(Ak) be the population profile. When aik = j, |r(f(sa), j)-r(f(sb), j)| = | ∑Nk=1 [r(f(Ak), j)r(f(Ak-1), j)]| ≤ ∑Nk=1 |r(f(Ak), j) - r(f(Ak-1), j)| = ∑Nk=1 |r(f(ak), j) - r(f(ak-1), j)|.

Let △k = r(f(ak), j) - r(f(ak-1), j), so we can express △k = ∆rk · (σ(ska ) - σ(skb )) where ∆rk is a Mlength vector with the l-th element ∆rk(l) as ∆rk(l) = ∑z∈a-i k ,zk=l r(f({j, z}), j) ∏m̸=k,i σ(Amk , zm). Note that ∆rk(h)1 · (σ(ska ) - σ(skb )) = 0, ∀h ∈ M, where 1 is a M-length vector with each element equal to 1. Therefore, we can rewrite △k = (∆rk - ∆rk(h)1) · (σ(ska ) - σ(skb )). If za, zb ∈ a-i k with only the k-th arm being different: zk a = l, zk b = h, we obtain ||f({j, za}) - f({j, zb})||1 ≤ 2N from Eq. (2). As r(fn, j) is θ-Lipschitz continuous, then:

As a result, we obtain:

Combining with Eqs. (14) and (15), we attain:

In line with Eq. (13), we present the final result:

The condition 4θ(1-η)β < 1 in Theorem 4 is a little stringent for two reasons. First, the reward function r(f(st), j) depends on all M elements of f(st). Second, r(f(st), j) is non-linear in f(st), so calculating the expected reward needs multiple scaling operations. In fact, the reward r(f(st), j) of playing arm j is often only impacted by the number of agents who select arm j [Gummadi et al., 2013], such as an agent playing arm j only competes with those making the same choice in a resource competition game. Hence, we assume r(f(st), j) merely depends on the j-th element, denoted as f(st, j). Besides, we further presume the reward is a linear function in the population profile. With these two assumptions, we recharacterize a relaxed contraction condition.

Corollary 1. If the reward r(f(st, j), j) is a θ-Lipschitz continuous linear function in the j-th element f(st, j), then r(f(st, j), j) is a ||·||∞-contraction in the state profile st under the condition θ(1-η)β 2 < 1, where β, η are from Eq. (1).

Proof. From Eqs. (1)-(2), the expected population profile, with a slight abuse of notations, is f(st, j) = E[∑Ni=1 1{ait=j} N ] = ∑Ni=1 σ(sit ,j) N . Since r(f(st, j), j) is θLipschitz continuous in f(st, j), we obtain | dr(f(st,j),j) df(st,j) | ≤ θ. For two state profiles sa, sb, there is a x ∈ [sa, sb] satisfying r(f (sa, j), j)-r(f (sb, j), j) = ∇r(f (x, j), j)·(sa-sb) based on mean value theorem. Hence, |r(f(sa, j), j) - r(f(sb, j), j)| ≤ ||∇r(f(x, j), j)||1||sa - sb||∞.

Considering r(f(x, j), j) is linear in f(x, j), we have dr(f(x,j),j) dxi (l) = dr(f(x,j),j) df(x,j) df(x,j) dxi (l) , ∀i ∈ N, l ∈ M. As | dr(f (x,j),j) df(x,j) | ≤ θ, we only need to handle df(x,j) dxi (l) . Moreover, df(x,j) dxi (l) = 1N dσ(xi ,j) dxi (l) = (1-η)βσ(xi ,j)(1{j=l}-σ(xi ,l)) N .

Consequently, we acquire the following result:

(18)

where the second inequality is because y(1 - y) ≤ 14 , ∀y ∈ [0, 1]. Finally, it results in:

4 State Change andModel Extension

In this section, we derive the cumulative state change to infer the regret information and extend the mean field model to demonstrate its effectiveness in various scenarios.

4.1 Cumulative State Change

After state updating according to Eq. (3), the state change is ∆sin = γn(win - sin ). Let σ(sin ) · ∆sin be the inner product between the simplex σ(sin ) in Eq. (1) and ∆sin . Also denote (∆sin )2 as the vector with square on each element of ∆sin . The following theorem provides the cumulative state change.

Theorem 5. Denote 1 as a M-length vector with each element equal to 1. For agent i and an arbitrary arm j, we have:

See Appendix B in the technical report [Wang and Jia, 2021] for the proof. Cumulative state change entails the regret of arm playing, i.e., maxj ∑T-1 n=0 (r(fn, j) - E[r(fn, ain )]). Specifically, if regarding the left-hand side of Eq. (20) as maxj r(fn, j), and expanding the right-hand side via r(fn, ain ), one can obtain a theoretically loose bound of a scaled regret, which serves as a tradeoff between regret minimization and system stability. We will show in the evaluations that the stationary policy actually has a small empirical regret.

Remark: The bandit game will not converge to an equilibrium when applying the traditional MAB algorithms which may have tight-bounded regret, like UCB [Auer et al., 2002a] and EXP3 [Auer et al., 2002b]. This is because they need to model an agent state as the cumulative reward. Hence, the state will consistently "increase" since realized rewards are positive, so that the system is unstable. This is also the underlying reason why works [Gummadi et al., 2013; Maghsudi and Hossain, 2017; Zhao and Liu, 2017] have to assume a state regeneration to achieve system stability.

4.2 Heterogeneous Learning Parameter

So far, we have analyzed the bandit game with homogeneous learning parameters β, η in stationary policy Eq. (1). Next, we explore the heterogeneous β, η for different agents.

For agent i, parameter βi will keep unchanged, while ηin is

diminishing and satisfies limn→∞ ηin = 0 to give less weight to the random choice when the reward information is accurately learned. Therefore, the stationary policy changes to σ(sin , j) = (1 - ηin ) Exp(βi sin (j)) ∑Mk=1 Exp(βi sin (k)) + ηin M . Except the playing policy, the updating rule is the same, as described in Eq. (3). Following a similar analysis in the homogeneous situation, it can be asserted that the results in Theorems 1-3 and Lemma 1 still hold. As for the contraction mapping conditions in Theorem 4 and Corollary 1, they turn out to be 4θβmax < 1 and θβmax 2 < 1, respectively, where βmax = max{βi |i ∈ N}. The cumulative state change in Theorem 5 is specified by replacing β, η with βi , ηin .

4.3 Overlapping Arms

Another extension is about overlapping arms. Mathematically, there are M arms, and each agent i pulls an arm from a subset Mi ,Mi ⊆ M with M i = |Mi |. Overlapping means there exist i, k such that Mi ∩Mk ̸= ∅. The conclusion is: previous results still hold after we make several adjustments. The proofs are the same, thus we skip them to save space.

One adjustment is to choose arms from Mi for agent i, i.e., σ(sin , j) = (1 - η) Exp(βsin (j)) ∑k∈Mi Exp(βsin (k)) + η Mi . The state sin is now a M i -length vector, and the state profile sn is in [0, 1]∑i∈N Mi . Other parameters, especially the cardinality of sets, are adapted accordingly. Similar to Section 3, we could obtain the existence and uniqueness of MFE.

5 Performance Evaluation

In this section, we carry out the evaluations where results are smoothed via LOWESS in Python for better exhibition.

5.1 Existence and Uniqueness of MFE

Reward function. We consider that agents will compete for different resources (arms), so the reward r(fn, j) is a nonlinear decreasing function in fn(j) [Gummadi et al., 2013]:

where θ(j) ∈ [0.8θ, θ], ∀j ∈ M. Hence, r(fn, j) ∈ [0, 1] is θ-Lipschitz continuous. Set γn = 1/(n + 1) in Eq. (5).

Contraction mapping. Let (θ, β, η) be (0.5, 0.5, 0.2), respectively, that is the contraction condition 4θ(1 - η)β < 1 holds. Given the number of arms M = 4, we run the bandit game for four times and display the state evolution of arm 2 in Figure 1. We can see that the state will converge to a unique MFE for different number of agents N.

Figure 2 shows the population profile of arm 2, which is unique and tends to be stable as N increases. Because E [1{ai=j} ] = σ(si , j) and var [1{ai=j} ] = σ(si , j)(1 - σ(si , j)) ≤ 14 , we have var[f(s, j)] = 1 N 2 ∑Ni=1 var [1{ai=j} ] ≤ 1 4N . The Chebyshev's inequality states that Pr (|f(s, j) -E[f(s, j)]| ≥ ϵ) ≤ 1 4Nϵ2 , i.e., if N increases, f(s, j) will be more stable around E[f(s, j)].

Non-contraction mapping. Let θ, η, M stay the same, while β changes to 30 so the contraction mapping 4θ(1 - η)β < 1 is violated. We run the bandit game for four times and depict the state evolution in Figure 3, which shows that the state converges to multiple distinct MFEs. The population profile is displayed in Figure 4, where the fluctuation around E[f(s, j)] is also impaired for larger N. Due to multiple MFEs, the population profile has various steady values.

5.2 Empirical Regret

For the general reward, we compute the regret when contraction mapping holds, i.e., (θ, β, η) = (0.5, 0.5, 0.2). Furthermore, we implement a linear reward: r(fn(j), j) = 1 -

θ(j)fn(j) where θ(j) ∈ [0.8θ, θ], ∀j ∈ M and (θ, β, η) = (1, 2, 0.2), so the reward is a contraction from Corollary 1. We run the evaluation for six times with each operating for T = 2000 time slots, and show the average regret and cumulative rewards in Table 1. The regret bound for EXP3 is O(√T ), and here √T = 44.721. We can see that both regrets are much smaller than √T for each N. Besides, the regret of general reward is less than that of linear reward, as changes in fn(j) have smaller impact when appearing in the denominator of Eq. (21). Moreover, the regrets decease as N grows large for both cases due to a more stable population profile. In summary, the stationary policy has a tight empirical regret.

6 Conclusion

We propose a mean field model to study a large-population bandit game with a continuous reward. Concretely, we characterize the existence and uniqueness of MFE by showing the state evolution is upper semi-continuous, and deriving contraction mapping conditions based on the stochastic approximation, respectively. Extensive evaluations are performed to validate our mean field analysis and tight empirical regret.

Acknowledgments

This work was supported by NSF China under Grant 61902358, Zhejiang Provincial Natural Science Foundation of China under Grant LQ19F020007.