# Understanding Curriculum Learning in Policy Optimization for Online Combinatorial Optimization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 55 references that are in the map.
- First posted on arXiv 11 Feb 2022.

## Builds on (most cited first, 29 of 29)

- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Curriculum Learning for Reinforcement Learning Domains: A Framework and Survey](https://mlsanity.com/paper/2003.04960/) (2020)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [Automated Curriculum Learning for Neural Networks](https://mlsanity.com/paper/1704.03003/) (2017)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [Fast Global Convergence of Natural Policy Gradient Methods with Entropy Regularization](https://mlsanity.com/paper/2007.06558/) (2020)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [Sample Efficient Reinforcement Learning with REINFORCE](https://mlsanity.com/paper/2010.11364/) (2020)
- [Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking](https://mlsanity.com/paper/2005.11081/) (2020)
- [RL for Latent MDPs: Regret Guarantees and a Lower Bound](https://mlsanity.com/paper/2102.04939/) (2021)
- [On Linear Convergence of Policy Gradient Methods for Finite MDPs](https://mlsanity.com/paper/2007.11120/) (2020)
- [Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time](https://mlsanity.com/paper/2006.03750/) (2020)
- [Transferable Graph Optimizers for ML Compilers](https://mlsanity.com/paper/2010.12438/) (2020)
- [Reinforcement Learning in Reward-Mixing MDPs](https://mlsanity.com/paper/2110.03743/) (2021)
- [Improving Optimization Bounds using Machine Learning: Decision Diagrams meet Deep Reinforcement Learning](https://mlsanity.com/paper/1809.03359/) (2018)
- [A Boosting Approach to Reinforcement Learning](https://mlsanity.com/paper/2108.09767/) (2021)
- [Interactive Learning with Corrective Feedback for Policies based on Deep Neural Networks](https://mlsanity.com/paper/1810.00466/) (2018)
- [Deep Policies for Online Bipartite Matching: A Reinforcement Learning Approach](https://mlsanity.com/paper/2109.10380/) (2021)
- [Mastering Rate based Curriculum Learning](https://mlsanity.com/paper/2008.06456/) (2020)
- [SOLO: Search Online, Learn Offline for Combinatorial Optimization Problems](https://mlsanity.com/paper/2104.01646/) (2021)
- [Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model](https://mlsanity.com/paper/1810.07903/) (2018)
- [Deep Reinforcement Learning with Feedback-based Exploration](https://mlsanity.com/paper/1903.06151/) (2019)
- [Improved Online Algorithms for Knapsack and GAP in the Random Order Model](https://mlsanity.com/paper/2012.00497/) (2020)

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

- [Self-Labeling the Job Shop Scheduling Problem](https://mlsanity.com/paper/2401.11849/) (2024)
- [Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes](https://mlsanity.com/paper/2210.11604/) (2022)

## Abstract (arXiv)

Over the recent years, reinforcement learning (RL) starts to show promising results in tackling combinatorial optimization (CO) problems, in particular when coupled with curriculum learning to facilitate training. Despite emerging empirical evidence, theoretical study on why RL helps is still at its early stage. This paper presents the first systematic study on policy optimization methods for online CO problems. We show that online CO problems can be naturally formulated as latent Markov Decision Processes (LMDPs), and prove convergence bounds on natural policy gradient (NPG) for solving LMDPs. Furthermore, our theory explains the benefit of curriculum learning: it can find a strong sampling policy and reduce the distribution shift, a critical quantity that governs the convergence rate in our theorem. For a canonical online CO problem, the Best Choice Problem (BCP), we formally prove that distribution shift is reduced exponentially with curriculum learning even if the curriculum is a randomly generated BCP on a smaller scale. Our theory also shows we can simplify the curriculum learning scheme used in prior work from multi-step to single-step. Lastly, we provide extensive experiments on the Best Choice Problem, Online Knapsack, and AdWords to verify our findings.