Evolutionary Reinforcement Learning with Action Sequence search for Imperfect Information Games

Deep Reinforcement Learning (DRL) has achieved remarkable success in perfect information games. However, when applied to imperfect information games like Contract Bridge, DRL faces challenges not only from unobservable partial information but also from the lack of efficient exploration. Although several Evolutionary Reinforcement Learning algorithms (ERLs) have harnessed Evolutionary Algorithms (EAs) to enhance exploration capabilities, the practical performance of EAs is limited either by the high-dimensional parameter space or possibly inaccurate guidance from value networks. In this paper, we introduce a novel ERL algorithm that employs the Particle Swarm Optimization (PSO) algorithm to search for superior action sequences, thereby aiding agents in exploring uncharted territory. We conduct the search in action space and evaluate action sequences through interactions with the environment to avoid the limitations of parameter space and value networks, respectively. The diverse experiences collected in the search and evaluation can boost the learning of the DRL agent. In addition, the action sequence search is executed only when the agent converges to local optima, which can reduce the overall cost of action evaluation and avoid influencing the optimization process of DRL. Through experimental comparisons conducted on Contract Bridge, our method demonstrates superior performance when compared with several state-of-the-art DRL and ERL algorithms. Furthermore, we utilize our method in the Bridge Competition of AAMAS 2023 Imperfect Information Card Games Competition and rank the first.

Keywords
Evolutionary Algorithm, Reinforcement Learning, Evolutionary Reinforcement Learning, Imperfect Information Game.

Autores:

Carlos Artemio Coello Coello.

Revista

Information Sciences.

DOI: https://doi.org/10.1016/j.ins.2024.120804