Learning Safe Action Models
summary
Proposes polynomial-time algorithms that output conservative precondition intersection (start with all literals, remove those violated) and learn effects by observed-switch union (add literals that turn on), giving a formal safety guarantee: any plan the planner finds executes in the real STRIPS model and predicted post-states are correct. Gives PAC-style completeness: with probability 1−δ the model is ε-adequate over new problems after O((|A||F|)/ε + log(1/δ)) trajectories, requires injective bindings, and shows conditional effects of size k incur sample complexity exponential in k.
AI-written summary · about
chapters (15)
- 0:00Intro
- 3:00STRIPS action models
- 4:40STRIPS problems
- 10:38A cousin: Offline Reinforcement Learning
- 12:46Key Assumption: Stationary Distribution
- 17:58Remark: action model = nondeterministic alg.
- 21:24Learning Safe Models
- 30:26Proof Outline: Counting Action Models
- 31:49Lifted Action Model Learning: Assumptions
- 32:43Lifted Action Model Learning: Algorithm
- 34:57Preconditions: positive-only learning
- 38:27Effects: VC-dimension/approx. interpolation
- 44:39Optimal algorithm for conditional effects
- 45:55Overview of algorithm
- 48:28Analysis of sample complexity
related talks
17mProgrammatic Strategy Synthesis: Resolving Nondeterminism in Probabilistic Progr...
41mTheory of Modern AI: Learning Theoretic, Game Theoretic, and Algorithmic Perspectives
52mLearning as a Tool for Algorithm Design and Beyond-Worst-Case Analysis
12mLanguage-Model Probabilistic Programming for Improving Autoformalization via Cycle(…)
26mPiecewise Analysis of Probabilistic Programs via k-Induction
22mStochastic Lazy Knowledge Compilation for Inference in Discrete Probabilistic Programs
43mModel Checking and Strategy Synthesis for Stochastic Games: From Theory to Practice
11mLinear Predictors in Reinforcement Learning: ...