2025/02/07 by Mukesh Ghimire, Zhe Xu, Ghimire, Mukesh +3
Earth and Planetary Sciences · Engineering · Medicine · #Aquatic and Environmental Studies #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Guidance and Control Systems #Mathematical and Theoretical Epidemiology and Ecology Models
paper · pdf · doi:10.48550/arxiv.2502.05314
openalex publication_date 2025/02/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Unlike Poker where the action space A is discrete, differential games in the physical world often have continuous action spaces not amenable to discrete abstraction, rendering no-regret algorithms with O(|A|) complexity not scalable. To address this challenge within the scope of two-player zero-sum (2p0s) games with one-sided information, we show that (1) a computational complexity independent of |A| can be achieved by exploiting the convexification property of incomplete-information games and the Isaacs' condition that commonly holds for dynamical systems, and that (2) the computation of the two equilibrium strategies can be decoupled under one-sidedness of information. Leveraging these insights, we develop an algorithm that successfully approximates the optimal strategy in a homing game. Code available in https://github.com/ghimiremukesh/cams/tree/workshop