Learning-theoretic agenda reading list
post by Vanessa Kosoy (vanessa-kosoy) · 2023-11-09T17:25:35.046Z · LW · GW · 0 commentsContents
General math background AI theory Agent foundations Bonus materials None No comments
Recently, I'm receiving more and more requests for a self-study reading list for people interested in the learning-theoretic agenda [AF · GW]. 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)
- "Embedded Agency" (Demski and Garrabrant 2019)
- Learning-theoretic AI alignment research agenda
- Overview [AF · GW]
- Infra-Bayesianism sequence [? · GW]
- Bonus: podcast
- “Online Learning in Unknown Markov Games” (Tian et al, 2020)
- Infra-Bayesian physicalism [LW · GW]
- Bonus: podcast
- Video [LW(p) · GW(p)]: "Towards a Theory of Metacognitive Agents"
- Reinforcement learning with imperceptible rewards [LW · GW]
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
0 comments
Comments sorted by top scores.