sample efficiency
In plain wordsHow much practice an AI needs to learn something — an agent that learns a game in a hundred tries is far more sample-efficient than one that needs millions.
The amount of data or experience a learning algorithm needs to reach a given level of performance — in reinforcement learningreinforcement learning, n.: A way of teaching a computer program by trial and error: it tries actions, earns points for good results and penalties for bad ones, and gradually learns which choices pay off over time., usually counted in environment interactions (steps, frames or episodesepisode, n.: One complete run of a task from start to finish — a single game of chess, one attempt at a maze — after which everything resets and the agent tries again.) rather than in gradient updates or compute. It matters most where experience is slow, costly or risky to collect: real robots, user-facing systems, medicine. Deep RL is notoriously inefficient: the 2015 deep Q-networkdeep Q-network, n.: A method, made famous by DeepMind in 2013–2015, in which a neural network learned to play dozens of Atari video games from screen pixels and the score alone, many at human level. trained on roughly 38 days of game experience for each Atari game, where people grasp the basics in minutes. Methods gain efficiency by reusing data (off-policyoff-policy, adj.: Describes learning that can use experience produced by some other strategy — an older version, a human, a different program — while improving the current one. learning, experience replayexperience replay, n.: Storing an AI agent's past experiences in a memory bank and repeatedly learning from random samples of them, rather than only from what just happened.), learning and exploiting models (model-based reinforcement learningmodel-based reinforcement learning, n.: Learning in which an AI agent builds, or is given, an inner simulation of how its world responds, and uses it to plan or practice in imagination before acting.), drawing on prior knowledge (pretraining, demonstrations, transfer learningtransfer learning, n.: Reusing what a model learned on one task to get a head start on another — like a pianist picking up the organ faster than a beginner. It lets models learn new jobs from little data.) and exploring more intelligently. Benchmarks such as Atari 100k, which allows about two hours of game time, measure it directly. In learning theory, sample complexity is the number of examples needed to guarantee a given accuracy with high probability.
The model-based method is ten times more sample-efficient, but each update costs far more compute.
Origin
'Sample complexity' comes from computational learning theory, formalized with Leslie Valiant's PAC framework (1984); Sham Kakade's 2003 thesis analyzed the sample complexity of reinforcement learning. 'Sample efficiency' became everyday deep RL vocabulary in the mid-2010s, as the data hunger of methods such as DQN became a central criticism.
Related
- model-based reinforcement learningmodel-based reinforcement learning, n.: Learning in which an AI agent builds, or is given, an inner simulation of how its world responds, and uses it to plan or practice in imagination before acting.
- experience replayexperience replay, n.: Storing an AI agent's past experiences in a memory bank and repeatedly learning from random samples of them, rather than only from what just happened.
- off-policyoff-policy, adj.: Describes learning that can use experience produced by some other strategy — an older version, a human, a different program — while improving the current one.
- Arcade Learning EnvironmentArcade Learning Environment, prop. n.: A software platform that lets AI programs play classic Atari 2600 video games, used since 2012 as a standard test of how well one AI can learn many different tasks from screen images.
- PAC learningPAC learning, n.: A mathematical definition of what it means to learn from examples: given enough data, a learner should, with high probability, find a rule that is almost always right.
- transfer learningtransfer learning, n.: Reusing what a model learned on one task to get a head start on another — like a pianist picking up the organ faster than a beginner. It lets models learn new jobs from little data.
Mentioned in
experience replayexperience replay, n.: Storing an AI agent's past experiences in a memory bank and repeatedly learning from random samples of them, rather than only from what just happened., model-based reinforcement learningmodel-based reinforcement learning, n.: Learning in which an AI agent builds, or is given, an inner simulation of how its world responds, and uses it to plan or practice in imagination before acting., model-free reinforcement learningmodel-free reinforcement learning, n.: Learning to act well purely from trial and error, without ever building an internal picture of how the world works — like learning a game by habit rather than by thinking moves ahead.