  Collision checking is a computational bottleneck in motion planning,
requiring lazy algorithms that explicitly reason about when to perform this
computation. Optimism in the face of collision uncertainty minimizes the number
of checks before finding the shortest path. However, this may take a
prohibitively long time to compute, with no other feasible paths discovered
during this period. For many real-time applications, we instead demand strong
anytime performance, defined as minimizing the cumulative lengths of the
feasible paths yielded over time. We introduce Posterior Sampling for Motion
Planning (PSMP), an anytime lazy motion planning algorithm that leverages
learned posteriors on edge collisions to quickly discover an initial feasible
path and progressively yield shorter paths. PSMP obtains an expected regret
bound of $\tilde{O}(\sqrt{\mathcal{S} \mathcal{A} T})$ and outperforms
comparative baselines on a set of 2D and 7D planning problems.
