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

Kintan Saha; Hamed Masoudi; Xinyi Sheng; Dominik Baumann; Joni Pajarinen; Arsenii Mustafin

cs.LGOct 15, 2026

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

Authors: Kintan Saha, Hamed Masoudi, Xinyi Sheng, Dominik Baumann, Joni Pajarinen, Arsenii Mustafin

Organizations: Indian Institute of Science · Aalto University

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 proven 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.

Figures & tables

\delta_{t}=R_{t+1}+\gamma\max_{a^{\prime}}Q_{t}(s_{t+1},a^{\prime})-Q_{t}(s_{t},a_{t}).

Algorithm 1 V-share

Panel of Figure 1 — Figure 1: Tabular experiments on randomly generated MDPs. (a): performance of single-timescale V-share (Algorithm 1 ) for different residual weights $\beta$ under constant stepsizes, compared with asynchronous Q-learning and Dueling Q-learning. (b): comparison of decreasing residual-preconditioning schedules that interpolate from $\beta_{\mathrm{high}}$ to $\beta_{\mathrm{low}}$ . Curves show the mean squared sup-norm error $\mathbb{E}\|Q_{t}-Q^{\star}\|_{\infty}^{2}$ over independent trajectories; shaded regions denote pointwise 95% confidence intervals. The y-axis is in the logarithmic scale in all plots.

Environment	DQN	ME Layer	Soft RDQ	V-share LR Multiplier					V-share $\beta$ -Scheduling
				$0.25\times$	$0.5\times$	$1\times$	$2\times$	$4\times$
Acrobot-v1	$-443.12\pm 101.39$	$-140.40\pm 113.25$	$-85.44\pm 9.30$	$\mathbf{-82.44\pm 11.32}$	$-103.80\pm 39.53$	$-87.24\pm 4.65$	$-169.08\pm 185.00$	$-167.24\pm 186.44$	$-108.72\pm 48.35$
CartPole-v1	$375.08\pm 143.63$	$342.40\pm 195.66$	$423.24\pm 171.64$	$\mathbf{500.00\pm 0.00}$	$\mathbf{500.00\pm 0.00}$	$\mathbf{500.00\pm 0.00}$	$464.00\pm 77.52$	$\mathbf{500.00\pm 0.00}$	$\mathbf{500.00\pm 0.00}$
LunarLander-v2	$218.37\pm 36.83$	$193.98\pm 101.57$	$244.94\pm 25.36$	$\mathbf{248.79\pm 11.53}$	$227.80\pm 51.22$	$202.93\pm 4.76$	$105.49\pm 98.36$	$-24.65\pm 76.29$	$168.55\pm 90.31$
MountainCar-v0	$-166.20\pm 46.36$	$-138.04\pm 16.81$	$\mathbf{-106.24\pm 5.87}$	$-183.36\pm 37.21$	$-136.92\pm 9.06$	$-131.48\pm 22.14$	$-133.60\pm 17.56$	$-141.40\pm 35.89$	$-129.28\pm 4.98$
Asterix-v1	$42.33\pm 14.28$	$41.90\pm 12.77$	$\mathbf{55.97\pm 9.13}$	$49.57\pm 10.05$	$41.47\pm 15.00$	$47.97\pm 20.52$	$35.70\pm 7.52$	$27.03\pm 4.82$	$41.53\pm 11.08$

Table 1: Deep RL results on Classic Control and MinAtar Environments. We compare different configuration of V-share against DQN ( Mnih et al., 2015 ) , ME Layer ( Nagarajan et al., 2026 ) , and Soft RDQ ( Daley et al., 2025 ) across four Classic Control and five MinAtar environments. Results report the mean

\pm

standard deviation over five independent training seeds. The results show that while it is hard to directly apply the theoretical results to the deep RL setting, V-share tends to perform at par with Soft RDQ and significantly outperforms vanilla DQN.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

\delta_{t}=R_{t+1}+\gamma\max_{a^{\prime}}Q_{t}(s_{t+1},a^{\prime})-Q_{t}(s_{t},a_{t}).

Appendix

Algorithm 2 V-share

Panel of Figure 2 — Figure 2: Tabular experiments on randomly generated MDPs. (a): performance of single-timescale V-share (Algorithm 1 ) for different residual weights $\beta$ under inverse linear stepsizes, compared with asynchronous Q-learning and Dueling Q-learning. (b): comparison of two-timescale V-share on with varying stepsize ratios and $\beta$ values using constant stepsizes. Curves show the mean squared sup-norm error $\mathbb{E}\|Q_{t}-Q^{\star}\|_{\infty}^{2}$ over independent trajectories; shaded regions denote pointwise 95% confidence intervals. The y-axis is in the logarithmic scale in all plots.

Figure 3: Learning curves for DQN, ME Layer, Soft RDQ, and V-share across four classic-control environments. We evaluate V-share with different advantage learning-rate multipliers and with decreasing-

\beta

scheduling to study the effects of timescale separation and residual-preconditioning schedules in the deep RL setting. Curves show the mean evaluation return over five independent training seeds, with shaded regions indicating

\pm 1

SEM.

Figure 4: Learning curves for DQN, ME Layer, Soft RDQ, and V-share across five MinAtar environments. We evaluate V-share with different advantage learning-rate multipliers and with decreasing-

\beta

scheduling to study the effects of timescale separation and residual-preconditioning schedules in the deep RL setting. Curves show the mean evaluation return over six independent training seeds, with shaded regions indicating

\pm 1

SEM.

Reinforcement Learning

Reinforcement learning studies how agents learn sequential decisions from rewards and interaction, balancing exploration, performance, safety, and adaptation.

See all 1,742 papers

A Convergence Framework for Deep $V$ -Learning: Error Propagation and Sharp Action-Gap Bounds
Sep 16, 2026Yury KolomeytsevReinforcement Learning Policy Learning
Faculty of Computational Mathematics and Cybernetics Lomonosov Moscow State University
Accelerating Q-learning through Efficient Value-Sharing across Actions
Jun 29, 2026Prabhat Nagarajan, Brett Daley, Martha White +1Deep Q-Learning Value Function Estimation
Department of Computing Science, University of Alberta, Edmonton, AB, Canada. · Alberta Machine Intelligence Institute · Meta (independent work, not on Meta’s behalf). +1
Relative Value Learning
Jul 23, 2026Marc Höftmann, Jan Robine, Stefan HarmelingValue Function Estimation Temporal-Difference Learning
Department of Computer Science, Technical University of Dortmund, Germany · Lamarr Institute for Machine Learning and Artificial Intelligence

Sep 16, 2026J/K move · Enter open · S save

A Convergence Framework for Deep $V$ -Learning: Error Propagation and Sharp Action-Gap Bounds

Yury Kolomeytsev

Faculty of Computational Mathematics and Cybernetics Lomonosov Moscow State University

Reinforcement Learning Policy Learning Model-Based RL

Open paper AskPDF arXiv

We establish convergence bounds for deep

V

-learning with horizon

H

. The algorithm fits a scalar value function to targets from executed transitions and selects actions using a predictive model and the value function. For current observed-successor targets with fresh true-kernel outcomes, the conditional mean is

\mathcal{T}^βV

, which averages over behavior-policy actions. The Bellman optimality update is

\mathcal{T} V

. We decompose the update error into six residuals: fitting, transition reuse, target construction, replay, action selection, and exploration. Under

L^s

concentrability, their

L^p

norms (

p=s/(s-1)

) control expected

L^1

policy loss. The bound explicitly weights residuals from only the last

H-1

update blocks, plus an initialization term for shorter runs. We quantify the cost of a shared sampling distribution across horizon levels. For statistical error bounds of order

n^{-ν}

, we derive optimal continuous allocations and an integer allocation whose objective is within a factor

2^ν

of the constrained optimum. A margin condition with exponent

α

gives action error of order

Λ^{1+α/p}

, where

Λ

combines network drift and score error; a one-step construction proves the exponent sharp. Bounds on the distance between frozen and optimal scores transfer an optimal-gap condition to frozen-iterate gap bounds while retaining the mass of optimal ties. Survival probabilities and coverage conditions at deployment yield bounds for policies selected with approximate scores. Separate spatial ReLU networks per horizon level give a conditional neural regression rate, and the finite-state case gives a log-free expected fit rate. These results give expected policy-loss consistency for the fixed-horizon generative-reset approximate-ERM procedure with exact action scores and provide an explicit residual-decay criterion for FIFO/interleaved SGD.

Abstract

Reinforcement Learning

Explore similar work

A Convergence Framework for Deep VVV-Learning: Error Propagation and Sharp Action-Gap Bounds

Accelerating Q-learning through Efficient Value-Sharing across Actions

Relative Value Learning

A Convergence Framework for Deep $V$ -Learning: Error Propagation and Sharp Action-Gap Bounds