Armand Jordana

Bilal Hammoud

Member, IEEE Justin Carpentier
email: justin.carpentier@inria.fr

Senior Member, IEEE Ludovic Righetti

Member, IEEE, Bilal Hammoud Student Member, IEEE Armand Jordana Student

Stagewise Newton Method for Dynamic Game Control with Imperfect State Observation

Keywords:

I. INTRODUCTION

D OING output-feedback Model Predictive Control (MPC) while being robust to the estimator uncertainty is a notoriously difficult problem [START_REF] Mayne | Model predictive control: Recent developments and future promise[END_REF]. In optimal control, when the state measurement is partial and corrupted by noise, a common practice is to treat the estimation problem independently from the control and rely on the most likely outcome. However, in some scenarios, one might want to design a controller robust to the worst case estimation error. Such controllers can be obtained through dynamic game control [START_REF] James | Risk-sensitive control and dynamic games for partially observed discrete-time nonlinear systems[END_REF], [START_REF] Bas | H ∞ -0ptimal control and related minimax design problems: A dynamic game approach[END_REF]. As Mayne [START_REF] Mayne | Model predictive control: Recent developments and future promise[END_REF] advocates, one meaningful way to properly take into account the measurement uncertainty is to use a minimax formulation linking control and estimation. This problem has been extensively studied in [START_REF] Copp | Nonlinear output-feedback model predictive control with moving horizon estimation[END_REF], [START_REF]Simultaneous nonlinear model predictive control and state estimation[END_REF], which shows that a specific dynamic game formulation leads to MPC approaches with bounded state trajectories and provides an explicit characterization of these bounds. However, the minimax problem was solved with an interior point method without taking into account the specific structure of the problem and the sparsity induced by time. In this work, we derive an explicit iterative solution that fully exploits sparsity, resulting in an algorithm that linearly scales with the time horizon length and which can be easily warm-started for use in MPC schemes [START_REF] Mastalli | Crocoddyl: An Efficient and Versatile Framework for Multi-Contact Optimal Control[END_REF].

In the linear dynamics and quadratic cost case, Jacobson [START_REF] Jacobson | Optimal stochastic linear systems with exponential performance criteria and their relation to deterministic differential games[END_REF] showed that dynamic game control is equivalent to risk sensitive control and derived a closed form solution. Later, Whittle [START_REF] Whittle | Risk-sensitive linear/quadratic/gaussian control[END_REF] extended the results to the linear quadratic case with imperfect state observations. In [START_REF] Hammoud | irisc: Iterative risk sensitive control for nonlinear systems with imperfect observations[END_REF], a first iterative version of Whittle's solution was introduced to tackle the nonlinear risk sensitive problem with imperfect observations. However, the stochastic nature of the problem hindered the development of theoretical guarantees. Although, dynamic game and risk sensitive control are equivalent in the linear quadratic case [START_REF] Jacobson | Optimal stochastic linear systems with exponential performance criteria and their relation to deterministic differential games[END_REF], this is no longer the case in the nonlinear setting [START_REF] Campi | Nonlinear discrete-time risk-sensitive optimal control[END_REF]. Nonetheless, dynamic game control is tightly connected to robust and risk sensitive control. In [START_REF] James | Risk-sensitive control and dynamic games for partially observed discrete-time nonlinear systems[END_REF], [START_REF] Campi | Nonlinear discrete-time risk-sensitive optimal control[END_REF], James and Campi showed that dynamic game control can be interpreted as the limit case of risk sensitive control when noise tends to zero. Recently, Bas ¸ar [START_REF] Bas ¸ar | Robust designs through risk sensitivity: An overview[END_REF] presented a detailed overview of the connections between both problems in continuous time. Additionally, Bas ¸ar and Bernhard [START_REF] Bas | H ∞ -0ptimal control and related minimax design problems: A dynamic game approach[END_REF], [START_REF] Bernhard | Minimax versus stochastic partial information control[END_REF] established the connections between dynamic game control and H ∞ -Optimal Control both in the perfect and imperfect state information case.

For nonlinear systems, estimating a state trajectory corresponding to some given measurements is usually intractable analytically. A common approach is to model the noise as Gaussian and to maximize the Maximum A Posteriori (MAP) [START_REF] Cox | On the estimation of state variables and parameters for noisy dynamic systems[END_REF]. If the dynamics are affine, then the problem can be solved analytically with the so-called Rauch-Tung-Striebel (RTS) smoother [START_REF] Rauch | Maximum likelihood estimates of linear dynamic systems[END_REF]. The RTS smoother is made of a forward recursion which resembles the Kalman Filter (KF) and a backward recursion. In the nonlinear case, iterative schemes are usually used. A popular choice is the iterative Kalman smoother which is equivalent to a Gauss-Newton method on the MAP [START_REF] Bell | The iterated kalman smoother as a gauss-newton method[END_REF]. The estimation part of our proposed solution resembles a risk sensitive version of this smoother.

In optimal control or dynamic game control with perfect state information, various numerical optimization algorithms have been developed to iteratively find solutions in the nonlinear case. In optimal control, the most analogous to our work are Differential Dynamic Programming (DDP) [START_REF] Murray | Differential dynamic programming and newton's method for discrete optimal control problems[END_REF] and the stagewise implementation of the Newton's method [START_REF] Dunn | Efficient dynamic programming implementations of newton's method for unconstrained optimal control problems[END_REF]. The stagewise Newton method is an exact implementation of Newton's method that exploits the specific structure of the Hessian matrix in order to scale linearly with the time horizon. DDP is an iterative algorithm that takes an update step on the control input by applying dynamic programming on a quadratic approximation of the value function. In [START_REF] Murray | Differential dynamic programming and newton's method for discrete optimal control problems[END_REF], Murray showed that DDP is very similar to a Newton step and inherits its convergence properties. For dynamic game control with perfect state information, the seminal work from [START_REF] Mukai | Game-theoretic linear quadratic method for air mission control[END_REF], [START_REF] Morimoto | Minimax differential dynamic programming: application to a biped walking robot[END_REF] introduced minimax DDP showing that DDP could be extended to zero-sum two players games. Recently, [START_REF] Di | Newton's method, bellman recursion and differential dynamic programming for unconstrained nonlinear dynamic games[END_REF] further extended the concepts of stagewise Newton method and DDP to nonzero-sum games with an arbitrary number of players in the full information case.

Despite having been widely studied theoretically, to the best of our knowledge, dynamic game control with imperfect state observations has not been approached from a numerical optimization point of view. In this work, we consider the general problem of dynamic game control with imperfect state observation and present a numerically efficient provably convergent algorithm to solve it. The solution presented generalizes commonly used techniques such as the extended Kalman smoother and Differential Dynamic Programming. The proposed solution fully exploits the sparsity of the problem and scales linearly with time, making it a promising method for model predictive control.

Contributions. In this paper, we derive a stagewise Newton method for dynamic game control with imperfect state observations. The proposed approach scales linearly in the time horizon. Furthermore, a merit function and a line search procedure are introduced to guarantee convergence. To our knowledge, this is the first iterative procedure with convergence guarantee for the dynamic game control problem with imperfect state observation. The proposed solver couples estimation and control by merging an iterative optimal control algorithm similar to minimax DDP and an iterative risk sensitive Kalman smoother. We illustrate the behavior of the resulting controller on two realistic robotic problems.

Notations. The derivative of a function f with respect to a vector v is denoted by f v , similarly for second order derivatives with respect to vectors u, v is denoted as f uv . If (v i ) i∈N is a sequence of vectors, then v k:t is a vector concatenating v k . . . v t . 1 x∈A is the indicator function which equals 1 if x ∈ A and 0 otherwise. I n denotes the identity matrix of size n by n.

II. PROBLEM STATEMENT

Similar to [START_REF] Copp | Nonlinear output-feedback model predictive control with moving horizon estimation[END_REF], [START_REF]Simultaneous nonlinear model predictive control and state estimation[END_REF], this work studies a special class of nonlinear dynamic games with imperfect state observation [START_REF] James | Risk-sensitive control and dynamic games for partially observed discrete-time nonlinear systems[END_REF]. Given a history of measurements y 1:t , a history of control inputs, u 0:t-1 and a prior on the initial state x0 , we aim to find a control sequence u t:T -1 that minimizes a given cost ℓ while an opposing player aims to find the disturbances (w 0:T , γ 1:t ) that maximize this cost ℓ minus a weighed norm of the disturbances. Such a problem is formally written as:

min u t:T -1 max w 0:T max γ1:t T -1 j=0 ℓ j (x j , u j ) + ℓ T (x T ) (1)
- 1 2µ   ω T 0 P -1 ω 0 + t j=1 γ T j R -1 j γ j + T j=1 w T j Q -1 j w j   subject to x 0 = x0 + w 0 , (2a) x j+1 = f j (x j , u j ) + w j+1 , 0 ≤ j < T, (2b) y j = h j (x j ) + γ j , 1 ≤ j ≤ t. ( 2c
)
where µ > 0. x j is the state, ω j the process disturbance, γ j the measurement disturbance, T the time horizon, t the current time. The transition model f j , the measurement model h j and the cost ℓ j are assumed to be C 2 . The measurement uncertainty R j , the process uncertainty Q j and the initial state uncertainty P are positive-definite matrices.

Interestingly, this problem encompass various formulations of control and estimation. If t = 0 and if w 0 is fixed to zero, we recover dynamic game control with perfect state information. Additionally, if t = 0, in the limit where µ tends to zero, we find the generic optimal control formulation [START_REF] Campi | Nonlinear discrete-time risk-sensitive optimal control[END_REF]. And lastly, if t = T and if we consider all the cost ℓ j to be null, then, (1) is equivalent to maximizing the MAP.

III. METHOD

A. First order conditions for a Nash equilibrium

The main challenge in the problem formulation (1) is the equality constraint maintaining the dynamic feasibility. A popular approach [START_REF] Morimoto | Minimax differential dynamic programming: application to a biped walking robot[END_REF] is to derive a DDP-like algorithm by sequentially taking quadratic approximations of the value function recursion. However, a stagewise Newton step can readily be derived. One of the key features of the dynamic game (1) is that by changing the decision variable of the opposing player, one can transform the problem into an unconstrained one [START_REF] James | Risk-sensitive control and dynamic games for partially observed discrete-time nonlinear systems[END_REF]. Indeed, we can use the equality constraints of Eq. ( 2) to replace disturbance maximization into a maximization over the state sequence. Then the problem loses its equality constraints and can be formulated as the search of the saddle point of

J(x 0:T , u t:T -1 ) = T -1 j=0 ℓ j (x j , u j ) + ℓ T (x T ) (3)
- 1 2µ (x 0 -x0 ) T P -1 (x 0 -x0 ) - 1 2µ t j=1 (y j -h j (x j )) T R -1 j (y j -h j (x j )) - 1 2µ T -1 j=0 (x j+1 -f j (x j , u j )) T Q -1 j+1 (x j+1 -f j (x j , u j )).
However, without convexity and concavity assumptions, we cannot aim at finding global solutions of the minimax problem. Hence, we restrict our attention to local Nash equilibrium, namely a point (x ⋆ 0:T , u ⋆ t:T -1 ) such that there exits δ > 0 such that for any (x 0:T , u t:T -1 )

satisfying ||x 0:T -x ⋆ 0:T || < δ and ||u t:T -1 -u ⋆ t:T -1 || < δ, we have J(x 0:T , u ⋆ t:T -1 ) ≤ J(x ⋆ 0:T , u ⋆ t:T -1 ) ≤ J(x ⋆ 0:T , u t:T -1
). (4) A standard approach to this problem is to search for a stationary point [START_REF] Bas | Dynamic noncooperative game theory[END_REF]:

∂J ∂x 0:T (x ⋆ 0:T , u ⋆ t:T -1 ) ∂J ∂u t:T -1 (x ⋆ 0:T , u ⋆ t:T -1 ) = 0 (5)
Interestingly, the change of decision variable in Eq. 3 turned the problem into an unconstrained one but made no assumption on the structure of the cost. The only required assumption is that each disturbance is in a one to one map with the state at each time step.

B. About the Linear Quadratic case

In the linear quadratic case, Whittle has shown that under some conditions, the saddle point of ( 4) is global and can be computed analytically. More precisely, the order of the minimization and maximization in (1) can be interchanged, namely the lower value and upper value of the game are equal. Despite this result, one of the difficulties of the problem ( 1) is that it links estimation and control. One the major contribution of Whittle is the introduction of the notion of past stress and future stress showing that the KF and LQR principles can still be applied. In other words, the problem can be solved by performing a backward recursion on the controls and future states and a forward recursion on the past states. The future stress recursion can be interpreted as a value function recursion similar to LQR, while the past stress can be interpreted as a rollout of KF. Here, we use these two principles to efficiently solve iteratively the nonlinear case.

C. A stagewise Newton's method

In this section, a stagewise formulation of the Newton method to find a stationary point of J is introduced. While a naive implementation of the Newton method would yield a complexity of O(T 3 ), it is shown that the special structure of the Hessian induced by time can be exploited in order to obtain a linear complexity in time O(T ). In the perfect state observation case, [START_REF] Dunn | Efficient dynamic programming implementations of newton's method for unconstrained optimal control problems[END_REF] and [START_REF] Di | Newton's method, bellman recursion and differential dynamic programming for unconstrained nonlinear dynamic games[END_REF] derived a stagewise Newton method with a backward recursion on the controls. However, with imperfect state observation, it is no longer clear how to do this with only one recursion. Instead, we show that the principles introduced by Whittle can be applied.

To ensure that the proposed method is well defined and to guarantee convergence, we assume that the cost satisfies smoothness and non-degeneracy conditions required for the convergence of Newton's method [START_REF] Nocedal | Numerical optimization[END_REF]. As the cost (3) is unconstrained, the gradients and Hessian of the cost can readily be computed. At iteration i, given a guess x i 0 , x i 1 . . . , x i T , u i t . . . , u i T -1 , also referred as the nominal trajectory, the Newton step, denoted by p, satisfies

    ∂ 2 J ∂x 0:T ∂x 0:T ∂ 2 J ∂x 0:T ∂u t:T -1 ∂ 2 J ∂u t:T -1 ∂x 0:T ∂ 2 J ∂u t:T -1 ∂u t:T -1     p =     ∂J ∂x 0:T ∂J ∂u t:T -1     (6) Here, p = p T x 0:T p T u t:T -1
T where p x 0:T ∈ R (T +1)nx is a stack of vectors p x k ∈ R nx with n x being the dimension of the state space. Similarly, p u t:T -1 ∈ R (T -t)nu is a stack of vectors p u k ∈ R nu with n u being the dimension of the control space. To simplify the notations, we define an augmented Hessian of the cost that contains the second order derivatives of the dynamics for all k < T .

lxx k = ℓ xx k + µ -1 w i k+1 T Q -1 k+1 f xx k + µ -1 1 1≤k≤t γ i k T R -1 k h xx k , lxu k = lux T k = ℓ xu k + µ -1 w i k+1 T Q -1 k+1 f xu k , luu k = ℓ uu k + µ -1 w i k+1 T Q -1 k+1 f uu k , (7)
where the derivatives are evaluated at the current guess and where

w i k+1 := x i k+1 -f k (x i k , u i k ) and γ i k := y k -h k (x i k ).
Here, the second order derivatives of the dynamics are tensors. The exact definition of the tensor indexing and the tensor product is provided in the supplementary material [START_REF] Jordana | [END_REF].

The next three propositions are analogous to the principles introduced by Whittle: the past stress recursion, the future stress recursion and the coupling of the past and future stress recursions. The first proposition, analogous to the future stress recursion, expresses every future state and control update steps as a function of p xt .

Proposition 1 (Future stress). In Equation (6), the last (T -t)(n x + n u ) rows are equivalent to:

∀k ≥ t, p u k = G k p x k + g k (8)
p x k+1 = (I -µQ k+1 V k+1 ) -1 (f x k p x k + f u k p u k + µQ k+1 v k+1 -w i k+1 )
where V k and v k are solutions of the backward recursion:

Γ k+1 = I -µV k+1 Q k+1 (9)
Q uu = luu k + f u k T Γ -1 k+1 V k+1 f u k Q ux = lux k + f u k T Γ -1 k+1 V k+1 f x k Q u = ℓ u k + f u k T Γ -1 k+1 v k+1 -V k+1 w i k+1 G k = -Q -1 uu Q ux g k = -Q -1 uu Q u V k = lxx k + f x k T Γ -1 k+1 V k+1 f x k + Q T ux G k v k = ℓ x k + f x k T Γ -1 k+1 v k+1 -V k+1 w i k+1 + Q T ux g k
with the terminal condition

V T = ℓ xx T , v T = ℓ x T . (10)
In those equations, µ intervenes only in Γ k and the augmented terms of the cost. Interestingly, Γ -1 k shifts, at each time step, the value function terms V k and v k . Then, the second proposition, analogous to the past stress recursion, expresses every past state update steps as a function of p xt .

Proposition 2 (Past stress). In Equation (6), if t ≥ 1, the first (t -1)n x rows are equivalent to: ∀k = 0, . . . , t -1,

p x k = E -1 k+1 f x k T Q -1 k+1 (w i k+1 + p x k+1 ) + P -1 k μk + µl x k ( 11
)
where P k and μk are solution of the forward recursion:

E k+1 = P -1 k + f x k T Q -1 k+1 f x k -µ lxx k Pk+1 = Q k+1 + f x k (P -1 k -µ lxx k ) -1 f x k T K k+1 = Pk+1 h x T k+1 (R k+1 + h x k+1 Pk+1 h x T k+1 ) -1 P k+1 = (I -K k+1 h x k+1 ) Pk+1 μk+1 = (I -K k+1 h x k+1 )(f x k μk -w i k+1 ) + K k+1 γ i k+1 + µP k+1 Q -1 k+1 f x k E -1 k+1 ( lxx k μk + ℓ x k ) ( 12
)
with the initialization

P 0 = P, μ0 = x0 -x i 0 . (13)
Interestingly, if all the cost terms ℓ j are zero and if t = T , the method is equivalent to a Newton method on the MAP. Furthermore, if the second order derivatives of the measurement function are omitted, then, the algorithm is equivalent to the iterative Kalman Smoother. Finally, the third proposition shows how both past stress and future stress recursions can be coupled to find the update step p xt . Proposition 3 (Coupling). In Equation ( 6), the remaining rows (from tn x + 1 to (t + 1)n x ) are equivalent to

p xt = P -1 t -µV t -1 P -1 t μt + µv t . (14)
In the limit case when µ tends to zero, the estimation and control are decoupled and we recover the usual certainty equivalence principle: p xt = μt . The algorithm is then equivalent to an iterative estimator and an iterative controller running independently. More precisely, at each iteration the controller uses the current estimate of the smoother.

Proof. The proof follows from the analytical derivations of the gradient and the Hessian of (3), a forward induction from 0 to t and a backward induction from T to t. The complete proof is provided in the supplementary material [START_REF] Jordana | [END_REF].

Algorithm 1: Stagewise Newton step

Input:

x i 0 , x i 1 . . . , x i T , u i t . . . , u i T -1 // Estimation forward pass 1 P 0 ← P , μ0 ← x0 -x i 0 2 for k = 0, ...t -1 do 3 P k+1 , μk+1 ← Eq. (12) // Control backward pass 4 V T ← ℓ xx T , v T ← ℓ x T 5 for k = T -1, ...t do 6 V k , v k ← Eq. (9)
// Estimation and control coupling Output: px 0 , px 1 . . . , px T , pu t . . . , pu T -1

7 px t ← P -1 t -µVt
In the end, the update step, p, can be computed with a forward recursion on the past indexes, a backward recursion on the future indexes, a coupling equation, a backward recursion on the past indexes and a forward recursion on the future indexes. Algorithm 1 summarizes those steps. Clearly, the complexity is linear in time. Instead of inverting a matrix of size ((T + 1)n x + (T -t)n u ), Algorithm 1 only operates with matrices of size n x or n u and the number of operation is proportional to T .

D. Line-search and convergence

In the linear quadratic case, Algorithm 1 is equivalent to Whittle's derivations and only one iteration is required to find a solution. However, in the general nonlinear case, several iterations of Newton's step are required. A common approach to guarantee the convergence of the overall iterative procedure is to introduce a line search and a merit function [START_REF] Nocedal | Numerical optimization[END_REF]. Given a guess at iteration i and a direction p, the next guess is defined by

x i+1 0:T u i+1 t:T -1 = x i 0:T u i t:T -1 + α i p x 0:T p u t:T -1 , (15)
where the step length α i is chosen in order to decrease the merit function. As advocated by Nocedal et al. [START_REF] Nocedal | Numerical optimization[END_REF], a Newton step provides a descent direction for the merit function

f M (x 0:T , u t:T -1 ) = 1 2 T j=0 ∂J ∂x j 2 + 1 2 T -1 j=t ∂J ∂u j 2 . (16)
This merit function can be derived analytically. The exact derivations of each gradient are provided in the supplementary material [START_REF] Jordana | [END_REF]. By construction, the expected decrease of the direction p derived by Algorithm 1 is

p T ∇f M = -||∇J|| 2 2
and the following convergence guarantees hold.

Proposition 4. Assuming that the norm of the inverse of the Hessian of J is bounded and that the step length α i satisfies the Wolfe conditions for the merit function (16), the sequence (x i 0:T , u i t:T -1 ) i defined by the update rule [START_REF] Bell | The iterated kalman smoother as a gauss-newton method[END_REF] with steps from Algorithm 1 is globally convergent to a stationary point of (3). Furthermore, when the iterate is sufficiently close to the solution, the sequence has quadratic convergence.

Proof. This proposition is a direct consequence from the fact that Algorithm 1 yields a Newton step. A detailed proof of the convergence guarantees of Newton method is provided in [START_REF] Nocedal | Numerical optimization[END_REF].

One may ask under which conditions the Hessian of J is non-degenerate. Intuitively, large values of µ can make the problem ill-defined. Indeed, if the opposing player can choose large disturbances, then the controller might not be able to compensate. In the linear quadratic case, Whittle [START_REF] Whittle | Risk-sensitive linear/quadratic/gaussian control[END_REF] studied this maximum value for µ that makes the problem ill-defined. Although, we do not study this limit value in the nonlinear case, we note that analogously to the linear quadratic case, the algorithm is well defined if Γ k and P -1 k -µ lxx k are positivedefinite which is the case when µ is small enough.

E. About the cooperative case

So far, only the case, µ > 0 has been considered, but, the case µ < 0 is also well defined. Indeed, the search for a stationary point of J can be done for an arbitrary sign of µ. However, such a stationary point would now be a way to find a local minimum of J with respect to the variables (x 0:T , u t:T -1 ). Interestingly, this scenario can be interpreted as a cooperative scenario between the controller and the opposing player. In fact, the disturbances can be seen a second controller minimizing the cost, ℓ, and maximizing the likelihood of the disturbances. Clearly, this change of sign does not affect the derivation of the stagewise Newton method. However, it can be noted that in that case, one can directly use the cost J as a merit function.

IV. EXPERIMENTS

A Python implementation of the proposed method is available online [START_REF] Jordana | [END_REF]. It is based on the Crocoddyl software [START_REF] Mastalli | Crocoddyl: An Efficient and Versatile Framework for Multi-Contact Optimal Control[END_REF], a state of the art (risk-neutral) DDP solver which provides analytical derivatives of robot dynamics. In this section, two numerical examples illustrate the proposed method.

A. Planar quadrotor

We study a quadrotor moving in a plane aiming to reach the position (p x p y ) = (2 0) starting at the origin without initial velocity. The state is x = (p x p y θ ṗx ṗy θ) T where θ is the orientation of the quadrotor. The system dynamics is

mp x = -(u 1 + u 2 ) sin(θ), mp y = (u 1 + u 2 ) cos(θ) -mg, J θ = r(u 1 -u 2 ), (17)
where the control input u = (u 1 u 2 ) T ∈ R 2 represents the force at each rotor and g is gravitational acceleration. An exponential cost models the presence of an obstacle

ℓ k (x k , u k ) = 0.3 exp -10(p xk -1) 2 -0.5(p y k + 0.1) 2 + 0.005∥u k -ū∥ 2 2 + 0.05(x k -x ⋆ ) T L(x k -x ⋆ ) ℓ T (x T ) = (x T -x ⋆ ) T L(x T -x ⋆ ), (18)
where ū = mg 2 (1 1) T , x ⋆ = (2 0 0 0 0 0) T , and L = diag(100 100 100 1 1 1). Only the position, p x , p y , and orientation θ are part of the measurements. The integration and discretization of the model is done with Runge Kutta 4 with a time step of 0.05 and the total horizon, T , is 60. Furthermore,

P 0 = Q = 10 -5 I 6 , R = 10 -4 diag(1 1 0.01) and x0 is the origin. A backtracking line-search is used -a step is accepted if f i+1 M ≤ f i M + α i cp T i f i M where f i M = f M (x i 0:T , u i t:T -1 ) with c = 1 4 .
The iterative process is stopped when the decrease in the merit function is lower than 10 -12 .

Fig. 1 illustrates the solution obtained by the solver for different values of µ. The neutral controller, the limit when µ tends to zero, aiming at minimizing the cost without accounting for disturbances, is solved using DDP. Interestingly, when µ is positive (the non-cooperative case), the opposing player chooses disturbances that will push the quadrotor towards to the obstacle and when µ is negative (the cooperative case), the opposing player chooses disturbances that will push the quadrotor away form the obstacle. For this experiment, we found that the value of µ for which Γ k and P -1 k -µ lxx k are no longer positive-definite matrices was around 20. Next, we illustrate the risk-sensitive behavior of the resulting controller in closed loop in a simulation with disturbances following Gaussian distributions: x 0 ∼ N (x 0 , P 0 ), w k ∼ N (0, Q) and γ k ∼ N (0, R). We set µ = 6 and at each time step of the simulation, Algorithm 1 is run and u t is applied to the system. Additionally, we compare to the neutral controller -an iterative Kalman smoother is used for the filtering and the controller uses DDP with the last state estimate from the smoother as an initial condition. Fig. 2 depicts the average and standard deviation over one thousand simulation. We can see that, in this MPC scheme, the dynamic game controller maintains a larger distance from the obstacle, resulting in safer behavior.

- 1 P - 1 t

 11 μt + µvt // Estimation backward pass 8 for k = t -1, ...0 do 9 px k ← Eq. (11) // Control forward pass 10 for k = t, . . . T -1 do 11 pu k , px k+1 ← Eq. (8)

Fig. 1 .

 1 Fig. 1. Initial plan for different values of µ. The larger µ the more the controller plans to be pushed against the obstacle.

Fig. 2 .

 2 Fig.2. Average trajectory. Compared the neutral controller, the dynamic game controller (µ = 6) exhibits a risk sensitive behavior as it remains further from the high cost area representing the obstacle.

Fig. 3

 3 Fig.3shows the distribution of control trajectories. Interestingly, the dynamic game controller has a larger standard deviation.

Fig. 3 .

 3 Fig. 3. Average control trajectories. Compared the neutral controller, the game controller (µ = 6) has a larger standard deviation.

V. CONCLUSION

We introduced an iterative solver to find local Nash equilibrium of dynamic game with imperfect state measurements. The proposed algorithm is proven to be equivalent to Newton's method and benefits from its convergence properties while scaling linearly with the time horizon.

This work was in part supported by the European Union Horizon 2020 research and innovation program (grant agreement 780684), the National Science Foundation grants 1825993, 1932187, 1925079, 2026479, and the French government under management of Agence Nationale de la Recherche as part of the "Investissements d'avenir" program, reference ANR-19-P3IA-0001 (PRAIRIE 3IA Institute), Louis Vuitton ENS Chair on Artificial Intelligence.

B. An industrial robot

In this example, we consider the 7-DoF torque-controlled KUKA LWR iiwa R820 14. The dynamics of the robot are provided by Pinocchio [START_REF] Carpentier | Pinocchio: fast forward and inverse dynamics for poly-articulated systems[END_REF]. The 14-dimensional state is composed of the joint positions and velocities. We consider the following prior on the initial condition x0 = 0.1 0.7 0. 0.7 -0.5 1.5 0.

T . The control input is a 7-dimensional vector of the torque applied on each joint. The goal is to move the end effector to a desired position, p target = -0.4 0.3 0.7 with the following cost:

) where ū(x k ) is the gravity compensation and p(x k ) the position of the end-effector. For the measurement model, we assume that only the joints position are measured. The initial control inputs u 0 , . . . u t-1 are generated with DDP. Given those t initial control inputs, t measurements are generated according to an undisturbed trajectory. More precisely, for 1 ≤ k ≤ t, the observations are defined by

)) where f (k) (x 0 , u 1:k-1 ) denotes the state value at the k th step integrated from the initial guess x0 . The horizon, T , is 100 and t is 5 while the sensitivity parameter is set to µ = 1.2. Here P 0 = Q = 0.01 × I 14 and R = 0.5 × I 7 . For this experiment, the second order derivatives of the dynamics were approximated to be null as the former are not provided by most standard rigid body dynamics libraries such as Pinocchio [START_REF] Carpentier | Pinocchio: fast forward and inverse dynamics for poly-articulated systems[END_REF]. Note that this is a common practice for state of the art optimal control algorithms in robotics [START_REF] Mastalli | Crocoddyl: An Efficient and Versatile Framework for Multi-Contact Optimal Control[END_REF]. Our solver converges nevertheless, suggesting that this approximation might be used to scale to a large number degrees of freedom for realtime computations (e.g. MPC). In Fig. 4, we plot the solution of the dynamics game solver compared to DDP in the end effector space, the shaded grey area represents the estimation part of the solution. We can see that the dynamic game controller plans that the disturbances will slow down the reaching task.