Optimal sequential planning in partially observable multiagent settings

We develop a new decision-theoretic framework called interactive POMDP (I-POMDP) for sequential optimality of an autonomous agent interacting with other agents within a common, and possibly uncertain, environment. I-POMDPs are applicable to self-interested agents who locally compute their actions to optimize their preferences given what they believe while interacting with others with possibly conflicting objectives. I-POMDPs replace the "flat" beliefs of POMDPs with nested hierarchical belief systems. Our approach of using a decision-theoretic framework and solution concept complements the equilibrium approach of analyzing interactions, as used in classical game theory. Specifically, we avoid the difficulties of non-uniqueness and incompleteness of the traditional Nash equilibrium approach, and offer solutions which are likely to be better than the solutions obtained from applying traditional POMDPs to multiagent settings.; Analogous to POMDPs, I-POMDPs also suffer from two sources of intractability: The complexity of the belief representation, sometimes called the curse of dimensionality, and the complexity of the policy space, also called the curse of history. To address the curse of dimensionality, we generalize the particle filter, specifically, the bootstrap filter, to the multiagent setting, resulting in the interactive particle filter (I-PF). Mirroring the hierarchical character of interactive beliefs, the I-PF involves sampling and propagation at each of the hierarchical levels of beliefs. To mitigate the curse of history, we present a complementary method based on sampling observations while building the reachability tree during value iteration.; We theoretically analyze the interactions between agents participating in the infinite horizon partially observable stochastic game as formalized within the I-POMDP framework. Under the assumption of truth compatibility of the agents' prior beliefs, we show that their behavior converges to the subjective equilibrium. In trying to empirically validate the existence of subjective equilibrium, we run into obstacles. The difficulties arise because we are unable to guarantee the satisfiability of the truth compatibility condition, in practice. We believe that these computational obstacles also signify a serious impediment to adopting equilibrium as a solution concept for multiagent planning.