論文の概要: Decentralized Online Bandit Optimization on Directed Graphs with Regret Bounds

• arxiv url: http://arxiv.org/abs/2301.11802v1
• Date: Fri, 27 Jan 2023 15:58:04 GMT
• ステータス: 処理完了
• システム内更新日: 2023-01-30 15:00:20.057617
• Title: Decentralized Online Bandit Optimization on Directed Graphs with Regret Bounds
• Title（参考訳）: レグレット境界付きダイレクトグラフによる分散オンライン帯域最適化
• Authors: Johan \"Ostman and Ather Gattami and Daniel Gillblad
• Abstract要約: 我々は、分散化されたマルチプレイヤーゲームが$T$ラウンドでプレイされると考えている。 各ラウンドの終了までに、全てのプレイヤーは、それぞれの共同アクションに基づいて、ジョイント・バンディット・リワードを受け取る。 シングルプレイヤーのマルチアームバンディット問題にインスパイアされた学習アルゴリズムは,ラウンド数においてサブ線形の擬似回帰を実現する。
• 参考スコア（独自算出の注目度）: 4.640835690336653
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider a decentralized multiplayer game, played over $T$ rounds, with a leader-follower hierarchy described by a directed acyclic graph. For each round, the graph structure dictates the order of the players and how players observe the actions of one another. By the end of each round, all players receive a joint bandit-reward based on their joint action that is used to update the player strategies towards the goal of minimizing the joint pseudo-regret. We present a learning algorithm inspired by the single-player multi-armed bandit problem and show that it achieves sub-linear joint pseudo-regret in the number of rounds for both adversarial and stochastic bandit rewards. Furthermore, we quantify the cost incurred due to the decentralized nature of our problem compared to the centralized setting.
• Abstract（参考訳）: 分散マルチプレイヤーゲームは$t$のラウンドでプレイされ、リーダー・フォローの階層構造は有向非循環グラフによって記述される。 各ラウンドにおいて、グラフ構造はプレイヤーの順番と、プレイヤーが互いのアクションをどのように観察するかを規定する。 各ラウンドの終了までに、全てのプレイヤーは、ジョイントアクションに基づいてジョイント・バンディット・リワードを受け取り、ジョイント・サブレグレットの最小化という目標に向けてプレイヤー戦略を更新するために使用される。 本稿では,単手マルチアームバンディット問題に触発された学習アルゴリズムを提案し,逆および確率バンディット報酬のラウンド数において,サブリニアジョイント擬似レグレットを実現することを示す。 さらに,中央集権的な設定と比較して,問題の分散性に起因するコストを定量化する。

関連論文リスト

• Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities [69.34646544774161]
  我々は、各アームへのリクエストの到着とプレイヤーへのリクエストの割り当てポリシーをキャプチャするマルチプレイヤーマルチアーム・バンディット(MAB)モデルの新しいバリエーションを定式化する。 課題は、プレイヤーが最適な腕引きプロファイルに従って腕を選択するように分散学習アルゴリズムを設計する方法である。 我々は,Mラウンドのみの最適腕引きプロファイルにおいて,プレイヤーがコンセンサスに達することを保証した反復分散アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-08-20T13:57:00Z)
• Multi-Player Approaches for Dueling Bandits [58.442742345319225]
  Follow Your Leaderのブラックボックスアプローチの直接的な使用は、この設定の低いバウンダリと一致することを示す。 また,Condorcet-Winnerレコメンデーションプロトコルを用いて,メッセージパッシングによる完全分散アプローチも分析する。
  論文  参考訳（メタデータ） (2024-05-25T10:25:48Z)
• Finding mixed-strategy equilibria of continuous-action games without gradients using randomized policy networks [83.28949556413717]
  グラデーションへのアクセスを伴わない連続アクションゲームのナッシュ平衡を近似的に計算する問題について検討する。 ニューラルネットワークを用いてプレイヤーの戦略をモデル化する。 本論文は、制約のない混合戦略と勾配情報のない一般的な連続アクションゲームを解決する最初の方法である。
  論文  参考訳（メタデータ） (2022-11-29T05:16:41Z)
• Collaborative Multi-agent Stochastic Linear Bandits [28.268809091816287]
  我々は,ネットワークを構成するN$エージェントが局所的に通信し,全体的な後悔を最小限に抑える,協調的マルチエージェント線形帯域設定について検討する。 すべてのエージェントは、プレイされたアクションの対応する報酬を観察し、加速されたコンセンサス手順を使用して、すべてのエージェントが取得した報酬の平均の見積もりを計算する。
  論文  参考訳（メタデータ） (2022-05-12T19:46:35Z)
• 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)
• Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit Feedback [51.21673420940346]
  コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。 我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。 有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
  論文  参考訳（メタデータ） (2021-01-21T10:35:09Z)
• Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisions [4.974932889340056]
  我々は、多腕バンディット問題の協調型マルチプレイヤー版を考える。 これらの特性は,任意の数の選手や腕に対して達成可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-08T03:14:19Z)
• Multitask Bandit Learning Through Heterogeneous Feedback Aggregation [35.923544685900055]
  我々は,この問題を,一組のプレイヤーが一組のアームと同時に相互作用する,$epsilon$-multi-player multi-armed bandit問題として定式化する。 我々は、異なるプレイヤーが収集した報酬を適応的に集約する高信頼な有界アルゴリズム、RobostAgg$(epsilon)$を開発する。
  論文  参考訳（メタデータ） (2020-10-29T07:13:28Z)
• Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
  学習者が最初にプレーするゲームと、選択した行動に反応する相手との連続的なゲームについて考察する。 対戦相手の対戦相手列と対戦する際,学習者に対して新しいアルゴリズムを提案する。 我々の結果には、相手の反応の正則性に依存するアルゴリズムの後悔の保証が含まれている。
  論文  参考訳（メタデータ） (2020-07-10T09:33:05Z)
• Selfish Robustness and Equilibria in Multi-Player Bandits [25.67398941667429]
  ゲームでは、複数のプレイヤーが同時に腕を引いて、同じ腕を同時に引っ張る場合、0の報酬で衝突する。 プレイヤーが集団報酬を最大化する協力的ケースは、主に考慮されてきたが、悪意のあるプレイヤーにとっては非常に重要かつ困難な問題である。 代わりに、社会的福祉を犠牲にして、個人の報酬を最大化するインセンティブを持つより自然な利己的なプレイヤーについて検討する。
  論文  参考訳（メタデータ） (2020-02-04T09:50:28Z)

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

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