Incidentally, I liked Barto and Sutton's book, but it feels a bit dated. Does anyone have another reinforcement learning book to recommend?
Also Csaba Szepesvári (a colleague of Rich's at the U of A) has a free RL book you can download. http://www.ualberta.ca/~szepesva/RLBook.html
A related book is "Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems" which you can find at http://www.princeton.edu/~sbubeck/index.html
The bandit problem is very strongly related to the reinforcement learning problem, so you'll get some mileage out of studying bandits. Be aware this area is very maths heavy, which is good or bad depending on your background. If you like you like this stuff, also checkout "Prediction, Learning, and Games" which deals more with the "adversarial" setup.
Apparently Sutton was going to do a second book, but has since retreated to a second edition. I'll take it though. :)
The Barto and Sutton book is available online too, http://webdocs.cs.ualberta.ca/~sutton/book/the-book.html although the printed copy is a high-quality publication so maybe worth it.
Check out Wiering + van Otterlo's "Reinforcement Learning: State-of-the-art." Covers many new techniques--I used it as a reference for a project earlier this year:
http://www.springer.com/engineering/computational+intelligen...