acceptodds
Under review as a conference paper at ICLR 2027

Understanding Information Freshness in Reinforcement Learning under Diffusive Distribution Shift

Abstract

Reinforcement learning relies on past interactions with the environment, but distribution shift can change how useful historical data remain for current decisions. Existing nonstationary-RL models often measure the cumulative magnitude of environmental change. We introduce diffusive distribution shift, a natural model for many real-world systems whose dynamics evolve continually through stochastic changes that may accumulate, cancel, or revert over time. We establish a simple, quantitative information freshness principle: historical data should be retained until the decision error caused by changing dynamics becomes comparable to the statistical uncertainty reduced by keeping them. This principle yields explicit expressions for how long historical data remain useful and for the unavoidable cost of tracking changing dynamics. Guided by this principle, we develop optimistic model-based RL algorithms for both known and unknown diffusion rates. We prove matching upper and lower bounds, up to logarithmic factors, for the additional regret caused by distribution shift, establishing the minimax optimality of freshness-guided learning. Moreover, without knowing the diffusion rate in advance, our adaptive algorithm achieves the same regret rate, up to logarithmic factors, as the algorithm tuned with the true rate. Controlled experiments validate the predicted freshness mechanism, and a wind-storage study illustrates its decision-level consequences.

Primary area:
learning theory
Keywords:
reinforcement learning, information freshness, diffusive distribution shift, dynamic regret, minimax optimality

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_spZoOpenReview ↗
Rating
3
Confidence
2(−1)
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies how much historical data to retain in tabular reinforcement learning when transition dynamics change over time under a conditional second-moment displacement assumption. It develops FRESH-RESTART for a known diffusion rate and ADA-FRESH for an unknown rate, balancing statistical uncertainty against mismatch with the current dynamics. The main results provide dynamic-regret guarantees and lower bounds matching the stationary and diffusion-dependent terms. An additional initialization term remains for unrestricted kernels, while complete matching is obtained under bounded successor support. Controlled experiments examine the predicted scaling and algorithm behavior. A wind-storage study further illustrates the freshness principle using a separate empirical window selector.

Critical strengths
  1. The model captures a meaningful distinction from cumulative variation. Bounding displacement across temporal separations makes cancellation and return relevant. The paper appropriately treats this as a different minimax problem rather than a sharper guarantee for the same variation-budget class.

  2. The proof chain addresses important technical issues. Appendix F derives interval-diameter bounds, including at stopping-time starts. Appendix G separates sampling error from kernel mismatch and handles paused copies. Appendix K controls adaptive replay costs instead of simply applying the original MASTER theorem unchanged.

  3. The lower-bound construction belongs to the same model class. Random refreshes satisfy the displacement condition, and the survival MDP converts action-identification errors into multistep value loss. Revealing the diffusion rate and refresh times strengthens the result. Its two-successor rows support matching within the bounded-successor class.

  4. The experiments separate development and evaluation seeds, report uncertainty, retain startup episodes in the online-RL runs, and test the complementary roles of the two consistency tests. The authors also acknowledge that coupling the instance gap to ν\nu can produce a fourth-root slope without independently establishing a minimax lower bound.

Critical weaknesses

1 Matching the diffusion-dependent term does not establish complete regret matching for unrestricted kernels

Theorems 4.1 and 4.2 match the stationary and diffusion-dependent terms, including their parameter dependence. The discussion on page 6 explicitly acknowledges the remaining initialization gap, and Corollary 4.3 gives complete matching under bounded successor support. My concern is therefore with the broader wording in the abstract and introduction, particularly “minimax optimality of freshness-guided learning,” which can imply complete finite-sample matching for unrestricted kernels.

The additional term HS2AK/WνHS^2AK/W_\nu remains part of dynamic regret even though it originates from stationary MVP. For ν>0\nu>0, it is paid repeatedly and depends on ν\nu through the restart period. In the interior regime,

{KH^{3/2}(SA)^{1/4}\nu^{1/4}} =H^{1/2}S^{5/4}A^{1/4}\nu^{1/4},$$ which can substantially exceed one. Comparing initialization only with the diffusion-dependent term gives the approximate absorption condition $\nu\lesssim(H^2S^5A)^{-1}$, ignoring constants and logarithms. This is not a complete characterization: other regimes can be dominated by stationary learning or have both bounds reach order $HK$. An upper-bound cap alone does not establish matching. The initialization term also affects the window interpretation. For an arbitrary restart period, Appendix H gives the following per-episode upper-bound structure, before truncation and ignoring logarithms: $$H\sqrt{\frac{SA}{W}}+\frac{HS^2A}{W} +H^2\sqrt{\nu W}.$$ The proposed $W_\nu$ balances the first and third terms. When initialization matters, balancing the second and third instead gives $$W\asymp\left(\frac{S^2A}{H\sqrt{\nu}}\right)^{2/3}.$$ This alternative balance is not a minimax memory lower bound, but it shows that $W_\nu$ need not minimize the complete unrestricted finite-sample expression. Please distinguish matching of the diffusion-dependent leading term for unrestricted kernels from matching of the full regret bound under bounded successor support or where the extra term is absorbed. Clarifying these claims would suffice; resolving the general initialization gap is not necessary for acceptance. **2 “Optimal information lifetime” needs a more precise interpretation** Proposition 3.2 minimizes the explicitly heuristic objective $$J_\nu(W)=H\sqrt{\frac{SA}{W}}+H^2\sqrt{\nu W}.$$ The subsequent theorems justify a restart scale associated with the worst-case regret rate. They do not establish that restricting memory below $W_\nu$ necessarily worsens regret, or that observations older than $W_\nu$ are necessarily harmful. Such statements would require a specified class of memory-restricted algorithms and a corresponding necessity result. Assumption 2.1 is an upper bound on displacement, so easier processes belong to the same class. Older observations may also become relevant again when dynamics return to earlier regimes. In particular, the statements on page 5 that all available history remains useful at one boundary, or that retaining data across episodes provides no benefit at the other, are stronger than what optimizing the heuristic alone establishes. The random-refresh lower bound does not establish the same difficulty for every smooth diffusion or mean-reverting subclass. Appendix L already acknowledges potentially faster rates with additional structure. Likewise, Figure 1(a) uses balanced probes from both rows in each episode; it diagnoses estimation-window scaling rather than proving a necessary memory length under policy-dependent state-action visitation. Please distinguish the minimizer of the heuristic, an effective restart/comparison scale, and an intrinsic expiration age of historical information. The first two interpretations are supported. Clarifying the language is sufficient unless the authors intend the stronger necessity claim. **3 Experimental parameterization and the application selector need clearer specification** The controlled implementation follows the analyzed algorithmic structure: dyadic snapshots, the empirical-Bernstein backup, the multiscale schedule, and both tests. Safe-prefix stopping is appropriately confined to the proof. The remaining issue is how the numerical parameterization relates to the sufficient conditions. The proofs use sufficiently large universal constants, while Appendix M.1 reports a bonus multiplier of 0.1 and $$C(n)=\min\\{n,\sqrt n+2\\},$$ with constants selected on development seeds. Practical tuning is reasonable, but “evaluates the exact ... algorithms analyzed in the paper” should distinguish structural correspondence from a parameter instance covered by the theoretical guarantees. Please report the main rate experiment's confidence level $\delta$, $\eta(n)=C(n)/n$, the implemented $\hat\eta(n)$ and its logarithmic inflation, and the two test constants. State whether these are parameters satisfying the theoretical sufficient conditions or practical choices within the same algorithmic structure. I am not asking the authors to recover unspecified constants or prove that 0.1 is sufficiently large. Existing optimism and test-behavior diagnostics could help clarify what the implementation empirically supports. The wind-storage experiment uses another adaptive rule. Appendix M.2 explicitly distinguishes its empirical uncertainty-plus-mismatch selector from ADA-FRESH. This distinction should be visible in the main text. More importantly, the PDF does not define the score completely: the uncertainty and mismatch estimators, their normalization, the numerical weight, and the window-update rule are unspecified. Because this selector produces the application results, its definition is essential. Key engineering and cost parameters also need to be provided, or located explicitly in the supplementary code. The study is appropriately disclosed as simulated nonstationarity anchored to real energy data. It illustrates the principle but does not establish that the original DK1 time series satisfies Assumption 2.1. The operating-cost magnitude also needs clear context. Table 1 gives $$\frac{4.497935-4.493103}{4.497935-4.492430} \approx0.8777.$$ Thus, the reported 87.8% is the fraction of the cost gap between all-history estimation and the best fixed window that the selector closes. The best cost window is chosen retrospectively from the evaluated grid, with $W=112$; it is distinct from the controller that knows the current kernel. The raw cost reduction relative to all-history estimation is approximately 0.107%. Please present both quantities and their reference points together. These requests concern existing definitions, configurations, and claims. A larger benchmark suite is not necessary to establish the paper's theoretical value. **4 Additional Theoretical Clarification ** Theorem 5.1 should state that the bounded-support adaptive wrapper assumes a known numerical upper bound $d_0$. Appendix K already discloses this: the complexity function uses $b=\widetilde\Theta(d_0SA)$, which affects scheduling and test configuration. Not knowing $\nu$ or the successor sets does not imply that the wrapper needs no structural parameters. This is a clarification of the theorem's scope, not a newly identified proof error.
Questions for authors

Q1. Please distinguish matching of the diffusion-dependent leading term for unrestricted kernels from complete regret matching under bounded successor support or where initialization is absorbed. Is WνW_\nu intended to balance the leading statistical and displacement costs, or to minimize the full finite-sample expression including initialization?

Q2. Does “optimal information lifetime” mean the minimizer of JνJ_\nu, a restart scale achieving the relevant worst-case rate, or a necessity statement about retention length? If necessity is intended, which theorem and algorithm class establish it?

Q3. What confidence level, η\eta, η^\hat\eta, logarithmic inflation, and test constants are used in the main rate experiment? Please distinguish parameters satisfying the theoretical sufficient conditions from practical tuning of the same algorithmic structure.

Q4. Please define the wind-storage selector's complete score and update rule, provide the key engineering and cost parameters or their code location, and distinguish this selector from ADA-FRESH in the main text. Please also report the 87.8% fraction of the cost gap closed alongside the 0.107% raw cost reduction, with their respective reference points.

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

This paper studies nonstationary reinforcement learning under diffusive distribution shift, where the transition kernel PkP_k evolves across episodes and its conditional expected squared displacement in total variation over ℓ\ell episodes is bounded by νℓ\nu\ell (up to 11) for a diffusion rate ν\nu. Unlike variation budget models that sum every step of movement along a path, this condition allows stochastic changes to cancel or revert over time. To decide how many recent episodes WW to retain, the authors balance statistical uncertainty of order H∣S∣∣A∣/WH\sqrt{|S||A|/W} against kernel mismatch of order H2νWH^2\sqrt{\nu W}. Balancing these two costs gives an optimal information lifetime Wν≍∣S∣∣A∣/(Hν)W_\nu \asymp \sqrt{|S||A|}/(H\sqrt{\nu}) in the interior regime and a per episode regret cost of order H3/2(∣S∣∣A∣)1/4ν1/4H^{3/2}(|S||A|)^{1/4}\nu^{1/4}. Guided by this principle, the paper develops two optimistic model based algorithms built on MVP. When ν\nu is known, FRESH RESTART periodically restarts MVP every WνW_\nu episodes. When ν\nu is unknown, ADA FRESH combines MVP with the multiscale schedule and consistency tests of MASTER to adapt the memory length online without estimating ν\nu. Both algorithms achieve the same dynamic regret upper bound, matching the minimax lower bound up to logarithmic factors and d0d_0 under the bounded successor assumption where each state action pair has at most d0d_0 possible next states.

Critical strengths

This paper proposes a new nonstationary setting with a complete and thorough theoretical treatment. Rather than measuring nonstationarity through variation budgets or switching counts along the realized path, Assumption 2.1 bounds the conditional second moment of kernel displacement over ℓ\ell episodes by νℓ\nu\ell. This provides a natural model for random walk drift, mean reverting dynamics, and stochastic refreshes, where local changes can cancel or revert over time and where variation budget classes overcharge historical data that still approximate PkP_k well. For this class, the paper delivers a tight set of theoretical guarantees. Proposition 3.2 offers clear intuition through the information freshness principle, showing how statistical uncertainty and value mismatch determine the lifetime WνW_\nu and the ν1/4\nu^{1/4} regret scaling. Theorem 4.1 gives a dynamic regret upper bound for FRESH RESTART when ν\nu is known, separating stationary learning, distribution shift, and the MVP restart overhead. Theorem 4.2 proves a minimax lower bound with explicit constants and no burn in condition across all parameter regimes using a survival MDP with at most two possible next states per state action pair. Under the bounded successor assumption with at most d0d_0 possible next states (Corollary 4.3), the restart overhead is absorbed and the bounds match up to d0d_0 and logarithmic factors for every ν\nu, while Theorem 5.1 shows that ADA FRESH achieves the same bound without knowing ν\nu.

Critical weaknesses

The empirical rate results in Figure 1(b, c) are largely determined by how the benchmark instances are built as a function of ν\nu. Both the survival benchmark in Figure 1(b) and the revealed refresh diagnostic in Figure 1(c) use the least favorable calibration of the lower bound from Appendix M.1, which sets ν=qΔ2\nu = q\Delta^2 with refresh probability q∝H2Δ2/(∣S∣∣A∣)q \propto H^2\Delta^2/(|S||A|) and thus enforces Δ∝ν1/4\Delta \propto \nu^{1/4}. Because a suboptimal action increases the absorption probability by Δ\Delta, the per episode value loss of a mistake scales as H2ΔH^2\Delta and is directly coupled to ν1/4\nu^{1/4} by construction. As the appendix notes, under this calibration "even a nearly constant action error rate can inherit that slope from the instance gap." This same coupling governs the upper bound curves for FRESH RESTART and ADA FRESH in Figure 1(b) and explains why they lie on the ν1/4\nu^{1/4} reference line. Any nonlearning baseline that selects a wrong action with a roughly constant probability across ν\nu will automatically incur per episode regret proportional to H2Δ∝ν1/4H^2\Delta \propto \nu^{1/4} on these instances. A slope fit on logarithmic axes therefore cannot separate an algorithm that learns and adapts its memory from one that does not, so these experiments do not fully validate the theory.

Questions for authors

In Figure 1(b), the diffusive survival benchmark sets ν=qΔ2\nu = q\Delta^2 with refresh probability q=H2Δ2/(∣S∣∣A∣)q = H^2\Delta^2/(|S||A|), which forces the instance gap to scale as Δ∝ν1/4\Delta \propto \nu^{1/4} so that even a constant action error rate inherits the ν1/4\nu^{1/4} slope from the per episode loss H2ΔH^2\Delta. How do FRESH RESTART and ADA FRESH compare against an all history MVP baseline when the instance gap Δ\Delta is held fixed and ν\nu is varied solely through the refresh probability qq, and how does ADA FRESH scale across ν\nu in a setting where its short window comparison test also triggers?

Reviewer_Q99kOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper is about reinforcement learning.

This paper introduces diffusive distribution shift for real world system.

The principle information freshness is established, where old data should be kept until some requirement.

The authors propose model-based for two cases unknown and known diffusion rates.

The upper and lower bounds are shown to match upon log factors.

The algorithm is also adaptive to the case where rates are unknown.

Expreiments are provided to validate the algorithm.

Critical strengths

The results shown are great since the upper and lower bounds are shown to match upon log factors.

It is a great addition since the algorithm is also adaptive to the case where rates are unknown.

Critical weaknesses

It could be helpful if some proof or sketch is provided in the main text.

The citation of the literature is not complete.

Questions for authors

In the abstract, why does it state that reinforcement learning relies on past interactions with the environment? My understanding is that reinforcement learning can also learn through ongoing online interactions, where the agent continuously collects new data and updates its policy.

Could you clarify why the newly collected data is described as being generated under new dynamics? Shouldn't the environment's dynamics remain fixed if the environment itself has not changed?

Or does the term new dynamics refer to changes in the agent's policy or behavior, which may lead to different state transitions and experiences even when the underlying environment dynamics remain unchanged?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.