{"id":"e1051315-bcff-4337-a1e6-f7f966e298dc","arxiv_id":"2504.16415","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A natural actor-critic algorithm for non-stationary average-reward MDPs achieves dynamic regret O~(sqrt(|S||A|) Delta_T^{1/6} T^{5/6}).","lead":"This paper introduces NS-NAC, a natural-actor-critic algorithm for reinforcement learning in environments where rewards and transition probabilities change over time, and proves a sublinear dynamic regret bound. It also gives a parameter-free variant and demonstrates the method in simulations.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition D.3's first inequality incorrectly drops the critic's Euclidean ball projection; the proof of the central regret bound is not valid as written.","rationale":"The reader's weakest assumption was the uniform lower bound C in Assumption 5.1, which is indeed a strong distributional restriction and limits applicability. However, the more load-bearing problem is internal to the proof: Proposition D.3's first displayed inequality is mathematically false because the ball projection Π_{R_Q} and the subspace projection Π_E do not commute. The algorithm projects the full Q_t update onto the Euclidean ball, while the analysis projects the error onto E and ignores the projection step. The numerical example in the attack satisfies the paper's stated bounds on R_Q, U_Q, and the TD increment, so the inequality fails in the regime the proof must cover. This gap sits at the root of the critic error bound, which is then used to bound the dominant regret terms. The concern is concrete and testable, and it is not a matter of disagreeing with an assumption; it is a missing argument in the proof of the central theorem. I do not recommend outright rejection because the projection error has magnitude O(α) and may well be repairable by adding extra terms to the recursion, but the current manuscript does not provide that argument. Hence the verdict should remain CONDITIONAL, with the condition being a corrected and complete proof of Proposition D.3 that accounts for the ball projection. I also note that the BORL proof in Appendix F appears to use inconsistent units for the restart count N per epoch (N = Δ_T^{5/6} T^{1/6} cannot be the number of restarts inside a W-step epoch), which further supports caution, but the projection gap is the single most load-bearing issue for the paper's main claim.","tokens_in":49177,"tokens_out":32222,"duration_ms":304850,"concrete_test":"Symbolically compute the exact first step of Proposition D.3: let x = Q_t + α(r_t - η_t + A(O_t)Q_t), y = Q_{t+1}^{π_{t+1}} ∈ E, and compare ||Π_E(Π_{R_Q}(x) - y)||^2 with ||Π_E(x - y)||^2. Use the explicit 2-D example in the attack (E = x-axis, R_Q = 1, y = (1,0), x = (0.95,0.3707)) to confirm the inequality fails. Then re-derive the critic recursion while carrying the exact projection term Π_E(Π_{R_Q}(x) - x); check whether this term can be bounded by O(α) per step and absorbed into the existing T√α term under α = (Δ_T/T)^{1/3}. If the extra term cannot be absorbed, Proposition D.3 and Theorem 5.3 are not established.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The central theorem 5.3 depends on Proposition D.3 (Appendix D.2), which bounds the critic error. Its proof begins by replacing the algorithm's projected update with the unprojected update: it asserts\n\n||Π_E[Q_{t+1} - Q_{t+1}^{π_{t+1}}]||^2 ≤ ||Π_E[Q_t + α(r_t - η_t + A(O_t)Q_t) - Q_{t+1}^{π_{t+1}}]||^2.\n\nThis treats Π_{R_Q} in Line 9 as if it commutes with Π_E or is otherwise harmless. It does not commute, and the inequality is false. Let E be the x-axis, R_Q=1, y=(1,0) ∈ E, and x=(0.95, 0.3707) with ||x||=1.019, which is feasible with Q_t within the ball and an α-sized TD increment. Then Π_{R_Q}(x) = x/1.019, and ||Π_E(Π_{R_Q}(x) - y)|| = 0.0683, while ||Π_E(x - y)|| = 0.05. The omitted projection error has E-component (1 - 1/||x||) x_E, which is nonzero and must be propagated through the ψ_t recursion. Because Proposition D.3 feeds the N√(H/α) and T√α terms of Theorem D.1, the regret bound is not established without a corrected treatment of this projection error. This is an internal proof gap in the main argument, not merely a restrictive assumption; the C-ratio condition in Assumption 5.1 is a separate concern about applicability, while this one invalidates the proof as written.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies infinite-horizon average-reward reinforcement learning in a non-stationary MDP where rewards and transition probabilities change under a total variation budget Δ_T. It proposes NS-NAC, a restart-based tabular natural actor-critic with softmax policy updates and a projected TD critic, and claims the first model-free policy-gradient dynamic regret bound of O~( |S|^{1/2}|A|^{1/2} Δ_T^{1/6} T^{5/6} ) under a uniform ergodicity assumption plus a ratio lower bound. A BORL wrapper is claimed to remove knowledge of Δ_T with the same regret. The analysis decomposes the regret into actor, critic, average-reward, Markov-noise, and nonstationarity terms; the main proof is in Appendix D. Simulations compare NS-NAC and BORL-NS-NAC with model-based and value-based baselines on synthetic switching MDPs.","tokens_in":49473,"tokens_out":13270,"duration_ms":133140,"significance":"If the bounds are correct, the paper fills a genuine gap: prior nonstationary RL theory focused on model-based or value-based methods, and this is the first policy-gradient method with a sublinear dynamic regret in the infinite-horizon average-reward setting with a single sample per environment. The appendix is detailed, the dominant-rate algebra in Theorem 5.3 is consistent with the stated α*, β*, N*, and the BORL argument is a reasonable adaptation of existing parameter-free frameworks. The paper also engages honestly with the lower bound and with the gap between its upper bound and the lower bound. However, the central proof has a substantive gap in the critic analysis (Proposition D.3), and some claimed extensions are asserted without proof; until these are fixed, the main theorem is not established.","major_comments":[{"comment":"The first inequality in the proof of Proposition D.3 replaces the projected critic update Q_{t+1}=Π_{R_Q}[Q_t+α(rt−ηt+A(Ot)Qt)] by its unprojected argument, i.e. it asserts ∥Π_E(Q_{t+1}−Q^{π_{t+1}}_{t+1})∥² ≤ ∥Π_E(Q_t+α(rt−ηt+A(Ot)Qt)−Q^{π_{t+1}}_{t+1})∥². This is not valid because Π_E and Π_{R_Q} do not commute. For example, with E the x-axis, R_Q=1, q=(1,0)∈E and x=(0.95,0.3707) with ∥x∥=1.019, we have ∥Π_E(Π_{R_Q}x−q)∥≈0.0683 while ∥Π_E(x−q)∥=0.05, so the asserted inequality fails in the direction used. The omitted projection error is not tracked in the ψ_t recursion, and Proposition D.3 supplies the critic-error terms N√(H/α) and T√α in Theorem D.1. A corrected argument must either show the projection is inactive under the stated step-size conditions or explicitly bound and propagate the projection error; as written, the proof of the main regret bound is incomplete.","section":"Appendix D.2, Proposition D.3, first inequality"},{"comment":"Proposition E.5 states the regret bound for NS-NAC with compatible linear function approximation, but its proof is explicitly omitted: the text says 'we choose not to repeat the proof here' and refers the reader to Wang et al. (2024). A citation is not a proof of the new nonstationary result. The function-approximation claim should either be proved in an appendix or removed from the stated contributions, since otherwise the manuscript claims an unverified result.","section":"Appendix E, Proposition E.5"},{"comment":"The choice N* = Δ_T^{5/6} T^{1/6} is presented as optimal for the regret bound, but the algorithm requires 0<N<T. Since the variation budget can be as large as Θ(T), for Δ_T larger than a constant multiple of T the stated N* exceeds T (e.g. Δ_T=2T gives N*≈1.78T), and the segment length H=⌊T/N⌋ need not be positive. The theorem needs an explicit regime condition such as Δ_T ≤ cT, or a modified choice of N*; otherwise the 'choosing optimal ...' statement is not valid in general.","section":"Theorem 5.3, parameter choice"},{"comment":"Assumption 5.1 bundles uniform ergodicity together with the ratio condition C = inf_{s,t,t',π} d^{π,P_t'}(s)/d^{π*_t,P_t}(s) > 0. This ratio condition is not a standard assumption and is used critically in Lemma D.6 to obtain the 1/C factors in Proposition D.2. The paper does not derive C from the stated ergodicity constants nor quantify its dependence on |S|, m, ρ, or T; since the O~(·) notation is claimed to hide only constants and logarithmic factors in T, an unquantified C could hide an exponential dependence. The authors should prove C>0 with explicit bounds from the preceding assumptions, state it as a separate nonstandard condition with its consequences, or remove the claim that Assumption 5.1 is standard.","section":"Assumption 5.1"}],"minor_comments":[{"comment":"The row 'This Work' in Table 1 reports O~(|S|^{1/2}|A|^{1/2} Δ_T^{1/9} T^{8/9}), which disagrees with Theorem 5.3's O~(|S|^{1/2}|A|^{1/2} Δ_T^{1/6} T^{5/6}); the table should be corrected.","section":"Appendix A, Table 1"},{"comment":"NS-NAC step-sizes and restarts are tuned by grid search while the baseline parameters are set using the theoretical expressions from their respective papers; this is not an apples-to-apples comparison and should be disclosed in the main text or replaced by a principled parameter choice for NS-NAC.","section":"Appendix G, simulation setup"},{"comment":"The label '(a) follows from Theorem D.1' refers to the inequality after the displayed decomposition, not to the decomposition itself; please relabel the steps so the derivation is unambiguous.","section":"Appendix F, proof of Theorem F.1"},{"comment":"There is a typographical error 'T√αß' immediately after step (c); this should read 'T√α'.","section":"Theorem D.1 proof"}],"recommendation":"major_revision","confidential_remarks":"The decisive issue is the invalid projection step in Proposition D.3; if it cannot be repaired, the paper's main theorem has no valid proof. The other issues—the function-approximation result without proof, the missing regime condition on N*, and the unquantified C-ratio condition—are also nontrivial. I do not see grounds to reject outright if the proof can be repaired, and the claimed contribution is relevant and novel for the journal. Please also verify that the related-work table's rate for the authors' own algorithm is corrected before acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the stress-test concern is right. In Proposition D.3, the proof replaces Q_{t+1} (projected onto the Euclidean ball) with the unprojected TD iterate and claims the Π_E-projected distance cannot increase. That is false. Take E as the x-axis, y=(1,0), x=(0.95,0.3707) with ||x||=1.019: the projected point is x/1.019 and the Π_E error is 0.0683 versus 0.05 for the unprojected x. Since this inequality feeds the critic bound that Theorem D.1 (and hence Theorem 5.3) relies on, the main dynamic regret guarantee is not established as written. This is load-bearing, not a cosmetic issue.\n\nNow the credit. The paper is the first model-free policy-based algorithm with a dynamic regret bound for non-stationary infinite-horizon average-reward MDPs, and that is a structural gap in the literature. The restart schedule and the Lyapunov argument with auxiliary Markov chains are a sensible template, and the tabular proof in Appendix D is lengthy and mostly self-contained. The authors also honestly flag the actor/critic norm mismatch that explains part of the gap to the lower bound. The BORL-NS-NAC extension is a standard bandit-over-RL wrapper, but it is clean.\n\nOther soft spots are smaller. Proposition E.5 on function approximation is asserted without proof; pointing to Wang et al. is not a proof, and that claim should be either proven or removed. The comparison table in Appendix A lists a different rate (Δ_T^{1/9} T^{8/9}) than Theorem 5.3's Δ_T^{1/6} T^{5/6}; probably a typo, but it needs fixing. Assumption 5.1's C = inf ratio is genuinely restrictive, but that is an applicability concern, not the thing that breaks the proof.\n\nVerdict: this deserves a serious referee, not a desk reject, because the novelty is real and the proof gap might be repairable with a careful accounting of the projection error. I would not cite the bound until the fix is verified. If you send it to review, ask the referees to focus on Appendix D.2 first.","headline":"NS-NAC's central regret bound rests on a false inequality that drops the critic projection; the paper is a genuinely novel first attempt but needs a corrected proof before the claims stand.","tokens_in":50051,"tokens_out":4634,"would_cite":false,"duration_ms":40762,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C40","68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"A restarted natural actor-critic provably achieves sublinear dynamic regret, $\\tilde{O}(|S|^{1/2}|A|^{1/2}\\Delta_T^{1/6}T^{5/6})$, in infinite-horizon average-reward non-stationary RL—the first such guarantee for a model-free policy-based…","keywords":["non-stationary reinforcement learning","average-reward MDP","natural policy gradient","actor-critic","dynamic regret","variation budget","restart-based exploration","bandit-over-RL"],"falsifier":"Engineer a two-state non-stationary MDP in which one action keeps the chain in a single state while the drifting optimal policy requires both states, so the ratio $C$ in Assumption 5.1 is exactly zero, run NS-NAC with the Theorem 5.3 parameters, and check whether dynamic regret stays sublinear; a linear regret growth would confirm the bound lives or dies by that ratio. As a second check, measure the empirical exponent of dynamic regret versus $T$ on the paper's synthetic benchmark: a scaling near $T^{5/6}$ supports the theorem, whereas a scaling near $T^{2/3}$ would suggest the gap to the lower bound is analysis slack.","tokens_in":48945,"feed_emoji":"🎯","tokens_out":14790,"duration_ms":112055,"temperature":0.7,"pith_summary":"The paper's aim is to bring policy-gradient methods—widely used in practice but without theory for changing environments—into the provably-correct regime for non-stationary reinforcement learning. It proposes NS-NAC, a two-timescale natural actor-critic that divides the horizon into segments, restarts exploration at each segment boundary, and sets its three learning rates as powers of the variation budget $\\Delta_T$, and it proves a dynamic regret bound of $\\tilde{O}(|S|^{1/2}|A|^{1/2}\\Delta_T^{1/6}T^{5/6})$ against the time-varying optimal policy. A companion algorithm, BORL-NS-NAC, tunes the same parameters through a bandit wrapper and attains the identical rate without knowing $\\Delta_T$ in advance. If the bound holds, model-free policy-based agents can provably chase a moving optimum with sublinear regret in the infinite-horizon average-reward setting, matching the guarantees previously available only to model-based or value-based methods.","feed_headline":"Policy gradients can chase shifting optima with sublinear regret","feed_subtitle":"A restarted natural actor-critic provably tracks changing rewards and dynamics, no model required.","key_machinery":"The argument is carried by a segment-anchored Lyapunov function, $W(\\pi_t) = \\sum_{s} d^{\\pi^*_{nH}, P_{nH}}(s)\\, D_{KL}(\\pi^*_{nH}(\\cdot|s)\\,\\|\\,\\pi_t(\\cdot|s))$, which measures the current softmax policy against the optimal policy frozen at the start of the segment; drift of this function gives the mirror-descent progress term, while the gap between frozen and current optima is charged to the variation budget through linear-programming and Lipschitz lemmas. Around that core, three mechanisms do fixed jobs: periodic restarts absorb the cost of forgetting stale estimates; an auxiliary Markov chain argument tames the Markovian noise when both the policy and the transition kernel drift; and the three learning rates $\\alpha, \\beta, \\gamma$ are interpreted as adapting factors that govern how quickly the agent discards the old environment in favor of the new one.","core_discovery":"NS-NAC tracks the drifting optimal policy by restarting the actor, critic, and average-reward estimates at the start of each of $N$ equal-length segments, so that within a segment the analysis can treat the environment as nearly stationary and the policy as converging toward a fixed anchor $\\pi^*_{nH}$ rather than a moving target. The central result, Theorem 5.3, decomposes dynamic regret into six sources—initialization, cumulative policy drift, critic error, average-reward estimation error, and two non-stationarity terms—and shows that the choices $\\alpha^* = \\gamma^* = (\\Delta_T/T)^{1/3}$, $\\beta^* = (\\Delta_T/T)^{1/2}$, and $N^* = \\Delta_T^{5/6} T^{1/6}$ balance them to yield $\\tilde{O}(|S|^{1/2}|A|^{1/2}\\Delta_T^{1/6}T^{5/6})$, with only logarithmic factors hidden. Theorem 6.1 extends the same rate to a parameter-free variant that runs EXP3.P over NS-NAC epochs. The proof adapts the stationary natural-policy-gradient Lyapunov analysis, with the auxiliary Markov chain technique modified so that drifting policies and drifting transition probabilities can both be handled.","pith_inferences":["Because the paper attributes the $T^{5/6}$-versus-$T^{2/3}$ gap to the mismatch between the actor's need for $\\|Q_t-Q^{\\pi_t}_t\\|$ and the critic's guarantee on its square, an improved stationary NAC analysis that closes this norm gap would very plausibly sharpen the non-stationary rate to $T^{2/3}$.","The uniform condition $C>0$ ranges over every policy and every environment rather than the algorithm's realized trajectory; a version that relaxes the infimum to reachable distributions, or inserts a short uniform-exploration phase, would be a testable weakening with the same rate.","Readers cross-checking the appendix should note an internal inconsistency: Table 1 lists this work's rate as $\\tilde{O}(\\Delta_T^{1/9}T^{8/9})$, while the abstract and Theorem 5.3 state $\\tilde{O}(\\Delta_T^{1/6}T^{5/6})$; the theorem is the authoritative statement.","The restart-and-bandit wrapper is a transferable recipe: any two-timescale policy method in a drifting environment could be wrapped with periodic resets and a bandit that tunes reset frequency, with the trade-off between exploration-for-change and exploitation quantified here."],"forward_implications":["Model-free policy-based algorithms gain provable sublinear dynamic regret under drift in rewards and transitions, closing a theoretical gap against model-based and value-based methods in the infinite-horizon average-reward setting.","The tuning rules $\\alpha^*=\\gamma^*=(\\Delta_T/T)^{1/3}$, $\\beta^*=(\\Delta_T/T)^{1/2}$, $N^*=\\Delta_T^{5/6}T^{1/6}$ give a concrete recipe: faster change demands larger step-sizes and more frequent restarts, trading exploitation for adaptation.","BORL-NS-NAC attains the same rate without knowing $\\Delta_T$, so the guarantee survives when the variation budget is unavailable in advance.","Under compatible linear function approximation the bound becomes $\\tilde{O}(d^{1/2}\\Delta_T^{1/6}T^{5/6}+d^{1/2}\\epsilon_{\\text{app}}T)$, extending the approach beyond tabular policies.","The analysis isolates the cost of non-stationarity as $\\tilde{O}(\\Delta_T^{1/3}T^{2/3}(1/\\sqrt{\\alpha}+1/\\sqrt{\\gamma}))$, pinpointing where the gap to the $\\Omega(|S|^{1/3}|A|^{1/3}\\Delta_T^{1/3}T^{2/3})$ lower bound arises."],"supporting_citations":[{"why":"Supplies the stationary natural-policy-gradient analysis—performance-difference lemma and mirror-descent drift—that the actor bound adapts to drifting environments.","marker":"Murthy & Srikant (2023)"},{"why":"Provides the two-timescale natural actor-critic finite-sample analysis whose rates the paper extends and compares against.","marker":"Khodadadian et al. (2022)"},{"why":"Contributes the two-timescale actor-critic toolbox: the squaring trick and the auxiliary Markov chain for Markovian noise.","marker":"Wu et al. (2020)"},{"why":"Lemma 2 gives the negative-semidefiniteness of $\\bar{A}^{\\pi,P}$ used throughout the critic analysis, plus the relative value function solution set.","marker":"Zhang et al. (2021b)"},{"why":"Source of the dynamic-regret lower bound quoted as Theorem 5.4 and of the bandit-over-RL parameter-free scheme reused in BORL-NS-NAC.","marker":"Mao et al. (2024)"},{"why":"Introduces the bandit-over-RL framework that BORL-NS-NAC adopts to tune step-sizes and restarts without knowing $\\Delta_T$.","marker":"Cheung et al. (2020)"},{"why":"Gives the EXP3.P regret bound that converts the bandit-tuning overhead into the logarithmic factor in Theorem 6.1.","marker":"Bubeck et al. (2012)"},{"why":"Provides the uniform-ergodicity perturbation inequalities behind Lemma D.26 on which the drifting-chain arguments rest.","marker":"Mitrophanov (2005)"},{"why":"Template for the single-loop NAC-with-compatible-function-approximation analysis used in Appendix E's extension.","marker":"Wang et al. (2024)"}],"fun_headline_variants":["Restart-based natural actor-critic tracks shifting RL environments","Model-free policy gradient for non-stationary average-reward RL","Provable sublinear regret for policy gradients in drifting MDPs","Parameter-free policy gradient adapts to variation budgets automatically"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Assumption 5.1 requires that the stationary distribution of every policy in every environment assigns enough probability to the states that the current optimal policy uses—the ratio $C$ must stay bounded away from zero—which is the step that ties the softmax normalization term to the optimal policy's advantage and underpins the choice of step-sizes and restart count.","fun_headline_variants_meta":{"raw":{"variants":["Restart-based natural actor-critic tracks shifting RL environments","Model-free policy gradient for non-stationary average-reward RL","Provable sublinear regret for policy gradients in drifting MDPs","Parameter-free policy gradient adapts to variation budgets automatically"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000358,"raw_usage":{"total_tokens":1991,"prompt_tokens":1050,"completion_tokens":941,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":666,"completion_tokens_details":{"reasoning_tokens":871}},"tokens_in":666,"tokens_out":941,"duration_ms":8403,"temperature":1.0,"reasoning_tokens":871,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:04:52.428677+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Engineer a two-state non-stationary MDP in which one action keeps the chain in a single state while the drifting optimal policy requires both states, so the ratio $C$ in Assumption 5.1 is exactly zero, run NS-NAC with the Theorem 5.3 parameters, and check whether dynamic regret stays sublinear; a linear regret growth would confirm the bound lives or dies by that ratio. As a second check, measure the empirical exponent of dynamic regret versus $T$ on the paper's synthetic benchmark: a scaling near $T^{5/6}$ supports the theorem, whereas a scaling near $T^{2/3}$ would suggest the gap to the lower bound is analysis slack.","supporting_citations":[{"cited_title":"T., Romberg, J., and Maguluri, S","cited_arxiv_id":null,"evidence_quote":"Provides the two-timescale natural actor-critic finite-sample analysis whose rates the paper extends and compares against."},{"cited_title":"Model-free nonstationary reinforcement learning: Near-optimal regret and applications in multiagent reinforcement learning and inventory control","cited_arxiv_id":null,"evidence_quote":"Source of the dynamic-regret lower bound quoted as Theorem 5.4 and of the bandit-over-RL parameter-free scheme reused in BORL-NS-NAC."},{"cited_title":"C., Simchi-Levi, D., and Zhu, R","cited_arxiv_id":null,"evidence_quote":"Introduces the bandit-over-RL framework that BORL-NS-NAC adopts to tune step-sizes and restarts without knowing $\\Delta_T$."},{"cited_title":"Regret analysis of stochastic and nonstochastic multi-armed bandit problems","cited_arxiv_id":null,"evidence_quote":"Gives the EXP3.P regret bound that converts the bandit-tuning overhead into the logarithmic factor in Theorem 6.1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the uniform-ergodicity perturbation inequalities behind Lemma D.26 on which the drifting-chain arguments rest."},{"cited_title":"Non-asymptotic analysis for single-loop ( N atural) actor-critic with compatible function approximation","cited_arxiv_id":null,"evidence_quote":"Template for the single-loop NAC-with-compatible-function-approximation analysis used in Appendix E's extension."}],"review_version":1}