mlsanityData to 7 Oct 2026

Learning Kernel-Based MDPs from Episodic Preferential Feedback

arXiv 2605.23650 ↗First posted 22 May 2026stat.ML cs.LGcited by 0

On the map: LLM alignment / RLHF / preference optimisation → Reward modeling and RLHF

Abstract (arXiv)

Human feedback often arrives as preferences rather than calibrated numeric rewards, motivating reinforcement learning from preferential feedback, also referred to as reinforcement learning from human feedback (RLHF). We present a rigorous theoretical study of preference-only learning in episodic kernel MDPs. In each episode, the learner deploys two policies from a common start state and receives a single binary label indicating which trajectory is preferred, modeled by a Bradley--Terry--Luce link on the difference of cumulative (unobserved) rewards. Under kernel-based assumptions on the reward and transition functions (one of the most general models amenable to theoretical analysis) we develop preference-based value estimation and confidence sets tailored to end-of-episode comparisons. We prove high-probability regret bounds that scale sublinearly in the number of episodes, implying that the value of the learned policy converges to that of the optimal policy.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Placed in Reward modeling and RLHF, one of 10 directions in LLM alignment / RLHF / preference optimisation. Builds on 38 of its 54 references that are in the map. First posted on arXiv 22 May 2026.

Builds on

38 of 54 references.

Closest ancestors · 3

Same direction, newest first

  1. 2025Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds29 May
  2. 2023Making RL with Preference-based Feedback Efficient via Randomization23 Oct
  3. 2017Deep reinforcement learning from human preferences12 Jun

Other references · 35

  1. 2022Training language models to follow instructions with human feedbackcited by 15,712
  2. 2018Neural Tangent Kernel: Convergence and Generalization in Neural Networkscited by 2,597
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 514
  4. 2019Scalable Global Optimization via Local Bayesian Optimizationcited by 359
  5. 2017On Kernelized Multi-armed Banditscited by 348
  6. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  7. 2018Gaussian Processes and Kernel Methods: A Review on Connections and Equivalencescited by 188
  8. 2013Finite-Time Analysis of Kernelised Contextual Banditscited by 177
  9. 2020On Information Gain and Regret Bounds in Gaussian Process Banditscited by 156
  10. 2020Improved Optimistic Algorithms for Logistic Banditscited by 117
  11. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 105
  12. 2018Preference-based Online Learning with Dueling Bandits: A Surveycited by 100
23 more
  1. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 100
  2. 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 80
  3. 2020Optimistic Policy Optimization with Bandit Feedbackcited by 79
  4. 2014Reducing Dueling Bandits to Cardinal Banditscited by 62
  5. 2021Gaussian Process Bandit Optimization with Few Batchescited by 57
  6. 2020Instance-Wise Minimax-Optimal Algorithms for Logistic Banditscited by 56
  7. 2021Optimal Order Simple Regret for Gaussian Process Banditscited by 52
  8. 2020Bandit optimisation of functions in the Mat'ern kernel RKHScited by 40
  9. 2020Reinforcement Learning with Trajectory Feedbackcited by 40
  10. 2022Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Modelscited by 35
  11. 2020Adversarial Dueling Banditscited by 33
  12. 2019On Online Learning in Kernelized Markov Decision Processescited by 32
  13. 2023On the Sublinear Regret of GP-UCBcited by 25
  14. 2023Kernelized Reinforcement Learning with Order Optimal Regret Boundscited by 20
  15. 2023Borda Regret Minimization for Generalized Linear Dueling Banditscited by 17
  16. 2023Random Exploration in Bayesian Optimization: Order-Optimal Regret and Computational Efficiencycited by 16
  17. 2024Near-Optimal Regret in Linear MDPs with Aggregate Bandit Feedbackcited by 10
  18. 2023Sample Complexity of Kernel-Based Q-Learningcited by 8
  19. 2024No-Regret Reinforcement Learning in Smooth MDPscited by 6
  20. 2024Kernel-Based Function Approximation for Average Reward Reinforcement Learning: An Optimist No-Regret Algorithmcited by 6
  21. 2024Local Linearity: the Key for No-regret Reinforcement Learning in Continuous MDPscited by 4
  22. 2024Demystifying Linear MDPs and Novel Dynamics Aggregation Frameworkcited by 4
  23. 2025Generalized Kernelized Bandits: A Novel Self-Normalized Bernstein-Like Dimension-Free Inequality and Regret Boundscited by 4

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025Reinforcement Learning from Multi-level and Episodic Human Feedback
  2. 2026Regret Bounds for Reinforcement Learning from Multi-Source Imperfect Preferences
  3. 2025Policy-labeled Preference Learning: Is Preference Enough for RLHF?
  4. 2026Reinforcement Learning from Human Feedback: A Statistical Perspective
  5. 2023Contrastive Preference Learning: Learning from Human Feedback without RL
  6. 2024Reward Model Learning vs. Direct Policy Optimization: A Comparative Analysis of Learning from Human Preferences
  7. 2022Models of human preference for learning reward functions
  8. 2026A Regret Minimization Framework on Preference Learning in Large Language Models