Fugu-MT 論文翻訳(概要): Coordination without communication: optimal regret in two players multi-armed bandits

論文の概要: Coordination without communication: optimal regret in two players multi-armed bandits

arxiv url: http://arxiv.org/abs/2002.07596v2
Date: Thu, 9 Jul 2020 19:11:02 GMT
ステータス: 処理完了
システム内更新日: 2023-01-01 04:42:16.554293
Title: Coordination without communication: optimal regret in two players multi-armed bandits
Title（参考訳）: コミュニケーションのないコーディネーション:マルチアームバンディットにおける最適後悔
Authors: S\'ebastien Bubeck and Thomas Budzinski
Abstract要約: 同一の3本腕バンディットを同時に演奏するエージェントを2つ検討する。プレイヤー間の衝突が全くない戦略を提案する。また、この問題の完全な情報変種に対する下位境界を証明することによって、余剰対数項 $sqrtlog(T)$ は必要であると主張する。
参考スコア（独自算出の注目度）: 1.6752182911522522
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider two agents playing simultaneously the same stochastic three-armed bandit problem. The two agents are cooperating but they cannot communicate. We propose a strategy with no collisions at all between the players (with very high probability), and with near-optimal regret $O(\sqrt{T \log(T)})$. We also argue that the extra logarithmic term $\sqrt{\log(T)}$ should be necessary by proving a lower bound for a full information variant of the problem.
Abstract（参考訳）: 両エージェントは同じ確率的三本腕バンディット問題を同時に行う。 2人のエージェントは協力していますが、通信できません。我々は(非常に高い確率で)プレイヤー同士の衝突が全くない戦略を提案し、ほぼ最適の後悔である$o(\sqrt{t \log(t)})$ を提案する。また、この問題の完全な情報変種に対する下界を証明するためには、余分な対数項$\sqrt{\log(T)}$が必要であるとも主張する。

関連論文リスト

Imperfect-Recall Games: Equilibrium Concepts and Their Complexity [74.01381499760288]
エージェントが以前保持していた情報を忘れたとき、不完全なリコールの下で最適な意思決定を行う。不完全なリコールを伴う広範囲形式のゲームフレームワークにおいて、マルチプレイヤー設定における平衡を求める際の計算複雑性を解析する。
論文参考訳（メタデータ） (2024-06-23T00:27:28Z)
Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
論文参考訳（メタデータ） (2024-04-02T12:15:37Z)
Constant or logarithmic regret in asynchronous multiplayer bandits [22.376992460581594]
マルチプレイヤーのバンディット問題は、まず探索-then-commit (ETC)アルゴリズムで取り組んだ。最適ポリシーが各アームに少なくとも1人のプレイヤーを割り当てる場合、常にインスタンス依存の後悔をもたらすアルゴリズムであるCautious Greedyを導入する。
論文参考訳（メタデータ） (2023-05-31T09:35:03Z)
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)
The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player Multi-Armed Bandits with no Communication [10.446001329147112]
マルチプレイヤーのマルチアームバンディット問題について検討する。この問題では、$m$プレーヤーは、合計報酬を$K > m$アームから最大化するために協力する。ここで$Delta$は$m$-thと$m+1$-stのベストアームのギャップである。
論文参考訳（メタデータ） (2022-02-19T18:19:36Z)
Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
論文参考訳（メタデータ） (2022-02-03T18:18:28Z)
Distributed Bandits with Heterogeneous Agents [38.90376765616447]
本稿では、M$エージェントが協力して$K$武器の盗賊問題を解くマルチエージェントの盗賊設定に取り組む。本稿では,ucbo と AAE の2つの学習アルゴリズムを提案する。 Oleft(sum_i:tildeDelta_i>0 log T/tildeDelta_iright)$, $tildeDelta_i$は報酬平均の最小部分最適差である。
論文参考訳（メタデータ） (2022-01-23T20:04:15Z)
An Instance-Dependent Analysis for the Cooperative Multi-Player Multi-Armed Bandit [93.97385339354318]
マルチプレイヤーマルチアーマッドバンドにおける情報共有と協調の課題について検討する。まず, プレイヤーの最適度差を推定するために, 逐次的除去戦略への簡単な修正が可能であることを示す。第2に,第1の結果を利用して,衝突の小さな報奨をプレイヤー間の協調に役立てる通信プロトコルを設計する。
論文参考訳（メタデータ） (2021-11-08T23:38:47Z)
Bandit Learning in Decentralized Matching Markets [82.39061186055775]
私たちは、一方の市場(プレーヤー)が他方の側(腕)の好みについて事前知識を持っていない両面マッチング市場を研究し、経験からその好みを学ぶ必要があります。このモデルは、標準のマルチアームバンディットフレームワークを競合する分散型マルチプレイヤー設定に拡張します。アームの選好が共有されるたびにアルゴリズムがインセンティブ互換であることが示されるが、選好が完全に一般的である場合には必ずしもそうではない。
論文参考訳（メタデータ） (2020-12-14T08:58:07Z)
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)

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