Paper deep dive
Policy Teaching via Data Poisoning in Learning from Human Preferences
Andi Nika, Jonathan Nöther, Debmalya Mandal, Parameswaran Kamalaruban, Adish Singla, Goran Radanović
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 96%
Last extracted: 3/12/2026, 5:29:21 PM
Summary
The paper presents a theoretical framework for analyzing data poisoning attacks in preference-based learning, specifically targeting Reinforcement Learning from Human Feedback (RLHF) and Direct Preference Optimization (DPO). The authors derive sample complexity bounds for an attacker aiming to enforce a target policy by synthesizing or augmenting preference datasets, demonstrating that the susceptibility of these paradigms depends on the alignment between the target policy and the reference policy.
Entities (5)
Relation Signals (3)
RLHF → issusceptibleto → Data Poisoning
confidence 95% · We study data poisoning attacks in learning from human preferences... namely: (a) reinforcement learning from human feedback (RLHF)
DPO → issusceptibleto → Data Poisoning
confidence 95% · We study data poisoning attacks in learning from human preferences... namely: (b) direct preference optimization (DPO)
Data Poisoning → targets → Target Policy
confidence 95% · the problem of teaching/enforcing a target policy π† by synthesizing preference data
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We study data poisoning attacks in learning from human preferences. More specifically, we consider the problem of teaching/enforcing a target policy $\pi^\dagger$ by synthesizing preference data. We seek to understand the susceptibility of different preference-based learning paradigms to poisoned preference data by analyzing the number of samples required by the attacker to enforce $\pi^\dagger$. We first propose a general data poisoning formulation in learning from human preferences and then study it for two popular paradigms, namely: (a) reinforcement learning from human feedback (RLHF) that operates by learning a reward model using preferences; (b) direct preference optimization (DPO) that directly optimizes policy using preferences. We conduct a theoretical analysis of the effectiveness of data poisoning in a setting where the attacker is allowed to augment a pre-existing dataset and also study its special case where the attacker can synthesize the entire preference dataset from scratch. As our main results, we provide lower/upper bounds on the number of samples required to enforce $\pi^\dagger$. Finally, we discuss the implications of our results in terms of the susceptibility of these learning paradigms under such data poisoning attacks.
Tags
Links
- Source: https://arxiv.org/abs/2503.10228
- Canonical: https://arxiv.org/abs/2503.10228
Trouble viewing inline? Open PDF directly →
Full Text
111,102 characters extracted from source content.
Expand or collapse full text
Policy Teaching via Data Poisoning in Learning from Human Preferences Andi Nika MPI-SWS Jonathan N ̈other MPI-SWS Debmalya Mandal University of Warwick Parameswaran Kamalaruban Featurespace Adish Singla MPI-SWS Goran Radanovi ́c MPI-SWS Abstract We study data poisoning attacks in learning from human preferences. More specifically, we consider the problem of teaching/enforcing a target policyπ † by synthesizing preference data. We seek to understand the suscepti- bility of different preference-based learning paradigms to poisoned preference data by analyzing the number of samples required by the attacker to enforceπ † . We first propose a general data poisoning formulation in learning from human preferences and then study it for two popular paradigms, namely: (a) reinforcement learning from human feedback (RLHF) that operates by learning a reward model using preferences; (b) direct preference optimization (DPO) that directly optimizes policy using preferences.We conduct a theoretical analysis of the effectiveness of data poisoning in a setting where the attacker is allowed to augment a pre-existing dataset and also study its special case where the attacker can synthesize the entire preference dataset from scratch. As our main results, we provide lower/upper bounds on the number of samples required to enforceπ † . Finally, we discuss the implications of our results in terms of the susceptibility of these learning paradigms under such data poisoning attacks. 1 Introduction Learning from human preferences has recently attracted considerable attention, largely due to its Proceedings of the 28 th International Conference on Artifi- cial Intelligence and Statistics (AISTATS) 2025, Mai Khao, Thailand. PMLR: Volume 258. Copyright 2025 by the author(s). effectiveness in fine-tuning large language models (LLMs). Unlike the traditional approach, which uses training data labeled with absolute scores, this method relies on pairs of examples marked with binary signals indicating preference—essentially assigning a relative score to each example. As such, it has proven to be practically beneficial since comparative feedback between two examples is more easily accessible than their individual absolute scores. Despite its practical advantages, learning from human preferences is susceptible to data poisoning attacks [Biggio et al., 2012], due to the potential presence of malicious human feedback in the training data. Malig- nant third parties could easily alter preference datasets to steer LLMs toward generating biased or harmful content which can lead to undesired model behaviours. This vulnerability is particularly concerning, given the rapid integration of LLMs into critical applications. It is thus essential to understand these attacks in order to design models with robust guarantees against them. These concerns have motivated a lot of recent work, all of which has focused on empirical investigations of poisoning attacks. For example, Wang et al. [2023b] demonstrated the effectiveness of ranking poisoning attacks, where attackers manipulate preference labels without altering the underlying data. Shi et al. [2023] showed how an attacker could inject trigger words into training prompts, influencing the LLM’s sentiment analysis. Rando and Tram`er [2023] proposed univer- sal backdoor attacks, embedding hidden functionalities within LLMs, and Baumg ̈artner et al. [2024] investi- gated data augmentation attacks that inject entirely new preference pairs. Despite these attempts, a strong theoretical foundation for understanding the robustness of learning from hu- man preferences against data poisoning attacks remains elusive. Motivated by this, we initiate a theoretical study of data poisoning attacks in learning from human preferences. We seek to analyze these attacks from the arXiv:2503.10228v1 [cs.LG] 13 Mar 2025 Policy Teaching in Learning from Human Preferences attacker’s viewpoint which, in turn, would allow us to identify more robust settings and design effective de- fenses, ultimately ensuring the security and reliability of preference-based learning in real-world applications. In particular, we focus on two of the most prominent techniques of learning from human preferences, namely, reinforcement learning from human feedback (RLHF) [Stiennon et al., 2020, Ouyang et al., 2022, Ziegler et al., 2019, Gao et al., 2023, Menick et al., 2022, Glaese et al., 2022, Bai et al., 2022, Brown et al., 2019, Shin et al., 2023] and direct preference optimization (DPO) [Rafailov et al., 2023]. We consider an attacker that aims to enforce a target policyπ † by generating new preference data b D . The aim of the attacker is to ensure an RLHF/DPO learner trained on b Dconverges to a pol- icy that isε-close toπ † . We analyze the number of sam- ples the attacker requires to enforceπ † in settings where the attacker can synthesize the entire preference dataset from scratch and where it has to augment a pre-existing datasetD. Our contributions are summarized below: •Attack problem formulation:We propose a general data poisoning formulation in learning from human preferences and instantiate it for two popular paradigms of RLHF and DPO. In partic- ular, we propose an attack problem formulation using theℓ 1 -norm as a constraint, motivated by previous formulations suited for reward-based RL with deterministic target policies. We consider two types of RLHF learners: unregularized RLHF and regularized RLHF, depending on whether the learner is restricted to remain close to a given reference policyμor not. •Attacks on RLHF:We analyze the sample complexity of the attack in unregularized and regularized RLHF settings. In the unregularized setting, our bounds depend on the state-action space cardinality, the attack granularity parameter ε, the covariance matrix of the pre-existing data, and its sizen. In the regularized RLHF setting, the dependence on the state-action space size is replaced with dependence on the regularization temperatureβand the gap betweenπ † andμ. •Attacks on DPO:Moreover, we provide lower and upper bounds on the attack sample complexity in the DPO setting, by showing that feasible regions for the surrogate problem act both as relaxations and restrictions of the original feasible region, for different values of attack granularity parameter. In this setting, the sample complexity depends on the squared norms of the parameters ofπ † andμand the pre-existing dataset sizen. •Comparison: Finally, we derive conclusions on the susceptibility of DPO to attack relative to RLHF, both in the data augmentation and data synthesis setting. Our results suggest that, the farther away the target policyπ † is from the reference policyμin the parameter space, the stronger the tendency of DPO to remain closer to μunder attacks, relative to RLHF. 2 Preliminaries and Background on Learning from Human Preferences In this section, we provide the necessary technical back- ground that will be used throughout the paper. 2.1 Preliminaries Environment.LetM=⟨S,A,P,r,γ,ρ⟩be an infinite-horizon discounted Markov decision process (MDP), whereSdenotes the state space andAdenotes the action space, with cardinalitiesSandA, respec- tively;P:S ×A×S →[0,1] denotes the transition function, whereP(s,a,s ′ ) denotes the probability of transitioning to states ′ when taking actionain state s; the reward is denoted byr:S ×A →Rand the discount factor byγ∈[0,1). Finally, we letρbe the initial state distribution. A contextual bandit can be viewed as a special case of this MDP formalism where the state transitions are independent of the actions taken, and the discount factorγis set to 0. Policies and value functions.Stochastic poli- cies are mappings from states to action simplices, π:S →∆(A), where ∆(A) is the probability simplex with support inA.A deterministic pol- icy is a mappingπ:S → A, a special case of stochastic policies. Let Π and Π det denote the set of all stochastic and deterministic policies defined overSandA, respectively.For a policyπand state-action pair (s,a), we defined π s,a (s ′ ,a ′ ) = (1− γ ) P ∞ t=1 γ t P(s t =s ′ ,a t =a ′ |s 0 =s,a 0 =a,π) ,and d π s (s ′ ,a ′ ) = (1−γ) P ∞ t=1 γ t P(s t =s ′ ,a t =a ′ |s 0 =s,π) . Furthermore,wedefined π s,a (s ′ )= P a ′ d π s,a (s ′ ,a ′ )π(a ′ |s ′ ),d π s (s ′ ) = P a ′ d π s (s ′ ,a ′ )π(a ′ |s ′ ), andd π ρ (s ′ ,a ′ ) =E s∼ρ [d π s (s ′ ,a ′ )]. We focus onergodic MDPs where every state is reachable under any policy and initial distribution. The value function of a policy π∈Π with respect to a given reward functionris given as V π r (s) =E π,P " ∞ X t=0 γ t r(s t ,a t )|s 0 =s # . Similarly, its action-value function is given as Q π r (s,a) =E π,P " ∞ X t=0 γ t r(s t ,a t )|s 0 =s,a 0 =a # . Nika, N ̈other, Mandal, Kamalaruban, Singla and Radanovi ́c We also defineV π r (ρ) =E s∼ρ [V π r (s)]. A policyπ ⋆ ∈Π is said to be optimal in Π with respect torifV π ⋆ r (ρ)≥ V π r (ρ), for allπ∈Π. Moreover,π ⋆ is said to beε- robust optimal in Π with respect tor, for a givenε >0, ifV π ⋆ r (ρ)≥V π r (ρ) +ε, for allπ∈Π\π ⋆ . We define the KL-divergence between two policiesπandπ ′ as D KL (π||π ′ ) = X s,a ρ(s)π(a|s) (logπ(s|a)−logπ ′ (a|s)). Whenπ,π ′ ∈Π det , we defineD KL (π||π ′ ) = 0 iffπ=π ′ , and∞otherwise. Later in our analysis, we consider the following classes. Definition 2.1(Linear rewards).Letφbe ad- dimensional feature mappingφ:S ×A →R d with max s,a ∥φ(s,a)∥ 2 ≤1. We consider the following class of linear reward functions: R=r ω :r ω (s,a) =ω ⊤ φ(s,a),∀(s,a)∈S×Aforω∈R d . Definition 2.2(Loglinear policies).Letψbe ad ′ - dimensional feature mappingψ:S ×A →R d ′ with max s,a ∥ψ(s,a)∥≤1. We consider the following class of loglinear policies: Π log = ( π θ :π θ (a|s) = exp ψ(s,a) ⊤ θ P a ′ exp (ψ(s,a ′ ) ⊤ θ) , ∀(s,a)∈S×Awhereθ∈R d ′ ) . By overloading the notation, for a trajectoryτ= (s 0 ,a 0 ,s 1 ,...), we defineφ(τ) = P ∞ t=0 γ t φ (s t ,a t ) andψ(τ) = P ∞ t=0 γ t ψ (s t ,a t ).Furthermore, for a policyπand state-action pair (s,a), we define φ π (s,a) = P s ′ ,a ′ d π s,a (s ′ ,a ′ )φ(s ′ ,a ′ ) andψ π (s,a) = P s ′ ,a ′ d π s,a (s ′ ,a ′ )ψ(s ′ ,a ′ ). 2.2 Background on Learning from Human Preferences In learning from human preferences, a learner refines behavior by iteratively learning from human feedback. Given a preference datasetD=(τ,τ ′ ,o), where o= 1 indicates that trajectoryτis preferred over τ ′ , ando=−1 indicates the opposite, the learnerL outputs a policyπ=L(D,μ) that aligns better with human preferences. Here,μrepresents a reference policy, which could be a pre-trained model. Examples of such learners include agents that use reinforcement learning from human feedback (RLHF)L RLHF [Ziegler et al., 2019] or direct preference optimization (DPO) L DPO [Rafailov et al., 2023]. Before introducing these methods, we first define the preference model. Definition 2.3(Bradley-Terry preference model [Bradley and Terry, 1952]).The Bradley-Terry prefer- ence model w.r.t. a reward functionris defined as fol- lows: for every tuple (τ,τ ′ ,o), we haveP(o= 1|τ,τ ′ )= σ( P ∞ t=0 γ t r(s t ,a t )− P ∞ t=0 γ t r(s ′ t ,a ′ t )), whereσ(z) = 1/(1 + exp(−z)). Reinforcement learning from human feedback. With access to the datasetDand reference policyμ, RLHF [Ziegler et al., 2019] proceeds in two phases. In the first phase, a reward function is learned fromD using maximum likelihood estimation (MLE) based on the Bradley-Terry preference model. This involves solving the following regularized MLE problem (with regularization parameterλ >0): min ω ℓ ω RLHF (D) :=− X (τ,τ ′ ,o)∈D log σ o· X t≥0 γ t (r ω (s t ,a t )−r ω (s ′ t ,a ′ t )) + λ 2 ∥ω∥ 2 . (P:RLHF.Reward) Letbωdenote the solution of Problem Equa- tion P:RLHF.Reward. In the second phase, RLHF solves the following regularized policy optimization based on the learned rewardr bω (with regularization parameterβ >0) to obtain optimal solutionπ reg r bω in: arg max π∈Π E π,P X t≥0 γ t r bω (s t ,a t )−βlog π(a t |s t ) μ(a t |s t ) . (P:RLHF.Policy) We denote byV π r bω (ρ) the regularized objective above. Direct preference optimization.DPO [Rafailov et al., 2023] leverages the relationship between a reward functionrand its corresponding regularized optimal policyπ reg r to bypass the reward-learning phase, and directly optimize the policy. However, DPO is currently limited to contextual bandit settings, where we have τ= (s,a) andτ ′ = (s,a ′ ). GivenDandμ, DPO solves the following optimization problem (with regularization parameterλ >0) to obtain optimal solution b θas: min θ ℓ θ DPO (D) :=− X (τ,τ ′ ,o)∈D log σ o· βlog π θ (a|s) μ(a|s) −βlog π θ (a ′ |s) μ(a ′ |s) + λ 2 ∥θ−θ μ ∥ 2 . (P:DPO) 3 Preference Poisoning Attack Setup In this section, we formulate the problem of data poi- soning attacks on learning from human preferences. We consider an attacker aiming to impose a target policy π † onto a learner. To achieve this, the attacker modifies the preference dataset so that the learner trained on the altered data produces a policy close toπ † . Ideally, the attacker should make minimal modifications to achieve this outcome. Policy Teaching in Learning from Human Preferences Attack goal and poisoned data.LetDrepresent the clean preference dataset originating from the en- vironmentM, and letμdenote the reference policy. The learner, denoted byL, is trained on the prefer- ence dataset. The attacker is modeled as a mapping P, which takes the clean datasetD, environmentM, reference policyμ, and learnerLas inputs, and outputs a poisoned dataset b D=P(D,μ,M,L). We assume the attacker has full knowledge of the environment. Given a margin parameterε, the attacker poisons the datasetDso that the learnerLtrained on the poisoned dataset b Dconverges to a policy within anεdistance ofπ † , i.e., π † −π L 1 ≤ε, whereπ L =L( b D,μ) and ∥π−π ′ ∥ 1 = P s,a ρ(s)|π(a|s)−π ′ (a|a)|is theℓ 1 norm between given policiesπandπ ′ . Attack cost and formulation.We consider a set- ting where the attacker canaugmenta pre-existing preference datasetD. Moreover, we instantiate this setting to the case whenDis empty. Since adding sam- ples incurs a cost, the attacker aims to enforceπ † by minimally adding additional samples. The attacker’s optimization problem can be formalized as min D |D|such that π † −π L 1 ≤ε , whereπ L =L( D∪D,μ).(P:Attack) Attack feasibility and synthesis.We consider poi- soning attacks on two learning paradigms in learning from human preferences, RLHF and DPO, as intro- duced in Section 2.2. We identify the specific condi- tions within both learning paradigms that make such attacks feasible: •We consider an attacker that has the synthesis capability to find a trajectory pair (τ,τ ′ ) for any givenz∈R d such thatφ(τ)−φ(τ ′ ) =zorψ(τ)− ψ (τ ′ ) =z. In practice, this assumption translates to the following requirement. Given a prompt- response pair (x,y) :=τand a vectorz∈R d , the attacker can find a responsey ′ such that the difference between (x,y) and (x,y ′ ) :=τ ′ in the embedding space is approximately equal toz, i.e., φ(τ)−φ(τ ′ )≈zorψ(τ)−ψ(τ ′ )≈z. • For an unregularized RLHF attack to be feasible, we must haveπ † ∈Π det . For a regularized RLHF and DPO attack to be feasible, we must haveπ † ,μ∈ Π log . Notation.Next we introduce some notation that will be useful in the following sections. As usual, [n] =1,2,...,ndenotes the set of firstnnatural numbers.⟨v,z⟩=v ⊤ zdenotes the inner product of two compatible vectorsvandz. Further, we denote by Φ and Ψ the matrices with columnsφ(s,a) ⊤ and ψ(s,a) ⊤ , respectively, for every (s,a)∈ S ×A. We assume throughout that Φ and Ψ are full rank. Unless otherwise specified,∥v∥denotes the Euclidean norm, ∥M∥denotes the spectral norm for matrixM, andM + denotes its pseudoinverse.0and1denote the vectors of zeroes and ones, respectively, andIdenotes the identity matrix. We denote byσ max (M) andσ min (M) the maximum and minimum eigenvalues (or singular values) of a given square (rectangular) matrixM, re- spectively. Letξ max :=max x x/(1+exp(x)) and denote byx ⋆ =arg max x x/(1 +exp(x)). Letξ −1 (a) denote the solution toa=x/(1 +exp(x)), for anya < ξ max , where the domain ofx/(1 +exp(x)) is (−∞,x ⋆ ]. More- over, we defineξ 1 (a) =ξ −1 (a⌈a/ξ max ⌉ −1 ) andξ 2 (a) = ξ −1 (2a⌈a/(2ξ max )⌉ −1 ). 4 Poisoning Attacks on RLHF In this section, we study data poisoning attacks on RLHF, where the attacker synthesizes b DfromD. We start our discussion by formulating the general attack problem for RLHF. We do this by instantiating Problem P:Attack for this setting as: min D |D|such thatbω= arg min ω ℓ ω RLHF D∪D and π † −π reg r bω 2 1 ≤ε .(P:Attack:RLHF.1) InAppendixA,weshowthatProblem P:Attack:RLHF.1 is feasible wheneverπ † ∈Π det or π † ,μ∈Π log . We study the following scenarios: (i) the general unregularized RLHF (β= 0) setting with data augmentation (D̸=∅) and data synthesis (D=∅), for deterministicπ † ; (i) the regularized RLHF setting (β >0) with data augmentation and data generation for general policiesπ † . 4.1 Unregularized RLHF Forβ= 0, Problem P:RLHF.Policy reduces to a stan- dard value maximization problem, for which optimal policiesπ L are known to be deterministic. Thus, if we are given a pre-existing datasetDand can aug- ment it into b Dsuch that, when used to solve Prob- lem P:RLHF.Reward, yields a reward function making π † ε ′ -robust optimal, for someε ′ >0, thenπ L is guar- anteed to converge toπ † as the unique optimal policy. Rakhsha et al. [2021] show that checking theε ′ -robust optimality condition for neighboring policiesπ † s,aof π † for all (s,a) pairs is sufficient. Here,π † s,a(s ′ ) = π † (s), ifs̸=s ′ , andπ † s,a(s ′ ) =a, otherwise. In the linear reward setting, these constraints are rep- resented compactly by the polytopeM ⊤ π † ω≥ε ′ (see Figure 1 for a geometric illustration), whereM π † is Nika, N ̈other, Mandal, Kamalaruban, Singla and Radanovi ́c Reward space Reward parameter Attack sample Region of target parameters Existing sample RLHF Reward spaceReward space Non-empty data (unregularized)Empty data (unregularized)Non-empty data (regularized) Figure 1:A geometric illustration of our attack model for RLHF. The shaded regions represent the reward parameter spaces where optimal policies areε-close toπ † . The blue arrows represent attack samples, while the yellow arrows represent the pre-existing data samples fromD. Finally, the red shape represents the optimal reward parameters with respect to the generated dataset b D. Each added attack sample moves the optimal parameter closer to the shaded region. For unregularized RLHF with emptyD(left), the attack problem is solved in the reward parameter space, and the target space is a polytope. For unregularized RLHF with non-emptyD(middle), the required samples depend on the alignment ofπ † withD. For regularized RLHF (right), since the optimal policy is not necessarily deterministic, the geometry of the target space becomes non-linear. ad×S(A−1)-dimensional matrix. 1 Its columns are defined as P s ′ φ(s ′ ,π † (s ′ ))−φ(s ′ ,π † s,a(s ′ )), for all (s,a), andε ′ is theS(A−1)-dimensional vector with entriesε ′ . The columns of matrixM π † represent the differences in the average feature distribution between π † and its neighbors. Leveraging this polytope constraint, we instanti- ate the general preference poisoning attack prob- lem P:Attack:RLHF.1 for the RLHF paradigm in the setting where the clean preference datasetDis non- empty (with size D = n), as follows: min D |D|such thatbω= arg min ω ℓ ω RLHF D∪D andM ⊤ π † bω≥ε ′ .(P:Attack:RLHF.2) Note that the above is a surrogate of Problem P:Attack:RLHF.1, since, in unregularized RLHFπ reg r bω is the optimal policy with respect tor bω which, as we ex- plained above, is enforced by the constraintM ⊤ π † bω≥ε ′ . The solution to the above data augmentation attack problem depends on data-dependent quantities due to the pre-existing data. Let us define the covariance matrix with respect toDas Σ φ D = (1/n) X (τ,τ ′ )∈D (φ(τ)−φ(τ ′ ))(φ(τ)−φ(τ ′ )) ⊤ . We are now ready to state our first result. Theorem 4.1.LetDbe a given preference dataset ofn samples, letβ= 0,ε ′ >0andπ † ∈Π det . Furthermore, letωbe optimal forℓ ω RLHF (D), defineω † as proj ω:M π † ω≥ε ′ ( ω) =ω+M π † M ⊤ π † M π † + (ε ′ −M π † ω) 1 Note that, since the vectorε ′ has all entriesε, the inequality condition can be satisfied even when the rank ofM π † is less thanSA. The minimal requirement is that all inequalities of the system are consistent, i.e., they yield intersecting regions. and letγ≥1−2 ω † /(ξ max + 1). Then, the dataset of l (ω † ) ⊤ ∇ ω ℓ ω † RLHF (D) /ξ max m identical samples sat- isfyingo= 1and φ(τ)−φ(τ ′ ) =ξ 1 ω † ⊤ ∇ ω ℓ ω † RLHF ( D) ω † ∥ω † ∥ 2 , is a feasible solution to Problem P:Attack:RLHF.1. Fur- thermore, there exists an optimal solution b D for Prob- lem P:Attack:RLHF.1 withbn RLHF identical samples such that bn RLHF ≤ & 2n+λ ξ max (ε ′ ) 2 SA σ 2 min (M π † ) +∥ω∥ ε ′ √ SA σ min (M π † ) !' . Sketch of proof.We start by considering the re- ward learning subproblem for the surrogate problem P:Attack:RLHF.2. We utilize the solution of the prob- lem of machine teaching to logistic regression learners [Liu and Zhu, 2016] and relate it to our reward sub- problem. Next, we proceed to solving the modified optimization problem with respect to the final con- straint. In our setting, the samples fromDare fixed, and thus cannot be treated as variable. Therefore, we need to design a new attack dataset b Dwith samples depending on the gradient of the loss with respect to D, which captures how alignedDis withπ † . In the best case, the optimal parameter with respect toD is already in the target polytope, meaning that the number of samples in this case is 0. In order to obtain closed-form bounds, we construct a feasible solution using the projection of the optimal solution with re- spect toDonto the polytope and make use of strong convexity and Lipschitzness ofℓ ω RLHF (D) to get our results. We also show in Appendix E thatM π † is full rank under mild assumptions. This guarantees that our bounds are finite. Before going to the next section, we instantiate Problem P:Attack:RLHF.2 to the case when the pre-existing Policy Teaching in Learning from Human Preferences dataset is empty. The following result is a corollary of Theorem 4.1. Corollary 4.1.LetD=∅,β= 0andε ′ >0, and letπ † ∈Π det . Defineω † =M π † M ⊤ π † M π † + ε ′ . Then, the dataset of λ ∥ ω † ∥ 2 ξ max identical samples satisfying φ(τ)−φ(τ ′ ) =ξ 1 λ ω † · ω † ∥ω † ∥ 2 , o= 1 is a feasible solution for Problem P:Attack:RLHF.1. Furthermore, there exists an optimal solution b Dfor Problem P:Attack:RLHF.1 withbn RLHF samples such that bn RLHF ≤ (ε ′ ) 2 λSA ξ max σ 2 min (M π † ) . 4.2 Regularized RLHF. Now, we consider Problem P:Attack:RLHF.1 under a general setting, where the regularization parameter β >0 and the preference datasetD̸=∅. In this set- ting, we are dealing with loglinear policies (see Section 3) which, since they are stochastic, lead to infinitely many constraints – hence, it is challenging to apply the polytope constraint idea from the above unregular- ized RLHF setting. Therefore, we consider a surrogate problem with constraints that are suited to stochastic policies. We will make use of the KL divergence for that purpose. We write the surrogate attack problem as min D |D|such thatbω= arg min ω ℓ ω RLHF D∪D andD KL π † ||π reg r bω ≤ε ′ ,(P:Attack:RLHF.3) whereπ reg r bω is the optimal policy for the regularized objective P:RLHF.Policy. We obtain the following bounds for this setting: Theorem 4.2.LetDbe a given preference dataset of nsamples,β >0and0< ε ′ ≤ε. Moreover, define Γ ω φ (π † ||π reg r ω ) = X s,a ρ(s)(π † (a|s)−π reg r ω (a|s))φ π reg r ω (s,a), for any givenω. Then, there exists a feasible solution b Dfor Problem P:Attack:RLHF.1 withbn RLHF samples which yieldsω † when solving Problem P:RLHF.Reward on dataset b D, such thatΓ ω φ (π † ||π reg r ω † )̸= 0and bn RLHF ≤O β 2 D KL π † ||μ −ε ′ 2 (1−γ) 2 σ 2 min (Σ φ D ) Γ ω † φ (π † ||π reg r ω † ) 2 + n (1−γ) 4 σ 4 min (Σ φ D ) ! . Sketch of proof.We start by showing that solving the surrogate subproblem is enough to obtain upper bounds on the sample size for suitableε ′ . Then, we solve the reward learning subproblem and obtain a dataset b D withbn RLHF identical samples that satisfyφ(τ)−φ(τ ′ ) = ξ −1 λ ∇ ω ℓ ω RLHF (D) ⊤ ω /bn RLHF ω/∥ω∥ 2 witho= 1, wherebn RLHF is given in terms of ∇ ω ℓ ω RLHF (D) ⊤ ω . Then, we solve the equivalent problem of minimizing ∇ ω ℓ ω RLHF (D) ⊤ ω , subject toωyielding a regularized optimal policyπ reg r ω that satisfiesD KL (π † ||π reg r ω )≤ε. Usingω † as a feasible solution in the expression, we finalize the bounds. Remark4.1.Note that the term Γ ω † φ (π † ||π reg r ω † ) repre- sents the average trajectory feature difference between π † andπ reg r ω when rolling out trajectories usingπ reg r ω † . If this term is uniformly0at the problem solutionω † , then this means that, eitherπ † =π reg r ω † , or at least the two policies are identical in the average trajectory feature space. Therefore, less samples are needed to satisfy our objective. The following result provides bounds that depend on such a solutionω † . Its proof follows immediately from the proof of Theorem 4.2. Corollary 4.2.There existsω † such thatπ † =π reg r ω † . Moreover, we have thatω † is a feasible solution for Problem P:Attack:RLHF.1 and bn RLHF ≤ 1 ξ max λ ω † 2 + ω † · 2n (1−γ) 2 . Finally, we instantiate the above result in the case when the pre-existing data is empty. Corollary 4.3.LetD=∅,β >0and0< ε ′ ≤ ε . There exists a feasible solution b D for Problem P:Attack:RLHF.1 withbn RLHF samples such that bn RLHF ≤ & λ ω † 2 ξ max ' , whereω † is defined as in Corollary 4.2. Remark4.2.Note that, whenD=∅, the number of samples required for an efficient attack on regularized RLHF depends on the norm of the reward parameter that makesπ † nearly-optimal. 5 Poisoning Attacks on DPO As we have mentioned, the DPO objective is formulated only for the contextual bandit setting. Recall that trajectories here are defined in terms of context-action pairsτ= (s,a). We instantiate the general poisoning attack problem P:Attack for the DPO paradigm as follows: Nika, N ̈other, Mandal, Kamalaruban, Singla and Radanovi ́c min D |D|such that b θ= arg min θ ℓ θ DPO (D∪D) and π † −π b θ 2 1 ≤ε .(P:Attack:DPO.1) In general, obtaining an intuitive form of attack con- struction for the above problem, as presented in Theo- rem 4.1, is challenging. To facilitate a more intuitive and efficient attack construction, we consider the fol- lowing surrogate problem: min D |D|such that b θ= arg min θ ℓ θ DPO D∪D and b θ−θ † 2 ≤ε ′ ,(P:Attack.DPO.2) whereθ † ∈R d ′ such thatπ † =π θ † (see Section 3). Specifically, we have replaced theℓ 1 -norm-based con- straint with anℓ 2 -norm-based constraint on the pol- icy parameter space. The attack is successful if the learner’s policy parameter converges closer to the tar- get parameterπ θ † . We derive the following result for this setting: Theorem 5.1.LetDbe a given preference dataset of nsamples, letβ >0and0< ε ′ ≤ε/2. Furthermore, letθbe the optimal point forℓ θ DPO (D)and define e θ= proj θ:∥θ−θ † ∥≤ε ′ θ =θ † + (ε ′ ) 2 θ−θ † 2 θ−θ † . Then, the dataset b Dcontaining 2 l |(∇ θ ℓ e θ DPO ( D)) ⊤ ( e θ−θ μ )|/(2ξ max ) m identical samples satisfying β e θ−θ μ ⊤ (ψ(s,a)−ψ(s,a ′ )) =o·ξ 2 ∇ θ ℓ e θ DPO ( D)) ⊤ e θ−θ μ , witho= 1for half the samples ando=−1 for the remaining, is a feasible solution to Problem P:Attack:DPO.1. Furthermore, there exists an opti- mal solution b Dto Problem P:Attack:DPO.1 withbn DPO identical samples such that bn DPO ≤2· ( nβ+λ) θ−θ † 2 −(ε ′ ) 2 2ξ max θ † − θ 3 θ † +∥θ μ ∥+ √ ε ′ . Sketch of proof.First, we show that, for suitableε ′ , any feasible solution to the surrogate problem is feasible for the original problem. The first main challenge in this setting for constructing b Dis the presence of bothD andθ μ in the DPO objective. We first show that, given parameterθ, the sample size that makesπ θ optimal forℓ θ DPO (D∪D) is a factor of ∇ θ ℓ θ DPO (D) ⊤ (θ−θ μ ) . Using this, we redefine the objective of our problem and use theℓ 2 -ball centered atθ † with radius √ ε ′ as constraint. The second main challenge consists of dealing with inverses of sums of matrices, due to the effect of the pre-existing data, for which we use the Woodbury inversion formula, and then proceed to solve a quadratic equation to obtain a fixed-point solution of our problem. Using the properties of that solution, we obtain the bounds on the norm of the optimal parameter e θ. To obtain bounds on the norm of the gradient, we utilize Lipschitzness ofℓ θ DPO (D), and the geometrical relationship betweenθandθ † . Next, we establish a lower bound on the attack sample complexity for the DPO setting. Theorem 5.2.LetDbe a given preference dataset of nsamples and letβ >0. Then, there existsη min >0, such that for anyε ′ ≥ε/η min , we have bn DPO ≥2 λ 2ξ max θ † −θ μ − √ ε ′ 2 − n . Sketch of proof. Let Θ 1 =θ:∥π θ −π θ † ∥ 2 1 ≤ε and Θ 2 =θ: θ−θ † 2 ≤ε ′ . First, we prove that there exists a positive constantη min such that Θ 1 ⊆Θ 2 , for anyε ′ ≥ε/η min . This means that the feasible region of the surrogate problem is larger, which im- plies that a lower bound on the solution of Problem P:Attack.DPO.2 is also a lower bound on the solution of Problem P:Attack:DPO.1. Next, we focus on Problem P:Attack.DPO.2 and show that we can reduce it to a convex program. Using KKT conditions, we obtain an exact solution to the problem. We then use this solution as a lower bound for Problem P:Attack:DPO.1. Remark5.1.Note that the upper bounds from The- orem 5.1 hold for different value ofε ′ than the one required for the lower bounds of Theorem 5.2. This is because we are essentially tuning the radius of the feasible region of Problem P:Attack.DPO.2 so that it is either contained in the feasible region of Problem P:Attack:DPO.1 (which is what we need for the upper bounds), or it contains the feasible region of Prob- lem P:Attack:DPO.1 (which is what we need for lower bounds). When there is no pre-existing data, the attacker can synthesise any poisoning dataset from scratch. An immediate solution to this problem is the instantiation of Theorem 5.1 whenD=∅. However, below we also provide tight upper bounds that match the lower bounds of Theorem 5.2 for the empty data setting. Theorem 5.3.LetD=∅, letβ >0and0< ε ′ ≤ ε/2. Furthermore, letπ † ,μ∈Π log be loglinear with Policy Teaching in Learning from Human Preferences Policy spacePolicy space DPO Empty dataNon-empty data Policy parameter Attack sample Region of target parameters Existing sample Figure 2:A geometric illustration of our attack model for DPO. Here, the distinction between empty and non-emptyDis similar to Figure 1. In contrast to the RLHF setting, here the attacker operates directly in the policy parameter space and the target feasible region is a ball centered aroundθ † with radiusεas outlined in the formulation of Problem P:Attack.DPO.2. parametersθ † andθ μ , respectively. Define e θ=θ † +e √ ε ′ (θ μ −2θ † )/ θ μ −2θ † , wheree= 1, ifθ † ⊤ θ † −θ μ ≥ √ ε ′ −ε ′ , ande= −1, otherwise. Then, the dataset of2 λ | λ e θ ⊤ ( e θ−θ μ )| 2ξ max samples satisfying β e θ−θ μ ⊤ (ψ(s,a)−ψ(s,a ′ )) =o·ξ 2 λ e θ−θ μ 2 witho= 1for half of the samples, ando=−1 for the remaining is a feasible solution to Problem P:Attack:DPO.1. Furthermore, there exists an opti- mal solution b Dto Problem P:Attack:DPO.1 withbn DPO identical samples such that bn DPO ≤2 λ 2ξ max θ † −θ μ − √ ε ′ 2 . Finally, there existsη min >0, such that, for anyε ′ ≥ ε/η min , we have bn DPO ≥2 λ 2ξ max θ † −θ μ − √ ε ′ 2 . 6 Comparison between RLHF and DPO for Attack Susceptibility In this section, we present some interesting takeaways from the analysis of previous sections. We aim to provide a comparative analysis of the attack sample complexities between the RLHF and DPO paradigms. Specifically, we focus on the contextual bandit setting. The following result establishes an explicit relationship between the sample complexities of data augmentation attacks on the RLHF and DPO paradigms. Specif- ically, we compare the sample complexities,bn RLHF andbn DPO , required by the optimal solutions to Prob- lems P:Attack:RLHF.1 and P:Attack:DPO.1, respec- tively (with D =n). Theorem 6.1.Letπ † ,μ∈Π log be loglinear with pa- rametersθ † andθ μ , respectively. Furthermore, letεbe such thatε≤1/(2ξ max ),ε ′ ≥ε/η min , whereη min >0 is an absolute constant, and letω † be a feasible solution to Problem P:Attack:RLHF.1. Defineκ 1 as λ ξ max θ † −θ μ − √ ε ′ 2 −n · 1 ξ max λ ω † 2 + ω † · 2 n (1−γ) 2 −1 Then, we havebn DPO ≥κ 1 ·bn RLHF . The value ofκ 1 is proportional to the distance between θ † andθ μ , which captures how farπ † is from the refer- ence policyμ. We observe that, the greater the distance betweenπ † andμ, the less susceptible DPO becomes relative to RLHF. Lower susceptibility implies DPO has a stronger tendency to remain close toμ. Further- more, note that if λ ξ max θ † −θ μ − √ ε ′ 2 ≤n, the lower bound in Theorem 5.2 becomes vacuous. There- fore, we should assume thatπ † andμare far enough, or that the size of theDis small, for this bound to be meaningful. This assumption is not restrictive, as in practice, the nature ofπ † often differs significantly fromμ, leading to large divergence terms. 7 Related Work Adversarial attacks in machine learning (ML). The problem of adversarial attacks in ML has a long history [Szegedy et al., 2013, Biggio et al., 2013, Nguyen et al., 2015, Papernot et al., 2017, Biggio et al., 2012, Li et al., 2016, Xiao et al., 2012], where various types of attacks have been considered, including training-time attacks, test-time attacks, and backdoor attacks. The focus of the present study is on training-time attacks. The closest to our work in this domain is that of Liu and Zhu [2016], who consider the teaching problem (via data synthesis) to various types of learners, including logistic regression learners. Similar to [Liu and Zhu, 2016], we also consider logistic regression in our op- timization problems. However, our attack problems include additional constraints, which necessitate the usage of additional technical machinery. Nika, N ̈other, Mandal, Kamalaruban, Singla and Radanovi ́c Data poisoning attacks and defenses in (multi- agent) reinforcement learning ((MA)RL).Ad- versarial attacks in RL have been explored extensively in the literature [Huang et al., 2017, Gleave et al., 2020, Lin et al., 2017, Sun et al., 2020, Rangi et al., 2022b, Ma et al., 2019, Rakhsha et al., 2020a, 2021], including training-time attacks [Rakhsha et al., 2020b, Xu et al., 2021], test-time attacks [Behzadan and Munir, 2017, Huang et al., 2017, Kos and Song, 2017, Sun et al., 2020], backdoor attacks [Kiourti et al., 2020, Wang et al., 2021, Yang et al., 2019] and attacks to MARL systems [Wu et al., 2024, Nika et al., 2024c, Moham- madi et al., 2023, Nika et al., 2024b]. Our research focuses on training-time poisoning attacks against sin- gle agents, where adversaries manipulate training data within certain constraints [Mei and Zhu, 2015, Xiao et al., 2015, Rakhsha et al., 2020a, 2021]. In the un- regularized RLHF setting, our attack problem utilizes constraints that determine the target policy’s strict optimality as in [Rakhsha et al., 2021]. Different from these works, our focus is on the studying attacks in RLHF. Complementing this, significant research has also been conducted on robust RL methods designed to defend against poisoning attacks [Zhang et al., 2021, Lykouris et al., 2021, Kumar et al., 2021, Rangi et al., 2022a, Wu et al., 2022, Zhang et al., 2022, McMahan et al., 2024, Banihashem et al., 2023, Nika et al., 2023]. Our work diverges from these studies by being the first to theoretically investigate the inherent robustness of RLHF and DPO paradigms against poisoning attacks. Data poisoning attacks and defenses in learn- ing from human preferences.Recent studies have empirically explored the vulnerability of the RLHF paradigm to poisoning attacks [Wang et al., 2023b, Shi et al., 2023, Rando and Tram`er, 2023, Baumg ̈artner et al., 2024], addressing various attack types such as la- bel flipping, backdoor, and data augmentation. Despite these empirical explorations, prior work has primarily focused on evaluating the effectiveness of these attacks, whereas our research aims to provide a theoretical un- derstanding of these vulnerabilities. On the defense side, Mandal et al. [2024] and Chowdhury et al. [2024] have proposed robust RLHF and DPO algorithms to handle data corruption. However, our work aims to understand the natural robustness of these algorithms against structured data poisoning attacks and studies the problem from an attacker’s perspective. Theoretical analysis of learning from human preferences.Significant research has focused on the- oretically understanding and improving the perfor- mance of RLHF and DPO [Zhu et al., 2023, Zhan et al., 2023, An et al., 2023, Azar et al., 2023, Wang et al., 2023a, Hejna et al., 2023, Nika et al., 2024a]. While in [Zhu et al., 2023, Zhan et al., 2023] the focus is on unregularized RLHF, Azar et al. [2023], Hejna et al. [2023], Nika et al. [2024a] study regularized RLHF and the effect of regularization. Our work also tries to further theoretical understanding of learning from human preferences, by undertaking a rigorous analysis of data poisoning attacks on these methods. 8 Concluding Discussion We considered data poisoning attacks in learning from human preferences. Specifically, we studied data augmentation attacks on RLHF and DPO. Based on our findings, we compared these paradigms in terms of susceptibility to attacks. There are several directions for future work. First, it would be interesting to relax the (log)linearity assumptions and solve the problem for general parametrizations. It is currently not clear whether RLHF and DPO attacks are feasible for general formulations. Second, as it is not possible to obtain closed-form solutions to our problems whenever KL constraints are present, it would be useful to study this attack framework with alternate constraints, such as total variation distance. Third, it would also be important to study other forms of attacks, e.g., label-flipping attackswhere the attacker is only allowed to flip a fraction of the preference labels in the dataset. Finally, it would be interesting to study attacks against more recent preference-based RL methods and understand the effectiveness of these attacks when a learner uses robust variants of these methods. Acknowledgements The work of Andi Nika and Goran Radanovic was funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – project number 467367360. References Gaon An, Junhyeok Lee, Xingdong Zuo, Norio Kosaka, Kyung-Min Kim, and Hyun Oh Song.Direct Preference-based Policy Optimization without Re- ward Modeling. InNeurIPS, 2023. Mohammad Gheshlaghi Azar, Mark Rowland, Bilal Piot, Daniel Guo, Daniele Calandriello, Michal Valko, and R ́emi Munos. A General Theoretical Paradigm to Understand Learning from Human Preferences. CoRR, abs/2310.12036, 2023. Yuntao Bai et al. Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback.CoRR, abs/2204.05862, 2022. Policy Teaching in Learning from Human Preferences Kiarash Banihashem, Adish Singla, and Goran Radanovic. Defense Against Reward Poisoning At- tacks in Reinforcement Learning.TMLR, 2023. Tim Baumg ̈artner, Yang Gao, Dana Alon, and Don- ald Metzler.Best-of-Venom: Attacking RLHF by Injecting Poisoned Preference Data.CoRR, abs/2404.05530, 2024. Vahid Behzadan and Arslan Munir. Whatever does not Kill Deep Reinforcement Learning, Makes it Stronger. CoRR, abs/1712.09344, 2017. Battista Biggio, Blaine Nelson, and Pavel Laskov. Poi- soning Attacks against Support Vector Machines. In ICML, 2012. Battista Biggio et al. Evasion Attacks Against Machine Learning at Test Time. InECML PKDD, 2013. Ralph Allan Bradley and Milton E Terry. Rank Analy- sis of Incomplete Block Designs: I. The Method of Paired Comparisons.Biometrika, 39(3/4), 1952. Daniel S. Brown, Wonjoon Goo, Prabhat Nagara- jan, and Scott Niekum. Extrapolating Beyond Sub- optimal Demonstrations via Inverse Reinforcement Learning from Observations. InICML, 2019. Sayak Ray Chowdhury, Anush Kini, and Nagara- jan Natarajan. Provably Robust DPO: Aligning Language Models with Noisy Feedback.CoRR, abs/2403.00409, 2024. Leo Gao, John Schulman, and Jacob Hilton. Scaling Laws for Reward Model Overoptimization. InICML, 2023. Amelia Glaese, Nat McAleese, Maja Trkebacz, John Aslanides, Vlad Firoiu, Timo Ewalds, Maribeth Rauh, Laura Weidinger, Martin Chadwick, Phoebe Thacker, et al. Improving Alignment of Dialogue Agents via Targeted Human Judgements.CoRR, abs/2209.14375, 2022. Adam Gleave, Michael Dennis, Cody Wild, Neel Kant, Sergey Levine, and Stuart Russell. Adversarial Poli- cies: Attacking Deep Reinforcement Learning. In ICLR, 2020. Joey Hejna, Rafael Rafailov, Harshit Sikchi, Chelsea Finn, Scott Niekum, W Bradley Knox, and Dorsa Sadigh.Contrastive Prefence Learning: Learn- ing from Human Feedback without RL.CoRR, abs/2310.13639, 2023. Abdolhossein Hoorfar and Mehdi Hassani. Inequali- ties on the Lambert W Function and Hyperpower Function.J. Inequal. Pure and Appl. Math, 9(2):5–9, 2008. Sandy Huang, Nicolas Papernot, Ian Goodfellow, Yan Duan, and Pieter Abbeel. Adversarial Attacks on Neural Network Policies.CoRR, abs/1702.02284, 2017. Panagiota Kiourti, Kacper Wardega, Susmit Jha, and Wenchao Li. Trojdrl: Evaluation of Back- door Attacks on Deep Reinforcement Learning. In ACM/IEEE (DAC), 2020. Jernej Kos and Dawn Song. Delving into Adversarial Attacks on Deep Policies.CoRR, abs/1705.06452, 2017. Aounon Kumar, Alexander Levine, and Soheil Feizi. Policy Smoothing for Provably Robust Reinforce- ment Rearning.CoRR, abs/2106.11420, 2021. Bo Li, Yining Wang, Aarti Singh, and Yevgeniy Vorob- eychik. Data Poisoning Attacks on Factorization- based Collaborative Filtering. InNeurIPS, 2016. Yen-Chen Lin, Zhang-Wei Hong, Yuan-Hong Liao, Meng-Li Shih, Ming-Yu Liu, and Min Sun. Tac- tics of Adversarial Attack on Deep Reinforcement Learning Agents. InIJCAI, 2017. Ji Liu and Xiaojin Zhu. The Teaching Dimension of Linear Learners.Journal of Machine Learning Resesearch, 17:162:1–162:25, 2016. Thodoris Lykouris, Max Simchowitz, Alex Slivkins, and Wen Sun. Corruption-robust Exploration in Episodic Reinforcement Learning. InCOLT, 2021. Yuzhe Ma, Xuezhou Zhang, Wen Sun, and Jerry Zhu. Policy Poisoning in Batch Reinforcement Learning and Control. InNeurIPS, 2019. Debmalya Mandal, Andi Nika, Parameswaran Ka- malaruban, Adish Singla, and Goran Radanovi ́c. Cor- ruption Robust Offline Reinforcement Learning with Human Feedback.CoRR, abs/2402.06734, 2024. Jeremy McMahan, Young Wu, Xiaojin Zhu, and Qiaomin Xie. Optimal Attack and Defense for Rein- forcement Learning. InAAAI, 2024. Shike Mei and Xiaojin Zhu. Using Machine Teaching to Identify Optimal Training-set Attacks on Machine Learners. InAAAI, 2015. Jacob Menick et al. Teaching Language Models to Support Answers with Verified Quotes.CoRR, abs/2203.11147, 2022. Mohammad Mohammadi, Jonathan N ̈other, Debmalya Mandal, Adish Singla, and Goran Radanovic. Im- plicit Poisoning Attacks in Two-agent Reinforcement Learning: Adversarial Policies for Training-time At- tacks. InAAMAS, 2023. Ofir Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans.Bridging the Gap Between Value and Policy based Reinforcement Learning. In NeurIPS, 2017. Anh Nguyen, Jason Yosinski, and Jeff Clune. Deep Neural Networks are Easily Fooled: High Confidence Predictions for Unrecognizable Images. InCVPR, 2015. Nika, N ̈other, Mandal, Kamalaruban, Singla and Radanovi ́c Andi Nika, Adish Singla, and Goran Radanovic. On- line Defense Strategies for Reinforcement Learning Against Adaptive Reward Poisoning. InAISTATS, 2023. Andi Nika, Debmalya Mandal, Parameswaran Ka- malaruban, Georgios Tzannetos, Goran Radanovi ́c, and Adish Singla. Reward Model Learning vs. Direct Policy Optimization: A Comparative Analysis of Learning from Human Preferences. InICML, 2024a. Andi Nika, Debmalya Mandal, Adish Singla, and Goran Radanovic. Corruption-robust Offline Two-player Zero-sum Markov Games. InAISTATS, pages 1243– 1251. PMLR, 2024b. Andi Nika, Jonathan N ̈other, Adish Singla, and Goran Radanovic. Defending Against Unknown Corrupted Agents: Reinforcement Learning of Adversarially Robust Nash Equilibria.TMLR, 2024c. Long Ouyang et al. Training Language Models to Fol- low Instructions with Human Feedback. InNeurIPS, 2022. Nicolas Papernot, Patrick McDaniel, Ian Goodfellow, Somesh Jha, Z Berkay Celik, and Ananthram Swami. Practical Black-box Attacks Against Machine Learn- ing. InACM, 2017. Rafael Rafailov, Archit Sharma, Eric Mitchell, Christo- pher D. Manning, Stefano Ermon, and Chelsea Finn. Direct Preference Optimization: Your Language Model is Secretly a Reward Model. InNeurIPS, 2023. Amin Rakhsha, Goran Radanovic, Rati Devidze, Xi- aojin Zhu, and Adish Singla. Policy Teaching via Environment Poisoning: Training-time Adversarial Attacks against Reinforcement Learning. InICML, 2020a. Amin Rakhsha, Goran Radanovic, Rati Devidze, Xi- aojin Zhu, and Adish Singla. Policy Teaching via Environment poisoning: Training-time Adversarial Attacks Against Reinforcement Learning. InICML, 2020b. Amin Rakhsha, Goran Radanovic, Rati Devidze, Xi- aojin Zhu, and Adish Singla. Policy Teaching in Reinforcement Learning via Environment Poisoning attacks.Journal of Machine Learning Research, 22: 210:1–210:45, 2021. Javier Rando and Florian Tram`er. Universal Jailbreak Backdoors from Poisoned Human Feedback. InICLR, 2023. Anshuka Rangi, Long Tran-Thanh, Haifeng Xu, and Massimo Franceschetti. Saving Stochastic Bandits from Poisoning Attacks via Limited Data Verification. InAAAI, 2022a. Anshuka Rangi, Haifeng Xu, Long Tran-Thanh, and Massimo Franceschetti. Understanding the Limits of Poisoning Attacks in Episodic Reinforcement Learn- ing. InIJCAI, 2022b. Jiawen Shi, Yixin Liu, Pan Zhou, and Lichao Sun. Badgpt: Exploring Security Vulnerabilities of Chat- GPT via Backdoor Attacks to InstructGPT.CoRR, abs/2304.12298, 2023. Daniel Shin, Anca D. Dragan, and Daniel S. Brown. Benchmarks and Algorithms for Offline Preference- Based Reward Learning.Transactions of Machine Learning Research, 2023. Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul F Christiano. Learning to Summarize with Human Feedback. InNeurIPS, 2020. Jianwen Sun, Tianwei Zhang, Xiaofei Xie, Lei Ma, Yan Zheng, Kangjie Chen, and Yang Liu. Stealthy and Efficient Adversarial Attacks Against Deep Re- inforcement Learning. InAAAI, 2020. Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus. Intriguing Properties of Neural Net- works.CoRR, abs/1312.6199, 2013. Chaoqi Wang, Yibo Jiang, Chenghao Yang, Han Liu, and Yuxin Chen. Beyond Reverse KL: Generalizing Direct Preference Optimization with Diverse Diver- gence Constraints.CoRR, abs/2309.16240, 2023a. Jiongxiao Wang, Junlin Wu, Muhao Chen, Yevgeniy Vorobeychik, and Chaowei Xiao. On the Exploitabil- ity of Reinforcement Learning with Human Feedback for Large Language Models.CoRR, abs/2311.09641, 2023b. Yue Wang, Esha Sarkar, Wenqing Li, Michail Mani- atakos, and Saif Eddin Jabari. Stop-and-go: Ex- ploring Backdoor Attacks on Deep Reinforcement Learning-based Traffic Congestion Control Systems. IEEE Transactions on Information Forensics and Security, 16, 2021. Fan Wu, Linyi Li, Chejian Xu, Huan Zhang, Bhavya Kailkhura, Krishnaram Kenthapadi, Ding Zhao, and Bo Li. Copa: Certifying Robust Policies for Offline Reinforcement Learning against Poisoning Attacks. CoRR, abs/2203.08398, 2022. Young Wu, Jeremy McMahan, Xiaojin Zhu, and Qiaomin Xie. Data Poisoning to Fake a Nash Equi- libria for Markov Games. InAAAI, 2024. Han Xiao, Huang Xiao, and Claudia Eckert. Adversar- ial Label Flips Attack on Support Vector Machines. InECAI, 2012. Policy Teaching in Learning from Human Preferences Huang Xiao, Battista Biggio, Gavin Brown, Giorgio Fumera, Claudia Eckert, and Fabio Roli. Is Feature Selection Secure Against Training Data Poisoning? InICML, 2015. Hang Xu, Rundong Wang, Lev Raizman, and Zinovi Rabinovich. Transferable Environment Poisoning: Training-time Attack on Reinforcement Learning. In ICAAMS, 2021. Zhaoyuan Yang, Naresh Iyer, Johan Reimann, and Nurali Virani. Design of Intentional Backdoors in Sequential Models.CoRR, abs1902.09972, 2019. Wenhao Zhan, Masatoshi Uehara, Nathan Kallus, Ja- son D Lee, and Wen Sun. Provable Offline Rein- forcement Learning with Human Feedback.CoRR, abs/:2305.14816, 2023. Xuezhou Zhang, Yiding Chen, Xiaojin Zhu, and Wen Sun. Robust Policy Gradient Against Strong Data Corruption. InICML, 2021. Xuezhou Zhang, Yiding Chen, Xiaojin Zhu, and Wen Sun. Corruption-robust Offline Reinforcement Learn- ing. InAISTATS, 2022. Banghua Zhu, Michael I. Jordan, and Jiantao Jiao. Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons. In ICML, 2023. Daniel M Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B Brown, Alec Radford, Dario Amodei, Paul Chris- tiano, and Geoffrey Irving.Fine-tuning Lan- guage Models from Human Preferences.CoRR, abs/1909.08593, 2019. Nika, N ̈other, Mandal, Kamalaruban, Singla and Radanovi ́c Appendix Table of Contents A Feasibility of Problem P:Attack:RLHF.1.13 B Proofs of Section 416 B.1 Unregularized RLHF with Nonempty Existing Data . . . . . . . . . . . . . . . . . . . . . . . . 16 B.2 Unregularized RLHF with Empty Existing Data. . . . . . . . . . . . . . . . . . . . . . . . . . . 19 B.3 Regularized RLHF with Non-empty Existing Data . . . . . . . . . . . . . . . . . . . . . . . . . 21 C Proofs of Section 527 C.1 DPO with Non-empty Existing Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 C.2 DPO with Empty Existing Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 D Proofs of Section 633 E Technical Lemmas33 A Feasibility of Problem P:Attack:RLHF.1. In this section, we prove that Problem P:Attack:RLHF.1 is feasible for certain classes ofπ † . Theorem A.1.Letε,β >0andμbe with full support. Then, the following statements hold: •Letπ † ∈Π det and assume thatω † opt is such thatπ † isε-robust optimal with respect tor ω † opt . Then, there exists c >0such thatc·ω † opt is a feasible solution for Problem P:Attack:RLHF.1. •Letπ † ,μ∈Π log and assume that the column space ofΦis a subspace of the column space ofΨ. Then the solution toΦω=β(logbπ † −logμ), wherelogbπ † −logμis the vector with entrieslogbπ † (a|s)−logμ(a|s), for each(s,a), is a feasible solution for Problem P:Attack:RLHF.1, for anybπ † such thatD KL (π † ||bπ † )≤ε ′ . Proof.We start with the first statement. Given datasetD, logistic regression applied onDreturns a reward functionr. IfDis to be feasible for Problem P:Attack:RLHF.1, this necessitates that the optimal regularized policyπ reg r with respect to reward functionrisε-close toπ † in the sense that π † −π reg r 1 ≤ε . Note that, if we can show that π † −π reg r ∞ ≤ε, then we are done. Thus, for the rest of this proof, we will focus on∥·∥ ∞ . Now, given reward functionrwith parameterω, Theorem E.15 shows us that we can always synthesise a dataset Dthat makesrthe outcome when logistic regression is applied on it. Therefore, we focus our attention on finding the right reward functionrfor which our constraint is satisfied. Note that our problem can be written as arg max π V π r (ρ)−βD γ KL (π||μ) :=π reg r s.t. π † −π reg r ∞ ≤ε , where D γ KL (π||μ) =E X t≥0 γ t log π(a t |s t ) μ(a t |s t ) ρ,π Policy Teaching in Learning from Human Preferences =E X t≥0 γ t X a π(a|s t ) log π(a|s t ) μ(a|s t ) ρ,π =E X t≥0 γ t D KL (π(·|s t )||μ(·|s t )) ρ,π .(1) Givenκ << ε, let us define the set Π κ =(1−κ)·π+κ·u|π∈Π, whereudenotes the policy that takes any action uniformly at random, at any given state. Furthermore, letl=min π,s d π ρ (s). By the ergodicity assumption, we have thatl >0. LetA π ρ (s,a) denote the advantage function ofπat state-action (s,a). By assumption, there exists anω † such thatM ⊤ π † ω † ≥ε, for a givenε. Obviously, the policyπ † is optimal with respect to the reward functionr ω † . We will use the short-hand notationr † =r ω † . Now, let us define ∆>0 such thatA π † (s,a)≤−∆, for alla̸=π † (s), letc >0 be an arbitrary positive constant and letr † max denote the maximum component ofr † . Letπ 1 = (1−κ)·π † +κ·u. For any policyπ, we have V π 1 c·r † (ρ)−V π c·r † (ρ) = V π 1 c·r † (ρ)−V π † c·r † (ρ) + V π † c·r † (ρ)−V π c·r † (ρ) . We will bound each term separately. First, using vector notation for the reward and occupancy measures, note that V π 1 c·r † (ρ)−V π † c·r † (ρ) =c· d π 1 ρ −d π † ρ ⊤ r † (2) ≥−c· d π 1 ρ −d π † ρ 1 · r † ∞ (3) ≥− γ·c·κ·r † max 1−γ ,(4) where Equation 2 uses the occupancy measure expression of the discounted return; Equation 3 uses Cauchy- Schwarz; for Equation 4 we have used that π 1 −π † 1 =κand thatsimilar policies imply similar state visitations, i.e., if∥π 1 −π 2 ∥ 1 ≤ζ, then d π 1 ρ −d π 2 ρ 1 ≤ζγ/ (1−γ), for given positiveζ(see the RL Theory book Lemma 14.1). For the second term, we have V π † c·r † (ρ)−V π c·r † (ρ) =− V π c·r † (ρ)−V π † c·r † (ρ) =− X s ′ d π ρ (s ′ ) X a ′ π(a ′ |s ′ )A π † c·r † (s ′ ,a ′ ) ! (5) =− X s ′ d π ρ (s ′ ) X a ′ ̸=π † (s ′ ) π(a ′ |s ′ )A π † c·r † (s ′ ,a ′ ) (6) = X s ′ d π ρ (s ′ ) X a ′ ̸=π † (s ′ ) π(a ′ |s ′ )· −A π † c·r † (s ′ ,a ′ ) ≥ X s ′ d π ρ (s ′ ) X a ′ ̸=π † (s ′ ) π(a ′ |s ′ )·c·∆(7) ≥l· X s ′ ,a ′ ̸=π † (s ′ ) π(a ′ |s ′ )·c·∆,(8) where Equation 5 follows from the Performance Difference Lemma; Equation 6 uses the fact thatA π † c·r † (s,π † (s)) = c·A π † r † (s,π † (s)) = 0; Equation 7 uses the fact thatA π † c·r † (s,π † (s))≤−c·∆; Equation 8 uses the definition ofl. Now, let us define the set Π ε κ = π∈Π κ : π−π † ∞ ≤ε . Equation 8 above implies that, for anyπ̸∈Π ε κ , V π † c·r † (ρ)−V π c·r † (ρ)≥l· X s ′ ,a ′ ̸=π † (s ′ ) π(a ′ |s ′ )·c·∆ Nika, N ̈other, Mandal, Kamalaruban, Singla and Radanovi ́c ≥l·max s,a̸=π † (s) π(a|s)·c·∆ > l·ε·c·∆,(9) where the third inequality follows from the fact that π−π † ∞ > ε . Thus, combining Equation 4 and Equation 9 into the original suboptimality gap, forπ̸∈Π ε κ , we obtain V π 1 c·r † (ρ)−V π c·r † (ρ)> l·ε·c·∆− γ·c·κ·r † max 1−γ .(10) Now, for a givenκ >0, the existsC κ >0, such thatD γ KL (π 1 ||μ)< C κ , since bothπ 1 andμhave full support and thusD γ KL (π 1 ||μ)≤(1/(1−γ)) max s D KL (π 1 (·|s)||μ(·|s)) :=C κ . Hence, we have that max π∈Π ε κ V π c·r † −βD γ KL (π||μ)≥V π 1 c·r † −β·C κ . Moreover, using the fact thatD γ KL (π||μ)≥0, we also have max π∈Π ε κ V π c·r † −βD γ KL (π||μ)≤max π∈Π ε κ V π c·r † < V π 1 c·r † (ρ)−c· l·ε·∆− γ·κ·r † max 1−γ , where the second inequality follows from Equation 10. Finally, letκ << l·ε·(1−γ)/(γ·r † max ) andc= β·C κ /(l·ε−(γ/(1−γ))·κ·r † max ). Then, we obtain max π∈Π ε κ V π c·r † −βD γ KL (π||μ)≥V π 1 c·r † −β·C κ =V π 1 c·r † −c· l·ε·∆− γ·κ·r † max 1−γ >max π̸∈Π ε κ V π c·r † (ρ)−β·D γ KL (π||μ). Hence, we conclude that, for the choice ofr=c·r † (and thusω=c·ω † ), the solution to the regularized value maximization problem is necessarily in Π ε κ , and thus,ε-close toπ † . Next, we consider the second statement. Letr=β(logπ † −logμ). Note that we have arg max π V π r (ρ)−βD γ KL (π||μ) =E X t≥0 γ t r(s t ,a t )−βlog π(a t |s t ) μ(a t |s t ) π,ρ = arg max π E X t≥0 γ t βlog π † (a t |s t ) μ(a t |s t ) −βlog π(a t |s t ) μ(a t |s t ) π,ρ = arg max π E X t≥0 γ t βlog π † (a t |s t ) π(a t |s t ) π,ρ = arg max π −E X t≥0 γ t βlog π(a t |s t ) π † (a t |s t ) π,ρ = arg min π D γ KL π||π † =π † . This implies that, as long as we can find a reward function as proposed, enforcingπ † is feasible. Sinceπ † ,μ∈Π log , there exist parametersθ † ,θ μ that realize these policies in the loglinear space. Thus, to find a linear reward function that satisfies our equation, we can equivalently solve Φω=β·Ψ θ † −θ μ , which would automatically be a solution. Lemma 4.1 of [Nika et al., 2024a] guarantees that we can find such a vectorωwhenever the column space of Φ is a subspace of the column space of Ψ. By assumption, this condition is satisfied, and thus there existsbωfor which we haver bω =β(logπ † −logμ). Policy Teaching in Learning from Human Preferences B Proofs of Section 4 In this section, we provide the full proofs of results from Section 4. B.1 Unregularized RLHF with Nonempty Existing Data We begin with the unregularized setting when the pre-existing data is non-empty and prove the following result. Theorem 4.1.LetDbe a given preference dataset ofnsamples, letβ= 0,ε ′ >0andπ † ∈Π det . Furthermore, letωbe optimal forℓ ω RLHF ( D), defineω † as proj ω:M π † ω≥ε ′ (ω) =ω+M π † M ⊤ π † M π † + (ε ′ −M π † ω) and letγ≥1−2 ω † /(ξ max + 1). Then, the dataset of l (ω † ) ⊤ ∇ ω ℓ ω † RLHF ( D) /ξ max m identical samples satisfying o= 1and φ(τ)−φ(τ ′ ) =ξ 1 ω † ⊤ ∇ ω ℓ ω † RLHF ( D) ω † ∥ω † ∥ 2 , is a feasible solution to Problem P:Attack:RLHF.1. Furthermore, there exists an optimal solution b Dfor Problem P:Attack:RLHF.1 withbn RLHF identical samples such that bn RLHF ≤ & 2n+λ ξ max (ε ′ ) 2 SA σ 2 min (M π † ) +∥ω∥ ε ′ √ SA σ min (M π † ) !' . Proof. Lemma E.3 implies that any feasible solution to Problem P:Attack:RLHF.2 is feasible for Problem P:Attack:RLHF.1. Thus, we focus on Problem P:Attack:RLHF.2. First, note that the conditionγ≥1−2 ω † / (ξ max + 1) is needed to ensure a well-defined feature construction for our dataset, based on the condition provided by Lemma E.10. Now, let us consider the simpler problem of augmenting the data so that the solution to the logistic regression subproblem is a givenbω. The subproblem can be written as min D |D| s.tbω= arg min ω X (τ,τ ′ ,o)∈D∪D log 1 + exp −o·ω ⊤ (φ(τ)−φ(τ ′ )) + λ 2 ∥ω∥ 2 . Lemma E.6 implies that the solution to the above is the dataset of & (bω) ⊤ ∇ ω ℓ bω RLHF ( D) ξ max ' identical samples satisfying φ(τ j )−φ(τ ′ j ) =ξ −1 (bω) ⊤ ∇ ω ℓ bω RLHF (D) & (bω) ⊤ ∇ ω ℓ bω RLHF ( D) ξ max ' −1 ∇ ω ℓ bω RLHF (D) (bω) ⊤ ∇ ω ℓ ω † RLHF ( D) ,o j = 1. Given this solution, we can equivalently write Problem Equation P:Attack:RLHF.2 in terms ofωas min ω ω ⊤ ∇ ω ℓ ω † RLHF (D) s.t.ε−M ⊤ π † ω≤0. Now, before we go any further, it is important to note that, whenever we have ∇ ω ℓ ω † RLHF ( D) =0, Nika, N ̈other, Mandal, Kamalaruban, Singla and Radanovi ́c the number of samples needed for the attack to succeed is 0 sinceω † is already optimal with respect toD. Recall that Σ φ D = 1 n X (τ,τ ′ )∈D (φ(τ)−φ(τ ′ )) (φ(τ)−φ(τ ′ )) ⊤ denotes the sample covariance matrix with respect toDand letC φ D denote its minimum eigenvalue. We will rewrite the problem using a different notation for simplicity in calculations. First, let X ω D = X (τ,τ ′ ,o)∈ D −o(φ(τ)−φ(τ ′ )) 1 + exp (oω ⊤ (φ(τ)−φ(τ ′ ))) ,(11) and Y ω D =∇ ω (X ω D + 2λω)(12) = X (τ,τ ′ ,o)∈D exp(oω ⊤ (φ(τ)−φ(τ ′ )) (1 + exp(oω ⊤ (φ(τ)−φ(τ ′ ))) 2 (φ(τ)−φ(τ ′ )) (φ(τ)−φ(τ ′ )) ⊤ + 2λI .(13) Note that X ω D = X (τ,τ ′ ,o)∈ D −o(φ(τ)−φ(τ ′ )) 1 + exp (oω ⊤ (φ(τ)−φ(τ ′ ))) ≤ X (τ,τ ′ ,o)∈ D 1 1 + exp (oω ⊤ (φ(τ)−φ(τ ′ ))) ∥φ(τ)−φ(τ ′ )∥(14) ≤ X (τ,τ ′ ,o)∈ D (∥φ(τ)∥+∥φ(τ ′ )∥)(15) ≤ 2 n (1−γ) ,(16) where Equation 14 follows from the triangle inequality, while Equation 15 uses that fact that ∞ X t=0 γ t φ(s t ,a t ) ≤ ∞ X t=0 γ t ∥φ(s t ,a t )∥≤ 1 1−γ , by assumption, and the fact that 1/(1 +exp(x))≤1. Also, note that, for strictly positiveλ, the matrixY ω D is symmetric positive definite. To obtain further information about the spectrum ofY ω D , which we will use for solving our problem, we prove the following intermediate result. Going back to our optimization problem and using the above notation and result, the Lagrangian can be written as L(ω,α) = ω ⊤ X ω D +λω + (ε−M ⊤ π † ω) ⊤ α , and its gradient is ∇ ω L(ω,α) =e ω · X ω D +λω+∇ ω (X ω D +λω)ω −M π † α =e ω · X ω D +Y ω D ω −M π † α , where e ω = sgn ω ⊤ X ω D +λω is the sign of the quantity inside the brackets. Thus, the first-order condition implies ω † = (Y ω † D ) −1 e ω ·M π † α−X ω † D . Policy Teaching in Learning from Human Preferences Complementary slackness implies that eitherM ⊤ π † ω † =ε,orα=0. We consider the first case, since the goal of the attacker is to be able to enforceπ † , thus we cannot haveα= 0 since this would disregard the constraint altogether. IfM ⊤ π † ω † =ε, then this, together with the first-order condition, imply M ⊤ π † (Y ω † D ) −1 e ω ·M π † α−X ω † D =ε. Using this and Cauchy-Schwarz, we have ∥M π † ∥ (Y ω † D ) −1 e·M π † α−X ω † D ≥ M ⊤ π † (Y ω † D ) −1 e ω ·M π † α−X ω † D = √ SAε which yields ω † = (Y ω † D ) −1 e·M π † α−X ω † D ≥ √ SAε ∥M π † ∥ ≥ √ SAε σ max (M π † ) .(17) On the other hand, using again Cauchy-Schwarz on the complementary slackness condition, we get ω † ≤ √ SAε σ min (M π † ) . Next, we will provide an upper bound on the norm of the gradient ofω † with respect toD. Letωbe the optimal point with respect toDand letproj ω:M π † ω≥ε (ω)denote the projection ofωonto theε-robust optimality polytope. To derive the upper bound, we use the fact that the projection ofωonto the polytope is a feasible solution and thus provides an immediate upper bound. Note that ω † ⊤ X ω † D +λω † = ω † ⊤ ∇ ω ℓ ω † RLHF ( D) ≤ proj ω:M π † ω≥ε (ω) ⊤ ∇ ω ℓ proj ω:M π † ω≥ε ( ω) RLHF (D) ≤ proj ω:M π † ω≥ε ( ω) ∇ ω ℓ proj ω:M π † ω≥ε ( ω) RLHF (D) ≤(2 n+λ) proj ω:M π † ω≥ε (ω) proj ω:M π † ω≥ε (ω)−ω ,(18) where the second inequality uses Cauchy-Schwarz and the third inequality uses the fact that the loss is Lipschitz (see Lemma E.14). Now, to compute the projection, we solve the following problem: min ω 1 2 ∥ω−ω∥ 2 such thatM π † ω≥ε. The Lagrangian of this problem is L(ω,ν) = 1 2 ∥ω−ω∥ 2 −ν(M π † ω−ε), and the first order condition becomes ω− ω−M π † ν=0, which gives us ω=ω+M π † ν . Nika, N ̈other, Mandal, Kamalaruban, Singla and Radanovi ́c To computeνwe use complementary slackness to obtain M π † ( ω+M π † ν) =ε, which in turn gives us ν= M ⊤ π † M π † + (ε−M π † ω). Hence, we get proj ω:M π † ω≥ε (ω) =ω+M π † M ⊤ π † M π † + (ε−M π † ω).(19) We can upper bound the projection norm by using complementary slackness as: ε √ SA=∥M π † ( ω+M π † ν)∥≤∥M π † ∥ ω+M π † ν∥≤σ max (M π † ) proj ω:M π † ω≥ε ( ω) , and ε √ SA=∥M π † (ω+M π † ν)∥≥σ min (M π † )∥ω+M π † ν∥=σ min (M π † ) proj ω:M π † ω≥ε ( ω) , where we use the fact thatσ min (M)∥x∥ ≤ ∥Mx∥ ≤σ max (M)∥x∥. Using the overall case whenα= 0 and Equation 18, we have ω † ⊤ X ω † D +λω † ≤(2n+λ) proj ω:M π † ω≥ε (ω) proj ω:M π † ω≥ε (ω)−ω ≤(2n+λ) ε √ SA σ min (M π † ) ε √ SA σ min (M π † ) +∥ ω∥ ! ≤(2 n+λ) ε 2 SA σ 2 min (M π † ) +∥ω∥ ε √ SA σ min (M π † ) ! . Putting things together, we finally obtain bn RLHF ≤ & 2 n+λ ξ max ε 2 SA σ 2 min (M π † ) +∥ ω∥ ε √ SA σ min (M π † ) !' B.2 Unregularized RLHF with Empty Existing Data. Next, we consider the unregularized setting when the pre-existing dataset Dis empty. Corollary 4.1.LetD=∅,β= 0andε ′ >0, and letπ † ∈Π det . Defineω † =M π † M ⊤ π † M π † + ε ′ . Then, the dataset of λ ∥ ω † ∥ 2 ξ max identical samples satisfying φ(τ)−φ(τ ′ ) =ξ 1 λ ω † · ω † ∥ω † ∥ 2 , o= 1 is a feasible solution for Problem P:Attack:RLHF.1. Furthermore, there exists an optimal solution b Dfor Problem P:Attack:RLHF.1 withbn RLHF samples such that bn RLHF ≤ (ε ′ ) 2 λSA ξ max σ 2 min (M π † ) . Proof.Lemma E.3 implies that any feasible solution to Problem P:Attack:RLHF.2 is feasible for Problem P:Attack:RLHF.1. Thus, we focus on Problem P:Attack:RLHF.2. Policy Teaching in Learning from Human Preferences First, note that, forβ= 0 the optimal policy is deterministic. Now, givenω † ̸=0, Lemma E.6 implies that the solution to the problem min D |D| s.t.ω † = arg min ω X (τ,τ ′ ,o)∈D log 1 + exp −o·ω ⊤ (φ(τ)−φ(τ ′ )) + λ 2 ∥ω∥ 2 is the dataset of & λ ω † 2 ξ max ' identical samples satisfying φ(τ i )−φ(τ ′ i ) =ξ −1 λ ω † 2 & λ ω † 2 ξ max ' −1 ω † ∥ω † ∥ 2 , o i = 1. Since the optimal sample size to solve the logistic regression subproblem depends on the norm of the parameter ω † , then, by using the construction above we can directly minimize ω † and constrainω † to remain in the desired region. In this case, we can equivalently rewrite our original problem in terms ofωas min ω 1 2 ∥ω∥ 2 s.t. X s ′ d π † ρ (s ′ )φ(s ′ ,π † (s ′ ))− X s ′ d π † s,a ρ (s ′ )φ(s ′ ,π † s,a(s ′ )) ! ⊤ ω≥ε,∀s,a̸=π † (s). Using vector notation, we have min ω 1 2 ∥ω∥ 2 s.t.ε−M ⊤ π † ω≤0, whereε=ε1. This is a convex program and thus local minima are global. The Lagrangian of the above is L(ω,α) = 1 2 ∥ω∥ 2 +α ⊤ ε−M ⊤ π † ω , and setting its gradient to zero gives us ω † =M π † α . Complementary slackness implies M ⊤ π † ω † =ε, which, together with the first-order condition, imply M ⊤ π † M π † α=ε. Note that M ⊤ π † M π † = M π † M ⊤ π † ≤Tr M π † M ⊤ π † ≤2SA , due to the fact that X s ′ d π † ρ (s ′ )φ(s ′ ,π † (s ′ ))− X s ′ d π † s,a ρ (s ′ )φ(s ′ ,π † s,a(s ′ )) Nika, N ̈other, Mandal, Kamalaruban, Singla and Radanovi ́c ≤ X s ′ d π † ρ (s ′ )φ(s ′ ,π † (s ′ )) + X s ′ d π † s,a ρ (s ′ )φ(s ′ ,π † s,a(s ′ )) ≤ X s ′ d π † ρ (s ′ ) φ(s ′ ,π † (s ′ )) + X s ′ d π † s,a ρ (s ′ ) φ(s ′ ,π † s,a(s ′ )) ≤2, for every (s,a) pair. Thus, it follows that ω † ∥M π † ∥≥ M π † ω † = M ⊤ π † M π † α =∥ε∥=ε √ SA , and σ min (M π † ) ω † ≤ M π † ω † =ε √ SA . From this, we have ε √ SA σ max (M π † ) ≤ ω † ≤ ε √ SA σ min (M π † ) , which implies that bn RLHF ≤ ε 2 λSA ξ max σ 2 min (M π † ) . B.3 Regularized RLHF with Non-empty Existing Data In this section, we provide the full proof of the following result for the regularized setting. Theorem 4.2.LetDbe a given preference dataset ofnsamples,β >0and0< ε ′ ≤ε. Moreover, define Γ ω φ (π † ||π reg r ω ) = X s,a ρ(s)(π † (a|s)−π reg r ω (a|s))φ π reg r ω (s,a), for any givenω. Then, there exists a feasible solution b D for Problem P:Attack:RLHF.1 withbn RLHF samples which yieldsω † when solving Problem P:RLHF.Reward on dataset b D, such thatΓ ω φ (π † ||π reg r ω † )̸= 0and bn RLHF ≤O β 2 D KL π † ||μ −ε ′ 2 (1−γ) 2 σ 2 min (Σ φ D ) Γ ω † φ (π † ||π reg r ω † ) 2 + n (1−γ) 4 σ 4 min (Σ φ D ) ! . Proof. Letε ′ ≤ε. Lemma E.4 implies that any feasible solution to Problem P:Attack:RLHF.3 is feasible for Problem P:Attack:RLHF.1. Thus, we focus on Problem P:Attack:RLHF.3. First, let us recall the KL-regularized objective in this setting. Given learned rewardr, the objective is max π V π r (ρ) :=E s∼ρ,π " ∞ X t=0 γ t r(s t ,a t )−βlog π(a t |s t ) μ(a t |s t ) s 0 =s # . Let us use the shorthand notationV r (s),Q r (s,a) andA r (s,a) to denote the functionsV π reg r r (s),Q π reg r r (s,a) and A π reg r r (s,a), respectively. Similarly, for parametrized reward functionr ω , Let us use the short-hand notation V ω (s),Q ω (s,a),A ω (s,a) to denoteV π reg r ω r ω (s),Q π reg r ω r ω (s,a) andA π reg r ω r ω (s,a), respectively. Policy Teaching in Learning from Human Preferences Given rewardr, Lemma E.1 implies that the regularized optimal policy in this case can be written as π reg r (a|s) =μ(a|s) exp 1 β Q r (s,a)− 1 β V r (s) , withexp(V r (s)/β) as the partition constant, since it is action-independent. This implies the following relation between the two value functions holds: V r (s) =βlog X a μ(a|s) exp 1 β Q r (s,a) .(20) Now, note that the second constraint of Problem P:Attack:RLHF.3 can be written as D KL π † ||π reg r ω † = X s,a ρ(s)π † (a|s) log π † (a|s) π reg r ω † (a|s) = X s,a ρ(s)π † (a|s) log π † (a|s) μ(a|s) − 1 β Q ω † (s,a) + 1 β V ω † (s) =D KL (π † ||μ)− 1 β E s∼ρ,a∼π † (·|s) h A ω † (s,a) i . Thus, the attack optimization problem can be written as min D |D| s.tω † = arg min ω X (τ,τ ′ ,o)∈ D∪D log (1 + exp (−o·(φ(τ)−φ(τ ′ )))) + λ 2 ∥ω∥ 2 D KL (π † ||μ)− 1 β E s∼ρ,a∼π † (·|s) h A ω † (s,a) i −ε ′ ≤0. Lemma E.6 implies that the solution to the subproblem min D |D| s.tω † = arg min ω X (τ,τ ′ ,o)∈D∪D log (1 + exp (−o·(φ(τ)−φ(τ ′ )))) + λ 2 ∥ω∥ 2 is the dataset of & ∇ ω ℓ ω RLHF ( D) ⊤ ω † ξ max ' identical samples satisfying φ(τ)−φ(τ ′ ) =ξ −1 (ω † ) ⊤ ∇ ω ℓ ω RLHF ( D) | ∇ ω ℓ ω RLHF ( D) ⊤ ω † | ξ max ω † ∥ω † ∥ 2 , o= 1. Thus, we can equivalently write the original problem in terms ofωas min ω ω ⊤ ∇ ω ℓ ω RLHF ( D) s.t.D KL (π † ||μ)− 1 β E s∼ρ,a∼π † (·|s) [A ω (s,a)]−ε ′ ≤0, with Lagrangian L(ω,α) = ω ⊤ ∇ ω ℓ ω RLHF ( D) +α D KL (π † ||μ)− 1 β E s∼ρ,a∼π † (·|s) [A ω (s,a)]−ε ′ . Before we consider the first-order conditions of the problem, we rewrite the expected advantage function in the constraint and derive its gradient below. Nika, N ̈other, Mandal, Kamalaruban, Singla and Radanovi ́c Lemma B.1.Given anyω∈R d , let us define Γ π φ (s,a) =E " ∞ X t=0 γ t φ(s t ,a t )|a 0 =a,s 0 =s,π # ,(21) for any policyπand feature mappingφ, and let Γ π reg r ω φ π † ||π reg r ω =E s∼ρ,a∼π † (·|s) h Γ π reg r ω φ (s,a) i −E s∼ρ,a∼π reg r ω (·|s) h Γ π reg r ω φ (s,a) i .(22) Then, we have E s∼ρ,a∼π † (·|s) [A ω (s,a)] =ω ⊤ Γ π reg r ω φ π † ||π reg r ω , and ∇ ω A ω (s,a) = Γ π reg r ω φ (s,a)− X a ′ π reg r ω (a ′ |s)Γ π reg r ω φ (s,a ′ ). Proof. We start by deriving the gradient of the action-value function. Given reward functionr, policyπand trajectoryτ, let P π s (τ) =π(a 0 |s)P(s,a 0 ,s 1 )π(a 1 |s 1 )P(s 1 ,a 1 ,s 2 )π(a 2 |s 2 )... and P π s,a (τ) =P(s,a,s 1 )π(a 1 |s 1 )P(s 1 ,a 1 ,s 2 )π(a 2 |s 2 )... . Now, for any given state-action pair (s,a) and parameterω, observe that ∇ ω Q ω (s,a) =∇ ω r ω (s,a) +γ X s ′ P(s,a,s ′ )V ω (s ′ ) ! =φ(s,a) +γ X s ′ P(s,a,s ′ )β∇ ω log X a ′ μ(a ′ |s ′ ) exp 1 β Q ω (s ′ ,a ′ ) (23) =φ(s,a) +γβ X s ′ P(s,a,s ′ ) 1 P a ′ μ(a ′ |s ′ ) exp 1 β Q ω (s ′ ,a ′ ) X a ′ μ(a ′ |s ′ ) exp 1 β Q ω (s ′ ,a ′ ) · 1 β ∇ ω Q ω (s ′ ,a ′ ) =φ(s,a) +γ X s ′ P(s,a,a ′ ) X a ′ μ(a ′ |s ′ ) exp 1 β Q ω (s ′ ,a ′ ) exp 1 β V ω (s ′ ) ∇ ω Q ω (s ′ ,a ′ )(24) =φ(s,a) +γ X s ′ ,a ′ P(s,a,s ′ )π reg r ω (a ′ |s ′ )∇ ω Q ω (s ′ ,a ′ ) =E τ∼P π reg r ω s,a [φ(s,a)] +γE τ∼P π reg r ω s,a [φ(s ′ ,a ′ )] +...(25) =E τ∼P π reg r ω s,a " ∞ X t=0 γ t φ(s t ,a t ) # =E τ∼P π reg r ω s,a [φ(τ)] = Γ π reg r ω φ (s,a),(26) where Equation 23 and Equation 24 follow from Equation 20, while Equation 25 follows from recursion. Similarly, for the gradient of the advantage function, we have ∇ ω A ω (s,a) =∇ ω (Q ω (s,a)−V ω (s)) =E τ∼P π reg r ω s,a [φ(τ)]−∇ ω βlog X a ′ μ(a ′ |s) exp 1 β Q ω (s,a ′ ) 1 β E τ∼P π reg r ω s,a ′ [φ(τ)] Policy Teaching in Learning from Human Preferences =E τ∼P π reg r ω s,a [φ(τ)]−E τ∼P π reg r ω s [φ(τ)] = Γ π reg r ω φ (s,a)− X a ′ π reg r ω (a ′ |s)Γ π reg r ω φ (s,a ′ ), where, for the last equality, we have used the definition of the trajectory feature as a discounted sum of state-action feature vectors and rewritten the expectation. Now, let us use the short-hand notation Γ π reg r ω φ (s,a) by Γ ω φ (s,a), following our earlier convention, for brevity. For the final statement of our result, we rewrite the expected regularized advantage function with respect toπ † as E s∼ρ,a∼π † (·|s) [A ω (s,a)] =E s∼ρ,a∼π † (·|s) " Q ω (s,a)− X a ′ π reg r ω (a ′ |s)Q ω (s,a ′ ) # = X s,a ρ(s) π † (s|a)−π reg r ω (a|s) Q ω (s,a) = X s,a ρ(s) π † (s|a)−π reg r ω (a|s) E X t≥0 γ t ω ⊤ φ(s t ,a t )−βlog π reg r ω (a t |s t ) μ(a t |s t ) s 0 =s,a 0 =a,π reg r ω = X s,a ρ(s) π † (s|a)−π reg r ω (a|s) · ω ⊤ Γ ω φ (s,a)−E X t≥0 γ t βlog μ(a t |s t ) exp 1 β A ω (s t ,a t ) μ(a t |s t ) s 0 =s,a 0 =a,π reg r ω = X s,a ρ(s) π † (s|a)−π reg r ω (a|s) ω ⊤ Γ ω φ (s,a)−E X t≥0 γ t A ω (s t ,a t ) s 0 =s,a 0 =a,π reg r ω =ω ⊤ Γ ω φ π † ||π reg r ω − X s,a ρ(s) π † (s|a)−π reg r ω (a|s) E X t≥0 γ t X a π reg r ω (a|s t )A ω (s t ,a) s 0 =s,a 0 =a,π reg r ω =ω ⊤ Γ ω φ π † ||π reg r ω ,(27) where the Equation 27 follows from the fact that X a π(a|s)A π (s,a) = X a π(a|s)Q π (s,a)− X a π(a|s)Q π (s,a) = 0. Now, let us return to the proof of our main result. First, note that Lemma B.1 implies that the constraint can be written as D KL (π † ||μ)− 1 β ω ⊤ Γ ω φ (π † ||π reg r ω )−ε ′ ≤0. As in the proof of Lemma B.1, let us denote Γ π reg r ω φ (s,a) by Γ ω φ (s,a). Moreover, let us reuse some definitions from the proof of Theorem 4.1. Recall that X ω D = X (τ,τ ′ ,o)∈ D −o φ(τ)−φ(τ ′ ) 1 + exp oω ⊤ φ(τ)−φ(τ ′ ) , and Y ω D =∇ ω (X ω D + 2λω) Nika, N ̈other, Mandal, Kamalaruban, Singla and Radanovi ́c = X (τ,τ ′ ,o)∈D exp(oω ⊤ φ(τ)−φ(τ ′ ) 1 + exp(oω ⊤ φ(τ)−φ(τ ′ ) 2 φ(τ)−φ(τ ′ ) φ(τ)−φ(τ ′ ) ⊤ + 2λI . Then, we can equivalently write the Lagrangian as L(ω,α) = ω ⊤ X ω D +λω +α D KL (π † ||μ)− 1 β E s∼ρ,a∼π † (·|s) [A ω (s,a)]−ε ′ Using this notation, the first-order condition then implies ∇ ω L(ω,α) =e ω · X ω D +Y ω D ω − α β Γ ω φ π † ||π reg r ω =0, where e ω = sgn ω ⊤ X ω D +λω denotes the sign of the quantity inside the brackets. In the above, we have used the fact that E s∼ρ,a∼π † (·|s) [A ω (s,a)] =ω ⊤ Γ ω φ π † ||π reg r ω , from Lemma B.1. Assumingα̸= 0, we can write the primal solution in terms of the fixed-point equation ω= Y ω D −1 e ω α β Γ ω φ π † ||π reg r ω −X ω D .(28) Note that, if Γ bω φ π † ||π reg r ω =0, at the solution of the fixed-point Equation 28, then the primal condition for this case reduces to the following solution, for anyα: bω=− Y bω D −1 X bω D , in which case we obtain bn RLHF = (bω) ⊤ ∇ ω ℓ ω RLHF (D) = X bω D +λbω ⊤ Y bω D −1 X bω D = X bω D −λ Y bω D −1 X bω D ⊤ Y bω D −1 X bω D ≤ X bω D 2 Y bω D −1 I− Y bω D −1 ≤ 2 n 1−γ 2 1 nσ min (Σ φ D ) + 2λ (29) ≤O n (1−γ) 2 σ min Σ φ D ,(30) where Equation 29 follows from Equation 16 and Lemma E.12. Having taken care of this case, let us now assume that the solution to the fixed point equation implies Γ ω φ π † ||π reg r bω ̸ =0. Using Lemma B.1, complementary slackness corresponding to the KL constraint can be written as ω ⊤ Γ ω φ π † ||π reg r ω =β D KL π † ||μ −ε ′ . Using Equation 28 above and expanding, we obtain the following result: β D KL π † ||μ −ε ′ = Y ω D −1 e ω α β Γ ω φ π † ||π reg r ω −X ω D ⊤ Γ ω φ π † ||π reg r ω Policy Teaching in Learning from Human Preferences = e ω α β Γ ω φ π † ||π reg r ω − X ω D ⊤ Y ω D −1 ⊤ Γ ω φ π † ||π reg r ω = e ω α β Γ ω φ π † ||π reg r ω ⊤ Y ω D −1 Γ ω φ π † ||π reg r ω − X ω D ⊤ Y ω D −1 Γ ω φ π † ||π reg r ω . This further implies that α=e ω · β 2 D KL π † ||μ −ε ′ +β X ω D ⊤ Y ω D −1 Γ bω φ π † ||π reg r bω Γ bω φ (π † ||π reg r bω ) ⊤ Y ω D −1 Γ bω φ (π † ||π reg r bω ) , where we have used the fact thatY ω D is positive definite from Lemma E.12, so the denominator is well-defined for any non-zero Γ bω φ π † ||π reg r bω . Putting things together we get bω= Y ω D −1 · e bω · β D KL π † ||μ −ε ′ + X ω D ⊤ Γ bω φ,D π † ||π reg r bω Γ bω φ (π † ||π reg r bω ) ⊤ Γ bω φ,D (π † ||π reg r bω ) Γ bω φ π † ||π reg r bω −X ω D , where Γ bω φ,D π † ||π reg r bω = Y ω D −1 Γ bω φ π † ||π reg r bω . Note that, as long as we chooseγso that 1−γ≤ 2∥bω∥ ξ max + 1 , wherebωis the solution to the above fixed-point equation, then Lemma E.10 guarantees that the dataset construction formula satisfies the feature boundedness condition. We will now derive upper bounds on the norm of the parameterbωas given by the fixed-point equation above – we will use this bound later for the final result. Observe that ∥bω∥= Y bω D −1 e bω · β D KL π † ||μ −ε ′ + X bω D ⊤ Γ bω φ, D π † ||π reg r bω Γ bω φ (π † ||π reg r bω ) ⊤ Γ bω φ, D (π † ||π reg r bω ) Γ bω φ π † ||π reg r bω −X ω D ≤ Y bω D −1 e bω · β D KL π † ||μ −ε ′ + X bω D ⊤ Y bω D −1 Γ bω φ π † ||π reg r bω Γ bω φ (π † ||π reg r bω ) ⊤ Y bω D −1 Γ bω φ (π † ||π reg r bω ) Γ bω φ π † ||π reg r bω −X bω D (31) ≤ Y bω D −1 · β D KL π † ||μ −ε ′ + X bω D Y bω D −1 Γ bω φ π † ||π reg r bω Γ bω φ (π † ||π reg r bω ) 2 σ min Y bω D −1 Γ bω φ π † ||π reg r bω + X bω D (32) = β D KL π † ||μ −ε ′ Y bω D −1 Γ bω φ (π † ||π reg r bω ) σ min Y bω D −1 + X bω D (Y bω D ) −1 2 σ min Y bω D −1 + X bω D (Y bω D ) −1 (33) ≤ β D KL π † ||μ −ε ′ Y bω D −1 Γ bω φ (π † ||π reg r bω ) σ min Y bω D −1 + 2 n(n+ 2(1−γ)λ) 2 (1−γ) 2 ( n e C φ D C φ D + 2λ) 2 + 2n (1−γ)(n e C φ D C φ D + 2λ) (34) Nika, N ̈other, Mandal, Kamalaruban, Singla and Radanovi ́c ≤ β D KL π † ||μ −ε ′ Γ bω φ (π † ||π reg r bω ) O n+ 2(1−γ)λ (1−γ) nσ min (Σ φ D ) + 2λ +O n (1−γ)σ min (Σ φ D ) 2 (35) ≤O β D KL π † ||μ −ε ′ (1−γ)σ min (Σ φ D ) Γ bω φ (π † ||π reg r bω ) + n (1−γ)σ min (Σ φ D ) 2 ,(36) where Equation 31 follows from the Cauchy-Schwarz inequality; Equation 32 follows from the triangle inequality and Cauchy-Schwarz applied on the spectral norm; in Equation 33 we expand and cancel out equal terms; finally, for Equation 34 and Equation 35 we have used Equation 16, and Equation 51 and Equation 52 from the proof of Lemma E.12. Now, in order to obtain upper bounds, we need to deal with the term in the denominator, which depends on the optimal solutionbωitself. To address this, we will use a feasible solution to the problem. Now, letbπ † be a policy that is at mostε-close toπ † and that the solutionω † to Φω=βlog(bπ † −μ) yields Γ ω φ (π † ||π reg r ω † )̸= 0. Theorem A.1 shows thatω † makesbπ † optimal for the regularized problem, and thus,ω † is feasible. Using this, and the above derivations, we finally obtain: bn RLHF (D) = (bω) ⊤ ∇ ω ℓ bω RLHF (D) ≤∥bω∥ 2 +∥bω∥ X bω D ≤O β 2 D KL π † ||μ −ε 2 (1−γ) 2 σ 2 min (Σ φ D ) Γ ω † φ π † ||π reg r ω † 2 + n 2 (1−γ) 4 σ 4 min (Σ φ D ) , where the first inequality uses Cauchy-Schwarz and the last inequality uses Equation 16 and Equation 36. C Proofs of Section 5 In this section, we provide the full proofs of the results from Section 5. C.1 DPO with Non-empty Existing Data In this section, we provide the full proof of Theorem 5.1. Theorem 5.1.LetDbe a given preference dataset ofnsamples, letβ >0and0< ε ′ ≤ε/2. Furthermore, letθ be the optimal point forℓ θ DPO (D)and define e θ= proj θ:∥θ−θ † ∥≤ε ′ θ =θ † + (ε ′ ) 2 θ−θ † 2 θ−θ † . Then, the dataset b Dcontaining 2 l |(∇ θ ℓ e θ DPO (D)) ⊤ ( e θ−θ μ )|/(2ξ max ) m identical samples satisfying β e θ−θ μ ⊤ (ψ(s,a)−ψ(s,a ′ )) =o·ξ 2 ∇ θ ℓ e θ DPO ( D)) ⊤ e θ−θ μ , witho= 1for half the samples ando=−1for the remaining, is a feasible solution to Problem P:Attack:DPO.1. Furthermore, there exists an optimal solution b Dto Problem P:Attack:DPO.1 withbn DPO identical samples such that bn DPO ≤2· (nβ+λ) θ−θ † 2 −(ε ′ ) 2 2ξ max θ † −θ 3 θ † +∥θ μ ∥+ √ ε ′ . Policy Teaching in Learning from Human Preferences Proof.Lemma E.5 implies that, for anyε ′ ≤ε/2, any feasible solution for Problem P:Attack.DPO.2 is feasible for Problem P:Attack:DPO.1. Thus, we focus on Problem P:Attack.DPO.2. First, note that, sinceμis loglinear, Lemma E.8 implies that Problem Equation P:Attack.DPO.2 can be written as min D |D| s.t e θ= arg min θ X (s,a,a ′ ,o)∈ D∪D log 1 + exp −o·β(θ−θ μ ) ⊤ (ψ(s,a)−ψ(s,a ′ )) + λ 2 ∥θ−θ μ ∥ 2 e θ−θ † 2 ≤ε ′ . Given fixed e θ̸=0, Lemma E.7 implies that the solution to the subproblem min D |D| s.t e θ= arg min θ X (s,a,a ′ ,o)∈ D∪D log 1 + exp −o·β(θ−θ μ ) ⊤ (ψ(s,a)−ψ(s,a ′ )) + λ 2 ∥θ−θ μ ∥ 2 is the set of 2 (∇ θ ℓ θ † DPO (D)) ⊤ (θ † −θ μ ) 2ξ max identical samples satisfying β θ † −θ μ ⊤ (ψ(s,a)−ψ(s,a ′ )) =o·ξ −1 (∇ θ ℓ θ † DPO (D)) ⊤ θ † −θ μ 2 (∇ θ ℓ θ † DPO ( D)) ⊤ (θ † −θ μ ) 2ξ max , witho= 1 for half the samples ando=−1 for the remaining samples. Thus, the attack problem can be equivalently written in terms ofθas: min ∇ θ ℓ θ DPO (D) ⊤ (θ−θ μ ) s.t θ−θ † 2 ≤ε ′ . The Lagrangian of the above can be written as L(θ,α) = ∇ θ ℓ θ DPO ( D) ⊤ (θ−θ μ ) +α θ−θ † 2 −ε ′ , and the first-order condition is ∇ θ L(θ,α) =e θ · ∇ 2 θ ℓ θ DPO ( D) (θ−θ μ ) +∇ θ ℓ θ DPO (D) + 2α θ−θ † =0, where e θ = sgn ∇ θ ℓ θ DPO (D) ⊤ (θ−θ μ ) denotes the sign of the quantity inside the brackets. This yields θ ∗ = ∇ 2 θ ℓ θ ∗ DPO ( D) + 2αI −1 e θ ∗ ∇ 2 θ ℓ θ ∗ DPO (D)θ μ −e θ ∗ ∇ θ ℓ θ ∗ DPO (D) + 2αθ † , and θ ∗ −θ μ = ∇ 2 θ ℓ θ ∗ DPO (D) −1 2e θ ∗ α θ ∗ −θ † −∇ θ ℓ θ ∗ DPO (D) . Nika, N ̈other, Mandal, Kamalaruban, Singla and Radanovi ́c For non-zeroα, we use complementary slackness to obtain ∇ 2 θ ℓ θ ∗ DPO ( D) + 2αI −1 e θ ∗ ∇ 2 θ ℓ θ ∗ DPO ( D)θ μ −e θ ∗ ∇ θ ℓ θ ∗ DPO ( D) + 2αθ † −θ † 2 =ε ′ . Before we proceed any further, note that, since the Hessian of the loss is symmetric positive definite, then ∇ 2 θ ℓ θ ∗ DPO ( D) =UΣU , whereUis an orthonormal matrix and Σ is the diagonal matrix with the eigenvalues of the Hessian. Using the Woodbury inversion formula, we have ∇ 2 θ ℓ θ ∗ DPO (D) + 2αI −1 = 1 2α I− 1 4α 2 U Σ −1 + 1 2α U ⊤ UI −1 U = 1 2α I− 1 4α 2 U Σ −1 + 1 2α I −1 U = 1 2α (I−UΣ α U), where Σ α is a diagonal matrix with entriesσ i /(σ i + 2α), whereσ i are the entries of Σ, for every 1≤i≤d. Let M α =I−UΣ α U, and g=e θ ∗ ∇ 2 θ ℓ θ ∗ DPO ( D)θ μ −e θ ∗ ∇ θ ℓ θ ∗ DPO ( D). Then, we have 4α 2 ε ′ = (I−UΣ α U) e θ ∗ ∇ 2 θ ℓ θ ∗ DPO (D)θ μ −e θ ∗ ∇ θ ℓ θ ∗ DPO (D) + 2αθ † −2αθ † 2 = M α g+ 2α M α θ † −θ † 2 =∥M α g∥ 2 + 4α M α g,M α θ † −θ † + 4α 2 M α θ † −θ † 2 . We can write the above as a quadratic equation ofαas 4 M α θ † −θ † 2 −ε ′ α 2 + 4 M α g,M α θ † −θ † α+∥M α g∥ 2 = 0. Note that we are treating as constants some terms that involveαnon-linearly. This implies fixed-point solutions in terms ofα. We follow this route since we are only interested in the final bounds, which will be independent of such components. The discriminant of this equation is ∆ = 16∥M α g∥ 2 M α θ † −θ † 2 −16 M α θ † −θ † 2 −ε ′ ∥M α g∥ 2 = 16∥M α g∥ 2 ε ′ . This implies the following fixed-point equations: α 1,2 = − M α g,M α θ † −θ † ±∥M α g∥ √ ε ′ 2 ∥M α θ † −θ † ∥ 2 −ε ′ . Note that we have − M α g,M α θ † −θ † −∥M α g∥ √ ε ′ 2 ∥M α θ † −θ † ∥ 2 −ε ′ ≥ −∥M α g∥ M α θ † −θ † + √ ε ′ 2 ∥M α θ † −θ † ∥ 2 −ε ′ = ∥M α g∥ 2 √ ε ′ −∥M α θ † −θ † ∥ which, since the maximum eigenvalue ofM α is bounded by 1, is positive whenever M α θ † −θ † ≤2 θ † ≤ √ ε ′ . This condition would guarantee a positive root ofα, which is required asαis a Lagrange multiplier. If there is none, we do not take into consideration complementary slackness and solve forα= 0. For now, let us assume Policy Teaching in Learning from Human Preferences that there exists a positive root and consider theα= 0 case later. Since the final bounds do not depend on which of the solutions we pick, let us pick the one with +∥M α g∥ √ ε ′ without loss of generality. Plugging it into the first-order solution, we get θ ∗ = 1 2α M α g+ 2αθ † =M α θ † + 1 2α M α g=M α θ † + M α θ † −θ † 2 −ε ′ ∥M α g∥ √ ε ′ −⟨M α g,M α θ † −θ † ⟩ M α g .(37) This implies that ∥θ ∗ ∥≤ M α θ † + M α θ † −θ † 2 −ε ′ √ ε ′ −⟨M α g,M α θ † −θ † ⟩/∥M α g∥ ≤ M α θ † + M α θ † −θ † 2 −ε ′ √ ε ′ −∥M α θ † −θ † ∥ = M α θ † + M α θ † −θ † + √ ε ′ ≤ θ † + 2 θ † + √ ε ′ = 3 θ † + √ ε ′ , where we have used the triangle inequality, Cauchy Schwarz and the fact that the maximum eigenvalue ofM α is upper-bounded by 1. Now we provide upper bounds on the gradient with respect to the pre-existing data forθ ∗ , similar to the proof of Theorem 4.1. Letθbe the optimal parameter with respect to the loss on the pre-existing dataset. Note that we have ∇ θ ℓ θ ∗ DPO ( D) ≤(nβ+λ) θ ∗ −θ ≤(nβ+λ) θ ∗ −proj θ:∥θ−θ † ∥≤ε ′ θ + proj θ:∥θ−θ † ∥≤ε ′ θ −θ ≤( nβ+λ) ε ′ + proj θ:∥θ−θ † ∥≤ε ′ θ −θ , where the first inequality follows from Lemma E.14; the second inequality uses triangle inequality and the third inequality uses the fact that any two points in theε ′ -ball are no farther thanε ′ away from each-other. To compute the projection onto theε ′ -ball, we solve the following problem: min θ θ− θ 2 ,such that θ−θ † 2 ≤(ε ′ ) 2 . The first-order of the problem with respect to dual variableαof the Lagrangian L(θ,α) = θ− θ 2 +α θ−θ † 2 −(ε ′ ) 2 gives us θ= 1 1 +α αθ † +θ . Complementary slackness implies that (1 +α)(ε ′ ) 2 = θ−θ † 2 which in turn implies that we have e θ=θ † + (ε ′ ) 2 θ−θ † 2 θ−θ † . Thus, we have bn DPO = ∇ θ ℓ e θ DPO (D) ⊤ e θ−θ μ Nika, N ̈other, Mandal, Kamalaruban, Singla and Radanovi ́c ≤ ∇ θ ℓ e θ DPO (D) 3 θ † +∥θ μ ∥+ √ ε ′ = (nβ+λ) θ † + (ε ′ ) 2 θ−θ † 2 θ−θ † −θ 3 θ † +∥θ μ ∥+ √ ε ′ ≤( nβ+λ) θ−θ † 2 −(ε ′ ) 2 θ † −θ 3 θ † +∥θ μ ∥+ √ ε ′ . Ifα= 0, then the first-order condition yields e θ−θ μ =− ∇ 2 θ ℓ e θ DPO ( D) −1 ∇ θ ℓ e θ DPO ( D), which implies bn DPO = ∇ θ ℓ e θ DPO (D) ⊤ ∇ 2 θ ℓ e θ DPO (D) −1 ∇ θ ℓ e θ DPO ( D) ≤ ( nβ+λ) σ min (Σ ψ D ) · θ−θ † 2 −(ε ′ ) 2 θ † − θ , using Lemma E.14 and the projection derivations above. For the lower bound, note that, in the best case scenario for the attacker,Dis a subset of an optimal solution b Dfor Problem P:Attack:DPO.1 in the case whenD=∅. Thus, the attack sample size in this case is the lower bound of Theorem C.1 without the sizenofD. C.2 DPO with Empty Existing Data In this section, we provide additional upper bounds on the sample complexity for the DPO setting whenD=∅. Our aim is to obtain bounds that are tighter than the ones obtained by directly instantiating the bounds of Theorem 5.1. Moreover, we also provide lower bounds for this setting and use them for the general lower bounds of Theorem 5.1. Theorem C.1.LetD=∅, letβ >0and0< ε ′ ≤ε/2. Furthermore, letπ † ,μ∈Π log be loglinear with parameters θ † andθ μ , respectively. Define e θ=θ † +e √ ε ′ (θ μ −2θ † )/ θ μ −2θ † , wheree= 1, ifθ † ⊤ θ † −θ μ ≥ √ ε ′ −ε ′ , ande=−1, otherwise. Then, the dataset of2 λ | λ e θ ⊤ ( e θ−θ μ )| 2ξ max samples satisfying β e θ−θ μ ⊤ (ψ(s,a)−ψ(s,a ′ )) =o·ξ 2 λ e θ−θ μ 2 witho= 1for half of the samples, ando=−1for the remaining is a feasible solution to Problem P:Attack:DPO.1. Furthermore, there exists an optimal solution b Dto Problem P:Attack:DPO.1 withbn DPO identical samples such that bn DPO ≤2 λ 2ξ max θ † −θ μ − √ ε ′ 2 . Finally, there existsη min >0, such that, for anyε ′ ≥ε/η min , we have bn DPO ≥2 λ 2ξ max θ † −θ μ − √ ε ′ 2 . Proof.First, note that, sinceμis loglinear, Lemma E.8 implies that Problem Equation P:Attack.DPO.2 can be written as min D |D| Policy Teaching in Learning from Human Preferences s.t e θ= arg min θ X (s,a,a ′ ,o)∈D log 1 + exp −o·β(θ−θ μ ) ⊤ (ψ(s,a)−ψ(s,a ′ )) + λ 2 ∥θ−θ μ ∥ 2 e θ−θ † 2 ≤ε ′ . Now, given e θ̸=0, Lemma E.7 implies that the solution to the problem min D |D| s.t e θ= arg min θ X (s,a,a ′ ,o)∈D log 1 + exp −o·β(θ−θ μ ) ⊤ (ψ(s,a)−ψ(s,a ′ )) + λ 2 ∥θ−θ μ ∥ 2 is the set of 2 λ e θ−θ μ 2 2ξ max identical samples satisfying β e θ−θ μ ⊤ (ψ(s,a)−ψ(s,a ′ )) =o·ξ −1 λ e θ−θ μ 2 2 λ ∥ e θ−θ μ ∥ 2 2ξ max , witho= 1 for half the samples ando=−1 for the remaining samples. Next, for the upper bound, we will consider the surrogate problem. Using Lemma E.5, for anyε ′ ≤ε/(2 √ d ′ ), any feasible solution for Problem P:Attack.DPO.2 is feasible for Problem P:Attack:DPO.1. Thus, we focus on the former. We can rewrite the problem directly in terms of a variableθ: min θ ∥θ−θ μ ∥ 2 such that θ−θ † 2 ≤ε ′ . The Lagrangian of the above can be written as L(θ,α) =∥θ−θ μ ∥ 2 +α θ−θ † 2 −ε ′ . The first-order condition can be written as ∇ θ L(θ,α) = (θ−θ μ ) +α θ−θ † =0, which implies that e θ= 1 1 +α αθ † +θ μ . Complementary slackness implies 1 1 +α αθ † +θ μ −θ † = √ ε ′ . Equivalently, θ † −θ μ =|1 +α| √ ε ′ , which, because all three terms are non-negative, implies that α= θ † −θ μ √ ε ′ −1, Nika, N ̈other, Mandal, Kamalaruban, Singla and Radanovi ́c Plugging this into the first-order condition and subtracting both sides byθ μ , we get e θ−θ μ = √ ε ′ ∥θ † −θ μ ∥ θ † −θ μ √ ε ′ −1 ! θ † +θ μ ! −θ μ =θ † −θ μ − √ ε ′ ∥θ † −θ μ ∥ θ † −θ μ = √ ε ′ ∥θ † −θ μ ∥ −1 ! θ † −θ μ Using the above and some algebraic manipulations, we can write e θ−θ μ 2 = √ ε ′ ∥θ † −θ μ ∥ −1 ! θ † −θ μ 2 = θ † −θ μ − √ ε ′ 2 . The desired bounds follow as an immediate consequence of the above. D Proofs of Section 6 In this section, we provide the proof of the following result. Theorem 6.1.Letπ † ,μ∈Π log be loglinear with parametersθ † andθ μ , respectively. Furthermore, letεbe such thatε≤1/(2ξ max ),ε ′ ≥ε/η min , whereη min >0is an absolute constant, and letω † be a feasible solution to Problem P:Attack:RLHF.1. Defineκ 1 as λ ξ max θ † −θ μ − √ ε ′ 2 −n · 1 ξ max λ ω † 2 + ω † · 2 n (1−γ) 2 −1 Then, we havebn DPO ≥κ 1 ·bn RLHF . Proof.Note that we have bn DPO ≥2 λ 2ξ max θ † −θ μ − √ ε ′ 2 − n ≥ λ ξ max θ † −θ μ − √ ε ′ 2 −n = λ ξ max θ † −θ μ − √ ε ′ 2 − n · 1 ξ max λ ω † 2 + ω † · 2 n (1−γ) 2 −1 · 1 ξ max λ ω † 2 + ω † · 2 n (1−γ) 2 ≥κ 1 ·bn RLHF , where the first inequality follows from Theorem 5.2 and the first inequality follows from Corollary 4.2. E Technical Lemmas This section includes miscellaneous technical results used throughout the paper. We begin by stating a result about the structure of the regularized optimal policy. Lemma E.1.Given policyπand reward functionr, let V π r (s) =E s∼ρ,a t ∼π(·|s t ) X t≥0 γ t r(s t ,a t )−βlog π(a t |s t ) μ(a t |s t ) Policy Teaching in Learning from Human Preferences and Q π r (s,a) =r(s,a) +γ X s ′ P(s,a,s ′ )V π r (s ′ ) denote the regularized value and action value functions with respect toπandr, respectively. Moreover, let the regularized advantage function be defined as A π r (s,a) =Q π r (s,a)−V π r (s). Then, the unique optimal regularized policy can be written, for every(s,a), as π reg r (a|s) =μ(a|s) exp 1 β A π reg r (s,a) . Proof. The proof of this result is a straightforward application of the results from Appendix C of [Nachum et al., 2017] from the entropy-based to KL divergence-based regularization. Now we prove thatM π † is full rank. Lemma E.2.Letπ † ∈Π det andΦbe of rankd. Assume that the setφ(s,a) :s∈S,a∈A (π † ), where supp(π)denotes the set of actions chosen by deterministic policyπ, containsdlinearly independent vectors. Then, the matrixM π † is full rank. Proof.Letvbe an arbitrary column ofM π † . Then, there exists (s,a) and coefficientsα s ′ ,a ′ such that v= X s ′ d π † (s ′ )φ(s ′ ,π † (s ′ ))− X s ′ d π † s,a (s ′ )φ(s ′ ,π † s,a(s ′ )) = X s ′ ,a ′ α s ′ ,a ′ φ(s ′ ,a ′ ). By definition of the neighbors ofπ † , we have thata=π † s,a(s)̸=π † (s) =π(s), for allπ∈N(π † )\πs,a. This is because all neighboring policies are deterministic and change only in one state fromπ † , and, consequently, from each-other. This implies that, there is no columnv ′ inM π † , such thatφ(s,a) appears in the decomposition ofv ′ . There are S(A−1) such vectors, since there areS(A−1) neighbors ofπ † . Assuming that they contain all vectors that span the column space of Φ, this means that the rank ofM π † is equal to the rank of Φ. Next, we provide three results that connect the solutions of the surrogate problems to their original problems throughout the paper. We start with the unregularized RLHF setting. Lemma E.3.Letε ′ >0. Then, any feasible solution to Problem P:Attack:RLHF.2 is a feasible solution to Problem P:Attack:RLHF.1. Proof. First, note that, whenβ= 0, given rewardr, thenπ reg r (·|s)∈arg max π V π r (s), for alls. Such optimal policies are known to be deterministic. Now, givenbω, note that, ifε ′ >0, thenV π † r bω (s)> V π r bω (s), for any state s. This means thatπ † is the unique optimal policy underr bω . This further implies thatπ reg r bω =π † , and thus, D KL (π † ||π reg r bω ) = 0< ε, for anyε >0. Next, we consider the regularized RLHF setting. Lemma E.4.Letε ′ ≤(2ln2)ε. Then, any feasible solution to Problem P:Attack:RLHF.3 is a feasible solution to Problem P:Attack:RLHF.1. Proof.Given two policiesπandπ ′ , we have ∥π−π ′ ∥ 2 1 = X s,a ρ(s)|π(·|s)−π ′ (·|s)| 2 ≤ X s ρ(s)2 ln 2D KL (π(·|s)||π ′ (·|s)) Nika, N ̈other, Mandal, Kamalaruban, Singla and Radanovi ́c = (2 ln 2)D KL (π||π ′ ), where the first inequality follows from Pinsker’s inequality. This implies that, as long asD KL (π||π ′ )≤ε ′ , then ∥π−π ′ ∥ 2 1 ≤(2 ln 2)ε ′ ≤ε. Finally, we consider the DPO setting. Lemma E.5.Letε ′ ≤ε/(2 √ d ′ ). Then, any feasible solution to Problem P:Attack.DPO.2 is a feasible solution to Problem P:Attack:DPO.1. Moreover, there existsη min >0such that, for allε ′ ≥ε/η min , any feasible solution to Problem P:Attack:DPO.1 is also a feasible solution to Problem P:Attack.DPO.2. Proof.First, it can be easily shown that the gradient of a loglinear policy is ∇ θ π θ (a|s) =π θ (a|s) ψ(s,a)−E a ′ ∼π θ (·|s) [ψ(s,a ′ )] . We can bound this gradient by∥∇ θ π θ (a|s)∥≤2. Thus, loglinear policies are 2-Lipschitz in their parametersθ. Now, given policiesπ θ andπ θ ′ , due to the above argument, we can write ∥π θ −π θ ′ ∥ 1 ≤2∥θ−θ ′ ∥≤2ε ′ ≤ε. This implies that, for anyε ′ ≤ε/2, any feasible solution to Problem P:Attack.DPO.2 will be feasible for Problem P:Attack:DPO.1. For the second statement, we argue as follows. Since the functionπ θ is continuously differentiable inθ, the Mean Value Theorem implies that, for anyθand (s,a), there existsθ M (s,a) such that π θ (a|s)−π θ † (a|s) =∇ θ π θ M (s,a) (a|s) ⊤ θ−θ † =π θ M (s,a) (a|s)ψ θ M (s,a) (s,a) ⊤ θ−θ † ,(38) where ψ θ (s,a) =ψ(s,a)− X a ′ π θ (a ′ |s)ψ(s,a ′ ). Let∇ θ π θ M be theS·A-dimensional matrix with columnsρ(s)π θ M (s,a) (a|s)ψ θ M (s,a) (s,a), and letπdenote the S·A-dimensional vector with entriesρ(s)π(a|s), for each (s,a). Then, we have ∥π θ −π θ † ∥ 1 ≥∥π θ −π θ † ∥= ∇ θ π θ M θ−θ † ≥σ min (∇ θ π θ M ) θ−θ † , where the first inequality follows from the relationship betweenℓ 1 andℓ 2 norms; the first equality follows from Equation 38 and the second inequality follows from the fact that∥Ax∥ 2 ≥σ min (A)∥x∥ 2 , for compatible matrixA and vectorx, whereσ min (A) denotes the minimum singular value ofA. Now, observe that ∇ θ π ⊤ θ M ∇ θ π θ M = X s,a ρ(s) 2 π θ M (s,a) (a|s) 2 ψ θ M (s,a) (s,a)ψ θ M (s,a) (s,a) ⊤ . We will show that this matrix is positive definite, whenever the vectorsψ(s,a) spanR d ′ . First, the ergodicity assumption and the loglinearity of the policies imply thatρ(s)π θ (a|s)>0, for any (s,a) andθ. Next, observe that, since vectorsψ(s,a) spanR d ′ , then vectorsψ θ M (s,a) (s,a) also do, as translations of basis vectors via mean vectors. It is clear that∇ θ π ⊤ θ M ∇ θ π θ M is positive semi-definite, meaning that, for every non-zero vectorv, v ⊤ ∇ θ π ⊤ θ M ∇ θ π θ M v≥0. The only way the above can be zero is if, for every (s,a), we have v ⊤ ψ θ M (s,a) (s,a) = 0. But since ψ θ M (s,a) (s,a) spanR d ′ , then there exist coefficientsα s,a such that v= X s,a α s,a ψ θ M (s,a) (s,a), Policy Teaching in Learning from Human Preferences which implies that v ⊤ v= X s,a α s,a ψ θ M (s,a) (s,a) ⊤ v= 0, which is a contradiction, sincevis assumed to be non-zero. Thus, the matrix∇ θ π ⊤ θ M ∇ θ π θ M is positive definite, for any givenθ. This means that σ min (∇ θ π θ M ) = q λ min ∇ θ π ⊤ θ M ∇ θ π θ M =η min (θ)≥min θ η min (θ) :=η min >0, which further implies that θ−θ † ≤ 1 η min ∥π θ −π θ † ∥≤ 1 η min ∥π θ −π θ † ∥ 1 ≤ 1 η min ε≤ε ′ . We now prove two important lemmas which we use in most of the results of the paper. They provide solutions to the attack subproblems for RLHF and DPO. We start with the RLHF result. Lemma E.6.Letω † ∈R d and letD=(τ,τ ′ ,o)be a given preference dataset ofnsamples. Consider the problem min D |D|such thatω † = arg min ω ℓ ω RLHF D∪D . Then, the solution to the above problem is the dataset of & ∇ ω ℓ ω RLHF ( D) ⊤ ω † ξ max ' identical samples satisfying φ(τ)−φ(τ ′ ) =ξ −1 (ω † ) ⊤ ∇ ω ℓ ω RLHF (D) | ∇ ω ℓ ω RLHF (D) ⊤ ω † | ξ max ω † ∥ω † ∥ 2 , o= 1. Moreover, ifD=∅, the solution of the problem is the set of & λ ω † 2 ξ max ' identical samples satisfying φ(τ)−φ(τ ′ ) =ξ −1 λ ω † 2 l λ∥ω † ∥ 2 ξ max m ω † ∥ω † ∥ 2 , o= 1. Proof.First, note that the second case, whenD=∅, is a direct consequence of Theorem E.15. We thus focus on the general case whenD̸=∅. The first-order condition of our problem can be written as X (τ,τ ′ ,o)∈ D −o(φ(τ)−φ(τ ′ )) 1 + exp (o(ω † ) ⊤ (φ(τ)−φ(τ ′ ))) + X (τ,τ ′ ,o)∈D o(φ(τ)−φ(τ ′ )) 1 + exp (o(ω † ) ⊤ (φ(τ)−φ(τ ′ ))) +λω=0. We can equivalently write the above as X (τ,τ ′ ,o)∈D o(φ(τ)−φ(τ ′ )) 1 + exp (o(ω † ) ⊤ (φ(τ)−φ(τ ′ ))) +∇ ω ℓ ω † RLHF (D) =0. Nika, N ̈other, Mandal, Kamalaruban, Singla and Radanovi ́c Recall that we have defined ξ max := max t t 1 + exp(t) . Let us denote byξ −1 (a) the solution toa=x/(1 +exp(x)), fora≤ξ max . Such a solution exists and can be written in closed form [Liu and Zhu, 2016] as ξ −1 (a) =a−W Lam (−aexp(a)), for everya≤ξ max , whereW Lam denotes the Lambert W function. Now, let b Dbe a preference dataset of bn:= & ∇ ω ℓ ω RLHF (D) ⊤ ω † ξ max ' identical samples satisfying φ(τ)−φ(τ ′ ) =ξ −1 (ω † ) ⊤ ∇ ω ℓ ω RLHF ( D) | ∇ ω ℓ ω RLHF (D) ⊤ ω † | ξ max ω † ∥ω † ∥ 2 , o= 1. Note that the first-order condition with respect to b Dyields X (τ,τ ′ ,o)∈ b D −o(φ(τ)−φ(τ ′ )) 1 + exp (o(ω † ) ⊤ (φ(τ)−φ(τ ′ ))) +∇ ω ℓ ω RLHF (D) =−bn ξ −1 (ω † ) ⊤ ∇ ω ℓ ω RLHF ( D) | (ω † ) ⊤ ∇ ω ℓ ω RLHF (D) | ξ max −1 ! 1 + exp ξ −1 (ω † ) ⊤ ∇ ω ℓ ω RLHF (D) | (ω † ) ⊤ ∇ ω ℓ ω RLHF ( D) | ξ max −1 !! · ∇ ω ℓ ω RLHF ( D) (ω † ) ⊤ ∇ ω ℓ ω RLHF (D) +∇ ω ℓ ω RLHF (D) =−bn(ω † ) ⊤ ∇ ω ℓ ω RLHF (D) & (ω † ) ⊤ ∇ ω ℓ ω RLHF ( D) ξ max ' −1 ∇ ω ℓ ω RLHF (D) (ω † ) ⊤ ∇ ω ℓ ω RLHF ( D) +∇ ω ℓ ω RLHF (D) =0, where the penultimate equality is due to the fact that ω ⊤ ∇ ω ℓ ω RLHF ( D) (ω † ) ⊤ ∇ ω ℓ ω RLHF ( D) ξ max −1 ≤ξ max and the property ofξ −1 (·); the last equality follows by the definition ofbn. Since the functionℓ ω RLHF (D) is strongly convex, the first-order condition is enough to determine the optimal solution. Similarly, we prove an analogous result for DPO. The difference here is that the problem of interest is not a homogeneous logistic regression anymore, due to the presence ofθ μ . Lemma E.7.Letθ † ,θ μ ∈R d ′ for some reference policyμand letD=(τ,τ ′ ,o)be a given preference dataset ofnsamples. Consider the problem min D |D|such thatθ † = arg min θ ℓ θ DPO D∪D . Then, the solution to the above problem is the dataset of 2 (∇ θ ℓ θ † DPO ( D)) ⊤ (θ † −θ μ ) 2ξ max Policy Teaching in Learning from Human Preferences identical samples satisfying β θ † −θ μ ⊤ (ψ(s,a)−ψ(s,a ′ )) =o·ξ −1 (∇ θ ℓ θ † DPO ( D)) ⊤ θ † −θ μ 2 (∇ θ ℓ θ † DPO ( D)) ⊤ (θ † −θ μ ) 2ξ max , witho= 1for half the samples ando=−1for the remaining samples. Moreover, ifD̸=∅, the solution of the problem is the dataset of 2 & λ θ † −θ μ 2 2ξ max ' identical samples satisfying β θ † −θ μ ⊤ (ψ(s,a)−ψ(s,a ′ )) =o·ξ −1 λ θ † −θ μ 2 2 l λ∥θ † −θ μ ∥ 2 2ξ max m , witho= 1for half the samples ando=−1for the remaining samples. Proof.We prove the general case. The second case follows directly from the fact that, if D=∅, we have ∇ θ ℓ θ † DPO ( D) =λ θ † −θ μ 2 . First, note that, for loglinearμwith parameterθ μ , the optimization problem of interest becomes min D |D| s.tθ † = arg min θ X (s,a,a ′ ,o)∈D∪ D log 1 + exp −o·β(θ−θ μ ) ⊤ (ψ(s,a)−ψ(s,a ′ )) + λ 2 ∥θ−θ μ ∥ 2 . The first-order condition of the above can be written as X (s,a,a ′ ,o)∈D −β(ψ(s,a)−ψ(s,a ′ )) 1 + exp (o·β(θ † −θ μ ) ⊤ (ψ(s,a)−ψ(s,a ′ ))) +∇ θ ℓ θ † DPO ( D) =0. Now let us consider the following construction. Let bn= 2 ∇ θ ℓ θ † DPO ( D) ⊤ θ † −θ μ 2ξ max . For every 1≤i≤bn/2, letψ + be such that β θ † −θ μ ⊤ ψ + =z , where z=ξ −1 ∇ θ ℓ θ † DPO ( D) ⊤ θ † −θ μ bn ! , and for everybn/2 + 1≤j≤bn, let ψ − =ψ + − 2z β∇ θ ℓ θ † DPO (D) ⊤ (θ † −θ μ ) ∇ θ ℓ θ † DPO (D). Nika, N ̈other, Mandal, Kamalaruban, Singla and Radanovi ́c Note that β θ † −θ μ ⊤ ψ − =−z . Using dataset b D=(s i ,a i ,a ′ i ,o i ) bn i=1 such thatψ(s i ,a i )−ψ(s i ,a ′ i ) =ψ + ando i = 1, for all 1≤i≤bn/2, and ψ(s i ,a i )−ψ(a i ,s ′ i ) =ψ − ando i =−1, for allbn/2 + 1≤j≤bn, we consider the first-order condition of our problem: −βbn 2 · 1 1 + exp β(θ † −θ μ ) ⊤ ψ + ψ + + βbn 2 · 1 1 + exp −β(θ † −θ μ ) ⊤ ψ − ψ − +∇ θ ℓ θ † DPO (D) = −βbn 2 · 1 1 + exp (z) ψ + + βbn 2 · 1 1 + exp (z) ψ + − 2z β∇ θ ℓ θ † DPO ( D) ⊤ (θ † −θ μ ) ∇ θ ℓ θ † DPO (D) +∇ θ ℓ θ † DPO (D) =−bn· z 1 + exp(z) 1 ∇ θ ℓ θ † DPO (D) ⊤ (θ † −θ μ ) ∇ θ ℓ θ † DPO (D) +∇ θ ℓ θ † DPO (D) =−bn· ξ −1 ∇ θ ℓ θ † DPO ( D) ⊤ ( θ † −θ μ ) bn 1 + exp ξ −1 ∇ θ ℓ θ † DPO (D) ⊤ (θ † −θ μ ) bn 1 ∇ θ ℓ θ † DPO (D) ⊤ (θ † −θ μ ) ∇ θ ℓ θ † DPO (D) +∇ θ ℓ θ † DPO (D) =−bn· ∇ θ ℓ θ † DPO (D) ⊤ θ † −θ μ bn 1 ∇ θ ℓ θ † DPO (D) ⊤ (θ † −θ μ ) ∇ θ ℓ θ † DPO ( D) +∇ θ ℓ θ † DPO ( D) =0. Strong convexity ofℓ θ DPO (D) (see Lemma E.14) implies that the first-order condition is enough to guarantee optimality. Next, we derive the DPO loss for loglinear policies and reference policy. Lemma E.8.The DPO loss for loglinear policy parametrization and loglinear reference policyμcan be written as ℓ θ DPO (D) = X (s,a,a ′ ,o)∈D log 1 + exp −oβ(θ−θ μ ) ⊤ (ψ(s,a)−ψ(s,a ′ )) + λ 2 ∥θ−θ μ ∥ 2 . Proof.Note that ℓ θ DPO (D) =− X (τ,τ ′ ,o)∈D logσ o· βlog π θ (a|s) μ(a|s) −βlog π θ (a ′ |s) μ(a ′ |s) + λ 2 ∥θ−θ μ ∥ 2 = X (τ,τ ′ ,o)∈D log 1 + exp −o· βlog π θ (a|s) μ(a|s) −βlog π θ (a ′ |s) μ(a ′ |s) + λ 2 ∥θ−θ μ ∥ 2 = X (s,a,a ′ ,o)∈D log 1 + exp −oβlog π θ (a|s)μ(a ′ |s) μ(a|s)π θ (a ′ |s) + λ 2 ∥θ−θ μ ∥ 2 = X (s,a,a ′ ,o)∈D log 1 + exp −oβ log exp(θ ⊤ ψ(s,a)) exp(θ ⊤ μ ψ(s,a ′ )) P a ′ exp(θ ⊤ μ ψ(s,a ′ )) P a ′ exp(θ ⊤ ψ(s,a ′ )) exp(θ ⊤ μ ψ(s,a ′ )) exp(θ ⊤ ψ(s,a ′ )) P a ′ exp(θ ⊤ μ ψ(s,a ′ )) P a ′ exp(θ ⊤ ψ(s,a ′ )) !! + λ 2 ∥θ−θ μ ∥ 2 = X (s,a,a ′ ,o)∈D log 1 + exp −oβ(θ−θ μ ) ⊤ (ψ(s,a)−ψ(s,a ′ )) + λ 2 ∥θ−θ μ ∥ 2 . Next, we prove that the KL constraints are convex for loglinear policies. Policy Teaching in Learning from Human Preferences Lemma E.9.Letπ θ ∈Π log be a loglinear policy with respect to feature mappingψ. Then,D KL (π † ||π θ )is convex. Proof.Using the gradient ofπ θ from the proof of Lemma E.1, we have ∇ θ D KL (π † ||π θ ) =∇ θ X s,a ρ(s)π † (a|s) logπ † (a|s)−logπ θ (a|s) =∇ θ X s ρ(s) log X a exp θ ⊤ ψ(s,a) − X s,a ρ(s)π † (a|s)θ ⊤ ψ(s,a) ! = X s,a ρ(s)π θ (a|s)ψ(s,a)− X s,a ρ(s)π † (a|s)ψ(s,a). Furthermore, note that for the Hessian we have ∇ 2 θ D KL (π † ||π θ ) =∇ θ X s,a ρ(s)π θ (a|s)ψ(s,a)− X s,a ρ(s)π † (a|s)ψ(s,a) ! = X s,a ρ(s)π θ (a|s) ψ(s,a)− X a ′ π θ (a ′ |s)ψ(s,a ′ ) ! ψ(s,a) ⊤ = X s ρ(s) X a π θ (a|s)ψ(s,a)ψ(s,a) ⊤ − X a π θ (a|s)ψ(s,a) ! X a π θ (a|s)ψ(s,a) ! ⊤ = X s ρ(s)E a∼π θ (·|s) h ψ(s,a)−E a ′ ∼π θ (·|s) [ψ(s,a ′ )] ψ(s,a)−E a ′ ∼π θ (·|s) [ψ(s,a ′ )] ⊤ i ⪰0. Next, we provide the necessary condition for the constructed dataset to satisfy the feature conditions. Lemma E.10.Letω 0 be a given parameter andfbe an arbitrary function ofω 0 . Assume thatγis such that 1−γ≤ 2∥ω 0 ∥ ξ max + 1 . Then, if there exist trajectory pairs(τ,τ ′ ), for which φ(τ)−φ(τ ′ ) =ξ −1 f(ω 0 ) f(ω 0 ) ξ max −1 ! ω 0 ∥ω 0 ∥ , they are feasible in the feature space, in the sense that they satisfy∥φ(τ)∥ 2 ,∥φ(τ ′ )∥ 2 ≤1. Proof.First, we will consider the case when the range offis non-negative, i.e.,f(ω 0 )≥0. For this case, note that 0≤f(ω 0 ) f(ω 0 ) ξ max −1 ≤ξ max =W Lam (1/e)<0.3, where we recall that ξ max = max t t 1 + exp(t) . Now, note that we can write ξ −1 (a) =a−W Lam (−aexp(a)),(39) Nika, N ̈other, Mandal, Kamalaruban, Singla and Radanovi ́c for anya≥−1/e, since, if we lett ∗ =a−W Lam (−aexp(a)), we obtain t ∗ 1 + exp(t ∗ ) = a−W Lam (−aexp(a)) 1 + exp(a−W Lam (−aexp(a))) = a+aexp(a)/exp(a−W Lam (−aexp(a))) 1 + exp(a−W Lam (−aexp(a))) =a . Our aim is to show that we can find pairs (τ,τ ′ ) that satisfy φ(τ)−φ(τ ′ ) =ξ −1 f(ω 0 ) f(ω 0 ) ξ max −1 ! ω 0 ∥ω 0 ∥ . This amounts to showing the right-hand side of the above equation satisfies the feature boundedness, i.e., that it is consistent with the assumption that∥φ(τ)∥≤1/(1−γ), for allτ. To that end, we will derive upper bounds on the norm of the quantity on the right hand side of the equation above. First, we consider theξ −1 (·) term. We have ξ −1 f(ω 0 ) f(ω 0 ) ξ max −1 ! = f(ω 0 ) f(ω 0 ) ξ max −1 −W Lam −f(ω 0 ) f(ω 0 ) ξ max −1 exp f(ω 0 ) f(ω 0 ) ξ max −1 !! (40) ≤ f(ω 0 ) f(ω 0 ) ξ max −1 + W Lam −f(ω 0 ) f(ω 0 ) ξ max −1 exp f(ω 0 ) f(ω 0 ) ξ max −1 !! (41) ≤ξ max + log 1−f(ω 0 ) f(ω 0 ) ξ max −1 exp f(ω 0 ) f(ω 0 ) ξ max −1 !! (42) ≤ξ max +|log (1−ξ max exp (ξ max ))|,(43) where Equation 40 follows from Equation 39; Equation 41 follows from the triangle inequality; Equation 42 follows from Theorem 2.3 of [Hoorfar and Hassani, 2008], where we lety= 1; Equation 43 follows from the fact that the function log(1−xe x ) is negative and decreasing in the range (0,ξ max ). Since we should have ∥φ(τ)−φ(τ ′ )∥≤∥φ(τ)∥+∥φ(τ ′ )∥≤ 2 1−γ , for the construction to be feasible in this case, we need ξ −1 f(ω 0 ) f(ω 0 ) ξ max −1 ! ω 0 ∥ω 0 ∥ ≤ ξ max +|log (1−ξ max exp (ξ max ))| ∥ω 0 ∥ ≤ 2 1−γ . Next, let us now consider the case whenf(ω 0 )≤0. In this case, the dataset construction uses the term f(ω 0 ) |f(ω 0 )| ξ max −1 . Note that, sincef(ω 0 )≤0, we have −ξ max ≤f(ω 0 ) |f(ω 0 )| ξ max −1 ≤− |f(ω 0 )|ξ max |f(ω 0 )|+ξ max ≤0. In this case, we obtain ξ −1 f(ω 0 ) f(ω 0 ) ξ max −1 ! ≤ξ max + log 1−f(ω 0 ) f(ω 0 ) ξ max −1 exp f(ω 0 ) f(ω 0 ) ξ max −1 !! (44) ≤ξ max + 1,(45) Policy Teaching in Learning from Human Preferences where Equation 44 follows directly from Equation 42, while Equation 45 follows from the fact that the maximum value of log(1−xe x ) in the interval (−∞,0) is upper bounded by 1. Thus, combining both cases, we obtain the condition max ξ max +|log (1−ξ max exp (ξ max ))| ∥ω 0 ∥ , ξ max + 1 ∥ω 0 ∥ = ξ max + 1 ∥ω 0 ∥ ≤ 2 1−γ . This finally implies that we should pickγsuch that 1−γ≤ 2∥ω 0 ∥ ξ max + 1 . Next, we provide results characterizing the spectra of matrices relevant to our setting. Lemma E.11.We have σ max (M π † )≤ √ SA and σ max (Σ D )≤ 1 1−γ . Proof.Note that ∥M π † ∥= q M ⊤ π † M π † = q M π † M ⊤ π † ≤ q 2 minSA,dmax s,a ∥φ(s,a)∥ ≤ p 2 minSA,d. Moreover, we have that σ max (Σ D ) =σ max 1 n X (τ,τ ′ )∈D (φ(τ)−φ(τ ′ )) (φ(τ)−φ(τ ′ )) ⊤ ≤ 1 n X (τ,τ ′ )∈D σ max (φ(τ)−φ(τ ′ )) (φ(τ)−φ(τ ′ )) ⊤ ≤ 1 n X (τ,τ ′ )∈D Tr (φ(τ)−φ(τ ′ )) (φ(τ)−φ(τ ′ )) ⊤ = 1 n X (τ,τ ′ )∈D (φ(τ)−φ(τ ′ )) ⊤ (φ(τ)−φ(τ ′ )) ⊤ ≤ 1 n X (τ,τ ′ )∈D (∥φ(τ)∥+∥φ(τ ′ )∥) ≤ 2 1−γ , whereTr(M) denotes the trace of matrixM. Next, we provide a characterization of the spectral properties of a matrix of interest for the RLHF setting. Lemma E.12.Given parameterω, letY ω D be defined as in Equation 12. Then, the following inequalities hold: n e C φ ω,D C φ D + 2λ≤σ min Y ω D ≤σ max Y ω D ≤nσ max Σ φ D + 2λ≤ n 1−γ + 2λ ,(46) Nika, N ̈other, Mandal, Kamalaruban, Singla and Radanovi ́c and 1−γ n+ 2(1−γ)λ ≤σ min (Y ω D ) −1 ≤σ max ((Y ω D ) −1 )≤ 1 n e C φ ω,D C φ D + 2λ , where e C φ ω,D =min (τ,τ ′ ,o)∈D exp(oω ⊤ (φ(τ)−φ(τ ′ )) (1 + exp(oω ⊤ (φ(τ)−φ(τ ′ ))) 2 . Proof.The first inequality in Equation 46 follows from σ min (Y ω D )≥σ min X (τ,τ ′ ,o)∈D exp(oω ⊤ (φ(τ)−φ(τ ′ )) (1 + exp(oω ⊤ (φ(τ)−φ(τ ′ ))) 2 (φ(τ)−φ(τ ′ )) (φ(τ)−φ(τ ′ )) ⊤ + 2λI ≥ e C φ ω,D σ min X (τ,τ ′ ,o)∈ D (φ(τ)−φ(τ ′ )) (φ(τ)−φ(τ ′ )) ⊤ + 2λ(47) ≥ n e C φ ω,D C φ D + 2λ ,(48) where Equation 47 uses the definition of e C φ ω, D and Equation 48 follows by the assumption on Σ φ D . The upper bound in Equation 46 follows from Y ω D =σ max Y ω D =σ max X (τ,τ ′ ,o)∈ D exp(oω ⊤ (φ(τ)−φ(τ ′ )) (1 + exp(oω ⊤ (φ(τ)−φ(τ ′ ))) 2 (φ(τ)−φ(τ ′ )) (φ(τ)−φ(τ ′ )) ⊤ + 2λI ≤ X (τ,τ ′ ,o)∈D exp(oω ⊤ (φ(τ)−φ(τ ′ )) (1 + exp(oω ⊤ (φ(τ)−φ(τ ′ ))) 2 σ max (φ(τ)−φ(τ ′ )) (φ(τ)−φ(τ ′ )) ⊤ + 2λ ≤ X (τ,τ ′ ,o)∈ D 1 2 Tr (φ(τ)−φ(τ ′ )) (φ(τ)−φ(τ ′ )) ⊤ + 2λ(49) = X (τ,τ ′ ,o)∈ D 1 2 (φ(τ)−φ(τ ′ )) ⊤ (φ(τ)−φ(τ ′ )) + 2λ ≤ n 1−γ + 2λ ,(50) where Equation 49 follows from the fact that σ max (v ⊤ )≤Tr v ⊤ =v ⊤ v , for any nonzero vectorv, and the fact that x (1 +x) 2 ≤ 1 2 for all positivex; Equation 50 follows from (φ(τ)−φ(τ ′ )) ⊤ (φ(τ)−φ(τ ′ ))≤2 max τ ∥φ(τ)∥= 2 1−γ . This concludes the first part of our result. For the characterization of the eigenspectrum of the inverse ofY ω D , we make use of the above derivations and immediately observe that σ min (Y ω D ) −1 ≥ 1 σ max (Y ω D ) ≥ 1−γ n+ 2(1−γ)λ ,(51) Policy Teaching in Learning from Human Preferences and σ max ((Y ω D ) −1 )≤ 1 n e C φ ω, D C φ D + 2λ .(52) Next, we show that the KL divergence of two loglinear policies is Lipshcitz with respect to their respective parameters. Lemma E.13.Letπ θ andπ θ ′ be two loglinear policies with respect to feature mappingψ. Then, D KL (π θ ||π θ ′ )≤2∥θ−θ ′ ∥. Proof.Note that D KL (π θ ||π θ ′ ) = X s,a π θ (a|s) (logπ θ (a|s)−logπ θ ′ (a|s)) = X s,a π θ (a|s) (θ−θ ′ ) ⊤ ψ(s,a) + X s ρ(s) log X a ′ exp (θ ′ ) ⊤ ψ(s,a ′ ) −log X a ′ exp θ ⊤ ψ(s,a ′ ) ! ≤ X s,a ρ(s)π θ (a|s)∥θ−θ ′ ∥ψ(s,a)∥+ X s ρ(s)∥θ−θ ′ ∥ψ(s,a)∥ ≤2∥θ−θ ′ ∥, where the third inequality uses Cauchy-Schwarz and the fact that the log-sum-exp function is Lipshcitz with parameter 1, since ∇ θ X s ρ(s) log X a exp θ ⊤ ψ(s,a) = X s,a ρ(s)π θ (a|s)ψ(s,a) ≤max s,a ∥ψ(s,a)∥≤1. Our next result states some nice properties of the regularized logistic regression loss. These implications are easy to prove. Nevertheless, we provide the full proofs for completion. Lemma E.14.Given datasetD=(x i ,y i ) n i=1 , let ℓ υ (D) = X (x,y)∈D log 1 + exp β·yυ ⊤ x+b + λ 2 ∥υ−ζ∥ 2 denote a regularized logistic regression loss with respect toυ∈R d , for somed∈N, whereb∈R,ζ∈R d , and λ >0. Moreover, let Σ D = 1 n X x∈D x ⊤ be the data covariance matrix with minimum eigenvalueσ, and letυ ∗ denote an optimal point forℓ υ (D). Then, the following hold: 1. The functionℓ υ (D)is strongly convex with parameternβC υ σ+λ. 2. We have∥∇ υ ℓ υ (D)∥≥2(nβC υ σ+λ)∥υ−υ ∗ ∥. 3. The function X υ D = X (x,y)∈D β·y 1 + exp (β·yυ ⊤ x+b) x is Lipschitz with parametern. Nika, N ̈other, Mandal, Kamalaruban, Singla and Radanovi ́c 4. We have∥∇ υ ℓ υ (D)∥≤(nβ+λ)∥υ−υ ∗ ∥. Proof.First, note that the Hessian ofℓ υ (D) can be written as ∇ 2 υ ℓ υ (D) = X (x,y)∈D βexp(β·yυ ⊤ x+b) (1 + exp(β·yυ ⊤ x+b)) 2 x ⊤ +λI ⪰βnC υ 1 n X (x,y)∈D x ⊤ +λI ⪰(nβC υ σ+λ)I , where we have only used the assumptions of the statement. This means thatℓ υ (D) is strongly convex with parameternβC υ σ+λ. The second statement is a direct implication of this. For the third statement, first note that we have ∥X υ D ∥= X (x,y)∈D −βx 1 + exp (β·yυ ⊤ x+b) ≤βn. Then, we can write ∥∇ υ ℓ υ (D)∥= ∇ υ ℓ υ (D)−∇ υ ℓ υ ∗ (D) = X υ D +λ(υ−ζ)−X υ ∗ D +λ(υ ∗ −ζ) ≤nβ∥υ−υ ∗ ∥+λ∥υ−υ ∗ ∥ ≤(nβ+λ)∥υ−υ ∗ ∥, where the penultimate inequality uses Lipschitzness ofX υ D . The next result is used for the solution of the logistic regression subproblems. Theorem E.15(Proposition 3 of [Liu and Zhu, 2016]).Given any target modelω † ̸=0, the following is a teaching set for the logistic regression problem min D ′ |D ′ |such thatω † ∈arg min ω X (x i ,y i )∈D ′ log 1 + exp −y i x ⊤ i ω + λ 2 ∥ω∥ 2 . There arebn= λ ∥ ω † ∥ 2 ξ max identical training samples, each taking the form x i =ξ −1 λ ω † 2 l λ∥ω † ∥ 2 ξ max m ω † ∥ω † ∥ 2 , y i = 1.