Faster Fixed-Point Methods for Multichain MDPs

We thank you for your positive review. We would like to respond to some of your listed weaknesses and questions.

1. Weakness 3/Question 2: For the theorems in Section 3 which involve an initialization $h_0$, no assumptions are made on $h_0$. In particular it does not need to satisfy both the modified and unmodified Bellman equations. A vector $h$ satisfying both equations is needed only within the analysis and the statement of the convergence guarantee within the theorems, but is not needed to run the algorithm.
2. Question 3: You are correct that our results can be generalized to operators beyond the Bellman operator, as we show in Appendix H.1 (culminating in Theorem H.5). However, this theorem shows that we can find points with small fixed-point error for operators satisfying a certain generalized commutativity property (equation (14)), but there is no obvious general analogue of extracting a “policy” from such a fixed point and arguing about the gain-preserving properties (in the sense of Corollary 2.2) of such a policy, so overall not all of our results have any analogue in this more general setting.
3. Question 4: The warm-start procedure is designed so that $T^{(t)}(0)$ is well-aligned with the direction $\rho^\star$ (in the sense that $T^{(t)}(0) \approx t \rho^\star$), so a different procedure could generally try to accomplish this in another fashion, but it is not immediately clear how to do so without knowing $\rho^\star$ a priori.
4. Question 5: It is unclear how to modify the proposed algorithms to utilize adaptive stepsizes, but this is an interesting topic of future research.

We thank you for your positive review. We would like to respond to some of your listed weaknesses and questions.

1. Third paragraph in Strengths and Weaknesses section regarding definition of $T_{drop}$: We agree that whether the indicator can be removed is an interesting question, and it would appear that the answer is negative for the following reason: We believe it is possible to show that $\mathbb{E}^\pi [\sum_{t=0}^\infty \rho^\star(S_t) - P_{S_t, A_t}\rho^\star ] = \mathbb{E}^\pi [\rho^\star(s_0) - \rho^\star(S_\infty)]$, where $S_\infty$ is some state in the (potentially random) closed recurrent class reached by the policy. This implies that we would always have $\mathbb{E}^\pi [\sum_{t=0}^\infty \rho^\star(S_t) - P_{S_t, A_t}\rho^\star] \leq \max_s \rho^\star(s) - \min_s \rho^\star(s)$, which is $\leq 1$ for our scaling (where $\|r\|_\infty \leq 1$), which is probably too small to serve as a complexity measure since it is bounded $O(1)$ independently of the properties of the MDP. (We believe that adding a max with $0$ would still not fix the overall issue.)
2. Second question: We are happy to expand upon our comments. One potential setup is that, instead of assuming access to the transition matrix $P$, and hence the ability to exactly compute matrix-vector products of the form $Ph$, we could instead investigate the development of algorithms which are only able to access $P$ stochastically via sampling: given $s,a$, we can only draw a sample $S’$ from the distribution given by the row vector $P_{sa}$; in this case then $h(S’)$ will be an unbiased estimate of $(Ph)(sa)$ (the $s,a$th coordinate of the vector $Ph$). Since computing $(Ph)(sa)$ will generally take $O(S)$ time, if $S$ is large then this sampling approach might be able to form a sufficiently good estimate of $(Ph)(sa)$ in a smaller amount of time (if samples can be obtained sufficiently quickly).
3. First paragraph of limitations: Beyond making quantitative improvements in algorithmic performance relative to prior work, we believe that overall we also develop a range of useful theoretical observations which expand the foundations of this topic. We also note that since value-iteration-style methods form the backbone of many approaches to reinforcement learning and have extensive prior work, even apparently small differences in approaches are still of significant interest and may lead to downstream impacts.
4. Second paragraph of limitations (re non-VI methods): We agree that this is an interesting topic, however, we are not aware of major studies of the complexity of alternative methods for solving general average-reward MDPs. Despite the very long history of VI methods for average-reward MDPs, non-asymptotic complexity guarantees have only been developed very recently.
5. Fourth paragraph of limitations: We feel that this paper is squarely within the stated call for papers for NeurIPS, fitting within the topic of "Reinforcement learning (e.g., decision and control, planning, hierarchical RL, robotics)", as our paper mainly focuses on solving MDPs (thus addressing the "planning" problem). Our paper is also related to the NeurIPS topic of Optimization. In particular, we present some results in a general language of fixed-point methods common to optimization researchers (ex. Theorem 4.2, Appendices H and I).

We thank you for your positive review. We would like to respond to some of your listed weaknesses and questions.

1. Weakness 2: While we agree that requiring $h$ to satisfy both Bellman equations reduces its interpretability (relative to $h$ which satisfies only the unmodified Bellman equation, since in this case the bias function of a bias-optimal/Blackwell-optimal policy can simply be used), we note that prior works studying the convergence of value iteration for general average-reward MDPs [Lee and Ryu 2024, Puterman 1994] have also utilized $h$ satisfying these requirements. (In fact, [Lee and Ryu 2024, Puterman 1994] analyze under arguably an even less interpretable assumption, that $h$ satisfies the modified Bellman equation and also admits a policy in the simultaneous argmax of equations (2a) and (2b), in the sense of equations (7) and (8); one of our minor contributions is showing that such $h$ are exactly the $h$ which satisfy both the modified and unmodified Bellman equations (Lemma D.1).)

2. Question 1: Here we provide more details of the proofs of Theorems 3.4 and 4.5. Overall, we agree that including these details would benefit the paper, and we would use an additional camera-ready page to do so.

   • Theorem 3.4: The high-level approach is to control both terms appearing in Corollary 2.2, which itself is a direct consequence of Lemma 2.1. As discussed in the paragraph beginning on line 241, Lemma 3.3 can be used to obtain an estimate $\hat{\rho}$ of the optimal gain $\rho^\star$. This enables the formation of the approximately shifted operator $\widehat{\mathcal{T}} := \mathcal{T} - \hat{\rho}$ which is used in Algorithm 1. At a high level, since standard convergence analyses of Halpern iteration would guarantee small fixed-point error if it were ran using the “perfectly” shifted operator $\mathcal{T} - \rho^\star$, our analysis then shows that instead using $\widehat{\mathcal{T}}$ does not cause too much error. As discussed in the paragraph beginning on line 248, this is only immediately sufficient to control the fixed-point error term from Corollary 2.2, but since the second phase of the algorithm is initialized with $x_n$ which is well-aligned with the direction $\rho^\star$ (and because our analysis demonstrates that this property is still true after the second phase terminates), the other term $\| P_\pi \rho^\star - \rho^\star \|$ appearing in Corollary 2.2 is also guaranteed to be small after termination.

   • Theorem 4.5: The starting point here is to use our novel discounted reduction Lemma 4.1. Internally the proof of this lemma also makes use of Corollary 2.2 and connects its bound to quantities related to the discounted Bellman operator. As discussed in the paragraph beginning on line 287, Lemma 4.1 suggests that we must try to achieve small discounted fixed-point error while using a large value of the effective horizon $\frac{1}{1-\gamma}$. This objective leads us to the development of Algorithms 2 and 3, for reasons which are explained in those sections but in particular in the paragraphs beginning on lines 314 and 330. This culminates in Algorithm 3 and Theorem 4.4 describing its performance, which we can essentially directly combine with the reduction Lemma 4.1. One interesting key lemma is Lemma J.1, which relates the optimal discounted value function $V_\gamma^\star$ to $\rho^\star$ using the $T_{drop}$ parameter and is key for both the proof of Lemma 4.1 and the proof of Algorithm 3/Theorem 4.4. Lemma J.8 performs a similar function but instead relates $\mathcal{T}^{(n)}(\mathbf{0})$ to $\rho^\star$, and is also key to the idea of Algorithm 3 and Theorem 4.4.

3. Question 2: The bounds of Lemmas F.5 and F.6 are tight, as can be seen by the following example: Fix a parameter $T > 1$. Consider an MDP with three states (1,2,3). State 1 has only one action which is absorbing with reward +1. State 2 also has only one action which is absorbing and with reward +0. State 3 has two actions: the action 1 leads deterministically to state 1 and gives reward +1. Action 2 gives reward +1, and has probability $1-1/T$ of leading back to state 3, and probability $1/T$ of leading to state 2. Then it is straightforward to compute that $\rho^\star = [1 ~ 0 ~ 1]$ and the parameters $\mathsf{B}, \mathsf{T}_{drop}$, and $1/\Delta$ are all equal to $T$ for this instance.

4. Question 3: We believe that there is a high possibility that the gain-dropping time could be useful in simulator/offline RL settings, and it might be interesting to understand whether new algorithms could achieve sample complexity results in terms of this sharper parameter, rather than the bounded transient time parameter used in [Zurek and Chen 2025b]. It may also be useful in the online setting, but a main obstacle in the online setting is formulating a useful notion of regret for general average-reward MDPs, since generally an algorithm may become “trapped” in low gain regions of the MDP without any ability to escape.

We would like to address several inaccuracies of this review.

1. Response to weaknesses bullet 1: Our algorithms for solving general average-reward MDPs do not depend on knowledge of Blackwell-optimal policies in any way. While some guarantees in our theorems depend on a vector $h$ which satisfies both the modified and unmodified Bellman equations, such a vector $h$ is only used in the analysis and is not needed to run the algorithms. Additionally, knowledge of $n > 1/\Delta$ is not required to run the algorithms. This condition is used in one location, Theorem 3.5, which strengthens the convergence rate for Algorithm 1 relative to Theorem 3.4 when this condition happens to hold. Overall, all our theorems explicitly state all assumptions required for them to apply to the algorithms, and there are no “scattered” caveats in the appendices/footnotes.
2. Response to weaknesses bullet 2: The paragraph beginning on line 248 is dedicated to discussing why the warm-start phase is helpful for solving the navigation problem. Section 2 features only two new definitions, our novel parameters $T^\pi_{drop}$ and $T_{drop}$.
3. Response to weaknesses bullet 3: As mentioned in our first bullet point, the only condition on phase lengths is $n > 1/\Delta$ appearing in Theorem 3.5, and this only strengthens the convergence rate of Algorithm 1 when this condition holds (relative to Theorem 3.4, which applies without this condition). Algorithm 1 does not require any unknown parameters to be run. While our results are stated for the setting where the desired number of iterations $n$ is decided upon beforehand, our convergence rates can trivially be extended to the “anytime” setting where $n$ is chosen later by running the algorithms with $n=2^1, 2^2, 2^3, …$. We feel as if the leading ($\Theta(1/n)$) terms in our results do not feature prohibitively large constants. Overall we focused on qualitative improvements relative to prior work.

We would like to address your questions:

Q1: As multichain average-reward MDPs are the most general class of average-reward MDPs, developing algorithms for solving them is an impactful endeavor. Since many RL algorithms are inspired by value iteration methods, we believe that developing value iteration methods with superior nonasymptotic convergence guarantees has the potential to lead to future RL advances. Essentially any real problem where a catastrophic choice of policy can lead to irrecoverable states (for example, a self-driving car which crashes, or a faulty datacenter cooling policy which causes irreversible damage to the datacenter) can be understood as a general MDP. Another example not involving “catastrophic” actions is the investment/consumption example in [Puterman 1994, Example 9.0.1], where, at a high level, long-term wealth can only be accumulated by individuals with sufficient wages and/or initial wealth, creating multichain structure. General/multichain MDPs have been of interest to researchers for many decades and we refer to the references within [Puterman 1994, Chapter 9] for many more examples.

Since it is probably impossible to develop sublinear regret algorithms for general average-reward MDPs in the standard online setting, this raises the importance of developing algorithms for the planning and offline settings, as they are thus the only ways of coping with these problem settings. We also note that our study of general MDPs has led to technical advances for both discounted (see Section 4) and weakly communicating MDPs (see Corollary 3.2, which applies to evaluating possibly suboptimal policies in weakly communicating MDPs, since even in weakly communicating MDPs not all policies are guaranteed to have constant gains).

Q2: Our work is focused on theory and complexity bounds, and the most relevant prior work on nonasymptotic guarantees for multichain MDPs (i.e. [Lee and Ryu, 2024], also [Zurek and Chen, 2025b]) does not provide numerical experiments. Still, we are happy to provide an example which demonstrates some qualitative improvements demonstrated by our work.

The following experiment is conducted on a MDP which consists of $T+1$ states, for a parameter $T$. State $0$ has only one action which gives reward $0$ (hence this state is absorbing and has $\rho^\star(0) = 0$.) The remaining $T$ states each have two actions, a “good” action and “bad” action. The good action leads to another of these $T$ states with probability $1$, such that if the good action is taken in all states, then they form a cycle of length $T$. The reward for the good action in each state is chosen randomly to be $0$ or $0.5$ with equal probability. In all these states $i = 1, .., T$ the bad action gives reward $1$ and leads to state $0$ with probability $1/T$, and remains in the state $i$ with probability $1-1/T$. Hence the optimal policy is to take the good action in all states besides state $0$ (leading to a gain of around $0.25$ for such states). For such MDPs we just consider the fixed-point error (FPE), since the problem of policy optimization is relatively straightforward for these instances, which are far from worst-case. Hence we plot our Algorithm 1 and the algorithm of [Lee and Ryu, 2024] (as the other algorithms mentioned in the paper are not designed to minimize fixed-point error of the average-reward Bellman operator). We also plot standard value iteration (VI). None of these algorithms require any tuning parameters. The following tables compare these two algorithms, where we set the environment parameter $T = 200$ and the total number of iterations ranges to $2000$:

As we can see, our Algorithm 1 converges faster, in particular exhibiting rapid convergence around 800 iterations, which may be related to the faster rate predicted by Theorem 3.5 when the number of iterations is sufficiently large. We also note that because of the periodic structure of this MDP (due to the cycle), standard (average-reward) value iteration does not drive the fixed-point error to $0$. We will add this and additional experimental results in the final version.