論文の概要: Improved Algorithms for Bandit with Graph Feedback via Regret Decomposition

• arxiv url: http://arxiv.org/abs/2205.15076v1
• Date: Mon, 30 May 2022 13:07:42 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-31 23:58:06.079433
• Title: Improved Algorithms for Bandit with Graph Feedback via Regret Decomposition
• Title（参考訳）: 後悔分解によるグラフフィードバックによるバンディット改善アルゴリズム
• Authors: Yuchen He and Chihao Zhang
• Abstract要約: グラフフィードバックによるバンディットの問題は、マルチアームバンディット(MAB)問題と専門家のアドバイスによる学習の両方を一般化する。 本稿では,フィードバックグラフの分割に基づく新しいアルゴリズムフレームワークを提案する。
• 参考スコア（独自算出の注目度）: 2.3034251503343466
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The problem of bandit with graph feedback generalizes both the multi-armed bandit (MAB) problem and the learning with expert advice problem by encoding in a directed graph how the loss vector can be observed in each round of the game. The mini-max regret is closely related to the structure of the feedback graph and their connection is far from being fully understood. We propose a new algorithmic framework for the problem based on a partition of the feedback graph. Our analysis reveals the interplay between various parts of the graph by decomposing the regret to the sum of the regret caused by small parts and the regret caused by their interaction. As a result, our algorithm can be viewed as an interpolation and generalization of the optimal algorithms for MAB and learning with expert advice. Our framework unifies previous algorithms for both strongly observable graphs and weakly observable graphs, resulting in improved and optimal regret bounds on a wide range of graph families including graphs of bounded degree and strongly observable graphs with a few corrupted arms.
• Abstract（参考訳）: グラフフィードバックによるバンディットの問題は、多腕バンディット(MAB)問題と専門家のアドバイスによる学習の両方を、ゲームの各ラウンドで損失ベクトルがどのように観測できるかを有向グラフにエンコードすることで一般化する。 ミニマックスの後悔はフィードバックグラフの構造と密接に関連しており、それらのつながりが完全には理解されていない。 本稿では,フィードバックグラフの分割に基づく問題に対する新しいアルゴリズムフレームワークを提案する。 本分析では,小部分による後悔の和と,その相互作用による後悔の和を分解することにより,グラフの様々な部分間の相互作用を明らかにする。 その結果,本アルゴリズムはmabのための最適アルゴリズムの補間と一般化であり,専門家のアドバイスにより学習することができる。 提案手法は, 強可観測グラフと弱可観測グラフの両方に対して, 従来のアルゴリズムを統一し, 有界次数グラフと弱可観測グラフを含む多種多様なグラフファミリにおいて, 改良および最適可観測限界を生成する。

関連論文リスト

• The graph alignment problem: fundamental limits and efficient algorithms [0.9246334723892301]
  グラフ同型問題のノイズバージョンは、エッジの大部分を保存する2つのグラフのノード間のマッチングを見つけることを目的としている。 この論文は、この問題の基本的な情報理論的限界を理解すること、および、基礎となるデータのアライメントを回復できるアルゴリズムを設計および分析することに焦点を当てている。
  論文  参考訳（メタデータ） (2024-04-18T15:31:13Z)
• Efficient Contextual Bandits with Uninformed Feedback Graphs [48.77120088347271]
  フィードバックグラフを持つバンディットは、完全な情報と古典的なバンディットの問題を補間する強力なオンライン学習モデルである。 ここでは,2乗損失ではなくログ損失を用いてグラフを学習し,良好な後悔の保証を得ることが重要であることを示す。
  論文  参考訳（メタデータ） (2024-02-12T23:50:47Z)
• FoSR: First-order spectral rewiring for addressing oversquashing in GNNs [0.0]
  グラフニューラルネットワーク(GNN)は、グラフのエッジに沿ってメッセージを渡すことによって、グラフデータの構造を活用することができる。 本稿では,グラフにエッジを体系的に付加することで過疎化を防止する計算効率のよいアルゴリズムを提案する。 提案アルゴリズムは,いくつかのグラフ分類タスクにおいて,既存のグラフリウィリング手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-10-21T07:58:03Z)
• Simultaneously Learning Stochastic and Adversarial Bandits with General Graph Feedback [15.429356827868514]
  一般フィードバックグラフの探索と活用のための新たなトレードオフ機構を導入する。 提案アルゴリズムは,対数設定において,$mathrmpoly-designed log T$ regretを同時に達成する。 これは、一般のフィードバックグラフに対する世界で初めての最良の結果である。
  論文  参考訳（メタデータ） (2022-06-16T04:21:27Z)
• A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs [21.563733343861713]
  フィードバックグラフを用いたオンライン学習は、学習者のフィードバックが行動集合上の有向グラフによって決定されるシーケンシャルな意思決定フレームワークである。 本稿では,このフレームワークで学習するための計算効率のよいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-06-01T15:14:32Z)
• Towards Graph Self-Supervised Learning with Contrastive Adjusted Zooming [48.99614465020678]
  本稿では,グラフコントラスト適応ズームによる自己教師付きグラフ表現学習アルゴリズムを提案する。 このメカニズムにより、G-Zoomはグラフから複数のスケールから自己超越信号を探索して抽出することができる。 我々は,実世界のデータセットに関する広範な実験を行い,提案したモデルが常に最先端の手法より優れていることを示す。
  論文  参考訳（メタデータ） (2021-11-20T22:45:53Z)
• Deep graph matching meets mixed-integer linear programming: Relax at your own risk ? [8.05409526074409]
  グラフマッチング問題のMILP定式化を統合する手法を提案する。 同様のアプローチは、グラフマッチング解決器の最適保証と品質レベルの導入によって導かれる。 実験により,いくつかの理論的知見が得られ,深部グラフマッチング手法の方向性を導出する。
  論文  参考訳（メタデータ） (2021-08-01T08:29:55Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  学習エージェントは、$d$-dimensionalコンテキストベクトルで提示された後、一連の$k$アクションから繰り返し選択する。 エージェントは選択されたアクションの損失を誘発し、観察するが、観察構造における隣り合うアクションの損失も観察する。 textttEXP3に基づく2つの効率的なアルゴリズムが開発された。
  論文  参考訳（メタデータ） (2020-12-10T15:40:07Z)
• Graph Information Bottleneck for Subgraph Recognition [103.37499715761784]
  本稿では,深層グラフ学習における部分グラフ認識問題に対するグラフ情報ブートネック(GIB)の枠組みを提案する。 この枠組みの下では、最大情報でありながら圧縮的な部分グラフ(IB-subgraph)を認識できる。 IB-サブグラフの特性を3つのアプリケーションシナリオで評価する。
  論文  参考訳（メタデータ） (2020-10-12T09:32:20Z)
• Reinforcement Learning with Feedback Graphs [69.1524391595912]
  エージェントがステップ毎に追加のフィードバックを受けた場合,決定過程におけるエピソード強化学習について検討する。 状態-作用対上のフィードバックグラフを用いてこの設定を定式化し、モデルベースのアルゴリズムが追加のフィードバックを利用してよりサンプル効率のよい学習を行うことを示す。
  論文  参考訳（メタデータ） (2020-05-07T22:35:37Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。 提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
  論文  参考訳（メタデータ） (2020-03-12T22:31:59Z)

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

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