# Anticipating Oblivious Opponents in Stochastic Games

arXiv: https://arxiv.org/abs/2409.11671 · HTML: https://mlsanity.com/paper/2409.11671/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 49 references that are in the map.
- First posted on arXiv 18 Sep 2024.

## Builds on (most cited first, 9 of 9)

- [The Complexity of Decentralized Control of Markov Decision Processes](https://mlsanity.com/paper/1301.3836/) (2013)
- [The IKEA ASM Dataset: Understanding People Assembling Furniture through Actions, Objects and Pose](https://mlsanity.com/paper/2007.00394/) (2020)
- [Approximate information state for approximate planning and reinforcement learning in partially observed systems](https://mlsanity.com/paper/2010.08843/) (2020)
- [Solving POMDPs by Searching the Space of Finite Policies](https://mlsanity.com/paper/1301.6720/) (2013)
- [Learning Finite-State Controllers for Partially Observable Environments](https://mlsanity.com/paper/1301.6721/) (2013)
- [Predictive Runtime Monitoring for Mobile Robots using Logic-Based Bayesian Intent Inference](https://mlsanity.com/paper/2108.01227/) (2021)
- [Sparse tree search optimality guarantees in POMDPs with continuous observation spaces](https://mlsanity.com/paper/1910.04332/) (2019)
- [Compact Representation of Value Function in Partially Observable Stochastic Games](https://mlsanity.com/paper/1903.05511/) (2019)
- [Probabilistic Bisimulation: Naturally on Distributions](https://mlsanity.com/paper/1404.5084/) (2014)

## Abstract (arXiv)

We present an approach for systematically anticipating the actions and policies employed by oblivious environments in concurrent stochastic games, while maximizing a reward function. Our main contribution lies in the synthesis of a finite information state machine whose alphabet ranges over the actions of the environment. Each state of the automaton is mapped to a belief state about the policy used by the environment. We introduce a notion of consistency that guarantees that the belief states tracked by our automaton stays within a fixed distance of the precise belief state obtained by knowledge of the full history. We provide methods for checking consistency of an automaton and a synthesis approach which upon successful termination yields such a machine. We show how the information state machine yields an MDP that serves as the starting point for computing optimal policies for maximizing a reward function defined over plays. We present an experimental evaluation over benchmark examples including human activity data for tasks such as cataract surgery and furniture assembly, wherein our approach successfully anticipates the policies and actions of the environment in order to maximize the reward.