Abstract

Interactive POMDPs (I-POMDPs) generalize POMDPs to multi-agent domains by modeling other agents' beliefs, capabilities, and preferences as part of the interactive state space. Agents in this framework have the ability to maintain and update beliefs about not only the physical environment, but also about other agents so as to predict their behavior. Because beliefs in I-POMDPs are structured nested and the space of models grows exponentially with the number of time steps, it is difficult to compute the optimal solution. For finite horizons the complexity of solving I-POMDPs is PSPACE-hard. In this paper, we try to find the relation between complexity of I-POMDPs and the Shannon entropy. We use block entropy, entropy rate and other definitions as tools to quantify the complexity of I-POMDPs. Then compute these measurements by playing tiger games using three different strategies. Experiments show that our measurements work well and comparing to POMDPs, the complexity of I-POMDPs is much higher.

Paper Details