PaperlayerView exact revision on arXiv

Source-linked AI summary

Dueling RL: Reinforcement Learning with Trajectory Preferences

Aldo Pacchiano, Aadirupa Saha, Jonathan Lee

arXiv:2111.04850v3cs.LG

TL;DR

Reward engineering can be difficult, motivating learning from relative preferences over trajectories instead of absolute rewards. The paper models those preferences with non-Markovian trajectory scores and proposes algorithms for known and unknown transition models, analyzing regret for both cases.

  • Problem

    Reward-based RL depends on reward functions that can require substantial engineering, while the paper studies finding a best finite-horizon policy using only relative trajectory preferences.

    Source: §1 · p. 2

  • Method

    The paper models trajectory preferences with a non-Markovian linear reward model and proposes algorithms for known and unknown transition models.

    Source: §5 · p. 13

  • Results

    The paper analyzes regret guarantees for its proposed algorithms in both known- and unknown-transition settings.

    Source: §5 · p. 13

  • Takeaways & Limitations

    The work formulates finite-time regret analysis for preference-based learning with non-Markovian rewards.

    Source: §1 · p. 3

    The treatment leaves extensions to preference subsets, alternative feedback, infinite-horizon settings, and more complex state-action spaces for future work.

    Source: §5 · p. 13

Abstract

from arXiv · show

We consider the problem of preference based reinforcement learning (PbRL), where, unlike traditional reinforcement learning, an agent receives feedback only in terms of a 1 bit (0/1) preference over a trajectory pair instead of absolute rewards for them. The success of the traditional RL framework crucially relies on the underlying agent-reward model, which, however, depends on how accurately a system designer can express an appropriate reward function and often a non-trivial task. The main novelty of our framework is the ability to learn from preference-based trajectory feedback that eliminates the need to hand-craft numeric reward models. This paper sets up a formal framework for the PbRL problem with non-markovian rewards, where the trajectory preferences are encoded by a generalized linear model of dimension $d$. Assuming the transition model is known, we then propose an algorithm with almost optimal regret guarantee of $\tilde {\mathcal{O}}\left( SH d \log (T / \delta) \sqrt{T} \right)$. We further, extend the above algorithm to the case of unknown transition dynamics, and provide an algorithm with near optimal regret guarantee $\widetilde{\mathcal{O}}((\sqrt{d} + H^2 + |\mathcal{S}|)\sqrt{dT} +\sqrt{|\mathcal{S}||\mathcal{A}|TH} )$. To the best of our knowledge, our work is one of the first to give tight regret guarantees for preference based RL problems with trajectory preferences.

1 Introduction

The paper motivates preference-based reinforcement learning as an alternative to reward engineering and develops regret analysis for trajectory preferences under non-Markovian rewards. It proposes algorithms for known and unknown transition dynamics.

1 Introduction

  • Reward engineering can require substantial effort, and small reward changes may yield very different learned behaviors.The paper links these challenges to reward shaping, reward hacking, infinite rewards, and multi-objective outcomes.Source: §1 · p. 2
  • PbRL replaces absolute rewards with relative, non-numerical feedback, while this paper models preferences over trajectories through a non-Markovian linear reward model.The paper considers finding the best finite-horizon policy from relative preference feedback on H-length trajectories.Source: §1 · p. 2
  • The paper formulates finite-time regret analysis for preference-based learning with non-Markovian rewards, addressing a literature whose theoretical guarantees are described as sparse.Its trajectory features need not decompose into sums of state-action features, so optimal policies may depend on history.Source: §1 · pp. 2–3
  • For known transition dynamics, the paper proposes an algorithm with a regret guarantee; the supplied contribution passage does not give the full bound.The introduction also proposes an extension to unknown transition models, but its displayed bound is incomplete in the supplied passages.Source: §1 · p. 3
  • Earlier trajectory-preference work proposed Double Posterior Sampling with asymptotically sublinear regret, while another approach studied sample complexity for finding an ε-best policy.The latter approach relies on a dueling-bandit black box with restricted preference structures, and its optimal sample complexity was not established in the cited discussion.Source: §1 · pp. 3–4
  • The paper distinguishes its feedback from imitation learning: it queries an expert for preferences over sampled trajectories, not expert trajectories or optimal actions.Classical RL instead uses absolute reward feedback to optimize accumulated long-term reward.Source: §1 · pp. 1, 4

2 Problem Setup

The setup models finite-horizon reinforcement learning with known trajectory embeddings and pairwise preference feedback. Because trajectory scores may be non-Markovian, the policy class includes history-dependent policies.

2 Problem Setup

  • The setup uses a finite-state, finite-action, T-episode, H-horizon MDP with a known initial-state distribution and trajectories formed from visited states and actions.The learner's objective is measured against the score-maximizing policy.Source: §2 · pp. 4, 6
  • Each trajectory has a known d-dimensional embedding, and each policy is represented by its expected trajectory embedding.The embedding may be trajectory-dependent rather than a sum of state-action features.Source: §2 · pp. 4–5
  • Pairwise trajectory preferences follow a logistic model of the difference in their scores, with the score linear in trajectory features and an unknown parameter.The parameter and feature norms are assumed bounded.Source: §2 · p. 5
  • Since trajectory scores may be non-Markovian, the score-maximizing policy may depend on history, so the policy class includes all history-dependent policies.This is identified as a main source of technical complexity relative to standard Markovian RL.Source: §2 · p. 5
  • The paper relates preference-based regret to performance regret: the score-maximizing policy also maximizes the comparison objective, and the regrets are equivalent up to constants when B and W are at most 1.The supplied passages describe the comparison as an alternative regret notion and state the equivalence condition.Source: §2 · p. 6

3 Preference-Based Learning with Known Model

With a known transition model, LPbRL learns from trajectory preferences using a logistic parameter estimate and confidence-based policy selection. Its regret scales nearly optimally with the dimension and number of rounds, with additional factors for non-Markovian rewards.

3.1 Maximum Likelihood Estimation

  • The algorithm estimates the logistic preference parameter by regularized maximum likelihood, projects the estimate when needed to satisfy boundedness, and constructs a confidence set containing the true parameter with high probability.The projection is used because the maximum-likelihood estimate may not satisfy the boundedness assumption.Source: §3.1 · p. 7

3.2 Algorithm and Analysis

  • Each round forms candidate policies predicted to be sufficiently good, selects a pair to maximize uncertainty using expected features, then updates data matrices from the trajectories and preference feedback.The algorithm repeats this procedure over T rounds.Source: §3.2 · p. 8

Algorithm 1 LPbRL: Regret minimization (Known Model)

  • For Algorithm 1, the regret bound is conditioned on confidence events, and the known-model setting has no dependence on state- or action-space size.Horizon dependence is accounted for through the bound B on trajectory-feature norms; decomposable per-step features give the example bound B ≤ B′H.Source: §3.2 · p. 8, Algorithm 1 LPbRL: Regret minimization… · p. 9

3.2 Algorithm and Analysis

  • The known-model regret scales nearly optimally with d and T, with additional factors B and W due to non-Markovian rewards revealed indirectly through preferences.The near-optimality comparison is to existing linear-bandit lower bounds and reductions between standard and preference regret.Source: §3.2 · p. 8

3.3 Regret Analysis: Proof Sketch of Thm. 1

  • The regret analysis uses confidence sets to keep the optimal policy among candidates and relates parameter-estimation accuracy to expected policy features used in regret.The proof sketch bounds instantaneous regret using confidence-set size and uncertainty values.Source: §3.3 · p. 8, Algorithm 1 LPbRL: Regret minimization… · p. 9

4 Unknown model: Algorithm and Analysis

For unknown transition dynamics, LPbRL adapts its policy-confidence set to account for model uncertainty. Its regret retains a preference-estimation term and gains state- and action-space dependence in the tabular setting.

4 Unknown model: Algorithm and Analysis

  • The unknown-model algorithm modifies the candidate-policy set to account for model uncertainty while ensuring it contains the optimal policy.The empirical model is updated during the algorithm, and the policy set is constructed using tools for handling model uncertainty.Source: §4 · p. 10, Algorithm 2 LPbRL: Regret minimization… · p. 11

4.1 Analysis of instantaneous regret:

  • The instantaneous-regret analysis relates bonus expectations under the empirical model to bonus terms under the true model, then bounds the resulting vanishing Markovian errors.The argument also bounds the γT term using quantities that hide logarithmic factors in δ, |S|, and |A|.Source: §4.1 · pp. 10–11, Algorithm 2 LPbRL: Regret minimization… · p. 12

Algorithm 2 LPbRL: Regret minimization (Unknown Model)

  • With unknown transitions, the leading regret term scales as eO(d√T), with additional |S| and |A| dependence arising from the tabular problem.The theorem holds simultaneously for all T with probability at least 1−15δ, while eO hides logarithmic factors in δ, |S|, and |A|.Source: Algorithm 2 LPbRL: Regret minimization… · p. 13

5 Discussions and Future Scopes

The paper studies reinforcement learning from relative preferences between trajectories and analyzes regret guarantees for known and unknown transition models. It identifies extensions and tighter performance analysis as future directions.

5 Discussions and Future Scopes

  • The work models relative trajectory preferences with a non-Markovian linear reward model and analyzes regret guarantees for algorithms with known and unknown transition models.The supplied discussion identifies the two transition-model settings but does not provide the guarantee expressions in these passages.Source: §5 · p. 13
  • Future extensions include preferences over subsets, alternative feedback without an underlying reward model, and infinite-horizon settings with more complex state-action spaces.The discussion also names fundamental performance limits and tighter regret guarantees as open directions.Source: §5 · p. 13
  • The paper points to applications including robot training, stock markets, recommender systems, two-player games, and chatbot interactions.These examples are presented as areas where preference-based reinforcement learning is applicable.Source: §5 · p. 13

A.1 Proof of Claim 2

The proof segment considers ordered policies under the conditions S,B < 1 and expresses their score difference as x. It concludes by combining inequalities with the definition of the optimal policy.

A.1 Proof of Claim 2

  • Under S,B < 1, the proof considers policies π1 and π2 whose scores satisfy s(π1) ≥ s(π2).The stated condition is used in the argument for the claim.Source: §A.1 · p. 20
  • The proof sets x equal to the score gap s(π1)−s(π2) and states that x lies in (0,1).Source: §A.1 · p. 20
  • The claim follows by combining the inequalities and using π* := arg maxπ∈Π s(π).The supplied proof passage does not state the claim itself.Source: §A.1 · p. 20

B.1 Proof of Corollary 1

The Corollary 1 proof uses matrix concentration and a covering argument to obtain a uniform bound, then uses that corollary in the proof of Lemma 2.

B.1 Proof of Corollary 1

  • Lemma 7 applies matrix concentration to a fixed unit vector, then extends the result to all unit vectors using a covering argument and union bounds.The proof chooses a 1/T-cover and then takes a union bound over t.Source: §B.1 · pp. 21–22
  • With probability at least 1 − δ − δ log2 T, the stated bound holds for all t ∈ [T] under Assumption 1 and the specified events.The bound is given as d log(T(1 + 2T)/δ).Source: §B.1 · p. 22

B.2 Proof of Lemma 2

  • The proof of Lemma 2 uses optimality of π* and Corollary 1 to compare its feature-based score with those of arbitrary policies.The supplied proof passage states that (φ(π*) − φ(π))⊤w* ≥ 0 for arbitrary π.Source: §B.2 · p. 23

B.3 Proof of Theorem 1

The proof of Theorem 1 bounds instantaneous regret using optimism and Corollary 1, then applies a determinant-based bound to control the cumulative terms.

B.3 Proof of Theorem 1

  • A determinant bound and Lemma 8 control the cumulative feature terms in the regret argument.Lemma 8 concerns a sequence of bounded vectors and a regularized matrix V_t.Source: §B.3 · pp. 23–24
  • Theorem 1 bounds expected regret with probability at least 1 − δ, although the supplied passage does not expose the bound's expression.The proof obtains the result by bounding instantaneous regret.Source: §B.3 · p. 23
  • The instantaneous-regret decomposition uses the optimistic bonus for its first two terms and Corollary 1 to bound the last two.The proof then combines these bounds to upper-bound instantaneous regret.Source: §B.3 · p. 24

C Appendix for Section 4

The appendix combines error and bonus bounds to establish a formal regret result for LPbRL under a conjunction of events.

C Appendix for Section 4

  • The appendix bounds empirical error terms by rewriting their sums over states and actions and applying Lemma 10.The displayed bound itself is not legible in the supplied passage.Source: C Appendix for Section 4 · pp. 26–27
  • The lemma’s main takeaway is that the sum of squared errors grows only logarithmically in T, and the bound is applied to γT using ε = 1/96T.Source: C Appendix for Section 4 · p. 30
  • Theorem 3 gives the formal version of Theorem 2, bounding LPbRL regret when the listed events hold.The supplied passage does not expose the regret expression.Source: C Appendix for Section 4 · p. 31

C.1 Supporting Related Work Lemmas

  • Supporting lemmas include fixed-policy and uniform concentration results attributed to Chatterji et al. (2021), plus a Euclidean-ball covering bound.The appendix identifies the uniform result as the uniform version of Lemma 12.Source: §C.1 · p. 31

C.2 Proof of Lemma 3

The proof of Lemma 3 uses a covering argument to establish a uniform bound, while the proof of Lemma 4 aims to show that the optimal policy remains in Π_t.

C.2 Proof of Lemma 3

  • The proof of Lemma 3 extends a bound from a finite ε-cover of the 2S ball to every vector in that ball.It uses a closest cover vector within ε and a union bound to make the inequality simultaneous over t.Source: §C.2 · pp. 31, 33

C.3 Proof of Lemma 4

  • Lemma 4 states that π* belongs to Π_t for all t, and its proof conditions on Eδ, Ē0, and E2, whose intersection has probability at least 1 − 4δ.The proof combines this event with a further probability bound to conclude π* ∈ Π_t.Source: §C.3 · pp. 33–34
  • The Lemma 4 argument combines optimality of π* with concentration and the bounds from Lemma 3 and Corollary 1.These steps are used to establish membership of π* in Π_t.Source: §C.3 · pp. 33–34

C.4 Proof of Lemma 6

The proof bounds regret under a specified intersection of events by controlling instantaneous regret and combining lemma-based bounds with optimistic bonuses. The technical lemmas provide uniform concentration bounds for martingale and sub-ψP processes.

C.4 Proof of Lemma 6

  • Under the stated event intersection, Lemma 15 bounds regret, though the bound itself is not given in the passage.Source: §C.4 · p. 35
  • The proof uses optimistic bonuses for the first two terms and Lemma 3 and Corollary 1 to bound the last two terms.Source: §C.4 · pp. 35–36

D Miscelaneous Technical Lemmas

  • For bounded martingale differences, the technical lemmas invoke time-uniform Hoeffding-style concentration and state a uniform empirical Bernstein bound for sub-ψP processes.The latter holds with probability at least 1 − δ for all t; its statement also allows arbitrary fixed m > 0.Source: D Miscelaneous Technical Lemmas · pp. 36–37
Loading 2111.04850v3…