Filtered Fictitious Play for Perturbed Observation Potential Games and Decentralised POMDPs

Archie C. Chapman, Simon Andrew Williamson, Nicholas R. JenningsUAI 2011

TL;DR

This paper introduces "Filtered Fictitious Play" (FFP), a novel algorithm that addresses the challenge of learning in multi-agent systems where observations of other agents' actions are noisy. FFP significantly improves convergence in decentralized partially observable Markov decision processes (Dec-POMDPs), outperforming state-of-the-art methods by up to 100% in noisy environments.

What Problem Does This Paper Address?

Controlling teams of autonomous agents in complex, real-world scenarios often involves decentralized decision-making under uncertainty. Two common frameworks for this are potential games (for static optimization) and Dec-POMDPs (for sequential decision-making). A key challenge in these settings is that agents rarely have perfect information about what other agents are doing. This uncertainty, often due to noisy sensors or communication, can prevent standard learning algorithms like fictitious play from converging to optimal solutions. Specifically, when agents receive inaccurate observations of their teammates' actions, their learning process can become unstable, leading to poor performance or complete failure to find a stable strategy. This paper tackles this problem by developing a robust learning algorithm that can handle such "perturbed observations."

Methods

The core contribution is the development of Filtered Fictitious Play (FFP). FFP builds upon Generalised Weakened Fictitious Play (GWFP), a standard iterative learning algorithm for games. The key innovation is the integration of a noise filtering process into GWFP's belief update mechanism. This filter aims to estimate the true actions of other agents, even when observations are noisy.

The paper first demonstrates why standard fictitious play fails in the presence of noisy observations, showing that it can prevent convergence to Nash equilibria (NE), especially for less stable ones. Then, FFP is introduced, which uses a filter (specifically, a Bayesian filter is derived for known noise models) to refine the agent's beliefs about others' actions. This filtered belief is then used in the learning update. The authors prove that FFP can converge to p-dominant Nash equilibria under certain conditions, which are more robust to noise than standard NE.

For sequential decision-making, FFP is integrated into a lookahead search algorithm called LFFP for Dec-POMDPs. LFFP uses FFP to learn about other agents' actions and track the current state of the game, enabling more accurate planning into the future.

Datasets

Not discussed in the paper. The paper uses a simulated "cooperative box pushing problem" as a benchmark Dec-POMDP.

Key Insights and Ideas

  • Noisy observations break standard learning: The paper clearly shows that even slight noise in action observations can fundamentally disrupt the convergence properties of traditional fictitious play algorithms, making them unsuitable for many real-world multi-agent systems.
  • Filtering is crucial for robustness: By explicitly modeling and filtering out observation noise, FFP can recover convergence guarantees for a broader range of Nash equilibria, including those that are critical for optimal team performance.
  • Bayesian inference as a solution: The use of Bayesian filtering, particularly when the noise model is known, provides a principled way to estimate true action frequencies from noisy observations, leading to more stable learning.
  • FFP enables effective Dec-POMDP learning: Integrating FFP into a lookahead search algorithm (LFFP) allows for robust learning in complex sequential decision-making problems with decentralized control and partial observability, outperforming existing methods.

Key Results

  • Theoretical Convergence: The paper proves that FFP can converge to p-dominant Nash equilibria in potential games with perturbed action observations, where standard GWFP fails.
  • Numerical Demonstration (UAV Game): In a simulated UAV monitoring game, FFP showed significantly higher convergence rates (82%) compared to GWFP (41%) across a range of observation noise levels. GWFP failed entirely at noise levels where FFP still performed well.
  • Dec-POMDP Performance (Box Pushing): In the cooperative box pushing Dec-POMDP, the LFFP algorithm consistently outperformed the state-of-the-art offline planner (PBPG) and a baseline GWFP-based learner (LGWFP), achieving up to 100% higher rewards across varying noise levels. LFFP demonstrated remarkable resilience to noise.

Limitations and Future Work

  • High Noise Levels: While FFP is robust, extremely high levels of observation noise can still prevent convergence, as there is simply too little information to infer anything meaningful.
  • Mixed Equilibria: The paper notes that while FFP is proven to converge to pure NE, its sufficiency for convergence to mixed NE is still an open question.
  • Learning Game Structure: Future work could explore relaxing the assumption that agents know the utility and transition functions of the underlying POSG. Instead, agents could learn this structure alongside their policies.
  • Complexity Analysis: Further analysis of the convergence and computational complexity of LFFP is planned.

Summary updated

BibTeX
@inproceedings{chapman2011filtered,
  author = {Archie C. Chapman and Simon Andrew Williamson and Nicholas R. Jennings},
  title = {{Filtered Fictitious Play for Perturbed Observation Potential Games and Decentralised POMDPs}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2011},
}
Figure