Online Minimization of Polarization and Disagreement via Low-Rank Matrix Bandits

This paper addresses the online minimization of polarization and disagreement in the Friedkin-Johnsen opinion dynamics model under incomplete information by proposing a two-stage low-rank matrix bandit algorithm that achieves a cumulative regret of $\widetilde{\mathcal{O}}\big(\max(\tfrac{1}{\kappa},\sqrt{|V|})\sqrt{|V|T}\big)$ through subspace estimation and linear bandit optimization.

The Gist

Imagine a massive, chaotic town square where thousands of people are constantly talking to their neighbors. Some people are naturally very optimistic, others are naturally very pessimistic. As they chat, they influence each other, eventually settling into a "group mood."

Sometimes, this group mood splits into two extreme camps (polarization), or neighbors start shouting at each other because they can't agree (disagreement). The goal of this research is to figure out how a city planner (an algorithm) can gently nudge the conversation to make everyone get along better, without knowing what anyone's natural personality is beforehand.

Here is the breakdown of the paper's ideas using simple analogies:

1. The Problem: The Blind City Planner

In the past, researchers assumed the city planner had a secret list of everyone's "innate opinions" (their true personality). With that list, they could calculate exactly which conversations to tweak to stop the fighting.

The Reality: In the real world (like on Facebook or X), we don't have a secret list. We can't ask people, "What is your true opinion?" because that's private or too hard to get.

• The Challenge: The planner has to make changes (interventions) blindly, watch what happens, learn from the result, and try again. It's like trying to tune a radio in a storm without knowing where the stations are.

2. The Solution: The "Two-Stage" Detective

The authors propose a smart, two-step strategy called OPD-Min-ESTR. Think of it as a detective solving a mystery:

Stage 1: The "Fingerprint" Scan (Exploration)
The detective doesn't know the culprit's face yet. So, they try out a bunch of different "what-if" scenarios (interventions) just to see how the crowd reacts.

• They aren't trying to win yet; they are just gathering clues.
• By watching how the crowd's mood shifts after these random nudges, the algorithm figures out the underlying shape of the problem. It realizes, "Ah! Even though there are 1,000 people, their opinions seem to be driven by just a few main factors."
• Analogy: Imagine trying to understand a complex machine. Instead of looking at every single screw, you tap it in different places to see which parts vibrate together. You realize the machine is actually just two big gears turning, not a million tiny parts.

Stage 2: The "Shortcut" Strategy (Exploitation)
Once the detective realizes the problem is actually much simpler than it looks (it has a "low-rank" structure), they stop looking at the whole messy machine.

• They zoom in on just the two main gears they found in Stage 1.
• Now, instead of trying to solve a puzzle with 1,000 pieces, they only have to solve a puzzle with 2 pieces.
• They use a standard, fast strategy to find the perfect move within this tiny, simplified world.

3. Why This is a Big Deal

Usually, when you have a problem with thousands of variables (like 1,000 people), trying to learn the best solution takes forever and requires massive computing power. It's like trying to find a needle in a haystack the size of a mountain.

• The Old Way: Try to find the needle by checking every single piece of hay. (Very slow, very expensive).
• This Paper's Way: Realize the needle is actually magnetized and only moves in two specific directions. Now you just need to check those two directions. (Super fast, very efficient).

4. The Result

The researchers proved mathematically that their "Two-Stage Detective" method works much better than the old "Blind Guessing" methods.

• Speed: It learns the solution much faster.
• Efficiency: It wastes less time making bad guesses.
• Real-world Test: They tested it on fake networks and real social networks (like the famous "Karate Club" friendship network). In every case, their method found the "peaceful" solution faster and with less "regret" (less time spent arguing) than the competition.

Summary in One Sentence

This paper teaches computers how to fix social media arguments by first doing a quick "scout mission" to find the hidden patterns in the chaos, and then using that shortcut to quickly find the perfect way to bring everyone together, all without ever needing to know anyone's private thoughts.

Technical Summary

Here is a detailed technical summary of the paper "Online Minimization of Polarization and Disagreement via Low-Rank Matrix Bandits", published as a conference paper at ICLR 2026.

1. Problem Formulation

The paper addresses the problem of minimizing polarization and disagreement in social networks under the Friedkin–Johnsen (FJ) opinion dynamics model.

• Context: In the FJ model, agents have fixed innate opinions ($s$) and evolving expressed opinions ($z$). The system converges to an equilibrium $z^* = (I + L)^{-1}s$, where $L$ is the graph Laplacian.
• Objective: Minimize the sum of polarization (variance of expressed opinions) and disagreement (local tension between neighbors). Mathematically, this sum is equivalent to $f(L) = s^\top(I + L)^{-1}s$.
• The Gap: Prior work assumes full knowledge of innate opinions ($s$) to perform offline optimization. However, in reality, $s$ is unknown, private, and difficult to query.
• The Novel Setting (OPD-Min): The authors formulate an Online Polarization and Disagreement Minimization problem.
  • Unknown Parameters: The innate opinion vector $s$ is unknown.
  • Action Space: The learner selects interventions (modifications to the network structure) represented by a set of admissible Laplacians $\mathcal{L}$, or equivalently, their corresponding "forest matrices" $X = (I + L)^{-1}$.
  • Feedback: After each intervention, the learner observes only a noisy scalar feedback representing the total polarization plus disagreement ($Y_t = \langle X_t, \Theta^* \rangle + \eta_t$, where $\Theta^* = ss^\top$).
  • Goal: Minimize cumulative regret over time horizon $T$ compared to the best fixed intervention in hindsight.

2. Methodology: OPD-Min-ESTR

The authors propose a two-stage algorithm called OPD-Min-ESTR (Explore-Subspace-Then-Refine), tailored to the specific structure of the problem (rank-one parameter matrix and structured action space).

Stage 1: Explore Opinion Subspace

• Goal: Estimate the low-dimensional subspace containing the true parameter matrix $\Theta^* = ss^\top$.
• Mechanism: The learner pulls arms (interventions) for $T_1$ rounds (e.g., uniformly at random).
• Estimator: They solve a nuclear-norm regularized least-squares problem to estimate $\Theta^*$:
  $$\hat{\Theta} = \arg\min_{\Theta} \left( \frac{1}{2T_1} \sum_{t=1}^{T_1} (Y_t - \langle X_t, \Theta \rangle)^2 + \lambda_{T_1} \|\Theta\|_{\text{nuc}} \right)$$
• Theoretical Challenge & Solution: Standard low-rank bandit analyses assume actions can be sampled from a continuous distribution (e.g., Gaussian) to ensure exploration. Here, actions are discrete forest matrices. The authors prove that Restricted Strong Convexity (RSC) holds for their specific structured action set under uniform sampling, allowing for accurate estimation of the subspace even without continuous sampling.
• Output: The top eigenvector $\hat{s}$ of $\hat{\Theta}$ is extracted to approximate the direction of $s$.

Stage 2: Dimensionality Reduction and Subspace Linear Bandit

• Goal: Solve the remaining bandit problem in a reduced dimension.
• Mechanism:
  1. Construct an orthonormal basis $[\hat{s}, \hat{S}_\perp]$ from the estimated vector.
  2. Rotate all arm matrices $X$ into this new basis: $X' = [\hat{s}, \hat{S}_\perp]^\top X [\hat{s}, \hat{S}_\perp]$.
  3. Discard the block corresponding to the orthogonal complement ($X'_{2:|V|, 2:|V|}$), as the signal lies primarily in the direction of $\hat{s}$.
  4. Construct a reduced feature vector $x' \in \mathbb{R}^{2|V|-1}$ from the remaining components.
• Algorithm: Run a standard Linear Bandit algorithm (e.g., OFUL) on the reduced $2|V|-1$dimensional space for the remaining$T - T_1$ rounds.

3. Key Contributions

1. Novel Problem Formulation: First formalization of minimizing polarization/disagreement in an online setting with unknown innate opinions, bridging opinion dynamics with stochastic low-rank matrix bandits.
2. Algorithmic Innovation: A two-stage algorithm (OPD-Min-ESTR) that handles the discrete, highly structured action space (forest matrices) where existing low-rank bandit methods fail. It avoids the prohibitive $O(|V|^6)$ complexity of optimal experimental design by leveraging nuclear-norm regularization and RSC analysis.
3. Theoretical Guarantees: Proved a cumulative regret bound of:
   $$\tilde{O}\left( \max\left\{ \frac{1}{\kappa}, \sqrt{|V|} \right\} \sqrt{|V| T} \right)$$
   where $\kappa$ depends on the diversity of interventions. This improves upon the naive linear bandit bound of $\tilde{O}(|V|^2 \sqrt{T})$ by exploiting the rank-one structure.
4. Empirical Validation: Demonstrated significant outperformance over high-dimensional baselines in both regret and runtime.

4. Experimental Results

• Datasets: Synthetic graphs (Erdős–Rényi, Stochastic Block Models) and real-world networks (Florentine families, Davis Southern women, Karate club, Les Misérables).
• Baselines: Compared against a high-dimensional OFUL (operating in $|V|^2$ space) and an Oracle Subspace OFUL (which knows the true subspace).
• Findings:
  • Regret: OPD-Min-ESTR achieves cumulative regret close to the Oracle baseline and significantly lower than the high-dimensional OFUL.
  • Efficiency: The algorithm is orders of magnitude faster than the full-dimensional baseline. For $|V|=16$, runtime was reduced from ~74s to ~15s; for larger graphs, the gap widens.
  • Scalability: The method scales effectively up to $|V|=1024$ nodes.
  • Robustness: Performance remains stable across varying noise levels and action set sizes.

5. Significance and Impact

• Practical Relevance: The work addresses a critical real-world constraint: social media platforms cannot directly query users' innate opinions due to privacy and cost. This framework allows for effective intervention strategies using only aggregate feedback (e.g., overall polarization metrics).
• Theoretical Advancement: It extends the theory of low-rank matrix bandits to discrete, structured action spaces (specifically graph Laplacians), overcoming limitations of existing methods that rely on continuous sampling assumptions.
• Ethical Considerations: The authors explicitly discuss the potential for misuse (e.g., increasing polarization) and emphasize the need for governance, transparency, and fairness in deploying such algorithmic interventions.

In summary, this paper provides a rigorous, computationally efficient, and theoretically sound framework for dynamically managing social network polarization when internal agent states are hidden, offering a practical path for algorithmic interventions on real-world platforms.