acceptodds
Under review as a conference paper at ICLR 2027

Stochastic Tracking of Drifting Affine Fixed Points

Abstract

Policy evaluation in a changing environment requires tracking a value function that moves during learning. We study this problem through affine contractions whose fixed points change over time. For a constant step size, we bound the total expected squared tracking error in terms of the initial error, observation noise, and target movement. The result extends known deterministic bounds to observations that can be correlated across time. In a scalar Gaussian model, matching lower bounds identify when a suitably chosen step size achieves the best possible tracking rate and quantify the cost of temporal correlation. We also show how to combine trackers with different step sizes without knowing the noise level or target variation, using additional bounded, unbiased observations of the target. Finally, we apply the analysis to synchronous tabular temporal-difference learning with simulator access and a common invariant distribution, and quantify the extra sampling cost of adaptation.

Primary area:
learning theory
Keywords:
Fixed Point, Reinforcement Learning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_Q8XfOpenReview ↗
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 C=1−ηκC = 1-\eta\kappa (generalizes Mokhtari et al., 2016)
    • per-step tradeoff and tuned rate already in Cutler et al. (2023)
    • T(2+α)/3T^{(2+\alpha)/3} 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: τ\tau, 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 τσ2/κ2<B2\tau\sigma^2/\kappa^2 < B^2 fails in TD by ∼(1−γ)−2\sim(1-\gamma)^{-2}, 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? (τσ2/κ2≈2γ2Vmax⁡2/(1−γ)2>B2\tau\sigma^2/\kappa^2 \approx 2\gamma^2V_{\max}^2/(1-\gamma)^2 > B^2)
  • (Clarification) Assumption 2 with iterate-dependent noise γ(P^t−Pt)vt\gamma(\hat P_t - P_t)v_t?
  • (Future work) general-norm analysis (Moreau envelope) to drop the invariant-distribution assumption
  • Suggestions: bound loose for random-walk drift (Wσ2T\sqrt{W\sigma^2T}); add a scalar simulation; note the ~4,000×4{,}000\times constant gap
  • Typos: incomplete references (pg 10, 11, 12)
7 comments

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\tau^{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\tau\sigma^2/\kappa^2<B^2. With our TD noise upper bound and B=Vmax⁡B=V_{\max}, we have σTD2/((1−γ)2B2)≥2γ2/(1−γ)2\sigma_{\mathrm{TD}}^2/((1-\gamma)^2B^2)\ge 2\gamma^2/(1-\gamma)^2. Thus, for γ≥2−1\gamma\ge\sqrt{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, γ(P^t−Pt)vt\gamma(\widehat P_t-P_t)v_t 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\tau=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.

Reviewer_Q8XfOpenReview ↗

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 τ2/3\tau^{2/3} 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.

Reviewer_njoWOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies stochastic tracking of time-varying fixed points of contractive affine operators. It establishes a finite-time cumulative mean-squared error bound that separates initialization error, observation noise, and target drift. The paper also develops lower bounds for independent and temporally correlated Gaussian noise, proposes stepsize adaptation using additional unbiased target observations, and presents applications to synchronous TD learning and coupled recursions.

Critical strengths
  1. Clear and interpretable guarantees. The main bound explicitly characterizes the trade-off between noise suppression and tracking a moving target, with transparent dependence on the stepsize, contraction strength, and path variation.
  2. Well-organized theoretical development. The proofs and supporting results are presented systematically, making the main arguments reasonably easy to follow.
Critical weaknesses
  1. Limited justification of novelty. The main tracking bound closely builds on existing contraction-based analyses, while the dependence on target variation is familiar from sequence forecasting. The paper needs to explain more clearly what substantial technical difficulty it resolves.

  2. Strong feedback requirements for adaptation. The adaptive method requires additional observations that directly estimate the target. These observations also support simpler approaches, such as direct smoothing. Although the paper discusses this alternative, it does not establish the benefit of retaining the additional operator updates.

  3. Restricted optimality guarantees. The upper and lower bounds match only under specific parameter conditions. The results do not fully characterize performance across different levels of target movement and noise correlation.

  4. Limited practical justification. The temporal-difference learning application relies on restrictive sampling assumptions, and the validation observations introduce substantial additional cost. An advantage over simpler methods under the same sampling budget is not demonstrated.

  5. Insufficient evidence to resolve these concerns. Experiments are not mandatory for a theoretical paper, but targeted comparisons against direct and adaptive smoothing would help establish the value of the proposed method.

Questions for authors
  1. What is the main technical advance beyond existing contraction-based tracking results and standard stochastic error analysis?
  2. Can the adaptive method outperform direct smoothing or adaptive smoothing when all observation costs are included?
  3. Can stepsize adaptation be achieved using only the original operator observations, without additional target observations?
  4. Are the restrictions required for matching upper and lower bounds fundamental, or consequences of the proof techniques?
  5. Can the authors provide a concrete learning setting in which the method offers a clear benefit after accounting for validation costs?
3 comments

We thank the reviewer for the constructive feedback and for recognizing the clarity of our theoretical results.

1. Novelty and technical contributions. (Weakness 1; Question 1)

We agree that deterministic contraction tracking and the general noise–tracking tradeoff are well established. Our work makes three additional contributions. First, we establish an explicit finite-time tracking bound under temporally correlated noise, without requiring conditional unbiasedness. The main technical challenge is controlling the accumulated noise while preserving the deterministic squared-variation bound. Second, we establish finite-horizon Gaussian lower bounds for both independent and correlated noise. Third, we develop an adaptive algorithm that achieves a regret upper bound similar to the best fixed-stepsize tracker without knowing the noise or drift parameters, using additional target-validation observations. We also apply our framework to nonstationary TD learning and coupled two-timescale recursions. We will emphasize these contributions and clarify their differences from prior work.

2. Comparison with direct smoothing (Weakness 2; Question 2)

Section 4.4 already compares operator tracking with direct smoothing. We show that, for matched stepsizes, both methods have the same initialization and drift terms in their error bounds, while operator tracking has a smaller noise term when τσ2/κ2<B2\tau\sigma^2/\kappa^2<B^2. This does not necessarily imply smaller actual error or lower sampling cost. To strengthen the comparison, we will also include direct-smoothing methods in our adaptive algorithm. The resulting guarantee will compete with the best operator tracker or direct smoother, with only an additional 8B2log⁡28B^2\log 2 in the bound and no additional validation observations.

3. Adaptation without additional observations (Question 3).

In our scalar Gaussian model, operator observations can be transformed into noisy target observations, allowing adaptation without separate validation samples. For general affine operators, our current method requires additional unbiased target observations to compare trackers with different stepsizes. We are currently working on removing this requirement, using the surrogate-loss techniques of the paper "Minimizing Adaptive Regret with One Gradient per Iteration", which allow multiple experts to learn from a single gradient observation. Establishing theoretical guarantees for this approach is ongoing work.

4. Restrictions on the matching bounds (Weakness 3; Question 4).

Theorem 3 holds for every target variation WTW_T and every stepsize η∈(0,1]\eta\in(0,1]. The restrictions apply only to the matching lower bounds, where they ensure that our Gaussian lower-bound constructions are valid and the balancing stepsize is at most one. We do not claim these restrictions are fundamental. In fact, Section 4.3 shows that, for a fixed target and stepsize, the effect of temporal correlation eventually saturates rather than growing indefinitely with τ\tau. Therefore, different parameter regimes may exhibit different behavior. We will clarify that our minimax-optimality results concern the specified regimes.

5. Practical relevance and TD application (Weakness 4; Question 5).

Our TD application considers synchronous policy evaluation with simulator access and a common invariant distribution across transition kernels. One concrete example is evaluating a fixed policy when rewards change over time but transition dynamics remain fixed. We also allow transition kernels to change, provided they preserve the same invariant distribution. We acknowledge that these assumptions restrict the application. Moreover, the validation observations require an expected ∣S∣/(1−γ)|\mathcal S|/(1-\gamma) simulator calls per round, in addition to the TD updates. Our theoretical results quantify this cost but do not establish that the adaptive method outperforms direct smoothing under the same sampling budget. We will make these limitations clearer.

6. Numerical experiments (Weakness 5).

We agree that numerical comparisons would help demonstrate the significance of our theoretical findings. We will add experiments comparing our tracking method with adaptive smoothing, including comparisons under equal sampling budgets. We will also examine how closely the theoretical bound predicts actual tracking error for different levels of target variation and temporal correlation, including outside the ranges where the upper and lower bounds match.

We thank the authors for their detailed and constructive response. The rebuttal clarifies the scope of the matching upper and lower bounds, the assumptions underlying the TD application, and the additional sampling costs associated with target validation. These explanations address some of our concerns. However, the practical benefit of retaining operator tracking over direct smoothing, particularly under equal sampling budgets, remains insufficiently established. The proposed extensions and experiments are promising but have not yet provided concrete supporting evidence. Regarding novelty, we still believe that the contributions should be characterized cautiously, given their close connections to existing contraction-based tracking analyses and sequence estimation results. Overall, we maintain our original rating.

We thank the reviewer for reconsidering our response and acknowledging the clarifications.

We would like to emphasize that Section 4.4 already provides a theoretical comparison between operator tracking and direct smoothing. Specifically, we show that both methods have identical initialization and drift terms in their error bounds, while operator tracking achieves a smaller noise term whenever τσ2/κ2<B2\tau\sigma^2/\kappa^2<B^2. Thus, our analysis identifies conditions under which operator tracking provides a tighter theoretical guarantee than direct smoothing. Thus, our analysis provides a concrete theoretical motivation for using noisy operator evaluations rather than relying exclusively on direct smoothing of the target observations.

Regarding novelty, we acknowledge that deterministic tracking bounds and the general noise–drift tradeoff have been studied previously. However, we believe our main theoretical contribution goes beyond these results by allowing temporally correlated noise without conditional unbiasedness and establishing matching Gaussian lower bounds that quantify the unavoidable cost of temporal correlation, even for estimators with access to future observations. To our knowledge, this combination of guarantees is not established in the cited prior work.

We will revise the paper to distinguish these contributions more clearly from existing results. We appreciate the reviewer's constructive feedback.

Reviewer_mdwiOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how well a constant step-size update (i.e., fixed-gain filter) can track a moving fixed point, such as a value function in a changing environment, when it only sees noisy and possibly time-correlated evaluations. The main result bounds the total tracking error by three (intuitive) parts: the iniital error, the noise, and how much the target drifts in an L2 sense. With a well-tuned step size, lower bounds in a simple Gaussian toy setting show this error rate can't be beaten. They also study how corelated noise carries an unavoidable extra cost. To translate this into an algorithm, since the best step size depends on unknown noise and drift levels, they run several trackers with different step sizes in parallel and combine them using extra unbiased observations of the target. They also apply this to tabular TD learning with a simulator, although I have some questions about whether the assumptions are realistic.

Critical strengths
  1. A simple, well-posed central problem:
    1. Tracking the drifting fixed point of affine contractions is a clean abstraction that still covers RL policy evaluation in tabular TD-learning as a special case.
  2. An interpretable main bound:
    1. Theorem 3 splits the tracking error into three intuitive sources: initialization, noise, and target drift.
    2. This made the step-size trade-off (noise reduction vs. adaptation speed) explicit and easy to reason about.
  3. Matching lower bounds.
    1. In the scalar Gaussian model, the tuned constant-stepsize tracker is shown to be minimax-optimal up to constants.
    2. The sub-linear cost of temporal correlation is shown to be unavoidable, which seems quite novel to me.
  4. Accessible and self-contained presentation.
    1. Proofs are well-structured, constants are explicit, and the math is organized in an easy-to-follow way.
Critical weaknesses
  1. Regarding notations:
    1. It would be great if the authors could add a table of notations to the appendix. That makes looking up the term meanings much easier.
    2. The paper starts with F_t = M_t x_t + b_t before even defining each term or mentioning what the fixed point equation should actually be; even if you believe a notation is standard, it should at least be defined once before referencing.
    3. A one-line example (e.g., the Bellman map with M being gamma times P, and b being the reward) early on would help the readers see the RL connection head on.
  2. Regarding tightness and utility:
    1. The guarantees are in expectation, with "loose" constants, and are shown to be tight only within specific W ranges.
    2. This begs the question:"How well does Theorem 3 predict actual error in practice?".
      1. A simple simulation comparing the bound to observed error, including outside the matching range and in the long-correlation regime, would show whether the bound captures real failure modes.
  3. Connection to long-standing prior control literature:
    1. Linear Time Variant (LTV) systems were long studied in the area of control (dating back to the 60s or possibly earlier).
    2. Your setup seems awfully close to LMS and adaptive filtering; they had similar error recursion filters, and also modelled noises and system disturbances in similar fashion.
      1. In fact, such eta updates may be identical to what they refer to as fixed-gain filters.
    3. Beyond the single Kalman-style citation, please discuss what is new relative to that literature, ideally with an explicit correspondence (e.g., eta is filter-gain, W is process noise, sigma is measurement noise).
    4. To be clear, I'm not discounting the value of the work or saying that there is nothing novel here; that's not my point.
      1. I just want the paper to make those connections properly, say what's shared, and what's exactly new. You could even cite related famous theoretical results from the area to bolster the foundation of your work.
  4. The paper was quite enjoyable up to Theorem 3, but then took a turn for complexity.
    1. My over-simplified understanding of the flow is as follows; please correct me if I am woefully wrong in the rebuttals:
      1. Theorem 3 writes an eta-dependent trade-off as an explicit simple formula/model. Optimizing eta gives a tuned rate, and the lower bounds (Theorems 5 and 7) say no algorithm can beat this rate in a toy scalar Gaussian setup.
      2. Since the optimal eta depends on unknowns such as the noise level sigma or the drift W, you run about log(T) trackers in parallel with various step sizes, and let an exponential-weights meta-algorithm combine them.
        1. This sidesteps estimating sigma or W, but it needs extra direct peeks at the target (the validation oracle), which I see as the weak link.
    2. The adaptive layer seems like too direct of an attempt at translating Theorem 3 into a practical algorithm.
      1. If one already has bounded, unbiased observations of the moving target, simply smoothing those observations gives comparable bounds without any operator calls. You acknowledge this, yet do not establish an advantage over this baseline.
      2. In the temporal-difference application, these validation observations are not cheap: each one costs horizon-long (i.e., 1/(1-gamma)) simulator calls per state, and they additionally require the invariant distribution to be known.
    3. That makes me wonder what the right way to view the paper results must be:
      1. If this algorithm is intended as a practical method, the paper lacks the experimental/numerical evaluations needed to show it is practical.
      2. If it is intended as a theoretical result, adaptation from operator observations alone (without a validation oracle) would be the more compelling contribution.
Questions for authors

See the critical weaknesses.

In addition, about the temporal-differences/RL application, I couldn't exactly figure out the constraints on the transition dynamics kernel changes; I doubt that you allow any and all P changes throughout time. Could you please clarify those constraints, and whether they're realistic in RL settings? If they're not reasonably realistic assumptions, that pours cold water on the RL application; we've already given a pass to only focusing on tabular RL, so further unrealistic restrictions are tough to swallow.

1 comment

We thank the reviewer for the constructive comments and for recognizing the value of our tracking formulation and matching bounds.

1. Notation and RL example. We will add a notation table, define Mt,btM_t,b_t and xt∗=Mtxt∗+btx_t^*=M_tx_t^*+b_t before using them, and introduce the Bellman example Ft(v)=γPtv+rtF_t(v)=\gamma P_tv+r_t earlier.

2(a). Expectation bounds and constants. Our assumptions control second moments and temporal correlations, but not noise tails; high-probability guarantees would need stronger assumptions. The upper and lower bounds match in rate, not necessarily in numerical constants.

2(b). Range of tightness. Theorem 3 holds for all WTW_T and η∈(0,1]\eta\in(0,1]. The matching lower bounds apply only in the stated variation ranges, where the Gaussian constructions are valid and the balancing stepsize is at most one. We will clarify that minimax optimality is claimed only in these ranges.

2(c). Experiments. We agree that simulations would help assess the bound's numerical tightness. We will add scalar experiments comparing the bound with observed errors, including outside the matching ranges and with long-range correlations.

3. Connections to control and adaptive filtering. The error recursion is a stable linear time-varying system: η\eta is the fixed gain, WTW_T measures squared disturbance energy, and σ2\sigma^2 measures observation noise. The novelty is not the recursion or the qualitative noise–tracking tradeoff, but the following guarantees:

  • Kalman (1960) assumes a stochastic state-space model; our finite-time bound permits arbitrary deterministic fixed-point drift controlled by its squared variation.
  • Widrow et al. (1976) analyze LMS noise–tracking tradeoffs under particular stochastic models; we give an explicit cumulative-error bound for deterministic drift and temporally correlated noise, plus matching Gaussian lower bounds.
  • Guo and Ljung (1995) analyze tracking-error covariances for adaptive filters; we instead obtain nonasymptotic cumulative bounds and matching minimax rates, including a provably unavoidable correlation penalty in specified regimes.

We will add these comparisons and references to the revision.

4(a). Structure of the results. The reviewer summarizes the progression correctly: Theorem 3 gives the stepsize tradeoff, Theorems 5 and 7 establish matching rates in scalar Gaussian models, and Theorem 9 adapts across stepsizes using additional target observations. We will make the different feedback assumptions clearer.

4(b). Direct smoothing baseline. Section 4.4 already derives a bound for smoothing validation observations without operator calls. It shows that the operator-tracking upper bound has a smaller noise term when τσ2/κ2<B2\tau\sigma^2/\kappa^2<B^2. As stated there, this compares bounds, not actual errors, and does not prove a universal sampling advantage.

4(c). TD validation cost and μ\mu. We agree that validation costs an expected ∣S∣/(1−γ)|\mathcal S|/(1-\gamma) simulator calls per round. Producing these observations does not require knowing μ\mu. It is needed only by the stated adaptive method to compute squared prediction losses in the weighted norm ∣v∣μ2=∑sμ(s)v(s)2\\|v\\|_\mu^2=\sum_s\mu(s)v(s)^2 and update expert weights. Standard synchronous TD likewise does not require μ\mu.

4(d). Practical role and operator-only adaptation. The main upper and lower bounds use only noisy operator observations; the additional target observations are required only for Theorem 9's adaptive oracle inequality. We quantify their sampling cost rather than claim practical efficiency. Obtaining comparable adaptation from operator observations alone remains open in our general setting.

5(a). Exact restrictions on changing transition kernels.

The TD application assumes a deterministic sequence of transition kernels on a fixed state space, satisfying

\qquad\text{for every }t$$ for one full-support distribution $\mu$. This provides a common $L_2(\mu)$ norm in which all Bellman maps contract. The kernels need not be reversible or close at consecutive rounds, although larger value-function movement increases the error bound. **5(b). Relevance and limitations of these restrictions.** The assumption covers fixed transition dynamics with changing rewards, as well as structured transition changes. For example, $P_t=(1-a_t)I+a_tP$ preserves the invariant distribution of $P$ while allowing the probability of remaining in place to change; mixtures of kernels sharing $\mu$ are also admissible. We agree that this does not cover arbitrary changing environments or policies. We will present the TD result explicitly as an application to this restricted class and explain these examples and limitations.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.