Reinforcement Learning with Pairwise Preferences in Long-Term Decision Problems

arXiv cs.LG Papers
reinforcement-learning pairwise-preferences markov-decision-process machine-learning long-term-decision theoretical-guarantees

Summary

This paper introduces the Markov decision contest, a new problem model for reinforcement learning with pairwise preferences. It proves optimality guarantees for stationary policies, exact solvability in P, and presents a learning-efficient approximate algorithm.

arXiv:2606.00367v1 Announce Type: new Abstract: Reinforcement learning problems typically define the goal as maximizing the expected value of a scalar reward function. But, pairwise preferences are often easier to specify than scalar rewards, and they express certain goals that scalar rewards cannot. Methods for reinforcement learning with pairwise preferences have thus received growing interest. Unfortunately, these methods are inefficient in problems with long time horizons, and they lack guarantees on the performance of Markov policies relative to history-dependent policies, which bridge the theory and practice of reinforcement learning. We therefore propose the \textit{Markov decision contest} as a new problem model for reinforcement learning with pairwise preferences. We prove that stationary Markov policies are optimal among all history-dependent policies, that solving a Markov decision contest exactly is in P, and that a simple iterative algorithm converges to an optimal policy at a sublinear rate. Lastly, in a set of high-dimensional decision problems with long time horizons, we show that our approximate algorithm is significantly more learning-efficient than prior work.
Original Article
View Cached Full Text

Cached at: 06/02/26, 03:42 PM 

# Reinforcement Learning with Pairwise Preferences in Long-Term Decision Problems
Source: [https://arxiv.org/abs/2606.00367](https://arxiv.org/abs/2606.00367)
[View PDF](https://arxiv.org/pdf/2606.00367)

> Abstract:Reinforcement learning problems typically define the goal as maximizing the expected value of a scalar reward function\. But, pairwise preferences are often easier to specify than scalar rewards, and they express certain goals that scalar rewards cannot\. Methods for reinforcement learning with pairwise preferences have thus received growing interest\. Unfortunately, these methods are inefficient in problems with long time horizons, and they lack guarantees on the performance of Markov policies relative to history\-dependent policies, which bridge the theory and practice of reinforcement learning\. We therefore propose the \\textit\{Markov decision contest\} as a new problem model for reinforcement learning with pairwise preferences\. We prove that stationary Markov policies are optimal among all history\-dependent policies, that solving a Markov decision contest exactly is in P, and that a simple iterative algorithm converges to an optimal policy at a sublinear rate\. Lastly, in a set of high\-dimensional decision problems with long time horizons, we show that our approximate algorithm is significantly more learning\-efficient than prior work\.

## Submission history

From: Jonathan Colaço Carr \[[view email](https://arxiv.org/show-email/56a9045a/2606.00367)\] **\[v1\]**Fri, 29 May 2026 21:16:25 UTC \(14,723 KB\)

Similar Articles

Progressive Point Matching (8 minute read)

TLDR AI

Progressive Point Matching (PPM) is a framework proposed to assign partial credit in reinforcement learning for long-horizon tasks in LLMs, addressing the inefficiency of sparse outcome rewards by treating reasoning as paths through a Markovian state space.