論文の概要: Federated Linear Bandits with Finite Adversarial Actions
- arxiv url: http://arxiv.org/abs/2311.00973v1
- Date: Thu, 2 Nov 2023 03:41:58 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-03 14:50:35.986906
- Title: Federated Linear Bandits with Finite Adversarial Actions
- Title（参考訳）: 有限な逆作用を持つフェデレート線形バンディット
- Authors: Li Fan, Ruida Zhou, Chao Tian, Cong Shen
- Abstract要約: 我々は、M$のクライアントが中央サーバと通信し、線形文脈の帯域幅問題を解決するための連合線形帯域幅モデルについて検討する。
逆有限作用集合のユニークな問題に対処するため、FedSupLinUCBアルゴリズムを提案する。
我々は、FedSupLinUCBが$tildeO(sqrtd T)$の完全後悔を達成したことを証明している。
- 参考スコア（独自算出の注目度）: 20.1041278044797
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a federated linear bandits model, where $M$ clients communicate with
a central server to solve a linear contextual bandits problem with finite
adversarial action sets that may be different across clients. To address the
unique challenges of adversarial finite action sets, we propose the
FedSupLinUCB algorithm, which extends the principles of SupLinUCB and OFUL
algorithms in linear contextual bandits. We prove that FedSupLinUCB achieves a
total regret of $\tilde{O}(\sqrt{d T})$, where $T$ is the total number of arm
pulls from all clients, and $d$ is the ambient dimension of the linear model.
This matches the minimax lower bound and thus is order-optimal (up to polylog
terms). We study both asynchronous and synchronous cases and show that the
communication cost can be controlled as $O(d M^2 \log(d)\log(T))$ and
$O(\sqrt{d^3 M^3} \log(d))$, respectively. The FedSupLinUCB design is further
extended to two scenarios: (1) variance-adaptive, where a total regret of
$\tilde{O} (\sqrt{d \sum \nolimits_{t=1}^{T} \sigma_t^2})$ can be achieved with
$\sigma_t^2$ being the noise variance of round $t$; and (2) adversarial
corruption, where a total regret of $\tilde{O}(\sqrt{dT} + d C_p)$ can be
achieved with $C_p$ being the total corruption budget. Experiment results
corroborate the theoretical analysis and demonstrate the effectiveness of
FedSupLinUCB on both synthetic and real-world datasets.
- Abstract（参考訳）: そこで我々は,$m$のクライアントが中央サーバと通信して,クライアント間で異なる可能性のある有限な逆作用セットを用いた線形文脈的バンディット問題を解決するフェデレーション線形バンディットモデルについて検討した。
逆有限作用集合の独特な挑戦に対処するために,線形文脈バンディットにおけるsuplinucbアルゴリズムとofulアルゴリズムの原理を拡張するfeedsuplinucbアルゴリズムを提案する。
我々は、FedSupLinUCBが$\tilde{O}(\sqrt{d T})$の完全後悔を達成することを証明し、$T$はすべてのクライアントからのアームプルの総数であり、$d$は線形モデルの周囲次元である。
これはミニマックス下限に一致し、従って順序最適化(ポリログ項まで)である。
非同期ケースと同期ケースの両方を調査し,通信コストをそれぞれ$o(d m^2 \log(d)\log(t))$と$o(\sqrt{d^3 m^3} \log(d))$で制御できることを示した。
fedsuplinucbの設計はさらに2つのシナリオに拡張されている: (1)$\tilde{o} (\sqrt{d \sum \nolimits_{t=1}^{t} \sigma_t^2})$の完全な後悔は、ラウンド$t$のノイズ分散である$\sigma_t^2$で達成できる。
実験結果は、理論解析とFedSupLinUCBの合成および実世界のデータセットに対する効果を裏付けるものである。
関連論文リスト
- Best-of-Both-Worlds Linear Contextual Bandits [45.378265414553226]
本研究は, 対向汚職下での多武装盗賊問題の事例である$K$腕線形文脈盗賊の問題を考察する。
我々は,理論的保証のもと,双方の敵環境に有効な戦略を開発する。
両体制の理論的保証から,我々の戦略をBest-of-Both-Worlds (BoBW) RealFTRLと呼んでいる。
論文 参考訳（メタデータ） (2023-12-27T09:32:18Z) - Corruption-Robust Offline Reinforcement Learning with General Function
Approximation [60.91257031278004]
一般関数近似を用いたオフライン強化学習(RL)における劣化問題について検討する。
我々のゴールは、崩壊しないマルコフ決定プロセス(MDP)の最適方針に関して、このような腐敗に対して堅牢で、最適でないギャップを最小限に抑える政策を見つけることである。
論文 参考訳（メタデータ） (2023-10-23T04:07:26Z) - Asymptotically Optimal Pure Exploration for Infinite-Armed Bandits [4.811176167998627]
我々は、未知の分布から生じる無限に多くのバンドイットアームを用いて純粋探索を研究する。
私たちのゴールは、平均的な報酬が1-delta$の1つの高品質なアームを、最高の$eta$-fraction of armsの1つとして$varepsilon$内で効率的に選択することにあります。
論文 参考訳（メタデータ） (2023-06-03T04:00:47Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [45.305256056479045]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - A Simple and Provably Efficient Algorithm for Asynchronous Federated
Contextual Linear Bandits [77.09836892653176]
我々は,M$エージェントが相互に協力して,中央サーバの助けを借りて,グローバルなコンテキスト線形バンドイット問題を解決するためのフェデレーション付きコンテキスト線形バンドイットについて検討した。
すべてのエージェントが独立して動作し、ひとつのエージェントとサーバ間の通信が他のエージェントの通信をトリガーしない非同期設定を考える。
texttFedLinUCBの後悔は$tildeO(dsqrtsum_m=1M T_m)$で、通信の複雑さは$tildeO(dM)であることを示す。
論文 参考訳（メタデータ） (2022-07-07T06:16:19Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。
逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
論文 参考訳（メタデータ） (2021-10-25T02:53:24Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z) - Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed
Payoffs [35.988644745703645]
我々は、リニアバンディットをヘビーテールのペイオフで分析し、そこではペイオフは1+epsilon$のモーメントしか持たない。
本稿では,$widetildeO(dfrac12Tfrac11+epsilon)$のサブ線形後悔境界を満足する2つの新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-04-28T13:01:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。