Deceptive Exploration in Multi-armed Bandits
This addresses a novel deception scenario in sequential decision-making, with potential applications in security or adversarial settings, though it appears incremental as it builds on existing bandit frameworks.
The paper tackles the problem of a deceptive agent in multi-armed bandits aiming to identify the best private arm without detection by an observer, showing that deceptive pulls can occur at most at a Θ(√T) rate under a KL divergence constraint and characterizing the optimal error exponent.
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 $Θ(\sqrt{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 $Θ(\sqrt{T}) $ rate and the behavior of the proposed algorithm.