Scale Invariant Monte Carlo under Linear Function Approximation with Curvature based step-size
This addresses a critical problem in reinforcement learning where equal importance across states is needed, offering an incremental improvement with adaptive optimization techniques.
The paper tackles the issue of Monte Carlo algorithms with linear function approximation being biased by states with large feature norms, proposing a scale-invariant version that converges to a solution unaffected by such scaling. It introduces an adaptive step-size based on curvature to speed up convergence and provides theoretical proofs and simulations showing efficacy.
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.