PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Jürgen Schmidhuber

arXiv:1112.5309v2cs.AIcs.LG

TL;DR

The paper asks how to build a practical general problem solver for unknown but computable tasks under realistic resource constraints. It introduces POWERPLAY, which searches for task–solver pairs that expand or improve a solver while preserving earlier skills. The framework continually tests current generalization, supports skill reuse and compression, and remains a greedy but practical approach with explicit scope and safety limitations.

  • Problem

    The central problem is how to construct a practical solver for many a priori unknown, easily solvable tasks while respecting architecture-specific computational restrictions.

  • Method

    POWERPLAY searches task–solver pairs in an unsupervised loop, accepting the first validated modification that solves a new task while preserving earlier tasks or improving their efficiency.

  • Results

    POWERPLAY continually expands its repertoire while testing and exceeding the current solver’s generalization abilities, with validation costs that need not grow with repertoire size.

  • Takeaways & Limitations

    The growing repertoire can be reused for externally posed tasks, while task invention and solver improvement provide a greedy but practical implementation of creativity principles.

  • Takeaways & Limitations

    Because POWERPLAY is greedy, many easy tasks may temporarily prevent it from learning harder tasks, and uncontrolled deployments may conflict with human intentions.

Abstract

from arXiv · show

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. The novel algorithmic framework POWERPLAY (2011) continually 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. Wow-effects are achieved by continually making previously learned skills more efficient such that they require less time and space. New skills may (partially) re-use previously learned skills. POWERPLAY's search orders candidate pairs of tasks and solver modifications by their conditional computational (time & space) complexity, given the stored experience so far. The new task and its corresponding task-solving skill are those first found and validated. The computational costs of validating new tasks need not grow with task repertoire size. POWERPLAY's ongoing search for novelty keeps breaking the generalization abilities of its present solver. This is related to Goedel'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. A first experimental analysis can be found in separate papers [53,54].

1 Introduction

POWERPLAY trains a practical general problem solver by inventing tasks and solver modifications, selecting the simplest pair that expands or improves its repertoire while preserving earlier abilities. Its greedy search is designed to remain feasible, exploit generalization and modularity, and support later externally posed tasks.

  • Framework: POWERPLAY searches for the simplest task–solver pair that adds a new solvable task without forgetting previous skills.Candidate pairs are ordered by computational complexity, with preference for short descriptions and quick validation.
  • Framework: The framework expands traditional solver search to include computable tasks, allowing the system to choose easy-to-find tasks that accelerate successive solver improvements.Inventing the task can reduce intervals between advances rather than merely enlarging the search space.
  • Repertoire growth: New tasks may improve efficiency or compress previous solutions, so the search trades off discovering new skills against refining known ones.Improvements can reduce computational time or storage requirements, and newly learned skills may partially reuse earlier skills.
  • Generalization: POWERPLAY continually tests the solver’s generalization by seeking self-invented tasks that its current instance cannot already solve.Previously untested tasks may already be solvable on typical computer or neural-network architectures.
  • Practicality: Solver modularization can reduce validation costs by limiting how many earlier skills need retesting, effectively decomposing parts of the search into more independent regions.This can make the greedy framework more practically feasible as the repertoire grows.
  • Applications: The growing repertoire may later be reused for externally posed tasks, while variants can penalize solution costs or permit forgetting when average prior performance does not decline.The paper points to separate algorithmic variants and experiments for these extensions.

2 Notation & Algorithmic Framework POWERPLAY (Variant I)

POWERPLAY represents solvers, tasks, and histories as binary strings on a fixed universal reference computer. Each successive solver is associated with an invented task that the new solver solves while the preceding solver does not.

  • Notation: The framework uses finite binary strings as a common representation for programs, tasks, solver states, and encoded objects.B* contains finite bitstrings over {0,1}, and their length is denoted L(x).
  • Solver representation: A fixed universal reference computer can represent deterministic computers, finite-state automata, and neural networks without loss of generality.A user-defined subset S of binary strings specifies the possible problem solvers.
  • Tasks and solver sequence: The initial solver is s0, while each task Ti is selected so si solves Ti and earlier tasks but si−1 does not solve Ti.Tasks may be pattern-recognition problems or robot-control problems, depending on the task-description set T.
  • Efficiency improvements: A valid task may require solving an earlier task with fewer resources, producing a wow-effect through reduced storage, computation time, or energy.The task definition can therefore reward efficiency improvements rather than only entirely new capabilities.
  • Search programs: Programs in P inspect the current solver and recorded history to generate modifications that increase the set of solvable tasks.The framework incrementally trains the solver by searching for such programs.

3 TASK INVENTION, SOLVER MODIFICATION, CORRECTNESS DEMO

Each POWERPLAY candidate program must allocate computation among inventing a task, modifying the current solver, and demonstrating correctness. These three procedures define the framework’s core operational cycle.

  • Core procedures: A tested program must perform TASK INVENTION, SOLVER MODIFICATION, and CORRECTNESS DEMONSTRATION.The three jobs organize candidate evaluation in the algorithmic framework.

3.1 Implementing TASK INVENTION

Task invention can specify pattern-recognition or sequential decision-making problems with explicit input, interaction, correctness, time, and space conditions. These definitions also permit efficiency improvements, while environmental uncertainty makes preservation checks stricter.

  • Task-generation cycle: Candidate programs generate tasks, modify the current solver, and test whether the modified solver solves the new and earlier tasks.This operational sequence is the framework’s basic execution loop.
  • Pattern recognition: Pattern-recognition tasks can specify an input, target output, time bound, and solver-size bound.The task is solved when the solver produces the target output within the stated resource limits.
  • Pattern recognition: A generated query can determine how the same image is classified across different tasks by pairing an input with a task-specific target pattern.The query may support distinct interpretations such as pixel detection or object recognition.
  • Efficiency tasks: Resource bounds allow a task to require a previously solved task to be completed more efficiently, with practical applications requiring gains above a threshold ǫ.Efficiency improvements may also benefit other earlier tasks.
  • Sequential decision making: Sequential decision-making tasks encode an input, an environmental goal test, a time limit, and a solver-size limit.The solver reads the task identifier, interacts through perceptions and actions, and must achieve a computable goal.
  • Sequential decision making: During interaction, internal states, environmental inputs, rewards, and actions form a trace whose recorded history is tested against a computable goal property.A task is solved when the property applied to the trace is satisfied.
  • Correctness demonstration: In partially observable or changing environments, correctness demonstration replays prior action sequences because achieving the same goal under changed conditions counts as a different task.Replay can be cheaper than retesting in the environment, but it cannot distinguish acceleration caused by luck.

3.2 Implementing SOLVER MODIFICATION

SOLVER MODIFICATION constructs each new solver from the previous one, potentially changing only a few components. The allowed solver space can be restricted to syntactically valid programs or weight matrices, and computation time must be balanced against task invention and correctness demonstration.

  • A new solver may require only a few changes to the previous solver, while potentially reusing access to its code.This supports incremental solver improvement rather than rebuilding the solver from scratch.
  • The solver space can be restricted to bit sequences encoding syntactically valid programs in languages such as LISP or Java.
  • For feedforward neural networks with fixed topology, solver states encode valid weight matrices and modifications produce new matrices.The search program may invoke pre-wired learning algorithms as primitive instructions.
  • Each candidate determines how much time to allocate to solver modification while preserving time for task invention and correctness demonstration.

3.3 Implementing CORRECTNESS DEMONSTRATION

CORRECTNESS DEMONSTRATION must establish that a new solver handles the new task without losing earlier skills. POWERPLAY can reduce validation cost by tracking which solver components affect which tasks, although broader proof-based or architectural strategies provide alternative implementations.

  • Naively retesting the new solver on every previous task can make correctness demonstration increasingly expensive as the repertoire grows.
  • A formal proof search can establish that the new solver, but not its predecessor, solves the new task and all earlier tasks without explicit retesting.
  • POWERPLAY can maintain component-specific task lists and test only tasks associated with components changed by the new solver.The tracked lists are updated when tasks begin or cease to use a component.
  • If few components change and those components affect few earlier tasks, correctness demonstration can be highly efficient.
  • Because validation time contributes to task definition, POWERPLAY favors solver modifications that leave many earlier tasks unaffected.This can produce partially independent task-and-solution regions and divide-and-conquer behavior.
  • Prefix-code restrictions can freeze used components, making preservation of earlier tasks easier, but simple task-identifier schemes lack immediate cross-task generalization.

4 Implementations of POWERPLAY

POWERPLAY can be implemented with ordered program search, recurrent neural networks, or stochastic and evolutionary search. Across implementations, candidate programs invent tasks, modify the solver, and demonstrate that the resulting solver improves capability without losing prior solutions.

  • 4.1 Implementation Based on Optimal Ordered Problem Solver OOPS: The OOPS implementation repeatedly allocates bounded time to candidate programs that invent a task, modify the current solver, and validate the modification.
  • 4.1 Implementation Based on Optimal Ordered Problem Solver OOPS: Successful candidates are stored with their program, solver, task, and trace in read-only storage for later searches and possible code reuse.
  • 4.1 Implementation Based on Optimal Ordered Problem Solver OOPS: POWERPLAY extends OOPS by allowing candidate programs to invent their own tasks in addition to searching for solver improvements.
  • 4.1 Implementation Based on Optimal Ordered Problem Solver OOPS: OOPS doubles its time limit until a sufficiently likely program finds a novel solvable task and a solver that preserves previous solutions.
  • 4.1.2 Alternative Problem Solvers Based on Recurrent Neural Networks: Recurrent neural networks provide a solver architecture supporting sequential and parallel computation, with another network potentially generating tasks and solver modifications.
  • 4.1.2 Alternative Problem Solvers Based on Recurrent Neural Networks: SLIM neural networks trace only used neurons and connections, enabling efficient resets when individual tasks use a small fraction of the network.
  • 4.3 Implementation Based on Stochastic or Evolutionary Search: A simpler but less general implementation uses stochastic or evolutionary search to generate task-producing and solver-modifying programs for recurrent networks.

5 Outgrowing Trivial Tasks - Compressing Previous Solutions

POWERPLAY avoids trivial task accumulation by forcing solution reuse and compression, although discovering novel tasks becomes increasingly difficult as the repertoire grows.

  • Once storage reaches its upper limit, POWERPLAY compresses previous solutions so relatively short code can solve different tasks.This addresses extreme modularization by making shared code useful across tasks.
  • Partial reuse of earlier code often makes new tasks easier to find than tasks assigned to previously unused solver parts.
  • Variant II can explicitly require minimal improvements in the average time and space complexity of previous solutions.
  • Over time, inventing novel tasks without forgetting previous solutions becomes increasingly difficult.The paper notes that experiments across solver architectures are needed to analyze this effect in detail.

6 Adding External Tasks

POWERPLAY’s growing repertoire can support externally posed tasks, either by incorporating external tasks into training or by reusing learned solvers, although benefits are not guaranteed.

  • External tasks can be inserted into POWERPLAY so later self-generated tasks acquire a bias toward useful directions.The resulting solver contains externally inserted code that makes some future self-generated tasks easier to find than others.
  • Copying a previously learned solver and searching from it may solve an external task faster than starting from scratch.This advantage depends on self-generated solutions containing reusable general knowledge or code.
  • Some external tasks do not benefit from self-generated solutions, which may even slow the search.
  • The paper proposes theoretical and experimental analysis of when self-generated tasks accelerate solutions to externally generated tasks.
  • POWERPLAY’s i-th goal searches for a program that creates a task and solver modification while demonstrating that the modified solver succeeds where its predecessor does not.

7 Softening Task Acceptance Criteria of POWERPLAY

POWERPLAY variants modify task-acceptance rules to account explicitly for computational cost, permit controlled trade-offs, and support probabilistic evaluation in uncertain environments.

  • 7. Softening Task Acceptance Criteria of POWERPLAY: Acceptance criteria can allow some previous tasks to slow slightly when aggregate runtime does not decrease.
  • 7. Softening Task Acceptance Criteria of POWERPLAY: Time and space constraints may also be traded off, including a Universal Search-style exchange of one extra space bit for a runtime speedup factor of 2.
  • 7. Softening Task Acceptance Criteria of POWERPLAY: The cost-based framework removes explicit time and space bounds from task definitions so computational costs are handled directly.
  • 7. Softening Task Acceptance Criteria of POWERPLAY: Cost-based POWERPLAY evaluates solver performance across all learned tasks using time, space, rewards, and task coverage.One example cost function balances solver size against task-solving time through a positive parameter α.
  • 7. Softening Task Acceptance Criteria of POWERPLAY: In partially observable or changing environments, prior-task correctness can be tested using stored trials, while probabilistic variants estimate costs from limited interactions.
  • 7. Softening Task Acceptance Criteria of POWERPLAY: A candidate program invents or receives a task, modifies the previous solver, and demonstrates correctness by computing its cost against earlier tasks.
  • 7. Softening Task Acceptance Criteria of POWERPLAY: Variant II accepts a modified solver when its overall cost improves, even if it forgets some predecessor abilities.Improvement can result from solving a new task or solving previous tasks more efficiently.
  • 7. Softening Task Acceptance Criteria of POWERPLAY: Implementations can track which solver components support which tasks to facilitate correctness demonstrations and protect valuable components.

8 First Illustrative Experiments

The first experiments use standard neural networks and SLIM RNNs as computational problem-solving architectures for POWERPLAY.

  • Initial experiments use standard neural networks and SLIM RNNs as computational problem-solving architectures.SLIM RNN weights can encode arbitrary computable tasks and self-delimiting programs that may affect environments and internal states.

9 Previous Relevant Work

POWERPLAY is positioned against theoretically optimal but impractical universal solvers and earlier creativity systems as a greedy, feasible framework for continually inventing solvable tasks while preserving prior skills. Its design also exposes trade-offs between short-term task discovery, long-term progress, and improving existing solutions.

  • 9.1 Existing Theoretically Optimal Universal Problem Solvers: Theoretically optimal universal problem solvers can suffer large constant slowdowns that make them infeasible for many small real-world problems.POWERPLAY instead exploits the particular architecture, search algorithm, and constant time and space limitations.
  • 9.2 Traditional Active Learning: POWERPLAY differs from traditional active learning by self-inventing arbitrary computational tasks rather than learning user-provided samples or a predefined task set.Its open-ended setup is not restricted to classification tasks.
  • 9.5 Opposing Forces: Improving Generalization Through Compression, Breaking Generalization Through Novelty: POWERPLAY may sacrifice large long-term gains for small short-term gains because its greedy search can favor many easy tasks over harder tasks.On general architectures, it may also soon run out of easy unsolved tasks because of limited capacity and generalization effects.
  • 9.3 Greedy Implementation of Aspects of the Formal Theory of Creativity: Compared with formal creativity agents, POWERPLAY is greedy but feasible, selecting simple tasks or solution improvements instead of optimizing far-ahead expected learning progress.Theoretically optimal implementations remain impractical, while some earlier reinforcement-learning implementations lack guarantees in partially observable or non-stationary environments.
  • 9.4 Beyond Algorithmic Zero-Sum Games [37, 38] (1997-2002): POWERPLAY cannot forget previously learned skills by design, unlike a previous system without that guarantee; its cost-based variant permits forgetting only when average prior efficiency improves.It records a sequence of separated tasks with explicitly recorded solutions.
  • 9.5 Opposing Forces: Improving Generalization Through Compression, Breaking Generalization Through Novelty: Its time-minimizing search trades off inventing new tasks against compressing or speeding up solutions to previously invented problems.Which improvement is selected depends on which requires fewer computational resources.

10 Words of Caution

POWERPLAY's behavior depends on the computational scope and limits of its task, solver, and search spaces, and an unrestricted deployment could conflict with human intentions or harm the system itself.

  • 10 Words of Caution: With computable task descriptions, general program-capable solvers and tasks, and a general program-space search method, POWERPLAY is limited mainly by computability.Its behavior still depends on the nature and limitations of the task, solver, and search components.
  • 10 Words of Caution: An unrestricted POWERPLAY system may behave unpredictably, conflict with human intentions, or harm itself when given network access, physical-device control, or additional resources.Its continual invention of self-generated tasks is driven by increasing general problem-solving capacity rather than externally specified goals.
Loading 1112.5309v2…