CDE: Curiosity-Driven Exploration for Efficient Reinforcement Learning in Large Language Models — part 4/4

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

• It is impossible that r ~ t ​ ( q , o 1 ) < 1 η ​ log ⁡ ( Z ⁡ ( q ) ) \tilde{r}_{t}(q,o_{1})<\frac{1}{\eta}\log\left(Z(q)\right) and r ~ t ​ ( q , o 2 ) ≥ 1 η ​ log ⁡ ( Z ⁡ ( q ) ) \tilde{r}_{t}(q,o_{2})\geq\frac{1}{\eta}\log\left(Z(q)\right) given that ( o 1 , o 2 ) (o_{1},o_{2}) has the same correctness label and − α T o 1 ​ log ⁡ π t ​ ( o 1 | q ) ≥ − α T o 2 ​ log ⁡ π t ​ ( o 2 | q ) -\frac{\alpha}{T_{o_{1}}}\log\pi_{t}(o_{1}|q)\geq-\frac{\alpha}{T_{o_{2}}}\log\pi_{t}(o_{2}|q) .

## Appendix E Proof for Consistency of Multi-head Critic Bonus

Linear MDP and Assumptions

###### Assumption E.1 (Linear MDP) .

We consider finite horizon ℳ = ( 𝒮 , 𝒜 , R , P , H ) \mathcal{M}=(\mathcal{S},\mathcal{A},R,P,H) with horizon H H , state space 𝒮 \mathcal{S} , action space 𝒜 \mathcal{A} , reward function R : 𝒮 × 𝒜 → ℝ R:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R} , and transition P : 𝒮 × 𝒜 → 𝒮 P:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{S} such that there exists a known feature ϕ ∈ ℝ d \phi\in\mathbb{R}^{d} and unknown features θ , ψ ∈ ℝ d \theta,\psi\in\mathbb{R}^{d} to ensure R ⁡ ( s , a ) = ϕ ​ ( s , a ) ⊤ ​ θ P ⁡ ( s ′ | s , a ) = ϕ ​ ( s , a ) ⊤ ​ ψ ​ ( s ′ ) . \displaystyle R(s,a)=\phi(s,a)^{\top}\theta\quad\quad P(s^{\prime}|s,a)=\phi(s,a)^{\top}\psi(s^{\prime}). Without loss of generality, we assume ‖ ϕ ⁡ ( s , a ) ‖ ≤ 1 \|\phi(s,a)\|\leq 1 for all ( s , a ) (s,a) , and ‖ ψ ⁡ ( s ′ ) ‖ ≤ d , ‖ θ ‖ 2 ≤ d \|\psi(s^{\prime})\|\leq\sqrt{d},\|\theta\|_{2}\leq\sqrt{d} .

###### Lemma E.2 (Proposition 2.3 in Jin et al. (2020) ) .

For linear MDPs that satisfy Assumption E.1 , there exists w h ⋆ ∈ ℝ d w_{h}^{\star}\in\mathbb{R}^{d} such that Q h π ( s , a ) := 𝔼 [ ∑ t = h H r t | s h = s , a h = a ] = ϕ ( s , a ) ⊤ w h ⋆ . Q_{h}^{\pi}(s,a):=\mathbb{E}\Big[\sum_{t=h}^{H}r_{t}\big|s_{h}=s,a_{h}=a\Big]=\phi(s,a)^{\top}w_{h}^{\star}.

The linearity of Q Q -functions enables using regression technique to solve it. Consider a dataset with n n observations 𝒟 = { s i , h , a i , h , G i , h } i = 1 n \mathcal{D}=\{s_{i,h},a_{i,h},G_{i,h}\}_{i=1}^{n} where G i , h G_{i,h} is the Monte-Carlo return. Let ϕ i , h = ϕ ⁡ ( s i , h , a i , h ) \phi_{i,h}=\phi(s_{i,h},a_{i,h}) and denote the regression noise as ε i , h = G i , h − ϕ i , h ⊤ ​ w h ⋆ \varepsilon_{i,h}=G_{i,h}-\phi_{i,h}^{\top}w_{h}^{\star} . We impose the following assumptions.

(A1) 𝔼 ⁡ [ ε i , h ∣ ϕ i , h ] = 0 \mathbb{E}[\varepsilon_{i,h}\mid\phi_{i,h}]=0 and { ( ε i , h ) } i = 1 n \{(\varepsilon_{i,h})\}_{i=1}^{n} are i.i.d. σ 2 \sigma^{2} –sub-Gaussian for each fixed h h ;

(A2) 1 n ​ ∑ i = 1 n ϕ i , h ​ ϕ i , h ⊤ → ℙ Σ t ≻ 0 \frac{1}{n}\sum_{i=1}^{n}\phi_{i,h}\phi_{i,h}^{\top}\xrightarrow{\mathbb{P}}\Sigma_{t}\succ 0

Jin et al. (2020) shows that doing value iteration on optimistically estimated Q function can achieve near-optimal regret for linear MDP, where the optimistic Q function is the combination of linear regression estimation and exploration bonus b n , h = β ​ ϕ n , h ⊤ ​ Λ n , h − 1 ​ ϕ n , h b_{n,h}=\beta\sqrt{\phi_{n,h}^{\top}\Lambda^{-1}_{n,h}\phi_{n,h}} , where Λ n , h = λ ​ I + ∑ i = 1 n ϕ i , h ​ ϕ i , h ⊤ \Lambda_{n,h}=\lambda I+\sum_{i=1}^{n}\phi_{i,h}\phi_{i,h}^{\top} and β \beta is some constant. Below we will formally connect our bootstrapped bonus with this term.

Formulation of the bootstrap multi-head critic

We accommodate the bootstrap multi-head into the linear-MDP setting. For any time step h h , we sample K K mini-batches { S k ⊂ [ n ] } k = 1 K \{S_{k}\subset[n]\}_{k=1}^{K} of size m = ζ ​ n m=\zeta n uniformly without replacement from 𝒟 \mathcal{D} and construct the ridge estimator as follows w ^ n , h ( k ) = arg ⁡ min ⁡ ∑ r ∈ S k w ⁡ ( G r , h − ϕ r , h ⊤ ​ w ) 2 + ζ ​ λ ​ ‖ w ‖ 2 . \widehat{w}_{n,h}^{(k)}=\arg\min_{w}\sum_{r\in S_{k}}(G_{r,h}-\phi_{r,h}^{\top}w)^{2}+\zeta\lambda\|w\|^{2}. For any feature ϕ ∈ ℝ d \phi\in\mathbb{R}^{d} , we define the bootstrap multi-head bonus as b h , K boot ​ ( ϕ ) = std ​ ( { ϕ ⊤ ​ w ^ n , h ( k ) | 1 ≤ k ≤ K } ) . b^{\text{boot}}_{h,K}(\phi)=\text{std}\left(\big\{\phi^{\top}\widehat{w}_{n,h}^{(k)}\big|1\leq k\leq K\big\}\right).

Elliptical (“count-based”) bonus in ( Jin et al., 2020 ) . The ridge estimator is constructed using all data across n n trajectories as follows w ^ n , h = arg ⁡ min ⁡ ∑ i = 1 n w ⁡ ( G i , h − ϕ i , h ⊤ ​ w ) 2 + ζ ​ λ ​ ‖ w ‖ 2 . \widehat{w}_{n,h}=\arg\min_{w}\sum_{i=1}^{n}(G_{i,h}-\phi_{i,h}^{\top}w)^{2}+\zeta\lambda\|w\|^{2}. For any query feature ϕ ∈ ℝ d \phi\in\mathbb{R}^{d} , the bonus term is b h cnt ​ ( ϕ ) = ϕ ⊤ ​ Λ n , h − 1 ​ ϕ b^{\text{cnt}}_{h}(\phi)=\sqrt{\phi^{\top}\Lambda_{n,h}^{-1}\phi} .

#### Formal Version and Proof of Theorem 3.2

###### Theorem E.3 .

Under Assumption E.1 and assumptions (A1)–(A2), for any fixed time-step h h and query ϕ ∈ ℝ d \phi\in\mathbb{R}^{d} , b h , K boot ​ ( ϕ ) → K → ∞ , n → ∞ ℙ β ​ ϕ ⊤ ​ Λ n , h − 1 ​ ϕ , b^{\text{boot}}_{h,K}(\phi)\xrightarrow[\ K\to\infty,\ n\to\infty\ ]{\ \mathbb{P}\ }\beta\sqrt{\phi^{\top}\Lambda_{n,h}^{-1}\phi}, where β \beta is some constant.

###### Proof.

For any time-step h h and S k ⊂ [ n ] S_{k}\subset[n] , we have the explicit solution of the ridge regression w ^ n , h = Λ n , h − 1 ​ ∑ i = 1 n ϕ i , h ​ G i , h . \widehat{w}_{n,h}=\Lambda_{n,h}^{-1}\sum_{i=1}^{n}\phi_{i,h}G_{i,h}. Conditioning on X h = [ ϕ 1 , h ⊤ ; … ; ϕ n , h ⊤ ] X_{h}=[\phi_{1,h}^{\top};\ldots;\phi_{n,h}^{\top}] , the conditional variance of the estimator is Var ​ ( ϕ ⊤ ​ w ^ n , h ∣ X h ) = σ 2 ​ ϕ ⊤ ​ ( Λ n , h − 1 − λ ​ Λ n , h − 2 ) ​ ϕ . \text{Var}\big(\phi^{\top}\widehat{w}_{n,h}\mid X_{h}\big)=\sigma^{2}\phi^{\top}\Big(\Lambda_{n,h}^{-1}-\lambda\Lambda_{n,h}^{-2}\Big)\phi. From Assumption (A2), we have ‖ Λ n , h − 1 ‖ op = O p ​ ( 1 / n ) \|\Lambda_{n,h}^{-1}\|_{\mathrm{op}}=O_{p}(1/n) , therefore ϕ ⊤ ​ Λ n , h − 1 ​ ϕ ≤ ‖ ϕ ‖ 2 ​ ‖ Λ n , h − 1 ‖ op = O p ​ ( 1 / n ) ​ and ​ ϕ ⊤ ​ Λ n , h − 2 ​ ϕ = O p ​ ( 1 / n 2 ) , \phi^{\top}\Lambda_{n,h}^{-1}\phi\leq\|\phi\|^{2}\,\|\Lambda_{n,h}^{-1}\|_{\mathrm{op}}=O_{p}(1/n)~~\text{and}~~\phi^{\top}\Lambda_{n,h}^{-2}\phi=O_{p}(1/n^{2}), and n ​ ϕ ⊤ ​ ( Λ n , h − 1 − λ ​ Λ n , h − 2 ) ​ ϕ − n ​ ϕ ⊤ ​ Λ n , h − 1 ​ ϕ = − n ​ λ ​ ϕ ⊤ ​ Λ n , h − 2 ​ ϕ → ℙ 0 . n\phi^{\top}\Big(\Lambda_{n,h}^{-1}-\lambda\Lambda_{n,h}^{-2}\Big)\phi-n\phi^{\top}\Lambda_{n,h}^{-1}\phi=-n\lambda\phi^{\top}\Lambda_{n,h}^{-2}\phi\xrightarrow{\mathbb{P}}0. Therefore, we have ϕ ⊤ ​ ( Λ n , h − 1 − λ ​ Λ n , h − 2 ) ​ ϕ → ℙ ϕ ⊤ ​ Λ n , h − 1 ​ ϕ . \phi^{\top}\Big(\Lambda_{n,h}^{-1}-\lambda\Lambda_{n,h}^{-2}\Big)\phi\xrightarrow{\mathbb{P}}\phi^{\top}\Lambda_{n,h}^{-1}\phi.

Before moving to b h , K boot ​ ( ϕ ) b^{\text{boot}}_{h,K}(\phi) , we define the following quantities Δ ​ Σ = 1 ζ ​ ∑ r ∈ S k ϕ r , h ​ ϕ r , h ⊤ − ∑ i = 1 n ϕ i , h ​ ϕ i , h ⊤ , b = ∑ i = 1 n ϕ i , h ​ G i , h , b s = 1 ζ ​ ∑ r ∈ S k ϕ r , h ​ G r , h , Δ ​ b = b s − b . \Delta\Sigma=\frac{1}{\zeta}\sum_{r\in S_{k}}\phi_{r,h}\phi_{r,h}^{\top}-\sum_{i=1}^{n}\phi_{i,h}\phi_{i,h}^{\top},\quad b=\sum_{i=1}^{n}\phi_{i,h}G_{i,h},\quad b_{s}=\frac{1}{\zeta}\sum_{r\in S_{k}}\phi_{r,h}G_{r,h},\quad\Delta b=b_{s}-b. Since Σ t ≻ 0 \Sigma_{t}\succ 0 , matrix Bernstein for sampling without replacement yields ‖ Δ ​ Σ ‖ op = O p ​ ( n ) \|\Delta\Sigma\|_{\mathrm{op}}=O_{p}(\sqrt{n}) . Use the expansion ( Λ n , h + Δ ​ Σ ) − 1 = Λ n , h − 1 − Λ n , h − 1 ​ Δ ​ Σ ​ Λ n , h − 1 + R Σ , ‖ R Σ ‖ op = O p ​ ( ‖ Λ n , h − 1 ‖ op 3 ​ ‖ Δ ​ Σ ‖ op 2 ) = O p ​ ( 1 / n 2 ) . (\Lambda_{n,h}+\Delta\Sigma)^{-1}=\Lambda_{n,h}^{-1}-\Lambda_{n,h}^{-1}\Delta\Sigma\Lambda_{n,h}^{-1}+R_{\Sigma},\quad\|R_{\Sigma}\|_{\mathrm{op}}=O_{p}(\|\Lambda_{n,h}^{-1}\|_{\mathrm{op}}^{3}\|\Delta\Sigma\|_{\mathrm{op}}^{2})=O_{p}(1/n^{2}).

The k k -th bootstrap ridge solution is w ^ n , h ( k ) = ( Λ n , h + Δ ​ Σ ) − 1 ​ b s . \widehat{w}^{(k)}_{n,h}=(\Lambda_{n,h}+\Delta\Sigma)^{-1}b_{s}. Subtracting w ^ n , h = Λ n , h − 1 ​ b \widehat{w}_{n,h}=\Lambda_{n,h}^{-1}b and inserting the expansion, w ^ ( k ) n , h − w ^ n , h = Λ n , h − 1 ​ Δ ​ b − Λ n , h − 1 ​ Δ ​ Σ ​ w ^ n , h ⏟ first order + ( − Λ n , h − 1 ​ Δ ​ Σ ​ Λ n , h − 1 ​ Δ ​ b + R Σ ​ b s ) ⏟ = : r n . \widehat{w}^{(k)}_{n,h}-\widehat{w}_{n,h}=\underbrace{\Lambda_{n,h}^{-1}\Delta b-\Lambda_{n,h}^{-1}\Delta\Sigma\,\widehat{w}_{n,h}}_{\text{first order}}+\underbrace{\big(-\Lambda_{n,h}^{-1}\Delta\Sigma\Lambda_{n,h}^{-1}\Delta b+R_{\Sigma}b_{s}\big)}_{=:r_{n}}. Since G i , h = ϕ i , h ⊤ ​ w h + ϵ i , h G_{i,h}=\phi_{i,h}^{\top}w_{h}+\epsilon_{i,h} , for any ϕ \phi we have ϕ ⊤ ​ ( w ^ n , h ( k ) − w ^ n , h ) = ϕ ⊤ ​ Λ n , h − 1 ​ ( 1 ζ ​ ∑ r ∈ S k ϕ r , h ​ ϵ r , h − ∑ i = 1 n ϕ i , h ​ ϵ i , h ) + ϕ ⊤ ​ Λ n , h − 1 ​ Δ ​ Σ ​ ( w h ⋆ − w ^ n , h ) + ϕ ⊤ ​ r n . \phi^{\top}(\widehat{w}^{(k)}_{n,h}-\widehat{w}_{n,h})=\phi^{\top}\Lambda_{n,h}^{-1}\Big(\frac{1}{\zeta}\sum_{r\in S_{k}}\phi_{r,h}\epsilon_{r,h}-\sum_{i=1}^{n}\phi_{i,h}\epsilon_{i,h}\Big)+\phi^{\top}\Lambda_{n,h}^{-1}\Delta\Sigma(w_{h}^{\star}-\widehat{w}_{n,h})+\phi^{\top}r_{n}. (7) From standard results for ridge regression, we have ‖ w h ⋆ − w ^ n , h ‖ 2 = O ℙ ​ ( 1 / n ) \|w_{h}^{\star}-\widehat{w}_{n,h}\|_{2}=O_{\mathbb{P}}(1/\sqrt{n}) , thus we have the second term ϕ ⊤ ​ Λ n , h − 1 ​ Δ ​ Σ ​ ( w h ⋆ − w ^ n , h ) = O ℙ ​ ( 1 / n ) \phi^{\top}\Lambda_{n,h}^{-1}\Delta\Sigma(w_{h}^{\star}-\widehat{w}_{n,h})=O_{\mathbb{P}}(1/n) . Similarly, for the last term we have ϕ ⊤ ​ r n ≤ ‖ ϕ ‖ ​ ( ‖ Λ n , h − 1 ‖ op 2 ​ ‖ Δ ​ Σ ‖ op ​ ‖ Δ ​ b ‖ op + ‖ Δ ​ Σ ‖ op ​ ‖ b s ‖ op ) = O ℙ ​ ( 1 / n ) . \phi^{\top}r_{n}\leq\|\phi\|\left(\|\Lambda_{n,h}^{-1}\|^{2}_{\mathrm{op}}\|\Delta\Sigma\|_{\mathrm{op}}\|\Delta b\|_{\mathrm{op}}+\|\Delta\Sigma\|_{\mathrm{op}}\|b_{s}\|_{\mathrm{op}}\right)=O_{\mathbb{P}}(1/n). Therefore, both terms are negligible at the ⋅ \sqrt{\cdot} scale. Condition on ( X h , { ϵ i , h } i = 1 n ) (X_{h},\{\epsilon_{i,h}\}_{i=1}^{n}) the only randomness comes from S S . By finite-population sampling theory, Var ∗ ​ ( 1 ζ ​ ∑ r ∈ S ϕ r , h ​ ϵ r , h ) = 1 − ζ ζ ​ ∑ i = 1 n ϕ i , h ​ ϕ i , h ⊤ ​ σ 2 . \text{Var}^{*}\Big(\frac{1}{\zeta}\sum_{r\in S}\phi_{r,h}\epsilon_{r,h}\Big)=\frac{1-\zeta}{\zeta}\sum_{i=1}^{n}\phi_{i,h}\phi_{i,h}^{\top}\sigma^{2}. Therefore, Var ∗ ​ ( ϕ ⊤ ​ ( w ^ n , h ( k ) − w ^ n , h ) ) \displaystyle\text{Var}^{*}\Big(\phi^{\top}(\widehat{w}^{(k)}_{n,h}-\widehat{w}_{n,h})\Big) = 1 − ζ ζ ​ σ 2 ​ ϕ ⊤ ​ Λ n , h − 1 ​ ( ∑ i = 1 n ϕ i , h ​ ϕ i , h ⊤ ) ​ Λ n , h − 1 ​ ϕ + o ℙ ​ ( 1 / n ) \displaystyle=\frac{1-\zeta}{\zeta}\sigma^{2}\phi^{\top}\Lambda_{n,h}^{-1}\Big(\sum_{i=1}^{n}\phi_{i,h}\phi_{i,h}^{\top}\Big)\Lambda_{n,h}^{-1}\phi+o_{\mathbb{P}}\big(1/n\big) = 1 − ζ ζ ​ σ 2 ​ ϕ ⊤ ​ ( Λ n , h − 1 − λ ​ Λ n , h − 2 ) ​ ϕ + o ℙ ​ ( 1 / n ) \displaystyle=\frac{1-\zeta}{\zeta}\sigma^{2}\phi^{\top}\Big(\Lambda_{n,h}^{-1}-\lambda\Lambda_{n,h}^{-2}\Big)\phi+o_{\mathbb{P}}\big(1/n\big) = 1 − ζ ζ ​ σ 2 ​ ϕ ⊤ ​ Λ n , h − 1 ​ ϕ + o ℙ ​ ( 1 / n ) \displaystyle=\frac{1-\zeta}{\zeta}\sigma^{2}\phi^{\top}\Lambda_{n,h}^{-1}\phi+o_{\mathbb{P}}\big(1/n\big)

Finally, by the conditional strong law of large numbers, we have b h , K boot ( ϕ ) = std ( { ϕ ⊤ w ^ n , h ( k ) | 1 ≤ k ≤ K } ) → a.s. Var ∗ ​ ( ϕ ⊤ ​ w ^ n , h ( k ) ) → ℙ 1 − ζ ζ σ ϕ ⊤ ​ Λ n , h − 1 ​ ϕ . b^{\text{boot}}_{h,K}(\phi)=\text{std}\left(\big\{\phi^{\top}\widehat{w}_{n,h}^{(k)}\big|1\leq k\leq K\big\}\right)\to_{\text{a.s.}}\sqrt{\text{Var}^{*}(\phi^{\top}\widehat{w}_{n,h}^{(k)})}\xrightarrow{\mathbb{P}}\sqrt{\frac{1-\zeta}{\zeta}}\sigma\sqrt{\phi^{\top}\Lambda_{n,h}^{-1}\phi}. ∎

## Instructions for reporting errors

We are continuing to improve HTML versions of papers, and your feedback helps enhance accessibility and mobile support. To report errors in the HTML that will help us improve conversion and rendering, choose any of the methods listed below:

Click the "Report Issue" ( ) button, located in the page header.

Tip: You can select the relevant text first, to include it in your report.

Our team has already identified the following issues . We appreciate your time reviewing and reporting rendering errors we may not have found yet. Your efforts will help us improve the HTML versions for all readers, because disability should not be a barrier to accessing research. Thank you for your continued support in championing open access for all.

Have a free development cycle? Help support accessibility at arXiv! Our collaborators at LaTeXML maintain a list of packages that need conversion , and welcome developer contributions .