Leveraging Similarities in Multi-Armed Bandits
2026-06-22 • Machine Learning
Machine Learning
AI summaryⓘ
The authors look at online learning problems where actions are related like a family tree, with closer actions more similar. They show that just getting feedback from one chosen action at a time (one-point bandit feedback) usually can't use these similarities effectively. They then design algorithms that do better when more detailed feedback is available, such as knowing losses from multiple actions at once. These algorithms perform well by considering a smaller effective number of actions based on their similarities. As an example, they prove that with two-point feedback, one can achieve good performance in problems where rewards change smoothly over a space of actions.
online learningbandit problemsaction similarityrooted treeloss sequenceone-point bandit feedbackmulti-point feedbackregret boundsLipschitz banditseffective number of actions
Authors
Khaled Eldowa, Thibaud Rahier, Augustin Cablant, Panayotis Mertikopoulos, Pierre Gaillard
Abstract
In many online learning and bandit problems, the actions we consider possess inherent similarities--for instance because they share latent traits, tags, or hierarchical structure. We study online learning with a similarity-structured action set, encoded by a rooted tree whose leaves are the actions and whose levels quantify how closely two actions are related. The loss sequence is assumed tree-compatible: losses of similar actions are constrained to be close. We establish an impossibility result showing that usual one-point bandit feedback cannot, in general, leverage range or tree-induced similarity, even under very strong similarity constraints. We then provide a unified set of algorithms which adapt to a wide range of richer feedback models, from semi-bandit feedback down to multi-point bandit protocols, including the minimal two-point feedback setting. We show these algorithms exhibit best-of-both-worlds guarantees and provably exploit action similarities by replacing the number of actions $K$ by a similarity-aware effective number of actions $K_{\mathrm{eff}}$ in the regret bounds. As an application, we show that under two-point feedback, it is possible to achieve $\sqrt{T}$ regret in Lipschitz bandits when $d \leq 2$.