Understanding Curriculum Learning in Policy Optimization for Online Combinatorial Optimization
Authors: Runlong Zhou
Yuandong Tian
Yi Wu
Simon Shaolei Du
Venue: Submitted to ICLR 2023 (2023)
Keywords: reinforcement learning theory
curriculum learning

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, Secretary Problem, we formally prove that distribution shift is reduced exponentially with curriculum learning even if the curriculum is randomly generated. Our theory also shows we can simplify the curriculum learning scheme used in prior work from multi-step to single-step. Lastly, we provide extensive experiments on Secretary Problem and Online Knapsack to verify our findings.

Under review as a conference paper at ICLR 2023
UNDERSTANDING CURRICULUM LEARNING IN POL- ICY OPTIMIZATION FOR ONLINE COMBINATORIAL OP- TIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Over the recent years, reinforcement learning (RL) starts to show promising re- sults in tackling combinatorial optimization (CO) problems, in particular when coupled with curriculum learning facilitate training. Despite emerging empiri- cal 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 strong sampling policy and reduce the distribution shift, a critical quantity that governs the convergence rate in our the- orem. For canonical online CO problem, Secretary Problem, we formally prove that distribution shift is reduced exponentially with curriculum learning even if the curriculun is randomly generated. Our theory also shows we can simplify the cur- riculum learning scheme used in prior work from multi-step single-step. Lastly, we provide extensive experiments on Secretary Problem and Online Knapsack to verify findings.
INTRODUCTION
In recent years, machine learning techniques have shown promising results in solving combinato- rial optimization (CO) problems, including traveling salesman problem (TSP, Kool al. (019)). ) maximum cut (Khalil et al., 2017) and satisfiability problem (Selsam et al. 2019). While in the worst case some CO problems
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 class of CO problems.
significant subclass of CO problems is called online CO problems, which has gained much atten- tion (Grötschel al.) 2001] Huang H 2019; Garg al., 2008). Online CO problems entail a sequential decision-making process, which perfectly matches the nature of reinforcement learning (RL).
This paper concerns using RL 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 (Pérez-Datarr et al. (2018). Schollen al. (2019). ). and policy aggregation (boosting, Brukhim et al. (021)). Practitioners use these techniques to accelerate the training speed.
While these hybrid techniques enjoy empirical success, the theoretical understanding is still limited: it 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 an 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 tackle online CO problems, with a particular emphasis on understanding the specialized techniques developed in this emerging subarea. Our contributions summarized below.
Formalization. For online CO problems, we want to learn a single policy that enjoys good perfor- mance distribution of problem instances. This motivates to Latent Markov Decision

---

Under review as a conference paper at ICLR 2023
Process (LMDP) (Kwon et al.) 2021a) instead of standard MDP formulation. We give concrete examples, Secretary Problem (SP) and Online Knapsack, to show how LMDP models online CO systematically analyze RL algorithms.
problems. With this formulation,
Provable efficiency of policy optimization. By leveraging recent theory on Natural Policy Gra- dient for standard MDP Agarwal et al. (202T) we analyze the performance of NPG for LMDP. The performance bound is characterized by the number of iterations, the excess risk of policy evalua- tion, the transfer error, and the relative condition number x that characterizes the distribution shift between the sampling policy and the optimal policy. 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 RI. 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 the Secretary Problem, we provably show that Curriculum Learning can exponentially reduce K compared with using the naive sampling policy. Surprisingly, this means even a random curriculum of SP 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 under- standing, we study the failure mode of Curriculum Learning, in a way to help practitioners to decide whether to use Curriculum Learning based on their prior knowledge. To verify our theories, we conduct extensive experiments on two classical online CO problems (Secretary Problem and Online Knapsack) and carefully track the dependency between the performance of the policy and k.
2 RELATED WORK
RL for CO. There have been rich literature studying RL for CO problems, e.g., using Pointer Net- work in REINFORCE and Actor-Critic for routing problems (Nazari et al. 2018 combining Graph Attention Network with Monte Carlo Tree Search for TSP (Drori al.
2020) and incorporating
Structure-to- Vector Network in Deep Q-networks for maximum independent set problems (Cappart al., 2019). Bello al. (2017) proposed a framework to tackle CO problems using RL and neu- ral networks. Kool et 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. |eegiio et al. (2020) 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, RI. not only mimics exist- ing heuristics, but also discover novel ones that humans have not thought of, for example chip design MMirhoseini al. 202I) and compiler optimization (Zhou et al. 2020b
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 ingth-inddeeeneent manner. For example, the i-th element of a Relength sequence is encoded by the fraction 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: Online Matching, Online Knapsack and Secretary Problem (SP). Currently, Online Matching 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 (2021) y uses deep-RL for Online Matching. Oren et al. (202T) studies Parallel Machine Job Scheduling problem (PMSP) and Capacitated Vehicle Routing problem (CVRP), which are both online CO problems, using offline-learing and Monte Carlo Tree Search.
We provide the exact definition of LMDP in Sec. 4.1 As studied by Steimle et al. (202T), I), in the general cases, optimal policies for LMDPss are history-dependent. This is different from standard MDP cases where there always exists an optimal distory-indepennent policy. They showed that even finding the optimal histere-independent policy is NP-hard. Kwon et al. (2021a) investigated the sample complexity and regret bounds of LMDP in the history-independent policy class. They presented an exponential sample complexities for cases with special assumptions. Kwon et al. (2021b) showed that in reward- mixing MDPs, where MDPs share the same transition model, a polynomial sample complexity is achievable without any assumption find an optimal history-indeeennent policy.
LMDP.
sower-bound for general LMDP and derived algorithms with polynomial
2

---

Under review as a conference paper at ICLR 2023
Convergence rate for policy gradient methods. There is line of work the convergence rates
of policy gradient methods for standard MDPs (Bhandari & Russo (022). Wang et al. (2020) Liu
et al. (2020), Ding et al. (202I), Zhang al. (2021)) For softmax tabular parameterization, NPG
can obtain an ((/TT) rate (Agarwal et al.
2021) where is the number of iterations; with entropy
regularization, both PG and NPG achieves linear convergence (Mei al. 2020 Cen et al. 2021
For log-linear policies, sample-based NPG makes an O(IvVT) convergence rate, with assumptions
on Estat, éhias and k. (Agarwal et al. 2021) (see Def. D exact NPG with entropy regularization enjoys
a linear convergence rate up Cbias (Cayci et 2021 We extend the analysis LMDP.
Curriculum Learning. There are rich body of literature on Curriculum Learning (Zhou et al., 2021b a 2020a Ao et al. [021] Willems et al. 2020) Graves 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 al. (2020) rigorously modeled curriculum as a directed acyclic graph and surveyed work on curriculum design. Kong et al.)
(2019) proposed bootstrapping Curriculum Learning approach: gradually increase the problem size after the model works sufficiently well on the current problem size.
3 MOTIVATING ONLINE COMBINATORIAL OPTIMIZATION PROBLEMS
Online CO problems are natural class of problems that admit constructions of small-scale in- stances, because the hardness of online CO problems 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 suit- able, because under proper distribution { ] instances with drastically different solutions do not occupy much of the probability space.
In this section we introduce two motivating online CO problems. We are interested in these problems because they have all been extensively studied and have closed-form, masy-to-implemen policies as references. Furthermore, they were studied in Kong et al. (2019), the paper that motivates our work. They also have real-world applications, e.g., auction design (Babaioff et al. (007).
3.1 SECRETARY PROBLEM
In SP, the goal is maximize the probability of choosing the best among n candidates, where n is known. All candidates have different scores to quantify their abilities. They arrive sequentially and when the i-th candidate shows up, the decision- maker observes the relative ranking X, among the first i candidates, which means being the X,th-best so far. A decision that whether to accept or reject the i-th candidate must be made immediately when the candidate comes, and such decisions cannot be revoked. Once one candidate is accepted, the game ends immediately.
The ordering of the candidates unknown. There are total n! permutations, and an instance of SP is drawn from unknown distribution over these permutations. In the classical SP, each permutation is sampled with equal probability. The optimal solution for the classical SP is the well- known 1/e-threshold strategy: reject all the first [n/c] candidates, then accept the first one who is the best so-far. In this paper, we also study some different distributions.
3.2 ONLINE KNAPSACK (DECISION VERSION)
In Online Knapsack problems the decision eecksr observes (which known) items arriving se- quentially, each with value e 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 known budget B.
The goal of standard Online Knapsack is to maximize the total value of accepted items. In this paper, we study the decision version, denoted as OKD, whose goal is to maximize the probability of total value reaching a known target V.
We assume that all values and sizes are sampled independently from two fixed distributions, namely Lid. U1 D2 .2.....,,, Un iid. F, and $1 S2...., Sn ~ F,. In Kong et al. (2019) the experiments were carried out with F. F, Unif j. and also study other distributions.
3

---

Under review as a conference paper at ICLR 2023
A challenge in OKD is the sparse reward: the only signal is reward 1 when the total value of accepted items first exceeds V (see the detailed formulation in Sec. Cc2) unlike in Online
Remark 1.
Knapsack the reward of v, is given instantly after the i-th item is successfully accepted. This makes random exploration hardly get reward signals, necessitating Curriculum Learning.
4 PROBLEM SETUP
In this section, we first introduce LMDP and why naturally formulates online CO problems. The next necessary components required by the algorithm, Natural Policy Gradient.
4.1 LATENT MARKOV DECISION PROCESS
Tackling an online CO problem entails handling a family of problem instances. Each instance can be modeled as Markov Decision Process. However, for online CO problems, we want to find one algorithm that works for family of 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 et al. ap is a collection of MDPs M = MDPs share state set S, action set A and horizon H. Each MDP Mm (S, A. H. Vm P mm) has its own initial state distribution Vm E A(S), transition Pm. X A + ASS) and reward Tm 8 x A [0, 1]. where ((8) is the probability simplex over S. Let W1, W2: WM be the mixing weights of MDPs such that Wm > for any m and ΣM Wm At the start of every episode, one MDP Mm.. M is randomly chosen with probability Wim
Mar).
the
Due to the time and space complexities of finding the optimal history-dependen policies, we stay in line with Kong et al. (2019) and care only about finding the optimal iistoor-indeeeedeet policy. Let = (N S [AA) denote the class of all the history-indeppedent policies.
Log-linear policy. Let Φ S A Rd be feature mapping function where d denotes the dimension of feature space. Assume that [|o(s, a)ll2 B. A log-linear policy of the form:
exp(O) ((s, a))
Ta(a)s) En'es exp(0 (()) where 0 Rd
Remark Log-linear parameterization generalization of softmax tabular parameterization by setting d = [S] and ((s, a) One-hot(s, a). They are "scalable": if Φ extracts important features from different As with fixed dimension d [S]|AA,, then a single ny can generalize.
Entropy regularized 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 it facilitate training. We define the value function in unified way: (s) is defined as the sum of future X-regularized rewards starting from and executing π for h steps in Mn i.c.
V (8) = Σ (st, ax)
Mm, T,
where (s, a) == P' (8, a) Ann [[a|s}+ and the expectation is with respect to the randomness of trajectory induced by in Mn. Denote VM (s) = ym,,h(s), the unregularized value function.
For any Mm, T., h, with H((((-()) = E Eeed (Tals) In भाें [0, In [A]] we define
H (8) = I
H(((-188))
Mm, T,
In fact, (s) = t (s) + XH (s).
Denote V = EM= Wm Emess Um (sv) V m.H (so) and Va = V=.0 We need to find . arg max VE, Under regularization, seek for क arg max V instead. Denote V*:= V=*, V+A V Since V < ya Vad v + XH In [A], the regularized optimal

---

Under review as a conference paper at ICLR 2023
policy मं
be nearly optimal long as the regularization coefficient À is small enough. For notational ease, we abuse π with π..
The Q-function can be defined in similar manner:
:-
Σ T. (s,, ax)
Mm, T. (50, (0) - (s.
and the advantage function is defined as A (s, a) a= = (8. VT
(s.
Modeling SP. For SP, each instance is a permutation of length n, and in each round an instance is drawn from unknown distribution over all permutations. In the i-th step for [n]. the state encodes the i-th candidate and relative ranking so far. The transition is deterministic according to the problem definition. A reward of 1 is given if and only if the best candidate is accepted. We model the distribution as follows: suppose for candidate i, he/she is the best so far with probability P. and is independent of other i'. Hence, the weight of each instance is simply the product of the probabilities on each position. The classical SP satisfies P. -
Modeling OKD. For OKD, each instance sequence of items with values and sizes drawn from unknown distributions F, and F.. In the i-th step for [n)) the state encodes the information of i-th item's value and size, the remaining budget, and the remaining target value fulfill. The transition is also deterministic according to the problem definition, and a reward of is given if and only if the agent obtains the target value for the first time. F, = F, Unif(o, Kong et al. (2019)
4.2 ALGORITHM COMPONENTS
In this subsection we will introduce some necessary notions used by our main algorithm. Definition (State(-action) Visitation Distribution). The state visitation distribution and state- action visitation distribution at step h 2 0 with respect in Mm are defined as den, (s) P(sh
Mm, x),
d (s, a) P(sh = 5,
(m.
We will encounter a grafted distribution d (s. a)) d (s) a (n) which in general cannot be the state-action visitation distribution with respect to any policy. However, it can be attained by first acting under for h steps to get states then sample actions from the uniform distribution Unif This distribution will be useful when we apply a variant of NPG, where the sampling policy is fixed.
Denote d d and a as short for {a (im.))ismsMMossesE 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 e be the collection of any distribution, which will be instantiated by d', d' etc. in 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:
M
H1
[
L,g00v)) Σ
A (s, g TVo (ollnoo(aas)
Wm
E
h=1
&
Definition 3 (Generic Fisher Information Matrix).
M
Wm
E 8,0
V Volnmo(((s) (Vo (o))s)(
m==1
Particularly, denote F(0) Ege the Fisher information matrix induced by mo.
LEARNING PROCEDURE
In this section we introduce the algorithms: NPG supporting any customized sampler, and our pro- posed Curriculum Learning framework.
5

---

Under review as a conference paper at ICLR 2023
Natural Policy Gradient The learning procedure generates series of parameters and policies. Starting from 80, the algorithm updates the parameter by setting 8[+1 = 8; + 79t. where 7 is a predefined constant learning rate, and 9. is the update weight. Denote ne == no. V := V and A = A for convenience. We adopt NPG (Kakade 2002) because it efficient in training pa- rameterized policies and admits clean theoretical analysis. NPG satisfies E arg min, Lgg 0, d (see Sec. [ for explanation). When we only have samples, we use the approximate version of NPG: G.
St 2 arg geg L(g: 0e, d, where G = {x: || 12 S G} for some
We also introduce variant of NPG: instead of sampling from d using the current policy me sample from d using a fixed sampling policy a. The update rule gr 2 arg min L(g: 0,, d This version makes a closed-fon form analysis for SP possible.
The main algorithm shown in A It admits two types of training: ① If ne None, calls Alg. (deferred to Ap to sample 8, ~ d':; @ If Ts o None, it then calls Alg to sample < Alg. also returns unbiased estimation of (s,
In both cases, denote d' as the sampling distribution and Σ, the induced Fisher Information Matrix used in step t. i.e. d' := d E, := F(t)) π. None; d' == d Eg := Σ _- otherwise.
The update rule can be written in a unified way as gr R arg min L(g; 0,, d²). This is equivalent to solving a constrained quadratic optimization and we can use existing solvers.
Remark Alg. Dis different from Alg. 4 of[Agarwal et al. (202T) in that we use a "batched" update while they used successive Projected Gradient Descents (PGD). This is an important implementation technique to speed up training in our experiments.
Curriculum Learning. We use Curriculum Learning to facilitate training. Alg. 2 is our proposed training framework, which first constructs easy environment F' and trains (near-)opptl (optiml policy T, of it. In the target environment E, we either use R, to sample data while training new policy from scratch, simply continue training a. To be specifie and provide clarity for the results in Sec. 7
we name a few training modes (without regularization) here, and the rest are in Tab.
curl, the standard Curriculum Learning, runs Alg. 2 with samp -iit; fix samp sam_curl stands for the fixed sampler Curriculum Learning, running Alg. with samm pi.s. rect means directly learning in E without curriculum, i.c., running Alg.[] with π., None; baive_samp also directly learns in E, while using ne naïve random policy to sample data in Alg. [
Algorithm 1: NPG: Sample-based NPG. (Full version: Alg.
Input: Environment E: learning rate n): episode number T: batch size initialization fg; sampler n. regularization coefficient X; entropy clip bound U: optimization domain G.
2: for t 4 0,1,-.., 7 do
3: For 0 S n S N 1 and N
< h
H - 1, sample (a .. and estimate Alr using Alg.
4: Calculate:
#-1
F,
Σ
Σ
V lu (a ( (n)) (v In Ne, (a (a(")11((2)
==0 h=u
V +
Σ
Σ
(n) セーh
Vo In ne, (a) (m) (m))
5: Call any solver get T.
+- arg min
giggeg 9 Fig 2g E..
6: Update 0141 +- 01 + r/..
7:
end for
8:
Return: 0r-
PERFORMANCE ANALYSIS
Our analysis contains two important components, namely the sub-optimality gap guarantee of the NPG we proposed, and the efficacy guarantee of Curriculum Learning Secretary Problem. The first component can also be extended to history-dependent policies with features being the tensor products of features from each time step (which is exponentially large).

---

Under review as a conference paper at ICLR 2023
Algorithm 2: Curriculum learning framework.
Input: Environment E: learning rate yi episode number T: batch size sampler type samp { (pi.s,
pi.t J; regularization coefficient X; entropy clip bound U: optimization domain G.
2: Construct an environment E' with a task casier than B. This environment should have optimal policy
similar to that of E.
3: 0, f NPG (E", 7), T,N, K,00, None, X, U, 9) (sce Alg.
4: if samp =pi_s ___ss_________ then
5: 0r t NPG (E, 7) N, 0", A, U,
6: else
7: 0y NPG (E, n, 0,,,, None, X, U,
8: end if
9: Return: Or.
6.1 NATURAL POLICY GRADIENT FOR LATENT MDP
Let of arg minge L(g; Oc, d²) denote the minimizer. We have the following definitions:
Definition 4. Define for SLST
(Excess risk) Stat := max, (g 0r, d')
L(g 0e, )))
(Transfer error) Chins := max, [g Br, (,,dd)) )];
1 SuPaER x Eex
(Relative condition number) k max, E
Note that term inside the expecta-
tion is a random quantity as O, is random.
The expectation is with respect to the randomness the sequence of weights go -1......1 GT.
All the quantities are commonly used literature mentioned in Sec. Estat due to that the min- imizer de from samples may not minimize the population loss L. ébias quantifies the approximation error due to feature maps. K characterizes the distribution mismatch between and d" This is a key quantity 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 xt and any policy n
Definition 5 (Fitting Error). Suppose the update rule is te-1 = 0: 1996 define
M
err, == W/m
E
A
( ge Vo (olms((a)s)
T.Vo
(a.0) m.
m==1
Thm. 6 shows the convergence rate of Alg. and its proof is deferred to Sec. B.1
Theorem 6. With Def 4
and our algorithm enjoys the following performance bound:
X(1 + (TTO)
B²G²
Σt -1 'El em,,
E min V*A VLA
+ +
OSEST
(1 T4
Σv -77)---
X(1 -+ (TO)
B²G²
1 1 (1 - + 2
/ H + V HR
where (TTO) is the Lyapunov potential function which is only relevant to the initialization.
Remark 4. ① This is the first result for LMDP and sample-base based NPG with entropy regularization. @ For any fixed > 0 we have a linear convergence, which matches the result discounted infinite horizon MDP (Thm. in Cayci al. 2021)); )) the limit when À tends to 0 is O(1((nT)) + n) (which implies an O(1/VT) rate), matching the result in Agarwal et al. 2001 @ Estat can be reduced using a larger batch size N (Lem. 19). The typical scaling is 6at. = NN. + If some d, (especially example). In
the initialization dg) is far away from d", н may be extremely large (Sec. 6.2 other words, we can find a policy whose x is small with a single curriculum, we do not need the multi-step curriculum learning procedure used in Kong al. (2019)

---

Under review as a conference paper at ICLR 2023
6.2 CURRICULUM LEARNING FOR SECRETARY PROBLEM
For SP, there exists a threshold policy that is optimal (Beckmann, 1990). Suppose the threshold is p E (0, 1), then the policy is: accept candidate i if and only if and X; = 1. For the classical SP where all the n! instances have equal probability to be sampled, the optimal threshold is 1/e.
To show that curriculum learning makes the training converge faster, Thm. gives direct hint: curriculum learning produces a good sampler leading to much smaller k than that of a naïve random sampler: Here samp = pi_t _t it is impossible to analyze a dynamic procedure. We show Thm. 7 characterize K SP. Its full statement and proof deferred to Sec B.2
focus the cases where samp -p because the sampler is fixed, while when
Theorem 7. Assume that each candidate is independent of others and the i-th candidate has probability P. of being the best so far (Sec. 4.1). Assume the optimal policy is a p-threshold policy and the sampling policy is a g-threshold policy. There exists a policy parameterization such that:
Keurt
Inp]
+1 T-p
S
q P.
i-1
Knnaive
2 2Lupl
max
max 12 pP]
II [mp]+1
2(1 - Pj)
+2
where Kecur and Figaive are K of the sampling policy and the naive random policy, respectively.
To understand how curriculum learning influences k, we apply Thm. to three concrete cases. They show that, when the state distribution induced by the optimal policy in the small problem similar to that in the original large problem, then a single-step curriculum suffices (cf. @ of Rem. 4
The classical case: an exponential improvement. We study the classical SP first, where all the n! permutations are sampled with equal probability. The probability series for this case is P. 3- Substituting them into Eq. directly gives:
ww/e]
0 1
Anuiiv = 2- [n/e]
Recul
Ing
1,
9
n
Except for the corner case where q < n' have that Keurl On)) while Nnaive 12(2). Notice that any distribution with P. < leads to an exponential improvement.
more general case, Now we try to loosen the condition where t. Let us consider the case where P. S for 2 2 (by definition P1 is always equal to 1). Eq. now becomes:
Keur {
2|mp1-
9 P. 7> p.
Knaiie 2 2(11)]
Clearly, Keurt I Rgnive always holds. When is close to p, the difference is exponential in [mg]-
Failure mode of Curriculum Learning. Lastly we show further relaxing the assumption on P; leads to failure cases. The extreme case is that all P: = 1. the best candidate always comes as
the last one, Suppose < 2-1, then d (#) = 0. Hence Keart = oo, larger than Knavve 2n From Eq.
n Kanive & 2- Similar as Sec. of Beckmann 1990). the optimal threshold satisfies:
P.
P
Σ Imp
51
Σ
1-
P
I-P
+2
i=(mp] +1
So letting P. > results in p E [ng] + < can always be manipulated adversarially. Sometimes there hardly any reasonable curriculum.
for any 1, then from Eq. Reud > 2 >> Kaaive- This means that Curriculum Learning
1).
Further, if < a-1 and P3 1->1-22
Remark 5. Here we only provide theoretical explanations for SP when samp = pi.s, because K is highly problem-dependent, and the analytical forms for is tractable when the sampler is fixed. For samp = pi t and other CO problems such as OKD, however, we do not have analytical forms, resort to empirical studies (Sec.
8

---

Under review as a conference paper at ICLR 2023
fix samp_
_aiee_samp
direct
curl
reference
0.4
fomme
0.6
reward
0.3
Kappaapaa)
40
avgierr
70.4
0.2
20
0.2
0.0
0.0
#sample 1e8
#sample 1e8
#sample
1e8
Figure 1: One experiment of SP. The 7-axis is the number of trajectories, i.e. number of epsidoes 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 Sec.5 The reference policy is the optimal threshold policy.
fix samp_ curl
naive naive_samp
direct
curl
reference
(b)
0.4
0.4
log(Kappa)
avg(errt)
reward
0.2
0.2
0.0
0.0
#sample
1e8
#sample 1e8
1e8 The reference policy
#sample
Figure 2: One experiment of OKD. Legend description is the same that of Fig.
the bang-pes berk algorithm for Online Knapsack (Sec. 3.1 of Kong et al. (2019).
EXPERIMENTS
The experiments' formulations are modified from Kong et al. (2019). Due to page limit, more formulation details and results are presented in Sec. C In Curriculum Learning the entire training process splits into two phases. We call the training on curriculum (small scale instances) "warm-up phase" and the training on large scale instances "final phase". We ran more than one experiments for each problem. In one experiment there are more than one training processes to show the effect of different samplers and regularization coefficients. 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 up phase (if any), respectively.
Secretary Problem. We show one of the four experiments in Fig. Aside from reward and In In em, All the instance distributions generated from parameterized series {Pn) with fixed random seeds, which guarantees reproducibility and comparability. There is no explicit relation between the curriculum and the target environment, the curriculum can be viewed random and independent. The ex- periments clearly demonstrate that curriculum learning can boost the performance by a large margin and curriculum learning indeed dramatically reduces K, even the curriculum is randomly generated.
plot the weighted average of emT, according to Thm. 6 avg( emr, E (1-
Online Knapsack (decision version). We show one of the three experiments in Fig. In k and avg( err;) are with respect the reference policy, a bang-per-buck algorithm, which is not the op- timal 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 effec- tiveness of curriculum learning and curriculum learning indeed dramatically reduces k.
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 standard SP any curriculum exponentially improves the learning rate. Our empirical results also corroborated our findings. Our work is the first attempt to systematically study techniques devoted to using RL to tackle online CO problems, which we believe is fruitful direction worth further investigations.

---

Under review as a conference paper at ICLR 2023
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-98:76, 2021.
Susanne Albers, Arindam Khan, and Leon Ladewig. Improved online algorithms for knapsack and gap in the random order model. Algorithmica, 83:1750- 1785, 2021.
Mohammad Ali Alomrani, Reza Moravej, and Elias B Khalil. Deep policies for online bipartite matching: A reinforcement learning approach. arXiv preprint arXiv:2109.10:300 2021.
Shuang Ao, Tianyi Zhou, Guodong Long, Qinghua Lu, Liming Zhu, and Jing Jiang. CO-PILOT: COllaborative planning and reinforcement learning on sub-task curriculum. In A. Beygelzimer, Y. Dauphin, P. Liang, J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL
net / forum? ?iduzz cdduu__tt6225 2t.6yby
Moshe Babaioff, Nicole Immorlica, David Kempe, and Robert D. Kleinberg. A knapsack secretary problem with applications. In
2007.
M.J. Beckmann. Dynamic programming and the secretary problem. Computers & Mathe-
matics with Applications,, 19(11))25-25 1990. ISSN 0898-1221 doi: http://doi.or//10/ 1016/0898 121. URL https: htmp::://ww.. www.wccceeeeeddrre.ccoomm ctt.setccccccccccccee/
atticle/p1100091222111002
Irwan Bello, Hieu Pham, Quoe V. Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning, 2017.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th Annual International Conference on Machine Learning. ICML '09 pp. 41 1-48, New York, NY, USA, 2009, Association for Computing Machinery. ISBN 9781605585161. doi: 10.1145/155337, 110.3377..11555333 1533380.
URL httpss//dci..or////// 10./1/.115/1
1553374.155338D
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost, Machine learning for combinatorial optimiza- tion: a methodological tour d' d''orizon. European Journal of Operational Research, 290, 08 2020.
doi: 0.10016f.jorr222000766666
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 Learn- m.r.
ing Research, pp. 1236623994 PMLR, 13-15 Apr 2021. URI. press/v130/bhanda.
html
Nataly Brukhim, Elad Hazan, and Karan Singh. A boosting approach to reinforcement learning, 2021.
Quentin Cappart, Emmanuel Goutierre, David Bergman, and I Louis Martin Rousseau. Improving optimization bounds using machine learning: Decision diagrams meet deep reinforcement learn- ing. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):1443-1455 Jul. 2019. doi: 10.1609/aaai 133101.33001444 URL httts:: www..a.//....i......//////e///e. wwpp:n/ww.pppp......p..p
article/view/B3 3956
Quentin Cappart, Didier Chételat, Blias B. Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. In Zui-Hua Zhou (ed.), Proceedings of the Thirtieth International Joins Conference on Artificial Intelligence, IJCAI-21, pp. $348-4355 International Joint Conferences Artificial Intelligence Organiza- tion, 8 2021. doi: 0..29633ijcai.2221/555 URL. uRl.https::/dot http:///dd..oo/1..2222.00 2021 / Survey Track.
jcai.
Semih Cayci, Niao He, and R. Srikant. Linear convergence of gradient with linear function approximation, 2021.
natural policy
10

---

Under review as a conference paper at ICLR 2023
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//pre.2021..555
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 Dietrich, David P. Williamson, and Madeleine Udell. Learning solve combi- natorial optimization problems on real-world graphs in linear time. 2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA), pp. 19-24, 2020.
Naveen Garg, Anupam Gupta, Stefano Leonardi, and Piotr Sankowski. Stochastic analyses for online combinatorial optimization problems. 2008
Alex Graves, Mare G. Bellemare, Jacob Menick, Rémi Munos, and Koray Kavukcuoglu. Auto- mated curriculum learning for neural networks. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learning, volume 70 of Pro- ceedings of Machine Learning Research, pp. 1311-1320. PMLR, 06-11 Aug 2017. URL
Martin Grötschel, Sven O Krumke, Jörg Rambau, Thomas Winter, and Uwe T Zimmermann. Com- binatorial online optimization in real time. Online optimization of large scale systems, pp. 679- 704, 2001.
Zhiyi Huang. Online combinatorial optimization problems with non-linear objectives. In Nonlinear Combinatorial Optimization, pp. 179-205. Springer, 2019.
Zhiyi Huang, Peng Binghui, Zhihao Tang, Runzhou Tao, Xiaowei Wu, and Yuhao Zhang. Tight Competitive Ratios of Classic Matching Algorithms in the Fully Online Model, pp. 2875-2886. 01 2019. ISBN 978-1-61197-548. doi: 97157//997811199544499 178.
Sham MM Kakade. Z. Ghahramani (eds.). Advances in Neural Information Processing Systems, volume 14. MIT Press, 2002. URL https::/procceddiiieee mew.eeeedddinnss..ee.s.......
natural policy gradient. In T. Dietterich, S. Becker, and
ott.://ee.........ooo.oooooorrra cc//pppppee/220//iieee/// 4bb6abe4 heteeeeeeeecccc1111ccc5e1361133
Elias Boutros Khalil, Hanjun Dai, Yuyu Zhang, Bistra N. Dilkina, and Le Song. Learning combina- torial optimization algorithms over graphs. In N/PS, 2017.
Weiwei Kong, Christopher Liaw, Aranyak Mehta, and D. Sivakumar, 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: Regret guarantees and lower bound. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan (eds.), Advances Neural Information Processing Systems, volume 34, pp. 14523-24534, Curran Associates, Inc., 202 URL https: / neurips... babe5ee-Papp pddf
Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, and Shie Mannor. Reinforcement learn- ing in reward-mixing mdps. In NewrIPS, 2021b.
Yanli Liu, Kaiqing Zhang, Tamer Basar, and Wotao Yin. An improved analysis of (variance-reduced) 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. 7624-7636. Curran Associates, Inc., 2020. URL httpatss//prrrceeennggg neurips. 7788 9b3c cd08 (tw.0000e0o6622222222225555555
cc cc/paper/e 0amper/2020///
Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnev.. Reinforcement learning for combinatorial optimization: A survey. Computers Operations Research, 134:105400, 05 2021. doi: 10. 00.101/..rr.2221.105555
11

---

Under review as a conference paper at ICLR 2023
Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global convergence rates of softmax policy gradient methods. In Hal Daumé and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 6820-6829. PMIR, 13-18 Jul 2020. URL http: httt:::/prooceeding
m mlr. mlr.press/vll / me 20b.
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, Quoe 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 Taylor, and Peter Stone. Curriculum 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 NeurlPS, 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-Dattari, 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 IEEE 58th Conference on Decision and Control (CDC), Dec 2019, doi: 10.1 10.1109/cc4400242209999900 909999003000 URL http: /x. dei. wtt.oi.org/111111...101 CDC4 2019. 9029503
Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L.
Dill. Learning a SAT solver from single-bit supervision..... In International Conference on Learning Representations, 2019. URL htRps:tts://///tt /tcttps://operrevieee wtt/
Lauren N. Steimle, David L. Kaufman, and Brian Denton. Multi-model markov decision pro- cesses. IISE Transactions, 13(10))1124-1139, 2021. 1011080247258542221.
URL pectps://doi..e http://oo.oo...ooooo/oo// 111.///0.1100022255554544 2021. 1895454
Natalia Vesselinova, Rebecca Steinert, Daniel F. Perez-Ramirez, and Magnus Boman. Learning combinatorial optimization graphs: A survey with applications to networking. IEEE Access, 8:120388-120416, 2020.
Lingxiao Wang, Qi Cai,, Zhuoran Yang, and Zhaoran Wang. Neural policy gradient methods: Global optimality and rates of convergence. In International Conference on Learning Representattinss 2020. URL https: /ttttp:///peervview.o net wot.:e//oooooneeddeeoeee
Lucas Willems, Salem Lahlou, and Yoshua Bengio. Mastering rate based curriculum learning, 2020.
Junzi Zhang, Jongho Kim, Brendan O' O'Donoguue, and Stephen Boyd. Sample efficient reinforce- ment learning with reinforce. In AAAI, 2021.
Tianyi Zhou, Shengjie Wang, and Jeffrey Bilmes. Curriculum learning by dynamic instance hardness. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), Ad- vances in Neural Information Processing Systems, volume 33, pp. 8602 8613. Curran Asso- ciates, Inc., 2020a. URL htRt:tsts://///ttt htttps::/ppocceednaggg.oooo neuriiniipp... httpapsss.c//ppe//2////EL/ www.iinnnnn.euiii...
pdf
Tianyi Zhou, Shengjie Wang, and Jeff Bilmes. Curriculum learning by optimizing learning dy- namics. In Arindam Banerjee and Kenji Fukumizu (eds.). Proceedings of The 24th International Conference Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learn- ing Research, pp. 433 441. PMLR, 13-15 Apr 2021a. URL attps: btttps://proceeeeee http://///ccceee...eeee .mlr. press/ http://vv002///222 html
12

---

Under review as a conference paper at ICLR 2023
Tianyi Zhou, Shengjie Wang, and Jeff Bilmes. Robust curriculum learning: from clean label de- tection to noisy label self-correction. In International Conference on Learning Representations, 2021b. URL httpttsss//ppeervveew..coo wtt.eeee//oooriiii...i.aaaaaaaaa
Yanqi Zhou, Sudip Roy, Amirali Abdolrashidi, Daniel Wong, Peter Ma. Qiumin Xu, Hanxiao Liu, Phitchaya Phothilimtha, Shen Wang, Anna Goldie, Azalia Mirhoseini, 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 Utpp mee cc Ses.2pee722201111112222266ee5533
13

---

Under review as a conference paper at ICLR 2023
A SKIPPED ALGORITHMS
In this section, present the algorithms skipped in the main text. Alg the full version of Alg. Alg. is the sampling function.
Algorithm 3: NPG: Sample-based NPG (full version).
1: Input: Environment E; learning rate y, episode number T; batch size N; initialization Oo:
sampler иi regularization coefficient X; entropy clip bound U; optimization domain G.
2: for f- 0, 11............ 1....... T - do
3: Initialize Ft + 0axd V, t 0".
4: for n 0, ,,l,,..,,, N do
5: for h 4 0.1,...,
do
6: if TT not None then
7:
Sh, Oh (s,
an) sample n.. True, Te. h,, U) (see Alg.
8, a d estimate A m a).
8:
else
Sh, Oh, ( an) Sample (E, False, ne, h, X, U).
9:
Li no estimate A n
10:
end if
11: end for
Update:
H-1
F, F. +
Σ
Vo In To. (an(s)) In (o (anlss))
h=0
H
8. - V.
Σ
Au (sh, an) Vo (Ol (an(sn)-
h=0
13:
end for
Call any solver get Ør arg mingeg g Fig 2g V
15:
Update 0.+1 0g 79t-
16:
end for
Return: 0r.
B PROOF OF THE MAIN RESULTS
B. PERFORMANCE NATURAL POLICY GRADIENT FOR LMDP
First we give the skipped definition of the Lyapunov potential function &, then prove Thm
Definition 8 (Lyapunov Potential Function (Cayci al. 2021)). We define the potential function Φ πI R follows: for any E IT,
M Σ VE
H
In x (als)
(T))
Wmn
E (s.a)rdd
x (al
h=0
Theorem 6 (Restatement of Thm. performance bound:
With Def
and
our algorithm enjoys the following
A(1 7/ T+ (T))
B.G²
ET (/) El emr)
min V*d vLa osiST
+
(1 7
2
Et --)
X(1 m/))=+I
B
+ 2
/ Heehus /HEGA
(1 T+)
14

---

Under review as a conference paper at ICLR 2023
Algorithm 4: Sample: Sampler for "wrr where m Multinomial (wi,..., wM), a Unif if unif True and Tsamp(-|s) otherwise, and estimate of (s,
1: Input: Environment E; sampler policy Tsamp whether to sample uniform actions after state wnif: current policy Ti; time step h; regularization coefficient X; entropy clip bound U.
2: E.reset)).
3: for i f 7.0.1,.... do
4: 8; - Eeet state().
5: Sample action a; sammpl s-smp(-18s) and (.execute(a.).
6: end for
7: 9h f- E.get.stateO..
8: if' unif =oiffTTrue True then
9: On Unif
10: else
On ~ >mmmpp-sss
12: end if
(s.a) + (8h, az).
14: Get random number p Unif[0,
15: p then
16: Override on (e(-)s)).
17: Set importance weight C f- 22
18: Th t E.xxecute(aa))
19:
Initialize cumulative reward R t- rh + AH((Te(-118) (-18))).
20: else
21:
C+2. 2.
тh < E.exccute(an).
23: R - Th + Amin (In [.(0x|9%)) U).
24: end if
25: for + h+ h+1,h 2...., do
26:
E.get state().
27: 0; ~ (x))) and Fh +- F.xxecute(ag).
R+ R+tr (+(mm(-)s:)..
29: end for
Return: s,a, A (s,o) CR.
Proof. Here make shorthands for the sub-optimality gap and potential function: 4, V Vt, and t = ((T)). From Lem. we have
3 (1 n Det1 + em, + +1² B²G
2
Taking expectation over the update weights, we have
E[7A < 77) E| B( + 17 RB erry] + +1²² G2G
2
Thus,
T
E
(1
T'A
1=0
Σ (1 n77)
T-
El
Σ (1 T/7)T= B[
1=0
t=0
B2 G2 T
+1
(1 - [mm]]
11
m/1)
T
BB T
(1 )1ru
T+1 Φ 1 + Σ (1 -
E etr.
+ +12
Σ 11
2
1=0
1=0
15

---

Under review as a conference paper at ICLR 2023
T
G² T
S - (1--2A)++00)
+
Σ
(1
12)T
E(emr]] + 17
Σ (1- --)=
1=
1=0
where the last step the fact that (T)) 0. This is weighted average, by normalizing the coefficients,
X(1 - 40
B²G²
+ Ei=(( - -np)-- E[
E
min OSTST
(1 - 77)T +1
2
E1=o(1-1A)7- --)
X(1 - (1 - 77)
7))=+1
G2G²
+ Veessss + V Hiissaa:
+1 2
where the last step comes from Lem. 16 and Jensen's 's inequality. This completes the proof.
B.2 CURRICULUM LEARNING AND THE CONSTANT GAP FOR SECRETARY PROBLEM
Theorem 7 (Formal statement of Thm. 7 For SP, set samp = pi.s in Alg.2 Assume that each candidate is independent from others and the i-th candidate has probability Ps, of being the best so far (see formulation in Sec. 4.1 and C.I). Assume the optimal policy is a p-threshold policy and the sampling policy is q-threshold policy. There exists a policy parameterization and quantities
f-1
keuul
9 P: j= P-p 9> p.
Kindive = =2(mpl max
1, max
II j=[np]+1
2(1 - Pj)
1,
12 +2
such that hicurt S Kenrt S 2k and Knavve S Knnaive S 2kinatve- Here Reau and Kinaiee correspond to induced by the q-threshold policy and the naive random policy respectively.
Proof. We need 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, d=url, and that induced by the naive random sampler, n This then boils down to calculating the statc(-action) visitation distribution under two types of policies: any threshold policy and the naive random policy.
For any policy x, denote (#) as the probability for the agent acting under क to see states i with arbitrary 2;. We do not need to take the terminal state g into consideration, since it stays in zero-reward loop and contributes to L(g: 0, d). We use the LMDP distribution described in Sec.
Denote up as the p-threshold policy, i.e. accept if and only if > p and x, = 1. Then
i
d
Preject all previous - states (T))
n
i n
(2.1) n
P
S p
+1
n
(1-P
2 1))
[p]
II (1- P2).
[1p
Denote Thaive as the naive random policy, i.c., accept with probability regardless the state. Then
Traise i
( 1PP(rejcct all previous states [navee) 21-1'
1
n
For any we see that the state visitation distribution satisfies dd (4, P,d ( and ddd (1, 0) (1 Pd)d (2).
16

---

Under review as a conference paper at ICLR 2023
To show the possible largest difference, parameterization that for each state s, 6(s) One-hot(s). The policy is then
exp(0) ((s))
To (a(ccepp))s) exp(0 ((s)) +
no (rejectt))) exp(OT +1
Denote No (s) (acccepp))ss we have
V In no (accept]s s) (1 (T()))((s)
V (reject)))))(s))) = -s)(s))(ss)
Now suppose the optimal threshold and the threshold learned through curriculum are p and g, then
Dg
(s) (1- + -1- =)()))()))o{(} o(s))(s)
SES
0 dan
Σ dm (s)
2 =T))))²
1 [ (()))())
1
D grike
m
(8)
2 (s)) mo( ((8)0(s)
#ES
Denote &ig (0) = ZRR
From parameterization we know all Ø(s) are orthogonal. Abus-
ing To with Teurt. we have
d' (8) (IT' (8) - no(s)) + (1 x (s))
(0)
max SES
(
+ (8))
We can separately consider each E S because of the orthogonal features. Observe that TT (s)
{0, 1). so for E S, its corresponding term in Na (0) is maximized when To(s) = 1 Ts(s) and is
equal to 2d"p(a) 2 (a))
By definition, Ka maxogesT E [ (0+)]. Since 0o = 04, we have vig Ai (0d)
where Ty (s) and the corresponding term is d
(s) So
(s)
dTT
max
K 2 max
SES
SES
(8)
We now have an order-accurate result
h& msX
(s) (8)
for N.. Direct computation gives
[np] [g
keurl
I-Pj
q > P:
i-1
knaive = 2(rpp] max
1, max
II
2(1 - P3)
[1p] +1
This completes the proof.
C FULL EXPERIMENTS
Here are all the experiments not shown in Sec. 7 All the experiments were server with CPU AMD Ryzen 3950X, GPU NVIDIA GeForce 2080 Super and 128G memory. For legend description please refer the caption of Fig. For experiment data (code, checkpoints, logging data and policy visualization) please refer to the supplementary files.
Policy parameterization. Since in all the experiments there exactly two actions, ((s) = Φ(s, accept) - Φ(8, reject) instead of Φ(s, accept) and Φ(s, reject). Now the policy is (acccetptss) cxp(0 o())) and no (reject) s) = exp(0) ((s))+i*
exp(oTe(3))+
Training schemes. We ran seven experiments total, three for Secretary Problem and four for Online Knapsack (decision version). The difference between the experiments of the problem
17

---

Under review as a conference paper at ICLR 2023
lies in the distribution over instances (i.e., {Wm)) H). In the following subsections, will introduce how we parameterized the distribution in detail. In a single experiment, we ran eight setups, each representing combination of sampler policies, initialization policies of the final phase, and whether we used regularization. For visual clarity, we did not plot setups with entropy regularization, but the readers plot it using plot. py (comment 1.55-58 and uncomment 1.59-62) in the supplementary files. We make a detailed list of the training schemes in Tab.
Abbreviation
Detailed setup
Script
fix.samp.curl
Fixed sampler curriculum learning. In the warm-up phase, train policy from scratch (with zero initialization in parameters) using small environment E". In the final phase, change to the true environment use r, as the sampler policy to train policy from scratch.
Run Alg with samp
pi_s and
À
fix-samp.curl ..r....ccurrrgggggg.. ler
The same as fix_s sappcurrl but add en- tropy regularization both phases.
Run
Alg
with
samp
pi.s and
X + 0.
direct
Direct learning. Only the final phase. Train policy from scratch directly in E.
Run Alg. 0 nx
1
with 0n None and
A = 0.
di rect.ree
The direct, but add entropy regularization.
Run Alg. with 0n 0d T
None and
A * 0.
na naive_s Learning with the naïve sampler. Only the fi- nal phase. Use the naïve random policy as the sampler to train a policy from scratch in
Run Alg. with dg 0d.
naive ran-
dom policy and 0.
naive_samp reg
The same as saive.samp. but add entropy regularization.
Run Alg wwtt 0n 0d Te naive ran-
dom policy and + 0.
curl
Curriculum learning. In the warm-up phase, train a policy т. from scratch E". In the final phase, change to E and continue training Wg.
Run samp = pi.t and
Alg with
X = 0.
curl_reg
The same as curl, but add entropy regularization.
Run
Alg with
samp
pi_t and
X # 0.
reference
This is the reference policy. For SP, it is ex- actly the optimal policy since it can be cal- culated. For OKD, it is bang-per-bucd pol- icy and is not the optimal policy (whose exact form is not clear).
N/A
Table 1: Detailed setups for each training scheme.
C.I SECRETARY PROBLEM
State and action spaces. States with X, > 1 are the same. To make the problem "scale-invare invariant", we use to represent i. So the states are (4.2; 2; = 1[X; = 1]). There an additional terminal state g (0, 0). For each state, the agent either accept reject.
18

---

Under review as a conference paper at ICLR 2023
Transition and reward. Any action in g leads back g. Once the agent accepts the i-th candidate, the state transits into 9. and reward is i is the best the instance. If the agent rejects, then the state goes to [ 11+1) if < n and g if
For all other cases, rewards are O.
Feature mapping. Recall that all states are of the form (f. x) where f [0,1], I E {0,1}. We set degree do and the feature mapping is constructed the collection of polynomial bases with degree less than do (d 2dg):
@ff x)) (1, f........ fdo- N. fz. fdo-
LMDP distribution. We model the distribution follows: for each i, can have x; 1 with probability P. and is independent from other i'. By definition, Pi = while other Pa can be arbitrary. The classical SP satisfies P. t. We also experimented on three other distributions (so in total there are four experiments), each with a series of numbers P2, P3........ Pr Lid Unif(o.1) and
set P. = pP 10.25
For each experiment, initialization policies of the final phase, and the value of regularization coefficient A. For the warm- 10 and for final phases
eight setups, cach with different combinations of sampler policies,
up phases
100.
along with Fig. _ (with seed 201801 1309) show four experiments of SP. 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 learning).
Results. Fig. 3 (with its full view Fig. Fig. 5 F
The experiment in Fig. was done in the classical SP environment, i.e., all permutations have prob- ability 1 to be sampled. Experiments Fig. Fig. and Fig. were done with other distributions (see LMDP distribution of Sec. 7 the only differences are the random seeds, which we fixed and used to generate P.s for reproducibility.
The experiment of classical SP was until the direct training of n 100 converges, while all other experiments were run to maximum episode of 30000 (hence sample number of THb 30000 100 100 3 x 10%)
The optimal policy was derived from dynamic programming.
fix _o__samp_com curl
naive_san samp
direct
curl
reference
(b)
(c)
40
log(Kappa)
reward
Wulerrr
0.2
20
0.1
0.0
2
3
0
3
#sample
1eB
#sample
1e8
#sample
1e8
Figure 3: Classical SP, truncated to 3 x 10 samples.
fix samp curl
naive naive_samp
direct
curl
reference
(b)
(C)
0.4
reward
0.3
(ogpK)ppa)
avgiem t)
0.2
20
0.1
0.5
1.0
0.0
1.0
0.0
1.0
#sample
1e9
#sample
1e9
#sample
1e9
Figure 4: Classical SP, full view.
All the four trainings shown in the figures have their counterparts with regularization (A 0.01). Check the supplementary files and TensorBoard for visualization.
19

---

Under review as a conference paper at ICLR 2023
fix samp_cur
naive_samp
direct
curl
reference
0.4
1.0
reward
0.3
log(Kappa)
avgierr
0.2
0.5
0.1
0.0
#sample
1e8
#sample
1e8
#sample
1e8
Figure 5: SP, with seed 20000308.
fix sa_ssap___a curl (a)
naive_ samp
direct
curl
reference
(b)
(c)
0.4
reward
0.3
log(Kappa)
40
awgterr
1.0
0.2
20
0.5
0.1
0.0
0.0
#sample
1e8
#sample
1e8
#sample
1e8
Figure 6: SP, with seed 19283746.
C.2 ONLINE KNAPSACK (DECISION VERSION)
State and action spaces. The states are represented as
Σ 15
24-1 Ej=1 Uztj
i - Sy, Us
B
V
where zy 1 litem j was successfully chosen] for < j < i (in the instance). There is additional terminal state y = (0, 0,0,0,0, 0). For each state (including for simplicity), the agent can either accept or reject.
Transition and reward. The transition is implied by the definition of the problem. Any action in terminal state g leads back g. The item successfully chosen and only if the agent accepts and budget sufficient. A reward of given only the first time Σ FeV; 2 V, and then the state goes g. For all other cases, reward 0.
Feature mapping. Suppose the state is (f,s, v,T,)) q). We set a degree do and the feature map- ping constructed as the collection of polynomial bases with degree less than do Φ(f. s, sh "" where is E {0, 10.......44 do -1. 1}.
d)):
LMDP distribution. In Sec. 3.2 the values and sizes are sampled from F, ans F,. If F. is not Unif we model the distribution as: first set granularity gran and take gran numbers P1, P2. ..... Pyron Unifjo.1- pt represents the (unnormalized) probability that (--1 gran 3.).
To sample, we take Multinomial ... and return i-1+
gran
For each experiment, we ran four setups, each with different combinations sampler policies and initialization policies of the final phase. For the warm-up up phases n = 10 and for final phases we set n 100 in experiments, while B and vary. one experiment satisfies that n are close for warm-up and final, and B increases from warm-up to final.
Results. Fig. 7 Fig. along with Fig (with F, F, Unifp.1) show three experiments of OKD. They shared a learning rate of 0.I, batch size of 100 per step in horizon, final n 100 and warm-up 10 (if applied curriculum learning).
20

---

Under review as a conference paper at ICLR 2023
Experiments Fig. and Fig. were done with other value and size distributions (see LMDP distri- bution of Sec. 7 the only differences are the random seeds, which we fixed and used to generate F, and Fs for reproducibility.
All experiments were run to a maximum episode of 50000 (hence sample number of THb = 50000 100 x 100 5 x 10").
The reference policy a bang- bang-per-buck algorithm (Sec. 3.1 of Kong et al. 2019)): ) given a threshold
accept i-th item if V> 2 We searched for the optimal with respect Online Knapsack because
found that in general the reward is unimodal and contains no "plain area", apply ternary search (the reward of OKD contains "plain area").
easily
fix sampsamppco curl
naive_samy
direct
curl
reference (C)
(a)
(b)
10.0
0.2
0.2
log(Kappa)
7.5
avglerr t)
reward
0.1
0.0
2.5
0.0
0.0
-0.1
0
2 #sample
sample
1e8
#sample
1e8
1e8
Figure 7: OKD, with seed 201801 1309.
fix__pp fix_samp_cuu
naive_samp
direct
curl
reference
(b)
0.2
0.2
[ogpKappa)
10
avg t)
reward
0.1
0.1
0.0
0.0
#sample
1eB
#sample
1eB
#sample
1e8
Figure 8: OKD, with seed 20000308.
D TECHNICAL DETAILS AND LEMMAS
D.1 NATURAL POLICY GRADIENT FOR LMDP
This section is complement to Sec. We give details about the correctness of Natural Policy Gradient for LMDP.
Thm. is the finite-horizon Policy Gradient Theorem for LMDP, which takes the mixing weight (wm) into consideration.
According to Agarwal et al. (2021). the unconstrained, full-information NPG update weight satisfies F(0,)g: = V... Lem. 12 and Lem. together show that: it is equivalent to finding minimizer of the fitting compatible function approximation loss (Def. (2).
Theorem 11 (Policy Gradient Theorem for LMDP). For any policy me parameterized by 0, and any 1 S m < M,
H
V
E Agrwemm
Vi (50)
Σ
E
a) In
(ome (s,
a,a 11-h
h=1
As a resuli,
M
H
Vol Vorond
Σ
Wm
E
Aum s
m=1
m.
21

---

Under review as a conference paper at ICLR 2023
Proof. For any S h H and S, since (s)
EoEA To(als) (s, we have
VoV m,h (s) = Σ
(s, (0
aEA
Hence
H
H
(m)
m, (s)) Σ (
m.h
=
sES
h= SES
aEA
(s)
Q
mih 7
1=1
aeA
H
m,H (5)
Tolals)Vo00mh11.0
h= SES
aEA
Q Vg
h=1
H
& n (8)
Σ
Vo
h=1 BES
aEA
Next we focus on the second term. From the Bellman equation,
V V ro(s,a)= Alnmo(als) +
Σ
P(s'ls,a)V (s
S'ES
(clb) + Σ
P(518, mo Vo (6).
8'E
Particularly, V VolTi(ssa)) =- - So
H H- (s)
h=1sES
aeA
11
Σ
m. HI (s)
Σ
To(a|s)
-XVo In +
Σ P(s'ls,
m.k m (60)
h= SES
aEA
#EES
m. - (s)
Voto(als) +
VoV A (5')
Σ
d H. - (s) Σ ((s(ss)
h= $E8
aEA
h
SES
aEA
H
H. Ho.H-htill (t m
2=
Hn ( mih (s)
Σ S0ES
um V M
VoV VoVnee (so),
where we used the definition of d and V'. So by rearranging the terms, we complete the proof.
Lemma 12. Suppose I' E Ru D = diag(dı, d2, dmp) mm where d, 2 0 and q E I
then = (TD D'r is solution to the equation DDD DDg.
.p- reduced to PP x = Pp. Suppose the singular value decomposition of is U.V where e
Proof. Denote 1/2 diag(Vdı, Vdz...,, Vdm). PDD1?
D1/2g. then the equation is
Raxn Σ E paxm V Rmxm where U and V are unitary, and singular values are σi, 22..... The So PPT = USEΣ )UT and (PPT)t = U(EE YOU Notice that
ΣΣT diag(oř, oz..... og .0... 0) E RR
22

---

Under review as a conference paper at ICLR 2023
then derive the pseudo-inverse of this particular diagonal matrix
(Σ = diag 00 ; 0 -2 1.... .......',
It is then easy verify that (Σ (EE))))))))))))))))) 1 = Σ. Finally,
PP x = (PP) (PP))](PPT)(P)) Ppl
=U JU JUT
(EET)
=UEV
Pp.
This completes the proof.
Lemma 13 (NPG Update Rule). The update rule 0 + 0 + + where
M
H
F(O)=
Σ
1m
Σ
E
Volnso(als) (Vo (n
mm
h=1
saadd H-h
equivalent to <- + "19",
where g" is a minimizer of the function
[A - g Vo (olool()))) I
L(g)
Wm
m.Hth
Proof.
V VgL(g) = Σ
[ [AmA (s. a) VV (olmm)(l)))) Vo mm
Wm
h=1
Suppose 9" is any minimizer of L(g), we have vgL(g*) 0, hence
[ Vo [n
Wmm
H-b
M
H
Σ
A m.h a) (n
Wi
E
a H.H
m=1
M
H
Wm
E
s
m==1
Am
m H-A
Since (u voy (vv) )u, then
F(0)g* = VoVTO.
Now we assign and set
M H A as indices to all (m, h 8, E
(n
d, wm & (s,
= Q (s, a),
where j is the index assigned to (m, h, a). Then F(0) TD and v, +Dq where
[7,, 72, YMHSA E RdxMMSA
diag(d, d1 dy...., dMHSA) RAHSAAMHSA
q = [q1. 92...... " E MHSA
We now conclude the proof by utilizing Lem. 12
23

---

Under review as a conference paper at ICLR 2023
D.2 AUXILIARY LEMMAS USED IN THE MAIN RESULTS
Lemma 14 (Performance Difference Lemma). For any two policies тH and n2, and any S m S
M,
11
A (s, A Aln (T(als)
E 8pm-t/
ViTiI Vm (50)
Vm (80)
E
Tı (a
A=1 s,ardd
As a result,
Aln {2(a Tt (a|s)
V
V
Wm
Jumm
5,and
m. -
Proof. First we fix 8o. By definition of the value function, we have
m.H (8o)
mm (so)
E
(sh: an)) A
Aln In (anlsa)
Mm, 80
-V (5o)
H
E
Tim (sh, an) - - In + V
mm.H (on+1) - V (on)
(on) Mms T 80
E
E
I'm (sn, an) (awaann)nmmmmmmm (2n2s(1))5) + VmLia - -1
82, Mm t2, sn, sh, an)
Mm, 01
h=0
(2 (sh) тii (ap (sp)
V=2.A (1 A
Mm TI,
where the last step uses law of iterated expectations. Since
E
I'm (Sn, an) A Iu (2(a(s5)))
V 1m. (((0+1)) Mm n2, 8n, on
= - m. (8h, an):
have
(2 (s))
VT (5o)
V.T. (s0)
E
Q - (5h,
V.T.A 12.A m.H-h (sh) + Aln
Mms 1 50
म. (ap 8hh)
h=0
m.H (s:: + Aln To (an|sa)
A T2.
Mms Tı, s0
Ii (an s/.)
h=0
By taking expectation over 8p, we have
A - (8h; an) + Aln T2 T2(an (s)) Ti (an sh
E 5m
ViTA (80)
=
Mm, m
h=0
H-1
Σ
Σ
a)) AT (
x2(a|s)
=
T9 (1(as)
A=
(s.0)ESxA
The proof is completed by reversing the order h. Lemma (Lyapunov Drift), Recall definitions in Def. 8 and We have that:
((T++1) (TTT)) < (7;)(== + eIT, (v+i) v(.) + B²2 1
2
Proof. Denote 4; == (TT)). This proof follows similar manner as in that of Lem. 6 in Cayci et al. By smoothness (see Rem. 6.7 Agarwal et al. (202T).
2021
(als)
B² 0 -0el3
In -e- (a|s) < (0, 0ct1) Vo (n +
2
24

---

Under review as a conference paper at ICLR 2023
17² n2B² B1
7g.
Vo ln +
2
By the definition of Φ,
M
H
In (a(s)
(+1
4.
Wm
E
m=1
Aum
(s.a)
m. A
TT+1
M
112 11
Wm
E
0 Voln (n
By the definition of em,, Lem.
14
and again the definition of o we finally have
M
H
1
4, S
17
Wm
E
Amm (s, ge Veln In
(s.a) Fray
m=1
h=
m.
AIn (a s)
mih (8,
Y)
Wm
(s.a)add
h=1
m.
M
H
In (als)
1j B²
171
Wm
E
(s,))vdm.
Te(aas)
2
m=1
²)²
(V*id - -V(A) 17211
17 emr
which completes the proof.
Lemma 16. Recall that oi is the true minimizer of L. 0i, d=) in domain g. em defined in Def. satisfies
emr, S /HLIh d+) + / 02 Ligt; 0,,d²) d))).
Proof. The proof is similar that of Thm. 6.1 in Agarwal et al. (2021) We make the following decomposition of emr,
M
H-1
A Am Di Vo Volnm((als)
err,
Wm
E (s.a)~dt
m==
h==
E (s.a)ad
[(o 9.) VVln
mm
h=0
m.hh
M Since Em=l Wm Σh=0 Jensen's inequality, then
E (ea)ESXA &e (s,
H, normalize the coefficients and apply
H-1
H-1 Wm
Σ
Wm Σ
Σ
d' (s,a)
Σ
Σ
(Ahth oi
-i Tv Volnm((als)
(s,a)
h= (s.
h=0
/ HL d).
Similarly,
H-1
H
Wm
[(oz -6) Vn =)
To)
h=0 (s.a)ddi
H-1
H
Wm
- Tott-a//Tooohr/////oonmm3a3 g:)]
h=0 (s.a)
25

---

Under review as a conference paper at ICLR 2023
/ Hilst - ge sell2%z.
SVHNN HKllgt gall3.. 13.
where in (i), for vector u, denote I = Vo Ae for symmetric positive semi-definite matrix A. Due to that 97 minimizes L(g; Oc, ) over the set 9, the first-order optimality condition implies that
(g "i)"" V L O,, d') 20
for any g. Therefore.
L(g; 8c, d
Ligi: de,
(A (s, - (0n (gi -9) " [ Ligh: d2
Σ Wm
Σ
M
H
Σ
[(0t-9) 9) [ (n
Wm
E
h=1 s,and
m=1
(Ami - -o)Voomm((ls))) volmm(ass
(g gi)T
Wm
E
m=
h=1
saad
nhh
|1:1 g E + (g
96 V T.ge; Oc. dc
2 |1 g E.
So finally we have
enr, S / 0,, + H d' L 0,,d') d))).
This completes the proof.
D.3 BOUNDING Estat
Lemma 17 (Hoeffding's Inequality). Suppose X1, X .......,, are i...d. random variables laking values in (a, b). with expectation p.. Let X denote their average, then for any e 2 0,
2nc
PP P - 2 < 2exp
(- a)
Lemma 18. For any policy n, any state E S and any U 2 In IA
1
}
A
0 < ((als)
Σ
((lss) min
In (als))
U
T(ass)
eUI
AEA
aEA
Proof.
The first inequality is straightforward,
focus the second part. Set A' = (aEA A
In [a]e]
U} = {a A <(als) < + and Enea' T(als), _aeA)((ass) then
Σ T(a|s) ln <(ass)
T(ass) min In T(als) / aEA
Σ
Σ
T(a|s)
Σ <(als)U
T(als)
aEA
"EA'
aEA
π
(als))
p
(als) PP
"EA'
(aass)
S 1n
-p
p (als)
[
< pln
pU;
p
where the penultimate step comes from concavity of In and Jensen's inequality. Let f(p) p In LAI -UU then ('()) = |A| U In Recall that U In |A] 1, so f(p) increases
when p E (0, ( and decreases when E (1/4) 1). Since f( = JAI we complete the proof.
26

---

Under review as a conference paper at ICLR 2023
Lemma 19 (Loss Funetion Concentration). set n, None and U
> In IAI - 1, then with proba-
bility 1 - 2T + +1) exp 2Ne²) ) thhe update weight sequence of Alg.
satisfies: for any 0 s T,
SAGBIA eU+
L(gri Oz, d L(ge; 0c d S +
where
C 16HGB[ + XU Am [A]) + 4HG B².
If To # None and X = O, then with probability 1 - 2(T + 1) exp -0 C2
2N
the update weight
sequence of Alg. 7 satisfies: for any STST,
L( 02 d
I.(g6: 02 ),, s 26,
where
C = =B + 4HG²
Proof. We first prove the T, None case. For time step i, Alg. samples HN trajectories. Abusing the notation, denote
F
Vo In To (Vo (a (nn,)))
N
--1
Σ
An, -h-H--hh (8m,h an,h Vo In (o
N
M
[(g)
E H
+g +g- Fig-20 - 2g" V.
1= s,a
m=1
Notice that ① is a constant. From Alg. Tr is the minimizer of @ (hence L(g) inside the ball G. From V In ( = o(s. a) - E. (- (o))s d')l, |Ø(s, a)ll S B, llgll2 S G. we know that 2GB. So 0 s g Fig 4HG B². From Alg. 4 know that any sampled
o In (a]s)
A satisfies |A| < 2[1 - XU + H AIn So وg V < 4HGB + AU + H + Aln [A)]]
We first have that
SHGB[1 AU H(1 Aln AI)) < 2 SHGB XU + ((1 Xln AI) 4HG² B
(2)
To apply any standard concentration inequality, we next need to calculate the expectation of @ According to Monte Carlo sampling and Lem. 18 for any < M, h < H and (s,a) S x A, we have
사|A c44I
A (s, a)
s
E
& A (s.
Denote V, as the exact policy gradient at time step i, then
E g
-9 T V.l
s lllll E
[. Vell
E [(ss.a)] A(s.a)/le
< ||9/|2 HI| V In (als))l
2AGB|A u+1
Since Monte Carlo sampling correctly estimates state-action visitation distribution, E Fr = F(O.).
Notice that Pig is linear in entries of Fr. we have E 9 P.g] g F(Or)g. Now we are in the
position to show that
4XGBIAI
E [(o)] L(g)
5
eU+1
27

---

Under review as a conference paper at ICLR 2023
Hoeffding's inequality (Lem. 17 gives
P (f()) -E [ 2c) = 2exp (- 2N
O2
where from Eq. 2
C = 1 XU + H(1 Aln AA) + 4HG² B².
After applying union bound for all t, with probability 1 - 2(T + 1) exp holds for any g E g:
(-204²)
2Ne2 c
the following
4AGBIA
[gg 0, d.) L(g; (,, SEt eU+1
Hence
4XGB A
[[ 02,dd) )):) S [[ 0z d +
4XGB A
< L(g 02, )
+
e+1
SAGBIA
< Migh: O2, 0,, + 2e +
eU+l
For TT * None and A = O, we notice that | < 2H and hence -HH&GB < @ < SH + 4HG² B². Moreover, E the result.
I m.h (s, a) = A a). So by slightly modifying the proof we can get
28


Reviews:
[{"review_id": "rsRWQoO11_w", "reviewer": "Reviewer_eGuH", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper investigates the impact of the curriculum learning used in applying reinforcement learning to solve the combinatorial optimization problems. To demonstrate the impact of the curriculum learning, the paper first formulates the combinatorial optimization problem as latent markov decision process (LMDP) and applying the technics developed in LMDP to show the convergence rate. Besides that, the paper shows that the curriculum learning is helpful in finding a strong sampling policy to reduce the distribution shift. It also formally proves that the relative condition number is reduced exponentially with the curriculum learning comparing to the naive random sampling policy.", "summary_of_the_review": "The paper focuses on finding the role of curriculum learning in helping the RL algorithms to solve the CO problems, which is well motivated and interesting. The paper has a few misleading notations but overall the paper is okay to read and understand. The insights of treating CO problems as LMDP is interesting but somehow straightforward. The convergence rate theoretical result is very incremental comparing with previous RL works in LMDP domain. For the curriculum learning role in the RL algorithms for solving the CO, it's interesting to see that it help reduce the relative condition number when using it as sampling policy, but the baseline is only the naive sampler which is not ideal when considering the practical usage. ", "strength_and_weaknesses": "Strength:\n  1. The paper reformulates the combinatorial optimization as a latent markov decision process (LMDP), which is interesting and useful in applying the technics of the RL in LMDP case. \n  2. The paper's motivation to find when and why the curriculum learning is helpful in applying RL in LMDP is meaningful. It also shows that the curriculum learning is helpful in finding a strong sampling policy to reduce the distribution shift by either formally proving or empirically showing that the relative condition number is reduced.\n\nWeakness:\n  1. The technics behind the theoretical results on the convergence rate of the proposed algorithm are well-known, which makes the theoretical result like Theorem 6 very incremental\n  2. The theoretical result to show that the curriculum learning could find a good sampling policy and reduce the relative condition number exponentially is only w.r.t. the naive random sampling policy, which is not usually used in practice. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "qQhXuYi91n", "reviewer": "Reviewer_1B7j", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper presents an exploration of the combination of curriculum learning for on-line reinforcement learning problems by application to two related combinatoric optimization problems.  Central to the approach is to solve for a mixture $w_m$ of MDP models called a \"Latent Markov Decision Process (LMDP) (Kwon et al., 2021a)\" by the relative condition number κ is reduced. \n\nCurriculum learning, as popularized in Bengio (2009), presents an approach to non-convex optimization in learning problems, that takes advantage of training on progressively more challenging subsets of cases. Insights from the domain inform what makes cases  more challenging. This has a regularization effect, in addition to guiding - or \"shaping\" the optimization toward desired solutions. \n\nOnline combinatoric problems, that have been termed \"generalized assignment problems\" (GAP) (Albers 2021), attempt to rank items where the policy is restricted to making a selection \"without recall\" -- once an item is passed over, it may not be chosen.  These belong to a class of optimal stopping sequential decision problems. ", "summary_of_the_review": "It's a credit to the authors to have made realistic claims, and to have provided valid evidence to support them.  Granted that the work is correct, the results are not substantial.  Again one recognises as stated that this is exploratory work on a novel formulation.  I would question how the problem is approached, and wonder if as stated it does not admit of a clean solution.   ", "strength_and_weaknesses": "The memorable take-away from the paper is the use of \"Latent Markov Decision Process (LMDP)\" to study sequential decision problems where the state cannot be fully observed, as opposed to trying to express these as partially  observable MDPS (POMDPs.) Solutions to  no-recall GAP problems is a vital area and deserves study. \n\nCurriculum implies exploiting a heuristic about problem complexity - to relate an evolution of simplicity versus complexity during training.  The only description of the curriculum I find is in the description of experimental results, that \"There is no explicit relation between the curriculum and the target environment, so the curriculum can be viewed as random and independent. \"  So as stated, \"even if the curriculum is randomly generated\" shouldn't this be viewed as a kind of random-restarts approach? \n\nThere is also the question of reframing GAP problems as RL-style problems that either implicitly or explicitly consider the probability distribution of samples. In related work \"Currently, Online Matching and Online Knapsack have only approximation algorithms (Huang et al., 2019; Albers et al., 2021).\"    This is true, but \"online matching -- eg. the SP -- is underspecified as a probability model. These \"generalized assignment problems\" (Albers 2021) do not consider the probability distribution of samples.  In short, one needs to make an assumption about the sample, as the authors do,  that the sample distributions are relevant; value and size distributions were assumed uniform (Section 3.2).   As Granger (\"Optimal Statistical Decisions, 1970, p. 331) states \" In the context of this fantasy (that only information received is the rank of the sample) it is assumed at the beginning of the process (one) knows nothing about the quality\" (e.g the distribution they are drawn from) of the n items one will see.   One may argue this is unrealistic, more importantly it obscures much of what's going on in a sequential process. \n\nAs a minor point, for the statement  \"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.\" I think Bengio (2020) is the citation of the survey you mean. DNNs were not prevalent in 2009, and the 2009 paper works merely with a 3-level NN. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "gJFcr3FHnuB", "reviewer": "Reviewer_qByH", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The current study formulates online CO problems as latent Markov Decision Processes and propose a policy optimization method using natural policy gradient. In addition, the current study characterizes performance and investigates the effect of curriculum learning in deriving optimum policy.", "summary_of_the_review": "I think the level of analysis and the mathematical rigor are very high. Since this is not my area of ​​expertise, I could not accurately evaluate this course. However, I think this paper is closer to optimization or optimal control paper than a machine learning paper.", "strength_and_weaknesses": "\nThis study formulates online combinatorial optimization and proposes a way to derive optimum sequential decision-making policy. In addition, the current study provides a rigorous analysis of the performance of the policy. \n\nI think the level of analysis and mathematical rigor is very high. Since this field is not my area of expertise, I could not accurately evaluate this process.\n\nI think the current study fits better with an optimization or statistical analysis paper rather than a machine learning conference. I believe the current study should at least provide intuition or inspiration on how to effectively employ a learning-based solver for such a problem based on the discussed mathematical properties and structures.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "atwFNvSmKp", "reviewer": "Reviewer_GcdD", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This proposes to solve online combinatorial optimization problems using reinforcement learning composed of latent MDPs and curriculum learning. The paper presents formal formulations and theoretical results regarding the performance bound based on the relative condition number. In addition, the paper also presents theoretical results showing the power of curriculum learning in reducing the relative condition number of the selection (secretary) problem. Experimental studies are also provided to support the theoretical findings.\n", "summary_of_the_review": "This paper proposes to solve online combinatorial optimization problems using reinforcement learning composed of latent MDPs and curriculum learning, and presents theoretical studies as well as experimental results. This paper is overall good and sound, but the significance of the theoretical contribution needs better justifications.\n\n\n", "strength_and_weaknesses": "Strength:\n\n- S1: A combination of latent Markov Decision process, natural policy gradient technique, and curriculum learning can be an effective solution to online combinatorial optimization problems, and therefore, its theoretical foundations are important.\n- S2: The presented analysis seems sound, but the proofs are not completely checked.\n- S3: This paper is well-written, with formal settings being provided. Many details are carefully organized in the supplementary materials.\n\n\nWeaknesses:\n\n- W1: The so-called latent MDP appears to be a linear combination of classic MDPs. In such a sense, the existing analysis of MDP might be applicable to latent MDP without many technical challenges. The paper could better explain the technical challenge in obtaining the theoretical results. \n- W2: Some minor comments:\n     - While the main contribution of this paper is on the theoretical side, the experiments could be improved by having more baselines and problems. In particular, given the simple nature of the two considered problems, the paper may include simpler baselines based on, for example, multi-armed bandits. In addition to the interest of  Theorem 7, is there any other justification for the choice of the two selected problems?\n  - Is the entropy regularization equivalent to enforcing a certain prior distribution?\n  - The burden of notations might be reduced by avoiding introducing new notations, e.g., V^{\\pi}=V^{\\pi,0}, F(\\theta)=\\sum_{d^{\\theta}}^{\\theta}, and “here /club can be any symbol”.\n  - What is the logic behind sampling from a fixed policy rather than the current policy?\n  - The concept of environment E could be treated in a formal manner.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject