As part of the process of resolving issues submitted by users via bug reports, Android developers attempt to reproduce and observe the failures described by the bug report. Due to the low-quality of bug reports and the complexity of modern apps, the reproduction process is non-trivial and time-consuming. Therefore, automatic approaches that can help reproduce Android bug reports are in great need. However, current approaches to help developers automatically reproduce bug reports are only able to handle limited forms of natural language text and struggle to successfully reproduce failures for which the initial bug report had missing or imprecise steps. In this paper, we introduce a new fully automated Android bug report reproduction approach that addresses these limitations. Our approach accomplishes this by leveraging natural language process techniques to more holistically and accurately analyze the natural language in Android bug reports and designing new techniques, based on reinforcement learning, to guide the search for successful reproducing steps. We conducted an empirical evaluation of our approach on 77 real world bug reports. Our approach achieved 67% precision and 77% recall in accurately extracting reproduction steps from bug reports, and reproduced 74% of the bug reports, significantly outperforming state of the art techniques.