論文の概要: An Efficient Algorithm for Cooperative Semi-Bandits

• arxiv url: http://arxiv.org/abs/2010.01818v2
• Date: Tue, 9 Feb 2021 08:55:30 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-10 20:39:13.392545
• Title: An Efficient Algorithm for Cooperative Semi-Bandits
• Title（参考訳）: 協調半帯域の効率的なアルゴリズム
• Authors: Riccardo Della Vecchia (BIDSA), Tommaso Cesari (TSE)
• Abstract要約: 本稿では,有名なFollow The Perturbed Leaderアルゴリズムの協調バージョンであるCoop-FTPLを紹介する。 T 時間ステップ後のアルゴリズムの期待された後悔は QT log(k)(k$alpha$ 1 /Q + m) であり、Q は総アクティベーション確率質量である。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of asynchronous online combinatorial optimization on a network of communicating agents. At each time step, some of the agents are stochastically activated, requested to make a prediction, and the system pays the corresponding loss. Then, neighbors of active agents receive semi-bandit feedback and exchange some succinct local information. The goal is to minimize the network regret, defined as the difference between the cumulative loss of the predictions of active agents and that of the best action in hindsight, selected from a combinatorial decision set. The main challenge in such a context is to control the computational complexity of the resulting algorithm while retaining minimax optimal regret guarantees. We introduce Coop-FTPL, a cooperative version of the well-known Follow The Perturbed Leader algorithm, that implements a new loss estimation procedure generalizing the Geometric Resampling of Neu and Bart{\'o}k [2013] to our setting. Assuming that the elements of the decision set are k-dimensional binary vectors with at most m non-zero entries and $\alpha$ 1 is the independence number of the network, we show that the expected regret of our algorithm after T time steps is of order Q mkT log(k)(k$\alpha$ 1 /Q + m), where Q is the total activation probability mass. Furthermore, we prove that this is only $\sqrt$ k log k-away from the best achievable rate and that Coop-FTPL has a state-of-the-art T 3/2 worst-case computational complexity.
• Abstract（参考訳）: 通信エージェントのネットワーク上での非同期オンライン組合せ最適化の問題を考える。 各段階において、エージェントのいくつかは確率的に活性化され、予測を要求され、システムは対応する損失を支払う。 次に、アクティブエージェントの隣人が半帯域フィードバックを受け取り、簡潔なローカル情報を交換する。 目的は、アクティブエージェントの予測の累積損失と、組合せ決定セットから選択された後見における最良のアクションとの差として定義されるネットワークの後悔を最小限にすることである。 このような文脈における主な課題は、最小限の後悔の保証を維持しながら、結果のアルゴリズムの計算複雑性を制御することである。 我々は,よく知られたFollow The Perturbed Leaderアルゴリズムの協調バージョンであるCoop-FTPLを紹介し,Neu と Bart{\'o}k [2013] の幾何学的サンプリングを一般化した新たな損失推定手順を実装した。 決定集合の要素が最大 m 個の非零エントリを持つ k-次元二進ベクトルであり、$\alpha$ 1 がネットワークの独立数であると仮定すると、t 時間ステップ後のアルゴリズムの期待される後悔は q mkt log(k)(k$\alpha$ 1 /q + m) の順であることを示し、q は全活性化確率質量である。 さらに、これは最高の達成可能なレートからたったの$\sqrt$ k log k-awayであり、Coop-FTPLは最先端のT 3/2最悪の計算量であることを示す。

関連論文リスト

• Decentralized Multi-Task Online Convex Optimization Under Random Link Failures [5.513958040574729]
  我々は不均一な確率を持つランダムリンク障害に対する頑健な分散型サドルポイントアルゴリズムを開発した。 我々はアルゴリズムと分析を2点の帯域フィードバックシナリオに拡張する。
  論文  参考訳（メタデータ） (2024-01-04T00:57:33Z)
• Cooperative Thresholded Lasso for Sparse Linear Bandit [6.52540785559241]
  本稿では,マルチエージェント・スパース文脈線形帯域問題に対処する新しい手法を提案する。 疎線形帯域における行単位の分散データに対処する最初のアルゴリズムである。 後悔を最小限に抑えるために効率的な特徴抽出が重要となる高次元マルチエージェント問題に適用可能である。
  論文  参考訳（メタデータ） (2023-05-30T16:05:44Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  マルコフ決定過程における純粋探索問題について検討する。 エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
  論文  参考訳（メタデータ） (2021-06-05T09:16:28Z)
• Improved Branch and Bound for Neural Network Verification via Lagrangian Decomposition [161.09660864941603]
  ニューラルネットワークの入出力特性を公式に証明するためのブランチとバウンド(BaB)アルゴリズムのスケーラビリティを改善します。 活性化に基づく新しい分岐戦略とBaBフレームワークであるブランチとデュアルネットワーク境界(BaDNB)を提案する。 BaDNBは、従来の完全検証システムを大きなマージンで上回り、対数特性で平均検証時間を最大50倍に削減した。
  論文  参考訳（メタデータ） (2021-04-14T09:22:42Z)
• Decentralized Multi-Agent Linear Bandits with Safety Constraints [31.67685495996986]
  本研究では,N$エージェントのネットワークが協調して線形帯域最適化問題を解く分散線形帯域幅について検討する。 ネットワーク全体の累積的後悔を最小限に抑える完全分散アルゴリズム DLUCB を提案する。 私たちのアイデアは、より困難な、安全な盗賊の設定にもかかわらず、自然界に広まっています。
  論文  参考訳（メタデータ） (2020-12-01T07:33:00Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

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

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