While planning in fully certain dynamic environments modeled by differential equations is well-studied, little is known about learning to plan under uncertainty. This work focuses on fast and provably efficient learning algorithms for unknown multi-dimensional stochastic differential equations and comprehensively studies the interplay between learning and planning. We present computationally fast algorithms that learn unknown dynamics by planning according to suitably-randomized parameter estimates. We prove efficiency by showing that the errors of both learning and planning decay as square-root of time and grow linearly with the number of unknown parameters. To obtain the results, novel theoretical analyses are developed for eigenvalues of perturbed matrices, for bounding ratios of stochastic integrals, and for lower-bounding singular values of (partially-) random matrices. The authors expect the framework to be applicable in other relevant problems.