Advantage based reinforcement learning algorithm shows provable convergence
V-SHARE: Provable Convergence Guarantees for Advantage-based Algorithms
Machine LearningArtificial Intelligence
Summary
Reinforcement learning is a way computers learn to make good decisions by trying things and learning from the results. Some methods learn values for actions separately, while others share information across actions, which helps learning. The authors present V-SHARE, a new algorithm that improves understanding of how these shared-value methods work by proving they reliably learn the correct values over time. Their work also identifies tradeoffs in the learning process and suggests ways to balance faster learning and less noise. They tested their ideas on both simple and complex tasks to confirm their findings.
What this means in practice
- •For autonomous vehicle engineers: Improve safety-critical decision-making algorithms with reliable value-sharing reinforcement learning methods that converge with theoretical guarantees under real-world uncertainties.
- •For video game ai developers: Enhance non-player characters' learning efficiency by deploying advantage-based value updates that share information across possible actions reliably.
Authors
Kintan Saha, Hamed Masoudi, Xinyi Sheng, Dominik Baumann, Joni Pajarinen, Arsenii Mustafin
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.