Choosing Artificial Intelligence after MS in Theory

As always, it's going to come down to your application and your history. From the sounds of it, you'll be a very strong candidate based on your theory background -- You just need to find the right school / supervisor that will see how to help you pursue those interests. Look for schools with good AI programs. Knowing the research focuses at the CS Department in the University of Alberta, I think you'd have a good shot there with a number of supervisors, both in reinforcement learning and in machine learning. Really though, it's going to come down to a demonstration that you can do the research, via your reference letters, CV, etc.