🤖 machine learning

Reinforcement Learning with Pairwise Preferences in Long-Term Decision Problems

This paper introduces the Markov decision contest as a new framework for reinforcement learning with pairwise preferences, proving that stationary Markov policies are optimal and demonstrating that a simple iterative algorithm achieves superior learning efficiency in long-horizon, high-dimensional problems compared to prior methods.

Original authors: Jonathan Colaço Carr, Prakash Panangaden, Doina Precup, Benjamin Van Roy

Published 2026-06-02

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jonathan Colaço Carr, Prakash Panangaden, Doina Precup, Benjamin Van Roy

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot how to walk, or how to play a video game. In the old way of doing this (called Reinforcement Learning), you act like a strict teacher with a scorecard. You tell the robot, "If you take this step, you get +10 points. If you fall, you get -5 points." The robot's only goal is to maximize those points.

But sometimes, giving a robot a specific score is hard. It's easier to just say, "I prefer this way of walking over that way." Maybe you don't know exactly why one is better, you just know you like it more. This is called pairwise preference.

The problem is, the old methods for teaching robots using these "I prefer this over that" comparisons only work well for short games. If the game goes on for a long time (like a robot learning to walk for hours), the old methods get confused, slow, and inefficient. They also can't guarantee that a simple, "in-the-moment" decision rule is as good as a complex rule that remembers every single thing that happened in the past.

This paper introduces a new way to solve this, called a Markov Decision Contest. Here is how it works, using some simple analogies:

1. The New Game: A "Contest" Instead of a Scorecard

Instead of giving the robot a scorecard, imagine the robot is playing a game against a mirror image of itself.

The Setup: The robot plays a round. Then, a "clone" of the robot plays a round using a different strategy.
The Judge: A judge looks at both rounds and says, "I prefer the first one," or "I prefer the second one," or "They are equal."
The Goal: The robot wants to find a strategy that is so good that, no matter what strategy its clone uses, the judge will never consistently prefer the clone's strategy over the robot's.

This is what the authors call a Markov Decision Contest. It turns the problem of "learning from preferences" into a fair game between two players.

2. The Big Surprise: Simplicity Wins

In many complex games, you might think you need to remember every single move you've ever made (a "history-dependent" strategy) to win. But the authors proved something surprising: You don't need a memory.

They proved that a "stationary" strategy—one that just looks at the current situation and decides what to do right now without worrying about the past—is actually just as good as any complex strategy that remembers the whole history.

Analogy: Imagine playing chess. You might think you need to remember the last 50 moves to make the best move. The authors proved that for this specific type of game, you only need to look at the board right now to make the perfect move. This makes the problem much easier to solve.

3. Solving the Puzzle Efficiently

The authors showed that solving this "Contest" is mathematically manageable.

Exact Solution: If the problem isn't too huge, you can solve it perfectly using standard math tools, and it won't take forever. It's in the same "difficulty class" as standard math problems we already know how to solve.
Approximate Solution (The "HPI" Algorithm): For huge, complex problems (like high-dimensional robot control), they created a simple, iterative algorithm called Hedged Policy Iteration (HPI).
- How it works: The robot tries a strategy, sees how it compares to a clone, and tweaks its strategy slightly to do better next time. It does this over and over.
- The Result: The robot gets better and better, converging on the best possible strategy at a predictable speed.

4. Did it Work? (The Experiments)

The authors tested their new method against the best existing methods for learning from preferences. They used a set of difficult, long-term robot control tasks (simulated environments where robots have to walk, reach, or run for thousands of steps).

The Result: Their new method (HPI) learned much faster and more efficiently than the old methods.
The "Non-Transitive" Twist: They even tested scenarios where preferences are weird. For example: "I prefer A over B, B over C, but C over A" (like Rock-Paper-Scissors). Old methods struggle with this, but the new "Contest" model handles it naturally.

Summary

The paper says: "Stop trying to force robots to maximize a complex scorecard when you just have preferences. Instead, let them play a 'Contest' against themselves. We proved that simple, 'in-the-moment' decisions are enough to win this contest, and we built a fast, reliable algorithm to teach them how to do it, even for very long and complex tasks."

This is particularly useful for things like training Large Language Models (like the one you are talking to now), where the "game" (a conversation or a task) can go on for a long time, and it's often easier to say "I like this answer better" than to assign a specific number to it.

Technical Summary: Reinforcement Learning with Pairwise Preferences in Long-Term Decision Problems

Problem Definition
Traditional reinforcement learning (RL) formulates goals as maximizing the expected value of a scalar reward function within a Markov Decision Process (MDP). However, in many applications, such as fine-tuning large language models (LLMs), specifying pairwise preferences (e.g., "trajectory A is better than trajectory B") is often more natural and feasible than defining a scalar reward. Existing methods for RL with pairwise preferences typically infer a reward function or optimize directly for preferences but suffer from two critical limitations:

They rely on finite, fixed time horizons, which is impractical for long-term decision problems where agents do not terminate at a fixed step.
They lack theoretical guarantees that stationary Markov policies are optimal relative to history-dependent policies, a cornerstone of standard MDP theory.

Furthermore, standard approaches often fail to capture non-transitive preferences (e.g., Condorcet's paradox), where the aggregate preference of a group or a multi-feature evaluation does not form a transitive ordering.

Methodology: Markov Decision Contests (MDCs)
The authors propose a new problem model called the Markov Decision Contest (MDC) to address these gaps. An MDC is defined by a finite environment $(S, A, P, \mu)$ and a Markov preference margin $M: (S \times A) \times (S \times A) \to \mathbb{R}$ . The objective is to find a policy $\pi$ that maximizes the average preference margin against any other policy $\pi'$ , formulated as a zero-sum game:
$\max_{\pi} \min_{\pi'} \sum_{s,a} \sum_{s',a'} x_\pi(s,a) x_{\pi'}(s',a') M((s,a), (s',a'))$
where $x_\pi$ represents the limiting average state-action frequency (occupancy measure).

To ensure theoretical tractability in infinite-horizon settings, the authors assume the transition probability function is unichain and aperiodic. Under these conditions, they establish that the set of occupancy measures for history-dependent policies is equivalent to the convex hull of occupancy measures for stationary deterministic policies.

Key Contributions

Optimality of Stationary Policies: The paper proves that within finite unichain MDCs, a stationary randomized policy is optimal among all history-dependent policies. This justifies restricting the search space to Markov policies, bridging a gap between theory and practice for preference-based RL.
Computational Complexity: The authors demonstrate that solving an MDC exactly is in P (polynomial time). Specifically, they construct a linear program with $|S||A| + |S| + 1$ variables and $2|S||A| + |S| + 1$ constraints. This complexity is comparable to standard average-reward MDPs, despite MDCs being a strict generalization that supports non-transitive preferences.
Hedged Policy Iteration (HPI): An approximate iterative algorithm, Hedged Policy Iteration (HPI), is introduced. It utilizes the Hedge algorithm to update decision rules based on "marginal values" (cumulative preference margins).
- Convergence: HPI converges to an optimal policy at a sublinear rate of $O(1/\sqrt{K})$ , where $K$ is the number of iterations.
- Scalability: The authors derive a policy-gradient form of HPI and a deep learning implementation (Algorithm 3) that utilizes buffers and value function approximations, making it suitable for high-dimensional environments.

Experimental Results
The authors evaluated HPI and a clipped variant (HPI-Clip) against Self-Play Preference Optimization (SPPO) (Swamy et al., 2024) across 13 high-dimensional tasks with long time horizons (2048 steps) using the Mujoco-v5 suite.

Setup: Tasks included standard continuous control problems (where preferences were derived from reward differences) and "Mujoco-NT" tasks featuring explicitly non-transitive preference margins (e.g., best-two-out-of-three rules).
Performance: In 12 out of 13 tasks, HPI and HPI-Clip demonstrated significantly higher learning efficiency (measured by the Area Under the Curve of the episodic return or inverted optimality gap) compared to SPPO.
Ablation: The results held even when preference models were learned from offline data.

Significance and Claims
The paper claims that reinforcement learning with pairwise preferences in long-term decision problems is more tractable than previously thought. By introducing the MDC model, the authors provide a framework where:

Stationary policies are theoretically sufficient, removing the need for complex history-dependent strategies.
The problem remains computationally efficient (in P), even with non-transitive preferences.
Practical algorithms (HPI) scale to high-dimensional, long-horizon problems, outperforming existing state-of-the-art methods.

The authors note that while these results are promising for applications like LLMs in long-horizon tasks, further investigation is required to determine when preference-margin learning outweighs reward-based learning and how effectively these methods align language models in practice. The work aims to bring the theory and practice of pairwise preference RL closer together.