  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.
