A Sufficient Statistic for Influence in Structured Multiagent Environments
arXiv:1907.09278 · doi:10.1613/jair.1.12136
Abstract
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.
References in corpus (22)
- An Introduction to Deep Reinforcement Learning
- Recent Trends in Deep Learning Based Natural Language Processing
- Decision-Theoretic Planning: Structural Assumptions and Computational Leverage
- Tractable Inference for Complex Stochastic Processes
- Stabilising Experience Replay for Deep Multi-Agent Reinforcement Learning
- SPUDD: Stochastic Planning using Decision Diagrams
- QMIX: Monotonic Value Function Factorisation for Deep Multi-Agent Reinforcement Learning
- Social Influence as Intrinsic Motivation for Multi-Agent Deep Reinforcement Learning
- QTRAN: Learning to Factorize with Transformation for Cooperative Multi-Agent Reinforcement Learning
- Learning Finite-State Controllers for Partially Observable Environments
- Near Optimal Behavior via Approximate State Abstraction
- Model Reduction Techniques for Computing Approximately Optimal Solutions for Markov Decision Processes
- A Laplacian Framework for Option Discovery in Reinforcement Learning
- DeepMDP: Learning Continuous Latent Space Models for Representation Learning
- Distributed Planning in Hierarchical Factored MDPs
- Relational Forward Models for Multi-Agent Learning
- Efficient Model-Based Deep Reinforcement Learning with Variational State Tabulation
- An Algorithm for Finding Minimum d-Separating Sets in Belief Networks
- A Deep Policy Inference Q-Network for Multi-Agent Systems
- Learning Compact Models for Planning with Exogenous Processes
- Influence-Optimistic Local Values for Multiagent Planning --- Extended Version
- Influence-Augmented Online Planning for Complex Environments