Corruption-robust Offline Multi-agent Reinforcement Learning From Human Feedback

Andi Nika; Debmalya Mandal; Parameswaran Kamalaruban; Adish Singla; Goran Radanović

cs.LGMar 30, 2026

Corruption-robust Offline Multi-agent Reinforcement Learning From Human Feedback

Authors: Andi Nika, Debmalya Mandal, Parameswaran Kamalaruban, Adish Singla, Goran Radanović

Organizations: MPI-SWS · University of Warwick · Visa

Abstract

We consider robustness against data corruption in offline multi-agent reinforcement learning from human feedback (MARLHF) under a strong-contamination model: given a dataset $D$ of trajectory-preference tuples (each preference being an $n$ -dimensional binary label vector representing each of the $n$ agents' preferences), an $ε$ -fraction of the samples may be arbitrarily corrupted. We model the problem using the framework of linear Markov games. First, under a uniform coverage assumption - where every policy of interest is sufficiently represented in the clean (prior to corruption) data - we introduce a robust estimator that guarantees an $O(ε^{1 - o(1)})$ bound on the Nash equilibrium gap. Next, we move to the more challenging unilateral coverage setting, in which only a Nash equilibrium and its single-player deviations are covered. In this case, our proposed algorithm achieves an $O(\sqrtε)$ bound on the Nash gap. Both of these procedures, however, suffer from intractable computation. To address this, we relax our solution concept to coarse correlated equilibria (CCE). Under the same unilateral coverage regime, we derive a quasi-polynomial-time algorithm whose CCE gap scales as $O(\sqrtε)$ . To the best of our knowledge, this is the first systematic treatment of adversarial data corruption in offline MARLHF.

Figures & tables

	Bounds on the NE (CCE) gap
NE & Unif. Cov.	$\widetilde{O}\left(\left(\frac{1}{\xi_{R}}+\frac{1}{\xi_{P}}\right)Hn\epsilon^{1-o(1)}+\frac{H^{2}n\sqrt{\textnormal{poly}(d)}}{\xi_{P}\sqrt{m}}\right)$
NE & Unil. Cov.	$\widetilde{O}\left(\left(\frac{1}{\sqrt{C_{R}}}+\frac{1}{\sqrt{C_{P}}}+\frac{1}{\sqrt{T_{1}}}\right)\left(H^{5/2}nd^{3/4}\sqrt{\epsilon}+\frac{H^{2}n\sqrt{\textnormal{poly}(d)}}{\sqrt{m}}\right)\right)$
CCE & Unil. Cov.	$\widetilde{O}\left(\left(\frac{1}{\sqrt{C_{R}}}+\frac{1}{\sqrt{C_{P}}}+\frac{1}{\sqrt{T_{1}}}\right)\left(H^{5/2}nd^{3/4}\sqrt{\epsilon}+\frac{H^{2}n\sqrt{\textnormal{poly}(d)}}{\sqrt{m}}\right)+\frac{Hn^{2}}{T_{2}}\right)$

Table 1: Summary of our bounds for: (i) NE gap minimization under uniform coverage, (ii) NE gap minimization under unilateral coverage, and (iii) CCE gap minimization under unilateral coverage. Here,

\widetilde{O}

hides any poly-logarithmic factors,

n

denotes the number of agents,

H

denotes the horizon and

d

denotes the dimension. Moreover,

\xi_{R}

and

\xi_{P}

denote the uniform coverage coefficients, while

C_{R}

and

C_{P}

denote the unilateral coverage coefficients;

\epsilon

denotes the corruption parameter,

m

is the data size,

T_{1}

is the number of gradient steps while

T_{2}

is the number of steps for which OptimisticHedge is run. It is worth mentioning that our bounds have optimal dependence on

\epsilon

in the uniform coverage setting, while maintaining the same dependence as the single-agent (and two-player zero-sum Markov game) settings under non-uniform coverage. Moreover, note that the algorithm for CCE approximation is also computationally efficient.

\displaystyle\widehat{\theta}^{(t+1)}_{i}=\mathcal{P}_{\Theta_{\textnormal{Unil}}(\widetilde{\theta}_{i})}\left(\widehat{\theta}^{(t)}_{i}+\eta\widetilde{\nabla}_{\theta_{i}}\textnormal{Gap}\left(\bm{\pi}^{*},\widehat{\bm{\theta}}^{(t)}\right)\right)~.

Algorithm 3 Reward Parameter Estimation ( RewardEst )

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

\displaystyle\pi^{\dagger,(t+1)}_{i}(a^{\dagger})=\frac{\pi^{\dagger,(t)}_{i}(a^{\dagger})\cdot\exp\left(\nu\cdot u^{(t)}_{i}(a^{\dagger})\right)}{\sum_{a^{\ddagger}}\pi^{\dagger,(t)}_{i}(a^{\ddagger})\cdot\exp\left(\nu\cdot u^{(t)}_{i}(a^{\ddagger})\right)}~.

Appendix

Algorithm 8 Optimistic Hedge for

n

\min-\max

Games ( OptimisticHedge )

Multi-Agent Reinforcement Learning

Multi-agent reinforcement learning studies how interacting agents learn coordinated or competitive policies through shared experience and rewards.

See all 373 papers

Corruption Robust Offline Reinforcement Learning with Human Feedback
Feb 9, 2024Debmalya Mandal, Andi Nika, Parameswaran Kamalaruban +2Offline RL Corruption Robustness
Dept. of Computer Science University of Warwick, UK · Max-Planck Institute for Software Systems, Germany · Independent Researcher London, UK
Interaction-Breaking Adversarial Learning Framework for Robust Multi-Agent Reinforcement Learning
May 18, 2026Sunwoo Lee, Mingu Kang, Yonghyeon Jo +1Adversarial Training Multi-Agent Coordination
Graduate School of Artificial Intelligence, UNIST, Ulsan, South Korea
Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximation
May 4, 2026Jingchu Gai, Laixi ShiMulti-Agent System Optimization Markov Models
Machine Learning Department, Carnegie Mellon University. · Department of Electrical and Computer Engineering, Johns Hopkins University, MD 21286, USA.

Feb 9, 2024J/K move · Enter open · S save

Corruption Robust Offline Reinforcement Learning with Human Feedback

Debmalya Mandal, Andi Nika, Parameswaran Kamalaruban, Adish Singla+1

Dept. of Computer Science University of Warwick, UK · Max-Planck Institute for Software Systems, Germany · Independent Researcher London, UK

Offline RL Corruption Robustness Robust RL Preference-Based RL RL from Human Feedback

Open paper AskPDF arXiv

We study data corruption robustness for reinforcement learning with human feedback (RLHF) in an offline setting. Given an offline dataset of pairs of trajectories along with feedback about human preferences, an

\varepsilon

-fraction of the pairs is corrupted (e.g., feedback flipped or trajectory features manipulated), capturing an adversarial attack or noisy human preferences. We aim to design algorithms that identify a near-optimal policy from the corrupted data, with provable guarantees. Existing theoretical works have separately studied the settings of corruption robust RL (learning from scalar rewards directly under corruption) and offline RLHF (learning from human feedback without corruption); however, they are inapplicable to our problem of dealing with corrupted data in offline RLHF setting. To this end, we design novel corruption robust offline RLHF methods under various assumptions on the coverage of the data-generating distributions. At a high level, our methodology robustifies an offline RLHF framework by first learning a reward model along with confidence sets and then learning a pessimistic optimal policy over the confidence set. Our key insight is that learning optimal policy can be done by leveraging an offline corruption-robust RL oracle in different ways (e.g., zero-order oracle or first-order oracle), depending on the data coverage assumptions. To our knowledge, ours is the first work that provides provable corruption robust offline RLHF methods.

Abstract

Multi-Agent Reinforcement Learning

Explore similar work

Corruption Robust Offline Reinforcement Learning with Human Feedback

Interaction-Breaking Adversarial Learning Framework for Robust Multi-Agent Reinforcement Learning

Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximation