# Leveraging Similarities in Multi-Armed Bandits

arXiv: https://arxiv.org/abs/2606.23414 · HTML: https://mlsanity.com/paper/2606.23414/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 39 references that are in the map.
- First posted on arXiv 22 Jun 2026.

## Builds on (most cited first, 20 of 20)

- [Online Learning: A Modern Introduction Using Convex Optimization](https://mlsanity.com/paper/1912.13213/) (2019)
- [Optimal rates for zero-order convex optimization: the power of two function evaluations](https://mlsanity.com/paper/1312.2139/) (2013)
- [Tsallis-INF: An Optimal Algorithm for Stochastic and Adversarial Bandits](https://mlsanity.com/paper/1807.07623/) (2018)
- [An Optimal Algorithm for Bandit and Zero-Order Convex Optimization with Two-Point Feedback](https://mlsanity.com/paper/1507.08752/) (2015)
- [Bandits and Experts in Metric Spaces](https://mlsanity.com/paper/1312.1277/) (2013)
- [Minimal Exploration in Structured Stochastic Bandits](https://mlsanity.com/paper/1711.00400/) (2017)
- [Efficient Learning in Large-Scale Combinatorial Semi-Bandits](https://mlsanity.com/paper/1406.7443/) (2014)
- [Hierarchical Bayesian Bandits](https://mlsanity.com/paper/2111.06929/) (2021)
- [A Blackbox Approach to Best of Both Worlds in Bandits and Beyond](https://mlsanity.com/paper/2302.09739/) (2023)
- [Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2206.00873/) (2022)
- [Refined Lower Bounds for Adversarial Bandits](https://mlsanity.com/paper/1605.07416/) (2016)
- [Deep Hierarchy in Bandits](https://mlsanity.com/paper/2202.01454/) (2022)
- [Robust Lipschitz Bandits to Adversarial Corruptions](https://mlsanity.com/paper/2305.18543/) (2023)
- [Mixed-Effect Thompson Sampling](https://mlsanity.com/paper/2205.15124/) (2022)
- [Adaptation to Easy Data in Prediction with Limited Advice](https://mlsanity.com/paper/1807.00636/) (2018)
- [Zeroth-order non-convex learning via hierarchical dual averaging](https://mlsanity.com/paper/2109.05829/) (2021)
- [Nested bandits](https://mlsanity.com/paper/2206.09348/) (2022)
- [Bandits with Side Observations: Bounded vs. Logarithmic Regret](https://mlsanity.com/paper/1807.03558/) (2018)
- [Prior-Dependent Allocations for Bayesian Fixed-Budget Best-Arm Identification in Structured Bandits](https://mlsanity.com/paper/2402.05878/) (2024)
- [Adaptive Regret for Bandits Made Possible: Two Queries Suffice](https://mlsanity.com/paper/2401.09278/) (2024)

## Abstract (arXiv)

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 Keff in the regret bounds. As an application, we show that under two-point feedback, it is possible to achieve √T regret in Lipschitz bandits when d ≤ 2.