Learning-theoretic agenda reading list

post by Vanessa Kosoy (vanessa-kosoy) · 2023-11-09T17:25:35.046Z · LW · GW · 1 comments

Contents

  General math background
  AI theory
  Agent foundations
  Bonus materials
None
1 comment

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)
  • "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

• "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
  • Linear infra-Bayesian bandits [LW · GW]
  • “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]
  • String machines [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

1 comments

Comments sorted by top scores.