Finite-horizon equilibria for neuro-symbolic concurrent stochastic games

Rui Yan, Gabriel Santos, Xiaoming Duan, David Parker, Marta Kwiatkowska

Research output: Chapter in Book/Report/Conference proceedingConference contribution

41 Downloads (Pure)

Abstract

We present novel techniques for neuro-symbolic concurrent stochastic games, a recently proposed modelling formalism to represent a set of probabilistic agents operating in a continuous-space environment using a combination of neural network based perception mechanisms and traditional symbolic methods. To date, only zero-sum variants of the model were studied, which is too restrictive when agents have distinct objectives. We formalise notions of equilibria for these models and present algorithms to synthesise them. Focusing on the finite-horizon setting, and (global) social welfare subgame-perfect optimality, we consider two distinct types: Nash equilibria and correlated equilibria. We first show that an exact solution based on backward induction may yield arbitrarily bad equilibria. We then propose an approximation algorithm called frozen subgame improvement, which proceeds through iterative solution of nonlinear programs. We develop a prototype implementation and demonstrate the benefits of our approach on two case studies: an automated car-parking system and an aircraft collision avoidance system.
Original languageEnglish
Title of host publicationProceedings of the 38th Conference on Uncertainty in Artificial Intelligence
Subtitle of host publicationUncertainty in Artificial Intelligence, 1-5 August 2022, Eindhoven, The Netherlands
EditorsJames Cussens, Kun Zhang
PublisherProceedings of Machine Learning Research
Pages2170-2180
Number of pages11
Publication statusPublished - 28 Sept 2022
Event38th Conference on Uncertainty in Artificial Intelligence - Eindhoven, Netherlands
Duration: 1 Aug 20225 Aug 2022

Publication series

NameProceedings of Machine Learning Research
Volume180
ISSN (Electronic)2640-3498

Conference

Conference38th Conference on Uncertainty in Artificial Intelligence
Abbreviated titleUAI2022
Country/TerritoryNetherlands
CityEindhoven
Period1/08/225/08/22

Fingerprint

Dive into the research topics of 'Finite-horizon equilibria for neuro-symbolic concurrent stochastic games'. Together they form a unique fingerprint.

Cite this