Laterre, A;
Fu, Y;
Jabri, MK;
Cohen, A-S;
Kas, D;
Hajjar, K;
Dahl, TS;
... Beguir, K; + view all
(2018)
Ranked Reward: Enabling Self-Play Reinforcement Learning for Combinatorial Optimization.
Advances in Neural Information Processing Systems 31 (NeurIPS 2018)
Preview |
Text
1807.01672v3.pdf - Published Version Download (1MB) | Preview |
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.
| Type: | Article |
|---|---|
| Title: | Ranked Reward: Enabling Self-Play Reinforcement Learning for Combinatorial Optimization |
| Open access status: | An open access version is available from UCL Discovery |
| Publisher version: | https://aaai.org/Conferences/AAAI-19/ws19workshops... |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Med Phys and Biomedical Eng |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10115794 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
