Learning from Stochastically Revealed Preference
Authors: John Birge
Xiaocheng Li
Chunlin Sun
Venue: NeurIPS 2022 Accept (2022)
Keywords: Revealed Preference
Bayesian Algorithm
Sample Complexity
Stochastic Models

Abstract: We study the learning problem of revealed preference in a stochastic setting: a learner observes the utility-maximizing actions of a set of agents whose utility follows some unknown distribution, and the learner aims to infer the distribution through the observations of actions. The problem can be viewed as a single-constraint special case of the inverse linear optimization problem. Existing works all assume that all the agents share one common utility which can easily be violated under practical contexts. In this paper, we consider two settings for the underlying utility distribution: a Gaussian setting where the customer utility follows the von Mises-Fisher distribution, and a $\delta$-corruption setting where the customer utility distribution concentrates on one fixed vector with high probability and is arbitrarily corrupted otherwise. We devise Bayesian approaches for parameter estimation and develop theoretical guarantees for the recovery of the true parameter. We illustrate the algorithm performance through numerical experiments. 

Learning from Stochastically Revealed Preference
John R. Birge
The University of Chicago Booth School of Business John wwwgge@chiiagoooooooiiccooococee edu
Xiaocheng Li
Imperial College Business School, Imperial College London xi xiaocheng... 11 wwwieiieeeeiiieeee all ac. uk
Chunlin Sun
Institute for Computational and Mathematical Engineering, Stanford University Chunlin@stanie edu
Abstract
We study the learning problem of revealed preference in stochastic setting: a learner observes the atilitymaximizing actions of a set of agents whose utility follows some unknown distribution, and the learner aims to infer the distribution through the observations of actions. The problem can be viewed as single- constraint special case of the inverse linear optimization problem. Existing works all assume that all the agents share one common utility which can easily be violated under practical contexts. this paper, consider two settings for the underlying utility distribution: a Gaussian setting where the customer utility follows the von Hlises-Fisher distribution, and 8-corruption setting where the customer utility distribution concentrates one fixed vector with high probability and is arbitrarily corrupted otherwise. We devise Bayesian approaches for parameter estimation and develop theoretical guarantees for the recovery of the true parameter. We illustrate the algorithm performance through numerical experiments.
Introduction
The problem of learning from revealed preference refers to the learning of a common utility function for set of agents based the observations of the utllit-maximizing actions from the agents. The revealed preference problem has long history in economics [Sam48] Afr67] (See [Var06] for review). line of works BV06 22 BDM 14 ACD 15) formulate the problem as a learning problem with two objectives:
(i) rationalizing a set of observations. i.c., to find a utility function which explains set of past observations: (ii) predicting the future behavior of militt-maximization agent. Mathematically, the action of the agents is modeled by optimization problem that maximizes linear (or concave) utility function subject to one linear budget constraint. The learner (decision maker) aims to learn the unknown utility function through set of observations of the constraints and the optimal solutions. The problem can be viewed as a single-constraint special case of the inverse optimization problem [AO0I] which covers wider range of applications: geoscience [T92 finance [BGP12] market analysis [BPP77. energy ASS18), etc.
In this paper, we study the problem under a stochastic setting where the agents have a linear utility function randomly distributed according to some unknown distribution. Such a stochastic setting is well-motivated by some application context where the agents are customers and the constraint models the prices and the customer's budget. The optimal solution encodes the customer's purchase
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

behavior and the stochastic utility (objective function) captures the heterogeneity of the customer preference for the products. The goal of learning in this stochastic setting thus becomes to learn the utility distribution through observations of the actions. To the best of our knowledge, we provide the first result of learning a stochastic utility for the revealed preference problem and even in the more general literature of the inverse optimization problem.
Related Literature: The existing approaches to the problem can be roughly divided into two
categories.
Query-based In query-based model, the learner aims to learn the utility function by querying an oracle for the agent's 's optimal actions, and the goal is to derive the sample complexity guarantee for sufficiently accurate estimation of the utility function. [BV66] initiates this line of research and studies a statistical setup where the input data is a set of observations and the learner's performance is evaluated by sample complexity bounds. [ZR12] studies the of linear linearly separable concave utility function, and [BM+144 generalizes the setting and devises learning algorithms for several classes of utility functions. Other than a statistical setup where the observations are sampled from some distribution, both of these two works study an "active" learning setting where the learner has the power to choose the linear constraint (set the prices of the products). Some subsequent works along this line study the associated revenue management problem [ACD+15] and game-theoretic setting [DRS* + 18) where the agents act strategically to hide the true actions.
Optimization baasdidddddobbad:::::: The optimization based approach is usually adopted in the literature of inverse optimization, and some algorithms developed therein can be applied to the special case of the revealed preference problem. [7L.66] and [AOOT] study the inverse optimization with one single observation and develop linear programming formulations solve the problem. Later, [KWB11] and [ASS18) study the statistical (or data-driven) setting where the observations are sampled from some distribution. Specifically, [ASSI8] 18] considers a setting where the optimal actions of the agents are contaminated with some independent noises, but all the agents still follow a common utility parameter vector. (EEAAHKT]] studies the distributional robust version of the problem and [BL22 considers contextual formulation. A recent line of works [BMPS18] DCZ18 DZ20, CKK20 cast the inverse optimization problem in an online context and develop (online) gradient- basedddd--dddeeeeeeeee algorithms.
As we understand, all the existing algorithms and analyses under this topic rely on the assumption that all the agents share one common utility function (or common utility parameter vector), and thus can fail in the stochastic setting. In this paper, we formulate the problem in Section and focus on the statistical data input where the budget constraint is sampled from some unknown distribution. We consider two stochastic settings: a Gaussian setting in Section 3 and a ó-corruption setting in Section We conclude with numerical experiments and discuss (i) how the results can be generalized the inverse optimization problem and (ii) the implications for the query-based model where the learner has the power to choose the budget constraints.
2
Model Setup
Consider a customer who purchases bundle of products subject to some budget constraint. The customer's maxiizig action can be modeled by the following linear program:
LP(u, b) = max
s.t.
ag < b, 0 < 1,,i= 1,.,,,
where u = (u,,,.,, v,)) R", a (#1..... (x) E RR, and b E R2 are the inputs of the LP. Here the decision variables æ encode the purchase decisions where a partial purchase is allowed, u, denotes the customer's 's utility for the i-th product, and a, denotes the price or cost of purchasing the i-th product. The right-hand-side b denotes the budget of the customer.
Throughout this paper, we make the following assumption. Assumption 1. We assume:
* The utility vector u follows some unknown distribution P...

---

The LP's input (a, b) follows some unknown distribution Pa. independent of Pa.
There exists 0 > 0 such that E [a, 1] almost surely for i = I,
Our goal is to infer the distribution through observations of customers' optimal actions. Mathemati- cally, we aim to estimate the distribution of Pu. through the dataset
Dr {( a2, be))
Here the 1-th sample corresponds to unobservable uu generated from Pu and at is one optimal solution of LP 0;, bb). Due to the scale invariance of the utility vector, we restrict the distribution Pu to the unit sphere S {u ||u|2 1). In the following two sections,
consider two settings: (i) Gaussian: P. follows the von Mises-Fisher distribution, i.e., the restriction of a
multivariate Gaussian distribution to the unit sphere; (ii) ô-corruption: Pu concentrates on one point u" with probability 1 - 5 and follows an arbitrarily corrupted distribution with probability 6.
U2
U1
U1
S
Figure 1: Visualizing the challenge of the problem in 1-D and 2-D.
The challenge of the problem. Each observation (zī, a, by) prescribes region Ue C Sn-1,
U, {u s"-1; æ; is optimal solution of LP(u, b.)
The set Ue captures all the possible values of u, that is consistent with the t-th observation. The following lemma states that the set Ue can be expressed by group of linear constraints.
Lemma 1, For each Us, there exists a matrix V; and a vector wi such that
U4 = {u E S=-1 Vau S wt}
In the deterministic setting of the revealed preference problem, all the u are identical and the learning problem is thus reduced to finding one feasible u in the set of nT But in a stochastic setting, may happen that the set of T 14g empty. Figure provides conceptual visualization of this challenge of "empty intersection" Each blue solid segment denotes one such U. and the blue dashed line represents a value of u that appears most frequently these Ut's. We remark that the figure is just for illustrative purpose as the problem may not be well-defined in the 1-dimensional case.
From an estimation viewpoint, the goal is to estimate the distribution of Pa without the knowledge of the realized samples u, s, but merely with the knowledge of 24 to which u, belongs. The sample efficiency of the estimation procedure is naturally contingent on the dispersion of 24, which is essentially determined by the generation of (a,, b.). For example, all the 24, coincide with each other, then one can hardly learn much about the underlying P.. In this paper, we aim to pinpoint conditions for Pa,s such that the learning of P,, is possible. Also, an alternative way to measure the estimation accuracy is to evaluate the predictive performance of the estimated model on new observations generated from Pa,b, and such performance bounds generally bear less dependency on the distribution of Pa.s. We also provide theoretical guarantees in this sense.

---

3 Gaussian Setting
In this section, we consider setting where the distribution Pa. follows the von Mises-Fisher distribu- tion parameterized by 0 (Me, k) with the density function
exp (-KH² u)
[uu; 0) Jugg-- exp( -xju u)du
X exp (-Kju u).
Here the vector la RR represents the mean direction and the parameter k concentration of the distribution. The deterministic setting of the revealed preference problem can be viewed as the case when x oc and then the distribution degenerates to point-mass distribution on the unit sphere. Denote the true parameters of the distribution Pa. by 0 = (μ² x²"). Then the likelihood of the dataset Dr under parameter is
controls the
T 0(D+10) = II P ((x), ar b.)
T II
/
f(u; d)u.
We remark that the maximum likelihood approach cannot be applied here for two reasons. First, the integration of fu; 0) over the region Ue closed-form. The first point not only pertaining to the Gaussian parameterization of Pu. The scale-invariant property of the utility vector restricts the distribution P. unit sphere simplex, and consequently, the likelihood function inevitably involves the con--losed-fore integration. This issue can be partially resolved by using the Monte Carlo method approximate the integration, and good thing is that the same integrand is shared across all the observations. Second, the likelihood function is not analytical in 0. Thus this prevents the usage of gradient- based algorithms to solve the problem and also makes difficult to derive theoretical guarantees for the maximum likelihood estimator.
We propose Bayesian perspective for the problem: instead of identifying the parameter that maximizes the likelihood function, we directly draw samples from the posterior distribution. We will see shortly that the approach be justified through concentration property of the posterior distribution. Suppose we have a prior distribution (0) and then we can define the posterior distribution by
Pr (0) Po(0) (
(DD))
T
α (0)
II 1=1
f(u; du.
uEld:
With slight abuse of notation, we use (-(()) (or Po(-)) to refer to both the density function and the probability measure of the posterior (or prior) distribution. We make the following assumption on the prior distribution.
We assume the concentration parameter K E (K, R) where K.R R are two known positive constants. The prior distribution (0) is uniform distribution sn-1 x (E. R).
Assumption 2.
Theorem 1. Let
Or = f (K, (P (P ar, b))
((x), ar, b.) S max (8)8 ni log
T1/2
where W(:-)) is the Wasserstein distance between two distributions support on X x RT R., equipped with Euclidean metric. Then, under Assumptions) 7
1-Pr(Or) > in probability as T 20.
Specifically, the following inequality holds
3 T
E Prr (0r)
where the expectation is taken with respect the random distribution Pr(-) (essentially, with respect to the dataset Dr..)

---

Theorem Thecoremmjustiffes Dustifiis the approach of posterior sampling. We first remark that the Bayesian sampling approach is just proposed to estimate the parameters, but all the theoretical results are stated in frequentist language. The proof of Theorem follows the standard analysis of the convergence of the posterior distribution [GGVDV0) CDBW2I] While similar results should also hold for other underlying distribution of P... the von Mises Fisher distribution provides much analytical convenience in deriving the bound. Each 0, together with the distribution of Pa. defines a distribution over the space of (zū at, b,). As we use observations (æī az bt)'s to identify the true 0", the set Or defines a set of indistinguishable O's based on the Wasserstein distance between distributions of (æ, az be). The set O2 shrinks T -> oo. The posterior sampling approach samples from the distribution (r(.), and Theorem 1 states that the samples will be concentrated in set Or with high probability. The posterior distribution Pr() (+) is dependent on the dataset Dr, it is a random distribution itself and the results in Theorem | are stated in either convergence in probability or expectation. As a side note, the Wasserstein distance in the theorem is not critical and it can be replaced with other distances such as the total variation distance and the Hellinger distance.
Intuitively, Theorem D says that for some O such that the likelihood distribution IP ((æj, az 0) differs from P ((æj, at be [0") ) to a certain extent, the posterior Pr(-) is unlikely to generate such O. In other words, the posterior distribution identifies the true 0* up to some "equivalence" in the likelihood distribution space. The following corollary formalizes this intuition that if there is an equivalence between the likelihood distribution space and the underlying parameter space, then the posterior distribution is capable of identifying the true parameter.
Corollary 1. Suppose
W (IP ((x ae, 6,)6, P ((xi, ae b)) >0
for all 0 + 0" E S x Is, Rj. Then the posterior distribution Fr(()) will converge to the point-mass
distribution on 0* almost surely as T + co. Moreover, suppose there exists a constant > satisfying
W (P ((0), ae, b.) 0) ((x). a,, b,)())))))) 2 L. 10 1'112
(1)
for all 0 + 0" E E x [1s, R).
Under Assumptions
1 the following inequality holds with probability no less than 1 n-T log
6L
11. 2-log? T
Er 0| 1or--0 0-112| S max (9, 9R) L TT1/2
where 0 is sampled from the posterior distribution Pr(-).
The corollary states that when there is some equivalence between the likelihood distribution space and the parameter space as (I. the true parameter is identifiable. The first part of the corollary states a consistency result that as long as all the 0 + 0" are distinguishable from 0" through the likelihood function, then the posterior sampling will eventually identify the true 0 The second part relates to the convergence rate with an equivalence parameter L.
In Assumption] we assume the constraint input (a;, is generated from some distribution Pa We note that Theorem I and Corollary Thold without any additional assumption on Pa.b. but the space topology of the likelihood distribution is highly dependent on Pa.b. Specifically, a different distribution of (a., by) determines the separateness of the parameter space through affecting the value of L in ① or even its existence. The value L of specific distribution of Pa.. can be examined through simulation. So if the learner has some flexibility in choosing the distribution of Pa,s, the optimal choice would be the one that corresponds to larger value of L. If the constraint input (a., b.) not randomly generated but can actively chosen as the query-based preference learning problem, the results in Theorem I and Corollary 1 still hold by conditioning on all the (a., b,) 's. Unlike the deterministic case where the utility vector u is fixed for all the observations, the stochastic nature of the problem setup here makes it generally very complicated to fully extract the benefit of designing (a;, 6,)'s by the learner. We leave it as a future open question.
Corollary 2. Suppose Pa. is discrete distribution with a finite support. Let (a. b) be a new sample from Pa,b, i.e., independent from the dataset Dr, and let 0r = (K) be a sample from the posterior distribution Pr(()). Denote à' and x² as the optimal solutions of LP a, b) the following inequality holds with
and LP("", a. b), respectively. Then, under Assumptions 12
probability no less than 1 /T-T1/" lo
log T
E || x l1ll S max (16, 16R)
T12
5

---

where the expectation is taken with respect to both the posterior distribution Pr(-) and (a, b).
Corollary 2 provides an upper bound on the predictive performance of the posterior distribution. Specifically, we want to predict the optimal solution of linear program specified by μ (proportion- ally to E(u)) and new sample of the constraint (a, b), and the prediction x" is based on a posterior sample. We know from Theorem that the posterior distribution concentrates indistinguishable from the true 0- in terms of the likelihood. Speaking of the predictive performance, only concern the distribution of the optimal solution (equivalently, the likelihood), but do not require the identification of exact true 0" so Corollary does not require the condition (T) to hold. Intuitively, the prediction of the optimal solution condition distribution of the optimal solution given (a, b). While the definition of Ör in Theorem | concerns the joint distribution of the optimal solution and (a, b), the finite-support condition on Pa,b in Corollary transforms the result on the joint distribution to the conditional distribution.
those O's that are
new observation (a, b) can be viewed
4 5-Corruption Case
In this section, we consider a setting where the utility vector is specified by
uu. w.p. 1 - 5,
(2)
P at w.p. 8,
where u E S is a fixed vector, E [0, 1], and P. is an arbitrary distribution that corrupts the inference of u². The deterministic setting of the revealed preference problem in literature can be viewed as the case of 5 = O, and the Gaussian setting in the previous section can be viewed as the case of 5 = 1 and Pi, being the von-Mises Fisher distribution. In this setting, do not aim to learn the distribution of P but rather our goal to identify the vector u' using the dataset Dy.
A natural idea to estimate u² is by solving the following optimization problem:
OPT,
max WES!
Σ Tu (u)
where the indicator function [e)e) 1 if and Ie(e) 0 otherwise. The rationale for the optimization problem is that for the t-th observation, a vector is consistent with the observation, i.e. a5 is the optimal solution of L.P(u, a;, br), if and only if Tea, (u) = 1. Thus the optimization problem finds vector u that is consistent with the maximal number of observations. The objective function discontinuous u, so we propose the simulated annealing algorithm Algorithm 2 to solve for its optimal solution.
We first build some connection between the optimization problem OPTs and that of the deterministic setting with 8 = 0. Let के be the optimal solution of LP(u", ar, b,) and define
U u E 5n-1, o is an optimal solution of LP(u, a,, bb)
Then the deterministic setting of the revealed preference problem solves
OPTs
Tu, (u).
WES
By the setup of the problem, u² is an optimizer of OPT, and the optimal objective value T. The following proposition establishes that the optimization problem OPT, is contaminated version of OPT, and the effect that the contamination has on the objective function can be bounded using 8. Proposition Under Assumption the following inequality holds
T Lu (u)
T
log T
IP
max uESa-1
T
T
La
(u)
S T
T
When the constraints (ar, bt''s are generated from some distribution Pa,s, it can happen that there exist some vectors u' that are indistinguishable from u" based the observations Dr in the

---

previous Gaussian case. So, we do not hope for an exact recovery of uz, , but alternatively, we aim to derive a generalization bound for our estimator ú. Specifically, we define and analyze the accuracy
Acc(û)= = E [u) with u = {u E s"-1; x x is an optimal solution of LP Unnww a. b)}
where is our estimator of u², (a, b) is a new sample from the distribution Pa,5 Unew new sample following the law of (2). and x: is the optimal solution of LP(u, a, b). In other words, the quantity captures the probability that is consistent with new (unseen) observation, and we know that for the true parameter, Acc(u") 2 1 - 6, which serves performance benchmark.
The challenge for deriving bound on Acc(u) arises from the discontinuity of the objective function 3 The existing methods for deriving generalization bound largely rely on the continuity and the Lipschitzness of the loss function. To make it worse, from Lemma [ we know that Ue is specified by (V, wy) and the Vi's are of different dimensions for different t's. To overcome these challenges, we devise the following y m-margin objective function. Specifically, we first define a parameterized version of U by
u1(7) = {uu S Vau S w; - -
where y is positive constant and is an all-one vector. It is obvious that U1(7)) C Ug Accordingly, we define the y-margin optimization problem by
(PTs(7) = max WE
Σ (u)
Proposition 2. Under Assumption 7 the following inequality holds with probability less than
T
log(T)
log (T/e)
(u) Acc(u)= s $4/ 22-2T + 6
max MES
T
T
fore 10,
Propsittion&relatee the generalization accuracy of any arbitrary u with the corresponding objective value of the y-margin optimization problem. As y increases, the objective function will decrease, so the right-hand-side becomes tighter. Importantly, the accuracy is defined by the original indicator function (or equivalently, 44), while the objective value defined by the 7-margin indicator function (or equivalently, Le (7)).. The implication is that when we optimize the 7-margin objective, we can still obtain bound on the original accuracy Acc(u) for sufficiently large 7,
Theorem 2. Suppose Pa,p is continuous distribution and has density function upper bounded by p. Then, under Assumption] 7 the following inequality holds for sufficient large T
np
20n log
4 T
P Acc(u) 2 1- 5
1
min song #0
|uc|
T1/4
1//4
where i is one optimal solution of OPTs(n) with 7 4nT174
Theorem states a generalization bound on the accuracy of for continuous distributions of (a, b). From Proposition 2 a larger leads to a smaller gap between the accuracy and the 7-margin objective function. Mcanwhile, a smaller leads and 1 - 8. In the extreme case of 0, E (OOPT value of y to trade off these two aspects. We note that the continuous distribution and the upper bound on the density function make it possible to bound the gap of the second aspect. Finally, we remark that the design of y-margin loss function inspired from the max max-ma classifier, but the analysis is entirely different. For the max-margin classifier, the introduction of the margin aims to make the underlying loss function 1 1-Lipschitz so that a generalization bound using Rademacher complexity can be derived. But for here, our 7-margin objective function is still discontinuous one.
smaller gap between the optimal objective value OPT, (7) Acc(u' (u)) 2 1 5. Theorem 2 Poptimizes the
5 Computational Aspects and Discussions
In the previous section, we developed theoretical results for both Gaussian and 5-corruption settings. Now discuss computational aspects with respect to the sampling of the posterior (-) and the
7

---

Algorithm Posterior Sampling for the Gaussian Setting
1: Input: dataset Dr ( ot, (e,, number of iterations K
2: Initialize (()) by randomly sampling from the prior distribution (P)
3: for k = ...,, K do
4: Draw random O' from a pre-determined proposal distribution (0
5: Compute the acceptance rate:
Pr Pr (0 11)
r min
6: Set
((h)
0
w.p.
0 1),
w.p. 1
7:
8: end for
9: Output: ((K)
optimization of (P) As mentioned earlier, the posterior sampling removes the complication of optimizing over 0 in the maximum likelihood estimation, but still inevitably needs deal with the sampling and numeric approximation of the likelihood function. Algorithm Metropolis-Hastien Hastings algorithm to sample from the posterior distribution Pr(.). In the numerical experiments, we choose the proposal distribution Q to be a Gaussian random perturbation, i.c., O' (roj(O((=1)) + E) where follows a Gaussian distribution and the projection ensures that O' stays on the sphere 8n-1, For the acceptance ratio, the posterior distribution is not in closed form, a Monte Carlo subroutine is needed to estimate the ratio.
[ describes a standard
Algorithm 2 Simulated annealing algorithm for ó-corruption
1: Input: dataset Dr {xxt), aee bt ) margin 7, number of iterations K, interval length 7 2: Initialize an initial (temperature) >> and the reduction rate E (0, 1)
3: Randomly generate the first estimate (0)
4: for k 1, 1..... K do
5: if mod = then
6: Update +- c
7: end
8: Draw proposal u' from predetermined proposal distribution Q22e'|ze
9: Compute the acceptance rate:
(
T Σ 1=1
== min
exp
(u)
(u)) Σ (ul
(3)
17
10: Set
(k)
uu' u (k-1)
w.p.
w.p.
11: end for 12: Output: (R)
Algorithm presents simulated annealing algorithm to solve the optimization problem OPT, (t) in Section It takes similar MCMC routine as Algorithm [ and we use the same Gaussian random perturbation for the proposal distribution Q. As the temperature parameter r) decreases, sampling distribution in Algorithm 2 will gradually be more concentrated on the optimal solution set of (PTs(7). Algorithm 2 can be implemented more efficiently than Algorithm in that the likelihood ratio calculation in 3 is analytical.
8

---

Table repports some numerical results for the two algorithms. For both the Gaussian and 6-corruption settings. we consider three distributions of Pa,s= (i) a uniform distribution where ~Unnf([ ) and b ~Unif((1, ni]:; (ii) a discrete distribution where Unif( (1,2) and b ~UUnif(1, n); (iii) fixed-a distribution where a (1, 1) and ~Unnf(( parameters (H²", k=) are uniformly generated from S x [1, 10], and the accuracy is calculated by (nx "x" - p vu==") "/"""")''""" p/"""" where x² and xx are defined in Corollary 2 For the Gaussian case, us" is uniformly generated from S and is set to be 0.1, and the accuracy is calculated by (ac/Acc("") where Acc(u) is defined in Section 4 The numbers in Table 1 are reported based on an average of 20 simulation trials, and we run both Algorithm [ and Algorithm 2 for K = 1000 iterations.
12). For the Gaussian case, the true
We make the following observations from the numerical experiments. First, we remark that the theoretical results in the previous sections provide strong guarantees the convergence property of the posterior distribution. So the deterioration of the algorithm performance for the case when 25 is solely caused by the inaccuracy of the approximate sampling in either Algorithm [T] or Algorithm 2 Such inaccuracy can definitely be mitigated to some extent by a more efficient algorithm implementation such as parallel computing. However, grows may point to a curse of dimensionality that is intrinsic to this estimation problem. Essentially, aim estimate high-dimenniiona distribution only through partial information, i.e., the sets U.'s On the positive end, the algorithms work well for S. 10, so if the learner has the power of choosing (a,, b,). s/he can break up the nigh-dimensional estimation problem into number of low-dimensional estimation problems by focusing on a handful of dimensions each time, Moreover, we provide a visualization of the condition (T) in Figure [ n = 5 calculated based on simulation. The visualization supports the existence of L and thus the identifiability of the true parameters when the posterior sampling can be accurately fulfilled.
argue that the performance deterioration as
3
5
10
25 n.
99.9%
99.9%
98.8%
59.9%
Gaussian
(ii)
99.9%
99.3%
96.9%
56.9%
(iii)
99.9%
94.8%
92.6%
68.5%
99.9%
96.7%
96.0%
55.7%
8-corru.
99.6%
97.9%
63.1% 97.6%
99.9%
98.7%
87.1%
58.7%
Table 1: Predictive accuracies under two settings.
((P(100)P((100))
0
0.5
1
1.5
110-0"11
Figure Visualization of TI..
We conclude our discussion with the following remarks.
Query- based model with leamer-chosen (a,, bz): In this paper, we have focused on the case where the constraints ba,, are stochastically generated. When the concentration parameter k is known for the Gaussian case, there is an efficient way of learning μ through choosing (a,, b,)'s (See the Appendix). In addition, the numerical experiments above also inspire a method that dismantles the high-di nigh-dimensional estimation problem into number of dinennsnnii problems. Another

---

interesting and important question is whether there exist designs of (a,, be)'s such that the posterior sampling can be more efficiently carried out.
The results in this paper are presented under the setting of linear objective and single constraint. We emphasize that the results can be easily generalized to the case of multiple constraints and parameterized nonlinear utility. Thus our result can be viewed as preliminary effort address the problem stochastic inverse optimization. Our conjecture is that when the set Ue corresponds to a multiple-constrain problem, it may feature more structure and thus facilitate the learning of the utility distribution.
Multiple constraints and nonlinear utility:
Choice modeling: The stochastic utility model in our paper also draws an interesting connection with the literature choice modeling. which is pillar for the pricing and assortment problems in revenue management (TVVRRO GT 19]. For most of the existing choice models, the learning problem be viewed special case of our study by letting (1, ..... 1) and 1. The results in paper complement to this line of literature developing a model where customers can make multiple purchases.
References
[ACD+15] 15] Kareem Amin, Rachel Cummings, Lili Dworkin, Michael Kearns, and Aaron Roth. Online learning and profit maximization from revealed preferences. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 29, 2015.
[Afr67] Sydney N Afriat. The construction of utility functions from expenditure data. Inter- national economic review, 8(1):67-77, 1967.
[A001] Ravindra K Ahuja and James B Orlin. Inverse optimization. Operations Research, 49(5):771-78,, 2001. 2001.
[ASS18] Anil Aswani, Zuo-Jun Shen, and Auyon Siddiq. Inverse optimization with noisy data. Operations Research, 66(3):870-89) 2018.
[BDM+ 14] Maria-Florina Balcan, Amit Daniely, Ruta Mehta, Ruth Urner, and Vijay V Vazi- rani. Learning economic parameters from revealed preferences. In International Conference on Web and Internet Economics, pages 338-353. Springer, 2014.
[BFL21] Omar Besbes, Yuri Fonseca, and Ilan Lobel. Contextual inverse optimization: Offline and online learning. Available at SSRN 3863366, 2021.
[BGP12] Dimitris Bertsimas, Vishal Gupta, and Ioannis Ch Paschalidis. Inverse optimization: A new perspective on the black-litterman model. Operations research, 60(6):1389- 1403, 2012.
[BPP17] John R Birge, Ali Hortaçsu, and J Michael Pavlin. Inverse optimization for the recovery of market structure from market outcomes: application to the miso electricity market. Operations Research, 65(4))837-855, 2017.
[BPP118] Andreas Bärmann, Alexander Martin, Sebastian Pokutta, and Oskar Schneider. An online-leariing approach to inverse optimization. arXiv preprint arXiv: 1810. 12997, 2018.
[BT92] Didier Burton and Ph L Toint. On an instance of the inverse shortest paths problem. Mathematical programming, 53(1):45-61, 1992.
[BV06] Eyal Beigman and Rakesh Vohra. Learning from revealed preference. In Proceedings of the 7th ACM Conference Electronic Commerce, pages 36-42, 2006.
(CDBW21] Minwoo Chae, Pierpaolo De Blasi, and Stephen G Walker. Posterior asymptotics in wasserstein metrics the real line. Electronic Journal of Statistics, 15(2)3633533677, 2021.
[CKK20] Violet Xinying Chen and Fatma Karzan-Kazzan Online convex optimization perspective for learning from dynamically revealed preferences. arXiv preprint arXiv:2008. 2020.
10

---

[DCZ18] Chaosheng Dong, Yiran Chen, and Bo Zeng. Generalized inverse optimization through online learning. Advances in Neural Information Processing Systems, 31, 2018.
[DRS 18] Jinshuo Dong, Aaron Roth, Zachary Schutzman, Bo Waggoner, and Zhiwei Steven Wu. Strategic classification from revealed preferences. In Proceedings of the 2018 ACM Conference Economics and Computation, pages 55-70, 2018.
[DZ20]
Chaosheng Dong and Bo Zeng. Expert learning through generalized inverse multiob- jective optimization: Models, insights, and algorithms. In International Conference Machine Learning, pages 2648-2657 PMLR, 2020.
[GGVDV00] Subhashis Ghosal, Jayanta K Ghosh, and Aad W Van Der Vaart. Convergence rates of posterior distributions. Annals of Statisties, pages 500- 100-531,220 2000.
[GT+ 19] Guillermo Gallego, Huseyin Topaloglu, et al. Revenue management and pricing analytics, volume 209. Springer, 2019.
[WB11]] Arezou Keshavarz, Yang Wang, and Stephen Boyd. Imputing a convex objective function. In 2011 IEEE international symposium on intelligent control, pages 613- 619. IEEE, 2011.
[MESAHK18] Peyman Mohajerin Esfahani, Soroosh Shaficezadel--baadeh, Grani A Hanasusanto, and Daniel Kuhn. Data-driven inverse optimization with imperfect information. Mathematical Programming, 167(1):191-234, 2018.
[Sam48] Paul A Samuelson. Consumption theory in terms of revealed preference. Economica, (5(6))2243 253,, 1948.
[TVRVR04] Kalyan T Talluri, Garrett Van Ryzin, and Garrett Van Ryzin. The theory and practice of revenue management, volume 1. Springer, 2004.
[Va006] Hal R Varian. Revealed preference. Samuelsonian economics and the twenty-first century, pages 99-115, 2006.
[Z1.9]] Jianzhong Zhang and Zhenhong Liu. Calculating some inverse linear programming problems. Journal of Computational and Applied Mathematics, 7222)261-273, 1996.
[ZR12] Morteza Zadimoghaddam and Aaron Roth. Efficiently learning from revealed prefer- ence. In International Workshop on Internet and Network Economics, pages 14-1127. Springer, 2012.


Reviews:
[{"review_id": "ad5l_HZZD4p", "reviewer": "Reviewer_9Dqv", "summary": "The paper considers the stochastic setting where utility comes from some unknown distribution and the goal is to learn the distribution from the utility-maximizing actions of agents. They consider two distributions: Gaussian and delta-corruption. In both settings, they derive Bayesian approaches to learn distribution and provide some theoretical guarantees. They also provide approximation techniques and present some numerical experiments. ", "questions": "I think paper can benefit from broader discussion on tractability and  inaccuracy in high dimension settings.", "limitations": "The authors address the limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strenghts:\nThey motivate the guarantees based on posterior distribution using sound explanation and examples.\n\nWeaknesses:\nThe experiments show that their approximation algorithms are quite weak and accuracy suffers in high dimensions.If we follow the authors argument that the primary reason is curse of dimensionality then this work only helps small dimensional settings.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Uuv4jvOlYNY", "reviewer": "Reviewer_tzej", "summary": "This paper studies the problem of learning utilities from purchasing behavior, or, learning from revealed preference. While multiple papers have studied the sample complexity of backing out a single set of feasible item utilities that explain purchasing data drawn from a distribution, the authors study stochastic revealed preferences: the item utilities themselves are drawn from a distribution, and the dataset consists of purchases with respect to iid draws of the item utilities. The authors consider two main settings: in the first the utilities are drawn from a von Mises-Fisher distribution, in the second there is a deterministic utility vector that explains the purchase w.h.p, but the purchase (with complementary probability) might be explained by a utility vector drawn from an arbitrary distribution (representing a probability-delta corruption). They provide sampling and optimization techniques for both settings, with guarantees, and verify convergence of the learned utility parameters experimentally via actual implementations of the techniques.", "questions": "Is there any relation to the literature on learning stochastic choice? See, e.g., the manuscript “Prediction and Stochastic Choice” on SSRN and references therein. That literature deals mostly with binary preference relations so maybe there’s not much of a relation, but could be worth looking into (I’m not suggesting that these works be cited). ", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I think this is an interesting contribution to the area of learning from choice data. The paper is nicely written and I was able to follow it with no issues. The techniques are interesting: the stochastic nature of the problem makes it more difficult than simply \"backing out\" a feasible utility vector. To this end I found the techniques used to overcome this challenge to be novel and interesting. I also appreciated the fact that the authors directly gave algorithms for arriving at the distribution P_u that could be experimentally verified, rather than stopping at sample complexity bounds.\n\nOne potential weakness is that the paper considers only two somewhat disparate settings, and there are not any connections (as far as I could tell) developed between the techniques used for both settings. It does seem like this setting is challenging and more general remarks would be tougher (e.g. there’s probably no general distribution-independent statement that can be made) but I wonder if there is a more general abstract learnability result in terms of parameters of P_u. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ESoJ82hv0B5", "reviewer": "Reviewer_qew4", "summary": "This paper studies the problem of revealed preference under a stochastic setting. The utility of the agents follows an unknown distribution and we estimate the distribution from only the observation of the utility-maximizing actions of the agents. In this paper, the authors consider two underlying distributions: a Gaussian setting and a $\\delta$-corruption setting, and provide Bayesian approaches for the problems with theoretical guarantees.", "questions": "- A typo in L261, where an extra \"0\" appears at the end of the sentence.\n- Figure 1 plus Figure 2 appears to be too wide.", "limitations": "The authors seem to have addressed the limitations of their work.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths:*\n\n- The paper studies the revealed preference problem under a stochastic setting, where existing analyses assume that the agents share the same utility function.\n- The authors propose Bayesian approaches for two utility function distributions and the method may potentially be extended to other settings beyond Gaussian and $\\delta$-corruption settings.\n- The authors also provide theoretical guarantees to the Bayesian models.\n\n*Weaknesses:*\n\n- The method requires sampling from a high-dimensional space, which incurs the curse of dimensionality that negatively impact the performance of the algorithms.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8-9LCwThzW", "reviewer": "Reviewer_5mMn", "summary": "This paper studies the problem of learning an known utility function via the actions (of an agent) in the stochastic setting, specifically a Gaussian setting and a $\\delta$-corruption setting. Under both settings, methods with theoretical guarantees are proposed to learn the known utility function paramerized by a vector. Two respective algorithms are described and implemented for numerical evaluation to verify the theoretical guarantees (i.e., convergence).", "questions": "- Please see the first Weakness about \"a set of agents\".\n- In Theorem 1, and in lines 130-132, why is it that $b$ no longer has a subcript $t$? What does $b$ (without the subscript $t$) refer to?\n- In lines 137, \"the Wasserstein distance in the theorem is not critical and it can be replaced with other distances such as the total variation distance and the Hellinger distance.\" \n    - Does the bound in the theorem depend on the specific choice of distance in terms of _expression_ and _properties_ (e.g., does it need to be a proper metric)?\n    - If multiple distances are possible, which should be used? In other words, what are some considerations one should make when picking the suitable distance?", "limitations": "The authors have identified in Sec. 5 that the approaches seem to scale poorly w.r.t. the dimension of the problem and argued that it can be mitigated by better and more efficient implementation. It would be good to briefly discuss this (perhaps in Appendix if there is no space) i) to pinpoint the component in the Algorithms that lead to this issue; ii) some intuitions for better implementation (e.g., why would parallel computing improve estimation accuracy, as I thought parallel computing is meant to distribute the computational load).", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper rigorously studies the problem of learning some unknown utility function under the stochastic setting (two specific settings). The problem setting is clearly laid-out and the proposed approaches seem sound (to the best of my ability). In particular, Theorems 1 and 2, provide the necessary theoretical guarantees for the approaches, respectively, which are later empirically verified. Regarding weaknesses, the setting of \"a set of agents\" can be made clearer and the motivation for considering the Gaussian setting and $\\delta$-corruption setting togeher in one paper can be made clearer, too.\n\nStrengths\n- The overall theoretical rigor is good: in problem formulation, discussing the approaches and providing the necessary theoretical guarantees.\n- The presentation is clear (i.e., writing and organization of content).\n\nWeaknesses\n- The setting of \"a set of agents\" is not so clear. A clear contrast (to existing works) this paper claims is \"all the existing algorithms and analyses uder this topic relay on the assumption that all the agents share one common utility function (or a common utility parmeter vector) and thus can fail in the stochastic setting.\"\n    - Are there multiple agents (with different utility functions) at the same time for the learner to learn? Why does stochasticity give rise to multiple utility functions (as opposed to one common utility function), since there is only one true $\\mathcal{P}_{\\mu}$ (for the Gaussian case) or $\\boldsymbol{u}^*$ (for the $\\delta$-corruption case)?\n    - Following this, the motivation of this setting can be made clearer with references in addition to the described use-case in lines 28-30.\n- The motivation for specifically considering both the Gaussian case and the $\\delta$-corruption can be made clearer. Is it a standard approach to consider these two options (if so, are there references for it), or is there a significant motivation for considering these two case together in one paper?\n\n ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept