Strategyproof Reinforcement Learning from Human Feedback
Authors: Thomas Kleine Buening
Jiarui Gan
Debmalya Mandal
Marta Kwiatkowska
Venue: NeurIPS 2025 poster ()
Keywords: reinforcement learning from human feedback
pluralistic alignment
mechanism design
strategyproofness
incentive-compatibility
Primary area: reinforcement_learning
TL;DR: We show RLHF is vulnerable to strategic manipulation, discuss trade-offs between incentive and policy alignment, and propose an approximately strategyproof algorithm to address it.

Abstract: We study Reinforcement Learning from Human Feedback (RLHF) in settings where multiple labelers may strategically misreport feedback to steer the learned policy toward their own preferences. We show that existing RLHF algorithms, including recent pluralistic methods, are not strategyproof, and that even a single strategic labeler can cause arbitrarily large misalignment with social welfare. Moreover, we prove that, in the worst case, any strategyproof RLHF algorithm must perform $k$-times worse than the optimal policy, where $k$ is the number of labelers. This suggests a fundamental trade-off between incentive alignment (ensuring labelers report truthfully) and policy alignment (maximizing social welfare). To address this, we propose the Pessimistic Median of MLEs algorithm, which, under appropriate policy coverage assumptions, is approximately strategyproof and converges to the optimal policy as the number of labelers and samples increases. Our results apply to both contextual bandits and Markov decision processes.

Strategyproof Reinforcement Learning from Human Feedback
Thomas Kleine Buening
Jiarui Gan
ETH Zurich ETH AI Center
Department of Computer Science University of Oxford
Debmalya Mandal
Marta Kwiatkowska
Department of Computer Science University of Warwick
Department of Computer Science University of Oxford
Abstract
We study Reinforcement Learning from Human Feedback (RLHF) in settings where multiple labelers may strategically misreport feedback to steer the learned policy toward their own preferences. We show that existing RLHF algorithms, including recent pluralistic methods, are not strategyproof, and that even single strategic labeler cause arbitrarily large misalignment with social welfare. Moreover, we prove that, in the worst case, any strategyproof RLHF algorithm must perform k-times worse than the optimal policy, where k is the number of labelers. This suggests a fundamental trade-off' between incentive alignment (ensuring labelers report truthfully) and policy alignment (maximizing social welfare). To address this, we propose the Pessimistic Median of MLEs algorithm, which, under appropriate policy coverage assumptions, approximately strategyproof and converges to the optimal policy as the number of labelers and samples increases. Our results apply both contextual bandits and Markov decision processes.
Introduction
Reinforcement Learning from Human Feedback (RLHF) has become widely used approach for aligning AI systems with human preferences. By leveraging numan-labeled comparisons, RLHF enables policy optimization in applications such as robotics, recommendation systems, and Large Language Models (LLMs) [5. 21]. This approach has and alignment with intended objectives. However, RLHF also introduces new challenges, particularly in situations where preferences are diverse, subjective, and potentially conflict.
significant improvements in usability
Recently, pluralistic alignment- the challenge of aligning with the preferences of diverse individuals or groups- has emerged as an active area of research [33, 14, 22, 3, 6]. Unlike traditional reinforce- ment learning, which optimizes policy according to single, well-defined reward function, pluralistic settings require reconciling multiple perspectives. This raises questions about whose preferences should shape AI decisions and how to aggregate diverse inputs fairly and effectively [20, 11]. In such pluralistic settings, existing methods often optimize policies based on aggregated human preferences, implicitly assuming that labelers provide feedback truthfully. However, this perspective crucially neglects the incentives of labelers when their feedback directly impacts policy outcomes.
When human preferences influence the final policy, labelers (or groups of labelers) may have incentives to manipulate their feedback in ways that benefits them at the expense of broader align-
ment [30, 19]. For example, in the context of LLM fine-tuning, human labelers may systematically misreport preferences to amplify specific biases and reinforce narratives favorable to their views.
Naturally, this challenge is not exclusive to human labelers but can also arise, or even be amplified, when learning from synthetic feedback sources designed to influence model behavior.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

As result, such strategic behavior threatens to distort the aligmment process through self-serving feedback and can undermine the fairness, robustness, and effectiveness of the system [13, 21. Despite its importance, this issue remains largely unaddressed in existing RL.F methodologies.
This paper aims to bridge this gap by studying RLHF through the lens of mechanism design and proposing solutions that ensure robustmess against strategic feedback. We formalize the problem, analyze the conditions and the cost under which strategyproofness can be achieved, and propose an RLHF method to mitigate incentive misalignment while maintaining policy performance.
In summary, our main contributions are:
We formally introduce the problem of offline RLHF with strategic human labelers, where each labeler potentially misreports preference labels to steer the final policy toward the maximization of their personal objectives, i.e., their reward function (Section 3). We focus on linear reward functions and social welfare maximization and study the tensions that arise between individual incentive alignment and policy alignment with social welfare.
We show that existing RLHF methods are not strategyproof (Proposition 3.3), and even a single strategic labeler can almost arbitrarily degrade policy performance of existing methods (Proposi- tion 3.4). Moreover, without additional assumptions, we find that any strategyproof RLHF method suffers from constant suboptimality (Theorem 3.5) and performs at least k-times worse compared to the optimal policy (Corollary 3.6), where is the number of distinct labelers. This points towards a fundamental trade-off between incentive alignment and policy alignment.
We propose an RLHF method called Pessimistic Median of MLEs, which combines pessimistic estimates with median rule to incentivize truthful preference reporting (Section 4). Interestingly. we find that Pessimistic Median of MLES is approximately strategyproof due to the uncertainty in reward estimation. Notably, the incentive strength depends on the uniform policy coverage of each labeler's data. This stands in contrast to standard RLHF guarantees, which rely only on the coverage of the optimal policy. More precisely, under additional domain restrictions, we show:
a) Pessimistic Median of MLEs is Ö / hes//n))ssrtatgyyrro for labeler i where K; quantifies the uniform policy coverage of labeler (Theorem 4.
b) The computed policy's ss suboptimality bounded by ((Va/k+ + max Ky k/d//) where Kt is the optimal policy coverage of labeler i (Theorem 4.2, Proposition 4.3, Corollary 4.5).
We establish these results for both contextual bandits and Markov decision processes (Section 5).
2 Related Work
Reinforcement Learning from Human Feedback. RLHF has emerged as a powerful framework for aligning Al systems with human values by leveraging human feedback to guide policy learning [10, 5, 21J. Most relevant to our work is the growing literature on RLHF in settings with diverse and
possibly conflicting preferences among individuals or demographic groups [7, 28, 37, 8]. Some of these works focus on maximizing the worst-case utility across labelers (or groups) [7, 28], whereas others optimize welfare functionn such as the additive social welfare [37].
Some other recent work has also explicitly taken a social choice perspective on pluralistic alignment and studies how ensure that methods for preference aggregation satisfy desirable properties inspired by social choice theory [11, 15, I]. Importantly, these works, while related, assume truthful feedback and do not account for the incentives created by Al alignment. However, aggregating and trading- off preferences naturally invites strategic or malicious behavior, as labelers may manipulate the aligmment process to more closely align the final policy with their own beliefs and goals. For example. Siththaranjan et al. [32] highlighted how standard RL.F methods implicitly aggregate preferences using the Borda count voting rule, which can create incentives for annotators to misreport their preferences to influence model behavior.
Another body of work considers robustness against adversarial corruptions in RLHF Mandal et al. [24] assume that an e- e-fraction of samples is adversarially manipulated, allowing for both manipulation of trajectory features and preference labels. Similarly, Bukharin et al. [4] and Cheng et al. [9] also consider the case where a fraction of samples is manipulated but restrict their attention to adversaries flipping preferences. This line of work differs from ours notably in both perspective (strategic vs. adversarial) and techniques (mechanism design vs. robust offline RL).

---

Mechanism Design for RLHF. Recently, several works have incorporated mechanism design principles into RLHF incentivize truthful feedback [27, 34, 35J. These approaches design payment rules to align labelers' incentives, often extending VCG-style mechanisms to the RLHF problem. In contrast, we propose a strategy-robust RI.FF method that does not rely on payments or other financial incentives, which are often impractical in real-world applications. Also closely related is the work of Hao and Duan [18], which studies an online RLHF framework where labelers sequentially provide preference feedback, aggregated using a linearly weighted average. Their approach focuses on identifying the most accurate labeler over time and adjusting the weights to incentivize truthful reporting. In contrast, we study the offline RLHF setting and do not impose a linear weighting assumptions on labelers. Moreover, unlike [18], we assume that labelers seek to influence the final policy rather than just an estimate of the aggregated preferences, which might better reflect real world strategic behavior, where individuals care about the actual policy outcomes rather than intermediate preference estimates. In particular, we will see, a more elosely aligned reward function does not imply a more aligned policy.
3 Problem Formulation
We consider episodic Markov Decision Processes (MDPs) and the special case of contextual bandits. Let M = (S, A, P, H. p) be an MDP without reward function, where S is the state space, AA is the action space, H is the horizon and p is the initial state distribution. p = (PI..... PH) denotes the tuple of transition functions, where Py: S x A + (SS) determines the transitions in step h [#]. A history-indepeendnt policy π = (TT))s maps from states to a distribution over actions in every time step, i.e., TA: S - (AA), and we let II denote its policy space. A trajectory in MDP M is given by a sequence of actions and states 7 = (01, $2, Q2, SH aH) The MDP reduces to a contextual bandit problem when // 1, in which case trajectory consists only of the action taken in the initial state and the initial states are interpreted as contexts sampled from p.
Multiple Labelers with Diverse Preferences. We consider the situation where 2 many labelers provide preference data to the RLHF algorithm. In particular, each labeler i E [K] is associated with a reward function r;: S x A R. The expected return of policy æ w.r.t. a reward function r is given by (s((s) == E Σ r(sn, TA (sx)) 81 = s]. Accordingly, we define the utility of labeler E [A]
w.r.t. the initial state distribution p and policy as
(p x) = Eamp [V. (s)]
Note that this simplifies to Je(p, .) = E E.-ppri(ss, (8)) the contextual bandit.
We focus on the linearly realizable case, where the reward function of each labeler is linear function re (s, a) (0, ((s, a]) of known feature embedding & of the state (i.e., context) and action.
Assumption 1 (Linear Realizability). Every labeler's reward function r; is given by a linear function
To: (s. (07, b(s,a)); Here, the reward parameter 87 is sampled from {0 E Rd: ||0||2 < B} with B 0 and @ is a known mapping with [|o((s a)]l2 < L for all (s, S x A.
Offline RLHE We focus on the offline RLHF setting, where each labeler E [k] is given a pre-determined set of examples (shJ, To 7()) indexed by [m] where şا denotes the initial state and (TD) -T-)) are two subsequent trajectories. For each such example, labeler provides a preference label 0²d E {0, 1), where the label 0.ر = 0 means that trajectory TO is preferred over Ti given initial state sh,, and vice versa.
We employ the widely used Bradley-Terry (BT) model under which labeler with a reward pa- rameter 0 (i.c., reward function r&) prefers trajectory To = (a1, 82, a2..... SH aH) over trajectory Ti (01, 32, ā2,..................... ..... 3H, az) with probability
exp(re(s,TT))
Po = 0 8, To. TT) exp(ro(s, mn)) 7x)()
(1)
where re(s, To) = Σ h- re (s an) is the total reward of the trajectory To given initial state $ S. In contextual bandit, where each trajectory consists of a single action only, i.c., TO ag and 7 = 01, the comparison model conveniently simplifies to (o = 0 s, ag, 01) x exp(ro (s, ag)).
With slight abuse of notation we let r(s, (s)) (a- [r(s, a)] if the policy is stochastic. 'To ease notation, we assume that every labeler provides preferences for the same number of examples n. This can be straightforwardly relaxed at the cost of additional notation and slightly more cumbersome statements.
3

---

Strategic Preference Labeling. We assume that if labeler E [[]] provides their preferences trutifully,, then the preference labels ofJ are sampled with respect to their true reward function ro:. Thus, the collected preference dataset under truthful labeling is given by
Dj- = (s
2.3 ,''))
Jisn with o²d ~ P 1
Since each labeler aims to more closely align the final policy with their personal preferences, labeler may strategically manipulate labels to maximize their utility Jj. In this case, we assume that labeler samples preference labels according to manipulated reward function ra.
D. (5
To i. i. o Jisn with H.d ~ Pa.
TI
Note that the examples (s T0 7i ( remain fixed and only the preference labels change."
Given a reported preference dataset D = (D....., Da), ) an RLHF algorithm computes policy #RLHP (D) II. We omit the argument D when the dataset is clear from context. We want to highlight that it is unknown to the RLHF algorithm (and impossible to tell) whether the preference labels in the dataset were truthfully reported or not.
We can now define what it means for an RLHF algorithm to be robust against strategic manipulation (in the incentive alignment sense). In short, RLHF method is strategyproof if truthfulness is an optimal strategy for every labeler irrespective of what the other labelers report.
Definition 3.1 (Strategyproofness). We say that the mapping (D) is strategyproof if for all i [k), other labelers' data D_, (D1... .......... D_ D++1. ........:....................... D2) and deviation 0 * 8 it holds that
Botss [Ji(FRILHF (D; D_))] Egssnp (FRLMEE D_.)
This property is also commonly referred to as dominant strategy incentive compatibiliry.
We can relax the strict incentive constraint by allowing labelers to have limited incentive to misreport, which provides us with the notion of e-strategyproofness.
Definition 3.2 --Straaeeyypoofnnsss). We say that the mapping TRLHF (D) is e-strategyproof with 0 if for all E [k], other labelers' data D=, and deviation 0 * 6r it holds that
Botiira, [J (T (D. (D.. -.
A few comments are in place. The careful reader might wonder why we define strategyproofness at the distributional level (ex ante) rather than at the level of realized preference labels, e.g.. by allowing labelers to flip preferences after sampling. The reason is that defining misreporting at the level of preference realizations instead of preference distributions would blur the line between strategic manip- ulation and post hoc noise correction, which is not the focus of our analysis. One can imagine that even a (conceptually) perfectly strategyproof algorithm would incentivize the labelers to flip preference re- alizations post hoc in an attempt to better teach the algorithm their reward function by correcting noise. Defining the labelers' strategics over preference distributions instead of realizations ensures a more meaningful comparison between truthful and strategic labeling and avoids these complications.
Learning Objective. We assume here that the set of labelers is representative of the population whose preferences we wish to align to. Our objective is then compute a policy maximizing the average social welfare given by
& W(p, π) = K Σ x).
In the following, we omit whenever the initial state distribution is clear from the context. Let T² = argmax W(p, л) be the optimal policy maximizing social welfare. The suboptimality of policy π is defined as
SubOpt m) W(p, m-) W(p, T).
*While we choose to present our results for mislabeling within the class of BT models for ease of presentation, we want to highlight that our results on strategyproofness in Section 4.1 extend beyond the BT model and apply also when labelers misreport according arbitrary preference distributions.

---

In addition to this standard notion of suboptimality. it can also be insightful to consider the multiplica- tive approximation ratio of policy x that is frequently studied in the computational social choice literature and given by the ratio
7(p,
x(p, = W(A
By definition, this ratio satisfies a(p, x) I 1 and the larger the ratio the better the policy. In the fol- lowing, we primarily use the approximation ratio as a secondary metric to understand the convergence behavior of RLHF method, i.e., when the number of samples is sufficiently large.
3.1 Existing RLHF is not Strategyproof
Unsurprisingly, we find that existing RLHF algorithms are not strategyproof. Exemplarily, we consider two recently proposed RLHF methods for learning from diverse human preferences [37, 7]. Whereas Zhong et al. [37] aims to maximize social welfare like we do, Chakraborty al. [7] consider a maximin objective, that is, they wish to maximize the worst-case utility across all labelers. While this different from the social welfare objective that we consider, does not prevent us from analyzing the strategyproofness of their algorithm or lack thereof.
Proposition 3.3. Existing RLHF methods such as Pessimistic Social Welfare [37] and MaxMin-RLHFF [7] are not strategyproof.
Next, we wish to understand what consequences being manipulable has on the policy performance of the RLHF algorithm. After all, one could imagine failing to guarantee ptrategyproofness but still learning a nearly optimal policy. This in general not the case and we show that the performance can degrade arbitrarily in the worst-case even if only a single labeler is strategic. We show this at the example of the Pessimistic Social Welfare approach from Zhong al. [37].
Proposition 3.4. Let at least one out of the k labelers report strategically. Let ã denote the output of the Pessimistic Social Welfare algorithm [37]. Recall that |00|2 S B and [|o(s, S L. In the worst-case, for sufficiently large. the social welfare of ît is upper bounded as W(+) S E. whereas the optimal social welfare at least W(x*) 2 BL- for any E 0. Hence, the suboptimality of
Pessimistic Social Welfare is lower bounded by SubOpt(#t 2 BL - 3E.
In other words. the policy learned by Pessimistic Social Welfare can be almost arbitrarily bad.
Proof Sketch. We provide a simple example for a contextual bandit where the first labeler strongly disagrees with all other labelers, but can exert significant influence on the computed policy by overstating its preference in dimension of the features that is otherwise irrelevant all labelers' utility (i.c., 0g is zero in said dimension for all labelers).
3.2 Inherent Limitations of Strategyproof RLHF
We have seen that existing RLHF approaches are not strategyproof, but can be manipulated by labelers to the detriment of policy aligmment with social welfare. We now also show that any RLHF algorithm that satisfies strategyproofness must suffer at least constant suboptimality (irrespective of the number of samples or policy coverage) and has an approximation ratio of at most 1/k. We thereby face fundamental trade-off between incentive alignment (strategyproofness)) and policy alignment (social welfare maximization) in RLHF with strategic preference labeling.
Theorem 3.5. The output of any strategyproof RLHF algorithun has worst-case expected subopti- mality at least SubOpt(ft) > K.
k-I where k denotes the number of labelers.
Proof Sketch. We can map each RLHF instance to a voting problem and map र to decision rule f for the latter, such that f always outputs the same alternative (or distribution of alternatives) as does. This construction ensures that if î is stratgyproof, then f is, too. The Gibbard- Satterthwaite theorem [16, 31] says that any strategyproof rule must be either a dictatorial rule or "duple", i.e.. either it always selects the most preferred alternative of a fixed voter, or selects among fixed pair of alternatives. Hence, if is strategyproof, must behave either as dictatorial rule, always selecting the most preferred action of a fixed labeler, or as a duple, always selecting the outcome among fixed pair of actions. The former case leads to low social welfare values for instances in which all the other labelers' rewards are negatively correlated with that of the fixed labeler. The latter leads to low social
5

---

welfare values for instances in which the fixed pair of actions have almost zero value to all labelers. In both cases, the suboptimality gaps are least (A- 1)/k.
Theorem 3.5 implies that even with infinitely many samples, no strategyproof RLHF algorithm converges to the optimal policy in the worst case. This is also reflected in the following upper bound on the multiplicative approximation ratio of any strategyproof algorithm.
Corollary 3.6. The approximation ratio of any strategyproff RLHI method is a(p, +) S +
In other words, any strategyproof RLHF algorithm achieves k-times worse social welfare compared to the optimal policy in the worst case.
4 Approximate Strategyproofnes:: Pessimistic Median of MLEs
We first consider the contextual bandit problem and discuss the extension to MDPs in Section 5, Our previous Theorem 3.5 suggests that without additional assumptions about the problem instance, we cannot reconcile strategyproofness with social welfare maximization. For this reason, we here introduce an additional assumption about the structure of the initial state distribution (i.e., context distribution) and the policy space.
Assumption 2. The set {Eaup (o(s, [(s)]] II] spans hyperrectangle in Rd
Specifically, in the simplest case when Ea-p (o(s, T()))] E [-1, 1]" this means that for any [-1, 1] there exists π E IT such that ||Ex-~ (0(s, TT (s)) =]112 = 0.5
We propose to median rule over learned reward parameters in combination with pessimistic estimates to achieve approximate praaeeyprooffess while maximizing social welfare. To do so, we must first introduce a few key concepts and quantities.
ML.Es and Confidences. Let D; (stid, a af) ofd))ssss be the preference data reported by labeler E [k] where の²ر ~ (-. 8ト., i- a) is sampled from a BT model w.r.t. some (a priori) unknown and potentially manipulated reward parameter Oz. Given the observations D., the Maximum Likelihood Estimate (MLF) of 0, is the maximizer of the tog-likelihood
@ argmaa
log Po Po
18855 300 a.7)).
J=1
We wish establish confidences around the MLE. To this end, let xij 0i8ts, .b))) 6(s a
and consider the covariance matrix Ed. 1 that Ep, is positive definite. Otherwise, n ΣØ= وا ( (xtd)T For convenience, here assume always consider Ep, + X2 for X; >> 0, which has negligible effect on our results when choosing X₂ of order d+log(1/8) (see, e.g., [38]). The confidence ellipsoid around @ML is then given by
C
(9 : 110 O1|SA, I f(d, 8)}.
well-known that when choosing f(d, n, = d+log(k/8) it holds with probability at least 1 that 0g E C2 (see Appendix A.5 for details).
Pessimistic Median Return. A fundamental insight from social choice theory is that under certain conditions aggregating preferences according to a median rule is strategyproof, such as in resource allocation in one dimension [26]. However, in our case, the high-diimessionaliyy of features and reward parameters, the uncertainty about rewards, and the policy optimization pose additional unique challenges that can cause median rule become manipulable by the labelers.
To incorporate our uncertainty about the reward parameters, we consider the pessimistic median return of policy defined as the return of policy w.r.t. the worst-case coordinate-wing median confidence sets C1..... Ck- In other words, we consider the worst-case performance of policies т with respect med(01 ...... 0x), where med denotes the coordinate- wise median and 0, is element in C,, We outline the Pessimistic Median of MLES approach in Algorithm 1.
'Without much additional difficulty we can relax this to ||E.>p (0(s, (s)) - =]112 S E for some > 0 at the cost of additive expressions of order in results.

---

Algorithm 1 Pessimistic Median of MLES (Pessimistic MoMLEss
1: input offline preference data D (D1..... D2)
2: for every labeler E [k] do
3: compute the MLE M from D;
4: construct confidence set C, {0 R.: 1 01|20, S f(d,n,
5: end for
6: get the median confidence set E = {med 1....... 0z): 0, E C, for E [K]
7:
compute the pessimistic median return w.r.t. E given by
( = min Eeup 10, 0(s, (s))) DE
8: return R(D) = argmax n W(T)
4.1 Approximate Strategyproofness
We begin the analysis by showing that the Pessimistic Median of MLES is approximately strategyproof. Perhaps surprisingly. the degree up to which the algorithm is strategyproof depends on the uniform policy coverage of every labeler's data. We discuss this in more detail further below.
Theorem 4.1.
Pessimistic Median of MLEs OK. (aoev/dd/)--tteeenninl -strategyproof labeler i, where K; ga |B_ooo((s, x (+)]]]| is the uniform policy coverage of D..
More precisely, for every labeler i E [k], any other labelers' reports D-; and deviation 0, & 07, with probability least 6, the gain from misreporting is upper bounded as
d log(k/8)
(A -J((((;, S const Ks
n
where the labels in Dj are sampled from Pa, and the labels in Dj truthfully sampled from Po;-
Proof Sketch. The key challenge is that the estimation errors of the reward parameters may uninten- tionally alter the median computation and thereby create unintended incentives for misreporting. To bound the gain from misreporting, we analyze the effect of estimation errors in conjunction with deviating choices of 0; on the learned policy. Using concentration inequalities, we show that the deviation in each labeler's expected return is proportional to the estimation error, which scales as /d/n. The worst-case impact on ptrategyyroofness is then controlled by the uniform coverage coefficient K;, which measures how well the labeler's data constrains policy choices.
Whereas the dd/n factor may be expected due to the construction of the confidence ellipsoids of corresponding size, the dependence on the uniform policy coverage coefficient K; is unexpected at first, since coverage of only the optimal policy π' is usually sufficient in offline RL [29, 12, 36, 38]. However, in our case, we are not bounding the suboptimality of learned policy but rather analyzing the strategic incentives of labelers. This shifts the focus the range of possible policies that could result from different labeler behavior. Since labelers can, in principle, report arbitrarily misleading reward parameters- coaennttrs-ptenntlllll potentially inducing policies far from x bounding their incentive to deviate requires uniform policy coverage rather than coverage of any single specific policy. This ensures that no matter what policy is induced by misreport, the confidence set remains vell-constrained and bounds the potential gain from misreporting.
4.2 Social Welfare Maximization
We have shown that being truthful is approximately optimal for all labelers. Next, we provide guarantees on the suboptimality and the approximation ratio of the Pessimistic Median of MLEs algorithm when the labelers are either truthful or act according to their (potentially manipulating)
"Note that for any positive definite matrix E and vector æ. we can write || = ||>==1/2<||2. It is also worth noting that labeler i cannot influence the coverage coefficient as it only depends on the state-action pairs and not the preference labels. Hence, labeler has influence the incentive strength of the algorithm.
7

---

weakly dominant strategy, which we show to exist. We begin with the case when the labelers are truthful, which is a ( (d/// domminat strategy according to our previous Theorem 4.1.
Theorem 4.2. Let it be the output of the Pessimistic Median of MLEs algorithm and suppose that all labelers report truthfully. With probability at least 1 1 ô:
(V
/dlog(k/0)) max K; k
d d+ log(k/5)
SubOpt(ft) S const
kV
(2)
vE[R]
where K = [ n (+))]]lz is the optimal policy coverage of labeler i.
Proof Sketch. The suboptimality arises from two sources: (I) the deviation of the pessimistic me- dian from the average, and (2) the deviation each true reward parameter from its worst-case estimate in its respective confidence set. The first term follows from median concentration around The second term upper bounded by O( log(k/o))/ng scaled by the worst-case policy coverage coefficient. Here, taking the median over confidence sets introduces an additional factor of k.
the mean, contributing an error Ooggkog(k/d)
IT
We also show that the Pessimistic Median of MLEs algorithm enjoys suboptimality upper bound matching the one from Theorem 4.2 under any weakly dominant strategy it induces.
Proposition 4.3. When the labelers report their preferences according to any weakly dominant stralegy under Pessimistic Median of MLEs, with probability least 6, the output & satisfies:
(Volostk + mmax; k.
log(k/5)
SubOpt(f)) S const
[E(M]
72
where K3 [[ x² (s)]]l[,, is the optimal policy coverage of labeler i.
The bounds in Theorem 4.2 and Proposition 4.3 suggest two sources of suboptimality. The first term stems from approximating the social welfare function using the coordinate wise median, which improves as the number of labelers increases. The second term results from the estimation of the underlying reward parameters, where the use of median rule introduces additional factor of k. Overall, as the number of samples increases and as the number of labelers grows, the Pessimistic Median MLEs algorithm converges the optimal policy.
Remark 4.4 (Suboptimality Lower Bound). The worst-case suboptimality of any RLHF algorithm in our problem setup is lower bounded by 92( e(vdd /d/n). This can be derived using a similar worst-cas case problem instance construction the one in Zhu et al. [38].
We want highlight the performance bounds of the Pessimistic Median of MLES algorithm in two interesting special cases: (1) when there is only single labeler so that k 1, and (2) when all k labelers have identical reward functions.
Corollary 4.S. When there is only single labeler, with probability at least 6:
d + log(k/0)
SubOpt(#t) S const K4
n
When all labelers have the same reward function, with probability at least 8:
log(k/8)
SubOpt(#t S const max No *E[K]
kv
n
The result for the single labeler matches the existing bounds in the offline RLHF literature and is tight up constants. Interestingly, we observe that in the special case of k labelers with identical reward functions, the Pessimistic Median of MLEs avoids the additive O log(k/8)/k) suboptimality but still suffers from an additional factor of k as the algorithm anticipates strategic manipulation and preemptively takes the median over the confidence sets.
Finally,
also derive lower bound the approximation ratio of Algorithm 1.
Corollary 4.6. Suppose W(=*) is constant. When the number of samples is sufficiently large and provide sufficient coverage of the optimal policy, with probability at least - 6, the approximation ratio of the Pessimistic Median of MLEs algorithm is given by ae(p, 7) 2 1 (Vdlog(kk/5)))

---

Extension to Markov Decision Processes
We now extend our algorithm and our previous results to MDPs. Recall that we consider trajectory- wise preferences so that labeler i provides preferences g² over two trajectories 1 and Ti given initial state shd according to BT model Fo, as defined in Section 3. Like before, the MLE of 0, given by the maximizer of the log-likelihood
O argmax
Σ log Po
1 1 )
To construct the confidence ellipsoid around the MLE, let x = Σ (6(8)) d.j (.5) ((5h az
a
with 5-j 5 g.d and consider the adapted covariance matrix Σp. و= x²d (x+م) Note that this agrees with our previous definition in the contextual bandit when H
1.
To derive the pessimistic estimate of the median social welfare, we now consider the state occupancy of a policy т given by gr (s p) : गテ >/ (s = P, T). We can then express the expected return of policy π w.r.t reward parameter 0 Egpp VV (s)] E grgg. [10, o(s [(s))}] and the pessimistic estimate of the median social welfare is given by ((T) = minge's E Be-gz (0, o(s, (s)))]. The
remainder of the Pessimistic Median of MLEs algorithm proceeds the same.
We assume the analogue of Assumption for MDPs.
Assumption 3. The set (Ba-g, x (s))]: π E [T] spans hyperrectangle in Rdd.
Under Assumption 3, obtain the following extension of Theorem 4.1 that shows the approximate strategyproofness of the Pessimistic Median of MLEs.
Theorem 5.1. Pessimistic Median of MLEEs Ó (llu:////-ssttttteeee -strateyyproff labeler with uniform policy coverage coefficient v, max | Ee ( a (s))]]
More precisely, for every labeler E [k], any other labelers' data D and manipulated reward parameter 0, + 0% with probability at least 1 - 6, the gain from misreporting is bounded as
d log(k/6)
J.
J4 D-.)) S const Vi,
where the labels Dj are sampled from Ps, and the labels in D are truthfully sampled from Po:-
The suboptimality upper bounds under truthful or weakly dominant reporting also take similar form their counterparts in Theorem 4.2 and Proposition 4.3. Similarly to before, the coverage of the optimal policy is enough.
Theorem 5.2.
When all labelers report truthfully or report according their weakly dominant strategies, then with probability at least 1 - ō:
(dllog(k/8)
d (k/(
SubOpt(#) S constt
max VS k.
KE[K]
where v/ = [| [Ø(s, n (6))]ll>s)
Note that we can also extend the corollaries from Section 4 to MDPs in similar fashion.
6 Discussion
We studied how to robustify offline RLHF against strategic preference labeling in a pluralistic alignment setting with multiple labelers. We demonstrated fundamental trade-off between incentive alignment and policy alignment and proposed the Pessimistic Median of MLEs algorithm that is based on pessimistic estimates of the median return of policy. We showed that this algorithm O( O(/d/n) strategyproof while guaranteeing suboptimality of at most O(va/t + /d//n). There are many directions for future work. It will be interesting to study strategyproofnes: for non-ling non-linear reward functions, parameterized or otherwise restricted policy classes, well more general preference models to the BT model used here. Another interesting future direction to empirically evaluate the effect of strategic preference labeling on AI alignment and to validate algorithmic mechanisms designed mitigate strategic manipulation. To do so scale, e-g., the context of LLM fine- fne-tuning, can expect scalability come at the cost of theoretical guarantees.

---

Acknowledgments and Disclosure of Funding
This work is supported by the EPSRC Prosperity Partnership FAIR (grant number EP/VO56883/1), and by the ETH AI Center through an ETH AI Center Postdoctoral Fellowship to TKB. MK receives funding from the ERC under the European Union's 's Horizon 2020 research and innovation programme FUN2MODEL (grant agreement No. 834115).
References
[1] Parand A Alamdari, Soroush Ebadian, and Ariel D Procaccia. Policy aggregation. Advances in Neural Information Processing Systems, 37:68308-68833 2025.
[2] Daniel Alexander Alber, Zihao Yang, Anton Alyakin, Eunice Yang, Sumedha Rai, Aly A Valliami, Jeff Zhang. Gabriel R Rosenbaum. Ashley K Amend-Thomas, David B Kurland, et al. Medical large language models are vulnerable to data-poisoning attacks. Nature Medicine, pages 1-9, 2025.
[3] Michiel Bakker, Martin Chadwick, Hannah Sheahan, Michael Tessler, Lucy Campbell- Gillingham, Jan Balaguer, Nat McAleese, Amelia Glaese, John Aslanides, Matt Botvinick, et al. Fine-tuning language models to find agreement among humans with diverse preferences. Advances in Neural Information Processing Systems, 13:38176-3818, 2022.
[4] Alexander Bukharin, Ilgee Hong. Haoming Jiang, Zichong Li, Qingru Zhang, Zixuan Zhang, and Tuo Zhao. Robust reinforcement learning from corrupted human feedback. arXiv preprint arXiv:2406. 15568, 2024.
[5] Stephen Casper, Xander Davies, Claudia Shi, Thomas Krendl Gilbert, Jérémy Scheurer, Javier Rando, Rachel Freedman, Tomasz Korbak, David Lindner, Pedro Freire, al. Open problems and fundamental limitations of reinforcement learning from human feedback. arXiv preprint 1.Xiv:2307.15212 2023.
[6] Louis Castricato, Nathan Lile, Rafael Rafailov, Jan-Philipp Fränken, and Chelsea Finn. Persona:
A reproducible testbed for pluralistic alignment. arXiv preprint arXiv:2407. 17387777777 2024.
[7] Souradip Chakraborty, Jiahao Qiu, Hui Yuan, Alec Koppel, Dinesh Manocha. Furong Huang, Amrit Bedi, and Mengdi Wang. Maxmin-rlff: Alignment with diverse human preferences. In forty-first International Conference on Machine Learning, 2024.
[8] Daiwei Chen, Yi Chen, Aniket Rege, and Ramya Korlakai Vinayak. Pal: Pluralistic alignment framework for learning from heterogeneous preferences. arXiv preprint wxXiv:2406.0846) 2024.
[9] Jie Cheng, Gang Xiong, Xingyuan Dai, Qinghai Miao, Yisheng Lv, and Fei-Yur Wang. Rime: Robust preference- reinforcement learning with noisy preferences. arXiv preprint 17X.v 2024.
[10] Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. Deep reinforcement learning from human preferences. Advances in neural information processing systems, 30, 2017.
[11] Vincent Conitzer, Rachel Freedman, Jobst Heitzig, Wesley Holliday, Bob M Jacobs, Nathan Lambert, Milan Mossé, Eric Pacuit, Stuart Russell, Hailey Schoelkopf, et al. So- cial choice should guide ai alignment in dealing with diverse human feedback. arXiv preprint 2404 10271, 2024.
[12] Qiwen Cui and Simon S Du. When are offline two-player zero-sum markov games solvable? Advances Neural Information Processing Systems, 35:25779-25791 2022.
[13] Kazuki Egashira, Mark Vero, Robin Staab, Jingxuan He, and Martin Vechev. Exploiting Ilm quantization. Advances in Neural Information Processing Systems, 37:41709-41732. 2025.
[14] Shangbin Feng, Taylor Sorensen, Yuhan Liu, Jillian Fisher, Chan Young Park, Yejin Choi, and Yulia Tsvetkov. Modular pluralism: Pluralistic alignment via multi-llm collaboration. arXiv preprint arXiv:2406.1599 15951, 2024.
10

---

[15] Luise Ge, Daniel Halpern Evi Micha, Ariel D Procaccia, Itai Shapira. Yevgeniy Vorob- eychik, and Junlin Wu. Axioms for alignment from human feedback. arXiv preprint arXiv:2405. 14758, 2024.
[16] Allan Gibbard. Manipulation of voting schemes: general result. Econometrica; journal of the Econometric Society, pages 587-601, 1973.
[17] Allan Gibbard. Straightforwardness of game forms with lotteries as outcomes, Econometrica: Journal of the Econometric Society, pages 595-614, 1978.
[18] Shugang Hao and Lingjie Duan. Online learning from strategic human feedback in 11m fine- tuning. arXiv preprint arXiv:2412. 2024.
[19] Jochen Hartmann, Jasper Schwenzow, and Maximilian Witte. The political idcology of conver- sational ai: Converging evidence on chatgpt's pro-envinommental, left-libertarian orientation. arXiv preprint arXiv:2301.01766 2023.
[20] Atoosa Kasirzadeh. Plurality of value pluralism and ai value alignment. In Pluralistic Alignment Workshop at NeurlPS 2024, 2024.
[21] Timo Kaufmann, Paul Weng, Viktor Bengs, and Eyke Hüllermeier. A survey of reinforcement learning from human feedback. arXiv preprint arXiv:2312.14925, 2023.
[22] Hannah Rose Kirk, Alexander Whitefield, Paul Röttger, Andrew Bean, Katerina Margatina, Juan Ciro, Rafael Mosquera, Max Bartolo, Adina Williams, He Hc, et al. The prism align- ment project: What participatory, representative and individualised human feedback reveals about the subjective and multicultural alignment of large language models. arXiv preprint arXiv:2404. 16019, 2024.
[23] Thomas Kleine Buening, Aadirupa Saha, Christos Dimitrakakis, and Haifeng Xu. Strategic linear contextual bandits. Advances in Neural Information Processing Systems, 37:1 11638- 1 116675, 2024.
[24] Debmalya Mandal, Andi Nika, Parameswaran Kamalaruban, Adish Singla, and Goran Radanović. Corruption robust offline reinforcement learning with human feedback. arXiv preprint arXiv:2402.066744 2024.
[25] Jincheng Mci, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans. On the global con- vergence rates of softmax policy gradient methods. In International conference machine learning, pages 6820-6829. PMLR, 2020.
[26] Hervé Moulin. On 1980.
and single peakedness. Public Choice, 35(4):437-455
[27] Chanwoo Park, Mingyang Liu, Dingwen Kong, Kaiqing Zhang, and Asuman Ozdaglar. Rlhf from heterogeneous feedback via personalization and preference aggregation. In 2024 Workshop: Aligning Reinforcement Learning Experimentalists and Theorisss, 2024.
[28] Shyam Sundhar Ramesh, Yifan Hu, Iason Chaimalas, Viraj Mehta, Pier Giuseppe Sessa, Haitham Bou Ammar, and Ilija Bogunovic. Group robust preference optimization in reward-free rlhf. arXiv preprint arXiv:2405. 20304, 2024.
[29] Paria Rashidinejad, Banghua Zhu, Cong Ma. Jiantao Jiao, and Stuart Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34:1 1702--1721 2021.
[30] Shibani Santurkar, Esin Durmus, Faisal Ladhak, Cinoo Lee, Percy Liang, and Tatsunori Hashimoto. Whose opinions do language models reflect? In International Conference Machine Learning, pages 29971-30008 PMLR, 2023.
[31] Mark Allen Satterthwaite. Strategy-proofiee and arrow's conditions: Existence and correspon- dence theorems for voting procedures and social welfare functions. Journal of economic theory, 10(2):187-217, 1975.
11

---

[32] Anand Siththaranjan, Cassidy Laidlaw, and Dylan HadfieldMMenell. Distributional prefer- ence learning: Understanding and accounting for hidden context in rlhf. arXiv preprint arXiv:23/2.08358, 2023.
[33] Taylor Sorensen, Jared Moore, Jillian Fisher, Mitchell Gordon, Niloofar Mireshghallah, Christo- pher Michael Rytting, Andre Ye, Liwei Jiang, Ximing Lu, Nouha Dziri, et al. roadmap to pluralistic alignment. arXiv preprint arXiv:2402.0500 240.000070 2024.
[34] Ermis Soumalias, Michael J Curry, and Sven Seuken. Truthful aggregation of Ilms with an application to online advertising. arXiv preprinl arXiv:2405.08: 05900, 2024.
[35] Haoran Sun, Yurong Chen, Siwei Wang, Wei Chen, and Xiaotie Deng. Mechanism design for IIm fine-tuning with multiple reward models. arXiv preprint arXiv:2405.16276 2024.
[36] Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee. Offline reinforcement learning with realizability and single-policy concentrability. In Conference on Learning Theory, pages 1730-2775 PMLR, 2022.
[37] Huiying Zhong, Zhun Deng, Weijie Su, Zhiwei Steven Wu, and Linjun Zhang. Provable multi- party reinforcement learning with diverse human feedback. arXiv preprint arXiv:2403005006, 2024.
[38] Banghua Zhu, Michael Jordan, and Jiantao Jiao. Principled reinforcement learning with human feedback from pairwise k-wise comparisons. In International Conference Machine Learning, pages 43067-43067. PMLR, 2023.
12

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: We outline the key claims and contributions of this work in the abstract and in the introduction in Section 1 and reference the corresponding theorems and corollaries when doing so.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We discuss the limitations of our work and the underlying assumptions throughout the paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
13

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Every theoretical result is accompanied by all assumptions made. We provide proof sketches of the theorems in the main paper and include detailed proof' in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm.
14

---

(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
Question: Does the paper provide open the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/ httgg/uddee/eeuuuiiieeeeeeeeeeee
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: cttilss.cc/publccguuuuecooo hecpii//guie////eee wtw.oceeuumisssionP....
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
15

---

The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: htt///uuriis.ee
16

---

Answer: [Yes]
Justification:
This research conforms to the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
This work studies how to robustify RLHF to strategic labeling of preferences, with the goal of ensuring appropriate representation of diverse preferences in the computed policy. Hence, we expect our work to have positive societal impact if any.
Justification:
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative socictal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Question: Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses such risks.
17

---

Released models that have high risk for misuse or dual use should be released with necessary safeguards to allow for controlled use of the model. for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember anonymize your assets (if applicable). You either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
18

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non ntn-standard components.
Please refer LLM policy for what should or should not be described.
19

---

A Proofs
A.1 Proof of Proposition 3.3
Proposition 3.3. Existing RLHF methods such as Pessimistic Social Welfare [37] and MaxMin-RLHH [7] are strategyproof
Proof. We construct straightforward examples for each of the algorithms and show that the algorithms are not strategyproof. W.l.ogg we assume that n is sufficiently large with appropriate policy coverage so that the algorithms are able to obtain perfect estimates. We thereby also avoid re-defining the preference model Pg to fit the models considered in the respective work. W.L.ogg. we also ignore the KL-regularization w.r.t. the reference policy Te in MaxMin-RLHE which would only add notational burden. In the following examples, the horizon is set to H 1, that is, we consider contextual bandit problems.
Pessimistic Social Welfare: Suppose there two labelers with true reward parameters 07 (1,0)
and 0g = (0, 1). Moreover, suppose that for all s, we have Φ(8,a) a) = (1/2, 1/2) and (0s b) (3/4,0). 0). If both labelers report truthfully, Pessimistic Social Welfare reports a policy x(s) for all
8 as action a is maximizing social welfare. In this case, labeler receives utility 1/2. Suppose that
labeler 1 misreports as 0 (1, (1) As result, the social welfare maximizing policy is x(s) b. which yields utility 3/4 for labeler 1. Hence, misreporting is beneficial to labeler and Pessimistic Social Welfare not strategyproof.
Max RL.F:: Consider the simple example where 0f = (1,0) and 03 = (1/2,1/2) as well as ((8,a) a) (1/2,1/2) and Ø(s, b) (3/4,0) 0) for all 8. If both labelers report truthfully, the MaxMin- RLHF would compute the policy (()) = a which yields return of 1/2 for both labelers.
However, suppose labeler reports 01 (1, -1) while labeler 2 truthfully reports 6 (1/2, 1/2). In this case, MaxMin RLHF returns policy (s)s
as this maximizes the minimal utility w.r.t. the reported reward parameters. The return for labeler 1 under policy # is 3/4, which means that misreporting is to the benefit of labeler and Max RHF not strategyproof.
A.2 Proof of Proposition 3.4
Proposition 3.4. Let at least out of the k labelers report strategically. Let â denote the output of the Pessimistic Social Welfare algorithum [37]. Recall that |10|| S B and [|ō(s, a)]l2 S L. In the worst-case, for sufficiently large, the social welfare of ft is upper bounded as W(f)
whereas the optimal social welfare is at least Wxx')= 2 BL- 25 for any E > 0. Hence, the suboptimality of Pessimistic Social Welfare is lower bounded by SubOpt(ft 2 BL- - 32.
In other words, the policy learned by Pessimistic Social Welfare can be almost arbitrarily bad.
Proof. We construct a contextual bandit problem, where Pessimistic Social Welfare is arbitrarily bad even a single labeler is strategic. We here assume that Pessimistic Social Welfare receives infinitely many samples from each labeler with full policy coverage.
Let 0f = (0, 1, and 0: = (, 0,0) for all i * 1. Moreover, suppose that o(s, a) = (VT.2 2e 0) and ((s, b) (0, E, vT.2 e²) for all s. Under truthful reporting, Pessimistic Social Welfare computes the policy T(s) a, which clearly maximizes social welfare. In partic- ular, the optimal social welfare is given by W(=*) BVL² 2 B(L V2e). In this case, labeler 1 receives utility zero. However, suppose that labeler misreports its reward parameter as 0- = (0, 0, B). In this case, Pessimistic Social Welfare returns the policy (ss) = b, which has social welfare W(#) E, whereas the utility of labeler is which is the best possible outcome for labeler 1.
As a result, even if only labeler 1 misreports, then W(#) = E and the suboptimality is at least Su)Opt(#) = W(r") that e does not depend on the reward parameter so that any estimation error would have no effect). This means that the suboptimality of Pessimistic Social Welfare can be maximal.
2 BI. - 3e. We can choose 0 arbitrarily small (in particular, note
L
20

---

A.3 Proof of Theorem 3,5
Theorem 3.5. The output ग of any strategyproof RLHF algorithm has worst-case expected subopti- mality least Su) 2 k=1, where k denotes the number of labelers.
Proof. Suppose for the sake of contradiction that the (worst-case) suboptimality gap of ń is h-1 for some O. We show that if this were true, we could construct voting rule based î that is strategyproof, non non-dictatorial, and onto at least three alternatives, contradicting the Gib- Hard-Satterthwait theorem [16, 31]. The rule does not exist. We will consider the case where ā is deterministic and discuss how the proof generalizes to the case with randomized ft too.
theorem asserts that such voting
Specifically, consider a voting instance with & voters and m alternatives a):-..;am am. A voting rule maps every possible preference profile of the voters to one of the alternatives.
To construct a voting rule based on Åt, we first map every voting instance Ty =x= (<1,..., [k)) to an RLHF instance /RLHF follows.
Let there be one state (so omit the state in what follows) and m actions 01...., ams each corresponding to an alternative in Tv-
The feature embedding é maps each action ag to the unit vector whose é-th component 1.
Let there be k labelers, each corresponding voter in Tv. Each labeler i's parameter 07 vector in which the é-th component is defined as follows:
1 if a is the most preferred alternative according to voter i's preference order X; in Iv.
- -1- 8 (for a sufficiently small 8) if az is the second most preferred alternative according -4z-
- 5. (m j) if ag is the j-th most preferred alternative, 2, according X
The parameters ensure that each labeler i's preference over the actions is the same X
With the above map from lv to JRLHF. then let be voting rule that outputs alternative as म outputs action ae in |RLHF. Clearly, f must be strategyproof given our assumption that î is strategyproof and the fact that JRLHF preserves the preference orders in lv. We next argue that, given the assumption that स has a suboptimality gap of at most k-1 C, f must be non non-dictatorial and onto least three alternatives.
is Non-Dictatorial Suppose that f is dictatorial; say, it always outputs the most preferred alternative of voter This means that must output a₁ on the RLHF instance that the following Iv =x instance maps to:
al -1 02 21 -1 am -1 am
Q2
-4 03
X am 34 for all 2.
However, this contradicts the assumption that the suboptimality gap of it is at most k-1 c. To see this, note that aj achieves social welfare in JRLHF, while d2 achieves social welfare 1c(1 8). The suboptimality is then least k-1-6k k-1 when 8 +
5k k
f is Onto. Similarly, we argue that f must be onto at least three alternatives by considering the set of all possible voting instances where all voters' preferences are identical. In this case, मे must always output either the most the second preferred actions of the labelers in the corresponding RLHF instances; otherwise, the suboptimality gap of ग can be arbitrarily close to 1 when ó + 0. Consequently, when all possible preference orders are considered, म, and hence f. must be onto at least three different alternatives (suppose that 2 4).
As result, we obtain voting rule that is strategyproof, non-dictatorial, and onto at least three alternatives. This contradicts the Güibard-SSaterthwe theorem. The stated lower bound on the suboptimality gap then follows for deterministic policies.
21

---

Randomized Policies. To further argue that the same bound holds even when ń is randomized, we invoke a generalization of the Sebbard-Satterthwaite theorem to randomized voting rules [17], which states that a voting rule, if strategyproof, must be probability mixture of dictatorial rules and "duples". A voting rule a duple if it restricts its outcomes, over possible instances, to a fixed pair of alternatives.
Similarly to our approach above, we construct a voting rule f based on ग the same way we did above and argue that, f is strategyproof and has suboptimality gap of k-1 for some e 0, then cannot be probability mixture of dictatorial rules and duples.
Suppose for the sake of contradiction that f is mixture of dictatorial rules and duples. Consider the following set of voting instances (<*)). each involving set of alternatives (a1...., Ok .i..... bx J. l + K) In each instance <'= (<1..... +7,,, the preference order - ranks
K 4/c (hence, a, first, by second, and all other alternatives according to the order d1,.... Okk, bj b1....,b.. bb.
By assumption, f is mixture of dictatorial rules and duples. Now that there alternatives while each duple selects at most two alternatives, there must be at least one alternative among bi....,br bx that is selected by the duples with probability most 2/K: W.l.o.g,, let this alternative be b and consider the instance =i, in which each voter ranks the first and bi the second.
than K
Clearly, in this instance, the policy that outputs b1 deterministically achieves social welfare k(1 6). Moreover, any other alternatives yields social welfare of at most 1 + ôrak, as each of these alternatives is ranked first by at most one labeler and third or even lower by all other labelers. Since selects by with probability most 2/ it is at most
does म. This means that the social welfare achieved by
2 K
(1 (1-x)
2 K (1 ōmk) < ek/2 Ōmkk.
k(1 6)
5)+
This gives a suboptimality gap of 1//2+++mm k(1-6)
k-1 when d + O.
A.4 Proof of Corollary 3.6
Corollary 3.6. The approximation ratio of any strategyproof RLHF method is a(p, f) S
Proof. This is direct consequence of Theorem 3.5.
A.5 Proof of Theorem 4.1
Before we begin with some preliminaries that we will repeatedly use in the proofs of both Theorem 4. and Theorem 4.2. Firstly, recall standard MLE concentration bound, which can be found, for instance, in [38].
Lemma A.1 (MLE Concentration Bound). In the contextual bandit problem, with probability least 1 8,
d + log(1/5)
10 1|,,,,
const
72n
1 exp(-1.B) (I)(..)).. Note that we here assume that the covariance matrix D, is positive definite. Otherwise, consider ED, + AI, which adds an additive term XB2 the square root.
Proof. See, e.g., [38].
Lemma A.2 (Median Concentration Bound). Suppose that 0I....,0y Bdd are sampled i.i.d. from o-sub Gaussian distribution. Let Omed be the coordinate-wise median and dayy the average of 9 91...., Oz. Then, for a universal constant e > O, it holds that, for every t > O,
ck12
TP (10meed 0mwz)l2 21) & 2exp
do
22

---

Hence, in other words, with probability at least 1 5:
dloo(1//))
|| 0aned
Buvgl Saglll - O
Proof. We begin by proving the median concentration in one dimension. To this end, let 6 denote mean the distribution. Since each 0, is o-sub-Gaussian with mean oggg centered variables
X; 0: Dv satisfy
C2 u
([[ 2 u) S 2 exp (
o²
for some constant C2 0. To control I9(0 medd
Davg 1), note that if m 2 Girg + t, least half of
the 8 are at least t + t. Define
p P(8: 2 0" t) =((;; 2 t).
By sub-Gaussianity, Binomial (k, p) distribution. Then P(0mod ing bound implies
exp ( cat Let Y = Σ 100 2 0r + t). which follows
0F)
+ S P(Y 2 k/2). Chernoff or Hoeffd-
P(Y 2 k/2) & cxp (-kD(2
where ( p) is the Kullback-Leible divergence between Bernoulli(12)) and Bernoullip)). For p < 1/2, D p) bounded below by constant times (1/2 p)?. Hence, there exists 01 such that
c1kt? o2
P(Omed 2 Og + exp
kt _ By symmetric argument, P(Omodd S Olvg 1) exp
(
Combining these, we obtain
P(l0med Gigl t) < PP0meed 2 0 + + P0 S 0o.g - < exp( e kt? o²
From Hoeffding's s inequality we get an analogous bound for TP( IP(110av 0ig 2 t) so that we get the desired result for d using the triangle inequality |Omed Gargl 10med 0ivg! + (liv Oavgl-
Finally, this translates to bound in d > 1 dimensions by using Jensen's inequality
d
1mmed Oavg ||2 =
Σ
(0med.) - Onwe.s)
S Vd max 10med.. Ome.i JE(d]
f=1
and applying the previous bound for each dimension.
We are now ready prove Theorem 4.1
Theorem 4.1. Pessimistic Median of MLEs is ((k::/d/n))sstarreee strategyrrooof labeler i, where K; max, [x~plo(ss (s))]lls is the uniform policy coverage of D
More precisely, for every labeler [k], any other labelers' reports D=, - and deviation o, + 07, with probability at least -8, 8, the gain from misreporting is upper bounded as
S const K; d log(k/8)
J, (,(, - -
n
where the labels DD are sampled from Pa and the labels DJ are truthfully sampled from Po;-
Proof. We begin first with the case where every individual can directly report their reward parameter the algorithm, hence, removing the noise and uncertainty from the process. In this case, show that Pessimistic Median of MLEs is exactly strategyproof.
Note that for any positive definite matrix and vector æ, we can write || = ||> 1/2 It is also worth noting that labeler i cannot influence the coverage coefficient as it only depends on the state-action pairs and not the preference labels. Hence, labeler has influence the incentive strength of the algorithm.
23

---

Let us begin with the case where we obtain infinitely many samples with appropriate coverage so that C, {6,} for all individuals i E [k]. We need show that reporting of is the optimal strategy for individual i irrespective of the other individuals' strategies.
Case 1 (direct access to .1.....00
0x):
The following two basic lemmas will prove useful.
Lemma A.3. Let 0_; [[x=1)xdd be fixed arbitrarily. For any j E [d] the following holds:
3 0 and med(O -ij. (/.5) < O, then med(O-i.j. 02,)) < 0 for all 0g E Rd.
Analogously, if O < 0 and med(0-i.. 07,5) > O, then med -i. 02s) > 0 for all 0; E IR..
Proof. W.l.o.g. let 0i 0 and let 0, E Rd. Suppose that 0,,, 0. It follows directly that med(9-i,j, {t,)) (f- f- Alternatively, suppose that 8,, O. Since med(f-i.j- B%,,)) O, it means that the median equals some 01,5 < 0 with + i. Hence, the median does not change for any alternative choice 8 0.
We assume hyperrectangularity, which allows use to decompose the eeward-maximinn policy as follows. For given policy æ, let 2 E x [s))] E I denote its feature occupancy and let Zn.j be its j-th entry. W.L.o.g. we here assume zn.j E [-1,, 1]. , but any other lower and upper bounds can be considered the same way.
We denote the optimal policy w.r.t a reward parameter 0 as (0) argmax J0 From Assumption 2 it follows that the optimal policy x (0) is such that (0),) = - for 0j < 0 and (0)()), = +1 for 0g 0. This yields an equivalence between reward parameters that have identical signs. In particular, this provides us with class of reward parameters that induce an optimal policy w.r.t the true reward parameter t7.
(0) Lemma A.4. Let 0 E IRd. If sig)( = sign(0z), then 07 - 2 02g ( for all
E Rd.
Proof. This follows from the structure of the optimal policies x (0) under Assumption 2.
We fix everyone's reported parameter 0_, except for individual i. Moreover, let 0, + 0 and let j = med (0,, 0s) be the coordinate-wise median w.r.t. 0,. Similarly, let μ² med 8r be the coordinate- wise median w.r.t. 0" We will now show that Jaz (#("") 2 Jo (f))). i.e., reporting 0f the optimal strategy for individual under the Pessimistic Median of MLES algorithm.
Since we here assume direct access to the reported parameters, given reported parameters 01, Og. Pessimistic Median of MLEs computes the optimal policy w.r.t. the median μ med(0; (a00(01.... ......... 0s). ie., â = x² (14)= = argmax, EE (T). We here assume that the μ p-maximizing policy is unique and otherwise use lexicographic tie-breaking. Clearly, if signs(Ø") sūgns( then the policies Å (2²) and A (M²) are identical.
Next, consider any j E [d] so that sign(pz) + (āgn Suppose that sign(1ç) sign(Oi,). In this case, Lemma A.4 tells that 02,- =a(a)).j 07, Z=(a),j- Hence, in any such dimension j. μ² implies policy that outperforms the policy maximizing w.r.t. labeler i's true reward parameter gr. Hence, misreporting 0., * 0i cannot be a strictly better strategy than truthfully reporting in dimension j.
Suppose that sign(n;) * sign(07,) ). In this case, Lemma A.3 implies that sign(ā,) = sign(uç), which implies 07,3 _a()).) = 07g ()()")d Once again misreporting is never strictly better strategy than truthfully reporting 0,-
We have thus confirmed that reporting 0 is optimal irrespective of the other individuals' reports A_,-
24

---

Case 2 (direct access to 8,, but not 0-;): Let C-v denote the product space of confidence sets derived from the preference data D_ all labelers but labeler i. Once again, the key lies in the observation that the assumption of hyperrectangularity implies that the labelers get to strategize over each dimension independently.
The main concern that we must alleviate is that, by taking the minimum over the confidence sets, misreporting becomes beneficial for the labelers. To this end, let fg be the report of individual i, which for now assume be directly observable. Given preference data D- and 0,, the Pessimistic Median MLEs computes a policy maximizing
min Σ (ned(f-a.j Oa.)), B
[o(s, ((s)])
Suppose that 0i > 0 for j E [d]. Clearly, by design of the median, for any 0 it follows from the same argument as in Lemma A.3 that misreporting either has no effect on the policy (if the report is 8t, 0), can only have adverse effect for labeler i (if the report is 8G, 0). Hence, it is optimal for individual to report 8f irrespective of the other individuals' reported preference data D_, and the confidence sets that construct.
Case 3 (no direct access to ., reporting is a dominant strategy for every individual E [k]. We will now see that this is in general no longer true when an individual cannot directly share their reward parameter with the algorithm. The reason lies in unintentional changes in the sign due to estimation errors and confidence sizes.
0k): In the previous cases, have shown that truthfully
In the following, we assume that the preference data D-; of all labelers but labeler i are fixed arbitrarily and C-; are the corresponding confidence sets that Pessimistic Median of MLEs constructs. From Case 2 we know that the policy
ft (0,) = argmax min sen e_iEC_.
0-.) Do. (()))
is preferred over any other policy A (C,) computed w.r.t. any confidence set C, given by R (C+)
argmax min =ell A,EC, .eC.
min
(med(0,, ( Bes (s))))
ie., Jo (+x( J (C.)) for any confidence set C..
Let us now consider the confidence C derived from Dú, which sampled according the true reward parameter 0r. By construction of the confidence sets, with probability at least 1 8, it follows from Lemma A. that for any E C.::
d + log
|10: - 01112,, 007-01112p
|10]
LYD + [|0MLE
20
n2n
We compare the difference in return w.r.t. 07 of policy (,)) and (c())). To do so, decompose the difference as follows:
Jop (ft - Jor (C,()))
= -(o;
min Jo Je (f.(0)))) 0,EC;
min Jo, (+t( Jo; Jo; (CT))
0.EC;
Using Cauchy-Schwand the first difference can be rewritten and bounded as
max (0) 0,, =*()))) S ||0] 0, IlE,, ||==(0))
4.eCt
We then further decompose the second difference into
min P.EC;
(+:((()))) Jo; (+;));;)
= =( -mii
min Jo. (07)) Gec;
min Jo, (+(()) + O,C;
min
Jo, (+((C))) - Joy (ox(1)())))
25

---

By definition of (C(),,, we have mino,ec; (0,, ( 2 ming, EC; (0,, za(0r)) so that the first expression on the right hand side is less or equal to zero. Since 0f E C we also know that ming,e;; (T) S Jo; (T) for all π E II. Thus, on the good event when 0g E Cj. we obtain:
d + log(116)
Jo- (+,(+())))) Jo: (#t(C)))
s
|| #t (0))
+ log(1/8)
s sCV
max xell
E S [o(s, 17 (
P
Note that the coverage coefficient on the right can be written as |> 1/2 BB- (o(s, (
We have here (arguably coarsely) upper bounded the coverage of +((;) ) by the uniform policy coverage K2 max, [sspp π [ls))] of labeler's i data. We must do this here the policy n. (0²) notably depends the other labeler's reported preferences D_, and is thus hard to control or express explicitly. Overall, we have thus shown that being truthful an approximately dominant strategy for labeler under Pessimistic Median of MLEs. Hence, Pessimistic MoMLEs is -strategyproof.
Remark A.5. As we wish to ensure strategyproofness, i.e., trathfulness is a dominant strategy. could not control the needed coverage carefully, but had to take worst-case perspective and consider uniform coverage of all policies as quantified by K4. Naturally, we would expect to improve upon this when considering incentive- incentive-comppaiileee compatibility instead of strategyproofness. ie.. showing that truthfulness forms an equilibrium but is not necessarily a dominant strategy profile. In that case, can show that Pessimistic Median of MLEs is approximately incentive- incentive-compatiby compatible where instead of the uniform policy coverage the coverage of the output it" of Pessimistic Median of MLES given that everyone reports truthfully is enough. In other words, the coverage coefficient is given by [EeSpll(ss ft (8)) S Ki.
A.6 Proof of Theorem 4.2
Theorem 4.2. Let ît be the output of the Pessimistic Median of MLEs algorithm and suppose that all labelers report truthfully. With probability at least 8:
SubOpt(#)) S const- (V dlog(k/0)) max K. kV
d log(k/0)
<E(M]
where K² E xt" (s))]]lss is the optimal policy coverage labeler i.
Proof. We will decompose the suboptimality in various ways. To this end, let nt denote the policy that maximizes social welfare and let स denote the policy computed by Pessimistic Median of MLEs. Recall the definition of the set of medians w.r.t. confidence sets Ci,..., Cp as E = (med(0 ( 0z): 0, Ci} and let of = 1 Σ 0. 0, C.) denote the set of averages. For convenience, we define for any m
2 Resplib(s (s))).
Moreover, we let
avg = avg( 0 and 0 =
correspond to the true average and median, respectively. We now decompose the suboptimality as follows:
SubOpt(#t)
Σ 10 2xm (0) 2+)
(0iig zn (8ivg- za)
(8) zm-) min (8, 2m
+ Beal
min (8, x (8ivg: za)
feal
26

---

In the following, we work on the good event such that B; E C, for all i E [k]. Using union bound, we can show that this event occurs with probability at least 1 k d'
We can bound the first term (I) using that the confidences concentrate around the true parameter at a rate of /d/n according to Lemma A.1 and considering the worst-case coverage of the optimal policy over all labeler's s data. For some constant > 0, this yields
(0 2xx) min (0, x.
max (0ax(0 avg 0, xxx) 0E
k Σ
max ko 01EC1
max
10
0g Zx,))
02 EC 1=1
max (0) 0s, Bx-) R,EC;
max 6,EC,
110
0, DEED || 11111
d + log(1/0) 1
xx* Exp
22n
k
d + log(1/8)
max
xxx !!x
72n
(E(A)
Bounding the second term (If) more involved as the policy á is not maximizing the average but the pessimistic median. We further decompose the second term into four parts as follows:
min (0, 2x-) (05rg: xx) Be
min (f, xx-) (i xx-)) B8
min(e. xn-) min z*x)
BE
BE'6
min((. (0 =x) DE
(0med 2+) + (Ommed 2*) - (0lmg za)
We first show that the second and third term are less or equal zero. We have
min 2.-) S min Za),
BE
05
since à maximizes minsge (0, xx) by definition of the Pessimistic Median of MLEs. Moreover, we see that
min (0, z+) S (fmed: x*), REE
as the true median is contained in the confidence set & on the good event when 0 E C. Hence, both the second and third term can be bounded from above by
To bound the first term, we once again decompose the expression as follows:
min (0, New
min (0, x DE
min lea
(0
0 aig::
Zxx + (0)
Tmeds Zn
max @
0, Zx+)
DET med
(b)
(a)
(e)
Similarly to before, using Lemma A.1, we bound (a) as
+ log(1/8)
min of
0 xx-) S <c
max
x 11s
n2n
iE(k)
For (b), it follows from Swwwwrzhwwaaccc.. and Lemma A.2 that
dlog(116)
(A ivg
guedd _ S ||0 0meillz 1| m 1l2 S e/
1| 122-112-
(4)
27

---

For (c), first note that we can write the difference between two medians as the telescoping sum
me 0%) me 0k)
med 0,41 0s.) -eed0" 1..... ...... 0--1: 1. .k).
By definition of the median, each difference on the right hand side can be bounded in terms of the difference 02 0z. Using Lemma A.l and the fact that 0, C2 for all E [At]. we obtain
k
max - 0, 2x,) - PE
110
0g 0,11z0,
Z 11x
d + log(1/5)
S cky
|| ||2_!
72n2
The proof is complete by combining these bounds.
A.7 Proof of Proposition 4.3
Proposition 4.3. When the labelers report their preferences according any weakly dominant strategy under Pessimistic Median of MLEs, with probability at least 6, the output â satisfies:
(Valosth
d log(k/0)
SubOpt(ft const.
+ max K. [E[k]
kV
72
where K. = [os, (+)]]lx is the optimal policy coverage of labeler i.
Proof. Let E Rd be the reward parameter according to which labeler E [At] samples its preferences that
under weakly dominant strategy. The intuition for the result is fairly straightforward describe it here first. First of all, we have seen in the proof of Theorem 4.1 that due to the median rule a labeler cannot achieve an individually better outcome by misreporting the sign of its reward parameter (see Lemma A.3 and Lemma A.4). As a result, 0g will have identical signs to 0 but potentially exaggerate its magnitude. Crucially, such exaggeration cannot worsen the suboptimality as it only helps to prevent flipped signs as we are taking the worst-case over confidence sets. Here, it is also worth noting that the primary reasons why Pessimistic Median of MLEs is approximately strategyproof are the estimation errors and the pessimism selection of the median over potentially large confidence sets.
Any weakly dominant strategy must preserve signs. Assume for contradiction that there exists some coordinate j such that 03 >> 0 but the labeler's 's chosen reward parameter is such that 0,,, < 0 (or similarly 0 < 0 but f,g > 0). By the hyperrectangular assumption, the Pessimistic Median of MLEs algorithm outputs policy that maximizes each dimension of the feature space independently. Specifically, æa. = Exxp(o(s, # (s))ls will be positive the considered median is positive and vice versa. Hence, by nature of the median, flipping the sign of coordinate can only have an adverse effect for labeler (see Lemma A.3) and no such strategy can be weakly dominant.
By the same argument, if Oi,- < O but Oig > 0, then labeler i would risk pushing the aggregator's dimension j to positive, contrary to its true negative preference, and thus risk reducing its true utility in that dimension. Hence it cannot be a weakly dominant strategy to flip signs in that scenario either. Consequently, in every dimension j. a weakly dominant report 0 must preserve sign(O..,) sign
Exaggeration benefits Pessimistic Median of MILEs. By the hyperrectangular ("sign-based") structure, the decision in each coordinate j of the learned policy depends essentially on whether the aggregated median positive or negative. Pessimistic Median of MLEs aggregates each labeler i's confidence set C; by taking coordinate-wi the median, chooses exactly one 0t,, from each C, and then takes the median value among these k numbers. Assume that the labeler i's original (w.l.o.g.) positive coordinate is 0r whereas its inflated coordinate is 0z,5 > 0i Under the inflated reported reward parameter, the labeler's 's MILE and confidence set for dimension shift toward strictly larger positive values (note that the covariance
median over a selection 6; E C, Thus, to form
28

---

matrix Ep, is positive definite). Consequently, the set of considered medians Htj for μ E & (i.e. all possible ways to pick f, C, for i ...... k and take their coordinate-wise median) does not move down: it can only stay the same or shift to more positive values. Intuitively, replacing one of the entries by a strictly larger positive number cannot decrease the median.
Hence, when labeler i is misreporting 8.g such that 0,,5 8% (while keeping the same sign), this cannot worsen the suboptimality of the final policy, but only, in some special cases, strietly lower suboptimality by "protecting" the sign within the confidence set. Since this argument holds for any dimension j. follows that an entire sign-preserving inflation by labeler cannot yield a higher suboptimality than the truthful report would.
A.8
Proof of Corollary 4.5
Corollary 4.5. When there is only a single labeler, with probability at least 6.
SubOpt(ft) S const Ki + log(k/6)
When all labelers have the same reward function, with probubility at least 6:
RV d log(k/6)
SubOpt(#t) S const- max ni sE]k]
Proof. When the claimed result follows directly from setting & 1 in our previous subopti- mality bounds (see Theorem 4.2).
Next, suppose that all k 2 1 labelers have the same reward parameter 0 = 0j =... 0z. As result, the true average and median coincide and have 0" 0ävg O 0meed To bound the suboptimality of the Pessimistic Median of MLEs algorithm in this special case we take the same steps as in the proof of Theorem 4.2 in Section A.6 with the difference that the expression (b) in equation (3) is zero since 8* = f = 6 This yields the claimed upper bound.
A.9 Proof of Corollary 4.6
Corollary 4.6. Suppose W(x*) is constant. When the number of samples is sufficiently large and provide sufficient coverage of the optimal policy, with probability at least 1- 6, the approximation ratio of the Pessimistic Median of MLEs algorithm is given by alp, F) 2 1 O (Vddlog(k/8)))
Proof. For n sufficiently large and sufficient coverage of the optimal policy, Theorem 4.2 implics that with probability at least
8:
d dlog(k/0)
SubOpt(#) W(T") W(+) - <ev
for some constant e > 0. As result, the approximation ratio is upper bounded as
app, = W(#) = W(=")-W(H 2 1 vv W(T+)
d (kg(
W(T*)
where we used that W(=*) is constant by assumption.
A.10 Proof of Theorem 5.1 and Theorem 5.2
Proof. We can prove Theorem 5.1 and Theorem 5.2 in a similar way we proved the analogous results in the contextual bandit problem. We refrain from reiterating and restating all necessary steps to prove these results as they are almost identical to before. Most importantly, similar MIL concentration bound holds for MDPs as for contextual bandits.
29

---

Lemma A.6 (MLE Concentration Bound for MDPs). With probability at least - 8,
d log(1/6)
10 8 1111 I const
7
where y= 1/(2+ exp(-HLB + exp(HLB)) The covariance matrix ED. is given by Ep, Ej=1 x1d (x²)) where xi1 ( a ( ,a,,)) with s = =| gh..
Swapping the initial state distribution p (i.e., context distribution) for the the state occupancy 4n as defined in Section 5, we can follow the same line of argument as in Section A.5 to prove Theorem 5.1.
B Computational Complexity
We now consider the computational complexity of computing the pessimistic median return. First, consider the contextual bandits formulation, and then consider the general MDP setting.
B.1 Contextual Bandits
Recall that we construct the confidence sets
C (0 E R | - 01) S S 8)}.
Then, the (coordinate-wisg median confidence set is defined as
E
0x) 0, E C. Vi E [k]]
and we aim to solve the following optimization problem:
max ((()) min Ee-p (0,, 6b8 (()))]]
TELl
8E
In first step, we show that the function ((T)) is concave. Indeed, consider two policies x1, and 72
Then,
W(aT1 a)T2)
min Egcu
Σ (aTI(a) + al)=a)((()) (0, (l a))
DES
min Eamp 0E%
Σ am (a) (a)(0,((s,)))
min Eg-p D6
W(T)) +1 a) W(22).
Therefore, W(-) can be efficiently optimized using projected gradient ascent long we can com- pute the gradient efficiently. For given n, we have V V= = p(s) (ø(s, a), 0+) where
0 E argmin Es- [10, 6(s (s)))
(5)
#E
In order show that the gradient V (m) can be efficiently computed, need to show that 0* can be efficiently computed.
The set 8 can be arbitrary, but can write down the following equivalent optimization problem involving linear and quadratic constraints:
min 0.
Egep (0, als, (T)))})
s.t. M - 0111E0; 5 n(d E
(6)
Σ 100) - 0.(i)l Σ Or(i) 0.(G) VE E Vj
The first set constraints encode that 0; E C2 for each that 0(j) is the median of (,))).... ()) for each coordinate [d]. The above optimization
i [k]. The second set of constraints encode
30

---

problem might be non-convex, and instead we will consider the following alternate optimization problem:
min 0,(0, hele)
(0,, + M Σ zg.
s.t. 0, E C, Vi [k]
2. 2 0(j) - 0,(,) 2. 2 0,(0 -
Vi -
[k],j E [d]
The next lemma shows that we can choose M and n to recover an approximate solution of the original optimization problem (6).
Lemma B.1. Suppose (0', he(s) is optimal solution to the optimization problem (6), and (0 (0.(0%))EIS) bE(s) x²) is an optimal solution to the optimization problem (7). Then,
2vd
Ex-p 10p ((, - E0 (((,,(()))))) + M Σ
[(d, [dd,,0) n,
Amiin \
and
0 - -P s Σ (P( -200 - Σ 4
2BL
v0.
M
Proof. Let define z - -001)] (i)l Then have the following inequality:
80m 7 (6))}|| + M Σ c I (0' ,6s x (+)))] + M Σ A/..
Without loss of generality, we can assume oL, = [5 - 6.( Hence,
2 = (2 0 = -) - 00 + --)
- - (((() 2 - -000))
Substituting this bound, we obtain
E E ((ss - E. (0), 00s (())))]
s M Σ (1) - 07( + M Σ (1) (2) + M >
(j
i.j
1
S M Σ |10] 111
< MM Σ va 00 0
Vd
2/d
M
Amiu (ED.) 100 0.llz $ M
[d, 8).
Amin (ED,)
The second inequality follows since 0² is coordinate-wise median of the parameters (0) heej) We also use the assumption that under uniform coverage (ED,) 0.
We now bound the violation of constraints of the solution 6². Indeed for any 0, (0p hejM and
{1Ō()) 62 (2)) i. since 8² as 8², [07) (e())) faithes is feasible solution to the optimization problem, we have (7):
Ee-pl 100 o(s (())))) + M Σ 2f, S
M Σ (0) -
After rearranging this yields
Σ (0( P05 Σ ((0) 00()
1 E, E0 8², 6(s (s)))
1
2BL
M
M
31

---

Since n[d,n,6) = O[ ( we can choose M 2BL and n 4B (dd(ollg((()/ and observe that 0² is e-approximately optimal and s-approximate coordinate-wise median of the parameters {0] he(k)-
(min, Amiu ASn,
General setting. Next, we consider the general setting where the state space can be arbitrarily large. We will assume that the policies are parametrized by a class of parameters y S R. i... == (Tp : & }. For example, the softmax parametrization models as the following class of policies:
exp(1) ((s,a) Es exp(x ((s, b))
IT
Th 8)
Vs li s <By
now aim solve the following optimization problem:
Σ [=m(abs(0,000s.0)
max W
= min Reup
NEW W
6E'6
The gradient of the objective is given by
W(v) = Eguu
Vomplala)00
where
#* E argmin Egvu (8, Ø(s, n (s)))).
NES
The above optimization is finiteddimensional (Okk)) even when the number of states very large and can be approximated using optimization problem (7). Thus, can perform projected gradient ascent steps to solve the optimization problem max WV)). However, unlike the tabular setting, the objective is longer concave. It is known that under softmax parametrization, the expected return satisfies a non-uniform Dollyk-LLojssewize (PL) condition [25] which guarantees linear convergence of gradient ascent method. We believe that similar conditions should hold for the function W( but leave the verification to the future.
B.2 Extension to Markov Decision Processes
We start with the assumption of tabular MDP. We aim to solve the following optimization prob- lem:
max W(T) min Esrgg [10, ((s, (s))))]
tEll
NEW
W(T)) is non-convex function of policy æ. However, it is concave function of qr. the state-action occupancy measure of policy æ. We can write down the above optimization problem in terms of state-action occupancy measure follows:
H ΣΣ
max mix H
(n a) (0, o(s.a))
DES
k=1 8,0
s.t. Σ
(s, p(s) Vs
Σ (h,1(s,b)
Σ qu(s a) Vh [H -1. s'a
Here, the last constraints encode Bellman-flow conditions which ensure that the solution is a valid state-action occupancy measure. Now we can write down stochastic gradient ascent step as a++1 Proj(g, ft + v)V)) Here the Proj(.) refers projection onto the feasible set defined by the flow conditions. As the number of states and actions are finite and small, the projection step can be computed efficiently. We now verify that the gradient (g) can be computed efficiently. The gradient is given by
V)
(s a) (8* ((s,)s))))
32

---

where
H (s, a) (0, ((s,
0" E argmin
OE
H h=1
8,0
Now we can proceed similarly to the contextual bandits setting and compute an approximate solution of the optimization problem above.
min 9, he
H ΣΣΣN (n(s,a) ((, + M
Σ
Zid
h=1
8
(8)
s.t. 0, E C. Vi [k]
2. 2 8()) - 0,0), 2. 2 0,() Vi) [K] [d]
General Setting: In the general setting, computing the projection step becomes infeasible as the number of states (and constraints) can be very large and possibly infinite. Instead, we again adopt a policy parametrization as discussed in the previous subsection. In particular, we assume that the policies are parametrized by a class of parameters V C Rd, i.e., II T solve the following optimization problem:
W We now aim to
max W(+) = min Eayp [V (s)]
NEW
DES
The gradient of the objective is given by
V W(F) Eemp Vo. (o)) (s)
where
O' argmin E B(s,a)=er, ((, a)}
DE'
C Experiments: Simulating Strategic Preference Labeling
We here conduct small-scale synthetic experiments that simulate strategic preference learning and serve as a preliminary empirical evaluation of the proposed methodology.
Experimental Setup. We simulate strategic labeling behavior by performing approximate gradient ascent (i.e., simultaneous perturbation stochastic approximation) on each labeler's utility J₃ w.r.t. the labelers' internal reward parameters 0,, which govern their preference distribution P3g We adopt this simulation approach from prior work on strategic contextual bandits [23]. Each labeler initialized their ground-truth reward vector 07, which is sampled from multivariate Gaussian. Labeler strategies are optimized for 200 steps. Since this process requires repeatedly re-labeling comparisons and re-running each algorithm. we focus on small problem settings in a contextual bandit formulation. All results are averaged over 5 random seeds, and we report standard errors. The results below are for embedding dimension
16, number of labelers k 5, and offline samples 20, 50, 100, 200. We compare the following approaches: (a) Naive MI.Es that simply computes the MI.ss given the preference data and optimizes a policy against the average reward estimate to maximize social welfare; (b) Pessimistic Social Welfare [37], which is the pessimistic version of Naive MLEs; (c) Median of MLES, which optimizes a policy against the reward function derived from the median over MLEs; (d) Pessimistic MoMLEs, which is proposed algorithm and outlined in Algorithm 1. We report the policy suboptimality under both truthful and strategic labeling.
Results. Overall, we observe that while the Naive MLES and its pessimistic version, Pessimistic Social Welfare, perform well when labelers are truthful, the performance degrades substantially under strategic preference labeling. In contrast, Pessimistic Median of MLEs exhibits almost no degradation, consistent with its approximate strategyproofness guarantee. Median of MLEs also shows slightly more robustness. though not to the same degree. We find that with increasing sample size, Pessimistic Median of MLEs primarily suffers the inherent cost being strategyproof, as indicated by diminishing performance gains from more samples. That said, the influence of strategic manipulation on the learned policy also grows with more data, thereby making discouraging strategic preference labeling increasingly more valuable.
33

---

Table 1: Suboptimality SubOpt(A) under truthful and strategic labeling across dataset sizes
20
Algorithm
SubOpt (Truthful)
SubOpt (Strategic)
Difference
Naive MLEs
0.512 + 0.067
0.649 0.082
+0.137
Pessimistic SW
0,641 0.081
0.751 = 0.086
+0.110
Median of MLEs
0,635 0.053
0,693 + 0.167
+0.058
Pessimistic MoMLEs
0,661 0.098
0.715 + 0.135
+0.054
50
Algorithm
SubOpt (Truthful)
SubOpt (Strategic)
Diff.
Naive MLEs
0.384 = 0.056
0,622 = 0.142
+0.238
Pessimistic SW
0,403 0.064
0.652
+0.249
Median of MLEEs
0.516 0.062
0.706 + 0.124
+-0.190
Pessimistic MoMLEs
0.508 + 0.058
0.532 0.154
+0.024
n
Algorithm
SubOpt (Truthful)
SubOpt (Strategic)
Diff.
Naive MLEs
0.230 = 0.071
0.516 0.131
+0.316
Pessimistic SW
0.249 0.068
0.584 +
+00.36
Median of MLEs
0.522 + 0.044
0.605 = 0.049
+000883
Pessimistic MoMLEs
0.506 + 0.045
0.574 : 0.132
+0.068
n 200
Algorithm
SubOpt (Truthful)
SubOpt (Strategic)
Diff.
Naive MLEs
0.133 + 0.029
0.491 + 0.251
+0.358
Pessimistic SW
0.136 0.027
0.459 : 0.266
+0.323
Median of MLES
0.487 1 0.061
0.514 ::: 0.259
+00027
Pessimistic MoMLEs
0.474 0.051
0.415 0.079
-0.059
34


Reviews:
[{"review_id": "yazEM1pUVj", "reviewer": "Reviewer_395W", "summary": "The paper is concerned with strategic manipulation in RLHF. It represents a model for the problem. It then shows that some existing RLHF are not strategy proof. In fact, there is a trade-off between strategy proofness and optimality. A strategy proof algorithm (Pessimistic median of MLEs) is then shown to be approximately strategy proof and to have a bounded sub-optimality.", "questions": "Please see the points under weaknesses.", "limitations": "Sufficient discussion was included.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "## Strengths\n\n-The paper is well-written. The sections follow a good logical sequence.\n\n-I'm not familiar with the area of strategic manipulations in RLHF but this paper seems to give some good results that are missing. \n \n\n## Weaknesses\n\n-Although, there has been literature on strategic manipulation in RLHF, but a broader point is that it's not clear (at least to me) how much of a practical issue it even is? \n\n-The paper is highly theoretical and no experiments are given. While the results are interesting, it's not clear how realistic they are. Here are more detailed points:\n\n* The dimension d is an embedding dimension for the state-action, correct? What value should we expect for it? Is it larger than the number of samples n we expect to have? This effects many of the given bounds \n\n* How realistic is assumption 2? Is it not reasonable to expect that the set partially covers the space instead of spanning R^d? \n\n* Lines (306-307): “Overall, as the number of samples increases and as the number of labelers grows, the Pessimistic Median of MLEs algorithm converges to the optimal policy”. Looking at proposition 4.3, it’s not clear to me that the upper bound converges to 0? I would expect that even with very large n there would be a lower bound ratio between k and n since any labeler can only label a finite number of points, so the second term in the upper bound would still be on the order of \\sqrt{d}, correct? \n\n* Lines (88-89) ”we propose a strategy-robust RLHF method that does not rely on payments or other financial incentives, which are often impractical in real-world applications”\n\nThe paper states that using financial incentives is impractical, but in standard RLHF aren’t the labelers paid for the labels they do? So, aren’t financial incentives already involved? \n\n* There is a restriction in the definition of  P_{\\tilde{\\theta_i}}, I can see a labeler following a distribution other than the truthful one that does not simply imply changing the vector \\theta and sampling according to Eq (1).", "was_revised": true, "final_justification": "I have not changed my recommendation score. The rebuttal has not changed my view of the paper significantly. While it has a nice theoretical contributions, the practical and experimental contributions can be improved significantly especially given that the paper is motivated by such practical applications.", "rebuttal": "Thank you for taking the time and effort to review our work and your helpful comments. We are glad to read that you found our results interesting and to be a good addition to the literature. We respond to your concerns and questions below. \n\n\n1. **“Is strategic manipulation of RLHF a practical issue?”**  \nWe believe that strategic manipulation is a serious concern in practice, which is becoming increasingly important. We want to highlight previous work [29, 19] that showed ChatGPT models exhibiting more politically biased behavior after RLHF fine-tuning, which suggests that the human evaluators’ personal preferences influenced the model. One major take-away from this is that such real-world biases in who provides feedback have had measurable effects on model behavior. Other recent work also shows that even small-scale strategic manipulation of human feedback can have disproportionately large effects on LLM fine-tuning in actual RLHF pipelines [Baumgärtner et al. 2024, Haider et al. 2025], which our Proposition 3.4 also supports theoretically. There is also other recent evidence that fine-tuning on a narrow task with a strategic / malicious annotator can cause general misalignment  [Betley et al. 2025]. \n\n\n2. **“The paper is highly theoretical and no experiments are given.”**    \nWhile the paper’s main contributions are theoretical, we now **added synthetic experiments** to the paper to corroborate our theoretical results, following your and the other reviewers' suggestions. You can find selected results of the newly added experiments further below.    \nWe now also respond to your additional questions concerning **\"How realistic are the results?\"**:\n   1. **“Typical values for the dimension d?”**      \nYes, $d$ is the embedding dimension of the state-action pairs and its value really depends on the application. If these embeddings are derived from a neural network or LLM the dimension can be quite large, e.g., 512 to 4096 for LLMs. Compared to this, most open-source preference datasets include anywhere between 5-50k comparisons. We agree with your intuition that our bounds should be interpreted in relation to $d$ and $n$ and if $d \\gg n$ offline RL(HF) bounds can become vacuous. However, this is expected and the $O(\\sqrt{d/n})$ bound in offline RLHF is tight as discussed in Remark 4.4 and Corollary 4.5. \n   2. **”How realistic is Assumption 2? Is it reasonable to expect that the set partially covers the space instead of spanning $\\mathbb{R}^d$?”**   \nAssumption 2 models the set of achievable feature expectations as a hyperrectangle rather than, for example, a sphere or general convex set. This structure simplifies the analysis and should act as a reasonable approximation when features are bounded and vary independently across dimensions. In practice, the set $ \\{ \\mathbb{E}_{s \\sim \\rho}[\\phi(s, \\pi(s))] : \\pi \\in \\Pi \\}$ often occupies a bounded convex subset of $\\mathbb{R}^d$, and the hyperrectangle assumption can be seen as an idealized version of such sets. As noted in Footnote 4, our results extend naturally to mild violations of this assumption, with only small additive error terms in the guarantees. \n   3. **“It's not clear [to me] that the upper bound of Proposition 4.3 converges to 0.”**  \nIn the mentioned paragraph we are referring to the asymptotic behavior of the algorithm and the corresponding bounds, which means we are looking at the case where the labelers can label an *arbitrarily* large amount of points even though of course this amount will always remain finite in practice. We wanted to express with this statement that if we could keep asking an increasing amount of labelers and each labeler for an arbitrarily large amount of data points, then the algorithm converges. We agree that the paragraph can be confusing and we rephrased the sentence in the paper to clarify this. \n   4. **“Aren’t financial incentives already involved? Why incentive design without payments?”**   \nWhile labelers are typically paid per annotation, implementing financial mechanisms that ensure strategyproofness in RLHF is often impractical. For instance, existing methods [24, 32] require conditioning payments or penalties on downstream effects, such as the performance of a fine-tuned policy, which are only observed well after labeling is complete. This makes enforcement difficult in real-world RLHF pipelines. Moreover, some RLHF settings, such as community-driven or crowdsourced alignment, do not involve financial compensation at all. In these cases, strategyproofness without payments is necessary by design. We also note that achieving strategyproofness without payments is significantly harder than when utility can be transferred directly through financial incentives. \n   5. **“Can labelers deviate to preference distributions other than the BT model?”**   \nWhile we define $P_{\\tilde \\theta_i}$ via the BT model of Eq. (1), our approximate strategyproofness results in fact do not rely on this specific parameterization. In the proof of Theorem 4.1, we show that for any fixed data from other labelers, the best possible outcome for labeler $i$ would be to directly report their true reward vector ${\\theta_i^\\star}$. Since labelers can only influence the mechanism through data, we argue that reporting according to $P_{\\theta_i^\\star}$ is nearly as good, within $O(\\sqrt{d/n})$, regardless of what other preference distributions are allowed. This argument extends to arbitrary preference distributions, not just the BT model. We have added a remark in the main text to clarify this generality. Thank you for drawing our attention to this point. \n\nPlease let us know if any concerns or questions remain. \n\n### **Example from Newly Added Experiments**\n**Experimental Setup:** \nWe simulate strategic labeling behavior by performing approximate gradient ascent (using SPSA) on each labeler's utility $J_i(\\hat \\pi)$ w.r.t. the labelers' internal reward parameters $\\tilde \\theta_i$, which govern their preference distributions $P_{\\tilde \\theta_i}$. Each labeler is initialized at their ground-truth reward vector $\\theta_i^*$, sampled from a multivariate Gaussian. Strategies are optimized for 200 steps. Since this process requires repeatedly relabeling data and rerunning each algorithm, we focus on small settings. All results are averaged over 5 random seeds, and we report standard errors. The results below are for embedding dimension $d = 16$, numer of labelers $k = 5$, and offline samples $n = 50$. We report the suboptimality under both truthful and strategic labeling, along with the difference.\n\nWe observe that while the Naive MLEs and its pessimistic version, Pessimistic Social Welfare, perform well when labelers are truthful, the performance degrades substantially under strategic labeler behavior. In contrast, Pessimistic Median of MLEs exhibits almost no degradation, consistent with its approximate strategyproofness. Median of MLEs also shows slighty more robustness, though not to the same degree. \n\n| Algorithm                    | $\\text{SubOpt}(\\hat{\\pi})$ (Truthful Labelers) | $\\phantom{00} \\text{SubOpt}(\\hat{\\pi})$ (Strategic Labelers) |  $\\phantom{00}$ Difference |\n|-----------------------------|---------------------------------------------------------------:|----------------------------------------------------------------:|----------------------------:|\n| Naive MLEs                  | $0.384 \\pm 0.056$                                              | $0.622 \\pm 0.142$                                               | $+0.238$                   |\n| Pessimistic Social Welfare  | $0.403 \\pm 0.064$                                              | $0.652 \\pm 0.149$                                               | $+0.249$                   |\n| Median of MLEs              | $0.516 \\pm 0.062$                                              | $0.706 \\pm 0.124$                                               | $+0.190$                   |\n| Pessimistic Median of MLEs | $0.508 \\pm 0.056$                                              | $0.532 \\pm 0.154$                                               | $+0.024$                   |\n|\n\n\n\n[19] Hartmann et al., 2023. The political ideology of conversational AI.\n\n[24] Park et al., 2024. RLHF from heterogeneous feedback via personalization and preference aggregation.\n\n[29] Santurkar et al., 2023. Whose opinions do language models reflect? \n\n[32] Sun et al., 2024. Mechanism design for LLM fine-tuning with multiple reward models.\n\nBaumgärtner et al., 2024, Best-of-Venom: Attacking RLHF by Injecting Poisoned Preference Data. \n\nHaider et al., 2025. A framework for mitigating malicious RLHF feedback in LLM training using consensus based reward. \n\nBetley et al., 2025. Emergent Misalignment: Narrow fine-tuning can produce broadly misaligned LLMs"}, {"review_id": "pfDXKe7nbR", "reviewer": "Reviewer_y9WG", "summary": "The paper addresses the vulnerability of RLHF to strategic manipulation by human labelers. The core problem is that when labelers know their feedback can influence the final learned policy, they may misreport preferences to skew the outcome toward their own interests. This is especially problematic when labelers have diverse and potentially conflicting preferences. The key contributions include a formalization of strategic RLHF and definition of strategyproofness. Some negative results are presented, like existing RLHF methods are not strategyproof, and a single strategic labeler can cause the learned policy to deviate arbitrarily far from the optimal social welfare. It also proves that any strategyproof RLHF algorithm must, in the worst case, perform k-times worse than the optimal policy.", "questions": "Overall I believe it is an interesting and solid paper. However, I do have the following questions:\n\n1. In terms of motivation, my main concern is whether strategic manipulation in terms of preferences by human labelers is practical. Because in reality, there is often a large number of labelers for training an LLM and as a result, the influence of each labeler's decision on the result is subtle and perhaps imperceptible. It is better to include some concrete motivating example in the paper to show that such strategic manipulations are happening in reality. Otherwise I'm not fully convinced that any human labeler is capable or initiative enough to engage in such manipulations. \n\n2. The paper assumes that all labelers’ preferences are linearly realizable in known feature spaces. This assumption is mathematically convenient but might be overly restrictive in practice. Human preferences are rarely linear or easily projected onto known features. I'm wondering if similar insight or result can hold under different assumptions, e.g., discrete or convex preference structures?\n\n3. The proposed Pessimistic Median of MLEs algorithm uses a conservative pessimistic estimate over the coordinate-wise median reward parameter. While it can promote robustness, it may also lead to overly cautious policies. I'm curious if there is any discussion about the potential tradeoff in such an algorithm design.", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The strengths of the paper: \n\nInteresting and timely research topic, solid theoretical results. The proposed solution combines median aggregation and pessimistic estimates over confidence sets of reward parameters is interesting.\n\nThe weaknesses of the paper:\n\nMotivation not strong enough, involves restrictive assumptions, lack experimental support.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our work. We are happy to hear that you found the research topic interesting and timely with solid theoretical results, and our proposed method interesting. \n\nBelow, we address your concerns and questions about the **motivation** (what about large numbers of labelers), **assuming linearly realizable rewards**, and **experimental support** (we now added synthetic experiments):   \n\n1. **Motivation (\"What if the number of labelers is very large?\"):**    \nWhen the number of individual labelers in RLHF is large, it is often more appropriate to think in terms of **groups of labelers** whose preferences closely align, for example along political, ideological, or stylistic lines. Each such group can be treated as a single effective labeler in our framework. Notably, such group effects have been observed in practice, where ChatGPT models became more politically biased after RLHF fine-tuning, which suggests that the human labelers’ personal preferences influenced the model [19, 29]. If a group is aware of this potential impact, it may have an incentive to strategize to steer the model toward its values. Moreover, single labelers (small groups) can have **substantial influence** even in large labeler populations. Proposition 3.4 shows this theoretically, and recent work by Baumgärtner et al. (2024) demonstrates empirically that injecting as little as 1-5% manipulated data is sufficient to shift a model's behavior toward targeted sentiment generation. Additional evidence from Betley et al. (2025) shows that fine-tuning on a narrow task with a strategic or malicious annotator can cause general misalignment. We now highlight these points more clearly in the introduction to strengthen the motivation.\n2. **Assuming Linearly Realizable Rewards:**    \nWe agree that assuming linearly realizable rewards can be a restrictive assumption that may be violated in practice. For more complex reward models, our ideas could likely be extended, as MLE concentration results exist for more general models (Zhan et al. 2023). The pessimistic median based algorithm might not be strategyproof but we believe some variant of the algorithm might work for general reward models and this would be interesting to explore in the future.  \n3. **Pessimistic Estimates and Trade-Offs:**  \nWe agree with your intuition that pessimism may lead to conservative policy choices, however, it is necessary to some extent in offline RL(HF) to obtain sample efficient algorithms: Theorem 1.2 in [35] shows that **without pessimism** the “naive” MLE approach suffers from **constant suboptimality** in offline RLHF. We don’t have a definitive answer to potential trade-offs, but our **newly added experiments** compare also with non-pessimistic versions of the median and social welfare algorithms (see further below). \n\n\nWe would be happy to further discuss if any concerns or questions remain. \n\n### **Excerpt from Additional Experiments**\n**Experimental Setup:** \nWe simulate strategic labeling behavior by performing approximate gradient ascent (using SPSA) on each labeler's utility $J_i(\\hat \\pi)$ w.r.t. the labelers' internal reward parameters $\\tilde \\theta_i$, which govern their preference distributions $P_{\\tilde \\theta_i}$. Each labeler is initialized at their ground-truth reward vector $\\theta_i^*$, sampled from a multivariate Gaussian. Strategies are optimized for 200 steps. Since this process requires repeatedly relabeling data and rerunning each algorithm, we focus on small settings. All results are averaged over 5 random seeds, and we report standard errors. The results below are for embedding dimension $d = 16$,  numer of labelers $k = 5$, and offline samples $n = 50$. We report the suboptimality under both truthful and strategic labeling, along with the difference.\n\nWe observe that while the Naive MLEs and its pessimistic version, Pessimistic Social Welfare, perform well when labelers are truthful, the performance degrades substantially under strategic labeler behavior. In contrast, Pessimistic Median of MLEs exhibits almost no degradation, consistent with its approximate strategyproofness. Median of MLEs also shows slighty more robustness, though not to the same degree. \n\n| Algorithm                    | $\\text{SubOpt}(\\hat{\\pi})$ (Truthful Labelers) | $\\phantom{00} \\text{SubOpt}(\\hat{\\pi})$ (Strategic Labelers) |  $\\phantom{00}$ Difference |\n|-----------------------------|---------------------------------------------------------------:|----------------------------------------------------------------:|----------------------------:|\n| Naive MLEs                  | $0.384 \\pm 0.056$                                              | $0.622 \\pm 0.142$                                               | $+0.238$                   |\n| Pessimistic Social Welfare  | $0.403 \\pm 0.064$                                              | $0.652 \\pm 0.149$                                               | $+0.249$                   |\n| Median of MLEs              | $0.516 \\pm 0.062$                                              | $0.706 \\pm 0.124$                                               | $+0.190$                   |\n| Pessimistic Median of MLEs | $0.508 \\pm 0.056$                                              | $0.532 \\pm 0.154$                                               | $+0.024$                   |\n|\n\n\n[35] Zhu et al., 2023. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons.\n\nZhan et al., 2023. Provable Offline Preference-Based Reinforcement Learning\n\nBaumgärtner et al. 2024, Best-of-Venom: Attacking RLHF by Injecting Poisoned Preference Data. \n\nBetley et al., 2025. Emergent Misalignment: Narrow fine-tuning can produce broadly misaligned LLMs"}, {"review_id": "4CpLCK4uzW", "reviewer": "Reviewer_rwWs", "summary": "This paper studies Reinforcement Learning from Human Feedback (RLHF) in settings where labelers may strategically misreport their preferences.\n\nOn the negative side, it shows that:\n(i) several popular pluralistic-alignment algorithms are manipulable (i.e., not strategy-proof), and\n(ii) any algorithm that is fully strategy-proof must, in the worst case, achieve only a 1/k fraction of the optimal social welfare, where k is the number of labelers.\n\nOn the positive side, the paper proposes Pessimistic Median of MLEs (MoMLE), a robust offline algorithm that, under linear rewards and certain coverage assumptions, is approximately strategy-proof and nearly optimal when the sample size n is large relative to the feature dimension d and the number of labelers k.\n\nThe analysis is first given for contextual bandits, then extended to finite-horizon MDPs.", "questions": "I am on the fence between \"borderline accept\"  and \"accept\". It would be helpful to clarify the following question to better see how compelling the results are.\n\n1. In the performance guarantee theorems, how do the constants kappa_i and nu_i depend on parameters such as n and d?\n\n2. In Theorem 4.1, the result conditions on the other labelers’ reports, and labeler i’s utility is evaluated ex-ante (i.e., taking expectation over their choices). Plus, the proposed algorithm is deterministic, and J_i is a deterministic function. Given these setups, over what source of randomness is the “with probability at least 1 - delta” statement defined?\n\n3. Related to W1, if a strategic labeler is allowed to deviate from the BT model altogether (e.g., always deterministically selecting the higher-reward response), how would this affect the performance of the proposed algorithm?\n\n4. Conversely, how difficult is it in practice to achieve epsilon-strategyproofness? For example, is the plain median aggregation method (without pessimistic adjustment) already o(1)-strategyproof and nearly optimal?\n\n5. Are Pessimistic Social Welfare and MaxMin-RLHF epsilon strategyproof? Proposition 3.3 only shows that they are not (strictly) strategyproof.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength: \n\nS1. (Timely and promising topic) This paper considers a timely topic. The consideration of strategic manipulation in human feedback to LLM alignment is natural, and I can see a good possibility that it spurs follow-up research on incentive-aware AI alignment. \n\n\nS2. (Natural design) The proposed algorithm is also natural. Median as a statistic is known for being robust to outliers. It is hence natural that even if an agent can unilaterally change his/her own perceived theta_i, the effect on the aggregated theta will only be minimal, leading to the small incentive to manipulate. \n\n\nWeakness:\n\nW1. (Solution concept)  The solution concept feels somewhat counterintuitive. On the one hand, the requirement of epsilon-strategyproofness is quite strong, as it demands that truth-telling be an ex-ante dominant strategy rather than simply a Nash equilibrium. On the other hand, the space of deviations is rather restricted: if a labeler deviates, they must still produce responses according to a BT model, albeit with a different parameter theta_i. This excludes arguably benign forms of preference reporting, such as simply choosing the preferred response deterministically (i.e., always selecting the higher-reward option).\n\n\nW2. (Empirical validation) This paper is purely theoretical and could benefit from the empirical validation. That said, I do not see this as a fundamental flaw.", "was_revised": true, "final_justification": "I find the topic to be timely and the solution is clean. Overall, I learned something from the paper and can see a good possibility that it spurs follow-up research on incentive-aware AI alignment. I understand the work is main theoretical but that is in line with the style many papers of similar topics.\n\nMy main justification for the score raise is that, based on the author rebuttal, the deviation strategy space can be broader than originally stated in the paper. In addition, the paper does incorporate incentive structures in the policy design and analysis, so it is not just about \"delicate ignorance of (or insensitivity to) data\".", "rebuttal": "Thank you very much for taking the time to review our paper and your helpful suggestions. We are pleased to hear that you found our research topic timely and promising (S1) and our algorithm design natural (S2). We respond to your questions below. \n\n**W1. (Space of deviations is restricted) & Question 3 (What if labelers deviate from the BT model if they wanted to?):**   \nIn fact, our approximate strategyproofness result for the Pessimistic Median of MLEs does not rely on the assumption that deviating labelers must follow a BT model. The analysis **extends directly to arbitrary deviation strategies**, that is, labelers can follow any preference distribution if they wanted to. To briefly outline why, in the proof of Theorem 4.1, we show that for any fixed data $D_{-i}$ from the other labelers, the optimal outcome for labeler $i$ in terms of expected utility would be to directly report their true reward parameter $\\theta_i^\\star$. Since labelers only influence the mechanism through the data they provide, we then show that providing labels according to a BT model with parameter $\\theta_i^\\star$ yields expected utility within $O(\\sqrt{d/n})$ of this best case. This argument does *not* rely on any assumptions about the structure of potential deviations. As for the specific case where a labeler deterministically selects the higher-reward option, this behavior corresponds to a BT model with high-magnitude parameters (rewards) and is therefore already included within our analysis. Thank you very much for highlighting this in your review, as this will be helpful to clarify in the paper. We have added a remark in the main text to make this generalization explicit. \n\n\n\n**W2. (Empirical validation; the paper could benefit from an empirical evaluation):**    \nAs you already pointed out, our main contributions are **theoretical** and **conceptual**. Still, we appreciate your suggestion, and **added synthetic experiments** to the paper (you can find an excerpt of the results with brief explanations further below). \n\n\n### Responses to your other Questions: \n1. **Coverage constants $\\kappa_i$ and $\\nu_i$:**   \nThe constants $\\kappa_i$ and $\\nu_i$ importantly do not depend on the other parameters. This means that there are no other parameter dependencies hidden in these constants. \n2. **Source of randomness in Theorem 4.1:**    \nThank you for catching this. The source of randomness is meant to come from sampling from $\\smash{P_{\\tilde \\theta_i}}$ and $\\smash{P_{\\theta_i^\\star}}$ and we shouldn’t have written the expectation over these distributions but instead that the labels in $\\smash{\\tilde D_i}$ are sampled from $P_{\\tilde \\theta_i}$ and the labels in $D_i^\\star$ are sampled from $P_{\\theta_i^\\star}$. We fixed this. \n3. **\"What if the labelers are allowed to deviate from the BT model?\"**    \n(Please see the response to W1 above.)\n4. **“How difficult is it in practice to achieve $\\varepsilon$-strategyproofness? What about non-pessimistic median MLE?”**    \nThis is an interesting question, which we don’t have a fully definitive answer to. What we do know is that in terms of social welfare (i.e., policy suboptimality) the median approach without pessimism will be theoretically **much worse** since pessimism is generally needed for provable sample efficiency: Theorem 1.2 in [35] tells us that the non-pessimistic “naive” MLE approach to RLHF suffers from **constant suboptimality**. Regarding the strategyproofness, our intuition is that the basic median approach should be approximately strategyproof as well (partially confirmed by the newly added experiments). However, a theoretical analysis is quite challenging as it becomes fully probabilistic due to the lack of pessimistic confidence bounds.   \n5. **“Are Pessimistic Social Welfare and MaxMin-RLHF epsilon-strategyproof?”**    \nNo. We can adapt the examples in the proof of Proposition 3.3 so that for any value of $\\varepsilon$ the incentive to manipulate exceeds $\\varepsilon$. Note that the current counterexample in the proof already implies  $\\varepsilon > 1/4$. We included a short sentence mentioning this below the proposition.\n\nPlease let us know if any of your concerns or questions remain. We are happy to further discuss. \n\n\n\n### **Excerpt from Newly Added Experiments**\n**Experimental Setup:** \nWe simulate strategic labeling behavior by performing approximate gradient ascent (using SPSA) on each labeler's utility $J_i(\\hat \\pi)$ w.r.t. the labelers' internal reward parameters $\\tilde \\theta_i$, which govern their preference distributions $P_{\\tilde \\theta_i}$. Each labeler is initialized at their ground-truth reward vector $\\theta_i^*$, sampled from a multivariate Gaussian. Strategies are optimized for 200 steps. Since this process requires repeatedly relabeling data and rerunning each algorithm, we focus on small settings. All results are averaged over 5 random seeds, and we report standard errors. The results below are for embedding dimension $d = 16$, numer of labelers $k = 5$, and offline samples $n = 50$. We report the suboptimality under both truthful and strategic labeling, along with the difference.\n\nWe observe that while the Naive MLEs and its pessimistic version, Pessimistic Social Welfare, perform well when labelers are truthful, the performance degrades substantially under strategic labeler behavior. In contrast, Pessimistic Median of MLEs exhibits almost no degradation, consistent with its approximate strategyproofness. Median of MLEs also shows slighty more robustness, though not to the same degree. \n\n| Algorithm                    | $\\text{SubOpt}(\\hat{\\pi})$ (Truthful Labelers) | $\\phantom{00} \\text{SubOpt}(\\hat{\\pi})$ (Strategic Labelers) |  $\\phantom{00}$ Difference |\n|-----------------------------|---------------------------------------------------------------:|----------------------------------------------------------------:|----------------------------:|\n| Naive MLEs                  | $0.384 \\pm 0.056$                                              | $0.622 \\pm 0.142$                                               | $+0.238$                   |\n| Pessimistic Social Welfare  | $0.403 \\pm 0.064$                                              | $0.652 \\pm 0.149$                                               | $+0.249$                   |\n| Median of MLEs              | $0.516 \\pm 0.062$                                              | $0.706 \\pm 0.124$                                               | $+0.190$                   |\n| Pessimistic Median of MLEs | $0.508 \\pm 0.056$                                              | $0.532 \\pm 0.154$                                               | $+0.024$                   |\n|\n\n\n\n[35] Zhu et al. Principled reinforcement learning with human feedback from pairwise or k-wise comparisons."}, {"review_id": "B6Iz3xrmid", "reviewer": "Reviewer_zDgj", "summary": "This paper tackles the problem of what happens in RLHF when there are multiple labelers who might strategically lie to push the resulting AI's policy closer to their own preferred outcomes. The authors frame this through the lens of mechanism design, looking at how to create systems that are robust to this kind of manipulation.\n\nThey begin by formally demonstrating that current RLHF methods aren’t immune to this issue. In fact, they prove that even a single strategic person can cause a surprising amount of distortion to the policy’s alignment with the overall group’s welfare. The most striking part is their impossibility result, where they tie the issue back to classic ideas from social choice theory, arguing that any perfectly strategyproof RLHF system is fundamentally limited in optimality. They therefore points to a core tradeoff between robustness to manipulation and getting the best possible policy. Given this challenge, they propose an alternative algorithm, which idea is to use pessimistic estimates combined with a median rule, which they show is approximately strategyproof and, under the right conditions, still finds the optimal policy as you get more data and more labelers", "questions": "* I really enjoyed the theoretical deep dive. To help bridge this theory to practice, I'd be curious to hear your thoughts on the value of a small, synthetic empirical study. How do you think such experiments might help us better understand the algorithm's performance in (a) more \"average-case\" strategic settings, and (b) the finite-sample regime? I feel like this could really strengthen the paper's message.\n\n* I'd like to push a bit on Assumption 2 (the hyperrectangle spanning assumption). Could you give me a bit more intuition on when you think this might hold, and what you suspect might happen to your guarantees if it's violated?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 4, "strengths_and_weaknesses": "# Strengths\n\n* Tackling strategyproofness in RLHF without relying on monetary incentives is, in my opinion, a critical research direction. The discovery of the fundamental trade-off between incentive alignment and policy alignment feels like a really important and lasting conceptual contribution.\n\n* From a technical standpoint, the work appears to be very solid (though I didn’t verify the proofs)\n\n* I also have to commend the authors on the writing: the paper is exceptionally clear and was a pleasure to read. It does a great job of motivating the problem and laying out the contributions in a logical, easy-to-follow manner.\n\n* The proposed \"Pessimistic Median of MLEs\" algorithm is a novel contribution. Combining pessimistic estimates with a median rule to handle strategic behavior is a clever idea, and the paper provides a solid theoretical analysis for why this approach works.\n\n# Weaknesses\n\nWhile the theory is elegant, I did find myself wondering about a few practical aspects, which could probably be clarified with some quick synthetic experiments.\n\n* The theoretical guarantees are asymptotic, but as always, the devil’s in the constants. Some of these bounds could hide large constants that render the algorithm impractical for realistic sample sizes. Is it effective with thousands of samples? Or do you need millions? Without some empirical calibration, it’s hard to tell where the method becomes usable.\n\n* Similarly, the proofs focus on specific worst-case constructions. It would be valuable to see how these methods hold up in more \"normal\" average-case scenarios, where e.g. the $\\theta$ are not adversarially chosen, but sampled from some realistic distribution. This would give us a better sense of how brittle current methods are in the wild", "was_revised": true, "final_justification": "The synthetic experiments addressed my concerns", "rebuttal": "Thank you very much for the time and effort you spent reviewing our work and your helpful comments. We are especially appreciative of your comments on the importance of strategyproof RLHF without monetary incentives, the conceptual clarity of the tradeoff between incentive and policy alignment, and the novelty of the proposed algorithm. \n\nBelow we respond to your comments and questions, where we first jointly respond to your questions and suggestions about adding an experimental evaluation. \n\n\n### **Adding an Experimental Evaluation:** \nWhile the paper’s **main contributions are theoretical**, we agree that experiments can help interpret and better understand the guarantees and the dynamics of strategic manipulation in RLHF. We therefore **added synthetic experiments** to the paper, an excerpt of which can be found further below. Following your suggestions and questions, we specifically analyzed the following two aspects:\n1. **“Dependence on the number of samples?”**    \nWe provide results for sample sizes $n=20, 50, 100, 200$ with $d=16$ below. In the low sample regime $n=20$, the pessimistic approaches (Pessimistic Median of MLEs and Pessimistic Social Welfare) achieve only about 60% of the optimal policy’s social welfare (1.6 is the optimal social welfare in the experiments), but quickly improve performance with increasing sample size. We find that eventually the main performance limitation of Pessimistic Median of MLEs becomes not the sample size, but instead the inherent cost of being strategyproof (by using a median rule), as indicated by diminishing performance gains from more samples. That said, the influence of strategic manipulation also grows with more data, making strategyproofness increasingly valuable. By $n = 200$, Pessimistic Median of MLEs outperforms all baselines under strategic behavior. \n2. **“Performance in average-case scenarios (not worst-case)?”**   \nYou are correct in that the proofs and guarantees are worst-case over possible problem instances. In the newly added experiments, we sample the true reward parameters $\\theta_i^\\star$ independently from a multivariate Gaussian distribution. From the experiments we observe that even in such average-case scenarios, labelers can have significant incentives to manipulate (see Difference column). \n\n\n\n**“More intuition about Assumption 2; What if it’s violated?”**   \nAssumption 2 models the set of achievable feature expectations as a hyperrectangle rather than, for example, a sphere or general convex set. This structure simplifies the analysis and our intuition is that this should act as a reasonable approximation when features are bounded and vary independently across dimensions. In practice, the set $\\{ \\mathbb{E}_{s \\sim \\rho}[\\phi(s, \\pi(s))] : \\pi \\in \\Pi \\}$ often occupies a bounded convex subset of $\\mathbb{R}^d$, and the hyperrectangle assumption can be seen as an idealized version of such sets. As noted in Footnote 4, our results extend naturally to mild violations of this assumption, with only small additive error terms in the guarantees. \n\n\nPlease let us know if any of your concerns or questions remain. \n\n\n### **Excerpt from Newly Added Experiments**\n**Experimental Setup:** \nWe simulate strategic labeling behavior by performing approximate gradient ascent (using SPSA) on each labeler's utility $J_i(\\hat \\pi)$ w.r.t. the labelers' internal reward parameters $\\tilde \\theta_i$, which govern their preference distributions $P_{\\tilde \\theta_i}$. Each labeler is initialized at their ground-truth reward vector $\\theta_i^*$, sampled from a multivariate Gaussian. Labeler strategies are optimized for 200 steps. Since this process requires repeatedly relabeling data and rerunning each algorithm, we focus on small settings. All results are averaged over 5 random seeds, and we report standard errors. The results below are for embedding dimension $d = 16$, numer of labelers $k = 5$, and offline samples $n = 20, 50, 100, 200$, and additional runs will be included in the appendix of the paper. We report the suboptimality under both truthful and strategic labeling, along with the difference.\n\nOverall, we observe that while the Naive MLEs and its pessimistic version, Pessimistic Social Welfare, perform well when labelers are truthful, the performance degrades substantially under strategic labeler behavior. In contrast, Pessimistic Median of MLEs exhibits almost no degradation, consistent with its approximate strategyproofness. Median of MLEs also shows slighty more robustness, though not to the same degree. \n\n\n#### n = 20:\n\n| Algorithm                    | $\\text{SubOpt}(\\hat{\\pi})$ (Truthful Labelers) | $\\phantom{00} \\text{SubOpt}(\\hat{\\pi})$ (Strategic Labelers) |  $\\phantom{00}$ Difference |\n|-----------------------------|----------------------------:|-----------------------------:|----------------------------:|\n| Naive MLEs                  | $0.512 \\pm 0.067$                                              | $0.649 \\pm 0.082$                                               | $+0.137$                   |\n| Pessimistic Social Welfare  | $0.641 \\pm 0.081$                                              | $0.751 \\pm 0.086$                                               | $+0.110$                   |\n| Median of MLEs              | $0.635 \\pm  0.053$                                              | $0.693 \\pm 0.167$                                               | $+0.058$                   |\n| Pessimistic Median of MLEs | $0.661 \\pm 0.098$                                              | $0.715 \\pm 0.155$                                               | $+0.054$                   |\n|\n\n#### $n=50$\n| Algorithm                    | $\\text{SubOpt}(\\hat{\\pi})$ (Truthful Labelers) | $\\phantom{00} \\text{SubOpt}(\\hat{\\pi})$ (Strategic Labelers) |  $\\phantom{00}$ Difference |\n|-----------------------------|---------------------------------------------------------------:|----------------------------------------------------------------:|----------------------------:|\n| Naive MLEs                  | $0.384 \\pm 0.056$                                              | $0.622 \\pm 0.142$                                               | $+0.238$                   |\n| Pessimistic Social Welfare  | $0.403 \\pm 0.064$                                              | $0.652 \\pm 0.149$                                               | $+0.249$                   |\n| Median of MLEs              | $0.516 \\pm 0.062$                                              | $0.706 \\pm 0.124$                                               | $+0.190$                   |\n| Pessimistic Median of MLEs | $0.508 \\pm 0.056$                                              | $0.532 \\pm 0.154$                                               | $+0.024$                   |\n|\n\n\n#### n=100\n\n\n| Algorithm                    | $\\text{SubOpt}(\\hat{\\pi})$ (Truthful Labelers) | $\\phantom{00} \\text{SubOpt}(\\hat{\\pi})$ (Strategic Labelers) |  $\\phantom{00}$ Difference |\n|-----------------------------|---------------------------------------------------------------:|----------------------------------------------------------------:|----------------------------:|\n| Naive MLEs                  | $0.230 \\pm 0.071$                                              | $0.516 \\pm 0.131$                                               | $+0.316$                   |\n| Pessimistic Social Welfare  | $0.249 \\pm 0.068$                                              | $0.584 \\pm 0.147$                                               | $+0.336$                   |\n| Median of MLEs              | $0.522 \\pm 0.044$                                              | $0.605 \\pm 0.049$                                               | $+0.083$                   |\n| Pessimistic Median of MLEs | $0.506 \\pm 0.045$                                              | $0.574 \\pm 0.152$                                               | $+0.068$                   |\n|\n\n\n#### n = 200: \n\n| Algorithm                    | $\\text{SubOpt}(\\hat{\\pi})$ (Truthful Labelers) | $\\phantom{00} \\text{SubOpt}(\\hat{\\pi})$ (Strategic Labelers) |  $\\phantom{00}$ Difference |\n|-----------------------------|---------------------------------------------------------------:|----------------------------------------------------------------:|----------------------------:|\n| Naive MLEs                  | $0.133 \\pm 0.029$                                              | $0.491 \\pm 0.251$                                               | $+0.358$                   |\n| Pessimistic Social Welfare  | $0.136 \\pm 0.027$                                              | $0.459 \\pm 0.266$                                               | $+0.323$                   |\n| Median of MLEs              | $0.487 \\pm 0.061$                                              | $0.514 \\pm 0.259$                                               | $+0.027$                   |\n| Pessimistic Median of MLEs | $0.474 \\pm 0.051$                                              | $0.415 \\pm 0.079$                                               | $-0.059$                   |\n|"}]

Author rebuttal:

Meta-review: The authors study strategyproofness of RLHF. In their model, labelers may strategically misreport feedback to steer the policy toward their own preferences. They show that existing RLHF algorithms are not strategyproof and that, in the worst case, any fully strategyproof RLHF algorithm must perform k times worse than the optimal policy, where k is the number of labelers. However, by slightly relaxing strategyproofness, they can do better: in line with previous work in social choice on the strategyproofness of median rules, they propose the Pessimistic Median of MLEs algorithm, which is approximately strategyproof and converges to the optimal policy in the limit. The central observation is while any single labeler can still move the policy an arbitrary amount, they can never move it closer to their preferences by reporting untruthfully.

Strengths:
- All reviewers appreciated the strong theoretical results in the paper.
- The paper is well-written overall.
- To address reviewer concerns (395W, y9WG, rwWs, zDgj) about empirical evaluation, the authors ran experiments and presented results in the rebuttal. All of the reviewers appreciated them, and the experiments support the theory in the paper.

Weaknesses:
- There was some disagreement about how practically relevant this problem is. How often are labelers actively trying to steer RLHF algorithms toward their own opinion? In their rebuttal, the authors provided a fairly convincing argument about this happening in political topics.
- The paper focuses on worst-case constructions as opposed to average-case scenarios; this was partially addressed by synthetic experiments.
Decision: Accept (poster)