mlsanityData to 14 Oct 2026

DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedback

arXiv 2410.05527 ↗First posted 7 Oct 2024cs.LG math.OC stat.MLcited by 2

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

Abstract (arXiv)

Restless multi-armed bandits (RMAB) has been widely used to model constrained sequential decision making problems, where the state of each restless arm evolves according to a Markov chain and each state transition generates a scalar reward. However, the success of RMAB crucially relies on the availability and quality of reward signals. Unfortunately, specifying an exact reward function in practice can be challenging and even infeasible. In this paper, we introduce Pref-RMAB, a new RMAB model in the presence of textitpreference signals, where the decision maker only observes pairwise preference feedback rather than scalar reward from the activated arms at each decision epoch. Preference feedback, however, arguably contains less information than the scalar reward, which makes Pref-RMAB seemingly more difficult. To address this challenge, we present a direct online preference learning (DOPL) algorithm for Pref-RMAB to efficiently explore the unknown environments, adaptively collect preference data in an online manner, and directly leverage the preference feedback for decision-makings. We prove that DOPL yields a sublinear regret. To our best knowledge, this is the first algorithm to ensure tildeO(√Tln T) regret for RMAB with preference feedback. Experimental results further demonstrate the effectiveness of DOPL.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Placed in Reward modeling and RLHF, one of 10 directions in LLM alignment / RLHF / preference optimisation. Builds on 38 of its 66 references that are in the map. First posted on arXiv 7 Oct 2024.

Builds on

38 of 66 references.

Closest ancestors · 10

Same direction, newest first

  1. 2024Exploration-Driven Policy Optimization in RLHF: Theoretical Insights on Efficient Data Utilization15 Feb
  2. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint18 Dec
  3. 2023Open Problems and Fundamental Limitations of Reinforcement Learning from Human Feedback27 Jul
  4. 2023Is RLHF More Difficult than Standard RL?25 Jun
  5. 2023Direct Preference Optimization: Your Language Model is Secretly a Reward Model29 May
  6. 2023SLiC-HF: Sequence Likelihood Calibration with Human Feedback17 May
  7. 2023Principled Reinforcement Learning with Human Feedback from Pairwise or K-wise Comparisons26 Jan
  8. 2019Fine-Tuning Language Models from Human Preferences18 Sep
  9. 2018Reward learning from human preferences and demonstrations in Atari15 Nov
  10. 2017Deep reinforcement learning from human preferences12 Jun

Other references · 28

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2023A General Theoretical Paradigm to Understand Learning from Human Preferencescited by 912
  3. 2019Provably Efficient Reinforcement Learning with Linear Function Approximationcited by 520
  4. 2024Generalized Preference Optimization: A Unified Approach to Offline Alignmentcited by 157
  5. 2021Dueling RL: Reinforcement Learning with Trajectory Preferencescited by 106
  6. 2015Contextual Dueling Banditscited by 101
  7. 2022Human-in-the-loop: Provably Efficient Preference-based Reinforcement Learning with General Function Approximationcited by 81
  8. 2015Regret Lower Bound and Optimal Algorithm in Dueling Bandit Problemcited by 52
  9. 2020Collapsing Bandits and Their Application to Public Health Interventionscited by 47
  10. 2020Whittle index based Q-learning for restless bandits with average rewardcited by 45
  11. 2021Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizabilitycited by 44
  12. 2016Double Thompson Sampling for Dueling Banditscited by 42
16 more
  1. 2021Learn to Intervene: An Adaptive Learning Policy for Restless Bandits in Application to Preventive Healthcarecited by 35
  2. 2019Regret Bounds for Thompson Sampling in Episodic Restless Bandit Problemscited by 34
  3. 2020Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Banditscited by 27
  4. 2021NeurWIN: Neural Whittle Index Network For Restless Bandits Via Deep RLcited by 27
  5. 2022Optimistic Whittle Index Policy: Online Learning for Restless Banditscited by 20
  6. 2021Restless Bandits with Many Arms: Beating the Central Limit Theoremcited by 18
  7. 2016Deadline Scheduling as Restless Banditscited by 16
  8. 2023Finite-Time Analysis of Whittle Index based Q-Learning for Restless Multi-Armed Bandits with Neural Network Function Approximationcited by 14
  9. 2016Optimal Recommendation to Users that React: Online Learning for a Class of POMDPscited by 13
  10. 2021Planning to Fairly Allocate: Probabilistic Fairness in the Restless Bandit Settingcited by 12
  11. 2021LP-based policies for restless bandits: necessary and sufficient conditions for (exponentially fast) asymptotic optimalitycited by 10
  12. 2022On learning Whittle index policy for restless bandits with scalable regretcited by 10
  13. 2023Online Restless Multi-Armed Bandits with Long-Term Fairness Constraintscited by 10
  14. 2021Restless and Uncertain: Robust Policies for Restless Bandits via Deep Multi-Agent Reinforcement Learningcited by 7
  15. 2022Towards Soft Fairness in Restless Multi-Armed Banditscited by 5
  16. 2024GINO-Q: Learning an Asymptotically Optimal Index Policy for Restless Multi-armed Banditscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 0; 2026: 1.

2 papers.

  1. 2024Towards Foundation-model-based Multiagent System to Accelerate AI for Social Impactcited by 9
  2. 2026Online Convex Optimization with Dueling Feedbackcited by 2

Similar, not cited

Close in wording, no citation either way

  1. 2024Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedback
  2. 2026On the Complexity of Preference-Based Bandits
  3. 2025Non-Stationary Restless Multi-Armed Bandits with Provable Guarantee
  4. 2025MARBLE: Multi-Armed Restless Bandits in Latent Markovian Environment
  5. 2019Dueling Posterior Sampling for Preference-Based Reinforcement Learning
  6. 2024Online Bandit Learning with Offline Preference Data for Improved RLHF
  7. 2024Bandits with Preference Feedback: A Stackelberg Game Perspective
  8. 2025Multi-Objective Reward and Preference Optimization: Theory and Algorithms