acceptodds
Under review as a conference paper at ICLR 2027

Mixing Regularization for Average-Reward -Learning and -Planning

Abstract

The average-reward setting for reinforcement learning is challenging because its Bellman operator is known to contract in span only when the underlying Markov chain is mixing. Whereas existing work typically a contraction property, e.g. through environment mixing, we consider the setting where we are given a reward-agnostic -step mixing policy, and we the contraction and exploration properties of the learned policy by regularizing toward the mixing policy. We provide finite-time analysis of -learning algorithms that can be instantiated with multiple choices of regularization, with guarantees measured with respect to the regularized fixed point. Our framework exposes novel regularizer-dependent objects that control contraction, exploration, and operator bias. In the one-step setting, our rates match the best known rates for -iteration and synchronous -learning, and for -step mixing we derive new rates. We also study -planning variants, and show that planning acts as time-localized learning, where the planning horizon trades off the bias from the boundary value against the sample complexity. Finally, we present numerical studies validating the analysis: (i) knowledge of a strong mixing policy improves convergence and exploration, and its advantage increases with bottleneck severity and (ii) our theory predicts the convergence and bias rankings of regularizers from the -divergence family.

Primary area:
reinforcement learning
Keywords:
Finite Sample Analysis, Average-Reward Reinforcement Learning, Q-learning

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_Nd6sOpenReview ↗
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:

  1. What is really concretely the main novelty claim of the paper.
  2. What is the main technical contribution that can enabled to obtain these new results.
1 comment

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 QQ-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 μ\mu into guarantees for the policies produced during learning. Starting from an mm-step Doeblin condition on μ\mu (Assumption 1), regularization toward μ\mu yields two properties (Lemma 1): the regularized Bellman operator contracts in span over mm steps, and the changing greedy policies visit every state–action pair with a quantifiable probability along a single trajectory. The same domination profile γΩ\gamma_\Omega (Definition 1) determines both bounds. Together with a bound on the bias introduced by regularization via the modulus ΛΩ\Lambda_\Omega (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 QQ-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 α\alpha-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′)\mathcal{T}_\Omega(Q)-\mathcal{T}_\Omega(Q') = K_{\bar\pi_{\Omega,[Q,Q']}}(Q-Q'), where πˉΩ,[Q,Q′]\bar\pi_{\Omega,[Q,Q']} averages the regularized greedy policies along the segment between QQ and Q′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\alpha_t acts as a lazy transformation on these kernels, allowing standard one-step QQ-learning updates to inherit the mm-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 QQ-learning updates without requiring multi-step estimators (Zhang et al., 2021) or the lazy Bellman operator of Chen et al. (2026).

Reviewer_kJV6OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper deals with the average reward reinforcement learning setting. The paper mentions that the design of algorithms that exploit the knowledge of mixing policies is understudied. This work aims to theoretically explore the effect of regularization on the control of the contraction, exploration, bias and sample complexity of average-reward Q learning. The perform experiments on a simple toy MDPs and simple gridworlds.

Critical strengths

(1) The authors study the effect of regularization with the knowledge of mixing policis rigorously.

(2) The authors derive the sample complexity of the framework as well.

Critical weaknesses

(1) The paper presentation can improve a lot. The paper does not do a good job of introducing all the components. For instance, the abstract contains, "our rates match the best known rates for Q-iteration..." It was not entirely clear at this point, what do the author mean by rates. Similarly, in the introduction, rather explaining the motivation and their contribution at a higher and motivating level, they dive straight into the mathematical design. The introduction was a lot more understandable after reading the preliminaries, and some portion of their main text.

(2) The authors also miss the opportunity to explain a lot more concepts in the preliminaries such as what do they mean by a mixing policy etc.

(3) The authors also are unable to draw connections to practical applications of this study. While the theoretical discussions are interesting, it is useful if some motivation is drawn towards the practical consequences of the study. The experiments are on very simple MDPs, which is understandable given the control needed for defining the mixing policies but I am not sure if such knowledge of the mixing policy would be available in more practical domains.

Questions for authors

(1) The authors mention "is natural in domains like robotics and fine-tuning, where new tasks are learned starting from an existing policy", but in such domains is it possible to have the knowledge of the mixing policy? That means, are the existing policies at all mixing? Are they m-step mixing with us knowing what is the value of m and the parameter βm\beta_m

1 comment

Regarding Weakness 1: we rewrote the Abstract and Section 1 to explain why mixing matters and state our motivation and contributions at a high level before introducing the technical details. The Abstract now specifies that the one-step bounds count model queries for QQ-iteration and sampled transitions for synchronous QQ-learning, with accuracy measured in span to QΩ∗Q_\Omega^*.

Regarding Weakness 2: in the revised Introduction, we define what "mixing" means in the paper. Section 2.1 (Eq. (2)) and Section 3.1 (Assumption 1) build from one-step to mm-step Doeblin minorization, the new Figure 1 in Section 3.2 illustrates how regularization transfers mixing, and Section 4 streamlines Theorems 1–3 by deferring technical parameter thresholds to Appendices H and I.

Regarding Weakness 3: we added connections to practical algorithms like SAC and PPO in the Introduction. As the focus of our work is theoretical, we consider complex experiments beyond the scope of the paper.

Regarding Question 1: the revised Introduction cites reference-policy fine-tuning (Xie et al., 2021) and online adaptation of pretrained policies in real robotic manipulation (Yang et al., 2024). A pretrained policy can have limited action support or visit only a small part of the state space, though a stochastic actor or a small uniform floor ensures full support. In our finite tabular setting, every full-support policy satisfies Assumption 1 for some finite mm if and only if the union transition graph is strongly connected and aperiodic (Appendix D, Propositions D.1–D.2), while μ\mu determines the constant βm\beta_m (Section 5.2, Figure 2). Crucially, our learning algorithms (Algorithms 1–3, Appendix B) only query μ(a∣s)\mu(a|s) and do not take mm or βm\beta_m as inputs. With a known model, one can find an admissible mm and compute βm\beta_m from the worst-case mm-step state probabilities, and this certificate carries over when fine-tuning changes only the reward. The updates can run with empirically chosen hyperparameters, while the certified schedules (Theorems H.2 and H.4) require quantitative mixing bounds. Establishing such bounds from robot rollouts remains a practical limitation of our approach (Section 7).

Reviewer_vGbaOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies average-reward learning with access to a full-support reference policy satisfying an m-step Doeblin condition. Regularization toward this policy induces a domination profile that transfers mixing to regularized greedy policies and controls both Bellman contraction and state-action coverage. A separate regularization modulus controls bias. The framework yields finite-time results for synchronous Q-iteration, synchronous Q-learning, single-trajectory epoch Q-learning, and localized planning. Alpha-divergence instances and tabular experiments illustrate the resulting convergence–exploration–bias trade-offs.

Critical strengths
  1. Using the same domination profile to explain contraction and exploration provides a coherent account of how a reference policy can help average-reward learning. The operator-difference representation makes the mechanism explicit.

  2. The paper separates several sources of difficulty through distinct algorithmic settings and derives regularizer-specific quantities rather than treating regularization as a generic perturbation. The experiments at matched bias are particularly helpful for interpreting convergence differences.

Critical weaknesses
  1. The headline sample complexities target the regularized fixed point. Although the paper provides bias and greedy-policy performance bounds, the practical comparison with methods targeting the original objective requires combining these bounds with the temperature dependence of the domination profile and solution radius. This can substantially worsen the effective complexity, particularly when the profile becomes small. An explicit end-to-end specialization would make the significance of the rates easier to assess.

  2. The finite-time prescriptions involve quantities such as the initial error, solution span, and mixing constants that may be unavailable in a model-free setting. The experiments demonstrate qualitative mechanisms in small tabular environments, but do not establish whether the theoretical parameter choices provide an implementable and useful procedure when these quantities are unknown.

Questions for authors
  1. Combining Corollary G.3 with the learning bounds, what explicit complexity follows for an ε-optimal policy under the original average-reward objective for representative KL and Hellinger regularizers, including all temperature-dependent constants?

  2. Which bounds must be supplied to choose the learning rate and epoch batch size in practice? Can conservative quantities derived from the reference policy and reward range replace the unknown solution-dependent terms, and how loose are they in the experimental environments?

1 comment

Regarding Question 1 (sample complexity and regularization bias): we respectfully maintain our position that, at fixed temperature, the regularized fixed point QΩ∗Q_\Omega^*—rather than Q∗Q^*—is the appropriate target for sample-complexity guarantees. Because QΩ∗Q_\Omega^* is the fixed point of TΩ\mathcal{T}_\Omega, increasing the sample budget drives the span error ∣Qt−QΩ∗∣sp\\|Q_t - Q_\Omega^*\\|_{\mathrm{sp}} to zero, whereas the regularization bias relative to Q∗Q^* (Lemma 1.(iii)) persists even at exact convergence and infinite samples. Measuring sample complexity against the regularized target is standard in prior work (Grill et al., 2019, Theorems 1–2; Lan, 2023, Proposition 1; Cayci et al., 2024). We now state this separation explicitly at the beginning of Section 4, in Section 4.2, and in Table 2.

Nevertheless, to answer your question directly for the unregularized gain ρ∗\rho^*, Corollary G.3 gives ρ∗−ρπΩ,Q(s)≤∣Q−QΩ∗∣sp+τΔΩ\rho^*-\rho^{\pi_{\Omega,Q}}(s)\leq\\|Q-Q_\Omega^*\\|_{\mathrm{sp}}+\tau\Delta_\Omega, so setting τ=ε/(2ΔΩ)\tau=\varepsilon/(2\Delta_\Omega) and targeting span error e=ε/2e=\varepsilon/2 guarantees an ε\varepsilon-optimal policy. At the temperature-independent radius R=3UR=3U (with UU defined below), the domination-dependent factors γΩ(R)−k\gamma_\Omega(R)^{-k} in the sufficient sample budgets scale, up to logarithmic terms, as

exp⁡!(2kRlog⁡(1/μmin⁡)ε)for reverse KL,(1+4R(1−μmin⁡)ε)2kfor Hellinger,\exp\\!\left(\frac{2kR\log(1/\mu_{\min})}{\varepsilon}\right) \quad\text{for reverse KL},\qquad \left(1+\frac{4R(1-\sqrt{\mu_{\min}})}{\varepsilon}\right)^{2k} \quad\text{for Hellinger},

where k=3(m−1)k=3(m-1) for synchronous learning (Theorem 1) and epoch learning under μ\mu (Remark H.7), and k=4m−3k=4m-3 for on-policy epoch learning (Theorem 2). Multiplying by ε−2\varepsilon^{-2}, the resulting static-temperature upper bounds grow polynomially in 1/ε1/\varepsilon for Hellinger (O~(ε−(2k+2))\widetilde O(\varepsilon^{-(2k+2)})) and exponentially for reverse KL when k>0k>0. We leave the analysis of temperature schedules to future work, with the goal of reducing bias while retaining the mixing benefits of regularization early in learning.

Regarding Question 2 (learning rate and epoch batch size): recall the theoretical learning rate and batch schedules to reach span error ee (deferred to Appendix H, Theorems H.2 and H.4):

α(e/2)=β~2e236m(2+β~)2(1+9m)2wˉ2ι,⌈B(e/2)⌉=⌈32m2wˉ2ιβ~2e2⌉,\alpha(e/2)=\frac{\tilde\beta^2 e^2}{36m(2+\tilde\beta)^2(1+9m)^2\bar w^2\iota}, \qquad \lceil B(e/2)\rceil=\left\lceil\frac{32m^2\bar w^2\iota}{\tilde\beta^2 e^2}\right\rceil,

where ι=log⁡(6∣S∣∣A∣(T+1)/δ)\iota=\log(6|\mathcal{S}||\mathcal{A}|(T+1)/\delta). The unknown quantities are the initial span error e0e_0, noise scale wˉ\bar w, and contraction constant β~\tilde\beta. With Q0=0Q_0=0 and a divergence to μ\mu, we propose to compute UU using knowledge of the reference policy and a certified Doeblin minorization for it: U=∣r∣sp(1+mβmνmin⁡)U=\\|r\\|_{\mathrm{sp}}\bigl(1+\frac{m}{\beta_m\nu_{\min}}\bigr), noting that e0≤Ue_0 \leq U and wˉ≤3U\bar w \leq 3U. Finally, the analytic lower bound on γΩ(3U)\gamma_\Omega(3U) (Table 1) gives β~≥βmγΩ(3U)m−1\tilde\beta\geq\beta_m\gamma_\Omega(3U)^{m-1}. We include this discussion in Appendix G.3.3.

In Two Rooms, under uniform μ\mu, the theoretical coverage scale is 6969, 5252, and 3939 times the observed median B=1B=1 epoch length at pcross=0.05p_{\text{cross}}=0.05, 0.30.3, and 11, respectively. In RiverSwim, the uniform-reference certificate at m=14m=14 gives U≈6,984U\approx 6{,}984, over 400400 times the regularized span at matched bias. These comparisons quantify the looseness of the coverage and span bounds, while the full prescribed schedules remain to be benchmarked. These empirical comparisons are discussed in Appendices C.1 and C.2.

In summary, the theoretical step size and batch size can be computed from supplied bounds on (∣r∣sp,m,βm,νmin⁡)(\\|r\\|_{\mathrm{sp}}, m, \beta_m, \nu_{\min}), while in practice they are easy to tune and match standard empirical practice.

Comments on the paper

1 comment

We thank the reviewers for their constructive feedback and positive assessment of the technical contributions. We have revised the manuscript to improve accessibility, explain the central mechanism more clearly, and clarify the scope and calibration of our guarantees. The revised PDF is uploaded. The main algorithms and leading sample-complexity rates are unchanged.

The main changes are:

  1. More accessible motivation and background (Sections 1–2). We rewrote the introduction around the motivation and high-level contributions, removing the technical rate expressions. We also expanded the explanation of mixing and Doeblin minorization and discussed connections to policy fine-tuning and entropy-regularized RL.

  2. A clearer explanation of the core contribution (Section 3). We now derive the operator-difference identity before stating the mixing lemma, making explicit how mixing transfers through the averaged greedy policy to both Bellman contraction and trajectory coverage. The new Figure 1 illustrates the averaged policy, kernel domination, and temperature trade-off.

  3. Simplified presentation of the algorithmic results (Section 4). We simplified the main learning-theorem statements, retaining detailed constants and parameter prescriptions in Appendix H and grouping the pseudocodes in Appendix B. We also brought the planning error bound into the main text as Theorem 3.

  4. More explicit scope and calibration of the guarantees. Section 4.2 now states the connection between regularized span accuracy and performance under the original objective. Appendix G.3.3 adds a temperature-independent span bound derived from the reward range and a certified reference-policy minorization, and Appendix C.2 illustrates its conservativeness on RiverSwim.

  5. Sharper positioning and experimental presentation. We refined the comparisons with prior work in Section 6 and Table 2, clarified the experimental descriptions and captions, and tightened several technical statements and proof details in the appendices.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.