{"id":"c0d79196-9110-40ea-ad9f-f54eb272dacb","arxiv_id":"2412.03727","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A Pareto-optimal trade-off between regret and treatment-effect estimation is derived and achieved for bandits with network interference, by compressing the action space through exposure mapping.","lead":"This paper builds a bandit framework for online experiments in which a person's treatment can also affect their network neighbors, and proves an optimal balance between estimating the treatment effect and limiting regret. It then proposes an algorithm, UCB-TSN, that reaches this balance, plus an adversarial variant, and argues it improves on an existing no-interference baseline.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Pareto-optimality claim is not established: Theorem 5's proof wrongly infers from a scalar product lower bound that no coordinate-wise dominating algorithm exists. Appendix H's jump to an instance nu'' is a non sequitur.","rationale":"The reader's weakest_assumption concerned misspecification of the exposure mapping. That is a legitimate external-validity concern, but it is a modeling assumption rather than an internal gap. The more load-bearing issue is internal: the claimed Pareto-optimality, which is the paper's headline contribution, depends on Theorem 5, whose sufficiency proof contains a logical non sequitur. The proof uses a scalar minimax product lower bound to rule out coordinate-wise Pareto-domination, but the lower bound applies to the worst-case instance, whereas Definition 2 defines fronts as the best-case envelope for each algorithm. These are different objects; domination of one algorithm's front by another's does not imply a worst-case violation of the scalar bound. This is not merely a missing constant: no argument in the paper connects the front to the worst-case product. The algorithm's regret and estimation bounds (Theorems 6-7) appear plausible and the lower-bound construction in Theorem 4 is standard, so the paper retains value, but the 'Pareto-optimal trade-off' claim requires either a repaired proof of Theorem 5 or a weaker claim of scalar-product minimax optimality. The reader noted the Pareto-optimality proof was under-specified, so our concern partially overlaps, but the reader's primary flagged assumption was the exposure mapping, which we do not regard as the decisive issue.","tokens_in":32403,"tokens_out":23578,"duration_ms":246463,"concrete_test":"Analytical check: In the degenerate no-interference case (N=1, |U_E|=K), take the two hard instances used in the proof of Theorem 4 and compute both the front F defined in Definition 2 and the worst-case scalar product for UCB-TSN and for a variant with T1' = T1/2. If the variant has smaller regret and smaller estimation error on every front point of UCB-TSN while its worst-case product still satisfies the Omega(sqrt(|U_E|)) lower bound due to a third instance, Theorem 5's sufficiency claim is false. If no such construction exists, attempt the missing step in Appendix H: derive from Definition 2 the existence of nu'' with sqrt(R_{nu''}(pi) e_{nu''}(Delta)) = omega(sqrt(|U_E|)).","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central claim (Theorems 4-5 plus Corollary 8) is that UCB-TSN achieves a Pareto-optimal regret/ATE trade-off. The sufficiency direction of Theorem 5 states that max_nu sqrt(R_nu e_nu) = O~(sqrt(|U_E|)) implies Pareto-optimality under Definition 2. The proof in Appendix H argues contrapositively: if {pi', Delta'} Pareto-dominates {pi, Delta}, Theorem 4 gives an instance nu' with sqrt(R_{nu'}(pi') e_{nu'}(Delta')) = Omega(sqrt(|U_E|)); it then asserts that 'there further exists another instance nu''' with sqrt(R_{nu''}(pi)e_{nu''}(Delta)) strictly larger than sqrt(|U_E|). This step does not follow. Pareto-domination compares the front F(pi), i.e., the lower-left envelope of achievable (R,e) pairs over instances for pi, with F(pi'). The hard instance nu' for pi' need not belong to F(pi'), and domination of F(pi) by F(pi') does not imply any single instance on which pi's product exceeds the worst-case lower bound. The scalar product lower bound in Theorem 4 constrains worst-case product, not the front; it cannot rule out an algorithm with a worse hard instance off the front that nevertheless dominates pi on every front point. Thus Theorem 5 is unproven as written, and the headline Pareto-optimality of UCB-TSN is unsupported. Establishing it would require either matching constants or a genuine two-objective lower bound on the front, not just on the scalarized product.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes MAB-N, a stochastic multi-armed bandit framework under network interference, where the action space is reduced via a statistical exposure mapping and clustering. The central claims are: (i) a minimax lower bound, inf_{Δ̂} max_ν sqrt(R_ν e_ν) = Ω(sqrt(|U_E|)) for any policy π (Theorem 4); (ii) a sufficiency criterion asserting that achieving max_ν sqrt(R_ν e_ν) = O~(sqrt(|U_E|)) implies Pareto-optimality (Theorem 5); and (iii) an algorithm UCB-TSN, whose two-stage design matches the lower bound (Corollary 8). An extension to an adversarial setting via EXP3-TSN is also given. The paper interprets these results as the first Pareto-optimal estimation-regret trade-off under general network interference.","tokens_in":32724,"tokens_out":21575,"duration_ms":201427,"significance":"If the claims were fully established, the paper would be a solid contribution: it unifies several prior bandit-under-interference models as special cases of a single exposure-mapping framework, and it extends the estimation-regret trade-off of Simchi-Levi and Wang (2024) from a single unit to general networks. The two-instance minimax construction and the UCB-type upper bound are standard in spirit and appear mostly coherent. However, the headline Pareto-optimality claim rests on Theorem 5, whose proof is invalid, and the proof of Theorem 4 also contains a gap in the translation from E[max] to max E. These are load-bearing issues, not cosmetic ones. The paper also includes reproducible-style algorithm pseudocode and a conservative choice of sub-Gaussian proxy (σ²=2) that keeps the concentration bounds safe despite an erroneous derivation in Appendix E.","major_comments":[{"comment":"The sufficiency proof is a non sequitur. From Pareto-domination of {π,Δ̂} by {π',Δ̂'}, the proof asserts that Theorem 4 gives an instance ν' with sqrt(R_{ν'}(π') e_{ν'}(Δ̂')) = Ω(sqrt(|U_E|)), and then that 'there further exists another instance ν''' with sqrt(R_{ν''}(π)e_{ν''}(Δ̂)) strictly larger than sqrt(|U_E|). The second step does not follow: Pareto-domination compares front points F(π,Δ̂), and the hard instance ν' for π' need not lie on the front of π', nor does it force any instance on the front of π to have large product. The scalarized worst-case product can be attained at a dominated, off-front instance, so the bound max_ν sqrt(R_ν e_ν) = O~(sqrt(|U_E|)) does not preclude front domination by another algorithm. Consequently, the claim that UCB-TSN is Pareto-optimal (Corollary 8, abstract) is not established by the given argument.","section":"§4, Theorem 5 and Appendix H"},{"comment":"The proof lower-bounds E_ν[max_{i,j}|Δ̂^{(i,j)}_t - Δ^{(i,j)}_ν|] and multiplies by sqrt(R_ν(T,π)), but the estimation error e_ν is defined in Eq. (5) as max_{i,j} E_ν[|Δ̂^{(i,j)}_t - Δ^{(i,j)}_ν|]. Since max_i E ≤ E max_i, the displayed lower bound on E[max] does not imply the claimed lower bound on e_ν. The argument can be repaired by applying the hypothesis-testing lower bound to the specific pair (S,S') selected in the construction and using E|Δ̂^{(S,S')} − Δ^{(S,S')}| ≥ (α/2)P(|Δ̂^{(S,S')} − Δ^{(S,S')}| ≥ α/2); as written, the proof does not establish Theorem 4.","section":"§4, Theorem 4 proof, Appendix G, Eq. (28)"},{"comment":"The derivation of the 'natural' sub-Gaussian proxy uses cosh(m/2) ≤ exp(m²/8) for Z = (1/N)∑_i (Y_i(A) − Ỹ_i(S_t)). This Z is zero-mean and bounded in [−1,1], so its MGF can be as large as cosh(m), not cosh(m/2); the claimed proxy 1/N + 1/4 is not justified. A valid bound for the sampling-noise term alone gives an additional factor exp(m²/2), so the combined proxy is at most 1/N + 1/2. Since the paper subsequently uses the conservative σ² = 2, the concentration bounds in Appendix I remain valid, but the derivation in Appendix E and the remarks about the order of N should be corrected.","section":"Appendix E, Eqs. (8)–(10)"}],"minor_comments":[{"comment":"The direction of the domination relation appears reversed: as written, the condition forbids an instance ν for which (R,e) is componentwise ≤ (sqrt(R_ν),e_ν), which would define maximal rather than minimal front points; the intended lower-left envelope requires the opposite inequality.","section":"Definition 2, condition (ii)"},{"comment":"The claimed set equality 'Pareto Frontier is represented as P = {(R_ν,e_ν) : sqrt(R_ν e_ν) = O~(sqrt(|U_E|))}' uses asymptotic notation inside a set definition; the intended asymptotic characterization should be stated explicitly.","section":"Theorem 5 statement"},{"comment":"In the pseudocode, the second-phase loop does not explicitly show the update of N_t^S and R̂_t(S); the 'Parameter' lines should be placed inside the for-loop to match the stated update rules.","section":"Algorithm 1"},{"comment":"The notation Δ̂_t in the probability bound should be indexed by the specific pair (S,S') used in the construction, to avoid the E[max] versus max E ambiguity in the conversion to a bound on e_ν.","section":"Appendix G, Eqs. (27)–(28)"},{"comment":"When choosing α so that qα²N R_{ν1}(T,π)/(|U_E||Δ1|) = 1/2, the proof should state explicitly that Condition 1 (T ≥ |U_E|) is used and should verify that α ≤ 1 remains feasible given the lower bound on |Δ1|.","section":"Appendix G, Eq. (30)"}],"recommendation":"major_revision","confidential_remarks":"The paper's real contribution is a minimax scalarized trade-off, not the genuine bi-objective Pareto optimality claimed in the abstract and Theorem 5. The authors should either repair the proof of Theorem 5 or revise the claims to a scalarized trade-off guarantee; the latter would still be a meaningful generalization of Simchi-Levi and Wang (2024). I also recommend that the front definition (Definition 2) be rewritten carefully, since its current ambiguity appears to have masked the proof gap. The lower-bound and upper-bound arguments are otherwise largely coherent and likely repairable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Zhiheng and Zichen's paper is worth a read, but not for the reason it gives itself. The real content is the MAB-N framework and a matching scalar bound: for any policy, some instance forces sqrt(R*e) = Ω(sqrt(|U_E|)), and UCB-TSN achieves O~(sqrt(|U_E|)) with T1 = sqrt(|U_E|*T). That part is a clean, useful generalization of the Simchi-Levi and Wang result to interference via exposure mapping, and the two-instance lower bound plus the UCB analysis look basically right. The framework genuinely does recover the Agarwal et al. and Jia et al. settings as special cases.\n\nWhat the paper does less well is the Pareto-optimality claim. Theorem 5's sufficiency proof is a non sequitur. Matching the worst-case product of regret and estimation error does not, by itself, show that no other pair dominates the front as defined in Definition 2. The proof in Appendix H jumps from 'there is a hard instance for the dominating pair' to 'there is an instance where the dominated pair's product is worse than sqrt(|U_E|)', but front domination doesn't give you that instance. The scalar product lower bound constrains the worst-case product, not the lower-left envelope. This is the paper's headline claim, so as written the central Pareto statement is unsupported. The fix is either to prove a genuine two-objective front lower bound or to restate the contribution as a minimax-optimal scalar trade-off, which the proofs do support.\n\nSmaller issues: the sub-Gaussian proxy derivation in Appendix E ends with sigma^2 = 2, which masks a factor slip; harmless because it is conservative, but worth cleaning. The correctly-specified exposure mapping assumption is the crux - if the mapping is wrong, the regret is measured against the wrong S*. The appendix mentions a relaxation via Manhattan distance but does not prove anything for it. The claimed improvement over Simchi-Levi and Wang in the no-interference case compares two specific algorithms, not fundamental limits, so 'strictly stronger' is overstatement.\n\nWho this is for: anyone working on bandits with interference or adaptive experiments with inference constraints. The framework and the scalar bounds are a solid step, but the paper should be revised before publication: fix or rescope Theorem 5, and tighten the noise and misspecification discussions. Send it to review - a serious referee will find the framework worth their time, and the current gap is exactly the kind of thing review should catch. My own verdict would be a major revision rather than acceptance as-is.","headline":"The MAB-N framework and matching scalar trade-off are solid and worth citing, but the Pareto-optimality theorem is not proved as written.","tokens_in":33253,"tokens_out":3160,"would_cite":true,"duration_ms":34624,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A unified exposure-mapping framework for online experiments proves that regret and ATE estimation under network interference obey the minimax trade-off $\\sqrt{R e} = \\Omega(\\sqrt{|U_E|})$, and the two-stage UCB-TSN algorithm achieves the…","keywords":["multi-armed bandits","network interference","exposure mapping","average treatment effect","regret-estimation trade-off","Pareto optimality","online experimental design","two-stage UCB"],"falsifier":"The proof of Theorem 4 hinges on the divergence bound $KL(P_{\\nu_1},P_{\\nu_2}) \\le qN\\alpha^2 E_{\\nu_1}[N_T^S]$. A reader can test the hinge on a two-unit network with $|U_E|=2$: if the KL divergence between the two constructed instances grows faster than $\\alpha^2$ times the expected number of pulls of the suboptimal exposure arm, the lower bound collapses. A complementary stress test is to run UCB-TSN with an exposure mapping that leaves out a real neighbor effect and check whether regret measured against the true optimal assignment stays $\\widetilde{O}(\\sqrt{|U_E|T})$.","tokens_in":32184,"feed_emoji":"🕸️","tokens_out":11860,"duration_ms":114653,"temperature":0.7,"pith_summary":"Online experiments over networked populations face two goals that pull in opposite directions: estimating average treatment effects requires revisiting suboptimal assignments, while minimizing regret requires abandoning them. The paper claims that under network interference this tension is governed by the size of a compressed action space: for any policy, the product of cumulative regret $R$ and worst-case ATE estimation error $e$ is at least $\\Omega(\\sqrt{|U_E|})$, where $U_E$ is the exposure arm space obtained from the exposure mapping. It then gives a two-stage algorithm, UCB-TSN, whose product is $\\widetilde{O}(\\sqrt{|U_E|})$, so the trade-off is Pareto-optimal. The result holds for general network topologies under a mild condition, and its scope includes the no-interference case, where it improves the previously known trade-off.","feed_headline":"Network interference forces a hard regret-estimation trade-off","feed_subtitle":"A two-stage UCB algorithm matches the lower bound, making regret and ATE estimation Pareto-optimal.","key_machinery":"The load-bearing object is the exposure mapping $S(i,A,H)$, a pre-specified function that summarizes the full treatment assignment $A$ into a low-cardinality exposure arm for each unit; the whole network state is then represented by the exposure super arm $S_t$, living in the set $U_E$ of cluster-wise switchback exposures that are also realizable by some original assignment. This reduces the exponentially large super-arm space $K^N$ to $|U_E| \\le |\\mathcal{U}_s|^C$ and makes the online problem tractable. The proof machinery is the divergence bound $KL(P_{\\nu_1},P_{\\nu_2}) \\le qN\\alpha^2 E_{\\nu_1}[N_T^S]$, which ties the distance between two hard instances to the expected number of pulls of a suboptimal exposure arm, converting estimation difficulty directly into regret. On the algorithmic side, UCB-TSN's first phase (round-robin over $U_E$) supplies the uniform sampling that makes ATE estimation consistent, and its second phase (UCB on $U_E$) controls regret; the choice $T_1=\\sqrt{|U_E|T}$ balances the two bounds.","core_discovery":"The central claim, established as Theorem 4 and Corollary 8, is that regret minimization and ATE estimation cannot both be pushed below a common barrier in online experiments with network interference. For any online policy and any estimator, the paper constructs two statistically close reward instances whose only meaningful difference is the ATE of a chosen exposure arm; the estimation error of any estimator and the number of pulls of that arm are coupled through a KL-divergence calculation, yielding $\\inf_{\\hat\\Delta}\\max_\\nu \\sqrt{R_\\nu(T,\\pi)e_\\nu(T,\\hat\\Delta)} = \\Omega(\\sqrt{|U_E|})$ up to constants in $K$ and $T$. A pair is Pareto-optimal whenever this product is $\\widetilde{O}(\\sqrt{|U_E|})$, and UCB-TSN attains exactly that by exploring all exposure arms uniformly for $T_1 = \\sqrt{|U_E|T}$ rounds and then running UCB on the exposure arm set. This both subsumes and strengthens the earlier estimation-regret trade-off obtained without interference.","pith_inferences":["Beyond the paper: the lower bound identifies $|U_E|$, not the number of units or original arms, as the complexity measure that governs the regret-estimation product, so any refinement of the exposure mapping or clustering that enlarges $U_E$ carries a direct statistical cost.","Beyond the paper: if the exposure mapping misses a real interference channel, the guarantees concern the best exposure arm rather than the true best assignment; a concrete stress test would run UCB-TSN on a network where an unobserved neighbor's treatment drives outcomes and check whether regret relative to the true optimum stays sublinear.","Beyond the paper: the paper's Appendix L replaces exact compatibility with Manhattan-distance proximity, but no analogous Pareto-optimality bound is proved there; proving one for the approximate case is a natural next step."],"forward_implications":["For any network topology and any exposure mapping satisfying $2\\le |U_E|\\le T$, no algorithm can reduce the product of regret and ATE estimation error below $\\Omega(\\sqrt{|U_E|})$.","UCB-TSN reaches the frontier: with $T_1=\\sqrt{|U_E|T}$ it guarantees $R=\\widetilde{O}(\\sqrt{|U_E|T})$ and $e=\\widetilde{O}(\\sqrt{|U_E|/T_1})$, so $\\sqrt{Re}=\\widetilde{O}(\\sqrt{|U_E|})$.","Practitioners can dial between estimation and regret by choosing $T_1$ along the Pareto frontier, since $T_1=0$ recovers standard UCB-like regret while $T_1=T$ recovers uniform estimation design.","In the single-unit, no-interference special case, the regret bound becomes $\\widetilde{O}(K+T_1)$ and the estimation bound $\\widetilde{O}(\\sqrt{K/T_1})$, which is stronger than the earlier baseline trade-off.","Replacing UCB with an EXP3 variant extends the same Pareto-optimal trade-off to adversarial rewards."],"supporting_citations":[{"why":"Supplies the exposure-mapping concept and potential-outcome notation on which the exposure arm space $U_E$ is built.","marker":"Leung (2022a)"},{"why":"Earlier general-interference causal estimation framework from which the exposure mapping formulation is drawn.","marker":"Aronow and Samii (2017)"},{"why":"Baseline estimation-regret trade-off without interference that MAB-N generalizes and improves.","marker":"Simchi-Levi and Wang (2024)"},{"why":"Prior interference-aware bandit model with first-order-neighbor and sparsity assumptions that is recovered as a special case of MAB-N.","marker":"Agarwal et al. (2024)"},{"why":"Prior switchback-style interference bandit that MAB-N subsumes via cluster-wise exposure arms.","marker":"Jia et al. (2024)"},{"why":"Supplies the UCB algorithm whose finite-time analysis is the template for the second-phase regret bound of UCB-TSN.","marker":"Auer et al. (2002)"},{"why":"Provides the information-theoretic lower-bound tools, including KL divergence and Bretagnolle-Huber inequalities, used in the proof of Theorem 4.","marker":"Lattimore and Szepesvári (2020b)"}],"fun_headline_variants":["Pareto-optimal regret vs. estimation under network interference","UCB matches lower bound for regret-estimation trade-off","Networked trials force Pareto-optimal trade-off, UCB attains it","Exact trade-off for online experiments with network interference","Two-stage UCB achieves lower bound for ATE and regret"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The exposure mapping is assumed to capture all ways treatment reaches outcomes: the potential outcome of every unit depends on the full assignment only through the exposure super arm $S_t$, and the regret target $S^*$ is defined in that reduced space. If a real interference channel is left out of $S$, the guarantees attach to a misspecified best arm.","fun_headline_variants_meta":{"raw":{"variants":["Pareto-optimal regret vs. estimation under network interference","UCB matches lower bound for regret-estimation trade-off","Networked trials force Pareto-optimal trade-off, UCB attains it","Exact trade-off for online experiments with network interference","Two-stage UCB achieves lower bound for ATE and regret"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000171,"raw_usage":{"total_tokens":1282,"prompt_tokens":963,"completion_tokens":319,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":579,"completion_tokens_details":{"reasoning_tokens":233}},"tokens_in":579,"tokens_out":319,"duration_ms":3965,"temperature":1.0,"reasoning_tokens":233,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T22:09:58.136511+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"The proof of Theorem 4 hinges on the divergence bound $KL(P_{\\nu_1},P_{\\nu_2}) \\le qN\\alpha^2 E_{\\nu_1}[N_T^S]$. A reader can test the hinge on a two-unit network with $|U_E|=2$: if the KL divergence between the two constructed instances grows faster than $\\alpha^2$ times the expected number of pulls of the suboptimal exposure arm, the lower bound collapses. A complementary stress test is to run UCB-TSN with an exposure mapping that leaves out a real neighbor effect and check whether regret measured against the true optimal assignment stays $\\widetilde{O}(\\sqrt{|U_E|T})$.","supporting_citations":[{"cited_title":"Estimating average causal effects under general interference, with application to a social network experiment","cited_arxiv_id":null,"evidence_quote":"Earlier general-interference causal estimation framework from which the exposure mapping formulation is drawn."},{"cited_title":"Finite-time analysis of the multiarmed bandit problem","cited_arxiv_id":null,"evidence_quote":"Supplies the UCB algorithm whose finite-time analysis is the template for the second-phase regret bound of UCB-TSN."}],"review_version":1}