Stochastic Low-rank Tensor Bandits for Multi-dimensional Online Decision Making

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

In the world of online recommendation and digital marketing, decisions are rarely one-dimensional. A marketer doesn't just pick an "ad"; they pick a combination of a user segment, a promotion offer, and a delivery channel. When you combine these choices, the number of possible actions explodes—a phenomenon known as the curse of dimensionality.

A new paper, "Stochastic Low-rank Tensor Bandits for Multi-dimensional Online Decision Making," introduces a framework to navigate this complexity by treating rewards not as a flat list, but as a low-rank tensor.

TL;DR

The authors propose a "tensor bandit" framework that exploits the inherent low-rank structure of multi-dimensional rewards to solve the "cold-start" problem in massive action spaces. Their new algorithms, tensor elimination and tensor epoch-greedy, achieve significantly lower regret than standard methods by reducing the required exploration from an exponential to a sub-linear dependency on dimensions.

What Problem Does This Paper Address?

Standard Multi-Armed Bandit (MAB) algorithms struggle when the number of "arms" is huge. If you have 100 user segments, 100 offers, and 10 channels, a traditional bandit sees $100 \times 100 \times 10 = 100,000$ independent arms. To even begin learning, it would need to pull every single combination at least once—a feat that is often computationally impossible and financially ruinous in a real-world "cold-start" scenario.

Existing solutions usually "vectorize" the problem (flattening the tensor into a long list) or "matricize" it (collapsing dimensions into a 2D grid). Both approaches are sub-optimal: vectorization ignores the multi-way correlations between entities, and matricization fails to capture the full structural richness of higher-order interactions ($d \ge 3$).

Figure 1: An example of interactive multi-dimensional online decision making. The rewards from all sequential multi-dimensional decisions formulate a tensor.

Methods

The core idea is to assume the underlying reward tensor $\mathcal{X}$ is low-rank, specifically following a Tucker decomposition. This means the complex interactions can be represented by a small "core" tensor and a few factor matrices.

The authors introduce three primary algorithms:

  1. Tensor Elimination: This algorithm uses a "spectral-based rotation" strategy. It first performs a brief random exploration to estimate the factor matrices, then rotates the action space to concentrate the reward information into a low-dimensional subspace. It then applies an Upper Confidence Bound (UCB) approach to eliminate sub-optimal arms.
  2. Tensor Epoch-greedy: A simpler approach that alternates between exploration (random pulls) and exploitation (pulling the current best-estimated arm). The length of the exploitation phases grows over time as the model's accuracy improves.
  3. Tensor Ensemble Sampling: Designed for contextual settings (where some dimensions, like the specific user or day of the week, are fixed by the environment). Because exact Bayesian updates for low-rank tensors are computationally intractable, this method uses an ensemble of models to approximate Thompson Sampling.

Datasets

The researchers evaluated their algorithms using both synthetic simulations and real-world datasets:

  • Synthetic Tensors: Order-3 tensors with varying dimensions ($p=15, 20$) and signal-to-noise ratios.
  • Online Advertising Data (Contextual): A dataset of ad impressions across 20 users, 7 days of the week, and 20 different advertisements.
  • Online Advertising Data (Non-contextual): A dataset of ad clicks across 20 advertisements, 10 publishers, and 7 days.

Key Insights and Ideas

  • The Power of Rotation: The "spectral rotation" in Tensor Elimination is a major technical contribution. It allows the researchers to transform a non-convex tensor problem into a structured linear bandit problem, enabling rigorous uncertainty quantification that was previously elusive for tensors.
  • Dimension vs. Time Horizon: The paper reveals a fascinating trade-off in regret bounds. Tensor epoch-greedy has a better dependency on the tensor's dimensions ($p$), making it superior for high-dimensional problems with short time horizons. Conversely, tensor elimination has a better dependency on the time horizon ($n$), making it the winner for long-running campaigns.
  • Initialization Efficiency: By exploiting low-rankness, the initialization phase only requires $O(p^{d/2})$ steps, a massive improvement over the $O(p^d)$ steps required by standard vectorization.

Key Results

The theoretical improvements are stark. As shown in the extracted table below, the regret bounds for the proposed tensor methods have much sharper dependencies on the dimension $p$ compared to existing competitors.

Table 1: Comparison of regret bounds. $n$ is the time horizon, $p$ is the max dimension, and $d$ is the tensor order. Note the significant reduction in the power of $p$ for the proposed methods.

In practical tests on real-world advertising data:

  • Tensor Ensemble Sampling reduced cumulative regret by 75% compared to vectorized UCB.
  • In non-contextual settings, both tensor algorithms significantly outperformed "Matricized ESTR," which is the current state-of-the-art for matrix-based bandits.

Limitations and Future Work

  • Known Rank: The current theory assumes the rank of the reward tensor is known beforehand. In practice, this must be estimated, and the authors suggest ad-hoc methods for this, but a formal integrated approach remains future work.
  • Non-Convexity: Tensor decomposition is inherently non-convex. While the bi-convex nature of their optimization ensures convergence to local optima, there is no theoretical guarantee of reaching the global optimum in every step.
  • Bayesian Theory: The Bayes regret bound for the ensemble sampling method is still preliminary and does not yet fully exploit the low-rank structure in its theoretical derivation, marking a challenging open problem for the community.

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. Extensive simulations and real analysis in online advertising data back up our theoretical findings and show that our algorithms outperform various state-of-the-art approaches that ignore the tensor low-rank structure.
BibTeX
@article{zhou2024stochastic,
  author = {Jie Zhou and Botao Hao and Zheng Wen and Jingfei Zhang and Will Wei Sun},
  title = {{Stochastic Low-rank Tensor Bandits for Multi-dimensional Online Decision Making}},
  journal = {Journal of the American Statistical Association},
  year = {2024},
  doi = {10.1080/01621459.2024.2311364},
}
Figure