PowerPlay: Training an Increasingly General Problem Solver by Continually Searching for the Simplest Still Unsolvable Problem

By J. Urgen Schmidhuber. 2011

161 citations recorded by the source corpus.

Most of computer science focuses on automatically solving given computational problems. I focus on automatically inventing or discovering problems in a way inspired by the playful behavior of animals and humans, to train a more and more general problem solver from scratch in an unsupervised fashion. Consider the infinite set of all computable descriptions of tasks with possibly computable solutions. Given a general problem-solving architecture, at any given time, the novel algorithmic framework PowerPlay (Schmidhuber, 2011) searches the space of possible pairs of new tasks and modifications of the current problem solver, until it finds a more powerful problem solver that provably solves all previously learned tasks plus the new one, while the unmodified predecessor does not. Newly invented tasks may require to achieve a wow-effect by making previously learned skills more efficient such that they require less time and space. New skills may (partially) re-use previously learned skills. The greedy search of typical PowerPlay variants uses time-optimal program search to order candidate pairs of tasks and solver modifications by their conditional computational (time and space) complexity, given the stored experience so far. The new task and its corresponding task-solving skill are those first found and validated. This biases the search toward pairs that can be described compactly and validated quickly. The computational costs of validating new tasks need not grow with task repertoire size. Standard problem solver architectures of personal computers or neural networks tend to generalize by solving numerous tasks outside the self-invented training set; PowerPlay’s ongoing search for novelty keeps breaking the generalization abilities of its present solver. This is related to Gödel’s sequence of increasingly powerful formal theories based on adding formerly unprovable statements to the axioms without affecting previously provable theorems. The continually increasing repertoire of problem-solving procedures can be exploited by a parallel search for solutions to additional externally posed tasks. PowerPlay may be viewed as a greedy but practical implementation of basic principles of creativity (Schmidhuber, 2006a, 2010). A first experimental analysis can be found in separate papers (Srivastava et al., 2012a,b, 2013).

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Meta & Continual Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Meta & Continual Learning

Citations in the corpus

Recurrent World Models Facilitate Policy Evolution (2018, methodology): “M approach collapses C and M into a single network, and uses PowerPlay-like [82, 91] behavioural replay (where the behaviour of a teacher net is compressed into a student net [79]) to avoid forgetting old prediction and control skills when learning new ones.”
Deep learning in neural networks: An overview (2014, methodology): “1991: UL-based history compression through a deep stack of RNNs Aworking Very Deep Learner (Section 3) of 1991 (Schmidhuber, 1992b, 2013a) could perform credit assignment across hundreds of nonlinear operators or neural layers, by using unsupervised pretraining for a hierarchy of RNNs.”
Solving Rubik's Cube with a Robot Hand (2019, methodology): “In similar spirit to our ADR, related works include PowerPlay [97, 103], POET [117] and different varieties of self-play [101, 102, 76].”
World Models (2018, methodology): “M approach collapses C and M into a single network, and uses PowerPlay-like (Schmidhuber, 2013; Srivastava et al., 2012) behavioural replay (where the behaviour of a teacher net is compressed into a student net (Schmidhuber, 1992)) to avoid forgetting old prediction and control skills when learning ”
CoMPS: Continual Meta Policy Search (2021, methodology): “Other recent methods support continual learning without ground truth task boundaries (Schmidhuber, 2011; Srivastava et al., 2012; Nguyen et al., 2017), but have not yet been demonstrated to perform well in reinforcement learning settings.”
Towards Continual Reinforcement Learning: A Review and Perspectives (2020, methodology): “For example, the PowerPlay framework (Schmidhuber, 2013) is a methodology for deciding on the optimal task to solve next in a lifelong learning setting.”
Continual Learning with Adaptive Weights (CLAW) (2019, methodology): “…memory-based approach relies on episodic memory to store data (or pseudo-data) from previous tasks (Ratcliff, 1990; Robins, 1993; 1995; Thrun, 1996; Schmidhuber, 2013; Hattori, 2014; Mocanu et al., 2016; Rebuffi et al., 2017; Kamra et al., 2017; Shin et al., 2017; Rolnick et al., 2018; van de Ven…”
Functional Regularisation for Continual Learning using Gaussian Processes (2019, background): “, 2017), although work on the problem dates back far longer than this (e.g. Ring, 1994; Robins, 1995; Schmidhuber, 2013; Goodfellow et al., 2013).”
Learning to Learn without Forgetting By Maximizing Transfer and Minimizing Interference (2018, methodology): “Another relevant work is the POWERPLAY framework (Schmidhuber, 2004; 2013) which is a method for asymptotically optimal curriculum learning that by definition cannot forget previously learned skills.”
Hindsight Experience Replay (2017, background): “Another interesting approach is PowerPlay (Schmidhuber, 2013; Srivastava et al., 2013) which is a general framework for automatic task selection.”
Multi-task Deep Reinforcement Learning with PopArt (2018, background): “Being able to acquire knowledge about a wide range of facts and skills has been long considered an essential feature for an RL agent to demonstrate flexible intelligent behaviour (Sutton et al. 2011; Degris and Modayil 2012; Legg and Hutter 2007; Schmidhuber 2013).”
First Experiments with PowerPlay (2012, methodology): “R. Steunebrink and Jurgen Schmidhuber¨ The Swiss AI Lab IDSIA, Galleria 2, 6928 Manno-Lugano University of Lugano & SUPSI, Switzerland 2012 Abstract Like a scientist or a playing child, POWERPLAY [24] not only learns new skills to solve given problems, but also invents new interesting problems b”
On Learning to Think: Algorithmic Information Theory for Novel Combinations of Reinforcement Learning Controllers and Recurrent Neural World Models (2015, methodology): “And POWERPLAY [243, 267] incrementally learns to become a more and more general algorithmic problem solver, by continually searching the space of possible pairs of new tasks and modifications of the current solver, until it finds a more powerful solver that, unlike the unmodified solver, solves all ”
Curiosity Driven Exploration of Learned Disentangled Goal Spaces (2018, methodology): “Related approaches were recently experimented in the context of Deep Reinforcement Learning, such as in Hindsight Experience Replay [21] and Reverse Curriculum Learning [22] (however using monolithic goal parameterized policies), and within the Power Play framework [23].”
One Big Net For Everything (2018, methodology): “…been learned by a copy of ONE (or even by another machine learning device), e.g., through slow trial and error-based evolution or reinforcement learning, ONE is simply retrained in P OWER P LAY style [75] through well-known, feasible, gradient-based methods on stored input/output traces [75, Sec.”
Reverse Curriculum Generation for Reinforcement Learning (2017, background): “Some very general frameworks have been proposed to generate increasingly hard problems [15], although few implementations concretize the idea and only tackle preliminary tasks [16].”
Paired Open-Ended Trailblazer (POET): Endlessly Generating Increasingly Complex and Diverse Learning Environments and Their Solutions (2019, methodology): “[16, 17]), the job of the algorithm could be to conceive both the challenges and the solutions at the same time.”