mlsanityData to 14 Oct 2026

Combinatorial Reinforcement Learning with Preference Feedback

arXiv 2502.10158 ↗First posted 14 Feb 2025stat.ML cs.LGcited by 2

On the map: Deep reinforcement learning methods → RL for games and combinatorial optimization

Abstract (arXiv)

In this paper, we consider combinatorial reinforcement learning with preference feedback, where a learning agent sequentially offers an action--an assortment of multiple items to--a user, whose preference feedback follows a multinomial logistic (MNL) model. This framework allows us to model real-world scenarios, particularly those involving long-term user engagement, such as in recommender systems and online advertising. However, this framework faces two main challenges: (1) the unknown value of each item, unlike traditional MNL bandits that only address single-step preference feedback, and (2) the difficulty of ensuring optimism while maintaining tractable assortment selection in the combinatorial action space with unknown values. In this paper, we assume a contextual MNL preference model, where the mean utilities are linear, and the value of each item is approximated by a general function. We propose an algorithm, MNL-VQL, that addresses these challenges, making it both computationally and statistically efficient. As a special case, for linear MDPs (with the MNL preference feedback), we establish the first regret lower bound in this framework and show that MNL-VQL achieves nearly minimax-optimal regret. To the best of our knowledge, this is the first work to provide statistical guarantees in combinatorial RL with preference feedback.

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods. First posted on arXiv 14 Feb 2025.

Builds on

0 of 0 references.

No references here yet.

Built on by

Cited by year (2026 to 14 Oct)

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

2 papers.

  1. 2025Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Optionscited by 2
  2. 2026Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descentcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Minimax Optimal Variance-Aware Regret Bounds for Multinomial Logistic MDPs
  2. 2025Preference Optimization for Combinatorial Optimization Problems
  3. 2025Heuristics for Combinatorial Optimization via Value-based Reinforcement Learning: A Unified Framework and Analysis
  4. 2026Variance-Adaptive Optimal Algorithm for Reinforcement Learning with Multinomial Logit Function Approximation
  5. 2024Bandits with Preference Feedback: A Stackelberg Game Perspective
  6. 2024Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation
  7. 2024A Minimaximalist Approach to Reinforcement Learning from Human Feedback
  8. 2023Iterative Preference Learning from Human Feedback: Bridging Theory and Practice for RLHF under KL-Constraint