Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: 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.
strengths_and_weaknesses: Strengths:
- The decomposition of the original MDP results in significantly reduced computation (due to the independences introduced)
- Short proofs help understand the properties and definitions as the reader proceeds.
Weaknesses:
- 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.
- 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
Minor typos/Corrections:
- L54: “in the exploitation”
- L151: Missing summation in line 2

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?
- 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. 
- How applicable are these structural assumptions to some real-world data/application?

limitations: The limitations are partially unaddressed as mentioned above, and the societal impact of using this on recommender systems is not discussed.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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.

Here, they introduce assumptions that allow them to decompose the problem into learning action-values on each item in a slate.

They test the approach on a simulated environment they designed.
strengths_and_weaknesses: Strengths:

RL for slate based recommendations is an interesting topic.

Weakness:

I found the decomposition proposed here difficult to follow. It would be helpful to try and provide more intuition behind this approach.

I have some concerns about the realism of the assumptions and whether its solving the main issues of interest in slate based recommendations (see questions).

The 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.
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.

Related 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?

Why use $\omega$ to denote the action instead of $a$?

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.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: **Strengths**
1. The sequential recommendation problem is interesting.

**Weaknesses**

1. The presentation is a little hard to follow.
2. 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?
3. The technical contributions seem limited.
questions: 1. Line 124, reward→cost.
2. If $S=K,$ why not just use one notation? 
3. 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. 
4. 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 
Some numerical experiment results are presented to show the effectiveness of the proposed algorithm. The proposed algorithm converges  faster compared to the SOTA algorithms. 

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. 
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. 
In 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. 

limitations: Yes. The authors provide adequate information about this.
review_title: null

Meta-review: metareview: This paper considers reinforcement learning with unordered slate recommendations and shows that this problem can be decomposed into one Q-value per available item as compared to one value per possible slate in existing work. The authors derive a Bellman equation for this formulation and propose model-free algorithms based on it. They show on small synthetic tasks that these methods converge and perform favorably compared to existing methods.

The reviewers appreciated the new decomposition and its potential to enable significantly more efficient algorithms. However, several reviewers also voiced concerns about the clarity of the presentation, the practicality of the approach and the strength of the assumptions. The authors were able to remove a key limiting assumption (costs only depend on state) in the rebuttal revision of the paper. This was viewed very positively and alleviated the concerns about the strong assumptions. However, the concerns about clarity and practicality could not be fully addressed by the authors' response. For this reason, the paper is recommended to be rejected. 

Based on the reviewers' comments, the discussions and the AC's own reading of the paper, the following suggestions would make this a very strong paper:

* In the fully general setting where costs are action-dependent, the costs in the Bellman equations are policy dependent and therefore change throughout the execution of the algorithms. As the authors acknowledge, this makes it unclear whether the algorithms provably converge. The authors demonstrate good empirical behavior but their experiments are limited to small toy problems in the absence of function approximation. However, the combination of function approximation and changing (policy-dependent) cost functions may lead to less stable algorithms, a major concern in practice. A theoretical convergence analysis or empirical results with function approximation on more realistic problems would be extremely valuable here.

* The paper lacks a more thorough discussion of the relation to prior works and settings. The questions raised in the reviews around generality and assumptions in this paper shows that readers are left wondering what exactly enables the results as compared to prior work. A better discussion of the exact setting and comparison to other works would be very valuable and a better use of space in the main paper than the short proofs (which could be moved to the appendix).

* The addition of simple illustrative examples would greatly help convey the intuition behind the decomposition.

* The setting in this paper considers the slates being unordered and ordering effects seem to not be captured by this formulation. This is in contrast to existing work. The reader may wonder whether this is crucial for the proposed decomposition. Unordered slates is certainly is a deviation from previous works in this area and most practical recommender systems settings, which would limit the applicability of this approach. Carefully discussing this and if necessary / possible extending this to ordered slates would help and strengthen the paper.
confidence: Certain
Decision: Reject