Natural Policy Gradient for Average Reward Non-Stationary RL

1. My main concern is that the paper seems to have limited technical innovation. The most challenging component of the analysis is to handle samples from a time-varying Markov chain induced by changing policies and transition probabilities. However, as the authors noted, the technique for doing so is standard if only the policies are changing. To handle the changes in $P$ seems to requires additionally bounding the TV distance in the samples by the shift in $P$, which is a straightforward extension. It is possible that I underestimate the amount of efforts and novelty in the analysis. In that case, I suggest that authors clearly state the key technical challenge that prevents existing analysis from being applied with small modification, as well as the novel analytical techniques that authors come up with.

2. The regret of the proposed algorithm is much inferior to that of the state-of-the-art value-based algorithms (for example, Mao et al., 2024), especially in terms of $T$. Though I understand that the techniques used to analyze gradient-based and value-based algorithms are quite different, the gap still undermines the contribution of the work. This work differs from Mao et al., 2024 in so many aspects that I cannot see where the degradation in the regret comes from (Q learning and policy gradient algorithm difference, actively restarting versus passive forgetting, episodic MDP versus infinite-horizon). Can the authors provide some discussion on why they think they cannot get a regret on the same order as Mao et al., 2024. An infinite-horizon average-reward MDP does not seem to be fundamentally harder than an episodic one, since the lower bounds in Mao et al., 2024 are similar for the two settings.

3. The statement "The projection step in line 9 ... ensures a unique solution to the Bellman equations in the average reward setting" is incorrect. Whatever algorithm you use to find a solution has nothing to do with whether the solution exists/is unique. The actual reason for using the projection is to guarantee boundedness of the critic iterates. It is by Assumption 2 that the critic solution is unique. It is known that Assumption 2 does not hold in any average-reward MDP (see Zhang et al., 2021). Any solution to the Bellman equation remains a solution when added with an all-one vector. Making an assumption that never holds weakens the theoretical results, even though the same assumption has been made in a number of existing works. However, the issue can be circumvented by slightly altering the critic convergence metric. Essentially, if we use an argument similar to the one in Zhang et al., 2021, Assumption 2 does not need to be assumed but can be shown to hold in a proper subspace. The entropy regularization approach discussed in line 385-397 is actually unnecessary if its sole purpose is to remove Assumption 2.

References

Zhang, S., Zhang, Z. and Maguluri, S.T., 2021. Finite Sample Analysis of Average-Reward TD Learning and $Q$-Learning. Advances in Neural Information Processing Systems, 34, pp.1230-1242.

1. The parameter configurations in Theorem 1 require further clarification. It is not clear whether the current configuration is the optimal one. For example, for parameter $N$, it should be chosen such that $N/\beta$ and $\Delta _{T}T/N$ have the same order. However, the current configuration does not satisfy this .

2. The suboptimality of the algorithm requires more discussion. As mentioned by the authors, the regret of NAC for an infinite horizon stationary MDP can be $O(T^{2/3})$. It is not clear whether this can be achieved for non-stationary setting under the similar assumptions.

3. The writing for the entropy regularization section is unclear. According to my understanding, people usually include the entropy term in the reward definition, and the regret is measured under this newly defined reward. However, the authors do not define this reward and just adopt the same notation for the un-regularized and regularized case. It is confusing since it looks like that adding a regularized term in the algorithm can relax the assumption for the un-regularized problem.

The novelty of the proposed algorihtm is a bit weak. The NAC algorithm is kind of standard. The primary innovation in NS-NAC appears to be the two-timescale technique, which essentially coordinates the learning rates between actor and critic updates to ensure slower policy learning relative to Q-function evaluation.

1. The paper seems to assume the optimal policy of a non-stationary average-reward MDP (i.e., $\pi^* = \arg\max_\pi\lim_{T\rightarrow\infty}\sum_{t=0}^Tr_t(s_t,a_t)/T$) is equivalent to the combination of optimal policies of each MDP $M_t$ environment at each time $t$ (i.e., $\pi_t^*$ in (4)). Although not explicitly stated, the authors seem to indicate this equivalence by the definition of the dynamic regret and statement such as "the agent chases a moving target, namely, the time-varying optimal policy $\pi_t^*$". However, this equivalence does not hold in general (please see my first comment in Questions below). Please clarify whether this equivlance holds in the paper. If the equivalence does not hold, then please explain why the dynamic regret is defined in the way of (4).

2. The premise of the problem is not clear, and it is not clear how to choose the learning rates in practice since the choice depends on quantities that are unknown in advance. Please see my sencond comment in Questions below.

3. Assumption 1 lacks justification. Please give examples that satisfy Assumption 1 and explain how to verify it in practice.

• The regret upper bound seems to be worse in time horizon $T$ dependency.

• The synthetic empirical results only seem to suggest comparative results. In addition, the experimental setting seems relatively simple.

• The implementation of the algorithm depends on strong assumptions on knowing variation budgets $\Delta_{R,T}$ and $\Delta_{P,T}$. Please justify such an assumption.

Assumption 2 cannot be satisfied in the tabular setting: It is my understanding that this paper has a serious technical error, which is that the tabular formulation of the average reward critic in NS-NAC means that Assumption 2 is not satisfiable under any circumstances. Specifically, in the tabular setting, the $\bar{A}$ that they constructed will always have a row sum of 0. Therefore $A$ is singular, and $0$ must be an eigenvalue which does not satisfy Assumption 2 which states that the largest eigenvalue of $\bar{A}$ is $-\lambda$ for $\lambda > 0$. To see that the row sums are always 0, given some observation $O(t) = (s_t, a_t, s_{t+1}, a_{t+1})$, if $(s_t, a_t) = (s_{t+1}, a_{t+1})$, the entire A matrix is $0$. So clearly in this case the row sums are 0. If $(s_t, a_t) \neq (s_{t+1}, a_{t+1})$ then one can readily check that there is a $-1$ on the main diagonal of A(O_t) and a single $+1$ value somewhere else on the same row. This means that for the row of $A(O_t)$ corresponding to $(s_t, a_t)$ there is a $-1$ entry and a $+1$ entry and every other entry is 0. This means means all the row sums are still 0 when $(s_t, a_t) \neq (s_{t+1}, a_{t+1})$. Then, checking that the row sums of $\bar{A}$ are also 0 is trivial by the linearity of expectation (i.e. $\sum_j \bar{A}_{(s,a),j} = E_{s,a,s',a'}[\sum_j A_{(s,a),j}] = E[0] = 0$). Since Assumption 2 cannot be verified for the tabular setting, the authors cannot guarantee that there exists a unique solution to the problem which invalidates the rest of their analysis.

Its worth noting that this problem of invertibility of $\bar{A}$ is the reason why the convergence of tabular average reward TD cannot be proven simply by invoking the convergence results for average reward TD with linear function approximation from works like Tsitsiklis and van Roy 1999 or Wu et al 2020 but with one-hot features. If I am incorrect in my analysis please let me know and I'm happy to change my score. However, this error renders the rest of the analysis in the paper to be incorrect and so it is for this reason I am recommending rejection.

There are a few other technical concerns and points for clarification:

• Algorithm 1: The input includes an exploration parameter, but the algorithm description does not utilize it. I assume the authors meant to include the epsilon greedy action selection but it appears it was forgotten.
• Non-stationarity in Notation: The Bellman equation for the value function should index policy $\pi$ by $t$ to reflect non-stationarity and to be consistent with subsequent notations.
• Experiment Plots: Uncertainty measures are inconsistently reported. Some plots use shaded regions, while others use error bars. Consistency here would be nice.
• Uniformly distributed switches in Experiments: In the experiment setup in section L, it appears that the switches betweent the two transition matrices are uniformly spread out throughout the time horizon. This is not captured in any of the theoretical assumptions for the Algorithm. Additionally, this setting seems like the best case scenario for the algorithm as the learning rate schedule (which is fixed and depends on $\delta T / T$) could be tuned to provide the best performance based on the consistent switching times. It would be nice to see an experiment where the switching times are randomly distributed throughout $T$. At the same time, I do recognize that this is primarily a theoretical paper with substantial theoretical contributions.

Novelty of the Proposed Algorithm

While the proposed NS-NAC algorithm is presented as a novel approach, it appears to align closely with a two-timescale natural gradient actor-critic method from Khodadadian et al 2022. The main distinction lies in the derivation of the two timescale learning rates $\beta_t$ and $\gamma_t$, which are optimally set based on a perturbation budget. However, this alone may not justify categorizing NS-NAC as a new algorithm. Instead, it could be more accurately described as a traditional natural actor-critic with a specialized learning rate schedule for application to the non-stationary setting. This is analogous to tabular TD learning using $1/t$ versus $1/t^2$ learning rates, which represent variations within the same algorithm rather than fundamentally new methods. If there are other differences between NS-NAC and the original NAC but applied to a non-stationary environment, additional clarification would be helpful. Again, the analysis of this NAS algorithm is already important itself, regardless if this "NS-NAC" algorithm is truly "new".

1. The regret definition used in this paper is questionable. J_t^{\pi_t} is the optimal reward in the steady state for reward r_t and transition kernel P_t. It may not represent the largest reward that can be achieved at time $t$. Therefore, measuring the difference from J_t^{\pi_t} may not be a good option. In other words, the definition in (4) may be negative.
2. Analysis in this paper is limited to the tabular case. While existing analysis for AC and NAC with function approximation are quite mature, the results in this paper then seem rather limited.
3. The assumption of uniform ergodicity rules out the need for exploration in this paper. This makes the contribution of this paper weak comparing to value based approaches where exploration is explicitly addressed.
4. In the literature, there are studies on adversarial MDPs with corrupted transition kernels, see e.g., No-Regret Online Reinforcement Learning with Adversarial Losses and Transitions The results in this paper has a linear regret in T if the variation budget is linear in T. Even if the variation budget is 0, i.e., it is a stationary problem, the regret has an order of T^8/9, which is strictly suboptimal.