Research map / Bandits and online learning / Online convex optimization and games
Online Learning with Sublinear Best-Action Queries
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 online learning with at most k best-action queries (oracle reveals the best action at a time step), deriving tight minimax regret rates under full and label-efficient feedback, plus stochastic i.i.d. results.
Problem
Online learning (prediction with experts) where the learner can issue a limited number k of best-action queries that reveal the identity of the best action at a time step; the goal is to characterize minimax regret as a function of k and feedback model.
Approach
Combines Hedge (or label-efficient Hedge) with uniformly random best-action queries; shows k queries yield a multiplicative improvement in regret (T/k instead of sqrt(T)), and gives matching lower bounds via stochastic two-expert instances.
Key results
- Full feedback: Hedge with k uniformly random best-action queries achieves regret O(min{sqrt(T log n), T log n / k}), matched by a lower bound Omega(min{sqrt T, T/k}).
- Label efficient feedback: modified label-efficient Hedge achieves O(min{T/sqrt(k), T^2/k^2}) regret, shown tight by lower bounds.
- Stochastic i.i.d. setting: Follow-The-Leader with queries achieves Theta(T/k) for k >= sqrt(T); Explore-Then-Commit achieves tilde-Theta(T^2/k^2) for k >= T^{2/3} in the label-efficient case.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add k best-action queries under full feedback | Online learning with Hedge · Full feedback, adversarial | regret: Θ(√T) without queries; Θ(min{√T, T/k}) with queries | Helped |
| Add k best-action queries when feedback is available only at query times | Label-efficient prediction · Label efficient feedback, adversarial | regret: Θ(T/√k) standard rate; Θ(min{T/√k, T^2/k^2}) with queries | Helped |
| Use k best-action queries and Follow-The-Leader | Online learning · Full feedback, stochastic i.i.d. | regret: \tilde \Theta(\sqrt{T}) otherwise; \Theta(\nicefrac{T}{k}) when k \geq \Omega(\sqrt{T}) | Helped |
| Use k best-action queries and Explore-Then-Commit | Online learning · Label efficient feedback, stochastic i.i.d. | regret: \tilde \Theta(\nicefrac{T}{\sqrt{k}}) otherwise; \tilde \Theta(\nicefrac{T^2}{k^2}) when k \geq \Omega(T^{\nicefrac{2}{3 | Helped |
Surprising findings
- A sublinear number of queries (e.g., k = T^{2/3}) reduces regret multiplicatively, from sqrt(T) to T^{1/3}, even though the total loss impact of queries is only additive O(k).
Limitations
- Assumes perfect oracle: queries always return the true best action.
- Analysis restricted to full and label-efficient feedback; bandit feedback, partial monitoring and feedback graphs are left open.
- Stochastic results use different algorithms and carry a suboptimal dependence on n.
Experimental setup
Metrics: regret
Baselines: Hedge without queries label efficient prediction with k feedback steps
Builds on: Hedge label efficient prediction Explore-Then-Commit Follow-The-Leader
Closest papers by meaning
- Multi-Armed Bandits With Best-Action Queries (NeurIPS 2026 · similarity 0.89)
- Online Decision Making with Generative Action Sets (ICLR 2026 · similarity 0.89)
- Bayesian Optimization from Human Feedback: Near-Optimal Regret Bounds (ICML 2025 · similarity 0.88)
- A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of $\Theta(T^{2/3})$ and its Application to Best-of-Both-Worlds (NeurIPS 2024 · similarity 0.87)
- Online Learning with Unknown Constraints (ICML 2025 · similarity 0.87)
- From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model (NeurIPS 2026 · similarity 0.87)
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.