論文の概要: Optimal Cooperative Multiplayer Learning Bandits with Noisy Rewards and No Communication

• arxiv url: http://arxiv.org/abs/2311.06210v1
• Date: Fri, 10 Nov 2023 17:55:44 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-13 14:29:48.653872
• Title: Optimal Cooperative Multiplayer Learning Bandits with Noisy Rewards and No Communication
• Title（参考訳）: 雑音とコミュニケーションを伴わない最適協調型マルチプレイヤー学習バンド
• Authors: William Chang, Yuanhao Lu
• Abstract要約: 我々は,プレイヤーが事前に戦略に合意することのみを許される,協調的なマルチプレイヤーバンディット学習問題を考える。 この問題では、各プレイヤーが同時にアクションを選択する。 我々は,このアルゴリズムが対数的$O(fraclog TDelta_bma)$(gap依存)後悔および$O(sqrtTlog T)$(gap非依存)後悔を達成することを示す。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We consider a cooperative multiplayer bandit learning problem where the players are only allowed to agree on a strategy beforehand, but cannot communicate during the learning process. In this problem, each player simultaneously selects an action. Based on the actions selected by all players, the team of players receives a reward. The actions of all the players are commonly observed. However, each player receives a noisy version of the reward which cannot be shared with other players. Since players receive potentially different rewards, there is an asymmetry in the information used to select their actions. In this paper, we provide an algorithm based on upper and lower confidence bounds that the players can use to select their optimal actions despite the asymmetry in the reward information. We show that this algorithm can achieve logarithmic $O(\frac{\log T}{\Delta_{\bm{a}}})$ (gap-dependent) regret as well as $O(\sqrt{T\log T})$ (gap-independent) regret. This is asymptotically optimal in $T$. We also show that it performs empirically better than the current state of the art algorithm for this environment.
• Abstract（参考訳）: 我々は,プレイヤーが事前に戦略に合意できるだけでなく,学習プロセス中にコミュニケーションができないような,協調的なマルチプレイヤーバンディット学習問題を考える。 この問題では、各プレイヤーが同時にアクションを選択する。 すべてのプレイヤーが選択したアクションに基づいて、プレイヤーのチームは報酬を受け取る。 すべての選手の行動は一般に観察される。 しかし、各プレイヤーは、他のプレイヤーと共有できない報酬のノイズバージョンを受け取る。 プレイヤーは潜在的に異なる報酬を受けるため、アクションの選択に使用される情報には非対称性がある。 本稿では,報酬情報の非対称性に拘わらず,プレイヤーが最適な行動を選択するために使用できる,上下の信頼境界に基づくアルゴリズムを提案する。 このアルゴリズムが対数的に$o(\frac{\log t}{\delta_{\bm{a}}})$(gapに依存しない)後悔と$o(\sqrt{t\log t})$(gap非依存)後悔を実現できることを示す。 これは漸近的に$T$で最適である。 また,この環境におけるアートアルゴリズムの現況よりも経験的に優れていることを示す。

関連論文リスト

• Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities [69.34646544774161]
  我々は、各アームへのリクエストの到着とプレイヤーへのリクエストの割り当てポリシーをキャプチャするマルチプレイヤーマルチアーム・バンディット(MAB)モデルの新しいバリエーションを定式化する。 課題は、プレイヤーが最適な腕引きプロファイルに従って腕を選択するように分散学習アルゴリズムを設計する方法である。 我々は,Mラウンドのみの最適腕引きプロファイルにおいて,プレイヤーがコンセンサスに達することを保証した反復分散アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-08-20T13:57:00Z)
• Competing for Shareable Arms in Multi-Player Multi-Armed Bandits [29.08799537067425]
  本稿では,プレイヤーが自尊心を持ち,自己報酬を最大化することを目的とした,新しいマルチプレイヤーマルチアームバンディット(MPMAB)について検討する。 本稿では, 平均アロケーション (SMAA) を用いた新たな自己中心型MPMABを提案する。 我々は,一人の利己的なプレイヤーが,逸脱によって報酬を著しく増加させることはできず,また,他のプレイヤーの報酬に有害な影響も与えないことを確認した。
  論文  参考訳（メタデータ） (2023-05-30T15:59:56Z)
• 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)
• Can Reinforcement Learning Find Stackelberg-Nash Equilibria in General-Sum Markov Games with Myopic Followers? [156.5760265539888]
  我々は,マルチプレイヤーのジェネラルサムマルコフゲームについて,リーダーに指名されたプレイヤーとフォロワーに指名されたプレイヤーの1人を用いて研究した。 そのようなゲームに対して、我々のゴールは、政策対 $(pi*, nu*)$ であるスタックルバーグ・ナッシュ均衡 (SNE) を見つけることである。 オンラインとオフラインの両方でSNEを解くために,サンプル効率強化学習(RL)アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-12-27T05:41:14Z)
• Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback [29.553652241608997]
  本研究では,テキストモオと強いモノトーンゲームの研究を行い,その学習方法について検討した。 我々はまず,新しい帯域学習アルゴリズムを構築し,$tildeTheta(nsqrtT)$の単一エージェント最適後悔を実現することを示す。 そこで我々は,このオープンな問題を解決し,広範にわたるバンディットゲーム理論学習に寄与した。
  論文  参考訳（メタデータ） (2021-12-06T08:27:54Z)
• Online Learning for Cooperative Multi-Player Multi-Armed Bandits [7.527034429851578]
  複数の協力者によるマルチアームバンディット(MAB)のための分散オンライン学習フレームワークを提案する。 各ラウンドのプレイヤーが獲得した報酬は、すべてのプレイヤーが獲得した行動に依存する。 プレイヤーの行動が観察できない場合の行動情報非対称性と、他のプレイヤーの行動が観測可能であるが、受信された報酬が同一分布のIDである場合の報酬情報非対称性とを考察する。
  論文  参考訳（メタデータ） (2021-09-07T18:18:58Z)
• Bandit Learning in Decentralized Matching Markets [82.39061186055775]
  私たちは、一方の市場(プレーヤー)が他方の側(腕)の好みについて事前知識を持っていない両面マッチング市場を研究し、経験からその好みを学ぶ必要があります。 このモデルは、標準のマルチアームバンディットフレームワークを競合する分散型マルチプレイヤー設定に拡張します。 アームの選好が共有されるたびにアルゴリズムがインセンティブ互換であることが示されるが、選好が完全に一般的である場合には必ずしもそうではない。
  論文  参考訳（メタデータ） (2020-12-14T08:58:07Z)
• Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies in Extensive-Form Zero-Sum Games [123.76716667704625]
  我々は,不完全情報ゼロサム拡張形式ゲームにおいて,対戦相手と対決する2人の選手のチームにとって最適な戦略を見つけることの課題に焦点をあてる。 この設定では、チームができる最善のことは、ゲーム開始時の関節(つまり相関した)確率分布から潜在的にランダム化された戦略(プレイヤー1人)のプロファイルをサンプリングすることである。 各プロファイルにランダム化されるのはチームメンバーの1人だけであるプロファイルのみを用いることで、そのような最適な分布を計算するアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-09-21T17:51:57Z)
• Learning to Play Sequential Games versus Unknown Opponents [93.8672371143881]
  学習者が最初にプレーするゲームと、選択した行動に反応する相手との連続的なゲームについて考察する。 対戦相手の対戦相手列と対戦する際,学習者に対して新しいアルゴリズムを提案する。 我々の結果には、相手の反応の正則性に依存するアルゴリズムの後悔の保証が含まれている。
  論文  参考訳（メタデータ） (2020-07-10T09:33:05Z)
• Multiplayer Bandit Learning, from Competition to Cooperation [3.7801191959442053]
  コンペティションと協力が探究と搾取のトレードオフに与える影響について検討する。 このモデルは、通常プレイヤーが互いの報酬を観察する戦略実験に関する経済学文献と関連している。
  論文  参考訳（メタデータ） (2019-08-03T08:20:54Z)

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

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