Reinforcement Learning from Adversarial Preferences in Tabular MDPs

Taira Tsuchiya, Shinji Ito, Haipeng LuoarXiv 2025 · OpenReview

Abstract

We introduce a new framework of episodic tabular Markov decision processes (MDPs) with adversarial preferences, which we refer to as preference-based MDPs (PbMDPs). Unlike standard episodic MDPs with adversarial losses, where the numerical value of the loss is directly observed, in PbMDPs the learner instead observes preferences between two candidate arms, which represent the choices being compared. In this work, we focus specifically on the setting where the reward functions are determined by Borda scores. We begin by establishing a regret lower bound for PbMDPs with Borda scores. As a preliminary step, we present a simple instance to prove a lower bound of $\Omega(\sqrt{HSAT})$ for episodic MDPs with adversarial losses, where $H$ is the number of steps per episode, $S$ is the number of states, $A$ is the number of actions, and $T$ is the number of episodes. Leveraging this construction, we then derive a regret lower bound of $\Omega( (H^2 S K)^{1/3} T^{2/3} )$ for PbMDPs with Borda scores, where $K$ is the number of arms. Next, we develop algorithms that achieve a regret bound of order $T^{2/3}$. We first propose a global optimization approach based on online linear optimization over the set of all occupancy measures, achieving a regret bound of $\tilde{O}((H^2 S^2 K)^{1/3} T^{2/3} )$ under known transitions. However, this approach suffers from suboptimal dependence on the potentially large number of states $S$ and computational inefficiency. To address this, we propose a policy optimization algorithm whose regret is roughly bounded by $\tilde{O}( (H^6 S K^5)^{1/3} T^{2/3} )$ under known transitions, and further extend the result to the unknown-transition setting.

Introduction

Standard Reinforcement Learning (RL) relies on scalar reward signals to guide agent behavior. However, in many real-world applications—such as training robotic assistants or fine-tuning large language models—assigning precise numerical scores to complex behaviors is difficult. Preference-based RL (PbRL) addresses this by learning from relative comparisons (e.g., "Option A is better than Option B"). While most PbRL research assumes stochastic preferences from a fixed distribution, this work investigates the adversarial setting, where preferences can be cyclic or change over time, requiring the agent to compete against a worst-case opponent.

Problem Formulation: PbMDPs and Borda Scores

We define Preference-based MDPs (PbMDPs) where the learner observes preferences between two candidate arms rather than direct losses. To handle potential cycles in adversarial preferences (e.g., A > B, B > C, but C > A), we utilize Borda scores. A Borda score ranks an action based on its probability of winning against a uniformly random opponent, providing a robust metric for optimization in non-transitive environments.

Theoretical Lower Bounds

A central contribution of this work is establishing the fundamental limits of learning in PbMDPs. We demonstrate that the adversarial preference setting is inherently more difficult than the standard adversarial loss setting. While standard RL typically achieves regret growing at $\sqrt{T}$, we prove a lower bound of $\Omega(T^{2/3})$ for PbMDPs with Borda scores.

Layered MDP construction used to establish regret lower bounds for both standard adversarial losses and preference-based settings.

To prove this, we construct a specific "layered" MDP instance (shown above). This construction first yields a simplified proof for the $\Omega(\sqrt{HSAT})$ lower bound in standard adversarial MDPs and is then extended to derive the $\Omega((H^2SK)^{1/3}T^{2/3})$ bound for the preference-based setting.

Algorithmic Approaches

We propose two primary algorithms to tackle the $T^{2/3}$ regret barrier:

  1. Global Optimization (Algorithm 1): This approach frames the problem as Online Linear Optimization (OLO) over the space of occupancy measures. By employing Follow-the-Regularized-Leader (FTRL) with Shannon entropy, the agent balances exploration and exploitation. To ensure global visibility of the environment and avoid "vanishing denominators" in value estimation, we incorporate a uniform state sampling strategy.
  2. Policy Optimization (Algorithm 2): To improve computational efficiency and state-space scaling, we develop a policy optimization variant. This algorithm updates policies locally at each state using a performance difference lemma, which is particularly advantageous for large state spaces.

Key Results

The theoretical performance of our proposed algorithms, alongside the established lower bounds, is summarized in the table below.

Summary of regret lower and upper bounds for adversarial losses and Borda-score preferences.

Our global optimization approach achieves the $T^{2/3}$ target but has a suboptimal $S^2$ dependence. The policy optimization approach improves the state dependence to $S^{1/3}$, matching the lower bound's scaling for states, though it incurs a higher dependence on the horizon $H$ and number of arms $K$. Notably, these results extend to settings where transition probabilities are initially unknown.

Conclusion and Future Work

This work provides the first comprehensive theoretical characterization of PbMDPs with adversarial preferences. While we achieve the optimal $T^{2/3}$ temporal scaling, gaps remain regarding the optimal dependence on the horizon $H$ and the number of arms $K$. Future research directions include exploring alternative optimality criteria, such as Condorcet winners, and extending these tabular results to function approximation for high-dimensional state spaces.

Summary updated

Abstract

We introduce a new framework of episodic tabular Markov decision processes (MDPs) with adversarial preferences, which we refer to as preference-based MDPs (PbMDPs). Unlike standard episodic MDPs with adversarial losses, where the numerical value of the loss is directly observed, in PbMDPs the learner instead observes preferences between two candidate arms, which represent the choices being compared. In this work, we focus specifically on the setting where the reward functions are determined by Borda scores. We begin by establishing a regret lower bound for PbMDPs with Borda scores. As a preliminary step, we present a simple instance to prove a lower bound of $\Omega(\sqrt{HSAT})$ for episodic MDPs with adversarial losses, where $H$ is the number of steps per episode, $S$ is the number of states, $A$ is the number of actions, and $T$ is the number of episodes. Leveraging this construction, we then derive a regret lower bound of $\Omega( (H^2 S K)^{1/3} T^{2/3} )$ for PbMDPs with Borda scores, where $K$ is the number of arms. Next, we develop algorithms that achieve a regret bound of order $T^{2/3}$. We first propose a global optimization approach based on online linear optimization over the set of all occupancy measures, achieving a regret bound of $\tilde{O}((H^2 S^2 K)^{1/3} T^{2/3} )$ under known transitions. However, this approach suffers from suboptimal dependence on the potentially large number of states $S$ and computational inefficiency. To address this, we propose a policy optimization algorithm whose regret is roughly bounded by $\tilde{O}( (H^6 S K^5)^{1/3} T^{2/3} )$ under known transitions, and further extend the result to the unknown-transition setting.
BibTeX
@misc{tsuchiya2025reinforcement,
  author = {Taira Tsuchiya and Shinji Ito and Haipeng Luo},
  title = {{Reinforcement Learning from Adversarial Preferences in Tabular MDPs}},
  year = {2025},
  eprint = {2507.11706},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2507.11706},
}
Figure