Ranking policies learned efficiently from past data using top k approach
Efficient Offline Learning of Ranking Policies via Top-$k$ Policy Decomposition
Machine Learning
Summary
Ranking systems, like those showing products or news, try to put the best items at the top. The challenge is learning better rankings just from past user behavior, which is tough because there are so many possible ways to arrange items. The authors came up with a new method that splits the ranking into two parts: picking the top items carefully and then arranging the rest. This reduces guesswork and improves learning from past data, making the system better at figuring out user preferences.
What this means in practice
- •For recommendation system engineers: Build better ranking algorithms that learn efficiently from logged user interaction data by focusing on top-k selections first.
- •For e-commerce platform operators: Improve product rankings shown to users by refining ranking policies offline using past shopping behavior to boost engagement.
Authors
Ren Kishimoto, Koichi Tanaka, Haruka Kiyohara, Yusuke Narita, Yasuo Yamamoto, Nobuyuki Shimizu, Yuta Saito
Abstract
Many recommender systems such as for e-commerce and news platforms aim to provide users with rankings they are likely to interact with. Off-Policy Learning (OPL) of ranking policies enables us to learn new ranking policies using only historical logged data. However, ranking settings make OPL remarkably challenging because their action spaces consist of permutations of unique items, being extremely large. Existing methods primarily use either policy- or regression-based approaches. The policy-based approach, which typically uses importance-weighted policy gradients, can suffer from high variance due to large action spaces. The regression-based approach, on the other hand, estimates the expected reward using conventional machine learning methods, avoiding variance issues but potentially suffering from severe bias. To circumvent these issues of existing methods, we propose a new OPL method for ranking, named Ranking Policy Optimization via Top-$k$ Policy Decomposition (R-POD), which combines the policy- and regression-based approaches in an effective fashion. Specifically, R-POD decomposes a ranking policy into a first-stage policy for selecting top-$k$ actions and a second-stage policy for choosing the bottom actions given the top-$k$ actions. It learns the first-stage policy using a new policy gradient estimator and the second-stage policy via the regression-based approach. This method can substantially reduce variance, since it applies importance weighting only to the top-$k$ actions. We also demonstrate that our policy-gradient estimator for the first-stage policy is unbiased under a conditional pairwise correctness condition, which only requires that the expected reward differences of pairs of rankings sharing the same top-$k$ actions can be estimated correctly.