Learning equilibrium strategies for games with unknown changing states

Equilibrium Learning in Unbounded Stochastic Games with Gaussian Transitions

Machine Learning

Summary

When multiple decision makers interact over time in a system where states can change in complicated, unbounded ways, it is hard to learn stable strategies. The authors study games where transitions between states involve random noise and unknown effects, and propose a method that learns from a single long sequence of observations. Their method uses a statistical model called a Gaussian process to estimate the unknown system behavior and then solves simpler versions of the game to approximate equilibrium strategies. They prove that, under certain conditions, the strategies learned converge to approximate Nash equilibria within a region of interest, and they show in experiments how their approach depends on problem complexity.

What this means in practice

  • For multiagent system engineers: Design adaptive strategies for interacting agents where system dynamics are complex and noisy without knowing full model details.
  • For autonomous vehicle control teams: Improve decision-making in scenarios with continuous state changes and uncertain environment dynamics using learned equilibrium strategies.

Authors

Jonathan Anthony Mavroforas, Fred Roosta

Abstract

Learning equilibria from data is difficult when several decision makers interact indefinitely and the system state has no prescribed bounds. We examine discounted general-sum stochastic games with compact action sets and an unknown nonlinear drift observed through Gaussian transition noise. The proposed procedure uses a single uninterrupted trajectory to update Gaussian-process models of the drift and to solve successively refined finite games. We prove a perturbation result showing that stability of equilibrium selection, together with uniform KL accuracy of Gaussian transition models, is sufficient for regional uniform convergence of the induced values and approximate Nash behavior in the original game. The region specifies where the guarantees are evaluated; strategies and dynamics continue to act on the entire Euclidean state space. For GP estimators, simultaneous confidence bounds yield a rate controlled by posterior uncertainty, kernel information gain, and joint-state dimension. Numerical studies illustrate how kernel choice and dimension appear in the predicted convergence behavior.
View PDFOpen arXiv