Technical Summary: Corruption Robust Offline Reinforcement Learning with Human Feedback

Problem Definition

This paper addresses the challenge of corruption robustness in Offline Reinforcement Learning from Human Feedback (RLHF). The authors consider a setting where an offline dataset consists of pairs of trajectories $(\tau^0, \tau^1)$ along with human preference feedback $o \in \{+1, -1\}$. The core problem is that an $\epsilon$-fraction of this data is corrupted by an adversary. This corruption can manifest as:

1. Feedback manipulation: Flipping the preference label $o$.
2. Trajectory feature manipulation: Altering the features of the trajectories $\tau$.

The goal is to design algorithms that can identify a near-optimal policy from such corrupted data with provable theoretical guarantees. The authors operate under the assumption of Linear Markov Decision Processes (MDPs), where rewards and transitions are linear functions of a $d$-dimensional feature map $\phi$, with a horizon length $H$.

Existing literature has separately studied corruption-robust RL (learning from scalar rewards under corruption) and offline RLHF (learning from preferences under clean data). However, these approaches are inapplicable to the specific intersection of learning from preference data that is corrupted in an offline setting.

Methodology

The proposed methodology follows a three-step framework to reduce the problem of robust offline RLHF to the problem of robust offline RL:

1. Robust Reward Model Estimation: The authors first robustly learn the reward parameter $\theta$ by solving a Trimmed Maximum Likelihood Estimation (MLE) problem. Instead of using all data, the algorithm selects a subset of $(1-\epsilon)N$ samples that maximizes the likelihood. To handle corrupted features, the method employs robust covariance estimation to whiten the covariates before running an alternating optimization procedure to find an approximate stationary point.
2. Confidence Set Construction: A confidence set $\Theta(\mathcal{D})$ is constructed around the estimated reward parameter $\hat{\theta}$. This set is defined based on the likelihood ratio between the estimated parameter and the true parameter, ensuring the true parameter lies within the set with high probability despite the corruption.
3. Pessimistic Policy Optimization: The final step involves learning a pessimistic optimal policy over the constructed confidence set. This is achieved by reducing the problem to corruption-robust offline RL. The specific algorithm used for this reduction depends on the coverage assumptions of the offline data distribution.

The paper instantiates this general framework under three distinct data coverage assumptions, utilizing different robust RL oracles for each:

1. Uniform Coverage

Under the assumption that the offline data uniformly covers the feature space (specifically, the difference feature covariance matrix $\Sigma^{diff}$ is well-conditioned), the authors utilize an existing corruption-robust offline RL algorithm, R-LSVI [Zha+22], as a zero-order oracle.

• Mechanism: The algorithm treats the robust offline RL method as a black box that returns a policy and a value estimate but does not provide gradient information.
• Result: This yields a suboptimality gap of $O(\epsilon^{1-o(1)})$, which is nearly optimal with respect to the corruption fraction $\epsilon$.

2. Low Relative Condition Number

Recognizing that uniform coverage is a strong assumption, the authors relax it to a Low Relative Condition Number assumption. This condition is weaker, requiring only that the ratio of the target policy's feature covariance to the behavior policy's covariance is bounded.

• Mechanism: Since the zero-order oracle (R-LSVI) cannot provide gradients, the authors employ a Gaussian approximation technique [NS17] to construct an approximate sub-gradient of the optimal value function $V^*(\theta)$. They treat the robust offline RL oracle as a biased, zero-order oracle and perform Projected Sub-Gradient Descent over the confidence set.
• Result: This approach achieves a suboptimality gap of $\tilde{O}(H^2 d \sqrt{\alpha \epsilon} + H^{5/4} d^{3/4} (\alpha \epsilon)^{1/4})$, where $\alpha$ is the relative condition number. The dependence on $\epsilon$ is $O(\epsilon^{1/4})$.

3. Bounded Generalized Coverage Ratio

To further improve the dependence on $\epsilon$, the authors consider a Bounded Generalized Coverage Ratio assumption, recently introduced by Gabbianelli et al. [Gab+24].

• Mechanism: Under this assumption, the authors design a novel corruption-robust offline RL method (Algorithm 7) that acts as a first-order oracle. This method, based on a primal-dual framework for linear MDPs, returns not only an approximately optimal policy but also an approximate sub-gradient of the optimal value function. This allows the main RLHF algorithm to perform direct projected sub-gradient descent without needing zero-order smoothing.
• Result: This yields a significantly improved suboptimality gap of $\tilde{O}(\nu \sqrt{\epsilon} H^2 d^{3/2})$, where $\nu$ is the generalized coverage ratio. The dependence on $\epsilon$ improves to $O(\sqrt{\epsilon})$.

Key Contributions and Results

The paper provides the first provable corruption-robust offline RLHF methods. The key contributions and theoretical results are summarized in Table 1 of the paper:

• Novel Framework: The reduction of robust RLHF to robust offline RL via robust reward estimation and confidence set construction.
• Algorithmic Instantiations:
  • Algorithm 1: For uniform coverage, achieving $O(\epsilon^{1-o(1)})$ suboptimality using R-LSVI as a zero-order oracle.
  • Algorithm 3: For low relative condition number, achieving $\tilde{O}(\epsilon^{1/4})$ suboptimality using Gaussian approximation with a zero-order oracle.
  • Algorithm 4 & 7: For bounded generalized coverage ratio, achieving $\tilde{O}(\sqrt{\epsilon})$ suboptimality using a newly designed first-order robust offline RL oracle.
• Oracle Efficiency: The paper highlights that moving from zero-order to first-order access (Algorithm 7) significantly reduces the number of oracle calls required and improves the dependence on the corruption parameter $\epsilon$.

Significance and Claims

The authors claim this work is the first to combine corruption robustness with offline RLHF, providing rigorous theoretical guarantees where previous works could not.

• Robustness to Adversarial Attacks: The methods are designed to withstand adversarial manipulation of both preference labels and trajectory features, a critical requirement for real-world deployment where data reliability is compromised.
• Theoretical Guarantees: The paper provides explicit bounds on the suboptimality gap in terms of the corruption fraction $\epsilon$, horizon $H$, feature dimension $d$, and coverage constants ($\xi, \alpha, \nu$).
• Modest Scope and Future Work: The authors are modest about the current scope, noting that the results are specific to linear MDPs. They acknowledge that extending these results to non-convex reward functions or general function approximation (e.g., deep neural networks) is a significant challenge, as the convexity of the optimal value function $V^*(\theta)$ in $\theta$—which is crucial for their gradient-based proofs—may not hold in non-linear settings. They also note that while they provide preliminary simulation results, applying these methods to practical settings like fine-tuning Large Language Models (LLMs) remains an open and challenging direction for future research.