Research map / Bandits and online learning / Online convex optimization and games
Learning Thresholds with Latent Values and Censored Feedback
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies active learning of a threshold in latent value space where reward is observed only when threshold is below the unknown value, giving tight query complexity bounds and a tight T^{2/3} online regret.
Problem
Setting a threshold (reserve price, hiring bar, task requirement) in a latent space where reward is observable only if the threshold is at most the unknown latent value; the goal is query complexity of finding an epsilon-optimal threshold and online regret.
Approach
Shows query complexity can be infinite for monotone rewards with general distributions (needle-in-haystack construction), and gives tight Theta~(1/eps^3) bounds under monotone+Lipschitz CDF or right-Lipschitz rewards, plus a matching lower bound via perturbed Lipschitz distributions; extends to online setting via continuous-armed one-sided Lipschitz bandits.
Key results
- Query complexity is infinite for monotone rewards with general value distributions, even at epsilon = 1/8.
- Tight query complexity Theta~(1/eps^3) for monotone rewards with Lipschitz value CDF, and for right-Lipschitz rewards with general distributions; lower bound Omega(1/eps^3 + eps^-2 log(1/delta)).
- Online adversarial threshold learning achieves O(T^{2/3}) regret, matched by an Omega(T^{2/3}) lower bound.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Restrict the value distribution to have a Lipschitz CDF | Monotone-reward threshold learning · Threshold learning with monotone reward | query complexity: Infinite -> O\InParentheses{\frac{L}{{\varepsilon}^3}\log\frac{L}{{\varepsilon}\delta}} | Helped |
| Assume the reward function is right-Lipschitz | Threshold learning with general value distributions · Threshold learning | query complexity: \tilde{O}(\frac{1}{\varepsilon^3}) | Helped |
| Use monotone and Lipschitz reward functions with a Lipschitz value distribution | Threshold learning · Threshold learning | query complexity: \Omega\InParentheses{\frac{1}{{\varepsilon}^3}+\frac{1}{{\varepsilon}^2}\log\frac{1}{\delta}} | Mixed |
| Use one-sided Lipschitz expected rewards and discretize the threshold arms | Adversarial online threshold learning · Online threshold learning | regret: O(T^{2/3}) | Helped |
Surprising findings
- Query complexity can be infinite even when the reward is monotone in both threshold and value.
- Learning the optimal threshold is impossible to approximate to o(1) regret under monotone rewards with general distributions.
Limitations
- Experiments are only toy simulations verifying upper and lower bound scaling.
- Positive results require monotonicity or right-Lipschitzness assumptions on the reward.
Experimental setup
Metrics: query complexity regret
Builds on: Poly INF DKW inequality
Closest papers by meaning
- Thresholding Bandit with Optimal Aggregate Regret (NeurIPS 2019 · similarity 0.87)
- On the Minimax Regret for Online Learning with Feedback Graphs (NeurIPS 2023 · similarity 0.86)
- Leveraging Offline Data in Linear Latent Contextual Bandits (ICML 2025 · similarity 0.86)
- Pareto-Optimality, Smoothness, and Stochasticity in Learning-Augmented One-Max-Search (ICML 2025 · similarity 0.86)
- Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality (NeurIPS 2025 · similarity 0.85)
- Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.