Optimize Neural Fictitious Self-Play in Regret Minimization Thinking
This work addresses a specific optimization problem in game theory algorithms for researchers in AI and game playing, representing an incremental improvement.
The paper tackled the optimality gap in Neural Fictitious Self-Play (NFSP) for learning Nash Equilibrium in imperfect information games by replacing its best response computation with regret matching, resulting in faster convergence and better performance than original NFSP in experiments on OpenSpiel environments.
Optimization of deep learning algorithms to approach Nash Equilibrium remains a significant problem in imperfect information games, e.g. StarCraft and poker. Neural Fictitious Self-Play (NFSP) has provided an effective way to learn approximate Nash Equilibrium without prior domain knowledge in imperfect information games. However, optimality gap was left as an optimization problem of NFSP and by solving the problem, the performance of NFSP could be improved. In this study, focusing on the optimality gap of NFSP, we have proposed a new method replacing NFSP's best response computation with regret matching method. The new algorithm can make the optimality gap converge to zero as it iterates, thus converge faster than original NFSP. We have conduct experiments on three typical environments of perfect-information games and imperfect information games in OpenSpiel and all showed that our new algorithm performances better than original NFSP.