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.
|Title of host publication||AAMAS '15 Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems|
|Publication status||Published - 2015|
Chen, Y., Doshi, P., & Zeng, Y. (2015). Iterative Online Planning in Multiagent Settings with Limited Model Spaces and PAC Guarantees. In AAMAS '15 Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (pp. 1161-1169). ACM.