Source-linked AI summary
Reinforcement Learning to Rank in E-Commerce Search Engine: Formalization, Analysis, and Application
Yujing Hu, Qing Da, Anxiang Zeng, Yang Yu, Yinghui Xu
TL;DR
E-commerce search ranking is a multi-step problem whose rounds are correlated, whereas many LTR methods treat them independently. The paper formulates search sessions as SSMDPs, analyzes accumulative rewards, and proposes a policy-gradient algorithm. It reports over 40% and 30% growth in gross merchandise volume in simulation and TaoBao, respectively, over state-of-the-art LTR methods.
Problem
Existing online LTR methods mostly model one-shot ranking and do not adequately capture sequential correlation across multiple rounds in e-commerce search sessions.
Method
The paper defines SSMDP, analyzes its reward structure, and proposes DPG-FBE, a policy-gradient algorithm designed for high reward variance and unbalanced reward distributions.
Results
More than 40% and 30% growth in gross merchandise volume is reported in simulation and the TaoBao search engine, respectively, over state-of-the-art LTR methods.
Takeaways & Limitations
Modeling ranking as a sequential decision problem and maximizing accumulative rewards improves reported transaction outcomes in the studied simulation and TaoBao application.
Takeaways & Limitations
The paper cannot report accurate transaction amounts because of Alibaba’s information protection rule.
Abstract
from arXiv · showhide
In e-commerce platforms such as Amazon and TaoBao, ranking items in a search session is a typical multi-step decision-making problem. Learning to rank (LTR) methods have been widely applied to ranking problems. However, such methods often consider different ranking steps in a session to be independent, which conversely may be highly correlated to each other. For better utilizing the correlation between different ranking steps, in this paper, we propose to use reinforcement learning (RL) to learn an optimal ranking policy which maximizes the expected accumulative rewards in a search session. Firstly, we formally define the concept of search session Markov decision process (SSMDP) to formulate the multi-step ranking problem. Secondly, we analyze the property of SSMDP and theoretically prove the necessity of maximizing accumulative rewards. Lastly, we propose a novel policy gradient algorithm for learning an optimal ranking policy, which is able to deal with the problem of high reward variance and unbalanced reward distribution of an SSMDP. Experiments are conducted in simulation and TaoBao search engine. The results demonstrate that our algorithm performs much better than online LTR methods, with more than 40% and 30% growth of total transaction amount in the simulation and the real application, respectively.
1 INTRODUCTION
E-commerce search sessions are multi-step ranking-and-feedback processes, but existing online LTR methods largely model ranking rounds independently. The paper formulates this sequential problem with RL and reports substantial transaction growth over online LTR baselines.
- Problem Setting: E-commerce search repeatedly ranks items, receives user actions, and reranks remaining items until purchase or session departure.A successful transaction typically involves multiple rounds of this process.
- Motivation: Existing online LTR methods often address one-shot ranking, leaving sequential correlations across multiple search-session rounds insufficiently modeled.Online LTR learns from user signals but commonly treats each ranking-and-feedback interaction as a single round.
- Approach: The paper proposes reinforcement learning to learn an optimal ranking policy for the multi-step sequential ranking problem.The approach targets correlated ranking decisions within a session rather than independent ranking steps.
- Contributions: The paper formally defines SSMDP, proves the necessity of maximizing accumulative rewards, and introduces DPG-FBE for high reward variance and unbalanced rewards.These contributions address the formalization and learning challenges of sequential ranking.
- Results: More than 40% and 30% growth in total transaction amount is reported in simulation and TaoBao application, respectively, versus online LTR methods.The reported improvements concern the simulation and real application settings.
2 BACKGROUND
The background introduces RL as interaction-based learning grounded in MDPs and reviews online LTR methods. It positions this work against one-shot ranking approaches while emphasizing multi-round e-commerce sessions.
- Reinforcement Learning: RL learns through trial-and-error interaction between an agent and its environment, with MDPs providing its fundamental mathematical model.An MDP specifies states, actions, rewards, transitions, and a discount rate.
- Reinforcement Learning: An MDP agent seeks a policy maximizing expected accumulative rewards, represented through optimal state-value or state-action value functions.The finite-horizon objective maximizes expected discounted return over T steps.
- Reinforcement Learning: Function approximation addresses the inability of tabular RL methods to scale to large state and action spaces.The background attributes this limitation to the curse of dimensionality.
- Online Learning to Rank: Online LTR methods use user signals and exploration strategies to learn ranking functions, avoiding offline label mismatch and labeling costs.The reviewed paradigms include supervised pointwise, pairwise, and listwise methods alongside online approaches.
- E-commerce Search Sessions: A typical TaoBao session lets users click item details, buy, request another page, or leave after successive ranking decisions.These user actions create the multi-step interaction structure studied by the paper.
- Research Gap: The paper differs from most prior online LTR work by modeling multiple interaction rounds rather than a one-shot ranking problem.This distinction is presented as especially relevant to e-commerce search sessions.
3 PROBLEM FORMULATION
The paper models e-commerce search as a search session MDP in which ranking actions determine item pages, user histories, and probabilistic continuation, conversion, or abandonment. This formalization supplies the state, action, transition, and reward structure for sequential ranking.
- 3 PROBLEM FORMULATION: E-commerce search requires a ranking action whenever a user requests an item page, creating a multi-step decision process.Pages are shown sequentially as users browse, compare, and eventually purchase or leave.
- 3.1 Search Session Modeling: A top K list is the ordered list of highest-scoring items, and each item page removes its displayed items from the remaining candidate set.The page at step t is generated by applying the previous ranking action to unranked items.
- 3.1 Search Session Modeling: Item-page history records the query and every displayed page observed by the user, forming the contextual basis for state modeling.The initial history contains the query; later histories add each item page.
- 3.1 Search Session Modeling: A finite item set bounds the number of pages and decision steps, while user behavior can terminate a session through purchase or abandonment.The environment samples conversion and abandonment behavior after each observed history.
- 3.1 Search Session Modeling: After an action, conversion, abandonment, and continuation occur with probabilities b(ht), l(ht), and c(ht)=1−b(ht)−l(ht), respectively.The initial history necessarily continues because no conversion or abandonment occurs before the first page is displayed.
- 3.2 Search Session MDP: SSMDP is a tuple containing the horizon, histories, states, ranking actions, rewards, and transition probabilities for a query and item set.Its state space includes continuation, conversion, and abandonment states.
- 3.2 Search Session MDP: In SSMDP, the search engine is the agent, users form the environment, and transitions derive directly from conversion and abandonment probabilities.The action space may be discrete or continuous, while the reward depends on the task goal.
4 ANALYSIS OF SSMDP
The SSMDP is Markovian when states encode search-session status, and its reward design links successful transactions to expected deal prices. The analysis shows that undiscounted accumulative rewards align with expected GMV, so ranking decisions across session steps should be optimized jointly.
- SSMDP formulation: The paper defines SSMDP states around continuation, conversion, and abandonment events, with ranking functions as actions and transition probabilities based on user behavior.The environment is the population of users, while the search engine is the agent.
- Markov property: SSMDP states satisfy the Markov property because the current state-action pair determines the resulting item-page history needed for future transitions.The paper proves this formally by showing that prior item-page histories are contained in later histories.
- Reward function: The reward function assigns positive reward only when a ranking action leads to a successful transaction, using conversion probability and expected deal price; otherwise reward is zero.In practice, the actual transaction deal price can serve as the reward signal when its expectation is unknown.
- Discount rate: The discount rate determines whether future rewards matter, and the analysis therefore compares discounted accumulative rewards with expected GMV.This connects the ranking objective to the search engine’s economic performance.
- Discount rate: When γ = 1, the value function equals expected GMV; when γ < 1, maximizing the value function cannot necessarily maximize expected GMV.The paper concludes that future rewards must be considered and that sequential ranking decisions should be optimized integrally rather than independently.
5 ALGORITHM
The paper develops DPG-FBE, a deterministic policy-gradient method using full-backup Q-value estimation for multi-step search-session ranking. It models conversion, continuation, and expected deal-price probabilities to address reward variance and imbalance.
- The policy gradient approach directly optimizes a parameterized policy, addressing policy representation and large-scale action-space issues in SSMDPs.The paper chooses deterministic rather than stochastic policy gradients because stochastic gradients may require more samples in high-dimensional action spaces.
- Algorithm 1 initializes actor and critic models, samples exploratory ranking actions, collects session trajectories, and updates models after search sessions.Exploration may use ε-greedy actions for discrete spaces or random output noise for continuous spaces.
- Full-backup updates use the next item-page history and Bellman structure to estimate Q-values while avoiding sampling errors from immediate rewards or returns.The computational cost is described as almost equal to one-step sample backups.
- DPG-FBE combines deterministic policy gradients with full-backup estimation to learn an optimal ranking policy in an SSMDP.The algorithm is designed for large action spaces and uses actor and critic models.
- The method models conversion probability, continuing probability, and expected deal price instead of fully modeling reward and state-transition functions.These models can be trained with online or offline data using statistical learning methods.
6 EXPERIMENTS
Experiments evaluate DPG-FBE in a TaoBao-based simulator and in TaoBao’s search engine. The method outperforms comparison ranking approaches and is deployed through a stream-driven asynchronous system.
- The study contains a simulated experiment comparing DPG-FBE and online LTR algorithms, plus a real TaoBao application.The real application evaluates the method in an online search-engine setting.
- 6.1 Simulation: 2% growth of transaction amount per session is achieved by DDPG-FBE with γ = 1 over the second-best simulation setting.Performance improves as γ increases, while γ = 0 performs far below the other curves.
- 6.1 Simulation: The five online LTR algorithms produce much smaller transaction amounts than DDPG-FBE and DDPG in the simulation.The paper attributes this comparison to their not being designed for integrated multi-step ranking decisions.
- 6.2 Application: The TaoBao system uses query planning, ranking, logging, reinforcement learning, and online key-value components in separate acting and learning loops.The loops operate asynchronously and exchange user logs and ranking-policy models through the log center and online KV system.
- 6.2 Application: 2.7% ∼4.3% more transaction amount per day is achieved by DDPG-FBE than DDPG during the one-week TaoBao A/B test.The application uses a 27-dimensional ranking action and a 90-dimensional state feature.
7 CONCLUSIONS
The paper formulates multi-step e-commerce ranking as an SSMDP, establishes the importance of accumulative rewards, and proposes an RL ranking algorithm. Experiments report improvements over state-of-the-art LTR methods in simulation and TaoBao.
- The paper uses reinforcement learning to control ranking in e-commerce search scenarios and formulates multi-step ranking with an SSMDP.
- The accurate transaction amount cannot be reported because of Alibaba’s information protection rule.The paper provides Alibaba’s 2016 China retail marketplace GMV as a reference index.
- The analysis theoretically proves that maximizing accumulative rewards is necessary for the multi-step ranking problem.
- More than 40% and 30% growth in gross merchandise volume is reported in simulation and TaoBao, respectively, compared with state-of-the-art LTR methods.