Hierarchical Adaptive Contextual Bandits for Resource-Constrained Recommendation (HATCH): A Detailed Review

The article reviews the paper "Hierarchical Adaptive Contextual Bandits for Resource Constraint based Recommendation" (HATCH) presented at WWW 2020 Research Track Oral, explaining how the method addresses resource‑constrained recommendation problems that traditional greedy strategies fail to solve.

It begins with a background on multi‑armed bandits, describing how states correspond to user contexts, actions to recommendable items, and rewards to user feedback, and highlights the challenge when each recommendation consumes a unit of limited resource such as ad impressions.

HATCH introduces a two‑layer hierarchical architecture: an upper resource‑allocation layer that decides how much resource to assign to each user class, and a lower personalization layer that performs contextual bandit recommendation within the allocated resource.

The method first clusters user features to obtain user classes with probabilities \(\oint\) and class centroids. Assuming user class distributions remain stationary, the cumulative reward maximization objective can be transformed into a per‑round expected reward maximization, where the expected reward for class \(u\) is estimated.

In the resource‑allocation layer, a linear model \(\hat{u}_{t,j}=x_{\sim j}^T \theta_{\sim t,j}\) estimates the value of each user class at learning step \(t\). Solving a linear program yields the resource‑allocation probability \(p\), which is updated after each feedback using the estimated parameters \(\theta\).

The personalization layer employs a standard contextual bandit with a linear reward estimator and an exploration term, selecting actions according to \(\hat{r}=\phi^T \beta + \alpha \sqrt{\phi^T A^{-1} \phi}\). After observing the reward, the layer updates its parameters via a ridge‑regression style rule.

Cumulative regret, defined as the gap between the optimal reward and the reward obtained by the algorithm, is derived analytically (see the displayed formula image). The bound shows that HATCH achieves sub‑linear regret.

Experimental evaluation on both synthetic data (generated by a linear model) and real Yahoo Today Model data demonstrates that HATCH attains lower cumulative regret and higher average click‑through rate (CTR) compared with baseline methods. The experiments also reveal that the algorithm explores low‑value user classes early on, ensuring balanced resource distribution before exploitation.

The conclusion notes that while HATCH adapts resource allocation dynamically, real‑world environments evolve over time, suggesting future extensions to non‑stationary settings. Links to the arXiv paper and the GitHub implementation are provided.