HSVI-based Online Minimax Strategies for Partially Observable Stochastic Games with Neural Perception Mechanisms
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 $\varepsilon$-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 $\varepsilon$-distance to the value of the game at the initial belief known to both agents.
Code (0)
등록된 구현이 없습니다.
Tasks
counterfactualHeuristic SearchSimilar Papers 제목 키워드 기반
HSVI can solve zero-sum Partially Observable Stochastic Games
State-of-the-art methods for solving 2-player zero-sum imperfect information games rely on linear programming or regret minimization, though not on dynamic programming (DP) or heuristic search (HS), while the latter are …
Decision MakingHeuristic SearchOpen-Ended Question AnsweringSequential Decision MakingHSVI for zs-POSGs using Concavity, Convexity and Lipschitz Properties
Dynamic programming and heuristic search are at the core of state-of-the-art solvers for sequential decision-making problems. In partially observable or collaborative settings (\eg, POMDPs and Dec-POMDPs), this requires …
Decision MakingHeuristic SearchSequential Decision MakingPartially Observable Stochastic Games with Neural Perception Mechanisms
Stochastic games are a well established model for multi-agent sequential decision making under uncertainty. In practical applications, though, agents often have only partial observability of their environment. Furthermor…
Decision MakingDecision Making Under UncertaintySequential Decision Makingrho-POMDPs have Lipschitz-Continuous epsilon-Optimal Value Functions
Many state-of-the-art algorithms for solving Partially Observable Markov Decision Processes (POMDPs) rely on turning the problem into a “fully observable” problem—a belief MDP—and exploiting the piece-wise linearity and …
On Bellman's Optimality Principle for zs-POSGs
Many non-trivial sequential decision-making problems are efficiently solved by relying on Bellman's optimality principle, i.e., exploiting the fact that sub-problems are nested recursively within the original problem. He…
Decision MakingHeuristic SearchSequential Decision Making