Puterman or Sutton Barto?
Sutton and Barto (2nd edition is out!). Also David's Silver slides for the RL course at UCL plus the youtube videos from his classes. You can start with the lecture videos and the slides and going back to the book for more details and exercises. Putterman is quite hard for a beginner, heavy on math and focusing on Dynamic Programming mostly.