Learning Thresholds with Latent Values and Censored Feedback

Thanks for your insightful comments with citations. We sincerely appreciate your time in reading the paper and providing useful references. Our point-to-point responses to your comments are given below.

1. The needle in a haystack phenomenon is known and has been used before in the pricing context.

Thank you for this insightful comment! We fully agree with the reviewer that the "needle in a haystack" phenomenon is a known concept. In response to this valuable feedback, we have added additional references in our revised paper to emphasize this phenomenon. However, we wish to clarify that it is more like a high-level idea rather than a panacea that can be used without careful consideration. In [1], they use this idea to give a linear regret lower bound (Theorem 4.4). In [4], they also use this idea to prove matching lower bounds and it is already cited in our original paper. Nevertheless, it is important to note that the specific setups they considered differ from ours, resulting in a distinct concrete construction. In essence, our paper's concrete construction stands independently and does not rely on previous works, highlighting the inherent difficulty of the problem we address.

2. Theorems 4.1 and 4.2 are not surprising: if some regularity or smoothness assumptions are made then the objective becomes Lipschitz in the threshold, and an epsilon grid on the threshold space immediately yields the desired result.

Thank you for this perceptive comment! We acknowledge that proving upper bounds by constructing an epsilon grid under the Lipschitz assumption is a standard approach. We included these results primarily for the completeness of our paper. As mentioned in our introduction, the main technical contribution and novelty of this paper lies in the novel and challenging impossibility result, along with a matching lower bound.

3. Theorem 4.3 is the more involved result but is not too surprising: the construction entails a family of distributions with $\Theta(\frac{1}{\epsilon})$ candidate optimal thresholds where each candidate needs to be evaluated $\Omega(\frac{1}{\epsilon^2})$ times.

Thank you for this thoughtful comment! We wish to clarify that our lower bound is built on the assumption that the value distribution is Lipschitz. Lipschitzness is a double-edged sword that allows a standard solution on the upper bound side but leads to difficulty in the construction of matching lower bound, which we believe is novel in our paper. In contrast to previous works, such as the construction in [3], which built a family of discrete distributions with support on $V = \\{\frac{1}{2}, \frac{1}{2} + \epsilon, \frac{1}{2} + 2\epsilon, . . . , 1 − \epsilon, 1\\}$, and recent work [5], which constructed a family of discrete distributions with support on $V=\\{\frac{1}{2}+ 4\epsilon, \frac{1}{2} + 8\epsilon, …, \frac{3}{4} − 4\epsilon, \frac{3}{4}\\}$, our lower bound result constructs a family of Lipschitz continuous distributions on the interval [0,1].

4. It seems like Theorem 5.1. could be a Corollary of [2] (for the upper bound, once Lipshitzness in the threshold has been established) and [3] (for the lower bound). Is it correct?

Thank you for this interesting question. Not precisely. While the upper bound in Theorem 5.1 does leverage standard techniques from the Lipschitz bandit literature (e.g., [5]), the lower bound, as we mentioned above, does not align with the conventional approach found in previous works, which typically involves constructing a family of discrete distributions. Instead, our unique contribution lies in the ability to construct a family of Lipschitz continuous distributions to establish the lower bound, which is novel and more challenging.

In conclusion, we express our sincere appreciation for the insightful comments accompanied by citations. We believe that our paper's primary contribution, the lower-bound technique, shares high-level similarities (e.g., the idea of “needle in a haystack”) with previous works while exhibiting distinctive and concrete differences, and it makes our lower bound construction challenging and novel.

Reference

[1] Cesa-Bianchi N, Cesari T R, Colomboni R, et al. A regret analysis of bilateral trade[C]//Proceedings of the 22nd ACM Conference on Economics and Computation.

[2] Kleinberg R, Slivkins A, Upfal E. Bandits and experts in metric spaces[J]. Journal of the ACM (JACM), 2019, 66(4): 1-77.

[3] Kleinberg R, Leighton T. The value of knowing a demand curve: Bounds on regret for online posted-price auctions[C]//44th Annual IEEE Symposium on Foundations of Computer Science, 2003.

[4] Leme R P, Sivan B, Teng Y, et al. Pricing query complexity of revenue maximization[C]//Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).

[5] Cesa-Bianchi N, Cesari T, Colomboni R, et al. The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations[J]. arXiv preprint arXiv:2307.09478, 2023.

Thanks for your constructive comments and suggestions, they are exceedingly helpful to improve our paper. We have carefully incorporated them in the revised paper. In the following, your comments are first stated and then followed by our point-by-point responses.

1. Can you provide a few toy examples as running examples to explain the setup and theorems (Table 1)? e.g. concrete distributions under different assumptions, possible $(\epsilon, \delta)$-estimator and corresponding query complexity bounds, etc.

Thank you for this meaningful question. Certainly. We illustrate the setup and theorems using the auction with a reserve price as a running example. In this scenario, the seller, serving as the learner, aims to learn the optimal reserve price for an item. The buyer, acting as the agent, possesses a private value for the item drawn from an unknown distribution and is willing to pay g(\gamma, v) when the reserve price is r, and the value is v. If the function is defined as $g(\gamma, v) = \gamma$ for $v < 1/3$ and $v$ for $v > 1/3$, and the value distribution follows a uniform distribution, the reward function is monotone but not Lipschitz, while the value distribution is Lipschitz. This corresponds to Theorem 4.1. On the other hand, if $g(\gamma, v) = \gamma$, the reward function is Lipschitz, aligning with Theorem 4.2. Moreover, the example corresponding to Theorem 4.3 is included in the proof, where $g(\gamma,v)=\gamma$ and the value distribution is a “hard” distribution.

2. It would be good to show empirical results that verify the theoretical results. Additionally, it would be even better if the toy example could correspond to the motivation example provided in the paper.

Thank you for this helpful comment! As you suggested, we have performed experiments within the mentioned examples which indeed can correspond to the motivation example provided in the paper. For the upper bound, we used the aforementioned two toy examples that fit the conditions in Theorem 4.1 and Theorem 4.2 respectively, and showed the relationship between the empirical loss and the number of queries (Please see toy example 1 and toy example 2). For the lower bound, we used the example in the proof of Theorem 4.3, where $g(\gamma,v)=\gamma$ and the value distribution is a "hard" distribution (Please see hard distribution). We fixed some $\epsilon$ and ran simulations to see the minimum number $n$ of queries that are necessary to learn the optimal threshold within $\epsilon$ additive error. Then we computed the logarithmic ratio $\frac{\ln n}{\ln\frac{1}{\epsilon}}$ and found it converging to 3, which verifies our lower bound $\tilde{\Omega}(\frac{1}{\epsilon^3})$ (Please see lower bound example). For more details, please refer to Appendix E of the revised paper. For more details, please refer to Appendix E of the revised paper.

3. It is not clear how the theoretical results provided in Table 1 and Section 5 (online learning) compare with related/previous work. In related work, the authors mentioned a few closely related works, it would be helpful to provide a detailed discussion or comparison when applicable.

Thank you for this instructive comment. Certainly. We have enhanced the discussion in the related work section of the paper to include a more detailed comparison with closely related works, as you suggested. Particularly, we have added related work about the continuous-arm one-sided Lipschitz bandit problem.

Thanks for your constructive comments and suggestions, they are exceedingly helpful in improving our paper. We have carefully incorporated them in the revised paper. In the following, your comments are first stated and then followed by our point-to-point responses.

1. The proof of the main query complexity upper bound in Theorem 4.1 doesn’t seem too surprising. Under conditions on the distribution, concentration bounds allow the true reward at any given threshold point to be sufficiently estimated, and then the learner runs that estimation for a suitable discretization of possible threshold values.

Thank you very much for this insightful comment. We acknowledge that the proof of the main query complexity upper bound in Theorem 4.1 employs a standard discretization method. However, it's important to note that the primary technical contribution of our paper lies in presenting novel and challenging impossibility results, along with a matching lower bound, as mentioned in our introduction. Besides we have addressed your question about the Lipschitz constant in the proof of Theorem 4.1, please see our response for the fourth comment, and the details are in our revised paper. We believe these aspects significantly contribute to the overall significance of our work.

2. Are there specific examples of reward functions g that the authors can give that fit the different conditions of their main theorems? If such examples could be further motivated in the context of the other two examples (crowdsourced data collection and hiring) presented, that would solidify the premise of the paper.

Thank you for this valuable question. Here are specific examples of reward functions $g$ that fit different conditions. For g being monotone but not Lipschitz, please refer to the specific g in our impossibility result (Theorem 3.1). For $g$ being Lipschitz but not monotone, consider $g(\gamma, v) = v\gamma + (1 - v)v$, which is not monotone with respect to $v$. For g being both monotone and Lipschitz, consider $g(\gamma, v) = \gamma$, $g(\gamma, v) = v$, and $g(\gamma, v) = c\gamma + (1 - c)v$ for some constant $c$.

The primary focus of our paper is addressing the challenge of learning the optimal threshold when faced with an unknown reward function $g$. In the context of the other two examples (crowdsourced data collection and hiring), it is more practical to assume that the employer or taskmaster does not know the specific form of $g$. Nevertheless, we offer interpretations for these examples. In the crowdsourced data example, the reward function $g(\gamma, v) = \gamma h(v)$ can be interpreted as follows. Here, the threshold corresponds to the normalized number of questions (ranging from 0 to 1) in a single task, while the value corresponds to the maximum number of questions the agent is willing to answer. In practical terms, an agent willing to engage with more questions may be inclined to provide more detailed information for each question. Consequently, the reward for each question becomes a monotone function with respect to $v$, denoted as $h(v)$. Thus, the overall reward function takes the form $g(\gamma, v) = \gamma h(v)$. In the hiring example, $g(\gamma, v) = c\gamma + (1 - c)v$ could represent the reward being between the ability bar (threshold) and the employee's actual ability, reflecting the real-world scenario where individuals may not fully utilize their potential.

3. I think the authors should include all parameters such as the Lipschitz constant $L$ in their query complexity bounds.

Thank you for this instructive comment. We have included the Lipschitz constant $L$ in our query complexity bounds in our revised paper. Apart from $L$, the only other parameters considered in our analysis are $\epsilon$ and $\delta$, which we also included. Your attention to detail is appreciated.

4. Is there any way to remove the assumption in Theorem 4.1 that the learner knows L, or could that lead to exponential/infinite query complexities?

Thanks for this insightful question! Our current sample complexity result in Theorem 4.1 can be extended to the setting where the learner does not know the Lipschitz constant. We have included the result and proof in the Appendix D of the revised paper. The high-level idea is as follows. Instead of constructing a uniform-grid discretization set that depends on $L$, we can adaptively construct a discretization set where the expected rewards of adjacent two points differ at most $\epsilon$. The new query complexity upper bound is $O(\frac{1}{\epsilon^3}\log\frac{L}{\epsilon}\log\frac{\log\frac{L}{\epsilon}}{\epsilon\delta})$, which improves the $\frac{L}{\epsilon^3}$ to $\frac{1}{\epsilon^3}$ while has an additional $\log L$ terms compared with the case that we know $L$. We hope our response can address your main concerns and further verify the technical contribution of our paper.

Thanks for your encouraging words and constructive comments. We sincerely appreciate your time in reading the paper and our point-to-point responses to your comments are given below.

1. The applications discussed in the introduction could be expanded with more practical details. For example, how do different auction formats correspond to different functions $g$?

Thank you for pointing out the need for more practical details in the introduction. These details are indeed discussed in Section 2, specifically in Examples 2.1, 2.2, and 2.3. Example 2.1 demonstrates how different auction formats are represented through distinct $g$ functions.

2. The high-level ideas and intuition could be emphasized more.

Thanks for your suggestion! We have included the high-level idea of Theorem 4.3 before its proof in our revised paper.

3. Some simple experiments on synthetic data would help support the theoretical results.

Thanks for your suggestion! We have conducted experiments on synthetic data with different assumptions, to provide additional support for our theoretical results. For the upper bound, we chose two toy examples that fit the conditions in Theorem 4.1 and Theorem 4.2 respectively, and showed the relationship between the empirical loss and the number of queries (Please see toy example 1 and toy example 2). For the lower bound, we used the example in the proof of Theorem 4.3, where $g(\gamma,v)=\gamma$ and the value distribution is a "hard" distribution (Please see hard distribution). We fixed some $\epsilon$ and ran simulations to see the minimum number $n$ of queries that are necessary to learn the optimal threshold within $\epsilon$ additive error. Then we computed the logarithmic ratio $\frac{\ln n}{\ln\frac{1}{\epsilon}}$ and found it converging to 3, which verifies our lower bound $\tilde{\Omega}(\frac{1}{\epsilon^3})$ (Please see lower bound example). For more details, please refer to Appendix E of the revised paper.