Research map / Bandits and online learning / Contextual bandits and Thompson sampling
Combinatorial Reinforcement Learning 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.
Proposes an algorithm (MNL-VQL) for combinatorial RL with MNL preference feedback and general function approximation for item-level Q-values, with regret guarantees and a matching lower bound in linear MDPs.
Problem
Combinatorial reinforcement learning where an agent offers assortments to users whose choices follow an MNL preference model, with long-term state transitions and unknown item values; prior theory covers only myopic MNL bandits.
Approach
Estimate item-level Q-values with general function approximation and variance-weighted regression, then select assortments via optimistic/pessimistic MNL utilities so optimism holds; assortment optimization is reduced to a linear program (Charnes-Cooper) rather than enumeration.
Key results
- Regret upper bound of d√(HK) + (1/κ)d²H² + function-approximation terms; for linear MDPs, Õ(d√(HK) + D√(HK)) matched by an Ω(d√(HK) + D√(HK)) lower bound, giving near-minimax optimality.
- In synthetic experiments, the proposed algorithm significantly outperforms Myopic and LSVI-UCB, with Myopic converging to a suboptimal policy and the method running much faster than LSVI-UCB when the assortment count is large.
- On MovieLens with N in {50,100,200} items and K=10000, the algorithm substantially outperforms baselines.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| account for long-term state transitions and item values instead of selecting assortments by immediate rewards only | Combinatorial RL with preference feedback · Synthetic online shopping with budget | episodic return | Helped |
| account for long-term state transitions and item values instead of selecting assortments by immediate rewards only | Combinatorial RL with preference feedback · MovieLens | episodic return | Helped |
Surprising findings
- Using optimistic MNL utilities alone does not guarantee optimism here, because the outside option's estimated value can be the highest, so the method alternates optimistic and pessimistic utilities.
Limitations
- Requires strong completeness and realizability assumptions on the function class, including second-moment completeness.
- Regret bound has large polynomial dependence on H and d_nu (e.g., H^5 and (D)^6 terms) and requires K large for the lower-order terms to be dominated.
- Experiments are simulated or use MovieLens ratings as MNL utilities rather than real user choice data.
Experimental setup
Datasets: MovieLens (25M ratings subset, 1.1e3 users) synthetic online shopping with budget environment
Benchmarks: synthetic online shopping with budget environment MovieLens-based recommender simulation
Metrics: episodic return regret runtime
Baselines: Myopic LSVI-UCB Optimal (reference)
Builds on: MNL bandits (OFU-MNL+) LSVI-UCB generalized eluder dimension value-function learning online mirror descent MNL estimation
Closest papers by meaning
- Nearly Minimax Optimal Regret for Multinomial Logistic Bandit (NeurIPS 2024 · similarity 0.90)
- Preference Optimization for Combinatorial Optimization Problems (ICML 2025 · similarity 0.89)
- Bandits with Preference Feedback: A Stackelberg Game Perspective (NeurIPS 2024 · similarity 0.89)
- Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation (NeurIPS 2024 · similarity 0.88)
- A Minimaximalist Approach to Reinforcement Learning from Human Feedback (ICML 2024 · similarity 0.88)
- Online Learning of Delayed Choices (NeurIPS 2024 · similarity 0.87)
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.