論文の概要: Adaptive Frontier Exploration on Graphs with Applications to Network-Based Disease Testing

• arxiv url: http://arxiv.org/abs/2505.21671v1
• Date: Tue, 27 May 2025 18:48:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-29 17:35:50.239408
• Title: Adaptive Frontier Exploration on Graphs with Applications to Network-Based Disease Testing
• Title（参考訳）: グラフ上の適応的フロンティア探索とネットワークベース疾患検査への応用
• Authors: Davin Choo, Yuqi Pan, Tonghan Wang, Milind Tambe, Alastair van Heerden, Cheryl Johnson,
• Abstract要約: 我々は,各ノードが未知のラベルを持つような$n$-node graph $G$について,逐次決定問題を研究する。 我々は、一般的なグラフに適用可能なGittinsインデックスベースのポリシーを設計し、$G$が森林である場合に確実に最適である。 合成および実世界のグラフの実験は、我々の手法が自然の基準線を一貫して上回っていることを示している。
• 参考スコア（独自算出の注目度）: 25.36924544001149
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study a sequential decision-making problem on a $n$-node graph $G$ where each node has an unknown label from a finite set $\mathbf{\Sigma}$, drawn from a joint distribution $P$ that is Markov with respect to $G$. At each step, selecting a node reveals its label and yields a label-dependent reward. The goal is to adaptively choose nodes to maximize expected accumulated discounted rewards. We impose a frontier exploration constraint, where actions are limited to neighbors of previously selected nodes, reflecting practical constraints in settings such as contact tracing and robotic exploration. We design a Gittins index-based policy that applies to general graphs and is provably optimal when $G$ is a forest. Our implementation runs in $O(n^2 \cdot |\mathbf{\Sigma}|^2)$ time while using $O(n \cdot |\mathbf{\Sigma}|^2)$ oracle calls to $P$ and $O(n^2 \cdot |\mathbf{\Sigma}|)$ space. Experiments on synthetic and real-world graphs show that our method consistently outperforms natural baselines, including in non-tree, budget-limited, and undiscounted settings. For example, in HIV testing simulations on real-world sexual interaction networks, our policy detects nearly all positive cases with only half the population tested, substantially outperforming other baselines.
• Abstract（参考訳）: 各ノードが有限集合 $\mathbf{\Sigma}$ から未知のラベルを持つような$n$ノードグラフ $G$ 上で逐次決定問題を研究する。 各ステップでノードを選択するとラベルが明らかになり、ラベルに依存した報酬が得られる。 目標は、期待される累積割引報酬を最大化するためにノードを適応的に選択することである。 我々は,従来選択されていたノードの近傍にのみ行動が制限されるフロンティア探索の制約を課し,接触追跡やロボット探索といった設定の実践的な制約を反映する。 我々は、一般的なグラフに適用可能なGittinsインデックスベースのポリシーを設計し、$G$が森林である場合に確実に最適である。 私たちの実装は、$O(n^2 \cdot |\mathbf{\Sigma}|^2)$timeで、$O(n \cdot |\mathbf{\Sigma}|^2)$oracleコールを$P$と$O(n^2 \cdot |\mathbf{\Sigma}|)$ spaceで実行します。 合成および実世界のグラフ実験により,本手法は非木,予算制限,未公表の設定など,自然のベースラインを一貫して上回っていることがわかった。 例えば、実世界の性交ネットワーク上でのHIV検査シミュレーションでは、人口の半分しか検査されていないほぼすべての陽性症例を検出し、他の基準よりも大幅に優れています。

関連論文リスト

• Collaborative non-parametric two-sample testing [55.98760097296213]
  目標は、null仮説の$p_v = q_v$が拒否されるノードを特定することである。 グラフ構造を効率的に活用する非パラメトリックコラボレーティブ2サンプルテスト(CTST)フレームワークを提案する。 提案手法は,f-divergence Estimation, Kernel Methods, Multitask Learningなどの要素を統合する。
  論文  参考訳（メタデータ） (2024-02-08T14:43:56Z)
• Minimizing Polarization in Noisy Leader-Follower Opinion Dynamics [17.413930396663833]
  本稿では,ノイズの多いソーシャルネットワークにおけるリーダ・フォロワーの意見ダイナミクスに対する偏極最適化の問題について考察する。 私たちは、すべてのリーダの意見が同一であり、変化のない、一般的なリーダフォローのDeGrootモデルを採用しています。 目的関数が単調で超モジュラーであることを示し、その後、近似係数が1-1/e$の単純なグレディアルゴリズムを提案し、O((n-q)3)$時間で問題を解く。
  論文  参考訳（メタデータ） (2023-08-14T08:52:24Z)
• 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)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。 グラフの構造は知られており、ノードは$N$である。 頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-08-26T16:21:31Z)
• Approximate Function Evaluation via Multi-Armed Bandits [51.146684847667125]
  既知の滑らかな関数 $f$ の値を未知の点 $boldsymbolmu in mathbbRn$ で推定する問題について検討する。 我々は、各座標の重要性に応じてサンプルを学習するインスタンス適応アルゴリズムを設計し、少なくとも1-delta$の確率で$epsilon$の正確な推定値である$f(boldsymbolmu)$を返す。
  論文  参考訳（メタデータ） (2022-03-18T18:50:52Z)
• Maximizing Influence of Leaders in Social Networks [15.05158252504978]
  我々は、$n$ノードと$m$エッジを持つソーシャルネットワークにおける意見力学のDeGrootモデルに対するエッジ加算問題を考察する。 提案アルゴリズムは,100万以上のノードを持つ大規模ネットワークに対して,効率的かつ効果的であることを示す。
  論文  参考訳（メタデータ） (2021-06-11T02:31:46Z)
• Nearly Minimax Optimal Reward-free Reinforcement Learning [88.75843804630772]
  本稿では、特にバッチ強化学習に適した報酬不要強化学習フレームワークと、複数の報酬関数に対するポリシーを必要とするシナリオについて検討する。 textbfStaged textbfSampling + textbfTruncated textbfPlanning (algoname) という新しい効率的なアルゴリズムを提供しています。
  論文  参考訳（メタデータ） (2020-10-12T17:51:19Z)
• Better Bounds on the Adaptivity Gap of Influence Maximization under Full-adoption Feedback [15.533908352376853]
  影響カスケードによって到達されるノードの期待数を最大化する$k$ノードのセットを探します。 適応性ギャップは $lceil nrceil $ で上界であることを示し、$n$ はグラフ内のノード数である。 また、0-有界グラフ、すなわち無向グラフにおいて、適応性ギャップは少なくとも$frac3e3e3-1approx 3.16$であることを示す。
  論文  参考訳（メタデータ） (2020-06-27T14:43:34Z)
• Agnostic Learning of a Single Neuron with Gradient Descent [92.7662890047311]
  期待される正方形損失から、最も適合した単一ニューロンを学習することの問題点を考察する。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。 ReLUアクティベーションでは、我々の人口リスク保証は$O(mathsfOPT1/2)+epsilon$である。
  論文  参考訳（メタデータ） (2020-05-29T07:20:35Z)
• Locally Private Hypothesis Selection [96.06118559817057]
  我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。 局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。 提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
  論文  参考訳（メタデータ） (2020-02-21T18:30:48Z)

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

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