Secure Best Arm Identification in the Presence of a Copycat
Consider the problem of best arm identification with a security constraint. Specifically, assume a setup of stochastic linear bandits with $K$ arms of dimension $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$ 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 $Ω\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 $Ω\left(\frac{T}{d}\right)$ exponent. In this paper, we propose a secure algorithm that plays with \emph{coded arms}. The algorithm does not require any key or cryptographic primitives, yet achieves an $Ω\left(\frac{T}{\log^2(d)}\right)$ exponent while revealing almost no information on the best arm.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Copycat CNN: Stealing Knowledge by Persuading Confession with Random Non-Labeled Data
In the past few years, Convolutional Neural Networks (CNNs) have been achieving state-of-the-art performance on a variety of problems. Many companies employ resources and money to generate these models and provide them a…
Reimplementation and Reinterpretation of the Copycat Project
We present the reinterpreted and reimplemented Copycat project, an architecture solving letter analogy domain problems. To support a flexible implementation change and rigor testing process, we propose a implementation m…
Copycat CNN: Are Random Non-Labeled Data Enough to Steal Knowledge from Black-box Models?
Convolutional neural networks have been successful lately enabling companies to develop neural-based products, which demand an expensive process, involving data acquisition and annotation; and model generation, usually r…
Copycat vs. Original: Multi-modal Pretraining and Variable Importance in Box-office Prediction
The movie industry is associated with an elevated level of risk, which necessitates the use of automated tools to predict box-office revenue and facilitate human decision-making. In this study, we build a sophisticated m…
Analogy-Making as a Core Primitive in the Software Engineering Toolbox
An analogy is an identification of structural similarities and correspondences between two objects. Computational models of analogy making have been studied extensively in the field of cognitive science to better underst…