Learning-theoretic agenda reading list

Vanessa Kosoy9 Nov 2023 17:25 UTC
LW: 98 AF: 36
1 comment2 min readLW link1 review

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)

    • “Reinforcement Learning in POMDPs Without Resets” (Even-Dar, Kakade, Mansour, 2005)

    • “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

Vanessa Kosoy9 Nov 2023 17:25 UTC
LW: 98 AF: 36
1 comment2 min readLW link1 review
No comments.