We consider almost sure convergence rates of averaged linear stochastic approximation algorithms, when applied to data with triangular dependence structure and heavy tails. We find that when the data is replaced by its running average in the algorithm, convergence may be faster. We then obtain rates of convergence of price estimates in the context of American option pricing via a dynamic programming algorithm with stochastic approximation. From a methodological point of view, our results show that using averaged data in the pricing algorithm leads to speeds of convergence that are more robust to the choice of parameters.