Introduction
In the field of cooperative AI, "ad hoc teamwork" represents a significant challenge: how can an agent collaborate effectively with a teammate it has never encountered before? This problem is particularly acute in natural language games like Codenames, where agents must navigate differences in both semantics (how words are defined) and pragmatics (how those definitions are used to communicate intent).
Most existing AI agents for these tasks are static, assuming their partners share their exact internal world model. However, if a Spymaster associates "Apple" with "Fruit" while a Guesser associates it with "Technology," the team is likely to fail. This research introduces a Bayesian framework that allows agents to treat their partner's identity as a latent variable to be inferred during gameplay, enabling dynamic adaptation to unique communication styles.
Methodology
The proposed framework combines two core probabilistic mechanisms to facilitate cooperation:
- Bayesian Inference: Agents maintain a "prior" distribution over a set of possible models their partner might be using. As the game progresses and the partner makes moves, the agent applies Bayes’ Rule to update its beliefs, narrowing down the likely language model or strategy in use.
- Cognitive Hierarchy (k-level reasoning): This approach models agents at varying levels of sophistication. A Level-0 agent is basic and static, while a Level-1 agent acts as a "best response" to a Level-0 partner, and so on. This allows for more nuanced strategic interactions.
Agent Configurations and Stochasticity
A critical innovation in this work is the introduction of stochasticity via Gaussian noise added to word embeddings. This ensures that every possible action has a non-zero probability, preventing the Bayesian update from failing when a partner performs an unexpected action.
As shown in the agent definitions above, the researchers tested various configurations of Spymasters ($S$) and Guessers ($D, B, X$), with tilde-marked versions ($\tilde{S}, \tilde{D}$, etc.) representing agents utilizing stochastic noise to bridge the gap with unknown partners.
Experimental Setup
The framework was evaluated using a variety of word embedding models as proxies for different vocabularies. "Internal" models (known to the agent) included Word2Vec, GloVe (300d), ConceptNet Numberbatch, and Dict2Vec. To test robustness, "Out-of-Distribution" (OOD) models like FastText and ELMo were used for teammates, representing unknown vocabularies.
Key Results and Discussion
The experiments demonstrated that Bayesian agents prioritize robustness over narrow optimality. While a static agent might perform perfectly with a known partner, it fails in diverse populations. In contrast, the Bayesian Spymaster with noise ($\tilde{S}$) significantly outperformed static benchmarks when paired with unknown (OOD) teammates.
As detailed in the results table, in deterministic environments with OOD guessers, the Bayesian Spymaster with noise achieved a win rate of 0.872, compared to 0.718 for the best-performing static model. In stochastic (noisy) environments, the advantage was even more pronounced, with the Bayesian agent maintaining a 0.625 win rate while the best static model plummeted to 0.468.
Strategic Insights
- Assassin Avoidance: Bayesian Spymasters are better at avoiding "assassin" cards because they consider multiple interpretations of a clue, identifying words that might be safe for one model but dangerous for another.
- Information Asymmetry: Spymasters generally learn their Guesser's model faster than vice versa, as a single clue word provides a denser signal of intent than a constrained board guess.
- The Role of Noise: Adding noise was not merely a mathematical necessity; it improved performance with OOD partners by allowing the agent to model behaviors not explicitly present in its internal library.
Conclusion
By treating the partner's model as a variable to be inferred, Bayesian agents can rapidly adapt to the semantics of unknown teammates. While computationally more intensive than static models, this approach offers a path toward more flexible and human-like cooperation in complex language-based tasks. Future work will look toward scaling these cognitive hierarchies and testing the framework against the more complex pragmatics of human players.
Summary updated