PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2610.21448v1cs.LGcs.AI

TL;DR

V-SHARE addresses the gap in convergence theory for advantage-based value learning under stochastic sampling. It combines value sharing with an importance-weighted residual correction, and the paper provides convergence guarantees while identifying practical principles for its schedules and updates.

  • Problem

    Advantage-based value sharing complicates the standard contraction argument, while existing tabular analyses rely on stronger assumptions such as synchronous updates.

    Source: §1 · p. 2

  • Method

    V-SHARE augments cross-action value sharing with a tunable, importance-weighted Bellman-residual correction and analyzes the algorithm under Markovian sampling.

    Source: §1 · p. 2

  • Results

    The paper establishes almost-sure convergence and finite-time guarantees for V-SHARE under Markovian sampling, and reports a contraction-variance tradeoff with schedules that reduce terminal stochastic error.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The results support stronger advantage updates early and weaker ones later, and a higher effective learning rate for low-advantage actions when they are sampled infrequently.

    Source: §5 · p. 9

    The analysis assumes a fixed behavior policy; extending it to iterate-dependent policies such as ε-greedy exploration remains future work.

    Source: §5 · p. 10

Abstract

from arXiv · show

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.

1 INTRODUCTION

Advantage-based value learning shares a state-value component across actions, but this coupling complicates convergence analysis under stochastic sampling. V-SHARE adds a tunable residual correction to address this gap and is analyzed through asymptotic and finite-time guarantees.

1 INTRODUCTION

  • Value sharing lets an update to the shared state-value component immediately propagate information from one action to the others.The value-advantage decomposition separates a state-dependent value from action-specific advantages.Source: §1 · pp. 1–2
  • Prior tabular analyses of coupled advantage-based methods rely on stronger structural or sampling assumptions, such as synchronous updates, motivating guarantees under stochastic sampling.The section frames the open question as retaining cross-action sharing while obtaining tractable convergence theory and finite-sample guarantees.Source: §1 · p. 2
  • V-SHARE combines cross-action value sharing with a tunable, importance-weighted Bellman-residual correction to recover convergence guarantees.The correction is parameterized by β.Source: §1 · p. 2
  • The paper establishes almost-sure convergence and finite-time guarantees under Markovian sampling, and analyzes schedules and a two-timescale formulation.The two-timescale analysis removes the single-timescale large-β requirement; experiments cover tabular MDPs and deep RL benchmarks.Source: §1 · p. 2
  • This work differs from policy-gradient uses of advantages by explicitly representing action values with a shared state value and action-specific advantages.The related-work discussion situates the approach alongside recent tabular and deep value-advantage methods and RB-S.Source: §1 · p. 2

2 PROBLEM SETUP

The setup considers finite discounted MDPs and learning from a single trajectory under a fixed behavior policy. It contrasts asynchronous Q-learning’s action-specific updates with value sharing, which couples actions at a visited state.

2 PROBLEM SETUP

  • A finite discounted MDP has finite state and action spaces, bounded rewards, and discount factor γ in [0, 1).The objective is a policy maximizing expected cumulative discounted reward.Source: §2 · p. 3
  • The algorithms learn asynchronously from single-trajectory transitions generated by a fixed behavior policy with full support and an irreducible, aperiodic state chain.This ergodicity assumption gives a unique stationary state and state-action distribution.Source: §2 · p. 3
  • Asynchronous Q-learning’s limiting ODE applies a diagonal sampling preconditioner to the Bellman residual, preserving coordinate-wise updates.The stationary mean dynamics are ˙Q = Dµ(T Q − Q).Source: §2 · p. 3
  • Value sharing represents Q as a state value plus action advantages, and its coupling propagates the Bellman-residual update across actions at the visited state.The setup contrasts the usual action-specific update Dµ(T Q − Q) with cross-action propagation through DB(T Q − Q).Source: §2 · pp. 3–4

3 MAIN RESULTS

V-SHARE combines cross-action value sharing with an importance-weighted Bellman-residual correction. Under Markovian sampling, the paper establishes convergence guarantees, studies the contraction–variance tradeoff and decreasing residual-preconditioning schedules, and analyzes a two-timescale approach that removes the single-timescale threshold on β.

3.1 V-SHARE ALGORITHM

  • V-SHARE augments shared value updates with an importance-weighted, action-specific Bellman-residual correction to address the contraction difficulty caused by cross-action coupling.The analysis represents the algorithm as a stochastic approximation for a fixed-point iteration.Source: §3 · p. 4, §3.1 · p. 4

3.2 ASYMPTOTIC GUARANTEES

  • Under Markovian sampling and suitable parameter choices, V-SHARE is almost surely bounded and converges to Q⋆; the paper identifies this as the first such guarantee for an advantage-based algorithm.The result uses a contractive fixed-point map under the stated condition κβ > 0.Source: §3.2 · p. 5

3.3 FINITE-TIME GUARANTEES

  • V-SHARE has finite-time convergence guarantees under Markovian sampling, and for large β its leading deterministic contraction gap avoids asynchronous Q-learning’s rare-action factor.Larger β also strengthens transient contraction while enlarging the constant-stepsize stochastic radius.Source: §3.3 · p. 6

3.4 DECREASING RESIDUAL-PRECONDITIONING SCHEDULES

  • A two-stage schedule uses large β for faster early contraction, then low β so the earlier error is contracted and the terminal stochastic scale is governed by the low-β phase.The paper also derives bounds for smoothly decreasing linear, polynomial, and normalized-exponential schedules.Source: §3.4 · pp. 6–7

3.5 TWO-TIMESCALE V-SHARE

  • Two-timescale learning removes the single-timescale threshold on β: for every fixed β > 0, the fast advantage dynamics reduce to Bellman dynamics with gap dmin(1 − γ).The advantage iterate evolves faster than the shared value component.Source: §3.5 · p. 7
  • The two-timescale analysis also establishes almost-sure convergence and e O(1/t^p) mean-square error rates for all β > 0.The finite-time tracking result treats movement of the value component as a slower perturbation controlled by αt/τt.Source: §3.5 · pp. 7–8

4 EXPERIMENTS

Across tabular MDPs and deep RL benchmarks, V-SHARE performs competitively with the compared methods, while its results depend on residual weighting and relative learning rates. Decreasing β combines rapid early tabular progress with a smaller terminal error.

4.1 DISCRETE MDP

  • Across tabular settings, V-SHARE converges faster than asynchronous Q-learning and Dueling Q-learning, while decreasing-β schedules combine rapid early progress with lower terminal error.With constant stepsizes, higher β accelerates initial decay but eventually increases the error floor.Source: §4.1 · p. 8, Figure 1 · p. 9
  • The tabular experiments use a fixed randomly generated 10-state, 5-action MDP and behavior policy, with trajectories varied across 10 independent seeds.The behavior policy mixes a randomly sampled deterministic policy with uniform action selection using ϵ = 0.8.Source: §4.1 · p. 8

4.2 DEEP RL

  • V-SHARE tends to match Soft RDQ and significantly outperform vanilla DQN across four Classic Control and five MinAtar environments.The best-performing V-SHARE configuration has the highest mean return on six of nine environments.Source: §4.2 · pp. 8–9, Table 1 · p. 9
  • No advantage learning-rate multiplier performs best across all deep RL tasks; smaller multipliers suit several environments, while intermediate settings suit others.Multipliers of 2× and 4× can substantially degrade performance on some tasks.Source: §4.2 · pp. 8–9

5 DISCUSSION AND FUTURE WORK

The discussion presents practical guidance on value and advantage updates, while identifying unresolved theoretical extensions. The appendices provide detailed analyses, technical lemmas, and experimental implementation details.

5 DISCUSSION AND FUTURE WORK

  • The authors’ practical takeaways include separating shared values from action-specific advantages and adjusting β to trade stronger early correction against later noise.They support larger effective advantage learning rates than value learning rates in tabular MDPs, but note that reducing advantage rates may improve deep RL stability by limiting noise.Source: §5 · p. 9
  • Open directions include explaining dueling Q-learning’s empirical acceleration, deriving sharper problem-dependent guarantees, extending analysis to function approximation, and allowing iterate-dependent sampling.The current analysis assumes a fixed behavior policy.Source: §5 · p. 10

OVERVIEW OF THE APPENDIX

  • The appendices detail single- and two-timescale analyses, decreasing-β schedules, technical lemmas, and experimental settings.They include convergence and finite-time analyses, schedule specializations, tracking guarantees, and additional experiments.Source: OVERVIEW OF THE APPENDIX · p. 13

A BACKGROUND DERIVATIONS

The appendix establishes the sampling and update foundations for comparing asynchronous Q-learning with value-sharing dynamics. Its central contrast is diagonal coordinate-wise updating versus cross-action coupling.

A BACKGROUND DERIVATIONS

  • The background appendix derives sample recursions and stationary mean fields, then recalls asynchronous Q-learning’s sup-norm contraction argument.The setup concerns finite discounted MDPs and a Markovian sampling model.Source: A BACKGROUND DERIVATIONS · p. 13, §A.1 · p. 13

A.1 SAMPLING MODEL AND BELLMAN RESIDUAL

  • The sampling model assumes an irreducible, aperiodic state chain with invariant distribution under the behavior policy.The Bellman optimality operator is a γ-contraction with a unique fixed point.Source: §A.1 · p. 13

A.2 ASYNCHRONOUS Q-LEARNING

  • Asynchronous Q-learning updates only the sampled state-action coordinate using its temporal-difference error.Its stationary mean dynamics lead to the coordinate-wise contraction argument.Source: §A.2 · p. 14

A.2.1 SUP-NORM CONTRACTION

  • The sup-norm contraction argument works because the Q-learning preconditioner is diagonal, making each coordinate a convex combination of its prior value and Bellman update.The contraction gap is μ_min(1 − γ).Source: §A.2.1 · p. 14

A.3 VALUE-ADVANTAGE UPDATE AND INDUCED Q-DYNAMICS

  • Value-advantage updates add a shared state-value increment to every action and an additional increment to the sampled action; the decomposition is not identifiable, so analysis tracks Q.A state-dependent shift between value and advantage components can leave Q unchanged.Source: §A.3 · pp. 14–15

A.4 DIAGONAL VERSUS CROSS-ACTION PRECONDITIONING

  • Unlike diagonal Q-learning updates, the shared-value preconditioner couples actions: a residual for one action contributes to every action at that state.This coupling prevents the coordinate-wise convex-combination argument from carrying over.Source: §A.4 · p. 15

B SINGLE-TIMESCALE V-SHARE: DETAILED ANALYSIS

The appendix derives V-SHARE’s single-timescale recursion and stationary mean operator. It shows that residual preconditioning preserves the optimal fixed point and gives a contraction under a stated condition.

B.1 V-SHARE RECURSION AND STATIONARY MEAN OPERATOR

  • V-SHARE updates the state value and action advantages from the sampled Bellman residual, with importance weighting in the advantage update.The induced action-value dynamics retain cross-action sharing while adding a diagonal residual correction βD.Source: §B.1 · p. 16

B.2 FIXED-POINT PRESERVATION AND CONTRACTION

  • For every β > 0, the optimal action-value function Q⋆ is the unique equilibrium of V-SHARE’s mean dynamics.Residual preconditioning preserves the Bellman fixed point.Source: §B.2 · p. 16
  • The V-SHARE fixed-point map is contractive when κβ > 0, with positivity following from a condition involving β, γ, and the behavior-policy action probabilities.The stated condition requires (1 − γ)β − (1 + γ) + 2b(a|s) > 0 for every (s, a).Source: §B.2 · p. 17

B.3 ALMOST-SURE CONVERGENCE UNDER MARKOVIAN SAMPLING

V-SHARE converges almost surely to the optimal action-value function under Markovian behavior-policy sampling and suitable parameter choices. The proof establishes stability through a globally exponentially stable limiting ODE.

B.3 ALMOST-SURE CONVERGENCE UNDER MARKOVIAN SAMPLING

  • The proof applies a Markovian stochastic-approximation framework and verifies its assumptions for the behavior-policy trajectory.The state-action-next-state chain is finite and ergodic when the behavior policy has full support and the state chain is irreducible and aperiodic.Source: §B.3 · pp. 17–19
  • Under Markovian sampling and suitable parameter choices, V-SHARE iterates converge almost surely to Q⋆.The convergence result assumes bounded rewards and κβ > 0.Source: §B.3 · pp. 17, 19
  • The limiting ODE contracts toward Q⋆ at rate κβ in the sup norm.The bound is ∥Q(t) − Q⋆∥∞ ≤ e^−κβt∥Q(0) − Q⋆∥∞.Source: §B.3 · p. 19
  • Unlike asynchronous Q-learning, V-SHARE requires ODE scaling arguments to establish boundedness because sampled TD information updates multiple action-values.The usual induction argument for asynchronous Q-learning does not establish V-SHARE iterate boundedness.Source: §B.3 · p. 20

B.4 FINITE-TIME ANALYSIS UNDER MARKOVIAN SAMPLING

The finite-time analysis treats V-SHARE as a contractive stochastic approximation under Markovian sampling. It controls temporal dependence through chain mixing and derives guarantees for different stepsize schedules.

B.4 FINITE-TIME ANALYSIS UNDER MARKOVIAN SAMPLING

  • The analysis casts V-SHARE as a contractive Markovian stochastic approximation with effective stepsize ϵk = αkLβ.The fixed-point map is a sup-norm contraction for κβ > 0 and 0 < η ≤ Lβ^−1.Source: §B.4 · pp. 20, 22
  • The finite-state, irreducible, aperiodic sampling chain is geometrically mixing, with mixing time tδ = O(log(1/δ)).The analysis specializes the resulting bound to constant and inverse-linear stepsize schedules.Source: §B.4 · pp. 21, 23
  • Because the sampled update is not conditionally unbiased, the analysis controls temporal dependence by allowing the Markov chain to mix over preceding tk iterations.The recursion separates contractive drift from additional error due to temporal dependence.Source: §B.4 · p. 21
  • Theorem B.4 states finite-time guarantees for V-SHARE under Markovian sampling, assuming Assumption 1 and κβ > 0, and sets the stepsize to η = L−1.Equation 22 is identified as the finite-time bound used below.Source: §B.4 · pp. 21–22

B.5 DEPENDENCE ON β AND COMPARISON WITH Q-LEARNING

V-SHARE’s residual-preconditioning parameter β trades stronger deterministic contraction for a larger constant-stepsize stochastic radius, while sufficiently large β improves transient contraction under inverse-linear stepsizes without worsening the leading asymptotic coefficient. Decreasing schedules use strong early contraction while setting the terminal stochastic radius through a lower-β phase.

B.5 DEPENDENCE ON β AND COMPARISON WITH Q-LEARNING

  • Increasing β improves deterministic contraction but increases the constant-stepsize stochastic radius linearly in β, up to the mixing-time factor.This tradeoff motivates decreasing-β schedules.Source: §B.5 · p. 24
  • With inverse-linear stepsizes, sufficiently large residual preconditioning improves transient contraction without worsening the leading β-dependence of the asymptotic coefficient.Source: §B.5 · p. 24
  • For large β, κβ ∼ dmin(1 − γ)β versus asynchronous Q-learning’s μmin(1 − γ), removing the rare-action factor from the leading deterministic contraction gap.Here μmin := mins,a d(s)πb(a|s).Source: §B.5 · p. 24

C DECREASING RESIDUAL-PRECONDITIONING SCHEDULES

  • In the two-stage decreasing schedule, the low-β phase determines the terminal stochastic radius rather than the largest residual weight used during learning.Each fixed-β phase can use its own phase-specific analysis scale.Source: C DECREASING RESIDUAL-PRECONDITIONING… · p. 25

C.1 TWO-STAGE SCHEDULE

The two-stage schedule combines strong early contraction with a terminal stochastic radius set by the low-β phase. General decreasing schedules also have guarantees, but their bound is more conservative; linear, polynomial, and normalized exponential schedules are treated as special cases.

C.1 TWO-STAGE SCHEDULE

  • The two-stage schedule retains contraction from both phases while setting the terminal stochastic radius to the same order as constant-βℓ V-SHARE.High-β phase noise is subsequently attenuated at the low-β contraction rate.Source: §C.1 · pp. 25–26

C.2 GENERAL DECREASING SCHEDULES

  • Any deterministic non-increasing βk in [βℓ, βh] with κβℓ > 0 is covered by a general decreasing-schedule guarantee.The analysis uses a common generalized Moreau envelope based on the worst contraction factor.Source: §C.2 · pp. 26–27
  • The general-schedule bound does not recover the fixed-βℓ terminal radius achieved by the two-stage result.The stated limitation follows from using a single Lyapunov function and common scale for the time-varying schedule, which propagates Lh into the stochastic coefficient.Source: §C.2 · p. 27

C.3 SMOOTHLY DECREASING SCHEDULES

  • Linear, polynomial, and normalized exponential decays are given as specializations of the general decreasing-schedule theorem.The supplied corollaries identify these schedule families, but do not provide complete bound expressions in the passages.Source: §C.2 · p. 27, §C.3 · p. 28

D TWO-TIMESCALE V-SHARE: DETAILED PROOFS

The two-timescale analysis separates advantage and value updates, with the advantage recursion tracking an equilibrium determined by the value iterate. Its tracking error is exactly the Q-error, allowing a vanishing-perturbation Markovian stochastic-approximation argument to establish convergence without requiring the slow value iterate to converge to a unique equilibrium.

D.1 STOCHASTIC-APPROXIMATION FORM AND FROZEN FAST DYNAMICS

  • The two-timescale updates evolve the advantage branch on the fast timescale and the value branch on the slow timescale.For a frozen value vector V, the fast advantage dynamics have equilibrium Q⋆ − LV.Source: §D.1 · pp. 29–30
  • For every fixed V, the frozen fast advantage ODE has the unique globally exponentially stable equilibrium Q⋆ − LV.The corresponding frozen Q-dynamics have Q⋆ as their unique globally exponentially stable equilibrium.Source: §D.1 · p. 30

D.2 ALMOST-SURE TRACKING UNDER TIMESCALE SEPARATION

  • The fast tracking error equals the Q-error, so the analysis rewrites it as a single-timescale Markovian stochastic approximation with a vanishing perturbation.The reduced slow drift vanishes identically because LV + λ(V) = Q⋆, leaving every V as an equilibrium of the reduced slow ODE.Source: §D.2 · p. 31

D.2.1 MARKOVIAN STOCHASTIC APPROXIMATION WITH VANISHING PERTURBATIONS

  • Under the stated assumptions, a Markovian stochastic approximation with vanishing drift perturbation is almost surely stable.Its asymptotic limit set is almost surely bounded and invariant for the unperturbed limiting ODE; if that ODE has a unique globally asymptotically stable equilibrium, the iterates converge to it.Source: §D.2.1 · p. 31

D.2.2 SPECIALIZATION TO TWO-TIMESCALE V-SHARE

This section analyzes two-timescale V-SHARE convergence and tracking, establishing almost-sure convergence for every fixed β and finite-time tracking guarantees under stepsize-ratio and mixing-window conditions. It also develops supporting results on Markovian stochastic approximation and Moreau-envelope properties, and reports an empirical separation between terminal noise and transient speed.

D.2.2 SPECIALIZATION TO TWO-TIMESCALE V-SHARE

  • Theorem D.2 establishes almost-sure convergence of two-timescale V-SHARE when Assumption 1 holds and, for any fixed β > 0, τt := βηt.Source: §D.2.2 · p. 37
  • The two-timescale theorem requires no residual-preconditioning threshold on β, and guarantees convergence of Qt = LVt + At, not of Vt or At separately.The shared-value dynamics act as a vanishing perturbation to the dominant fast dynamics.Source: §D.2.2 · p. 38

D.3 FINITE-TIME MARKOVIAN STOCHASTIC APPROXIMATION WITH A SMALL PERTURBATION

  • A sufficiently small state-dependent Markovian perturbation preserves the finite-time order of the contractive Markovian-SA bound, changing only its constants.The perturbation must be uniformly small enough to be absorbed into the dominant negative drift.Source: §D.3 · pp. 39, 44
  • The perturbation adds a stationary drift term controlled by its uniform smallness and a centered Markovian term contributing a mixing-window error of the original noise order.The centered term is of order ak ak−tk,k−1.Source: §D.3 · p. 44

D.4 FINITE-TIME TRACKING UNDER TIMESCALE SEPARATION

  • The next subsection begins applying Theorem D.3 to the two-timescale V-SHARE recursion and introduces its tracking error.Source: §D.4 · p. 44
  • Under timescale-separation and Markovian mixing-window conditions, two-timescale V-SHARE satisfies the finite-time tracking bound for every t ≥ K.The slow update enters through the ratio r_t = α_t/τ_t; when small enough to be absorbed into the fast drift, it changes the bound’s constants without creating a moving-target error. The slow update consumes at most one quarter of the dominant negative Moreau drift.Source: §D.4 · pp. 46–47

E USEFUL TECHNICAL LEMMAS

  • The generalized Moreau envelope is convex and L/θ-smooth, with an ℓ∞ specialization using ∥·∥s = ∥·∥p for p = 2 log d.For this specialization, the stated constants include L = p − 1 ≤ 2 log d, ℓ_cs = e^−1/2, and u_cs = 1.Source: E USEFUL TECHNICAL LEMMAS · pp. 47–48

F.1 DISCRETE MDP

  • In discrete-MDP experiments, β largely determines the terminal noise floor, whereas the timescale ratio r primarily controls how quickly V-SHARE approaches it.The passage presents this separation as an empirical observation and a possible two-timescale design principle, while identifying its formalization into sharper sample-complexity guarantees as future work.Source: §F.1 · p. 48

F.2 DEEP RL EXPERIMENTS

The deep-RL experiments compare V-SHARE learning curves with DQN, ME Layer, and Soft RDQ across Classic Control and MinAtar, varying advantage learning rates and β scheduling.

F.2 DEEP RL EXPERIMENTS

  • V-SHARE uses separate value and advantage networks, whose outputs are combined as Q(s, a) = V(s) + A(s, a).Separate networks allow their learning rates to vary independently.Source: §F.2 · pp. 48, 50
  • The experiments vary the advantage learning-rate multiplier and decrease β from 100 to 1 during the first 10% of Classic Control training; MinAtar clips inverse behavior probabilities.For Classic Control, the residual-preconditioning weight is the inverse behavior probability; β then remains at 1.Source: §F.2 · pp. 49–50
  • The TD loss updates the value network, while the advantage network is updated separately through its preconditioned advantage objective and regularization.Gradients from the TD objective are stopped with respect to advantage-network parameters.Source: §F.2 · p. 50
  • Learning curves compare DQN, ME Layer, Soft RDQ, and V-SHARE across four Classic Control and five MinAtar environments, with V-SHARE learning-rate and β-scheduling variants.Classic Control curves average five independent training seeds; MinAtar curves average six, with shaded regions showing ±1 SEM.Source: Figure 3 · p. 51, Figure 4 · p. 52

Related papers

Loading 2610.21448v1…