Offline Congestion Games: How Feedback Type Affects Data Coverage Requirement
Authors: Haozhe Jiang
Qiwen Cui
Zhihan Xiong
Maryam Fazel
Simon Shaolei Du
Venue: ICLR 2023 poster (2023)

Abstract: This paper investigates when one can efficiently recover an approximate Nash Equilibrium (NE) in offline congestion games. The existing dataset coverage assumption in offline general-sum games inevitably incurs a dependency on the number of actions, which can be exponentially large in congestion games. We consider three different types of feedback with decreasing revealed information. Starting from the facility-level (a.k.a., semi-bandit) feedback, we propose a novel one-unit deviation coverage condition and show a pessimism-type algorithm that can recover an approximate NE. For the agent-level (a.k.a., bandit) feedback setting, interestingly, we show the one-unit deviation coverage condition is not sufficient. On the other hand, we convert the game to multi-agent linear bandits and show that with a generalized data coverage assumption in offline linear bandits, we can efficiently recover the approximate NE. Lastly, we consider a novel type of feedback, the game-level feedback where only the total reward from all agents is revealed. Again, we show the coverage assumption for the agent-level feedback setting is insufficient in the game-level feedback setting, and with a stronger version of the data coverage assumption for linear bandits, we can recover an approximate NE. Together, our results constitute the first study of offline congestion games and imply formal separations between different types of feedback.

Published as a conference paper at ICLR 2023
OFFLINE CONGESTION GAMES: HOW FEEDBACK TYPE AFFECTS DATA COVERAGE REQUIREMENT
Haozhe Jiang" Qiwen Cui²- Zhihan Xiong²
Maryam Fazel² Simon S. Du²
Institute for Interdisciplinary Information Sciences, Tsinghua University
University of Washington
ABSTRACT
This paper investigates when one can efficiently recover an approximate Nash Equilibrium (NE) in offline congestion games. The existing dataset coverage assumption in offline general-sum games inevitably incurs dependency on the number of actions, which can be exponentially large in congestion games. We consider three different types of feedback with decreasing revealed information. Starting from the facility-level (a.k.a., semi-bandil feedback, we propose novel one-unit deviation coverage condition and show a pessimism-type algorithm that can recover approximate NE. For the agent-level (a.k.a., bandit) feedback set- ting, interestingly. we show the one-unit deviation coverage condition is not suf- ficient. On the other hand, we convert the game to multi-agent linear bandits and show that with a generalized data coverage assumption in offline linear bandits, we can efficiently recover the approximate NE. Lastly, we consider novel type of feedback, the game-level feedback where only the total reward from all agents is revealed. Again, we show the coverage assumption for the agent-level feed- back setting is insufficient in the game-level feedback setting, and with stronger version of the data coverage assumption for linear bandits, we can recover an ap- proximate NE. Together, our results constitute the first study of offline congestion games and imply formal separations between diffcrent types of feedback.
INTRODUCTION
Congestion game a special class of general-sum matrix games that models the interaction of players with shared facilities (Rosenthal 1973). Each player chooses some facilities to utilize, and each facility will incur a different reward depending on how congested it is. For instance, in the routing game (Koutsoupias & Papadimitriou 1999), each player decides a path to travel from the starting point to the destination point in a traffic graph. The facilities are the edges and the joint decision of all the players determines the congestion in the graph. The more players utilize one edge, the longer the travel time on that edge will be. As one the most well-known classes of games, congestion game has been successfully deployed in numerous real-works applications such as resource allocation (Johari & Tsitsiklis) 2003), electrical grids (Ibars et al. (2000) and cryptocurrency ecosystem (Altman al. 2019).
Nash equilibrium (NE), one of the most important concepts in game theory (Nash Jr 1950). char- acterizes the emerging behavior in a multi-agent system with selfish players. is commonly known that solving for the NE is computationally efficient in congestion games as they are isomorphic to potential games (Monderer & Shapley 1996). Assuming full information access, classic dynamics such as best response dynamics (Fanelli li et al. 2008), replicator dynamics (Drighes et al. 2014) and no-regret dynamics (Kleinberg et al. (2009) provably converge to NE in congestion games. Recently Heliou et al. (2017) and Cui et al. (2022) relaxed the full information setting to the online (semi-) bandit feedback setting, achieving asymptotic and non-asymptotic convergence, respectively. It is worth noting that Cui et al. (2022) proposed the first algorithm that has sample complexity indepen- dent of the number of actions.
"Equal contribution.

---

Published as a conference paper at ICLR 2023
Offline reinforcement learning has been studied in many real-world applications (Levine et al. 2020). From the theoretical perspective, a line of work provides understanding of offline single- agent decision making, including bandits and Markov Decision Processes (MDPs), where searchers derived favorable sample complexity under the single policy coverage (Rashidinejad et al.) [202 Xie et al., 2021b). However, how to learn in offline multi-agent games with offline data is still far from clear. Recently, the unilateral coverage assumption has been proposed as the minimal as- sumption for offline zero-sum games and offline general-sum games with corresponding algorithms to learn the NE (Cui & Du 2022a bj Zhong et al. 2022). Though their coverage assumption and the algorithms apply the most general class of normal-form games, when specialized to congestion games, the sample complexity will scale with the number of actions, which can be exponentially large. Since congestion games admit specific structures, one may hope to find specialized data coverage assumptions that permit sample-efficient offline learning.
In different applications, the types of feedback, i.e., the revealed re- ward information, can be different in the offline dataset. For instance, the dataset may include the reward of each facility, the reward of each player, or the total reward of the game. With decreasing informa- tion contained in the dataset, differ- coverage assumptions and algo- rithms are necessary. In addition, the main challenge in solving congestion games lies in the curse of an expo- nentially large action set, as the num- ber of actions can be exponential in the number of facilities. In this work, aim to answer the following question:
Weak Covariance Domination
Strong Covariance Domination
One-Unit Deviation
Facility-Level Agent-I.eve Game-Level
X
X
Table 1: A summary of how data coverage assumptions af- fect offline learnability. In particular, V represents under this pair of feedback type and assumption, an NE can be learned with sufficient amount of data; on the other hand, X rep- resents there exists some instances in which NE cannot be learned no matter how much data is collected.
When can we find approximate NE in offline congestion games with different types of feedback, without suffering from the curse of large action set?
We provide an answer that reveals striking differences between different types of feedback.
1.1 MAIN CONTRIBUTIONS
We provide both positive and negative results for each type of feedback. See Table for summary.
Three types of feedback and corresponding data coverage assumptions. We consider three types of feedback: facility-level feedback, agent-level feedback and game-level feedback to model different real-world applications and what dataset coverage assumptions permit finding an approxi- mate NE. In offline general-sum games, Cui & Du (202bb proposes the unilateral coverage assump- tion. Although their result can be applied to offline congestion games with agent-level feedback, their unilateral coverage coefficient is at least large as the number of actions and thus has an ponential dependence on the number of facilities. Therefore, for each type of feedback, we propose corresponding data coverage assumption to escape the curse of the large action set. Specifically: Facility-Leve Feedback: For facility-level feedback, the reward incurred in each facility is pro- vided the offline dataset. This type of feedback has the strongest signal. We propose the One-Uni Deviation coverage assumption (cf. Assumption 2 for this feedback.
Agent-Level Feedback: For leent-level feedback, only the sum of the facilities' rewards for each agent is observed. This type of feedback has weaker signals than the facility-level feedback does, and therefore we require stronger data coverage assumption (cf. Assumption 4
Game-Level Feedback: For the game-level feedback, only the sum of the agent rewards is ob-
tained. This type of feedback has the weakest signals, and we require the strongest data coverage assumption (Assumption 5)
Notably, for the latter two types of feedback, we leverage the connections between congestion games and linear bandits.
2

---

Published as a conference paper at ICLR 2023
2. Sample complexity analyses for different types of feedback. We adopt the surrogate mini- mization idea in Cui & Du (2022b) and show a unified algorithm (cf. Algorithm I with carefully designed bonus terms tailored to different types of feedback can efficiently find an approximate NE, therefore showing our proposed data coverage assumptions are sufficient. For each type of feedback, give a polynomial upper bound under its corresponding dataset coverage assumption.
3. Separations between different types of feedback. To rigorously quantify the signal strengths in the three types of feedback, we provide concrete hard instances. Specifically, we show there exists a problem instance that satisfies Assumption [ but with only agent-level feedback, we prov- ably cannot find an approximate NE, yielding a separation between the facility-level feedback and the agent-level feedback. Furthermore, we also show there exists problem instance that satisfies Assumption
4 but with only game-level feedhack, we provably cannot find an approximate NE, yielding separation between the agent-level feedback and game-level feedback.
In addition, we also provide several concrete scenarios exemplify and motivate the aforemen- tioned three types of feedback, which can be found in Appendix
1.2 RELATED WORK
Potential Games and Congestion Games. Potential games are a special class of normal-form games with potential function to quantify the changes in the payoff of each player and deterministic NE is proven to exist (Monderer Shapley] (996). Asymptotic convergence
the NE can be
achieved by classic game theory dynamics such as best response dynamic (Durand 2018 Swenson jet al. (2018), replicator dynamic (Sandholm et al., |0008] Panageas & Piliouras] 2016) and no-regret dynamic (Heliou al. (017). Recently, Cen et al. (2021) proved that natural policy gradient has a convergence rate independent of the number of actions in entropy regularized potential games. Anagnostides et al. (2022) provided the non-asymptotic convergence rate for mirror descent and
O(1) individual regret for optimistic mirror descent.
Congestion games proposed in the seminal work (Rosenthal 1973) and the equivalence with potential games is proven in (Monderer & Shapley 1996). Note that congestion games can have ex- ponentially large action sets, efficient algorithms for potential games are not necessarily efficient for congestion games. Non-atomic congestion games consider separable players, which enjoy a convex potential function if the cost function non-decreasing (Roughgarden & Tardos 2004). For atomic congestion games, the potential function is usually non-convex, making the problem more difficult. (Kleinberg et al. 2009; Krichene et al. 2014) show that no-regret algorithms asymptoti- cally converge to NE with full information feedback and (Krichene et al., 2015) provide averaged iterate convergence for bandit feedback. (Chen & Lu 2016)) provide -onasyymtooiic conver- gence by assuming the atomic congestion game is close to non-atomic one, and thus approximately woweecoonnidenebonnnee
enjoys the convex potential. Recently, [ui et al. (2022) first proposed an type algorithm and Frank- Frank-Wolfe-tyy Wolfe-type algorithm that has convergence rate without dependence on the number of actions for mani-b feedback and bandit feedback settings, respectively. To the best of knowledge, all of these works either consider the full information setting or the online feedback setting instead of the offline setting in this paper.
Offline Bandits and Reinforcement Learning. For related works in empirical offline reinforce- ment learning, interested readers can refer to (Levine et al., 2020). From the theoretical perspective, researchers have been putting efforts into understanding what dataset coverage assumptions allow for learning the optimal policy. The most basic assumption is the uniform coverage, i.e., every state- action pair is covered by the dataset (Szepesvári & Munos 2005). Provably efficient algorithms have been proposed for both single-agent and multi-agent reinforcement learning (Yin et al. 22020] 2021 Ren et al., 2021; [iifford et al., 20200: Cui & Yang. 2021 Zhang et al.. 2020; (Subraaanian et al. 2021). In single-agent bandits and reinforcement learning, with the help of pessimism, only single policy coverage is required, i.e., the dataset only needs to cover the optimal policy (Jin et al.)
202 Rashidinejad et al.] 2021 Xie et al.] 202 a). For offline multi-agent Markov games, Cui & Du (2022a) first show that it is impossible to learn with the single policy coverage and they identify the unilateral coverage assumption the minimal coverage assumption while Zhong et al.) (2022);
Xiong et al. (2022) provide similar results with linear function approximation. Recently, Yan et al.
(002)) CCi & Du (0022)) give minimax sample complexity for offline zero-sum Markov games.
3

---

Published as a conference paper at ICLR 2023
In addition, Cui & Du (2022b) proposes an algorithm for offline multi-playe general-sum Markov games that do not suffer from the curse of multiagents.
PRELIMINARY
2.1 CONGESTION GAME
General-Sum Matrix Game. A general-sum matrix game is defined by a tuple G = ((A.)) where m is the number of players, A; is the action space for player i and R(-(a) is a distribution over [0, T'ax yn with mean r(a). When playing the game, all players simultaneously select actions, constituting joint action a and the reward is sampled as r ~ R(((a), where player i gets reward ri.
A - -I= A; A joint policy is distribution with n, E (AA),, where ((x)) denotes the probability simplex over X. If the players follow a л. The expected return of player
A(A) while product policy is X ;=1 T
policy オ, their actions are sampled from the distribution under some policy π is defined as value V = Eawn [a)r]ri(a)]]
Let T-; be the joint policy of all the players except for player i. The best response of the player i to policy T- is defined as म. f. = arg maA,) V. Here μ is the policy for player and (n, T-)) constitutes joint policy for all players. We can always set the best response to be a pure
strategy since the value function is linear in μ.. We also denote Viti5= V," s as the best response value. To evaluate a policy म, we use the performance gap defined as
Gap(#)
max (E(m]
V -. V.
A product policy is e-approximate NE if Gap(T) S e. A product policy is an NE if Gap(z) 0. Note that is possible to have multiple Nash equilibria in one game.
Congestion Game. A congestion game is general-sum matrix game with special structures. In particular, there is a facility set FF such that a S F for all a E A., meaning that the size of A, can at most be 2", where F [F]. A set of facility reward distributions {RC {R (-In) E N) JEF associated with each facility f. Let the number of players choosing facility f in the action be n (a) = - 1 {f E a.). where is the joint action. A facility with specific number of players selecting said to a configuration on f. Two joint actions where the same number of players selecting f are said to have the same configuration on f. The reward associated with facility ʃ is sampled by rf ~ Rf (-In (a)) and the total reward of player is r, = E, rf. With slight abuse of notation, r (n) be the mean reward that facility ʃ generates when there are n players choosing it. We further assume the support of R! (-In) is [-1.1] for all n [m]] is well known that every congestion game has pure strategy NE.
The information we get from the game each episode is (a*, r*),, where a is the joint action and * contains the reward signal. In this paper, we will consider three types of reward feedback in congestion games, which essentially make r different in each data point (a*,r*).
Facility-Level Feedback (Semi-Bandit Feedback): In each data point (at r²),, net contains reward received from each facility f E U at meaning that p.th = [r/sk) SEU' af.
Agent-Level Feedback (Bandit Feedback): each data point (at, rd) rd contains reward received by each player, meaning that و {r++) 1==1" where r = Eyeu, r..kk
Game-Level Feedback: each data point (a k r²),, p. contains only the total reward received by all players, meaning that n. Σm r which becomes a scalar. This type of feedback is the minimal information we can get and has not been discussed in previous literature.
2.2 OFFLINE MATRIX GAME
Offline Matrix Game. In the offline setting, the algorithm only has access an offline dataset D {aat, r.) )²))" collected by some exploration policy p in advance.
4

---

Published as a conference paper at ICLR 2023
A joint action a is said to be covered if p(a) 0. Cui & Du (022a)) has proved that the following assumption is minimal dataset coverage assumption to learn an NE in a general-sum matrix game. The assumption requires the dataset to cover all unilaterally deviated actions from one NE. Assumption 1. There exists an NE π such that for any player and policy n; E A(A), a covered by p as long as (Tt, π (a)) > 0.
Cui & Du 2022b provides sample complexity result for matrix games with dependence C(r²), where ((T) quantifies how well π is unilaterally covered by the dataset. The definition is as follows.
Definition 1. For strategy a and satisfying Assumption 7 the unilateral coefficient defined as
TT<)
C(T) =
(, (()))(
max
p(a)
(1)
Surrogate Minimization. Cui & Du (022b) proposed algorithm called Strategy-wise Bonus + Surrogate Minimization (SBSM) to achieve efficient learning under Assumption | SBSM moti- vates general algorithm framework for learning congestion games in different settings. First we design (a) which estimates the reward player i gets when the joint action is a. Offine bandit (reinforeement learning) algorithm usually leverages the confidence bound (bonus) to create pes- simistic estimate of the reward estimator, inducing conservatism in the output policy and achieving a sample-efficient algorithm. Here we formally define bonus as follows.
Definition 2. For any reward estimator F; A + TR that estimates reward with expectation Tù A R. b; A + R. is called the bonus term for f if for all i E [m]] A, with probability at least 1 - 8, it holds that
(r:(a) (a)) b((a).
The formulae for P; and b vary according to the type of feedback as discussed later sections. The optimistic and pessimistic values for policy æ and player are defined as
Ears
(a) + ba()),
V. = Ea-* (a) - ba)].
(3)
Finally, the algorithm minimizes max
L over the policy ग, which serves as a sur-
rogate of the performance gap (see Lemma T.. We summarize Algorithm [ Note that we only take the surrogate gap from SBSM but not the strategy-wise bomus, which is deliberately designed bonus term depending on the policy. Instead, we design specialized bonus terms by exploiting the unique structure of the congestion game, which will be discussed in detail in later sections.
Algorithm 1 Surrogate Minimization for Congestion Games
Require: Offline dataset D
1: Compute F(a), b(a) for all a E A according to the dataset D.
2: Compute the optimistic value V and pessimistic value V for all policy and player i by
3: Compute v!-=- maXA/EA(AA)
Vi 1
4: return arg min, max
The sample complexity of this algorithm is guaranteed by the following theorem. Theorem 1. Let 11 be the set of all deterministic policies and b is bonus termfor' f. With probability 8, it holds that
(x) + Ea by(a)) l'e
Gap(
<
max =E(ma
max
where x oupput is the output of Algorithm
Here, the expectation of bonus term over some policy reflects the degree uncertainty of the reward under that policy. Inside the operation min the first term is for unilaterally deviated policy from N that maximizes this uncertainty and the second term is the uncertainty for x. The full proof is deferred to Appendix B This theorem tells that if we want to bound the performance gap, we need to precisely estimate rewards induced by unilaterally deviated actions from the NE, which caters to Assumption
5

---

Published as a conference paper at ICLR 2023
3 OFFLINE CONGESTION GAME WITH FACILITY-LEVEL FEEDBACK
Recall that for Definition [ If æ is deterministic, the minimum value of ((x)) achieved when uniformly covers all actions achievable by unilaterally deviating from (see Proposition [ Since having o. deviating from can at least cover A, actions, the smallest value of C(x) scales with maX A,, which is reasonable for general-sum matrix game. However, this congestion games since the size of action space can exponential (A; S 2 As a result, covering all possible unilateral deviations becomes inappropriate.
acceptable for
Compared to general-sum games, congestion games with facility-level feedback inform us not only the total reward but also the individual rewards from all chosen facilities. This allows to estimate the reward distribution from each facility separately. Instead of covering all unilater- ally deviating actions a, only need make any such action a and any facility f E F, we cover some actions that share the same configuration with on This motivates the dataset coverage assumption on facil- ities rather than actions. particular, we quantify the fa- cility coverage condition and present the new assumption as follows.
5
5
5
5
5
4
4
4
4
3
3
3
for
2
2
2
1
1
1
1
52
f3
f+
fs
Figure I: Illustration of Assumption 2 There are five facilities and five players with full action space. The facility con- figuration in T is marked in red. The transparent boxes cover the facility con- figuration required in the assumption.
Definition 3. For strategy facility and integer n, the facility cumulative density is defined as
dg(())
Σ T(a).
(a)=n
Furthermore, a facility f is said to be covered by at n. if dn O.
Assumption 2 (One-Unit Deviation). There exists an NE X² such that for any player i, facility f and integer n., if there exists a policy E ((A) such that d - (n) > 0, we have dl (n((n) > 0.
In plain text, this assumption requires us to cover all possible facility configurations induced by unilaterally deviated actions. As mentioned in Section 2.1 we can always choose ' be deter- ministic. In the view of each facility, the unilateral deviation is either player who did not select it now selects it or a player who selected now does not select it. Thus for each f E F, it sufficient to cover configurations where the number of players selecting differs from that number of NE by 1. This why we call it the one-unit deviation assumption. The facility coverage condition visualized in Figure Meanwhile, Definition I adapted to this assumption as follows.
Assumption 3. There exists a constant
Cfscilit
and an NE π such that Cfacility
di (1)) where we use the convention that = O.
mf
The sample complexity bound depends on Ciscility (see Theorem 3 The minimum value of Ciasility is at most 3, which is acceptable (see Proposition 2) Furthermore, we show that no assumption weaker than the onc-unit deviation allows NE learning, as stated in the following theorem.
Theorem 2. Define a class X of congestion game M and exploration strategy p that consists of all M and pairs that Assumption 2 is satisfied except for most one configuration for one facility. For any algorithm ALG there exists (M, p) E such that the output of ALG at most a 1/2-NE strategy no matter how much data is collected.
Proof Sketch. Consider congestion games with a single facility f and five players. The action space for each player is (0, {f}}. We construct the following two congestion games with deterministic rewards. The facility coverage condition of NEs are marked using bold symbols in the table. The exploration policy is set to be
p(a)= = {
1/20 one, three four players select f. otherwise.

---

Published as a conference paper at ICLR 2023
Congestion Game 1:
(1)== W(2 13 #44=1 (1) Congestion Game (1) R1 =1 R13 (4) =1 R (5) -
These two games with are not distinguishable for ALGG Full proof is deferred to Appendix B
In the facility-level feedback setting, the bonus term is similar that from Cui et al. First, we count the number of tuples in dataset D with players choosing facility as N (n) EatED {n (a*) =n.. Then, we define the estimated reward function and bonus term as
2022
Diat rf frr (a*) = n (a)}
P((a)= = Σ
b((a)= = EV
NO (n (a)
fEa:
SEa:
Here , = 2 log( (0(g(4(m+)))) F1F/6)). The contribution for each term in b, mimics the bonus terms from the well-known UCB algorithm and the sample complexity bound provided by the following theorem.
Theorem 3. With probability 1 - 6, if Assumption is satisfied, it holds that
Gap( n (uuph))
S 8vm + Cfacittyy P/nn.
The proof of this theorem involves bounding the expectation by exploiting the special structure of congestion game. The actions can be classified by the configuration one facility. This helps bound the expectation over actions, which is essentially the sum over A, actions, by the number of players. Detailed proof is deferred to Section B in the appendix.
OFFLINE CONGESTION GAME WITH AGENT-LEVEL FEEDBACK
4.1 IMPOSSIBLLITY RESULT
In the agent-level feedback setting, we no longer have access to rewards provided by individual facilities, so estimating them separately is no longer feasible. From limited actions covered in the dataset, we may not be able to precisely estimate rewards for all unilaterally deviated actions, and thus unable to learn an approximate NE. This observation is formalized in the following theorem.
Theorem 4. Define class X of congestion game M and exploration strategy p that consists of all and p pairs such that Assumption is satisfied. For agent-level feedback, for any algorithm ALG there exists (M, p) E X such that the output of ALG is most 1 a //-aaproximaat NE matter how much data is collected.
Proof Sketch. Consider congestion game with two facilities f1, f2 and two players. Action space for both players is unlimited. We construct the following two congestion games with deterministic rewards. The facility coverage conditions for these NEs are marked by bold symbols in the tables. The exploration policy p is set be
R (2) = 1/2 (1(1)=1 =1
R = -1 R (1)
(2) = 1/4 R = -1/ R5((1 =1
Rfa
Congestion Game 3
Congestion Game 4
1/3
01 = 02 02 f2)
p(a1,az)
1/3
01 = (f1,,02 a2 = (J2) or a = a2
02 =
(4)
0 otherwise.
It can be verified that both fi and fa are covered at 1 and 2 as shown in Figure These two games look identical with agent-level feedback. Hence it is impossible for the algorithm to distinguish them. Detailed proof deferred to Appendix
4.2 SOLUTION VIA LINEAR BANDIT
7

---

Published as a conference paper at ICLR 2023
In the agent-level feedback setting, congestion game can be viewed as m linear bandits. Let be d-dimensional vector where d = mF and (ndr(() Ou+my. Let A, A (0, 1] and
(f1
(f2, 2)
1) (f2 1)
[A)a)) Hij = + mf.f f E a, n² (a)}
Figure 2: Facility coverage condition for p. Each pair (J, n) represents the configuration that n players select facility f. Each box con- tains the facility coverage condition for one player. There are two classes of covered ac- tions as described in the formula ( The color of each box represents the class of ac- tions it belongs to.
Here we assign each facility an index in 0,1,-...,
Then the mean reward for player i can be written as r:(a) = (a, 8). In the view of bandit problem, bandit and the action taken is a, which is identical for all bandits. fa(a)= = (A:(a), where can be estimated through ridge regression together with bonus term as follows,
the index of the
i V-
Σ
Σ
A,aa)) V
E E Arla Aa(a)) (a (at,rt)ED iE(m
(5)
(a r JED xE(m)
b:(a)= ||A((a))llvv))) 1- 13, where vB = 2vd Vdlog (1 mnF
+
(6)
d
Jin al. (2021) studied offline linear Markov Decision Process (MDP) and proposed sufficient coverage assumption for learning optimal policy. A linear bandit is essentially a linear MDP with only one state and horizon equals 1. Here we adapt the assumption to bandit setting and generalize it to congestion game in Assumption 4
Assumption 4 (Weak Covariance Domination). There exists constant Cagen 0 and an NE π such that for all E [m] and policy Te, it holds that
V 2 I + nCCgenBa-(n, [A(a)A(aa']]
To see why Assumption implies learnability, notice that the right hand side of (7 is equal to the expectation of the covariance matrix V if the data is collected by running policy (Tzj T for C Cagem? episodes. By using such a matrix, we can estimate the rewards of actions sampled from (T T" m",)) precisely via linear regression. Here, Assumption states that for all unilaterally deviated policy (Tj, n= m=j); we can estimate the rewards it generate at least as well as collecting data from (Tj, n" for Cl episodes, which implies that we can learn an approximate NE (see Theorem Tp. Under Assumption we can obtain the sample complexity bound as follows.
Theorem 5. If Assumptiin is satisfied, with probability 1 - 5, it holds that
mFB Cagourt
Gap(Touupuy S
<
where /B is defined in (6) and n oupput is the output of Algorithm 1.
Remark 1. As illustrative example, consider congestion game and full action space, i.e. A, 2F for all player with pure strategy NE. The dataset uniformly covers all actions where only one player deviates and only deviates on one facility. For example, if player chooses {/1 the dataset should cover player selecting {/i, {f2), (fi, f2, fz), {1,, f4). with other players unchanged. There
such actions for each player, so the dataset covers mF actions in total. The change in reward when a single player deviates from ग is the sum of change in reward from each deviated facility. With sufficient data, we can precisely estimate the change in reward from each deviated facility and estimate the reward from any unilaterally deviated action afterward. With high probability, Cagent for this example is no smaller than 1/2m/* (see Proposition 4 in the appendix). Hence with appropriate dataset coverage, our algorithm can achieve sample-efficient approximate NE learning in agent-level feedback.
OFFLINE CONGESTION GAME WITH GAME-LEVEL FEEDBACK
With less information revealed in game-level feedback, stronger assumption is required to lear an
approximate NE, which is formally stated in Theorem 6 The proof is similar to that of Theorem and we defer it to the Appendix D
8

---

Published as a conference paper at ICLR 2023
Theorem 6. Define class X of congestion game M and exploration strategy p that consists of all M and p pairs such that Assumption 4 is satisfied. For game-level feedback, feedbback for any algorithm ALG there exists (M, p) X such that the output of ALG is at least 1/ a/Aaappoxieaate NE matter how much data is collected.
In the game-level feedback setting, congestion game can be viewed as linear bandit. Let A : A {o, 1 a and A(a) = Eie(m) (a).) The game-level reward can be written as r(a) = (A(a), Thus, we can similarly use ridge regression and build bonus terms as follows.
Fr(a) (Ar(a),0). v
Σ A(at))
=
Σ A(a*),
(8)
(a JEE
(a ,)ED
(a(a) max |A(aa)ll-i where VB= =B=2vd Vd nm) + L. /E|ml
(9)
The coverage assumption is adapted from Assumption as follows.
Assumption (Strong Covariance Domination). There exists a constant Cgame > and an NE n
such that for all i E [m] and policy Ta it holds that
V I + ACggaeea--nann
[A(())A(a)))
(10)
Note that although the statement of Assumption is identical to that of Assumption 4 the definition of V has changed, so they are actually different. The interpretation of this assumption is similar to that of Assumption
It states that for all unilaterally deviated policy (m, =".), we can estimate the reward at least as well as collecting data from (#i, m==;) for Coupuul episodes with agent-level feedback. Under this assumption, we get the sample complexity bound as follows.
Theorem 7. If Assumption 5 is satisfied, with probability 1 - 5, it holds that
mFB
Gap( (uppu cuiput S
Ogameti"
where B is defined in equation and π nuipua is the output of Algorithm [
Remark As illustrative example, consider a congestion game with full action space and pure strategy NE. Let the numbers of players selecting each facility be (nı, f2,, ... n.)). The dataset uniformly contains the following actions: action where the number of players selecting each facility are (0, n........ ny); (n1 1, n22 ny), (m1 + 12, ,n and similar actions for other facili- ties. Besides, we cover an NE action. From this dataset, we can precisely estimate the reward from each single facility with one-unit deviation configuration from NE and hence estimate the reward of unilaterally deviated actions. With high probability, Ceame for this example is no smaller than 1/24r" (see Proposition 6 in the appendix). Hence with appropriate dataset coverage, our algorithm can achieve sample-efiiiien approximate NE learning in game-level feedback.
CONCLUSION
In this paper, studied NE learning for congestion games in the offline setting. We analyzed the problem under various types of feedback. Hard instances were constructed to show separations identified dataset coverage
between different types of feedback. For each type of feedback, assumptions to ensure NE learning. With tailored reward estimators and bonus terms, we showed the surrogate minimization algorithm is able find an approximate NE efficiently.
ACKNOWLEDGEMENT
This work was supported in part by NSF TRIPODS II-DMS 2023166, NSF CCF 2007036, NSF IIS 2110170, NSF DMS 21 2134106, NSF CCF 2212261, NSF IIS 2143493, NSF CCF 2019844.
REFERENCES
Eitan Altman, Alexandre Reiffers, Daniel S Menasche, Mandar Datar, Swapnil Dhamal, and Corinne Touati. Mining competition in a multi-cryptocurrency ecosystem at the network edge: a conges- tion game approach. ACM SIGMETRICS Performance Evaluation Review, 46(3): 117, 2019.

---

Published as a conference paper at ICLR 2023
Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina, and Tuomas Sandholm. On last-iterate convergence beyond zero-sum games. arXiv preprint arXiv:2203./20550 2022.
Dietrich Braess, Anna Nagurney, and Tina Wakolbinger. On a paradox traffic planning. Trans-
portation Science, 39(4):446 450, 2005. ISSN 00411655, 15265447. URL http://wwyy
jstor.org/stable/22222
Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 2021.
Po-An Chen and Chi-Jen Lu. Playing congestion games with bandit feedbacks. In AAMAS, pp- 1721-1722, 2015.
Po-An Chen and Chi-Jen Lu. Generalized mirror descents in congestion games. Artificial Intelli- gence, 241:217-243, 2016.
Qiwen Cui and Simon Du. When is offline two-player zero-sum markov game solvable? arXiv preprint arXiv:2201.03522 2022a.
Qiwen Cui and Simon S Du. Provably efficient offline multi-agent reinforcement learning via strategy-wise bonus. arXiv preprint arXiv:2206.00159, 2022b.
Qiwen Cui and Lin F Yang. Minimax sample complexity for turn-based stochastic game. In Uncer- tainty in Artificial Intelligence, pp. 1496-1504. PMLR, 2021.
Qiwen Cui, Zhihan Xiong, Maryam Fazel, and Simon S Du. Learning in congestion games with bandit feedback. arXiv preprint arXiv:2206.01888 2022.
Benjamin Drighes, Walid Krichene, and Alexandre Bayen. Stability of nash equilibria the con- gestion game under replicator dynamics. In 53rd IEEE Conference Decision and Control, pp- 1923-1929. IEEE, 2014.
Stéphane Durand. Analysis of Best Response Dynamics in Potential Games. PhD thesis, Université Grenoble Alpes, 2018.
Angelo Fanelli, Michele Flammini, and Luca Moscardelli. The speed of convergence in congestion games under best-response dynamics. International Colloquium on Automata, Languages, and Programming, pp. 796-807. Springer, 2008.
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 Smart Grid Com- munications, pp. 495-500. IEEE, 2010.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline RL? In International Conference Machine Learning, pp. 5084-5096. PMLR, 2021.
Ramesh Johari and John N Tsitsiklis. Network resource allocation and congestion game. In Proceedings of the Annual Allerton Conference on Communication Control and Computing, vol- ume 41, pp. 769-778. Citeseer, 2003.
Robert Kleinberg, Georgios Piliouras, and Éva Tardos. Multiplicative updates outperform generic no-regret learning in congestion games. In Proceedings of the forty-firs annual ACM symposium on Theory of computing, pp. $33-542. 2009.
Elias Koutsoupias and Christos Papadimitriou. Worst-case equilibria. In Annual symposium on theoretical aspects of computer science, pp. 404 413. Springer, 1999.
Walid Krichene, Benjamin Drighès, and Alexandre Bayen. On the convergence of no-regret learning in selfish routing. International Conference on Machine Learning, pp. 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, 5352) 2015.
10

---

Published as a conference paper at ICLR 2023
Tor Lattimore and Csaba Szepesvári. Confidence Bounds for Least Squares Estimators, pp. 219- 230. Cambridge University Press, 2020. doi: 10.1017/978 (088771401.02
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tuto- rial, review, and perspectives open problems. arXiv preprint arXiv:2005.01643 2020.
Dov Monderer and Lloyd S Shapley. Potential games. Games and economic behavior, 14(1):124- 143, 1996.
John Nash Jr. Equilibrium points in n-person games. Proceedings of the national academy of sciences, 36(1):48 49, 1950.
Ioannis Panageas and Georgios Piliouras. Average case performance of replicator dynamics in po- tential games via computing regions of attraction. In Proceedings of the 2016 ACM Conference on Economics and Computation, pp. 703-720, 2016.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline rein- forcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34, 2021.
Tongzheng Ren, Jialian Li, Bo Dai, Simon S Du, and Sujay Sanghavi. Nearly horizon-free offline reinforcement learning. 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-6) 67, 1973.
Tim Roughgarden and Éva Tardos. Bounding the inefficiency of equilibria in nonatomic congestion games. Games and economic behavior, 47(2):389-40) 2004.
William H Sandholm, Emin Dokumaeı, and Ratul Lahkar. The projection dynamic and the replicator dynamic. Games and Economic Behavior, 64(2):666-683, 2008.
Aaron Sidford, Mengdi Wang, Lin Yang, and Yinyu Ye. Solving discounted stochastic two-player games with near-optimal time and sample complexity. In International Conference on Artificial Intelligence and Statistics, pp. 2992-3002. PMLR, 2020.
Jayakumar Subramanian, Amit Sinha, and Aditya Mahajan. Robustness and sample complexity of model-based MARL for general-sum markov games. arXiv preprint arXiv:2110.02355, 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.
Csaba Szepesvári and Rémi Munos. Finite time bounds for sampling based fitted value iteration. In Proceedings of the 22nd international conference on Machine learning, pp. 880-887 2005.
Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman pessimism for offline reinforcement learning. Advances in neural information processing systems, 34:6683-6694, 2021a.
Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridg- ing sample-efficient offline and online reinforcement learning. Advances in neural information processing systems, 34, 2021b.
Wei Xiong, Han Zhong, Chengshuai Shi, Cong Shen, Liwei Wang, and Tong Zhang. Nearly mini- max optimal offline reinforcement learning with linear function approximation: Single-agent mdp and markov game. arXiv preprint vrXiv:2205.15522 2022.
Yuling Yan, Gen Li, Yuxin Chen, and Jianqing Fan. Model-based reinforcement learning is minimax-optimal for offline zero-sum markov games. arXiv preprint arXiv:2206.00 2022.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal provable uniform convergence in offline policy evaluation for reinforcement learning. arXiv preprint arXiv:2007.03766) 2020.
Ming Yin, Yu Bai, and Yu-Xiang Wang. Near-optimal offline reinforcement learning via double variance reduction. Advances in neural information processing systems, 34, 2021.

---

Published as a conference paper at ICLR 2023
Kaiqing Zhang, Sham Kakade, Tamer Basar, and Lin Yang. Model-based multi-agent RL in zero- sum markov games with near-optimal sample complexity. Advances in Neural Information Pro- cessing Systems, 33:1166-1178, 2020.
Han Zhong, Wei Xiong, Jiyuan Tan, Liwei Wang, Tong Zhang, Zhaoran Wang, and Zhuoran Yang. Pessimistic minimax value iteration: Provably efficient equilibrium learning from offline datasets. arXiv preprint arXhv:2202.075111 2022.
12

---

Published as a conference paper at ICLR 2023
A MOTIVATING EXAMPLES
In this section, we provide concrete scenarios for each type of feedback. Example 1 (Facility-level feedback). Suppose Google Maps is trying to improve its route assigning algorithm through historical data based on certain regions. Then, each edge (road) on the traffic graph of this region can be considered as a facility and the action that a user will take is path that connects a certain origin and destination. In this setting, the cost of each facility the waiting time on that road, which may increase as the number of users choosing this facility increases. In the historical data, each data point contains the path chosen by each user and his/her waiting time on each road, which is offline dataset with facility-level feedback.
Example (Agent-level feedback). Suppose a company trying learn a policy advertise its products from historical data. We can consider a certain set of websites as the facility set, and the products as the players. The action chosen for each product pany will place advertisements for that product. The reward for each product is measured by its sales. In the historical data, each data point contains the websites chosen for each product advertise- ment and the total amount of sales within a certain range of time. This offline dataset inherently has only agent-level feedback since the company cannot measure each website's ' contribution to sales.
subset of websites where the com-
Example (Game-level feedback). Under the same setting above, suppose now another company (called is also trying learn such a policy but lacks internal historical data. Therefore, B decides to use the data from the company mentioned in the above example (called A). However, since com- pany does have internal access company A's database, the precise sales of each product not visible to company B. As result, company B can only record the total amount of sales of all concerning products from company A's public financial reports, making its offline dataset have only the game-level feedback.
B OMITTED PROOF IN SECTION 3
Lemma 1.
With probability - 6, for any policy n,, we have
Gap(#) < max iE(m)
V
In addition, we have
Gap π nutputt
I min max sE(m]
V t
V
Proof. By 3 and 2). with probability 1
V S V SV¹
Hence
Gap(r) ( max (E(m)
V
V.T
< max max re(m]
V
Since both ViLTT and V are linear each entry of म, the first maximizer on the RHS must correspond to deterministic policy. This proves the first statement. The second statement by the fact that the algorithm minimizes the RHS of the first statement.
Theorem 1. Let 11 the set of all deterministic policies and is a bonus term With probability 1 - 8, it holds that
Gap( oupput
<
max max (x,, + Easx- bi(a)) =E(m]
where n. output is the output of Algorithm
Proof.
V E Banz (ri(a) F(((a) b.(a)) b((a)
13

---

Published as a conference paper at ICLR 2023
V Earn (i((a)
ri(a) b.(a)] 2Earrb((a).
Let = arg max,' max can always choose iT E II.
V
By similar argument in Lemma
we know that we
Gap oupptt S min max
V 1
V
a i6(m]
A V
min max
ve[m]
min max ve[m]
V. V V," + 2B (a (bb((a) + b.))
S min LiE[m]
max
V. V. V."
max ic(m!
2 -)b(a) + BBarrbi(a)]
min
GGap(T) i6fml
max
2
max e'elt
Ba (x/1 );((a) + 2B bi(a)
<Gap(Tr)
max imlm
max E. Ba-(at, (b(()))))))))) r'lll
+ 2E (((() b1(a)
=2 max mm|m]
max E (n, bi(a) + bi(a) La'Ell
Lemma 2. With probability - 6, we have
(r:(a) f:(a)) b:aa), (f S 4H
ndd
for all a E A,i [m]. FF, E [m].
Proof.
re(a) - F(((a) Σ (w' -r (n
/Ea.
By Hoeffding's bound and union bound we have
4(m + 1)F
pJ (n)(a)) - (nd (a))
S NJ (nd
log
8
for all E F.a A with probability statement hold with probability 8/2. By lemma A.1 of Xie et al. (2021b), replacing p by de (nd (a)) and the union bound get
8/2. Combine the above inequalities get the first
1 (1
8log(2(m + 1)F/88 (nd((n)
4u
<
ndy
(n)
for all f a,a A with probability 1 5/2. Finally, the proof is complete by using the union bound.
Theorem 3. With probability 1 - 8, if Assumption is satisfied, it holds that
Cap(Toupun
8/m m FC F/ /n.
Proof. We have
E, Ea-(r
Σ Ban(stia N (n v1 JeF
14

---

Published as a conference paper at ICLR 2023
4r2 ndly (nd)
facillity
Σ
dl (n'),
V
feJ
d' (n')
-CCnnilitty
JEF n'
m
Σ <2Cnnclity
m
dz (n')
72
fer
m/=0
<2/m + 1Ctucitity LF/ P//n
The first inequality is by Definition B (a) 1. Combine this with Theorem and Lemma
and Lemma
2
The second inequality by the fact that we get the conclusion.
Theorem 2. Define a class X of congestion game M and exploration strategy p that consists of all M and pairs that Assumption 2 is satisfied except for at most one configuration for one facility. For any algorithm ALG there exists (M. p) E such that the output of ALG most 1/2-NE strategy no malter how much data is collected.
Proof. Consider congestion game with a single facility f and five players. The action space for each congestion games with deterministic rewards.
player is {Ø, }. We construct the following Since there is only one facility, the reward players receive and whether a joint action is NE only depends the configuration, i.e. the number of players selecting f. Hence in the remaining part of the proof we will use configuration to describe the action. For the first game, there are two NEs, which are "only one player selecting f" and "all players selecting s" For the second game, the NE is "four players selecting f". The exploration policy is set to be
p(a) = 1/20 one, three or four players select f, otherwise.
For the first game, we cover the first NE and its unilateral deviation except for two players selecting
R(1)=1 =1 (2) =- -1 (3) =1 R4(4) =1 R(5)= = =1
Congestion Game
R(11= =1 R5 =1 R3 (4) R5 --1
Congestion Game
f. For the second game, cover the NE except for five players selecting f. Hence both game with p are X and are not distinguishable for ALG. Let the probability of the output policy selecting four players choosing f be p. Then it is least p-approximate NE for game and (1 p)-approximate NE for game In conclusion, there exists (M, p) E such that the output of ALG is at most 1/2-NE strategy no matter how much data is collected.
B. PURE NASH EQUILIBRIUM
is well known that pure Nash equilibrium exists for any congestion game (Rosenthal) 1973). Now we restrict our attention to pure Nash equilibrium and show that we can remove the /m factor in Theorem 3 We use I| to denote the set of all pure strategies. We modify Assumption and Algorithm for pure strategies.
Assumption 6. There exists a constant facility
Oppure > and a pure NE πt" such that
d -. (n)
pure fucility
mAX El1
.
d2(
15

---

Published as a conference paper at ICLR 2023
where the convention that 0 = O.
Algorithm 2 Surrogate Minimization for Congestion Games (Pure Strategy)
Require:
Offline dataset 'D
Compute F(a), b(a) for all according the dataset D.
2: Compute the optimistic value Vi and pessimistic value V,"" for all policy x and player by 3
3: Compute V V!.-= (EAA(E
V
4: return arg min fe maxie(m)
Theorem 8. With probability
8, if Assumption 6 is satisfied, it holds that
Gap( ouupur
S 2v 3aaatty F/ //vn.
Proof. We have
(a (.((a)
Σ Banltiaid
NS (a)
feF
n' (x')+1
4x2
SC
Σ
Σ
d (n'),
Taciiiy
V nay (n')
JEF n'=nn'
(x (x*)+1 H1
d (n')
-20pu facility
n
JEF n'=n (x+))
(+*)+1
20 pure facility
di (Tl)
FEF
12' (m*)-1
<2v <2V3Cppre facility (F/ L///n
The first inequality is by Definition Oouure Combine this with Theorem andd Lemma
B and Lemma The second inequality is by the definition of we get the conclusion.
ffcility
B.2 OMITTED CALCULATIONS IN SECTION 3
Proposition Suppose w is a deterministic strategy. For a fixed domain of p. the value of ((T) is the smallest when p is uniform over all actions achievable from unilaterally deviating from n.
Proof. Assume that covers an action a which is not achievable from unilaterally deviating from pi, then construct new ff where (a) and the other entries scales up by factor 1/(1-p(a)). / achieves larger ((T)) than p. Hence only cover the actions achievable from unilaterally deviating from π.
Assume that the distribution is not uniform. Since the best response to pure strategy can always taken be pure strategy, the numerator of [ can always achieve matter what is. Let a" arg min p(a), then there exists à such that p(a) > p(a"). Construct p' such that p'(a") p p((ā) (p(a") p(ā)) then C(T) would not increase. By contradiction we get the conclusion.
Proposition 2. The minimum value of Cjucitty is larger than 3.
Proof. Consider the case when p is a policy that induces uniform coverage on all facility config- urations achievable from n². Since most three configurations are covered for each facility, the minimum value of (n) is 1/3. Thus the minimum value of C(rr") is larger than 3
n
16

---

Published as a conference paper at ICLR 2023
C
OMITTED PROOF IN SECTION
Lemma 3. With probability 1- å we have
(n((a) - Pi(a)) - b,(a)
for all i E [m]. E A.
Proof. As degenerate version of theorem 20.5 of Lattimore & Szepesvári (2020) we have with probability 1 - 8 it holds that
0 8 v
|01|2 + v /lggdet(V) 2log(118), s
Hence with probability
1 5
(ri(a) - -i((a) = (A.(a), 0 8)
- [| | ellv
< [|A((a))ll-> (10112 v /log del (V) log (1/0)
for all E [m] and a E A. By Lemma of Cui et al. (2022) we have
det(V) - mnF
since by 5 [|A((a)]3 < F. Besides, |101|2 S 2vd. The proof is complete by combining all these and taking maxie(m).
Theorem 5. If Asssupptin 4 is satisfied, with probability 1 - 5, it holds that
mFB
Gap( ouspur S 4
Cagenit
where /B is defined in (6) and x ouppr is the output of Algorithm
Proof. We have for all i [m]
) (a)
=Bo-(Ra )
<Ba(tant ) V AJ (a) (I (ar ((()))))) -1
A((a)
_Bar(Ru tr (T (4tar//Baaunnnrrr144444444441111 ((())(T
(4:(a')) A((a)AT(a)
Baa tr (T Cagent (F (M()))))))))))))()((((())))))))) ((()))))))"""(())TT(((()""
((a))T(a))
Sy tr (1 + Cagemtilla (TT. ( Ba (A(())) (a)
tr
(1 (ag (((T)) "
/agge
d
mFF
Cagem
Cagem!
Combine this with Theorem D we get the conclusion.
Theorem 4. Define class X of congestion game M and exploration strategy p that consists of all M and p pairs such that Assumption 2s satisfied. For agent-level feedback, for any algorithm ALG there exists (M, p) E such that the output of ALG is at most 1 1/8-approximate NE no malter how much data is collected.
17

---

Published as a conference paper at ICLR 2023
Proof. Consider congestion game with two facilities f1, f2 and two players. Action space for both
players are unlimited, i.c. A1 = A2 = [[f]. {f2], {f1 f21}. We construct the following two congestion games with deterministic rewards. The NE for game 3 is aj = f2), 02 = {fi} or d2 = (fi, f2),a) a1 = {oi) The NE for game 4 is 0 = {f1),02 02 = {f2) or d2 = (fi),a di = {/2)-
The facility coverage conditions for these NEs are marked by bold symbols in the tables. The
R (2) = 1/2
Rfa =-1 (1) =1
(2) = 114 Rfa -144
(1(1)= =1
R1(11= =1 (1) =
Congestion Game
Congestion Game 4
exploration policy is set to be
1/3 01 = = (11,
p(a1, a2) =
1/3
0 = {fi..02 = {f2) or = (22), = {fi}
(II)
otherwise
21
(fz. 2)
(f. 1)
(f2. 1)
Figure 3: Facility coverage condition for p. Each pair (f.n) represents the configuration that players select facility f. Fach box contains the facility coverage condition for one player. There are two classes of covered actions described in formula [1]. The color of each box represents the class of actions it belongs to.
It can be casily verified that both f1 and fa are covered 1 and 2. However, all information may extract from the dataset is R (1) = 1, (1) = and (2) + R (2) = 1/2 It is impossible for the algorithm to distinguish these two games. Suppose the output strategy of AL.G selects action such that two players select fi with probability Then π is at least a (1 2pp/4-approximmae NE for the first game and at least p/ /44aaprrxximat NE for the second game. In conclusion, there exists (M, p) E X' such that the output of the algorithm ALG is at most 1 aprroxmme NE strategy no matter how much data is collected.
C.I OMITTED CALCULATIONS IN SECTION
Lemma 4. If n 2 8lo + 1)/8) + 1), with probability 1 - 6, Naa)) 2 p(a)n/2 = n/2(mF + 1) for all a with p(a) > O.
Proof. Naa follows binomial distribution with parameters n and p(a). By Chernoff bound, for all E E Rt
s²mp(aa
(N S 5 -1 ())p))((a)} S exp
Hence if p 2 -8 8/n, we have for all covered in the example, have
Pr (r(N(a) 2 (1 =)mp(a)} 2 1 - exx((((u//)) 2 1 - 5.
By construction p(a) = 1/(mF 1) for covered action a. By the union bound we get the conclu- sion.
Proposition 3. 1f 2 F, the maximum value of Cagen is no smaller than 1/2F.
Proof. Let the NE be pure strategy taking joint action a". For some specific i, Let A theorem there is joint policy
(A,(a, a"))a, E A.} and span(AA)) = d, by #' such that
FANAY (Aa(a) A d.
max AEA;
18

---

Published as a conference paper at ICLR 2023
From now scale each entry of カ' by 1/m. It is no longer valid probability measure but the definition of expectation retains. Hence for each E A
A [I/m m + nEaaa (A,(a)47 A d
mn A [1/m + nBa (A((a)AA A mn A|
By Cauchy inequality for each A E Ai
d
Let C = m/d 1/n,, then for each A E A AT [I/m + ni (()))) A (nC + 1)| AT +CAAATA
Let से be the sum of # over all player i, then for each A E A and
A |/ + nlEaa ((a)) A 2 A (1 +CAAA)A
Hence for each A E A₁ and i
I + nl a (A:(a)A:(a)) 2 + +
Furthermore, for each A E A₁ and
I+ n. (A((a)A(()) = + nCE nC (miNT (A(a))((a)]]
Now we are ready to lower bound Cagent. By d S mF
1
Cagem C 2
2d
2F
Proposition 4. If 2 8log((mF + 11/0)(mFF + 1) and Cagons 1/2mF', then with probability 1 - 6, Assumption 4 holds for the example described in Remark
Proof. It suffices show that inequality 7 hoolds for all pure strategy and because the right hand side is linear in any entry of π; From now on, let us focus on some specific i and pure strategy (Te, = choosing deterministically.
Without loss of generality, suppose among all elements in ā, facility that deviates from NE are fi, f2. Ss- For convenience, let Ag Aaa") where a" is the NE. For Jj. to estimate its contribution to the reward change, we need an action besides a", which we denote as a That is, a deviates from a" only on fy and let Aj = Aa(as) Without loss of generality, suppose the contribution corresponds (A, Ao, 0). Then we can write
A. = Ao + Σ (A₃ An) = Σ
A₁ + -1 A)
JE[N]
]E
By Lemma it suffices to show
I 2(mF +
Σ A1A] + 2(mF + +1
n
AdA I I + C (1)
SE[2]
In other words, for any x. E IR
we have
n1
Σ x TTAAAA AJAAAAJ
2mmF+1) x An 2 Cagen A((ā)) Tx.
n
2(m
JE[s]
For convenience, let I = x
A,, this inequality can be rewritten as
2
n
x +
2(mF + +1) o Cugen ?1
n
Σ jE(s]
x + +1 8)00
2(m +1)
JE(2]
By Jensen's 's inequality it suffices to show
Σ 2ラ
2mm + 1) J/6 2 Cs +1)
n
Σ
2 +1 (1- s)
2(mF
JE(()
[E((+)
Hence suffices to show
Cagent 1) - 1)2
2(m + 1)
19

---

Published as a conference paper at ICLR 2023
D OMITTED PROOF IN SECTION 5
Lemma 5. With probability 1- - å we have
Ini(a) ((a)) - b;(a)
for all i [m]. A.
Proof. Similar to Lemma 3 we have
Ire(a) Fr((a) [|A((a)ll-i (100)22 + (V) llg((1)))
The bound of (V) is now as follows. The basic idea is the same as that of lemma 4 by Cui et al. 2022)
det(V) - tr (r(V)) d (Ir(I)
-(m))) (Ir(T)+ EeD |l((a)) d I =( d (d+ mmmmm=F)
(1 + mP
d
Besides, |10||2 S 2vd. Combine all these we get the conclusion.
Theorem 7. If Assumpttin is satisfied, with probability 5, it holds that
mFB
Gap( oupput 1
Ca
where B is defined in equation 9 and ouiput is the output of Algorithml 7
Proof. The proof is identical to that of Theorem 5 exceptt that Cgame is used instead of C game-
Theorem 6. Define class X of congestion game M and exploration strategy that consists of all M and p pairs such that Assumption is satisfied. For game-level feedback, for any algorithm ALG there exists (M, p) X such that the output of ALG is at least 1 /AAaaproximatee NE matter how much data is collected.
Proof. Similar to the proof of Theorem consider congestion game with two facilities f1, f2 and two players. Action space for both players are unlimited. i.c. A = A = fffi). ff1 fe] We construct the following two congestion games with deterministic rewards. The NE for game
a = {fi},02 42 = {/1}- The NE for game is a1 = (h1, 02 = {/2) or 02 = [fi, a1 = (2)-
The exploration policy is set to be
Rh (2) 1/2
R = -1 R (1) -1
R (2) -1/2 R2 =-1
(1)1)=
R (1) =1 Rfa =
Congestion Game
Congestion Game 6
1/5
a = 02 = [
1/5
a1 = [11, a2 = (f2) or (/2)
a2) = 1/5
a1 = (i. f2. = (fi or 02 - (f}
0
otherwise
The reward information we can receive from the dataset the agent-level feedback setting includes: (2),)), (1), (1) + Rfa(1) and Rf (2). Hence we can compute the NE directly. In the geve- feedback setting, we only know (2) R (1)+ (1=(1) and f (2) + (1). Hence ALG cannot distinguish these two games. Suppose the output of ALG selects ac- tion that 2 players select fi with probability p. then it is at least (1 p1tppp/-pproxiimattt NE for game 5 and at least p 2aapproxima NE for game 6. In conclusion. ALG is at least 1/4-approximate NE strategy matter how much data is collected.
(fi 2)
(f2 2)
(f
(f2 1)
Figure 4: Facility coverage condition for p. Similar to Figure
20

---

Published as a conference paper at ICLR 2023
D.1 OMITTED CALCULATIONS IN SECTION 5
Lemma 6. nf 2 (3F + ()F + 1), with probability ó, N(a) 2 p(a)n/2 -
n/2(3F + 1)for all with p(a) 0.
The proof is identical to Lemma except that we have at most 3F + actions to cover instead of at most mF + actions.
Proposition If 2 F, the maximum value of Coverutl is smaller than 1/2F.
Proof. The proof is very similar to that of Proposition except that here we have A(a) instead of A:(a)
Proposition 6. If 2 (3o 1) + 1) and Cgame 1/2AF", then with probability 6, Assumption holds for the exampled described in Remark
Proof. The procedure is similar to that in the proof of Proposition Let us focus some specific pure strategy и choosing ä deterministically and player To calculate the reward from one facility, we need two actions. Suppose à; covers f1, So with configuration R4, "'2,". fag. Let the action vector corresponding to facility fg be Aj and A,,2. Without loss of generality, suppose the reward from the individual facility is (A,,1 Aj /mj. Then we can write
A A3
A.(a) Σ
nj
jE
suffices to show
72
(A + A222A3)) = C Cgame ((())
2F +
jEls
Note that because {Ai,1, A may have repeated elements and repeats at most F times, so we further discount the number of samples the left hand side by F. Following similar procedure in the proof of Proposition 6 and n, 2 1, s S F we get it suffices to show
2 O 2 F
2F(FF + +1)
E EXPERIMENT
We implement algorithm for the facility-level feedback setting and test its performance on a di- dactic example to verify theory. In this section, aim answer three questions: (i) Does algorithm recover the NE from datasets that satisfy assumption 3 (ii) How fast does our algorithm converge? (ii) How does the convergence rate vary with the number of players m??
F.
SETTING
The Bracss paradox (Braess al. 2005) is famous example of congestion game. The game presented here is a modified version but retains the core idea the paradox. There are m cars wanting travel simultaneously from S D. There are five roads (facilities) the road map, indexed from to as illustrated in figure It takes some time to travel from the starting point the destination point and everyone wants accomplish it quickly possible. The reward (negative latency) for each facility is as follows.
n² (a)
n na(a)
m +1 + 7J. ~ -1 + m. 12, 3 -1 na.
P4
+ 174
where 7a. 71, 122 73. 77 i..d. random variables with Gaussian distribution of mean 0 and vari- ance 1. Formally, the facility set and the action set of this game are F = {0, 2, 4}. = {{0, 1). (0, 2, 4), mm The NE for this game is (0, 2, 4) m An interesting fact about the game
21

---

Published as a conference paper at ICLR 2023
s
2
D
4
Figure 5: the Braess Paradox
that when m >> 2 if remove facility the road that does provide zero latency on average, the NE of this game gives everybody less latency. This means constructing more roads may aggravate traffic jams if we assume all drivers are selfish. In this paper, we employ the original game test our algorithm.
We use two different exploration policies to collect datasets. The first policy random exploration, where each player uniformly randomly selects his/her action from A. Formally for any player
1/3
{0, 1} 0;
random
(a:)
1/3
{0, 2, 4]
1/3
{3,4]
This policy covers all possible facility configurations and Ciaeiity = nd The second policy as follows.
1/3
ag {0, 1]
To
Facility
(oo)
1/3
{0,
1/3 ag {3,4]
T (a:) 1[a = (0, for i + 0
facility
For m > 1, this policy does not satisfy assumption Tas it only covers the actions NE unilaterally deviated by player However, it covers all facility configurations achievable from unilaterally deviated actions, hence satisfying assumption Moreover, since the NE covered is pure strategy, it satisfies assumption 6 and Cacility Cisiiity 3.
E.2 RESULT
For m 1, 2, 3, 4, 5, and two exploration policies, we test the algorithm for different sample sizes and evaluate the performance gap of the output policy. Results are visualized in Figure 6 and For each n, we run the algorithm on 16 datasets sampled from different random seeds. Mean performance gaps are shown with solid lines in the figures. We set å = 10-2
When the dataset is collected by raddom the algorithm can always find the optimal policy as long as the dataset is large enough. Fixing m, increases, the gap drops quickly when is small and gets more slowly when n becomes large. This complies with the 1/ l/vīi term in the bound from theorem As increases, convergence becomes slower, which also complies with theorem 3
When the dataset is collected by x facility the algorithm can always find the optimal policy as well. Furthermore, the size of dataset needed is far smaller than that for 7 random Except for the case the convergence rate barely varies with m, which complies with theorem g
22

---

Published as a conference paper at ICLR 2023
2
112
771
m
Figure 6: Result for facility The horizontal axis is sample size and the vertical axis the perfor- mance gap. Solid lines are means of gap over 16 seeds. Upper bounds and lower bounds of the light blue regions represent the standard deviation.
23

---

Published as a conference paper at ICLR 2023
Figure 7: Result for of random For m > 2, we provide two figures. The global view is on the left which shows the algorithm converges to a NE policy. The local view is on the right show the curve for small n in detail.
19200
4402
1903
1940
2
4
62
6
m
m
0.5
02
730 1600 3190 3500 3700 3000
2500
62
3
m 5
777
17
A0E53 DOCER 200200
03
10030 POOCE
0.
24


Reviews:
[{"review_id": "m4ekJOxC3m", "reviewer": "Reviewer_Kv1e", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper studies offline learning of the Nash equilibrium of the congestion game. In a congestion game, agents choose which facility to use. The reward the agent obtains from using the facility depends only on the number of total agents using that facility. In this paper, the authors consider three types of feedback: agent, facility, and game-level rewards. The major technical tool used in the paper is a meta-result (Theorem 1 in the paper) from Cui & Du (2022b), which reduces the problem to the one of designing a bonus function. The author proposes several coverage conditions on the exploration policy so that the meta algorithm from Cui & Du (2022b) learns the Nash equilibrium of the congestion game. Some coverage conditions are complemented with impossibility results to justify the imposing of such conditions.", "summary_of_the_review": "I suggest an accept. However, I'm not expert in congestion game so I chose a confidence score of 2.", "strength_and_weaknesses": "Strength: \n\nThe paper presents a rich collection of results for the problem of offline Nash equilibrium learning in congestion games. The paper is well-written and easy to follow.\n\nWeakness:\n\n\nMinor issues:\n\nIn page 4 when you write $R^f(\\cdot | n ) \\in [-1,1]$ is a bit confusing since $R^f$ is a distribution. It might be better to write the support of the distribution $R^f$ is [-1,1].\n\nAssumptions 3 and 4 are justified only for specific examples. Can we provide conditions on the exploration policy so that they hold with high probability?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "P9KrfXnTWU", "reviewer": "Reviewer_3Ebi", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "In their work, the authors focus on congestion games and examine information theoretic conditions for identifying NE. Specifically, they identify the minimal assumptions required to efficiently determine if a policy is a Nash Equilibrium of a congestion game from a given dataset. The authors examine 3 different models, one with access to the costs of individual facilities, one with access to agent level costs, and one with access to the sum of agents' costs. The required assumptions depend on the information encompassed in the dataset, and stronger assumptions are naturally required when less information is provided. \n", "summary_of_the_review": "A theoretical and mathematically sound paper, which lacks clarification in some parts but requires further work regarding experimental results and given examples. I would be happier if the impossibility results did not require the assumption of agents with having the choice of an empty strategy. ", "strength_and_weaknesses": "\nStrengths:\n\n1) The authors take recent work's particularly by Ciu and Du on finding a minimal dataset coverage assumption to learn an NE in a general-sum matrix to the realm of congestion games.\n2) The results are novel to the best of my knowledge.\n3) Given the time constraints, I verified a large part of the mathematical work, and their work is mathematically sound to the best of my knowledge.\n\n\nWeaknesses:\n\n1) The impossibility results (Theorem 4 and 6) require the assumption of agents whose allowable sets of actions includes the empty set. This is a highly non-standard assumption in congestion games/game theory. Is this assumption necessary for these proofs or is there a workaround? \n2) Various parts of the paper need more clarification or/and notational precision. For example, what is $n$ in Assumption 2? Do we assume that the condition holds for some $n$ or all possible $n$? Of course, the following paragraph clarifies the issue, but the assumption is not self-explanatory.\n3) The lack of experimental results is disappointing. Although this work is theoretical, it should be relatively easy to add experimental results showing how close the theoretical bound is to the actual gap. \n4) Even in the toy examples provided, adding the actual scale of the required data would be very beneficial, even if just for clarity. For example, in Figure 1, what is the actual number of data required to determine this equilibrium?\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Nklh-MAjLGt", "reviewer": "Reviewer_g7gc", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper studies the problem of computing an approximate Nash equilibrium in congestion games from offline game data.\nThe authors consider three different types of data, depending on whether rewards are observed at the facility level, player level, or game level, and analyze their corresponding hardness in terms of required number of samples and data coverage assumptions. Moreover, to compute such approximate NE, they adapt the surrogate minimization approach of Cui and Du (2022) and decline it for the three different settings.", "summary_of_the_review": "Overall, I think the paper is quite original and could be interesting to the algorithmic game theory community.\nMoreover, I have also appreciated the counter examples designed by the authors to show separability of the different feedback models and provide intuition. Thus, I believe it deserves acceptance. \nHowever, I would like the authors to consider the weaknesses outlined above and I am happy to increase my score upon their response.", "strength_and_weaknesses": "I think the authors consider a relevant problem, e.g. arising in modern routing networks, and place their work nicely into the existing literature. Moreover, the paper is nicely written and contributions are spelled out clearly.\nThe results are also sound, and the authors give a good intuition about the different settings and resulting guarantees. \n\nWhat I did not like about the paper is:\n- Depending on the feedback, the authors come up with  (often necessary) data coverage assumptions, under which the resulting sample complexities are derived. However, it is not obvious to me how easy is for such assumptions to be true in practice. More specifically, it would be nice to provide (even at an intuitive level) data collection strategies that will satisfy such assumptions. Unless I am missing some details, I think this would be a very nice addition to the paper.\n- No experiments are performed to illustrate the developed technique and how such bounds translate into practice.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "AWiVU_XQKh6", "reviewer": "Reviewer_oumy", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The paper studies the conditions for recovering approximate NE of offline congestion games from samples under different types of feedback. Leveraging the structures of congestion games, new data converage assumptions are proposed to prove NE learnability, overcoming the exponentially growth of the sample complexity if directly applying the condition for general general-sum games.", "summary_of_the_review": "The paper studies an important problem, studing the data coverage condition required for leanring NE from offline samples for congestion games with different types of feedback. Although maybe restricted to the special class of games, the theoretical analysis is concrete. Overall, the paper is of high quality and I would recommend accecption.", "strength_and_weaknesses": "Strength:\n1. Learning NE from offline samples is a rising direction and the curse of large action set would be a general issue if applying the idea to specific games. The paper provides clear discussion on congestion games.\n2. The theoretical contributions are concrete.\n\nWeaknesses:\n1. The analysis on different types of feedback relies on much knowledge about the congestion game. Basically, these types are strongly related to congestion games. Thus, the techniques may not be able to inspire works on other games.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster