Multi-agent Deep FBSDE Representation For Large Scale  Stochastic Differential Games
Authors: Tianrong Chen
Ziyi Wang
Ioannis Exarchos
Evangelos Theodorou
Venue:  (2021)
Keywords: Multi-agent Deep FBSDE Representation For Large Scale  Stochastic Differential Games

Abstract:    In this paper we present a deep learning framework for solving large-scale multi-agent non-cooperative stochastic games using fictitious play. The Hamilton-Jacobi-Bellman (HJB)  PDE associated with each agent is reformulated into a set of Forward-Backward Stochastic Differential Equations (FBSDEs) and solved via forward sampling on a suitably defined neural network architecture. Decision-making in multi-agent systems suffers from the curse of dimensionality and strategy degeneration as the number of agents and time horizon increase. We propose a novel Deep FBSDE controller framework which is shown to outperform the current state-of-the-art deep fictitious play algorithm on a high dimensional inter-bank lending/borrowing problem. More importantly, our approach mitigates the curse of many agents and reduces computational and memory complexity, allowing us to scale up to 1,000 agents in simulation, a scale which, to the best of our knowledge, represents a new state of the art.  Finally, we showcase the framework's applicability in robotics on a belief-space autonomous racing problem.

Under review as a conference paper at ICLR 2021
MULTI-AGENT DEEP FBSDE REPRESENTATION FOR LARGE SCALE STOCHASTIC DIFFERENTIAL GAMES
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper we present deep learning framework for solving large-scale multi- agent non-cooperative stochastic games using fictitious play. The Hamilton- Jacobi-Bellna (HJB) PDE associated with each agent reformulated into set of Worward-Backwerr Stochastic Differential Equations (FBSDEs) and solved via forward sampling on a suitably defined neural network architecture. Decision making in multi-agent systems suffers from curse of dimensionality and strategy degeneration as the number agents and time horizon increase. We propose novel Deep FBSDE controller framework which is shown to outperform the current state-of-the-ane deep fictitious play algorithm on a high dimensional inter- bank lending/borrowing problem. More importantly, our approach mitigates the curse of many agents and reduces computational and memory complexity, allow- ing to scale up to 1,000 agents in simulation, a scale which, to the best of our knowledge, represents a new state of the art. Finally, we showcase the frame- work's 's applicability in robotics on belief-space autonomous racing problem.
INTRODUCTION
Stochastic differential games represent framework for investigating scenarios where multiple play- ers make decisions while operating in a dynamic and stochastic environment. The theory of differ- ential games dates back the seminal work Isaass (9655) studying two-player zero-sum dynamic games, with a first stochastic extension appearing in Kushner & Chamberlain (1969). A key step in the study of games is obtaining the Nash equilibrium among players (Osborne Rubinstein 1994). A Nash equilibrium represents the solution of non- non-cooperative game where two or more players are involved. Each player cannot gain benefit by modifying his/her own strategy given opponents equilibrium strategy. In the context of adversarial multi-objective games, the Nash equilibrium can be represented as system of coupled camilton-Jacohee Beelb-- (HJB) equations when the system satisfies the Markovian property. Analytic solutions exist only for few special cases. Therefore, ob- taining the Nash equilibrium solution usually done numerically, and this can become challenging as the number of states/agents increases. Despite extensive theoretical work, the algorithmic part has received less attention and mainly addresses special cases of differential games (c.g., Duncan & Duncan (2015)), or suffers from the curse of dimensionality (Kushner) 2002). Neverthe- less, stochastic differential games have a variety of applications including in robotics and autonomy, economics and management. Relevant examples include Mataramvura & Oksendal (2008), which formulate portfolio management as a stochastic differential game in order to obtain market port- folio that minimizes the convex risk measure of terminal wealth index value, as well Prasad & Sethi (2044). who investigate optimal advertising spending in duopolistic settings via stochastic differential games.
Reinforcement Learning (RL) aims in obtaining a policy which can generate optimal sequential de- cisions while interacting with the environment. Commonly, the policy is trained by collecting histo- ries of states, actions, and rewards, and updating the policy accordingly. Multi-agent Reinforcement Learning (MARL) is an extension of RL where several agents compete in a common environment, which is more complex task due to the interaction between several agents and the environment, as well as between the agents. One approach is to assume agents to be part of environment (Tan) 1993), but this may lead to unstable learning during policy updates (Matignon al. 2012). On the other hand, a centralized approach considers MARL through an augmented state and action system, reducing its training to that of single agent RL problem. Because of the combinatorial complexity,

---

Under review as a conference paper at ICLR 2021
the centralized learning method cannot scale to more than 10 agents Yang et al. 2019 Another method is centralized training and decentralized execute (CTDE), however the challenge therein lies on how decompose value function in the execute phase for value-based MARL. [Sunchag et al. (2018) and /Zhou et al. (2019) decompose the joint value function into a summation of individual value functions. Rashid et al. (2018) keep the monotonic trends between centralized and decentral- ized value functions by augmenting the summation non non-linearly and designing a mixing network (QMIX). Further modifications on QMIX include [Snn et al. (2019) Mahajan al. (2019).
The mathematical formulation of differential game leads to a nonlinear PDE. This motivates algo- rithmic development for differential games that combine elements of PDE theory with deep learn- ing. Recent encouraging results (Han et al.] 20188 Raissi 2018) in solving nonlinear PDEs within the deep learning community illustrate scalability and numerical efficiency of neural networks. The transition from PDE formulation to trainable neural network is done via the concept of sys- tem of Forward-Backe
Stochastic Differential Equations (FBSDEs). Specifically, certain PDE solutions are linked to solutions of FBSDEs, and the latter can be solved using a suitably defined neural network architecture, This is known the literature as the deep FBSDE approach. Han et al. (2018) Pereira et al. (2019); Wang et al. (019b) utilize various deep neural network architectures to solve such stochastic systems. However, these algorithms address single agent dynamical sys- tems. Two-player zero-sum games using FBSDEs
initially developed in [Exarchos et al. (2019) and transferred to a deep learning setting in Wang et al.) (2019a). Recently Hu (2019) brought deep learning into fictitious play solve multi-agent mon-zero-sile game, [Han & Hu (2019) introduced the deep FBSDEs to a multi-agent scenario and the concept of fictitious play, furthermore, Han et al. (020 gives the convergence proof.
In this work we propose an alternative deep FBSDE approach to multi-agent non-cooperative dif- ferential games, aiming on reducing complexity and increasing the number of agents the framework can handle. The main contribution of our work is threefold:
1. We introduce an efficient Deep FBSDE framework for solving stochastic multi-agent games via fictitious play that outperforms the current state of the art in Relative Square Error (RSE) and runtime/memoor efficiency on an inter-bank lending/borrowing example.
2. We demonstrate that our approach scales a much larger number of agents (up to 1,000 agents, compared to 50 in existing work). To the best of our knowledge, this represents new state of the art.
3. We showcase the applicability of our framework robotics belief-space autonomous racing problem which has larger individual control and state space. The experiments demonstrates that the decoupled BSDE provides the possibility of applications for com- petitive scenario.
The rest of the paper is organized as follows: in Section 2 we present the mathematical preliminaries. In Section 3 we introduce the Deep Fictitious Play Belief FBSDE, with simulation results following in Section We conclude the paper and discuss some future directions in Section
2 MULTI-AGENT FICTITIOUS PLAY FBSDE
Fictitious play is learning rule first introduced in Brown 1951) where each player presumes other players' strategies to be fixed. An N-player game can then be decoupled into N individual decision- making problems which can be solved iteratively over M stages. When each agen(" converges stationary strategy stage m. this strategy will become the stationary strategy for other players at stage m + 1. We consider a N N-player non-cooperative stochastic differential game with dynamics
converens to a
dx (t) (f tt) + G(X ()))))) + E(X (t), X(() =X,
(1)
where X (001, ... (N) is vector containing the state process of all agents generated by their controls U = (1), u uN) with x; E R and u, E R". Here, f R x [0, + R represents the drift dynamics, G R" x [0, + Xm, represents the actuator dynamics, and Σ: [o, T] x " + R x represents the diffusion term. We assume that each agent is only driven by its controls G is block diagonal matrix with G; corresponding the actuation of agent
gent and player are used interchangeably in this paper
2

---

Under review as a conference paper at ICLR 2021
Each agent is also driven by its own dimeennniion independent Brownian motion W,, and denote W = (W1, W....., Wx).
Let U, be the set of admissible strategies for agent E I : 21. N and U @ - Ug the Kronecker product space of U; Given the other agents' strategies, the stochastic optimal control problem for agent i under the fictitious play assumption is defined minimizing the expectation of the cumulative cost functional Ji
(X Mim u 1.m- = E ((X(T)) J. C'(X(T), u.m ( i.m ----imm11100 d
(2)
where m - R++ is the terminal cost, and C [0, R x R+ is the run- ning cost for the i-th player. In this paper we assume that the running cost is of the form C(X, (i,m,t) (xx) + fuf, Ruim + +'"uu We use the double subscript uim to de- note the control of agent i at stage m and the negative subscript -i as the strategies excluding player i, u-, (u1...., 1, U1+1, .., ur). We can define value function of each player as
(t, (t)) = inf EU;
[X Ui u u.-.-mmm11 i.m- (T (T)) = x (T))
(3)
Assume that the value function in eq. (3) is once differentiable w.r.t. and twice differentiable w.r.. r. Then, standard stochastic optimal control theory leads to the HJB PDE
V + h VeT (S -U) + ((=()==))=== 0,
(4)
where h = C GU=.0- The double subscript of Uao denotes the augmentation of the optimal control u = -R
+ xT and zero control u-i,m-1 0, and Uo denotes the augmentation of um = 0 and u- Here we drop the functional dependencies in the HJB equation for simplicity. The detailed proof is in Appendix A can be related to a set of FBSDES
The value function in the HJB PDE
dx = (f GU. EdW, X(0) ZD
(5)
dV = - V.
V GU. VJ EdW, V(T) 9(T)=
where the backward process corresponds to the value function. The detailed derivation can be found in Appendix [ Note that the FBSDEs here differ from that of Han & Hu (2019) in the optimal control of agent i, GU., in the forward process and compensation, V..GU. (GO..- .0- in the backward process. This is known as the importance sampling for FBSDEs and allows for the FBSDEs to be guided to explore the state space more efficiently.
DEEP FICTITIOUS PLAY FBSDE CONTROLLER
In this section, we introduce a novel and scalable Deep Fictitious Play FBSDE (SDFP) Controller to solve the multi-agent stochastic optimal control problem. The framework can be extended to the partially observable scenario by combining with an Extended Kalman Filter, whose belief propaga- tion can be described by an SDE for the mean and variance (see derivation in Appendix C By the natural of decoupled BSDE, the framework can also been extended to cooperative and competitive scenario. In this paper, demonstrate the example of competitive scenario.
3.1 NETWORK ARCHITECTURE AND ALGORITHM
Inspired by the success of LSTM-based deep FBSDE controllers (Wang et al., 2219bb] Percira et al.) 2019, we propose an approach based on an L.TTM architecture similar to Pereira et al. (2019). The benefits of introducing LSTM are two-fold: 1) LSTM can capture the features of sequential data. A performance comparison between L.ST and fully connected (FC) layers in the deep FBSDE framework has been elaborated in Wang al. (009b): 2) LSTM significantly reduces the memory complexity of our model since the memory complexity of LSTM with respect to time is O(1) in the inference phase compared with ((T) in previous work (Han al. 2018), where T is the number of time steps. The overall architecture of SDFP shown in Fig. I and features the same time discretization scheme Pereira al. (201)). Each player's policy is characterized by its copy
3

---

Under review as a conference paper at ICLR 2021
NN;
NWW
N/lky-
Ale=
Nifiy-s
Wiyy
Ny
X
X;
X+
Figure 1: SDFP framework for N Players. Each NN block has the architecture in Fig.
of the network defined in Fig. I1 At stage m, each player can access the stationary strategy of all other players from stage predicted by a FC layer parameterized by ø. At each timestep, the optimal policy for each player is computed using the value function gradient prediction VA from the recurrent network (consisting of FC and LSTM layers), parameterized by 0. The FSDE and BSDE are then forward-propagated using the Euler integration scheme. At terminal time T, the loss function for each player is constructed as the mean squared сттоr between the propagated terminal value V and the true terminal value V/* computed from the terminal state. The parameters and 0 of each player can be trained using any stochastic gradient descent type optimizer such as Adam. The detailed training procedure is shown in Algorithm
During training within stage, the initial value of each player is
3.2 MITIGATING CURSE OF DIMENSIONALITY AND SAMPLE COMPLEXITY
Scalability and sample efficiency are two crucial criteria of reinforcement learning- In SDFP, as the number of agents increases, the number of neural network copies would increase correspondingly. Meanwhile, the size of each neural network should be enlarged to gain enough capacity to cap- ture the representation of many agents, leading the infamous curse of dimensionality: this limits the scalability of prior works. However, one can mitigate the curse of dimensionality in this case by taking advantage of the symmetric game setup. We summarize merits of symmetric game as following:
1. Since all agents have the same dynamics and cost function, only one copy of the network is needed. The strategy of other agents can be inferred by applying the same network.
2. Thanks to the symmetric property, we can applied invariant layer to extract invariant fea- tures to accelerate training and improve the performance with respect to the accumulate cost and RSE loss.
It's important to note that querying other agents should not introduce ad- ditional gradient paths. This significantly reduces the memory complexity. When querying other agents' strategy, one either iterate through each agent or feed all agents' states to the network in a batch. The latter approach reduces the time complexity by adopting the parallel nature of modern GPU but requires (N memory rather than O(N) for the first approach.
Sharing network:
Invariant Layers: The memory complexity can be further reduced with an invariant layer embedding (Zaheer et al. 2017). The invari- ant layer utilizes sum function along with the features in the same set to render the network invariant to permutation of agents. We apply the invariant layer on X-; and concatenate the resulting features to the features extracted from X, However, vanilla invariant layer embed- ding will not reduce the memory complexity. Thanks the symmetric problem setup, one can apply a trick to reduce the invariant layer memory complexity form (N22) O(N). A
033
FEGDC
828
ranroura In 2818 serple
Figure 2: Sample efficiency between FBSDE framework w/ and w/o invariant layer.
detailed introduction to the invariant layer and our implementation can be found in Appendix and
The full algorithm outlined in Algorithm I
4

---

Under review as a conference paper at ICLR 2021
Algorithm Scalable Deep Fictitious Play FBSDE for symmetric simplification
Hyper-parameters.. Number of players, T': Number of timesteps, M: Number of stages in fictitious play, Nod Number of gradient descent steps per stage, Un: the initial strategies for players in set Batch size, c: training threshold, At: time discretization
2: Parameters: (au; Φ): Network weights for initial value prediction, 6: Weights and bias of fully connected layers and LSTM layers.
3: 0: Initialize trainable papermeters:0%, d0
4: while LOSS is above certain threshold e do to M do 6: for all i E I1 parallel do Collect opponent agent's policy which is same ith policy: fESTM. ()) 17, ()) for 7 < to Ng do do if Using Invariant Layer then
5: for
7:
8:
9:
for
10:
X, faneariant (X;,
12:
end if for + in parallel do
Compute network prediction for ith player: V = SFc; (fLSTM (X:; 6!-1))
15:
Compute ith optimal Control :u - R2 (GT Q.
16:
Infer -ith players' network prediction and stop the gradient for them: V2 Va_..
JFC. (UESTM, (Xc;0:))
Compute -ith optimal Control and stop the gradient for them: u
-RT,
Q_,
Sample noise AWi (N AI)
Propagate FSDE: x ++1 = fASDE( whi whi AWi,
19:
Propagate BSDE: Vi fBSDE( (X( uix AWS,t) end for end for Compute loss: L= 1/8 Σト= (V v2r)²²
21:
22:
23:
24:
Gradient Update: 0¹,0'
25:
end for
26:
end for
end for
28:
end while
0.5
1.0
0.2
tngeeary
-3.5
-0.4
Estimated Soludion
-2.8
Eimels
Figure 3: Comparison of SDFP and analytic solution for the inter- bank problem. Both the state (left) and control (right) trajectories are aligned with the analytic solution (represented by dots).
SIMULATION RESULTS
In this section, we demonstrate the capability of SFDP on two different systems in simulation. We first apply the framework to an inter-bank lending/borrowing problem, which is a classical multi- player non-cooperative game with an analytic solution. We compare against both the analytic solu- tion and prior work (Han& & Hu 2019). Different approaches introduced in Section 3.2 2 are compared empirically this system. We also apply the framework to variation of the problem for which no analytic solution exists. Finally, we showcase the general applicability of our framework in an autonomous racing problem in belief space. All experiment configurations be found in Ap-
5

---

Under review as a conference paper at ICLR 2021
25
baodin clansit teralivel
cese Ire Iifans tu Satcho
Fann Wankiiteleeaaaaab--e Farta
Our (LSTM4 Invartant--aacch
Time per Iterattion (s)
20
Memory (G8)
15
10
5
10a
102
10a 101
102 number agents
10a
number of agents
Figure 4: Time and memory complexity comparison between batch, iterate and invariant layer+batch implementations. Time complexity measured by per-iteration time.
Table 1: Comparison with previous work the 10-agent inter-bank problem.
Framework
# stages
Learning Rate
RSE
Total Time (hr) [
Han & Hu (2019)
80
le-3
0.0423
2.23
SFDP
80
1e-3
0.0105
1.55
pendix ! we plot the results of 3 repeated runs with different seeds with the line and shaded region showing the mean and standrd deviation respectively. The hyperparameters and dynamics coefficients used in the inter-bank experiments are the same as Han & Hu (2019) unless otherwise noted.
4.1 BATER-BANK LENDING/BORROWING PROBLEM
We first consider an inter- baek-bank lending and borrowing model (Carmona et al., 2013) where the dynamics of the log monnetryy reserves of N banks is described by the diftusion process
N Σ
axp = [a(x - x;) + wt] di + (odW? + -
- paw)) X N X
(6)
The state X; E IR denotes the log-monetary reserve of bank i time > 0. The control ug denotes the cash flow to/from central bank, where a(X - -X;) denotes the lending/borrowiin bank é from all other banks. The system is driven by N independent standard Brownian motion Wi, which denotes the idiosyncratic noise, and common noise WT- The cost function has the form,
rate of
C (X, uo; u.) = 2 u qu, x,)
6 (X xx,² 2
The derivation of the FBSDEs and analytic solution can be found in Appendix F We compare the result of implementation corresponding to Algorithm - on a 10-agent problem with analytic solu- tion and previous work from Han & Hul (2019) with the same hyperparameters. Fig. shows the performance of our method compared with analytic solution. The state and control trajectories out- putted by the deep FBSDE solution aligned closely with the analytic solution. Table [shllss numerical performance compared with prior work by Han & Hu (001). Our method outperforms by Relative Square Error (RSE) metries and computation wall time. The RSE is defined following:
shows the
RSE = DISRE (0, XO (0, (0))²
(
EISE (V: X² Vo (0)))
Where 5/ is the analytic solution of value function for ith agents at intial state (0)) The initial state X²(0) (0) new batch data sampled from same distribution as X X(0) in the training phase. The batch size B is 256 for all inter- bank simulations. ' is the approximated value function for ith agent by FBSDE controller, and 5 is the average of analytic solution for ith agent over the entire batch.
Time/Memory Complexity Analysis: We empirically verify the time and memory complexity of
different implementation approaches introduced in 3.2) which is shown in Fig. 4 Note that all
The experiment conducted Nvidia TITAN RTX

---

Under review as a conference paper at ICLR 2021
2.2
7.0
2.0
6.5
1.8
1.6
5.5
Foemmntant ayer (Ound)
FC dic dalnn Danelinnt
1.4
RC (lubiaan Baeeine:
FC+ noar layer (Dun)
LSTH mer Layer 10unt
LST Firvarint Layer (bur))
10
102
10a
10a
10a
10a
number of agents
number of agents
Figure 5: RSE and total loss comparison between our FBSDE framework and that of baseline Han
& Hu 2019)
experiments hereon correspond to the symmetric SDEP implementation in Algorithm T We also test sample efficiency and generalization capability of the invariant layer on 50-agent problem trained over 100 stages. The number of initial states is limited during the training and the evaluation criterion the terminal cost of the test set in which the initial states are different from the initial states during training. Fig. T showcases the improvement in sample efficiency and generalization performance of invariant layer. We suspect this is due to the network needing to learn with respect to a specific permutation of the input, whereas permutation invariance is built into the network architecture with invariant layer.
An important distinction of SDFP from the baseline in Han & Hu (2019) is the importance sampling scheme, which helps the LSTM architecture achieve a fast convergence rate during training. However, the baseline, which uses fully connected layer backbone, is not suitable for importance sampling, as it would lead to an extremely deep network with fully connected layers from gradient topology perspective. (Sandler al. (2018) mentioned that the information loss is inevitable for this kind of fully connected deep network with nonlinear activation. On the other hand, LSTM does not suffer from this problem because of the existence of long and short memory. We illustrate the benefits of importance sampling for LSTM backbone and gradient flow of fully connected layer backbone in Appendix[]
Importance sampling:
High dimension experiment: We also analyze the performance of our framework and that of Han Hu (2019) both with and without invariant layer on high dimensional problems. We first demon- strate the mitigation of the invariant layer on the curse of many agents. Fig. 5 demonstrates the ablation experiment of the two deep FBSDE frameworks (SDFP and Han & Hu (2019). In order to illustrate that invariant layer can mitigate the curse of dimensionality, we also integrate invariant layers on Han & Hu (201)) and shows the performance the same figure In this experiment, the weights of FBSDE frameworks with invariant layer are adjusted in order to dismiss the performance improvement resulting from increased weights from the invariant layers. The total cost and RSE computed by averaging the corresponding values over the last twenty stages of each run. It can be observed from the plot that without invariant layer, the framework suffers from curse of many agents in the prediction of initial value as the RSE increases with respect to the number of agents, On the other hand, RSE increases at a slower rate with invariant layer. In terms of total cost, which computed from the cost function defined in e our framework enjoys the benefits of importance sampling and invariant layer, and achieves better numerical results over the number of agents. We further analyse the influence of invariant layers in the training phase by demonstrating fig[7] Invari- ant layer helps mintage over-fitting phenomenon in the training and evaluation phase, meanwhile accelerating the training process, even though both of frameworks adopting same feature extracting backbone (LSTM) and importance sampling technique.
We also show that the invariant layer accelerates training empirically on 500-agent problem. Fig shows that the FBSDE frameworks converge much faster with invariant layer than without it. We suspect that the acceleration effect results from increased sample efficiency. Note that the compar- ison is done the invariant layer. A comparison of the two frameworks with invariant layer only on a 1000-agent problem can be found in Fig 16, which shows similar results to the 500-agent problem.
500-agent problem because the framework does not scale to 1000 agents without

---

Under review as a conference paper at ICLR 2021
thu Dansknnl
Hibittn Basding
TClimartant ager (0ura)
Total Loss
RSE
101
Number of Stages
Number of Stages
Figure 6: RSE and total loss trajectory comparison between our FBSDE framework and that of Han & Hu 2019) w/ and w/o invariant layer for 500 agents.
(Peraia Beseline)
Layer cOuret
eiroriant Layer (ound
10
Training
RSE
20
40
60
80
20
40
60
80
Number of Stages
Number of Stages
Figure 7: RSE and training loss trajectory comparison between our FBSDE framework and the extension of Pereira et al. (2019) w/ and w/o invariant layer for 500 agents.
Superlinear Simulation: We also consider a variant of dynamics in section 4.1
N X 2=1
dx; [a(x x;)² ui] dt + (pdW? + vI pddw), X,
(9)
N
Due to the nonlinearity in the drift term, analytic solution simple numerical representation of the Nash equilibrium does not exist (Han & Hu 2019). The drift rate is set to 1.0 to compensate for the vanishing drift term caused by super-linearity Heuristically, the the distribution of control and state should be more concentrated than that the linear dynamics. We compare the state and control of fixed agent terminal time against analytic solution and deep FBSDE solution of the linear dynamics with the same coefficients. Fig. 8 is generated by evaluating the trained deep FBSDE model with batch size of 50000. can be observed that the solution from super-linear dynamics is more concentrated as expected. The terminal control distribution plot verifies that the super-linear drift term pushes the state back the average faster than linear dynamics and thus requires less control effort. Since the numerical solution is not available in the superlinear case, we compare the total loss and training loss between baseline Han Hu (2019) and our algorithm in the appendix T2
Anablic
1.2
Anabtic
0.6
rssos Jsar Dynamis racor
1550 Usar Dynamiks T350 superiirr Dynamics
auperlesr Sysamies
1.0
Density
Density
0.8
0.6
0.3
0.2
0.4
0.1
0.2
0.0
-3
2
3
-2
U;
Figure 8: Terminal time step state and control distribution of agent for linear and superlin- ear dynamics.
8

---

Under review as a conference paper at ICLR 2021
4.2 BELIEF SPACE AUTONOMOUS RACING
In this section, we demonstrate the general applicability of our framework on an autonomous racing example in belief space. We consider 2-car autonomous racing competition problem with racecar dynamics
x = [v cos 0, U sin 0, Mace - Cdrag Usteer 0/ [.]
(10)
where x = [at, y, U, 8) represent the x. position, forward velocity and heading respectively. Here we assume z; M, U, Mace E IR, Usterr E [-1, 1]. The goal each player is to drive faster than the oppo- nent, stay on the track and avoid collision. An additional competition loss can be added to facilitate competition between players. During the competition, players have access to the global augmented states and opponent's history controller. Additionally, tem through the control channels and have continuous-time noisy observation model with full-state observation. The FBSDE derivation of belief space stochastic dynamics is included in Appendix G trained with
assume that stochasticity enters the sys-
The framework for the racing problem batch size of 64, and 100 time steps over a time horizon of 10 seconds. Since all the trials will run over lapse of the circle, here we only show the first 8 second result for neatness. Fig. demoonstra the capability of our frame- work. When there no competition loss, both of cars can stay in the track. Since there is no competition between two cars, they demonstrate similar behaviors. When we add competition loss on both cars, both of them try to cut the corner in order to occupy the leading position as shown in the second plot in Fig. 13 If competition loss present in only one of the two cars, then the one with competition loss will dominate the game shown in the botton subplots of Figure [3] Notably the simulation is rumning belief space where all states are estimated with observation noise and additive noise in the system. The results emphasizes the generalization ability of our framework on more complex systems with higher state and control dimensions. Fig. 9 shows single trajectory of each car's posterior distribution.
Carl
Car2
0.
0.0
Figure One belief racing trajec- tory. The solid line represents the mean and the circles represent the variance.
5 CONCLUSION
In this paper, we propose scalable deep learning framework for solving multi-agent stochastic differential game using fictitious play. The framework relies on the FBSDE formulation with impor- tance sampling for sufficient exploration. In the symmetric game setup, an invariant layer is incor- prated to render the framework agnostic to permutatoon of agents and further reduce the memory complexity. The scalability of this algorithm. along with detailed sensitivity analysis, is demon- strated in an bnter-bank borrowing/lendnng example. The framework achieves lower loss and scales much higher dimensions than the state of the art. The general applicability of the framework is showcased on a belief space autonomous racing problem in simulation.

---

Under review as a conference paper at ICLR 2021
REFERENCES
George W Brown, Iterative solution of games by fictitious play. Activity analysis of production and allocation, 13(1):374-370) 376, 1951.
Rene Carmona, Jean-Pierre Fouque, and Li-Hsien Sun. Mcan field games and systemic risk. Avail- able at SSRN 23078/4, 2013.
T. Duncan and B. Dasik-Ducaan. Some stochastic differential games with state dependent noise. 54th IEEE Conference on Decision and Control, Osaka, Japan, December 15-18, 2015.
loannis Exarchos, Evangelos Theodorou, and Panagiotis Tsiotras. Stochastic differential games: A sampling approach via FBSDEs. Dynamic Games and Applications. 92):486-505, 2019.
Jiequn Han and Ruimeng Hu. Deep fictitious play for finding markovian nash equilibrium multi- agent games. arXiv preprint arXiv: 199992228999 2019.
Jiequn Han, Arnulf Jentzen, and E Weinan, Solving high-dimensional partial differential equations using deep learning. Proceedings of the National Academy of Sciences, 115(34):8505-88100 2018.
Jiequn Han, Ruimeng Hu, and Jihao Long. Convergence of deep fictitious play for stochastic differ- ential games. arXiv preprint arXiv:2008.05519 2020.
Ruimeng Hu. Deep fictitious play for stochastic differential arXiv:1903.09376. 0997909..777. 2019.
games.
arXiv preprint
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint arXiv:1502.03167, 2015.
R. Isaacs. Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization. New York: Willey, 1965.
AH Jazwinski. Stochastic process and filtering theory, academic press. A subsidiary of Harcourt Brace Jovanovich Publishers, 1970.
H. Kushner. Numerical approximations for stochastic differential games. SIAM J. Control Optim., 41:457-486, 2002.
H. Kushner and S. Chamberlain. On stochastic differential games: Sufficient conditions that a given strategy be a saddle point, and numerical procedures for the solution of the game. Journal of Mathematical Analysis and Applications, 26:560-577 -75, 1969.
Anuj Mahajan, Tabish Rashid, Mikayel Samvelyan, and Shimon Whiteson. Maven: Multi-agent variational exploration. In Advances in Neural Information Processing Systems, pp. 7613-7624, 2019.
Sure Mataramvura and Bernt Øksendal. Risk minimizing portfolios and hjbi equations for stochastic differential games. Stochastics An International Journal of Probability and Stochastic Processes, 80(4):317-337, 2008.
Laetitia Matignon, Guillaume J Laurent, and Nadine Le Fort-Piat, Independent reinforcement learn- ers in cooperative markov games: survey regarding coordination problems. 2012.
Martin J Osborne and Ariel Rubinstein. A course in game theory cambridge. MA: MIT Press |Google Scholar), 1994.
Mareus A Pereira, Ziyi Wang. Ioannis Exarchos, and Evangelos A Theodorou. Learning deep stochastic optimal control policies using forward-backward sdes. In Robotics: science and sys- fems, 2019.
Ashutosh Prasad and Suresh P Sethi. Competitive advertising under uncertainty: A stochastic differ- ential game approach. Journal of Optimization Theory and Applications, 123(1):163-185, 2004.
10

---

Under review as a conference paper at ICLR 2021
Maziar Raissi. herward-bacwwerr stochastic neural networks: Deep learning of high- high-dimensional partial differential equations. arXiv preprint arXiv:1804.07010 2018.
Tabish Rashid, Mikayel Samvelyan, Christian Schroeder De Witt, Gregory Farquhar, Jakob Foer- ster, and Shimon Whiteson. Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning. arXiv preprint arXiv: 1 1485, 2018.
Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang- Shang-Chieh Chen. Mo- bilenetv2: Inverted residuals and linear bottlenecks. Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4510-4520, 2018.
Dan Simon. Optimal state estimation: Kalman, H infinity, and nonlinear approaches. John Wiley & Sons, 2006.
Kyunghwan Son, Daewoo Kim, Wan Ju Kang, David Earl Hostallero, and Yung Yi. Qtran: Learn- ing to factorize with transformation for cooperative multi-agent reinforcement learning. arXiv preprint arXiv:1905.05444 2019.
Peter Sunehag, Guy Lever, Audrunas Gruslys, Wojciech Marian Czarnecki, Vinícius Flores Zam- baldi, Max Jaderberg, Marc Lanctot, Nicolas Sonnerat, Joel Z. Leibo, Karl Tuyls, et al. Value- decomposition networks for cooperative multi-agent learning based on team reward. In AAMAS, pp. 2085-20888 2018.
Ming Tan. Multi-agent reinforcement learning: Independent vs. cooperative agents. In Proceedings of the tenth international conference on machine learning, pp. 330-337, 1993.
Ziyi Wang, Keuntaek Lee, Marcus A Pereira, Ioannis Exarchos, and Evangelos A Theodorou. Deep SDEs for min-mar max control. In 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 6807-6814. 14. IEFE, 2019a.
Ziyi Wang, Marcus A Pereira, and Evangelos A Theodorou. Deep 2fbsdes for systems with control multiplicative noise. arXiv preprint
2019b.
Yaodong Yang, Rasul Tutunov, Phu Sakulwongtana, Haitham Bou Ammar, and Jun Wang. -r-nk:: Scalable multi-agent evaluation through evolution. arXiv preprint arXiv:
2019.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. In Advances neural information processing systems, pp. 3391- 2017.
Ming Zhou, Yong Chen, Ying Wen, Yaodong Yang, Yufeng Su. Weinan Zhang, Dell Zhang, and Jun Wang. Factorized q-learning for large-scale multi-agent systems. In Proceedings of the First International Conference Distributed Artificial Intelligence, pp. 1-7, 2019.

---

Under review as a conference paper at ICLR 2021
APPENDIX
A MULTI-AGENT HJB DERIVATION
Applying Bellman's principle to the value function equation 3 as following
++
(1, x()) inf E
(i(t+ di, (t
C'
u;EU;
inf E (C'dt V (t, (t)) + (t,
a.EU;
1 + (IT X (I))dX + (t. (()EE") ))d )dr
inf E
(t. (())dtt
a,EU;
+ V=T (t) (f) + tr X (t. (+))EE dt
in [C'd (2((, (1(,))(1))))) X())dl
aieu;
+ ViT(t. (t. X(I)((( + dU) + 2 tr X (1))EX))))) dt
0 = ((() + inf u.el,
+ (t, (()) +U)]] (V (t, (t, (())22))
(11)
Given the cost function assumption, the infimum can be obtained explicitly using optimal control u R (G + oTz)). With that we can obtain the final form of the HJB PDE as
V + h + V (ʃ + -i) + (r E O, = (())))).
(12)
B FBSDE DERIVATION
Given the HJB PDE in equation (2019) to obtain a set of FBSDE as
4 one can apply the nonlinear Feynman-Kac lemma Han & Hu
dx (t) = (f D) + EaW, X(0) = Eg
(13)
dv hhtt + T Edw, V(X(T)) = (()))))
Note that the forward process X is driven by the control of all agents other than i. This means that agent searches the state space with Brownian motion only to respond to other agents' strategies. To increase the efficiency of the search, one can add any control from agent i to guide its exploration, as long as the backward process is compensated for accordingly. this work, since we consider problems with closed form solution of the optimal control Uim, add it to the forward process for importance sampling from a new set of FBSDEs.
d.X = +f+ d),, + EdW, X(0) = Zo
(14)
dvi = - v GUG + V yaw, V(T) = -
C CONTINOUS TIME EXTENDED KALMAN FILTER
The Partial Observable Markov Decision Process is generally difficult to solve within infinite di- mensional space belief. Commonly, the Value function does not have explicit parameterized form.
Kalman filter overcome this challenge by presuming the noise distribution is Gaussian distribution. In order to deploy proposed Forward Backward Stochastic Differential Equation (FBSDE) model in the Belief space, need utilize extended Kalman filter in continuous time Jazwinski (970))
correspondingly. Given the partial observable stochastic system:
dr di =(x, u, w. ()2 and z = ==1(x, v,
(15)
12

---

Under review as a conference paper at ICLR 2021
Where f is the stochastic state process featured by Gaussian noise w (0, Q), is the obser- vation function while v ~ (0, R) is the observation noise. Next, we consider the linearization of the stochastic dynamics in equation 20 represented as follows:
oʃ dr
0ʃ Ow
Oh
Oh
I.
M
Q = LQL"" f= MRM
(16)
dr
dv
write the posterior mean state 2 and prior covariance matrix P estimation update rule by Simon (2006):
2(0) E[z(0)), (T( = E[(((0) 2)(x(0) =
K PCT
(17)
å = f(0, u, wo, t) + K| h(2, vo. t)]
p- AP- P ^ Q C
We follow the notation in (Simon) 2006), where is the real state, è is the mean of state estimated by Kalman filter based on the noisy sensor observation, P represents for the covariance matrix of the estimated state, nominal noise values are given as Why 0 and th where superscript + the posterior estimation and is the prior estimation. Then we can define Gaussian belief dynamics as b b Pt) by the mean state and variance P of normal distribution. M(te; P5
The belief dynamics results in decoupled FBSDE system as follows:
dbg- y(bb; Uk O)dl + E(b,, ug O)dW, dW ~ ()
(18)
dV = -C" dt + V Edw
where:
b(t, X (t), umm (t); u
g(b;, Uz)
BeeCAApP + AT Qx PF C (xPP)
V KrCCPP dt
Eb,, uz)
(19)
V(T) (())
(() = E[X(O))
PT (0) (I(X(0) -)(
D DEEP SETS
function if maps its domain from to V. Domain X' a vector space I2 and y is a continuous space R. Assume the function take set input:X {x1....N }, then the function f is indifferent it satisfies property (Zaheer et al. 2017).
Property function f + y defined on sets is permutation invariant to the order of objects in the set. i.e. For any permutation function r: m=f(([x)...N)) [W
In this paper, discuss when is nerual network strictly.
Theorem X has elements from countable universe. A function f(X) is valid permutation invariant function, i.e invariant to the permutation of X, iff it can decomposed in the from p(Exex ((x)), for appropriate function p and
In the symmetric multi-agent system, each agents is not distinguishable. This property gives some hints about how to extract the features -ith agents by using neural network. The states of -ith agents can be represented
set:X [X1,X2, .... X,-1, ........, Xx We want to design neural network f which has the property of permutation invariant. Specifically, ø is represented as one layer neural network and p common nonlinear activation function.
13

---

Under review as a conference paper at ICLR 2021
concakeunte(Fi.F..
F-i
FC2
F;
F
FC1
ModeriantMMddl
X;
X
X(t)
Figure 10: Invariant layer architecture.
E INVARIANT LAYER ARCHITECTURE
The architecture of invariant layer is described in Fig. 10 The input of the layer is the states at time step l. The Invariant Model module in Fig. i0 is described Appendix where is a neural network and p is nonlinear activation function. The specific configuration of neural network in Invariant model can be found jn
Noticing that all the agents has the access to the global states, we define the state input features of neural network for ith agent as:
X,, = (1,, F1, #4-1, Fi
(20)
with shape [BS, N]. In the other word, we always put own feature at first place. For each agent there exists such feature tensor, then the shape of input tensor will become [SS, N, N] for invariant layer. In invariant layer, we first separate the input feature X, into two parts: X,, and X,,-s- Then the features of -ith agents Xt,-i will be sent to the invariant model. The shape of Xt,-i will be [B,N,N 1] where N is the number agents. First,we could use neural network to map the feature into N, dimension space, where N, is the feature dimensions. Then the shape of the tensor will become [BS, N,N N, After summing up the features of all the element in the set, the dimension of the tensor would reduce [BS, N, 1, Ny), and denote this feature tensor Fi. However, the memory complexity is O(N2 x NN)) which is not tolerable when the number of agent N increases. Alternatively, we can simply mapping the feature tensor [BS, N]] into desired feature dimension Ny. then the tensor would become BS, N. N2 and denote it be F2. Now create another tensor which the average of features element in set with size [BS, 1, N2] and we denote to be F.. Then we denote Fy = (F, x F2)/ (NV (N-1) -1) which has size of BS, N. Nyy). We find that F22 Fi, and the memory complexity of computing F/ is just O(N). The derivation true the system is symmetric and the agents are not distinguishable. The trick can extended to high state dimension for individual agent.
14

---

Under review as a conference paper at ICLR 2021
Via
V2
KG
Min-
%
Xy-1
Figure 11: FBSDE Network for Single Agent. Note that the same FC is shared across all timesteps.
Pank-ta Susetre
Hans- Sandi ne sirvorant Layer (Oun)
109
invartart Layor 10un)
Training
RSE
10-1
20
40
60
80
100
40
60
80
100
Number of Stages
Number of Stages
Figure 12: Superlinear dynamics comparison between baseline and our algorithm
F INTERBANK
By pluging the running cost to the HJB function, one can have,
N Σ 1=1
Vi, + inf u.EU,
la(x - + + uu² -qu;(x (x))) + _x - x1)² -x,}
+
2
(21)
ク tr( str(Vez, (2, 0.
By computing the infimum explicitly, the optimal control of player is:u; (X,t) = 9(8 - (x))
V (X,t) The final form of HJB be obtained
1 (r 2n, E.T + a(x - -X,) +
Vi, 2
Σ 1a(x -X,) + u
jzi
(22)
X x
(g(X X2) 2 =
Applying Feynman- -ac lemma to equation
22 the corresponding FBSDE system is
dx = (f( +) (t), E(t,
+() (()) X(0)
AV, = -1 x,) (a x.) 12.)) uidd V. V(T) ((X(T))
(23)
15

---

Under review as a conference paper at ICLR 2021
of
-0.
-0.5
-0.5
Gii CrngeE Se
-10
-1.0
Figure 13: car racing problem with 8 second time horizon.
G BELIEF CAR RACING
The full stochastic model can be written as
dx
(f(x) + G(x)u)dt + E(x)dw,
z h(x) + m
v cos 0
0
sin
0 0
(24)
f(x)
G(x) = -(x)
h((x) x
Carag
0
0
v/L
Where dw is standard brownian motion. We consider the problem of two cars racing on circle track. The cost function of each car is designed
2
y²
J. exp
+ ReLRR -v + exp (- d)
a
62
track cost
vefocity cast
collision cost
Where d is Euclidean distance between two cars. In this showcase, we use continuous time extended Kalman Filter to propagate belief space dynamics described in equation T9] The detailed algorithm for Belief space deep fictitious play FBSDE can found Appendix. We introduce the concept of game by using additional competition cost:
(0) sin(
T
J 42
J Jeompetition = exp(
5/1 y/2
Where 24, is the r, position of ith car. When ith car is leading, the competition loss will be minor, and it will increase exponentially when the car trailing.
Thanks to decoupled BSDE structure, each car can measure this competition loss separately and optimize the value function individually.
H ANALYTIC SOLUTION FOR ANTER-BANK BORROWING/LENDING PROBLEM
The analytic solution for linear bnter-bank problem was derived in Carmona et al. (2013). We provide them here for completeness. Assume the ansatz for HJB function is described as:
17(t)
(t x)
X
x2) ) = (t) I
(25)
16

---

Under review as a conference paper at ICLR 2021
Vo
Vi
Va
Vx
Vx
X
FCs
X
FCs
X
u
u
Figure 14: The gradient path of FBSDE model w/ and w/o importance sampling. The figure on the left is FBSDE with importance sampling and the figure on the right is FBSDE without importance sampling. One can identify that the framework with importance sampling would lead to long chain of gradient.
0.25
W9 impotatt samping
ait ipporarkssrppln
impetantsurginn
14.17
important samp
0.20
Training
0.15
0.10
0.05
2x10
0.00
20
20 Number Stades
Number Stades
Figure 15: The training loss and RSE of LSTM backbone FBSDE architecture w/ and w/o impor- tance sampling
Where p(t) are scalar functions. The optimal control under this ansatz is:
- N x X.)
(1, X) q (()
(26)
By pluginging the ansatz into HJB function derived in 22 one can have,
ii() 2a + g)n(t) +
N2 nn(() - (c (icc-9),n(TT (T) -c
(27)
((t) = - 2 - ())(11)))(1 N ))((),, (()) = O.
There exists the analytic solution for the Riccati equation described above as,
(T m)(t) = -(c (e ( -
c(8+ e XT -8) 8-
(28)
(5 -0- 1,0 ((T-)))((( -1
Where 8th -a + R and R (a + q)² (1- -92)
I IMPORTANCE SAMPLING
Fig. 14 demonstrates how fully connected layers with importance sampling would lead to extreme deep fully connected neural network. Fig. [5]]dmonsttttttee how importance sampling helps increase convergence rate in FBSDE with LSTTM backbone. The experiment conducted with 50 agents and 50 stages. All the configuration is identical except the existence of importance sampling.
J EXPERIMENT CONFIGURATIONS
This Appendix elaborates the experiment configurations for section 4 For all the simulation in section 4 the number of SGD iteration is fixed NsGD 100. We are using Adam optimizer
17

---

Under review as a conference paper at ICLR 2021
nvarant layer (Durs) sinvarant Laper (Ous)
ant (oye)
invarant Layer (Ous)
4110
109
Training Loss
Total Loss
10*
4x10
Number of Stages
Number of Stages
Figure 16: The Total loss and RSE of 1000 agents simulation
with 1E-3 learning rate for all simulations.
In section 4.1 For the prediction of initial value function, all frameworks are using layers feed forward network with 128 hidden dimension. For the baseline framework, we followed the suggested configuration motioned in Han et al. (2018). each time steps, Vz,; approximated by three layers of feed forward network with 64 hidden dimensions. We add batch norm [offe & Szegedy 2015) after each affine transformation and before each nonlinear activation function. For Deep FBSDE with LSTM backbone, are using two layer LSTM parametrized by 128 hidden state. the framework includes the invariant layer, the number of mapping features is chosen to be 256. The hyperparameters of the dynamics is listed following:
= 0.1, q = 0.1, = 0.5, e = 0.5, p = 0.2, a= -T
(29)
In the simulation, the time horizon is separated into 40 time-steps by Euler method. Learning rate chosen to be IE-3 which is the default learning rate for Adam optimizer. The initial state for each agents are sampled from the uniform distribution [6,, Where dg is the constant standard deviation of state (t) during the process. In the evaluation, we are using 256 new sampled trajectory which are different from training trajectory to evaluate the performance in RSE error and total cost error. The number stage is be 100 which enough for all framework to converge.
In section 4.2 the hyperparameter is listed as following:
Cdrag 0.01, L 0.1, 0.5, T 10.0
(30)
The observation noise is sampled from Gaussian noise rolled into 100 time-steps by Buler method. this experiments, the initial value VÚ is approximated single trainable scale and (t) is approximated by two layers of LSTM parametrized with 32 hidden dimensions. The number of stage is set to be 10.
(O00,.011 The time horizon is en-
18

---

Under review as a conference paper at ICLR 2021
Algorithm 2 Scalable Deep Fictitious Play FBSDE
Jyyeer-prrameters..: Number of players, T: Number of timesteps, M: Number of stages in fictitious play, N gg Number of gradient descent steps per stage, Un: the initial strategies for players in set B: Batch size, c: training threshold, At: time discretization
2: Parameters: V (æo; c): Network weights for initial value prediction, 0: Weights and bias of fully connected layers and LSTM layers.
3: Initialize trainable papermeters:8f. d
4: while LOSS is above certain threshold e do M do
5: for
6: for all i E TI in parallel do
fT 7: Collect opponent agent's policy fiSTTM, FFo ())
8: for / < to Ng do
9:
for t + 1 to T - do
for <- to in parallel do
Compute network prediction for ith player: Vinia. = SFC, (FESTM, (X/ (/11)
12:
Compute ith optimal Control:u = - Su.fhe + Q+
13:
Infer -ith players' network prediction: V2_
FC LSTM- (X,; 0 02:))
pin-1 (fm-
14:
Compute -ith optimal Control:uu - R_ (G Vol
V Q Q_,x!_)
15:
Sample noise AW1 (0,
Propagate FSDE: X = frSDE (X, wht u AW ,t)
17:
Propagate BSDE: V / = SBSDE (V; X/, u. AW3, f) end for
18:
end for
19:
20:
Compute loss: L= E (Vi. 1.T V2
21:
Gradient Update: 0',d0 end for
22:
23:
end for
24:
end for
25:
end while
19


Reviews:
[{"review_id": "vAR77G0R1IX", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Clarity:\nTill page 3 the paper was easy to follow, i.e., the analytical expressions in eq(5), and the basic idea of Algorithm 1 (which is same as prior works by Han et al. , Wang et al., Periera et al.) are clear.  However, after page 3 the paper is hard to follow. The specific points are as follows:\n1) It looks like both LSTM and FC have been tried in the past.  So what is the novelty here? Is it making the deep FBSDE framework scalable?  and if so how is this achieved? by introducing the invariant layer? or just using the symmetry property to share the networks?\n2) Comparisons with Han& Hu (2019) is presented only in Table 2. Figure 5 says comparison with Han & Hu (2019), but only FC w/wo invariant layer and LSTM w/wo invariant layer have been presented. Is it true that Han & Hu (2019) is FC and LSTM without the invariant layer and the current approach in the paper is FC and LSTM with the invariant layer?\n3) Figure 2, says comparison between analytical and deep FBDSDE solutions. Yet, 10 trajectories are displayed. Do they correspond to 10 different agents? If  so, what is the difference between the 10 trajectories and the deep FBSDE solution?\n4) In the autonomous racing section,  the authors  mention \"The results emphasizes the generalization ability of our framework\" what is generalization here? Is it that the method also works on a different domain?\n\nQuality:\n1) The main contribution seems to be scalability. It will be a lot helpful if Section 3.2 is elaborated a bit more, where the `scalability' aspects of the current work is discussed in detail. As of now, Section 3.2 seems `rushed'.\n2) Table 2 compares the proposed method with Han&Hu (2019). This is done for 10 agents. Yet, we do not know what happens as we increase the number of agents.\n3) Figure 4 has number of agents in x-axis, yet it compares only the various implementations of the current work and prior work is not included. \n\n\nNovelty:\nIt appears that the paper puts together blocks/algorithms in prior works (say invariant layer from Zaheer et al. 2017, deep FBSDE from Wang et al., Periera et al., Han & Hu). This way novelty seems  to be limited. \n\nSignificance:\nScalability is the main take away of this paper. Figure  5 and Figure 4 show that the proposed method is better than prior methods, yet the performance improvement is not significant. However, the savings could be in the time/space complexity, which the paper does not elaborate. In short, due to the fact that certain critical parts have not been explained it is hard to judge the significance.\n\n\nOverall Feedback:  The critical information regarding the invariant layers, scaling, savings in the scaling is missing. Also, adding this information may not take significantly extra space. So, it will be great if the authors can provide this information.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "V4rOyZuiYxb", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n\nThe paper introduces improved deep learning architecture for solving stochastic differential games by fictitious play. Compared to previous best model it uses LSTM instead of MLP to capture forward dynamics of the system, importance sampling and order invariant encoding of other agents to improve sample efficiency of learning.\n\n\nStrong points\n\n* Order invariant encoding uses inherent structure of the problem that improves sample efficiency compared to previous approaches. \n* Batching of some operations speeds up the algorithm.\n* Two different domains are used to evaluate the model.\n\n\nWeak points\n\n* Time complexity claims are problematic.\n* The paper is sometimes difficult to follow. It seems like 8 pages aren't enough to describe the whole approach in detail. Many things in appendix seem central for the presented system. \n* Importance sampling that is claimed to be important ingredient isn't described well enough neither in the main text nor in the appendix.\n* Quantitative evaluation is presented only for domains that can be already solved analytically. In other domains only qualitative results are presented.\n\n\nRecommendation\n\nI recommend rejecting the paper due to lack of clarity and lack of evaluation against other methods suitable for solving problems that can't be solved analytically.\n\n\nQuestions\n\n* It seems to me that \"propagate by batch\" time complexities in Table 1 assume constant time computation of batches. Is that correct? That would however be a simplification, while batched computation is much faster on GPUs it isn't in general constant time. This view is further supported by Fig 4 where empirical time complexity also isn't constant as is suggested by Table 1.\n\n* My understanding of empirical results is that the model is run in domains with analytical solution only as sanity check. The true value is in domains without analytical solution (e.g. Superlinear Simulation section). Current evaluation for superlinear setup and autonomous racing is only qualitative. I would like to see comparison to previous methods applicable to these domains if there are any (numerical solvers?). If there aren't any the paper should explain why this is the case. I understand that the model is an improvement over Han & Hu however does it allow us to do something we couldn't do before when we consider even non learning methods? Please reflect on this point to help me better understand main contribution of the paper. This broader context would help readers (like me) that aren't experts in stochastic differential games.\n\n\nPossible improvements\n\n* Since most of the results compare presented model against Han & Hu 2019 it would help to add a paragraph that briefly summarizes algorithmic/model differences. Is it true that current system is Han & Hu with LSTM instead of MLP + importance sampling + invariant layer? \n\n* In table 2 unit of \"Total time\" isn't specified.\n\n* \"memory complexity of LSTM with respect to time is O(1)\" --- this is true for inference time, at train time O(T) activations still have to be stored. (If they aren't to be recomputed again for each t < T). The text can be more clear on that.\n\n* In Figs 5 and 6 captions say that it compares current system against Han & Hu however the legend shows FC and LSTM with and without invariant layers. I assume that Han & Hu = FC and current system is LSTM + invariant layer. However being more explicit about that would  help. Does FC model here use importance sampling or not?\n\nTypos\n* solutions exist only few special -> only FOR few\n* stochastic optional control problem -> OPTIMAL control\n* drive fast than -> drive fastER\n* global augment -> augmentED\n* The paper would benefit from further proofreading. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "6Cd6XNlI996", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\n\nSummary:\nThe paper proposes a deep learning based algorithm for computing Multi agent Nash equilibrium, relying on the Forward Backward Stochastic Differential Equation representation (BSDE) of the solution together with Fictitious play algorithm. The authors present numerical examples on linear quadratic symetric stochastic games with 1000 agents, as well as solutions to partially observed 2 agents racing problem using extended Kalman filter. \n\nStrength of the paper:\n- The derivation on a scalable  Deep learning based algorithm for solving FBSDEs and related stochastic game;\n- The possibility to approximate the Nash equilibrium in a game with a large number of players (more than 1000)\n- The presentation of examples in a partially observable framework, where Kalman filtering is necessary to derive the solution of the game.\n\nWeakness of the paper:\n- The BSDE presented in the paper is obtained through the consideration of the corresponding Hamilton Jacobi Bellman  Partial Differential Equation, although such representation could a priori be obtained in a more general and possibly non Markovian framework\n- The BSDE representation is claimed to be different form the one introduced in Han & Hu, but this should be detailed more precisely, as few information on this crucial point is given in the current version of the paper. Is it e.g. related to the use of Pontryagin principle of value process approach for the FBSDE? \n- In the car racing example, it does not seem clear how the proximity to a Nash equilibrium is quantified. It is also surprising to focus on a 2 agents example, while the paper seems to intend to emphasize the scalability of the approach.\n- It is a priori not clear how the presented BSDE representation differs from a related recent paper by Han, Hu and Long (Convergence of Deep Fictitious Play for Stochastic Differential Games). This should be discussed.\n- It seems that this paper only focuses on games with unique Nash equilibrium, although the use of RL algorithm for games seems to become intricate whenever several Nash equilibrium shop up into the picture. \n\n\nRecommandation; Given the strengths of the paper in terms of FBSDE representation of the solution, together with the weaknesses presented above, I recommend to reject the paper, but am looking forward to get clarifications on the points raised above.\n\nMinor points:\n1. Typos: « drive fast than » p8.; « invarint layer » in Figure 5; \n2. Figure 2: Can you clarify the number of agents considered for such approximation? By the way, how does the solution changes as the number of agents increases? It could a priori seem to be quite stable.\n3. Do the games considered here need to be non-cooperative by nature? For which purpose for the algorithm?\n4. Some important references seem to be missing: some on the use of Fictitious Play for learning the Nash equilibrium in multi player games; some connecting BSDE representation to multi-player  stochastic games.\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces a scalable method for FSP based on FBSDE. The method is theoretically derived then applied on two problems, one simple but with many (1000) agents, and one with only 2 agents but partial observability.

The main strength of this paper lies in the scalability and the time complexity of the proposed method. Computing Nash equilibriums for many agents is a difficult problem and this paper is interesting in this aspect.

However, the reviewers point out several weak points to this paper. The difference with a previous work by Han, Hu and Long needs to be highlighted. Some parts of the paper are not clear, and too much of the important results are pushed into the appendix. Maybe this work is not best fitted to a conference format, and should be submitted to a journal? Another concern raised by the reviewers is that the experimental section does not show significant enough results, and that it is surprising to see a 2-agents problem as an illustration of a method that is aiming at addressing scalability with respect to the number of agents.

Reviewers agree on rejection for this paper, although by a small margin. I therefore recommend rejection. I think that if the authors improve this paper by following the reviewer suggestions, it can be accepted in a future venue.
Decision: Reject