A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach

Markovian Noise: We agree that applying projections or invoking the assumption of finite action space is common in the literature. For example, the MAC algorithm derives bounds using MLMC estimates from (Dorfman and Levy 2022), which assume a finite state space and a bounded domain, thereby necessitating a projection step in the critic update. Our analysis models the NPG and critic updates as stochastic linear recursions with Markovian noise, which we show to converge without invoking the above preconditions. A similar result can be found in (Beznosikov et al. 2023). However, their update differs from ours since we deal with biased estimates, which are not considered in the cited paper.

(Q1) Lipschitz Property: Lipschitz continuity and smoothness of the function $J$ can be easily proven within the framework of discounted-reward MDPs (Lemma 2, Mondal and Aggarwal 2024). In this case, $L$ depends only on the discount factor. However, to the best of our knowledge, no such result is known in the average-reward case. We want to emphasize that nearly all papers analyzing general parameterized policy gradient methods for average-reward MDPs assume the stated properties of the $J$ function. These properties are expected to hold in practice since they ensure that a slight change in the parameter does not result in a large change in the $J$ function. In our assumption, $L$ is a constant that does not depend on other model-specific parameters.

(Q2) Step Sizes: The values of the step sizes $\beta$ and $\gamma$ are given in Theorems 3 and 4, respectively: $\beta = \frac{4\log H}{\lambda H}$, and $\gamma = \frac{2\log H}{\mu H}$. Moreover, the value of $\alpha$ is mentioned at the top of Page 20, line 1045: $\alpha = \frac{\mu^2}{4G_1^2L}$. Observe that none of these parameters depend on the mixing time, $t_{\mathrm{mix}}$, which is consistent with our claim that our algorithm does not require the knowledge of $t_{\mathrm{mix}}$. In the revised version, we will explicitly state the values of these parameters in Theorem 1.

(Q3) Regarding $\Lambda_P$ and $\Lambda_Q$: The terms $\Lambda_P$ and $\Lambda_q$ in (35) are parts of Theorem 2 that analyzes the convergence of a general stochastic linear recursion (SLR). Specifically, Eq. (35) forms a precondition for Theorem 2. We recognize that both NPG and critic updates can be formulated as SLRs. Moreover, these updates satisfy a precondition similar to (35). In particular, (53) and (54) allow us to choose $\Lambda_P=c_\beta+3$ and $\Lambda_q=c_\beta+1$ for the critic update while (55) dictates $\Lambda_P = G_1^2$ and $\Lambda_q = \mathcal{O}(G_1t_{\mathrm{mix}})$ for the NPG update. Note that, although $\Lambda_q$ for the NPG update is dependent on $t_{\mathrm{mix}}$, it is not used as an input to our algorithm, thereby maintaining the claim that our algorithm does not require knowledge of the mixing time.

(Q4) On Two-Timescale Approach: We emphasize that no algorithm (be it single- or two-timescale) exists in the literature that achieves the optimal convergence rate of $\mathcal{O}(1/\sqrt{T})$ for average-reward MDPs with general parameterized policies via Markovian sampling. Our natural actor-critic-based algorithm achieves this goal, and that itself is a contribution worth highlighting.

Secondly, the algorithms mentioned by the reviewer are not single timescale. We note that the paper NAC-CFA (https://arxiv.org/pdf/2406.01762) mentions (page 5) that ``Here, the AC and NAC algorithms in Algorithm 1 are single-loop, single sample trajectory and two timescale." Similarly, the MAC algorithm is also two timescale since the critic loop has an order-larger step size which makes the algorithm two timescale. Thus, we note that both the mentioned algorithms are two timescale. We will mention this in the paper and enlist designing a one-scale algorithm as a future work.

(Q5) Novelty: Our main contribution is designing an algorithm for average-reward MDPs that achieves the optimal $\mathcal{O}(1/\sqrt{T})$ rate for general parameterized policies with Markovian sampling. This is a contribution worth highlighting because no algorithm, be it single- or two-timescale, achieves this feat. Moreover, as previously pointed out, all known actor-critic algorithms on average-reward MDPs with general parameterized policies are all, to the best of our knowledge, two-timescale. In summary, we respectfully disagree with the reviewer's stance that not being a single-timescale algorithm is a good enough reason to discount the merit of our work.

The optimization literature teaches us that single-timescale algorithms typically develop based on the intuitions provided by two-timescale algorithms. We are, therefore, hopeful that the intuitions provided by our algorithm will pave the way to designing the first single-timescale actor-critic algorithm for average reward MDPs with general parameterized policies. We will mention this as a future work in the revised paper.

(a) Related Works: Thanks for mentioning references [1] and [2]. We will include them in the revised version of our paper. In addition to [1], we will also include some other works on robust MDPs.

(b) Message for Practitioners: Our algorithm is designed for large state and action spaces, with parameterized representations for both the actor and critic, making it well-suited for large-scale problems. While there are multiple practical insights, we highlight a few key ones below.

1. Sampling: Many existing policy gradient-type algorithms assume access to a simulator capable of generating independent trajectories at will from a given state distribution (e.g., see [1], [2]). Typically called the i.i.d sampling, the procedure of generating independent and identically distributed trajectories greatly simplifies the algorithm design and analysis. However, for many practical applications, building an accurate simulator is itself a difficult problem. Fortunately, our algorithm works on a single trajectory, eliminating the need for a simulator.

2. Dependence on Unknown Parameters: As stated in the paper, many previous works assume knowledge of mixing time and hitting time [3], [4], which are difficult to obtain for most applications. Our algorithm does not require the knowledge of the above parameters, thereby making it easier to adopt in practice.

3. Memory/Space Complexity: Our algorithm is memory-efficient. One can verify that the memory complexity of our algorithm is $\mathcal{O}(\max\\{\mathrm{d}, m\\})$ where $\mathrm{d}, m$ are the sizes of the policy parameter, $\theta$, and the critic parameter, $\zeta$ respectively. It is to be noted that although the Fisher matrix, $F(\theta)$ (and its estimates) require $\mathcal{O}(\mathrm{d}^2)$ space, one only needs to store quantities of the form $F(\theta)\omega$, $\omega\in\mathbb{R}^{\mathrm{d}}$, which need $\mathcal{O}(\mathrm{d})$ space.

4. Computational Complexity: One way of computing the natural policy gradient (NPG) $\omega_\theta^* = [F(\theta)]^{-1}\nabla_{\theta}J(\theta)$ is first obtaining an estimate of the Fisher matrix $F(\theta)$, and then directly using its pseudo-inverse to compute $\omega_{\theta}^*$. Such a method was adopted in [5]. We, instead, pose the problem of computing the NPG as a stochastic least square problem with Markovian noise. This eliminates the computationally expensive process of inverting a regularized Fisher matrix estimate (whose computational complexity is $\mathcal{O}(\mathrm{d}^3)$ where $\mathrm{d}$ denotes the size of the policy parameter). It can be checked that the computational complexity of our algorithm for a given iteration instance $(k, h)$ is $\mathcal{O}(\mathrm{d}^2+m^2)$ where $m$ is the size of the critic parameter.

5. Convergence Rate: Finally, the convergence rate of our algorithm is optimal in the horizon length, $T$. Practically, it indicates that our algorithm takes a relatively small number of training iterations to reach a certain accuracy.

[1] Liu, Y., et al., An improved analysis of (variance-reduced) policy gradient and natural policy gradient methods. Advances in Neural Information Processing Systems, 33:7624–7636, 2020.

[2] Mondal, W. U. and Aggarwal, V. Improved sample complexity analysis of natural policy gradient algorithm with general parameterization for infinite horizon discounted reward Markov decision processes. International Conference on Artificial Intelligence and Statistics, 2024.

[3] Bai, Q., et al., Regret analysis of policy gradient algorithm for infinite horizon average reward Markov decision processes. Proceedings of the AAAI Conference on Artificial Intelligence, 2024.

[4] Ganesh, S. et al., Order-Optimal Regret with Novel Policy Gradient Approaches in Infinite Horizon Average Reward MDPs. In The 28th International Conference on Artificial Intelligence and Statistics, 2025.

[5] Xu, T., et al., Improving sample complexity bounds for (natural) actor-critic algorithms. Advances in Neural Information Processing Systems, 2020.

(a) Sample Complexity: We note that there is a misunderstanding here. The convergence rate and the sample complexity are two faces of the same coin, and one can be derived from the other, as long as the error metric is taken to be the same. For example, consider our algorithm that uses a trajectory of length $\max\\{2^{Q_{kh}}, T_{\max}\\}$ where $Q_{kh}\sim \mathrm{Geo}(1/2)$ for each $k, h$. It is easy to check that $\mathbf{E}[\max\\{2^{Q_{kh}}, T_{\max}\\}]\leq \mathcal{O}(\log T_{\max})$

Since we have taken the number of iterations of $k, h$ to be $K=\Theta(\sqrt{T})$ and $H=\tilde{\Theta}(\sqrt{T})$, and $T_{\max} = H^2 = \tilde{\Theta}(T)$, the expected number of state transition samples used by our algorithm is $\mathcal{O}(KH\log T_{\max}) = \tilde{\Theta}(T)$. Theorem 1 exhibits that for such choices of parameters, our algorithm achieves $\tilde{\mathcal{O}}(1/\sqrt{T})$ global error (up to some additive factors of $\epsilon_{\mathrm{bias}}$ and $\epsilon_{\mathrm{app}}$). This establishes the convergence rate of our algorithm. Alternatively, if we want to ensure a global error of $\epsilon$ (up to the additive factors stated before), the expected number of state transition samples required would be $\tilde{\mathcal{O}}(\epsilon^{-2})$. This expresses the same result in terms of sample complexity.

Although both notions are the same, the literature on average-reward MDP typically expresses the results in terms of the convergence rate, while the literature on discounted-reward MDP typically adopts the sample complexity framework. The cited paper [A] analyzes a discounted-reward setup where the common metric is the sample complexity. The same article has also been cited in our paper (line 118), where we mention its global convergence rate to be $\mathcal{O}(T^{-1/3})$. This is obtained from their equivalent sample complexity result of $\mathcal{O}(\epsilon^{-3})$. It is to be noted that even in the discounted MDP setup, there is no actor-critic algorithm that achieves $\mathcal{O}(\epsilon^{-2})$ sample complexity for general parameterization.

(b) Typo: Thanks for pointing out the typo. We will correct it in the revised version.

Concerning the table, the authors state that their approach works for infinite states and actions, and similar claims are made for some of the related works. However, by inspecting those works, it appears that their results are defined with respect to large but finite spaces. Can the authors comment on this?

We agree that some related works (NAC-CFA and MAC) assume large but finite state spaces, and we have mistakenly given them more credit by stating that their conclusions extend to infinite state spaces. We will make changes in the revised paper accordingly. In this context, we want to emphasize that our work does apply to infinite states and action spaces, and there is no mistake in that claim.

Concerning the weaknesses, the authors do not properly highlight the technical novelty in terms of theoretical analysis. Indeed, this work shares many similarities both in terms of assumptions and in terms of methods with the one of Patel et al. (2024). I believe that the work may benefit from a clearer comparison between the current work and the one just mentioned.

The assumptions used in this work are commonly used in the literature and thus are similar to those used in multiple works including (Patel et al., 2024).

Although our methods bear some similarities with that of (Patel et al., 2024), there are multiple novel components in the analysis that allow us to establish an order-optimal convergence rate of $\tilde{O}(T^{-1/2})$ for average reward MDPs without the knowledge of mixing time, a feat achieved by no other work in the literature. While existing AC analyses (including that in the cited paper) apply relatively loose bounds, we refine the analysis to get sharper results. The first step towards this goal is to establish that the global convergence error is bounded by terms proportional to the bias and second-order error in the NPG estimation (Lemma 1). In prior AC works (including the cited paper), a coarser bound was used instead of the NPG bias that led to an error of the form $\mathbb{E} ||\xi_t - \xi^\star||$ in the global convergence bound where $\xi_t$ is the critic estimate at time $t$ and $\xi^\star$ denotes the true value. Utilizing Lemma 1 and Theorem 3, our analysis refines this term to $||\mathbb{E}[\xi_t] - \xi^\star ||$, which can be significantly smaller than the previous estimate. It is to be noted that bounding $||\mathbb{E}[\xi_t] - \xi^\star||$ remains challenging due to Markovian sampling. Interestingly, we observe that both critic and NPG updates can be interpreted as linear recursions with Markovian noise. Efficient analysis of such a linear recursion is another novelty of our paper. In Theorem 2, we obtain a convergence rate for a generic stochastic linear recursion. This, along with the improved error estimates, form a basis for Theorems 3 and 4, which finally leads to our desired result in Theorem 1.

In summary, improving the error estimates, recognizing the NPG and critic updates as linear recursions, and performing a sharp convergence analysis of a general stochastic linear recursion are the novel cornerstones of our analysis.

Another weakness is the absence of numerical simulations.

The focus of the paper is obtaining the first theoretical result for a state-action space size independent global convergence rate of $\tilde{\mathcal{O}}\left(T^{-1/2}\right)$ for general parameterized policies in average reward infinite-horizon MDPs, using a practical algorithm that does not require the knowledge of mixing times. Evaluation of this work on some practical applications is left as future work.