Multi-Agent Systems of Inverse Reinforcement Learners in Complex Games

Dave MobleyIJCAI 2017 · DOI

TL;DR

This paper proposes a novel approach to train intelligent agents in complex games by decomposing the problem into smaller, manageable sub-tasks. By leveraging Inverse Reinforcement Learning (IRL) and Hierarchical Task Networks (HTNs), the system learns to infer expert goals and rewards, enabling agents to tackle intricate environments with vast state spaces more efficiently.

What Problem Does This Paper Address?

Training intelligent agents to solve real-world problems, such as driving or managing a business, is incredibly challenging due to the sheer number of features that define the state space. As the number of features grows, the problem size explodes, leading to the "Curse of Dimensionality" where exponentially more data is needed for effective training. This makes traditional Reinforcement Learning (RL) approaches intractable. Furthermore, in many complex scenarios, defining explicit reward functions for every action and goal is difficult or even impossible. This paper tackles the challenge of learning effective policies in these high-dimensional, complex environments where explicit reward engineering is not feasible.

Methods

The core of the proposed research lies in task-based RL and Inverse Reinforcement Learning (IRL). Instead of trying to learn a single, monolithic policy for the entire complex problem, the authors advocate for decomposing the problem into smaller, independent sub-tasks. Each sub-task is trained using only the features necessary to solve it.

Key techniques include:

  • Inverse Reinforcement Learning (IRL): This is crucial when explicit reward functions are unknown. IRL infers the underlying reward function from expert demonstrations. The paper suggests using expert policies as a starting point to learn these rewards.
  • Hierarchical Task Networks (HTNs): This approach is used to structure the problem decomposition. HTNs allow for the representation of complex tasks as a hierarchy of simpler sub-tasks. This decomposition helps manage the complexity of the state space.
  • Multi-Agent Systems: The paper acknowledges the competitive nature of complex games and suggests considering adversary actions as part of the state/action transition, potentially using minimax strategies with Q-learning.
  • Deep RL Algorithms: While not explicitly detailed for the proposed method, the paper mentions Deep Q Networks (DQNs) as a potential tool for learning navigation in sub-tasks where rewards can be generated without an expert.

The novelty lies in the combination of HTNs for decomposition and IRL for reward inference, allowing sub-tasks to be solved independently and their learned rewards to be funneled up to a higher-level agent. This approach aims to ease the data requirements and computational burden of training agents in complex environments.

Datasets

Not discussed in the paper. The paper focuses on the methodology and proposes using complex games as benchmarks, specifically mentioning:

  • Text-based RPGs (MUDs): Described as gridworld-like games with quests and primary goals.
  • Graphical RPGs (Pirate101): A first-person RPG with similar tasks but more varied and nuanced environments.

The paper suggests using expert demonstrations from these games to train the learners.

Key Insights and Ideas

  • Decomposition is Key: Tackling complex problems by breaking them into smaller, feature-specific sub-tasks significantly reduces the complexity and data requirements compared to monolithic approaches.
  • IRL for Implicit Goals: When explicit reward functions are hard to define, IRL provides a powerful mechanism to infer expert intentions and goals from their behavior.
  • Hierarchical Learning for Scalability: HTNs offer a structured way to manage the hierarchy of tasks, allowing a higher-level agent to focus on strategic goals while lower-level agents handle specific sub-tasks.
  • Apprenticeship Learning: Learning from expert demonstrations (apprenticeship learning) is a viable strategy for teaching agents complex behaviors and inferring their underlying objectives.
  • Human-Level Competency as a Baseline: The goal is not necessarily to achieve superhuman performance immediately, but to reach human-level competency as a starting point, with continuous improvement over time.

Key Results

Not discussed in the paper. The paper outlines a proposed research direction and methodology rather than presenting empirical results from trained agents. It focuses on the theoretical framework and the potential benefits of the proposed approach.

Limitations and Future Work

  • Computational Complexity of IRL: While IRL helps with reward definition, the process of inferring rewards can still be computationally intensive, especially in complex state spaces.
  • Expert Data Sparsity: The paper acknowledges that for rare game states, expert policies might not exhibit choices, leading to data sparsity for those specific situations.
  • Defining Sub-task Boundaries: Determining the optimal way to decompose a complex problem into sub-tasks and defining their boundaries is a challenge.
  • Future Work: The authors suggest exploring the use of Hierarchical Task Networks (HTNs) in combination with IRL tasks to demonstrate how MDPs can be decomposed and solved independently. They also propose training systems using multiple experts to establish a consensus on goals and rewards, which can then be used to train a new reinforcement learner. The goal is to monotonically improve reward estimates and goals, ultimately converging on knowledge of goals and rewards.

Summary updated

BibTeX
@inproceedings{mobley2017multi,
  author = {Dave Mobley},
  title = {{Multi-Agent Systems of Inverse Reinforcement Learners in Complex Games}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/755},
}
Figure