Paper deep dive

Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer

Zhihan Liu, Miao Lu, Shenao Zhang, Boyi Liu, Hongyi Guo, Yingxiang Yang, Jose Blanchet, Zhaoran Wang

Year: 2024Venue: arXiv preprintArea: Alignment TrainingType: TheoreticalEmbeddings: 257

Models: Zephyr-7b-beta, Zephyr-7b-gemma

Intelligence

Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 97%

Last extracted: 3/12/2026, 7:44:49 PM

Summary

The paper addresses the problem of reward overoptimization in Reinforcement Learning from Human Feedback (RLHF) for Large Language Models (LLMs). It identifies the root cause as distributional shift and uncertainty in reward modeling. The authors propose a theoretical algorithm that uses an adversarial reward penalty to mitigate overoptimization and derive a practical, easy-to-implement objective called Regularized Preference Optimization (RPO), which combines Direct Preference Optimization (DPO) loss with a Supervised Fine-Tuning (SFT) loss. Theoretical analysis and empirical evaluations on LLM benchmarks demonstrate that RPO effectively mitigates overoptimization and improves alignment performance.

Entities (5)

Direct Preference Optimization · algorithm · 100%Regularized Preference Optimization · algorithm · 100%Reinforcement Learning from Human Feedback · methodology · 100%Bradley-Terry model · mathematical-model · 95%Supervised Fine-Tuning · methodology · 95%

Relation Signals (4)

Regularized Preference Optimization → combines → Direct Preference Optimization

confidence 100% · this objective fuses the direct preference optimization (DPO) loss with the supervised fine-tuning (SFT) loss

Regularized Preference Optimization → combines → Supervised Fine-Tuning

confidence 100% · this objective fuses the direct preference optimization (DPO) loss with the supervised fine-tuning (SFT) loss

Regularized Preference Optimization → mitigates → Overoptimization

confidence 95% · RPO effectively alleviates overoptimization.

RLHF → suffersfrom → Overoptimization

confidence 95% · Aligning generative models with human preference via RLHF typically suffers from overoptimization

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:Aligning generative models with human preference via RLHF typically suffers from overoptimization, where an imperfectly learned reward model can misguide the generative model to output undesired responses. We investigate this problem in a principled manner by identifying the source of the misalignment as a form of distributional shift and uncertainty in learning human preferences. To mitigate overoptimization, we first propose a theoretical algorithm that chooses the best policy for an adversarially chosen reward model; one that simultaneously minimizes the maximum likelihood estimation of the loss and a reward penalty term. Here, the reward penalty term is introduced to prevent the policy from choosing actions with spurious high proxy rewards, resulting in provable sample efficiency of the algorithm under a partial coverage style condition. Moving from theory to practice, the proposed algorithm further enjoys an equivalent but surprisingly easy-to-implement reformulation. Using the equivalence between reward models and the corresponding optimal policy, the algorithm features a simple objective that combines: (i) a preference optimization loss that directly aligns the policy with human preference, and (ii) a supervised learning loss that explicitly imitates the policy with a (suitable) baseline distribution. In the context of aligning large language models (LLM), this objective fuses the direct preference optimization (DPO) loss with the supervised fine-tuning (SFT) loss to help mitigate the overoptimization towards undesired responses, for which we name the algorithm Regularized Preference Optimization (RPO). Experiments of aligning LLMs demonstrate the improved performance of RPO compared with DPO baselines. Our work sheds light on the interplay between preference optimization and SFT in tuning LLMs with both theoretical guarantees and empirical evidence.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

256,405 characters extracted from source content.

Expand or collapse full text

Provably Mitigating Overoptimization in RLHF: Your SFT Loss is Implicitly an Adversarial Regularizer Zhihan Liu Miao Lu11footnotemark: 1 Shenao Zhang22footnotemark: 2 Boyi Liu Hongyi Guo22footnotemark: 2 Yingxiang Yang44footnotemark: 4 Jose Blanchet33footnotemark: 3 Zhaoran Wang22footnotemark: 2 Equal contributions.Northwestern University.zhihanliu2027,shenaozhang2028,hongyiguo2025@u.northwestern.edu,zhaoranwang@gmail.comStanford University. miaolu, jose.blanchet@stanford.eduByteDance Inc. boyi.liu01, yingxiang.yang@bytedance.com (December 4, 2024; December 4, 2024) Abstract Aligning generative models with human preference via RLHF typically suffers from overoptimization, where an imperfectly learned reward model can misguide the generative model to output undesired responses. We investigate this problem in a principled manner by identifying the source of the misalignment as a form of distributional shift and uncertainty in learning human preferences. To mitigate overoptimization, we first propose a theoretical algorithm that chooses the best policy for an adversarially chosen reward model; one that simultaneously minimizes the maximum likelihood estimation of the loss and a reward penalty term. Here, the reward penalty term is introduced to prevent the policy from choosing actions with spurious high proxy rewards, resulting in provable sample efficiency of the algorithm under a partial coverage style condition. Moving from theory to practice, the proposed algorithm further enjoys an equivalent but surprisingly easy-to-implement reformulation. Using the equivalence between reward models and the corresponding optimal policy, the algorithm features a simple objective that combines: (i) a preference optimization loss that directly aligns the policy with human preference, and (i) a supervised learning loss that explicitly imitates the policy with a (suitable) baseline distribution. In the context of aligning large language models (LLM), this objective fuses the direct preference optimization (DPO) loss with the supervised fine-tuning (SFT) loss to help mitigate the overoptimization towards undesired responses, for which we name the algorithm Regularized Preference Optimization (RPO). Experiments of aligning LLMs demonstrate the improved performance of RPO compared with DPO baselines. Our work sheds light on the interplay between preference optimization and SFT in tuning LLMs with both theoretical guarantees and empirical evidence. Keywords: Alignment, reinforcement learning from human feedback, large language model, overoptimization, supervised fine-tuning Contents 1 Introduction 1.1 Our Contributions 1.2 Related Works 2 Preliminaries of RLHF 3 A Theory-motivated Objective 4 An Equivalent and Implementation-friendly Objective 5 Theoretical Analysis 5.1 Establishing the Sample Complexity of Maximin Objective (Algorithm 1) 5.2 Equivalence between Maximin and Minimax Objectives 5.3 Generalization to New Prompt Distributions 6 Experiments 7 Conclusions A Further Discussions B Proofs for Sample Complexity Analysis B.1 Concepts B.2 Proof of Theorem 5.3 B.3 Technical Lemmas C Proofs for Equivalence between Maximin and Minimax Objectives C.1 Proof of Theorem 5.6 C.2 Auxiliary Lemmas D Proofs for Generalization to New Prompt Distributions E Additional Details on Experiments E.1 Training Details E.2 Evaluation Details E.3 Additional Results on Experiments F Experiments on Math, Reasoning, and Coding Tasks F.1 Experimental Details F.2 Experimental Results 1 Introduction A key step in building state-of-the-art LLMs is Reinforcement Learning from Human Feedback (RLHF) (Christiano et al., 2017; Ziegler et al., 2019), which aligns pretrained LLMs with human preferences using human assessment data, making the model more helpful, truthful, and harmless (Ouyang et al., 2022; Casper et al., 2023). Without doing RLHF, pretrained LLMs could exhibit harmful behaviors including offensive or toxic outputs, social biases, and leaking sensitive information from training data, etc (Gehman et al., 2020; Carlini et al., 2021; Ganguli et al., 2022). Typically, RLHF first learns a reward model from data (pair-wise comparisons of responses) to quantify the human preferences of LLM outputs. Then it fine-tunes the LLM to maximize the learned reward using RL techniques. In this pipeline, a crucial challenge is reward overoptimization or reward hacking (Michaud et al., 2020; Tien et al., 2022; Gao et al., 2023). Since the reward model is learned from finite data, this reward might not be perfectly aligned with the underlying human preference. Optimizing the LLM towards such an imperfectly learned and potentially overfitted reward model leads to performance degeneration and a substantial decrease in the probability of choosing the preferred responses in the data (Hong et al., 2024; Rafailov et al., 2024). Given the importance of RLHF and the outlined challenge, a crucial research question is: How to mitigate reward overoptimization in RLHF in a principled and efficient manner for better alignment? To answer the question, we model RLHF as an offline contextual bandit (Ouyang et al., 2022) and ascribe overoptimzation to distributional shifts and reward uncertainty. Intuitively, when fine-tuning an LLM, the response (action) distribution of the tuned LLM could deviate from that of the training data. For the out-of-distribution responses, which are dissimilar with (or not well covered by) the responses in the data, the high inherent uncertainty of underlying human preferences could make the learned reward model misleading for out-of-distribution responses. In this situation, reward overoptimization can occur because the LLM is fine-tuned towards maximizing a reward model with defective out-of-distribution prediction, giving a potential consequence that the LLM responses are favored by the learned reward but less preferred by a human (Zhu et al., 2024). We illustrate such an issue inherent to overoptimization in Figure 1. In this work, we propose a new RLHF algorithm to mitigate reward overoptimization. From a high level, our theoretical algorithm seeks the best LLM for an adversarially chosen reward model that minimizes the sum of its maximum likelihood estimation (MLE) loss and its own expected reward value. Intuitively, since the reward value is also minimized when minimizing the sum, it can automatically prevent the misleadingly high reward caused by the uncertainty inherent in learning from finite preference data. Furthermore, we show that the theoretical algorithm enjoys an easy implementation: it simply adopts a supervised fine-tuning (SFT) loss as a regularizer during training. By explicitly regularizing the LLM to imitate high-quality responses (e.g., the preferred responses in dataset), the algorithm can effectively mitigate the issue of overoptimization. We provide both theory and experiments to demonstrate our findings, which we summarize next. action a b c r⋆superscript⋆r r⋆ 1 0.5 0 Dataset =(a,b,1)1D=\(a,b,1)\D = ( a , b , 1 ) πrefsuperscriptrefπ^refπroman_ref 0.450.450.450.45 0.450.450.450.45 0.10.10.10.1 πDPOsuperscriptDPOπ^DPOπroman_DPO 0.50.50.50.5 00 0.5 πRPOsuperscriptRPOπ^RPOπroman_RPO 1.01.0 [rgb]0,0,1 [named]pgfstrokecolorrgb0,0,1 1.01.0 00 00 Figure 1: Left: Reward overoptimization due to distributional shift and uncertainty in reward. Middle: Overoptimization can cause the probability of outputting the preferred responses from preference data to decrease substantially using original DPO proposed by (Rafailov et al., 2023). Our algorithm (RPO) can significantly alleviate this decrease. See more discussions in Section 6. Right: For the illustration of the intuition behind the success of RPO, we give a simple example with no prompts and only three responses a, b, and c (Xu et al., 2024). The dataset DD only consists of a single data point where response a is preferred than response b (as indicated by the label 1111). Writing out the DPO loss, one needs to minimize log⁡(1+(π⁢(b)/π⁢(a))β)1superscript (1+(π(b)/π(a))^β)log ( 1 + ( π ( b ) / π ( a ) )β ) for 0≤π⁢(a)+π⁢(b)≤1010≤π(a)+π(b)≤ 10 ≤ π ( a ) + π ( b ) ≤ 1, which gives π⁢(b)=00π(b)=0π ( b ) = 0 and leaves π⁢(a)π(a)π ( a ) arbitrary. Thus possible solutions to DPO objective would bring out non-zero probabilities of response c that is not desirable since r⋆⁢(c)=0superscript⋆0r (c)=0r⋆ ( c ) = 0. In contrast RPO objective simultaneously maximizes another term log⁡π⁢(a) π(a)log π ( a ) as regularizer, avoiding the output of response c. 1.1 Our Contributions We summarize our contributions in three areas as follows. A theoretical algorithm under general function approximation. Our first contribution is a new theoretical algorithm (Algorithm 1). It features an unconstrained maximin problem, outputting the optimal policy (LLM) against an adversarially chosen reward model that minimizes the summation of: (a) the MLE loss for estimating the underlying reward; and (b) a reward expected value term as a penalty that aims to prevent spuriously high reward estimation caused by data uncertainty and insufficient coverage. Algorithm 1 is compatible with general function approximations of the reward model, meaning that we do not impose any specific structural form to the hypothesis class of reward, demonstrating its generality. In this regime, we establish the finite-sample suboptimality gap of Algorithm 1 as ~⁢(Ccoverage2⁢ℛ/N)~subscriptsuperscript2coveragesubscriptℛ O(C^2_coverage N_R% /N)over~ start_ARG O end_ARG ( C2roman_coverage square-root start_ARG Ncaligraphic_R / N end_ARG ) when competing with any LLM in terms of the underlying human reward (Theorem 5.3). Here N denotes the number of human comparison data. ℛsubscriptℛN_RNcaligraphic_R denotes the complexity of the reward model class ℛRR, and CcoveragesubscriptcoverageC_coverageCroman_coverage characterizes the coverage of the preference dataset with respect to the response distribution of the LLM to compete (please see Assumption 5.2 for details). This indicates that, as long as the training data well cover the LLM π to compete, the algorithm is guaranteed to align an LLM to output responses as good as π in terms of human reward, without suffering from overoptimization caused by distributional shifts and inherent uncertainty in human preference. An easy-to-implement practical objective. Moving towards practice, we show that the objective of Algorithm 1 adopts a surprisingly simple and equivalent form for its use in practice. Specifically, with mild regularity conditions, we prove that the maximin objective (Algorithm1) is equivalent to the corresponding minimax objective, which is further reduced to a single minimization problem for the reward model since its inner problem adopts a closed form solution. Inspired by recent RLHF research that uses reward-model-free methods to align LLMs (Rafailov et al., 2023), we further re-parameterize the reward model via its corresponding KL-regularized optimal policy. Then the minimization objective of the reward modeling naturally translates to a target that directly aligns the LLM, which we call Regularized Preference Optimization (RPO; Algorithm 2). The objective of RPO features a simple weighted combination of two losses: RPO objective=Preference optimization loss+Imitation (SFT) loss.RPO objectivePreference optimization lossImitation (SFT) loss [rgb]0,0,0 [named]pgfstrokecolorrgb0,0,0% @color@gray@stroke0 @color@gray@fill0RPO objective\,% =\, [rgb]0.45,0.45,1 [named]pgfstrokecolorrgb% 0.45,0.45,1Preference optimization loss\,+\, [rgb]% 0.8625,0.45,0.5875 [named]pgfstrokecolorrgb0.8625,0.45,0.5875% Imitation (SFT) loss.RPO objective = Preference optimization loss + Imitation (SFT) loss . (1.1) Here the Preference optimization loss coincides with the DPO (Rafailov et al., 2023) objective, which tends to optimize the LLM towards maximizing the underlying true reward. The Imitation (SFT) loss explicitly supervises the LLM to mimic the responses from a proper distribution that is well covered by the dataset. The choice of the distribution is guided and justified by our theory of Algorithm 1, but can also be flexibly adapted in practice, e.g., the preferred response in the dataset, or the responses of the initial model. We highlight that the Imitation (SFT) loss serves as an important term to mitigate overoptimization. Even though the original DPO objective has already involved a KL regularization between the tuned LLM and the initial LLM, is not enough to prevent overoptimization. As elaborated in Section 4, the KL-regularization weight of the DPO objective could only control the scale of the gradient per training example, while the RPO objective can further modify the gradient direction. Calling back to the theoretical Algorithm 1, such a modification of gradient direction originates from the reward penalty in the adversarial objective for the reward model. This modification, as we expose in our theoretical analysis, helps to mitigate overoptimization. Thus, incorporating SFT loss in RLHF gives you a regularizer that provably mitigates overoptimization. Empirical evaluations. Following the training setup of two series of released chat models Zephyr-7b-beta (trained on Ultrafeedback dataset (Cui et al., 2023) using DPO) and Zephyr-7b-gemma (trained on Argilla-DPO-Mix-7K dataset (argill, 2024) using DPO) (Tunstall et al., 2023b), we implement RPO for the beta series and gemma series respectively to show that: (i) RPO is a flexible plug-in module and can be applied to different reference models. (i) RPO effectively alleviates overoptimization. (i) RPO consistently achieves better alignment performance than DPO in in-data distribution. (iv) RPO can also achieve consistently better performance in standard LLM benchmarks like MT-bench and AlpacaEval 2.0, which shows its potential of mitigating overoptimization for better alignment performance, justifying our theory. 1.2 Related Works In the following, we relate our work to recent lines of RLHF research on both theory and practice sides. We also review related works on reward hacking and overoptimization in RLHF. RLHF: algorithm design. The technique of RLHF (Christiano et al., 2017; Ziegler et al., 2019; Ouyang et al., 2022; Bai et al., 2022) has recently demonstrated its great importance in building the state-of-the-art LLMs, including ChatGPT (Achiam et al., 2023), Gemini (Team et al., 2023), Claude (Anthropic, 2023). In the RLHF pipeline therein, the LLM is fine-tuned towards maximizing a learned reward model using the RL algorithm Proximal Policy Optimization (PPO; Schulman et al. (2017)). Meanwhile, PPO-style algorithm is also known for its instability, sample-inefficiency, and especially, a high demand for proper hyperparameter tuning (Engstrom et al., 2020). This thus casts prohibitive computational cost to make the most effectiveness of PPO-based RLHF methods to align LLMs, especially for the open-source community. Given that, further research on RLHF has explored various alternatives to PPO-based methods, with the most popular approach being the direct preference optimization method (Zhao et al., 2023; Rafailov et al., 2023), which skips the reward learning phase and directly optimize the LLM to align it with the human preference. Our practical implementation (RPO) also harnesses the wisdom of reward-LLM equivalence to avoid explicit reward learning followed by PPO training. Besides the original DPO algorithm (Rafailov et al., 2023), ever since it popularizing the direct preference learning style method, variants of the direct preference learning approach are proposed, including but not limited to Liu et al. (2023a); Azar et al. (2023); Xiong et al. (2023); Tang et al. (2024); Ji et al. (2024); Ye et al. (2024); Pal et al. (2024); Hong et al. (2024); Rosset et al. (2024); Liang et al. (2024); Zhang et al. (2024a); Tajwar et al. (2024); Wu et al. (2024). Each of them aims to address further challenges of direct preference learning from varying perspectives. Specifically, the algorithm proposed by Pal et al. (2024); Hong et al. (2024) share similar algorithmic components as RPO proposed in this work. Both work consider SFT style regularization during preference optimization. However, theoretical understanding of how SFT loss can help alignment remains unknown. In contrast, we provide theoretical justifications to the SFT loss as an implicit adversarial regularizer that provably mitigates overoptimization in preference learning. RLHF: theoretical investigation. Initiated from the literature of dueling bandits and dueling RL (Yue et al., 2012; Bengs et al., 2021; Pacchiano et al., 2021), recent success of RLHF in fine-tuning LLMs also motivates a long line of research to investigate the theoretical foundations of RLHF under different settings (Chen et al., 2022; Zhu et al., 2023; Zhan et al., 2023a, b; Wang et al., 2023b; Li et al., 2023; Xiong et al., 2023; Ye et al., 2024; Du et al., 2024; Zhong et al., 2024), aiming to propose provably sample-efficient algorithms to learn a human-reward-maximizing policy from human preference signals. Our theoretical study of RLHF falls into the paradigm of offline learning from a pre-collected preference dataset, and is most related to Zhu et al. (2023); Zhan et al. (2023a); Li et al. (2023); Xiong et al. (2023); Ye et al. (2024). In this setup, the main challenge is to address the overoptimization issues due to human reward uncertainty and distributional shifts when only a fixed dataset is available. In the sequel, we compare our work with them in more detail. Existing theoretical work on provably sample-efficient offline RLHF typically suffers from two drawbacks: they are either restricted to the linear function approximations setting (Zhu et al., 2023; Xiong et al., 2023) which is far from the practical situations, or are generally unable to be implemented in the LLM experiments. Typically, to encompass the pessimistic principle in the face of uncertainty, the existing literature proposes to return the optimal policy against either an estimated reward model plus a structure-aware reward uncertainty penalty (Xiong et al., 2023) or the most pessimistic reward model inside a confidence region (Zhu et al., 2023; Zhan et al., 2023a). Both of these two types of method involve intractable components for implementation and needs for additional algorithmic design to approximate the theoretical algorithm in practice. In contrast, our theory works in the context of general function approximations while being friendly to be implemented. Finally, we remark that, while our study focuses on the standard Bradley-Terry model of human preference with general reward function approximations, the work of Ye et al. (2024) further considers a general human preference model. But it remains unknown how their algorithms can be efficiently implemented in practice. It serves as an interesting direction to extend our technique to RLHF with general reward model and device new practical algorithms. Finally, we mention that the algorithm design of RPO is also related to the “pessimism” principle in the standard offline RL literature. It proposes to maintain a pessimistic estimate of the policy values or constrain the policy not to take unseen actions in the data to handle the challenge of the insufficient coverage of the dataset, e.g., Jin et al. (2021); Uehara and Sun (2021); Xie et al. (2021a, b); Rashidinejad et al. (2021); Yin and Wang (2021); Fu et al. (2022); Xiong et al. (2022); Liu et al. (2022a, b); Shi et al. (2022); Zhan et al. (2022); Lu et al. (2022); Rashidinejad et al. (2022); Shi and Chi (2024); Blanchet et al. (2024). In contrast, we consider the offline RLHF problem and the techniques to obtain the objective of our algorithm along with its sample complexity analysis are new and different from these prior works on standard offline RL. Reward hacking and overoptimization in RLHF for LLM. As is discussed in the introduction, the challenge of reward hacking or overoptimization may prevent the successful alignment of LLMs, degenerating the performance of an LLM because of maximizing an imperfect, overfitted, and misgeneralized proxy reward learned from the finite data (Michaud et al., 2020; Tien et al., 2022; Gao et al., 2023; Casper et al., 2023). Efforts have been made to mitigate this fundamental issue through the perspective of theory, e.g., Zhu et al. (2023); Xiong et al. (2023); Zhu et al. (2024), and practice, e.g., Coste et al. (2023); Eisenstein et al. (2023); Dong et al. (2023); Moskovitz et al. (2023); Zhang et al. (2024b); Rita et al. (2024); Pal et al. (2024); Hong et al. (2024). Our approach starts from the theoretical insights of handling inherent uncertainty in learning human preference from finite data, while being suprisingly easy to implement in practice. 2 Preliminaries of RLHF In this section, we introduce the mathematical framework of studying RLHF for alignining LLMs. We adopt the framework of offline contextual bandits (Ouyang et al., 2022; Zhu et al., 2023, 2024), where we identify the contextual space XX as the space of prompts, and we identify the action space AA as the space of responses. An LLM, which is defined as a policy π(⋅|⋅):↦Δ()π(·|·):X (A)π ( ⋅ | ⋅ ) : X ↦ Δ ( A ), can take a prompt x∈x ∈ X as its input and output a response a∈a ∈ A obeying a∼π(⋅|x)a π(·|x)a ∼ π ( ⋅ | x ). Preference model. Given any reward function r:×↦ℝ:maps-toℝr:X×A : X × A ↦ blackboard_R belonging to certain reward class ℛRR which represents the “human’s rating” of LLM responses given some prompts, we consider the Bradley-Terry model (Bradley and Terry, 1952) of human preference. That is, given a prompt x∈x ∈ X and two responses a1,a0∈superscript1superscript0a^1,a^0 1 , a0 ∈ A, the probability of a1superscript1a^1a1 being preferred to a0superscript0a^0a0 (denoted by y=11y=1y = 1, otherwise y=00y=0y = 0) is given by ℙr⁢(y=1|x,a1,a0)=exp⁡(r⁢(x,a1))exp⁡(r⁢(x,a1))+exp⁡(r⁢(x,a0))=σ⁢(r⁢(x,a1)−r⁢(x,a0)),subscriptℙconditional1superscript1superscript0superscript1superscript1superscript0superscript1superscript0 _r(y=1|x,a^1,a^0)= (r(x,a^1)) (r(% x,a^1))+ (r(x,a^0))=σ (r(x,a^1)-r(x,a^0) ),blackboard_Pr ( y = 1 | x , a1 , a0 ) = divide start_ARG exp ( r ( x , a1 ) ) end_ARG start_ARG exp ( r ( x , a1 ) ) + exp ( r ( x , a0 ) ) end_ARG = σ ( r ( x , a1 ) - r ( x , a0 ) ) , (2.1) where σ⁢(z)=1/(1+exp⁡(−z))11σ(z)=1/(1+ (-z))σ ( z ) = 1 / ( 1 + exp ( - z ) ) is the sigmoid function. For simplicity of future discussion, we explicitly write out the dependence of the preference probability ℙr⁢(⋅)subscriptℙ⋅P_r(·)blackboard_Pr ( ⋅ ) on the reward model r∈ℛr ∈ R. In the section of theory, i.e., Section 5, we specify the assumptions on the reward model class ℛRR. Learning protocol. Typically in an LLM training pipeline, the RLHF phase starts from certain reference policy πrefsuperscriptrefπ^refπroman_ref which is obtained by pretraining and then supervised fine-tuning (SFT). Then RLHF aligns the LLM based on certain human preference data. In this work, we consider offline RLHF setup where the LLM is aligned using a fixed offline preference dataset DD. It consists of N i.i.d. tuples in the form of =(xi,ai1,ai0,yi)i=1N.superscriptsubscriptsubscriptsubscriptsuperscript1subscriptsuperscript0subscript1 = \(x_i,a^1_i,a^0_i,y_i) \_i=% 1^N.D = ( xitalic_i , a1italic_i , a0italic_i , yitalic_i ) i = 1N . (2.2) Here the prompt xisubscriptx_ixitalic_i and the response ai1,ai0superscriptsubscript1superscriptsubscript0a_i^1,a_i^0aitalic_i1 , aitalic_i0 are distributed according to (x,a1,a0)∼μ⁢(⋅)similar-tosuperscript1superscript0subscript⋅(x,a^1,a^0) _D(·)( x , a1 , a0 ) ∼ μcaligraphic_D ( ⋅ ), and conditioning on (xi,ai1,ai0)subscriptsuperscriptsubscript1superscriptsubscript0(x_i,a_i^1,a_i^0)( xitalic_i , aitalic_i1 , aitalic_i0 ), yisubscripty_iyitalic_i is distributed according to (2.1) for an underlying true (but unknown) reward model r⋆∈ℛsuperscript⋆ℛr ⋆ ∈ R. Performance metric. The target of RLHF is to align an LLM, or equivalently, to learn a policy π, so as to maximize the expected true reward r⋆superscript⋆r r⋆. Correspondingly, we define the value function of a policy π as J⁢(π)=x∼d0,a∼π(⋅|x)⁢[r⋆⁢(x,a)]. J(π)=E_x d_0,a π(·|x) [r % (x,a) ].J ( π ) = blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 , a ∼ π ( ⋅ | x ) end_POSTSUBSCRIPT [ r⋆ ( x , a ) ] . (2.3) Here we allow the prompt distribution d0⁢(⋅)subscript0⋅d_0(·)d0 ( ⋅ ) to be different from that of the offline dataset distribution μ⁢(⋅)subscript⋅ _D(·)μcaligraphic_D ( ⋅ ), but is assumed to be known. In the meanwhile, we consider the policies that share the same support as the reference policy πrefsuperscriptrefπ^refπroman_ref, that is, we take a policy class Π Π as Π=π:↦Δ()|Supp(π(⋅|x))⊆Supp(πref(⋅|x)),∀x∈. = \π:X (A)\, |\,% Supp(π(·|x)) (π^ref(·|x))% ,\,\,∀ x \.Π = π : X ↦ Δ ( A ) | Supp ( π ( ⋅ | x ) ) ⊆ Supp ( πroman_ref ( ⋅ | x ) ) , ∀ x ∈ X . (2.4) The performance gap of a learned policy π^∈Π^Π π∈ start_ARG π end_ARG ∈ Π with respect to any other policy π∈Ππ∈ π ∈ Π is measured as Gapπ⁢(π^)=J⁢(π)−J⁢(π^).superscriptGap^ ^π( π)=J(π)-J( π).Gapitalic_π ( over start_ARG π end_ARG ) = J ( π ) - J ( over start_ARG π end_ARG ) . (2.5) Our goal is to propose a sample-efficient and also implementation-friendly algorithm to learn a policy π^∈Π^Π π∈ start_ARG π end_ARG ∈ Π that can compete with a given policy π∈Ππ∈ π ∈ Π in terms of Gapπ⁢(π^)≤εsuperscriptGap^Gap^π( π)≤ _π ( over start_ARG π end_ARG ) ≤ ε, using a number of samples polynomial in 1/ε11/ 1 / ε and logarithmic in the complexity of the reward class ℛRR and the failure probability inversed 1/δ11/ 1 / δ. We do not assume parametric forms of the reward class ℛRR (Zhu et al., 2023; Xiong et al., 2023), and thus we fall into the paradigm of general function approximations. 3 A Theory-motivated Objective Our method seeks to find the best policy π^ πover start_ARG π end_ARG against an adversarially chosen reward model r^advsubscript^adv r_advover start_ARG r end_ARGadv that minimizes a weighted sum of its expected value and the maximum likelihood estimation (MLE) loss. Intuitively, such a reward model can prevent the overoptimization issue by taking its own value into account when minimizing the MLE loss. Since the reward value is also minimized when minimizing the sum, this method prevents the misleadingly high reward caused by the uncertainty due to finite data. Formally, given two hyperparameters β,η>00β,η>0β , η > 0 and a “baseline policy” πbasesuperscriptbaseπ^baseπroman_base, we define Tβ,ηadv(π)=minr∈ℛη⋅x∼d0,a1∼π(⋅|x),a0∼πbase(⋅|x)[r(x,a1)−r(x,a0)−β⋅KL(π(⋅|x)∥πref(⋅|x))]+ℒ(r), T_β,η^adv(π)= _r \% η·E_ subarraycx d_0,a^1 π(·|x),\\ a^0 π^base(·|x) subarray [r(x,a^1)-r(x,a^0% )-β·KL (π(·|x)\|π^ref(·|x) )% ]+L_D(r) \,Titalic_β , ηroman_adv ( π ) = minitalic_r ∈ R η ⋅ blackboard_Estart_ARG start_ROW start_CELL x ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ π ( ⋅ | x ) , end_CELL end_ROW start_ROW start_CELL a0 ∼ πroman_base ( ⋅ | x ) end_CELL end_ROW end_ARG end_POSTSUBSCRIPT [ r ( x , a1 ) - r ( x , a0 ) - β ⋅ KL ( π ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] + Lcaligraphic_D ( r ) , (3.1) where the loss function ℒ⁢(⋅)subscriptℒ⋅L_D(·)Lcaligraphic_D ( ⋅ ) is the average negative log-likelihood function of the BT model (2.1) (and here it becomes the cross-entropy loss) over the preference dataset DD, defined as ℒ⁢(r)=−^⁢[yi⁢log⁡(σ⁢(r⁢(xi,ai1)−r⁢(xi,ai0)))+(1−yi)⁢log⁡(σ⁢(r⁢(xi,ai0)−r⁢(xi,ai1)))].subscriptℒsubscript^delimited-[]subscriptsubscriptsubscriptsuperscript1subscriptsubscriptsuperscript01subscriptsubscriptsubscriptsuperscript0subscriptsubscriptsuperscript1 _D(r)=- E_D% [y_i (σ (r(x_i,a^1_i)-r(x_i,a^0_i) % ) )+(1-y_i) (σ (r(x_i,a^0_i)-r(x_i,a^1_% i) ) ) ].Lcaligraphic_D ( r ) = - over start_ARG blackboard_E end_ARGD [ yitalic_i log ( σ ( r ( xitalic_i , a1italic_i ) - r ( xitalic_i , a0italic_i ) ) ) + ( 1 - yitalic_i ) log ( σ ( r ( xitalic_i , a0italic_i ) - r ( xitalic_i , a1italic_i ) ) ) ] . (3.2) As we can see, Tβ,ηadv⁢(π)superscriptsubscriptadvT_β,η^adv(π)Titalic_β , ηroman_adv ( π ) is the minimum value of a weighted sum of the MLE loss and the expected reward value of π, but with two important modifications that we explain in the following. Firstly, we subtract another expected reward of certain policy πbasesuperscriptbaseπ^baseπroman_base. This is because the BT model (2.1) essentially only uses the reward differences to define the preference probabilities. As a result, the data can only reveal information of the differences between the true reward r⋆superscript⋆r r⋆ of different responses (Zhan et al., 2023a). Accordingly, we subtract a baseline expected reward value to match this observation. The choice of the baseline policy is discussed in the theory part (Section 5) and experiments (Section 6). Secondly, we subtract a KL divergence between π and πrefsuperscriptrefπ^refπroman_ref from the expected reward, weighted by the coefficient β>00β>0β > 0. Such a term is for practical considerations that would be explained in Sections 4 and 5.2. We note that the KL regularized reward is commonly adopted in RLHF practice to ensure the learned policy is not far away from the reference policy (Ouyang et al., 2022; Xiong et al., 2023). Algorithm 1 Theoretical Algorithm: Maximin Objective 1: Input: Preference dataset DD, parameters β,η>00β,η>0β , η > 0, reference policy πrefsuperscriptrefπ^refπroman_ref, baseline policy πbasesuperscriptbaseπ^baseπroman_base. 2: Output: Policy π^ πover start_ARG π end_ARG given by (3.3) with the cross-entropy loss function ℒsubscriptℒL_DLcaligraphic_D defined in (3.2). Finally, the overall algorithm design (Algorithm 1) is to output the policy that maximizes Tβ,ηadv⁢(π)superscriptsubscriptadvT_β,η^adv(π)Titalic_β , ηroman_adv ( π ), i.e., π^∈argmaxπ∈ΠTβ,ηadv⁢(π)^subscriptargmaxΠsuperscriptsubscriptadv π∈ argmax_π∈ T_β,η^% adv(π)over start_ARG π end_ARG ∈ argmaxitalic_π ∈ Π Titalic_β , ηroman_adv ( π ), which gives the following theoretical target: π^∈argmaxπ∈Πminr∈ℛη⋅x∼d0,a1∼π(⋅|x),a0∼πbase(⋅|x)[r(x,a1)−r(x,a0)−β⋅KL(π(⋅|x)∥πref(⋅|x))]+ℒ(r). \!\!\!\!\!\!\!\! π∈ argmax_π∈% \, _r \η·E_ subarraycx% d_0,a^1 π(·|x),\\ a^0 π^base(·|x) subarray [r(x,a^1)-r(x,a^0% )-β·KL (π(·|x)\|π^ref(·|x) )% ]+L_D(r) \.over start_ARG π end_ARG ∈ argmaxitalic_π ∈ Π minitalic_r ∈ R η ⋅ blackboard_Estart_ARG start_ROW start_CELL x ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ π ( ⋅ | x ) , end_CELL end_ROW start_ROW start_CELL a0 ∼ πroman_base ( ⋅ | x ) end_CELL end_ROW end_ARG end_POSTSUBSCRIPT [ r ( x , a1 ) - r ( x , a0 ) - β ⋅ KL ( π ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] + Lcaligraphic_D ( r ) . (3.3) Given the form of (3.3), we name it the maximin objective in the sequel. Upon seeing (3.3), one might be arguing that such a theory-motivated objective seems hard to implement in practice. Nevertheless, in the coming Section 4, we demonstrate that the maximin objective (3.3) adopts an easy-to-implement equivalent form, allowing us to design a practical algorithm for aligning LLMs. Remark 3.1 (Comparison with Zhan et al. (2023a)). We remark that in the work of Zhan et al. (2023a), they also mentioned a maximin object similar to (3.3) for offline preference-based RL as a complementary to their theoretical algorithm. However, the sample complexity of the maximin algorithm they presented is unknown. Furthermore, our objective (3.3) features another KL-regularization term, which is essential for the proposal of our new practical algorithm design for aligning LLM in Section 4. Remark 3.2 (Comparison with Xiong et al. (2023)). Another theoretical work on RLHF (Xiong et al., 2023) explicitly models the KL-regularization between the target policy and the reference policy in the learning objective, referred to as the KL-regularized contextual bandit. This means that their metric becomes the KL-regularized expected reward. In contrast, here we put the KL-regularization as a component of our algorithm design, but we still keep the metric as the expected reward (2.3). Therefore our theory in Section 5.1 directly reveals how the learned policy performs in terms of the expected reward compared to any given target policy. 4 An Equivalent and Implementation-friendly Objective In this section, we propose another minimax-style objective that is equivalent to the maximin objective (3.3). Based on the minimax objective, we propose a new LLM aligning algorithm called Regularized Preference Optimization (RPO). It draws inspirations from the reparametrization technique originated in Direct Preference Optimization (DPO) (Rafailov et al., 2023) and goes beyond to further address the overoptimization issue in offline RLHF by incorprating an SFT loss as an explicit adversarial regularizer. An equivalent minimax objective. If the reward model class ℛRR satisfies certain regularity conditions, which we discuss in detail in Section 5.2, the minimax theorem holds: solving the maximin objective (3.3) is equivalent to solving a minimax target, given by minr∈ℛmaxπ∈Πη⋅x∼d0,a1∼π(⋅|x),a0∼πbase(⋅|x)[r(x,a1)−r(x,a0)−β⋅KL(π(⋅|x)∥πref(⋅|x))]+ℒ(r). _r \, _π∈ \η·E% _ subarraycx d_0,a^1 π(·|x),\\ a^0 π^base(·|x) subarray [r(x,a^1)-r(x,a^0% )-β·KL (π(·|x)\|π^ref(·|x) )% ]+L_D(r) \.minitalic_r ∈ R maxitalic_π ∈ Π η ⋅ blackboard_Estart_ARG start_ROW start_CELL x ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ π ( ⋅ | x ) , end_CELL end_ROW start_ROW start_CELL a0 ∼ πroman_base ( ⋅ | x ) end_CELL end_ROW end_ARG end_POSTSUBSCRIPT [ r ( x , a1 ) - r ( x , a0 ) - β ⋅ KL ( π ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] + Lcaligraphic_D ( r ) . (4.1) Such a minimax formulation (4.1) is the starting point of our practical algorithm. The magic of (4.1) is that the inner maximization problem adopts a closed form solution, which further simplifies such an objective. To see this, note that given any reward model r∈ℛr ∈ R, the inner problem is equivalent to maxπ∈Πx∼d0,a∼π(⋅|x)[r(x,a)−β⋅KL(π(⋅|x)∥πref(⋅|x))]. _π∈ \E_x d_0,a π(·|x% ) [r(x,a)-β·KL (π(·|x)\|π^ref(% ·|x) ) ] \.maxitalic_π ∈ Π blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 , a ∼ π ( ⋅ | x ) end_POSTSUBSCRIPT [ r ( x , a ) - β ⋅ KL ( π ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] . (4.2) It has been well established that the policy that maximizes the KL-regularized expected reward (4.2) has a closed form solution. Due to its importance, we present it as the following lemma. Lemma 4.1 (Oracle optimal KL-regularized policy). Given any reward model r∈ℛr ∈ R, the optimal policy πrsubscript _rπitalic_r to the maximization problem (4.2) is given by πr(⋅|x)=1Zr⁢(x)⋅πref(⋅|x)⋅exp(β−1r(x,⋅)),Zr(x)=∫a∈exp(β−1r(x,a))dπref(a|x), _r(·|x)= 1Z_r(x)·π^ref(·|% x)· (β^-1r(x,·) ),\,\,Z_r(x)= _a % (β^-1r(x,a) )dπ^ref(a|x),πitalic_r ( ⋅ | x ) = divide start_ARG 1 end_ARG start_ARG Zitalic_r ( x ) end_ARG ⋅ πroman_ref ( ⋅ | x ) ⋅ exp ( β- 1 r ( x , ⋅ ) ) , Zitalic_r ( x ) = ∫a ∈ A exp ( β- 1 r ( x , a ) ) d πroman_ref ( a | x ) , (4.3) and correspondingly the optimal value of (4.2) is given by (⁢4.2⁢)=x∼d0⁢[β⋅log⁡(Zr⁢(x))]italic-(4.2italic-)subscriptsimilar-tosubscript0delimited-[]⋅subscript eq: kl-regularized reward=E_x d_0[β· (Z_r% (x))]italic_( italic_) = blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT [ β ⋅ log ( Zitalic_r ( x ) ) ]. Proof of Lemma 4.1. This follows directly from Proposition 7.16 and Theorem 15.3 of Zhang (2023). ∎ Specifically, by Lemma 4.1, we can solve the inner maximization problem in (4.1) and obtain that (⁢4.1⁢)=minr∈ℛ⁡η⋅x∼d0,a0∼πbase(⋅|x)⁢[−r⁢(x,a0)+β⋅log⁡(Zr⁢(x))]+ℒ⁢(r). eq: target min max= _r \η% ·E_ subarraycx d_0,a^0 π^base(% ·|x) subarray [-r(x,a^0)+β· (Z_r(x) )% ]+L_D(r) \.italic_( italic_) = minitalic_r ∈ R η ⋅ blackboard_Estart_ARG start_ROW start_CELL x ∼ d start_POSTSUBSCRIPT 0 , a0 ∼ πroman_base ( ⋅ | x ) end_CELL end_ROW end_ARG end_POSTSUBSCRIPT [ - r ( x , a0 ) + β ⋅ log ( Zitalic_r ( x ) ) ] + Lcaligraphic_D ( r ) . (4.4) Furthermore, from Lemma 4.1, one immediately see that given any reward model r∈ℛr ∈ R, we can reparameterize it via its corresponding optimal KL-regularized policy πrsubscript _rπitalic_r (Rafailov et al., 2023), that is, r⁢(x,⋅)=β⋅log⁡(πr(⋅|x)πref(⋅|x))+β⋅log⁡(Zr⁢(x)). r(x,·)=β· ( _r(·|x)π^% ref(·|x) )+β· (Z_r(x)).r ( x , ⋅ ) = β ⋅ log ( divide start_ARG πitalic_r ( ⋅ | x ) end_ARG start_ARG πroman_ref ( ⋅ | x ) end_ARG ) + β ⋅ log ( Zitalic_r ( x ) ) . (4.5) Taking (4.5) back into (4.1), we are able to further simplify it as (⁢4.1⁢)=minr∈ℛ⁡η⋅x∼d0,a0∼πbase(⋅|x)⁢[−β⋅log⁡(πr⁢(a0|x))]+ℒ⁢(β⋅log⁡(πr(⋅|⋅)πref(⋅|⋅))). \!\!\!\!\!\!\!\!\!\! eq: target min max= _r∈ % R \η·E_ subarraycx d_0,a^0 π^% base(·|x) subarray [-β· ( _r(a^0|x)% ) ]+L_D (β· ( _r(% ·|·)π^ref(·|·) ) ) \.italic_( italic_) = minitalic_r ∈ R η ⋅ blackboard_Estart_ARG start_ROW start_CELL x ∼ d start_POSTSUBSCRIPT 0 , a0 ∼ πroman_base ( ⋅ | x ) end_CELL end_ROW end_ARG end_POSTSUBSCRIPT [ - β ⋅ log ( πitalic_r ( a0 | x ) ) ] + Lcaligraphic_D ( β ⋅ log ( divide start_ARG πitalic_r ( ⋅ | ⋅ ) end_ARG start_ARG πroman_ref ( ⋅ | ⋅ ) end_ARG ) ) . (4.6) Thanks to the KL-regularization term in the original minimax objective (4.1) (or equivalently, the maximin objective (3.3)), we have the following theorem. It theoretically shows that the policy πr^subscript _ rπover start_ARG r end_ARG associated with the reward model r^ rover start_ARG r end_ARG solving (4.6) also solves the maximin target (3.3) of the theoretical algorithm (Algorithm 1) that enjoys finite-sample convergence guarantees. Theorem 4.2 (Equivalence between maximin and minimax algorithm (informal)). Under certain regularity assumptions on ℛRR and given η,β>00η,β>0η , β > 0, solving the minimax objective (4.1) via (4.6), i.e., r^=argminr∈ℛη⋅x∼d0,a0∼πbase(⋅|x)⁢[−β⋅log⁡(πr⁢(a0|x))]+ℒ⁢(β⋅log⁡(πr(⋅|⋅)πref(⋅|⋅))), r= argmin_r \% η·E_ subarraycx d_0,a^0 π^base% (·|x) subarray [-β· ( _r(a^0|x)) ]+% L_D (β· ( _r(·|·)% π^ref(·|·) ) ) \,over start_ARG r end_ARG = argminitalic_r ∈ R η ⋅ blackboard_Estart_ARG start_ROW start_CELL x ∼ d start_POSTSUBSCRIPT 0 , a0 ∼ πroman_base ( ⋅ | x ) end_CELL end_ROW end_ARG end_POSTSUBSCRIPT [ - β ⋅ log ( πitalic_r ( a0 | x ) ) ] + Lcaligraphic_D ( β ⋅ log ( divide start_ARG πitalic_r ( ⋅ | ⋅ ) end_ARG start_ARG πroman_ref ( ⋅ | ⋅ ) end_ARG ) ) , (4.7) then the corresponding optimal KL-regularized policy πr^subscript _ rπover start_ARG r end_ARG also solves the maximin objective (3.3). Proof of Proposition 4.2. Please see Section 5.2 for a formal statement and proof of Theorem 4.2. ∎ Algorithm 2 Practical Algorithm: Regularized Preference Optimization (RPO) 1: Input: Preference dataset DD, parameters β,η>00β,η>0β , η > 0, reference policy πrefsuperscriptrefπ^refπroman_ref, baseline policy πbasesuperscriptbaseπ^baseπroman_base. 2: Output: Policy πθ^subscript _ θπover start_ARG θ end_ARG obtained by optimizing objective (4.8). Regularized Preference Optimization. Target (4.6) gives a quite simple objective to use in practice! Since (4.6) depends on r∈ℛr ∈ R only through its corresponding optimal policy πrsubscript _rπitalic_r, we formulate a minimization objective over a parameterized policy πθsubscript _θπitalic_θ, i.e., the LLM to be aligned, and directly optimize the parameters θ∈Θθ∈ θ ∈ Θ. More formally, the new RLHF objective becomes minθ∈Θ⁡ℒRPO⁢(θ):=η⁢β⋅x∼d0,a0∼πbase(⋅|x)⁢[−log⁡(πθ⁢(a0|x))]⏟Imitation (SFT) loss+ℒ⁢(β⋅log⁡(πθ(⋅|⋅)πref(⋅|⋅)))⏟Preference opt. loss. \!\!\!\! _θ∈ \L_RPO% (θ):=ηβ· E_ subarraycx d_0% ,a^0 π^base(·|x) subarray [- ( _θ% (a^0|x)) ]_ [rgb]0.8625,0.45,0.5875% [named]pgfstrokecolorrgb0.8625,0.45,0.5875Imitation (% SFT) loss+ L_D (β· (% _θ(·|·)π^ref(·|·) ) % )_ [rgb]0.45,0.45,1 [named]% pgfstrokecolorrgb0.45,0.45,1Preference opt. loss \.minitalic_θ ∈ Θ Lroman_RPO ( θ ) := η β ⋅ under⏟ start_ARG blackboard_Estart_ARG start_ROW start_CELL x ∼ d start_POSTSUBSCRIPT 0 , a0 ∼ πroman_base ( ⋅ | x ) end_CELL end_ROW end_ARG end_POSTSUBSCRIPT [ - log ( πitalic_θ ( a0 | x ) ) ] end_ARGImitation (SFT) loss + under⏟ start_ARG Lcaligraphic_D ( β ⋅ log ( divide start_ARG πitalic_θ ( ⋅ | ⋅ ) end_ARG start_ARG πroman_ref ( ⋅ | ⋅ ) end_ARG ) ) end_ARGPreference opt. loss . (4.8) In (4.8), the second term coincides with the objective of DPO algorithm (Rafailov et al., 2023) which optimizes the policy towards maximizing the underlying true reward, and the first term stands for a regularization term weighted by η⋅β⋅η·βη ⋅ β which explicitly regularizes the policy to imitate the baseline policy. Therefore, we name the resulting algorithm as Regularized Preference Optimization (RPO). We summarize it abstractly in Algorithm 2. As for DPO, implementing RPO does not require to maintain a reward model r. Thus it is computationally more friendly compared to reward-based algorithms. How does RPO improve DPO? We illustrate the effect of the imitation loss by analyzing the gradient of the RPO target ℒRPO⁢(θ)subscriptℒRPOL_RPO(θ)Lroman_RPO ( θ ) in (4.8). Notice that by (4.8) we have ∇θℒRPO⁢(θ)subscript∇subscriptℒRPO -2m _θL_RPO(θ)∇θ Lroman_RPO ( θ ) =η⁢β⋅x∼d0,a0∼πbase(⋅|x)⁢[−∇θlog⁡(πθ⁢(a0|x))]⏟increase the alignment with the baseline policy+∇θℒDPO⁢(θ)⏟decrease the DPO Loss, =ηβ· E_ subarraycx d% _0,a^0 π^base(·|x) subarray [- _% θ ( _θ(a^0|x)) ]_increase the alignment with % the baseline policy+ _θL_DPO(% θ)_decrease the DPO Loss,= η β ⋅ under⏟ start_ARG blackboard_Estart_ARG start_ROW start_CELL x ∼ d start_POSTSUBSCRIPT 0 , a0 ∼ πroman_base ( ⋅ | x ) end_CELL end_ROW end_ARG end_POSTSUBSCRIPT [ - ∇θ log ( πitalic_θ ( a0 | x ) ) ] end_ARGincrease the alignment with the baseline policy + under⏟ start_ARG ∇θ Lroman_DPO ( θ ) end_ARGdecrease the DPO Loss , (4.9) where the derivative of the DPO loss ∇θℒDPO⁢(θ)subscript∇subscriptℒDPO _θL_DPO(θ)∇θ Lroman_DPO ( θ ) is given by the following, ∇θℒDPO⁢(θ)=−^⁢[β⋅σ⁢(r^θ⁢(x,arej)−r^θ⁢(x,acho))⏟gradient weight⋅(∇θlog⁡πθ⁢(acho|x)−∇θlog⁡πθ⁢(arej|x))].subscript∇subscriptℒDPOsubscript^delimited-[]⋅subscript⏟⋅subscript^subscriptrejsubscript^subscriptchogradient weightsubscript∇subscriptconditionalsubscriptchosubscript∇subscriptconditionalsubscriptrej _θL_DPO(θ)=- % E_D [ β·σ ( r% _θ(x,a_rej)- r_θ(x,a_cho) )% _gradient weight\!· ( _θ _θ(a_% cho|x)- _θ _θ(a_rej|x) )% ].∇θ Lroman_DPO ( θ ) = - over start_ARG blackboard_E end_ARGD [ under⏟ start_ARG β ⋅ σ ( over start_ARG r end_ARGθ ( x , aroman_rej ) - over start_ARG r end_ARGθ ( x , aroman_cho ) ) end_ARGgradient weight ⋅ ( ∇θ log πitalic_θ ( aroman_cho | x ) - ∇θ log πitalic_θ ( aroman_rej | x ) ) ] . (4.10) For simplicity we denote r^θ⁢(x,a)=β⋅log⁡(πθ⁢(a|x))/log⁡(πref⁢(a|x))subscript^⋅subscriptconditionalsuperscriptrefconditional r_θ(x,a)=β· ( _θ(a|x))/ (π^% ref(a|x))over start_ARG r end_ARGθ ( x , a ) = β ⋅ log ( πitalic_θ ( a | x ) ) / log ( πroman_ref ( a | x ) ), and denote achosubscriptchoa_choaroman_cho for the chosen response and arejsubscriptreja_rejaroman_rej for the rejected response. Intuitively, RPO (4.8) modifies the gradient direction of DPO to ensure the alignment with the baseline policy πbasesuperscriptbaseπ^baseπbase, and the hyper-parameter η controls the power of alignment. In comparison, the hyper-parameter β in DPO only controls the gradient weight when increasing the likelihood of achosubscriptchoa_choaroman_cho and decreasing the likelihood arejsubscriptreja_rejaroman_rej. In this perspective, the hyper-parameter β only changes the scale of the gradient instead of the direction. By introducing η, we stabilize the training and reduce the side-effect of uncertain labels in data to prevent overoptimization. 5 Theoretical Analysis In this section, we present theoretical analysis of our proposed algorithms (Algorithm 1 and Algorithm 2). In Section 5.1, we first establish a finite-sample complexity result for the theoretical algorithm (Algorithm 1) that adopts maximin objective (3.3). In Section 5.2, we formally provide an equivalence result between the maximin objective (3.3) and the minimax objective (4.1) that we use in practice, based on which we further obtain the sample complexity guarantee of our practical algorithm design (Algorithm 2). In Section 5.3, we further extend our theory to guarantee the performance on new prompt distributions. Through this theory section, we assume that the space of prompts and responses are compact subsets of high-dimensional spaces, that is, ⊆ℝdsuperscriptℝsubscriptX ^d_XX ⊆ blackboard_Rdcaligraphic_X and ⊆ℝdsuperscriptℝsubscriptA ^d_AA ⊆ blackboard_Rdcaligraphic_A for some d,d∈ℕ+subscriptsubscriptsubscriptℕd_X,d_A _+dcaligraphic_X , dcaligraphic_A ∈ blackboard_N+, and XX and AA are compact (closed and bounded). We take the policy class Π Π as (2.4), that is, Π=π:↦Δ()|Supp(π(⋅|x))⊆Supp(πref(⋅|x)),∀x∈. = \π:X (A)\, |\,% Supp(π(·|x)) (π^ref(·|x))% ,\,\,∀ x \.Π = π : X ↦ Δ ( A ) | Supp ( π ( ⋅ | x ) ) ⊆ Supp ( πroman_ref ( ⋅ | x ) ) , ∀ x ∈ X . (5.1) 5.1 Establishing the Sample Complexity of Maximin Objective (Algorithm 1) We first make the following two assumptions for the sample complexity analysis of Algorithm 1. Assumption 5.1 (True reward model). We assume that the true reward model r⋆∈ℛsuperscript⋆ℛr ⋆ ∈ R, and for any r∈ℛr ∈ R and (x,a)∈×(x,a) ×A( x , a ) ∈ X × A, it holds that r⁢(x,a)∈[0,R]0r(x,a)∈[0,R]r ( x , a ) ∈ [ 0 , R ]. Assumption 5.2 (Partial coverage coefficient (Zhan et al., 2023a)). Given a policy π∈Ππ∈ π ∈ Π, the coverage coefficient of the offline dataset distribution μsubscript _Dμcaligraphic_D w.r.t. reward model class ℛRR, policy π, and the baseline policy πbasesuperscriptbaseπ^baseπroman_base, denoted by Cμ⁢(ℛ;π,πbase)subscriptsubscriptℛsuperscriptbaseC_ _D(R;π,π^base)Citalic_μ start_POSTSUBSCRIPT D end_POSTSUBSCRIPT ( R ; π , πroman_base ), is defined as max⁡0,supr∈ℛx∼d0,a1∼π(⋅|x),a0∼πbase(⋅|x)⁢[(r⋆⁢(x,a1)−r⋆⁢(x,a0))−(r⁢(x,a1)−r⁢(x,a0))](x,a1,a0)∼μ⁢[|(r⋆⁢(x,a1)−r⋆⁢(x,a0))−(r⁢(x,a1)−r⁢(x,a0))|2]. \0, _r E_x d_0,% a^1 π(·|x),a^0 π^base(·|x) [(r (% x,a^1)-r (x,a^0))-(r(x,a^1)-r(x,a^0)) ] E_% (x,a^1,a^0) _D [ |(r (x,a^1)-r^% (x,a^0))-(r(x,a^1)-r(x,a^0)) |^2 ] \.max 0 , supitalic_r ∈ R divide start_ARG blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ π ( ⋅ | x ) , a0 ∼ πroman_base ( ⋅ | x ) end_POSTSUBSCRIPT [ ( r⋆ ( x , a1 ) - r⋆ ( x , a0 ) ) - ( r ( x , a1 ) - r ( x , a0 ) ) ] end_ARG start_ARG square-root start_ARG blackboard_E( x , a1 , a0 ) ∼ μ start_POSTSUBSCRIPT D end_POSTSUBSCRIPT [ | ( r⋆ ( x , a1 ) - r⋆ ( x , a0 ) ) - ( r ( x , a1 ) - r ( x , a0 ) ) |2 ] end_ARG end_ARG . (5.2) We assume that Cμ⁢(ℛ;π,πbase)<+∞subscriptsubscriptℛsuperscriptbaseC_ _D(R;π,π^base)<+∞Citalic_μ start_POSTSUBSCRIPT D end_POSTSUBSCRIPT ( R ; π , πroman_base ) < + ∞ for the policy π to compete. Assumption 5.1 is standard in sample complexity analysis (Zhu et al., 2023; Zhan et al., 2023a; Ye et al., 2024). Assumption 5.2 characterizes how well the dataset DD covers the policy π to compete. Intuitively, this can be understood from the fact that Cμ⁢(ℛ;π,πbase)subscriptsubscriptℛsuperscriptbaseC_ _D(R;π,π^base)Citalic_μ start_POSTSUBSCRIPT D end_POSTSUBSCRIPT ( R ; π , πroman_base ) is upper bounded by the density ratio Cμ⁢(ℛ;π,πbase)≤‖d0⊗π⊗πbaseμ‖∞=sup(x,a1,a0)∈×d0⁢(x)⁢π⁢(a1|x)⁢πbase⁢(a0|x)μ⁢(x,a1,a0).subscriptsubscriptℛsuperscriptbasesubscriptnormtensor-productsubscript0superscriptbasesubscriptsubscriptsupremumsuperscript1superscript0subscript0conditionalsuperscript1superscriptbaseconditionalsuperscript0subscriptsuperscript1superscript0C_ _D(R;π,π^base)≤ \| d_% 0 π π^base _D \|_∞=% _(x,a^1,a^0)∈S×A×A % d_0(x)π(a^1|x)π^base(a^0|x) _D(x,a^1,a^% 0).Citalic_μ start_POSTSUBSCRIPT D end_POSTSUBSCRIPT ( R ; π , πroman_base ) ≤ ∥ divide start_ARG d0 ⊗ π ⊗ πroman_base end_ARG start_ARG μcaligraphic_D end_ARG ∥∞ = sup( x , a1 , a0 ) ∈ S × A × A divide start_ARG d0 ( x ) π ( a1 | x ) πroman_base ( a0 | x ) end_ARG start_ARG μcaligraphic_D ( x , a1 , a0 ) end_ARG . In order for Algorithm 1 to achieve provable sample efficiency, we only require that DD covers the target policy π, a weak partial coverage style assumption for the sample complexity analysis (Zhu et al., 2023; Zhan et al., 2023a; Xiong et al., 2023). To illustrate it, when calling back to Figure 1, the data distribution therein well covers those nearly optimal responses under r⋆superscript⋆r r⋆, but does not sufficiently cover the responses with low r⋆superscript⋆r r⋆. Under such a partial coverage data condition, however, the human preference of responses a∈a ∈ A that are not well covered by the dataset DD can be poorly estimated, misguiding the policy π^ πover start_ARG π end_ARG to behave suboptimally if it is overoptimized (recall Figure 1). Fortunately, the following theorem shows that Algorithm 1 provably mitigates the overoptimization issue and achieves a finite-sample convergence of the suboptimality gap (2.5). Theorem 5.3 (Suboptimality of Algorithm 1). Taking the policy class Π Π as (2.4), supposing that Assumptions 5.1 and 5.2 hold, and assuming that the reward model class ℛRR has a finite ε ε-covering number under ∥⋅∥∞\|·\|_∞∥ ⋅ ∥∞-norm ε(ℛ,∥⋅∥∞)<+∞N_ (R,\|·\|_∞)<+∞Nitalic_ε ( R , ∥ ⋅ ∥∞ ) < + ∞ with ε=(6⋅(1+eR)⋅N)−1superscript⋅61superscript1 =(6·(1+e^R)· N)^-1ε = ( 6 ⋅ ( 1 + eitalic_R ) ⋅ N )- 1. Setting η=1(1+exp⁡(R))2⋅24⋅log(ε(ℛ,∥⋅∥∞)/δ)N,β=1N η= 1(1+ (R))^2· 24· (% N_ (R,\|·\|_∞)/δ )N,% β= 1 Nη = divide start_ARG 1 end_ARG start_ARG ( 1 + exp ( R ) )2 end_ARG ⋅ square-root start_ARG divide start_ARG 24 ⋅ log ( Nitalic_ε ( R , ∥ ⋅ ∥∞ ) / δ ) end_ARG start_ARG N end_ARG end_ARG , β = divide start_ARG 1 end_ARG start_ARG square-root start_ARG N end_ARG end_ARG in Algorithm 1. Then the output policy π^ πover start_ARG π end_ARG of Algorithm 1 satisfies that with probability at least 1−δ11- 1 - δ, Gapπ⁢(π^)≤6⋅(1+exp(R))2⋅((Cμ(ℛ;π,πbase))2+1)⋅ι+4⋅x∼d0[KL(π(⋅|x)∥πref(⋅|x))]4⁢N, ^π( π)≤ 6· (1+% (R) )^2· ( (C_ _D(R;π,π% ^base) )^2+1 )· +4·E_x d_0% [KL (π(·|x)\|π^ref(·|x) ) % ]4 N,Gapitalic_π ( over start_ARG π end_ARG ) ≤ divide start_ARG square-root start_ARG 6 end_ARG ⋅ ( 1 + exp ( R ) )2 ⋅ ( ( Citalic_μ start_POSTSUBSCRIPT D end_POSTSUBSCRIPT ( R ; π , πroman_base ) )2 + 1 ) ⋅ ι + 4 ⋅ blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT [ KL ( π ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] end_ARG start_ARG 4 square-root start_ARG N end_ARG end_ARG , (5.3) where ι=log(ε(ℛ,∥⋅∥∞)/δ) = (N_ (R,\|·\|_∞% )/δ )ι = square-root start_ARG log ( Nitalic_ε ( R , ∥ ⋅ ∥∞ ) / δ ) end_ARG with ε=(6⋅(1+eR)⋅N)−1superscript⋅61superscript1 =(6·(1+e^R)· N)^-1ε = ( 6 ⋅ ( 1 + eitalic_R ) ⋅ N )- 1. Here, N denotes the number of preference pairs in DD, R denotes the upper bound of the reward models, and the partial coverage coefficient Cμ⁢(ℛ;π,πbase)subscriptsubscriptℛsuperscriptbaseC_ _D(R;π,π^base)Citalic_μ start_POSTSUBSCRIPT D end_POSTSUBSCRIPT ( R ; π , πroman_base ) is defined in Assumption 5.2. Proof of Theorem 5.3. Please refer to Appendix B.2 for a detailed proof of Theorem 5.3. ∎ Remark 5.4 (Choice of the baseline policy πbasesuperscriptbaseπ^baseπroman_base). As is indicated by Assumption 5.2, the least requirement is that πbasesuperscriptbaseπ^baseπroman_base can be covered by the offline data distribution. For example, we can take πbasesuperscriptbaseπ^baseπroman_base as the distribution of the preferred responses in the dataset. In this case, the SFT loss in the RPO objective explicitly regularizes the LLM to imitate the preferred responses. We choose this baseline policy in our experiments (Section 6). 5.2 Equivalence between Maximin and Minimax Objectives In this section, we formally show that under certain regularity assumptions, the theoretical target (maximin objective (3.3)) and the target for practical algorithm design (minimax objective (4.1)) are equivalent. This can naturally extend the sample complexity of Algorithm 1 (Section 5.1) to that of minimax-based algorithms in Section 4, providing the theoretical guarantee for our practical algorithm design (RPO). First, for notational simplicity, we denote the optimization target we investigate in Sections 3 and 4 as ϕ(π,r):=η⋅x∼d0,a1∼π(⋅|x),a0∼πref(⋅|x)[r(x,a1)−r(x,a0)−β⋅DKL(π(⋅|x)∥πref(⋅|x))]+ℒ(r), φ(π,r):=η·E_x d_0,a^1 π(·|% x),a^0 π^ref(·|x) [r(x,a^1)-r(x,a^0)-β% · D_KL (π(·|x)\|π^ref(·|x) )% ]+L_D(r),ϕ ( π , r ) := η ⋅ blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ π ( ⋅ | x ) , a0 ∼ πroman_ref ( ⋅ | x ) end_POSTSUBSCRIPT [ r ( x , a1 ) - r ( x , a0 ) - β ⋅ Droman_KL ( π ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] + Lcaligraphic_D ( r ) , (5.4) for any (π,r)∈Π×ℛΠℛ(π,r)∈ ×R( π , r ) ∈ Π × R. Our result relies on the following assumptions on the reward model class ℛRR. Assumption 5.5 (Regularity of reward model class). We assume the following things on the reward model class ℛRR: (i) the space ℛRR is a compact topological space; (i) the function ϕitalic-ϕφϕ in (5.4) is convex-like on ℛRR, that is, for any r1,r2∈ℛsubscript1subscript2ℛr_1,r_2 1 , r2 ∈ R and α∈[0,1]01α∈[0,1]α ∈ [ 0 , 1 ], there exists r3∈ℛsubscript3ℛr_3 3 ∈ R such that ϕ⁢(π,r3)≤α⋅ϕ⁢(π,r1)+(1−α)⋅ϕ⁢(π,r2),∀π∈Π,formulae-sequenceitalic-ϕsubscript3⋅italic-ϕsubscript1⋅1italic-ϕsubscript2for-allΠ φ(π,r_3)≤α·φ(π,r_1)+(1-α)·φ% (π,r_2), ∀π∈ ,ϕ ( π , r3 ) ≤ α ⋅ ϕ ( π , r1 ) + ( 1 - α ) ⋅ ϕ ( π , r2 ) , ∀ π ∈ Π , (5.5) We note that by the definition, the convex-like property (5.5) not only depends on the function ϕitalic-ϕφϕ, but also depends on the reward model class ℛRR. As a special case, if ℛRR is convex, e.g., a linear model class (Zhu et al., 2023; Xiong et al., 2023; Zhu et al., 2024) or more general the Lipschitz continuous model class ℛRR, we can directly obtain that the function ϕ⁢(π,⋅)italic-ϕ⋅φ(π,·)ϕ ( π , ⋅ ) is convex over ℛRR (since the dependence on r∈ℛr ∈ R is linear terms plus a convex loss ℒsubscriptℒL_DLcaligraphic_D of r∈ℛr ∈ R), which implies the convex-like property (5.5). Under Assumption 5.5, it holds that (Lemma C.1) maxπ∈Π⁡minr∈ℛ⁡ϕ⁢(π,r)=minr∈ℛ⁡maxπ∈Π⁡ϕ⁢(π,r).subscriptΠsubscriptℛitalic-ϕsubscriptℛsubscriptΠitalic-ϕ _π∈ \, _r φ(π,r)= _r∈% R\, _π∈ φ(π,r).maxitalic_π ∈ Π minitalic_r ∈ R ϕ ( π , r ) = minitalic_r ∈ R maxitalic_π ∈ Π ϕ ( π , r ) . (5.6) Furthermore, thanks to the KL-divergence regularization in ϕitalic-ϕφϕ which intuitively makes ϕitalic-ϕφϕ “strongly concave” over the policy π, (5.6) can gives us the following stronger result. Theorem 5.6 (Formal statement of Theorem 4.2). For the policy class Π Π defined in (5.1) and the reward model class ℛRR satisfying Assumption 5.5, consider the following policy defined as πr^∈argmaxπ∈Πϕ⁢(r^,π),w⁢h⁢e⁢r⁢er^∈argminr∈ℛmaxπ∈Π⁡ϕ⁢(π,r).formulae-sequencesubscript^subscriptargmaxΠitalic-ϕ^ℎ^subscriptargminℛsubscriptΠitalic-ϕ _ r∈ argmax_π∈ φ(% r,π), where r∈ argmin_r∈% R\, _π∈ φ(π,r).πover start_ARG r end_ARG ∈ argmaxitalic_π ∈ Π ϕ ( over start_ARG r end_ARG , π ) , w h e r e over start_ARG r end_ARG ∈ argminitalic_r ∈ R maxitalic_π ∈ Π ϕ ( π , r ) . (5.7) Then the policy πr^subscript _ rπover start_ARG r end_ARG also satisfies the maximin objective (3.3) of Algorithm 1, that is, πr^∈argmaxπ∈Πminr∈ℛ⁡ϕ⁢(π,r).subscript^subscriptargmaxΠsubscriptℛitalic-ϕ _ r∈ argmax_π∈ \, _r% φ(π,r).πover start_ARG r end_ARG ∈ argmaxitalic_π ∈ Π minitalic_r ∈ R ϕ ( π , r ) . (5.8) Proof of Theorem 5.6. Please refer for Appendix C.1 for a detailed proof of Proposition 5.6. ∎ Theorem 5.6 shows that the optimal KL-regularized policy associated with the reward model solving the minimax objective (3.3) also solves the maximin target for the policy (i.e., objective (4.1) of Algorithm 1). This further allows us to extend our theoretical guarantee of Algorithm 1 (Section 5.1) to that of minimax-based algorithms, justifying our practical algorithm design in Section 4. Corollary 5.7 (Suboptimality of minimax-based algorithm). Take the policy class Π Π in (5.1) and the reward model class satisfying Assumption 5.5. Given any given policy π to compete, if Assumption 5.2 holds for π, then under the same choice of η and β as in Theorem 5.3, the policy πr^subscript _ rπover start_ARG r end_ARG defined in (5.7) satisfies that Gapπ⁢(πr^)≤~⁢(1/N).superscriptGapsubscript^~1 ^π( _ r)≤ O% (1/ N ).Gapitalic_π ( πover start_ARG r end_ARG ) ≤ over~ start_ARG O end_ARG ( 1 / square-root start_ARG N end_ARG ) . (5.9) with probability at least 1−δ11- 1 - δ, where ~⁢(⋅)~⋅ O(·)over~ start_ARG O end_ARG ( ⋅ ) hides the same factors as shown in Theorem 5.3 for Algorithm 1. Proof of Corollary 5.7. This is a direct corollary of Theorem 5.3 and Theorem 5.6. ∎ 5.3 Generalization to New Prompt Distributions In this section, we further generalize our previous theoretical analysis to guarantee the performance of the proposed algorithm on new prompt distributions different from the data or training distribution. Specifically, we would like to consider a new prompt distribution d1⁢(⋅)∈Δ⁢()subscript1⋅Δd_1(·)∈ (X)d1 ( ⋅ ) ∈ Δ ( X ) that is different from d0subscript0d_0d0. This corresponds to testing the learned policy on a new set of prompts with a different distribution than the training prompts. The following corollary demonstrates that, as long as the new prompt distribution d1subscript1d_1d1 is well covered by the distribution d0subscript0d_0d0, we still have a finite-sample convergence guarantee. Corollary 5.8 (Generalization to new prompt distributions). Under the same setups as in Corollary 5.7, we consider the policy to compete as the optimal policy π⋆∈Πsuperscript⋆Ππ ∈ π⋆ ∈ Π, that is, π⋆=argmaxπ∈Πa∼π(⋅|x)⁢[r⋆⁢(x,a)]π = argmax_π∈ E_a π(·|x)% [r (x,a)]π⋆ = argmaxitalic_π ∈ Π blackboard_Ea ∼ π ( ⋅ | x ) [ r⋆ ( x , a ) ] for any x∈x ∈ X. Assume that the density ratio between the prompt distributions d1subscript1d_1d1 and d0subscript0d_0d0 are bounded, i.e., C∞⁢(d0,d1):=supx∈d1⁢(x)d0⁢(x)<+∞.assignsubscriptsubscript0subscript1subscriptsupremumsubscript1subscript0 C_∞(d_0,d_1):= _x \, d_1(x)% d_0(x)<+∞.C∞ ( d0 , d1 ) := supitalic_x ∈ X divide start_ARG d1 ( x ) end_ARG start_ARG d0 ( x ) end_ARG < + ∞ . (5.10) Then the following bound holds, for the policy πr^subscript _ rπover start_ARG r end_ARG (see Corollary 5.7), with probability at least 1−δ11- 1 - δ, x∼d1,a∼π⋆(⋅|x)⁢[r⋆⁢(x,a)]−x∼d1,a∼πr^(⋅|x)⁢[r⋆⁢(x,a)]≤~⁢(C∞⁢(d0,d1)N), _x d_1,a π (·|x)[r (x,a)% ]-E_x d_1,a _ r(·|x)[r (x,a)]≤% O ( C_∞(d_0,d_1) N ),blackboard_Ex ∼ d start_POSTSUBSCRIPT 1 , a ∼ π⋆ ( ⋅ | x ) end_POSTSUBSCRIPT [ r⋆ ( x , a ) ] - blackboard_Ex ∼ d start_POSTSUBSCRIPT 1 , a ∼ πover start_ARG r end_ARG ( ⋅ | x ) end_POSTSUBSCRIPT [ r⋆ ( x , a ) ] ≤ over~ start_ARG O end_ARG ( divide start_ARG C∞ ( d0 , d1 ) end_ARG start_ARG square-root start_ARG N end_ARG end_ARG ) , (5.11) where ~⁢(⋅)~⋅ O(·)over~ start_ARG O end_ARG ( ⋅ ) hides the same factors as shown in Theorem 5.3 for Algorithm 1. Proof of Corollary 5.8. Please refer to Appendix D for a detailed proof of Corollary 5.8. ∎ In our experiments (Section 6), we evaluate the performance of RPO-trained LLMs (trained using the Ultrafeedback Dataset) on two standard benchmarks, MT-Bench and AlpacaEval 2.0 (with a different prompt distribution than Ultrafeedback), which demonstrates the capability of RPO to adapt to new prompt distributions, as is indicated by the above Corollary 5.8. A key requirement of Corollary 5.8 is that the training prompt distribution well covers the new prompt distribution. In the following, we use Principle Component Analysis (PCA) analysis to illustrate the prompt distribution of these two benchmarks as well as the training data. We use text-embedding-ada-002 provided by OpenAI to extract the embeddings of the prompts in the training dataset, MT-bench, and AlpacaEval 2.0, for the two models we train in experiments (the beta series and the gemma series). Here, each embedding is a vector with a length of 1536. For each model, we use Singular Value Decomposition (SVD) on the matrix stacked by the embeddings of the training dataset and obtain the first two PCA axises v1subscript1v_1v1 and v2subscript2v_2v2. Here, unit vectors v1subscript1v_1v1 and v2subscript2v_2v2 have a length of 1536 and correspond to the first largest and the second largest singular value in SVD, respectively. Then, for each embedding e in the training dataset, MT-Bench, and AlpacaEval 2.0, we use (⟨e,v1⟩,⟨e,v2⟩)subscript1subscript2( e,v_1 , e,v_2 )( ⟨ e , v1 ⟩ , ⟨ e , v2 ⟩ ) as the coordinate to draw a 2D scatter plot in Figures 3 and 3. Results show that (5.10) in Corollary 5.8 approximately holds for both beta and gemma series on MT-Bench and AlpacaEval 2.0, which suggests the desired performance of RPO on these two benchmarks given by Corollary 5.8. Figure 2: PCA of the embeddings of prompts in the training dataset of the beta series (Ultrafeedback), MT-Bench, and AlpacaEval 2.0. Figure 3: PCA of the embeddings of prompts in the training dataset of the gemma series (Argilla-DPO-Mix-7K), MT-Bench, and AlpacaEval 2.0. 6 Experiments In this experiment section, we provide a detailed empirical analysis of RPO to highlight the following four key points: (i) RPO is a flexible plug-in module and can be applied to different reference models. (i) RPO mitigates overoptimization in the training phase by giving more trust to the chosen responses in the preference dataset. (i) As a justification of our theoretical analysis, RPO achieves better alignment performance than DPO in in-data distribution. (iv) RPO can also achieve consistently better performance in LLM benchmarks like MT-bench (Zheng et al., 2024) and AlpacaEval 2.0 (Dubois et al., 2024), which shows the potential of mitigating overoptimization for better generalization performance. Experiment setup. To show that RPO is a flexible plug-in module regardless of the reference model, we follow the training setup for two well-studied series of released chat models with around 7 billion parameters trained by DPO: Zephyr-7b-beta and Zephyr-7b-gemma (Tunstall et al., 2023b) to implement RPO in beta and gemma series. Mirrored by their training configurations, we introduce how we select the reference model and the preference dataset for our training pipeline of these two series as follows. For the beta series, we use mistral-7b-sft-beta as the reference model πrefsuperscriptrefπ^refπref. mistral-7b-sft-beta is a fine-tuned version of Mistral-7b-v0.1 on the distilled version of the UltraChat dataset (Ding et al., 2023), which contains approximately 200k examples of multi-turn dialogues generated by GPT-3.5-TURBO. For the training preference dataset, we use the Ultrafeedback Dataset (Cui et al., 2023), which consists of approximately 60k prompts. For the gemma series, we use zephyr-7b-gemma-sft-v0.1 as our reference model πrefsuperscriptrefπ^refπref. zephyr-7b-gemma-sft-v0.1 is a fine-tuned version of gemma-7b on the Deita dataset (Liu et al., 2023b), which involves around 10k distilled SFT data. For the training preference dataset, we use the Argilla-DPO-Mix-7K Dataset (argill, 2024), which is a mixture of multiple distilled public preference datasets. For simplicity, we denote Ref. (beta) as the reference model, DPO (beta) as the model trained by DPO, and RPO (beta) as the model trained by RPO, all for the beta series. We use the same notations for the gemma series. Practical implementation. According to Algorithm 2 and as we discussed in Remark 5.4, we implement RPO by adding an SFT loss (log probability of chosen responses in the preference dataset) to the original DPO loss. By comparing the evaluation performance on the test split of the training dataset, we select the hyperparameter η as 0.0050.0050.0050.005 for both RPO (beta) and RPO (gemma). During the training of DPO and RPO, We keep the remaining hyperparameters including β, batch size, and learning rate to be the same for a fair comparison. Please see Appendix E.1 for a detailed training configuration. RPO alleviates overoptimization. As mentioned in the introduction (Figure 1), DPO is observed to have a significant and continual decrease in log probability on chosen responses (Hong et al., 2024; Rafailov et al., 2024) during training and we regard it as the consequence of overoptimization. Implied by our theory, overoptimization could arise when the model maximizes its own proxy reward formed on the responses less covered by the data. Due to the overoptimization, the model tends to disprefer the chosen responses as they are away from the maximizers of the proxy reward despite that some chosen responses are highly preferred by humans. Consistent with our theoretical conclusion, we empirically find that RPO can indeed alleviate overoptimization in DPO. During the training phase of both beta and gemma series, we observe that the log probability given by the RPO-trained model is notably higher than that given by the DPO-trained model for the chosen responses, which are shown in Figures 1 and 6. RPO improves the alignment performance in in-data distribution. For the in-data distribution evaluation, we select the 200 prompts (which are not used in the selection of paremeter η) in the test split of the training dataset to let the reference model, DPO, and RPO generate the response respectively. We choose GPT-4 to annotate the preference in the response pairs. Though we instruct GPT-4 to give an annotation among win, lose, and tie (please see the full prompt in Appendix E.2), GPT-4 might still provide undesired annotations. Therefore, we filter all the undesired annotations and collect 150 examples for evaluation. We report the pairwise win rate among Ref., RPO, and DPO in Table 1 for both the beta and gemma series. To show a more illustrative comparison between DPO and RPO, we provide the barplot to report the number of pairwise examples annotated by GPT-4 in Figures 6 and 6. We observe that for both beta and gemma series, RPO has a better performance than DPO in terms of both RPO/DPO-SFT and RPO-DPO win rates. The performance improvement matches our theoretical results in Corollary 5.7, which shows the credit of the alleviation of overoptimization. Win rate (%) RPO (beta) Ref. (beta) DPO (beta) Win rate (%) RPO (gemma) Ref. (gemma) DPO (gemma) RPO (beta) 50.0 79.0 56.0 RPO (gemma) 50.0 71.7 54.0 Ref. (beta) 21.0 50.0 22.7 Ref. (gemma) 28.3 50.0 32.7 DPO (beta) 44.0 77.3 50.0 DPO (gemma) 46.0 67.3 50.0 Table 1: Pairwise win rate (left vs. right) among RPO-trained model, DPO-trained model, and the reference model. Annotated by GPT-4, evaluations of beta and gemma series are made on the 150 examples of the test split of the Ultrafeedback and the Argilla-DPO-Mix-7K dataset, respectively. Figure 4: Log probability of chosen responses during the training of RPO (gemma) and DPO (gemma). Figure 5: Pairwise annotations (by GPT-4) on RPO (beta) vs. DPO (beta) on the test split of the Ultrafeedback dataset. Figure 6: Pairwise annotations (by GPT-4) on RPO (gemma) vs. DPO (gemma) on the test split of the Argilla-DPO-Mix-7K dataset. RPO consistently improves the benchmark performance. We further evaluate the reference model, RPO-trained model, DPO-trained model, and the officially released DPO-trained model for both beta and gemma series in two standard LLM chat benchmarks: MT-bench (Zheng et al., 2024) and AlpacaEval 2.0 (Dubois et al., 2024). MT-Bench is a multi-turn benchmark that contains 160 questions across eight different domains of knowledge. The score for MT-Bench is evaluated by GPT-4 on a scale from 1 to 10. AlpacaEval 2.0 is a single-turn benchmark including 805 questions on different topics, mostly focused on helpfulness. The metrics of AlpacaEval 2.0 are the win rate and Length-Control (LC) win rate compared with GPT-4 Preview (11/06), where the annotator is also GPT-4 Preview (11/06) and LC win rate is proposed to mitigate the length bias of GPT-4. The results are summarized in Table 2, which shows that RPO consistently exceeds the performance of all the competitors (DPO, Reference model, and the officially released model trained by DPO) on MT-Bench and AlpacaEval 2.0. We also provide additional results on the pairwise win rate for these two benchmarks in Appendix E.3 to illustrate the performance improvement. The improvement can also be explained by the theoretical results in Corollary 5.8. Finally, we remark that RPO is a flexible plug-in module and can steadily improve the benchmark performance without changing the original training configuration or accessing extra preference data. This also sheds light on the potential of mitigating overoptimization for better alignment and generalization performance. Model Name MT-Bench AlpacaEval 2.0 Model Name MT-Bench AlpacaEval 2.0 Score LC win rate (%) win rate (%) Score LC win rate (%) win rate (%) RPO (beta) 7.381 23.28 21.01 RPO (gemma) 7.916 15.51 13.85 Ref. (beta) 5.088 7.19 4.69 Ref. (gemma) 7.266 8.35 4.61 DPO (beta) 7.278 21.15 17.27 DPO (gemma) 7.688 15.36 13.69 zephyr-beta-7b 7.200 13.20 10.99 zephyr-gemma-7b 7.719 14.78 12.14 Table 2: Results on MT-Bench scores and AlpacaEval 2.0. zephyr-beta-7b and zephyr-gemma-7b are the officially released models. win rates and Length-Control (LC) win rates in AlpacaEval 2.0 are evaluated by GPT-4 compared with GPT-4. RPO also improves math, reasoning, and coding abilities. In addition to the MT-Bench and AlpacaEval 2.0 benchmarks, we further use benchmarks on math, reasoning, and coding tasks for evaluations of the RPO algorithm. Specifically, we choose the Grade School Math 8K (GSM8K) (Cobbe et al., 2021), AI2 Reasoning Challenge (ARC) (Clark et al., 2018), and Mostly Basic Python Programming (MBPP) (Austin et al., 2021) to measure the math, reasoning, and coding abilities of the model trained by RPO, respectively. We refer the readers to Appendix F for the detailed setups and results of these experiments. 7 Conclusions This work proposes a new algorithm that provably mitigates reward overoptimization in RLHF. We establish its finite-sample convergence under a partial coverage style data condition, and provide an equivalent practical implementation, RPO. As a flexible plug-in module, RPO exhibits consistent improvement over the DPO baseline and effectively mitigates overoptimization. Future works include extending our idea of theoretical algorithm design and analysis to the iterative RLHF setup where further preference data could be collected. Also, since our practical algorithm RPO is a plug-in module that effectively mitigates overoptimization and improves alignment performance, it serves as an exciting direction to combine it with explorative preference data collecting mechanism in iterative RLHF to further boost the performance of LLM alignment. Acknowledgement The authors would like to thank the anonymous reviewers for their helpful comments. The authors would also like to thank Junyan Zhang for valuable discussions on the equivalence between the minimax and maxmin optimization. References Achiam et al. (2023) Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S. et al. (2023). Gpt-4 technical report. arXiv preprint arXiv:2303.08774 . Anthropic (2023) Anthropic (2023). Introducing claude. https://w.anthropic.com/news/introducing-claude . argill (2024) argill (2024). argilla-dpo-mix-7k. https://huggingface.co/datasets/argilla/dpo-mix-7k. Austin et al. (2021) Austin, J., Odena, A., Nye, M., Bosma, M., Michalewski, H., Dohan, D., Jiang, E., Cai, C., Terry, M., Le, Q. et al. (2021). Program synthesis with large language models. arXiv preprint arXiv:2108.07732 . Azar et al. (2023) Azar, M. G., Rowland, M., Piot, B., Guo, D., Calandriello, D., Valko, M. and Munos, R. (2023). A general theoretical paradigm to understand learning from human preferences. arXiv preprint arXiv:2310.12036 . Bai et al. (2022) Bai, Y., Jones, A., Ndousse, K., Askell, A., Chen, A., DasSarma, N., Drain, D., Fort, S., Ganguli, D., Henighan, T. et al. (2022). Training a helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204.05862 . Bengs et al. (2021) Bengs, V., Busa-Fekete, R., El Mesaoudi-Paul, A. and Hüllermeier, E. (2021). Preference-based online learning with dueling bandits: A survey. Journal of Machine Learning Research 22 1–108. Blanchet et al. (2024) Blanchet, J., Lu, M., Zhang, T. and Zhong, H. (2024). Double pessimism is provably efficient for distributionally robust offline reinforcement learning: Generic algorithm and robust partial coverage. Advances in Neural Information Processing Systems 36. Bradley and Terry (1952) Bradley, R. A. and Terry, M. E. (1952). Rank analysis of incomplete block designs: I. the method of paired comparisons. Biometrika 39 324–345. Carlini et al. (2021) Carlini, N., Tramer, F., Wallace, E., Jagielski, M., Herbert-Voss, A., Lee, K., Roberts, A., Brown, T., Song, D., Erlingsson, U. et al. (2021). Extracting training data from large language models. In 30th USENIX Security Symposium (USENIX Security 21). Casper et al. (2023) 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. arXiv preprint arXiv:2307.15217 . Chen et al. (2022) Chen, X., Zhong, H., Yang, Z., Wang, Z. and Wang, L. (2022). Human-in-the-loop: Provably efficient preference-based reinforcement learning with general function approximation. In Proceedings of the 39th International Conference on Machine Learning (K. Chaudhuri, S. Jegelka, L. Song, C. Szepesvari, G. Niu and S. Sabato, eds.), vol. 162 of Proceedings of Machine Learning Research. PMLR. Christiano et al. (2017) Christiano, P. F., Leike, J., Brown, T., Martic, M., Legg, S. and Amodei, D. (2017). Deep reinforcement learning from human preferences. Advances in neural information processing systems 30. Clark et al. (2018) 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 preprint arXiv:1803.05457 . Cobbe et al. (2021) 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 preprint arXiv:2110.14168 . Coste et al. (2023) Coste, T., Anwar, U., Kirk, R. and Krueger, D. (2023). Reward model ensembles help mitigate overoptimization. arXiv preprint arXiv:2310.02743 . Cui et al. (2023) Cui, G., Yuan, L., Ding, N., Yao, G., Zhu, W., Ni, Y., Xie, G., Liu, Z. and Sun, M. (2023). Ultrafeedback: Boosting language models with high-quality feedback. arXiv preprint arXiv:2310.01377 . Ding et al. (2023) Ding, N., Chen, Y., Xu, B., Qin, Y., Zheng, Z., Hu, S., Liu, Z., Sun, M. and Zhou, B. (2023). Enhancing chat language models by scaling high-quality instructional conversations. arXiv preprint arXiv:2305.14233 . Dong et al. (2023) Dong, H., Xiong, W., Goyal, D., Zhang, Y., Chow, W., Pan, R., Diao, S., Zhang, J., Shum, K. and Zhang, T. (2023). Raft: Reward ranked finetuning for generative foundation model alignment. arXiv preprint arXiv:2304.06767 . Du et al. (2024) Du, Y., Winnicki, A., Dalal, G., Mannor, S. and Srikant, R. (2024). Exploration-driven policy optimization in rlhf: Theoretical insights on efficient data utilization. arXiv preprint arXiv:2402.10342 . Dubois et al. (2024) Dubois, Y., Galambosi, B., Liang, P. and Hashimoto, T. B. (2024). Length-controlled alpacaeval: A simple way to debias automatic evaluators. arXiv preprint arXiv:2404.04475 . Eisenstein et al. (2023) Eisenstein, J., Nagpal, C., Agarwal, A., Beirami, A., D’Amour, A., Dvijotham, D., Fisch, A., Heller, K., Pfohl, S., Ramachandran, D. et al. (2023). Helping or herding? reward model ensembles mitigate but do not eliminate reward hacking. arXiv preprint arXiv:2312.09244 . Engstrom et al. (2020) Engstrom, L., Ilyas, A., Santurkar, S., Tsipras, D., Janoos, F., Rudolph, L. and Madry, A. (2020). Implementation matters in deep policy gradients: A case study on ppo and trpo. arXiv preprint arXiv:2005.12729 . Fan (1953) Fan, K. (1953). Minimax theorems. Proceedings of the National Academy of Sciences 39 42–47. Fu et al. (2022) Fu, Z., Qi, Z., Wang, Z., Yang, Z., Xu, Y. and Kosorok, M. R. (2022). Offline reinforcement learning with instrumental variables in confounded markov decision processes. arXiv preprint arXiv:2209.08666 . Ganguli et al. (2022) Ganguli, D., Lovitt, L., Kernion, J., Askell, A., Bai, Y., Kadavath, S., Mann, B., Perez, E., Schiefer, N., Ndousse, K. et al. (2022). Red teaming language models to reduce harms: Methods, scaling behaviors, and lessons learned. arXiv preprint arXiv:2209.07858 . Gao et al. (2023) Gao, L., Schulman, J. and Hilton, J. (2023). Scaling laws for reward model overoptimization. In International Conference on Machine Learning. PMLR. Gehman et al. (2020) Gehman, S., Gururangan, S., Sap, M., Choi, Y. and Smith, N. A. (2020). Realtoxicityprompts: Evaluating neural toxic degeneration in language models. arXiv preprint arXiv:2009.11462 . Hong et al. (2024) Hong, J., Lee, N. and Thorne, J. (2024). Orpo: Monolithic preference optimization without reference model. arXiv preprint arXiv:2403.07691 . Hu et al. (2024) Hu, J., Wu, X., Wang, W., Xianyu, Zhang, D. and Cao, Y. (2024). Openrlhf: An easy-to-use, scalable and high-performance rlhf framework. arXiv preprint arXiv:2405.11143 . Ji et al. (2024) Ji, H., Lu, C., Niu, Y., Ke, P., Wang, H., Zhu, J., Tang, J. and Huang, M. (2024). Towards efficient and exact optimization of language model alignment. arXiv preprint arXiv:2402.00856 . Jin et al. (2021) Jin, Y., Yang, Z. and Wang, Z. (2021). Is pessimism provably efficient for offline rl? In International Conference on Machine Learning. PMLR. Li et al. (2023) Li, Z., Yang, Z. and Wang, M. (2023). Reinforcement learning with human feedback: Learning dynamic choices via pessimism. arXiv preprint arXiv:2305.18438 . Liang et al. (2024) Liang, X., Chen, C., Wang, J., Wu, Y., Fu, Z., Shi, Z., Wu, F. and Ye, J. (2024). Robust preference optimization with provable noise tolerance for llms. arXiv preprint arXiv:2404.04102 . Liu et al. (2023a) Liu, T., Zhao, Y., Joshi, R., Khalman, M., Saleh, M., Liu, P. J. and Liu, J. (2023a). Statistical rejection sampling improves preference optimization. arXiv preprint arXiv:2309.06657 . Liu et al. (2023b) Liu, W., Zeng, W., He, K., Jiang, Y. and He, J. (2023b). What makes good data for alignment? a comprehensive study of automatic data selection in instruction tuning. arXiv preprint arXiv:2312.15685 . Liu et al. (2022a) Liu, Z., Lu, M., Wang, Z., Jordan, M. and Yang, Z. (2022a). Welfare maximization in competitive equilibrium: Reinforcement learning for markov exchange economy. In International Conference on Machine Learning. PMLR. Liu et al. (2024) Liu, Z., Lu, M., Xiong, W., Zhong, H., Hu, H., Zhang, S., Zheng, S., Yang, Z. and Wang, Z. (2024). Maximize to explore: One objective function fusing estimation, planning, and exploration. Advances in Neural Information Processing Systems 36. Liu et al. (2022b) Liu, Z., Zhang, Y., Fu, Z., Yang, Z. and Wang, Z. (2022b). Learning from demonstration: Provably efficient adversarial policy imitation with linear function approximation. In International conference on machine learning. PMLR. Lu et al. (2022) Lu, M., Min, Y., Wang, Z. and Yang, Z. (2022). Pessimism in the face of confounders: Provably efficient offline reinforcement learning in partially observable markov decision processes. arXiv preprint arXiv:2205.13589 . Michaud et al. (2020) Michaud, E. J., Gleave, A. and Russell, S. (2020). Understanding learned reward functions. arXiv preprint arXiv:2012.05862 . Moskovitz et al. (2023) Moskovitz, T., Singh, A. K., Strouse, D., Sandholm, T., Salakhutdinov, R., Dragan, A. D. and McAleer, S. (2023). Confronting reward model overoptimization with constrained rlhf. arXiv preprint arXiv:2310.04373 . Ouyang et al. (2022) Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A. et al. (2022). Training language models to follow instructions with human feedback. Advances in neural information processing systems 35 27730–27744. Pacchiano et al. (2021) Pacchiano, A., Saha, A. and Lee, J. (2021). Dueling rl: reinforcement learning with trajectory preferences. arXiv preprint arXiv:2111.04850 . Pal et al. (2024) Pal, A., Karkhanis, D., Dooley, S., Roberts, M., Naidu, S. and White, C. (2024). Smaug: Fixing failure modes of preference optimisation with dpo-positive. arXiv preprint arXiv:2402.13228 . Rafailov et al. (2024) Rafailov, R., Hejna, J., Park, R. and Finn, C. (2024). From r to q⋆superscript⋆q q⋆: Your language model is secretly a q-function. arXiv preprint arXiv:2404.12358 . Rafailov et al. (2023) 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. Advances in Neural Information Processing Systems 36. Rashidinejad et al. (2021) Rashidinejad, P., Zhu, B., Ma, C., Jiao, J. and Russell, S. (2021). Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems 34 11702–11716. Rashidinejad et al. (2022) Rashidinejad, P., Zhu, H., Yang, K., Russell, S. and Jiao, J. (2022). Optimal conservative offline rl with general function approximation via augmented lagrangian. arXiv preprint arXiv:2211.00716 . Rita et al. (2024) Rita, M., Strub, F., Chaabouni, R., Michel, P., Dupoux, E. and Pietquin, O. (2024). Countering reward over-optimization in llm with demonstration-guided reinforcement learning. arXiv preprint arXiv:2404.19409 . Rosset et al. (2024) Rosset, C., Cheng, C.-A., Mitra, A., Santacroce, M., Awadallah, A. and Xie, T. (2024). Direct nash optimization: Teaching language models to self-improve with general preferences. arXiv preprint arXiv:2404.03715 . Schulman et al. (2017) Schulman, J., Wolski, F., Dhariwal, P., Radford, A. and Klimov, O. (2017). Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347 . Shi and Chi (2024) Shi, L. and Chi, Y. (2024). Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity. Journal of Machine Learning Research 25 1–91. Shi et al. (2022) Shi, L., Li, G., Wei, Y., Chen, Y. and Chi, Y. (2022). Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity. In International conference on machine learning. PMLR. Tajwar et al. (2024) Tajwar, F., Singh, A., Sharma, A., Rafailov, R., Schneider, J., Xie, T., Ermon, S., Finn, C. and Kumar, A. (2024). Preference fine-tuning of llms should leverage suboptimal, on-policy data. arXiv preprint arXiv:2404.14367 . Tang et al. (2024) Tang, Y., Guo, Z. D., Zheng, Z., Calandriello, D., Munos, R., Rowland, M., Richemond, P. H., Valko, M., Pires, B. Á. and Piot, B. (2024). Generalized preference optimization: A unified approach to offline alignment. arXiv preprint arXiv:2402.05749 . Taori et al. (2023) Taori, R., Gulrajani, I., Zhang, T., Dubois, Y., Li, X., Guestrin, C., Liang, P. and Hashimoto, T. B. (2023). Stanford alpaca: An instruction-following llama model. Team et al. (2023) Team, G., Anil, R., Borgeaud, S., Wu, Y., Alayrac, J.-B., Yu, J., Soricut, R., Schalkwyk, J., Dai, A. M., Hauth, A. et al. (2023). Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312.11805 . Tien et al. (2022) Tien, J., He, J. Z.-Y., Erickson, Z., Dragan, A. D. and Brown, D. S. (2022). Causal confusion and reward misidentification in preference-based reward learning. arXiv preprint arXiv:2204.06601 . Tunstall et al. (2023a) Tunstall, L., Beeching, E., Lambert, N., Rajani, N., Huang, S., Rasul, K., Rush, A. M. and Wolf, T. (2023a). The alignment handbook. https://github.com/huggingface/alignment-handbook. Tunstall et al. (2023b) Tunstall, L., Beeching, E., Lambert, N., Rajani, N., Rasul, K., Belkada, Y., Huang, S., von Werra, L., Fourrier, C., Habib, N. et al. (2023b). Zephyr: Direct distillation of lm alignment. arXiv preprint arXiv:2310.16944 . Uehara and Sun (2021) Uehara, M. and Sun, W. (2021). Pessimistic model-based offline reinforcement learning under partial coverage. In International Conference on Learning Representations. Wang et al. (2023a) Wang, P., Li, L., Chen, L., Zhu, D., Lin, B., Cao, Y., Liu, Q., Liu, T. and Sui, Z. (2023a). Large language models are not fair evaluators. arXiv preprint arXiv:2305.17926 . Wang et al. (2023b) Wang, Y., Liu, Q. and Jin, C. (2023b). Is rlhf more difficult than standard rl? a theoretical perspective. Advances in Neural Information Processing Systems 36. Wu et al. (2024) Wu, Y., Sun, Z., Yuan, H., Ji, K., Yang, Y. and Gu, Q. (2024). Self-play preference optimization for language model alignment. arXiv preprint arXiv:2405.00675 . Xie et al. (2021a) Xie, T., Cheng, C.-A., Jiang, N., Mineiro, P. and Agarwal, A. (2021a). Bellman-consistent pessimism for offline reinforcement learning. Advances in neural information processing systems 34 6683–6694. Xie et al. (2021b) Xie, T., Jiang, N., Wang, H., Xiong, C. and Bai, Y. (2021b). Policy finetuning: Bridging sample-efficient offline and online reinforcement learning. Advances in neural information processing systems 34 27395–27407. Xiong et al. (2023) Xiong, W., Dong, H., Ye, C., Zhong, H., Jiang, N. and Zhang, T. (2023). Gibbs sampling from human feedback: A provable kl-constrained framework for rlhf. arXiv preprint arXiv:2312.11456 . Xiong et al. (2022) Xiong, W., Zhong, H., Shi, C., Shen, C., Wang, L. and Zhang, T. (2022). Nearly minimax optimal offline reinforcement learning with linear function approximation: Single-agent mdp and markov game. arXiv preprint arXiv:2205.15512 . Xu et al. (2024) Xu, S., Fu, W., Gao, J., Ye, W., Liu, W., Mei, Z., Wang, G., Yu, C. and Wu, Y. (2024). Is dpo superior to ppo for llm alignment? a comprehensive study. arXiv preprint arXiv:2404.10719 . Ye et al. (2024) Ye, C., Xiong, W., Zhang, Y., Jiang, N. and Zhang, T. (2024). A theoretical analysis of nash learning from human feedback under general kl-regularized preference. arXiv preprint arXiv:2402.07314 . Yin and Wang (2021) Yin, M. and Wang, Y.-X. (2021). Towards instance-optimal offline reinforcement learning with pessimism. Advances in neural information processing systems 34 4065–4078. Yue et al. (2012) Yue, Y., Broder, J., Kleinberg, R. and Joachims, T. (2012). The k-armed dueling bandits problem. Journal of Computer and System Sciences 78 1538–1556. Zhan et al. (2022) Zhan, W., Huang, B., Huang, A., Jiang, N. and Lee, J. (2022). Offline reinforcement learning with realizability and single-policy concentrability. In Conference on Learning Theory. PMLR. Zhan et al. (2023a) Zhan, W., Uehara, M., Kallus, N., Lee, J. D. and Sun, W. (2023a). Provable offline preference-based reinforcement learning. In The Twelfth International Conference on Learning Representations. Zhan et al. (2023b) Zhan, W., Uehara, M., Sun, W. and Lee, J. D. (2023b). How to query human feedback efficiently in rl? arXiv preprint arXiv:2305.18505 . Zhang et al. (2024a) Zhang, R., Lin, L., Bai, Y. and Mei, S. (2024a). Negative preference optimization: From catastrophic collapse to effective unlearning. arXiv preprint arXiv:2404.05868 . Zhang (2023) Zhang, T. (2023). Mathematical analysis of machine learning algorithms. Cambridge University Press. Zhang et al. (2024b) Zhang, X., Ton, J.-F., Shen, W., Wang, H. and Liu, Y. (2024b). Overcoming reward overoptimization via adversarial policy optimization with lightweight uncertainty estimation. arXiv preprint arXiv:2403.05171 . Zhao et al. (2023) Zhao, Y., Joshi, R., Liu, T., Khalman, M., Saleh, M. and Liu, P. J. (2023). Slic-hf: Sequence likelihood calibration with human feedback. arXiv preprint arXiv:2305.10425 . Zheng et al. (2024) Zheng, L., Chiang, W.-L., Sheng, Y., Zhuang, S., Wu, Z., Zhuang, Y., Lin, Z., Li, Z., Li, D., Xing, E. et al. (2024). Judging llm-as-a-judge with mt-bench and chatbot arena. Advances in Neural Information Processing Systems 36. Zhong et al. (2024) Zhong, H., Feng, G., Xiong, W., Zhao, L., He, D., Bian, J. and Wang, L. (2024). Dpo meets ppo: Reinforced token optimization for rlhf. arXiv preprint arXiv:2404.18922 . Zhou (2002) Zhou, D.-X. (2002). The covering number in learning theory. Journal of Complexity 18 739–767. Zhu et al. (2023) Zhu, B., Jiao, J. and Jordan, M. I. (2023). Principled reinforcement learning with human feedback from pairwise or k-wise comparisons. arXiv preprint arXiv:2301.11270 . Zhu et al. (2024) Zhu, B., Jordan, M. I. and Jiao, J. (2024). Iterative data smoothing: Mitigating reward overfitting and overoptimization in rlhf. arXiv preprint arXiv:2401.16335 . Ziegler et al. (2019) Ziegler, D. M., Stiennon, N., Wu, J., Brown, T. B., Radford, A., Amodei, D., Christiano, P. and Irving, G. (2019). Fine-tuning language models from human preferences. arXiv preprint arXiv:1909.08593 . Appendix A Further Discussions In this section, we make several further discussions on the RPO algorithm and its theory Discussions on the partial coverage assumption (Assumption 5.2). A sufficient condition to make this partial coverage condition (Assumption 5.2) hold is that the distribution of the offline dataset, which is μsubscript _Dμcaligraphic_D, can well cover the joint distribution of (a1,a0)∼(π,πbase)similar-tosuperscript1superscript0superscriptbase(a^1,a^0) (π,π^base)( a1 , a0 ) ∼ ( π , πroman_base ). Here to discuss focus on πbase=πchosensuperscriptbasesuperscriptchosenπ^base=π^chosenπroman_base = πroman_chosen as we adopted in the experiment part. First, we clarify that the offline dataset distribution μsubscript _Dμcaligraphic_D is not simply (a1,a0)∼(πunchosen,πchosen)similar-tosuperscript1superscript0superscriptunchosensuperscriptchosen(a^1,a^0) (π^unchosen,π^chosen)( a1 , a0 ) ∼ ( πroman_unchosen , πroman_chosen ), since according to our definition (see Section 2) whether a1superscript1a^1a1 or a0superscript0a^0a0 is chosen is random and is determined by y∈0,101y∈0,1y ∈ 0 , 1 obeying the BT model. Thus, (a1,a0)∼μsimilar-tosuperscript1superscript0subscript(a^1,a^0) _D( a1 , a0 ) ∼ μcaligraphic_D can be interpreted as a mixture of (πunchosen,πchosen)superscriptunchosensuperscriptchosen(π^unchosen,π^chosen)( πroman_unchosen , πroman_chosen ) and (πchosen,πunchosen)superscriptchosensuperscriptunchosen(π^chosen,π^unchosen)( πroman_chosen , πroman_unchosen ). This mixture probability would not be too small as long as the quality of (a1,a0)superscript1superscript0(a^1,a^0)( a1 , a0 ) does not vary too much, i.e., both of them are possible to be chosen, which is the case in practice. As a result, in the offline data distribution (a1,a0)∼μsimilar-tosuperscript1superscript0subscript(a^1,a^0) _D( a1 , a0 ) ∼ μcaligraphic_D, both a1superscript1a^1a1 and a0superscript0a^0a0 partly comes from the chosen distribution πchosensuperscriptchosenπ^chosenπroman_chosen. Then in order for μsubscript _Dμcaligraphic_D to cover the joint distribution of (a1,a0)∼(π,πbase)similar-tosuperscript1superscript0superscriptbase(a^1,a^0) (π,π^base)( a1 , a0 ) ∼ ( π , πroman_base ), it suffices to argue that πchosensuperscriptchosenπ^chosenπroman_chosen can cover the target policy π, which is then reduced back to the traditional coverage condition. Thus our assumption essentially requires that πchosensuperscriptchosenπ^chosenπroman_chosen well covers and only needs to cover the target policy π. This coincides with the spirit of the minimal data assumption in offline RL theory, i.e., the so-called partial coverage condition. On the relationship between observed chosen probability and reward overoptimization. First, we note that the actions and their chosen probabilities can be interpreted as a proxy of analyzing the underlying (estimated) reward model r^ rover start_ARG r end_ARG due to the representation πr^⁢(a|x)∝πref⁢(a|x)⁢exp⁡(β−1⁢r^⁢(x,a))proportional-tosubscript^conditionalsuperscriptrefconditionalsuperscript1 _ r(a|x) π^ref(a|x) (β^-1 r% (x,a))πover start_ARG r end_ARG ( a | x ) ∝ πroman_ref ( a | x ) exp ( β- 1 over start_ARG r end_ARG ( x , a ) ). Analyzing the (log) probabilities of the actions can be utilized to detect the mitigation of over-optimization, because according to the representation, an overestimated reward of a poor action would result in a higher probability of choosing this action, and would also cause a decay in the probability of choosing other better actions (since the probabilities are normalized to 1111). To further showcase the ability of RPO to address overoptimization (through the lense of probability), consider the following theoretical example with only one state and three actions (Xu et al., 2024) where we can track everything clearly. It has three actions a,b,ca,b,ca , b , c with R⋆⁢(a)=1,R⋆⁢(b)=0.5,R⋆⁢(c)=0formulae-sequencesuperscript⋆1formulae-sequencesuperscript⋆0.5superscript⋆0R (a)=1,R (b)=0.5,R (c)=0R⋆ ( a ) = 1 , R⋆ ( b ) = 0.5 , R⋆ ( c ) = 0. The reference policy πref⁢(a)=πref⁢(b)=0.4,πref⁢(c)=0.1formulae-sequencesuperscriptrefsuperscriptref0.4superscriptref0.1π^ref(a)=π^ref(b)=0.4,π^ref(c)=0.1πroman_ref ( a ) = πroman_ref ( b ) = 0.4 , πroman_ref ( c ) = 0.1, and the dataset consists of one data point =(a,b,1)1D=(a,b,1)D = ( a , b , 1 ) (meaning action a is preferred in the data). Then an ideally solved DPO objective would be πDPOsubscriptDPO _DPOπroman_DPO as long as πDPO⁢(b)=0superscriptDPO0π^DPO(b)=0πroman_DPO ( b ) = 0, and the value of πDPO⁢(a)superscriptDPOπ^DPO(a)πroman_DPO ( a ) can be arbitrarily chosen in [0,1]01[0,1][ 0 , 1 ]. Thus a possible solution to DPO would be πDPO⁢(a)=0.5,πDPO⁢(b)=0formulae-sequencesuperscriptDPO0.5superscriptDPO0π^DPO(a)=0.5,π^DPO(b)=0πroman_DPO ( a ) = 0.5 , πroman_DPO ( b ) = 0, and by the normalizing condition πDPO⁢(c)=0.5superscriptDPO0.5π^DPO(c)=0.5πroman_DPO ( c ) = 0.5, which is undesirable since the action c has reward R⋆⁢(c)=0superscript⋆0R (c)=0R⋆ ( c ) = 0. In contrast, solving the RPO objective would additionally require the maximization of πRPO⁢(a)subscriptRPO _RPO(a)πroman_RPO ( a ) due to the SFT regularization term, and thus the solution is shifted towards πRPO⁢(a)=1,πRPO⁢(b)=πRPO⁢(c)=0formulae-sequencesubscriptRPO1subscriptRPOsubscriptRPO0 _RPO(a)=1, _RPO(b)= _RPO(c)=0πroman_RPO ( a ) = 1 , πroman_RPO ( b ) = πroman_RPO ( c ) = 0, which is better than the DPO policy. Thus, RPO is able to prevent overoptimization towards poor actions that are less covered by the dataset (action c here), therefore resulting in a better policy. About the relationships and distinctions between PTX loss in (Taori et al., 2023) and the SFT loss of RPO. The original PTX loss is an imitation loss calculated on the pretraining data. In contrast, the SFT loss in the RPO objective is an imitation loss calculated on the RLHF dataset. In more specific, our experiments use this SFT loss to imitate the chosen responses in the RLHF dataset. Thus the relationship is that they are both imitation loss which aims to mimic certain data distribution. The distinction is that they are calculated on different data sources. The SFT loss in the RPO objective naturally comes from our theoretical algorithm and provably serves as an important regularization term to mitigate overoptimization in offline RLHF. About the computational complexity of the SFT loss gradient. According to the paragraph Practical implementation in Section 6, RPO adds an additional SFT loss (the log probability of the chosen labels in the preference dataset) on the original DPO loss, where we highlight that the SFT loss is actually an intermediate quantity in the calculation of the DPO loss. Therefore, our proposed method does not incur any additional computation overhead compared with the vanilla DPO. Appendix B Proofs for Sample Complexity Analysis B.1 Concepts We provide some useful concepts for the simplicity of later discussions. • Hellinger distance DHellinger⁢(p∥q)subscriptHellingerconditionalD_Hellinger(p\|q)Droman_Hellinger ( p ∥ q ) between two probability density functions p and q defined on XX is defined as DHellinger⁢(p∥q)=12⁢∫x∈(p⁢(x)−q⁢(x))2⁢dx.subscriptHellingerconditional12subscriptsuperscript2differential-d D_Hellinger(p\|q)= 12 _x % ( p(x)- q(x) )^2dx.Droman_Hellinger ( p ∥ q ) = divide start_ARG 1 end_ARG start_ARG 2 end_ARG ∫x ∈ X ( square-root start_ARG p ( x ) end_ARG - square-root start_ARG q ( x ) end_ARG )2 d x . • Total variation (TV) distance DTV⁢(p∥q)subscriptTVconditionalD_TV(p\|q)Droman_TV ( p ∥ q ) between two probability density functions p and q defined on XX is defined as DTV⁢(p∥q)=12⁢∫x∈|p⁢(x)−q⁢(x)|⁢dx.subscriptTVconditional12subscriptdifferential-d D_TV(p\|q)= 12 _x |p(x)-q(% x)|dx.Droman_TV ( p ∥ q ) = divide start_ARG 1 end_ARG start_ARG 2 end_ARG ∫x ∈ X | p ( x ) - q ( x ) | d x . • Kullback–Leibler (KL) divergence KL⁢(p∥q)KLconditionalKL(p\|q)KL ( p ∥ q ) between two probability density functions p and q defined on XX is defined as KL⁢(p∥q)=∫x∈log⁡(p⁢(x)q⁢(x))⁢p⁢(x)⁢dx.KLconditionalsubscriptdifferential-d (p\|q)= _x ( p(x)q(x)% )p(x)dx.KL ( p ∥ q ) = ∫x ∈ X log ( divide start_ARG p ( x ) end_ARG start_ARG q ( x ) end_ARG ) p ( x ) d x . • We denote ϵ(ℱ,∥⋅∥∞)N_ε(F,\|·\|_∞)Nitalic_ϵ ( F , ∥ ⋅ ∥∞ ) as the ϵitalic-ϵεϵ-covering number (Zhou, 2002) for function class ℱFF under the infinity norm ∥⋅∥∞\|·\|_∞∥ ⋅ ∥∞. Widely used in the theoretical analysis, the ϵitalic-ϵεϵ-covering number characterizes the complexity of the function class ℱFF. B.2 Proof of Theorem 5.3 Proof of Theorem 5.3. By definition, the suboptimality gap of π^ πover start_ARG π end_ARG w.r.t. π is decomposed as following, Gapπ⁢(π^)superscriptGap ^π( π)Gapitalic_π ( over start_ARG π end_ARG ) (B.1) =x∼d0,a∼π(⋅|x)⁢[r⋆⁢(x,a)]−x∼d0,a∼π^(⋅|x)⁢[r⋆⁢(x,a)] =E_x d_0,a π(·|x) [r % (x,a) ]-E_x d_0,a π(·|x) [r^% (x,a) ]= blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 , a ∼ π ( ⋅ | x ) end_POSTSUBSCRIPT [ r⋆ ( x , a ) ] - blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 , a ∼ over start_ARG π end_ARG ( ⋅ | x ) end_POSTSUBSCRIPT [ r⋆ ( x , a ) ] (B.2) =x∼d0,a1∼π(⋅|x),a0∼πbase(⋅|x)[r⋆(x,a1)−r⋆(x,a0)−β⋅KL(π(⋅|x)∥πref(⋅|x))] =E_x d_0,a^1 π(·|x),a^0 π% ^base(·|x) [r (x,a^1)-r (x,a^0)-β% ·KL (π(·|x)\|π^ref(·|x) ) ]= blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ π ( ⋅ | x ) , a0 ∼ πroman_base ( ⋅ | x ) end_POSTSUBSCRIPT [ r⋆ ( x , a1 ) - r⋆ ( x , a0 ) - β ⋅ KL ( π ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] (B.3) −η−1⋅minr∈ℛη⋅x∼d0,a1∼π^(⋅|x),a0∼πbase(⋅|x)[r(x,a1)−r(x,a0)−β⋅KL(π^(⋅|x)∥πref(⋅|x))]+ℒ(r) -η^-1· _r \η·% E_ subarraycx d_0,a^1 π(·|x),\\ a^0 π^base(·|x) subarray [r(x,a^1)-r(x,a^0% )-β·KL ( π(·|x)\|π^ref(% ·|x) ) ]+L_D(r) \- η- 1 ⋅ minitalic_r ∈ R η ⋅ blackboard_Estart_ARG start_ROW start_CELL x ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ over start_ARG π end_ARG ( ⋅ | x ) , end_CELL end_ROW start_ROW start_CELL a0 ∼ πroman_base ( ⋅ | x ) end_CELL end_ROW end_ARG end_POSTSUBSCRIPT [ r ( x , a1 ) - r ( x , a0 ) - β ⋅ KL ( over start_ARG π end_ARG ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] + Lcaligraphic_D ( r ) (B.4) +η−1⋅minr∈ℛη⋅x∼d0,a1∼π^(⋅|x),a0∼πbase(⋅|x)[r(x,a1)−r(x,a0)−β⋅KL(π^(⋅|x)∥πref(⋅|x))]+ℒ(r) +η^-1· _r \η·% E_ subarraycx d_0,a^1 π(·|x),\\ a^0 π^base(·|x) subarray [r(x,a^1)-r(x,a^0% )-β·KL ( π(·|x)\|π^ref(% ·|x) ) ]+L_D(r) \+ η- 1 ⋅ minitalic_r ∈ R η ⋅ blackboard_Estart_ARG start_ROW start_CELL x ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ over start_ARG π end_ARG ( ⋅ | x ) , end_CELL end_ROW start_ROW start_CELL a0 ∼ πroman_base ( ⋅ | x ) end_CELL end_ROW end_ARG end_POSTSUBSCRIPT [ r ( x , a1 ) - r ( x , a0 ) - β ⋅ KL ( over start_ARG π end_ARG ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] + Lcaligraphic_D ( r ) (B.5) −x∼d0,a1∼π^(⋅|x),a0∼πbase(⋅|x)[r⋆(x,a1)−r⋆(x,a0)−β⋅KL(π^(⋅|x)∥πref(⋅|x))] -E_x d_0,a^1 π(·% |x),a^0 π^base(·|x) [r (x,a^1)-r (% x,a^0)-β·KL ( π(·|x)\|π^ref% (·|x) ) ]- blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ over start_ARG π end_ARG ( ⋅ | x ) , a0 ∼ πroman_base ( ⋅ | x ) end_POSTSUBSCRIPT [ r⋆ ( x , a1 ) - r⋆ ( x , a0 ) - β ⋅ KL ( over start_ARG π end_ARG ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] (B.6) +β⋅x∼d0[KL(π(⋅|x)∥πref(⋅|x))−KL(π^(⋅|x)∥πref(⋅|x))] +β·E_x d_0 [KL% (π(·|x)\|π^ref(·|x) )-KL (% π(·|x)\|π^ref(·|x) ) ]+ β ⋅ blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT [ KL ( π ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) - KL ( over start_ARG π end_ARG ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] (B.7) :=Term (A)+Term (B)+Term (C),assignabsentTerm (A)Term (B)Term (C) :=Term (A)+Term (B)+Term (C),:= Term (A) + Term (B) + Term (C) , (B.8) where in the above Term (A), Term (B), and Term (C) are abbreviations for Term (A) =x∼d0,a1∼π(⋅|x),a0∼πbase(⋅|x)[r⋆(x,a1)−r⋆(x,a0)−β⋅KL(π(⋅|x)∥πref(⋅|x))] =E_x d_0,a^1 π(·|x),a^0 π^% base(·|x) [r (x,a^1)-r (x,a^0)-β% ·KL (π(·|x)\|π^ref(·|x) ) ]= blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ π ( ⋅ | x ) , a0 ∼ πroman_base ( ⋅ | x ) end_POSTSUBSCRIPT [ r⋆ ( x , a1 ) - r⋆ ( x , a0 ) - β ⋅ KL ( π ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] (B.9) −η−1⋅minr∈ℛη⋅x∼d0,a1∼π^(⋅|x),a0∼πbase(⋅|x)[r(x,a1)−r(x,a0)−β⋅KL(π^(⋅|x)∥πref(⋅|x))]+ℒ(r), -η^-1· _r \η·% E_ subarraycx d_0,a^1 π(·|x),\\ a^0 π^base(·|x) subarray [r(x,a^1)-r(x,a^0% )-β·KL ( π(·|x)\|π^ref(% ·|x) ) ]+L_D(r) \,- η- 1 ⋅ minitalic_r ∈ R η ⋅ blackboard_Estart_ARG start_ROW start_CELL x ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ over start_ARG π end_ARG ( ⋅ | x ) , end_CELL end_ROW start_ROW start_CELL a0 ∼ πroman_base ( ⋅ | x ) end_CELL end_ROW end_ARG end_POSTSUBSCRIPT [ r ( x , a1 ) - r ( x , a0 ) - β ⋅ KL ( over start_ARG π end_ARG ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] + Lcaligraphic_D ( r ) , (B.10) and Term (B) =η−1⋅minr∈ℛη⋅x∼d0,a1∼π^(⋅|x),a0∼πbase(⋅|x)[r(x,a1)−r(x,a0)−β⋅KL(π^(⋅|x)∥πref(⋅|x))]+ℒ(r) =η^-1· _r \η·E_% subarraycx d_0,a^1 π(·|x),\\ a^0 π^base(·|x) subarray [r(x,a^1)-r(x,a^0% )-β·KL ( π(·|x)\|π^ref(% ·|x) ) ]+L_D(r) \= η- 1 ⋅ minitalic_r ∈ R η ⋅ blackboard_Estart_ARG start_ROW start_CELL x ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ over start_ARG π end_ARG ( ⋅ | x ) , end_CELL end_ROW start_ROW start_CELL a0 ∼ πroman_base ( ⋅ | x ) end_CELL end_ROW end_ARG end_POSTSUBSCRIPT [ r ( x , a1 ) - r ( x , a0 ) - β ⋅ KL ( over start_ARG π end_ARG ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] + Lcaligraphic_D ( r ) (B.11) −x∼d0,a1∼π^(⋅|x),a0∼πbase(⋅|x)[r⋆(x,a1)−r⋆(x,a0)−β⋅KL(π^(⋅|x)∥πref(⋅|x))], -E_x d_0,a^1 π(·|x),a^% 0 π^base(·|x) [r (x,a^1)-r (x,a^0% )-β·KL ( π(·|x)\|π^ref(% ·|x) ) ],- blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ over start_ARG π end_ARG ( ⋅ | x ) , a0 ∼ πroman_base ( ⋅ | x ) end_POSTSUBSCRIPT [ r⋆ ( x , a1 ) - r⋆ ( x , a0 ) - β ⋅ KL ( over start_ARG π end_ARG ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] , (B.12) and Term (C)=β⋅x∼d0[KL(π(⋅|x)∥πref(⋅|x))−KL(π^(⋅|x)∥πref(⋅|x))]. (C)=β·E_x d_0 [% KL (π(·|x)\|π^ref(·|x) )-KL (% π(·|x)\|π^ref(·|x) ) ].Term (C) = β ⋅ blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT [ KL ( π ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) - KL ( over start_ARG π end_ARG ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] . (B.13) In the following, we analyze Term (A) and Term (B) respectively. Upper bound Term (A). Notice that by the optimality of our choice of policy π^ πover start_ARG π end_ARG in (3.3), we have Term (A) (B.14) =x∼d0,a1∼π(⋅|x),a0∼πbase(⋅|x)[r⋆(x,a1)−r⋆(x,a0)−β⋅KL(π(⋅|x)∥πref(⋅|x))] =E_x d_0,a^1 π(·|x),a^0 π% ^base(·|x) [r (x,a^1)-r (x,a^0)-β% ·KL (π(·|x)\|π^ref(·|x) ) ]= blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ π ( ⋅ | x ) , a0 ∼ πroman_base ( ⋅ | x ) end_POSTSUBSCRIPT [ r⋆ ( x , a1 ) - r⋆ ( x , a0 ) - β ⋅ KL ( π ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] (B.15) −η−1⋅minr∈ℛη⋅x∼d0,a1∼π^(⋅|x),a0∼πbase(⋅|x)[r(x,a1)−r(x,a0)−β⋅KL(π^(⋅|x)∥πref(⋅|x))]+ℒ(r) -η^-1· _r \η·% E_ subarraycx d_0,a^1 π(·|x),\\ a^0 π^base(·|x) subarray [r(x,a^1)-r(x,a^0% )-β·KL ( π(·|x)\|π^ref(% ·|x) ) ]+L_D(r) \- η- 1 ⋅ minitalic_r ∈ R η ⋅ blackboard_Estart_ARG start_ROW start_CELL x ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ over start_ARG π end_ARG ( ⋅ | x ) , end_CELL end_ROW start_ROW start_CELL a0 ∼ πroman_base ( ⋅ | x ) end_CELL end_ROW end_ARG end_POSTSUBSCRIPT [ r ( x , a1 ) - r ( x , a0 ) - β ⋅ KL ( over start_ARG π end_ARG ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] + Lcaligraphic_D ( r ) (B.16) ≤x∼d0,a1∼π(⋅|x),a0∼πref(⋅|x)[r⋆(x,a1)−r⋆(x,a0)−β⋅KL(π(⋅|x)∥πref(⋅|x))] _x d_0,a^1 π(·|x),a^0 % π^ref(·|x) [r (x,a^1)-r (x,a^0)-β% ·KL (π(·|x)\|π^ref(·|x) ) ]≤ blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ π ( ⋅ | x ) , a0 ∼ πroman_ref ( ⋅ | x ) end_POSTSUBSCRIPT [ r⋆ ( x , a1 ) - r⋆ ( x , a0 ) - β ⋅ KL ( π ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] (B.17) −η−1⋅minr∈ℛη⋅x∼d0,a1∼π(⋅|x),a0∼πbase(⋅|x)[r(x,a1)−r(x,a0)−β⋅KL(π(⋅|x)∥πref(⋅|x))]+ℒ(r) -η^-1· _r \η·% E_ subarraycx d_0,a^1 π(·|x),\\ a^0 π^base(·|x) subarray [r(x,a^1)-r(x,a^0% )-β·KL (π(·|x)\|π^ref(·|x) )% ]+L_D(r) \- η- 1 ⋅ minitalic_r ∈ R η ⋅ blackboard_Estart_ARG start_ROW start_CELL x ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ π ( ⋅ | x ) , end_CELL end_ROW start_ROW start_CELL a0 ∼ πroman_base ( ⋅ | x ) end_CELL end_ROW end_ARG end_POSTSUBSCRIPT [ r ( x , a1 ) - r ( x , a0 ) - β ⋅ KL ( π ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] + Lcaligraphic_D ( r ) (B.18) =maxr∈ℛ⁡x∼d0,a1∼π(⋅|x),a0∼πbase(⋅|x)⁢[(r⋆⁢(x,a1)−r⋆⁢(x,a0))−(r⁢(x,a1)−r⁢(x,a0))]−η−1⋅ℒ⁢(r), = _r \E_x d_0,a^% 1 π(·|x),a^0 π^base(·|x) [ (r^% (x,a^1)-r (x,a^0) )- (r(x,a^1)-r(x,a^0) )% ]-η^-1·L_D(r) \,= maxitalic_r ∈ R blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ π ( ⋅ | x ) , a0 ∼ πroman_base ( ⋅ | x ) end_POSTSUBSCRIPT [ ( r⋆ ( x , a1 ) - r⋆ ( x , a0 ) ) - ( r ( x , a1 ) - r ( x , a0 ) ) ] - η- 1 ⋅ Lcaligraphic_D ( r ) , (B.19) where in the inequality we apply the optimality of the choice of policy π^ πover start_ARG π end_ARG in (3.3). Upper bound Term (B). For this term, we directly consider the following bound, Term (B) (B.20) =η−1⋅minr∈ℛη⋅x∼d0,a1∼π^(⋅|x),a0∼πbase(⋅|x)[r(x,a1)−r(x,a0)−β⋅KL(π^(⋅|x)∥πref(⋅|x))]+ℒ(r) =η^-1· _r \η·% E_ subarraycx d_0,a^1 π(·|x),\\ a^0 π^base(·|x) subarray [r(x,a^1)-r(x,a^0% )-β·KL ( π(·|x)\|π^ref(% ·|x) ) ]+L_D(r) \= η- 1 ⋅ minitalic_r ∈ R η ⋅ blackboard_Estart_ARG start_ROW start_CELL x ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ over start_ARG π end_ARG ( ⋅ | x ) , end_CELL end_ROW start_ROW start_CELL a0 ∼ πroman_base ( ⋅ | x ) end_CELL end_ROW end_ARG end_POSTSUBSCRIPT [ r ( x , a1 ) - r ( x , a0 ) - β ⋅ KL ( over start_ARG π end_ARG ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] + Lcaligraphic_D ( r ) (B.21) −x∼d0,a1∼π^(⋅|x),a0∼πbase(⋅|x)[r⋆(x,a1)−r⋆(x,a0)−β⋅KL(π^(⋅|x)∥πref(⋅|x))] -E_x d_0,a^1 π(·% |x),a^0 π^base(·|x) [r (x,a^1)-r (% x,a^0)-β·KL ( π(·|x)\|π^ref% (·|x) ) ]- blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ over start_ARG π end_ARG ( ⋅ | x ) , a0 ∼ πroman_base ( ⋅ | x ) end_POSTSUBSCRIPT [ r⋆ ( x , a1 ) - r⋆ ( x , a0 ) - β ⋅ KL ( over start_ARG π end_ARG ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] (B.22) ≤x∼d0,a1∼π^(⋅|x),a0∼πbase(⋅|x)[r⋆(x,a1)−r⋆(x,a0)−β⋅KL(π^(⋅|x)∥πref(⋅|x))]+η−1⋅ℒ(r⋆) _x d_0,a^1 π(·|x)% ,a^0 π^base(·|x) [r (x,a^1)-r (x,a% ^0)-β·KL ( π(·|x)\|π^ref(% ·|x) ) ]+η^-1·L_D(r )≤ blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ over start_ARG π end_ARG ( ⋅ | x ) , a0 ∼ πroman_base ( ⋅ | x ) end_POSTSUBSCRIPT [ r⋆ ( x , a1 ) - r⋆ ( x , a0 ) - β ⋅ KL ( over start_ARG π end_ARG ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] + η- 1 ⋅ Lcaligraphic_D ( r⋆ ) (B.23) −x∼d0,a1∼π^(⋅|x),a0∼πbase(⋅|x)[r⋆(x,a1)−r⋆(x,a0)−β⋅KL(π^(⋅|x)∥πref(⋅|x))] -E_x d_0,a^1 π(·% |x),a^0 π^base(·|x) [r (x,a^1)-r (% x,a^0)-β·KL ( π(·|x)\|π^ref% (·|x) ) ]- blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ over start_ARG π end_ARG ( ⋅ | x ) , a0 ∼ πroman_base ( ⋅ | x ) end_POSTSUBSCRIPT [ r⋆ ( x , a1 ) - r⋆ ( x , a0 ) - β ⋅ KL ( over start_ARG π end_ARG ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] (B.24) =η−1⋅ℒ⁢(r⋆),absent⋅superscript1subscriptℒsuperscript⋆ =η^-1·L_D(r ),= η- 1 ⋅ Lcaligraphic_D ( r⋆ ) , (B.25) where in the inequality we apply the fact that r⋆∈ℛsuperscript⋆ℛr ⋆ ∈ R by Assumption 5.1. Combining Term (A), Term (B), and Term (C). Now by (B.8), (B.15), and (B.25), we have that Gapβπ⁢(π^)=Term (A)+Term (B)+Term (C)superscriptsubscriptGap^Term (A)Term (B)Term (C) _β^π( π)=Term (A)+% Term (B)+Term (C)Gapitalic_βitalic_π ( over start_ARG π end_ARG ) = Term (A) + Term (B) + Term (C) (B.26) ≤maxr∈ℛ⁡x∼d0,a1∼π(⋅|x),a0∼πbase(⋅|x)⁢[(r⋆⁢(x,a1)−r⋆⁢(x,a0))−(r⁢(x,a1)−r⁢(x,a0))]+η−1⋅(ℒ⁢(r⋆)−ℒ⁢(r)) ≤ _r \E_ % subarraycx d_0,a^1 π(·|x),\\ a^0 π^base(·|x) subarray [ (r (x,% a^1)-r (x,a^0) )- (r(x,a^1)-r(x,a^0) ) ]+% η^-1· (L_D(r )-L_% D(r) ) \≤ maxitalic_r ∈ R blackboard_Estart_ARG start_ROW start_CELL x ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ π ( ⋅ | x ) , end_CELL end_ROW start_ROW start_CELL a0 ∼ πroman_base ( ⋅ | x ) end_CELL end_ROW end_ARG end_POSTSUBSCRIPT [ ( r⋆ ( x , a1 ) - r⋆ ( x , a0 ) ) - ( r ( x , a1 ) - r ( x , a0 ) ) ] + η- 1 ⋅ ( Lcaligraphic_D ( r⋆ ) - Lcaligraphic_D ( r ) ) (B.27) +β⋅x∼d0[KL(π(⋅|x)∥πref(⋅|x))−KL(π^(⋅|x)∥πref(⋅|x))]. +β·E_x d_0 [KL% (π(·|x)\|π^ref(·|x) )-KL (% π(·|x)\|π^ref(·|x) ) ].+ β ⋅ blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT [ KL ( π ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) - KL ( over start_ARG π end_ARG ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] . (B.28) In the following, we upper bound the right hand side of (B.26) via relating the MLE loss difference term to the reward difference term through a careful analysis of the preference model. On the one hand, we invoke Lemma B.1 to give an upper bound of the difference of the MLE loss as following, with probability at least 1−δ11- 1 - δ over random samples and ε=(6⋅(1+eR)⋅N)−1superscript⋅61superscript1 =(6·(1+e^R)· N)^-1ε = ( 6 ⋅ ( 1 + eitalic_R ) ⋅ N )- 1, for any reward model r∈ℛr ∈ R, it holds that ℒ⁢(r⋆)−ℒ⁢(r)subscriptℒsuperscript⋆subscriptℒ _D(r )-L_D(r)Lcaligraphic_D ( r⋆ ) - Lcaligraphic_D ( r ) ≤−2⋅(x,a1,a0)∼μ⁢(⋅,⋅,⋅)[DHellinger2(ℙr⋆(⋅|x,a1,a0)∥ℙr(⋅|x,a1,a0))] ≤-2·E_(x,a^1,a^0) _D(·% ,·,·) [D_Hellinger^2 (P_r (% ·|x,a^1,a^0)\|P_r(·|x,a^1,a^0) ) ]≤ - 2 ⋅ blackboard_E( x , a1 , a0 ) ∼ μ start_POSTSUBSCRIPT D ( ⋅ , ⋅ , ⋅ ) end_POSTSUBSCRIPT [ Droman_Hellinger2 ( blackboard_Pr⋆ ( ⋅ | x , a1 , a0 ) ∥ blackboard_Pr ( ⋅ | x , a1 , a0 ) ) ] (B.29) +3N⋅log⁡(ε(ℛ,∥⋅∥∞)δ), + 3N· ( N_ (% R,\|·\|_∞)δ ),+ divide start_ARG 3 end_ARG start_ARG N end_ARG ⋅ log ( divide start_ARG Nitalic_ε ( R , ∥ ⋅ ∥∞ ) end_ARG start_ARG δ end_ARG ) , (B.30) where we recall that we use the subscript r in ℙrsubscriptℙP_rblackboard_Pr to emphasize the dependence of the probabilistic model on the reward model. Here ε(ℛ,∥⋅∥∞)N_ (R,\|·\|_∞)Nitalic_ε ( R , ∥ ⋅ ∥∞ ) denotes the ε ε-covering number of the reward model class and R is the upper bound on the reward functionss (Assumption 5.1). Now to facilitate the calculation, we lower bound the Hellinger distance by total variation (TV) distance as DHellinger2(ℙr⋆(⋅|x,a1,a0)∥ℙr(⋅|x,a1,a0))≥DTV2(ℙr⋆(⋅|x,a1,a0)∥ℙr(⋅|x,a1,a0)), D_Hellinger^2 (P_r (·|x,% a^1,a^0)\|P_r(·|x,a^1,a^0) )≥ D_TV^% 2 (P_r (·|x,a^1,a^0)\|P_r(·|x,a% ^1,a^0) ),Droman_Hellinger2 ( blackboard_Pr⋆ ( ⋅ | x , a1 , a0 ) ∥ blackboard_Pr ( ⋅ | x , a1 , a0 ) ) ≥ Droman_TV2 ( blackboard_Pr⋆ ( ⋅ | x , a1 , a0 ) ∥ blackboard_Pr ( ⋅ | x , a1 , a0 ) ) , (B.31) By the expression of the probability model ℙrsubscriptℙP_rblackboard_Pr, we can further write the TV distance above as DTV(ℙr⋆(⋅|x,a1,a0)∥ℙr(⋅|x,a1,a0)) D_TV (P_r (·|x,a^1,a^0% )\|P_r(·|x,a^1,a^0) )Droman_TV ( blackboard_Pr⋆ ( ⋅ | x , a1 , a0 ) ∥ blackboard_Pr ( ⋅ | x , a1 , a0 ) ) (B.32) =12⋅|σ⁢(r⋆⁢(x,a1)−r⋆⁢(x,a0))−σ⁢(r⁢(x,a1)−r⁢(x,a0))|absent⋅12superscript⋆superscript1superscript⋆superscript0superscript1superscript0 = 12· |σ (r (x,a^1)-r^% (x,a^0) )-σ (r(x,a^1)-r(x,a^0) ) |= divide start_ARG 1 end_ARG start_ARG 2 end_ARG ⋅ | σ ( r⋆ ( x , a1 ) - r⋆ ( x , a0 ) ) - σ ( r ( x , a1 ) - r ( x , a0 ) ) | (B.33) +12⋅|σ⁢(r⋆⁢(x,a0)−r⋆⁢(x,a1))−σ⁢(r⁢(x,a0)−r⁢(x,a1))|⋅12superscript⋆superscript0superscript⋆superscript1superscript0superscript1 + 12· |σ (r (x,a^0% )-r (x,a^1) )-σ (r(x,a^0)-r(x,a^1) ) |+ divide start_ARG 1 end_ARG start_ARG 2 end_ARG ⋅ | σ ( r⋆ ( x , a0 ) - r⋆ ( x , a1 ) ) - σ ( r ( x , a0 ) - r ( x , a1 ) ) | (B.34) =|σ⁢(r⋆⁢(x,a1)−r⋆⁢(x,a0))−σ⁢(r⁢(x,a1)−r⁢(x,a0))|,absentsuperscript⋆superscript1superscript⋆superscript0superscript1superscript0 = |σ (r (x,a^1)-r (x,a^0)% )-σ (r(x,a^1)-r(x,a^0) ) |,= | σ ( r⋆ ( x , a1 ) - r⋆ ( x , a0 ) ) - σ ( r ( x , a1 ) - r ( x , a0 ) ) | , (B.35) where in the second equality we use the fact that σ⁢(−z)=1−σ⁢(z)1σ(-z)=1-σ(z)σ ( - z ) = 1 - σ ( z ). Now by Lemma B.2 and the condition that r⁢(x,a)∈[0,R]0r(x,a)∈[0,R]r ( x , a ) ∈ [ 0 , R ] for any (x,a,r)∈×ℛ(x,a,r) ×A×R( x , a , r ) ∈ X × A × R (Assumption 5.1), we know that |σ⁢(r⋆⁢(x,a1)−r⋆⁢(x,a0))−σ⁢(r⁢(x,a1)−r⁢(x,a0))|≥κ⋅|(r⋆⁢(x,a1)−r⋆⁢(x,a0))−(r⁢(x,a1)−r⁢(x,a0))|,superscript⋆superscript1superscript⋆superscript0superscript1superscript0⋅superscript⋆superscript1superscript⋆superscript0superscript1superscript0 |σ (r (x,a^1)-r (x,a^0) )-% σ (r(x,a^1)-r(x,a^0) ) |≥κ· | (r% (x,a^1)-r (x,a^0) )- (r(x,a^1)-r(x,a^0) )% |,| σ ( r⋆ ( x , a1 ) - r⋆ ( x , a0 ) ) - σ ( r ( x , a1 ) - r ( x , a0 ) ) | ≥ κ ⋅ | ( r⋆ ( x , a1 ) - r⋆ ( x , a0 ) ) - ( r ( x , a1 ) - r ( x , a0 ) ) | , (B.36) where κ=1/(1+exp⁡(R))21superscript12κ=1/(1+ (R))^2κ = 1 / ( 1 + exp ( R ) )2. As a result, the difference of the MLE loss is upper bounded by ℒ⁢(r⋆)−ℒ⁢(r)subscriptℒsuperscript⋆subscriptℒ _D(r )-L_D(r)Lcaligraphic_D ( r⋆ ) - Lcaligraphic_D ( r ) ≤−2⁢κ2⋅(x,a1,a0)∼μ⁢(⋅,⋅,⋅)⁢[|(r⋆⁢(x,a1)−r⋆⁢(x,a0))−(r⁢(x,a1)−r⁢(x,a0))|2]absent⋅2superscript2subscriptsimilar-tosuperscript1superscript0subscript⋅delimited-[]superscriptsuperscript⋆superscript1superscript⋆superscript0superscript1superscript02 ≤-2κ^2·E_(x,a^1,a^0) _ % D(·,·,·) [ | (r (x,a^1)-r (x,a% ^0) )- (r(x,a^1)-r(x,a^0) ) |^2 ]≤ - 2 κ2 ⋅ blackboard_E( x , a1 , a0 ) ∼ μ start_POSTSUBSCRIPT D ( ⋅ , ⋅ , ⋅ ) end_POSTSUBSCRIPT [ | ( r⋆ ( x , a1 ) - r⋆ ( x , a0 ) ) - ( r ( x , a1 ) - r ( x , a0 ) ) |2 ] (B.37) +3N⋅log⁡(ε(ℛ,∥⋅∥∞)δ). + 3N· ( N_ (% R,\|·\|_∞)δ ).+ divide start_ARG 3 end_ARG start_ARG N end_ARG ⋅ log ( divide start_ARG Nitalic_ε ( R , ∥ ⋅ ∥∞ ) end_ARG start_ARG δ end_ARG ) . (B.38) On the other hand, the reward difference term in (B.26), which is evaluated on actions from π and πbasesuperscriptbaseπ^baseπroman_base, can be related to the reward difference evaluated on the data distribution μsubscript _Dμcaligraphic_D via Assumption 5.2, i.e., x∼d0,a1∼π(⋅|x),a0∼πbase(⋅|x)⁢[(r⋆⁢(x,a1)−r⋆⁢(x,a0))−(r⁢(x,a1)−r⁢(x,a0))] _x d_0,a^1 π(·|x),a^0 π^% base(·|x) [ (r (x,a^1)-r (x,a^0)% )- (r(x,a^1)-r(x,a^0) ) ]blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ π ( ⋅ | x ) , a0 ∼ πroman_base ( ⋅ | x ) end_POSTSUBSCRIPT [ ( r⋆ ( x , a1 ) - r⋆ ( x , a0 ) ) - ( r ( x , a1 ) - r ( x , a0 ) ) ] (B.39) ≤Cμ⁢(ℛ;π,πbase)⁢(x,a1,a0)∼μ⁢[|(r⋆⁢(x,a1)−r⋆⁢(x,a0))−(r⁢(x,a1)−r⁢(x,a0))|2].absentsubscriptsubscriptℛsuperscriptbasesubscriptsimilar-tosuperscript1superscript0subscriptdelimited-[]superscriptsuperscript⋆superscript1superscript⋆superscript0superscript1superscript02 ≤ C_ _D(R;π,π^base% ) E_(x,a^1,a^0) _D [ | (% r (x,a^1)-r (x,a^0) )- (r(x,a^1)-r(x,a^0) % ) |^2 ].≤ Citalic_μ start_POSTSUBSCRIPT D end_POSTSUBSCRIPT ( R ; π , πroman_base ) square-root start_ARG blackboard_E( x , a1 , a0 ) ∼ μ start_POSTSUBSCRIPT D end_POSTSUBSCRIPT [ | ( r⋆ ( x , a1 ) - r⋆ ( x , a0 ) ) - ( r ( x , a1 ) - r ( x , a0 ) ) |2 ] end_ARG . (B.40) Finally, combining (B.38), (B.39), and (B.26), denoting Δr:=(x,a1,a0)∼μ⁢[|(r⋆⁢(x,a1)−r⋆⁢(x,a0))−(r⁢(x,a1)−r⁢(x,a0))|2],assignsubscriptΔsubscriptsimilar-tosuperscript1superscript0subscriptdelimited-[]superscriptsuperscript⋆superscript1superscript⋆superscript0superscript1superscript02 _r:= E_(x,a^1,a^0) _D% [ | (r (x,a^1)-r (x,a^0) )- (r(x,% a^1)-r(x,a^0) ) |^2 ],Δitalic_r := square-root start_ARG blackboard_E( x , a1 , a0 ) ∼ μ start_POSTSUBSCRIPT D end_POSTSUBSCRIPT [ | ( r⋆ ( x , a1 ) - r⋆ ( x , a0 ) ) - ( r ( x , a1 ) - r ( x , a0 ) ) |2 ] end_ARG , (B.41) we have that Gapπ⁢(π^)superscriptGap ^π( π)Gapitalic_π ( over start_ARG π end_ARG ) ≤maxr∈ℛ⁡Cμ⁢(ℛ;π,πbase)⋅Δr−2⁢η−1⁢κ2⋅Δr2+3η⁢N⋅log⁡(ε(ℛ,∥⋅∥∞)δ) ≤ _r \C_ _D(% R;π,π^base)· _r-2η^-1κ^2· _r% ^2 \+ 3η N· ( N_ (% R,\|·\|_∞)δ )≤ maxitalic_r ∈ R Citalic_μ start_POSTSUBSCRIPT D end_POSTSUBSCRIPT ( R ; π , πroman_base ) ⋅ Δitalic_r - 2 η- 1 κ2 ⋅ Δitalic_r2 + divide start_ARG 3 end_ARG start_ARG η N end_ARG ⋅ log ( divide start_ARG Nitalic_ε ( R , ∥ ⋅ ∥∞ ) end_ARG start_ARG δ end_ARG ) (B.42) +β⋅x∼d0[KL(π(⋅|x)∥πref(⋅|x))−KL(π^(⋅|x)∥πref(⋅|x))] +β·E_x d_0 [KL (% π(·|x)\|π^ref(·|x) )-KL ( % π(·|x)\|π^ref(·|x) ) ]+ β ⋅ blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT [ KL ( π ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) - KL ( over start_ARG π end_ARG ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] (B.43) ≤(Cμ⁢(ℛ;π,πbase))2⁢η8⁢κ2+3η⁢N⋅log(ε(ℛ,∥⋅∥∞)δ)+β⋅x∼d0[KL(π(⋅|x)∥πref(⋅|x))], ≤ (C_ _D(R;π,π^% base) )^2η8κ^2+ 3η N· (% N_ (R,\|·\|_∞)δ % )+β·E_x d_0 [KL (π(·|x)\|π% ^ref(·|x) ) ],≤ divide start_ARG ( Citalic_μ start_POSTSUBSCRIPT D end_POSTSUBSCRIPT ( R ; π , πroman_base ) )2 η end_ARG start_ARG 8 κ2 end_ARG + divide start_ARG 3 end_ARG start_ARG η N end_ARG ⋅ log ( divide start_ARG Nitalic_ε ( R , ∥ ⋅ ∥∞ ) end_ARG start_ARG δ end_ARG ) + β ⋅ blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT [ KL ( π ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] , (B.44) where in the second inequality we use that fact that a⁢z−b⁢z2≤a2/(4⁢b)superscript2superscript24az-bz^2≤ a^2/(4b)a z - b z2 ≤ a2 / ( 4 b ) for any z∈ℝz ∈ blackboard_R and that KL-divergence is non-negative. Consequently, with the choice of η=2⁢6⋅log(ε(ℛ,∥⋅∥∞)/δ)N,β=1N,κ=1(1+exp⁡(R))2, η=2 6· (N_ % (R,\|·\|_∞)/δ )N, β= 1 % N, κ= 1(1+ (R))^2,η = 2 square-root start_ARG 6 end_ARG ⋅ square-root start_ARG divide start_ARG log ( Nitalic_ε ( R , ∥ ⋅ ∥∞ ) / δ ) end_ARG start_ARG N end_ARG end_ARG , β = divide start_ARG 1 end_ARG start_ARG square-root start_ARG N end_ARG end_ARG , κ = divide start_ARG 1 end_ARG start_ARG ( 1 + exp ( R ) )2 end_ARG , (B.45) we conclude that with probability at least 1−δ11- 1 - δ and ε=(6⋅(1+eR)⋅N)−1superscript⋅61superscript1 =(6·(1+e^R)· N)^-1ε = ( 6 ⋅ ( 1 + eitalic_R ) ⋅ N )- 1, Gapπ⁢(π^)≤6(1+exp(R))2((Cμ(ℛ;π,πbase))2+1)ι+4x∼d0[KL(π(⋅|x)∥πref(⋅|x))]4⁢N, ^π( π)≤ 6 (1+ (% R) )^2 ( (C_ _D(R;π,π^% base) )^2+1 ) +4E_x d_0 [KL% (π(·|x)\|π^ref(·|x) ) ]4 N,Gapitalic_π ( over start_ARG π end_ARG ) ≤ divide start_ARG square-root start_ARG 6 end_ARG ( 1 + exp ( R ) )2 ( ( Citalic_μ start_POSTSUBSCRIPT D end_POSTSUBSCRIPT ( R ; π , πroman_base ) )2 + 1 ) ι + 4 blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT [ KL ( π ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] end_ARG start_ARG 4 square-root start_ARG N end_ARG end_ARG , (B.46) where we denote ι=log(ε(ℛ,∥⋅∥∞)/δ) = (N_ (R,\|·\|_∞% )/δ )ι = square-root start_ARG log ( Nitalic_ε ( R , ∥ ⋅ ∥∞ ) / δ ) end_ARG with ε=(6⋅(1+eR)⋅N)−1superscript⋅61superscript1 =(6·(1+e^R)· N)^-1ε = ( 6 ⋅ ( 1 + eitalic_R ) ⋅ N )- 1. This proves Theorem 5.3. ∎ B.3 Technical Lemmas Lemma B.1 (Uniform concentration). Consider the MLE loss (3.2) and define the approximation error as ε=(6⋅(1+eR)⋅N)−1superscript⋅61superscript1 =(6·(1+e^R)· N)^-1ε = ( 6 ⋅ ( 1 + eitalic_R ) ⋅ N )- 1 where R is the upper bound on the reward functions (Assumption 5.2). Suppose that the reward model class ℛRR has a finite ε ε-covering number ε(ℛ,∥⋅∥∞)<∞N_ (R,\|·\|_∞)<∞Nitalic_ε ( R , ∥ ⋅ ∥∞ ) < ∞. Then for any δ<1/e1δ<1/eδ < 1 / e it holds with probability at least 1−δ11- 1 - δ that ℒ⁢(r⋆)−ℒ⁢(r)subscriptℒsuperscript⋆subscriptℒ _D(r )-L_D(r)Lcaligraphic_D ( r⋆ ) - Lcaligraphic_D ( r ) ≤−2⋅(x,a1,a0)∼μ⁢(⋅,⋅,⋅)[DHellinger2(ℙr⋆(⋅|x,a1,a0)∥ℙr(⋅|x,a1,a0))] ≤-2·E_(x,a^1,a^0) _D(·% ,·,·) [D_Hellinger^2 (P_r (% ·|x,a^1,a^0)\|P_r(·|x,a^1,a^0) ) ]≤ - 2 ⋅ blackboard_E( x , a1 , a0 ) ∼ μ start_POSTSUBSCRIPT D ( ⋅ , ⋅ , ⋅ ) end_POSTSUBSCRIPT [ Droman_Hellinger2 ( blackboard_Pr⋆ ( ⋅ | x , a1 , a0 ) ∥ blackboard_Pr ( ⋅ | x , a1 , a0 ) ) ] (B.47) +3N⋅log⁡(ε(ℛ,∥⋅∥∞)δ). + 3N· ( N_ (% R,\|·\|_∞)δ ).+ divide start_ARG 3 end_ARG start_ARG N end_ARG ⋅ log ( divide start_ARG Nitalic_ε ( R , ∥ ⋅ ∥∞ ) end_ARG start_ARG δ end_ARG ) . (B.48) Proof of Lemma B.1. For notational simplicity, we use ε(ℛ,∥⋅∥∞)C_ (R,\|·\|_∞)Citalic_ε ( R , ∥ ⋅ ∥∞ ) to denote an ε ε-cover of the reward model class ℛRR under the ∥⋅∥∞\|·\|_∞∥ ⋅ ∥∞-norm. It holds that ε(ℛ,∥⋅∥∞)=|ε(ℛ,∥⋅∥∞)|N_ (R,\|·\|_∞)=|C_% (R,\|·\|_∞)|Nitalic_ε ( R , ∥ ⋅ ∥∞ ) = | Citalic_ε ( R , ∥ ⋅ ∥∞ ) |. First we invoke Proposition 5.3 of Liu et al. (2024) to obtain a uniform concentration over the finite set of ε ε-cover ε(ℛ,∥⋅∥∞)C_ (R,\|·\|_∞)Citalic_ε ( R , ∥ ⋅ ∥∞ ). Specifically, with probability at least 1−δ11- 1 - δ, for any r∈ε(ℛ,∥⋅∥∞)r _ (R,\|·\|_∞)r ∈ Citalic_ε ( R , ∥ ⋅ ∥∞ ), ℒ⁢(r⋆)−ℒ⁢(r)subscriptℒsuperscript⋆subscriptℒ _D(r )-L_D(r)Lcaligraphic_D ( r⋆ ) - Lcaligraphic_D ( r ) ≤−2⋅(x,a1,a0)∼μ⁢(⋅,⋅,⋅)[DHellinger2(ℙr⋆(⋅|x,a1,a0)∥ℙr(⋅|x,a1,a0))] ≤-2·E_(x,a^1,a^0) _D(·% ,·,·) [D_Hellinger^2 (P_r (% ·|x,a^1,a^0)\|P_r(·|x,a^1,a^0) ) ]≤ - 2 ⋅ blackboard_E( x , a1 , a0 ) ∼ μ start_POSTSUBSCRIPT D ( ⋅ , ⋅ , ⋅ ) end_POSTSUBSCRIPT [ Droman_Hellinger2 ( blackboard_Pr⋆ ( ⋅ | x , a1 , a0 ) ∥ blackboard_Pr ( ⋅ | x , a1 , a0 ) ) ] (B.49) +2N⋅log⁡(ε(ℛ,∥⋅∥∞)δ). + 2N· ( N_ (% R,\|·\|_∞)δ ).+ divide start_ARG 2 end_ARG start_ARG N end_ARG ⋅ log ( divide start_ARG Nitalic_ε ( R , ∥ ⋅ ∥∞ ) end_ARG start_ARG δ end_ARG ) . (B.50) Now for any reward model r∈ℛr ∈ R, we take a r†∈ε(ℛ,∥⋅∥∞)r _ (R,\|·\|_∞)r† ∈ Citalic_ε ( R , ∥ ⋅ ∥∞ ) satisfying ‖r−r†‖∞≤εsubscriptnormsuperscript†\|r-r \|_∞≤ ∥ r - r† ∥∞ ≤ ε. We have ℒ⁢(r⋆)−ℒ⁢(r)subscriptℒsuperscript⋆subscriptℒ _D(r )-L_D(r)Lcaligraphic_D ( r⋆ ) - Lcaligraphic_D ( r ) =ℒ⁢(r⋆)−ℒ⁢(r†)+ℒ⁢(r†)−ℒ⁢(r)absentsubscriptℒsuperscript⋆subscriptℒsuperscript†subscriptℒsuperscript†subscriptℒ =L_D(r )-L_D(r% )+L_D(r )-L_D(r)= Lcaligraphic_D ( r⋆ ) - Lcaligraphic_D ( r† ) + Lcaligraphic_D ( r† ) - Lcaligraphic_D ( r ) (B.51) ≤−2⋅(x,a1,a0)∼μ⁢(⋅,⋅,⋅)[DHellinger2(ℙr⋆(⋅|x,a1,a0)∥ℙr†(⋅|x,a1,a0))] ≤-2·E_(x,a^1,a^0) _D(·% ,·,·) [D_Hellinger^2 (P_r (% ·|x,a^1,a^0)\|P_r (·|x,a^1,a^0) ) % ]≤ - 2 ⋅ blackboard_E( x , a1 , a0 ) ∼ μ start_POSTSUBSCRIPT D ( ⋅ , ⋅ , ⋅ ) end_POSTSUBSCRIPT [ Droman_Hellinger2 ( blackboard_Pr⋆ ( ⋅ | x , a1 , a0 ) ∥ blackboard_Pr† ( ⋅ | x , a1 , a0 ) ) ] (B.52) +2N⋅log⁡(ε(ℛ,∥⋅∥∞)δ)+ℒ⁢(r†)−ℒ⁢(r) + 2N· ( N_ (% R,\|·\|_∞)δ )+L_D(r^% )-L_D(r)+ divide start_ARG 2 end_ARG start_ARG N end_ARG ⋅ log ( divide start_ARG Nitalic_ε ( R , ∥ ⋅ ∥∞ ) end_ARG start_ARG δ end_ARG ) + Lcaligraphic_D ( r† ) - Lcaligraphic_D ( r ) (B.53) ≤−2⋅(x,a1,a0)∼μ⁢(⋅,⋅,⋅)[DHellinger2(ℙr⋆(⋅|x,a1,a0)∥ℙr(⋅|x,a1,a0))] ≤-2·E_(x,a^1,a^0) _D(·% ,·,·) [D_Hellinger^2 (P_r (% ·|x,a^1,a^0)\|P_r(·|x,a^1,a^0) ) ]≤ - 2 ⋅ blackboard_E( x , a1 , a0 ) ∼ μ start_POSTSUBSCRIPT D ( ⋅ , ⋅ , ⋅ ) end_POSTSUBSCRIPT [ Droman_Hellinger2 ( blackboard_Pr⋆ ( ⋅ | x , a1 , a0 ) ∥ blackboard_Pr ( ⋅ | x , a1 , a0 ) ) ] (B.54) +2N⋅log⁡(ε(ℛ,∥⋅∥∞)δ)+ℒ⁢(r†)−ℒ⁢(r) + 2N· ( N_ (% R,\|·\|_∞)δ )+L_D(r^% )-L_D(r)+ divide start_ARG 2 end_ARG start_ARG N end_ARG ⋅ log ( divide start_ARG Nitalic_ε ( R , ∥ ⋅ ∥∞ ) end_ARG start_ARG δ end_ARG ) + Lcaligraphic_D ( r† ) - Lcaligraphic_D ( r ) (B.55) +4⋅(x,a1,a0)∼μ⁢(⋅,⋅,⋅)[DHellinger2(ℙr†(⋅|x,a1,a0)∥ℙr(⋅|x,a1,a0))], +4·E_(x,a^1,a^0) _D% (·,·,·) [D_Hellinger^2 (P_r^% (·|x,a^1,a^0)\|P_r(·|x,a^1,a^0) ) % ],+ 4 ⋅ blackboard_E( x , a1 , a0 ) ∼ μ start_POSTSUBSCRIPT D ( ⋅ , ⋅ , ⋅ ) end_POSTSUBSCRIPT [ Droman_Hellinger2 ( blackboard_Pr† ( ⋅ | x , a1 , a0 ) ∥ blackboard_Pr ( ⋅ | x , a1 , a0 ) ) ] , (B.56) where in the fir inequality we use (B.50) for r†superscript†r r† and in the second inequality we utilize the triangular inequality for Hellinger distance. Therefore, it remains to upper bound the approximation error induced by r†superscript†r r†. On the one hand, by the definition of ℒsubscriptℒL_DLcaligraphic_D in (3.2), we have that ℒ⁢(r†)−ℒ⁢(r)subscriptℒsuperscript†subscriptℒ _D(r )-L_D(r)Lcaligraphic_D ( r† ) - Lcaligraphic_D ( r ) =1N⁢∑i=1Nyi⋅log⁡(σ⁢(r⁢(xi,ai1)−r⁢(xi,ai0))σ⁢(r†⁢(xi,ai1)−r†⁢(xi,ai0)))absent1superscriptsubscript1⋅subscriptsubscriptsubscriptsuperscript1subscriptsubscriptsuperscript0superscript†subscriptsubscriptsuperscript1superscript†subscriptsubscriptsuperscript0 = 1N _i=1^Ny_i· ( σ (% r(x_i,a^1_i)-r(x_i,a^0_i) )σ (r (x_i,a% ^1_i)-r (x_i,a^0_i) ) )= divide start_ARG 1 end_ARG start_ARG N end_ARG ∑i = 1N yitalic_i ⋅ log ( divide start_ARG σ ( r ( xitalic_i , a1italic_i ) - r ( xitalic_i , a0italic_i ) ) end_ARG start_ARG σ ( r† ( xitalic_i , a1italic_i ) - r† ( xitalic_i , a0italic_i ) ) end_ARG ) (B.57) +1N⁢∑i=1N(1−yi)⋅log⁡(σ⁢(r⁢(xi,ai0)−r⁢(xi,ai1))σ⁢(r†⁢(xi,ai0)−r†⁢(xi,ai1))).1superscriptsubscript1⋅1subscriptsubscriptsubscriptsuperscript0subscriptsubscriptsuperscript1superscript†subscriptsubscriptsuperscript0superscript†subscriptsubscriptsuperscript1 + 1N _i=1^N(1-y_i)· ( % σ (r(x_i,a^0_i)-r(x_i,a^1_i) )σ (r^% (x_i,a^0_i)-r (x_i,a^1_i) ) ).+ divide start_ARG 1 end_ARG start_ARG N end_ARG ∑i = 1N ( 1 - yitalic_i ) ⋅ log ( divide start_ARG σ ( r ( xitalic_i , a0italic_i ) - r ( xitalic_i , a1italic_i ) ) end_ARG start_ARG σ ( r† ( xitalic_i , a0italic_i ) - r† ( xitalic_i , a1italic_i ) ) end_ARG ) . (B.58) Use the inequality that log⁡(x)≤x−11 (x)≤ x-1log ( x ) ≤ x - 1, we can further upper bound ℒ⁢(r†)−ℒ⁢(r)subscriptℒsuperscript†subscriptℒL_D(r )-L_D(r)Lcaligraphic_D ( r† ) - Lcaligraphic_D ( r ) by ℒ⁢(r†)−ℒ⁢(r)subscriptℒsuperscript†subscriptℒ _D(r )-L_D(r)Lcaligraphic_D ( r† ) - Lcaligraphic_D ( r ) ≤1N⁢∑i=1Nyi⋅σ⁢(r⁢(xi,ai1)−r⁢(xi,ai0))−σ⁢(r†⁢(xi,ai1)−r†⁢(xi,ai0))σ⁢(r†⁢(xi,ai1)−r†⁢(xi,ai0))absent1superscriptsubscript1⋅subscriptsubscriptsubscriptsuperscript1subscriptsubscriptsuperscript0superscript†subscriptsubscriptsuperscript1superscript†subscriptsubscriptsuperscript0superscript†subscriptsubscriptsuperscript1superscript†subscriptsubscriptsuperscript0 ≤ 1N _i=1^Ny_i· σ (r(x_i% ,a^1_i)-r(x_i,a^0_i) )-σ (r (x_i,a^1_i% )-r (x_i,a^0_i) )σ (r (x_i,a^1_i% )-r (x_i,a^0_i) )≤ divide start_ARG 1 end_ARG start_ARG N end_ARG ∑i = 1N yitalic_i ⋅ divide start_ARG σ ( r ( xitalic_i , a1italic_i ) - r ( xitalic_i , a0italic_i ) ) - σ ( r† ( xitalic_i , a1italic_i ) - r† ( xitalic_i , a0italic_i ) ) end_ARG start_ARG σ ( r† ( xitalic_i , a1italic_i ) - r† ( xitalic_i , a0italic_i ) ) end_ARG (B.59) +1N⁢∑i=1N(1−yi)⋅σ⁢(r⁢(xi,ai0)−r⁢(xi,ai1))−σ⁢(r†⁢(xi,ai0)−r†⁢(xi,ai1))σ⁢(r†⁢(xi,ai0)−r†⁢(xi,ai1)).1superscriptsubscript1⋅1subscriptsubscriptsubscriptsuperscript0subscriptsubscriptsuperscript1superscript†subscriptsubscriptsuperscript0superscript†subscriptsubscriptsuperscript1superscript†subscriptsubscriptsuperscript0superscript†subscriptsubscriptsuperscript1 + 1N _i=1^N(1-y_i)· σ% (r(x_i,a^0_i)-r(x_i,a^1_i) )-σ (r (x% _i,a^0_i)-r (x_i,a^1_i) )σ (r (% x_i,a^0_i)-r (x_i,a^1_i) ).+ divide start_ARG 1 end_ARG start_ARG N end_ARG ∑i = 1N ( 1 - yitalic_i ) ⋅ divide start_ARG σ ( r ( xitalic_i , a0italic_i ) - r ( xitalic_i , a1italic_i ) ) - σ ( r† ( xitalic_i , a0italic_i ) - r† ( xitalic_i , a1italic_i ) ) end_ARG start_ARG σ ( r† ( xitalic_i , a0italic_i ) - r† ( xitalic_i , a1italic_i ) ) end_ARG . (B.60) Now since ‖r†−r‖∞≤εsubscriptnormsuperscript†\|r -r\|_∞≤ ∥ r† - r ∥∞ ≤ ε and r†∈[0,R]superscript†0r ∈[0,R]r† ∈ [ 0 , R ], invoking Lemma B.2, we can derive that ℒ⁢(r†)−ℒ⁢(r)subscriptℒsuperscript†subscriptℒ _D(r )-L_D(r)Lcaligraphic_D ( r† ) - Lcaligraphic_D ( r ) ≤1N⁢∑i=1N|(r⁢(xi,ai1)−r⁢(xi,ai0))−(r†⁢(xi,ai1)−r†⁢(xi,ai0))|(1+eR)−1absent1superscriptsubscript1subscriptsubscriptsuperscript1subscriptsubscriptsuperscript0superscript†subscriptsubscriptsuperscript1superscript†subscriptsubscriptsuperscript0superscript1superscript1 ≤ 1N _i=1^N | (r(x_i,a^1_i% )-r(x_i,a^0_i) )- (r (x_i,a^1_i)-r (x% _i,a^0_i) ) |(1+e^R)^-1≤ divide start_ARG 1 end_ARG start_ARG N end_ARG ∑i = 1N divide start_ARG | ( r ( xitalic_i , a1italic_i ) - r ( xitalic_i , a0italic_i ) ) - ( r† ( xitalic_i , a1italic_i ) - r† ( xitalic_i , a0italic_i ) ) | end_ARG start_ARG ( 1 + eitalic_R )- 1 end_ARG (B.61) +1N⁢∑i=1N|(r⁢(xi,ai0)−r⁢(xi,ai1))−(r†⁢(xi,ai0)−r†⁢(xi,ai1))|(1+eR)−11superscriptsubscript1subscriptsubscriptsuperscript0subscriptsubscriptsuperscript1superscript†subscriptsubscriptsuperscript0superscript†subscriptsubscriptsuperscript1superscript1superscript1 + 1N _i=1^N | (r(x_i,a^0% _i)-r(x_i,a^1_i) )- (r (x_i,a^0_i)-r % (x_i,a^1_i) ) |(1+e^R)^-1+ divide start_ARG 1 end_ARG start_ARG N end_ARG ∑i = 1N divide start_ARG | ( r ( xitalic_i , a0italic_i ) - r ( xitalic_i , a1italic_i ) ) - ( r† ( xitalic_i , a0italic_i ) - r† ( xitalic_i , a1italic_i ) ) | end_ARG start_ARG ( 1 + eitalic_R )- 1 end_ARG (B.62) ≤4⋅‖r†−r‖∞⋅(1+eR)≤4⁢ε⋅(1+eR).absent⋅4subscriptnormsuperscript†1superscript⋅41superscript ≤ 4·\|r -r\|_∞·(1+e^R)≤ 4% ·(1+e^R).≤ 4 ⋅ ∥ r† - r ∥∞ ⋅ ( 1 + eitalic_R ) ≤ 4 ε ⋅ ( 1 + eitalic_R ) . (B.63) On the other hand, we upper bound the hellinger distance between ℙrsubscriptℙP_rblackboard_Pr and ℙr†subscriptℙsuperscript†P_r blackboard_Pr†, for any (x,a1,a0)∈×superscript1superscript0(x,a^1,a^0) ×A×A( x , a1 , a0 ) ∈ X × A × A, DHellinger2(ℙr†(⋅|x,a1,a0)∥ℙr(⋅|x,a1,a0)) D_Hellinger^2 (P_r (·|% x,a^1,a^0)\|P_r(·|x,a^1,a^0) )Droman_Hellinger2 ( blackboard_Pr† ( ⋅ | x , a1 , a0 ) ∥ blackboard_Pr ( ⋅ | x , a1 , a0 ) ) (B.64) ≤DTV(ℙr†(⋅|x,a1,a0)∥ℙr(⋅|x,a1,a0)) ≤ D_TV (P_r (·|x% ,a^1,a^0)\|P_r(·|x,a^1,a^0) )≤ Droman_TV ( blackboard_Pr† ( ⋅ | x , a1 , a0 ) ∥ blackboard_Pr ( ⋅ | x , a1 , a0 ) ) (B.65) =|σ⁢(r†⁢(x,a1)−r†⁢(x,a0))−σ⁢(r⁢(x,a1)−r⁢(x,a0))|absentsuperscript†superscript1superscript†superscript0superscript1superscript0 = |σ (r (x,a^1)-r (x,a^% 0) )-σ (r(x,a^1)-r(x,a^0) ) |= | σ ( r† ( x , a1 ) - r† ( x , a0 ) ) - σ ( r ( x , a1 ) - r ( x , a0 ) ) | (B.66) ≤|(r†⁢(x,a1)−r†⁢(x,a0))−(r⁢(x,a1)−r⁢(x,a0))|absentsuperscript†superscript1superscript†superscript0superscript1superscript0 ≤ | (r (x,a^1)-r (x,a^0)% )- (r(x,a^1)-r(x,a^0) ) |≤ | ( r† ( x , a1 ) - r† ( x , a0 ) ) - ( r ( x , a1 ) - r ( x , a0 ) ) | (B.67) ≤2⋅‖r†−r‖∞≤2⁢ε,absent⋅2subscriptnormsuperscript†2 ≤ 2·\|r -r\|_∞≤ 2 ,≤ 2 ⋅ ∥ r† - r ∥∞ ≤ 2 ε , (B.68) where the first inequality uses the fact that DHellinger2≤DTVsuperscriptsubscriptHellinger2subscriptTVD_Hellinger^2≤ D_TVDroman_Hellinger2 ≤ Droman_TV, the equality uses the same argument as (B.35), and the second inequality applies Lemma B.2. Finally, combining (B.56), (B.63), and (B.68), we conclude that ℒ⁢(r⋆)−ℒ⁢(r)subscriptℒsuperscript⋆subscriptℒ _D(r )-L_D(r)Lcaligraphic_D ( r⋆ ) - Lcaligraphic_D ( r ) ≤−2⋅(x,a1,a0)∼μ⁢(⋅,⋅,⋅)[DHellinger2(ℙr⋆(⋅|x,a1,a0)∥ℙr(⋅|x,a1,a0))] ≤-2·E_(x,a^1,a^0) _D(·% ,·,·) [D_Hellinger^2 (P_r (% ·|x,a^1,a^0)\|P_r(·|x,a^1,a^0) ) ]≤ - 2 ⋅ blackboard_E( x , a1 , a0 ) ∼ μ start_POSTSUBSCRIPT D ( ⋅ , ⋅ , ⋅ ) end_POSTSUBSCRIPT [ Droman_Hellinger2 ( blackboard_Pr⋆ ( ⋅ | x , a1 , a0 ) ∥ blackboard_Pr ( ⋅ | x , a1 , a0 ) ) ] (B.69) +2N⋅log⁡(ε(ℛ,∥⋅∥∞)δ)+6⁢ε⋅(1+eR). + 2N· ( N_ (% R,\|·\|_∞)δ )+6 ·(1+e^R).+ divide start_ARG 2 end_ARG start_ARG N end_ARG ⋅ log ( divide start_ARG Nitalic_ε ( R , ∥ ⋅ ∥∞ ) end_ARG start_ARG δ end_ARG ) + 6 ε ⋅ ( 1 + eitalic_R ) . (B.70) By taking the approximation error ε=(6⋅(1+eR)⋅N)−1superscript⋅61superscript1 =(6·(1+e^R)· N)^-1ε = ( 6 ⋅ ( 1 + eitalic_R ) ⋅ N )- 1, we conclude that for δ<e−1superscript1δ<e^-1δ < e- 1, with probability at least 1−δ11- 1 - δ, for any r∈ℛr ∈ R, it holds that ℒ⁢(r⋆)−ℒ⁢(r)subscriptℒsuperscript⋆subscriptℒ _D(r )-L_D(r)Lcaligraphic_D ( r⋆ ) - Lcaligraphic_D ( r ) ≤−2⋅(x,a1,a0)∼μ⁢(⋅,⋅,⋅)[DHellinger2(ℙr⋆(⋅|x,a1,a0)∥ℙr(⋅|x,a1,a0))] ≤-2·E_(x,a^1,a^0) _D(·% ,·,·) [D_Hellinger^2 (P_r (% ·|x,a^1,a^0)\|P_r(·|x,a^1,a^0) ) ]≤ - 2 ⋅ blackboard_E( x , a1 , a0 ) ∼ μ start_POSTSUBSCRIPT D ( ⋅ , ⋅ , ⋅ ) end_POSTSUBSCRIPT [ Droman_Hellinger2 ( blackboard_Pr⋆ ( ⋅ | x , a1 , a0 ) ∥ blackboard_Pr ( ⋅ | x , a1 , a0 ) ) ] (B.71) +3N⋅log⁡(ε(ℛ,∥⋅∥∞)δ). + 3N· ( N_% (R,\|·\|_∞)δ ).+ divide start_ARG 3 end_ARG start_ARG N end_ARG ⋅ log ( divide start_ARG Nitalic_ε ( R , ∥ ⋅ ∥∞ ) end_ARG start_ARG δ end_ARG ) . (B.72) This completes the proof of Lemma B.1. ∎ Lemma B.2 (Sigmoid function). For any real numbers z1,z2∈[−R,R]subscript1subscript2z_1,z_2∈[-R,R]z1 , z2 ∈ [ - R , R ], it holds that κ⋅|z1−z2|≤|σ⁢(z1)−σ⁢(z2)|≤|z1−z2|,⋅subscript1subscript2subscript1subscript2subscript1subscript2 κ·|z_1-z_2|≤ |σ(z_1)-σ(z_2)% |≤|z_1-z_2|,κ ⋅ | z1 - z2 | ≤ | σ ( z1 ) - σ ( z2 ) | ≤ | z1 - z2 | , (B.73) where the constant κ=1/(1+exp⁡(R))21superscript12κ=1/(1+ (R))^2κ = 1 / ( 1 + exp ( R ) )2. Proof of Lemma B.2. Since the sigmoid function σ⁢(⋅)⋅σ(·)σ ( ⋅ ) is differentiable, we know that for any z1,z2∈[−R,R]subscript1subscript2z_1,z_2∈[-R,R]z1 , z2 ∈ [ - R , R ], there exists some ξ⁢(z1,z2)∈[−R,R]subscript1subscript2ξ(z_1,z_2)∈[-R,R]ξ ( z1 , z2 ) ∈ [ - R , R ] such that σ⁢(z1)−σ⁢(z2)=σ′⁢(ξ⁢(z1,z2))⋅(z1−z2).subscript1subscript2⋅superscript′subscript1subscript2subscript1subscript2 σ(z_1)-σ(z_2)=σ (ξ(z_1,z_2% ) )·(z_1-z_2).σ ( z1 ) - σ ( z2 ) = σ′ ( ξ ( z1 , z2 ) ) ⋅ ( z1 - z2 ) . (B.74) Notice that σ′⁢(z)=σ⁢(z)⋅(1−σ⁢(z))superscript′⋅1σ (z)=σ(z)·(1-σ(z))σ′ ( z ) = σ ( z ) ⋅ ( 1 - σ ( z ) ), we can obtain that 1≥σ′⁢(ξ⁢(z1,z2))1superscript′subscript1subscript2 1≥σ (ξ(z_1,z_2) )1 ≥ σ′ ( ξ ( z1 , z2 ) ) =σ⁢(ξ⁢(z1,z2))⋅(1−σ⁢(ξ⁢(z1,z2)))absent⋅subscript1subscript21subscript1subscript2 =σ (ξ(z_1,z_2) )· (1-σ (% ξ(z_1,z_2) ) )= σ ( ξ ( z1 , z2 ) ) ⋅ ( 1 - σ ( ξ ( z1 , z2 ) ) ) (B.75) =11+exp⁡(ξ⁢(z1,z2))⋅(1−11+exp⁡(ξ⁢(z1,z2)))absent⋅11subscript1subscript2111subscript1subscript2 = 11+ (ξ(z_1,z_2))· (1- 11+ (% ξ(z_1,z_2)) )= divide start_ARG 1 end_ARG start_ARG 1 + exp ( ξ ( z1 , z2 ) ) end_ARG ⋅ ( 1 - divide start_ARG 1 end_ARG start_ARG 1 + exp ( ξ ( z1 , z2 ) ) end_ARG ) (B.76) ≥11+exp⁡(R)⋅(1−11+exp⁡(−R))absent⋅11111 ≥ 11+ (R)· (1- 11+ (-R) )≥ divide start_ARG 1 end_ARG start_ARG 1 + exp ( R ) end_ARG ⋅ ( 1 - divide start_ARG 1 end_ARG start_ARG 1 + exp ( - R ) end_ARG ) (B.77) =1(1+exp⁡(R))2.absent1superscript12 = 1(1+ (R))^2.= divide start_ARG 1 end_ARG start_ARG ( 1 + exp ( R ) )2 end_ARG . (B.78) This completes the proof of Lemma B.2. ∎ Appendix C Proofs for Equivalence between Maximin and Minimax Objectives C.1 Proof of Theorem 5.6 Proof of Theorem 5.6. Consider denoting an auxiliary policy π^ πover start_ARG π end_ARG as π^∈argmaxπ∈Πminr∈ℛ⁡ϕ⁢(π,r).^subscriptargmaxΠsubscriptℛitalic-ϕ π∈ argmax_π∈ \, _r∈% Rφ(π,r).over start_ARG π end_ARG ∈ argmaxitalic_π ∈ Π minitalic_r ∈ R ϕ ( π , r ) . (C.1) By the definition of r^ rover start_ARG r end_ARG and π^ πover start_ARG π end_ARG, the duality gap of (r^,π^)^^( r, π)( over start_ARG r end_ARG , over start_ARG π end_ARG ), defined as Dual⁢(r^,π^):=maxπ∈Π⁡ϕ⁢(π,r^)−minr∈ℛ⁡ϕ⁢(π^,r)assignDual^^subscriptΠitalic-ϕ^subscriptℛitalic-ϕ ( r, π):= _π∈ φ(% π, r)- _r φ( π,r)Dual ( over start_ARG r end_ARG , over start_ARG π end_ARG ) := maxitalic_π ∈ Π ϕ ( π , over start_ARG r end_ARG ) - minitalic_r ∈ R ϕ ( over start_ARG π end_ARG , r ) (C.2) is zero. This is because the following deduction, Dual⁢(r^,π^)Dual^ ( r, π)Dual ( over start_ARG r end_ARG , over start_ARG π end_ARG ) =(maxπ∈Π⁡ϕ⁢(π,r^)−minr∈ℛ⁡maxπ∈Π⁡ϕ⁢(π,r))absentsubscriptΠitalic-ϕ^subscriptℛsubscriptΠitalic-ϕ = ( _π∈ φ(π, r)- _r % \, _π∈ φ(π,r) )= ( maxitalic_π ∈ Π ϕ ( π , over start_ARG r end_ARG ) - minitalic_r ∈ R maxitalic_π ∈ Π ϕ ( π , r ) ) (C.3) +(maxπ∈Π⁡minr∈ℛ⁡ϕ⁢(π,r)−minr∈ℛ⁡ϕ⁢(π^,r))subscriptΠsubscriptℛitalic-ϕsubscriptℛitalic-ϕ + ( _π∈ \, _r φ(π,r)-% _r φ( π,r) )+ ( maxitalic_π ∈ Π minitalic_r ∈ R ϕ ( π , r ) - minitalic_r ∈ R ϕ ( over start_ARG π end_ARG , r ) ) (C.4) =0,absent0 =0,= 0 , (C.5) where in the first equality we apply Lemma C.1 that the minimax objective and the maximin objective are equivalent, and the last equality applies the definition of r^ rover start_ARG r end_ARG and π^ πover start_ARG π end_ARG respectively. Note that we can rewrite the duality gap as following Dual⁢(r^,π^)=(maxπ∈Π⁡ϕ⁢(π,r^)−ϕ⁢(π^,r^))+(ϕ⁢(π^,r^)−minr∈ℛ⁡ϕ⁢(π^,r)).Dual^^subscriptΠitalic-ϕ^italic-ϕ^^italic-ϕ^^subscriptℛitalic-ϕ ( r, π)= ( _π∈ % φ(π, r)-φ( π, r) )+ (φ(% π, r)- _r φ( π,r) ).Dual ( over start_ARG r end_ARG , over start_ARG π end_ARG ) = ( maxitalic_π ∈ Π ϕ ( π , over start_ARG r end_ARG ) - ϕ ( over start_ARG π end_ARG , over start_ARG r end_ARG ) ) + ( ϕ ( over start_ARG π end_ARG , over start_ARG r end_ARG ) - minitalic_r ∈ R ϕ ( over start_ARG π end_ARG , r ) ) . (C.6) Combining (C.5) and (C.6), we can conclude that maxπ∈Π⁡ϕ⁢(π,r^)=ϕ⁢(π^,r^)⇒π^∈argmaxπ∈Πϕ⁢(r^,π).formulae-sequencesubscriptΠitalic-ϕ^italic-ϕ^^⇒^subscriptargmaxΠitalic-ϕ _π∈ φ(π, r)=φ( π, % r) π∈ argmax_π∈ % φ( r,π).maxitalic_π ∈ Π ϕ ( π , over start_ARG r end_ARG ) = ϕ ( over start_ARG π end_ARG , over start_ARG r end_ARG ) ⇒ over start_ARG π end_ARG ∈ argmaxitalic_π ∈ Π ϕ ( over start_ARG r end_ARG , π ) . (C.7) Now comparing what πr^subscript _ rπover start_ARG r end_ARG and π^ πover start_ARG π end_ARG satisfy in (5.7) and (C.7) respectively, invoking Lemma C.3 that the maximizer of ϕ⁢(⋅,r)italic-ϕ⋅φ(·,r)ϕ ( ⋅ , r ) given any r∈ℛr ∈ R is unique on the support of d0subscript0d_0d0, we can conclude that πr^(⋅|x)=π^(⋅|x),∀x∈Supp(d0). _ r(·|x)= π(·|x), ∀ x% (d_0).πover start_ARG r end_ARG ( ⋅ | x ) = over start_ARG π end_ARG ( ⋅ | x ) , ∀ x ∈ Supp ( d0 ) . (C.8) Therefore, by (C.1) and (C.8), and the fact that ϕ⁢(π,r)italic-ϕφ(π,r)ϕ ( π , r ) depends on π only through its value on the support of d0subscript0d_0d0, we can conclude that πr^∈argmaxπ∈Πminr∈ℛ⁡ϕ⁢(π,r).subscript^subscriptargmaxΠsubscriptℛitalic-ϕ _ r∈ argmax_π∈ \, _r% φ(π,r).πover start_ARG r end_ARG ∈ argmaxitalic_π ∈ Π minitalic_r ∈ R ϕ ( π , r ) . (C.9) This finishes the proof of Theorem 5.6. ∎ C.2 Auxiliary Lemmas Lemma C.1 (Equivalence of maximin and minimax objectives). For the policy class Π Π defined in (2.4) and the reward model class ℛRR satisfying Assumption 5.5, it holds that the maximin objective is equivalent to the minimax objective, i.e., maxπ∈Π⁡minr∈ℛ⁡ϕ⁢(π,r)=minr∈ℛ⁡maxπ∈Π⁡ϕ⁢(π,r).subscriptΠsubscriptℛitalic-ϕsubscriptℛsubscriptΠitalic-ϕ _π∈ \, _r φ(π,r)= _r∈% R\, _π∈ φ(π,r).maxitalic_π ∈ Π minitalic_r ∈ R ϕ ( π , r ) = minitalic_r ∈ R maxitalic_π ∈ Π ϕ ( π , r ) . (C.10) Proof of Lemma C.1. The foundation of this result is a minimax theorem given by Fan (1953) (Lemma C.2). In our setting, the policy class Π Π is a nonempty set, and the reward model class ℛRR is a nonempty compact Hausdorff space. Furthermore, by our choice of the policy class Π Π in (2.4), Π Π is a convex set. Meanwhile, the function ϕitalic-ϕφϕ is a concave function of π∈Ππ∈ π ∈ Π since the dependence on π is linear terms plus a negative KL term (concave). Finally, by our assumption, the function ϕitalic-ϕφϕ is convex-like on the reward model class ℛRR and is also continuous on ℛRR. As a result, all the conditions of Lemma C.2 are satisfied and the minimax theorem holds in our problem setup, finishing the proof of Lemma C.1. ∎ Lemma C.2 (Minimax theorem (Fan, 1953)). Let XX be a nonempty set (not necessarily topologized) and YY be a nonempty compact topological space. Let f:×↦ℝ:maps-toℝf:X×Y : X × Y ↦ blackboard_R be lower semicontinuous on YY. Suppose that f is concave-like on XX and convex-like on YY, i.e., for any x1,x2∈subscript1subscript2x_1,x_2 1 , x2 ∈ X, α∈[0,1]01α∈[0,1]α ∈ [ 0 , 1 ], there exists x3∈subscript3x_3 3 ∈ X such that f⁢(x3,⋅)≥α⋅f⁢(x1,⋅)+(1−α)⋅f⁢(x2,⋅)⁢on ,subscript3⋅subscript1⋅1subscript2⋅on , f(x_3,·)≥α· f(x_1,·)+(1-α)· f(x% _2,·)\,\,on $ Y$,f ( x3 , ⋅ ) ≥ α ⋅ f ( x1 , ⋅ ) + ( 1 - α ) ⋅ f ( x2 , ⋅ ) on Y , (C.11) and for any y1,y2∈subscript1subscript2y_1,y_2 1 , y2 ∈ Y, β∈[0,1]01β∈[0,1]β ∈ [ 0 , 1 ], there exists y3∈subscript3y_3 3 ∈ Y such that f⁢(⋅,y3)≤β⋅f⁢(⋅,y1)+(1−β)⋅f⁢(⋅,y2)⁢on .⋅subscript3⋅subscript1⋅1⋅subscript2on . f(·,y_3)≤β· f(·,y_1)+(1-β)· f(% ·,y_2)\,\,on $ Y$.f ( ⋅ , y3 ) ≤ β ⋅ f ( ⋅ , y1 ) + ( 1 - β ) ⋅ f ( ⋅ , y2 ) on Y . (C.12) Then the following equation holds, maxx∈⁡miny∈⁡f⁢(x,y)=miny∈⁡maxx∈⁡f⁢(x,y).subscriptsubscriptsubscriptsubscript _x \, _y f(x,y)= _y∈% Y\, _x f(x,y).maxitalic_x ∈ X minitalic_y ∈ Y f ( x , y ) = minitalic_y ∈ Y maxitalic_x ∈ X f ( x , y ) . (C.13) Lemma C.3 (Unique maximizer of ϕitalic-ϕφϕ). Consider the function ϕitalic-ϕφϕ defined as ϕ⁢(π,r)italic-ϕ φ(π,r)ϕ ( π , r ) :=η⋅x∼d0,a1∼π(⋅|x),a0∼πbase(⋅|x)[r(x,a1)−r(x,a0)−β⋅DKL(π(⋅|x)∥πref(⋅|x))] :=η·E_x d_0,a^1 π(·|x),a^0% π^base(·|x) [r(x,a^1)-r(x,a^0)-β· D_% KL (π(·|x)\|π^ref(·|x) ) ]:= η ⋅ blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ π ( ⋅ | x ) , a0 ∼ πroman_base ( ⋅ | x ) end_POSTSUBSCRIPT [ r ( x , a1 ) - r ( x , a0 ) - β ⋅ Droman_KL ( π ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] (C.14) +ℒ⁢(r).subscriptℒ +L_D(r).+ Lcaligraphic_D ( r ) . (C.15) Then given any r∈ℛr ∈ R, the maximimzer of ϕ⁢(⋅,r)italic-ϕ⋅φ(·,r)ϕ ( ⋅ , r ) is unique on the support of d0subscript0d_0d0. Proof of Lemma C.3. Given any r∈ℛr ∈ R, consider that maxπ∈Π⁡ϕ⁢(π,r)subscriptΠitalic-ϕ _π∈ φ(π,r)maxitalic_π ∈ Π ϕ ( π , r ) (C.16) =η⋅maxπ∈Πx∼d0,a1∼π(⋅|x)[r(x,a1)−β⋅DKL(π(⋅|x)∥πref(⋅|x))] =η· _π∈ \E_x d_0,a^% 1 π(·|x) [r(x,a^1)-β· D_KL (π(% ·|x)\|π^ref(·|x) ) ] \= η ⋅ maxitalic_π ∈ Π blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 , a1 ∼ π ( ⋅ | x ) end_POSTSUBSCRIPT [ r ( x , a1 ) - β ⋅ Droman_KL ( π ( ⋅ | x ) ∥ πroman_ref ( ⋅ | x ) ) ] (C.17) =η⋅maxπ∈ΠCr−β⋅x∼d0[DKL(π(⋅|x)∥πref(⋅|x)⋅exp(β−1⋅r(x,⋅))∫a′∈dπref⁢(a′|x)⋅exp⁡(β−1⋅r⁢(x,a′)))], =η· _π∈ \C_r-β·E% _x d_0 [D_KL (π(·|x) \| π^% ref(·|x)· (β^-1· r(x,·)) _a % dπ^ref(a |x)· (β^-1% · r(x,a )) ) ] \,= η ⋅ maxitalic_π ∈ Π Citalic_r - β ⋅ blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT [ Droman_KL ( π ( ⋅ | x ) ∥ divide start_ARG πroman_ref ( ⋅ | x ) ⋅ exp ( β- 1 ⋅ r ( x , ⋅ ) ) end_ARG start_ARG ∫a′ ∈ A d πroman_ref ( a′ | x ) ⋅ exp ( β- 1 ⋅ r ( x , a′ ) ) end_ARG ) ] , (C.18) where Cr=x∼d0⁢[β⋅log⁡(∫a∈dπref⁢(a|x)⋅exp⁡(β−1⋅r⁢(x,a)))]subscriptsubscriptsimilar-tosubscript0delimited-[]⋅subscript⋅differential-dsuperscriptrefconditional⋅superscript1C_r=E_x d_0 [β· ( _a % dπ^ref(a|x)· (β^-1· r(x,a) )% ) ]Citalic_r = blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT [ β ⋅ log ( ∫a ∈ A d πroman_ref ( a | x ) ⋅ exp ( β- 1 ⋅ r ( x , a ) ) ) ] is a constant independent of π. Therefore, the maximizer of ϕ⁢(⋅,r)italic-ϕ⋅φ(·,r)ϕ ( ⋅ , r ) on the support of d0subscript0d_0d0 must equal to πr(⋅|x)=πref(⋅|x)⋅exp(β−1⋅r(x,⋅))∫a′∈dπref⁢(a′|x)⋅exp⁡(β−1⋅r⁢(x,a′)), _r(·|x)= π^ref(·|x)· (β% ^-1· r(x,·)) _a dπ^% ref(a |x)· (β^-1· r(x,a )),πitalic_r ( ⋅ | x ) = divide start_ARG πroman_ref ( ⋅ | x ) ⋅ exp ( β- 1 ⋅ r ( x , ⋅ ) ) end_ARG start_ARG ∫a′ ∈ A d πroman_ref ( a′ | x ) ⋅ exp ( β- 1 ⋅ r ( x , a′ ) ) end_ARG , (C.19) which completes the proof of Lemma C.3. ∎ Appendix D Proofs for Generalization to New Prompt Distributions Proof of Corollary 5.8. Consider by Holder’s inequality, we can bound the new target as x∼d1,a∼π⋆(⋅|x)⁢[r⋆⁢(x,a)]−x∼d1,a∼πr^(⋅|x)⁢[r⋆⁢(x,a)] _x d_1,a π (·|x)[r (x,a)% ]-E_x d_1,a _ r(·|x)[r (x,a)]blackboard_Ex ∼ d start_POSTSUBSCRIPT 1 , a ∼ π⋆ ( ⋅ | x ) end_POSTSUBSCRIPT [ r⋆ ( x , a ) ] - blackboard_Ex ∼ d start_POSTSUBSCRIPT 1 , a ∼ πover start_ARG r end_ARG ( ⋅ | x ) end_POSTSUBSCRIPT [ r⋆ ( x , a ) ] (D.1) =x∼d1⁢[a∼π⋆(⋅|x)⁢[r⋆⁢(x,a)]−a∼πr^(⋅|x)⁢[r⋆⁢(x,a)]] =E_x d_1 [E_a π % (·|x)[r (x,a)]-E_a _ r(·|x)[r^% (x,a)] ]= blackboard_Ex ∼ d start_POSTSUBSCRIPT 1 end_POSTSUBSCRIPT [ blackboard_Ea ∼ π⋆ ( ⋅ | x ) [ r⋆ ( x , a ) ] - blackboard_Ea ∼ π start_POSTSUBSCRIPT over start_ARG r end_ARG ( ⋅ | x ) end_POSTSUBSCRIPT [ r⋆ ( x , a ) ] ] (D.2) =x∼d0⁢[d1⁢(x)d0⁢(x)⋅(a∼π⋆(⋅|x)⁢[r⋆⁢(x,a)]−a∼πr^(⋅|x)⁢[r⋆⁢(x,a)])] =E_x d_0 [ d_1(x)d_0(x)% · (E_a π (·|x)[r (x,a)]-E_% a _ r(·|x)[r (x,a)] ) ]= blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT [ divide start_ARG d1 ( x ) end_ARG start_ARG d0 ( x ) end_ARG ⋅ ( blackboard_Ea ∼ π⋆ ( ⋅ | x ) [ r⋆ ( x , a ) ] - blackboard_Ea ∼ π start_POSTSUBSCRIPT over start_ARG r end_ARG ( ⋅ | x ) end_POSTSUBSCRIPT [ r⋆ ( x , a ) ] ) ] (D.3) ≤C∞⁢(d0,d1)⋅x∼d0⁢[|a∼π⋆(⋅|x)⁢[r⋆⁢(x,a)]−a∼πr^(⋅|x)⁢[r⋆⁢(x,a)]|], ≤ C_∞(d_0,d_1)·E_x d_0% [ |E_a π (·|x)[r (x,a)]-E_% a _ r(·|x)[r (x,a)] | ],≤ C∞ ( d0 , d1 ) ⋅ blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT [ | blackboard_Ea ∼ π⋆ ( ⋅ | x ) [ r⋆ ( x , a ) ] - blackboard_Ea ∼ π start_POSTSUBSCRIPT over start_ARG r end_ARG ( ⋅ | x ) end_POSTSUBSCRIPT [ r⋆ ( x , a ) ] | ] , (D.4) where the last inequality follows from Holder’s inequality and the definition of the density ratio C∞⁢(d0,d1)subscriptsubscript0subscript1C_∞(d_0,d_1)C∞ ( d0 , d1 ) in Corollary 5.8. Now since π⋆superscript⋆π π⋆ is the optimal policy in Π Π in the sense that π⋆=argmaxπ∈Πa∼π(⋅|x)⁢[r⋆⁢(x,a)]π = argmax_π∈ E_a π(·|x)% [r (x,a)]π⋆ = argmaxitalic_π ∈ Π blackboard_Ea ∼ π ( ⋅ | x ) [ r⋆ ( x , a ) ] for any x∈x ∈ X, we have that x∼d0⁢[|a∼π⋆(⋅|x)⁢[r⋆⁢(x,a)]−a∼πr^(⋅|x)⁢[r⋆⁢(x,a)]|] _x d_0 [ |E_a π (% ·|x)[r (x,a)]-E_a _ r(·|x)[r^% (x,a)] | ]blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 end_POSTSUBSCRIPT [ | blackboard_Ea ∼ π⋆ ( ⋅ | x ) [ r⋆ ( x , a ) ] - blackboard_Ea ∼ π start_POSTSUBSCRIPT over start_ARG r end_ARG ( ⋅ | x ) end_POSTSUBSCRIPT [ r⋆ ( x , a ) ] | ] (D.5) =x∼d0,a∼π⋆(⋅|x)⁢[r⋆⁢(x,a)]−x∼d0,a∼πr^(⋅|x)⁢[r⋆⁢(x,a)] =E_x d_0,a π (·|x)[r^% (x,a)]-E_x d_0,a _ r(·|x)[r % (x,a)]= blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 , a ∼ π⋆ ( ⋅ | x ) end_POSTSUBSCRIPT [ r⋆ ( x , a ) ] - blackboard_Ex ∼ d start_POSTSUBSCRIPT 0 , a ∼ πover start_ARG r end_ARG ( ⋅ | x ) end_POSTSUBSCRIPT [ r⋆ ( x , a ) ] (D.6) =Gapπ⋆⁢(πr^),absentsuperscriptGapsuperscript⋆subscript =Gap^π ( _ r),= Gapitalic_π start_POSTSUPERSCRIPT ⋆ end_POSTSUPERSCRIPT ( πover start_ARG r end_ARG ) , (D.7) Therefore, by combining (D.4) and (D.7), invoking Corollary 5.7, we have that x∼d1,a∼π⋆(⋅|x)⁢[r⋆⁢(x,a)]−x∼d1,a∼πr^(⋅|x)⁢[r⋆⁢(x,a)]≤~⁢(C∞⁢(d0,d1)N), _x d_1,a π (·|x)[r (x,a)% ]-E_x d_1,a _ r(·|x)[r (x,a)]≤% O ( C_∞(d_0,d_1) N ),blackboard_Ex ∼ d start_POSTSUBSCRIPT 1 , a ∼ π⋆ ( ⋅ | x ) end_POSTSUBSCRIPT [ r⋆ ( x , a ) ] - blackboard_Ex ∼ d start_POSTSUBSCRIPT 1 , a ∼ πover start_ARG r end_ARG ( ⋅ | x ) end_POSTSUBSCRIPT [ r⋆ ( x , a ) ] ≤ over~ start_ARG O end_ARG ( divide start_ARG C∞ ( d0 , d1 ) end_ARG start_ARG square-root start_ARG N end_ARG end_ARG ) , (D.8) with probability at least 1−δ11- 1 - δ. This proves Corollary 5.8. ∎ Appendix E Additional Details on Experiments E.1 Training Details We train the gemma series models with 8 NVIDIA A6000 GPUs and the beta series models with 8 NVIDIA A100 GPUs, where they are all GPT-like models with around 7 billion parameters. It takes around three hours to train a beta series model and five hours to train a gemma one. Our codebase is adapted from the Alignment Handbook (Tunstall et al., 2023a). By comparing the validation loss on the test split (not used for later evaluation), we select the hyperparameter η of both RPO (beta) and RPO (gemma) to be 0.0050.0050.0050.005. We list the remaining training configurations in Table 3, which are recommended by the Alignment Handbook. Configuration Beta Series Gemma Series learning rate 5.0e-7 5.0e-7 learning scheduler type cosine cosine warmup ratio 1.0 1.0 batch size 128 128 gradient accumulation 2 16 batch size per device 8 1 training epoch 1 2 β 0.01 0.05 optimizer adamw torch adamw torch seed 42 42 precision bfloat16 bfloat16 Table 3: Training configurations for beta series and gemma series models in this paper. E.2 Evaluation Details GPT-4 evaluation on the test split. We use the following prompts to guide GPT-4 (0613) to annotate the preferences among win, lose, and tie (we denote them by A, B, and C, respectively). Prompts: Please act as an impartial judge and evaluate the quality of the responses provided by two AI assistants to the user question displayed below. You should choose the assistant that follows the user’s instructions and answers the user’s question better. Your evaluation should consider factors such as the helpfulness, relevance, accuracy, depth, creativity, and level of detail of their responses. Begin your evaluation by comparing the two responses and provide a short explanation. Avoid any position biases and ensure that the order in which the responses were presented does not influence your decision. Do not allow the length of the responses to influence your evaluation. Do not favor certain names of the assistants. Be as objective as possible. After providing your explanation, output your final verdict by strictly following this format: [[A]] if assistant A is better, [[B]] if assistant B is better, and [[C]] for a tie. [Instruction] instruction [The Start of Assistant A’s Answer] answer A [The End of Assistant A’s Answer] [The Start of Assistant B’s Answer] answer B [The End of Assistant B’s Answer] Here, we replace answer A and answer B with the answers of two models. Since GPT annotation has shown to prefer the answer in the first position (Wang et al., 2023a), we randomly exchange the positions between two answers during the evaluation to ensure a fair comparison. Benchmark evaluation. We use the default configuration for the evaluations on MT-Bench111https://github.com/lm-sys/FastChat/tree/main/fastchat/llm_judge and AlpacaEval 2.0222https://github.com/tatsu-lab/alpaca_eval/tree/main. By default, the annotator of MT-Bench is the latest version of GPT-4. The default annotator and the competitor model are both GPT-4 (Preview 11/06). We only need to manually import the proper chat template that formats the training dataset, which are shown as follows. Chat Template for Beta Series: <|system|></s><|user|> instruction</s> <|assistant|> Chat Template for Gemma Series: <bos><|im_start|>user instruction<|im_end|> <|im_start|>assistant E.3 Additional Results on Experiments In this section, we provide the additional results to show the performance gain for RPO (beta) in MT-Bench and RPO (gemma) in AlpacaEval 2.0. We report the pairwise win rates in Tables 4, 5, and 6 to analyze their performance gaps, where all the annotation configurations are the same in Table 2. Results show that RPO still exceeds DPO in the metric of the pairwise win rates on the benchmarks for both beta series and gemma series. win rate (%) RPO (beta) Ref. (beta) DPO (beta) RPO (beta) 50.00 83.75 57.81 Ref. (beta) 16.25 50.00 21.25 DPO (beta) 78.75 42.19 50.00 Table 4: Pairwise win rates (left vs. right) for beta series models on MT-Benchmark. win rate (%) RPO (beta) Ref. (beta) DPO (beta) RPO(beta) 50.00 80.13 52.02 Ref.(beta) 19.87 50.00 20.61 DPO (beta) 47.98 79.39 50.00 Table 5: Pairwise win rates (left vs. right) for gemma series models on AlpacaEval 2.0. win rate (%) RPO (beta) Ref. (beta) DPO (beta) RPO (beta) 50.00 64.93 51.33 Ref. (beta) 35.07 50.00 36.44 DPO (beta) 48.67 64.56 50.00 Table 6: Pairwise Length-Control (LC) win rates (left vs. right) for gemma series models on AlpacaEval 2.0. Appendix F Experiments on Math, Reasoning, and Coding Tasks F.1 Experimental Details To provide a more comprehensive analysis of the trained LLM, we introduce more benchmarks on the math, reasoning, and coding tasks for evaluations. Specifically, we choose the Grade School Math 8K (GSM8K), AI2 Reasoning Challenge (ARC), and Mostly Basic Python Programming (MBPP) to measure math, reasoning, and coding abilities, respectively. In this section, we focus on the gemma series for the experiments. We do not use chain-of-thought or few shots in all the benchmarks. We compare the greedy decoding result (pass @⁢1@1@1@ 1) on the MBPP benchmark. Here we use the OpenRLHF codebase (Hu et al., 2024) to implement a new variant of RPO, where the SFT loss regularizer is averaged by the number of tokens of the chosen labels, that is, (log⁡πθ⁢(acho|x))/|acho|subscriptconditionalsubscriptchosubscriptcho( _θ(a_cho|x))/|a_cho|( log πitalic_θ ( acho | x ) ) / | acho |. Such a variant balances the weight of the averaged SFT loss regularizer between the shorter chosen response and the longer one. We set the coefficient for the SFT loss regularizer as 0.20.20.20.2. We use 8 NVIDIA A100 GPUs for the training and evaluation. The remaining hyperparameters are in Table 7. Configuration Gemma Series learning rate 5.0e-7 learning scheduler type cosine with a minimum learning rate batch size 128 gradient accumulation 8 batch size per device 2 training epoch 2 β 0.5 optimizer adamw torch seed 42 precision bfloat16 Table 7: Training configurations for DPO and RPO for the experiments in Appendix F. F.2 Experimental Results Table 8 demonstrates that our proposed method still outperforms or performs equally to the vanilla DPO on these benchmarks of math, reasoning, and coding, which verifies the effectiveness of our proposed method. Model Name GSM8K ARC MBPP (Pass @⁢1@1@1@ 1) (%) Easy (%) Challenge (%) Normal (%) Plus (%) RPO 49.9 79.1 49.8 54.2 46.3 DPO 45.3 75.7 50.0 54.2 43.9 Ref. 45.4 75.0 45.8 50.3 44.2 zephyr-gemma-7b 47.3 77.6 48.6 54.5 44.7 Table 8: The results on GSM8K, ARC, and MBPP. Here, zephyr-gemma-7b is the officially released models trained by DPO and Ref. denotes the reference model zephyr-7b-gemma-sft used for our training. RPO and DPO are trained with the OpenRLHF codebase (Hu et al., 2024) and we average the SFT loss regularizer in RPO by the number of tokens of the chosen response. We do not use chain-of-thought or few shots in all the benchmarks. We compare the greedy decoding result (pass @⁢1@1@1@ 1) for MBPP.

Instant research discovery