論文の概要: Pure Exploration with Feedback Graphs

• arxiv url: http://arxiv.org/abs/2503.07824v1
• Date: Mon, 10 Mar 2025 20:11:59 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-12 15:45:52.558739
• Title: Pure Exploration with Feedback Graphs
• Title（参考訳）: フィードバックグラフによる純粋探索
• Authors: Alessio Russo, Yichen Song, Aldo Pacchiano,
• Abstract要約: オンライン学習問題における純粋探索のサンプル複雑性について,フィードバックグラフを用いて検討した。 我々は、信頼を保った最良の行動を学ぶ際のサンプルの複雑さに基づいて、インスタンス固有の低い境界を導出する。 以上の結果から,サンプルの複雑性がキーグラフ依存量とどのようにスケールするかが明らかとなった。
• 参考スコア（独自算出の注目度）: 23.16863295063427
• License:
• Abstract: We study the sample complexity of pure exploration in an online learning problem with a feedback graph. This graph dictates the feedback available to the learner, covering scenarios between full-information, pure bandit feedback, and settings with no feedback on the chosen action. While variants of this problem have been investigated for regret minimization, no prior work has addressed the pure exploration setting, which is the focus of our study. We derive an instance-specific lower bound on the sample complexity of learning the best action with fixed confidence, even when the feedback graph is unknown and stochastic, and present unidentifiability results for Bernoulli rewards. Additionally, our findings reveal how the sample complexity scales with key graph-dependent quantities. Lastly, we introduce TaS-FG (Track and Stop for Feedback Graphs), an asymptotically optimal algorithm, and demonstrate its efficiency across different graph configurations.
• Abstract（参考訳）: オンライン学習問題における純粋探索のサンプル複雑性について,フィードバックグラフを用いて検討した。 このグラフは学習者に利用可能なフィードバックを指示し、完全な情報、純粋な盗聴フィードバック、選択されたアクションに対するフィードバックのない設定の間のシナリオをカバーします。 この問題の変種は, 後悔の最小化のために検討されているが, 本研究の焦点である純粋探査環境に対処する以前の研究は行われていない。 我々は、フィードバックグラフが未知で確率的であっても、最良の行動を学ぶ際のサンプルの複雑さに基づいて、インスタンス固有の下限を導出し、ベルヌーイの報酬に対する識別不可能な結果を示す。 さらに,本研究では,サンプルの複雑さがキーグラフ依存量とどのようにスケールするかを明らかにした。 最後に、漸近的に最適なアルゴリズムであるTaS-FG(Track and Stop for Feedback Graphs)を導入し、その効率性を異なるグラフ構成で示す。

関連論文リスト

• Towards joint graph learning and sampling set selection from data [27.52699981080567]
  グラフ構造が事前に定義されていないシナリオにおいて,グラフ信号をサンプリングする問題について検討する。 既存のアプローチは、2段階のプロセスに依存しており、まずグラフを学習し、次にサンプリングする。 この研究は、グラフ構造とサンプリングセットを共同最適化するための基礎的なステップを提供する。
  論文  参考訳（メタデータ） (2024-12-12T23:05:40Z)
• Scalable Graph Self-Supervised Learning [5.111788854550303]
  正規化におけるグラフの自己監視学習(SSL)法では、グラフ内のノード数や埋め込み次元によって計算複雑性が増大する。 ボリューム最大化項を用いた事前学習損失関数の共分散行列計算のコスト削減のための新しい手法を提案する。
  論文  参考訳（メタデータ） (2024-02-14T22:23:35Z)
• Rethinking Explaining Graph Neural Networks via Non-parametric Subgraph Matching [68.35685422301613]
  そこで我々はMatchExplainerと呼ばれる新しい非パラメトリックな部分グラフマッチングフレームワークを提案し、説明的部分グラフを探索する。 ターゲットグラフと他のインスタンスを結合し、ノードに対応する距離を最小化することで最も重要な結合部分構造を識別する。 合成および実世界のデータセットの実験は、最先端のパラメトリックベースラインをかなりのマージンで上回り、MatchExplainerの有効性を示す。
  論文  参考訳（メタデータ） (2023-01-07T05:14:45Z)
• Joint graph learning from Gaussian observations in the presence of hidden nodes [26.133725549667734]
  本稿では,隠れ変数の存在を考慮した共同グラフ学習法を提案する。 従来の考察から得られた構造を利用して凸最適化問題を提案する。 提案したアルゴリズムを異なるベースラインで比較し、合成グラフと実世界のグラフ上での性能を評価する。
  論文  参考訳（メタデータ） (2022-12-04T13:03:41Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• Context-Aware Graph Convolution Network for Target Re-identification [61.34688291210318]
  提案手法は、人および車両再識別データセットにおける最先端のパフォーマンスを実現する。 本稿では,プローブとガリーの関係をグラフノードにエンコードする新しいコンテキストアウェアグラフ畳み込みネットワーク(cagcn)を提案する。 実験により,提案手法が車体および車体の再識別データセットにおいて最先端の性能を実現することを示す。
  論文  参考訳（メタデータ） (2020-12-08T09:18:39Z)
• Graph Information Bottleneck for Subgraph Recognition [103.37499715761784]
  本稿では,深層グラフ学習における部分グラフ認識問題に対するグラフ情報ブートネック(GIB)の枠組みを提案する。 この枠組みの下では、最大情報でありながら圧縮的な部分グラフ(IB-subgraph)を認識できる。 IB-サブグラフの特性を3つのアプリケーションシナリオで評価する。
  論文  参考訳（メタデータ） (2020-10-12T09:32:20Z)
• Sample Efficient Graph-Based Optimization with Noisy Observations [17.91308664586981]
  グラフのサイズに依存しない少数のクエリの後に、ベストアーム識別の変種が、ほぼ最適解を見つけることができることを示す。 グラフベース近傍分類の問題に対して,再起動によるグリーディアルゴリズムの有効性とシミュレーションアニーリングの有効性を示す。
  論文  参考訳（メタデータ） (2020-06-04T07:22:28Z)
• Reinforcement Learning with Feedback Graphs [69.1524391595912]
  エージェントがステップ毎に追加のフィードバックを受けた場合,決定過程におけるエピソード強化学習について検討する。 状態-作用対上のフィードバックグラフを用いてこの設定を定式化し、モデルベースのアルゴリズムが追加のフィードバックを利用してよりサンプル効率のよい学習を行うことを示す。
  論文  参考訳（メタデータ） (2020-05-07T22:35:37Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。 しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。 本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
  論文  参考訳（メタデータ） (2020-01-18T09:14:16Z)

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

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