論文の概要: Secure Best Arm Identification in the Presence of a Copycat
- arxiv url: http://arxiv.org/abs/2507.18975v2
- Date: Mon, 28 Jul 2025 08:28:48 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-07-29 14:15:47.138249
- Title: Secure Best Arm Identification in the Presence of a Copycat
- Title（参考訳）: コピーキャット存在下での安全なベストアーム識別
- Authors: Asaf Cohen, Onur Günlü,
- Abstract要約: 本稿では,エンコードアームを用いたセキュアなアルゴリズムを提案する。
このアルゴリズムは鍵や暗号のプリミティブを一切必要としないが、最高の腕に関する情報をほとんど示さずに$Omegaleft(fracTlog2(d)right)$ exponentを達成する。
- 参考スコア（独自算出の注目度）: 23.13665306465456
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: 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 $\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 $\Omega\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 $\Omega\left(\frac{T}{\log^2(d)}\right)$ exponent while revealing almost no information on the best arm.
- Abstract（参考訳）: セキュリティ制約のあるベストアーム識別の問題を考える。
具体的には、次元$d$の腕を持つ確率線型包帯の集合を仮定する。
各アームプルにおいて、プレイヤーは未知のパラメータベクトルと独立ノイズを持つアームのドット積の和である報酬を受け取る。
プレイヤーのゴールは、T$腕を引いた後に最適な腕を特定することである。
さらに、クロエが腕の引っ張りを観察しているコピーキャットを仮定する。
プレイヤーはクロエが最高の腕を知らないことを望んでいます。
ミニマックス最適化アルゴリズムは、$\Omega\left(\frac{T}{\log(d)}\right)$ error exponentでベストアームを識別するが、ベストアームがより頻繁に演奏されるため、そのベストアーム推定を外部観測者に容易に明らかにする。
すべての腕を均等に演奏する単純でセキュアなアルゴリズムは、$\Omega\left(\frac{T}{d}\right)$ exponentとなる。
本稿では, \emph{coded arms} を用いたセキュアなアルゴリズムを提案する。
このアルゴリズムは鍵や暗号のプリミティブを一切必要としないが、最高のアームに関する情報をほとんど示さずに$\Omega\left(\frac{T}{\log^2(d)}\right)$ exponentを達成する。
関連論文リスト
- Multi-thresholding Good Arm Identification with Bandit Feedback [1.079960007119637]
我々は,多目的のバンドイット設定において,良好な腕識別問題を考える。
サンプル複雑性境界を持つマルチスレッド UCB (MultiTUCB) アルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-03-13T14:04:04Z) - A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
我々の洗練された分析により、アルゴリズムの平均的なアームプル数が、$delta$が消えるにつれて、基本的限界に収束する速度に縛られる新しい現象が明らかになった。
論文 参考訳（メタデータ） (2024-09-08T12:19:12Z) - Almost Cost-Free Communication in Federated Best Arm Identification [76.12303738941254]
中央サーバと複数のクライアントを備えた多腕バンディット構成の連合学習における最適なアーム識別の問題について検討する。
逐次除去に基づく指数時間ステップでのみ通信を行う新しいアルゴリズム sc FedElim を提案する。
論文 参考訳（メタデータ） (2022-08-19T08:37:09Z) - Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
マルチアームバンディット環境における最適な腕を特定することの問題点について検討する。
決定エンティティは、上限誤差確率を条件として、ベストアームのインデックスをできるだけ早く見つけることを希望する。
このポリシーは、$R$に依存する上限を達成し、$Rtoinfty$として単調に増加しないことを示す。
論文 参考訳（メタデータ） (2022-03-29T04:58:04Z) - Best-Arm Identification in Correlated Multi-Armed Bandits [9.180690233707645]
本稿では,武器間の相関に関するドメイン知識を捉えた新しい相関バンディットフレームワークを提案する。
C-LUCBで得られた全サンプルは$mathcalOleft(sum_k in MathcalC logleft(frac1deltaright)$であり、通常の$mathcalOleft(sum_k in MathcalC logleft(frac1deltaright)$とは対照的である。
論文 参考訳（メタデータ） (2021-09-10T15:41:07Z) - Variance-Dependent Best Arm Identification [12.058652922228918]
マルチアームバンディットゲームにおける最適な腕を特定する問題について検討する。
武器の報酬のギャップと分散を探索する適応アルゴリズムを提案する。
このアルゴリズムは2つの対数項に最適であることを示す。
論文 参考訳（メタデータ） (2021-06-19T04:13:54Z) - Combinatorial Bandits without Total Order for Arms [52.93972547896022]
セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。
我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
論文 参考訳（メタデータ） (2021-03-03T23:08:59Z) - Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy [71.17938026619068]
我々は、腕の総数が膨大であることができるトップ$ k$極端な文脈的包帯問題を研究します。
まず,Inverse Gap Weighting戦略を用いて,非極端に実現可能な設定のアルゴリズムを提案する。
我々のアルゴリズムは、$O(ksqrt(A-k+1)T log (|mathcalF|T))$である。
論文 参考訳（メタデータ） (2021-02-15T19:10:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。