PaperlayerView exact revision on arXiv

Source-linked AI summary

Learning Dynamic Games for Cooperative Iterative Tasks

Mark Pustilnik, Francesco Borrelli

arXiv:2610.28901v1cs.RO

TL;DR

Repeated cooperative tasks require learning from prior executions while handling individual costs and coupled constraints, including trade-offs among players. The paper proposes joint selection of stored terminal states and equilibrium candidates using cooperative rules, with retained feasible continuations supporting recursive feasibility and player-wise non-degradation under stated conditions.

  • Problem

    Iterative learning for dynamic games must address multiple equilibria with different player trade-offs, so improving one player's cost may worsen another's and players need a way to agree on new solutions.

    Source: §I · p. 1

  • Method

    The framework builds a sampled joint safe set and player-specific costs-to-go from successful feasible trajectories, then jointly selects terminal states and equilibrium candidates under agreed cooperative rules.

    Source: §I · p. 1, A. Sampled Joint Safe Set and Cost-to-Go · p. 3

  • Results

    The scheme is recursively feasible under its stated assumptions, and player-wise acceptance guarantees non-degradation across completed iterations under the applicable conditions.

    Source: §V · p. 5, §VII · p. 8

  • Takeaways & Limitations

    The framework accommodates nonlinear and nonconvex games through verified feasible candidates and illustrates cooperative selection in a three-player motion-planning example.

    Source: §VII · p. 8

    The finite-horizon GNE conditional on a selected terminal state does not imply that the concatenated full-task trajectory or receding-horizon policy is a Nash equilibrium.

    Source: B. Cooperative Iterative Learning… · p. 2

Abstract

from arXiv · show

We consider cooperative and iterative tasks involving multiple agents whose interactions are modeled as a dynamic game with shared constraints. We propose a general learning framework applicable to nonlinear and nonconvex dynamic games that uses previously executed feasible trajectories to construct a sampled joint safe set and player-specific cost-to-go functions. At each time step, the agents jointly select a previously sampled terminal state and a Generalized Nash equilibrium used to reach it. A new solution is adopted only if it satisfies a cooperative acceptance rule agreed upon by the players. The framework accommodates individual non-degradation requirements and selection criteria such as weighted costs and Nash bargaining. We show that the proposed framework guarantees recursive feasibility and characterize conditions under which each player's cost is non-increasing across iterations.

I. INTRODUCTION

The paper extends iterative learning to cooperative dynamic games, where players retain individual objectives but must agree on how to select among outcomes with different trade-offs. It combines prior game-learning work with a repeated-task formulation involving deterministic dynamics and private and shared constraints.

I. INTRODUCTION

  • The framework jointly selects terminal occurrences and equilibrium candidates under a pre-agreed cooperative rule, addressing trade-offs among players with individual costs.Individual non-degradation can govern admissibility, while weighted costs or Nash bargaining can select among admissible candidates.Source: §I · p. 1

II. RELATED WORK

  • Prior work spans iterative learning, multi-agent MPC, generalized Nash equilibria, and cooperative criteria such as Nash bargaining,,,.Learned terminal information has also been incorporated into generalized Nash games.Source: §II · p. 1

III. PROBLEM FORMULATION

  • Each repeated task starts from the same joint state and seeks a common target under deterministic, unchanged game data, with individual dynamics and private constraints coupled by shared constraints.Player costs may depend on joint states and inputs, without objective separability.Source: §III · p. 2

A. Generalized Nash Equilibrium

A generalized Nash equilibrium captures strategic interaction when players’ feasible sets are coupled by shared constraints. The learning objective combines equilibrium-based candidate generation with cooperative acceptance, while distinguishing finite-horizon equilibria from equilibrium properties of the full task.

A. Generalized Nash Equilibrium

  • A generalized Nash equilibrium is a joint strategy where no player can lower its cost through a feasible unilateral action.For differentiable games, combined KKT conditions can compute equilibrium candidates, but in nonconvex games they may identify stationary candidates that are not GNEs.Source: A. Generalized Nash Equilibrium · p. 2

B. Cooperative Iterative Learning Objective

  • The learning objective starts from a successful feasible trajectory and seeks improvement while preserving a feasible continuation, cooperative acceptance, and individual non-degradation under the applicable rule.The formulation's GNE is an open-loop equilibrium of the finite-horizon game conditional on the selected terminal state, not necessarily an equilibrium of the full-task trajectory or resulting receding-horizon policy.Source: B. Cooperative Iterative Learning… · p. 2

IV. LEARNING DYNAMIC GAME METHOD

At each step, players jointly choose a previously sampled terminal state and an equilibrium candidate, then evaluate the resulting complete trajectory under agreed rules. Stored successful trajectories supply terminal states, player-specific costs-to-go, and feasible continuations.

IV. LEARNING DYNAMIC GAME METHOD

  • Players jointly select a terminal joint state from the sampled safe set and an equilibrium candidate that reaches it, then evaluate the complete trajectory under agreed acceptance and selection rules.If no candidate is accepted, they continue along the retained feasible backup.Source: §IV · pp. 2–3

A. Sampled Joint Safe Set and Cost-to-Go

  • Previously successful trajectories construct a sampled joint safe set and player-specific costs-to-go, supplying feasible continuations beyond the prediction horizon and accounting for remaining task cost.An iteration is successful when it reaches the target in finite time while satisfying private and shared constraints.Source: A. Sampled Joint Safe Set and Cost-to-Go · p. 3
  • Each stored joint-state occurrence is linked to its continuation and cost vector, and repeated visits remain distinct when their continuations or costs differ.Reconnecting a feasible predicted trajectory to a stored occurrence yields a complete feasible continuation without requiring a new equilibrium at every later step.Source: A. Sampled Joint Safe Set and Cost-to-Go · p. 3
  • The method retains the executed feasible state-input continuation as a backup because it may combine segments from different terminal states and GNE parameterizations.That backup need not itself be a GNE for any single parameterization.Source: A. Sampled Joint Safe Set and Cost-to-Go · p. 3

B. Mixed-Integer Dynamic Game Formulation

The formulation makes terminal selection discrete and equilibrium strategies continuous, then applies the cooperative rule to both terminal occurrences and equilibrium candidates. A shared-multiplier parameterization supplies a way to explore candidate equilibria, with qualifications in nonconvex games.

B. Mixed-Integer Dynamic Game Formulation

  • A common binary vector selects exactly one stored terminal occurrence to be reached after N prediction steps.Each occurrence identifies a stored joint state, its continuation, and player-specific costs-to-go.Source: B. Mixed-Integer Dynamic Game… · p. 3
  • The objective combines predicted horizon cost with the selected continuation cost, and an equality constraint enforces exact reconnection to the stored joint state.For a fixed terminal selection, the continuation cost is constant in the inner game but influences which terminal state is selected.Source: B. Mixed-Integer Dynamic Game… · p. 3
  • The cooperative rule selects among both terminal occurrences and equilibrium candidates because each terminal selection may admit multiple GNEs.Terminal selection is discrete, whereas the corresponding strategies are continuous.Source: B. Mixed-Integer Dynamic Game… · p. 3

C. GNE Parameterization

  • The shared-multiplier parameterization explores candidate equilibria by varying positive diagonal player-specific scalings while preserving shared-constraint complementarity.A solution need not exist for every allocation.Source: C. GNE Parameterization · pp. 3–4
  • In nonconvex games, KKT solutions are stationary candidates and do not certify GNEs.The parameterization's candidate-generating role therefore does not itself establish equilibrium validity in nonconvex cases.Source: C. GNE Parameterization · p. 4
  • Removing common-rescaling redundancy leaves M − 1 independent allocation parameters and recovers the KKT structure of Rosen’s r-normalized equilibria.The paper states that ri ∝ 1/ai.Source: C. GNE Parameterization · p. 4

D. Cooperative Solution Selection

The players agree on admissibility and selection rules to choose among candidate trajectories without increasing any player's remaining cost. Adopted candidates must be feasible and form a complete continuation to the target; otherwise the current backup is retained.

D. Cooperative Solution Selection

  • Each candidate connects a selected terminal occurrence to its stored trajectory suffix, defining a complete joint trajectory whose cost is compared with the retained backup.Players share the database and backup and apply the rules to the same candidate set with common tie-breaking and synchronized adoption.Source: D. Cooperative Solution Selection · pp. 4–5
  • The admissibility rule excludes any candidate that increases a player's remaining cost relative to the retained backup.This player-wise rule underlies the individual non-degradation guarantee.Source: D. Cooperative Solution Selection · p. 4
  • Among admissible candidates, selection can minimize a weighted sum of player costs or use Nash bargaining relative to continuing along the current backup.The standard Nash product can fail to distinguish candidates when some player cannot improve; regularization changes only ranking, not admissibility.Source: D. Cooperative Solution Selection · p. 4
  • An adopted candidate must be verified primal feasible, admissible, and selected by the agreed rule; its predicted prefix and stored suffix form a feasible trajectory to the target.If no candidate passes these tests, the current backup is retained.Source: D. Cooperative Solution Selection · p. 4

E. Practical Solution Considerations

The practical learning problem combines discrete terminal-occurrence selection with continuous allocation and equilibrium selection. The implementation samples allocation scalings, solves candidate games, and trades denser sampling against computation.

E. Practical Solution Considerations

  • The learning problem jointly selects a terminal occurrence, allocation, and equilibrium under a cooperative criterion written in minimization form.The criterion Φ can be the negative regularized Nash product.Source: E. Practical Solution Considerations · p. 5
  • For each sampled terminal occurrence and allocation scaling, the implementation formulates and solves an MCP, then checks candidates for primal feasibility and individual admissibility.It selects the accepted candidate minimizing Φ, applies its first input, and retains the existing backup if none is accepted.Source: E. Practical Solution Considerations · p. 5
  • With one MCP attempt per terminal-occurrence and scaling pair, each update needs at most nsna solves; finer scaling grids increase sampling density and computation.The implementation is a proof of concept, not intended for real-time execution.Source: E. Practical Solution Considerations · p. 5

V. THEORETICAL GUARANTEES

With an initial feasible joint trajectory and deterministic, exactly known, unchanged dynamics and constraints, the scheme preserves a feasible continuation at every step. Under individual non-degradation acceptance, completed iterations also satisfy player-wise cost guarantees.

V. THEORETICAL GUARANTEES

  • Given an initial feasible joint trajectory and deterministic, exactly known dynamics and constraints unchanged across iterations, the scheme is recursively feasible at every time step.A candidate's predicted prefix and stored suffix provide the complete feasible continuation when adopted.Source: §V · p. 5
  • The shift-and-concatenation argument preserves feasibility by retaining the backup when no candidate is adopted, or replacing it with an adopted candidate's feasible complete trajectory.Exact dynamics ensure the realized next state matches the backup's next state, so induction carries the feasible continuation forward.Source: §V · pp. 5–6
  • Under Theorem 1's conditions and individual non-degradation acceptance, each player's realized cost in every finite-time completed iteration is non-increasing.Finite-time completion additionally follows under Assumption 1 if stage costs are bounded below by a positive function away from the target.Source: §V · pp. 5–6
  • The feasibility and non-degradation guarantees do not require exhaustive GNE exploration or globally optimal outer selection; verified primal-feasible KKT/MCP candidates need not have certified global best-response optimality.If no acceptable candidate is found, the existing feasible backup is retained.Source: §V · p. 6

A. Three-Player Cooperative Motion Planning

The example studies three agents moving between initial and target states around a shared obstacle, with individual costs and constraints coupled by shared limits. Its nonlinear unicycle dynamics and nonconvex feasible set make it a cooperative motion-planning game.

A. Three-Player Cooperative Motion Planning

  • Three agents repeatedly move between initial and final states in a shared planar environment with an elliptical obstacle, individual targets, and individual cost functions.Collision avoidance and shared speed and longitudinal-actuation bounds couple their decisions.Source: A. Three-Player Cooperative Motion… · p. 6
  • The agents use a nonlinear unicycle model with heading as a state and heading rate as a control input.The continuous-time dynamics include quadratic drag and are discretized by fourth-order Runge-Kutta with a 0.25 s sampling time.Source: A. Three-Player Cooperative Motion… · p. 6
  • A joint quadratic speed budget and pairwise separation constraints couple the players, while the obstacle and separation constraints make the feasible set nonconvex.Constraints are imposed at discrete prediction nodes.Source: A. Three-Player Cooperative Motion… · p. 6
  • Each player's stage cost penalizes position error, control effort, and elapsed time outside the target joint state.The position coordinates in the obstacle constraint are expressed in meters; the obstacle is centered at (1, 0) m with semi-axes 6 m and 2 m.Source: A. Three-Player Cooperative Motion… · p. 6

B. Numerical Solution

The numerical solution compares three candidate-generation and selection configurations, initialized from a feasible trajectory. Equilibria are found by solving an MCP, while cooperative selection applies admissibility checks before choosing among candidates.

B. Numerical Solution

  • Learning starts from a feasible task-completing trajectory, and each sampled terminal occurrence is stored with its joint continuation as a backup plan.The prediction horizon is 5 steps, corresponding to 1.25 s.Source: B. Numerical Solution · p. 7
  • The KKT conditions are assembled into an MCP and solved with PATH, but convergence supplies only a first-order equilibrium candidate, not global best-response optimality.The game is nonconvex, and the reported convergence tolerance is 10^-4.Source: B. Numerical Solution · p. 7
  • The three configurations are multiple GNE candidates with Nash bargaining (M-NB), normalized GNE candidates with Nash bargaining (N-NB), and multiple GNE candidates with equally weighted cost (M-WS).N-NB uses equal shared-constraint multipliers; M-NB and M-WS explore the multiplier allocation grid.Source: B. Numerical Solution · p. 7
  • Nash bargaining selects an admissible candidate using disagreement costs initialized from the preceding iteration and updated for accepted plans and remaining continuations.The individual acceptance condition is checked before the bargaining product, so clipping negative improvements cannot admit a degrading candidate.Source: B. Numerical Solution · p. 7

C. Numerical Results

Across the three configurations, M-NB has the lowest aggregate cost at iteration 5 and the final comparison, although final individual costs trade off. The conclusion ties recursive feasibility and individual non-degradation to retained feasible continuations and stated assumptions.

C. Numerical Results

  • At iteration 5, M-NB achieves the lowest aggregate cost, 1631.37, improving on M-WS and N-NB by 1.91% and 4.05%, respectively.Its costs are also lower for every individual player at this checkpoint.Source: C. Numerical Results · p. 7, Figure 2 · p. 8
  • At iteration 15, M-NB's aggregate cost is 1548.92, 2.47% below M-WS, while its Player 1 cost is 1.14% higher and its Player 2 and 3 costs are 4.44% and 3.50% lower.N-NB terminates at iteration 6 with final aggregate cost 1700.26; M-NB's iteration-15 aggregate cost is 8.90% below that value.Source: C. Numerical Results · p. 7, Figure 2 · p. 8

VII. CONCLUSIONS

  • Stored joint trajectories provide a sampled safe set and player-specific costs-to-go for cooperative selection among terminal joint states and equilibrium candidates.The framework accommodates nonlinear and nonconvex games through verified feasible candidates.Source: §VII · pp. 7–8

C. Numerical Results

  • Under M-NB, the displayed trajectories evolve across iterations 1, 4, 8, and 15, with final displayed costs of 450.78, 449.78, and 648.36 for Players 1–3.Figure 2 shows a pronounced initial cost decrease followed by smaller improvements across the configurations.Source: C. Numerical Results · p. 7, Figure 1 · p. 8, Figure 2 · p. 8

VII. CONCLUSIONS

  • Retaining a feasible continuation ensures recursive feasibility, while player-wise acceptance guarantees non-degradation across completed iterations under stated assumptions.Future work will address computational efficiency and robustness to model uncertainty.Source: §VII · p. 8
Loading 2610.28901v1…