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

Bonus materials

  • “Logical Induction” (Garrabrant et al, 2016)
  • “Forecasting Using Incomplete Models” (Kosoy 2017)
  • “Cartesian Frames” (Garrabrant, Herrman and Lopez-Wild, 2021)
  • “Optimal Polynomial-Time Estimators” (Kosoy and Appel, 2016)
  • “Algebraic Geometry and Statistical Learning Theory” by Watanabe
New Comment