Source-linked AI summary
A Definition of Continual Reinforcement Learning
David Abel, André Barreto, Benjamin Van Roy, Doina Precup, Hado van Hasselt, Satinder Singh
TL;DR
The paper addresses the lack of a clean definition of continual reinforcement learning, where standard RL often treats learning as finding a solution rather than endless adaptation. It formalizes implicit search over agent bases with generates and reaches, then defines CRL as problems whose best agents never stop learning. The framework also identifies basis dependence and undecidable reachability questions as important scope boundaries.
Problem
The paper addresses the lack of a clean, general definition of continual reinforcement learning, despite the importance of formalizing agents that never stop learning.
Method
The paper introduces generates and reaches operators to formalize agents as implicitly searching over an agent basis and to characterize whether that search continues indefinitely.
Results
The paper defines CRL as the setting in which all best agents never stop their implicit search, with multi-task RL and continual supervised learning presented as motivating examples.
Takeaways & Limitations
The definitions provide a mathematical language for analyzing continual learning agents and reframing learning as indefinite adaptation rather than identifying a single fixed solution.
Takeaways & Limitations
The definition is basis-dependent, so an agent may be continual relative to one basis but not another; some related decision problems are undecidable.
Abstract
from arXiv · showhide
In a standard view of the reinforcement learning problem, an agent's goal is to efficiently identify a policy that maximizes long-term reward. However, this perspective is based on a restricted view of learning as finding a solution, rather than treating learning as endless adaptation. In contrast, continual reinforcement learning refers to the setting in which the best agents never stop learning. Despite the importance of continual reinforcement learning, the community lacks a simple definition of the problem that highlights its commitments and makes its primary concepts precise and clear. To this end, this paper is dedicated to carefully defining the continual reinforcement learning problem. We formalize the notion of agents that "never stop learning" through a new mathematical language for analyzing and cataloging agents. Using this new language, we define a continual learning agent as one that can be understood as carrying out an implicit search process indefinitely, and continual reinforcement learning as the setting in which the best agents are all continual learning agents. We provide two motivating examples, illustrating that traditional views of multi-task reinforcement learning and continual supervised learning are special cases of our definition. Collectively, these definitions and perspectives formalize many intuitive concepts at the heart of learning, and open new research pathways surrounding continual learning agents.
1 Introduction
The paper argues that standard RL focuses on finding a solution, whereas continual reinforcement learning treats learning as endless adaptation. It introduces a definition in which an RL problem is continual when its best agents never stop learning.
- Standard RL commonly restricts attention to agents that learn to solve problems, rather than adapt indefinitely.
- The community lacks a clean, general CRL definition, motivating a framework for conceptualizing and designing continual learning agents.
- An RL problem is continual reinforcement learning when the best agents never stop learning.
- The framework views agents as implicitly searching over history-based policies and formalizes this perspective with generates and reaches operators.
2 Preliminaries
The paper formalizes RL using countable action-observation interfaces, history-based agents, environments, reward functions, and bounded performance. An RL problem asks an agent designer to identify an optimal available agent in a particular environment.
- An agent-environment interface consists of countable action and observation sets, with at least two actions and one observation.
- Histories are sequences of action-observation pairs, and environments map histories and actions to probability distributions over observations.
- The framework allows Markovian or partially observable environments and both episodic and non-episodic settings.
- An agent is a history-based policy that maps each history to a probability distribution over actions.
- Performance is a bounded function of history, agent, and environment, while reward implementation and aggregation remain unspecified.
- An RL problem is a tuple (e, v, Λ) in which the designer seeks an optimal agent among the available agents for an environment and performance function.
3 Agent Operators: Generates and Reaches
The paper formalizes learning as implicit search over an agent basis and distinguishes agents that eventually stop searching from those that continue indefinitely. The generates and reaches operators provide the language for these distinctions.
- The framework starts from two insights: every agent searches over another agent set, and every agent either searches forever or eventually stops.
- Generates: A learning rule selects a base agent from an agent basis for each history, thereby modeling experience-dependent switching among basis elements.
- Generates: A basis generates an agent set when agents in that set can be understood as switching among the basis elements in an environment.
- Generates: Theorem 3.1 states that every agent-environment pair has infinitely many nontrivial bases that generate the agent.
- Reaches: The reaches operator asks whether an agent eventually becomes equivalent or sufficiently similar to a basis element, distinguishing eventual stopping from continued search.
- Reaches: For any agent and generating basis, exactly one of sometimes reaches or never reaches holds, making indefinite search the basis for continual learning.
4 Continual Reinforcement Learning
The paper defines continual reinforcement learning as settings where optimal agents continue their implicit search over an agent basis indefinitely rather than converge. It formalizes this view and illustrates it with switching MDPs and continual supervised learning, while showing that the definition depends on the chosen basis.
- CRL captures settings in which the best agents do not converge but continue their implicit search over an agent basis indefinitely.
- The paper formalizes continual learning agents using generates and never reaches operators, with continuality meaning that search over a basis continues forever.
- An RL problem is CRL when all optimal agents are continual learning agents relative to the selected basis.
- Q-Learning in Switching MDPs: In switching MDPs, environmental switches make previously optimal policies obsolete, so convergent agents cannot be optimal and optimal agents must continue learning.
- Continual Supervised Learning: The framework also captures continual supervised learning when distributional shifts make continual switching among classifiers necessary for optimality.
- The CRL classification can change with the agent basis, whose choice is constrained in practice by computational resources and domain-specific design considerations.
5 Discussion
The paper frames continual reinforcement learning through two insights: agents can be viewed as searching over agent bases, and this search either continues indefinitely or eventually stops. It presents these tools as a foundation for studying CRL and related artifacts.
- Every agent can be understood as implicitly searching over an agent basis.This is identified as the first central insight underlying the paper’s definition.
- Every agent, in the limit, either continues searching or eventually stops.This is the second central insight used to formalize agents that never stop learning.
- The paper develops mathematical tools and perspectives intended to support more careful thinking about continual reinforcement learning.The discussion presents these tools as an opportunity for further study of CRL and related artifacts.
- The paper includes a summary table of relevant notation before presenting proof details.
B.1 Section 3 Proofs
The proof of Theorem 3.1 constructs infinitely many agent bases that generate a given agent without containing it. The construction alternates behavior across enumerated histories and generalizes to arbitrary basis sizes.
- Theorem 3.1: For any agent-environment pair, infinitely many bases exclude the agent while generating it.This is the statement of Theorem 3.1.
- Proof construction: The construction enumerates realizable histories and designs bases whose agents match the target agent periodically.The kth constructed basis contains k+1 distinct agents and reproduces the target’s actions at recurring positions in the history sequence.
- Proof construction: The first basis uses two agents that agree with the target on alternating history lengths while differing on the others.One agent matches the target on even-indexed histories and differs on odd-indexed histories; the complementary agent supplies the alternating behavior.
- Generalization: The procedure generalizes to every natural number k≥2 by constructing a k-agent basis that still generates the target without containing it.
B.2.1 Theorem 4.1: Properties of CRL
Theorem 4.1 establishes structural properties of CRL instances, including dependence on the chosen basis, exclusion of optimal agents from the basis, and non-minimality of the full agent set.
- Basis dependence: Changing the basis can change an instance from CRL to not CRL.The theorem’s discussion emphasizes that CRL status depends on the selected basis.
- Non-minimality: If the agent set is finite, a smaller agent set generates it.The theorem states that there exists Λ◦ with |Λ◦| < |Λ| and Λ◦⊢_eΛ.
- Non-minimality: If the agent set is infinite, a proper subset generates it.This is the infinite-set counterpart of the theorem’s reduction property.
- Optimal agents: No optimal agent belongs to the basis in a CRL instance.The proof derives this from the defining relation between optimal agents and basis elements.
- Non-minimality: Consequently, the full agent set Λ is not minimal for any CRL instance.Lemma B.3 covers both finite and infinite rank cases.
B.2.2 Theorem 4.2: Properties of Generates
Theorem 4.2 characterizes the generates operator through transitivity, non-commutativity, and undecidable basis-generation decisions. The proofs establish these properties using composition, counterexamples, and a Halting Problem reduction.
- Theorem 4.2: Generates is transitive: if Λ1 generates Λ2 and Λ2 generates Λ3 in e, then Λ1 generates Λ3.The proof composes learning rules to reproduce the behavior of agents in Λ3 from Λ1.
- Theorem 4.2: Generates is not commutative: some Λ1 generates Λ2 while Λ2 does not generate Λ1.A counterexample uses a singleton set and an overlapping agent to establish the asymmetry.
- Theorem 4.2: The decision problem AGENTSGENERATE is undecidable.The proof reduces the Halting Problem to deciding whether a basis generates an agent set.
- Discussion: The transitivity and non-commutativity results motivate viewing agent sets with learning rules through an algebraic perspective.The paper presents this as a direction for future work rather than as an established algebraic theory.
B.2.3 Theorem 4.3: Properties of Reaches
The reaches operator captures whether an agent’s search sometimes stops at a basis or never does. Its properties include non-transitivity, non-commutativity, and undecidability of the associated decision problem.
- Theorem 4.3: Reaches distinguishes agents that sometimes reach a basis from agents that never reach it.The paper frames these as complementary limiting behaviors of an agent’s search process.
- Theorem 4.3: Sometimes reaches is not commutative: one agent set can reach another even when the reverse relation fails.The paper establishes this through a counterexample and Lemma B.10.
- Theorem 4.3: The paper anticipates that many decision problems about arbitrary agent sets will be undecidable, while special decidable cases remain an open direction.It specifically identifies efficient algorithms for such special cases as future work.
- Theorem 4.3: Sometimes reaches is not transitive because successive reachability claims may hold on different realizable histories.A history witnessing the first reach need not be the history witnessing the second.
- Theorem 4.3: The AGENTREACHES decision problem—whether an agent reaches an agent set in an environment—is undecidable.The proof reduces the Halting Problem to AGENTREACHES.
C.1 Additional Analysis: Generates
The generates analysis establishes how agent bases relate across environments and learning rules. Uniform generation is stronger than environment-specific generation and is transitive, while subset relations imply generation.
- C.1 Additional Analysis: Generates: Uniform generation entails generation in every environment.If a basis uniformly generates an agent set, it generates that set under each environment-specific operator.
- C.1 Additional Analysis: Generates: Whenever Λsmall ⊆ Λbig, the smaller agent set generates the larger set under the environment-specific generates relation.The argument uses self-generation and the fact that removing generated agents does not affect generation.
- C.1 Additional Analysis: Generates: For any basis and agent set, either the basis uniformly generates the set under all learning rules or no learning-rule subset does.This dichotomy follows from the universal learning-rule set and excluded middle.
- C.1 Additional Analysis: Generates: Uniform generation is transitive: if Λ1 uniformly generates Λ2 and Λ2 uniformly generates Λ3, then Λ1 uniformly generates Λ3.The proof composes learning rules across the intermediate agent set.
- C.1 Additional Analysis: Generates: A singleton basis generates only itself because generation requires switching among base agents.With one base agent, no nontrivial switching is possible.
C.1.1 Rank and Minimal Bases
The paper characterizes basis size and redundancy through rank and minimality. Minimal bases need not be unique, while a natural basis over all observation-to-action distributions is both minimal and universal.
- C.1.1 Rank and Minimal Bases: The rank of an agent set is the size of the smallest agent basis that uniformly generates it.Rank measures the minimum basis size needed to express the agent set.
- C.1.1 Rank and Minimal Bases: Minimality differs by rank: finite-rank bases require no lower-rank generator, while infinite-rank bases allow no proper subset with equal expressive power.The paper gives separate definitions for finite and infinite rank.
- C.1.1 Rank and Minimal Bases: A minimal basis of an agent set uniformly generates that set and is itself minimal.This definition combines generation with the appropriate minimality condition.
- C.1.1 Rank and Minimal Bases: The minimal basis of an agent set is not necessarily unique.The paper constructs an agent set with two distinct minimal bases.
- C.1.1 Rank and Minimal Bases: The basis B = {λ: 𝒪→Δ(𝒜)} is both minimal and universal.It uniformly generates all agents, and no proper subset retains that universality.
- C.1.1 Rank and Minimal Bases: Every universal basis has infinite rank.This follows directly from the paper’s characterization of universal bases.
C.1.2 Orthogonal and Parallel Agent Sets
The paper extends basis analysis with orthogonality and parallelism. Orthogonal bases generate disjoint agent sets, whereas parallel bases generate the same agent sets.
- C.1.2 Orthogonal and Parallel Agent Sets: The formal notions can be adapted to environment-relative generation or to specified learning-rule sets.The paper notes that these variants preserve the same general formal structure.
- C.1.2 Orthogonal and Parallel Agent Sets: Orthogonal bases generate disjoint agent sets.The paper derives several consequences from this disjointness condition.
- C.1.2 Orthogonal and Parallel Agent Sets: Every non-universal agent basis has an orthogonal agent basis.The paper states this as Corollary C.12.
- C.1.2 Orthogonal and Parallel Agent Sets: Two agent bases are parallel when they generate the same agent sets.Parallelism compares bases by expressive equivalence rather than by their elements.
C.2 Analysis: Reaches
The reaches analysis distinguishes whether agents eventually become behaviorally equivalent to basis agents, either on some histories or across all realizable histories. It establishes implications, transitivity, and set relations among these modalities in CRL.
- Always reaches means that an agent eventually matches a basis agent on every history realizable in the environment.This modality captures eventual equivalence to a basis behavior uniformly across realizable histories.
- Always reaches implies sometimes reaches, because universal eventual equivalence includes at least one realizable history.
- Every agent in a basis always reaches that basis, so any smaller basis-agent set is included in the corresponding always-reaching set.The inclusion follows from basis agents being behaviorally equivalent to themselves.
- Always reaches is transitive: if one agent set always reaches a second and the second always reaches a third, the first always reaches the third.
- The full agent set uniformly generates every agent set and is always reached by all agents.These properties follow from every agent set being contained in the full set and every agent belonging to it.
- Figure 3 organizes the basis, generated agent set, and sometimes-, never-, and always-reaching subsets; the sometimes- and never-reaching sets are disjoint.The basis is visualized as a subset of the generated set, and the always-reaching set is contained within the sometimes-reaching set.