Can Meta-Interpretive Learning outperform Deep Reinforcement Learning of Evaluable Game strategies?

Céline HocquetteIJCAI 2019 · DOI

TL;DR

This paper introduces MIGO, a novel Meta-Interpretive Learning system for learning optimal strategies in two-player games. MIGO outperforms Deep Reinforcement Learning (DRL) methods in terms of cumulative minimax regret on simple games like Noughts-and-Crosses and Hexapawn, while also producing more interpretable, symbolic strategies that demonstrate strong transfer learning capabilities.

What Problem Does This Paper Address?

Deep Reinforcement Learning (DRL) has achieved remarkable success in mastering complex games like Go and Chess, often surpassing human players. However, DRL systems face several challenges: they typically require massive amounts of training data, their learned strategies are often opaque "black boxes" lacking interpretability, and they struggle with transferring learned knowledge to new games. Evaluating the performance of these systems is also difficult, as metrics like minimax regret are computationally intractable for complex games. This paper addresses these limitations by proposing a new approach based on Meta-Interpretive Learning (MIL) to learn game strategies that are not only effective but also interpretable and transferable, using simpler games where performance can be rigorously evaluated.

Methods

The core of this work is the MIGO (Meta-Interpretive Game Ordinator) system, built upon the Meta-Interpretive Learning (MIL) framework. MIL is a type of Inductive Logic Programming (ILP) that supports predicate invention and learning recursive programs. MIGO leverages a strong inductive bias, allowing it to learn from a limited number of examples.

Key methodological aspects include:

  • Symbolic Representation: Strategies are learned as symbolic logic programs, making them inherently interpretable.
  • Meta-Interpretive Learning (MIL): MIGO uses an adapted Prolog meta-interpreter to learn hypotheses (strategies) from examples and background knowledge.
  • Dependent Learning: MIGO learns predicates incrementally, building more complex definitions from simpler ones. For instance, it first learns to win in one move (win_1/1) and then uses that to learn to win in two moves (win_2/1).
  • Credit Assignment: The paper introduces theoretical frameworks (Theorems 3.2 and 3.3) to assign positive examples for learning winning and drawing strategies, particularly when the opponent plays optimally. This allows learning from positive examples only.
  • Game Evaluation: Minimax regret is used as the primary evaluation metric. To make this tractable, the experiments are conducted on simpler games (Noughts-and-Crosses, Hexapawn) and games are started from specific initial board positions to ensure a range of outcomes.
  • Two Variants of MIGO:
    • Separated Learning: win/2 and draw/2 predicates are learned sequentially.
  • Mixed Learning: win/2 and draw/2 are learned simultaneously, with draw/2 examples being re-evaluated as the win/2 strategy improves. Mixed learning is found to be more effective.

Datasets

The paper uses two evaluable games for experiments:

  • Noughts-and-Crosses: A standard tic-tac-toe game.
  • Hexapawn: A simpler game played on a 3x3 or 4x4 board. The paper refers to Hexapawn3 and Hexapawn4 for these variants.

The "datasets" are generated through game play. Initial boards are sampled from positions that are one full move ahead, ensuring a variety of starting conditions. The learning process involves playing games and using the outcomes to generate positive examples for the learning system.

Key Insights and Ideas

  • Symbolic Strategies Outperform DRL: MIGO, a symbolic learning system, achieves lower cumulative minimax regret than both standard and deep reinforcement learning methods on simple games. This suggests that symbolic representations and inductive biases can be more sample-efficient and effective for certain tasks.
  • Interpretability Matters: The learned strategies from MIGO are presented as logic programs, which are relatively easy for humans to comprehend. This contrasts sharply with the opaque nature of DRL policies.
  • Transfer Learning is Powerful: MIGO demonstrates significant transfer learning capabilities, where strategies learned for a simpler game (e.g., Hexapawn3) can be effectively transferred to a more complex game (e.g., Hexapawn4), leading to faster convergence.
  • Theoretical Foundation for Learning: The paper provides theoretical grounding for learning from positive examples in game playing, which is crucial for MIL systems that might struggle with negative examples.
  • Mixed Learning Advantage: The mixed learning approach, where win and draw strategies are learned concurrently, proves more effective than learning them separately.

Key Results

  • Performance: MIGO consistently achieves lower cumulative minimax regret than MENACE/HER, Q-Learning, and Deep Q-Learning on both Noughts-and-Crosses and Hexapawn3. This refutes the first null hypothesis that MIGO cannot converge faster.
  • Convergence Speed: MIGO converges significantly faster than the tested RL systems.
  • Transfer Learning: Strategies learned for Hexapawn3 can be effectively transferred to Hexapawn4, leading to improved performance compared to learning from scratch (refuting the second null hypothesis).
  • Interpretability: The learned rules are presented as examples (Table 3), demonstrating a clear, rule-based structure that explains winning and drawing conditions.
  • Running Time: While MIGO's learning time is competitive, the execution time of learned strategies can increase rapidly with state dimensions, indicating a potential scalability issue.

Limitations and Future Work

  • Scalability: The execution time of learned strategies increases with the complexity of the game state, limiting scalability to very large games. Future work aims to optimize execution time and explore hypothesis selection methods.
  • Over-generalization: The paper acknowledges a risk of over-generalization due to learning from positive examples only. Future work will explore more robust methods for learning from positive examples.
  • Optimal Opponent Assumption: The current system relies on an optimal opponent, which is intractable for larger games. Future work plans to relax this assumption, potentially by learning from self-play.
  • Sample Complexity: While MIGO is more sample-efficient than DRL, many examples are still "wasted" as they cannot be attributed labels. Investigating active learning strategies is proposed to further reduce sample complexity.
  • Comprehensibility: While MIGO's strategies are more interpretable than DRL, further study is needed to evaluate the comprehensibility of learned strategies.

Summary updated

BibTeX
@inproceedings{hocquette2019can,
  author = {Céline Hocquette},
  title = {{Can Meta-Interpretive Learning outperform Deep Reinforcement Learning of Evaluable Game strategies?}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/909},
}
Figure