acceptodds
Under review as a conference paper at ICLR 2027

V-share: Provable Convergence Guarantees for Advantage-based Algorithms

Abstract

In reinforcement learning, advantage-based value-learning methods, unlike standard Q-learning, share information across actions by decomposing the action-value function into a state-dependent value component and action-specific advantages. While this mechanism has proved effective in both tabular and deep reinforcement learning, its theoretical understanding remains incomplete. We introduce **V-share**, an advantage-based value-learning algorithm that combines cross-action value sharing with an importance-weighted Bellman-residual correction. To our knowledge, we provide the first complete theoretical characterization of an advantage-based algorithm, including both asymptotic convergence and non-asymptotic finite-sample guarantees. We identify a regime in which V-share mitigates the rare-action bottleneck of asynchronous Q-learning and uncover a contraction–variance tradeoff between stronger deterministic contraction and increased importance-weighting noise. Motivated by this tradeoff, we develop decreasing residual-preconditioning schedules that combine faster early contraction with lower asymptotic noise. We further develop a two-timescale analysis that removes the single-timescale residual-weight threshold while preserving convergence guarantees. Experiments on discrete Markov decision processes (MDPs) and deep reinforcement-learning benchmarks corroborate our results.

Primary area:
reinforcement learning
Keywords:
Reinforcement Learning Theory, Algorithm Convergence Analysis, Advantage-based Algorithms

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_qrV6OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes V-SHARE, an advantage-based value-learning algorithm that combines cross-action value sharing with an importance-weighted Bellman-residual correction. The authors provide asymptotic and finite-time convergence guarantees under Markovian sampling, including decreasing-β\beta and two-timescale variants, and evaluate the method on tabular MDPs and deep RL benchmarks.

Critical strengths

1.The paper addresses a concrete theoretical difficulty introduced by cross-action value sharing and provides a coherent convergence analysis for the resulting stochastic updates. In particular, V-SHARE preserves the shared value component while adding an importance-weighted residual correction, and establishes both almost-sure and finite-time guarantees under Markovian sampling.

  1. The analysis goes beyond a single convergence result by characterizing the role of β\beta, developing decreasing-β\beta schedules, and providing a two-timescale formulation that removes the single-timescale threshold under timescale separation. These results give a broader picture of the stability–noise tradeoff and the different regimes in which V-SHARE can be analyzed.
Critical weaknesses

1.The main tabular experiments used to illustrate the single-timescale contraction–variance tradeoff are not aligned with the stated sufficient contraction regime. In the reported setup, γ=0.95\gamma=0.95, there are five actions, and ϵ=0.8\epsilon=0.8, giving bmin⁡=0.16b_{\min}=0.16; Lemma B.2 therefore requires β>32.6\beta>32.6, whereas Figure 1 uses β≤2\beta\leq2. The experiments demonstrate an interesting empirical trend, but they do not directly validate the regime covered by the corresponding theory.

2.The paper does not fully disentangle the effect of cross-action value sharing from the importance-weighted residual correction. Since the rare-action improvement in the mean dynamics is closely tied to the importance weighting, the mechanism behind the claimed acceleration should be stated more carefully.

Questions for authors

1.Could the authors clarify how the tabular experiments relate to the sufficient contraction condition, given that the reported β\beta values appear to lie outside the regime guaranteed by Lemma B.2?

  1. Could the authors clarify which part of the rare-action improvement should be attributed specifically to cross-action value sharing, rather than to the importance-weighted residual correction?
4 comments
AuthorsOpenReview ↗

Author Response Part 1

We thank the reviewer for their positive assessment of our contributions and for their constructive questions. We address each question below.

W1. Mismatch between the experimental parameters and the sufficient contraction regime.

We acknowledge that the values of β\beta used in the original tabular experiments lie outside the sufficient contraction regime of Lemma B.2. These values were chosen to illustrate the contraction–variance tradeoff more clearly, and the sufficient condition should not be interpreted as necessary for convergence.

To address this concern, we conduct additional experiments with larger values of β\beta satisfying the theoretical contraction condition. As shown in Appendix G, we observe the same qualitative contraction–variance tradeoff in this regime. We discuss these results further in our response to Q1.

W2. Distinguishing value sharing from importance-weighted residual correction.

We appreciate the reviewer's suggestion to clarify the respective roles of the two mechanisms. The central motivation behind V-SHARE is to retain the empirical benefits of cross-action value sharing, which have also been observed in existing advantage-based algorithms, while developing rigorous convergence guarantees for the resulting coupled dynamics.

Value sharing is thus an essential component of the proposed algorithm. However, the cross-action coupling introduced by value sharing prevents the standard sup-norm contraction argument used for asynchronous Q-learning. Our residual-preconditioning approach is designed to overcome this analytical difficulty, enabling us to establish a sufficient contraction regime for the combined dynamics and derive asymptotic and finite-time convergence guarantees under Markovian sampling.

Furthermore, Figure 2(b) provides complementary empirical evidence for the contribution of value sharing. Increasing the value-sharing timescale ratio generally accelerates transient convergence while maintaining comparable steady-state error floors. Thus, the experiments suggest an additional benefit of value sharing beyond the convergence guarantees captured by our current analysis. We clarify the respective roles of the two mechanisms further in our response to Q2.

We continue our response in the next official comment, Author Response Part 2.

AuthorsOpenReview ↗

Author Response Part 2

Q1. Could the authors clarify how the tabular experiments relate to the sufficient contraction condition, given that the reported β\beta values appear to lie outside the regime guaranteed by Lemma B.2?

We acknowledge that the condition in Lemma B.2 is sufficient rather than necessary, and our experimental observations suggest that it can be conservative. We deliberately chose smaller values of β\beta in the original tabular experiments to illustrate the contraction–variance tradeoff more clearly. In particular, varying β\beta in this regime allows us to better distinguish its effects on transient convergence and the steady-state error floor.

We observe the same qualitative contraction–variance tradeoff for larger values of β\beta satisfying the sufficient condition of Lemma B.2. We have included these additional experiments in Appendix G of the updated manuscript. Thus, the original and additional experiments illustrate the behavior of V-SHARE both outside and within the theoretically guaranteed contraction regime.

Q2. Could the authors clarify which part of the rare-action improvement should be attributed specifically to cross-action value sharing, rather than to the importance-weighted residual correction?

We thank the reviewer for raising this important distinction. The two mechanisms play complementary roles in V-SHARE. The limiting ODE dynamics decompose as

\underbrace{DB(\mathcal TQ-Q)}_{\text{cross-action value sharing}} + \underbrace{\beta D(\mathcal TQ-Q)}_{\text{importance-weighted residual correction}}.$$ The first term propagates information across actions, whereas the second removes the dependence on behavior action probabilities in the diagonal component. The cross-action coupling introduced by value sharing prevents the standard sup-norm contraction argument, while the importance-weighted correction enables us to establish contraction for sufficiently large $\beta$. In particular, the removal of the multiplicative rare-action factor $b_{\min}$ from the leading-order contraction gap in our theoretical comparison is attributable to the importance-weighted residual correction. Moreover, Figure 2(b) partially isolates the contribution of value sharing by varying $r=\alpha_V/\alpha_A$, where $r=0$ removes value sharing while retaining the importance-weighted correction. Increasing $r$ generally accelerates transient convergence, with comparable, occasionally slightly higher, steady-state error floors. Thus, the two mechanisms play complementary roles: cross-action value sharing is central to V-SHARE and contributes to the empirical transient acceleration observed in our experiments, while residual preconditioning enables rigorous convergence guarantees for the combined dynamics. As acknowledged in Section 5, theoretically characterizing the additional acceleration attributable specifically to value sharing, also observed in Dueling Q-learning, remains an interesting open direction.
Reviewer_qrV6OpenReview ↗

Post-rebuttal assessment

Thank you for the response and the additional experiments in Appendix G. The rebuttal addresses my two main concerns.

  • Alignment between theory and tabular experiments (W1 & Q1): The authors acknowledge that the original tabular experiments used parameters outside the sufficient condition in Lemma B.2. The additional evaluations at larger residual weights, including β∈{40,50}\beta \in \{40,50\}, and with the prescribed two-timescale schedules strengthen the connection between the analysis and the tabular results. They also provide further evidence for the contraction–variance trade-off.
  • Value sharing versus importance weighting (W2 & Q2): The response makes the attribution clearer: removing the bmin⁡b_{\min} dependence from the leading contraction term comes from the importance-weighted residual correction, while varying r=αV/αAr = \alpha_V/\alpha_A provides empirical evidence that value sharing can further accelerate transient learning. Please carry this distinction into the revised main text.

I continue to view the convergence analysis of coupled value-sharing dynamics under Markovian sampling as the paper’s main contribution. Establishing both asymptotic and finite-sample guarantees is valuable. The deep RL implementation also uses replay buffers, clipping, and regularization beyond the analyzed recursion; the final version should clearly distinguish these implementation choices from the tabular guarantees and streamline the theoretical exposition.

The clarifications and additional experiments support my original assessment. I maintain my rating of 3: Weak acceptance.

AuthorsOpenReview ↗

Acknowledgement of Reviewer Feedback

We thank the reviewer for their positive assessment of our work and for their constructive feedback throughout the discussion. We are glad that our clarifications and additional experiments have addressed their main concerns.

We will incorporate the suggested improvements into the revised manuscript, particularly by clarifying the distinct roles of cross-action value sharing and importance-weighted residual correction, distinguishing the tabular theoretical guarantees from the neural implementation, and streamlining the theoretical exposition.

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

The paper presents V-share, an advantage-based variant that splits Q(s,a)=V(s)+A(s,a)Q(s,a)= V(s) + A(s,a). It keeps the shared update rule of previous methods and adds an importance-weighted advantage update scaled by a parameter β\beta and the behavior policy. For this algorithm the authors prove almost-sure convergence and finite-time bounds under Markovian sampling. Experiments cover a small tabular MDP and DQN-style versions on classic control and MinAtari.

Critical strengths
  • The paper gives convergence guarantees for an advantage-based method under markovian sampling and provides almost-sure convergence and finite-time bounds. The theory also predicts a contraction-noise tradeoff in β\beta, which the tabular experiments confirm, and the decreasing β\beta schedules built on that tradeoff beat any fixed β\beta.
Critical weaknesses
  • The deep RL version is quite different from the algorithm that is presented and its theoretical guarantees. It uses replay buffers with behavior probabilities stored at collection time which results in numerous behavior policy mixed within the replay buffer. These probabilities represent not the correct behavior policy at the current point in time (but are necessary for the theory to hold). Furthermore, policy churn (Schaul et al., 2022) shows the greedy action changes in a sizable fraction of states after every update, so the stored values quickly stop matching the policy that generated the data. Also, epsilon annealing directly breaks Assumption 1 and the clipping in MinAtari needs further analysis especially when ϵ\epsilon gets small.

  • Table 1 compares a single configuration per baseline with the best of six V-share settings per environment. This comparison is unfair, and no single V-share configuration is best on all tasks. Aggregated metrics are needed.

  • The main text (and all its references to the appendix) is not easy to follow. While the algorithmic extension is small (almost a one-liner), the theory gets complicated and large. I think additional simplifications or a good rewrite would help the reader to follow the paper properly.

  • The deep RL experiments cover only small benchmarks with 5 seeds and rather high standard deviation. A standard 57-game Atari benchmark (+ aggregated metrics, Agarwal et al., 2021) would be very helpful for empirical evaluation. MELayer, DQN and Dueling DQN (which should become a baseline more so than DQN, because DQN does not have the value and advantage decomposition like Dueling DQN) are already evaluated on the full Atari suite.

References: Schaul, Tom, et al. "The phenomenon of policy churn." Advances in Neural Information Processing Systems 35 (2022):

Questions for authors
  • Is the speedup from value sharing or from importance weighting?
7 comments
AuthorsOpenReview ↗

Author Response Part 1

We thank the reviewer for their detailed reading of our manuscript and for acknowledging the importance of the problem and the relevance of our theoretical results.

We would first like to clarify that the primary objective of this work is theoretical: to develop an advantage-based value-learning algorithm with provable asymptotic convergence and finite-time guarantees under Markovian sampling, thereby addressing an open gap in the existing literature. Our main contributions lie in establishing the stability and convergence of the proposed coupled value-sharing dynamics, characterizing the contraction–variance tradeoff, and developing a two-timescale analysis that removes the large-β\beta requirement of the single-timescale theory.

The deep RL experiments were included as a complementary investigation of the feasibility of extending the proposed algorithmic ideas to function approximation. They were not intended to establish that V-SHARE universally outperforms existing deep RL algorithms or achieves state-of-the-art performance across benchmarks.

In this regard, we note that a similar distinction exists between classical Q-learning and its practical deep RL counterpart, DQN. While the convergence theory of tabular Q-learning analyzes a relatively simple stochastic recursion, DQN incorporates several additional components, such as experience replay, target networks, and an ϵ\epsilon-greedy behavior policy, to achieve effective learning with neural function approximation. Likewise, our neural implementation introduces practical modifications that are not covered by the tabular analysis. We therefore distinguish the theoretical guarantees established in this work from the empirical feasibility demonstrated by the deep RL experiments.

With this distinction in mind, we address the reviewer's concerns individually below.

W3. Organization, length, and complexity of the theoretical development.

We agree that the theoretical development is extensive. This was a deliberate choice to provide detailed proofs of both the asymptotic and non-asymptotic convergence guarantees for the different variants of the proposed algorithm under Markovian sampling.

In particular, the analysis of the coupled value-sharing dynamics, the finite-time guarantees, and the two-timescale formulation requires different technical arguments that are not immediate consequences of standard Q-learning analyses. Nevertheless, we recognize that the presentation can be made more accessible, particularly by improving the exposition of the main proof ideas and the connections between the different theoretical results.

We will improve the organization and transitions between sections, while retaining the detailed technical arguments in the appendix. We would also appreciate any suggestions from the reviewer regarding specific sections where further simplification would be particularly helpful.

W1. Differences between the theoretical algorithm and the deep RL implementation.

As clarified above, the neural implementation is intended to investigate the feasibility of extending the proposed value-sharing mechanism to function approximation, rather than to directly validate the tabular convergence guarantees. We acknowledge that experience replay, changing behavior policies, clipping, and regularization introduce additional considerations beyond our theoretical setting. In particular, replay with stored behavior probabilities and ϵ\epsilon-annealing do not satisfy the fixed-policy Markovian sampling assumptions of our analysis.

These modifications are motivated by practical considerations, analogous to the additional mechanisms introduced when extending tabular Q-learning to DQN. Clipping controls the magnitude of importance-weighted updates, while regularization addresses the non-identifiability of the value–advantage decomposition. We do not claim that our theoretical guarantees extend directly to the neural implementation, and will clarify this distinction and the limitations associated with policy churn and clipping in the revised manuscript.

We continue our response in the next official comment, Author Response Part 2.

AuthorsOpenReview ↗

Author Response Part 2

W2. Fairness of the hyperparameter comparison and lack of aggregated metrics.

We thank the reviewer for raising this concern. For the baseline algorithms, we adopted the standard hyperparameter configurations reported in the corresponding literature (Huang et al., 2022), rather than performing additional tuning. For V-SHARE, we evaluated multiple configurations to investigate the effect of varying the relative learning rates of the value and advantage components.

As clarified above, our goal was to demonstrate the feasibility of the proposed neural implementation and illustrate the behavior of different V-SHARE variants, rather than to establish state-of-the-art performance or claim that V-SHARE uniformly outperforms the baselines. Table 1 reports the best-performing configurations among those evaluated for each environment, demonstrating that V-SHARE can achieve competitive performance, although the comparison does not involve equal hyperparameter-tuning budgets.

We will further clarify this distinction in the updated manuscript.

W4. Limited benchmark coverage and statistical reliability of the deep RL experiments.

We acknowledge the reviewer's concern regarding the limited benchmark coverage and statistical variability of the current deep RL experiments. As noted above, our primary objective is to establish theoretical convergence guarantees for advantage-based value learning, while the deep RL experiments serve as a complementary empirical investigation.

Nevertheless, we agree that a broader evaluation would help assess the practical relevance of the proposed algorithm. We are currently conducting additional experiments on the full 57-game Atari suite, as suggested by the reviewer, and intend to incorporate these results into the revised manuscript. We shall inform the reviewer within the discussion period when these experiments conclude.

Q1. Is the speedup from value sharing or from importance weighting?

We thank the reviewer for raising this important distinction. The two mechanisms play complementary roles in V-SHARE. In particular, the limiting ODE dynamics decompose as

\underbrace{DB(\mathcal TQ-Q)}_{\text{cross-action value sharing}} + \underbrace{\beta D(\mathcal TQ-Q)}_{\text{importance-weighted residual correction}}.$$ The first term propagates information across actions through the shared value component, whereas the second term removes the dependence on the behavior action probabilities in the diagonal component through importance weighting. From a theoretical perspective, the cross-action coupling introduced by value sharing prevents the standard sup-norm contraction argument used for asynchronous Q-learning. Moreover, the value-sharing component alone does not uniquely identify $Q^\star$: when $\beta=0$, the preconditioner $DB$ is singular, and hence the equilibrium condition $DB(\mathcal TQ-Q)=0$ does not necessarily imply $\mathcal TQ=Q$. Introducing the importance-weighted residual correction makes the preconditioner $D(B+\beta I)$ nonsingular for every $\beta>0$, thereby preserving $Q^\star$ as the unique equilibrium. For sufficiently large $\beta$, it additionally enables us to establish a sup-norm contraction for the combined dynamics. In particular, the removal of the multiplicative rare-action factor $b_{\min}$ from the leading term in our theoretical contraction-gap comparison is attributable to the importance-weighted residual correction. Our theoretical guarantees therefore establish improved contraction properties for the combined value-sharing dynamics, rather than relying on value sharing alone. Moreover, our experiments also partially isolate the empirical contribution of value sharing. In Figure 2(b) of the manuscript, we vary the ratio $r=\alpha_V/\alpha_A$, where $r=0$ corresponds to removing value sharing entirely while retaining the importance-weighted advantage update. Increasing $r$ generally leads to faster transient convergence, with comparable steady-state error floors that are occasionally slightly higher. Thus, these experiments suggest that cross-action value sharing provides additional empirical acceleration beyond that induced by importance weighting alone. Taken together, our results distinguish two complementary effects: the importance-weighted residual correction enables us to establish contraction-based convergence guarantees and helps mitigate the rare-action bottleneck, whereas cross-action value sharing contributes to the additional transient acceleration observed empirically. As acknowledged in Section 5 (Discussion and Future Work), our current theoretical analysis does not fully characterize the acceleration arising specifically from value sharing, a phenomenon also observed in Dueling Q-learning. Establishing sharper problem-dependent convergence or sample-complexity guarantees that capture this effect remains an interesting open direction. We will further clarify this distinction in the revised manuscript.

Thanks for your reply.

  • W1: I understand that the contribution is primarily theoretical. But the paper should say so. The abstract states that the experiments corroborate the results, and the caption of Table 1 still claims a significant improvement over DQN (why even DQN as baseline? Does not make sense here, use Dueling DQN instead). Five seeds, the reported standard deviations, and best-of-six selection against weak/untuned baselines do not support this.

  • W3: My concern is more general than like organization ... As I understand, Sections 3.2 - 3.5 describe five theorems and three algorithm variants in about four pages? Each comes with its own constants (κβ\kappa_\beta, LβL_\beta, c2,βc_{2,\beta}, νβ\nu_\beta, tαLβt_{\alpha L_\beta}, KmixK_{mix}, τt\tau_t, csepc_{sep}) and complex notation. And most are introduced on the fly without intuition. How should one understand this properly? This style is not suitable for humans. Further, the algorithmic change is a single additional term, so the idea itself should be explanable in like a paragraph/section or something. But every substantive argument is linked to a 40-page appendix that we are not required to read. I would suggest concentrating the main text on one setting, with the short proof of Lemma B.2 included, and stating the other variants briefly. In its current form I cannot verify the main claims from the main text alone.

  • W2/W4: Okay, I can take the Atari results into account once posted ... please report ONE fixed V-share configuration across all games, with Dueling DQN, and give aggregate metrics with confidence intervals (Agarwal et al., 2021). This is common practise.

  • Q1: Okay, your answer confirms that the contraction and the rare-action improvement come from the importance-weighted term. The proofs work by making value sharing negligible ... so, I think that the no-value-sharing variant with r=0r=0 should be a main baseline.

Best regards.

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

The paper proposes V-SHARE, an advantage-based algorithm that decomposes the action-value function into state- and action-dependent components, and establishes asymptotic convergence and finite-sample guarantees. V-SHARE combines a shared TD update with an importance-weighted action-specific update. For finite, discounted MDPs under a fixed full-support behavior policy, the paper establishes stability, almost-sure convergence, and finite-time bounds in a contractive parameter regime. The authors also analyze decreasing residual-weight schedules and a two-timescale formulation that removes the single-timescale threshold, clarifying the tradeoff between deterministic contraction and stochastic noise. Empirical results include a tabular MDP, ClassicControl, and MinAtar. The deep RL results are competitive with the advantage-based baselines, but depend strongly on relative learning rates and implementation choices.

Critical strengths
  1. The theory addresses a real difficulty introduced by the coupled updates. Building on VA-learning and Regularized Dueling Q-learning, the paper modifies the coupled update so that stability and finite-time behavior can be analyzed under trajectory sampling, motivating its two-timescale approach. Because cross-action updates couple the value estimates, the coordinate-wise arguments used for standard Q-learning no longer apply directly; the paper addresses this difficulty by establishing boundedness and then deriving almost-sure convergence and finite-time guarantees for the modified update. This extends the understanding provided by VA-learning and Regularized Dueling Q-learning to the studied Markovian setting.

  2. Non-identifiability is handled carefully in the two-timescale analysis. In particular, since the decomposition Q=LV+AQ=LV+A is not unique, requiring convergence to a particular value–advantage pair would impose an unnecessary restriction. The paper uses At−(Q⋆−LVt)=Qt−Q⋆A_t-(Q^\star-LV_t)=Q_t-Q^\star instead to analyze the error relevant to control. The contraction–variance analysis also explains why stronger residual correction can accelerate initial progress while increasing stochastic error, motivating decreasing residual-weight schedules.

Critical weaknesses
  1. Which component drives the acceleration remains unclear. Section 3.33.3 compares deterministic contraction gaps, but increasing β\beta also strengthens the action-specific update and increases importance-weighting noise. Consequently, faster contraction at a fixed raw stepsize does not by itself establish better sample efficiency or identify the contribution of cross-action sharing. The main experiments do not separate these effects. This distinction matters because an improvement driven primarily by action-specific preconditioning would provide limited evidence for the proposed benefits of value sharing.

  2. The sufficient conditions in Theorems 3.13.1 and 3.23.2 differ substantially from the parameter settings used in the experiments, limiting the practical relevance of the guarantees. Under the tabular settings in Section 4.14.1, the minimum behavior probability is 0.8/5=0.160.8/5 = 0.16, so the sufficient contraction condition (κβ>0\kappa_{\beta}>0) in Section 3.23.2 requires β>32.6\beta>32.6. However, Figure 11 evaluates β\beta values between 0.250.25 and 22. Similarly, Theorem 3.4 prescribes diminishing stepsizes with 1/2<p<q≤11/2<p<q\le1, implying αt/τt→0\alpha_t/ \tau_t \to 0. The experiments therefore illustrate useful behavior beyond the sufficient conditions, while leaving their conservatism unresolved.

Questions for authors
  1. Since the principal tabular experiments lie below the sufficient threshold β>32.6\beta>32.6, their success suggests that the condition may be conservative. Could the authors evaluate theorem-valid settings alongside the practical variants, including the prescribed timescale schedules, across independently generated MDPs and different levels of action imbalance? This would establish whether the guarantees describe a useful operating regime and show where practical performance extends beyond the current analysis.

  2. The neural method introduces clipping and regularization beyond the analyzed recursion, while different configurations perform best in different environments. Which modifications are necessary for stability, and how are the hyperparameters optimized?

4 comments
AuthorsOpenReview ↗

Author Response Part 1

We thank the reviewer for their detailed reading of our manuscript and constructive suggestions. We address the stated weaknesses and answer questions below.

W1. Distinguishing the contributions of value sharing and importance weighting.

The main theoretical challenge addressed in our work arises from the cross-action coupling introduced by value sharing. Unlike asynchronous Q-learning, where individual state-action values are updated separately, advantage-based algorithms propagate information across actions through the shared value component. This coupling prevents a direct application of the standard sup-norm contraction argument, making the convergence analysis of such algorithms substantially more challenging.

Our proposed residual preconditioning addresses this difficulty by recovering a provable contraction regime for the combined value-sharing dynamics, thereby enabling asymptotic and finite-time convergence guarantees under Markovian sampling. Thus, our theoretical contribution is the convergence analysis of an advantage-based algorithm that retains cross-action value sharing.

Moreover, Figure 2(b) partially disentangles the empirical contributions of the two mechanisms. Keeping the importance-weighted advantage update fixed, we vary the relative contribution of value sharing through r=αV/αAr=\alpha_V/\alpha_A. We observe that increasing rr generally accelerates transient convergence, with comparable steady-state error floors. These results provide empirical evidence for an additional benefit of value sharing, although they do not establish a general sample-complexity improvement under optimally tuned stepsizes. As discussed in Section 5, obtaining sharper theoretical guarantees that characterize this acceleration, also observed in Dueling Q-learning, remains an interesting direction for future work.

W2. Conservatism and practical relevance of the sufficient conditions.

The original experiments used smaller values of β\beta to illustrate the contraction–variance tradeoff more clearly. Since the contraction condition is sufficient rather than necessary, the favorable behavior observed for smaller values of β\beta suggests that our worst-case analysis may be conservative.

To complement these results, we conduct additional experiments using both practical and theorem-valid values of β\beta, across 1010 independent trajectory seeds and varying levels of action imbalance. We also evaluate polynomially decaying stepsizes satisfying the asymptotic timescale-separation conditions of Theorem 3.4. These results, presented in Appendix section G of the revised manuscript and discussed in our response to Q1, provide a more comprehensive assessment of the theoretical and practical operating regimes of V-SHARE.

We continue our response in the next official comment, Author Response Part 2

AuthorsOpenReview ↗

Author Response Part 2

Q1. Could the authors evaluate theorem-valid settings alongside practical variants, including prescribed timescale schedules, across independently generated MDPs and different levels of action imbalance?

We acknowledge that the contraction condition in Theorem 3.2 is sufficient rather than necessary, and our experimental observations suggest that it can be conservative. We deliberately chose smaller values of β\beta in the original experiments to illustrate the contraction–variance tradeoff more clearly.

We conduct additional experiments across 1010 independent seeds with varying levels of action imbalance. For the single-timescale setting, we vary the exploration parameter ϵ∈0.1,0.4,0.8,1\epsilon\in \\{0.1,0.4,0.8,1\\} and consider both practical values β∈1,5\beta\in\\{1,5\\} and theorem-valid values β∈40,50\beta\in\\{40,50\\}. We observe the same qualitative contraction–variance tradeoff for the larger values satisfying the sufficient contraction condition.

For the two-timescale setting, we additionally evaluate polynomially decaying stepsizes τt=τ0/(t+h)p\tau_t=\tau_0/(t+h)^p and αt=α0/(t+h)q\alpha_t=\alpha_0/(t+h)^q, with (p,q)∈(0.6,0.9),(0.75,1),(0.8,0.95)(p,q)\in\\{(0.6,0.9),(0.75,1),(0.8,0.95)\\} and β∈0.5,2\beta\in\\{0.5,2\\}. These schedules satisfy 1/2<p<q≤11/2<p<q\leq1 and αt/τt→0\alpha_t/\tau_t\to0, as prescribed by Theorem 3.4. The results are presented in Appendix G of the revised manuscript.

Q2. Which modifications are necessary for stability, and how are the hyperparameters optimized?

We thank the reviewer for highlighting this distinction between our theoretical algorithm and its neural implementation. The clipping and regularization mechanisms serve different purposes.

The importance-weighted updates involve factors inversely proportional to the behavior action probabilities, which can become large for infrequently selected actions and introduce substantial variance. We therefore employ clipping to control the magnitude of these updates and improve numerical stability, motivated by similar variance-control techniques used in RL algorithms such as PPO.

The regularization term addresses a separate issue arising from the non-identifiability of the value–advantage decomposition Q=V+AQ=V+A. Without an additional constraint, multiple decompositions can represent the same action-value function. Following the motivation of Daley et al. (2025), we introduce regularization to mitigate this ambiguity and encourage a more stable decomposition. Regularization also helps in stabilizing the neural network weight updates since all of them are updated simultaneously due to the shared network head structure.

We emphasize that these modifications are practical design choices for the neural implementation and are not required by, or covered under, our tabular convergence analysis. Accordingly, we do not claim that the theoretical guarantees extend directly to the neural algorithm.

Regarding hyperparameter selection, we did not perform a dedicated hyperparameter optimization for our method. We used β=1\beta=1 as the default residual-preconditioning parameter and did not optimize it for individual environments. However, to investigate the effect of two-timescale learning, we used different learning rates for the value and advantage networks, as summarized in Table 1. All other hyperparameters and training configurations for the deep RL experiments follow the CleanRL DQN implementation (Huang et al., 2022). We will clarify these implementation details and the distinction between the theoretical and neural algorithms in the revised manuscript.

Thank you for the clarifications and additional experiments. Figure 2(b) does provide meaningful control by varying the value-update rate while keeping the importance-weighted advantage update fixed, so the experiments do separate these mechanisms. The experiments with residual weights and the diminishing step sizes also reduce my concern about the connection between the theory and experiments.

My remaining reservation concerns the strength of the acceleration claim. Increasing the value-update rate changes the total update magnitude alongside cross-action sharing, so whether independently tuning the no-sharing baseline would recover some of the observed gain is unclear. I maintain my score.

AuthorsOpenReview ↗

Acknowledgement of Reviewer Feedback

We thank the reviewer for their follow-up and are glad that our clarifications and additional experiments have addressed several of their concerns.

We appreciate the observation regarding the value-sharing ablation in Figure 2(b). Our experiments demonstrate faster transient convergence when increasing the value-sharing contribution while keeping the advantage update fixed. However, we acknowledge that the extent to which this acceleration is attributable specifically to cross-action value sharing, rather than changes in the effective update magnitude, remains to be fully characterized. In particular, independently tuning the no-sharing baseline could provide further insight into this distinction.

As acknowledged in Section 5, developing finer-grained sample-complexity guarantees that explain the empirically observed acceleration is an important direction for future work. We will clarify the scope of the empirical evidence in the discussion of Figure 2(b) and explicitly highlight comparisons against independently tuned no-sharing alternatives as a direction for future investigation.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the Discussion and Improvements to Our Manuscript

We thank all reviewers for their careful reading of our manuscript and their constructive feedback throughout the discussion period. Their suggestions have helped us substantially strengthen the paper, clarify its contributions, and improve the empirical evaluation.

In particular, the rebuttal and subsequent discussion have led to the following improvements:

  1. Clarification of the theoretical contributions. We have revised the abstract to distinguish more clearly between our theoretical guarantees, established for tabular MDPs under Markovian sampling, and the deep RL experiments which investigate the feasibility and demonstrate competitive empirical performance of V-SHARE under neural function approximation. We will also improve the theoretical exposition by providing additional intuition for the convergence arguments and clarifying the roles of the different algorithmic components.

  2. Additional tabular experiments aligned with the theoretical guarantees. We have expanded our tabular experiments to include settings satisfying the sufficient contraction condition, varying degrees of action imbalance, and polynomial stepsize schedules satisfying the theoretical timescale-separation requirements. These experiments, presented in Appendix G.1, G.2, provide additional evidence supporting our theoretical findings across different parameter regimes.

  3. Expanded deep RL evaluation on Atari. We have conducted additional experiments on 18 Atari games, comparing V-SHARE against Dueling DQN using a fixed V-SHARE configuration across all evaluated games. The results, presented in Appendix G.3, demonstrate competitive performance, with improvements in aggregate IQM and mean human-normalized scores. Due to computational and time constraints during the rebuttal, we have currently reported results on 18 of the 57 games and intend to include the complete suite in the final manuscript.

  4. Aggregate metrics and new empirical insights. Following Reviewer XMsC's suggestion, we have introduced aggregate IQM and mean performance metrics with 95% bootstrap confidence intervals for the Classic Control, MinAtar, and Atari experiments. Beyond strengthening the statistical evaluation, these metrics have provided new insights into the relative performance of different V-SHARE configurations. In particular, while the original per-environment comparisons suggested that the preferred learning-rate configuration was environment-dependent, the aggregate results identify single-timescale V-SHARE (1×1\times) as a competitive default across Classic Control and MinAtar, achieving the highest combined IQM and mean among the evaluated V-SHARE variants, while also exhibiting competitive aggregate performance relative to Soft RDQ.. This has allowed us to strengthen the conclusions of Section 4.2 by identifying a practically useful default configuration, rather than only highlighting environment-dependent performance differences. It also provides a connection to our Atari evaluation, where we employ this same configuration across all evaluated games without environment-specific hyperparameter tuning. We appreciate this suggestion, as it has led to a substantive improvement in the interpretation and presentation of our empirical findings.

We are particularly grateful to the reviewers for their constructive engagement, which has helped us address ambiguities in the presentation, strengthen our empirical comparisons, and draw more informative conclusions from our results. We believe these revisions have substantially improved the clarity, empirical support, and overall quality of the manuscript, and we will incorporate them into the final version.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.