Many machine learning and optimization algorithms are built upon the framework of stochastic approximation (SA), for which the selection of step-size (or learning rate) $\{α_n\}$ is crucial for success. An essential condition for convergence is the assumption that $\sum_n α_n = \infty$. Moreover, in all theory to date it is assumed that $\sum_n α_n^2 < \infty$ (the sequence is square summable). In this paper it is shown for the first time that this assumption is not required for convergence and finer results. The main results are restricted to the special case $α_n = α_0 n^{-ρ}$ with $ρ\in (0,1)$. The theory allows for parameter dependent Markovian noise as found in many applications of interest to the machine learning and optimization research communities. Rates of convergence are obtained for the standard algorithm, and for estimates obtained via the averaging technique of Polyak and Ruppert. $\bullet$ Parameter estimates converge with probability one, and in $L_p$ for any $p\ge 1$. Moreover, the rate of convergence of the the mean-squared error (MSE) is $O(α_n)$, which is improved to $O(\max\{ α_n^2,1/n \})$ with averaging. Finer results are obtained for linear SA: $\bullet$ The covariance of the estimates is optimal in the sense of prior work of Polyak and Ruppert. $\bullet$ Conditions are identified under which the bias decays faster than $O(1/n)$. When these conditions are violated, the bias at iteration $n$ is approximately $β_θα_n$ for a vector $β_θ$ identified in the paper. Results from numerical experiments illustrate that $β_θ$ may be large due to a combination of multiplicative noise and Markovian memory.