{'fraction_non_alphanumeric': 0.04106825883492012, 'fraction_numerical': 0.012304340810069389, 'mean_word_length': 4.8423285411265615, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 2, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Approximating Discontinuous Nash Equilibrial Values of Two-Player General-Sum Differential Games

Finding Nash equilibrial policies for two-player differential games requires solving Hamilton-Jacobi-Isaacs (HJI) PDEs. Self-supervised learning has been used to approximate solutions of such PDEs while circumventing the well-known curse of dimensionality. However, this method fails to learn discontinuous PDE solutions due to its sampling nature, leading to poor safety performance of the resulting controllers in robotics applications when player rewards are discontinuous. This paper investigates two potential solutions to this problem: a hybrid method that leverages both supervised Nash equilibria and the HJI PDE, and a value-hardening method where a sequence of HJIs are solved with a gradually hardening reward. We compare these solutions using the resulting generalization and safety performance in two vehicle interaction case studies with 5D and 9D state spaces, respectively. Result shows that with informative supervision (e.g., collision and near-collision demonstrations) and the low cost of self-supervised learning, the hybrid method achieves better safety performance than the supervised, self-supervised, and value hardening approaches on equal computational budget. Value hardening fails to generalize in the higher-dimensional case without informative supervision. Lastly, we show that the neural activation function needs to be continuously differentiable for learning PDEs and its choice can be case dependent.


I. INTRODUCTION
Problem statement. Human-robot interactions (HRIs) in real time can be modeled as general-sum differential games. The Nash equilibrial value of the game is a viscosity solution to the Hamilton-Jacobi-Isaacs (HJI) equations [1], and is a function of the players' states and time. Conventional algorithms for solving Hamilton-Jacobi PDEs are known to suffer from the curse of dimensionality [2], i.e., values become hard to compute for high-dimensional state spaces. Recent attempts consider self-supervised (and physics-informed) learning that forces the consistency between the value and the PDE, and have achieved empirical success on a variety of differential games [3], [4]. While convergence of this method has been proven for Lipschitz and Hölder continuous player rewards [4], [5], our experiments suggest that convergence to the true values cannot be achieved when players' rewards, and thus the values, are discontinuous with respect to states and time. Such discontinuity can occur when players receive both continuous and logic rewards, e.g., energy consumption and safety penalties, respectively.
Solutions. We examine a set of potential solutions to this challenge: (1) A supervised method where value is learned based on sample equilibrial trajectories derived from Pontryagin's Maximum Principle (PMP) [6], (2) a hybrid method where both supervised data and the HJI equations are used, and (3) a modified self-supervised method where we gradually harden an initially softened reward. Comparisons are performed on two vehicle interaction studies: An uncontrolled intersection case with a 5D value function with and without complete information about player types, and a collision avoidance case with a 9D value function.
Contributions. Our study leads to the following new findings: • We show that the hybrid method achieves better generalization performance on value prediction and safer control policies than other methods under the same computational budget. On the other hand, value-hardening fails to generalize in the higher-dimensional case, indicating the importance of informative supervision. To the authors' best knowledge, this is the first paper that addresses the challenge in approximating discontinuous values for HJI PDEs with terminal boundary conditions. • We show that the choice of neural activation in the value network is important: Relu does not generalize well due to its discontinuous derivative. Performance of sin activation varies across case studies, indicating the need for hyperparameter tuning. Meanwhile tanh and continuously differentiable variants of relu, e.g., gelu, generalize well using the hybrid method. These new findings add counter examples to the existing literature that promotes the use of sin activation for value approximation [3], and support recent discussions on the need for adaptive activations for deep networkbased PDE solvers [7].
II. RELATED WORK Solving Hamilton-Jacobi PDEs via deep learning. With the development of auto-differentiation [8], deep neural networks have become means to solving PDEs when analytical methods suffer from the curse of dimensionality [9]. Existing methods of this kind can be grouped into three types: "Boundary matching" methods first reformulate PDEs as backward stochastic differential equations and solve them by forcing a match between the terminal states of the resultant stochastic processes and the boundary conditions [10], [11]. "Equation matching" methods, which are often called physics-informed neural nets (PINN), directly force a match between a surrogate function and the PDE [3], [12]. Both arXiv:2207.01773v2 [cs.
LG] 23 Sep 2022 boundary and equation matching are self-supervised, and have proven convergence to the ground truth solutions when both the network and the governing equations are continuous [4], [11], [12]. Lastly, supervised learning methods train a network based on sampled solutions to the PDE. To the authors' best knowledge, there is currently few generalization analysis for this method. Recent studies have investigated the effectiveness of "equation matching" at solving PDEs with discontinuous solutions (e.g., Burgers equation [7]) where both initial and terminal boundaries are specified. We show in this paper that PDEs with only terminal (or initial) boundary conditions, such as HJIs, cause unidentifiability challenge.
Games with incomplete information. Incompleteinformation games are often studied as imperfect-information ones by considering unknown player types as drawn randomly by the Nature [13], [14]. Studies on imperfectinformation dynamic games have proved the convergence of the counterfactual regret minimization (CFR) algorithm [15] and successfully applied the algorithm to heads-up Texas hold'em poker [16], [17]. However, CFR, and other algorithms for Markov games such as fictitious self-play, do not scale well along time, and thus have limited applications to continuous-time interactions. Alternatively, policies for HRI are often approximated via simplifications of the underlying games that balance theoretical soundness and practical utility. Most attempts of this type simplify games as optimal control problems or complete-information games (e.g., [18]- [21]), and some use belief update to adapt the planned motion (e.g., [22]- [27]). For real-time control, [28] proposed to solve linear-quadratic games iteratively to approximate the equilibrial policy of a complete-information differential game. Unlike existing studies, in this paper we achieve real-time belief update and feedback control in incomplete-information games by learning off-line the Nash equilibrial value functions of hypothetical games to be played by all possible combinations of player types. The values then enable online Bayesian belief update to correct players' false beliefs about each other's type.
III. METHODS Notations. Let X i (resp. U i ) be the state (resp. action) spaces for Player i. The time-independent state dynamics of Dependence of time will be omitted when possible. For a fixed-time interaction within [0, T ], the instantaneous and terminal losses of Player i are denoted by l((x i , x −i ), u i ) and c((x i , x −i ), u i ), respectively. For a complete-information differential game between two players, the value function of Player i is ν i (·, ·, ·) : X i × X −i × [0, T ] → R where the arguments are in the order of the ego's (Player i's) states, the other player's states, and the current time. To reduce notational burden, we will use f i , l i , c i , and ν i respectively for the player-wise dynamics, losses, and the value, and use a i = (a i , a −i ) to concatenate variables from the ego (i) and the other players. We use ∇ x (·) to denote partial derivative with respective to x.
Preliminaries. Hamilton-Jacobi-Isaacs equations: The Nash equilibrial values of a two-player differential game solve the following HJI equations (L) and satisfy the boundary conditions (D) [29]: (1) Here players' policies are derived by maximizing the equi- Pontryagin's Maximum Principle: While solving the HJI would provide a feedback control policy, it is often more tractable to compute open-loop policies for specific initial state (x 1 ,x 2 ) ∈ X 1 × X 2 by solving the following boundary value problem (BVP) according to PMP 1 : Here λ i is the time-dependent co-state for Player i. The costate connects PMP and HJI through λ i = ∇ xi ν i . Solutions to Eq. (2) are specific to the given initial states.
Self-supervised learning for differential games. This approach directly trains a neural network to comply with the governing equations. Letν i (·, ·, ·) : We extend the existing formulation for solving zerosum games [3] to the general-sum setting: −i , t (k) and C 1 balances the inconsistencies of the value network to the HJI (L) and to the boundary conditions (D). It is worth noting that in each iteration of solving Eq. (3), a sub-routine is needed to find the control policies that maximize the Hamiltonian. [12] proved the convergence ofν i to ν i via solving Eq. (3) when φ(·) is a H 3/2 -norm; [4] provided convergence and generalization analyses of the learning in forms of Eq. (3) for linear second-order elliptic and parabolic type PDEs (which include HJI) with continuity assumptions on L, D, andν i .
Challenge in approximating discontinuous HJI values. We use a toy case to explain the challenge in approximating discontinuous solutions of a differential equation with only terminal boundary conditions using self-supervised learning: Consider a 1D function ν(·) as a solution to ∇ x ν −δ(x) = 0 with the boundary condition ν(1) = 0 within x ∈ [−1, 1], where δ(x) is a delta function that peaks at x = 0 (see Fig. 1). With uniform samples, the self-supervised loss (L 1 ) can be minimized almost surely using a horizontal line ν(x) = 0. This is because, due to the differential nature of the governing equation, the accuracy of a self-supervised model at one point in space and time solely relies on that of its neighboring samples, yet informative neighbors (here at x = 0) have low (or zero) probability to be sampled. Also notice that when both initial and terminal boundaries are specified (here ν(−1) = −1 and ν(1) = 0), self-supervised learning can potentially work, like in the case of a Burgers equation.
Solutions. This leads to two potential solutions.
(1) Hybrid method: Supervised data reveals the structure of the solution. In the toy case, an approximation to the solution can be learned based on two informative data points sampled from each side of 0 (see the SL curve). When solving HJIs, the drawbacks of supervised learning are (1) its high data acquisition cost due to the need of solving BVPs and (2) its lack of generalization proof for solving PDEs. We hypothesize that these drawbacks can be addressed by combining supervised and self-supervised learning, since the latter only requires evaluating the HJI equations and is generalizable under continuity assumptions. This leads to the following hybrid method: be a dataset derived from solving Eq. (2) with initial states sampled in X 1 × X 2 . The supervised loss is defined as: where C 2 is a hyperparameter that balances the losses on value and its gradient. The hybrid method minimizes L 1 +L 2 .
(2) Value hardening: The second solution is to first introduce a surrogate differential equation, the continuous solution of which approximates the ground truth. Then we approximate the true solution by gradually "hardening" this surrogate. In the toy case, convergence of the solution can be achieved by gradually hardening a softened delta function (Fig. 1). Nonetheless, a potential issue with this approach is that as we harden the delta function, the set of informative samples (that specifies non-zero ∇ x ν in the toy case) reduces. Importance sampling becomes necessary to avoid convergence towardsν = 0. In practice, however, the importance of samples is unknown a priori.

IV. CASE STUDIES
We report and compare generalization performance from self-supervised, supervised, hybrid, and value-hardening methods on two vehicle interaction studies. The first case considers an interaction between two players at an uncontrolled intersection, which leads to HJIs with coupled value functions defined on a 5D state space. With proper coordinate transformation [31], this case study represents a broad range of challenging two-vehicle interactions including roundabouts and unprotected left turns. For completeness, we study both a complete-information setting where players know each other's type, and an incomplete-information setting where player types are private and inferred during the interaction. We then consider a higher-dimensional collisionavoidance case to examine the scalability of the proposed methods. We note that this case is similar to that of [3], which is the highest dimensionality for two-vehicle interactions as far as the authors are aware of. The difference from [3] is that we encounter value discontinuity when players are required to both minimize effort and avoid collision.

A. Case 1: Uncontrolled intersection
Experiment setup. The schematics of the interaction is shown in Fig. 2, where Player i's states are composed of two scalars representing its location (d i ) and speed (v i ): , 10]m/s 2 is a scalar control input that represents the acceleration. The instantaneous loss considers the control effort and a collision penalty: where σ(d, θ) = 1 iff d ∈ [R/2 − θW/2, (R + W )/2 + L] or otherwise σ(d, θ) = 0; b = 10 4 sets a high loss for collision; R, L, and W are the road length, car length, and car width, respectively (see Fig. 2). Θ = {1, 5} represents the aggressive (a) and non-aggressive (na) types of players, respectively. Note that the collision penalty is the source of discontinuity (or numerically, large Lipschitz constant, which contributes to the rapid value change in Fig. 2). The terminal loss is defined to incentivize players to move across the intersection and restore nominal speed: where α = 10 −6 ,v = 18m/s, and T = 3s. Data. For a fair comparison, data sizes for each learning method are chosen so that the total wall-clock computational costs for data acquisition and learning combined are similar across different methods. Note that we do not use computational complexity to measure the computational budget due to the different nature of computations involved in acquiring supervised data (which requires iterative BVP solving) and self-supervised data (which only requires random sampling). Specifically, all training sessions are around 300 minutes on one GeForce GTX 1080 Ti GPU with 11 GB memory 2 . Detailed data acquisition methods and data sizes are as follows: For supervised learning, we generate 1.7k ground truth trajectories from initial states uniformly sampled in X GT := [15,20]m × [18,25]m/s and by solving Eq. (2). Each trajectory contains 31 × 2 data-points (sampled with a time interval of 0.1s and for two players), which leads to a total of 105.4k data points. For self-supervised learning and its value-hardening variant, we sample 122k states uniformly in X HJ := [15,105]m × [15, 32]m/s. For hybrid learning, we sample 1k ground truth trajectories (62k data points) uniformly in X GT and sample 60k states uniformly in X HJ . We repeat the same sampling procedure for all four player type configurations (a, a), (na, a), (a, na), and (na, na).
The choices of the state spaces to sample from are based on the following rationale: The ground truth trajectories are derived by sampling initial states from identical domains of the two players. This is because collision and nearcollision cases, which are informative for the learning, often happen when players start with similar distances and speeds. Similarly, the distance range for supervised data ( [15,20]m) is calibrated so as to increase the chance of sampling informative trajectories within the specified time window. The speed range ( [18,25]m/s) is set based on nominal vehicle speed limits. For self-supervised learning, we use a space (X HJ ) that approximately covers all states players can reach in [0, T ]. Adaptive sampling is yet to be studied.
Network Architecture. Due to space limit, we only report results using fully-connected networks with 3 hidden layers, each containing 64 neurons, and with tanh, relu, or sin activations. Deeper or wider networks do not change our conclusions. gelu achieves similar performance as tanh. We normalize input data to [−1, 1] to improve training convergence. Case 2 uses the same architecture.
Training. All training problems are solved using the Adam optimizer with a fixed learning rate of 2 × 10 −5 . For supervised learning, we train networks for a fixed 100k iterations. For self-supervised learning, we follow the curriculum learning method in [3] by first training the networks for 10k iterations using 1k uniformly sampled boundary states (at terminal time). The networks are then refined for 260k gradient descent steps, with states sampled from an expanding time window starting from the terminal. The value-hardening variant follows the same learning procedure but softens the collision penalty using sigmoid functions and gradually increases the shape parameter of the sigmoid to harden the penalty. For fair comparison, we use 5.4k training iterations for each hardening step for a total of 50 steps. For the hybrid method, we pre-train the networks for 100k iterations using the supervised data, and combine the supervised data with states sampled from an expanding time window starting from the terminal time to minimize L 1 + L 2 for 100k iterations.
Results for complete-information games. We generate a separate set of 600 ground truth trajectories with initial states in X GT for each of the four player type configurations. For generalization performance, we measure the MAEs of value and control input predictions (denoted by |ν −ν| and |u −û| respectively) across the test trajectories. For safety performance, we use the learned value networks as closed-loop controllers to generate complete-information interactions, and report the percentage of avoidable collisions. Initial states follow the test data. Control inputs are computed by first auto-diffing the values and then maximizing the resultant Hamiltonian. Performance results are summarized in Table I and sample trajectories for the (a, a) case shown in Fig. 3. Performance of (a, na) and (na, a) are averaged due to the symmetry of players in these settings.
To examine the out-of-distribution performance of the   Ablation studies. We perform ablation studies to under-stand the influences of activation functions and the norm of boundary loss on model performance. Safety results are summarized in Table II for player types (a, a) and using the hybrid learning method, with training and test in X GT . Corresponding trajectories are visualized in Fig. 4. Results show that (1) the choice of the activation function has a significant influence on the resultant models, with tanh outperforming relu and sin, and that (2) the choice of the boundary norm does not have significant influence. Remarks: (1) relu networks have proven convergence to piecewise smooth functions in a supervised setting [32]. However, convergence in the self-supervised setting requires continuity of the network and its gradient [4], which relu does not offer. This result is consistent with [7] where relu underperforms in solving PDEs. We conjecture that this contributes to the deteriorated performance of relu under the hybrid setting. We note, however, that smooth variants of relu such as gelu can achieve performance comparable to that of tanh.
(2) sin does not perform well for Case 1, yet achieves comparable performance to tanh in Case 2. This result suggests that fine-tuning of the frequency parameter of sin is necessary and case-dependent.
Results for incomplete-information games. We examine the advantage of the hybrid method when adopting value networks as closed-loop controllers for interactions in an incomplete-information setting. To constrain the scope of tests, we explore two settings of initial beliefs: Everyone believes that everyone is (1) most likely non-aggressive (p i := Pr(θ i = a) = 0.2), or (2) most likely aggressive (p i = 0.8 for i = 1, 2). The common belief assumption indicates that Player i knows about Player j's belief about i. Also note that players' initial beliefs can mismatch with their true types. We model players to continuously perform Bayes updates on their beliefs based on observations, and determine the next control inputs based on the value networks that correspond to the most likely player types according to their current beliefs (see [27] for details on belief update and control). This model allows us to simulate state and belief dynamics in turn, although the values are approximated based on complete-information games and are thus decoupled from the belief dynamics. Table III compares safety performance of incomplete-information interactions using the same initial states as previous tests and values learned by the hybrid and the supervised methods. The former outperforms the latter across all belief settings.  Fig. 7, where Player i's states are composed of its location (p x i , p y i ), orientation (ψ i ) and speed (v i ): consider a unicycle model as the dynamics: where ω i ∈ [−1, 1]rad/s and u i ∈ [−5, 10]m/s 2 are control inputs that represent angular velocity and acceleration, respectively. The instantaneous loss considers the control effort and the collision penalty: where the penalty is . b = 10 4 sets a high loss for collision; γ = 5 is a shape parameter; R is road length; k = 100 balances the control effort on turning and acceleration; η = 1.5m is a threshold for collision. The terminal loss encourages players to move along the lane and restore nominal speed: where α = 10 −6 ,v = 18m/s,p y = 3m, and T = 3s. Data. For supervised learning, we generate 1.45k ground truth trajectories from initial states uniformly sampled in X GT := [15,20] Training. Self-supervised learning adopts pretraining of networks for 10k iterations using 1k uniformly sampled boundary states and trains the network for 350k iterations. The value-hardening variant uses 7.2k training iterations for each hardening step with a total of 50 steps for fair comparison. The rest of the settings follows Case 1.
Results. We use a separate test set of 600 ground truth collision-free trajectories with initial states drawn from X GT . Performance results are summarized in Table IV. Distance between players during the interactions are visualized in Fig. 5. Similar to Case 1, hybrid learning outperforms other methods. Value-hardening fails to generalize in this higherdimensional case. Comparing with Case 1, we conjecture that the failure is caused by a decreasing probability of capturing informative samples (where rapid value changes happen) as the state dimension increases. Fig. 6 illustrates one initial state where the hybrid method induces a safe interaction while other baselines have collisions.

V. CONCLUSIONS
We proposed a hybrid learning method that combines the advantages of supervised and self-supervised learning for approximating discontinuous value functions as solutions to two-player general-sum differential games. Using two vehicles interaction cases, we showed that the proposed method leads to better generalization and safety performance than purely supervised and self-supervised learning when using the same computational cost. In essence, our algorithm allows the value network to first adapt to the structure of the value function through supervised data, and then uses the underlying governing equations to satisfy the PDE in the entire state space. We also tested the idea of value hardening, and showed that without informative supervised data, this method does not guarantee convergence to the true values when discontinuity exists. Lastly, we empirically showed the importance of continuous differentiability of activation functions in solving PDEs with deep learning. Future study will investigate the relationship between the types of PDEs and the effective choices of activations that solve these PDEs.