Provable Benefits of Policy Learning from Human Preferences in Contextual Bandit Problems

1 Introduction

• Complex real-world tasks can lack a clear reward function, and handcrafted rewards may misalign with objectives or fail to produce the desired policy.The authors note that random exploration can be prohibitively expensive and that algorithms use rewards to guide exploration deliberately.Source: §1 · p. 1
• Preference methods have shown empirical effectiveness, but their theoretical properties and the reason for their practical advantage over ratings remain largely unexplored.The paper focuses on tabular contextual bandits in the offline setting.Source: §1 · p. 2
• The paper introduces a rating model with monotone expected bias and general uncertainty, then analyzes the standard LCB algorithm’s suboptimality.The model preserves reward ordering, keeping policy learning consistent; the analysis is described as the first known suboptimality analysis for human rating in bandit problems.Source: §1 · p. 2
• Preference feedback has lower suboptimality than rating under extreme rating bias, but no provable advantage when both feedback types have equally strong bias and uncertainty.The paper attributes preference methods’ potential advantage to milder bias and uncertainty in preference data.Source: §1 · p. 3

1.1 Related Works

• Prior preference-based reinforcement-learning results cited here focus on online settings, while offline policy-learning work studies pessimistic algorithms under assumptions about data coverage.The paper studies human feedback with pessimism in this offline-learning context.Source: §1.1 · p. 3

2.1 Contextual bandit

• A tabular contextual bandit has a state space, an action space, an unknown deterministic reward function, and an initial-state distribution.The reward is the immediate payoff for taking an action in a state.Source: §2.1 · p. 4
• A policy specifies action-selection probabilities for each state, and an optimal policy maximizes value for all states simultaneously.The paper also denotes the policy’s state-action visitation distribution from the initial distribution.Source: §2.1 · p. 4

2.2 Offline policy learning

• Offline policy learning uses i.i.d. samples from a sampling distribution to learn a policy that performs as well as possible against the optimal policy.Performance is measured by suboptimality, the difference between the optimal policy’s and learned policy’s values.Source: §2.2 · p. 4

Human Rating Models

• Existing rating models allow unknown bias and additive sub-Gaussian uncertainty, but bias can reverse expected reward ordering and make policy learning inconsistent.The paper also notes that simple additive noise does not capture uncertainty that interacts with reward and bias.Source: §3 · pp. 4–5
• The proposed rating model transforms true reward and independent Gaussian noise through a general deterministic function, with expected transformed reward denoted as biased reward.The expected bias function represents the reward in the annotator’s mind when producing ratings.Source: §3 · p. 5
• Strict monotonicity of expected biased reward preserves true-reward rankings in expectation, allowing the optimal policy to be identified from rating data.The paper notes that this monotonicity also makes samples correctly comparable and ranked in expectation, supporting comparison with preference models.Source: §3 · p. 5
• The model permits higher-order uncertainty whose effect can depend on reward and bias, while requiring the uncertainty not to favor a direction in expectation.The stated polynomial and symmetry conditions regulate uncertainty; the authors describe the resulting noise as more flexible than additive Gaussian noise.Source: §3 · pp. 5–6
• Regularity conditions constrain the expected bias function so it does not transform rewards too drastically, easing the theoretical analysis.The conditions bound differences between transformed rewards and their inverse-transformed counterparts.Source: §3 · p. 6
• The example model captures extreme personal opinions through a quadratic expected-bias function and lets rating fluctuations grow with true reward.Its uncertainty tail is dominated by a degree-two polynomial, and the example satisfies the model’s three conditions.Source: §3 · p. 6

4 Results for Human Rating

• The analysis evaluates standard LCB under a more practical rating model to isolate how human bias and uncertainty affect policy-learning suboptimality.Source: §4 · p. 6

4.1 Lower Bound under Partial Coverage

• With partial coverage (Assumption 1) and C⋆=2, LCB can suffer constant suboptimality even when ratings preserve expected reward ordering; variance-only knowledge is insufficient for convergence.The lower bound applies to the practical rating model with q ≥ 2.Source: §4.1 · pp. 7–8

4.2 Lower Bound under Full Coverage

• Under uniform coverage, LCB has a bias-dependent suboptimality lower bound regardless of its penalty, so full state-action coverage does not remove the bias bottleneck.For example model (4), annotator bias can make suboptimality decay more slowly.Source: §4.2 · pp. 8–9

4.3 Upper Bound with Knowledge of Noise Distribution

• The upper-bound comparison assumes full knowledge of the rating-noise distribution, equivalent to knowing its cumulative distribution function, an unrealistic condition for real human feedback.Even with that knowledge, bias still worsens LCB suboptimality; in example model (4), quadratic bias slows its decay.Source: §4.3 · p. 9

5 Comparison with Preference-based Methods

• Preference feedback contains less information than ratings and is incompatible with standard bandit algorithms, but it has drawn interest because people may find comparisons easier and more accurate.The section compares rating and preference approaches in light of those trade-offs.Source: §5 · p. 10

5.1 Human Preference under BTL

• Pairwise preference feedback is modeled as a binary response to comparing two state-action pairs, and pessimistic MLE selects a policy using a pessimistic version of its estimated reward.The coverage assumption requires the sampling distribution to cover state-action pairs reachable by an optimal policy.Source: §5.1 · p. 10
• Under the BTL model, pessimistic MLE learns the optimal policy under mild data coverage, with suboptimality decaying at O(1/√n).The authors contrast this result with negative results for human rating and attribute faster decay to BTL’s bias-free, mildly noisy modeling.Source: §5.1 · p. 11

5.2 Human Preference under Biased BTL

• The biased BTL analysis considers preferences generated from a biased reward and compares sample complexity with ratings when the bias closes the biased optimality gap.For rating noise variance proxy σ² ≤ 4, the authors report fewer samples for ratings than for preferences in the considered setting.Source: §5.2 · p. 12
• With equally strong bias and uncertainty in both feedback types, preference-based learning has no provable advantage over rating-based learning.The authors attribute preference methods’ empirical success largely to modeling preference feedback with milder bias and uncertainty.Source: §5.2 · p. 12

6 Conclusion

• The theory finds that human bias and uncertainty can adversely affect policy learning, with no provable preference-method advantage when both feedback types have equally strong bias and uncertainty.The authors suggest preference methods’ empirical success might reflect milder bias and uncertainty in preference data.Source: §6 · p. 12
• Comparing ratings and preferences for feedback generated by a mixture model representing a group of annotators remains an open direction.The authors identify this comparison as future work.Source: §6 · pp. 12–13

C.1 Proof of Theorem 1

• The proof constructs a single-state bandit with A = n² and considers the event that every suboptimal action is observed at most once.It then combines this event with an event concerning the optimal action’s sample count to bound algorithm failure.Source: §C.1 · pp. 19–20
• A probability lower bound for selecting a suboptimal action is used to obtain a lower bound on expected suboptimality.The proof states that a threshold for n depends on q, cb, cV, δ, σ, and R.Source: §C.1 · p. 22

C.2 Proof of Corollary 1

• The construction uses h(r, ε) = r² + r²ε|ε|, whose expected rating is r² and whose variance is 3r⁴σ⁴.The proof says the constructed reward function satisfies the conditions used for Theorem 1.Source: §C.2 · p. 23
• The proof reuses the state and action space from Theorem 1 and says the remaining argument is similar to that theorem’s proof.Source: §C.2 · p. 23
• Algorithm 1 suffers suboptimality of 1/4 with constant probability in this construction.The probability depends on q, cb, δ, and σ.Source: §C.2 · p. 23

• The proof uses a one-state, two-action bandit instance and sets a1 as the optimal action.Source: §D.1 · p. 23
• The sampling distribution is uniform, and the construction can make the optimal action the one with more offline samples, with sample counts within a factor of three.Source: §D.1 · p. 23
• For n ≥ max{c(R, σ, q), 120}, Algorithm 1 incurs expected suboptimality at least c_0 \bar{h}^{-1}(n).Source: §D.1 · p. 24

• The specialized rating function is h(r, ε) = r^2 + r^2ε|ε|, whose mean rating is r^2.Source: §D.2 · p. 24
• Under this model, the rating variance is 3r^4σ^4.Source: §D.2 · p. 24
• For n ≥ max{48σ^4, 60}, Algorithm 1 suffers suboptimality σ^(1/4) with constant probability depending on q.Source: §D.2 · p. 24

E.1 Proof of Theorem 3

• Theorem 3’s proof decomposes suboptimality and uses the pessimistic penalty to bound the selected action’s estimated reward by its mean rating with high probability.Source: §E.1 · p. 25
• A uniform concentration event for rating observations, combined with sample-count control, supplies the estimation bounds used in Theorem 3.Source: §E.1 · pp. 25–26

E.2 Proof of Corollary 3

• The proof decomposes Algorithm 1’s output suboptimality into three terms involving r2 and br; with probability 1 − δ/2, the pessimistic penalty bn ensures br(s, bπ(s)) ≤ r2(s, bπ(s)).Source: §E.2 · pp. 26–27
• For Corollary 3, concentration of ε|ε| and sample-count control support simultaneous bounds across state-action pairs.Source: §E.2 · p. 27

F Proof of Theorem 4

• Theorem 4’s analysis largely follows prior work but handles distributional mismatch more carefully and characterizes it for the tabular setting.Source: F Proof of Theorem 4 · p. 28
• The proof decomposes suboptimality and uses pessimistic reward selection and policy maximization to control its terms.Source: F Proof of Theorem 4 · p. 28

F.1 Proof of Lemma 7

• Lemma 7 bounds the difference between the ground-truth and empirical reward estimates with respect to the population covariance matrix.Source: F Proof of Theorem 4 · p. 29
• The lemma’s proof invokes a bound involving the empirical covariance matrix, with the population covariance defined as its expectation.Source: §F.1 · p. 29

G Proof of Theorem 5

• For the preference-based method, the MLE is equivalent to maximizing the scalar reward difference r(a2) − r(a1) and fitting a Bernoulli MLE parameter.Correctly identifying a2 requires the estimated parameter to exceed 1/2; a sample threshold is derived so the failure probability is at most δ.Source: G Proof of Theorem 5 · p. 30
• The preference-based sample threshold ensures correct identification of the optimal arm with probability at least 1 − δ once the sample count exceeds it.The proof denotes the minimum preference-based sample count by n_pref.Source: G Proof of Theorem 5 · p. 30
• With uniform data coverage, pessimism does not affect the rating-based algorithm, whose minimum sample count is defined for equal samples per action.The proof bounds the failure probability using Hoeffding’s inequality.Source: G Proof of Theorem 5 · p. 31
• As the biased reward gap approaches 0, n_pref approaches 0.25σ^2.The proof identifies this as the advertised result for the preference-based approach.Source: G Proof of Theorem 5 · p. 31