Research map / Reinforcement learning / RL from feedback

A Unified Linear Programming Framework for Offline Reward Learning from Human Demonstrations and Feedback

ICML 2024 · Reinforcement learning › RL from feedback · approach: Theory of RLHF · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes an offline linear-programming framework that estimates a convex feasible reward set for IRL (from expert trajectories) and RLHF (from pairwise comparisons), with a sample-complexity optimality guarantee and no assumed preference model.

Problem

Offline reward learning from expert demonstrations (IRL) and pairwise human feedback (RLHF) typically relies on MLE with assumed decision or preference models (e.g., BTL or softmax expert), which lacks robustness and yields non-convex reward sets with limited guarantees under non-uniform data covera

Approach

Build an empirical LP of the MDP dual with marginal importance sampling and a relaxed occupancy constraint, then estimate the feasible reward set from primal-dual optimality conditions as a polyhedron; RLHF comparisons enter as linear margin constraints, so IRL and RLHF data can be intersected in one convex set.

Key results

• In offline IRL experiments, LP-based algorithms generally outperform the bi-level MLE baseline in L1 occupancy error on a synthetic tabular MDP.
• In offline RLHF experiments under a greedy evaluator, LP error decreases rapidly with samples while the pessimistic BTL-MLE error decreases more slowly.
• Theory gives suboptimality of order tilde-O(sqrt(|S||A|/N)) for the expert over the confidence set under data coverage via the radius B=d_min^{-1}.

Measured effects reported in the paper

Surprising findings

• Continuous human feedback (LP-IRL-C) yields better performance than discrete feedback (LP-IRL-D) in the IRL experiments, attributed to stricter constraints.
• A bandit counterexample is given where BTL-based MLE and pessimistic MLE return a non-optimal policy under a greedy evaluator while LP recovers the optimal policy (with high probability).

Limitations

• Tabular setting; extension to non-convex function approximation and continuous state-action spaces is deferred to future work.
• Guarantee requires data coverage and depends on the radius B = d_min^{-1}, and the (1+B)gamma^H term needs long-horizon trajectories.
• Degeneracy avoidance relies on heuristic choices of relaxation parameters (epsilon_g, epsilon_r) and suboptimal trajectory samples.

Experimental setup

Datasets: synthetic tabular MDP trajectories synthetic pairwise trajectory comparisons

Benchmarks: synthetic tabular MDP (|S|=10, |A|=2, gamma=0.95)

Metrics: L1 error between optimal occupancy measures under true and e

Baselines: bi-level MLE offline IRL algorithm pessimistic MLE for offline RLHF (Zhu et al.) BTL-based MLE

Builds on: maximum margin planning marginal importance sampling LP for offline RL Bradley-Terry-Luce model pessimistic MLE for offline RLHF

Closest papers by meaning

• Offline Inverse RL: New Solution Concepts and Provably Efficient Algorithms (ICML 2024 · similarity 0.89)
• Reward Model Learning vs. Direct Policy Optimization: A Comparative Analysis of Learning from Human Preferences (ICML 2024 · similarity 0.89)
• Provable Offline Preference-Based Reinforcement Learning (ICLR 2024 · similarity 0.89)
• Zeroth-Order Policy Gradient for Reinforcement Learning from Human Feedback without Reward Inference (ICLR 2025 · similarity 0.89)
• Leveraging Sub-Optimal Data for Human-in-the-Loop Reinforcement Learning (ICLR 2025 · similarity 0.89)
• Is Inverse Reinforcement Learning Harder than Standard Reinforcement Learning? A Theoretical Perspective (ICML 2024 · similarity 0.88)