We develop new graphical representations for the problem of sequential decision making in partially observable
multiagent environments, as formalized by interactive partially observable Markov decision processes (I-POMDPs). The graphical models
called
interactive influence diagrams (I-IDs) and their dynamic counterparts,
interactive dynamic influence diagrams (I-DIDs), seek to explicitly model the structure that is often present in real-world problems by decomposing the situation into chance
and decision variables, and the dependencies between the variables. I-DIDs generalize DIDs, which may be viewed as graphical
representations of POMDPs, to multiagent settings in the same way that I-POMDPs generalize POMDPs. I-DIDs may be used to compute
the policy of an agent given its belief as the agent acts and observes in a setting that is populated by other interacting
agents. Using several examples, we show how I-IDs and I-DIDs may be applied and demonstrate their usefulness. We also show
how the models may be solved using the standard algorithms that are applicable to DIDs. Solving I-DIDs exactly involves knowing
the solutions of possible models of the other agents. The space of models grows exponentially with the number of time steps.
We present a method of solving I-DIDs approximately by limiting the number of other agents’ candidate models at each time
step to a constant. We do this by clustering models that are likely to be behaviorally equivalent and selecting a representative
set from the clusters. We discuss the error bound of the approximation technique and demonstrate its empirical performance.
Keywords Probabilistic graphical models - Interactive POMDPs - Sequential multiagent decision making