Interactive Learning and Decision Making: Foundations, Insights & Challenges

Frans A. OliehoekIJCAI 2018 · DOI

TL;DR

This paper provides a comprehensive overview of Interactive Learning and Decision Making (ILDM), a field focused on designing intelligent agents that can learn and coordinate in complex, uncertain environments. It lays out the foundational frameworks, key insights, and significant challenges in this area, emphasizing the need for principled approaches to handle uncertainty and decentralization.

What Problem Does This Paper Address?

The core problem this paper addresses is the design of intelligent agents, particularly teams of agents, that can effectively learn and coordinate their actions in dynamic and uncertain environments. This is crucial for AI systems that need to operate in real-world scenarios, where perfect information is rare, and other agents (human or artificial) are present. The paper highlights several sources of uncertainty: outcome uncertainty (actions don't always have predictable effects), state uncertainty (agents have incomplete information about the environment), and agent uncertainty (agents don't know what other agents will do). Traditional AI approaches often struggle with these challenges, especially when dealing with multiple agents that need to make decisions in a decentralized manner.

Methods

The paper introduces and discusses several key frameworks and methods for tackling ILDM:

  • Decentralized Partially Observable Markov Decision Processes (Dec-POMDPs): This is presented as a general framework for formalizing decision-making problems for teams of agents under uncertainty. It captures outcome and state uncertainty, and the decentralized nature of agent decision-making.
  • Planning: When a complete model of the environment is available, the problem becomes planning. The paper discusses how to compute optimal policies, but notes the inherent complexity of Dec-POMDPs, suggesting the need for approximate solutions and heuristics.
  • Learning (Reinforcement Learning): When the environment model is incomplete or inaccurate, agents must learn through interaction. The paper frames this within the context of Partially Observable Reinforcement Learning (PORL) and its multiagent extensions.
  • Factored Value Functions: To address the exponential complexity of representing value functions in multiagent systems, factored representations are introduced. These decompose the value function into smaller, manageable components, often leveraging structure in the problem.
  • Transfer Planning (TP): This approach uses "source problems" to compute components of value functions, which are then transferred to a larger "target task." This allows for more efficient planning by leveraging solutions from simpler, related problems.
  • Influence-Based Abstraction: This concept aims to simplify complex multiagent interactions by focusing on the "influence" one agent's policy has on another, rather than the full policy itself. This can lead to more efficient search and better understanding of coordination.
  • Subjective Approximation: This involves reasoning from the perspective of a single agent, simplifying the problem by focusing on what is relevant to that agent.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The "objective" vs. "subjective" perspective: The paper distinguishes between formalizing the entire multiagent system (objective) and modeling other agents as part of a single agent's environment (subjective). Both have their place in ILDM.
  • Complexity of Dec-POMDPs is inherent to the problem, not just the model: The authors argue that the difficulty of solving problems with state uncertainty and decentralization is fundamental, and frameworks like Dec-POMDPs are necessary to capture this complexity, even if they are computationally challenging.
  • Decentralization profoundly impacts complexity: The need for individual agents to make decisions based on their own limited observations and histories, rather than a global state, is a key driver of computational difficulty.
  • Abstraction and factorization are crucial for scalability: To make progress on complex ILDM problems, researchers must develop methods that exploit structure, factorize representations, and create abstractions to reduce the computational burden.
  • Value function factorization is a powerful tool: Decomposing value functions into smaller, more manageable parts is a key strategy for handling the combinatorial explosion in multiagent systems.
  • Influence-based abstraction offers a new way to simplify interactions: By focusing on how agents influence each other, rather than their exact policies, significant computational gains can be achieved.

Key Results

The paper is primarily a survey and conceptual overview, rather than a presentation of specific empirical results. However, it highlights the following:

  • Theoretical results on Dec-POMDP complexity: The paper references results showing Dec-POMDPs are provably intractable (NEXP-complete).
  • Scalability improvements through approximation methods: Techniques like factored value functions and transfer planning have led to significant increases in the scalability of approximation methods for Dec-POMDPs.
  • Effectiveness of influence-based abstraction: This approach has been shown to be useful for efficiently searching for joint policies and providing factored upper bounds on value functions, even for problems with hundreds of agents. For example, it was used to show that a transfer planning solution for a 50-agent benchmark was essentially optimal.

Limitations and Future Work

  • Scalability remains a central challenge: Despite advances, providing scalability for ILDM problems is an ongoing and significant challenge.
  • Truly Decentralized RL: While progress is being made in multiagent RL, many approaches still rely on centralized training or require all agents to observe global rewards, which is often impractical in real-world decentralized settings.
  • Learning Models of Other Agents: A grand challenge is developing methods to learn models of other agents' behavior, which is crucial for effective interaction and coordination.
  • Understanding Interactive Learning: The paper points to the need for a deeper theoretical understanding of interactive learning, particularly in the context of competing networks (like GANs) and how to avoid local Nash equilibria.
  • Benchmark Tasks and Shareable Models: The authors suggest that progress in learning models of agent behavior will require benchmark tasks and shared models, similar to the impact of ImageNet in computer vision.
  • Making approaches more scalable: While Bayes Adaptive POMDPs offer a principled approach to learning and planning, making them more scalable is a key area for future research.

Summary updated

BibTeX
@inproceedings{oliehoek2018interactive,
  author = {Frans A. Oliehoek},
  title = {{Interactive Learning and Decision Making: Foundations, Insights \& Challenges}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/813},
}
Figure