Combinatorial Reinforcement Learning with Preference Feedback
Authors: Joongkyu Lee
Min-hwan Oh
Venue: ICML 2025 poster (2025)
Keywords: Reinforcement Learning
Preference Feedback
Multinomial Logistic Model
Function Approximation
Combinatorial Action
Primary area: theory->reinforcement_learning_and_planning
TL;DR: We study combinatorial reinforcement learning with multinomial logistic (MNL) preference feedback and propose a computationally efficient algorithm that establishes the first regret bound in this framework.

Abstract: 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 near-optimal regret. To the best of our knowledge, this is the first work to provide statistical guarantees in combinatorial RL with preference feedback.

Combinatorial Reinforcement Learning with Preference Feedback
Joongkyu Lee"
Min-hwan Oh
Abstract
some previous studies have addressed problems within this cesting-paatiiuunn in deep RL (Sunchag et al., 2015; He et al., 2016; Swaminathan et al., 2017; Metz et al., 2017; Ryu et al., 2019; Ie et al., 2019; Delarue et al., 2020; McIn- erney et al., 2020; Vlassis et al., 2021; Chaudhari et al., 2024), with less emphasis on theoretical RL-to the best of our knowledge, it appears that no prior work has for- mally and theoretically defined the concept of combinatorial RL. This framework is especially relevant for wealdworld applications such recommender systems and online adver- tising, where multiple items (base actions) must be selected simultaneously, such as a set of products to recommend or advertisements to display. The challenge in combinatorial RL lies in the exponentially large action space and the need to efficiently optimize the agent's action selection while balancing exploration and exploitation (a challenge even for single action selection), while considering the long-term effects of these actions.
In this paper, we consider combinatorial reinforce- ment learning with preference feedback, where a learning agent sequentially offers an action- an assortment of multiple items-to user, whose preference feedback follows multinomial lo- gistic (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 chal- lenges: (1) the unknown value of each item, un- like traditional MNL bandits that only address single-step preference feedback, and (2) the dif- ficulty of ensuring optimism while maintaining tractable assortment selection in the combinatorial action space with unknown values. this paper. we assume a contextual MNL preference model, where the mean utilities are linear, and the value of each item is approximated by general func- tion. We propose an algorithm, MNL-VQL, that addresses these challenges, making it both com- putationally and statistically efficient, As a spe- cial case, for linear MDPs (with the MNL prefer- ence 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 RI. with preference feedback.
One of the most widely encountered settings in combinato- rial RL is preference feedback over combinatorial actions, commonly seen in streaming services, online retail, and sim- ilar platforms. Despite the broad applicability of this setting, theoretical studies have predominantly focused the multi- nomial logistic (MNL) bandit model (Rusmevichientong et al., 2010; Sauré & Zeevi, 2013; Agrawal et al., 2017, 7; 2019; Oh & Iyengar, 2019; 2021; Perivier & Goyal, 2022; Agrawal et al., 2023; Zhang & Sugiyama, 2024; Lee & Oh, 2024). The MNL bandit framework focuses on assortment (a set of items) selection by selecting subsets of items and receiving feedback on chosen items, modeled by the MNL. model (McFadden, 1977). However, these studies take myopic approach, optimizing for immediate, known rewards without considering the long-term impact on user behavior.
1. Introduction
While MNL bandits have been widely studied, the myopic approach is limiting many real-world scenarios. For exam- ple in recommender systems, incorporating the long- long-term impact of recommendations opens the door balancing short-term engagement with long-term user satisfaction. For instance, recommending junk product or content might lead to high immediate reward but it can decrease user satis-
We first formally state the concept of Combinatorial Re- inforcement Learning (RL), which we refer to as a class of RI. problems where the action space is combinatorial, meaning that the agent selects combination or subset of base actions from a set of possible base actions. Although
'Scoul National University, Scoul, Korca. Correspondence to: Min-hwan Oh <minoh@ anr
Surprisingly, this is in contrast to the rich theoretical literature in combinatorial bandits (Chen et al., 2013; Kveton et al., 2015b;a; Combes et al., 2015), which extend the multi-armed bandits.
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Combinatorial Reinforcement Learning with Preference Feedback
faction over time due fatigue. This trade-off between immediate and long-term outcomes is not captured by tradi- tional MNL bandit. See Appendix A for a more details.
mas D.5, D.9, and D.13) requires fundamentally more so- phisticated analytical techniques. Finally, we avoid naive combinatorial enumeration when selecting the assortment (Equation (8)) by reformulating the optimization problem as a linear program (LPP, inspired by Davis et al. (2013). Finally, for challenge (3), instead of naively summing over MNL bandit regrets, we bound the regret of the MNL preference model in terms of the sum of the variances of value functions and apply the law of total variance (Latti- more & Hutter, 2012; Gheshlaghi Azar et al., 2013). This approach reduces MNI. regret by factor of /H compared to directly summing И MNL bandit regrets. Moreover, in the special case of linear MDPs with preference feedback, we achieve nearly minimax -pptimall regret.
On the empirical side, several studies have explored long- term user engagement in recommendation systems, partic- ularly using deep RL (Swaminathan et al., 2017; Ie et al., 2019; MeInerney et al., 2020; Vlassis et al.. 2021; Chaud- hari et al., 2024). However, there is a significant gap in the theoretical understanding of combinatorial actions with preference feedback, particularly within the RL framework. To the best of our knowledge, no theoretical work has yet explored this important problem setting.
In this paper, we aim to address this gap by rigorously studying combinatorial RL with preference feedback and developing provably efficient algorithm that maximizes long-term user engagement by incorporating state transi- tions (e.g., historical behavior) into decision-making. We consider a setting where the Q-function of an assortment is decomposed into two components: the preference model and the item values, inspired by Ie et al. (2019). Specifi- cally, we focus on the contextual MNL preference model with linear mean utilities (Agrawal & Goyal, 2013; Cheung & Simchi-Lew 2017; Agrawal et al., 2019; Oh & Iyen- gar, 2019; 2021; Amani & Thrampoulidis, 2021; Perivier & Goyal, 2022; Agrawal et al., 2023; Zhang & Sugiyama, 2024; Lee & Oh, 2024) and use general function approxima- tion to estimate item values (Jiang et al., 2017; Wang et al., 2020; Jin et al., 2021: Du et al., 2021; Foster et al., 2021:
Our main contributions are summarized as follows:
We propose MNL-VQL, which achieves a regret upper bound of Ō (dvHK HK + (dim(F))K log [FI) while maintaining computational efficiency (Theorem 5. Here, H is the horizon length, K is the total number of episodes. d is the feature dimension of the MNL pref- erence model, and dim(F) (F) is the generalized Eluder dimension (see Definition 3.5) of the function class F. To the best of our knowledge, this is the first theoretical regret guarantee in combinatorial RL with preference feedback.
For the special case of linear MDPs (with preference feedback), MNL-VQL obtains regret upper bound of O(d/HK + (Hi) ), where d is the feature di- mension of the linear MDPs (Theorem 5.2). Further- more, we establish matching regret lower bound of M(d/HK HK + d'in /HK), ), show the minimax-oppimmaliyy of our algorithm in linear MDPs (Theorem 5.3).
Agarwal et al., 2023; Zhao et al., 2023). The key challenges in this framework are: (1) the unknown long-term value of each item due to the stochastic nature of rewards and transitions, (2) the difficulty of selecting an assortment that ensures optimism while considering tractable assortment optimization in the combinatorial action space, given the unknown values, and (3) achieving a tighter regret bound (for MNL preference model) than simply summing over H MNL bandit regrets.
2. Related Work
MNL bandits. The MNI. bandits were initially studied in Rusmevichientong et al. (2010), followed by a line of improvements (Filippi et al., 2010; Rusmevichientong et al., 2010; Agrawal et al., 2017; Oh & Tyengar, 2019; Faury et al., 2020; Abeille et al., 2021; Faury al., 2022; Oh & Iyengar, 2021; Perivier & Goyal, 2022; Agrawal et al., 2023; Lee & Oh, 2024). In MNL bandits, the goal is to offer an assortment that maximizes the expected rewards, which are adaptively learned based on user preference feedback from the offered assortment. However, there are no state transitions, and is assumed that the value of each item is known, with the value of the outside option fixed zero. Our study extends this by not only estimating the MNL model but also the long-term item values.
Technical novelties. To tackle challenge (1), we estimate the optimistic item values by employing point-wise opti- mism under general function approximation (Agarwal et al., 2023). Based on these optimistic item values (which incor- porate uncertainty), we then select an assortment that en- sures sufficient exploration and guarantees optimism. This step is the most challenging part of our framework. Since the true value of each item is unknown, directly applying techniques from MNL bandits (which assume known true values) is not feasible. Thus, to address challenge (2), we propose a novel method to estimate the optimistic prefer- ence model by carefully alternating between optimistic and pessimistic utilities (for the preference model), using the optimistic item values (Equation (7)). Additionally, proving optimism (Lemma D.15) and other related results (Lem-
Combinatorial RL with preference feedback. Recently, several studies have demonstrated the empirical success of combinatorial RL with preference feedback (Swaminathan
2

---

Combinatorial Reinforcement Learning with Preference Feedback
al., 2017; le et al., 2019; McInerney et al., 2020; Vlassis et al., 2021; Chaudhari et al., 2024), where a set of items is offered to user, and (relative) choice feedback along with a reward is received. leading to transition to the next state. However, theoretical results quantifying the benefits of such methods are still few and far between. A closely related work is cascading RL (Du et al., 2024), which also involves selecting a set of items. However, in cascading RL, items offered to the user one by one, and the user decides only whether to choose the currently offered item. As result, this framework does not capture relative preference feedback across multiple items. Furthermore, in cascading RL, the probability of choosing each item is independent of the others, which is not the case in our framework.
assortment by default. A is the set of candidate assortments that always include the outside option do, contain at least one item (other than do), and have at most M items (includ- ing au), i.e., A = {A S I: do E A, 1 < | < M), where A is an assortment. For any (s, A) E S x A. we denote Pa, (a|s, A) as the probability of the user choosing on item a E A (including the outside option dg). Further- more, we let PA. : S I - Ag and th : S x I x S R characterize the transition kernel and instantaneous reward, respectively, at a given horizon h E [H]. Throughout this paper, we assume that Σ (sh, One Sh+1) E [0. 1] for all possible sequence (s), 01 ................................ 8H, sH,aH, 8H+1). H E Z+ is the length of each episode. A policy : S - A is mapping from the state space to the assortment space. Since the optimal policy is non-stationary in an episodic MDP, we use π to refer to the H -ttllee (TA)
Another related line of work is preference- (PbRL) (Akrour et al., 2012; Wirth et al., 2017: Christiano et al., 2017; Ouyang et al., 2022; Saha et al., 2023; Zhu et al., 2023; Zhan et al., 2023), where the policy is opti- mized based on relative, rather than absolute, preference feedback. However, our framework differs from PbRL in that our goal is not to offer just a single item, but to offer multiple items (a combinatorial base action).
RL
In each episode k E [K], an initial state of is picked arbi- trarily (e.g., user arrives at the system). The agent then follows a policy Λ² starting from sf At each step h e [H], the agent observes the current state sy. (c.g.. historical behav- iors of the user) and offers an assortment A = T (sf). The user's preference feedback o E A is then observed, which is drawn based on the choice probability Pn Af). Next, the system transitions to the next state s/+11 (1st at) and receives a reward ra (*% a 1 After H steps, the episode terminates, and the agent proceeds to the next.
RL with non-linear function approximation. With the limitations of the linear models (e.g., as shown in Lee & Oh (2023)), RL under non-lineat function approximation has gained attention (Jiang et al., 2017; Wang et al., 2020; Jin et al., 2021; Du et al., 2021; Foster et al., 2021; Ishfaq et al., 2021; Agarwal et al., 2023; Zhao et al., 2023) for model- ing complex function spaces like neural networks. Among these, Agarwal al. (2023); Zhao et al. (2023) achieved the best-known regret guarantees under general function approximation by introducing the concept of generalized Eluder dimension to handle weighted regression. Inspired by their work, we estimate the value of items (referred to as item-level Q-value) using general function approximation in this paper.
For any policy π {TT) we define the value func- tion of policy म, denoted as Vir S - RR the expected sum of rewards under the policy until the end of the episode when starting from Sn. = s, i.e., V (s) := E " aw,, Sw-)) sh = = More- over, we define the action-value function of policy m 0% S A + R, as the expected sum of rewards un- der policy starting from step h until the end of the episode after taking action A in state s; that is. Q7 A) :=
E - ax' +1) Sh s, A, = Al. Further- more we define the ltee- Q-value function (also called the Q-value) (%(s,a) a) := Σ. (n (s|ss, () a, s') + (s')(' Then, the Bellman equation for assortment RL is denoted as follows:
3. Problem Setting
3.1. Combinatorial MDPs with Preference Feedback
In this paper, we consider episodic combinatorial Markov decision processes (MDPs) with preference feedback, M,S,I,A, M, (P (r H). Here, S the set of states. Each state 8 E S reflects the user's status, capturing both relatively static user features (c.g.. demographics, interests) and relevant user history past behavior (e.g.. past recommendations items purchased or clicked). I := (aI..... .., ax, ) is the ground set of items (base actions), where @1, .1,.... aN are items and ag refers to the "outside option", meaning the user has chosen none of the items from the offered set of items (referred to as an "assortment" throughout the paper). It is included in every
(i A) Σ Pa(als, A)
A
Similarly, we define the optimal value function (s) sup, (s) and the optimal Q-value function as A)= Palals, A ()) a)), where Q' (s(ssa): := Σ. (5 a)) (r,)(,,,,s)) + Vi+z (6')) is the item-level optimal Q-value function. For any V : S - R and h E [H]. we define the item-level Bellman operator of
TThis assumes the chosen item's 's rewards and transitions are independent of other items in the assortment.
3

---

Combinatorial Reinforcement Learning with Preference Feedback
V as VvV= 8 - R, such that for all (s, a) 8 x I, (s, a) : - (1a,a) [ra(s, a, + V(s') s, a] The definition of value functions ensures that they satisfy the equation Qx(s,a)
3.3. Generalized Function Approximation for Q
We estimate the item-level Q-functions (referred as Q- values) using general function approximation. Specifically, the agent is given function class F == [_Fi)=-' where each set Fr. is composed of functions fn : S x I - [0, L], where L = (1)) Since no reward is collected in the (H + 1)th steps, we set fH+1 = O. We denote / as the maximal size of function class, i.., = max [Ful. We assume the completeness and realizability for F.
Th V. (s. We also define the second moment item-level Bellman operator of V as TRV S x - R such that for all (s, E S x I, ((,, a) = By (rn(s, a, 8') + ((s))² s,
Our goal is to minimize the cumulative regret over K episodes Regret(M,, == E - (st)..
Assumption 3.3 (Completeness & Realizability). For each h [H] and any V S - [[0, 1], we assume that Q7 Fi. and there exists fn, f% Fr, such that, for all (s, a) E S x
3.2. Multinomial Logistic Preference Model
In this paper, we make a structural assumption about the MDP M, where the user's choice probability {PA) follows multinomial logistic (MNL) model (McFadden, 1977) parameterized by {0%) We denote (- A: 07) as equivalent to (- A), explicitly showing the depen- dence on the parameter - Throughout the paper, we use (r,-)s, A) and Pa(-1s, A; 0)) interchangeably.
fa a) (s,, and f1,s, (s,
Remark 3.4. The completeness and realizability assump- tions are standard in RL with general function approxima- tion (Wang et al., 2021; Jin et al., 2021; Agarwal et al., 2023; Zhao et al., 2023). Our assumption is the same as those in Agarwal et al. (2023); Zhao et al. (2023), but stronger than those in Wang et al. (2021); Jin et al. (2021), especially, in terms of the second moment completeness. However, this assumption is essential for using point point-wise exploration bonuses and achieving tighter regret bound. Additionally, it naturally holds for both tabular and linear MDPs.
Assumption& 3.1 (MNL preference model). Let there exist a known feature map o : S XI - Rd such that (os,, a) 1)l22) E 1, and an unknown 0% E θ for all h E [H] where θ = {0 e Rd ||0||2 < B = (1)). Then, for any (s, HI) E S x A x [M, the probability of choosing any item a e A is defined
To capture the complexity of exploration in the MDP, we define the generalized Eluder dimension, which is weighted regression version of the original definition (Russo & Van Roy, 2013).
exp (Ø(s, a) 00)) Pa(a|s, A) - Ph(als, Ed'ed exp (ōls, T'TT07) 07
Definition 3.5 (Generalized Eluder dimension, Agarwal et al. 2023). Let p > 0, a sequence of state-item pairs Z₁ {z" )ー where xT = (8" (s",a"). a²), and a sequence of positive numbers σ = {a-}
Here, without loss of generality, we assume that (68, ao)
0 for all s S which implies that exp(ø(s, a 0%) 1.
J==1 The generalized Eluder dimension of a function class F F S.S. x I [0, L] with respect to p is defined dim (F) Ezk. dim (F, o).
Thus, the preference model can be equivalently expressed
exp( (pp()(s.)) 0%)
as PA (a| A: 0))
L+EooeAA) exp( ((s.a') 0;)
where
Following the previous MNL bandits (Oh& & Iyengar, 2021;
K Σ min ( D3 (=*: Zk-1, FK-1) 1,
Perivier & Goyal, 2022: Zhang & Sugiyama, 2024; Lee & Oh, 2024), we also introduce the following constant:
dim ZK. σk)==
(a+)2
Definition 3.2 deepedend constant). There exist 0 such that, for any A E A, a A A (aoo), h E [H], we have m (ala,, A, O)P, (4o s, A, 0) > K.
D3 (2 Zk- xx-1) sup Suppr.a -ー= Mite )- 3-fo(o))
(1((e) f2()))²
(o*1=
We write d, =
1 H > dim,, k (Fr) for simplicity.
A small k indicates larger deviation from the linear model. Note that 1/k can be exponentially large, so it is crucial to avoid any dependency on 1/K in our regret bound.
By Theorem 4.6 of Zhao al. (2023), the generalized Eluder dimension is upper bounded by the standard Eluder dimen- sion (Russo & Van Roy, 2013) up logarithmic terms.
By subtracting ((s,aa) from each d(s,a), where I. and defining d'(s, (s.a) : ($(,,a) (s)) we can ensure that ø' (s, 0a) = 0. This implies that exp(o' ) 00,) = 1. This assumption is commonly made in contextual MNL handits (Oh & Tyengar, 2019; 2021; Perivier& Goyal, 2022; Agrawal et al., 2023; Zhang& & Sugiyama, 2024; Lee & Oh, 2024).
4. Algorithm
In this section, we introduce an algorithm, which, to the best of our knowledge, is the first to provide statistical guaran- tees in combinatorial RL with preference feedback while
4

---

Combinatorial Reinforcement Learning with Preference Feedback
maintaining computational tractability, Step 1 involves on- line parameter estimation for the MNL preference model, proposed by Lee & Oh (2024). Steps 2, 3, and 4 implement vuriance-weighter regression to tighten the regret bound, as outlined in Agarwal et al. (2023). Step 5, which is our main contribution, ensures optimism in a computationally effi- cient manner, even with uncertainty in item-level Q-values. Step 6 introduces an exploration step that accounts for esti- mation errors from the MNL preference model.
The bonus is calculated as (s, n.x, (n(s, a) fie,, (s a). In general, this uncertainty bonus has high complexity, as the maximizing and minimizing func- tions can differ arbitrarily for each (s,a) E S x I. To address this, we use a low-complexity bonus oracle B (Agar- wal et al., 2023) that approximately dominates the value obtained from the point-wise maximization over Fr. With the oracle B, we can efficiently calculate the bonus by, with error of cb- Due space constraints, provide the formal definition of B in Appendix B (Definition B.
Step 1. Online parameter estimation for MNL (Line 6). At episode k and horizon h. given the user's choice feedback cf E Ar. the response for each item ai... E A is defined as vh (at.... := [ch, = a.m) ) E {0, 13. Therefore, the response variable y :- (v)(()) y% (ai,); )......... ..................... yt (a,,)), where & M I, is sampled from a multinomial distribution: va MNL(1, Pa (a 18, A4: B7..... ,a 5% Al; (,
Step 3. Overly optimistic/pessiiitti estimation for Q (Line 10-13). For a sharp analysis of the convergence of the optimistic estimate fh. we define an overly optimistic Q-value estimate fi.2. as well as overly pessimistic Q- value estimate Jhi--- Similarly to Sh. they are calculated by solving an unweighted regression problem (Line 10), and by adding (or subtracting) a bonus function, which is the output of the bonus oracle B (Line 12-13).
where the parameter 1 indicates that y is a single-trial sample, i.e. v/(a)) + E (a: ) 1. Then, for any (k, E [K] x [H] the multinomial logistic loss function is defined as:
Step 4. Variance estimation (Line 14 and 21). To calculate o introduced in (3), we first estimate the second moment by solving the unweighted regression problem:
(0) = Σ oE
vi(aa) log Ph(alst
gh E argmin ghEFn
E
(an(8h.a7) aT)) - (rh + (6++))()++))
Inspired by Zhang& & Sugiyama (2024); Lee & Oh (2024), for all (k: h) E [K] x [H]. we use the online mirror descent algorithm to estimate the true parameter 0 as follows:
Then, denoting # = (sh ah) for simplicity, we calculate the estimated variance as follows (this is an informal de- scription; for the precise formulation, see Equations (D.9) and (D.10) in Appendix):
1 110 ONli
@l ( 0) 0ee
(1)
27
where 7) = Ollog.M M) is the step-size, H. := H +
(oh)²= gh((A)) - (fh 2 Dhh O (Vlog.NNs)
= 6% (0%). and =²== Ala + -
Remark 4.1. The computation cost of the optimization prob- lem in (1) is (Md"), which dose not scale with is at all.
of max ( ff: Ollog
Then, with high probability, 0% lies within the following confidence interval (Corollary D.2).
max (Fh - st.- DZ.)) )}
(4)
c² = (0 0 o: 10- okllnn < aa =
(2)
where Dh,n
Dr 1x- (17+=) and Dh. Drr (2:; 2--1
Step 2. Weighted regression and optimistic estimation for Q (Line 7-9). Using the past dataset, we solve the following (weighted) regression problem to fit Ta Vk
Step 5. Efficient optimistic Q-value estimation based on unknown item values (Line 15-16). In this step, we address our main challenge: selecting an optimistic assort- ment based on the optimistic Q-values, which incorporate uncertainty, while ensuring computational tractability.
((a(5h.55) - r - Vk (.
fk, E argmin freF
(o%)²
To introduce optimism and encourage exploration, we need to solve the following optimization problem using the op- timistic (or pessimistic) estimates of the Q-values, specifi- cally Sh. for j 1, +2:
(3)
where (at)2 is variance upper bound, i.e., (at)² >
V[rn + Viz (s afI, which will be specified later. Then, an optimistic Q-value estimate at horizon h is de- fined as fh.1 = fh.1 + bb, where by is the optimistic bonus.
Ah. E aargmax max Σ Ph A A:0)Sh (s),a) (5) AEA DECk asA
5

---

Combinatorial Reinforcement Learning with Preference Feedback
Algorithm 1 MNL-VQL, MNL. Preference Model with Variance-weighted Item-level Q-Learning
1: Inputs: parameter space O function class (Fa) H consistent bonus oracle B.
2: Parameters: {art, //, hh,2 3 (I.A)][H[xx[K)+
IK P. bonus error Eb,, v,
3: Initialize: dataset D2 = Ø for all h E [H].
4: Generate (D,) h=1 from initial state s) by random policy and set of = o/ 2 for all h E [H].
5: for episode = 2, ... K do
6: for horizon h H, H ,,...,, do
// CACULATE OPTIMISTIC AND OVERLY OPTIMISTIC, PESSIMISTIC Q- Q-VALUES
fh.1 E argmin M.FF, - (mp) (fa(s), (/) - r% - (5++1))
7:
1//1 - (1o) Fi; Sh. Ph.,P.p cb) (see Definition B.
8:
Update (1,](:;)) - mmnn [1h: (+--) + [ (t,),(
9:
10:
fh.j argmin -x=1 fn 07p) - r/- - Vitt (8++ .j +2.
11:
1//22 - B (117) - Fr, Ph / 2/ 2, P: Cb) (see Definition B.I).
12:
Update (1.)( - min J (1..) ) 26 (, .) b/ (..1).....
13:
Update (h,) - max (..)) 0/ 2..0
Sh argmin AM I gh(5% (7) - (r% + Vi 2)
14:
// UPDATE VALUES
15:
Update (t).)) (7). (7).
Update Q (1. - Emen Ph (l) and (.) maxAEA (h A), 1.
16:
17:
end for
18:
Receive initial state si.
19:
for
1, .2.....7 H do
20:
Offer A by (9) and receive ati rhe and s/111
21:
Update D - D u (sh ab, rhe shit and update of and of by (4).
22:
Update 0++1 using online mirror descent (I).
23:
end for
24:
end for
where Cj is defined in (2). One naive approach to solving the optimization problem in (5) is to add bonus terms to the estimation for each assortment A and then enumerate all A e A to find the maximum. However, this approach results in computational cost of M)
However, in our setting, using the optimistic utilities can decrease the expected value of Jk.j- To explain why: even
if the true value of the outside option, (s oo). is the lowest, its estimated value, fh. (s, ap). can be the highest- i.e., fh ag) (*, for all E (((a))-da to uncertainty. In this case, increasing the MNI. utilities results in a decrease in the expected value of fh.j. This challenge arises from the unknown item values, Q which is one of the main difficulties we face in our framework.
To avoid this exponential computational cost, inspired by Tran-Dinh al. (2015), we use optimistic MNL utilities instead of directly adding bonus terms to A A Ph (alst, A; ()))), (s, However, unlike tradi- tional MNL bandits (Oh & Iyengar, 2019; 2021; Lee & Oh, 2024), simply using optimistic utilities does not always guarantee optimism because of fhi is not the true values. In MNL bandits, the item values are known, and the value of the outside option ag is fixed zero. Therefore, increasing the MNL utilities (using the optimistic utilities) lowers the probability of choosing the outside option, which in turn increases the expected value of the item values.
To tackle this problem, more refined approach is required to use the utility based on fh Given the confidence inter- val in (2), we define the optimistic utility b (s, a) and the pessimistic utility (5((s, a) as:
(x) = o(s, a) 0 + a (bs a) ((H:)))
() = o(s, a) 0h - at (2l (l))
(6)
6

---

Combinatorial Reinforcement Learning with Preference Feedback
We then the optimistic utility when ( ag) is not the highest estimate to calculate the optimistic choice prob- abilities Ph..- Formally, let 1h E {1,0} indicate whether there exists a E Iafoo) such that ( ())= > shiss, 0o) (hh. = if such an event occurs). Then, we define
and 3.3 hold. Then, with probability at least 8, the regret of XNL-VQL is upper-boundee by:
Regret(M,,)) K) & dvHK + dd
regret from MNL model
exp (ol(s,a))
V dd log + H log N Vlog log (NN)),
if hi
DeER exp (f, exp (s))a
(al A) ==
regret from general funccion approximation of Q where d is the feature dimension of the MNL preference model, N maX [Fr)), and No is the size of the bonus function class, i.e., No = [W]
otherwise.
Ever exp (s,))))))
Equipped with Ph.j. for any j = 1, 22, we select the assort-
Discussion of Theorem 5.1. The proof is deferred to Ap- pendix D. The first two terms arise from the regret of the MNL preference model, while the other two terms come from the regret associated with the general function approxi- mation for item-level Q-values. When H = 1, reducing our setting to MNL bandits (though not exactly the traditional MNL. bandits, as we consider a more general case where item values are unknown and the value of the outside option can be non-zero), the first two terms of regret simplify to Öddv K + d.). This matches the known minimax opti- mal regret established by Lee & Oh (2024). Note that we avoid the detrimental dependence on k. in our leading term. The last two terms of our regret, incurred from estimating item-level Q-values using general function approximation, similar to Agarwal et al. (2023) and Zhao et al. (2023).
ments Ah. as follows:
Ahi arrgax Σ
Phis(alsh, A)5h (sh a),
(8)
AEA
aEA
(o%
Here, ( A) Ene Phe ( A) f),k (s a) is the optimistic Q-values. This construction can induce suf- ficient exploration and guarantee optimism (Lemma D.15). Furthermore, by using the optimistic (or pessimistic) util- ities for each item, instead of calculating bonus terms for each A E A, the optimization problem in (8) can be solved efficiently (Davis et al., 2013).
Remark 4.2. The optimization problem in (8) can be trans- formed into a linear programming (LP), making it solvable
With respect to computational cost, by using the online sensitivity sub-sampling method (Algorithm B.I), we can efficiently implement the bonus oracle B with log [ log,, - Ô (max dim,,x log log SS x ZI). Furthermore, we can avoid the exponential computational cost required to solve the optimization (8) (see Re- mark 4.2). As a result, our algorithm is both computationally tractable and statistically efficient.
in polynomial time with respect to [Z] (see Appendix C).
Step 6. Exploration policy (Line 20). We then offer the assortment A to the user as follows:
A
if S ( (n)) 20 ( uky Vay E Abr wh' & h.
A/ =
otherwise,
5.2. Technical Comparisons to Related Work
(9) where 2k is a carefully chosen threshold (see Table D.2 for the exact value). When the optimistic sequence fī. and the overly optimistic sequence fh,2 diverge beyond a certain threshold, we offer the assortment Af.2. which is selected based on 2h This approach ensures that by occasionally using fh.2. the variance upper bound of. estimated from fh.2. does not become overly pessimistic.
Comparison to Lee & Oh (2024). Our framework ad- dresses strictly more challenging problem than Lee & Oh (2024) because consider (1) multiple steps, (2) un- known values, and (3) nonzero values for the outside op- tion. The key challenge in tackling these three aspects lies in ensuring optimism while maintaining computational efficiency, which requires a fundamentally different ap- proach-carefully leveraging optimistic and pessimistic util- ities. Moreover, in Theorem 5.1, our regret analysis for the MNL preference model goes beyond merely summing over H MNL bandit regrets. Instead, we introduce a novel regret decomposition, bound the regret in terms of the sum of the variances of value functions, and apply the law of total variance (Lattimore & Hutter, 2012; Gheshlaghi Azar et al., 2013). As a result, we achieve a regret reduction by a
5. Main Results
5.1. Non-linear Function Approximation for Q
Theorem 5.1 (Informal, Regret upper bound of MNL-VQL). 1 H dimy,k (Fr) with v = /I/KH. and Let d, = H set uy as in Equation (D.20). Suppose Assumptions 3.1

---

Combinatorial Reinforcement Learning with Preference Feedback
factor of VH compared directly summing over H MNL bandit regrets.
6. Numerical Experiment
In this section, we empirically evaluate the performance of our algorithm, MNL-VQL, in two settings: a synthetic environment (Subsection 6.1) and a real-world dataset (Sub- section 6.2).
Comparison to Agarwal et al. (2023). While the regret analysis for general function approximation largely follows the approach of Agarwal et al. (2023), several technical lem- mas (e.g., Lemmas D.23 and D.24) and parameters (e.g., (4)) are revised to accommodate the estimation errors specific to
We compare our algorithm against two baselines: Myopic and LSVI-UCB (Jin et al., 2020). Myopic is a variant of OFU-MNL+ (Lee & Oh, 2024) adapted for unknown rewards. It selects assortments based only on immediate rewards, ignoring long-term effects. LSVI-UCB (Jin et al., 2020) treats each assortment as a single atomic action, requiring enumeration of all possible assortments. We also include the optimal policy (Optimal) as a reference.
MNL models.
Overall, our results cannot be gleaned by simply piecing to- gether prior techniques. Instead, they arise from an involved analysis, leading to stronger theoretical guarantees in more general and new combinatorial RL. settings.
5.3. Linear MDPs with Preference Feedback
As special case, we also consider linear MDPs (refer Defi- nition E. with preference feedback. To show the depen- dency on parameters, we denote the linear MDPs as MM.,, where 3' = {(0)) ( [= Note that the bonus oracle can be easily implemented using the standard elliptical bonus, which satisfies all the necessary properties (refer Appendix E). The proof is deferred to Appendix E.
6.1. Synthetic Environment
Setup. We consider an online shopping with budget environ- ment (Figure G.1), modeled as linear MDP with an MNL preference model. Let S = {s,,..... , $1s} of states and I = {a....., aN an) the set of items, where ag represents the outside option (no purchase). Each state 8y E corresponds to a user's budget level, with larger indices indicating a higher budget. The initial state is to the middle budget level. $[|s]/2]- The transition probabilities PA, rewards rh and preference model Pa remain constant across all time steps h E [H. so we omit the subscript h.
denote the set
Theorem 5.2 (Informal, Regret upper bound for linear MDPs). In linear MDPs, under the same conditions Theorem 5.1, with probability at least 1 8, the regret of MNL-VQL is upper-bounded by:
Regret (ME., K) & d.HR + 1 H2
At state 8j. the agent offers an assortment A E A with a maximum size of M. The user either purchases an item a A or does not (Ag A). If the user buys item a,, the agent receives reward rs)) the state transitions according to PP P((min(j++1]s) (8,, a:) x.. and P(=max(j-1.0) (5. a.) x- If the user does not buy anything (an), the reward is r(s), ao) = 0, and the state transitions as P( P($min()++11s))
+ d HK + H
(1oàx + (2) /H and
We also establish matching lower bound by constructing novel multi-layered (linear) MDP (see Figure F.1) with preference feedback. The proof is deferred to Appendix F. Theorem 5.3 (Informal, Regret lower bound for linear MDPs). For any algorithum and sufficiently large K, there exists an episodic linear MDP Me with MNL preference feedback such that the worst-case expected regret is lower bounded as follows:
on) = 1. For the MNL preference model, the true parameter 0* E Rd and the feature vector 6(s, a) E RRd are randomly sampled from a d-dimensional uniform distribution for each instance.
Results. Figure I demonstrates that our algorithm signifi- cantly outperforms other baseline algorithms. Remarkably, Myopic converges to a suboptimal solution, highlighting the importance of accounting for long-term values. Moreover, in Appendix Table G.I, we show that our algorithm is much faster than others, especially when the total number of as- sortments |A| is large. Due to the extremely slow runtime of LSVI-UCB, we could not include its performance results for N = 20 and N = 40. For more details, see Appendix G.
sup E= [Regret (Mg, K)] = Ω (d (dvHK- HK + d VHK..
Discussion of Theorems 5.2 and 5.3. For sufficiently large K, i.e., K > H3 (diin) ) the regret upper bound for linear MDPs scales as Õd HK + /HK, which matches the lower bound up to logarithmic factors. Note that if we rescale the rewards to be 1/H in the lower bounds of Zhou et al. (2021a) to align with our setting, their regret bound matches the second term of our regret bound, D (dddin HK). To the best of our knowledge, this is the first theoretical result proving minimax- opttialty in linear MDPs with preference feedback.
6.2. Real-Worke MovieLens Experiment
Setup. The Moviel.ens dataset contains 25 million ratings on a 5-star scale for 62,000 movies (base items a) provided by 162,000 users (w). We define the state as the number
8

---

Combinatorial Reinforcement Learning with Preference Feedback
MNL-VLL (ours)
LSVI-UCB (holistic)
Myopic (OFU-MNL+)
Optimal
N=10, |A|=637
N=20, |A|=21699
N=40, 760098
0.7
0.7
0.7
0.5
10000
20000
30000
10000
20000
30000
10000
20000
30000
Episodes
Episodes
Episodes
Figure 1: Synthetic experiment: Episodic returns averaged over 10 runs. Dotted lines indicate estimated returns for incomplete runs due to excessive runtime. Shading denotes +1 standard deviation.
MNL-VOL (ours)
LSVI-UCB (holistic)
Myopic (DFU-MNL+)
Optimal
5=50, |A|=20875
N=100, |A|=166750
N=200, |A|= 1333500
3.0
3.0
3.0
2.0
2.0
1.5
1.5
1.5
2500
5000
7500
10000
7500
10000
2500
10000
Episodes
Episodes
Figure 2: MovieLens experiment: The dotted lines represent estimated (virtual) episodic returns for cases that could not be run due to excessively long runtimes. Shaded regions represent =1 standard deviation.
of movies a user u has watched after entering the system, denoted by 8 = (u, n), where n E (O...., H - 1] is the number of movies watched during the session. We interpret the ratings as representing MNL utilities.
thetic data experiments. We set the parameters as follows:
K = 10000, H = 3, M = 4, S| = 100 (H + 1) 400 (including the absorbing state), d = 26 (MNL feature di- mension), din 204 (Linear MDP feature dimension), N (50, 100, 200} (number of base items) and |A| MM-1 (m) (20875, 166750, 1333500). The proportion of junk items is set to 30%.
In each episode k; user (ug) is randomly sampled and arrives at the recommender system, initiating the state of (ux, 0). The agent offers set of items with maxi- mum size of M. If the user clicks on an item, they receive reward and transition to the next state zi = (ux,7 1). If no item is clicked, the user receives no reward and remains in the current state (of = sf) In addition, certain junk items-such those with provocative title and poster but to leave the system immedi- ately. This is modeled as a transition to absorbing state, where no further rewards are received and the state remains unchanged regardless of future actions. We believe the pres- ence of such junk items quite natural and reflective of real-world recommendation environments.
Results. Consistent with the synthetic experiment results, Figure 2 shows that algorithm substantially outperforms the baseline methods the real-world dataset. This demon- strates the robustness of our approach and its practical effec- tiveness in realistic settings.
poor content-can
7. Conclusion
In this work, study combinatorial RL with prefer- ence feedback, extending MNL bandit problems account for the influence of user states and state transitions in ap- plications like recommendation systems. Under an MNL preference model with linear utilities and general function approximation for item values, we propose an efficient al- gorithm, MNL-VQL, which, to the best of our knowledge, provides the first statistical guarantee. As special case, in linear MDPs, we show the minimax-optimality of MNL-VQL by establishing matching upper and lower bounds.
For our experiments, use subset of the dataset con- taining 1.1 103 users and varying number of movies, N E (50, 100, 200). To construct MNL features, we fol- low a similar experimental setup as in Li et al. (2019), em- ploying low-rank matrix factorization. For linear MDP features, we apply the same approach as used in our syn-

---

Combinatorial Reinforcement Learning with Preference Feedback
Impact Statement
Chaudhari, S., Arbour, D., Theocharous, G., and Vlassis, N. Distributional off-policy evaluation for slate recom- mendations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
2024.
Chen, K. D. and Hausman, W. H. Mathematical proper- ties of the optimal product line selection problem using choice- conjoint analysis. Management Science, 46 (2):327-332, 2000.
Acknowledgements
This work was supported by the National Research Foun- dation of Korea (NRF) grant funded by the Korea gov- ernment (MSIT) (No. RS-2022-NR071853 and RS-2023- 00222663), by Institute of Information & communications Technology Planning& & Evaluation (IITP) grant funded by the Korea government (MSIT) (No. RS-2025-02263722 and by AI-Bio Research Grant through Seoul National Uni-
Chen, W., Wang, Y., and Yuan, Combinatorial multi- armed bandit: General framework and applications. In International conference on machine learning, pp. 151- 159. PMLR, 2013.
Cheung, W. C. and Simchi-Levi, D. Thompson sampling for online personalized assortment optimization problems with multinomial logit choice models. Available at SSRN 3075658, 2017.
versity.
References
Christiano, P. F., Leike, J., Brown, T., Martic, M., Legg, S., and Amodei, D. Deep reinforcement learning from human preferences. Advances in neural information pro- cessing systems, 30, 2017.
Abeille, M., Faury, L.., and Calauzènes, C. Instance-wise minimax-optimal algorithms for logistic bandits. In Inter- national Conference on Artificial Intelligence and Statis- fics, pp. 3691-3699. PMLR, 2021.
Combes, R., Talebi Mazraeh Shahi, M. S., Proutiere, A., et al. Combinatorial bandits revisited. Advances in neural information processing systems, 28, 2015.
Agarwal, A., Jin, Y., and Zhang, T. Vo g Towards optimal regret in model-free rl with nonlinear function approxima- tion. In The Thirty Sixth Annual Conference on Learning Theory, pp. 987-1063. PMLR, 2023.
Cooper, A. C. W. et al. Programming with linear fractional functionals. Naval Research logistics quarterly. 9(3): 181-186, 1962.
Agrawal, P., Tulabandhula, T., and Avadhanula, V. A tractable online learning algorithm for the multinomial logit contextual bandit. European Journal of Operational Rexearch, 310(2):737-750, 2023.
Davis, J., Gallego, G., and Topaloglu, H. Assortment planning under the multinomial logit model with to- tally unimodular constraint structures. department of ieor, columbia university, 2013.
Agrawal, S. and Goyal, N. Thompson sampling for contex- tual bandits with linear payoffs. In International Confer- ence on Machine Learning, pp. 127-135. PMLR, 2013.
Delarue, A., Anderson, R., and Tjandraatmadja, Rein- forcement learning with combinatorial actions: An appli- cation to vehicle routing. Advances in Neural Information Processing Systems, 33:609-622 02099966022200 2020.
Agrawal, S., Avadhanula, V., Goyal, V., and Zeevi, A. Thompson sampling for the mnl-bandit. In Conference on learning theory, pp. 76-78. PMLR, 2017.
Agrawal, S., Avadhanula. V. Goyal, V., and Zeevi, A. Mnl- bandit: A dynamic learning approach to assortment selec- 2019.
Du, S., Kakade, S., Lee, J., Lovett. S., Mahajan, G., Sun, W., and Wang, R. Bilinear classes: A structural framework for provable generalization rl. International Conference on Machine Learning, pp. 2826-2836. PMLR, 2021.
tion. Operations Research, (7(5)):1433311
Akrour, R., Schoenauer, M., and Sebag, M. April: Active preference learning-base based reinforcement learning. In Ma- chine Leurning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2012, Bristol, UK September 24-28, 2012. Proceedings, Part II 23, pp. 116 131. Springer, 2012.
Du, Y., Srikant, R., and Chen, W. Cascading reinforcement learning. arXiv preprint arXiv:24011.08961 2024.
Faury, I.., Abeille, M., Calauzènes, C., and Fercoq, O. Im- proved optimistic algorithms for logistic bandits. In In- ternational Conference Machine Learning, pp. 3052- 3060. PMLR, 2020.
Amani, S. and Thrampoulidis, C. Ucb-based algorithms for multinomial logistic regression bandits. Advances in Neural Information Processing Systems, 14:2913-29244 2021.
Faury, L., Abeille, M., Jun, K.-S,, and Calauzènes, C. Jointly efficient and optimal algorithms for logistic bandits. In
10

---

Combinatorial Reinforcement Learning with Preference Feedback
International Conference on Artificial Intelligence and Statistics, pp. 546-580. PMLR, 2022.
Kong, D., Salakhutdinov, R., Wang, R., and Yang. L. F. Online sub-sampling for reinforcement learning with general function approximation. arXiv preprint arXiv:2106.07200 2021.
Filippi, S., Cappé, O., Garivier, A., and Szepesvári, C. Para- metric bandits: The generalized linear case. In Proceed- ings of the 23rd International Conference on Neural In- formation Processing Systems Volume NIPS' 10, pp. 586-594, Red Hook, NY, USA, 2010. Curran Associates Inc.
Kveton, B., Szepesvari, C.,, Wen, Z.., and Ashkan, A. Cas- cading bandits: Learning to rank in the cascade model. In International conference on machine learning, pp. 767- 776. PMLR, 2015a.
Foster, D. J., Kakade, S. M., Qian, J., and Rakhlin, A. The statistical complexity of interactive decision mak- ing. arXiv preprint 1111::211..13487, 2021.
Kveton, B., Wen, Z., Ashkan, A., and Szepesvari, C. Com- binatorial cascading bandits. Advances in Neural Infor- mation Processing Systems, 28, 2015b.
Lattimore, T. and Hutter, M. Pac bounds for discounted mdps. In Algorithmic Learning Theory: 23rd Interna- tional Conference, ALT 2012, Lyon, France, October 29- dynamics aggregation framework. In The Twelfth Inter- national Conference on Learning Representations, 2023.
Gheshlaghi Azar, M., Munos, R., and Kappen, H. J. Mini- max pac bounds the sample complexity of reinforce- ment learning with generative model. Machine learning, 91:325-344 1195--3992000 2013.
31, 2012. Proceedings 23, pp. 320-334. Springer, 2012.
Lee, J. and Oh, M.-h. Demystifying linear mdps and novel
He, J., Ostendorf, M., He, X., Chen, J., Gao, J., Li, L., and Deng, L. Deep reinforcement learning with a combina- torial action space for predicting popular reddit threads. arXiv preprint arXiv: /606. 03666 2016.
Lee, J. and Oh, M.-h. Nearly minimax optimal regret for multinomial logistic bandit. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
le, E., Jain, V., Wang, J., Narvekar, S., Agarwal, R., Wu, R., Cheng, H.-T., Chandra, T., and Boutilier, C. Slateq: A tractable decomposition for reinforcement learning with recommendation sets. In Proceedings of the Twenty- Eighth International Joint Conference on Artificial In- felligence, IJCAI-19, pp. 2592-2599, 2019.
Li, S., Lattimore, T., and Szepesvári, C. Online learning rank with features. In International Conference on Machine Learning, pp. 3856-3865. PMLR, 2019.
Ishfaq, H., Cui, Q. Nguyen, V., Ayoub, A., Yang. Z., Wang, Z., Precup, D., and Yang. L. Randomized exploration in reinforcement learning with general value function approximation. International Conference on Muchine Learning, volume 139. pp. 4607-4616. PMLR, 2021.
McFadden, D. Modelling the choice of residential location. 1977.
McInerney, J., Brost, B., Chandar, P., Mehrotra, R., and Carterette, B. Counterfactual evaluation of slate recom- mendations with sequential reward interactions. In Pro- ceedings of the 26th ACM SIGKDD International Con- ference Knowledge Discovery & DDta Mining, pp. 1779-1788, 2020.
Jinng N., Krishnamurthy, A., Agarwal, A., Langford, J., and Schapire, R. E. Contextual decision processes with low bellman rank are pac-learnable. In International Con- ference on Machine Learning, pp. 1704-1713. PMLR, 2017.
Metz, L., Ibarz, J., Jaitly, N., and Davidson, J. Discrete sequential prediction of continuous actions for deep rl. arXiv preprint 17Xiv:7705.05000 2017.
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. Is q-learning provably efficient? In Advances in Neural Information Processing Systems, volume 31, pp. 4868- 4878, 2018
Mhammedi, Z., Koolen, W. M., and Van Erven, T. Lipschitz adaptivity with multiple learning rates in online learn- ing. In Conference on Learning Theory, pp. 2490-2511. PMLR, 2019.
Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. Provably efficient reinforeement learning with linear function ap- proximation. In Conference on Learning Theory, pp- 2137-2143. PMLR, 2020.
Oh, M.-h. and Iyengar, G. Thompson sampling for multi- nomial logit contextual bandits. Advances in Neural Information Processing Systems, 32, 2019.
Jin, C., Liu, Q., and Miryoosefi, S. Bellman eluder di- mension: New rich classes of problems, and sample- efficient algorithms. Advances in neural information processing systems, 34:13406-1341 2021.
Oh, M.-h. and Iyengar, G. Multinomial logit contextual bandits: Provable optimality and practicality. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 9205-9213, 2021.

---

Combinatorial Reinforcement Learning with Preference Feedback
Orabona, F. A modern introduction online learning. arXiv 2019.
Vlassis, N., Chandrashekar, A., Amat, F,, and Kallus, N. Control variates for slate off-policy evaluation. Ad- vances in Neural Information Processing Systems, 34: 3667-3679, 2021.
preprint
Ouyang, L., Wu, J., Jiang, X., Almeida, D., Wainwright, C., Mishkin, P., Zhang, C., Agarwal, S., Slama, K., Ray, A., et al. Training language models to follow instructions with human feedback. Advances in neural information processing systems, 35:27730-277444 2022.
Wang. R., Salakhutdinov, R. R., and Yang, L. Reinforce- ment learning with general value function approximation: Provably efficient approach via bounded eluder dimen- sion. Advances in Neural Information Processing Sys- lems, 33, 2020.
Perivier, N. and Goyal, V. Dynamic pricing and assortment under a contextual mnl demand. Advances Neural Information Processing Systems, 35:3461-3474, 2022.
Wang, Y., Wang. R., Du, S.S. and Krishnamurthy, A. Op- timism in reinforcement learning with generalized lin- ear function approximation. In International Confer- ence on Learning Representations, 2021. URL https: / //openreview. meeefoorumiddCCCee /ttp:/mmmmddccm/////eppp
Rusmevichientong, P., Shen, Z.-J. M., and Shmoys, D. B. Dynamic assortment optimization with a multinomial logit choice model and capacity constraint. Operations research, 1866):6666-1688 2010.
Wirth, C., Akrour, R., Neumann, G., and Fürnkranz, J. A survey of preference-hased reinforcement learning meth- ods. Journal of Machine Learning Research, 18(136): 1-46, 2017.
Russo, D. and Van Roy. B. Eluder dimension and the sample complexity of optimistic exploration. In Advances in Neural Information Processing Systems, pp. 2256-2264, 2013.
Yang. L. and Wang, M. Sample-optimal parametric q- learning using linearly additive features. In Interma- tional Conference on Machine Learning, pp. 6995-7004. PMLR, 2019.
Ryu, M., Chow, Y., Anderson, R., Tjandraatmadja, C., and Boutilier, C. Caql: Continuous action q-learning. arXiv 2019.
preprint
Zhan, W., Uehara, M., Kallus, N., Lee, J. D., and Sun, W. Provable offline preference-based reinforcement learning. arXiv preprint arXiv:2305. 2023.
Saha, A., Pacchiano, A., and Lee, J. Dueling rl: Reinforce- ment learning with trajectory preferences. In Interna- tional Conference on Artificial Intelligence and Statistics, pp. 6263-6262222 6289. PMLR, 2023.
Zhang. Y.-J. and Sugiyama, M. Online (multinomial) logis- tic bandit: Improved regret and constant computation cost. Advances in Neural Information Processing Systems, 36, 2024.
Sauré, D. and Zeevi, A. Optimal dynamic assortment plan- ning with demand learning. Manufacturing & Service Operations Management, 15(3):387 2013.
Zhao, H., He, J., and Gu, Q. A nearly optimal and low-switching algorithm for reinforcement learning with general function approximation. arXiv preprint arXiv:2311. 2023.
Sunehag, P., Evans, R., Dulac-Arnold, G., Zwols, Y., Visentin, D., and Coppin, B. Deep reinforcement learn- ing with attention for slate markov decision processes with high-dimensional states and actions. arXiv preprinl 1rXiv:1512.01124, 2015.
Zhou, D., Gu, Q., and Szepesvari, C. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference Learning Theory, pp. 4532-4555 4576. PMLR, 2021a.
Swaminathan, A., Krishnamurthy, A., Agarwal, A., Dudik, M., Langford, J., Jose, D., and Zitouni, I. Off-policy evaluation for slate recommendation. Advances in Neural Information Processing Systems, 30, 2017.
Zhou, D., He, J., and Gu, Q. Provably efficient reinforce- ment learning for discounted mdps with feature mapping. In International Conference on Machine Learning, pp. 12793-12802. PMLR, 2021b.
Tran-Dinh Q., Li, Y.-H., and Cevher, V. Composite convex minimization involving self-concordant-liie cost func- tions. In Modelling, Computation and Optimization in Information Systems and Management Sciences: Proceed- ings of the 3rd International Conference on Modelling, Computation and Optimization in Information Systems and Management Sciences-MCC 2015-Part I, pp. 155- 168. Springer, 2015.
Zhu, B., Jordan, M., and Jiao, Principled reinforcement learning with human feedback from pairwise k-wise comparisons. In International Conference Machine Learning, pp. 43037-43067. PMLR, 2023.
12

---

Combinatorial Reinforcement Learning with Preference Feedback
Appendix
A. Illustrative Explanation for Combinatorial RL with Preference Feedback
Items
Items
Items
A
State
State 1
State 2
3
4
4
5
Receive a reward and Transition to the next state.
A is offered to the user.
chosen by user.
Figure A.1: Illustration of combinatorial RL with preference feedback.
In this section, we provide additional explanation of our framework, combinatorial RI with preference feedback, for better clarity. In this framework, at each episode, as a user arrives the system (starting the initial state, e.g., high loyalty), learning agent selects assortment A (a of items) and offers it the user (the first figure in Figure A. The user then chooses item from the assortment A (the second figure in Figure A.1). The agent receives reward, along with preference (or choice) feedback, and transitions to the next state (e.g., lower loyalty) (the last figure in Figure A. This process repeats until the episode concludes.
The key advantage of this framework its ability to capture the long-term value choosing an item by considering state transitions and avoiding myopic decisions. For instance, in Figure 1, a user may choose a junk item that provides high immediate reward. However, repeatedly recommending such items can lead to user fatigue, resulting in transition state of lower satisfaction loyalty to the system, ultimately leading lower cumulative reward.
We compare our framework with other related works.
vs MNL bandits. Our framework can be considered as a multi-step extension of MNL bandits (Rusmevichientong et al., 2010; Sauré & Zeevi, 2013; Agrawal al., 2017; 2019; Oh & Iyengar, 2019; 2021; Perivier & Goyal, 2022; Agrawal et al., 2023; Zhang & Sugiyama, 2024; Lee & Oh, 2024). In MNL bandits, there are no state transitions; thus, Figure F.1, the user exits the system immediately after receiving a reward.
Another important difference is that, in MNL bandits, the value (reward) of choosing an item is assumed to be known, and the value of choosing the outside option ag is always assumed to be zero. In contrast, in our framework, the value of choosing an item is unknown due to the stochastic nature of rewards and transition probabilities. Additionally, we allow the value choosing the outside option Ag to be non-zero.
vs Cascading RL. In cascading RL (Du et al., 2024), the agent also selects a set of items, and state transitions are taken into account when making decisions. However, these items are offered to the user one by one, and the user decides whether to choose the currently offered item.
Cascading RL fundamentally differs from our framework because the user does not compare multiple items at once, so it does not involve relative preference feedback. Another key distinction is that in cascading RI., the probability of choosing each item is independent of the others in the chosen set of items In contrast, in our MNL preference model, the choice probability of an item is influenced by the other items in the assortment.
vs PbRL.. preference- based RI. (PhRI.) (Akrour et al., 2012; Wirth al., 2017; Christiano al., 2017; Ouyang et al.,
13

---

Combinatorial Reinforcement Learning with Preference Feedback
2022; Saha al., 2023; Zhu et al., 2023; Zhan al., 2023), the agent learns from explicit numerical rewards, but through preferences feedback. The user is presented with two (or sometimes multiple) items and chooses a preferred one.
In our framework, if we treat the reward signal generated by the user's choice as preference signal instead of a numerical reward, we can learn the policy based on user preferences, similar to PbRL, without relying on explicit rewards. However, our framework differs fundamentally from PbRL. because our goal is not just to offer a single item, but multiple items-a combinatorial (base) action-at each timestep.
B. Efficient Bonus Oracle B using Online-subsampling
The guarantees of Algorithm rely on consistent bonus oracle, B, that satisfies Definition B.1.
Definition B.1 (Oracle B, Agarwal et 2023). For any (h, [H]] x [K], sequence of (
[-] and dataset
D ((5) o The )) function class Fn with fn E Fh. 3n. > 0, error parameter ea > 0, the bonus or-
acle B(1og)==1 D Fr, fh. Bh. p. Eb) outputs a bonus function bx(-) such that, for any 2h (sh, as) 8 I, we have
. bn: : S x I R2 belongs to bonus function class W and denote No [W]-
bn(2n) 2 max (In(le)) - fa(z))..
Σ (ot)² (In(TT) fk(=z)) & =BBW))
bb(zn) & C. Drn Canit (0))=1)) V 2 eb 3n with 0 < 0 00.
+
Further we say the oracle is consistent if for any < k with consistent [,x s [o K- D = D 3h non-decreasing in l for each h [H] and ftt as defined in (3), it holds that (( D F P. 3 B((0T) DK Fr, fk Ph p. ta) element-wise.
DD
With the oracle B, we can efficiently calculate the optimistic Q-value estimate fh with an error of eb-
To implement this oracle, we use the online sensitivity sub-sampling approach described by Agarwal et al. (2023), which builds on the original sensitivity sub-sampling method proposed by Kong et al. (2021) and Wang et al. (2020).
For completeness, we include the sub-sampling procedure in Algorithm B.1 and show its guarantees Proposition B.3. Let (s S x I. We first define the weighted data set 2, where each element is (z, (2)), and introduce the weighted sensitivity score as follows:
गे (f(z))f(22)
sensitivity min
sup f.f'FF min
K(#+1) Evez (ج(2) (f(*)-f(()))
w + 72
Now we introduce the sub-sampling procedure.
Algorithm B.1 Online Sensitivity Sub-sampling with Weights
1: Inputs: function class F, current sub-sampled dataset 2 = S x I, new state-action pair 8, a, parameter 7, threshold
v > 0, failure probability
2: Parameter: 1 & C' < oc
3: Let pz be the smallest real number such that
1/pa is an integer and p. min ( C, sensitivity 2 (z) log(KN/8))
4: Independently add l/p, copies of (z, (2)) into 2 with probability Ps.
5: Return: 2.
14

---

Combinatorial Reinforcement Learning with Preference Feedback
For the weighted dataset _/-1_ ((0h) Wi we defined |/ -/- Ex नोz (2)) i.e., weighted sum
of 42-ormm square. We denote 2 as the dataset sub-sampled from 2/-1 At every hk, [K] [H], we call
Algorithm B.1 with the current sub-sampled dataset _/-1 and the new state action-pair 2 (s a generate the next sub-sampled dataset 2
The following proposition shows that the distance any two functions measured by the historical dataset 2 is well approximated by the subsamping dataset 2 Additionally, it shows that both the number of distinct elements in 12 and its the total size (counting repetitions) do not scale with poly(S).
Proposition B.2 (Guarantees of online sensitivity sub-sampling, Proposition 13 of Agarwal et al. 2023). Let z = (8, I. When (z) e V for any 2, then with probability at least 6, it holds that
sup Ji.hi:1/ - fal z/ Er
- ((a))-f(=)1
sup fi-fi: f1 - fall z/ $002,3
[f((2) - f2(2)]
sup 5.56:
- [2(=)|-
100 2
Further, for any (k, E [K] x [H], the number of distinct elements in sub-sampled dataset 2 is always bounded by d [ma dim,, , (Fi) and the total size of 2), is bounded by O(K3/8)
O (log KN...
We can assert that the predictive differences between the functions are preserved up to constant factors, while requiring significantly less data. Then, the size of the bonus class W in Definition B.1 is bounded follows:
Proposition B.3 (Implementing B using maline-subsampiigg Corollary 14 of Agarwal al. 2023). There exists algorithm (see Algorithm B. such that, with probability at least 1 8, implements consistent bonus oracle B with eb for all (k, h) E [K] x [H]. where
KN 5
K|S x Z 8
log W| & 0 max dim,, (Fr) log he(m]
log
C. Efficient combinatorial optimization
In this section, we explain how to solve the combinatorial optimization problem in (8), following the method outlined in Davis et al. (2013); le et al. (2019).
To find an assortment AA that maximizes the optimistic Q-value, a fundamental step in Q-learning and crucial for inducing exploration, we must solve the following combinatorial optimization problem:
max ΛEA
Σ
Ph (alsh A)Jk, (sh,
(C.1)
ASA
where Ph. the optimistic choice probability as defined in (7) (also in (D.17)), and fh, is the Q-value estimate (item-level Q-values) defined in (D.15).
Fix (k:, 8. E
[K] x [H] x S (1, 21,2.-2). For simplicity, we will abbreviate these indices. Accordingly, we denote
wa = exp (D a)) or wa = exp (s) a)), depending on the value of j. Additionally, let fa = fk fh. (sh, a) for
simplicity.
We can then express the optimization problem in (C.1) in terms of w as fractional mixed-integer program (MIP), with binary variables Fa {0, 13 for each item E I I{fao) indicating whether is included in the assortment A:
WapSoo + EnETy Fa waJa
max
(C.2)
Wao + EneE Wa
s.t.
Σ
La < M-
aEI((fa))
Ta {0, 1}, Va Iifao)
15

---

Combinatorial Reinforcement Learning with Preference Feedback
By Chen & Hausman (2000), the binary indicator in the MIP can be relaxed, resulting in the following fractional linear program (LP):
Way fao + LaEDitout Fa Fa
max
(C.3)
Wao
Lo'ED Mao) Zd Wa!Waa Wa
Σ La & - 1;
S.t.
0 & Fa & 1, Va E D(foo).
Since this relaxed problem is fractional linear program (LPP, using the Charnes-Coopel method (Cooper et al., 1962), can be transformed into (non-fractional) LP. To achieve this, we introduce additional variables:
Ja
Ya
Woo + La'eIitao Tel Wa!
Wao + Lo'EIitou) Lad We
Then, we can obtain the following LP:
max
Σ aEIiaa)
fawala+ + Sag Waok
(C.4)
s.t.
Σ
Walla wao 1;
aEZ)(ao}
Σ aEZ)(ao)
Ya & (M - 1)t; 130 0.
The optimal solution (Vaz :.... Vag, to this LP (C.4) provides the optimal 2; values for the fractional LP in (C.3) by setting xa = Va/t". This, ture, determines the optimal assortment in the original fractional MIP (Equation (C.2)) by including any item where va Thus, the optimization problem is proven to be solvable in polynomial time.
D. Proof of Theorem 5.1
D.1. Notations and Preliminaries
In this subsection, for easy reference, we introduce notations and definitions used throughout the proof. The key notations are summarized in Table D.I, and the specific parameter choices are listed in Table D.2.
Online parameter update and confidence interval for MNL preference model. We define the multinomial logistic loss function at (ks, h) [K] [H] follows:
(0)
Σ (a( log (alss A 0)-
(D.1)
To achieve constant-time parameter estimation, the online mirror descent algorithm estimate the true parameter 0
k++1 E argmin V
0
where θ {0 E dRd |00| & B}.
(D.2)
0e
2m
where 7 = log( M + 1) + B + is the step-size parameter, and the related matrices are defined as:
H : XL + Σ v ,
i H (
(D.3)
where
22r)(0) = Σ Pa A 0))(() a) () T)
oE
Σ Σ P 45. A1oss
AE d'EAK
16

---

Combinatorial Reinforcement Learning with Preference Feedback
Table D.I: Summary of notations
Notation
Meaning
Remark
S,A,I
state space, action (assortment) space, item set & [K] episode, [# 1] horizon
k
r 8/: A/ an
reward, state, action item at k, random reward, state, action and item shorthand for state-item pair (8, item-level Q-value function
8h. Ab,
Q:5 I
Th, T
Bellman operator and accond-moment operator
D
data (6% o The 1
Fb
function class for horizon E [H]
Ass. 3.3
linear function class for horizon & E [H]
Eqn. E.1
(ee)
ec-Cver of linear function class Fili
W
bonus function class defined for bonus oracle error paremeter for bonus oracle
Def. B.1
cb
N
maximal size of function class, i.c., maXKE(H] (Fa
No
size of bonus function class [W]
D& (1
sup f. Se-l to (=(==")/a(=="))) generalized Eluder dimension defined in Definition 3.5
param.
dim,, (F) d,
param.
"iI dim,, (Fi,) (Definition 3.5)
param.
(0)
Emeea (a) log Pa [s, A 0), loss for MNL model at k
Eqn. D.1
H Hi
AL Σ!=l (egg(05+)) - H& 1)V respectively confidence interval for MNL model at k. optimistic Q k,
Eqn.
ch
Eqn. D.5
fha
fla
solution of fitting weighted regression at k version space of optimistic Q at k overly optimistic (pessimistic) Q at k solution of fitting unweighted regression at kt version space of overly optimistic (pessimistic) Q at k.
Eqn. D.7
Fka
Eqn. D.8
Eqn. D.11
Fh
Eqn. D.12
solution of fitting second-moment regression at k;
Eqn. D.13
version space of second-momen estimates k, event that {0; E Cg for all Is > and all h [H]] 1 E Fky for j 1, 12 and T E Gk
Eqn. D.14
g
E Egk (h
event that (Tr V
Ass. 3.3
joint event that n N Eg
( (s A)
optimistic (pessimistic) utility defined in (6)
optimistic choice probability defined in (7)
(s,
Eacs Phi, (a|s, A)SK, (s. a) for #2
= max AEA Qh (s, A) for 1,
argmax AEA Emea Ph. (al A)fk,(sh a) for j 1,12
AK 0f A), (s)
chosen assortment at k, le by assortment selection rule in (9) realized optimistic values determined by (D.18)
Eqn. 9
ha Ko, Kin bhi is aft, V-1-1s s all Er.- AN
random when first taking action A
i.e.. A = Af.2
Eqn.
disjoint subsets of [K] when lts H + 1 or lu E [H]] bonus term obtained in Line and 11 using B
Eqn. 9
Def. B.1
Bay. (elff at [l of V P
Bay Ph Gllg |s A
17

---

Combinatorial Reinforcement Learning with Preference Feedback
Table D.2: Summary of parameter choices
Notation
Choice
Remark
E (0, 1/ 15))
8%
((K + 1) + 1))
n
$ + + step-size parameter for OMD
Eqn. D.2
84 regularization parameter
oi
O(vālog log M) confidence radius of Cj error due to taking covering of function class
Eqn. D.6
cc
V VI/KH
Def. 3.5
p
Def. 3.5
o(d)
V log N2 (ogg(811)))1113
((6)
3/ log NA (8100(())))))))
N DX SLB 2) 34 +2)
(6/p+ 156) log
confidence radius of FX
Eqn. D.8
((6)
log (
2(21 21)(( confidence radius of Fk
2:
Eqn. D.12
(6)
2lg (2 + (2
/8(11L ()))( confidence radius of G.
Eqn. D.14
min {1. (=h) (jh,
(oh)²
Eqn.
(V + 2 (sh.2) + P
D23 (shi (=1) 1 111)
max oh u, v2.())) / 1/2 2(2h),
0%
2 (O(OR)) + ((%)) v Das (2ft: (2 |-اn (
Eqn. D.7
Viog (
C.
NKH [log
NNKH 0b
1 /dd + v vkHeo)
+d log K log M / llg NNKH vb
/Vk C>0
Eqn. 9
By standard online mirror descent formulation (Orabona, 2019), (D.2) be solved using single projected gradient step through the following equivalent formula:
0 0%
(iTh)
(e) and
0 argmin 0 0 ing Aee
(D.4)
which enjoys computational cost of only O(Md)), completely independent of & (Mhammedi et al., 2019; Zhang & Sugiyama, 2024; Lee & Oh, 2024).
We define the confidence interval at (k, h)
[K] x [H] as follows:
ch 00 :
0% o & <ai)
(D.5)
18

---

Combinatorial Reinforcement Learning with Preference Feedback
where the radius of the confidence interval C% is follows:
2v 2k
7
k +
+1
c Oh
21y 11 (3 [og(11 + (M + 1)k) + B + 2) log
+ 2
dn log 11
+
+ 4XB2
5
6
21
(D.6)
Then, we define the optimistic and pessimistic utility follows:
(s, == ((s a) o af)l ", (x(s,a)==((5)
afild(s, ())( 4
Regression and confidence intervals for item-level functions. In this paper, we define N == max [Fa] as the maximum size of the function classes Fi..... FF and N₁ | as the size of the bonus function class W.
For all (k. h) E [k] x [ the weighted regression problem for fitting the optimistic item-level Q-functions, Q. along with the version space of these functions, is defined as:
1h.11 E argmin JuEFb
(fh(sh, - V. (htt,
(D.7)
(o7)
(fu(sh, (R) - -h o7)) < (sh. ) }3. 5.
F = fnE
E
Σ (
(D.8)
Let 2x = (5%) a.. The parameters are as follows (for ls > 2):
(o²)² = min 4, gh(2hh - (f%-2((7t)
(17)tt) (V(B)) + +p+ (Bha)) +P)
+ Dr, (=hi [2 (
(D.9)
; = max { (ohi 22(t)) (+)) fr. 2
2 Vo(ot) + ((6%) ) v D (2h) (
(-)))
(D.10)
4LK N²(K + 1)(H + 1)(2 log
+ 2)og / + 2)
8h = V (6VD p 156) log
v
8
(22 + 2) (log(8L/vv3 + +
5
o(8))
log
8% =
5
(K + 1) + +)
(VNG(21og(4LK//) + 2) (log(811/))) +
(6)) 8, log
g/
For all h) [K] [M]. the unweighted regression for fitting overly optimistic and overly pessimistic item-level Q-functions, along with the version space of them, is defined as follows:
f E argmin JNEF
(fn(sT, ah) - r V. (8h+))(
(D.11)
k-1
Fk = fn E E Fr
(ra(sh.a7) ah) Phise(5h
07) (Bh {
(D.12)
19

---

Combinatorial Reinforcement Learning with Preference Feedback
We choose the parameters as follows:
Bh = 22(2AL+ +1)
(2 + ()og(( + 2)
((8)) = 12 /2 log
6% = (K + 1)(H + 1)
0%
For all (k: h) E [K] x [M] the unweighted regression for fitting second-moment function values to item-level Q-functions, and their version space, as follows:
5% E argmin
Σ
(g(( (5) (1% +
(D.13)
ShEJn
k-1
gh = In E Fr
Σ
(0n(sh a7) - gh(s a))) $ (3h)²
(D.14)
We choose the parameters as follows:
3 V 8(11L + ())))))))
(3 2)ogg(321.) + 2)
((5)) = 2lo
ox = (K H)
Given the center of the constructed confidence intervals, fhi for j 1, =2, we define the optimistic, overly optimistic, and overly pessimistic Q-values as follows:
Sh,( min (fh1(.-) + 1b.1 (1:),,
sh,((,:) == min (faal:-) + 1t, + 22 - (k2))))))))
sh =- max
(D.15)
Good events. We define the following good events:
g {Ak 1, Vh E [H] 0% Ck).
(D.16)
εg n 1 |
ok
3 Eh. c - 2 n Ek.
where Ehi = VaVii h FFi for = 12 and ह V h+1,1 E 9%
Optimistic Q-values. For (k, h 8, A) E [K] x [ll x S x A and for j = 1, 22, we define the optimistic choice probability as follows:
exp (s) a))
if E IMfool s.t. Shi(s,, a) > (t,
Ewee exp (o) (s)
Pk (al, ==
(D.17)
exp (oh(s,
otherwise,
En's exp (5 (s)))))
where
(=) T + at (is a) (m)),, a=) a(s,a)T0) (illo(s,a)((m))))
Next, we define the optimistic Q-values for j = 1, +2, each constructed using fh, and pi:j:
(s, A) Σ A) Vht(() max 2 A).
AeA
20

---

Combinatorial Reinforcement Learning with Preference Feedback
For convenience, we also define the realized optimistic value functions (k, [K] [H] as follows:
(s, A) = Q () if A (%,2(,,)) A) otherwise,
= A
Vi((s) max (s A), AEA
(D.18)
where A is the assortment offered to the user by the assortment selection rule in (9) (or equivalently in (D.19)). Therefore, we write x (s)) argmax Ae 2% (s%, A).
Design of exploration policy. At each episode k. the agent collects data using both Ai,1 and A where Ah, argmaX ie Ph Pb, (als; A) fh, ($h. a) for j = 1, Given sequence of pre-specified {ux) k- at episode k, the agent select an assortment based on the following rule:
A
(5h an) (w)> > fh 2 aw) - us VaN A, Vh' & h.
1/
(D.19)
A f.
otherwise,
where
Vlog
log
NKH. 0b
(log NAAKH. 2b
1 Vd vkHles) + d.1 log K log M My Vlog
NAAKH 4b
Uk =
(D.20)
Vk
We denote h& [H+1] + 1] the (random) horizon at which the agent first begins offering the assortment A More formally, for l & hg. the assortment offered is A A and for h > hg, the assortment offered A A/. We then divide the set of episodes [K] into disjoint subsets: K. and Kon, such that
K. (k E [K] h4 H 1}, and Kn :- (k E [K] he H}.
Later in the proof, we separately bound the regret for each case.
as, 24 (sn, an) and a (s% at) interchangeably. We sometimes use Pr(--s A; (0)) instead of Pa ls, A) to explicitly indicate the dependence on the parameter 0₁ For simplicity, we denote 15 1--1-16 / off] E.,, ~ Pal at) 1 l. Vrl-is afl = V V (tlo a 1s afl. and Eplis A
Other notations. Throughout the proof,
[1 [ A
D.2. Confidence Intervals and good events
In this subsection, we show that, given the construction confidence intervals C and Fhi for j 1, =2, the good events 0 and EgK occurs with high probability.
Proposition D.1 (Online parameter confidence interval, Lemma of Lee & Oh 2024). Letd (0, 1). Under Assumption 3.1, for the confidence interval defined (2) with
2v1 + 2k
7V6
1: ++ 1+
aft = 1
2n 11 (1- (3log(1 + (M + 1)k) + B + log
+ 2 +
dn log
+2 + 4AB²
8
6
21
12v1+ + 2k ))
7vO
k + 1
1/2
16 log
dn log
1
+2
XB2
8
2
= O(Vdlog dog ls log M).
n
log(M [M + 1) B and À 84v 2dn, and for any E [H], we have
Pr[vk > 1, 1 E ch1 > 1 - 5.
Now, we define the good event for the preference model 8 as follows:
80
(Vk > 1, Wh [M] 0ī C.)
Then, by applying proposition D.1 and using union bound over E [H], we obtain the following corollary:
21

---

Combinatorial Reinforcement Learning with Preference Feedback
Corollary D.2 (Good event for MNL preference model). Under the same assumption and settings as in Proposition D.I, for 8 (0, 1), with probability at least 6, the good event for the preference model & happens, i.e,, 0% C%2, for all k ž 1 and all h [.].
The following proposition shows that T% V. h+1.j for j 12, and TR 7V1,,,, h+1,1 lie within their respective confidence intervals.
Proposition D.3 (Good event for general functions, Proposition 33 of Agarwal et al. 2023), Suppose Algorithm 1 uses a consistent bonus oracle satisfying Definition B.I. Let ō E 1/5). Then, with probability at least 55, the good event Egg 1- N Eh happens, that is, Th h+1,1 Fh., To To h+1,12 E F and T h+1,1 9 for all
hk, E [K] [H].
D.3. Bound for MNL Preference Model
In this subsection, provide proofs for several properties of the MNL preference model.
The following lemma presents both the optimistic and pessimistic utilities.
Lemma D.4. For any (k. h s, [K] [H] S I, let oyf as) a) = 6(s, a) T a (l)) and (5,
o(s, a) 0% - af a)l (Ht) Under the good event 8d defined in (D.16), it holds that
< (s, - o(s a) 0f & 2o (H)) and < a(s,)) 0 - (s, a) & 20 (H:) 1.
Proof of Lemma D.4. Conditioning the good event 3 holds, we have
(o(s, a) 0% - ő(s, a) 0% < | a) (H:) | - 0illeny < a lō(s, ()(s,
where the first inequality holds by Hölder's inequality, and the last inequality holds by Corollary D.2. Therefore, it follows that
(s, - ((8,a) TO o(s a) 0 a(s,a) 0% + alllo(s, (H+)
((Ht))
2a lø(s, a))l (HH))
Furthermore, since a) To)T 0h a(s,a) 00 > - 10 ( we also get
(> a) 0 al 0 oss a) 0 (hll 2 0.
The second statement directly follows from the results mentioned above.
Lemma D.5 useful for proving optimism (Lemma D.15) and bounding the approximation error of the optimistic Q (Lemma D.20).
Lemma D.5. For all (k, h s, A) [K] x [H] x S x A and any j e {1,2), under the good event 0 defined in (D.16),
there exists a subset A A such that A E and
Σ aeA
Phy A) A)lls (),)
Rh EPh A1)
max
ae
ae
where je # j.
Proof of Lemma D.5. First, recall that, without loss of generality, we assumed that Φ(s, an) for s Therefore,
22

---

Combinatorial Reinforcement Learning with Preference Feedback the true preference model and the optimistic preference model be written
exp (é(s,a)T6)
Pa(als, A) 1+ E L'E exp
exp (v)(8, a))
if 3a IMtoo s.t. (s, 2 (h
M(o)) exp 0 a2)
Ph A))
(D.21)
exp (1) a
otherwise.
+ ((oo) exp (*)
Fix S and AE A. We now present the proof by considering cases: (1) (s, > (s, for all a a and (ii) 3a A such that (s, ao) < (s,))
Case (i) fhis (s, au) (s, a) for all a A. denote à ar AMao) (5, a). Let À = {ao, ā}. Since ( ao) > (s, a) for all a e A and dg always included in A, removing any item e AMooo) from A increases the expected value of fh.. Thus, we get
Σ
(s, &
Σ P) A),h
and
Σ p n.y (als,
(als,
(8, & A),h
Σ ph (als, A) (
(D.22)
DEA
By the definition of Phyy in (7), we use the pessimistic utility (8, a) this case. Since (x, & ((x, To by Lemma D.4, using this utility, Th,s, a), reduces the probability of selecting à (compared to the true choice probability P.)).
Moreover, we know that 1/ (s, oo) > [8 ā), we have
Σ ( a
A)5h (s, Σ Phy (s.aa.
(D.23)
asA
Furthermore, if h.j is constructed using the pessimistic utility ( a). then, Ph.y Ph.s However, if Ph is constructed using the optimistic utility (s, a), replacing 0h a) with (s, a) (which is equivalent to replacing hij' with Ph,y ) decreases the probability of choosing a, meaning increase the expected value of fh.s Thus, we get
Σ
(ala A) & Σ (ay () (s,k)
(D.24)
A
A
Combining (D.22), (D.23), and (D.24), we have
max Σ
Pr(als, a), Σ (aly
EPh (),,,()))
aed
Case (ii) 3a A'ffau) such that (s, & Sh (s.
Let Å A's A: Jh, > (s, ao). Va E A') Note that |Å| > 2 and ao E Å by definition of action space A. By selecting À instead of A, we exclude items with the small values of fh. (8,a). a), thereby increasing the expected value of fh.j i...
Σ A)th & Σ Pn(als, (s.a)
a
and
Σ
Ph (als,
A)Sk ()) & Σ (als, (
(D.25)
06 A
aeA
By the definition of Ph. in (7), we use the optimistic utility (5 a) in this case. Since a(s,a)Top 0z < 8)(s, a) by Lemma D.4, this choice of utility increases the probability of choosing item a * Al(ao) compared the true Ph). implying
23

---

Combinatorial Reinforcement Learning with Preference Feedback
that
Σ A) (s,a) & Σ (ass (s.))) (s,a). a
(D.26)
asA
Moreover, if Phi.. constructed using the pessimistic utility (s, a). replacing (s, a) with (s a) (which equivalent to replacing Pk A.g"" with Pk increases the probability of choosing item a # Al/oo. However, Pk the optimistic utility (s, a). have Ph.j Ph To this end, we weger get
hgy" is constructed using
Σ Phy (als A)Sk (8, & Σ
(D.27)
Combining (D.25), (D.26), and (D.27), we have
Σ
(hs ()th
max
..A
aEd
acA
This concludes the proof of Lemma D.5.
Denote J(k, h) {1,2) as the chosen index of function fl. at (k, h). Then, show that the value estimates for the chosen assortment, (h., (sh a) for all E A are greater than equal to En Pk
(.. A Ah. (k. a). Lemma D.6. For any (Re, h) [K] x [H]. let J(k, h)) K. [H] (1.2} be the one-to-one function that maps from K x [H] to the index set (1,2) such that A ((.,)) argmaX,e.t EaEd Ph
P., (a) s/ A) A) (8t, a). Then,
under the good event 0 defined in (D.16), we have
Jh. (s,, a)
Σ
Va A
aEA
Proof of Lemma D.6. By Lemma D.5, there exists a subset As A and A such that
Σ P A
Σ
Ph. (alshh 10.
Σ
Ph (h A (
where the second inequality holds the assortment selection rule. Thus, sufficient to show that sh. (5) a) Lne at (k, (alsh, A&) (h. (sh,a) a) for all E AK
Pkk
prove this by contradiction. Suppose there exists an item a E A such that
sh ( < Σ Ph. Jo
a
we remove item a from the assortment A it would result in higher value. This contradicts the optimality of A Hence, we conclude
Σ Ph. Ph. At)5h.
a
which completes the proof.
Lemma D.7 is an elliptical potential lemma used for bounding the regret incurred from the MNL preference model (Lemma D.10 and D.13).
24

---

Combinatorial Reinforcement Learning with Preference Feedback
Lemma D.7 (Elliptical potential lemma, Lemma E.2 and H.3 Lee & Oh 2024). Assume that 2 and o( an) ((s,
0 for
all E S. For any (k, ht a) E [K] x [H] x I, we define @ a) = $( a) - E PP ( A8:00 11 ( a)}. Then, for
Hy defined in (D.3), and any h E [H]. the following statements hold true:
Σ Σ 7-1 ae A
(.00 A Ph 11:
| 0) (1H)) & 2d
(1+
1+
A
dA
k
Σ Pa Ah
| h. a) ((HT)) & 2d
1
dd
1 aEA3
max
max dEA
16(5% a) (15)
max
106 a)l (11)))11 & -d
1 +
aEA
dd
Lemma D.8 used to derive the tight bound for the second-order regret term of the MNL preference model (LemmaD.13)
Lemma D.8 (Lemma E.3 of Lee & Oh 2024). Let M E Z+ Define R RRM - R. such that for any vo = (vi,..., UMM)
RM, R(v)= Im=1 I+ exp(v;)
M exp(Um)
Let Pm (v) I+ exp(w))
exp(Um)
Then, for all [M], we have
6²R Ōmdn
(p)
if m n, if +
2pm( (p)(()))(())
Lemma D.9 crucial for deriving the x-improved bound for the MNL preference model (LemmaD.13), enabling the analysis. Lemma D.9 (Overly optimistic choice probability). We define
exp (b((,))) u) 0 20 16 (1t)
if 3a Iitaot (h > fh.
En'es exp (') 0 + 20 (1)))) (11))-)
Bh (alsa
(D.28)
exp (0(s,)) 0 2 10 a)ll (HE)
otherwise.
Ewer exp
0 - 20 a')l (1))))))))))))))))))))
Let Ak, E argmax AEA Laes A Pha(alof A) (sh a), where j je (1,2). Then, under the good event for all (k. h. J)
[K] [H] x (1,2), we have
Σ QE A
(alsh Ah Σ (alsh A at A
Proof of Lemma D.9. Fix (k, j) E [K] x [M] [1,2]. We consider the two cases: (1) fh (sh ao) > fh (h a) for all E I and (ii) 3a Daao such that /hi (sf ao) & Jh. ())
Case (i) (st on) > (sh a) for all I.
Recall that, by the definition of Ph., in (7), use the pessimistic utility Ty (s. a) to construct Pk, in this case. Note that the outside option ag must be included in the assortment, i.e., 0g E A&. Moreover, under the event E² by Lemma D.4, we have
(s) a) > o(s),,) a) 0 - 2l a)ll (H:)
Thus, since we assume, without loss of generality, that o on) 0 (refer (D.21)), using Pi, instead of Pk, decreases the probability of choosing any item a E A/oo- As a result, the expected value of fhi increases, since (8, >
25

---

Combinatorial Reinforcement Learning with Preference Feedback
() for all A Formally, have
Σ
(ay fhy aEA
Σ
GEA
Case (ii) 3a E ]ffao} such that fhi (5 ao) & (h
1 fao); we have (hh 3 Eoest Phy(olsh, (h Suppose that there exists a Mao) for which (sh, a) Energ, Pho (h a). Then, removing item from the assortment A results in the increase in the expected value of fh.s Consequently, this contradicts the optimality of A Hence, we get
First, we show that for
(5h > Σ of AEA
Ah Va E Aaaa
On the other hand, recall that, by the definition of Ph, in (7), the pessimistic utility (f a) to construct Ph, in this case. Furthermore, by Lemma D.4, we know that (hh, a) & sssh TT, 0% + 2 a)ll a)) (Hz)
If we increase of a) to ( a) a)T, 8 20 ( a)l (H:: for all a A (ao), the probability of choosing the outside option decreases (because @ish an) = 0). In other words, the sum of probabilities of choosing a E A increases. Since (h.(6% a) >> EmEAt, (alsa (h, a) for all a A& Mao), the expected value of fh. increases. Formally, we get
Σ A
Ph (1, &
Σ aEAk
Phy (3,.))
This concludes the proof.
Lemma D.10 will be used to carefully bound the sum of by (Lemma D.23). Note that the following MNL bandit regret
improves upon the one proposed in (Oh Iyengar, 2021) by a factor of 1/vK, which can be exponentially large.
Lemma D.10 (Crude bound for MNL bandits). For any h [H], j {1, 2, 22] and subset K. [K], under the good event 8d defined in (D.16), we have
Σ
Σ
Ph (Ph
A
Ph(alsh, AlD) she (sh
<0 ( ddViK (log K) log M M),
keK.
where M is the maximum size of the assortment.
Proof of Lemma D.10. We denote Mj as the size of the assortment at horizon h in episode k i.e., Mt |A/] For any j [1,,, 2), we define a function Ry RR TRME R such that, for all v e RM,,, R2(w) IMA exp(mmn /5h,, (s%.
1- exp(ve)
For simplicity, we denote (s, a) as the utility, which can represent either the optimistic utility () a) or the pessimistic utility (H(s,,), a). determined by (7), depending on fh.." Let (+,)
(ut (vh,((th aEAA
E M and vg(s
(Ø(s), ()ish,aTTor T0)) a E MR, Then, by the mean value theorem, there exists vector oh (st)). which is a convex combination of u (5t) and vi (st), such that
Σ KEA
Σ A
Phy (alsh, A Ph(alsh.AAt) sh (hh
Ry (v (sh)) R2 (v)(1))
kek:
VR, ( (sh)) (ui w(())))
kgk
26

---

Combinatorial Reinforcement Learning with Preference Feedback
Therefore, we get
Σ kE
vR (o (8h (sh)) (sh) -
exp (hh
(sh: a)) Shi a)
Σ
EnTEAt exp (8h (uh (sh a) al 07))
kek: DEA
exp Tit (o a) (0 a) exp ( (ohh,(oth a²)
Σ
Σ
a') - a(
(iineay exp (0h (oh.(( a())
,EAR d'EA
Σ kek. DE
Σ
Ph (alsh, Ah: oh (sh)) ( - a) 0%)
pri a) - - Pa (+)) (5h a'))
2 Σ Σ Ph (alsh: Ah: oh (sh)) (s a) a)) 0%
(D.29)
kEA RE
where the inequality is from 1h.3 1. Recall that v ( a) can be either ( a) or (st a). Then, by Lemma D.4, we have [(o} (5h, a) - oish, a) 0% < 2a a) (m:)) 1. Hence, we can further bound the right- side of (D.29).
2 Σ Σ
Pa (als A ) (s:)) (u a) - Msh a)) 0%
kER as 1
4a
Σ Σ
Ph (al k A ot (+,)) (0 a) (H+)))
kE AEA,
4a K
ΣΣ
A2: ( (+)))
Σ Σ kek AE
Pu Pa(al sh, oh,
(x)) (5h 1)
(HH)) (Hz))
KE AE
< 4a VIKI
Σ | a)l ( (HA))
A
K
(alsf Ah; 02 1 Pa (aol s 0kt1
-4a%% VITT
Ph (a) f,. AB: (): PP (aol s Ah: 1)+1) (10( a)) (
aE At
K
4 VIK.
Σ
(alatt A4: 0% ")P ( ( a) a)l (1)))
K
A
1 V
K
< 4 V
od
1+
(D.30)
di
where the first inequality holds because af & ... & of the second inequality follows from the Cauchy-Schwand Schwarz inequality, the second-to-the last inequality holds due to the definition of k. and the last inequality holds by Lemma D.7.
Combining (D.29) and (D.30), and plugging in the value of at we derive that
Pk (h.s At) Pulalsh, Ph())sh.AAi) (sh a) = -0 dv I7
(log K)3/2 log M
kEK #5
27

---

Combinatorial Reinforcement Learning with Preference Feedback
Lemma D.11. For any (k, [K] [H]. 01, 02 E C% and ( e under the event 8 defined in (D.16), we have
Σ
Pa A 01) Pa(aas A 01) whi(a) 4afk max w((aa) max
llo(sh a) (1))
oEA rEA
Proof of Lemma D.II. By the mean value theorem, there exists & =1 --)0 + c02 for some DE (0, 1) such that
Σ
Ph Mh: 01) - Ph(alsh A2: (x)aa))((aa> - Σ
VPa(als 5) (0) 02)) (x(()
a
Σ
Paialsh 1) Ph(aas - 5) Σ Ph(a'Ish A (bshh)()h.o))) (0) - 02) wh(la)
A
d'eA
Σ Palalsø los T) (0: -2) 0 (+) + Σ
Pa () Σ Ph(a'Ish A (((s T0; -02)
at a
aEA
a'EA
2
Σ Pa A 4 ( a) 00ll + max REAR
max (a)
Σ
(als A E)0( a) (
aEA
4a max w (a) A
max aEA,
[ a) (
where the second-to-last inequality holds under the good event 8 defined in (D.16).
Lemma D.12 pertains to the law of total variance (Lattimore & Hutter, 2012; Gheshlaghi Azar et al., 2013) that the variance of the value function is smaller than its magnitude by factor VH.
Lemma D.12 (Total variance lemma, Lemma C.5 of Jin et al. 2018). Let fi.j E [0, 1J. Then, with probability at least 1 - 8, we have
K H Σ
Nvvassls)) O (K + H log(1/6)
Lemma D.13 is crucial for obtaining a k-independent regret in our leading term. While the proof largely inspired by Lee & Oh (2024), extending their result to setting is non-trivial because the unknown item values fh, add complexity to the analysis. Moreover, thanks to Lemma D.12, we can obtain tight bound by factor of v H, instead of naively summing over H MNL bandit regrets.
Lemma D.13 (k-immpooed bound for MNL bandits), For any subset K. [K], let J(k, h) K. x [M] [1.2] be the one-to-one function that maps from K. x [H] the index set {1.2} such that A A A a). argmax Eees Pk Ph.J(k.)gaasst ()..o.,salsts.AAff...... a). Then, under the good event 0 defined in (D.16), with probabil- ity at least 6, we have
H
Σ kER A
Σ
Dk Ph. A Ph(alsh. fh fh.Jean)(shh
o dv (dw HH K/ log M 1 (((a)
H(og K) K) (log (log M1)
M7²)
k
Proof of Lemma D.13. We begin by defining (als, A) as given in D.28. Then, by Lemma D.9, we have
Σ
Σ
Att - Palalsh Ah)) (sh
kEA h= 1
Σ E(P
(ah. A/ Pn Abi) sh.nae)(shh
kek. h-1 GEA
28

---

Combinatorial Reinforcement Learning with Preference Feedback
We denote M as the size of the assortment horizon episode k. i... M -A4%1- We define function R R R such that for all i E MR, R(v)) M exp(em (o,.
1 I+ exp(v))
For any h) K x [H] and all I, we denote oh(s% a) the utility, which be either Φ( a) 0% 20filo ()]( - or o(sh, 0% 20 a) (nt)) 1, determined deterministically based on the history up to h):
o(sh T 0 20 (H)) if Ba E IMfoot s.t. fhi (s a) 3 sh, ao) (1 a) 0% - 2 a) (1a))1 Va Iifao) 10 ( a) Sh a0). ao).
()) a)
Let 2 (5f) (u a)) ae RM and u a) T0%) DeA; E ERM Thanks to exact second-order Taylor expansion, we obtain that
H
ΣΣ
Σ
Ph
(k.n - At)) fht (
REK MEKh=leEA
"
Σ
Σ
(()) - ((11)s))))
h=1
H
H
( (uf(()) - ((
- -
v (( (uf(s)) - v(()))),
kEK
kE h=1
(
(B)
(D.31)
where ( (+ a))aa)) aeag E I MI is the convex combination of (st)) and (x))
We first bound the term (A) in (D.31).
v ((()) (uf(*
(s
NEK
exp (o(sh, T)T TT)) 1 Ji.Jcamnlohh (hh,
(uR(s), o(sh. a) TO;)
A Emee exp (Ø(s), an) T07)
KER k=1
exp (d(s), a) (7) sh. a) exp (p(sh, T²T
(uf a') a'sh:aa) 06)
Eneent exp (o(s), an) TO;)
AE d'EAK
ΣΣ
Σ Pr. (alsh. (l: fh
KEA. h-1 AE
(utt))) (st -1 0;
Σ a'eAt
Pn (a'lsh (u)(s) o(st o3)
(D.32)
We bound the right-hand side of (D.32) by examining two separate cases. For any fixed h [H], let K(() denote the set of episodes where Case (i) holds, and ((a)) denote the set of episodes where Case (ii) holds. More formally, we define:
K(() = K K: ( = Φ( a) 0h + 20 (())))))))
(Case (i))
K(a)= {KEK ( a) p a) T 0 ( (H)(
(Case (ii)
Case (i) For (k, h) e KC x [H] such that ( a) = dis T + 20/ll0( a) (H:)
29

---

Combinatorial Reinforcement Learning with Preference Feedback
Denoting BoL.] Ba [-] and ok == maxke[[] of for simplicity, we get
"
Σ
VMOA(()) (u)) - )((
( Ph (alsh: 01) shiseanglshi a) (loletz (0(()))))(((()'"))))))))) Eo; [ilo(si.a') a ([((= 1
Σ
2
Σ
at A
< 2äk Σ
H
Σ
Ph. (alo Ali 0%) Jhn a) (101e)% [1 (18)) - Eoi [lolot a') ))ll (11))
(x)
aEAt
H
2ōx
Σ
Eor
[Ji 100-Faa Eo; [1 (1)) (106 a)l (1x)) - -Roz [llocitt a' ([t)) 1)]
kE
H
(Frreannshh a) Eog ( d') [lo(st: - Eog Lo a' (
< 2āk
Σ
Σ
Eog
(D.33)
30
where, in the first incquality, we use the fact that at is nen-eccrngsing with respect to k, and by Lemma D.6, we have
Σ
Ph (alsh, Ah; 07) sh.ra,))ssh a) (1orst= a)ll (mz)) - Eo; [lo(sh a') (0]l(()))) ((HE))
Σ Pa (alsh, 1/: 07) ( (H7)) (fh.saan((hsaa Eo; [Jh. ad)
A
-Eara Ph(ayloh AiniAAtshh (ot
>0 O.
And the last inequality of Equation (D.33) holds because
l a)ll (()))) Eo; | a')
(1:)) < 11o( a)] (H)) - ||Eo; < [| a) - Eoz (0/ a''] (H:)-
-1Eo; [ a')] (H:))
where the first inequality holds by Jensen's inequality and the last inequality holds due to the fact that |a|l = ||a- - b-bbbb bll <
||a b] + |b| for any vectors a, b e Rd.
We further decompose the right-hand side of (D.33) as follows:
Σ keK h-1
Σ
Eo;;
[ a)- - Eo; (t)) I 10(h).a) - Lo::,0(hh: a' ([)l)()))))
(H;)
H
Σ
Σ
v Ph (alsh, AW: 07) Pn (als 1 (Fh.scnassst a) -Eog stt (tth
ke 1
1105s a) -Eof. [ a a')ll (H:))
H
Σ
Σ
(VPx (als), 07) v Pr (als), A5:00 0 v Pr (alst) 07)
kE 1= A
(Jh Roo (o% (0(( -Rogt [cb all (18))
H
Σ Σ
Σ
Pa (alshi (aish,,A:08 0%) (fh.scknnsssh Eo;
-Bo; pl (1t. a'))
kE b=1ocA4 45
(10(0), a) Eor (0 a')] (() llo((sh, a) - Eog. 1660 a (20)((z))))
(D.34)
30

---

Combinatorial Reinforcement Learning with Preference Feedback
For simplicity, let c a) c( a) Egg [ a'] and (( a) o( a) - Bog [0(sh a') Now, bound the terms on the right-hand side of (D.34) individually. For the first term, with probability at least 8, we get
H
Σ ΣΣD
Σ
Ph (als%, A2: 2)t)) (Jh.s.AA)ooh))) - Eog [Ih.emmsssth (()) 1 10 (]]l( (alok) A/: (al
(GX h-1
11
Ph Aa 07) (1hh) a) - Eor (o)) ?
Σ
Σ
REA
H
Σ Σ
Σ
Ph (alot) Ah: 0kt1)
10(0%% 1) ((pa))"
REA. h dEAl
H
K dd
Σ
Σ
Vn ((nn))
2dH log log
1
h-
K dd
0 (Vik1+H)lg(110))
2dH log
1+
(D.35)
where the first inequality follows from the Cauchy-Schwar inequality, the second-to-last inequality holds by Lemma D.7, and the last equality holds by Lemma D.12. Additionally, the second term in (D.34) can be bounded as follows:
H Σ
(v/P PN 01: - v Ph 44: 0kt)) v Ph A4::
Σ
Σ
())
h=1 AE
(Jh - Ro; [ (o. lō a)l (14;)-
H
|Ph (alsh. 0%) Pn (alsh, Ap: 0x+2) V Pn (als A/: 01) (0st (H²))
Σ
Ph (alst A2; + Ph (ul*f) Ap: 0%t1)
kE)(() h=1 De
H
Σ Σ
Σ
Pk (alsh, a Ah: 0%) - Ph (als Ah: o 0 [ a) ((x))
k h=1 oe At
& 4āk Σ
Σ
max 1 & a) (HH)) AEA
max
max dEAR
|10( s a) a)) (HA))-
kE
1=1
4āKA
max ( (11A5)
max
6( a)]l
(H$) a)l(
de At
a
ōK VK
4
ΣΣ Σ
Pa(als Ah. +
a)l (0)))))))
(m!)
Σ Σ max (0(s) a)l (H:)) aeA
k= h=1h= a AE
k= 1=
8 LadHHogg log
K
1+
(D.36)
VR
dA
where the third inequity holds by Lemma D.11 and by the definition of ā = maX a the recond-to-las inequality holds by the definition of xs and the last inequality holds by Lemma D.7.
31

---

Combinatorial Reinforcement Learning with Preference Feedback
Finally, we bound the last term in (D.34). Using the inequality |||] |b|| < ||a bl] for any vectors a, b E Rd, have
H
Σ
Σ
Ph
(alsh
0%)
(Jh.(mn)(thh))) - Foz (c..ccaa)ssh (10(5) a) (1F)) - (1x( a) (1Et))))
())
h-1 oE A
20
H
Σ
Σ
Ph (alsh, Alt 01)
Σ (Ph (a'1sh 0%) Ph (a'loh, Ah: 1)+ a')
(E)(()) aE A
d'EAR
(1T
K
Σ
Ph (alsh A/g Pn (alsh Af: 0% [1b a) (1)))
R- h-
H
< 4ök Σ
Σ
max
(
aEA!
8
axdH log
1+
K
(D.37)
dd
where the third inequity holds by Lemma D.11 and by the definition of ãx = maX a and the last incquality holds by Lemma D.7.
By plugging (D.35), (D.36), and (D.37) into (D.34), and ccombining the result with (D.33), we obtain
"
Σ (e)
Σ
(o)(0)) (x1))
K
K
<0 ( + H log(1 2āx 2dH log 1+
+
ax
dH log 1+
di
dA
1 dd H(og (log (log =o (av H//HKK((oogg 3/2 log M + K
(D.38)
Now, we consider the second case to bound the term (A) in Equation (D.31).
Case (ii) For (k, h) E K. [H] such that vf (0),, a) (( a) 00 2o a) (x))))
In this case, we know that ( a) < Sh. ((. (o2, on) for all E I(fa). This implies that |4 2, since adding
any item a E I I'fau} to the set {ao} always decreases the expected value of fh,j Furthermore, since we assume d ao) 0 (which also implies o an) 0), and denoting A {ao, a we have:
#
Σ
Σ
v (+)) (VX(+) (x7))
Σ
H
k (a Al; 01) fh fh abd (10(5%
(H+) (H;))
Pn (atls) 07) [ at)1 (M:) 1)
ka) h=1
Eo: (1is 10--1 Bon (( ) (10((s)
20g keKiu)
Σ
Σ Ro;
- (ost (l)ll(())))
(D.39)
where in the inequality, we use the definition ox == maxNe[H] of The rest of the analysis is similar to that in Case (i). Therefore, we derive
" Σ Σ ( (v)(s)) - (x(t)) =o ( K)3/2 log M + H K) (log My²). ())) (D.40)
keKG 1=1
k
32

---

Combinatorial Reinforcement Learning with Preference Feedback
exp(1)(s2.a))
Now, we bound the term (B) in (D.31). Let (et I-Eneea expl (1t
H
Σ
Σ
(uX(s)) - v/(s))) T (> (
k= h=1
1 Σ Σ
H
Σ
-(($t,)
- a) 0%)
2 ( (u%(s) o')
a')
Eada'
kE af A a'eAk
2 ΣΣΣΣ Σ
1
(u a) - o(sh.a) 0) ( (u%(s alhh
2
dada'
kE 4= A e'eAR ta
a) - a)) 8 o)(((
Σ
Eada
KE h-1 aEAl
Σ
(u((s o(sh.a) T Po (M oshh T
kE A d'eAk a'sa
3 3 2 KEK. h- 1
- -o(t,,))) (o((())))) (1
(D.41)
AEAA
where the inequality holds by Lemma D.8 and F (,, & 1. To bound the first term in (D.41), by applying the AM-GM inequality, we get
Σ ΣΣΣ Σ
(u o(sh)a a) TB Pa po (ut(sh, - ((hh 0
0%
KEA 1= AE a'
a. 7
Σ
Σ
(u)(s oo ( a') - a')
kE -= 1 aE a'eAk
(uilsh, a) - a)) oO)² ( (ot(s)))
ke h- 1 oe Ag d'eAk
Σ
(c( (u" o(s) a') - 07:²
kEk 4=1 AE d'EA
ΣΣΣ Σ tech-laEAy
- a) 07)) Pa (o)(s)))
(D.42)
33

---

Combinatorial Reinforcement Learning with Preference Feedback
Plugging (D.42) into (D.41), we have
H
(u - (/() (( (o vs()))
kEAh==
H
5
Σ Σ
Σ (a(()((())
(ui(s), p( a) a) 0%))
2
keKch=1om
H
{(k)) Σ
Σ
Σ
(u( (())))
TaKh=lacn aE
H
(āx)
Σ
max ( aE h-1
Σ
& a)ll (1z)) o 122 H (log K) (log Mn²)
(D.43)
kEK
where the last inequality holds by Lemma D.7. Combining (D.38), (D.40) and (D.43), we obtain
H
Σ
Σ
Σ
(h.)(k (alsh, A Pa(aloh, AR)) S (
AE
(0(x)) ((H) log M d
H(og K) (log (log M))
This conclude the proof of Lemma D.13.
D.4. Optimism
In this subsection, we prove the optimism of our value estimates VíA Lemma D.14 (Point-wise monotonicity, Lemma 31 of Agarwal et al. 2023). Suppose Algorithm I uses consistent bonus oracle satisfying Definition B. For any fixed (k, h) E [K] x [H]. conditioning on events Ecx-1 N (n ).fo.ffrrrr) for all (8h; 0h) I, we have
1. (Sh, an) & p (Sh, an);
2. fh,-1 an) < Q% an);
3. [T,2(5h,an) an) > max
Tn V/ h+ 1,1 1,1 (80, un), Sh. (Sh, Sh, an) VT [k].
Lemma D.15 (Optimism). Let Vi be the realized optimistic value function defined in (D.18). Suppose Algorithm 1
uses a consistent bonus oracle satisfying Desinition B. I. On the even conditioning on the good event E n EEgK all
(k, h) E [K] [H], we have
(x > (8)))
Proof of Lemma D.15. We denote A argmax EMEA Pa(alst, (s a). If A Ah by the definition of the
34

---

Combinatorial Reinforcement Learning with Preference Feedback
optimal value function Vi2 we have
Vi
Σ
Pa bh: (sh. a)
max
AEA
Σ
Ph(als R A 1Q
Σ Ph(als 1 (5 a)
a
Σ
P Pa,i(abbh
A 1, (0h: a)
at 4
P (ali Σ
fh.
aE.4,
Σ
F (alo% () (*)),
max AEA
where the first inequality holds by Lemma D.14, in the second inequality, we use the fact that, by Lemma D.5, there exists a subset A% = Ax with 4 A such that the inequality holds, and the last inequality holds by the definition of A
The case where A = A can be proven using the same reasoning.
D.5. Variances
In this subsection, we present properties related to variances.
Lemma D.16 (Upper bound of variance estimator, Lemma 34 of Agarwal et al. 2023). Let z Es afl Egg L-PP, (1 af and Vz[-Ish a = V. 11 Glst at) a where the expectation in only taken over 8h+1 due to the transition for shorthand. Suppose Algorithm uses consistent bonus oracle satisfying Definition B.I. For any episode k > 2 conditioning on the good event EsK, the variance estimator of satisfies
(s of).. We denote
(oh)² & [r 1 * (Fh,(=1)) 2h-2((hh)
2/ (Bt)² + + 4e ( + +
+ 4min 1. (=hs
- (.
Lemma D.17 (Sum of variances, Corollary 50 of Agarwal et al. 2023). Let # (0/ at)) We denote Ea Eo dg
E B PPP Gllk (oggatt Iss a and VeL-Ish a&] = V ( [ a where the expectation in only taken over 8h+1 due to the model transition for shorthand. When L ((1), with probability at least 8, we have
K
H
Ph
+ V
H K H
(+h)())) - (h)) K KH H||Kool + H log KH Σ
<
0
D.6. Approximation Error of Optimistic, Overly Optimistic (Pessimistic) Q-values
In this section, provide some inequalities for bounding the optimistic values, overly optimistic values, and overly pessimistic values sequence, which useful for the proofs in Subsection D.7.
Lemma D.18 (Approximation error of overly pessimistic Q). Suppose Algorithm I uses consistent bonus oracle satisfying
35

---

Combinatorial Reinforcement Learning with Preference Feedback
Definition B.I. Conditioning on the good event EgK, for any (k: h) [K] [H], it holds that
H
( 10h-2-Qh110 (5h a
Σ
Σ
(Ph.
-
A
Par(alsshi, AAt))
W= 2
H
H
H
2
Σ
26 alf)) +
Σ
_ +
Σ
W-h+1
W-
where 2
Ep (V +x+ (8n) | 11 a
(V
and th
Ep ( - Qh- (0% an)
shh 4tl (fh.-2 -Qhi (sh a/,).
Proof of Lemma D.18. Under the event Egk, we have
(fh. Q% nk (5 a
= (Jhh-2 Tn 1 ax) + (Th V 1 0% ( (sh ah)
25 a + Ex (rn-rr) + (V (M - Vn (5h+)(5+))
25h a + (V - ( (5h+11) + 5h+,1-2
- 25% a²) + (Qh+11-2- - ( A/+1)) + 1h+
Σ
2 (a' -ht (DL 1
d'EAf+1
25h a + ck Sh+1.-2
Σ Pht11-22 ( ( (hth 2
d'EAR+1
+ Ep
2 (5 ant:s A Ahtt (0 ath) + Sh+
= Σ 2
- Pntz(a'Is (
d'e
- Qhin) (oh+t,, 20% a + c + 2h+,,,-2
where the first inequality holds because Va inequality holds since V/b 2 > 2 AB 1
h+1,-2 E F under the event ESK and definition of 2, and the last
Hence, by recursion we obtain that
H
( 2h >>
Σ
2 A/t
Pnola'lsh,,, Alt)) shi a')
W-htld'eAy
H
H Σ -
22
bb (s ate)
+
Σ
-
W=+++
W==++1
Lemma D.19 (Approximation error of overly optimistic Q) Suppose Algorithm 1 uses a consistent bonus oracle satisfying Definition B. Conditioning on the good event &gg,, for any k E [K] and any h 2 hgs it holds that
(hh - (sh,
&
Σ Σ
(Ph A&r)) - Par(a'lsii A Shi (
N +-++1cm d'EAR
H
H Σ
2
b/j . s a 2 Σ
b axc
Σ
Sh
M=h
w=h
W=h+1
k=++1
36

---

Combinatorial Reinforcement Learning with Preference Feedback
Ep (V/,2 - (sn) 15-1./-1 (Vh,2 Ep (fh. - Qh: (ot) and s/ At (fh:2 Qh (s ab)
where Sh.2
(sf) and Sh
=
Proof of Lemma D.19. Under the event Kg at h 2 hgs we have
1hh - (s a (hh Tn v h+12)) a (ThV -7 (sh
< 2 a + 2 a + E [V - (sh+ att]
26h a 25 a + 11,,, (s Ch+1,2
25h aht + 2 ( o + (Qh+12 Qx ( Ah+1) + Ch+
Σ (Ph+1 // A 2. - Ph+z(a') (a A Q (5h
d'eAR.12
+ 26% (sh. a + 26 ahh + Sh+122
Σ
Ph
(hht12(d11bh+ 1/t11) 14+1(a'10/41 Aht1)) 1
d'EAitt
Ep
(5 sht1] (sh, att 20h af) S
Σ (Pht12ldllst
Ah+1) Pa+i(a' :
Aliti) sh+te(5hh4.aa)
d'Ahi1
( a + 26% (s a + 26h att + sh+11 + it 5h+
where the first inequality holds based on the assumption that TA E Fli2 and definition of bh.22 and the third equality holds because for h > hu, we know that A E argmax ( A) argmax, A EAEA Pt 2h+1,2(alsh+4 2, a) by the data collection policy in (9). Therefore, by recursion we get
-h.--00 (
(s
Σ
- Pn-(a'ls Alo) f (
W= d'EAt.
H 2
H
H
H
Σ
by
b
(8 ak)) + Σ
2 axr
Σ
$ +
Σ
Shi
hr=h
W=h+1
k==h+1
Lemma D.20 (Approximation error of optimistic Q). Suppose Algorithum 1 uses consistent bonus oracle satisfying Definition B.I. Conditioning the good event 8 n E for any k [K] and any h & hys have
(hh1 - The (shi ah
h
Σ
Σ
(Ph (a'lsh A/) Pm Aht) (st,
W= ==h+1 d'eAt
H
Σ
Σ
(Ph Abd
fh 2
N M-hx A'E
h+-1
+
Σ
b b ( a(i,) +2 Σ
1 a +
Σ
(Shv + 2
(ch 21
W-h+1
37

---

Combinatorial Reinforcement Learning with Preference Feedback
where
S = EF [(V, 1/ (sh) 1h-1] (V%, V/ (5%)
Ch, Ep (1t. 2h Th
(sh, an))
8/ 1hl
(fh, Q%
(sh: aft,
2 =- Er [(Vi, - (/*)((8)) 5 0z 1]
(Vi,22 m/ (shi)
čk = Epp [Jhh - 0% (s an)
8/ Af.
[h122 2h (sh: af)).
Here, following the convention, use the empty sum notation, i.e. Ei= 2; = O. when b
Proof of Lemma D.20. Under the event Egk, by Lemma D.14 it holds that (h,( & (h. for all (s,a) E S x Therefore, for h = hg. by Lemma D.19, we get
(fh,1 - x%x))ss a
(hh - (sh. at
H
Σ
Σ
P 2 A&,) (ar Aht)) She 25hk.
W h-hhlla'df
H
+ 2
Σ
b 1 (5 (/r axr) + 2
Σ
b 2s a Σ
She +
Σ
(D.44)
A/=h
=/=h
N=+++
h==h+1
For h = 11 - 1, we have
(th.1 - 2% ) // ) (hh - Tn h+ a + (TaV Q% (s ap)
< 26 (,), a + E [(V/41,1 1/²ht (5 | at]
20% a/) E [(V - -VrT ($ 1)1,% at
(,h ah) + (V - ( + 2h
(5% at) - ( Sh+1,2
Aht1))
Σ
Pntall')sh Ah1 A RNithhhh))
d'EAt
+ (sh. at + Sht,,2
Σ (Phtz,2(a)) |5+t1, Aht1) Phtzla'lshtu Ahtz)) (h+z2(5h+1,,
d'EAR+1
+ Ep [Th+12- - -hit1) (0 (1 an41)))) Ahtta + 20% at) + shit2
Σ ( - (a' + Aht1)) 2
=
d'EAk
(h+1) + 2 (5h at) + Sh+12 + ch+t12
(D.45)
where the first inequality holds based on the assumption that T&VE 1+1,1 Fhi and definition of b/ and the second inequality holds because for any 8h+1 E S, we have
Vhh (18+1,(80+11)
Σ
d'EAnti.1
Σ
a'e AntAn
Σ d'E
(a'1,(('18h11 An
Σ
d'EA
38

---

Combinatorial Reinforcement Learning with Preference Feedback
where in the first equality, we denote Ah+1,1 E argmax A Eo'Ea Pk 1 (d1s A) (#h+1, ), for the first inequality, we use the fact that (1 a) & fi+1228, a) (Lemma D.14), the second inequality holds for some A S A4, (Lemma D.5), and the last inequality follows from the definition of 1 Moreover, the third equality of (D.45) holds because for h + = h2, we know that 1 A by the data collection policy in (9).
Therefore, by recursion, we have
(Fh,1 2%) (sh
H
Σ
Σ
(Ph - Par A33)
2
W/ W-h+la'eAt W
H
2
Σ
( ab.)) +
Σ
2 +
Σ
She +
$
(D.46)
W=
W=++1
M1=h+1
Finally, we consider the case where h < h4: - 1.
(hh. - ab) (fh,1 Tn 1 a + (Th (TAV 2% [sh ah)
20 (5/ at)) E [[(
af]
(s% a/:)= + (Vi+1,)) - -V7t1 + Sh+1,1
2b% (0/, att (Qh+111 - -0h+11- 0h+1) Ahr1a + 2h-
Σ (a' ( ( - 1a''s (h
1'eA
+
a + Sht12
Σ (Phti,(d'1 (d''sss Ah+1) P Ah+n)) fh (htta
d'EARt1
+ Epp [Jh+1 - @itt)) (sh+1 (sh+1) (11))sh+) lh+1] + 16% at) + sh+ra
= Σ (Phtzala') (ainn - Ph+i(a (a'l s Altt2) 8 (
d'EAt
+ (Jh+1,1 Qhi1) ( + 1 Sh + Ch
V where the first inequality holds based on the assumption that Ta 1+1 Fhi and definition of 6/21 and the third equality holds because for h + < fys, we have Af+1 = - by the data collection policy in (9). Hence, by recursion we have
h--1
(hh, - (sh,
Σ
Σ
(a'l At) Pn-(a'lsh Att) A P (s)
W=++lad A'e
H
Ph (a'lsa sty ( Prr( Att) 2
W=h d'e
hy-1
+ 2
Σ
byg 1 (s ald) 2
Σ ( att
Σ (sk ((h,))
W w=++1
H
+
Σ
(Ch
ck (k)
(D.47)
Combining (D.44), (D.46), and (D.47), we conclude the proof.
39

---

Combinatorial Reinforcement Learning with Preference Feedback
D.7. Bounds bonuses and ooo
In this subsection, we provide proofs for the bounds on the sum of bonuses (Lemma D.21, Lemma D.22, and Lemma D.23) well the bound on the size of Ko (Lemma D.24).
Lemma D.21 (Crude bound on b/,1, Lemma 39 of Agarwal et al. 2023). Let 2 (sh af).. Given bi,1 & C--
(3h.)) )
Drn (3 (
+ p + cophi11 when p 1, & 1, it holds that for any subset K. E [K]. we
have
min (1 + L, (2h)}
kEK A=1
= -0 ( log
NKH vd
(Vios'
NN,KH vg
NN,KH vd
d. + 1.H+IK(HH,) )
K. + log
Lemma D.22 (Crude bound on 2/.22 Lemma 38 of Agarwal et al. 2023). Let zh
(oh, ot).. Given b1 & C.
DA. (s ((tta) + p + when p 1. & it holds that for any subset [K]. we
huve
H min {1 L, b. (2,))))
=(Vlog NNKK
(HVd)KK(dHHH dd +K]HH)))
8
kEA
Lemma D.23 (Fine-grained bound on 1/ Let # = (sh a.)). Recall that the bonus oracle B oulputs bonus function
such that by (-) & C. Das (s (Z (o)) . (0%..) ) +p + co0h.1) When 1, 1/V KH, 8 < (0, 1/7)
and the event EgK holds, with probability at least 1 - 76, we have
K Σ
min 1 L, b (2h))
NKH
NN,KH
NKH
du HK. llgg
d/ Vooloo K) log M log
log
8
V
8
8
NKH 8
NN,KH
3/2
NKH
+ 0
d, 2/ log
log
+
log
KHH + v de dr
8
NKH
NN.KH
+
|1o0
log
d,H
H2 Σ kEK.
uk +
v H2 H22
8
8
Proof of Lemma D.23. By the definition of the oracle B (Definition B.1), we have
K
min (1 + L, (x
1=1
min 1. Dr, (shi (o)+=)) (8%.) 2 +D} + KHo max Bk
o
k.
(vi08
NKH 1og 5
ΣΣ
min (1, Dz, (2h (- (0) + KHeb
(D.48)
where the last equality holds by the definition of Bh.1.
40

---

Combinatorial Reinforcement Learning with Preference Feedback
Now, we bound the summation terms
K
H
min {1, Dr, (2 (,
K
H
min 1 (ot) -1 Drn (=3
by dividing into the following cases:
4 (kr,h) E [K] x [H] (o%) -1 Drn (=hi: (0) =1] =1}.
I2 ((h,h) E [K] x [M] oh u, (k. h) + In}.
I3 (K. [K] [M] o = 2 (o(o8) + (ot)) v (et
(k.h) # }
I4 (k,h) E [K] x [H] の = v2(06))) v [hi((hh)
Is ((i,h) E [K] x [M] th (k, h) * IT),
For the case of I, we have
Σ min f1,0h (0t) (0h) (zh (1104
(k
11 dim (Fr) = d.H.
E Σ
E
(D.49)
(K,A)EZ,
For Iz, we use the Cauchy-Schwarr Schwarz inequality to get
Σ min 11 (ot) -1 Dr, (=h: (271)1
(k.b)eI,
H
& NVRKH.
Σ
(oh) - D3 (45
Σ
((m,,((F))
-dHHH.
(D.50)
(A.A)EIz
For I3, we have
Σ
min (1,0% (5%) Dr, (+)+)))))))))
x Σ (80(5)) + + min {1, (oh) -2 D2, (sh (.
NKH
NN6KH 8
H
log
+ log
Σ
dim (Fr)
8
((vos
1ogg
NKH
+ log
N
d
(D.51)
8
where the inequality holds because, by dividing both sides of of = 2 (Vo(o)) + +((8)))
V
by / at and rearranging terms, we get:
of < (8o(6)) + ((6))) Dr. (4
41

---

Combinatorial Reinforcement Learning with Preference Feedback
We also use the property that (o*) Dra (# (+)))) & 1 for (k; h) E Iz. which follows directly from the definition of Zz.
For I1, have
Σ
min
1 (0%) Dr, 1
(K.A)EI4
Σ
th (0%) Dr, (2 (277)) (o)=
(k.A)EI4
Σ
v2((8h) (hi2(h)) 2 (0h)
Dr (28 (+])= (o)=-
(K.A)ET4
NN.K
H
log
Σ
(2 - fh 2 &dHH) )
(D.52)
8
1=
where the last inequality holds by the Lastly, restricting on Is. if the event EsK holds, we have
inequality together with the definition of c(0))
Σ min
{ (1 o (oh) " Dr, (2i
(K.
Σ
(0%)
Dr (
(k,N)eIs
Σ (ot)²
Σ
(oh)
(K.
Σ
V + V/ (Sh+1))))+1)
+ + Σ
(1h)( - fh. fh . dd
ki
k.h
NNIKH
+ 0
> k
min (1, (2t (1++=)
log
/d.H
(D.53)
where the second inequality holds by the Cauchy-Schwarr inequality, the last inequality holds by Lemma D.16 and the definition of Eluder dimension.
To further bound the first term on the right-hand side of (D.53), we apply Lemma D.17. Therefore, with probability at least 1 - 8, we have
Σ (T
min 61 (5%) Dyn (=his [= (o)
KH
(h2(())) - 1 sh. + K+ KH28 + H2|KCol + H4 log?
v d,
k.h
Σ (hal()))) - fh ( vdyH +0 (1 H.d,K)
NN,KH
log
V H
K + KH28 + H2|Kool + Ha log KH
VV d +
H Σ (hi - 1h - . d
NNGKH H,H. log
+0
(D.54)
42

---

Combinatorial Reinforcement Learning with Preference Feedback
where the first inequality holds by the fact that
Σ
min (1, Drn (# (e00a11117 H.H
k.A
Σ
min min (1, (2 (T)))) < VK
Σ
D2 (17)))))))))) &
k.h
and the last inequality holds by the AM-GM inequality such that
NN,KH
NNAKH
N K de log 8
<K+
H2+ log
8
Combining Equation D.49, D.50, D.51, D.52, and D.54, we get
H
min (1, Pr, (=h: (1 (o)==))
NN,KH
K H
0
log
dd,H
(h.2(zh)) - (2h))
8
h=11
KH ddlll + do Vlog log
NN:KH
K KH28 H2|Kool
14 log"
(D.55)
Now, we bound the term Σx,h (Jh((z)) - shh-)(=)) For k E Kon, we have
Σ -ha(th)) - ( - O(1Kool H). K
Otherwise, for episodes & E Ko. we know that it holds true that fh, (=h) > ph - up by (9). Therefore, under the event Cg we have
Σ kEA.
(Fhe(=h)) 22,) Σ Σ
(Jh,(
sh.-((1h0) H Σ
uk
ke h=1
KeK.
H
= Σ
Σ
(Uh.. - (=h) + (Q% The f (+ + ..H Σ uk
kek,
keK.
H
Σ
Σ
Σ
1/ At) - Parla'lsti, Alt)) (sh.
kEk. h=1 1==1====+ l'=
H
Σ
Ph. ( Atd
(wi(d'ss ( fht -
kEA, v-=h+ o d'
H
H
H
H
+ 2
min
1+ L,
Σ
bh (ote abr))
+ Σ
min 1 + L,
Σ
bi 2 ale)
ke h-1
hhh
Mek. h-!
H
Σ
(he + th Shv--2 5
+ + Σ
ukk
(D.56)
kEK. h= h=h+1
keK.
martingale difference sequences (MDSs)
where the second inequality holds by Lemma D.18 and D.20.
To further the right-hand side of (D.56), we apply Lemma D.10 (which holds with probability at least 1 26) to the first and the second terms, Lemma D.21 to the third term, Lemma D.22 to the forth term, and we bound the fifth term using the
43

---

Combinatorial Reinforcement Learning with Preference Feedback
Azuma-Hoeffding inequality (which holds with probability at least -6). As result, absorbing the low-order terms, obtain that
Σ
(fh)(=))))
2
1-1-11
0
AHHVK (log K) log M
VR
NKH 8
NN.KH
NN.K
+0
log
V1og
SPVd,K + log
8
NN,KH
KH
+0
log
KH + HN K 8
Koo
H + H Σ
(D.57)
8
Joe Kip
where the last inequality holds by the AM-GM inequality. Plugging (D.57) (D.55), have
K
H
min 1, 1 (oh)
DAA (#hi (27 (o)+=)))
Vlog
NN,KH d. (V
V VR
1
dHH K33822 log M VK + H²
Σ ke
uk
AN.KH 3/4
NKH
NN.KH
log
VdH..
log
Ha + Vlog
dr
NN,KH
NNOKH
KH KH H' KH log
log
d.
VV log
+ KKoo H2
KH
dr H d.H 1 Vlo NN.KH
K KH28 HA log
NN.KH log
K
NN.KH
Vd,H.
log NNKK + d2 HD (llg K)3/2 log 103 M log
NN,KH
NKH NN,KH
log
d.H.
d log
log
H2 Σ Uk
8
kE
NN.KH 8
log
d. v H2|/Coo KHe V d,H VKH2
K23322 log log M log NN.KH
ddHHK- dHT/2 / (log
VK
NKH 8
NNOKH 3/2)
0
H7 log
NNCKH
+0
Vlog
d.
H2
Σ up + v H2 Kooo kek.
+ KHH, + / dyKH38
(D.58)
where the second inequality holds by applying the AM-GM inequality and absorbing the lower-order terms.
44

---

NN,KH Combinatorial Reinforcement Learning with Preference Feedback
Finally, plugging (D.58) (D.48), we derive that
K H
min {1 L, by (=h0)
NKH
NN.KH
NKH
H log
dH /d K) log M log
V log
Vk
8
+0
1/2 log
NKH 8
[og NN.KH
3/2
NKH + log
(KIles V ddKK1188)
ò
NKH NN.KH
(1
log
dyH
H2 Σ un v H 1122 Kool
8
6
kEK.
This concludes the proof of Lemma D.23.
Lemma D.24 (Bounding size of Koo). Suppose and we set
V
log
NKH PB
[log
NN.KH vō
1512 vkHls
d K)3/2 log M log NN.KH
Uk C.
VI.
for some large enough constant C 00, when the event EaK holds true, then with probability at least 28, it holds that
K
dw
d' d'og K)3/2 log My d2, log
|K < 60
H
log
H3
NKH (log N
28
vb
vd
Proof of Lemma D.24. By the definition of h4, for each k E Koo, we have fh, 2 alr)) 30 S aire + up. which implies that
Σ (hh.2- 15 ald
uk
k
ke
NKH (NiSs
NN,KH
[Kroll VK
C.
log
H Hd/2//d dr
+ +Kooal Heb
Dō
vd
NAGKH vd
|Koo
+ 5/2 (log K) 3/3/2 log M
log
(D.59)
VK
Furthermore, under the event εgK, by Lemma D.14, it holds that f (sh, an) > Qn(s,, an) > Q (sh (sh, an) I. Thus, we get
(sh, ax) for all
Σ (Jh..2 (s ol
Σ 2 Qhe afr.)
kE
keKw
Σ (Ph Alr Pho(allstt Alr Sh 2shh,
ke M=hh +1 L
H
+ Σ
min {1 L, bbr (5t ah. +
Σ
min {1 + L, by. ( a
Σ
(ch + (ttz2)
kEK.n. -'=ha
ke h M==ha
keK -1=hut1
(llg K/3//110 log M) 2
KH v KKn log 5
dH /HH/Kmm) (log k/33/2 log M + &
K
NKH
(Vies- NNGKH 28
NN.KH
+0
11g" log
H d, Kool
+log
d,H + (Kool HeO
(D.60)
118
45

---

Combinatorial Reinforcement Learning with Preference Feedback
where in the first inequality, note that A A for // > hg. the second inequality follows from D.19. And for the third inequality, we apply Lemma 1.13 to the first term, Lemma D.21 the second term, Lemma D.22 the third term. Finally, we bound the last term using the
inequality with probability at least 1 26.
Thus, in order for the two inequalities D.59 and D.60 to hold simultaneously, the following condition must be satisfied:
|Cool &
max
K NN.KH
NKH ddylog log NN.KH H3/2
NNAKH vb
log
2B
NKH NNKKH 28 + d(log K )3/2 log M })
1 (( ((log))32 log M))2 VK
H3 log
Vlog vn
(V log ub
log
Using the AM-GM inequality, we can further bound the second term inside the max operation.
do log NKH Po
log NN.KH
d K)8/2 log M)2 VR
H3/2, v log NN.KH vb
NKH (y dy log
log NN.KH d(log K K)3/2 log M)
NKH day dan/ /og
NN.KH log vo
+ ((lg K) K)3/2 log M)²
0
K
4b
H log NN,KH
H3/2 v de log
NKH log NN.KH vd
nd
K
de
&((log K)3/2 log M)²
0
H log
NN.K
H3
H3/2 V dh log NKH log NNKKH
K
dy
dt ('og K)3/2 log M)
H log
NNKH
H3
i.d,, H3 log
NKH nb
(log NASKH Mb
vd
where the second inequality also follow from the AM-GM inequality and the last inequality holds due to the fact that 2a² 21² for any a, b E RR+ This concludes the proof.
(a + b)2
D.8. Proof of Theorem 5.1
Now, we are ready to provide the proof of Theorem 5.1. To start, we formally restate the thorem.
Theorem D.25 (Restatement of Theorem 5.1, Regret upper bound of MNL-VQL). Suppose Assumptions 3.1 and 3.3 hold. We assume that we have the generalized Eluder dimension dim, (.,,k(FF,, (Fr). E [H]. as defined in Definition 3.5 with
and
access to consistent bonus oracle B satisfying Definition B.1 with c (H)/KH). Let d,- - dim,, (Fi) with == H, and set ug = O VlogNN N -oooo Nlog.NNN H / /logg /K). Then, for any d < 1/(H2 2 +1)) with probability at least the regret of MNL-VQL upper-bounded by:
NKH 1 d2 H2 2 K) (log $log M))
(M,
O
dv (V 3/2 log M + V H. log
+
8
K
NKH
NNGKH 2
NN.KH
+ +0
d log
log
log
KH
5
8
where d is the feature dimension of the MNL preference model, N is the maximum size of the function class, iee, N max Ful, and N2, is the size of the bonus function class, i.e., No, = (W)
Proof of Theorem 5.1. When the event 8 N Egg happens (with probability at least -25), we can bound the regret as
46

---

Combinatorial Reinforcement Learning with Preference Feedback
follows:
K Σ k-1
K Σ
Regret(M, K)
(Vi VTTh) & Σ (v/ - (x9) k-1
(0) Q(*) (0)
R-1
< 01 + Σ (of - -1+ (5)
2-2
= 0(1) +
Σ (0) - QT- + Σ (Q) - (bf,
(D.61)
kE
kEA (12)
where the first inequality holds by Lemma D.15.
For k KoM(),, recall that (s) = Emea Ph, At)h, a1) for all h E [H]] defined in (D.18).
Therefore, we have
(0-- 18--94 21+) (5 At) = Σ
p (aii( (t) Σ
Pi (s).a1)
aJEAt
Σ
(a - Pi(ailst APi(cllss At) Sta(sh. a1)
=
arEAf
Σ
Pi (ft: - x7th (1)
+
Σ
(Pi, (1 A4) - (a2alst st. (sh, a1) + (ft; - Φ.tt) (s),
=
arfft
+ Ep - (sf,ai) of At] - ( - Qia (o)
Then, by applying Lemma D.20 with hy
H 1, we have
H
(Qt - (
(4) x
Σ
Σ
(ani(anlshi Ah)
Pulanl AB3) sh. (sh, an)
A
in
H
H
H
+
bb.1 (sh: anh)
+ Σ
Sh.1
+
Sh
(D.62)
h=1
h=1
h=2
where 1k.1 Ep (V% (sh - -hh+ (.haati)
V
(sa))
1 /
b/
-(V% -V, -VVi,,-V%%" (*t) and Ch.
Ep [1 - -2%% (ohgan) 5/ A4
Now, consider the case where & Kool11). In this cases, note that h4 [H]. Similar to the above analysis, by Lemma D.20, we get
(Q) - Q7" (0f, AH
Σ
Phk (anssh AW) Pa(anlsh:Ah)) [h az)
h-1 anEA
H1
Σ
Σ
(pt Phha(anlsh At) Pa A Att) sh an)
hx aA E.A
h
hy
H
H
+ 2
b (stt at) + 2 Σ 2 a
Sh,,1
Hk
+
ck
+
Σ
Sh.2
#k
+
Σ
ch.p.
h-ha
h-2
hー
hーha
(D.63)
where 2hi2= = Ex [1 -12" (sn)) 1 / // 1/ 1 -V,
(s{t) (ot) and Cti2 = Ep (
1% -
(s an)
./..Af..
(Ih.2 - 0,11) (s/h att).
47

---

Combinatorial Reinforcement Learning with Preference Feedback
Plugging (D.62) and (D.63) into (D.61), and denoting J(k; [[K] [M] [ (1, as the one-to-one function that maps from [K] x [H] to the index set {1, 2} such that A = J(k,)) E argmax Lee Ph we obtain that
hc, (alss, A) ((..)) (sh a),
(egret(M,Al
K
H
< 0(1)+
Σ
Σ
(
(anleenyaanlsh A Ph (an AR3) Sh (ka
K
H
min 1 + L,
Un
(s 4 +2 Σ
Σ
min {1 + L, 2sh: ah)
k-2k=1
Ke A At=ha h4
K
K
Σ
* S6.2
2= A=1
k=2
h=2
k=2 h=b
A= hmmk
Now, by applying the results from Lemma D.13 to bound the first term (which holds with probability at least 1 - 28), Lemma D.23 for the second term (which holds with probability at least 1 - 76), Lemma D.22 for the third term, and applying the Azuma-Hoeffding inequality to the remaining terms (which holds with probability at least 1 - 46), we get
Regret(M,, K)
dy (log 3) log M + de H K) (log
<0
K
NKH 1
NN,KH
NKH log
+0
[..HK log
d/ V (log 8/
log M log
VK
5
8
NKH 8
NNOKH
3/2
NKH
+0
d 1/ log
7/2
log
log 8
(KHe V Vd,KH38
NKH
NN,KH
+0
log 5
log
Vd
H2
Σ kER.
un + v H2 Kool
5
NN,KH 5
log
H del (oal + |Kno Hes)
1 d (log dv HK (log k/3/2 log M +
K
NKH
NN,KH
NKH
\V.
d.HK log
dH
// K/2/2 3/2
log M log
log
VR
8
8
NKH
NNGKH
3/2
NN.KH 8
2/11 log
log
log
(KHEs Vd,KH')
NKH NNGKH
+0
log
log
d.H
H2
Σ
Wk
(D.64)
ke
where the second inequality holds by Lemma D.24 with probability least 1 25, and use the fact that [A Hc,
K KH
Now, we apply the AM-GM inequality to the term O 12 K/3/2 log log NN.KH we get
V log NKH
thus
8
NN.KH NKH
dHT/2 /d. 3)322 log M log
log
Vk
NN,KH 8
2
NKH
0
d2 H² (log M)² + d
log
-log
(D.65)
k
8
48

---

NKH Combinatorial Reinforcement Learning with Preference Feedback
Furthermore, by substituting the chosen values of ug and applying the AM-GM inequality, we get
NKH NNKKH
V
log
log
d. H
Σ
uk
NKH 5
(log NNGKH 2
dd -log
+ de (H2 K)) M)² + d. H log
5
NKH
log
KH
(D.66)
Then, by plugging (D.65) and (D.66) into (D.64), and setting H2415 derive that
NKH
1
(Mg =
dv H (log 3) log M V Vd,HK log
- (log K) (log M)²
8
K
NKH
(10g WN.KH + log
NN.KH
0
log d log
K KHeb
5
5
We conclude the proof of Theorem 5.1.
E. Proof of Theorem 5.2
In this section, we introduce several properties linear function class. We formally define the linear MDP as follows: Definition E.1 (Linear MDPs, Yang & Wang 2019; Jin et al. 2020). An MDP M is linear MDP if we have a known feature mapping vb : S - IRd" and there exist dln unknown (signed) measures μ4 (14 ....,,,, Ph (2")) over S and unknown vector w Re" such that for any (8,a) a) S I, have (=(()s, a) (vb(, a), p (+) and (s( a) (1)(s,)), wf). assume that sup(e //tasssxxx/////s//////////s [s, a)]l2 < 1, max Eees [n] (s) 21., [[w],22] & vddin for all h E [H].
In this proof, to explicitly indicate the dependency on parameters, we denote the linear MDPs as Ma we. where and w"=(wA)]'
[0=
We also assume that Σ Th [0, 1]. Proposition 2.3 of Jin et al. (2020) shows that linear MDPs satisfy Assumption 3.3 under the linear function class Fi defined as follows:
Fl (v(+)) (((()),ww)) wh) wh Idd |wlll2 2Vdmm). for any h [H].
(E.I)
For linear MDPs, let (c.) be an cover of Flin under the lo norm, so that
2 din
log [ (E)) o diin
log
Ô (d
(E.2)
Eo
Then, the definition of generalized Eluder dimension for the linear function class Jiin can be expressed as:
Lemma E.2 (Lemma of Agarwal et al. 2023). For the class Flin defined (E.1), letting Jl (cc) be the co-cover of Flin for some e, have
dim,, K (F (ce)) dim,, (FF - (d log 1
-0
K K vAp)) O(dtin)
The bonus oracle for linear MDPs can be easily instantiated using the standard elliptical bonus, and, as demonstrated the next lemma, satisfies all the required properties for bonus oracle.
49

---

Combinatorial Reinforcement Learning with Preference Feedback
Lemma E.3 (Bonus oracle B for linear MDPs, Lemma 7 of Agarwal al. 2023). Given K, H 2+, suppose all 3
and By, is non-decreasing in k E [or each h [H]] For any k > 1, E [H], variances (0%,7-1 satisfying oh z v for some U O, dataset D (bb( w) , ah h The vb( (6 7 k- function class Ft and f%th E Fh defined via weighted
regression in (3), and parameters PA O, let (((o)) 7-1 D
Pr.c) 11 (1x)s,))(<xt)-1V (Bh) P.
where Σ fa I + Σ (σT) (5 (5h aT) For any choice of covering radius ec & p//p/KK the oracle satisfies all the properties of Definition I with
log.N = log [W] = 1m/=0(( = (1+ d Vdim 3/(2)) = ((d
Theorem E.4 (Formal version of Theorem 5.2, Regret upper bound of MNL-VQL for linear MDPs). Under the same conditions with Theorem 5.1. suppose that the underlying MDP has linear transition probabilities and rewards, so that the function class for linear MDPs, Fkh, satisfies Assumption 3.3. Let (l.n((c.) ) be an <c-overr of Fl! under byp norm. We set 1, θ ((d H + d(dding:/2 ( / KVK), < //HKK, 6b e 1/(8HK) and ō < 1/(H2 + 15). Then, with probability at least 1 - 8, the cumulative regret of MNL-VQL, with bonus oracle defined in Lemma E.3, is upper-bounded by
Regret w", o dv dVHK HK
! d VHK + ( H
regret from MNI, model
regret from linear MDPs
Proof of Theorem 5.2. We apply the above results linear MDPs Mø. - r w with function class F Fih (Ee), , E [H], and bonus oracle B. From (E.2), we know that N Ö(din). Additionally, Lemma E.2 shows that de = (d Therefore, by combining these results with Theorem 5.1 and Lemma E.3, we can establish the upper regret bounds for linear MDPs.
Regret (Mor.u w" K) Ö(dv (ddV1K HK d VHK + d2 + (diin)0115)
K.
where we set p = 1, ds ① ((dinn33 3/ WK, v VIHKK, cb ce & 1/(8HK) and 1/(H²+ 15).
F. Proof of Theorem 5.3
In this section, we provide a regret lower bound for linear MDPs with preference model. We construct a hard in- stance M(S, A, ( ( H), illustrated as in Figure F.1. This instance is based on an H + 1- layered structure, where each layer is a variation of the hard-to-learn MDPs introduced in Zhou et al. (2021b).
Without loss of generality, we assume that d > and that dinn 5 is divisible by 2. Let é [H + 2] represent the layer index. For each layer i E [H + 2]. there are H - i + 3 states, denoted as (.()) ...., #2+2 where HH is the absorbing state. Furthermore, there is a global absorbing state In. which can only be reached at any state and horizon through the
user's choice of the outside option ag (not choosing any item in the assortment). Thus, there are (ff + 1)(H + 2)/2 + 1 1, 13 - 5)/2 u (ao). The set states in total in the set of states S. There are nd -5)/2 + 1 items, so the item set is I = {-1, of candidate assortments follows the definition Section 3, i.e., A {A I ag E A, 1 & [a) & M).
F.1. Construction of linear transitions and rewards
At each episode k e [K], the agent starts from the fixed initial state 21" We define a as an item such that aj, argmax (mr)) (pn, a), where 1h (- -5/2 with A (B/K/(4/2) and 1/H.
If the state 2%/ with i e [H + 1] and E [ú, H + 17, and the user chooses the item aj, the agent remains in the same layer (8)
H i and receives a reward of /1-1//H1 where 7 I+H The next state will be either 2h41a #41 2 with probabilities
(6)
1 1- (8 (MAn, a>) and 8 <Mh, a), respectively. If the user chooses an item सf ag, ag,a, at in the state z with i [M 1]
(t)
(i+1) and h E [i, H + 1]. the agent obtains a reward of / and transitions to #h+1AH4 or x H+2
((+2*H+2)
with probabilities
*If din is not divisible by 2, we can set d < Lin + by adding zero padding.
50

---

Combinatorial Reinforcement Learning with Preference Feedback
1,- -0-
pontin www.
1/11
#1
6-
2
33
2213
b+ (n a 1/11
a),
H/H
(1)
22-2
1/H
(2)
12)
8+ (m a). r= H
(2)
1.
23
(3)
-H42
7//
1,
Figure F.I: Inhomogeneous, hard-to-learn linear MDPs with MNL preference model. The solid line indicates the transition caused by the user choosing the item a (with a reward of Th -//1//H) the dashed line shows the transition caused by the user choosing any item a A a ag (with reward of Fą = 7²/H), and the dotted line represents the transition caused by the user choosing the outside option ag (with a reward of гд = 0). The blue solid line indicates a transition from the absorbing state back to itself, caused by the user choosing any item (with a reward of ra HH), and the red dotted line indicates transition from the global absorbing state back itself, caused by the user choosing any item (with a reward of mh 0).
(8 (Mh, a)) and + (Mh, a), respectively. the user does not choose any item, i.e., chooses the outside option ag, in (2) the state 2h with e [H + and h [i, H + 1], the agent will deterministically transition to the global absorbing state and receive no reward.
the agent is in any the absorbing states- H-2 for E [H + 2he agent will remain in the same state and receive a reward of 1H11/ regardless of which item (including the outside option) the user chooses.
Formally, construct transition probabilities Pn(s'|s, s, a) (wbss, a), (s))) with
(a, .,.00,T00,000. 0,,0,0,0, v2 a0,0,a, Ba ,,,0,
x a E [H + 1], e [1, H + 1];
10
8 x (4)
a a ap, i [ 1], E [i, H + 1];
(33 a)
(F.I)
(0,0T 0, 0,1,0)
s x a ag, ie H 1], E [i, H 1];
(0,0T T 72 0,
8 H+ ie H + 2].

---

Combinatorial Reinforcement Learning with Preference Feedback
and
(1ا 1 0,000..0..0) a 3 (a 3 220000 (0,0, (0,0, 4 0.0.0) 10,0,
s' hhlnH++1
(6)
s' H422
(6)
S' h4+1 li+1);
(F22
(++2xH+2),
s' 2H+2
(0.0 0,000000,0,11001
s' Zoi otherwise,
(0, (0,0 ,00000,,00
where we denote 0 -8/2 the zero vector of dimension (d 5)/2, and set set H+I as the discount factor for transitioning to the next layer. Additionally, we choose 1/H, 4th (-A, -)dd with A (8/
H
a = / 1/ Á (dim 5)), and v (2 + A (dim 5)).
And the parameter vectors for the linear rewards rh (s, a) = (vi(s. a). w are as follows:
w = (0, T 0,000000,
which ensures that the reward function satisfies:
HH
2 , a [H 11, [i, H + +1;
(1)
7/H,
2 hhaa a a ao. i [H + 1]. h E [i, H + 1]:
(1)
Th (s, a)
0.
8 x b a = i [H + 1], E [1. H 11:
8= # [H + 2]. HH,
where 0 < <T> & H is the discount factor for transitioning to the next layer. Ø4T
This parameter setting satisfies the boundedness assumption of linear MDPs (refer Definition E.1). First, we show that [1,(s, a)ll2 & 1:
din
[v(ss, a)]l m a²+
B² +
2 = 1,
(the first and second cases of (F.1)),
(v(s, a) = 1
(the third case of (F.
1
(Mssa))l E
+ 1,
(the fourth case of (F.1)),
2
2
Moreover, since din 6 and K > 13(d din 5)2/ H. ensure that max Eses (n [w]]2) & v vdti:
(s)( seS
Σ
2(1 - (11-8)2+ + 28
|alll
+3
a²
132
2 A. (d 5)) 2A (a 5) (2 + A (ddin 5))
< (2 + 24 24 (d - 5))² 2
& in
and
[w] 3 <
< in
2
F.2. Construction of MNL preference model
Inspired by the lower bound proposed in Lee & Oh (2024), we construct an adversarial setting for the MNL preference model.
We assume that d >> 2 and that d 1 is divisible by 4 (without loss of generality). Let (o. (0 be small
positive parameter. Throughout the proof, we set c - / d-1 (H++))
1MCC-K # for some C 0. For every subset W = [d 1].
we define the corresponding parameter Ow Rdd1 as [0wli = for all j E W, and [0w]; = 0 for all j $ W.
52

---

Combinatorial Reinforcement Learning with Preference Feedback
Next, for any h [H]. we define the parameter set as:
0 E θ = {(Ow. log H) T We e W(a-1)/a
[(O log H) W = [d - 1I, [ = (d- 1)/43,
where W3 denotes the class of all subsets of [d - 1] of size k.
The feature vector Φi a) is invariant across the state s. For each W(d-1)/1, we define vectors zy E IRd-1 as follows:
[= 1/va-1 for j U: [ = 0 for $ U.
Let 2 = ( : U Wa-1)/a We define the function I - 2, so that (a) E Z. Then, the feature vector ((s, a) is constructed as follows:
as, (Z(a) ,0), a a an; (0,11)
a0.
where 0 E Rd-1, For all V Vaja and (s, a) 8 I, it can be verified that Oy and ((s, satisfy the boundedness in Assumption 3.1 as follows:
(é(s,a)l & ( 1) ((dd-)) 11
10 & /(d 1)e² (- log H)² < V2 H =: B.
Let at (defined in the previous subsection) also have the maximum utility, i.e. aj argmax (0) Φ(8, a)) (note that -(:,-) is identical for all E S).
E3. Proof of Theorem 5.3
A good policy is one that quickly reaches the state H while remaining in the lower layers (i.e., with lower i). Recall that the item a has the highest utility and, therefore, the highest choice probability. It also has the best chance of quickly (4)
(4)
reaching the state TH while staying within the same layer. In other words, good policy encourages the user to frequently select the item a e argmax, (Hh, a) argmax (mo))) (0) o(s, a)). Note that a unique due to the way the action space and transition probabilities constructed.
We formally restate Theorem 5.3 as follows.
Theorem F.1 (Restatement of Theorem 5.3, Regret lower bound for linear MDPs with preference feedback). Suppose that > 2, d > 6, H > 3, and K > max|C. (d'n - -)) HH + 1)?, C² (d- + H)/H; ; for some constant C, C" O. Then, for any algorithmm, there exists an episodic linear MDP Me with MNL. preference feedback such that the worst-case expected regret lower bounded as follows:
sup Eo,.. [Regret (Ma K)] = Ω (dVHK d /HK) p.p.w
Proof of Theorem 5.3. Fix and μ so that we can omit the parameter dependency of P and P throughout the proof. Based on the construction of the hard instance M discussed in the previous subsections, the following lemma shows that the optimal assortment at horizon h [H] is {ag, a
Lemma F.2. For any h e [H]. we have Aü, (ao, a.j.
Furthermore, we can bound the expected value of Q" for any assortment as follows:
Lemma F.3. For any (i) E A [H] x [H]. let a E argmax o(x (1) a) 0 A = (a an), and (1) a). For any + ac. we define
(0) E argmax AM (7.4
(1)
a')
+ Pa (2 1a V (0)+1) (2 (1
(8)
(1)
FA(*H42222 a') (H- a' a
(8)
(a VL (0)
(8)
(x)+1)
(x
(6+2) (8)
a²)
(H -)²²
H
a' a
53

---

Combinatorial Reinforcement Learning with Preference Feedback
Then, for any policy n, if K 4(d 5)2H(H 1)2, have
Σ (
la 10) A 1. a a
Now, we are ready provide the proof of Theorem 5.3.
For any h [H] and any An E A. let ä argmax A, Maa) 6(2) a) T We also denote A. {āz, an} and ān ( Qn (TA, a). Recall that the index can be omitted for a because the transition and choice probabilities are identical across all 2h (1)
(H) given a The change in layer i only affects the scaling of rewards, and consequently Th .....h the Q-values, but the item that maximizes ((=)) (8) a) remains the same across layers.
By applying Lemma F.3, the value of policy æ in state oi can be bounded as follows:
(
Σ Pi(al (1) Q a) & Pi ( a a1).
(F.3)
DCA1
Moreover, according to Lemma F.2, the optimal assortment for horizon h [M] A a,,, Thus, the optimal value function in state zi (1) can be written follows:
(((=("))=
Σ A20 (ital (20))
a
where the last equality holds because (1,) an) 0. We denote 8и-2 can be either x (1) whether the item (for transition) is a or any ai, ao. Then, we have
zH+2 or x H4 depending
(3)
(V' - VT) (1(0) > Pi(alla)) (1) (1) (1) aaj) Pi (1)
A)) aaj a1)
(Pilatl (1) A1) Pi (1) An) (1 (1) at)
+ Pi (1) ( (Qi(a)) (a.a)))))))))) a(.ā))
(Pi(atile)) (1) A1) (a A1) Q/ (f af)
+ (1 lof aj1 + (1 at) (HI-1
+ (a Ai)
H
(1 + P2 , (i) (1 a1) (H (H-
1
H ))
H
-PPi(atlo)) ("(a))((",4) Pi 11( A1) 01 ( ai)
ai)
+ + (1) A.) (1) (1) |-
(1) aV (z)
+ + (1) An) IP -
(1) aj) Pi (sn an)
(H -
(F.4)
H
where the first inequality holds by (F.3). Note that, by construction, for any h [H. we have
Q1 , = H + 1 a.i))
H
Pa ( , Anw >
(1)
1
H
1 + H (1) (2) ,, = =1 (d 5)4, (x
1/H +
PA ai) - PF
(1) (1)
(1) an) (d 5) (ur, an.)
(F.5)
54

---

Combinatorial Reinforcement Learning with Preference Feedback Hence, by plugging (F.5) into (F:4) and applying recursion, we get
(Vi ((") (21
H 111
H
Σ (aa 1 ,4) - (arla (1) .Am))
-(1- 8 (at - 5)4))
H
H +
Σ ((d - ر)ه an))
H h
H
((1- - d (d - 5)4)) h-1
H
H H++1
Σ
(H (H-h) h)
((1 )
H
h
d (d 5)4)) h-1
(F.6)
HVK h-1
Furthermore, since H and 3(d - 5) & f= 1/H, we have
h
H
H+1
3
H+1
H
+
10'
((1 8- -ddh -515) h-1
46
H
1
3
(F.7)
3
3
Therefore, by substituting (F.7) into (F.6), and considering the terms where H/2, we obtain
H
1/2
(V' - (2) (z(1))
1
Σ
Pa
AAA - (a (2) An)) + Th (1)
((d 5) - (uin, an))
20
20
H/2
1
Σ
Ph(af l 2 AAA (a 1 An)
max weZ
(n a) (er an>
(F.8)
20
20
MNI. bandit regret
linear bandit zegret
On the right-hand side of (F.8), the first term corresponds to an MNL bandit problem. Recall that |A] =Ahnl = and, by construction, we have
exp (p( (1) .aj)) TA)TTi
exp (0(0))) (1) an) TO)
(1) wh AAA) 1/H + exp Mahh TA;
(1) An)
1/H + exp (61)) an) T0p
(1)
Hence, this corresponds to an MNL bandit problem with a maximum assortment size = 2, where the attraction purameter for the outside option (the constant the denominator) 1/H.
Furthermore, the second term on the right-hand side of (F.8) represents a linear bandit problem. To sum up, the learning problem is not harder than minimizing the regret Ω ((H/2) MNL and linear bandit problems.
To bound each term of (F.8), we introduce the following propositions:
Proposition F.4 (Regret lower bound of MNL bandits, Lee & Oh 2024). Let vn denote the attraction parameter for the outisde option. Let d be divisible by Suppose K > C- d - 1) for some constant C> 0. Then, in the uniform reward setting (where rewards are identical) with the reward for the outside option being zero, for any policy and the MNL preference model parameterized by O, there exists a worst-case problem instance such that the worst-case expected regret lower bounded as follows:
V / - 00 M-1 dv K
sup E. MNN.BanditRegret ()] = Ω
Proposition E.5 (Lemma C.8 in Zhou et al. 2021a), Fix 0 < 1/3. Consider the linear bandit problem parameterized with a vector μ E (-A, A) and action set I = (-1,1]d. And the reward distribution for taking action a E I a Bernoulli distribution denoted as B( + (p, a)). Let K be the number of time steps playing this bandit problem. Assume K 2 de d2/(28)
55

---

Combinatorial Reinforcement Learning with Preference Feedback
and A / Then, for any bandit algorithm B, there exists ja such that the expected pseudo-regret of B over K steps is lower bounded as follows:
dv Kō
F Linear Renieeerrann K)]
8v2
where the expectation is with respect to the reward distribution that depends on Ja.
Now, by using Proposition F.4 and F.5, we can bound the regret as follows:
H/2
1
(hhaaio0h (A)) - Ph (ān /2/ Ani)
sup H,,,, [Regret (Mo K]]
sup
Ee
9 p.
20
9
1=1
//2
K
(mn, a) (Hens an> )
Σ
Σ
+
sup En
max aEE
20
/
= Ω (dv (dvHK + d (HH)
where, in the last equality, we use vo = 1/H, M = 2, and I/H. This concludes the proof Theorem 5.3.
F.4. Proof of Lemmas for Theorem 5.3
F.4.1. PROOF OF LEMMA F.2
Proof of Lemma F.2. For any i E [H]. we can write the optimal Q-value in state (4) at horizon h E [M] as follows:
(a (8)
th a) V Vit ( +
(x (i)
a)
(H- 1-1
H1 a = a
Qh a)
2' 17
+ Pa (I h41 [h a)V (=(+)) (# (1+2) (1)
((+1) (
2h
(H-hW/+)
11
a a a0:
0,
ag.
First, we show that for any (i, h) E [H] x [H].
we have
(1 a) Σ
Pa AN) a'), Vae AhV(a))-
(F.9)
a'EAt
We prove this by contradiction. Suppose there exists Aj, such that (1
(1) a) >ivea Pa(a'Izh (9) P (A)
( a').
In that case, removing the item a from the assortment A%, results in higher expected value of Qú This contradicts the optimality of Ar. Therefore, (F.9) must hold.
By the definition of Th (1 a). for any a E D.(aj, we have
i-1
(H - -hy'-1
(1
+ PA
(++1) (1)
h+1 2h ( + PA (z (1+2)
h
H
(H -hl H+2
H
Pn
PA H
H
(x
(i)
where the first inequality holds since Vi (i-1)
[+11
& (- and the second inequality holds due to the fact that ( (6)
Vitta (1 (442) (H-b)='- and Pa
(i)
(i+2) (4) PM 2 at)
Since Q7 (x at)) has the highest value among all items, the optimal assortment Aj, should include aj, Thus, we have
(1)
aj, ag E AI. In other words, when A (a an). the condition in (F.9) is satisfied. Thus, we begin with A = =[aj an) and check if there exist item o a an that can increase the expected value of Q To this end, for A {aa,, ag),
get
Σ 1A a') = (a(a (1 at) > (2 aj),
(F.10)
56

---

Combinatorial Reinforcement Learning with Preference Feedback
where the equality holds since Q7 (1i aa) O, and the inequality holds by the definition of y/
(1)
H
exp (0(s, a) 0%) kE[H] sES AEA aifffo) I/H + exp (Ø(s, s, T
min min min min
1
1/H +1
exp
( (8) aa
0%
P (0 AA))
(F.11)
1/H exp (0(=)) an) TT0
(6)
Here, we rely on the fact that the sigmoid function is monotonically increasing to establish the inequalities. On the other hand, for any item a ag. we have
7d + PM(
[H h)7 1+
la m a)V ( + a)
H
H
/' + Ph
(641 a)V
(441
+
(1 - -h)
H
H
n' + Pa -
+ (H hiy
H
(
(H
h1)
+ -
7.
H
H
(1 al):
(F.12)
where the second inequality holds because V (1 (++1)) < (H-hhn PA P /- a) second equality follows from the fact that VV (2 (8)
((+2)
a) & (2(4/42200/ (1) aa). and the
H
h+1 = (
(i+1) by construction.
Combining (F. and (F.12), when 4 = (a%, ao), for any item a * a ag. we get
Σ a' e'e 4g
Pa ( A a/) > Q1 a).
Since (h a) for a * at, ap is not greater than the expected value of T7 for Aj, adding any item a * aj, ag to Aj does not increase the expected value of Qn. This confirms the optimality of A/--
F.4.2. PROOF OF LEMMA F.3
Proof of Lemma F.3. For any E [H], we can write the Q-value for the policy π in state 2/
horizon h [H] as follows:
# + ( (i)
1 1 a)V ( + PP(4
(H- H a a
Q (1h
a))
2'
1 + (x(())))) (i)
h+1 2h a)V (++1)) + (x
h+1
h
(1)
a
(H-h)
H-hhy h
11
a a a0:
0,
a ag.
We provide proof by considering the following cases: Case (i) ai.3 E A. Recall that, by (F.11), we have
exp ((x (1) TT;
H
(F.13)
1 + H
1/H + exp (00//² (3)
T
57

---

Combinatorial Reinforcement Learning with Preference Feedback
By multiplying Q7 (0) a a') on both sides of (F.13), we get
exp (ola)) (4) an)
T 0% (%7 (8) , a')
2. VT(a a') &
1/H + exp (o(ah"aa)
Σ exp .a) att
a) 01) 7 (T(a a a') (1/H + exp (olah f. aa)) Ta)) 0)))
+
exp (olof) .a) a0T)) oxp (o(a)) an) T0:) @n(a ( ai)
aa)
exp (b(ah (1) an) TO:) +
Σ
r exp (o(ah)) .a) a)To0) @xco)" al)
1/H + exp ( an) TO))
(1) an) [ + Σ exp (d(ah) (0) a) 0i)) exp (olok) TajToi 0i 1/H + exp (0(0))
<
aEA) a0)
2% (1)
(1) a/. a')
exp (o(0%) an) TT:) (T)
(8)
(1) aj, a() + Eiv Al(a) EieAl exp (ola) aa) (0) a())aa))))))) a')
1/H + 2ied)(oo) exp (o(o)/, a) TO0
(1)
exp (xp(d (1) a 07 Q7 (1) a
(F.14)
1/H + exp (0())² at) 07)
On the other hand, by the definition of Ộ7 (2/ (t) ai, a'), for any a' # ai. au, we have
(H - 1))t-11)
( ( a') x7 7.
+ PA PA V PA a')
(442) (
H
H
7/
a') (H - -hyp
+ PM
(i)
10 aN V ( PM (1+2)
(8)
H
H
(H hyp't1
> +
+P
// V') (1 + ( 2h
(422 a)) H
(
(F.15)
where the second equality holds since VV 1 (2/+11 = V (=+((1/+11) (++1)) ), and the inequality holds because, for K > 4(d HH + 1)2, the following inequality holds:
(1) P ( + PP (1+2)) (8) a() (H -hyttt
H
& &Pa(o!0) 6 a ((t))) + (1 a²) (H - -h)?
H
+ (PrCo 10
10 a') - (1 10 aj) Vit & (1
(1+2) H+2 Io a')
-h)
H
Specifically, if the upper bound of the lent-hand side is less than or equal to the lower bound of the right- side, the inequality holds. To demonstrate this, we have:
(Pa(oRhilef 2 a') a')
( ( aii) Vī- & 2(c 5)A
(H h)
(F.16)
H
58

---

Combinatorial Reinforcement Learning with Preference Feedback
i
H+1
and, since 7
H 1++1
To we get
3
1+11
(H- - h)) (7--
(H - -h)
PR(TH42
(6+2)
h a')
3 (6 (nt -5)A)
H (1 (1-11) (1)
H42
H
(H - h) 3 1
11 (d 5)A}
(F.17)
H
10
H+1
Combining (F.16) and (F.17), and rearranging the terms, we get
(d 5) (2
3 10(H +1)
3
10H(H+1)
which holds when K3 > 4(d - 5) + 1)². This explains how the inequality in (F.15) is satisfied.
(+) argmax ( (1 (8) a) ai.- Note that a is unique due the way the action space and transition
Let a probabilities are constructed, Then, by combining (F.14) and (F.15), and using the fact that Q7 (a,) ao) we obtain that
(9)
Σ Ph(al=// (0) (1
( a) &
Σ
(a(a
(9)
A)Q (3 (4) a
nEA
exp
(0(2)) (6) )
T
0% @7( a a
I/H + exp ((2))
(1) a T0
m8X exp (x(h)²
(i) a)
07)) 27 (1/h (1) ah, kh)
1/H + max exp
dxx a) TOO
where the first inequality holds since a. is the action that maximizes the Q-value. The second inequality follows from (F.14) and (F.15), and from the fact that (1) definition of aj.
(1) ( Th(a (0) an) (17 a a.). Finally, the last equality holds by the
Case (ii) a². $ A.
Again, by (F.1) I), for any A E A, we have
exp
(b( aa) TT=
7 min asA((ao) 1/H + exp (6(2)/ (6) a) T
(ax0 exp (0(1/))
(1) a) 0%
1/H + (00) exp (120) a) T07;
(1)
((xa exp 0l a) 07
(1)
1/H +2n+ >i exp (00;;)
(4) aa)
1/H + max a exp
(11//²² a) To;
(1)
Emed((an)) exp (0(/)) (1) a) 0%
where the second inequality holds since the sigmoid function is monotonically increasing function.
(i) We denote a argmax Maoo sides and rearranging terms, we get
(1)) a). Then, multiplying (77() (6) an a()) (note that (1)) a a²) on both
EoEA)(Eu) exp ((x)1)) (1) a) T0P) 7. (x) a a/ (0))
1/H + EaEA exp (0011)) .a) TT:;
max exp (0(z))) (1) . a) T Q7 (0) at, a())
1/H max 1 (oo) exp (0 (1) a) 07
59

---

Combinatorial Reinforcement Learning with Preference Feedback
Recall that for any a' * a/ ao, we have 7 (1(h, a') 2
Q ( a') by (F.15). Thus, we get
Σ
Pa (8) ( (1) a) <
(ala AAQ (=h )
aEA
A
(a A)7 2% ( aj. ana)
aEA
a exp (B(zh)) aaTT) 2% (a/h (6)
a k
1/H H + Aa exp (b(2/h (1) a) 0%
This concludes the proof of Lemma F.3.
G. Numerical Experiments
1
1-
1
N N
81
84
N
N
N
1
Figure G.1: The "online shopping with budget" environment with |S| Each state represents the user's budget level of 2,2,3,4 4, or 5. The solid line indicates the transition when the user purchases actual item (with reward of (i/100N) + f/(()) (H), and the dashed line shows the transition when the user does not purchase any item (with a reward of 0). The initial state is $3.
In this section, we empirically evaluate the performance of our algorithm, MNL-VQL, linear MDPs. We consider an online shopping with budget (refer Figure G.1) environment under linear MDPs and an MNL user preference model. We denote the set of states as S {81, {81,--.,8 8 and the set of items I {a1,-- --.------ AN 0o] (ag denotes the outside option). Each state 9j S corresponds to user's budget level, where larger index j indicates higher budget (e.g., $|S) represents the state with the largest budget). The initial state is set to the medium budget state $1S1/21- Furthermore, we let the transition probabilities Ph. rewards rh, and preference model Pn, be the same for all h [H]. and thus we omit the subscript h.
At state sy. the agent offers an assortment A E A with a maximum size of M. The user then either purchases an item a; E or opts not to buy anything, represented by the outside option ag E A. Then, the reward is defined as follows:
If the user purchases an item 0 E A, the reward is: r(sj:a;) (TobN /
If the user does not buy anything (ag). the reward is: r(sj, 0o) = 0.
The reward can be regarded as the user's rating of the purchased item. It is reasonable to assume that, at higher budget states, users tend to be more generous in their ratings, leading to higher ratings (rewards). And the transition probability is defined as follows:
If the user purchases an item 0g E A, the transition probability is:
i P(sminG++ a.) = 1 N
and P(smax(-- a.) i N
If the user does not buy anything (ag), the transition probability is:
P( P(smin(++1/S))lss..o an) =
If the user does purchase an item, the budget level decreases with a certain probability that depends on the chosen item. Conversely, if the user does not purchase any item (og), the budget level increases deterministically.
60

---

Combinatorial Reinforcement Learning with Preference Feedback
Myoptic
LSVI-UCB
MNL-VQL (ours)
N 10, |A| 637
0.089
0.136
0.463
N 20, 21, 699
0.097
4.861
0.526
N 40, A 760, 098
0.113
453.641
0.620
Table G.1: Average runtime (seconds) per episode for M 6.
We construct the feature map (s, a) (for linear MDPs) using SVD. Specifically, the transition kernel IP(-),-) e R |||]|||s has at most [S] singular values, and the reward vector r(-,)) :) E | has one singular value. Consequently, the feature map (s, a) Rhin lies in space of dimension [S] 1, i.c. diin | +1
For MNL preference model, the true parameter 0* e Rd, and the feature ((s, a) IRd (for MNL preference model) are randomly sampled from d-dimensional uniform distribution in each instance.
We set K 30000, H 5, M 6, ||| 5, d (feature dimension for MNL preference model), dinn 6 (feature dimension for linear MDP), N {10, 20, 403 (the number of items), and | Σ IM=1 = (A) (637, 21699, 760098) (the unweighted regression
number of assortments). Moreover, for simplicity, we set a in our algorithm. As result, to estimate the Q-values.
We compare our algorithm with two baselines: Myopic and LSVI-UCB (Jin et al., 2020). Myopic is a variant of myopic algorithm that selects assortments based
OFU-MNL+ (Lee & Oh, 2024) adapted for unknown rewards. only on immediate rewards, ignoring state transitions. LSVI-UCB (Jin et al., 2020) treats each assortment as a single, atomic (holistic) action, requiring enumeration of all possible assortments. To demonstrate the effectiveness of our approach, we also include the performance of the optimal policy (Optimal) to highlight that our algorithm converging toward optimality, We the algorithms 10 independent instances and report the episodic return across all episodes.
Figure demonstrates that our algorithm significantly outperforms other baseline algorithms. And Table G. shows that our algorithm maintains robust runtime performance even as the total number of assortments |.A] increases. Although the runtime of Myopic is approximately 5.3 times faster than ours, its performance substantially worse, converging to a suboptimal solution. This underscores a key limitation of myopic strategy-it can completely fail in certain environments, highlighting the importance of accounting for fong-term outcomes. Additionally, the runtime of LSVI-UCB increases exponentially as N grows, because requires enumerating all possible assortments. Due to the extremely slow did not include its performance results for N = 20 and N 40. Instead, for these cases, used
runtime of LSVI-UCE, dotted lines to represent the average episodic return observed for N 10. Even for the smaller case of N 10, LSVI-UCB demonstrated the worst performance. Based on this observation, we suspect that its performance is unlikely to improve as N increases.
61


Reviews:
[{"review_id": "8a5DIKxhF6", "reviewer": "Reviewer_ofJq", "summary": "This paper studies a combinatorial reinforcement learning setting in which an agent repeatedly offers a subset (assortment) of items and observes the user’s choice according to a multinomial logistic (MNL) model. Key challenges include (1) learning long-term (multi-step) item values rather than merely single-step rewards, and (2) preserving computational efficiency in selecting an assortment optimistically from an exponentially large set. To address these, the authors propose MNL-VQL, an algorithm that uses a linear (contextual) MNL model for user preferences and general function approximation for item values. They provide theoretical guarantees on regret, including a nearly minimax-optimal bound for the linear MDP case.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for acknowledging the value of our work and providing a positive evaluation! We will address your questions below.\n\n---\n### **Additional real-world data experiments**\n\nAs 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.\n\nThe 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.\n\nIn 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.\n\nFor 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.\n\nWe 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\\\\%$.\n\n- We provide a link to the experimental results here: [[Link]](https://rebrand.ly/pyss7cc)\n\nThe results demonstrate the superior performance of our algorithm, highlighting its practicality for real-world scenarios.\n\n[1] Shuai Li, Tor Lattimore, and Csaba Szepesvari. Online learning to rank with features. In International Conference on Machine Learning, pages 3856–3865, 2019.\n\n---\n### **Additional realted works**\n\nWe 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:\n\n*\"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.\"*\n\n---\n### **Question**\n\n> *Is the exploration method (Line 20) effective? compared to other classic exploration methods like UCB and TS?*\n\nWe can evaluate the effectiveness of the exploration method (Eqn.(9)) from two perspectives: statistical and computational efficiency.\n\n- Statistical efficiency:\nThe 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.\n\n- Computational efficiency:\nSince 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.", "claims_and_evidence": "Authors claim \"This is the first work to provide statistical guarantees in combinatorial RL with preference feedback.\" From the literature review, this claim is true while some important related works are missing.", "methods_and_evaluation_criteria": "This paper proposes the algorithm, MNL-VQL, that learns both: the MNL preference parameters (how likely each item is to be chosen), and the long-term value of each item using value-based RL techniques (with function approximation). Ensures computational feasibility by carefully separating the MNL-utility estimation from the state-value estimation. The key novelty is how it maintains “optimistic” and “pessimistic” estimates of item Q-values under unknown item values, and then constructs optimistic MNL utilities in a way that still admits polynomial-time optimization over the combinatorial action set.", "theoretical_claims": "I didn't carefully check the proof.", "experimental_designs_or_analyses": "The paper includes an experiment in a synthetic “online shopping with budget” environment. Each state represents a user’s budget level; the agent recommends an assortment, observes which item is selected (if any), and the user’s budget transitions based on the purchase.\nHowever, the experiments don't include the real-world datasets and bandit-based baselines.", "relation_to_broader_scientific_literature": "Provide new theoretical insights to the combinatorial RL/Bandit literature.", "essential_references_not_discussed": "The following two works also study combinatorial action space in bandits and provide the theoretical guarantee. Authors should include them into related works.\n\n\n[1] Multi-facet contextual bandits: A neural network perspective. KDD'21\n[2] Combinatorial neural bandits. ICML'23", "other_strengths_and_weaknesses": "The algorithm’s regret bounds are clearly laid out, with a special focus on minimax-optimal results in linear settings; The paper avoids intractable enumeration of subsets by formulating the assortment selection via an LP-based approach, making it feasible for moderate I. However, the empirical evaluation is relatively weak, given the synthetic data and a few number of baselines.", "other_comments_or_suggestions": "No", "questions_for_authors": "(1) Is the exploration method (Line 20) effective? compared to other classic exploration methods like UCB and TS?\n\n\n(2) The following work are also related to combinotorial bandits, can author add them to related work as well?  \n[1] Multi-facet contextual bandits: A neural network perspective. KDD'21\n[2] Combinatorial neural bandits. ICML'23", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "c49KU92nW0", "reviewer": "Reviewer_HZFp", "summary": "This paper considers the combinatorial RL with a MNL preference distribution, where given an combinatorial action(assortment), the final action is sampled from a linear MNL model. In this setting, the learner needs to estimate both the underlying MNL model parameter and the transition dynamics, as in the standard RL task. Authors provide an algorithm that combines the weighted regression routine for value estimation and online mirror descent for learning MNL parameters. This algorithm works for general non-linear value function classes with finite generalized Eluder dimension. Corresponding lower bound results are also provided in linear value approximation setting to illustrate the optimality.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.", "claims_and_evidence": "Yes. Most statements made in this paper are clear and well-supported.", "methods_and_evaluation_criteria": "The proposed algorithm is well-founded, the authors also provide an LP formulation for assortment optimization to address computational challenges, making the algorithm applicable to real-world problems.", "theoretical_claims": "I didn't go through the proof in detail since it is too long to check. However, the theoretical guarantee provided for the algorithm make sense for me  as both its value estimation block and the MNL parameter estimation block are well supported by existing literature. And the final regret bound can be decomposed to the summation of these two parts.", "experimental_designs_or_analyses": "No.", "relation_to_broader_scientific_literature": "The topic studied in this paper is novel to both combinatorial RL and MNL bandits, I believe it contributes to both areas.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Other Strength:\n\nIt is somewhat surprising that the authors directly establish a relatively complete set of results in a newly proposed setting, which allows for non-linear function approximation and achieves nearly optimal regret. This makes the contributions of this paper solid.", "other_comments_or_suggestions": "No.", "questions_for_authors": "I don't have additional questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "9ggNeaXCay", "reviewer": "Reviewer_GikG", "summary": "The paper addresses the problem of combinatorial reinforcement learning with preference feedback, where a learning agent offers an assortment of multiple items (an action) to a user, whose preferences follow a multinomial logistic model. This framework is particularly relevant for applications like recommender systems and online advertising, where long-term user engagement is key. The paper identifies two main challenges: the unknown value of each item and the difficulty of ensuring optimism while maintaining tractable assortment selection in the combinatorial action space.\n\nTo tackle these challenges, the authors propose an algorithm called MNL-VQL, which is both computationally and statistically efficient. The algorithm estimates optimistic item values using point-wise optimism under general function approximation and selects assortments that ensure sufficient exploration and optimism. The paper also establishes the first regret lower bound for linear MDPs with MNL preference feedback and shows that MNL-VQL achieves nearly minimax-optimal regret.\n\nMain contributions from the paper are:\n\n- Introduction of MNL-VQL, an algorithm that addresses the challenges of combinatorial RL with preference feedback, ensuring computational and statistical efficiency.\n- Regret upper bound and Minimax-Optimal regret using MNL-VQL (linear MDPs)\n  is the feature dimension of the linear MDPs, and establishes a matching regret lower bound, showing the minimax-optimality of the algorithm.\n- Development of analytical techniques to prove optimism and related results, avoiding naive combinatorial enumeration by reformulating the optimization problem as a linear program.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your time to review our paper and your valuable feedback. \n\nIt 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.\n\nNevertheless, 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. \n\n---\n### **Additional real-world data experiments**\n\nThe 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.\n\nIn 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.\n\nFor 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\\\\%$.\n\n- We provide an anonymous link to the experimental results here: [[Link]](https://rebrand.ly/pyss7cc)\n\nThe results demonstrate the superior performance of our algorithm, highlighting its practicality for real-world scenarios.\n\n[1] Shuai Li, Tor Lattimore, and Csaba Szepesvari. Online learning to rank with features. In International Conference on Machine Learning, pages 3856–3865, 2019.\n\n---\n### **Comparison to other baselines in the experiments**\n\nThe 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.\n\n---\n### **First theoretical guarantee in combinatorial RL with preference feedback**\n\nWe 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.\n\nAlthough 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.\n\n---\n> 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.", "claims_and_evidence": "Most of claims reported in the paper are supported by clear and convincing evidence. Notwithstanding, there are a few areas where the evidence could be strengthened.\n\n** ''Full'' Supported Claims**\n\n1. Introduction of MNL-VQL algorithm:\n - The paper provides a detailed description of the MNL-VQL algorithm, including its steps and theoretical foundations. The algorithm is well-supported by the mathematical formulations and the step-by-step explanation provided in the paper.\n\n2. Regret Upper Bound:\n - The paper claims that MNL-VQL achieves a regret upper bound. This claim is supported by Theorem 5.1 and the accompanying proof in Appendix D. The theoretical analysis appears rigorous and thorough.\n\n3. Minimax-Optimal regret for linear MDPs:\n - The claim that MNL-VQL achieves nearly minimax-optimal regret for linear MDPs is supported by Theorem 5.2 and the corresponding proof. The paper provides a detailed comparison with existing work to highlight the novelty and effectiveness of their approach.\n\n\n** \"Weaker\" Claims **\n\n1. First theoretical guarantee in combinatorial RL with preference feedback:\n - The paper claims to be the first to provide statistical guarantees in combinatorial RL with preference feedback. While the paper does provide strong theoretical results, it would benefit from a more comprehensive review of existing literature to ensure that no prior work has addressed this problem. The claim could be seen as overstated without a thorough literature review.\n\n2. Empirical validation:\n - The paper focuses heavily on theoretical contributions and provides limited empirical validation. While the theoretical results are strong, more extensive empirical experiments demonstrating the practical effectiveness of the MNL-VQL algorithm would strengthen the claim. The lack of more extensive empirical results may contrast the benefits of the proposed approach", "methods_and_evaluation_criteria": "Yes, the proposed methods and evaluation criteria in the paper make sense for the problem at hand.", "theoretical_claims": "No", "experimental_designs_or_analyses": "The paper primarily focuses on theoretical contributions and does provide limited empirical analyses.", "relation_to_broader_scientific_literature": "The key contributions of the paper  are closely related to several areas within the broader scientific literature, particularly in the fields of reinforcement learning (RL), multi-armed bandits, and preference modelling.\n\nCombinatorial RL involves selecting combinations or subsets of actions from a set of possible actions. Concerning prior works on the topics, previous studies have addressed problems within this setting, particularly in deep RL (e.g., Sunehag et al., 2015; He et al., 2016; Swaminathan et al., 2017; Metz et al., 2017; Ryu et al., 2019; Ie et al., 2019; Delarue et al., 2020; McInerney et al., 2020; Vlassis et al., 2021; Chaudhari et al., 2024). However, the authors of the paper formalize the concept of combinatorial RL with preference feedback, which had not been theoretically defined in prior work.", "essential_references_not_discussed": "Yes", "other_strengths_and_weaknesses": "Overall, the paper makes significant and original contributions to the field of combinatorial RL with preference feedback. The theoretical foundations are strong, and the proposed algorithm addresses important challenges.\n\n**Strengths**\n\n- Novel framework: the paper introduces a novel framework for combinatorial reinforcement learning (RL) with preference feedback, which had not been theoretically defined before. The development of the MNL-VQL algorithm is a notable contribution, addressing specific challenges in combinatorial RL with preference feedback that were not previously tackled. Such a framework is especially  relevant for applications such as recommender systems and online advertising.\n\n- Theoretical contributions: the paper provides strong theoretical contributions, including the first regret lower bound for linear MDPs with MNL preference feedback and nearly minimax-optimal regret bounds.\n\n- Detailed explanations: the paper provides detailed explanations of the algorithm steps, theoretical foundations, and proofs. This clarity helps readers understand the complex concepts and methods used. \n\n** Weaknesses **\n\n1. Lack of experiments: the main issue of the paper is the lack of an extensive empirical validation of the proposed algorithm. Including experiments on benchmark datasets and comparisons with more baseline methods would strengthen the claims and demonstrate the practical effectiveness of the algorithm.", "other_comments_or_suggestions": "see Other Strengths And Weaknesses", "questions_for_authors": "see Other Strengths And Weaknesses", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1JX19aojoS", "reviewer": "Reviewer_rH3e", "summary": "This paper studies combinatorial reinforcement learning (Combinatorial RL) under Multinomial Logit (MNL) preference feedback, where the agent selects a subset of items (an \"assortment\") at each step, and user choices follow an MNL model. Unlike traditional MNL bandits, which optimize single-step rewards, this work extends the problem to reinforcement learning (RL) settings, where decisions impact long-term rewards through state transitions.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your positive review! Below, we provide our responses to your comments and concerns. \n\n---\n### **Experiment**\n\n- **Additional real-world data experiments:**\nIn 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. \n   - A link to the results is provided here: [[Link]](https://rebrand.ly/pyss7cc)\n\n- **Request for additional ablations:**\nWhile we appreciate the reviewer’s suggestion regarding ablation studies, we believe they may NOT be essential for the following reasons:\n   - **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.\n\n   - **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.\n\n- **Confidence interval:** In Figure 1, the shaded area represents $\\pm1$ standard deviation. \n\n--- \n### **Computational efficiency**\nOur algorithm enjoys polynomial computational complexity with respect to the number of items $N$, making it highly efficient both computationally and statistically.\n\nThe 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.\n\nMoreover, 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.\n\nAdditionally, we reported the runtime per round in Table G.1 (and provided results for larger item sets at [[Link]](https://rebrand.ly/pyss7cc)), 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)$.\n\n---\n### **Techinical novelties**\nOur key technical contributions are as follows:\n1. A **novel assortment selection** strategy that alternates between optimistic and pessimistic utility estimates.\n2. The **first** to incorporate both **unknown item values (rewards)** and **nonzero outside-option item values** in the MNL choice model.\n3. A $\\sqrt{H}$ **improvement** over naïve summation of $H$ bandit regrets.\n4. A fine-grained regret analysis for general function approximation.\n\nFor further details, please refer to Section 5.2.\n\n---\n### **Generalized Eluder dimension**\n\nThe 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.\n\n---\n### **Others**\n\n- **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).\n\n- **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.\n\n- **Intuition behind switching utilities**: We design an optimistic strategy where the estimated value is likely greater than the true value.", "claims_and_evidence": "Most of the paper’s key claims are well-supported by theoretical analysis and synthetic experiments. Some claims, particularly those regarding computational efficiency and variance-weighting, require additional empirical validation.", "methods_and_evaluation_criteria": "The proposed methods are well-motivated and aligned with the problem setting. While Online Sensitivity Sub-sampling is proposed to reduce computation, there is no formal complexity analysis comparing its efficiency with baselines like LSVI-UCB.", "theoretical_claims": "The theoretical claims and proofs are mostly correct, with well-supported regret bounds and sound reasoning behind optimism-pessimism switching.  \n\nSome extensions (e.g., generalized Eluder dimension) require further justification or comparison, e.g., compare regret bounds using standard vs. generalized Eluder dimension since it is unclear if this extension significantly improves regret bounds compared to existing Eluder dimension results.", "experimental_designs_or_analyses": "1. No empirical validation for the optimistic-pessimistic strategy; perhaps add an ablation study comparing optimistic-only, pessimistic-only, and alternating strategies.\n\n2. The experiments only use synthetic data; should also run experiments on real-world datasets to test robustness under realistic conditions.\n\n3. The action space in the experiments seems relatively small compared to real-world combinatorial RL settings.\n\n4. The paper introduces multiple novel techniques (e.g., variance-weighted Q-learning, Online Sensitivity Sub-sampling, alternating optimism-pessimism) but does not test their individual contributions. Does each component improve performance, or is the gain from just one or two?\n\n5. The results lack confidence intervals or statistical significance tests.", "relation_to_broader_scientific_literature": "The work extends MNL bandits (Multinomial Logit Bandits), a well-studied framework for recommendation systems and assortment optimization. Instead of focusing on single-step rewards (as in MNL bandits), the paper extends the model to long-term reinforcement learning settings.\n\nThe paper builds on literature in function approximation for RL, particularly when Q-values are learned in complex, structured action spaces.", "essential_references_not_discussed": "The paper generalizes Eluder dimension but does not compare its new regret bounds with prior function approximation methods in RL.\n\nThe paper proposes Online Sensitivity Sub-sampling but does not compare it with deep RL’s structured exploration techniques.", "other_strengths_and_weaknesses": "Other Strengths：\n\n1. The use of preference feedback in long-term decision-making is a meaningful contribution, as most prior MNL studies focus on single-step decision-making (bandits) rather than RL settings.\n2. The paper establishes tight upper and lower regret bounds.\n\nOther Weaknesses：\n\n1. The experiments are conducted only in a synthetic online shopping environment, without real-world datasets.\n2. The results largely build on existing work in combinatorial RL/bandits under choice models, and RL with function approximation. How does this approach go beyond simply combining prior methods?\n3. The paper lacks intuitive explanations for certain formulas, such as:  a. Why is the generalized Eluder dimension more suitable for this problem compared to the standard Eluder dimension?  b. How do the key mathematical principles of variance-weighted Q-learning influence its convergence?", "other_comments_or_suggestions": "1. The proof outlines failure cases where a purely optimistic approach can lead to biased Q-value estimation due to state transitions. The theoretical argument is strong, but an empirical ablation study would reinforce this claim.\n\n2. The model assumes fixed user preferences, which is unrealistic in many real-world settings. Many RL-based recommenders address evolving user interests, but this paper does not discuss or experiment with preference drift.\n\n3. The condition for switching between optimistic and pessimistic utilities is not clearly motivated. Add intuition behind this condition.\n\n4. Algorithm 1 Pseudocode: Step descriptions are too compact to follow easily.", "questions_for_authors": "1. The action space in combinatorial reinforcement learning grows exponentially, even with Online Sensitivity Sub-sampling. Can the proposed method efficiently compute the optimal policy? While the paper claims to avoid exponential computation, does it truly achieve polynomial-time optimization?\n\n2. Your method is designed for recommendation systems, yet all experiments use synthetic data. Why did you not test MNL-VQL on real-world datasets like MovieLens or Amazon Reviews?\n\n3. The paper claims Online Sensitivity Sub-sampling improves efficiency. What is the formal computational complexity of MNL-VQL?\n\n4. How well does MNL-VQL scale to large action spaces?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: All reviewers appreciates the novel framework and the theoretical results derived in this work. Details of algorithms and proofs are provided which make it a solid theoretical machine learning work. While the theoretical contribution may suffice for a conference paper, I would highly encourage the authors apply the proposed algorithm in some real tasks for the next version of this work (maybe a journal paper).
Decision: Accept (poster)