# Deceptive Exploration in Multi-armed Bandits

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 26 references that are in the map.
- First posted on arXiv 9 Oct 2025.

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

- [Optimal Best Arm Identification with Fixed Confidence](https://mlsanity.com/paper/1602.04589/) (2016)
- [Simple Bayesian Algorithms for Best Arm Identification](https://mlsanity.com/paper/1602.08448/) (2016)
- [Improving the Expected Improvement Algorithm](https://mlsanity.com/paper/1705.10033/) (2017)
- [Algorithms for Differentially Private Multi-Armed Bandits](https://mlsanity.com/paper/1511.08681/) (2015)
- [Fixed-Confidence Guarantees for Bayesian Best-Arm Identification](https://mlsanity.com/paper/1910.10945/) (2019)
- [Best Arm Identification with Safety Constraints](https://mlsanity.com/paper/2111.12151/) (2021)
- [Information-Directed Selection for Top-Two Algorithms](https://mlsanity.com/paper/2205.12086/) (2022)
- [Cost Aware Best Arm Identification](https://mlsanity.com/paper/2402.16710/) (2024)
- [Optimizing Adaptive Experiments: A Unified Approach to Regret Minimization and Best-Arm Identification](https://mlsanity.com/paper/2402.10592/) (2024)
- [Deceptive Reinforcement Learning in Model-Free Domains](https://mlsanity.com/paper/2303.10838/) (2023)
- [Differentially Private Best-Arm Identification](https://mlsanity.com/paper/2406.06408/) (2024)
- [Data-Injection Attacks in Stochastic Control Systems: Detectability and Performance Tradeoffs](https://mlsanity.com/paper/1704.00748/) (2017)
- [Best Arm Identification with Resource Constraints](https://mlsanity.com/paper/2402.19090/) (2024)
- [Identity Concealment Games: How I Learned to Stop Revealing and Love the Coincidences](https://mlsanity.com/paper/2105.05377/) (2021)
- [Balancing Performance and Costs in Best Arm Identification](https://mlsanity.com/paper/2505.20583/) (2025)

## Built on by (most cited first, 1 of 1)

- [Generalized Information Gathering Under Dynamics Uncertainty](https://mlsanity.com/paper/2601.21988/) (2026)

## Abstract (arXiv)

We consider a multi-armed bandit setting in which each arm has a public and a private reward distribution. An observer expects an agent to follow Thompson Sampling according to the public rewards, however, the deceptive agent aims to quickly identify the best private arm without being noticed. The observer can observe the public rewards and the pulled arms, but not the private rewards. The agent, on the other hand, observes both the public and private rewards. We formalize detectability as a stepwise Kullback-Leibler (KL) divergence constraint between the actual pull probabilities used by the agent and the anticipated pull probabilities by the observer. We model successful pulling of public suboptimal arms as a % Bernoulli process where the success probability decreases with each successful pull, and show these pulls can happen at most at a Theta(√T)  rate under the KL constraint. We then formulate a maximin problem based on public and private means, whose solution characterizes the optimal error exponent for best private arm identification. We finally propose an algorithm inspired by top-two algorithms. This algorithm naturally adapts its exploration according to the hardness of pulling arms based on the public suboptimality gaps. We provide numerical examples illustrating the Theta(√T)  rate and the behavior of the proposed algorithm.