論文の概要: Simultaneously Learning Stochastic and Adversarial Bandits with General Graph Feedback

• arxiv url: http://arxiv.org/abs/2206.07908v1
• Date: Thu, 16 Jun 2022 04:21:27 GMT
• ステータス: 処理完了
• システム内更新日: 2022-06-17 15:50:28.432877
• Title: Simultaneously Learning Stochastic and Adversarial Bandits with General Graph Feedback
• Title（参考訳）: 一般グラフフィードバックを用いた確率帯域と逆帯域の同時学習
• Authors: Fang Kong, Yichi Zhou, Shuai Li
• Abstract要約: 一般フィードバックグラフの探索と活用のための新たなトレードオフ機構を導入する。 提案アルゴリズムは,対数設定において,$mathrmpoly-designed log T$ regretを同時に達成する。 これは、一般のフィードバックグラフに対する世界で初めての最良の結果である。
• 参考スコア（独自算出の注目度）: 15.429356827868514
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The problem of online learning with graph feedback has been extensively studied in the literature due to its generality and potential to model various learning tasks. Existing works mainly study the adversarial and stochastic feedback separately. If the prior knowledge of the feedback mechanism is unavailable or wrong, such specially designed algorithms could suffer great loss. To avoid this problem, \citet{erez2021towards} try to optimize for both environments. However, they assume the feedback graphs are undirected and each vertex has a self-loop, which compromises the generality of the framework and may not be satisfied in applications. With a general feedback graph, the observation of an arm may not be available when this arm is pulled, which makes the exploration more expensive and the algorithms more challenging to perform optimally in both environments. In this work, we overcome this difficulty by a new trade-off mechanism with a carefully-designed proportion for exploration and exploitation. We prove the proposed algorithm simultaneously achieves $\mathrm{poly} \log T$ regret in the stochastic setting and minimax-optimal regret of $\tilde{O}(T^{2/3})$ in the adversarial setting where $T$ is the horizon and $\tilde{O}$ hides parameters independent of $T$ as well as logarithmic terms. To our knowledge, this is the first best-of-both-worlds result for general feedback graphs.
• Abstract（参考訳）: グラフフィードバックによるオンライン学習の問題は,その汎用性と様々な学習タスクをモデル化する可能性から,文献で広く研究されている。 既存の著作は主に逆境フィードバックと確率フィードバックを別々に研究している。 フィードバックメカニズムに関する事前の知識が利用できなければ、そのような特別に設計されたアルゴリズムは大きな損失を被る可能性がある。 この問題を避けるため、 \citet{erez2021towards} は両方の環境に最適化を試みる。 しかし、フィードバックグラフは非指向であり、各頂点には自己ループがあり、フレームワークの汎用性を損なうものであり、アプリケーションでは満足できない可能性がある。 一般的なフィードバックグラフでは、このアームを引っ張ると腕の観察が不可能になり、探索が高価になり、アルゴリズムが両方の環境で最適に実行することがより困難になる。 そこで本研究では,探索と搾取を念入りに設計した新たなトレードオフ機構によって,この課題を克服した。 提案アルゴリズムは, 確率的設定において, $\mathrm{poly} \log T$後悔と$\tilde{O}(T^{2/3})$の最小最適後悔を同時に達成し, $T$が地平線であり, $\tilde{O}$が$T$に依存しないパラメータを隠蔽する。 私たちの知る限りでは、これは一般的なフィードバックグラフのための世界で最初の最良の結果である。

関連論文リスト

• Efficient Contextual Bandits with Uninformed Feedback Graphs [48.77120088347271]
  フィードバックグラフを持つバンディットは、完全な情報と古典的なバンディットの問題を補間する強力なオンライン学習モデルである。 ここでは,2乗損失ではなくログ損失を用いてグラフを学習し,良好な後悔の保証を得ることが重要であることを示す。
  論文  参考訳（メタデータ） (2024-02-12T23:50:47Z)
• Online Learning with Feedback Graphs: The True Shape of Regret [82.00098840619847]
  ミニマックスの後悔は任意のグラフと時間的地平線に対して$R*$に比例することを示す。 複雑な探索戦略を導入し、最小限の最小後悔境界を達成する主アルゴリズムを定義する。
  論文  参考訳（メタデータ） (2023-06-05T15:35:00Z)
• Learning on the Edge: Online Learning with Stochastic Feedback Graphs [12.83118601099289]
  有向フィードバックグラフが帯域幅を持つ拡張について検討する。 グラフの各ラウンドにおいて、グラフの各エッジは、それぞれのエッジに対して異なる確率で実現されるか、実現されないかのいずれかである。 我々は、独立性の重み付けされたバージョンと弱い支配数に依存する、より効率的なアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2022-10-09T11:21:08Z)
• Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs [62.52390282012508]
  我々は、T$ラウンド以上の時間変化フィードバックグラフを持つ、敵対的な$K$武器付きバンディットに対する高い確率的後悔境界について検討する。 提案アルゴリズムは,高い確率で最適に後悔する$widetildemathcalO((sum_t=1Talpha_t)1/2+max_tin[T]alpha_t]$を達成するアルゴリズムを開発した。 また,弱可観測グラフに対する最適高確率残差を求めるアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-10-04T04:36:15Z)
• Multi-armed Bandit Learning on a Graph [0.0]
  そこで,エージェントがグラフの上を移動して,異なるノードから収集した報酬を最大化するグラフバンドイットと呼ばれるMABの拡張について検討する。 我々は,楽観主義の原理を用いて長期探査・探索のバランスをとる学習アルゴリズムG-UCBを設計する。 提案アルゴリズムは,ノード数として$O(sqrt|S|Tlog(T)+D|S|log T)$学習後悔を実現する。
  論文  参考訳（メタデータ） (2022-09-20T02:31:42Z)
• Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs [34.37963000493442]
  本研究では,汎用的なフィードバックグラフを用いたオンライン学習について考察する。 両世界のベスト・オブ・ワールドズ・アルゴリズムは、敵の環境に対してほぼ厳密な後悔の限界を達成できる。
  論文  参考訳（メタデータ） (2022-06-02T05:01:40Z)
• A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs [21.563733343861713]
  フィードバックグラフを用いたオンライン学習は、学習者のフィードバックが行動集合上の有向グラフによって決定されるシーケンシャルな意思決定フレームワークである。 本稿では,このフレームワークで学習するための計算効率のよいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-01T15:14:32Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  フレーム間のデータアソシエーションは、Multiple Object Tracking(MOT)タスクの中核にある。 既存の手法は、主にトラックレットとフレーム内検出の間のコンテキスト情報を無視する。 そこで本研究では,学習可能なグラフマッチング手法を提案する。
  論文  参考訳（メタデータ） (2021-03-30T08:58:45Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。 エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
  論文  参考訳（メタデータ） (2020-12-10T15:40:07Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  我々は高密度サブグラフ発見のための新しい学習問題を導入する。 まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。 そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-06-24T11:37:33Z)

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

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