Strategy synthesis for zero-sum neuro-symbolic concurrent stochastic games

Journal article

Neuro-symbolic approaches to artificial intelligence, which combine neural networks with classical symbolic techniques, are growing in prominence, necessitating formal approaches to reason about their correctness. We propose a novel modelling formalism called neuro-symbolic concurrent stochastic games (NS-CSGs), which comprise two probabilistic finite-state agents interacting in a shared continuous-state environment. Each agent observes the environment using a neural perception mechanism, which converts inputs such as images into symbolic percepts, and makes decisions symbolically. We focus on the class of NS-CSGs with Borel state spaces and prove the existence and measurability of the value function for zero-sum discounted cumulative rewards under piecewise-constant restrictions. To compute values and synthesise strategies, we first introduce a Borel measurable piecewise-constant (B-PWC) representation of value functions and propose a B-PWC value iteration. Second, we introduce two novel representations for the value functions and strategies, and propose a minimax-action-free policy iteration based on alternating player choices.

Authors: Yan, R; Santos, G; Gethin, N; Parker, D; Kwiatkowska, M

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Elsevier
• Journal: Information and Computation
• Volume: 300
• Article number: 105193
• Publication date: 2024-07-25
• Acceptance date: 2024-07-09
• DOI: 10.1016/j.ic.2024.105193
• EISSN: 1090-2651
• ISSN: 0890-5401
• Language: English
• Keywords: policy iteration; neuro-symbolic systems; stochastic games; value iteration; Borel state spaces