Regret Analysis of Average-Reward Unichain MDPs via an Actor-Critic Approach

We sincerely thank the reviewer for their thoughtful feedback and comments. Below we address the questions raised.

Response to Question 1: We agree that providing more context on the works both within and outside the table would help improve the clarity of our paper, which we will make sure to do. For the specific papers mentioned:

• [26] Provides only local convergence, giving a bound on the norm of the policy gradient rather than the suboptimality in average reward relative to the optimal policy.

• [34] Based on a model-based approach using a generative model, whereas our setting is entirely model-free.

• [14] Does not provide a regret bound, but establishes a closely related global convergence guarantee. We will include it in the table for completeness. A regret bound may not follow directly from this result due to the use of varying trajectory lengths across iterations.

• [3] This is already included in the table. If you are referring to the other unichain work [21], it is because the unichain result in this work assumes access to a simulator, unlike the other works listed in the table.

• [20] Assumes access to exact gradients, which significantly simplifies the setup and enables the authors to obtain a logarithmic regret bound.

We will definitely expand details on these related works in the final version.

Response to Question 2: Yes that is correct, the reason $b_v$ is defined with 2 inputs and $b_u$ with 3 is that $b_u$ depends additionally on the estimate of value function parameter $\xi$ as well so that it can form an estimate of the policy gradient. Thus, $b_v$ and $b_u$ are different functions.

Response to Question 3: Thank you for pointing this out. In the context of our paper, either definition is acceptable, as we only use it to define the Fisher information matrix where we take $a = b = \nabla \log \pi_\theta(a|s)$. We will revise the expression to omit the outer product notation and simply write it as $[\nabla \log \pi_\theta (a|s)\nabla \log \pi_\theta(a|s)^\top]$.

Response to Question 4: Thank you for pointing this out. We will update $T_\theta$ to $T_\theta - 1$ accordingly.

Response to Limitations: We note that this work provides the first order-optimal regret analysis for general policy gradient methods in non-ergodic MDPs under the average-reward setting. By showing that unichain MDPs can be effectively handled within the policy gradient framework, we open several promising research directions outlined in the future work section. While empirical validation is valuable and planned for future work, our focus here is on establishing provable guarantees for policy gradient methods, which are widely used in practice but lack comparable theoretical guarantees in this setting.

We thank the reviewer for their feedback. Below we address the points raised.

Response to Weakness 1/Question 1: While our algorithm shares surface-level similarity with MLMC-NAC in the use of nested sampling, there are critical differences in both methodology and analysis objectives.

First, we intentionally adopt a simpler design in which the inner loop size is fixed to a batch size $B$ rather than being sampled from a geometric distribution as in MLMC-NAC. This choice is deliberate: our goal is to demonstrate that even a simple averaging scheme, without elaborate techniques such as MLMC, can achieve order-optimal regret guarantees. We believe this yields a stronger statement, as it shows that optimal performance can be guaranteed only using simple sample averaging even without ergodicity.

More specifically, MLMC-NAC in [14] uses multilevel Monte Carlo to achieve an $O(1/T)$ bias with only $O(\log T)$ samples in expectation, leveraging exponential mixing of the MDP. Since we do not assume such fast mixing, we resort to simple averaging, which requires $\Theta(\sqrt{T})$ samples to control bias. However, the reduced variance from averaging allows us to limit the number of outer iterations to $O(\log T)$, preserving order-optimal complexity through a more refined analysis.

Finally, while the reviewer only mentions the algorithm comparison and not the analysis - our analysis is significantly different from [14]. In addition to the differences arising from the algorithmic since the bulk of our analysis is in handling challenges arising due to the unichain assumption vs the well-studied ergodic case. Analyses in the ergodic setting typically rely on exponentially fast mixing, a property that does not generally hold in the classical unichain setting. For example, in periodic MDPs, the limit $\lim_{t \to \infty}(P_{\pi_\theta})^t(s_0, \cdot)$ may not exist. To overcome this, we introduce a large-batch averaging technique and show that the time-averaged distribution converges to the stationary distribution at a rate of $O(1/t)$ (Lemma 2), even without exponential mixing. This averaging approach is a key novelty that enables us to prove decay rates for the bias and variance of our estimators (Lemma 3), which in turn facilitates bounds on value and Q-functions. Another technical contribution is our treatment of transient states, which remain problematic due to their limited long-term relevance. To isolate their effect, we establish a rapid entry time into the recurrent class (Lemma 10), allowing the use of the strong Markov property to restrict the analysis to the recurrent component.

Response to Weakness 2: Thank you for pointing this out. We will move the details of the TD learning procedure from the appendix to the main paper.

Response to Question 2: When only the Bellman optimality equation is assumed, the classic policy gradient theorem is not applicable, as it relies on the unichain assumption. To the best of our knowledge, no policy gradient methods with guarantees exist for average-reward, infinite-horizon settings beyond this case. Our work is the first to establish such guarantees under the general unichain assumption, the weakest condition under which the policy gradient theorem is known to hold.

While value-based methods achieve regret bounds under only the Bellman optimality assumption, policy gradient methods require fundamentally different analysis. Policy gradient methods scale far better with large state and action spaces, making it the practical default. Given their empirical success, extending theoretical guarantees to more general MDPs is a compelling goal. One possible direction, though purely conjectural at this stage and which may require significant effort, is to restrict policy search to unichain-inducing policies by maintaining strong exploration early and then annealing it as the algorithm converges. Weakly communicating MDPs, the most general class solvable with a single stream of experience, always admit an optimal unichain policy. This conjectured approach could bridge the gap between theory and practice but remains to be rigorously investigated. We will point to this future work direction in the final version.

We thank the reviewer for their feedback and comments. We hope to clarify and address the points raised.

Regarding experiments and practicality of large-batch sizes: As noted in the manuscript, this work focuses on establishing theoretical regret guarantees, with detailed experimental evaluations left for future work.

While our algorithm makes use of a large batch size $B = \mathcal{O}(\sqrt{T})$, this does not require storing all $\sqrt{T}$ samples. In fact, we only need to maintain an online average of the policy gradient estimate, which can be updated incrementally as new samples are collected. This design avoids the need for storing the entire batch, making the implementation efficient and scalable in practice.

In our algorithm, large batches are theoretically justified: collecting a substantial number of samples per iteration improves the accuracy of both the critic estimate and the resulting natural policy gradient direction. This leads to fewer policy updates and ultimately enables order-optimal regret.

To further illustrate the practicality of using a large number of samples per policy update, consider Trust Region Policy Optimization (TRPO), which is based on the Natural Actor Critic framework. Although TRPO differs from our method, for instance by being formulated in the discounted reward setting, it reflects standard design choices in practice. It is typical for TRPO to use thousands of samples per policy iteration, with values commonly ranging from 2,000 to 20,000 depending on the environment. For instance, the Spinning Up implementation sets the default number of samples per iteration to 4,000, as specified in both their documentation and source code. Although the notion of "batch size" differs due to how gradients are computed in both works, this is to highlight that even TRPO relies on large number of state-action samples to estimate the natural policy gradient direction.

On the Scalability of $C_{\text{hit}}$ and $C_{\text{tar}}$: We appreciate the reviewer’s concern regarding the constants $C_{\text{hit}}$ and $C_{\text{tar}}$, which capture the difficulty of exploration under a given policy class. We agree that these constants may scale with structural properties of the MDP such as its connectivity or the number of states. However, we note that some dependence on state-space size or connectivity in discrete state MDPs is unavoidable in general since any algorithm must visit all states to avoid incurring constant regret at each iteration. We note that even the mixing time, $t_{mix}$ in ergodic MDPs can scale with the size of the state space.

We emphasize that our result extends existing guarantees from ergodic MDPs to the more general unichain setting without any degradation in the underlying constants. For instance, the state-of-the-art complexity for actor-critic methods in ergodic MDPs is $O(t_{\text{mix}}^3 \sqrt{T})$ [14]. Although this result does not provide a regret bound, it may be interpreted as a pseudo-regret guarantee. In contrast, our result achieves a bound of $O(C^3 \sqrt{T})$, where the constant $C$, defined in our paper, can be viewed as a characterization of the Cesàro mixing time as established in Lemma 2. The Cesàro mixing time (Section 6.6 in [A]) captures time-averaged convergence behavior and is at most $7 t_{\text{mix}}$ in ergodic chains (see Exercise 6.11 in [A]).

Furthermore, in certain ergodic Markov chains, the Cesàro mixing time can be substantially smaller than the standard mixing time. For instance, in the biased random walk on the $n$-cycle (Example 24.2 in [A]), the standard mixing time is of order $n^2$ (see Section 5.3.2 in [A]), whereas the Cesàro mixing time is only $O(n)$ (see Example 24.2 in [A]). This improvement arises from bounds on the expected stopping time to reach a randomly chosen state from the stationary distribution, which scales linearly with $n$. By averaging the distributions over the first $t$ steps, Cesàro mixing mitigates the effects of periodicity and accelerates convergence to the stationary distribution compared to relying on the distribution at a single time step.

In addition, we note that the computational complexity of our algorithm is independent of the cardinalities of the state and action spaces, offering a substantial advantage over tabular or value-based approaches. While our algorithm is applicable to continuous state and action spaces, our theoretical analysis presently focuses on the finite setting.

We will revise the paper to clarify the interpretation of these constants and include further discussion comparing them with mixing-time-based assumptions used in prior work.

[A] Levin, D.A., & Peres, Y. (2017). Markov Chains and Mixing Times (2nd ed.). American Mathematical Society.

We thank the reviewer for their comments and feedback. We address the weaknesses raised below.

Regarding experimental evaluation: While empirical validation is valuable, our focus here is on establishing theoretical guarantees, which remain limited for policy gradient methods beyond ergodicity. However, we would like to clarify the rationale for using large batch sizes in policy gradient estimation. In our algorithm, large batches are theoretically justified: collecting a substantial number of samples per iteration improves the accuracy of both the critic estimate and the resulting natural policy gradient direction. This leads to fewer policy updates and ultimately enables order-optimal regret.

To further illustrate the practicality of using a large number of samples per policy update, consider Trust Region Policy Optimization (TRPO), which is based on the Natural Actor Critic framework. Although TRPO differs from our method, for instance by being formulated in the discounted reward setting, it reflects standard design choices in practice. It is typical for TRPO to use thousands of samples per policy iteration, with values commonly ranging from 2,000 to 20,000 depending on the environment. For instance, the Spinning Up implementation sets the default number of samples per iteration to 4,000, as specified in both their documentation and source code. Although the notion of "batch size" differs due to how gradients are computed in both works, this is to highlight that even TRPO relies on large number of state-action samples to estimate the natural policy gradient direction.

Regarding the unichain assumption: We present two examples below: one in which the MDP is periodic and another in which it is reducible. In both cases, the optimal policy does not induce an ergodic chain, implying that one cannot restrict the search to policies that induce ergodic chains. This demonstrates that periodicity and transient states may be unavoidable. Nonetheless, the underlying themes in these examples are commonly encountered in practice.

An autonomous drone operates in three modes: active delivery ($s_1$), standby hovering ($s_2$) and low‑battery shutdown ($s_3$). At each step it may choose to continue deliveries (action $a_1$) or return to standby (action $a_2$). In state $s_1$, action $a_1$ leads to $s_1$ with probability $0.8$, to $s_2$ with probability $0.15$ and to $s_3$ with probability $0.05$. In $s_2$, action $a_1$ returns deterministically to $s_1$ while action $a_2$ keeps the drone in $s_2$ with probability $0.9$ and moves it to $s_3$ with probability $0.1$. Once in $s_3$, the drone remains there indefinitely. Rewards are $1$ in $s_1$, $0.5$ in $s_2$ and $0$ in $s_3$. All policies induce a single recurrent class, either the cycle $\{s_1,s_2\}$ or the absorbing state $\{s_3\}$, so the MDP is unichain but not ergodic.

In robotic gait control, particularly for bipedal or quadrupedal robots, the system transitions through discrete movement phases such as left stance, right stance, or flight. States include these phases along with joint configurations and velocities, while actions correspond to motor commands. The dynamics are stochastic yet controllable, and most policies lead to all phases being visited, making the system irreducible. However, optimal locomotion, minimizing energy or maximizing stability, relies on repeating a fixed sequence of movements, such as alternating stances, inducing a periodic policy. This reflects the inherent cyclic nature of locomotion, where balance and rhythm are essential for efficient and stable motion. More broadly, periodic optimal policies can naturally arise in other settings where the environment or reward structure strongly incentivizes strict alternation or repetition over a fixed cycle, such as traffic signal control, task scheduling, or maintenance operations.