Abstract
This paper introduces multi-level Thompson Sampling algorithms designed for multi-armed bandit (MAB) problems where arms are organized into clusters or hierarchies. By leveraging this structure, the proposed methods—TSC (Thompson Sampling for Clustered arms) and HTS (Hierarchical Thompson Sampling)—significantly reduce cumulative regret. The key contribution is shifting the performance bottleneck from the total number of arms ($N$) to the number of clusters ($K$), making these algorithms highly effective for large-scale recommendation systems where $N$ can reach millions.
Introduction
In the standard MAB framework, a learner attempts to identify the optimal action (arm) to maximize cumulative rewards. A fundamental challenge in modern applications, such as e-commerce, is that the "regret"—the difference between the earned reward and the reward of the optimal action—typically scales linearly with the number of arms $N$. When $N$ is massive, exploration becomes prohibitively expensive.
However, in many real-world scenarios, arms are naturally organized into categories or clusters. For instance, products on a retail site are grouped into hierarchies like "Electronics" or "Kitchen Appliances." This paper explores how to mathematically exploit this known cluster structure to improve exploration efficiency and minimize regret.
Methodology
The authors propose three primary algorithms based on Thompson Sampling (TS), a Bayesian approach that selects actions based on their probability of being optimal:
- TSC (Thompson Sampling for Clustered arms): A two-level policy for disjoint clusters. It first uses a TS instance to select a cluster, then a second TS instance to pick an arm within that cluster.
- HTS (Hierarchical Thompson Sampling): An extension of TSC for tree-structured hierarchies, recursively applying TS at every level until a leaf (arm) is reached.
- LinTSC: A variant for contextual bandits where rewards depend on external features, utilizing linear reward models at both cluster and arm levels.
A critical innovation is the multi-level update: upon receiving a reward, the algorithm updates the belief for the specific arm and every node in the hierarchical path leading to it.
Key Insights and Theoretical Bounds
The most significant theoretical insight is that under a condition called "Strong Dominance"—where the best arm in the optimal cluster is superior to any arm in sub-optimal clusters—the regret no longer depends on the total number of arms $N$. Instead, it depends on the number of clusters $K$ and the number of arms in the optimal cluster $A^*$.
For extremely large $N$, HTS provides a regret dependence of $O(\log_2 N)$ when using a full binary tree, representing a massive improvement over the standard $O(N)$ scaling.
Experimental Results
The algorithms were tested against synthetic Bernoulli bandits and complex reward functions.
As shown in the figure above, as $N$ increases from 10 to 150, the regret for standard TS climbs steeply. In contrast, the regret for TSC remains relatively flat, confirming its ability to successfully exploit cluster structure and break the linear dependence on $N$.
Furthermore, the experiments demonstrate that the performance bottleneck shifts to the number of clusters $K$. While TSC consistently outperforms standard TS, its regret does increase with the complexity of the cluster space, as seen in the scaling with $K$.
Limitations and Future Work
While robust, the current algorithms require the clustering or hierarchy to be provided upfront; they do not yet learn the structure from scratch. Additionally, the tightest theoretical bounds rely on the "Strong Dominance" assumption. Future work aims to explore regret under weaker assumptions and adapt the models for dynamic clusters where categories may shift over time.
Summary updated