{"id":"48f10763-cd9e-4f38-ac5e-c3a26b69e4f2","arxiv_id":"2411.12786","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"AIPW estimators with nuisance estimates from no-regret online learning attain near-optimal finite-sample MSE for off-policy evaluation with adaptively collected data.","lead":"This paper proves finite-sample error bounds for treatment-effect estimators when the data were collected adaptively by an online algorithm. It shows that combining an augmented inverse propensity weighting estimator with online learning for the nuisance model reaches the statistically optimal error rate.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Optimality claim depends on uniform overlap; a single n^{-2}-propensity round makes the stated regret/MSE bound off the lower bound by a growing factor.","rationale":"The reader's weakest_assumption is exactly Assumption 1 (strict overlap, Eq. 3.14) plus known propensities. My stress test confirms this is the most load-bearing condition for the paper's central optimality claim. The concrete example shows that a single very rare target-action round makes the stated MSE upper bound diverge from the local minimax lower bound by a growing polynomial factor; the no-regret property as proved in Theorem 3.3 is simply not available when B is not a fixed constant. This is not an internal inconsistency in the derivations, but it is a substantive limitation of the advertised scope: the paper motivates itself with adaptive data collection and drifting overlap, yet the finite-sample optimality guarantee requires uniform overlap. The reader already marked the verdict CONDITIONAL partly for this reason, so I do not change the verdict. I agree with the reader's identification rather than offering a new objection. The concrete test is a direct simulation of the pathological instance, which would settle whether the looseness is only in the bound or in the actual performance of the proposed estimator.","tokens_in":34477,"tokens_out":17642,"duration_ms":179328,"concrete_test":"Run the tabular example above: X is a singleton, Y = mu* + epsilon with epsilon in {+1,-1} equally likely, mu*=0, binary actions, g(1)=1, g(0)=0, and behavioral policy pi*_1(action 1)=n^{-2}, pi*_i(action 1)=1/2 for i>=2. Implement Algorithm 3 (OGD) with F=[-1,1]^2 and Algorithm 1 for n in {10^2, 10^3, ..., 10^6}. Estimate the MSE of tau_hat_n by Monte Carlo (e.g., 10^4 replicates) and compare it with the lower bound v2_*/n ~ 1 and with the paper's upper bound from Theorem 3.2/3.3, approximately n^{2.5}. If the empirical MSE grows like n^2 or n^{2.5}, then the optimality claim fails whenever B is not fixed; if it stays bounded, the stated bounds are merely loose and the claim may survive with a refined regret analysis.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim -- that no-regret online learning attains the instance-dependent optimal MSE up to constants -- is only established under Assumption 1: |g/pi*_i| <= B with B a fixed constant. The regret guarantees in Theorems 3.3 and 3.4 scale as B^2 sqrt(n), while the lower bound v2_*/n can be much smaller when B is large. Concretely, take binary actions, g(1)=1, g(0)=0, mu*=0, sigma^2=1, and an adaptive policy with pi*_1(1)=n^{-2} and pi*_i(1)=1/2 for i>=2. Then B=n^2, v2_* = (1/n) E[g^2/(pi*_1)^2] + (1/n) sum_{i>=2} E[g^2/(pi*_i)^2] ~ n, so the lower bound is v2_*/n ~ 1. Theorem 3.3 gives Regret = O(B^2 sqrt(n)) = O(n^{4.5}); plugging into Theorem 3.2 yields an MSE upper bound of order n^{2.5}, far above the lower bound. Even a refined per-round regret bound of n^4 gives excess n^2. The paper itself notes in Section 3.5 that Assumption 1 is necessary for Theorems 3.3, 3.4, and the general function-approximation arguments. Thus the motivating challenge of drifting overlap is exactly the regime where the stated upper bounds do not prove optimality; the abstract's unqualified optimality claim is not supported when B is allowed to grow with n.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies estimation of a linear functional of the treatment effect (e.g., off-policy evaluation or average treatment effect) from adaptively collected contextual-bandit data. It analyzes a class of augmented inverse propensity weighting (AIPW) estimators whose nuisance treatment-effect estimates are produced by online learning algorithms. The main contributions are: (i) Theorem 3.1, a generic finite-sample MSE bound for AIPW estimators that exposes a sequentially weighted estimation error; (ii) Theorem 3.2, an oracle inequality connecting the MSE to the expected regret of an online non-parametric regression algorithm plus an approximation error; (iii) concrete regret bounds for tabular OGD (Theorem 3.3), linear OGD (Theorem 3.4), and general function approximation via online non-parametric regression (Appendix B.6); and (iv) Theorem 4.1, a local minimax lower bound of order v2*/n. The authors conclude that no-regret online learning attains instance-dependent optimality of AIPW in the large-sample regime.","tokens_in":34842,"tokens_out":13905,"duration_ms":145812,"significance":"If the main claims hold, the paper provides a clean and useful reduction: the estimation of a linear functional with adaptively collected data is controlled by a sequential weighted loss, and no-regret online regression yields finite-sample MSE bounds that match a local minimax lower bound up to lower-order terms. The strongest assets are Theorem 3.2, which is a compact and provable oracle inequality; the explicit tabular and linear OGD regret bounds; and the Le Cam lower bound that captures the variance v2*/n. The paper also ships proofs for the variance decomposition and for the local minimax argument. However, the optimality claim is only established under a strict-overlap assumption with a fixed constant B, and the tabular OGD result needs a convexity condition on F; these qualifications must be handled before the contribution can be assessed as fully valid.","major_comments":[{"comment":"The tabular OGD result does not state that the function class F is convex. Online gradient descent with projection requires F to be a closed convex set; for an arbitrary subset F of [-L,L]^{X×A}, the projection map Π_F is not well-defined in the sense used in Algorithm 3, and the standard OGD regret bound invoked in the proof (Theorem 3.1 of [18]) does not apply. The theorem and algorithm should explicitly assume F is closed and convex, or specify an alternative projection-based argument that handles nonconvex F.","section":"Section 3.5.1, Algorithm 3, Theorem 3.3"},{"comment":"The claimed instance-dependent optimality of no-regret online learning is only justified when the overlap constant B in Assumption 1 is fixed independently of n. If B is allowed to grow with n, the bounds degrade polynomially. For example, with binary actions, g(1)=1, g(0)=0, µ*=0, σ=1, and an adaptive policy with π*_1(1)=n^{-2} and π*_i(1)=1/2 for i≥2, Assumption 1 holds with B=n^2, v2*/n is of order n^2, while (3.13) with the regret bound (3.17) gives an MSE upper bound of order n^{2.5}. Thus the upper bound can be polynomially larger than the lower bound in the drifting-overlap regime that the introduction cites as a key motivation. The authors should qualify the optimality claim in the abstract and contributions to the strict-overlap regime, or extend the analysis to time-varying overlap.","section":"Abstract, Section 1.1, and Assumption 1 (Eq. 3.14)"},{"comment":"The KL-divergence computation in the proof of Lemma C.2 is not correct as written. The perturbation Γ_i(s) changes the outcome kernel at a single round i, so the log-likelihood ratio is nonzero only at that round; Eq. (C.23) displays a sum over all n rounds and uses the same index i for the perturbation and the summation. The argument is repairable because the single surviving term is bounded by n||σ||^2_(n), but the display should be corrected and the notation should distinguish the perturbed round from the summation index.","section":"Appendix C.3, Lemma C.2, Eq. (C.23)"}],"minor_comments":[{"comment":"The statement says B is a 'universal constant' but does not explicitly say B is independent of n and known to the algorithm. Please state this explicitly, since the later optimality discussion depends on B being fixed.","section":"Assumption 1, Eq. (3.14)"},{"comment":"Assumption 4 divides by ||σ||_(n). The degenerate case ||σ||_(n)=0 should be handled separately or excluded, otherwise the assumption and Lemma C.2 are not well-defined in that case.","section":"Assumption 4, Eq. (4.3)"},{"comment":"The 'general function approximation' instantiation is deferred entirely to the appendix, and Algorithm 5 is non-constructive because the relaxation R_n in Eq. (B.44) is generally not computable. The main text should state clearly what is and is not provided for this case, to avoid overclaiming an algorithmic instantiation.","section":"Section 3.5.3 and Appendix B.6"},{"comment":"The constant in the final lower bound of Lemma C.2 appears to be off by a factor of two relative to the standard Le Cam constant used in the proof (1/16 vs. 1/8). Please check the constants in the derivation from (C.27) to (C.28).","section":"Appendix C.3, Eq. (C.28)"}],"recommendation":"major_revision","confidential_remarks":"The paper's core decomposition and oracle inequality are sound, and the lower bound is a reasonable generalization of [42]. The main risk is the scope of the optimality claim: if the authors are willing to restrict the claim to fixed overlap constants, the missing convexity condition and the KL-divergence typo are local fixes. If they intend to cover drifting overlap, substantially new analysis is needed. I would suggest the editors ask for a careful revision that either extends the results to time-varying B or sharply qualifies the abstract and contributions."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: this paper gives the first non-asymptotic MSE bounds for AIPW estimators with adaptively collected data, via a reduction to online regression, plus a local minimax lower bound. The oracle inequality in Theorem 3.2 is the real contribution, and it is clean and correct. The lower bound is standard Le Cam but carefully adapted to the adaptive setting. The paper deserves a serious referee.\n\nThe variance decomposition in Proposition 3.1 is solid, and Theorem 3.1's reduction of the MSE to a sequentially weighted estimation error is exactly the right way to expose the effect of adaptivity. The reduction to online learning regret is elegant, and the proof of Theorem 3.2 checks out. The tabular and linear OGD regret bounds are standard, and the general function approximation section is honestly presented as non-constructive.\n\nSoft spots, in proportion:\n\n1. The abstract's 'instance-dependent optimality' claim is too strong. Theorems 3.3 and 3.4, and the general function approximation results, all require Assumption 1 with a fixed constant B. If overlap drifts so that B grows with n, the regret bounds scale polynomially in B while v2*/n can stay bounded. Concretely, a single round with selection probability n^{-2} gives B = n^2, v2*/n of order 1, and the Theorem 3.2 upper bound of order n^{2.5}. The paper itself states in Section 3.5 that Assumption 1 is necessary for the ensuing theorems, so the limitation is not hidden, but the abstract presents a result that the analysis does not support in the drifting-overlap regime.\n\n2. Theorem 3.3 uses the OGD update with projection onto a function class F, but standard OGD requires F to be convex. The paper never states that F is convex. This is a technical gap, easily fixed by adding the assumption or replacing the projection argument, but it should be fixed.\n\n3. The general function approximation subsection produces an algorithm that is not computable in general; the paper acknowledges this in Appendix B.6. So it is an existence result, not a practical instantiation.\n\nNone of these are fatal. The central oracle inequality and lower bound hold as stated, and the missing convexity is a minor repair. The optimality claim needs a caveat, not a withdrawal. I would accept this for peer review with major-minor revision, as the core ideas are original and the main technical machinery is sound.\n\nFor the reading group, yes, this is worth discussing. I would cite it in my own work on OPE, mainly for the Theorem 3.2 reduction.","headline":"A solid finite-sample oracle inequality and lower bound for OPE with adaptive data, but the advertised instance-dependent optimality is only proven under uniform overlap and the tabular analysis misses a convexity condition.","tokens_in":35320,"tokens_out":2600,"would_cite":true,"duration_ms":27240,"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":"With adaptively collected data, an AIPW estimator driven by a no-regret online learner achieves the instance-dependent optimal mean-squared error up to constants.","keywords":["off-policy evaluation","average treatment effect","adaptive data collection","AIPW estimator","online learning","online non-parametric regression","local minimax lower bound","contextual bandits"],"falsifier":"Simulate the tabular two-armed bandit with known propensities, bounded outcomes, and a fixed behavior policy so that $K=1$ in Eq. (4.1); at $n \\ge 10^5$, compare the empirical MSE of the OGD-based AIPW estimator (averaged over many replications) with the lower bound $C(K) v_*^2/n$ and the right-hand side of the oracle inequality (3.13). If the empirical MSE consistently falls below the minimax lower bound, the claimed optimality is wrong; if it exceeds the upper bound, the oracle inequality is wrong.","tokens_in":34286,"feed_emoji":"🎯","tokens_out":11404,"duration_ms":107972,"temperature":0.7,"pith_summary":"Estimating a linear functional of the treatment effect — the average treatment effect or the value of a target policy — becomes delicate when the data were collected adaptively, because the behavior policy changes with what has been seen. This paper proves finite-sample mean-squared-error bounds for augmented inverse propensity weighting (AIPW) estimators in that setting, showing the excess error is a sequentially weighted discrepancy between the true treatment effect and the estimates plugged into the scores. The central move is a reduction: obtain those estimates from an online non-parametric regression algorithm, so the discrepancy becomes the algorithm's regret plus an approximation error measured in a weighted norm. With a no-regret learner and a well-specified model class, the AIPW estimator matches the local minimax lower bound up to a constant, establishing that online learning is the right way to handle nuisance estimation under adaptivity.","feed_headline":"No-regret online learning makes AIPW estimation optimal","feed_subtitle":"Finite-sample bounds show the estimator matches the local minimax rate up to constants.","key_machinery":"The load-bearing object is the sequentially weighted $\\ell^2$-norm $\\|\\varphi\\|_{(n)}^2 := \\frac{1}{n}\\sum_{i=1}^n \\mathbb{E}_{I^*}\\left[ \\frac{g^2(X_i,A_i)\\,\\varphi^2(X_i,A_i)}{(\\pi_i^*)^2(X_i,O_{i-1};A_i)} \\right]$, which weights each round's squared error by the squared inverse propensity of the behavior policy. The AIPW scores are $\\hat\\Gamma_i := \\frac{g}{\\pi_i^*}(Y_i - \\hat\\mu_i) + \\langle g, \\hat\\mu_i\\rangle$, with $\\hat\\mu_i$ depending only on the past trajectory; Lemma B.1 shows these scores are unbiased and uncorrelated across rounds. The key reduction (Eqs. B.11–B.13) rewrites the MSE's excess term as the expected cumulative loss of the online learner minus the noise variance, then upper-bounds it by the learner's static regret plus the approximation error $\\inf_{\\mu\\in\\mathcal{F}} \\|\\mu-\\mu^*\\|_{(n)}^2$. Plugging in online gradient descent for the tabular and linear cases yields regret $O(B^2\\sqrt{n})$, and the general case follows the online non-parametric regression framework with sequential Rademacher complexity.","core_discovery":"The paper's central claim is an oracle inequality (Theorem 3.2) for the AIPW estimator: when the treatment-effect estimates $\\{\\hat\\mu_i\\}$ are produced by an online regression algorithm $\\mathcal{A}$ over a function class $\\mathcal{F}$, the mean-squared error satisfies $\\mathbb{E}_{I^*}[\\{\\hat\\tau_n - \\tau\\}^2] \\le \\frac{1}{n}\\left( v_*^2 + \\frac{1}{n}\\mathbb{E}_{I^*}[\\mathrm{Regret}(n,\\mathcal{F};\\mathcal{A})] + \\inf_{\\mu\\in\\mathcal{F}} \\|\\mu-\\mu^*\\|_{(n)}^2 \\right)$, where $v_*^2$ is the variance of an oracle AIPW estimator that knows $\\mu^*$, Regret is the static regret of the online learner against $\\mathcal{F}$, and the norm is the sequentially weighted $\\ell^2$-norm. Complementing this, Theorem 4.1 gives the local minimax lower bound $M_n(C_\\delta(I^*)) \\ge C(K)\\, v_*^2 / n$ over a neighborhood of problem instances. Together they show that no-regret online learning of the outcome model (Regret $= o(n)$) with a well-specified class achieves the instance-dependent optimal MSE up to a universal constant, generalizing the i.i.d. theory of [42] to adaptive data collection without cross-fitting. The paper instantiates the reduction in three cases: tabular models and linear function approximation via online gradient descent, and general function approximation via online non-parametric regression.","pith_inferences":["Because the weighting norm $\\|\\cdot\\|_{(n)}$ is defined through the actual adaptive behavior policy, the optimal variance $v_*^2$ is instance-dependent: the same estimator automatically adapts to how much exploration actually occurred, suggesting a principled way to account for the cost of exploration in adaptive experiments.","The uncorrelated-score property in Lemma B.1 suggests a direct route to anytime-valid inference: combined with time-uniform concentration bounds, the AIPW scores should yield confidence sequences for the ATE under adaptivity, an extension the paper does not develop.","The paper notes that the general function-approximation forecaster from the relaxation recipe is not directly computationally implementable in full generality; the reduction is therefore most immediately actionable through the OGD-based tabular and linear instantiations and through the constructive finite-class algorithms from the online regression literature.","The reduction only relies on regret and approximation error in the weighted norm, so other online learners (e.g., online mirror descent or online Newton step) should plug into the same oracle inequality unchanged, with their own regret rates determining the resulting MSE bound."],"forward_implications":["An AIPW estimator using any no-regret online regression algorithm for the outcome model achieves mean-squared error $v_*^2/n$ plus $o(1/n)$ when the model class is well specified, so efficient off-policy estimation is possible with adaptively collected data.","The estimator does not require cross-fitting; the online nature of the nuisance estimates automatically preserves the martingale structure of the AIPW scores, which are uncorrelated across rounds.","For tabular and linear outcome models, concrete rates follow: with OGD, the excess MSE is $O(B^2/\\sqrt{n})$ in the tabular case and $O(B^2 R(L+R)/\\sqrt{n})$ in the linear case.","For general function classes with sequential metric entropy exponent $p$, the excess MSE vanishes at rate $n^{-2/(p+2)}$ for $p<2$ and $n^{-1/p}$ for $p>2$, matching the minimax online-regression rates.","The local minimax lower bound identifies $v_*^2/n$ as the fundamental benchmark, so no alternative estimator can do better on all instances in a local neighborhood, up to a constant depending on the coverage $K$."],"supporting_citations":[{"why":"Supplies the i.i.d. counterpart of the analysis, including the weighted $\\ell^2$-norm framework and the local-neighborhood lower-bound strategy that this paper generalizes to adaptive data.","marker":"[42]"},{"why":"Supplies the online non-parametric regression minimax theory and the relaxation recipe used for the general function-approximation case.","marker":"[45]"},{"why":"Provides the online convex optimization regret bound used to analyze the OGD instantiations in Theorems 3.3 and 3.4.","marker":"[18]"},{"why":"Establishes semi-parametric efficiency of doubly robust estimators, the benchmark the paper aims to match non-asymptotically.","marker":"[6]"},{"why":"Motivates the adaptive weighting and drifting-overlap problem, and supplies the proximity-to-Markov condition used in the lower bound.","marker":"[67]"},{"why":"Supplies the data-generating procedure: contexts sampled i.i.d., actions from an adaptive policy, outcomes from a fixed kernel.","marker":"[26]"},{"why":"Provides the relaxation recipe that converts minimax regret bounds into forecasters in the general function-approximation setting.","marker":"[47]"}],"fun_headline_variants":["Online learning powers optimal off-policy estimation","No-regret learning gives minimax-optimal AIPW","Adaptive data: online learning achieves optimal estimates","AIPW meets its oracle via online regret bounds","Online learning closes the gap to minimax in OPE"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"All finite-sample guarantees assume strict overlap — the known propensities keep $|g/\\pi_i^*| \\le B$ almost surely — and the lower bound further assumes the adaptive policy stays within a constant factor $K$ of some reference Markov policy; if either constant degrades, the bounds blow up or the optimality claim loses its force.","fun_headline_variants_meta":{"raw":{"variants":["Online learning powers optimal off-policy estimation","No-regret learning gives minimax-optimal AIPW","Adaptive data: online learning achieves optimal estimates","AIPW meets its oracle via online regret bounds","Online learning closes the gap to minimax in OPE"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000463,"raw_usage":{"total_tokens":2402,"prompt_tokens":1122,"completion_tokens":1280,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":738,"completion_tokens_details":{"reasoning_tokens":1214}},"tokens_in":738,"tokens_out":1280,"duration_ms":8555,"temperature":1.0,"reasoning_tokens":1214,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T17:35:36.513249+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the tabular two-armed bandit with known propensities, bounded outcomes, and a fixed behavior policy so that $K=1$ in Eq. (4.1); at $n \\ge 10^5$, compare the empirical MSE of the OGD-based AIPW estimator (averaged over many replications) with the lower bound $C(K) v_*^2/n$ and the right-hand side of the oracle inequality (3.13). If the empirical MSE consistently falls below the minimax lower bound, the claimed optimality is wrong; if it exceeds the upper bound, the oracle inequality is wrong.","supporting_citations":[{"cited_title":"Off-policy estimation of linear functionals: Non-asymptotic theory for semi-parametric efficiency","cited_arxiv_id":"2209.13075","evidence_quote":"Supplies the i.i.d. counterpart of the analysis, including the weighted $\\ell^2$-norm framework and the local-neighborhood lower-bound strategy that this paper generalizes to adaptive data."},{"cited_title":"Online non-parametric regression","cited_arxiv_id":null,"evidence_quote":"Supplies the online non-parametric regression minimax theory and the relaxation recipe used for the general function-approximation case."},{"cited_title":"Introduction to online convex optimization","cited_arxiv_id":null,"evidence_quote":"Provides the online convex optimization regret bound used to analyze the OGD instantiations in Theorems 3.3 and 3.4."},{"cited_title":"Double/debiased machine learning for tre atment and structural parameters, 2018","cited_arxiv_id":null,"evidence_quote":"Establishes semi-parametric efficiency of doubly robust estimators, the benchmark the paper aims to match non-asymptotically."},{"cited_title":"Off-policy evaluation via adaptive weighting with data from contextual bandits","cited_arxiv_id":null,"evidence_quote":"Motivates the adaptive weighting and drifting-overlap problem, and supplies the proximity-to-Markov condition used in the lower bound."},{"cited_title":"Relax and ra ndomize: From value to algorithms","cited_arxiv_id":null,"evidence_quote":"Provides the relaxation recipe that converts minimax regret bounds into forecasters in the general function-approximation setting."}],"review_version":1}