SlateFree: a Model-Free Decomposition for Reinforcement Learning with Slate Actions
Authors: Anastasios Giovanidis
Venue: NeurIPS 2022 Submitted (2022)
Keywords: reinforcement learning
slate
MDP
decomposition
recommender system

Abstract: We consider the problem of sequential recommendations, where at each step an agent proposes some slate of $N$ distinct items to a user from a much larger catalog of size $K>>N$. The user has unknown preferences towards the recommendations and the agent takes sequential actions that optimise (in our case minimise) some action-related cost, with the help of Reinforcement Learning. The possible item combinations for a slate is $\binom{K}{N}$, an enormous number rendering value iteration methods intractable. We prove that the slate-MDP can actually be decomposed using just $K$ item-related $Q$ functions per state, which describe the problem in a more compact and efficient way. Based on this, we propose a novel model-free SARSA and Q-learning algorithm that performs $N$ parallel iterations per step, without any prior user knowledge. We call this method SlateFree, i.e. free-of-slates, and we show numerically that it converges very fast to the exact optimum for arbitrary user profiles, and that it outperforms alternatives from the literature.

SlateFree: a Model-Free Decomposition for Reinforcement Learning with Slate Actions
Anonymous Author(s)
Affiliation Address
email
Abstract
We consider the problem of sequential recommendations, where each step an agent proposes some slate of N distinct items to a user from a much larger catalog of size K >> N. The user has unknown preferences towards the recommendations and the agent takes sequential actions that optimise (in our case minimise) some user-related cost, with the help of Reinforcement Learning. The possible item combinations for slate is (K) an enormous number rendering value iteration methods intractable. We prove that the slate-MDP can actually be decomposed using just K item-related Q functions per state, which describe the problem in a more compact and efficient way. Based on this, we propose novel model-free SARSA and Q-learning algorithm that performs N parallel iterations per step, without any prior user knowledge. We call this method SlateFree, i.e. free-of- slates, and we show numerically that it converges very fast to the exact optimum for arbitrary user profiles, and that it outperforms alternatives from the literature.
6
10
11
12
Introduction
14
15 In many real-life applications, an agent needs to optimally adapt to a random environment through the choice of multi-dimensional actions time. A specific, common scenario is that of a personalised recommender system (RS), which should pick a set of N > 1 items among much larger corpus of size K N, given the user's recent and past viewing history. An illustrative example this challenge to solve the top-N recommendations problem is Google's YouTube algorithm, where the current corpus contains several tens of billions of videos Gooddoo [2021] and the number of recommended items per view may vary (based on scrolling) but in general involves N > 20 items. In such applications the group of N items recommended per step often called a slate.
17
18
19
20
21
22
23 As Shani et al. 2005) observed, the RS problem is essentially of sequential nature. The recommenda- tion of specific slate some point in time offers not only immediate gains if some recommended item is clicked, but can also generate future benefits by guiding the user towards a path of more interesting items as the user session evolves. (Sani et (2005) formulated this problem within the framework of Markov Decision Processes (MDPs) (Puterman 1994]), and tried to solve it under strong assumptions of independence. Naturally, when the RS needs to learn unknown user prefer- ences, it can do so by observing user-item interactions over time, and the tools of Reinforcement Learning (RL) are most appropriate, see Taghipour et al. 2007 for an early effort.
25
26
27
28
29
30
31 The optimal slate selection problem per step is in fact combinatorial: the user's choice affected by
32 the combination (and possibly the order) of the items in the slate, not just their individual importance
33 to the user Aouali et al. [0021] In such control problems over long horizon, the challenge with
slate actions is that the corresponding combinatorial action space is immense and the search for
35 optimal solution quickly becomes intractable. Even for small catalog of size K = 100 items and
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

36
recommendation slate of size N = 4, there are (1) You Consequently, the number of slate actions in the YouTube example is astronomical.
= 4 million unordered slates as possible actions.
37
38
To tackle the dimensionality explosion in such value iteration algorithms, le et al. [2019] (motivated by previous work from [Sunehag et al.] (2015) have shown that the slate-value function can be exactly decomposed into K individual Q item-values, per state. Such decomposition could actually render cemporal-difference (TD) learning with slates tractable. However, this proposal is based on prior knowledge about the user behaviour given any slate and single item choice. In essence this is not a model-free algorithm. It can be implemented if either a user model is assumed, or if the user preference choice per slate is learned from history, which doubles the learning effort of RL and needs to keep in memory N (K) unknowns per user, one unknown per slate and per item choice.
39
40
41
42
43
44
45
Our contribution. We introduce in this work novel exact decomposition of the Q values for slates, into K individual item-Q values and propose a tractable TD-learning (SARSA- and Q-) algorithm, named here SlateFree, which allows to solve efficiently learning and control problems of arbitrary slate dimension N > 1 using value-iteration. The important difference compared to Ic et al. 2019) is that our decomposition is entirely model-free in the sense that it does not require any prior knowledge over the user behaviour, and it allows to include costs that depend on both state and action. The proposed decomposition without assuming any independence, simplifies Q-learning considerably:
47
49
50
51
52
(i) It keeps K state-item Q functions per state in memory, instead of (K) massive reduction.
53
54
(ii) The optimal slate in the exploitation consists of the Noout-of-K K items with best item-Q function.
The novel RL algorithm is based on definitions of state-item Q functions, item-costs and transitions. It performs N-parallel Q-updates per step, one per item included in the slate. This way, the relevance of an individual item is updated every time this is included in a slate. The method reminds of the independent learners in multi-agen systems, by Claus and Boutilier [998), one agent per dimension.
56
58
59
The SlateFree has considerable performance features. It can learn and take optimal actions over time for any unknown user behaviour. It shown to be insensitive to the slate-size N, thus allowing to scale for arbitrary dimensions. The MDP decomposition is proved in this paper to hold under certain assumptions: (i) the slates are unordered sets of distinct items, and (ii) the user behaviour is Markovian, i.e. the user choice is based only on the current state and recommended slate. Numerical evaluations of the novel RL algorithm show empirically that it finds the optimum even when the cost is a function of both the state and the chosen action-slate something not possible in other works.
60
61
62
64
86 In Section 2 we introduce state-item values as marginal quantities and prove the decomposition of the Bellman equations in the MDP setting. In Section 3 we present the decomposed SARSA- and RI.- algorithms, referred to from now on, jointly, as SlateFree. In Section f we show numerically the exactness of the solution compared to vanilla-RL. for users with various preference behaviour and illustrate significant performance improvements against SlateQ in Ie et al. [2019]. We also illustrate how SlateFree converges for any type of user and the convergence speed does not depend on the size of the slate. We further illustrate how the algorithm behaves in situations where the cost is a function of both state and action-slate. The code is available on Google Colab Slateliree Authors and here SlateFree Authors 2022bb.
67
68
69
70
71
72
73
74
2022a
75
Related literature. The established solution for static recommender systems is based on collaborative filtering, as in Deshpande and Karypis (2044) or matrix factorisation, as in Takács al. 2008). Since the problem is actually dynamic, Reinforcement Learning (Sutton and Barto (2018) is at the moment widely applied to propose more effective or more diverse recommender systems (Karatzoglou et al.) [,03]] Rohde et al. [2018). Zhou et al. 2020). WWrllp et al.] (2018). To overcome the curse of dimensionality in the action space a deep reinforcement learning approach is taken: Zheng et al. 2018 work with a value-based approach and approximate the Q-value by a neural network, whereas
76
77
78
79
80
81
82
Liu et al. 20206), Liu et al. [2020a] use an actor-critic architecture for policy-based opimisation, where the actor network outputs continuous feature vector, which can be mapped to an item, thus avoiding the discrete formulation.
84
85 RL problems with continuous and high-dimensional action spaces have been recently approached
86 by policy iteration methods. Deterministic policy gradient by (Silver al. (2044) is shown to considerably outperform standard policy updates. This method was combined with an efficient mapping to discrete actions by Dulac-Arold et al. [2015). so that problems like the search for top-N recommendations can be efficiently resolved. [Chnn et al. [2019] adapt the REINFORCE algorithm
87
88
90 with reward independence assumptions. de Wiele et al.
2020 work with amortised inference to
2

---

91
maximise over smaller subset of possible actions. Metz et al. [017]] propose an autoregressive network architecture to sequentially predict the action value for each action dimension, which requires manual ordering of the actions. Tavakoli et al. 2018 propose a neural architecture with many network branches, one for each action dimension. The special structure of fate-recommeenations has given rise to problem specific solutions, like the one by [Sunehag et al. (2015) who introduce a formulation that benefits from the fact that at each step the user chooses a single item, for a given action slate. Their approach cannot scale because it needs to keep memory one value-function per slate. In very interesting recent approach Ie et al.] (2019) show how the slate-value function can be exactly decomposed into individual Q item-values and introduce the method SlateQ. They construct optimal slates from the individual item-values by solving a Linear Program (LP) per step. As mentioned, their
92
93
94
95
96
96
99
100
decomposition is based on prior knowledge of user choice behaviour.
102
2
Decomposition of slate-MDPs
103
We first introduce the slate-MDP, defined as (S,A, and describe the process for the special
104
application of the recommender system. Time is slotted with current step t. The state S. = 8 at time
105
1 will be here the currently viewed item, the state-space S = K. is the full item catalog of size K.
106
But we can use more general states, e.g. the history of the last m-viewed items m >> 1, so S * K. is an N N-sized unordered slate of recommended items. The set of possible actions A is the set of all possible unordered N --sized slates, where in each slate w E AA no item is duplicated. Here, "unordered" means that only the set of recommended items in the slate is important, not their order. The state transition function P S x A x S -> [o. 1] is the probability, given the current state s and recommended slate w, that the user moves to state s', by either picking one of the recommended
107 The action At
108
109
110
111
112 items, or rejecting them and selecting some item from the search bar. The general cost function
113 is C: : S x A + I and À E (0, 1) is the discount rate. The objective is to find an optimal policy S x A + [0, 1] to minimise the expected cumulative discounted cost from any initial state E S, 115 which is the fulue-function of state a (alternatively one could work with rewards and maximisation)
V=(s) = E
1 =
(1)
116 In the above, E, is the expectation under given policy æ,, the current time-step is t and the cost at future step + k is Ce+A = ((St-k,44 A+++). The randomness is due to the user choice behaviour. We consider a stationary policy π,, which a distribution over actions given the current state. It does not depend on time f. This is randomised policy in general,
117
118
119
(w) == P [A, | Ss s] If the mass is concentrated on single slate-action w. the policy is called deterministic and we denote it by Tá (or just d). Given state s, it holds EveA(s) [w( = 1. Observe that we introduced an
E A(s).
120
121
122
action space A(s) per state s, because for our recommender application the currently viewed item should not be included in the recommendation slate.
123
The state-action function (s, w) of pair (s,w) S x A is the expected cumulative discounted cost, starting from state s, taking action w and following policy n,
125
Qx(s,w)= = E
X cctt S 8, A, =
(3)
126 From Sutton and Barto (0118) and Puterman 1994 we know that the state-value functions satisfy
127
the recursive system of Bellman equations (just policy x evaluation here), (s) E x A
(s,ww) = c(s,w) + A Σ IP [s
Σ (=
(4)
S'ES
w'EA(N")
= c(s, w) + AE (V*(')) S = 8, A(s) = w]
(5)
128
where in the last equation we replaced with the value function in s' because for stationary randomised policies it holds V=(s')= En'E T. (w') (s')Q=(s',,)))
129
130 The P [5'|1, w in ( models the random user choice behaviour when visiting state & and exposed to slate w. which is considered known in the MDP setting. Notice here, that the process is Markovian exactly because the user is Markovian, meaning that their choice is only based on the current state
132
and action and not the past.
3

---

134
2.1
Item frequencies, fransition probabilities, and state-item functions
135
For the decomposition we need introduce some new marginal quantities to shift the analysis from slates to items. Since the policy и is stationary and randomised, given state it randomly recommends among feasible slates, each containing a different set of items. Obviously, the item j K can appear in several action-slates.
136
137
138
Definition 1. The frequency of recommended item j K at state S, under policy n, is defined through the randomised probabilities of slate-actions in (2 as
140
J = P| = E A(s: = =s] =] Σ
P P"W]s]]
Σ wE)((a)
Ts(W)1(j E w))
(6)
where A(s: (i}) S A(s) is the set of actions state s, that necessarily include item j. The indicator function 1 E w) = 1 if j is included in the slate, otherwise O. What we call "frequency" is in fact the probability to randomly select some dlate-action that includes item j. when at state It holds,
142
ΣE jEK JEK wEA(s)
[e(w) E w) N, Vs E
144
where we use the fact that each slate contains N distinct items, i.c. there are no duplicates. Definition 2. The transition probability given item j inside the recommended slate is defined as Tpah [s PP(s' |s, w E A(s; (i})), vs 8, Vj E K.
145
148
For the transition probability given state s and some action including item j we prove three Properties:
147
Property 1. The single-item transition probability depends on the policy x. It satisfies,
PT [111,,]] = Σ
P['|s,w]] [ E EW)
((s)(s)
148
Proof. We can write the slate as w (w-j.
j) which contains item j and W-j are the remaining N entries. It holds due to conditioning, that
149
P. is' w ت
Pa [s w|s,]]
([s'|s.w] w] = P[s'|s, (w-
P [ز
P [w]ss
150
where the superseript ı is included, because IP [w]s. 1l depends on the policy æ. Using this expression, IP [T
Σ
P[s' Isa'|s, [w]s.
(E)((s())
WEA(=())
Summing at the left-hand side over all that contain j. we get the marginal pst PM [s||s,]].
151
Property 2. The single-item transition probability is a marginal probability of and it holds
152
[[(W)[( E W = WEA(()
Σ
E Vj K.
(10)
Proof. It holds that T. (w) = PT [w|s]. We use the conditional probability formula
Σ (.(w)l(je E (P)
Σ P(s',wls)1(j Ew)
wEA(s)
wEA(s)
=PP(s -P A(s: (1))ss)
PPs' (is'ss,we
E A(s; (i}) Plw E A(s: [1) [s'ss. Ar..
D Def
PTT
0
Property 3. Ifr 0, then P[s is a probability mass function, Eves PT 1T = 1.
155
Proof. Using Definition 2 and Definition I we can write
Σ
Def
Pls's,, A(s:())))
Σ s'ES
Pls' E A(s; [i)lss
Plw E A(s; (i))ss]
e'ES
10 1(jew) (EW)PPss Σ Σ S'ES WEA()))))
PIw E A(s: (1)1ss
Def
Σ T.(4)I(jEW)
Σ P[ =
1 1.
wEAls)
''ES

---

156
Definition 3. The marginal cost-item function c² (s, that depends on policy is defined as
re
Σ
T=(w)c(s,w))1i E w), Vs S, EjEK.
(11)
wEAls)
157
In the special case that the cost is just function of the current state, c² (s. = c(s).
158
Finally, we give the following special definition for the state-item function {s, Definition 4. The state-item function Q (s. is defined from the state-action functions Qx (s, w) as
159
(=)))()))) = E Qx. EW) Vs,j E S.
(12)
WEA(s)
180
Notice that this definition is different from what would be the most natural one, i.e. to be the falue-function starting from state s, and taking some initial slate-action that necessarily includes item j and following policy æT The Definition is in fact a marginal quantity, i.c., the expectation over all state-value functions that include item; j normalised by the frequency rā. >
161
182
183
Notice here that for items such that 'x. 0, the state-item functions (=, j) are not well defined. We will see next that this not actually a problem for the decomposition.
165
186
2.2
Decomposed Bellman equations
167
Theorem 1. [SlateFree-MDD
The Bellman equations in 4 for state-action functions with slates
188
Qx (x.ww) w), are equivalent to the following system of equations with state-item functions Qn (8, (, j) from Def cost-item fanctions cost-itemfiacttions from Def.
189
3
and transition probability given some item j from Def.
( [r2
Qx(s.j)= + P'
N
As S, VjEK. (13)
KEX
170 If the cost is a function of just the current state, we replace in the above by c² (*( = c(s), so that
171 the cost does not depend the policy.
Proof. We multiply both sides of (4) by [T(W)](j E w) and sum over all feasible slate-actions
Σ
Tr(w)1(j E (),x = Σ
( w
(EA((s)
wEA(s)
+
Σ
T. (.(w)I(jjw))
Σ s|s s'ES
wEA(s)
Then, replace the left-hand side by the function Definition 4 the first term of the right-hand side 174 by the cost-item Definition 3 and in the second term we use Property 2 to find
The (c((s.)) (o(s,j)-c5(s5 - Σ pa -
(is P' = 0.
(14)
S'ES
175 Now, use the equality V=(s')= EwEA(S)) Ter Qn (s', w), multiply from both sides by 1 w) and sum over K. We use the fact that the slate size is N and again Definition so we get
=
178
I (=())((kW)) = KEK
Th (w) E Va(s')
Σ KEK
N
NEKWEA(S))
By replacing the above expression for (s('') in (14 we get the expression in 13 as long as r",, > 0 for the (s.j) pair. In the case that re, = 0 for some pair (5, L), notice that regardless of its value (3, E) oc, it will always contribute 2x, e)
when found the right-hand side of (3). hence the pairs with zero frequencies do not affect the equations of others. For their own state-item
(5,
181 value, any solution (=(5,)) () - e(s) Eves pa [5'18, VV (8') = x < oo satisfies (4), hence also
the one for A 0. This way result in the validity of [13 for any possible state-item pair. D
5

---

183
2.3
Optimality equations
184
We know from Puterman 1994, Prop.6.2.1] that the discounted MDPs always have a stationary deterministic optimal policy. We denote from now on deterministic policies by index d (we may omit T) and the optimal policy by d' (we may omit d). Then by definition,
185
186
1, for unique slate (*))) E A(ss)
7 (w) -
(15)
O. Vo # (s) and w E A(s)
187
A special case is when we follow the optimal deterministic policy, so that 1, for (s) = arg minwe Qe (s,w)
(
(16)
0. otherwise
188
When more than one action-slates have the minimum Q(s, w) ties are broken arbitrarily. For the deterministic and optimal policies the value function starting from state s equal
189
Va(s)= = Σ Qa(s,) = (s)) opt. Va- (s) = min Qa- (s,(s. (17) wEA(s))
WEA(())
190
Theorem 2. [Optimal SlateFree-MDPJ The Bellman optimality equations for slates are equivalent
191
to the following system of equations with state-item functions from Def. 4 cost-item functions from
192
Def. 3 and transition probabiliyy given some item j from Def. 2 under the optimal policy π = =d'
Qa (s,j) = cs, + X
Σ
Te"
[s'|s,]] min Qu (s',e),
E. VjEK
(18)
EEK
SEES
and it holds Qa (s.j) Va (s), Vj E (s) inside the optimal slate. Also, d¹ (s,j) ca(s, (o(ssw"(g wn (s))
194 for j in the optimal slate, For & wn (s) the cost c² (s,() can be any convex combination of the slate-
costs ()s,w),for for w E A(s; [f}). For state-only dependent cost, we replace by ct (s,w" (s)) = c(s).
195
196
Proof. For deterministic (and optimal) policies the quantities in Section 2.1 related to items become: 1. Item-frequencies (from Definition]
1,
Vj E (s) otherwise
(19)
0.
198
2. Transition probability (from Definition
2
[s j] P[s |s, w (s)),
Vj ()),
(20)
199
meaning that the transition probability given some item in the slate, is equal to the transition probability given the whole information about the slate. 3. Cost if it depends on the action w (from Definition 3)
200
201
(a( = ca(s, w wo (s)),
Aj (s))
(21)
202
4. State-item function (from Definition 4
Qa(s.)) = Qa w (s)),
(s))
(22)
203
In words, given state s, all items included in the deterministic (resp. optimal) slate have the same state-item item function value, equal to that of the whole slate.
205
Lemma 1. For any stationary policy d (and also the optimal d²),, ), it holds that Qa(s, Va(s).
Vj (s). Specifically for the optimal,
Qa (s, min wEA(s)
Vj (s)
(23)
207
Proof of Lemma 7 For stationary deterministic policies we have from
22 that Qa(s, =
Qa(s, (s)), Vj (s). It also holds from 17 that Va(s) = Qa(s, w (s)).
208
209
We now continue to the proof of Theorem 2 Applying the optimal deterministic policy to the state-
action equations for item-frequencies from Theorem (see formulation in 14 we get, (c" = =
210
(s. = (s,5) + pdd [s [s'(s.)]Vaa
17
c (s.J)) + +
pd [s'|s,]] min Qx- Qs-(s'ww). WEA(s)
From 23 in Lemma [ it holds that Qu- (s' = Va. (s'), Vj E (s').. Then, necessarily 212 Qe (s' (s'.) S (s' K), Vk & (s''), otherwise Va- (s') would not be the optimal value. In
211
213 other words, Va' mineex Qa- (s', f). From (11) we get (1) (s, = cd (s, for all
214 j E ws).. For E & w (s), we know that ree + O and æ, (w) = 0 for all w E A(s; (L)), so that
from II c² (s, E) can be any convex combination of the slate-costs c(s, w), for w A(s: (t)). O

---

3
Decomposed SARSA and Q-learning for slate actions
216
as Consider sequence of states, slate-actions and costs over discrete time-slots t
(Si = 8, A1 = w, C1 = c(s), = s'. A2 _ = c(s')....). The transition from state S to S2 depends on the slate recommended by the agent, and the unknown user behaviour select one of the items in the slate; the user is allowed to disregard the slate and select another item of their
218
219
220
221
own preference. The vanilla SARSA Suttonn and Barto (2018) is an on-policy (D) method, which updates the state-action values (s+,, wt) as follows
222
(24) The slate-actions w can follow the e-greedy exploration policy. We denote it by x;; based on this, the greedy slate w' (s) that minimises Q(s w) chosen with probability random slate w E A(s) is chosen with probability e. This implementation requires per state s E S, all (N) combinations of Q-values stored in memory. Furthermore, all these combinations need to be traversed when searching for the minimum in the greedy step.
Q(sr, wx) + 7 (x) + ( ((ss:ww)))
223
224
and uniformly
225
(K)
227
228
SlateFree updates. We can use the decomposition of the Bellman equations in Theorem 1 to propose SlateFree-SAMe SARSA policy. We remind that a state-action pair w) corresponds to N state-item pairs ($ one per j E w. The update can be written based on (13
229
230
[llateFree- SARSA]
For all N items in the slate j E we
(ss..) Q(s..)) + è (ss
X 1
Σ -(= ((s..) (25)
kEWe+1
231 For the e-greedy policy, each time state 8t is visited, the transition to 81+1 is sampled from the unknown transition probability [P*stt+ st, j]. which depends user preferences, but also on the policy e-greedy, which can change over time in the transient regime. The frequencies r in (13) do not appear above, because the new action batch W141 is sample of the policy x' (and the frequencies r²). In fact it can be easily shown that Ekeett Q(s++ kk)N is just one-sample unbiased estimator of > I''s Q k))N The cost o' (st, j) also depends on the e-greedy; in the
233
234
236
special case that depends the state only, we replace cf (st. j) c(s²), otherwise the cost per item
238
will evolve over time and needs to be recalculated using Def. 3 keeping track of 7", estimators.
Similar to SARSA, we can introduce decomposed version of the Q-learning algorithm (Warkins and Dayan (992]). which is an off-policy (D) method, where the Q functions are updated based on the optimal action policy, although the actions may follow some other (say e-greedy) policy. Then as above, we can use Theorem propose the updated step of the state-item functions following (18).
240
242
[SlateFree - Q] For all N items in the slate j Ew
Q(s..)) = () +7 (())).)) + A min ((5 -((s)
(26)
EEK
243
In the special case that it depends on the state only, we replace by c(8,, wi) = c(st). The implemen- lation of SlateFree (both -SARSA and -Q variations) requires per state s at most K values stored in memory (if we avoid self-loops, then recommending the same item is not an option).
245
246
Finding the best slate. In the exploitation phase of the c-greedy policy, we need to decide which N slate is optimal. We are given, however, for each state s, not the state-action values Q(s, w) but rather the K state-item values ((s, j). Since we are looking for stationary deterministic optimal policy, then we can apply the results from Section 2.3] Specifically, we have proved in Lemma] T that Qa () = minwe,A(s) Qa- (s,w), Vs E ws), meaning that all state-item values will be equal, for the items included in the optimal slate (or more generally in the slate of the deterministic policy). Hence, we need only select in the greedy phase, the N items with smallest Q(s.)) values, both in the SARSA and -Q version of SlateFree.
247
249
251
253
254
The update steps in 25 and 26p have important novelties compared to alternatives, as in e.g. le et al. [2019] eq. 14, ISJ. They are strictly model-free and do not need any prior knowledge over the environment. Also, costs that depend on both state and action are allowed. Hence, SlateFree uses N parallel updates to learn any stationary environment over time, using a more compact Q- function representation, compared to the non-decomposed vanilla-SARSA and Q-learning methods. Convergence to the optimal is empirically verified practice, but yet not provably guaranteed, due to the dependence of the costs and transition probabilities per item in the learned policy.
255
256
257
259
7

---

261
4
Numerical evaluation
262
In this section, we evaluate numerically the performance of SlateFree (both -Q and -SARSA variations), against two methods from the literature: (i) the standard Q-learning and SARSA tabular
263
method (called Vanilla- Q and Kiiilla-ARSA, where all possible (x) action-slate combinations are accounted for, each having its own Q-value per state; furthermore against (ii) the proposed in [ee
265
266
al. [019] method SlateQ with greedy slate selection in exploitation phase. Our environment is a recommendation system where a user starts their viewing episode from a certain item, and the system recommends a slate of N (unordered) items, excluding the currently viewed item. Each episode has average length (1 - A) steps. The experience is repeated over Tepia 2 1 episodes. The great challenge test the SlateFree method on user behaviours whose solution needs to be combinatorially searched. We evaluate three such artificial user choice models:
267
268
289
270
271
272
User-1
The user has a fixed retention probability a E [o.1] 1] per step to select one of the N recommended items uniformly at random, and (1 a) probability to disregard the recom- mendations and select on their own for one of the K library items uniformly at random.
274
275
2
The user has set X' of undesired items that they would never click on. Then, this behaviour is similar to user-1, with the difference that user-2 will choose either from the recommended items (with probability a), or from the whole library (with 1 a) one item uniformly at random among all items, ignoring in both cases those items in set X.
276
277
278
279
3
The user has a set y of must-include global items. This user does not follow a retention probability a. Instead, they will select among the recommended items at random, as long as at least one item from y is included in the recommendation slate.
280
281
282
A. Small scenario. We first study a small size scenario with K 10 and N = 4. The number of possible combinations per state is (K-1) = 126, where we exclude recommendation of the currently viewed item. With SlateFree we get reduction in memory for the Q-table from 10 x 126 to
283
285
10 9. The costs per item are all high 20 + 21. where 2; ~ Uniforrm(.. 4). but there are four items with lower cost, namely Co- 5
+ zg. C = 0+ 21. C7 4 27 and cy 8 + Zg (remember it is minimisation problem). The discount is fixed in all experiments to X = 0.85. For user-1 and -2, the retention is a 0.75. For user-2 the exclusion set X {0, 1, 8). For user-3 we select X' = ) as in user-2. The learning rate is 7 = 0.004 and the e-greddy GLIE strategy has fixed = 0.05 for the exploration probability. We consider as number of episodes for the evaluation Tepis 600 Each episode is a walk of the user on the library of K items, with mean length (1 -)= 6, 67 views. The evaluation for the three types of users and Tepis = 600 is shown in Fig. | (TO--row) We use on the x-axis logarithmic scale of episodes. The value per episode has high variance and so smooth the results within a window of 200 episodes. SlateFree- Q and SARSA converge for any user type in around 10K episodes, order of magnitude faster than the Vanilla-Q and Vanilla-SAAe SARSA. Also, the average value after convergence is the same for the two methods, indicating that SlateFree converges to the optimal value function. Both SlateFree and SlateQ converge to the optimal value, but we will see this is not true for larger catalog and dimension instances. Our method shows faster and steeper convergence than SlateQ in all users, because SlateQ updates the item-Q values only for the single selected item, whereas SlateFree for all N items included in the slate.
287
289
280
292
294
296
287
298
289
300
B. Larger Scenario. Next we evaluate the convergence in more difficult scenario with K- 100 and N = 10, which corresponds to (99) x 15- - 10th combinations. This problem is not tractable for Vanilla- or Vanilla-SARSA. Hence, we only show results for SlateFree-D SlateFree-SARe
302
303
304
and SlateQ in Fig. (BOTTOM-rOW)) The value per episode has high variance and so we smooth the results within a window of 1000 episodes. Now, both SlateFree-O Q and -SASSA can solve all three user cases within x 500K episodes, whereas SlateQ seems to learn and improve over time, but cannot solve for any user, at least within the Topie = 1M cpisodes.
305
307
308 C. Insensitivity in N. Our evaluations show that the convergence time given some library size K becomes almost insensitive to the dimension size N. To illustrate this, we simulate user-3 for a catalog size K- = 10 and various sizes of N E {1, 2. 3, 4, 5). The results are illustrated in Fig. 2 (left). One can observe that surprisingly the slowest converging curve is for N = 1, whereas for the higher N almost all curves converge before T Tepis = 10K. The reason for the poor convergence behaviour of N is probably due to the fact that each step the episode contributes a single
309
310
311
312
313
update of the -tate-item functions, whereas for N the multiple parallel updates accelerate the
8

---

Sieeo
Tamber Epsedds
Namber Bep?
Bumber Batsoiics
20000, E.
Cner2 1-136,
13.33
13.25
18:3
San0
SUBSO
ACOIES
2018
NEDA KOOK
Figure 1: (TOP-row) Value function user-1 (left), user-2 (centre), user-3 (right); library K = 10, dimension N 4, episodes 600K, methods: SlateFree- Q. SlateFree-SARR SARSA, SlateQ, Vanilla * (BOTTOM-row) Value function user-1 1 (left), user-2 (centre), user-3 (right); library K = 100, dimension N- 10, episodes 1M, methods: SlateFree-D Q, SlateFree-She SARSA, and SlateQ.
3.5
30000
20000 2000
20500
sodeo sp00e 300000
560003
Spowecs
Humbo Dutseiis Food
Figure 2: (left) Insensitivity in N, (centre) Number of Q-updates, (right) Slate-dependent cost.
process considerably. This is the same reason why SlateFree- in Fig. shows steeper learning curve compared to SlateQ, where the latter updates a single state-item function per step.
316
317 D. Effect of parallel updates. We investigate the role of N paraliel updates in the convergence of the Sl alateFree-Q algorithm. More specifically, for user-1, and the small scenario K = 10 and N
318
319
we evaluate the algorithm using different number of updates per step at each evaluation. Aside the proposed algorithm which updates all four items in the slate per step, in the others we allow three
320
321
items per step, two items, and finally a single item to update. We plot our results in Fig. (centre). We observe that the complete method with all four updates converges in 10K episodes already (shown in red). For three updates per step, the method seems to converge (green curve) to value close to the optimum, albeit very slowly. For two and a single update (brown and pink curves) we observe that
322
324
the method gradually improves over the episodes but even in 150K events it has not converged to the optimum. To conclude, the plot shows that it is necessary to do all N parallel updates per step for the method to converge to the best possible value, and fast.
326
328
E. Dependence of cost on both state and action-slate. We study now how the performance of SlateFree is affected when the cost depends on both the current state and the entire action-slate c(s, w.). Such an option is not supported by SlateQ Ie et al. [2019] We now modify the cost so that penalty = 42 is applied to all () where E W. are the items participating in the recommended slate, whenever the user does not follow (rejects) the recommendation slate. Obviously this penalty is
329
330
331
332
dlateddependent. We illustrate the performance of all methods in Fig. 2 (right). We observe that the decomposed SlateFree converges to the optimal solution for both -Q and -SARSA variations, same
334
as Vanilla-Q and Amilla-SARS.. SlateQ from le et al. [009 fails to converge to the minimal value.

---

References
336
Imad Aouali, Sergey Ivanov, Mike Gartrell, David Rohde, Flavian Vasile, Victor Zaytse,, and Diego Legrand. Combining reward and rank signals for slate recommendation, 2021. JRI.phttss:/aaxii http///rxivvrrra.ea////// aaaaaaaa//100 2107
338
339
12455
340
Minmin Chen, Alex Beutel, Paul Covington, Sagar Jain, Francois Belletti, and Ed H. Chi. Top-k off- correction for reinforce recommender system. In Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, WSDM '19, pages 456-464, New York, NY. USA, 2019. Association for Computing Machinery. ISBN 9781450359405. doi: 10.1145/322860003299999 URL hattps:://oos
342
343
344
10. 0145/3289600.3335 3290999
Caroline Claus and Craig Boutilier. The dynamics of reinforcement learning in cooperative multiagent systems. In Jack Mostow and Chuck Rich, editors. Proceedings of the Fifteenth National Conference on Artificial Intelligence and Tenth Innovative Applications of Artificial Intelligence Conference, AAAI 98, IAAI 98, July 26-30, 1998, Madison, Wisconsin, USA, pages
348
347
348
AAAI Press / The MIT Press, 1998. URL
http: / //www//wwwco//oo//////// asai otg/Liibaary/AMA///SS 1998// /tt99///aaaa/0 asai98 106.ppp
350
Tom Van de Wiele, David Warde- fardee Andriy Mnih, Volodymyr Mnih. Q-learning in enormous action spaces via amortized approximate maximization. CoRR, abs/2001.08111 2020. URLtttss:://arxi //rxio.or///
351
352
aba/2001 08116
Mukund Deshpande and George Karypis. Item-based top-N recommendation algorithms. ACM Trans. Inf. Syst., 22(1):143-177, jan 2004. TSSN 1046-8188. doi: 10.1 197967777777 URI httphhttpp///oi....
354
355
1145/963770.963777
356
Gabriel Dulac-Amold, Richard Evans, Peter Sunchag, and Ben Coppin. Reinforcement learning in large discrete action spaces. CoRR, abs/1512.07679, 2015. URL
07679
358
Cristos Goodrow. On youtube's recommendation system, September 2021. URL httpss/:s://blog youtube/ inside- youtube/uuubboooo horauuubeeooooooubbeeuueee www.oeeeooooooommccodooo-o-eee styta/dtttttttttssmeemmmmm [Online; posted 15 15-September-2021, ac- cessed 07-May-2021J.
359
360
Fugene Ie, Vihan Jain, Jing Wang. Sanmit Narvekar, Ritesh Agarwal, Rui Wu, Heng-Tze Cheng, Tushar Chandra, and Craig Boutilier. SlateQ: tractable decomposition for reinforcement learning with recommendation sets. In Proceedings of the Twenty-eighth International Joint Conference on Artificial Intelligence (ICCAI-19), pages 2592-2599, Macau, China, 2019. See arXiv:1905.1221 12767 for a related and expanded paper (with additional material and authors).
362
363
364
385
Alexandros Karatzoglou, Linas Baltrunas, and Yue Shi. Learning rank for recommender systems. In
367
Proceedings of the 7th ACM Conference on Recommender Systems, RecSys '13, pages 493-494, New York, NY, USA, 2013. Association for Computing Machinery. ISBN 978 9781450324090. doi: 10.1145/2507157. 2508063. URL httpp:://do .trp//...r/1.11 10. 1145/2507157 22008063
368
389
Feng Liu, Huifeng Guo. Xutao Li. Ruiming Tang, Yunming Ye, and Xiuqiang He. End-to-end deep reinforcement learning based recommendation with supervised embedding. Proceedings of the 13th International Conference on Web Search and Data Mining, pages 384-392, New York, NY, USA, 2020a. Association for Computing Machinery. ISBN 9781 0781450368223. htR.https:: htt/://ii.oo//////
371
372
373
1145//3336991..1 337 3371858
Feng Liu, Ruiming Tang, Xutao Li. Weinan Zhang, Yunming Ye. Haokun Chen, Huifeng Guo, Yuzhou Zhang, and Xiuqiang Hc. State representation modeling for deep reinforcement learning based recommendation. Knowledge-Basse BBsed Systems, 205: 106- 170, 2020b. ISSN 0950-7051, doi: http://ooo.oog/ooo.011oo..ooooom 106170. URL https://: http://wwwwccccccccc wwwp::/sceinncccceeeeee.ee http::/:www...ocooooooooooooooos http://www...oorcooooo////////00
375
376
377
Luke Metz, Julian Ibarz, Navdeep Jaitly, and James Davidson. Discrete sequential prediction of continuous actions for deep RI. CoRR, abs/1 705.05035, 2017. http:aatp:./aarii.or///a///////e 05035
379
380
Martin L Puterman. Markov decision procexsex: discrete stochastic dynamic programming. Joha Wiley & Sons,
381
1994, ISBN 978047161977 197722.
David Rohde, Stephen Bonner, Travis Dunlop. Flavian Vasile, and Alexandros Karatzoglou. Recogym: A reinforcement leaming environment for the problem of product recommendation online advertising, 2018
383
384
uttpsstss://axx org/ wwwpggg/bb/siaaa wwwpaa//././//////////////eaeeee 1800.00010110 00720
385
Guy Shani, David Heckerman, and Ronen 1. Brafiman. An map-based recommender system. Journal of Machine Learning Research. 6(43): 1295, 2005. URL htctp:///mmlr.or//ppprssssts
html
10

---

387
David Silver, Guy Lever. Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In Eric P. Xing and Tony Jebara, editors, Proceedings of the 31st International Conference on Machine Learning, volume 32 Proceedings of Machine Learning Rewearch, pages 387-395 Bejing, China, 22-24 24 Jun 2014, PMLR. URL httLhtttp://prroceedingg mlr. wwtpssmw......eeeeee.... wwwpppeeesesseeeeeeeeeee swle/r11vle1111re html
309
390
Anonymous SlateFree Authors. Slatefrre code in google colab, May 2022a. URL http::///oabbbeeeeeeeeeee
392
cww /ri http://www.aaaoooooooooooooooonn 2022; accessed 15- 15-May-2022)
[Online; posted 10-May-
395
Anonymous SlateFree Authors. Slatefree code download from dropbox, May 2022b. /www
395
dropbox cemppoxx.com/teee wwt.coo.cccccee
396
[Online; posted 10- 10-May-20222 accessed M5-M2y-2022].
Peter Sunehag. Richard Evans, Gabriel Dulac-Arold Yori Zwols, Daniel Visentin, and Ben Coppin. Deep reinforcement learning with attention for slate markov decision processes with high-dimensional states and actions. CoRR, abs/ 1bwp/512..01111. 1224 2015. URL http:://://aat http:///wwwwor/r////////oo abs wwtpaa//....ee... 05124
398
399
Richard S. Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018. URL http:://nccompleeeeddees. wwt./ete////oteeeee the book 2nd 2nd.htmml
401
.ttm
402
Nima Taghipour, Ahmad Kardan, and Saeed Shiry Ghidary. Usage-based web recommendations: A reinforce- ment learning approach. In Proceedings of the 2007 ACM Conference Recommender Systems, RecSys '07, pages 113- 120, New York, NY, USA, 2007. Association for Computing Machinery. ISBN 9781595937308. URL
404
405
doi: /0.1145/1297231.222 1292250
10. 1ee111111112 11445/19972311199777
Gábor Takáes, István Pilászy. Boutyn Németh, and Domonkos Tikk. Matrix factorization and neighbor based algorithms for the netflix prize problem. In Proceedings of the 2008 ACM Conference on Recommender Systems, RecSys '08, pages 267-274, New York. NY, USA, 2008. Association for Computing Machinery, ISBN 9781605580937. doi: 10.1145/1454008 1454049. URL https::///i..... 10. 1145/1454006
407
408
409
410
1454049
411
Arash Tavakoli, Fabio Pardo, and Petar Kormushev. Action branching architectures for deep reinforcement learning. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applications of Artificial Intelligence Conference and Lighth AAAI Symposium on Educational Advances in Artificial Intelligence, AAAT 18/IAAI 18/EAAT 18. AAAI Press, 2018. ISBN 178-1-57735-800-
412
413
415
416
Romain Warlop, Alessandro Lazaric, and Jérémie Mary. Fighting boredom in recommender systems with linear reinforcement learning, In Proceedings of the 32nd International Conference Neural Information Processing Systems, NIPS' 18, pages 1764-1773, Red Hook, NY, USA, 2018. Curran Associates Inc.
418
Christopher J. C. H. Watkins and Peter Dayan. Q-learning. 8:279 - 292, 1992.
420
Guanjie Zheng, Fuzheng Zhang, Zihan Zheng, Yang Xiang, Nicholas Jing Yuan, Xing Xie, and Zhenhui Li. DRN: A deep reinforcement learning framework for news recommendation. In Proceedings of the 2018 World Wide Web Conference, WWW 18, pages 167-176, Republic and Canton of Geneva, CHE, 2018. International World Wide Web Conferences Steering Committee. ISBN 9781450356398. doi: 10.1145/317886631188989
421
422
424
URL https::/ http:://dooooorog// org/10. /145/31788661... 3185994
425
Sijin Zhou, Xinyi Dai, Haokun Chen, Weinan Zhang, Kan Ren, Ruiming Tang, Xiuqiang He, and Yong Yu. Interactive recommender system via knowledge graph-enhanced reinforcement learning. In Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval, pages
427
428
179 188, New York, NY, USA, 2020, Association for Computing Machinery. ISBN 9781450380164. URL / org/ 110.00..15113333 77411777771341174 3401174
429
Checklist
431
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A]. . You are strongly encouraged to include a justification to your answer, either by referencing the appropriate section of your paper or providing brief inline description. For example:
433
435
Did you include the license to the code and datasets? YYs]] In Section T we include references where the code can be downloaded from Dropbox S SlateFree Authors [2022b). One can also run the code on Google Colab [SlateF-ree Authors [022a]]. both cases the Apache 2.0 licence has been included on the relevant jooyoor-.otebok..
437

---

439
1. For all authors...
440
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
442
(b) Did you describe the limitations of your work? [Yes] The limitations are described in lines 60-64 in page 2, Section ! These include the necessary assumptions to prove the main theorems. In the simulations we show that the method performs in practice very well even when assumption (ii, related to cost, is not satisfied. The necessity of N parallel updates is described and illustrated in page 9, Section DDD.
443
445
447
(c) Did you discuss any potential negative societal impacts of your work? [No] The work is about the solution of standard mathematical problem of Slate-MDPs and has both theoretical and practical flavour, but general applicability to various practical cases, not a specific one.
448
450
451
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
452
453
2. If you are including theoretical results...
454
(a) Did you state the full set of assumptions of all theoretical results? [Yes] As mentioned above, these are given in lines 60-64 in page 2, Section These assumptions are further repeated when necessary in the presentation of Theorems I and 2. In the simulations we show that the method performs in practice very well even when assumption (ii), related to cost, is not satisfied. We also argue about the necessity of N parallel updates. (b) Did you include complete proofs of all theoretical results? [Yes] The available pages where sufficient to include all proofs.
455
456
457
458
459
480
461
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [Yes] The code is included URL in the references. Specifically, the code can be downloaded from Dropbox through reference SlateFree Authors [2022b] and can be used online in
463
465
Google Colab (SltteFree Authors [202aa] is the exact code that used to produce all figures.
467
468
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] All details and hyperparameters are explicitly stated in the Numerical Evaluation Section 4
470
471
(c) Did you report error bars (c.g., with respect to the random seed after running exper- iments multiple times)? [No] The randomness in the initialization of the algorithm could be related to the initial value of the Q-matrix. We did not explicitly run many experiments with various initialisations, but we let this option available
472
473
the code. The aim is to identify whether and how fast our algorithm converges to the optimal policy compared to alternatives. Various initialisations could start closer or further away from the optimal solution, but this would hold for all policies/methods tested and the relative results would be similar to what we show.
475
476
477
478
479
(d) Did you include the total amount of compute and the type of resources used (e.g.. type of GPUs, internal cluster, or cloud provider)? [No] The experiments we perform are of small scale validate the theory. We only used local CPUs and the x-axis of the plots are in "number of learning episodes", which is a measure of time.
480
481
482
483
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [No] All code was developed by the authors.
485
486
(b) Did you mention the license of the assets? [No]
487
(c) Did you include any new assets either the supplemental material or as URL? [Yes]
We include the code for the numerical evaluations as URL on the paper references (for
489
Dropbox SSateeFree Authors 2022b) and for Google Colab SlateFree Authors (022al) )
490
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [No] Does not apply.
492
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No] Data content is not relevant to our numerical evaluation.
493
12

---

5. If you used crowdsourcing conducted research with human subjects...
486
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [No] Does apply.
498
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [No] Does not apply.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [No] Does not apply.
501
A
Appendix
502
No appendix accompanies the submission. The pages and extra references self-sufficient. Two
504
URLs (for Dropbox SlateFree Authors (2022b] and for Google Colab SlateFree Authors (2022a)
505
link the code used for the numerical evaluations.
13


Reviews:
[{"review_id": "beN5PpN3RI", "reviewer": "Reviewer_CrKM", "summary": "This work proposes (under some assumptions) a novel approach to RL for slate based recommendations. In general, standard RL approaches are not tractable since the action space when considering slates of recommendations is combinatorially large.\n\nHere, they introduce assumptions that allow them to decompose the problem into learning action-values on each item in a slate.\n\nThey test the approach on a simulated environment they designed.", "questions": "Isn't the assumption that the cost depends only on the state and not the action very unrealistic? $c(s, \\omega)=c(s)$. In particular, in almost all recommendation problems the reward is likely to be something like the expected user engagement which is action dependent. I'm aware you relax this assumption in a specific numerical experiment (line 318), but this is still very different than the general case of action-dependence.\n\nRelated to the above point. Much of the interest in slate based approaches is that the value of recommending an item depends on other items in the slate. For example, if the state allows us to infer that the user is interested in either basketball or baseball, showing a (slate size 2) basketball recommendation and a baseball recommendation is probably a good slate. But showing two (potentially relevant) basketball videos is likely to suboptimal since it is less diverse so the additional value of the second basketball video is much lower. It seems like the approach proposed here does not address this problem of diversity and that the value of an item in a slate may depend on the other items in the slate?\n\nWhy use $\\omega$ to denote the action instead of $a$?\n", "limitations": "I don't think this work discusses the limitations of this approach clearly. It would helpful to test on some other environments and explain more clearly the limits of the assumptions needs for this decomposition.\n", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\nRL for slate based recommendations is an interesting topic.\n\nWeakness:\n\nI found the decomposition proposed here difficult to follow. It would be helpful to try and provide more intuition behind this approach.\n\nI have some concerns about the realism of the assumptions and whether its solving the main issues of interest in slate based recommendations (see questions).\n\nThe approach is only tested on a simple simulation tailored to this approach. There are a number of public (real) datasets that can be used for evaluating this approach using off-policy estimators or SlateQ released a simulation with their method. Testing on a broader range of environment (particularly with real data) would help better understand the useful and realism of this approach.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WujJHVMsZUo", "reviewer": "Reviewer_MKZi", "summary": "This paper considers the problem of N items recommendation system which is a intractable due to the combinatorial nature of the problem. The authors introduce a slate-MDP for solving such problems. Through theoretical analysis, the authors show that the slate-MDP can be decomposed using just item-related Q function per state. This paper also proposes a SlateFree algorithm which is shown to be  insensitive to the slate size. \nSome numerical experiment results are presented to show the effectiveness of the proposed algorithm. The proposed algorithm converges  faster compared to the SOTA algorithms. \n", "questions": "The second assumption seems to be essential. By assuming the reward is only a function of individual items, the combinatorial problem is simplified. I can understand this assumption is essential for getting the theorems. The numerical evaluations shows this assumption can be raised. But a similar result does not hold for SlateQ algorithm. Can you provide more details about this comparison? Both the theorems of these algorithm assume the independency. \nIn this experiment, the SlateQ algorithm converges faster than the proposed one for User1 setup. What is the reason that SlateQ performs better when user select the item by sampling from a bernoulli distribution? It will be great if you can provide more analysis for the experiment results. \n", "limitations": "Yes. The authors provide adequate information about this.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The problem considered in this paper is promising since it is a generalization of the standard recommendation system problem. Due to the size of the action space is extremely large, it is important to have a time efficient algorithm. The proposed algorithm is shown to achieve good performance for such problems. Sufficient analysis is provided to support the theorems in this paper. The idea of decomposing the slate-based Q function into individual item-based Q function makes sense to me. Overall, this paper is well written and easy to follow. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "CvwUcDCfdf", "reviewer": "Reviewer_1QMW", "summary": "This paper tackles the problem of sequential slate recommendations, where at each step the agent has to choose from a combinatorially large action set. It defines some assumptions for the structure of the MDP (called SlateFree-MDP) and then derives the Bellman equations for this setup. The modified Q-learning and SARSA algorithms then operate on these modified Bellman equations.", "questions": "- The definition of the state is not quite clear to me. If the state is the last-viewed item, the transition is the next viewed state under a given policy?\n- What is the difference between the terms $P^\\pi[\\omega|s,j]$ and $P[\\omega \\in A(s;j)|s]$? Given that the policy depends only on the current state. \n- How applicable are these structural assumptions to some real-world data/application?\n", "limitations": "The limitations are partially unaddressed as mentioned above, and the societal impact of using this on recommender systems is not discussed.\n", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The decomposition of the original MDP results in significantly reduced computation (due to the independences introduced)\n- Short proofs help understand the properties and definitions as the reader proceeds.\nWeaknesses:\n- The assumptions, particularly Definition 2 along with the state (only) dependent cost, essentially reduce the problem to (almost) K-independent sequential slot problems. This is far from solving the original slate problem. This is further highlighted by the fact that this method needs to store atmost NK q-values overall.\n- Experiments: No comparison against vanilla-SARSA. Given that the reward depends only on the state (viewed item) along with Definition 2, I believe that SARSA would perform better than Vanilla-Q and should be an essential benchmark\nMinor typos/Corrections:\n- L54: “in the exploitation”\n- L151: Missing summation in line 2\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6SAgFcKTOyV", "reviewer": "Reviewer_8bDr", "summary": "This paper studies the sequential recommendation problem and shows that the Q functions can be decomposed based on the state-dependent cost function assumption. Evaluation results are also presented in the paper to verify the efficiency of the algorithm.", "questions": "1. Line 124, reward→cost.\n2. If $S=K,$ why not just use one notation? \n3. I have a question about the model. From the definition from Sec.2, the state s is the currently viewed item. Can the viewed items change over time or do they remain the same available $K$ items? If the states can change, I didn’t see the formal definition of the state space. If not, what do you mean (lines 109–110) by saying \"the user moves to state $s’$ by either picking one of the recommended items or selecting something else from the catalog?” Will the MDPs stop if the user picks a recommended item? If so, the MDP should include a terminal state, and all the proofs need to be reconsidered. \n4. What is the case when K=10 and N=4, and you said the memory for the Q-table was reduced from 10x126 to 10x9 calculated? ", "limitations": "I don't think this paper has any potential negative societal impact.", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n1. The sequential recommendation problem is interesting.\n\n**Weaknesses**\n\n1. The presentation is a little hard to follow.\n2. The decomposition is only possible when the cost is state-dependent; no further discussions are included for other cases. For example, what if the Q function can be decomposed approximately, or is local convergence achievable in other sensorial?\n3. The technical contributions seem limited.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject