Dissimilarity Bandits

Paolo Battellani, Alberto Maria Metelli, Francesco TrovòAISTATS 2024

Abstract

Traditional Multi-Armed Bandit (MAB) problems focus on identifying the single arm with the highest expected reward. This paper introduces the Dissimilarity Bandit problem, where the objective is to find the pair of arms that maximizes a given dissimilarity function. We present the Successive Elimination for Dissimilarity (SED) algorithm, which maintains confidence sets for individual arms to prune suboptimal pairs. Theoretical analysis shows that SED achieves a sample complexity that scales linearly with the number of arms rather than quadratically. Empirical results on synthetic and real-world datasets demonstrate that SED provides significant sample efficiency gains, particularly in high-dimensional settings.

Introduction

In many practical scenarios, the goal of data collection is not to find an optimal single entity, but to identify extreme differences. For instance, in environmental monitoring, researchers may seek the two time periods during which water quality profiles are most divergent to understand the impact of human activity. This task is formalized as the Dissimilarity Bandit problem: given $K$ arms, each producing $d$-dimensional observation vectors, identify the pair $\{i, j\}$ that maximizes a dissimilarity function $w(\mu_i, \mu_j)$.

The primary challenge lies in the combinatorial explosion of potential pairs ($O(K^2)$) and the multi-dimensionality of observations. Naive approaches that treat each pair as an independent arm fail to exploit the fact that a single sample from arm $i$ provides information about its dissimilarity to all other $K-1$ arms.

Methodology

The proposed Successive Elimination for Dissimilarity (SED) algorithm addresses these challenges by maintaining confidence sets $\mathcal{C}_{i,t}^\delta$ for the mean vector $\mu_i$ of each individual arm.

Algorithm 1: Successive Elimination for Dissimilarity (SED).

As shown in Algorithm 1, SED iteratively pulls arms and updates these confidence sets. A pair of arms is pruned from the candidate set $\mathcal{S}$ as soon as the maximum possible dissimilarity between them is strictly less than the minimum possible dissimilarity of the current best candidate pair. By focusing on individual arm estimates rather than pair-wise estimates, SED "reuses" samples across all pairs involving a specific arm, leading to a complexity index that scales linearly with $K$.

Experimental Evaluation

The performance of SED was evaluated across synthetic 1D and $d$-dimensional environments ($d=16$), as well as a real-world water quality dataset.

Synthetic Environments

In high-dimensional synthetic tests, SED demonstrated remarkable efficiency. Compared to "BAI on Pairs" (algorithms that treat every pair as an independent arm, such as SE-P and LIL-LUCB-P), SED required significantly fewer samples to identify the most dissimilar pair with the same confidence level. In $d=16$ settings, the authors report speedups of roughly two orders of magnitude.

Empirical performance comparison of SED and baseline algorithms across three synthetic environments.

As illustrated in Figure 1, SED (represented by the brown '+' markers) consistently outperforms the pair-based baselines (SE-P and LIL-LUCB-P) across various environments and confidence levels $\delta$. In 1D environments (Env #1 and #2), SED also remains competitive with specialized "Max-Min" baselines (SE-MM and LIL-LUCB-MM), which are only applicable in scalar settings.

Real-World Application

On a 30-day water quality monitoring dataset, where arms represented hours of the day and rewards were fluorescence response grids, SED achieved a 60% reduction in the number of samples required compared to standard baseline approaches. This confirms the algorithm's practical utility in resource-constrained monitoring tasks.

Conclusion

The Dissimilarity Bandit framework and the SED algorithm provide a robust solution for finding the "odd ones out" in multi-dimensional data. By proving that the sample complexity is essentially linear in the number of arms, this work establishes a new theoretical benchmark for dissimilarity-based search. Future research may extend this work to settings where the dissimilarity metric is unknown or where arms exhibit temporal correlations, further enhancing the efficiency of environmental and industrial monitoring systems.

Summary updated

BibTeX
@inproceedings{battellani2024dissimilarity,
  author = {Paolo Battellani and Alberto Maria Metelli and Francesco Trovò},
  title = {{Dissimilarity Bandits}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
}
Figure