Understanding Curriculum Learning in Policy Optimization for Online Combinatorial Optimization
Authors: Runlong Zhou
Zelin He
Yuandong Tian
Yi Wu
Simon Shaolei Du
Venue: Accepted by TMLR ()

Abstract: 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.

Published in Transactions on Machine Learning Research (11/2023)
Understanding Curriculum Learning in Policy Optimization for Online Combinatorial Optimization
Runlong Zhou
nectorah@@cs.uushiigg
University of Washington
Zelin He University of Washington
zelinh2@uw.eed. edu
Yuandong Tian
yuandong@ft.com
Facebook AI Reseorch
Yi Wu Tsinghua University
jawwyi@gmail.cco
Simon S. Du University of Washington
sadu@cs. Siluu@essuasshngtto..e.
Reviewed on OpenReview: https: // operevveee.r.e.eee.em net/ forum? id= 9KE6BKRUjA
Abstract
Over the recent years, reinforcement learning (RI) starts to show promising results in tack- ling combinatorial optimization (CO) problems, in particular when coupled with curriculum learning to facilitate training. Despite emerging empirical evidence, thcoretical 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 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 strong sampling policy and reduce the distribution shift, 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 reduced exponentially with curriculum learning even if the curriculum is randomly generated BCP smaller scale. Our theory also shows 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 Ad to verify our findings.
be
simplify the
1 Introduction
In recent years, machine learning techniques have shown promising results in solving combinatorial opti- mization (CO) problems, including traveling salesman problem (TSP, Kool et al. (2019)), maximum cut [Khalil et al. 2017) and satisfiability problem (Selsam et al. 2019). While in the worst some CO prob- lems are NP-hard, in practice, the probability that we need to solve the worst-case problem instance is low (Cappart et al. 2021). Machine learning techniques are able to find generic models which have exceptional performance on the majority of a class of CO problems.
A significant subclass of CO problems called online CO problems, which has gained much attention Grötschel et al. 2001 Huang 2019 Garg et al.] 22008). Online CO problems entail sequential decision- making process, which perfectly matches the nature of reinforcement learning (RI).

---

Published in Transactions on Machine Learning Research (11/2023)
This paper concerns using RL to tackle online CO problems. RL is often coupled with specialized techniques including (a particular type of) Curriculum Learning (Kong et al.) 2019), human feedback and correction et al. (0018) Scholten et al. (2019)), and policy aggregation (boosting, Brukhhm et al. (2021) Practitioners use these tochniques to accelerate the training speed.
While these hybrid techniques enjoy empirical success, the theoretical understanding is still limited: is unclear when and why they improve the performance. In this paper, we particularly focus on RL with Curriculum Learning (Bengio et al.] (2009), also named "bootstrapping" in Kong et al. (2019)): train the agent from easy task and gradually increase the difficulty until the target task. Interestingly these techniques exploit the special structures of online CO problems.
Main contributions. In this paper, we initiate the formal study on using RL to lackle online CO problems, with a particular emphasis on understanding the specialized techniques developed in this emerging subarea. Our contributions are summarized below.
Formalization. For online CO problems, we want. to learn a single policy that enjoys good perfor- mance over a distribution of problem instances. This motivates us to use Latent Markov Decision Process (LMDP) (Kwon et al. 2021a) instcad of standard MDP formulation. We give concrete examples, the Best Choice Problem (BCP, also known as the Secretary Problem), Online Knapsack, and Wordss (Online Match- ing and Ad Allocation, ADW), to show how LMDP models online CO problems. With this formulation, we can systematically analyze RL algorithms.
Provable efficiency of policy optimization. By leveraging recent theory on Natural Policy Gradient for standard MDP Agarwal et al. (2021), ; we analyze the performance of NPG for LMDP. The performance bound is characterized by the number of iterations, the excess risk of policy evaluation, the transfer error, and the relative condition number x that characterizes the distribution shift between the sampling policy and the optimal policy. We also take into account the effect of entropy regularization. To our knowledge, this is the first performance bound of policy optimization methods on LMDP
Understanding and simplifying Curriculum Learning. Using our performance guarantee on NPG for LMDP, we study when and why Curriculum Learning is beneficial to RL for online CO problems. Our main finding is that the main effect of Curriculum Learning is to give a stronger sampling policy. Under certain circumstances, Curriculum Learning reduces the relative condition number K, improving the convergence rate. For BCP, we provably show that Curiculum Learning can exponentially reduce к compared with using the naïve sampling policy. Surprisingly, this means even a randomly constructed curriculum of BCP accelerates the training exponentially. As a direct implication, we show that the multi-step Curriculum Learning proposed in Kong et al.] (2019) can be significantly simplified into a single-step scheme. Lastly, to obtain a complete understanding, we study the failure mode of Curriculum Learning, in a way help practitioners to decide whether to use Curriculum Learning based their prior knowledge. To verify our theories, we conduct extensive experiments on three classical online CO problems [BCP, Online Knapsack (decision version, OKD), and ADW (decision version)] and carcfully track the dependency between the performance of the policy and k.
2 Related Works
Combinatorial Optimization problems. CO has been a long lasting field of people's interest. There are a rich literature regarding CO problems such as traveling salesman problem (Flood (1956): Bellmore & Nemhauser (1968)) ) maximum cut (Karp 19722; Goemans & Williamson (1995)), and satisfiability problem
(Cook) (1971); Trakhtenbrol (1984)).
RL for CO. There have been rich literature studying RL for CO problems, e.g., using Pointer Network
in REINFORCE and Actor-Critic for routing problems (Nazari et al. 2018), combining Graph Attention Network with Monte Carlo Tree Search for TSP (Drori et al., 2020) and incorporating Structture-o- Vector
Network in Deep Q-networks for maximum independent set problems (Cappart et al. 2019 Bello et al.
(217 proposed a framework to tackle CO problems using RI. and neural networks. Kool al. (2019)
combined REINFORCE and attention technique to learn routing problems. Vesselinova et al. (2020) and
Mazyavkina et al. (2021) are taxonomic surveys of RL approaches for graph problems. [Beggio et al. (0020)
2

---

Published in Transactions on Machine Learning Research (11/2023)
summarized learning methods, algorithmic structures, objective design and discussed generalization. In particular scaling to larger problems was mentioned as a major challenge. Compared to supervised learning, RL not only mimics existing heuristics, but also discover novel ones that humans have not thought of, for example chip design (Mirhoseini ct al. 2021) and compiler optimization (Zhou et al. 2020b). Theoretically, there is line of work on analyzing data-driven approach to combinatorial problems (Balcan 2020 However, to our knowledge, the theoretical analysis for RI-based method is still missing.
Kong et al. (2019) focused on using RL to tackle online CO problems, which means that the agent must make sequential and irrevocable decisions. They encoded the input in length-indeependent manner. For example, the i-th element of a n-length sequence is encoded by the fraction i/n and other features, so that the agent can generalize to unseen n, paving the way for Curriculum Learning. Three online CO problems were mentioned in their paper: ADW, Online Knapsack, and BCP. Currently, Online Matching (ADW) and Online Knapsack have only approximation algorithms (Huang et al., 2019; Albers et al.) 2021 There are also other works about RL for online CO problems. Alomrani et al. (2021) uses doep-RL for Online Matching. Oren al. (2021) studies Parallel Machine Job Scheduling problem (PMSP) and Capacitated Vehicle Routing problem (CVRP), which are both online CO problems, using offline- offine-learning and Monte
Carlo Tree Search.
LMDP. We provide the exact definition of LMDP in Section 4.1 As studied by Steimle et al. 2021 in the general cases, optimal policies for LMDPs are cases where there always exists an optimal history-independent policy. They showed that even finding the policy is NP-hard. [woon et al. (2021a) investigated the sample complexity and regret bounds of LMDP in the history-independent policy class. They presented exponential lower- bound for general LMDP and derived algorithms with polynomial sample complexities for cases with special assumptions. Kwon et al. (202bb) showed that in reward-mixing MDPs, where MDPs share the same transition model, a polynomial sample complexity is achievable without any assumption to find an optimal history-independent policy.
This is different from standard MDP
optimal distory-independens
Convergence rate for policy gradient methods. There line of work on the convergence rates of policy gradient methods for standard MDPs (Bhandari & Russo (2021), Wang et al. (2020), Liu et al. (2020). Ding
ct al. 22021, Zhang et al.] (2021)). For softmax tabular parameterization, NPG can obtain an O(1/T) rate
(Agarwal el al. 2021 where T is the number of iterations; with entropy regularization, both PG and NPG
achieves linear convergence Mee et al.] 2020 Cen et al. 2021). For log-tinear policies, sample-basee NPG makes an O(/vTT) convergence rate, with assumptions on Estat, Ebias and A. (Agarwal et al.
2021 (see our
Definition exact NPG with entropy regularization enjoys a linear convergence rate up to Ebiss CCayc
et al. 2021
We extend the analysis to LMDP
Curriculum Learning. There are a rich body of literature on Curriculum Learning (Zhou et al. 2021b aj
2020a; Ao et al. 2021 Willems et al. 2020: Graves et al.) 2017). As surveyed in Bengio et al. (2009). Curriculum Learning has been applied to training deep neural networks and non-convex optimizations and improves the convergence in several cases. Narvekar et al. (2020) rigorously modeled curriculum as a di- rected acyelic graph and surveyed work on curriculum design. Kong el al. (2019) proposed a bootstrapping (Curriculum Learning) approach: gradually increase the problem size after the model works sufficiently well on the current problem size.
3 Motivating Online CO Problems
Online CO problems are a natural class of problems that admit constructions of small-scale instances, because the hardness of them can be characterized by the input length, and instances of different scales are similar. This property simplifies the construction of curricula and underscores curriculum learning. We also believe online CO problems make the use of LMDP suitable, because under a proper distribution {wm), inslances in a large portion of the probability space have similar near optimal solutions.
In this section we introduce three motivating online CO problems. We are interested in these problems because they have all been extensively studied. Furthermore, they were studied in Kong et al. (2019) the
3

---

Published in Transactions on Machine Learning Research (11/2023)
paper that motivates work. They also have real-world applications, e.g., auction design (Babaioff et al. 2007 and advertisement targeting (Mehta et al. 2007
3.1 The Best Choice Problem (BCP)
In BCP, the goal is to maximize the probability of choosing the maximum among n different numbers, where n is known. They arrive sequentially and when the i-th number shows up, the decision-maker observes the relative ranking X among the first numbers, which means being the X;th-best so far. A decision that whether to accept reject the i-th number must be made immediately when it comes, and such decisions cannot be revoked. Once one number is accepted, the game ends immodiately.
The ordering of the numbers is unknown. There are in total n! permutations, and an instance of BCP is drawn from an unknown distribution over these permutations. In the classical BCP, each permutation is sampled with equal probability. The optimal solution for the classical BCP the well-known 1/c-threshold stralegy: reject all the first [n/e] numbers, then accept. the first one which is the best so-far. In this paper, also study some different distributions.
3.2 Online Knapsack (decision version, OKD)
In Online Knapsack problems the decision-maker observes n (which is known) items arriving sequentially, each with value V2 and size & revealed upon arrival. A decision to either accept or reject the i-th item must be made immediately when it arrives, and such decisions cannot be revoked. At any time the accepted items should have their total size no larger than a known budget B.
The goal of standard Online Knapsack is to maximize the total value of accepted items. In this paper, we study its decision version, whose goal is to maxinize the probabilily of total value reaching a known largel V.
We assume that all values and sizes are sampled independently from two fixed distributions, namely U1, ..,,..., On Lid. F. and 81, ........0 8n Lid. F.. In Kong et al. (2019) the experiments were carried with F. F. Unifo,11, and we also study other distributions.
Remark 1. A challenge in OKD the sparse reward: the only signal reward when the total value of accepted items first exceeds V (see the detailed formulation in Appendix C.2), unlike in Online Knapsack the reward of is given instantly after the i-th item is successfully accepted. This makes random exploration hardly get reward signals, necossitating Curriculum Learning.
3.3 AdWords (decision version, ADW)
In ADW, there are n advertisers each with budget 1 and m ad slots. Each ad slot j arrives sequentially along with a vector (Vi,j, U2,j..2.jj.... vo.j) where Vi the value that advertiser wants to pay for ad slot, Once ad slot arrives, it must be èrrevocably allocated to advertiser not allocated at all. If ad slot j is allocated to advertiser and the remaining budget of advertiser is not less than V.js the total revenue increases by Uay while advertiser i's budget decreases by Ut.j-
We assumee that for any advertiser i, U1,1, Ui.,...., Ui.m Lid. F, Kong et al. (0019) studied a very special case called online b-matching where F; is a Bernoulli distribution. We study different distributions.
The objective of the standard ADW is to maximize the total revenue. For a similar reason as in OKD, we set known targed V for the decision version. The goal of ADW to maximize the probubilily of total revenue reaching V.
We follow the statement in Kong optimal stopping problem.
2019 that BCP (secretary problem) CO prablem. It is categorized
4

---

Published in Transactions on Machine Learning Research (11/2023)
4 Problem Setup
In this section, we first introduce LMDP and why it naturally formulates online CO problems. Then we list necessary components required by Natural Policy Gradient for LMDP (Algorithm
For any positive integer n, we denote [n] := {1, ...,, nn. For any vector I E R", we denote x. == r = xx T as the celf-outer-produce z. Further for any y E R",, we denote (ro == x(i)(()).
Notations.
4.1 Latent Markov Decision Process
Tackling an online CO problem entails handling a family of problem instances, and each instance can be modeled as a Markov Decision Process. For online CO problems, we want to find one algorithm that works for a family problem instances and performs well on average over an (unknown) distribution over this family. To this end, we adopt the concept of Latent MDP which naturally models online CO problems.
Latent MDP (Kwon al. 2021a is collection of MDPs M M2.-.,,M All the MDPs share state set S, action set A and horizon H. Each MDP .Mm (S,A, H, Um, Pm, Tm) has its own initial state
distribution V' E A(S), transition Pm S x A - A(S) and reward rm : S x A- [o, 1]. where A(S) is the probability simplex over S. Let W1, u2,..., war be the mixing weights of MDPs such that wm > 0 for any m and EM=1 Wm = At the start of every cpisode, one MDP Mm M is randomly chosen with probability Wm-
Due to the time and space complexities of finding the optimal history-dependent policies, we stay in line with Kong et al. (2019) and care only about finding the optimal historg-indeependen policy. Let II {x S [(A)} denote the class of all the history-independent policies.
Log-linear policy. Let Φ : S x A - Ed be a feature mapping function where d denotes the dimension of fcature space. Assume that [ a) 2 E B. A log-lincar policy is the form:
exp(0 (0s a))
(als))
En'EA exp(@T exp(OTo(saa)) o(s,a'))' where O e IRd..
Remark 2. Log-lincar paramcterization is a gencralization of softmar tabular parameterization by setting d = |S]|A| and a(s.a) = One-hot(s, a). They are "scalable": if ø extracts important features from different S x As with a fixed dimension d & A), then a single my can generalize.
Value function, Q-function and advantage function. The expected reward of executing π on Mm is defined via value functions. We incorporate entropy regularization for completeness because prior works (especially empirical works) used to facilitate training. Due to space limit, we defer all the entropy regularized notations, algorithe and theorem to Appendix
A
We define the value function:
V V (s) == E.M
Σ
Tm ar)
80
where the expectation is with respect to the randomness of trajectory induced by in Mm Denote V* := M Wm Lnjes Vm (m V V (5o), then we need to find x² = arg ma V=, Denote V == Va
The Q-funtiion can be defined in a similar manner:
( = E.M.
Σ Tm Ton ar)
(so. 0o) = (8,
and the advantage function is defined as A A a) = Qt (s, Va (s).
Modcling BCP. For BCP, each instance permutation of length n, and in each round an instance is drawn from an unknown distribution over all permutations. In the i-th step for E [n], the state encodes the i-th number and its relative ranking far. The transition is deterministic according to the problem
5

---

Published in Transactions on Machine Learning Research (11/2023)
definition. A reward of 1 is given and only if the maximum is accepted. We model the distribution follows: for the i-th number, it has probability P, to be the best so-far and is independent of other i'. Hence, the weight of each instance is simply the product of the probabilities on each position. The classical BCP satisfics P. = 1/i.
Modeling OKD. For OKD, each instance is a sequence of items with values and sizes drawn from unknown distributions and Fg. In the i-th step for E [n], the state encodes the information of i-th item's value and size, the remaining budget, and the remaining target value to fulfill. The transition is also deterministic according to the problem definition, and reward of is given if and only if the agent obtains the target value for the first time. F. F, Unifo,.] in Kong et al. 2019).
Modeling ADW. For ADW, each instance is a n. x m malrix (vi,g) [mm] with each row subject lo a distribution Fç. In the j-th step for j [m]] the state encodes the value vector (V1,) v2...... Un,5), the remaining budget vector (B1, Ba..... B,), and the remaining target revenue fulfill. The transition also deterministic according to the problem definition, and reward of 1 is given and only if the agent obtains the target revenue for the first time.
4.2 Algorithm components
In this subsection will introduce some necessary notations used by main algorithm. Definition 1 (Visitation Distribution). The state visitation distribution and state-action visitation distri- bution at step h 3 0 with respect to in Mm are defined as
(s) P. (8p 8), d I a) = - PM h 8, = a).
We will encounter a grafted distribution d= d,,n, (s, a) = d' (s) Unifa(a) which in general is not the state- action visitation distribution with respect to any policy. However, can be attained by first acting under æ for h steps to get states then sample actions from the uniform distribution UnifA. This distribution will be useful when we apply variant of NPG, where the sampling policy is fixed.
Denote
d m. - d and t short for (dm,) 3 gmm M.meMM. here can be any symbol.
We also need the following definitions for NPG, which are different from the standard versions for discounted MDP because weights [wm] must be incorporated in the definitions to deal with LMDP. In the following definitions, let be the collection of any distribution, which will be instantiated by d', d, etc. the remaining sections.
Definition 2 (Compatible Function Approximation Loss). Let g be the parameter update weight, then NPG is related to finding the minimizer for the following function:
L(g; 0 v) =
M
Σ
E. E.
( [A -
Definition 3 (Generic Fisher Information Matrix).
D
WmD Eaa (
Particularly, denote F(O)= = t0
as the Fisher information matrix induced by ma.
5 Learning Procedure
In this section we introduce the algorithms: NPG supporting any customized sampler, and our proposed Curriculum Learning framework.

---

Published in Transactions on Machine Learning Research (11/2023)
Natural Policy Gradient. The learning procedure generates series of parameters and policies. Starting from for the algorithm updates the parameter by setting 0c+1 0, + 19t,, where v is predefined constant :=
learning rate, and gt is the update weight. Denote := Te, v=: V and A : A for convenience.
We adopt NPG (Kakade, 2002) because it is efficient in training paramcterized policies and admits clean theoretical analysis. NPG satislies 9t E arg ming g L(g: 0N, d (see Appendix D.1 for explanation). When we only have samples, we use the approximate version of NPG: gr. x arg min g=g Lgg; Oz, d where G = {x ||>|| < G} for some hyper-parameter G.
geg
We also introduce variant of NPG: instead of sampling from de using the current policy Tt, we sample from d= using& a fized sampling policy T.. The update rule 9 x arg mingeg L(g; (00;00,0t d)). This version makes closed-form analysis for BCP possible.
The main algorithm is shown in Algorithm 1 It admits two types of training: @ If T. = None, it calls Algorithm 4 (deferred to Appendix A) to sample s, ~ d 2 If # None, it then calls Algorithm 4 to sample 8, d=. Algorithm also returns an unbiased estimation of as)
In both cases, we denote d' as the sampling distribution and Σg as the induced Fisher Information Matrix used in step t, i.e. d'==d',... d == F(O,) if π. None; d' := d , == 20, otherwise. The update rule can be written in unified way as It arg mingag Lgg; d') This is equivalent to solving a constrained quadratic optimization and we use existing solvers.
Remark 3. Algorithm is different from Algorithm 4 of Agarwal et al. 2021 in that we use a "batched" update while they used successive Projected Gradient Descents (PGD). This is an important implementation tochnique to speed up training in our experiments.
Curriculum Learning. We use Curriculum Learning to facilitate training. Algorithm 2 our proposod training framework, which first constructs an easy environment E' and trains (near- Joptima policy π, of it. The design of E' is problem-dependent. For the problems described in this paper (BCP, OKD, and ADW) well as any similar problems (online load balancing, online set cover, etc.), we can n, the sequence length of online decision-making, to represent the difficulty. For these problems, we construct E' to be the environment with n smaller than that of E. For other problems, we first find the hyperparameters controlling the difficulty of the problem, c.g., the sequence length, the action space size, the number of interaction steps, then reduce these hyperparameters to construct a smaller scale and simpler problem.
In the target euvironment E, we either use म. to sample data while training a new policy from scratch, or simply continue training т.. To be specific and provide clarity for the results in Section 7
we name few
training modes (without regularization) here, and the rest are in Table 1 in Appendix C
curl, the standard Curriculum Learning, runs Algorithm 2 with samp pi_t; dix_samp_cur stands for the fixed sampler Curriculum Learning, rumning Algorithm 2 with samp = pi_s. direct means directly learning in E without curriculum, i.e., running Algorithm | with ne = None; naive_ _amppppapppppe also directly learns in E, while using n, naive random policy to sample data Algorithm 1
6 Performance Analysis
Our analysis contains two important components, namely the sub-optimality gap guarantec of the NPG proposed, and the efficacy guarantee of Curriculum Learning on BCP. The first component can also be extended to history-dependent policies with features being the tensor products of features from each time step (exponentially large).
6.1 Natural Policy Gradient for Latent MDP
Let of E arg min
mingeg yeg L(g; Br, dt,d") denote the true minimizer. We have the following definitions:
Definition 4. Define for 0 & T T:
(Excess risk) Cstat == max, (g:; 8c, d') L(g 0c, d')];
(Transfer error) chins
max, [[T 0,, d' d')];
7

---

Published in Transactions on Machine Learning Research (11/2023)
Algorithm NPG (Full version: Algorithm 3)
Input: Environment E; learning rate y; episode number T; batch size N; initialization fo; sampler *s; optimiza-
tion domain g.
2: for t + 0, o,l,..., - do
For 0 & n N and h H 1,, sample (a ,) and estimate A using Algorithm
4: Calculate:
N H-1
Fe.
Σ
Vo (1.
n=
N-1 H-1
V
Σ
Σ
(n)
H- Vo mo (a 10) 10)
n-U N-U
Call any solver to get 9t arg min 9 Fig- 2g V..
6:
Update 0141 <- 02 n9:.
end for
8: Return: 0r.
Algorithm Curriculum learning framework.
Input:
Environment E; learning rate y) episode number T; batch size N; sampler type samp é { pi_s, pi_t t }: optimization domain G.
2: Construct an environment E" with a task casier than E. This enviromment should have optimal policy similar to that of E.
3: 0. + NPG (E", 17, O." None, G) (Algorithm samp =pi_s then
5: Pr - NPG (E, N,N, 9).
else
7: fT - NPG (E, n, N,N, 0s, None, 9).
end if
9: Return: 0r.
(Relative condition number) K = max, E sup random quantity as Og is random.
Note that term inside the expectation is Lix
The expectation with respect the randomness in the sequence of weights go. 90.91.-.. .1....,
9r. .
All the quantities commonly used in literature mentioned in Section Estat is due that the minimizer gr from samples may not minimize the population loss L. Chius quantifies the approximation error due to fcature maps. & characterizes the distribution mismatch between d' and d' and is a key quantily in Curriculum Learning and will be studied in more details in the following sections.
Our main result based on a fitting error which depicts the closeness between Λ and any policy m. Definition 5 (Fitting Error). Suppose the update rule is oc+1 0s 19t, define
Σ Win
Σ E(s.a) (m ge Vo (o
CITY =
Theorem 0 shows the convergence rate of Algorithm
and its proof is deferred to Appendix A.3
Theorem 6. With Definitions 5 and
Algorithm enjoys the following performance bound:
E
min O
(xxo) nT
+
B²
Σ
E[em]]
2
T
(
B²G²
+ +
+ Hebias + v HNEaat
nT
2
where (TTO) is the Lyapunov potential function which is only relevant. to the inilialization.

---

Published in Transactions on Machine Learning Research (11/2023)
Remark 4. ① For the results of sample-based NPG with entropy regularization for LMDP, please see Appendix @ Taking 7 ((/vVT) gives an O(1/VT) rate, matching the result in Agarwal et al. (2021)
① Cstat be reduced using larger batch size N (Lemma 20 that Stat Ö(1vVN) 4 If some d, (especially the initialization do) is far away from d", may be extremely large (Section 6.2 example). If we can find a policy whose is small with single curriculum, we do not need the malli-step curriculum learning procedure used in Kong et al. (2019).
6.2 Curriculum learning for BCP
For BCP, there exists threshold policy that is optimal (Beckmann 1990). Suppose the threshold is E (0, 1), then the policy is: accept the i-th number if and only i/n > p and X, 1. For the classical BCP where all the nf instances have equal probability, the optimal threshold is 1/e.
To show that curriculum learning makes the training converge faster, Theorem gives direct hint: cur- riculum learning produces good sampler leading to much smaller than that of naive random sampler. Here we focus on the cases where samp pi_ _s because the sampler is fixed, while when samp pi_t t it is impossible to analyze dynamic procedure. We show Theorem 7 to characterize in BCP. Its full statement and proof is deferred to Appendix B
Thcorem 7. Assume that each number is independent of others and the i-th number has a probobility P. of being the mazimum so Sar (Section 4.7/. Assume the oplimal policy is a p-threshold policy and the sampling policy is q thtreshhlld policy. There erists a policy parameterization such that:
({
I npl
bmglt I-15
1,
q > P:
Knaive
2|mel max
max s S2[up]+2
I
2(1 - P2))
(1)
j-Inp]+1
where Rearl and Knaive are of the sampling policy and the naiue random policy, respectively-
To understand how curriculum learning influences K, we apply Theorem to three concrete cases. They show that, when the state distribution induced by the optimal policy in the small problem is similar to that in the original large problem, then a single-step curriculum suffices (ef. @ of Remark 4
The classical case: an exponential improvement. We study the classical BCP first, where all the n! permutations sampled with equal probability. The probability series for this case is P. 1/i. Substituting them into Equation ( directly gives:
ln/el ng
1
Knaive 2 [n/el
Keurl
e:
q
Except for the corner case where q < 1/n, we have that Kearl O()) while fiuaive 1((2). Notice that any distribution with P: & 1/i leads to an exponential improvement.
A more general case. Now we try to loosen the condition where P. & 1/i. Let consider the case where
P & 1/2 for > 2 (by definition Pi is always equal to 1). Equation 1 now becomes:
Keurl {
2 glupl-ing [ng]
S q> > p.
Knaiie > 2|mpl
Clearly, Keurl & nnaive always holds. When g is close to p. the difference exponential [ng]
Failure mode of Curriculum Learning. Lastly we show further relaxing the assumption on P. leads failure cases. The extreme case is that all P: 1, i..,, the maximum number always comes as the last one. Suppose < - 1/n, then (1) 0. Hence Kearl 00, larger than Knaive 2n-1, From Equation ①
Knuive & 2n-1, Similar as Section 3 of Beckmann 1990 the optimal threshold p satisfies:
P.
P
Σ
1 1<
Σ
P
P
+2
+1
9

---

Published in Transactions on Machine Learning Research (11/2023)
fix samp_cum curl
naive_samp
direct
curl
reference
(a)
(b)
(C)
0.4
0.6
0.3
log(Kappa)
2,04
avrr
0.2
20
0.2
0.1
0.0
0
2
3
2
0
2
#sample
1e8
#sample
1e8
#sample
1e8
Figure
One experiment of BCP. The r-axis is the number of Irajectories, i.e., number of episodes horizon batch size. Dashed lines represent only final phase training and solid lines represent Curriculum Learning. The shadowed area shows the 95% confidence interval for the expectation. The explanation for different modes can be found in Section The reference policy is the optimal threshold
policy.
fix samp_ curl
Saive_samp
direct
curl
reference
(b)
0.4
(og(Kappa)
avg(err, .)
0.2
0.2
5
0.0
0.0
0
2
2
4
0
#sample
1e8
#sample
1e8
#sample
1e8
Figure 2: One experiment of OKD. Legend description the same as that of Figure The reference policy is the bang-per-buck algorithm for Online Knapsack (Section 3.1 of Kong et al. (2019
So letting Pa > 1/2 results in p E [1- 1/n, 1). Further, if q < 1- 1/n and P3 > 1-2 2- for any [ng] + < j & n n-1, 1, then from Equation 4 Keurl > 2n > Kaaive- This means that Curriculum Learning can always be manipulated adversarially. Sometimes there is hardly any reasonable curriculum.
Remark 5. Here we only provide theoretical explanations for BCP when samp pi_ s, because x highly problem-dependent, and the analytical forms for k is tractable when the sampler fixed. For samp = pi_t and other CO problems such as OKD, however, do not have analytical forms, we resort empirical studies (Section
7 Experiments
The experiments' formulations are modified from Kong et al. (2019). Due to page limit, more formulation de- tails and results are presented in Appendix C and code can be found htttp://giihhb. ctme /hourunlooogg///////// mL--for-Combinatriiall oirr-oobbbnntrrrra---pppiiiaaaii Optimizatiin In Curriculum Learning the entire training process splits into most two phases. We call the training curriculum (small scale instances) "warm-up phase" and the train- ing on large scale instances "final phase". If the training is directly on large scale instances, we still call it "final phase" for convenience. For each problem, we run multiple experiments using different. distributions of instances. Each experiment contains multiple training methods, e.g., direct training, curriculum learning, etc. To highlight the effect of curriculum learning, we omit the results regarding regularization, and they can be found in supplementary files. All the trainings in the same experiment have the same distributions over LMDPs for final phase and warm-up phase (if any), respectively.
10

---

Published in Transactions on Machine Learning Research (11/2023)
fix samp_ curl
naive_same sampp
direct
curl
reference
(a)
(b)
0.8
1.5
0.8
0.6
log(Kappa)
avg(err t
0.6
1.0
0.4
0.4
0.5
0.2
0.2
0.0
0.0
0.0
0.00
0.25
0.50 #sample
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
1e7
#sample
#sample
1e7
Figure One experiment of ADW. Legend description the same as that of Figure The reference policy obtained by running a curl procedure. The in k and avg(err,) curves are then plotted with the above reference policy hard-coded into the environment.
The Best Choice Problem (BCP). We show one of the four experiments in Figure Aside from reward and lnx, we plot the weighted average of err, according to Theorem 6 avg(err,) Σ - err./T. All the instance distributions guarantees reproducibility and comparability. Aside from the fact that the curriculum is smaller BCP, there is no other erplicit relationship between the curriculum and the target environment, so the curriculum can be viewed as random and independent. The experiments clearly demonstrate that curriculum learning can boost the performance by a large margin and curriculum learning indeed dramatically reduces N, even the curriculum is randomly generated.
generated from parameterized series (Pn} with fixed random seeds, which
Online Knapsack (decision version, OKD). We show of the three experiments in Figure 2 In and avg(err,) are with respect to the reference policy, bang-per-buck, algorithm, which is not the optimal policy. Thus, they are only for reference. The curriculum generation is also parameterized, random and independent of the target environment. The experiments again demonstrate the effectiveness of curriculum learning and curriculum learning indeed dramatically reduces k.
The reference policy is obtained by using curriculum learning and training until nearly convergence. The curriculum generation is also parameterized, random and independent of the target environment. The experiments again demonstrate the effectiveness of curriculun learning.
AdWords (decision version, ADW). We show one the two experiments Figure 3
8 Conclusion
We showed online CO problems could be naturally formulated as LMDPs, and we analyzed the convergence rate of NPG for LMDPs. Our theory shows the main benefit of curriculum learning is finding a stronger sampling strategy, especially for classical BCP any curriculum exponentially improves the learning rate. Our empirical results on BCP, OKD, and ADW also corroboratod our findings. Our work the first attempt systematically study techniques devoted to using RT. to tackle online CO problems, which we believe is fruitful direction worth further investigations.
Acknowledgement
SSD acknowledges the support of NSF IIS 2110170, NSF DMS 2134106, NSF CCF 2212261, NSF IIS 2143493, NSF CCF 2019844, NSF IIS 2229881.
References
Alckh Agarwal, Sham M. Kakade, J. Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. J. Mach. Learn. Res,, 22:98:1-9848 2021.
11

---

Published in Transactions on Machine Learning Research (11/2023)
Susanne Albers, Arindam Khan, and Leon Ladewig. Improved online algorithms for knapsack and gap in the random order model. Algorithmica, 83:1750 - 17785, 2021.
Mohammad Ali Alomrani, Reza Moravej, and Elias B Khalil. Deep policies for online bipartite matching: A reinforcement learning approach. arXiv prepriat or arvi::2109. 10380, 2021.
Shuang Ao, Tianyi Zhou, Guodong Long, Qinghua Lu, Liming Zhu, and Jing Jiang. CO-PILOT: COI- laborative planning and reinforcement learning on sub-task curriculum. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https://openreviee http:rreweeeeeee/oummmmm..
Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert D. Kleinberg, A knapsack secretary problem with applications. In APPROX-RANDOM, 2007.
Maria-Florina Balcan. Data-driven algorithm design. arXiv preprint arXiv:2011.07177 2020.
M.J. Beckmann. Dynamic programming and the secretary problem. Computers & Mathemalics with Appli- cations, 19(11):25 28, 1990. ISSN 0898- 1221. doi: https://bbo.orr///00000/00////// 12010088-12199000000 (9009990144 URL
/ttps://www. wtt.::/swwnnndeee......m.m. com httpa///................a//////.
M. Bellmore and G. L. Nemhauser. The traveling salesman problem: A survey. Operations Research, 16(3):
538-558, 1968. ISSN 0030364X, 15265463. URL http://www.jjtte wtwpooobbeeeeeeeree/ |
Irwan Bello, Hieu Pham, Quoe V. Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial opti- mization with reinforcement learning, 2017.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th Anmual International Conference on Machine Learning. ICML '09, pp. 41-48, New York, NY, USA, 2009. Association for Computing Machinery. ISBN 9781605585161. doi: URL http:::/ab...oggg..111111666// 1145///3.111///33777... 1553380
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine lcarning for combinatorial optimization: a methodological tour d'horizon. European Journal of Operational Research, 290, 08 2020. doi: 10.1016/j. 5jor.2020.07.066 0636
Jalaj Bhandari and Daniel Russo. On the linear convergence of policy gradient methods for finite mdps. In Arindam Banerjee and Kenji Fukumizu (eds.), Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 2386-
2394. PMLR, 13-15 15 Apr 2021. URL htttps//procceddnggz mlr. ppress/v130/ wwwpb/aannaaaa... html
Nataly Brukhim, Elad Hazan, and Karan Singh. A boosting approach to reinforcement learning, 2021.
Quentin Cappart, Emmanuel Goutierre, David Bergman, and Louis-Martin Rousseau. Improving optimiza- tion bounds using machine learning: Decision diagrams meet deep reinforeement learning. Proceedings of the AAAI Conference on Artificial Intelligence, (31):1144 1451, Jul. 2019. doi: 10. 10.1609/aaai.v330 3301 1443. URL https://ojs...... aaaii
aaai. org/ wetg//ndx..... phpp /At.A///arrticceevi///////
Quentin Cappart, Didier Chételat, Elias B. Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. In Zhi-Hua Zhou (ed.), Proceedings of the Thirticth International Joint Conference on Artificial Intelligence, IJCAI-21, pp. 4348-4355. Inter- national Joint Conferences Artificial Intelligence Organization, 8 2021. doi: 10.24963 /ijcaai 2021..20 URL https: org/10 10. 24963/1jcai 2021/595) Survey Track.
Semih Cayei, Niao He, and R. Srikant. Lincar convergence of entropy-rogularized natural policy gradient with linear function approximation, 2021.
Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 12 2021. doi: 10.1287 20pre.2021.2111
12

---

Published in Transactions on Machine Learning Research (11/2023)
Stephen A. Cook. The complexity of theorem-proving procedures. In Proceedings of the Third Annual ACM Symposium on Theory of Computing, STOC '71, pp. 151-158, New York, NY, USA, 1971. Association for Computing Machinery. ISBN 9781450374644. doi: 001144/800157.805555 URL https://doi. org///00..0..//....
Yuhao Ding, Junzi Zhang, and Javad Lavaei. On the global convergence of momentum-based policy gradient, 2021.
Iddo Drori, Anant Kharkar, William R. Sickinger, Brandon Kates, Qiang Ma, Suwen Ge, Eden Dolev, Brenda L. Dictrich, David P. Williamson, and Madeleine Udell. Learning to solve combinatorial optimiza- tion problems on real-world graphs in linear time. 2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA), pp. 19 24, 2020.
Merrill M. Flood. The traveling-saleesman problem. Operations Research, 4(1):61-75, 1956. ISSN 0030364X, 15265463. URL
Naveen Garg, Anupam Gupta, Stefano Leonardi, and Piotr Sankowski. Stochastic analyses for online com- binatorial optimization problems. 2008.
Michel X. Goemans and David P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42((): 1145, nov 1995. ISSN 0004- 5411. doi: 10.1145 01155/27663..22177
URL https::/doi. 10. wttpoo/..1//////..../.. /141//17683111./// 227684
Alex Graves, Mare G. Bellemare, Jacob Menick, Rémi Munos, and Koray Kavukcuoglu. Automated cur- riculum learning for neural networks. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, mlr, wttess//vO//gravesl11 html
pp. 1311-1320. PMLR, 06-11 Aug 2017. URL https::/proceedding:
Martin Grötschel, Sven O Krumke, Jörg Rambau, Thomas Winter, and Uwe T Zimmermann. Combinatorial online optimization in real time. Online oplimization of large scale systems, pp. 679 704, 2001.
Zhiyi Huang. Online combinatorial optimization problems with non-linear objectives. In Nonlinear Combi- natorial Optimization, pp. 179-205 Springer, 2019.
Zhiyi Huang, Peng Binghui, Zhihao Tang, Runzhou Tao, Xiaowei Wu, and Yuhao Zhang. Tight Competêtive Ratios of Classic Matching Algorithms in the Fully Online Model, pp. 2875-2886. 01 2019. ISBN 978-1- 61197-548-2. doi:
Sham M Kakade. A natural policy gradient. In T. Dielterich, S. Becker, and Z. Ghahramani (eds.), Advances in Newrol Information Processing Systems, volume 14. MIT Press, 2002. URL httpps:/prroceddnngs
.dff
Richard Karp. Reducibility among combinatorial problems. volume 40, pp. 85 103, 01 1972. ISBN 978-3-
540-66274-5. doi: 000000997783-5--6277777 8.
Elias Boutros Khalil, Hanjun Dai, Yuyu Zhang, Bistra N. Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In NIPS, 2017.
Weiwei Kong, Christopher Liaw, Aranyak Mehta, and D. Sivakumar. A new dog learns old tricks: RI finds classic optimization algorithms. In ICLR, 2019.
Wouter Kool, Herke van Hoof, and Max Welling, Attention, learn to solve routing problems! In ICLR, 2019.
Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, and Shie Mannor. RI for latent mdps: Re- gret guarantees and a lower bound. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (cds.), Advances in Neural Information Processing Systems, volume 34, pp. 24523- 24534. Curran Associates, Inc., 2021a. URL http://pwwooooaooooooooooooppppp ae775a666bs9950bbccccaaaaaaaa1
13

---

Published in Transactions on Machine Learning Research (11/2023)
Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, and Shie Mannor. Reinforcement learning in reward-mixing mdps. In NewrIPS, 2021b.
Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (variance-reduces) policy gradient and natural policy gradient methods. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 7634-7636. Curran Associates, Inc., 2020. URL httpss//prooceeding.. wttpp/pp..//ppppe////////////// Paper. pdf
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Ergeny Burnacv. Reinforcement learning for combinatorial optimization: A survey. Computers & Operalions Research, 134:105400, 05 2021. doi: 10.1016/j.cor.2221..666 2000..00000
Aranyak Mchta, Amin Saberi, Umesh Vazirani, and Vijay Vazirani. Adwords and generalized online match- ing. Journal of the ACM (JACM), 54(5):22 es, 2007.
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, PMLR, 13-18 Jul 2020. URL http:://proo/// http:///proceedings mlr wtt.:ppwweeeeeeeeeeeeee
pp.
html
Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Wenjie Jiang, Ebrahim M. Songhori, Shen Wang, Young-Joon Lee, Eric Johnson, Omkar Pathak, Azade Nazi, Jiwoo Pak, Andy Tong, Kavya Srinivasa, Will Hang, Emre Tuncer, Quoc V. Le, James Laudon, Richard Ho, Roger Carpenter, and Jeff' Dean. A graph placement methodology for fast chip design. Nature, 594 7862:207- 212, 2021.
Sanmit Narvekar, Bei Peng, Matteo Leonetti, Jivko Sinapov, Matthew E. Taylor, and Peter Stone. Cur- riculum learning for reinforcement learning domains: A framework and survey, J. Mach. Learn. Res., 21: 181:1-181:50, 2020.
M. Nazari, Afshin Oroojlooy, Lawrence V. Snyder, and Martin Takác. Reinforcement learning for solving the vehicle routing problem. In NewrIPS, 2018.
Joel Oren, Chana Ross, Maksym Lefarov, Felix Richter, Ayal Taitler, Zohar Feldman, Christian Daniel, and Dotan Di Castro. Solo: Search online, learn offline for combinatorial optimization problems. ArXiv, abs/2104.01646, 2021.
Rodrigo Pérez-Dattane Carlos Celemin, Javier Ruiz del Solar, and Jens Kober. Interactive learning with corrective feedback for policies based on deep neural networks. In ISER, 2018.
Jan Scholten, Daan Wout, Carlos Celemin, and Jens Kober. Deep reinforcement learning with feedback- based exploration. 2019 TEFF 58th Conference on Decision and Control (CDC), Dec 2019. doi: 10.1109/ 2019 9029503
cdc40024.2019 201.999990..... URL http://dx doi wtt.://///...1/////////////0
Daniel Selsam, Matthew Lammn Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L. Dill. Learn- ing SAT solver from single-bit supervision. In International Conference on Learning Representations, 2019. URL
iA5tm
Lauren N. Steimle, David L. Kaufman, and Brian T. Denton. Multi-model markov decision processes. IISE Transactions, 13(10):1124-1133, 2021. doi: 1080/24725854. 1895454)
URL https://doi.
B.A. Trakhtenbrot. survey of russian approaches to perebor (brute-force searches) algorithms. Annals of the History of Computing, 6(4)33844400 1984. doi:
Natalia Vesselinova, Rebecca Steinert, Daniel F. Perez-Ramirez, and Magnus Boman. Learning combinatorial optimization graphs: A survey with applications to networking. IEFE Access,
2020.
14

---

Published in Transactions on Machine Learning Research (11/2023)
Lingxiao Wang, Qi Cai, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global opti-
mality and rates of convergence. In International Conference on Learning Representations, 2020. URL
https://opeereviert http:///wwwwt.eeoooooooooooooaau
Lucas Willems, Salem Lahlou, and Yoshua Bengio. Mastering rate based curriculum learning, 2020.
Junzi Zhang, Jongho Kim, Brendan O'Donoghue, and Stephen Boyd. Sample efficient reinforcement learning with reinforce. In AAAI, 2021.
Tianyi Zhou, Shengjic Wang, and Jeffrey Bilmes. Curriculum learning by dynamic instance hardness. H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Advances in Neural Infor- mation Processing Systems, volume 33, pp. 1602-8613. Curran Associates, Inc., 2020a. URL https: //proceedings. penoceedings.neurips.. nwwrips........
Tianyi Zhou, Shengjie Wang, and Jeff Bilmes. Curriculum learning by optimizing learning dynamics. In Arindam Banerjee and Kenji Fukumizu (eds.), Proceedings of The 24th International Conference on Ar- tificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 433-441. PMLR, 13 15 Apr 2021a. URL htttps://proceedingg mlr (anoss/vv3///zouuus
Tianyi Zhou, Shengjic Wang, and Jeff Bilmes. Robust curriculum lcarning: from clean label detection noisy label self-correction. In International Conference on Learning Representations, 2021b. URL
https://openreviier http:://ppepeeeeeeeeeeeeeeeeeeap
Yanqi Zhou, Sudip Roy, Amirali Abdolrashidi, Daniel Wong, Peter Ma, Qiumin Xu, Hanxiao Liu, Phitchaya Phothilimtha, Shen Wang. Anna Goldie, Azalia Mirhoscini, and James Laudon. Trans- ferable graph optimizers for ml compilers. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Bal- can, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 13844- 13855. Curran Associates, Inc., 2020b. URL 9779440022be11055557744446666363 Paperraaarar..r....e. Paredd-aapppp.............
A Full Results of the Main Algorithm and Theorem for Entropy Regularization
A.1 Notations and Definitions
Entropy regularized value function, Q-function and advantage function. We incorporate entropy regularization for completeness because prior works (especially empirical works) used it to facilitate training, We define the value function in unified way: V= (s) is defined as the sum of future X-regularized rewards starting from and executing for h steps in M i.e.,
(s E.M.
Σ rm (st,
8D
where r (s, a) = rm(ss + Aln Z(olaj/ 1 and the expectation with respect to the randomness of trajectory induced by x in Mm. Clearly, VT, = (s))
For any Mms n. h, with H(T(-1s)) = EmEa (alss) In Z(al)) E [0, In [A]] we define
(s) = E.
Σ H(T(-10))
80 =
In fact, (T = VTT (s) + AH (.
Denote VRA = EMh Wm Ennes (So) V (8o) then V V=.0 The original goal is to find x² arg max V Under regularization, seek for मx arg max VRA instead. Denote V Vai.A.
15

---

Published in Transactions on Machine Learning Research (11/2023)
Since V & V VM & V AH In |n], the regularized optimal policy गं can be nearly optimal long as the regularization coefficient À is small enough. For notational ease, we abuse I' with xx- The Q-function can be defined in similar manner:
Q (s, a) = EMm.. Σ rm (s6, az)
(so, (00, an) = (s, (0.0)
and the advantage function defined A m a) Q (s, (s).
Denote IT nB., VLA V and A AmA for convenience.
Definition 8 (Definition with entropy regularization). Let g be the parameter update weight, then NPG is related to finding the minimizer for the following function:
H
[ -9" Vo (o
L(g: 0)
Σ Wm 172=1
E
H
Definition 9 (Tyapunov Potential Function Cayci et al. as follows: for any π E II,
2021
We define the potential function c II - R
M Σ
H-
n" (a|ss) [aass)
((T)
Wm
In
A.2 Algorithms
Algorithm 3 is the full version of Algorithm skipped sampling function.
with support of entropy regularization. Algorithm is the
A.3
Performance of Natural Policy Gradient for LMDP
We restate Theorem with entropy regularization.
Theorem (Full Stalement of Theorem performance bound:
With Desinilions
4
and
Algorillm
enjoys the following
A(1 - 177) T (T)))
B2G
E - -n) TOTT-EEoan Eferr]]
min V*d - vCa TEtET
E
<
(1 7A)T+1
2
Ex - T
X(1 - 7T T+ ((mu)
B2G²
+
+ / /Hebias + v HHestat-
(1 - m/jT+1
2
Proof. Here make shorthands for the sub-optimality gap and potential function: A V*d. Voa and Φ = ((T)). From Lemma 16 we have
B²G²
n (1 n/) - nerr, + 17
Taking expectation over the update weights, we have
B[nA,] & (1 .>)[[(.] - BB(err + +1² B²
Thus,
T T ' & [1 )1ri ) T-++ [ - Σ
T
E
11
πaa T- $
t=
16

---

Published in Transactions on Machine Learning Research (11/2023)
Algorithm 3 NPG: Sample-based NPG (full version).
1: Input: Environment E; learning rate y episode number T; batch size N; initialization du; sampler Ts regularization coefficient X; entropy clip bound U; optimization domain g.
for t 0, 1, ..... . 1 do Initialize F, 0dxd V, 04.
for n 0, N 1 do
5:
for h - 0, H do
6: if To is not None then
7:
Sh. an. AH-n(Shh an) - Sample (E, Rz, True, Te, h, A, U) (sec Algorithm 4
1/
d'in estimate 1 A m. (8,a).
8:
else
8/: 0h: A (sn, an) - Sample (E, Te, False, ne, A,,,,, U).
9:
1/ 8,0 a the no estimate H- (8,a).
10:
end if
11:
end for
12:
Update:
H-1
P. F++ +
Vo In no, (aklsk) (Vo In no, (anlsh))
H
V. V
An- (sh an) Vo In no, (an(sn)-
13:
end for
14: Call any solver to get 9: arg geg g Fig 2g" V
15: Update 0,+1 O2 ng:
16: end for
17:
Return: 0r.
G2 P
+ 1
(1 m/t) "-)"-=EEerrr Elerre] n/²
Σ
(1-1))-~~
(1
2
(=0
1=0
T
B²
E +
Σ
- (1--))== (PA)="'B(err))) + +1²
Σ
(1-1
(1
2
1-0
1-1
T
G²G² T
<
- nAa T
2u +
Σ (1- - naa
T- T-
+ np
Σ (1-
(1-
2
where the last step uses the fact that ((T) > 0. This is a weighted average, so by normalizing the cocfficients,
A(1 - + To
B²Ga
ΣT ET - 7A "Beer.
E
min A
DELET
1 (1 (1-mA)++1
2
E (1A T
X(1 - + 1o
B2G
+ 11
/ Hebias + / Hresttat
2
where the last step comes from Lemma 17 and Jensen's inequality. This completes the proof.
Aside from Remark we have extra remarks:
Remark 6. This is the first result for LMDP and sample- based NPG with entropy regularization. @ For any fixed À we have lincar convergence, which matches the result of discounted infinite horizon MDP
(Theorem 1 in Cayci al. (2021)): the limit when tends O(I(rTT) + +n) (which implies an O(1/VT)
rate), matching the result. in Agarwal et al. 2001
17

---

Published in Transactions on Machine Learning Research (11/2023)
Algorithm Sample: Sampler for duump where m Multinomial (wi,..., WMr), a UnifA if wnif True and Tsamp(+|s) otherwise, and estimate of A Hn
Input: Environment E; sampler policy Tsamp: whether to sample uniform actions after state unif: current policy #6 time step h; regularization coefficient X; entropy clip bound U. E.rese(().
3: for 0,1....,A do
4: 8; E.get
E.get_state(). state().
5: Sample action a, ~ (-)s) and E.xxccutoaa)).
end for
7: 8h < F.ttet -F.ett_state(] state().
if unif = True then
an UnifA.
10: else
11: an Taamp (-sh).
12: end if
13: (s,a) - (sk, an).
14: Get random number p ~ Uniff0, 1].
15: if < then
16: Override as --((s))))
17: Set importance weight C +- -2.
18: Th - E.exccute(aa).
19: Initialize cunulative reward R -- Tn + XH((T((16nn).
20: else
21:
C' 2.
22: Th E.executo(aa).
23:
R rh. + \ Amin(n Te(ap [b) U}.
24: end
25: for i h 1, 2..... H. do
26: 8; E.get state()-
27: a m.((ss)) and Th E.execute(aa).
28: R- R XH((TT(-Is;)).
29: end for
30: Return: s,a, A (s, = CR.
B Results of Curriculum Learning for the Best Choice Problem (BCP)
Theorem (Formal statement Theorem 7) For BCP, sel samp pi_s s Algoritim X Assume that
each number is independent from others and the i-th number has probability Ps of being the best so far (see
formulation in Section 4.1 and Appendir C. 1. Assume the optimal policy is p-threshold policy and the sampling policy is g-threshold policy. There crists policy parameterization and quantities
q E P. { ingggg T-P 1,
f-1
keurl =
Knaive 2!mpl max
max is (alnp]+ +2
II
2(1 P.) }
>
j=Inpl+1
such that keurl & Veurl & 2keurl and knaive & Knaive & 2k Here Heurl and Knaive correspond to induced the q-thi -threshold policy and the naive random policy respectively.
Proof. We need to calculate three state-action visitation distributions: that induced by the optimal policy, d:: that induced by the sampler which is the optimal for the curriculum, dourl, and that induced by the naïve random sampler, doavve This then boils down to calculating the state(-action) visitation distribution under two types of policies: any threshold policy and the naïve random policy.
18

---

Published in Transactions on Machine Learning Research (11/2023)
For any policy n, denote (i/i)) the probability for the agent acting under и to states i/n with arbitrary We do not need to take the terminal state g into consideration, since it stays in zero-reward loop and contributes 0 to L(g;0,) d). We use the LMDP distribution parameterization {Px] described in Scction 7
Denote "p as the p-threshold policy, iee accept and only i/n > p and ot
Then
Prreject all previous states/
1 = p
2
P
+1
n
n
71
(1- IP (2)1)
1-1pp|+1
Pz).
Ilppp+1
Denote Tnaive as the naive random policy, ie., accept any number with probability 1/2 regardless of the state. Then
1
d Tostive
P'reject all previous - states states|Tnaive) Tnaive) 2
For any n, we can see that the state visitation distribution satisfies d= (i/n, 1) P.d (i/n) and d" (i/n,
(1 - P))d (i/n).
To show the possible largest difference, we use a parameterization that for each state 8, o(s) = One-hot(s).
The policy is then satisfied into
exp(0T Te(aceept|s) exp(0) ((x))
(rejecct||s) exp(0 o(s))
because there are only two actions. Denote TT(s) ne (accept)s), we have
V In (acceptl)) (1
V (rejject)))))) = (s))s)((ss).
Now suppose the optimal threshold and the threshold learned through curriculum are and q, then o(s)
Σ
(s) (T) = + (1
S
a deurl
Σ (s)
1/2 (1- - =T(ss)² + T d(s)o(s)
S
(1
d junive
Σ (maive(s)
[1 m + = (())((s)
Denote K& (0) d
x Far d
From parameterization know all d(s) are orthogonal. Abusing Ty with
Neurl; we have
d'rr() (8) (TT (s) (8))) + (1 x (s))
(0) max SES
8) (1 (1-+)(>)) (2)) + (s)))
We can separately consider each s S because the orthogonal features. Observe that Tp(s) {0, 1}, so for S, its corresponding term in Ka (0) is maximized when TT(s) 1 (p(s) and is equal to 2 dd)
19

---

Published in Transactions on Machine Learning Research (11/2023)
By definition, K maxpgesT (0))) Since 80 0%, we have Ki 2 (0*) where no(s) 1/2 and the corresponding term (s)(s) So [a)
(s)
Fig = 2 max d seS d
a (s)
We now have an order-accurate result & = max,ES
(a) for Rg. Direct computation gives 2
1 1 P- $ P.
Keurl
1,
9>> p.
i-1 II
Knaive = 2|mpl max
1, max
2(1 Pj)
La [pp] +2
1= j=|mp|+1
This completes the proof.
C Full Experiments
Here are all the experiments not shown in Section 7 All the experiments were run on server with CPU AMD Ryzen 9 3950X, GPU NVIDIA GeForee 2080 Super and 128G memory. For legend descrip- For code please refer to https://github. com //e/uuooouunoog////
tion please refer the caption of Figure
RL Au-oor-Comminatrrrii----iiaaaai
Policy parameterization.
For BCP and OKD, there are exactly two actions, so we can use Φ(s) accopt ((s reject)
instead of o(s, and reject).. Now the policy is To (accepp)))s)
exp(O d(s)) exp m(+))+I and
mo(reject[s)
exp(O +())++I
For ADW, there are n + actions (n for assigning slot to advertisers and 1 for not assigning it). So, must follow the canonical form of log-linear policies.
Training schemes. We ran nine experiments in total, four for BCP, three for OKD, and two for ADW. The difference between the experiments of the same problem lies in the distribution over instances (i.e., (wm)). In the following subsections, we will introduce how parameterized the distribution in detail. single experiment, policies of the final phase, and whether used regularization. For visual clarily, we did not plot setups with entropy regularization, but the readers can plot it using plot. py in the supplementary files. We make detailed list of the training schemes in Table [
eight sctups, cach representing a combination of sampler policics, initialization
C.1 The Best Choice Problem (BCP)
State and action spaces. States with X; > 1 are the same. To make the problem "scale-invariant" we use i/n to represent So the states are s (i/n, x2 = 1[X, = 1]). There is an additional terminal state (), For each state, the agent can either accept or reject.
Transition and reward. Any action in g leads back to g. Once the agent accepts the i-th number, the state transits into g, and reward is 1 if is the maximum in the instance. If the agent rejects, then the state goes to ((i + 1)/n, 11+1) if < and g if i = For all other cases, rewards are 0.
Feature mapping. Recall that all states are of the form () where f E 10, x E {0, 1). We set a degree do and the feature mapping constructed as the collection of polynomial bases with degree less than do (d 2do):
Φ(fx*) (1, po xr, fx,,.., -
20

---

Published in Transactions on Machine Learning Research (11/2023)
Abbreviation
Detailed setup
Script
sos_samp_cuu
Fixed sampler curriculum learning. In the warm-up phase, train a policy 7a from scratch (with zero initialization parame- ters) using a small environment E'. In the final phase, change to the true environment. E, use H. the sampler policy to train policy from scratch.
Run
Alg with
samp = pi_s and
À
fix_samg ex__samp_curl___
The same as _ex__sam_co___ but add en- tropy regularization to both phases.
Run samp
Alg 2 with
pi_s s and
A + 0.
direct
Direct learning. Only the final phase. Train a policy from scratch directly in E.
Run Alg On and
with
04, Rs
None
0.
direct_reg _re
The same as direct, but add entropy regularization.
Run Alg 1 On
with
0 Tx
None
and
* 0.
naive_samp
Learning with the naïve sampler. Only the final phase. Use the naïve random pol- icy as the sampler to train a policy from scratch in E.
Run Alg. | with
Og = 0 T. naive
random policy and
=
naive_samp_ree
The same naive samp, but add entropy regularizatio..
Run Alg. 1 with
On 04 n. naive
random policy and
À 0.
curl
Curriculum learning. In the warm-up phase, train policy na from scratch in E'. In the final phase, change to E and con- tinue on training T.-
Run Alg. 2 with
samp
pi_t and
A = 0.
curl_reg
The same curl, but add entropy regularization.
Run
Alg 2 with
samp
pi_t and
A * 0.
reference
This is the reference policy. For BCP, it. exactly the optimal policy since it can be calculated. For OKD, it is bang-per-ben policy and is not the optimal policy (whose exact form is not clear). For ADW, it is the near optimal policy in our restricted policy feature class (trained using curriculum learning).
N/A
Table 1: Detailed setups for each training scheme.
LMDP distribution. We model the distribution as follows: for each i, we can have x; = 1 with probability P. and is independent from other z' By definition, P1 = while other P. can be arbitrary. The classical BCP satisfies P; 1/2. We also experimented on three other distributions (so total there are four experiments),
each with series of numbers p2, P3:- .......1 Pn.
iidd Unif and set P; 1/22p.40.25.
21

---

Published in Transactions on Machine Learning Research (11/2023)
eight setups, each with different combinations of sampler policies, initialization policies of the final phase, and the value of regularization coefficient X. For the warm-up phases we set n = 10 and for final phases n = 100.
For each experiment,
Results. Figure (with its full view Figure 5) Figure 2018011309 show four experiments of BCP. They shared learning rate of 0.2, batch size of 100 per step in horizon, final n = 100 and warm-up = 10 (if applied curriculum lcarning).
Figure along with Figure (with seed
The experiment in Figure was done in the classical BCP enviromment, i.e., all permutations have probability 1/n! to be sampled. Experiments Figure [ Figure and Figure 7 were done with other distributions: the only differences are the random seeds, which we fixed and used to generate P&s for reproducibility.
The experiment of classical BCP was run until the direct training of n 100 converges, while all other experiments were to maximum episode of 30000 (hence sample mumber of THb 30000 100 x 100 3 x 10a).
The optimal policy was derived from dynamic programming.
fix samp curl
Taive_sampy
direct
curl
reference (C)
(b)
(c)
0.4
0.3
40
log(Kappa)
reward
avgle (erre
0.2
20
0.1
Muw
0.0
3
sammle
1e8
#sample
1e8
#sample
1e8
Figure 4: Classical BCP, truncated to 3 10 samples.
fix camp_curt
naive_samp
direct
curl
reference
b
0.4
0.3
log(Kappa)
40
avg (err 1)
reward
0.2
20
0.1
0.0
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
#sample
1e9
#sample
1e9
#sample
1e9
Figure Classical BCP, full view.
2 All the four trainings shown in the figures have their counterparts with regularization (A 0.01). Check the supplementary files and Tensor Board for lization...
22

---

Published in Transactions on Machine Learning Research (11/2023)
fix samp_ curl
naive_samm _amee_sappp
direct
curl
reference
(b)
(C)
0.4
40
1.0
0.3
log(Kappa)
avg(err H)
reward
0.2
20
0.5
0.1
0.0
0.0
3
2
3
0
#sample
1e8
#sample
1e8
#sample
1e8
Figure 6: BCP, with seed 20000308.
fix samp_cum curl (a)*
maive_samp
direct
curl
reference
(b)
(C)
0.4
40
reward
0.3
(ag(Kappa)
1.0
(err
0.2
20
0.1
0.0
0.0
0
3
0
2
#sample
1e8
#sample
1e8
#sample
1e8
Figure 7: BCP, with seed 19283746.
C.2
Online Knapsack (decision version, OKD)
State and action spaces.
The states are represented as
Σ 15
81, Us;
B
V
where zj 1[item j successfully chosen] for & j < i - 1 (in the instance). There is an additional terminal state = (0, 0, O, 0) For cach state (including g for simplicity), the agent can either accept reject.
Transition and reward. The transition is implied by the definition of the problem. Any action in terminal state y leads back to g. The item is successfully chosen and only if the agent accepts and the budget is sufficient. A reward of 1 is given only the first time Σj 1a4e > V, and then the state goes g. For all other cases, reward is 0.
Feature mapping. Suppose the state is (f, u, r, q). We set degree do and the feature mapping is constructed as the collection of polynomial bases with degree less than do (d dz): o(f,,v,r,d 1}.
pfupttgg Saddurrd where is E (0,
LMDP distribution. In Soction 3.2 the values and sizes are sampled from F, and F,. If F, or F, is not Unifio.1), we model the distribution as: first set a gramularity gran and take gran numbers Pl: Pgran iid. Uniffo,1-- P; represents the (unnormalized)) probability that x E ((i //gran, pttpiioommalppppp........
To sample, we take
and return x (i 1+ (niffo.u)/gran.
For each experiment, we ran four setups, each with different combinations of sampler policies and inittaliza- tion policies of the final phase. For the warm-up phases 10 and for final phases set 100 in all
23

---

Published in Transactions on Machine Learning Research (11/2023)
experiments, while B and V vary. In one experiment it satisfies that B/n are close for warm-up and final, and V/B increases from warm-up to final.
Results. Figure Figure along with Figure 2 (with Fg F. 11) show three experiments of OKD. They shared learning rate of 0.1, batch size of 100 per step in horizon, final n 100 and warm-up = 10 (if applied curriculum learning).
Experiments in Figure X and Figure were done with other value and size distributions: the only differences are the random soeds, which we fixed and used generate F, and F, for reproducibility.
All experiments were run maximun episode of 50000 (hence sample number of Tbb 50000 100x 100 5 x 10*).
The reference policy is a bang-per- per-buck algorithm (Section 3.1 of Kong et al. 2019 ): given threshold accept i-th item if 0//8; s r. We searched for the optimal r with respect to Online Knapsack because we found that in general the reward is unimodal to r and contains no "plain area", so we can easily apply ternary search (the reward of OKD contains "plain area").
fix sas_sap__com curl (a)
naive_samp
direct
curl
reference
(b)
10.0
0.2
0.2
log(Kappa)
7.5
avg(err (t)
0.1
0.1
0.0
2.5
0.0
0.0
-0.
2
0
2
4
2
#sample
1e8
#sample
#sample
1e8
Figure OKD, with seed 2018011 1309.
fix samp_ccm curl (a)
haive_samp
direct
curl
reference
(b)
(C)
0.2
0.2
reward
avg(err
0.1
0.1
5
0.0
0.0
#sample
1e8
#sample
1e8
#sample
1e8
Figure 9: OKD, with seed 20000308.
C.3 AdWords (decision version, ADW)
State and action spaces.
The states are represented as
j _ Vi 02.h Un.j. Bi, B2, Bay
V
where V, equal to the total revenue up until now. There an additional terminal state g 02x+2, For each state (including g for simplicity), the agent has n 1 actions, with representing assigning the slot and 1, 1,..., representing assigning to the corresponding advertiser.
24

---

Published in Transactions on Machine Learning Research (11/2023)
Transition and reward. The transition is implied by the definition of the problem. Any action in terminal state leads back to g. The slot is successfully assigned to advertiser if and only if the action is i and B; E o.j. The next state is then with B; - B; vi and V3 - V + Vidi A reward of is given only the first time Vj + Vi.5 2 V, and then the state goes to For all other cases, reward is 0.
Feature mapping. The feature design in ADW is bit tricky, since the state dimension is super large. We simplify the sctting by assuming all the advertisers are symmetric, so we design function Φ and for action 1 & isin n,
De, Φ ( 1 (,, Bir V2 m
and
0n.0 @ (2. ( V
V/2
Actually, not assigning the slot is equal to assigning the slot to virtual advertiser with value O.
We set a degrec dg and off, v. B. is constructed as the collection of polynomial bases with degrce less than do (d = d)): olf u. g) = (f Bir'tBBiggh 3'"g'") (iy duddddd where i (0.1..... do 1).
LMDP distribution. In Section 3.3 the values vi are sampled from F. If F; not Unifju,1J, we model the distribution in the same manner in OKD. For each experiment, ran four setups, each with different combinations of sampler policies and initialization policies of the final phase.
In the experiment depicted in Figure For the warm-up phases we set (n, m) = (3, 6) and V = 2.7. For final phases we set (n, m) = (10, 20) and = 9. The distributions are parameterized random ones with gran 10.
In the experiment depicted in Figure 10 For the warm-up phases we (n, m) (3, 6) and V 2.64. For final phases set (n, m) = (8, 32) and V 7.04. The distributions specially designed distributions, with probability it has 0.4 value, and the rest 1 - p mass is random on (0.6. 1). This distribution type has special near optimal policy class: either pick two 0.4, pick anything in (0.8, 1).
Results. Figure 3 and Figure TO are experiments of ADW. They shared learning rate of 0.1 and batch size of 100 per step in horizon.
The reference policy is obtained by first running curiculum learning, then using the learned policy as the reference policy. This is because after we simplify the feature representation, we need to compare with the near optimal policy inside this restricted policy / feature class.
fix samp_cum curl
_amv
direct
curl
refgrence
(b)
0.4
log(Kappa) 3
avg(errrt) t)
reward
2
0.2
0.0
1
2
0
2
3
#sample
1e7
#sample
1e7
#sample
1e7
Figure 10: ADW, with seed 19260817 and special distributions.
25

---

Published in Transactions on Machine Learning Research (11/2023)
D Technical Details and Lemmas
D.1 Natural Policy Gradient for LMDP
This section is a complement to Scction We give details about the correctness of Natural Policy Gradient for LMDP.
Theorem 12 is the horizon Policy Gradient Theorem for LMDP, which takes the mixing weight {um} into considcration.
According to Agarwal et al. 2021 the unconstrained, full-information NPG update weight satisfies F(0:)ge = VoV Lemma 13 and Lemma 14 together show that: it is equivalent to finding minimizer of
the fitting compatible function approximation loss (Definition B
Theorem 12 (Policy Gradient Theorem for LMDP). For any policy we parameterized by 0, and any & m M,
H E a de
Vo E
VM
Σ h=1
As result,
M Σ
VolV
Wm
E
Be m.
m=1
Proof. For any 1 & h & H and SE S, since Vi (s) = Tocesto(als))0. (s, as, we have
V (s) = Σ
(omen
m.h
aEd
Hence
H
H
Σ
Σ
(e) = Σ
Σ
m. (n)) Σ
d
(mee as) + voldss)
h- SES
s
acA
Σ
d
m, (s Σ
(s. 1(4.)/
aES
aEA
H
Un.H-hh (m))) Σ V
1=1 SES
aEA
H
E
1e H-h
H
m. H (8))
Σ
Ta(als) Volals)
h-1 SES
aeAA
Next we focus on the second term. From the Bellman equation,
VoQ = V, (Ta(ssa)) - Alnmo(als)+ + Σ P(s'ls, Vo) 1
ses
(npoaa) + Σ [( ( (5')
SES
Particularly, VoQTi" In So
Σ Σ 0 (s)) Σ Vo
R- 1 SES
aeA
26

---

Published in Transactions on Machine Learning Research (11/2023)
H
Σ
Σ
l H (s() Σ TT(aas)
[VVolu Σ a(dlss,) mi
#ES
REA
SES
H
H
m, (s))
(olo(
+
Vo Fo m,h-1 (5) Σ
d
m. (s() Σ
no (ss(ss)
1= SES
aEA
h= SEES
SES
aEd
H
Σ
Σ
m H -- htt' m.h-1 (5')
h=2
Σ
Σ
d
mf (s
(o mih
Σ
Vm (Su) Vo V (sp),
h=1
#065
where we used the definition of d and Vm- So by rearranging the terms, complete the prool.
Lemma 13. Suppose D E R=xm D diag(d1, d2,.... .mm) (TDrT)DDg is solution to the equation DDD x ID4.
dm) e mxx where dj and q R then
Proof. Denote D1/2 diag(vdı, ,d dd DD .p DV/2g. then the equation is reduced to
PPT x Pp. Suppose the singular value decomposition of P is UEVT where U E Ru Raxm, V e R where U and V are unitary, and singular values are 01, 02 (
So PPT = U( and
Notice that
ΣΣ
0) R"**
we can then derive the pseudo- inverse of this particular diagonal matrix as
(Σ yt = diag(a - ,000z ...... 2,,.,,.......
It is then easy verify that (EE (EET) E. Finally,
PPT x = (PPT)((PPT) Ppl
=U(EET JU USEE JUTVET
-U(EET) (EE) (EE")EVT, "EV
=UEVT
Pp.
This completes the proof.
Lemma 14 (NPG Update Rulc). The update rule 0 - + nF(()
(F((F))(VVo))) VoVaod
where
M
H
F(0)
Σ
W
E
m.
m=1
is equivalent to 0 + ng", where g" is a minimizer of the function
M
(
(ATT - Vo (n mit
[(gg)
W'm
H.
Proof.
V Lg) = - Σ Wm
E
B
[AT (s, -9 - Vollmo())s) Vo vo
H
m=m
1=
27

---

Published in Transactions on Machine Learning Research (11/2023)
Suppose 9" is any minimizer of L(g), we have vgL(gg)) = 0, hence
M
H
Wm
E s
[9 In m)(()))) Vo Volnmo(als))
M
H
Σ
Wm
E as
d H-h
A V
M
H
Wm
E gg d0
Since (u t)v (ve) )u, )u, then
F(0)g* VoVTO.A
Now we assign ,, MHSA as indices to all (m, h a) fI...., M3 x (I....,... H} x S x A, and set
yj = [olnso(a(s))
dj Wm d (m
= Q (s.
where j is the index assigned to (m, h, 8, a). Then F(0) = DD and V,V² DDq where
r = [n, 72, YMHSA E U
diag(dı, d2.................. ..... dMHSA) MHSAMMHAA
q = 14,, 42. [MHSA] RHSA
We now conclude the proof by utilizing Lemma 13
D.2 Auxiliary lemmas used in the main results
Lemma 15 (Performance Difference Lemma). For any two policies Ti and IT2 and any 1 & & M,
11
A a) + Aln (2(a T (a|s)
Eeg~Vm Vm VITI V. (80) = Σ
VM
EE Ex
di H.H
As result,
M
H
A Taid (s. a) + Aln T2(a|3)
Vand Vona
Wm
E
H-
TT (((ss)
Proof. First we fix 80- By definition of the value function, we have
V
a (so)
m.
H
T' (Sh, an) - A Aln (lmss(a))s)
Mm, T 80
-Vminn (su)
I'm (Sh, an) - (lnm(a VT2id (
Vi (
Mm, T1,
(m an) - -IInz((alls) +
Mm, R2, 8n, an
Mm, 01,
28

---

Published in Transactions on Machine Learning Research (11/2023)
v m, (3h) + Aln (2) T (a (h))
Σ
Mm. T 80
where the last step uses law of iterated expectations. Since
(mh ap) - Aln + m. -m Mm T2, sh, an = (sh, an), E
we have
H
V (sh) + Aln (2(an) sh) Ti (ap (h))
VATLA (8o) (80)
E
@ H (sh, an)
Mm, T1,
122. m, (8h, an) AIn T2(an)51)
E
Mm: mı; 80
Ti (ap 8h)
By laking expectation over 80, we have
Eg Mmm (T
=
H-1
Σ
A va.d
m, - (sn an) Aln x2 (8h)
Mm, #1
T (1 sn)
H
A =2 Am + Aln T2(a(s)
Σ
dhi (0,
T (a|s)
h-0 (s.a)ESxA
The proof is completed by reversing the order of h.
Lemma 16 (Lyapunov Drift). Recall definitions in Definitions 5 and We have that:
((T++1) - ((T)) & -m))((Te)) + nerr (V+r VOd) + B² 1
Proof. Denote O ((T.). This proof follows similar manner as in that of Lemma 6 in Cayci al. (2021
By smoothness (see Remark 6.7 in Agarwal et al. (2021)
In Te(a|s) (ass(a & (0c- - Bet1) Voln
B² 1
2 0.1
172 B²
1
= V lo
2
By the definition of Ø,
din In (e(a)s) (ats(a)s)
P++11
$,
Σ
Wm
M
H
7 B B²llgall
[ot Vo lu (als]] +
-Y) 7)
Wm
By the definition of err,, Lemina
15 and again the definition of d we finally have
M
( A m, (8, a) gl V lnm(ass)))
$
11+1
Φ & 17
Wm
(s.a)~d' di
N-hh
m
M
H
Lnd A (8,, a) + An (a(a)) (a|s)
1)
Um
B(e,0)
m M-A
m=
h-
M
F
In n (als) my (a(s))
n" 2 9e
771
Wm
E (s.aa)ddt..n
2
771
29

---

Published in Transactions on Machine Learning Research (11/2023)
- V(A) -nAi, + 1f2 = mjrTT - 17 -V
2
which completes the proof.
Lemma 17. Recall that gi is the true minimizer of Lig: 0,, in domain g. err, defined Definition satisfies
err, & : d') + HHi Ligi 0g, (z,d"))
Proof. The proof is similar to that of Theorem 6.1 in Agarwal et al. 2021 We make the following decom- position of erry:
H-1
eIT,
W/m
E (s.a)
(An 9t Vo (als)
h=0
H B( [1yt 9t) Vo Polnm (a)s)
m=1
h--
Since MM Wm - E(sa)eSxA (s H, normalize the coefficients and apply Jensen's inequality, then
M
H-1
M
H-1 Σ
Σ Wm 77
Σ
d (m)((s,a)
Σ Wm
E (s.a) ada
[Ahhs((s - si" Vo Vo (m()ss))))
h=u
(s.n)eSxA
770
h=0
Similarly,
H-1
[(ot 9t) (o
H
Wm
E ((.
0
H
Wm
E (s.0)~
[[g V (n (alss) Tot 9.)l
1=0
2
9t
Hillgt gell2..
where (i), for vector v, denote |e]la = VUT Av for a symmetric positive semi-definite matrix A. Due to that oi minimizes L(g Oz, d') over the set G, the first-order optimality condition implies that
(g - ( TV, 02 d') >
for any g. Therefore,
L(g: l2, d²)
L(gt: 0c, )*)
M
( [Atth gi Vlnm((a))) + (gf - -g) [In - L(gt; Oz,
Σ
Wm
F B.aad df
m=1
M
11
Σ
Wm
E Ba
[(0i- -g) (o
H-N
m
30

---

Published in Transactions on Machine Learning Research (11/2023)
M
H
+ - -
-2 Σ
Wm
(4n a) VV (n Vo lmm((ass))
= = E, + (g - 9:) (V.]Vooo V 5 02.
> 19 9 E..
So finally we have
eTT, < 0 Hn - L(gi; d)))
This completes the proof.
D.3 Bounding Cstat
Lemma 18 (Hoelfding's Inequality). Suppose X1, X2,..... Xn are i..dd random variables laking values in [a, b], with expectation μ. Let X denote their average, then for any 2 0,
P( - Ml p|>c
2exp (-
2nc²
a)²
Lemma 19. For any policy n, any state E S and any U 3/ In |A|
- 1,
o Σ
T(als)
1
xalss) min Σ aEA
1
U
A
T[ass))
T(ass)
cU+I
AEA
Proof. The first inequality is straightforward, so we focus on the second part. Set A' fa U} = {a n[als)= < d } and p EeEr T(als), then
In
Σ {(cls) In 1 Σ
(a|ss) min In 1
Σ
T(ass)
In
Σ {(ass)
<(ass) asA
(a|s))
T(aas)
A
aEA
T(als)
p
In
([als)
PU
P
aeA
π T(lss)
< pln
Σ
PU
P x(a|s)
A - -U,
< <ln
where the penultimate step comes from concavity In and Jensen's 's inequality. Let f(p) = pln 14 pU, then (p) = In |A| U - 1 - Inp. Recall that > In |A| - 1, so f(p) increases when E (0, ( and [A| decrcases when e (ob1). 1). Since f( f( 2+ we complete the proof.
Lemma 20 (Loss Function Concentration). If set w, None and U > In |A| 1, then with probability 2N22 the updale weight sequence of Algorithm 3 salisfies: for any O & l T,
1-2(T 1) exp
c
L(ār; 0z, dd.)) L(gi;0e, ) < 2e + SAGBIA
eU+
where
16HGG[ + XU + H(1 + Aln Aln[ 4HG²
If n. * None and X 0, then with probability 1 - 2(T + 1) exp (-2Ne') ) the update weight sequence of Algorithum 3 satisfies: for any 0 < t & T,
( 0,, d L(gi: 0r, dda & 2c,
31

---

Published in Transactions on Machine Learning Research (11/2023)
where
C 16H 4H
Proof. We first prove the n = None case. For time step i, Algorithm 3 samples HN trajectories. Abusing the notation, denote
N
H
F
Vy In no (a (Vo In ((n
N
N
H-1
Σ
An and Vo In Te(an,
N
M
H
((9)= =
Σ
Fig 2g V. As, + di u-
Wm
h=1
Notice that @ is constant. From Algorithm 3 De is the minimizer of @ (hence I(g) inside the ball g. From Vo In re((s)) d(s, a) (o-)) a²) ]] (0(s,)) a2 & B, 1l912 < G, we know that [g V V ln (o <
2GB. So 0 & g P.g & 4HG² From Algorithm we know that any sampled satisfies | $ 2 + XU +
H(1 AIn [A)] So 1g V, & 4HGB AU + H(1 + AIn]AA)] We first have that
SHGB + AU H(1 + AIn A|) 2 SHGB + AU H(1 + A [A)] B2
(2)
To apply any standard concentration inequality, we next need calculate the expectation of @. According to Monte Carlo sampling and Lemma 19 for any 1 & & M. h & H and (s, a) E S A, we have
ALA
A mi (8, a)
E
A (8, (s,
Denote V, as the exact policy gradient at time step 4, then
9
V.
<
lgla
E G V.
V (a(1)))12 E [(s,,a)] A(s,00).o
1992 H
A
Since Monte Carlo sampling correctly estimates state-action visitation distribution, E P.
F(O.). Notice
that g" Fig is linear in entries of Fr, we have g Fig = =FF(() Now we are in the position show
that
E
[1)O]
T(9) &
4XGBIA cU+l
Hoeffding's inequality (Lemma 18 gives
PP (((0)) - [E(()]
> >c) < exx
(- C22
(_2Ne² 22Ne2
where from Equation
C 16HGB| XU H(1 Aln |4) B2
32

---

Published in Transactions on Machine Learning Research (11/2023)
After applying union bound for all t, with probability 1 - 2(T + 1) exp (22
the following holds for any
g e g:
1(g;0r, T(g; (c Ect 4AGB|A
cU+l
Hence
) + A
L(ūr )) L(gri 02, )),
eU+1
Ligh 02, (),ddi),+ + 4)GB|AI
cU+11
SAGBIA
00, + 2c +
cU+1
For * None and x 0, we notice that |A| < 2H and hence -HPGB < 2 < SH + 4
Morcover, E Am, a) = Am,nss a). So by slightly modifying the proof we can get the result.
33


Reviews:
[{"review_id": "r9MwHtrbQ6", "reviewer": "Reviewer_dyf8", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall I like the paper and appreciate the insights. Like all papers, there are weaknesses. However, there are some issues that really detract from the quality of the paper that I hope the authors can fix.\n\nStrengths:\n- The paper studies an interesting and important problem. In particular, the continued use of RL to optimize problems in other fields, such as combinatorial optimization, is interesting. \n- The results provide formal insight into how curriculum learning can be helpful for policy optimization (exponentially so).\n- The results also suggest that methods of prior work can be simplified.\n\nWeaknesses:\n- While the results are certainly informative, the paper is very unclear. \n    - Algorithm 2 says to construct an easier E’ form E. This is very vague and nonspecific. What is an ‘easier’ environment? Certainly There are many that one can think of that are not very informative and others that are informative but still hard to solve. While I think it’s okay to be nonspecific to maintain generality, the paper does not do a good job of providing concrete examples of elaborating on characteristics that would satisfy this condition. The only part that sheds light on this is Section C.1 in the appendix where it is finally concretely revealed what the curriculum problems look like. This should be discussed when Algorithm 2 is introduced and then concretely stated in Section 7 of the experiments. Overall, it’s important to define the curricula in the main paper.\n    - It’s not clear why the problem is formulated as an LMDP, even though it can be. One of the major insights of the LMDP is that they are hard to learn in general, but can be made easier with either hindsight information or some separability. Neither of those are really used to great effect here. Why not model it as a normal MDP/POMDP where you drop some state information? It’s also not clear what gains can be made from such a formulation in theory either since regret bounds for LMDP typically depend polynomial on the number of MDPs, which is exponential for BCD.\n    - The lack of history-dependence is a little concerning for some problems. For instance, the BCP has a state that only contains the current position and rank. While this is enough for the worst-case optimal policy, it seems like it was  formulated with prior knowledge that the optimal policy does already look like this rather than letting the algorithm discover this or find a better solution. For certain distributions, you might be able to do a lot better with history-dependence. Related to this, I believe the LMDP paper does use history-dependent policies (contrary to the claim in the present paper in Section 2).\n- The results on CO problems do not appear to be very strong compared to reference baselines. It’s not clear that the methods studied here show promise for finding stronger algorithms for specific problem instances or distributions over instances. However, this is not a big deal in my opinion because the insights are still useful and it’s good proof-of-concept.\n- There is not a significant algorithm contribution, but the insights are still useful.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of reinforcement learning to solve combinatorial optimization problems. The proposed method is to use curriculum learning along with a policy optimization procedure to ensure more scalable learning of the optimal policy. Some theory is provided to justify the use of curriculum learning as reducing the distribution mismatch exponentially. The methods and analyzes are applied on 3 combinatorial problems BCP, OKD, and ADW.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "My primary recommendation is to fix the clarity issues mentioned above, which will require some significant changes to the writing, but I think it’s most definitely doable for a revision.\n\nMinor suggestions:\n- BCP is not really a combinatorial problem. It’s more of an optimal stopping problem. I would note this somewhere where it is introduced such as 3.1\n- All the CO problems should have citations to relevant texts/surveys/original papers on the topic.\n- In OKD, why not just work with the original variant that gets to observe the reward to optimize? Doesn’t the policy get to see the value anyway at each timestep? It seems like this was artificially made difficult.\n- A lot of important information about how the CO problems are formulated – such as state spaces, actions spaces, rewards – are missing from Section 4.1 and have been relegated to Appendix C without a link. I would advise including this information in the main paper. At the very least there should be a reference to the appendix.\n- Section 6.2 second sentence: should this be i/n instead of 1/n?\n- Section 7 first paragraph is vague and imprecise (see “more than one experiment” and “In one experiment there are more than one training processes”). I would either leave out sentences like this or be more precise or put them where they are relevant.", "broader_impact_concerns": "No concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8AmZrZC6yE", "reviewer": "Reviewer_d4qr", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- The main weakness of the paper is their theoretical result. In particular, Theorem 6 is essentially the same as the results in Agarwal et al 2021. Also, since Theorem 7 only provides an upper bound, we cannot argue for improved performance of curriculum learning based on Theorem 7.\n- Another issue is the experimental results. In particular, the performance of the dashed line is unrealistically bad. We observe flat zero reward for the baseline after 1e7 samples. Did the authors make sure the baseline is tuned carefully enough?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies Combinatorial Optimization (CO) problems combined with curriculum learning. The authors study the performance of modeling with problem as an LMDP and using NPG to solve this problem. In order to motivate and study the performance, the authors consider several case studies and analyze the performance of their algorithm applied to these cases. \nThe authors also provide a theoretical analysis for the convergence of their algorithm.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Can you add comparison of your result with the best method which does not use RL for solving these CO problems?", "broader_impact_concerns": "The paper is mainly mathematical and a simulation based on synthetic data. I believe broader impact is not necessary.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "WMFoonH1eW", "reviewer": "Reviewer_KbY1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths:\n\n- The connection of online combinatorial optimization and latent Markov decision processes explored in this work is new and interesting, introducing a fresh perspective to the understandings of CO. \n\n- The theoretical findings underscoring how CL accelerates the reduction of the condition number $\\kappa$ serves as a important tool to explain the efficacy and the foundational mechanics of CL. This could be a interesting contribution to the academic community.\n\n- The paper is overll well-written and easy to follow.\n\n\n## Weakness:\n\n- The set of problems considered in this paper appears to be relatively narrow. There's a doubt regarding the relevance of these problems to the broader machine learning community. An exploration or at least a discussion about the potential to extrapolate these findings to other Reinforcement Learning (RL) problems would enhance its relevance, as CL has been wildely studied and used in many RL algorithms to solve the task, see https://lilianweng.github.io/posts/2020-01-29-curriculum-rl/.\n\n- The paper restricts its theoretical studies majorly to NPG. I wonder if it's possible to replicate similar insights or theoretical results for other RL algorithms, e.g., value based methods.\n\n- It would be beneficial if the authors could include a discussion on how to construct a curriculum for more complex problems. While it may not be very challenging to construct a sequence of curriculum for the problems addressed in the paper, devising a suitable curriculum for more intricate issues remains a significant challenge.\n\n\n- The theoretical analysis in Section 6 appears somewhat incremental. Given the existing comprehensive understanding of NPG and the similarity between LMDPs and standard MDPs, the analysis seems quite straightforward.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the effectiveness of policy optimization for online combinatorial optimization (CO) problems, which frames online CO as latent Markov Decision Processes (LMDPs). The authors first proved convergence bounds of the natural policy gradient (NPG) for solving LMDPs. Then, the authors shed light on the advantages of curriculum learning: primarily, its potential to establish a robust sampling policy and significantly diminish the distribution shift. In the context of BCP, the authors demonstrates that the distribution shift will have an exponential reduction with curriculum learning, irrespective of whether the curriculum is a randomly generated BCP on a smaller scale. Their insights suggests that Curriculum Learning's primary contribution lies in facilitating a more potent sampling policy, which in turn lowers the relative condition number $\\kappa$. To bolster their arguments, the authors also provide empirical results on simple problems.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See Weaknesses in the above section.", "broader_impact_concerns": "Not applicable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes to combine curriculum learning and policy optimization for reinforcement learning to solve online combinatorial optimization problems. All reviewers think that the problem studied is interesting, and the theoretical results on the BCP problem are insightful, and they all recommended acceptance. These are nice first steps towards understanding the utility of curriculum learning for real-world application of RL, including other online combinatorial optimization problems.
Decision: Accept (poster)