Learning Thresholds with Latent Values and Censored Feedback

本文研究了在潜在空间中积极学习阈值的问题，其中未知的奖励$g(\gamma, v)$取决于所提出的阈值$\gamma$和潜在值$v$，只有当阈值低于或等于未知的潜在值时才能获得。该问题在实际场景中具有广泛的应用，例如在线拍卖中的保留价格优化、众包中的在线任务分配、招聘中的设定招聘门槛等。我们首先表征了学习阈值的查询复杂度，使得期望奖励最多比最优解小$\epsilon$，并证明了即使$g(\gamma, v)$在$\gamma$和$v$方面都是单调的，所需的查询次数也可能是无限的。在积极的一面，我们提供了一个紧密的查询复杂度$\tilde{\Theta}(1/\epsilon^3)$，当$g$是单调的且价值分布的CDF是Lipschitz时。此外，我们展示了一个紧密的$\tilde{\Theta}(1/\epsilon^3)$查询复杂度可以被实现，只要$g$满足单侧Lipschitzness，这为这个问题提供了一个完整的描述。最后，我们将这个模型扩展到在线学习环境中，并使用连续臂赌博技术和上述查询复杂度结果展示了一个紧密的$\Theta(T^{2/3})$遗憾界。

本文研究在潜在空间中主动学习阈值的问题，其中未知的奖励取决于建议的阈值和潜在值，并且仅当阈值小于或等于未知的潜在值时才能获得。这个问题在实际场景中有广泛的应用，如在线拍卖中的保留价优化，众包中的在线任务分配，招聘中的招聘标准设置等。

本文提出了一种算法，可以在一定的查询复杂度下学习到最优阈值，并证明了在满足一定条件下，可以达到最优的查询复杂度。

本文提供了紧密的查询复杂度证明，证明了当奖励函数满足一定条件时，可以达到最优的查询复杂度。同时，将模型扩展到在线学习中，并使用连续臂赌博机技术和上述查询复杂度结果证明了一个紧密的遗憾界。

最近在这个领域中，还有一些相关的研究，如《Active Learning with Partially Known Thresholds》和《Learning to Optimize Reserves in Second-Price Auctions with Unknown Value Distributions》。