# Cost-Aware Optimal Pairwise Pure Exploration

arXiv: https://arxiv.org/abs/2503.07877 · HTML: https://mlsanity.com/paper/2503.07877/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 34 references that are in the map.
- First posted on arXiv 10 Mar 2025.

## Builds on (most cited first, 16 of 16)

- [On the Complexity of Best Arm Identification in Multi-Armed Bandit Models](https://mlsanity.com/paper/1407.4443/) (2014)
- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Contextual Dueling Bandits](https://mlsanity.com/paper/1502.06362/) (2015)
- [Best-Arm Identification in Linear Bandits](https://mlsanity.com/paper/1409.6110/) (2014)
- [Tight (Lower) Bounds for the Fixed Budget Best Arm Identification Bandit Problem](https://mlsanity.com/paper/1605.09004/) (2016)
- [Optimal Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2006.16073/) (2020)
- [Lipschitz Bandits: Regret Lower Bounds and Optimal Algorithms](https://mlsanity.com/paper/1405.4758/) (2014)
- [On Multi-Armed Bandit Designs for Dose-Finding Clinical Trials](https://mlsanity.com/paper/1903.07082/) (2019)
- [Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection](https://mlsanity.com/paper/1702.03605/) (2017)
- [On the bias, risk and consistency of sample means in multi-armed bandits](https://mlsanity.com/paper/1902.00746/) (2019)
- [Minimax Optimal Algorithms for Fixed-Budget Best Arm Identification](https://mlsanity.com/paper/2206.04646/) (2022)
- [Nearly Optimal Sampling Algorithms for Combinatorial Pure Exploration](https://mlsanity.com/paper/1706.01081/) (2017)
- [Cost Aware Best Arm Identification](https://mlsanity.com/paper/2402.16710/) (2024)
- [Best Arm Identification with Fixed Budget: A Large Deviation Perspective](https://mlsanity.com/paper/2312.12137/) (2023)
- [Fast and Regret Optimal Best Arm Identification: Fundamental Limits and Low-Complexity Algorithms](https://mlsanity.com/paper/2309.00591/) (2023)
- [Approximate Top-m Arm Identification with Heterogeneous Reward Variances](https://mlsanity.com/paper/2204.05245/) (2022)

## Abstract (arXiv)

Pure exploration is one of the fundamental problems in multi-armed bandits (MAB). However, existing works mostly focus on specific pure exploration tasks, without a holistic view of the general pure exploration problem. This work fills this gap by introducing a versatile framework to study pure exploration, with a focus on identifying the pairwise relationships between targeted arm pairs. Moreover, unlike existing works that only optimize the stopping time (i.e., sample complexity), this work considers that arms are associated with potentially different costs and targets at optimizing the cumulative cost that occurred during learning. Under the general framework of pairwise pure exploration with arm-specific costs, a performance lower bound is derived. Then, a novel algorithm, termed CAET (Cost-Aware Pairwise Exploration Task), is proposed. CAET builds on the track-and-stop principle with a novel design to handle the arm-specific costs, which can potentially be zero and thus represent a very challenging case. Theoretical analyses prove that the performance of CAET approaches the lower bound asymptotically. Special cases are further discussed, including an extension to regret minimization, which is another major focus of MAB. The effectiveness and efficiency of CAET are also verified through experimental results under various settings.