publications
2026
- The Sampling Complexity of Condorcet Winner Identification in Dueling BanditsEl Mehdi Saad, Victor Thuot, and Nicolas VerzelenIn Advances in Neural Information Processing Systems , Dec 2026To appear
We study best-arm identification in stochastic dueling bandits under the sole assumption that a Condorcet winner exists, i.e., an arm that wins each noisy pairwise comparison with probability at least 1/2. We introduce a new identification procedure that exploits the full gap matrix Δ(i,j) = q(i,j) − 1/2 (where q(i,j) is the probability that arm i beats arm j), rather than only the gaps between the Condorcet winner and the other arms. We derive high-probability, instance-dependent sample-complexity guarantees that (up to logarithmic factors) improve the best known ones by leveraging informative comparisons beyond those involving the winner. We complement these results with new lower bounds which, to our knowledge, are the first for Condorcet-winner identification in stochastic dueling bandits. Our lower-bound analysis isolates the intrinsic cost of locating informative entries in the gap matrix and estimating them to the required confidence, establishing the optimality of our non-asymptotic bounds. Overall, our results reveal new regimes and trade-offs in the sample complexity that are not captured by asymptotic analyses based only on the expected budget.
@inproceedings{saad:hal-05551276, title = {The Sampling Complexity of {Condorcet} Winner Identification in Dueling Bandits}, author = {Saad, El Mehdi and Thuot, Victor and Verzelen, Nicolas}, booktitle = {Advances in Neural Information Processing Systems}, year = {2026}, month = dec, note = {To appear}, url = {https://hal.science/hal-05551276}, } - The Sample Complexity of Multiple Change Point Identification under Bandit FeedbackMaximilian Graf, and Victor ThuotIn Advances in Neural Information Processing Systems , Dec 2026To appear
We study multiple change point localization under bandit feedback. An unknown piecewise-constant function on a compact interval can be queried sequentially at adaptively chosen inputs, and each query returns a noisy evaluation of the function. The goal is to identify a prescribed number of discontinuities, known as change points, within a target precision η and confidence level 1 − δ, while using as few samples as possible. We propose an adaptive algorithm that first detects intervals likely to contain change points and then refines their locations to precision η. We establish non-asymptotic upper bounds on its sample budget, together with corresponding lower bounds. Prior work shows that jump magnitudes alone determine the asymptotic sample complexity as δ → 0. We reveal that this picture is incomplete beyond this regime. We demonstrate, both empirically and theoretically, that for general δ and η, the complexity is jointly governed by the jumps and the relative positions of the change points.
@inproceedings{graf2026samplecomplexitymultiplechange, title = {The Sample Complexity of Multiple Change Point Identification under Bandit Feedback}, author = {Graf, Maximilian and Thuot, Victor}, booktitle = {Advances in Neural Information Processing Systems}, year = {2026}, month = dec, note = {To appear}, eprint = {2605.13252}, archiveprefix = {arXiv}, url = {https://arxiv.org/abs/2605.13252}, } - Nonparametric Kernel Clustering with Bandit FeedbackOct 2026Preprint
Clustering with bandit feedback refers to the problem of partitioning the arms of an N-armed stochastic bandit according to their underlying distributions, based on noisy observations collected sequentially and adaptively. This setting has attracted growing interest for its applicability in recommendation systems, crowdsourcing, and adaptive trials. Existing works rely on the strong assumption that arm distributions are sub-Gaussian, which can only distinguish arms whose distributions differ in mean - missing realistic settings where distributional differences lie in shape or higher moments. We introduce a framework of nonparametric clustering with bandit feedback, free of any parametric assumptions regarding the arm distributions. We adopt a kernel-based approach and reformulate the problem as clustering arms according to their kernel mean embeddings in a reproducing kernel Hilbert space (RKHS). Building on this formulation, we introduce the KABC algorithm, prove that it is δ-PAC, and derive a non-asymptotic high-probability upper bound on its sampling complexity. The bound is governed by a variance-aware signal-to-noise ratio defined as the minimum over pairs of arms in distinct clusters of the ratio between their squared MMD and their RKHS variance. KABC achieves instance-dependent guarantees while being adaptive to this unknown ratio. We validate our approach empirically on synthetic and real-world datasets, demonstrating that KABC succeeds in distributional clustering settings where mean-based methods fail.
@misc{thuot2026kernel, title = {Nonparametric Kernel Clustering with Bandit Feedback}, author = {Thuot, Victor and Vogt, Sebastian and Ghoshdastidar, Debarghya and Verzelen, Nicolas}, year = {2026}, month = oct, note = {Preprint}, url = {https://hal.science/hal-05451062}, }
2025
- Clustering with bandit feedback: breaking down the computation/information gapIn Proceedings of The 36th International Conference on Algorithmic Learning Theory , Feb 2025
We investigate the Clustering with Bandit feedback Problem (CBP). A learner interacts with an N-armed stochastic bandit with d-dimensional subGaussian feedback. There exists a hidden partition of the arms into K groups, such that arms within the same group share the same mean vector. The learner’s task is to uncover this hidden partition with the smallest budget - i.e. the least number of observations - and with a probability of error smaller than a prescribed constant δ. In this paper, (i) we derive a non asymptotic lower bound for the budget, and (ii) we introduce the computationally efficient ACB algorithm, whose budget matches the lower bound in most regimes. We improve on the performance of a uniform sampling strategy. Importantly, contrary to the batch setting, we establish that there is no computation-information gap in the bandit setting.
@inproceedings{pmlr-v272-thuot25a, title = {Clustering with bandit feedback: breaking down the computation/information gap}, author = {Thuot, Victor and Carpentier, Alexandra and Giraud, Christophe and Verzelen, Nicolas}, booktitle = {Proceedings of The 36th International Conference on Algorithmic Learning Theory}, editor = {Kamath, Gautam and Loh, Po-Ling}, series = {Proceedings of Machine Learning Research}, volume = {272}, pages = {1221--1284}, publisher = {PMLR}, year = {2025}, month = feb, url = {https://proceedings.mlr.press/v272/thuot25a.html}, } - Clustering Items through Bandit Feedback: Finding the Right Feature out of ManyMaximilian Graf, Victor Thuot, and Nicolas VerzelenIn Proceedings of the 42nd International Conference on Machine Learning , Jul 2025
We study the problem of clustering a set of items based on bandit feedback. Each of the n items is characterized by a feature vector, with a possibly large dimension d. The items are partitioned into two unknown groups, such that items within the same group share the same feature vector. We consider a sequential and adaptive setting in which, at each round, the learner selects one item and one feature, then observes a noisy evaluation of the item’s feature. The learner’s objective is to recover the correct partition of the items, while keeping the number of observations as small as possible. We provide an algorithm which relies on finding a relevant feature for the clustering task, leveraging the Sequential Halving algorithm. With probability at least 1 − δ, we obtain an accurate recovery of the partition and derive an upper bound on the budget required. Furthermore, we obtain an instance-dependent lower bound, which is tight in some relevant cases.
@inproceedings{graf2025clustering, title = {Clustering Items through Bandit Feedback: Finding the Right Feature out of Many}, author = {Graf, Maximilian and Thuot, Victor and Verzelen, Nicolas}, booktitle = {Proceedings of the 42nd International Conference on Machine Learning}, series = {Proceedings of Machine Learning Research}, pages = {20296--20325}, publisher = {PMLR}, year = {2025}, month = jul, url = {https://openreview.net/forum?id=99zsyZpUqp}, }