- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper study average reward optimization in regularized MDPs. The authors show that the typical assumptions necessary in this setting is that the environment satisfies a contraction property. This facilitates the analysis because it ensures that most actions in the environment lead to for example mixing conditions. Instead in this work the authors study a scenario where an m-step mixing policy is given and they derive finite bounds for the convergence rate of Q-iteration, learning with a generative model, and an algorithm based on training on a single trajectory.
Critical strengths
The paper seems to be technically correct. I didn't find any major issues in the writeup. As far as I know this is the first work that shows that this is the first paper introducing a theory that shows how to regularize towards a mixing policy can be used to get convergence guarantees for average reward Q learning. This seems to be a novel and interesting contribution to the community.
Critical weaknesses
The main weakness is the slightly confusing way in which the paper is presented. I think the paper is a bit tricky to read. It jumps into very heavy notation very fast. Additionally, it does not really place within the literature how the contributions of this paper are novel as compared with what was already out there.
Questions for authors
If you had some comments on:
- What is really concretely the main novelty claim of the paper.
- What is the main technical contribution that can enabled to obtain these new results.
Regarding Weakness 1 (paper presentation): we have substantially revised the manuscript to address feedback on presentation and literature positioning: we rewrote Section 1 (Introduction) to motivate and state our contributions before introducing mathematical notation, streamlined Section 2 (adding the 1-step Doeblin condition in Eq. (2)) and Section 4 (simplifying Theorems 1–3 and deferring technical thresholds to Appendices H–I), reordered Section 3.2 and added Figure 1 to visually illustrate the mechanism, and expanded Section 6 and Table 2 to clarify how our results compare to prior work.
Regarding Weakness 2 (literature — Sections 3.2 & 6, Table 2): as now discussed at the end of Section 3.2 and in Section 6 (with a detailed comparison in Table 2), Neu et al. (2017) and Adamczyk et al. (2025) study KL/entropy regularization in average-reward MDPs without deriving mixing transfer or finite-time Q-learning bounds. Zhang et al. (2021) and Chen (2025) assume multi-step or one-step span contraction directly, and Chen et al. (2026, Lemma B.6) use a related factorization for hard maxima to analyze a lazy Bellman operator under all-policy reachability. Lee (2026, Lemma 6) uses a related factorization for hard maxima in the discounted setting. The new link in our analysis is the quantitative transfer from one mixing reference policy to both the Bellman operator and the learning trajectory through the factorized average-path kernel.
Regarding Question 1 (main novelty — Section 3 & Lemma 1): we show how to turn a mixing guarantee for one reference policy μ into guarantees for the policies produced during learning. Starting from an m-step Doeblin condition on μ (Assumption 1), regularization toward μ yields two properties (Lemma 1): the regularized Bellman operator contracts in span over m steps, and the changing greedy policies visit every state–action pair with a quantifiable probability along a single trajectory. The same domination profile γΩ (Definition 1) determines both bounds. Together with a bound on the bias introduced by regularization via the modulus ΛΩ (Definition 2 and Lemma 1.(iii)), this gives a framework for deriving finite-time guarantees across different regularizers and algorithms (Theorems 1–3 and Table 1). To our knowledge, this is the first work to establish finite-time average-reward Q-learning and planning guarantees from a single mixing reference policy rather than assuming environment-wide contraction or all-policy mixing, providing a practical tool to compare and design regularizers (such as the α-divergence family in Table 1).
Regarding Question 2 (key technical step — Section 3.2, Figure 1 & Appendix H): in Section 3.2, we write a difference of regularized Bellman updates as TΩ(Q)−TΩ(Q′)=KπˉΩ,[Q,Q′](Q−Q′), where πˉΩ,[Q,Q′] averages the regularized greedy policies along the segment between Q and Q′ (illustrated in Figure 1a). This average preserves their pointwise domination of the reference policy (Figure 1b). That property lets us transfer the reference minorization to products of the averaged kernels for contraction (Lemma 1.(i)) and to the policies that generate the trajectory for coverage (Lemma 1.(ii)). In Appendix H.2, we combine this with a block-Jacobian analysis showing that the step size αt acts as a lazy transformation on these kernels, allowing standard one-step Q-learning updates to inherit the m-step contraction. Unlike unregularized hard-max factorizations—whose mediating policy need not retain the mixing of a single reference policy—this average-path representation and block-Jacobian technique are new and allow us to analyze unmodified one-step Q-learning updates without requiring multi-step estimators (Zhang et al., 2021) or the lazy Bellman operator of Chen et al. (2026).