We study contextual search, a generalization of binary search in higher dimensions, which captures settings such as feature-based dynamic pricing. Standard game-theoretic formulations of this problem assume that agents act in accordance with a specific behavioral model. In practice, however, some agents may not subscribe to the dominant behavioral model or may act in ways that seem to be arbitrarily irrational. Existing algorithms heavily depend on the behavioral model being (approximately) accurate for all agents and have poor performance in the presence of even a few such arbitrarily irrational agents. We initiate the study of contextual search when some of the agents can behave in ways inconsistent with the underlying behavioral model. In particular, we provide two algorithms, one based on multidimensional binary search methods and one based on gradient descent. We show that these algorithms attain near-optimal regret guarantees in the absence of irrational agents and their performance degrades gracefully with the number of such agents, providing the first results for contextual search in any adversarial noise model. Our techniques draw inspiration from learning theory, game theory, high-dimensional geometry, and convex analysis.
翻译:我们研究上层环境搜索,即二进制搜索的概括化,它捕捉了地貌动态定价等环境。标准的游戏理论配方假定代理人按照特定的行为模式行事。然而,在实践中,一些代理人可能不认同主要的行为模式,或可能采取似乎不合理的方式。现有的算法在很大程度上取决于行为模式是否(大约)准确适用于所有代理人,即使有少数这种任意不合理的代理人,其性能也很差。当一些代理人的行为方式与基本的行为模式不一致时,我们开始研究背景搜索。特别是,我们提供了两种算法,一种基于多层面的二进制搜索方法,一种基于梯度下降。我们表明,这些算法在没有非理性的代理人及其性能的情况下,几乎实现了最佳的遗憾保证,这些代理人的数量与此类代理人的数量相比优异,为在任何对抗性噪音模型中进行背景搜索提供了初步结果。我们的技术从学习理论、博学理论、高尺度的几何学和康韦克斯分析中得到灵感。