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

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.