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

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

da_{min}(1-\gamma_{c})(1-\gamma)^{3}}+\frac{2\gamma\beta}{(1-\gamma)^{2}}\Bigg) + ∑ k = 1 K − 1 ∥ Q K − Q k ∥ d K \displaystyle+\sum_{k=1}^{K-1}\|Q_{K}-Q_{k}\|_{d_{K}} This completes the proof.

∎

#### A.1.2 Proof of Theorem 3.2

###### Proof.

From the Finite-Sample Theorem for CRL, we aim to control all error terms to achieve the desired accuracy. We allocate the total error budget ϵ \epsilon across the K K curriculum steps, with ϵ k \epsilon_{k} being the error allocation for step k k , such that ∑ k = 1 K ϵ k ≤ ϵ \sum_{k=1}^{K}\epsilon_{k}\leq\epsilon . For each curriculum k k , we need to control the following terms: γ T ​ K ​ ‖ Q 1 ∗ − Q 1 π 0 ‖ ∞ \displaystyle\gamma^{TK}\|Q^{*}_{1}-Q^{\pi_{0}}_{1}\|_{\infty} ≤ ϵ 4 \displaystyle\leq\frac{\epsilon}{4} (8) 6 ​ ( 1 − ( 1 − γ c ) ​ λ m ​ i ​ n ​ α ) 1 2 ​ [ J k − ( t α + n + 1 ) ] ( 1 − γ ) 3 ​ ( 1 − γ c ) 1 / 2 ​ λ m ​ i ​ n 1 / 2 \displaystyle\frac{6(1-(1-\gamma_{c})\lambda_{min}\alpha)^{\frac{1}{2}[J_{k}-(t_{\alpha}+n+1)]}}{(1-\gamma)^{3}(1-\gamma_{c})^{1/2}\lambda_{min}^{1/2}} ≤ ϵ k 4 \displaystyle\leq\frac{\epsilon_{k}}{4} (9) 70 ​ L k ​ [ α ⁡ ( t α + n + 1 ) ] 1 / 2 λ m ​ i ​ n ​ ( 1 − γ c ) ​ ( 1 − γ ) 3 \displaystyle\frac{70L_{k}[\alpha(t_{\alpha}+n+1)]^{1/2}}{\lambda_{min}(1-\gamma_{c})(1-\gamma)^{3}} ≤ ϵ k 4 \displaystyle\leq\frac{\epsilon_{k}}{4} (10) 2 ​ γ ​ β ( 1 − γ ) 2 \displaystyle\frac{2\gamma\beta}{(1-\gamma)^{2}} ≤ ϵ k 4 \displaystyle\leq\frac{\epsilon_{k}}{4} (11) We can solve each of these constraints. For the first constraint, we need: T ≥ 1 K ​ log γ ⁡ ( ϵ 4 ​ ‖ Q 1 ∗ − Q 1 π 0 ‖ ∞ ) \displaystyle T\geq\frac{1}{K}\log_{\gamma}\left(\frac{\epsilon}{4\|Q^{*}_{1}-Q^{\pi_{0}}_{1}\|_{\infty}}\right) Since ‖ Q 1 ∗ − Q 1 π 0 ‖ ∞ ≤ 1 1 − γ \|Q^{*}_{1}-Q^{\pi_{0}}_{1}\|_{\infty}\leq\frac{1}{1-\gamma} , we have: T ≥ 1 K ​ log ⁡ γ ⁡ ( ϵ ⁡ ( 1 − γ ) 4 ) = O ⁡ ( log ⁡ ( 1 / ϵ ) K ) \displaystyle T\geq\frac{1}{K}\log\gamma\left(\frac{\epsilon(1-\gamma)}{4}\right)=O\left(\frac{\log(1/\epsilon)}{K}\right) For the second constraint, we need: ( 1 − ( 1 − γ c ) ​ λ m ​ i ​ n ​ α ) 1 2 ​ [ J k − ( t α + n + 1 ) ] \displaystyle(1-(1-\gamma_{c})\lambda_{min}\alpha)^{\frac{1}{2}[J_{k}-(t_{\alpha}+n+1)]} ≤ ϵ k ​ ( 1 − γ ) 3 ​ ( 1 − γ c ) 1 / 2 ​ λ m ​ i ​ n 1 / 2 24 , \displaystyle\leq\frac{\epsilon_{k}(1-\gamma)^{3}(1-\gamma_{c})^{1/2}\lambda_{min}^{1/2}}{24}, thus by taking log, 1 2 ​ [ J k − ( t α + n + 1 ) ] ​ log ⁡ ( 1 − ( 1 − γ c ) ​ λ m ​ i ​ n ​ α ) \displaystyle\frac{1}{2}[J_{k}-(t_{\alpha}+n+1)]\log(1-(1-\gamma_{c})\lambda_{min}\alpha) ≤ log ⁡ ( ϵ k ​ ( 1 − γ ) 3 ​ ( 1 − γ c ) 1 / 2 ​ λ m ​ i ​ n 1 / 2 24 ) , \displaystyle\leq\log\left(\frac{\epsilon_{k}(1-\gamma)^{3}(1-\gamma_{c})^{1/2}\lambda_{min}^{1/2}}{24}\right), thus J k \displaystyle J_{k} ≥ ( t α + n + 1 ) + 2 ​ log ⁡ ( ϵ k ​ ( 1 − γ ) 3 ​ ( 1 − γ c ) 1 / 2 ​ λ m ​ i ​ n 1 / 2 24 ) log ⁡ ( 1 − ( 1 − γ c ) ​ λ m ​ i ​ n ​ α ) . \displaystyle\geq(t_{\alpha}+n+1)+\frac{2\log\left(\frac{\epsilon_{k}(1-\gamma)^{3}(1-\gamma_{c})^{1/2}\lambda_{min}^{1/2}}{24}\right)}{\log(1-(1-\gamma_{c})\lambda_{min}\alpha)}. Using log ⁡ ( 1 − x ) ≈ − x \log(1-x)\approx-x for small x x , and α ⁡ ( t α + n + 1 ) ≤ ( 1 − γ c ) ​ λ m ​ i ​ n 130 ​ L k 2 \alpha(t_{\alpha}+n+1)\leq\frac{(1-\gamma_{c})\lambda_{min}}{130L_{k}^{2}} , we have: J k \displaystyle J_{k} ≥ ( t α + n + 1 ) − 2 ​ log ⁡ ( 24 ϵ k ​ ( 1 − γ ) 3 ​ ( 1 − γ c ) 1 / 2 ​ λ m ​ i ​ n 1 / 2 ) ( 1 − γ c ) ​ λ m ​ i ​ n ​ α \displaystyle\geq(t_{\alpha}+n+1)-\frac{2\log\left(\frac{24}{\epsilon_{k}(1-\gamma)^{3}(1-\gamma_{c})^{1/2}\lambda_{min}^{1/2}}\right)}{(1-\gamma_{c})\lambda_{min}\alpha} = ( t α + n + 1 ) + 2 ​ log ⁡ ( ϵ k ​ ( 1 − γ ) 3 ​ ( 1 − γ c ) 1 / 2 ​ λ m ​ i ​ n 1 / 2 24 ) ( 1 − γ c ) ​ λ m ​ i ​ n ​ α \displaystyle=(t_{\alpha}+n+1)+\frac{2\log\left(\frac{\epsilon_{k}(1-\gamma)^{3}(1-\gamma_{c})^{1/2}\lambda_{min}^{1/2}}{24}\right)}{(1-\gamma_{c})\lambda_{min}\alpha} For the third constraint, we need: α ⁡ ( t α + n + 1 ) \displaystyle\alpha(t_{\alpha}+n+1) ≤ ϵ k 2 ​ ( 1 − γ ) 6 ​ ( 1 − γ c ) 2 ​ λ m ​ i ​ n 2 4900 ​ L k 2 \displaystyle\leq\frac{\epsilon_{k}^{2}(1-\gamma)^{6}(1-\gamma_{c})^{2}\lambda_{min}^{2}}{4900L_{k}^{2}} = O ⁡ ( ϵ k 2 ​ ( 1 − γ ) 6 ​ ( 1 − γ c ) 2 ​ λ m ​ i ​ n 2 L k 2 ) \displaystyle=O\left(\frac{\epsilon_{k}^{2}(1-\gamma)^{6}(1-\gamma_{c})^{2}\lambda_{min}^{2}}{L_{k}^{2}}\right) For the fourth constraint, we need: β ≤ ϵ k ​ ( 1 − γ ) 2 8 ​ γ \displaystyle\beta\leq\frac{\epsilon_{k}(1-\gamma)^{2}}{8\gamma} Combining these constraints, the dominant factor in the sample complexity comes from the third constraint, which gives us: α ≤ O ⁡ ( ϵ k 2 ​ ( 1 − γ ) 6 ​ ( 1 − γ c ) 2 ​ λ m ​ i ​ n 2 L k 2 ​ ( t α + n + 1 ) ) \displaystyle\alpha\leq O\left(\frac{\epsilon_{k}^{2}(1-\gamma)^{6}(1-\gamma_{c})^{2}\lambda_{min}^{2}}{L_{k}^{2}(t_{\alpha}+n+1)}\right) The mixing time t α t_{\alpha} is O ⁡ ( log ⁡ ( 1 / α ) ) O(\log(1/\alpha)) , which gives us: α \displaystyle\alpha ≤ O ⁡ ( ϵ k 2 ​ ( 1 − γ ) 6 ​ ( 1 − γ c ) 2 ​ λ m ​ i ​ n 2 L k 2 ​ ( log ⁡ ( 1 / α ) + n + 1 ) ) \displaystyle\leq O\left(\frac{\epsilon_{k}^{2}(1-\gamma)^{6}(1-\gamma_{c})^{2}\lambda_{min}^{2}}{L_{k}^{2}(\log(1/\alpha)+n+1)}\right)\ This implies: α \displaystyle\alpha = O ⁡ ( ϵ k 2 ​ ( 1 − γ ) 6 ​ ( 1 − γ c ) 2 ​ λ m ​ i ​ n 2 L k 2 ​ log ⁡ ( 1 / α ) ) \displaystyle=O\left(\frac{\epsilon_{k}^{2}(1-\gamma)^{6}(1-\gamma_{c})^{2}\lambda_{min}^{2}}{L_{k}^{2}\log(1/\alpha)}\right) α ​ log ⁡ ( 1 / α ) \displaystyle\alpha\log(1/\alpha) = O ⁡ ( ϵ k 2 ​ ( 1 − γ ) 6 ​ ( 1 − γ c ) 2 ​ λ m ​ i ​ n 2 L k 2 ) \displaystyle=O\left(\frac{\epsilon_{k}^{2}(1-\gamma)^{6}(1-\gamma_{c})^{2}\lambda_{min}^{2}}{L_{k}^{2}}\right) Using the Lambert W function, we can solve for α \alpha : α \displaystyle\alpha = Θ ⁡ ( ϵ k 2 ​ ( 1 − γ ) 6 ​ ( 1 − γ c ) 2 ​ λ m ​ i ​ n 2 L k 2 ​ log ⁡ ( L k 2 ϵ k 2 ​ ( 1 − γ ) 6 ​ ( 1 − γ c ) 2 ​ λ m ​ i ​ n 2 ) ) \displaystyle=\Theta\left(\frac{\epsilon_{k}^{2}(1-\gamma)^{6}(1-\gamma_{c})^{2}\lambda_{min}^{2}}{L_{k}^{2}\log\left(\frac{L_{k}^{2}}{\epsilon_{k}^{2}(1-\gamma)^{6}(1-\gamma_{c})^{2}\lambda_{min}^{2}}\right)}\right) = Θ ~ ​ ( ϵ k 2 ​ ( 1 − γ ) 6 ​ ( 1 − γ c ) 2 ​ λ m ​ i ​ n 2 L k 2 ) \displaystyle=\tilde{\Theta}\left(\frac{\epsilon_{k}^{2}(1-\gamma)^{6}(1-\gamma_{c})^{2}\lambda_{min}^{2}}{L_{k}^{2}}\right) where Θ ~ \tilde{\Theta} hides logarithmic factors. The number of samples required for curriculum step k k is: M k \displaystyle M_{k} = J k ⋅ T \displaystyle=J_{k}\cdot T = O ⁡ ( ( t α + n + 1 ) + log ⁡ ( 1 / ϵ k ) ( 1 − γ c ) ​ λ m ​ i ​ n ​ α ) ⋅ O ⁡ ( log ⁡ ( 1 / ϵ ) K ) \displaystyle=O\left((t_{\alpha}+n+1)+\frac{\log(1/\epsilon_{k})}{(1-\gamma_{c})\lambda_{min}\alpha}\right)\cdot O\left(\frac{\log(1/\epsilon)}{K}\right) = O ⁡ ( log ⁡ ( 1 / α ) + n + 1 K ​ log ⁡ ( 1 / ϵ ) + log ⁡ ( 1 / ϵ k ) ​ log ⁡ ( 1 / ϵ ) K ⁡ ( 1 − γ c ) ​ λ m ​ i ​ n ​ α ) \displaystyle=O\left(\frac{\log(1/\alpha)+n+1}{K}\log(1/\epsilon)+\frac{\log(1/\epsilon_{k})\log(1/\epsilon)}{K(1-\gamma_{c})\lambda_{min}\alpha}\right) = O ⁡ ( log ⁡ ( 1 / ϵ ) ​ log ⁡ ( L k 2 ϵ k 2 ​ ( 1 − γ ) 6 ​ ( 1 − γ c ) 2 ​ λ m ​ i ​ n 2 ) + n ​ log ⁡ ( 1 / ϵ ) K CLOSE \displaystyle=O\Bigg(\frac{\log(1/\epsilon)\log\left(\frac{L_{k}^{2}}{\epsilon_{k}^{2}(1-\gamma)^{6}(1-\gamma_{c})^{2}\lambda_{min}^{2}}\right)+n\log(1/\epsilon)}{K} OPEN + log ⁡ ( 1 / ϵ k ) ​ log ⁡ ( 1 / ϵ ) ​ L k 2 ​ log ⁡ ( L k 2 ϵ k 2 ​ ( 1 − γ ) 6 ​ ( 1 − γ c ) 2 ​ λ m ​ i ​ n 2 ) K ​ ϵ k 2 ​ ( 1 − γ ) 6 ​ ( 1 − γ c ) 3 ​ λ m ​ i ​ n 3 ) \displaystyle+\frac{\log(1/\epsilon_{k})\log(1/\epsilon)L_{k}^{2}\log\left(\frac{L_{k}^{2}}{\epsilon_{k}^{2}(1-\gamma)^{6}(1-\gamma_{c})^{2}\lambda_{min}^{2}}\right)}{K\epsilon_{k}^{2}(1-\gamma)^{6}(1-\gamma_{c})^{3}\lambda_{min}^{3}}\Bigg) = O ~ ​ ( n ​ log ⁡ ( 1 / ϵ ) K + log ⁡ ( 1 / ϵ k ) ​ log ⁡ ( 1 / ϵ ) ​ L k 2 K ​ ϵ k 2 ​ ( 1 − γ ) 6 ​ ( 1 − γ c ) 3 ​ λ m ​ i ​ n 3 ) \displaystyle=\tilde{O}\left(\frac{n\log(1/\epsilon)}{K}+\frac{\log(1/\epsilon_{k})\log(1/\epsilon)L_{k}^{2}}{K\epsilon_{k}^{2}(1-\gamma)^{6}(1-\gamma_{c})^{3}\lambda_{min}^{3}}\right) The second term dominates, giving us: M k = O ~ ​ ( log 2 ⁡ ( 1 / ϵ k ) ​ log ⁡ ( 1 / ϵ ) ​ L k 2 K ​ ϵ k 2 ​ ( 1 − γ ) 6 ​ ( 1 − γ c ) 3 ​ λ m ​ i ​ n 3 ) \displaystyle M_{k}=\tilde{O}\left(\frac{\log^{2}(1/\epsilon_{k})\log(1/\epsilon)L_{k}^{2}}{K\epsilon_{k}^{2}(1-\gamma)^{6}(1-\gamma_{c})^{3}\lambda_{min}^{3}}\right) (12) The total number of samples across all curriculum steps is: M C ​ R ​ L \displaystyle M_{CRL} = ∑ k = 1 K M k \displaystyle=\sum_{k=1}^{K}M_{k} = ∑ k = 1 K O ~ ​ ( log 2 ⁡ ( 1 / ϵ k ) ​ log ⁡ ( 1 / ϵ ) ​ L k 2 K ​ ϵ k 2 ​ ( 1 − γ ) 6 ​ ( 1 − γ c ) 3 ​ λ m ​ i ​ n 3 ) \displaystyle=\sum_{k=1}^{K}\tilde{O}\left(\frac{\log^{2}(1/\epsilon_{k})\log(1/\epsilon)L_{k}^{2}}{K\epsilon_{k}^{2}(1-\gamma)^{6}(1-\gamma_{c})^{3}\lambda_{min}^{3}}\right) = O ~ ​ ( log ⁡ ( 1 / ϵ ) K ​ ∑ k = 1 K log 2 ⁡ ( 1 / ϵ k ) ​ L k 2 ϵ k 2 ​ ( 1 − γ ) 6 ​ ( 1 − γ c ) 3 ​ λ m ​ i ​ n 3 ) \displaystyle=\tilde{O}\Bigg(\frac{\log(1/\epsilon)}{K}\sum_{k=1}^{K}\frac{\log^{2}(1/\epsilon_{k})L_{k}^{2}}{\epsilon_{k}^{2}(1-\gamma)^{6}(1-\gamma_{c})^{3}\lambda_{min}^{3}}\Bigg) Assuming ϵ k = ϵ K \epsilon_{k}=\frac{\epsilon}{K} for all k k (uniform error allocation), we get: M C ​ R ​ L \displaystyle M_{CRL} = O ~ ​ ( log ⁡ ( 1 / ϵ ) K ​ ∑ k = 1 K log 2 ⁡ ( K / ϵ ) ​ L k 2 ( ϵ / K ) 2 ​ ( 1 − γ ) 6 ​ ( 1 − γ c ) 3 ​ λ m ​ i ​ n 3 ) \displaystyle=\tilde{O}\left(\frac{\log(1/\epsilon)}{K}\sum_{k=1}^{K}\frac{\log^{2}(K/\epsilon)L_{k}^{2}}{(\epsilon/K)^{2}(1-\gamma)^{6}(1-\gamma_{c})^{3}\lambda_{min}^{3}}\right) = O ~ ​ ( log ⁡ ( 1 / ϵ ) ​ log 2 ⁡ ( K / ϵ ) ​ K ϵ 2 ​ ( 1 − γ ) 6 ​ ( 1 − γ c ) 3 ​ λ m ​ i ​ n 3 ​ ∑ k = 1 K L k 2 ) \displaystyle=\tilde{O}\left(\frac{\log(1/\epsilon)\log^{2}(K/\epsilon)K}{\epsilon^{2}(1-\gamma)^{6}(1-\gamma_{c})^{3}\lambda_{min}^{3}}\sum_{k=1}^{K}L_{k}^{2}\right) = O ~ ​ ( log 3 ⁡ ( 1 / ϵ ) ​ K ϵ 2 ​ ( 1 − γ ) 6 ​ ( 1 − γ c ) 3 ​ λ m ​ i ​ n 3 ​ ∑ k = 1 K L k 2 ) \displaystyle=\tilde{O}\left(\frac{\log^{3}(1/\epsilon)K}{\epsilon^{2}(1-\gamma)^{6}(1-\gamma_{c})^{3}\lambda_{min}^{3}}\sum_{k=1}^{K}L_{k}^{2}\right) Adding the dependence on the bootstrapping parameter n n , we have: M C ​ R ​ L = O ⁡ ( ∑ k = 1 K log 3 ⁡ ( 1 / ϵ k ) ϵ k 2 ⋅ O ~ ​ ( L k 2 ​ n ( 1 − γ ) 7 ​ ( 1 − γ c ) 3 ​ λ m ​ i ​ n 3 ) ) \displaystyle M_{CRL}=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) (13)

This completes the proof for the first half of the Theorem. Now we move on to prove the second half of the Theorem.

The sample complexity for the final task K K is: M K = O ⁡ ( log 3 ⁡ ( 1 / ϵ K ) ϵ K 2 ⋅ L K 2 ⋅ C ( 1 − γ ) 7 ​ ( 1 − γ c ) 3 ​ λ m ​ i ​ n 3 ) . M_{K}=O\left(\frac{\log^{3}(1/\epsilon_{K})}{\epsilon_{K}^{2}}\cdot L_{K}^{2}\cdot\frac{C}{(1-\gamma)^{7}(1-\gamma_{c})^{3}\lambda_{min}^{3}}\right).

We can factor this term out of the total sum: M C ​ R ​ L = M K ⋅ ( 1 + ∑ k = 1 K − 1 L k 2 ⋅ log 3 ⁡ ( 1 / ϵ k ) ⋅ ϵ K 2 L K 2 ⋅ log 3 ⁡ ( 1 / ϵ K ) ⋅ ϵ k 2 ) . M_{CRL}=M_{K}\cdot\Bigg(1+\sum_{k=1}^{K-1}\frac{L_{k}^{2}\cdot\log^{3}(1/\epsilon_{k})\cdot\epsilon_{K}^{2}}{L_{K}^{2}\cdot\log^{3}(1/\epsilon_{K})\cdot\epsilon_{k}^{2}}\Bigg).

Define the curriculum efficiency factor: C ​ E ​ F = 1 + ∑ k = 1 K − 1 L k 2 ⋅ log 3 ⁡ ( 1 / ϵ k ) ⋅ ϵ K 2 L K 2 ⋅ log 3 ⁡ ( 1 / ϵ K ) ⋅ ϵ k 2 . CEF=1+\sum_{k=1}^{K-1}\frac{L_{k}^{2}\cdot\log^{3}(1/\epsilon_{k})\cdot\epsilon_{K}^{2}}{L_{K}^{2}\cdot\log^{3}(1/\epsilon_{K})\cdot\epsilon_{k}^{2}}.

This factor represents the ratio of total curriculum sample complexity to the sample complexity of just the final task. We make two structure assumptions about our curriculum design, geometric error allocation and L k L_{k} progression, ϵ k = ϵ K ⋅ e K − k \epsilon_{k}=\epsilon_{K}\cdot e^{K-k} and L k = L K / l K − k L_{k}=L_{K}/l^{K-k} , where e > 1 e>1 . This reflect a curriculum that gradually increases in difficulty while allowing larger errors in earlier stages. For a well-designed curriculum where early tasks are simpler than later ones, l > 1 l>1 .

For the error ratio term: ϵ K 2 ϵ k 2 = ϵ K 2 ( ϵ K ⋅ e K − k ) 2 = e − 2 ​ ( K − k ) , \frac{\epsilon_{K}^{2}}{\epsilon_{k}^{2}}=\frac{\epsilon_{K}^{2}}{(\epsilon_{K}\cdot e^{K-k})^{2}}=e^{-2(K-k)}, and for the L k L_{k} ratio term: L k 2 L K 2 = L k 2 ( L k ⋅ l K − k ) 2 = l − 2 ​ ( K − k ) . \frac{L_{k}^{2}}{L_{K}^{2}}=\frac{L_{k}^{2}}{(L_{k}\cdot l^{K-k})^{2}}=l^{-2(K-k)}. For the logarithmic term: log ⁡ ( 1 / ϵ k ) = log ⁡ ( 1 / ( ϵ K ⋅ e K − k ) ) = log ⁡ ( 1 / ϵ K ) − ( K − k ) ​ log ⁡ ( e ) . \log(1/\epsilon_{k})=\log(1/(\epsilon_{K}\cdot e^{K-k}))=\log(1/\epsilon_{K})-(K-k)\log(e).

Substituting these expressions into C ​ E ​ F CEF : C ​ E ​ F = 1 + ∑ k = 1 K − 1 l − 2 ​ ( K − k ) ⋅ [ log ⁡ ( 1 / ϵ K ) − ( K − k ) ​ log ⁡ ( e ) ] 3 ⋅ e − 2 ​ ( K − k ) log 3 ⁡ ( 1 / ϵ K ) . CEF=1+\sum_{k=1}^{K-1}\frac{l^{-2(K-k)}\cdot[\log(1/\epsilon_{K})-(K-k)\log(e)]^{3}\cdot e^{-2(K-k)}}{\log^{3}(1/\epsilon_{K})}.

Since e > 1 e>1 and K ≥ k K\geq k , ( K − k ) ​ log ⁡ ( e ) ≥ 0 (K-k)\log(e)\geq 0 . Thus we have C ​ E ​ F \displaystyle CEF = 1 + ∑ k = 1 K − 1 [ log ⁡ ( 1 / ϵ K ) − ( K − k ) ​ log ⁡ ( e ) ] 3 log 3 ⁡ ( 1 / ϵ K ) ⋅ ( e ​ l ) − 2 ​ ( K − k ) \displaystyle=1+\sum_{k=1}^{K-1}\frac{[\log(1/\epsilon_{K})-(K-k)\log(e)]^{3}}{\log^{3}(1/\epsilon_{K})}\cdot(el)^{-2(K-k)} ≤ 1 + ∑ k = 1 K − 1 ( e ​ l ) − 2 ​ ( K − k ) . \displaystyle\leq 1+\sum_{k=1}^{K-1}(el)^{-2(K-k)}.

The sum is a geometric series: ∑ k = 1 K − 1 ( e ​ l ) − 2 ​ ( K − k ) = ∑ k = 1 K − 1 ( e ​ l ) 2 ​ ( k − K ) = ( e ​ l ) 2 ​ ( 1 − K ) ​ 1 − ( e ​ l ) 2 ​ ( K − 1 ) 1 − ( e ​ l ) 2 = ( e ​ l ) 2 ​ ( 1 − K ) − 1 1 − ( e ​ l ) 2 \sum_{k=1}^{K-1}(el)^{-2(K-k)}=\sum_{k=1}^{K-1}(el)^{2(k-K)}=(el)^{2(1-K)}\frac{1-(el)^{2(K-1)}}{1-(el)^{2}}=\frac{(el)^{2(1-K)}-1}{1-(el)^{2}}

CRL is more sample-efficient than direct learning when: M C ​ R ​ L < M D ​ i ​ r ​ e ​ c ​ t M_{CRL}<M_{Direct} Since M C ​ R ​ L = M K ⋅ C ​ E ​ F M_{CRL}=M_{K}\cdot CEF and for a comparable direct learning approach, M D ​ i ​ r ​ e ​ c ​ t = M K ⋅ m M_{Direct}=M_{K}\cdot m where m m represents the relative difficulty factor of direct learning, our condition becomes: C ​ E ​ F < m . CEF<m. Thus for M C ​ R ​ L < M D ​ i ​ r ​ e ​ c ​ t M_{CRL}<M_{Direct} , substituting expressions it becomes: M C ​ R ​ L = M K ⋅ C ​ E ​ F ≤ M K ⋅ ( 1 + ( e ​ l ) 2 ​ ( 1 − K ) − 1 1 − ( e ​ l ) 2 ) < M K ⋅ m = M D ​ i ​ r ​ e ​ c ​ t . M_{CRL}=M_{K}\cdot CEF\leq M_{K}\cdot(1+\frac{(el)^{2(1-K)}-1}{1-(el)^{2}})<M_{K}\cdot m=M_{Direct}. Thus M CRL < M Direct ⇔ ( e ​ l ) 2 ​ ( 1 − K ) − 1 1 − ( e ​ l ) 2 < m − 1 . M_{\text{CRL}}<M_{\text{Direct}}\iff\frac{(el)^{2(1-K)}-1}{1-(el)^{2}}<m-1.

This completes the proof.

∎

## Appendix B Sample Efficiency Gains with CRL

Our theoretical analysis (see Sec. 3.3 ) establishes that curriculum reinforcement learning (CRL) attains target performance while requiring fewer hard samples than non-curriculum RL methods. To show this empirically, we count how many training samples from each difficulty level are seen during post-training. All methods are trained for 1600 iterations with an effective batch size of 8, totaling 12,800 samples, which allows a direct comparison of their sample efficiency under the same budget. For simplicity, we perform this analysis on Blocksworld, shown Table 8 . Our empirical results show that CRL methods are between 2.5 − 3 × 2.5-3\times more sample efficient than non-CRL methods that train exclusively on hard samples, while also achieving better performance, underscoring the importance of curriculum design for post-training.

## Appendix C Dataset Details

In this section we provide details of the datasets used for evaluation. We categorize the datasets into two categories, datasets that contain human annotated difficulties and others that do not.

### C.1 Datasets with Human Annotated Difficulties