論文の概要: Online Minimization of Polarization and Disagreement via Low-Rank Matrix Bandits

• arxiv url: http://arxiv.org/abs/2510.00803v1
• Date: Wed, 01 Oct 2025 12:05:10 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-03 14:32:17.20361
• Title: Online Minimization of Polarization and Disagreement via Low-Rank Matrix Bandits
• Title（参考訳）: 低ランクマトリックスバンドによる偏光・分解のオンライン最小化
• Authors: Federico Cinus, Yuko Kuroki, Atsushi Miyauchi, Francesco Bonchi,
• Abstract要約: 不完全情報下でのFriedkin-Johnsen意見力学モデルにおける分極と不一致の最小化の問題について検討する。 ソーシャルメディアプラットフォームに対する定期的な介入を自然に反映したこの新しい設定は、後悔の最小化問題として定式化されている。 本アルゴリズムは, 累積的後悔とランニング時間の両方において, 線形バンディットベースラインを著しく上回ることを示す。
• 参考スコア（独自算出の注目度）: 11.533572890849902
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We study the problem of minimizing polarization and disagreement in the Friedkin-Johnsen opinion dynamics model under incomplete information. Unlike prior work that assumes a static setting with full knowledge of users' innate opinions, we address the more realistic online setting where innate opinions are unknown and must be learned through sequential observations. This novel setting, which naturally mirrors periodic interventions on social media platforms, is formulated as a regret minimization problem, establishing a key connection between algorithmic interventions on social media platforms and theory of multi-armed bandits. In our formulation, a learner observes only a scalar feedback of the overall polarization and disagreement after an intervention. For this novel bandit problem, we propose a two-stage algorithm based on low-rank matrix bandits. The algorithm first performs subspace estimation to identify an underlying low-dimensional structure, and then employs a linear bandit algorithm within the compact dimensional representation derived from the estimated subspace. We prove that our algorithm achieves an $ \widetilde{O}(\sqrt{T}) $ cumulative regret over any time horizon $T$. Empirical results validate that our algorithm significantly outperforms a linear bandit baseline in terms of both cumulative regret and running time.
• Abstract（参考訳）: 不完全情報下でのFriedkin-Johnsen意見力学モデルにおける分極と不一致の最小化の問題について検討する。 ユーザの本質的な意見を完全に把握した静的な設定を前提とした以前の作業とは違い,本質的な意見が不明で,逐次的な観察によって学ぶ必要がある,より現実的なオンライン設定に対処する。 ソーシャルメディアプラットフォームに対する定期的介入を自然に反映したこの新しい設定は、後悔の最小化問題として定式化され、ソーシャルメディアプラットフォームに対するアルゴリズム的介入と、マルチ武器の盗賊理論との鍵となるつながりを確立する。 我々の定式化では、学習者は介入後の全体偏極と不一致に対するスカラーフィードバックのみを観察する。 この新たな帯域幅問題に対して,低ランク行列帯域幅に基づく2段階のアルゴリズムを提案する。 このアルゴリズムは、まず、下層の低次元構造を特定するために部分空間推定を行い、次に、推定された部分空間から導出されるコンパクトな次元表現の中に線形帯域アルゴリズムを用いる。 我々のアルゴリズムは任意の時間軸に対して$ \widetilde{O}(\sqrt{T}) $ cumulative regret を達成することを証明している。 その結果,提案アルゴリズムは,累積的後悔とランニング時間の両方において,線形バンディットベースラインを著しく上回っていることがわかった。

関連論文リスト

• Influential Bandits: Pulling an Arm May Change the Environment [44.71145269686588]
  現実世界のアプリケーションは、しばしば非定常環境と武器間の相互依存を含む。 本稿では,未知の,対称な正の半定値相互作用行列による腕間相互作用をモデル化する,影響力のあるバンドイット問題を提案する。 我々は,損失ダイナミクスの構造に合わせて,低信頼境界(LCB)推定器に基づく新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-11T02:05:51Z)
• Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
  本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。 政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。 提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
  論文  参考訳（メタデータ） (2024-02-24T06:36:08Z)
• Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
  本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。 本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。 我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
  論文  参考訳（メタデータ） (2023-03-15T17:59:27Z)
• Exploration in Linear Bandits with Rich Action Sets and its Implications for Inference [23.364534479492715]
  期待行列の最小固有値は、アルゴリズムの累積後悔が$sqrtn)$であるときに、$Omega(sqrtn)として増加することを示す。 本研究は, 線形帯域におけるEmphmodel selectionとEmphclusteringの2つの実践シナリオに適用する。
  論文  参考訳（メタデータ） (2022-07-23T20:25:07Z)
• Online Nonsubmodular Minimization with Delayed Costs: From Full Information to Bandit Feedback [98.7678704343537]
  我々は,オンラインおよび近似的オンライン帯域勾配勾配アルゴリズムのいくつかの変種に対する後悔の保証を,特別な構造を持つ非部分モジュラ関数のクラスに焦点をあてる。 我々は,決定の選択と帰属費用の受け取りの遅れが無拘束である場合でも,エージェントの完全な情報と盗賊のフィードバック設定に対する後悔の限界を導出する。
  論文  参考訳（メタデータ） (2022-05-15T08:27:12Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。 各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。 我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
  論文  参考訳（メタデータ） (2021-01-31T16:49:07Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)
• Bandit algorithms to emulate human decision making using probabilistic distortions [20.422725678982726]
  報奨分布に歪んだ確率を持つ2つの多重武装バンディット問題を定式化する。 以上のような後悔の最小化の問題と、マルチアームバンディットのための最高の腕識別フレームワークについて考察する。
  論文  参考訳（メタデータ） (2016-11-30T17:37:51Z)

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

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