REVIEW 3 major objections 6 minor 39 references
Batched Adaptive Network Formation
T0 review · 3 major / 6 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read By proving that batched variational estimates behave like Gaussian signals, this paper turns adaptive network formation into a Bayesian bandit whose policy improves toward oracle performance within a few batches.
desk verdict A genuinely useful bridge between WSBM network econometrics and batched bandits, with a promising algorithm and a real gap between the asymptotic theory and the Bayesian type-updating step. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the equivalence of three likelihoods under batched sparse asymptotics: the complete-graph likelihood with observed agent types, the marginal likelihood with types integrated out, and the mean-field variational ELBO all have the same local Gaussian limit, with per-type-pair variance inversely proportional to the policy's sampling frequency times the Fisher information (Proposition 1 and Theorems 1–2). This identity is what licenses the paper's central move: treat each batch's variational estimator as a Gaussian signal for $\theta$, treat each agent's local variational approximation as a categorical signal for $Z$, and combine them across batches by Gaussian and categorical Bayesian updating (equations 5.1 and 5.2). The resulting posteriors are plugged into a constrained maximum-weight matching problem whose solution is the next batch's pairing policy, and the Hybrid Greedy-Thompson algorithm is the specific greedy-in-$\theta$, Thompson-in-$Z$ instance of that machinery.
What would settle it
Run a simulation with true latent types known and compare the batch-by-batch posterior (5.2) with the oracle posterior; if the posterior's probability on the true type decreases or its credible-set coverage of the true type falls well below nominal as batches grow, the categorical-signal premise is refuted. Alternatively, artificially sharpen the LVA by exponentiating $q_{t,i}$ and observe whether label accuracy and network value degrade.
Extended reading notes
Core claim
The paper's claim is that, under batched sparse network asymptotics, a weighted stochastic block model with unobserved latent types is asymptotically equivalent to a Gaussian shift experiment at the level of likelihood ratios, and the computationally feasible mean-field variational ELBO inherits the same limit as the full marginal likelihood. Consequently, batched variational estimates of the complementarity parameters can be treated as Gaussian signals, and the per-agent local variational approximations can be treated as categorical signals for the latent types. The paper then aggregates these signals by Bayesian updating and converts the resulting posteriors into a network policy by solving a constrained maximum-weight matching problem; in the proposed Hybrid Greedy-Thompson algorithm the production parameters are used at their posterior means while agent types are sampled from their categorical posteriors. Monte Carlo experiments with two and three latent types show the policy's expected total output rising toward the oracle benchmark within about six batches, with false labeling rates declining steadily, and with the algorithm remaining effective—though slower to converge—when agents enter and exit the pool.
Load-bearing premise
The algorithm's type-learning step assumes each batch's local variational approximation acts as an independent, well-calibrated categorical signal for that agent's latent type; the paper proves global asymptotic normality of parameter estimates but does not prove this per-agent signal interpretation, and miscalibrated or data-correlated signals would mislead the matching policy.
Editorial extensions
If this is right
- If the Gaussian/categorical signal interpretation holds, the algorithm's expected total network output approaches the oracle benchmark within a few batches, as the simulations demonstrate for $K=2$ and $K=3$ latent types.
- The same asymptotic results justify offline estimation: treating the full sample as a single batch gives variational estimates that are asymptotically normal and equivalent to complete-graph maximum likelihood.
- Practical constraints—per-agent workload limits and clipping rates that keep every type pair observable—are built into the policy as integer constraints in the matching problem, so exploration is never starved.
- In nonstationary pools with agent entry and exit, the algorithm keeps improving but needs additional batches to relearn new agents' types; its regret converges to a higher floor at higher turnover.
- Posteriors for both $\theta$ and $Z$ sharpen over batches, with false labeling rates roughly halved or better in the simulated settings.
Reading between the lines
- A direct calibration test of equation (5.2)—checking whether the posterior's coverage of true latent types matches nominal levels in simulations where $Z$ is known—would show whether the LVA can be used at face value as a categorical likelihood or needs tempering.
- Nothing in the Gaussian-signal argument fixes the greedy-in-$\theta$ choice; posterior sampling or upper-confidence-bound rules on $\theta$ would inherit the same asymptotic justification, making HGT one point on a family of viable policies.
- Because the proof relies on local asymptotic normality plus sparse-degree asymptotics rather than on details of the WSBM, the same batched design should transfer to other pairwise latent-type models, such as mixed-membership or dynamically evolving types, if the analogous equivalence theorems hold.
- The small finite-sample biases visible in the posterior histograms suggest a practical extension: measuring how bias decays with per-batch sample size would tell practitioners when batched updating dominates a single offline estimate.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper proposes an online, batched network formation algorithm for weighted stochastic block models in which agents' latent types are unobserved and only pairwise edge outcomes are observed. The authors establish a batched local asymptotic normality result for the complete-graph model (Proposition 1), an asymptotic equivalence between the marginal likelihood and the complete-data likelihood under sparse network asymptotics (Theorem 1), and an asymptotic equivalence between the variational ELBO and the complete-data likelihood (Theorem 2). They use these results to justify treating each batch's variational estimates of θ and the local variational approximations q_{t,i} as Gaussian and categorical 'signals,' respectively, in a Bayesian updating scheme (Section 5.1), and feed the resulting posteriors into a maximum-weight matching problem to form the next batch's network (HGT algorithm, Section 5.3). Monte Carlo simulations in Section 6 show declining false labeling rates and regret moving toward the oracle benchmark, including with worker turnover.
Significance. If the theoretical link between the variational estimates and the Bayesian signals is made rigorous, the paper makes a genuinely useful contribution: it brings Le Cam's asymptotic theory for batched adaptive experiments into a network setting with latent heterogeneity, and it shows how feasible variational inference can be embedded in an online allocation policy. The paper is also commendable for providing proofs in Appendix A, for explicitly modeling sparse network asymptotics, and for calibrating the simulations to real-world studies (Rohrer et al. 2021; Xu et al. 2024). The main weakness is that the asymptotic results in Section 4 justify consistency and asymptotic normality of point estimates, but they do not establish the calibration and independence properties that the Bayesian update in Eq. (5.2) requires. This gap is directly relevant to the paper's central claim that variational estimates can be treated as normal/categorical signals, and it needs to be addressed before the theoretical foundation claim is supported.
major comments (3)
- [Section 5.1, Eq. (5.2)] This update treats each batch's local variational approximation q_{t,i}(a) as an independent categorical likelihood for Z_i. Section 4 shows consistency of q_i toward the true indicator and asymptotic equivalence of the variational estimator to the complete-graph MLE, but consistency does not imply calibration: no result in the paper establishes that q_{t,i}(a) equals or approximates the conditional probability of batch t's data given Z_i=a, nor that q_{t,i} is independent of the information summarized in ω_{t-1,i}. In fact, q_{t,i} is computed from the same batch data and from the same θ-hat_t used in Eq. (5.1), so the θ and Z signals from a batch are correlated. Because Eq. (5.2) compounds the approximation error across batches, and because the Thompson-in-Z draws enter the matching problem (5.3), this is the load-bearing step for the paper's claimed 'theoretical foundation for treating variational estimates as normal signals.' The authors should either prove a calibration result for q under Assumptions 1-5, or recast the update as a heuristic and provide a regret or risk analysis that does not rely on exact likelihood interpretation.
- [Section 4.2, Theorems 1-2; Appendix A.2] The proof of Theorem 1 depends on high-level Assumptions 4 and 5 (the concentration inequalities (A.4)-(A.5), Lipschitz continuity, and the negative directional derivative condition) as well as on the unimodality and identifiability restrictions stated immediately before the theorem. The text asserts at the end of Section 4.2 that these are 'readily verified' for the models used, but the paper does not actually verify them for the binary-outcome WSBM used in Section 6. Unimodality of f_{π,θ} is a strong global condition that is not obviously implied by the local conditions in Assumption 2. Since Theorem 2 inherits these assumptions and Theorem 2 is the theoretical foundation for the Gaussian-signal update (5.1), the manuscript should provide the verification (or a precise citation with the conditions checked) for the simulation DGP and for the classes of p_θ advertised in Section 2.
- [Section 5.2, Eqs. (5.3)-(5.6)] The agent-level matching problem uses realized draws \tilde Z_i from the posterior as if they were the true types, both in the objective (5.3) and in the clipping constraint (5.6). Since \tilde Z_i are random, the resulting policy need not satisfy the intended type-pair-level constraints (2.5)-(2.6) for the actual latent types, and the expected network output is evaluated under a single posterior draw rather than under the posterior distribution. This weakens the claim that the HGT policy solves the constrained optimization problem (2.7). The paper should justify the plug-in approach, for example by a consistency argument for the matching solution as the posterior concentrates, or by reformulating the constraints in terms of the posterior probabilities of type assignments.
minor comments (6)
- [Section 2.2, Eq. (2.3)] The objective in Eq. (2.3) appears to be missing the summation over type pairs; the expression 'max_{ψ∈Ψ} ψ(a,b)Υ(a,b)' should be 'max Σ_{a,b} ψ(a,b)Υ(a,b)' in display (2.3) and in (2.7).
- [Section 1, Introduction] There is a duplicated word 'that' in the sentence comparing production models; it reads 'production models that that impose structure.'
- [Figures 2 and 3] The legends in Figures 2 and 3 label the algorithm 'HTG'; elsewhere in the paper it is 'HGT'. Please correct.
- [Section 4.2, after Assumption 3] There is a typo 'in these dateset' that should be 'in these datasets.'
- [Section 5.1, Eq. (5.1)] The standard error bse_{t,ab} is introduced in Eq. (5.1) without a formula or implementation details; the simulations should state how it is obtained from the variational estimate (e.g., a plug-in of the asymptotic variance Q^{-1}_{θ,t}).
- [Theorem 2] The statement of Theorem 2(i) asserts the o_P(1) term is uniform over π and θ, but the proof in Appendix A.3 only demonstrates pointwise equality; the proof or statement should be adjusted to track uniformity.
Circularity Check
Eq. (5.2) treats the variational posterior q̂t,i as an independent categorical likelihood for Zi, making the 'categorical signal' foundation self-definitional.
-
self definitional
[Section 3 (LVA definition) and Section 5.1, Eq. (5.2)]
"Each component qi, referred to as a local variational approximation (LVA), serves as an individual approximation to the posterior distribution for the latent variable Zi ... These categorical signals can be aggregated recursively for each agent via Bayesian classification. Assuming a categorical prior ω0,i(a) on Zi, the posterior after batch t, denoted by ωt,i(a), remains categorical and updates as ωt,i(a) = ωt−1,i(a)ˆqt,i(a) / Σ_{a=1}^K ωt−1,i(a)ˆqt,i(a)."
The LVA q̂t,i is introduced as a variational approximation to the posterior distribution of Zi, i.e., it already contains the batch-t evidence about Zi. Eq. (5.2) then multiplies the running posterior ωt−1,i by q̂t,i as if q̂ were an independent categorical likelihood for Zi. This is not a Bayes update with a signal; it updates a posterior with a posterior (or posterior approximation) computed from the same data. Section 4 establishes only consistency of q̂i toward the true indicator and asymptotic normality of θ̂; it never shows that q̂i equals or approximates the conditional likelihood p(Yt|Zi) in a calibrated sense. Hence the 'categorical signals' foundation for 'principled Bayesian updating' is self-definitional: the signal is defined as the posterior it is used to update.
full rationale
The main asymptotic results are not circular: Proposition 1 and Theorems 1–2 derive batched LAN and variational-to-MLE equivalence from external statistical machinery (Hajek–Le Cam, Hirano–Porter, Bickel et al.), and the Gaussian Bayesian update for θ in Eq. (5.1) is supported by the asymptotic normality in Theorem 2(ii). The simulations are data-generating exercises compared against an oracle, so the reported productivity gains are not fitted to the target outcome. The load-bearing circularity is confined to the Z-side of the algorithm: the LVA is defined as an approximation to the posterior of Zi, and Eq. (5.2) then reuses it as a categorical likelihood in a recursive Bayesian update. No theorem in Section 4 calibrates q̂ as a likelihood; consistency of label recovery is a different property from calibration. This makes the paper's advertised 'categorical signals' foundation partially circular, though the θ-side and the matching policy retain independent content.
Assumptions & free parameters
free parameters (5)
- Number of latent types K =
2 (Simulation 6.1), 3 (Simulation 6.2)
- Clipping rate lambda =
not specified numerically
- Workload bounds d_l, d_h =
d_l=d_h=24 in K=2 case; [35,45] in K=3 case
- Prior hyperparameters for theta and Z =
uninformative priors in simulations
- Initial policy psi_1 =
not specified in Algorithm 1
assumptions (8)
- standard math Hajek-Le Cam asymptotic representation theorem and LAN theory (Van der Vaart 2000; Hirano-Porter 2025)
- domain assumption Assumption 1: policy psi_t is pre-determined (F_{t-1}-measurable)
- domain assumption Assumption 2: per-type pair LAN plus asymptotic normality of the pair-specific MLE
- domain assumption Assumption 3: sparse network asymptotics, m_t/(n_t log n_t) -> lambda_t
- domain assumption Assumptions 4-5: concentration inequalities and smoothness or identifiability of the likelihood modularity
- domain assumption Agent types Z_i are i.i.d. from a fixed distribution pi with known K
- ad hoc to paper LVA q_t,i(a) is used as a categorical likelihood in the Bayesian update (5.2)
- ad hoc to paper Sampled types Z~_i in the matching problem are treated as fixed true types for the constraints (5.5)-(5.6)
Cite this review
Pith. "Pith review of Batched Adaptive Network Formation." pith.science (2026). https://pith.science/paper/ALAFD5MY
@misc{pith2026250718961,
author = {Pith},
title = {Pith review of: Batched Adaptive Network Formation},
year = {2026},
howpublished = {\url{https://pith.science/paper/ALAFD5MY}},
note = {Machine review of arXiv:2507.18961}
}
read the original abstract
Networks are central to many economic and organizational applications, including workplace team formation, social platform recommendations, and classroom friendship development. In these settings, networks are modeled as graphs, with agents as nodes, agent pairs as edges, and edge weights capturing pairwise production or interaction outcomes. This paper develops an adaptive, or \textit{online}, policy that learns to form increasingly effective networks as data accumulates over time, progressively improving total network output measured by the sum of edge weights. Our approach builds on the weighted stochastic block model (WSBM), which captures agents' unobservable heterogeneity through discrete latent types and models their complementarities in a flexible, nonparametric manner. We frame the online network formation problem as a non-standard \textit{batched multi-armed bandit}, where each type pair corresponds to an arm, and pairwise reward depends on type complementarity. This strikes a balance between exploration -- learning latent types and complementarities -- and exploitation -- forming high-weighted networks. We establish two key results: a \textit{batched local asymptotic normality} result for the WSBM and an asymptotic equivalence between maximum likelihood and variational estimates of the intractable likelihood. Together, they provide a theoretical foundation for treating variational estimates as normal signals, enabling principled Bayesian updating across batches. The resulting posteriors are then incorporated into a tailored maximum-weight matching problem to determine the policy for the next batch. Simulations show that our algorithm substantially improves outcomes within a few batches, yields increasingly accurate parameter estimates, and remains effective even in nonstationary settings with evolving agent pools.
Figures
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[1]
, " * write output.state after.block = add.period write newline
ENTRY address author booktitle chapter edition editor howpublished institution journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block FUNCTION init.state.consts #0 'before.all := #1 'mid.sentence := #2 '...
-
[2]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in " " * FUNCTION format....
-
[3]
(2015), An empirical model of the medical match, American Economic Review, 105, 1939--1978
Agarwal, N. (2015), An empirical model of the medical match, American Economic Review, 105, 1939--1978
work page 2015
-
[4]
Ahmadpoor, M. and Jones, B. F. (2019), Decoding team and individual impact in science and invention, Proceedings of the National Academy of Sciences, 116, 13885--13890
work page 2019
-
[5]
Amini, A. A., Chen, A., Bickel, P. J., and Levina, E. (2013), Pseudo-likelihood methods for community detection in large sparse networks,
work page 2013
-
[6]
(2014), Regret in online combinatorial optimization, Mathematics of Operations Research, 39, 31--45
Audibert, J.-Y., Bubeck, S., and Lugosi, G. (2014), Regret in online combinatorial optimization, Mathematics of Operations Research, 39, 31--45
work page 2014
-
[7]
Auer, P. (2002), Using confidence bounds for exploitation-exploration trade-offs, Journal of Machine Learning Research, 3, 397--422
work page 2002
-
[8]
Bickel, P., Choi, D., Chang, X., and Zhang, H. (2013), Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels, The Annals of Statistics, 41, 1922--1943
work page 2013
Show all 39 references
-
[9]
Bickel, P. J. and Chen, A. (2009), A nonparametric view of network models and Newman--Girvan and other modularities, Proceedings of the National Academy of Sciences, 106, 21068--21073
2009
-
[10]
(2021), Teams: Heterogeneity, sorting, and complementarity, arXiv preprint arXiv:2102.01802
Bonhomme, S. (2021), Teams: Heterogeneity, sorting, and complementarity, arXiv preprint arXiv:2102.01802
2021 arXiv
-
[11]
(2025), Adaptive maximization of social welfare, Econometrica, 93, 1073--1104
Cesa-Bianchi, N., Colomboni, R., and Kasy, M. (2025), Adaptive maximization of social welfare, Econometrica, 93, 1073--1104
2025
-
[12]
(2013), Combinatorial multi-armed bandit: General framework and applications, in International conference on machine learning, PMLR, pp
Chen, W., Wang, Y., and Yuan, Y. (2013), Combinatorial multi-armed bandit: General framework and applications, in International conference on machine learning, PMLR, pp. 151--159
2013
-
[13]
(2008), A mixture model for random graphs, Statistics and computing, 18, 173--183
Daudin, J.-J., Picard, F., and Robin, S. (2008), A mixture model for random graphs, Statistics and computing, 18, 173--183
2008
-
[14]
(2022), Online team formation under different synergies, in International Conference on Web and Internet Economics, Springer, pp
Eichhorn, M., Banerjee, S., and Kempe, D. (2022), Online team formation under different synergies, in International Conference on Web and Internet Economics, Springer, pp. 78--95
2022
-
[15]
and De Paula, \'A
Graham, B. and De Paula, \'A . (2020), The econometric analysis of network data, Academic Press
2020
-
[16]
Graham, B. S. (2020), Network data, in Handbook of econometrics, Elsevier, vol. 7, pp. 111--218
2020
-
[17]
(1970), A characterization of limiting distributions of regular estimates, Zeitschrift f \"u r Wahrscheinlichkeitstheorie und verwandte Gebiete , 14, 323--330
H \'a jek, J. (1970), A characterization of limiting distributions of regular estimates, Zeitschrift f \"u r Wahrscheinlichkeitstheorie und verwandte Gebiete , 14, 323--330
1970
-
[18]
and Porter, J
Hirano, K. and Porter, J. R. (2025), Asymptotic representations for sequential decisions, adaptive experiments, and batched bandits, arXiv preprint arXiv:2302.03117
2025 arXiv
-
[19]
(2024), Nonparametric Identification And Estimation of Stochastic Block Models From Many Small Networks, TSE Working Paper
Jochmans, K. (2024), Nonparametric Identification And Estimation of Stochastic Block Models From Many Small Networks, TSE Working Paper
2024
-
[20]
and Weidner, M
Jochmans, K. and Weidner, M. (2019), Fixed-effect regressions on network data, Econometrica, 87, 1543--1560
2019
-
[21]
(2021), Matching while learning, Operations Research, 69, 655--681
Johari, R., Kamble, V., and Kanoria, Y. (2021), Matching while learning, Operations Research, 69, 655--681
2021
-
[22]
K., and Li, H
Johari, R., Kamble, V., Krishnaswamy, A. K., and Li, H. (2018 a ), Exploration vs. exploitation in team formation, arXiv preprint arXiv:1809.06937
2018 arXiv
-
[23]
Exploitation in Team Formation for Collaborative Work, in Conference on Web and Internet Economics (WINE)
--- (2018 b ), Exploration vs. Exploitation in Team Formation for Collaborative Work, in Conference on Web and Internet Economics (WINE)
2018
-
[24]
and Sautmann, A
Kasy, M. and Sautmann, A. (2021), Adaptive treatment assignment in experiments for policy choice, Econometrica, 89, 113--132
2021
-
[25]
and Teytelboym, A
Kasy, M. and Teytelboym, A. (2023), Matching with semi-bandits, The Econometrics Journal, 26, 45--66
2023
-
[26]
Lai, T. L. and Robbins, H. (1985), Asymptotically efficient adaptive allocation rules, Advances in applied mathematics, 6, 4--22
1985
-
[27]
Le Cam, L. et al. (1972), Limits of experiments, in Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability, University of California Press, vol. 1, pp. 245--261
1972
-
[28]
(2016), Effect of online dating on assortative mating: Evidence from South Korea, Journal of Applied Econometrics, 31, 1120--1139
Lee, S. (2016), Effect of online dating on assortative mating: Evidence from South Korea, Journal of Applied Econometrics, 31, 1120--1139
2016
-
[29]
and Snijders, T
Nowicki, K. and Snijders, T. A. B. (2001), Estimation and prediction for stochastic blockstructures, Journal of the American statistical association, 96, 1077--1087
2001
-
[30]
(2016), Batched bandit problems, The Annals of Statistics, 44, 660--681
Perchet, V., Rigollet, P., Chassang, S., and Snowberg, E. (2016), Batched bandit problems, The Annals of Statistics, 44, 660--681
2016
-
[31]
(2022), A causal test of the strength of weak ties, Science, 377, 1304--1310
Rajkumar, K., Saint-Jacques, G., Bojinov, I., Brynjolfsson, E., and Aral, S. (2022), A causal test of the strength of weak ties, Science, 377, 1304--1310
2022
-
[32]
M., Keller, T., and Elwert, F
Rohrer, J. M., Keller, T., and Elwert, F. (2021), Proximity can induce diverse friendships: A large randomized classroom experiment, PloS one, 16, e0255097
2021
-
[33]
Thompson, W. R. (1933), On the likelihood that one unknown probability exceeds another in view of the evidence of two samples, Biometrika, 25, 285--294
1933
-
[34]
Van der Vaart, A. W. (2000), Asymptotic statistics, vol. 3, Cambridge university press
2000
-
[35]
Wang, Y. R. and Bickel, P. J. (2017), Likelihood-based model selection for stochastic block models,
2017
-
[36]
and Deming, D
Weidmann, B. and Deming, D. J. (2021), Team players: How social skills improve team performance, Econometrica, 89, 2637--2657
2021
-
[37]
Weigel, J., Bessone, P., Bergeron, A., Tourek, G., and Kabeya, J. K. (2024), Supermodular Bureaucrats: Evidence from Randomly Assigned Tax Collectors in the DRC, Working Paper
2024
-
[38]
Xu, Y., Hu, M., Chu, J., and Ching, A. T. (2024), Heterogeneous Complementarity and Team Design: The Case of Real Estate Agents, Marketing Science
2024
-
[39]
(2020), Inference for batched bandits, Advances in neural information processing systems, 33, 9818--9829
Zhang, K., Janson, L., and Murphy, S. (2020), Inference for batched bandits, Advances in neural information processing systems, 33, 9818--9829
2020
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.