Finite-Time Bounds for Average-Reward Fitted Q-Iteration

We thank the reviewer for detailed feedback.

Questions

(i) Intuitively speaking, a weakly communicating MDP requires that one policy be good, whereas a unichain MDP requires every policy to be good. By definition [1], an MDP is weakly communicating if there exists a policy for which set of states where every state in the set is accessible from every other state (plus a possibly empty set of transient states), and an MDP is unichain if, for all policies, the induced Markov chain has a single recurrent class (plus a possibly empty set of transient states). As we clarified in the introduction, this difference induces that a weakly communicating MDP guarantees the Bellman equation only for the optimal policy, while a unichain MDP satisfies the Bellman equation for every policy. In this sense, weakly communicating assumption is less restrictive than ergodic or unichain assumption, and many practical algorithms have been developed for various settings of weakly communicating MDPs [2,3].

(ii) Roughly speaking, in the anchoring mechanism, the anchor term pulls the iterates toward the starting point, and this gives the effect of acceleration in convergence. In the fixed‑point literature, it is known that when the anchoring mechanism is combined with fixed‑point iteration, it effectively reduces the residual error. Recently, [4,5] have shown that anchoring indeed provides accelerated rates and efficient sample complexity in the average reward setup. In our analysis, the anchoring mechanism ensures sublinear convergence with respect to both the Bellman error and the policy as shown in the proof of Proposition 1, and this lead to first finite time bounds for weakly communicating MDPs.

(iii) The role of relative normalization in R‑Anc‑F‑QI is to bound the norm of the function approximator, $\|f_k\|$, from diverging, as our function space range assumption states. Compared to Anc-F-QI, this normalized technique leads to efficient sample complexity. This is because, in the theoretical analysis, we used Bernstein’s and Pollard’s inequalities, whose upper bounds are proportional to the square of $\|f_k\|$. Thus, R‑Anc‑F‑QI improves sample complexity, as we showed in Theorems 3 and 4.

(iv) As the reviewer pointed out, our theorems show that the sample complexity of an IID dataset is more efficient than that of a single‑trajectory dataset. We believe that this discrepancy arises because the inequalities we applied differ in the analysis. As shown in the proofs of Lemmas 5 and 11, we used Bernstein’s inequality for the IID dataset and Pollard’s tail inequality generalized to mixing data for the single‑trajectory dataset, and Pollard’s tail inequality yields looser bounds than Bernstein’s inequality. Consequently, the sample complexity for a mixing single‑trajectory dataset is less efficient than for an IID dataset. We briefly note that this gap also exists in the discounted‑reward offline RL setting [7,8].

(v) Our analysis of Anc-F-QI uses the full coverage condition to bound the products of transition matrices induced by policies. As shown in the proof of Proposition 1, the policy error of Approximate Anchored Q‑Iteration is bounded by a sum of such products with products of coefficients due to the anchoring mechanism. To control these terms, the full coverage is needed and this is how standard Fitted Q‑Iteration analyses in the discounted reward setting use the full coverage condition [7,9].

We expect that our anchoring mechanism can provide finite sample complexity guarantees under partial coverage condition by incorporating a pessimistic approach. A series of works [10–12] has shown that penalizing the estimated value or policy according to its uncertainty relaxes the need for full coverage condition. In particular, [12] introduced Pessimistic Value Iteration, which subtracts an uncertainty term scaled by a confidence parameter from the estimated Q‑value, and achieve finite bounds under partial coverage condition. Referring to those prior works, by combining our anchoring mechanism with this pessimistic approach, we believe that our analysis can be extended to the partial coverage setting.

(vi) For continual or infinite‑horizon tasks where long‑term performance is significant, the average reward setup is a preferable alternative to the discounted reward setup [13-15]. Specifically, average reward framework suits problems like robotic locomotion [16] and queuing systems [17], and many practical RL algorithms have been studied for this setup [18,19].

References

[1] M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, 2014

[2] Bartlett, Peter L., and Ambuj Tewari. REGAL: A regularization based algorithm for reinforcement learning in weakly communicating MDPs. arXiv preprint arXiv:1205.2661 (2012).

[3] Wan, Yi, and Richard S. Sutton. On convergence of average-reward off-policy control algorithms in weakly communicating MDPs. arXiv preprint arXiv:2209.15141 (2022).

[4] J. Lee and E. Ryu. Optimal non-asymptotic rates of value iteration for average-reward MDPs International Conference on Learning Representations, 2025.

[5] J. Lee, M. Bravo, and R. Cominetti. Near-optimal sample complexity for MDPs via anchoring. Interantional Conference on Machine Learning, 2025.

[6] D. J. White. Dynamic programming, Markov chains, and the method of successive approximations. J. Math. Anal. Appl, 6(3):373–376, 1963.

[7] J. Chen and N. Jiang. Information-theoretic considerations in batch reinforcement learning. International Conference on Machine Learning, 2019.

[8] A. Antos, C. Szepesvári, and R. Munos. Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning, 2008.

[9] R. Munos and C. Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 2008

[10] Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch off-policy reinforcement learning without great exploration. Neural Information Processing Systems, 2020

[11] T. Xie, C.-A. Cheng, N. Jiang, P. Mineiro, and A. Agarwal. Bellman-consistent pessimism for offline reinforcement learning. Neural Information Processing Systems, 2021

[12] Y. Jin, Z. Yang, and Z. Wang. Is pessimism provably efficient for offline RL? International Conference on Machine Learning, 2021

[13] Sutton, R. S., Barto, A. G. (1998). Reinforcement learning: An introduction. Cambridge: MIT press.

[14] Mahadevan, S. (1996). Average reward reinforcement learning: Foundations, algorithms, and empirical results. Machine learning, 22(1), 159-195.

[15] Naik, A., Shariff, R., Yasui, N., Yao, H., Sutton, R. S. (2019). Discounted reinforcement learning is not an optimization problem. arXiv preprint arXiv:1910.02140.

[16] Kober, J., Bagnell, J. A., Peters, J. (2013). Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 32(11), 1238-1274.

[17] Schneckenreither, Manuel, Stefan Haeussler, and Juanjo Peiro. Average reward adjusted deep reinforcement learning for order release planning in manufacturing. Knowledge-based systems 247 (2022): 108765.

[18] Hisaki, Yukinari, and Isao Ono. RVI-SAC: average reward off-policy deep reinforcement learning. arXiv preprint arXiv:2408.01972. 2024

[19] Zhang, Yiming, and Keith W. Ross. On-policy deep reinforcement learning for the average-reward criterion. International Conference on Machine Learning. 2021.

We thank the reviewer for the constructive feedback.

Weakness

(i) As the reviewer pointed out, [1,2] have studied the anchoring mechanism in tabular setting. However, it was not known whether the anchoring mechanism provides benefit in the offline RL setting, where only given dataset is available and distribution mismatch between the data distribution and the transition matrices could cause problem. Moreover, it was not clear whether the anchoring mechanism could be incorporated with general function that approximate the output of the Bellman operator in a supervised learning manner. In this paper, we address these questions and, for the first time, establish finite time bounds for the offline average reward setting for both IID and single-trajectory datasets.

(ii) We first note that in the tabular setup, the iterates of Value Iteration (VI) asymptotically behave as $V^k \sim \Theta(k)$ as $k \rightarrow \infty$ where $V^k$ is $k$-th iterate [3]. Since in our framework, the general function $f_k$ attempts to approximate $V^k$ with offline data, considering the tabular setup as a baseline for the offline setup, we believe that the increasing function range assumption $\|f_k\| \sim \Theta(k)$ is acceptable.

To address this divergence of the iterates of VI, [4] proposed relative VI which normalizes the iterates by subtracting a uniform constant vector at each iteration. Motivated by this, we propose Relative Anchored Fitted Q-Iteration with function range assumption, specifically assuming $\|f_k\| \sim \Theta(1)$, and as shown in Theorems 3 and 4, we obtained finer sample complexities $\tilde{O}(\epsilon^{-4})$ and $\tilde{O}(\epsilon^{-8})$ for IID and single-trajectory dataset, respectively.

(iii) As reviewer pointed out, in our Theorems 1 and 2, the policy error is bounded by a given $\epsilon$ and an $O(K)$ term containing the coverage coefficient and inherent Bellman error, where, by condition of Theorem, $K$ is fixed if $\epsilon$ is fixed. We note that if the inherent Bellman error is low or the approximation power of the function class is strong enough, this term can be relatively small. Or, it can be ignored under the Bellman completeness assumption, which assumes that the inherent Bellman error is zero. These assumptions, low inherent Bellman error and Bellman completeness, are commonly used in the RL theory literature [5, 6]. Furthermore, we believe this $O(K)$ term in the theoretical upper bound is natural in average reward analysis (please refer to response (v)).

(iv) The reviewer raises a good point. We first note that in section 5, we presented Relative Anchored Fitted Q-Iteration and further obtained refined sample complexities of $\tilde{O}(\epsilon^{-4})$ and $\tilde{O}(\epsilon^{-8})$ for IID and single-trajectory datasets. Also, to the best of our knowledge, there exist two prior works that studied the sample complexity in this setup. [7] and [8] obtained $\tilde{O}(\epsilon^{-2})$ and $\tilde{O}(\epsilon^{-4})$ sample complexities for IID datasets under ergodic and unichain MDPs, respectively, and our Theorem 3 provides a $\tilde{O}(\epsilon^{-4})$ sample complexity for IID datasets under weakly commuting MDPs. But none of prior works address single-trajectory datasets.

As far as we know, there exist no lower bound results in the offline average reward setting. Hence, it is subtle to argue the tightness and optimality of our sample complexity results. However, reflecting optimality results in the discounted reward setup, we expect that our results may be tight or close to optimal sample complexity with respect to $\epsilon$. To be more precise, we speculate that the optimal sample complexity of the average reward setup would be the square of the optimal sample complexity of the discounted reward setup.

In the discounted reward setup, [9, 10] established a $\tilde{O}(\epsilon^{-2})$ lower bound on sample complexity for IID datasets, and several works achieve optimal sample complexity. For the single-trajectory dataset, to the best of our knowledge, there exist no lower bound results, but [11] establishes $\tilde{O}(\epsilon^{-4})$ sample complexity. Considering the technical difficulty in the average reward setup (please refer to response (v)), we carefully expect that our sample complexity results in the average reward setup, $\tilde{O}(\epsilon^{-4})$ and $\tilde{O}(\epsilon^{-8})$ for IID and single-trajectory datasets, which are exactly the squares of the sample complexities in the discounted reward setup, $\tilde{O}(\epsilon^{-2})$ and $\tilde{O}(\epsilon^{-4})$, would be tight or close to optimal. But, as we said, a lower bound in the offline average reward setting remains unknown, and studying optimality in this setup would be an interesting research direction.

(v) To the best of our knowledge, in the discounted reward offline RL setting, there exists an $\epsilon^{-2}$ gap between IID and mixing single-trajectory datasets. Roughly speaking, [5] provides a sample complexity $\tilde{O}(\epsilon^{-2})$ for an IID dataset, whereas [11] proves a sample complexity $\tilde{O}(\epsilon^{-4})$ for a mixing single-trajectory dataset. This discrepancy arises from the different concentration inequalities used in the analyses. In particular, [5] applies Bernstein’s inequality, while [11] uses Pollard’s tail inequality generalized to mixing single-trajectory data, and Pollard’s tail inequality yields looser bounds than Bernstein’s inequality. This induces an $\epsilon^{-2}$ gap between IID and mixing single-trajectory datasets.

Turning to the average reward setup, in the proofs of our Lemmas 5 and 11, we also apply Bernstein’s inequality and the generalized Pollard inequality. Thus, similarly, we have an $\epsilon^{-2}$ gap. But, moreover, an additional gap occurred for the following reason: in the discounted reward setup, the sum of sample errors is bounded by $\sum_{i=1}^{K}\gamma^{i}\epsilon\le \frac{\epsilon}{1-\gamma},$ where $\epsilon$ is the per-iteration sample error. However, in the average reward setup, where the discount factor is considered equal to $1$, we get $O(K)$ bound on the sum of sample errors proportional to the number of iterations by $\sum_{i=1}^{K}\epsilon \le K\epsilon.$ This caused an additional gap in the average-reward setup, and consequently, our results exhibit an $\epsilon^{-4}$ gap, which is the square of the $\epsilon^{-2}$ gap in the discounted reward setup.

Lastly, [12] indeed establishes a sample complexity $\tilde{O}(\epsilon^{-2})$ for both IID and single‑trajectory datasets. However, that paper studies a different setting from ours in two respects. First, Algorithm 1 performs online updates, sampling state and action in real time, so its theoretical analysis does not require the coverage condition that offline RL usually needs to address the distribution shift [5,11]. Second, the paper considers the policy evaluation problem of estimating $V^{\pi}$ for a given policy $\pi$, whereas we study the policy control problem of finding the optimal policy $\pi^{\star}$. We think that the different results follow from different setups.

(vi) First, we clarify that our work does not assume a mixing MDP for either the IID or single‑trajectory setting. Actually, we assume only that the single-trajectory dataset, generated by a specific behavior policy, is mixing. As noted in the introduction, a mixing MDP requires the mixing condition to hold for every policy and initial distribution, whereas our mixing assumption requires it to hold only for the behavior policy and the distribution of the dataset. Thus, our mixing assumption on single-trajectory datasets is much weaker than the mixing assumption on the MDP, and therefore, sample complexity results in the discounted reward setting under mixing Markov chains do not imply our results in either the IID or single-trajectory setting.

We kindly ask that the reviewer consider raising the score if our answer addresses their concerns and questions.

References

[1] J. Lee and E. Ryu. Accelerating value iteration with anchoring. Neural Information Processing Systems, 2023.

[2] J. Lee and E. Ryu. Optimal non-asymptotic rates of value iteration for average-reward MDPs International Conference on Learning Representations, 2025.

[3] M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, 2014

[4] D. J. White. Dynamic programming, Markov chains, and the method of successive approximations. J. Math. Anal. Appl, 6(3):373–376, 1963.

[5] J. Chen and N. Jiang. Information-theoretic considerations in batch reinforcement learning. International Conference on Machine Learning, 2019.

[6] A. Zanette, A. Lazaric, M. Kochenderfer, E. Brunskill, Learning near optimal policies with low inherent bellman error. International Conference on Machine Learning 2020.

[7] A. Ozdaglar, S. Pattathil, J. Zhang, and K. Zhang. Offline reinforcement learning via linear programming with error-bound induced constraints. arXiv preprint arXiv:2212.13861, 2024.454

[8] G. Gabbianelli, G. Neu, M. Papini, and N. M. Okolo. Offline primal-dual reinforcement learning for linear MDPs. International Conference on Artificial Intelligence and Statistics, 2024

[9] G. Li, et al. Settling the sample complexity of model-based offline reinforcement learning. The Annals of Statistics 52.1 (2024): 233-260.

[10] P. Rashidinejad, et al. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems 34 (2021): 11702-11716.

[11] A. Antos, C. Szepesvári, and R. Munos. Learning near-optimal policies with bellman-residual minimization based fitted policy iteration and a single sample path. Machine Learning, 2008.

[12] J. Bhandari, D. Russo, R. Singal. A finite time analysis of temporal difference learning with linear function approximation. Conference on learning theory, 2018.

We thank the reviewer for insightful feedback.

Questions

1. Our analysis of anchored fitted Q‑Iteration uses the full coverage condition to bound the products of transition matrices induced by policies. As shown in the proof of Proposition 1, the policy error of approximate anchored Q‑Iteration is bounded by a sum of such products with products of coefficients due to the the anchoring mechanism. To control these terms, we exploit the full coverage coefficient and thereby obtain finite sample complexity. We note that this is how standard fitted Q‑Iteration analyses in the discounted reward setting use the full coverage condition [1,2], and lastly, we briefly note that our anchoring mechanism might provide finite sample complexity guarantees under partial coverage conditions by incorporating a pessimistic approach [3-5].

References

[1] J. Chen and N. Jiang. Information-theoretic considerations in batch reinforcement learning. International Conference on Machine Learning, 2019.

[2] R. Munos and C. Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 2008

[3] Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch off-policy reinforcement learning without great exploration. Neural Information Processing Systems, 2020

[4] T. Xie, C.-A. Cheng, N. Jiang, P. Mineiro, and A. Agarwal. Bellman-consistent pessimism for offline reinforcement learning. Neural Information Processing Systems, 2021

[5] Y. Jin, Z. Yang, and Z. Wang. Is pessimism provably efficient for offline RL? International Conference on Machine Learning, 2021

We thank the reviewer for the positive feedback.

Questions

1. We expect that our anchoring mechanism can provide finite sample complexity guarantees under partial coverage condition by incorporating a pessimistic approach. A series of works [1–3] has shown that penalizing the estimated value or policy according to its uncertainty relaxes the need for full coverage condition. In particular, [3] introduced Pessimistic Value Iteration, which subtracts an uncertainty term scaled by a confidence parameter from the estimated Q‑value, and achieve finite bounds under partial coverage condition. Referring to those prior works, by combining our anchoring mechanism with this pessimistic approach, we believe that our analysis can be extended to the partial coverage setting.

2. In the proofs of our Theorems, we observed that the sample error incurred at each iteration grows proportionally with the number of iterations and $O(K)$ terms appeared in the upper bound of policy error, where $K$ is number of iterations. In contrast, in the discounted‑reward setting, sum of sample error is bounded by $\sum_{i=1}^{K}\gamma^{i}\epsilon \le \frac{\epsilon}{1-\gamma}$ where $\epsilon$ is the per‑iteration sample error (note that the discount factor is considered equal to $1$ in average reward setup). Adding the complexity of Bellman equation, we believe that the sample error in the average reward setup is harder to control. Nevertheless, as we noted in the conclusion, more efficient sample complexity bounds might be obtained by applying variance reduction techniques [4-6] .

Some comments

1. We briefly note that Assumption 1 is valid for weakly communicating MDPs, and a different assumption is needed for multichain MDPs. For multichain MDPs, the most general class of MDP, it is known that the Bellman equations consists of two coupled equations and requires more complicated analysis [7].

References

[1] Yao Liu, Adith Swaminathan, Alekh Agarwal, and Emma Brunskill. Provably good batch off-policy reinforcement learning without great exploration. Neural Information Processing Systems, 2020

[2] T. Xie, C.-A. Cheng, N. Jiang, P. Mineiro, and A. Agarwal. Bellman-consistent pessimism for offline reinforcement learning. Neural Information Processing Systems, 2021

[3] Y. Jin, Z. Yang, and Z. Wang. Is pessimism provably efficient for offline RL? International Conference on Machine Learning, 2021

[4] M. J. Wainwright. Variance-reduced Q-learning is minimax optimal. arXiv preprin arXiv:1906.04697, 2019.498

[5] J. Lee, M. Bravo, and R. Cominetti. Near-optimal sample complexity for MDPs via anchoring. Interantional Conference on Machine Learning, 2025

[6] A. Sidford, M. Wang, X. Wu, and Y. Ye. Variance reduced value iteration and faster algorithms for solving Markov decision processes. Naval Research Logistics, 70(5):423–442, 2023.

[7] M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley and Sons, 2014