Reinforcement Learning with Pairwise Preferences in Long-Term Decision Problems

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 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.

Teaching an AI to behave well is hard, partly because it is difficult to describe what "good behavior" looks like as a single score. It is often easier to simply compare two behaviors and say which one is better — just as a person might find it easier to pick their favorite dish from a menu than to rate every dish on a scale from one to ten. This kind of feedback is called a pairwise preference. Existing AI training methods that use pairwise preferences work well in short tasks, but struggle when the AI needs to make good decisions over a long period of time — for example, when assisting a user over an extended conversation. They also lack the theoretical foundations that make standard AI training methods trustworthy and practical. We introduce a new framework, the Markov decision contest, designed to address these gaps. We prove that simple, memory-efficient AI policies can perform just as well as more complex ones, that finding the best policy is computationally tractable, and that a practical training algorithm converges to a good policy efficiently. In experiments on a standard set of challenging control tasks with long time horizons, our algorithm learns significantly faster than the best existing method for training from pairwise preferences. These results suggest that training AI systems directly from human preferences — without converting those preferences into a score — is more feasible than previously thought, even for long-horizon tasks like conversational AI assistants.