論文の概要: Constant or logarithmic regret in asynchronous multiplayer bandits
- arxiv url: http://arxiv.org/abs/2305.19691v1
- Date: Wed, 31 May 2023 09:35:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-01 17:28:39.612746
- Title: Constant or logarithmic regret in asynchronous multiplayer bandits
- Title（参考訳）: 非同期マルチプレイヤーバンディットにおける定数的・対数的後悔
- Authors: Hugo Richard, Etienne Boursier, Vianney Perchet
- Abstract要約: マルチプレイヤーのバンディット問題は、まず探索-then-commit (ETC)アルゴリズムで取り組んだ。
最適ポリシーが各アームに少なくとも1人のプレイヤーを割り当てる場合、常にインスタンス依存の後悔をもたらすアルゴリズムであるCautious Greedyを導入する。
- 参考スコア（独自算出の注目度）: 22.376992460581594
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Multiplayer bandits have recently been extensively studied because of their
application to cognitive radio networks.
While the literature mostly considers synchronous players, radio networks
(e.g. for IoT) tend to have asynchronous devices. This motivates the harder,
asynchronous multiplayer bandits problem, which was first tackled with an
explore-then-commit (ETC) algorithm (see Dakdouk, 2022), with a regret
upper-bound in $\mathcal{O}(T^{\frac{2}{3}})$. Before even considering
decentralization, understanding the centralized case was still a challenge as
it was unknown whether getting a regret smaller than $\Omega(T^{\frac{2}{3}})$
was possible.
We answer positively this question, as a natural extension of UCB exhibits a
$\mathcal{O}(\sqrt{T\log(T)})$ minimax regret.
More importantly, we introduce Cautious Greedy, a centralized algorithm that
yields constant instance-dependent regret if the optimal policy assigns at
least one player on each arm (a situation that is proved to occur when arm
means are close enough). Otherwise, its regret increases as the sum of
$\log(T)$ over some sub-optimality gaps. We provide lower bounds showing that
Cautious Greedy is optimal in the data-dependent terms.
Therefore, we set up a strong baseline for asynchronous multiplayer bandits
and suggest that learning the optimal policy in this problem might be easier
than thought, at least with centralization.
- Abstract（参考訳）: マルチプレイヤー・バンディットは認知無線ネットワークへの応用により近年広く研究されている。
文献は主に同期プレイヤーを考慮しているが、無線ネットワーク(IoTなど)は非同期デバイスを持つ傾向にある。
これはより困難で非同期なマルチプレイヤーバンディット問題であり、最初は探索列コミット(ETC)アルゴリズムに取り組み(Dakdouk, 2022 を参照)、後悔すべき上限は$\mathcal{O}(T^{\frac{2}{3}})$である。
分散化を考える前にも、$\omega(t^{\frac{2}{3}})$未満の後悔が得られなかったため、集中型ケースの理解は依然として困難であった。
UCB の自然な拡張は $\mathcal{O}(\sqrt{T\log(T)})$ minimax regret を示す。
より重要なことは、最適なポリシーが各腕に少なくとも1人のプレイヤーを割り当てた場合に、一定のインスタンス依存の後悔をもたらす集中型アルゴリズムである(arm平均が十分近い場合に発生すると証明される状況)。
さもなくば、その後悔は、いくつかの準最適ギャップに対して$\log(T)$の和として増加する。
我々は、データ依存の用語でCautious Greedyが最適であることを示す低い境界を提供する。
そこで我々は,非同期マルチプレイヤーバンディットの強力なベースラインを設定し,この問題における最適方針の学習は,少なくとも集中化を伴って考えるよりも容易である可能性が示唆された。
関連論文リスト
- Explore-then-Commit Algorithms for Decentralized Two-Sided Matching Markets [7.512199306943756]
我々は、需要側(プレイヤー)が供給側(アーム)と競合する分散化された二面マッチング市場を研究する。
この問題に対して,エポック型CA-ETC (Collision avoidance explore then commit) (textttCA-ETC,略してtextttCA-ETC) という多相探索型アルゴリズムを提案する。
初期エポック長が$T_circ$で、その後のエポック長が$2l/gamma T_circ$の場合、textttCA-ETC がプレイヤーとなることを示す。
論文 参考訳（メタデータ） (2024-08-16T12:06:09Z) - Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。
我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。
我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
論文 参考訳（メタデータ） (2024-06-15T13:26:17Z) - Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。
ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
論文 参考訳（メタデータ） (2024-04-02T12:15:37Z) - Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳（メタデータ） (2023-10-02T08:15:52Z) - 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) - Complete Policy Regret Bounds for Tallying Bandits [51.039677652803675]
政策後悔は、適応的な敵に対してオンライン学習アルゴリズムのパフォーマンスを測定するという、よく確立された概念である。
我々は,不完全な政策後悔を効果的に最小化できる敵の制限について検討する。
我々は、$tildemathcalO(mKsqrtT)$の完全なポリシーを後悔するアルゴリズムを提供し、$tildemathcalO$表記は対数要素だけを隠す。
論文 参考訳（メタデータ） (2022-04-24T03:10:27Z) - 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) - Bandit Learning in Decentralized Matching Markets [82.39061186055775]
私たちは、一方の市場(プレーヤー)が他方の側(腕)の好みについて事前知識を持っていない両面マッチング市場を研究し、経験からその好みを学ぶ必要があります。
このモデルは、標準のマルチアームバンディットフレームワークを競合する分散型マルチプレイヤー設定に拡張します。
アームの選好が共有されるたびにアルゴリズムがインセンティブ互換であることが示されるが、選好が完全に一般的である場合には必ずしもそうではない。
論文 参考訳（メタデータ） (2020-12-14T08:58:07Z) - Contextual Blocking Bandits [35.235375147227124]
我々は,多腕バンディット問題の新たな変種について検討し,各ステップごとに,腕の平均報酬を決定する独立したサンプルコンテキストをプレイヤーが観察する。
アームを再生することで(すべてのコンテキストにわたって)将来の時間ステップの固定および既知の回数をブロックする。
我々は、$mathcalO(log T)$-regret w.r.t.$alpha$regret戦略を$Tタイムステップで保証し、$Omega(log(T)$low boundと一致する UCB ベースのフル情報アルゴリズムの変種を提案する。
論文 参考訳（メタデータ） (2020-03-06T20:34:42Z) - Coordination without communication: optimal regret in two players
multi-armed bandits [1.6752182911522522]
同一の3本腕バンディットを同時に演奏するエージェントを2つ検討する。
プレイヤー間の衝突が全くない戦略を提案する。
また、この問題の完全な情報変種に対する下位境界を証明することによって、余剰対数項 $sqrtlog(T)$ は必要であると主張する。
論文 参考訳（メタデータ） (2020-02-14T17:35:42Z) - Blocking Bandits [33.14975454724348]
我々は、腕を弾くことで固定時間帯で使用できなくなる、新しいマルチアームバンディット・セッティングについて考察する。
全ての武器の報酬と遅延の事前知識により、累積報酬を最適化する問題は擬似多項式時間アルゴリズムを含まないことを示した。
我々は,このアルゴリズムに対して,$c log T + o(log T)$ cumulative regret を持つ UCB ベースのアルゴリズムを設計する。
論文 参考訳（メタデータ） (2019-07-27T20:42:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。