E-commerce stores typically test changes to ranking algorithms through rigorous A/B testing which requires a change to satisfy some predefined success criteria on multiple metrics. This problem of simultaneously optimization of multiple metrics is multi-objective-optimization (MOO). A common method for MOO is to choose a set of weights to scalarize the multiple metrics into one ranking objective. However, in practical settings, rather than simply improving all metrics, the experimenter might be interested in improving a few metrics significantly with negligible trade-of for others. We can refer to such requirements as a desired policy. An experimenter chooses weights to scalarize the objective such that it best approximates the desired policy. Repeated A/B testing to arrive at a set of weights that approximates the desired policy well enough is costly and ineficient. This problem lends itself to of-policy evaluation methods. In this paper, we develop a framework for approximate Ofline MultiObjective Optimization for , explore-exploit policies where a small ( = 1 − 5%) trafic is reserved for exploration while the majority is served by exploiting the current best arm under the policy. Further, the metrics being optimized in our use case are highly skewed with zero-inflation. We then develop a simulator/ reward vector generator using a neural network that learns a distribution of rewards for a given context from exploration data. We empirically show that this reward vector generator is an unbiased estimator of such policies. Finally, we demonstrate empirical data that this estimator is able to correctly predict the order of treatments from an A/B test in an e-commerce page layout ranker across 4 diferent metrics.
Page layouts for e-commerce search determine the diferent kinds of content displayed on the search page. These layouts are aimed at providing excellent shopping experience to customers and improving various metrics such as clicks, purchases etc. Typically, these page layouts vary the number and type of item slots. Determining the most appropriate page layout can be thought of as a ranking problem which takes as input some customer and query features and chooses a layout from a set of well designed candidates [1].
To continuously learn from customer behaviour, explore-exploit policies such as contextual bandits are efective and widely used in production systems [ 2]. A page layout ranker (PLR) can be trained on contextual features to optimize for one or more metrics. Typically, in an ecommerce system, we are interested in optimizing multiple metrics- multi objective optimization (MOO). To make ranking decisions, we can then choose a set of weights to scalarize the multiple metrics into one ranking objective. To launch any changes to the ranking objective we follow the standard A/B testing approach. We embed this ranking objective in the PLR and evaluate it on a segment of live trafic for some suficiently long time-period. If the new ranking objective outperforms the current one, it is accepted and either stored for future use or deployed right after. This approach has three major limitations. Firstly, each iteration of A/B testing takes a long time and many iterations are needed to find an ideal choice. Secondly, it is expensive; it requires substantial engineering efort (in deploying each treatment to the live trafic). Lastly and most importantly, it can have negative customer experience impact.
Given the multi-dimensional nature of MOO and its post-facto nature, it is desirable to have some systematic way of selecting a few good choices of ranking objectives that can then be deployed online for final A/B testing. Using Of Policy Evaluation Methods for solving MOO has been described in IMO3[3]. However, in that paper the authors devised a method to learn the preferences of the experimenter with regards to tradeofs between metrics and assumed that a good enough of policy estimator was available. In this work, we tackle the problem of devising a good enough estimator when the reward distributions are skewed, zero-inflated and multi-modal as in our applicationand formulate a framework for applying this in production.
In this section, we develop our notation and formulate the MOO problem as a contextual bandit problem with delayed vector-valued rewards.
Let us consider a decision-maker (in this case, PLR along with its prediction module), which interacts with an environment (the customer population) over a large number of time-steps = 1, 2, . . . , , with the goal of optimizing a fixed number of distinct objectives, say . The interaction of the decision-maker with the environment is modeled as follows. 1. The environment reveals a (random) context to the decision-maker as well as a fixed set of possible actions (). Each such action is also referred to as an arm permissible for context . Let us denote the set of all possible contexts by . 2. The decision-maker chooses an arm from () according to some behavioral policy . 3. Our policy is policy space restricted to all , -policies where , is defined as ( , Policy) For any [0, 1] and any ∈ Δ , by , = , (·| , ), we denote a policy that, given a context , i) with probability , chooses an arm from () randomly, ii) with probability 1 − , chooses an arm with the highest predicted scalar reward (, , ).
. Let Π be the set of all behavioral policies. 4. Once is chosen, the environment generates a (random) vector-valued reward = ((1), (2), . . . , ()Σ) ∈ that is revealed to the decision-maker after a delay such as in the batched bandits setting[4].
Below are our assumptions for our problem setup.
1. Assumption 1: The contexts {()}=1 are drawn in an i.i.d (independent and identically distributed) manner from some fixed/time-invariant unknown distribution (· ). 2. Assumption 2: Given and decision-maker’s chosen action ∈ (), the reward is drawn from some fixed/time-invariant unknown distribution (·| , ).1 3. Assumption 3: The reward-vector is almost-surely bounded, i.e., ‖‖2 ≤ < ∞ for () denotes the reward obtained for the ℎ-objective at all = 1, 2, . . . , .2 Here, each time .
In rounds, the expected average reward of the decision-maker in objective ∈ []3, if they follow a behavioral policy , is given by, ()( ; ) 1 [∑︁ ()].
=1
The goal of the decision-maker is to learn a behavioral policy that optimizes over all the
objectives simultaneously, i.e., the decision-maker seeks a policy ⋆ that satisfies,
⋆ ∈ ∈Π ( (
⏟ ( ;⏞) With slight abuse of notation, assume that Π is the set of all policies that at time take action by using the current context and some statistic that is a summary/compression of the decision-maker’s observations in the previous time-steps 1, 2, . . . , − 1. Also, we will call ( ; ) as the value-function of policy when the horizon is time-steps.
If we consider a weight-vector ∈ Δ { ∈ : ≥ 0, 1 = ∑︁ () = 1}, Σ =1 then from the definition of Pareto-optimality, it is clear that a policy that solves the scalarized optimization problem,
⋆ ∈ ∈Π ( ; ), is a Pareto-optimal policy. Thanks to linearity of expectation, this is equivalent to optimizing in a contextual bandit setting with delayed scalar rewards of the form .
In OPE, a target-policy is evaluated using experience-data collected from some loggingpolicy that should preferably satisfy the below coverage(/absolute-continuity) criterion. Assumption 4: For any context and corresponding permissible action ∈ (), if ( ())() > 0, then ( ())() > 0.
Any soft explore-exploit based policy, , will satisfy Assumption 4 for all policies . (However, this does not mean that it is a good candidate for generating experience-data for OPE).
Now, in principle, the general scheme to explore all choices of could work as follows
1Here, we do not assume that the components of are conditionally-independent given and .
2This assumption is useful when = ∞.
3For all ∈ , we define []{1, 2, . . . , }.
(
We refer to this scheme as pseudo-Pareto-front generation. The usage of the term pseudo highlights that we are only exploring ,-policies. One way to explore the set ⋃︀∈Δ { ( ,; )} rather quickly would be to simulate simultaneous (possibly biased) random-walks in the weightsimplex Δ through multiple worker-nodes. We do not address methods of random walks in this paper.
Suppose we are given a , -policy whose value-function we would like to estimate using the experience data, . There are of-the-shelf algorithms, mainly including Simulation-method/Reward-vector-generator (described here), Direct-method, Vanilla Estimator [5], Inverse-Propensity-Score (IPS) Based Estimator [6], Doubly-Robust (DR) Estimator [7].
Distributions and {(·|* )} on contexts and rewards can change over time. But they should remain more or less time-invariant for some small time-frame. Performing of-policy evaluation on fresh experience-data helps ensure that value-function estimates of a given policy are reasonably accurate. Using experience-data from far of in the past may produce bad estimates if there has been a distribution-shift in the contexts and/or rewards (seasonal variations in customer’s preferences of a specific locale, change in national economies etc.). In the limit of large-data, i.e., || = → ∞, the Vanilla, IPS, and DR estimators provide (1 − )-type probabilistic guarantees for reliable accuracy. Amongst these algorithms, DR is preferable. However, its accuracy guarantees in the case of a finite data-set and for non-stationary policies (such as in our case) are diferent. Even for stationary policies, the accuracy of the DR estimator depends on the the accuracies of the IPS and the DM parts. Most of the work on OPE has been focused on improving the IPS part [8, 9]. One work [10] addressed this gap by designing the loss function of the DM part of the DR estimator to minimize the variance of the DR estimator. However, they assume that the target policy is known beforhand to design the loss function.
To use the DR estimator, either we require a mean-reward-vector predictor or a (possibly random) reward-vector generator, : (, ) ↦→
( ∈ , ∈ (), ∈ ).
: (, ) ↦→
( ∈ , ∈ (), ∈ ).
(
We used two datasets for our experiments. The small dataset we used for our experiments was obtained by 5% random sampling of PLR model training dataset from a policy deployed in production. This base data-set consists of 25MM samples and has a total of 13 fields. The online experiment dataset we used for our experiments was obtained by 10% random sampling of PLR model training datasets for treatments during an online A/B test of diferent policies. We used one policy as the logging policy and two (T1, T2) for testing.
The first eight features make up the context, the ninth feature is the action, and the remaining four are the corresponding rewards which are Reward 1, Reward 2, Reward 3, and Reward 4 respectively. In practice, there is a tension between these metrics.
We split the training data-sets into train, validation, and test data-sets using a split of 70%, 15%, and 15% respectively. A few important statistics of the unlogged versions of the target-labels are provided in Table 6 where we observe the below three properties. 1. The metrics Reward 1 (log), Reward 2 (log), and Reward 3 (log) are zero-inflated . 2. Conditioned on being non-zero, the histograms of Reward 1 (log) and Reward 3 (log) are unimodal.4 3. On the other hand, the histogram of Reward 2 (log) conditioned on being non-zero is bimodal.
We will assume a simple reward-vector generation model that incorporates the three properties
we mentioned above. Let us denote the context and action random variables at time by
and respectively. For the random variables that represent the metrics Reward 1, Reward 2,
Reward 3, and Reward 4 at time , we will use (1), (2), (3), and
(
the mean and standard-deviation of 1() by (1) and 1 (), then 1 1() (|, ) = √2 1()(, ) exp(− ( − (1)(, ))2 2( 1()(, ))2 ).
Intuitively speaking, we are assuming that in response to a (context, action) pair, (, ), the nature conducts a Bernoulli trial with (failure, success) probabilities, ((0)(, ), (1)(, )). If the result of this trial is a success, the nature draws a sample using a pdf that is obtained from trimming some gaussian pdf to the positive real line. In the case of failure, the reward assumes the zero value. • Conditional Distribution of (2):
(
Joint Conditional Distribution of Reward Vector : We assume that the scalar rewards are conditionally independent given a (context, action) pair. Therefore, the joint conditional distribution is given by P(|, ) = Π=1P()(()|, ).
4
− log P(|, ) = −
4 ∑︁ log P()(()|, ).
=1
Here, (02)(, ) + (
(
0 (14)(, ), = 1.
⎪⎧⎪(02)(, ), = 0,
P(
̃︀2
5.1. Advantages of Reward-Vector Generator Model
1. Inherently Random: Can play the role of a simulator that can generate
instantaneousreward-vectors.
(
Given our reward-vector generator model, we have to learn 17 functions of the (context, action)
pair. These are
• {(1)(, )}3=1, (22)(, ) (4 tasks for predicting conditional means);
• { 1()(, )}3=1, 2(
The learning of these 17 functions can be framed as a supervised multi-task learning (sMTL)
problem with 12 tasks because while {(0)(, ), (1)(, )}4=1 are 8 functions, they are two
classification tasks (as indicated in the parentheses above). Since conditional variances are part
of our reward-vector generator model, there is no need to set any weights for the first 8 tasks. For
(), = 1, 2, 3, 4Σ}.
the remaining tasks, (the 4 classification tasks), let us use temperatures = {
Then, using the model-uncertainty method [11], we can derive the below neural-network (
based) approximation of the log-likelihood function (
− ( (4))2 [log (
Making the standard assumption that the training-examples {(, , )}=1 are generated in an i.i.d5 manner, one justifies training a neural-network for minimizing the negative loglikelihood, i.e.,
1 ∑︁ log P˜(|, ; , ).
, − =1
(14)
-log (|, ; , )
≈ −
[∑︀=1,3 1[() = 0] l(og()(0)2) + 1[() > 0]( log (1) 1
( ())2 + 2( 1())2
(() − (1))2 + log √2 1())]
. + 1[(
( (2))2 + 2( 2(
( (2))2 + 2( 1(
There is one little caveat we need to address. The empirical-risk-function in 14 has variances and temperatures in the denominators which would cause errors in our implementation if they are initialized to zero or get close to zero during the training. To solve this issue, let us use the substitution,
= log . Thus, the optimization problem we will solve in our implementation is given by 1 ∑︁ log P˜(|, ; , ). , − =1 (15) (16) 6.2. Other Reward-Vector Generator Models 1. We currently use regression for estimation of Reward 1, Reward 2, and Reward 3, i.e., by assuming the conditional-distributions to be some gaussian pdfs. Together with Reward 4, this assumption about conditional distributions results in 4 tasks. Let us call a neuralnetwork model learnt by setting the weights of each task to 1 as type-1 model, whereas when the weights are obtained using the model-uncertainty method, we will call it type-2 model. 2. In our reward-vector generator model, if we enforce all (context, page-layout)-conditioned variances of Reward 1, pos. Reward 2, neg. Reward 2, Reward 3 to be the same, we retrieve the model-uncertainty method. This reduces the number of tasks to 8. Let us call this type-3 model.
We will call the model learned by solving function 16 as type-4 model. Without loss of generality, we used the Multi-gate Mixture of Experts (MMoE) architecture [12] for training purposes.
Mean
While the primary purpose of the models is not as a mean reward predictor, we performed an experiment to compare the model types for the task of predicting mean rewards. These results are summarized in Table 5 in Appendix A. We consider this as evidence that our choice of conditional distributions better models the rewards.
The results of our experiments for the comparision of model-types 1 through 4 for the task of generating reward-vectors are summarized in Table 1. Each row corresponds to some statistic of a reward signal and the highlighted values are the ones closest to the ground-truth. We can observe that overall type-4 model performs better in replicating the statistics.
Having obtained a trained reward-vector-generator which can also output mean-reward-vector predictors, we ran the simulation and direct methods on the entire small dataset using modeltype 4. The results of these two methods are listed in Table 2. The values closest to the ground-truth are highlighted. We note that the simulation-method performed better than the direct-method. In Table 3, we see that on the online experiment dataset, Model-4 was able to correctly predict winners among two treatments in 3 out of 4 metrics. Here the model was trained using experience data from a separate online logging policy from the same period. These results demonstrate the generalisability of our simulator/reward vector generator.
Since the reward vector generator/simulation method samples from a distribution, which is atypical of model based methods, we expect some variance in the estimates. We empirically estimated the variance of this method and compared it to the variance of the the Self Normalized IPS (SNIPS) method in Table 4. We see that our random vector generator method has 3 to 6 orders of magnitude less variance than the SNIPS estimator.
Many eCommerce applications use contextual bandit models for decision making. These models often optimize for an objective that is a linear combination of multiple objectives. Finding a pareto-optimal linear scalarization of the objectives is an OPE problem in this setting.
Amongst the OPE methods, theoretically, under mild assumptions, the Dobuly Robust (DR) estimator has low bias, and also enjoys good variance properties as long as one of the estimators (model or IPS) is accurate. However, in practice, this is rarely the case. On the other hand, the simulation and direct methods do not have good theoretical guarantees of the DR-estimator, but they do not require any attributions apart from tuples of the form (context, considered-actions, action, reward), which are already widely available in our current deployment of PLR. Keeping this in mind, we developed a random vector generator methods. In doing so, we formulated and implemented a Bayesian model (model-4) about the ground-truth conditional distributions of rewards. In our results, we noted that model-4 can improve upon the performance of a baseline MMOE model as the mean reward-vector predictor. Interestingly, we also found that the random vector generator method performed better than the direct-method on our small dataset. Further, we trained our random vector generator on an online policy and validated that it predicted the correct winner among two treatments of an A/B test (online experiment dataset). The random vector generator method does this at 3 to 6 orders of magnitue lower variance than Self Normalized IPS (SNIPS) method. This is an interesting observation, one that is worth exploring both theoretically and empirically.
Model Type 1 2 3 4
Train
Test
Train
Test
Train
Test Data-set Validation Test Metric Reward 1 Reward 2 Reward 3
Mean Variance
Zeroes
Positives Cond’l Mean Pos Cond’l Mean Pos
Mean Variance
Zeroes Positives Negatives Cond’l Mean Non-zero Cond’l Var Non-zero Cond’l Mean Pos
Cond’l Var Pos Cond’l Mean Neg
Cond’l Var Neg Train 0.7441