Strategy synthesis for zero-sum neuro-symbolic concurrent stochastic games
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 gam...
| Main Authors: | , , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Elsevier
2024
|
| _version_ | 1826314327679827968 |
|---|---|
| author | Yan, R Santos, G Gethin, N Parker, D Kwiatkowska, M |
| author_facet | Yan, R Santos, G Gethin, N Parker, D Kwiatkowska, M |
| author_sort | Yan, R |
| collection | OXFORD |
| description | 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. |
| first_indexed | 2024-09-25T04:30:47Z |
| format | Journal article |
| id | oxford-uuid:ec3098e5-572d-450d-809b-6efdd6f65be7 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-09-25T04:30:47Z |
| publishDate | 2024 |
| publisher | Elsevier |
| record_format | dspace |
| spelling | oxford-uuid:ec3098e5-572d-450d-809b-6efdd6f65be72024-08-27T14:52:51ZStrategy synthesis for zero-sum neuro-symbolic concurrent stochastic gamesJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:ec3098e5-572d-450d-809b-6efdd6f65be7EnglishSymplectic ElementsElsevier2024Yan, RSantos, GGethin, NParker, DKwiatkowska, MNeuro-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. |
| spellingShingle | Yan, R Santos, G Gethin, N Parker, D Kwiatkowska, M Strategy synthesis for zero-sum neuro-symbolic concurrent stochastic games |
| title | Strategy synthesis for zero-sum neuro-symbolic concurrent stochastic games |
| title_full | Strategy synthesis for zero-sum neuro-symbolic concurrent stochastic games |
| title_fullStr | Strategy synthesis for zero-sum neuro-symbolic concurrent stochastic games |
| title_full_unstemmed | Strategy synthesis for zero-sum neuro-symbolic concurrent stochastic games |
| title_short | Strategy synthesis for zero-sum neuro-symbolic concurrent stochastic games |
| title_sort | strategy synthesis for zero sum neuro symbolic concurrent stochastic games |
| work_keys_str_mv | AT yanr strategysynthesisforzerosumneurosymbolicconcurrentstochasticgames AT santosg strategysynthesisforzerosumneurosymbolicconcurrentstochasticgames AT gethinn strategysynthesisforzerosumneurosymbolicconcurrentstochasticgames AT parkerd strategysynthesisforzerosumneurosymbolicconcurrentstochasticgames AT kwiatkowskam strategysynthesisforzerosumneurosymbolicconcurrentstochasticgames |