Research map / Reinforcement learning / RL from feedback

Towards Theoretical Understanding of Sequential Decision Making with Preference Feedback

ICML 2025 · Reinforcement learning › RL from feedback · approach: Theory of RLHF

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.

Builds a theoretical framework for sequential decision making from partial-order preference feedback, linking preferences, multi-objective utilities, and Markovian rewards with complexity results and an approximation bound.

Problem

Sequential decision making in RL/RLHF is usually based on reward or utility signals, but human preferences can be incomparable and non-Markovian; there is limited theory linking preferences, utilities, and rewards.

Approach

Models preferences over trajectories as a partial preorder (allowing incomparabilities), represents them by compatible multi-dimensional utilities via order dimension, defines preference-based policy dominance over all compatible utilities, and approximates utilities by Markovian rewards via a QP with a bound on Pareto-frontier loss.

Key results

• Constructing a minimum-dimensional compatible utility is NP-hard (Theorem 4.2), with the minimum dimension equal to the order dimension of the preorder.
• Policy dominance for total orders can be verified in O(|T|) via cumulative-sum conditions (Theorem 5.1).
• The Markovian reward approximation error satisfies L(u, ũ) <= 2*sqrt(m*eta*) (Theorem 6.1).

Surprising findings

• Policy dominance for partial orders is not known to be efficiently checkable; the authors conjecture it is computationally hard.

Limitations

• Does not address statistical complexity or learning the preference relation from samples.
• Computing minimal utilities and checking partial-order dominance are NP-hard or conjectured hard.

Experimental setup

Builds on: Markov decision process without reward Pareto optimality order dimension theory RLHF MDP with preferences (MDPP)

Closest papers by meaning

• Efficient Preference-Based Reinforcement Learning: Randomized Exploration meets Experimental Design (NeurIPS 2025 · similarity 0.91)
• Reward Model Learning vs. Direct Policy Optimization: A Comparative Analysis of Learning from Human Preferences (ICML 2024 · similarity 0.91)
• Learning Optimal Advantage from Preferences and Mistaking It for Reward (AAAI 2024 · similarity 0.91)
• Policy-labeled Preference Learning: Is Preference Enough for RLHF? (ICML 2025 · similarity 0.91)
• A Minimaximalist Approach to Reinforcement Learning from Human Feedback (ICML 2024 · similarity 0.91)
• PILAF: Optimal Human Preference Sampling for Reward Modeling (ICML 2025 · similarity 0.90)