Curriculum Reinforcement Learning from Easy to Hard Tasks Improves LLM Reasoning — part 2/6

Cleaned-text code points [15914, 31507). Bibliography omitted here; source.md includes it.

Cosine scheduling (E2H-C). To alleviate both the reward sparsity and forgetting issues, we propose a non-parametric scheduling strategy, namely, cosine sampling. This strategy can be written as: 𝐒 cosine ​ ( t , k ) = α t ⋅ ( K − k − 1 ) + ( 1 − α t ) ⋅ k , and ​ α t = 0.5 ⋅ ( 1 + cos ⁡ ( π ​ t T ) ) , \mathbf{S}_{\text{cosine}}(t,k)=\alpha_{t}\cdot(K-k-1)+(1-\alpha_{t})\cdot k,\,\,\,\text{and}\,\,\,\alpha_{t}=0.5\cdot(1+\operatorname{cos}(\frac{\pi t}{T})), where the resulting probabilities need to be normalized before sampling. Intuitively, this cosine sampler sets both the initial and ending sampling probabilities simply according to their ordinal number and interpolates the intermediate probabilities using a cosine function. As shown in Figure 3 , the easiest task has the highest probability of being sampled at the beginning, and has the lowest probability of being sampled at the end.

Gaussian scheduling (E2H-G). Although cosine scheduling addresses reward sparsity and forgetting, the parameter-free design limits flexibility in handling issues like trivial task overfitting and fine-grained control over different learning stages. Empirically, while adding the trivial task can boost the model performance, it is also easy for the model to overfit to trivial tasks. To overcome this challenge, we propose a Gaussian scheduling strategy inspired by the Gaussian mixture model ( Reynolds and others, 2009 ) .

As shown in Figure 4 (a), in a one-dimensional space, we assume the data distributions of tasks follow Gaussian distributions with the same variance σ \sigma . The means of the adjacent task’s Gaussian distributions are assumed to have the same distance 1 1 , i.e . , μ k = k − 1 \mu_{k}=k-1 . Then the sampling probability is defined as the likelihood of a given position x t x_{t} belonging to different task Gaussian distributions, similar to the expectation–maximization algorithm ( McLachlan and Krishnan, 2008 ) . Therefore, the Gaussian scheduling strategy can be expressed as: 𝐒 Gaussian ​ ( t , k ) = exp ⁡ ( − ( x t − μ k ) 2 2 ​ σ 2 ) , and x t = ( t T ) β ​ ( K − 1 ) , \mathbf{S}_{\text{Gaussian}}(t,k)=\operatorname{exp}\left(-\frac{(x_{t}-\mu_{k})^{2}}{2\sigma^{2}}\right),\ \mbox{and}\ \ x_{t}=\left(\frac{t}{T}\right)^{\beta}\left(K-1\right), (1) where we ignore the normalization term, and the probabilities will be normalized for sampling. In this sampling scheduler, we only have two hyperparameters, i.e . , σ \sigma and β \beta . While the variance σ \sigma controls the sampling concentration, β > 0 \beta>0 controls the sampling position x t x_{t} ’s moving speed. When σ \sigma is smaller, the training is more focused, more similar to traditional curriculum learning. When β < 1 \beta<1 , the sampling process will assign fewer training steps focusing on easier tasks and train harder tasks longer, avoiding easy task overfitting. As shown in Figure 4 (bcd), we use three typical hyperparameter settings for this Gaussian sampler, i.e . , β = 0.25 ​ σ = 0.75 \beta=0.25\ \sigma=0.75 , β = 0.75 ​ σ = 0.25 \beta=0.75\ \sigma=0.25 , and β = 0.5 ​ σ = 0.5 \beta=0.5\ \sigma=0.5 .

### 3.3 Theoretical Analysis

In this section, we analyze our curriculum reinforcement learning framework for LLMs under the lens of Approximate Policy Iteration (API). We follow the theoretical structure of Chen and Maguluri (2025) ; Scherrer (2014) , adapting it to our curriculum setting. Specifically, we show how sequentially solving interpolated curriculum distributions enables convergence guarantees and improved sample complexity bounds, under function approximation errors. Our analysis considers action-value functions and explicitly tracks the impact of approximation and distribution shift across curriculum stages. All proofs are presented in Appendix A .

#### 3.3.1 Theoretical Setup

Recall our MDP ℳ = ( 𝒮 , 𝒜 , P , r , γ ) \mathcal{M}=(\mathcal{S},\mathcal{A},P,r,\gamma) . We denote the policy space as Π \Pi , where each policy π ∈ Π \pi\in\Pi is a mapping from states to distributions over actions, π : 𝒮 → Δ ⁡ ( 𝒜 ) \pi:\mathcal{S}\to\Delta(\mathcal{A}) . In our curriculum setting, we introduce a sequence of MDPs { ℳ k } k = 1 K \{{\mathcal{M}_{k}}\}_{k=1}^{K} where each MDP shares the same state and action spaces but may differ in reward functions and/or transition dynamics. Each MDP induces a state visitation distribution d k d_{k} under the optimal policy for that curriculum, with { d k } k = 1 K \{d_{k}\}_{k=1}^{K} interpolating between an easy source distribution d 1 d_{1} and the final hard task d K d_{K} . Let π k \pi_{k} be the learned policy at curriculum step k k , and let π K ∗ \pi^{*}_{K} be the optimal policy under the final target task. The goal is to learn a sequence of policies { π k } k = 1 K \{\pi_{k}\}_{k=1}^{K} such that the final policy π K \pi_{K} performs well under the target distribution d K d_{K} .

The action-value function of a policy π \pi is defined as Q π ( s , a ) := 𝔼 [ ∑ t = 0 ∞ γ t r ( s t , a t ) | s 0 = s , a 0 = a , a t ∼ π ( ⋅ | s t ) , s t + 1 ∼ P ( ⋅ | s t , a t ) ] . Q^{\pi}(s,a):=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})\middle|s_{0}=s,a_{0}=a,a_{t}\sim\pi(\cdot|s_{t}),s_{t+1}\sim P(\cdot|s_{t},a_{t})\right]. Let 𝒯 π \mathcal{T}^{\pi} be the Bellman operator for policy π \pi , defined as 𝒯 π Q ( s , a ) := r ( s , a ) + γ 𝔼 s ′ ∼ P ( ⋅ | s , a ) , a ′ ∼ π ( ⋅ | s ′ ) [ Q ( s ′ , a ′ ) ] . \mathcal{T}^{\pi}Q(s,a):=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim P(\cdot|s,a),a^{\prime}\sim\pi(\cdot|s^{\prime})}\left[Q(s^{\prime},a^{\prime})\right]. We define the optimal Bellman operator 𝒯 \mathcal{T} , 𝒯 Q ( s , a ) := r ( s , a ) + γ 𝔼 s ′ ∼ P ( ⋅ | s , a ) [ max a ′ Q ( s ′ , a ′ ) ] . \mathcal{T}Q(s,a):=r(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim P(\cdot|s,a)}\left[\max_{a^{\prime}}Q(s^{\prime},a^{\prime})\right]. The fixed point of the optimal Bellman operator is 𝒯 ​ Q ∗ = Q ∗ \mathcal{T}Q^{*}=Q^{*} .

The Approximate Policy Iteration (API) framework is a generalization of classical policy iteration that accommodates function approximation and inexact updates. It serves as a foundational tool for analyzing practical reinforcement learning algorithms including actor-critic and deep RL methods. The API algorithm alternates between two stages. At iteration k k , the algorithm performs two algorithmic steps. ( i ) (i) Policy Evaluation: Given policy π k \pi_{k} , compute an approximate estimate Q ^ k \widehat{Q}_{k} of its action-value function Q π k Q^{\pi_{k}} , ( i ​ i ) (ii) Policy Improvement: Update the policy to π k + 1 \pi_{k+1} , which is greedy or approximately greedy with respect to Q ^ k \widehat{Q}_{k} . In the context of CRL, API offers a natural framework to study how sequentially adapted policies, defined over interpolated curriculum distributions, evolve toward the optimal policy and shape the final policy π K \pi_{K} .

We adopt the following API assumptions from Chen and Maguluri (2025) ; Scherrer (2014) , adapted to the curriculum setting. Let Q k := Q π k Q_{k}:=Q^{\pi_{k}} be the action-value function for the policy π k \pi_{k} at curriculum k k .

Approximate Policy Evaluation. At each iteration k k , a function approximator Q ^ k \widehat{Q}_{k} is used to estimate Q k Q_{k} . The estimated Q-function Q ^ k π k \widehat{Q}^{\pi_{k}}_{k} satisfies ‖ Q ^ k π k − Q k π k ‖ ∞ ≤ δ k . \|\widehat{Q}^{\pi_{k}}_{k}-Q^{\pi_{k}}_{k}\|_{\infty}\leq\delta_{k}.

Approximate Greedy Policy Improvement. Let π k + 1 \pi_{k+1} be an ϵ k \epsilon_{k} -greedy policy with respect to Q ^ k \widehat{Q}_{k} : 𝔼 s ∼ μ k ​ [ Q π k + 1 ​ ( s , π k + 1 ​ ( s ) ) ] ≥ 𝔼 s ∼ μ k ​ [ max a ⁡ Q ^ k ​ ( s , a ) ] − ϵ k , \mathbb{E}_{s\sim\mu_{k}}\left[Q^{\pi_{k+1}}(s,\pi_{k+1}(s))\right]\geq\mathbb{E}_{s\sim\mu_{k}}\left[\max_{a}\widehat{Q}_{k}(s,a)\right]-\epsilon_{k}, for a sampling distribution μ k \mu_{k} at step k k , i.e. , ‖ 𝒯 ​ Q ^ k π k − Q k π k + 1 ‖ ∞ ≤ ϵ k . \|\mathcal{T}\widehat{Q}^{\pi_{k}}_{k}-Q^{\pi_{k+1}}_{k}\|_{\infty}\leq\epsilon_{k}.

Distribution Mismatch (Concentrability). Let μ k \mu_{k} be the sampling distribution for policy improvement at step k k , and d k d_{k} the true task distribution. We assume the distribution mismatch between μ k \mu_{k} and d k d_{k} is bounded by C k C_{k} , i.e. , sup s ∈ 𝒮 d k ​ ( s ) μ k ​ ( s ) ≤ C k . \sup_{s\in\mathcal{S}}\frac{d_{k}(s)}{\mu_{k}(s)}\leq C_{k}.

Bounded Curriculum Drift. For the weighted norm, ‖ Q ‖ d k = 𝔼 s ∼ d k ​ [ max a ⁡ Q ​ ( s , a ) 2 ] \|Q\|_{d_{k}}=\sqrt{\mathbb{E}_{s\sim d_{k}}[\max_{a}Q(s,a)^{2}]} . The deviation between successive optimal Q-functions satisfies ‖ Q K ∗ − Q k ∗ ‖ d K ​ is bounded for all ​ k . \|Q^{*}_{K}-Q^{*}_{k}\|_{d_{K}}\text{ is bounded for all }k.

#### 3.3.2 Convergence Guarantee

Let Q K ∗ Q^{*}_{K} be the optimal Q-function for the final task under distribution d K d_{K} , and let Q π K Q^{\pi_{K}} be the Q-function of the policy learned at the final step. Define the performance loss of the final policy compared to the optimal target policy as: ℰ K := ‖ Q K ∗ − Q π K ‖ d K . \mathcal{E}_{K}:=\|Q^{*}_{K}-Q^{\pi_{K}}\|_{d_{K}}.

###### Theorem 3.1 (CRL Performance Guarantee) .

Let T T be the number of API policy updates within each task. β > 0 \beta>0 is a tunable parameter for stepsizes specified in Chen and Maguluri (2025) . Under the approximate greedy update and evaluation error assumptions above, the final performance gap ℰ K \mathcal{E}_{K} satisfies: ℰ K ≤ ∑ k = 1 K ( γ T ​ η k + 2 ​ γ ​ ( 1 − γ T ) ( 1 − γ ) 2 ​ δ k + 2 ​ γ β ​ ( 1 − γ ) 2 ) + ∑ k = 1 K − 1 ‖ Q K ∗ − Q k ∗ ‖ d K , \mathcal{E}_{K}\leq\sum_{k=1}^{K}\left(\gamma^{T}\eta_{k}+\frac{2\gamma(1-\gamma^{T})}{(1-\gamma)^{2}}\delta_{k}+\frac{2\gamma}{\beta(1-\gamma)^{2}}\right)+\sum_{k=1}^{K-1}\|Q^{*}_{K}-Q^{*}_{k}\|_{d_{K}}, where η k := ‖ Q k ∗ − Q k π k ‖ ∞ \eta_{k}:=\|Q^{*}_{k}-Q^{\pi_{k}}_{k}\|_{\infty} is the per-task Bellman error, δ k \delta_{k} is the evaluation error, and ϵ k \epsilon_{k} is absorbed in η k \eta_{k} .

The first term represents the convergence bias of the actor, and goes to zero geometrically fast as T T goes to infinity. The second term captures accumulated evaluation errors, which involves the stochastic error due to sampling and the error due to function approximation The third term captures the error introduced by the policy update rule, which can be made arbitrarily small by using large enough β \beta . Alternatively, we can use geometrically increasing stepsizes, in which case the third term goes to zero at a geometric rate. The last term captures the deviation in optimal Q-functions across curriculum stages, representing the cumulative gap between intermediate curriculum-optimal values and the final optimal value, which we refer to as the curriculum approximation error. This decomposition highlights the dual effect of CRL in improving sample efficiency (small δ k , ϵ k \delta_{k},\epsilon_{k} ) and ensuring smooth interpolation (small ‖ Q K ∗ − Q k ∗ ‖ \|Q^{*}_{K}-Q^{*}_{k}\| ).

#### 3.3.3 Finite Sample Approximation Error Analyses

In this section, we perform finite-sample analysis. Considering the critic, i.e., how to obtain an estimate of Q π Q^{\pi} , we can estimate the Q-function Q π Q^{\pi} of a given target policy π \pi using TD-learning. In TD-learning, especially when the state-action space size is large, the use of function approximation is natural. In linear function approximation, a set of basis vectors is selected to approximate the target value function Q π Q^{\pi} using linear combinations of the basis vectors. Let Φ ∈ ℝ | 𝒮 | ​ | 𝒜 | × d \Phi\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\times d} be the matrix of basis vectors Φ = [ ϕ 1 , ⋯ , ϕ d ] \Phi=[\phi_{1},\cdots,\phi_{d}] . Then, the goal is to find from the linear subspace 𝒬 = { Q ^ w = Φ ​ w ∣ w ∈ ℝ d } \mathcal{Q}=\{\hat{Q}_{w}=\Phi w\mid w\in\mathbb{R}^{d}\} the “best” approximation of the Q Q -function Q π Q^{\pi} , where w ∈ ℝ d w\in\mathbb{R}^{d} is the weight vector.

Following Section 3 and 4 of Chen and Maguluri (2025) , we derive the finite-sample theorem for CRL. Theorem A.1 and its analyses are provided in Appendix A.1.1 . The result of Theorem A.1 suggests that smoother curriculum trajectories, together with smaller approximation errors under finite samples, can lead to improved final policy performance. These effects are closely tied to the choice of stepsize and the number of updates per iteration.

Following Chen and Maguluri (2025) , let 𝒦 𝒮 ​ 𝒜 ∈ ℝ | 𝒮 | ​ | 𝒜 | × | 𝒮 | ​ | 𝒜 | \mathcal{K}_{\mathcal{S}\mathcal{A}}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\times|\mathcal{S}||\mathcal{A}|} be a diagonal matrix and let 𝒦 𝒮 ​ 𝒜 , min \mathcal{K}_{\mathcal{S}\mathcal{A},\min} be the minimal diagonal entry. J k J_{k} is the number of critic updates per policy iteration at curriculum k k . The bootstrapping parameter n n is chosen such that γ c := γ n / 𝒦 𝒮 ​ 𝒜 , min < 1 \gamma_{c}:=\gamma^{n}/\sqrt{\mathcal{K}_{\mathcal{S}\mathcal{A},\min}}<1 . L k L_{k} is the parameter defined by 1 + ( γ ​ ρ max , k ) n 1+(\gamma\rho_{\text{max},k})^{n} , ℰ approx , k := sup π ‖ Q c , ρ π k − Φ ​ w c , ρ π k ‖ ∞ \mathcal{E}_{\text{approx},k}:=\sup_{\pi}\left\|Q^{\pi_{k}}_{c,\rho}-\Phi w^{\pi_{k}}_{c,\rho}\right\|_{\infty} is the critic’s function approximation error, ‖ Q K ∗ − Q k ∗ ‖ ∞ \|Q^{*}_{K}-Q^{*}_{k}\|_{\infty} is the gap between the curriculum subtask and the final task, and λ min \lambda_{\min} is the mininum eigenvalue of the positive definite matrix Φ T ​ 𝒦 𝒮 ​ 𝒜 ​ Φ \Phi_{T}\mathcal{K}_{\mathcal{S}\mathcal{A}}\Phi . The term N 2 , 1 = ∑ k = 1 K 2 ​ γ ​ ℰ approx , k ( 1 − γ ) 2 N_{2,1}=\sum_{k=1}^{K}\frac{2\gamma\mathcal{E}_{\text{approx},k}}{(1-\gamma)^{2}} in Theorem A.1 is the function approximation error and equals zero when using a complete basis. A term of similar form is present in all existing work studying RL with function approximation ( Munos, 2003 ; Agarwal et al., 2021 ) . Based on Theorem A.1 , we next derive the sample complexity result.

###### Theorem 3.2 (Sample Complexity) .

For a given accuracy level ϵ > 0 \epsilon>0 , to achieve E ⁡ [ ‖ Q K ∗ − Q π K ‖ ∞ ] ≤ ϵ + N 2 , 1 + ∑ k = 1 K − 1 ‖ Q K ∗ − Q k ∗ ‖ d K , E[\|Q^{*}_{K}-Q^{\pi_{K}}\|_{\infty}]\leq\epsilon+N_{2,1}+\sum_{k=1}^{K-1}\|Q^{*}_{K}-Q^{*}_{k}\|_{d_{K}}, the total number of samples (i.e., the integer T ​ ∑ k = 1 K J k T\sum_{k=1}^{K}J_{k} ) required across all K K curriculum stages is of the order: O ⁡ ( ∑ k = 1 K log 3 ⁡ ( 1 / ϵ k ) ϵ k 2 ⋅ O ~ ​ ( L k 2 ​ n ( 1 − γ ) 7 ​ ( 1 − γ c ) 3 ​ λ m ​ i ​ n 3 ) ) , O\left(\sum_{k=1}^{K}\frac{\log^{3}(1/\epsilon_{k})}{\epsilon_{k}^{2}}\cdot\tilde{O}\left(\frac{L_{k}^{2}n}{(1-\gamma)^{7}(1-\gamma_{c})^{3}\lambda_{min}^{3}}\right)\right), where ϵ k \epsilon_{k} is the target accuracy for curriculum k k , and ∑ k = 1 K ϵ k ≤ ϵ \sum_{k=1}^{K}\epsilon_{k}\leq\epsilon .

Let M CRL = ∑ k = 1 K M k M_{\text{CRL}}=\sum_{k=1}^{K}M_{k} be the total number of samples needed by CRL with K K curriculum steps to achieve error ϵ \epsilon on the final task, and let M Direct = m ∗ M K M_{\text{Direct}}=m*M_{K} be the number of samples needed by direct learning, where m > 1 m>1 represents the relative difficulty factor of direct learning. Under geometric error and L k L_{k} allocation ϵ k = ϵ K ⋅ e K − k \epsilon_{k}=\epsilon_{K}\cdot e^{K-k} and L k = L K l K − k L_{k}=\frac{L_{K}}{l^{K-k}} for curriculums, we have: M CRL < M Direct ⇔ ( e ∗ l ) 2 ​ ( 1 − K ) − 1 1 − ( e ∗ l ) 2 < m − 1 . \displaystyle M_{\text{CRL}}<M_{\text{Direct}}\iff\frac{(e*l)^{2(1-K)}-1}{1-(e*l)^{2}}<m-1. (2)