論文の概要: Square-Root Regret for Adversarial Multiplayer Bandits without Collision Information or Shared Randomness
- arxiv url: http://arxiv.org/abs/2610.05688v1
- Date: Mon, 05 Oct 2026 02:03:44 GMT
- ステータス: 情報取得中
- システム内更新日: 2026-10-06 21:36:36.467162
- Title: Square-Root Regret for Adversarial Multiplayer Bandits without Collision Information or Shared Randomness
- Title（参考訳）: 衝突情報や共有ランダム性のない対戦型マルチプレイヤー帯域に対する正方形ルートレグレット
- Abstract要約: 我々は、衝突情報、共有ランダム性、または外部通信チャネルを使わずに、K$アームと2le mK$ラベル付きプレーヤーによる対戦型マルチプレイヤーバンドの研究を行った。
我々はモンテカルロ公共コンストラクタを用いた構築的通信および同期プロトコルを設計する。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: We study adversarial multiplayer bandits with $K$ arms and $2\le m<K$ labeled players, without collision information, shared randomness, or an external communication channel. We design a constructive communication and synchronization protocol with a Monte Carlo public constructor. With probability at least $1-CN^{-32}$ over preprocessing, where $N=2Km(T+1)$, its fixed published output satisfies \[ R_T\le C K^{5/2}\sqrt T\log^2(2Km(T+1)) \] simultaneously for every oblivious reward sequence chosen after preprocessing. Here $R_T$ is expected regret over the players' private execution randomness. Positive reward observations establish a common learning schedule and synchronize players before learning begins. The cost of delayed communication is charged to the support of positive rewards, ensuring that periods with little useful feedback incur only limited regret. A slow--fast learning procedure then maintains valid reward estimates while assignments and scores are exchanged.
- Abstract（参考訳）: 我々は、衝突情報、共有ランダム性、外部通信チャネルを使わずに、K$アームと2ドルm<K$ラベル付きプレーヤーによる対戦型マルチプレイヤーバンドの研究を行った。
我々はモンテカルロ公共コンストラクタを用いた構築的通信および同期プロトコルを設計する。
確率が 1-CN^{-32}$ 以上の前処理では、$N=2Km(T+1)$ となると、その固定された出力は前処理後に選択されたすべての不愉快な報酬列に対して同時に \[R_T\le C K^{5/2}\sqrt T\log^2(2Km(T+1)) \] を満たす。
ここで$R_T$は、プレイヤーのプライベートな実行ランダム性を後悔する。
肯定的な報酬観察は共通の学習スケジュールを確立し、学習が始まる前にプレイヤーを同期させる。
遅延通信のコストは、肯定的な報酬の支持に充てられ、有用なフィードバックがほとんどない期間は、後悔にしかならないことが保証される。
遅い学習手順では、割り当てとスコアが交換される間、有効な報酬推定が維持される。
関連論文リスト
- Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary [13.08870048693199]
我々は, 1 つのアルゴリズムが, 難解な敵に対して 1 ドルごとに$widetildemathcalO(sqrt(S+1)KT)$ expected regret を達成することを示す。
提案アルゴリズムは,固定共有学習者と,局所的な改善を探索するダイアディック・インターバルを併用する。
論文 参考訳（メタデータ） (2026-09-11T21:23:20Z) - Adversarial Learning in Games with Bandit Feedback: Logarithmic Pure-Strategy Maximin Regret [64.73231630190121]
ゼロサムゲームを学ぶことは、ゲーム理論と機械学習の基本的な問題である。
ビジットフィードバックによるゼロサムゲームにおける対戦学習について検討し,最大戦略に対する障害を最小限に抑えることを目的とした。
我々は,Tsallis-INFアルゴリズムがゲーム依存パラメータ$c$で$O(c log T)$インスタンス依存後悔を実現することを示す。
論文 参考訳（メタデータ） (2026-02-06T03:26:01Z) - Instance-Dependent Regret Bounds for Learning Two-Player Zero-Sum Games with Bandit Feedback [60.610120215789976]
純粋な戦略 ナッシュ均衡が存在するとき、$c$ は 0 となり、最適のインスタンス依存後悔境界となることを示す。
また,本アルゴリズムは最終段階の収束性も享受し,ほぼ最適サンプルを用いて純粋な戦略ナッシュ均衡を同定することができる。
論文 参考訳（メタデータ） (2025-02-24T20:20:06Z) - Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
クライアントが学習者にコミュニケーション制約のあるフィードバックを提供する分散マルチアームバンディットについて検討する。
我々は、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$mathtUEtext-UCB++$を提案する。
論文 参考訳（メタデータ） (2023-04-25T09:31:20Z) - 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 Regret for Adversarial MDP with Delayed Bandit Feedback [67.63049551992816]
エピソードマルコフ決定過程(MDP)におけるオンライン学習について検討した。
ほぼ最適の$sqrtK + D$ regret, where $K$ is the number of episodes, $D = sum_k=1K dk$ is the total delay。
論文 参考訳（メタデータ） (2022-01-31T12:34:26Z) - An Instance-Dependent Analysis for the Cooperative Multi-Player
Multi-Armed Bandit [93.97385339354318]
マルチプレイヤーマルチアーマッドバンドにおける情報共有と協調の課題について検討する。
まず, プレイヤーの最適度差を推定するために, 逐次的除去戦略への簡単な修正が可能であることを示す。
第2に,第1の結果を利用して,衝突の小さな報奨をプレイヤー間の協調に役立てる通信プロトコルを設計する。
論文 参考訳（メタデータ） (2021-11-08T23:38:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。