mlsanityData to 7 Oct 2026

Reinforcement Learning with Pairwise Preferences in Long-Term Decision Problems

arXiv 2606.00367 ↗First posted 29 May 2026cs.LG cs.AIcited by 0

Not on the map. Why?

Abstract (arXiv)

Reinforcement learning with scalar rewards is widely used for aligning machine-learning systems with user preferences. But, pairwise preferences are often more natural for users 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 address these limitations in a new problem setting for reinforcement learning with pairwise preferences called the textitMarkov decision contest. In this setting, we prove that stationary Markov policies perform just as well as history-dependent policies; that the problem of recovering an optimal policy exactly is in P; and that a simple iterative algorithm converges to an optimal policy at a sublinear rate. Lastly, we implement a deep-learning variant of our iterative algorithm and demonstrate its efficiency in long-term decision problems that require function approximation.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 17 of its 39 references that are in the map. First posted on arXiv 29 May 2026.

Builds on

17 of 39 references.

References · 17

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Modelcited by 7,916
  3. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,635
  4. 2017Deep reinforcement learning from human preferencescited by 3,846
  5. 2020Learning to summarize from human feedbackcited by 2,562
  6. 2023A General Theoretical Paradigm to Understand Learning from Human Preferencescited by 906
  7. 2023Open Problems and Fundamental Limitations of Reinforcement Learning from Human Feedbackcited by 743
  8. 2023Nash Learning from Human Feedbackcited by 220
  9. 2024Direct Nash Optimization: Teaching Language Models to Self-Improve with General Preferencescited by 176
  10. 2024A Minimaximalist Approach to Reinforcement Learning from Human Feedbackcited by 141
  11. 2023Is RLHF More Difficult than Standard RL?cited by 96
  12. 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 80
5 more
  1. 2015Simple, Robust and Optimal Ranking from Pairwise Comparisonscited by 68
  2. 2024Multi-turn Reinforcement Learning from Preference Human Feedbackcited by 65
  3. 2024Iterative Nash Policy Optimization: Aligning LLMs with General Preferences via No-Regret Learningcited by 45
  4. 2013On the Complexity of Solving Markov Decision Problemscited by 31
  5. 2024Magnetic Preference Optimization: Achieving Last-iterate Convergence for Language Model Alignmentcited by 20

Built on by

Not cited yet.