Paper deep dive

Generalisation of RLHF under Reward Shift and Clipped KL Regularisation

Kenton Tang, Yuzhu Chen, Fengxiang He

Year: 2026Venue: arXiv preprintArea: cs.LGType: PreprintEmbeddings: 113

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%

Last extracted: 7/20/2026, 12:14:22 PM

Summary

This paper develops a generalisation theory for Reinforcement Learning from Human Feedback (RLHF) that accounts for reward shift and clipped KL regularisation. It decomposes generalisation error into sampling error, reward shift error, and KL clipping error, providing bounds for each. The theory offers practical implications for optimizing KL clipping thresholds and allocating computational budgets across prompts, rollouts, and preference data.

Entities (9)

Kenton Tang · person · 99%RLHF · method · 98%Clipped KL Regularisation · method · 95%Reward Shift · concept · 95%University of Edinburgh · organization · 95%KL Clipping Error · concept · 92%Sampling Error · concept · 92%PAC-Bayes · method · 85%Ornstein-Uhlenbeck process · concept · 80%

Relation Signals (7)

Kenton Tang → affiliatedwith → University of Edinburgh

confidence 99% · Kenton Tang University of Edinburgh

RLHF → suffersfrom → Reward Shift

confidence 95% · reward shift: reward models are trained on preference data from earlier or mixed behaviour policies while RLHF optimises the current policy on its own rollouts

RLHF → uses → Clipped KL Regularisation

confidence 95% · clipped KL regularisation: the KL regulariser is estimated from sampled log-probability ratios and then clipped for stabilisation

Generalisation Error → composedof → Sampling Error

confidence 92% · generalisation error stems from a sampling error from prompts and rollouts

Generalisation Error → composedof → Reward Shift Error

confidence 90% · generalisation error stems from ... a reward shift error

Generalisation Error → composedof → KL Clipping Error

confidence 90% · generalisation error stems from ... a KL clipping error

RLHF → analyzedusing → PAC-Bayes

confidence 85% · employing PAC-Bayes tools ... our analysis yields high-probability generalisation bounds

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:Alignment and adaptation in large language models heavily rely on reinforcement learning from human feedback (RLHF); yet, theoretical understanding of its generalisability remains premature, especially when the learned reward could shift, and the KL control is estimated and clipped. To address this issue, we develop generalisation theory for RLHF that explicitly accounts for (1) \emph{reward shift}: reward models are trained on preference data from earlier or mixed behaviour policies while RLHF optimises the current policy on its own rollouts; and (2) \emph{clipped KL regularisation}: the KL regulariser is estimated from sampled log-probability ratios and then clipped for stabilisation, resulting in an error to RLHF. We present generalisation bounds for RLHF, suggesting that the generalisation error stems from a sampling error from prompts and rollouts, a reward shift error, and a KL clipping error. We also discuss special cases of (1) initialising RLHF parameters with a uniform prior over a finite space, and (2) training RLHF by stochastic gradient descent, as an Ornstein-Uhlenbeck process. The theory yields practical implications in (1) optimal KL clipping threshold, and (2) budget allocation in prompts, rollouts, and preference data.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

111,699 characters extracted from source content.

Expand or collapse full text

Generalisation of RLHF under Reward Shift and Clipped KL Regularisation Kenton Tang University of Edinburgh Yuzhu Chen University of Science and Technology of China Fengxiang He University of Edinburgh Abstract Alignment and adaptation in large language models heavily rely on reinforcement learning from human feedback (RLHF); yet, theoretical understanding of its generalisability remains premature, especially when the learned reward could shift, and the KL control is estimated and clipped. To address this issue, we develop generalisation theory for RLHF that explicitly accounts for (1) reward shift: reward models are trained on preference data from earlier or mixed behaviour policies while RLHF optimises the current policy on its own rollouts; and (2) clipped KL regularisation: the KL regulariser is estimated from sampled log-probability ratios and then clipped for stabilisation, resulting in an error to RLHF. We present generalisation bounds for RLHF, suggesting that the generalisation error stems from a sampling error from prompts and rollouts, a reward shift error, and a KL clipping error. We also discuss special cases of (1) initialising RLHF parameters with a uniform prior over a finite space, and (2) training RLHF by stochastic gradient descent, as an Ornstein-Uhlenbeck process. The theory yields practical implications in (1) optimal KL clipping threshold, and (2) budget allocation in prompts, rollouts, and preference data. 1 Introduction Reinforcement learning from human feedback (RLHF) has become a central method for steering large language models (LLMs) towards better reflecting human preferences [christiano2017deep, stiennon2020learning], task requirements [ouyang2022training, chung2022scaling], safety constraints [bai2022training, bai2022constitutional], amongst many others. Despite the empirical success of RLHF, the theoretical understanding of its generalisability remains largely absent. To address this issue, this paper presents generalisation bounds for RLHF. To note, we analyse the post-trained policy in deployment, rather than studying online reinforcement learning during interactions with the environment. A typical RLHF algorithm consists of two coupled components: (1) a reward model trained from preference data and serving as a proxy for human judgment, and (2) a policy model optimised to maximise the reward model. Most RLHF algorithms additionally employ Kullback-Leibler (KL) regularisation to keep the policy close to a reference model, typically, a supervised fine-tuned (SFT) model [ziegler2019fine], for improving stability and limiting distribution shift [schulman2015trpo]. These induce two major challenges that significantly complicate analysis, as follows. Reward shift. The reward model is usually trained on preference data collected from an earlier behaviour policy or a mixture of policies [christiano2017deep]. However, the policy model is evaluated and optimised on rollouts drawn from the current distribution of responses. As the policy improves or drifts, it can move into regions where the reward model is less reliable, creating a feedback loop in which reward-model error is amplified in optimisation [gao2022scaling]. This calls for the potential RLHF generalisation theory to account for reward shift between the data used to train the reward model and the rollout distribution induced by the current policy. Clipped KL regularisation. KL regularisation is usually assumed to be computed as a population expectation in theoretical treatments [schulman2015trpo]. In practice, however, the KL control is computed from sampled sequences through log probability ratios; empirical analyses have shown that the choice of estimator and implementation details can materially affect optimisation stability [shah2025comedy]. A common stabilisation is to clip the per-sample log ratio, in order to control rare trajectories whose likelihood ratios are extreme, echoing clipping used in PPO [schulman2017ppo, lambert2025rlhfbook]. This clipped KL regularisation further introduces an error. Motivated by these, we develop generalisation theory for RLHF that explicitly accounts for both: the reward is learned and shifting, rather than given and fixed; and the KL regularisation is estimated and clipped, rather than an exact population quantity. Based on a change-of-measure decomposition and employing PAC-Bayes tools [mcallester1999modelavg, seeger2002pac, catoni2007pac], our analysis yields high-probability generalisation bounds for the learned, data-dependent policy that decompose the generalisation error into three distinct, interpretable sources: (1) a sampling error, induced by the two-stage sampling of observing finitely many prompts and estimating expectations from limited Monte Carlo rollouts, (2) a reward shift error, capturing the gap between the learned reward and the (implicit) target reward, and the additional error induced when the policy-driven rollout distribution differs from the reward model’s training distribution, (3) a KL clipping error, characterising the deviation from the clipped KL regulariser. A good theory has practical implications. Our theory suggests: (1) optimal KL clipping threshold: the theory indicates that the KL log-ratio clipping threshold τ controls the bias-variance trade-off, since clipping reduces sampling noise while introducing an objective mismatch that does not vanish asymptotically. Our theory further provides advice on how to strike a good balance; (2) budget allocation across prompts, rollouts, and preference labels: our generalisation bounds separate the impacts of prompts, rollouts per prompt, and preference labels, thereby guiding budget allocation across prompts and rollouts, and preference data collection. 2 Related Work Optimisation theory of RLHF Efforts have been made in theoretically studying RLHF from an optimisation perspective. zhu2023principled analyse RLHF based on pair-wise and list-wise comparisons, and characterise how the reward model error can induce suboptimal policies, motivating conservative strategies under coverage assumptions. Similarly, zhan2023provable provide finite-sample guarantees for offline RLHF that depend on a concentrability coefficient quantifying the coverage of the target policy by the offline data. xiong24a establish finite-sample guarantees for KL-regularised RLHF, in the offline, online, and hybrid regimes. Reward shift The literature has seen empirical studies on the impact of reward shift. gleave2022uncertainty empirically study uncertainty estimation for reward models, highlighting that reward models can be unreliable out of distribution. gao2022scaling empirically characterise reward model over-optimisation by measuring how the proxy-oracle gap grows when a policy is optimised against a learned proxy reward and evaluated under a stronger oracle reward. In addition, RewardBench provides a complementary evaluation resource for quantifying reward model behaviour on challenging and out-of-distribution comparisons [lambert2024rewardbench]. Clipped KL regularisation As an empirical work, shah2025comedy provide an extensive analysis showing that several commonly used estimators for KL regularisation can produce biased gradients, which can affect optimisation and stability. liu2025rethinkingkl analyse KL regularisation implementations in RLHF and characterise when common choices are principled or biased, including off-policy bias that arises when importance weighting is neglected. Concurrent paper A concurrent work, released on 23 Jan 2026, provides interesting results on the generalisation of RLHF, under linear reward model assumption, through the algorithmic stability framework [li2026generalization]. Our work is more general, formulated for RLHF pipelines beyond linear reward; instead, the reward in this paper is learned from preference data and shifts with policy updates. Moreover, our paper allows the KL control to be estimated from sampled log ratios and clipped for stabilisation, while li2026generalization formulate the KL penalty as an exact conditional KL divergence term in the objective, without sample-based KL estimation or clipping. 3 Preliminaries RLHF Given a prompt x∈x , a policy π specifies a conditional distribution π(⋅∣x)π(· x) over responses y∈y . We denote the post-trained policy by πθ _θ with parameter θ∈Θθ∈ , and denote πref _ref as a fixed reference policy. Evaluation uses prompts drawn from a distribution ρ, while preference data for reward modelling may come from a different prompt distribution ρlabel _label because of prompt shift. Suppose the target reward is r⋆:×→[0,1]r :X×Y→[0,1]. A reward model is a proxy r^ϕ:×→[0,1] r_φ:X×Y→[0,1], with parameter ϕ∈Φφ∈ ; the pointwise error is eϕ(x,y)=r^ϕ(x,y)−r⋆(x,y)e_φ(x,y)= r_φ(x,y)-r (x,y). Training the reward model uses a data collection distribution, defined as Dtrain(x,y)=ρlabel(x)πref(y∣x)D_train(x,y)= _label(x) _ref(y x), where we also use πref _ref as the behaviour policy for reward-data collection. In practice, this policy can be a mixture, and we write πref(⋅∣x):=∑m=1Mcmπ(m)(⋅∣x) _ref(· x):= _m=1^Mc_mπ^(m)(· x), reflecting the standard practice of collecting preference rankings over diverse behaviour policy mixtures. Moreover, the policy-induced distribution is defined as Dθ(x,y)=ρ(x)πθ(y∣x)D_θ(x,y)=ρ(x)\, _θ(y x). The reward model is evaluated on the training distribution by the mean-squared error Ltrain(2)(ϕ)L_train^(2)(φ), defined by (X,Y)∼Dtrain[(r^ϕ(X,Y)−r⋆(X,Y))2]. _(X,Y) D_train\! [ ( r_φ(X,Y)-r (X,Y) )^2 ]. (1) This quantity is an oracle-risk term defined with respect to r⋆r , and is typically not directly observable from pairwise preference labels in practice. Clipped KL regularisation Let β>0β>0 denote the regularisation strength, and ℓθ(x,y)=log⁡πθ(y∣x)−log⁡πref(y∣x) _θ(x,y)= _θ(y x)- _ref(y x) denote the exact log ratio. This log ratio is the per-sample quantity that appears when the KL control is implemented from sampled rollouts, which refer to the response sequence generated by sampling sequentially from the policy conditioned on the prompt. Its conditional expectation strictly recovers the standard reference KL divergence (Definition 2, Appendix B) within the population objective. In particular, for every prompt x, we have Y∼πθ(⋅∣x)[ℓθ(x,Y)]=KL(πθ(⋅∣x)∥πref(⋅∣x))E_Y _θ(· x)\! [ _θ(x,Y) ]=KL\! ( _θ(· x)\, \|\, _ref(· x) ). In post-training, ℓθ(x,y) _θ(x,y) can have a large magnitude on rare samples, which can significantly increase the variance of empirical KL-related quantities and destabilise optimisation unless additional control is imposed [shah2025comedy, lambert2025rlhfbook]. To stabilise KL control while keeping the target objective explicit, a popular approach is clipping with threshold τ>0τ>0: ℓθτ(x,y)=clip⁡(ℓθ(x,y),−τ,τ) _θ^τ(x,y)=clip( _θ(x,y),-τ,τ) [schulman2017ppo, lambert2025rlhfbook]. Correspondingly, the clipped population objective Jr,τ(θ)J^r,τ(θ) is given by X∼ρY∼πθ(⋅∣X)[r(X,Y)−βℓθτ(X,Y)]. _X ρE_Y _θ(· X)\! [r(X,Y)-β\, _θ^τ(X,Y) ]. (2) Generalisation The population objective is Jr(θ)=X∼ρY∼πθ(⋅∣X)[r(X,Y)−βℓθ(X,Y)],J^r(θ)=E_X ρE_Y _θ(· X)\! [r(X,Y)-β\, _θ(X,Y) ], where ℓθ(x,y)=log⁡πθ(y∣x)−log⁡πref(y∣x) _θ(x,y)= _θ(y x)- _ref(y x) is the exact log ratio. Evaluating a policy relies on finite prompts and rollouts. Let x1,…,xnx_1,…,x_n be independent prompts drawn from ρ. For each xix_i, let yi,1,…,yi,Ky_i,1,…,y_i,K denote K independent rollouts drawn from πθ(⋅∣xi) _θ(· x_i). The resulting empirical objective is J^n,Kr,τ(θ)=1n∑i=1n1K∑j=1K[r(xi,yi,j)−βℓθτ(xi,yi,j)]. J_n,K^r,τ(θ)= 1n _i=1^n 1K _j=1^K [r(x_i,y_i,j)-β\, _θ^τ(x_i,y_i,j) ]. For brevity, J^n,Kϕ,τ(θ) J_n,K^φ,τ(θ) denotes J^n,Kr^ϕ,τ(θ) J_n,K r_φ,τ(θ); J⋆(θ)J (θ) denotes Jr⋆(θ)J^r (θ); Jϕ(θ)J^φ(θ) denotes Jr^ϕ(θ)J r_φ(θ); Jϕ,τ(θ)J^φ,τ(θ) denotes Jr^ϕ,τ(θ)J r_φ,τ(θ). The generalisability can be quantified by the generalisation error, defined to be the discrepancy between the empirical and population objectives: |J^n,Kϕ,τ(θ)−J⋆(θ)| | J_n,K^φ,τ(θ)-J (θ) |. 4 Main Results This section presents our theoretical results. 4.1 Decomposing Generalisation Error We decompose the generalisation error into three components: (1) a sampling error, induced by prompts and rollouts, which is present even if the following two terms do not exist; (2) a reward shift error, induced by reward shift under the same exact KL regulariser; and (3) a KL clipping error, induced by the objective mismatch induced by estimating and clipping the KL penalty. Lemma 1 (Generalisation error decomposition). Given parameters θ∈Θθ∈ and ϕ∈Φφ∈ , and clipping threshold τ>0τ>0. Then, we have the following decomposition, |J^n,Kϕ,τ(θ)−J⋆(θ)| | J_n,K^φ,τ(θ)-J (θ) | (3) ≤ ≤ |J^n,Kϕ,τ(θ)−Jϕ,τ(θ)|⏟sampling error+|Jϕ(θ)−J⋆(θ)|⏟reward shift error | J_n,K^φ,τ(θ)-J^φ,τ(θ) |_sampling error+ |J^φ(θ)-J (θ) |_reward shift error +|Jϕ,τ(θ)−Jϕ(θ)|⏟KL clipping error + |J^φ,τ(θ)-J^φ(θ) |_KL clipping error 4.2 Sampling Error Bound We first study the sampling error |J^n,Kϕ,τ(θ)−Jϕ,τ(θ)| | J_n,K^φ,τ(θ)-J^φ,τ(θ) |. We define J^n,∞r,τ(θ) J_n,∞^r,τ(θ) as the conditional expectation of J^n,Kr,τ(θ) J_n,K^r,τ(θ), given the prompts x1:nx_1:n. Equivalently, it is the value one would obtain by averaging infinitely many rollouts per prompt while keeping the same finite set of prompts. The estimator J^n,Kϕ,τ(θ) J_n,K^φ,τ(θ) thus has a two-stage structure: (1) prompts are sampled from ρ, leading to a deviation |J^n,∞r,τ(θ)−Jr,τ(θ)| | J_n,∞^r,τ(θ)-J^r,τ(θ) |, and (2) rollouts are sampled from πθ(⋅∣x) _θ(· x), conditional on each prompt, inducing a deviation |J^n,Kr,τ(θ)−J^n,∞r,τ(θ)| | J_n,K^r,τ(θ)- J_n,∞^r,τ(θ) |. We first bound the rollout sampling error as follows. Lemma 2 (Rollout sampling error bound). Given parameter θ∈Θθ∈ , reward r:×→[0,1]r:X×Y→[0,1], clipping threshold τ>0τ>0, and confidence level δ∈(0,1)δ∈(0,1), with probability at least 1−δ1-δ over rollouts, conditional on prompts x1:nx_1:n, we have |J^n,Kr,τ(θ)−J^n,∞r,τ(θ)|≤(1+2βτ)log⁡(2/δ)2nK. | J_n,K^r,τ(θ)- J_n,∞^r,τ(θ) |≤ (1+2βτ ) (2/δ)2nK. Proof sketch Loss clipping ensures that ℓθτ(x,y)∈[−τ,τ] _θ^τ(x,y)∈[-τ,τ] by construction, which is a standard stabilisation approach in reinforcement learning [mnih2015dqn, schulman2017ppo]. Combining that the reward function satisfies r(x,y)∈[0,1]r(x,y)∈[0,1], for each per-rollout contribution, r(x,y)−βℓθτ(x,y)r(x,y)-β\, _θ^τ(x,y) lies in an interval of length 1+2βτ1+2βτ. Given the prompts x1:nx_1:n, the rollouts are independent across both i and j. Applying Hoeffding’s inequality (Lemma 8) to the average over the nKnK rollout terms yields Lemma 2. Detailed proofs are in Appendix C.2. Remark 1. Lemma 2 controls the Monte Carlo error from using finitely many rollouts per prompt. The bound decays at rate O(nK)−1/2O(nK)^-1/2 as the number of rollouts per prompt K increases (assuming β and τ are independent of n and K). The factor 1+2βτ1+2βτ comes from the range of the per-rollout contribution. Clipping is the mechanism that makes this range finite without imposing any artificial uniform bound on the exact log ratio ℓθ _θ. Lemma 3 (Prompt sampling error bound). Under the same conditions of Lemma 2, with probability at least 1−δ1-δ over prompts x1:nx_1:n, we have |J^n,∞r,τ(θ)−Jr,τ(θ)|≤(1+2βτ)log⁡(2/δ)2n. | J_n,∞^r,τ(θ)-J^r,τ(θ) |≤ (1+2βτ ) (2/δ)2n. Proof sketch Treating J^n,∞ϕ,τ(θ) J_n,∞^φ,τ(θ) as a function of the sampled prompts only, it is an average of n independent bounded terms, each term being the conditional expectation over rollouts for a fixed prompt. Applying Hoeffding’s inequality again yields Lemma 3. Detailed proofs are in Appendix C.2. Remark 2. Lemma 3 suggests that the prompt sampling error decays at rate O(n−1/2)O(n^-1/2), and the corresponding bound does not depend on the number of rollouts per prompt K, similarly, assuming β and τ are independent of n and K. It isolates the deviation induced purely by finite prompt sampling. Even an arbitrarily accurate estimate of each conditional expectation over rollouts cannot compensate for having too few evaluation prompts, because the population objective is defined as an expectation over ρ. Combining the two lemmas leads to the following lemma on the sampling error. Lemma 4 (Sampling error bound). Under the same conditions of Lemma 2, with probability at least 1−δ1-δ over both prompts and rollouts, the sampling error satisfies |J^n,Kr,τ(θ)−Jr,τ(θ)| | J_n,K^r,τ(θ)-J^r,τ(θ) | (4) ≤(1+2βτ)(log⁡(4/δ)2n+log⁡(4/δ)2nK). ≤(1+2βτ) ( (4/δ)2n+ (4/δ)2nK ). Remark 3. In addition to the noise induced by prompts and rollouts, a penalty term carries the additional factor 2βτ2βτ because the clipped log ratio ranges in [−τ,τ][-τ,τ]. Consequently, increasing τ enlarges the range of each rollout penalty term, and the resulting concentration bound is looser. 4.3 Reward shift error bound This subsection studies the reward shift error |Jϕ(θ)−J⋆(θ)| |J^φ(θ)-J (θ) |. To characterise the reward shift error in transfers from DtrainD_train to DθD_θ, we use a χ2χ^2 coverage coefficient, defined below, based on χ2χ^2 divergence (see Definition 3 in Appendix B). χ2χ^2 coverage coefficient is standard in the literature of importance weighting and covariate shift analyses; see, e.g., sugiyama2007covariate, owen_chisq_notes. Definition 1 (χ2χ^2 coverage coefficient). Suppose that DθD_θ is absolutely continuous with respect to DtrainD_train. The χ2χ^2 coverage coefficient is defined to be (θ):=1+χ2(Dθ∥Dtrain),C(θ):= 1+χ^2(D_θ\|D_train), (5) where χ2(⋅∥⋅)χ^2(·\|·) is χ2χ^2 divergence. Remark 4. Intuitively, (θ)C(θ) measures how far the policy-induced distribution departs from the distribution used to train the reward model. It acts as an amplification factor when we upper bound the reward shift error. Because Jϕ(θ)J^φ(θ) and J⋆(θ)J (θ) share the same exact KL regulariser, the KL penalty cancels in the difference; consequently, only the reward model error remains. Defining eϕ(x,y)=r^ϕ(x,y)−r⋆(x,y)e_φ(x,y)= r_φ(x,y)-r (x,y), we have Jϕ(θ)−J⋆(θ)=(X,Y)∼Dθ[eϕ(X,Y)]J^φ(θ)-J (θ)=E_(X,Y) D_θ\! [e_φ(X,Y) ], so the problem is to control the reward model error under the deployment distribution DθD_θ using information available under the training distribution DtrainD_train. This step requires a coverage condition, stated below, when deriving the change-of-measure bound; it yields the same coefficient (θ)C(θ) defined in eq. (5). Assumption 1 (Absolute continuity and finite coverage). The policy-induced distribution DθD_θ is absolutely continuous with respect to the reward model training distribution DtrainD_train. Moreover, the χ2χ^2 divergence χ2(Dθ∥Dtrain)χ^2(D_θ\|D_train) is finite, so the coverage coefficient (θ)C(θ) in eq. (5) is finite. Remark 5. Assumption 1 is the standard condition that makes a change of measure from DθD_θ back to DtrainD_train legitimate [sugiyama2007covariate, shimodaira2000covariate, precup2000eligibility]. It ensures that the density ratio dDθdDtrain dD_θdD_train exists and has a finite second moment, which is required for the Cauchy-Schwarz step in Lemma 5 [owen_chisq_notes]. The coefficient (θ)C(θ) plays the role of an amplification factor, which quantifies how strongly the reward model error can be magnified when the policy visits regions that are rare under the data used for reward modelling. Our theory also relies on the following mild assumption. Assumption 2 (Bounded training error). The squared training error Ltrain(2)(ϕ)L_train^(2)(φ) defined in eq. (1) is bounded. Remark 6. This assumption does not assert that the reward model is accurate everywhere; instead, it provides a baseline level of accuracy on the distribution where preference supervision is available. The coverage coefficient explains how the baseline can degrade under deployment. We then prove the reward shift bound. Lemma 5 (Reward shift error bound). Under Assumptions 1 and 2, we have |Jϕ(θ)−J⋆(θ)|≤(θ)Ltrain(2)(ϕ). |J^φ(θ)-J (θ) | (θ)\, L_train^(2)(φ). Proof sketch To relate |Jϕ(θ)−J⋆(θ)| |J^φ(θ)-J (θ) | to the training distribution, we rewrite the expectation under DθD_θ as an importance-weighted expectation under DtrainD_train. Assumption 1 ensures that the required density ratio exists and has finite second moment. Applying the χ2χ^2 change-of-measure bound (Lemma 11 in Appendix B) yields a product of two square roots: the first factor under the square root is exactly 1+χ2(Dθ∥Dtrain)1+χ^2(D_θ\|D_train), the second moment of the density ratio under DtrainD_train, whose square root therefore produces (θ)C(θ); and the second factor under the square root is Ltrain(2)(ϕ)L_train^(2)(φ) by definition, the second moment of the reward model error under DtrainD_train. This yields Lemma 5. Detailed proofs are in Appendix C.3. Remark 7. Lemma 5 characterises two ingredients that play different roles: (1) the term Ltrain(2)(ϕ)L_train^(2)(φ) measures reward model error only on the reward model training distribution DtrainD_train; and (2) the coefficient (θ)C(θ) measures how far DθD_θ moves away from that training distribution. It also quantifies how much training error can be amplified when moving to deployment. When prompt shifts and policy shifts are qualitatively different, it is useful to further factorise the coverage coefficient. The next lemma interprets the source of shifts in practice. Lemma 6 (Coverage factorisation). Suppose ρ≪ρlabelρ _label and πθ(⋅∣x)≪πref(⋅∣x) _θ(· x) _ref(· x), for any prompt x with ρlabel(x)>0 _label(x)>0. Define prompt=(X∼ρlabel[(ρ(X)ρlabel(X))2])1/2,C_prompt= (E_X _label [ ( ρ(X) _label(X) )^2 ] )^1/2, and define pol(θ)C_pol(θ) by supx∈:ρlabel(x)>0(Y∼πref(⋅∣x)[(πθ(Y∣x)πref(Y∣x))2])1/2. aligned _x : _label(x)>0 (E_Y _ref(· x) [ ( _θ(Y x) _ref(Y x) )^2 ] )^1/2 aligned. If both promptC_prompt and pol(θ)C_pol(θ) are bounded, we have (θ)≤promptpol(θ)C(θ) _prompt\,C_pol(θ). Remark 8. Lemma 6 separates mismatch in prompts from mismatch in policies. The coefficient promptC_prompt depends only on the shift between ρ and ρlabel _label. The coefficient pol(θ)C_pol(θ) depends only on how far πθ _θ departs from πref _ref on the support of ρlabel _label. This separation is valuable when diagnosing failures in reward modelling and post training, because the two sources of shift have different operational causes and different mitigation strategies. 4.4 KL Clipping Error Bound We now bound the KL clipping error |Jϕ,τ(θ)−Jϕ(θ)|. |J^φ,τ(θ)-J^φ(θ) |. This is the only place where the systematic mismatch created by clipping enters the analysis. Clipping is beneficial in the sampling bounds because it makes each rollout contribution bounded. Meanwhile, clipping may bias the objective used in practice, thereby introducing a systematic mismatch between the optimised objective and the target objective. To state this mismatch cleanly, we only require an integrability condition on the exact log ratio in deployment. Assumption 3 (Integrability of exact log ratio). The exact log ratio is integrable in deployment, i.e., (X,Y)∼Dθ[|ℓθ(X,Y)|]<∞E_(X,Y) D_θ\! [| _θ(X,Y)| ]<∞. Remark 9. Assumption 3 is mild. It allows heavy tails in ℓθ _θ while still ensuring that the exact objective is well defined. Under this assumption, clipping is analysed as an explicit bias-inducing modification of the penalty; the KL clipping error term in Lemma 7, β(X,Y)∼Dθ[|ℓθ(X,Y)−ℓθτ(X,Y)|],β\,E_(X,Y) D_θ\! [ | _θ(X,Y)- _θ^τ(X,Y) | ], is an objective mismatch term that does not vanish asymptotically as the number of evaluation prompts or rollouts increases. It is strictly weaker than assuming ℓθ _θ is uniformly bounded, and it matches the intent of treating clipping as an algorithmic choice rather than as a structural property of the policy class. Similar integrability conditions are standard in analysing truncation-based stabilisation and importance sampling; see, e.g., ionides2008truncated, owen2000safeis. We then prove the following bound on the bias induced by the surrogate. Lemma 7 (KL clipping error bound). Under Assumption 3, we have |Jϕ,τ(θ)−Jϕ(θ)| |J^φ,τ(θ)-J^φ(θ) | (6) ≤β(X,Y)∼Dθ[|ℓθ(X,Y)−ℓθτ(X,Y)|]. ≤β\,E_(X,Y) D_θ\! [ | _θ(X,Y)- _θ^τ(X,Y) | ]. Proof sketch |Jϕ,τ(θ)−Jϕ(θ)| |J^φ,τ(θ)-J^φ(θ) | is not an estimation error; it compares two population objectives under the same learned reward, with the only difference being whether the penalty uses ℓθτ _θ^τ or ℓθ _θ. Expanding definitions shows that the reward contributions cancel and only the penalty difference remains. Taking absolute values and applying the triangle inequality yields Lemma 7. Detailed proofs are in Appendix C.3. Remark 10. The right-hand side of eq. (6) measures clipping bias directly as the expected amount of truncation under the deployment distribution. This term can remain nonzero even with infinite evaluation data, which reflects the fact that clipping is an objective mismatch rather than an estimation error. It is small when the policy rarely produces extreme log ratios under DθD_θ, and it can be large when the policy places substantial mass in regions where the exact log ratio has heavy tails. This is why the final bound contains a term that depends on the tail behaviour of the exact log ratio under DθD_θ and does not involve n or K. 4.5 Fixed-Policy generalisation Bound We now combine the results on sampling error, reward shift error, and KL clipping error into a single statement for a fixed policy parameter θ, as follows. Theorem 1 (Fixed-policy generalisation bound). Under Assumptions 1, 2, and 3, with probability at least 1−δ1-δ over the evaluation prompts and rollouts, the following holds, |J^n,Kϕ,τ(θ)−J⋆(θ)| | J_n,K^φ,τ(θ)-J (θ) | (7) ≤(1+2βτ)(log⁡(4/δ)2n+log⁡(4/δ)2nK)⏟sampling error ≤ (1+2βτ) ( (4/δ)2n+ (4/δ)2nK )_sampling error +(θ)Ltrain(2)(ϕ)⏟reward shift error + C(θ)\, L_train^(2)(φ)_reward shift error +β(X,Y)∼Dθ[|ℓθ(X,Y)−ℓθτ(X,Y)|]⏟KL clipping error. + β\,E_(X,Y) D_θ\! [ | _θ(X,Y)- _θ^τ(X,Y) | ]_KL clipping error. 4.6 Data-Dependent PAC-Bayes Bound The fixed-policy theorem treats θ as pre-fixed. In practice, θ is often selected after observing data. This section fixes the gap by employing PAC-Bayes theory that extends our analysis to data-dependent selection [mcallester1999modelavg, seeger2002pac, catoni2007pac]. Specifically, we provide a bound that holds simultaneously for all posteriors Q over Θ , at the cost of a complexity term that measures how far Q deviates from a prior P on Θ . Define J^n,Kϕ,τ(Q)=θ∼Q[J^n,Kϕ,τ(θ)],J⋆(Q)=θ∼Q[J⋆(θ)]. J_n,K^φ,τ(Q)=E_θ Q\! [ J_n,K^φ,τ(θ) ], J (Q)=E_θ Q\! [J (θ) ]. Then, we have the following data-dependen PAC-Bayes bound. Theorem 2 (Data-dependent generalisation bound). Let P be any prior distribution on Θ that is independent of the evaluation prompts and rollouts. For any posterior Q on Θ , suppose Assumptions 1, 2, and 3 hold for any θ in the support of Q. Then, with probability at least 1−δ1-δ over the evaluation prompts and rollouts, the following inequality holds simultaneously for all such posteriors Q, |J^n,Kϕ,τ(Q)−J⋆(Q)| | J_n,K^φ,τ(Q)-J (Q) | ≤(1+2βτ)(KL(Q∥P)+log⁡(8/δ)2n+KL(Q∥P)+log⁡(8/δ)2nK)⏟sampling error ≤ (1+2βτ) aligned & ( KL(Q\|P)+ (8/δ)2n\\ & + KL(Q\|P)+ (8/δ)2nK ) aligned_sampling error +θ∼Q[(θ)]Ltrain(2)(ϕ)⏟reward shift error + E_θ Q\! [C(θ) ]\, L_train^(2)(φ)_reward shift error +βθ∼Q[(X,Y)∼Dθ[|ℓθ(X,Y)−ℓθτ(X,Y)|]]⏟KL clipping error. + β\,E_θ Q\! [E_(X,Y) D_θ\! [ | _θ(X,Y)- _θ^τ(X,Y) | ] ]_KL clipping error. Remark 11. Comparing with Theorem 1, Theorem 2 replaces the fixed θ with an average over θ∼Qθ Q. The complexity term KL(Q∥P)KL(Q\|P) appears only inside the sampling error, as the price paid for making the guarantee hold uniformly over data-dependent choices of Q. 5 Special cases The PAC-Bayes bound in Theorem 2 contains a complexity term KL(Q∥P)KL(Q\|P), which measures how strongly the data-dependent posterior Q departs from the data-independent prior P. This subsection discusses two operational instantiations of KL(Q∥P)KL(Q\|P) that are common in practice. 5.1 Initialisation by uniform prior over finite candidate class Let M≥2M≥ 2 be an integer, θ(1),…,θ(M)∈Θθ^(1),…,θ^(M)∈ be a collection of candidate parameters specified independently of the evaluation sample used to construct J^n,Kϕ,τ J_n,K^φ,τ. Suppose ΘM:=θ(1),…,θ(M) _M:=\θ^(1),…,θ^(M)\ and restrict both P and Q to be distributions on ΘM _M. Suppose the prior is uniform on ΘM _M; i.e., P(θ(m))=1/MP(θ^(m))=1/M for any m. This non-informative prior is standard in finite model selection [seeger2002pac]. Corollary 1 (KL bound for uniform prior over finite candidate class). Under the conditions above, KL(Q∥P)≤log⁡MKL(Q\|P)≤ M. In particular, if Q is the Dirac distribution supported on a data-selected checkpoint θ(m^)θ^( m), we have KL(Q∥P)=log⁡MKL(Q\|P)= M. Remark 12. Corollary 1 yields a direct interpretation of model selection in the PAC-Bayes bound. Evaluating M fixed checkpoints and selecting one using the evaluation sample incurs an additional sampling error cost in Theorem 2, controlled by log⁡M M via the quantity KL(Q∥P)KL(Q\|P). 5.2 Training RLHF by SGD as Ornstein-Uhlenbeck process Stochastic gradient descent (SGD), and its variants, are popular optimisers [RobbinsMonro1951]. Suppose the parameter space is ℝdR^d for some d∈ℕd . Assume the prior is Gaussian, i.e., P=(θ0,Λ)P=N( _0, ) for some θ0∈ℝd _0 ^d and some symmetric positive definite matrix Λ∈ℝd×d ^d× d. We employ a standard local diffusion approximation for constant-step-size SGD. Near a locally stable optimum, late-stage SGD iterates follow an Ornstein-Uhlenbeck (OU) process [Uhlenbeck1930]: dθt=−H(θt−θ^)dt+εΣg1/2dWt,d _t=-H( _t- θ)\,dt+ \, _g^1/2\,dW_t, where WtW_t is a d-dimensional Brownian motion, H≻0H 0 is the local Hessian at θ θ, and Σg≻0 _g 0 is the local gradient-noise covariance. We make the following assumptions, standard for this local OU approximation; see Mandt2017, he2019control, chen2023stochastic. Assumption 4. Assume the optimisation problem has a locally stable optimum θ^∈ℝd θ ^d; i.e., within a neighbourhood of θ θ, the objective admits a quadratic approximation with Hessian H≻0H 0 and the gradient noise covariance is approximately constant and equal to Σg≻0 _g 0. In addition, the matrices H and Σg _g commute; i.e., HΣg=ΣgH _g= _gH holds. Moreover, there exist constants 0<m≤M<∞0<m≤ M<∞ such that the local curvature spectrum satisfies mI⪯H⪯MImI H MI. Under the assumption above, the OU process admits a stationary Gaussian law (θ^,Σ)N( θ, ), where Σ≻0 0 satisfies the continuous Lyapunov equation HΣ+ΣH=εΣgH + H= _g. Accordingly, we approximate the PAC-Bayes posterior induced by late-stage SGD iterates by QSGD:=(θ^,Σ).Q_SGD:=N( θ, ). Corollary 2 (KL bound for SGD as Ornstein-Uhlenbeck process). In the special case above, the PAC-Bayes complexity term admits the upper bound KL(QSGD∥P) (Q_SGD\|P) (8) ≤12( ≤ 12 ( (θ^−θ0)⊤Λ−1(θ^−θ0)+ε2mtr⁡(Λ−1Σg)−d ( θ- _0) ^-1( θ- _0)+ 2mtr( ^-1 _g)-d +logdet(Λ)−logdet(Σg)−dlog(ε2M)). + \! ( )- \! ( _g)-d ( 2M ) ). A detailed proof is given in Appendix C.7.2. Remark 13. Corollary 2 yields a locally valid, optimiser-explicit bound for KL(Q∥P)KL(Q\|P) via the stationary diffusion approximation of constant-step-size SGD. This secondary specialisation of Theorem 2 imposes no additional structural assumptions on the main RLHF analysis. The diffusion perspective and the associated Ornstein-Uhlenbeck approximation are discussed in detail by Mandt2017. 6 Practical Implications The discussion below translates our theory into concrete, practical algorithm design recommendations. 6.1 Optimal KL clipping threshold Lemma 4 includes a factor 1+2βτ1+2βτ, indicating that a smaller τ tightens the sampling deviations that arise from finite n and K. Lemma 12 in Appendix B gives the corresponding KL-specific concentration bound for the clipped log-ratio average, whose deviation also scales linearly with τ. Meanwhile, clipping changes the regularised objective and introduces a systematic mismatch that does not vanish with more evaluation samples, as formalised in Lemma 7. Therefore, τ acts as a bias-variance trade-off hyperparameter rather than a purely stabilising tweak. Aggressive clipping reduces Monte Carlo noise but increases objective mismatch; weak clipping preserves the exact KL objective but exposes training to high-variance log-ratio estimates. For brevity, we define αn,K,δ:= _n,K,δ= log⁡(4/δ)2n+log⁡(4/δ)2nK, (4/δ)2n+ (4/δ)2nK, Tθ(τ):= T_θ(τ)= (X,Y)∼Dθ[(|ℓθ(X,Y)|−τ)+]. _(X,Y) D_θ [(| _θ(X,Y)|-τ)_+ ]. Since |ℓθ−ℓθτ|=(|ℓθ|−τ)+| _θ- _θ^τ|=(| _θ|-τ)_+ under symmetric clipping, the τ-dependent part of eq. (7) is thus Bθ(τ):=(1+2βτ)αn,K,δ+βTθ(τ).B_θ(τ):=(1+2βτ)\, _n,K,δ\;+\;β\,T_θ(τ). Let τ⋆τ be any minimiser of τ↦Bθ(τ)τ B_θ(τ) over τ≥0τ≥ 0. We have the following corollary. Corollary 3 (Optimal KL clipping threshold). For any parameters θ∈Θθ∈ and ϕ∈Φφ∈ , regularisation coefficient β>0β>0, confidence level δ∈(0,1)δ∈(0,1), and integers n≥1n≥ 1 and K≥1K≥ 1, if 2αn,K,δ<12 _n,K,δ<1, τ⋆τ satisfies Pr(X,Y)∼Dθ⁡(|ℓθ(X,Y)|>τ⋆)≤ _(X,Y) D_θ\! (| _θ(X,Y)|>τ )\;≤\; 2αn,K,δ≤Pr(X,Y)∼Dθ⁡(|ℓθ(X,Y)|≥τ⋆), 2\, _n,K,δ\;≤\; _(X,Y) D_θ\! (| _θ(X,Y)|≥τ ), if, in addition, Pr(X,Y)∼Dθ⁡(|ℓθ(X,Y)|=τ⋆)=0 _(X,Y) D_θ(| _θ(X,Y)|=τ )=0, we have Pr(X,Y)∼Dθ⁡(|ℓθ(X,Y)|>τ⋆)= 2αn,K,δ, _(X,Y) D_θ\! (| _θ(X,Y)|>τ )\;=\;2\, _n,K,δ, and, equivalently, τ⋆τ is the (1−2αn,K,δ)(1-2 _n,K,δ)-quantile of |ℓθ(X,Y)|| _θ(X,Y)| under DθD_θ. Otherwise, if 2αn,K,δ≥12 _n,K,δ≥ 1, we have τ⋆=0τ =0 is a minimizer of τ↦Bθ(τ)τ B_θ(τ) over τ≥0τ≥ 0. Detailed proofs are in Appendix C.4. Remark 14. Corollary 3 suggests choosing τ so that the clipping fraction Pr⁡(|ℓθ|>τ) (| _θ|>τ) matches the target level 2αn,K,δ2 _n,K,δ. As the evaluation budget (n or K) increases, αn,K,δ _n,K,δ decreases. Consequently, the target clipping fraction decreases and the recommended threshold τ increases. This quantile-based rule automatically relaxes clipping as Monte Carlo error diminishes. Threshold calibration Practitioners often treat the clipping threshold τ as a static hyperparameter that requires manual tuning. Corollary 3 instead yields a direct, budget-aware calibration rule. Given an evaluation batch (xi,yi,j)i≤n,j≤K\(x_i,y_i,j)\_i≤ n,\,j≤ K, compute the log-ratio magnitudes ui,j:=|ℓθ(xi,yi,j)|u_i,j:=| _θ(x_i,y_i,j)|. If 2αn,K,δ≥12 _n,K,δ≥ 1, set τ^:=0 τ:=0. Otherwise, set τ τ to the empirical (1−2αn,K,δ)(1-2 _n,K,δ)-quantile of ui,j\u_i,j\. Algorithmically, this theory-guided rule balances the bias–variance trade-off by clipping approximately the top 2αn,K,δ2 _n,K,δ fraction of extreme log-ratios in the batch, thereby reducing reliance on heuristic hyperparameter sweeps. Theorems 1–2 treat τ as fixed; when τ is selected from the evaluation sample (e.g., by an empirical quantile rule), the resulting procedure should be viewed as a practical calibration heuristic unless additional uniformity or sample-splitting arguments are used. 6.2 Budget allocation across prompts, rollouts, and preference data Given a fixed computational budget, practitioners often face an allocation trade-off among prompts, rollouts per prompt, and preference data. This subsection provides theoretically grounded guidelines for this budget distribution. 6.2.1 Uniform-cost baseline Suppose rollouts share the same cost and the sampling budget is bounded by nK≤BnK≤ B for some B>0B>0. Substituting n=B/Kn=B/K into the leading-order sampling terms of Lemma 4 reveals that the upper bound is minimised at K⋆=1K =1. Therefore, under a uniform-cost model, the range-based concentration bound strongly favours allocating budget to prompt coverage rather than additional rollouts per prompt. A detailed derivation is given in Appendix C.8. 6.2.2 Prefill and decode cost model In LLM inference, sampling costs are typically asymmetric across prompts and rollouts [pope2023transformer_inference]. Evaluating a new prompt requires a forward pass over prompt tokens to construct an attention cache, whereas additional rollouts reuse this cache, primarily incurring incremental decoding costs [kwon2023pagedattention]. We model this asymmetry by separating a prefill and a decode cost, imposing the constraint: B≥ncprefill+nKcdecodeB\;≥\;n\,c_prefill\;+\;nK\,c_decode. Substituting n=B/(cprefill+Kcdecode)n=B/(c_prefill+Kc_decode) into the dominant sampling structure isolates a one-dimensional objective in K. Treating K≥1K≥ 1 as a continuous variable in the leading-order proxy from Lemma 4 yields the following optimal allocation rule. Corollary 4 (Optimal rollout allocation). The continuous proxy minimiser over K≥1K≥ 1 satisfies K⋆=max⁡1,(cprefillcdecode)2/3.K \;=\; \! \1, ( c_prefillc_decode )^2/3 \. In practice, one may take K=⌊K⋆⌉K= K , and then set n by the budget constraint. Detailed proofs are in Appendix C.8. Remark 15. The expression for K⋆K depends only on the ratio cprefill/cdecodec_prefill/c_decode because the shared range multiplier 1+2βτ1+2βτ does not affect the minimiser. The 2/32/3 power law implies that the optimal number of rollouts per prompt grows sublinearly with cprefill/cdecodec_prefill/c_decode. Variance-aware refinement The range-based sampling simplification above is conservative because it does not separate prompt-level variability from rollout-level variability. A refinement is to use a two-stage variance decomposition. Let Z denote a per-rollout contribution in the empirical objective (see the variables Zi,jZ_i,j in the proof of Lemma 2 in Appendix C.2), and define σprompt2:=Var([Z∣X]),σrollout2:=[Var(Z∣X)]. _prompt^2:=Var\! (E[Z X] ), _rollout^2:=E\! [Var(Z X) ]. Corollary 5. Under the same cost constraint B≥ncprefill+nKcdecodeB≥ n\,c_prefill+nK\,c_decode, optimising the resulting variance proxy yields an allocation rule of the form K⋆≈max⁡1,cprefillcdecode⋅σrollout2σprompt2.K \;≈\; \! \1, c_prefillc_decode· _rollout^2 _prompt^2 \. A proof is given in Appendix C.8. 6.2.3 Preference data Beyond prompts and rollouts, the reward shift error introduces an additional budget consideration. By Lemma 5, this term depends on the reward-model training error Ltrain(2)(ϕ)L_train^(2)(φ) and the coverage coefficient (θ)C(θ). Preference data collection therefore affects the bound in two ways. Increasing relevant preference data can improve reward-model fit on the training distribution, and collecting data closer to the policy-induced distribution can reduce the mismatch captured by (θ)C(θ). These observations provide guidance for preference data collection through their effect on the reward shift term, although the present analysis does not derive an explicit allocation rule in terms of the number of preference labels. This implication is most relevant when the sampling terms are no longer the dominant terms in the bound. 7 Conclusions Alignment and adaptation in large language models (LLMs) are now driven by reinforcement learning from human feedback (RLHF), but a rigorous theory of how RLHF generalises is still underdeveloped, particularly when the reward could shift, and a KL clipping regularisation is implemented. To address this gap, we develop generalisation theory for RLHF that explicitly models two key practical effects: (1) distribution shift between the data used to train the reward model and the policy-induced distribution encountered at deployment, and (2) statistical noise introduced by empirical estimation of the clipped KL regulariser. We prove high-probability generalisation bounds that decompose the generalisation error into interpretable components, including sampling error from both prompts and rollouts, reward shift error, and KL clipping error. Our theory suggests optimal KL clipping threshold rules, quantitative budget allocation guidance on prompts and rollouts, and guidance for preference data collection through the reward shift term. References Generalisation of RLHF under Reward Shift and Clipped KL Regularisation (Supplementary Material) Appendix A Notation Table 1: Notation Symbol Meaning ,X,Y Prompt space and response space. (x,y)(x,y) A prompt-response pair. ρ Prompt distribution used for post-training / evaluation. ρlabel _label Prompt distribution used for collecting preference data (reward modelling). π(⋅∣x)π(· x) A policy: conditional distribution over responses given prompt x. πθ _θ Post-trained policy, parameterised by θ. Θ Policy parameter space. πref _ref Reference policy (typically an SFT model). θ Parameters of the policy πθ _θ. Φ Reward-model parameter space. ϕφ Parameters of the learned reward model r^ϕ r_φ. r⋆:×→[0,1]r :X×Y→[0,1] Target (oracle) reward function. r^ϕ:×→[0,1] r_φ:X×Y→[0,1] Learned reward model with parameters ϕφ. eϕ(x,y)e_φ(x,y) Reward-model error, typically eϕ(x,y)=r^ϕ(x,y)−r⋆(x,y)e_φ(x,y)= r_φ(x,y)-r (x,y). DtrainD_train Joint distribution for reward-model training, e.g. Dtrain(x,y)=ρlabel(x)πref(y∣x)D_train(x,y)= _label(x)\, _ref(y x). DθD_θ Policy-induced joint distribution, Dθ(x,y)=ρ(x)πθ(y∣x)D_θ(x,y)=ρ(x)\, _θ(y x). Ltrain(2)(ϕ)L^(2)_train(φ) Reward-model MSE on DtrainD_train: (X,Y)∼Dtrain[eϕ(X,Y)2]E_(X,Y) D_train[e_φ(X,Y)^2]. χ2(Dθ∥Dtrain)χ^2(D_θ\|D_train) Chi-square divergence measuring coverage / shift from DtrainD_train to DθD_θ. C(θ)C(θ) Coverage coefficient, typically C(θ)=1+χ2(Dθ∥Dtrain)C(θ)= 1+χ^2(D_θ\|D_train). CpromptC_prompt Prompt-shift component of coverage (in a factorisation of C(θ)C(θ)). Cpol(θ)C_pol(θ) Policy-shift component of coverage (in a factorisation of C(θ)C(θ)). β>0β>0 KL-regularisation strength (penalty coefficient). ℓθ(x,y) _θ(x,y) Log-ratio, ℓθ(x,y)=log⁡πθ(y∣x)−log⁡πref(y∣x) _θ(x,y)= _θ(y x)- _ref(y x). τ>0τ>0 Clipping threshold for log-ratios. ℓθτ(x,y) _θ^τ(x,y) Clipped log-ratio, ℓθτ(x,y)=clip(ℓθ(x,y),−τ,τ) _θ^τ(x,y)=clip( _θ(x,y),-τ,τ). KL(πθ(⋅∣x)∥πref(⋅∣x))KL( _θ(· x)\| _ref(· x)) Reference KL at prompt x (population expectation of ℓθ(x,Y) _θ(x,Y) under Y∼πθ(⋅∣x)Y _θ(· x)). Jr(θ)J_r(θ) Population objective under reward r: X∼ρ,Y∼πθ(⋅∣X)[r(X,Y)−βℓθ(X,Y)]E_X ρ,Y _θ(· X)[r(X,Y)-β\, _θ(X,Y)]. Jr,τ(θ)J_r,τ(θ) Clipped population objective: replace ℓθ _θ by ℓθτ _θ^τ in Jr(θ)J_r(θ). J⋆(θ)J (θ) Target objective, typically J⋆(θ)=Jr⋆(θ)J (θ)=J_r (θ). Jϕ(θ)J^φ(θ) Learned-reward objective, typically Jϕ(θ)=Jr^ϕ(θ)J^φ(θ)=J_ r_φ(θ). Jϕ,τ(θ)J^φ,τ(θ) Learned-reward clipped objective, typically Jϕ,τ(θ)=Jr^ϕ,τ(θ)J^φ,τ(θ)=J_ r_φ,τ(θ). Symbol Meaning J^n,Kr,τ(θ) J^r,τ_n,K(θ) Empirical objective using n prompts and K rollouts per prompt (reward r, clipping τ). J^n,∞r,τ(θ) J^r,τ_n,∞(θ) Conditional (infinite-rollout) analogue: expectation over rollouts given the n sampled prompts. n Number of sampled prompts. K Number of rollouts per prompt. P Prior distribution over Θ (PAC-Bayes). Q Posterior distribution over Θ (PAC-Bayes). KL(Q∥P)KL(Q\|P) PAC-Bayes complexity term. δ∈(0,1)δ∈(0,1) Confidence parameter for high-probability bounds. Appendix B Definitions and Lemmas Definition 2 (KLKL divergence [kullback1951]). Suppose that P is absolutely continuous with respect to Q. The KLKL divergence is defined by KL(P∥Q):=∫p(x)log⁡(p(x)q(x))x.KL(P\|Q):= p(x) \! ( p(x)q(x) )dx. Lemma 8 (Hoeffding’s inequality [hoeffding1963probability]). Let Z1,…,ZNZ_1,…,Z_N be independent random variables. Assume there exist constants a≤ba≤ b such that a≤Zi≤ba≤ Z_i≤ b almost surely for every i. Then, for any δ∈(0,1)δ∈(0,1), with probability at least 1−δ1-δ, |1N∑i=1NZi−[1N∑i=1NZi]|≤(b−a)log⁡(2/δ)2N. 1N _i=1^NZ_i-E\! [ 1N _i=1^NZ_i ] ≤(b-a) (2/δ)2N. Lemma 9 (Hoeffding’s lemma [boucheron2013concentration]). Let Z be a random variable and assume a≤Z≤ba≤ Z≤ b almost surely. Then, for any λ∈ℝλ , [exp⁡(λ(Z−[Z]))]≤exp⁡(λ2(b−a)28).E\! [ (λ(Z-E[Z]) ) ]≤ \! ( λ^2(b-a)^28 ). Lemma 10 (Change of measure [catoni2007pac]). Let P and Q be distributions on Θ such that KL(Q∥P)<∞KL(Q\|P)<∞. Let F:Θ→ℝF: satisfy θ∼P[exp⁡(F(θ))]<∞E_θ P[ (F(θ))]<∞. Then, θ∼Q[F(θ)]≤KL(Q∥P)+log⁡θ∼P[exp⁡(F(θ))].E_θ Q[F(θ)] (Q\|P)+ _θ P\! [ (F(θ)) ]. Proof. Let p and q denote densities of P and Q with respect to a common reference. By definition, KL(Q∥P)=Q[log⁡(q/p)]KL(Q\|P)=E_Q[ (q/p)]. Start from the identity Q[F]=Q[log⁡(eF)].E_Q[F]=E_Q[ (e^F)]. Insert the density ratio p/qp/q inside the logarithm: Q[F]=Q[log⁡(eFpq)]+Q[log⁡(qp)].E_Q[F]=E_Q\! [ \! (e^F pq ) ]+E_Q\! [ \! ( qp ) ]. The second term is exactly KL(Q∥P)KL(Q\|P). For the first term, Jensen’s inequality gives Q[log⁡(eFpq)]≤log⁡Q[eFpq]=log⁡P[eF].E_Q\! [ \! (e^F pq ) ]≤ _Q\! [e^F pq ]= _P[e^F]. Substituting these two relations into the previous display yields Q[F]≤KL(Q∥P)+log⁡P[eF],E_Q[F] (Q\|P)+ _P[e^F], which is the claimed inequality. ∎ Definition 3 (χ2χ^2 divergence [tsybakov2009]). Suppose that DθD_θ is absolutely continuous with respect to DtrainD_train. The χ2χ^2 divergence is defined by χ2(Dθ∥Dtrain):=(X,Y)∼Dtrain[(Dθ(X,Y)Dtrain(X,Y)−1)2].χ^2(D_θ\|D_train):=E_(X,Y) D_train\! [ ( D_θ(X,Y)D_train(X,Y)-1 )^2 ]. Lemma 11 (χ2χ^2 change of measure). Let P and Q be distributions on a common space and assume Q≪PQ P. Let w=dQdPw= dQdP and assume χ2(Q∥P)<∞χ^2(Q\|P)<∞. If f satisfies Z∼P[f(Z)2]<∞E_Z P[f(Z)^2]<∞, we have |Z∼Q[f(Z)]|≤1+χ2(Q∥P)Z∼P[f(Z)2]. _Z Q[f(Z)] ≤ 1+χ^2(Q\|P)\, E_Z P[f(Z)^2]. Proof. Because Q≪PQ P, the density ratio w=dQdPw= dQdP exists and the expectation under Q can be written as Z∼Q[f(Z)]=Z∼P[w(Z)f(Z)].E_Z Q[f(Z)]=E_Z P[w(Z)f(Z)]. Applying Cauchy–Schwarz to the right-hand side gives |P[wf]|≤P[w2]P[f2]. _P[wf] ≤ E_P[w^2]\, E_P[f^2]. It remains to express P[w2]E_P[w^2] in terms of χ2(Q∥P)χ^2(Q\|P). By definition, χ2(Q∥P)=P[(w−1)2]=P[w2]−2P[w]+1.χ^2(Q\|P)=E_P[(w-1)^2]=E_P[w^2]-2E_P[w]+1. Also P[w]=1E_P[w]=1, since w=dQ/dPw=dQ/dP integrates to 11 under P. Substituting P[w]=1E_P[w]=1 into the previous identity yields P[w2]=1+χ2(Q∥P)E_P[w^2]=1+χ^2(Q\|P). Plugging this into the Cauchy–Schwarz bound gives |Z∼Q[f(Z)]|≤1+χ2(Q∥P)Z∼P[f(Z)2], _Z Q[f(Z)] ≤ 1+χ^2(Q\|P)\, E_Z P[f(Z)^2], which completes the proof. ∎ Lemma 12 (Monte Carlo estimation of the clipped log ratio). Under the same conditions of Lemma 2, with probability at least 1−δ1-δ over the evaluation prompts and rollouts, |κ^n,Kτ(θ)−κτ(θ)|≤2τ(log⁡(4/δ)2n+log⁡(4/δ)2nK). | κ_n,K^τ(θ)-κ^τ(θ) |≤ 2τ ( (4/δ)2n+ (4/δ)2nK ). (9) Lemma 13 (KL divergence between Gaussian distributions [murphy2022pml1]). Let Q=(μQ,ΣQ)Q=N( _Q, _Q) and P=(μP,ΣP)P=N( _P, _P) be Gaussian distributions on ℝdR^d, where ΣQ≻0 _Q 0 and ΣP≻0 _P 0. Then, KL(Q∥P)=12(tr⁡(ΣP−1ΣQ)+(μQ−μP)⊤ΣP−1(μQ−μP)−d+log⁡det(ΣP)det(ΣQ)). (Q\|P)= 12 (tr( _P^-1 _Q)+( _Q- _P) _P^-1( _Q- _P)-d+ ( _P) ( _Q) ). (10) Appendix C Proofs C.1 Error decomposition Proof of Lemma 1. Let θ∈Θθ∈ and ϕ∈Φφ∈ be arbitrary, and let τ>0τ>0 be an arbitrary clipping threshold. The argument is a purely algebraic decomposition in which two intermediate population objectives are inserted between the empirical surrogate objective and the target objective. Consider the difference J^n,Kϕ,τ(θ)−J⋆(θ) J_n,K^φ,τ(θ)-J (θ). Add and subtract the intermediate quantities Jϕ,τ(θ)J^φ,τ(θ) and Jϕ(θ)J^φ(θ) to obtain J^n,Kϕ,τ(θ)−J⋆(θ)= J_n,K^φ,τ(θ)-J (θ)= J^n,Kϕ,τ(θ)−Jϕ,τ(θ)+Jϕ,τ(θ)−Jϕ(θ)+Jϕ(θ)−J⋆(θ). J_n,K^φ,τ(θ)-J^φ,τ(θ)+J^φ,τ(θ)-J^φ(θ)+J^φ(θ)-J (θ). Taking absolute values and applying the triangle inequality gives |J^n,Kϕ,τ(θ)−J⋆(θ)|≤ J_n,K^φ,τ(θ)-J (θ) ≤ |J^n,Kϕ,τ(θ)−Jϕ,τ(θ)|+|Jϕ,τ(θ)−Jϕ(θ)|+|Jϕ(θ)−J⋆(θ)|. J_n,K^φ,τ(θ)-J^φ,τ(θ) + J^φ,τ(θ)-J^φ(θ) + J^φ(θ)-J (θ) . This is exactly the inequality stated in Lemma 1. ∎ C.2 Statistical error Proof of Lemma 2. Let θ∈Θθ∈ be an arbitrary policy parameter. Let r:×→[0,1]r:X×Y→[0,1] be an arbitrary reward function, let τ>0τ>0 be an arbitrary clipping threshold, and let δ∈(0,1)δ∈(0,1) be an arbitrary confidence level. The goal is to control the Monte Carlo deviation arising from drawing only K rollouts per prompt, while conditioning on the realized prompts. Let x1,…,xnx_1,…,x_n denote the realized prompts. For each i∈1,…,ni∈\1,…,n\ and each rollout index j∈1,…,Kj∈\1,…,K\, define the per-rollout contribution Zi,j:=r(xi,yi,j)−βℓθτ(xi,yi,j).Z_i,j:=r(x_i,y_i,j)-β\, _θ^τ(x_i,y_i,j). By the definition of the empirical objective, one can rewrite J^n,Kr,τ(θ)=1nK∑i=1n∑j=1KZi,j. J_n,K^r,τ(θ)= 1nK _i=1^n _j=1^KZ_i,j. Next define the conditional expectation of the empirical objective given the prompts. For each fixed prompt xix_i, conditional on xix_i the rollout yi,jy_i,j is distributed as πθ(⋅∣xi) _θ(· x_i), hence [Zi,j∣xi]=Y∼πθ(⋅∣xi)[r(xi,Y)]−βY∼πθ(⋅∣xi)[ℓθτ(xi,Y)].E[Z_i,j x_i]=E_Y _θ(· x_i)[r(x_i,Y)]-β\,E_Y _θ(· x_i)[ _θ^τ(x_i,Y)]. Averaging these conditional expectations over i yields the infinite-rollout analogue J^n,∞r,τ(θ):=1n∑i=1n[Zi,1∣xi]. J_n,∞^r,τ(θ):= 1n _i=1^nE[Z_i,1 x_i]. By construction, [J^n,Kr,τ(θ)∣x1:n]=J^n,∞r,τ(θ).E\! [ J_n,K^r,τ(θ) x_1:n ]= J_n,∞^r,τ(θ). To apply Hoeffding’s inequality, it remains to verify a uniform bound on each Zi,jZ_i,j. Because r(xi,yi,j)∈[0,1]r(x_i,y_i,j)∈[0,1] and ℓθτ(xi,yi,j)∈[−τ,τ] _θ^τ(x_i,y_i,j)∈[-τ,τ], it follows that −βτ≤Zi,j≤1+βτ,-βτ≤ Z_i,j≤ 1+βτ, so the interval width is 1+2βτ1+2βτ. Conditional on the prompts x1:nx_1:n, the rollouts are independent across all index pairs (i,j)(i,j). Therefore the collection Zi,ji≤n,j≤K\Z_i,j\_i≤ n,\,j≤ K is independent conditional on x1:nx_1:n. Applying Lemma 8 to the average of these nKnK bounded independent random variables, with failure probability δ, gives that with probability at least 1−δ1-δ over the rollouts conditional on x1:nx_1:n, |J^n,Kr,τ(θ)−[J^n,Kr,τ(θ)∣x1:n]|≤(1+2βτ)log⁡(2/δ)2nK. J_n,K^r,τ(θ)-E\! [ J_n,K^r,τ(θ) x_1:n ] ≤(1+2βτ) (2/δ)2nK. Replacing the conditional expectation by J^n,∞r,τ(θ) J_n,∞^r,τ(θ) yields |J^n,Kr,τ(θ)−J^n,∞r,τ(θ)|≤(1+2βτ)log⁡(2/δ)2nK, J_n,K^r,τ(θ)- J_n,∞^r,τ(θ) ≤(1+2βτ) (2/δ)2nK, which is the conclusion of Lemma 2. ∎ Proof of Lemma 3. Let θ∈Θθ∈ be an arbitrary policy parameter. Let r:×→[0,1]r:X×Y→[0,1] be an arbitrary reward function, let τ>0τ>0 be an arbitrary clipping threshold, and let δ∈(0,1)δ∈(0,1) be an arbitrary confidence level. This lemma controls the deviation due only to sampling finitely many prompts, after taking the conditional expectation over rollouts. Define, for each prompt x∈x , gθr,τ(x)=Y∼πθ(⋅∣x)[r(x,Y)]−βY∼πθ(⋅∣x)[ℓθτ(x,Y)].g_θ^r,τ(x)=E_Y _θ(· x)[r(x,Y)]-β\,E_Y _θ(· x)[ _θ^τ(x,Y)]. Because r(⋅,⋅)∈[0,1]r(·,·)∈[0,1] and ℓθτ(⋅,⋅)∈[−τ,τ] _θ^τ(·,·)∈[-τ,τ] pointwise, the first expectation lies in [0,1][0,1] and the second expectation lies in [−τ,τ][-τ,τ]. Consequently, for every x, −βτ≤gθr,τ(x)≤1+βτ,-βτ≤ g_θ^r,τ(x)≤ 1+βτ, so the interval width is again 1+2βτ1+2βτ. By definition, J^n,∞r,τ(θ)=1n∑i=1ngθr,τ(xi),Jr,τ(θ)=X∼ρ[gθr,τ(X)]. J_n,∞^r,τ(θ)= 1n _i=1^ng_θ^r,τ(x_i), J^r,τ(θ)=E_X ρ[g_θ^r,τ(X)]. Since x1,…,xnx_1,…,x_n are independent draws from ρ, the sequence gθr,τ(x1),…,gθr,τ(xn)g_θ^r,τ(x_1),…,g_θ^r,τ(x_n) consists of i.i.d. random variables bounded in an interval of width 1+2βτ1+2βτ. Applying Lemma 8 with N=nN=n and failure probability δ yields that with probability at least 1−δ1-δ over the prompts, |J^n,∞r,τ(θ)−Jr,τ(θ)|≤(1+2βτ)log⁡(2/δ)2n. J_n,∞^r,τ(θ)-J^r,τ(θ) ≤(1+2βτ) (2/δ)2n. This is precisely the statement of Lemma 3. ∎ Proof of Lemma 4. Let θ∈Θθ∈ be an arbitrary policy parameter. Let r:×→[0,1]r:X×Y→[0,1] be an arbitrary reward function, let τ>0τ>0 be an arbitrary clipping threshold, and let δ∈(0,1)δ∈(0,1) be an arbitrary confidence level. The proof combines the two previous concentration statements by enforcing that they hold on a common high-probability event, and then applying a triangle inequality. Define the rollout concentration event ℰroll:=|J^n,Kr,τ(θ)−J^n,∞r,τ(θ)|≤(1+2βτ)log⁡(4/δ)2nK.E_roll:= \ J_n,K^r,τ(θ)- J_n,∞^r,τ(θ) ≤(1+2βτ) (4/δ)2nK \. Lemma 2 applied with confidence parameter δ/2δ/2 implies that, conditional on x1:nx_1:n, Pr⁡(ℰroll∣x1:n)≥1−δ/2. (E_roll x_1:n)≥ 1-δ/2. Define the prompt concentration event ℰprompt:=|J^n,∞r,τ(θ)−Jr,τ(θ)|≤(1+2βτ)log⁡(4/δ)2n.E_prompt:= \ J_n,∞^r,τ(θ)-J^r,τ(θ) ≤(1+2βτ) (4/δ)2n \. Lemma 3 applied with confidence parameter δ/2δ/2 yields Pr⁡(ℰprompt)≥1−δ/2. (E_prompt)≥ 1-δ/2. Let ℰstat:=ℰroll∩ℰpromptE_stat:=E_roll _prompt. By the union bound, Pr⁡(ℰstat)≥1−δ. (E_stat)≥ 1-δ. Assume that ℰstatE_stat holds. Then, the triangle inequality gives |J^n,Kr,τ(θ)−Jr,τ(θ)|≤ J_n,K^r,τ(θ)-J^r,τ(θ) ≤ |J^n,Kr,τ(θ)−J^n,∞r,τ(θ)|+|J^n,∞r,τ(θ)−Jr,τ(θ)| J_n,K^r,τ(θ)- J_n,∞^r,τ(θ) + J_n,∞^r,τ(θ)-J^r,τ(θ) ≤ ≤ (1+2βτ)(log⁡(4/δ)2n+log⁡(4/δ)2nK), (1+2βτ) ( (4/δ)2n+ (4/δ)2nK ), which is exactly the inequality claimed in Lemma 4. ∎ Proof of Lemma 12. Let θ∈Θθ∈ be an arbitrary policy parameter, let τ>0τ>0 be an arbitrary clipping threshold, and let δ∈(0,1)δ∈(0,1) be an arbitrary confidence level. Recall that x1,…,xnx_1,…,x_n are independent draws from ρ, and that, conditional on each xix_i, the rollouts yi,1,…,yi,Ky_i,1,…,y_i,K are independent draws from πθ(⋅∣xi) _θ(· x_i). Define the per-rollout clipped log ratio Zi,j:=ℓθτ(xi,yi,j),Z_i,j:= _θ^τ(x_i,y_i,j), so that, by the definition of κ^n,Kτ(θ) κ_n,K^τ(θ), κ^n,Kτ(θ)=1nK∑i=1n∑j=1KZi,j. κ_n,K^τ(θ)= 1nK _i=1^n _j=1^KZ_i,j. Because ℓθτ(x,y)=clip⁡(ℓθ(x,y),−τ,τ) _θ^τ(x,y)=clip( _θ(x,y),-τ,τ) by definition, it follows that Zi,j∈[−τ,τ]Z_i,j∈[-τ,τ] almost surely for all (i,j)(i,j), and therefore each Zi,jZ_i,j is bounded in an interval of width 2τ2τ. To make the two-stage sampling structure explicit, introduce the conditional infinite-rollout analogue κ^n,∞τ(θ):=1n∑i=1n[Zi,1∣xi]=1n∑i=1nY∼πθ(⋅∣xi)[ℓθτ(xi,Y)]. κ_n,∞^τ(θ):= 1n _i=1^nE\! [Z_i,1 x_i ]= 1n _i=1^nE_Y _θ(· x_i)\! [ _θ^τ(x_i,Y) ]. By construction, conditional on the realized prompts x1:nx_1:n, the random variables Zi,ji≤n,j≤K\Z_i,j\_i≤ n,\,j≤ K are independent, and moreover [κ^n,Kτ(θ)∣x1:n]=κ^n,∞τ(θ).E\! [ κ_n,K^τ(θ) x_1:n ]= κ_n,∞^τ(θ). Applying Lemma 8 to the average of the nKnK bounded independent random variables Zi,j\Z_i,j\, conditional on x1:nx_1:n and with failure probability δ/2δ/2, yields that with probability at least 1−δ/21-δ/2 over the rollouts conditional on x1:nx_1:n, |κ^n,Kτ(θ)−κ^n,∞τ(θ)|≤2τlog⁡(4/δ)2nK. | κ_n,K^τ(θ)- κ_n,∞^τ(θ) |≤ 2τ (4/δ)2nK. It remains to control the deviation due to sampling only finitely many prompts. Define the prompt-level functional hθτ(x):=Y∼πθ(⋅∣x)[ℓθτ(x,Y)].h_θ^τ(x):=E_Y _θ(· x)\! [ _θ^τ(x,Y) ]. Since ℓθτ(x,Y)∈[−τ,τ] _θ^τ(x,Y)∈[-τ,τ] almost surely under Y∼πθ(⋅∣x)Y _θ(· x), it follows that hθτ(x)∈[−τ,τ]h_θ^τ(x)∈[-τ,τ] for every x, and thus hθτ(X)h_θ^τ(X) is bounded in an interval of width 2τ2τ when X∼ρX ρ. By the definition of κ^n,∞τ(θ) κ_n,∞^τ(θ), κ^n,∞τ(θ)=1n∑i=1nhθτ(xi). κ_n,∞^τ(θ)= 1n _i=1^nh_θ^τ(x_i). Moreover, by the definition of Dθ(x,y)=ρ(x)πθ(y∣x)D_θ(x,y)=ρ(x) _θ(y x), the clipped population average can be written as κτ(θ)=(X,Y)∼Dθ[ℓθτ(X,Y)]=X∼ρ[hθτ(X)].κ^τ(θ)=E_(X,Y) D_θ\! [ _θ^τ(X,Y) ]=E_X ρ\! [h_θ^τ(X) ]. Since x1,…,xnx_1,…,x_n are independent draws from ρ, the sequence hθτ(x1),…,hθτ(xn)h_θ^τ(x_1),…,h_θ^τ(x_n) consists of i.i.d. random variables bounded in an interval of width 2τ2τ. Applying Lemma 8 with N=nN=n and failure probability δ/2δ/2 yields that with probability at least 1−δ/21-δ/2 over the prompts, |κ^n,∞τ(θ)−κτ(θ)|≤2τlog⁡(4/δ)2n. | κ_n,∞^τ(θ)-κ^τ(θ) |≤ 2τ (4/δ)2n. Finally, consider the event on which both of the preceding inequalities hold. By the union bound, this event has probability at least 1−δ1-δ over the joint draw of prompts and rollouts. On this event, the triangle inequality implies |κ^n,Kτ(θ)−κτ(θ)| | κ_n,K^τ(θ)-κ^τ(θ) | ≤|κ^n,Kτ(θ)−κ^n,∞τ(θ)|+|κ^n,∞τ(θ)−κτ(θ)| ≤ | κ_n,K^τ(θ)- κ_n,∞^τ(θ) |+ | κ_n,∞^τ(θ)-κ^τ(θ) | ≤2τ(log⁡(4/δ)2n+log⁡(4/δ)2nK), ≤ 2τ ( (4/δ)2n+ (4/δ)2nK ), which is exactly the claimed bound in (9). ∎ C.3 Reward shift and surrogate bias Proof of Lemma 5. Let θ∈Θθ∈ and ϕ∈Φφ∈ be arbitrary parameters. The proof begins by expressing the objective gap as an expectation of reward-model error under the deployment distribution, and then transferring this expectation back to the reward-model training distribution via a density ratio. By definition, Jϕ(θ)=X∼ρY∼πθ(⋅∣X)[r^ϕ(X,Y)]−βX∼ρKL(πθ(⋅∣X)∥πref(⋅∣X)),J^φ(θ)=E_X ρE_Y _θ(· X)[ r_φ(X,Y)]-β\,E_X ρKL( _θ(· X)\| _ref(· X)), and J⋆(θ)=X∼ρY∼πθ(⋅∣X)[r⋆(X,Y)]−βX∼ρKL(πθ(⋅∣X)∥πref(⋅∣X)).J (θ)=E_X ρE_Y _θ(· X)[r (X,Y)]-β\,E_X ρKL( _θ(· X)\| _ref(· X)). The KL regularization terms coincide, so they cancel after subtraction, giving Jϕ(θ)−J⋆(θ)=X∼ρY∼πθ(⋅∣X)[r^ϕ(X,Y)−r⋆(X,Y)].J^φ(θ)-J (θ)=E_X ρE_Y _θ(· X)[ r_φ(X,Y)-r (X,Y)]. Introduce the pointwise reward-model error eϕ(x,y)=r^ϕ(x,y)−r⋆(x,y)e_φ(x,y)= r_φ(x,y)-r (x,y). Using the joint distribution Dθ(x,y)=ρ(x)πθ(y∣x)D_θ(x,y)=ρ(x) _θ(y x), the preceding display can be rewritten as Jϕ(θ)−J⋆(θ)=(X,Y)∼Dθ[eϕ(X,Y)].J^φ(θ)-J (θ)=E_(X,Y) D_θ[e_φ(X,Y)]. Assume that Dθ≪DtrainD_θ D_train and define the density ratio wθ(x,y):=Dθ(x,y)Dtrain(x,y).w_θ(x,y):= D_θ(x,y)D_train(x,y). Then, the expectation under DθD_θ can be written under DtrainD_train as (X,Y)∼Dθ[eϕ(X,Y)]=(X,Y)∼Dtrain[wθ(X,Y)eϕ(X,Y)].E_(X,Y) D_θ[e_φ(X,Y)]=E_(X,Y) D_train[w_θ(X,Y)e_φ(X,Y)]. Applying Cauchy–Schwarz yields |Dtrain[wθeϕ]|≤Dtrain[wθ2]Dtrain[eϕ2]. _D_train[w_θe_φ] ≤ E_D_train[w_θ^2]\, E_D_train[e_φ^2]. The second factor is exactly Ltrain(2)(ϕ) L_train^(2)(φ) by the definition of Ltrain(2)(ϕ)L_train^(2)(φ). For the first factor, note that Dtrain[wθ]=1E_D_train[w_θ]=1 and χ2(Dθ∥Dtrain)=Dtrain[(wθ−1)2]=Dtrain[wθ2]−1.χ^2(D_θ\|D_train)=E_D_train [(w_θ-1)^2 ]=E_D_train[w_θ^2]-1. Consequently, Dtrain[wθ2]=1+χ2(Dθ∥Dtrain)E_D_train[w_θ^2]=1+χ^2(D_θ\|D_train). Substituting these identities into the Cauchy–Schwarz bound gives |Jϕ(θ)−J⋆(θ)|≤1+χ2(Dθ∥Dtrain)Ltrain(2)(ϕ). J^φ(θ)-J (θ) ≤ 1+χ^2(D_θ\|D_train)\, L_train^(2)(φ). By the definition of (θ)C(θ) in eq. (5), this is |Jϕ(θ)−J⋆(θ)|≤(θ)Ltrain(2)(ϕ), J^φ(θ)-J (θ) (θ)\, L_train^(2)(φ), which is the statement of Lemma 5. ∎ Proof of Lemma 6. Let θ∈Θθ∈ be arbitrary. Assume that ρ≪ρlabelρ _label and that πθ(⋅∣x)≪πref(⋅∣x) _θ(· x) _ref(· x) for every x with ρlabel(x)>0 _label(x)>0. Under these conditions, Dθ≪DtrainD_θ D_train holds and the density ratio wθ(x,y):=Dθ(x,y)Dtrain(x,y)w_θ(x,y):= D_θ(x,y)D_train(x,y) is well defined on the support of DtrainD_train. By definition, (θ)2=1+χ2(Dθ∥Dtrain)=(X,Y)∼Dtrain[wθ(X,Y)2].C(θ)^2=1+χ^2(D_θ\|D_train)=E_(X,Y) D_train [w_θ(X,Y)^2 ]. Using Dtrain(x,y)=ρlabel(x)πref(y∣x)D_train(x,y)= _label(x) _ref(y x) and Dθ(x,y)=ρ(x)πθ(y∣x)D_θ(x,y)=ρ(x) _θ(y x), one obtains the factorization wθ(x,y)=ρ(x)ρlabel(x)⋅πθ(y∣x)πref(y∣x).w_θ(x,y)= ρ(x) _label(x)· _θ(y x) _ref(y x). Substituting this expression into the definition of (θ)2C(θ)^2 and taking expectation under DtrainD_train yields (θ)2=X∼ρlabel[(ρ(X)ρlabel(X))2Y∼πref(⋅∣X)[(πθ(Y∣X)πref(Y∣X))2]].C(θ)^2=E_X _label [ ( ρ(X) _label(X) )^2E_Y _ref(· X) [ ( _θ(Y X) _ref(Y X) )^2 ] ]. By the definition of pol(θ)C_pol(θ), the inner expectation is bounded above by pol(θ)2C_pol(θ)^2 for each x in the support of ρlabel _label. Therefore, (θ)2≤pol(θ)2X∼ρlabel[(ρ(X)ρlabel(X))2]=pol(θ)2prompt2.C(θ)^2 _pol(θ)^2E_X _label [ ( ρ(X) _label(X) )^2 ]=C_pol(θ)^2\,C_prompt^2. Taking square roots yields (θ)≤promptpol(θ)C(θ) _prompt\,C_pol(θ). ∎ Proof of Lemma 7. Let θ∈Θθ∈ and ϕ∈Φφ∈ be arbitrary parameters, and let τ>0τ>0 be an arbitrary clipping threshold. The argument is an identity at the level of population objectives, followed by a standard absolute-value bound. By definition of the clipped objective, Jϕ,τ(θ)=X∼ρY∼πθ(⋅∣X)[r^ϕ(X,Y)]−βX∼ρY∼πθ(⋅∣X)[ℓθτ(X,Y)].J^φ,τ(θ)=E_X ρE_Y _θ(· X)[ r_φ(X,Y)]-β\,E_X ρE_Y _θ(· X)[ _θ^τ(X,Y)]. Using Dθ(x,y)=ρ(x)πθ(y∣x)D_θ(x,y)=ρ(x) _θ(y x), this can be written as Jϕ,τ(θ)=(X,Y)∼Dθ[r^ϕ(X,Y)]−β(X,Y)∼Dθ[ℓθτ(X,Y)].J^φ,τ(θ)=E_(X,Y) D_θ[ r_φ(X,Y)]-β\,E_(X,Y) D_θ[ _θ^τ(X,Y)]. For the exact objective, recall that KL(πθ(⋅∣x)∥πref(⋅∣x))=Y∼πθ(⋅∣x)[ℓθ(x,Y)].KL( _θ(· x)\| _ref(· x))=E_Y _θ(· x)[ _θ(x,Y)]. Substituting this identity into the definition of Jϕ(θ)J^φ(θ) yields Jϕ(θ)=(X,Y)∼Dθ[r^ϕ(X,Y)]−β(X,Y)∼Dθ[ℓθ(X,Y)].J^φ(θ)=E_(X,Y) D_θ[ r_φ(X,Y)]-β\,E_(X,Y) D_θ[ _θ(X,Y)]. Subtracting the two displays gives the exact identity Jϕ,τ(θ)−Jϕ(θ)=β(X,Y)∼Dθ[ℓθ(X,Y)−ℓθτ(X,Y)].J^φ,τ(θ)-J^φ(θ)=β\,E_(X,Y) D_θ [ _θ(X,Y)- _θ^τ(X,Y) ]. Taking absolute values and using |[U]|≤[|U|] [U] [ U ] yields |Jϕ,τ(θ)−Jϕ(θ)|≤β(X,Y)∼Dθ[|ℓθ(X,Y)−ℓθτ(X,Y)|], J^φ,τ(θ)-J^φ(θ) ≤β\,E_(X,Y) D_θ [ _θ(X,Y)- _θ^τ(X,Y) ], which is precisely the inequality asserted in Lemma 7. ∎ C.4 Unified fixed-policy bound Proof of Theorem 1. Let θ∈Θθ∈ and ϕ∈Φφ∈ be arbitrary, and let τ>0τ>0 and δ∈(0,1)δ∈(0,1) be arbitrary. Assume the conditions stated in Theorem 1, so that Lemmas 4, 5, and 7 are applicable. Lemma 1 provides the deterministic decomposition |J^n,Kϕ,τ(θ)−J⋆(θ)|≤ J_n,K^φ,τ(θ)-J (θ) ≤ |J^n,Kϕ,τ(θ)−Jϕ,τ(θ)|+|Jϕ,τ(θ)−Jϕ(θ)|+|Jϕ(θ)−J⋆(θ)|. J_n,K^φ,τ(θ)-J^φ,τ(θ) + J^φ,τ(θ)-J^φ(θ) + J^φ(θ)-J (θ) . To control the first term, apply Lemma 4 with r=r^ϕr= r_φ. With probability at least 1−δ1-δ over the evaluation prompts and rollouts, |J^n,Kϕ,τ(θ)−Jϕ,τ(θ)|≤(1+2βτ)(log⁡(4/δ)2n+log⁡(4/δ)2nK). J_n,K^φ,τ(θ)-J^φ,τ(θ) ≤(1+2βτ) ( (4/δ)2n+ (4/δ)2nK ). The remaining two terms are controlled deterministically. Lemma 7 gives |Jϕ,τ(θ)−Jϕ(θ)|≤β(X,Y)∼Dθ[|ℓθ(X,Y)−ℓθτ(X,Y)|], J^φ,τ(θ)-J^φ(θ) ≤β\,E_(X,Y) D_θ\! [ _θ(X,Y)- _θ^τ(X,Y) ], and Lemma 5 gives |Jϕ(θ)−J⋆(θ)|≤(θ)Ltrain(2)(ϕ). J^φ(θ)-J (θ) (θ)\, L_train^(2)(φ). Substituting these three bounds into the decomposition yields the inequality stated in Theorem 1. ∎ Proof of Corollary 3. Let θ∈Θθ∈ be an arbitrary policy parameter, let ϕ∈Φφ∈ be an arbitrary reward-model parameter, let β>0β>0 be an arbitrary regularization coefficient, let δ∈(0,1)δ∈(0,1) be an arbitrary confidence level, and let n≥1n≥ 1 and K≥1K≥ 1 be arbitrary integers. Define αn,K,δ:=log⁡(4/δ)2n+log⁡(4/δ)2nK,Bθ(τ):=(1+2βτ)αn,K,δ+βTθ(τ), _n,K,δ:= (4/δ)2n+ (4/δ)2nK, B_θ(τ):=(1+2βτ) _n,K,δ+β T_θ(τ), where Tθ(τ):=(X,Y)∼Dθ[(|ℓθ(X,Y)|−τ)+].T_θ(τ):=E_(X,Y) D_θ [(| _θ(X,Y)|-τ)_+ ]. Let (X,Y)∼Dθ(X,Y) D_θ and define the nonnegative random variable Z:=|ℓθ(X,Y)|Z:=| _θ(X,Y)|. With this notation one has Tθ(τ)=[(Z−τ)+]T_θ(τ)=E[(Z-τ)_+], so the function of interest can be written as Bθ(τ)=(1+2βτ)αn,K,δ+β[(Z−τ)+].B_θ(τ)=(1+2βτ) _n,K,δ+β\,E[(Z-τ)_+]. The next step is to relate the one-sided derivatives of τ↦[(Z−τ)+]τ [(Z-τ)_+] to the tail probabilities of Z. For every z≥0z≥ 0 and every τ≥0τ≥ 0, the identity (z−τ)+=∫τ∞z>tt(z-τ)_+\;=\; _τ^∞1\z>t\\,dt holds, because the integrand equals 11 precisely on the interval t∈[τ,z)t∈[τ,z) when z>τz>τ, and otherwise it is identically zero. Applying this identity with z=Zz=Z and using Tonelli’s theorem, which is applicable because the integrand is nonnegative, yields the representation [(Z−τ)+]=∫τ∞Pr⁡(Z>t)t.E[(Z-τ)_+]= _τ^∞ (Z>t)\,dt. Let τ≥0τ≥ 0 and let h>0h>0. Using the integral representation at τ and at τ+hτ+h gives [(Z−(τ+h))+]−[(Z−τ)+]=−∫τ+hPr⁡(Z>t)t.E[(Z-(τ+h))_+]-E[(Z-τ)_+]=- _τ^τ+h (Z>t)\,dt. Since the function t↦Pr⁡(Z>t)t (Z>t) is nonincreasing, one has hPr⁡(Z>τ+h)≤∫τ+hPr⁡(Z>t)t≤hPr⁡(Z>τ).h\, (Z>τ+h)\;≤\; _τ^τ+h (Z>t)\,dt\;≤\;h\, (Z>τ). Dividing by h and combining with the previous display yields −Pr⁡(Z>τ)≤[(Z−(τ+h))+]−[(Z−τ)+]h≤−Pr⁡(Z>τ+h).- (Z>τ)\;≤\; E[(Z-(τ+h))_+]-E[(Z-τ)_+]h\;≤\;- (Z>τ+h). Letting h↓0h 0 and using the monotone convergence Pr⁡(Z>τ+h)→Pr⁡(Z>τ) (Z>τ+h)→ (Z>τ) yields the right derivative identity dτ+[(Z−τ)+]=−Pr⁡(Z>τ). ddτ^+E[(Z-τ)_+]\;=\;- (Z>τ). Let τ>0τ>0 and let h∈(0,τ)h∈(0,τ). Using the integral representation at τ and at τ−hτ-h gives [(Z−τ)+]−[(Z−(τ−h))+]=−∫τ−hτPr⁡(Z>t)t.E[(Z-τ)_+]-E[(Z-(τ-h))_+]=- _τ-h^τ (Z>t)\,dt. Since t↦Pr⁡(Z>t)t (Z>t) is nonincreasing, one has hPr⁡(Z>τ)≤∫τ−hτPr⁡(Z>t)t≤hPr⁡(Z>τ−h).h\, (Z>τ)\;≤\; _τ-h^τ (Z>t)\,dt\;≤\;h\, (Z>τ-h). Dividing by h and combining with the previous display yields −Pr⁡(Z>τ−h)≤[(Z−τ)+]−[(Z−(τ−h))+]h≤−Pr⁡(Z>τ).- (Z>τ-h)\;≤\; E[(Z-τ)_+]-E[(Z-(τ-h))_+]h\;≤\;- (Z>τ). Letting h↓0h 0 and using the monotone convergence Pr⁡(Z>τ−h)→Pr⁡(Z≥τ) (Z>τ-h)→ (Z≥τ) yields the left derivative identity dτ−[(Z−τ)+]=−Pr⁡(Z≥τ). ddτ^-E[(Z-τ)_+]\;=\;- (Z≥τ). It now follows that BθB_θ has one-sided derivatives for every τ≥0τ≥ 0, and these derivatives satisfy Bθ′(τ+)=2βαn,K,δ−βPr⁡(Z>τ),Bθ′(τ−)=2βαn,K,δ−βPr⁡(Z≥τ)for every τ>0.B_θ (τ^+)=2β _n,K,δ-β (Z>τ), B_θ (τ^-)=2β _n,K,δ-β (Z≥τ) every τ>0. Let τ⋆τ be any minimizer of τ↦Bθ(τ)τ B_θ(τ) over τ≥0τ≥ 0. If τ⋆>0τ >0, the minimality of τ⋆τ implies that the left derivative is nonpositive and the right derivative is nonnegative, so Bθ′((τ⋆)−)≤0≤Bθ′((τ⋆)+)B_θ ((τ )^-)≤ 0≤ B_θ ((τ )^+) holds. Substituting the one-sided derivative expressions yields Pr⁡(Z>τ⋆)≤ 2αn,K,δ≤Pr⁡(Z≥τ⋆). (Z>τ )\;≤\;2 _n,K,δ\;≤\; (Z≥τ ). If τ⋆=0τ =0, the minimality of τ⋆τ implies 0≤Bθ′(0+)0≤ B_θ (0^+), and therefore Pr⁡(Z>0)≤2αn,K,δ (Z>0)≤ 2 _n,K,δ holds. If 2αn,K,δ<12 _n,K,δ<1, the inequality 2αn,K,δ≤Pr⁡(Z≥0)=12 _n,K,δ≤ (Z≥ 0)=1 holds as well, and this yields the same two-sided condition with τ⋆=0τ =0. Finally, if 2αn,K,δ≥12 _n,K,δ≥ 1, for every τ>0τ>0, one has Bθ′(τ−)=2βαn,K,δ−βPr⁡(Z≥τ)≥2βαn,K,δ−β≥0,B_θ (τ^-)=2β _n,K,δ-β (Z≥τ)≥ 2β _n,K,δ-β≥ 0, and therefore BθB_θ is nondecreasing on (0,∞)(0,∞), which implies that τ⋆=0τ =0 is a minimizer over τ≥0τ≥ 0. Recalling that Z=|ℓθ(X,Y)|Z=| _θ(X,Y)| with (X,Y)∼Dθ(X,Y) D_θ, the stated conditions are exactly Pr(X,Y)∼Dθ⁡(|ℓθ(X,Y)|>τ⋆)≤ 2αn,K,δ≤Pr(X,Y)∼Dθ⁡(|ℓθ(X,Y)|≥τ⋆), _(X,Y) D_θ\! (| _θ(X,Y)|>τ )\;≤\;2 _n,K,δ\;≤\; _(X,Y) D_θ\! (| _θ(X,Y)|≥τ ), and when Pr⁡(Z=τ⋆)=0 (Z=τ )=0 the two inequalities collapse to the equality Pr⁡(Z>τ⋆)=2αn,K,δ (Z>τ )=2 _n,K,δ, which is equivalent to the quantile statement. ∎ C.5 PAC-Bayes auxiliary bounds Lemma 14 (PAC-Bayes bound for prompt sampling [mcallester1999modelavg, seeger2002pac]). Let P be a prior distribution on Θ , let τ>0τ>0 and δ∈(0,1)δ∈(0,1) be given, and let r:×→[0,1]r:X×Y→[0,1] be a given reward function. With probability at least 1−δ1-δ over x1,…,xn∼ρx_1,…,x_n ρ, the following inequality holds simultaneously for all posteriors Q on Θ : |Jr,τ(Q)−J^n,∞r,τ(Q)|≤(1+2βτ)KL(Q∥P)+log⁡(4/δ)2n. J^r,τ(Q)- J_n,∞^r,τ(Q) ≤(1+2βτ) KL(Q\|P)+ (4/δ)2n. Proof. Let λ>0λ>0 be arbitrary. For a given parameter value θ∈Θθ∈ , consider a single prompt draw X∼ρX ρ. As in the prompt-sampling argument in Lemma 3, the quantity gθr,τ(X)g_θ^r,τ(X) lies in the interval [−βτ, 1+βτ][-βτ,\,1+βτ]. Consequently, the centered random variable Jr,τ(θ)−gθr,τ(X)J^r,τ(θ)-g_θ^r,τ(X) is almost surely bounded in an interval of width 1+2βτ1+2βτ. Applying Lemma 9 yields X∼ρexp⁡(λ(Jr,τ(θ)−gθr,τ(X)))≤exp⁡(λ2(1+2βτ)28).E_X ρ \! (λ (J^r,τ(θ)-g_θ^r,τ(X) ) )≤ \! ( λ^2(1+2βτ)^28 ). Now let x1,…,xnx_1,…,x_n be i.i.d. draws from ρ. Using independence and the definition J^n,∞r,τ(θ)=1n∑i=1ngθr,τ(xi), J_n,∞^r,τ(θ)= 1n _i=1^ng_θ^r,τ(x_i), it follows that exp⁡(λ(Jr,τ(θ)−J^n,∞r,τ(θ)))≤exp⁡(λ2(1+2βτ)28n).E \! (λ (J^r,τ(θ)- J_n,∞^r,τ(θ) ) )≤ \! ( λ^2(1+2βτ)^28n ). Taking expectation with respect to θ∼Pθ P and applying Markov’s inequality yields that, with probability at least 1−δ/21-δ/2 over x1:nx_1:n, θ∼Pexp⁡(λ(Jr,τ(θ)−J^n,∞r,τ(θ)))≤2δexp⁡(λ2(1+2βτ)28n).E_θ P \! (λ (J^r,τ(θ)- J_n,∞^r,τ(θ) ) )≤ 2δ \! ( λ^2(1+2βτ)^28n ). On this event, Lemma 10 can be applied with F(θ)=λ(Jr,τ(θ)−J^n,∞r,τ(θ)).F(θ)=λ (J^r,τ(θ)- J_n,∞^r,τ(θ) ). For every posterior Q on Θ , this gives λ(Jr,τ(Q)−J^n,∞r,τ(Q))≤ λ (J^r,τ(Q)- J_n,∞^r,τ(Q) )≤ KL(Q∥P)+log⁡2δ+λ2(1+2βτ)28n. (Q\|P)+ 2δ+ λ^2(1+2βτ)^28n. Optimizing over λ>0λ>0 yields the one-sided bound Jr,τ(Q)−J^n,∞r,τ(Q)≤(1+2βτ)KL(Q∥P)+log⁡(2/δ)2n.J^r,τ(Q)- J_n,∞^r,τ(Q)≤(1+2βτ) KL(Q\|P)+ (2/δ)2n. Applying the same argument to the opposite deviation J^n,∞r,τ(Q)−Jr,τ(Q) J_n,∞^r,τ(Q)-J^r,τ(Q) and taking a union bound yields the stated two-sided inequality with log⁡(4/δ) (4/δ). ∎ Lemma 15 (PAC-Bayes bound for rollout sampling [catoni2007pac]). Let P be a prior distribution on Θ , let τ>0τ>0 and δ∈(0,1)δ∈(0,1) be given, and let r:×→[0,1]r:X×Y→[0,1] be a given reward function. With probability at least 1−δ1-δ over the rollouts conditional on x1:nx_1:n, the following inequality holds simultaneously for all posteriors Q on Θ : |J^n,∞r,τ(Q)−J^n,Kr,τ(Q)|≤(1+2βτ)KL(Q∥P)+log⁡(4/δ)2nK. J_n,∞^r,τ(Q)- J_n,K^r,τ(Q) ≤(1+2βτ) KL(Q\|P)+ (4/δ)2nK. Proof. Condition on the realized prompts x1:nx_1:n, and let λ>0λ>0 be arbitrary. For each index pair (i,j)(i,j), define Zi,j(θ):=r(xi,yi,j)−βℓθτ(xi,yi,j).Z_i,j(θ):=r(x_i,y_i,j)-β\, _θ^τ(x_i,y_i,j). For every θ∈Θθ∈ , the bounds r∈[0,1]r∈[0,1] and ℓθτ∈[−τ,τ] _θ^τ∈[-τ,τ] imply −βτ≤Zi,j(θ)≤1+βτ.-βτ≤ Z_i,j(θ)≤ 1+βτ. Conditional on (x1:n,θ)(x_1:n,θ), the rollouts are independent across all pairs (i,j)(i,j). Define the deviation Δ(θ):=J^n,∞r,τ(θ)−J^n,Kr,τ(θ). (θ):= J_n,∞^r,τ(θ)- J_n,K^r,τ(θ). By construction, J^n,Kr,τ(θ) J_n,K^r,τ(θ) is the average of the nKnK random variables Zi,j(θ)Z_i,j(θ), and J^n,∞r,τ(θ) J_n,∞^r,τ(θ) is their conditional expectation given x1:nx_1:n. Applying Lemma 9 to the average of bounded independent terms yields [exp⁡(λΔ(θ))∣x1:n,θ]≤exp⁡(λ2(1+2βτ)28nK).E\! [ (λ (θ) ) x_1:n,θ ]≤ \! ( λ^2(1+2βτ)^28nK ). Taking expectation over θ∼Pθ P and applying Markov’s inequality implies that, with probability at least 1−δ/21-δ/2 over rollouts conditional on x1:nx_1:n, θ∼P[exp⁡(λΔ(θ))∣x1:n]≤2δexp⁡(λ2(1+2βτ)28nK).E_θ P [ (λ (θ) ) x_1:n ]≤ 2δ \! ( λ^2(1+2βτ)^28nK ). On this event, Lemma 10 applied with F(θ)=λΔ(θ)F(θ)=λ (θ) yields that, for every posterior Q, λ(J^n,∞r,τ(Q)−J^n,Kr,τ(Q))≤KL(Q∥P)+log⁡2δ+λ2(1+2βτ)28nK.λ ( J_n,∞^r,τ(Q)- J_n,K^r,τ(Q) ) (Q\|P)+ 2δ+ λ^2(1+2βτ)^28nK. Optimizing over λ>0λ>0 gives J^n,∞r,τ(Q)−J^n,Kr,τ(Q)≤(1+2βτ)KL(Q∥P)+log⁡(2/δ)2nK. J_n,∞^r,τ(Q)- J_n,K^r,τ(Q)≤(1+2βτ) KL(Q\|P)+ (2/δ)2nK. Applying the same argument to the deviation −Δ(θ)- (θ) and taking a union bound yields the stated two-sided inequality with log⁡(4/δ) (4/δ). ∎ C.6 PAC-Bayes main bound Proof of Theorem 2. Let ϕ∈Φφ∈ be arbitrary, and let τ>0τ>0 and δ∈(0,1)δ∈(0,1) be given. Let P denote the prior that appears in Theorem 2. The proof proceeds by combining two PAC-Bayes concentration inequalities with the deterministic reward-shift and clipping-bias bounds, and then substituting these ingredients into the same three-term decomposition used in the fixed-policy case. Apply Lemma 15 with reward r=r^ϕr= r_φ and confidence level δ/2δ/2. Apply Lemma 14 with reward r=r^ϕr= r_φ and confidence level δ/2δ/2. By a union bound, with probability at least 1−δ1-δ over prompts and rollouts, both inequalities hold simultaneously for all posteriors Q on Θ . On this event, for every posterior Q, |J^n,Kϕ,τ(Q)−J^n,∞ϕ,τ(Q)|≤ J_n,K^φ,τ(Q)- J_n,∞^φ,τ(Q) ≤ (1+2βτ)KL(Q∥P)+log⁡(8/δ)2nK, (1+2βτ) KL(Q\|P)+ (8/δ)2nK, |J^n,∞ϕ,τ(Q)−Jϕ,τ(Q)|≤ J_n,∞^φ,τ(Q)-J^φ,τ(Q) ≤ (1+2βτ)KL(Q∥P)+log⁡(8/δ)2n. (1+2βτ) KL(Q\|P)+ (8/δ)2n. Combining these two bounds via the triangle inequality yields |J^n,Kϕ,τ(Q)−Jϕ,τ(Q)|≤ J_n,K^φ,τ(Q)-J^φ,τ(Q) ≤ (1+2βτ)(KL(Q∥P)+log⁡(8/δ)2n+KL(Q∥P)+log⁡(8/δ)2nK). (1+2βτ) ( KL(Q\|P)+ (8/δ)2n+ KL(Q\|P)+ (8/δ)2nK ). The remaining two contributions follow by averaging pointwise bounds over θ∼Qθ Q. Taking expectation in Lemma 7 yields |Jϕ,τ(Q)−Jϕ(Q)|≤βθ∼Q[(X,Y)∼Dθ[|ℓθ(X,Y)−ℓθτ(X,Y)|]]. J^φ,τ(Q)-J^φ(Q) ≤β\,E_θ Q\! [E_(X,Y) D_θ\! [ _θ(X,Y)- _θ^τ(X,Y) ] ]. Taking expectation in Lemma 5 yields |Jϕ(Q)−J⋆(Q)|≤θ∼Q[(θ)]Ltrain(2)(ϕ). J^φ(Q)-J (Q) _θ Q[C(θ)]\, L_train^(2)(φ). Finally, apply the same add-and-subtract decomposition used in Lemma 1 directly to J^n,Kϕ,τ(Q)−J⋆(Q) J_n,K^φ,τ(Q)-J (Q), and then substitute the three bounds established above to obtain the stated inequality. On the same event of probability at least 1−δ1-δ, this gives the inequality stated in Theorem 2, and the statement holds simultaneously for all posteriors Q because the concentration step was uniform over Q. ∎ C.7 Proofs for PAC-Bayes special cases C.7.1 Finite candidate class and checkpoint selection Proof of Corollary 1. Let M≥2M≥ 2 be an integer, and let ΘM=θ(1),…,θ(M) _M=\θ^(1),…,θ^(M)\ be the finite set of candidate parameters described in the statement of the corollary. Let P denote the uniform distribution on ΘM _M, so that P(θ(m))=1/MP(θ^(m))=1/M holds for every m∈1,…,Mm∈\1,…,M\. Let Q be an arbitrary distribution supported on the same finite set ΘM _M. For each m∈1,…,Mm∈\1,…,M\, define pm:=P(θ(m))=1M,qm:=Q(θ(m)),p_m:=P(θ^(m))= 1M, q_m:=Q(θ^(m)), so that qm≥0q_m≥ 0 holds for every m and ∑m=1Mqm=1 _m=1^Mq_m=1 holds by the definition of a probability mass function. By the definition of the Kullback–Leibler divergence on a finite set, one has KL(Q∥P)=∑m=1Mqmlog⁡qmpm.KL(Q\|P)= _m=1^Mq_m q_mp_m. Substituting the identity pm=1/Mp_m=1/M into the preceding display yields KL(Q∥P)=∑m=1Mqmlog⁡(qmM)=log⁡M+∑m=1Mqmlog⁡qm,KL(Q\|P)= _m=1^Mq_m (q_mM)= M+ _m=1^Mq_m q_m, where the final equality follows because ∑m=1Mqm=1 _m=1^Mq_m=1 allows the factor log⁡M M to be separated from the summation. It therefore remains to control the quantity ∑m=1Mqmlog⁡qm _m=1^Mq_m q_m. For every index m∈1,…,Mm∈\1,…,M\, the probability value qmq_m lies in the interval [0,1][0,1], and therefore one has log⁡qm≤0 q_m≤ 0 whenever qm>0q_m>0, which implies that qmlog⁡qm≤0q_m q_m≤ 0 whenever qm>0q_m>0. When qm=0q_m=0, the contribution qmlog⁡qmq_m q_m is interpreted as 0, which is consistent with the limiting identity limt↓0tlog⁡t=0 _t 0t t=0. Consequently, every term in the sum ∑m=1Mqmlog⁡qm _m=1^Mq_m q_m is less than or equal to 0, and hence ∑m=1Mqmlog⁡qm≤0. _m=1^Mq_m q_m≤ 0. Substituting this inequality into the identity above gives KL(Q∥P)=log⁡M+∑m=1Mqmlog⁡qm≤log⁡M.KL(Q\|P)= M+ _m=1^Mq_m q_m≤ M. Finally, consider the special case in which Q is the Dirac distribution concentrated on a single element θ(m^)∈ΘMθ^( m)∈ _M. In that case one has qm^=1q_ m=1 and qm=0q_m=0 for all m≠m^m≠ m. Substituting these values into the definition KL(Q∥P)=∑m=1Mqmlog⁡qmpmKL(Q\|P)= _m=1^Mq_m q_mp_m shows that the only nonzero contribution is the term indexed by m m, and therefore KL(Q∥P)=1⋅log⁡11/M=log⁡M.KL(Q\|P)=1· 11/M= M. This proves the final statement of the corollary. ∎ C.7.2 OU–SGD special case for the PAC-Bayes complexity term Lemma 16 (Bounds for the stationary covariance in the OU approximation). Let H∈ℝd×dH ^d× d be symmetric and positive definite, let Σg∈ℝd×d _g ^d× d be symmetric and positive definite, and let ε>0 >0. Assume that Σ∈ℝd×d ^d× d is symmetric and satisfies the matrix equation HΣ+ΣH=εΣg.H + H= \, _g. Assume also that H and Σg _g commute, meaning that HΣg=ΣgH _g= _gH holds. Assume finally that there exist constants 0<m≤M<∞0<m≤ M<∞ such that mI⪯H⪯MImI H MI. Then, Σ satisfies the two-sided bound ε2MΣg⪯Σ⪯ε2mΣg. 2M\, _g 2m\, _g. (11) Proof. Throughout the proof, for symmetric matrices A and B, the notation A⪯BA B means that v⊤Av≤v⊤Bv Av≤ v Bv holds for every vector v∈ℝdv ^d. This definition is convenient because it reduces the verification of a matrix inequality to the verification of an ordinary inequality that holds uniformly over all vectors. Define the matrix-valued function F(t):=e−tHΣe−tHfor t≥0.F(t):=e^-tH\, \,e^-tH t≥ 0. Since H is symmetric, the matrix exponential e−tHe^-tH is well-defined for every t≥0t≥ 0, and the map t↦F(t)t F(t) is differentiable. Differentiating and using the product rule yields dtF(t)=(−He−tH)Σe−tH+e−tHΣ(−He−tH)=−e−tH(HΣ+ΣH)e−tH. ddtF(t)=(-He^-tH) e^-tH+e^-tH (-He^-tH)=-e^-tH(H + H)e^-tH. Substituting the identity HΣ+ΣH=εΣgH + H= \, _g gives dtF(t)=−εe−tHΣge−tH. ddtF(t)=- \,e^-tH _ge^-tH. Integrating the preceding identity from 0 to T gives F(T)−F(0)=−ε∫0Te−tHΣge−tHt.F(T)-F(0)=- _0^Te^-tH _ge^-tH\,dt. Since F(0)=ΣF(0)= , rearranging yields Σ=F(T)+ε∫0Te−tHΣge−tHt. =F(T)+ _0^Te^-tH _ge^-tH\,dt. Because H is positive definite, there exists a constant m0>0m_0>0 such that H⪰m0IH m_0I, and therefore the operator norm satisfies ‖e−tH‖2≤e−tm0\|e^-tH\|_2≤ e^-tm_0 for every t≥0t≥ 0. This inequality implies ‖F(T)‖2=‖e−THΣe−TH‖2≤‖e−TH‖22‖Σ‖2≤e−2Tm0‖Σ‖2\|F(T)\|_2=\|e^-TH e^-TH\|_2≤\|e^-TH\|_2^2\| \|_2≤ e^-2Tm_0\| \|_2, and hence F(T)F(T) converges to the zero matrix as T→∞T→∞. Taking the limit T→∞T→∞ yields the integral identity Σ=ε∫0∞e−tHΣge−tHt. = _0^∞e^-tH _ge^-tH\,dt. It remains to compare e−tHΣge−tHe^-tH _ge^-tH to scalar multiples of Σg _g in the Loewner order. The assumption mI⪯H⪯MImI H MI means that every eigenvalue of H lies in the interval [m,M][m,M]. Consequently, every eigenvalue of e−2tHe^-2tH lies in the interval [e−2tM,e−2tm][e^-2tM,\,e^-2tm], and this implies the inequalities e−2tMI⪯e−2tH⪯e−2tmIfor every t≥0.e^-2tMI e^-2tH e^-2tmI every t≥ 0. The commutativity condition HΣg=ΣgH _g= _gH implies that Σg _g commutes with the matrix exponential e−tHe^-tH for every t≥0t≥ 0. Therefore one has e−tHΣge−tH=Σge−tHe−tH=Σge−2tH.e^-tH _ge^-tH= _ge^-tHe^-tH= _ge^-2tH. Since Σg≻0 _g 0, the matrix square root Σg1/2 _g^1/2 exists and is symmetric and positive definite. Applying the congruence transformation with Σg1/2 _g^1/2 to the Loewner inequalities above yields Σg1/2(e−2tMI)Σg1/2⪯Σg1/2e−2tHΣg1/2⪯Σg1/2(e−2tmI)Σg1/2for every t≥0. _g^1/2 (e^-2tMI ) _g^1/2 _g^1/2e^-2tH _g^1/2 _g^1/2 (e^-2tmI ) _g^1/2 every t≥ 0. Using Σg1/2IΣg1/2=Σg _g^1/2I _g^1/2= _g and the scalar factors in the two outer terms gives e−2tMΣg⪯Σg1/2e−2tHΣg1/2⪯e−2tmΣgfor every t≥0.e^-2tM _g _g^1/2e^-2tH _g^1/2 e^-2tm _g every t≥ 0. The commutativity condition implies that Σg1/2 _g^1/2 commutes with e−tHe^-tH and therefore also commutes with e−2tHe^-2tH, which yields Σg1/2e−2tHΣg1/2=e−2tHΣg=e−tHΣge−tH. _g^1/2e^-2tH _g^1/2=e^-2tH _g=e^-tH _ge^-tH. Substituting this identity into the preceding display yields e−2tMΣg⪯e−tHΣge−tH⪯e−2tmΣgfor every t≥0.e^-2tM _g e^-tH _ge^-tH e^-2tm _g every t≥ 0. Substituting these two bounds into the integral representation of Σ yields ε∫0∞e−2tMΣgt⪯Σ⪯ε∫0∞e−2tmΣgt. _0^∞e^-2tM _g\,dt _0^∞e^-2tm _g\,dt. Evaluating the scalar integrals gives ε∫0∞e−2tMt=ε2M,ε∫0∞e−2tmt=ε2m, _0^∞e^-2tM\,dt= 2M, _0^∞e^-2tm\,dt= 2m, and substituting these values proves eq. (11). ∎ Proof of Corollary 2. Assume the parameter space is ℝdR^d and the prior is P=(θ0,Λ)P=N( _0, ) with Λ≻0 0. Furthermore, assume the posterior induced by SGD with constant step size ε>0 >0 is approximated by the stationary Ornstein-Uhlenbeck law QSGD=(θ^,Σ)Q_SGD=N( θ, ). By the local quadratic approximation of the objective, the covariance Σ satisfies the continuous Lyapunov equation HΣ+ΣH=εΣgH + H= \, _g, where Σg≻0 _g 0 is the gradient noise covariance and H≻0H 0 is the objective Hessian at the optimum θ θ. We assume that H and Σg _g commute, and that the matrix H is symmetric and satisfies mI⪯H⪯MImI H MI for some constants 0<m≤M<∞0<m≤ M<∞. Apply Lemma 13 with μQ=θ _Q= θ, ΣQ=Σ _Q= , μP=θ0 _P= _0, and ΣP=Λ _P= . This yields KL(QSGD∥P)=12(tr⁡(Λ−1Σ)+(θ^−θ0)⊤Λ−1(θ^−θ0)−d+log⁡det(Λ)det(Σ)). (Q_SGD\|P)= 12 (tr( ^-1 )+( θ- _0) ^-1( θ- _0)-d+ ( ) ( ) ). (12) The remaining task is to upper bound the trace term and to upper bound the logarithmic determinant ratio in a way that makes the dependence on ε , Σg _g, and the constants m and M explicit. First, apply Lemma 16, which gives Σ⪯ε2mΣg 2m _g. Since Λ−1≻0 ^-1 0, this inequality implies Λ−1/2ΣΛ−1/2⪯ε2mΛ−1/2ΣgΛ−1/2 ^-1/2 ^-1/2 2m ^-1/2 _g ^-1/2, and taking traces yields tr⁡(Λ−1Σ)=tr⁡(Λ−1/2ΣΛ−1/2)≤ε2mtr⁡(Λ−1/2ΣgΛ−1/2)=ε2mtr⁡(Λ−1Σg).tr( ^-1 )=tr( ^-1/2 ^-1/2)≤ 2mtr( ^-1/2 _g ^-1/2)= 2mtr( ^-1 _g). Second, apply Lemma 16 again, which also gives Σ⪰ε2MΣg 2M _g. This inequality implies that the eigenvalues of Σ dominate the eigenvalues of ε2MΣg 2M _g when both collections are arranged in nondecreasing order, and therefore the product of the eigenvalues of Σ is at least the product of the eigenvalues of ε2MΣg 2M _g. Consequently, det(Σ)≥det(ε2MΣg)=(ε2M)ddet(Σg), ( )≥ \! ( 2M _g )= ( 2M )^d ( _g), where the last equality uses the basic scaling rule for determinants. Taking logarithms and rearranging yields log⁡det(Λ)det(Σ)≤logdet(Λ)−logdet(Σg)−dlog⁡(ε2M). ( ) ( )≤ ( )- ( _g)-d \! ( 2M ). Substituting the preceding two bounds into eq. (12) yields the claimed inequality eq. (8), and this completes the proof. ∎ C.8 Budget allocation Derivation of the uniform-cost baseline K⋆=1K =1. Assume that the sampling budget satisfies nK≤BnK≤ B for some B>0B>0, and assume that each rollout has the same cost so that the constraint depends only on the product nKnK. Consider the leading-order sampling structure in Lemma 4 and ignore multiplicative constants that do not depend on K. The resulting proxy has the form 1n+1nK. 1 n+ 1 nK. Under the constraint nK≤BnK≤ B, one may take n=B/Kn=B/K without loss of generality for minimizing the proxy over K≥1K≥ 1. Substituting n=B/Kn=B/K yields 1n+1nK=KB+1B. 1 n+ 1 nK= KB+ 1 B. The second term does not depend on K, and the first term is strictly increasing in K for K≥1K≥ 1. Therefore the proxy is minimized by the smallest admissible value of K, which is K⋆=1K =1. ∎ Proof of Corollary 4. Let B>0B>0, cprefill>0c_prefill>0, and cdecode>0c_decode>0 be given. Assume the budget constraint B≥ncprefill+nKcdecode,B≥ n\,c_prefill+nK\,c_decode, and consider the leading-order sampling structure induced by Lemma 4. As in the statement, treat K as a continuous variable with K≥1K≥ 1 and ignore multiplicative constants and logarithmic factors that do not depend on K. The sampling proxy can be written in the form E(n,K)=1n+1nK.E(n,K)= 1 n+ 1 nK. Under the constraint, the choice n=Bcprefill+Kcdecoden= Bc_prefill+Kc_decode saturates the budget and maximizes n for a given K, hence it minimizes E(n,K)E(n,K) for that K. Substituting this expression for n gives an objective that depends only on K, E(K)=cprefill+KcdecodeB(1+1K).E(K)= c_prefill+Kc_decodeB (1+ 1 K ). Since B is constant, minimizing E(K)E(K) over K≥1K≥ 1 is equivalent to minimizing the squared objective F(K):=(cprefill+Kcdecode)(1+1K)2.F(K):= (c_prefill+Kc_decode ) (1+ 1 K )^2. Expanding the square gives F(K)=(cprefill+Kcdecode)(1+2K+1K)=(cprefill+Kcdecode)+2(cprefill+Kcdecode)K−1/2+(cprefill+Kcdecode)K−1.F(K)= (c_prefill+Kc_decode ) (1+ 2 K+ 1K )= (c_prefill+Kc_decode )+2 (c_prefill+Kc_decode )K^-1/2+ (c_prefill+Kc_decode )K^-1. Differentiating term by term yields F′(K)=cdecode+2(cdecodeK−1/2−12(cprefill+Kcdecode)K−3/2)+(cdecodeK−1−(cprefill+Kcdecode)K−2).F (K)=c_decode+2 (c_decodeK^-1/2- 12 (c_prefill+Kc_decode )K^-3/2 )+ (c_decodeK^-1- (c_prefill+Kc_decode )K^-2 ). Simplifying this expression gives F′(K)=cdecode+cdecodeK−1/2−cprefillK−3/2−cprefillK−2.F (K)=c_decode+c_decodeK^-1/2-c_prefillK^-3/2-c_prefillK^-2. Multiplying by K2K^2 yields an equivalent first-order condition K2F′(K)=cdecodeK2+cdecodeK3/2−cprefillK1/2−cprefill.K^2F (K)=c_decodeK^2+c_decodeK^3/2-c_prefillK^1/2-c_prefill. Let u=Ku= K, so that K=u2K=u^2 and K3/2=u3K^3/2=u^3. The condition F′(K)=0F (K)=0 is equivalent to cdecodeu4+cdecodeu3−cprefillu−cprefill=0,c_decodeu^4+c_decodeu^3-c_prefillu-c_prefill=0, and the polynomial factors as cdecodeu3(u+1)−cprefill(u+1)=(u+1)(cdecodeu3−cprefill).c_decodeu^3(u+1)-c_prefill(u+1)=(u+1) (c_decodeu^3-c_prefill ). Since u=K≥1u= K≥ 1, one has u+1>0u+1>0, so any interior stationary point satisfies cdecodeu3=cprefillc_decodeu^3=c_prefill. Therefore u=(cprefillcdecode)1/3,K=u2=(cprefillcdecode)2/3.u= ( c_prefillc_decode )^1/3, K=u^2= ( c_prefillc_decode )^2/3. This is the interior stationary point. Because the optimisation domain is K≥1K≥ 1, the continuous proxy minimiser is K⋆=max⁡1,(cprefillcdecode)2/3.K = \! \1, ( c_prefillc_decode )^2/3 \. ∎ Proof of Corollary 5. Let Z denote the per-rollout contribution used in the empirical objective. Assume that the estimator averages Z over n independent prompts and K independent rollouts per prompt. Define the two-stage variance quantities σprompt2:=Var([Z∣X]),σrollout2:=[Var(Z∣X)]. _prompt^2:=Var\! (E[Z X] ), _rollout^2:=E\! [Var(Z X) ]. The standard variance decomposition for a two-stage average yields the proxy V(n,K)=σprompt2n+σrollout2nK.V(n,K)= _prompt^2n+ _rollout^2nK. Assume the budget constraint B≥ncprefill+nKcdecode,B≥ n\,c_prefill+nK\,c_decode, and substitute the saturated choice n=B/(cprefill+Kcdecode)n=B/(c_prefill+Kc_decode). This yields V(K)=cprefill+KcdecodeB(σprompt2+σrollout2K).V(K)= c_prefill+Kc_decodeB ( _prompt^2+ _rollout^2K ). Since B is constant, minimizing V(K)V(K) over K≥1K≥ 1 is equivalent to minimizing G(K):=(cprefill+Kcdecode)(σprompt2+σrollout2K).G(K):= (c_prefill+Kc_decode ) ( _prompt^2+ _rollout^2K ). Expanding gives G(K)=cprefillσprompt2+cprefillσrollout2K+cdecodeKσprompt2+cdecodeσrollout2.G(K)=c_prefill _prompt^2+c_prefill _rollout^2K+c_decodeK _prompt^2+c_decode _rollout^2. Differentiating yields G′(K)=−cprefillσrollout2K2+cdecodeσprompt2.G (K)=-c_prefill _rollout^2K^2+c_decode _prompt^2. Setting G′(K)=0G (K)=0 gives cdecodeσprompt2=cprefillσrollout2K2,c_decode _prompt^2=c_prefill _rollout^2K^2, which implies K2=cprefillcdecode⋅σrollout2σprompt2.K^2= c_prefillc_decode· _rollout^2 _prompt^2. Taking square roots yields the interior stationary point K=cprefillcdecode⋅σrollout2σprompt2.K= c_prefillc_decode· _rollout^2 _prompt^2. Because the optimisation domain is K≥1K≥ 1, the continuous proxy minimiser is K⋆=max⁡1,cprefillcdecode⋅σrollout2σprompt2.K = \! \1, c_prefillc_decode· _rollout^2 _prompt^2 \. ∎

Instant research discovery