論文の概要: Regret Lower Bounds in Multi-agent Multi-armed Bandit

• arxiv url: http://arxiv.org/abs/2308.08046v1
• Date: Tue, 15 Aug 2023 21:20:24 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-17 15:35:46.857144
• Title: Regret Lower Bounds in Multi-agent Multi-armed Bandit
• Title（参考訳）: マルチエージェントマルチアームバンドにおけるレギュレット下界
• Authors: Mengfan Xu, Diego Klabjan
• Abstract要約: Multi-armed Banditは、後悔の証明可能な上限を持つメソッドを動機付けている。 異なる設定にまたがる後悔の少ない境界について、初めて包括的な研究を行った。
• 参考スコア（独自算出の注目度）: 14.822625665220068
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-armed Bandit motivates methods with provable upper bounds on regret and also the counterpart lower bounds have been extensively studied in this context. Recently, Multi-agent Multi-armed Bandit has gained significant traction in various domains, where individual clients face bandit problems in a distributed manner and the objective is the overall system performance, typically measured by regret. While efficient algorithms with regret upper bounds have emerged, limited attention has been given to the corresponding regret lower bounds, except for a recent lower bound for adversarial settings, which, however, has a gap with let known upper bounds. To this end, we herein provide the first comprehensive study on regret lower bounds across different settings and establish their tightness. Specifically, when the graphs exhibit good connectivity properties and the rewards are stochastically distributed, we demonstrate a lower bound of order $O(\log T)$ for instance-dependent bounds and $\sqrt{T}$ for mean-gap independent bounds which are tight. Assuming adversarial rewards, we establish a lower bound $O(T^{\frac{2}{3}})$ for connected graphs, thereby bridging the gap between the lower and upper bound in the prior work. We also show a linear regret lower bound when the graph is disconnected. While previous works have explored these settings with upper bounds, we provide a thorough study on tight lower bounds.
• Abstract（参考訳）: 多腕バンディットは、後悔の証明可能な上界を持つ手法を動機付け、他方の下界もこの文脈で広く研究されている。 近年、マルチエージェントマルチアームバンドは、個々のクライアントが分散的にバンディット問題に直面し、目的はシステム全体のパフォーマンスであり、通常後悔によって測定される。 後悔の上界を持つ効率的なアルゴリズムが出現する一方で、近年の敵の設定に対する下界を除いて、対応する後悔下界に対して限定的な注意が向けられている。 この目的のために、我々は、異なる設定における後悔の下限に関する最初の包括的な研究を行い、その厳密さを確立する。 具体的には、グラフが良好な接続性を示し、報酬が確率的に分布しているとき、平均ギャップ独立境界に対して$O(\log T)$と$\sqrt{T}$の下位境界を示す。 逆の報酬を仮定すると、連結グラフに対して下限 $o(t^{\frac{2}{3}})$ を定め、これにより前作業における下限と上限の間のギャップを橋渡しする。 また,グラフの切り離し時に,線形な後悔値下限を示す。 先行研究では,これらの設定を上界で検討してきたが,下界の密接性について徹底的な研究を行っている。

関連論文リスト

• Learning to Explore with Lagrangians for Bandits under Unknown Linear Constraints [8.784438985280094]
  線形制約が未知の多腕バンディットにおける純粋探索として問題を研究する。 まず、制約下での純粋な探索のために、サンプルの複雑さを低く抑えたラグランジアン緩和を提案する。 第二に、ラグランジアンの下界と凸の性質を利用して、トラック・アンド・ストップとガミファイド・エクスプローラー(LATSとLAGEX)の2つの計算効率の良い拡張を提案する。
  論文  参考訳（メタデータ） (2024-10-24T15:26:14Z)
• Best Arm Identification with Minimal Regret [55.831935724659175]
  最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。 エージェントの目標は、所定の信頼度で最高の腕を特定することである。 二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
  論文  参考訳（メタデータ） (2024-09-27T16:46:02Z)
• Closing the Gap Between the Upper Bound and the Lower Bound of Adam's Iteration Complexity [51.96093077151991]
  我々はAdamの新しい収束保証を導出し、$L$-smooth条件と有界雑音分散仮定のみを導出する。 本証明は,運動量と適応学習率の絡み合いを扱うために,新しい手法を利用する。
  論文  参考訳（メタデータ） (2023-10-27T09:16:58Z)
• Lower Bounds for Learning in Revealing POMDPs [88.23337313766355]
  本稿では, 難易度の高い環境下での強化学習(RL)の基本的限界について検討する。 Emphmulti-steping POMDPs に対して、潜伏状態空間依存はサンプル複雑性において少なくとも$Omega(S1.5)$であることを示す。
  論文  参考訳（メタデータ） (2023-02-02T18:59:30Z)
• Precise Regret Bounds for Log-loss via a Truncated Bayesian Algorithm [14.834625066344582]
  対数損失下での逐次的オンライン回帰(シーケンシャル確率代入)について検討する。 我々は、専門家のクラスで発生する過剰な損失として定義される連続したミニマックスの後悔に対して、厳密で、しばしば一致し、下限と上限を得ることに重点を置いている。
  論文  参考訳（メタデータ） (2022-05-07T22:03:00Z)
• Sharp Bounds for Federated Averaging (Local SGD) and Continuous Perspective [49.17352150219212]
  Federated AveragingFedAvg(ローカルSGD)は、Federated Learning(FL)で最も人気のあるアルゴリズムの1つである。 微分方程式(SDE)の観点から、この量を解析する方法を示す。
  論文  参考訳（メタデータ） (2021-11-05T22:16:11Z)
• Unified lower bounds for interactive high-dimensional estimation under information constraints [40.339506154827106]
  我々は、異なるパラメトリックな分布族に対して、様々な(八)ミニマックスの下限を導出できる統一的なフレームワークを提供する。 我々の下界フレームワークは汎用的であり、幅広い推定問題に適用可能な「プラグ・アンド・プレイ」境界が得られる。
  論文  参考訳（メタデータ） (2020-10-13T17:25:19Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)
• Tight Lower Bounds for Combinatorial Multi-Armed Bandits [72.56064196252498]
  Combinatorial Multi-Armed Bandit 問題は、エージェントが各ラウンドで一組の腕を選択する、シーケンシャルな意思決定問題である。 最近提案されたGini重み付き滑らか度パラメータが単調報酬関数の下限を決定することを示す。
  論文  参考訳（メタデータ） (2020-02-13T08:53:43Z)

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

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