We assume a recommendation system is charged with the task of recommending an option to a user in a multi attribute space (e.g., computers, cars, apartment rental, etc.). Products are characterized by a finite set of attributes X = {X1, ...Xn}, each with finite domains Dom (Xi). Let X ⊆ Dom(X ) denote the set of feasible configurations. For instance, attributes may correspond to the features of various apartments, such as size, neighborhood, distance from public transportation, etc., with X defined either by constraints on attribute combinations (e.g., constraints on computer components that can be put together), or by an explicit database of feasible configurations (e.g., a rental database).

The user has a utility function u : Dom(X ) → R. In what follows we will assume either a linear or additive utility function depending on the nature of the attributes (Keeney and Raiffa 1976) . In both additive and linear models, we assume that u can be decomposed as follows: u(x) =

X fi(xi) =

X λivi(xi) i i where each local utility function fi assigns a value to each element of Dom(Xi). In classical utility elicitation, these values can be determined by assessing local value functions vi over Dom(Xi) that are normalized on the interval [0, 1], and importance weights λi (Pi λi = 1) for each attribute (Keeney and Raiffa 1976; Fishburn 1967) . This sets fi(xi) = λivi(xi) and ensures that global utility is normalized on the interval [0, 1]. A simple additive model in the rental domain might be:

u(Apt ) = f1(Size ) + f2(Distance) + f3(Nbrhd ) When Dom(Xi) is drawn from some real-valued set, we often assume that vi (hence fi) is linear in Xi.2

Since a user’s utility function is not generally known, we often write u(x; w) to emphasize the dependence of u on 2Our approach relies considerably on the additive assumption, though can easily be generalized to more general models such as GAI (Fishburn 1967; Bacchus and Grove 1995; Braziunas and Boutilier 2007a) . The assumption of linearity is simply a convenience; nothing critical depends on it. user-specific parameters. In the additive case, the values fi(xi) over ∪i{Dom(Xi)} serve as a sufficient parametrization of u (for linear attributes, a more succinct representation is possible). The optimal product for the user with utility parameters w is that x ∈ X that maximizes u(x; w). Our goal is to recommend, or help the user find, an optimal product, or one whose utility is near optimal.

In probabilistic approaches to recommendation, a distribution over preferences—typically in the form a density over utility function parameters—is maintained, and the option with highest expected utility is recommended (Chajewska et al. 2000; Boutilier 2002; Boutilier et al. 2003) . When a set of alternatives need to be recommended, the expectimax or EMAX criterion can be used (Boutilier et al. 2003; Price and Messinger 2005) . One difficulty with probabilistic models is that one requires probabilistic prior information over utility models, which can be difficult to formulate and represent. Another is that exact computation can often be computationally intense; this is especially true since (arguably) natural density models for utility functions are rarely closed under the type of evidence provided by user interaction (e.g., behavioral observation or answers to queries) (Boutilier 2002; Chajewska and Koller 2000) ); as a result, computationally demanding fitting of (say) mixture models is required after every model update.

Instead, we propose the use of minimax regret to generate recommendation sets. As we will see, this obviates the need to complex probabilistic reasoning, yet can offer robust recommendations and provide very effective guidance for the user. In traditional regret-based approaches, a single recommendation is made using the minimax regret (Savage 1954) criterion. For multiple joint recommendations, we develop the notion of setwise minimax regret (defined below). We can summarize the correspondence between the Bayesian and the regret-based approach with the following table: Probabilistic approach

Expected Utility Expected Max (EMAX) Regret approach

Minimax Regret

Minimax Setwise Regret

In this paper we propose a framework that maintains a set W of feasible utility models, and at each step, the system shows a set of recommendations that are jointly optimal with respect to minimax regret. At a very high level, our regretbased recommender works as follows: 1. The set W is initialized given some initial constraints; 2. The current recommendations are determined (using the setwise minimax regret); 3. After each user action, W is refined to reflect the new constraints imposed by the user’s feedback; 4. The process repeats (steps 2 and 3) until the user is satisfied or minimax regret reaches some target threshold. This process is appealing for two reasons. First, the current recommendation (i.e., set of options) is always optimal; in other words, it minimizes setwise max regret given the current information about the user’s utility function, making it extremely robust in the presence of utility function uncertainty (in a way to be made precise below). Second, max regret is a well-defined progress metric that lets the user know the cost and benefit of further exploration of product space. Finally, the information contained in user selection of some choice from the recommended set is maximally informative (in a sense defined below).

Minimax regret has been advocated as a means for robust optimization (Kouvelis and Yu 1997) , and has more recently been used for decision making with utility uncertainty (Boutilier et al. 2001; Salo and Ha¨ma¨la¨inen 2001; Boutilier et al. 2006a) .

Assume that through some interactions with a user, and possibly using some prior knowledge, we determine that her utility function w lies in some set W . Following (Boutilier et al. 2006a) we define: Definition 1 Given a set of feasible utility functions W , we define the pairwise max regret MR(x, y; W ) of x, y ∈ X; the the max regret MR(x; W ) of x ∈ X; the minimax regret MMR(W ) of W ; and the minimax optimal configuration x∗W as follows:

MR(x, y; W ) = max u(y; w) − u(x; w)

w∈W MR(x; W ) = max MR(x, y; W )

y∈X MMR(W ) = min MR(x, W )

x∈X x∗W = arg min MR(x, W ) x∈X (1) (2) (3) (4) Intuitively, MR(x; W ) is the worst-case loss associated with recommending configuration x; i.e., by assuming an adversary will choose the user’s utility function w from W to maximize the difference in utility between the optimal configuration (under w) and x. The minimax optimal configuration x∗W minimizes this potential loss. MR(x, W ) bounds the loss associated with x, and is zero iff x is optimal for all w ∈ W . Any choice that is not minimax optimal has strictly greater loss than x∗W for some w ∈ W .

Minimax regret has proven to be an effective tool in utility elicitation in a variety of domains. A decision support or recommender system can query (or otherwise interact with) a user providing additional constraints on the utility set W until minimax regret reaches some acceptable level (possibly optimality), elicitation costs become too high, or some other termination criterion is met.

Example Consider the following example, where the options oi are defined using two features/coordinates x1 and x2: o1 o2 o3 o4 o5 0.9 0.8

We assume linear utility: u(x; w) = w1x1 + w2x2 where w is vector of tradeoff weights, with w2 = 1−w1, 0 ≤ w1 ≤ 1; and the local value functions for each coordinate are identity functions. (i.e., vi(xi) = xi). Given these assumptions, utility is one-dimensional; it can be written as u(x; w) = (x1 − x2)w1 + x2. So we deal only with the uncertainty on the single parameter w1.

This simple example is convenient because it is easy to visualize option utilities as a 1D function of w1 graphically. The utility of the different options are shown in Fig. 1 with respect to the parameter w1. We notice that, for some values of w1, each of the options o1, o2, o3 and o4 is optimal, but not so o5. When considering a particular value of w1 (a particular utility function) the actual regret (or real loss) is the difference between the utility of the best option given w1 and the utility of our recommendation in that case. For instance, for w1 = 0.9, the best option is o4 with utility 0.9, while o1 has utility 0.38, so the actual regret of o1 would be 0.9 − 0.38 = 0.52. Max regret accounts for the uncertainty over w1 and it is the maximum of the possible actual regret values (for o1 is 0.65 when w1 = 1).

When the options are few as in this case, we can compute the max regret of each choice by explicitly enumerating the maximum the pairwise regret of that choice against any possible adversarial choice of option. The table below illustrates this, where each row corresponds to a recommendation, each column to an adversarial choice, and we display the pairwise max regret (allowing the adversary to choose utility) in the cells. The max regret of an option is shown in the last column, and corresponds to the maximum value in its row. In the unconstrained situation (where w1 can take any value between 0 and 1), we have the following values:

Minimax regret is 0.5, and the minimax optimal recommendation is option o5; its max regret occurs at adversarial choice of utility w1 = 1, and choice of option o4. It can be easily shown that regret is maximized at one of the vertexes of the feasible region W when W is a bounded, convex polytope (such a polytope induced by the interactions we discuss later).

Now imagine that, perhaps as the result of interactions with the user, we learn that 0.2 ≤ w1 ≤ 0.6. The new minimax regret value for this constrained case is 0.138. This value corresponds to recommendation o1, and adversarial option o2 and utility w1 = 0.6. In this case, the constraints 0.2 ≤ w1 and w1 ≤ 0.6 decrease minimax regret significantly. However usually constraints are not added directly as such, but result from the acquisition of knowledge acquired through a variety of interaction modalities, such as direct user preference queries, or passive observation of user behavior. For instance, comparison queries ask the user which of two proposed options is preferred. The impact of the information acquired depends greatly on the comparison, as different options can lead to different degrees of regret reduction.

A natural meta-heuristic for generating elicitation queries is the current solution strategy (CSS), first described in (Boutilier et al. 2006a) . This strategy would ask the user ∗ whether she prefers the minimax regret option xW or the adversary option xw = MRAdv (x∗W , W ).

In our example, starting from the unconstrained space W , CSS would select {o4, o5} (the minimax regret option and the adversarial option) and ask the user to compare them. Now, let’s assume that the user asserts that she prefers o4 over o5; then a new constraint u(o4; w1) ≥ u(o5; w1), equivalent to w1 ≥ 0.375, is added to our model. In the space W o4≻o5 resulting from the incorporation of this constraint, the minimax regret is 0.1, resulting from recommendation o2 and adversarial option o4. Option o4, even if known to be better than o5, has max regret of 0.18 (at w1 = 0.374, with adversarial option o1). Therefore, option o2 will be recommended.

Minimax regret offers recommendations that are robust given the uncertainty of the preference model. In this example, o5 is recommended (in the unconstrained setting) even though it cannot possibly be optimal for any user utility function; this is so because it prevents “disastrous” situations, such as would occur if options o1 or o2 are recommended when w1 is very low (despite the fact that for a good part of utility space, these options are optimal. Note, that as knowledge of user utility increases, more accurate recommendations are made; for example, recommending o2 when we learn that o4 is preferred to o5.

Optimal Recommendation Sets: Setwise Regret In most cases the value of a set of recommendations is dependent on the elements of the set jointly, not on each individually. If the user is going to benefit from only one of the recommendations (example: recommending apartments) then the utility of the set is then the maximum utility among the individual options, i.e., the one the user will pick from the set.

The problem of set recommendations has been addressed using probabilistic expectation: Price and Messinger (Price and Messinger 2005) optimize set recommendations using the EMAX criterion, defined as the expectation of the maximum utility among the options in the set.

In order to retrieve optimal set recommendations, we define the notion of setwise max regret. The setwise max regret of a recommendations set can be seen as the equivalent of EMAX in our non-probabilistic framework. Suppose we have a slate of k options to present to the user and want to quantify the possible loss by restricting the user’s decision to options in that slate. Intuitively, the user may select any of the k options as being “optimal.” An adversary wanting to maximize regret should do so assuming the any such choice is possible—unlike max regret, we allow the user to select from among any of the set of k options. In this formalization, we choose the set of k options first, but delay the final choice from the slate only after the adversary has chosen a utility function w. The regret of a set is then the minimum difference between the utility of the best configuration under w and the utility of the options in the slate. Specifically, define the setwise maximum regret of option set Z = {x1, . . . , xj } to be:

SMR(Z; W ) = xm′∈aXx wm∈aWx mx∈iZn u(x′; w) − u(x; w) SMR-Adv (Z; W ) = arg xm′∈aXx wm∈aWx mx∈iZn u(x′; w) − u(x; w) Setwise max regret has some intuitive properties. First, adding new items to a set cannot increase setwise max regret: SMR(A ∪ B, W ) ≤ SMR(A, W ). At the same time incorporating options that are known to be dominated given W does not change setwise max regret: in other words, if u(a, w) > u(b, w) for some a ∈ Z and all w ∈ W , then SMR(Z ∪ {b}, W ) = SMR(Z, W ). Finally, the max regret associated with recommending the entire product set is zero: SMR(X, W ) = 0. This is the equivalent to asking the user to directly choose the best option from the space of available options—obviously, a task of with extreme cognitive cost, and one that runs counter to the spirit of recommendation assistance! But should the user be able to answer correctly, it guarantees optimality.

Setwise max regret can be equivalently written in as follows:

SMR(Z, W ) = max max[u(y; w) − max u(x; w)] (5) y∈X w∈W x∈Z This captures the intuition that, given w, the option (among those in Z) that determines setwise max regret is that with highest utility with respect to w. In fact, it can be useful to explicitly partition utility space with respect to which option in Z is maximal. We define the utility subset W Z→xi as the set of utilities such that xi has greater utility than any option in Z.

W Z→xi = {w ∈ W : u(xi; w) > u(xj ; w) ∀j 6= i, 1 ≤ j ≤ k}

The set of all W Z→xi for any xi ∈ Z partitions W (we ignore the possibility of ties over full-dimensional subsets of W , which can easily be dealt with, but complicate the presentation marginally). An important observation (that will be used later) is that we can rewrite the setwise max-regret SMR as the aggregate maximum of the (individual) maxregret considering a partition of the utility space according to which option has higher utility.

Observation 1 Given Z = {x1, . . . , xk} and, for 1 ≤ i ≤ k, Example (continued) We now consider setwise max regret for the example introduced above. Let the number of options in a recommendation set be k = 2. The following combinations are ranked best according to the setwise regret criterion.

Set SMR Adversary Adversary W {o1, o4} 0.07 o3 w1 = 0 {o1, o2} 0.1 o4 w1 = 1 {o3, o2} 0.1 o4 w1 = 1 {o3, o4} 0.11 o1 w1 = 0.42

The set {o1, o4} is the best choice for a joint recommendation of two options, corresponding to a value of regret of 0.07. Other combinations, such as {o1, o2}, {o3, o2} and {o3, o4}, also have a relative low value of regret.

A set recommendation can often have dramatically lower regret than the minimax optimal single recommendation (in this case, o5).

It is interesting the fact that the optimal recommendation set is composed of two options, o1 and o4 that, when considered alone, are associated with high regret. Any set including o5, the single best recommendation, is ranked poorly with respect to setwise regret.

We now consider the case of larger sets. If we need to select a slate of three options (k = 3), the regret will be 0.04 and the recommendation would be {o1, o3, o4}; in this case the adversary would pick o2, and the value w1 = 0.51 (intersection point of o1 and o4).

In the case of four options to be selected (k = 4), the set {o1, o2, o3, o4} would be recommended and it would be associated to a setwise regret of 0: the slate includes all the options that can ever become optimal (considering Observation 1, it follows that for any W Z→oi that partitions W , the max regret has to be 0).

Now we consider how setwise regret changes when new information is included. We consider a slate of two options to be selected (k = 2) and we suppose that the user asserts the preference of o4 over o5. The recommendation set is still {o1, o4} but with a much lower value of (setwise) regret: only 0.04.

We conclude the discussion of the example with some remarks on the optimization process. The adversary’s utility does not necessarily corresponds to one the vertex of the feasible region, as in the single recommendation case; it may also lie in any intersection of the hyperplanes associated with the options. For instance (in the unconstrained case) the setwise regret of {o3, o4} is maximized for the value w1 = 0.42 (the utility that makes o3 and o4 equally preferred).

Computation of Setwise Minimax Regret In this section we discuss how to efficiently compute regretbased recommendations. We first discuss how to compute minimax regret for single recommendations and then describe how to modify these procedures to compute setwise minimax regret for recommendation sets. We distinguish two settings: configuration problems, where options are defined by variables and configuration constraints (i.e., as solutions to a constraint satisfaction problem (CSP)); and database problems, where options are enumerated in a product database.

Configuration problems In configuration problems, optimization over product space X is formulated as a constraint optimization problem or MIP. In such domains, minimax regret computation can be formulated as a MIP, and solved practically for large problems using techniques such as Bender’s decomposition and constraint generation. We refer to (Boutilier et al. 2006a; 2004; Braziunas and Boutilier 2007a) for more details. Our MIP formulations for setwise minimax regret below will draw heavily on these techniques, but necessitate important modifications.

Database problems When options are enumerated in a product database, minimax regret computation requires to repeated computation of the pairwise regret between a candidate recommendation and an adversarial option in order to identify the option with minimax regret. For ease of presentation, assume a linear utility function as above, defined by weights wi over m attributes. Pairwise regret MR(x, y, W ) of recommendation x and adversarial option y is readily computed with the following LP:

max w:wi∈[0,1]

X 1≤i≤m

wi(yi − xi) s.t. X wi = 1

i w ∈ W (7) (8) (9)

Here we assume the feasible parameter set W is captured by linear constraints. A similar LP can be formulated for discrete-valued attributes, without assuming linearity, just additivity. Hybrid models with continuous and discrete attributes can easily be represented with a combination of these two representations. Generalized additive utility models models (Fishburn 1967; Braziunas and Boutilier 2006; 2007b) can also be easily represented in this framework. This means that pairwise regret can be computed extremely efficiently (e.g., in a few milliseconds using CPLEX on the types of problems discussed below).

Minimax regret computation is more complex because we need to maximize over all possible adversarial choices, and minimize over all possible recommendations. A naive approach would consider every pair of options, requiring O(n2) pairwise regret computations for a database of size n, where each of these computations requires the solution of an LP of size proportional to the number of utility parameters.

However, since minimax regret can be seen as a game between the recommender and an adversary, the computation can be greatly improved in practice by formulating the optimization as a minimax search and using standard pruning techniques. Unlike typical games, the search tree has very limited depth: only two ply, one choice of recommendation by the MIN player (attempting to minimize regret) and one choice of adversarial option by the MAX player (attempting to maximize the regret of the recommendation).3 Note that the game has a large number of actions, once per product in the database. The MIN player (recommender) moves first, the MAX player (adversary) second. The leaves of the minimax tree are labeled with the pairwise max regret of the two choices on its path.

A full evaluation of the tree requires the solution of n(n − 1) pairwise regret LPs (noting that the MIN player’s choice need not be explicitly evaluated or even represented as a possible MAX choice, since it must yield pairwise regret of 0). However, it is generally not necessary to evaluate every node of the tree as Alpha-beta pruning (see (Russell and Norvig 2003) for an introductory description) can be used to eliminate branches from evaluation.

3The choice of the utility function by the adversary is dictated by pair of options, so it need not be modeled as a move.

Alpha-beta pruning is simple in such a simple game tree: during the tree evaluation, we maintain an upper bound UB (initially +Inf) at the root, representing the max regret of the best solution found so far (from the perspective of MIN), and lower bounds LB (n) at each MAX node, one for each possible MIN choice (or recommendation). Every time we evaluate a leaf node, we compute pairwise regret MR(omin, omax, W ) of MIN’s choice omin and MAX’s choice omax on the path. We update the lower bound at the corresponding MAX node, and prune (α cut 4) whenever LB (n) ≥ U B. This is because MR(omin, omax, W ) ≤ MR(omin, W ). At the same time, whenever we complete the evaluation of a MAX node n, we update the upper bound UB to min(U B, v(n)) where v(n), the value of the node, is the maximum value among the leafs.

The efficiency of this pruning depends on the order in which nodes are evaluated (Russell and Norvig 2003) ; this is especially true given the very shallow, broad nature of our tree. Pruning is most effective when, at each node, the best children (with respect to the relevant node evaluation, MIN or MAX) are evaluated first. Figure 2 shows, in our simple example, that in the best case only 5 nodes out of 9 need to be evaluated (i.e., 5 pairwise regret maximization). To speed up the search, we consider a heuristic that first evaluates choices at the MIN (recommender) node that are likely to be good candidates for minimizing max regret; and we first evaluate at at MAX (adversarial) nodes options that are likely to induce high regret against the given MIN choice. These heuristics give us an evaluation order for both MIN and MAX choices and can lead to considerable pruning. We discuss each in turn.

For the MIN node, we note that the regret of any option is maximized at one of the vertices of the feasible region W . Thus we sample t vertices (for instance, by considering extreme weights that maximize the importance of one of the attributes) and refer to the the w so-sampled as reference utilities. These are used to initialize the lower bounds LB (n): we simply compute the actual regret with respect to these utilities for the option that leads to (MAX node) n. We then evaluate MIN’s children n in increasing order of initial lower bound LB (n).

To order the children of MAX node, for each MAX node n, we consider the feasible utility function w− that minimizes the utility the MIN choice. (This requires a simple optimization.) The option that maximizes utility at w− (i.e., the optimal choice under w−) is likely to give a high value of for pairwise regret and thus represents a potentially good adversary. Moreover, once we have generated w−, we can use it to update the lower bound by considering the actual regret for each option. MAX choices are evaluated in order of decreasing utility under w−.

In practice, these heuristics can significantly speed up the computation of minimax regret in product databases. Table 1 shows that number of pairwise regret checks (LPs) is almost linear in the number of options in the database; indeed, with these orderings, MAX nodes are often pruned immediately without even considering an adversarial choice. (These are 4beta cuts are not possible given the depth of the tree attributes 4 5 7 10 10 15 num of pairwise checks 41 207 492 1003 1998 999 experiments run on synthetic data for illustrative purposes.) Set Recommendations: Setwise Minimax Regret We now consider the modification of the techniques above for setwise minimax regret. Naturally, setwise max regret is more computationally demanding, requiring selection of a set of options. However, it is still possible to formulate the computation in a MIP for configuration problems. Database problems are more challenging: the adversarial search presented above for single-item recommendation can be applied directly, with replacement of a single move by the recommender (MIN player) by k moves, corresponding to the choice of k options for the slate. However, performance can take a dramatic hit as the size of the desired recommendation set increases. However, we develop a simple heuristic hill-climbing strategy that seems to provide very good recommendation sets in practice.

Configuration problems: MIP formulation For configuration problems we formulate the problem of setwise minimax regret following the general strategy for single-option minimax regret, formulating as a (MIP) minimization with exponentially many constraints. We use a constraint generation procedure to prevent enumeration of the entire constraint set (Boutilier et al. 2006a; 2004) . However, there are some critical differences in the formulation, which we describe here.

Setwise minimax regret for configuration problems can be formulated as the following MIP.

min M,Iwj,Xj,Vwj

M s.t. M ≥

X Vwj 1≤j≤k

∀w ∈ Vert Vwj ≥ w · (x∗w − Xj) + (Iwj − 1)mbig ∀j ∈ [1, k] ∧

∀w ∈ Vert X Iwj = 1 ∀w ∈ Vert 1≤j≤k Iwj ∈ {0, 1} Vwj ≥ 0 ∀j ∈ [1, k], ∀w ∈ Vert (10) (11) (12) (13) (14) (15)

This MIP minimizes M by: (a) choosing k options (or configurations xj designated by variables Xj (where each Xj is a vector of n attributes) for the recommendation set; (b) selecting, for each adversary w, one of those options (the jth option) as the choice that has minimum max regret against an adversary, and ensuring that M is greater than the true regret of the jth option relative to every possible choice of adversary utility function and option.

Note however that this constraint need not be applied to (continuously many) utility functions or exponentially many adversarial choices. In the MIP, we post these constraints only for each vertex of W (i.e., w ∈ Vert (W )) and for the optimal product choice x∗w for that vertex. This relies on the observation that regret maximized at vertices of W , and, for any adversarial choice of w, the adversarial option that maximizes the pairwise regret for any user choice is the optimal option for w.5

However, this MIP still requires (potentially) exponentially many constraints, one for each element of Vert (W ). We can make computation much more effective by applying constraint generation, observing that at the optimal solution, very few of these constraints are likely to be active. Our procedure works as follows: we solve a relaxed version of the MIP above—the master problem—using only the constraints corresponding to a small subset Gen ⊂ Vert (W ) of the constraints in the MIP above. We then test whether any unexpressed constraints are violated at the current solution. This involves computing the true setwise max regret of the slate generated by the master problem. If the true setwise max regret is of the slate is greater than δ, we know that a constraint has been violated. Specifically, the computation of setwise max regret will produce the element w ∈ Vert (W ) and optimal product x∗w that corresponds to the maximally violated constraint at the current master solution. So if a constraint is violated, we add this maximally violated constraint to Gen , tightening the MIP relaxation, and repeat; if not, we are assured that the current solution minimizes setwise max regret.6

In the formulation, mbig is an arbitrary big number, that we need to encode the fact that, for any given w, only the option with the highest utility (among those in the slate) with respect to w contributes to the actual setwise regret.

The SMR maximization subproblem can be also encoded with a MIP, similar to (Boutilier et al. 2006b) . The optimization makes use of a decision variable to explicitly represent the setwise regret, M , to be maximized and we constrain M to be greater than the single max regret M R(xj , W ), for each option in the slate.

Database Problems: A Hill-climbing Strategy As discussed above, while minimax search can be applied directly 5Vwj is the actual regret of option Xj of the slate with respect to the utility w when the corresponding I wj is activated. For any w, one and only one I wj is set to 1. In order to minimize M , the optimization will activate the I wj corresponding to the xj with lower actual regret. The first constraint (10) captures the idea that for a slate of options, given w, the regret of the joint slate is the minimum among the individual values of regret (in the summation, all but one term are zeros).

6Note that the adding a new constraint requires the introduction of new variables to the master problem. Every time we add a new w to Gen, k new variables I and V are necessary. to the problem of setwise minimax regret for database problems, scaling is sometimes a concern. We now present a heuristic hill-climbing strategy that scales much more effectively. We describe it in the context of database problems, but it can also be used directly for configuration problems.

The central idea is that is possible to modify a given recommendation set Z in such a way that setwise max regret cannot increase, and usually decreases until a high quality set is found. We define the MMR-transformation T to be a mapping that refines a recommendation set Z by partitioning the current feasible utility space W into {W Z→xi }, ∀xi ∈ Z, as discussed in Observation 1. In each partition we compute the single recommendation that has minimax regret in that region of utility space, and define the new set recommendation T (Z) to be the collection of these (single) minimax-optimal recommendations. ′ Definition 2 Define the MMR-transformation T : Z → Z , where Z = {x1, . . . , xk}, to be T (Z) = {x′1, . . . , x′k} such that for all 1 ≤ i ≤ k:

x′i = MMR-Opt (W Z→xi ) We can show that T cannot increase setwise max regret.

SMR(T (Z)) ≤ SMR(Z) set recommendation

Z We use the MMR-transformation to define our heuristic search strategy to produce good recommendation sets; intuitively, we repeatedly T until a fixed point (with respect to setwise max regret, not the set itself) is found.

The algorithm considers an initial set Z, and rewrites Z using T until a fixed-point is found. • Repeat Z := T(Z) • Until SMR(T (Z), W ) = SMR(Z, W )

We initialize the slate Z using the current solution strategy (CSS), empirically, this seems to produce the most promising recommendation sets. For k = 2, this means that the initial set is Z = {x∗W , xw}, where x∗ = MMR-Opt (W ), and xw = MRAdv (W ).

For larger sets (k > 2), there is not a standard definition of the CSS. We propose to use the following strategy, that we call chain of adversaries, to generate the initial slate. We start from {x∗W , xw} and repeatedly maximize setwise max regret given the current set, in some sense maximizing the diversity of choices from perspective of utility space. This gives the set {x1, . . . , xk} where:  x1 = xi =

∗ xW

Adv ({x1, .., xi−1}, W ) 2 ≤ i ≤ k

The chain of adversaries requires to solve single minimax regret once, and then k − 2 setwise regret maximizations. The chain of adversaries can be seen as a generalization of CSS to sets of any size, and could also be considered as an alternative, faster strategy to select recommendations. 2 3 4 5 6 7

8 steps

To validate our regret-based approach to critiquing we designed a framework that simulates a full interaction of a user with a user interface. As in a real system, each simulation comprises a number of cycles of interaction, each showing a current product which the user can critique using either unit or the selection of one of the suggested recommendations.

The simulated user continues the critiquing process until the perceived increase in utility is lower than some threshold. We assume that among all possible critiquing actions, the one with highest perceived improvement will be chosen by the user.

In our experiment, at each interaction the system displays: • the current product, • a choice of unit critiques of the current product (they request the modification of a particular product attribute), • a set of suggestions, alternative options that can change focus for the search, presented as such or labeled as compound critiques (“lighter and faster processor, but more expensive”)

At each step, the user can choose to either select the current product (and finish the interaction) or to tweak it in order to improve it and get better recommendations in the next cycle.

We compare our regret-based approach to three other approaches that use compound critiques. In our case, we use the generation of a set of recommendations (based on setwise regret) to display as alternatives. One is selected as current product and the others are displayed as suggestions.

We briefly review the different critiquing approaches and then we present the experimental results.

The dynamic critiquing model (Reilly et al. 2004) makes use of a particular similarity metric to retrieve the current product and uses the APriori datamining algorithm to propose alternative compound critiques. The algorithm dynamically generates compound critiques by discovering common feature patterns among the set of products. Essentially, each compound critique describes a set of products in terms of the features they have in common. For example in the PC domain, a typical compound critique might be “Faster CPU and a Larger Hard Drive.” Whenever a product is shown to the user as the current product, the APriori datamining algorithm is used to quickly discover these patterns and convert them into a set of suggested compound critiques. Each compound critique corresponds to a product that is, among all products satisfying the pattern most similar to the current one.

The generation of suggestions consists of two steps. First, each product is matched against the current product to produce lists of critique patterns, each comprising an attributes and a comparison operators from the set: <,>,¬,=. An example pattern might be: {[Price >], [ProcessorSpeed >]}. Second, the algorithm uses APriori to find recurrent critiquing patterns; a compound critique based on a pattern is then presented to the user it has sufficient support in the product database. In our experiments, the support threshold is set to 0.3 and selection of compound critiques corresponds to the low-support strategy in (Reilly et al. 2004).

Incremental critiquing (Reilly et al. 2005) (IC) improves the basic dynamic critiquing model by incorporating a user model. While suggestions are still based on the APriori algorithm (as above), the retrieval of the next product associated with a critiquing action is based on a quality metric that values both the score given to the product by the preference model and its similarity to the current product.

In the implementation we developed for our experiments, we take advantage of the fact that the preference ordering over attributes is known: the score is dictated by a linear utility function that gives equal weight to all attributes. The initial product is the option with maximum utility. When retrieving the next example from the set of products that satisfy the user-chosen critique, we select the product x that maximizes score(x) · Similarity (x, y), where y is the product recommended at the previous cycle, and score is the heuristic utility function.

Another implementation of incremental critiquing (Reilly et al. 2007) uses a simple multi attribute utility (MAUT) model to make recommendations and generate compound critiques (rather than similarity). In this approach, a simple additive utility model u is generated, initially giving equal weight to all attributes; each time an attribute is critiqued, its weight is multiplied by a constant (and all weights renormalized). The original design of this algorithm makes use of parameterized value functions for each attribute, where the value taken by the current option is considered preferred. Since our experimental set up assumes that the local preference ordering over attribute values is known, we instead assume a linear utility model.

Suggestions are generated using optimization with respect to the estimated utility model, and the k best products are presented as alternative cases. A limitation of this approach is its reliance on a fixed utility model (as opposed to reasoning with the space of possible user utilities). Moreover, options that all have high value in a single utility sample are unlikely to be diverse or informative enough to generate useful distinctions.

Our version of dynamic critiquing exploits setwise minimax regret using the ideas above. Specifically, at any point in the interaction cycle, we generate the current optimal recommendation set (with respect to minimax setwise regret), and propose one of these options a current product. The remainder of the set is used to display suggestions. 0.9 0.8

In the experiments we compare the four different versions of dynamic critiquing discussed above: the original dynamic critiquing algorithm (similarity plus APriori), incremental critiquing, incremental critiquing with MAUT, and regretbased critiquing. We used a C implementation of the APriori algorithm (Bodon 2003) . All systems make available unit critiques of any attribute (and user’s adopt an expected improvement semantics). We evaluate the performance of all algorithms with respect to recommendation efficiency and offer some speculative examination of regret-based critiquing in terms the tradeoff between cognitive cost and number of compound critique options presented at each interaction.

We evaluate the different critiquing methods by comparing the quality of the recommendations with respect to max regret. We tested the methods on a real database of 200 apartments, using randomly drawn utility functions (as described above), and k = 3 suggested products at each interaction cycle. All results are averaged over 20 simulated users. Fig. 4 shows the maximum regret of the recommended product at each stage of the interaction. We note that regret-based critiquing outperforms the other methods of generating compound critiques by a wide margin. This is true when considering both the “anytime” profile of the method (i.e., the degree to which minimax drops) and its final convergence: our technique converges on a product who max regret is about 3% on average, while the MAUT incremental critiquing settles at about 10% (and the others worse, with dynamic critiquing unable to reduce max regret to less than 18%).

More interesting is the fact that regret-based critiquing offers better “actual” recommendations, as measured by true regret (difference from the true optimal recommendation). Regret-based critiquing is designed to attack bounds on re0.25 0.2 gret (i.e., worst-case loss); so one might wonder whether other techniques find better products despite being unable to “prove” that they are good. Fig. 5 shows this not to be the case. While other critiquing techniques recommend products that are much better than their regret-bounds suggest, regret-based critiquing is able to consistently find the optimal product (and find a near-optimal product in as few as five or six interaction cycles). By contrast, the other three methods are unable to identify the optimal option at convergence.