Link to original article

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.