{'fraction_non_alphanumeric': 0.04569802296263432, 'fraction_numerical': 0.01358063434006774, 'mean_word_length': 4.1005629760459215, 'pattern_counts': {'":': 0, '<': 6, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 15, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Active Learning for Non-Parametric Choice Models

We study the problem of actively learning a non-parametric choice model based on consumers' decisions. We present a negative result showing that such choice models may not be identifiable. To overcome the identifiability problem, we introduce a directed acyclic graph (DAG) representation of the choice model, which in a sense captures as much information about the choice model as could information-theoretically be identified. We then consider the problem of learning an approximation to this DAG representation in an active-learning setting. We design an efficient active-learning algorithm to estimate the DAG representation of the non-parametric choice model, which runs in polynomial time when the set of frequent rankings is drawn uniformly at random. Our algorithm learns the distribution over the most popular items of frequent preferences by actively and repeatedly offering assortments of items and observing the item chosen. We show that our algorithm can better recover a set of frequent preferences on both a synthetic and publicly available dataset on consumers' preferences, compared to the corresponding non-active learning estimation algorithms. This demonstrates the value of our algorithm and active-learning approaches more generally.


Introduction
Choice modeling allows firms to model consumers' preferences and decisions. It can help with important operational decisions, including demand forecasting (e.g., McFadden et al. (1977), McGill and Van Ryzin (1999)), inventory planning (e.g., , Gaur and Honhon (2006), Aouad et al. (2019)), assortment optimization (e.g., Talluri and Van Ryzin (2004), Rusmevichientong et al. (2010), Davis et al. (2014), Golrezaei et al. (2014)), and product ranking optimization (e.g., Derakhshan et al. (2020), Niazadeh et al. (2021), ). Among choice models, parametric choice models -and in particular random utility maximization models -have received the most attention by far. While parametric choice models provide concise representations of consumer preferences and decisions, they impose certain structures on consumer preferences, which may not be valid (Jagabathula and Rusmevichientong (2019)). If the structures are invalid, imposing them can lead to model misspecification and inaccurate decision making. These drawbacks have motivated the recent introduction and study of non-parametric choice models (Farias et al. 2013, Jagabathula and Rusmevichientong 2017, Paul et al. 2018). Non-parametric choice models, however, are challenging to estimate using only offline collected transaction data since such data may not have enough variation in the offered sets of items.
In many settings, particularly on online platforms, one can go beyond using offline data. On these platforms, one can influence the data collection process, obtaining data sets more suitable for estimating non-parametric choice models. The process of influencing data collection, which is known as active learning, has been widely used in various contexts (see Settles (2009) and Aggarwal et al. (2014) for surveys, and Section 2 for a more detailed discussion of related work). In this process, the platform can dynamically change the offered set of items to arriving consumers and observe their choice. However, it is still unclear whether active learning can fully overcome the challenge of estimating non-parametric choice models. This motivates our main research question: How can we estimate a non-parametric choice model by relying on active learning? Can we estimate non-parametric choice models with a polynomial-size dataset, which is obtained through an efficient active learning process?
To answer these questions, we consider an online platform with n items. The platform faces distinct types of consumers: each consumer type is characterized by a preference ranking over the n items and the fraction of the population having this type. Consumers choose according to their types/rankings, and their types are not observable by the platform. The model is presented more formally and in detail in Section 3.
Very rare consumer types are hard or impossible to learn since the platform will (almost) never see them. However, their presence may still affect the learning of the more frequent types. To capture this trade-off, we distinguish types based on a threshold κ ∈ (0, 1): Types with probability at least κ are frequent, while types with probability less than κ are rare. Based on the preceding discussion, the platform is only interested in learning the rankings and probabilities associated with frequent types.
To learn frequent rankings, the platform engages in an active learning process. In every round of this process, a consumer (whose unobservable type is drawn based on the unknown population distribution) arrives. Upon the arrival of the consumer, the platform decides on the set (assortment) of items to offer. The consumer then chooses the item she ranks highest among the items offered. The platform observes the choice made by the consumer; then, the process repeats with another consumer. That is, in every round, based on past observations, the platform actively/dynamically decides what set to offer the consumer to learn frequent rankings and their associated probabilities.

Our Contributions
Indistinguishability. One of the main challenges in learning non-parametric choice models is the identifiability problem: the data may not uniquely identify the choice model. This problem clearly exists when the choice model is estimated from offline transaction data that contains the choices made by consumers only for some pre-specified offered sets. To illustrate this point starkly, consider a data set where all consumers were offered the same set S. In this case, the algorithm can only learn the distribution of the most preferred item in S. The algorithm cannot infer how the rest of the items are compared. With active learning, however, the algorithm can introduce heterogeneity in the offered sets. This raises the following question: Is it possible to learn every non-parametric choice model using active learning? In Section 4, we show that even with active learning, regardless of how many consumers the algorithm interacts with, the choice model may not be uniquely identifiable. In particular, we determine simple conditions under which two different nonparametric choice models are information-theoretically not distinguishable from each other, no matter how many and what assortments are offered to arriving consumers. This is shown in Theorem 1.
Directed Acyclic Graph (DAG) representations of non-parametric choice models. In light of our indistinguishability result, in Section 5, we provide a novel representation of non-parametric choice models. This representation, which we refer to as Directed Acyclic Graph (DAG) representation, can always be uniquely identified, assuming enough samples with suitably chosen choice sets. In the DAG, each node is labeled with a set A. Additionally, each node with label A is assigned a probability, which is the probability that a consumer ranks all items in A ahead of all items not in A.
All nodes labeled with sets A of the same cardinality j = |A| together form level j of the DAG. The DAG representation contains a directed edge from A to A if and only if |A | = |A| + 1, and there exists at least one consumer type that ranks all items in A ahead of all items not in A, and ranks all items in A ahead of all items not in A . In particular, this implies that A = A ∪ {z} for some item z.
We highlight that the j-th level of the DAG representation (for j ∈ [n]) provides a distribution over top-j most preferred item sets; hence, it can be used in various decision-making processes, including inventory planning and product design decisions.
Active learning of the DAG representation of non-parametric choice models.
Having introduced our DAG representation, in Section 6, we develop a polynomial-time algorithm to learn the DAG representation associated with frequent types in a non-parametric choice model; recall that a type is frequent if it appears with probability at least κ. Our algorithm decides which assortment to offer for each arriving consumer and how to process the observed information (i.e., the chosen item). The algorithm is inspired by the structure of the DAG: it learns the nodes in the DAG level by level while estimating the probability of each node using an inclusion-exclusion method.
To learn level j + 1 of the DAG, the algorithm considers all nodes A for level j, as well as all items z / ∈ A. It then estimates the combined probability of all types that have A in the first j positions in their ranking (in any order), followed by z in position j + 1, followed by the remaining items in any order. The sum of these estimated probabilities for all pairs (A, z) with A ∪ {z} = A then gives the estimated combined probability of types having the items of A as their top j + 1 items (in any order). Whenever this estimated probability is large enough, the algorithm adds a node for A to the estimated DAG. Hence, the key task is to accurately estimate the combined frequency of types ranking A in the first j position, z in position j + 1, and the remaining items last. Unfortunately, this quantity cannot directly be estimated; instead, the algorithm can find out the combined frequency of types ranking a given item z highest within a given set (by offering that set multiple times and observing the frequency with which z is chosen). In particular, notice that simply offering the set N \ A and observing the frequency with which z is chosen does not give the correct probability: it faces "interference" from types that not only rank z ahead of the rest of N \ A, but also ahead of some or all of A. Inferring the correct cumulative frequency requires the use of an inclusion-exclusion approach using multiple choice sets of different sizes.
Our main technical contribution is a way to choose a much smaller and non-obvious collection of sets to run inclusion-exclusion, by running a set cover approximation algorithm on suitably chosen prefixes of A. When the set covers are sufficiently small (logarithmic in size), the algorithm idenitfies the correct DAG (with high probability) using only a polynomial number of active queries; in particular, this holds when the set of frequent types is uniformly random. When the set covers are larger, the algorithm can adapt by using more queries or by diagnosing that an ouput obtained using few queries may not be reliable. This distinguishes our approach from parametric models, where one may output an inaccurate choice model if the modeling assumption is violated. The algorithm and its analysis (Theorem 2) are presented in detail in Section 6.
Value of active learning via a case study. To evaluate the accuracy and simplicity of our algorithm, we test it empirically on a set of choice models synthetically generated and a set of ranked preference parameters inferred from a Sushi preference data set (Kamishima (2003), Kamishima et al. (2005)); the experiments are presented in Section 7. We show that empirically, the number of data points needed to estimate the DAG representation of a choice model accurately is smaller than the theoretical bound, which shows the robustness of our algorithm. We also observe that our algorithm significantly outperforms a non-active learning estimation algorithm (Farias et al. (2013)) in estimating the set of frequent preferences and their probability using a smaller number of queries. This shows the value of our algorithm and the active learning approach in estimation.

Related Work
Parametric choice models. There are two general approaches to modeling consumer preferences: parametric and non-parametric models. Parametric choice models specify some functional form that connects related attributes and price to utility values and choice probabilities. One example is a choice model that assumes independent demand for each product; such a model does not capture substitution effects between similar products in the offered assortment ). Another example is the Multinomial Logit model (MNL), a parametric choice model that is commonly used in marketing, economics (see Ben-Akiva et al. (1985) and ), and revenue management (McFadden (1973), Ben-Akiva et al. (1985)). MNL has the IIA (independence of irrelevant alternatives) property: the odds of choosing one item over another do not depend on whether or not a third item is present in the assortment. This property is frequently unrealistic, especially when products exhibit complementarities. Other examples of parametric choice models, such as the generalized nested logit model (Wen and Koppelman (2001)), and mixed logit model (Ben-Akiva et al. (1985)) overcome the IIA restriction. Along with MNL, they are included as special cases of the generalized random utility model (Walker and Ben-Akiva (2002)). Yet another example of a parametric choice model is the cascade choice model (Aggarwal et al. (2008), Kempe and Mahdian (2008), ) that was originally defined to model click probabilities in sponsored search ads, but can model how a consumer goes through items sequentially until she chooses an item to buy or exits the process.
Historically, there is a vast literature on optimizing the assortment and price based on some parametric choice models. This includes the seminal work by Talluri and Van Ryzin (2004) that infers a revenue-ordered set (a set containing a certain number of items with the highest revenue) as an optimal assortment for the deterministic MNL model, the work of Rusmevichientong et al. (2010) determining the optimal assortment for the MNL model with a capacity constraint, the work of Rusmevichientong and Topaloglu (2012) who develop an optimal assortment for a robust set of likely parameters of choice models, and the work of Davis et al. (2014) who optimize the assortment for the nested logit model. Implicit in this general approach is the caveat that one should fit the right parametric choice model to data before making predictions or decisions; this is a difficult problem since the implicit prespecified structures in the parametric choice models might not be true in practice. There is a huge risk of model mis-specification, which will lead to inaccurate decision making downstream. Thus, there is a trade-off between specification and estimation: while a complex model can approximate a wider range of choice behavior and hence has a small specification error, a complex model may have big estimation errors when estimated using a finite set of data.
Non-parametric choice models.  (2015) start from a parsimonious set of preferences, then iteratively add new preferences that increase the likelihood value of the data using a column generation based procedure; van Ryzin and Vulcano (2015) develop an efficient and easy-to-implement expectation maximization method that finds the non-parametric choice model with the highest likelihood. Our work is different from these three in one main aspect: we go beyond offline data and estimate the choice model via an active learning procedure, meaning that the algorithm gets to determine the assortments offered to consumers. This procedure allows us to acquire the most useful data, by querying the right assortments. As a result, our algorithm overcomes the identifiability issues that arise when one estimates the choice model using offline data. We highlight that instead, van Ryzin and Vulcano (2015) and Farias et al. (2013) aim to overcome this issue by imposing assumptions on the observed data. In van Ryzin and Vulcano (2015) and van Ryzin and Vulcano (2017), the authors impose that for each offer set S and product z in the set, there exists a preference ranking under which z ranks highest in S; thus, they only consider items that are preferred the most by at least one type. In contrast, we consider all items and learn the set of the most popular items. Farias et al. (2013) impose the assumption that for every preference appearing in the population, there exists a query and an item in the data such that the item ranks the highest in the query only for that preference, and that the set of probabilities is linearly independent with respect to the integers. 1 We do not need to make any such assumptions, instead using active learning to learn the DAG representation of the non-parametric choice model; the DAG representation is unique given the transaction data.
There is a long line of work that aims to design algorithms identifying optimal or nearoptimal revenue maximizing assortments, under the assumption that the model primitives are known. These studies are usually accompanied by a case study in which the model primitives are estimated from either real or synthetic data sets. The case studies are usually used to evaluate the proposed assortment planning algorithms; see, for example, (Haensel andKoole (2011), Honhon et al. (2012), Jagabathula and Rusmevichientong (2017), Aouad et al. (2018), Aouad et al. (2019), Feldman et al. (2019, Derakhshan et al. (2020)) for some of the work that follows this approach for non-parametric choice models. To estimate the choice models, these approaches mostly use maximum likelihood estimators (MLE): the locally optimal solutions are obtained via expectation maximization (EM) algorithms. Notice that the estimation process in these works tends to be conducted under restrictive assumptions. While these assumptions are mainly imposed to ensure the tractability of the assortment planning problem, the assumptions can simplify the estimation process as well. For example, Feldman et al. (2019) assume that consumer types are derived from paths in a tree, where the set of preference lists consists of ordered nodes visited along each path in the tree. This assumption allows them to use MLE on a domain of polynomial support size, to derive a fitted general tree representing the choice model while only considering linear paths on the tree. Honhon et al. (2012) assume that all the products can be mapped onto a hierarchical ordering system, such as branched, vertical or horizontal order; they then use a dynamic programming based algorithm to find the optimal assortment. On the contrary, we do not make any such assumptions on the items.
Online learning for assortment planning. The literature on online learning for assortment planning is also related to our work. In this literature, the goal is to learn the consumers' preferences from their actions, in order to identify the revenue-optimal assortments. This is mainly done for parametric choice models such as the multinomial logit model (MNL) and Markov Chain model, as seen, for example, in (Rusmevichientong et al. (2021)). While these works mostly care about identifying the optimal assortment and minimizing regret, we focus on estimating the choice model itself. Furthermore, online learning has, to the best of our knowledge, not yet been studied for non-parametric choice models.
Active learning. Active learning, sometimes also known as "query learning" or "optimal experimental design" in statistics, is a field of machine learning in which the learning algorithm gets to choose the queries (unlabeled data), to be labeled by an oracle which knows the true labels. This control over the training data typically improves the performance of the algorithm with less training data. Within machine learning, the idea of active or online learning was introduced in the seminal papers of Angluin (1988) and Littlestone (1988), in the context of learning a binary classifier. Naturally, combining offline or unlabeled data with data obtained online is frequently the best or most natural choice in practice; see, e.g., Cohn et al. (1996). Although active learning has been well studied in the literature (see Settles (2009) and Aggarwal et al. (2014) for surveys), to the best of our knowledge, active learning has not been used for learning choice models. Previously, several works in the literature have explored and shown the value of active learning compared to its "passive" counterpart. For example, Zheng and Padmanabhan (2006) developed a new active learning technique for an information acquisition problem in order to, for example, predict the probability of purchase and credit default rate. They demonstrated that the proposed method performs well empirically. Similarly, Aviv and Pazgal (2002) explored the value of proactively setting prices to impact the revenue. A line of work similar to active learning is the dynamic sampling literature where one dynamically selects samples to learn parameters while optimizing the objective functions (see Shi et al. (2021), Zhang et al. (2020), Shin et al. (2018)). Shi et al. (2021) dynamically allocate samples in a finite sampling budget to learn the system's feasible alternatives efficiently in a feasibility determination problem appearing in many applications, such as call center design and hospital resource allocation. Shin et al. (2018) intelligently allocate samples in their simulation to minimize the probability of selecting a system that does not have the highest mean out of several competing alternatives ("systems"), when the probability distribution determining each system's performance is unknown but can be learned from a limited number of samples they can obtain. However, none of these dynamic sampling approaches was done in the assortment planning or choice modeling setting.
Active learning of a ranking in a non-parametric setting is also closely related to the classic sorting problem. Indeed, sorting n items using pairwise comparisons can be described as follows: There is only one type of ranking, and a "learner" repeatedly chooses two elements, learning which of the two items is "preferred." When the query responses are noiseless (that is, the comparison results are always correct, corresponding to a single type), "Merge Sort" is an efficient algorithm that discovers the underlying ranking in O(n log n) queries. Several versions of this problem with noisy responses have also been studied. Such noisy responses can be construed as arising due to additional types which have different rankings. When types are drawn i.i.d. for each comparison, this results in a model in which each comparison result is incorrect (with respect to the ranking of the majority type, which is to be inferred) with some probability, independent of all of the previous comparisons. It is easy to see Merge Sort can be adapted to learn the underlying ranking with high probability using O(n log 2 n) comparison. More sophisticated algorithms have been designed to improve the query complexity down to O(n log n). See Feige et al. (1990) and Karp and Kleinberg (2007).

Model
We use the following standard conventions.
[k] = {1, . . . , k} is the set of the first k integers. Vectors are denoted by bold face. When some quantity (such as a frequency/probability p or a set V etc.) has a ground truth value and an estimate by an algorithm, we usep (orV etc.) to distinguish the estimate from the ground truth. We may omit the hat when there is little risk for confusion.

Choice Model
Let N = {1, 2, . . . , n} be the universe of items and Π be the set of all possible rankings over N . That is, |Π| = n!. We consider a non-parametric choice model, where each ranking π ∈ Π over N represents the preferences of a type. π(i) is the i th most preferred item by consumers of type π, and for any item z ∈ N , π −1 (z) is the rank/position of item z for consumers of type π. For each ranking π ∈ Π, let p(π) denote the probability of a consumer having the ranking π. Note that for some π ∈ Π, we can have p(π) = 0. When a consumer of type π is offered an assortment of items S ⊆ N , she chooses her most preferred item among those in S; that is, she chooses the item z ∈ S such that π −1 (z) < π −1 (x) for all x ∈ S, x = z. We write Θ z (S) = {π ∈ Π | π −1 (z) < π −1 (x) for all x ∈ S, x = z} for the set of types π ∈ Π that choose item z ∈ S when the set S is offered. Then, for any set S and item z ∈ S, we define q z (S) as the probability that a consumer chooses item z when the set S is offered. That is,

Frequent vs. Rare Rankings, and a Generative Model
In our model, there is a set Π F 0 of (at most) K candidate frequent types. In our general type model, Π F 0 can be chosen adversarially. Under the random type model, Π F 0 is chosen as a set of K i.i.d. uniformly drawn rankings from the set of all rankings. 2 All of our correctness results for inferring types hold in the general type model, while the sample efficiency results hold under the random type model.
An adversary chooses the actual frequent types Π F ⊆ Π F 0 from the set of candidate frequent types; all remaining types with positive probability, Π R = π ∈ Π | p(π) > 0, π / ∈ Π F , are called rare types, where we recall that Π is the set of types/rankings. The adversary then assigns probabilities p(π) to each type/ranking π ∈ Π, subject to the following constraints: 1. The frequent types appear at least κ fraction of the time, i.e., p(π) ≥ κ for all π ∈ Π F . 2. The rare types appear less than κ fraction of the time, even cumulatively, i.e., p(π) < κ for all rare types π ∈ Π R and π∈Π R p(π) ≤ ρ.
Note that for some of the rankings π in Π, we can have p(π) = 0, but all the rankings in Π F and Π R have positive probability. When the candidate frequent rankings Π F 0 can be adversarial, we call the model with parameters κ ∈ (0, 1) and ρ ∈ [0, 1) the (κ, ρ)-General Model; when Π F 0 is random, we refer to the model as the (κ, ρ)-Random Model. We note that our random model captures a scenario where consumer types are very heterogeneous. We further note that even though the sample complexity parts of our guarantees hold only under the Random Model, our experiments (in Section 7) show that the algorithm performs well when applied to the sushi data that contains very similar rankings.
Notice that due to the lower bound of κ on probabilities in Π F , we have that |Π F | ≤ 1 κ . Intuitively, we can think of Π F as a set of main types in the choice model and Π R as the noise. An algorithm's goal will then be to accurately infer the rankings in Π F and their probabilities; the larger the combined probability ρ on the rare types (i.e., the noise), the less accurate the estimates will become.

Active Learning of the Choice Model
We are interested in actively learning the choice model in a setting where consumers' types are not observable. In an active learning framework, the algorithm gets to decide -based on all past observed choices -which subset/assortment S ⊆ N to offer to the next consumer. The algorithm does so without knowing the next consumer's ranking/type, which is drawn from the choice model, independently of all past consumers' types. That is, the consumer is of type π ∈ Π with probability p(π). Upon being presented with the assortment S, the consumer chooses her most preferred item within the set S according to her ranking π. For simplicity, we assume that a consumer always chooses an item when the assortment offered is non-empty; that is, no type has a no-purchase option. 3 We emphasize that due to practical consideration (consider an online retail site in which each consumer purchases items much less frequently than the overall rate of transactions), we assume that each consumer can only be queried once. This prevents an algorithm from immediately collecting detailed information about a type via multiple queries.
The algorithm's goal is then to learn, with probability at least 1 − δ, the top n 0 positions of all frequent rankings (i.e., (π(1), π(2), . . . , π(n 0 )), π ∈ Π F ) and their corresponding probabilities within accuracy (plus an error term depending on ρ) as seen in Theorem 2, using a number of queries which is polynomial in n, 1/κ and 1/ . (We use the terms "samples" and "queries" interchangeably throughout the paper.) Here, n 0 = αn for some constant α ∈ (0, 1). Note that the algorithm need not learn the rare types; after all, it could take many queries to even observe a single sample from the rare types. We also are only interested in learning the n 0 most popular items in the frequent rankings. Knowing the most popular items could help decision makers with inventory planning and product design decisions, to name a few. Furthermore, learning the top n 0 items can be justified from both practical and technical perspectives. Practically speaking, consumers are often unsure about their preferences for the non-top items in their ranking; hence, they can be inconsistent in choosing among the set of items at the bottom of their ranking (Chernev (2006), Goldin and Reck (2015)). In other words, even if the items appearing in low positions were learned, the results might not be very reliable. Moreover, the items at the end of a consumer's ranking are only purchased when none of her top items are available in the offered sets. Thus, when we see an item in one of the bottom positions of a type being purchased in the transaction data, this data point is likely the result of a different consumer type which ranks the particular item higher. From a technical perspective, as shown in Theorem 2, as n 0 gets larger, distinguishing different types of consumers in order to learn their rankings requires a large number of queries. Given the cost of querying, one would like to avoid having large values for n 0 , i.e., there is a tradeoff between using few queries vs. learning the bottom fraction of items of each type.

Indistinguishable Pairs of Rankings
In this section, we show that there exist instances for which it is information-theoretically impossible to recover the set of types representing the consumer's choice model using active learning. This motivates our choice to use DAGs as a representation of the types -in a sense, they extract the most information that can be learned. We will discuss the DAG representation more in the following section. Here, we show that when the set of frequent rankings Π F contains an indistinguishable pair of rankings (in the sense of the following definition), it is information-theoretically impossible to discover the set of types Π F uniquely.
Definition 1 (Indistinguishability). Two rankings π and π are i-indistinguishable for some 2 ≤ i ≤ n − 2 if and only if they satisfy the following three conditions: 1. the set of items in the first i position of π and π are identical, i.e., 2. at least one item among the top i items has different positions in π and π , i.e., for at least one j ∈ [i], we have π(j) = π (j), and 3. at least one item among the bottom n − i items has different positions in π and π , i.e., for at least one j ∈ {i + 1, . . . , n}, we have π(j) = π (j).
Two rankings are indistinguishable if they are i-indistinguishable for some 2 ≤ i ≤ n − 2.
The following is the main result of this section.
Theorem 1 (Impossibility Result). Suppose that the set of frequent rankings Π F contains two rankings π and π that are indistinguishable. Then, it is information-theoretically impossible to discover the set of types Π F uniquely.
We will prove that no algorithm -regardless of computational power or number of queries -can distinguish between Π F and Π F . We do so by a simple coupling argument: we couple the draws of types from Π F and Π F in such a way that the algorithm will see the exact same responses for each query. Importantly, because the algorithm chooses the query without knowledge of the consumer's type, the coupling can be based on the query. The coupling is straightforward. For any type π ∈ Π F \ {π, π }, the type π is drawn under Π F exactly when it is drawn under Π F . In particular, exactly the same item is chosen by the drawn consumer under both models, because the consumer has the same type. For the remaining types π, π , π, π , we use the following couplings, depending on the query set S: • If S ∩ A = ∅, then the coupling produces (π, π) with probability q, (π , π ) with probability q, and (π , π ) with probability q − q. That is, for example, when π is generated under Π F with probability q, π is also generated under Π F with the same probability.
Notice that the respective marginal probabilities are all as prescribed by the choice models, so this is a valid coupling. Furthermore, because only an item from S∩A can be chosen, the same item will be chosen for each possible pair of types (π, π), (π , π ), (π , π ), because for each pair, the two types comprising it agree on the ranking of the top i items.
• If S ∩ A = ∅, then the coupling produces (π, π ) with probability q, (π , π) with probability q, and (π , π ) with probability q −q. Again, notice that all marginal probabilities match those prescribed by the choice models, so the coupling is valid.
Because the chosen item will always be from S \ A, all possible pairs of types will choose the same item; this is because each such pair has the same rankings for S \ A.
We have thus produced a valid coupling under which exactly the same item is chosen under Π F and Π F . In particular, this means that the marginal probabilities of choosing each item are the same under both choice models, so an algorithm will observe the exact same distribution under both models, and cannot distinguish them.
Theorem 1 shows that when there are indistinguishable pairs of (frequent) rankings, no algorithm can learn the choice model. However, even if the set of frequent rankings Π F contains pairs of indistinguishable rankings, we would still like to recover as much information as possible. Motivated by our indistinguishability result, we present a novel representation of a non-parametric choice model, a Directed Acyclic Graph (DAG) representation, in the next section. The DAG representation of a choice model can always be uniquely identified using active learning.
We remark that even if the frequent types are drawn i.i.d. uniformly, indistinguishable pairs are likely to occur -in particular, assuming the random model for frequent types does not obviate the need for DAG representations. To see this, consider i = 2. Given a ranking π, a uniformly random ranking starts with (π(2), π(1)) with probability 1 n(n−1) , so it is 2-indistinguishable from π with probability 1 n(n−1) ·(1−1/(n−2)!) ≥ 1 n 2 (for n ≥ 4, which is necessary for indistinguishability). By a Birthday Paradox argument, a 2-indistinguishable pair of types will occur with constant probability when K = Ω(n), and with high probability when K = ω(n). (Recall that K is an upper bound on the number of frequent types.) Thus, as the number of types will typically exceed the number of items, indistinguishable pairs must be accounted for, even in our random model.

DAG Representation of a Choice Model
We present the Directed Acyclic Graph (DAG) representation of a choice model. The DAG representation is inspired by our negative result in the previous section; in a sense, it allows us to encode as much information about the types as can be inferred from a sampling process in which each consumer has unknown type and makes only a single choice.
To motivate the approach, we revisit the proof of the impossibility result in Theorem 1. Consider two i-indistinguishable rankings π, π . Then, we cannot tell apart a world in which just these two types are present, or some/all of the probability lies on types combining the ranking of the first i items according to π with the ranking of the remaining n − i items according to π (and vice versa). Let A = {π(1), . . . , π(i)} = {π (1), . . . , π (i)} denote the common set of i items ranked first (in different orders) by π, π . Then, a sampling-based algorithm can infer the probabilities with which A is ranked according to π and according to π , and similarly for N \ A; it just cannot infer how these rankings are "combined." We can consider this as the rankings π, π "merging" after position i, because they both have the set A in the first i positions; subsequently, they split again, but the "merge point" corresponds to an indistinguishability. This intuition generalizes to more complex similarities and differences between types, and leads to our definition of the DAG representation. We will later see in Figure 2 that Π F andΠ F in Theorem 1, with their corresponding types' probability, have the same DAG representation.

Prefixes, Sets of Prefixes, and their Probabilities in DAG Representation
The DAG representation relies on the notion of prefixes in the choice model. We begin by defining the following nomenclature for prefixes and sets of prefixes.

2.
A j denotes the set of prefixes containing the j most preferred items of types with positive probability in Π, i.e., A j denotes the set of prefixes of at most j items.
Note that different rankings can have the exact same set of items for their top j positions, and even if their ordering of the top j items differs, they could have the same prefix.
For the rest of the paper, when we restrict ourselves to frequent (rare) types Π F (Π R ), we simply add a superscript F (R) to all the variables. For example, A F j denotes the set of prefixes containing the j most preferred items of types in Π F . The following definition captures sets of prefixes focusing on a set of items A and a specific item z.
Definition 3 (Sets of Prefixes with specified element). Let A ∈ A j be a prefix of size j = |A|, and z / ∈ A. We define the following.
1. Π A⊕z denotes the set of rankings with positive probability in Π whose top j items form the set A (in any order), and the item in position j + 1 is z, i.e., Notice that the prefixes of size (j + 1) of all rankings in Π A⊕z are all A ∪ {z}. The definitions of Π F A⊕z and Π R A⊕z follow, restricted to the set of frequent and rare rankings, respectively.
2. We denote by Φ Pre,F (A, z) the set of all frequent prefixes A in A F ≤j that are a proper subset of A and such that A ∪ {z} is also a prefix of a frequent type, i.e., We define Φ Pre,R (A, z) analogously.
We next define probabilities of a prefix and of sets of prefixes.
Definition 4 (Probabilities of Prefixes). space 1. The probability for an arbitrary prefix A is i.e., the probability that the set of the top |A| items of a random consumer type equals the set A.
2. Consistent with our general convention, the probability of a set of rankings with certain condition on the prefixes (such as Π A⊕z ) is the sum of probabilities of rankings in the set.
As a result of this definition, notice that p(A) = 0 whenever A / ∈ A |A| . We next observe some useful basic properties of the sets of types we defined and their probabilities.
Proof. For the first part of the lemma, if |A| = |A |, then z is in different positions for types in Π A⊕z and Π A ⊕z , so no type can be in both sets. Otherwise, the set of elements preceding z is different in Π A⊕z and Π A ⊕z , so again, no type can be in both sets. Then, because the sets Π A ⊕z for A ∈ Φ Pre,R (A, z) are pairwise disjoint, we obtain that where the second step used that we are considering the total probability on a (sub-)set of rare types.

The DAG Representation
Having defined prefixes and their probabilities, we now define the DAG representation of a non-parametric choice model.
Definition 5 (DAG Representation of Π). The DAG representation of a choice model (Π, p), denoted by G = (V, E), has one node for each prefix A ∈ j∈[n] A j :=V; we identify nodes with the prefix they correspond to. Level j of the DAG consists of exactly the prefixes of size j, i.e., of A j . Edges in the DAG only exist between consecutive levels. For a prefix A ∈ A j and z / ∈ A such that A := A ∪ {z} ∈ A j+1 , the edge from A to A exists if and only if Π A⊕z = ∅, i.e., there exists at least one type in Π with positive probability that ranks A first in some order, followed by z. In this case, the label of the edge (A, A ) is (A, A ) = z. The probability of a node is simply the probability p(A) of the corresponding prefix A. We say that two DAG representations G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 ) are identical if V 1 = V 2 and E 1 = E 2 , with all the labels of the nodes (and thus the edges) and the probabilities of the nodes being the same.
Definition 6 (Truncated DAG). We define G j = (V j , E j ) to be the DAG induced on the nodes on levels 0 to j, i.e., the nodes that represent sets with top j ∈ {0, 1, . . . , j} items, and their corresponding probability.
As before, G F j = (V F j , E F j ) denotes the DAG induced on the nodes that represent sets of top j ∈ {0, 1, . . . , j} items in the rankings Π F . In what follows, our goal is to design algorithms to learn the DAG representation of a choice model, specifically learning nodes on the top n 0 level in the choice model DAG and their corresponding probabilities.

The DAG Ranking Algorithm
The DAG Ranking algorithm, AlgDAG (Algorithm 1), builds a DAG representation (Ĝ F n 0 ,p(·)) of the first n 0 levels of the choice model level by level. 4 The goal is to obtain, with probability at least 1 − δ, the correct DAGĜ F n 0 = G F n 0 = (V F n 0 , E F n 0 ) on the frequent types, and to approximate the probabilities associated with all nodes well, guaranteeing that max Here, > 0 and δ ∈ (0, 1) are the desired accuracy and correctness probability, which are specified by the decision-maker. Ideally, we would like to bound the error in the estimates by just ; unfortunately, an error term of the order of ρ seems unavoidable, as the rare types might be essentially identical to one of the frequent types (up to the order of the last two items). Whether the factor n 0 can be avoided is an interesting question, discussed in Section 9.
AlgDAG takes α, , and δ as inputs: α = n 0 n is the fraction of positions the algorithm should estimate while and δ are the accuracy parameters; it aims to estimate the frequent rankings of either a (κ, ρ)-General Model or a (κ, ρ)-Random Model. We consider n, κ, and ρ as global "information" throughout the paper.
AlgDAG starts withĜ F 0 = {∅} and its correspondingp(∅) = 1. It then buildsĜ F j and its respective probabilitiesp(·) level by level. We writeĜ F j = (V F j ,Ê F j ) for the estimated DAG up to level j, andp(·) for the estimated probabilities.
To estimate the set A j+1 of nodes on level (j + 1) (which are the sets of the top (j + 1) items), the algorithm aims to find all nodes of the formÂ ∪ {z} for allÂ ∈ A j (soÂ is one of the nodes earlier inferred for level j) and z / ∈Â, whose probabilities exceed κ. For each nodeÂ in A j and z / ∈Â, the algorithm calls another algorithm AlgIE to obtain an estimatê p(ΠÂ ⊕z ) of the probability p(ΠÂ ⊕z ) of havingÂ for the top j items followed by item z. If the estimatep(ΠÂ ⊕z ) is sufficiently large, specifically,p(ΠÂ ⊕z ) ≥ κ/2, the algorithm adds tô E F j+1 an edge with label z fromÂ toÂ ∪ {z}, and adds the estimated probabilityp(ΠÂ ⊕z ) to the probability ofÂ ∪ {z}. (It also creates the nodeÂ ∪ {z} if it did not exist inV F j+1 before.) AlgDAG does this for all n 0 levels, and returns the resulting DAGĜ F n 0 = (V F n 0 ,Ê F n 0 ) with corresponding probabilitiesp(·). Note that this algorithm is easy to implement.
We emphasize the crucial distinction between the three different probabilities we consider and their empirical estimates: • The quantity the algorithm aims to ultimately compute is an estimatep(A ∪ {z}) of p(A ∪ {z}), the probability that the items in A ∪ {z}, in any order, comprise the first j + 1 items of a random type.
• As an intermediate step, the algorithm computes an estimate of p(ΠÂ ⊕z ), the probability that a random type ranksÂ first, and z in position j + 1 exactly. This probability is upper-bounded by p(Â ∪ {z}), but typically differs.
• The direct observation of the algorithm is the estimateq z (N \Â) of the probability q z (N \Â) that for a random type, z is ranked before all other items in N \Â. Since such rankings do not impose any restrictions on where the items ofÂ are ranked, they constitute a larger set than those withÂ ∪ {z} in their first j positions. Thus, the probability is an upper bound on p(Â ∪ {z}).
The key intermediate step is thus obtaining accurate estimates of the probability of ΠÂ ⊕z from the observedq z (N \Â). Thereto, AlgDAG uses ALgIE (Algorithm 2), which is based on the Inclusion-Exclusion Principle -the analysis of its errors is the key mathematical contribution of our work.

Interference and Inclusion-Exclusion
In the following, we focus on one set A, and omit the distinction between true and estimated sets, since it has no bearing on the analysis. Recall from the preceding discussion that the algorithm's observation q z (N \ A) is the probability that a random type ranks z ahead of all items in N \ A, whereas the algorithm aims to estimate the probability of Π A⊕z , the probability that a random type ranks z ahead of all items in N \ A and behind all items in A. We consider the fact that these quantities are different as a type of interference of other types with the estimate of Π A⊕z : they are an undesirable part of the estimation.
The approach is to subtract from q z (N \ A) the total probability of the interfering types, i.e., those which rank z in the first j positions (and ahead of all of N \ A). Doing this type of estimation leads to an Inclusion-Exclusion formula.
Because each ranking that has z ahead of all of N \ A must have a (possibly empty) subset of A ahead of z, and z ahead of the remaining items, by also accounting for the rare rankings, we directly obtain the following lemma: Algorithm 1: The DAG Ranking Algorithm (AlgDAG(α, , δ)) Input: α: the fraction of positions to estimate, : desired bound on deviations in output estimates, δ: maximum allowed probability of large. deviations Output: a DAG (Ĝ F n 0 ,p(·)) estimating the top n 0 = αn items in the set of rankings Π F with their associated probabilities.
, andp(∅) = 1. Estimating the DAG level by level for j = 0, . . . , n 0 − 1 do for node (representing the set)Â on level j ofĜ F j do for each item z / ∈Â do Checking the existence of a prefix via AlgIE Setp(ΠÂ ⊕z ) ← AlgIE(Ĝ F j ,Â, z; α, , δ ) with = min( /n 0 , κ/4) and δ = δ Lemma 2. For any prefix A and z / ∈ A, we have The second term, i.e., A ⊂A p(Π A ⊕z ), corresponds to the interference probabilities from rankings that rank a strict subset of A ahead of z.
Lemma 2 is an implication of Lemma 1, which states that for A = A , the sets Π A⊕z and Π A ⊕z are disjoint. The most direct way to use Lemma 2 is to obtain estimates for the quantities q z (N \ A ) for all A ⊂ A. Then, Equation (5) (with interference terms for rare types removed) for all such A in place of A defines a set of linear equations. Solving this set of equations for the terms p(Π A ⊕z ) gives the desired quantity. The problem with this approach is that the linear system could be poorly conditioned. As a result, the coefficients multiplying the q z (N \ A ) terms in the expression for p(Π A⊕z ) could be exponentially large. We illustrate this problem with the following example.

A Better Inclusion-Exclusion Algorithm Based on Set Cover
In order to motivate our general Set Cover based approach, we begin by revisiting Example 1.
Example 2 (Revisiting Example 1). Inspecting Figure 3, we can observe that for levels above level 6, all types corresponding to edges labeled 7 out of blue nodes (which, recall, are interfering with the estimate of the probability of the edge Π {1,2,3,4,5,6}⊕7 ) prefer item 7 over at least one of items 5 and 6 (in addition to item 8). The respective probabilities of these two groups of types are q 7 ({6, 7, 8}) and q 7 ({5, 7, 8}). Simply adding these two probabilities would double-count those types which prefer 7 over both 5 and 6 (in addition to 8), but we can correct this by subtracting out the probability of such types, which is q 7 ({5, 6, 7, 8}). In summary, focusing on complements of sets as we have so far, we observe that The DAG corresponding to the set of rankings in Example 1. Here, the rankings corresponding to the blue nodes interfere when we want to estimate the probability of the ranking corresponding to the purple node and edge. That is, the blue nodes represent prefix A ⊂ A = {1, 2, 3, 4, 5, 6} in Lemma 2.
In the example, notice that the sets S = {1, 2, 3, 4, 5}, S = {1, 2, 3, 4, 6} jointly cover all blue sets that are subsets of the (purple) set {1, 2, 3, 4, 5, 6}, in the sense that each such set is fully contained in one of S , S . Furthermore, both S , S are contained in {1, 2, 3, 4, 5, 6}. It turns out that such set covers are sufficient to obtain an Inclusion-Exclusion characterization in which all coefficients are ±1, as captured by the following lemma. In order to express the lemma, and our subsequent analysis, cleanly, we define Φ − (A) = {A \ {x} | x ∈ A} to be the collection of all subsets of A obtained by removing exactly one element of A.
Lemma 3. Let A be a set of size j = |A|, and z / ∈ A. Recall that is the set of all frequent prefixes A in A F ≤j that are a proper subset of A and such that A ∪ {z} is also a prefix of a frequent type. Let C ⊆ Φ − (A) be a set cover of Φ Pre,F (A, z), using only sets from Φ − (A), in the sense that for each A ∈ Φ Pre,F (A, z), there is a set C ∈ C with A ⊆ C. Then, Lemma 3 is proved in Appendix 11. The high-level idea is to consider, for each set C in the set cover, the types that rank z before the complement of C. The probability of the union of all these sets of types is the alternating sum by the standard inclusion-exclusion formula, and we can upper-and lower-bound the union by the terms on the right and left, respectively.
We now discuss the implication of this lemma on our estimation procedure. By Equation (5), we can express the probability of Π A⊕z as p(Π A⊕z ) = q z (N \ A) − A ⊂A p(Π A ⊕z ). Our algorithm estimates the interference term A ⊂A p(Π A ⊕z ) by the inclusion-exclusion formula in the middle of Equation (7). The estimation error is then the difference between the right-hand side and the middle term of Equation (7). Lemma 3 allows us to upperbound this error by the difference between the right-hand side and the left-hand side of the equation. This difference can be written as a sum of terms only over rare types, and will be upper-bounded by ρ.
Putting these together and considering the middle term of Lemma 3, to estimate the probability of Π A⊕z with small error amplification, we find a set cover of the corresponding Φ Pre,F (A, z) using strict subsets of A. Since the middle term of Equation (7) comprises a number of terms 6 exponential in |C|, it is desirable to make this set cover as small as possible. Unfortunately, the Set Cover problem is well known to be NP-hard, so minimizing |C| exactly is unlikely to be possible in polynomial time (and our version subsumes the general version, as we show below). Instead, we use the greedy algorithm, which is known (see, e.g., (Kleinberg and Tardos 2006)) to offer an approximation guarantee logarithmic in the number of items -see Section 6.2.1. Combining these ideas, we obtain the improved Set Cover based Inclusion-Exclusion Algorithm, AlgIE (Algorithm 2). 7 Recall that this algorithm is used in AlgDAG as a way to obtain improved probability estimates. Moreover, the number of samples required by AlgIE depends on the size of the set covers found in the algorithm; hence, if all set covers encountered when AlgIE is called by AlgDAG are small enough, the number of samples needed is small.

Set Cover and the Greedy Algorithm
The minimum set covering problem we define is equivalent to the classic Set Cover problem. In the problem, a universe U = {1, 2, . . . , n} is given along with a collection L of m sets whose union covers U . The goal is to find the smallest subcollection of L whose union still covers U .
In our case, the universe is Φ Pre,F (A, z) because as we see in Lemma 2, we want to find a set cover of Φ Pre,F (A, z). Since every element of Φ Pre,F (A, z) is a proper subset of A, for each element A ∈ Φ Pre,F (A, z), there always exists x such that x ∈ A \ A and A ⊆ A \ {x}. We remark that the reduction also works in the other direction: every Set Cover instance can be encoded in our setting. Given an instance (U, L), we let j = |L| be the number of sets, and set A = {1, 2, . . . , j}. Then, for each element u ∈ U , let T u be the indices of sets S i ∈ L such that u ∈ S i . We define a corresponding prefix A u = A \ T u . Because T u = ∅ for all u (otherwise, u could never be covered), all A u are strict subsets of A. Furthermore, A u ⊆ A \ {x} for exactly those x such that u ∈ S x ; thus, the instance we generated exactly encodes the original Set Cover instance.
Algorithm 2: The Set Cover based Inclusion-Exclusion Algorithm (AlgIE(Ĝ F j , A, z; α, , δ)) Input:Ĝ F j : the inferred DAG representing the j most preferred items in frequent rankings, A: the current node/set considered, z: the item currently considered, α: the fraction of positions the algorithm aims to estimate, : desired bound on deviations in output estimates, δ: maximum allowed probability of large deviations in output estimates. Output: an estimated total probabilityp(Π A⊕z ) of Π A⊕z .
The preceding reduction from Set Cover to our problem shows that both the NPhardness and approximation hardness to within better than (1 − o(1)) · ln n (Feige (1998)) carry over to our problem. On the positive side, the reduction from our problem to Set Cover shows that approximation algorithms for the latter can be applied to our problem with the same guarantees. In particular, this applies to the well known greedy approximation algorithm (see, e.g., (Kleinberg and Tardos 2006)), which has a multiplicative approximation guarantee of ln n. 8 The greedy algorithm for Set Cover, denoted by greedymincover (U, L), repeatedly adds a set L ∈ L which covers the largest number of elements from U which had not been covered by previously added sets. It terminates when all of U is covered. Specialized to our setting, the greedy algorithm greedymincover Φ Pre,F (A, z), Φ − (A, z) repeatedly selects a set from Φ − (A) that contains as subsets the largest number of prefixes A ∈ Φ Pre,F not contained in any selected set so far. The algorithm terminates when all prefixes in Φ Pre,F have been covered.

Guarantees for AlgDAG
The key guarantees for AlgDAG (Algorithm 1) are summarized by the following theorem, which we prove in Section 8.
Theorem 2 (Performance Guarantee of AlgDAG). Let n 0 = αn for some constant α ∈ (0, 1), and assume that the total probability of the rare rankings is at most ρ < κ/4. Under the (κ, ρ)-General Model, Algorithm 1 (run with parameters > 0 and δ ∈ (0, 1)) returns an estimated choice model (Ĝ F n 0 ,p(·)), such that with probability at least 1 − δ, Furthermore, under the (κ, ρ)-Random Model, writing ν = log α (1/2) > 0, with probability at least 1 − 2δ, the total number of queries and the total computation time are bounded by We highlight that our algorithm works for both the General and Random Models. However, the size of all set covers is guaranteed to be logarithmically small only for the Random Model (with high probability) -this results in a polynomial total number of samples in that case. Nevertheless, even for the General Model, if the size of all set covers is small, the required number of samples is also small. Furthermore, notice that in AlgIE, after finding the approximate minimum set cover, the algorithm knows the size of the set cover. Therefore, AlgIE (and consequently also AlgDAG) can easily diagnose when a larger number of samples is needed to obtain good accuracy; alternatively, the algorithm can use a theoretically insufficient number of samples and return the result with some confidence interval around the probability of each node. Note that the number of samples used in AlgIE can change adaptively based on the size of the set cover for a given node. 9 , we fix the number of samples in advance for practicality. In this way, AlgIE can trade off the number of samples with accuracy.

Experiments
We evaluate the performance of AlgDAG empirically on both synthetic and real-world data sets. We compare the true DAG representation of the choice model with the DAG produced by AlgDAG for various values of n 0 (the number of top positions to estimate). We consider two metrics to measure the performance of AlgDAG. The first one is the number of nodes in the DAG that are added wrongly (false positive) or not inferred (false negative). The second one is the maximum probability discrepancy/difference between the true DAG and the inferred DAG.
Our goal is to investigate the benefit of actively learning the choice model, compared to learning the best choice model given the available transaction data, as previously done in Farias et al. (2013), van Ryzin andVulcano (2015), and van Ryzin and Vulcano (2017). Our experiments show that, in addition to being easy to implement, AlgDAG can recover the true DAG accurately (low estimation errors) with high probability using a reasonable number of samples. They further show that actively learning the choice model gives better performance empirically than learning the model directly from predetermined/given transaction data. Finally, we note that the number of samples needed in our experiments is much smaller than the theoretical value for a given set of accuracy parameters, highlighting the effectiveness of our designed algorithm.

Settings
We consider two settings, a synthetic setting and a real-world setting. For the latter, we use a sushi preference data set (Kamishima et al. (2005)).
Synthetic setting. We generate choice models as follows. We consider 5 frequent types and 8 items. (In Appendix 14, we also consider a larger number of types and items to observe how AlgDAG performs when the instance gets bigger.) The total probability of noise, which is ρ, is then chosen from {0, 0.001, 0.01, 0.05}. When ρ is 0, there are no noisy types; when ρ is either 0.001, 0.01 or 0.05, there are 20 noisy types. 10 For each of the frequent and noisy types, a ranking over the n items is chosen uniformly at random. The probability of the frequent types is drawn from a symmetric Dirichlet distribution whose coefficient of variation is 0.1, 11 multiplied by (1−ρ). When ρ > 0, the probability of the noisy types is distributed as a symmetric Dirichlet distribution whose coefficient of variation is 0.1, multiplied by ρ. For 10 Separate experiments have shown that changing the number of rare types does not impact our results given a fixed ρ. 11 A k-dimensional Dirichlet distribution β with parameters α 1 , . . . , α k has coefficient of variation k−1 kα+1 when α 1 = α 2 = · · · = α k = α.
Real-world setting. For the real-world setting, we evaluate the performance of AlgDAG on the sushi data set (Kamishima et al. (2005)). This publicly available data set describes preferences over 10 popular types of sushi based on a consumer survey that involved 5000 people specifying their exact ranking of those 10 types of sushi. In the sushi data set, unlike the data one would acquire in an active learning manner, a user declares his/her entire ranking over the 10 types of sushi, whereas from transaction data, we only get to see the most popular sushi among those offered.
In the sushi dataset, there are 4926 distinct rankings over the 10 types of sushi. Taking κ = 0.0001, there are 90, 561, 1800, and 3273 frequent prefixes for the top n 0 = 2, 3, 4 and 5 items, respectively, all with zero noise probability, i.e. ρ = 0. 12 In our experiments, we aim to only learn the top 2, 3, 4, and 5 items because the benchmark algorithm (we elaborate on this more in the next section) is computationally inefficient when estimating more than 5 top items. Observe that in this setup, there are a lot more distinct types and prefixes compared to the synthetic setting. This causes a lot more interference, which makes it harder for AlgDAG to estimate each node properly. Furthermore, the set of rankings in the sushi data is obviously not generated i.i.d. uniformly at random. We finally note that we use the empirical frequency of each prefix in the data set as our ground truth, so for each n 0 ∈ {2, 3, . . . , 5}, we get the set of types of size n 0 with its corresponding probability distribution.

Benchmark
As our benchmark, we implemented the primal linear program (LP) from Farias et al. (2013) to find the set of types. Farias et al. (2013) summarize the given transaction data in an mdimensional vector y = Aλ, where A ∈ {0, 1} m×n! represents the relationship between the observed data (y) and the choice model. 13 Here, the choice model is represented by the vector λ, which is the variable representing the probability distribution over all possible types of preferences. Unlike AlgDAG, which builds the DAG level by level by using active learning, this method determines the distribution over the whole ranking (containing n items) using an offline data set. That is, in our synthetic setting, for a given offline data set, it returns 12 Increasing the threshold κ for frequent types causes the total probability of noise to be much larger than κ; hence we choose κ = 0.0001 to be our threshold. For instance, when κ = 0.0002, we have ρ = 0.4754, which is more than 2000 times the threshold for frequent types.
13 Specifically, the i-th element of y, which is associated with a set S and an item z, represents the fraction of consumers who choose an item z given assortment S. Then, the element in the i-th row and j-th column of matrix A, where i-th row is associated with a set S and an item z, is 1 if consumers with type j prefer z among all items in S, and 0 otherwise. a distribution over all possible 8! = 40320 candidate rankings. In the sushi setting, since we only run the benchmark algorithm to estimate the top 5 items, we limit our type space to only consist of the set of all possible rankings of five items; in this case, the benchmark returns a distribution over all 5!· 11 5 = 55440 possible top 5 items in the sushi setting. Thus, in the sushi data set, we use a smaller search space for the types instead of searching over all 11! = 39, 916, 800 rankings since AlgDAG also only estimates up to the top 5 items. This is beneficial for the calculation complexity for the benchmark since it reduces the number of decision variables in the LP. 14 For both the sushi and synthetic data sets, we do the following for the benchmark: (1) solve the primal LP fully (without constraint sampling) using the Gurobi solver, instead of solving the dual approximately (as done in Farias et al. (2013)), and (2) impose sparsity on λ, the probability distribution of types. These give the primal LP algorithm an extra benefit, since solving the primal fully permits searching over a bigger space, and the sparsity constraint helps the LP to deal with the indistinguishability problem. Furthermore, we relax the LP constraint to overcome infeasibility, by incorporating 1/ √ m standard error for the empirically calculated probability that each item in the assortment is chosen, where m is the number of samples used per offered assortment in AlgDAG and the benchmark. So instead of having the constraint y = Aλ, we haveŷ − 1/ √ m · 1 ≤ Aλ ≤ŷ + 1/ √ m · 1. We do so because the primal LP often does not yield any solutions when we use the constraintŷ = Aλ whereŷ is empirically calculated using the same number of samples as AlgDAG. 15 To evaluate the benchmark, two types of offline transaction data sets are generated for the synthetic setting. In the first data set, we intuitively want to replicate the common stockout cases in the real world. A lot of work has also investigated the effect of stockouts on demand and revenue (Caine andPlaut (1976), Fitzsimons (2000), Kim and Lennon (2011)). To do so, we assume that 3 out of n items are not available and the consumers can only see the remaining (n − 3) items. There are n 3 distinct assortments generated, where each distinct assortment is shown to m consumers. When the number of items is 8, this results in 56 distinct assortments. Another set of offline transaction data that we use is pairwise comparison data (assortments consisting of every distinct pair of items) that represents the fraction of consumers that prefer z to z for every pair of distinct items (z, z ), as seen in (Farias et al. 2013). There are n 2 distinct assortments in this case, when there are 8 items, the number of distinct assortments is 28. In comparison, when we run AlgDAG on synthetic dataset, we observe that AlgDAG only uses at most 20 16 distinct assortments even when n 0 = 5. This shows that the number of distinct queries that AlgDAG uses is quite small, even smaller than that in offline data sets. But, since the queries are selected carefully through an active learning procedure, as we will show later, AlgDAG significantly outperforms the benchmark.
In the sushi setting, similarly, we generate two types of offline transaction data, the set of assortments that have 3 stockout (their size is 11 − 3 = 8) and the set of pairwise assortments. When we use the pairwise assortments, the linear programs are often not solved to completion due to the linear system being undetermined. This was not an issue for the synthetic dataset because we have fewer types (at most 35 distinct rankings), while there are 4926 distinct rankings in the sushi data. Hence, for the sushi dataset, we only present the results for the set of offline assortments with 3 stockout, to give extra benefit to the offline benchmark. Nonetheless, as we will show later, even in the synthetic data, the performance of the benchmark was worse on the pairwise data set, compared with that on the 3-stockout data set.

AlgDAG Implementation
In the synthetic setting, we want to estimate the top n 0 = 3, 5 positions when the number of items is 8, while in the sushi setting, we want to estimate the top n 0 = 2, 3, 4, 5 positions. In the synthetic data set, we consider as frequent the types whose probability is at least κ = 0.01; this is a consequence of our choice of Dirichlet parameters for the probability distribution of the frequent types in the synthetic setting. 17 Meanwhile, in the sushi setting, we choose κ = 0.0001 by looking at the smallest type probability in the ranking. Note that in our experiment, we do not always have ρ < κ/4 for our chosen ρ ∈ {0, 0.001, 0.01, 0.05}. While this assumption is required for our theoretical guarantee in Theorem 2, by violating it, we can observe how robust AlgDAG is. We set our accuracy parameters to be = 0.001 for the synthetic setting and = 1e − 5 in the sushi setting. Here, is very small for the sushi data because as we explain above, we choose the threshold κ to be 0.0001 and we want to have κ as the accuracy parameter. We further set δ = 0.05, meaning that we want each node's estimate to be within of its true probability, with probability at least 95%.
In simulating active learning, given a set of (true) synthetic parameters, one consumer is drawn in each round and the item she chooses based on her preference is observed. The algorithm gets to decide which assortment is offered for each consumer. Although the number of samples to use is specified in AlgIE (which in turn is called by AlgDAG), for practicality, we limit the number of samples for each AlgIE run to be at most 10k, i.e., m ≤ 10k. This allows us to see how AlgDAG and AlgIE perform with a small number of samples (smaller than required for the theoretical guarantees). The experiment is run 100 times for each value of n 0 .

Synthetic Data Set.
We present our results in Tables 1 and 2. First, in Table 1, we look at the maximum probability discrepancy out of all nodes between the DAG returned by the algorithm and the true DAG. We see that AlgDAG outperforms the benchmark for both offline data sources: the 3 stockout and pairwise data. In general, the results for both algorithms (AlgDAG and the benchmark) get worse when the noise probability increases. Further, if we look closely at Table 1, we see that the maximum probability discrepancy for the DAG returned by AlgDAG, which is attained when the noise probability is the largest, i.e., 0.05, is at most 0.00892 on average (when n 0 = 5). Moreover, the maximum noise discrepancy is larger for n 0 = 5 than for n 0 = 3. This shows that as the number of top items being inferred increases, the problem becomes harder. This is similar to the behavior predicted by Theorem 2, where more samples are needed to obtain the same level of accuracy. Among the benchmarks with two different data sources, the benchmark with 3 stockout offline data set far outperforms the benchmark with pairwise data set. The former has more variation in the transaction data with 56 distinct assortments, therefore containing more information.
In Table 2, we look at the percentage of vertices that are added wrongly or not inferred, i.e., the number of vertices that appear only once (either in the true DAG or in the DAG returned by AlgDAG, but not in both) on level n 0 , as a percentage of the number of vertices   on level n 0 in the true DAG formed by the frequent types. Compared with the benchmark, AlgDAG produces fewer vertices that are being added wrongly or not inferred compared to the benchmark, with both data sources. 18 For example, when n 0 = 5 and the noise level is 0.001, while the percentage of different vertices is 5.04% in AlgDAG, it is 41.01% for the benchmark with 3 stockout data and 45.25% for the benchmark with pairwise data. Further, as before, the benchmark with 3 stockout data outperforms the one with pairwise data due to the existence of more variation in the data. As expected, for both AlgDAG and the benchmark, the percentage of different vertices gets bigger as the total noise probability increases.
0  Table 3: The maximum probability discrepancy, over all nodes, between the DAG returned by AlgDAG or the benchmark and the true DAG, and the percentage of vertices that are added wrongly or not inferred by AlgDAG or the benchmark, averaged over 100 instances run on the sushi data.
We summarize our results on the sushi data set in Table 3. There, we show the maximum probability differences and the percentages of different vertices between the DAG returned by AlgDAG and the true DAG, averaged over 100 runs. AlgDAG far outperforms the benchmark in both metrics. Specifically, AlgDAG returns node probabilities within 0.0765 of the actual probability on average when we look at the fifth level (i.e., n 0 = 5), compared to 0.0950 for the benchmark. Similarly, when we look at the number of vertices that are either added wrongly or not inferred, on average, the percentage for AlgDAG is nine times smaller than for the benchmark, for n 0 = 5. These results are surprising since we are only using m = 10k; they indicate that even with such a small number of samples (far smaller than what is needed in the theoretical guarantee), AlgDAG can estimate the true distribution of types with good accuracy in the sushi data. Note that this holds even though the types are not drawn i.i.d. uniformly at random for the sushi data.

Concluding Remarks for Experiments.
Overall, we observe that the performance of both algorithms, AlgDAG and the offline benchmark, get worse as the total probability of noise (i.e., ρ) gets larger or the fraction of items being estimated (i.e., n 0 ) gets bigger. Furthermore, the experiments show that AlgDAG can get a small probability discrepancy and few "wrong" vertices even with a small number of samples (m = 10k), which is far smaller than the theoretical number needed to get such a guarantee. When the number of types increases, the performance gets worse but is still comparable, which can be seen in the results for the sushi data set (Section 7.4.2) and the bigger synthentic dataset with 15 frequent types and 20 items (Appendix 14). AlgDAG also performs well when the number of items is larger than the number of types, as is the case, for example, in the sushi data; this is true as long as there are not too many types with similar preferences causing a lot of interference when AlgDAG is run. Additional experiments with m = 50k -not shown here -show that the maximum probability discrepancy and the number of different vertices go down to 0 as the number of samples increases; they are close to 0 when we increase m to 50k. In all scenarios, AlgDAG outperforms the benchmark despite using a small number of distinct queries.

Proof of Theorem 2
In this section, we give a proof of Theorem 2, with the proofs of two technical lemmas deferred to the appendix.
The main part of the analysis is captured by Lemma 5, which will be stated later in this section. This lemma shows that under the general model, the estimatesp(Π A⊕z ), which AlgIE obtains of the true probabilities p(Π A⊕z ), are accurate enough with sufficiently high probability. The lemma further bounds the number of queries required under the (κ, ρ)-Random Model. The number of queries required increases exponentially in the size of the set covers used, so to bound the former, we would like to bound the latter. We observe that certain configurations of types could possibly cause a need for large set covers. Therefore, we first show that under the (κ, ρ)-Random Model, these configurations are sufficiently unlikely to occur.
More formally, for any positive integer c ∈ [n − 1], we define E c to be the event that there are two distinct types π 1 = π 2 ∈ Π F , a position j ≤ n 0 , and an item z in position j + 1 of ranking π 1 , such that • z is in position c + 1 or later in π 2 , and • the set of items preceding z in π 2 is a subset of the first j items in π 1 .
Lemma 4 shows that E c is unlikely to occur. Because E c can never happen for c > n, Lemma 4 is of interest only in the regime when log 1/α K 2 n δ ≤ n, or K ≤ (1/α) n δ n . Otherwise, the lemma is trivial since the probability of the event E c is 0.
Next, we show that having computed the graph correctly up to the previous level is enough to ensure that AlgIE returns accurate estimates with high probability -this forms the key of the inductive correctness proof of AlgDAG. Furthermore, when E c happens, all the set cover solutions in AlgIE are small enough that the number of samples stays polynomial.
Lemma 5. Let j ∈ {0, 1, . . . , n 0 − 1} be a level, and assume thatĜ F j = G F j . Then, the estimated probabilityp(Π A⊕z ) returned by AlgIE (Algorithm 2), called with parameters and δ, satisfies with probability at least 1 − δ. Furthermore, if E c did not happen, then the number of consumer queries and the total computation time are upper-bounded by O 2 2c (c+log(1/δ)) 2 .
We are now ready to show Theorem 2. We will prove by induction on the level j that with probability at least (1 − δ 2n 0 ) j , The first part of the theorem then follows by setting j = n 0 = αn, and noting that (1 − δ 2n 0 ) n 0 ≥ 1 − δ 2 .
We now complete the induction proof. The base case j = 0 holds becauseĜ F 0 = {∅} = G F 0 holds deterministically. For the induction step, by induction hypothesis,Ĝ F j = G F j with probability at least (1 − δ 2n 0 ) j (and the estimates up to level j are accurate to within an additive + n 0 ρ). We condition on this case.
To obtainĜ F j+1 fromĜ F j , Algorithm 1 goes through each nodeÂ on level j ofĜ F j and all candidate items z / ∈Â, and uses AlgIE to compute an estimatep(ΠÂ ⊕z ) of the true value p(ΠÂ ⊕z ). BecauseĜ F j = G F j , Lemma 5 implies that for each of its calls (characterized by the choice of z), AlgIE returns a probabilityp(ΠÂ ⊕z ) that is at most + A ∈Φ Pre,R (A,z) p(Π A ⊕z ) = min( /n 0 , κ/4) + A ∈Φ Pre,R (A,z) p(Π A ⊕z ) =: z far from the true value p(ΠÂ ⊕z ), with probability at least 1 − δ = 1 − δ 2αn 2 K . Note that by Lemma 1, z ≤ κ/4 + ρ. (Note that AlgDAG calls AlgIE with parameters and δ .) Because there are at most K frequent types, and the nodes on level j ofĜ F j correspond to disjoint sets of types, there are at most K nodes on level j. For each such node, the algorithm checks at most n items z to add. By a union bound over all of the invocations of AlgIE for these different pairs (Â, z), all estimates of p(ΠÂ ⊕z ) are simultaneously accurate to within an additive z with probability at least Under the assumptions of the theorem, z ≤ κ/4 + ρ < κ/2. In particular, when the estimates are accurate to within z , rare rankings alone can never make the algorithm add a nodeÂ ∪ {z} to layer j + 1. Conversely, every frequent type has probability at least κ, so when the estimates are accurate to within z , every frequent type whose first j + 1 items arê A ∪ {z} has estimated frequency at least κ − z ≥ κ − (κ/4 + ρ) ≥ κ/2, hence causes the creation of the nodeÂ ∪ {z}. Thus, we have shown thatĜ F j+1 = G F j+1 whenever all estimates are accurate to within z .
To bound the error in the estimated probabilities, consider a node A ∈ V F j+1 . The true combined probability of types who rank all of A ahead of all items not in A is p(A) = z∈A p(Π (A\{z})⊕z ). AlgDAG, on the other hand, uses estimated probabilitiesp(Π (A\{z})⊕z ) in place of the true probabilities, and furthermore only adds these estimates for elements z such that the set A \ {z} ∈ V F j is a frequent type, i.e., it usesp(A) = z∈A:A\{z}∈V F jp (Π (A\{z})⊕z ). Using the triangle inequality along with the upper bound on individual estimation errors z we obtained above, and the fact that |A| ≤ n 0 , we get that the error is at most (9) The inequality on the third line used the upper bound on the error term z derived above. The inequality on the fourth line holds because 1) A has at most n 0 terms so z∈A:A\{z}∈V F j min( /n 0 , κ/4) ≤ n 0 · n 0 , and 2) if z ∈ A and A \ {z} / ∈ V F j , yet the probability of Π (A\{z})⊕z is greater than 0, then A = A \ {z} must be in Φ Pre,R (A, z) by definition. Hence Furthermore, the penultimate step in Equation (9) upper-bounds the last sum (which runs only over subsets of size |A| − 1) by one running over all subsets. Finally, in the last step of Equation (9), we used Lemma 1 to bound the inner sum by ρ, then used that |A| ≤ n 0 . Finally, by induction hypothesis, the event we conditioned on (thatĜ F j = G F j and the estimates up to level j are accurate to within an additive + n 0 ρ) had probability at least (1 − δ 2n 0 ) j , and conditioned on this event, level j + 1 is correct (and accurate to within + n 0 ρ) with probability at least (1 − δ 2n 0 ). Hence, the entire inferred graph up to level j + 1 is accurate with probability at least (1 − δ 2n 0 ) j+1 , completing the induction step, and thus the proof of the first part of the theorem.
We now prove the second part of the theorem, bounding the number of queries and the computation time under the random model. With a slight abuse of notation, define c = log 1/α K 2 n δ . By Lemma 4, with probability at least 1 − δ, the event E c did not happen. By a union bound with the first part of the proof, we obtain that with probability at least 1−2δ, G F n 0 is correctly reconstructed, all probability estimates are accurate to within an additive + n 0 ρ, and the event E c did not happen.
By the second part of Lemma 5, each invocation of AlgIE results in O K 4ν ·n 2ν ·log(nK/δ) δ 2ν ·min( ,κ) 2 consumer queries and computation. Each frequent type contributes at most one distinct node A ∈ A j for each level j, and for each such node A, AlgDAG considers all items z / ∈ A for addition, and calls AlgIE. Thus, the total number of calls to AlgIE is at most Knn 0 . Substituting, bounding that n 0 ≤ n, and writing the constant ν = log α (1/2) > 0, we obtain that the number of consumer queries is at most which is polynomial. Since the computation is dominated by the queries, the same bound applies to the computation time.

Conclusion, Discussions, and Future Directions
Non-parametric choice models, despite their ability to capture general choice models, are difficult to estimate using only offline transaction data. This is primarily due to the lack of variation in the data. In many settings, especially on online platforms, one can influence the process of acquiring data based on past observations; this is also known as an active learning process. Motivated by this, we studied the problem of estimating a non-parametric choice model using active learning. In addition to product ranking, non-parametric choice models have also been used in other applications, such as a non-parametric joint assortment and price choice model with consideration set (Jagabathula and Rusmevichientong (2017)) and non-parametric demand for dynamic pricing (Perakis and Singhvi (2019)). It would be interesting to see how an active learning approach applies to those problems in future work. We present a negative result showing that such non-parametric choice models might be indistinguishable regardless of the sequence of assortments offered in the active learning process. To overcome this, we present a directed acyclic graph (DAG) representation of the choice model that captures as much as can be uniquely identified about the distribution when the types of consumers are unobservable and each consumer only makes one choice. We then design an efficient algorithm to accurately estimate the DAG representation of non-parametric choice models using a polynomial-sized data set. The algorithm learns the distribution over the most popular items and their corresponding probabilities by actively choosing assortments to offer the next arriving consumer based on past observations. The algorithm employs an inclusion-exclusion method to better estimate each ranking probability. We also show that our algorithm outperforms a non-active learning algorithm on synthetic and real-world (sushi) data sets.
Our work raises several immediate questions for technical follow-up work. First, the factor n 0 in the error bound of Theorem 2 seems like it could perhaps be avoided. Notice, however, that rare types could indeed impact the estimate of p(Π A ⊕z ) for multiple A , for instance those rare types that rank z first (or early). Similarly, while for most practical applications, it suffices to learn the first n 0 = αn items of each ranking, from a theory perspective, it would be interesting to understand whether learning the entire rankings is possible. To learn about the last few items in rankings, it is necessary to offer small sets to consumers, but if types are sufficiently frequent, it may be possible to obtain data on those items. However, the approach based on Set Cover is unlikely to succeed: when n 0 is large, it is indeed likely that the required set covers are large, and hence, the Inclusion-Exclusion formula requires exponentially many terms, and thus exponentially small error in each term to compensate.
Our polynomially small bounds on the required samples only applied under the (κ, ρ)-Random Model. It would be interesting to investigate whether small sample bounds can be obtained under a fully adversarial model. Some preliminary work suggests that this may be difficult. Yet, although there is no polynomial sample bound for the general model, AlgDAG still requires a small number of samples as long as the approximate solution to the Set Cover instance is small.
Experimentally, it would be desirable to evaluate the performance of our algorithms, as well as alternatives, on larger and richer data sets. Ultimately, the goal should be to deploy them in a real-world setting and have them interact with actual consumers. In such a setting, there may be other considerations, such as the cost of exploration (i.e., offering consumers sets of items that are ranked low by many types, to disambiguate the rankings). Many other practical concerns such as inventory constraints are likely to arise.
Fundamentally, we view our work as a first step towards a much more comprehensive evaluation of active learning in the context of choice models and related settings. Our work opens up new avenues for future work, and we hope that it will lead to studying the framework in other Operations Research problems, such as product ranking and assortment planning.
10 Appendix 11 Proof of Lemma 3 In this section, we prove Lemma 3, which is restated below.
Lemma 3. Let A be a set of size j = |A|, and z / ∈ A. Recall that is the set of all frequent prefixes A in A F ≤j that are a proper subset of A and such that A ∪ {z} is also a prefix of a frequent type. Let C ⊆ Φ − (A) be a set cover of Φ Pre,F (A, z), using only sets from Φ − (A), in the sense that for each A ∈ Φ Pre,F (A, z), there is a set C ∈ C with A ⊆ C. Then, Proof. For any non-empty subset B ⊆ C, we write This implies that S B∪B = S B ∪ S B . Because z / ∈ C for all C ∈ C (because C ⊆ Φ − (A), and z / ∈ A), we obtain that z ∈ S B . Recall that Θ z (S B ) is the set of types choosing z when offered S B z. A type π chooses z from C∈B (N \ C) if and only if π chooses z from N \ C for each C ∈ B. Therefore, Θ z (S B ) = C∈B Θ z (N \ C). Applying the standard Inclusion-Exclusion formula to the sets Θ z (N \ C), we obtain that where the last step used that q z (S) = p(Θ z (S)) for all sets S z. We now upper-and lower-bound the left-hand side p C∈C Θ z (N \ C) . For the upper bound, fix an arbitrary set C ∈ C, and consider a type π in Θ z (N \ C). Because π ranks z ahead of all of N \ C, there exists a set A ⊆ C such that π ranks all of A first (in some order), then z, and then all items not in A . This is exactly the definition of Π A ⊕z . Because each set C ⊂ A (because the set cover used only sets in Φ − (A)) and A ⊆ C, we have shown that C∈C Θ z (N \ C) ⊆ A ⊂A Π A ⊕z , and hence For the lower bound, consider a set A ∈ Φ Pre,F (A, z). Because C is a set cover of Φ Pre,F (A, z), there exists a set C ∈ C, C ⊇ A . Any type π ∈ Π A ⊕z ranks only A ahead of z. Because the assortment N \ C does not contain any items of A , but does contain z, the type π chooses z from N \ C. Thus, we have shown that Π A ⊕z ⊆ Θ z (N \ C). Since this holds for all A , we obtain that A ∈Φ Pre,F (A,z) p(Π A ⊕z ) ⊆ C∈C Θ z (N \ C), and hence Finally, by Lemma 1, the sets Π A ⊕z are pairwise disjoint, i.e., Π A ⊕z ∩ Π A ⊕z = ∅ for all completing the proof.

Proof of Lemma 4
In this section, we prove Lemma 4, which is restated below.
Proof. We want to bound the probability that there are two distinct types π 1 = π 2 ∈ Π F and a position j ≤ n 0 such that the item z which is in position j + 1 in π 1 is in position c + 1 or later in π 2 , and the set of items preceding z in π 2 is a subset of the first j items in π 1 .
For now, focus on two types and a fixed position j ≤ n 0 , with π 1 already drawn (and thus defining z), and the uniformly random draw defining π 2 . Let E c,k (for k ≥ c + 1) denote the event that z is in position k in π 2 , and the first k − 1 items of π 2 are all among the first j items of π 1 .
There are j k−1 ways to pick the first k −1 items of π 2 from the first j items of π 1 , (k −1)! ways to order them, and (n − k)! ways to order the items after position k. Since there are n! total rankings, the probability of E c,k is P[E c,k ] = j k−1 · (k − 1)! · (n − k)! n! = j! · (n − k)! (j + 1 − k)! · n! ≤ j! · (n − (c + 1))! (j − c)! · n! , where the inequality holds because the probability is monotone decreasing in k and thus maximized when k is as small as possible, i.e., k = c + 1. Next, we bound because (j − k)/(n − k) is monotone decreasing in k, so it is maximized at k = 0, and j ≤ n 0 . Now, taking a union bound over all choices of k = c + 1, . . . , j (of which there are at most n − c) as well as all choices of j ≤ n 0 ≤ n and ordered pairs of types (of which there are at most K(K − 1) ≤ K 2 ), we obtain the bound P[E c ] ≤ K 2 · n · (n − c) · 1 n − c · (n 0 /n) c = K 2 · n · α c .
Finally, substituting the lower bound on c, we obtain that P[E c ] ≤ K 2 · n · α c ≤ K 2 · n · δ K 2 · n = δ, completing the proof.

Proof of Lemma 5
In this section, we complete the proof of Lemma 5, which is restated below for convenience.
Furthermore, if E c did not happen, then the number of consumer queries and the total computation time are upper-bounded by O 2 2c (c+log(1/δ)) 2 .
Proof. Recall that AlgIE computes an approximately smallest set cover C of Φ Pre,F (A, z) using sets in Φ − (A); specifically, this means that C ⊆ Φ − (A) and that for each set A ∈ Φ Pre,F (A, z), there exists a set C ∈ C with A ⊆ C.
By Lemma 2, the true probability of having a prefix of A followed by z is so Lemma 3 implies that Thus, the absolute estimation error is where the first inequality is based on applying the triangle inequality first at the outer level, then pulling it through the sum.
There are 2 |C| − 1 sets S of the form S = C∈B C (one for each B ⊆ C, B = ∅), plus the set S = A. Hence, by a union bound over all such sets S, with probability at least 1 − 2 |C| · δ 2 |C| = 1 − δ, all of the estimates satisfy |q z (N \ S) −q z (N \ S)| ≤ 2 |C| . In that case, the total estimation error is at most = + A ∈Φ Pre,R (A,z) p(Π A ⊕z ).
Finally, we prove the second part of the lemma, i.e., the bound on the number of consumer queries (and hence computation, since the inclusion-exclusion computation dominates the computing time as well). We will show that whenever E c did not happen, |C| ≤ c. For contradiction, assume that |C| > c, i.e., the greedy min cover algorithm returned a solution of size at least c+1. Recall that the greedy algorithm selects subsets of the form A\{x} until all prefixes are covered. Notice that by the assumption of the lemma thatĜ F j = G F j , the set of prefixes that the greedy algorithm is trying to cover is exactly Φ Pre,F (A, z). Consider the moment when the greedy algorithm has selected c sets C i = A \ {x i } in its cover. At that point, there is still an uncovered set A ∈ Φ Pre,F (A, z), since the greedy algorithm added at least one more set. Because A is not contained in any of the C i , it must contain all of the elements x i ; in particular, it has size at least c. Furthermore, by definition of Φ Pre,F (A, z), A ⊆ A, and A is a prefix followed by z. Therefore, there exist a type π 1 which has all of A followed by z and a type π 2 which has all of A preceding z directly, where A ⊆ A and |A | ≥ c, implying that z is in position c + 1 or later in π 2 . This certifies that the event E c happened, which the assumption of the lemma ruled out. Substituting the bound |C| ≤ c into the definition of m gives us the claimed bound.

Additional Experimental Results
As a robustness check on the performance of AlgDAG, for the synthetic setting, we vary the number of types and the number of items. Specifically, we consider a setting with 15 frequent types and 20 items. The total probability ρ of noise is still chosen from the set {0, 0.001, 0.01, 0.05}, and 20 noisy types are generated when ρ is greater than 0. The probabilities of frequent and noisy types are generated as those for the first synthetic setting (see Section 7), i.e., according to a symmetric Dirichlet distribution with coefficient of variation 0.1, multiplied by (1 − ρ) and ρ, respectively. The goal is to estimate the top n 0 ∈ {5, 10} positions, and we choose κ and to be 0.01 and 0.001, respectively. Results are then averaged over 100 generated instances. Noise = 0 Noise = 0.001 Noise = 0.01 Noise = 0.05 n 0 = 5 n 0 = 10 n 0 = 5 n 0 = 10 n 0 = 5 n 0 = 10 n 0 = 5 n 0 = 10 max. prob. 0.0099± 0.0102± 0.0114± 0.0159± 0.0122± 0.0157± 0.0132± 0.  Table 4: The maximum probability discrepancy over all nodes, between the DAG returned by AlgDAG and the true DAG, and the percentage of vertices that are added wrongly or not inferred by AlgDAG, averaged over 100 instances run on synthetic data with 15 frequent types and 20 items.
The experimental results for this setting are summarized in Table 4. The maximum o probability discrepancy is 0.0160, which is obtained when the top 10 positions are being estimated. The value of this maximum probability discrepancy is comparable with that in the 5 frequent types setting. Similarly, the percentages of different vertices over different frequent cases are at most 9.98%, which is comparable with the result for the cases with 5 frequent types. The benchmark is not included in this setting because with a large number of items, the benchmark is computationally inefficient.