Research map / Bandits and online learning / Multi-armed bandits
Constrained Feedback Learning for Non-Stationary Multi-Armed Bandits
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.
Introduces constrained-feedback non-stationary bandits (ConFee-nsMAB) with a query budget and proposes HyQue, a prior-free hybrid query allocation algorithm achieving near-optimal dynamic regret Õ(K^{1/3}V_T^{1/3}T/B^{1/3}) with a matching lower bound.
Problem
Non-stationary multi-armed bandits typically assume reward feedback every round, which is unrealistic when feedback is costly or limited; the paper asks how a total query budget affects dynamic regret and whether prior-free near-optimal algorithms exist.
Approach
Extends multi-scale restart (MASTER-style) bandit algorithms with a block-level baseline query allocation (BaQue) that guarantees a minimal query rate per instance, plus an on-demand query injection (HyQue) that keeps cumulative query usage near a linear pacing schedule, and proves a matching lower bound.
Key results
- HyQue attains dynamic regret Õ(K^{1/3} V_T^{1/3} T / B^{1/3}) without prior knowledge of V_T, for B = ω(T^{3/4}).
- A matching lower bound Ω(K^{1/3} V_T^{1/3} T / B^{1/3}) is established up to logarithmic factors.
- When B = Ω(T), the bound recovers the known Õ(K^{1/3} V_T^{1/3} T^{2/3}) nsMAB rate.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use HyQue with constrained feedback and a query budget B | ConFee-nsMAB · ConFee-nsMAB | dynamic regret: \tilde{\mathcal{O}}\left( \frac{K^{1/3} V_T^{1/3} T}{B^{1/3}} \right) | Helped |
| add on-demand query allocation to BaQue (ablation) | HyQue · stable or mildly changing environments in ConFee-nsMAB | dynamic regret | Helped |
| use the baseline allocation alone, without on-demand query allocation (ablation) | HyQue · stable or mildly changing environments in ConFee-nsMAB | dynamic regret | Hurt |
| allow queries at every round (B = T) | HyQue · non-stationary multi-armed bandits | dynamic regret: \Tilde{O} \left( K^{1/3} V_T^{1/3} T^{2/3} \right) | Helped |
Limitations
- Relies on a predefined, fixed query budget that may not reflect dynamic feedback availability.
- Theoretical only; no empirical experiments reported in the text.
- Extension to non-stationary RL with constrained feedback left open.
Experimental setup
Metrics: dynamic regret
Baselines: UCB1 with variation budget (known V_T) MASTER stationary feedback-constrained bandits
Builds on: UCB1 MASTER non-stationary bandits with variation budget
Closest papers by meaning
- Tracking Most Significant Shifts in Infinite-Armed Bandits (ICML 2025 · similarity 0.90)
- Bandits with Ranking Feedback (NeurIPS 2024 · similarity 0.90)
- Adaptive Regret for Bandits Made Possible: Two Queries Suffice (ICLR 2024 · similarity 0.89)
- Non-Stationary Lipschitz Bandits (NeurIPS 2025 · similarity 0.89)
- Non-stationary Bandit Convex Optimization: A Comprehensive Study (NeurIPS 2025 · similarity 0.89)
- No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.89)
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.