Online Minimization of Polarization and Disagreement via Low-Rank Matrix Bandits
Authors: Federico Cinus
Yuko Kuroki
Atsushi Miyauchi
Francesco Bonchi
Venue: ICLR 2026 Poster (2026)
Keywords: bandits
online learning
opinion dynamics
social media platforms
Primary area: optimization
TL;DR: We present the first online framework for minimizing polarization and disagreement in the Friedkin–Johnsen model, using a two-stage low-rank matrix bandit algorithm with guarantees and strong empirical gains over linear bandits.

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 agents' 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 the 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 show that our algorithm achieves the  cumulative regret of
$\widetilde{\mathcal{O}}\big(\max(\tfrac{1}{\kappa},\sqrt{|V|})\sqrt{|V|T}\big)$ over time horizon $T$, where $V$ is the set of agents and $\kappa$ is a parameter dependent on the diversity of interventions. Empirical results validate that our algorithm significantly outperforms a linear bandit baseline in terms of both cumulative regret and running time.

Published as a conference paper at ICLR 2026
ONLINE MINIMIZATION OF POLARIZATION AND DISAGREEMENT VIA LOW-RANK MATRIX BANDITS
Federico Cinus', Yuko Kuroki', Atsushi Miyauchi", Francesco Bonchi
1 Intesa Sanpaolo AI Research Intesa Sanpaolo
[aaariico.cinsa siko.miyauchi, atoushi... Beeiahi.miiyeee yauchi,, francesca.banchl gintesaconpoolo.com
ABSTRACT
We study the problem of minimizing polarization and disagreement the Fried- kin-Johnsen opinion dynamics model under incomplete information. Unlike prior work that assumes a static setting with full knowledge of agents' innate opinions, unknown
address the more realistic online setting where innate opinions and must be learned through sequential observations. This novel setting, which naturally mirrors periodic interventions on social media platforms, is formulated a regret minimization problem, establishing a key connection between algorithmic interventions on social media platforms and the theory of multi-armed bandits. In our formulation, a learner observes only 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 linear bandit algorithm within the compact dimensional representation derived from the estimated subspace. We show that our algorithm achieves the
cumulative regret of ① (max { VIV] VIVIT) over time horizon T, where V is the set of agents and is parameter dependent on the diversity of interventions. Empirical results validate that our algorithm significantly outperforms linear bandit baseline in terms of both cumulative regret and running time.
INTRODUCTION
Social media platforms such as X and Facebook have become critical public infrastructures, facilitat- ing the swift formation of public opinion. While such dynamics can serve as powerful force for positive social change-for instance, by mobilizing collective action against undesirable political decisions thesy can also exacerbate polarization and societal division (Barberá, 2020). This has driven research into algorithmic interventions to mitigate these harmful effects (Bindel et al., 2015; Matakos al., 2017; Tu et al., 2020; Xu & Zhang, 2023; Ristache et al., 2024; Kühne al., 2025; Liu et al., 2025; Ojer et al., 2025). foundational model underlying this line of research is the Friedkin-Johnsen (FJ) opinion dynamics model in a social network, where each agent has two types of opinions: innate opinions, which are fixed, and expressed opinions, which evolve over time (Friedkin & Johnsen, 1990). Specifically, agents' expressed opinions evolve by taking weighted average of their own innate opinions and their neighbors' expressed opinions. A key property that makes the FJ model particularly appealing is that the final equilibrium state of expressed opinions can be precisely calculated from the network's ss structure and the vector of all agents' innate opinions.
The seminal work of Musco et (2018) initiated the study of minimizing polarization and disagree- ment at the FJ model equilibrium. Polarization is defined as the extent to which expressed opinions deviate from the overall average opinion, while disagreement measures the extent to which neighbor- ing agents hold divergent opinions. Musco et al. (2018) proposed an intervention on innate opinions, seeking to minimize the sum of polarization and disagreement by making limited adjustments to agents' innate opinions. Following this work, many researchers have explored alternative forms of intervention, including modifications to the network structure (Zhu et al., 2021) and adjustments to the strength of interpersonal connections (Cinus et al., 2023).

---

Published as a conference paper at ICLR 2026
Despite these advances, critical assumption persists: the full knowledge of all agents' innate opinions is available. In reality, however, acquiring this information is costly and difficult, possibly requiring extensive surveys or behavioral analysis, highlighted by recent works (Chen et al., 2018; Chaitanya et al., 2024; Neumann et al., 2024; Cinus et al., 2025).
The foundational work of Chen al. (2018) initiated the study of polarization and disagreement minimization in a more realistic setting by relaxing the assumption of full knowledge of agents' innate opinions; however, those innate opinions are restricted binary values. Chaitanya al. (2024) proposed a method to minimize an upper bound on the sum of polarization and disagreement that valid for any possible agents' innate opinions. However, the tightness of such an upper bound to the optimum remains unclear. Moreover, the proposed method relies on semidefinite programming. which can be computationally expensive. Along similar lines, Cinus et al. (2025) considered setting in which the innate opinions of limited subset of nodes can be queried in order to infer the remaining ones. However, this approach still relies on the ability to query some innate opinions: in many real-world scenarios, particularly those requiring strong privacy considerations, directly querying a node's innate opinion may be very hard or simply impossible. Neumann et al. (2024) studied the estimation of relevant measures under the FJ model, such node opinions, polarization and disagreement, without having access to the entire network and assuming to know a small number of node opinions. In particular, they showed how to estimate expressed opinions at equilibrium having access to an oracle for innate opinions, and conversely, how to estimate innate opinions from an oracle for expressed opinions at equilibrium. Their focus on sublincar-time computability.
While highlighting the need to drop the assumption of full knowledge of innate opinions, this body of work leaves significant, unaddressed gap: how to effectively minimize polarization and disagreement in an online setting, where agents' innate opinions are unknown and unqueryable, and must be learned through sequential observations, after each intervention. Our research directly addresses this challenge by introducing novel framework that bridges opinion dynamics with online learning.
Our Contributions. In this paper, we bridge the gap by utilizing the theory of malti-armed bandits (Lattimore & Szepesvári, 2020). Specifically, we address the realistic online setting where agents' innate opinions are unknown and must be learned through sequential observations. This novel setting naturally mirrors the periodic nature of interventions on social media platforms. Our core contributions are as follows:
1. We formulate the above online setting regret minimization problem, which we term the Online Polarization and Disagreement Minimization (OPD-Min) problem, establishing a key connection between algorithmic interventions on social media platforms and theory of multi- armed bandits. In our formulation, at each time step, an intervention is chosen, and the learner receives only a scalar feedback representing the overall polarization and disagreement in the network. This setup, where the underlying parameters (i.e., innate opinions) are unknown and the feedback is a low-dimensional function of the intervention, naturally links the problem to the well-established stochastic low-rank matrix bandits.
2. To solve this bandit problem, we propose a two-stage algorithm. The algorithm first performs subspace estimation to identify an underlying low-dimensional structure of the problem, and then employs a linear bandit algorithm within the compact @(VV) dimensional representation, which is significant reduction from the original dym-ddimnsioonal space, where V represents the set of agents.
3. We prove that our algorithm achieves cumulative regret bound of the form δ max { vIvI] VIVIT) over any time horizon T, where e is a parameter dependent on the diversity of feasible interventions. This the first theoretical guarantee for sequential interventions on opinion dynamics under incomplete information.
4. We substantiate our theoretical findings with extensive experiments on both synthetic and real- world networks. Our results demonstrate that our proposed algorithm significantly outperforms a linear bandit baseline in terms of both cumulative regret and running time.
Technical Challenges. A direct reduction to a linear bandit formulation (e.g., Abbasi- Yadkori et al. (201 1)) is unsatisfactory, because the feature dimension grows quadratically with [V], which results
2

---

Published as a conference paper at ICLR 2026
in the regret bound that scales with [V]2. On the other hand, existing low-rank matrix bandits (Lu et al., 2021; Kang et al., 2022), while seemingly well aligned with the low-rank nature of our problem, rely sampling actions from a continuous space, such as Gaussian random matrices. This approach is infeasible to our setting whose action space is discrete, highly structured, and induced by graph Laplacians (forest matrices). As result, existing algorithms cannot be applied directly, and their theoretical guarantees do not extend to our problem. While optimal design approaches such as (Jang al., 2024) offer theoretical benefits, they are not directly applicable our setting. Our action set consists of strictly symmetric forest matrices, which need not span RIVI" Moreover, computing the optimal design involves the covariance matrices of vectorized arms, resulting in time complexity of O((V)))-a cost that is prohibitive for large social networks. These fundamental limitations necessitate the development of algorithm tailored to the unique structure of OPD-Min. See Appendix A for more detailed discussion.
BACKGROUND
In this section, first review the Friedkin-Johnsen (FJ) opinion dynamics model (Friedkin & Johnsen, 1990), and then provide the canonical formulation of the offline problem of minimizing polarization and disagreement, which forms the basis of online formulation.
2.1 FRIEDKIN-JOHNSET (FJ) OPINION DYNAMICS MODEL.
We consider a connected, undirected, edge-weighted graph G = (V, E, w). where V corresponds to the set of agents, E represents the interactions among agents, and w E R>0 quantifies the strength of the interactions. Let A (wi,) E R |V]I|VI be a weighted adjacency matrix of G. The innate opinions of agents are represented by s = (s;) E [-1, where higher 8; value represents a more favorable opinion towards a given topic. The opinion dynamics evolve discrete-time fashion. Specifically, agents' expressed opinions 2 (t) at time 1 (t = I....) are determined
from z as follows:
(c-1) (D + II+ + +) (z 8),
where D is the degree matrix of G. whose diagonal entries are given by the weighted degrees of the nodes, and I is the V x [V] identity matrix. Since the matrix (D + -I- "A has spectral radius strictly less than 1, the process converges to a unique fixed point as f - oo (Faires Burden, 2015, Theorem 7.17 and Lemma 7.18). Specifically, equilibrium, the expressed opinions satisfy
z' = =I++L)
(I)
where L D A the Laplacian G. Note that for fixed network structure, the equilibrium depends only on the innate opinions s. Because the spectral radius p of M = (D + I)- A is strictly less than 1, the deviation from equilibrium decays at an exponential rate p(M)', so only a small number of iterations
needed for the dynamics to become arbitrarily close to x".
The matrix (I ++ -)- known as the forest matrix (Chebotarev & Agaev, 2002), symmetric positive definite with its eigenvalues in (0, 1]. Each entry Mij be interpreted the probability that random walk starting at node is absorbed at node j.
2.2 OFFLINE PROBLEM: MINIMIZATION OF POLARIZATION AND DISAGREEMENT
The FJ model admits rich family of quadratic functionals that capture different aspects of the equilibrium opinion landscape. These quantities are not independent but are coupled by a fundamental conservation law (Chen al., 2018): minimizing one measure (e.g., disagreement) may inherently increase another (e.g., polarization), and vice versa.
In this work, focus Definition (Polarization at equilibrium). Given an equilibrium vector zt E R/V,, the polarization is defined as the variance of opinions around their mean.
central metries.
P( =
> (2) - U2-)
(2)
iEV
where Uzz- Vi Eiev 27
3

---

Published as a conference paper at ICLR 2026
Assumption (Innate opinions mean-centered), We assume that the innate opinions centered:
Σ =
This assumption does not restrict generality; it simply removes global offset and sets the reference point of opinions to zero. As shown in prior work (Musco al., 2018), mean-centering standard in the literature and does not affect polarization, disagreement, the FJ equilibrium. It also implies that the equilibrium mean zero, allowing polarization to simplify to P(z", ;)) = |
Definition (Disagreement equilibrium). Given an equilibrium vector z", the disagreement (also called external conflict) is:
D E wislz] - ===)²=(22)) Lz*. -2² (iJ)EE
Polarization captures global opinion variance, while disagreement quantifies local tensions among socially connected agents. Together, they provide a comprehensive view of opinion fragmentation and are widely adopted in the literature (Musco et al., 2018; Wang & Kleinberg, 2023; Zhu et al., 2021).
Recalling that the equilibrium opinion vector =² depends only the innate opinions and the Laplacian L via Eq. (I), one obtains the following:
Observation (Polarization plus disagreement for undirected graphs). For any mean-centered innate opinion vector 8, the sum of polarization and disagreement can be wrillen as
f(s, L) S L)
This follows from summing Eq. (2) and Eq. (3), i.e., f(s, L)
= =)
(1+
L) 8, which corresponds exactly to the decomposition into polarization and disagreement.
The canonical offline problem is to minimize Eq. (4) with respect to over the set of admissible Laplacians. Prior work observed that the function f(L) s (I L) is matrix-conver whenever belongs to convex subset of Laplacians (Nordström, 2011).
Rather than assuming prior knowledge of the innate opinions required for the one-shot offline optimization above, we adopt an online learning framework in which the optimal intervention is discovered through sequential interaction. We focus on online regret minimization rather than Best Arm Identification (BAI) or batched updates because interventions on platforms occur sequentially, and each action has immediate impact. Minimizing cumulative regret therefore captures the cost of suboptimal interventions, aligning with how recommender systems operate in practice. BAI or batched formulations are potential alternatives, but they assume exploration has no interim effect.
PROBLEM FORMULATION
We now formalize the problem of minimizing polarization and disagreement in an online framework, where a learner sequentially intervenes on the network and, without access to innate opinions observes only noisy losses, i.e., noisy evaluation of polarization and disagreement. We cast the task as stochastic low-rank matrix bandit problem.
Online Learning Protocol. Let L (L1, L Lx) be the intervention space, finite set of admissible graph Laplacians representing possible network structures. Each intervention L E L uniquely determines equilibrium via forest matrix X (I+L) We therefore define the action space for our bandit algorithm as
X [X, -
L, E C).
By expressing the objective in Eq. (4) with the forest matrix X = (I+L)-1 and O = s8 we formulate it fXX) (0*, x), where (..) denotes the trace inner product. Since e is rank-one the problem reduces to a low-rank matrix bandit. The online learning protocol proceeds in rounds i 1,..., T as follows:
4

---

Published as a conference paper at ICLR 2026
The learner selects an intervention L, L, equivalently action X, X. Under the FJ dynamics, the system converges to equilibrium. and the learner incurs the loss f(X:).
The learner observes bandit feedback in the form of noisy loss signal: IR, where 1/- [(0, r²). ). No information is revealed about the losses of other actions. For simplicity, we focus on the case where
f(X,) + 7)
the theoretical analysis.
Objective and Regret. The learner's goal is minimize the cumulative regret, defined as the difference between the cumulative loss of the chosen actions and that of the best fixed action X arg minxex f(X):
Ro -
An effective algorithm must ensure that the average regret vanishes as T - x0. We refer to this complete setup as Online Polarization and Disagreement Minimization (OPD-Min).
Norm Boundedness. While norm boundedness the unknown parameter and arms is standard assumption the bandit framework, a key advantage OPD-Min that these properties emerge naturally from its inherent structure of the FJ model.
Unknown parameter. Following Assumption I, the innate opinions 8 are mean-centered with entries bounded in [_,, Since O* ss" its Frobenius norm satisfies ||0||| P || [o, [V]] To ensure the learning problem is non-trivial, we assume that the innate opinions are not all zero. For instance, assuming constant fraction of agents have non-zero opinions gives lower bound of | = || _ 22(VV). This prevents the degenerate case where the objective is always zero regardless of the intervention.
Arms. Each admissible arm corresponds to matrix X = (I+L)-1 e R |VXIVV which is symmetric
positive semidefinite with cigenvalues in (0, 1]. Consequently, || 17 = EN' xx)2 < [V], where we denote the eigenvalues of matrix X by XX()), indexed in descending order such that (x) 2 Xx 2 ... (X).
4
ALGORITHM AND REGRET ANALYSIS
Our main algorithm follows an spplore-subpuuce-thrrs of the OPD-Min problem. While similar in structure to prior work in low-rank matrix bandits (Lu et al., 2021; Kang et al., 2022), we tailor it specifically to the rank-one case to obtain computational simplifications. We also introduce novel analysis to handle the specific constraints imposed by action set. The algorithm proceeds in two stages: Explore Opinion Subspace and Subspace Linear Bandit in Reduced Dimensions. Our main algorithm, OPD-MMn-EESTR summarized in Algorithm 1.
paradigm, adapted to the unique structure
4.1 STAGE 1: EXPLORE OPINION SURSPACE
The initial Ti rounds are dedicated to an exploration phase designed to learn the low -ww-dmmnniiona subspace containing the true parameter matrix O' s8* T. To achieve this, we employ an estima- tor based on nuclear-norm regularized least-squares a technique whose theoretical properties are thoroughly analyzed in Wainwright (2019):
T [X, 0))² + Az O nuc
E arg
min IERIVIXIVI
Σ (Y: NX,-
(5)
27:
where X7, is the regularization parameter, which will be specified later. Here is the nuclear norm, where (,(@) is the i-th singular value.
||] |
(9))
key challenge, however, distinguishes our setting from conventional low-rank bandit problems (Lu et al., 2021; Kang et al., 2022). The action set X is composed of forest matrices, which are highly structured and do not allow the random sampling strategies (e.g.. from Gaussian distribution) commonly used in existing analyses that guarantee sufficient exploration. To overcome this limitation. we provide a novel theoretical analysis that explicitly leverages the Restricted Strong Convexity (RSC) condition for our specific set of structured actions. This analysis allows to establish
5

---

Published as a conference paper at ICLR 2026
Algorithm 1: Eiplore-Suhsaae--Teeeeeeie for OPD-Min (OPD-
Input:
Fixed arm set X' = (X, X, = (I + ,
b E C}, total rounds T', exploration length
Ti. regularization parameter ÅT;
Stage 1: Explore Opinion Subspace
for f = Ti do
Pull arm X E X' (c.g., uniformly at random);
Observe the noisy loss Y; fX,)) + T
end
Solve nuclear-norm penalized least-squares problem:
Ti
= arg min GERIVIXIE VIXIVI
Σ 1=1
(Y, (X,, (X,, + An | luu
27
Compute the top eigenvector & of θ;
Extend & to its orthonormal basis: $ [8, S RIVIIII
Stage 2: Dimensionality Reduction and Subspace Linear Bandit
for X E X do
Rotate each arm: X' == o $.]
X s
S.]:
Form reduced vectorized arm:
x' == vec (X1,)) U Vec(X v1.1 U vee(Xi R
end
Define reduced arm set Xsu == f x'k} R2M-- for / Ti + to 7 do
Select x E Nsub using any linear bandit algorithm with dimension 2 - 1; Play the original arm X, E X' that corresponds to æ/;;
Observe the noisy loss Y;;
Update bandit algorithm with (ar; Ye)
end
high-probabiln bound on the estimation error | O'||,, where the number parameters |V|2 can exceed the number of samples Ti.
As detailed by Wainwright (2019) (e.g., Chapter 9.3.1). the RSC condition requires the loss function to have sufficient curvature only over restricted subset of directions relevant to the true, structured parameter. For our problem, where the loss function quadratic, the RSC condition defined directly on the design operator. Let 1 Th X be the sequence forest matrices selected during the Ti exploration rounds. We define the linear observation operator ΦT, : RIVIx|VI + R by its action on any matrix A [ For each E T1, the t-th entry of the Ti "1-dimensional vector 2r, is
( (A) == (X,, A)
where [.]c denotes the (-th coordinate. With this operator, the RSC condition is stated as follows.
Assumption (RSC for Forest Matrix Sampling). The operator 4r, satisfies the RSC condition if
there exist a curvature constant k. and tolerance parameter oh. 2 such that the inequality
ΦT A
7 A | Puc
(6)
2T
holds for all matrices A in the set C V Here, C is the structured error set induced by muclear-norm deconposability; see Definition in Appendix B (cf. Wainwright 2019, Prop. 9.13).
Remark 1. In our setting with i.i.d. uniform draws from the fixed set X, let Kmin(X)) =
(0) 1 D (X. with K = 12 For any 8 E (0, 1), there exists a universal constant C'
inf inf

---

Published as a conference paper at ICLR 2026
O such that with probability at least 1 6, Assumption 2 holds with: k:= Kmin (2)) and T
1og(2 VD
log(1/8) Ti
See Proposition in Appendix B for precise statement and proof.
21
For A O", the term K| A Al guarantees that the loss function has strong quadratic- -ike curvature, which is essential for ensuring that the estimator θ is close the true parameter O* The tolerance term r | l allows for this strong curvature to be violated in certain directions. but only in those directions corresponding to high-rank matrices. Since our nuclear-norm penalty specifically discourages such directions, this trade-off is manageable.
We present our first theoretical result: high-probability bound on the Frobenius norm of the estimation error, which can be obtained via Proposition 10.6 in Wainwright (2019). The proof is provided in Appendix C. This proposition provides guarantee that the estimation error ||@ 1 decreases at rate of 1/Ti. This accurate estimation is the foundation upon which the efficiency of the second stage built.
ERIVIxIV] be the true rank-one parameter mairix. Fix a confidence parameter E (0, Define 3 as any solution to the nuclear-norm
Proposition (Estimation Error Bound). Let O 8s*
regularized least squares problem Eq. (5) with XT; = 2 / probability at least - 8.
11 T1
Under Assumption 2, with
- 36 log 128(2)11/8)
2 Ti
valid for 1287 K.
4.2 STAGE DIMENSIONALITY REDUCTION AND SUBSPACE LINEAR BANDIT
After the subspace estimation phase, we reduce the original matrix bandit problem into a lower- dimensional linear bandit problem using the nuclear-norm penalized estimator @. This reduction leverages the assumed rank-one structure of the unknown parameter matrix O = ss T, which implies that the signal lies the span single vector 8 E IRIV), We extract only the top singular component of θ, denoted as & e RIVI, which approximates the underlying signal direction. We extend ø to an orthonormal basis [s, S E | |x|V| to define a rotation matrix.
For each matrix arm X E X
VIXIVV we then perform the bilinear rotation:
X
$
x
$1].
Then, we discard the bottom-right block X 2,21111,. corresponding to directions orthogonal the estimated subspace. We then form reduced arm vector in 2 by concatenating the top-left scalar, the first column below the diagonal, and the first row to the right the diagonal:
X
sab X)
X 2: vI.1
1.2.v|]
We call i: 2
the projected dimension. This transformation defines fixed, low- dimensional arm set over which we can run a standard linear bandit algorithm (e.g.. (Abbasi-Yadd al., 2011; Dani et al., 2008) or see also (Lattimore & Szepesvári, 2020)) for the remaining Tr T - Ti rounds. The computational cost of computing is low, we only need the top eigenvector of a symmetric matrix, which can be obtained via the power method Lanczos iteration in time ((V))/e) for accuracy 0. This projection reduces the ambient dimension from |/|2 to ((V)), enabling faster convergence and sharper confidence bounds.
4.3 REGRET ANALYSIS
The overall regret decomposes into projection error due to misalignment of é and s, which vanishes with large T,, and the standard regret from the linear bandit phase scaling with vTz. The following theorem formalizes the resulting regret bound. The proof is provided in Appendix D.
7

---

Published as a conference paper at ICLR 2026
Theorem 4.1 (Regret Bound for OPD-Min-ESTR). Suppose the subspace linear bandit algo- rithm used in Stage 2 enjoys Hep OkvTT), where k 2 Under Assumption 2, for any failure probability å E (0,1) and an optimally chosen number of exploration rounds (Tlog(2(V1/8)) the total regret of OPD-Min-ESTTR over sufficiently large T 2 To x
T T
|
log (1)/)))) rounds satisfies, with probability least 1, 6, [
RT = max {
Vivi VIVI-T).
The regret bound Theorem confirms the statistical efficiency of OPD-Min-ESTR, The (vVT) rate of the time horizon T is optimal for stochastic bandit problems (Lattimore & Szepesvári, 2020), and the dependence on [V] instead of [V demonstrates the effectiveness the two-stage approach.
The following corollary specifies the regret bound when the algorithm's 's hyperparameter is set using more practically available lower bound, e. instead of the unknown true signal strength ||s||
Corollary (Regret Bound with a Lower Bound Signal Strength). Under the same assumptions as Theorem 1.1, suppose that the true signal strength || is unknown, but a lower bound & > 0 is
V then the known, such that || 2 l, If we set the exploration phase length Tı x ENN /T log
1
total regret RT is bounded by:
RT R
Remark 2. The curvature parameter K. in our RSC condition is set to (X). This quantity serves as a crucial measure of the diversity of the available actions strictly along the error manifold defined by the cone C. In our framework, this parameter is critical; as error bounds scale with 1/x² and the regret bound scales with 1/K, Js,00, a small k implies a weak theoretical guarantee. However, for highly structured problems such rank-one matrix recovery, this global metric can be overly pessimistic. We complement the theory with an empirical study in Appendix G.I, which shows that the effective curvature in practice can be substantially higher than the worst-case over the cone suggested by Eiinn (X).
EXPERIMENTS
In this section, we evaluate the performance of our algorithm, which integrates OFUL (Abbasi- Yadkori et al., 201 1) as the Stage-2 optimizer in a (2]V)- -dimensional subspace. The benchmarks consist of: (i) a nigh-dimensional OFUL baseline that operates directly in the dimmeninnli space, and (ii) oracle subspace variant that has access to the true subspace O and thus provides natural lower bound on the regret achievable during the exploration phase.
All experiments follow the online protocol described in Section 3. At each round t, the learner selects an arm X, from a finite set and observes the noisy scalar loss Y, = (X,, θ*) ) + T), where measured
N (O, ). ) The objective is to minimize cumulative polarization-plut in terms of regret relative to the best fixed arm in hindsight. We first report results in a controlled low-
rank bandit environment, consistent with prior works (Lu al., 2021; Kang et al., 2022). Additional experiments on real-worke networks, scalability, and sensitivity are provided in Appendix G.
Experimental Setup. We consider | E {10, 100, 1000} candidate arms. Each arm is constructed by perturbing a fixed undirected Laplacian L with [V] random rank-one updates, generalizing the construction of (Zhu al., 2021); and each perturbation weight is sampled uniformly from [0.5. 1.5]. This produces a low-diversity action space, corresponding to a worst-case setting for our algorithm.
The innate opinion vector sampled uniformly from [-1, 1] and then mean- centeceeteeeed, following standard practice (Musco et al., 2018). Environment noise is set on {0.01, 0.1. 1.0). We fix the confidence parameter to 0.001 and the OFUL regularization to À = 0.1. The time horizon is T 10,000, with our algorithm allocating Ti = /T rounds to subspace exploration and T2 = T-Ti rounds to projected OF UL. By contrast, the dinee-iimnsional OF baseline uses the entire horizon. Each experiment is repeated over 100 independent runs. We report mean cumulative regret with one standard deviation, together with average runtime.
8

---

Published as a conference paper at ICLR 2026
1,500
6,000
Suluppace
Gure (3]V) 13 p0.621 63c
Ours (2[V) (14 83.2..00
Cumulative Rogret
(PPT>
Cumuuative Regret
(VT))
1,200
4,500
900
3,000
600
1,500
300
0
0
2,000
4,000
6,000
8,000
10,000
0
2,000
4,000
6,000
8,000
10,000
Iterations
Ierations
1,500
Oraclo
Ours (2[V) 2.744
OFUL
4,000
OOaccle Subepace OPUL
Ours (2[M) 1) 24.76x11008)
Cumulative Regret
1,200
(PVP) [16.4833
Cumulstive Regret
OKUL (IVF) (78.0744.
3,200
900
2,400
1,600
300
800
0
0
2,000
4,000
6,000
8,000
10,000
2,000
1,000
6,000
8,000
10,000
Iterations
Iserations
Figure 1: Cumulative regret for Erdös-Rény' graphs (top) and homophilic Stochastic Block Model graphs (bottom) with V/ {8, 16]. Runtime (mean + std) over 100 repetitions is reported in the legend. For ER graphs the edge probability is p 0.2. For SBM graphs, two communities are generated with sizes [V] ss 0.75 [V2] = |V| [V intra-community edge probability p = 0.5, and inter-community probability p = 0.07.
Results. Figure compares OPD-Min, full-dimensional CFUL, and the subspace oracle. Across both network models and sizes ([V = 8, 16), OPD-Min consistently achieves lower regret and faster runtime than OFUL. At [ = 16, the differences become particularly pronounced: OFUL suffers both substantially higher regret and significantly slower execution. In contrast, OPD-Min closely tracks the oracle baseline, effectively closing the initial gap due to subspace estimation. These results demonstrate that exploiting the low-rank structure of O" yields substantial improvements in both sample efficiency and computational efficiency.
Additional Experiments. Further results are provided in the appendix and demonstrate: (i) empirical lower bounds for the restricted strong convexity (RSC) condition (Sec. G): (ii) scalability to large graphs with up to V 1024 nodes (Sec. G.2); (iii) applications to real-world graphs, including Florentine families, Davis Southern women, Karate club, and Les Misérables (Sec. G.4); and (iv) robustness through sensitivity analyses on noise levels and the number arms (Sec. G.5).
CONCLUSION
We introduced the first formalization of minimizing polarization and disagreement in the Fried- kin-Johnsen model under incomplete information in an online setting. This setting naturally mirrors the continuous interventions observed on real platforms and the dynamic nature of opinion formation.
We cast the problem as regret minimization in stochastic low-rank matrix bandits, where after each intervention the opinion dynamies allowed converge equilibrium, and the learner observes only a scalar feedback corresponding to the resulting polarization and disagreement. Throughout the process, the innate opinions of agents remain unknown. To address this, we proposed the novel two-stage algorithm OPD-Min-ESTT first estimating the latent subspace, then running a linear bandit method in a compact 2 dimensional representation derived from the estimate.
By leveraging structural properties of opinion dynamics and tools from matrix analysis and bandit op- timization, proved that the algorithm achieves Ö((V)VT regret under mild diversity assumptions of feasible interventions. Experiments on synthetic and real graphs confirmed both the statistical and computational benefits of our approach over full-dimensiona. baselines.

---

Published as a conference paper at ICLR 2026
This work opens several promising directions for future work. On the theoretical side, developing problem-speciffe notions of curvature could sharpen our guarantees. Our analysis relies on a global RSC condition which, though sufficient, may be overly conservative in the rank-one setting. Exploring effective curvature localized to the relevant error manifold could yield tighter guarantees even when the global curvature Kinin (X') is small. On the empirical side, natural next step is apply the framework to real-world opinion dynamics, leveraging observational or intervention data from online platforms to capture the complexities of agent behavior and feedback. Moreover, moving beyond scalar equilibrium feedback to richer but noisy signals (e.g., community-leeel polarization) could further bridge the gap between theoretical analysis and practical deployment.
ACKNOWLEDGMENTS
This work is partially supported by Japan Science and Technology Agency (JST) Strategic Basic Research Programs PRESTO "R&D Process Innovation by Al and Roboties: Technical Foundations and Practical Applications" grant number JPMJPR24T2.
REPRODUCIBILITY STATEMENT
All theorems and lemmas are stated under consistent notation in Sec. 4, and complete proofs are provided in the appendix. particular, Sec. establishes the restricted strong convexity (RSC) conditions, Sec. C derives the estimation error bound for the unknown parameter in Stage 1, and Sec. D presents the main regret analysis. The proposed algorithm described Alg. 1, and the im- plementation is available at https: //gittui com/ htt////eeeeeininieeeeeeeeeeeeeee code overview is provided in Sec. E.1. For empirical evaluation, Sec. E.2 details the experimental setup, including parameters and datasets (all publicly available), and Sec. F provides additional details on the benchmark algorithms.
oonline- -ii---n--- min-pol.
ETHICS STATEMENT
Societal Impact. This work develops framework for designing interventions aimed at reducing opinion polarization in online social networks. The intended beneficiaries are platform users and society at large, as mitigating extreme fragmentation can support more constructive dialogue, improve information flow, and reduce the likelihood of harmful echo chambers. By grounding the analysis in rell-established poinin-ddnamiie model, the approach provides transparent mechanism for understanding how small structural changes in a network can influence collective outcomes.
Potential Misuse and Risks. Despite its positive intent, any methodology that models or modifies opinions carries inherent risks. One potential misuse the deployment of such tools to intentionally increase polarization, manipulate user beliefs, disproportionately influence specific demographic groups. Mathematically, the same optimization framework could be applied to maximize polarization simply by changing the sign of the objective. However, doing so would require privileged access platform-level controls (c.g., recommendation, exposure, or graph interventions), which are typically restricted platform operators rather than arbitrary malicious actors.
Our formulation assumes that agents' innate opinions are unknown and never directly observed; the learner only receives scalar feedback, corresponding the global plarization-plus-diagreeee value at equilibrium. Thus, the framework does not rely on individual-leve opinion estimation, but instead on aggregated network-level outcomes. Nevertheless, repeated interventions that affect exposure patterns can still have normative implications (e.g., shaping which content or connections are promoted), and such decisions should be subject to appropriate ethical and governance safeguards.
Beneficiaries vs. Risks. The primary beneficiaries of responsible use are online communities where reduced polarization leads to healthier discourse, more diverse exposure, and improved collective decision-making The main risks arise if interventions are applied without transparency or accountability, potentially impacting user autonomy or systematically affecting certain groups more than others. These risks highlight the need for careful oversight: any real-worle deployment should comply with regulatory standards, respect user rights, and be designed with fairness and explainability in mind.
10

---

Published as a conference paper at ICLR 2026
REFERENCES
Yasin Abhasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Proc. NIPS. pp. 2312-2320, 2011.
Pablo Barberá. Social Media, Echo Chambers, and Political Polarization, pp. 34-55. SSRC Anxieties of Democracy. Cambridge University Press, 2020.
David Bindel, Jon Kleinberg, and Sigal Oren. How bad is forming your own opinion? Games and Economic Behavior, 92:248-265, 2015.
Ronald I.. Breiger and Philippa E. Pattison. Cumulated social roles: The duality of persons and their algebras. Social Networks, 8(3):215-256 1986.
Meher Chaitanya, Adarsh Barik, and Jean Honorio. An SDP formulation for minimizing p-th order controversy with unknown initial opinions. In Proc. Complex Networks, pp. 293-304, 2024.
Pavel Chebotarev and Rafig Agaev. Forest matrices around the Laplacian matrix. Linear Algebra and 2002.
Its Applications,
Xi Chen, Jefrey Lijffijt, and Tijl De Bie. Quantifying and minimizing risk of conflict in social networks. In Proc. KDDD, pp. 1197-1205, 2018.
Federico Cinus, Aristides Gionis, and Francesco Bonchi. Rebalancing social feed minimize polarization and disagreement. In Proc. CIKM, pp. 369-378, 2023.
Federico Cinus, Atsushi Miyauchi, Yuko Kuroki, and Francesco Bonchi. Minimizing polarization and disagreement in the friedkin-johnsen model with unknown innate opinions. In Proc. IJCAI, pp. 7365-7373, 2025.
Varsha Dani, Thomas Hayes, and Sham M. Kakade. Stochastic linear optimization under bandit feedback. In Proc. COLT, pp. 355-366, 2008
Allison Davis, Burleigh B. Gardner, Mary R. Gardner, and W. Lloyd Warner. Deep South: A Soccological Anthropological Study of Caste and Class. University of Chicago Press, 1941.
J. Douglas Faires and Richard L. Burden. Numerical Analysis. Nelson Education, 9th edition, 2015.
Noah E. Friedkin and Eugene C. Johnsen. Social influence and opinions. Journal of Mathematical Sociology, 15(3-4):193-206 1990.
Baihe Huang, Kaixuan Huang, Sham M. Kakade, Jason D. Lee, Qi Lei, Runzhe Wang, and Jiaqi Yang. Optimal gradient- based algorithms for non-concave bandit optimization. In Proc. NeurIPS, pp. 29101-291191 15, 2021.
Kyoungseok Jang, Kwang-Sung Jun, Se- Young Yun, and Wanmo Kang. Improved regret bounds of bilinear bandits using action space analysis. Proc. ICML, pp. 4744-4754, 2021.
Kyoungseok Jang, Chicheng Zhang, and Kwang-Sung Jun. Efficient low-rank matrix estimation, experimental design, and arm-set-depenndet low-rank bandits. In Proc. ICML, pp. 21329 21372, 2024.
Kwang-Sung Jun, Rebecca Willett, Stephen Wright, and Robert Nowak. Bilinear bandits with low-rank structure. In Proc. ICML., pp. 3163-3172, 2019.
Yue Kang, Cho-Jui Hsieh, and Thomas Chun Man Lee. Efficient frameworks for generalized low-rank matrix bandit problems. In Proc. NeurIPS, pp. 19971-19983, 2022.
Yue Kang, Cho-Jui Hsieh, and Thomas Lee. Low-rank matrix bandits with heavy-tailed rewards. In Proc. UAI, pp. 1863-1889, 2024.
Sumeet Katariya, Branislav Kveton, Csaba Szepesvari, Claire Vernade, and Zheng Wen. Stochastic rank-1 bandits. Proc. AISTATS, pp. 392 401, 2017.
Donald E. Knuth. The Stanford GraphBase: A Platform for Combinatorial Computing. ACM Press New York, 1993.
11

---

Published as a conference paper at ICLR 2026
Marino Kühne, Panagiotis D Grontas, Giulia De Pasquale, Giuseppe Belgioioso, Florian Dörfeer, and John Lygeros. Optimizing social network interventions via hypergradient- based recommender system design. In Proc. ICML, 2025.
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Junghyun Lee, Kyoungseok Jang, Milan Vojnović, Kwang-Sung Jun, and Se-Young Yun. GL- LowPopArt: A nearly instance-wise minimax-optimal estimator for generalized low-rank trace regression. In Proc. AISTATS, 2026.
Yilu Liu, Xi Lin, and Qingfu Zhang. Leader-follower disagreement minimization in social networks. IEEE Transactions on Evolutionary Computation, pp. 1-1, 2025.
Yangyi Lu, Amirhossein Meisami, and Ambuj Tewari. Low-rank generalized linear bandit problems. In Proc. AISTATS, pp. 460-468. PMLR, 2021.
Antonis Matakos, Evimaria Terzi, and Panayiotis Tsaparas. Measuring and moderating opinion polarization in social networks. Data Mining and Knowledge Discovery, 0004480055,,,, 2017.
Cameron Musco, Christopher Musco, and Charalampos E Tsourakakis. Minimizing polarization and disagreement in social networks. In Proc. The Web Conference, pp. 369-378, 2018.
Stefan Neumann, Yinhao Dong, and Pan Peng, Sublincar-time opinion estimation in the Friedkin- Johnsen model. In Proc. The Web Conference, pp. 2563-2571, 2024.
Kenneth Nordström. Convexity of the inverse and Coore-Penrosee inverse. Linear Algebra and Its Applications, 434(6):1489-1511 2011.
Jaume Ojer, Michele Starnini, and Romualdo Pastor-Satorral Social network heterogeneity promotes depolarization multidimensional correlated opinions. Physical Review Research, 7(1):013207, 2025.
Dragos Ristache, Fabian Spach, and Charalampos E. Tsourakakis. Wiser than the wisest of crowds: The Asch effect and polarization revisited. In Proc. ECML PKDD, pp. 440-458, 2024.
Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics, 12(4):399-434, 2012.
Sijing Tu, Cigdem Aslay, and Aristides Gionis. Co-exposure maximization in online social networks.
In Proc. NeurIPS, pp. 3232-3243, 2020.
Martin J. Wainwright. High- lige-Dimensional Statisties: A Non-Asymptotic Viewpoint, volume 48 of Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
Yanbang Wang and Jon Kleinberg. On the relationship between relevance and conflict in online social link recommendations. In Proc. NeurIPS, pp. 36708-36725, 2023.
Yao Wang, Jiannan Li, Yue Kang, Shanxing Gao, and Zhenxin Xiao. Generalized low-rank matrix contextual bandits with graph information. arXiv preprint arXiv:2507.17525 2025.
Wanyue Xu and Zhongzhi Zhang. Minimizing polarization in noisy leader-follower opinion dynamics. In Proc. CIKM, pp. 2865. 2023.
Qianxin Yi, Yiyang Yang, Shaojie Tang, Jiapeng Liu, and Yao Wang. Effective generalized low-rank tensor contextual bandits. IEEE Transactions on Knowledge and Data Engineering, 36:8051-8000 2024.
Yi Yu, Tengyao Wang, and Richard J. Samworth. A useful variant of the Davis -ahan theorem for statisticians. Biometrika, 102(2):315-333, 2015.
Wayne W. Zachary, An information flow model for conflict and fission in small groups. Journal of Anthropological Research, 33(4):452-473, 1977.
Liwang Zhu, Qi Bao, and Zhongzhi Zhang. Minimizing polarization and disagreement in social
networks via link recommendation. In Proc. NeurlPS, pp. 2072-2084, 2021.
12

---

Published as a conference paper at ICLR 2026
Appendix
A Comparison with Existing Linear or Low Rank Matrix Bandits
14
RSC Condition
15
B.1 Preliminaries
15
B.2 Auxiliary results
16
B.3 Proposition 5 and Its Proof
17
Proof of Proposition
19
C.I Auxiliary Results
19
C.2 Proof of Proposition
20
Proof of Theorem 4.1
21
D.I Auxiliary Results
21
D.2 Proof of Theorem 4.1
21
D.3 Proof of Corollary
24
Implementation Details
25
E.1 Code and Reproducibility
25
E.2
Experimental Settings
25
F
Algorithmic Details
26
F.1
Computational Complexity
26
F22
Adapting OPDMin to OFUL
26
Additional Experiments
27
G.I Empirical Validation of the RSC Parameters
27
G.2 Scalability...
27
G.3 Experiments under Polarized Opinion Distributions
28
G.4 Results on Real- World Networks
28
G.5 Sensitivity Analysis
29
G.6 Comparison with the Offline Baseline
30
13

---

Published as a conference paper at ICLR 2026
A COMPARISON WITH EXISTING LINEAR OR Low RANK MATRIX BANDITS
To address our formulation, one might consider adapting standard handit frameworks (Lattimore & Szepesvári, 2020). A naive approach is linearize the objective by treating it as inner product in an Iime-dimeniion space, i.e., vec( (88 ) vec(X), where 8 is the innate opinions vector and X is a matrix determined by the intervention. This reduces the problem to a linear bandit (e.g., (Abbasi- Yadkori et al., 2011)), but the cost of a prohibitive regret bound of Ó(VI3VT) rendering impractical even for small networks.
An alternative, seemingly more suitable approach would be leverage low-rank matrix bandits, as the unknown parameter matrix ss is inherently rank-one. A broad line of work studies bandit and estimation problems under low-rank strueture (Katariya et al., 2017; Jun et al., 2019; Huang et al., 2021; Jang et al., 2021; Lu et al.. 2021; Kang et al., 2022; Jang et al., 2024; Kang et al., 2024; Yi et al., 2024; Wang et al., 2025). All of them share the principle that large parameter matrix can be effectively approximated by low-rank representation, enabling sample efficiency and computational tractability.
(ESTR) type algorithm belongs to a successful line of research on efficient low-rank matrix bandits, drawing inspiration from seminal works such as Jun al. (2019); Lu et al. (2021); Kang al. (2022); Jang et al. (2024). All these works share common high-level strategy: an initial exploration phase to estimate the latent low-rank subspace, followed by an exploitation phase that leverages this structure solve a lower-dimensional bandit problem such as OFUL (Abbasi-Yane Yadkori et al., 2011) 1). The first ESTR algorithm by Jun et al. (2019) 9) was designed for bilinear bandits where arms are rank-one matrices: the learner chooses a pair of arms, each from two different action spaces of dimension d1 and d2.
Our two-stage,
Our algorithm built upon efficient low-rank matrix bandits, most notably the LowESTR algorithm of Lu et al. (2021). LowESTR first performs an exploration phase using nuclear norm regularization to recover a low-rank structure, and then runs a linear bandit algorithm restricted to the estimated subspace. Kang et al. (2022) present frameworks (G-EST,, G-ESTS) that extend low-rank matrix bandits to generalized linear models, which use Stein's 's method for matrix estimation during the exploration phase, followed by refinement phase that runs a linear bandit in a reduced-dimensionn
space. They provide regret bounds of order ((v(d, dz 3TT D,) for the general rank matrix of dimensions d, and dz. where D, is the r-th largest singular value for the true matrix O". Jang et al. (2024) propose LowPopArt for low-rank trace regression with experimental designs, and its arm set geometry-adaptive bandit algorithms LPA-ETC and LPA-ESTR using LowPopArt
However, these existing works cannot be applied directly to our problem, where the action set X consists of highly structured forest matrices derived from graph Laplacians. In Lu et al. (2021); Kang et al. (2022), they posit the existence of a nice exploration distribution over the arm set that ensures sufficient exploration (e.g., Assumption 2 in (Lu et al., 2021)). Specifically, Lu et al. (2021) assume the existence of an exploration distribution D over the action set X, whose covariance has Amin(E) 2 d2) and is sub-Gaussian. This assumption naturally holds when conv(X)) contains a ball of radius = (11), e.g., in continuous and isotropic settings. In contrast, our setting involves finite and highly structured action set (forest matrices), where such distribution is not available. Recent work, such as LowPopArt by Jang et al. (2024), develops a theoretical framework applicable to general arm sets via optimal experimental design. More recently, Lee et al. (2026) extended this framework to generalized linear models. However, these approaches require constructing and inverting covariance matrix in the vectorized space of dimension IV 2 x V As a consequence, forming the corresponding estimator entails a computational cost on the order of O(VV)) in the worst case. This scaling is prohibitive in social network settings with many agents. Also, in those works, the action space is supposed to span the full space, while our restricted actions derived from undirected graph Laplacians do not span in RR IV1, which implies we cannot rely on the existence of well-behaved exploration distribution. While one could potentially adapt these methods by restricting the design to the span of symmetric actions, developing such variant is beyond our scope.
To overcome these limitations, our work provides a novel and self-contained analysis. Instead of assuming favorable sampling properties, we directly prove that the Restricted Strong Convexity (RSC) condition holds for our specific action set under uniform sampling (see Proposition and its proof in Appendix B). This analysis validates our exploration phase without external assumptions about the
14

---

Published as a conference paper at ICLR 2026
action set structure, establishing solid foundation for using the explore-then-reene framework in online opinion dynamics.
B
RSC CONDITION
B.1 PRELIMINARIES
In order to analyze the RSC condition for our case, we follow the fundamental tools Section 10.2.1 of Wainwright (2019), which deals with the general rank case. For the special case where the true matrix is = 88 the left and right singular vector subspaces are identical: 21 = V1 span(s).
Definition (Subspaces for O* =ssJ, ). defined as follows:
For the rank-one matrix O ss the key subspaces are
The model subspace M consists of all matrices that are scalar multiples of e":
M:= A E
A = c c--8
ss' T for some scalar c R
The perturbation subspace M consists of all matrices that are orthogonal in both their row and column spaces:
M AERIVII As and A =
(8)
The decomposability subspace M (M+)+ is the set of all matrices that can be written the sum of matrix whose column space is in span(s) 8) and matrix whose row space is in span(s):
M : M
A = sa + bs for some vectors b E RVI.
(9)
The following proposition, adapted from Proposition 9.13 of Wainwright (2019) for specialization for nuclear norm regularization and our specific case, establishes that for suitable choice of the regularization parameter λT,, the estimation error vector is not arbitrary but is confined to a specific cone-like set.
Proposition (ef. Prop. 9.13 of Wainwright (2019)). Let LT, Ω + R be convex function and let the regularizer be the nuclear norm. Consider the subspace pair (M, M) over which the nuclear norm is decomposable. Then conditioned on the event
G(A = (oin=(11Vmm 1lpp
I S
An 2
(10)
any optimal solution θ yields an error vector
e that belongs to the set:
Co. = (AE A llaue I 3 M laaue + 44 [lauc]
(11)
In the well-specified case where the true parameter @" belongs to the model subspace M, the approximation error term ||0" M- llme vanishes. In this scenario, the set simplifies to the cone C, and
the error vector guaranteed to satisfy A ||nue < 3 M Ilmuc.
Recalling that an optimal solution θ symmetric, this provides a revised RSC condition.
Definition (RSC Condition Restricted the Cone). An observation operator Pr, is said to satisfy the Restricted Strong Convexity (RSC) condition if there exist curvature constant 0 and tolerance ,H 2 such that the following inequality holds,or all matrices A &eelnnging to the cone C:
Pr
Ri A
7
1
(12)
2T;
where C = (A E V
Xx
A M
Iuc
3/ Imnc)
15

---

Published as a conference paper at ICLR 2026
B.2 AUXILIARY RESULTS
We need to introduce the Talagrand concentration for empirical processes.
Proposition 3 (Theorem 3.27 of Wainwright (2019)). Consider countable class of functions
F = {fo 0 E } for all uniformly bounded by b, Lee, sups ll S b. Let = supage 1 Σ i=1 fo(X.)). Assume that for some constants o², we have supa BiJo(X)a S o² Then for all t 0, the random variable Z satisfies the upper tail bound
Tit
P (Z 2 2E|Z] + exp (-80²
800 06,2+40 4bt
Lemma (cf. Proposition. 4.11 of Wainwright (2019) ). Let F be class of functions. For an iid.
sequence (X,) the expected supremum of the centered empirical process is bounded by twice the expected supremum of the Rademacher process:
T
7
E
sup FEF
Σ
(g(x.)
((xx))Elg(X))) Elg(X)I))
S 21E
sup FEF
Eig (xx)
Ti
1=1
where ( is an ii.d. Rademacher sequence (taking values in (-1, +1} with equal probability). independent of {Xirer
Proof. Let (M be an iid. sequence of random variables, drawn from the same distribution as (2 and independent of it. As (lg((x)) (xlg((Y)] for any sample E [Ti], we have
= Ex
sup fEr
Σ
(x())) (lo(X.))) = Ex
sup FEF
(g((,) - Ey Er
==1
As sup(-) is convex function and by Jensen's 's inequality,
T
Z Ex
sup |EF
Ey
Σ
-o(X)))((Y))
-
T
1 T₁
$ Ex
sup
Σ (o(X,) -0(3a)
fEF
T
i=1
Since i.i.d. Rademacher random variables {E:)T= are independent both {X.} and (Yi), we have
1
(x((X))) (((3)
Z < Exys
sup JEF
7
Using the triangle inequality, we further obtain:
Ti
Ti Σ Es cs(- ((-( )
Z < Ex,y.
sup fEF
(X,,
Ti
Ti (Xi)
Ti
Ex,
sup
By
sup fEF
Eig(Y))
fEF
Ti
Ti
i=1
T
1
2E..
sup fEF
(xg(X,))
T
which completes the proof.
Next, we introduce the Matrix Rademacher Series.
Proposition (Theorem 4.1.1 of Tropp (2012)). Consider a finite sequence (BR} of fixed symmetric matrices with dimension d x d, and let {GA be finite sequence of independent Rademacher random
variables. Let e Σm= B [ ll.p Then, E Ex BB S /2v log(2d).
16

---

Published as a conference paper at ICLR 2026
B.3 PROPOSITION 5 AND ITS PROOF
Proposition 5 (RSC Condition for Uniform Sampling over Forest Matrices). Let the observation operator ọT, be constructed from Tí i..d. samples drawn uniformly from fixed set of measurement matrices [X;]pm] UKK. C RIVIXIVI, Then, for any failure probability ô E (0, 1), there exists universal constant O such that with probability least 1 6, the RSC condition from Definition 4 holds for all matrices A in the cone C {0}. The curvature and tolerance parameters are given by:
C
log(2[V[) Ti
log(1/1 (1/5)
= Kmin (2) and
T
where (X) == ::nnf =inf f Σ* AX)
Proof of Proposition 5. The proof is based on bounding the deviation between the sample covariance
matrix H Ti Σtn a and its expectation H = EHH, where æ, (X.)
To verify the RSC condition, evaluate the quadratic form for any matrix A within the cone C:
1
PT (A)l voc(A) A) H vec(A) = vee A "H vee( A) + (rcc(A)) (H H vec(A)
Ti
(1) Population Curvature
(II) Statistical Devistion
(13)
Using the definition of (m), for any A E C, we immediately have:
vec A
vec 2 Kimin A||
(14)
Suppose that with probability least 1 8,
1og(2|VV)
log(1/6)
vec vec(A) A) (H H) vec A)
S C C|A|
(15)
Ti
Ti
which will be proved later in Proposition 6. We substitute these bounds into Eq. (13). Then, with probability least 1 d, obtain
(VDO
Vi
log (og(1/))
PT
11
Kmin (2) |//|
||
CII
2T:
Ti
Ti
Amin (2)
C
log(2[V])
log(1/5)
A
2
Ti
Ti
mue
The last step to prove Eq. (15) is due to the following proposition, which completes the proof.
Proposition 6. Let the assumptions of Definition hold. There exists a universal constant C such that for any 8 (0, 1). the following inequality holds with probability at least 8 for all matrices A C simultaneously:
(1
1og(21V1) T
(og(1/))
(ec(A)
H vec A)
SCAA
iuc
T
17

---

Published as a conference paper at ICLR 2026
Proof of Proposition 6. For each A E C, define the zero- rea- function fA E E X, A/. For term (II) in Eq. (13), we first expand the statistical deviation term for a matrix A
(X,
v A vec(A) (H H) (e) vec(A)
1 i
(leeaT] vec(A)
T
1=1
T
((z) vec( A))² [[00 vec( vec( ())
Ti
T
Σ
(
-I(,, A)
Ti
T Ti 1=1
fx()).
Consider the normalized set C1 (A' E C A
'Ilme
1}. We aim to bound the supremum of the
empirical process using Proposition
T Σ fa (x) t=
Ze. = sup AEC
Ti
for the function class Fc, (SA A ECC.
For the maximum variance, we have supAEC, Var(/a S supaec, B[(X,, A) In our setting, recall that each matrix X, = (I+ L,) in the arm set has eigenvalues in (0, 1]. which implics |Xiilop < and |X |p S VIV.. Consider any A E C1, and let the random variable Z, == (X,, A) be drawn from the finite set { (X,, A).... (XK. A)}. Then, [Ze] is deterministically bounded as:
Zzl
X A < |Xelop || S || nuc S 1.
Iuc S 1. Thus o² = 1. We need a uniform bound on Ifa (X.) & sup (X,, A/ Again, us- ing the property of the trace inner product: [Xt, A) < || ll Illue
We use this uniform boundedness to control the fourth moment B| E|Z 271 < A
Then we have
sup Iʃa (X,)l < 2. ll S 2, meaning 2.
Next, we aim to bound
1 Ti fA
Ei = E sup AEC,
Σ Ti 1=1
Let Te be an i.i.d. Rademacher sequence. Then, we have
Ti Σ ((x))
E
sup AEC₁
2E
sup AEC,
X 1
A
T t=1
T
t=1
Ti
< 4E
sup AEC;
e (X,, A
T
Ti
< 4 A
E
X llop
nuc
T
1=1
where the first inequality is due to Lemma (Proposition 4.11 of Wainwright (2019)), the second
and third inequalities are due to the Talagrand contraction inequality and [X,,, A) S A Imue- By
Proposition 4 with e = max(1] [1 ET", X,X, Iop I Ti x, Xellop} < I X ol < Tí, we obtain
T
E
S
X
S 22 log(2d) < 2T,, log(2d).
op
18

---

Published as a conference paper at ICLR 2026
Using it, we obtain
T
Ti
1
E
sup AEC;
fa (
<
<4 nuc Ti
E
El x
llop
Ti t=1
1=1
<4 A
2T, (og(2
mic T
2
A
nue
Ti
Therefore,
2 (2)
2log(2|V]
E ElZc,] 4 |
<'1
(AV Ci).
nuc
T1
Ti
With the parameters b= 2, 0, Proposition 3 states that for any 0:
Ti
Tit²
P (ez, 2 Ze, + t)
exp (- 80 + 4bt
exp
8 8t
Setting the right-hand side to 8 implies that for universal constants C1 C2 > 0, we have S
C
(1/(1
C2
log(1/8) Thus, with probability at least 1 ò: 71
T1
2 2o + CiV
log(1/8) Ti
log(1/6)
Ze - 2c, 1 16
+ C2
(16)
Ti
Ti
Recall that the function fa is quadratic in A, meaning foa e² fa. This implies that the process v(A) follows the scaling rule v(cA) (v(()) Consequently, we can write:
A
M
|
Iuc
|
2
A Iiuuc
A
muc
Therefore, by Eq. (16), for any
A E C, with probability at least
8:
(
(Voster)
[og(2|V1)
(og(1/5)
M (A) < A 2 Ze, C
C|||| Iucc
Ti
Ti
where we have absorbed all numerical constants and the less dominant square-root term into single universal constant C. This completes the proof.
C PROOF OF PROPOSITION 1
C. AUXILIARY RESULTS
We state Proposition 10.6 in Wainwright (2019) when adapted for our exploration phase with length Ti in Algorithm 1 for the rank-one case.
Proposition 7 (Adaptation of Proposition 10.6 in Wainwright (2019)). Suppose that the observation
operator DT,, satisfies the RSC condition in Assumption with k > 0, and 7 2 0:
-1
A
A E C)
(17)
2T
Then conditioned on the event g(\1;) )
<
An
any nuclear-norm regular-
ized least squares estimator in Eq. (5) satisfies the bound
19

---

Published as a conference paper at ICLR 2026
9 1 | 1 S
2 x2
valid for 128777 S ni
Next, we introduce the following concentration inequality.
Theorem C.1 (Matrix Gaussian Series Concentration (Tropp, 2012, Theorem 1.2)). Let {Aa} be a finite sequence of fixed, self-adjoint matrices in IRIV [ and let { be independent standard normal or Rademacher random variables. Then. for all 2 0.
P Amax Σ ESNAR 2
[ exp
82
where o² ==
Σ k
A
2
op
C.2 PROOF PROPOSITION
Proof. Proposition 7 conditions the analysis on the event 9(
11
{
+ Σ
7
op
which bounds the empirical gradient at the truth in the dual norm. The noise term is small relative to the penalty, so the random cross term is dominated and the estimation error stays in a low-rank cone. We show that this event occurs with high probability.
We standard matrix concentration result from Theorem C.1 to the Gaussian series Σ/=1 A Σ>
where o²
T
A
and T/s ~N 1) are independent, we have that for all / 2 0,
T's Σ
12
IP
Amax
A;
2
V
exp
(18)
2x
1=1
Recall that for any matrix A > the operator norm satisfies:
|| = || = Amax (A),
where I1-112 is the spectral norm, and Amax (A) is the largest eigenvalue of A. These quantities coincide for symmetric matrices, since their singular values equal the absolute values of their eigenvalues. In our setting, each matrix X, [[V]x[VI is symmetric and defined
X, = (I L,)
where L; ž is positive semidefinite matrix (e.g., graph Laplacian). Because the eigenvalues of L, are nonnegative, the eigenvalues of X, lie in the interval (0, 1). In particular, have:
Amax (X.) 1
$ 1. Amin (L,)
Therefore,
X ol Amax (X,) S
for all X; E X.
Define the scaled matrices A; 1 Xx Since
Ti
T
T
Σ
2
X
2 op
<
=
=T,
up
1=1
we have
T
1
2
<
T
Ti
op
op
Given the above bound
>
Ti (-)
A
< T,
setting t
(2
is sufficient to guarantee
Ti
lp
t
2
A?
log
This ensures the event in Eq. (18) occurs with a failure probability
op
20

---

Published as a conference paper at ICLR 2026
of at most 8, since
T 2
V
t²
N
A lp
log
|V|
exp
S
8..
2
Σ Ti 1==
A
i=1
By the union bound, the same result holds for the operator norn with slightly adjusted constant, ensuring that with probability at least 1 - ò:
T T
2 log (100
T₃
To satisfy the condition of Proposition 7, choose regularization parameter Ar,
(2 this gives
2v
71
Ti Σ
}
Xz;
Pr[g(An)] Pr
2 $
Ti
op
Finally, by Proposition 7, with probability at least 1
9 2 (2
(222
36 log (1))))
j 1
2 R2
2
R²
R²2 T
D PROOF OF THEOREM 4.
D.I AUXILIARY RESULTS
We introduce the ric matrices to perturbations in the matrix.
theorem, which relates the deviation between eigenspaces of symmet-
Theorem D.1 (Davis-Kahan sin 0 Theorem (Yu al., 2015, Theorem 1)). Let Σ. E Rexp be symmetric matrices. Suppose M E Roxd and M Roxd are matrices with orthonormal columns corresponding to eigenspaces of Σ and E, respectively. Let dy denote the minimum eigengap between the eigenvalues corresponding to M and the rest. Then:
Σ --E --E
|| sin 0 M,MM]|e S
D.2 PROOF OF THEOREM 4.1
Armset rotation. Recall that the ground truth matrix is O s8 where a E B| is the vector of
innate opinions. Let E TRIV denote the top eigenvector of the estimator @ in Stage 1. We complete into orthonormal basis of [V by selecting orthonormal matrix S [VIx((V1-1) such that
S
g VI is an orthogonal matrix.
That is. $1 spans the orthogonal complement of s, satisfying $ 0 and $ V----
We then rotate each arm X E into the new orthonormal basis defined by [&, S resulting in:
X 8 x
X
$1
X
$
X
S[x$_]
21

---

Published as a conference paper at ICLR 2026
Let k ; 2 1 be the projected dimension. We extract the projected feature vector Xsub R by collecting the first row and column X':
X 1,1 8 Xs
Xgubl (X) ==
X
21V1
x
1.2
X
Similarly, define the projected signal vector fuh
E R as:
8 O'8
0aub
We adapt the proof strategy of Theorem 4.3 in Kang et al. (2022) to our OPD-Min-ESTR algorithm under rank-one signal assumption.
arg minxex X, Ar) be the optimal arm and X E X' be the arm selected by the learner at time t E [T2] during the State 2. We write zub = sub (X*) and su (X,). The instantaneous regret is:
The instantaneous regret in Stage 2. Let X*
θ-) (X, O*).
We decompose this regret as:
Tr X -
(xt Sub O (ubb + (xx
Tt sub. (ub)
t Oubb
(X,, θa)
(A) projection error for X-
(B) regret within subsgace
(C) projection error for X,
Term (A) and (C) represent the approximation while term (B) is the regret of the low-dimensional linear bandit problem.
due to the projection into the estimated subspace,
We bound the projection errors, terms (A) and (C), denoted by r! ((X* O*) (cr 0%b) + ((Fr, 0% suh
(X,,
As the only component not captured in the subspace representation lies in the orthogonal complement S1, the projection error for X can be written solely in terms of the orthogonal complement subspace:
X, @*)
(X), ) = [S[x$1, S
The total projection error can thus be expressed as:
pmuj
S
S
Applying Cauchy-Sch inequality (4, < |||| B|| for each term gives:
( < X S || TT
($ [ < s |r S |n..
We write maxx |X| ||r S Sx for some constant Sx > 0. Since orthogonal projection cannot
increase the Frobenius norm | x$ || <
| F < Sx for any X, we have
proj
(ISIXX (|Ix,_111)
S |rr 25x ||_ers
Using O = 88 we have:
S
T ||| ([S (s
)lr |
The above analysis concludes that
pro < 25x SSSx|SST $1
(19)
22

---

Published as a conference paper at ICLR 2026
Now, aim to establish explicit relation between S s|| and the angle between the vectors and 8. in order to apply the Davis Davis-Kahan Kahan sin & theorem. To proceed, we decompose into a component aligned with s and a residual orthogonal component:
Str.
where TT S.
Projecting onto the orthogonal complement:
S = SIr
|S s|| = ||-||
Using the Pythagorean theorem:
(8, 8)
(s. 8)2 ||
|||| = ||$||2
= ||$|
||
Recalling that
(s. 8)
cos(O)
|||||
we obtain:
||r||² = ||s||2(1 cos² 0) = =|<011- sin? 0.
Therefore, conclude:
| s|| = ||||| sin
In our setting, we apply Theorem D.1 with - and Σ ê. Since O = ss is rank-one, its top eigenspace is spanned by 8, and the orthogonal complement corresponds to S Its largest eigenvalue X A1(@% (@*) Amax (@*) || and all other eigenvalues are zero. Therefore, the
eigengap for the top eigenspace of the true matrix O" is 6M (0)) - (e |s||
Thus, we obtain:
|6
O
0
S s|| =
||||| sin(O) I
||||||
|
s
Substituting this inequality into Eq. (19) yields:
1 O |F
proj < 2Sx
|||||
From Theorem 1, with probability least 1- 5,
36 log 1/8)
R² Ti
Thus, the instantaneous projection error bounded as:
(2
p < 72Sx
(20)
|s 1s
Final regret bound. We now incorporate the remaining components of the regret.
During the initial exploration phase = 1,..., Ti, we incur the linear regret, so we conservatively bound the cumulative regret by applying Cauchy-Schwarz:
X θ*) X., θ*) < X X.I x < 28x ||s|
Thus, the exploration cost bounded as:
7
r1 < 2T -xx ||
t=1
23

---

Published as a conference paper at ICLR 2026
We denote the cumulative regret incurred the linear bandit algorithm (e.g.. OFUL (Abbasi- Yadkori et al., 201 1)) is RT OkkTT), where 2/ - is the subspace dimension. Combining all terms, the total regret is:
T
T
RT
Tt
+
Tb
1=1
Am T1+1
Ti
Σ
Tt
+
proj
+ RT
1=1++1
log(2 (1 2x
2T: Sx +
T+
ck)VT
(21)
exploration cost
in-subspace lincar regret
bias due to misalignment
where used Eq. (20) and c(k) is the constant term dependent on arm size ls in Ryp.. When set T 0 [.|..//Tii log /0),, this gives:
RT O Sx T (log(VV1/))+
Since each matrix X (I L) E IR in (0, 1], we have:
[X is symmetric positive semidefinite with eigenvalues
M IV.
5 max | max
max Tr(x²)
max Σ ( S
Finally, we obtain
( 1 /T v (I+IVV)) - -0 [.vll vIMIT))
Pr -
where we used c(k) Ō(k) Ō((V)) as standard regret bound for linear bandits. From the assumption, we have K = Kmin (X'), which completes the proof.
D.3 PROOF OF COROLLARY
Proof. We have Eq. (21) with the same analysis in Theorem 4.1.
log(2)V1/6)
Rr < 2T Sx ||a||2 728x
T in subspace linear regret
(K)VT.
exploration cost
bias due misalignment
Set
V Eg K.
T
T log 8
with
|| > l..
Substituting into the above inequality gives
Po < 12 Sx || fg
V +o(k)VT
24 |
2 +c(k)VT.
+
T log
T log
[|
k
Using ||s||2 < VV. l.
=((V)), Sx S V and c(k) = Ō((V)) 1). we obtain
RT δ |V11//2 VT)
K.
24

---

Published as a conference paper at ICLR 2026
E
IMPLEMENTATION DETAILS
This section outlines the codebase and experimental settings used in our study. Additional notes on computational complexity are provided in Appendix F.I.
E.
CODE AND REPRODUCIBILITY
Code repository: https:://// whg.h.......... com/ ccmm//eeerrrccciii////oonooonnoo
The repository is organized around main src/ directory with modules for graph generation, subspace estimation, bandit optimization, and visualization. Each experimental setting can be reproduced with dedicated scripts, and all figures are automatically stored the f figures/ directory. A yaml file specifying the conda environment is provided to ensure full reproducibility.
E.2 EXPERIMENTAL SETTINGS
We summarize in Table 1 all parameters used in our experiments. The parameter grid is designed study factors that directly influence opinion dynamics, putting less emphasis on standard bandit hyperparameters, In the main text we report results for representative values near the middle of each range, while additional experiments with extreme values are deferred this appendix.
Data. Real-world graphs are taken from the NetworkX library, and all synthetic graphs can be reproduced using the provided code. No additional preprocessing was applied.
Graph models, Opinions. Arms, Noise environment, General setting, Stuge (subspace estimation), and Stage 2 (OFUL optimization).
Table 1: Overview of experimental parameters, grouped by component:
Description
Symbol Values
Graph models
Number of nodes Stochastic Block Model
V {8, 16, 32, 34, 64, 77, 256, 1024) (synthetic + real) Two-community, homophilic: |Vi x 0.75/V|, [V1] = [V| [V
Intra-community p 0.5, inter-community p 0.07
Erdös-Réóp Model
Edge probability 0.2
Opinions
Opinion vector
Unif([-1, 1]ll),, mean-centered
Arms X E (10, 100, 1000}
Number of arms Single arm generation
X V random rank-one updates of L, weight Unif[0.5, 1.5]
Noise environment
Noise variance
on {0.01, 0.1, 1.0g
General setting
Confidence parameter
5 = 0.001
Time horizon
T 10,000
Stage duration
Ti VT
Stage 2 duration
T2 = T - Ti
Stage I: Subspace estimation
Nuclear-norm weight
Amuc
VT. (log(2d/1022)
Stage 2: OFUL optimization
Regularization
A = 0.1
Arm norm bound Parameter norm bound
L [V| (conservative upper bound)
| =|V (conservative upper bound)
25

---

Published as a conference paper at ICLR 2026
F ALGORITHMIC DETAILS
In this section, we analyze the computational complexity each stage and show how OPDMin maps to the linear bandit framework of OFUL, verifying the necessary assumptions.
F.1 COMPUTATIONAL COMPLEXITY
We analyze the time and memory complexity of our Algorithm I, separating the theoretical require- ments of each stage from the properties of our current implementation and possible optimizations. Let V denote the number of nodes, T the horizon, Ti the Stage-1 budget, and X' the arm set.
Stage-1: Subspace Estimation. We solve nuclear-norm regularized problem using proximal gradient descent. Each iteration involves: (i) computing a gradient over Ti sampled arms, costing D(TiVV))) and (ii) applying singular value thresholding (SVT) step, which requires full SVD of a [V x V matrix at cost ((VV)). With K iterations, the total complexity is
OKK KT]
This complexity is inherent to the method, though in practice the SVD can be replaced with ran- domized or power methods that approximate the top singular directions, reducing the cost closer to O([V]2log [V]) per iteration.
Stage-1 1 Projection. After estimating 8, each arm X E RIVIIVV must be projected onto a basis aligned with é and reduced a (2|VI 1)-dimensional feature vector. Naively forming the rotated matrix would cost ((VV)) per arm, but by computing only the necessary bilinear forms our low- memory implementation reduces this ((V)3) operations per arm, for total time of (( [V Moreover, we never materialize full [V] x IV matrices in memory: instead, each arm is stored directly its reduced form, requiring only O(I [V]) storage overall.
Stage-2: OFUL in Reduced Dimension. Let 2 - denote the reduced dimension. Each round of OFUL requires solving for A A-1z for all arms at cost O(I-Ip²), plus updates to the design matrix A Rexp and vector b E RP, costing O4²²). Thus, the overall complexity of Stage-2 is (TT)')p))
Comparison with Standard OFUL. Running OFUL directly in the full 2 -dimensiona space would require ([2''VVV*)) operations per round and O ((V) memory, which prohibitive even for moderate [V]. By contrast, our reduction to = 2
dimensions lowers the per-round cost (Ixx') (2) and the memory usage to ((. This reduction preserves theoretical guarantees while yielding orders-of- orders-of-magnitudd magnitude improvements in both time and memory efficiency.
F.2 ADAPTING OPDMIN TO OFUL
The OFUL algorithm (Abbasi- Yadkori et al., 2011) is a standard approach for linear bandits that maintains confidence sets around the unknown parameter and plays optimistically. To apply it in our OPDMin setting, we rewrite the quadratic loss s Xs as a linear form. Let O and x vec(X), Then the loss is s Xs (X, O*) = (x, 0*). At each round f, the learner selects an arm X,, observes the noisy loss
vec(@*).
Y1- (xe, 0*) + T]t
and updates its estimate of the unknown parameter 6".
Norm bounds on actions. For x = vec(X), we have ||x||| = ||]|F. Since X = (I L) with
graph Laplacian, all eigenvalues lie in (0, 1]. Thus |||||2 I and | & VIVi. giving
||x||a S V.V.
Norm bounds on the unknown parameter. The parameter d* voc(ss with ||0 10 = |ss || = ||s| Since each s; [], we obtain ||0* S VV]
Therefore, the OFUL assumptions are satisfied with parameter norm bound S = |V| and action norm bound Tep V
26

---

Published as a conference paper at ICLR 2026
G ADDITIONAL EXPERIMENTS
In this section of the appendix, we provide extended experimental results that complement the main text. We evaluate the robustness of our method under different network models, real-world datasets, large-scale settings, and sensitivity analyses.
G.1 EMPIRICAL VALIDATION OF THE RSC PARAMETERS
The Restricted Strong Convexity (RSC) condition (Definition 4) requires that the quadratic form in Eq. (12) is uniformly bounded below across all admissible directions A E C, up to a tolerance term. Formally, balances positive curvature term with constant against an additional tolerance proportional to lluuce
For empirical validation, we focus only on the curvature component. Following standard RSC-style analysis, we empirically compute the observation operator as
min R AEC, ||
Tj | (A)
which approximates the normalized curvature across admissible directions. Although this proxy ignores the tolerance term in the formal definition, it still provides a conservative diagnostic for whether the sampled arms induce sufficient curvature to recover the low-rank structure. The unit Frobenius constraint is without loss of generality, since the quadratic form is homogeneous and depends only on the direction of A.
Computing this minimum exactly is intractable due to the high-dimensional, non-convex search space. We therefore approximate i via a projected gradient descent (PGD) heuristic. At each iteration, we normalize A to satisfy | 1, enforce cone membership, and project to rank-2 (motivated by the fact that the difference of two rank-1 matrices has rank at most 2). Multiple random restarts are used to mitigate local minima.
The resulting & only an approximate estimate of the curvature proxy defined above. Thus, & cannot be interpreted rigorous lower bound on the theoretical RSC constant from Definition 4. Instead, should be viewed as practical diagnostic: when A is reasonably large, this provides empirical evidence that the sampled arms induce sufficient curvature to make the problem well-conditioned.
Experimental setup. We compare two graph families and two arm-generation regimes. For Rrdōs-Rényi (ER) graphs
edge probability p 0.2. For Stochastic Block Model (SBM) graphs we consider a homophilic two-community structure with 75% of the nodes the first community and 25% the second, mntra-community probability p 0.5, and inter-community probability = 0.07. Arms are generated either (i) Local, by applying 2|V| random edge edits to fixed base Laplacian, or (ii) Diverse, by independently sampling fresh random Laplacians (ER for ER graphs, homophilic SBM for SBM graphs). In all cases we fix | = 100. Reported values are averaged over 25 trials. Very small estimates in the Local regime reflect nearly collinear arms, which induce weak curvature.
Table 2: Empirical values of & (mean + std) across graph families and arm regimes. See main text for detailed description graph models and arm generation procedures.
Graph
Arm regime
V 32
V = 128
V = 1024
ER
Diverse
0.393 (+0.037)
0.410 (=0.045)
0.499 (#0.039)
ER
Local
(1.68 + 0.40) x 10-5
(1.49 + 0.19) x 10-7
(2.21 + 0.00) x 10-7
SBM
Diverse
0.386 (+:0.40)
0.476 (=0.017)
0.462 (+.0.066)
SBM
Local
(2.97 0.43) 10-6
(8.05 + 0.08) x 10-7
(1.05 0.00) 10-7
G.2 SCALABILITY
To empirically assess scalability, we evaluate our algorithm on Erdös Rényi graphs with increasing node sizes, up to |V| 1024. Figure 2 reports the wall-clock time (averaged over trials) function
27

---

Published as a conference paper at ICLR 2026
of the network size. The results show near-polynomin growth consistent with complexity analysis, confirming that the algorithm remains practical for graphs of moderate size.
Our
Wall-clock time (s)
10a
OFUL
10"
10a
24
2
2
21
Number of nodes M
Figure 2: Wall-clock time of OPD-Min as a function of the number of nodes [V] on Erdös-Rényi graphs. Shaded regions indicate standard deviation across trials.
G.3 EXPERIMENTS UNDER POLARIZED OPINION DISTRIBUTIONS
To study the impact of stronger polarization, generate innate opinions using bimodal distribution that concentrates mass near the extremes - and +1. Specifically, for opinions 8; ~ ([-1 1]), we apply the transformation 5; + sign(s;) |s 1/3, which amplifies values closer to +1 while compressing those near O.
Figure shows the resulting cumulative regret curves on Erdös Erdös-Rényi graphs. We observe behavior similar to the uniform setting, with nearly identical regret curves. However, the polarized case achieves faster reduction of polarization and lower absolute regret, suggesting that interventions are easier to identify and exploit when opinions more extreme.
1,500
OFUL
Oracle Ours (8.4720.
Ouza 1) [2.41#0.10s)
5,000
Curntative Regret
1,200
(IVP) 03)
Cumulstive Regret
([V(P) 10.3130.133)
4,000
900
3,000
600
2,000
1,000
0
2,000
8,000
4,000
6,000
10,000
Iverations
Iterations
Figure 3: Cumulative regret on Rédōs-Rényi graphs with polarized innate opinions (pol = 3).
Runtime (mean + std) over 100 repetitions is reported in the legend. Edge probability is 0.2.
G.4 RESULTS ON REAL- WORLD NETWORKS
We evaluate algorithm three widely studied real-world social networks: (i) the Florentine families network Breiger & Pattison (1986), representing marriage ties among prominent families in Renaissance Florence, (ii) the Davis Southern women network Davis et al. (1941), bipartite affiliation network connecting women to the social events they attended, (iii) the Karate club net- work Zachary (1977), capturing friendships among members of university karate club, and (iv) the Les Misérables network Knuth (1993), describing co-occurrences of characters in Victor Hugo's novel. All four are standard benchmark graphs available in Networkx! Figure 4 illustrates the cumulative regret over 10,000 iterations on real-world networks, evaluated under different noise levels and action set sizes. The results highlight the robustness and efficacy of our algorithm across heterogencous real graph topologies.
hntre://neeuurrx.oooooooommeeee http:///wwwoo..eoooooooooettttt/ es/ ndex. htm!
28

---

Published as a conference paper at ICLR 2026
For all real-data experiments, generate candidate interventions using the same procedure in synthetic settings: each arm applies 2 random rank one edge updates to the base Laplacian, with additive weight offsets sampled uniformly from (0.5, 1.5).
Floreatine families, | = 10
Florentine lamilies,, [.t = 1000
Cummlative Rogret
2,000
1.0
0.01
Cumulative Regret
2,000
0.01
1.0
1,600
1,500
1,200
1,000
800
500
400
0
0
2,000
4,000
6,000
8,000
10,000
2,000
4,000
6,000
8.000
10,000
Icerations
Iterations
Davis southern women, |
Davis southern women, [xl 1000
0.01
Cutmlaatvv Regret
2,500
1.0
Cumulative Regret
2,400
2,000
1,800
1,500
1,200
1,000
500
600
2,000
4,000
6,000
8,000
10,000
2,000
4,000
6,000
8,000
10,000
Iverations
Iterations
Karate club, |x
10
Karate club, |x]] 1000
0.01
500
0.01
Cuntulativ Rogres
1.0
Cunulative Regret
400
450
300
300
200
150
100
0
2,000
4,000
6,000
8,000
10,000
2,000
4,000
6,000
8,000
10,000
Iterations
Iterations
miserables, x|
miserables, |.]
1000
Cunmlative Regret
6,000
1.0
Cumulative Regret
6,000
1.0
0.01
4,500
4,500
3,000
3,000
1,500
1,500
0
2,000
4,000
6,000
8,000
10,000
2,000
4,000 6,000
8,000 10,000
Icerations
Iterations
Figure 4: Cumulative regret 10,000 iterations four benchmark social networks (Florentine families, Davis southern women, Karate club, and Les Misérables), under two noise levels (a = 0.01 and a 1.0). The left column corresponds action size | 10, while the right column corresponds to | = 1000. Each curve shows the mean regret across runs, with shaded regions indicating 95% confidence intervals.
G.5 SENSITIVITY ANALYSIS
We conduct a series of sensitivity analyses to study the robustness of our algorithm with respect to key environment parameters.
Figure reports the cumulative regret over 10,000 iterations on real networks under varying noise levels (a 0.01 and 1.0) and action set sizes ( 10 the left, | 1,000 the right).
29

---

Published as a conference paper at ICLR 2026
Across all datasets, the cumulative regret of our method grows predictably with the horizon, with lower regret observed for smaller action sets and lower noise levels.
G.6 COMPARISON WITH THE OFFLINE BASELINE
To empirically verify that online algorithms can outperform the offline SDP baseline of Chaitanya et al. (2024)-wiich which, in our discrete setting, reduces to evaluating the objective on all arms and selecting the minimizer (Eq. 10) we run two short experiments on small graphs where exact evaluation
we
feasible. We consider: (i) stochastic block model with homophilic links, [V] = 16. T 250,
T = 50, a 10-1, X = 100, and 500 trials; and (ii) the same setting with [V] 32. For each method, we plot the minimun polarization + disagreement achieved so far function of the number of iterations (i.e., interventions). The curve for Chaitanya et al. (2024) is flat, since this offline method does not incorporate online feedback.
Minimum Objective Value
3.60
Oure [2[V) 1) (0.09=0.08.)
Oredi Sulopuee OFUL
Minimum Objective Value
3.44
Oradle Subsgsce OF (2]V 1) 10.11
3.36
3.28
3.20
3.20
3.00
3.12
2.80
3.01
50
100
150
200
250
100
150
250
Iccrations
Iterations
Figure 5: Minimum polarization + disagreement over 250 iterations (interventions) for our method, the oracle subspace OFUL, and the offline baseline. The offline baseline is flat. We also report the mean final objective values: for [V] = 32, ORACLE = 3.05 and OURS 3.09; for [V] 16. ORACLE 2.64 and OURS 2.71.
In both settings, the two online algorithms (ours and the oracle subspace OFUL) quickly drop below the offline optimum and continue to improve as additional samples are collected, demonstrating the benefit of sequential feedback. At the end of each run, we also report the mean objective of the final selected arm. These results confirm that, in this regime, online exploration yields strictly better interventions than the best offline solution.
30


Reviews:
[{"review_id": "4GSwDSNiBw", "reviewer": "Reviewer_M4wL", "summary": "This paper studies the problem of minimizing polarization and disagreement under the *Friedkin–Johnsen (FJ) opinion dynamics model* when there is incomplete information about the innate opinions. By defining actions as constructing different forest matrices $X = (I + L)^{-1}$, where $L$ is the Laplacian matrix of the graph, the authors formulate the minimization of polarization and disagreement as a multi-armed bandit problem. By sequentially intervening on the network graph, the algorithm aims to minimize the cumulative regret—the sum of expressed polarization and disagreement—over a finite horizon $T$.\n\nThe proposed method consists of two stages. Stage 1 performs uniform sampling over the action set to learn about the opinion subspace. Stage 2, using the noisy loss observations collected in Stage 1, performs dimensionality reduction and maps the linear bandit problem onto the reduced subspace. The proposed algorithm achieves a regret bound of  $\\tilde{O}(|V|\\sqrt{T})$, \nwhere $|V|$ denotes the number of nodes in the graph.\n\nThe paper further compares the proposed algorithm with two baselines:  (1) applying OFUL directly on the full high dimensional space $R^{\\mid V\\mid ^2}$; (2) the oracle case where the true subspace is known, serving as a lower bound. By learning the subspace first, the proposed algorithm achieves substantially lower regret and faster convergence compared to performing OFUL on the full space.", "questions": "1. It is not very clear why the action space is assumed to be discrete in the problem setup. By definition, the action is given as  $X_w = (I + L_w)^{-1}$, where $L_w = D - A_w$ is the Laplacian matrix of a graph. Since $A_w$ is the adjacency matrix of the graph $G$ with edge weights $w$, and these weights could form a continuous but constrained vector, it is not immediately obvious why the action space cannot be treated as continuous.\n\n2. I would recommend revising the definition in line 287 to clarify that the subscript $t$ refers to $t \\in T_1$ and that $[\\cdot]_t$ denotes an entry of the vector. This notation was somehow unclear upon first reading.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "This paper advances the study of polarization and disagreement minimization in the following ways:  (1) it assumes no prior knowledge about the innate opinion information; (2) it reformulates the minimization of polarization and disagreement under the FJ model within a multi-armed bandit framework.  The technical contribution of this paper lies in adapting previous MAB algorithms, which typically assume a continuous action space (e.g., Gaussian random matrices), to a setting where the action space is discrete, highly structured, and induced by the graph Laplacian. The paper provides a novel theoretical analysis of the regret bound that used the Restricted Strong Convexity (RSC) condition for the defined action set. The authors show that the RSC condition holds when performing uniform sampling over their specific action set. Furthermore, in the experimental section, the proposed algorithm’s performance closely matches the empirical lower bound corresponding to the oracle case, which has access to the true subspace $\\Theta^*$.  \n\nI have skimmed through the proofs for the subspace reduction and regret analysis, and I do not see any obvious issues with them. However, since I am not very familiar with the RSC condition, I will refrain from commenting further on that aspect.  \n\nOverall, this paper is clearly written, and the notations are well defined and consistent.", "weaknesses": "1. Although it might be a common assumption in the FJ opinion dynamics model, this paper assumes that the innate opinion $s$ is static over time, and only the expressed opinion $z_t$ evolves. I am somewhat skeptical about this assumption, as innate opinions could also be influenced by the expressed opinions of neighbors. However, since this work explicitly follows the assumptions of the standard FJ model, this limitation may not significantly undermine the overall validity of the paper.\n\n2. The rationale for why the action space is discrete is not clearly explained, nor is it entirely clear whether this assumption is reasonable within the given problem setting. (See Question 1.)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GoLdnOxlDb", "reviewer": "Reviewer_zipZ", "summary": "This paper studies an online learning problem involving the Friedkin-Johnsen (FJ) opinion dynamics model. The model describes a discrete-time dynamical system over the expressed opinions of users connected by an interaction graph, which also depends on some innate opinions of the finitely many users, which initializes the system. The system is known to converge to an equilibrium (fixed-point), at which one can measure polarization (variance of the equilibrium opinion distribution) and disagreement (essentially some notion of smoothness of the equilibrium distribution as given by its quadratic form under the graph Laplacian). The authors study the fundamental question of whether, without knowledge of the initial, innate opinion distribution of the users, one can choose interaction graph structures to minimize polarization and disagreement. This is formulated as an online learning problem where, at each time step, the user chooses an interaction graph structure and receives bandit feedback on an objective function encoding the polarization and disagreement of the resulting FJ dynamics at equilibrium. The problem is motivated by social media platforms implementing interventions (via changes to user interaction structure) to minimize polarization and disagreement.\n\nFor this problem, the authors obtain a sublinear regret bound scaling like O(|V| \\sqrt{T}) (where |V| is the number of users) using an explore-then-commit approach: first, using some uniform exploration phase to learn a low-rank subspace in the interaction graph space, and then to run a no-regret linear bandit algorithm on the set of actions in the learned, lower-dimensional representation. The result of the two-phase approach is an improved linear dependence on |V| in the final regret bound, as opposed to a quadratic dependence if one naively runs a standard linear bandit algorithm from the initial round. One of the core technical novelties of the work is the design of the initial subspace estimation phase, which is specialized to the particular discrete structure of the problem setting and departs from prior works on dimensionality reduction in matrix bandits. \n\nThe authors additionally show the effectiveness of the proposed method experimentally.", "questions": "Regarding the assumptions mentioned under Weaknesses:\n* Are you assuming the intervention space is a priori finite and fixed due to some exogenous problem constraints (e.g., a platform can only choose certain network structures given privacy/connection constraints between users)? In principle, this set could be exponentially large in |V| (since each graph Laplacian corresponds to a different adjacency matrix). How does the final regret bound of Theorem 4.1 depend on the size of the intervention space K? \n* Is it known how quickly the FJ dynamics converges to equilibrium (c.f., the comment regarding asymptotic convergence in L126-L127)? In other words, at what timescale with respect to the FJ dynamics does the outer OPD-Min-ESTR algorithm operate, since it is assumed that the learner receives bandit feedback on the objective function for the dynamics at equilibrium.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Overall, the paper is very clearly written and presented, and the new subspace estimation technique used in the main algorithm seems novel.", "weaknesses": "Several assumptions made in the paper could be discussed further: \n* One assumption is that the intervention space (action space) is comprised of a fixed set of K admissible graph Laplacians, but it is not discussed how the regret of the algorithm scales with K (in particular if the action set contains all graph Laplacians). \n* A second assumption is that the user observes an estimate of the polarization/disagreement objective at equilibrium under the FJ dynamics, but it is not discussed how fast the FJ dynamics actually converges to this equilibrium.\n\nNote that the main body of the paper also exceeds 9 pages by several lines (but after communication with a PC representative, this is OK).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xOkSaJjiL3", "reviewer": "Reviewer_jpz5", "summary": "The paper tackles minimizing polarization plus disagreement in the Friedkin–Johnsen model with online bandit feedback, observing one noisy scalar per intervention. It runs two phases: a low rank trace regression estimates a rank one matrix and its top direction to rotate and compress arm features to linear in the number of nodes, then a standard linear bandit such as OFUL operates on the reduced features; the authors prove phase one recovery and an overall regret that scales with the square root of time and network size, and validate empirically.", "questions": "1/ Why choosing a regret setting and not BAI setting in your case?\n\n2/ Could you detail how the candidate arms are generated for the real-data experiments?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "1/ The subject is highly relevant and important.\n\n2/ The approach is clearly presented with an exemplary writing.\n\n3/ The authors cleverly adapt classical bandit strategies to their specific setting.", "weaknesses": "Summary\n\nWhile the paper has the merit of carefully deriving the technical aspects and adapts classical bandit concepts (a preconditioning phase followed by OFUL), it does not clearly justify the online formulation over prior offline formalisms (or a BAI formalisms) and omits state-of-the-art baselines in the experiments.\n\nMajor concerns\n\n1/ Please compare with additional baselines (e.g., Chaitanya et al., 2024) and with the subspace Oracle in a sample-based evaluation. Using the same arm set and sample budget, plot the minimum polarization plus disagreement obtained versus the number of observed intervention outcome pairs (learning-curve style). For your method and the Oracle also report the mean polarization plus disagreement of the best arm selected after T = number of samples.\n\n2/ Please justify the online regret minimization (vs. offline periodic updates and a BAI setting for example). Explain why interventions are sequential and interim loss matters a real case, and add a brief disscussion on the comparison to batched/BAI baseline in this aspect.\n\nMinor comments\n\n1/ Consider restricting the regret plot to the first 2,000 iterations and use a logarithmic x-axis/y-axis to better expose the early hinge between Phase-1 and Phase-2.\n\n2/ There are numerous typos, for example: \"which which we term\", \"problem reduces to a low-rank matrix bandits\", \"existing analyzes\", etc\n\n3/ In the supplementary material, expand the ethics/impacts discussion (potential misuse, beneficiaries vs. risks, etc). Also add a plain-language note on the meaning in real life of the mean-centered innate opinions assumption.\n\nGrading explanation\n\nThe paper is clear and technically strong, yet key SOTA baselines are missing (and the motivation for the setting is not clear).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)