Poster
Learning the Valuations of a -demand Agent
Hanrui Zhang · Vincent Conitzer
Virtual
Keywords: [ Active Learning ] [ Game Theory and Mechanism Design ] [ Learning Theory ] [ Statistical Learning Theory ]
Abstract:
We study problems where a learner aims to learn the valuations of an agent by observing which goods he buys under varying price vectors. More specifically, we consider the case of a -demand agent, whose valuation over the goods is additive when receiving up to goods, but who has no interest in receiving more than goods. We settle the query complexity for the active-learning (preference elicitation) version, where the learner chooses the prices to post, by giving a {\em biased binary search} algorithm, generalizing the classical binary search procedure.
We complement our query complexity upper bounds by lower bounds that match up to lower-order terms. We also study the passive-learning version in which the learner does not control the prices, and instead they are sampled from some distribution. We show that in the PAC model for passive learning, any {\em empirical risk minimizer} has a sample complexity that is optimal up to a factor of .
Chat is not available.