Secure Best Arm Identification in the Presence of a Copycat

Asaf Cohen 1, Onur Günlü 2 3 · 2025

Read Secure Best Arm Identification in the Presence of a Copycat by Asaf Cohen 1, Onur Günlü 2 3 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-18975.txt.

Introduction

Cohen and Gunlu study how to find the best choice by trial while a watcher tries to learn it too in twenty twenty-five. The setup is like testing many slot machines to find the one that pays most. A rival sees each test the player makes. If the player tests the best machine most, the rival can guess it at once.

Playing all machines in equal shares hides the best one but slows the search a lot. Their method mixes the tests into coded blends that hide the pattern. It needs no secret key or code locks. Yet it finds the best machine at near top speed while leaking almost no clue to the watcher.

Catalog record

CREATORAsaf Cohen 1, Onur Günlü 2 3
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-18975

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Secure Best Arm Identification in the Presence of a Copycat Asaf Cohen 1, Onur Günlü 2 3 Abstract Consider the problem of best arm identification with a security constraint. Specifically, assume a setup of stochastic linear bandits with K K arms of dimension d d . In each arm pull, the player receives a reward that is the sum of the dot product of the arm with an unknown parameter vector and independent noise. The player’s goal is to identify the best arm after T T arm pulls. Moreover, assume a copycat Chloe is observing the arm pulls. The player wishes to keep Chloe ignorant of the best arm. While a minimax–optimal algorithm identifies the best arm with an Ω ⁡ ( T log ⁡ ( d ) ) \Omega\left(\frac{T}{\log(d)}\right) error exponent, it easily reveals its best-arm estimate to an outside observer, as the best arms are played more frequently. A naive secure algorithm that plays all arms equally results in an Ω ⁡ ( T d ) \Omega\left(\frac{T}{d}\right) exponent. In this paper, we propose a secure algorithm that plays with coded arms . The algorithm does not require any key or cryptographic primitives, yet achieves an Ω ⁡ ( T log 2 ⁡ ( d ) ) \Omega\left(\frac{T}{\log^{2}(d)}\right) exponent while revealing almost no information on the best arm. I Introduction Reinforcement learning is a framework that involves a user interacting with an unknown environment. During this interaction, the user takes actions and receives rewards based on those actions. The primary objective is to learn the optimal actions that maximize overall rewards. Multi-Armed Bandit (MAB) problems represent a specific case within this framework, where the user is faced with a selection of arms to pull. Each arm is associated with its own unique reward (or reward distribution), and the challenge is to pull the arms sequentially to maximize the cumulative rewards. MAB problems have diverse applications across various fields, including clinical trials [ 1 ] , finance (such as portfolio selection [ 2 ] and dynamic pricing [ 3 ] ), recommendation systems [ 4 ] , influence maximization in social networks [ 5 ] , and even routing [ 6 ] . Best arm identification is a specific problem in which the player does not accumulate rewards. Instead, the player has the opportunity to pull T arms before making a decision regarding the best arm. Performance is evaluated based on the error probability in identifying the best arm. To illustrate a specific application, consider dynamic pricing . A seller preparing to launch a new product must assess its acceptance based on several characteristics. However, the seller is uncertain about the degree to which consumers value each characteristic. To address this, the seller tests a few initial product variations, each with different attribute values or weights influencing the overall appearance of the product. After experimenting with these initial variations, the seller must ultimately decide which combination of attribute weights yields the highest reward. The aforementioned application raises a critical concern: an outside observer can see the initial product variations, and as the seller refines their tests, the observer can infer the market demand as well. An astute seller would want to conduct initial product tests and refine them to gain a better understanding of market demand, while minimizing the amount of information revealed to competing sellers. This raises the problem of secure best arm identification . I-A Main Contributions In this work, we focus on best arm identification in the linear–stochastic setting, were there are K arms of dimension d . We present a novel model, with a novel solution, in which a secure algorithm effectively balances the need for accurate identification of the best arm while minimizing the information disclosed to external observers. The state–of–the–art best arm identification algorithm in [ 7 ] , proposing a minimax-optimal algorithm, achieves an error exponent of \Omega\left(\frac{T}{\log(d)}\right) but does so by exposing its best arm estimates, making them vulnerable to competitive analysis. Conversely, a naive secure approach that plays all arms equally results in a significantly worse error exponent of \Omega\left(\frac{T}{d}\right) . Note that contemporary learning applications consider datasets where the dimension is of the same order as the number of samples (arm pulls), hence \Omega\left(\frac{T}{d}\right) may reflect poor performance. Our proposed algorithm achieves an error exponent of \Omega\left(\frac{T}{\log^{2}(d)}\right) without relying on cryptographic keys or complex primitives. By employing a coding strategy , the algorithm allows efficient exploration of arm variations while hiding valuable information about the best arm from competitors. In fact, the best arm declared by the algorithm is among \frac{d}{2} of the arms it uses with the same frequency, resulting in \log(d)-1 bits of information missing for an outside observer. We argue that \log(d) is the optimal equivocation, as the critical parameter for the estimation is d rather than K . Revisiting the dynamic pricing example as a test case, we allow the seller to introduce “coded products”. In this approach, the seller can manipulate the weights assigned to each characteristic in a way that does not necessarily reflect their best current estimate. However, through this method, the seller is able to infer the optimal weights, possibly by intelligently analyzing the rewards received from multiple previous initial product variations. The coded products thus help the seller gain information, yet they mix initial products such that an outside observer cannot understand which initial products are suspected to be more successful by the seller. Such a compromise between exploration and information security can mark a significant advancement in adaptive decision–making frameworks, yielding a practical tool for sellers and decision-makers in environments where confidentiality is paramount. I-B Related Work A model of particular interest to this work is that of linear stochastic bandits [ 8 ] , and especially [ 7 ] , focusing on minimax optimal fixed-budget best arm identification. [ 9 ] introduces an additional constraint of minimal regret. Notably, the lower bound established in [ 7 ] builds upon the non–linear, more general problem addressed in [ 10 ] , which is integral to understanding the limits of current approaches. The exploration of constrained stochastic bandit problems, such as those discussed in [ 11 ] , is relevant even though they do not directly address security considerations. For instance, [ 12 ] examines best arm identification under communication constraints, establishing key connections between communication and decision–making. Moreover, [ 13 ] portrays a network of clients sharing a common set of arms, communicating with a central server over cost–incurring links, allowing the server to estimate the global best arm. The integration of meta–learning and emerging concepts, such as learning–to–learn, has begun to shape the MAB literature, as illustrated by [ 14 ] . In terms of secure versions of the problem, there are a few recent works. Specifically, [ 15 ] considers private stochastic MAB, but the focus is on protecting the privacy of the data returned from the bandits, i.e., rewards are protected rather than the information gained by the learner. Note that even if rewards are protected or completely unobserved, the learner itself is not necessarily safeguarded. The actions taken by the learner during interactions with the environment can potentially disclose its inferred model. In the same context,

Read the complete text