Individual Planning in Infinite-Horizon Multiagent Settings: Inference, Structure and Scalability
This paper provides the first formalization of self-interested planning in multiagent settings using expectation-maximization (EM). Our formalization in the context of infinite-horizon and finitely-nested interactive POMDPs (I-POMDP) is distinct from EM formulations for POMDPs and cooperative multiagent planning frameworks. We exploit the graphical model structure specific to I-POMDPs, and present a new approach based on block-coordinate descent for further speed up. Forward filtering-backward sampling -a combination of exact filtering with sampling -is explored to exploit problem structure.
This paper presents an EM method for solving interactive POMDPs (I-POMDPS), which exploits problem structure in the I-POMDP model. Specifically, an EM method for I-POMDPs is introduced, along with improvements which use block-coordinate descent and forward filtering-backward sampling. Experimental results show significant scalability gains using some of these methods. To the best of my knowledge, this is the first EM method applied to I-POMDPs. While I-POMDPs have many similarities to POMDP (and Dec-POMDPs), where EM has been used, there is additional structure in I-POMDPs in the form of models of the other agents in the problem. As such, while EM could be applied naively to I-POMDPs, more specialized methods could also be developed. Since EM methods have been shown to perform well in problems (particularly when there is significant structure), using EM to solve the very difficult (but structured) I-POMDP problems could be promising. The proposed EM method exploits the idea that a distribution over other agent actions is sufficient instead of using a distribution over models. This allows more efficient inference, but will still have scalability issues. As a result, the authors include block-coordinate descent, which is an optimization scheme that groups sets of variables and iteratively improves them. Block-coordinate descent could be used in any EM method, but the structure of the I-POMDP may be helpful to setting the blocks.The authors also introduce a forward filtering-backward sampling (FFBS) method to improve scalability. The experimental results show significantly improved performance compared to the previous method (bounded policy iteration or BPI) --- larger problems can be solved and other problems can be solved more quickly. Nevertheless, the experiments are missing some combinations of methods making it difficult to analyze the methods. Really, the authors should compare all algorithm combinations on all domains (or give a good reason why this is not possible). The authors also chose the quickest combination of methods *for each problem* to compare against BPI. This is unfair, as you wouldn't know this a priori. Also, FFBS does not perform very well, so the authors should consider additional analysis on this method or removing those results. Additional analysis concerning the experimental results would be helpful. For instance, both BPI and EM can get stuck in local optima, but BPI has the ability to escape some local optima by adding nodes. Why is it that the EM method is able to so significantly outperform BPI? Also, it is not clear how to set the blocks in block-coordinate descent or how to set the sizes for the other agent finite-state controllers. These are key features affecting the complexity and performance of the methods, so they should be discussed in more detail. The writing is understandable, but there are several typos and grammatical errors. Additional detail should be given in section 4 (computational complexity) concerning the complexity of the methods themselves. And additional EM-based methods for POMDPs should be discussed such as: H. Li, X. Liao, and L. Carin. Multi-task reinforcement learning in partially observable stochastic environments. Journal of Machine Learning Research, 10:1131-1186, 2009.