Learning the Valuations of a $k$-demand Agent
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 $k$-demand agent, whose valuation over the goods is additive when receiving up to $k$ goods, but who has no interest in receiving more than $k$ 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 $\widetilde{O}(k)$.
Code (0)
등록된 구현이 없습니다.
Tasks
Active LearningSimilar Papers 제목 키워드 기반
Probing EFX via PMMS: (Non-)Existence Results in Discrete Fair Division
We study the fair division of indivisible items and provide new insights into the EFX problem, which is widely regarded as the central open question in fair division, and the PMMS problem, a strictly stronger variant of …
AgentGym2: Benchmarking Large Language Model Agents in De-Idealized Real-World Environments
Language agents, i.e., LLM agents, progress rapidly and are increasingly deployed in production environments. This trend underscores the urgent need for rigorous and realistic evaluations. However, most existing benchmar…
Navigation Pixie: Implementation and Empirical Study Toward On-demand Navigation Agents in Commercial Metaverse
While commercial metaverse platforms offer diverse user-generated content, they lack effective navigation assistance that can dynamically adapt to users' interests and intentions. Although previous research has investiga…
Optimizing Cooperative path-finding: A Scalable Multi-Agent RRT* with Dynamic Potential Fields
Cooperative path-finding in multi-agent systems demands scalable solutions to navigate agents from their origins to destinations without conflict. Despite the breadth of research, scalability remains hampered by increase…
Computational EfficiencyMulti-Agent Path FindingNavigateRTSGameBench: An RTS Benchmark for Strategic Reasoning by Vision-Language Models
Modern Vision-Language Models (VLMs) often struggle with strategic reasoning, i.e., anticipating and influencing other agents' actions, under uncertainty in competitive and cooperative settings. Real-time strategy (RTS) …