Pith. sign in

REVIEW 4 major objections 4 minor 59 references

Natural Policy Gradient for Average Reward Non-Stationary RL

T0 review · 4 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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…

desk verdict 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. read the letter →

arxiv 2504.16415 v1 pith:KRIEML4U submitted 2025-04-23 cs.LG stat.ML

Neharika Jali , Eshika Pathak , Pranay Sharma , Guannan Qu , Gauri Joshi This is my paper · ORCID
classification cs.LGstat.ML MSC 90C4068Q32
keywords non-stationaryreinforcementlearningaverage-rewardMDPnaturalpolicygradientactor-criticdynamicregretvariationbudgetrestart-basedexplorationbandit-over-RL
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 4 minor

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.

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 (4)
  1. [Appendix D.2, Proposition D.3, first inequality] 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.
  2. [Appendix E, Proposition E.5] 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.
  3. [Theorem 5.3, parameter choice] 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.
  4. [Assumption 5.1] 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.
minor comments (4)
  1. [Appendix A, Table 1] 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.
  2. [Appendix G, simulation setup] 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.
  3. [Appendix F, proof of Theorem F.1] 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.
  4. [Theorem D.1 proof] There is a typographical error 'T√αß' immediately after step (c); this should read 'T√α'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the dynamic regret bound is derived from stated assumptions and compared with external lower bounds; no fitted parameter is relabeled as a prediction.

full rationale

The paper's central claim, Theorem 5.3, is derived, not fitted: the regret bound is obtained by decomposing Dyn-Reg into I1 (suboptimality of the learned policy) and I2 (Markov sampling bias), bounding I1 via a Lyapunov/NPG argument (Proposition D.2) that depends on Assumption 5.1's uniform ergodicity and the C-ratio, bounding the critic error through a TD-style recursion (Proposition D.3), and bounding the average-reward estimation error through a similar recursion (Proposition D.5). The step-sizes alpha*, beta*, gamma* and restart count N* in Theorem 5.3 are chosen by analytically minimizing the displayed bound, not by fitting to data; the empirical grid search in Section 8 is explicitly a tuning exercise and does not feed back into the theorem. The only self-citation (Jali et al., 2024) appears in the introduction as a motivating application, not as a load-bearing premise. External citations (Zhang et al., 2021b for Lemma 5.2; Murthy & Srikant, 2023 for the stationary NPG analysis; Wu et al., 2020 for the auxiliary-chain and squaring tricks; Mao et al., 2024 for the lower bound and BORL framework) are used as standard building blocks and are not the source of the paper's claims. The reviewer-identified issue in Proposition D.3 (dropping the Euclidean projection in the critic recursion) is a potential proof gap, but it is not an instance of a prediction reducing to its inputs or of a self-citation chain forcing the result; therefore it does not affect the circularity score.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The central bound rests on uniform ergodicity, bounded rewards, the TD fixed-point structure, and knowledge of Delta_T. No new physical entities are introduced; the step sizes and restart count are analytically optimized hyperparameters.

free parameters (3)
  • Actor step-size beta = beta* = (Delta_T/T)^{1/2}
    Analytically optimized in Theorem 5.3 to balance regret terms; not fitted to data, but the bound and tuning both depend on this value.
  • Critic and average-reward step-sizes alpha, gamma = alpha* = gamma* = (Delta_T/T)^{1/3}
    Analytically optimized in Theorem 5.3; the proof requires a two-timescale separation and the regret depends on these choices.
  • Restart count N = N* = Delta_T^{5/6} T^{1/6}
    Analytically optimized in Theorem 5.3 to trade exploration-for-change against learning within each segment.
assumptions (4)
  • domain assumption Uniform ergodicity and the stationary-distribution ratio lower bound C > 0 (Assumption 5.1).
    Used throughout the proof to bound Markovian noise, stationary-distribution mismatch, and the softmax advantage term; the proof collapses without it.
  • domain assumption Rewards are bounded in magnitude by U_R.
    Used to bound Q-functions, regrets, variance terms, and projection radius R_Q; standard but necessary.
  • standard math The TD limiting matrix A-bar is negative semidefinite and its pseudo-inverse norm is bounded (Lemma 5.2 from Zhang et al. 2021b).
    Invoked to ensure critic error contracts and to set projection radius R_Q = 2 U_R lambda^{-1}.
  • domain assumption The variation budget Delta_T is known to NS-NAC.
    The step-sizes and restart count are functions of Delta_T; BORL-NS-NAC removes this assumption.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Natural Policy Gradient for Average Reward Non-Stationary RL." pith.science (2026). https://pith.science/paper/KRIEML4U

@misc{pith2026250416415,
  author       = {Pith},
  title        = {Pith review of: Natural Policy Gradient for Average Reward Non-Stationary RL},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KRIEML4U}},
  note         = {Machine review of arXiv:2504.16415}
}
abstract

We consider the problem of non-stationary reinforcement learning (RL) in the infinite-horizon average-reward setting. We model it by a Markov Decision Process with time-varying rewards and transition probabilities, with a variation budget of $\Delta_T$. Existing non-stationary RL algorithms focus on model-based and model-free value-based methods. Policy-based methods despite their flexibility in practice are not theoretically well understood in non-stationary RL. We propose and analyze the first model-free policy-based algorithm, Non-Stationary Natural Actor-Critic (NS-NAC), a policy gradient method with a restart based exploration for change and a novel interpretation of learning rates as adapting factors. Further, we present a bandit-over-RL based parameter-free algorithm BORL-NS-NAC that does not require prior knowledge of the variation budget $\Delta_T$. We present a dynamic regret of $\tilde{\mathscr O}(|S|^{1/2}|A|^{1/2}\Delta_T^{1/6}T^{5/6})$ for both algorithms, where $T$ is the time horizon, and $|S|$, $|A|$ are the sizes of the state and action spaces. The regret analysis leverages a novel adaptation of the Lyapunov function analysis of NAC to dynamic environments and characterizes the effects of simultaneous updates in policy, value function estimate and changes in the environment.

Figures

Figures reproduced from arXiv: 2504.16415 by the authors.

Figure 1
Figure 1. Performance of NS-NAC and baseline algorithms across various settings. (a) Dynamic regret for a single instance [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Log-log plots showing the effect of varying: (a) number of states [PITH_FULL_IMAGE:figures/full_fig_p041_2.png] view at source ↗
Figure 4
Figure 4. Performance of NS-NAC and baseline algorithms in various non-stationary settings. (a) Dynamic regret for a single instance over T = 1 × 104 steps in an environment with 50 abrupt, randomly scheduled switches. (b) Dynamic regret for a single instance over T = 1 × 104 steps in an environment with small, continuous changes. Additional Environments. We conducted further experiments to evaluate the adaptability of NS-NAC… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

59 extracted references · 50 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    M., Lee, J

    Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. On the theory of policy gradient methods: optimality, approximation, and distribution shift. Journal of Machine Learning Research, 2021

    work page 2021

  3. [3]

    U., and Aggarwal, V

    Bai, Q., Mondal, W. U., and Aggarwal, V. Regret analysis of policy gradient algorithm for infinite horizon average reward markov decision processes. In AAAI Conference on Artificial Intelligence, 2024

    work page 2024

  4. [4]

    First-order methods in optimization

    Beck, A. First-order methods in optimization. SIAM, 2017

    2017

  5. [5]

    Stochastic multi-armed-bandit problem with non-stationary rewards

    Besbes, O., Gur, Y., and Zeevi, A. Stochastic multi-armed-bandit problem with non-stationary rewards. Neural Information rocessing systems, 27, 2014

    work page 2014

  6. [6]

    S., Ghavamzadeh, M., and Lee, M

    Bhatnagar, S., Sutton, R. S., Ghavamzadeh, M., and Lee, M. Natural actor-critic algorithms. Automatica, 2009

    work page 2009

  7. [7]

    Regret analysis of stochastic and nonstochastic multi-armed bandit problems

    Bubeck, S., Cesa-Bianchi, N., et al. Regret analysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 2012

    work page 2012

  8. [8]

    Fast global convergence of natural policy gradient methods with entropy regularization

    Cen, S., Cheng, C., Chen, Y., Wei, Y., and Chi, Y. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 2022

    work page 2022

Show all 59 references
  1. [9]

    Optimizing for the future in non-stationary mdps

    Chandak, Y., Theocharous, G., Shankar, S., White, M., Mahadevan, S., and Thomas, P. Optimizing for the future in non-stationary mdps. In International Conference on Machine Learning, 2020

    2020

  2. [10]

    Stabilizing reinforcement learning in dynamic environment with application to online recommendation

    Chen, S.-Y., Yu, Y., Da, Q., Tan, J., Huang, H.-K., and Tang, H.-H. Stabilizing reinforcement learning in dynamic environment with application to online recommendation. In ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, 2018

    2018

  3. [11]

    and Zhao, L

    Chen, X. and Zhao, L. Finite-time analysis of single-timescale actor-critic. Neural Information Processing Systems, 2023

    2023

  4. [12]

    C., Simchi-Levi, D., and Zhu, R

    Cheung, W. C., Simchi-Levi, D., and Zhu, R. Learning to optimize under non-stationarity. In International Conference on Artificial Intelligence and Statistics, 2019

    2019

  5. [13]

    C., Simchi-Levi, D., and Zhu, R

    Cheung, W. C., Simchi-Levi, D., and Zhu, R. Reinforcement learning for non-stationary markov decision processes: The blessing of (more) optimism. In International Conference on Machine Learning, 2020

    2020

  6. [14]

    C., Simchi-Levi, D., and Zhu, R

    Cheung, W. C., Simchi-Levi, D., and Zhu, R. Nonstationary reinforcement learning: The blessing of (more) optimism. Management Science, 2023

    2023

  7. [15]

    A kernel-based approach to non-stationary reinforcement learning in metric spaces

    Domingues, O., Menard, P., Pirotta, M., Kaufmann, E., and Valko, M. A kernel-based approach to non-stationary reinforcement learning in metric spaces. In International Conference on Artificial Intelligence and Statistics, 2021

    2021

  8. [16]

    M., and Mansour, Y

    Even-Dar, E., Kakade, S. M., and Mansour, Y. Online markov decision processes. Mathematics of Operations Research, 2009

    2009

  9. [17]

    Dynamic regret of policy optimization in non-stationary environments

    Fei, Y., Yang, Z., Wang, Z., and Xie, Q. Dynamic regret of policy optimization in non-stationary environments. Neural Information Processing Systems, 2020

    2020

  10. [18]

    Non-stationary reinforcement learning under general function approximation

    Feng, S., Yin, M., Huang, R., Wang, Y.-X., Yang, J., and Liang, Y. Non-stationary reinforcement learning under general function approximation. In International Conference on Machine Learning, 2023

    2023

  11. [19]

    A sliding-window algorithm for markov decision processes with arbitrarily changing rewards and transitions, 2018

    Gajane, P., Ortner, R., and Auer, P. A sliding-window algorithm for markov decision processes with arbitrarily changing rewards and transitions, 2018

    2018

  12. [20]

    and Moulines, E

    Garivier, A. and Moulines, E. On upper-confidence bound policies for non-stationary bandit problems. arXiv preprint arXiv:0805.3415, 2008

    2008 arXiv

  13. [21]

    Transient non-stationarity and generalisation in deep reinforcement learning

    Igl, M., Farquhar, G., Luketina, J., Boehmer, W., and Whiteson, S. Transient non-stationarity and generalisation in deep reinforcement learning. arXiv preprint arXiv:2006.05826, 2020

    2006 arXiv

  14. [22]

    Near-optimal regret bounds for reinforcement learning

    Jaksch, T., Ortner, R., and Auer, P. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 2010

    2010

  15. [23]

    Efficient reinforcement learning for routing jobs in heterogeneous queueing systems

    Jali, N., Qu, G., Wang, W., and Joshi, G. Efficient reinforcement learning for routing jobs in heterogeneous queueing systems. In International Conference on Artificial Intelligence and Statistics, 2024

    2024

  16. [24]

    Jia, S., Xie, Q., Kallus, N., and Frazier, P. I. Smooth non-stationary bandits. In International Conference on Machine Learning, 2023

    2023

  17. [25]

    and Qian, P

    Kanoria, Y. and Qian, P. Blind dynamic resource allocation in closed networks via mirror backpressure. Management Science, 2024

    2024

  18. [26]

    Towards continual reinforcement learning: A review and perspectives

    Khetarpal, K., Riemer, M., Rish, I., and Precup, D. Towards continual reinforcement learning: A review and perspectives. Journal of Artificial Intelligence Research, 2022

    2022

  19. [27]

    R., Varma, S

    Khodadadian, S., Jhunjhunwala, P. R., Varma, S. M., and Maguluri, S. T. On the linear convergence of natural policy gradient algorithm. In IEEE Conference on Decision and Control, 2021

    2021

  20. [28]

    T., Romberg, J., and Maguluri, S

    Khodadadian, S., Doan, T. T., Romberg, J., and Maguluri, S. T. Finite-sample analysis of two-time-scale natural actor--critic algorithm. IEEE Transactions on Automatic Control, 2022

    2022

  21. [29]

    Konda, V. R. and Tsitsiklis, J. N. On actor-critic algorithms. SIAM Journal on Control and Optimization, 2003

    2003

  22. [30]

    Improved regret bound and experience replay in regularized policy iteration

    Lazic, N., Yin, D., Abbasi-Yadkori, Y., and Szepesvari, C. Improved regret bound and experience replay in regularized policy iteration. In International Conference on Machine Learning, 2021

    2021

  23. [31]

    and Rachelson, E

    Lecarpentier, E. and Rachelson, E. Non-stationary markov decision processes, a worst-case approach using model-based reinforcement learning. Neural Information Processing Systems, 2019

    2019

  24. [32]

    Pausing policy learning in non-stationary reinforcement learning

    Lee, H., Jin, M., Lavaei, J., and Sojoudi, S. Pausing policy learning in non-stationary reinforcement learning. In International Conference on Machine Learning, 2024

    2024

  25. [33]

    Rl-qn: A reinforcement learning framework for optimal control of queueing systems

    Liu, B., Xie, Q., and Modiano, E. Rl-qn: A reinforcement learning framework for optimal control of queueing systems. ACM Transactions on Modeling and Performance Evaluation of Computing Systems, 2022

    2022

  26. [34]

    A definition of non-stationary bandits

    Liu, Y., Kuang, X., and Van Roy, B. A definition of non-stationary bandits. arXiv preprint arXiv:2302.12202, 2023 a

    2023 arXiv

  27. [35]

    Nonstationary bandit learning via predictive sampling

    Liu, Y., Van Roy, B., and Xu, K. Nonstationary bandit learning via predictive sampling. In International Conference on Artificial Intelligence and Statistics, 2023 b

    2023

  28. [36]

    Average reward reinforcement learning: Foundations, algorithms, and empirical results

    Mahadevan, S. Average reward reinforcement learning: Foundations, algorithms, and empirical results. Machine learning, 1996

    1996

  29. [37]

    Model-free nonstationary reinforcement learning: Near-optimal regret and applications in multiagent reinforcement learning and inventory control

    Mao, W., Zhang, K., Zhu, R., Simchi-Levi, D., and Basar, T. Model-free nonstationary reinforcement learning: Near-optimal regret and applications in multiagent reinforcement learning and inventory control. In Management Science, 2024

    2024

  30. [38]

    New insights and perspectives on the natural gradient method

    Martens, J. New insights and perspectives on the natural gradient method. Journal of Machine Learning Research, 2020

    2020

  31. [39]

    Mitrophanov, A. Y. Sensitivity and convergence of uniformly ergodic markov chains. Journal of Applied Probability, 2005

    2005

  32. [40]

    and Srikant, R

    Murthy, Y. and Srikant, R. On the convergence of natural policy gradient and mirror descent-like policy methods for average-reward mdps. In 2023 62nd IEEE Conference on Decision and Control (CDC), 2023

    2023

  33. [41]

    Performance bounds for policy-based average reward reinforcement learning algorithms

    Murthy, Y., Moharrami, M., and Srikant, R. Performance bounds for policy-based average reward reinforcement learning algorithms. Neural Information Processing Systems, 2023

    2023

  34. [42]

    Bridging the gap between value and policy based reinforcement learning

    Nachum, O., Norouzi, M., Xu, K., and Schuurmans, D. Bridging the gap between value and policy based reinforcement learning. Neural Information Processing Systems, 2017

    2017

  35. [43]

    Variational regret bounds for reinforcement learning

    Ortner, R., Gajane, P., and Auer, P. Variational regret bounds for reinforcement learning. In Uncertainty in Artificial Intelligence, 2020

    2020

  36. [44]

    A survey of reinforcement learning algorithms for dynamically varying environments

    Padakandla, S. A survey of reinforcement learning algorithms for dynamically varying environments. ACM Computing Surveys (CSUR), 2021

    2021

  37. [45]

    and Papadimitriou, C

    Peng, B. and Papadimitriou, C. The complexity of non-stationary reinforcement learning. In International Conference on Algorithmic Learning Theory, 2024

    2024

  38. [46]

    Reinforcement learning for humanoid robotics

    Peters, J., Vijayakumar, S., and Schaal, S. Reinforcement learning for humanoid robotics. In IEEE-RAS International Conference on Humanoid Robots, 2003

    2003

  39. [47]

    Puterman, M. L. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2014

    2014

  40. [48]

    and Kalyani, S

    Raj, V. and Kalyani, S. Taming non-stationary bandits: A bayesian approach. arXiv preprint arXiv:1707.09727, 2017

    2017 arXiv

  41. [49]

    Sutton, R. S. and Barto, A. G. Reinforcement Learning: An Introduction. MIT Press, 2018

    2018

  42. [50]

    S., McAllester, D., Singh, S., and Mansour, Y

    Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y. Policy gradient methods for reinforcement learning with function approximation. In Neural Information Processing Systems, 1999

    1999

  43. [51]

    and Vincent, P

    Touati, A. and Vincent, P. Efficient learning in non-stationary linear markov decision processes. arXiv preprint arXiv:2010.12870, 2020

    2010 arXiv

  44. [52]

    Non-asymptotic analysis for single-loop ( N atural) actor-critic with compatible function approximation

    Wang, Y., Wang, Y., Zhou, Y., and Zou, S. Non-asymptotic analysis for single-loop ( N atural) actor-critic with compatible function approximation. In International Conference on Machine Learning, 2024

    2024

  45. [53]

    and Luo, H

    Wei, C.-Y. and Luo, H. Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach. In Conference on learning theory, 2021

    2021

  46. [54]

    F., Zhang, W., Xu, P., and Gu, Q

    Wu, Y. F., Zhang, W., Xu, P., and Gu, Q. A finite-time analysis of two time-scale actor-critic methods. Neural Information Processing Systems, 2020

    2020

  47. [55]

    M., Golmohammadi, A., Shi, Y., et al

    Yeh, C., Li, V., Datta, R., Arroyo, J., Christianson, N., Zhang, C., Chen, Y., Hosseini, M. M., Golmohammadi, A., Shi, Y., et al. Sustaingym: Reinforcement learning environments for sustainable energy systems. Neural Information Processing Systems, 2024

    2024

  48. [56]

    Multi-agent reinforcement learning: A selective overview of theories and algorithms

    Zhang, K., Yang, Z., and Ba s ar, T. Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of reinforcement learning and control, 2021 a

    2021

  49. [57]

    Zhang, S., Zhang, Z., and Maguluri, S. T. Finite sample analysis of average-reward td learning and q-learning. In Neural Information Processing Systems, 2021 b

    2021

  50. [58]

    R., and Jagmohan, A

    Zhou, H., Chen, J., Varshney, L. R., and Jagmohan, A. Nonstationary reinforcement learning with linear function approximation. arXiv preprint arXiv:2010.04244, 2020

    2010 arXiv

  51. [59]

    Finite-sample analysis for sarsa with linear function approximation

    Zou, S., Xu, T., and Liang, Y. Finite-sample analysis for sarsa with linear function approximation. Neural Information Processing Systems, 2019

    2019

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.