Recently, I'm receiving more and more requests for a self-study reading list for people interested in the learning-theoretic agenda. I created a standard list for that, but before now I limited myself to sending it to individual people in private, out of some sense of perfectionism: many of the entries on the list might not be the best sources for the topics and I haven't read all of them cover to cover myself. But, at this point it seems like it's better to publish a flawed list than wait for perfection that will never come. Also, commenters are encouraged to recommend alternative sources that they consider better, if they know any. So, without further adieu:
General math background
Theoretical computer science
"Computational Complexity: A Conceptual Perspective" by Goldreich (especially chapters 1, 2, 5, 10)
“Lambda-Calculus and Combinators: An Introduction” by Hindley
“Tree Automata Techniques and Applications” by Comon et al (mostly chapter 1)
"Introductory Functional Analysis with Applications" by Kreyszig (especially chapters 1, 2, 3, 4)
"Probability: Theory and Examples" by Durret (especially chapters 4, 5, 6)
"Elements of Information Theory" by Cover and Thomas (especially chapter 2)
“Game Theory, Alive” by Karlin and Peres
“Categories for the Working Mathematician” by Mac Lane (especially parts I, III, IV and VI)
AI theory
“Handbook of Markov Decision Processes” edited by Feinberg and Shwartz (especially chapters 1-3)
“Aritifical Intelligence: A Modern Approach” by Russel and Norvig (especially chapter 17)
"Machine Learning: From Theory to Algorithms" by Shalev-Shwarz and Ben-David (especially part I and chapter 21)
"An Introduction to Computational Learning Theory" by Kearns and Vazirani (especially chapter 8)
"Bandit Algorithms" by Lattimore and Szepesvari (especially parts II, III, V, VIII)
Alternative/complementary: "Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems" by Bubeck and Cesa-Bianchi (especially sections 1, 2, 5)
“Prediction, Learning and Games” by Cesa-Bianchi and Lugosi (mostly chapter 7)
"Universal Artificial Intelligence" by Hutter
Alternative: "A Theory of Universal Artificial Intelligence based on Algorithmic Complexity” (Hutter 2000)
Bonus: “Nonparametric General Reinforcement Learning” by Jan Leike
Reinforcement learning theory
Video and slides: "Introduction to Reinforcement Learning Theory"
"Near-optimal Regret Bounds for Reinforcement Learning" (Jaksch, Ortner and Auer, 2010)
"Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning" (Fruit et al, 2018)
"Regret Bounds for Learning State Representations in Reinforcement Learning" (Ortner et al, 2019)
“Efficient PAC Reinforcement Learning in Regular Decision Processes” (Ronca and De Giacomo, 2022)
“Tight Guarantees for Interactive Decision Making with the Decision-Estimation Coefficient” (Foster, Golowich and Han, 2023)
Agent foundations
"Functional Decision Theory" (Yudkowsky and Soares 2017)
Recently, I'm receiving more and more requests for a self-study reading list for people interested in the learning-theoretic agenda. I created a standard list for that, but before now I limited myself to sending it to individual people in private, out of some sense of perfectionism: many of the entries on the list might not be the best sources for the topics and I haven't read all of them cover to cover myself. But, at this point it seems like it's better to publish a flawed list than wait for perfection that will never come. Also, commenters are encouraged to recommend alternative sources that they consider better, if they know any. So, without further adieu:
General math background
AI theory
Agent foundations
Bonus materials