Hierarchical Adaptive Contextual Bandits for Resource Constraint based Recommendation

Mengyue Yang, Qingyang Li, Zhiwei Tony Qin, Jieping Ye

Introduction

In standard Multi-Armed Bandit (MAB) problems, an agent aims to maximize rewards by selecting the best "arm" (e.g., a news article or advertisement) based on user context. However, real-world applications often face resource constraints, such as a limited marketing budget or a fixed number of ad impressions. In these scenarios, exploration is not free; every recommendation consumes a unit of a finite resource.

Existing approaches often rely on greedy strategies that prioritize immediate reward-to-cost ratios. These methods frequently fail over long time horizons because they exhaust their budget prematurely on low-value contexts. The challenge lies in balancing the exploration-exploitation trade-off not just across items, but across user contexts over time, ensuring resources are preserved for the most valuable opportunities.

The HATCH Framework

The authors propose the Hierarchical AdapTive Contextual bandit metHod (HATCH) to address these constraints. HATCH organizes the decision-making process into a two-level hierarchy:

  1. Upper Level (Resource Allocation): This level acts as a gatekeeper. It clusters incoming users into finite classes based on historical data. Using a Dynamic Resource Allocation (DRA) strategy based on adaptive linear programming, it determines the probability of "retaining" a user context. It evaluates the remaining budget, remaining time, and estimated reward for that user class to decide if spending a unit of budget is currently optimal.
  2. Lower Level (Personalized Recommendation): If the upper level decides to proceed, the lower level selects the best individual arm using high-dimensional contextual features. This level typically employs a linear model (similar to LinUCB) to estimate specific rewards.
The HATCH framework architecture, illustrating the two-level hierarchy between resource allocation and personalized recommendation.

Unlike previous "Bandits with Knapsacks" approaches that require known prior distributions of users, HATCH adaptively updates its allocation strategy as it learns the reward distributions of different user clusters.

Experimental Evaluation

The researchers evaluated HATCH using both synthetic and real-world datasets:

  • Synthetic Dataset: A controlled environment with 10 user classes and 10 arms, testing various budget-to-time ratios ($\rho$).
  • Yahoo! Today Module: A real-world benchmark containing 4.68 million user/article interactions. A subset of 1.28 million events was used with a modified "reject sampling" evaluation to ensure stable user distribution testing.

Key Insights and Results

A core innovation of HATCH is Context-Aware Budgeting. By clustering users, the algorithm learns that certain user types are inherently more valuable. It learns to "skip" low-value contexts to save budget for high-value ones later in the time horizon. This is achieved through Adaptive Thresholding, where HATCH uses the ratio of remaining budget to remaining time to adjust its risk tolerance.

Allocation Rate vs. Average Reward across User Classes (at $\rho = 0.25$), demonstrating how HATCH prioritizes resources for high-reward contexts.

Performance Highlights

  • Superior CTR: On the Yahoo! dataset with a budget ratio of $\rho = 0.5$, HATCH achieved a Click-Through Rate (CTR) of 4.04, significantly outperforming greedy-LinUCB (3.29) and random-LinUCB (2.92).
  • Theoretical Optimality: The authors proved that HATCH's cumulative regret grows at a rate of $O(\sqrt{T})$, which is theoretically optimal for this class of problem.
  • Stability: While greedy methods often see a sharp decline in rewards once the budget is exhausted, HATCH maintains a stable reward rate by pacing its spending throughout the entire horizon.

Conclusion

HATCH provides a robust solution for personalized recommendations under resource constraints. By separating global resource management from local item selection, it achieves state-of-the-art performance and theoretical efficiency. Future work may focus on handling non-stationary user distributions and extending the framework to more complex, multi-resource constraints.

Summary updated

Abstract

Contextual multi-armed bandit (MAB) achieves cutting-edge performance on a variety of problems. When it comes to real-world scenarios such as recommendation system and online advertising, however, it is essential to consider the resource consumption of exploration. In practice, there is typically non-zero cost associated with executing a recommendation (arm) in the environment, and hence, the policy should be learned with a fixed exploration cost constraint. It is challenging to learn a global optimal policy directly, since it is a NP-hard problem and significantly complicates the exploration and exploitation trade-off of bandit algorithms. Existing approaches focus on solving the problems by adopting the greedy policy which estimates the expected rewards and costs and uses a greedy selection based on each arm's expected reward/cost ratio using historical observation until the exploration resource is exhausted. However, existing methods are hard to extend to infinite time horizon, since the learning process will be terminated when there is no more resource. In this paper, we propose a hierarchical adaptive contextual bandit method (HATCH) to conduct the policy learning of contextual bandits with a budget constraint. HATCH adopts an adaptive method to allocate the exploration resource based on the remaining resource/time and the estimation of reward distribution among different user contexts. In addition, we utilize full of contextual feature information to find the best personalized recommendation. Finally, in order to prove the theoretical guarantee, we present a regret bound analysis and prove that HATCH achieves a regret bound as low as $O(\sqrt{T})$. The experimental results demonstrate the effectiveness and efficiency of the proposed method on both synthetic data sets and the real-world applications.
BibTeX
@inproceedings{yang2020hierarchical,
  author = {Mengyue Yang and Qingyang Li and Zhiwei Tony Qin and Jieping Ye},
  title = {{Hierarchical Adaptive Contextual Bandits for Resource Constraint based Recommendation}},
  booktitle = {The Web Conference},
  year = {2020},
  url = {https://openreview.net/forum?id=i-7iwUadDSD},
}
Figure