Suggested reading for Reinforcement Learning: 

** General Stuff:

Reinforcement Learning , 
Richard S. Sutton and Andrew G. Barto. 
MIT Press, 1998. 

Reinforcement Learning: A Survey, 
L.P. Kaebling, M.L. Littman, and A.W. Moore, 
Journal of Artificial Intelligence Research, 4:237--285, 1996. 


** Papers on  MDPs: 

On the Complexity of Solving Markov Decision Processes , 
M. Littman, T. Dean, L. Kaelbling. 

On the significance of Markov Decision Processes
R.S. Sutton, 


** COLT-like theoretical results for learning in MDPs:


Finite-Sample Rates of Convergence for Q-Learning and Indirect Methods , 
M. Kearns and S. Singh. 
NIPS 11, 1999.   

Near-Optimal Reinforcement Learning in Polynomial Time, 
M. Kearns and S. Singh. 
15th ICML, 260--268, 1998. 


Efficient Reinforcement Learning in Factored MDPs,
M. Kearns and D. Koller, 
IJCAI'99, to appear. 


** Applications: 

Temporal Difference Learning and TD-Gammoon,
G.J. Tesauro, 
Communications of the ACM, 38:58--68, 1995. 

Improving elevator performance using reinforcement learning,
NIPS 8, 1017--1023, 1996. 

High performance job-shop scheduling with a time-delay td(lambda) network.
W. Zhang and T.G. Dietterich. 
NIPS 8, 1024--1030, 1006.