  Making decisions in complex environments is a key challenge in artificial
intelligence (AI). Situations involving multiple decision makers are
particularly complex, leading to computational intractability of principled
solution methods. A body of work in AI has tried to mitigate this problem by
trying to distill interaction to its essence: how does the policy of one agent
influence another agent? If we can find more compact representations of such
influence, this can help us deal with the complexity, for instance by searching
the space of influences rather than the space of policies. However, so far
these notions of influence have been restricted in their applicability to
special cases of interaction. In this paper we formalize influence-based
abstraction (IBA), which facilitates the elimination of latent state factors
without any loss in value, for a very general class of problems described as
factored partially observable stochastic games (fPOSGs). On the one hand, this
generalizes existing descriptions of influence, and thus can serve as the
foundation for improvements in scalability and other insights in decision
making in complex multiagent settings. On the other hand, since the presence of
other agents can be seen as a generalization of single agent settings, our
formulation of IBA also provides a sufficient statistic for decision making
under abstraction for a single agent. We also give a detailed discussion of the
relations to such previous works, identifying new insights and interpretations
of these approaches. In these ways, this paper deepens our understanding of
abstraction in a wide range of sequential decision making settings, providing
the basis for new approaches and algorithms for a large class of problems.
