Iterative Online Planning in Multiagent Settings with Limited Model Spaces and PAC Guarantees

Methods for planning in multiagent settings often model other agents’ possible behaviors. However, the space of these models – whether these are policy trees, finite-state controllers or intentional models – is very large and thus arbitrarily bounded. This may exclude the true model or the optimal model. In this paper, we present a novel iterative algorithm for online planning that considers a limited model space, updates it dynamically using data from interactions, and provides a provable and probabilistic bound on the approximation error. We ground this approach in the context of graphical models for planning in partially observable multiagent settings – interactive dynamic influence diagrams. We empirically demonstrate that the limited model space facilitates fast solutions and that the true model often enters the limited model space.