Combinatorial Reinforcement Learning with Preference Feedback

Thank you very much for your positive review! Below, we provide our responses to your comments and concerns.

Experiment

• Additional real-world data experiments: In response to the reviewer’s suggestion, we conducted experiments on the real-world MovieLens dataset (Harper & Konstan, 2015). Due to space limitations, we refer the reader to our response to reviewer ofJq for details on the experimental setup.

  • A link to the results is provided here: [Link]

• Request for additional ablations: While we appreciate the reviewer’s suggestion regarding ablation studies, we believe they may NOT be essential for the following reasons:

  • Optimistic- (or pessimistic-) only variants: Given the theoretical nature of our work, we believe it is sufficient to empirically evaluate algorithms that are either provably guaranteed or previously proposed, such as LSVI-UCB and Myopic (OFU-MNL+). However, if the reviewer strongly believes that ablation studies on "optimistic-only" or "pessimistic-only" variants are necessary to support our theoretical findings, we are open to conducting these experiments and will include the results in our final response.

  • Variance-weighted Q-learning / Online sensitivity sub-sampling: We believe there may be a misunderstanding—these techniques are NOT original contributions of our work. As stated in Section 4 and Appendix B, we adopted them from prior literature (e.g., Agarwal et al., 2023; Kong et al., 2021), adapting them to our problem setting. Therefore, we see no strong motivation to perform ablation studies specifically on these components.

• Confidence interval: In Figure 1, the shaded area represents $\pm1$ standard deviation.

Computational efficiency

Our algorithm enjoys polynomial computational complexity with respect to the number of items $N$, making it highly efficient both computationally and statistically.

The computational complexity per episode is $\mathcal{O}(\text{poly}(N) H + H \log \frac{T \mathcal{N}}{\delta} \max_h \text{dim}_{\nu,K}(\mathcal{F}_h) )$. The first term arises from the assortment selection (see Remark 4.2), and the second term comes from the online sensitivity sub-sampling procedure (see Proposition B.2). For further details regarding the computational cost of the sub-sampling, please refer to Theorem 1 in Kong et al. (2021), as space is limited here.

Moreover, we'd like to clarify that the computational cost of the online sensitivity sub-sampling does NOT scale with the action space size $A$ nor with the number of items $N$. (The generalized eluder dimension may depend on $N$, though not on $A$.) Therefore, even if the action space grows exponentially, the method remains highly effective.

Additionally, we reported the runtime per round in Table G.1 (and provided results for larger item sets at [Link]), which shows that the runtime of our algorithm indeed scales polynomially with $N$, and is significantly more efficient than LSVI-UCB, whose computational cost is $\mathcal{O}(HA)\simeq\mathcal{O}(HN^M)$.

Techinical novelties

Our key technical contributions are as follows:

1. A novel assortment selection strategy that alternates between optimistic and pessimistic utility estimates.
2. The first to incorporate both unknown item values (rewards) and nonzero outside-option item values in the MNL choice model.
3. A $\sqrt{H}$ improvement over naïve summation of $H$ bandit regrets.
4. A fine-grained regret analysis for general function approximation.

For further details, please refer to Section 5.2.

Generalized Eluder dimension

The generalized Eluder dimension is applicable to weighted regression, while the standard Eluder dimension applies only to non-weighted regression. Thus, the generalized Eluder dimension is the appropriate choice for our setting. If we were to use unweighted regression with the standard Eluder dimension, it is straightforward to see that this would yield a looser regret bound for general function approximation—similar to what arises in $\mathcal{F}$-LSVI (Wang et al., 2020). For a detailed comparison between the two Eluder dimensions, we refer the reader to Theorem 4.6 in Zhao et al. (2023), as mentioned in Line 184.

Others

• Explanation of variance-weighted Q-learning: This method adaptively adjusts update weights using variance estimates, giving more importance to low-variance (hard) regions. This also allows for tighter confidence intervals and stronger theoretical guarantees (see Agarwal et al., 2023).

• Fixed user preference: We do NOT assume fixed user preferences; instead, the state can capture dynamic factors like satisfaction and interaction history, allowing preferences to evolve over time.

• Intuition behind switching utilities: We design an optimistic strategy where the estimated value is likely greater than the true value.

We appreciate your time to review our paper and your valuable feedback.

It seems that your main concern is the lack of empirical validation for the proposed algorithm. However, we would like to emphasize that this is a theoretical paper, submitted to the theory category. Our work introduces a new framework—combinatorial RL with preference feedback—in a principled way, supports non-linear function approximation, and achieves near-optimal regret guarantees in linear MDPs. We believe these contributions represent a substantial advancement in the foundations of RL and, on their own, are sufficient to merit acceptance.

Nevertheless, in response to the reviewer’s request, we have also conducted experiments on the large-scale, real-world MovieLens dataset (Harper & Konstan, 2015) to provide additional empirical validation.

Additional real-world data experiments

The MovieLens dataset contains 25 million ratings on a 5-star scale for 62,000 movies (base items $a$) provided by 162,000 users ($u$). We define the state $s$ as the number of movies a user $u$ has watched after entering the system, denoted by $s = (u, n)$, where $n \in \\{0, \ldots, H-1\\}$ is the number of movies watched during the session. We interpret the ratings as representing MNL utilities.

In each episode $k$, a user ($u_k$) is randomly sampled and arrives at the recommender system, initiating the state $s^k_1 = (u_k, 0)$. The agent offers a set of items with a maximum size of $M$. If the user clicks on an item, they receive a reward of $1$ and transition to the next state $s^k_2 = (u_k, 1)$. If no item is clicked, the user receives no reward and remains in the current state ($s^k_2 = s^k_1$). In addition, certain junk items—such as those with a provocative title and poster but poor content—can cause users to leave the system immediately. This is modeled as a transition to an absorbing state, where no further rewards are received and the state remains unchanged regardless of future actions. We believe the presence of such junk items is quite natural and reflective of real-world recommendation environments.

For our experiments, we use a subset of the dataset containing $1.1 \times 10^3$ users and a varying number of movies, $N \in \\{50, 100, 200\\}$. To construct MNL features, we follow a similar experimental setup as in [1], employing low-rank matrix factorization. For linear MDP features, we apply the same approach as used in our synthetic data experiments. We set the parameters as follows: $K = 10000, H=3, M=4, |\mathcal{S}|=100*(H+1)=400$ (including the absorbing state), $d=26$ (MNL feature dimension), $d^{lin}=204$ (Linear MDP feature dimension), $N\in\\{50, 100, 200\\}$ (number of base items) and |\mathcal{A}|= \sum_{m=1}^{M-1}$$N \choose m $\in \\{20875, 166750, 1333500\\}$. The proportion of junk items is set to $30\\%$.

• We provide an anonymous link to the experimental results here: [Link]

The results demonstrate the superior performance of our algorithm, highlighting its practicality for real-world scenarios.

[1] Shuai Li, Tor Lattimore, and Csaba Szepesvari. Online learning to rank with features. In International Conference on Machine Learning, pages 3856–3865, 2019.

Comparison to other baselines in the experiments

The reviewer also suggested including comparisons with more baselines. However, to the best of our knowledge, our framework is the first of its kind, and there are NO directly comparable baselines available. We believe it is sufficient to compare against the state-of-the-art myopic algorithm (OFU-MNL+, Lee & Oh, 2024) and a representative linear MDP algorithm (LSVI-UCB, Jin et al., 2020), and to demonstrate the limitations of these existing approaches within our more practical and general setting.

First theoretical guarantee in combinatorial RL with preference feedback

We strongly believe that our claim of providing the "first theoretical regret guarantee" is NOT overstated and therefore should not be considered a weakness of the paper. This is because, to the best of our knowledge, no prior theoretical work has addressed the framework we propose—combinatorial RL with preference feedback—which underscores the novelty of our contribution.

Although there have been recent significant advances in RL theory, we are not aware of any existing study that considers this framework. The most closely related line of research is cascading RL (Du et al., 2024); however, that setting involves presenting items sequentially, one at a time, rather than simultaneously as sets, which represents the key distinction of our framewokr.

We sincerely believe that we have addressed all of your concerns. If you agree, we would greatly appreciate it if you could kindly reconsider your initial evaluation. Additionally, please feel free to reach out if you have any further questions or require clarification on any point.

We sincerely appreciate your positive support and recognition of the value of our work! We truly hope this research helps to shed light on a new direction for the RL community, particularly in the area of combinatorial RL. Please don’t hesitate to reach out if you have any further questions.

Thank you for acknowledging the value of our work and providing a positive evaluation! We will address your questions below.

Additional real-world data experiments

As per the reviewer’s request for real-world experiments, we have additionally conducted experiments on the large-scale, real-world MovieLens dataset (Harper & Konstan, 2015) to provide further empirical validation.

The MovieLens dataset contains 25 million ratings on a 5-star scale for 62,000 movies (base items $a$) provided by 162,000 users ($u$). We define the state $s$ as the number of movies a user $u$ has watched after entering the system, denoted by $s = (u, n)$, where $n \in \\{0, \ldots, H-1\\}$ is the number of movies watched during the session. We interpret the ratings as representing MNL utilities.

In each episode $k$, a user ($u_k$) is randomly sampled and arrives at the recommender system, initiating the state $s^k_1 = (u_k, 0)$. The agent offers a set of items with a maximum size of $M$. If the user clicks on an item, they receive a reward of $1$ and transition to the next state $s^k_2 = (u_k, 1)$. If no item is clicked, the user receives no reward and remains in the current state ($s^k_2 = s^k_1$). In addition, certain junk items—such as those with a provocative title and poster but poor content—can cause users to leave the system immediately. This is modeled as a transition to an absorbing state, where no further rewards are received and the state remains unchanged regardless of future actions. We believe the presence of such junk items is quite natural and reflective of real-world recommendation environments.

For our experiments, we use a subset of the dataset containing $1.1 \times 10^3$ users and a varying number of movies, $N \in \\{50, 100, 200\\}$. To construct MNL features, we follow a similar experimental setup as in [1], employing low-rank matrix factorization. Specifically, we randomly split the user set into two subsets, $U_1$ and $U_2$, where $|U_1|=100$ and $|U_2|=1000$. The rating matrix from users in $U_1$ is used to derive user and movie embeddings via singular value decomposition (SVD), with both user and movie feature dimensions set to $d_U = 5$. We define the user-movie feature as the outer product of the corresponding user and movie embeddings, resulting in a $25$-dimensional vector. The final MNL feature vector is then given by $\phi(s,a)= [\text{user-movie feature}, \text{number of movies watched}]^\top \in \mathbb{R}^{26}$. For linear MDP features, we apply the same approach as used in our synthetic data experiments.

We set the experimental parameters as follows: $K = 10000, H=3, M=4, |\mathcal{S}|=100*(H+1)=400$ (including the absorbing state), $d=26$ (MNL feature dimension), $d^{lin}=204$ (Linear MDP feature dimension), $N\in\\{50, 100, 200\\}$ (number of base items) and |\mathcal{A}|= \sum_{m=1}^{M-1}$$N \choose m $\in \\{20875, 166750, 1333500\\}$. The proportion of junk items is set to $30\\%$.

• We provide a link to the experimental results here: [Link]

The results demonstrate the superior performance of our algorithm, highlighting its practicality for real-world scenarios.

[1] Shuai Li, Tor Lattimore, and Csaba Szepesvari. Online learning to rank with features. In International Conference on Machine Learning, pages 3856–3865, 2019.

Additional realted works

We will ensure that combinatorial bandits are discussed in the Related Work section and that the papers suggested by the reviewer are included in the final version of the paper. Specifically, we plan to add the following discussion:

"Our work is related to prior studies on combinatorial bandits with semi-bandit or cascading feedback [appropriate references]. However, our framework differs significantly from these approaches. In the semi-bandit and cascading settings, user feedback on a specific item depends only on that item’s context, independent of other items offered simultaneously. Thus, these approaches do not account for substitution effects among items. In contrast, our work utilizes an MNL choice model where user feedback depends explicitly on the entire assortment presented, leading to additional analytical challenges."

Question

Is the exploration method (Line 20) effective? compared to other classic exploration methods like UCB and TS?

We can evaluate the effectiveness of the exploration method (Eqn.(9)) from two perspectives: statistical and computational efficiency.

• Statistical efficiency: The proposed exploration strategy ensures that overly optimistic item $Q$-estimates (which have larger bonuses) are used infrequently, resulting in tighter regret bounds compared to classical methods.

• Computational efficiency: Since our exploration method employs a non-Markovian policy, it requires computations involving the entire history up to horizon $h$. Consequently, its computational cost is roughly $H$ times greater than that of UCB or TS.