Deep Generalized Schrödinger Bridge
Authors: Guan-Horng Liu
Tianrong Chen
Oswin So
Evangelos Theodorou
Venue: NeurIPS 2022 Accept (2022)
Keywords: Mean-Field Game
Schrödinger Bridge
Deep Reinforcement Learning
Forward-Backward Stochastic Differential Equations

Abstract: Mean-Field Game (MFG) serves as a crucial mathematical framework in modeling the collective behavior of individual agents interacting stochastically with a large population. In this work, we aim at solving a challenging class of MFGs in which the differentiability of these interacting preferences may not be available to the solver, and the population is urged to converge exactly to some desired distribution. These setups are, despite being well-motivated for practical purposes, complicated enough to paralyze most (deep) numerical solvers. Nevertheless, we show that Schrödinger Bridge — as an entropy-regularized optimal transport model — can be generalized to accepting mean-field structures, hence solving these MFGs. This is achieved via the application of Forward-Backward Stochastic Differential Equations theory, which, intriguingly, leads to a computational framework with a similar structure to Temporal Difference learning. As such, it opens up novel algorithmic connections to Deep Reinforcement Learning that we leverage to facilitate practical training. We show that our proposed objective function provides necessary and sufficient conditions to the mean-field problem. Our method, named Deep Generalized Schrödinger Bridge (DeepGSB), not only outperforms prior methods in solving classical population navigation MFGs, but is also capable of solving 1000-dimensional opinion depolarization, setting a new state-of-the-art numerical solver for high-dimensional MFGs. Our code will be made available at https://github.com/ghliu/DeepGSB.

Deep Generalized Schrödinger Bridge
Guan-Horng Liu', Tianrong Chen', ; Oswin So Evangelos A. Theodorou'
GGeorgia Institute Technology, USA
Maasachussetts Institute of Technology. USA
{ghliu, ti tianrong. chen, evangelos.. theodooou) @gatech. edu oswinsoCmit. edu
Abstract
Mean-Field Game (MFG) serves crucial mathematical framework in modeling the collective behavior individual agents interacting stochastically with a large population. In this work, aim at solving challenging class of MFGs in which the differentiability of these interacting preferences may not be available to the solver, and the population is urged converge exactly some desired distribution. These setups are, despite being well-motivated for practical purposes, complicated enough to paralyze most (deep) numerical solvers. Nevertheless, we show that optimal transport model - can
Schrödinger Bridge - as an be generalized to accepting mean-field structures, hence solving these MFGs. This is achieved via the application of Forward- -aarrd-Bakwardd Stochastic Differential Equations theory, which, intriguingly, leads computational framework with similar structure to Temporal Difference learning. As such, it opens up novel algorithmic connections facilitate practical training. We show that our proposed objective function provides necessary and sufficient conditions to the mean-field problem. Our method, named Deep Generalized Schrödinger Bridge (DeepGSB), not only outperforms prior methods in solving classical population navigation MFGs, but is also capable solving 1000-dimensional opinion depolarization, setting new state-of-the-art numerical solver for nigh-dimensional MFGs. Our code will be made available at https:// gigghh........ com/ ggw.g/DeeepGSB.
Deep Reinforcement Learning that we leverage
Introduction
On scorching morning, you navigated through the crowds toward the office. As you walked through a crosswalk, you were pondering the growing public opinion on new policy over the past week, and suddenly interrupted by the honking as the traffic started moving...
SB
DeepRL
DeepGSB (ours)
From navigation in crowds propagation of opinions and traffic move- ment, examples of individual agents interacting with a large population widespread in daily life and, due to their prevalence, appear an important subject in multidisciplinary scientific areas, including economics [1, 2], opinion modeling [3-5], robotics [6, 7], and more recently machine learning [8-10].
Solving 1000-dim opinion MFG
Polartted
Modersted
Figure 1: DeepGSB paves new algorithmic connec- tion between Schrödinger Bridge (SB) and model- based DeepRL for solving high -ith-imnnnsionl MFGs.
Mathematically, the decision-making processes under these scenarios can be characterized by the Mean-Field Game [1 []1-13] (MFG), which models noncooperative differential game finite horizon between a continuum population of rational agents. Let u(x, 1) be the value
'These authors contributed equally, Work was done while Oswin was Georgia Tech.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Table 1: Comparison to existing methods w.r.t various desired features in Mean-Field Games (MFGs). Our DeepGSB is capable of solving a much wider class of MFGs higher dimensional state spaces.
continuous state space
stochastic MF dyn. (2)
converges to exact Prarget
discontinuous
highest
MF interaction F
dimension
/ Ruthotto et al. [14]
X
X
X
100
Lin et al. [15]
/
100
Chen [16]
x
V
V
X
DSe (ours)
1000
function, also known as optimal cost-to-goal, that governs agents' policies at each state x E Rd and time / E [0, 7T, and denote the resulting population density by p(:,() E P(RR), where P(R4) is the set of probability measures on R.. At the Nash equilibrium where no agent has the incentive to change his/her decision, MFG, at its most general form, solves the following partial differential equations (PDEs):
Bu(c.)) de + HI, Vu, p) ]02 F(x, p),
u(x, G(();(())) T))
(I)
Op(z,t) 01
V (p Hx, Vu, - 0(r;0)=po(z)
:
where V. V., and A are respectively the gradient, divergence, and Laplacian operators. 2 These two PDEs are respectively known as the Hamilton-Jacob Jacobi-Bellmal (HJB) and Fokker-Plank (FP) equations, which characterize the evolution of u(x: t) and p(z, t). They are coupled with each other through the Hamiltonian (x, P. p): R& x R P(IR)) + R, which describes the dynamics of the game, and the mean-field interaction F(z, p) Rd x P(R") +R, R, which quantifies the agent's s preference when interacting with the population. The terminal condition G typically penalizes deviations from some desired target distribution Purget, e.g., G R (p(- l (-)). Given solution (u,p) to (1), each agent acts accordingly and follows stochastic differential equation(SDE)
dX, (X,, Vu(X,, (), ())4 odW, Xo ~ po:
(2)
where W, E 1dd the Wiener process and a E IR is some diffusiio scalar. At the mean-field limit, i.e., when the number of agents goes to infinity, the collective behavior of (2) yields the density p(:, ().
Numerical methods for solving (1) have advanced rapidly with the aid of machine learning. Seminar works such as Ruthotto et al. [14] and Lin et al. [15] approximated (u, p) with deep neural networks (DNNs) and directly penalized the violation of PDEs. Despite showing preliminary successes, the underlying dynamics (2) were either degenerate (e.g., o == 0) [14]. or completely discarded by instead regressing network outputs on the entire state space [15], which can scale unfavorably as the dimension d grows. An alternative that avoids both limitations, i.e., it keeps the full stochastic dynamies in (2) while being computationally scalable, is to recast these PDEs to a set of forward- backward SDEs (FBSDEs) by applying the nonlinear Feynman- fey Lemma [17-19]. The FBSDEs analysis appears extensively in the theoretical study of MFG [20-23], yet development of scalable FBSDEs-based solver has remained, surprisingly, limited. Our work contributes to this direction.
Since Prarget is known in prior, in many cases there are direct interests seek an optimal policy that guides the agents from an initial distribution Po to the exact Ptarget. while respecting the structure of MFG, particularly the MF interaction F(x, (z,p) p). Lifting (1) to this setup, however, is highly nontrivial. Indeed, replacing the soft penalty at u(x, 7) = DEL (Pllaae)) with a hard distributional constraint at p(x;, T) Purget yields an HJB whose boundary condition can only be defined implicitly through FP, which now contains two distributional constraints and resembles an optimal transport problem. As such, despite being well- mellvnotivated, most prior methods have struggled to extend this setup.
Ptarge))
In this work, we show that Schrödinger Bridge (SB), as an antropy-regulariae optimal transport problem [24-28], provides elegant recipe for solving this challenging class of MFGs with distribu- tional boundary constraints (po: Prurget). Although SB is traditionally set up with F := 0 [29-31], we show that SB-FBSDE [27]. an FBSDE-based method for solving SB, can be generalized to accept nontrivial F; hence solving MFG. Interestingly, the new FBSDEs system admits similar computa- tional structure to temporal difference (TD) learning, leading a framework that narrows the gap
I Precisely, Chen [16] considered discontinuous yet non-MF interaction, F:=F(x) on discrete state space. These operators taken w.r.t. unless otherwise noted. See Appendix A.I for the notational summary.

---

between SB and Deep Reinforcement Learning (DeepRL); see Fig. 1. This connection enables our method to take advantage of DeepRL techniques, such as target networks, replay buffer, actor-critic, etc, and, more importantly, to handle wide class of MF interactions that need not be continuous nor differentiable. This is in contrast to most existing works, which require differentiable [14, 15] or quadratic [32] structure on F. discretize the state space [16]. We validate our method, called Deep Generalized Schrödinger Bridge (DeepGBB), on various challenging MFGs from crowd navigation to high-dimensional opinion depolarization (where d 1000), setting a state-of-the-an art record in the area of numerical MFG solvers.
In summary, we present the following contributions.
We present a novel numerical method, rooted in Schrödinger Bridge (SB), for solving a challenging
class of Mean-Field Game where the population needs to converge exactly to the target distribution.
The resulting method, DeepGSB, generalizes prior SB results to accepting flexible mean-field interaction (e.g, non-differentiable) and enjoys modern training techniques from DeepRL.
DeepGSB achieves promising empirical results in navigating crowd motion and depolarizing dimessimaai opinion dynamics, setting a new state-of of-the-art numerical MFG solver.
2 Preliminary on Schrödinger Bridge (SB)
time 0.5
The SB problem was originally introduced in the 1930s for quantum mechan- ics [29, 33] and later draws broader interests with its connection to optimal transport and control [34-37]. Given a pair of boundary distributions (po. PT), SB seeks an optimal pair of stochastic processes of the forms:
time coordinate
dx, = tf + V log
+ a dW,, Xo ~ Pu:
(3a) Figure 2: Simulation
dx, 1-f 5) + log T (X,, s)]ds dW., Xo pr. (3b)
of the forward (3a)
and backward (3b)
While X₁ a standard stochastic process starting from pa. X, evolves along the "reversed" time coordinate s := T - from pr. The base drift f and diffusion a are typically known in prior and related to the Hamiltonian H. Suppose V E CRR, [0, TT) solve the following coupled PDEs,
SDEs in SB, which
are minimum-energy solution when (VV, v
obey the PDEs in (4).
W ((.0)( = Po (v..) - (+f)+ s.t.
(v((..)) VV s f
(4)
((,T)((,TT) = PT
then the theory of SB suggests that the SDEs in (3) are optimal solution (i.e., minimum control) optimization problem. Furthermore, the path-wise measure induced by (3a) along [0, T] is equal almost surely to the path-wise measure induced by (3b) along s == T t.
entropy-regularie
In other words, the two SDEs in (3) can be thought of as the "reversed" process to each other; and hence we also have Xy pr and XT ~ Po (see Fig. 2).
Due to the coupling constraints at the boundaries, solving (4) is no easier than solving (1). Fortunately, recent advances [27, 28] have demonstrated computationally scalable numerical method via the application of the nonlinear Feynman-Kee Kac (FK) Lemma a mathematical tool that recasts certain classes of PDEs into sets of forward-backwanl SDEs (FBSDEs) via some transformation. These nonlinear FK transformations are parametrized FB-FBSDE [27] by some DNNs with @ and ø, i.e.,
Za(:,) -) V log (-..))
and Zo x V log (...),,
(5)
and the FBSDEs resulting from (4) and (5) yield the following objectives (see Appendix A.2):
(Ipr(0)
E
Zo Zo
X., 2)11 + Zo(X., 8) 2x
(2 s)+ ds,
(6a)
(orr(()=
E 2
2 (X 0 2x,,,, Zo XX, + 2 (Xt, dt.
(6b)
The following lemma, as a direct consequence of Vargas [38], suggests that these objectives can be interpreted as the KL divergences between the parametrized path measures.
3

---

Lemma 1. Let q and 9º be the path-wise densities of the forwe and backward SDEs
dxp o (X?,tt)) dt odW,, dx.- = =-= ds + odW.
Then, we have
(x (1 Lirr()) and DRL( Lirr(0).
Proof. See Appendix A.3.2.
Lemma suggests that alternative minimization between (ir and LIr((0) is equivalent to performing iterative KL projection [39], and is hence equivalent to applying the Iterative Proportional Fitting [40] (IPF) algorithm to solve parametrized SBs [24, 25].
3 Deep Generalized Schrödinger Bridge (DeepGSB)
3.1 Connection between the coupled PDEs in MFG and SB
We begin by first stating problem of inter- est -st--Ma MFG with hard distributional constraints (Po. Plaget) in its mathematical form. Similar to prior works [14, 15], we will adopt the control- affine Hamiltonian, (xx, Vu, p) := 2 Vill
MFG (1) t
SB (4) $
MFG with Pirrget constraint (7)
Hopf-Cole
SB with MF
interaction (9)
DeepGSB Framework
Vu fax p). given some base drift f and diffusion scalar a. Substituting this control-aftin Hamilto-
Figure 3: Connection between different coupled
nian into the PDEs in (1) yields
PDEs appearing in MFG, SB, and DeepGSB.
Op(z.t) V (p f)) 102 0 p(x, po(x), p(x; Purree(())) Bu(z.)) de + 2 1 - VuT f 2 20 = p).
which, as we briefly discussed in 1, differ from (1) in that the boundary condition of the HJB, u(z,T) is now absorbed into FP and defined implicitly through p(z, T') = Ptarge(()). Since analytic conversion between the boundary conditions of (1) and (7) exists only for highly degenerate cases [41]. this seemingly innocuous change suffices to paralyze most prior methods." Nevertheless, (7) now describes a transformation between two distributions (from FP) while obeying some optimality (from HJB), it suggests a deeper connection to optimal transport, and hence the SB.
To bridge these new MFG PDEs (7) to the PDEs appearing SB (4), we follow standard treatment [30] and apply the Hopf-Cole transform [42, 43]:
V (x, t) == exp (- t)), (I, == p(x,, t) exp (u(x,
(8)
which, after some algebra (see Appendix 1.4.1 1 for details), yields the following PDEs:
(v..))) - T o FU
((,0)((,,0) = Po
s.t.
(ū(a,) - (7-((f)) 1 1 F ((,T) = Ptarget 8t
can be seen that (9) generalizes (4) by introducing the MF interaction F. Let (v, T be the solution to these new MF-extended PDEs in (9), and recall the Hamiltonian adopted in (7), one can find that
- (X, Vu, p) f V"Vu = f + o log V.
That is, the agent's 's dynamic (2) coincides with the forward SDE (3a) in SB. Hence, we have connected the MFG (1) and SB (4) frameworks through the PDEs in (7) and (9); see Fig. 3.
"Zhang and Chen [+1] suggested F = 0. f. == f(x) and degenerate Dirac delta distribution.
*For completeness. we note that when the base drift is independent the density, f := fæx). mean-field preference, F(p): Fiz, p) bp
&I is convex in p. the variational optimization inherited in (7) remains convex. In these cases, the discretized problems converge to the global solution [16, 32j. However, for generic mean-fied -ield dynamics, such as the polarized fxx p) in our (18). the problem is in general non-convex; hence only local convergence can be established (see e.g., Remark I in [16]).

---

3.2 Generalized SB-FBSDEs with mean-field interaction
With (9), we are ready to present our result that generalizes prior FBSDE for SB to MF interaction.
Theorem 2 (Generalized SB-FBSDES). Suppose V, V E C and let J, F satisfy usual growth and Lipchitz conditions [44, 45). Consider the following nonlinear FK transformations applied to (9):
Y = , f) = log V/ (),,);
Z = ( 1) = 0 V log V (X,, t);
(10)
Y = (X,,,) t) log T (X,,
Ž = 2X,,,
V log T (X,, t),
where X, follows (3a) with Xo Po. Then, the resulting FBSDEs system takes the form:
dX2 (fr + oZz) dt odW;
(11a)
sYp 1 1 Fb dt + Z dW,
FBSDEs w.r.t (3a)
(11b)
1 ( 1
(o fi)+ 2, Ze Fb) dt + 2 dW,
(11c)
Now, consider similar transformation (9) but instead w.r.. the "reversed" SDE X, (3b) and Xo ~ Purrgtt i.e. Y, Y(X,, 8, 8) = log V0 (XX,, 8), and etc. The resulting FBSDEs system reads
dx,
(fo + o oZ.) ds odW.
(12a)
ds + 2 dW, dY, 1 (/122,11 + V..., + fa) +2)+2222, 2, -.
FBSDEs w.r.t. (3b)
(12b)
dP 1 (-122.12+ ds + 2. dw,
(12c)
Since Yi + Y1 loo ((X,t) by construction, the functions ft and Fę in (11) take the arguments
f=:= fel (x, eY, exp(, vi)) and : Fx,,,, exp(Y: Y, + P:)).
Similarly, we have fa fx exp(Y, + Pa)) and F3 = Fx(X,, exp(Y, Pa)) in (12).
Proof. See Appendix A.3.3.
Just like how (9) generalizes (4), our results in Theorem also generalize the ones appearing in vanilla SB-FBSDE [27] (see (22) in Appendix A.2) by introducing nontrivial MF interaction F. Despite seemingly complex compared to the original PDEs (9), these FBSDEs systems - namely (11) and (12) stand as the foundation for developing scalable numerical methods, they describe precisely how the values of Y log and Y log V shall change along the optimal SDEs (notice, e.g., that both Y, and Z, are functions of X, from (10)). Essentially, the nonlinear FK Lemma provides stochastic representation (in terms of Y and 9) of the PDEs in (9) by expanding them w.r.t. the optimal SDEs in (3) using the Itô formula [46]. Consequently, rather than solving the PDEs (9) in the entire function space as in the prior work [15], it suffices to solve them locally around high probability regions characterized by (3), which leads to computationally scalable methods.
3.3 Design of the computational framework
Looking from Theorem 2, suffices to approximate Yo Y and V P with some parametrized functions (we use DNNs), since one may infer Za R VVY, and 2, ~ oVYo, as suggested by (10), and then solve for (X,, X,) via (11a, 12a). Below, we explore options of designing training objectives for (0, Φ), with the aim to encourage (Yo, Y%) to satisfy the FBSDEs systems in (11, 12).
Option 1: LIFF. Given how Theorem generalizes the in [27] (see (22) in Appendix A.2), it is natural to wonder adopting the computation used to derive (6), egg., Lirr (Φ) = E'yy + d
Additionally, have (or 1 dy. ]: see (24) in Appendix A.2 for the derivation.
5

---

suffices to reach the FBSDE (11). This is, unfortunately. not the case as one can verify that
TPP (0) - -
1 (ax2 + d8:0]
1 1
2i1 + V. (o 5) dt - CIF (Ø).
Despite that (11) differs from (22) by the extra terms "+F," in (11b) and = in (1lc), the two terms cancel out in the sum of d + dÝ," thereby yielding the same objectives that do not depend on F. This implies that naively optimizing LIPF from [27] is insufficient for solving FBSDE systems with nontrivial F. We must seek additional objectives, if any, in order to respect the MF structure.
Option 2: Lire Temporal Difference objective LTD- Let revisit the relation between the FBSDEs (11, 12) and their PDEs counterparts but this time the HJB in (7). Take (X,, Yt) for example: The fact that Y log V (X,,tt) as the stochastic representation of the HJB, which, crucially, can be seen as the continuous time analogue of the Bellman equation [47]. Indeed, discretizing (l)b) with some fixed step size òt yields
(x; suggests alternative interpretation of Y
y 246t V=+8=-,y- Y,, + +-112111= Ft)
öt 2 oW,, SW; (0,
(13)
which resembles a (non-discounted) Temporal Difference (TD) [48, 49] except that, in addition to the standard "rewards" (in terms of control and state costs), we also have a stochastic term. This stochastic term, which vanishes in the vanilla Bellman equation upon taking expectations, plays crucial role in characterizing the inherited stochasticity of the value function Y,. With this interpretation in mind, we can construct suitable TD targets for our FBSDEs systems as shown below.
Proposition 3 (TD objectives LTD for (11, 12)). The single-step TD targets take the forms:
TD
single
= +
2
+
V
20 - fi) + 2 -.- Fb
8t 27 sW,,
(14a)
2
TD single 8488
Y +
2
(o + fa) + 2 FF,
8s + 2 8W..
(14b)
with TDg == log Pa - Yo" and TDn == log Pianger
ve and the multi-step TD targets take the forms:
TD = TDo
multi
TD
8+55 = TDn + Σ SY=
(15)
T
T=ôt
T=óa
where 5Y, = TD TDe+ r+bt - Ye and 5Y, = TD
single
single stée
Y,. Given these TD targets, we can construct
T
LTD(0) = Σ [X))) -TDblll 8s, CTD(O)
Σ E (1Fo(X..)-TDD..)) öt. (16)
Proof. See Appendix A.3.4.
can be readily seen that the single-step TD targets in (14) obey a similar structure to (13), except deriving from different SDEs (11c, 12b). Doing so reduces the computational overhead, as the related objectives for each parameter, e.g., LIPF (0) and (0), can be evaluated from the same expectation. In practice, we find that the multi-step objectives often yield better performance, consistently observed in the DeepRI. literature [50-52]. Additionally, common practices such as computing TD, and TD, using the exponential moving averaging (i.e., target values) and replay buffers also help stabilize training. Finally, the fact that the TD targets in (16) appear as the regressands implies that from a computational standpoint, the MF interaction F' needs not to be continuous or differentiable.
Necessity and sufficiency of LIPF LTD- It remains unclear whether appending LTD to the objective suffices for (Ys, Yo) satisfy the FBSDEs (11, 12). Below, we provide a positive result.
Proposition 4. The functions (Yo, Zo. Yo. 2o) satisfy the FBSDEs (11,12) in Theorem 2 if and only if they are the minimizers of the combined losses L(0, () := LIPF (d) + LTD()) + LipF(0) + (T).
Proof. See Appendix A.3.5.

---

Algorithm Deep Generalized Schrödinger Bridge (DeepGSB)
Input: (Yo, Yo, oVe, a vY2) for critic or (Ya, Yo, Zo. Zo) for actor-critic parametrization. repeat
Sample X (xx, 2i, oW: heejo,7 from the forward SDE (aa) add " to replay buffer B.
for k = to K do
Sample on-policy X and off-policy X samples respectively from X and B. Compute [(Ø) (irr(d; X + LT Xx) + LTD(d; X.n) + Lrx X
Update á with the gradient (dC()) end for
Sample = 2g SW J from the backward SDE (12a); add X to replay buffer B.
for k 1 to K do
Sample on-policy X and off-policy X samples respectively from X and B.
Compute L(0) = Lir(0; (0; X..) + (0v X=)) + Liv(0; x (0; X.). Update I with the gradient Vo((0).
end for until converges
Proposition 4 asserts the validity of the combined objectives LIFF + LTD in solving the generalized SB-FBSDEs in Theorem 2, and hence the MIG problem in (7). shall be interpreted as follows: The minimizer of LIPF. as implied in Lemma 1, would always establish a valid "bridge" transporting between the boundary distributions Pg and Purgeet yet, without further conditions, this bridge needs not obey a "Schrödinger" bridge. While general IPF and Sinkhorn [16, 32], upon proper initialization or discretization, provides one way ensure the convergence toward the "S our Proposition suggests an alternative by introducing the TD objectives LTD- This gives us flexibility to handle generalized SB in MFGs where F becomes nontrivial or non-convex. Further, it naturally handles non-differentiable F, which can offer extra benefits in many cases.
Option 3: LIF + LTD + FK objective LyK. Though it seems sufficient to parametrize (Yo, Fo) then infer Ze = VV and Z == o vY,,, . as suggested in previous options, in practice we find that parametrizing (Zo, Zo) with two additional DNNs then imposing the following FK objective, i.e..
(Fx -
Σn E [
7 s]]] o), 8s, (Fx(Ø)
EE 1=0
(IoV
2 (Xxx))))
0) 8t,
often offers extra robustness. These objectives aim to ensure that the nonlinear FK (10) holds.
Our DeepGSB is summarized in Alg. 1. Hereafter, we refer Option and 3 respectively to DeepGSB critic and DeepGSB actor-critic, as Yo and Zo play similar roles of critic and actor networks [53, 54].
Remarks on convergence. Despite Alg. sharing a similar alternating structure IPF [16, 24, 27], the combined objective, e.g., L(Ø) x DKI. (e"llp") + Eg +Ege [CT] /f DKL. (o"Ile [pe)) ) is not equivalent to the (reversed) KL appearing in IPF. Instead, DeepGSB may closer to trust region optimization
[55], as both iteratively update the policy using samples from the previous stage while subjected to some KL penalty: (++1) arg min, DxI.(T
[[][[ + [C(T]] Hence, one can expect
DeepGSB to admit similar monotonic improvement and local convergence properties. We leave more discussions to Appendix A.4.2.
4 Experiment
Instantiation of MFGs. We validate our DeepGSB on two classes of MFGs, including classical crowd navigation (d=2) and high nigh-dimensional (d=1000) opinion depolarization. For crowd navigation, we consider three MFGs appearing prior methods [14, 15], including (i) asymmetric obstacle avoidance, (ii) entropy interaction with V-shape bottleneck, and (ii) congestion interaction on an S-shape tunnel. We will refer them respectively as GMM, V-neck, and S S-tunnel. The obstacles and the initial/target Gaussian distributions (Pu. Puaget) are shown in Fig. 4. For opinion depolarization, we set Po and Pharget to two zero-mean Gaussians with varying variances for representing the initially polarized and desired moderated opinion distributions. Finally, we consider zero and constant base drift f respectively for GMM and smeck//--unnel and adopt the polarized MF dynamics [4] for opinion MFG; see Sec. 4.2 for a detailed discussion.
7

---

GMM
V-neck
S-tunnel
Table MF interactions for 3 crowd navigation MFGs and the high- sigh-dimensional opinion MFG.
10
GMM (d=2)
Fobstacle
Au
V-neck (d=2)
Fobstacle 1 F F'entropy
Purpe!
20
20
-10
10
-15
15
S-tunnel (d=2)
Pobstacle F'congestoon Fentrops
Figure 4: Crowd navigation MFGs.
Opinion (d=1000)
MF interactions F. We follow standard treatments from the MFG theory [11] by noting that given a functional F(p) that quantifies the MF cost w.r.t. the population e.g., Fennopy == Ep p] or F congestion := Be. ++1 one can derive its associated MF interaction function F(z, p) by
taking the funetional derivative, i.e., *F(a) (x) F(z, p). Hence, the entropy and congestion MF interactions, together with the obstacle cost, follow (see Appendix A.4.3 for the derivation):
Feetropy == log p(z, t)+1, F Feongestion == Eyyp
Fobstacle == 1500-1lbss6 (17)
y
where (.) is the (discontinuous) indicator of the mroblem-dependee obstacle set. We summarize the MF interaction in Table 2.
Architecture & Hyperparameters. We parameterize the functions with fully-connected DNNs for crowd navigation, and deep residual networks for high-dimensional opinion MFGs. All networks adopt sinusoidal time embeddings and are trained with Adam [56]. All SDEs in (11, 12) are method. Due to space constraints,
solved with the Euler-Maruyy results of actor-critic parametrization DeepGSB-ac, and leave the discussion of critic parametrization DeepGSB-c, along with additional experimental details, to Appendix A.5.
will focus mostly on the
4.1 Two-dimensional crowd navigation
Figure 5 shows the simulation results of our DeepGSB-ac on three crowd navigation MFGs. We also report existing numerical methods [14-16] that are best-tuned on each MFG (see Appendix A.5. for details) but note that in practice, they either require softening F to differentiable [14, 15] to yield reasonable results, discretizing the state space [16), which can lead to prohibitive complexity."
We first compare to Chen [16] on GMM (see Fig. 5a) as their method only applies non-MF inter- action, i.e., F == Fzz). While DeepGSB-ac guides the population to smoothly avoid all obstacles (notice the sharp contours of Y around them). [16] struggles to escape due to the discretization of the state space (hence the policy). To better examine the effect of p in F(x, p). we next simulate the dynamics on V-neck (see Fig. 5b) with and without the MF interaction. It is clear that our DeepGSB-ac encourages the population spread out once the entropy interaction F Featopy is enabled, yet similar effect is barely observed in [14]. We observed difficulties in balancing the MF interaction F and the terminal penalty DKL (errgg))))) for [14], yet this problem is alleviated in DeepGSB by construction. Lastly, we validate the robustness of our method on S-tunnel (see Fig. 5c) w.r.t. varying diffusions = (0.5, 1,2). Again, our DeepGSB-ac reaches the same Piange despite being subject to different levels of stochasticity. This is in contrast to [15], which, due to discarding the SDE dynamics, necessitates solving PDEs on the entire state space that may be sensitive hyperparameters. In short, our DeepGSB outperforms prior methods [14-16] by better respecting obstacles and MF interactions yet without losing convergence Ptarget, and its performance remains robust across different MFGs.
4.2 High-dimensional opinion depolarization
Next, we showcase our DeepGSB in solving high- nigh-dimensional MFGs in the application of opinion dynamics [3-5], where each agent now possesses d-dimensional opinion x' Ed that evolves through the interactions with the population. In light of increasing recent attention, we consider a particular class of opinion dynamics known to yield strong polarization [4], i.e. the agents' opinions tend to partition into groups holding diametric views. Take the party model [4] for instance: Given random information & e & sampled from some distribution independent p. each agent updates
As stated in [16], the complexity scales quadratically w.r.t. the number of discretized grid points.

---

(a)
D0ep (ours) 1- 0.507
1 02257
-- 0.5T
(reed discred siate space!
(b)
DeepESB-ar lours)
Ruthotto et 134)
viee MF Plaraction
Weo ME
With ME
with ME
SD-ac t 5.507
t=
= 025
tH 0.75T
t=T
Ineed differentatic Fan
OPOS
o-20
o=20
Figure 5: Simulation of the three crowd navigation MFGs, including (a) GMM, (b) V-neck, and (c) S-tunnel, from
T. The first five columns show the population snapshots, each with different color, guided by our DeepGSB-ac, whereas the sixth (rightmost) column overlays the same population snapshots generated by existing methods [14-16]. The time- mare-varying contours represent Yo z log Y whose gradient relates to the policy via Z = VY. This figure is best viewed in color.
polarize dynamics fesores (18) dm22
Directional similarity facure d=1000
(b) Terminal distribution fr after applying DeepGSB-ac d-1000 (PCA embedding!.
Directional similarity after applying DeepG5B-ac
d-1000
highly
highly disagree
Figure 6: (a) Visualization of polarized dynamics Fpolarize in 2- and 1000 dimeeninni opinion space, where the directional similarity [3] counts the histogram of cosine angle between pairwise opinions at the terminal distribution pr. (b) DeepGSB-ac guides pr toward moderated distributions, hence depolarizes the opinion dynamics. We use the first two principal components to visualize d=1000.
the opinion following a normalized polarize dynamic Fpolarize Spotsiize/ [ ||
where
Fpolatize P:E) == Eyyo [a(x, (a(x,):E))) E) a(x, 3: = {
if Sign((x, - sig (18) otherwise
and j = 2/ The agreement function a(,; y; indicates whether the two opinions xr and y agree on the information &. Intuitively, the dynamic in (18) suggests that the agents tend to be receptive to opinions they agree with, and antagonistic to opinions they disagree with. As shown in Fig. 6a, this behavioral assumption, also known as biased assimilation [57, 58), easily lead to polarization.

---

We can apply our MFG framework (7) to this polarized base drift (18), where, starting from some weakly polarized Po. we seek a policy that compensates the polarization tendency and helps guide the opinion towards a moderated distribution Praget (assuming as Gaussian for simplicity). We consider the entropy MF interaction Pentropy& as encourages opinions diversity before reaching consensus. As shown in Fig. 6b, in both lower- (d=2) and higher- (d=1000) dimensions, our DeepGSB-ac successfully guides the opinion towards the desired distribution centered symmetrically at E gd, thereby mitigates the polarization. Results of DeepGSB-c remain similar despite being more sensitive to hyperparameters; see Appendix A.5.2. We highlight these state-of-the-ar results on a challenging class of MFGs that, comparing existing methods [14, 15], consider more difficult mean-fiell dynamic (f(z. p) vs. f()) in an order of magnitude higher dimension (d=1000 vs. d=100).
4.3 Discussion
Table 3: Comparison of DeepGSB-ac vs. DeepGSB-c w.r.t Wasserstein distance to Pharget and FBSDEs violation, in terms of TD errors and nonlinear FK, averaged over runs.
DeepGSB-ca vs. Deep Ta- ble compares actor-critic with critic parametrizations crowd navigation MFGs. While Deep- GSB-ac typically achieves lower Wasserstein and TD errors, sel- dom closes the consistency gap of FFx (0), as opposed to DeepGSB-c. In practice, the results of Deep- GSB-c are visually indistinguish- able from DeepGSB- ac, despite the different contours of Y; see Ap- pendix A.5.2 for more discussions.
FBSDEs Violation 4
MFGs
DeepGSB
W2 4
LTD())
LTD(O)
(r)
GMM
-ac
22
9,5+25
7.1+0.6
5,2+111
-C
.61
7.0+1.3
10.1+1.
0.0=0.0
V-neck
-ac
.00.1.00
4.9.
1.1
0.6
-C .01
8,2+008
8.7+1.6
0.0=0.0
S-tunnel
-ac
.01...0
12.
28.6
2.1
-c _031..1
30.916.9
26.4.555
0.0
DeepGSB works with intractable Ptarget. While the availability of the target density Puaget is a common assumption adopted in prior works [14, 15], in which Puargtt is involved in computing the boundary loss, in most real-world applications, Prarget is seldom available. Here, we show that DeepGSB works well without knowing Prarge (and Pa) long
sample from X, Po and Xo Ptargtt This is similar to the setup of generative modeling [27]. In Fig. 9 (see Appendix A.5.2), we show that DeepGSB trained without the initial and terminal densities can converge equally well. Crucially, this is because DeepGSB replies single-step TD objectives and KL-matching in IPF objective) to generate equally informative gradients. This is in contrast to [14, 15] where the training signals mostly obtained by differentiatingg through DKL Prarge): consequently, their methods fail to converge in the absence of Prarget-
variety of other mechanisms (e.g., self-consistency in
5 Conclusion, Limitation, and Boarder Impact
We present DeepGSB, a new numerical method for solving a challenging class of MFGs with distributional boundary constraints. By generalizing prior FBSDE theory for Schrödinger Bridge to accepting mean-field interactions, we show that practical training can be achieved via an intriguing algorithmic connection to DeepRL. Our DeepGSB outperforms prior methods in crowd navigation MFGs and sets a new state-of-the-art record in depolarizing (000-dimensional opinion MFGs. DeepGSB is mainly developed for MFGs in unconstrained state spaces such as R. Yet, it may be necessary to adopt domain-specific structures, egg,, constrained state spaces. Additionally, the divergence in the IPF objectives may scale unfavorably as the dimension grows. This may be mitigated by adopting a simpler regression from De Bortoli et al. [24]. Study of Mean-Field Games (MFGs) possesses its own societal influence. Thus, MFG solver, DeepGSB may pose potential impact in offering solutions to previously unsolvable MFGs under more practical settings.
Acknowledgments and Disclosure of Funding
The authors would like to thank Yu-ting Chiang, Augustinos and Molei for their helpful supports. The authors would also like to thank the anonymous Reviewer A4H3 for his/her initially harsh yet constructive comments on OpenReview, which led substantial improvements of the theoretical results. This research was supported by DoD Basic Research Office Award HQ003421 10002.
10

---

References
[1] Yves Achdou, Francisco Buera, Jean-Michel Lasry, Pierre-Louis Lions, and Benjamin Moll. Partial differential equation models in macroeconomies. Philosophical Transactions of the Royal Society A: Mathmmttical, Physical and Engineering Sciences, 372(2028):2110037) 2014.
[2] Yves Achdou, Jiequn Han, Jean-Michel Lasry, Pierre-Louis Lions, and Benjamin Moll. Income and wealth distribution in macrocconomics: continuous- approach. The review of economic studies, 89(1):45-88) 2022.
[3] Simon Schweighofer, David Garcia, and Frank Schweitzer. An agent-based model of multi- dimensional opinion dynamics and opinion alignment. Chaos: An Intendisciplinary Journal of Nonlinear Science, 30(9):093139 2020.
[4] Jason Gaitonde, Jon Kleinberg, and Eva Tardos. Polarization in geometric opinion dynamics. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 499-519, 2021.
[5] Jan Hazla, Yan Jin, Elchanan Mossel, and Govind Ramnarayan. A geometric model of opinion polarization. arXiv preprint arXiv:1910.05274. 2019.
[6] Zhiyu Liu, Bo Wu, and Hai Lin. mean field game approach to swarming robots control. In 2018 Annual American Control Conference (ACC), pages 4293-4298. IEEE, 2018.
[7] Karthik Elamvazhuthi and Spring Berman. Mean-field models in swarm robotics: A survey. Bioinspiration & Biomimetics, 15(1) 500010,,,,, 2019.
[8] Yiping Lu, Chao Ma, Yulong Lu, Jianfeng Lu, and Lexing Ying. A mean-field analysis of deep resnet and beyond: Towards provable optimization via overparameetrrizatoo from depth. arXiv preprint 2xXxi:2003.055000 2020.
[9] Kaitong Hu, Anna Kazeykina, and Zhenjie Ren. Mean-field langevin system, optimal control and deep neural networks. arXiv preprint 199.07789 2019.
[10] Weinan, Jiequn Han, and Qianxiao Li. A mean-field optimal control formulation of deep learning. arXiv preprint 1.07v:1800.00003 2018.
[11] Jean-Michel Lasry and Pierre-Louis Lions. Mean field games. Japanese journal of mathematics, 2(1):229-260, 2007.
[12] Olivier Guéant, Jean-Michel Lasry, and Pierre-Louis Lions. Mean field games and applications.
In Paris-Princeton lectures on mathematical finance 2010, pages 206-266. Springer, 2011.
[13] Alain Bensoussan, Jens Frehse, Phillip Yam, et al. Mean field games and mean field type control theory, volume 101. Springer, 2013.
[14] Lars Ruthotto, Stanley Osher, Wuchen Li, Levon Nurbekyan, and Samy Wu Fung. machine learning framework for solving high-dimensional mean field game and mean field control problems. Proceedings of the National Academy of Sciences, 117(17):183-9199 2020.
[15] Alex Tong Lin, Samy Wu Fung, Wuchen Li, Levon Nurbekyan, and Stanley Osher. Alternating the population and control neural networks to solve high- -igh-dimensionll stochastic mean-field games. Proceedings of the National Academy of Sciences, 1 118(31), 2021.
[16] Yongxin Chen. Density control of interacting agent systems. arXiv preprint a1X.v:2108.07342, 2021.
[17] 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-88116 8510, 2018.
[18] Ioannis Exarchos and Evangelos A Theodorou. Stochastic optimal control via forward and backward stochastic differential equations and importance sampling. Automatica, 87:159-165. 2018.

---

[19] Marcus Pereira, Ziyi Wang, Ioannis Exarchos, and Evangelos A Theodorou. Neural network architectures for stochastic control using the nonlinear feynman-ken lemma, arXiv preprint arXiv: wtt.:/922..99... 2019.
[20] René Carmona, François Delarue, and Aimé Lachapelle. Control of tickean-vlaso dynamics versus mean field games. Mathematics and Financial Economics, 7(2):131-166, 2013.
[21] René Carmona and François Delarue. Mean field forward-backward stochastic differential equations. Electronic Communications in Probability, 18:1-15, 2013.
[22] René Carmona and Mathieu Laurière. Convergence analysis of machine learning algorithms for the numerical solution of mean field control and games: li-the finite horizon case. arXiv preprint /00.:vv9000001..1 2019.
[23] René Carmona and Mathieu Laurière. Convergence analysis of machine learning algorithms for the numerical solution of mean field control and games i: the ergodic case. SIAM Journal on Numerical Analysis, 59(3): 455-1485, 2021.
[24] Valentin De Bortoli, James Thortoo, Jeremy Heng, and Arnaud Doucet. Diffusion schrödinger bridge with applications to score-based generative modeling. arXiv preprint arXiv:2106.01357, 2021.
[25] Francisco Vargas, Pierre Thodoroff, Neil D Lawrence, and Austen Lamacraft. Solving schrödinger bridges via maximum likelihood. arXiv preprint arXiv:2106. 02081, 2021.
[26] Gefei Wang, Yuling Jiao, Qian Xu, Yang Wang, and Can Yang. Deep generative learning via schrödinger bridge. arXiv preprint arXiv: 106. 10410, 2021.
[27] Tianrong Chen, Guan-Horng Liu, and Evangelos A Theodorou. Likelihood training of schrödinger bridge using forward-backward sdes theory. arXiv preprint arXiv:2110.11291, 2021.
[28] Charlotte Bunne, Ya-Ping Hsieh, Marco Cuturi, and Andreas Krause. Recovering stochastic dynamics via gaussian schr\," odinger bridges. arXiv preprint arXiv:2202.05722, 2022.
[29] Erwin Schrödinger. Sur théorie relativiste de l'électron l'interprétation de mécanique quantique. In Annales de I l'institut Henri Poincaré, volume 2, pages 269-310, 1932.
[30] Kenneth Caluya and Abhishek Halder. Wasserstein proximal algorithms for the schrödinger bridge problem: Density control with nonlinear drift. IEEE Transactions on Automatic Control, 2021.
[31] Julio Backhoff, Giovanni Conforti, Ivan Gentil, and Christian Léonard. The mean field schrödinger problem: ergodic behavior, entropy estimates and functional inequalities. Probabil- ity Theory and Related Fields, 178(1):475-530, 2020.
[32] Yongxin Chen, Tryphon Georgiou, and Michele Pavon. Optimal steering of inertial particles diffusing anisotropically with losses. 2015 American Control Conference (ACC), pages 1252-1257. IEEE, 2015.
[33] Erwin Schrödinger. Über die unkehrung der naturgesetze. Verlag der Akademie der Wis- senschaften in Kommission bei Walter De Gruyter u u..., 1931.
[34] Christian Léonard. From the schrödinger problem to the of Functional Analysis, (6799))1879-112) 2012.
problem. Journal
[35] Christian Léonard. A survey of the schr'. odinger problem and some of its connections with optimal transport. arXiv preprint arXiv: 1308.:1330..20 0215, 2013.
[36] Michele Pavon and Anton Wakolbinger. On free energy, stochastic control, and schrödinger processes. In Modeling, Estimation and Control of Systems with Uncertainty, pages 334-348. Springer, 1991.
[37] Paolo Dai Pra. A stochastic control approach to reciprocal diffusion processes. Applied mathematics and Optimization, 23(1):313-32, 1991.
12

---

[38] Francisco Vargas. Machine-learninn approaches for the empirical schrödinger bridge problem. Technical report, University of Cambridge, Computer Laboratory, 2021.
[39] Jean-David Benamou, Guillaume Carlier, Marco Cuturi, Luca Nenna, and Gabriel Peyré. Itera- tive bregman projections for regularized transportation problems. SIAM Journal on Scientific Computing, A7(2):A1111-A 138, 2015.
[40] Solomon Kullback. Probability densities with given marginals. The Annals of Mathematical Statistics, 1934)112331 1968.
[41] Qinsheng Zhang and Yongxin Chen. Path integral sampler: stochastic control approach for sampling. arXiv preprint arXiv:2111.151411 2021.
[42] Eberhard Hopf. The partial differential equation ut+ uux= μxx. Communications on Pure and Applied mathematics, 3(3):201-233) 1950.
[43] Julian D Cole. On linear parabolic equation occurring in aerodynamics. Quarterly of applied mathematics, 9(3):225 236, 1951.
[44] Jiongmin Yong and Xun Yu Zhou. Stochastic controls: Hamiltonian systems and HJB equations, volume 43. Springer Science & Business Media, 1999.
[45] Magdalena Kobylanski. Backward stochastic differential equations and partial differential equations with quadratic growth. Annals of probability, pages 558-602, 2000.
[46] Kiyosi Itô. On stochastic differential equations, volume 4. American Mathematical Soc., 1951.
[47] Richard Bellman. The theory of dynamic programming. Technical report, Rand corp santa monica ca, 1954.
[48] Emanuel Todorov. Efficient computation of optimal actions. Proceedings of the national academy of sciences, 106(28): 114881118388 2009,
[49] Michael Lutter, Shie Mannor, Jan Peters, Dieter Fox, and Animesh Garg. Value iteration in continuous actions, states and time. arXiv preprint arXiv: 105. 00.604 2021.
[50] Lingheng Meng, Rob Gorbet, and Dana Kulić. The effect of multi-step methods on overes- timation in deep reinforcement learning. In 2020 25th International Conference Pattern Recognition (ICPR), pages 347-353, IEEE, 2021.
[51] Harm van Seijen. Effecttive multi-step temporal-diftie differencce learning for non-lincar function approximation. arXiv preprint 1oXiv:6608.0551. 2016.
[52] Matteo Hessel, Joseph Modayil, Hado Van Hasselt, Tom Schaul, Georg Ostrovski. Will Dab- ney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. In Thirty-second AAAI conference on artificial intelligence, 2018
[53] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 1..::6022. 2013.
[54] Timothy P Lillicrap. Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint (mXiv:1509.02971 2015.
[55] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. International conference on machine learning, pages 1889-1897, 2015.
[56] Uly Loshchilov and Frank Hutter. Decoupled weight decay regularization, arXiv preprint 1,1.0500 2017.
[57] Charles G Lord, Lee Ross, and Mark R Lepper. Biased assimilation and attitude polarization: The effects of prior theories on subsequently considered evidence. Journal of personality and social psychology, 37(11):2099 1979.
13

---

[58] Pranav Dandekar, Ashish Goel, and David T Lee. Biased assimilation, homophily, and the dynamics of polarization. Proceedings of the National Academy of Sciences, 110(15):5791- 5796, 2013.
[59] Etienne Pardoux and Shige Peng. Backward stochastic differential equations and quasilinear parabolic partial differential equations. In Stochastic partial differential equations and their applications, pages 200-217. Springer, 1992.
[60] Balint Negyesi, Kristoffer Andersson, and Comellss W Oosterlee. The one step malliavin scheme: new discretization of bsdes implemented with deep learning regressions. arXiv preprint arXiv:2110.05421, 2021.
[61] Qianxiao Li and Shuji Hao. An optimal control approach to deep learning and applications to discrete-weije neural networks. In International Conference on Machine Learning, pages 2985 2994. PMLR, 2018.
[62] Guan-Horg Liu, Tianrong Chen, and Evangelos Theodorou. Ddpnopt: Differential dynamic programming neural optimizer. In International Conference Learning Representations, 2021.
[63] Guan-Horng Liu, Tianrong Chen, and Evangelos A Theodorou. Second-order neural ode optimizer. In Advances in Neural Information Processing Systems, 2021.
[64] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:201 13446, 2020.
[65] Edward Nelson. Dynamical theories of Brownian motion, volume 106. Princeton university press, 2020.
[66] Brian DO Anderson. Reverse-time diffusion equation models. Stochastic Processes and their Applications, 12(3):313-326, 1982.
[67] Grigorios A Pavliotis. Stochastic processes and applications: diffusion processes, the Fokker- Planck and Langevin equations, volume 60. Springer, 2014.
[68] Yang Song, Conor Durkan, lain Murray, and Stefano Ermon. Maximum likelihood training of score-based diffusion models. arXiv e-prints, pages arXiv-2101, 2021.
[69] Chin-Wer Wei Huang, Jae Hyun Lim, and Aaron Courville. variational perspective on diffusion- based generative models and score matching. arXiv preprint arXiv:2106.02800 2021.
[70] Stefan Elfwing. Eiji Uchibe, and Kenji Doya. Segmoid-weighted linear units for neural network function approximation reinforcement learning. Neural Networks, 107:3-11, 2018.
[71] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary Ve Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Sec.5.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Sec.5.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix A.3.
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (cither in the supplemental material or as a URL)? [Yes] We provide the pseudocode in Alg. I and detail the hyperparameter in Table 6.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix A.5.1.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Table 3.
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Appendix A.5.1.
4. If you are using existing assets (e.g., code, data, models) or curating/releasin new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] See Appendix A.5.1.
(c) Did you include any assets either in the supplemental material or as URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're you're
using/curating? [N/A] Not applicable.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] Not applicable.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] Not applicable.
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A] Not applicable.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A] Not applicable.
15


Reviews:
[{"review_id": "xPs93ck2PKY", "reviewer": "Reviewer_ijsA", "summary": "This article proposes *Deep Schrödinger Bridge (DeepGSB)*, a numerical algorithm for solving large-scale (in state dimension) stochastic Mean Field Games (MFG) with hard distributional target constraint, continuous state space and flexible mean-field (MF) interaction function.  The authors adapted the use of Hopf-Cole transformation and Schrödinger factors, similar to in [1], to transform MFG PDEs (with hard target) to a system of Schrödinger Bridge (SB) PDEs that depend on an MF interaction term $F$.  In order to solve this system, the authors extended the Forward-Backward Stochastic Differential Equation (FBSDE) representation for (SB) from [2] to account for $F$.  DeepGSB solves this FBSDE by fitting neural network approximators in an alternating manner, similar to in [2] and past works, with an added TD-like loss function to account for $F$. Experiments are performed for a crowd-navigation use case, similar to in [3, 4], and an opinion depolarization use case (based on the party model [5]).\n\n[1] Wasserstein Proximal Algorithms for the Schrödinger Bridge Problem: Density Control with Nonlinear Drift. K.F. Caluya, A. Halder.\n\n[2] Likelihood Training of Schrödinger Bridge using Forward-Backward SDEs Theory. T. Chen, G. Liu, E. Theodorou.\n\n[3] A machine learning framework for solving high-dimensional mean field game and mean field control problems. Ruthotto, et. al.\n\n[4] Alternating the Population and Control Neural Networks to Solve High-Dimensional Stochastic Mean-Field Games. Lin, et. al.\n\n[5] Polarization in geometric opinion dynamics. Gaitonde, et. al.", "questions": "Every item under \"Weaknesses\" contains a question and/or suggestion that can be answered/addressed.", "limitations": "Adequately addressed", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- A neural-based numerical solver for MFGs with exact terminal distribution and flexible mean field interaction can be highly useful and desirable in practice. In the crowd motion use case, the method is shown to respect the obstacles (e.g., flexible MF interaction) without losing convergence to the target, implying that in a real-world scenario, the agents are moving safely until they finally reach their intended destination.  Present methods are only able to solve for a smaller class of MFGs.\n- In addition to exactness and flexibility, the method is empirically shown to be scalable by solving a high-dimensional ($d=1000$) instance. Having surveyed related works, as far as I can tell, this seems to be the largest documented to date.\n- The algorithm is as simple as/simpler than APAC-Net [1] and [2], yet it solves a wider class of MFGs.  Setting the TD terms as regressand to allow account for $F$ is a principled way to handle a flexible of choice of $F$.  As the paper states, this can be generalized further to make use of other computational tools in reinforcement learning (RL).  As it stands, the design choices make use of best practices in RL, such as replay buffers and using multi-step TDs.\n- The use case of opinion depolarization by adopting the party model in an MFG seems to be novel and it seems very realistic to have a high-dimensional opinion space.  This could be a good test bed for future (and past) numerical MFG solvers.\n- To obtain an FBDSE system for an MFG, the authors extended and proceeded very similarly to an established result in [3] (Theorem 3 and its proof) originally intended for generative models.  This reuse unlocks a numerical solver for a wide class of MFGs.\n\nWeaknesses\n- The ML-based methods in [1] and [2] seem to be designed to solve high-dimensional MFGs.  This paper seems to indicate that they are not able solve for $d=1000$ but it's not clear why (too much computational resource needed?).  It might be informative to compare the computational complexity and/or running time of the methods (instead).\n- The direct comparisons against present methods are done visually (Figure 5 and 7, in the appendix). It can be more rigorous to compare the Wasserstein distance to target of the proposed method against that of the present methods.  I see that it can be hard to put all the methods on an equal footing, as the proposed method solves a wider class of MFGs.  It would be a fair comparison though if we restrict to a class of MFGs that are solvable by all the methods -- it seems that crowd motion is a use case that is also showcased in [1,2].  A dynamical optimal transport problem can also be a good test bed, as per Example 1 in [1].\n- There are some clarity issues -- while the paper is mostly well-written, it would be beneficial for non-expert readers to make some changes:\n1. (Line 64) I don't think it's correct to write that SB is an emerging machine learning *model*, it might be more accurate to introduce the topic by stating what the SB problem is.\n2. In equation 1, what is the domainof $G$? Shouldn't it be $\\mathbb{R}^d \\times \\mathcal{P}(\\mathbb{R}^d)$? If so, then the value function should be defined as: $u(x,T)=G(x,\\rho(\\cdot,T))$.\n3. (Line 49-52) As the authors discuss the drawbacks of present methods, it would be good to include citations for every drawback (which method has which drawback).\n4. Proposition 2 does not seem to be proven.   Please provide at least a proof-sketch -- it is not obvious to me how exactly the random terms in equations 14(a,b) are dealt with.\n5. There are grammatical mistakes, but they do not seem to impact my understanding.  It would be beneficial if the authors were to edit the article.\n6. It is not clear to me why DeepGSB is more robust to hyperparameters (Line 247).  Can you please clarify via a theoretical and/or empirical argument?\n\n[1] Alternating the Population and Control Neural Networks to Solve High-Dimensional Stochastic Mean-Field Games. Lin, et. al.\n\n[2] A machine learning framework for solving high-dimensional mean field game and mean field control problems. Ruthotto, et. al.\n\n[3] Likelihood Training of Schrödinger Bridge using Forward-Backward SDEs Theory. T. Chen, G. Liu, E. Theodorou.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "xNPEYkus7s5", "reviewer": "Reviewer_A4H3", "summary": "The authors of this work propose and explore extensively a unique and elegant generalization of SBPs to Mckean-Vlasov type of SDEs / MFGs. Whilst these types of systems have already been proposed and explored in the literature, the connection to SBPs and the reinterpretation as a generalization is novel and elegant. One of the contributions of this work is that leveraging some new interpretations the authors propose new ML aided numerical algorithms to solve these systems and provide extensive experimental evidence showing their success and some initial theoretical motivation. ", "questions": "Questions / Corrections (suggestions):\n\n1. The claim that IPF in all generality does not suffice based on a naive marginal based iteration of IPF specifically in termed “likelihood training objectives” proposed by [27] seem like a major overstatement and not a rigorous one either. At the very best the authors should state that the IPF flavor proposed in [27] is not suitable for the generalized SB since that is what they motivate. In the most general setting as a coordinate ascent algorithm IPF and Sinkhorn probably still have theoretical guarantees and could potentially admit practical iterations for this problem, the authors have not proved otherwise and should not state otherwise. It's not helpful for the reader to inflate claims in this manner, especially without proof (you do provide an argument but that proves something much more specific).  This is my main counterpoint. If the authors are happy to clarify and state this more humbly then I believe we have an excellent paper (there is no need for this really … ). \n2. Despite making criticisms towards a specific instance of IPF (which is only nicely satisfied / justified when Y,Y_hat are at equilibrium rather than approximately parameterized) the final form of the proposed algorithm is very IPF-esq, and whilst the differences are outlined as they are developed it feels they are not clearly emphasized enough. And as mentioned in the previous point its not necessarily proved that the alternating objective provided can not be re-written or re-interpreted as alternating path KLs with constraints. There is a gap here in the comparison or relationship between the schemes and the small paragraph claiming IPF is not applicable falls very short. \n3. Line 140 the notation is not particularly nice. I would advise subscripting Y and Y_hat with time indices as done in [27] and in the Appendix.\n4. App A.2 Eq 26, whilst their are prior results which have not being acknowledged (eg [2] Equation 16 and Theorem 5 or [3] Theorem 3) trading off scores with divs in the context of diffusions, it is not clear how the cross terms involving the score q vanish after applying Green’s identity, its clear how divergences arise on Z_theta, but terms involving  q and Z_theta/phi typically would require further identities/steps (i.e. using the FPK equation) to substitute div(f) , this is missing a lot of clarity and steps. Whilst I know this result to be true I find the sketch incomplete and very uninformative.  \n5. FBSDE Theory asserts conditions at which some particular system of Ito Processes satisfies certain HJB equations. Typically reaching said conditions numerically (see [1]) is achieved by minimizing some MSE styled error whose fixed point trivially matches the conditions in Theorem 1 , the authors fail to detail how they go from Theorem 1  to the objectives L(theta) and L(phi).\n6. Overall this paper is lacking an additional proposition which proves that a combined objective function L(\\phi, \\theta) is minimized when the conditions of theorem 1 are satisfied, whilst this is informally discussed and partially derived/motivated  it is not formally stated or argued anywhere. Then after this a further lemma or remark asserting how a coordinate ascent scheme would lead from this objective to a fixed point satisfying the conditions in Theorem 1 would substantially improve the presentation and results.  Going through the appendix it does seem that this can be achieved without too much additional new work but with substantial change in the write up. It is not the job of the reviewer/reader to infer (and basically have to prove) this from partial information and semi-connected statements.  \n7. To maybe emphasize further the previous point there are no convergence guarantees proved for algorithm 1 the way its sketched / presented comes across as mostly heuristic with some components derived but without any overall guarantee presented.\n\n\n\n[1] Nüsken, N. and Richter, L., 2021. Solving high-dimensional Hamilton–Jacobi–Bellman PDEs using neural networks: perspectives from the theory of controlled diffusions and measures on path space. Partial Differential Equations and Applications, 2(4), pp.1-48.\n\n[2] Huang, C.W., Lim, J.H. and Courville, A.C., 2021. A variational perspective on diffusion-based generative models and score matching. Advances in Neural Information Processing Systems, 34, pp.22863-22876.\n\n[3] Song, Y., Durkan, C., Murray, I. and Ermon, S., 2021. Maximum likelihood training of score-based diffusion models. Advances in Neural Information Processing Systems, 34, pp.1415-1428.\n\n[27] Chen, T., Liu, G.H. and Theodorou, E.A., 2021. Likelihood Training of Schr\\\" odinger Bridge using Forward-Backward SDEs Theory. arXiv preprint arXiv:2110.11291.\n", "limitations": "As detailed in the suggestions / questions the paper contains incomplete proofs, and disconnected statements. Overall the text is not well connected and the reviewer feels it is not well written for a machine learning auidence, even one specialising in the relevant subfields covered in this work. Thus due to the lack of clarity and verifiability I cannot recommend this work for publication in its current form, it feels that the author expects readers to complete and guess many intermediate and missing steps in proofs to the point where in some cases the overall desired statements you would expect for a new numerical scheme are not actually proved or even stated.  Overall the way in which the theory is presented does not prove/outline overall convergence guarantees for the final numerical scheme, the paper requires significant re-writing and its overall presentation in order to be clear/accesible. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall there are issues issues in the way the paper is written and how some previous ideas / methods are underplayed (and arguably innacurately portrayed). I believe this was not the author's intention as they merely seeked to showcase / emphasize their contribution however I do believe it has a negative rather than a positive effect when reading the paper with the potential of confusing the reader. Furthermore there is a gap connecting the practical optimisation scheme used to the central theoretical results in the paper (main), whilst the connection may be in the appendix or possible to infer it is not clearly outlined. \n\nPros: \n1. Sufficient and Extensive successful experimental criteria\n2. Clear and accessible lit review of SBPs and MFGs\n3. Cleanly presented and readable results/theorems \n\nCons:\n1. There is a gap between Theorem 1 and the training algorithm which makes it difficult for a reader to motivate the origin of the algorithm\n2. Lack of clarity when connecting (or arguing significant differences) to IPF\n3. Overall arguments in the paper are not well connected making it difficult for a reader to assert the validity of the final approach in particular bridging the theory and the practice.\n4. As a result there seems to be no convergence proofs or guarantees for algorithm 1 , its somewhat heuristically motivated by IPF and Theorem 1 but there is no overarching argument establishing / justifying its convergence. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "hWkBAkB7eew", "reviewer": "Reviewer_ckTW", "summary": "This paper proposed the DeepGSB, a framework for solving (a variant of) mean-field games including non-differentiable interaction terms. The key idea is to replace the usual terminal condition on the control by a hard constraint on the target distribution, and then invoke the Schrodinger Bridge (SB) framework.The authors provide promising empirical evidence for the proposed method.", "questions": "My two major questions are:\n\n1. Is there any chance to relax the hard constraint on the target density? For me, this seems quite hard as the SB is mostly expressed in the two fixed end-points formulas.\n\n2. Is there any practical motivation for considering the hard distributional constraint formulations of MFGs? ", "limitations": "As mentioned in my review, although this paper aims at solving MFGs, its proposed variant does not seem particularly interesting to me (although the technique is elegant). I'm willing to raise my score if the authors can convince me of the value of their setting.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n- This paper is well-written, with ideas clearly presented.\n- The proposed model is novel and interesting.\n- The connection to TD-like objectives is intuitive and may potentially be useful in practice.\n\n\nWeakness:\n- The motivation for replacing the terminal control constraint with the hard distributional constraint is not very convincing to me. Under what circumstance does such a scenario arise? To me, it seems like for most applications, the target distribution is almost never available. In the experimental section, the authors simply assume that the target density is some simple distributions (such as Gaussians), for which I fail to grasp the reason why this is reasonable.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "fdCEu3U3JMQ", "reviewer": "Reviewer_TjfA", "summary": "The authors apply diffusion Schrodinger Bridges (DSB) to mean field game applications, this generalizes existing DSB approaches to include mean field interactions. The authors utilise a novel loss term based on temporal difference objectives within each IPF-like iteration.\n\nThe experiments are validated on 2D crowd navigation and opinion depolarisation experiments.", "questions": "- Is the code available?\n- Is there a reason to use the FB-SDE SB approach over the simpler original DSB approach given they have the same objective?\n- How many IPF iterations were used? And how many training steps, K, per IPF iteration?\n- What is the run time/ training time?\n- How is $\\hat{TD}_0$ computed if it requires the log of the target density?, line 182\n", "limitations": "The authors have not discussed limitations. Given the iterative nature of the procedure, similar to other SB approaches, it appears difficult to scale. Experiments are relatively toy-ish.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- This is an interesting paper and connects DSB beyond generative modelling to interesting mean field game tasks.\n- The contributions are simple but effective, adding a mean field term to SB and deriving a new loss based on temporal difference\n\nWeaknesses\n- Line 159 is not very clear, the objective of FB-SDE is only a log-likelihood at convergence and appears to only be justified by its equivalence to IPF \n- Is the statement that IPF methods will not work with MF interaction true for the the regression objective of [1]?, between line 164 and 165\n- Experiments appear relatively simple, does the method scale to more complex examples?\n- It does not appear that the code is available, however the authors have stated that the code is available in the checklist. Have I missed the link?\n- Some experimental details such as number of IPF iterations, diffusion steps, training details are missing.\n- Not clear how to tune training procedure in FBSDE approach. \n    - If number of training steps per IPF iteration, denoted K in Algo 1, is very small then this will just map noise to noise per IPF iteration hence not solve SB and surely cannot work?\n    - If like in the original FBSDE SB paper [2] the forward/ backward networks are trained for a large number of training iterations in the first IPF step then fine-tuned by a small number of steps in later IPF steps, do they get stuck in local minima? is fine tuning doing much or is this essentially the same as score based generative modelling? If fine tuning and not following IPF by training each network to completion at each IPF step, is this actually approximating Optimal Transport? There appears to be no empirical evidence this is close to OT\n   \nMinor\n- Line 4 typo, \"preferences needs not available\" does not make sense\n- Capital \"L\" needed for Laplacian operator, line 37\n- Typo line 73, \"need not be continuous\" is fine\n- Line 203, \"testify\" seems to be the wrong word here\n\n[1] Diffusion Schrödinger Bridge with Applications to Score-Based Generative Modeling, Bortoli 2021\n[2] LIKELIHOOD TRAINING OF SCHRÖDINGER BRIDGE USING FORWARD-BACKWARD SDES THEORY, 2022", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept