Multi-Armed Bandits With Best-Action Queries
Researchers Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi, and Francesco Emanuele Stradi have published a new study resolving an open problem in multi-armed bandit (MAB) theory. The paper investigates MABs augmented with best-action queries, where learners can query an oracle to identify the optimal arm. While previous work by Russo et al. characterized this setting in full-feedback models, this study focuses on the more realistic bandit-feedback model, where only the played arm's reward is observed. The authors demonstrate that for stochastic but correlated rewards, the benefits seen in full-feedback settings do not apply, establishing a regret lower bound of Omega(sqrt(T-k)). Conversely, for independent and identically distributed (i.i.d.) stochastic rewards, they prove that a regret of O(min{T/k, sqrt(T-k)}) is achievable, matching the lower bound up to logarithmic factors. These findings provide a complete characterization of best-action queries' utility in bandit-feedback environments, significantly advancing theoretical understanding in machine learning and artificial intelligence.
Wire timeline
Multi-Armed Bandits With Best-Action Queries
Researchers Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi, and Francesco Emanuele Stradi have published a new study resolving an open problem in multi-armed bandit (MAB) theory. The paper investigates MABs augmented with best-action queries, where learners can query an oracle to identify the optimal arm. While previous work by Russo et al. characterized this setting in full-feedback models, this study focuses on the more realistic bandit-feedback model, where only the played arm's reward is observed. The authors demonstrate that for stochastic but correlated rewards, the benefits seen in full-feedback settings do not apply, establishing a regret lower bound of Omega(sqrt(T-k)). Conversely, for independent and identically distributed (i.i.d.) stochastic rewards, they prove that a regret of O(min{T/k, sqrt(T-k)}) is achievable, matching the lower bound up to logarithmic factors. These findings provide a complete characterization of best-action queries' utility in bandit-feedback environments, significantly advancing theoretical understanding in machine learning and artificial intelligence.
cs.AI updates on arXiv.org