Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons

Banghua ZhuMichael I. JordanJiantao Jiao

article2023ICML268 citations

Establishes a theoretical foundation for reinforcement learning with human feedback, proving why standard maximum likelihood reward estimation fails during policy optimization, how pessimistic estimation fixes this failure, and deriving the first sample complexity bound for maximum-entropy inverse reinforcement learning.

Listen

Aligning modern artificial intelligence systems with human values is essential for safety, reliability, and performance, particularly in large language models like ChatGPT. Reinforcement learning from human feedback has emerged as the dominant method for achieving this alignment by learning a reward model from ranked human comparisons and using it to guide model behavior. Despite widespread empirical adoption, the theoretical foundations of reward learning and downstream decision making from comparison data have remained poorly understood.

The article establishes a rigorous mathematical framework to evaluate the sample efficiency, parameter convergence, and policy performance of reinforcement learning from human feedback. Specifically, it analyzes how standard statistical estimation techniques perform when learning from pairwise and multi-item comparison data, and evaluates whether these learned rewards reliably guide an agent toward optimal actions.

To address these questions, the authors analyze linear reward models under standard probabilistic ranking frameworks, specifically the Bradley-Terry-Luce model for pairs and the Plackett-Luce model for rankings of several items. They evaluate both contextual bandit settings (analogous to prompt-and-response generation) and sequential decision-making environments, extending the framework to inverse reinforcement learning. The theoretical findings were corroborated through numerical simulations evaluating sample sizes ranging from 10 to 500 samples across multiple iterations.

The analysis yields four critical findings. First, while standard maximum likelihood estimation accurately converges to the underlying reward parameters, training a direct greedy policy on this raw estimate consistently fails, leaving a persistent performance gap of at least 10% regardless of sample size due to over-optimization on poorly represented actions. Second, incorporating a pessimism principle—which discounts actions lacking sufficient coverage in the training data—achieves a provably near-optimal policy with an error rate that vanishes at the optimal theoretical rate as data increases. Third, when evaluating multi-item rankings, both the full ranking estimator and the common industry practice of splitting rankings into all possible pairs converge, but the full ranking estimator achieves lower asymptotic variance and higher data efficiency. Finally, the framework unifies reward learning with maximum-entropy inverse reinforcement learning, establishing its first theoretical sample complexity bounds.

These findings provide direct operational and algorithmic implications for developing aligned machine learning systems. Standard reward optimization carries a substantial risk of catastrophic policy failure and performance degradation when models venture into under-explored action spaces. The results justify incorporating conservatism or regularization during policy fine-tuning to prevent the over-optimization observed in practical deployments, while demonstrating that adopting true listwise ranking estimators can reduce the volume of costly human annotations needed for alignment.

Organizations developing aligned artificial intelligence systems should explicitly integrate pessimism into policy optimization workflows, either through conservative offline learning algorithms or constraint penalties that keep the model close to well-covered reference behaviors. Furthermore, data pipelines collecting multi-item rankings should utilize full listwise likelihood estimation rather than pairwise decompositions to maximize statistical efficiency. Future work should extend this theoretical framework beyond linear representations to dynamic neural network feature spaces and analyze the complete pipeline combining pre-training, reward modeling, and proximal policy optimization.

University of California Berkeley maximum likelihood maximum likelihood estimate maximum likelihood estimator reinforcement learning with human feedback pairwise comparisons preference-based reinforcement learning

arXiv: 2301.11270

Paper: Deep reinforcement learning from human preferences, Paul F. Christiano et al. (2017). Introduces the foundational paradigm of training reward models from pairwise human trajectory comparisons to guide reinforcement learning, which the source formally analyzes.
Paper: Fine-Tuning Language Models from Human Preferences, Daniel M. Ziegler et al. (2019). Establishes the standard RLHF framework using human preference models to fine-tune language models with policy optimization, providing the empirical setting theoretically investigated in the source.
Paper: Maximum Entropy Inverse Reinforcement Learning, Brian D. Ziebart et al. (2008). Defines maximum entropy inverse reinforcement learning, establishing the framework that the source unifies with reinforcement learning from human feedback.
Paper: Training a Helpful and Harmless Assistant with Reinforcement Learning from Human Feedback, Yuntao Bai et al. (2022). Demonstrates the practical deployment and empirical success of preference modeling and RLHF in language assistants that the source seeks to theoretically validate.
Paper: Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time Guarantees, Siliang Zeng et al. (2022). Provides finite-time convergence guarantees for maximum-likelihood inverse reinforcement learning, serving as an important prerequisite for the sample complexity bounds developed in the source.
Paper: Apprenticeship learning via inverse reinforcement learning, Pieter Abbeel et al. (2004). Lays foundational theoretical groundwork for inverse reinforcement learning and policy recovery under linear reward formulations.
Paper: Algorithms for Inverse Reinforcement Learning, Andrew Y. Ng et al. (2000). Introduces the foundational algorithmic problem of recovering underlying reward functions from observed behavior in Markov decision processes.

Paper: From RLHF to Direct Alignment: A Theoretical Unification of Preference Learning for Large Language Models, Tarun Raheja et al. (2026). Extends theoretical preference-learning analysis from classic reward-model RLHF to direct alignment paradigms under unified coverage and optimization principles.
Paper: HelpSteer2-Preference: Complementing Ratings with Preferences, Zhilin Wang et al. (2025). Empirically compares and unifies Bradley-Terry pairwise preference modeling with direct rating regressions for language model reward learning.
Paper: KTO: Model Alignment as Prospect Theoretic Optimization, Kawin Ethayarajh et al. (2024). Develops an alternative alignment framework optimizing language models directly from binary feedback using prospect-theoretic utility formulation.
Paper: Rewards-in-Context: Multi-objective Alignment of Foundation Models with Dynamic Preference Adjustment, Rui Yang et al. (2024). Generalizes preference alignment to handle conflicting multi-objective rewards dynamically during foundation model deployment.
Paper: RLAIF vs. RLHF: Scaling Reinforcement Learning from Human Feedback with AI Feedback, Harrison Lee et al. (2024). Investigates replacing human preference labels in RLHF pipelines with automated AI feedback across standard text generation tasks.
Paper: HybridFlow: A Flexible and Efficient RLHF Framework, Guangming Sheng et al. (2024). Addresses the systems and computational scalability bottlenecks of running complex RLHF multi-model workflows across distributed hardware.

Cover for Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons

Abstract

We provide a theoretical framework for Reinforcement Learning with Human Feedback (RLHF). Our analysis shows that when the true reward function is linear, the widely used maximum likelihood estimator (MLE) converges under both the Bradley-Terry-Luce (BTL) model and the Plackett-Luce (PL) model. However, we show that when training a policy based on the learned reward model, MLE fails while a pessimistic MLE provides policies with improved performance under certain coverage assumptions. Additionally, we demonstrate that under the PL model, the true MLE and an alternative MLE that splits the $K$ -wise comparison into pairwise comparisons both converge. Moreover, the true MLE is asymptotically more efficient. Our results validate the empirical success of existing RLHF algorithms in InstructGPT and provide new insights for algorithm design. Furthermore, our results unify the problem of RLHF and max-entropy Inverse Reinforcement Learning (IRL), and provide the first sample complexity bound for max-entropy IRL.

Topics

maximum likelihood maximum likelihood estimate maximum likelihood estimator pair-wise comparison reinforcement learning with human feedback reward function

Keywords

reinforcement learning with human feedback pairwise comparisons preference-based reinforcement learning offline preference-based reward learning pessimistic MLE Markov decision processes contextual bandits reward model inverse reinforcement learning

1 Introduction
1.1 Main Results
1.2 Related Work
2 Preliminaries
2.1 Markov decision processes
2.2 Sampling Procedure and Comparison Model
2.3 Organization
3 Learning from Pairwise Comparison
3.1 Algorithms: MLE and Pessimistic MLE
3.2 Failure of MLE and Lower Bounds
4 Learning from KK-wise comparisons
4.1 Algorithms
5 Extension to MDPs
5.1 Trajectory-based Comparison
5.2 Action-based Comparison
6 Connection with Inverse Reinforcement Learning
6.1 Trajectory-based IRL
6.2 Action-based IRL
7 Experiments
8 Conclusion
References
A Analysis for nonlinear rθr_{\theta}
B Remaining Proofs
B.1 Proof of Lemma
B.2 Proof of Theorem
B.3 Proof of Theorem
B.4 Proof of Theorem
B.5 Proof of Theorem
B.6 Proof of Theorem
B.7 Proof of Lemma
B.8 Proof of Theorem
B.9 Proof of Theorem
B.10 Proof of Theorem

Knowls

Knowl 1 — Pessimistic Maximum Likelihood Policy Optimization Algorithm for Preference-Based Learning
algorithm
The Pessimistic Maximum Likelihood Estimator (Pessimistic MLE) algorithm designs a policy from human comparison data by computing a Lower Confidence Bound (LCB) on the expected policy return to guard against poorly covered regions of the feature space.
Input: Initial parameter estimator $\hat{\theta} \in \mathbb{R}^d$ , empirical covariance matrix $\Sigma_D \in \mathbb{R}^{d \times d}$ , regularization parameter $\lambda > 0$ , confidence radius function $f(n, d, \delta, \lambda) > 0$ , reference vector $v \in \mathbb{R}^d$ , state distribution $q$
Construct confidence set around $\hat{\theta}$ :
   $\Theta(\hat{\theta}, \lambda) = \{ \theta \in \mathbb{R}^d \mid \langle 1, \theta \rangle = 0, \|\theta\|_2 \le B, \|\hat{\theta} - \theta\|_{\Sigma_D + \lambda I} \le f(n, d, \delta, \lambda) \}$
For any candidate policy $\pi$ , define the pessimistic expected return:
   $\hat{J}(\pi) = \min_{\theta \in \Theta(\hat{\theta}, \lambda)} \mathbb{E}_{s \sim q}[\theta^\top (\phi(s, \pi(s)) - v)]$
   $\hat{J}(\pi) = (\mathbb{E}_{s \sim q}[\phi(s, \pi(s))] - v)^\top \hat{\theta} - \|(\Sigma_D + \lambda I)^{-1/2}(\mathbb{E}_{s \sim q}[\phi(s, \pi(s))] - v)\|_2 \cdot f(n, d, \delta, \lambda)$
Return: $\hat{\pi} = \arg\max_\pi \hat{J}(\pi)$
The algorithm computes the point estimate $\hat{\theta}$ via maximum likelihood under the comparison model (such as Bradley-Terry-Luce or Plackett-Luce), sets a confidence ellipsoid with metric $\Sigma_D + \lambda I$ , and penalizes actions whose expected feature shift $(\mathbb{E}_{s \sim q}[\phi(s, \pi(s))] - v)$ has high uncertainty under the empirical query covariance. The reference vector $v \in \mathbb{R}^d$ is typically chosen as a frequent baseline feature in the dataset to center the coverage radius.
Knowl 2 — Sub-optimality and Estimation Error Bounds for Pessimistic MLE under Pairwise Feedback
theoretical result
Consider a contextual bandit with state space $\mathcal{S}$ , action space $\mathcal{A}$ , state distribution $\rho$ , and linear ground-truth reward $r_{\theta^\star}(s, a) = \langle \theta^\star, \phi(s, a) \rangle$ parameterized by known features $\phi(s, a) \in \mathbb{R}^d$ with $\max_{s,a} \|\phi(s, a)\|_2 \le L$ . The parameter space is $\Theta_B = \{ \theta \in \mathbb{R}^d \mid \langle 1, \theta \rangle = 0, \|\theta\|_2 \le B \}$ . Given a pre-collected dataset $\mathcal{D} = \{(s^i, a_0^i, a_1^i, y^i)\}_{i=1}^n$ of pairwise queries whose binary preferences follow the Bradley-Terry-Luce (BTL) model:

$\mathbb{P}(y^i = 1 \mid s^i, a_0^i, a_1^i) = \frac{\exp(r_{\theta^\star}(s^i, a_1^i))}{\exp(r_{\theta^\star}(s^i, a_0^i)) + \exp(r_{\theta^\star}(s^i, a_1^i))},$

the maximum likelihood estimator is $\hat{\theta}_{\text{MLE}} = \arg\min_{\theta \in \Theta_B} \ell_{\mathcal{D}}(\theta)$ , where $\ell_{\mathcal{D}}(\theta)$ is the negative log-likelihood. Define the empirical covariance matrix and the scalar constant:

$\Sigma_D = \frac{1}{n} \sum_{i=1}^n (\phi(s^i, a_1^i) - \phi(s^i, a_0^i))(\phi(s^i, a_1^i) - \phi(s^i, a_0^i))^\top, \quad \gamma = \frac{1}{2 + \exp(-LB) + \exp(LB)}.$

For any $\lambda > 0$ and failure probability $\delta \in (0, 1)$ , the estimation error satisfies with probability at least $1 - \delta$ :

$\|\hat{\theta}_{\text{MLE}} - \theta^\star\|_{\Sigma_D + \lambda I} \le C \sqrt{\frac{d + \log(1/\delta)}{\gamma^2 n} + \lambda B^2}.$

Furthermore, let $\hat{\pi}_{\text{PE}}$ be the policy returned by Pessimistic MLE with $q = \rho$ , $f(n, d, \delta, \lambda) = C \sqrt{\frac{d + \log(1/\delta)}{\gamma^2 n} + \lambda B^2}$ , and any reference vector $v \in \mathbb{R}^d$ . The sub-optimality $\text{SubOpt}(\hat{\pi}_{\text{PE}}) = \mathbb{E}_{s \sim \rho}[r_{\theta^\star}(s, \pi^\star(s)) - r_{\theta^\star}(s, \hat{\pi}_{\text{PE}}(s))]$ satisfies with probability at least $1 - \delta$ :

$\text{SubOpt}(\hat{\pi}_{\text{PE}}) \le 2C \sqrt{\frac{d + \log(1/\delta)}{\gamma^2 n} + \lambda B^2} \cdot \|(\Sigma_D + \lambda I)^{-1/2} \mathbb{E}_{s \sim \rho}[\phi(s, \pi^\star(s)) - v]\|_2,$

where $C > 0$ is a universal constant and $\pi^\star(s) = \arg\max_a r_{\theta^\star}(s, a)$ .
Knowl 3 — Provable Failure of Greedy MLE Policy versus Pessimistic Policy in Contextual Bandits
theoretical result
Standard maximum likelihood estimation without pessimism can yield a greedy policy $\hat{\pi}_{\text{MLE}}(s) = \arg\max_a \langle \hat{\theta}_{\text{MLE}}, \phi(s, a) \rangle$ with constant sub-optimality even though the dataset provides adequate coverage for pessimistic methods.

Consider a single-state linear bandit with four actions having features $\phi(a_1) = [1, 1, 0]^\top$ , $\phi(a_2) = [1, 0, 0]^\top$ , $\phi(a_3) = [0, 0, 0]^\top$ , $\phi(a_4) = [0, 1, 0]^\top$ , and true parameter $\theta^\star = [-1, 0.1, 0.9]^\top \in \Theta_B$ with $B = 2$ . The true rewards are $r(a_1) = -0.9$ , $r(a_2) = -1.0$ , $r(a_3) = 0.0$ , $r(a_4) = 0.1$ , making $a_4$ the optimal action. Suppose the dataset queries $(a_1, a_2)$ for $n - 1$ samples and $(a_2, a_3)$ for $1$ sample. Then for all $n > 1$ :

$\mathbb{E}[\text{SubOpt}(\hat{\pi}_{\text{MLE}})] \ge 0.1.$

In contrast, the single concentratability coefficient $\|\Sigma_D^{-1/2} \phi(a_4)\|_2 = \frac{n}{n-1} \le 2$ (for $n \ge 2$ ). The pessimistic policy $\hat{\pi}_{\text{PE}}$ achieves with probability at least $1 - \delta$ :

$\text{SubOpt}(\hat{\pi}_{\text{PE}}) \le \frac{C \cdot \log(1/\delta)}{\sqrt{n}},$

where $C$ is a universal constant. Thus, greedy policy optimization on an MLE reward model fails due to over-optimization in poorly queried directions, whereas pessimistic MLE converges at the rate $\mathcal{O}(1/\sqrt{n})$ .
Knowl 4 — Minimax Policy Sub-optimality Lower Bound in Contextual Bandits under Concentratability
theoretical result
Let $\text{CB}(\Lambda)$ denote the family of contextual bandit instances $\mathcal{Q} = (\rho, \{(s^i, a_1^i, a_2^i)\}_{i=1}^n, \theta^\star)$ parameterized by $\theta^\star \in \Theta_B = \{ \theta \in \mathbb{R}^d \mid \langle 1, \theta \rangle = 0, \|\theta\|_2 \le B \}$ whose empirical covariance $\Sigma_D$ is invertible and satisfies the single concentratability coefficient bound:

$\|\Sigma_D^{-1/2} \mathbb{E}_{s \sim \rho}[\phi(s, \pi^\star(s))]\|_2 \le \Lambda.$

For any dimension $d > 6$ , sample size $n \ge C_0 d \Lambda^2$ , and coverage parameter $\Lambda \ge 2$ , there exists a feature mapping $\phi: \mathcal{S} \times \mathcal{A} \to \mathbb{R}^d$ such that the minimax policy sub-optimality is lower bounded by:

$\inf_{\hat{\pi}} \sup_{\mathcal{Q} \in \text{CB}(\Lambda)} \text{SubOpt}_{\mathcal{Q}}(\hat{\pi}) \ge C \Lambda \sqrt{\frac{d}{n}},$

where $C, C_0 > 0$ are universal constants. This establishes that the $\mathcal{O}(\Lambda \sqrt{d/n})$ rate achieved by Pessimistic MLE is minimax-optimal up to constant factors.
Knowl 5 — Asymptotic Variance Comparison between Full Plackett-Luce MLE and Pairwise Splitted Estimator
theoretical result
When learning from $K$ -wise ranked comparison data under the Plackett-Luce (PL) model, the full likelihood estimator $\hat{\theta}_{\text{MLE}_K}$ and the pairwise splitted estimator $\hat{\theta}_{\text{MLE}_2}$ (which splits each $K$ -wise ranking into $K(K-1)/2$ pairwise comparisons) are both consistent and asymptotically normal, but $\hat{\theta}_{\text{MLE}_K}$ has strictly smaller or equal asymptotic covariance.

As $n \to \infty$ , the estimators satisfy:

$\sqrt{n}(\hat{\theta}_{\text{MLE}_K} - \theta^\star) \xrightarrow{d} \mathcal{N}(0, I(\theta^\star)^{-1}), \quad \sqrt{n}(\hat{\theta}_{\text{MLE}_2} - \theta^\star) \xrightarrow{d} \mathcal{N}(0, V),$

where $I(\theta^\star)$ is the Fisher Information matrix of the full Plackett-Luce model:

$I(\theta^\star) = \mathbb{E}_{\theta^\star} \left[ \sum_{j=0}^{K-1} \sum_{k=j}^{K-1} \sum_{k'=j}^{K-1} \frac{\exp(\langle \theta^\star, \phi(s^i, a_{\sigma_i(k)}^i) + \phi(s^i, a_{\sigma_i(k')}^i) \rangle)}{2 \left( \sum_{l=j}^{K-1} \exp(\langle \theta^\star, \phi(s^i, a_{\sigma_i(l)}^i) \rangle) \right)^2} (\phi(s^i, a_{\sigma_i(k)}^i) - \phi(s^i, a_{\sigma_i(k')}^i))(\phi(s^i, a_{\sigma_i(k)}^i) - \phi(s^i, a_{\sigma_i(k')}^i))^\top \right],$

and $V = \Sigma^{-1} \mathbb{E}_{\theta^\star}[G G^\top] \Sigma^{-1}$ is the asymptotic covariance of the M-estimator $\hat{\theta}_{\text{MLE}_2}$ , with $x_{jk}^i = \phi(s^i, a_j^i) - \phi(s^i, a_k^i)$ and:

$\Sigma = \mathbb{E}_{\theta^\star} \left[ \sum_{j=0}^{K-1} \sum_{k=j}^{K-1} \frac{\exp(-\langle \theta^\star, x_{\sigma_i(j)\sigma_i(k)}^i \rangle)}{(1 + \exp(-\langle \theta^\star, x_{\sigma_i(j)\sigma_i(k)}^i \rangle))^2} x_{\sigma_i(j)\sigma_i(k)}^i (x_{\sigma_i(j)\sigma_i(k)}^i)^\top \right],$

$G = \sum_{j=0}^{K-1} \sum_{k=j+1}^{K-1} \frac{\exp(-\langle \theta^\star, x_{\sigma_i(j)\sigma_i(k)}^i \rangle)}{1 + \exp(-\langle \theta^\star, x_{\sigma_i(j)\sigma_i(k)}^i \rangle)} x_{\sigma_i(j)\sigma_i(k)}^i.$

By the efficiency of the maximum likelihood estimator among M-estimators, $I(\theta^\star)^{-1} \preceq V$ in the positive semidefinite ordering, demonstrating that utilizing full Plackett-Luce ranking likelihood is statistically more efficient than pairwise decomposition.
Knowl 6 — Reward Estimation and Policy Sub-optimality for Full K-wise Plackett-Luce MLE
theoretical result
Let a dataset $\mathcal{D} = \{(s^i, a_0^i, \dots, a_{K-1}^i, \sigma^i)\}_{i=1}^n$ consist of $K$ -wise comparison queries with full rankings $\sigma^i: [K] \to [K]$ generated under the Plackett-Luce model:

$\mathbb{P}(\sigma^i \mid s^i, a_0^i, \dots, a_{K-1}^i) = \prod_{j=0}^{K-1} \frac{\exp(r_{\theta^\star}(s^i, a_{\sigma^i(j)}^i))}{\sum_{k=j}^{K-1} \exp(r_{\theta^\star}(s^i, a_{\sigma^i(k)}^i))}.$

The full $K$ -wise MLE $\hat{\theta}_{\text{MLE}_K}$ minimizes $\ell_{\mathcal{D}}(\theta) = -\frac{1}{n} \sum_{i=1}^n \sum_{j=0}^{K-1} \log \left( \frac{\exp(\langle \theta, \phi(s^i, a_{\sigma^i(j)}^i) \rangle)}{\sum_{k=j}^{K-1} \exp(\langle \theta, \phi(s^i, a_{\sigma^i(k)}^i) \rangle)} \right)$ over $\Theta_B = \{ \theta \in \mathbb{R}^d \mid \langle 1, \theta \rangle = 0, \|\theta\|_2 \le B \}$ . Define:

$\Sigma_D = \frac{2}{K(K-1)n} \sum_{i=1}^n \sum_{j=0}^{K-1} \sum_{k=j+1}^{K-1} (\phi(s^i, a_j^i) - \phi(s^i, a_k^i))(\phi(s^i, a_j^i) - \phi(s^i, a_k^i))^\top, \quad \gamma = \frac{\exp(-4LB)}{2}.$

For any $\lambda > 0$ and $\delta \in (0, 1)$ , the estimation error satisfies with probability at least $1 - \delta$ :

$\|\hat{\theta}_{\text{MLE}_K} - \theta^\star\|_{\Sigma_D + \lambda I} \le C \sqrt{\frac{K^4(d + \log(1/\delta))}{\gamma^2 n} + \lambda B^2}.$

The pessimistic policy $\hat{\pi}_{\text{PE}_K}$ constructed using Algorithm 1 satisfies with probability at least $1 - \delta$ :

$\text{SubOpt}(\hat{\pi}_{\text{PE}_K}) \le C \sqrt{\frac{K^4(d + \log(1/\delta))}{\gamma^2 n} + \lambda B^2} \cdot \|(\Sigma_D + \lambda I)^{-1/2} \mathbb{E}_{s \sim \rho}[\phi(s, \pi^\star(s)) - v]\|_2.$
Knowl 7 — Reward Estimation and Policy Sub-optimality for Splitted Pairwise Estimator under K-wise Feedback
theoretical result
When $K$ -wise ranking data under the Plackett-Luce model is decomposed into $K(K-1)/2$ pairwise comparisons (as in InstructGPT), the splitted estimator is defined by:

$\hat{\theta}_{\text{MLE}_2} = \arg\min_{\theta \in \Theta_B} -\frac{1}{n} \sum_{i=1}^n \sum_{j=0}^{K-1} \sum_{k=j+1}^{K-1} \log \left( \frac{\exp(\langle \theta, \phi(s^i, a_{\sigma^i(j)}^i) \rangle)}{\exp(\langle \theta, \phi(s^i, a_{\sigma^i(j)}^i) \rangle) + \exp(\langle \theta, \phi(s^i, a_{\sigma^i(k)}^i) \rangle)} \right).$

Define $\Sigma_D = \frac{2}{K(K-1)n} \sum_{i=1}^n \sum_{j=0}^{K-1} \sum_{k=j+1}^{K-1} (\phi(s^i, a_j^i) - \phi(s^i, a_k^i))(\phi(s^i, a_j^i) - \phi(s^i, a_k^i))^\top$ and $\gamma = \frac{1}{2 + \exp(-2LB) + \exp(2LB)}$ .

For any $\lambda > 0$ , $v \in \mathbb{R}^d$ , and $\delta \in (0, 1)$ , with probability at least $1 - \delta$ :

$\|\hat{\theta}_{\text{MLE}_2} - \theta^\star\|_{\Sigma_D + \lambda I} \le C \sqrt{\frac{d + \log(1/\delta)}{\gamma^2 n} + \lambda B^2},$

and the corresponding pessimistic policy $\hat{\pi}_{\text{PE}_2}$ satisfies:

$\text{SubOpt}(\hat{\pi}_{\text{PE}_2}) \le C' \sqrt{\frac{d + \log(1/\delta)}{\gamma^2 n} + \lambda B^2} \cdot \|(\Sigma_D + \lambda I)^{-1/2} \mathbb{E}_{s \sim \rho}[\phi(s, \pi^\star(s)) - v]\|_2,$

where $C, C'$ are universal constants.
Knowl 8 — Sample Complexity and Sub-optimality of Pessimistic Trajectory-Based Preference Learning in MDPs
theoretical result
In a finite-horizon MDP $(\mathcal{S}, \mathcal{A}, H, \{P_h\}_{h=1}^H, \{R_h\}_{h=1}^H, \rho)$ with deterministic linear rewards $r_h(s, a) = \langle \theta^\star, \phi(s, a) \rangle$ satisfying $\|\phi(s, a)\|_\infty \le L$ , human feedback is received as trajectory-level pairwise comparisons between $\tau_0 = (s_0, a_0, \dots, s_H, a_H)$ and $\tau_1 = (s_0, a_0', \dots, s_H', a_H')$ starting at the same initial state $s_0 \sim \rho$ :

$\mathbb{P}(y = 1 \mid s_0, \tau_0, \tau_1) = \frac{\exp\left( \sum_{h=0}^H r_{\theta^\star}(s_h, a_h) \right)}{\exp\left( \sum_{h=0}^H r_{\theta^\star}(s_h, a_h) \right) + \exp\left( \sum_{h=0}^H r_{\theta^\star}(s_h', a_h') \right)}.$

Given $n$ trajectory comparison pairs, define the trajectory difference covariance matrix and constant $\gamma$ :

$\Sigma_D = \frac{1}{n} \sum_{i=1}^n \left( \sum_{h=0}^H (\phi(s_h^i, a_h^i) - \phi(s_h^{i'}, a_h^{i'})) \right) \left( \sum_{h=0}^H (\phi(s_h^i, a_h^i) - \phi(s_h^{i'}, a_h^{i'})) \right)^\top, \quad \gamma = \frac{1}{2 + \exp(-2HLB) + \exp(2HLB)}.$

With probability at least $1 - \delta$ , the MLE estimator satisfies $\|\hat{\theta}_{\text{MLE}} - \theta^\star\|_{\Sigma_D + \lambda I} \le C \sqrt{\frac{d + \log(1/\delta)}{\gamma^2 n} + \lambda B^2}$ .

When the transition kernel $P$ is known, using the state-action occupancy distribution $d^{\pi^\star}(s, a) = \sum_{h=0}^H \mathbb{P}_h(s_h = s, a_h = a \mid \pi^\star)$ as the target distribution $q = d^\pi$ in Pessimistic MLE yields a policy $\hat{\pi}_{\text{PE}}$ satisfying:

$\text{SubOpt}(\hat{\pi}_{\text{PE}}) \le C' \sqrt{\frac{d + \log(1/\delta)}{\gamma^2 n} + \lambda B^2} \cdot \|(\Sigma_D + \lambda I)^{-1/2} \mathbb{E}_{(s, a) \sim d^{\pi^\star}}[\phi(s, a) - v]\|_2.$
Knowl 9 — Sample Complexity of Max-Entropy Inverse Reinforcement Learning
theoretical result
In maximum-entropy Inverse Reinforcement Learning (max-entropy IRL) with deterministic transitions, an expert chooses a trajectory $\tau = (s_0, a_0, \dots, s_H, a_H)$ from the set $\mathcal{T}(s_0)$ of all possible trajectories originating at $s_0$ according to the Plackett-Luce distribution:

$\mathbb{P}(\tau) = \frac{\exp\left(\sum_{h=0}^H \langle \theta^\star, \phi(s_h, a_h) \rangle\right)}{\sum_{\tau' \in \mathcal{T}(s_0)} \exp\left(\sum_{h=0}^H \langle \theta^\star, \phi(s_h', a_h') \rangle\right)}.$

Given $n$ independent trajectory demonstrations $\{\tau^i\}_{i=1}^n$ , let $\hat{\theta}_{\text{MLE}}$ be the maximum likelihood estimator on $\Theta_B = \{ \theta \in \mathbb{R}^d \mid \langle 1, \theta \rangle = 0, \|\theta\|_2 \le B \}$ . Define $\gamma = \frac{1}{2} \exp(-4LB)$ and:

$\Sigma_D = \frac{1}{n \sup_s |\mathcal{T}(s)|^2} \sum_{i=1}^n \sum_{\tau \in \mathcal{T}(s_0^i)} \sum_{\tau' \in \mathcal{T}(s_0^i)} \left( \sum_{h=0}^H (\phi(s_h, a_h) - \phi(s_h', a_h')) \right) \left( \sum_{h=0}^H (\phi(s_h, a_h) - \phi(s_h', a_h')) \right)^\top.$

For any $\lambda > 0$ , with probability at least $1 - \delta$ :

$\|\hat{\theta}_{\text{MLE}} - \theta^\star\|_{\Sigma_D + \lambda I} \le C \sqrt{\frac{\sup_s |\mathcal{T}(s)|^2 \cdot (d + \log(1/\delta))}{\gamma^2 n} + \lambda B^2}.$

The pessimistic policy $\hat{\pi}_{\text{PE}}$ constructed with state-action occupancy weighting $q = d^\pi$ achieves with probability at least $1 - \delta$ :

$\text{SubOpt}(\hat{\pi}_{\text{PE}}) \le C' \sqrt{\frac{\sup_s |\mathcal{T}(s)|^2 \cdot (d + \log(1/\delta))}{\gamma^2 n} + \lambda B^2} \cdot \|(\Sigma_D + \lambda I)^{-1/2} \mathbb{E}_{(s, a) \sim d^{\pi^\star}}[\phi(s, a) - v]\|_2.$
Knowl 10 — Reward Estimation Error Bound under Non-linear and Non-convex Rewards
theoretical result
When the reward function $r_\theta(s, a)$ is non-linear and non-convex in parameter $\theta \in \Theta_B = \{ \theta \in \mathbb{R}^d \mid \langle 1, \theta \rangle = 0, \|\theta\|_2 \le B \}$ , suppose it satisfies the smoothness conditions for all $\theta \in \Theta_B, s \in \mathcal{S}, a \in \mathcal{A}$ :
1. $|r_\theta(s, a)| \le \alpha_0$ (bounded value),
2. $\|\nabla r_\theta(s, a)\|_2 \le \alpha_1$ (bounded gradient),
3. $\|\nabla^2 r_\theta(s, a)\|_2 \le \alpha_2$ (Lipschitz gradient / bounded Hessian).
Let $\hat{\theta}_{\text{MLE}} = \arg\min_{\theta \in \Theta_B} \ell_D(\theta)$ be the pairwise comparison MLE estimator. Define $\gamma = \frac{1}{2 + \exp(-2\alpha_0) + \exp(2\alpha_0)}$ and the empirical gradient covariance:

$\Sigma_D = \frac{1}{n} \sum_{i=1}^n \nabla (r_{\theta^\star}(s^i, a_1^i) - r_{\theta^\star}(s^i, a_0^i)) \nabla (r_{\theta^\star}(s^i, a_1^i) - r_{\theta^\star}(s^i, a_0^i))^\top.$

For any $\lambda > 0$ and $\delta \in (0, 1)$ , with probability at least $1 - \delta$ :

$\|\hat{\theta}_{\text{MLE}} - \theta^\star\|_{\Sigma_D + \lambda I} \le C \sqrt{\frac{d + \log(1/\delta)}{\gamma^2 n} + \left(\lambda + \frac{\alpha_2}{\gamma} + \alpha_1 \alpha_2 B\right) B^2},$

where $C$ is a universal constant. The additional additive term depends on the Hessian bound $\alpha_2$ and does not vanish as $n \to \infty$ , recovering the linear result when $\alpha_2 = 0$ .
Knowl 11 — Reward Parameter Estimation in Action-Based RLHF and Action-Based IRL
theoretical result
In action-based comparison RLHF, human preference between action pairs $(a_0, a_1)$ at state $s$ is dictated by the optimal Q-function $Q^\star_\theta(s, a) = \langle \theta, \phi(s, a) \rangle$ :

$\mathbb{P}(y = 1 \mid s, a_0, a_1) = \frac{\exp(Q^\star_{\theta^\star}(s, a_1))}{\exp(Q^\star_{\theta^\star}(s, a_0)) + \exp(Q^\star_{\theta^\star}(s, a_1))}.$

Under covariance $\Sigma_D = \frac{1}{n} \sum_{i=1}^n (\phi(s^i, a_1^i) - \phi(s^i, a_0^i))(\phi(s^i, a_1^i) - \phi(s^i, a_0^i))^\top$ and $\gamma = \frac{1}{2 + \exp(-LB) + \exp(LB)}$ , the action-based MLE satisfies $\|\hat{\theta}_{\text{MLE}} - \theta^\star\|_{\Sigma_D + \lambda I} \le C \sqrt{\frac{d + \log(1/\delta)}{\gamma^2 n} + \lambda B^2}$ .

In action-based Inverse Reinforcement Learning (action-based IRL), no explicit comparisons are queried; single expert actions are sampled from the Boltzmann policy $\pi^\star(a \mid s) = \frac{\exp(\langle \theta^\star, \phi(s, a) \rangle)}{\sum_{a' \in \mathcal{A}} \exp(\langle \theta^\star, \phi(s, a') \rangle)}$ . With $\Sigma_D = \frac{1}{n |\mathcal{A}|^2} \sum_{i=1}^n \sum_{a, a' \in \mathcal{A}} (\phi(s^i, a) - \phi(s^i, a'))(\phi(s^i, a) - \phi(s^i, a'))^\top$ and $\gamma = \frac{1}{2} \exp(-4LB)$ , the resulting MLE satisfies:

$\|\hat{\theta}_{\text{MLE}} - \theta^\star\|_{\Sigma_D + \lambda I} \le C \sqrt{\frac{|\mathcal{A}|^2(d + \log(1/\delta))}{\gamma^2 n} + \lambda B^2}.$

Both bounds guarantee parameter estimation convergence under their respective query covariances.
Knowl 12 — Empirical Verification of Policy Sub-optimality and Estimator Efficiency for Preference-Based Learning
empirical result
Numerical experiments on simulated contextual bandit and $K$ -wise ranking environments corroborate the theoretical predictions:
1. MLE Policy Failure vs. Pessimistic MLE: On the 4-action linear contextual bandit counterexample, across sample sizes $n \in [10, 500]$ averaged over 100 trials, the parameter estimation error under the semi-norm $\|\hat{\theta}_{\text{MLE}} - \theta^\star\|_{\Sigma_D}$ decreases from $0.35$ to below $0.10$ . However, the sub-optimality of the greedy MLE policy $\hat{\pi}_{\text{MLE}}$ fails to vanish, fluctuating between $0.25$ and $0.40$ . In contrast, the sub-optimality of the pessimistic policy $\hat{\pi}_{\text{PE}}$ steadily drops to zero as $n$ increases.
2. $\text{MLE}_K$ vs. $\text{MLE}_2$ Efficiency: On synthetic 3-dimensional Gaussian feature datasets with true Plackett-Luce generation, for both $K = 4$ and $K = 9$ , both the full Plackett-Luce estimator $\hat{\theta}_{\text{MLE}_K}$ and the pairwise splitted estimator $\hat{\theta}_{\text{MLE}_2}$ converge as $n$ ranges from $10$ to $500$ . However, $\hat{\theta}_{\text{MLE}_K}$ achieves consistently lower parameter estimation error than $\hat{\theta}_{\text{MLE}_2}$ across all sample sizes, and the efficiency advantage of $\hat{\theta}_{\text{MLE}_K}$ over $\hat{\theta}_{\text{MLE}_2}$ widens substantially when $K$ increases from $4$ to $9$ .

Coverage note — None was omitted; all primary contributions covering contextual bandits, $K$-wise comparison models, MDP extensions, inverse reinforcement learning bounds, non-linear reward analyses, and empirical validations were included.

References

1.Y. Abbasi-Yadkori, D. P'al, and C. Szepesv'ari. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
2.P. Abbeel and A. Y. Ng. Apprenticeship learning via inverse reinforcement learning. In Proceedings of the Twenty-First International Conference on Machine Learning, page 1, 2004.
3.Y. Abdelkareem, S. Shehata, and F. Karray. Advances in preference-based reinforcement learning: A review. In 2022 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pages 2527–2532. IEEE, 2022.
4.N. Ailon, Z. S. Karnin, and T. Joachims. Reducing dueling bandits to cardinal bandits. In ICML, volume 32, pages 856–864, 2014.
5.Y. Bai, A. Jones, K. Ndousse, A. Askell, A. Chen, N. DasSarma, D. Drain, S. Fort, D. Ganguli, T. Henighan, et al. Training a helpful and harmless assistant with reinforcement learning from human feedback. arXiv preprint arXiv:2204.05862, 2022a.
6.Y. Bai, S. Kadavath, S. Kundu, A. Askell, J. Kernion, A. Jones, A. Chen, A. Goldie, A. Mirhoseini, C. McKinnon, et al. Constitutional ai: Harmlessness from ai feedback. arXiv preprint arXiv:2212.08073, 2022b.
7.R. A. Bradley and M. E. Terry. Rank analysis of incomplete block designs i: The method of paired comparisons. Biometrika, 39(3/4):324–345, 1952.
8.J. Bretagnolle and C. Huber. Estimation des densit'es: risque minimax. Zeitschrift f¨ur Wahrscheinlichkeitstheorie und Verwandte Gebiete, 47(2):119–137, 1979. doi: 10.1007/BF00535278. URL https://doi.org/10.1007/BF00535278.
9.D. Brown, W. Goo, P. Nagarajan, and S. Niekum. Extrapolating beyond suboptimal demonstrations via inverse reinforcement learning from observations. In International Conference on Machine Learning, pages 783–792. PMLR, 2019.
10.R. Busa-Fekete, B. Sz¨or'enyi, P. Weng, W. Cheng, and E. H¨ullermeier. Preference-based reinforcement learning: evolutionary direct policy search using a preference-based racing algorithm. Machine Learning, 97(3):327–351, 2014.
11.Z. Cao, T. Qin, T.-Y. Liu, M.-F. Tsai, and H. Li. Learning to rank: From pairwise approach to listwise approach. In Proceedings of the 24th International Conference on Machine Learning, pages 129–136, 2007.
12.N. S. Chatterji, A. Pacchiano, P. L. Bartlett, and M. I. Jordan. On the theory of reinforcement learning with once-per-episode feedback, 2022.
13.X. Chen, P. N. Bennett, K. Collins-Thompson, and E. Horvitz. Pairwise ranking aggregation in a crowdsourced setting. In Proceedings of the Sixth ACM International Conference on Web Search and Data Mining, pages 193–202, 2013.
14.X. Chen, H. Zhong, Z. Yang, Z. Wang, and L. Wang. Human-in-the-loop: Provably efficient preferencebased reinforcement learning with general function approximation. In International Conference on Machine Learning, pages 3773–3793. PMLR, 2022.
15.Y. Chen and C. Suh. Spectral MLE: top-k rank aggregation from pairwise comparisons. In International Conference on Machine Learning, pages 371–380. PMLR, 2015.
16.C.-A. Cheng, T. Xie, N. Jiang, and A. Agarwal. Adversarially trained actor critic for offline reinforcement learning. arXiv preprint arXiv:2202.02446, 2022.
17.P. F. Christiano, J. Leike, T. Brown, M. Martic, S. Legg, and D. Amodei. Deep reinforcement learning from human preferences. Advances in Neural Information Processing Systems, 30, 2017a.
18.P. F. Christiano, J. Leike, T. Brown, M. Martic, S. Legg, and D. Amodei. Deep reinforcement learning from human preferences. In Advances in Neural Information Processing Systems, pages 4299–4307, 2017b.
19.L. Faury, M. Abeille, C. Calauz`enes, and O. Fercoq. Improved optimistic algorithms for logistic bandits. In International Conference on Machine Learning, pages 3052–3060. PMLR, 2020.
20.U. Feige, P. Raghavan, D. Peleg, and E. Upfal. Computing with noisy information. SIAM Journal on Computing, 23(5):1001–1018, 1994.
21.P. Florence, C. Lynch, A. Zeng, O. A. Ramirez, A. Wahid, L. Downs, A. Wong, J. Lee, I. Mordatch, and J. Tompson. Implicit behavioral cloning. In Conference on Robot Learning, pages 158–168. PMLR, 2022.
22.P. Gajane, T. Urvoy, and F. Cl'erot. A relative exponential weighing algorithm for adversarial utility-based dueling bandits. In Proceedings of the 32nd International Conference on Machine Learning, pages 218–227, 2015.
23.D. Ganguli, L. Lovitt, J. Kernion, A. Askell, Y. Bai, S. Kadavath, B. Mann, E. Perez, N. Schiefer, K. Ndousse, et al. Red teaming language models to reduce harms: Methods, scaling behaviors, and lessons learned. arXiv preprint arXiv:2209.07858, 2022.
24.L. Gao, J. Schulman, and J. Hilton. Scaling laws for reward model overoptimization. arXiv preprint arXiv:2210.10760, 2022.
25.S. Ghoshal and A. Saha. Exploiting correlation to achieve faster learning rates in low-rank preference bandits. In International Conference on Artificial Intelligence and Statistics, pages 456–482. PMLR, 2022.
26.A. Glaese, N. McAleese, M. Tre·bacz, J. Aslanides, V. Firoiu, T. Ewalds, M. Rauh, L. Weidinger, M. Chadwick, P. Thacker, et al. Improving alignment of dialogue agents via targeted human judgements. arXiv preprint arXiv:2209.14375, 2022.
27.V. P. Godambe. An optimum property of regular maximum likelihood estimation. The Annals of Mathematical Statistics, 31(4):1208–1211, 1960.
28.B. Hajek, S. Oh, and J. Xu. Minimax-optimal inference from partial rankings. Advances in Neural Information Processing Systems, 27, 2014.
29.R. Heckel, M. Simchowitz, K. Ramchandran, and M. Wainwright. Approximate ranking from pairwise comparisons. In International Conference on Artificial Intelligence and Statistics, pages 1057–1066. PMLR, 2018.
30.R. Heckel, N. B. Shah, K. Ramchandran, and M. J. Wainwright. Active ranking from pairwise comparisons and when parametric assumptions do not help. Annals of Statistics, 47(6):3099–3126, 2019.
31.J. Ho and S. Ermon. Generative adversarial imitation learning. Advances in Neural Information Processing Systems, 29, 2016.
32.D. Hsu, S. Kakade, and T. Zhang. A tail inequality for quadratic forms of subgaussian random vectors. Electronic Communications in Probability, 17:1–6, 2012.
33.A. Hussein, M. M. Gaber, E. Elyan, and C. Jayne. Imitation learning: A survey of learning methods. ACM Computing Surveys (CSUR), 50(2):1–35, 2017.
34.A. Jain, B. Wojcik, T. Joachims, and A. Saxena. Learning trajectory preferences for manipulators via iterative improvement. In Advances in neural information processing systems, pages 575–583, 2013.
35.M. Jang, S. Kim, C. Suh, and S. Oh. Optimal sample complexity of m-wise data for top-k ranking. Advances in Neural Information Processing Systems, 30, 2017.
36.Y. Jin, Z. Yang, and Z. Wang. Is pessimism provably efficient for offline RL? In International Conference on Machine Learning, pages 5084–5096. PMLR, 2021.
37.J. I. Kiger. The depth/breadth trade-off in the design of menu-driven user interfaces. International journal of man-machine studies, 20(2):201–213, 1984.
38.W. B. Knox and P. Stone. Tamer: Training an agent manually via evaluative reinforcement. In 7th IEEE International Conference on Development and Learning, pages 292–297. IEEE, 2008.
39.J. Komiyama, J. Honda, H. Kashima, and H. Nakagawa. Regret lower bound and optimal algorithm in dueling bandit problem. In COLT, pages 1141–1154, 2015.
40.I. Kostrikov, A. Nair, and S. Levine. Offline reinforcement learning with implicit Q-learning. arXiv preprint arXiv:2110.06169, 2021.
41.A. Kumar, A. Zhou, G. Tucker, and S. Levine. Conservative Q-learning for offline reinforcement learning. Advances in Neural Information Processing Systems, 33:1179–1191, 2020.
42.A. Kupcsik, D. Hsu, and W. S. Lee. Learning dynamic robot-to-human object handover from human feedback. In Robotics research, pages 161–176. Springer, 2018.
43.M.-j. Lee. M-estimator and maximum likelihood estimator (mle). In Micro-Econometrics, pages 91–132. Springer, 2008.
44.G. Li, C. Ma, and N. Srebro. Pessimism for offline linear contextual bandits using ℓp confidence sets. arXiv preprint arXiv:2205.10671, 2022.
45.T.-Y. Liu et al. Learning to rank for information retrieval. Foundations and Trends® in Information Retrieval, 3(3):225–331, 2009.
46.R. D. Luce. Individual Choice Behavior: A Theoretical Analysis. Courier Corporation, 2012.
47.J. MacGlashan, M. K. Ho, R. Loftin, B. Peng, G. Wang, D. L. Roberts, M. E. Taylor, and M. L. Littman. Interactive learning from policy-dependent human feedback. In International Conference on Machine Learning, pages 2285–2294. PMLR, 2017.
48.C. Mao, J. Weed, and P. Rigollet. Minimax rates and efficient algorithms for noisy sorting. In Algorithmic Learning Theory, pages 821–847. PMLR, 2018.
49.J. Menick, M. Trebacz, V. Mikulik, J. Aslanides, F. Song, M. Chadwick, M. Glaese, S. Young, L. CampbellGillingham, G. Irving, et al. Teaching language models to support answers with verified quotes. arXiv preprint arXiv:2203.11147, 2022.
50.G. A. Miller. The magical number seven, plus or minus two: Some limits on our capacity for processing information. Psychological Review, 63(2):81, 1956.
51.R. Nakano, J. Hilton, S. Balaji, J. Wu, L. Ouyang, C. Kim, C. Hesse, S. Jain, V. Kosaraju, W. Saunders, et al. Webgpt: Browser-assisted question-answering with human feedback. arXiv preprint arXiv:2112.09332, 2021.
52.S. Negahban, S. Oh, K. K. Thekumparampil, and J. Xu. Learning from comparisons and choices. The Journal of Machine Learning Research, 19(1):1478–1572, 2018.
53.G. Neu and C. Szepesv'ari. Training parsers by inverse reinforcement learning. Machine Learning, 77(2): 303–337, 2009.
54.A. Y. Ng, S. Russell, et al. Algorithms for inverse reinforcement learning. In International Conference on Machine Learning, volume 1, page 2, 2000.
55.E. R. Novoseller, Y. Sui, Y. Yue, and J. W. Burdick. Dueling posterior sampling for preference-based reinforcement learning. arXiv preprint arXiv:1908.01289, 2019.
56.L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. L. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, et al. Training language models to follow instructions with human feedback. arXiv preprint arXiv:2203.02155, 2022.
57.A. Pacchiano, A. Saha, and J. Lee. Dueling rl: reinforcement learning with trajectory preferences. arXiv preprint arXiv:2111.04850, 2021.
58.R. L. Plackett. The analysis of permutations. Journal of the Royal Statistical Society: Series C (Applied Statistics), 24(2):193–202, 1975.
59.A. Rajkumar and S. Agarwal. A statistical convergence perspective of algorithms for rank aggregation from pairwise data. In International conference on machine learning, pages 118–126. PMLR, 2014.
60.D. Ramachandran and E. Amir. Bayesian inverse reinforcement learning. In IJCAI, volume 7, pages 2586–2591, 2007.
61.R. Ramamurthy, P. Ammanabrolu, K. Brantley, J. Hessel, R. Sifa, C. Bauckhage, H. Hajishirzi, and Y. Choi. Is reinforcement learning (not) for natural language processing?: Benchmarks, baselines, and building blocks for natural language policy optimization. arXiv preprint arXiv:2210.01241, 2022.
62.P. Rashidinejad, B. Zhu, C. Ma, J. Jiao, and S. Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34: 11702–11716, 2021.
63.T. L. Saaty and M. S. Ozdemir. Why the magic number seven plus or minus two. Mathematical and computer modelling, 38(3-4):233–244, 2003.
64.D. Sadigh, A. D. Dragan, S. Sastry, and S. A. Seshia. Active preference-based learning of reward functions. In Robotics: Science and Systems, 2017.
65.A. Saha and A. Gopalan. Battle of bandits. In Uncertainty in Artificial Intelligence, 2018a.
66.A. Saha and A. Gopalan. Active ranking with subset-wise preferences. International Conference on Artificial Intelligence and Statistics (AISTATS), 2018b.
67.A. Saha and A. Gopalan. PAC Battling Bandits in the Plackett-Luce Model. In Algorithmic Learning Theory, pages 700–737, 2019.
68.A. Saha and A. Krishnamurthy. Efficient and optimal algorithms for contextual dueling bandits under realizability. In International Conference on Algorithmic Learning Theory, pages 968–994. PMLR, 2022.
69.N. Shah, S. Balakrishnan, J. Bradley, A. Parekh, K. Ramchandran, and M. Wainwright. Estimation from pairwise comparisons: Sharp minimax bounds with topology dependence. In Artificial Intelligence and Statistics, pages 856–865. PMLR, 2015.
70.N. B. Shah and M. J. Wainwright. Simple, robust and optimal ranking from pairwise comparisons. The Journal of Machine Learning Research, 18(1):7246–7283, 2017.
71.R. M. Shiffrin and R. M. Nosofsky. Seven plus or minus two: a commentary on capacity limitations. 1994.
72.D. Shin, A. D. Dragan, and D. S. Brown. Benchmarks and algorithms for offline preference-based reward learning. arXiv preprint arXiv:2301.01392, 2023.
73.M. Soare, A. Lazaric, and R. Munos. Best-arm identification in linear bandits. Advances in Neural Information Processing Systems, 27, 2014.
74.N. Stiennon, L. Ouyang, J. Wu, D. Ziegler, R. Lowe, C. Voss, A. Radford, D. Amodei, and P. F. Christiano. Learning to summarize with human feedback. Advances in Neural Information Processing Systems, 33: 3008–3021, 2020.
75.A. W. Van der Vaart. Asymptotic Statistics, volume 3. Cambridge university press, 2000.
76.G. Warnell, N. Waytowich, V. Lawhern, and P. Stone. Deep tamer: Interactive agent shaping in highdimensional state spaces. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
77.C. Wirth, J. Furnkranz, G. Neumann, et al. Model-free preference-based reinforcement learning. In 30th AAAI Conference on Artificial Intelligence, AAAI 2016, pages 2222–2228, 2016.
78.C. Wirth, R. Akrour, G. Neumann, and J. F¨urnkranz. A survey of preference-based reinforcement learning methods. The Journal of Machine Learning Research, 18(1):4945–4990, 2017.
79.J. Wu, L. Ouyang, D. M. Ziegler, N. Stiennon, R. Lowe, J. Leike, and P. Christiano. Recursively summarizing books with human feedback. arXiv preprint arXiv:2109.10862, 2021.
80.F. Xia, T.-Y. Liu, J. Wang, W. Zhang, and H. Li. Listwise approach to learning to rank: theory and algorithm. In Proceedings of the 25th International Conference on Machine Learning, pages 1192–1199, 2008.
81.T. Xie, C.-A. Cheng, N. Jiang, P. Mineiro, and A. Agarwal. Bellman-consistent pessimism for offline reinforcement learning. Advances in Neural Information Processing Systems, 34:6683–6694, 2021a.
82.T. Xie, N. Jiang, H. Wang, C. Xiong, and Y. Bai. Policy finetuning: Bridging sample-efficient offline and online reinforcement learning. Advances in Neural Information Processing Systems, 34:27395–27407, 2021b.
83.T. Xu and Y. Liang. Provably efficient offline reinforcement learning with trajectory-wise reward. arXiv preprint arXiv:2206.06426, 2022.
84.Y. Xu, R. Wang, L. Yang, A. Singh, and A. Dubrawski. Preference-based reinforcement learning with finite-time guarantees. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 18784–18794. Curran Associates, Inc., 2020. URL https://proceedings.neurips.cc/paper/2020/file/d9d3837ee7981e8c064774da6cdd98bf-Paper.pdf.
85.B. Yu. Assouad, fano, and le cam. In Festschrift for Lucien Le Cam, pages 423–435. Springer, 1997.
86.Y. Yue and T. Joachims. Interactively optimizing information retrieval systems as a dueling bandits problem. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 1201–1208. ACM, 2009.
87.Y. Yue and T. Joachims. Beat the mean bandit. In Proceedings of the 28th International Conference on Machine Learning (ICML-11), pages 241–248, 2011.
88.Y. Yue, J. Broder, R. Kleinberg, and T. Joachims. The k-armed dueling bandits problem. Journal of Computer and System Sciences, 78(5):1538–1556, 2012.
89.A. Zanette. When is realizability sufficient for off-policy reinforcement learning? arXiv preprint arXiv:2211.05311, 2022.
90.A. Zanette, M. J. Wainwright, and E. Brunskill. Provable benefits of actor-critic methods for offline reinforcement learning. Advances in Neural Information Processing Systems, 34:13626–13640, 2021.
91.B. D. Ziebart, A. L. Maas, J. A. Bagnell, A. K. Dey, et al. Maximum entropy inverse reinforcement learning. In AAAI, volume 8, pages 1433–1438. Chicago, IL, USA, 2008.
92.D. M. Ziegler, N. Stiennon, J. Wu, T. B. Brown, A. Radford, D. Amodei, P. Christiano, and G. Irving. Fine-tuning language models from human preferences. arXiv preprint arXiv:1909.08593, 2019.
93.M. Zoghi, S. Whiteson, R. Munos, M. d. Rijke, et al. Relative upper confidence bound for the k-armed dueling bandit problem. In JMLR Workshop and Conference Proceedings, number 32, pages 10–18. JMLR, 2014a.
94.M. Zoghi, S. A. Whiteson, M. De Rijke, and R. Munos. Relative confidence sampling for efficient on-line ranker evaluation. In Proceedings of the 7th ACM international conference on Web search and data mining, pages 73–82. ACM, 2014b.

Citation

MLA

Zhu, B., et al. “Principled Reinforcement Learning with Human Feedback from Pairwise or $K$-wise Comparisons”. arXiv, 2023, http://arxiv.org/abs/2301.11270v5.

APA

Zhu, B., Jiao, J., & Jordan, M. I. (2023). Principled Reinforcement Learning with Human Feedback from Pairwise or $K$-wise Comparisons. arXiv. http://arxiv.org/abs/2301.11270v5

Chicago

Zhu, B., J. Jiao, and M. I. Jordan. 2023. “Principled Reinforcement Learning with Human Feedback from Pairwise or $K$-wise Comparisons”. arXiv. http://arxiv.org/abs/2301.11270v5.

Harvard

Zhu, B., Jiao, J. and Jordan, M.I. (2023) “Principled Reinforcement Learning with Human Feedback from Pairwise or $K$-wise Comparisons”, arXiv [Preprint]. Available at: http://arxiv.org/abs/2301.11270v5.

Vancouver

1. Zhu B, Jiao J, Jordan MI (2023) Principled Reinforcement Learning with Human Feedback from Pairwise or $K$-wise Comparisons. arXiv

BibTeX

@article{zhu2023principled,
  title = {Principled Reinforcement Learning with Human Feedback from Pairwise or $K$-wise Comparisons},
  author = {Zhu, Banghua and Jiao, Jiantao and Jordan, Michael I.},
  year = {2023},
  journal = {arXiv},
  url = {http://arxiv.org/abs/2301.11270v5},
  eprint = {2301.11270}
}

Metadata:arXiv

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: https://creativecommons.org/licenses/by/4.0/

Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Pessimistic Maximum Likelihood Policy Optimization Algorithm for Preference-Based Learning

Knowl 2 — Sub-optimality and Estimation Error Bounds for Pessimistic MLE under Pairwise Feedback

Knowl 3 — Provable Failure of Greedy MLE Policy versus Pessimistic Policy in Contextual Bandits

Knowl 4 — Minimax Policy Sub-optimality Lower Bound in Contextual Bandits under Concentratability

Knowl 5 — Asymptotic Variance Comparison between Full Plackett-Luce MLE and Pairwise Splitted Estimator

Knowl 6 — Reward Estimation and Policy Sub-optimality for Full K-wise Plackett-Luce MLE

Knowl 7 — Reward Estimation and Policy Sub-optimality for Splitted Pairwise Estimator under K-wise Feedback

Knowl 8 — Sample Complexity and Sub-optimality of Pessimistic Trajectory-Based Preference Learning in MDPs

Knowl 9 — Sample Complexity of Max-Entropy Inverse Reinforcement Learning

Knowl 10 — Reward Estimation Error Bound under Non-linear and Non-convex Rewards

Knowl 11 — Reward Parameter Estimation in Action-Based RLHF and Action-Based IRL

Knowl 12 — Empirical Verification of Policy Sub-optimality and Estimator Efficiency for Preference-Based Learning

References

Citation

BibTeX

Access the Paper