Pure exploration in multi-armed bandits with low rank structure using oblivious sampler

Yaxiong Liu, Atsuyoshi Nakamura, Kohei Hatano, Eiji TakimotoarXiv 2023 · arXiv

TL;DR

This paper introduces a "separated" pure exploration setting for multi-armed bandits where the exploration strategy samples arms obliviously without seeing rewards, while a separate recommendation strategy makes the final choice. By leveraging a low-rank reward structure, the authors design efficient algorithms for both fixed and stochastic kernels, achieving near-optimal regret bounds with only a small logarithmic gap from the theoretical lower bound.

What Problem Does This Paper Address?

Traditional pure exploration in multi-armed bandits (MAB) assumes adaptive sampling—the algorithm pulls an arm, observes the reward, and uses that feedback to decide which arm to pull next.

However, real-world scenarios like crowdsourcing platforms often separate these roles due to privacy or system constraints. For example, a platform might select workers (exploration) without knowing the confidential task rewards, while the end-user observes the rewards and makes the final decision (recommendation). This is known as the oblivious sampling or separated setting.

To make learning feasible in large arm spaces ($N$ arms) under this constraint, the authors incorporate a low-rank structure, where the reward vector depends on a lower-dimensional ($d \ll N$) latent space defined by a kernel matrix and a seed vector. The challenge is designing an exploration strategy that provides enough information to the recommendation strategy without ever seeing the feedback from its own choices.

Methods

The authors propose two main algorithms depending on the nature of the kernel matrix:

  1. Stochastic (Time-Varying) Kernel: The exploration strategy samples arms uniformly at random. The recommendation strategy then constructs an unbiased estimator of the latent seed vector using the provided kernel information, ultimately recommending the arm that maximizes the estimated reward.
  2. Fixed Kernel: Instead of uniform sampling over all $N$ arms, the algorithm uses a Bary-centric spanner to identify $d$ "important arms" that geometrically span the latent reward space. The exploration strategy cycles through these $d$ arms uniformly, and the recommendation strategy estimates the seed vector based solely on their feedback.

Datasets

Not discussed in the paper. This is a purely theoretical paper focused on mathematical proofs and algorithmic regret bounds; no empirical evaluation or datasets were used.

Key Insights and Ideas

  • Separation of Powers: Decoupling exploration from feedback means standard adaptive approaches (like UCB or Thompson Sampling) fail completely. Uniform or structured oblivious sampling is required.
  • The Power of Low Rank: Even without feedback during exploration, knowing the kernel structure allows the recommendation engine to project high-dimensional arm spaces ($N$) down to a manageable low-dimensional space ($d$), making oblivious learning efficient.
  • Bary-centric Spanners as Dimensionality Reducers: For fixed kernels, you don't need to waste time exploring all $N$ arms. Exploring just $d$ core spanning arms provides enough geometric coverage to accurately estimate the rewards of all other arms.

Key Results

The authors provide a comprehensive theoretical analysis comparing oblivious and adaptive samplers across fixed and stochastic kernels, summarized in the paper's main table:

Table 1: Comparison with our work and previous works
  • For the Fixed Kernel setting with an oblivious sampler, their algorithm achieves a simple regret bound of $O\left(\frac{d\sqrt{\ln N}}{\sqrt{n}}\right)$.
  • For the Stochastic Kernel setting, the algorithm achieves a bound of $O\left(\sqrt{\frac{d^2\ln N}{n}}\right)$.
  • They also establish a lower bound of $\Omega\left(\sqrt{\frac{d\ln N}{n}}\right)$ when $d \ge \ln N$, revealing a tight $\sqrt{\ln N}$ gap between their oblivious upper bounds and the fundamental limits of the setting.

Limitations and Future Work

  • Prior Kernel Knowledge: The current algorithms strictly require the kernel matrix information to be known in advance for each round, which may not always be practical.
  • Future Directions: The authors highlight two major open problems:
  • Designing efficient oblivious algorithms that do not require prior knowledge of the kernel matrix.
  • Extending this framework to adversarial multi-armed bandits with low-rank rewards.

Summary updated

Abstract

In this paper, we consider the low rank structure of the reward sequence of the pure exploration problems. Firstly, we propose the separated setting in pure exploration problem, where the exploration strategy cannot receive the feedback of its explorations. Due to this separation, it requires that the exploration strategy to sample the arms obliviously. By involving the kernel information of the reward vectors, we provide efficient algorithms for both time-varying and fixed cases with regret bound $O(d\sqrt{(\ln N)/n})$. Then, we show the lower bound to the pure exploration in multi-armed bandits with low rank sequence. There is an $O(\sqrt{\ln N})$ gap between our upper bound and the lower bound.
BibTeX
@misc{liu2023pure,
  author = {Yaxiong Liu and Atsuyoshi Nakamura and Kohei Hatano and Eiji Takimoto},
  title = {{Pure exploration in multi-armed bandits with low rank structure using oblivious sampler}},
  year = {2023},
  eprint = {2306.15856},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2306.15856},
}
Figure