Learning Thresholds with Latent Values and Censored Feedback
Jiahao Zhang Tao Lin Weiqiang Zheng Zhe Feng Yifeng Teng Xiaotie Deng
In this paper, we investigate a problem of actively learning threshold in
latent space, where the unknown reward $g(\gamma, v)$ depends on the proposed
threshold $\gamma$ and latent value $v$ and it can be $only$ achieved if the
threshold is lower than or equal to the unknown latent value. This problem has
broad applications in practical scenarios, e.g., reserve price optimization in
online auctions, online task assignments in crowdsourcing, setting recruiting
bars in hiring, etc. We first characterize the query complexity of learning a
threshold with the expected reward at most $\epsilon$ smaller than the optimum
and prove that the number of queries needed can be infinitely large even when
$g(\gamma, v)$ is monotone with respect to both $\gamma$ and $v$. On the
positive side, we provide a tight query complexity
$\tilde{\Theta}(1/\epsilon^3)$ when $g$ is monotone and the CDF of value
distribution is Lipschitz. Moreover, we show a tight
$\tilde{\Theta}(1/\epsilon^3)$ query complexity can be achieved as long as $g$
satisfies one-sided Lipschitzness, which provides a complete characterization
for this problem. Finally, we extend this model to an online learning setting
and demonstrate a tight $\Theta(T^{2/3})$ regret bound using continuous-arm
bandit techniques and the aforementioned query complexity results.