Pairwise Preference Reinforcement Learning in Long-Horizon Decisions: The Mechanisms and Boundaries of Markov Decision Contest

by
Table of contents

🌏 閱讀中文版本

Reinforcement learning (RL) faces a structural tension in long-horizon decision tasks: as time horizons grow and state spaces expand, traditional scalar reward functions often struggle to capture complex values precisely. Methods based on pairwise preferences are easier to specify, but leave gaps in theoretical guarantees and computational efficiency. The research team’s Markov Decision Contest model aims to close that gap. It proves that, under specific preference criteria, a stationary randomized Markov policy is globally optimal, and that the solution problem belongs to P. This guarantee applies only to the average preference-margin criterion and finite unichain setting proved in the paper: exact solutions and HPI have corresponding theoretical guarantees, while HPI-Clip is an approximate method for high-dimensional tasks. Its current support comes from empirical comparisons and cannot directly inherit those guarantees.

The Boundaries of Scalar Rewards and Pairwise Preferences

In the traditional RL paradigm, an agent’s objective is defined as maximizing the sum of expected scalar rewards. This works well in environments with quantifiable goals, but becomes less natural when handling human values or complex multi-objective decisions. Assigning a concrete numerical reward is straightforward. Precisely quantifying which behavioral trajectory better aligns with human preferences is much more challenging. By comparison, asking a person to compare two outcomes and identify the better one is usually easier to specify in practice.

However, existing pairwise-preference RL methods encounter a bottleneck in long-horizon decisions. They typically lack performance guarantees for Markov policies relative to history-dependent policies. While history-dependent policies can theoretically provide more complete decision information, they are often computationally impractical. This gap between theory and practice leads to lower training efficiency and less clearly defined theoretical boundaries.

Core Mechanism: The Causal Chain of Markov Decision Contest

To address this gap, the research team introduced a new problem model: Markov Decision Contest. One way to understand why it works is to view it as a strategic contest.

In traditional RL, an agent attempts to maximize a fixed reward function r. In Markov Decision Contest, preference relations are modeled as a variant of a zero-sum game. Specifically, the researchers define a preference margin, M((s,a),(s′,a′)), which measures the advantage of taking action a in state s over another policy taking action a′ in state s′.

Markov Decision Contest turns preference learning into a problem of maximizing the average preference margin. This enables a decision problem that would otherwise depend on complex historical memory to find an optimal solution within the space of Markov policies. Its core insight is that maximizing the average preference margin transforms the task into an optimization problem solvable in the Markov-policy space. The research proves that, under this setting, there exists a stationary randomized Markov policy π that is optimal among all history-dependent policies. This provides a more computationally efficient framework for complex preference settings without requiring the model to maintain complex historical memory.

Mathematically, the optimal stationary randomized Markov policy is equivalent to solving the following maximin problem:

maxπ ∈ ΠSRminπ′ ∈ ΠSR∑s, a∑s′, a′xπ(s,a)xπ′(s′,a′)M((s,a),(s′,a′))

Here, ΠSR represents the space of stationary randomized Markov policies. The equation shows that the research is not seeking an absolute reward function. It is seeking the policy that performs most robustly when compared with every possible opponent.

Computational Feasibility and HPI in Practice

The study’s key contribution is not only conceptual innovation, but also rigorous theoretical guarantees and improved empirical efficiency.

Theoretical Breakthrough: Computational Feasibility

First, at the theoretical level, the research proves that solving a finite unichain Markov Decision Contest belongs to P. This means the problem has efficient computational feasibility: a linear program can solve it exactly using |S||A| + |S| + 1 variables and 2|S||A| + |S| + 1 constraints. The work establishes a clear computational boundary by placing the complexity of pairwise-preference RL on par with traditional Markov Decision Processes (MDPs).

Algorithm in Practice: From HPI Theory to HPI-Clip

Second, in algorithm design, the research distinguishes between theoretical guarantees and practical approximation. On the theoretical side, it introduces HPI (Hedge Policy Iteration), an iterative algorithm based on the Hedge Algorithm. The analysis shows that HPI’s optimization gap is no greater than $4M_{max} \tau \sqrt{\log(|A|)/K}$ and converges at a sublinear rate of $1/\sqrt{K}$.

However, strictly executing HPI is not practical in high-dimensional continuous state spaces. The team therefore introduced HPI-Clip as an approximate algorithm for practical use. Empirically, the team tested it on several high-dimensional, long-horizon decision tasks and compared it with SPPO (Swamy et al., 2024). The results show that HPI-Clip is significantly more sample-efficient than SPPO:

  • Performance improvement: Across Ant-v5, Half Cheetah-v5, Hopper-v5, Humanoid Standup-v5, Pusher-v5, Reacher-v5, and Swimmer-v5, HPI-Clip’s AUC confidence intervals were strictly higher than SPPO’s.
  • Core difference: SPPO averages accumulated preferences over every timestep in an entire trajectory. HPI-Clip preserves local signals by not applying that averaging, making it more sensitive to local preferences.

In addition, on the Walker2d-NT task, the research demonstrates a boundary-case implementation based on non-transitive preferences, where three competing objectives follow the cycle “height > speed > stability > height.” This further validates the model’s ability to handle complex preference structures.

Trade-offs and Practical Implications: From PPO to HPI-Clip

Viewing HPI-Clip as a generalization of PPO is an especially useful perspective. PPO learns from a reward function r, while HPI-Clip learns from a preference margin M. When the preference margin M equals the win probability PBT based on the Bradley–Terry model, the two methods do not have the same optimal policy. This reveals an inherent difference between pairwise-preference learning and traditional reward maximization: the former focuses on relative advantage, while the latter focuses on absolute value.

In practical applications, this shift brings clear trade-offs:

  1. Labeling cost vs. training efficiency: Collecting pairwise preference data is often easier than designing a precise reward function, especially when the objective involves subjective values. HPI-Clip makes it possible to use this more accessible data for efficient long-horizon optimization.
  2. Theoretical guarantees vs. practical scalability: The theoretical HPI algorithm provides a sublinear convergence rate and a clear optimization-gap bound, but exact solutions become computationally expensive in extremely high-dimensional state spaces. HPI-Clip relaxes these strict theoretical guarantees in exchange for execution efficiency on high-dimensional tasks through approximation. Researchers need to weigh exact solutions with theoretical guarantees against approximate algorithms with scalability.

For teams using RLHF, this research offers a direction worth considering: when traditional PPO becomes unstable in long-horizon tasks or rewards become difficult to define, moving to a preference-margin optimization framework may be a more robust option. However, the current evidence comes primarily from high-dimensional control tasks. It has not yet covered large language model fine-tuning or real-world RLHF workflows, so this remains a hypothesis that needs validation.

Conclusion and Future Validation Points

Under the average preference-margin criterion and a finite unichain setting, Markov Decision Contest proves that stationary randomized Markov policies can be optimal among all history-dependent policies, and that exact solutions belong to P. HPI has a clear sublinear convergence guarantee. HPI-Clip is an approximate algorithm for high-dimensional problems, supported by comparisons with SPPO across a set of long-horizon control tasks; it cannot directly inherit HPI’s theoretical guarantees. These results define the range the framework currently supports, but transfer beyond control tasks has not yet been validated.

The framework also has clear boundaries. Its current theoretical guarantees focus primarily on finite unichain Markov Decision Contests. Generalization to more complex state-transition structures or partially observable environments (POMDPs) requires further research. Algorithm performance also depends heavily on the quality of preference data. If human preferences contain internal inconsistencies or excessive noise, convergence may be affected.

Future directions worth watching include evaluating HPI-Clip’s long-term stability relative to SPPO in larger-scale LLM fine-tuning; exploring the algorithm’s robustness and convergence behavior in settings with more complex non-transitive preferences; and studying how linear-programming solvers can work more effectively with deep neural networks to address exact solutions in continuous state spaces.

This work does not aim to replace traditional reward-maximization methods. It adds an alternative path to the RL toolbox, one with rigorous theoretical foundations in specific settings. When the boundaries of a reward function become unclear, preference margins provide a computable path.

Sources