論文の概要: LOFA: Online Influence Maximization under Full-Bandit Feedback using Lazy Forward Selection

• arxiv url: http://arxiv.org/abs/2601.00933v1
• Date: Fri, 02 Jan 2026 08:00:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-01-06 16:25:21.867674
• Title: LOFA: Online Influence Maximization under Full-Bandit Feedback using Lazy Forward Selection
• Title（参考訳）: LOFA:遅延フォワード選択を用いた全帯域フィードバックによるオンライン影響最大化
• Authors: Jinyu Xu, Abhishek K. Umrawal,
• Abstract要約: オンライン環境における影響問題(L-OFA)を利用して,ノードのサブセットを選択する。 既存のアルゴリズムと比較して優れた性能を実現するアルゴリズムを実証するために実験を行う。
• 参考スコア（独自算出の注目度）: 2.2942509826099107
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We study the problem of influence maximization (IM) in an online setting, where the goal is to select a subset of nodes$\unicode{x2014}$called the seed set$\unicode{x2014}$at each time step over a fixed time horizon, subject to a cardinality budget constraint, to maximize the expected cumulative influence. We operate under a full-bandit feedback model, where only the influence of the chosen seed set at each time step is observed, with no additional structural information about the network or diffusion process. It is well-established that the influence function is submodular, and existing algorithms exploit this property to achieve low regret. In this work, we leverage this property further and propose the Lazy Online Forward Algorithm (LOFA), which achieves a lower empirical regret. We conduct experiments on a real-world social network to demonstrate that LOFA achieves superior performance compared to existing bandit algorithms in terms of cumulative regret and instantaneous reward.
• Abstract（参考訳）: オンライン環境でのインフルエンス最大化(IM)の問題について検討し、そこでは、予測累積影響を最大化するために、固定時間地平線上の各ステップ毎にシードセット$\unicode{x2014}$at というノードのサブセットを選択することを目標としている。 我々は全帯域フィードバックモデルの下で動作し、ネットワークや拡散過程に関する付加的な構造情報を持たず、各時点における選択されたシードセットの影響のみを観測する。 影響関数が部分モジュラーであることは確実であり、既存のアルゴリズムはこの特性を利用して少ない後悔を実現する。 本研究では、この特性をさらに活用し、経験的後悔の少ない Lazy Online Forward Algorithm (LOFA) を提案する。 実世界のソーシャルネットワーク上で実験を行い、LOFAが既存のバンディットアルゴリズムと比較して、累積的後悔と即時報酬の点で優れた性能を発揮することを示す。

関連論文リスト

• Fair Algorithms with Probing for Multi-Agent Multi-Armed Bandits [15.700062892888084]
  我々は、割り当て前に選択した武器に関する情報を戦略的に収集する新しい探索フレームワークを導入する。 報奨分布が知られているオフライン環境では、準モジュラ特性を利用して、証明可能な性能境界を持つ欲求探索アルゴリズムを設計する。 より複雑なオンライン設定では、公平性を維持しながらサブ線形後悔を実現するアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2025-06-17T21:43:21Z)
• Submodular Reinforcement Learning [38.40138241424851]
  強化学習(RL)では、状態の報酬は通常加法的と見なされ、マルコフの仮定に従って、それらは以前に訪れた状態に対して$textitindependent$である。 カバー範囲制御、実験設計、情報経路計画といった多くの重要な応用において、報酬は自然にリターンを減少させ、すなわち、それらの価値は以前に訪れた同様の状態から減少する。 減少するリターンをキャプチャするサブモジュール集合関数をモデルとした,より汎用的で非付加的(かつ履歴に依存しない)報酬を最適化するパラダイムである$textitsubmodular RL$ (SubRL)を提案する。
  論文  参考訳（メタデータ） (2023-07-25T09:46:02Z)
• Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation [69.0695698566235]
  線形関数近似による強化学習と,コスト関数の逆変化について検討した。 本稿では,未知のダイナミクスと帯域幅フィードバックの一般設定に挑戦する,計算効率のよいポリシ最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T17:26:39Z)
• Provably Efficient Reinforcement Learning for Online Adaptive Influence Maximization [53.11458949694947]
  本稿では,リアルタイムフィードバックに基づいてシードノードを逐次活性化する,コンテンツ依存型オンライン影響問題の適応バージョンについて検討する。 提案アルゴリズムは,最適政策を楽観的に改善しつつ,ネットワークモデルの推定を保守し,適応的にシードを選択する。
  論文  参考訳（メタデータ） (2022-06-29T18:17:28Z)
• Online Nonsubmodular Minimization with Delayed Costs: From Full Information to Bandit Feedback [98.7678704343537]
  我々は,オンラインおよび近似的オンライン帯域勾配勾配アルゴリズムのいくつかの変種に対する後悔の保証を,特別な構造を持つ非部分モジュラ関数のクラスに焦点をあてる。 我々は,決定の選択と帰属費用の受け取りの遅れが無拘束である場合でも,エージェントの完全な情報と盗賊のフィードバック設定に対する後悔の限界を導出する。
  論文  参考訳（メタデータ） (2022-05-15T08:27:12Z)
• Where is the Grass Greener? Revisiting Generalized Policy Iteration for Offline Reinforcement Learning [81.15016852963676]
  オフラインRL体制における最先端のベースラインを、公正で統一的で高分解能なフレームワークの下で再実装する。 与えられたベースラインが、スペクトルの一方の端で競合する相手よりも優れている場合、他方の端では決してしないことを示す。
  論文  参考訳（メタデータ） (2021-07-03T11:00:56Z)
• Lenient Regret for Multi-Armed Bandits [72.56064196252498]
  エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。 アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。 我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
  論文  参考訳（メタデータ） (2020-08-10T08:30:52Z)

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

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