Research map / Bandits and online learning / Multi-armed bandits
DOPL: Direct Online Preference Learning for Restless Bandits with Preference Feedback
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces Pref-RMAB, a restless bandit setting where only pairwise preference feedback (Bradley-Terry) is observed, and DOPL, an episodic UCRL-style algorithm with preference inference and a direct LP-based index policy achieving Õ(√(T ln T)) regret.
Problem
Restless multi-armed bandits where scalar rewards are unobservable and only pairwise preference feedback between activated arms is available, under unknown transitions and unknown preference model in an online setting.
Approach
Represent scalar rewards via preference-reference terms under a Bradley-Terry model, infer unobserved pairwise preferences from others (reducing comparisons from O(B^2) to B-1 per epoch), add an optimistic preference bonus, and build a direct index policy from an LP over occupancy measures defined in preference terms.
Key results
- DOPL regret is Õ((2c1+4B/(1-D))√(2NT|S|ln(4|S||A|NT/ε))) with probability at least 1-2ε, claimed as first Õ(√(T ln T)) regret for RMAB with preference feedback.
- DOPL significantly outperforms MLE-based baselines in episodic reward on App Marketing, CPAP and ARMMAN and approaches the oracle.
- Preference inference reduces required comparisons per decision epoch from O(B^2) to B-1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use DOPL instead of the considered baselines | App Marketing, CPAP Therapy, and ARMMAN · App Marketing, CPAP Therapy, and ARMMAN | episodic reward | Helped |
| Use DOPL instead of the considered baselines | App Marketing, CPAP Therapy, and ARMMAN · App Marketing, CPAP Therapy, and ARMMAN | cumulative regret | Helped |
Limitations
- Preference feedback carries less information, requiring more online data.
- Frequent activation of arms across states is needed for empirical preference estimation, which may need a platform to collect feedback.
- Asymptotic optimality of the index policy relies on a uniform global attractor assumption.
Experimental setup
Datasets: App Marketing (synthetic) CPAP therapy environment ARMMAN maternal healthcare environment
Benchmarks: App Marketing CPAP ARMMAN
Metrics: episodic reward cumulative regret
Baselines: Oracle MLE_WIBQL MLE_LP MLE_QWIC RANDOM
Builds on: UCRL2 Colored-UCRL2 Whittle index Bradley-Terry model direct preference optimization
Closest papers by meaning
- Provably Efficient Reinforcement Learning for Adversarial Restless Multi-Armed Bandits with Unknown Transitions and Bandit Feedback (ICML 2024 · similarity 0.90)
- Online Restless Multi-Armed Bandits with Long-Term Fairness Constraints (AAAI 2024 · similarity 0.89)
- Bandits with Preference Feedback: A Stackelberg Game Perspective (NeurIPS 2024 · similarity 0.88)
- Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.88)
- Enhancing Preference-based Linear Bandits via Human Response Time (NeurIPS 2024 · similarity 0.88)
- Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits (NeurIPS 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.