Multi-Armed Bandits With Best-Action Queries

arXiv:2605.08287v1 Announce Type: cross Abstract: We study multi-armed bandits (MABs) augmented with best-action queries, in which the learner may additionally query an oracle that reveals the best arm in the current round. This setting was recently characterized by Russo et al. [2024] in the full-feedback model, where the learner observes the rewards of all arms after each round. They show that, in both stochastic and adversarial environments, k best-action queries reduce the optimal widetilde{O}(sqrt{T}) regret to widetilde{O}(min{T/k,sqrt{T}}). Whether this improvement extends to the more realistic bandit-feedback model -- where the learner observes only the reward of the played arm -- was left as an open problem. We fully resolve this question. When rewards are stochastic but correlated among arms, we show that the full-feedback result does not carry over: any algorithm must incur regret at least Omega(sqrt{T-k}). This lower bound directly extends to adversarial environments. On the positive side, we show that widetilde{O}(min{T/k,sqrt{T-k}}) regret is still achievable when rewards are stochastic and i.i.d., and establish a matching lower bound, up to logarithmic factors. Together, these results provide a complete characterization of the benefits of best-action queries in the bandit-feedback model.

Source: arXiv cs.AI | 2026-05-12