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

arXiv: https://arxiv.org/abs/1807.01672 · HTML: https://mlsanity.com/paper/1807.01672/

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 4 Jul 2018.

## Built on by (most cited first, 27 of 27)

- [Combinatorial Optimization with Policy Adaptation using Latent Space Search](https://mlsanity.com/paper/2311.13569/) (2023)
- [MuZero with Self-competition for Rate Control in VP9 Video Compression](https://mlsanity.com/paper/2202.06626/) (2022)
- [Learning Practically Feasible Policies for Online 3D Bin Packing](https://mlsanity.com/paper/2108.13680/) (2021)
- [Beyond Games: A Systematic Review of Neural Monte Carlo Tree Search Applications](https://mlsanity.com/paper/2303.08060/) (2023)
- [Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective](https://mlsanity.com/paper/2404.06492/) (2024)
- [Attend2Pack: Bin Packing through Deep Reinforcement Learning with Attention](https://mlsanity.com/paper/2107.04333/) (2021)
- [Improving Generalization of Neural Combinatorial Optimization for Vehicle Routing Problems via Test-Time Projection Learning](https://mlsanity.com/paper/2506.02392/) (2025)
- [SOLO: Search Online, Learn Offline for Combinatorial Optimization Problems](https://mlsanity.com/paper/2104.01646/) (2021)
- [Qubit Routing using Graph Neural Network aided Monte Carlo Tree Search](https://mlsanity.com/paper/2104.01992/) (2021)
- [Self-play Learning Strategies for Resource Assignment in Open-RAN Networks](https://mlsanity.com/paper/2103.02649/) (2021)
- [LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation](https://mlsanity.com/paper/2205.10106/) (2022)
- [Planning Spatial Networks with Monte Carlo Tree Search](https://mlsanity.com/paper/2106.06768/) (2021)
- [Machine Learning for the Multi-Dimensional Bin Packing Problem: Literature Review and Empirical Evaluation](https://mlsanity.com/paper/2312.08103/) (2023)
- [Policy-Based Self-Competition for Planning Problems](https://mlsanity.com/paper/2306.04403/) (2023)
- [Neural Packing: from Visual Sensing to Reinforcement Learning](https://mlsanity.com/paper/2311.09233/) (2023)
- [First-Order Problem Solving through Neural MCTS based Reinforcement Learning](https://mlsanity.com/paper/2101.04167/) (2021)
- [Breaking the Performance Ceiling in Reinforcement Learning requires Inference Strategies](https://mlsanity.com/paper/2505.21236/) (2025)
- [Alphazzle: Jigsaw Puzzle Solver with Deep Monte-Carlo Tree Search](https://mlsanity.com/paper/2302.00384/) (2023)
- [Parameter Optimization of LLC-Converter with multiple operation points using Reinforcement Learning](https://mlsanity.com/paper/2303.00004/) (2023)
- [Minimize Control Inputs for Strong Structural Controllability Using Reinforcement Learning with Graph Neural Network](https://mlsanity.com/paper/2402.16925/) (2024)
- [Model-based reinforcement learning for protein backbone design](https://mlsanity.com/paper/2405.01983/) (2024)
- [Competing for pixels: a self-play algorithm for weakly-supervised segmentation](https://mlsanity.com/paper/2405.16628/) (2024)
- [TSS GAZ PTP: Towards Improving Gumbel AlphaZero with Two-stage Self-play for Multi-constrained Electric Vehicle Routing Problems](https://mlsanity.com/paper/2502.15777/) (2025)
- [DOPPLER: Dual-Policy Learning for Device Assignment in Asynchronous Dataflow Graphs](https://mlsanity.com/paper/2505.23131/) (2025)
- [One4Many-StablePacker: An Efficient Deep Reinforcement Learning Framework for the 3D Bin Packing Problem](https://mlsanity.com/paper/2510.10057/) (2025)
- [Diffusion Reinforcement Learning Based Online 3D Bin Packing Spatial Strategy Optimization](https://mlsanity.com/paper/2604.10953/) (2026)
- [Learning to Play: Reinforcement Learning and Games](https://mlsanity.com/paper/2610.17391/) (2026)

## Abstract (arXiv)

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.