Paper deep dive
Provably Mitigating Corruption, Overoptimization, and Verbosity Simultaneously in Offline and Online RLHF/DPO Alignment
Ziyi Chen, Junyi Li, Peiran Yu, Heng Huang
Models: Zephyr-7b-gemma-sft-v0.1
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 96%
Last extracted: 3/11/2026, 12:40:33 AM
Summary
The paper introduces RLHF-COV and DPO-COV, novel algorithms designed to simultaneously mitigate corrupted preference data, reward overoptimization, and verbosity bias in LLM alignment. The authors provide theoretical guarantees for generalization error rates in both offline and online settings, prove the equivalence between their RLHF-COV and DPO-COV variants, and demonstrate that these methods generalize vanilla RLHF and DPO.
Entities (7)
Relation Signals (4)
RLHF-COV → mitigates → Corruption
confidence 95% · we propose RLHF-COV and DPO-COV algorithms that can simultaneously mitigate these three issues
DPO-COV → mitigates → Overoptimization
confidence 95% · we propose RLHF-COV and DPO-COV algorithms that can simultaneously mitigate these three issues
DPO-COV → mitigates → Verbosity
confidence 95% · we propose RLHF-COV and DPO-COV algorithms that can simultaneously mitigate these three issues
DPO-COV → equivalentto → RLHF-COV
confidence 90% · our DPO-COV algorithm is simple to implement without reward estimation, and is proved to be equivalent to our RLHF-COV algorithm
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Reinforcement learning from human feedback (RLHF) and direct preference optimization (DPO) are important techniques to align large language models (LLM) with human preference. However, the quality of RLHF and DPO training is seriously compromised by \textit{\textbf{C}orrupted} preference, reward \textit{\textbf{O}veroptimization}, and bias towards \textit{\textbf{V}erbosity}. To our knowledge, most existing works tackle only one of these important issues, and the few other works require much computation to estimate multiple reward models and lack theoretical guarantee of generalization ability. In this work, we propose RLHF-\textbf{COV} and DPO-\textbf{COV} algorithms that can simultaneously mitigate these three issues, in both offline and online settings. This ability is theoretically demonstrated by obtaining length-regularized generalization error rates for our DPO-COV algorithms trained on corrupted data, which match the best-known rates for simpler cases with clean data and without length regularization. Moreover, our DPO-COV algorithm is simple to implement without reward estimation, and is proved to be equivalent to our RLHF-COV algorithm, which directly implies the equivalence between the vanilla RLHF and DPO algorithms. Experiments demonstrate the effectiveness of our DPO-COV algorithms under both offline and online settings.
Tags
Links
- Source: https://arxiv.org/abs/2510.05526
- Canonical: https://arxiv.org/abs/2510.05526
Trouble viewing inline? Open PDF directly →
Full Text
90,636 characters extracted from source content.
Expand or collapse full text
Provably Mitigating Corruption, Overoptimization, and Verbosity Simultaneously in Offline and Online RLHF/DPO Alignment Ziyi Chen 1 , Junyi Li 2 , Peiran Yu 3 , Heng Huang 1 1 Department of Computer Science, University of Maryland, College Park zc286,heng@umd.edu 2 Amazon junyili.ai@gmail.com 3 Department of Computer Science and Engineering, University of Texas Arlington peiran.yu@uta.edu Abstract Reinforcement learning from human feedback (RLHF) and direct preference optimization (DPO) are important techniques to align large language models (LLM) with human preference. However, the quality of RLHF and DPO training is seriously compromised by Corrupted preference, reward Overoptimization, and bias towards Verbosity. To our knowledge, most existing works tackle only one of these important issues, and the few other works require much computation to estimate multiple reward models and lack theoretical guarantee of generalization ability. In this work, we propose RLHF-COV and DPO-COV algorithms that can simultaneously mitigate these three issues, in both offline and online settings. This ability is theoretically demonstrated by obtaining length-regularized generalization error rates for our DPO-COV algorithms trained on corrupted data, which match the best-known rates for simpler cases with clean data and without length regularization. Moreover, our DPO-COV algorithm is simple to implement without reward estimation, and is proved to be equivalent to our RLHF-COV algorithm, which directly implies the equivalence between the vanilla RLHF and DPO algorithms. Experiments demonstrate the effectiveness of our DPO-COV algorithms under both offline and online settings. 1 Introduction Reinforcement learning from human feedback (RLHF) has been widely used in robotics (Christiano et al., 2017; Bukharin et al., 2024), autonomous driving (Wang et al., 2024; Cao et al., 2024), large language models (LLM) (Ouyang et al., 2022; Bai et al., 2022b; Rafailov et al., 2023), image and video generation (Wallace et al., 2023; Liang et al., 2024; Liu et al., 2024b), etc. This work will focus on the application of RLHF to LLM alignment which makes LLM more helpful, honest, and harmless (Ouyang et al., 2022; Bai et al., 2022b). LLM alignment has two critical steps. The first step is reward modeling, which estimates the reward model that measures the quality of LLM responses, based on human preference data. The second step is reinforcement learning (RL), which fine-tunes the LLM policy to generate responses with an improved expected value of the learned reward (Ouyang et al., 2022). Direct preference optimization (DPO) (Rafailov et al., 2023) further simplifies the standard RLHF process by directly fine-tuning the optimal policy without reward estimation. However, the LLM aligned by RLHF and DPO sometimes yields undesirable responses, due to the corruption, overoptimization, and verbosity issues, as introduced below. 1 arXiv:2510.05526v2 [cs.LG] 9 Dec 2025 Corruption. The quality of preference data is essential in RLHF and DPO. However, preference labels given by human may be corrupted due to inexperience, inattention, personal bias, unclear context, and even malicious falsification (Bukharin et al., 2024). For instance, when fine-tuning LLM for automated content moderation on social media, malicious annotators may mislabel harmful contents like misinformation and hate speech as preferable, which misleads the LLM to generate such harmful contents. Therefore, robustness of RLHF and DPO to such corruption is critical, but is tackled by only a few recent works to our knowledge. For example, Cheng et al. (2024); Mandal et al. (2024); Gao et al. (2024b) use confidence-based data filtering. Ethayarajh et al. (2024) maximizes the utility function defined based on the prospect theory of human decision making (Tversky and Kahneman, 1992) to filter out noisy data. Coste et al. (2024); Rame et al. (2024) estimate an ensemble of rewards. The recently proposed robust RLHF and robust DPO approaches in (Bukharin et al., 2024) use noise modeling to automatically select the outliers and the estimated reward provably converges to the true reward. Overoptimization. RLHF and DPO may overoptimize the reward model, yielding LLM responses of high estimated reward but low actual quality (Gao et al., 2023; Casper et al., 2023). Various methods have been proposed to tackle such overoptimization issue (a.k.a. reward hacking). For example, Gao et al. (2023) uses larger reward model which significantly increases the computational cost of pretraining. Moskovitz et al. (2024) applies constraints to RLHF. TheΦPo method (Azar et al., 2024) optimizes a general preference function. Eisenstein et al. (2024); Coste et al. (2024); Rame et al. (2024); Fisch et al. (2024); Zhai et al. (2023) use an ensemble of estimated rewards. An emerging and popular strategy with provable generalization ability to solve overoptimization is to adopt a pessimistic (resp. an optimistic) approach for RLHF and DPO with offline (resp. online) data. Specifically, in the offline setting where only precollected offline preference data is available for training, there are many out-of-distribution samples about which we cannot obtain any information. Therefore, Zhu et al. (2023, 2024); Liu et al. (2024c); Cen et al. (2024); Ji et al. (2024); Yang et al. (2024); Huang et al. (2024); Xiong et al. (2024); Ye et al. (2024); Fisch et al. (2024) apply pessimistic principle to RLHF or DPO which penalizes LLM from generating such unknown out-of-distribution responses and thus to mitigate overoptimization. Such pessimism principle has also been used in conventional offline RL (Xie et al., 2021; Jin et al., 2021; Rashidinejad et al., 2021; Bai et al., 2022a; Cheng et al., 2022). In contrast, in the online setting where online data can be collected from the up-to-date policy during the training process, optimistic approaches have been used to encourage the collection of unexplored samples to enrich data diversity in RLHF and DPO (Cen et al., 2024; Xie et al., 2024; Zhang et al., 2024; Ye et al., 2024; Xiong et al., 2024) as well as conventional RL (Wei et al., 2017; Zhong and Zhang, 2023; Liu et al., 2023a,b). Verbosity. LLM aligned by vanilla RLHF and DPO is likely to prefer verbose but possibly low-quality responses (Singhal et al., 2023; Chen et al., 2024; Liu et al., 2024a; Dong et al., 2024; Fisch et al., 2024). Multiple methods have been used to tackle verbosity. For example, Shen et al. (2023); Chen et al. (2024) disentangle length-related reward component. Guo et al. (2024) instructs the LLM to prefer concise response. Eisenstein et al. (2024); Fisch et al. (2024); Chakraborty et al. (2024) estimate an ensemble of reward models. Singhal et al. (2023); Liu et al. (2024a); Dong et al. (2024); Park et al. (2024) use length penalty and similarly Meng et al. (2024) uses length normalization. Our Motivation. However, to our knowledge, most existing works primarily tackle only one of these three issues (corruption, overoptimization and verbosity). The only method to our knowledge that has been used to tackle all these issues is to estimate an ensemble of reward models (Coste et al., 2024; Fisch et al., 2024; Eisenstein et al., 2024; Rame et al., 2024), which, however, requires much computation and lacks theoretical guarantee of generalization ability. Therefore, we are motivated to ask the following research question. 2 Q: Can we design RLHF and DPO algorithms that solve corruption, overoptimization and verbosity simultaneously with simple implementation and theoretical guarantee of generalization ability? 1.1 Our Contributions We answer the above question affirmatively, by proposing RLHF-COV and DPO-COV algorithms that simultaneously mitigate Corruption, Overoptimization and Verbosity issues, in both offline and online settings. Specifically, we tackle Corruption by noise modeling, tackle Overoptimization by pessimistic and optimistic regularizers in the offline and online settings respectively, and tackle Verbosity by length regularizer. Our DPO-COV algorithms are almost as simple to implement as the vanilla DPO algorithm without reward model estimation. We prove that our RLHF-COV and DPO-COV are equivalent in the reward-induced policy space in both the offline and online settings. Since our RLHF-COV and DPO-COV algorithms generalize the vanilla RLHF and DPO algorithms respectively, our equivalence result implies that the vanilla RLHF and DPO algorithms are also equivalent. Moreover, we obtain the length-regularized generalization error rates of our DPO-COV algorithms on both offline and online datasets obtained from corrupted preference, and the rates match the existing results in the simple special case with clean dataset and without verbosity regularization. This theoretically demonstrates that our algorithms can simultaneously mitigate the Corruption, Overoptimization and Verbosity issues. In particular, the effect of noise modeling on the generalization error of learned policy for corrupted data has not been studied to our knowledge, which requires novel proof techniques. The true and estimated noise terms have very different effects on the generalization error, and thus have to be analyzed at different stages. To elaborate, the estimated noise has to be bounded before applying concentration inequality, such that this unbounded estimated noise term can be canceled out by the noise regularizer. In contrast, the true noise has to be bounded after applying the concentration inequality, since the concentration inequality bounds the distance between the true data distribution (with the true noise term) and the estimated data distribution. 2 Preliminaries Reinforcement learning from human feedback (RLHF). A large language model (LLM) provides a random language responsea∈Xto any given language promptx∈X(for example, instruction or question) following the LLM’s policyπ(·|x). Fine-tuning LLM by reinforcement learning from human feedback (RLHF) consists of two critical steps: training reward model and reinforcement learning (RL) (Ouyang et al., 2022). The reward model is denoted by a functionr(x,a) ∈ Rwhich measures the quality of the responseagiven the promptx. To train the reward model, preference dataD = x i ,a w i ,a ℓ i N i=1 of size Nis collected where a pair of responsesa w i ,a ℓ i are generated given eachi-th promptx i , and the response a w i is more preferable thana ℓ i (i.e.a w i ≻ a ℓ i ). Such a pairwise preference is widely assumed to follow the Bradley-Terry model (Bradley and Terry, 1952), that is, given promptx, the generated responsea ′ is more desirable than a with the following probability. P(a ′ ≻ a|x) = σ[r ∗ (x,a ′ )− r ∗ (x,a)](1) whereσ(x) def = 1/(1 + e −x )andr ∗ is the unknown true reward model.r ∗ can be estimated by maximum likelihood estimation (MLE), that is, to minimize the following negative log-likelihood function over a certain reward model familyR. min r∈R − 1 N N X i=1 logσ[r(x i ,a w i )− r(x i ,a ℓ i )].(2) 3 Finally, given the estimated reward modelr ∈R, the optimal policy is obtained by the following optimization problem over the whole policy space Π def =π|π(·|x) is a distribution overA for any x. max π∈Π E x∼ρ,a∼π(·|x) [r(x,a)]− βE x∼ρ KL π(·|x) π ref (·|x) ,(3) whereρis the prompt distribution,π ref is the reference policy obtained by supervised fine-tuning, and KL(p∥q) = P a∈A p(a) log p(a) q(a) denotes the KL divergence between any pair of response distributionsp,q andβ > 0is the regularizer coefficient which controls the trade-off between generating responses with high expected reward and bounded distance from the reference policy π ref . Direct preference optimization (DPO). As introduced above, classical RLHF requires two large-scale optimization problems to learn the reward modelrand the optimal policyπrespectively. DPO (Rafailov et al., 2023) is introduced to remove the reward learning step and thus reducing computation. To elaborate, note that the optimization problem (3) has the following analytical solution. π(a|x) = π ref (a|x) Z(x) exp h r(x,a) β i ,(4) whereZ(x) := P a ′ ∈A π ref (a ′ |x) exp[r(x,a ′ )/β] is the normalization factor. Conversely, given the optimal policyπ,r(x,a) = β log π(a|x) π ref (a|x) is a solution to Eq.(1). Substituting this reward model into the MLE objective(3), Rafailov et al. (2023) develops the following simple DPO objective which only requires policy training. min π∈Π − 1 N N X i=1 logσ h β log π(a w i |x i ) π ref (a w i |x i ) − β log π(a ℓ i |x i ) π ref (a ℓ i |x i ) i .(5) However, this DPO objective and the aforementioned vanilla RLHF process are prone to suffer from corrupted preference, reward overoptimization, and bias towards verbose response. We will propose our novel variants of RLHF and DPO to solve the three issues simultaneously, for both offline and online settings, in Sections 3 and 4 respectively. 3 Our Offline DPO-COV Algorithm In this section, we will derive our proposed offline RLHF-COV objective and offline DPO-COV algorithm (Algorithm 1) which simultaneously solve the Corruption, Overoptimization and Verbosity issues, and then obtain the generalization error rates of our offline DPO-COV algorithm. 3.1 Our Offline RLHF-COV Objective Offline Data from Corrupted Preference. Assumption 1. The offline dataD def = x i ,a (1) i ,a (−1) i ,y i N i=1 = x i ,a w i ,a ℓ i ,y i N i=1 is generated from the following model with corrupted preference. x i ∼ρ, a (−1) i ,a (1) i ∼ π b (·|x i ),(6) P(a (1) i ≻a (−1) i ) =σ[r ∗ (x i ,a (1) i )−r ∗ (x i ,a (−1) i )+ξ ∗ i ],(7) whereπ b denotes the behavior policy andξ ∗ i ∈ R denotes the true preference noise for thei-th sample. If a (1) i ≻ a (−1) i , assign the labely i = 1and denotea w i = a (1) i as the more preferable response anda ℓ i = a (−1) i as the less preferable response; Otherwise, let y i =−1, a w i = a (−1) i , a ℓ i = a (1) i . 4 The above assumption is very similar to that of offline vanilla RLHF and DPO, except that we add noise ξ ∗ i to the Bradley-Terry model (1) for each possibly corrupted sample i (Bukharin et al., 2024). Based on Assumption 1,P(y i |a (1) i ,a (−1) i ) = σ[r ∗ (x i ,a w i )− r ∗ (x i ,a ℓ i ) + y i ξ ∗ i ],y i ∈ −1, 1 1 . Hence, we define a penalized negative log-likelihood function of the labelsy i N i=1 as follows. L N,λ (r,ξ) def = − 1 N N X i=1 logσ[r(x i ,a w i )− r(x i ,a ℓ i ) + y i ξ i ] + λ N ∥ξ∥ 1 ,(8) which, compared with the standard non-corrupted negative log-likelihood function(2), adds the estimated preference noiseξ = [ξ 1 ,...,ξ N ]∈ R N and the noise regularizer∥ξ∥ 1 = P N i=1 |ξ i | with coefficientλ > 0 to encourage the sparsity of the noise. Reward Estimation via Pessimistic MLE to Solve Overoptimization. After collecting offline data, the next step is to learn the reward modelr. One may consider corrupted MLE objectivemin r∈R,ξ∈R N L N,λ (r,ξ) (Bukharin et al., 2024) which generalizes the non-corrupted MLE objective(2). However, this corrupted MLE objective tend to overfit limited offline data (Gao et al., 2023; Zhu et al., 2024; Liu et al., 2024c; Cen et al., 2024; Xiong et al., 2024), producing an inaccurately estimated reward that leads to overoptimization. Therefore, we consider the following pessimistic MLE inspired by (Liu et al., 2024c; Cen et al., 2024; Ji et al., 2024; Yang et al., 2024). min r∈R,ξ∈R N n L N,λ (r,ξ) + η max π∈Π V β (π,r) o ,(9) where the pessimistic hyperparameter η ≥ 0 and V β (π,r) def = E x∼ρ,a∼π(·|x),a ′ ∼π base (·|x) r(x,a)− r(x,a ′ ) − βE x∼ρ KL π(·|x) π ref (·|x) (10) denotes the relative value of the policyπto a certain baseline policyπ base given the rewardr. The regularizer max π∈Π V β (π,r)in Eq.(9)can be seen as the relative value of the optimal policy, and will help reduce the reward valuer(x,a)of any samplex,awith smallπ base (a|x), so that the optimal policyπ(a|x)given by Eq.(4)will also be reduced. In other words, such samplesx,aare considered pessimistic and are thus discouraged from being generated by the learned policyπ. Hence, the regularizermax π∈Π V β (π,r)is called the pessimistic regularizer. Furthermore, if we selectπ base to represent the offline data distribution (see the end of Section 3.2 for the choice ofπ base ), then these samplesx,awith smallπ base (a|x)can be seen as out-of-distribution, so that such pessimism on the out-of-distribution samples mitigates the overoptimization issue which often results from overestimation of the reward on low-quality out-of-distribution samples (Liu et al., 2024c). Policy Training with Penalized Verbosity. The vanilla RLHF usually yields reward modelr(x,a) that has bias towards long and detailed responses. To suppress verbose responses in the policy optimization stepmax π∈Π V β (π,r), we can replace the reward modelr(x,a)with the proxy reward modelr ω (x,a) = r(x,a)− ω|a|where|a|is the length (i.e., number of tokens) of the responseaand the hyperparameter ω ≥ 0controls the length penalty strength (Singhal et al., 2023; Liu et al., 2024a; Dong et al., 2024; Park et al., 2024). In this way, the policy training objectiveV β (π,r)(defined by Eq.(10)) is generalized to the following length-regularized relative value function. V β,ω (π,r) def = E x∼ρ,a∼π(·|x),a ′ ∼π base (·|x) r(x,a)−ω|a|−r(x,a ′ ) + ω|a ′ | −βE x∼ρ KL π(·|x) π ref (·|x) .(11) 1 We corrected the mistake in (Bukharin et al., 2024) which usesP(y i |a (1) i ,a (−1) i ) = σ[r ∗ (x i ,a w i )− r ∗ (x i ,a ℓ i ) + ξ ∗ i ],y i ∈ −1, 1 that yields P y i ∈−1,1 P(y i |a (1) i ,a (−1) i )̸= 1. 5 ReplacingV β (π,r)withV β,ω (π,r)in the pessimistic MLE objective(9), we propose offline RLHF-COV objective below. (Offline RLHF-COV):min r∈R,ξ∈R N max π∈Π L N,λ (r,ξ) + ηV β,ω (π,r) .(12) Remark: Our offline RLHF-COV objective shown above simultaneously tackles the Corruption, Overoptimization and Verbosity issues, via noise modeling, pessimism and length penalty with controllable hyperparametersλ, η,ωrespectively. Specifically, the length penalty is only added toV β,ω notL N,λ , because in the pessimistic MLE we still want to obtain a rewardrpossibly with length bias, and then verbosity is only suppressed in the policy optimization partmax π∈Π V β,ω (π,r). Whenλ≥ 1andη = ω = 0, our offline RLHF-COV objective above reduces to the reward estimation (2) and policy optimization (3) in the vanilla RLHF. 3.2 Our Offline DPO-COV Algorithm The offline RLHF-COV objective(12)involves minimax optimization over three high-dimensional variables r,ξ,π. As the first step to simplify this objective, we obtain the following proposition. Proposition 1. (π,r,ξ) is the solution to the offline RLHF-COV objective (12) if and only if π = π r def = arg max π ′ ∈Π V β,ω (π ′ ,r) ,ξ = ξ r def = arg min ξ∈R N L N,λ (r,ξ) andris the solution to the following optimization problem. min r∈R [L N,λ (r,ξ r ) + ηV β,ω (π r ,r)].(13) In addition, π r and ξ r,i (the i-th entry of ξ r ) have the following analytical solutions. π r (a|x) = π ref (a|x) Z r (x) exp h r(x,a)− ω|a| β i ,(14) ξ r,i =y i Iλ < 1 h log 1 λ −1 −r(x i ,a w i )+r(x i ,a ℓ i ) i + ,(15) whereZ r (x) def = P a ′ ∈A π ref (a ′ |x) exp r(x,a ′ )−ω|a ′ | β is the normalization factor,Iλ < 1equals 1 ifλ < 1 and 0 otherwise, and [u] + = max(u, 0) for any u∈ R. The above proposition simplifies the offline RLHF-COV objective(12)into the reward estimation problem (13). Next, we will transform it into our DPO-COV objective of the policyπ. In Eq.(14), givenπ = π r , a solution to the reward model r is r π (x,a) def = ω|a| + β log h π(a|x) π ref (a|x) i .(16) With the above rewardr π , the corresponding noise can also be parameterized byπasξ π def = ξ r π , whosei-th entry has the following analytical solution based on Eqs. (15) and (16). ξ π i def =ξ r π ,i = y i Iλ < 1 h log 1 λ −1 −ω(|a w i |−|a ℓ i |)− β log π(a w i |x i )π ref (a ℓ i |x i ) π(a ℓ i |x i )π ref (a w i |x i ) i + ,(17) Substituting the above r π and ξ π i into Eq. (13), we propose our DPO-COV objective as follows. 2 2 The = in the offline DPO-COV objective (18) is based on Eqs. (8), (11) and (16). 6 (Offline DPO-COV): min π∈Π R n L N,λ (r π ,ξ π ) + ηV β,ω (π r π ,r π ) =−βηE x∼ρ,a∼π base (·|x) logπ(a|x) + 1 N N X i=1 h λ|ξ π i |−logσ ω(|a w i |−|a ℓ i |) +β log π(a w i |x i )π ref (a ℓ i |x i ) π(a ℓ i |x i )π ref (a w i |x i ) +y i ξ π i i +C off o ,(18) whereC off def = βηE x∼ρ,a∼π base (·|x) logπ ref (a|x) is a constant independent ofπ, and we use the reward- induced policy spaceΠ R def = π r : r ∈ R since the optimal policy isπ r for some rewardrbased on Proposition 1. Note that suchΠ R is sufficiently general to admit any parameterized policyπ θ since by definingR =r π θ : θ ∈ Θ, we have Π R =π θ : θ ∈ Θ based on Lemma 3. Remark: Our proposed offline DPO-COV objective(18)simultaneously tackles Corruption, Overoptimization and Verbosity issues. Corruption is modeled by the noise termξ π = [ξ π 1 ,...,ξ π N ] which becomes sparser as the hyperparameterλ≥ 0increases, andξ π = 0whenλ≥ 1. Overoptimization is tackled by the pessimistic regularizer−βηE x∼ρ,a∼π base (·|x) logπ(a|x) which helps to increaseπ(a|x)for in-distribution samples (x,a)well covered byπ base . Verbosity is penalized by the length regularizersω|a w i |,ω|a ℓ i |. Whenλ≥ 1and η = ω = 0, our above offline DPO-COV objective (18) reduces to the vanilla DPO objective (5). We formally establish the equivalence between our offline RLHF-COV objective(12)and offline DPO- COV objective(18)in the following Proposition 2, which implies the equivalence between the vanilla RLHF and DPO algorithms as a special case when λ≥ 1 and η = ω = 0. Proposition 2. A policyπ ∈ Πis optimal for the offline DPO-COV objective(18)if and only if there exist r ∈R,ξ ∈ R N such that(π,r,ξ)is optimal for the offline RLHF-COV objective(12). In this case,ξ = ξ π , and for any x∈X , there exists U π (x)∈ R such that r(x,·) = r π (x,·) + U π (x). As suggested by (Liu et al., 2024c; Yang et al., 2024) and discussed in Section 3.3, in the DPO-COV objective(18), we can takeπ base (·|x)as the distribution of the preferable responsesa w i givenx i = x under Assumption 1, and then adopt the simple stochastic approximationE x∼ρ,a∼π base (·|x) logπ(a|x) ≈ 1 N P N i=1 logπ(a w i |x i ). This yields our fully stochastic offline DPO-COV algorithm as Algorithm 1, which only requires to solve the policy optimization problem that is almost as simple as the vanilla DPO objective (5). Algorithm 1 Offline DPO-COV Algorithm 1: Inputs: Hyperparameters β,η,ω,λ≥ 0, offline datax i ,a w i ,a ℓ i N i=1 , reference policy π ref . 2: Output: Obtain policy bπ via the following practical offline DPO-COV objective. min π∈Π R ψ N (π) def = 1 N N X i=1 n λ|ξ π i |−βη logπ(a w i |x)−logσ h ω(|a w i |−|a ℓ i |) +β log π(a w i |x i )π ref (a ℓ i |x i ) π(a ℓ i |x i )π ref (a w i |x i ) +y i ξ π i io ,(19) where ξ π i is defined by Eq. (17). 3.3 Generalization Analysis of Offline DPO-COV While the policyπis trained from the offline dataD, the ultimate goal is to makeπgeneralize well to all possible promptsx∼ ρ. Specifically, we define the following length-regularized value function which 7 characterizes the generalization ability of the policyπas a trade-off among the true reward valuer ∗ (response quality), the length of the generated response a, and the policy’s distance to π ref . J β,ω (π) :=E x∼ρ,a∼π(·|x) h r ∗ (x,a)− ω|a|− βKL π(·|x) π ref (·|x) i .(20) To analyze the generalization error of the policybπobtained from Algorithm 1, we make the standard assumptions below. Assumption 2 (Realizable and Bounded Reward (Zhu et al., 2023; Zhan et al., 2024; Cen et al., 2024; Ji et al., 2024; Liu et al., 2024c)). The reward model setRincludes the true reward modelr ∗ , that is,r ∗ ∈R. Also, there exists a constant R∈ (0, +∞) such that for any x∈X , a∈A and r ∈R, we have r(x,a)∈ [0,R]. Assumption 3 (Offline Data Coverage (Zhan et al., 2024; Ji et al., 2024; Liu et al., 2024c)). There exists a constantG D ∈ (0, +∞)called offline coverage coefficient, such that the choice of the baseline policyπ base satisfies the following coverage property for all r ∈R. E x∼ρ,a∼π r ∗ (·|x),a ′ ∼π base (·|x) r ∗ (x,a)−r ∗ (x,a ′ )−r(x,a)+r(x,a ′ ) ≤ G D E r ,(21) whereE r def = E D r ∗ (x 1 ,a w 1 )−r ∗ (x 1 ,a ℓ 1 )−r(x 1 ,a w 1 )+r(x 1 ,a ℓ 1 ) 2 1/2 with the offline data samplex 1 ,a w 1 ,a ℓ 1 generated via Assumption 1. The offline coverage coefficientG D above describes how well the offline dataDcovers the responses fromπ base and the true optimal policyπ r ∗ ∈ arg max π∈Π J β,ω (π). Algorithm 1 takesπ base (·|x)as the distribution of the preferable responses a w i given x i = x, which is well covered byD. Theorem 1. Suppose Assumptions 1-3 hold andRis a convex set. For anyδ ∈ (0, 1), select hyperparameters λ∈ [σ(R), 1],η = 2 √ ∥ξ ∗ ∥ 1 +5 log[|N 1/N (R)|/δ] √ N (3+e R ) . Then, the policyeπfrom the offline DPO-COV objective(18) has the following generalization error rate with probability at least 1− δ. max π∈Π J β,ω (π)− J β,ω (eπ)≤ (G 2 D +1)(3+e R ) √ N q ∥ξ ∗ ∥ 1 +5 log[|N 1/N (R)|/δ],(22) whereN 1/N (R)is a(1/N )-cover ofR, that is, for anyr ∈ R, there existsr † ∈ N 1/N (R)satisfying ∥r † − r∥ ∞ ≤ 1/N . Comparison with Existing Works. Note that|N 1/N (R)| ≤ O[(RN ) |X||A| ]sinceR ⊂ [0,R] |X||A| by Assumption 2. Hence, as long as∥ξ ∗ ∥ 1 ≤O[log(N )](much weaker than Assumption 4.2 of (Bukharin et al., 2024) that there exist constants c 0 ,c ∞ > 0 such that ξ ∗ has at most c 0 nonzero entries and they range in[−c ∞ ,c ∞ ]), the generalization error rate(22)has the order ofO[log(N )/ √ N ]. This rate matches the existing error rates of the offline pessimistic DPO-type algorithms (Liu et al., 2024c; Cen et al., 2024; Ji et al., 2024) up to logarithm, in the simple case with clean data (λ≥ 1) and without length regularization (ω = 0). This implies that our offline DPO-COV algorithm provably mitigates Overoptimization. In addition, Theorem 1 also for the first time extends to the corrupted data and the length-regularized generalization error, which shows that our Algorithm 1 also mitigates Corruption and Verbosity. In particular, to mitigate Corruption, we use novel techniques below to bound the noise terms in the generalization error of the learned policy, whereas Bukharin et al. (2024) only analyzes the estimation error of the reward and noise, but not that of the policy. Technical Novelty. The proof logic of Theorem 1 is inspired from that of (Liu et al., 2024c), but our proof requires novel techniques to bound the effects of the true noiseξ ∗ and estimated noiseξ π . To elaborate, theξ π is analyzed by our proposed Lemma 4, such that the error boundσ(R)|ξ r,i |can later be canceled out by the regularizer−λ|ξ r,i |when bounding the MLE error in Lemma 8. Next, we bound the distance between the true data distribution under(r ∗ ,ξ ∗ )and the noiseless data distribution under the estimatedrandξ = 0 (see (c) of Eq.(43)) by concentration inequality. Then we boundξ ∗ by our proposed Lemma 5 which has a different form from Lemma 4 used for bounding ξ π . 8 4 Our Online DPO-COV Algorithm Compared with offline RLHF and DPO-type algorithms which use precollected offline data, the online algorithms improve the data coverage and the quality of the trained policy (Cen et al., 2024; Dong et al., 2024; Xu et al., 2024; Ye et al., 2024; Guo et al., 2024) at the computation cost of collecting the online preference data in the training process (Zhan et al., 2024; Ji et al., 2024; Huang et al., 2024; Mandal et al., 2024). Therefore, online and offline algorithms have different advantages, so both are important. In this section, we will derive our online RLHF-COV objective and online DPO-COV algorithm, and provide the generalization analysis result of our DPO-COV algorithm. At eacht-th iteration of our online algorithm, we use the current policyπ t to obtain thet-th sample by x t ∼ ρ,a (−1) t ∼ π ref (·|x t ),a (1) t ∼ π t (·|x t ), and the labely t is obtained from a stochastic oracle (such as GPT-4) assumed to follow the corrupted preference model(7). We propose the following online RLHF-COV objective to train the next policy π t+1 on the online datax i ,a (−1) i ,a (1) i ,y i t i=1 . (Online RLHF-COV): π t+1 ∈ arg min π∈Π n min r∈R,ξ (t) ∈R t L t,λ (r,ξ (t) )−ηV β,ω (π,r) o ,(23) whereξ (t) = [ξ 1 ,...,ξ t ]denotes the noise. The above online RLHF-COV objective is similar to the offline RLHF-COV objective(12)with the major difference that they tackle overoptimization in seemingly opposite ways. The offline RLHF-COV objective(12)(i.e.,min r∈R,ξ∈R N [L N,λ (r,ξ)+η max π∈Π V β,ω (π,r)]) uses the pessimistic term+η max π∈Π V β,ω (π,r)to discourage LLM from generating out-of-distribution samples. In contrast, inspired by (Cen et al., 2024), our above online RLHF-COV objective (i.e.,min r∈R,ξ∈R N [L t,λ (r,ξ)− η max π∈Π V β,ω (π,r)] ) uses the sign-flipped optimistic term−η max π∈Π V β,ω (π,r)to encourage LLM to collect out-of-distribution samples to enrich the diversity of the online data to improve policy optimization. Similar to the offline DPO-COV objective (18), we obtain our online DPO-COV objective as follows. (Online DPO-COV): π t+1 ∈ arg min π∈Π R n L t,λ (r π ,ξ π,(t) )− ηV β,ω (π r π ,r π ) = βηE x∼ρ,a∼π base (·|x) logπ(a|x) + 1 t t X i=1 h λ|ξ π i |−logσ ω(|a w i |−|a ℓ i |)+β log π(a w i |x i )π ref (a ℓ i |x i ) π(a ℓ i |x i )π ref (a w i |x i ) + y i ξ π i i + C on o ,(24) whereξ π,(t) def = [ξ π 1 ,...,ξ π t ]is given by Eq.(17)andC on =−βηE x∼ρ,a∼π base (·|x) [logπ ref (a|x)]is a constant independent ofπ. Similar to Proposition 2, we can show that the online RLHF-COV objective(23)and the online DPO-COV objective (24) are equivalent as follows. Proposition 3. A policyπ ∈ Πis optimal for the online DPO-COV objective(24)if and only if there exist r ∈R,ξ ∈ R N such that(π,r,ξ)is optimal for the offline RLHF-COV objective(23). In this case,ξ = ξ π and for any x∈X , there exists U π (x)∈ R such that r(x,·) = r π (x,·) + U π (x). Inspired by (Xie et al., 2024), we selectπ base = π ref and use its generated samplesa (−1) i t i=1 to approximate the expectation in the above online DPO-COV objective. This yields our fully stochastic online DPO-COV algorithm (Algorithm 2), which is also almost as simple to implement as the online vanilla DPO algorithm (Guo et al., 2024) (also Algorithm 2 with η = ω = 0 and λ = 1). To analyze the generalization error of Algorithm 2, define the following coverability coefficient (Xie et al., 2024), which ensures that there exists at least one policyν ∈ Π R with good coverage over the responses generated by any policy π ∈ Π R . G on def = inf ν∈Π R sup x∈X,a∈A,π∈Π R π(a|x) ν(a|x) .(26) 9 Algorithm 2 Online DPO-COV Algorithm 1: Inputs: β,η,ω,λ > 0, reference policy π ref , inital policy π 0 . 2: for Iterations t = 1,...,T do 3:Generate thet-th sample byx t ∼ ρ,a (−1) t ∼ π ref (·|x t ),a (1) t ∼ π t (·|x t ), and labely t from a certain stochastic oracle assumed to follow the corrupted preference model (7). 4:Obtain π t+1 by solving the following stochastic online DPO-COV objective (25). min π∈Π R φ t (π) = 1 t t X i=1 n λ|ξ π i | + βη logπ(a (−1) i |x i )− logσ h ω(|a w i |−|a ℓ i |) + β log π(a w i |x i )π ref (a ℓ i |x i ) π(a ℓ i |x i )π ref (a w i |x i ) + y i ξ π i io ,(25) 5: end for 6: Output: π b T where b T ∼ Uniform(2, 3,...,T,T + 1). Theorem 2. Under Assumption 2 and for anyδ ∈ (0, 1), select hyperparametersλ ∈ [σ(R), 1],η = √ log[4TN 1/T (R)/δ]+∥ξ ∗ ∥ 1 (3+e R ) √ TG on whereξ ∗ = [ξ ∗ 1 ,...,ξ ∗ T ] . Then the output policyπ b T of Algorithm 2 satisfies the following generalization error rate with probability at least 1− δ. max π∈Π J β,ω (π)− E J β,ω (π b T ) ≤ 37(3 + e R )(logT ) r G on T h log 4T|N 1/T (R)| δ +∥ξ ∗ ∥ 1 i .(27) Remark: Theorem 2 above demonstrates that our online DPO-COV algorithm can simultaneously mitigate the Corruption, Overoptimization and Verbosity issues. When∥ξ ∗ ∥ 1 ≤ O(logT ), the above generalization error rate is e O(1/ √ T ), which also matches the existing results of the online optimistic DPO-type algorithms (Xie et al., 2024; Cen et al., 2024) up to logarithm. Technical Novelty. Similar to the proof of Theorem 1, we also use the novel bounds on the effect of the estimated and true noise terms, which are obtained in Lemmas 4 and 5 respectively. 5 Experiments on the Offline Argilla Data In this section, we conduct experiments to compare our offline DPO-COV algorithm with its offline popular special cases including robust DPO algorithm (Bukharin et al., 2024) that only tackles Corruption, pessimistic DPO algorithm (Liu et al., 2024c) that only tackles Overoptimization, length regularized DPO algorithm (Park et al., 2024) that only tackles Verbosity, and the vanilla DPO (Rafailov et al., 2023). We select the offline preference datasetDto be Argilla-DPO-Mix-7K (Argill, 2024), andπ ref to be zephyr-7b-gemma- sft-v0.1 (HuggingFaceH4, 2024). For each algorithm, we fixβ = 0.05and perform grid search on the other hyperparameters over a holdout validation set of the preference dataset. We compare the length- controlled win rates (LC-win rates (Dubois et al., 2024)) ofπ ref and that of the models obtained by the above algorithms against the model GPT-4 Preview (11/06) (OpenAI, 2024). We summarize the LC-win rates and the hyperparameter values in Table 1, which indicates that our offline DPO-COV algorithm with all three components activated achieves the highest LC win rates. Therefore, it is important to tackle the Corruption, Overoptimization and Verbosity issues simultaneously. 10 Table 1: Hyperparameter Values and LC-win Rates of Offline DPO-type Algorithms Algorithmsλ ηωLC-win rates Our DPO-COV (all 3 components activated)0.70.00050.00057.61% Robust DPO (Corruption only)0.1007.04% Pessimistic DPO (Overoptimization only)10.00505.50% Length-regularized DPO (Verbosity only)100.00057.30% Vanilla DPO1006.29% Reference model π ref ---4.92% 6 Conclusion We proposed RLHF-COV and DPO-COV algorithms that simultaneously mitigate the Corruption, Overoptimization and Verbosity issues, in both offline and online settings. This ability is theoretically proved by length- regularized generalization analysis on corrupted data, and empirically demonstrated. Limitations: This work focuses on simple question and answer, and in the future could be extended to dialogue, reasoning and multimodality, etc. Also, our algorithms cannot totally remove hallucinations that may yield false or unsafe information disclosure, which could be tackled in the future. References Argill (2024). Argilla-dpo-mix-7k.https://huggingface.co/datasets/argilla/dpo-mix- 7k. Accessed: 2024-09-30. Azar, M. G., Guo, Z. D., Piot, B., Munos, R., Rowland, M., Valko, M., and Calandriello, D. (2024). A general theoretical paradigm to understand learning from human preferences. In International Conference on Artificial Intelligence and Statistics (AISTATS), pages 4447–4455. Bai, C., Wang, L., Yang, Z., Deng, Z.-H., Garg, A., Liu, P., and Wang, Z. (2022a). Pessimistic bootstrap- ping for uncertainty-driven offline reinforcement learning. In International Conference on Learning Representations (ICLR). Bai, Y., Jones, A., Ndousse, K., Askell, A., Chen, A., DasSarma, N., Drain, D., Fort, S., Ganguli, D., Henighan, T., et al. (2022b). Training a helpful and harmless assistant with reinforcement learning from human feedback. ArXiv:2204.05862. Bradley, R. A. and Terry, M. E. (1952). Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika, 39(3/4):324–345. Bukharin, A., Hong, I., Jiang, H., Zhang, Q., Zhang, Z., and Zhao, T. (2024). Robust reinforcement learning from corrupted human feedback. ArXiv:2406.15568. Cao, Y., Ivanovic, B., Xiao, C., and Pavone, M. (2024). Reinforcement learning with human feedback for realistic traffic simulation. In IEEE International Conference on Robotics and Automation (ICRA), pages 14428–14434. IEEE. Casper, S., Davies, X., Shi, C., Gilbert, T. K., Scheurer, J., Rando, J., Freedman, R., Korbak, T., Lindner, D., Freire, P., et al. (2023). Open problems and fundamental limitations of reinforcement learning from human feedback. Transactions on Machine Learning Research. 11 Cen, S., Mei, J., Goshvadi, K., Dai, H., Yang, T., Yang, S., Schuurmans, D., Chi, Y., and Dai, B. (2024). Value- incentivized preference optimization: A unified approach to online and offline rlhf. ArXiv:2405.19320. Chakraborty, S., Qiu, J., Yuan, H., Koppel, A., Huang, F., Manocha, D., Bedi, A. S., and Wang, M. (2024). Maxmin-rlhf: Towards equitable alignment of large language models with diverse human preferences. ArXiv:2402.08925. Chen, L., Zhu, C., Chen, J., Soselia, D., Zhou, T., Goldstein, T., Huang, H., Shoeybi, M., and Catanzaro, B. (2024). Odin: Disentangled reward mitigates hacking in rlhf. In International Conference on Machine Learning (ICML). Cheng, C.-A., Xie, T., Jiang, N., and Agarwal, A. (2022). Adversarially trained actor critic for offline reinforcement learning. In International Conference on Machine Learning (ICML), pages 3852–3878. PMLR. Cheng, J., Xiong, G., Dai, X., Miao, Q., Lv, Y., and Wang, F.-Y. (2024). Rime: Robust preference-based reinforcement learning with noisy preferences. ArXiv:2402.17257. Christiano, P. F., Leike, J., Brown, T. B., Martic, M., Legg, S., and Amodei, D. (2017). Deep reinforcement learning from human preferences. In International Conference on Neural Information Processing Systems (Neurips), pages 4302–4310. Clark, P., Cowhey, I., Etzioni, O., Khot, T., Sabharwal, A., Schoenick, C., and Tafjord, O. (2018). Think you have solved question answering? try arc, the ai2 reasoning challenge. ArXiv:1803.05457. Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J., Nakano, R., et al. (2021). Training verifiers to solve math word problems. ArXiv:2110.14168. Coste, T., Anwar, U., Kirk, R., and Krueger, D. (2024). Reward model ensembles help mitigate overoptimiza- tion. In International Conference on Learning Representations (ICLR). Dong, H., Xiong, W., Pang, B., Wang, H., Zhao, H., Zhou, Y., Jiang, N., Sahoo, D., Xiong, C., and Zhang, T. (2024). Rlhf workflow: From reward modeling to online rlhf. ArXiv:2405.07863. Dubois, Y., Galambosi, B., Liang, P., and Hashimoto, T. B. (2024). Length-controlled alpacaeval: A simple way to debias automatic evaluators. Eisenstein, J., Nagpal, C., Agarwal, A., Beirami, A., D’Amour, A. N., Dvijotham, K. D., Fisch, A., Heller, K. A., Pfohl, S. R., Ramachandran, D., Shaw, P., and Berant, J. (2024). Helping or herding? reward model ensembles mitigate but do not eliminate reward hacking. In First Conference on Language Modeling (COLM). Ethayarajh, K., Xu, W., Muennighoff, N., Jurafsky, D., and Kiela, D. (2024). Kto: Model alignment as prospect theoretic optimization. ArXiv:2402.01306. Fan, K. (1953). Minimax theorems. Proceedings of the National Academy of Sciences, 39(1):42–47. Fisch, A., Eisenstein, J., Zayats, V., Agarwal, A., Beirami, A., Nagpal, C., Shaw, P., and Berant, J. (2024). Robust preference optimization through reward model distillation. ArXiv:2405.19316. Gao, L., Schulman, J., and Hilton, J. (2023). Scaling laws for reward model overoptimization. In International Conference on Machine Learning (ICML), pages 10835–10866. 12 Gao, L., Tow, J., Abbasi, B., Biderman, S., Black, S., DiPofi, A., Foster, C., Golding, L., Hsu, J., Le Noac’h, A., Li, H., McDonell, K., Muennighoff, N., Ociepa, C., Phang, J., Reynolds, L., Schoelkopf, H., Skowron, A., Sutawika, L., Tang, E., Thite, A., Wang, B., Wang, K., and Zou, A. (2024a). A framework for few-shot language model evaluation. https://zenodo.org/records/12608602. Gao, Y., Alon, D., and Metzler, D. (2024b). Impact of preference noise on the alignment performance of generative language models. In First Conference on Language Modeling (CoLM). Guo, S., Zhang, B., Liu, T., Liu, T., Khalman, M., Llinares, F., Rame, A., Mesnard, T., Zhao, Y., Piot, B., et al. (2024). Direct language model alignment from online ai feedback. ArXiv:2402.04792. Harsha, P. (2011). Lecture note 12 on communication complexity. url:https://w.tcs.tifr.res .in/~prahladh/teaching/2011-12/comm/lectures/l12.pdf. Hu, E. J., Shen, Y., Wallis, P., Allen-Zhu, Z., Li, Y., Wang, S., Wang, L., and Chen, W. (2021). Lora: Low-rank adaptation of large language models. Huang, A., Zhan, W., Xie, T., Lee, J. D., Sun, W., Krishnamurthy, A., and Foster, D. J. (2024). Correcting the mythos of kl-regularization: Direct alignment without overparameterization via chi-squared preference optimization. ArXiv:2407.13399. HuggingFaceH4 (2024). zephyr-7b-gemma-sft-v0.1.https://huggingface.co/HuggingFaceH4 /zephyr-7b-gemma-sft-v0.1. Accessed: 2024-09-30. Ji, X., Kulkarni, S., Wang, M., and Xie, T. (2024). Self-play with adversarial critic: Provable and scalable offline alignment for language models. ArXiv:2406.04274. Jin, Y., Yang, Z., and Wang, Z. (2021). Is pessimism provably efficient for offline rl? In International Conference on Machine Learning (ICML), pages 5084–5096. Liang, Z., Yuan, Y., Gu, S., Chen, B., Hang, T., Li, J., and Zheng, L. (2024). Step-aware preference optimization: Aligning preference with denoising performance at each step. ArXiv:2406.04314. Liu, J., Zhou, Z., Liu, J., Bu, X., Yang, C., Zhong, H.-S., and Ouyang, W. (2024a). Iterative length- regularized direct preference optimization: A case study on improving 7b language models to gpt-4 level. ArXiv:2406.11817. Liu, Q., Weisz, G., György, A., Jin, C., and Szepesvári, C. (2023a). Optimistic natural policy gradient: a simple efficient policy optimization framework for online rl. In International Conference on Neural Information Processing Systems (Neurips), pages 3560–3577. Liu, Y., Zhang, K., Li, Y., Yan, Z., Gao, C., Chen, R., Yuan, Z., Huang, Y., Sun, H., Gao, J., et al. (2024b). Sora: A review on background, technology, limitations, and opportunities of large vision models. ArXiv:2402.17177. Liu, Z., Lu, M., Xiong, W., Zhong, H., Hu, H., Zhang, S., Zheng, S., Yang, Z., and Wang, Z. (2023b). Maximize to explore: one objective function fusing estimation, planning, and exploration. In International Conference on Neural Information Processing Systems (Neurips), pages 22151–22165. Liu, Z., Lu, M., Zhang, S., Liu, B., Guo, H., Yang, Y., Blanchet, J., and Wang, Z. (2024c). Provably mitigating overoptimization in rlhf: Your sft loss is implicitly an adversarial regularizer. ArXiv:2405.16436. Loshchilov, I. and Hutter, F. (2017). Decoupled weight decay regularization. 13 Mandal, D., Nika, A., Kamalaruban, P., Singla, A., and Radanovi ́ c, G. (2024). Corruption robust offline reinforcement learning with human feedback. ArXiv:2402.06734. Meng, Y., Xia, M., and Chen, D. (2024). Simpo: Simple preference optimization with a reference-free reward. ArXiv:2405.14734. Moskovitz, T., Singh, A. K., Strouse, D., Sandholm, T., Salakhutdinov, R., Dragan, A., and McAleer, S. M. (2024). Confronting reward model overoptimization with constrained rlhf. In International Conference on Learning Representations (ICLR). OpenAI (2024). Gpt-4 technical report. Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Gray, A., et al. (2022). Training language models to follow instructions with human feedback. In International Conference on Neural Information Processing Systems (Neurips). Park, R., Rafailov, R., Ermon, S., and Finn, C. (2024). Disentangling length from quality in direct preference optimization. ArXiv:2403.19159. Rafailov, R., Sharma, A., Mitchell, E., Manning, C. D., Ermon, S., and Finn, C. (2023). Direct preference optimization: Your language model is secretly a reward model. In International Conference on Neural Information Processing Systems (Neurips), volume 36. Rame, A., Vieillard, N., Hussenot, L., Dadashi, R., Cideron, G., Bachem, O., and Ferret, J. (2024). Warm: On the benefits of weight averaged reward models. In International Conference on Machine Learning (ICML). Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S. (2021). Bridging offline reinforcement learning and imitation learning: a tale of pessimism. In International Conference on Neural Information Processing Systems (Neurips), pages 11702–11716. Rein, D., Hou, B. L., Stickland, A. C., Petty, J., Pang, R. Y., Dirani, J., Michael, J., and Bowman, S. R. (2024). Gpqa: A graduate-level google-proof q&a benchmark. In First Conference on Language Modeling. RLHFlow (2024). pair-preference-model-llama3-8b.https://huggingface.co/RLHFlow/pair- preference-model-LLaMA3-8B. Accessed: 2024-09-30. Shen, W., Zheng, R., Zhan, W., Zhao, J., Dou, S., Gui, T., Zhang, Q., and Huang, X.-J. (2023). Loose lips sink ships: Mitigating length bias in reinforcement learning from human feedback. In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 2859–2873. Singhal, P., Goyal, T., Xu, J., and Durrett, G. (2023). A long way to go: Investigating length correlations in rlhf. ArXiv:2310.03716. Tversky, A. and Kahneman, D. (1992). Advances in prospect theory: Cumulative representation of uncertainty. Journal of Risk and uncertainty, 5:297–323. Wallace, B., Dang, M., Rafailov, R., Zhou, L., Lou, A., Purushwalkam, S., Ermon, S., Xiong, C., Joty, S., and Naik, N. (2023). Diffusion model alignment using direct preference optimization. AXiv:2311.12908. Wang, Y., Liu, L., Wang, M., and Xiong, X. (2024). Reinforcement learning from human feedback for lane changing of autonomous vehicles in mixed traffic. ArXiv:2408.04447. Wang, Y., Liu, Q., and Jin, C. (2023). Is rlhf more difficult than standard rl? ArXiv, abs/2306.14111. 14 Wei, C.-Y., Hong, Y.-T., and Lu, C.-J. (2017). Online reinforcement learning in stochastic games. In International Conference on Neural Information Processing Systems (Neurips), pages 4994–5004. Xie, T., Cheng, C. A., Jiang, N., Mineiro, P., and Agarwal, A. (2021). Bellman-consistent pessimism for offline reinforcement learning. In International Conference on Neural Information Processing Systems (Neurips), pages 6683–6694. Xie, T., Foster, D. J., Krishnamurthy, A., Rosset, C., Awadallah, A., and Rakhlin, A. (2024). Exploratory pref- erence optimization: Harnessing implicit q*-approximation for sample-efficient rlhf. ArXiv:2405.21046. Xiong, W., Dong, H., Ye, C., Wang, Z., Zhong, H., Ji, H., Jiang, N., and Zhang, T. (2024). Iterative preference learning from human feedback: Bridging theory and practice for rlhf under kl-constraint. In International Conference on Machine Learning (ICML). Xu, W., Li, J., Wang, W. Y., and Li, L. (2024). Bpo: Supercharging online preference learning by adhering to the proximity of behavior llm. ArXiv:2406.12168. Yang, R., Ding, R., Lin, Y., Zhang, H., and Zhang, T. (2024). Regularizing hidden states enables learning generalizable reward model for llms. ArXiv:2406.10216. Ye, C., Xiong, W., Zhang, Y., Jiang, N., and Zhang, T. (2024). Online iterative reinforcement learning from human feedback with general preference model. ArXiv:2402.07314. Zhai, Y., Zhang, H., Lei, Y., Yu, Y., Xu, K., Feng, D., Ding, B., and Wang, H. (2023). Uncertainty-penalized reinforcement learning from human feedback with diverse reward lora ensembles. ArXiv:2401.00243. Zhan, W., Uehara, M., Kallus, N., Lee, J. D., and Sun, W. (2024). Provable offline preference-based reinforcement learning. In International Conference on Learning Representations (ICLR). Zhang, S., Yu, D., Sharma, H., Yang, Z., Wang, S., Hassan, H., and Wang, Z. (2024). Self-exploring language models: Active preference elicitation for online alignment. ArXiv:2405.19332. Zhang, T. (2023). Mathematical analysis of machine learning algorithms. Cambridge University Press. Zhong, H. and Zhang, T. (2023). A theoretical analysis of optimistic proximal policy optimization in linear markov decision processes. In International Conference on Neural Information Processing Systems (Neurips), pages 73666–73690. Zhu, B., Jordan, M., and Jiao, J. (2023). Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. In International Conference on Machine Learning (ICML), pages 43037–43067. Zhu, B., Jordan, M., and Jiao, J. (2024). Iterative data smoothing: Mitigating reward overfitting and overoptimization in rlhf. In International Conference on Machine Learning (ICML). 15 Appendix Table of Contents A Experiments16 A.1 Experiments on the Offline Argilla Data . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 A.2 Experiment on Math and Reasoning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 A.3 Experiment on Online Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 B Supporting Lemmas18 C Proof of Proposition 130 D Proof of Proposition 231 E Proof of Proposition 332 F Proof of Theorem 132 G Proof of Theorem 233 A Experiments A.1 Experiments on the Offline Argilla Data In this section, we will compare the following offline DPO-type algorithms on offline datasets. 1. Our offline DPO-COV algorithm with all the three modules activated (Corruption, Overoptimization, Verbosity): This is Algorithm 1 with η,ω > 0 and λ∈ (0, 1). 2. Offline robust DPO algorithm (Bukharin et al., 2024): This is a special case of Algorithm 1 with η = ω = 0 and λ∈ (0, 1), which only tackles Corruption. 3.Offline pessimistic DPO algorithm (Liu et al., 2024c): This is a special case of Algorithm 1 withη > 0, ω = 0 and λ = 1, which only tackles Overoptimization. 4. Offline length regularized DPO algorithm (Park et al., 2024): This is a special case of Algorithm 1 with η = 0, ω > 0 and λ = 1, which only tackles Verbosity. 5. Offline vanilla DPO (Rafailov et al., 2023): Algorithm 1 with η = ω = 0 and λ = 1. We select the preference datasetDto be Argilla-DPO-Mix-7K (Argill, 2024), andπ ref to be zephyr- 7b-gemma-sft-v0.1 (HuggingFaceH4, 2024), which is a fine-tuned version of gemma-7b on the Deita dataset (Wang et al., 2023). Then we apply LoRA (Hu et al., 2021) and two epochs of the AdamW optimizer (Loshchilov and Hutter, 2017) with learning rate5× 10 −7 to the objective(19). For each algorithm, we fixβ = 0.05and perform grid search on the other hyperparameters over a holdout validation set. We obtain the length-controlled win rates (a.k.a. LC-win rates, defined in AlpacaEval 2.0 (Dubois et al., 2024)) ofπ ref and that of the models obtained by the above algorithms against the model GPT-4 Preview (11/06) (OpenAI, 2024), as well as the output length averaged over the AlpacaEval 2.0 (Dubois et al., 2024) data. We 16 summarize these results and the hyperparameter values of all the algorithms in Table 2, which indicates that our offline DPO-COV algorithm with all three components activated achieves the highest LC win rates, and that all these algorithms yield comparable output lengths. Table 2: Hyperparameters and results of offline DPO-type algorithms on the clean Argilla data Algorithmsλ ηωLC-win ratesAvg length Our DPO-COV (all 3 components activated)0.70.00050.00057.61%699.93 Robust DPO (Corruption only)0.1007.04%670.86 Pessimistic DPO (Overoptimization only)10.00505.50%710.61 Length-regularized DPO (Verbosity only)100.00057.30%705.52 Vanilla DPO1006.29%708.69 Reference model π ref ---4.92%747.08 Table 3: Hyperparameters and results of offline DPO-type algorithms on the Argilla data (with 25% corrup- tion) Algorithmsλ ηωLC-win ratesAvg length Our DPO-COV (all 3 components activated)0.70.00050.00056.50%745.54 Robust DPO (Corruption only)0.1006.80%742.77 Pessimistic DPO (Overoptimization only)10.00505.92%745.91 Length-regularized DPO (Verbosity only)100.00056.38%746.79 Vanilla DPO1006.03%742.34 Reference model π ref ---4.92%747.08 Table 4: Experimental Results on Math and Reasoning ModelGSM8KARCARCGPQAGPQA (Easy set)(Challenge set)(Main set)(Diamond set) Our DPO-COV46.7872.5249.3229.9131.31 Robust DPO46.2572.1447.3527.6829.29 Pessimistic DPO45.1972.1446.1623.8828.39 Length-reg DPO44.5072.3146.1625.2229.29 Vanilla DPO45.2671.8946.5026.1234.85 Reference Model42.3871.7245.1428.3526.26 To further evaluate our algorithm’s robustness to data corruption, we change the labels of randomly selected 25% samples from the Argilla data and implement these algorithms. Similar to Table 2, we summarize the results and hyperparameters on this corrupted data in Table 3, which shows that both our DPO-COV and the robust DPO are more robust to the corruption than the other non-robust DPO variants, and the outputs of these models again have comparable lengths on the corrupted data. A.2 Experiment on Math and Reasoning We also compare our Algorithm 1 with other offline DPO variants over datasets of math and reasoning tasks, including Grade School Math 8K (GSM8K) (Cobbe et al., 2021), AI2 Reasoning Challenge (ARC) 17 Table 5: Hyperparameter Values and LC-win Rates of Online DPO-type Algorithms Algorithmsλ ηωLC-win rates Our DPO-COV (all 3 components activated)0.70.00050.00057.87% Robust DPO (Corruption only)0.1007.03% Optimistic DPO (Overoptimization only)10.00506.23% Length-regularized DPO (Verbosity only)100.00056.19% Vanilla DPO1006.58% Reference model π ref ---4.92% tasks (both easy and challenge sets) (Clark et al., 2018), GPQA (both main and diamond sets) (Rein et al., 2024). We run the benchmark test with (Gao et al., 2024a) and report the accuracies in Table 4. The model hyper-parameters are the same as in Table 2. The results shown in Table 4 indicate that our DPO-COV algorithm outperforms the other variants also on most of the math and reasoning tasks. A.3 Experiment on Online Data Similar to the offline experiments in Section A.1, we compare important special cases of Algorithm 2, including our online DPO-COV with all 3 components activated, the online variant of the robust DPO algorithm (Bukharin et al., 2024), online optimistic DPO algorithm (named XPO in (Xie et al., 2024)), online length regularized DPO algorithm (Liu et al., 2024a) and online vanilla DPO algorithm (using DPO objective in (Guo et al., 2024)). We use zephyr-7b-gemma-sft-v0.1 (HuggingFaceH4, 2024) as the reference model π ref and the initial modelπ 0 . Each algorithm is trained withβ = 0.05andT = 3iterations. In each iteration, we generate the online labelsy t from pair-preference-model-LLaMA3-8B (RLHFlow, 2024), and combine the online data with 50% of the preference dataset of Argilla-DPO-Mix-7K (Argill, 2024). Then we apply LoRA (Hu et al., 2021) and two epochs of the AdamW optimizer (Loshchilov and Hutter, 2017) with stepsize 5× 10 −7 to the objective(25). On AlpacaEval 2.0 (Dubois et al., 2024), we compare the LC-win rates ofπ ref and that of the models obtained by the above algorithms against the model GPT-4 Preview (11/06) (OpenAI, 2024). Again, the results in Table 5 indicate that our online DPO-COV algorithm with all three components activated achieves the highest length-controlled win rates. B Supporting Lemmas Lemma 1. For any A∈ (0,∞) and z 1 ,z 2 ∈ [−R,R], the following inequality holds. |z 1 − z 2 | 3 + e R ≤|σ(z 1 )− σ(z 2 )|≤ 1 4 |z 1 − z 2 |.(28) Remark: Our bound(28)is strictly tighter than |z 1 −z 2 | (1+e R ) 2 ≤ |σ(z 1 )− σ(z 2 )| ≤ |z 1 − z 2 |obtained in Lemma A.2 of (Liu et al., 2024c). Proof. Denote z min = min(z 1 ,z 2 ) and z max = max(z 1 ,z 2 ). Then we have |z 1 − z 2 | = z max − z min , |σ(z 1 )− σ(z 2 )| = σ(z max )− σ(z min ) = Z z max z min σ ′ (z)dz. 18 Hence, it suffices to prove thatσ ′ (v) ∈ 1 3+e R , 1 4 for anyv ∈ [z min ,z max ] ⊂ [−R,R]. Note that for any v ∈ [z min ,z max ]⊂ [−R,R],σ(v)∈ [σ(−R),σ(R)] = [1− σ(R),σ(R)]. Hence, we conclude the proof by the following two bounds. σ ′ (v) = σ(v)[1− σ(v)] = 1 4 − h σ(v)− 1 2 i 2 ≤ 1 4 . σ ′ (v) = 1 4 − h σ(v)− 1 2 i 2 ≥ 1 4 − h σ(R)− 1 2 i 2 =σ(R)[1− σ(R)] = 1 1 + e R e R 1 + e R = 1 (1 + e R )(1 + e −R ) = 1 2 + e R + e −R ≥ 1 3 + e R . Lemma 2. For any x∈X , a 0 ,a 1 ∈A and r ∈R, the following equality holds r π r (x,a 1 )− r π r (x,a 0 ) = r(x,a 1 )− r(x,a 0 ),(29) whereπ r andr π are defined by Eqs.(14)and(16)respectively. Furthermore, under Assumption 2, both sides of the above Eq. (29) range in [−R,R]. Proof. r π r (x,a 1 )− r π r (x,a 0 ) (a) =ω(|a 1 |−|a 0 |) + β log π r (a 1 |x)π ref (a 0 |x) π r (a 0 |x)π ref (a 1 |x) (b) =r(x,a 1 )− r(x,a 0 ), where (a) uses Eq. (16) and (b) uses Eq. (14). Furthermore, under Assumption 2, r(x,a 0 ),r(x,a 1 )∈ [0,R], so r π r (x,a 1 )− r π r (x,a 0 ) = r(x,a 1 )− r(x,a 0 )∈ [−R,R]. Lemma 3. Any policyπ ∈ Πsatisfiesπ = π r π whereπ r andr π are defined by Eqs.(14)and(16)respectively. Furthermore, under Assumption 2, anyπ ∈ Π R def = π r : r ∈R satisfies|r π (x,a 1 )− r π (x,a 0 )|≤ Rfor any x∈X , a 0 ,a 1 ∈A. Proof. Eq. (16) implies that for any x∈X and a∈A, we have π ref (a|x) exp h r π (x,a)− ω|a| β i = π(a|x).(30) 19 Hence, Z r π (x) = X a∈A π ref (a|x) exp h r π (x,a)− ω|a| β i = X a∈A π(a|x) = 1.(31) Therefore, π = π r π can be proved as follows. π r π (a|x) (a) = π ref (a|x) Z r π (x) exp h r π (x,a)− ω|a| β i (b) = π(a|x), where (a) uses Eq. (14) and (b) uses Eqs. (30) and (31). When π ∈ Π R def = π r : r ∈R, there exists r ∈R such that π = π r . Hence, |r π (x,a 1 )− r π (x,a 0 )| (a) = |r π r (x,a 1 )− r π r (x,a 0 )| (b) = |r(x,a 1 )− r(x,a 0 )| (c) ≤ R, where (a) uses π = π r , (b) uses Eq. (29) and (c) uses Assumption 2. Lemma 4. Under Assumption 2, for any r ∈R and ξ r,i defined by Eq. (15), the following inequality holds. logσ[r(x i ,a w i )− r(x i ,a ℓ i ) + y i ξ r,i ]≤ logσ[r(x i ,a w i )− r(x i ,a ℓ i )] + σ(R)|ξ r,i |.(32) For any π ∈ Π R def = π r : r ∈R and ξ π i defined by Eq. (17), the following inequality holds. logσ[r π (x i ,a w i )− r π (x i ,a ℓ i ) + y i ξ π i ]≤ logσ[r π (x i ,a w i )− r π (x i ,a ℓ i )] + σ(R)|ξ π i |.(33) Proof. y i ξ r,i ≥ 0by Eq.(15)sincey i ∈ −1, 1. Then Eq.(32)follows from d dv [logσ(v)] = σ(−v) ≤ σ(R)for anyv ∈ [r(x i ,a w i )−r(x i ,a ℓ i ),r(x i ,a w i )−r(x i ,a ℓ i ) +y i ξ r,i ]⊆ [−R, +∞)where⊂is implied by Assumption 2. Similarly,y i ξ π i ≥ 0by Eq.(17)sincey i ∈ −1, 1. Then Eq.(33)follows from d dv [logσ(v)] = σ(−v)≤ σ(R)for anyv ∈ [r π (x i ,a w i )− r π (x i ,a ℓ i ),r π (x i ,a w i )− r π (x i ,a ℓ i ) + y i ξ π i ]⊆ [−R, +∞)where ⊂ is implied by Lemma 3. Lemma 5. For any ξ i ∈ R and reward models r,r ′ :X ×A→ R, we have σ[r ′ (x i ,a w i )− r ′ (x i ,a ℓ i ) + y i ξ i ]− σ[r(x i ,a w i )− r(x i ,a ℓ i )] 2 ≥ σ[r ′ (x i ,a w i )− r ′ (x i ,a ℓ i )]− σ[r(x i ,a w i )− r(x i ,a ℓ i )] 2 − 1 2 |ξ i |.(34) Proof. Denote A ′ i = r ′ (x i ,a w i )− r ′ (x i ,a ℓ i ) and A i = r(x i ,a w i )− r(x i ,a ℓ i ). Define the following function. f (u) = σ(A ′ i + u)− σ(A i ) 2 .(35) Note that the range of the sigmoid function σ is (0, 1). Hence, for any u∈ R, d du f (u) = 2σ(A ′ i + u) 1− σ(A ′ i + u) σ(A ′ i + u)− σ(A i ) ∈ − 1 2 , 1 2 .(36) Therefore, f (0)− f (y i ξ i )≤|f (y i ξ i )− f (0)|≤ 1 2 |y i ξ i | = 1 2 |ξ i |, which implies Eq. (34). 20 Lemma 6. For anyx∈X,a∈Aandr,r ′ ∈R, the policiesπ r ,π r ′ defined by the analytical solution(14) satisfy log π r ′ (a|x) π r (a|x) ≤ 2∥r ′ − r∥ ∞ β ,(37) where∥r ′ − r∥ ∞ = sup x∈X,a∈A |r ′ (x,a)− r(x,a)|. Proof. Note that for any x∈X , a ′ ∈A and r,r ′ ∈R, we have π ref (a ′ |x) exp r ′ (x,a ′ )−ω|a ′ | β π ref (a ′ |x) exp r(x,a ′ )−ω|a ′ | β = exp h r ′ (x,a ′ )− r(x,a ′ ) β i ∈ exp(−∥r ′ − r∥ ∞ /β), exp(∥r ′ − r∥ ∞ /β) . Therefore, Z r ′ (x) Z r (x) = P a ′ ∈A π ref (a ′ |x) exp r ′ (x,a ′ )−ω|a ′ | β P a ′ ∈A π ref (a ′ |x) exp r(x,a ′ )−ω|a ′ | β ∈ exp(−∥r ′ − r∥ ∞ /β), exp(∥r ′ − r∥ ∞ /β) . As a result, π r ′ (a|x) π r (a|x) = Z r ′ (x) Z r (x) −1 π ref (a ′ |x) exp r ′ (x,a ′ )−ω|a ′ | β π ref (a ′ |x) exp r(x,a ′ )−ω|a ′ | β ∈ exp(−2∥r ′ − r∥ ∞ /β), exp(2∥r ′ − r∥ ∞ /β) (38) which directly implies Eq. (37). We slightly adjust Theorem 13.2 of (Zhang, 2023) as follows, by using filtrationF t =∅(so the conditional expectation becomes the total expectation), replacing−ξ i withZ i , and negating the small probability event. Lemma 7. Consider random variablesZ i N i=0 . For anyδ ∈ (0, 1)andλ ′ > 0, the following inequality holds simultaneously for all n = 1, 2,...,N with probability at least 1− δ. n X i=1 Z i ≤ log(1/δ) λ ′ + 1 λ ′ n X i=1 log E[exp(λ ′ Z i )]. Lemma 8. Fixε > 0,λ∈ [σ(R), 1]andδ ∈ (0, 1). Under Assumption 1, the following bound holds for any r ∈R and ξ r = [ξ r,1 ,...,ξ r,N ]∈ R N (given by Eq. (15)) simultaneously with probability at least 1− δ. L N,λ (r ∗ ,ξ ∗ )−L N,λ (r,ξ r )≤ 2 N h ∥ξ ∗ ∥ 1 + log |N ε (R)| δ i − E 2 r 2(3 + e R ) 2 + 7ε,(39) whereE r := q E D r ∗ (x 1 ,a w 1 )− r ∗ (x 1 ,a ℓ 1 )− r(x 1 ,a w 1 ) + r(x 1 ,a ℓ 1 ) 2 andN ε (R)is a finiteε-cover ofR, that is, for any r ∈R, there exists r † ∈N ε (R) satisfying∥r † − r∥ ∞ ≤ ε. 21 Proof.Based on Assumption 1, given(x i ,a (1) i ,a (−1) i ), the target labely ∈−1, 1as well as the underlying reward r and noise ξ i , the event y i = y occurs with the following probability. p r,ξ i (y|x i ,a (1) i ,a (−1) i ) = ( σ[r(x i ,a (1) i )− r(x i ,a (−1) i ) + ξ i ], y = 1 σ[r(x i ,a (−1) i )− r(x i ,a (1) i )− ξ i ], y =−1. (40) By merging the two cases above, we have p r,ξ i (y i |x i ,a (1) i ,a (−1) i ) = σ[r(x i ,a w i )− r(x i ,a ℓ i ) + y i ξ i ].(41) Define the following random variables for r ∈R and i = 1,...,N . Z i (r) = 1 2 log σ[r(x i ,a w i )− r(x i ,a ℓ i )] σ[r ∗ (x i ,a w i )− r ∗ (x i ,a ℓ i ) + y i ξ ∗ i ] = 1 2 log p r,0 (y i |x i ,a (1) i ,a (−1) i ) p r ∗ ,ξ ∗ i (y i |x i ,a (1) i ,a (−1) i ) .(42) Then the following inequality holds for finitely manyr ∈ N ε (R)simultaneously with probability at least 1− δ. L N,λ (r ∗ ,ξ ∗ )−L N,λ (r,ξ r ) = 1 N N X i=1 logσ[r(x i ,a w i )−r(x i ,a ℓ i )+y i ξ r,i ]−logσ[r ∗ (x i ,a w i )−r ∗ (x i ,a ℓ i )+y i ξ ∗ i ]+λ(|ξ ∗ i |−|ξ r,i |) (a) ≤ 1 N N X i=1 logσ[r(x i ,a w i )− r(x i ,a ℓ i )] + σ(R)|ξ r,i |− logσ[r ∗ (x i ,a w i )− r ∗ (x i ,a ℓ i ) + y i ξ ∗ i ] + λ(|ξ ∗ i |−|ξ r,i |) (b) ≤ 1 N N X i=1 |ξ ∗ i | + 2Z i (r) (c) ≤ 1 N N X i=1 |ξ ∗ i | + 2 log E D exp[Z i (r)] + 2 N log |N ε (R)| δ (d) = 2 N N X i=1 log E D ( E y i ∼p r ∗ ,ξ ∗ i (·|x i ,a (1) i ,a (−1) i ) " v u u t p r,0 (y i |x i ,a (1) i ,a (−1) i ) p r ∗ ,ξ ∗ i (y i |x i ,a (1) i ,a (−1) i ) x i ,a (1) i ,a (−1) i #) + 1 N h ∥ξ ∗ ∥ 1 + 2 log |N ε (R)| δ i (e) ≤ 2 N N X i=1 E D " X y∈−1,1 q p r,0 (y|x i ,a (1) i ,a (−1) i )p r ∗ ,ξ ∗ i (y|x i ,a (1) i ,a (−1) i )− 1 # + 1 N h ∥ξ ∗ ∥ 1 + 2 log |N ε (R)| δ i =− 1 N N X i=1 E D " X y∈−1,1 q p r,0 (y|x i ,a (1) i ,a (−1) i )− q p r ∗ ,ξ ∗ i (y|x i ,a (1) i ,a (−1) i ) 2 # + 1 N h ∥ξ ∗ ∥ 1 + 2 log |N ε (R)| δ i (f ) ≤ − 1 4N N X i=1 E D " X y∈−1,1 p r,0 (y|x i ,a (1) i ,a (−1) i )− p r ∗ ,ξ ∗ i (y|x i ,a (1) i ,a (−1) i ) 2 # 22 + 1 N h ∥ξ ∗ ∥ 1 + 2 log |N ε (R)| δ i (g) = − 1 2N N X i=1 E D σ[r ∗ (x i ,a w i )− r ∗ (x i ,a ℓ i ) + y i ξ ∗ i ]− σ[r(x i ,a w i )− r(x i ,a ℓ i )] 2 + 1 N h ∥ξ ∗ ∥ 1 + 2 log |N ε (R)| δ i (h) ≤ − 1 2N N X i=1 n E D σ[r ∗ (x i ,a w i )− r ∗ (x i ,a ℓ i )]− σ[r(x i ,a w i )− r(x i ,a ℓ i )] 2 − 1 2 |ξ ∗ i | o + 1 N h ∥ξ ∗ ∥ 1 + 2 log |N ε (R)| δ i (i) ≤− 1 2(3 + e R ) 2 E D r ∗ (x 1 ,a w 1 )− r ∗ (x 1 ,a ℓ 1 )− r(x 1 ,a w 1 ) + r(x 1 ,a ℓ 1 ) 2 + 2 N h ∥ξ ∗ ∥ 1 + log |N ε (R)| δ i (j) = 2 N h ∥ξ ∗ ∥ 1 + log |N ε (R)| δ i − E 2 r 2(3 + e R ) 2 ,(43) where (a) uses Eq.(32)from Lemma 4, (b) uses Eq.(42)andσ(R) ≤ λ ≤ 1, (c) denotesE D as the expectation under Assumption 1 and (c) holds for finitely manyr ∈ N ε (R)simultaneously with probability at least1 − δ(by Lemma 7 withλ ′ = 1), (d) uses Eq.(42)and Assumption 1, (e) uses logv ≤ v− 1for anyv > 0, (f) uses Lemma 12.2 of (Harsha, 2011), (g) uses Eq.(41), (h) uses Lemma 5, (i) uses Lemma 1 as well as the fact that theNsamplesx i ,a w i ,a ℓ i N i=1 are i.i.d., (j) denotesE r := q E D r ∗ (x 1 ,a w 1 )− r ∗ (x 1 ,a ℓ 1 )− r(x 1 ,a w 1 ) + r(x 1 ,a ℓ 1 ) 2 . We have proved that with probability at least1− δ, the eventE := Eq.(43)holds for allr ∈ N ε (R) simultaneouslyoccurs. We will extend the range to anyr ∈ R. By the definition of theεcoverN ε (R), there exists at least one r † ∈N ε (R) such that∥r † − r∥ ∞ ≤ ε. Therefore, L N,λ (r,ξ r )−L N,λ (r † ,ξ r † ) (a) = 1 N N X i=1 logσ[r † (x i ,a w i )− r † (x i ,a ℓ i ) + ξ r † ,i ]− logσ[r(x i ,a w i )− r(x i ,a ℓ i ) + ξ r,i ] + λ N (∥ξ r ∥ 1 −∥ξ r † ∥ 1 ) (b) ≤ 1 N N X i=1 h [r † (x i ,a w i )− r † (x i ,a ℓ i ) + ξ r † ,i ]− [r(x i ,a w i )− r(x i ,a ℓ i ) + ξ r,i ] + λ(|ξ r,i |−|ξ r † ,i |) i ≤ 1 N N X i=1 h r † (x i ,a w i )− r(x i ,a w i ) + r(x i ,a ℓ i )− r † (x i ,a ℓ i ) + ξ r † ,i − ξ r,i + λ(|ξ r,i − ξ r † ,i |) i (c) ≤ 1 N N X i=1 h r † (x i ,a w i )− r(x i ,a w i ) + r(x i ,a ℓ i )− r † (x i ,a ℓ i ) + (λ + 1) r(x i ,a ℓ i )− r(x i ,a w i )− [r † (x i ,a ℓ i )− r † (x i ,a w i )] i (d) ≤ 6ε,(44) where (a) uses the definition ofL N,λ given by Eq.(8), (b) uses triangle inequality and d dv [logσ(v)] = σ(−v)∈ [0, 1] for any v ∈R, (c) uses the property that ξ r,i defined by Eq. (15) is a 1-Lipschitz continuous 23 function ofr(x i ,a ℓ i )− r(x i ,a w i ) (sincemax(·, 0)is 1-Lipschitz continuous), (d) uses∥r † − r∥ ∞ ≤ εand λ ≤ 1. Under the eventE, Eq.(43)holds withrreplaced byr + , which along with Eq.(44)implies the following inequality. L N,λ (r ∗ ,ξ ∗ )−L N,λ (r,ξ r ) ≤[L N,λ (r † ,ξ r † )−L N,λ (r,ξ r )] + [L N,λ (r ∗ ,ξ ∗ )−L N,λ (r † ,ξ r † )] ≤6ε + 2 N h ∥ξ ∗ ∥ 1 + log |N ε (R)| δ i − E 2 r † 2(3 + e R ) 2 =6ε + 2 N h ∥ξ ∗ ∥ 1 + log |N ε (R)| δ i − E 2 r † − E 2 r 2(3 + e R ) 2 − E 2 r 2(3 + e R ) 2 (a) ≤ 6ε + 2 N h ∥ξ ∗ ∥ 1 + log |N ε (R)| δ i + 4Rε (3 + e R ) 2 − E 2 r 2(3 + e R ) 2 (b) ≤7ε + 2 N h ∥ξ ∗ ∥ 1 + log |N ε (R)| δ i − E 2 r 2(3 + e R ) 2 ,(45) which proves Eq.(39). Here, (a) uses the following inequality and (b) uses(3 + e R ) 2 > 6e R + e 2R > 6R + 2R = 8R. |E 2 r † − E 2 r | = E D r ∗ (x 1 ,a w 1 )− r ∗ (x 1 ,a ℓ 1 )− r † (x 1 ,a w 1 ) + r † (x 1 ,a ℓ 1 ) 2 − E D r ∗ (x 1 ,a w 1 )− r ∗ (x 1 ,a ℓ 1 )− r(x 1 ,a w 1 ) + r(x 1 ,a ℓ 1 ) 2 = E D r(x 1 ,a w 1 )− r(x 1 ,a ℓ 1 )− r † (x 1 ,a w 1 ) + r † (x 1 ,a ℓ 1 ) 2r ∗ (x 1 ,a w 1 )− 2r ∗ (x 1 ,a ℓ 1 )− r † (x 1 ,a w 1 ) + r † (x 1 ,a ℓ 1 )− r(x 1 ,a w 1 ) + r(x 1 ,a ℓ 1 ) (a) ≤ (2ε)(4R) = 8Rε, where (a) uses Assumption 2 and∥r † − r∥ ∞ ≤ ε. Lemma 9. Fixing anyε > 0,δ ∈ (0, 1), the online datasetx i ,a w i ,a ℓ i ,y i T i=1 generated from Algorithm 2 satisfies the following bound for allt = 1,...,Tandπ ∈ Π R def = π r : r ∈ R simultaneously with probability at least 1− δ. t X i=1 log σ r π (x i ,a w i )− r π (x i ,a ℓ i ) + y i ξ π i σ r ∗ (x i ,a w i )− r ∗ (x i ,a ℓ i ) + y i ξ ∗ i ≤2 log T|N ε (R)| δ + 4tε + t X i=1 n 1 4 |ξ ∗ i | + σ(R)|ξ π i | − 1 2(3 + e R ) 2 E x∼ρ,a (1) ∼π i (·|x),a (−1) ∼π ref (·|x) f 2 π (x,a (1) ,a (−1) ) o , where the functionf π is defined below andN ε (R)is a finiteε-cover ofR, that is, for anyr ∈R, there exists r † ∈N ε (R) satisfying∥r † − r∥ ∞ ≤ ε. f π (x,a (1) ,a (−1) ) def = r ∗ (x,a (1) )− r ∗ (x,a (−1) )− r π (x,a (1) ) + r π (x,a (−1) ),(46) 24 Proof. Define the following function. q π,ξ i (y i |x i ,a (1) i ,a (−1) i ) def = σ β log π(a (1) i |x i ) π ref (a (1) i |x i ) − β log π(a (−1) i |x i ) π ref (a (−1) i |x i ) + ω(|a (1) i |−|a (−1) i |) + ξ i , y i = 1 σ β log π(a (−1) i |x i ) π ref (a (−1) i |x i ) − β log π(a (1) i |x i ) π ref (a (1) i |x i ) + ω(|a (−1) i |−|a (1) i |)− ξ i , y i =−1. =σ r π (x i ,a w i )− r π (x i ,a ℓ i ) + y i ξ i ,(47) where the second=uses Eq.(16)and merges the above two cases. The aboveq π,ξ i (y i |x i ,a (1) i ,a (−1) i ) can be seen as a conditional probability ofy i ∈−1, 1sinceq π,ξ i (1|x i ,a (1) i ,a (−1) i ) +q π,ξ i (−1|x i ,a (1) i ,a (−1) i ) = 1 . Then define the following random variables for i = 1,...,T . W i (π) = 1 2 log σ r π (x i ,a w i )− r π (x i ,a ℓ i ) σ r ∗ (x i ,a w i )− r ∗ (x i ,a ℓ i ) + y i ξ ∗ i = 1 2 log q π,0 (y i |x i ,a (1) i ,a (−1) i ) p r ∗ ,ξ ∗ i (y i |x i ,a (1) i ,a (−1) i ) ,(48) where p r,ξ i (y i |x i ,a (1) i ,a (−1) i ) is defined by Eq. (41). For anyr ∈R, there existsr † ∈N ε (R)satisfying∥r † − r∥ ∞ ≤ ε, and thus we can temporarily denote r u = ur π r † + (1− u)r π (u∈ [0, 1]). Then we obtain that d du logσ r u (x i ,a w i )− r u (x i ,a ℓ i ) =σ r u (x i ,a ℓ i )− r u (x i ,a w i ) r π r † (x i ,a w i )− r π r † (x i ,a ℓ i )− r π (x i ,a w i ) + r π (x i ,a ℓ i ) (a) ≤ r † (x i ,a w i )− r † (x i ,a ℓ i )− r π (x i ,a w i ) + r π (x i ,a ℓ i ) ≤ r † (x i ,a w i )− r π (x i ,a w i ) + r π (x i ,a ℓ i )− r † (x i ,a ℓ i ) ≤ 2ε,(49) where (a) uses Eq. (29) and σ(x)∈ (0, 1) for any x∈ R. Therefore, |W i (π r † )− W i (π)| (a) = 1 2 h logq π r † ,0 (y i |x i ,a (1) i ,a (−1) i )− logq π,0 (y i |x i ,a (1) i ,a (−1) i ) i (b) = 1 2 logσ r π r † (x i ,a w i )− r π r † (x i ,a ℓ i ) − logσ r π (x i ,a w i )− r π (x i ,a ℓ i ) (c) = 1 2 logσ r 1 (x i ,a w i )− r 1 (x i ,a ℓ i ) − logσ r 0 (x i ,a w i )− r 0 (x i ,a ℓ i ) (d) ≤ ε,(50) where (a) and (b) use Eq.(48), (c) uses the above notation thatr u = ur π r † + (1− u)r π (u∈ [0, 1]), and (d) uses Eq.(49). Then based on Algorithm 2 and Assumption 1, given(x i ,a (1) i ,a (−1) i ), the labely i is generated with probability distributionp r ∗ ,ξ i (y i |x i ,a (1) i ,a (−1) i )defined by Eq.(41). Therefore, given anyδ ∈ (0, 1) andε > 0, by Lemma 7 withλ ′ = 1, the following inequality holds fort = 1,...,Tand finitely many π ′ ∈N ε (R) simultaneously with probability at least 1− δ. t X i=1 W i (π ′ )≤ log T|N ε (R)| δ + t X i=1 log E μ i [e W i (π ′ ) ]. whereμ i denotes the distribution of thei-th online data sample(x i ,a (−1) i ,a (1) i ,y i )generated by Algorithm 2. We further upper bound the above inequality as follows. t X i=1 W i (π ′ )− log T|N ε (R)| δ 25 ≤ t X i=1 log E μ i [e W i (π ′ ) ] (48) = t X i=1 log E μ i ( E y i ∼p r ∗ ,ξ ∗ i (·|x i ,a (1) i ,a (−1) i ) " v u u t q π ′ ,0 (y i |x i ,a (1) i ,a (−1) i ) p r ∗ ,ξ ∗ i (y i |x i ,a (1) i ,a (−1) i ) x i ,a (1) i ,a (−1) i #) (a) ≤ t X i=1 E μ i " X y∈−1,1 q q π ′ ,0 (y|x i ,a (1) i ,a (−1) i )p r ∗ ,ξ ∗ i (y|x i ,a (1) i ,a (−1) i )− 1 # =− 1 2 t X i=1 E μ i " X y∈−1,1 q q π ′ ,0 (y|x i ,a (1) i ,a (−1) i )− q p r ∗ ,ξ ∗ i (y|x i ,a (1) i ,a (−1) i ) 2 # (b) ≤ − 1 8 t X i=1 E μ i " X y∈−1,1 q π ′ ,0 (y|x i ,a (1) i ,a (−1) i )− p r ∗ ,ξ ∗ i (y|x i ,a (1) i ,a (−1) i ) 2 # (c) = − 1 4 t X i=1 E μ i n σ[r π ′ (x i ,a w i )− r π ′ (x i ,a ℓ i )]− σ[r ∗ (x i ,a w i )− r ∗ (x i ,a ℓ i ) + y i ξ ∗ i ] o 2 (d) ≤ − 1 4 t X i=1 nh E μ i σ[r π r ∗ (x i ,a w i )− r π r ∗ (x i ,a ℓ i )]− σ[r π ′ (x i ,a w i )− r π ′ (x i ,a ℓ i )] 2 i − 1 2 |ξ ∗ i | o (e) ≤ 1 8 t X i=1 n |ξ ∗ i |− 2 (3 + e R ) 2 E μ i h r π r ∗ (x i ,a w i )−r π r ∗ (x i ,a ℓ i )−r π ′ (x i ,a w i )+r π ′ (x i ,a ℓ i ) 2 io ,(51) where (a) useslogv ≤ v− 1for anyv > 0, (b) uses Lemma 12.2 of (Harsha, 2011), (c) uses Eqs.(41)and (47), (d) uses Eq.(29)and Lemma 5, and (e) uses Assumption 2 and Lemma 1. Combining Eqs.(50)and (51), we obtain the following inequality which holds for allt = 1,...,Tandπ ∈ Πsimultaneously with probability at least 1− δ. t X i=1 W i (π) ≤ t X i=1 [W i (π)− W i (π r † )] + W i (π r † ) (a) ≤ 1 8 t X i=1 n |ξ ∗ i |− 2 (3 + e R ) 2 E μ i h r π r ∗ (x i ,a w i )−r π r ∗ (x i ,a ℓ i )−r π r † (x i ,a w i )+r π r † (x i ,a ℓ i ) 2 io + log T|N ε (R)| δ + tε (b) ≤ 1 8 t X i=1 n |ξ ∗ i |− 2 (3 + e R ) 2 E μ i h r π r ∗ (x i ,a w i )− r π r ∗ (x i ,a ℓ i )− r π (x i ,a w i ) + r π (x i ,a ℓ i ) 2 io + log T|N ε (R)| δ + 2tε,(52) where (a) uses Eq.(51)(withπ ′ replaced byπ r † ) and Eq.(50), (b) uses the following inequality and (3 + e R ) 2 > 6e R + e 2R > 6R + 2R = 8R. r π r ∗ (x i ,a w i )− r π r ∗ (x i ,a ℓ i )− r π (x i ,a w i ) + r π (x i ,a ℓ i ) 2 26 − r π r ∗ (x i ,a w i )− r π r ∗ (x i ,a ℓ i )− r π r † (x i ,a w i ) + r π r † (x i ,a ℓ i ) 2 = r π r † (x i ,a w i )− r π r † (x i ,a ℓ i )− r π (x i ,a w i ) + r π (x i ,a ℓ i ) 2r π r ∗ (x i ,a w i )− 2r π r ∗ (x i ,a ℓ i )− r π (x i ,a w i ) + r π (x i ,a ℓ i )− r π r † (x i ,a w i ) + r π r † (x i ,a ℓ i ) (a) = r † (x i ,a w i )− r † (x i ,a ℓ i )− r π (x i ,a w i ) + r π (x i ,a ℓ i ) 2r π r ∗ (x i ,a w i )− 2r π r ∗ (x i ,a ℓ i )− r π (x i ,a w i ) + r π (x i ,a ℓ i )− r π r † (x i ,a w i ) + r π r † (x i ,a ℓ i ) (b) ≤(2ε)(4R) = 8Rε, where (a) uses Eq. (29), and (b) uses∥r † − r∥ ∞ ≤ ε and Lemma 3. Finally, we conclude the proof as follows. t X i=1 log σ r π (x i ,a w i )− r π (x i ,a ℓ i ) + y i ξ π i σ r ∗ (x i ,a w i )− r ∗ (x i ,a ℓ i ) + y i ξ ∗ i (a) ≤ t X i=1 h log σ r π (x i ,a w i )− r π (x i ,a ℓ i ) σ r ∗ (x i ,a w i )− r ∗ (x i ,a ℓ i ) + y i ξ ∗ i + σ(R)|ξ π i | i (b) = t X i=1 2W i (π) + σ(R)|ξ π i | (c) ≤2 log T|N ε (R)| δ + 4tε + t X i=1 n 1 4 |ξ ∗ i | + σ(R)|ξ π i | − 1 2(3 + e R ) 2 E μ i h r π r ∗ (x i ,a w i )− r π r ∗ (x i ,a ℓ i )− r π (x i ,a w i ) + r π (x i ,a ℓ i ) 2 io (d) = 2 log T|N ε (R)| δ + 4tε + t X i=1 n 1 4 |ξ ∗ i | + σ(R)|ξ π i | − 1 2(3 + e R ) 2 E μ i h r ∗ (x i ,a (1) i )− r ∗ (x i ,a (−1) i )− r π (x i ,a (1) i ) + r π (x i ,a (−1) i ) 2 io (e) = 2 log T|N ε (R)| δ + 4tε + t X i=1 n 1 4 |ξ ∗ i | + σ(R)|ξ π i | − 1 2(3 + e R ) 2 E x∼ρ,a (1) ∼π i (·|x),a (−1) ∼π ref (·|x) f 2 π (x,a (1) ,a (−1) ) o , where (a) uses Eq.(33)from Lemma 4, (b) usesW i (π)defined by Eq.(48), (c) uses Eq.(52), (d) uses Eq. (29) anda w i ,a ℓ i =a (1) i ,a (−1) i (based on Assumption 1), and (e) uses Eq. (46). Lemma 10 (Azuma-Hoeffding Inequality (Xie et al., 2024)). The random variablesX t T t=1 satisfy|X t |≤ C almost surely. Then with probability at least 1− δ, we have T X t=1 [X t − E(X t |X 1 ,...,X t−1 )] ≤ C p 8T log(2/δ).(53) Lemma 11. Fixing anyε > 0,δ ∈ (0, 1), the online datasetx i ,a (1) i ,a (−1) i ,y i T i=1 generated from Algorithm 2 satisfies the following inequality for allt = 1,...,Tandπ ∈ Π R def = π r : r ∈Rsimultaneously with 27 probability at least 1− δ. h t X i=1 log π(a (−1) i |x i ) π r ∗ (a (−1) i |x i ) i −tE x∼ρ,a∼π ref (·|x) h log π(a|x) π r ∗ (a|x) i ≤ 4R β r 2t log h 2TN ε (R) δ i + 4tε β . Proof. For anyr ∈ R, denoteX i (r) = log π r (a (−1) i |x i ) π r ∗ (a (−1) i |x i ) which satisfies|X i (r)| ≤ 2R β based on Lemma 6 and Assumption 2. Then by applying Lemma 10 toX i (r)with union bound, we obtain the following inequality which holds for all t = 0, 1,...,T − 1 and r ′ ∈N ε (R) simultaneously with probability at least 1− δ. t X i=1 [X i (r ′ )− E μ i X i (r ′ )] ≤ 2R β r 8t log h 2TN ε (R) δ i .(54) whereμ i denotes the distribution of thei-th online data sample(x i ,a (−1) i ,a (1) i ,y i )generated by Algorithm 2. For any r ∈R, there exists r † ∈N ε (R) satisfying∥r † − r∥ ∞ ≤ ε, so Lemma 6 implies that |X i (r † )− X i (r)| = log π r † (a (−1) i |x i ) π r (a (−1) i |x i ) ≤ 2ε β . Therefore, if the above high probability eventE := Eq. (54) holds for all r ′ ∈ N ε (R)occurs, then the following inequality holds for any r ∈R. t X i=1 [X i (r)− E μ i X i (r)] ≤ 2R β r 8t log h 2TN ε (R) δ i + 4tε β .(55) For any π ∈ Π R def = π r : r ∈R, there exists r ∈R satisfying π = π r . Then we have X i (r) = log π(a (−1) i |x i ) π r ∗ (a (−1) i |x i ) . and thus E μ i X i (r) = E x i ∼ρ,a (−1) i ∼π ref (·|x) " log π(a (−1) i |x i ) π r ∗ (a (−1) i |x i ) # = E x∼ρ,a∼π ref (·|x) h log π(a|x) π r ∗ (a|x) i . Substituting the above two equalities into Eq. (55) concludes the proof. Lemma 12. Suppose that the offline datasetx i ,a w i ,a ℓ i ,y i N i=1 is generated from Assumption 1, and select the baseline policyπ base to be the distribution ofa w i givenx i . Then fixing anyε > 0,δ ∈ (0, 1), the following inequality holds for all π ∈ Π R def = π r : r ∈R simultaneously with probability at least 1− δ. h N X i=1 log π(a w i |x i ) π r ∗ (a w i |x i ) i −NE x∼ρ,a∼π base (·|x) h log π(a|x) π r ∗ (a|x) i ≤ 4R β r 2N log h 2N ε (R) δ i + 4Nε β . Proof. The proof logic is the same as that of Lemma 11. The major difference is that the inequality here only has to hold for anyπ ∈ Π R while Lemma 11 requires to hold also fort = 1,...,T. As a result, when applying Lemma 10 with union bound, 2TN ε (R) δ in the proof of Lemma 11 is replaced with 2N ε (R) δ . 28 Lemma 13. Define the following quantity. I t def = E x∼ρ,a (1) ∼π t+1 (·|x),a (−1) ∼π ref (·|x) f π t+1 (x,a (1) ,a (−1) ) 2 R 2 + P t i=1 E x∼ρ,a (1) ∼π i (·|x),a (−1) ∼π ref (·|x) [f 2 π t+1 (x,a (1) ,a (−1) )] ,(56) where the function f π is defined by Eq. (46). Then we have T X t=1 I t ≤ 12G on log(T + 2),(57) where G on is defined by Eq. (26). Proof. Applying Assumption 2 and Lemma 3 to the function f π defined by Eq. (46), we have f π (x,a (1) ,a (−1) ) =r ∗ (x,a (1) )−r ∗ (x,a (−1) )−r π (x,a (1) )+r π (x,a (−1) )∈ [−2R, 2R].(58) Denoteν ∗ ∈ argmin ν∈Π R sup x∈X,a∈A,π∈Π R π(a|x) ν(a|x) as the policy used in the coverability coefficient(26). Then we have π(a (1) |x)≤ G on ν ∗ (a (1) |x), ∀x∈X,a (1) ∈A,π ∈ Π R .(59) Then for each (x,a (1) )∈X ×A, define the following quantity (min∅ = +∞ by default) τ (x,a (1) ) = min ( t≥ 1 t X i=1 π i+1 (a (1) |x)≥ G on ν ∗ (a (1) |x) ) .(60) Hence, T X t=1 π t+1 (a (1) |x)It≤ τ (x,a (1) )− 1 < G on ν ∗ (a (1) |x),(61) t X i=1 π i (a (1) |x)≥ G on ν ∗ (a (1) |x), ∀t≥ τ (x,a (1) ) + 1.(62) Then we conclude the proof as follows. T X t=1 I t = T X t=1 E x∼ρ,a (1) ∼π t+1 (·|x),a (−1) ∼π ref (·|x) f π t+1 (x,a (1) ,a (−1) )It≤ τ (x,a (1) ) 2 R 2 + P t i=1 E x∼ρ,a (1) ∼π i (·|x),a (−1) ∼π ref (·|x) [f 2 π t+1 (x,a (1) ,a (−1) )] + T X t=1 E x∼ρ,a (1) ∼π t+1 (·|x),a (−1) ∼π ref (·|x) f π t+1 (x,a (1) ,a (−1) )It≥ τ (x,a (1) ) + 1 2 R 2 + P t i=1 E x∼ρ,a (1) ∼π i (·|x),a (−1) ∼π ref (·|x) [f 2 π t+1 (x,a (1) ,a (−1) )] (a) ≤ 1 R 2 T X t=1 (2RE x∼ρ,a (1) ∼π t+1 (·|x) It≤ τ (x,a (1) )) 2 + T X t=1 E x∼ρ,a (1) ∼π t (·|x),a (−1) ∼π ref (·|x) f π t+1 (x,a (1) ,a (−1) )· π t+1 (a (1) |x) π t (a (1) |x) It≥ τ (x,a (1) ) + 1 2 tE x∼ρ,a (1) ∼π t (·|x),a (−1) ∼π ref (·|x) [f 2 π t+1 (x,a (1) ,a (−1) )] 29 (b) ≤4 T X t=1 E x∼ρ,a (1) ∼π t+1 (·|x) It≤ τ (x,a (1) ) + T X t=1 1 t E x∼ρ,a (1) ∼π t (·|x) h π t+1 (a (1) |x) π t (a (1) |x) i 2 It≥ τ (x,a (1) ) + 1 =4 X x,a (1) ρ(x) " T X t=1 [π t+1 (a (1) |x)It≤ τ (x,a (1) )− 1] + T X t=1 [π t+1 (a (1) |x)It = τ (x,a (1) )] # + 2 X x,a (1) ρ(x) T X t=1 π t+1 (a (1) |x) tπ t (a (1) |x) + tπ t (a (1) |x) [π t+1 (a (1) |x)It≥ τ (x,a (1) ) + 1] (c) ≤4 X x,a (1) ρ(x)[G on ν ∗ (a (1) |x) + G on ν ∗ (a (1) |x)] + 2 X x,a (1) ρ(x) T X t=1 π t+1 (a (1) |x) tπ t (a (1) |x) + G on ν ∗ (a (1) |x) [π t+1 (a (1) |x)It≥ τ (x,a (1) ) + 1] (d) ≤ 8G on X x,a (1) ρ(x)ν ∗ (a (1) |x) +4 X x,a (1) ρ(x) T X t=1 log h (t + 1) π t+1 (a (1) |x) + G on ν ∗ (a (1) |x) tπ t (a (1) |x) + G on ν ∗ (a (1) |x) i [G on ν ∗ (a (1) |x)] =8G on + 4G on X x,a (1) ρ(x)ν ∗ (a (1) |x) log h (T + 1)π T +1 (a (1) |x) + G on ν ∗ (a (1) |x) π 1 (a (1) |x) + G on ν ∗ (a (1) |x) i (e) ≤ 8G on + 4G on X x,a (1) ρ(x)ν ∗ (a (1) |x) log h (T + 1)G on ν ∗ (a (1) |x) + G on ν ∗ (a (1) |x) G on ν ∗ (a (1) |x) i ≤12G on log(T + 2), where (a) denotesπ t = 1 t P t i=1 π i and uses Eq.(58)and(EX) 2 ≤ E(X 2 )for any random variableX ∈ R, (b) uses Cauchy-Schwartz inequality, (c) uses Eqs.(59),(61)and Eq.(62), (d) uses Eq.(59)and the inequality thatu ≤ 2 log(1 + u)foru = π t+1 (a (1) |x) tπ t (a (1) |x)+G on ν ∗ (a (1) |x) ∈ [0, 1] (u ∈ [0, 1]due to Eq.(59)), (e) uses Eq. (59). C Proof of Proposition 1 (π,r,ξ) is the solution to the offline RLHF-COV objective (12) means the following two conditions hold π ∈arg max π ′ ∈Π L N,λ (r,ξ) + ηV β,ω (π ′ ,r), (r,ξ)∈arg min r ′ ∈R,ξ ′ ∈R N max π ′ ∈Π L N,λ (r ′ ,ξ ′ ) + ηV β,ω (π ′ ,r ′ ). Based on the notation that π r def = arg max π ′ ∈Π V β,ω (π ′ ,r), the above two conditions are equivalent to π = π r ,(r,ξ)∈ arg min r ′ ∈R,ξ ′ ∈R N L N,λ (r ′ ,ξ ′ ) + ηV β,ω (π r ′ ,r ′ ) 30 Furthermore, based on the notation thatξ r def = arg min ξ∈R N L N,λ (r,ξ) , the above two conditions are equiva- lent to π = π r , ξ = ξ r , r = arg min r ′ ∈R L N,λ (r ′ ,ξ r ′ ) + ηV β,ω (π r ′ ,r ′ ).(63) This prove the first part of the theorem. Next, we will obtain the analytical solutions of π r and ξ r,i . We rewrite the function (11) as follows. V β,ω (π,r) =E x∼ρ,a∼π(·|x),a ′ ∼π base (·|x) r(x,a) + ω|a|− r(x,a ′ )− ω|a ′ | − βE x∼ρ KL π(·|x) π ref (·|x) =E x∼ρ,a∼π(·|x) h r(x,a) + ω|a|− β log π(a|x) π ref (a|x) i − E x∼ρ,a ′ ∼π base (·|x) r(x,a ′ ) + ω|a ′ | =− βE x∼ρ,a∼π(·|x) h log π(a|x)/Z r (x) π ref (a|x) exp [r(x,a) + ω|a|]/β /Z r (x) i − E x∼ρ,a ′ ∼π base (·|x) r(x,a ′ ) + ω|a ′ | =C− βE x∼ρ KL h π(·|x) π ref (·|x) exp [r(x,·) + ω|·|]/β /Z r (x) i , whereZ r (x) def = P a ′ ∈A π ref (a ′ |x) exp r(x,a ′ )−ω|a ′ | β and the constantC = βE x∼ρ logZ r (x)−E x∼ρ,a ′ ∼π base (·|x) r(x,a ′ )+ ω|a ′ | is independent ofπ. Therefore,π r def = arg max π ′ ∈Π V β,ω (π ′ ,r) should minimize the above KL term, which gives the analytical solution (14). Note that the log-likelihood function (8) can be rewritten as follows. L N,λ (r,ξ) def = 1 N N X i=1 f i (ξ i ), wheref i (v) := λ|v|− logσ[r(x i ,a w i )− r(x i ,a ℓ i ) + y i v]. Hence,ξ r ∈ arg min ξ L N,λ (r,ξ)is equivalent to the following condition: ξ r,i ∈ arg min v∈R f i (v);i = 1, 2,...,N. Asf i is a convex function forλ > 0, the above optimality condition is equivalent to the following stationary condition. 0∈ ∂f i (ξ r,i ) = λ∂|ξ r,i | + y i σ[r(x i ,a w i )− r(x i ,a ℓ i ) + y i ξ r,i ]− 1 ,(64) where∂denotes partial differential. Noticing thaty i ∈ −1, 1, it can be easily verified that the above equation has unique solution ξ r,i defined by Eq. (15). D Proof of Proposition 2 Note that ξ π r (a) = ξ r π r (b) = ξ r ,(65) where (a) uses Eq.(17)and (b) substitutes Eq.(29)into Eq.(15). Therefore, by using Lemma 3, Eq.(65), and substituting Eq. (29) into Eqs. (8) and (11), we obtain that L N,λ (r π r ,ξ π r ) + ηV β,ω (π r π ,r π r ) =L N,λ (r,ξ r ) + ηV β,ω (π,r),(66) 31 Since Π R def = π r : r ∈R, the following two statements are equivalent. (P1): π is optimal for the offline DPO-COV objective (18), i.e., π ∈ arg min π ′ ∈Π R [L N,λ (r π ′ ,ξ π ′ ) + ηV β,ω (π r π ′ ,r π ′ )]. (P2): There exists r ∈ arg min r ′ ∈R [L N,λ (r π r ′ ,ξ π r ′ ) + ηV β,ω (π r π r ′ ,r π r ′ )] such that π = π r . This along with Eq. (66) implies that (P2) is equivalent to the following statement. (P3): There exists r ∈ arg min r ′ ∈R [L N,λ (r ′ ,ξ r ′ ) + ηV β,ω (π r ′ ,r ′ )] such that π = π r . By Proposition 1, (P3) is equivalent to the following statement. (P4): There existr ∈Randξ = ξ r ∈ R N such thatπ = π r , and(π,r,ξ)is the optimal solution to the offline RLHF-COV objective (12). So far, we have proved the equivalence among (P1)-(P4), so the first part of this proposition is correct which states that (P1) and (P4) are equivalent. It remains to prove the second part of this proposition, i.e., to figure outξandrgivenπunder the assumption that (P1)-(P4) hold. Note that based on the analytical solution(14)ofπ r ,π = π r required by (P2)-(P4) holds if and only if for anyx∈Xthere existsU π (x)∈ Rsuch thatr(x,·) = r π (x,·) + U π (x) . In this case, we have ξ (a) = ξ r (b) = ξ r π (c) = ξ π , where (a) uses (P4), (b) substitutes r(x,·) = r π (x,·) + U π (x) into Eq. (16), (c) uses ξ π def = ξ r π . E Proof of Proposition 3 The proof logic is exactly the same as that of Proposition 2, with η replaced by−η. F Proof of Theorem 1 Obtaineπ ∈ arg min π∈Π R L N,λ (r π ,ξ π ) + ηV β,ω (π r π ,r π ) by minimizing the offline DPO-COV objective (18). Then based on Proposition(2), there existser ∈Rsuch that(eπ,er,ξ eπ )(ξ eπ is defined by Eq.(17)) is the optimal solution to the offline RLHF-COV objective (12), that is, (er,ξ eπ )∈ arg min r ′ ∈R,ξ ′ ∈R N max π ′ ∈Π L N,λ (r ′ ,ξ ′ ) + ηV β,ω (π ′ ,r ′ ) ,(67) eπ = π er ∈ arg max π ′ ∈Π V β,ω (π ′ ,er).(68) Then denote eπ 2 ∈ arg max π ′ ∈Π min r ′ ∈R,ξ ′ ∈R N L N,λ (r ′ ,ξ ′ ) + ηV β,ω (π ′ ,r ′ ) and we have L N,λ (er,ξ eπ ) + ηV β,ω (eπ 2 ,er) ≥min r ′ ∈R,ξ ′ ∈R N L N,λ (r ′ ,ξ ′ ) + ηV β,ω (eπ 2 ,r ′ ) (a) = max π ′ ∈Π min r ′ ∈R,ξ ′ ∈R N L N,λ (r ′ ,ξ ′ ) + ηV β,ω (π ′ ,r ′ ) (b) =min r ′ ∈R,ξ ′ ∈R N max π ′ ∈Π L N,λ (r ′ ,ξ ′ ) + ηV β,ω (π ′ ,r ′ ) (69) (c) = max π ′ ∈Π L N,λ (er,ξ eπ ) + ηV β,ω (π ′ ,er) ,(70) where (a) useseπ 2 ∈ arg max π ′ ∈Π min r ′ ∈R,ξ ′ ∈R N L N,λ (r ′ ,ξ ′ ) + ηV β,ω (π ′ ,r ′ ) , (b) applies the minimax theorem (Theorem 1 of (Fan, 1953)) to the functionL N,λ (r ′ ,ξ ′ ) + ηV β,ω (π ′ ,r ′ )(defined by Eqs.(8)and 32 (11)) which is a concave function ofπ ′ ∈ Πand a convex function of(r ′ ,ξ ′ ) ∈ R× R d , and (c) uses Eq. (67). The above inequality implies that eπ 2 ∈ max π ′ ∈Π V β,ω (π ′ ,er) and thus eπ 2 = π er (68) = eπ. This means eπ = eπ 2 ∈ arg max π ′ ∈Π min r ′ ∈R,ξ ′ ∈R N L N,λ (r ′ ,ξ ′ ) + ηV β,ω (π ′ ,r ′ ) .(71) Note that for any π ∈ Π, Eqs. (11), (20) imply that J β,ω (π)− J β,ω (eπ) = V β,ω (π)− V β,ω (eπ).(72) Hence, π r ∗ ∈ arg max π∈Π V β,ω (π) also satisfies π r ∗ ∈ arg max π∈Π J β,ω (π).(73) Finally, we prove the generalization error rate (22) as follows. max π∈Π J β,ω (π)− J β,ω (eπ) (a) =V β,ω (π r ∗ ,r ∗ )− η −1 max π∈Π min r∈R,ξ∈R N L N,λ (r,ξ) + ηV β,ω (π,r) + η −1 min r∈R,ξ∈R N L N,λ (r,ξ) + ηV β,ω (eπ,r) − V β,ω (eπ,r ∗ ) (b) ≤V β,ω (π r ∗ ,r ∗ )− η −1 min r∈R L N,λ (r,ξ r ) + ηV β,ω (π r ∗ ,r) + η −1 L N,λ (r ∗ ,ξ ∗ ) + ηV β,ω (eπ,r ∗ ) − V β,ω (eπ,r ∗ ) (c) = max r∈R n E x∼ρ,a∼π r ∗ (·|x),a ′ ∼π base (·|x) r ∗ (x,a)− r ∗ (x,a ′ )− r(x,a) + r(x,a ′ ) + η −1 [L N,λ (r ∗ ,ξ ∗ )−L N,λ (r,ξ r )] o (d) ≤ max r∈R n G D E r + 2 Nη h ∥ξ ∗ ∥ 1 + log |N 1/N (R)| δ i − E 2 r 2η(3 + e R ) 2 + 7 Nη o (e) ≤ 2 Nη h ∥ξ ∗ ∥ 1 + 5 log |N 1/N (R)| δ i + ηG 2 D 2 (3 + e R ) 2 (f ) ≤ (G 2 D + 1)(3 + e R ) √ N q ∥ξ ∗ ∥ 1 + 5 log[|N 1/N (R)|/δ],(74) where (a) uses Eqs.(71),(72)and(73), (b) usesξ r ∈ arg min ξ∈R N L N,λ (r,ξ)as well asr ∗ ∈ Rin Assumption 2, (c) uses Eq.(11), (d) uses Assumption 3 and Lemma 8 withε = 1/NandE r := q E D r ∗ (x 1 ,a w 1 )− r ∗ (x 1 ,a ℓ 1 )− r(x 1 ,a w 1 ) + r(x 1 ,a ℓ 1 ) 2 , (e) uses1 ≤ log[|N 1/N (R)|/δ]as well asbE− aE 2 ≤ b 2 4a for any a > 0 and b,E ∈ R, (f) uses η = 2 √ ∥ξ ∗ ∥ 1 +5 log[|N 1/N (R)|/δ] √ N (3+e R ) . G Proof of Theorem 2 The update rule (25) implies that 0≤tφ t (π r ∗ )− tφ t (π t+1 ) (a) = t X i=1 ( λ(|ξ r ∗ ,i |−|ξ π t+1 i |) + βη log π r ∗ (a (−1) i |x i ) π t+1 (a (−1) i |x i ) 33 + log σ[r π t+1 (x i ,a w i )− r π t+1 (x i ,a ℓ i ) + y i ξ π t+1 i ] σ[r ∗ (x i ,a w i )− r ∗ (x i ,a ℓ i ) + y i ξ r ∗ ,i ] ) (b) ≤ t X i=1 ( λ(|ξ ∗ i |−|ξ π t+1 i |) + βη log π r ∗ (a (−1) i |x i ) π t+1 (a (−1) i |x i ) + log σ[r π t+1 (x i ,a w i )− r π t+1 (x i ,a ℓ i ) + y i ξ π t+1 i ] σ[r ∗ (x i ,a w i )− r ∗ (x i ,a ℓ i ) + y i ξ ∗ i ] ) ,(75) where (a) uses Eq.(16),ξ π r ∗ i = ξ r ∗ ,i (by Eq.(65)), and Lemma 2 (withrreplaced byr ∗ ) and (b) uses the fact thatξ r ∗ ,i ∈ arg min ξ i ∈R λ|ξ i |− logσ[r ∗ (x i ,a w i )− r ∗ (x i ,a ℓ i ) + y i ξ i ] , thei-th component ofL t,λ (r ∗ ,ξ) defined in Eq. (8). Based on Lemmas 9 and 11 (both withδreplaced byδ/2andπreplaced byπ t+1 ), the following two inequalities hold for t = 1,...,T simultaneously with probability at least 1− δ. t X i=1 log σ[r π t+1 (x i ,a w i )− r π t+1 (x i ,a ℓ i ) + y i ξ π t+1 i ] σ[r ∗ (x i ,a w i )− r ∗ (x i ,a ℓ i ) + y i ξ ∗ i ] ≤2 log 2T|N ε (R)| δ + 4tε + t X i=1 n 1 4 |ξ ∗ i | + σ(R)|ξ π t+1 i | − 1 2(3 + e R ) 2 E x∼ρ,a (1) ∼π i (·|x),a (−1) ∼π ref (·|x) f 2 π t+1 (x,a (1) ,a (−1) ) o ,(76) t X i=1 log π r ∗ (a (−1) i |x i ) π t+1 (a (−1) i |x i ) ≤ 4R β r 2t log h 2TN ε (R) δ i + 4tε β +tE x∼ρ,a∼π ref (·|x) h log π r ∗ (a|x) π t+1 (a|x) i .(77) Substituting Eqs. (76) and (77) into Eq. (75), we obtain that 0≤4ηR r 2t log h 4TN ε (R) δ i + 4ηεt + βηtE x∼ρ,a∼π ref (·|x) h log π r ∗ (a|x) π t+1 (a|x) i + λ t X i=1 (|ξ ∗ i |−|ξ π t+1 i |) + 2 log 2T|N ε (R)| δ + 4tε + t X i=1 n 1 4 |ξ ∗ i | + σ(R)|ξ π t+1 i | − 1 2(3 + e R ) 2 E x∼ρ,a (1) ∼π i (·|x),a (−1) ∼π ref (·|x) f 2 π t+1 (x,a (1) ,a (−1) ) o (a) ≤ 4ηR r 2t log h 4TN ε (R) δ i + 2 log 2T|N ε (R)| δ + 4ηεt + 4εt − βηtE x∼ρ,a∼π ref (·|x) h log π t+1 (a|x) π r ∗ (a|x) i + t X i=1 n 5 4 |ξ ∗ i |− 1 2(3 + e R ) 2 E x∼ρ,a (1) ∼π i (·|x),a (−1) ∼π ref (·|x) f 2 π t+1 (x,a (1) ,a (−1) ) o ,(78) where (a) uses λ∈ [σ(R), 1]. Then, we have J β,ω (π r ∗ )− J β,ω (π t+1 ) (a) = E x∼ρ,a∼π r ∗ (·|x) h r ∗ (x,a)− ω|a|− β log π r ∗ (a|x) π ref (a|x) i 34 − E x∼ρ,a∼π t+1 (·|x) h r ∗ (x,a)− ω|a|− β log π t+1 (a|x) π ref (a|x) i (b) =E x∼ρ,a∼π ref (·|x) h r ∗ (x,a)− ω|a|− β log π r ∗ (a|x) π ref (a|x) i − E x∼ρ,a∼π t+1 (·|x) h r ∗ (x,a)− ω|a|− β log π t+1 (a|x) π ref (a|x) i =βE x∼ρ,a∼π ref (·|x) h log π t+1 (a|x) π r ∗ (a|x) i + E x∼ρ,a∼π t+1 (·|x) h ω|a| + β log π t+1 (a|x) π ref (a|x) − r ∗ (x,a) i − E x∼ρ,a∼π ref (·|x) h ω|a| + β log π t+1 (a|x) π ref (a|x) − r ∗ (x,a) i (c) =βE x∼ρ,a∼π ref (·|x) h log π t+1 (a|x) π r ∗ (a|x) i + E x∼ρ,a∼π t+1 (·|x) r π t+1 (x,a)− r ∗ (x,a) − E x∼ρ,a∼π ref (·|x) r π t+1 (x,a)− r ∗ (x,a) (d) =βE x∼ρ,a∼π ref (·|x) h log π t+1 (a|x) π r ∗ (a|x) i −E x∼ρ,a (1) ∼π t+1 (·|x),a (−1) ∼π ref (·|x) [f π t+1 (x,a (1) ,a (−1) )] (e) ≤βE x∼ρ,a∼π ref (·|x) h log π t+1 (a|x) π r ∗ (a|x) i + ηt 2 (3 + e R ) 2 I t + 1 2ηt(3 + e R ) 2 n R 2 + t X i=1 E x∼ρ,a (1) ∼π i (·|x),a (−1) ∼π ref (·|x) [f 2 π t+1 (x,a (1) ,a (−1) )] o (f ) ≤ ηt 2 (3 + e R ) 2 I t + 1 2ηt + 4R r 2 t log h 4TN ε (R) δ i + 2 ηt log 2T|N ε (R)| δ + 4ε + 4ε η + 5 4ηt t X i=1 |ξ ∗ i |, where (a) uses Eq.(20), (b) uses Eq.(14)which implies thatr ∗ (x,a)−ω|a|−β log π r ∗ (a|x) π ref (a|x) = β logZ r ∗ (x) does not rely ona, (c) uses Eqs.(16), (d) uses Eq.(46), (e) applies Cauchy-Schwartz inequality to Eq.(56), (f) uses Eq.(78)and3 + e R > R > 0. Finally, we conclude the proof by averaging the above inequality over t∈1, 2,...,T as follows. E J β,ω (π r ∗ )− J β,ω (π b T ) = 1 T T X t=1 J β,ω (π r ∗ )− J β,ω (π t+1 ) (a) ≤ 6ηG on (3 + e R ) 2 log(T + 2) + 3 logT 2ηT + 8R r 2 T log h 4TN ε (R) δ i + 6 logT Tη log 2T|N ε (R)| δ + 4ε + 4ε η + 15 logT 4Tη T X i=1 |ξ ∗ i | (b) ≤6(3 + e R ) log(T + 2) r G on T h log 4T|N 1/T (R)| δ +∥ξ ∗ ∥ 1 i + 3(3 + e R )(logT ) √ G on 2 q T log[2TN 1/T (R)/δ] + 8R r 2 T log h 4TN 1/T (R) δ i + 6(3 + e R )(logT ) r G on T log 4T|N 1/T (R)| δ + 4 T + 4(3 + e R ) s G on T log[2TN 1/T (R)/δ] + 15(3 + e R )(logT ) √ G on 4 q T log 42TN 1/T (R)/δ] + T∥ξ ∗ ∥ 1 ∥ξ ∗ ∥ 1 35 (c) ≤(6 + 1.5 + 8 √ 2 + 6 + 4 + 4)(3 + e R )(logT ) r G on T h log 4T|N 1/T (R)| δ +∥ξ ∗ ∥ 1 i + 15(3 + e R )(logT ) √ G on 4 q T log[4TN 1/T (R)/δ] + T∥ξ ∗ ∥ 1 log[4TN 1/T (R)/δ] +∥ξ ∗ ∥ 1 ≤37(3 + e R )(logT ) r G on T h log 4T|N 1/T (R)| δ +∥ξ ∗ ∥ 1 i , where (a) uses P T t=1 1 t ≤ 1+logT ≤ 3 logT, P T t=1 1 √ t ≤ 2 √ Tand Eq.(57), (b) usesη = √ log[4TN 1/T (R)/δ]+∥ξ ∗ ∥ 1 (3+e R ) √ TG on , ε = 1 T , and (c) usesG on ≥ 1(by Eq.(26)),R < 3 + e R ,log(T + 2) ≤ 2 logTandlog 4T|N 1/T (R)| δ ≥ logT ≥ 1. 36