The Nonlinear Library AF - Learning-theoretic agenda reading list by Vanessa Kosoy
Nov 9, 2023
03:35
Welcome to The Nonlinear Library, where we use Text-to-Speech software to convert the best writing from the Rationalist and EA communities into audio. This is: Learning-theoretic agenda reading list, published by Vanessa Kosoy on November 9, 2023 on The AI Alignment Forum.
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.
General math background
"Introductory Functional Analysis with Applications" by Kreyszig (especially chapters 1, 2, 3, 4)
"Computational Complexity: A Conceptual Perspective" by Goldreich (especially chapters 1, 2, 5, 10)
"Probability: Theory and Examples" by Durret (especially chapters 4, 5, 6)
"Elements of Information Theory" by Cover and Thomas (especially chapter 2)
"Lambda-Calculus and Combinators: An Introduction" by Hindley
"Game Theory: An Introduction" by Tadelis
AI theory
"Machine Learning: From Theory to Algorithms" by Shalev-Shwarz and Ben-David (especially part I and chapter 21)
"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
"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
Infra-Bayesianism sequence
Bonus:
podcast
"Online Learning in Unknown Markov Games" (Tian et al, 2020)
Infra-Bayesian physicalism
Bonus:
podcast
Reinforcement learning with imperceptible rewards
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
Thanks for listening. To help us out with The Nonlinear Library or to learn more, please visit nonlinear.org.
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.
General math background
"Introductory Functional Analysis with Applications" by Kreyszig (especially chapters 1, 2, 3, 4)
"Computational Complexity: A Conceptual Perspective" by Goldreich (especially chapters 1, 2, 5, 10)
"Probability: Theory and Examples" by Durret (especially chapters 4, 5, 6)
"Elements of Information Theory" by Cover and Thomas (especially chapter 2)
"Lambda-Calculus and Combinators: An Introduction" by Hindley
"Game Theory: An Introduction" by Tadelis
AI theory
"Machine Learning: From Theory to Algorithms" by Shalev-Shwarz and Ben-David (especially part I and chapter 21)
"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
"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
Infra-Bayesianism sequence
Bonus:
podcast
"Online Learning in Unknown Markov Games" (Tian et al, 2020)
Infra-Bayesian physicalism
Bonus:
podcast
Reinforcement learning with imperceptible rewards
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
Thanks for listening. To help us out with The Nonlinear Library or to learn more, please visit nonlinear.org.