[YSN+24] Rui Yan, Gabriel Santos, Gethin Norman, David Parker and Marta Kwiatkowska. HSVI-based Online Minimax Strategies for Partially Observable Stochastic Games with Neural Perception Mechanisms. In Proc. Learning for Dynamics and Control Conference (L4DC'24), volume 242 of Proceedings of Machine Learning Research. To appear. July 2024. [pdf] [bib]
Downloads:  pdf pdf (543 KB)  bib bib
Links: [Google] [Google Scholar]
Abstract. We consider a variant of continuous-state partially-observable stochastic games with neural perception mechanisms and an asymmetric information structure. One agent has partial information, with the observation function implemented as a neural network, while the other agent is assumed to have full knowledge of the state. We present, for the first time, an efficient online method to compute an ε-minimax strategy profile, which requires only one linear program to be solved for each agent at every stage, instead of a complex estimation of opponent counterfactual values. For the partially-informed agent, we propose a continual resolving approach which uses lower bounds, pre- computed offline with heuristic search value iteration (HSVI), instead of opponent counterfactual values. This inherits the soundness of continual resolving at the cost of pre-computing the bound. For the fully-informed agent, we propose an inferred-belief strategy, where the agent maintains an inferred belief about the belief of the partially-informed agent based on (offline) upper bounds from HSVI, guaranteeing ε-distance to the value of the game at the initial belief known to both agents. Keywords: Minimax strategies, continual resolving, partially observable stochastic games.