Policy-Based Self-Competition for Planning Problems
Jonathan Pirnay Quirin Göttl Jakob Burger Dominik Gerhard Grimm
AlphaZero-type algorithms may stop improving on single-player tasks in case
the value network guiding the tree search is unable to approximate the outcome
of an episode sufficiently well. One technique to address this problem is
transforming the single-player task through self-competition. The main idea is
to compute a scalar baseline from the agent's historical performances and to
reshape an episode's reward into a binary output, indicating whether the
baseline has been exceeded or not. However, this baseline only carries limited
information for the agent about strategies how to improve. We leverage the idea
of self-competition and directly incorporate a historical policy into the
planning process instead of its scalar performance. Based on the recently
introduced Gumbel AlphaZero (GAZ), we propose our algorithm GAZ 'Play-to-Plan'
(GAZ PTP), in which the agent learns to find strong trajectories by planning
against possible strategies of its past self. We show the effectiveness of our
approach in two well-known combinatorial optimization problems, the Traveling
Salesman Problem and the Job-Shop Scheduling Problem. With only half of the
simulation budget for search, GAZ PTP consistently outperforms all selected
single-player variants of GAZ.