Ranked Reward: Enabling Self-Play Reinforcement Learning for Combinatorial Optimization

Abstract

Adversarial self-play in two-player games has delivered impressive results when used with reinforcement learning algorithms that combine deep neural networks and tree search. Algorithms like AlphaZero and Expert Iteration learn tabula-rasa, producing highly informative training data on the fly. However, the self-play training strategy is not directly applicable to single-player games. Recently, several practically important combinatorial optimisation problems, such as the travelling salesman problem and the bin packing problem, have been reformulated as reinforcement learning problems, increasing the importance of enabling the benefits of self-play beyond two-player games. We present the Ranked Reward (R2) algorithm which accomplishes this by ranking the rewards obtained by a single agent over multiple games to create a relative performance metric. Results from applying the R2 algorithm to instances of a two-dimensional and three-dimensional bin packing problems show that it outperforms generic Monte Carlo tree search, heuristic algorithms and integer programming solvers. We also present an analysis of the ranked reward mechanism, in particular, the effects of problem instances with varying difficulty and different ranking thresholds.

References in corpus (8)

• Adam: A Method for Stochastic Optimization
• Deep Learning in Neural Networks: An Overview
• Deep Residual Learning for Image Recognition
• Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm
• Thinking Fast and Slow with Deep Learning and Tree Search
• Emergent Complexity via Multi-Agent Competition
• Solving a New 3D Bin Packing Problem with Deep Reinforcement Learning Method
• A0C: Alpha Zero in Continuous Action Space

Cited by in corpus (12)

• Learning Compositional Neural Programs with Recursive Tree Search and Planning
• Attend2Pack: Bin Packing through Deep Reinforcement Learning with Attention
• Online 3D Bin Packing with Constrained Deep Reinforcement Learning
• A Generalized Reinforcement Learning Algorithm for Online 3D Bin-Packing
• Deep Model-Based Reinforcement Learning for High-Dimensional Problems, a Survey
• Learning Practically Feasible Policies for Online 3D Bin Packing
• First-Order Problem Solving through Neural MCTS based Reinforcement Learning
• Self-play Learning Strategies for Resource Assignment in Open-RAN Networks
• Reinforcement Learning Enhanced Quantum-inspired Algorithm for Combinatorial Optimization
• A* Search Without Expansions: Learning Heuristic Functions with Deep Q-Networks
• Single-Agent Optimization Through Policy Iteration Using Monte-Carlo Tree Search
• Self-Play Learning Without a Reward Metric