Search

This paper presents algorithms for non-zero sum nonlinear constrained dynamic games with full information. Such problems emerge when multiple players with action constraints and differing objectives interact with the same dynamic system. They model a wide range of applications including economics, defense, and energy systems. We show how to exploit the temporal structure in projected gradient and Douglas-Rachford (DR) splitting methods. The resulting algorithms converge locally to open-loop Nash equilibria (OLNE) at linear rates. Furthermore, we extend stagewise Newton method to find a local feedback policy around an OLNE. In the of linear dynamics and polyhedral constraints, we show that this local feedback controller is an approximated feedback Nash equilibrium (FNE). Numerical examples are provided., Comment: 19 pages. Full version of submission to ACC 2020

Dynamic games arise when multiple agents with differing objectives control a dynamic system. They model a wide variety of applications in economics, defense, energy systems and etc. However, compared to single-agent control problems, the computational methods for dynamic games are relatively limited. As in the single-agent case, only specific dynamic games can be solved exactly, so approximation algorithms are required. In this paper, we show how to extend a recursive Newton's algorithm and the popular differential dynamic programming (DDP) for single-agent optimal control to the case of full-information non-zero sum dynamic games. In the single-agent case, the convergence of DDP is proved by comparison with Newton's method, which converges locally at a quadratic rate. We show that the iterates of Newton's method and DDP are sufficiently close for the DDP to inherit the quadratic convergence rate of Newton's method. We also prove both methods result in an open-loop Nash equilibrium and a local feedback $O(\epsilon^2)$-Nash equilibrium. Numerical examples are provided., Comment: 19 pages. The shortened version was accepted at CDC 2019. arXiv admin note: substantial text overlap with arXiv:1809.08302

One of the primary challenges of system identification is determining how much data is necessary to adequately fit a model. Non-asymptotic characterizations of the performance of system identification methods provide this knowledge. Such characterizations are available for several algorithms performing open-loop identification. Often times, however, data is collected in closed-loop. Application of open-loop identification methods to closed-loop data can result in biased estimates. One method used by subspace identification techniques to eliminate these biases involves first fitting a long-horizon autoregressive model, then performing model reduction. The asymptotic behavior of such algorithms is well characterized, but the non-asymptotic behavior is not. This work provides a non-asymptotic characterization of one particular variant of these algorithms. More specifically, we provide non-asymptotic upper bounds on the generalization error of the produced model, as well as high probability bounds on the difference between the produced model and the finite horizon Kalman Filter.

In this paper, we present simple algorithms for Dueling Bandits. We prove that the algorithms have regret bounds for time horizon T of order O(T^rho ) with 1/2

In the stochastic formulation of chemical kinetics, the stationary moments of the population count of species can be described via a set of linear equations. However, except for some specific cases such as systems with linear reaction propensities, the moment equations are underdetermined as a lower order moment might depend upon a higher order moment. Here, we propose a method to find lower, and upper bounds on stationary moments of molecular counts in a chemical reaction system. The method exploits the fact that statistical moments of any positive-valued random variable must satisfy some constraints. Such constraints can be expressed as nonlinear inequalities on moments in terms of their lower order moments, and solving them in conjugation with the stationary moment equations results in bounds on the moments. Using two examples of biochemical systems, we illustrate that not only one obtains upper and lower bounds on a given stationary moment, but these bounds also improve as one uses more moment equations and utilizes the inequalities for the corresponding higher order moments. Our results provide avenues for development of moment approximations that provide explicit bounds on moment dynamics for systems whose dynamics are otherwise intractable.

This paper gives a new solution to the output feedback H_2 model matching problem for a large class of delayed information sharing patterns. Existing methods for such problems typically reduce the decentralized problem to a centralized problem of higher state dimension. In contrast, the controller given in this paper is constructed from the solutions to the centralized control and estimation Riccati equations for the original system. The problem is solved by decomposing the controller into two components. One is centralized, but delayed, while the other is decentralized with finite impulse response (FIR). It is then shown that the optimal controller can be constructed through a combination of centralized spectral factorization and quadratic programming., Comment: Preliminary draft of conference paper