# Sign-SZPO: Provable Preference-based Reinforcement Learning with an Unknown Link Function

arXiv: https://arxiv.org/abs/2506.03066 · HTML: https://mlsanity.com/paper/2506.03066/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods.
- Builds on 60 of its 89 references that are in the map.
- First posted on arXiv 3 Jun 2025.

## Placed in

- Deep reinforcement learning methods / [RL theory and sample complexity](https://mlsanity.com/deeprl/rl-theory-and-sample-complexity/)

## Builds on (most cited first, 30 of 60)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Deep reinforcement learning from human preferences](https://mlsanity.com/paper/1706.03741/) (2017)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Scaling Language Models: Methods, Analysis & Insights from Training Gopher](https://mlsanity.com/paper/2112.11446/) (2021)
- [Scaling Laws for Reward Model Overoptimization](https://mlsanity.com/paper/2210.10760/) (2022)
- [A General Theoretical Paradigm to Understand Learning from Human Preferences](https://mlsanity.com/paper/2310.12036/) (2023)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Open Problems and Fundamental Limitations of Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2307.15217/) (2023)
- [Stochastic First- and Zeroth-order Methods for Nonconvex Stochastic Programming](https://mlsanity.com/paper/1309.5549/) (2013)
- [Deep Reinforcement Learning for Autonomous Driving: A Survey](https://mlsanity.com/paper/2002.00444/) (2020)
- [Evolution Strategies as a Scalable Alternative to Reinforcement Learning](https://mlsanity.com/paper/1703.03864/) (2017)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Lojasiewicz Condition](https://mlsanity.com/paper/1608.04636/) (2016)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [SLiC-HF: Sequence Likelihood Calibration with Human Feedback](https://mlsanity.com/paper/2305.10425/) (2023)
- [Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint](https://mlsanity.com/paper/2312.11456/) (2023)
- [Fine-Tuning Language Models with Just Forward Passes](https://mlsanity.com/paper/2305.17333/) (2023)
- [RLHF Workflow: From Reward Modeling to Online RLHF](https://mlsanity.com/paper/2405.07863/) (2024)
- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [A Survey of Reinforcement Learning from Human Feedback](https://mlsanity.com/paper/2312.14925/) (2023)
- [Reward Design with Language Models](https://mlsanity.com/paper/2303.00001/) (2023)
- [Direct Language Model Alignment from Online AI Feedback](https://mlsanity.com/paper/2402.04792/) (2024)
- [Inverse Reward Design](https://mlsanity.com/paper/1711.02827/) (2017)
- [Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons](https://mlsanity.com/paper/2301.11270/) (2023)
- [From r to Q^*: Your Language Model is Secretly a Q-Function](https://mlsanity.com/paper/2404.12358/) (2024)
- [Nash Learning from Human Feedback](https://mlsanity.com/paper/2312.00886/) (2023)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [Direct Nash Optimization: Teaching Language Models to Self-Improve with General Preferences](https://mlsanity.com/paper/2404.03715/) (2024)

## Built on by (most cited first, 4 of 4)

- [Semiparametric Preference Optimization: Your Language Model is Secretly a Single-Index Model](https://mlsanity.com/paper/2512.21917/) (2025)
- [Objective Decoupling in Social Reinforcement Learning: Recovering Ground Truth from Sycophantic Majorities](https://mlsanity.com/paper/2602.08092/) (2026)
- [Offline Constrained RLHF with Multiple Preference Oracles](https://mlsanity.com/paper/2604.00200/) (2026)
- [Efficient Federated RLHF via Zeroth-Order Policy Optimization](https://mlsanity.com/paper/2604.17747/) (2026)

## Abstract (arXiv)

The link function, which characterizes the relationship between the preference for two trajectories and their returns, is a crucial component in designing RL algorithms that learn from preference feedback. Most existing methods, both theoretical and empirical, assume that the link function is known (often a logistic function based on the Bradley-Terry model), which is arguably restrictive given the complex nature of preferences, especially those of humans. To avoid mis-specification, this paper studies preference-based RL with an unknown link function and proposes a novel zeroth-order policy optimization algorithm called Sign-SZPO. Unlike typical zeroth-order methods, which rely on the known link function to estimate the value function differences and form a gradient estimator, Sign-SZPO only estimates the sign of the value function difference. It then constructs a parameter update direction that is positively correlated with the true policy gradient, eliminating the need to know the link function exactly. Under mild conditions, Sign-SZPO provably converges to a stationary policy with a polynomial rate in the number of policy iterations and trajectories per iteration. Empirical evaluations further demonstrate the robustness of Sign-SZPO under link function mis-specifications.