Learning Thresholds with Latent Values and Censored Feedback
Authors: Jiahao Zhang
Tao Lin
Weiqiang Zheng
Zhe Feng
Yifeng Teng
Xiaotie Deng
Venue: ICLR 2024 poster (2024)
Keywords: Threshold
Latent Value
Censored Feedback
Query Complexity
Primary area: learning theory

Abstract: 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.

Published as a conference paper at ICLR 2024
LEARNING THRESHOLDS WITH LATENT VALUES AND CENSORED FEEDBACK
Jiahao Zhang 1.2 Tao Lin', Weiqiang Zheng", Zhe Feng". Yifeng Teng'. Xiaotie Deng ..2
'School of Electronics Engineering and Computer Science, Peking University
CFCS, Peking University 'Harvard University 'Yale University Google Research
{jiahao. , zhang, xiaotic edu, en, tlinag
mlingg.harvard.o hwwvarad edu, weiqiang. zhengeyaLe. {zheš, (.ffeng]@@google com
ABSTRACT
In this paper, we investigate a problem of actively learning threshold in latent space, where the unknown reward 9(7, v) depends on the proposed threshold Y and latent value e and can be achieved only 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 online auctions, online task assign- ments in crowdsourcing, setting recruiting bars in hiring, etc. We first characterize the query complexity of learning a threshold with the expected reward at most e smaller than the optimum and prove that the number of queries needed can be in- finitely large even when g(7, v) is monotone with respect to both and v. On the positive side, we provide tight query complexity Ô(1/=²) when g is monotone and the CDF of value distribution is Lipschitz. Moreover, we show that a tight @(1/E²) query complexity can achieved as long as g satisfies right Lipschitz- ness, which provides complete characterization for this problem. Finally, we extend this model to an online learning setting and demonstrate a tight (T22/3) regret bound using the aforementioned query complexity results.
INTRODUCTION
The thresholding strategy is widely used in practice, e.g., setting bars in the hiring process, setting reserve prices in online auctions, and setting requirements for online tasks in crowdsourcing, due its intrinsic simplicity and transparency. In addition, the practical scenarios mentioned above, the threshold can be only
latent space, which makes the problem more challenging:
In hiring, the recruiter wants to set recruiting bar that maximizes the quality of the hires without knowing the true qualifications of each candidate.
In online auctions, the seller wants to set a reserve price that maximizes their revenue. However, the seller does know the true value of the item being auctioned.
crowdsourcing, the taskmaster wants to set a requirement (e.g., the number of questions that need to be answered) for each task so that the tasks can be assigned to qualified workers who have a strong willingness to complete the task, but has no access to the willingness of each worker. The target of the taskmaster is to collect high-quality data much as possible.
Although the latent value cannot be observed, it will affect the reward jointly with the threshold. In the examples above, the reward is the quality the hire, revenue from the auction, or the quality of the collected data. In some cases, the reward only depends on the latent value as long as the value is larger than the threshold, e.g., the quality of the hire may only depend on the intrinsic qualification and skill level of the candidate long she passes the recruiting bar, the revenue in second price auction only depends on the value since the bidders will report truthfully regardless of the reserve price. However, the threshold does play important role in other settings, e.g., the winning bid in

---

Published as a conference paper at ICLR 2024
the first price auction relies and increases with the reserve price in general (Krishna, 2010) thus the revenue highly depends on both reserve price and latent value. Similarly, in crowdsoureing, the requirements of the tasks directly affeet the quality of data collected by the taskmaster. In this work, we consider a general framework where the reward can depend on both threshold and latent value.
Another difficulty in setting proper threshold is to balance the per-entry reward and capability. For example, in hiring, setting a higher recruiting bar can guarantee the qualification of each candidate and thus the return the company. However, a too-high bar may reject all candidates and cannot fit the position needs. To balance this tradeoff, the threshold needs to be set appropriately.
1.1 OUR MODEL AND CONTRIBUTION
An informal version of our model In this work, we propose a general active learning abstraction for the aforementioned thresholding problem. We first provide some notations of the model con- sidered in this paper to facilitate the presentation. Let g(7, o) be the reward function that maps the threshold 7 [0, 1] and latent value v E [0, 1] to the reward, where 9(7, v) can be observed if and only if y I v. We assume that the latent value follows an unknown distribution and we can only observe the reward (as long as y v) but not the value itself. We investigate the query complexity of learning the optimal threshold in the latent space: the number of queries that are needed to learn threshold with expected reward at most smaller than the optimum.
Our contributions The first contribution in this work is an impossibility result for this active learning problem. We prove that the query complexity can be infinitely large even when the reward function is monotone with respect to the threshold and the value. Our technique is built upon the idea of "needle in the haystack". Intuitively, a higher threshold o gives a higher reward g(7, e) because of the monotonicity but decreases the probability of getting a reward which can only be achieved if y S v. This tradeoff allows us construct an interval that has an equal expected utility. We find that if the reward function has a discontinuous bump at some point in the interval and the value distribution has a mass exactly at the same point, then the expected utility at this point will be constantly higher than the equal expected utility. Therefore we can hide the unique maximum ("needle") in an equal utility interval ("haystack"), which makes the learner need infinite queries to learn the optimal threshold.
Our second contribution a series of positive results with tight query complexity up to logarithmic factors. We consider two special cases with common and minor assumptions: (1) the reward function monotone and the CDF of value distribution is Lipschitz and (2) the reward function is right- Lipschitz. With each of the two assumptions, we can apply a discretization technique to prove an )(5) upper bound on the query complexity of the threshold learning problem. We also give matching lower bound, which is technically more challenging: least S queries are needed to find an e-optimal threshold, even if the reward function is both monotone and Lipschitz and the value distribution CDF is Lipschitz. Previous papers like Kleinberg & Leighton (2003); Leme et al. (2023b) do not require the value distribution to be Lipschitz, which makes it much easier to construct a value distribution with point mass to prove lower bounds. To prove our lower bound with strong constraints on the reward function and distribution, we provide a novel construction of value distribution by careful perturbation of a smooth distribution. We summarize our main results in Table 1.
Finally, we extend the threshold learning problem to an online learning setting. Relating this problem to continuous-armen Lipschitz bandit, and using the aforementioned query complexity lower bound, we show a tight (TT2/3) regret bound for the online learning problem.
1.2 RELATED WORKS
The most related work is the pricing query complexity of revenue maximization by Leme et al. (2023b;a). They consider the problem of how many queries are required to find an approximately optimal reserve price in the posted pricing mechanism, which is a strictly special case of our model by assuming 9(7,0) 7. Our work also relates to previous work about reserve price optimization in online learning settings, e.g., Bosa--Banchi et al. (2014); Feng et al. (2021), who consider revenue maximization in the online learning setting, where the learner can control the reserve price each
2

---

Published as a conference paper at ICLR 2024
Table 1:
Our results the query complexity of learning optimal threshold. Rows correspond to
reward functions and columns value distribution. Ó(-) ignores poly-logarithmie factors.
Lipschitz
General
Reward / Value
lower bound
upper bound
lower bound
upper bound
Infinite
Monotone
Ö(2b)
Theorem 3.1
Theorem 4.3
Theorem 4.1, 4.2
((+)
+
Right-Lipschitz
Theorem 4.3
Theorem 4.2
round. Our work is loosely related the sample complexity of revenue maximization (e.g.. (Cole & Roughgarden, 2014; Morgenstern & Roughgarden, 2015; Gonczarowski & Nisan, 2017; Guo et al., 2019; Brustle al., 2020)). They focus on learning near-optimal mechanisms, which lies in the PAC learning style framework. Whereas, our work characterizes the query complexity in the active learning scenario.
Technically, our work is inspired by high-level idea called "the needle in the haystack", which was first proposed by Auer et al. (1995) and also occurred recent works such as online learning about bilateral trade (Cesa-Biie Bianchi et al., 2021; 2023a), first-price auction (Cesa-Bianch) Bianchi et al., 2023b), and graph feedback (Eldowa et al., 2023). Nevertheless, this idea is only high-level. As we will show in the proofs, adopting this idea to prove our impossibility results and lower bounds is not straightforward and requires careful constructions.
Additionally, work is related to works censored/rruncated data and the Lipschitz bandit prob- lem. We leave them to the Appendix A.
2 MODEL
We first define some notations. For an integer n, [n]] denotes the set f1.2...., n). 1 is the indi- cator function. We slightly abuse notation use F to denote both distribution and its cumulative distribution function (CDF).
We study the query complexity of learning thresholds with latent values between learner and an agent. The latent value t represents the agent's 's private value and is drawn from an unknown distri- bution F supported on [0, 1]. In each query, the learner is allowed to choose threshold y E [o, 1]; then with fresh sample v ~ F, the learner gets reward feedback b determined by the threshold and the value
6(7, = [g(7,0) v)
u if
(1)
where g [0, 1j2 - [0, 1] is an unknown reward function. The notation b(>) = b(7, v) denotes F. The learner's goal is to learn optimal threshold
random reward with randomness y E [0. 1] that maximizes its expected reward/utility ((y) defined as
U(>) E b(y, v)] = E.-F [9(7, v) 1.27].
(2)
Typically, higher threshold decreases the probability of getting a reward but gives a higher reward the value exceeds the threshold. Our model of learning optimal thresholds with latent value captures many interesting questions, as illustrated by the following examples.
Example 2.1 (reserve price optimization). A seller (learner) repeatedly sells a single item to a set of n bidders. The seller first sets reserve price (threshold) n. Each bidder then submits bid by The bidder with the highest bid larger than " wins the item and pays their bid; if no bidder bids above 7 the item goes unallocated. Each bidder i has a private valuation v; [0, 1] for the item, where each value o; is drawn independently (but not necessarily identically) from some unknown distribution. If the seller adopts the first-price auction, only the highest bid matters for both allocation and payment. We denote the maximum value (latent value) ((1) A vs and (1)
3

---

Published as a conference paper at ICLR 2024
is drawn from a unknown distribution. Then we only consider this representative highest bidder (agent).' The unknown bidding function (reward function) 9 and g(),,(") is the maximum bid when the reserve price is ? and the maximum value is e(1), If the seller adopts the second-price auction, only the second-highest value matters for both allocation and payment. We denote the second highest value (latens value) u(2) and vl2? is drawn from an unknown distribution. Similarly, we only need to consider the second-highest bidder (agent). Because bidders in the second price auction bid truthfully, it has a bidding function (reward function) g with g(7, (())) = = for all Y, 7,u(2) E [0, 1] and v/(2) 2 "I- If the seller faces a single bidder (agent) and adopts a posted price auction, we have g(7,, = 7 as the bid when the reserve price is Y and the bidder's 's value v.
Example 2.2 (crowdsourced data collection). Data crowdsourcing platforms typically allow users (agent) to sign up and complete tasks in exchange for compensation. These tasks might involve answering questions. providing feedback, or rating products. The taskmasters (learner) need to decide how many questions should be included in each task or how detailed the feedback should be. We denote such difficulties (threshold) of the task r.. The users have individual willingness (latent value) v to complete the task. The willingness followw a specific probability distribution, which is unknown to the taskmasters or platform. Typically, more difficult task decreases the probability of getting feedbuck from the users but gives a higher reward if the users are willing to complete the lasks because more detailed information can be included when using a more difficult task. We use the notation g(7, v) to represent the reward when the difficulty of the task is ry and the user's s willingness is v.
Example 2.3 (hiring bar). A company (learner) sets a predefined bar (threshold) y for candidate admission. These candidates (agents) have individual measurements (latent value) u. which reflects their inherent ability. They will apply to the company if and only if they think of themselves as qualified, namely, e 2 7/- The measurements follow specific probability distribution, which is unknown to the company. A candidate with a measurement v admitted with a hiring bar pproduces an output (reward) g(7; v) to the company.
We assume that the value distribution F belongs to some class C, and the reward function g belongs to some class G. The classes C and G are known to the learner. The learner makes queries adaptively and then outputs a threshold 7 E [0, 1] according to some algorithm A, namely, "/-- = A(TI, bi. Yt-1, b1) b, = b(Te, vz), Vt E [mm]. and 9 = A(TI, .i..... Tiu bm).
Definition 2.1 ((e, esstimatt)))). An (c, (e,5))esttmattn (for C and G) is an algorithm A that, for any F E C.C E G, can output a 9t satisfying (+)) 2 (77)) - with probability at least 1-6 8 using m queries (where the randomness is from .i...., Um ~ F and the internal randonness of A).
Definition 2.2 (query complexity). Given C, 9, for any 0 and E (0, 1). the query complexity QCc,g(E, 8) is the minimum integer m.for which there exists an (5,8)- -esttimator
The query complexity depends on both the value distribution class C and the reward function class g. In this work, we will consider two natural classes of value distributions: (1) CALL. the set of all distributions supported on [0, 1): (2) CLIP, the set of distributions on [0, 1] whose CDF F is I Lipschitz continuous. And we consider two types of reward functions: monotone and right-Lipschitz (with respect to 7). Specifically, for any fixed v E [0, 1]. define projection gu 2 g(s v), which is a one dimensional function of 7 E [0, v). Let MONO be the set of reward functions y whose projection ge is weekly increasing (w.I.t.y) for all v E 1). For the Lipschitzness, we define:
Definition 2.3 (Lipschitzness), A one dimensional function f is
[L>)eff--iipschizz for all x, y E dfom(f) with x S
[() 2 r).
(Z-)right-Liipshitz, for all x. y dom(s) with x S y. f(y) - M x).
one-sided Lipsciise if it is either (L- (L-Jleft-Lipschit or (L-)rightt-ipshne Lipscchh if is both left- and right-Lipshirz.
Let LIIGHT (Gr.p) be the set of reward functions whose projection Je is right-Lipschitz (Lips- chitz) for all v E [0, 1]. Monotonicity and right Lipschitzness are natural assumptions of the reward functions. In the above examples, the rewards (quality of the hire, revenue, and the quality of col- lected data) are all weakly increasing with respect to the thresholds (hiring bar, reserve price, and the difficulty of the requirement). For Lipschitz functions, one can see Duetting et al. (2023) for some practical examples.
'This reduction is proved to he without loss of generality in Feng et al. (2021).
4

---

Published as a conference paper at ICLR 2024
3 IMPOSSIBILITY RESULT: MONOTONE REWARD FUNCTION AND GENERAL VALUE DISTRIBUTION
In this section, we investigate the query complexity of learning the optimal threshold for general value distributions. We show that even when the reward function is monotone with respect to both the threshold and the latent value an (E, -estimatoo cannot be learned with finitely many queries, even for a constant E =
Theorem 3.1. For any 8 E (0, and & S 1 g. the query complexity QC (e, is infinite.
High-Level Ideas To prove the theorem, we carefully construct of pairs of monotone reward function and value distribution (go. Fa) E GMONO x CALL.. parameterized by a E that the utility function (7) has unique maximum point at 7" any y & a. To learn an E-approximately optimal threshold, the learner must find the point " = a. But there are infinitely many possible values for ( _), and our construction ensures that the learner cannot determine the exact value of a from the feedback of finitely many queries.
9 ) such that 2 T0
and U(7) U (a)
for
Proof. Fix any a ( 1e). We define value distribution Fa with the following CDF:
0
o [0, 2
v E 2 2.a) V E [a, 1)
(e)
16v
v= 1.
More specifically, Fa consists of the following four parts: (1) A point mass at }:: P(v 1)) ) : (2)
Continuous CDF over the interval (3, a): = : (3) A point mass at o: P(r = a) 16a7
3
(4) A point mass at 1: PP(u = 1) = 2. Then we define a reward function Ja that is monotone with respect both the threshold y and the latent value
E (0,,),, 00,
15
16
3
E (0,),
15
Ia (r,))))
8
16
7
7 E
[a, [0, T6
7 E 1,,1),
(1
Now we can compute the expected utility (7) when the learner chooses the threshold y E [0, for the reward function Ja and value distribution F.. We have
when 7 E [0, $). the utility is (7) = 1 + 16 < :/4
when y E (}. at), the utility is (T( = (F(a) F(())
- =
18
when = a, the utility is (n(7) a P/v al
T6
when E (ox, 1J. the utility is (7) = 2
Therefore, (7) is maximized at 7" a, and for any 7 + a, it holds that (a - Un(T) $.
To approximate the optimal utility within = 8 error, the learner must learn the exact value of a. However, the following claim shows that when a learner chooses any threshold 7 E [0. 1]. it only observes censored feedback in (v, 03.
Claim 3.1. When the learner chooses y E [0, it observes feedback in (0.7, 7.
5 1.1).
Proof. We consider two cases. If the learner chooses threshold y < a, the learner only receives feedback in (5. 7, 0} depending on the latent value v: if 2 15 I6. the learner receives go v) =
w- 3 = 1- 8 x:
5. (2) if y S 1/2 < Té the learner receives Ja (7, v) = 7: (3) if u < 7, the learner
15
receives 0. Similarly, if the learner chooses threshold 7 a, the learner only receives feedback
in 1. (1) if >
I6 the learner receives ga (1. = if 7, the learner receives 0. This proves the claim.
10 the learner receives go (7, v) = v = 1; (2) if 7 < < 15
16.
Note that the above results holds for all E (}) ) By properties of (7) and Claim 3.1, learner is not able to output the exact value of using finite queries with feedback only in {0, 7, 5 1) against infinitely many pairs of (Fagga) for E (2) ).
5
n
5

---

2. the total query complexity is Published as a conference paper at ICLR 2024
4 TIGHT QUERY COMPLEXITY FOR THE LIPSCHITZ CASES
4.1 MONOTONE REWARD FUNCTION AND LIPSCHITZ VALUE DISTRIBUTION
The negative result in Section 3 implies that we need more assumptions on the reward function g or the value distribution F for the learner to learn the optimal threshold in finite queries. In this subsection, we keep assuming that & is the class of monotone functions w.r.t. y and further assume that C is the class of Lipschitz distributions. We argue that the monotonicity of g and the Lipschitzness of F guarantee that the gap between the expected utility of two thresholds can be bounded by the gap between their CDFs.
Lemma 4.1. With E GMONO and F E CLIP. the expected ulility function U satisfies that U(Y2) U(m) 2 (72) F(n)) for any 0 I 71 S 72
Then we show that Ō queries are enough to learn the optimal threshold. And this can be achieved even if the learner does not know the Lipschitz, constant L of the value distribution F.
Theorem 4.1. For GMONO and CLIP, we have
L
log Eg
@Cenooo. Cur (c, 50 log
log
Proof. If the learner chooses threshold y and makes m queries with the same threshold 7, it will observe m i..dd samples by (7), b2(7)....,, b.. (m)()) (7). b(7), v)) where the empirical distribution: G. Σ 1.,())5 By the DKW inequality (Lemma B. I), if the log 81 then with probability at least 1 8' we have
Here we use (x(7) to denote the random variable F. Let G-y be the CDF of the distribution of by()). Let G₂ be the CDF of
number of queries m reaches ( g²
(z)x) - Gz( S Vo E R.
By Tonelli's theorem, U(7) Bb [b())] fo P((()) fjdt= So (t)
Define ((7) = So' (1 (t) Then have
-())
- (G,(0) ( (C,(0) se.
1
(3)
This means that, after O log 4t) queries at the same point y, we can learn the expected utility of threshold y in e additive error with probability at least 8'.
Next, we will adaptively build a discretization set A C
[0, 1] without knowing the Lipschitz constant
I such that (1) A = 42, ... 1 where 0 T1
< x2 < < FIpAl = and [T =
(2) & < F(++1)) - F(x,) < E for i = 1, 2, :.. [ 1. O()):
By Chernoff bound, we know that O log }) queries are sufficient to learn F(x) with f ad- ditive eиror for any
[0, 1]. At step let L' = {0}. At step n 1, assuming I'A {21, ( .2,,.. Tn,..., and the estimations of corresponding CDF f (x1). F (x22. F(,,,,,-,,,,)) are com- puted. Let In-1 max ma. Then we use binary search to find the next element Vn satisfy- ing 2- - <<<FF F(an)
The binary search works because the empirical CDF function F monotone. Note that we can al- ways find such In within Oflog 4) points because of the Lipschitzness. Overall, to build T we need to estimate n = O(log (Ta)) oe log ()) points of the value distribution. By union bound, to successfully build aa with probability
3
F(Fn-1)
25 S and hence 5 F(x.) F(xn-1)
O(n 1/2 log #) O log log Log 4
Once A built, we make ( log have with probability at least 1 - || शा = =1- & the estimate (()) satisfies (Ū()) -U)) S
2[Al for each threshold 7 E TA- By the union bound, we
for every threshold 7 TΛ. Since |a O we need |[ O log [Ta))) 0 log )

---

Published as a conference paper at ICLR 2024
queries in total. Then, y arg ye (T)) be the optimal threshold in [0, 1] for U(y) and let 7-' = arg MAX (2) be the optimal threshold in l'A for Ü(7). And let " E T' such that 7- < 7" S Tr.800 80 < ((+)) ) F(>*) < e. Then, we have the following chain of inequalities:
U 2 (19)) Delinition of
(4)(3) (3)
Eq
2
Ü(Tr)
U -2
Lemma 4.1
2 U(>') - 3E.
We conclude that 5- is a 3e-optimal threshold with probability 1
4.2 RIGHT-LIPSCHITTZ REWARD FUNCTION AND GENERAL VALUE DISTRIBUTION
In this section, we first show that the expected utility function is right- when the class of right-Lipschitz continuous reward function and C is the class of general distribution.
Lemma 4.2. Suppose reward function g GIIP then the expected reward function U is right- Lipschitz continuous.
Then assuming that know the Lipschitz constant L, apply similar discretization method in Theorem 4.1 to provide an upper bound.
Theorem 4.2. For the class of
reward functions GRIGHT-LIP and general distributions
CALL. E> 0, E [0, 1), we have
L Ed
QC (E, & QC @UCamauurcC.mmm CALL (c, S
log
4.3 LOWER BOUND
In this section, prove that even if G is the class of reward functions that both Lipschitz and monotone w.r.t. 7 and C is the class of Lipschitz distributions, S2( ((=+) queries are needed to learn the optimal utility within error. This uniformly matching lower bound for all the upper bounds in this paper.
Theorem 4.3. For GLIP GMONO, CLIP, we have
1 [/4
log )
QCg.c.m (e, 2
High-level ideas To prove the theorem, we construct a Lipschitz value distribution and carefully perturb on a O(e) interval. The base value distribution leads to any 7 [1 1] being the optimal threshold. However, the perturbed distribution leads to a unique optimal threshold >" 1) To learn an e-approximately optimal threshold, the learner needs to distinguish the base distribution and O(2) perturbed distributions. It can proved that (2 log 1) queries are needed to distinguish the base distribution and perturbed distribution, which leads to desired lower bound. This idea significantly different from previous works that constructed discrete distributions (c.g.. Kleinberg & Leighton (2003); Leme et al. (2023b)).
Proof. Let g(>, v) = for any 7, E [0, 1] such that v 2 It is not difficult to verify that is Lipschitz continuous and monotone w.r.t. ?. this case, the expected utility can be written simple form U (t)) = 7(1 - F())).
Consider the following Lipschitz continuous distribution Fo:
20
v E [0,
Po(v)
v e [
4
This distribution leads to the following expected utility function:
7(1 - 27) 7(1 - (1 +)
7 [0, 33
Un(r)=
7 E 11
7(1 (1)))
7 E ( 1].
7

---

Published as a conference paper at ICLR 2024
8(z)
e
8())
3
Left: The base distribution F (black, dotted) and the perturbed distribution F Furyy (red solid), which moves one unit of mass from interval [w - 3e, w| to interval [w, w + 3e]. Right: The corresponding qualitative plots of + (T) (black, dotted) and y + (w)(() (red, solid).
Figure 1:
Because 7(1 ? is increasing interval [0, ()) and 7(1 7) is decreasing interval (2 1], Up(7) (0) when 7 E [0, }) and Uo(7) < ( = when 7 E (5 1]. In other words, the expected utility funetion reaches maximum value if and only if y [3 2) There is "plateau" on the utility curve. (See Figure 1.)
Next, we perturb the distribution Fo to obtain another distribution Fu.ex whose expected utility function will only have one maximum point rather than the interval [ 2). So estimate the optimal utility, the learner must distinguish Fo and class of perturbed distributions. However, by carefully designing the perturbation, the difference between Fo and perturbed distributions is small enough to lead to the desired lower bound.
Let E = {(w,e) E [0, 112, w - 3e 2 $, w + 35 < 1) For any (w,e) E, let hw.e(v) [uE(w,w+3e) 3e..w-3e.w) Notice that Fo has the following probability distribution function fo:
VE [0, 3
So(u)
E 1. (1.
So fu(u) 2 when V E 1/ 21. Define (w) fo(u) + (w), then we have (w,e(u) 2 0 for any v E [0, 1]. And f. fw.e(() (v) = 1, so fw.e is a valid probability density function. Let Fu.. be the corresponding cumulative distribution function. Note that Fu,e is L-Lipschitz for any constant L> 4. By definition, (v) So (t)et fo (fo(t) + (t)e Fo(v) + S hw (f)dt.
Claim 4.1. (See proof in Appendix C.4) The CDF function Fw,s is
Fu(u)) (v 32)
E [w 3z, w) [w, w + 3a] otherwisc.
Fw.e (v)
Fo(u) - (w 33 v)
Fu(u)
Claim 4.1 means that Fare and Fo are nearly the same except on the Gg-long interval [w (w-35, w 3E].
Let (1) be the expected utility function when the agent's value distribution Fu.e-
7(7 (w - -3)) [w 35, w)
Uwe((T) - Uo(y) ((F(77) Fw,e(t))
[w, 3s] 7(w + 35 7) otherwise.
Un. has unique maximum point at 7 w, with (w))(w) Ua(w) + 1 + 3we 1 + because 7(7 - (w 3e)) is increasing in (w - 3e, w/) and 7(w 35 -7) decreasing in [w, w +e)..
Let 1 + 3(2i 1)e, E 21,
36e }}. Note that (w;, E) E E for all i E [n]. It can
3
be proved that distinguishing distributions Fo and Fw..e requires Q 3 log 1) queries in the interval [ui 3z, w. + 3z] (see Appendix C.5). Queries not in [w; 3e, w; + 3s do not help to distinguish Fo and Fur,c because their CDFs are the same outside of the range |w; 3e, W; 3e].
8

---

Published as a conference paper at ICLR 2024
Lemma 4.3. For any i E [n]. 2 log 3)) queries in interval [w, 32, wi + 3E] are needed to distinguish Fo and Fw,.e.
Now consider setting where the underlying value distribution is Fw,.e for i uniformly drawn from Finding out the optimal utility and the corresponding threshold is equivalent to finding
{1, 2, 2.... n.. out the underlying value distribution. On one side, fixing 6, for each [n]] need 52( 2 queries to distinguish Fu..s and Fo and all these queries must lie in the interval I; = [ut, 3e, wA + 3e].
Since these intervals [Ti)etm) are disjoint, and the learner must make Q (z)z)) queries in each interval I, this leads to n- n (2(22 (2 = 9 ((33) ( queries in total. On the other side, for any d 1). S log ) are needed distinguish the underlying value distribution and other distributions with probability at least 1 - 5. Combining these two lower bounds, 9 = + zz log () queries are needed to learn the optimal threshold in e additive error with probability at least
Corollary 4.1. Qu (E, S2 t log f). QC (c. ( MA# + + log ())
ONLINE LEARNING
Previous sections studied the threshold learning problem in an offline query complexity model. In this section, we consider an (adversarial) online learning model and show that the threshold learning problem in this setting can be solved with a tight (T2/33 regret in the Lipschitz case.
Adversarial online threshold learning The learner and the agent interact for rounds. At each round E [7]. the learner selects threshold "i [0, 1] and the agent realizes value F, E C. The learner then observes reward b = by(T,, 24) = ( uy) 1,,27 as in Eq. (I), which depends on the unknown reward function 9r G and the value ty- Unlike the query complexity model where the learner only cares about the quality of the final output threshold 9, here, the learner cares about the total reward gained during the T rounds: E (e(7h, We compare this total reward against the best total reward the learner could have obtained using some fixed threshold in hindsight. In other words, we measure the performance of the learner's 's algorithm A by its regret:
RegT
C. (A) sup E 67,00) yE[0,1]
-
be be
Unlike the query complexity model where the value distribution F and reward function g are fixed, in this online learning model we allow them change over time. Moreover, they can be controlled by an adaptive adversary who, given classes C and G. at each round / can arbitrarily choose an Fe E and 9r E based on the history (71, 0i,-.. 1t-, 12-1).
We have shown in Section 3 that learning an c-optimal threshold is impossible for monotone reward functions GMONO and general distributions CALL. Similarly, it is impossible to obtain o(1) regret in this case. So, we focus the two cases with finite query complexity: S (GRamI-LLP CALL),, S2 = (GMONO, CLIP). The following theorem shows that, for those two cases, there exists a learning algorithm that achieves (TT2/3) regret, and this bound is tight.
Theorem 5.1. For the adversarial online threshold learning problem, there exists an algorithm A that, for both cases S (GRIGHT CALL.) and S (GMoNo, CLIP), achieves regret
Regs (A) S 1(12)31113)
And for any algorithm A, there exists fixed reward function 9 GLI GMONO and fixed distribution F CL.P for which the regret of A is at least Rega. (A) 2 S(T2/3).
The proof idea is as follows. The lower bound 2(T2/33 follows from the 2 query complex- ity lower bound in Theorem 4.3 by standard online-to-batee conversion. To prove the upper bound 2(12/3 we note that under the two environments S2, the expected reward func- tion U2(r) = Eu [b(y. v1)] is one-sided Lipschitz in 7. Therefore, we can treat the problem as continuous arm one-sided Lipschitz bandit problem, where each threshold y [0, 1] is an arm. This problem can be solved by discretizing the arm set and running no-regret bandit algorithm for finite set, e.g., Poly INF (Audibert & Bubeck, 2010). See details in Appendix D.

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGMENTS
We acknowledge the financial support from the National Natural Science Foundation of China (NSFC) (No.62172012). We thank all anonymous reviewers for their helpful feedback.
REFERENCES
Jacob D Abernethy, Kareem Amin, and Ruihao Zhu. Threshold Bandits, With and Without Censored Feedback. In Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016.
Rajeev Agrawal. The continuum-armed bandit problem. SIAM journal control and optimization, 33(6)1926-11511 1995.
Takeshi Amemiya. Regression analysis when the dependent variable is truncated normal. Econo- metrica: Journal of the Econometric Society, pp. 997-1016, 1973.
Jean- Jean-Yves Audibert and Sébastien Bubeck. Regret Bounds and Minimax Policies under Partial Monitoring. Journal of Machine Learning Research, (1(94):2785-288)) 2010.
Peter Auer, Nicolo Cesa-Biancle Yoav Freund, and Robert E Schapire. Gambling in a rigged casino: The adversarial multi-armed bandit problem. In Proceedings of IEEE 36th annual foundations of computer science, pp. 322-331. IEEE, 1995.
Richard Breen. Regression models: Censored, sample selected, or truncated data, volume 111. Sage, 1996.
Johannes Brustle, Yang Cai, and Constantinos Daskalakis. Multi-Iten Mechanisms without Item- Independence: Learnability via Robustness. In Proceedings of the 21st ACM Conference on Economics and Computation, pp. 715-761, Virtual Event Hungary, July 2020. ACM. ISBN 978- 1-4503-7975-5.
Nicolo Cesa- Besa-Bianchi, Claudio Gentile, and Yishay Mansour. Regret minimization for reserve prices in second-price auctions. IEEE Transactions on Information Theory, 61(1):549-564, 2014.
Nicolò Cesa-Bianche Tommaso R Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. A regret analysis of bilateral trade. In Proceedings of the 22nd ACM Conference on Economics and Computation, pp. 289-309, 2021.
Nicolò Cesa-Bianchi, Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. Bilateral trade: A regret minimization perspective. Mathematics of Operations Research, 2023a.
Nicolò Cesa- Risachianchi, Tommaso Cesari, Roberto Colomboni, Federico Fusco, and Stefano Leonardi. The role of transparency in repeated first-price auctions with unknown valuations. arXiv preprint arXiv:2307.09477, 2023b.
Richard Cole and Tim Roughgarden. The sample complexity of revenue maximization. In Proceed- ings of the forty-sixth annual ACM symposium on Theory of computing, pp. 243-252, 2014.
Constantinos Daskalakis, Themis Gouleakis, Chistos Tzamos, and Manolis Zampetakis. Efficient statistics, high dimensions, from truncated samples. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 639 639. IEEF, 2018
Constantinos Daskalakis, Themis Gouleakis, Christos Tzamos, and Manolis Zampetakis. Com- putationally and statistically efficient truncated regression. In Proceedings of the Thirty-Second Conference Learning Theory, pp. 955-960, 2019.
Paul Duetting, Guru Guruganesh, Jon Schneider, and Joshua Ruizhi Wang. Optimal no-regret leam- ing for one-sided lipschitz functions. In International Conference Machine Learning, 2023.
A. Dvoretzky, J. Kiefer, and J. Wolfowitz. Asymptotic Minimax Character of the Sample Distribu- tion Function and the Classical Multinomial Estimator. The Annals of Mathematical Statistics, 07(3):642-669 September 1956.
10

---

Published as a conference paper at ICLR 2024
Khaled Eldowa, Emmanuel Esposito, Tommaso Cesari, and Nicolò Cesa- On the minimax regret for online learning with feedback graphs. arXiv preprint arXiv:2305.15383, 2023.
Zhe Feng, Sébastien Lahaie, Jon Schneider, and Jinchao Ye. Reserve price optimization for first price auctions in display advertising. In International Conference on Machine Learning, pp. 3230-3239. PMLR, 2021.
Yannai A Gonczarowski and Noam Nisan. Efficient empirical revenue maximization in single- parameter auction environments. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 856 868, 2017.
Gauthier Guinet, Saurabh Amin, and Patrick Jaillet. Effective Dimension in Bandit Problems under Censorship. Advances in Neural Information Processing Systems, volume 35, pp. 5243-5255. Curran Associates, Inc., 2022.
Chenghao Guo, Zhiyi Huang, and Xinzhi Zhang. Settling the sample complexity of longle-paramette revenue maximization. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 20119.
Nika Haghtalab, Tim Roughgarden, and Abhishek Shetty. Smoothed analysis with adaptive adver- saries. In 2021 / IEFE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pp- 942-953. IEEE, 2022.
Robert Kleinberg and Tom Leighton. The value of knowing a demand curve: Bounds on regret for online posted-pric pricce-prcceeeeooe auctions. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. pp. 594-5995555 IEEE, 2003.
Robert Kleinberg, Aleksandrs Slivkins, and Eli Upfal. Bandits and experts metric spaces, Journal of the ACM (JACM), 66(4):1-77, 2019.
Vasilis Kontonis, Christos Tzamos, and Manolis Zampetakis. Efficient truncated statistics with unknown truncation. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pp.
IEEE, 2019.
Vijay Krishna. In Auction Theory (Second Edition), pp- iii. Academic Press, San Diego, second edition edition, 2010. ISBN 12-34-12--7
Jasper Lee. Lecture 11: Distinguishing (discrete) distributions. 2020.
Renato Paes Leme, Balasubramanian Sivan, Yifeng Teng, and Pratik Worah. Description complexity of regular distributions. arXiv preprint arXiv:2305.055500 2023a.
Renato Paes Leme, Balasubramanian Sivan, Yifeng Teng, and Pratik Worah. Pricing query com- plexity of revenue maximization. In Proceedings the 2023 Annual ACM-SIAM Symposium Discrete Algorithms (SODA), pp. 399-415. SIAM, 2023b.
Roderick J. A. Little and Donald B. Rubin. Statistical Analysis with Missing Data. Wiley series in probability and statistics. Wiley, Hoboken, NJ, third edition edition, 2020.
Stefan Magureanu, Richard Combes, and Alexandre Proutiere. Lipschitz bandits: Regret lower bound and optimal algorithms. In Conference on Learning Theory, pp. 975-999. PMLR, 2014.
P. Massart. The Tight Constant in the Dvoretzky-Kiefe--Wolle ability, 18(3). July 1990. ISSN 0091-1798.
Inequality. The Annals of Prob-
Jamie H Morgenstern and Tim Roughgarden. On the pseudo-dimension of nearly optimal auctions. Advances in Neural Information Processing Systems, 28, 2015.
James Tobin. Estimation of relationships for limited dependent variables. Econometrica: journal of the Econometric Society, pp. 24-36, 1958.
Arun Verma, Manjesh Hanawal, Arun Rajkumar, and Raman Sankaran. Censored Semi-Bandii A Framework for Resource Allocation with Censored Feedback. In Advances in Neural Information Processing Systems, volume 32, Curran Associates, Inc., 2019.
11

---

Published as a conference paper at ICLR 2024
A ADDITIONAL RELATED WORKS
For the online setting, our work is most related to the Lipschitz bandit problem, which was first studied by Agrawal (1995). Once we have Lipschitzness, there is a standard discretization method get the desired upper bound and is widely used in online settings. See Magureanu et al. (2014); Kleinberg et al. (2019); Haghtalab et al. (2022). The upper bound of our online results follows this standard method, but the lower bound relies continuous-armi armed Lipschitz bandit problems. Several recent works study multi aamti bandit prob- lems with censored feedback. For example, Abernethy et al. (2016) study bandit problem where the learner obtains reward of if the realized sample associated with the pulled arm is larger than an exogenously given threshold. Verma al. (2019) study resource allocation problem where the learner obtains reward only if the resources allocated to an arm exceed certain threshold. In Guinet al. (2022), the reward of each arm is missing with some probability at every pull. These models significantly different from ours, hence the results are not comparable.
offline results and is different from previous
Censored/Truncated data are also widely studied in statistical analysis. For example, a classical problem is truncated linear regression, which has remained a challenge since the early works of Tobin (1958); Amemiya (1973); Breen (1996). Recently, Daskalakis et al. (2019) provided a com- putationally and statistically efficient solution this problem. Statistics problems with known unknown truncated sets have received much attention recently (e.g. (Daskalakis et al., 2018; Kon- tonis et al., 2019)). For more knowledge of this field, the reader turn to the textbook of Little & Rubin (2020). While this line of work studies passive learning settings where the censored dataset is given the data analyst exogenously. we consider an active learning setting where the learner can choose how to censor each data point, and how to do that optimally.
B BASIC MATH
B. DKW INEQUALITY
The following well-known concentration inequality will be used in our proofs.
Lemma B.1 (Dvoretzky-Kinne Kienee--KKieee--M Kifeeer-oooeewooiiittt (DKW) inequality (Dvoretzky et al., 1956; Massart, 1990)). Let X1, X2, .,, be n real-valued i.id random variahles with cumulative distribution function F. Let F, = >t 1x,5x be the associated empirical distribution function. Then for all 8 8>0, O,
IP sup (Fx(z) - F(x)) >5{ < 2e 2nc
LEER
B.2 PROPERTIES OF HELLINGER DISTANCE
Then we review some useful properties the Hellinger distance and total variation distance. First, the Hellinger distance gives upper bounds on the total variation distance:
Fact B.1. Let D1, D2 be two distribution on X. Their total variance distance and Hellinger distance are drv (Dr, D2) and du (D,, D2) respectively. We have
- (Dr, D2) 2 (1 (L.)((D.)))))
The total variation distance has the following well-known property that upper bounds the difference between the expected values of a function on two distributions:
Fact B.2. For any function h X + [0, 1), (Ez~D [h())] - EE- [h(x]] & dDv,
Second, we use the following lemma to upper bound the squared Hellinger distance between two
distributions that are close to each other. We use D specifically denote discrete distributions. We slightly abuse the notation by using D to denote PDF of distribution D.
Lemma B.2. Let D,, D2 be two distribution on satisfying S Then (D1, D2) 2
(2(x) Di S + for all x E X.
12

---

Published as a conference paper at ICLR 2024
Proof. By definition,
1 D2) =
Σ - -2)(0)))))))))
= Σ
1
Di(z) 1- D2(x)
2
Di(x)
ZEX
FEA
If D2(x) < Di(x), then we have
Da(x)
S (1- 8) 5 (1 - (1 - e)) = 82.
Di(0)
D2(x) 2 (x)), we have
Da(a) Di(z)
2 (v1 -8 8- -1) < ((1+--1)) = ². Combining these
two cases, have
(2) ΣΣ Di(ree 1 ?
#EA
Finally, let D m denote the empirical distribution of T i.i.d samples from D, namely, the product of independent D distributions. We have the following lemma relates ( m D m with (D,, D2).
Lemma B.3. (Lee (2020)) & "
D2) S m. (D, D2).
B.3 DISTINGUISHING DISTRIBUTIONS
Let D1. D2 be two distributions over discrete space X. A distribution D; is chosen uniformly from the set (D1, D2). Then we are given m samples from D; and want to distinguish whether the distribution is Di D2. It is known that at least = O Ii log ()) samples are needed to 5, no matter how we guess. Formally we have
guess correctly with probability at least
Lemma B.4. Let j E {1,2] be the index of the distribution we guess based on the samples. The probability of making a mistake when distinguishing D1 and D2 using samples, namely Prlj + 2 Prij 1L: 2). least
? 2 Prij 2 1] + 1
Pr[j #
4 (1- (D, (D,, D2)) 2m 22)) 2
1 (mm
if < 1.- The inequality implies that, in order to achieve Prlj # i] S 8. must have m D2) log 45'
Proof. The draw of m samples from Dj D2 is equivalent to the draw of one sample from D or g000 guessing the distribution is at least
m Given one sample from D or D the probability of making one mistake when
2 m
Pr(j = 2 = 1|+ 1
Pr[j +
Pr(j 1li = 2]
2
2
1 Pr[p 1/i 1] 1 Pr(j 1li 2]
(Prjj= = 1| Pr(j = 1|li 1))
(5)
=
2 2
E 0 [1=1] - E D [1 11
byF act B.2 >
dTv 1880 m ,D
Then we upper bound drv (D Lemma B.3, we have
Dmm to prove the lemma.
According to Fact B. and
1 dGv
D 2
2 2(1
(1
(D D DS )²) = (1- (1-d((D, D2)) 2m
13

---

Published as a conference paper at ICLR 2024
Since
1 1- d-d (D@=
m -0 (1 drv (D@ D2 0)0r))(( drv (D@m -)
s 22(1 Utv 1100 D m)
we have
1 1- dTv dTv
(DSmm. D2 m 2 2 (D), D2))
Plugging into Eq. (5), we have
P 2 (1 (Di, D2)) 2m
When dfi D2) < 1.2 the inequality 1 - 2x for all (0, ( concludes that
Príj # i) 2 Amd Do),
C MISSING PROOFS FROM SECTION 4
C.1 PROOF OF LEMMA 4.1
Proof. The distribution is weakly differentiable because is Lipschitz. Let f be the weak deriva- tive of F. We have f(v) I L for all v E [0, 1] because of Lipschitzness. We rewrite the expected utility U(+) = E [g97 v) 1.27] as J._, g(7 v) ( Then for any S m S 72 S 1,
U(12) - U(n) = / 0(12,0)f(U)d f g(n, ()f(d)o
1=
f
(g(72,0) g(n, v)) f(u)do |m g(71, f(v)do
gmm ((d)d Z (F(7)) - F(1))
where the first inequality holds because is monotone in 7, the second inequality holds because g(7.0) < 1.
C.2 PROOF OF LEMMA 4.2
Proof. For any 0 S 71 12 1
U(12) - U(m) = E [g(72, v) 122% - En-r 1.27]
= B ( v) - g(%,,))) 1 10272l - Ev- (lg_,,))1))) 1 Sueyal
B (9( 1) - v(n,,)) . 102%) S I(12 -1)
where the first inequality holds because y(7,v) 2 O, the second inequality holds because the pro- jection 9u is night-Lipschite continuous and the expectation E.- 1.212 <
C.3 PROOF OF THEOREM 4.2
(e, for all 0, 6 1). For any & > 0, let's consider all the multiples of f. in [0, 1], r 2 1 k E N < L. We make O log [T] queries for each threshold 7 Z in r. By a union bound, we have with
Proof. Because CLIP CALL. have QCn....cun. (s,
probability at least 1 [T] A
IIT 6, the estimate Ü (>) satisfies (ύ(x) - U(>) < s for every
threshold in P. Since [T| O this uses [T] 0 log (1) O log 4) queries in total.
14

---

Published as a conference paper at ICLR 2024
Let 7 arg maa.max. (7) be optimal threshold. And let " mrg be the optimal
threshold on the discretized set. And let iL In respectively be the multiples of closest to the left. Then we have " E and 0 < 7- 7 < E. Since the reward function g is right-L- Lipschiz-ccontnnous,
U(9") (8*) 2 ((n)
2 U(r)) - 2E
2 U(()))
L(? -1)
2 U(>)) - 33
where the first and third inequality holds because Eq. (3), the second inequality holds because the selection of 9*, the fourth inequality holds because of Lemma 4.2.
C.4 PROOF OF CLAIM 4.1
Proof. For V < 3a and > w 3e, Jizo ( because (t)) when < 35 ort > 35 and putte (t,= 30 32 0. Therefore, for 3e and 3c, (w,e(U) = Fo(v). For any UE (w 3E, w),
Pu (v) - Fo(v) f
-sw-3c (w)dl -(v - w 3e).
And for any E [w, w + 3z).
(w) Fo(v)= = ff" ww-3e
(m)elt)dl = puttee
(1)de - putte nm (1)dl -(w + 3e - v).
C.5 PROOF OF LEMMA 4.3
Proof. When the learner sets different thresholds y and the value distribution is Fo, the samples come from different distributions G... Similarly, when the learner sets different thresholds and the value distribution is Fw,e, assume that the samples come from diffcrent distributions G
In order to distinguish Fo and Fw,s, the learner must at least find threshold y that it is able to distinguish G., and G
Given g(7, v) = 1 1uzy G.y a Bernoulli distribution that for all X ~ Gay, Pr[X 0] Fo(T) and Pr[X- 7] = Fo(r). And G is also Bernoulli distribution that for all Y G
Pr[Y 0] Fu. (7) and Pr(Y 7 = 1 (7).
Recall that
Fu(u) - (v w 32)
E [w 3z, w) [w, w + 3s]
Fv,e (v)
Fo(v) (w 35 v)
Fo(u)
otherwise
When 7 < w 35 or w + 3E, G.,, and Gu are the same Bernoulli distribution. The learner
can't distinguish them. When E [w 3e, w + 3e), we have Fo(7) 2 Fm.s(7) 2 Fo(r) - 3 and Fo( 2 (7) 2 Fo( Recall ( = and Fa( = 2 ,Then we get
1 12 Pr(Y 0]
Fwo(?))
Fo(r) 38 =1
38 Fo(r)
38 F)(
>
12s.
Pr[X = 0] Fo(2)
Folr)
and
Pr|Y 7
1 1 Fw,e())
1- Foly) + 35
3z
35
1
$
1+ 1-65.
Pr[X []]
1- Fo(7)
Folr)
1 Fo(r)
1
Fo(
15

---

Published as a conference paper at ICLR 2024
According Lemma B.2, we have di GG, - 1 (12:) I 72s2. Then know from Lemma B.4 that 2 log }) samples are needed distinguish G2 and G with probability at least --
In other words, the learner must at least find a threshold Y E [w 3E, w + 3E| and do least ! log ()) queries at the same threshold y to distinguish Fb and Fure with probability at least 1 8.
D PROOF OF THEOREM 5.1
Proof. First, because et F, is independent of Tts we have Eu,- (be Ux)l Ue(7e), and can rewrite the regret as
E < [< ).
E [E
sup
Σ b.(.) v2)
sup 1E(0.1]
E
Σ U(())
where the expectation on the right-hand-side is only over the randomness of algorithm A but not Ct-
We treat the online learning problem continuous-amm adversarial bandit problem, where each threshold 7 E [0, 1] is an arm. According to Lemma 4.1 and Lemma 4.2, in all the three environ- ments Si, S2,82, S3 in the theorem the expected utility function U2(>) = Eng=F, F, [7, 2t]] is one-sided Lipschitz in y. W.l.o.g, assume that U, is right-Lipschitz. Let's discretize the arm space [0, 1] uni- formly with interval length f. obtaining a finite set of arms r = {0, É. .... with [ S f + Let n" arg 1 E Σi=1 Ue(7)] be an optimal threshold in the interval [0, (for the expected sum of utility funetions). And let 4" E arg max E Σ U+(1)] be optimal threshold in the discretized set r. And let fi E be the largest multiple of æ that does not exceed y Clearly,
7" in f. Because every U, right-Lipschitz, we have
E Σ
UL("")
E MEuGh < Eu4 -A) $ Te.
This implies that the optimal threshold 4th satisfies
E
Σ (.(A9)
R
2 E Σ U.()*) Te.
Recall that the Poly INF algorithm (Theorem of (Audibert Bubeck, 2010)) is an adversarial multi-armed bandit algorithm with OVVTK) regret when running on an arm set of size K. we run that algorithm on the arm set 1, and let E 14)1/3, then we get a total expected utility of at least
E
Ud(TH)
2 E
Σ
U.(7") - O(VTTT))
1=1
E
Σ U((7")
-Ts 0 TT(
E
Σ U((r*)
(113)
So, the regret most 117333
E EXPERIMENTAL RESULTS
In this section, we provide simple experiments to verify theoretical results.
16

---

Published as a conference paper at ICLR 2024
E.1 UPPER BOUND
otherwise 9(7, v) = and the value distribution the uniform distribution on [0, which corresponds the monotone reward function and Lipschitz value distribution. The second example is g(,, = and the value distribution is a point distribution that all the mass on 3. which corresponds the Lipschitz reward function and general distribution case (Theorem 4.2). In our experiment, we first fix the number of queries
We consider two toy examples. The first example ((, - if if <
K" where K 100 + 3i for integer < S 33, i.e. we choose K from [100, 200]. Therefore, the algorithm for the upper bound should output errors smaller than the predetermined loss K The following figure shows the relationship between the loss and the number of queries. The empirical loss curve under the predetermined loss curve, which verifies our upper bound results.
Lipshitz reward function discrete distribution
Monotone reward function Lipschitz distribution
-1.6
empincal loss
predetermined
-5.5
the utilty lass
-5.0
the utiit
-6.0
-65
-54
empirical
predetermined
14.5
the number of quenes
the number queries
Figure 2: Loss curves under different examples. The orange line: the predetermined loss curve. The blue line: the empirical loss curve. All variables are in logarithmic form.
E.2 LOWER BOUND
In this section, we provide experimental results to verify our lower bound result (Theorem 4.3). We consider the example we provided in the proof Theorem 4.3 where g v) = 7 and the value distribution is "hard distribution" (see the left part of Fig. 3). For E 400 500 600 J. algorithm in Thcorem 4.1 to determine the minimum number n of queries that are necessary to learn the optimal threshold with additive error. Due to randomness, each round, we compute In and find it converging to 3, which verifies our lower bound result.
the
repeat 10 times for each At
frequency realized samples
Int 32
2.0
3.15
3.1
15
g
1.0
0.5
2.95
0.0
02
0.6
2.9
1/400
1/500
1/600
Figure 3: Left: The blue curve is the probability distribution function. The orange part is the frequency realized samples. Right: The box plot when E E 200 500 600 }. The horizontal axe represents s. The vertical axe represents the logarithmic ratio In
T
17


Reviews:
[{"review_id": "GizRlcfksc", "reviewer": "Reviewer_sD7K", "summary": "The paper studies the question of learning threshold in latent space. In this problem, we have an unknown reward function $g(\\gamma, v)$ and unknown distribution on $v$ and need to pick $\\gamma$ that maximizes $E_{v}[g(\\gamma, v) \\cdot [v \\ge \\gamma] ]$. \n\nThe paper presents the sequence of impossibility and positive results. The first contribution is the proof that query complexity is infinitely large for general monotone functions. The second contribution is the series of positive results when CDF of distribution $v$ is Lipshitz and when g is one-sided Lipshitz with respect to $\\gamma$. In both cases, algorithms achieve $O(\\epsilon^{-3})$ sample complexity for learning $\\epsilon$ approximation.  Additionally, the authors complement this result with matching lower bounds.", "questions": "See weaknesses.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper introduces an important problem that looks very natural and has applications. This is an interesting and practically relevant setting that captures real-world scenarios like setting reserve prices in auctions, difficulty levels in crowdsourcing, and hiring bars in recruiting. \n\nThe paper provides a solid theoretical analysis. The authors achieve tight results. The results are technically sound.\n\n\nThe problem formulation and results are clearly explained. The paper is well-written and easy to follow.\n\nOverall, the paper studies an interesting problem and provides nice theoretical results that advance our understanding of learning in latent spaces.", "weaknesses": "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?\n\n The high-level ideas and intuition could be emphasized more.\n\n Some simple experiments on synthetic data would help support the theoretical results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Bl4AwCtDqj", "reviewer": "Reviewer_F7cS", "summary": "This paper studies an abstraction of a threshold learning problem that arises in a number of applications such as reserve price learning in single-item auctions, crowd-sourced task allocation/data collection, and theoretical models of hiring. Here, the reward function is specified by a value and a threshold. The threshold is chosen by the learner, the value is then drawn from an unknown distribution, and the learner observes the reward if the value exceeds the threshold. \n\nFirst, the authors construct the existence of a monotone reward function and a “hard” distribution over values involving point masses that requires an unbounded query complexity to learn the optimal threshold. The authors then give tight query complexity bounds under Lipschitzness assumptions on the reward and value distributions. Finally, an extension to the online setting is studied.", "questions": "Are there specific examples of reward functions g that the authors can give that fit the different conditions of their main theorems? Specifically, reward functions that go beyond the simple case of reserve price learning. 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.\n\nI think the authors should include all parameters such as the Lipschitz constant L in their query complexity bounds. \n\nThe query policy in the proof of Theorem 4.1 requires that the learner knows the Lipschitz constant L of the CDF of the unknown value distribution. So the value distribution is not really fully unknown here. Is there any way to remove the assumption that the learner knows L, or could that lead to exponential/infinite query complexities?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The question posed has a clear motivation and is a nice abstraction of questions like reserve price learning. The paper itself is a nice complete contribution, characterizing hardness and giving tight query complexity bounds in tractable cases. The writing is clear and precise. The lower bound constructions are interesting.", "weaknesses": "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. The same proof gives the main upper bound results for the other settings as well.\n\nOverall, my main concern is with the originality and novelty of the question being studied. While it is a neat way to abstract away from more specific applications like reserve price learning, and I think the results presented are certainly nice ones, the overall motivation through the examples of reserve pricing, crowdsourcing, and hiring are not enough to convince me that this is a sufficiently novel work for publication in ICLR. Perhaps a more fine-grained structural analysis in terms of practically-motivated properties of the reward function is possible here, which would make the story more compelling.\n\nThe assumption that the learner knows the Lipschitz constant of the unknown distribution in the querying algorithm in the proof of Theorem 4.1 seems too strong given the premise of the value distribution being unknown. Perhaps the results could be augmented to remove this assumption, and L is a parameter that must be learned as a part of the querying?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pqrN6yWDKD", "reviewer": "Reviewer_Z8bt", "summary": "This paper considers a new setting of actively learning threshold in latent space with censored feedback, where the rewards can be observed only when the threshold is lower than or equal to the unknown latent value. The reward function g is defined over both the proposed threshold and latent value.  They proved that the query complexity can be infinitely large even when the reward function is monotone with respect to the threshold and the value. When adding assumptions of Lipschitz CDF, they proved tight query complexity up to logarithmic factors. They also extended to the online learning setting, related it to continuous-armed Lipschitz bandit, with theoretical results.", "questions": "- 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. \n- For the online setting, the proposed setup links to continuous-arm one-sided Lipschitz bandit problem. can you add the related work about this? Also, as mentioned in the weakness, adding a comparison to the existing results in bandits literature is needed.", "limitations": "", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Clear motivation examples for the proposed setting\n- Provided high-level ideas and intuition for proofs, which helps readers understand the theorems\n- Provided the query complexity lower and upper bound for both Lipschitz and general reward distributions. Table 1 summarizes the results and is very clear.\n- Link to continuous-armed Lipschitz bandit in an online learning setting is interesting, with theoretical results.", "weaknesses": "- 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.\n- No experimental results. It would be good to show empirical results which verify the theoretical results (see below question 1). Additionally, it would be even better if the toy example could correspond to the motivation example provided in the paper. \n\nHappy to raise the score if my main concerns are addressed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "imTyA8JVvG", "reviewer": "Reviewer_MPBo", "summary": "This paper studies the sample complexity of active threshold learning when samples are censored. The authors then apply their offline results to provide a tight regret guarantee for the online version of the problem. \n\nThe model is as follows: there is a latent variable $v$ in $[0,1]$ sampled according to an unknown distribution and a reward function $g$ that maps (threshold, latent variable) pairs in $[0,1]$. The learner repeatedly and adaptively queries the value of $g$ on specific thresholds (for i.i.d. realizations of the latent variable) and obtains censored feedback, i.e., if the threshold is larger than the latent variable, it does not observe anything. The goal of the learner is to get an $(\\varepsilon,\\delta)$ approximation of the best threshold, using as few (adaptive) samples as possible. \n\nThe results are as follows: \nin the general case, the sample complexity is infinite (Theorem 3.1.)\nwhen function $g$ is Lipshitz or the latent variable distribution has Lipshitz CDF, then $\\tilde O(\\tfrac{1}{\\varepsilon^3})$ samples are enough (Theorems 4.1 and 4.2)\nthese bounds are tight up to poly-logarithmic terms (Theorem 4.3)\nthese results immediately imply a $\\Theta(T^{2/3})$ minimax regret regime for the online learning version of the problem", "questions": "- 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?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Censored data are interesting as they naturally arise from applications and have been studied both in the sample complexity and online learning literature. The paper is well written and the proofs in the main body are easy to understand. The fact that the authors provide a complete picture of the problem is compelling.", "weaknesses": "My main concern with the paper, which motivates my low score, is given by the technical contribution of the paper, as all the theoretical results are not too surprising and build on known techniques.\n- the needle in a haystack phenomenon is known and has been used before in pricing context, see e.g., [1] “A Regret Analysis of Bilateral Trade\" EC, 2021\n- Theorems 4.1 and 4.2 are not surprising: if some regularity or smoothness assumptions are made then the objective becomes Lipshitz in the threshold, and an epsilon grid on the threshold space immediately yields the desired result see. e.g., [2] “Bandits and Experts in Metric Spaces” J ACM, 2019.\n- Theorem 4.3 is the more involved result but is not too surprising: the construction entails a family of distributions with $\\Theta(\\tfrac 1{\\varepsilon})$ candidate optimal thresholds where each candidate needs to be evaluated $\\Omega(\\tfrac 1{\\varepsilon^2})$ times. This has already been done, e.g., in the $\\Omega(T^{2/3})$ lower bounds in [3] “The Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price Auctions” FOCS 2003.\n\nThe problem studied, and the techniques used, are closely related to Lipshitz bandits [2], pricing [3] and bilateral trade [1]. Please consider a more thorough comparison with the already known results and techniques there.\n\n%%%%\nI thank the authors for the insightful comments and the submission revision. Overall, I am convinced that the technical contribution --although deeply inspired by past works- is novel enough to raise my score slightly.\nI particularly appreciated that the authors added some comments and pointers to the literature before the proofs to highlight this.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)