- Rating
- 2
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
- Extends Hadiji et al.'s deterministic tracking bound to noisy/temporally correlated observations
- Cumulative squared tracking error: initial error + noise + target movement
- Matching Gaussian lower bounds
- Step-size adaptation via validation stream + synchronous tabular TD application
Critical strengths
- Main theorem, corollaries, and lower bounds correct (I worked through the math and checked)
- Lower bounds hold for all estimators, quantify cost of correlation
Critical weaknesses
- Contribution is smaller than presented due to large overlap with related works that are not clearly explained:
- deterministic part = Hadiji et al. Thm 2.1 with (generalizes Mokhtari et al., 2016)
- per-step tradeoff and tuned rate already in Cutler et al. (2023)
- rate under stochastic feedback (main claimed extension) already in Duvocelle et al. (2023)
- adaptation = exponential weights over a step-size grid (Zhang, Lu & Zhou, 2018; van Erven et al.); Hadiji et al. use the same
- uncited: Mokhtari et al., Duvocelle et al., aggregation literature, classical tracking (Benveniste et al.; Kushner & Yin; Guo & Ljung)
- Sahu et al. (2026): cited only as "the same stepsize tradeoff"; their Prop B.1 summed over time = Thm 3; policy-restricted lower bounds (Thm 3.9); contemporaneous, not counted
- genuinely new: , all-estimator lower bounds (Assouad), cumulative path variation combined with noise
- TD application and missing experiments:
- common invariant distribution across kernels (very restrictive)
- Section 4.4 condition fails in TD by , so direct smoothing wins
- no experiments, not even a small simulation
Questions for authors
- (Clarification) position against Duvocelle, Mokhtari, Zhang–Lu–Zhou, and the classical literature: what's new in Thms 3 and 9?
- (Clarification) compare Thm 3 with Sahu et al. Prop B.1 and Thm 3.7 (contemporaneous, not counted), you have cited Sahu even though it is a new paper so I would expect more comparison here with them.
- (Clarification) state that Thm 5 holds for all estimators vs. Sahu et al. Thm 3.9; discuss Chen, Wang & Wang (2019) and Besbes et al. (2015)
- (Clarification) when does adaptive TD beat direct smoothing? ()
- (Clarification) Assumption 2 with iterate-dependent noise ?
- (Future work) general-norm analysis (Moreau envelope) to drop the invariant-distribution assumption
- Suggestions: bound loose for random-walk drift (); add a scalar simulation; note the ~ constant gap
- Typos: incomplete references (pg 10, 11, 12)
7 comments
Response
Thank you for your detailed response and the work you have put in to the rebuttal process!
Some of these aren't accurate: Duvocelle et al already give a cumulative stochastic tracking bound, they have it detailed in Section 4.2, page 12, they define exactly the same type of tracking objective the authors have in their paper (Equations 20-25 should detail these.) They have some differences which you have built upon, but your current explanation of Duvocelle et all downplays how similar these papers are. A lot of these pieces are extensions build upon other work, which would be fine if the paper was really well written. As it stands, the paper doesn't do a good job of detailing the map from other works well and slightly leans on downplaying the novelty of some of these other papers to make their paper stand. Both Zhang and Hadiji's papers use adaptive algorithms. But I see that there is some difference here between the number of observations needed. The paper and this response don't clearly address why this method is better. Gaussian lower bound is a good contribution but that specific piece is not enough to get the paper accepted as it stands since it's not framed as the main contribution. The TD application is also less convincing. The common invariant-distribution assumption is very restrictive, the validation for it seems expensive, and the analysis does not establish why it is better than direct smoothing under equal sampling budgets. This rebuttal does clarify the scope of the paper beyond what the paper discusses but I think this paper needs significant rewrites and reframing to really make the contribution clear. I maintain my rating.
We thank the reviewer for the careful follow-up and the specific reference to Duvocelle et al.
1. Correction concerning Duvocelle et al. You are correct: In Section 4.2 Duvocelle et al. study tracking Nash equilibria, whereas we study fixed points of affine contractions. These formulations are closely related: the residual of a contractive affine map is strongly monotone, and its fixed point can be represented as the equilibrium of a quadratic game. We therefore agree that cumulative stochastic tracking itself is an established part of their work. Our comparison should focus on the precise operator and noise assumptions, the explicit dependence on temporal correlation, and the matching Gaussian lower bounds, rather than the distinction between Nash equilibria and fixed points.
2. Main contribution and framing. We acknowledge that deterministic contraction-based tracking bounds and independent-noise tracking rates have been studied previously. Our main contribution is to extend these guarantees to temporally correlated noise without requiring conditional unbiasedness, and to establish matching Gaussian lower bounds showing that the additional factor is unavoidable in the specified regimes. Importantly, these lower bounds apply to all estimators, even those that know the noise covariance and have access to future observations. Thus, our results establish when a constant-stepsize tracker achieves the minimax-optimal rate despite temporal correlation. We will revise the abstract, introduction, and related-work discussion to emphasize these contributions and clearly distinguish them from existing results.
3. Comparison with existing adaptive methods. We agree that Zhang et al. and Hadiji et al. already develop adaptive algorithms using expert aggregation. Our contribution is to establish a finite-time guarantee for combining affine fixed-point trackers with different stepsizes, without knowing the noise level or target variation. Specifically, our algorithm achieves cumulative tracking error close to that of the best fixed-stepsize tracker, using additional unbiased observations of the moving target to compare their performance. We will clarify both the contribution and the additional observation requirements in our comparison with prior work.
4. TD application and comparison with direct smoothing. Our TD application demonstrates how the general tracking guarantees can be applied to policy evaluation when rewards and transition dynamics change over time. We acknowledge that requiring a common invariant distribution restricts the allowed changes in transition kernels and that the additional validation observations increase the sampling cost. However, Section 4.4 identifies conditions under which operator tracking achieves a tighter theoretical error bound than direct smoothing. While our current TD analysis does not establish such an advantage under equal sampling budgets, it provides a concrete application of our theoretical framework. We will clarify these distinctions and limitations in the revised paper.
We appreciate that these concerns require substantive changes to the paper’s organization and positioning. We will add explicit comparisons of assumptions, feedback requirements, and guarantees alongside the corresponding results.
We thank the reviewer for checking the proofs and for the detailed suggestions. We clarify our contributions and limitations below.
1(a). Hadiji, Mokhtari, and Cutler. Hadiji et al. establish the deterministic tracking bound, building on Mokhtari et al.; Cutler et al. study the noise–drift tradeoff. Our contribution is a finite-time cumulative bound combining squared target variation with temporally correlated noise, without requiring conditional unbiasedness. Our Gaussian lower bounds show that the resulting rates are unavoidable in specified regimes.
1(b). Duvocelle et al. They study stochastic tracking in time-varying games using decreasing stepsizes and asymptotic rates. We provide an explicit finite-time constant-stepsize bound separating initialization, noise, and drift; allow temporally correlated noise without conditional unbiasedness; and establish Gaussian lower bounds applying to all estimators, even those using future observations. In particular, we prove the unavoidable τ2/3 correlation penalty in the matching regimes. Duvocelle et al. do not establish these lower bounds.
1(c). We agree that combining multiple algorithms using exponential weights is a well-established technique, studied by Zhang, Lu, and Zhou, van Erven and Koolen, and Hadiji et al. Our contribution is to apply this approach to stochastic tracking of affine fixed points and establish a finite-time guarantee showing that the combined estimator performs nearly as well as the best fixed-stepsize tracker, without knowing the noise level or target variation. This requires additional unbiased observations of the moving fixed point, which allow us to compare the trackers' prediction errors. We will clarify this distinction and expand our discussion of the classical tracking literature, including Benveniste et al., Kushner and Yin, and Guo and Ljung.
2. Sahu et al. Summing their Proposition B.1 yields the same-order initialization, noise, and squared-drift terms as our Theorem 3 for conditionally unbiased noise; their Theorem 3.7 also gives high-probability bounds under stronger noise assumptions. Our distinction is handling temporally correlated noise without conditional unbiasedness, with explicit dependence on the correlation parameter.
3. Prior lower bounds. Our Theorems 5 and 7 apply to all estimators, including those using future observations, whereas Sahu et al.'s Theorem 3.9 concerns constant-stepsize momentum algorithms. Besbes et al. (2015) and Chen–Wang–Wang (2019) derive minimax lower bounds under variation budgets on objective functions; we study moving fixed points and quantify the unavoidable cost of temporally correlated noise. We will acknowledge the classical independent-noise rate and clarify that our bounds match up to constants only in the stated ranges.
4. Adaptive TD versus smoothing. Section 4.4 shows a smaller operator-tracking noise term when τσ2/κ2<B2. With our TD noise upper bound and B=Vmax, we have σTD2/((1−γ)2B2)≥2γ2/(1−γ)2. Thus, for γ≥2−1, this bound cannot establish the condition. This does not prove that smoothing achieves smaller actual error, but our analysis does not demonstrate an advantage under equal sampling budgets. We will clarify this limitation.
5. Iterate-dependent noise. Assumption 2 allows noise depending on the current iterate. In TD, γ(Pt−Pt)vt has zero conditional mean because simulator transitions are sampled independently of the past. Bounded iterates also ensure a uniform conditional second-moment bound. Thus, Assumption 2 holds with τ=1. Correlated iterate-dependent noise would require separate verification of the covariance condition.
6. Common invariant distribution. A shared invariant distribution makes all TD Bellman operators contractive in the same weighted Euclidean norm, but restricts changes in transition kernels. Bellman operators remain contractions in the sup norm without this assumption. A general-norm analysis, potentially using Moreau-envelope techniques, could remove this restriction. We will highlight this extension.
7. Random-walk drift. Our bound allows arbitrary deterministic target movement. Independent, zero-mean random-walk increments may partially cancel, leading to tighter tracking bounds. Our analysis does not exploit this structure, and we will clarify this limitation.
8. Experiments, constants, and references. We will add scalar simulations comparing theoretical bounds with observed errors and operator tracking with fixed-gain and adaptive smoothing under equal sampling budgets. We will also acknowledge the approximately 4,000-fold gap between upper- and lower-bound constants and correct the incomplete references on pages 10–12.