# Scale Invariant Monte Carlo under Linear Function Approximation with Curvature based step-size

arXiv: https://arxiv.org/abs/2104.07361 · HTML: https://mlsanity.com/paper/2104.07361/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 66 references that are in the map.
- First posted on arXiv 15 Apr 2021.

## Builds on (most cited first, 19 of 19)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [Group Normalization](https://mlsanity.com/paper/1803.08494/) (2018)
- [An overview of gradient descent optimization algorithms](https://mlsanity.com/paper/1609.04747/) (2016)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Self-Normalizing Neural Networks](https://mlsanity.com/paper/1706.02515/) (2017)
- [Weight Normalization: A Simple Reparameterization to Accelerate Training of Deep Neural Networks](https://mlsanity.com/paper/1602.07868/) (2016)
- [How Does Batch Normalization Help Optimization?](https://mlsanity.com/paper/1805.11604/) (2018)
- [On the Convergence of A Class of Adam-Type Algorithms for Non-Convex Optimization](https://mlsanity.com/paper/1808.02941/) (2018)
- [Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence](https://mlsanity.com/paper/2002.10542/) (2020)
- [CrossQ: Batch Normalization in Deep Reinforcement Learning for Greater Sample Efficiency and Simplicity](https://mlsanity.com/paper/1902.05605/) (2019)
- [Normalization Techniques in Training DNNs: Methodology, Analysis and Application](https://mlsanity.com/paper/2009.12836/) (2020)
- [Global convergence of the Heavy-ball method for convex optimization](https://mlsanity.com/paper/1412.7457/) (2014)
- [Understanding the Role of Momentum in Stochastic Gradient Methods](https://mlsanity.com/paper/1910.13962/) (2019)
- [Unified Convergence Analysis of Stochastic Momentum Methods for Convex and Non-convex Optimization](https://mlsanity.com/paper/1604.03257/) (2016)
- [Convergence of a Stochastic Gradient Method with Momentum for Non-Smooth Non-Convex Optimization](https://mlsanity.com/paper/2002.05466/) (2020)
- [On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergence](https://mlsanity.com/paper/1411.3224/) (2014)
- [Online Algorithms for Estimating Change Rates of Web Pages](https://mlsanity.com/paper/2009.08142/) (2020)

## Abstract (arXiv)

We study the feature-scaled version of the Monte Carlo algorithm with linear function approximation. This algorithm converges to a scale-invariant solution, which is not unduly affected by states having feature vectors with large norms. The usual versions of the MCMC algorithm, obtained by minimizing the least-squares criterion, do not produce solutions that give equal importance to all states irrespective of feature-vector norm -- a requirement that may be critical in many reinforcement learning contexts. To speed up convergence in our algorithm, we introduce an adaptive step-size based on the curvature of the iterate convergence path -- a novelty that may be useful in more general optimization contexts as well. A key contribution of this paper is to prove convergence, in the presence of adaptive curvature based step-size and heavy-ball momentum. We provide rigorous theoretical guarantees and use simulations to demonstrate the efficacy of our ideas.