Optimal Sample Complexity for Average Reward Markov Decision Processes

Thanks for your comments and the question! We hope that the following will resolve some of your concerns:

1. Reduction to AMDP approach: The idea of solving an AMDP by reducing it to a DMDP and applying dynamic programming has been considered and implemented since the 1970s, see Hordijk and Tijms (1975). In fact, the optimality of our DMDP algorithm implies that one can choose $\gamma$ of the approximating DMDP to be larger than that in Jin and Sidford (2021), where $(1-\gamma) = \Theta(\epsilon/t_{mix})$, and still get the optimal sample complexity. This is not the case in Jin and Sidford (2021), where enlarging $\gamma$ will worsen the sample complexity. However, note that choosing large $\gamma$ is inefficient from a computational standpoint, because solving the empirical MDP with $\gamma$ close to 1 is typically hard (consider using value iteration). Thus, we choose $\gamma$ to be as small as possible, yielding the same $(1-\gamma) = \Theta(\epsilon/t_{mix})$ as in Jin and Sidford (2021).
2. Numerical experiments: Thanks for the suggestion. We added two experiments that separately verify our algorithm's complexity dependence on $\epsilon$ and $t_{mix}$, yielding results that are consistent with our theory's prediction.
3. The weakly communicating AMDP setting: We are not aware of a way to generalize our method to the weak communication setting that can improve the existing sample complexity dependence of $\widetilde O (H^2\epsilon^{-2})$ in Zhang and Xie (2023). The weak communication setting is connected to a simpler DMDP setting where only one optimal policy induces mixing. In this simpler setting, there is no known matching sample complexity upper and lower bound in the literature, while an upper bounds with $\widetilde O(t_{mix}^2\epsilon^{-2})$ dependence is achieved in Wang et al. (2023). We believe that a variant of our method can yield a $\widetilde O (H^2\epsilon^{-2})$ dependence, matching that in Zhang and Xie (2023). But we are not sure how to improve upon this.

Thanks for the careful reading and suggestions! We hope that the following can resolve your concerns and questions:

1. Contribution: The optimal sample complexity for AMDP has been recognized as a significant and challenging open problem in RL theory, motivating many attempts and improvements over the last 6 years (see Table 1). Our algorithm is the first one in the literature that achieves minmax optimal sample complexity for uniformly ergodic MDP. This is achieved by bringing in multiple algorithmic ideas and analysis techniques. We highlight this contribution in our revised abstract and in the third paragraph of the introduction.
2. Technical challenge: The main challenge to our algorithm design and analysis is to achieve a $\widetilde O(t_{mix}(1-\gamma)^{-2}\epsilon^{-2})$ sample complexity with small minimum sample size. This is explained in the introduction, Sections 3, and 3.1. These are resolved in Theorem 1 by the error upper bound (3.1) where we obtain a term of the form $\sqrt{t_{mix}(1-\gamma)^{-2} n^{-1}}$ and the minimum sample size $n = 64\beta (1-\gamma)^{-1}$. We added a remark to highlight this. The error bound of $\sqrt{t_{mix}(1-\gamma)^{-2} n^{-1}}$ from Proposition A.1 requires a key step that decouples the dependence of $\widehat P$ and $\hat\pi_0$, an idea that is due to Agarwal et al. (2020). We include a detailed presentation of the procedure in Appendix C.
3. Definition of $\alpha^{\pi}$: The $\alpha^{\pi}$ is the long run average reward. In general, it is indeed a function $S\rightarrow R$. However, because we assume that all policies induce mixing (Assumption 1), the long-run average reward induced by any policy is independent of the initial state. Therefore, as explained between equations (2.3) and (2.4), we define it as a limit $\alpha^\pi\in R$.
4. $\eta(\cdot)$ definition: Thanks for pointing this out! We made changes to the manuscript, and now $\eta_\pi$ is the stationary distribution of $P_\pi$.
5. Uniform distribution of $Z$: $Z$ need not be uniformly distributed. It only serves as a perturbation so that the optimal value is unique with a positive optimality gap. This technique is introduced by Li et al. (2022). We added a short discussion about this after equation (3.1).
6. Numerical experiments: Thanks for the suggestion. We added two experiments that separately verify our algorithm's complexity dependence on $\epsilon$ and $t_{mix}$, yielding results that are consistent with our theory's prediction.

Thanks for your insightful questions. We hope that the following answers will clarify them, and we are happy to discuss them further.

1. Span semi norm $H$: As you suggest, the parameter $H$ has advantages over $t_{mix}$ as the basis for an upper bound. We included a short discussion of this in Section 5. Moreover, we have evidence suggesting that the natural analog of our algorithm should have a sample complexity upper bound of $\widetilde O (|S||A|H\epsilon^{-2})$, if we replace the uniform ergodicity assumption by one that assumes the span semi-norm of the transient value function induced by any policy is bounded by $H$. However, we didn't adopt this setup for the following reasons. First, $t_{mix}$ places a direct assumption on the primitives---namely the transition kernel---of the AMDP, yet the assumption on $H$ involves the solution to Poisson equations. Second, we are aiming at a "worst case" complexity result for the AMDP. The $H$ metric, considering the interplay between the reward and the transition kernel, has the flavor of instance-dependent complexity theory (see Khamaru et al. (2021), cited in the paper).
2. Reduction procedure: Thanks for asking about this. Before giving a direct response, we would like to point out that the idea of solving an AMDP by reducing it to a DMDP and applying dynamic programming has been considered and implemented since the 1970s, see Hordijk and Tijms (1975). In fact, the optimality of our DMDP algorithm implies that one can choose $\gamma$ of the approximating DMDP to be much smaller than that in Jin and Sidford (2021), where $(1-\gamma) = \Theta(\epsilon/t_{mix})$, and still get the optimal sample complexity. This is not the case in Jin and Sidford (2021), where enlarging $\gamma$ will worsen the sample complexity. However, note that choosing large $\gamma$ is inefficient from a computational standpoint, because solving the empirical MDP with large $\gamma$ is typically hard (consider using value iteration), and hence is not implemented in the paper. Therefore, the reduction method is mainly a computational tool. So, statistically speaking, we think it is possible to achieve the same sample complexity using a model-based approach without the reduction. However, this might lead to computational complications, e.g. slow convergence rate for non-mixing empirical AMDPs.
3. Extension to the online setting: The key ideas and bounds extend to the online setting without any issue. As our answer to your question (2) suggests, our bound is not reliant on a particular choice of the discount $\gamma$. Therefore, we do believe that our theory can be used to extend classical model-based online discounted RL algorithms to the average reward setting.

Thanks for your comments and suggestions! We address your concerns and revise the paper accordingly as follows:

1. Contribution: The optimal sample complexity for AMDP is a significant and challenging open problem in RL theory. A number of related publications in notable venues have appeared in the last six years (see Table 1). We offer a new algorithm and a novel analysis that combined yield the provably first min-max optimal sample complexity method for uniformly ergodic MDPs. We strongly believe that our result holds significant theoretical value and is therefore worth publishing. In fact, it is hard to argue the opposite in view of the importance of this problem. We acknowledge the useful ideas introduced in earlier papers. But clearly, key (non-trivial!) additional insights were required to solve this problem; otherwise, a minmax optimal result would have been offered already by one of the previous authors who have worked on this problem. Our contribution requires skillfully combining and extending multiple algorithm ideas and analysis techniques. We highlight these contributions earlier in the paper, in our revised abstract, and in the third paragraph of the introduction.
2. Main challenge: A crucial idea that allows us to achieve optimality, compared to the previous approaches, is the realization that the optimal complexity dependence for Discounted MDPs (DMDPs) should be $\widetilde O(t_{mix}(1-\gamma)^{-2}\epsilon^{-2})$, c.f. Wang et al. (2023). However, from an algorithm design standpoint, this is not enough. This needs to be coupled with a sufficiently small initialization sample size. Therefore, the main challenge to our algorithm design and analysis is to achieve a $\widetilde O(t_{mix}(1-\gamma)^{-2}\epsilon^{-2})$ sample complexity with a small minimum sample size. This is explained in the Introduction, Sections 3, and 3.1. These are key insights that are non-trivial to obtain and exploit in algorithmic design, as we explain and illustrate in the numerical results added in the paper.
3. Algorithm design: The idea of solving an Average reward MDP (AMDP) by reducing it to a DMDP and applying dynamic programming has been considered and implemented since the 1970s, see Hordijk and Tijms (1975). If this insight was enough, optimal sample complexity would have been achieved in the literature. However, all of the existing papers in RL that use this strategy (Jin and Sidford 2021, Wang et al. 2022) have a $\widetilde O(\epsilon^{-3})$ dependence, which yields a convergence rate of order $O(n^{-1/3})$, a significant deviation from the canonical convergence rate of $O(n^{-1/2})$. Moreover, as shown in the newly added numerical experiment 1, this $\widetilde O(\epsilon^{-3})$ dependence of the prior works is not just an artifact of the analysis, but an issue intrinsic to their algorithm design. We are able to resolve this issue with our new algorithm through more sophisticated analysis techniques.