Off-policy Learning to Rank (LTR) aims to optimize a ranker from data collected by a deployed logging policy. However, existing off-policy learning to rank methods often make strong assumptions about how users generate the click data, i.e., the click model, and hence need to tailor their methods specifically under different click models. In this paper, we unified the ranking process under general stochastic click models as a Markov Decision Process (MDP), and the optimal ranking could be learned with offline reinforcement learning (RL) directly. Building upon this, we leverage offline RL techniques for off-policy LTR and propose the Click Model-Agnostic Unified Off-policy Learning to Rank (CUOLR) method, which could be easily applied to a wide range of click models. Through a dedicated formulation of the MDP, we show that offline RL algorithms can adapt to various click models without complex debiasing techniques and prior knowledge of the model. Results on various large-scale datasets demonstrate that CUOLR consistently outperforms the state-of-the-art off-policy learning to rank algorithms while maintaining consistency and robustness under different click models.
Paper
Similar papers
Peer review
Summary
This paper aims to unify the assumptions on user behavior in a ranking called click model by formulating the ranking problem as a click-model agnostic Markov Decision Process (MDP). By doing so, the paper proposes to reduce the Off-Policy Learning to Rank (LTR) problem to a variant of offline RL, which does not require precise estimation of the click models. Under this formulation, the proposed offline RL method, which incorporates state representation learning to the well-known Conservative Q-Learning (CQL), enables more accurate estimations of ranking metrics than baseline estimators in real-world datasets.
Strengths
1. The manuscript is easy to follow. The motivation for unifying click models and introducing the offline RL framework is clearly explained. 2. The RL formulation of LTR is reasonable, and showing the connection between offline RL and Off-Policy LTR would be insightful for the LTR community. 3. The ablation study on state representation learning is insightful.
Weaknesses
1. While the connection between LTR and offline RL is interesting, the proposed method (CUOLR) itself is not a fundamentally new framework for offline RL. In particular, the proposed state representation learning method, which applies positional encoding and attention to the inputs, seems to be an engineering effort rather than a very novel framework. 2. In experiments, an offline RL algorithm (CQL) does not show advantages over a simple RL baseline (SAC). While I acknowledge the author(s)’ contribution to formulating LTR as an RL problem, I think the algorithm has room for improvement.
Questions
- In general, SAC does not perform very well in the offline RL setting and thus the offline RL algorithms, including CQL, have been proposed. However, the experiment results show that CUOLR (CQL) and CUOLR (SAC) perform competitively. Could you provide some justification for this result?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
2 fair
Contribution
2 fair
Limitations
This limitation is not special for this paper, but classical click models and MDP both assume that the reward observed at each position are not affected by lower positions including the neighboring ones. If this assumption does not hold, LTR may introduce some bias and offline RL may also ignore some causal relation between actions and rewards.
Summary
This paper presents a unified approach for off-policy learning to rank (LTR) that is adaptable to general click models. The authors formulate off-policy LTR as a Markov Decision Process (MDP) and leverage offline reinforcement learning (RL) techniques to optimize the ranking process. They propose the Click Model-Agnostic Unified Off-policy Learning to Rank (CUOLR) method, which can be easily applied to a wide range of click models. The authors provide empirical evidence demonstrating the effectiveness of CUOLR in comparison to state-of-the-art off-policy LTR algorithms.
Strengths
● The paper presents an innovative and practical methodology for off-policy learning to rank. The formulation of off-policy LTR as an MDP and the use of offline RL techniques provide a comprehensive and adaptable approach for ranking optimization. ● The authors provide insightful empirical findings, showing that the CUOLR method consistently outperforms state-of-the-art off-policy learning to rank algorithms. The results on various large-scale datasets demonstrate the effectiveness, consistency, and robustness of CUOLR under different click models. ● The paper presents a detailed introduction on state representation learning. There are also empirical analyses on its practical effect.
Weaknesses
● The synthetic dataset and the offline evaluation can give biased evaluation results of the algorithms. ● There are some related works that are not mentioned in this paper. Cai, et al. [1] also apply RL techniques to recommendation systems and provide a new MDP formulation. It also includes ranking scores in the formulation that can be regarded as a downstream application to this paper. Xue, et al. [2] provides another MDP formulation of RL for optimizing long-term user engagement. ● There remain some issues unsolved in the paper. See the questions for details. [1] Cai, Qingpeng, et al. "Reinforcing User Retention in a Billion Scale Short Video Recommender System." arXiv preprint arXiv:2302.01724 (2023). [2] Xue, Wanqi, et al. "PrefRec: Preference-based Recommender Systems for Reinforcing Long-term User Engagement." arXiv preprint arXiv:2212.02779 (2022).
Questions
● Lines130-133 are hard to understand. Why not include remaining documents that are yet to rank? How will the policy perform on $s_0$, where nothing will be included as input? ● The introduction of dynamic action space can introduce dynamics shift in RL and unstable training. Are there any specific techniques to handle this issue? ● Why does SAC obtain similar performance with CQL when learning in static datasets? Will the issue of policy distribution mismatch lead to poor performance?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
The formulation and evaluation are limited to off-policy/offline RL that learn from a static dataset. In applications where there are adequate online interaction data, it will be helpful to consider some online RL counterparts.
Summary
The paper talks about how to model user behaviors with positional biases in an online search system. The paper proposes a unified RL framework to generalize three common types of positional bias models: Position-Based Modeling (PBM), CASCADE (each click depends on the previous click), and Dependent Click Models (DCM). By capturing all previous clicks into a state, the paper suggests that standard offline RL algorithms, such as Conservative Q-Learning (CQL) and Soft Actor Critic (SAC), can be used to estimate and optimize for the positional-aware ranking policies. Simulation experiments are included to support the claims.
Strengths
Originality. The paper observes commonalities in three different types of methods and proposes a unified method to combine them. The generality of the proposal is further examined by simulating different cases from each of the method and showing similar performance using the proposed method. The observation and the empirical validation feel original to me. The authors addressed my concerns and I have adjusted my scores accordingly.
Weaknesses
Significance. The paper made a rather limiting assumption that all users in the same search system follow a single pattern of positional bias. This may not be true, as different users may have different positional biases. A more practical approach is to insert perturbations to the ranking positions to estimate the true positional effects using IPS. To mitigate the risks of perturbations, methods have been introduced to swap only adjacent search results. Please see this paper as an example: https://www.cs.cornell.edu/people/tj/publications/agarwal_etal_19a.pdf Clarity. The description of the proposed method lacks sufficient details (see additional questions). Also the experimental results (Table 1) did not seem to contain significant differences between the algorithms being considered. This leads me to wonder if the proposed RL solution is actually easy to find, or is it fundamentally difficult to implement and the results may be sensitive to hyperparameter choices. The paper did not discuss common limitations of RL algorithms.
Questions
Table 1. The table compares the proposed method with baseline methods, one of which is used to simulate the ground-truth user behaviors. However, in the results, the baseline method which was used to simulate the user behaviors did not perform the best in estimating the user behaviors. Is this expected? Also, the differences between all methods seem pretty small. Algorithm 1. Line 6, where is psi defined? Eq (5). What is the difference between CQL and SAC? Why is there only one equation being presented for both algorithms? More details would be appreciated for clarity purposes.
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
2 fair
Contribution
2 fair
Limitations
No, the paper did not discuss the choice of hyperparameters or the closeness of the experimental results. They seem to be common challenges with RL algorithms.
Summary
- Authors propose a unified off-policy reinforcement learning-based approach for learning to rank (LTR) problem that is adaptable to all general click models. - Authors argue that a user's behavior in terms of clicks can be modeled by a Markov Decision Process (MDP), thereby allowing them to look at LTR from the perspective of offline reinforcement learning. - Authors' key contribution is a novel state representation that takes into account features of all the items/documents presented to a user. Specifically, they represent state at position $k$ by $s_k = [(d_1, d_2, \cdots, d_{k-1}), k]$ to capture the context of user behavior prior to reaching position $k$-ranked position. The action set at position $k$ is all the available items/documents that haven't been presented to the user in prior $k-1$ positions, and the reward is simply the users' click behavior when presented with action $a_k$. - Authors use positional encoding and self-attention layer to extract the state representation given the sequence of items/documents at prior ranked positions, i.e., $(d_1, d_2, \cdots, d_{k-1})$. They train an end-to-end model that jointly optimizes for state representation as well as the policy.
Strengths
**Motivation** - Authors present a strong motivation for their approach based upon the need for a unified a click model-agnostic LTR method which generalizes well to use of any RL algorithm. - Authors do a good job at placing their work in context of related work in the field by comparing/contrasting their approach with other works. _Note_: I am not updated on the state-of-the-art RL approaches for LTR, and therefore may not be aware of some recent works. **Technical Presentation** - Authors do a good job at formalizing the problem and providing all the relevant technical information in Sections 3 and 4 that would be required for reproducibility. - Authors contribution is quite easy and intuitive to understand. **Experiments** - Authors evaluate their approach (using CQL and SAC) in comparison to baselines such as Dual Learning Algorithm (DLA), Inverse Propensity Weighting (IPW) algorithm and Cascade-model based IPW, as well as LambdaMart model which serves an upper bound. The metrics of authors' proposed approach are significantly favorable in comparison to baselines. _Note_: Just as above, because I am unaware of the SOTA, I am unable to comment on whether the right baselines have been used for comparison. - Authors provide ablation study to validate the need for each component of their proposed approach.
Weaknesses
**Is this a Markov Decision Process?** Formally, the Markovian property of MDP refers to the fact that given states $s_i$ and actions $a_i$, the equality $\mathrm{Pr}(s_t | s_0, a_0, s_1, a_1, \cdots, s_{t-1}, a_{t-1}) = \mathrm{Pr}(s_t | s_{t-1}, a_{t-1})$ holds. Intuitively, it means that the probability of landing in state $s_t$ of the Markov chain only depends on the last state-action pair $(s_{t-1}, a_{t-1})$, and not the state-action pairs preceding that. Given the authors' approach uses state representation as $s_k = [(d_1, d_2, \cdots, d_{k-1}), k]$, it is unclear to me how/if the Markovian property still hold? **Effect of Click Data Generation** Authors mention that they use 1% of training data to train a Ranking SVM to generate initial ranked list of items, upon which clicks are simulated using different click models. How does the usage of more/less portion of training data affect the comparative baselines and in turn the relative performance improvement provided by the proposed approach over those baselines?
Questions
- Could the authors address the questions raised in the weaknesses section of the review?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
3 good
Contribution
3 good
Limitations
- Authors have not explicitly addressed limitations of their approach or any potential negative societal impact in the manuscript. However, authors' proposed approach is not a significant departure from the prevalent large scale recommender systems.
Summary
In this work, the authors model the process of learning optimal ordering of ranked lists, called Learning to Rank (LTR) as a Markov decision process (MDP). This allows them to utilize techniques from reinforcement learning to solve for the policy that generates the optimal ordering. In practical applications of LTR, a pre-collected dataset (offline) is typically used which is collected using a logging policy that is not optimal (off-policy). As a result, techniques for offline off-policy reinforcement learning are used in this work. In the MDP formulation, the reward is defined as an item of the ranked list being clicked. The distribution of clicks is referred to as a click model, which results in various reward functions. An RL algorithm can optimize a wide range of reward functions and allows this approach to be largely click-model agnostic. The approach is empirically validated on semi-synthetically generated click datasets, and it demonstrates competitive performance across different click models compared to click-model-specific baselines for learning optimal rankings.
Strengths
The paper succinctly models LTR as a sequential decision-making problem, building on top of prior work, in a manner that allows the use of transformer architecture to be employed in conjunction with an RL algorithm. This allows for a couple of benefits: 1) being agnostic of specific click models since any click distribution in the offline dataset can in theory be encoded as the reward that the RL algorithm can optimize for, and 2) allowing for flexibility in defining the state representation through the use of attention and position embeddings. Both of the claims are supported by strong empirical analysis.
Weaknesses
The paper extended prior formulations of LTR as an MDP to allow for using the transformers architecture, with the aim performing policy learning without click model specific methods. In addition to the existing experiments, one experiment that would highlight the point would be one that learns the optimal ranking for data generated from a non-standard click model – say a randomly picked click distribution – where all other methods fail. Additionally, the utility of the section on the optimality of rankings (Definition 3; Assumption 3.1) is unclear. These are possibly included to tie this work to existing literature, however, this method should not require those conditions for finding an optimal policy. On a related note, L122-L123 incorrectly states that Definition 1 is explained in Appendix C, which only discusses the definitions of examination probabilities of various click models. The writing and presentation could be improved in places, a few examples being highlighted below. Minor/Typos: - “Debiasing” as caused by bias in the data, versus bias due to estimation procedure has been used interchangeably through the paper leading to a fair amount of confusion (Ex: L26-L29) - Equation (1) should have a $\propto$ and not $=$ - L121: mutually independent of what? - L227: $d\\_model$ undefined. - Algorithm 1: Mistake on Line 7
Questions
A few questions: - Assumption 3.1 holds only for monotonically decreasing examination probabilities. The reference [64] proves the result in Assumption 3.1 only for PBM and cascade models, and is not the case for other click models. Why is this top-down scanning of the ranked list necessary for the working of the algorithm? - The robustness to change in $\alpha$ in CQL seems to indicate that just fitting a Q function on the offline data should suffice. This would be true if the logging policy provides enough support for all actions, which is commonly the case in practice where uniform random logging policies are used. Why is a conservative algorithm (CQL) necessary for the experiments? - (L148-L149) How is the action set restricted to not repeat actions implementationally? - The gains in performance are more significant for ERR as compared to NDCG. Why is that the case?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
2 fair
Contribution
3 good
Limitations
Like any other method for LTR, the performance of the algorithm should depend on the coverage provided by the logging policy. A comment on the effect of the coverage of the logging policy and it's effects on the learnt rankings would be useful. State representations play an important role in the performance of the algorithm and in the context of this work the representations are learned via architectural choices in the Q-function estimator. The claim that (L248) that an additional component is added on top of CQL is overstated.
The authors' response addresses some of my concerns while overlooking a couple of others. My question about the non-standard click model still stands: The method is designed to be click-model agnostic, and should in theory be able to optimize for any reward --- click probability --- independent of Definition 3. In that setting, all other click-model specific baseline would be expected to struggle. This would be an insightful result about the utility of the method. I will keep my initial score.
We thank the reviewer for the follow-up comment and are glad to hear that some concerns have been addressed by our initial response. The reviewer's comment on > The method is designed to be click-model agnostic, and should in theory be able to optimize for any reward --- click probability --- independent of Definition 3. caught our attention. Firstly, we would like to emphasize that we have accurately pointed out that our method can be applied to "a wide range of click models" as early as in the abstract. It would be a misunderstanding and an overstatement that our method (or any algorithm) can solve offline LTR with click feedback without basic assumptions of how clicks are generated. Secondly, our Definition 3 and Assumption 3.1 are mild but necessary assumptions on the optimality of the ranking list. Definition 3 assumes optimal ranking is the one with descending attractiveness of documents, which is the standard assumption of LTR problem and aligns with evaluation metrics such as ERR and NDCG. Assumption 3.1 assumes optimal ranking list maximizes total rewards (clicks), which is needed to align the goal in Definition 3 and the solution of RL. The assumption has been proved correct for PBM and Cascade model [1] and we empirically showed that our method worked well for other click models such as DCM, CCM and UBM. However, for certain click models, optimal ranking list does not maximize total clicks. We here provide a counterexample: consider three documents with attractiveness $d_1 = 0.1, d_2=0.2, d_3=0.3$ and the examination probabilities depend on both document and position. For the two ranking list * attractiveness: 0.3 0.2 0.1, examination prob: 0.5, 0.1, 0.1 * attractiveness: 0.1 0.2 0.3, examination prob: 0.5, 0.4, 0.3 , the optimal ranking list (first one) has smaller expected total clicks (0.18 < 0.22) because this click model encourages postponing good documents to keep user browsing and generating more clicks. Thus this example cannot be solved by our method. However, we note that this example does not belong to any click models we studied (PBM, Cascade, DCM, CCM, UBM) and to the best of our knowledge, has not been studied in previous offline/counterfactual LTR literature. Actually, our method can already cover most of the click models that have been studied in offline LTR. We are happy to answer any questions that the reviewer finds not fully addressed. [1] Masrour Zoghi, Tomas Tunys, Mohammad Ghavamzadeh, Branislav Kveton, Csaba Szepesvari, and Zheng Wen. Online learning to rank in stochastic click models. In International Conference on Machine Learning, pages 4199–4208, 2017.
Thank you for the clarification. This along with the additional experiments address my concerns, and accordingly, I have updated my score.
Thank you for the discussion
We are happy to see that our response addressed the concerns. We thank the reviewer for the review and engagement during the discussion period. Regards, Authors
Dear authors, Thank you for your response and additional experimental results presented in the rebuttal document. I shall take this additional information into account during the discussion phase. Thank you.
Thank you
We sincerely thank the reviewer for the time and effort in reviewing our paper. Regards, Authors
More experimental result
To verify the robustness of our proposed method CUOLR-CQL, we add the performance comparison of CUOLR-CQL with various baselines under logging policies with different qualities. Specifically, as stated in A2, we add a logging policy with SVMRank trained with 0.01% data. The performance when using a logging policy with SVMRank trained with 1% training data is shown in the main paper Table 1. The performance are shown in the following table: The metrics from left to right are: ERR@3,5,10, NDCG@3,5,10 DLA (PBM): | 0.155 | 0.179 | 0.202 | 0.246 | 0.261 | 0.293 | IPW (PBM): | 0.164 | 0.187 | 0.210 | 0.259 | 0.273 | 0.304 | Ours(PBM): | 0.214 | 0.239 | 0.262 | 0.324 | 0.339 | 0.367 | DLA (CASCADE): | 0.171 | 0.195 | 0.218 | 0.261 | 0.277 | 0.309 | IPW (CASCADE): | 0.180 | 0.204 | 0.227 | 0.284 | 0.297 | 0.327 | Ours(CASCADE): | 0.214 | 0.239 | 0.262 | 0.326 | 0.340 | 0.368 | DLA (DCM): | 0.191 | 0.215 | 0.238 | 0.290 | 0.304 | 0.333 | IPW (DCM): | 0.190 | 0.214 | 0.237 | 0.299 | 0.310 | 0.340 | Ours (DCM): | 0.212 | 0.238 | 0.260 | 0.324 | 0.338 | 0.367 | This demonstrates the effectiveness and robustness of our proposed method under various logging policies. We thank the reviewer for the suggestion here and will also add this table in the final version of the paper.
Dear Reviewer79J3, We were wondering if you have gotten a chance to go through our responses and the additional experiments we add to the paper, and if these revisions and responses address your concerns regarding the paper. We are happy to address any remaining concerns and would really appreciate it if you engage in a discussion with us. Thank you so much!
Reply
Thanks for the rebuttal, I am more pleased with the paper. I will keep my original score and wish you good luck.
Thank you
We sincerely thank the reviewer for the time and effort in reviewing our paper. Regards, Authors
Dear Reviewer atvb, Thanks for your review! We were wondering if you have gotten a chance to go through our responses and the additional experiments we add to the paper, and if these revisions and responses address your concerns regarding the paper. We are happy to address any remaining concerns and would really appreciate it if you engage in a discussion with us. Thank you so much!
Thanks
The authors addressed my concerns and I have adjusted my scores accordingly. Regarding Q1, my original question was regarding perturbation during data logging/generation. I am from a recommendation background where such perturbations are often necessary. For search problems, the queries may already contain enough randomness such that further perturbations may not be necessary. The authors should briefly discuss these details, if they apply.
Thank you for the follow-up
Thank you for the discussion and for adjusting the score. We appreciate your efforts in reviewing our paper. Regarding Q1, while the perturbations have not been applied to the baselines and our method, we will discuss the suggested paper in the next version.
Thank you
We are happy to see that our response clarifies the questions and the new experiments are helpful. We thank the reviewer for the time and effort in reviewing our paper. Regards, Authors
Decision
Accept (poster)