In a typical e-commerce setting, Content Ranking Optimization (CRO) mechanisms are employed to surface content on the search page to fulfill customers' shopping missions. CRO commonly utilizes models such as contextual deep bandits model to independently rank content at diferent positions, e.g., one optimizer dedicated to organic search results and another to sponsored results. However, this regional optimization approach does not necessarily translate to whole page optimization, e.g., maximizing revenue at the top of the page may inadvertently diminish the revenue of lower positions. In this paper, we propose a reinforcement learning based method for whole page ranking to jointly optimize across all positions by: 1) shifting from position level optimization to whole page level optimization to achieve an overall optimized ranking; 2) applying reinforcement learning to optimize for the cumulative rewards instead of the instant reward. We formulate page level CRO as a cooperative Multi-agent Markov Decision Process , and address it with the novel Multi-Agent Deep Deterministic Policy Gradient (MADDPG) model. MADDPG supports a flexible and scalable joint optimization framework by adopting a “centralized training and decentralized execution” approach. Extensive experiments demonstrate that MADDPG scales to a 2.5 billion action space in the public Mujoco environment, and outperforms the deep bandits modeling by 25.7% on the ofline CRO data set from a leading e-commerce company. We foresee that this novel multi-agent optimization is applicable to similar joint optimization problems in the field of information retrieval.
Traditional e-commerce search results page can be consisted of several positions (a.k.a “slots”), e.g., shown as the blue boxes in Figure 1. Such an explicit design helps maintain a consistent shopping experience for the customers and is easy to maintain. Each position accommodates several rankable pieces of contents. Diferent positions could also serve diferent purposes: top-position content (e.g., position 1) includes highly relevant contents or a dedicated module answering or clarifying customers’ questions; middle positions can help customers navigate, narrow down, or discover related products and categories; bottom positions may have lower relevance, but aims to inspire customers to either diverge from the original intent or explore their search further. Content providers can schedule their contents to show at particular positions, based on diferent content properties. When multiple pieces of contents compete for the same position, a content optimizer (a.k.a ranker) is often designed to determine which are the most helpful pieces of contents to surface.
In common use cases, content ranking optimization
(CRO) can be formalized as a ranking problem, such as Search Bar
building contextual deep learning models to optimize for Position 1
certain objective functions, e.g., revenue, profit, or
clickthrough rate (CTR), etc. [
In this paper, we propose to utilize a multi-agent deep reinforcement learning (RL) solution (MADDPG) to tackle the CRO problem, which aims to 1) achieve a joint whole-page level contextual optimization across multiple positions, by learning the interactions among positions and generating whole page contents combinations; 2) optimize for long term benefits instead of instant benefits; 3) improve customer experience to better fulfill customers’ shopping missions. The optimizer of each position is referred as an “agent”, and contents of each position are referred as “actions”. All agents act cooperatively to receive collective whole page level rewards. We utilize full RL to optimize for the accumulative future rewards during the entire customer journey, instead of heuristic instant rewards. We believe this novel method is applicable and innovative to other joint optimization applications in e-commerce.
The rest of the paper is organized as follows: Section 2 describes the related work used in the industry; Section 3 describes the CRO problem formulation; Section 4 describes the proposed solution; Section 5 describes the evaluation and results; and Section 6 summarizes our work and discusses future research directions.
Reinforcement learning has gained significant attention in the field of e-commerce for ranking related problems, where the goal is to present customers with ranked list of items to maximize customer engagement and conversions. Specifically, we focus on the work addressing the high-dimensional action space in the ranking scenario.
Multi-Variate Testing (MVT) [
Hierarchical RL (HRL) [
Reinforcement learning has also been applied in diferent ranking methodologies, e.g.,
listwise recommendation [
In CRO, we firstly apply MADDPG to the whole page search ranking problem, providing a scalable solution for an industrial setting with tailored modifications.
We formalize the content ranking optimization (CRO) as a combinatorial optimization problem, where the major challenge is to deal with a combinatorial action space. In CRO, an action is content. With more new positions and contents, the action space will grow exponentially. Formally, for a CRO environment with positions and discrete actions at each position , there will be ∏︀
=1 possible actions to be considered. Table 1 lists the existing contents, containing the possible combinations and the actual max combinations from a single search request: (Actual max is less than the possible number because contents may have diferent trafic coverage).
Such a large action space is intractable for conventional single-agent single-dimensional RL
algorithms, such as DQN [
In this part, we formalize the problem in CRO using MADDPG. We consider a multi-agent
extension of a MDP called Markov games [
At each time step, a customer issues a request to CRO, CRO observes the customer’s shopping state, chooses a content combination and display to the customer, and then receives the rewards from the session. CRO goal is to learn the policy for each agent which maximizes the expected return across all sessions.
It is intractable to collect business rewards instantly online, which is the key limitation preventing online RL. As Figure 2 shows, CRO is defined as a mix-ofline RL system in the current scenario: every day, a trained agent is deployed online to interact with the environment; at the end of the day, the trajectories are collected to train the agent, then the trained agent is deployed online to act. CRO is closer to an ofline RL scenario where the agent can interact with the environment.
We utilize the MADDPG model [
[︃ ∇ ( ) = E,∼ ∇ (|)∇ (, , ..., )|= ()) updated as follows:
Here the experience replay bufer contains the tuples (, ′ , 1, ..., , ), recording the experience of all agents. The centralized action-value function is [︃ ( ) = E,,,′ ( (, , ..., ) − ( + ′ (′ , ′1, ..., ′ ))|′= ′( ) 2 ]︃ where ′ = { 1′ , ...,
′ } is the set of target policies with delayed parameters ′. state regardless of the changes in the policy of other agents.
This method resolves the non-stationarity issue [
Rewards are critical to an RL system. In our setting, we formulate the reward as follows: ]︃ ]︃ (1) (2) (3) = + + * + * + * (4)
Clicks and Abandonments are part of the reward due to two reasons: 1) we aim to
encourage more engagements in the session and reduce session abandonments, which are
an unbiased indicators and indicate long-term value; 2) to enable rewards shaping [
We sample actions from the Gumbel Softmax [
We conduct extensive evaluations both in a public Mujoco environment [
We choose the Mujoco [
We leverage the following models as benchmarks:
• DQN: The classical DQN model. We flatten multi-dimensional action spaces into a single
dimension
• CQL: Conservative Q-learning [
CQL is designed to address the over-estimation issue [
We run models in HalfCheetah-v2 in an online fashion with the discrete per-dimension action
sizes of [
(a) Mean Reward, Action Size 5
(b) Mean Reward, Action Size 10
The results in Figure 4 indicates that typical DQN and CQL models are intractable for handling the large action space due to the insuficient explorations, which is expected. Branching models learn well at relatively low dimension action size but do not scale as well as MADDPG. MADDPG demonstrates consistent and optimal performance in all online experiments.
The online study demonstrates that MADDPG scales well in an online setting. However, CRO
is more suitable for an ofline setting. Specifically, the CRO agent is required to learn from
the trajectories collected by online policies at the end of the day. In this section, we conduct
experiments to verify whether MADDPG can perform well in an ofline setting. We still apply
per-dimension action sizes of [
The results in Figure 5 demonstrates that 1) conservative models can learn better than DQN in an ofline setting, which aligns with their design purpose, but CQL does not scale well with larger action sizes; 2) MADDPG scales well in the ofline setting.
(a) Mean Reward, Action Size 5
(b) Mean Reward, Action Size 5 (c) Mean Reward, Action Size 5 Figure 5: Model Performance in Ofline Setting
(d) Mean Reward, Action Size 5 In this section, we conduct experiments to evaluate MADDPG on the CRO data set. For simplicity, we extract a business metric as the reward for benchmarking. We evaluate the models on desktop trafic only and consider joint optimization for 3 positions - top/middle/bottom positions, as they have the most impacts and content competition.
Trajectory data serves as the training source for RL. We follow a standard procedure to extract the training trajectories from CRO logs. As a result, we extracted 40M training trajectories from desktop trafic. The trajectories are from baseline policies: 5% random policy (generated by 5% epsilon greedy) and 95% deep bandits policy. For evaluation trajectories, we follow the same steps but use an exploration filter to extract 4M trajectories from the random policy.
We leverage the following models and and rewards as benchmarks: • Random: It randomly selects content combinations from available options. • Baseline (Multi-component reward): It is a baseline ranker with click-based Multiobjective Optimization objective. • Position-level bandits: It is identical to the baseline model structure, past search queries are tokenized by the pre-trained SentencePiece tokenizer [25] and encoded by Embedding and LSTM [26] layers. Then we concatenate embedding with other inputs and feed it to an MLP layer with 256 hidden units. The final output is one unit with a Mean Squared Error (MSE) loss. This model is similar to the baseline, with the major diferences in the features and reward. • Page-level bandits: It utilizes an MLP structure with a multi-head output structure. Each "head" represents one position and outputs the content probability for available contents at this position. Features are the same as described above: past search queries, customer context, top position content ID, inline stop content ID, and bottom position content IDs. • MADDPG w/ gamma=0: We train it on trajectories with a discounted factor=0.0. State is encoded by SentencePiece, Embedding and LSTM layers as well. Since the discounted factor is 0, this actually acts as a bandits model which optimizes for the instant reward without considering the future rewards. • MADDPG w/ gamma=0.99: We train it on trajectories with a discount factor as 0.99; others settings are the same as described above.
The diference between the baseline and random models demonstrates the impact of the
baseline model. The diference between position-level and page-level bandits presents the benefit
of joint optimization. The diference between “MADDPG w/ gamma=0.99” and “MADDPG w/
gamma=0” illustrates the benefit of RL over bandits.
5.2.3. Metrics
We adopt the Inverse Propensity Scoring (IPS) method [27] to evaluate the trained policies:
Given logged exploration data with a policy , and an evaluation policy , the following IPS
estimator of is unbiased:
ˆ ( ) =
1 ∑︁ (|)
=1 (|)
(5)
where is the trajectory count, is the trajectory reward. Since it is a random policy,
(|) = |1| is extracted by softmax [
Table 2 demonstrates that MADDPG outperforms the the bandits model with logged and unlogged reward. The diference between “MADDPG with gamma=0.99” and “MADDPG with gamma=0” shows that RL is beneficial by considering state transition and delayed reward. The diference between page-level and position-level models shows that ranking holistically is beneficial. The baseline IPS is not high, which we assume is due to the composite efect of diferent objectives and the over-estimation issue. We also conducted an experiment to verify whether MADDPG can gradually learn during training. We periodically dump the model during training and evaluate it on the CRO evaluation data set and observe the IPS trending. Figure 6 shows the IPS trending, demonstrating that MADDPG can learn during ofline model training.
We implemented this approach on one of the leading e-commerce platforms and ran an A/B test to verify its performance. We tested with both discount factor as 0 (refer to as Treatment 1) and 0.99 (refer to as Treatment 2), optimizing a multi-component reward function. By training and deploying it on the online trafic, both treatments demonstrated incremental multi-million revenue value. However, treatment 2 resulted in significant profit losses, leading to a flat overall reward, i.e., a larger discount factor resulted in poorer performance in our setting.
The evaluation demonstrates that the MADDPG model scales well in both online and ofline multi-agent environment setting, and is able to learn from the CRO ofline data set. MADDPG also significantly outperforms the baseline like bandits model by 25.7% on IPS evaluation. We also evaluated this through online A/B test and the proposed solution brought incremental multi-million revenue.
In this paper, we frame page-level content ranking as a joint optimization problem, and tackle it using the novel MADDPG model. We conduct extensive experiments on both online Mujoco environment and an ofline CRO data set. The evaluations demonstrate that MADDPG scales well up to a 2.5 billion action space and outperforms the baseline bandits model by 25.7%. In the future, we will further invest in multi-agent RL in several directions: 1) explainability: interpretation of why an agent takes certain action is important for content owners but this is not a trivial task, especially for neural network-based RL. Fortunately we have several directions to explore, such as reward decomposition [28] and shapley on Q-values [29]; 2) eficient exploration: exploration is critical for RL. This paper applies a noisy-based method which may not be the optimal for new contents. We will test entropy-based and variance-based exploration methods; 3) enhanced lifelong RL: retraining new models with a saved experience replay when encountering new contents is not ideal. We will research transfer RL to support the onboarding of new contents without needing to retrain the models. reinforcement learning, arXiv preprint arXiv:2004.07219 (2020). [25] T. Kudo, J. Richardson, Sentencepiece: A simple and language independent subword tokenizer and detokenizer for neural text processing, arXiv preprint arXiv:1808.06226 (2018). [26] S. Hochreiter, J. Schmidhuber, Long short-term memory, Neural computation 9 (1997) 1735–1780. [27] E. J. Williamson, A. Forbes, Introduction to propensity scores, Respirology 19 (2014) 625–635. [28] Z. Juozapaitis, A. Koul, A. Fern, M. Erwig, F. Doshi-Velez, Explainable reinforcement learning via reward decomposition, in: IJCAI/ECAI Workshop on explainable artificial intelligence, 2019. [29] J. Wang, Y. Zhang, T.-K. Kim, Y. Gu, Shapley q-value: A local reward approach to solve global reward games, in: Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, 2020, pp. 7285–7292.