Low-rank Tensor Bandits

Botao Hao, Jie Zhou, Zheng Wen, Will Wei Sun

TL;DR

This paper introduces "low-rank tensor bandits" to tackle complex, multi-dimensional online decision-making problems, like personalized recommendations. They propose novel algorithms that outperform existing methods by effectively leveraging the inherent low-rank structure of the underlying reward data, leading to significantly reduced regret.

What Problem Does This Paper Address?

Many real-world applications, such as online advertising and recommendation systems, involve making decisions across multiple dimensions simultaneously. For instance, a marketer might need to choose an optimal combination of user segment, promotion offer, and advertising channel. These decisions can be modeled as selecting an "arm" in a multi-dimensional "tensor" of rewards. Traditional bandit algorithms struggle with this high dimensionality, often leading to inefficient exploration and poor decision-making (high regret). This paper addresses this by proposing methods that specifically exploit the often-present low-rank structure in these high-dimensional reward tensors, which is a common characteristic in such applications.

Methods

The authors propose two main algorithms for "tensor bandits without context":

  • Tensor Elimination: This algorithm adapts the successful Upper Confidence Bound (UCB) strategy. It cleverly transforms the tensor bandit problem into a lower-dimensional linear bandit problem by using a tensor spectral-based rotation strategy. This allows for uncertainty quantification and efficient elimination of unpromising arms, leading to strong theoretical regret bounds.
  • Tensor Epoch-Greedy: This algorithm follows an epoch-based approach, alternating between exploration (random arm pulls) and exploitation (pulling the best-estimated arm). It's simpler to implement and offers a better dependency on tensor dimensions, making it competitive for shorter time horizons.

For "tensor bandits with context" (where some dimensions are contextual and not controlled by the agent), they develop:

  • Tensor Ensemble Sampling: This is a Bayesian algorithm that uses Thompson sampling and an ensemble of models to approximate the posterior distribution. It's designed to be computationally tractable and empirically effective, particularly in scenarios with contextual information.

Datasets

The paper uses simulated data for experiments and also presents a real-world application on online advertising data. This data is structured as a third-order tensor representing impressions for advertisements across users, days of the week, and advertisements.

Key Insights and Ideas

  • Low-rank structure is key: The paper strongly emphasizes that the low-rank property of reward tensors is not just a mathematical convenience but a crucial structural element that can be exploited for significant performance gains in online decision-making.
  • Beyond Vectorization: Simply flattening a high-dimensional tensor into a vector (vectorization) for standard bandit algorithms leads to information loss and poor performance. The proposed methods retain and leverage the tensor structure.
  • Contextual vs. Non-Contextual: The paper distinguishes between problems where the agent controls all decision dimensions (non-contextual) and those where some dimensions are external (contextual), requiring different algorithmic approaches.
  • Theoretical Guarantees Matter: The authors provide finite-time regret bounds for their algorithms, offering theoretical justification for their effectiveness and insights into their performance trade-offs (e.g., dimension vs. time horizon dependency).

Key Results

  • Outperformance: Both theoretical analysis and empirical simulations show that the proposed algorithms (Tensor Elimination, Tensor Epoch-Greedy, and Tensor Ensemble Sampling) outperform baseline methods like vectorized UCB and matricized ESTR, especially in high-dimensional settings.
  • Tensor Ensemble Sampling Dominance: In the contextual online advertising application, Tensor Ensemble Sampling achieved a 75% reduction in cumulative regret compared to vectorized UCB and 85.6% reduction compared to tensor epoch-greedy.
  • Regret Bound Improvements: Tensor Elimination offers the best overall regret bound for long time horizons, while Tensor Epoch-Greedy is more competitive for short horizons and has a better dependency on tensor dimensions.

Limitations and Future Work

  • Hyperparameter Tuning: The paper acknowledges that hyperparameter tuning in bandit problems is challenging due to the real-time, irreversible nature of decisions. While they conduct sensitivity analyses, finding optimal hyperparameters in practice can still be difficult.
  • Rank Determination: Determining the appropriate low-rank for tensor models is an open problem. The current work assumes prior knowledge of the true rank, but the authors suggest that ad-hoc methods could be employed in practice.
  • Bayesian Regret for TS: The theoretical analysis for Tensor Ensemble Sampling (an approximate Thompson Sampling algorithm) focuses on Bayes regret, and the authors believe its dependence on tensor dimension p could be further improved by better exploiting the low-rank structure.
  • Non-convex Optimization: The optimization problems in some of the algorithms (e.g., Tensor Ensemble Sampling) are non-convex, meaning they might converge to local optima. While empirically effective, a deeper theoretical understanding of this aspect is a future research direction.

Summary updated

Abstract

Multi-dimensional online decision making plays a crucial role in many real applications such as online recommendation and digital marketing. In these problems, a decision at each time is a combination of choices from different types of entities. To solve it, we introduce stochastic low-rank tensor bandits, a class of bandits whose mean rewards can be represented as a low-rank tensor. We consider two settings, tensor bandits without context and tensor bandits with context. In the first setting, the platform aims to find the optimal decision with the highest expected reward, a.k.a, the largest entry of true reward tensor. In the second setting, some modes of the tensor are contexts and the rest modes are decisions, and the goal is to find the optimal decision given the contextual information. We propose two learning algorithms tensor elimination and tensor epoch-greedy for tensor bandits without context, and derive finite-time regret bounds for them. Comparing with existing competitive methods, tensor elimination has the best overall regret bound and tensor epoch-greedy has a sharper dependency on dimensions of the reward tensor. Furthermore, we develop a practically effective Bayesian algorithm called tensor ensemble sampling for tensor bandits with context. Numerical experiments back up our theoretical findings and show that our algorithms outperform various state-of-the-art approaches that ignore the tensor low-rank structure. In an online advertising application with contextual information, our tensor ensemble sampling reduces the cumulative regret by 75% compared to the benchmark method.
BibTeX
@article{hao2024low,
  author = {Botao Hao and Jie Zhou and Zheng Wen and Will Wei Sun},
  title = {{Low-rank Tensor Bandits}},
  journal = {Journal of the American Statistical Association},
  year = {2024},
  doi = {10.1080/01621459.2024.2311364},
}
Figure