We show the equivalence of discrete choice models and a forest of binary decision trees. This suggests that standard machine learning techniques based on random forests can serve to estimate discrete choice models with an interpretable output: the underlying trees can be viewed as the internal choice process of customers. Our data-driven theoretical results show that random forests can predict the choice probability of any discrete choice model consistently. Moreover, our algorithm predicts unseen assortments with mechanisms and errors that can be theoretically analyzed. We also prove that the splitting criterion in random forests, the Gini index, is capable of recovering preference rankings of customers. The framework has unique practical advantages: it can capture behavioral patterns such as irrationality or sequential searches; it handles nonstandard formats of training data that result from aggregation; it can measure product importance based on how frequently a random customer would make decisions depending on the presence of the product; it can also incorporate price information and customer features. Our numerical results show that using random forests to estimate customer choices can outperform the best parametric models in synthetic and real datasets when presented with enough data or when the underlying discrete choice model cannot be correctly specified by existing parametric models.

§ INTRODUCTION

Discrete choice models (DCM) have become central to revenue management and e-commerce as they enable firms to predict consumer's choice behavior when confronted with a given assortment of products. Firms that can get inside the mind of their consumers enjoy unique advantages that allow them to implement effective strategies to improve profits or market shares. Firms can then further invest in technologies that sharpen their predictive power. This virtuous cycle has created a number of market juggernauts while those incapable of playing in this field are disappearing from the landscape.

To understand and predict consumers' choice behavior, academics and practitioners have proposed several frameworks, some of which are widely adopted in the industry. One ubiquitous framework is  model-then-estimate. In this framework, a parametric DCM is proposed to explain how a consumer chooses a product when offered an assortment. The parameters are then estimated using historical data. Once the model has been estimated properly, it can then be used as a workhorse to predict the choice behavior of future consumers.

In the model-then-estimate framework, there is a trade-off between flexibility and accuracy.  A flexible DCM incorporates a wide range of patterns of consumers' behavior, but it may be difficult to estimate and may overfit the training data. A parsimonious model, on the other hand, may fail to capture complex choice patterns in the data.
Even estimated correctly, it would be misspecified and not perform well in prediction.
The key to a successful model is to reach a delicate balance between flexibility and predictability.
Not surprisingly, it is not straightforward to find the “sweet spot” when selecting among the large class of parametric DCMs. For this reason a variety of models are usually tested and calibrated and the one which performs the best on test data is then used until more data is collected and the process is repeated.

Another framework favored by data scientists is to estimate without models.
Advanced machine learning algorithms are applied to historical sales data, and used to predict future choice behavior.
The framework skips “modeling” entirely and does not attempt to understand the rationality (or irrationality) hidden behind the patterns observed in the training data.
With engineering tweaks, the algorithms can be implemented efficiently and capture a wide range of choice behavior.
For example, neural networks are known to be able to approximate any continuous functions.

This approach may sound appealing: if an algorithm achieves impressive accuracy when predicting the choice behavior of consumers, why do we care about the actual rationale in consumers' minds when they make choices?
There are two counterarguments. First, the firm may be interested in not only making accurate predictions but also in other goals such as finding an optimal assortment that maximizes the expected revenue, which may not have appeared in the data.
Without a proper model, it is unclear if the goal can be formulated as an optimization problem. Second, when the market environment is subject to secular changes,  having a reasonable model often provides a certain degree of generalizability while black-box algorithms may fail to capture an obvious pattern just because the pattern has not appeared frequently in the past.

In this paper, we introduce a data-driven framework which we call estimate-and-model that combines machine learning with interpretable models, and thus retains the strengths of both frameworks mentioned previously.
The model we propose, binary choice forests, is a mixture of binary choice trees, each of which reflects the internal decision-making process of a potential customer.
We show that the binary choice forest can be used to approximate any DCM, and is thus sufficiently flexible. Moreover, it can be efficiently estimated using random forests <cit.>, a popular machine learning technique that has stood the test of time.
Random forests are easy to implement using R or Python <cit.> and have been shown to have extraordinary predictive power in other applications.
We provide theoretical analyses: as the sample size increases, random forests can successfully recover the binary choice forest, and thus any DCM; random forests serve as adaptive nearest neighbors and effectively use the historical data to extrapolate the choice of future customers; moreover, the splitting criterion used by the random forests is intrinsically connected to the preference ranking of customers.

Besides the theoretical properties, the framework we propose has the following practical advantages:
(1) It can capture patterns of behavior that elude other models, such as irregularity and sequential searches <cit.>; details can be found in Section <ref>.
(2) It can deal with nonstandard formats of historical data, which is a major challenge in practice; details can be found in Section <ref>.
(3) It can return an importance index for all products, based on how frequently a random customer would make decisions depending on the presence of the product; details can be found in Section <ref>.

(4) It can incorporate  prices  and reflect the information in the decision-making of consumers.
(5) It can naturally incorporate customer features and is compatible with personalized online retailing.

§.§ Literature Review

We first review DCMs proposed in the literature following the model-then-estimate framework, in the order of increasing flexibility but more difficult estimation.
The independent demand model and the MNL model <cit.> have very few parameters (one per product), which are easy to estimate <cit.>.
Although the MNL model is still widely used, its inherent property of independence of irrelevant alternatives (IIA) has been criticized for being unrealistic (see  for more details).
The  nested logit model, the Markov chain DCM, the mixed logit model and the rank-based DCM (see, e.g., ) are able to capture more complex choice behavior than the MNL model. In fact, the mixed logit model and the rank-based DCM can approximate any random utility model (RUM), encompassing an important class of DCMs. The estimation of these models is challenging, but there has been exciting progress in recent years <cit.>.
However, the computational feasibility and susceptibility to overfitting remain a challenge in practice.
In addition, the class of RUM belongs to the class of regular models with the property that the probability of choosing an alternative cannot increase if the offered set is enlarged.  Experimental studies show strong evidence that regularity may be violated in practice <cit.>.
Several models are proposed to capture more general behavior than RUM <cit.>, but it is not yet clear if the estimation for such models can be done efficiently.

The binary choice forest in this paper can be seen as a mixture of customer segments, where each segment has the choice behavior represented by a decision tree. In this sense, it is related to recent studies on consumer segmentation such as <cit.>.
This paper focuses on the estimation of DCMs and the segments emerge as a byproduct to improve the predictive accuracy: the trees have equal weights and we do not control for the number of trees (segments).
In contrast, <cit.> design specific clustering/segmentation algorithms so the objectives differ. It is worth noticing that <cit.> also use the tree structure for market segmentation; however, their input consists of customer features while ours is the inclusion of a product.

The specifications of random forests used in this paper are introduced by <cit.>, although many of the ideas were discovered earlier.
The readers may refer to <cit.> for a general introduction.
Although random forests have been very successful in practice, little is known about their theoretical properties relatively.
Most studies are focused on isolated setups or simplified versions of the procedure.
For example, <cit.> study the connection between random forests and adaptive nearest-neighbor methods under stylized assumptions.
<cit.> provide an excellent survey of the recent theoretical and methodological developments in the field. There are recent papers on theoretical properties (consistency and asymptotic normality) under less restrictive assumptions. <cit.> establish the consistency of random forests in regression problems. <cit.> show that asymptotic normality can be established from the “honest” assumption.
These three papers require the regression function to be continuous and the samples to have positive density in the input domain, which do no hold in the context of discrete choice models.
We show that consistency can be established under general assumptions, using standard techniques such as concentration inequalities. Our result is similar to the consistency of single decision trees in <cit.>, but we need to handle the additional issue of resampling in random forests. Moreover, in Section <ref> we utilize the nearest-neighbor interpretation of random forests to explain why the algorithm performs well on  assortments that have not appeared in the data. Such connection is also specific to the application to discrete choice models.

A recent paper by <cit.> proposes a similar tree-based DCM.
They are the first to show that the so-called “decision forest” can approximate any DCMs with arbitrary precision; a similar result is proved with a different approach in this paper.

Our studies differ substantially in the estimation step:
we focus on random forests, while <cit.> follow an optimization approach based on column generation.
On the theoretical side, <cit.> focus on the complexity of the optimization problem. We establish the consistency of random forests, explain why the algorithm works well for unseen assortments, and show that the estimation can accommodate the price information and aggregated choice data.
For the numerical studies, <cit.> focus on the irrational behavior in the data.
In contrast, we investigate the performance of random forests more broadly.
We find that random forests are quite robust and have good performance even compared with the Markov chain model estimated using the expectation-maximization (EM) algorithm, which has been shown to have outstanding empirical performance compared to MNL, the nested logit, the mixed logit and rank-based DCM <cit.>, especially when the training data is large.
It is worth noticing that the applicability of the modeling framework in <cit.> and our paper is greatly extended by an exciting recent study <cit.> that provides an optimization framework to solve the optimal assortment planning problem for tree-based DCMs.

§ DISCRETE CHOICE MODELS AND BINARY CHOICE FORESTS

Consider a set $[N]\triangleq\left\{1,\ldots,N\right\}$ of $N$ products and define $[N]_+ \triangleq [N] \cup \{0\}$ where $0$ represents the no-purchase option.
Let $\bm x \in \left\{0,1\right\}^N$ be a binary vector representing an assortment of products, where $\bm x(i) = 1$ indicates the inclusion of product $i$ in the assortment and $\bm x(i) = 0$ otherwise.
A discrete choice model (DCM)  is a non-negative mapping $p(i,\bm x): [N]_+\times \left\{0,1\right\}^N \to [0,1]$ such that

\begin{align}\label{eq:dcm}
\sum_{i \in [N]_+}p(i,\bm x)=1,\quad
p(i,\bm x)=0\;~~ \text{if }~~\bm x(i) = 0.
\end{align}

Here $p(i,\bm x) \in [0,1]$ represents the probability that a customer selects product $i$ from assortment $\bm x$. We refer to a subset $S$ of $[N]$ as an assortment associated with $\bm x \in \{0,1\}^N$, i.e., $i\in S$ if and only if $\bm x(i) = 1$.
In the remaining paper, we use $p(i, S)$ and $p(i,\bm x)$ interchangeably.

A binary choice tree $t(\bm x)$ maps $\bm x \in \{0,1\}^N$ into $[N]_+$ by sequentially splitting $[0,1]^N$ along $N$ products,
as illustrated by the right panel of Figure <ref>.
Moreover, to be consistent with DCMs, we require that $t(\bm x) = i$ only if $\bm x(i) = 1$.

Equivalently, a binary choice tree partitions $\{0,1\}^N$ into a number of regions, denoted as $\{R_i\}$.
Each $R_i$ corresponding to a leaf node of the tree.
The tree assigns a label $c_i$ for all $\bm x\in R_i$.
Therefore, one can write
$t(\bm x) = \sum_{R_i} c_i \cdot \I{\bm x\in R_i}$.
A binary choice tree representation of a partition when $N=2$ is demonstrated in Figure <ref>.

(0,0) –(0,4) –(4,4) –(4,0) –(0,0);
(0,2) –(2,2);
(2,0) –(2,4);
[->] (4,0) – (5,0) node[below right] Product 1;
[->] (0,4) – (0,5) node[left] Product 2;
[below left] at (0,0) 0;
[below] at (4,0) 1;
[left] at (0,4) 1;
at (1,1) $R_1, c_1 = 0$;
at (3,2) $R_2, c_2 = 1$;
at (1,3) $R_3, c_3 = 2$;

for tree=l sep+=.8cm,s sep+=.5cm,shape=rectangle, rounded corners,
draw, align=center,
top color=white, bottom color=gray!20
[$\bm x(1)\ge 0.5$
[1,edge label=node[midway,left]Y
[$\bm x(2)\ge 0.5$,edge label=node[midway,right]N
[2, edge label=node[midway,left]Y]
[0, edge label=node[midway,right]N]

A binary choice tree representation of the partition.

A  binary choice forest (BCF) is a convex combination or a mixture of multiple binary choice trees.
More precisely, a binary choice forest can be written as

$$f(i, \bm x) = \sum_{b =1}^B w_b \I{t_b(\bm x) = i}$$

where the $t_b(\bm x)$ and $w_b$ are, respectively,  binary choice trees and non-negative weights summing up to one. A BCF can be interpreted as decisions made by $B$ consumer types or segments, with consumers of type $b$ having weight $w_b$ and making decisions based on binary choice tree $t_b(\bm x)$.

Notice that $f(i,\bm x)$ maps $[N]_+\times \left\{0,1\right\}^N \mapsto [0,1]$ just like DCMs do, so a BCF is always a DCM according to the definition (<ref>).
The converse is also true by the next theorem.

Every BCF is a DCM. Every DCM can be represented as a BCF with at most $N\cdot 2^{N-1}+1$ binary choice trees.

A recent paper by <cit.> has independently shown, by construction, that any choice model can be represented by a decision forest where each of the trees has depth $N+1$.

Our result provides a smaller number of binary choice trees needed for the representation.

§ DATA AND ESTIMATION

The main goal of this paper is to provide a practical method to estimate BCFs using random forests, which have been shown to be able to approximate all DCMs.
The numerical recipe for random forests is widely available and implementable.

We assume that arriving consumers make selections independently based on an unknown DCM $p(i, \bm x)$, and that a firm collects data of the form $(i_t, \bm x_t)$ (or equivalently $(i_t,S_t)$) where $\bm x_t$ is the assortment offered to the $t$th consumer and $i_t \in S_t \cup \{0\}$ is the choice made by consumer $t = 1,\ldots, T$.  Our goal is to use the data to construct a family of binary choice trees as a means to estimate the underlying DCM $p(i,\bm x)$ represented by a BCF.
We view the problem as a classification problem: given the input $\bm x$, we would like to provide a classifier that maps the input to a class label $i\in [N]_+$, or the class probabilities.

To this end we use a random forest as a classifier.
The output of a random forest consists of $B$ individual binary decision trees (CART), $\left\{t_b(\bm x)\right\}_{b=1}^B$, where $B$ is a tunable parameter.
Although a single tree only outputs a class label in each region, the aggregation of the trees, i.e., the forest,
is naturally equipped with the class probabilities. Then the choice probability of item $i$ in the assortment $\bm x$ is estimated as

\begin{equation}\label{eq:class-prob}
\sum_{b=1}^B \frac{1}{B}\I{t_b(\bm x)=i},
\end{equation}

which is a BCF measuring the proportion of trees that assign  label $i \in [N]_+$ to input $\bm x$.

We now review the basic mechanism of CART and describe how it can be used to estimate random forests. The CART mechanism  performs recursive binary splitting of the input space $[0,1]^N$, which is extended from $\left\{0,1\right\}^N$.
In each iteration, it selects a product $i\in [N]$ and a split point to split the input space.
More precisely, the split $(i,s_i)$ divides the observations to $\left\{(i_t,\bm x_t): \bm x_t(i)\le s_i\right\}$ and $\left\{(i_t,\bm x_t): \bm x_t(i)> s_i\right\}$.
In our problem, because $\bm x_t \in \left\{0,1\right\}^N$ is at the corner of the hypercube, all split points between 0 and 1 create the same partition of the observations and thus we simply set $s_i\equiv 0.5$.
To select a product for splitting, an empirical criterion is optimized to favor splits that create “purer” regions.
That is, the resulting region should contain data points that mostly belong to the same class.
We use a common measure called Gini index: $\sum_{R_j} \frac{t_j}{T}\sum_{k=0}^N \hat p_{jk}(1-\hat p_{jk})$ where $t_j$ is the number of observations in region $R_j$ of the partition and $\hat p_{jk}$ is the empirical frequency of class $k$ in $R_j$.
It is not hard to see that the Gini index takes smaller values when the regions contain predominantly observations from a single class.
In this case, a product is selected that minimizes the measures and the partition is further refined by a binary split.
This splitting operation is conducted recursively for the regions in the resulting partition until a stopping rule is met.

The main drawback of CART is its tendency to overfitting the training data.
If a deep decision tree is built (having a large number of splits), then it may fit the training data well but introduce large variances when applied to test data.
If the tree is pruned and only has a few leaves (or regions in the input space), then it loses the predictive accuracy.
Random forests, by creating a number of decision trees and then aggregating them, significantly improve the power of single trees and moves the bias-variance trade-off toward the favorable direction.
The basic idea behind random forests is to “shake” the original training data in various ways in order to create decision trees that are as uncorrelated as possible.
Because the decision trees are deliberately “decorrelated”, they can afford to be deep, as the large variances are remedied by aggregating the “almost independent” trees.
Interested readers may refer to <cit.> for a formal discussion.

Next, we explain the details of random forests.
To create $B$ randomized trees, for each $b=1,\dots,B$, we randomly choose $z$ samples with replacement from the $T$ observations (a bootstrap sample).
Only the sub-sample of $z$ observations is used to train the $b$th decision tree.
Splits are performed only on a random subset of $[N]$ of size $m$ to minimize the resulting Gini index.
The random sub-sample of training data and random products to split are two key ingredients in creating less correlated decision trees in the random forest. The depth of the tree is controlled by the minimal number of observations, say $l$, in a leaf node for the tree to keep splitting.

These ideas are formalized in Algorithm <ref>.

Random forests for DCM estimation
[1]
Data: $\left\{(i_t,\bm x_t)\right\}_{t=1}^T$
Tunable hyper-parameters: number of trees $B$, sub-sample size $z\in\left\{1,\dots,T\right\}$,
number of products to split $m\in \left\{1,\dots,N\right\}$, terminal leaf size $l\in\{1,\dots,z\}$
$b=1$ to $B$
Select $z$ observations from the training data with replacement, denoted by $Z$
Initialize the tree $t_b(\bm x)\equiv 0$ with a single root node
some leaf has greater than or equal to $l$ observations belonging to $Z$ and can be split
Select $m$ products without replacement among $\left\{1,\dots,N\right\}$
Select the optimal one to split among the $m$ products that minimizes the Gini index
Split the leaf node into two
Denote the partition associated with the leaves of the tree by $\left\{R_1,\dots,R_M\right\}$;
let $c_i$ be the class label of a randomly chosen observation in $R_i$ from the training data
Define $t_b(\bm x) = \sum_{i=1}^{M} c_i\I{\bm x\in R_i}$
The trees $\left\{t_b(\cdot)\right\}_{b=1}^B$ are used to estimate the class probabilities as (<ref>)

The use of random forests as a generic classifier has a few benefits:
(1) Many machine learning algorithms such as neural networks have numerous hyper-parameters to tune and the performance crucially depends on a suitable choice of hyper-parameters.
Random forests, on the other hand, have only a few hyper-parameters.
In the numerical studies in this paper, we simply choose a set of hyper-parameters that are commonly used for classification problems, without cross-validation or tuning, in order to demonstrate the robustness of the algorithm.
In particularly, we mostly use $B=1000$, $z=T$, $m=\sqrt{N}$ and $l=50$.
The effect of the hyper-parameters is studied in Appendix <ref>.
(2) The numerical recipe for the algorithm is implemented in many programming languages such as R and Python and ready to use.
In Appendix <ref>, we provide a demonstration using scikit-learn, a popular machine learning package in Python that implements random forests, to estimate customer choice.
As one can see, it takes less than 20 lines to implement the procedure.

More specifically, because of the structure of the application, there are three observations.
(1) Because the entries of $\bm x$ are binary $\left\{0,1\right\}$, the split position of decision trees is always $0.5$.
Therefore, along a branch of a decision tree, there can be at most one split on a particular product,
and the depth of a decision tree is at most $N$.
(2) The output random forest is not necessarily a BCF.
In particular, the probability of class $i$, or the choice probability of product $i$ given assortment $\bm x$, may be positive even when $\bm x(i)=0$, i.e., product $i$ is not included in the assortment.

To fix the issue, we adjust the probability of class $i$ by conditioning on the trees that output reasonable class labels:

\begin{equation*}
\label{eq:normalization}
\sum_{b=1}^B\frac{1}{\sum_{j:\bm x(j)=1} \sum_{b=1}^B \I{t_b(\bm x)=j}}\I{t_b(\bm x)=i, \bm x(i)=1}.
%    \sum_{b=1}^B \frac{1}{\sum_{j:\bm x(j)=1}\I{t_b(\bm x)=j}}\I{t_b(\bm x)=i, \bm x(i)=1}.
\end{equation*}

(3) When returning the class label of a leaf node in a decision tree, we use a randomly chosen tree instead of taking a majority vote (Step <ref> in Algorithm <ref>).
While not being a typical choice, it seems crucial in deriving our consistency result (Theorem <ref>),

because a majority vote would favor the choice of product that most consumers make and ignore less attractive products.

§ WHY DO RANDOM FORESTS WORK WELL?

Many machine learning algorithms, including random forests, have strong performances in practice.
However, with a few exceptions, they do not provide an explanation for the predictions.  For example, consistency and asymptotic normality, two most fundamental properties a statistician would demand, are only recently established for random forests under restrictive assumptions <cit.>.
The lack of theoretical understandings can worry practitioners when stakes are high and the failure may have harmful consequences. In this section, we attempt to answer the “why” question.
The section consists of three parts:
(1) random forests are consistent for any DCM, (2) random forests can be viewed as nearest neighbors, whose performance are explained by a few crucial factors, and (3) the splitting rule  (Gini index) can help random forests recover DCMs represented by decision trees.
Note that all three theoretical explanations depend specifically on the structure of the discrete choice problem and do not hold for general classification problems. Therefore, our findings reveal the benefits of applying random forests to DCMs.

§.§ Random Forests are Consistent for Any Discrete Choice Model

We now show that given enough data, random forests can recover the choice probability of any DCM. To obtain our theoretical results, we impose mild assumptions on how the data is generated.

There is an underlying DCM from which all $T$ consumers independently make choices from the offered assortments, generating data $(i_t,\bm x_t)$, $t = 1, \ldots T$.

Notice that the assumption only requires consumers to make choices independently. We do not assume that the offered assortments $\bm x_t$s are IID, and allow the sequence of assortments offered $\bm x_t$ to be arbitrary as the assortments are chosen by the firm and are typically not randomly generated.
Such a design reflects how firms select assortments to maximize expected revenues or to explore customer preferences.

For a given assortment $\bm x$, let $k_T(\bm x)  \triangleq \sum_{t=1}^T \I{\bm x_t=\bm x}$ be the number of consumers who see assortment $\bm x$. We are now ready to establish the consistency of random forests.

Suppose Assumption <ref> holds, then for any $\bm x$ and $i$, if  $~\liminf_{T \to \infty} k_t(x) / T>0$, $l_T$ is fixed, $z_T\to\infty$, $B_T\to\infty$, then the random forest is consistent:

\begin{equation*}
\lim_{T\to\infty}\PR\left(\left|\sum_{b=1}^{B_T} \frac{1}{B_T}\I{t_b(\bm x)=i}-p(i, \bm x)\right|>\epsilon\right) =0
\end{equation*}

for all $\epsilon>0$.

The consistency of individual decision trees have been shown under certain conditions, typically including the diminishing diameter and the increasing number of data points in terminal nodes.
See Theorem 13.1 in <cit.> or Chapters 20 and 21 of <cit.>.
While these conditions hold in our setting, because of the clustering of data points at the corners,
we have to handle the additional issue of resampling in Step <ref> in Algorithm <ref>.
The proof is based on standard concentration inequalities.

According to Theorem <ref>, the random forest can accurately predict the choice probability of any DCM, given that the firm offers the assortment for many times.
Practically, the result can guide us about the choice of parameters.
In fact, we just need to generate many trees in the forest ($B_T\to\infty$), resample many observations in a decision tree ($z_T\to\infty$), and keep the terminal leaf small ($l_T$ is fixed).
The requirement is easily met by the choice of parameters in the remarks following Algorithm <ref>, i.e., $z=T$, $m=\sqrt{N}$ and $l=50$.
Theorem <ref> guarantees good performance of the random forest when the seller has collected a large dataset. This is a typical case in online retailing, especially in the era of “big data.”
Random forests thus provide a novel data-driven approach to model customer choices.
In particular, the model is first trained from data, and then used to interpret the inherent thought process of consumers when they make purchases.
By Theorem <ref>, when the historical data has a large sample size, the model can accurately predict how consumers make decisions in reality.

§.§ Random Forests and Nearest Neighbors

In Section <ref>, we state that when an assortment is offered frequently, the choice probabilities estimated by random forests of this assortment are consistent.
However, this doesn't explain the strong performance of random forests on assortments that have not been offered frequently in the training data (so-called unseen assortments).
In this section, following the intuition provided in <cit.>, we attempt to provide a unique perspective based on nearest neighbors.
To motivate, consider the following examples.

Consider $N=4$ products. Suppose only four assortments are offered in the training data:
$S_1 = \{1,2,3\}$, $S_2 = \{1,2,4\}$, $S_3 = \{3,4\}$, $S_4 = \{1,2\}$.
As a result, the assortment $S=\left\{1,2,3,4\right\}$ (or $\bm x=(1,1,1,1)$) is never offered in the data.
How would random forests predict the choice probabilities of the unseen $S$?
By searching for the terminal leaves which $S$ falls in among individual trees, Step <ref> in Algorithm <ref> uses the samples of the assortment appearing in the training data which happens to be in the same leaf node to extrapolate the choice probabilities of $S$.
If we use Algorithm <ref> with $B = 1000, z = T, m = \sqrt{N}, l = 1$, then Figure <ref> illustrates the frequencies of the three assortments appearing in the same leaf node as $S$ (a deeper color indicates a higher frequency).
As we can see, $S_1$ and $S_2$ are more likely to fall in the same leaf node as $S$, while $S_3$ is less frequent and $S_4$ is never used to predict the choice probabilities of $S$.
The frequency roughly aligns with the “distance” from $S_i$ to the unseen $S$ in the graph, defined as the number of edges to traverse between two vertices.
However, the distance doesn't explain why $S_4$, which is of the same distance as $S_3$, is never used.
We will address this puzzle later in the section.

[circle, draw, color = black, fill = red, fill opacity = 1, minimum size=38pt, label = [red] left: Unseen $S$] (1111) at (0,) 1111;
[circle, draw, color = black, fill = blue, fill opacity = 0.5, text opacity = 1, label =  left: $S_2$] (1101) at (0,0) 1101;
[circle, draw, color = black, fill = blue, fill opacity = 0, text opacity = 1, label =  right: $S_4$] (1100) at (,0) 1100;
[circle, draw, color = black, fill = blue, fill opacity = 0.6, text opacity = 1, label =  below right: $S_1$] (1110) at (,) 1110;
(1001) at (, ) 1001;
(1000) at (+, ) 1000;
(1011) at (, +) 1011;
(1010) at (+,+) 1010;

(0101) at (,̱)̱ 0101;
(0100) at (*̱2, )̱ 0100;
(0111) at (,̱ *̱2) 0111;
(0110) at (*̱2, *̱2) 0110;
(0001) at (+̱ξ,+̱) 0001;
(0000) at (*̱2+ξ, +̱) 0000;
[circle, draw, color = black, fill = blue, fill opacity = 0.2, text opacity = 1, label =  above: $S_3$] (0011) at (+̱ξ, *̱2+) 0011;
(0010) at (*̱2+ξ, *̱2+) 0010;

[black] (1111) – (1110) – (1100) – (1101) – (1111);
[black] (1011) – (1010) – (1000) – (1001) – (1011);
[black] (1111) – (1011);
[black] (1110) – (1010);
[black] (1101) – (1001);
[black] (1100) – (1000);

[black] (0111) – (0110) – (0100) – (0101) – (0111);
[black] (0011) – (0010) – (0000) – (0001) – (0011);
[black] (0111) – (0011);
[black] (0110) – (0010);
[black] (0101) – (0001);
[black] (0100) – (0000);

[black] (1111) – (0111);
[black] (1101) – (0101);
[black] (1110) – (0110);
[black] (1100) – (0100);
[black] (1001) – (0001);
[black] (1000) – (0000);
[black] (1011) – (0011);
[black] (1010) – (0010);

The frequency (number of trees in the forest) at which the assortments in the training data are used to predict the unseen assortment for $N=4$.

To provide a more concrete example, we consider $N=10$ and only allow $100$ out of $2^{10}=1024$ assortments to be included in the training data.
After generating $T=1000$ samples for the training data using the MNL model,
we use Algorithm <ref> with $B = 1000, z = T, m = \sqrt{N}, l = 1$ to predict the choice probability of the unseen assortment $S = \{1,2,3,4,5,6\}$.
The 10 most frequent assortments in the training data that fall into the same leaf node as $S$ are listed in Table <ref> as well as their frequencies.
We also count the number of different products between the assortments and $S$, in terms of the symmetric difference of two sets.
Clearly, the frequency is strongly negatively associated with the number of different products, a distance measure of two assortments.

Assortment     #Different products     Frequency

$\{1,2,3,4,5\}$       1      0.328

$\{1,2,3,4,5,6,8\}$       1      0.202

$\{1,2,3,6\}$       2       0.173

$\{1,2,4,6\}$       2      0.097

$\{1,2,4,5,6,7,10\}$       3       0.074

$\{1,3,4,6,10\}$       3       0.051

$\{2,3,4,5,6,9\}$      2     0.038

$\{1,3,4,6,7\}$      3     0.032

$\{1,2,5,6,9,10\}$      4     0.004

$\{1,4,5,6,9\}$       3      0.001

The frequency at which the assortments in the training data are used to predict the unseen assortment $S=\left\{1,2,3,4,5,6\right\}$ for $N=10$.

The examples reveal the intrinsic connection between random forests and nearest neighbors.
Namely, if an assortment is not offered in the training data, then random forests would look for its neighboring assortments in the training data, by grouping them in the same leaf node, to predict the choice probabilities of the unseen assortment.
Different from nearest neighbors, random forests don't always find the nearest one, as the chosen neighbor is determined by layers of mechanisms such as splitting and randomization.
Arguably, it is this difference that leads to the improved performance of random forests, as well as its intractability.

Based on this perspective, there are three crucial factors that determine the performance of random forests when predicting unseen assortments:

* How “far” is the unseen assortment to the neighboring assortments in the training data? If all the assortments in the training data include many different products from the unseen assortment, then the extrapolation may not perform well.
This is a property regarding what assortments are offered in the training data and the unseen assortment.

* How “continuous” is the DCM to be estimated? The information of the neighbors is not helpful if the choice probabilities vary wildly as the assortment “travels” to the neighbors.
This is a property regarding the underlying DCM that generates the choice of the training data.

* How representative are the choices made by customers? To extrapolate to the unseen assortment, the estimated choice probabilities of the assortments offered in the training data need to be accurate.
This is determined by the number of samples for each assortment.

Next, we analyze the impact of the three factors on the performance of random forests.

§.§.§ Distance to Neighbors in the Training Data

For two assortments (subsets) $S_1$ and $S_2$, the symmetric difference is defined as $ S_1 \ominus S_2 \coloneqq S_1 \cup S_2 - S_1 \cap S_2 = (S_1 - S_2) \cup (S_2-S_1)$.
We define the distance between $S_1$ and $S_2$, $d(S_1,S_2)$, by the cardinality of the symmetric difference:

\begin{equation}\label{eq:distance}
d(S_1,S_2) \coloneqq |S_1 \ominus S_2|.
\end{equation}

This is the number of different products mentioned in Examples <ref> and <ref>.

We first attempt to study what assortments in the training data can potentially be a neighbor to the unseen assortment, i.e., they fall into the same leaf node in some trees in the forest.
Let $\mathcal{T} \subseteq 2^{[N]}$ denote the family of assortments observed in training data.

For an unseen assortment $S$ and an assortment $S_1\in \mathcal T$, we define the concept of Potential Nearest Neighbor (PNN).

The assortment $S_1\in \mathcal T$ is a PNN of $S\notin \mathcal T$ if for all $S_2\in \mathcal T$, we have $S \ominus S_2 \not\subset S \ominus S_1$.

In other words, $S_1$ is a PNN of $S$ if no other assortment observed in the training data
dominates $S_1$ in terms of the similarity to $S$ at the product level.
The concept is closely related to which sample can fall into the same terminal leaf node as $S$.

Suppose the terminal leaf size $l=1$ in Algorithm <ref>. An unseen assortment $S \notin \mathcal{T}$ and an assortment $S_i \in \mathcal{T}$ can fall into the same terminal leaf node for some trees if and only if $S_i$ is a PNN of $S$.

We study the case $l=1$ for the simplicity of the analysis and to provide technical insights.
For $l>1$, the condition for PNN is much more involved.
Moreover, $l=1$ is a popular choice for classification problems <cit.>.

Based on Proposition <ref>, the distance of an unseen assortment $S$ to the training data boils down to the distance to its PNNs.
We first provide an estimate of this distance when a fraction of assortments are observed in the training data.
In particular, we show that for all PNNs of an unseen assortment to be close to it, the training set only needs to have $\Big\lceil2^N \cdot \lceil\log_2 N\rceil \cdot \log N / (N-2)\Big\rceil$ assortments.

Suppose we draw $\Big\lceil2^N \cdot \lceil\log_2 N\rceil \cdot \log N / (N-2)\Big\rceil$ assortments with replacement as the training data and set $l=1$ in Algorithm <ref>.
For an arbitrary assortment $S$, with probability no less than $1 - 1/(\lceil \log_2 N \rceil)!$
[We can show that $(\lceil \log_2 N \rceil)!>\lceil\log_2 N\rceil \cdot (\lceil\log_2 N\rceil -1)\cdot \ldots \cdot (\lceil\log_2 N /2\rceil) > (\log_2 N / 2)^{\log_2 N/2}$, so all bounds hold when we replace $\lceil\log_2 N\rceil!$ by $(\log_2 N/2)^{\log_2 N/2}$.],
the distance $d(S,S')\leq \lceil\log_2 N\rceil-1$ for all PNNs $S'$.

In other words, if a fraction $O(\log(N)^2/N)$ of assortments appear in the training set, then the distance of $S$ to its PNNs is guaranteed (in a probabilistic sense) to be of order $O(\log(N))$.
However, this is a fairly strong event:
for all the trees in the forest, the assortment $S'$ that falls into the same terminal leaf node as $S$ is close to, or equivalently, has a similar set of products to $S$.
It guarantees the choice probabilities of $S'$ can predict those of $S$ reasonably well.
In practice, even if there are a number of trees that predict $S$ by a PNN that includes a very different set of products, whose choice probabilities may induce a large bias,
random forests are able to mitigate the bias by averaging them with other trees.
This is one of the reasons why random forests perform much better than CARTs in general.

To explore such an effect, we consider the expected distance of a PNN.
To simplify the analysis, we consider a stylized splitting rule: random splitting.
That is, we take $m=1$ in Algorithm <ref>.
Random splitting is commonly used to shed theoretical insights about the performance of random forests <cit.>.
It also satisfies the “honest tree” assumption in <cit.>.

Note that for an individual tree, it never splits at the same product more than once, because of the structure of the problem.
Therefore, under random split, one can treat the sequence of attempted splits of an individual tree as a permutation of $(1,\dots,N)$.
Note that not all products in the permutation show up in the tree due to two reasons: (1) the split corresponding to some product in the permutation may result in empty leaves containing no training data, in which case the split is redrawn (moving to the next one in the permutation) and (2) terminal leaves containing less than $l$ data points cannot be further split before reaching the end of the permutation, in which case the training of this tree is completed.
Similar to the setup in Proposition <ref>, the $M$ assortments in the training data are randomly drawn from $2^{[N]}$ with replacement.
Therefore, by symmetry, we focus on a specific permutation $1,2,\dots$ from now on.

We encode the $M$ assortments in the training data as binary vectors $\bm x_i\in \{0,1\}^{N}$, $i=1,\dots,M$, as mentioned in Section <ref>.
If we fix the unseen assortment $S$, or equivalently, $\bm x$, to be $\bm x=(1,\dots,1)$ by symmetry, then
the distance $d(S,S_i)=N-\|\bm x_i\|_1$ is the number of $0$s in $\bm x_i$.
Whenever a split is performed on the $j$th product, only the assortments among $\{\bm x_i\}_{i=1}^M$ whose $j$th digit is 1 may still be in the same leaf node as $\bm x$.
Under the splitting order of $1,2,\dots$ mentioned above, for instance,
consider $N = 3$ and the three assortments in the training data $\bm x_1 = (1,0,1), \bm x_2 = (1,0,0), \bm x_3 = (0,1,1)$.
In the first split on product one, $\bm x_1$ and $\bm x_2$ are still in the same leaf as $\bm x=(1,1,1)$.
The second split on this leaf is discarded because both $\bm x_1$ and $\bm x_2$ do not include product two and the split creates empty leaves.
In the third split, $\bm x_1$ is the only product remaining in the terminal leaf node of $\bm x$.
From this example, it is easy to see that the assortment in the same terminal node of $\bm x$ must be the largest one among $\{\bm x_i\}_{i=1}^M$, which are interpreted as binary numbers.

With this interpretation, the average distance from $S$ to a PNN in the training data is equivalent to the following problem.
Consider $M$ random binary numbers drawn with replacement from $\{0,1,\dots,2^N-1\}$.
What is the number of zeros in the largest number?
Note that the number of zeros is precisely the distance from the assortment corresponding to this binary number and the unseen $S$, or $\bm x=(1,\dots,1)$, according to definition (<ref>).
It allows us to derive the next result.

Suppose we draw $M = \lceil 2^N / N\rceil$ assortments with replacement as the training data and set $l=m=1$ in Algorithm <ref>.
For an arbitrary assortment, its expected distance to the PNN in the training data is bounded above by
$\lceil\log_2(N) /2\rceil+a$, where $a \leq 0.455$.

Although the order of magnitude seems to be similar to Proposition <ref>, i.e.,
with $\tilde{O}(2^N/N)$ assortments[The notation $\tilde O$ represents the asymptotic order neglecting the logarithmic factors.], the distance is controlled by $O(\log_2(N))$,
the constants and logarithmic factors may play a role in explaining why random forests (the average distance) perform better than individual trees (all PNNs).
We have also conducted numerical studies showing the bound in Proposition <ref> is more or less tight:
If $M$ grows polynomially in $N$ or even $M=O(N^{\log N})$, then the average distance cannot be bounded by $O(\log(N))$. See Appendix <ref>.

If the $M$ assortments in the training data are selected by the firm to minimize the distance to all unseen assortments, then how do the results change?

This is similar to the setting of experimental design.
For this question, we refer to the literature on the so-called Covering Code problem, see <cit.>.

The Covering Code problem aims to find the minimum number of binary vectors in $\{0,1\}^N$, such that every other element in the set is within distance $r$ of some selected ones.
To our knowledge, this is still an open problem and numerous bounds are established.

In general, when $M = \lceil 2 \cdot 2^N / N\rceil$, these binary vectors can cover all the space within distance 1.
This improves the distance in Proposition <ref> from $\log_2(N)$ to $1$.

The literature may provide some useful instructions on how to design assortments in a new market in order to explore it efficiently.

We summarize the main results in this section below.
When $M = \Big\lceil2^N \cdot \lceil\log_2 N\rceil \cdot \log N / (N-2)\Big\rceil$, we guarantee the distance of all PNNs to be less than $\lceil \log_2 N \rceil-1$ with high probability.
If random split is used instead of the Gini index, then when $M = \lceil2^N/N\rceil$, the average distance is bounded by $\lceil\log_2 N / 2\rceil+a$, where $a$ is a constant smaller than 0.455.
When the firm can design assortments to minimize the distance, $M = \lceil 2 \cdot 2^N / N\rceil$ assortments are sufficient to guarantee that every other assortment has a PNN of distance 1.

§.§.§ Continuity of DCMs

Having established bounds on the distance to PNNs of an unseen assortment, we next explore the continuity of DCMs.
This is a crucial property: the estimated choice probabilities for an assortment appearing frequently in the training data can be used to extrapolate an unseen assortment, only if choice probabilities do not vary significantly when the assortment changes slightly.
However, the notion of continuity itself is ambiguous in this study and deviates from the literature on random forests, because of two reasons:
First, the $\bm x$-space of our problem is not continuous and consists of the extreme points of a hypercube;
Second, the “$y$” variable is a vector of choice probabilities.

To formalize the notion,
define the following quantity between the choice probabilities of two assortments $S_1, S_2$ under a given DCM $p(i,S)$:

\begin{equation}
\Phi(S_1, S_2) \coloneqq \frac{\sum_{i \in [N]_+} \Big|p(i, S_1) - p(i, S_2)\Big|}{d(S_1,S_2)}.
\end{equation}

The quantity is similar to $(f(x)-f(y))/(x-y)$ for continuous functions: how close are their choice probabilities relative to the distance of $S_1$ and $S_2$?
If $\Phi(S_1, S_2)$ can be bounded, then the DCM is more or less “Lipschitz continuous” and the proximity of the unseen assortments to PNNs (results in Section <ref>) leads to good performance of random forests.

The DCM is $c$-continuous if for all $\emptyset \subsetneq S_1,S_2 \subset [N]$ and $S_1 \neq S_2$,

\begin{equation}
\label{eq:c-continuous}
\Phi(S_1,S_2) \leq c / N.
\end{equation}

By triangular inequality, it is sufficient to show a DCM is $c$-continuous if (<ref>) holds for all $S_1, S_2$ such that $d(S_1, S_2) = 1$.
If a DCM is $c$-continuous, then roughly speaking, the difference in the choice probabilities of two neighboring assortments with distance one is $c/N$.
Combining the results with Section <ref>, if the distance between two assortments is $O(\log N)$ (e.g., Proposition <ref>), then the error in the extrapolation of the choice probabilities is $O(\log N/N)$.
We next consider the continuity of popular DCMs.

The MNL model.
Suppose $p(i,S)= v_i/(v_0+\sum_{j\in S}v_j)$ where $\{v_l\}_{l \in [N]_+}$ represents the attraction of the products.
Then for $\emptyset \subsetneq S \subsetneq [N]$ and $j \notin S$ we have that

\begin{equation*}
\Phi(S, S \cup \{j\}) = \frac{2v_j}{v_0+v_j+\sum_{l \in S} v_l},
\end{equation*}

If the size of $S$ is $\epsilon N$, then it is easy to verify that $\Phi(S, S \cup \{j\})\le 2v_{\max}/(v_0+v_{\max}+\epsilon v_{min}N)$.

Rank-based DCMs.
Suppose $\pi$ is a permutation of $[N]$ and $\pi(i)$ denotes the rank of product $i$ in $\pi$.

Define $\pi^*(S)\coloneqq \argmin_{i \in S_+} \pi(i)$ to be the top choice in $\pi$ when $S$ is offered.
The rank-based model is represented by $w_{\pi}$, the weight of customers whose preference is consistent with $\pi$ in the population.
One can show that

\begin{equation*}
\Phi(S, S \cup \{j\}) = \sum_{j = \pi^*(S \cup \{j\})} w_\pi.
\end{equation*}

If the fraction of customers who rank $j$ as the top choice in $S\cup \left\{j\right\}$ is small, then the DCM is more continuous according to Definition <ref>.

§.§.§ Sampling Error

Another source of error stems from the empirical distribution used to estimate the choice probabilities of the assortments in the training data.

In the terminal leaf node, suppose a tree uses the choice probabilities of $S'$ to predict those of the unseen $S$.
Moreover, let $k$ denote the number of observations for $S'$ in the training data.
For each $i \in S \cap S'$, the frequency of customers choosing $i$ from the assortment $S'$ can be approximated by a normal distribution with mean $p(i,S')$ as the sample size increases.
The standard deviation is bounded by $\sqrt{p(i,S')(1-p(i,S'))/k} \leq 1/(2\sqrt{k})$.
Fortunately, the sampling error is more or less independent of the other two sources of errors articulated in Section <ref> and <ref> and can be controlled using the standard concentration inequalities.
In particular, when an assortment has $O(|S|^2 \cdot N^2 / (\log N)^2)$ samples, the error in using the frequencies to approximate the choice probabilities is at most $O(\log N / (N \cdot |S|))$.

§.§.§ Combining the Errors

In this section, we provide a unified bound combining the three sources mentioned above.
It provides a finite sample result for the performance of random forests predicting unseen assortment.

Suppose the DCM satisfies $c$-continuity and $l=1$ in Algorithm <ref>.

* If we draw $\Big\lceil2^N \cdot \lceil\log_2 N\rceil \cdot \log N / (N-2)\Big\rceil$ assortments with replacement in the training data and each assortment $S'$ has at least $\lceil\frac{N^3 \cdot (|S'|+1)^2}{c_1^2(\log_2 N)^2}\rceil$ transactions, then the error of predicting an unseen assortment using Algorithm <ref> is bounded by $(c+c_1) (\log_2 N) / N$ with probability no less than $1-1/N-1/(\lceil \log_2 N \rceil)!$;

* If $m=1$ (random splitting) and we draw $\lceil 2^N / N\rceil$ assortments with replacement and each assortment $S' $ has at least $\lceil\frac{N^2 \cdot (|S'|+1)}{ c_1^2(\log_2 N)^2}\rceil$ transactions for each assortment in the training data, then the expected error of predicting an unseen assortment using Algorithm <ref> is bounded by $((c/2+c_1)(\log_2 N) + 1.455c)/ N$.

Roughly speaking, when the number of assortments in the training data is $\tilde O(2^N/N)$
and the transactions of each assortment is $O(N^2)$,
the estimation error of random forests is $\tilde O(1/N)$.
Note that the result only provides an upper bound for the error and we have seen much better performance of random forests in practice.

§.§ Gini Index Recovers the Ranking

In Section <ref>, we have shown that any DCM can be represented by a mixture of binary choice trees.
Moreover, through numerous experiments, we have found out that random forests perform particularly well when the data is generated by DCMs that can be represented by a few binary decision trees.
In this section, we further explore this connection by studying a concrete setting where the DCM is represented by a single decision tree. Without loss of generality, we assume that customers always prefer product $i$ to $i+1$, for $i=1,\dots,N-1$, and product $N$ to the no-purchase option.
Equivalently, the DCM is a single ranking for all customers:
$1 \succ 2 \succ \ldots \succ N\succ 0$. The following finite-sample result demonstrates that the ranking can be recovered from the random forest with high probability.
Since the bound scales exponentially in $T$, the predictive accuracy improves tremendously with data size.

Suppose the actual DCM is a preference ranking and the assortments in the training data are sampled uniformly and independently: each assortment includes product $j$ with probability $1/2$ for all $j=1,\dots,N$.
The random forest algorithm with sub-sample size $z=T$ (without replacement), $m=N$, terminal leaf size $l = 1$ and $B=1$ correctly predicts the choices of more than $(1-\epsilon)2^N$ assortments with probability no less than

\begin{equation*}
1-\sum_{i=1}^k \left[13\exp\left(-\frac{T}{164\cdot 2^{i-1}}\right)+10(N-i-1)\exp\left(-\frac{T}{113 \cdot 2^{i-1}}\right)\right]
\end{equation*}

where $k=\lceil \log_2 \frac{1}{\epsilon} \rceil$.

The proof of the theorem reveals an intrinsic connection between the Gini index and the recovery of the ranking.
We analyze the deterministic output of the theoretical random forests when the data size is infinite.
It allows us to show that the theoretical Gini index leads to a sequence of splits consistent with the ranking, i.e., the ranking is recovered under the theoretical random forest.
For example, if the first split is on product $i$, then the resulting theoretical Gini index is

\begin{equation*}
\frac{2}{3}-\frac{1}{3\cdot 2^{2i-2}}.
\end{equation*}

In other words, the first split would occur on product one under the theoretical random forest.
Then we analyze the difference between empirical and theoretical Gini indices and bound the probability of incorrect splits using concentration inequalities. The recursive splits are analyzed using the union bound.

The proof provides the following insight into why random forests may work well in practice:
The Gini index criterion tends to find the products that are ranked high in the rankings because they create “purer” splits that lower Gini index.
As a result, the topological structure of the decision trees trained in the random forest is likely to resemble that of the binary choice trees underlying the DCM generating the data.

We also complement the results in Theorem <ref> by additional numerical studies in Appendix <ref>.
Numerically the result still holds when the training data is not uniform.
We provide some examples showing that in the cases when random forests fail to recover the rankings exactly, the predicted probability is still quite accurate as random forests attempt to “restructure” the tree.
Moreover, we demonstrate the insights that when the rank-based DCM consists of more than one rankings (customer segments), the random forest may output a tree that concatenates and merges multiple rankings.

§ FLEXIBILITY AND PRACTICAL BENEFITS OF RANDOM FORESTS

In this section, we demonstrate the flexibility of random forests and how the method can be adapted in practice to handle different situations.

§.§ Behavioral Issues

Because of Theorem <ref> and Theorem <ref>, random forests can be used to estimate any DCMs.
For example, there is empirical evidence showing that behavioral considerations of consumers may distort their choice, e.g., the decoy effect <cit.>, comparison-based choices <cit.> and search cost <cit.>.
It implies that regular (see Section <ref>) DCMs cannot predict the choice behavior well.
It is already documented in <cit.> that the decision forest can capture the decoy effect.
In this section, we use the choice forest to model consumer search.

<cit.> proposes a sequential search model with search costs.
Before the search process, consumers only know the distribution of $V_j$, the net utility of product $j \in [N]$, and the cost $c_j$ to learn the realization of $V_j$.
Let $z_j$ be the root of the equation $E[(V_j - z_j)^+]  = c_j$ and suppose that  products are sorted in the descending order of the $z_j$s.
<cit.> shows that it is optimal not to purchase if the realized value of the no-purchase alternative, $ V_0$, exceeds $z_1$. Otherwise the consumer searches product one at a cost $c_1$ and $W_1 = \max(V_1, V_0)$ is computed.
The search process stops $W_i$ exceeds $z_{i+1}$ for the first time with the consumer selecting the best product among those that were searched.

We next show that this search process can be represented by binary choice trees.
Consider three products ($N=3$).
Suppose that the products are sorted so that $z_1>z_2>z_3>0$, so the consumer searches in the order of product one $\to$ product two $\to$ product three. Suppose that an arriving customer has realized utilities satisfying  $v_2> z_3 > v_1>v_3$. Then the decision process is  illustrated by the tree in Figure <ref>.
For example, suppose products $\{1,3\}$ are offered. The customer first searches product one, because the reservation price of product one $z_1$ is the highest. The realized valuation of product one is, however, not satisfactory  ($v_1<z_3 < z_1$). Hence the customer keeps on searching for the product with the second-highest reservation price in the assortment, which is product 3.
However, the search process results in an even lower valuation of product three $v_3<v_1$.
As a result, the customer stops and chooses product one.
Clearly, a customer with different realized valuations would conduct a different search process, corresponding to a  different decision tree.

for tree=l sep+=.5cm,s sep+=.2cm,shape=rectangle, rounded corners,
draw, align=center,
top color=white, bottom color=gray!20
[Has product 1
[Has product 2, edge label=node[midway,left]Y
[Choose 2,edge label=node[midway,left]Y]
[Has product 3,edge label=node[midway,right]N
[Choose 1,edge label=node[midway,left]Y]
[Choose 1,edge label=node[midway,right]N]
[Has product 2,edge label=node[midway,right]N
[Choose 2,edge label=node[midway,left]Y]
[Has product 3,edge label=node[midway,right]N
[Choose 3,edge label=node[midway,left]Y]
[No purchase, edge label=node[midway,right]N]

The sequential search process when $N=3$ and the realized valuations and reservation prices satisfy $v_2>v_1>v_3$, $z_1>z_2>z_3>0$ and $v_2>z_3>v_1$.

§.§ Aggregated Choice Data

One of the most pressing practical challenges in data analytics is the quality of data.
In Section <ref>, the historical data $\left\{(i_t,\bm x_t)\right\}_{t=1}^T$ is probably the most structured and granular form of data a firm can hope to acquire.
While most academic papers studying the estimation of DCMs assume this level of granularity, in practice it is frequent to see data in a more aggregate format.  As an example, consider an airline offering three service classes E, T and Q of a flight where data is aggregated over different sales channels over a specific time window during which there may be changes in the offered assortments.  The company records information at certain time clicks as in Table <ref>.

Class     Closure percentage     #Booking

E     20%     2

T     0%    5

Q     90%    1

A sample daily data of offered service classes and number of bookings.

For each class, the closure percentage reflects the fraction of time that the class is not open for booking, i.e., included in the assortment.
Thus, 100% would imply that the corresponding class is not offered during that time window.
The number of bookings for each class is also recorded.
There may be various reasons behind the aggregation of data.
The managers may not realize the value of high-quality data or are unwilling to invest in the infrastructure and human resources to reform the data collection process.

Fortunately, random forests can deal with aggregated choice data naturally.
Suppose the presented aggregated data has the form
$\left\{(\bm p_s, \bm b_s)\right\}_{s=1}^S$, where $\bm p_s\in [0,1]^N$ denotes the closure percentage of the $N$ products in day $s$, $\bm b_s\in \Z_+^{N+1}$ denotes the number of bookings[Again, we do not deal with demand censoring in this paper and assume that $\bm b_s$ has an additional dimension to record the number of consumers who do not book any class.], and the data spans $S$ time windows.
We  transform the data into the desired form as follows:
for each time window $s$, we create $ D_s\triangleq \sum_{k=0}^N \bm b_s(k)$ observations, $\left\{(i_{s,k}, \bm x_{s,k})\right\}_{k=1}^{D_s}$.
The predictor $\bm x_{s,k}\equiv \bm 1-\bm p_s \in[0,1]^N$ and let the choices $i_{s,k}$ be valued $j$ for $b_s(j)$ times, for $j=0,\dots,N$.

To explain the intuition behind the data transformation, notice that we cannot tell from the data which assortment a customer faced when she made the booking.
We simply take an average assortment that the customer may have faced, represented by $\bm 1-\bm p_s$.
In other words, if $1-\bm p_s(j)\in[0,1]$ is large, then it implies that product $j$ is offered most of the time during the day, and the transformation leads to the interpretation that consumers see a larger “fraction” of product $j$.
As the closure percentage has a continuous impact on the eventual choice, it is reasonable to transform the input into a Euclidean space $[0,1]^N$,
and build a smooth transition between the two ends $\bm p_s(j)=0$ (the product is always offered) and $\bm p_s(j)=1$ (the product is never offered).

The transformation creates a training dataset for classification with continuous input.
The random forest can accommodate the data with minimal adaptation.
In particular, all the steps in Algorithm <ref> can be performed.
The tree may have different structures:
because the predictor $\bm x$ may not be at the corner of the unit hypercube anymore,
the split points may no longer be at 0.5.

§.§ Product Importance

Random forests can be used to assign scores to each product and rank the importance of products.
A common score, mean decrease impurity (MDI), is based on the total decrease in node impurity from splitting on the product, averaged over all trees <cit.>.
The score for product $m$ is defined as

\begin{align*}
\text{MDI}(m) &= \frac{1}{B} \sum_{b=1}^B \sum_{\substack{\text{all splits } s\\\text{ in the $b$th tree}}} (\text{fraction of data in the parent node of } s)\\
&\quad \times(\text{reduction in the Gini index caused by }s)\times\I{s\text{ splits on }m}.
\end{align*}

In other words, if consumers make decisions frequently based on the presence of product $m$ (a lot of splits occur on product $m$), or
their decisions are more consistent after observing the presence of product $m$ (the Gini index is reduced significantly after splitting on $m$), then the product gains more score in MDI and regarded as important.
To illustrate this measure, we provide examples in Appendix <ref>.

The identification of important products provides simple yet powerful insights into the behavioral patterns of consumers.
Consider the following use cases:
(1) An online retailer wants to promote its “flagship” products that significantly increase the conversion rate.
By computing the MDI from the historical data, important products can be identified without extensive A/B testing.
(2) Due to limited capacity, a firm plans to reduce the available types of products in order to cut costs.
It could simply remove the products that have low sales according to the historical data.
However, some products, while not looking attractive themselves, serve as decoys or references and boost the demand of other products.
Removing these products would distort the choice behavior of consumers and may lead to unfavorable consequences.
The importance score provides an ideal solution: if a product is ranked low based on MDI, then it does not strongly influence the decision-making of consumers.
It is therefore safe to leave them out.
(3) When designing a new product, a firm attempts to decode the impact of various product features on customer choices.
Which product feature is drawing the most attentions?
What do attractive products have in common?
To conduct successful product engineering, first it needs to use the historical data to nail down a set of attractive products.
Moreover, to quantify and separate the contribution of various features, a numerical score of product importance is necessary.
The importance score is a more reasonable criterion than sales volume because the latter cannot capture the synergy created between the products.

§.§ Incorporating Price Information

One benefit of a parametric DCM, such as the MNL or nested logit model, is the ability to account for covariates.
For example, in the MNL model, the firm can estimate the price sensitivity of each product, and extrapolate/predict the choice probability when the product is charged at a new price that has never been observed in the historical data.
Many nonparametric DCMs cannot easily be extended to new prices.
In this section, we show that while enjoying the benefit of a nonparametric formulation, random forests can also accommodate the price information.

Consider the data of the following format: $\left\{(i_t,\bm p_t)\right\}_{t=1}^T$, where $\bm p_t\in [0,+\infty]^N$ represent the prices of all products.
For product $j$ that is not included in the assortment offered to customer $t$, we set $\bm p_t(j)=+\infty$.
This is because when a product is priced at $+\infty$, no customer would be willing to purchase it, and it is equivalent to the scenario that the product is not offered at all.

Therefore, compared to the binary vector $\bm x_t$ that only records whether a product is offered, the price vector $\bm p_t$ encodes more information.

However, the predictor $\bm p$ can not be readily used in random forests.
The predictor space $[0,+\infty]^{N}$ is unbounded, and the value $+\infty$ added to the extended real number line is not implementable in practice.
To apply Algorithm <ref>, we introduce link functions that map the input into a compact set.

A function $g(\cdot):[0,+\infty)\mapsto (0,1]$ is referred to as a link function, if (1) $g(x)$ is strictly decreasing, (2) $g(0)=1$, and (3) $\lim_{x\to +\infty} g(x)=0$.

The link function can be used to transform a price $p\ge 0$ into $(0,1]$.
Moreover, because of property (3), we can naturally define $g(+\infty)=0$.
Thus, if product $j$ is not included in assortment $\bm x_t$, then $g(\bm p_t(j))=g(+\infty)=0=\bm x_t(j)$.
If product $j$ is offered at the low price, then $g(\bm p_t(j))\approx g(0)= 1$.
After the transformation of inputs, $\bm p_t\to g(\bm p_t)$[When $g(\cdot)$ is applied to a vector $\bm p$, it is interpreted as applied to each component of the vector.], we introduce a continuous scale to the problem in Section <ref>.
Instead of binary status (included or not), each product now has a spectrum of presence, depending on the price of the product.
Now we can directly apply Algorithm <ref> to the training data $\left\{(i_t,g(\bm p_t))\right\}_{t=1}^T$ after modifying Step <ref>, because the algorithm needs to find not only the optimal product to split but also the optimal split location.
The slightly modified random forests are demonstrated in Algorithm <ref>.

Random forests for DCM estimation with price information
[1]
Data: $\left\{(i_t,\bm p_t)\right\}_{t=1}^T$
Tunable parameters: number of trees $B$, sub-sample size $z\in\left\{1,\dots,T\right\}$,
number of products to split $m\in \left\{1,\dots,N\right\}$, terminal leaf size $l\in\{1,\dots,z\}$, a link function $g(\cdot)$
Transform the training data to $\left\{(i_t,g(\bm p_t))\right\}_{t=1}^T$
$b=1$ to $B$
Select $z$ observations from the training data with replacement, denoted by $Z$
Initialize the tree $t_b(g(\bm p))\equiv 0$ with a single root node
some leaf has greater than or equal to $l$ observations belonging to $Z$ and can be split
Select $m$ products without replacement among $\left\{1,\dots,N\right\}$
Select the optimal one among the $m$ products and the optimal position to split that minimize the Gini index
Split the leaf node into two
Denote the partition associated with the leaves of the tree by $\left\{R_1,\dots,R_M\right\}$;
let $c_i$ be the class label of a randomly chosen observation in $R_i$ from the training data
Define $t_b(g(\bm p)) = \sum_{i=1}^{M} c_i\I{g(\bm p)\in R_i}$
The choice probability of product $i$ given price vector $\bm p$ is $\sum_{b=1}^B \frac{1}{B}\I{t_b(g(\bm p))=i}$

Because of the nature of the decision trees, the impact of prices on the choice behavior is piecewise constant.
For example, Figure <ref> illustrates a possible binary choice tree with $N=3$.

for tree=l sep+=.5cm,s sep+=.2cm,shape=rectangle, rounded corners,
draw, align=center,
top color=white, bottom color=gray!20
[$g(\bm p(1))>0.3$
[$g(\bm p(1))>0.9$, edge label=node[midway,left]Y
[1,edge label=node[midway,left]Y]
[$g(\bm p(2))>0.5$,edge label=node[midway,right]N
[2,edge label=node[midway,left]Y]
[0,edge label=node[midway,right]N]
[$g(\bm p(3))>0.4$,edge label=node[midway,right]N
[$g(\bm p(3))>0.8$,edge label=node[midway,left]Y
[3,edge label=node[midway,left]Y]
[0,edge label=node[midway,right]N]
[$g(\bm p(2))>0.3$,edge label=node[midway,right]N
[2,edge label=node[midway,left]Y]
[0,edge label=node[midway,right]N]

A possible decision tree when the price information is incorporated for $N=3$. $g(\bm p(i))>a$ is equivalent to $\bm p(i)<g^{-1}(a)$, i.e., product $i$ is included in the assortment and its price is less than $g^{-1}(a)$.

It is not surprising that there are numerous link functions to choose from.
We give two examples below:

* $g(x) = e^{-x}$

* $g(x) = 1- \frac{2}{\pi}\arctan(x)$

In fact, the survival function of any non-negative random variables with positive PDF is a candidate for the link function.
This extra degree of freedom may concern some academics and practitioners:
How sensitive is the estimated random forest to the choice of link functions?
What criteria may be used to pick a “good” link function?
Our next result guarantees that the choice of link functions does not matter.
For any two link functions $g_1(x)$ and $g_2(x)$, we can run Algorithm <ref> for training data $\left\{(i_t,g_1(\bm p_t))\right\}_{t=1}^T$ and $\left\{(i_t,g_2(\bm p_t))\right\}_{t=1}^T$.
We use $t_b^{(j)}(\bm x)$ to denote the returned $b$th tree of the algorithm for link function $g_j(x)$, $j=1,2$.

If we equalize

* the choice of parameters in Step <ref> except for the link function

* the internal randomizers in Step <ref>, <ref>, and <ref>

in Algorithm <ref>, then the trees of both link functions return the same class label for an observation in the training data: $t_b^{(1)}(g_1(\bm p_t)) = t_b^{(2)}(g_2(\bm p_t)) $ for all $t=1,\dots,T$ and $b=1,\dots,B$.

It is worth pointing out that although the random forests using two link functions output identical class labels for $\bm p_t$ in the training data,
they may differ when predicting a new price vector $\bm p$.
This is because the splitting operation that minimizes the Gini index in Step <ref> is not unique.
Any split between two consecutive observations[If the algorithm splits on product $m$, then $\bm p_{t_1}$ and $\bm p_{t_2}$ are consecutive if there does not exist $\bm p_{t_3}$ in the same leaf node such that $(\bm p_{t_1}(m)-\bm p_{t_3}(m))(\bm p_{t_2}(m)-\bm p_{t_3}(m))<0$.] results in an identical class composition in the new leaves and thus the same Gini index.
Usually, the algorithm picks the middle between two consecutive observations to split, which may differ for different link functions.

§.§ Incorporating Customer Features

A growing trend in online retailing and e-commerce is personalization.
Due to the increasing access to personal information and computational power, retailers are able to implement personalized policies, including pricing and recommendation, for different customers based on his/her observed features.

Leveraging personal information can greatly increase the garnered revenue of the firm.

To offer a personalized assortment, the very first step is to incorporate the feature information into the choice model.
It has been considered in many classic DCMs by including a term that is linear in the features; see <cit.> for a general treatment.

In this section, we demonstrate that it is natural for random forests to capture customer features and return a binary choice forest that is aware of such information.
Suppose the collected data of the firm have the form $(i_t, \bm x_t, \bm f_t)$ for customer $t$, where in addition to $(i_t, \bm x_t)$, the choice made and the offered set, the customer feature $\bm f_t\in [0,1]^M$ is also recorded (possibly normalized).
The procedure in Section <ref> can be extended naturally.
In particular, we may append $\bm f_t$ to $\bm x_t$, so that the predictor $(\bm x,\bm f)\in [0,1]^{M+N}$.
Algorithm <ref> can be modified accordingly.

The resulting binary choice forest consists of $B$ binary choice trees.
The splits of the binary choice tree now encode not only whether a product is offered, but also predictive feature information of the customer.
For example, a possible binary choice tree illustrated in Figure <ref> may result from the algorithm.

for tree=l sep+=.5cm,s sep+=.2cm,shape=rectangle, rounded corners,
draw, align=center,
top color=white, bottom color=gray!20
[Has product 1
[Has product 3, edge label=node[midway,left]Y
[Choose 3,edge label=node[midway,left]Y]
[Choose 1,edge label=node[midway,right]N]
[Age $\ge 30$,edge=dashed, edge label=node[midway,right]N
[Married,edge=dashed,edge label=node[midway,left]Y
[Choose 4,edge=dashed,edge label=node[midway,left]Y]
[Choose 2,edge label=node[midway,right]N]
[No purchase, edge label=node[midway,right]N]

A possible binary choice tree after incorporating customer features.

Compared with other DCMs with linear features,
the framework introduced in this paper has the following benefits:
(1) The estimation is straightforward (same as the algorithm without customer features) and can be implemented efficiently.
(2) The nonparametric nature of the model allows capturing complex interaction between products and customer features, and among customer features. For example, “offering a high-end handbag” may become a strong predictor when the combination of features “female” and “age$\ge 30$” are activated.
In a binary choice tree, the effect is captured by three splits (one for the product and two for the customer features) along a branch.
It is almost impossible to capture in a parametric (linear) model.
(3) The framework can be combined with the aforementioned adjustments, such as pricing and product importance. For example, the measure MDI introduced in Section <ref> can be used to identify predictive customer features.

§ NUMERICAL EXPERIMENTS

In this section, we conduct a comprehensive numerical study based on both synthetic and real datasets.
We find that (1) random forests are quite robust and the performance does not vary much for underlying DCMs with different levels of complexity. In particular, random forests only underperform the correctly specified parametric models by a small margin and do not overfit;
(2) the standard error of random forests are small compared to other estimation procedures;
(3) random forests benefit tremendously from increasing sample size compared to other DCMs;
(4) the computation time of random forests almost does not scale with the size of the training data;
(5) random forests have a robust performance even if the training set only includes less than $1/30$ of all available assortments;
(6) random forests handle training data with nonstandard format reasonably well, such as aggregated data and price information (see Section <ref> and <ref> for more details) which cannot be handled easily by other frameworks.

We compare the estimation results of random forests with the MNL model <cit.> and the Markov chain model <cit.>[The MNL model is estimated using the maximum likelihood estimator. The Markov chain model is estimated using the EM algorithm, the same as the implementation in <cit.>. The random forest is estimated using the Python package “scikit-learn”.] for both synthetic and real datasets.
We choose the MNL and the Markov Chain models as benchmarks because the MNL model is one of the most widely used DCM and
the Markov chain model has been shown <cit.> to have an outstanding empirical performance compared to MNL, the nested logit, the mixed logit, and rank-based DCM.
Notice that the actual DCM generating the training data is not necessarily one of the three models mentioned above.

When conducting numerical experiments, we set the hyper-parameters of the random forest as follows: $B=1000$, $z=T$, $m=\sqrt{N}$, $l=50$.
The investigation of the sensitivity to hyper-parameters is shown in Appendix <ref>.
Choosing the hyper-parameters optimally using cross validation would further improve the performance of random forests.

§.§ Real Data: IRI Academic Dataset

In this section, we compare different models on the IRI Academic Dataset <cit.>.
The IRI Academic Dataset collects weekly transaction data from 47 U.S. markets from 2001 to 2012,
covering more than 30 product categories.
Each transaction includes the week and the store of purchase, the universal product code (UPC) of the purchased item, number of units purchased and total paid dollars.

The preprocessing follows the same steps as in <cit.> and <cit.>.
In particular, we regard the products sharing the same vendor code as the same product.
Each assortment is defined as the unique combination of stores and weeks. Such an assortment includes all the products that are available in the store during that week.
We conduct the analysis for 31 categories separately using the data for the first two weeks in 2007.
We only focus on the top nine purchased products from all stores during the two weeks in each category and treat all other products as the no-purchase alternative.

Unfortunately, sales data for most categories are too large for the EM algorithm to estimate the Markov chain model. For example, carbonated beverages, milk, soup and yogurt have more than 10 million transactions.
For computational efficiency, we uniformly sample 1/200 of the original data size without replacement.
This does not significantly increase the sampling variability as most transactions in the original data are repeated entries.

To compare different estimation procedures, we use five-fold cross validation to examine the out-of-sample performance.

We follow <cit.> and evaluate the empirical root mean squared error (RMSE) in the validation set.
That is, for estimated choice probabilities $\hat\PR$ and validation set $\Tscr$, we define

\begin{equation}
\label{RMSE_realdata}
R M S E\left(\hat\PR, \Tscr\right)=\sqrt{\frac{\sum_{(i,S) \in \Tscr} \sum_{j \in S \cup\{0\}}\left(\I{j=i}-\hat\PR(j , S)\right)^{2}}{\sum_{(i,S) \in \Tscr}(|S|+1)}}.
\end{equation}

The result is shown in Table <ref> comparing random forests to MNL and the Markov chain model. Random forests outperform the other two in 24 of 31 categories, especially for large data sizes.
According to <cit.>, the Markov chain choice model has already been shown to have a strong performance in synthetic and real-world studies.
Table <ref> fully demonstrates the potential of random forests as a framework to model and estimate consumer behavior in practice.
For robustness, we also test the result when considering the top five/fifteen products instead of nine.
The results are shown in Tables <ref> and <ref> in Appendix <ref>.
Random forests perform the best among the three models in 25 and 27 out of 31 categories, respectively.

Product category     #Data     #Unique assort    #Avg prod     RF     MNL     MC Beer     10,440     29     5.66     0.2717 (0.0006)     0.2722 (0.0009)     0.2721 (0.0008) Blades     1,085     36     4.83     0.3106 (0.0041)     0.3092 (0.0039)     0.3096 (0.0040) Carbonated Beverages     71,114     24     5.42      0.3279 (0.0004)     0.3299 (0.0005)     0.3295 (0.0005) Cigarettes     6,760     48     5.73     0.2620 (0.0031)     0.2626 (0.0034)     0.2626 (0.0034) Coffee     8,135     46     6.26     0.2904 (0.0011)     0.2934 (0.0010)     0.2925 (0.0011) Cold Cereal     30,369     15     6.80     0.2785 (0.0004)     0.2788 (0.0003)     0.2787 (0.0003) Deodorant     2,775     20     6.75     0.2827 (0.0005)     0.2826 (0.0006)     0.2826 (0.0006) Diapers     1,528     13     3.85     0.3581 (0.0027)     0.3583 (0.0023)     0.3583 (0.0025) Facial Tissue     8,956     22     4.09     0.3334 (0.0007)     0.3379 (0.0011)     0.3375 (0.0008) Frozen Dinners/Entrees     48,349     35     6.46     0.2733 (0.0004)     0.2757 (0.0003)     0.2750 (0.0003) Frozen Pizza     16,263     50     5.32     0.3183 (0.0002)     0.3226 (0.0001)     0.3210 (0.0001) Household Cleaners     6,403     18     6.67     0.2799 (0.0011)     0.2798 (0.0010)     0.2798 (0.0010) Hotdogs     7,281     66     5.06     0.3122 (0.0012)     0.3183 (0.0006)     0.3170 (0.0008) Laundry Detergent     7,854     51     6.14     0.2738 (0.0018)     0.2875 (0.0019)     0.2853 (0.0018) Margarine/Butter     9,534     15     6.60     0.2985 (0.0005)     0.2995 (0.0004)     0.2990 (0.0004) Mayonnaise     4,380     38     5.08     0.3212 (0.0027)     0.3242 (0.0011)     0.3230 (0.0007) Milk     56,849     32     4.72     0.2467 (0.0007)     0.2501 (0.0005)     0.2538 (0.0013) Mustard     5,354     42     6.21     0.2844 (0.0009)     0.2856 (0.0006)     0.2852 (0.0006) Paper Towels     9,520     34     5.71     0.2939 (0.0011)     0.2964 (0.0009)     0.2959 (0.0009) Peanut Butter     4,985     31     4.97     0.3113 (0.0019)     0.3160 (0.0006)     0.3146 (0.0011) Photography supplies     189     30     3.63     0.3456 (0.0090)     0.3399 (0.0090)     0.3456 (0.0098) Razors     111     10     2.60     0.3269 (0.0334)     0.3294 (0.0251)     0.3323 (0.0218) Salt Snacks     44,975     28     5.50     0.2830 (0.0006)     0.2844 (0.0007)     0.2840 (0.0007) Shampoo     3,354     25     6.68     0.2859 (0.0007)     0.2855 (0.0008)     0.2856 (0.0008) Soup     68,049     23     6.96     0.2709 (0.0006)     0.2738 (0.0007)     0.2729 (0.0007) Spaghetti/Italian Sauce     12,377     32     5.88     0.2901 (0.0004)     0.2919 (0.0007)     0.2914 (0.0006) Sugar Substitutes     1,269     40     5.35     0.3092 (0.0047)     0.3085 (0.0047)     0.3085 (0.0047) Toilet Tissue     11,154     23     5.65     0.3084 (0.0006)     0.3126 (0.0004)     0.3132 (0.0016) Toothbrushes     2,562     45     6.04     0.2860 (0.0010)     0.2859 (0.0004)     0.2858 (0.0006) Toothpaste     4,258     33     6.00     0.2704 (0.0009)     0.2708 (0.0012)     0.2708 (0.0012) Yogurt     61,671     42     5.19     0.2924 (0.0013)     0.2976 (0.0009)     0.2960 (0.0009)
The summary statistics (the data size, the number of unique assortments in the data, and the average number of products in an assortment) of the IRI dataset after preprocessing and the average and standard deviation of the out-of-sample RMSE (<ref>) for each category when considering the top 9 products.

§.§ Real Data: Hotel

In this section, we apply the random forest algorithm to a public dataset <cit.>.

The dataset includes transient customers (mostly business travelers) who stayed in one of five continental U.S. hotels between March 12, 2007, and April 15, 2007.
The minimum booking horizon for each check-in date is four weeks.
Rate and room type availability and reservation information are collected via the hotel and/or customer relationship officers (CROs), the hotel’s websites, and offline travel agencies.
Since there is no direct competition among these five hotels, we process the data separately.
A product is uniquely defined by the room type (e.g., suite).
For each transaction, the purchased room type and the assortment offered are recorded.

When processing the dataset, we remove the products that have less than 10 transactions.
We also remove the transactions whose offered assortments are not available due to technical reasons.
For the transactions that none of the products in the available sets are purchased by the customer, we assume customers choose the no-purchase alternative.

We use five-fold cross-validation and RMSE defined in (<ref>) to examine the out-of-sample performance.
In Table <ref> we show the summary statistics of the five datasets after preprocessing.
We also show the out-of-sample RMSE for each hotel (average and standard deviation).
In addition, we show the performance of the independent demand model (ID), which does not incorporate the substitution effect and is expected to perform poorly, in order to provide a lower bound of the performance.

We find that the random forest algorithm outperforms the parametric methods for large datasets (Hotel 1, 2 and 3).
For smaller data sizes (Hotel 4 and 5), the random forest is on par with the best parametric estimation procedure (Markov chain) according to <cit.>.

#Prod     #In-sample     #Out-sample     #Unique assort     #Avg prod

Hotel 1     10     1271     318     50     5.94

Hotel 2     6     347     87     26     3.27

Hotel 3     7     1073     268     25     4.32

Hotel 4     4     240     60     12     2.33

Hotel 5     6     215     54     21     3.52

RF     MNL     MC     ID

Hotel 1     0.3040 (0.0046)     0.3098 (0.0031)     0.3047 (0.0039)     0.3224 (0.0043)

Hotel 2     0.3034 (0.0120)     0.3120 (0.0148)     0.3101 (0.0124)     0.3135 (0.0178)

Hotel 3     0.2842 (0.0051)     0.2854 (0.0065)     0.2842 (0.0064)     0.2971 (0.0035)

Hotel 4     0.3484 (0.0129)     0.3458 (0.0134)     0.3471 (0.0125)     0.3584 (0.0047)

Hotel 5     0.3219 (0.0041)     0.3222 (0.0069)     0.3203 (0.0046)     0.3259 (0.0058)

The summary statistics (the total number of products, the data size for in-sample and out-of-sample tests, the number of unique assortments in the data, and the average number of products in an assortment) of the five hotel datasets and the average and standard deviation of the out-of-sample RMSE across five folds.

§.§ Generalizability to Unseen Assortments

One of the major challenges in the estimation of the DCM, compared to other statistical estimation problems, is the limited coverage of the training data.
In particular, the seller tends to offer a few assortments that they believe are profitable.
As a result, in the training data $\{\bm x_t\}_{t=1}^T$ only makes up a small fraction of the total $2^N$ available assortments.
Any estimation procedure needs to address the following issue: can the DCM estimated from a few assortments generalize to the assortments that have never been offered in the training data?

While the theoretical foundation has been studied in Section <ref>,
we show the numerical performance in this section.

Consider $N=10$ products.
We randomly choose $T_1$ assortments to offer in the training set and thus there are $T/T_1$ transactions for each assortment on average.

We use the rank-based DCM to generate the data with $k=4$ and 10 customer types.
The rank-based DCM is shown to be equivalent to RUM <cit.>.
Consumers are divided into $4$ or $10$ different types, each with a random preference permutation of all the products and the no-purchase alternative (see, e.g., ).

We randomly generate the fractions of customer types as follows:
draw uniform random variables $u_i$ between zero and one for $i=1,...,k$, and then set $\frac{u_i}{\sum_{j=1}^k u_j}$ to be the proportion of type $i$, $i=1,...,k$.

The performance is evaluated by the root mean squared error (RMSE), which is also used in <cit.>:

\begin{equation}
\label{RMSE_soft}
R M S E\left(\PR, \hat\PR\right)=\sqrt{\frac{\sum_{S \subseteq [N]} \sum_{j \in S \cup\{0\}}\left(\PR(j , S)-\hat\PR(j , S)\right)^{2}}{\sum_{S \subseteq [N]}(|S|+1)}},
\end{equation}

where $\PR$ denotes the actual choice probability and $\hat\PR$ denotes the estimated choice probability.
The RMSE tests all the assortments and there is no need to generate a test set.
For each setting, we generate 100 independent training datasets and compute the average and standard deviation of the RMSEs.

The results are shown in Tables <ref> and <ref>.

Notice that there are $2^N-1=1023$ possible available assortments.
Therefore, for example, $T_1=30$ implies that less than $1/30$ of the total assortments have been offered in the training data.

In general, the random forest outperforms the MNL model and is on par with the Markov chain DCM when $T$ is large.
For small sample sizes, the Markov chain model performs better.
It is likely due to the similarity between the rank-based model and the Markov chain model, e.g., both are regular choice models (definition in Section <ref>).
As we shall see, when the underlying model is irregular, the random forest tends to have the best performance (see Table <ref>).

Moreover, in the real datasets, when the underlying model is unknown and likely to be irregular, the random forest performs better than the Markov chain model (see Table <ref>).

$T$              3c$T_1 = 30$          3c$T_1 = 100$          3c$T_1 = 300$
3-5 7-9 11-13
RF          MNL         MC               RF           MNL         MC               RF           MNL         MC
$ 300$            0.103       0.117       0.077            0.094        0.113       0.065            0.092        0.111       0.062

(0.014)     (0.016)     (0.021)          (0.011)      (0.016)     (0.017)          (0.011)      (0.014)     (0.015)

$ 3000$           0.090       0.114       0.063            0.060        0.109       0.048            0.050        0.108       0.044

(0.016)     (0.017)     (0.024)          (0.009)      (0.015)     (0.017)          (0.007)      (0.015)     (0.017)

$ 20000$          0.084       0.110       0.063            0.053        0.107       0.048            0.038        0.108       0.043

(0.019)     (0.022)     (0.025)          (0.011)      (0.019)     (0.017)          (0.005)      (0.016)     (0.017)

The average RMSE and the standard deviation for random forests, MNL and the Markov chain model when the training data is generated by the rank-based model with 4 rankings.

$T$              3c$T_1 = 30$          3c$T_1 = 100$          3c$T_1 = 300$
3-5 7-9 11-13
RF          MNL         MC               RF           MNL         MC               RF           MNL         MC
$ 300$            0.084       0.080       0.073            0.079        0.079       0.067            0.077        0.079       0.064

(0.009)     (0.009)     (0.012)          (0.009)      (0.008)     (0.010)          (0.009)      (0.008)     (0.009)

$ 3000$           0.071       0.077       0.050            0.054        0.074       0.043            0.048        0.074       0.041

(0.009)     (0.009)     (0.009)          (0.006)      (0.008)     (0.007)          (0.004)      (0.008)     (0.006)

$ 20000$          0.067       0.075       0.047            0.046        0.074       0.039            0.039        0.072       0.038

(0.009)     (0.010)     (0.009)          (0.005)      (0.007)     (0.005)          (0.003)      (0.008)     (0.005)

The average RMSE and the standard deviation for random forests, MNL and the Markov chain model when the training data is generated by the rank-based model with 10 rankings.

We run our algorithm on a server with 2.50GHz dual-core Inter Xeon CPU E5-2680 and 256GB memory.
The running time is shown in Table <ref>.
In terms of computation time, the random forest is the most efficient, while the EM algorithm used to estimate the Markov chain model takes much longer.
When $T = 20000$, the random forest spends 1/160 of the computation time of the Markov chain model.
Notice that the running time of random forests only increases slightly for large training sets.

$T$     RF     MNL     MC

$300$     1.4s     0.3s     14.5s

$3000$     1.9s     3.2s     120.9s

$20000$     5.1s     22.6s     819.9s

The average running time of random forests, MNL and the Markov chain Model.

§.§ Behavioral Choice Models

When the DCM is outside the scope of RUM and the regularity is violated, the Markov chain and MNL model may fail to specify the choice behavior correctly.
In this section, we generate choice data using the

comparison-based DCM <cit.>, described below.
Consumers implicitly score various attributes of the products in the assortment.
Then they undergo an internal round-robin tournament of all the products.
When comparing two products from the assortment, the customer checks their attributes and counts the number of preferable attributes of both products.

Eventually, the customer count the total number of “wins” in the pairwise comparisons.

Here we assume that customers choose with equal probability if there is a tie.

In the experiment, we consider $N = 10$ products.
Consumers are divided into $k=2$ different types, whose proportions are randomly generated between 0 and 1.
Each type assigns uniform random variables between 0 and 1 to the five attributes of all the products (including the no-purchase option).

Again we use the RMSE in (<ref>) to compare the predictive accuracy.
Like in the previous experiment, each setting is simulated 100 times. The result is shown in Table <ref>.

$T$              3c$T_1 = 30$          3c$T_1 = 100$          3c$T_1 = 300$
3-5 7-9 11-13
RF          MNL         MC               RF           MNL         MC               RF           MNL         MC
$ 300$            0.153       0.164       0.149            0.140        0.155       0.128            0.139        0.153       0.125

(0.029)     (0.030)     (0.035)          (0.024)      (0.029)     (0.033)          (0.023)      (0.028)     (0.032)
$ 3000$           0.141       0.158       0.142            0.099        0.147       0.121            0.084        0.145       0.116

(0.034)     (0.041)     (0.045)          (0.023)      (0.037)     (0.038)          (0.020)      (0.037)     (0.038)
$ 20000$          0.135       0.154       0.135            0.098        0.145       0.124            0.063        0.138       0.109

(0.032)     (0.032)     (0.034)          (0.023)      (0.030)     (0.033)          (0.017)      (0.037)     (0.037)

The average RMSE and the standard deviation using random forests, MNL and the Markov chain Model under the comparison-based DCM with different number of observed assortments in the training data ($T_1$).

Because of the irregularity, both the MNL and the Markov chain DCM are outperformed by the random forest, especially when the data size increases.
Notice that as $T\to\infty$, the random forest is able to achieve diminishing RMSE, while the other two models do not improve because of the misspecification error.
Like the previous experiment, the random forest achieves stable performances with small standard deviations.

§.§ Aggregated Choice Data

In this section, we investigate the performance of random forests when the training data is aggregated as in Section <ref>.
To generate the aggregated training data, we first generate $T$ observations using the MNL model for $N=10$ products.
The utility of each product and the outside option is generated uniformly between 0 and 1.

Then, we let $a$ be the aggregation level, i.e., we aggregate $a$ data points together.
For example, $a = 1$ is equivalent to the original unaggregated data.
For $a=5$, Table <ref> illustrates five observations in the original dataset for $N=5$.
Upon aggregation, the five transactions are replaced by five new observations with $\bm x_t \equiv [0.6,0.4,0.8,0.4,0.6]$ and $i_t=1,0,4,3,1$ for $t=1,2,3,4,5$.

Product 1     Product 2     Product 3     Product 4     Product 5    Choices

1     1     1     1     1     1

0     1     0     0     1     0

1     0     1     1     1     4

0     0     1     0     0     3

1     0     1     0     0     1

Five observations in the unaggregated original data. Upon aggregation, they are replaced by five new observations with $\bm x_t \equiv [0.6,0.4,0.8,0.4,0.6]$ and $i_t=1,0,4,3,1$ for $t=1,2,3,4,5$.

We test the performance of different aggregate levels $a \in \{1,5,10,20,50\}$ when $T = 5000$.
The performance is measured in RMSE (<ref>).
Note that other DCMs cannot handle the situation naturally.
To apply the benchmarks, we “de-aggregate” the data by randomly generating $a$ assortments, each of which includes product $j$ with probability 1-$\bm p_s(j) \in [0,1]$ independently.
Then we estimate the parameters for MNL and the Markov chain model from the unaggregated data.

We simulate 100 instances for each setting to evaluate the average and standard deviation, shown in Table <ref>.

Aggregate levels     RF     MNL     MC

$a = 1$      0.038 (0.002)     0.007 (0.002)     0.020 (0.001)

$a = 5$      0.045 (0.005)     0.048 (0.007)     0.052 (0.006)

$a =10$     0.051 (0.010)     0.057 (0.008)     0.060 (0.007)

$a =20$     0.054 (0.009)     0.062 (0.008)     0.065 (0.007)

$a =50$     0.060 (0.010)     0.065 (0.009)     0.067 (0.008)

The performance of random forests and two other benchmarks for different aggregate levels.

From the results, MNL and the Markov chain model perform well for the original data ($a=1$).
However, after aggregation, random forests outperform the other two even when the underlying model is indeed MNL.
It showcases the strength of random forests for this type of data.

§.§ Incorporating Pricing Information

In this section, we test the performance of random forests when the price information is incorporated.
We use the MNL model to generate the choice data. Let $\bm u$ denote the expected utility of the products and $\bm p$ their prices. Therefore, for given assortment $S$, the choice probabilities of product $i \in S$ and the no-purchase option are:

\begin{equation}
\label{eq:MNL choice probability}
p(i, S) = \frac{\exp(u_i-p_i)}{1+\sum_{j \in S} \exp(u_j-p_j)},\quad p(0, S) = \frac{1}{1+\sum_{j \in S} \exp(u_j-p_j)}.
\end{equation}

Consider $N=10$ products.
We generate $u_i$ as uniform random variables between 0 and 5 for each product.

Then we generate a price uniformly on $[0,5]$ for each product.
Note that in this experiment, all products are available in an assortment.

As explained in Section <ref>, we use the link function $g(x) = \exp(-x)$.
The customer's choice then follows the choice probability (<ref>).
The RMSE in (<ref>) is no longer applicable because the assortments and prices cannot be exhausted.
To evaluate the performance, we randomly generate $1000$ assortments and prices according to the same distribution as the training data.
Then we evaluate the empirical RMSE in the test data.

In addition to the MNL model, we also use the linear demand as a benchmark.
Under the linear demand, a customer purchases product $i$ with probability
$p(i,\bm p)=(a_i + \sum_{j\in N} b_{ij} p_j)^+$ for some coefficients $a_i$ and $b_{ij}$.
The no-purchase probability is thus $1-\sum_{i=1}^N p(i, \bm p)$.
We estimate the coefficients using linear regression.
Note that linear demand is very popular in modeling demand for multiple products with price information.

We investigate the performance of random forests and the two benchmarks for different sizes of training data $T \in \{300,1500,5000\}$.

$T$        RF      MNL     Linear

300       0.075 (0.004)       0.020 (0.005)       0.064 (0.004)

1500     0.050 (0.002)       0.009 (0.002)       0.053 (0.003)

5000     0.039 (0.002)       0.005 (0.001)       0.050 (0.003)

The RMSE of random forests, MNL and linear demand with price information when the underlying model is MNL.

From Table <ref>, it is not surprising that MNL has the best performance, because the data is generated by the MNL model.
However, when $T=1500$ and 5000, random forests are able to outperform the linear model, which is believed to be fairly robust and used widely.
We believe it is due to the model misspecification of the linear model. It further demonstrates the benefit of random forests.

§ CONCLUDING REMARKS

This paper demonstrates some theoretical and practical benefits of using random forests to estimate discrete choice models.
It opens up a series of exciting new research questions:

* What type of DCMs can be estimated well by random forests and have higher generalizability to unseen assortments?

* As we use the choice forest to approximate DCMs, how can we translate the properties of a DCM to the topological structure of decision trees?

* Can we provide finite-sample error bounds for the performance of random forests, with or without the price information?

* What properties does the product importance index MDI have?

* Given a binary choice forest, possibly estimated by random forests, can we compute the optimal assortment and prices efficiently?

We hope to address some of these questions in future research.

§ PROOFS

It is easy to see that a BCF is a DCM.
To show the converse, we first show that DCMs are closed under a convex combination.
Consider a collection of DCMs $p_c(i,S)$ $c \in C$. Let $\alpha_c \geq 0$ with $\sum_{c \in C} \alpha_c = 1$, Then $p(i,S) = \sum_{c \in C}\alpha_c p_c(i,S)$ is clearly a DCM, so a convex combination of DCM is a DCM and thus all DCMs form a convex set.

Consider the extreme points, i.e., DCMs that cannot be written as a non-trivial convex combination of two or more DCMs.
Let $E$ be the collection of all extreme DCMs, $p_e(i,S), e \in E$.
Then any DCM is in the convex hull of $p_e, e \in E$.
A deterministic DCM is a DCM such that $p(i,S)\in \{0,1\}$ for every $i \in S\cup \{0\}$ and every $S \subset N$.
Next, we show that a DCM is an extreme point if and only if it is deterministic.
It is clear that deterministic DCMs are extreme points.
Conversely, for an extreme DCM, if it is not deterministic, then we can always split the probability between 0 and 1 and makes it a convex combination of two different DCMs.
Therefore, extreme points are equivalent to deterministic DCMs.

Next, we show that all deterministic DCMs can be represented as a BCF.
This follows directly because every deterministic DCM is a binary choice tree and can be explicitly constructed.
This proves that any DCM can be represented as a BCF.

To calculate the number of extreme points,
recall that Carathéodory's theorem states that if a point $x$ of $\R^d$ lies in the convex hull of a set $P$, then $x$ can be written as the convex combination of at most $d + 1$ points in $P$.
To apply Carathéodory's theorem to DCMs, we may flatten a DCM $p(i, \bm x)$ to a vector by concatenating the choice probabilities  of all possible assortments.
Because the choice probability of an assortment of size $k$ can be represented by a vector of dimension $k$
and there are $\binom{N}{k}$ assortments of size $k$,
the length of the concatenated vector is of length
$\sum_{k=1}^N k\binom{N}{k}=\sum_{k=1}^N k \cdot \frac{N!}{k!(N-k)!}=N\cdot\sum_{k=1}^N \frac{(N-1)!}{(k-1)!(N-k)!}=N\cdot 2^{N-1}$.
Therefore, Every DCM can be represented as a convex combination of a BCF containing at most $N\cdot 2^{N-1}+1$ binary choice trees.

We first prove that for a single decision tree, there is a high probability that the number of observations chosen in Step <ref> in which $\bm x$ is offered is large.
More precisely, let $X_t = \I{\bm x_t= \bm x}$. It is easy to see that $\sum_{t=1}^T X_t = k_T$.
Step <ref> randomly selects $z_T$ observations out of the $T$ with replacement.
Denote the bootstrap sample of $\left\{X_1,\dots,X_T\right\}$ by $\left\{Y_1,\dots,Y_{z_T}\right\}$.
By Hoeffding's inequality, we have the following concentration inequality

\begin{equation}\label{eq:sum-Yj-large}
\PR\left( \left|\frac{\sum_{j=1}^{z_T}Y_j}{z_T} - \frac{k_T}{T}\right|\le \epsilon\right)\le 2\exp\left( - 2z_T\epsilon^2\right)
\end{equation}

for any $\epsilon>0$.
In other words, the bootstrap sample in Step <ref> does not deviate too far from the population as long as $z_T$ is large.
As we choose $\epsilon<\lim_{T\to\infty}k_T/T$, it implies that $\sum_{j=1}^{z_T}Y_j\to\infty$ and in particular

\begin{equation}\label{eq:greater-than-lT}
\lim_{T\to\infty}\PR(\sum_{j=1}^{z_T}Y_j>l_T) = 1.
\end{equation}

Next we show that given $\sum_{j=1}^{z_T}Y_j>l_T$ for a decision tree, the leaf node that contains $\bm x$ only contains observations with $Y_j=1$.
That is, the terminal leaf containing $\bm x$ is a single corner of the unit hypercube.
If the terminal leaf node containing an observation with predictor $\bm x$, then it has no less than $\sum_{j=1}^{z_T}Y_j$ observations, because all the $\sum_{j=1}^{z_T}Y_j$ samples used to train the tree fall on the same corner in the predictor space.
If another observation with a different predictor is in the same leaf node, then it contradicts
Step <ref> in the algorithm, because it would imply that another split could be performed.
Suppose $\left\{R_1,\dots,R_M\right\}$ is the final partition corresponding to the decision tree.
As a result, in the region $R_j$ such that $\bm x\in R_j$, we must have that $t_b(\bm x)$ is a random sample from the $\sum_{j=1}^{z_T}Y_j$ customer choices, according to Step <ref>.

Now consider the estimated choice probability of a given assortment $\bm x$ from the random forest: $\sum_{b=1}^{B_T} \frac{1}{B_T}\I{t_b(\bm x)=i}$.
Notice that $t_b(\bm x)$, $b=1,\dots,B_T$, are IID given the training set.
By Hoeffding's inequality, conditional on $\left\{(i_t,\bm x_t)\right\}_{t=1}^T$,

\begin{equation}\label{eq:hoeffding1}
\PR\left(\left|\sum_{b=1}^{B_T} \frac{1}{B_T}\I{t_b(\bm x)=i}-\PR(t_b(\bm x)=i|\left\{(i_t,\bm x_t)\right\}_{t=1}^T)\right|>\epsilon_1\bigg|\left\{(i_t,\bm x_t)\right\}_{t=1}^T\right)\le 2e^{-2B_T\epsilon_1^2},
\end{equation}

for all $\epsilon_1>0$.
Next we analyze the probability $\PR(t_b(\bm x)=i|\left\{(i_t,\bm x_t)\right\}_{t=1}^T)$ for a single decision tree.
By the previous paragraph, conditional on $\sum_{j=1}^{z_T}Y_j>l_T$, the output of a single tree $t_b(\bm x)$ is randomly chosen from the class labels of $\sum_{j=1}^{z_T}Y_j$ observations whose predictor is $\bm x$.
Let $Z_j$ be the class label of the $j$th bootstrap sample $Y_j$
in Step <ref>.
Therefore, conditional on the event $\sum_{j=1}^{z_T}Y_j>l_T$ and the training data, we have

\begin{equation}\label{eq:iid-tree}
\PR(t_b(\bm x)=i|\left\{(i_t,\bm x_t)\right\}_{t=1}^T,\sum_{j=1}^{z_T}Y_j>l_T) = \sum_{j=1}^{z_T} \frac{Y_j\I{Z_j=i}}{\sum_{j=1}^{z_T} Y_j}.
\end{equation}

Because $\{Y_j\I{Z_j=i}\}_{j=1}^{z_T}$ is a bootstrap sample, having IID distribution

\begin{equation*}
\PR(Y_j\I{Z_j=i}=1) = \frac{\sum_{t=1}^T\I{i_t=i,\bm x_t=\bm x}}{T}
\end{equation*}

given the training data, we apply Hoeffding's inequality again

\begin{equation}\label{eq:hoeffding2}
\PR\left( \left| \frac{\sum_{j=1}^{z_T}Y_j\I{Z_j=i}}{z_T} - \frac{\sum_{t=1}^T\I{i_t=i,\bm x_t=\bm x}}{T}\right|>\epsilon_2\bigg|\left\{(i_t,\bm x_t)\right\}_{t=1}^T \right)\le 2\exp(-2z_T \epsilon_2^2)
\end{equation}

for all $\epsilon_2>0$.
Now applying Hoeffding's inequality to $\sum_{t=1}^T\I{i_t=i,\bm x_t=\bm x}$ again, and because of Assumption <ref>, we have that

\begin{align}\label{eq:hoeffding4}
\PR\left(\left| \frac{\sum_{t=1}^T\I{i_t=i,\bm x_t=\bm x}}{k_T}-p(i,\bm x)\right|> \epsilon_3\right)\le 2\exp(-2k_T\epsilon_3^2)
\end{align}

for all $\epsilon_3>0$.

With the above results, we can bound the target quantity

\begin{align*}
&\PR\left(\left|\sum_{b=1}^{B_T} \frac{1}{B_T}\I{t_b(\bm x)=i}-p(i,\bm x)\right|>\epsilon\right)\\
&= \E\left[\PR\left(\left|\sum_{b=1}^{B_T} \frac{1}{B_T}\I{t_b(\bm x)=i}-p(i,\bm x)\right|>\epsilon\bigg| \left\{(i_t,\bm x_t)\right\}_{t=1}^T\right)\right]\\
&\le \E\left[\PR\left(\left|\sum_{b=1}^{B_T} \frac{1}{B_T}\I{t_b(\bm x)=i}-\PR(t_b(\bm x)=i|\{(i_t,\bm x_t)\}_{t=1}^T)\right|>\epsilon/2\bigg| \{(i_t,\bm x_t)\}_{t=1}^T\right)\right]\\
&\quad +\E\left[\PR\left(\left|p(i,\bm x)-\PR(t_b(\bm x)=i|\{(i_t,\bm x_t)\}_{t=1}^T)\right|>\epsilon/2\bigg| \{(i_t,\bm x_t)\}_{t=1}^T\right)\right]
\end{align*}

By (<ref>), the first term is bounded by $2\exp(-B_T\epsilon^2/2)$ which converges to zero as $B_T\to\infty$.
To bound the second term, note that

\begin{align}\label{eq:second-term-split}
&\PR\left(\left|p(i,\bm x)-\PR(t_b(\bm x)=i|\{(i_t,\bm x_t)\}_{t=1}^T)\right|>\epsilon/2\bigg| \{(i_t,\bm x_t)\}_{t=1}^T\right)\notag\\
&\le \PR\left(\left|p(i,\bm x)- \frac{\sum_{t=1}^T\I{i_t=i,\bm x_t=\bm x}}{k_T}\right|>\epsilon/6\bigg| \{(i_t,\bm x_t)\}_{t=1}^T\right)\notag\\
&\quad+ \PR\left(\left|\frac{\sum_{t=1}^T\I{i_t=i,\bm x_t=\bm x}}{k_T}-\sum_{j=1}^{z_T} \frac{Y_j\I{Z_j=i}}{\sum_{j=1}^{z_T} Y_j}\right|>\epsilon/6\bigg| \{(i_t,\bm x_t)\}_{t=1}^T\right)\notag\\
&\quad + \PR\left(\left|\sum_{j=1}^{z_T} \frac{Y_j\I{Z_j=i}}{\sum_{j=1}^{z_T} Y_j}-\PR(t_b(\bm x)=i|\{(i_t,\bm x_t)\}_{t=1}^T)\right|>\epsilon/6\bigg| \{(i_t,\bm x_t)\}_{t=1}^T\right)
\end{align}

The expected value of the first term in (<ref>) is bounded by $2\exp(-k_T\epsilon^2/18)$ by (<ref>), which converges to zero as $k_T\to\infty$.
For the second term of (<ref>), we have that

\begin{align}
&\PR\left(\left|\frac{\sum_{t=1}^T\I{i_t=i,\bm x_t=\bm x}}{k_T}-\sum_{j=1}^{z_T} \frac{Y_j\I{Z_j=i}}{\sum_{j=1}^{z_T} Y_j}\right|>\epsilon/6\bigg| \{(i_t,\bm x_t)\}_{t=1}^T\right)\notag\\
%        &= \PR\left( \sum_{j=1}^{z_T}Y_j\le l_T\bigg|\{(i_t,\bm x_t)\}_{t=1}^T\right)\PR\left(\left|\frac{\sum_{t=1}^T\I{i_t=i,\bm x_t=\bm x}}{k_T}-\sum_{j=1}^{z_T} \frac{Y_j\I{Z_j=i}}{\sum_{j=1}^{z_T} Y_j}\right|>\epsilon/6\bigg| \{(i_t,\bm x_t)\}_{t=1}^T, \sum_{j=1}^{z_T}Y_j\le l_T\right) \notag\\
%        &\quad + \PR\left( \sum_{j=1}^{z_T}Y_j> l_T\bigg|\{(i_t,\bm x_t)\}_{t=1}^T\right)\PR\left(\left|\frac{\sum_{t=1}^T\I{i_t=i,\bm x_t=\bm x}}{k_T}-\sum_{j=1}^{z_T} \frac{Y_j\I{Z_j=i}}{\sum_{j=1}^{z_T} Y_j}\right|>\epsilon/6\bigg| \{(i_t,\bm x_t)\}_{t=1}^T, \sum_{j=1}^{z_T}Y_j> l_T\right)\notag \\
%        &\le \PR\left( \sum_{j=1}^{z_T}Y_j\le l_T\bigg|\{(i_t,\bm x_t)\}_{t=1}^T\right)\notag \\
&\le \PR\left(\left|\frac{\sum_{t=1}^T\I{i_t=i,\bm x_t=\bm x}}{k_T}-\sum_{j=1}^{z_T} \frac{TY_j\I{Z_j=i}}{z_Tk_T}\right|>\epsilon/12\bigg| \{(i_t,\bm x_t)\}_{t=1}^T\right)\notag\\
&\quad + \PR\left(\left|\sum_{j=1}^{z_T} \frac{TY_j\I{Z_j=i}}{z_Tk_T}-\sum_{j=1}^{z_T} \frac{Y_j\I{Z_j=i}}{\sum_{j=1}^{z_T} Y_j}\right|>\epsilon/12\bigg| \{(i_t,\bm x_t)\}_{t=1}^T\right)\label{eq:term2of8}
%        &\quad + \PR\left(\left|\frac{\sum_{t=1}^T\I{i_t=i,\bm x_t=\bm x}}{k_T}-\sum_{j=1}^{z_T} \frac{Y_j\I{Z_j=i}}{\sum_{j=1}^{z_T} Y_j}\right|>\epsilon/6\bigg| \{(i_t,\bm x_t)\}_{t=1}^T, \sum_{j=1}^{z_T}Y_j> l_T\right)\\
%        &\le \PR\left( \sum_{j=1}^{z_T}Y_j\le l_T\right) + \PR\left(\left|\frac{\sum_{t=1}^T\I{i_t=i,\bm x_t=\bm x}}{k_T}-\sum_{j=1}^{z_T} \frac{TY_j\I{Z_j=i}}{z_Tk_T}\right|>\epsilon/12\bigg| \{(i_t,\bm x_t)\}_{t=1}^T, \sum_{j=1}^{z_T}Y_j> l_T\right)\\
\end{align}

For the first term in (<ref>), note that by (<ref>)

\begin{align*}
&\PR\left(\left|\frac{\sum_{t=1}^T\I{i_t=i,\bm x_t=\bm x}}{k_T}-\sum_{j=1}^{z_T} \frac{TY_j\I{Z_j=i}}{z_Tk_T}\right|>\epsilon/12\bigg| \{(i_t,\bm x_t)\}_{t=1}^T\right)\\
&=\PR\left(\left|\frac{\sum_{t=1}^T\I{i_t=i,\bm x_t=\bm x}}{T}-\sum_{j=1}^{z_T} \frac{Y_j\I{Z_j=i}}{z_T}\right|>k_T\epsilon/12\bigg| \{(i_t,\bm x_t)\}_{t=1}^T\right)\le 2\exp(- z_Tk_T^2\epsilon^2/72)\to 0
\end{align*}

as $T\to\infty$.
For the second term in (<ref>), we have

\begin{align*}
&\PR\left(\left|\sum_{j=1}^{z_T} \frac{TY_j\I{Z_j=i}}{z_Tk_T}-\sum_{j=1}^{z_T} \frac{Y_j\I{Z_j=i}}{\sum_{j=1}^{z_T} Y_j}\right|>\epsilon/12\bigg| \{(i_t,\bm x_t)\}_{t=1}^T\right)\\
&\le\PR\left(\frac{\sum_{j=1}^{z_T}Y_j\I{Z_j=i}}{z_T}\left| \frac{T}{k_T}-\frac{z_T}{\sum_{j=1}^{z_T} Y_j}\right|>\epsilon/12\bigg| \{(i_t,\bm x_t)\}_{t=1}^T\right)\\
&\le\PR\left(\left| \frac{T}{k_T}-\frac{z_T}{\sum_{j=1}^{z_T} Y_j}\right|>\epsilon/12\bigg| \{(i_t,\bm x_t)\}_{t=1}^T\right)\\
&= \PR\left( \frac{Tz_T}{k_T\sum_{j=1}^{z_T} Y_j}\left| \frac{k_T}{T}-\frac{\sum_{j=1}^{z_T} Y_j}{z_T}\right|>\epsilon/12\bigg| \{(i_t,\bm x_t)\}_{t=1}^T\right)
\end{align*}

It is easy to see that $\frac{Tz_T}{k_T\sum_{j=1}^{z_T} Y_j}$ converges almost surely to a constant as $T\to\infty$.
Therefore, by (<ref>) the last term converges to zero.
Finally, we move on to the third term of (<ref>).
By (<ref>), we have

\begin{align*}
&\PR\left(\left|\sum_{j=1}^{z_T} \frac{Y_j\I{Z_j=i}}{\sum_{j=1}^{z_T} Y_j}-\PR(t_b(\bm x)=i|\{(i_t,\bm x_t)\}_{t=1}^T)\right|>\epsilon/6\bigg| \{(i_t,\bm x_t)\}_{t=1}^T\right)\notag\\
&=\PR\left(\left|\PR(t_b(\bm x)=i|\{(i_t,\bm x_t)\}_{t=1}^T, \sum_{j=1}^{z_T}Y_j>l_T)-\PR(t_b(\bm x)=i|\{(i_t,\bm x_t)\}_{t=1}^T)\right|>\epsilon/6\bigg| \{(i_t,\bm x_t)\}_{t=1}^T\right)\notag\\
&\le \PR\left(2\PR\left( \sum_{j=1}^{z_T}Y_j\le l_T\bigg|\{(i_t,\bm x_t)\}_{t=1}^T\right)>\epsilon/6\bigg| \{(i_t,\bm x_t)\}_{t=1}^T\right).
\end{align*}

Notice that we are focusing on a fixed-design case, and $\{Y_j\}$ and $\{i_t\}$ are independent given Assumption <ref>.

\begin{align*}
\PR\left( \sum_{j=1}^{z_T}Y_j\le l_T\bigg|\{(i_t,\bm x_t)\}_{t=1}^T\right) = \PR\left( \sum_{j=1}^{z_T}Y_j\le l_T\right)\to 0
\end{align*}

by (<ref>).
This completes the proof.

To show the if part, we can construct a tree that splits at all products in $[N] \backslash (S \ominus S_i)$, then $S_i$ is the only assortment in the leaf node by the definition of PNN.

To show the only if part, we assume that there exists $S_j \in \mathcal{T}$ such that $S \ominus S_j \subsetneq S \ominus S_i$, then $S_j$ is always in the same leaf node as $S_i$ when predicting $S$ because $S_j$ is strictly more similar. Since the leaf node size is at most 1, $S_i$ will never be assigned.

Denote $M \coloneqq \Big\lceil2^N \cdot \lceil\log_2 N\rceil \cdot \log N / (N-2)\Big\rceil$.
Let $\mathcal{S}(S,r)\coloneqq \{S' \in 2^{[N]}: d(S,S') = r\}$ denote the set of assortments with distance equal to $r$ to assortment $S$.
Note that the cardinality of $\mathcal{S}(S,r)$ is $\binom Nr$.
By Definition <ref>, for an assortment $S' \in \mathcal{S}(S,r)$, $S'$ is the PNN of $S$ if none of the $2^r-2$ assortments that dominate $S'$
are included in $\mathcal T$.
That is, $\#\{S''\in 2^{[N]}: S''\ominus S\subsetneq S'\ominus S, S''\neq S\}=2^r-2$.
It is thus easy to see the probability that $S'$ is a PNN is $(1-\frac{2^r-2}{2^N})^M$ by Proposition <ref>.

Let $\mathcal{P}$ denote the set of all PNNs of $S$.
Then we have the probability that $S$ has PNNs within distance $r$ is

\begin{align*}
&\PR (\mathcal{S}(S,r) \cap \mathcal{P} \neq \emptyset)
< \binom{N}{r} \cdot \PR(S' \in \mathcal{P} | d(S, S') = r, S' \in \mathcal{T})\\
& = \binom Nr \cdot \Big(1-\frac{2^r-2}{2^N}\Big)^M < \binom Nr \cdot \frac{1}{N^{\frac{2^r-2}{N-2} \cdot \lceil \log_2 N\rceil}},
\end{align*}

where the first inequality follows from the union bound, and the second inequality follows from $(1-1/x)^x < 1/e$.
We write the upper bound of the above probability as $\PR_r\coloneqq \binom Nr \big/  N^{\frac{2^r-2}{N-2} \cdot \lceil \log_2 N\rceil}$ for simplicity.

We first consider for $r = \lceil\log_2 N\rceil$:

\begin{align*}
&\PR_r < \binom {N}{\lceil\log_2 N\rceil} \cdot \frac{1}{N^{\lceil \log_2 N\rceil} }
= \frac{N \cdot (N-1) \cdot \ldots \cdot (N-\lceil \log_2 N\rceil +1)}{(\lceil \log_2 N\rceil)! \cdot N^{\lceil \log_2 N\rceil}}\\
&< \frac{1}{(\lceil \log_2 N \rceil)!} \cdot \frac{N-\lceil \log_2 N\rceil +1}{N}.
\end{align*}

Next, we consider the case $r > \lceil \log_2 N \rceil$.
We bound $\PR_r$ in this case by a geometric sequence, because

\begin{equation}
\label{eq:P_r+1/P_r}
\frac{\PR_{r+1}}{\PR_r}
=\frac{N-r}{r+1} \cdot \frac{1}{N^{\lceil\log_2 N\rceil \cdot \frac{2^r}{N-2}}}
< \frac{N^{1-\lceil \log_2 N \rceil}}{\lceil \log_2 N\rceil+1}.
\end{equation}

From the above two inequalities we can conclude:

\begin{align*}
&\PR((\cup_{r = \lceil \log_2 N \rceil}^N \mathcal{S}_{S,r} ) \cap \mathcal{P} \neq \emptyset)
< \sum_{r = \lceil \log_2 N \rceil}^N \PR_{r} \\
& < \frac{1}{(\lceil \log_2 N \rceil)!} \cdot \frac{N-\lceil \log_2 N\rceil +1}{N} \cdot \frac{1}{1-N^{1-\lceil \log_2 N \rceil}/(\lceil \log_2 N\rceil+1)}\\
&= \frac{1}{(\lceil \log_2 N \rceil)!} \cdot \frac{1-(\lceil \log_2 N\rceil+1) / N}{1-N^{1-\lceil \log_2 N \rceil} / (\lceil \log_2 N\rceil+1)}
< \frac{1}{(\lceil \log_2 N \rceil)!},
\end{align*}

where the first inequality follows from union bound, the second inequality from (<ref>) and sum of an infinite geometric sequence, and the last inequality follows from $(\lceil \log_2 N\rceil+1)^2>N^{2-\lceil \log_2 N\rceil}$.

Let $\tilde{r}(N, M)$ denote the following random variable: the number of zeros in the largest binary number among $\{\bm x_i\}_{i=1}^M$, defined as $X_{(1)}$.
Let $r(N, M) \coloneq \E[\tilde{r}(N, M)]$.
As explained before Proposition <ref>, $r(N,M)$ is the expected distance from the assortment $\bm x=(1,1,\dots,1)$ to its PNN in the training data.
Let $Z$ denote the (random) number of $1$s before the first 0 in the largest number $X_{(1)}$.
Let $M_i$ denote the (random) number of binary numbers such that the first $i$ digits are all $1$s among $\{\bm x_i\}_{i=1}^M$.
Notice that $M_i \geq 1$ when $Z = i$. We have that

\begin{align}
\label{eq: R(N,M)_ineq}
r(N,M) &= \sum_{i = 0}^{N} \E\Big[\tilde{r}(N,M) \Big| Z = i\Big] \cdot \PR \Big(Z = i\Big)\nonumber\\
&=\sum_{i=0}^N \Bigg(\sum_{j=1}^M \E\Big[\tilde{r}(N,M)\Big| Z=i, M_i =j\Big]\cdot \PR \Big(M_i=j\Big)\Bigg) \cdot \PR \Big(Z=i\Big)
\end{align}

Note that conditional on $Z=N$, all digits of $X_{(1)}$ are $1$s and thus $\tilde{r}(N,M)=0$.
When $Z = i < N$ and  $M_i=j$, there are $j$ binary numbers (including $X_{(1)}$) such that the first $i$ digits are $1$s, and the $(i+1)$st digit is 0.
Otherwise $X_{(1)}$ (with exactly $i$ leading $1$s) cannot be the largest binary number.
For the digits from $(i+2)$nd to $N$th, it is a subproblem with $(N-i+1)$ digits and $j$ binary numbers.

\begin{align}\label{eq:PZ=i}
\eqref{eq: R(N,M)_ineq}&=\sum_{i=0}^{N-1} \sum_{j=1}^M \Big(1+r(N-i-1,j)\Big)\cdot \PR \Big(M_i=j\Big) \cdot \PR\Big(Z=i\Big)\notag\\
&\le\sum_{i=0}^{N-1} \sum_{j=1}^M \Big(1+r(N-i-1,1)\Big)\cdot \PR \Big(M_i=j\Big) \cdot \PR\Big(Z=i\Big)\notag\\
&= \sum_{i=0}^{N-1} \Big(1+r(N-i-1,1)\Big) \cdot \PR \Big(Z=i\Big) \nonumber\\
&= \sum_{i=0}^{N-1} \frac{N-i+1}{2} \cdot \PR \Big(Z = i\Big).
\end{align}

The last equality follows from the fact that for a random binary number of $N-i+1$ digits, the expected number of zeros is $(N-i+1)/2$ and thus its expected distance to $(1,1,\dots,1)$ is $(N-i+1)/2$.
To rigorously show the inequality in (<ref>), we can prove $r(N, M) \leq r(N,1)$ for $M \geq 2$ by induction.
Obviously $r(N,M) \leq r(N,1)$ holds when $N = 1,2$. For $N \geq 3$, suppose $r(i,M) \leq r(i,1), i =1,\ldots, N-1$ hold, then inequality (<ref>) hold, and we want to show $r(N, M) \leq r(N,1) = N / 2$.

\begin{align}
2\cdot \big(r(N,1) - r(N,M)\big) &\geq N - \sum_{i=0}^{N-1} (N-i+1) \cdot \PR \Big(Z = i\Big) \nonumber\\
&=N \cdot \PR \Big(Z=N\Big) + \sum_{i=2}^{N-1} (i-1) \cdot \PR \Big(Z = i\Big) - \PR \Big(Z = 0\Big) \nonumber\\
&\geq 1- \PR \Big(Z=1\Big) - 2 \PR \Big(Z=0\Big) \nonumber\\
&=1-\big(\frac{3}{4}\big)^M - \big(\frac{1}{2}\big)^M > 0.
\end{align}

The last equality follows from $\PR \Big(Z = 0\Big) = (1/2)^M$ and $\PR \Big(Z = 1\Big) = (3/4)^M-(1/2)^M$, which we will formally discuss later.
The last inequality holds when $M \geq 2$, then we prove that $r(N,M) \leq r(N,1)$, thus (<ref>) holds for all $N$ and $M$.

Next we analyze the probability $\PR(Z=i)$.
Note that $\PR(Z=i)=\PR(Z\le i)-\PR(Z\le i-1)$.
For $i<N$, the event $Z\le i$ occurs if and only if none of the $M$ binary numbers have $i+1$ leading $1$s.
Therefore $\PR(Z\le i)=(1-1/2^{i+1})^M$ and as a result $\PR (Z = i)=(1-1/2^{i+1})^M - (1-1/2^i)^M$.
For $i=N$, we have $\PR(Z=N)=1-(1-1/2^N)^M$.
Plugging $\PR(Z=i)$ into (<ref>), we have

\begin{align*}
r(N,M) &\leq \sum_{i=0}^{N-1} \frac{N-i+1}{2} \cdot \PR \Big(Z = i\Big)\nonumber\\
&= \frac{N+1}{2} \cdot \bigg(1-\PR\Big(Z=N\Big)\bigg)- \frac{1}{2}\sum_{i=0}^{N-1} i \PR \Big(Z = i\Big)\nonumber\\
&=\frac{1}{2}\Bigg[(N+1)\bigg(1-\frac{1}{2^N}\bigg)^M+\sum_{i=1}^{N-1} \bigg(1-\frac{1}{2^i}\bigg)^M-(N-1)\cdot \bigg(1-\frac{1}{2^N}\bigg)^M\Bigg]\nonumber\\
&=\frac{1}{2}\Bigg[\sum_{i=1}^{N} \bigg(1-\frac{1}{2^i}\bigg)^M + \bigg(1-\frac{1}{2^N}\bigg)^M\Bigg].
\end{align*}

Next we consider $M = \lceil 2^N / N\rceil$. When $N \geq 3$, using the fact that $1-1/2^i< \exp(-1/2^i)$, we have

\begin{align*}
&\sum_{i=1}^{N} \bigg(1-\frac{1}{2^i}\bigg)^{\lceil 2^N / N\rceil} + \bigg(1-\frac{1}{2^N}\bigg)^{\lceil 2^N / N\rceil}\nonumber\\
\le &\sum_{i=1}^{N-\lceil \log_2 N\rceil-1} \exp\left( - \frac{2^N}{N2^i}\right)
+\sum_{i=N-\lceil \log_2 N\rceil}^{N} \exp\left( - \frac{2^N}{N2^i}\right) +1\nonumber\\
\le &\sum_{i=1}^{N-\lceil \log_2 N\rceil-1} \exp\left( - \frac{2^N}{N2^i}\right)
+\frac{1}{e}+\frac{1}{\sqrt{e}}+\frac{1}{\sqrt[4]{e}}+\sum_{i=N-\lceil \log_2 N\rceil+3}^{N} \exp\left( - \frac{2^N}{N2^i}\right) +1\nonumber\\
\le&\sum_{i=1}^{N-\lceil \log_2 N\rceil-1} \frac{1}{e^{2^{ N-\lceil \log_2 N\rceil-i }}}
+\frac{1}{e}+\frac{1}{\sqrt{e}}+\frac{1}{\sqrt[4]{e}}+\sum_{i=N-\lceil \log_2 N\rceil+3}^{N} 1 +1\nonumber\\
\le &\sum_{i=1}^{N-\lceil \log_2 N\rceil-1} \frac{1}{e^{2( N-\lceil \log_2 N\rceil-i )}}
+\frac{1}{e}+\frac{1}{\sqrt{e}}+\frac{1}{\sqrt[4]{e}}+\lceil \log_2 N\rceil-1\nonumber\\
\le& \frac{1/e^2}{1-1/e^2} +\frac{1}{e}+\frac{1}{\sqrt{e}}+\frac{1}{\sqrt[4]{e}}+\lceil \log_2 N\rceil-1 < \lceil \log_2 N\rceil+0.91.
\end{align*}

The key to the inequalities is the fact that $\exp\left( - 2^N/(N2^i)\right)\le 1/e$ if $i=N-\lceil \log_2 N\rceil$.
In the last inequality, we bound the infinite sum of the geometric sequence.
It is easy to check the inequality also holds for $N=2$.
Thus $r(N,M) < \lceil \log_2 N\rceil/2+0.455$.

Consider the assortment to predict $S$ and the assortment in the same leaf node $S^*$.
We first prove the first part of the theorem.
From Proposition <ref> we know that $\PR (d(S, S^*) > \lceil \log_2 N\rceil-1) < 1/(\lceil \log_2 N\rceil)!,$ and by $c$-continuity we have

\begin{equation}
\label{eq:continue_error}
\PR\Big(\sum_{i \in [N]_+} \big|p(i, S) - p(i, S^*)\big|>\frac{c\log_2 N}{N}\Big) < 1/(\lceil \log_2 N\rceil)!.
\end{equation}

Suppose $Q$ is the number of transactions for assortment $S$ in the training data.
Let $\hat{p}(i, S^*)$ be the empirical frequency of choosing product $i$ among $Q$ samples.
Conditional on $Q$, we know $\hat{p}(i, S^*)$ has mean $p(i, S^*)$ and variance $p(i,S^*) (1-p(i, S^*))/Q$. Then by Chebyshev's inequality and $Q\ge \lceil\frac{N^3 \cdot (|S'|+1)^2}{c_1^2(\log_2 N)^2}\rceil$, we have

$$\PR \Big(\big|\hat{p}(i, S^*)-p(i, S^*)\big|\geq \frac{c_1 \cdot \log_2 N}{N \cdot (|S^*|+1)}\Big)
\leq \frac{p(i,S^*) (1-p(i, S^*))}{Q} \cdot \frac{N^2 \cdot (|S^*|+1)^2}{c_1^2 \cdot (\log_2 N)^2} < \frac{p(i, S^*)}{N}.$$

The total sampling error can be bounded by

\begin{equation}
\label{eq:sample_error}
\PR \Big(\sum_{i \in S^*\cup \left\{0\right\}} \big|\hat{p}(i, S^*)-p(i, S^*)\big|\geq \frac{c_1 \cdot \log_2 N}{N}\Big) < \frac{\sum_{i \in S^*\cup \left\{0\right\}} p(i, S^*)}{N} = 1/N.
\end{equation}

Combining (<ref>) and (<ref>) we have that

$$\PR \Big(\sum_{i \in [N]_+} \big|p(i,S) - \hat{p}(i, S^*)\big|>\frac{(c+c_1)\cdot \log_2 N}{N}\Big) <  \frac{1}{(\lceil \log_2 N\rceil)!}+\frac{1}{N}.$$

This completes the proof for the first part.

For the second part, similarly, let $S^*$ denote the assortment in the same leaf node as $S$. Let $M$ denote the number of assortments drawn with replacement. Let $Q$ denote the number of transactions for each assortment.
From Proposition <ref> we know $\E[d(S,S^*)] \leq \lceil \log_2 N/2\rceil+0.455< \log_2 N / 2+1.455$, and by $c$-continuity we have

\begin{equation}
\label{eq:continue_error_random_split}
\E\Big[\sum_{i \in [N]_+} \big|p(i,S)-p(i, S^*)\big|\Big] < \frac{c \cdot \log_2 N/2+1.455c}{N}.
\end{equation}

Recall that the empirical distribution $\hat{p}(i, S^*)$ has mean $p(i, S^*)$ and variance $p(i,S^*) (1-p(i, S^*))/Q$, then we have total sampling error is bounded by

\begin{align}
\label{eq:sample_error_randomsplit}
&\E\Big[\sum_{i \in S^*\cup\{0\}} \big|\hat{p}(i, S^*)-p(i, S^*)\big|\Big]
= \sum_{i \in S^*\cup\{0\}} \E\Big[\big|\hat{p}(i, S^*)-p(i, S^*)\big|\Big]
\leq \sum_{i \in S^*\cup\{0\}} \sqrt{\E \Big[\big(\hat{p}(i, S^*)-p(i, S^*)\big)^2\Big]}\nonumber\\
&=\sum_{i \in S^*\cup\{0\}} \sqrt{\Var\big[\hat{p}(i, S^*)-p(i, S^*)\big]}
< \sum_{i \in S^*\cup\{0\}} \sqrt{p(i, S^*)/ Q}
\leq \sqrt{(|S^*|+1) / Q}
\leq \frac{c_1 \log_2 N}{N}.
\end{align}

Combining (<ref>) and (<ref>) we have

$$\E\Big[\sum_{i \in [N]_+} \big|p(i,S) - \hat{p}(i, S^*)\big|\Big] < \frac{(c/2+c_1)(\log_2 N) + 1.455c}{N}.$$

This completes the second part.

We first provide a road map of the proof.
The analysis of the first split is the most important, as the subsequent splits can be analyzed similarly with similar error probabilities.
Therefore, we prove two lemmas to analyze the first split.
In the first lemma, we show that when $T\to +\infty$, the first split is on product one almost surely.
In the second lemma, we control the probability errors when $T$ is finite.
The remaining part of the proof applies the same technique to the remaining splits.

When the data size is sufficiently large, $T \rightarrow +\infty$, then the first split converges to product 1 almost surely, i.e., the theoretical Gini index of splitting at product one is the smallest almost surely.

Given the training data, we define the random variables $n_k^j$ ($n_k^{-j}$), which represent the number of assortments in the training data where $j$ is (not) in the assortment and product $k$ is chosen.
Also, let $n^j$ denote the number of assortments in the training data including product $j$.
To simplify the notation, we use product $N+1$ to denote the no-purchase option.
Our first step is to compute the Gini index $G_j$ if the first split is on product $j$.
Recall the definition of the Gini index: $\sum_{R_j} \frac{t_j}{T}\sum_{k=0}^N \hat p_{jk}(1-\hat p_{jk})$.
If the first split is on product $j$, then the left node (assortments without product $j$) has $n^j$ data points while the right node has $T-n^j$.
In the left node,
the fraction of assortments resulting in a purchase of product $k$, is $n_k^{-j}/(T-n^j)$.
Similarly, in the right node, the frequency is $n_k^j/n^j$ for product $k\le j$ and 0 for product $k>j$.
Therefore, we have that

\begin{align}
\label{Gini_j}
G_j &= \frac{n^j}{T}\sum_{k=1}^j \frac{n_k^j}{n^j}(1-\frac{n_k^j}{n^j})+\frac{T-n^j}{T}\sum_{k=1}^{j-1} \frac{n_k^{-j}}{T-n^j}(1-\frac{n_k^{-j}}{T-n^j})+\frac{T-n^j}{T}\sum_{k=j+1}^{N+1} \frac{n_k^{-j}}{T-n^j}(1-\frac{n_k^{-j}}{T-n^j})\nonumber\\
&= \frac{1}{T} \left(n^j-\frac{\sum_{k=1}^j (n_k^j)^2}{n^j}+T-n^j-\frac{\sum_{k=1}^{j-1} (n_k^{-j})^2 +\sum_{k=j+1}^{N+1} (n_k^{-j})^2}{T-n^j}\right)\nonumber\\
&=1-\frac{\sum_{k=1}^j (n_k^j)^2}{T n^j}-\frac{\sum_{k=1}^{j-1} (n_k^{-j})^2 +\sum_{k=j+1}^{N+1} (n_k^{-j})^2}{T(T-n^j)}.
\end{align}

Notice that the second term in (<ref>) only depends on assortments including product $j$, and the third term only depends on assortments without product $j$.

We define $H_j$ for the quantity in (<ref>) for simplicity:

\begin{equation}\label{eq:Hj-formula}
H_j \triangleq \frac{\sum_{k=1}^j (n_k^j)^2}{n^j}+\frac{\sum_{k=1}^{j-1} (n_k^{-j})^2 +\sum_{k=j+1}^{N+1} (n_k^{-j})^2}{T-n^j}.
\end{equation}

It's easy to see that $G_1<G_j$ if and only if $H_1>H_j$.

To compute and compare Gini indices $G_j$, we need to analyze the probability distributions of $n^j$, $n_k^j$, and $n_k^{-j}$,
Note that the randomness of $n^j$, $n_k^j$, and $n_k^{-j}$ are caused by the randomness of sampling assortments uniformly in the training data.
It is clear that $n^j$ has a binomial distribution $B(T,1/2)$, because each assortment includes product $j$ with probability $1/2$.
The random variables $n_k^j$ and $n_k^{-j}$ we defined above have the following binomial distribution for $1\leq j \leq N$:

& B(T,1/2^{k+1}) & & {1\leq k<j}\\
& B(T,1/2^j) & & {k=j}\\
&0 & & {j<k\leq N+1}
\end{aligned}\right. ,\quad
& B(T,1/2^{k+1}) & & {1\leq k<j}\\
&0 & & {k=j}\\
& B(T,1/2^k) & & {j<k\leq N}\\
& B(T,1/2^N) & & {k=N+1}
\end{aligned}\right. .$$

To understand it, note that an assortment is counted in $n_k^j$ when products $1$ to $k-1$ are not in the assortment while product $k$ and $j$ are in the assortment, according to the preference ranking.
So the probability is $1/2^{k+1}$.
The other probabilities follow a similar argument.
From the above distributions, we can show that when $T \rightarrow \infty$, $H_j$ converges to

$$H_j \rightarrow \frac{T}{3} \cdot \Big(1+\frac{1}{2^{2j-2}}+ \frac{1}{2^{2N}}\Big).$$

The theoretical Gini index for product $j$ is

\begin{equation*}
G_j \rightarrow \frac{2}{3}-\frac{1}{3\cdot 2^{2j-2}}-\frac{1}{3\cdot 2^{2N-2}}.%+O(1/T).
\end{equation*}

Obviously, $G_1 < G_j, j \geq 2$, so the theoretical cut of the first split is on product one.

Next, for finite $T$, we are going to bound the probability of incorrect splits.
We write $H_j$ as

\begin{align*}
H_j &= n^j \cdot \Bigg(\sum_{k = 1}^j \hat{p}_{k,j}^2\Bigg) + (T-n^j) \cdot \Bigg(\sum_{k = 1}^{N+1} \hat{p}_{k,-j}^2\Bigg) \\
&=\frac{T}{2} \cdot \Bigg(\sum_{k = 1}^j \hat{p}_{k,j}^2\Bigg)+ \frac{T}{2} \cdot \Bigg(\sum_{k = 1}^{N+1} \hat{p}_{k,-j}^2\Bigg) + \Bigg(n^j-\frac{T}{2}\Bigg) \cdot \Bigg(\sum_{k = 1}^j \hat{p}_{k,j}^2 - \sum_{k = 1}^{N+1} \hat{p}_{k,-j}^2\Bigg)\\
&=\frac{T}{2} \cdot \Bigg(\sum_{k = 1}^j \hat{p}_{k,j}^2\Bigg)+ \frac{T}{2} \cdot \Bigg(\sum_{k = 1}^{N+1} \hat{p}_{k,-j}^2\Bigg)+O_T(1) \cdot \Bigg|n^j-\frac{T}{2}\Bigg|,
\end{align*}

where $(\hat{p}_{k,j})_k$ and $(\hat{p}_{k,-j})_k$ are the empirical distributions of two multinomial random variables over $n^j$ and $T-n^j$  IID samples, respectively.