論文の概要: Differential Privacy in the Extensive-Form Bandit Problem

• arxiv url: http://arxiv.org/abs/2605.05266v1
• Date: Wed, 06 May 2026 09:19:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-08 22:27:11.326017
• Title: Differential Privacy in the Extensive-Form Bandit Problem
• Title（参考訳）: 広帯域問題における差分プライバシー
• Abstract要約: 広義のバンディット問題について考察し、各トライアルにおいて、学習者が難解な相手に対して広義のゲームをする。 局所微分プライバシーを$$で満たし、$tildeO(sqrtAln(S)T/)$を後悔する問題に対するアルゴリズムを提供する。 各試行において、我々のアルゴリズムの複雑さの時間は、インフォセットにおけるアクションの最大回数において最大対数であり、その削減戦略をユーザに伝達するために必要な時間に等しい。
• 参考スコア（独自算出の注目度）: 6.572714770742585
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the extensive-form bandit problem, where on each trial the learner (a user coordinated by a server) plays an extensive-form game against an oblivious adversary, observing the information sets it finds itself in as well as the resulting payoff/loss. We give an algorithm for this problem that satisfies $ε$-local differential privacy and attains a regret of $\tilde{O}(\sqrt{A\ln(S)T}/ε)$, where $A$ is the total number of actions that the learner can possibly take, $S$ is the number of the learner's possible reduced strategies, and $T$ is the number of trials. On each trial, the time complexity of our algorithm is, up to a factor logarithmic in the maximum number of actions at an infoset, equal to the time required for the server to transmit the reduced strategy to the user. We note that local differential privacy is the strongest version of differential privacy and, to the best of our knowledge, this is the first work to study differential privacy of any form in the extensive-form bandit problem.
• Abstract（参考訳）: 本稿では,学習者(サーバによって調整されたユーザ)が,不愉快な相手に対して広義のゲームを行う場合の広義の盗賊問題について考察する。 本稿では, 局所微分プライバシーが$ε$を満足し, $\tilde{O}(\sqrt{A\ln(S)T}/ε)$を後悔するアルゴリズムを提案する。 各試行において、我々のアルゴリズムの時間複雑性は、インフォセットにおけるアクションの最大回数において最大対数であり、その削減戦略をユーザに伝達するために必要な時間に等しい。 ローカルな差分プライバシーは、微分プライバシーの最も強力なバージョンであり、私たちの知る限りでは、広義のバンディット問題におけるあらゆる形式の差分プライバシーを研究する最初の研究である。

関連論文リスト

• Tracking the Best Strategy in an Extensive-Form Game [6.572714770742585]
  本稿では, 学習者の期待性能を, 振り返りにおける混合戦略のスイッチングシーケンスに対して測定する, 後悔の切り替えという概念に焦点をあてる。 我々のアルゴリズムは非常に効率的で、トライアル時間は$mathcalO(HB)$で、そこでは$B$は学習者が任意の情報集合で利用できる最大アクション数である。
  論文  参考訳（メタデータ） (2026-08-10T12:05:54Z)
• Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms [67.94856074923571]
  本稿では,マルチプレイヤー通信ゲームに基づく新しい証明手法を提案する。 本稿では,このコミュニケーションゲームに勝つためには,過剰なユーザ数に比例した情報伝達が必要であることを示す。 このコミュニケーション理論の手法は幅広い問題のクラスに一般化し、プライベートな中央値、量子化値、最大選択値の下位境界を導出することを示す。
  論文  参考訳（メタデータ） (2026-02-12T17:49:07Z)
• Nearly-Optimal Bandit Learning in Stackelberg Games with Side Information [57.287431079644705]
  そこで我々は,Stackelbergゲームにおけるオンライン学習の問題について,リーダーとフォロワーの列の側情報を用いて検討した。 我々は,リーダに対する学習アルゴリズムを提供し,盗聴フィードバックの下でO(T1/2)$後悔を達成する。
  論文  参考訳（メタデータ） (2025-01-31T22:40:57Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Differentially Private Secure Multiplication: Hiding Information in the Rubble of Noise [7.110450972801578]
  プライベート分散マルチパーティ乗算の問題点を考察する。 Shamirの秘密共有コーディング戦略が、分散計算における完全な情報理論プライバシを実現することは、十分に確立されている。
  論文  参考訳（メタデータ） (2023-09-28T02:13:13Z)
• Robust and differentially private stochastic linear bandits [23.96322363134793]
  差分プライバシー,ロバスト性,バッチ化観測などの追加要件の下で線形帯域問題について検討する。 対数バッチクエリを用いたアーム除去アルゴリズムの差分プライベートおよびロバストな変形について述べる。
  論文  参考訳（メタデータ） (2023-04-23T20:17:03Z)
• Near-Optimal Differentially Private Reinforcement Learning [16.871660060209674]
  差分プライバシー制約による強化学習におけるオンライン探索について検討する。 共同微分プライバシ(JDP)と局所微分プライバシ(LDP)の下では、非回帰学習が可能であることが確立されている。 我々は、情報理論上の非私的学習の下位境界に一致する$widetildeO(sqrtSAH2T+S2AH3/epsilon)$を後悔する$epsilon$-JDPアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2022-12-09T06:03:02Z)
• Private Online Prediction from Experts: Separations and Faster Rates [74.52487417350221]
  専門家によるオンライン予測は機械学習の基本的な問題であり、いくつかの研究がプライバシーの制約の下でこの問題を研究している。 本研究では,非適応的敵に対する最良な既存アルゴリズムの残差を克服する新たなアルゴリズムを提案し,解析する。
  論文  参考訳（メタデータ） (2022-10-24T18:40:19Z)
• Quantifying identifiability to choose and audit $\epsilon$ in differentially private deep learning [15.294433619347082]
  機械学習で差分プライバシーを使用するには、データサイエンティストがプライバシパラメータを$(epsilon,delta)$を選択する必要がある。 私たちは$(epsilon,delta)$を、トレーニングデータセット内のレコードの存在に関する差分プライバシーによって想定される相手のベイジアン後方信念にバインドに変換します。 我々は、データサイエンティストがモデルのトレーニングを監査し、経験的識別可能性スコアと経験的$(epsilon,delta)$を計算することを可能にするこの差分プライバシーの敵対の実装を策定します。
  論文  参考訳（メタデータ） (2021-03-04T09:35:58Z)
• Learning with User-Level Privacy [61.62978104304273]
  ユーザレベルの差分プライバシー制約下での学習課題を,アルゴリズムを用いて解析する。 個々のサンプルのプライバシーのみを保証するのではなく、ユーザレベルのdpはユーザの貢献全体を保護します。 プライバシコストが$tau$に比例した$K$適応的に選択されたクエリのシーケンスにプライベートに答えるアルゴリズムを導き出し、私たちが検討する学習タスクを解決するためにそれを適用します。
  論文  参考訳（メタデータ） (2021-02-23T18:25:13Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。 各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。 我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
  論文  参考訳（メタデータ） (2021-01-31T16:49:07Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。