Search papers, labs, and topics across Lattice.
This paper investigates online learning in multi-armed bandit problems where actions exhibit inherent similarities, represented through a rooted tree structure. The authors establish that traditional one-point feedback fails to utilize these similarities effectively, leading to an impossibility result, but they introduce a unified set of algorithms that adapt to richer feedback models, including semi-bandit and two-point feedback. Their algorithms demonstrate improved regret bounds by leveraging action similarities, achieving $\sqrt{T}$ regret in Lipschitz bandits under specific conditions.
Traditional one-point feedback in bandit problems misses the mark, but new algorithms can exploit action similarities to achieve significantly lower regret.
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$.
