Understanding Curriculum Learning in Policy Optimization for Solving
  Combinatorial Optimization Problems
  Over the recent years, reinforcement learning (RL) has shown impressive
performance in finding strategic solutions for game environments, and recently
starts to show promising results in solving combinatorial optimization (CO)
problems, inparticular 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 solving CO problems. We show that 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 combinatorial problem, Secretary Problem, we formally prove
that distribution shift is reduced exponentially with curriculum learning. 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 Secretary Problem and Online Knapsack to empirically verify our findings.
