Learning in Congestion Games with Bandit Feedback
Authors: Qiwen Cui
Zhihan Xiong
Maryam Fazel
Simon Shaolei Du
Venue: NeurIPS 2022 Accept (2022)
Keywords: reinforcement learning theory
multi-agent reinforcement learning
congestion game

Abstract: In this paper, we investigate Nash-regret minimization in congestion games, a class of games with benign theoretical structure and broad real-world applications. We first propose a centralized algorithm based on the optimism in the face of uncertainty principle for congestion games with (semi-)bandit feedback, and obtain finite-sample guarantees. Then we propose a decentralized algorithm via a novel combination of the Frank-Wolfe method and G-optimal design. By exploiting the structure of the congestion game, we show the sample complexity of both algorithms depends only polynomially on the number of players and the number of facilities, but not the size of the action set, which can be exponentially large in terms of the number of facilities. We further define a new problem class, Markov congestion games, which allows us to model the non-stationarity in congestion games. We propose a centralized algorithm for Markov congestion games, whose sample complexity again has only polynomial dependence on all relevant problem parameters, but not the size of the action set.

Learning in Congestion Games with Bandit Feedback
Qiwen Cui
Zhihan Xiong'
qucuiθcs. washington.
zhihanx@cs washington. edu
Maryam Fazel? mf mfazelluw..o edu
Simon S. Du saduêcs washington edu
Paul G. Allen School of Computer Science & Engineering, University of Washington 2 Department of Electrical & Computer Engineering, University of Washington
Abstract
In this paper, we investigate Nash-regret minimization in congestion games, a class of games with benign theoretical structure and broad real-world applications. We first propose a centralized algorithm based on the optimism in the face of uncertainty principle for congestion games with (semi-) )bandit feedback, and obtain finite-sample guarantees. Then we propose decentralized algorithm via a novel combination of the Frank-Wolfe method and G-optimal design. By exploiting the structure of the congestion game, we show the sample complexity of both algorithms depends only polynomially on the number of players and the number of facilities, but not the size of the action set, which can be exponentially large in terms of the number of facilities. We further define new problem class, Markov congestion games, which allows us to model the non-stationarity in congestion games. We propose centralized algorithm for Markov congestion games, whose sample complexity again has only polynomial dependence on all relevant problem parameters, but not the size the action set.
Introduction
Nash equilibrium (NE) is widely adopted concept in game theory community, used to describe the behavior of multi-agent systems with selfish players [Roughgarden, 2010]. At the Nash equilibrium, no player has the incentive to change its own strategy unilaterally, which implies it is steady state of the game dynamics. For a general-sum game, computing the Nash equilibrium PPAD-hard [Daskalakis, 2013] and the query complexity is exponential in the number of players [Rubinstein, 2016]. To help address these issues, a natural approach is to consider games with special structures. In this paper, we focus congestion games.
Congestion games are general-sum games with facilities (resources) shared among noncooperative players [Rosenthal, 1973]. During the game, each player will decide what combination of facilities to utilize, and popular facilities will become congested, which results possibly higher cost on each user. One example of congestion game is the routing game [Fotakis al., 2002], where each player needs to travel from a given starting point to destination point through some shared routes. These routes are represented as a traffic graph and the facilities are the edges. Each player will decide her path to go, and the more players use the same edge, the longer the edge travel time will be. Congestion games also have wide applications in electrical grids [lbars et al., 2010], internet routing
"Equal contribution.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

[Al-Kashoash et al., 2017] and rate allocation [Johari and Tsitsiklis, 2004]. In many real-world scenarios, players can only have (semi-)bandii feedback, i.c. players know only the payoff of the facilities they choose. This kind of learning under uncertainty has been widely studied in bandits and in reinforcement learning for the single-agent setting, while theoretical understanding for the multi-agent case is still largely missing.
There are two types of algorithms in multi-agent systems, namely centralized algorithms and de- centralized algorithms, For centralized algorithms, there exists a central authority that can control and receive feedback from all players in the game. As we have global coordination, centralized algorithms usually have favorable performance. On the other hand, such central authority may not always be available in practice, and thus people turn to decentralized algorithms. i.e., each player makes decisions individually and can only observe her own feedback. However, decentralized algo- nonstationary
rithms are vulnerable to nonstationarity because each player is making decisions environment as others' strategies are changing [Zhang et al., 2021a]. In this paper, we will study both centralized and decentralized algorithms in congestion games with bandit feedback, and we will provide motivating scenarios for both algorithms in Section 1.2.
The main challenge in designing algorithms for m-player congestion games with bandit feedback is the curse of exponential action set, i.e., the number of actions can be exponential in the number of facilities F because every subset of facilities can be an action. As result, an efficient algorithm should have sample complexity polynomial in m and F and has no dependence on the size of the action space. One closely related type of general-sum game is the potential game, in which each individual's 's payoff changes, resulting from strategy modification, can be quantified by common potential function. It well-known that all congestion games are potential games, and each potential game has an equivalent congestion game formulation [Monderer and Shapley, 1996]. However, existing algorithms designed for potential games all have sample complexity scaling at least linearly in the number of actions [Leonardos et al., 2021, Ding et al., 2022], which is inefficient for congestion games. This motivates the following question:
Can we design provably sample-efiiciett centralized and decentralized learning algorithms for congestion games with bandit feedback?
We provide an affirmative answer to this question. To be precise, we use Nash-regret minimization (formally defined in Section 3) as our objective for learning in congestion games. This regret- like objective commonly appears in the literature of online learning and reinforcement learning [Orabona, 2019, Ding et al., 2022, Liu et al., 2021], which focuses on finite-time analysis and accumulative rewards throughout the learning process instead of the asymptotic behavior. In general, sublinear Nash regret implies best-iterate convergence, meaning that the algorithm has reached the approximate Nash equilibrium least once, while the converse does not hold.
We highlight our contributions below and compare our results with previous algorithms in Table 1. Our algorithms are shaded and we prove sublinear Nash regrets for all of them. In Table 1, sample complexity refers to the number of samples required to reach best-iterate convergence to an e-approximate Nash equilibrium and the results are obtained by standard online-to-batch conversion as in Section 3.1 of [Jin et al., 2018].
1.1 Main Novelties and Contributions
1. Centralized algorithm for congestion game. We adapt the principle of optimism in the face of uncertainty in stochastic bandits to ensure sufficient exploration congestion games. We begin with congestion games with semi-bandit feedback, in which each player can observe the reward of every facility in the action. Instead of estimating the action reward as in stochastic multi-armed bandits, estimate the facility rewards directly, which removes the dependence on the size of action space. Furthermore, we consider congestion games with bandit feedback, in which each player can only observe the overall reward. In this setting, we borrow ideas from linear bandits to estimate the reward function and analyze the algorithm. The algorithm is provably sample efficient in both cases.
2. Decentralized algorithm for congestion game. Our decentralized algorithm is a Frank- Wolfe method with exploration, which each player only observes her own actions and rewards. To efficiently explore in the congestion game, we utilize G-optimal design allocation for bandit feedback and a specific distribution for semi-bandit feedback. As a result, the sample complexity does not depend on the number of actions. In addition, the L1 smoothness parameter of the potential function

---

Table 1: Comparison of algorithms for congestion games in terms of sample complexity and Nash regret, where "IPPG" stands for "independent projected policy gradient", "IPGA" stands for "inde- pendent policy gradient ascent", "I" represents the setting of semi-bandit feedback and "I[" represents the setting of bandit feedback. Bandit feedback is assumed for algorithms from previous work. Here, A; is the size of player i's action space, m is the number of players, Amax = max A,, the number of facilities and I is the number of samples collected. Our algorithms are shaded. Algorithms
Sample complexity
Nash regret
Decentralized
Nash-VI [Liu et al., 2021]
T2 F/)
VII 1 A.
No
V-learning [Jin et al., 2021a]
Amax (CCE)
NA
Yes
IPPG [Leonardos et al., 2021]
A Amax
NA
Yes
IPGA [Ding et al., 2022]
A A m Fb /6
mF4/3 VAmac T
Yes
Nash-UCB
mF2 /62
FVmT mF33 VT m² F3/2255/6 m² F27566
No
Nash-UCB II
m²p3/1 /e?
No
Prank-Wolfe with Exploration Frank-Wolf with Exploration II
m m² 3/2F//c
Yes
m2 p22/11//
Yes
does not depend on the number of actions, which is exploited by the Frank-Wolfe method. With the help of these two specific algorithmic designs for congestion games, we give the first decentralized algorithm for both semi-bandi feedback and bandit feedback that has no dependence on the size of the action space in congestion games.
3. Centralized algorithm for independent Markov congestion game. We extend the formulation of congestion game into a Markov setting and propose the independent Markov congestion game (IMCG), in which each facility has its own internal state and state transition happens independently among all the facilities. In Section 1.2, we give some examples that in this model. By utilizing techniques from factored MDPs, we extend our centralized algorithms for congestion games to efficiently solve IMCGs, with both semi-bandit and bandit feedback.
1.2 Motivating Examples
We provide an exmple here to motivate our proposed models. See Section 3 for the formal definition of (semi-)bandit feedback and (Markov) congestion games and Appendix A for additional examples. Example 1 (Routing Games). For a routing game, there are multiple players in a traffic graph travelling from starting points to destination points, and the facilities are the edges (roads). The cost of each edge is the waiting time, which depends on the number of players using that edge.
Centralized algorithm for routing games: Imagine each player is using Google Maps navigate. Then Google Maps can serve as a center that knows the starting points and the destination points, as well as the real-time feedback of the waiting time on each edge of all the players. Google Maps itself also has the incentive to assign paths according to the Nash equilibrium strategy as then each player will find out that deviating from the navigation has no benefit and thus sticks to the app.
Decentralized algorithm for routing games: Consider the case where players still using Google Maps but due to privacy concerns or limited bandwidth. they only use the offline version, which has access only the information of each single user. Then Google Maps needs use decentralized algorithms so that it can still assign Nash equilibrium strategy to each user after repeated plays.
Markov routing games: For Markov routing games, the time cost on each edge will change between different timesteps, which is more accurate model of the real-world. For instance, some roads are prone to car accidents, which will result in an increasing cost on the next timestep, and the chance of accidents also depends the number of players using that edge currently. This is modeled by the Markovian facility state transition in independent Markov congestion games.
2 Related Work
Potential Games. Potential games are general-sum games that admit a common potential function to quantify the changes in individual's payoff [Monderer and Shapley, 1996]. Algorithmic game
3

---

theory community has studied how different dynamics converge to the Nash equilibium, e.g., best response dynamics [Durand, 2018. Swenson al., 2018] and no-regret dynamics [Heliou et al., 2017, Cheung and Piliouras, 2020], while usually they provide only asymptotic convergence, with either full information setting or bandit feedback setting. Recently, reinforcement learning community studied Markov potential games with bandit feedhack, which can be applied to standard potential games. See the Markov Games part below for more details.
Congestion Games. Congestion games are developed in the seminal work [Rosenthal, 1973], and later Monderer and Shapley [1996] builds close connection between congestion games and potential games. Congestion games are divided into atomic and non-atomic congestion games depending on whether each player is separable. Many papers consider non-atomic congestion games with non-decreasing cost function, which implies a convex potential function [Roughgarden and Tardos, 2004]. We consider the more difficult atomic congestion game where the potential function can be non-convex. For online non-atomic case, [Krichene et al., 2015] considers partial information setting while they provide convergence in the sense of Cesaro means. [Kleinberg et al., 2009, Krichene et al., 2014] show that some no-regret online learning algorithms asymptotically converges to Nash equilibrium. [Chen and Lu, 2015, 2016] are two closely related works that consider bandit feedback in atomic congestion games and provide non-asymptotic convergence. However, they still assume convex potential function and the sample complexity has exponential dependence on the number of facilities, which is far from ideal.
Markoy Games. Markov games are widely studied since the seminal work [Shapley, 1953]. Recently, the topic has received much attention due to advances in reinforcement learning theory. Liu et al. [2021] provides a centralized algorithm for learning the Nash equilibrium in general-sumt Markov games, and [Jin et al., 2021a, Song et al., 2021] provide decentralized algorithms for learning the (coarse) correlated equilibrium. One closely related line of research is on Markov potential games [Leonardos et al., 2021, Zhang et al., 2021b, Fox et al., 2021, Cen et al., 2022, Ding et al., 2022]. However, applying their algorithms to congestion games leads to explicit dependence on the number of actions, which would be exponentially worse than our algorithms. See Table 1 for comparisons. Our independent Markov congestion game is motivated by the state-based potential games studied in Marden [2012] and Macua et al. [2018], and its transition kernel is closely related to the factored MDPs, for which single agent algorithms are studied in [Osband and Van Roy, 2014, Chen et al., 2020, Xu and Tewari, 2020, Tian et al., 2020, Rosenberg and Mansour, 2021].
Learning in Games. Different from our paper, learning in games in traditional literature of game theory mainly considers players' asymptotic behavior [Leslie and Collins, 2005, Cominetti et al., 2010, Coucheney et al., 2015]. In early literature, Leslie [2004] investigates actor-critic learning and Q-learning algorithms in games with bandit feedback and their connection to best-response dynamics. Leslie and Collins [2005] proposes individual Q-learning algorithm and shows that converges to the NE almost surely in two-player zero-sum game and Leslic and Collins [2006] studies learning the NE from the perspective of a fictitious play-like process. Later, Cominetti et al. [2010] considers payoff- based learning rules and shows convergence to NE in traffic games, while another payoff-based learning model for continuous games is developed in Bervoets et al. [2020). Coucheney al. [2015] derives a new penalty-regulant
dynamics and proposes a corresponding learning algorithms that converges to NE in potential games with bandit feedback. Bravo et al. [2018] proposes that in monotone games with bandit feedback, as long as all players are using some no-regret learning algorithm, the dynamics will converge to the NE, and an improved analysis of the same derivative-free algorithm is given in Drusvyatskiy et al. [2022]. In contrast, our learning objective focuses on finite-time cumulative rewards, which is more widely used in current multi-agent reinforcement learning literature [Ding et al., 2022, Liu et al., 2021].
3 Preliminaries
General-sum Matrix Games. We consider the model of general-sum sum matrix games, defined by the tuple G = (m R). where m is the number of players, A, is the action space of player and R(-la) is the reward distribution on [0, rmax] T with mean r(a). Let A = Ai x ... x Am be the whole action space and denote an element as (a),..., am) E A. After all players take actions a E A, a reward vector is sampled r ~ R(-la) and player i will receive reward r; E [0, rmax] with mean (a). Each player's objective is to maximize her own reward.

---

A general policy x is defined as vector in A(A), the probability simplex over the action space A. product policy (........
................................ Tm)) is defined tuple in ((Ai) x x ((Am). in which a
(01,...;;.l) ~ represents 0; Ti. The value of policy ι for player i is V Ea-w [Ba-n(rr(a))
ii.d.
Nash Equilibrium and Nash Regret. Given a general policy म, let T- be the marginal joint policy of players 1,..., 1 1,
m. Then, the best response of player under policy is
π. argmax V and the corresponding value is V/t.5 := Vi Our goal is to find the approximate Nash equilibrium of the matrix game, which is defined below.
Definition 1. A product policy и is e-approximate Nash equilibrium if max, (V, V,*)
An e-approximate Nash equilibrium can be obtained by achieving a sublinear Nash regret, which is defined below. See Section 3 in Ding et al. [2022] for more detailed discussion. Definition 2. With n being the policy k-th episode, the Nash regret after K episodes is define as
Nash-Regret K)
Σ
max xE(m)
Vi (VI-
V.
Remark 1. Here, if we replace [mX by Ei= in the definition of Nash regret, the single-step
Nash regret at episode & will become the Nikaido-Isoda (NI) function evaluated at x², which is popular objective for equilibrium computation [Nikaidō and Isoda, 1955, Raghunathan et al., 2019]. Replacing max4e[m] by mm will multiply our regret bounds by factor of m, while our conclusion will not be affected.
Potential Games. A potential game is general-sum game such that there exists potential function 4 (A4) + [0, 4 max] such that for any player i E [m] and policies nú, T., TT it satisfies
( T-:) D( T-.)
Vo V
We can immediately see that a policy that maximizes the potential function is Nash equilibrium.
Congestion Games. A congestion game is defined by G = (F, (F:():) , )e>), where {R(}
F [F) is called the facility set and RC' (-In) E [0 is the reward distribution for facility ʃ with mean (n). where n E [m]. Each action ag E A. is a subset of F (i.c., as F). Suppose the joint action chosen by all the players
A, then a random reward is sampled r R (-Inn/ (a) for each facility f. where n/ (a) = EiE 1l {ʃ E a;} is the number of players using facility f. The reward collected by player i T; = E,ea. rd with mean (a) ES rf (n)(a)) E [].
Connection to Potential Games [Monderer and Shapley, 1996]. As special class of potential game, all congestion games have the potential function: 4(a) = ΣSEF ii=l
(a)(a) r (i). To see this, we can easily verify that (a,,,a)) - 4(a a);) = (a a) - r: a_s) holds. Then, by defining (TT) = Ea-a [a)), we can have o 7 -.) ((T,, T.:) VV V -V-
Types of feedback. There are in general two types of reward feedback for the congestion games, semi-bandit feedback and bandit feedback, both of which are reasonable under different scenarios. In semi-bandii feedback, after taking the action, player will receive reward information r' for each f E a;: in bandit feedback, after taking the action, player will only receive the reward Eren, Tf with no knowledge about each rf In this paper, will address both of them, with more focus on the bandit feedback, which can be directly generalized to semi-bandit feedback.
4 Centralized Algorithms for Congestion Games
In this section, we introduce two centralized algorithms for congestion games one for the semi- bandit feedback and one for the bandit feedback. We will see that both of them can achieve sublinear Nash regret with polynomial dependence on both m and F.
4.1 Algorithm for bandit Feedback
Summarized in Algorithm 1, Nash upper confidence bound (Nash-UCB) for congestion games is developed based on optimism in the face of uncertainty. In particular, the algorithm estimates the
5

---

reward matrices optimistically in line 4, computes its Nash equilibrium policy in line 5 and then follows this policy.
For convenience, we define the empirical counter (n) = Σ 1 (aa)) n and ž 2 1og(4(m + 1)). Then, the reward estimator for f and the bonus term are defined as
pk.l (n) E R. 1 { n (a n
(a)
E
i (n
(I)
N (n) V1
SEa; V
where pk. E [0, 1] the random reward realization of r (n (a*)). Naturally, the reward estimator for player is PM (a) Efe,. GR.f (n (a)).
Algorithm Nash-UCB for Congestion Games
1: Input: accuracy parameter for Nash equilibrium computation
2: for episode 1,.... K do
3: for player = 1,...,.., do
4: (a) + (a) b (a) for all a E A (.) (Algorithm 2) 6: Take action a T and observe reward yka
5: nh + (eNNAS(("
7: Update reward estimators p/ and bonus term b/
Algorithm is motivated by the Nash- VI algorithm in [Liu et al., 2021] plus deliberate utilization of the special reward structure in the congestion games. Moreover, notice that a matrix game with
(-) ".....,,,,, we can efficiently compute the c-approximate Nash equilibrium π for that matrix game by utilizing Algorithm (see Lemma 2). is a simple greedy algorithm such that in each round, modifies one player's 's policy whose modification can increase the potential function most. In addition, Algorithm 2 always outputs a deterministic product policy.
reward functions (.).... Q
forms a potential game (see Lemma 1). As result, in line 5,
Algorithm 2 e-approximate Nash Equilibrium for Potential Games
1: Input: c, accuracy parameter; full information potential game (fA.), (r.),))) such that ri [0, mmax] for all E [m]]
2: Initialize: ग = a² arbitrary deterministic product policy
3: for round A = ....., ma do
4: for player = 1,...,,. do
5: A max ro x-,) (T(
6: k+1 = argmax,eeA ra(a; n² x - (Tx)
7: if max] A; < then
8: return x
9: j argmax.g(ml A
10: k + = aj x++1 (i), for all i j
4.2 Algorithm for Bandit Feedback
When the players only receive bandit feedback, estimating pk.f directly for each F is no longer feasible. However, notice that the reward function r:(a) Efeo, r (nnn(a) can be seen as an inner product between vectors characterized by action and reward function r (.). Therefore, under bandit feedhack, we can treat it as a linear handit and use ridge regression to build the reward estimator f and corresponding bonus term JA+t whose index is dropped since it is the same for all players. The new algorithm will use these two terms to replace o and 6h in line 4 of Algorithm 1.

---

In particular, define 0 E [0, 11 with d = mmF to be the vector such that r' = On+m(f-1)- Mcanwhile, for player E [m]. define A, A {0, 1]" to be the vector-valued function such that [A:(a]]; - 1 {j n m( 1), at, n n (a))
In other words, (a) a 0-1 vector with element 1 only at indices corresponding to those in 0 that represents of (n) for f E a; and n n (a). Now, with these definitions, the reward function can be written as ri(a) = (a) 8). Then, we build the reward estimator and the bonus term through ridge regression and corresponding confidence bound, which are defined the following:
(a) = (000((AAa))) (A(()) (a)((a)= max ||::(a)l( V sEmml
(2)
where ~² = (VL) ΣK' E A, yr V = I Ex Em A,(a ((a")))))) and VB. Vā + v FFdlog (1 mkP FT. Note that we cannot bound the sum of this bonus
terms by directly applying the elliptical potential lemma. We instead prove its variant in Lemma 4.
4.3 Regret Analysis
The Nash regret bounds for the two versions of Algorithm are formally presented in Theorem 1. The proof details are deferred to Appendix
Theorem Let = 1/K. For congestion games with semi-bandit feedback, feeebbbc, by running Algorithm I with reward estimator and bonus term in (1), with probability at least - 8, we can achieve that
Nash-Regreti K) S = = (FVRK).
Furthermore, if we only have bandit feedback, then by running Algorithm I with reward estimator and bonus term in (2), with probability at least 1 - 5, we can achieve that
Nash-Regre K) < 5 (m
Remark 2. Since each action is a subset of F, the size of each player's action space can be 2 As result, directly applying Nash-VI VI in [Liu ct al., 2021] ]] leads to a regret bound exponential in F. Remark 3. Note that we assume /- E [0, 1]. which implies r; E [0, F for each player E [m]]
Decentralized Algorithms for Congestion Games
In this section, we present decentralized algorithm for congestion games. Due limited space, we only introduce the version of bandit feedback as in Section 4.2. The algorithmic details for the semi-bandit feedback setting are deferred into Appendix D.3. We will show that under both settings, even though each player can only observe her own actions and rewards, our decentralized algorithm still enjoys sublinear Nash regret with polynomial dependence on m and F.
We first define the vector-valued function Φ; Ar + {0, 13 F4 be the feature map of player such that (a,)), = 1 {f E a for a; A; and E Ua,EA, Here, F; is the size of Ua,EA, a, S F and we can immediately see that F: < F for any E [m].
The core idea of our algorithm is that the Nash equilibrium can be found by reaching the stationary points of the potential function since all congestion games are potential games. Here, the UCB- like algorithms used in the centralized setting are not applicable because their policy computation requires value functions for all players (e.g.. line 5 of Algorithm 1), which are not available in the decentralized setting. Summarized in Algorithm 3, the decentralized algorithm is developed based on the Frank- Wolfe method and has the following three major components.
Gradient Estimator. In line 7, the algorithm builds the estimator & defined in (4) by using the reward samples collected from line 5. Here, A. estimates the gradient of potential function & with respect to the policy पF. Recall that for congestion game, we have ((a) EreIEn'' (i)
nn
7

---

Algorithm 3 Frank-Wolfe with Exploration for Congestion Game
1: Input: 7, mixture weights; mł. initial policy.
2: Initialize: P;. the G-optimal design for player i, defined in (5).
3: for episode k 1, K do
4: for round f = 1, 1... r do
5: Each player takes action az ~ प, observes reward r
6: for player 1,... m do
7: Compute (a;) by the formula in (4) for a; E A,
8: Compute 7//+1 + argmax x Thy 4/4
9: Update o. 1++1 <- (1 - (VT) + + (1- )))x,) TPi
and ((T)) = Ea-s [.[a]] Then we can define V = Vx, D as a vector of dimension [A.]. For the component indexed by some E Ai, we can see that ( m (T:()) ima [ri(at, a a-)) + const, where const does not depend on ny(a;). Therefore, we have
(ap(a,) int Ir:aa; a-))
-E : Eai
[r(n((a,a.i))) (0)((t)))((T))) (3)
FEas
where (T)), =a--st [n' (a + 1)]. Meanwhile, the mean of the t-th reward that player i received at episode li satisfies
E
k.t a
ri(aat))= = Σ (' (n ((ak.()) (00))) (, (c)))
fEat
where 10 (a = rf (a + 1) and its mean is [0((T*)], )]5. Therefore, we can use linear regression to estimate 8 (,(xx) (. In particular, we have (: = E (I+) & (a. (a (r with the covariance matrix Σ = E B (())a)))(aa)))) Then, we have the unbiased gradient estimate
(),()) = ( (f))) - (a.))) (2:) o.(a
(4)
Remark 4. One difference between Algorithm 3 (decentralized) and Algorithm (centralized) is that in the decentralized algorithm, each player is required to play the same policy for times before an update can be applied. An episode is thus defined for convenience as the time period during which the players' policies fixed. We make this artificial design mainly for controlling the variance of the gradient estimator (a.). However, we conjecture that with more careful design and analysis, it should be possible to improve Algorithm 3 so that only one sample is required per episode [Zhang al., 2020].
G-optimal Design. In line 8 and 9, the algorithm performs standard Frank- Wolfe update and mixes the updated policy with an exploration policy Pt. which defined as the G-optimal allocation for features (dx(a)))a To be specific, we have
Pi = argmin max [1dv(a:))l xEA(A,) a:EA: (ea (o101111101"1)
(5)
Here Pi guarantees that E invertible and the variance of ( = (d)(aa), ( depends only on F instead of the size of action space (Lemma 9) because by the famous Kiefer- Wolfowitz theorem, have ma [[)) Eag [0((4)))())]]] F; < F [Lattimore and Szepesvári, 2020].
Frank- Wolfe Update. Finally, we emphasize that it is crucial to use Frank- update because is compatible with L, norm and we can show that & m m-smoothh with respect to the I,, norm (Lemma 11). In contrast, its smoothness for Le norm will depend on the size of the action space.

---

Before the game starts, each player can compute her P; based on her own action set A, During the game, all players only have access to their own actions and rewards, which means that Algorithm fully decentralized. The Nash regret bound for this algorithm is formally stated in Theorem 2 and the proof details are given in Appendix D.I and D.2.
Theorem 2. Let T Kr. For congestion game with bandit feedback, by running Algorithm 3 with gradient estimator 4 (4) and exploration distribution pi (5), if K Z m then with probability at least - 8, we have
K
Nash-Regrer( = Σ
VI V. < 2O mm (0 + m F8121
max
iE(m]
k=1
For congestion game with semi-bandit feedback, by running Algorithm ((a)) and exploration distribution defined in Appendix D.3, 2/E then with probability at least 8, we have
3 with gradient estimator
Nash-Regre (T) S SO (0mm² 13/26//76 m2 + p2T2/3)
6 Extension to Independent Markov Congestion Games
In this section, we propose and analyze a Markov extension of the congestion games, called the independent Markov congestion games (IMGGs).
6.1 Problem Formulation
General-sum Markoy Games. finite-horizon time-inhomogeneouu tabular general-sum Markov game is defined by M = {S, { H, P. R. so). where S is the state space, m is the number of players, Ar is the action space of player i, A A1
Am the whole action space, H A PH) with Ps [0, 1|5xAx5 as the h=1 with Rd. (-1Shh a. the reward distribution on [0, I mmax]" 1M with mean (sh. 04) E 0, maax 1mh at timestep h E [H]. At timestep h, all players choose their actions simultaneously and reward vector is sampled Th R2, (-1sh, an). where 8 is (4n, ah.2.
is the time horizon, so is the initial state' P =P,,
transition kernel at timestep h,
(-18%, a=))==
aa.m) is the joint action. Each player receives reward Th, and the state transits to 8641 ~ PA (-1sh, an). The objective for each player to maximize her own total reward. We assume that the initial state 81 is fixed.
the current state and
(Markov) policy æ is a collection H functions (mx : S + A(A)) h- each of which maps a state distribution over the action space. is a product policy if Tr (- s) is product policy for each (h, s) E [H] x S. The value function and Q-value function of player i at timestep h under policy ı are defined
(s) = Ex
Σ
aw) s =
(r,((, = Ex Σ rwe aw) 8h an =
The best responses and Nash regret can be defined similarly as those for matrix games. In particular, given a policy æ, player i's best response policy is Th argmax Viitti(s)) and the corresponding value function is denoted as V
Definition 3. With n being the policy at kth episode, the Nash regret after K episodes is define as
Vyli* 1.
Nash-Regret K) =
max ie(m)
V., (81).
Independent Markov Congestion Game A general-sum Markov game is an independent Markov congestion game (IMCG) if there exists facility set F such that a; S F for any a; Ai, state space S I Sf, set of facility reward distributions (R (R such that if the joint
An episode is defined running H steps from the initial so. which is common for the episodic MDP

---

action at Sn, is we have Thi EyE, The where rh ~ R/,(-18h,, n (a)) with support on [0, and mean rf (8h, n (a)), and a set of transition matrices {PA he(H such that Pr(8'1s, a) 11 (x (s |s, nf (a)). In other words, at each timestep and state S, the players are in congestion game. Meanwhile, each facility has its own state and independent state transition, which only depends on its current state and number of players using that facility. This transition kernel can be viewed special case of that in factored MDPs [Szita and Lörinez, 2009]. The IMCG also admits two types of feedback, semi bandit feedback and bandit feedback, just like the congestion game. In this paper, we will consider both types of feedback.
6.2 Theoretical Guarantee
Summarized in Algorithm 5, centralized algorithm for IMCGs is naturally extended from the Nash-UCB (Algorithm 1) by incorporating transition kernel estimators, corresponding bonus terms and Bellman backward update. The key idea is to utilize the independent transition structure to remove the dependence on the exponential size of the state space S = II S We tackle this issue by adapting technique from factored MDP [Chen et al., 2020]. The algorithmic details for both types of feedback are deferred into Appendix E. The Nash regret bounds for the two versions of Algorithm 5 are stated in Theorem and the proof details are deferred to Appendix F.
Theorem 3. For independent Markov congestion game with semi-bandi feedbuck, by running the achieve that
centralized Algorithm 5. with probability at least 1 1 8.
H Σ (s 1#1
Nash-Regrea K) SO Σ
FS' VmH3T JEF
+ +
Furthermore, if we only have bandit feedback, then by running Algorithm 5 with reward estimator and bonus term (12) and (13), with probability at least we can achieve that
m² H2F Σ (st 178
Nash- (esse-)egre(())) S SŌ
FS$ VT Σ FEF
+Õ
The regret bound in [Liu al., 2021] can be exponential in F. Our bounds have polynomial dependence all the parameters.
(I where both A, and S IIyEF S
Conclusion
In this paper, we study sample-efficient learning in congestion games by utilizing the special reward structure. We propose both centralized and decentralized algorithms for congestion games with two types of feedback, all achieving sample complexities only polynomial in the number of facilities. To the best of our knowledge, each one of them is the first sumple-efficiee learning algorithm for congestion games in its own setting. We further define the independent Markov congestion game (IMCG) a natural extension of the congestion game into the Markov setting together with sample-efficient centralized algorithm for both types of feedback.
One promising future direction is to find sample-efficient decentralized algorithm such that from each player's own perspective, the algorithm is still no-regret. other words, diminishing regret is guaranteed for the player by running this algorithm even though other players may use policies from different algorithms. Another important future direction is find sample-efficient central- ized/decentralized algorithms that can explicitly find an approximate Nash equilibrium policy.
Acknowledgements
We sincerely thank Jing Dong for pointing out mistake in the initial draft of this paper. This work was supported in part by NSF TRIPODS II-DMS 2023166, NSF CCF 2007036, NSF IIS 21 2110170, NSF DMS 2134106, NSF CCF 2212261, NSF IIS 2143493, NSF CCF 2019844.
10

---

References
Hayder AA Al-Kashoush, Maryam Hafeez, and Andrew H Kemp. Congestion control for 6lowpan
networks: A game theoretic framework. IEEE internet of things journal, 4(3):760-771, 2017.
Yu Bai and Chi Jin. Provable self-play algorithmss for competitive reinforcement learning. In International conference on machine learning, pages 551-560. PMLR, 2020.
Sebastian Bervoets, Mario Bravo, and Mathieu Faure. Learning with minimal information in continuous games. Theoretical Economics, 15(4): 1471-1508, 2020.
Mario Bravo, David Leslie, and Panayotis Mertikopoulos, Bandit learning concave n- n-person games. Advances in Neural Information Processing Systems, 31, 2018.
Shicong Cen, Fan Chen, and Yuejie Chi. Independent natural policy gradient methods for po- tential games: Finite-time global convergence with entropy regularization. arXiv preprint 2rX1v:2204.05466, 2022.
Po-An Chen and Chi-Jen Lu. Playing congestion games with bandit feedbacks. In AAMAS, pages 1721-1722, 2015.
Po-An Chen and Chi-Jen Lu. Generalized mirror descents in congestion games. Artificial Intelligence, 241:217-243, 2016.
Xiaoyu Chen, Jiachen Hu, Lihong Li, and Liwei Wang. Efficient reinforcement learning in factored mdps with application to constrained rl. arXiv preprint arXiv:2008. 13319, 2020.
Yun Kuen Cheung and Georgios Piliouras. Chaos, extremism and optimism: Volume analysis of learning in games. Advances in Neural Information Processing Systems, 33:9039- 9049, 2020.
Roberto Cominetti, Emerson Melo, and Sylvain Sorin. A payoff-hased learning procedure and its application to traffic games. Games and Economic Behavior, 70(1):71-83, 2010.
Pierre Coucheney. Bruno Gaujal, and Panayotis Mertikopoulos, Penalty-regulated dynamics and robust learning procedures in games. Mathematics of Operations Research, (003):611-633 2015,
Constantinos Daskalakis. On the complexity of approximating nash equilibrium. ACM Transactions on Algorithms (TALG), 93))1-35, 2013.
Dongsheng Ding, Chen-Yu Wei, Kaiging Zhang, and Mihailo R. Jovanović. Independent policy gradient for large-scale markov potential games: Sharper rates, function approximation, and game-agnostic convergence, 2022.
Dmitriy Drusvyatskiy, Maryam Fazel, and Lillian J Ratliff. Improved rates for derivative free gradient play in strongly monotone games. In Proc. IEEE Conference on Decision and Control, 2022.
Stéphane Durand. Analysis of Best Response Dynamics in Potential Games. PhD thesis, Université Grenoble Alpes, 2018.
Dimitris Fotakis, Spyros Kontogiannis, Elias Koutsoupias, Marios Mavronicolas, and Paul Spirakis. The structure and complexity of nash equilibria for a selfish routing game. International Colloquium on Automata, Languages, and Programming, pages 123-134. Springer, 2002.
Roy Fox, Stephen McAleer, Will Overman, and Ioannis Panageas. Independent natural policy gradient always converges in markov potential games. arXiv preprint 11Xiv:2110.10614, 2021.
Amélie Heliou, Johanne Cohen, and Panayotis Mertikopoulos. Learning with bandit feedback in potential games. Advances in Neural Information Processing Systems, 30, 2017.
Christian Ibars, Monica Navarro, and Lorenza Giupponi. Distributed demand management in smart grid with a congestion game. In 2010 First IEEE International Conference on Smart Grid Communications, pages 495-500. IEEE, 2010.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael Jordan. q-learning provably efficient? Advances in neural information processing systems, 31, 2018.

---

Chi Jin, Qinghua Liu, Yuanhao Wang, and Tiancheng Yu. V-learning simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint arXiv:2110.14555, 2021a.
Chi Jin, Qinghua Liu,, Yuanhao Wang, and Tiancheng Yu. V-learning a simple, efficient, decentral- ized algorithm for multiagent rl, 2021b.
Ramesh Johari and John Tsitsikiis. Efficiency loss in a network resource allocation game. Mathe- matics of Operations Research, (9(3):4074435 2004.
Robert Kleinberg, Georgios Piliouras, and Éva Tardos. Multiplicative updates outperform generic no-regret learning in congestion games. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 533-542, 2009.
Walid Krichene, Benjamin Drighès, and Alexandre Bayen. On the convergence of no-regret learning in selfish routing. In International Conference on Machine Learning, pages 163-171, PMLR,
2014.
Walid Krichene, Benjamin Drighès, and Alexandre M Bayen. Online learning of nash equilibria in congestion games. SIAM Journal on Control and Optimization, 53(2):1056-1081, 2015.
Tor Lattimore and Csaba Szepesvári. Bandit algorithms. Cambridge University Press, 2020.
Stefanos Leonardos, Will Overman, Ioannis Panageas, and Georgios Piliouras. Global convergence of multi-agent policy gradient in markov potential games, 2021.
David S Leslie. Reinforcement learning in games. PhD thesis, University of Bristol, 2004.
David S Leslie and Edmund Collins. Individual q-learning in normal form games. SIAM Journal on Control and Optimization, 44(2):495-55 2005.
David S Leslie and Edmund J Collins. Generalised weakened fictitious play. Games and Economic Behavior, 56(2):285 298, 2006.
Qinghua Liu, Tiancheng Yu, Yu Bai, and Chi Jin. A sharp analysis of model-based reinforcement learning with self-play. In International Conference Machine Learning, pages 7001-7010. PMLR, 2021.
Sergio Valcarcel Macua, Javier Zazo, and Santiago Zazo. Learning parametric closed-loop policies markov potential games. arXiv preprint arXiv:1802.00899 2018.
Jason Marden. State based potential games. Automatica, 48(12):3055-3083 2012.
Dov Monderer and Lloyd S Shapley. Potential games. Games and economic behavior, 14(1):124-14) 1996.
Hukukane Nikaidó and Kazuo Isoda. Note on non-cooperative convex games. Mathematics, 5($1):807-81) 1955.
Pacific Journal of
Francesco Orabona. A modern introduction online learning. arXiv preprint 2019.
Ian Osband and Benjamin Van Roy. Near-optimal reinforcement learning in factored mdps. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
Arvind Raghunathan, Anoop Cherian, and Devesh Jha. Game theoretic optimization via gradient- based nikaido-isoda function. In International Conference on Machine Learning, pages 5291-53000 PMLR, 2019.
Aviv Rosenberg and Yishay Mansour. Oracle-efficient regret minimization in factored mdps with unknown structure. Advances in Neural Information Processing Systems, 34, 2021.
Robert W Rosenthal. A class of games possessing pure-strategy nash equilibria. International Journal of Game Theory, 2(1))65-67, 1973.
12

---

Tim Roughgarden. Algorithmic game theory. Communications of the ACM, 53(7)788-8)) 86, 2010.
Tim Roughgarden and Éva Tardos. Bounding the inefficiency of equilibria in nonatomic congestion games. Games and economic behavior, 47(2):389-44) 403, 2004.
Aviad Rubinstein. Settling the complexity of computing approximate two-player nash equilibria. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 258-265. IEEE, 2016.
Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10): 1095-1100, 1953.
Ziang Song, Song Mei, and Yu Bai. When can we learn general-sum markov games with a large number of players sample-efficienlyy? arXiv preprint arXiv:2110.04184 2021.
Brian Swenson, Ryan Murray, and Soummya Kar. On best-response dynamics in potential games. SIAM Journal on Control and Optimization, 56(4):2734-2767, 2018.
István Szita and András Lörinez. Optimistic initialization and greediness lead to polynomial time learning in factored mdps. Proceedings of the 26th annual international conference on machine learning, pages 1001-1008, 2009.
Yi Tian, Jian Qian, and Suvrit Sra. Towards minimax optimal reinforcement learning in factored markov decision processes. Advances in Neural Information Processing Systems, 13:19896-19907, 2020.
Ziping Xu and Ambuj Tewari. Reinforcement learning in factored mdps: Oracle-efficient algorithms and tighter regret bounds for the non-episodic setting. Advances in Neural Information Processing Systems, 33:18226-188 18236, 2020.
Kaiqing Zhang, Zhuoran Yang. and Tamer Basar. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, pages 321-384, 2021a.
Mingrui Zhang. Zebang Shen, Aryan Mokhtari, Hamed Hassani, and Amin Karbasi. One sample stochastic frank-wolfe. In International Conference on Artificial Intelligence and Statistics, pages 4012-4023. PMLR, 2020.
Runyu Zhang, Zhaolin Ren, and Na Li. Gradient play in stochastic games: stationary points, convergence, and sample complexity. arXiv preprint urXiv:2106.00190 2021b.
13

---

Checklist
1. 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]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits. hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
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? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(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]
14


Reviews:
[{"review_id": "lumbTe0i0Kw", "reviewer": "Reviewer_KcbX", "summary": "This work studies the problem of learning in repeated congestion games and proposes the first efficient algorithms with good regret guarantees for the following cases\n- centralized case with both bandit and semi-bandit feedback\n- decentralized case with both bandit and semi-bandit\n- centralized case for Markov congestion games with both bandit and semi-bandit feedback", "questions": "My main questions regard the claims of good \"sample complexity\" as explained in the weaknesses section.\n\n----- Minor comments -----\n\n1) In definition 3, I think it would be good to precise the dependency on pi of the Nash regret, as it depends on it both in the cumulated reward (second term), but also in the baseline reward (first term).\n\n2) How can we efficiently compute the solution of eq (5) ? Also, there seems to be a typo line 283 as I believe the = sign should be an inequality?\n\n3) In Theorems 1 and 2, what are the dependencies of the regret in delta ?", "limitations": "Not concerned", "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\nThis work provides first good efficient algorithms for several version of online congestion games.\nThe used techniques are nice and natural. The claimed results seem sound.\n\n---- Weaknesses ----\n\n1) One of the main novelty of this paper comes from what is called \"sample complexity\" by the authors, but I am not even sure what they do refer by this word. It seems to me that they meant \"computational complexity\", but I might be wrong. In any case, there seems to be no further discussion on the \"sample complexity\" results after the introduction. It is a major point of this work as shown in the Table page 2, and I think the authors should explain in details (at least for one or two algorithms) why these complexity bounds do hold.\n\n2) If my interpretation is correct and the authors did refer to computational complexity, it then seems that simulations (on a toy model) would be required to illustrate the fact that these methods can be efficiently implemented. Otherwise, this suggests that the claimed efficient algorithms are actually not that efficient.", "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": "VfaulB5imFa", "reviewer": "Reviewer_P7XP", "summary": "This paper studies congestion games which has wide application in practice. The authors propose novel algorithms for learning the congestion game with semi-bandit or bandit feedbacks, i.e., the centralized algorithm and the decentralized algorithm. They define a new problem, Markov congestion game, and propose a centralized algorithm to learn the Markov congestion game. They further derive the upper bounds of the learning regret and the sample complexity for the above problems, which are independent of the size of the action set.", "questions": "Please see the above section.", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper studies the congestion game learning with (semi-)bandit problems, whose regret and sample complexity are not well understood before. Novel algorithms different from the existing UCB-type method are proposed to solve the corresponding problem. And the theoretical results are novel, which does not depend on the size of the action set and thus avoids the curse of exponential action set. Therefore, the theoretical contribution of this submission is significant. Moreover, this paper is well written and the structure is clear to the readers. Besides these strengths, I also have several questions regarding this paper:\n\n(1) Can we still propose a UCB-type algorithm for the decentralized case? If not, what is the major obstacle of designing the UCB-type algorithm and what is the technical advantage of using FW + G-optimal design to solve this problem comparing to the UCB-type algorithm?\n\n(2) The sample complexity for the algorithms with FW still has high-order dependence on m and F. Is it possible to lower the order of powers in the dependence on m and F?", "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": "1FFu5ZeBdjD", "reviewer": "Reviewer_1yNk", "summary": "This paper studies the problem of learning Nash equilibria in congestion games and in independent Markov congestion games, where the latter are a simple and natural generalization of congestion games to the Markov setting. The authors propose both centralized and decentralized algorithms for congestion games, whose sample complexity does not depend on the number of players’ actions (which in this setting can be exponential in the size of the game representation). The algorithms work under both semi-bandit feedback (the players observe the cost of each facility they choose) and bandit feedback (the players only observe the overall cost of all the facilities they select). Then, the authors generalize their centralized algorithms to the independent Markov congestion game setting, obtaining sample complexities that do not depend on the number of players’ actions.\n", "questions": "1) Can you provide me some intuition as to why you techniques cannot be used if one wants to minimize the regret of each player rather than the (overall) Nash regret as you are doing?\n", "limitations": "I think there are not limitations and potential negative societal impact for this work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "ORIGINALITY\n\n(+) The paper provides the first algorithms for learning Nash equilibria with bandit feedback in congestion games whose sample complexities guarantees do not depend on the number of players’ actions.\n\n(-) The tools used in order to derive the main results in the paper are rather straightforward adaptations of commonly-used techniques: the centralized algorithms work by exploiting the optimism in face of uncertainty principle, while the decentralized ones leverage the Frank-Wolfe method, the G-optimal design, and the specific structure of rewards in congestion games. \n\nQUALITY\n\n(+) As far as I am concerned, the technical results are correct and adequately commented.\n\nCLARITY\n\n(+) The quality of writing is sufficiently good, even though there are some typos and grammatical errors that I invite the authors to spot by a simple applications of free spell checking tools.\n\n(-) The presentation of the results is hard to follow in some parts. I think the main problem is that more than half of the paper is devoted to introducing models and notation, while only the last three pages are reserved for the main technical results. I think that maybe the authors should try to amend this issue by removing some notation that is not needed in the main paper and putting it in the appendix. \n\nSIGNIFICANCE\n\n(+) The results presented in the paper are significant since they considerably improve over already known sample complexities results for learning Nash equilibria with bandit feedback in congestion games.\n\n(-) One of the main drawback (in my opinion) of the paper is that the decentralized algorithms do not extend to independent Markov congestion games. I think this is a major missing point and I am questioning whether it is worth devoting so much space in the paper to them even if the main decentralized algorithms do not work in that setting. Maybe it is better to concentrate on the simple congestion games model where all the algorithms are shown to work.\n\n(-) The results can be of interest only for a small portion of the NeurIPS community, in particular to those interested in algorithmic game theory and online learning.\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": {}}]

Author rebuttal:

Decision: Accept