Anticipatory Fictitious Play

Abstract

Fictitious play is an algorithm for computing Nash equilibria of matrix games. Recently, machine learning variants of fictitious play have been successfully applied to complicated real-world games. This paper presents a simple modification of fictitious play which is a strict improvement over the original: it has the same theoretical worst-case convergence rate, is equally applicable in a machine learning context, and enjoys superior empirical performance. We conduct an extensive comparison of our algorithm with fictitious play, proving an optimal convergence rate for certain classes of games, demonstrating superior performance numerically across a variety of games, and concluding with experiments that extend these algorithms to the setting of deep multiagent reinforcement learning.

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keycloud2022anticipatory

Related papers

• Fictitious Play In Markov Games With Single Controller (2022)6.77
• Improving Fictitious Play Reinforcement Learning With Expanding Models (2019)0.00
• Fictitious Play In Zero-sum Stochastic Games (2020)0.00
• Provably Efficient Fictitious Play Policy Optimization For Zero-sum Markov Games With Structured Transitions (2022)0.00
• Best-response Dynamics And Fictitious Play In Identical-interest And Zero-sum Stochastic Games (2021)0.00
• Deep Reinforcement Learning From Self-play In Imperfect-information Games (2016)0.00
• Mastering Strategy Card Game (legends Of Code And Magic) Via End-to-end Policy And Optimistic Smooth Fictitious Play (2023)0.00
• Neural Auto-curricula (2021)0.00