Source-linked AI summary
Inverse Linear Quadratic Gaussian Games: Constrained Setting and Transferability
Kai Ren, Maryam Kamgarpour
TL;DR
The paper addresses recovering costs in finite-horizon multi-agent LQG games from observed behavior, including settings with shared constraints. It characterizes constrained-game costs and dual values and derives an unconstrained transferability bound; simulations and experiments examine recovery and performance on perturbed dynamics.
Problem
In multi-agent control, cost functions may be unknown and difficult to specify, yet they are needed to infer intent and reconstruct policies under shared constraints.
Source: §I · p. 1Method
The paper characterizes costs and optimal dual values for a constrained generalized Nash equilibrium and derives an unconstrained transferability bound for errors in costs and dynamics.
Source: §I · p. 2Results
Constrained recovery matched ground-truth policies and trajectories, while robot transferability scaled roughly linearly with dynamics error except on the wet floor.
Source: A. Cost identification in constrained… · p. 7, C. Robot experiments for transferability · p. 9Takeaways & Limitations
With small cost-parameter errors and sufficiently close dynamics, Nash policies and cost values remain close to those under expert costs.
Source: §V · p. 9The transferability analysis is restricted to unconstrained games because multiple constrained dual-value solutions make sensitivity analysis ill-posed.
Source: §I · p. 2
Abstract
from arXiv · showhide
This work addresses finite-horizon inverse linear quadratic Gaussian games. In a constrained setting, we characterize the set of cost parameters and optimal dual values that generate a given generalized Nash equilibrium, and we propose an algorithm to compute these parameters. In an unconstrained setting, we address transferability, namely, we bound the cost value perturbation between two policies: one induced by the identified cost parameters, the other by the expert parameters, under a set of different dynamics. This cost value perturbation scales linearly with the deviations in the dynamics and the identified cost parameters. Through numerical simulations, we show that, in a constrained setting, our algorithm identifies the cost parameters and dual values that can reproduce the policy and trajectories corresponding to the observed generalized Nash equilibrium. In an unconstrained setting, we show with a traffic simulation and real-robot experiments that the identified cost parameters can be used to control sufficiently close dynamics, with performance degrading linearly with the deviations in the dynamics and the identified cost parameters.
I. INTRODUCTION
The paper studies finite-horizon inverse LQG games, where costs must be recovered from observed behavior, and asks how identified costs perform under changing dynamics. It characterizes costs and dual values for a constrained generalized Nash equilibrium and develops a transferability bound for unconstrained games.
I. INTRODUCTION
- Multi-agent cost identification supports inferring intent and reconstructing policies under shared constraints, while transferability asks how performance changes on perturbed systems.The motivation includes agents whose decisions affect one another's costs, such as systems with shared collision-avoidance constraints.Source: §I · p. 1
- Prior constrained-game methods do not exactly characterize costs for generalized Nash equilibria, leaving that characterization open for linear quadratic games.The cited maximum-likelihood methods use approximate forward-game gradients, while Bayesian methods iteratively update an initial cost distribution.Source: §I · p. 1
- For constrained games, the paper characterizes cost parameters and optimal dual values corresponding to an observed generalized Nash equilibrium and gives an algorithm to compute them.The inverse problem is to make the observed policy a generalized Nash equilibrium under the identified costs and known shared constraints.Source: §I · p. 2, §II · p. 3
- For unconstrained games, the transferability bound covers errors in both identified cost parameters and dynamics, while the analysis focuses on this setting because constrained dual values can have multiple solutions.The multiple solutions make sensitivity analysis of the constrained dual-value computation ill-posed.Source: §I · p. 2
II. INVERSE LQG GAME IN CONSTRAINED SETTINGS
- The constrained inverse problem uses system dynamics, shared constraints, and an observed control policy to find costs and dual values that reproduce its generalized Nash equilibrium.The game models agents optimizing their own costs under affine constraints shared across agents.Source: §II · pp. 2–3
A. Characterization of the cost parameters and the optimal dual value
For a given generalized Nash equilibrium policy, the characterization recovers corresponding cost parameters and an optimal dual value. A backward recursion determines the quadratic cost parameters and auxiliary linear terms, while the dual characterization uses the affine dependence of expected state trajectories on the dual variable.
A. Characterization of the cost parameters and the optimal dual value
- Separating the linear cost term from the auxiliary linear term gives reference states for each agent.The passages describe this separation as part of distinguishing the two linear terms.Source: A. Characterization of the cost… · p. 3
- For affine constraints, the expected state trajectory depends affinely on an arbitrary dual variable, supporting the dual-value characterization.The affine relation is expressed using matrices determined by the known dynamics, equilibrium policy, and Riccati parameters.Source: A. Characterization of the cost… · pp. 3–4
- For a given generalized Nash equilibrium policy, Proposition 1 characterizes corresponding cost parameters and an optimal dual value.The characterization covers quadratic cost parameters, auxiliary linear terms, and the dual value.Source: A. Characterization of the cost… · p. 4
- The quadratic cost parameters and auxiliary linear terms are determined by a backward recursion.The recursion is introduced as necessary for deriving these parameters.Source: A. Characterization of the cost… · pp. 3–4
B. Computation of the cost parameters and the optimal dual values
The computation procedure selects cost parameters and an optimal dual value consistent with the observed equilibrium policy. It uses a quadratic program for cost parameters and a linear complementarity problem for the dual value.
B. Computation of the cost parameters and the optimal dual values
- A quadratic program computes cost parameters, while a linear complementarity problem computes an optimal dual value when the characterizations admit multiple solutions.The resulting parameters and dual value are consistent with the observed equilibrium policy.Source: B. Computation of the cost parameters… · p. 4
- The procedure enforces diagonal dominance of R_t to ensure R_t is positive semidefinite.A small positive τ and τ̄ are chosen for this purpose, using the Gershgorin circle theorem.Source: B. Computation of the cost parameters… · p. 4
- Existence and uniqueness conditions for the dual-value problem remain uncharacterized, and verifying the sufficient P-matrix condition is challenging.Numerical experiments consistently found solutions even though −C̃ was often not positive definite.Source: B. Computation of the cost parameters… · p. 4
III. TRANSFERABILITY OF THE IDENTIFIED COST PARAMETERS
The section bounds policy changes caused separately by cost-parameter and dynamics errors, then combines them to analyze transferability. Because constrained transferability requires a difficult dual-value sensitivity analysis, the authors focus on the unconstrained game.
III. TRANSFERABILITY OF THE IDENTIFIED COST PARAMETERS
- Constrained transferability would require sensitivity analysis of dual estimates, which is challenging because the relevant linear complementarity matrix lacks guaranteed structural conditions; the section therefore studies the unconstrained game.The approach first bounds policy perturbations, then propagates them to obtain a transferability bound.Source: §III · p. 5
A. Policy perturbation under cost parameters and dynamic errors
- The analysis distinguishes expert costs θE, an optimal identified solution θid, and perturbed identified costs bθid; θE and θid induce the same observed policy on the true dynamics.The perturbation analysis uses θid as the reference for cost-parameter error.Source: A. Policy perturbation under cost… · p. 5
- Cost-parameter error ε produces an O(ε) Nash-policy error, with a constant that grows exponentially in the remaining horizon through multiplicative Riccati-error propagation.The perturbation bounds are obtained by propagating errors in the backward Riccati terms.Source: A. Policy perturbation under cost… · p. 5
- With fixed cost parameters θ, Lemma 2 compares the Nash equilibrium policies induced on perturbed dynamics (A′, B′) with those induced on the true dynamics (A^E, B^E).Source: A. Policy perturbation under cost… · p. 6
- Proposition 2 bounds the policy difference under both dynamics and identified-cost errors by applying the separate perturbation bounds and the triangle inequality.The comparison is between policies induced by the expert and perturbed identified costs on dynamics in P.Source: A. Policy perturbation under cost… · p. 6
B. Transferability of the identified cost parameters to neighbouring dynamics
The section derives a transferability bound for identified costs on neighboring dynamics by propagating policy, state, and input perturbations into the cost difference. The cost-value perturbation is linear in the dynamics and identified-cost errors, although its bound constant grows exponentially with the squared horizon.
B. Transferability of the identified cost parameters to neighbouring dynamics
- Theorem 1 bounds cost-value perturbation linearly in the errors of the identified cost parameters and dynamics, while its constant depends exponentially on the squared horizon T^2.The horizon dependence is inherited from the policy-perturbation bound.Source: B. Transferability of the identified… · p. 6
- The proof propagates policy perturbations into state and input trajectories, then into the quadratic cost difference, including O(ε) contributions from initial-state and process-noise covariance terms.A conservative product-difference estimate bounds perturbations in the block products defining the state dynamics.Source: B. Transferability of the identified… · p. 6
- Across 100 randomized cost matrices, Fig. 2 reports optimization residuals and deviations in policy, state, and input trajectories generated from identified cost parameters and optimal dual values, relative to expert parameters.Source: Figure 2 · p. 7
- With sufficiently many demonstration samples, the estimated equilibrium policy yields ν-transferability with probability at least 1−δ.The guarantee combines Theorem 1 with a policy-estimation sample-complexity result.Source: B. Transferability of the identified… · pp. 6–7
IV. CASE STUDIES
The case studies test whether the method recovers constrained-game costs and equilibria, then examine trajectory and cost sensitivity to perturbations. In the constrained simulation, recovered policies and trajectories closely match the ground truth across randomized games and exemplary episodes.
A. Cost identification in constrained LQG game
- In five exemplary episodes, trajectories generated by identified costs closely align with ground truth.Fig. 3 compares the recovered trajectories with the ground truth.Source: Figure 3 · p. 7, A. Cost identification in constrained… · p. 7
- Across 100 randomized games, recovered policies, states, and inputs closely match ground truth, while optimization residuals remain near zero.Residual error partly reflects numerical solution error and the approximate generalized Nash equilibrium used as input.Source: A. Cost identification in constrained… · p. 7
IV. CASE STUDIES
- Small cost and dynamics perturbations preserve close trajectories, but at ϵ = 0.1 the recovered trajectory deviates significantly.These representative trajectories illustrate sensitivity to perturbation size.Source: Figure 4 · p. 8
- For the multi-car example, median cost-value perturbation grows linearly through ϵ ≤ 0.075 and more sharply at larger perturbations.The measure aggregates cost values across agents.Source: Figure 5 · p. 8
A. Cost identification in constrained LQG game
- The identified cost parameters reproduce multi-agent behavior while respecting collision-avoidance constraints.The simulation evaluates recovery from a generalized Nash equilibrium policy.Source: A. Cost identification in constrained… · pp. 7–8
B. Transferability of the identified cost parameters in an unconstrained LQG game
The transferability studies test identified costs under perturbed dynamics in a vehicle simulation and on robots moving across surfaces. Cost perturbations grow roughly linearly for sufficiently small errors, while larger dynamics errors can prevent trajectory recovery or transfer.
B. Transferability of the identified cost parameters in an unconstrained LQG game
- For ϵ ≤ 0.075, median multi-agent cost-value perturbation grows linearly; above that threshold, it grows more drastically and trajectories are no longer recovered at ϵ = 10^-1.The vehicle study uses 30 independent noise realizations; the threshold behavior is consistent with Theorem 1.Source: B. Transferability of the identified… · p. 8
C. Robot experiments for transferability
- On the lab floor, paper, and fabric, identified-cost trajectories approximately reproduce expert-cost trajectories; on the wet floor, wheel slip prevents the robots from moving.The experiment controls three JetBots on four surfaces.Source: C. Robot experiments for transferability · p. 9, Figure 6 · p. 9
- Across robot surfaces other than the wet floor, average cost-value perturbation scales roughly linearly with dynamics error; the wet-floor error is too large for transfer.Table I reports dynamics-error bounds and average cost-value perturbations over 10 runs, but its caption gives no surface-specific values.Source: C. Robot experiments for transferability · p. 9, Table I · p. 9
V. CONCLUSION
- The conclusion limits the transferability result to unconstrained games with small cost errors and dynamics sufficiently close to the expert system.Extending transferability analysis to constrained dynamic games is left for future work.Source: §V · p. 9
APPENDIX A PROOF OF LEMMA 1
The proof bounds changes in game parameters by tracing perturbations through stacked policy quantities and Riccati parameters. It uses inverse-matrix perturbation and backward unrolling to obtain the stated bounds.
APPENDIX A PROOF OF LEMMA 1
- The proof first stacks agents’ feedback gains and biases into a joint representation for the LQG game.The stacked representation uses the block matrix Φ_t and Riccati parameters defined earlier.Source: Appendix A · p. 10
A. Preliminary parameters’ bounds.
- The proof takes differences in the policy-parameter equations, bounds terms, and unrolls the recursion backward from the horizon to establish Lemma 1’s bounds.It derives bounds for changes in gains and biases from perturbations in Riccati parameters.Source: A. Preliminary parameters’ bounds · pp. 10–11
- An inverse-matrix perturbation identity bounds changes in Φ^-1 by changes in Φ when the error is sufficiently small.The passage states that the inverse perturbation is O(ϵ) for arbitrarily small ϵ.Source: A. Preliminary parameters’ bounds · p. 10
APPENDIX B PROOF OF LEMMA 2
The proof compares games with the same cost parameters under expert and neighboring dynamics, then propagates dynamics-induced changes through Riccati quantities and the Nash policy to establish Lemma 2’s bounds.
APPENDIX B PROOF OF LEMMA 2
- The comparison holds cost parameters fixed and varies the expert dynamics to a neighboring dynamics.The proof uses differences between parameters induced by the two dynamics.Source: Appendix B · p. 11
- Differences in the Riccati and policy equations are bounded using dynamics perturbations, yielding the two bounds stated in Lemma 2.The proof applies product-difference expansion and completes the square when combining bounds.Source: Appendix B · pp. 11–12
- With terminal costs held equal, the proof propagates Riccati perturbations backward through the horizon.The recursion starts with zero terminal Riccati difference.Source: Appendix B · p. 12
APPENDIX C DERIVATION OF THE TRANSFERABILITY COST BOUND
The appendix derives the transferability cost bound by bounding stacked trajectory and input perturbations under changed dynamics, then bounding covariance trace terms.
APPENDIX C DERIVATION OF THE TRANSFERABILITY COST BOUND
- The stacked mean trajectories and player inputs are represented as x = Fµ0 + Zα and ui = −Kix − αi.The appendix uses these stacked forms in its transferability-bound derivation.Source: Appendix C · p. 12
A. Bounding the stacked terms.
- A conservative product-difference bound is used to bound stacked terms built from products of transition matrices and, for Z, control matrices.The bound considers the stacked blocks over time and the stated control-matrix norm contribution.Source: A. Bounding the stacked terms · p. 12
C. Bounding the covariance trace terms.
- Unrolling covariance perturbations from ∥∆Σ0∥ = 0 yields a time-dependent bound, and the associated trace term accounts for initial-state uncertainty and accumulated process noise.The stated bound is ∥∆Σt∥ ≤ t(t + 1)ξ\bar F^(2t−1).Source: Appendix C · p. 12, C. Bounding the covariance trace terms · p. 13
D. Transferability bound in Theorem 1.
The derivation simplifies the cost-deviation terms to obtain the transferability bound in Theorem 1, and the appendix defines matrices omitted from the main text.
D. Transferability bound in Theorem 1.
- The cost-deviation terms are bounded and collected into the overall cost-deviation bound stated in Theorem 1.The supplied derivation identifies this as the overall bound but does not provide a readable bound expression.Source: D. Transferability bound in Theorem 1 · p. 13
- The derivation drops quadratic ε terms and identifies ξ∥ui∥∥∆ui∥ as dominating ξ∥x∥∥∆x∥ because it carries higher powers of ξ and T.It then substitutes bounds on ∥x∥ and ∥∆x∥ before collecting dominant terms.Source: D. Transferability bound in Theorem 1 · p. 13
APPENDIX D MATRICES DEFINITIONS
- Appendix D supplies matrix definitions omitted from the main text, including block matrices built from H, B, and F terms.The provided matrix fragments show repeated diagonal F blocks and transition-matrix products multiplying B blocks.Source: Appendix D · p. 13