Learning What to Talk about in Descriptive Games

Hugo Zaragoza, Chi-Ho LiEMNLP 2005

TL;DR

This paper tackles the challenge of teaching AI agents what to say in descriptive games, where the goal is to communicate information about a game world. They propose framing this "message planning" problem as a Markov Decision Process (MDP) and using Reinforcement Learning (RL) to train optimal communication policies. A key innovation is the use of "back-off policies" to combat the state-space explosion inherent in complex environments.

What Problem Does This Paper Address?

In many text generation systems, the focus is on how to say something (sentence generation) after the topic has already been decided. However, in complex environments like computer games, deciding what to talk about is a significant challenge. There can be a vast number of objects and properties to describe, and the agent needs to select the most relevant and informative ones for the listener. This is particularly difficult when the environment is dynamic, the listener has partial knowledge, and the agent's utterances can even change the world state. The authors call these "descriptive games" and aim to develop a strategy for agents to learn optimal message content.

Methods

The core of the paper proposes framing message planning as a Markov Decision Process (MDP). This allows them to model the environment, agent knowledge, actions (both physical and communicative), and their consequences. To learn the optimal communication strategy (the "message policy"), they employ Reinforcement Learning (RL), which allows agents to learn through trial and error by interacting with the environment and receiving rewards.

A major hurdle in RL is the state dimensionality explosion, where the number of possible states becomes computationally intractable. To address this, the authors introduce back-off policies, inspired by language modeling techniques. The idea is to use a hierarchy of increasingly specific policies. The agent first tries to use the most specific policy for which it has sufficient data. If not, it "backs off" to a less specific, more general policy. This allows for more efficient learning by leveraging prior knowledge about the structure of the problem.

They illustrate this with a "Talking God" setting, where an all-knowing agent (the talker) communicates with a listener agent that can act in the environment.

Datasets

The paper does not introduce new datasets. Instead, it uses a simulated computer game environment as a benchmark for evaluating their proposed methods. The game involves a scout navigating a grid-world with objects like bombs and trees. The complexity of the environment is manipulated by introducing "noise objects" (stones) to artificially inflate the state space.

Key Insights and Ideas

  • Message Planning as an MDP: Framing the "what to talk about" problem as an MDP provides a principled way to learn optimal communication strategies, even in dynamic and reactive environments.
  • Back-off Policies for State Explosion: This is the paper's most significant contribution. By leveraging hierarchical representations and a "back-off" mechanism, they effectively mitigate the state dimensionality explosion problem, making RL feasible in complex scenarios.
  • Progressive Learning: Back-off policies lead to a natural learning progression. Agents first learn simpler communication strategies and gradually develop more complex ones as they encounter more states, making the learning process more intuitive.
  • Importance of Prior Knowledge: The effectiveness of back-off policies hinges on having prior knowledge about the domain's structure (e.g., object properties, ontologies). This knowledge is used to define the hierarchy of policies.

Key Results

The paper presents simulation results demonstrating the effectiveness of their approach.

  • In a simplified game setting, a policy that only considered object type and location achieved an average reward of approximately 400, significantly outperforming a random talking policy (average reward < -3000).
  • A policy that used all attributes (type, size, location) achieved an even higher reward (double that of the previous policy), indicating the value of richer descriptions.
  • Crucially, the back-off policy with noise objects performed comparably to the full state policy without noise objects, and significantly better than the "simple state" policy with noise. This highlights the back-off approach's ability to handle increased state complexity without sacrificing performance.
  • The back-off policy learned to use the "size" attribute only when necessary, demonstrating a nuanced and efficient communication strategy.

Limitations and Future Work

  • State Space Explosion: While back-off policies are a significant step, the paper acknowledges that for extremely large state spaces, even this approach might become unfeasible.
  • Generalization: The current work focuses on a simplified "Talking God" setting. The authors mention plans to generalize to more complex scenarios involving multiple listeners, partially observable environments (POMDPs), and agents that also take physical actions.
  • Confidence Measure: The paper uses simple visit counts as a confidence measure for back-off policies. More sophisticated confidence measures could potentially improve performance.
  • Real-world Complexity: The simulations, while demonstrating the core ideas, are still simplified. Real-world games involve more complex dynamics, communication noise, and ambiguity, which are areas for future exploration.

Summary updated

BibTeX
@inproceedings{zaragoza2005learning,
  author = {Hugo Zaragoza and Chi-Ho Li},
  title = {{Learning What to Talk about in Descriptive Games}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2005},
}
Figure