A Definition of Continual Reinforcement Learning
Authors: David Abel
Andre Barreto
Benjamin Van Roy
Doina Precup
Hado van Hasselt
Satinder Singh
Venue: NeurIPS 2023 poster (2023)
Keywords: Continual Reinforcement Learning
Reinforcement Learning
Lifelong Reinforcement Learning
Continual Learning
TL;DR: We carefully define the continual reinforcement learning problem.

Abstract: 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.

A Definition of Continual Reinforcement Learning
David Abel dmabel @ google..com Google DeepMind
André Barreto andrebarreto snattebarret@ggoglee.oo google..com Google DeepMind
Benjamin Van Roy benvanroy @ google.comm Google DeepMind
Doina Precup doinap @ doinap@goggle.oom google.com Google DeepMind
Hado van Hasselt hado@ google.com Google DeepMind
Satinder Singh
naveja@google... google.com Google DeepMind
Abstract
In standard view of the reinforcement learning problem, an agent's goal is to efficiently identify 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. 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 simple definition of the problem that highlights its commitments and makes its primary concepts precise and clear. To this end, this paper dedicated 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 continual learning agent 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 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.
Introduction
In The Challenge of Reinforcement Learning, Sutton states: "Part of the appeal of reinforcement learning is that it is in sense the whole AI problem in microcosm" [56]. Indeed, the problem facing an agent that learns to make better decisions from experience is at the heart of the study of Artificial Intelligence (AI). Yet, when we study the reinforcement learning (RL) problem, it is typical restrict our focus in a number ways. For instance, we often suppose that complete description of the state of the environment is available to the agent, or that the interaction stream is subdivided into episodes. Beyond these standard restrictions, however, there another significant assumption that constrains the usual framing of RI: We tend to concentrate on agents that learn to solve problems, rather than agents that learn forever. For example, consider an agent learning to play Go: Once the agent has discovered how to master the game, the task is complete, and the agent's 's learning can stop. This view learning is often embedded in the standard formulation of RL, in which an agent interacts with Markovian environment with the goal of efficiently identifying optimal policy, at which point learning can cease.
But what if this is not the best way to model the RL problem? That is, instead of viewing learning as finding a solution, we can instead think as endless adaptation. This suggests study of the continual reinforcement learning (CRL) problem [47, 48, 25, 27]. as first explored in the thesis by
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Ring [46], with close ties to supervised never-ending [10, 39, 43] and continual learning [47, 48, 26, 54, 41, 42, 49, 22, 30, 45, 4].
Despite the prominence CRI,, the community lacks a clean, general definition of this problem. is critical to develop such definition promote research on CRL from a clear conceptual foundation, and to guide us in understanding and designing continual learning agents. To these ends, this paper is dedicated to carefully defining the CRL problem. Our definition is summarized follows:
The CRL Problem (Informal)
An RI. problem is an instance of CRI. if the best agents never stop learning.
The core of our definition is framed around two new insights that formalize the notion of "agents that never stop learning": (i) we can understand every agent as implicitly searching over a set of history-basee policies (Theorem 3.1), and (īi) every agent will either continue this search forever, or eventually stop (Remark 3.2). We make these two insights rigorous through a pair of logical operators agents that call generates and reaches that provide a new mathematical language for characterizing agents. Using these tools, we then define CRL as any RL problem in which all of the best agents never stop their implicit search. We provide two motivating examples of CRL, illustrating that traditional multi-task RL and continual supervised learning are special cases of our definition. We further identify necessary properties of CRL (Theorem 4.1) and the new operators (Theorem 4.2, Theorem 4.3). Collectively, these definitions and insights formalize many intuitive concepts at the heart of continual learning, and open new research pathways surrounding continual learning agents.
2 Preliminaries
We first introduce key concepts and notation. Our conventions are inspired by Ring [46], the recent work by Dong et al. [16] and Lu et al. [32], well as the literature general RL by Hutter [23, 24), Lattimore [28], Leike [29], Cohen et al. [12], and Majeed [36].
Notation. We let capital calligraphic letters denote sets (X). lower case letters denote constants and functions (x), italic capital letters denote random variables (X), and blackboard capitals denote the natural and real numbers (N, R. No = N U (0)). Additionally, we let A(X) denote the probability simplex over the set X. That is, the function p X x y A(Z) expresses a probability mass function p(- x, y), over Z, for each E X and y E y. Lastly, we use to denote logical negation, and we use VxeX and Exex express the universal and existential quantifiers over set X.
2.1 Agents and Environments
We begin by defining environments, agents, and related artifacts. Definition 2.1. An enviroenni interface is a pair (A,0) of countable sets A and O where | and |O| 2
We refer to elements A as actions, denoted a, and elements of as observations, denoted o. Histories define the possible interactions between an agent and an environment that share an interface. Definition 2.2. The histories with respect to interface (A,O) are the set of sequences of action- observation pairs,
oo H U JAXOO 1=0
(2.1)
We refer to an individual element of H as a history, denoted h, and we let hh' express the history resulting from the concatenation of any two histories h, h' E H. Furthermore, the set of histories of length E No is defined as H, (A O) and we use h, E H, to refer to a history containing t action-observation pairs, h; Ag00 ... At-10 with ho = 0 the empty history. An environment is then a function from the set of all environments, &, that produces observations given a history.
Definition 2.3. An environment with respect to interface (A,0) is function e H x A - A(O).
This model of environments is general in that it can capture Markovian environments such Markov decision processes (MDPs, Puterman, 2014) and partially observable MDPs (Cassandra et al., 1994), as well as both episodic and non-episodic settings. We next define an agent follows.

---

Definition 2.4. An agent with respect to interface (A, 0) is function À H - A(H).
We let A denote the set of all agents, and let A denote any non-empty subset of A. This treatment of an agent captures the mathematical way experience gives rise behavior, as in "agent functions" from work by Russell and Subramanian [50]. This is in contrast to mechanistic account of agency as proposed by Dong et al. [16] and Sutton [58]. Further, note that Definition 2.4 is precisely history-baset policy; we embrace the view that there is no real distinction between an agent and policy, and will refer to all such functions as "agents" unless otherwise indicated.
2.2 Realizable Histories
We will be especially interested in the histories that occur with non-zero probability as a result of the interaction between particular agent and environment.
Definition 2.5. The realizable histories of a given agent-environment pair, (A,e), define the set of histories of any length that can occur with non-zero probability from the interaction of A and e,
1-1
Hhe = = =
h E H.
e(oxH1 I R=0
hg, ax)A(ax h2) > 0
(2.2)
1=0
Given realizable history ht will refer to the realizable history suffixes, h', which, when concate- nated with It produce realizable history hl' H. Definition 2.6. The realizable history suffixes of a given (A, pair, relative to a history prefix h E HAP define the set of histories that, when concatenated with prefix h, remain realizable,
Ha Hi = (h' E H hh' E HH*).
(2.3)
We abbreviate HM to H. and H H4, where à and are obscured for brevity.
2.3 Reward, Performance, and the RL Problem
Supported by the arguments of Bowling al. [7], assume that all of the relevant goals or purposes of an agent are captured by deterministic reward function (in line with the reward hypothesis [57]). Definition 2.7. We cull r A x O - R reward function.
We remain agnostic to how the reward function is implemented: it could be a function inside of the agent, or the reward function's output could be special scalar in each observation. Such commitments do not impact our framing. When we refer to an environment we will implicitly mean that a reward function has been selected as well. We remain agnostic to how reward aggregated to determine performance, and instead adopt the function defined as follows.
Definition 2.8. The performance, V constants Viin, Vmax E R.
H X X [Vmin, Vmax] is a bounded function for fixed
The function e e It) expresses some statistic the received future random rewards produced by the interaction between A and following history h, where we v(A,e) e) as shorthand for v(A,e e ho). While we accommodate any v that satisfies the above definition, it may be useful to think of specific choices of vA,, e h₂), such as the average reward,
lim inf BB,,e +... Ri+k H, h.).
(2.4)
where Ex,el H, ht] denotes expectation over the stochastic process induced by A and following history hy. Or, we might consider performance based on the expected discounted reward, o(d,e h2) = [A,,RR + yR,+
H, = h,], where y E [0, 1) is discount factor.
The above components give rise to simple definition of the RL problem.
Definition 2.9. An instance of the RL problem is defined by tuple (e, v, A) as follows
A = arg max v(A, e). ACA
(2.5)
This captures the RL problem facing an agent designer that would like to identify an optimal agent (A' E A') with respect to the performance (v), among the available agents (A), in a particular environment (e). We note that simple extension of this definition of the RL problem might instead consider set of environments (or similar alternatives).
3

---

3 Agent Operators: Generates and Reaches
We next introduce two new insights about agents, and the logical operators that formalize them:
1. Theorem 3.1: Every agent can be understood as searching over another set of agents.
2. Remark 3.2: Every agent will either continue their search forever, or eventually stop.
We make these insights precise by introducing a pair of logical operators on agents: (1) set of agents generates (Definition 3.4) another set of agents, and (2) a given agent reaches (Definition 3.5) an agent set. Together, these operators enable to define learning the implicit search process captured by the first insight, and continual learning as the process continuing this search indefinitely.
3.1 Operator 1: An Agent Basis Generates an Agent Set.
The first operator is based on two complementary intuitions.
From the first perspective, an agent can be understood as searching over space of representable action-selection strategies. For instance, in an MDP, agents can be interpreted as searching over the space of policies (that is, the space of stochastic mappings from the MDP's state action). It turns out this insight can be extended to any agent and any environment.
The second complementary intuition notes that, as agent designers, often first identify the space of representable oction-selection strategies of interest. Then, it is natural to design agents that search through this space. For instance, in designing an agent to interact with an MDP, we might be interested in policies representable by a neural network of a certain size and architecture. When we design agents, then consider all agents (choices of loss function, optimizer, memory, and on) that search through the space of assignments of weights to this particular neural network using standard methods like gradient descent. We codify these intuitions in the following definitions.
Definition 3.1. An agent basis (or simply, basis), AB C A, is any non-emply subset of A.
Notice that an agent basis is choice of agent set, A. We explicitly call out a basis with distinet notation (Ag) as it serves important role in the discussion that follows. For example, we next introduce learning rules as functions that switch between elements of an agent basis for each history. Definition 3.2. A learning rule an agent basis AB is a function, H Ag, that selects base agent for each history.
We let Σ denote the set of all learning rules over Ag, and let E denote any non-empty subset of J. A learning rule is a mechanism for switching between the available base agents following each new experience. Notice that learning rules are deterministic; while simple extension captures the stochastic case, we will see by Theorem 3.1 that the above is sufficiently general in a certain sense. We use o (h) to refer to the action distribution selected by the agent À o(h) at any history h. Definition 3.3. Let Σ be set of learning rules over some basis AB, and let e be an environment. We say that a set E-generated by AB e, denoted AB Fy. A, if and only if
VACABoEIY nen A(h) = o(h)(h).
(3.1)
Thus, any choice of Σ together with basis Ag induces a family of agent sets whose elements can be understood as switching between the basis according to the rules prescribed by Σ. We then say that a basis generates an agent set in an environment if there exists a set of learning rules that switches between the basis elements to produce the agent set.
Definition 3.4. We say a basis Ag generates in e, denoted Ag F A, if and only if
AB Fz A.
(3.2)
Intuitively, an agent basis AB generates another agent set A just when the agents in A can be understood as switching between the base agents. It is in this sense that we can understand agents as searching through basis-an an agent just particular sequence of history-conditioned switches over a basis. For instance, let us return to the example of neural network: The agent basis might represent a specific multilayer perceptron, where each element of this basis is an assignment to the network's 's weights. The learning rules are different mechanisms that choose the next set of weights in

---

A1
AB
OA
A1
Aa
(a) Generates (Ag F A)
(b) Sometimes Reaches (A1 ~is Ag)
Figure 1: A visual of the generates (left) and sometimes reaches (right) operators. (a) Generates: An agent basis, An. comprised of three base agents depicted by the triangle, circle, and square, generates a set A containing agents that can each be understood as switching between the base agents in the realizable histories of environment e. (b) Sometimes Reaches: On the right, visualize À E A generated by Aв (from the figure on the left) to illustrate the concept of sometimes reaches. That is, the agent's choice of action distribution each history can understood switching between the three basis elements, and there is at least one history for which the agent stops switching betching-heee, we show the agent settling on the choice of the blue triangle and never switching again.
response to experience (such gradient descent). Together, the agent basis and the learning rules generate the set of agents that search over choices of weights in reaction to experience. We present a cartoon visual of the generates operator in Figure (a)).
Now, using the generates operator, we revisit and formalize the central insight of this section: Every agent can be understood as implicitly searching over agent basis. We take this implicit search process to be the behavioral signature of learning.
Theorem 3.1. For any agent-enviromment pair (A, e), there exists infinitely many choices of a basis, Ag. such that both (1) A Ag, and (2) Ag F (A).
Due to space constraints, all proofs are deferred to Appendix B.
We require that À & Aв ensure that the relevant bases are non-trivial generators of (A). This theorem tells us that no matter the choice of agent or environment, we can view the agent as series of cisttry-condiiioone switches between basis elements. In this sense, we can understand the agent as if it were carrying out a search over the elements some Ag. We emphasize that there are infinitely many choices of such a basis to illustrate that there are many plausible interpretations of an agent's behavior we return to this point throughout the paper.
3.2 Operator 2: An Agent Reaches a Basis.
Our second operator reflects properties of agent's limiting behavior in relation basis. Given agent and basis that the agent searches through, what happens to the agent's 's search process in the limit: does the agent keep switching between elements of the basis, does it eventually stop? For example, in an MDP, many agents interest eventually stop their search on choice of a fixed policy. We formally define this notion in terms of agent reaching a basis according two modalities: an agent (i) sometimes or (ii) never reaches basis.
Definition 3.5. We say agent À E sometimes reaches Ag in e, denoted A ao AB. if and only if
BMeAA MEA, A(hh') = Ag(hh').
(3.3)
That is, for at least one realizable history, there is some base agent (Ag) that produces the same action distribution as A forever after. This indicates that the agent can be understood as if it has stopped its search over the basis. We present visual of sometimes reaches in Figure 1(b). By contrast, say an agent never reaches a basis just when it never becomes equivalent to a base agent.
Definition 3.6. We say agent À never reaches Ag e, denoted À *to Ag. iff (A rhs AB).
We use if in the sense of the positive economists, such Friedman [19].

---

The reaches operators formalize the intuition that, since every agent can be interpreted as if it were searching over basis, every agent will either (1) sometimes, or (2) never stop this search. Since (1)
and (2) are simply negations of each other, we can now plainly state this fact as follows.
Remark 3.2. For any agent-envinn eennteenvirommntt pair (A, e) and any choice of basis AB such that Ag F {1), exactly one of the following two properties must be satisfied:
(1) A Aha AB,
(2) A a/s AB.
(3.4)
Thus, by Theorem 3.1, every agent can be thought of as implicitly searching over an agent basis, and by Remark 3.2, every agent will either (1) sometimes, or (2) never stop this search. We take this implicit search process to he the behavioral signature of learning, and will later exploit this perspective to define a continual learning agent as one that continues its search forever (Definition 4.1). Our analysis in Section 4.4 further elucidates basic properties of both the generates and reaches operators, and Figure 1 presents a cartoon visualizing the intuition behind each of the operators. We summarize all definitions and notation in a table in Appendix A.
Considerations on the Operators. Naturally, we can design many variations of both wis and F. For instance, we might be interested in a variant of reaches in which an agent becomes e-close to any of the basis clements, rather than require exact behavioral equivalence. Concretely, we highlight four axes of variation that can modify the definitions of the operators. We state these varieties for reaches, but similar modifications can be made to the generates operator, too:
1. Realizability, An agent reaches a basis (i) in all histories (and thus, all environments), or (ii) in the histories realizable by given (A, e) pair.
2. History Length. An agent reaches a basis over (i) infinite or, (ii) finite length histories.
3. Probability. An agent reaches basis (i) with probability one, (ii) with high probability.
4. Equality or Approximation. An agent reaches basis by becoming (i) equivalent to a base agent, or (ii) sufficiently similar to base agent.
Rather than define all of these variations precisely for both operators (though do explore some in Appendix C), we acknowledge their existence, and simply note that the formal definitions of these variants follow naturally.
4 Continual Reinforcement Learning
We now provide a precise definition of CRL. The definition formalizes the intuition that CRL captures settings in which the best agents do not converge they continue their implicit search over an agent basis indefinitely.
4.1 Definition: Continual RL
We first define continual learning agents using the generates and never reaches operators as follows. Definition 4.1. An agent is a continual learning agent in relative to AB if and only if the basis generates the agent (Ag* # {A]) and the agent never reaches the basis (A a4s Ag).
This means that an agent is continual learner in an environment relative to AB if the agent's search over Ag continues forever. Notice that an agent might be considered a continual learner with respect to one basis but not another; we explore this fact more in Section 4.4.
Then, using these tools, we formally define CRL as follows.
Definition 4.2. Consider an RL problem (e, v, A). Let AB C. A be basis such that Ag F A, and let A' = arg max v(A,e), We say (e, v, A, AB) defines a CRL problem if VAEN A ats AB-
Said differently, an RL problem is an instance of CRL just when all of the best agents are continual learning agents relative to basis Ag- This problem encourages a significant departure from how we tend to think about designing agents: Given a basis, rather than try to build agents that can solve problems by identifying fixed high-quality element of the basis, we would like to design agents that continue to update their behavior indefinitely in light of their experience.

---

4.2 CRL Examples
next detail two examples CRL to provide further intuition.
Q-Learning in Switching MDPs. First we consider simple instance of CRL based on the standard multi-task view of MDPs. In this setting, the agent repeatedly samples an MDP to interact with from fixed but unknown distribution [64, 9, 2, 25, 20J. particular, make use of the switching MDP environment from Luketina et al. [33]. The environment e consists of a collection of n underlying MDPs, MI..... My, with a shared action space and environment-
space. We refer to this environment-staute space using observations, E O. The environment has fixed constant positive probability of 0.001 switch the underlying MDP, which yields different transition and reward functions until the next switch. The agent only observes each environment state O, which does not reveal the identity of the active MDP. The rewards of each underlying MDP are structured so that each MDP has unique optimal policy. We assume v is defined as the average reward, and the basis is the set of e-greedy policies over all Q(o, a) functions, for fixed E = 0.15. Consequently, the set of agents we generate, AB if A, consists of all agents that switch between these e-greedy policies.
Now, the components (e, v, A, AB) have been defined, of CRL: None of the base agents can be optimal, as the moment that the environment switches its underlying MDP. know that any previously optimal policy will no longer be optimal in the next MDP following the switch. Therefore, any agent that converges (in that it reaches the basis Ag) cannot be optimal either for the same reason. We conclude that all optimal agents A are continual learning agents relative to the basis AB-
see that this is indeed an instance
We present visual of this domain in Figure 2(a), and conduct simple experiment contrasting the performance of e-greedy continual Q-learning (blue) that uses a constant step-size parameter of 0.1, with convergent Q-learning (green) that anneals its step size parameter over time zero. Both use = 0.15, and we set the number of underlying MDPs to # = 10. We present the average reward with 95% confidence intervals, averaged over 250 runs, in Figure 2(b). Since both variants of Q-learning can be viewed as searching over AB. the annealing variant that stops its search will under-perfore compared to the continual approach. These results support the unsurprising conclusion that it is better to continue searching over the basis rather than converge in this setting.
Continual Supervised Learning. Second, we illustrate the power of our CRL definition to capture
continual supervised learning. We adopt the problem setting studied by Mai et al. [35]. Let X denote set of objects to be labeled, each belonging to one of & E N classes. The observation space O consists of pairs, 0, (xx, y1), where X; X and yt E y Here, each x; is input object be classified and yt is the label for the previous input X+ Thus, O = Xx V. We assume by convention that the initial
4.
Qllerrnng (contnux))
mi
11
Qikorrnng (aneeal)
3.5
Bewaad
3.0
25-
m1
M3
10
0.5
5000
10000
15000
20000
25000
Steps
(a) Switching MDP Visual
(b) Switching MDP Results
Figure A visual of a grid world instance of the switching MDPs problem (left) [33], and results from an experiment contrasting continual learning and convergent Q-learning (right). The environment pictured contains и distinct MDPs. Each underlying MDP shares the same state space and action space, but varies in transition and reward functions, indicated by the changing walls and rewarding locations (stars, circles, and fire). The results pictured on the right contrast continual Q-learning (with 0.1) with traditional Q-learning that anneals its step-size parameter to zero over time.
7

---

label yo is irrelevant and can be ignored. The agent will observe a sequence of object-label pairs, (Xo, yo), (1), Vi),.... and the action space is choice of label, R { ax) where | = k. The reward for each history h; is +1 if the agent's most recently predicted label is correct for the previous input, and -I otherwise:
r(a=-10))= = r(a [+1
A: yt,
(4.1)
At-1 otherwise.
Concretely, the continual learning setting studied by Mai et al. [35] supposes the learner will receive samples from a sequence of probability distributions, do, di,,.., each supported over X x Y The (x,y) E X y pairs experienced by the learner are determined by the sequence of distributions. We capture this distributional shift in an environment e that shifts its probability distribution over O depending on the history to match the sequence, do, di.....
Now, is this an instance of CRL? To answer this question precisely, we need to select a (A, AB) pair. We adopt the basis Ag = {Ag x r yi, V yyey) that contains each classifier that maps each object to each possible label. By the universal set of learning rules Σ, this basis generates the set of all agents that search over classifiers. Now, our definition says the above is an instance of CRL just when every optimal agent never stops switching between classifiers, rather than stop their search on fixed classifier. Consequently, if there is an optimal classifier in Ag. then this will not be an instance of CRL. If, however, the environment imposes enough distributional shift (changing labels, adding mass to new elements, and so on), then the only optimal agents will be those that always switch among the base classifiers, in which case the setting is an instance of CRL..
4.3 Relationship to Other Views on Continual Learning
The spirit of continual learning has been an important part of machine learning research for decades, often appearing under the name of "lifelong learning" [63, 62, 53, 55, 51, 3, 4J, "nnver-ending learning" [39, 43] with close ties to transfer-learning [61, 60], meta-learning [52, 17], as well as online learning and non-stationarity [5, 40, 13, 6, 31]. In a similar vein, the phrase "continuing tasks" is used in the classic RL textbook [59] to refer explicitly to cases when the interaction between agent and environment is not subdivided into episodes. Continual reinforcement learning was first posed in the thesis by Ring [46]. In later work [47, 48), Ring proposes a formal definition of the continual reinforcement learning problem The emphasis of Ring's 's proposal is on the generality of the environment: rather than assume that agents of interest will interact with an MDP, Ring suggests studying the unconstrained case in which an agent must maximize performance while only receiving stream of observations as input. The environment or reward function, in this sense, may change over time or may be arbitrarily complex. This proposal is similar in spirit to general RL, studied by Hutter [24], Lattimore [28]. Leike [29], and others [12, 37, 36] in which an agent interacts with an unconstrained environment. General RL inspires many aspects of our conception of CRL; for instance, our emphasis on history-dependence rather than environment-strr
comes directly from general RI. More recently, Khetarpal et al. [25] provide a comprehensive survey of the continual reinforcement learning literature. We encourage readers to explore this survey for a detailed history of the subject.² In the survey, Khetarpal et al. propose a definition of the CRL problem that emphasizes the non-stationarity of the underlying process. In particular, in Khetarpal et al.'s 's definition, an agent interacts with POMDP in which each of the individual components of the FOMDP-such as the state space or reward function- are allowed to vary with time. We note that, as the environment model we study (Definition 2.3) is function of history, it can capture time-indexed non-stationarity. In this sense, the same generality proposed by Khetarpal et al. and Ring is embraced and retained by our definition, but we add further precision to what is meant by continual learning by centering around a mathematical definition of continual learning agents (Definition 4.1).
4.4 Properties of CRL
Our formalism is intended to be a jumping off point for new lines of thinking around agents and continual learning. We defer much of our analysis and proofs to the appendix, and here focus on highlighting necessary properties of CRL.
For other surveys, see the recent survey on continual robot learning by Lesort et al. [30], a survey on continual learning with neural networks by Parisi et al. [42]. survey on transfer learning in RL by Taylor and Stone [60], and survey on continual image classification by Mai et al. [35].
8

---

Theorem 4.1. Every instance of CRL (,, AB) necessarily satisfies the following properties:
1. If + AB Nr, then there exists a Ng such that (1) Ag A, and (2) (, N2) is not instance of CRL.
2. No element of Aa is optimal: AB O =
3. I[[A] is finite, there exists an agent set, A such that |^ < |A| and A F..
4. If[A] is infinite, there exists an agent set, A. such that A C A and A F A.
This theorem tells us several things. The first point of the theorem has peculiar implications. We see that as we change a single element (the basis Ag) of the tuple (e, v, AB, A), the resulting problem can change from CRL to not CRL. By similar reasoning, an agent that is said to be a continual learning agent according to Definition 4.1 may not be continual learner with respect to some other basis. We discuss this point further in the next paragraph. Point (2.) notes that no optimal strategy exists within the basis instedd, to be optimal, an agent must switch between basis elements indefinitely. As discussed previously, this fact encourages a departure in how we think about the RL problem: rather than focus on agents that can identify a single, fixed solution to a problem, CRL instead emphasizes designing agents that are effective at updating their behavior indefinitely. Points (3.) and (4.) show that A cannot be minimal. That is, there are necessarily some redundancies in the design space of the agents in CRL this is expected, since we are always focusing on agents that search over the same agent basis. Lastly, is worth calling attention to the fact that in the definition of CRL, we assume AB C A this suggests that in CRL, the agent basis is necessarily limited in some way. Consequently, the design space of agents A are also limited in terms of what agents they can represent at any particular point in time. This limitation may come about due to a computational or memory budget, or by making use of constrained set of learning rules. This suggests a deep connection between bounded agents and the nature of continual learning, explored further by Kumar et al. [27]. While these four points give an initial character of the CRL problem, we note that further exploration of the properties of CRL is an important direction for future work.
Canonical Agent Bases. It is worth pausing and reflecting on the concept of an agent basis. As presented, the basis is arbitrary choice of set of agents-consequemng consequently, point (1.) of Theorem 4.1 may stand out as peculiar. From this perspective, it is reasonable to ask if the fact that our definition of CRL is basis-dependant renders it vacuous. We argue that this is not the case for two reasons. First, we conjecture that any definition of continual learning that involves concepts like "learning" and "convergence" will have to sit on top of some reference object whose choice arbitrary. Second, and more important, even though the mathematical construction allows for an easy change of basis, in practice the choice of basis is constrained by considerations like the availability of computational resources. It is often the case that the domain or problem of interest provides obvious choices of bases, or imposes constraints that force us as designers to restrict attention bases or learning rules. For example, as discussed earlier, a choice of neural network architecture might comprise basis-any assignment of weights an element of the basis, and the learning rule o is a mechanism for updating the active element of the basis (the parameters) in light of experience. In this case, the number of parameters of the network is constrained by what we can actually build, and the learning rule needs to be suitably efficient and well-behaved. We might again think of the learning rule o as gradient descent, rather than a rule that can search through the basis in an unconstrained way. In this sense, the basis is not arbitrary. We as designers choose a class of functions to act as the relevant representations of behavior, often limited by resource constraints on memory or compute. Then, we use specific learning rules that have been carefully designed to react to experience in a desirable way-for instance, stochastic gradient descent updates the current choice of basis in the direction that would most improve performance. For these reasons, the choice of basis is not arbitrary, but instead reflects the ingredients involved in the design of agents as well as the constraints necessarily imposed by the environment.
space of plausible
4.5 Properties of Generates and Reaches
Lastly, we summarize some of the basic properties of generates and reaches. Further analysis of generates, reaches, and their variations is provided in Appendix C.
Theorem 4.2. The following properties hold of the generates operator:

---

1. Generates is transitive: For any triple (A) , and e E 8, if F A² and A F A3, then A & A
2. Generates not commutative: there exists a pair (A), ,?) and E & such that l A2.
but -(A² &f N.).
3. For all A and pair of agent bases (gg.A2) such that A1 S A A, then AB A.
4. For all A and e E &, A.A.
5. The decision problem, Given (e, A), output True iff Ag A, is undecidable.
The fact that generates is transitive suggests that the basic tools of agent set-paired with set of learning rules-might be likened to an algebraic structure. We can draw symmetry between an agent basis and the basis of vector space: vector space is comprised of all linear combinations of the basis, whereas A is comprised of all valid switches (according to the learning rules) between the base agents. However, the fact that generates is not commutative (by point 2.) raises a natural question: are there choices of learning rules under which generates is commutative? We suggest that useful direction for future work can further explore an algebraic perspective on agents.
We find many similar properties hold of reaches.
Theorem 4.3. The following properties hold of the reaches operator:
1. ro and +f are not transitive.
2. "Sometimes reaches" is not commutative: there exists a pair (A), (23) and e E & such that V MEN A nes A2, but ExPA X2 7/4 A!
3. For all pairs (A, if A, then À ris A.
4. Every agent satisfies À rho A in every environment.
5. The decision problem, Given (e, A), output True iff No A, is undecidable.
Many of these properties resemble those in Theorem 4.2. For instance, point (5.) shows that deciding whether a given agent sometimes reaches a basis an environment is undecidable. We anticipate that the majority of decision problems related to determining properties of arbitrary agent sets interacting with unconstrained environments will be undecidable, though it is still worth making these arguments carefully. Moreover, there may be interesting special cases in which these decision problems decidable (and perhaps, efficiently so). We suggest that identifying these special cases and fleshing their corresponding efficient algorithms is interesting direction for future work.
Discussion
In this paper, we carefully develop simple mathematical definition of the continual RL problem. We take this problem to be of central importance AI field, and hope that these tools and perspectives can serve as an opportunity to think about CRL and its related artifacts more carefully. Our proposal is framed around though it were searching over an agent basis (Theorem 3.1), and (ii) every agent, in the limit, will either sometimes never stop this search (Remark 3.2). These two insights are formalized through the generates and reaches operators, which provide a rich toolkit for understanding agents in a new way-for example, we find straightforward definitions of continual learning agent (Definition 4.1) and learning rules (Definition 3. 3.2). We anticipate that further study of these operators and different families of learning rules can directly inform the design of new learning algorithms: for instance, we might characterize the family of continual learning rules that are guaranteed to yield continual learning agents, and use this guide the design of principled continual learning agents (in the spirit of continual backprop by Dohare et al. [14]). In future work, we intend to further explore connections between our formalism of continual learning and some of the phenomena at the heart of recent empirical continual learning studies, such as plasticity loss [34, 1, 15], in-context learning [8], and catastrophic forgetting [38, 18, 21, 26]. More generally, we hope that our definitions, analysis, and perspectives can help the community to think about continual reinforcement learning in new light.
new insights about agents: (i) every agent can be understood as
10

---

Acknowledgements
The authors are grateful to Michael Bowling, Clare Lyle, Razvan Pascanu, and Georgios Piliouras for comments on draft of the paper, as well as the anonymous NeurIPS reviewers that provided valuable feedback on the paper. The authors would further like to thank all of the 2023 Barbados RL Workshop participants and Elliot Catt, Will Dabney, Sebastian Flennerhag, András György, Steven Hansen, Anna Harutyunyan, Mark Ho, Joe Marino, Joseph Modayil, Rémi Munos, Evgenii Nikishin, Brendan O' Donoghue, Matt Overlan, Mark Rowland, Tom Schaul, Yannick Shroecker, Rich Sutton, Yunhao Tang, Shantanu Thakoor, and Zheng Wen for inspirational conversations.
References
[1] Zaheer Abbas, Rosie Zhao, Joseph Modayil, Adam White, and Marlos C Machado. Loss of plasticity in continual deep reinforcement learning. arXiv preprint arXiv:2303.07507, 2023.
[2] David Abel, Yuu Jinnai, Yue Guo, George Konidaris, and Michael L.. Littman. Policy and value transfer in lifelong reinforcement learning. In Proceedings of the International Conference on Machine Learning, 2018.
[3] Haitham Bou Ammar, Rasul Tutunov, and Eric Eaton. Safe policy search for lifelong reinforce- ment learning with sublinear regret. In Proceedings of the International Conference on Machine Learning, 2015.
[4] Megan M Baker, Alexander New, Mario Aguilar-Simon Ziad Al-Halah, Sébastien MR Arnold, Ese Ben-lwhiwhu, Andrew P Brna, Ethan Brooks, Ryan C Brown, Zachary Daniels, et al. domain-agnostic approach for characterization of lifelong learning systems. Neural Networks, 160:274-296 296, 2023.
[5] Peter L Bartlett. Learning with slowly changing distribution. In Proceedings of the Annual Workshop on Computational Learning Theory, 1992.
[6] Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi-armed-bante problem with non-stationary rewards. Advances in Neural Information Processing Systems, 2014.
[7] Michael Bowling, John D. Martin, David Abel, and Will Dabney. Settling the reward hypothesis. In Proceedings of the International Conference on Machine Learning, 2023.
[8] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in Neural Information Processing Systems, 2020.
[9] Emma Brunskill and Lihong Li. PAC-inspired option discovery in lifelong reinforcement learning. In Proceedings of the International Conference on Machine Learning, 2014.
[10] Andrew Carlson, Justin Betteridge, Bryan Kisiel, Burr Settles, Estevam R Hruschka, and Tom Mitchell. Toward an architecture for never-ending language learning. Proceedings of the AAAI Conference on Artificial Intelligence, 2010.
[11] Anthony R. Cassandra, Leslie Pack Kaelbling, and Michael L. Littman. Acting optimally in partially observable stochastic domains. In Proceedings of the AAAI Conference on Artificiall Intelligence, 1994.
[12] Michael K Cohen, Elliot Catt, and Marcus Hutter. A strongly asymptotically optimal agent in general environments. arXiv preprint arXiv: 190..010000022 2019.
[13] Travis Dick, András György, and Csaba Szepesvari. Online learning in Markov decision processes with changing cost sequences. In Procedings of the International Conference on Machine Learning, 2014.
[14] Shibhansh Dohare, Richard S Sutton, and A Rupam Mahmood. Continual backprop: Stochastic gradient descent with persistent randomness. arXiv preprint arXiv:2108.0633 2021.
11

---

[15] Shibhansh Dohare, Juan Hernandez- Garcia, Parash Rahman, Richard Sutton, and A Rupam Mahmood. Loss of plasticity in deep continual learning. arXiv preprint 2rXiv:2306.38822 2023.
[16] Shi Dong, Benjamin Van Roy, and Zhengyuan Zhou. Simple agent, complex environment: Efficient reinforcement learning with agent states. Journal of Machine Learning Research, 23 (255):1-54, 2022.
[17] Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-leaming for fast adapta- tion of deep networks. In Proceedings of the International Conference on Machine Learning, 2017.
[18] Robert M French. Catastrophic forgetting in connectionist networks. Trends in cognitive sciences, 3(4):128-1335 1999.
[19] Milton Friedman. Essays in positive economics. University of Chicago press, 1953.
[20] Haotian Fu, Shangqun Yu, Michael Littman, and George Konidaris. Model-based lifelong reinforcement learning with Bayesian exploration. Advances in Neural Information Processing Systems, 2022.
[21] Ian J Goodfellow, Mehdi Mirza, Da Xiao, Aaron Courville, and Yoshua Bengio. An empirical investigation of catastrophic forgetting in gradient-basee -based neural networks. arXiv preprint 1:Xiv:1312.6211, 2013.
[22] Raia Hadsell, Dushyant Rao, Andrei A Rusu, and Razvan Pascanu. Embracing change: Con- tinual learning in deep neural networks. Trends in cognitive sciences, 24(12):1028-1044 2020.
[23] Marcus Hutter. A theory of universal artificial intelligence based on algorithmic complexity. arXiv preprint cs/0004001, 2000.
[24] Marcus Hutter. Universal artificial intelligence: Sequential decisions based algorithmic probability. Springer Science & Business Media, 2004.
[25] Khimya Khetarpal, Matthew Riemer. Irina Rish. and Doina Precup. Towards continual rein- forcement learning: review and perspectives. Journal of Artificial Intelligence Research, 75: 1401-1476, 2022.
[26] James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kicran Milan, John Quan, Tiago Ramalho, Agnieszka Baabskk-Barwwiska. et al. Overcoming catastrophic forgetting in neural networks. Proceedings of the National Academy of Sciences, 114(13):3521-332 2017.
[27] Saurabh Kumar, Henrik Marklund, Ashish Rao, Yifan Zhu, Hong Jun Jeon, Yueyang Liu, and Benjamin Van Roy. Continual learning computationally constrained reinforcement learning. arXiv preprint arXiv:2307.04345. 2023.
[28] Tor Lattimore. Theory of general reinforcement learning. PhD thesis, The Australian National University, 2014.
[29] Jan Leike. Nonparametric general reinforcement learning. PhD thesis, The Australian National University, 2016.
[30] Timothée Lesort, Vincenzo Lomonaco, Andrei Stoian, Davide Maltoni, David Filliat, and Natalia Bodriged Continual learning for robotics: Definition, framework, learning strategies, opportunities and challenges. Information fusion, 58:52 68, 2020.
[31] Yueyang Liu, Benjamin Van Roy, and Kuang Xu. definition of non-stationary bandits. arXiv preprint arXiv:2302. 12202, 2023.
[32] Xiuyuan Lu, Benjamin Van Roy, Vikranth Dwaracherla, Morteza Ibrahimi, Ian Osband, and Zheng Wen. Reinforcement learning, bit by bit. Foundations and Trends Machine Learning, (6(6):733-866 2023. ISSN 1935-8237.
12

---

[33] Jelena Luketina, Sebastian Flennerhag, Yannick Schroecker, David Abel, Tom Zahavy, and Satinder Singh. Meta-gradie geta-gradients in non-stationary environments. In Proceedings of the Confer- ence on Lifelong Learning Agents, 2022.
[34] Clare Lyle, Zeyu Zheng, Evgenii Nikishin, Bernardo Avila Pires, Razvan Pascanu, and Will Dabney. Understanding plasticity in neural networks. In Proceedings of the International Conference Machine Learning. 2023.
[35] Zheda Mai, Ruiwen Li, Jihwan Jeong, David Quispe, Hyunwoo Kim, and Scott Sanner. Online continual learning in image classification: An empirical survey. Neurocomputing. 469:28-51, 2022.
[36] Sultan J Majeed. Abstractions of general reinforcement Learning. PhD thesis, The Australian National University, 2021.
[37] Sultan Javed Majeed and Mareus Hutter. Performance guarantees for homomorphisms beyond Markov decision processes. In Proceedings of the AAAI Conference on Artificial Intelligence, 2019.
[38] Michael McCloskey and Neal J Cohen. Catastrophic interference in connectionist networks: The sequential learning problem. In Psychology of learning and motivation, volume 24, pages 109-165, Elsevier, 1989.
[39] Tom Mitchell, William Cohen, Estevam Hruschka, Partha Talukdar, Bishan Yang, Justin Bet- teridge, Andrew Carlson, Bhavana Dalvi, Matt Gardner, Bryan Kisiel, al. Never-ending learning. Communications of the ACM, 61(5):103-115 2018.
[40] Claire Monteleoni and Tommi Jaakkola. Online learning of non non-stationary sequences. Advances in Neural Information Processing Systems, 16, 2003.
[41] Cuong V Nguyen, Yingzhen Li, Thang Bui, and Richard E Turner. Variational continual learning. 2018.
[42] German I Parisi, Ronald Kemker, Jose L Part, Christopher Kanan, and Stefan Wermter. Continual lifelong learning with neural networks: A review. Neural networks, 113:54-71, 2019.
[43] Emmanouil Antonios Platanios, Abulhair Saparov, and Tom Mitchell. Jelly bean world: A testbed for never-ending learning. arXiv preprint arXiv:2002.06306, 2020.
[44] Martin L Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 2014.
[45] Matthew Riemer, Sharath Chandra Raparthy, Ignacio Cases, Gopeshh Subbaraj. Maximilian Puelma Touzel, and Irina Rish. Continual learning in environments with polynomial mixing times. Advances in Neural Information Processing Systems, 2022.
[46] Mark B Ring. Continual learning in reinforcement environments. PhD thesis, The University of Texas at Austin, 1994.
[47] Mark B Ring. Child: A first step towards continual learning. Machine Learning, 28(1):77-104, 1997.
[48] Mark B Ring. Toward formal framework for continual learning. In NeurlPS Workshop on Inductive Transfer, 2005.
[49] David Rolnick, Arun Ahuja, Jonathan Schwarz, Timothy Lillicrap, and Gregory Wayne. Ex- perience replay for continual learning. Advances in Neural Information Processing Systems, 2019.
[50] Stuart J Russell and Devika Subramanian. Provably bounded-optimal agents. Journal of Artificial Intelligence Research, 2:575-609, 1994.
[51] Paul Ruvolo and Eric Faton. ELLA: An efficient lifelong learning algorithm. In Proceedings of the International Conference on Machine Learning, 2013.
13

---

[52] Tom Schaul and Jürgen Schmidhuber. Metalearning. Scholarpedia, 5(6):4650, 2010.
[53] Jürgen Schmidhuber, Jieyu Zhao, and Nicol N Schraudolph. Reinforcement learning with self-modifying policies. Learning to Learn, pages 293-309. Springer, 1998.
[54] Jonathan Schwarz, Wojciech Czarnecki, Jelena Luketina, Agnieszka Grabska-Barwinsse Yee Whye Teh, Razvan Pascanu, and Raia Hadsell. Progress & compress: A scalable framework for continual learning. In Proceedings of the International Conference on Machine Learning.
2018.
[55] Daniel Silver. Machine lifelong learning: Challenges and benefits for artificial general intelligence. In Proceedings of the Conference on Artificial General Intelligence, 2011.
[56] Richard S Sutton. Introduction: The challenge of reinforcement learning. In Reinforcement Learning, pages 1-3. Springer, 1992.
[57] Richard S Sutton. The reward hypothesis, 2004, URL /.t.htppp//hacompeeeeeeeeeesssss wwwberta. Ctt//LLA//rroarrdyyyttttettse
html.
[58] Richard S Sutton. The quest for common model of the intelligent decision maker. arXiv preprint 23X. 2022.
[59] Richard S Sutton and Andrew G. Barto. Reinforcement Learning: An Introduction. MIT Press, 2018.
[60] Matthew E. Taylor and Peter Stone. Transfer learning for reinforcement learning domains: survey. Journal of Machine Learning Research, 10331):1633-1683 2009.
[61] Sebastian Thrun. Is learning the n-th thing any easier than learning the first? Advances in Neural Information Prucessing Systems, 1995.
[62] Sebastian Thrun. Lifelong learning algorithms. Learning to Learn, 8:181-209, 1998.
[63] Sebastian Thrun and Tom M Mitchell. Lifelong robot learning. Robotics and autonomous systems, 151-2)):55446 1995.
[64] Aaron Wilson, Alan Fern, Soumya Ray, and Prasad Tadepalli. Multi-task reinforcement learning: a hierarchical Bayesian approach. In Proceedings of the International Conference on Machine learning, 2007.
14

---

A
Notation
We first provide table summarizing all relevant notation.
Notation
Meaning
Definition
A
Actions
0
Observations
H
Length f histories
H4 (Ax H U H,
H
All histories
history
E
hh
History concatenation
h4
Length f history
h; E H, H Uis (hr EH, e(ox h2, ax) h2) > 0} Hy = (I' EH: hh' e HAe)
H HiA
Realizable histories
Hy: H Ae
Realizable history suffixes
Environment
e: A(A)
Set of all environments
A
Agent
A: - AA)
Set of all agents
A
Set of agents Agent basis
AÇA
AB
An C
r
Reward function
r:AXO- - R
V
Performance
D:HXAXE-
[ Vmmx
a
Learning rule
8:H4 - AB
F
Set of all learning rules Set of learning rules
Σ
Σ3Σ
AB Fx A
E-generates
v ReN Mh) ((h)(h)
Ag # A
Generates
Beer AB FI A
AB FE A
Universally E-generates
VA keH 21h) o(h)(h) Beer AB FS A
AB F A
Universally generates
A rás AB
Sometimes reaches
Eneri AygeAg M A(hh') An(hh")
A 7pt> AB
Never reaches
(A mi Ar)
Inla AB
Always reaches
V Yee Bee V We W & MEH, A(hhh") = AB(hh*h)
Table 1: A summary of notation.
B Proofs of Presented Results
We next provide proofs of each result from the paper. Our proofs make use of some extra notation: we use logical implication, and we use (XX to denote the power set of any set X. Lastly, we use Vac and 3ySx as shorthand for V ()))() and 3 respectively.
15

---

B.1
Section 3 Proofs
Our first result is from Section of paper.
Theorem 3.1. For any pair (A, e). there exists infinitely many choices of a basis, Ag. such that both (1) & Ag, and (2) Ag F {A}.
Proof of Theorem 3.1.
Choose fixed but arbitrary pair (A,e). Then, enumerate the realizable histories, Hhe and let ht denote the first element of this enumeration, 1/² the second, and so on.
Then, we design a constructive procedure for basis that, when repeatedly applied, induces an infinite enumeration of bases that satisfy the desired two properties. This constructive procedure for the k-th basis will contain k + agents, where each agent is distinet from A, but will produces the same action as the agent every + elements of the history sequence, h! ,
For the first (k 1) basis, construct agents. The first, A1.- chooses the same action distribution as A on each even numbered history: (k') = A(h'). Then, this agent will choose a different action distribution on the odd length histories: 1 (1 * A(h"*),, for any even natural number. The second agent, A will do the opposite to 1/- each odd numbered history h Ag (l # A(h"tl), but on every even numbered history, Ag (h') = A(H').
Observe first that by construction, A AB. and À # A since there exist histories where they choose different action distributions. Next, observe that basis, AB [ 11) generates {1} in e through the following set of learning rules, Σ: given any realizable history, / E HAe. check whether the history has an even odd numbered index in the enumeration. If odd, choose A/. and if even, choose 2
More generally, this procedure can be applied for any k:
(A(h) # A(h)
[k]==1,
Λ (Ap..... Agt1) 1
(B.1)
otherwise,
where we use the notation [h] == i to express the logical predicate asserting that the modulos of the index of h in the enumeration h! h? .?? is equal to í.
Further, * A(h) simply refers to any choice of action distribution that unequal to A(h). Thus, for all natural numbers k 2 2, we can construct new basis consisting of k base agents that generates A in e, but does not contain the agent itself. This completes the argument. O
B.2
Section 4 Proofs
We next present the proofs of results from Section 4.
B.2.1 Theorem 4.1: Properties of CRL
We begin with Theorem 4.1 that establishes basic properties of CRL.
Theorem 4.1. Every instance of CRL (e, V, A, An) satisfies the following properties:
1. If A * AB U A', there exists Ag such that (1) Ng F A, and (2) (e, D, D, is not instance of CRI.
2. No element of Aa is optimal: An A 0.
3. If [F|I| is finite, there exists an agent set, A such that |A < [A] and A F A.
4. [|| is infinite, there exists agent set, A such that A A and A F AA.
16

---

We prove this result in the form of three lemmas, corresponding to each of the four points of the theorem (with the third lemma, Lemma B.3, covering both points and 4.). Some of the lemmas make use of properties of generates and reaches that we establish later in Appendix C.
Lemma B.I. For all instances of CRL (, AB). if A + AB U, then there exists choice Agg such that (1) Ag F A, and (2) (e, v, A, Agg is not an instance of CRL.
Proof of Lemma B.I.
Recall that a tuple (e, A, AB) CRL.just when all of the optimal agents A do not reach the basis. Then, the result holds straightforward consequence of two facts. First, we can always construct a new basis containing all of the optimal agents, Ag An U A'. Notice that Ag still generates by property three of Theorem 4.2. Further, since both Aş and A' are each subsets of A, and by assumption A # AB U (so there is at least one sub-optimal agent that is not in the basis), follows that Ag A. Second, by Proposition C.15, know that every element Ag Ag will always reach the basis, Ag DMis Ag. Therefore, in the tuple (e, v, A, Ag), each of the optimal agents will reach the basis, and therefore this is not an instance of CRL.
Lemma B.2. No element of AB optimal: AB O
Proof of Lemma B.2.
The lemma follows combination of facts.
First, recall that, by definition of CRL, each optimal agent À E A satisfies 1 a/s AB. Second, note that by Lemma B.11, we know that each ÅB E AB satisfies ÅB ~is AB-
Therefore, since sometimes reaches (~o*) and never reaches (~f²) are negations of another, we conclude that no basis element can be optimal.
D
Before stating the next lemma, note that points (3.) and (4.) of Theorem 4.1 simply expansions of the definition a minimal agent set, which we define precisely in Definition C.4 and Definition C.5.
Lemma B.3, For any instance of CRL, A is not minimal.
Proof of Lemma B.3.
We first show that A cannot be minimal. To do so, consider the cases where the rank (Definition C.3) of A is finite and infinite separately.
(Finite Rank A.)
rank(A) is finite and minimal, then follows immediately that there is no agent set of smaller rank that generates A. By consequence, since AB A and Ag F A, we conclude that cannot minimal.
(Infinite Rank A.)
If rank(A) is infinite and minimal, then there no proper subset of A that uniformly generates A by definition. By consequence, since AB C A and AB F A, we conclude that A cannot be minimal. /
This completes the argument of both cases, and conclude that for any instance of CRL, A is not minimal.
17

---

B.2.2 Theorem 4.2: Properties of Generates
Next, we prove basic properties of generates.
Theorem 4.2. The following properties hold of the generates operator:
1. Generates is transitive: For any triple (A), ,2) and e E &, if A F A² and A F A3, then A $ AA.
2. Generates not commutative: there exists a pair (A), (A' and E such that A A2,
but -(A² N.).
3. For all A and pair of agent bases (Ag, such that A18 S A if if # A, then A # A
4. For all A and &, A.A.
5. The decision problem, Given (e, AB, A), output True iff AB is undecidable.
The proof of this theorem is spread across the next five lemmas below.
The fact that generates is transitive suggests that the basic tools of an agent set-paired with a set of learning rules
be likened to an algebraic structure. We can draw symmetry between an agent basis and the basis of vector space: vector space comprised of all linear combinations of the basis, whereas A is comprised of all valid switches (according to the learning rules) between the base agents. However, the fact that generates is not commutative (by point 2.) raises a natural question: there choices of learning rules under which generates is commutative? An interesting direction for future work is to explore this style algebraic analysis on agents.
Lemma B.4. Generates is transitive: For any triple (A), A2, and e & if A and A F A3, then A F A
Proof of Lemma B.4.
Assume A F A2 and A $ A3, Then, by Proposition C.4 and the definition of the generates operator, we know that
V hew A²(hh db()(h))
(B.2)
Y W neA A² = (h)(()),
(B.3)
where E and 2 express the set of all learning rules over A and A² respectively. By definition of learning rule, a, we rewrite the above as follows,
V VAPEAYY Be A?(h) = (1),,,
(B.4)
V (3(h) A²(h).
(B.5)
Then, consider fixed but arbitrary A A3. We construct learning rule defined over A as a¹ :H( - A' that induces an equivalent agent as follows. For each realizable history. h E H. by Equation B.5 we know that there is A such that (3 A²(h), and by Equation B.4, there an A such that A (h) = (h). Then, set a!! + A such that A A'(h) = A A2 (h)
Since It and 3 were chosen arbitrarily, we conclude that
Y A²(h) = A
But, by the definition of E, this means there exists learning rule such that
W (2 = a' (h)(h).
This is exactly the definition of E-generation, and by Proposition C.4, we conclude A! F A
18

---

Lemma B.5. Generates is not commutative: there exists a pair (A (A' ,A) and e E & such that A3, but -A2 )
Proof of Lemma B.5.
The result follows from a simple counterexample: consider the pair
A' (A:: h aıa,,
A (Ai : - al, h + a2).
Note that since A, is both sets, A is a singleton, we know that A2 A in any environment. But, by Proposition C.6, we know that A cannot generate A?.
Lemma B.6. For all A and pair of agent bases (A A2) such that AB A A A, then Ag A.
Proof of Lemma B.6.
The result follows as a natural consequence of the definition of generates. Recall that Ag F A just when,
Bricr Ag FE! A
(B.6)
= Brigr V WheR A(h) = A1g (1)(
(B.7)
where again 1g'(h) E Ag is the base agent chosen by dh)). We use superscripts E' and a to signify that a! is defined relative A1. that is, a¹ : E
But, since AB S AAg. we can define I Σ! and ensure that ^ Fg' A, since the agent basis A was already sufficient to generate A. Therefore, conclude that A3 F A.
Lemma B.7. For all A and e &
Proof of Lemma B.7
| This is direct consequence of Proposition C.18.
Lemma B.8. The decision problem, AGENTSGENERATE, Given (e, AB, A), output True iff Ap F A, undecidable.
Proof of Lemma B.8.
We proceed as is typical such results by reducing AGENTSGENERATE from the Halting Problem.
In particular, let m a fixed but arbitrary Turing Machine, and w be a fixed but arbitrary input to be given to machine Then, HALT defines the decision problem that outputs True iff m halts on input w.
We construct an oracle for AGENTSGENERATE that can decide HALT as follows. Let (A, O) be an interface where the observation space is comprised of all configurations of machine m. Then, we consider deterministic environment e that simply produces the next configuration of m when run on input w, based on the current tape contents, the state of m, and the location of the tape head. Note that all three of these elements are contained in Turing Machine's 's configuration, and that a single configuration indicates whether the Turing Machine is halting state not. Now, let the action space A consist of two actions, {Ano-op, Ahalr). On execution of ano-op no-op. the environment moves to the next configuration. On execution of Ahalt the machine halts. That is, restrict ourselves to the singleton agent set, A, containing
19

---

the agent A that outputs 4halt directly following the machine entering a halting configuration, and ono-op otherwise:
Analt
0 is halting configiration,
A hao +
A = {A?}.
ano-op otherwise.
Using these ingredients, we take any instance of HAI.T, (m, w), and consider the singleton agent basis: Ag {ano-op).
We make one query to our AGENTSGENERATE oracle, and ask: AB F A. it is True, then the histories realizable by (A", e) pair ensure that the single agent in A never emits the Ghall action, and thus, does not halt which m halts on w. We thus use the oracle's 's response directly to decide the given instance of HALT
If is False, then there realizable histories in in
B.2.3 Theorem 4.3: Properties of Reaches
We find many similar properties hold for reaches.
Theorem 4.3. The following properties hold of the reaches operator:
1. no and af are not transitive.
2. Sometimes reaches is not commutative: there exists pair (A ,A)) and e E & such that
V VAE A as A2, but ExEENe X2 *ts A!
3. For all pairs (A, if A, then À whs A.
4. Every agent satisfies À ais A in every environment.
5. The decision problem, Given A), output True iff A do A, is undecidable.
Again, prove this result through five lemmas that correspond to each of the above properties.
Many of these properties resemble those Theorem 4.2. For instance, point (5.) shows that deciding whether given agent sometimes reaches basis in an environment is undecidable. We anticipate that the majority of decision problems related to determining properties of arbitrary agent sets will be undecidable, though it is still worth making these arguments carefully. Moreover, there may be interesting special cases in which these decision problems are decidable (and perhaps, efficiently so). Identifying these special cases and their corresponding efficient algorithms is another interesting direction for future work.
Lemma B.9. wh and ats not transitive.
Proof of Lemma B.9.
We construct two counterexamples, one for each of "sometimes reaches" (~is and "never reaches" (>fs).
Counterexample: Sometimes Reaches. such that both
To do so, we begin with tuple (e, (e,
VANEN A ro A
VAPAAE 12 Ne A2.
We will show that there is an agent, A' A', such that T' 7/s A3, thus illustrating that sometimes reaches is not guaranteed be transitive. The basic idea is that sometimes reaches only requires an agent stop its search on one realizable history. So, A we A might happen on some history Jt, but each X A might only reach A on an entirely different history. As a result, reaching A is not enough to ensure the agent also reaches A3
In more detail, the agent sets of the counterexample are as follows. Let A (a1,az) .2) and 0 (01,02), Let A be all agents that, after ten timesteps, always take a2. À is simple: it
20

---

always takes 41, except on one realizable history, h" (and all of the realizable successors of h. I/" where it switches to taking R2 after ten timesteps. Clearly A Mi A since after ten timesteps. we know there will be some X2 such that Ā (h* h²" for all realizable history suffixes h Now, by assumption, we know that 12 ~hs A². This ensures there a single realizable history such that there an A where A2(hh') A² for any realizable suffix It' To finish the counterexample, we simply note that this realizable h can be different from h and all of its successors. For example, ht might be the history containing only 01 for the first ten timesteps, while h could be the history containing only for the first ten timesteps. Thus, this A never reaches A3, and we conclude the counterexample. /
Counterexample: Never Reaches. The instance for never reaches simple: Let A {ai, 42, 23), and A = A². Suppose all agents in A (and thus A3) only choose actions and Ø3. Let A² singleton, A = (A2) such that A2 r> 42. Clearly, every A с A will never reach A since none of them ever choose A2. Similarly, A will never reach A since no agents A choose 22. However, by Proposition C.15 and the assumption that A A3, we know VAPAA A' DM& A². This directly violates transitivity. /
This completes the argument for all three cases, and we conclude.
Lemma B.10. Sometimes reaches is not commutative: there exists pair ,A), and such that V Vae A res A but ExPENT X a/s A.
Proof of Lemma B.10.
The result holds as straightforward consequence of the following counterexample. Consider the pair of agent sets
A' (Ar ( h4:h->a) a1),
A (A₁ a1, + a2).
Note that since A is both sets, and A is a singleton, we know that A res A in any environment by Lemma B.11. But, clearly Aj never reaches A since no agent in Al ever chooses d1.
Lemma B.11. For all pairs (A, e), if E A, then À ne A.
Proof of Lemma B.11.
The proposition is straightforward, as any A will be equivalent to itself behavior for all histories.
Lemma B.12. Every agent satisfies A de A in every environment.
Proof of Lemma B.12.
This is again a direct consequence of Proposition C.18.
Lemma B.13. The decision problem, AGENTREACHES, Given (e, A, A), output True iff who A, undecidable.
Proof of Lemma B.13.
We again proceed by reducing AGENTREACHES from the Halting Problem.
21

---

In particular, let m be fixed but arbitrary Turing Machine, and w be a fixed but arbitrary imput to be given to machine m. Then, HALT defines the decision problem that outputs True iff m halts on input w.
We construct oracle for AGENTREACHES that decide HALT follows. Consider the same observation space used in the proof of Lemma B.8: Let O be comprised of all configurations of machine m. Then, sequences of observations are simply evolution of different Turing Machines processing possible inputs. We consider an action space, A =
(ahalted, yeet-yatt where agents simply report whether the history so far contains halting configuration.
Then, we consider deterministic environment that simply produces the next configuration of m when run on input w, based on the current tape contents, the state of m, and the location of the tape head. Note again that all three of these elements are contained in a Turing Machine's configuration.
Using these ingredients, we take any instance of HALT, (m,w), and build the singleton agent set AB containing only the agent Ahalted + Ahalted that always reports the machine as having halted. We then consider whether the agent that outputs Anot-yet indefinitely until m reports halting, at which point the agent switches to Ahalted-
We make one query to our AGENTREACHES oracle, and ask: A ~is AB. If is True, then the branching agent eventually becomes equivalent to Apalted in that they both indefinitely output Ahalted on at least one realizable history. Since e is deterministic, we know this equivalence holds across all histories. the query reports False, then there is no future in in which m halts on w, otherwise the agent would become equivalent to Ahated. We thus use the oracle's response directly to decide the given instance of HALT.
C Additional Analysis
Finally, we present a variety of additional results about agents and the generates and reaches operators.
C.1 Additional Analysis: Generates
We first highlight simple properties of the generates operator. Many of our results build around the notion of uniform generation, a variant of the generates operator in which a basis generates an agent set in every environment. We define this operator precisely follows.
Definition C.1. Let be a set of learning rules over some basis AB. We say that set uniformly E-generated by Ag, denoted AB FE A, if and only if
VaeA nen A(h) o(h)(h).
(C.1)
Definition C.2. We say basis Ag uniformly generates A, denoted AB += A, if and only if
BESI AB A
(C.2)
We will first show that uniform generation entails generation a particular environment. As a consequence, when prove that certain properties hold of uniform generation, can typically also conclude that the properties hold for generation as well, though there is some subtlcty as to when exactly this implication will allow results about /= to apply directly to Proposition C.1. For any (AB, A) pair, if Ag += A, then for all e E. Ag F A.
Proof of Proposition C.I.
Recall that in the definition of uniform generation. Ag A, we require,
Bisz VAeA Kee A(h) ohh)hh).
(C.3)
Now, contrast this with generates with respect to specific enviromment e,
Biez BeAA new A(h) = (h))
(C.4)
22

---

The only difference in the definitions is that the set of histories quantified over is H in the former, and H A. in the latter.
Since H C H for any choice of environment e, we can conclude that when Equation C.3, it is also the case that Equation C.4 holds, too. Therefore, AB += A = Ap F A for any 0
We next show that the subset relation implies generation. Proposition C.2. Any pair of agent sets (Asmall, Abig) such that Asmall C Abig satisfies
Abig }= Asmall-
(C.5)
Proof of Proposition C.2.
The result follows from the combination of two facts. First, that all agent sets generate themselves. That is, for arbitrary A, we know that A F A, since the trivial set of learning rules,
Σn {a, : h A, Vyeat
(C.6)
that never switches between agents is sufficient to generate the agent set.
Second, observe that removing an agent from the generated set has no effect on the generates operator. That is, let A' A \ A, for fixed but arbitrary À E A. We see that A', since Enr sufficient generate A' too. By inducting over all removals of agents from A, we reach our conclusion.
Next, we establish properties about the sets of learning rules that correspond to the generates operator. Proposition C.3. For any (AB, L, A) such that AB Fy A. holds that
|A| S E]
(C.7)
Proof of Proposition C.3.
We proceed toward contradiction, and assume |A] [Σ]. Then, there is least learning rule a E that corresponds to two or more distinct agents A. Call this element a², and without loss of generality let Al and A2 be two distinct agents that each generated by d² in the sense that,
A A'(h) d' (h),),,
(²hh)= = o'()))),
(C.8)
for every h E H. But, by the distinctness of A and A there must exist history h in which A (h) # A2hh). We now arrive at a contradiction as such a history cannot exist: By Equation C.8, we know that A (h) o (h) = (h) for all h.
We see that the universal learning rules, Σ, is the strongest in the following sense.
Proposition C.4. For any basis AB and agent set A, exactly one of the two following properties hold:
1. The agent basis AB uniformly generates under the set of all learning rules: AB Fz A.
2. There no set of learning rules for which the basis E-uniformly generates the agent set: -xyc AB Fg A.
Proof of Proposition C.4.
The proof follows from the law of excluded middle. That is, for any set of learning rules Σ, either generates A or it does not. If it does generate A, by Lemma B.6 so does Σ. By consequence, does not generate A, neither do any of its subsets.
D
Furthermore, uniform generation is also transitive.
23

---

Theorem C.5. Uniform generates is transitive: For any triple (A ,2,,", if F A² and A2 A3, then A FA.
Proof of Theorem C.5.
Assume A == A and A? }= A². Then, by Proposition C.4 and the definition of the uniform generates operator, we know that
V Ve V hen (²(h) (h)(k))
(C.9)
V V a²(h) (h)(k))
(C.10)
where X and 2 express the set of all learning rules over A and A respectively. By definition of learning rule, d, we rewrite the above follows,
VAPAAVMEHHNNNN 22(h) = A (H),,,
(C.11)
VeeENVeeHHeEN A²(h) = A²()).
(C.12)
Then, consider fixed but arbitrary A E A². We construct learning rule defined over A
as o² : H - A' that induces an equivalent agent as follows. For each history, h E H, by Equation C.12 we know that there is A such that (h) = (h)),, and by Equation C.I1. there is an A such that (2) (h). Then, set a¹ + A such that Ả (h) 12 A² (h). Since h and 13 were chosen arbitrarily, we conclude that
V
A² A (h).
But, by the definition of E, this means there exists learning rule such that Doles A (²(h a (h)(h)).
This is exactly the definition of E-uniform generation, and by Proposition C.4, conclude A FA
Next, we show that a singleton basis only generates itself. Proposition C.6. Any singleton basis, AB {A), only uniformly generates itself.
Proof of Proposition C.6.
Note that generates requires switching between base agents. With only a single agent, there cannot be any switching, and thus, the only agent that can be described as switching amongst the elements of the singleton set AB = (A} the set itself.
C.1.1 Rank and Minimal Bases
As discussed in the paper, one natural reaction to the concept of an agent basis is to ask how we can justify different choices of basis. And, if we cannot, then perhaps the concept of agent basis is disruptive, rather than illuminating. In the main text, we suggest that in many situations, the choice of basis is made the constraints imposed by the problem, such the available memory. However, there are some objective properties of different bases that can help us to evaluate possible choices of suitable basis. For instance, some bases minimal in the sense that they cannot be made smaller while still retaining the same expressive power (that is, while generating the same agent sets). Identifying such minimal sets may be useful, as it is likely that there good reason consider only the most compressed agent bases.
To make these intuitions concrete, we introduce the rank of an agent set. Definition C.3. The rank of an agent set, rank(A), the size of the smallest agent basis that uniformly generates it:
rank(A) = min AApl
S.I.
Ap =
(C.13)
Arch
24

---

For example, the agent set,
A {2 h a0,
(C.14)
a h a1
A²: h + a0 [|] mod 2 = 0,
@1
[h] mod 2 = 1,
},
has rank(A) = 2, since the basis,
AB {A h - ao, Ag h - ath.
uniformly generates A, and there no size-one basis that uniformly generates A by Proposition C.6.
Using the notion of an agent set's rank, we now introduce the concept of a minimal basis. We suggest that minimal bases are particular important, as they contain no redundancy with respect to their expressive power. Concretely, we define minimal basis in two slightly different ways depending whether the basis has finite or infinite rank. In the finite case, we say a basis is minimal there is no basis of lower rank that generates it.
Definition C.4. An agent basis AB with finite rank is said to be minimal just when there is no smaller basis that generates it,
VAycA 1 AB rank(AA)) 2 rank(An))
(C.15)
In the infinite case, as all infinite rank bases will have the same effective size, instead consider notion minimiality based on whether any elements can be removed from the basis without changing its expressive power.
Definition C.S. An agent basis AB with infinite rank is suid to be minimal just when no proper subset of AB uniformly generates AB-
VA,AAB 1=
Ag AB.
(C.16)
Notably, this way of looking at minimal bases will also apply to finite rank agent bases direct consequence the definition of a minimal finite rank basis. However, we still provide both definitions, finite rank basis may not contain subset that generates but there may exist lower rank basis that generates it.
Corollary C.7. As Corollary of Proposition C.2 and Definition C.4, for any minimal agent basis Ag, there is no proper subset of Ag that generates Ag-
Regardless whether an agent basis has finite or infinite rank, we say the basis is a minimal basis of agent set A just when the basis uniformly generates A and the basis is minimal.
Definition C.6. For any A, minimal basis of A is any basis AB that is both (1) minimal, and (2) AB }= A.
A natural question arises as whether the minimal basis of any agent set A is unique. We answer this question in the negative.
Proposition C.8. The minimal basis of a set of agents not necessarily unique.
Proof of Proposition C.8.
To prove the claim, we construct an instance of an agent set with two distinct minimal bases. Let R {ao, a1}, and O {(oo). We consider the agent containing four agents. The first two map every history to dg and #j, respectively, while the second two alternate between do
25

---

and di depending on whether the history is of odd or even length:
A (1 h + do,
(C.17)
A h di
@o Ih mod = 0
12: h +
[k| mod = 1,
A3
h
do
[h] mod
a1 [h] mod = O,
}.
Note that there distinct subsets that each universally generate A:
Ag = (4g.a AEh.
A (11.1111
(C.18)
Next notice that there cannot be singleton basis by Proposition C.6, and thus, both Ag and 0.1 Ag. satisfy (1) (1) = IAg rank(A), and (2) both AB } A. A F..
O
Beyond the lack of redundancy of basis, may also be interested in their expressive power. For instance, if we compare two minimal bases, Ag and Ag. how might we justify which to use? To address this question, we consider another desirable property of basis: universality.
Definition C.7. An agent basis AB is universal if Ap F A.
Clearly, it might be desirable to work with universal basis, as doing so ensures that the set of agents consider in our design space is rich possible. We next show that there is least natural basis that is both minimal and universal.
Proposition C.9. The basis,
A 11:0 A())),
(C.19)
is a minimal universal basis:
1. Ag == A: The basis uniformly generates the set of all agents.
2. Ag is minimal.
Proof of Proposition C.9.
We prove each property separately.
Ag A
First, we show that the basis universal: A } A. Recall that this amounts to showing that,
VAEA VeeAWeeHRENN A(h) = A(hh).
(C.20)
Let A E A and h E H be fixed but arbitrary. Now, let us label the action distribution produced by A(h) as РА())- Let o refer to the last observation contained construct the agent Ag member of Ag. and furthermore, we know that Ag produces the same output as on h. Since both À and ht were chosen arbitrarily, the construction will work for any choice of Á and h, and we conclude that at every history, there exists a basis agent Ag e Ag that produces the same probability distribution over actions as any given agent. Thus, the first property holds. /
(or h = ho 0). Now; Pa(k)- By construction of Ag- this agent is guaranteed to be
Ag is minimal.
26

---

Second, we show that Ag. is a minimal basis of A. Recall that since rank(Ag) = co, the definition of minimal basis means that:
V Aacag AB F A
AB AB-
(C.21)
To do so, fix arbitrary proper subset of AB E (AA)). Notice that since AB is a proper subset, there exists non-emply set Ag such that,
AB AB = Ag.
Now, show that Ag cannot uniformly generate A by constructing agent from Ag. In particular, consider the first element of AB, which, by construction of Ag. is some mapping from O to choice of probability distribution over A. Let refer this agent's output probability distribution over actions as p. Notice that there cannot exist an agent in Ag that chooses p. otherwise Aş would not be a proper subset of Ag. Notice further that the set of all agents, there are infinitely many agents that output p in at least one history. We conclude that AB cannot uniformly generate A, as it does not contain any base element that produces p. The set AB was chosen arbitrarily, and thus the claim holds for any proper subset of Ap. and we conclude.
This completes the proof of both statements.
Corollary C.10. As direct consequence of Proposition C.9, every universal basis has infinite rank.
C.1.2 Orthogonal and Parallel Agent Sets
Drawing inspiration from vector spaces, we introduce notions of orthogonal and parallel agent bases according to the agent sets they generate. Definition C.8. pair of agent bases (Ap AZ)) are orthogonal if any pair (A), ,2)) they each uniformly generate
A A
AB A
(C.22)
satisfy
A 2
(C.23)
Naturally this definition can be modified to account for environment-relative generation (F), or to be defined with respect to a particular set of learning rules in which case two bases are orthogonal with respect to the learning rule set just when they generate different agent sets under the given learning rules. As with the variants of the two operators, we believe the details of such formalisms are easy to produce.
few properties hold of any pair of orthogonal bases. Proposition C.11. If two bases Ab. Ag are orthogonal, then the following properties hold:
1. A n A = O.
2. Neither AA nor A2 are universal.
Proof of Proposition C.11.
We prove each property independently.
4/4 A
We proceed toward contradiction. That is, suppose that both A orthogonal to A2. and that Al n A3 # 0. Then, by the latter property, there at least one agent that is an element of
27

---

both bases. Call this agent Ag. It follows that the set Ag (Ag) is a subset of both Ag and A By Proposition C.2, it follows that A |= Aü and Ag }= Ag But this contradicts the fact that Ag is orthogonal to Ag. and we conclude. /
2. Neither AB nor Ag are universal.
We again proceed toward contradiction. Suppose without loss of generality that A is universal. Then, we know A }= A. Now, we consider two cases: either A generates some non-empty set, A2, or does not generate any sets. If generates a set A2, then we arrive at contradiction A n A # 0, which violates the definition of orthogonal bases. If if does not generate set, this violates the definition of a basis, as any basis is by construction non-empty, and we know that containing even single element is sufficient to generate at least one agent set by Proposition C.6. Therefore, in either the two cases, we arrive at contradiction, and thus conclude the argument. /
This concludes the proof of each statement.
Corollary C.12. For any non-universal agent basis AB, there exists orthogonal agent basis, Ag.
Conversely, two agent bases A/r A are parallel just when they generate the agent sets.
Definition C.9. A pair of agent bases (Ap, Alg are parallel for every agent set A, A } A if and only if A A.
Proposition C.13. two bases Ap. Ag are parallel, then the following properties hold:
Both AB }= Ag and A F A
2. rank(AA) )
3. AB is universal if and only if Ag is universal.
Proof of Proposition C.13.
We prove each property separately.
1. Both AB -= AB and A7 + Ag.
The claim follows directly from the definition of parallel bases. An agent set A is uniformly generated by Ag if and only it is uniformly generated by AG. Since by Proposition C.2 we know both A F Ag and A }= Ag. we conclude that both Ag =A} and A - Ag. /
rank(A)) (A)) = (an)
Recall that the definition of rank refers the size of the smallest basis that uniformly generates it,
rank(A) min |ABl
s.t.
AB A A.
ApcA
Now, note that by property (1.) of the proposition, both sets uniformly generate each other. Therefore, we know that
ran)(AA)) s min 1A
(ank(A))) s min |
since the smallest set that generates each basis is larger than the basis itself, the other basis.
28

---

3. Ag is universal if and only if Ag is universal.
The claim again follows by combining the definitions of universality and parallel: If A is universal, then by definition of parallel bases, Ag must uniformly generate all the same agent sets including A, and therefore tg is universal, too. Now, if zo is not universal, then it does not uniformly generate A. By the definition of parallel bases, we conclude Ag does not generate A as well. Both directions hold for each labeling of the two bases without loss of generality, and we conclude.
This completes the argument for each property, and we conclude.
C.2 Analysis: Reaches
We now establish other properties of the reaches operator. Several of these results are based on third modality the reaches operator: always reaches, in which an agent eventually reaches an agent basis in all histories realizable in given environment. We define this precisely follows.
Definition C.10. We say agent À E A always reaches Ag, denoted À Dw AB. if and only if
Y REA " Y MEA, A(hh h')
(C.24)
The nested quantifiers allows the agent to become equivalent to different base behaviors depending on the evolution of the interaction stream. For example, in an environment that flips coin to determine whether Abeads or Auils optimal, the might output Thaads indefinitely if the coin is heads, but Angil otherwise. In this case, such agent will still always reach the basis AB {A h + &eads Ag.
+ ). Notice that we here make use of the notation, F which refers to all history suffixes of length greater, defined precisely
1:00 k
(h H4 11' 1]
(C.25)
We first show that the always reaches operator implies sometimes reaches. Proposition C.14. If D A. then nhs A.
Proof of Proposition C.14.
Assume À Ova A. That is, expanding the definition of always reaches, we assume
VeefFraN, V e AAecA V "ee,, A(hh h') = Ag(hh')))
(C.26)
Further recall the definition of can reach À me AB follows
3 A Y Meek A(hh' AB(hh').
(C.27)
Then, the claim follows quite naturally: pick any realizable history h E H. By our initial assumption that A Dv's A, follows (by Equation C.26) that there a time and realizable history suffix ht for which
BAgeAs V Men, A(hhhh) = Ag(hh
By construction of 11h² Hy. we know h/ is realizable history. Therefore, there exists realizable history, htht" for which AAgeAy Meeri, ((hh')) = (h' It') holds. this is exactly the definition of can reach, and therefore, we conclude the argument.
Next, we highlight the fact that every agent in a basis also reaches that basis. Proposition C.15. For any agent set A, it holds that À DV A for every À e A.
Proof of Proposition C.15.
29

---

The proposition is straightforward, any A e A will be equivalent to itself in behavior for all histories.
Corollary C.16. As a corollary of Proposition C.15, any pair of agent sets (Asmall, Abig) where Asmall S Abig satisfies
A D Abig.
(C.28)
We further show that, unlike sometimes and never reaches, always reaches is transitive. Proposition C.17. Always reaches is transitive.
Proof of Proposition C.17.
We proceed by assuming that both V VAEAA A Dut A² and VaPcAa A2 DMAs A and show that it must follow that VAAA A DMis A3. To do so, pick a fixed but arbitrary A', and expand A D+6 A as
NeAR Bee Het, (hh"')) whhh)))
Now, consider for any realizable history hh" we know that the corresponding A² that pro- duces the same action distribution as A also satisfies A2 DMás A Thus, there must exist some time at which, any realizable history h4. will satisfy ErAC "ieA A2 h') A (hh H
But then there exists time (f), that ensures every A E A² will have corresponding A A with the same action distribution at all subsequent realizable histories. Therefore,
hc7 PEN V cT ExPEARV NeM, W'hh"() = A2
Betas =A-(RCR())
Thus, rewriting,
Y NeeABrak V
MeA, A'(hh"h) 13hhp)))
But this is precisely the definition of always reaches, and thus conclude.
Next, we show basic properties of the set of all agents: uniformly generates all agent sets, and it is always reached by all agents.
Proposition C.18. For any e, the set of all agents & (1) uniformly generates all other agent sets, and (ii) is always reached by all agents:
(1) VACA A F A,
(ii) ViER à Dri A.
(C.29)
Proof of Proposition C.18.
(i) AC
The property holds as straightforward consequence of Proposition C.2: Since any set A is subset of A, it follows that & |= A. /
(ï). Meaa A DMis A
The property holds as a straightforward consequence of Proposition C.15: Since every agent satisfies A e A, follows that À nis A. /
This concludes the argument of both statements.
30

---

C.3 Figure: Set Relations in CRL
Finally, in Figure 3 we present visual depicting the relations in CRL between an agent basis Ag, an agent set it generates A, and the three agent sets corresponding to those agents in A that (i) sometimes, (ii) never, (ii) always reach the basis. First, we highlight that we visualize AB as subset of A since we define AB C A in CRL (Definition 4.2). However, there can exist triples (AB, A, e) such that AB A, but that AB not subset of A. Such cases are slightly peculiar, since it means that the basis contains agents that cannot be expressed by the agent set A. Such cases are not line with our definition of CRL., so we instead opt to visualize Ag as subset of A. Next, notice that the basis is subset of both the agents that always reach the basis and the agents that sometimes reach the basis-this follows directly from the combination of Proposition C. 14 and point (3.) of Theorem 4.3. By similar reasoning from Proposition C.14, we know that the set of agents that always reaches Ag is a subset of the agents that sometimes reach the basis. Further, since sometimes and never reaches negations of one another (Remark 3.2), observe that the two sets disjoint, and together comprise the entirety A. Lastly, we know that the set of optimal agents, A', contains only agents that never reach the basis, and thus the set A is disjoint from AB and the set of agents that sometimes reach AB-
{1 A A: 1 res AB}
{1 A : Dw AB}
AB
A
A'
{h A : Mps AB}
Figure 3: A depiction of the division of a set of agents A relative to basis Ap through the reaches operator in CRL.
31


Reviews:
[{"review_id": "hZJ7zbBBNO", "reviewer": "Reviewer_z8Jz", "summary": "In the paper the authors propose a formal framework for reasoning about continual reinforcement learning problems. To this end they introduce mathematical definitions for environments and agents which serve as a basis for defining the general reinforcement learning setting as well as the continual setting. In particular, the authors tie the problem of continual learning to the learning progress an agent makes and two operators describing its limitting learning behaviour. Finally, they provide two examples and derive sevaral characteristics of the proposed operators.", "questions": "-", "limitations": "-", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem of continual RL is most certainly relevant to the community and will arguably become more prominent as real-world agents adapting throughout their deployment become more common-place. To my knowledge the proposed formalism is original in its attempt to characterise this setting formally.\n\nOverall I found the framework sound and its description easy to follow. I agree with the authors that such a formalism has the potential to open up new perspectives on and analysis of (long-term) learning behaviour of agents.", "weaknesses": "Throughout the paper the terms \"agent\" and \"behaviour\" are used almost interchangeably. However, a formal definition of behaviours is missing, making it somewhat unclear whether or not the two terms are actually meant to be equivalent. If so, the statement \"we can understand every agent as implicitly searching over a set of behaviors\" needs clarification. If not, I would encourage the authors to formally define what a \"behaviour\" constitutes.\n\nA related issue is the separation of agents and their learning rules. Arguably, an agent parameterised by a recurrent network is a continual learner as it changes its \"behaviour\" (in the sense of the one-step policy) based on the history giving rise to its internal state. However, under the provided definition such an agent would not be considered a continual learner unless it updates its weights.\n\nFinally, the paper would benefit from a more in-depth discussion of how previous approaches to continual RL compare to the proposed framework or can be embedded into it. Similarly, the authors mention several avenues for future research such as the examination of catastrophic forgetting - it might be interesting to include at least a characterisation of these problems in the new framework to inspire future work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we would like to thank the reviewer for their time and energy in reading and reviewing our paper. We address the reviewer’s primary questions and concerns below, and will plan to update the paper in line with the reviewer’s suggestions.\n\n> Definition of agent vs. behaviour…\n\nThis is a great point, and one we will be sure to attend to carefully in the paper. We use the term “behaviour” early on in (and throughout) the paper to appeal to intuition before we have defined “agent” more precisely in Definition 2.4. The reason for this choice is that we find the phrase, “we can understand every agent as implicitly searching over a set of behaviors” easier to grasp than “we can understand every agent as implicitly searching over another set of agents”. In light of your comment, we will revise the paper to remove references to “behavior” entirely, or make it clear in some cases when we are using the term in a colloquial way to appeal to intuition (and that it will be replaced by the more precise “agent” after Def. 2.4). We hope this helps.\n\n> A related issue is the separation of agents and their learning rules. Arguably, an agent parameterised by a recurrent network is a continual learner as it changes its \"behaviour\" (in the sense of the one-step policy) based on the history giving rise to its internal state. However, under the provided definition such an agent would not be considered a continual learner unless it updates its weights.\n\nThe reviewer makes an excellent point, and one that was at the heart of a lot of the puzzles we thought about as part of this work. In short, as per Theorem 5.1.2, depending on the basis, agents can be understood as learning or not. In an MDP, for instance, do we want to consider a fixed stationary policy as learning, simply because it reacts to a change in the MDP state? Or should we only consider explicit _updates_ to the policy as learning (or something else)? This tension is at the heart of our view of continual learning, and one we fully embrace by allowing the choice of basis to characterize what it means for an agent to learn: an agent is a continual learner with respect to a basis if the agent keeps switching between basis elements forever. We discuss the choice of basis in response to one of the questions of reviewer 9sbq, which addresses a similar point. In the case of the neural net described by the reviewer, if the agent can be understood as switching to a new basis element in light of experience, then the neural net is viewed as learning (that is, an agent updating its weights its not, own its own, sufficient to produce a learning agent—it must be that the agent actually updates its behavior in response to experience in the relevant way; and this could happen due to the recurrent state update, or due to weight change).\n\n> Finally, the paper would benefit from a more in-depth discussion of how previous approaches to continual RL compare to the proposed framework or can be embedded into it. Similarly, the authors mention several avenues for future research such as the examination of catastrophic forgetting - it might be interesting to include at least a characterisation of these problems in the new framework to inspire future work.\n\nThese are both very good suggestions, thanks! We will add two pieces of discussion to the paper. First, as mentioned in the reply to all reviewers (\"[Overall Response]\"), we will add an in-depth discussion about the relationship between our definition of CRL and prior approaches to thinking about CRL, with an emphasis on the work by Ring and the recent CRL survey by Khetarpal et al. Succinctly, the work by Ring emphasizes the generality of the environment model and the reward function, while the survey by Khetarpal et al. focuses explicitly on non-stationarity, similar to work on multi-task RL. Our definition will directly accommodate and extend both of these views, and we are happy to include this discussion in the paper. Second, we can expand on connections to central empirical phenomena like catastrophic forgetting and in-context learning. For example, in-context learning might be fully characterized in terms of specific kinds of learning rules and agent bases (our definitions 3.1 and 3.2), where the base elements themselves are capable of more sophisticated learning. Plasticity loss can be captured in terms of changes to the capacity of an agent over time, as discussed in the general response— we believe these tools may help open new lines of study surrounding plasticity and related concepts. While these lines of research are still developing, we believe there is new opportunity raised to model and analyze these important empirical phenomena using the formal language from our work.\n"}, {"review_id": "aHxxsqJGtU", "reviewer": "Reviewer_9sbq", "summary": "This is an ambitious paper.  The paper notes that the problem of \"Continual Reinforcement Learning\" lacks a rigorous definition and seeks to provide one.  It mathematically defines the reinforcement learning problem and then explores the conditions in which an instance of the RL problem is a CRL problem.\n\nThe legwork is done through the new \"generates\" and \"reaches\" operators.\n\nThe \"generates\" operator accepts two arguments: 1. a set of \"basis\" agents, and 2. a particular agent (which may not be in that set, but is exhibits some combined behavior of the basis agents).  It returns boolean truth value.  The \"generates\" operator expresses if there exists a learning rule that can search over \"basis\" agents (with respect to an environment / historical observations) and find a combination of them that is equivalent to the particular agent in the argument. This function is also undecidable in general.\n\nLoosely, the \"reaches\" operator (wrt an environment) accepts two arguments: 1. a particular agent 2. a set of \"basis\" agents It returns a boolean truth value.  It returns True when an agent's behavior settles on an element in the basis set.  The authors actually define a more precise \"sometimes reaches\" and \"never reaches\" operator. This is also undecidable.\n\nA learned agent will always choose a behavior equivalent to some basis agent in the context of the environment and history.\n\nUsing these formalisms, a CRL agent is one that never reaches an agent basis, and a CRL problem is one where the best agent is a CRL agent. \n\nNotably, a problem is a CRL problem depending on the choice of basis.\n\nThe paper performs mathematical analysis on these operators, relates them to two example instances of CRL, and provides a thoughtful discussion for new questions that can be asked about agent basis sets.\n", "questions": "On line 47 the authors explicitly call out that the set A and O are countable.  Does this imply that some other (non-numeric - i.e. non-ℝ) sets may be uncountable in this definition?\n\nI think the order of appendix A and appendix B should be switched. Provide the notation first. (The table was very helpful in reviewing).\n\n\nI became confused when I first read Theorem 3.1. Particularly when the selected agent was not an element of the agent basis. In hindsight it makes sense that the new agent is a (linear?) combination behaviors in the agent basis set, but I think the paper could make that more clear. It wasn't intuitive what \"switches\" meant to me. Or that lambda(h) in Figure 1 was a combination of the basis agents conditioned on history. (At first I thought the learning rule was just choosing an element of the basis set).\n\nIn Theorem 3.1 are the infinite choices of basis countable?\n\nIf a problem's status as CRL or not depends on the choice of basis, and there are an infinite choices for the basis, then is this framework all that useful for thinking about problems?\n\nTheorem 5.1.2 suggests that it is possible to reduce any CRL problem to an RL problem via a change of basis.\n\nIs it possible to reduce any CRL problem to a RL problem by finding a function that changes the basis? Are there problems where such a mapping does not exist?\n\nHave you formalized any of the proofs into a proof assistant like Lean? I took a peek at the appendix, but I simply don't have the time to verify these proofs. Being able to point to an automatically checked proof in each theorem would greatly increase the quality of the paper.", "limitations": "An optimal CRL agent could be difficult to rectify with the alignment problem. In contrast, it might be the case that deciding if a CRL agent will remain aligned with its creators is undecidable. That question is worth exploring.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The informal definition \"An RL problem is an instance of CRL is the best agents never stop learning\" is intuitive and clear.\n\nI always appreciate explicit definitions for notation. (although defining logical negation, and the quantifiers might not be necessary in a conference paper). I type checked several of the equations and everything seems to work out nicely. The theory gives a good feel for how someone might implement a framework for exploring agents in the language of this theory using a strongly typed language.\n\nThe paper gives explicit examples and experiments demonstrating intuitive properties of this theory in the setting of Q-learning and finite Markov decision processes. As well as a more complex example in continual supervised learning.\n\nThe paper proves several basic properties of the new reaches and generates operators. I have not checked the proofs for correctness, but I also don't see any obvious problems.\n\nSection 5 made me delete a lot of my questions because it answered them. The idea of exploring choices of the basis is mathematically interesting.\n\nThe paper raises more questions than it answers.\n", "weaknesses": "The abstract is terse - problematically so. Even if this succeeds at being a theoretically sound definition of continual reinforcement learning, I think it is important to elaborate at least a little bit more. Note this is the main reason I'm rating this a 5 / 10. Given a better abstract I think this is a 7/10, but I think it is critical to give a better overview to the researchers' attention you are competing for.\n\nA 9 page paper with a 20 page appendix full of proofs may be better suited for a journal.\n\nThe paper raises more questions than it answers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we would like to thank the reviewer for their time and energy in reading and reviewing our paper. We recognize the reviewer spent a lot of time understanding and commenting on our work, and we appreciate it. Below, we respond to each in point detail, and we are happy to update the paper to reflect the reviewer’s suggestions, and to continue the discussion.\n\n> The abstract is terse - problematically so…\n\nWe had originally thought a simple abstract would be a good choice, but in hindsight, we completely agree with the reviewer, and will modify our abstract accordingly. We will plan to change our abstract to the text provided in the reply to all reviewers (\"[Overall Response]\"), and are open to suggestions for improvement.\n\n> Swap Appendix A and B\n\nThis is a great idea. We will swap the order of these two appendices.\n\n> I became confused when I first read Theorem 3.1. Particularly when the selected agent was not an element of the agent basis..\n\nThis is helpful feedback. We can spend time and improve the exposition of this result.\n\n> In Theorem 3.1 are the infinite choices of basis countable?\n\nGood question! The proof strategy of the result involves constructing a countable sequence of basis sets (where each of the sets will generate the original agent in the environment). Thus, the proof strategy only *requires* countably infinitely many bases. However, we suspect that there are augmentations to the proof strategy that also make use of uncountably infinitely many bases, so the argument can likely go through in both cases.\n\n> If a problem's status as CRL or not depends on the choice of basis, and there are an infinite choices for the basis, then is this framework all that useful for thinking about problems?\n\nThis is a critical point, and one we have focused on in developing this work. We believe that this point is a feature of the definition, rather than a bug. To see why, we will plan to include the following text in Section 5 following the statement of Theorem 5.\n\n_It is reasonable to ask if the fact that our definition of CRL is basis-dependant renders it vacuous. We argue that this is not the case for two reasons. First, we conjecture that any definition of continual learning that involves concepts like “learning” and “convergence” will have to sit on top of some reference object whose choice is arbitrary. Second, and more important, even though the mathematical construction allows for an easy change of basis, in practice the choice of basis is constrained by considerations like the availability of computational resources. It is often the case that the domain or problem of interest provides obvious choices of bases, or imposes constraints that force us as designers to restrict attention to a space of plausible bases. For example, as discussed earlier, a choice of neural network architecture might comprise a basis—any assignment of weights is an element of the basis, and the learning rule $\\sigma$ is a mechanism for updating the active element of the basis (the parameters) in light of experience. In this case, the number of parameters of the network is constrained by what we can actually build. Further, we can think of the learning rule $\\sigma$ as something like stochastic gradient descent, rather than a rule that can search through the basis in an unconstrained way. In this sense, the basis is not arbitrary, nor is the learning rule. We as designers choose a class of functions to act as the relevant representations of a mapping from observations to actions, often limited by resource constraints on memory or compute. Then, we use specific learning rules that have been carefully designed to react to experience in a desirable way—for instance, stochastic gradient descent updates the current choice of basis in the direction that would most improve performance. For these reasons, the choice of basis is not arbitrary, but instead reflects the ingredients involved in the design of agents as well as the constraints necessarily imposed by the environment._\n\nWe hope the above answers your question, but we are happy to discuss this point further.\n\n> Is it possible to reduce any CRL problem to a RL problem by finding a function that changes the basis? Are there problems where such a mapping does not exist?\n\nThis is a really interesting question, and we suspect that crafting a well-formed answer is a great direction to explore further. We do know that, by Theorem 5.1.2, if we were to include all of the optimal agents in the agent basis in question, then the problem is no longer CRL (since there is now an optimal agent that reaches the basis). However, finding a function to construct the optimal agents in this setting is not necessarily feasible. There might exist problems where, depending on the constraints imposed on the basis or set of learning rules, finding this function is either impossible or feasible. Clarifying such settings would be an interesting direction to pursue further.\n\n> An optimal CRL agent could be difficult to rectify with the alignment problem. In contrast, it might be the case that deciding if a CRL agent will remain aligned with its creators is undecidable. That question is worth exploring.\n\nIn our view, most agents we as a community build and deploy will be facing a CRL problem, rather than a more traditional RL problem (i.e. those with a fixed solution). As a result, we believe it is an important open question how to frame safety and alignment research around CRL—we take this to be an important line of future work. In our view, it is a positive aspect of the work that it opens new lines of research (that are perhaps more well calibrated to the actual problems facing agents we design) surrounding safety.\n\n> Have you formalized any of the proofs into a proof assistant like Lean?\n\nWe have not formalised the proofs into a proof assistant.\n"}, {"review_id": "0bIyfIX1LE", "reviewer": "Reviewer_oHpE", "summary": "The authors propose a new definition of continual reinforcement learning where an optimal continual learning agent will not converge to a fixed policy. This is formalized through the generate operator, which defines the \"searching\" between different policies; and the reach operator, which defines whether the agent will stop searching.", "questions": "1. Can you elaborate on how this formal definition of continual learning can address practical problems such as plasticity loss, in-context learning, and catastrophic learning as mentioned in the Discussion section?", "limitations": "The authors mention the limitations implicitly as future work in the discussion section. Essentially, since this paper is almost purely theoretical, they treat the lack of empirical study as future work or limitation.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. This paper provides a unique definition of the continual learning problem, which is formalized by their mathematical framework.\n2. Based on their framework, the authors were able to prove a number of interesting theorems.", "weaknesses": "1. It is not immediately obvious how this definition can inspire new learning algorithms.\n2. The underlying concept that an optimal learning agent should not converge is not surprising. The author also mentioned that it's an \"unsurprising conclusion that it is better to track than converge\" for their toy non-stationary environment.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we would like to thank the reviewer for their time and energy in reading and reviewing our paper. Below, we respond to each in point detail, and we are happy to update the paper to reflect the reviewer’s suggestions, and to continue the discussion.\n\n> It is not immediately obvious how this definition can inspire new learning algorithms.\n\nThis is a valid point. Our view is that this paper is about clarifying what problem we are actually studying. Doing so will remove the ambiguity that has surrounded continual learning, and allow us as a community to ensure we are studying the right problem. Further, this clarity provides new language to talk about agents and continual learning more carefully. The promise, then, is that exploration of these new tools can yield new perspectives on the design of algorithms. For instance, our work emphasizes the view that an agent can be understood as a choice of a learning rule (definition 3.2) and a choice of agent basis (definition 3.1). These two objects provide a new abstraction on the components of an agent. Furthermore, this abstraction may yield new kinds of learning rules that can inform algorithm design. As an example, we might consider learning rules that are guaranteed to produce a continual learning agent of the kind defined by definition 4.1—what are the necessary and sufficient conditions of such a learning rule? Answering this question will give a path toward defining algorithms that are guaranteed to produce continual learning agents (which, as Dohare et al. showed recently, is not true of many standard learning rules). Or, as we explore briefly in Appendix C, we might consider learning rules that capture certain intuitive families of agents, such as a model-based learning rule. Combined with tools for thinking about continual learning, we could imagine delineating between continual model-based agents and regular model-based agents; such a distinction could give rise to new algorithmic principles and other algorithmic primitives, but working out the precise details is beyond the scope of the present submission.\n\n> The underlying concept that an optimal learning agent should not converge is not surprising.\n\nWe agree, and we take the intuitive appeal of the statement “an optimal learning agent should not converge”, as a positive characteristic of our definition. Our goal is to make this intuition mathematically precise, which we believe we have done.\n\n\n> Q:  Can you elaborate on how this formal definition of continual learning can address practical problems such as plasticity loss, in-context learning, and catastrophic learning as mentioned in the Discussion section?\n\nThis is a great question, and our reasoning will be similar to our response to the first point above. Now that we have a precise mathematical language for talking about continual learning agents, we believe we are well positioned to unpack and examine the kinds of phenomena that regularly arise in continual learning. We provide a similar answer in the response to all reviewers (\"[Overall Response]\"), but for simplicity, here are our thoughts. As an example, let’s consider plasticity loss. We suggest that plasticity loss can be modeled precisely using the conceptual tools we develop: _plasticity_ is the fraction of an agent’s corresponding agent basis that remains reachable to the agent over time, and plasticity _loss_ is any reduction of this number. We foresee pathways to both diagnose agents from a new perspective, and to design algorithms based around this measure; for example, by developing learning rules (def 3.2) that provably maintain plasticity. This unlocks a new point of emphasis from designing learning algorithms that is grounded in a rich mathematical toolkit. Or, we can understand in-context learning precisely in terms of the kinds of agent bases that agents search through—certain kinds of bases might be sufficiently rich to be capable of in-context learning, while others are not. Therefore, in the same way that we precisely define a continual learning agent in definition 4.1, we might unlock a precise definition of an in-context learning agent, at which point we can study the necessary and sufficient conditions required of such an agent. This is one example, but the same kind of analysis is possible for a variety of agent-centric properties such as plasticity loss and catastrophic forgetting.\n"}, {"review_id": "lGdko8oipk", "reviewer": "Reviewer_EKup", "summary": "- This paper lays out a foundation for continual reinforcement learning (CLR) from the ground up—establishing definitions for the purpose of building towards a technical definition of CRL itself, proving various properties of CRL, and through employing simple CRL examples, demonstrating some of these properties.", "questions": "- Do we really want agents that will adapt their policy forever? Or are the environments we care about simply non-stationary, i.e. because the world changes, and the agent is required to learn more about the environment in order to continue to act optimally? Maybe the policy (in some high-level sense) should remain the same, and it is the world model that should be adapted? E.g. suppose the expressed behavior of the agent policy can be boiled down to “helping humans”, and this policy is fixed, given the agents current understanding of the world as context. Perhaps only this context needs to be updated, i.e. as the world changes, and/or the agent learns more about the existing world. This seems to fit within the proposed framework, if we consider the inferred world model as part of the agent. And while it does seem likely that the discovery of new contexts would require updating the policy, it still appears to me to be beneficial to disentangle these aspects explicitly. What are the authors' thoughts on this?\n", "limitations": "- The authors have discussed the limitations thoroughly, and I have listed them above as a strength as there are many directions ripe for future work.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The writing is exceptionally clear and precise.\n- The framework is well thought-out; the definitions are clear and useful, and the framework as a whole is both technical and intuitive. Importantly the provided definition of CRL seems to get at the root of what researchers have always vaguely meant by CRL.\n- There is a rich foundation set for future work (e.g. exploring “connections between our formalism of continual learning and some of the phenomena at the heart of recent empirical continual learning studies, such as plasticity loss, in-context learning, and catastrophic forgetting”; line 364). ", "weaknesses": "- I understand the appeal of a short abstract (i.e. it is to the point, and (albeit somewhat pompously) implies some special finality or importance to the contributions in the work), but the resolution of the abstract, for good reason, usually sits between the resolution of the title and the paper itself. The abstract in this case does not provide much more information than the title, so any reader that wants a quick overview of the paper must read the paper itself, defeating the purpose of the abstract. I suggest the authors to reconsider employing such a short abstract.\n- I feel that the paper could have developed more connections to previous literature, performed more experiments building off of this framework, etc., i.e. more validation for why we should care about this framework. Better (nonstationary) environments to evaluate agents on? Agent structures? Assessment of how well current methods fit into/exploit elements of this framework? The framework is nice, but it would be useful to see how it can situated into current literature, either by retroactively analyzing current agents/environments w.r.t. this framework, or designing new agents/environments from the principles this framework provides.\n- Maybe more real-world examples of changing environments? Or where we want the behavior to change in the same environment (but then we just have an oscillating agent…). Something about the environment changing (or being better understood over time) is fundamental to continual RL)\n- It took me a number of readings to understand agent bases; i.e. the relationship between $\\Lambda$ and $\\Lambda_B$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we would like to thank the reviewer for their time and energy in reading and reviewing our paper. We address the reviewer’s primary questions and concerns below, and will plan to update the paper in line with the reviewer’s suggestions.\n\n> The abstract in this case does not provide much more information than the title, so any reader that wants a quick overview of the paper must read the paper itself, defeating the purpose of the abstract. I suggest the authors to reconsider employing such a short abstract.\n\nWe had originally thought a simple abstract would be a good choice, but we hear the reviewers' suggestion, and will modify it accordingly. We will plan to change our abstract to the one listed in the rebuttal comment provided to all reviewers (see \"[Overall Response]\" above). We are happy to make any further changes based on your feedback.\n\n> I feel that the paper could have developed more connections to previous literature, \n\nThis is a valid point, thanks! We have two reactions:\n\nFirst, in light of this suggestion, we will include additional text discussing explicit connections with previous approaches to continual reinforcement learning, with an emphasis on the work by Ring and the recent continual RL survey by Khetarpal et al. Succinctly, the work by Ring emphasizes the generality of the environment model and the reward function (which we also adopt), while the survey by Khetarpal et al. focuses explicitly on non-stationary MDPs, similar to typical work on multi-task RL (as in work by Brunskill and Li, for instance). Our definition directly accommodates and extends both of these views, and we are happy to include discussion on this topic in the paper.\n\nSecond, one of the primary goals of this paper is to promote a change of mindset—popular thinking in RL tends to view the learning problem as the search for one policy (typically, the optimal policy of an MDP). However, in some cases it is better to think of learning as endless adaptation. We suspect this change in perspective will be increasingly important as agents are deployed in the real world, which is notoriously messy and changes regularly. While this shift in mindset is not new, we do believe we offer a concrete way to conceptualize of this change in perspective that can help promote new RL research aligned with the problem facing agents we are building today.\n\n> …performed more experiments building off of this framework, etc., i.e. more validation for why we should care about this framework. Better (nonstationary) environments to evaluate agents on? Agent structures?\n\nRegarding additional validation, evaluation, and environments: we agree with the spirit of this point, and intend to carry out further work motivated by the definition. However, we do believe that the essence of this paper is about carefully defining the problem, and that further evaluation of the kind suggested is best deferred for follow-up work to give it the care and space it deserves.\n\n> Q: Do we really want agents that will adapt their policy forever? Or are the environments we care about simply non-stationary, i.e. because the world changes, and the agent is required to learn more about the environment in order to continue to act optimally?\n\nThis is another great point, and one we explored in depth as part of this work. We believe it is an open question as to whether the two concepts (policy adaptation vs. learning more about the environment) are different, deeply connected, or the actually same concept just viewed from different lenses. Roughly, we can see that an agent that must learn more about its environment to act optimally but does not ever adapt its policy is a peculiar case, and one that we suggest should not be viewed as continual learning (that is, when the agent can be optimal while _never_ updating its policy). We suggest there is a deep connection between the two views, and are actively exploring this connection in follow up work. We are happy to comment on their connections in the discussion section of the paper, and to discuss this further."}, {"review_id": "rhCfbck6Oj", "reviewer": "Reviewer_DFWz", "summary": "The paper proposes a mathematical formulation for the problem of continual reinforcement learning in an infinite horizon setting.", "questions": "No.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The authors propose a new mathematical formalism for continual RL.\n2. The paper can be of interest to mathematically inclined readers and could potentially lead to theoretical results in continual reinforcement learning.\n", "weaknesses": "1. Abstract: there already are foundations for CRL. You cited a survey paper [16] and multiple other existing works. As unconventional as it is, I wouldn’t be against a short abstract, but I do not believe the current one will do.\n2. Missed important opportunities to connect your formalism with existing (continual) RL. E.g. eq 2.1 states an infinite horizon, which is required for example in Theorem 3.1, but the very standard “infinite horizon” vocabulary never appears. I think the paper is not connected enough to existing (continual) RL literature.\n3. Generally, I’m not convinced by motivations. The paper says it is important, but I did not really see a convincing motivation for abstracting the problem of continual RL. The theorems provide results that can be conveyed in significantly easier ways with existing formulations: e.g. non commutativity in thm 5.2 signifies that in continual RL, some policy transitions cannot be “unlearnt” in some settings. The formalism incurs a very significant overhead over such high level language – I believe that the authors can improve the motivations to justify why their formalism is worth it.\n\n\n**Typos and suggestions:**\n1. L10: we instead of We\n2. L41: I would use $\\mathcal{Z}$ instead of $\\mathcal{X}$ so it flows better in the following sentence.\n3. L84: phrasing “instead opt for simply the bounded…”\n4. L93: did you mean the sum of rewards to start at index 0 ? or t+1, t+2, etc.\n5. L95: I know it got absorbed into v, but I would still prepend this line with “Given <initial conditions> $h_0$, any tuple…” since your work aims to formalise rigorously the problem.\n6. “We use as if in the sense of the positive economists” this is terminology that should be defined in the paper.\n7. L334: “generates is commutative” -> are\n8. L338: I recommend not defining objects used in a main body theorem in the appendix. \n9. I believe that the insights, as stated in the conclusion, are trivial; perhaps “insight” isn’t the word that should be used (using the Cambridge dictionary definition of “insight” “ a clear, deep, and sometimes sudden understanding of a complicated problem or situation” – I do not believe the idea for example that agents in CRL either can or cannot find a set of policies/behaviours is insightful).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we would like to thank the reviewer for their time and energy in reading and reviewing our paper. We address the reviewer’s primary questions and concerns below, and will plan to update the paper in line with the reviewer’s suggestions.\n\n> Abstract: there already are foundations for CRL. You cited a survey paper [16] and multiple other existing works. As unconventional as it is, I wouldn’t be against a short abstract, but I do not believe the current one will do.\n\nThis is a great point, and we are happy to extend our abstract in light of the feedback. Our proposed abstract draft is provided in the reply to all reviewers (\"[Overall Response]\")\n\n> Missed important opportunities to connect your formalism with existing (continual) RL. E.g. eq 2.1 states an infinite horizon, which is required for example in Theorem 3.1, but the very standard “infinite horizon” vocabulary never appears. I think the paper is not connected enough to existing (continual) RL literature.\n\nWe agree, and recognize the importance of discussing the relationship between our formalism and prior approaches to continual RL. We will include a discussion that elucidates these relationships further, with a focus on the thesis by Ring and the recent survey by Khetarpal et al. Further details of this relationship are mentioned in the \"[Overall Response]\" to all reviewers.\n\n> Generally, I’m not convinced by motivations. The paper says it is important, but I did not really see a convincing motivation for abstracting the problem of continual RL... I believe that the authors can improve the motivations to justify why their formalism is worth it.\n\nWe believe that precise definitions are essential for clarity in science. For example, prior to the discovery of pseudo-randomness, much work in theoretical computer science relied on ad-hoc heuristics for producing random sequences to the detriment of the effectiveness of these approaches. Then, a series of papers carefully defined what it would mean for a sequence to be pseudo-random (for instance, in “The definition of random sequences” by P. Martin-Lof, and “Theory and applications of trapdoor functions” by Yao). On Yao’s view, a pseudo-random sequence is one that a bounded adversary cannot distinguish from truly random. Achieving this clarity allowed for pseudo-random number generators to be developed, and for the community to direct its research at the right concepts, and toward the right objectives. In our view, continual reinforcement learning is at a similar stage in its scientific development to pseudo-randomness in its infancy: we lack precise definitions for what, exactly, it is we are conceptualizing. Some people think of non-stationarity, others think of computational constraints, while others think of multi-task learning and transfer. Our goal in developing a single abstract definition is to encompass all of these views as special cases, and the point of formalizing it is to remove any ambiguity in the use of terms like “continual learning”, or “continual learning agent”. We can include more of this motivation in the paper, and are happy to discuss further.\n\n> I believe that the insights, as stated in the conclusion, are trivial; perhaps “insight” isn’t the word that should be used… I do not believe the idea for example that agents in CRL either can or cannot find a set of policies/behaviours is insightful.\n\nThanks for the feedback here, and we are happy to consider alternative words to replace “insight”. However, we would like to clarify one point, and justify another. First, to clarify: the second insight does not state an agent in CRL can or cannot find a set of policies. This does not reflect the semantics of Remark 3.2. The remark says that _every_ agent can be classified into exactly one of two families: (1) the agent eventually stops its search over its corresponding basis, or (2) searches forever. This is regardless of the learning setting, environment, or reward function. The generality and precision of the statement is why we believe it is insightful. Second, to justify further why we chose the term “insight”: we provide a formalism of an intuitive fact that holds true of every possible agent in a way that, in hindsight, the fact seems clear and even obvious. Even if the intuition is obvious (in hindsight), knowing how precisely to state this fact rigorously in a way that holds true of every possible agent is non-trivial (in our opinion). In this sense, we take the precise formalisation of the intuition to be insightful. Moreover, the first insight (conveyed through Theorem 3.2), we take to be the stronger of the two. We are happy to discuss further, and if the reviewer is unswayed by the above, we are happy to change the term “insight” to something weaker.\n\n> L95: I know it got absorbed into v, but I would still prepend this line with “Given <initial conditions> ℎ0, any tuple…” since your work aims to formalise rigorously the problem.\n\nGood point, fixed!\n\n> “We use as if in the sense of the positive economists” this is terminology that should be defined in the paper.\n\nWe are happy to include an expanded description of this terminology in the paper.\n\n> L338: I recommend not defining objects used in a main body theorem in the appendix.\n\nThis is a fair point. We will move the definition of “always reaches” to the main body of the paper.\n\n> Other Typos and Writing suggestions:\n\nThanks! We have fixed the remaining suggested typos and writing suggestions."}, {"review_id": "yj0iuMbIcO", "reviewer": "Reviewer_tAG2", "summary": "In this paper, the authors develop a simple mathematical definition of the continual RL problem. These definitions, insights, and results formalize many intuitive concepts at the heart of continual learning, and may open new research pathways surrounding continual learning agents. ", "questions": "1.What information can we get from Figure 2(a) Switching MDP Visual?  Do authors just want to emphasis “Each underlying MDP shares the same state space and action space, but varies in transition and reward functions”? \n2.How can we prove or evaluate the definitions, the proposed operators, and so on?\n3.Can authors add some ablation studies in this paper?", "limitations": "Please modify the paper as the weaknesses and questions above, and add limitation analysis in the paper.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The mathematical definition of continual reinforcement learning give us some inspirations when thinking of the continual learning, multi-task RL, continual supervised learning, and so on. ", "weaknesses": "1.The abstract is too simple that readers cannot get enough information and key ideas from it.\n2.This paper is not easy to follow, for the overall mathematical definitions and analysis. I hope the authors can give us more cases or experiments using the definitions proposed in this paper to highlights the benefits of following such definitions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we would like to thank the reviewer for reviewing our paper. We address the reviewer’s primary questions and concerns below, and will plan to update the paper in line with the reviewer’s suggestions.\n\n> 1.The abstract is too simple that readers cannot get enough information and key ideas from it.\n\nWe had originally thought a simple abstract would be a good choice, but in hindsight, we agree with the reviewer and will modify it accordingly. We will plan to change our abstract to the one mentioned in the rebuttal reply to all reviewers, and are open to suggestions for improvement.\n\n> 1.What information can we get from Figure 2(a) Switching MDP Visual? Do authors just want to emphasis “Each underlying MDP shares the same state space and action space, but varies in transition and reward functions”?\n\nYes, that is correct; we would like to give the reader a clear sense of the learning problem by emphasizing that each individual MDP shares a state-action space, but differs in its other components.\n\n> 2.How can we prove or evaluate the definitions, the proposed operators, and so on?\n\nWe believe that our definitions and operators should (1) capture intuitions and easily accommodate known cases of continual learning, (2) hold up under scrutiny, and (3) provide a language for carefully discussing important phenomena related to continual learning. We believe that our definition and the operators accomplish these three feats.\n\nFor instance, our CRL definition formalizes the intuition that “the best agents keep learning forever”, and the two examples we provide in Section 4.2 showcase that our definition can accommodate known special cases. Moreover, the necessary properties we establish of the CRL definition and the operators (Theorem 5.1, Theorem 5.2, Theorem 5.3) provide initial character that goes beyond the contents of the definitions themselves. For example, in defining the generates operator, it may not be obvious that deciding whether a given basis generates an agent set in an environment is undecidable–Theorem 5.2 proves this is in fact the case. In this sense, we believe our definition and operators satisfy the three above criteria (capture intuitions and accommodates known cases, holds up under scrutiny, and provides a language for discussing phenomena related to continual learning).\n\n> 3. Can authors add some ablation studies in this paper?\n\nIt is unclear to us what exactly an ablation would be in this case, and to what end we need one. Can you please elaborate?\n"}, {"review_id": "uf8llEd8cM", "reviewer": "Reviewer_1ia1", "summary": "The paper looks at developing a foundation for continual reinforcement learning (CRL). The authors develop definitions and insights, aiming to formalize the intuitive concepts in continual learning fields. They also provide two examples of CRL to illustrate the difference between traditional RL and CRL, which is viewing learning as endless adaptation instead of finding a solution.", "questions": "The high-level idea of CRL training is understandable, but I am unsure about the training details in Section 4.2 CRL examples. Including a pseudocode description could clarify the training process and help understand the implementation details.", "limitations": "Overall, the paper requires a lot of additional work to become publishable. Adding figures and pseudocode would enhance readability and understanding. Furthermore, conducting more experiments to demonstrate the effectiveness of the proposed CRL idea would strengthen the paper's contributions.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1, The concept of CRL as agent designer aiming to identify an optimal agent among available agents is innovative.\n\n2, The use of rigorous math tools and definition in this paper could provide valuable insight into continual learning and potentially inspire future CRL algorithms development.", "weaknesses": "1, Though it's not the focus and goal of this paper, the idea of agent basis contains redundancies and may hinder the transformation of it into a memory and computation efficient CRL algorithm.\n\n2, The training process of agent basis is unclear in Figure 2 (b). I guess two examples are presented to show the effectiveness of CRL, but it's not surprising that CRL can beat RL without adaptation in these changing envs. More online learning benchmarks would help to achieve a fair comparison.\n\n3, The paper is not well structured, and only few related works are mentioned. Continual Learning is discussed in many fields, with different names (e.g., online learning, few-shot adaptation, adaptive control), it would be valuable to provide a broader literature review.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we would like to thank the reviewer for reviewing our paper. We address the reviewer’s primary questions and concerns below, and will plan to update the paper in line with the reviewer’s suggestions.\n\n\n> 1, Though it's not the focus and goal of this paper, the idea of agent basis contains redundancies and may hinder the transformation of it into a memory and computation efficient CRL algorithm.\n\nCan you say more here? We do not understand the comment. It is unclear in what sense a basis contains redundancies. We show in Theorem 5.1.4+5.1.5 that it is a necessary property of every CRL problem that the design space of agents contains redundancies in a particular sense (with proofs provided in Appendix C). We suggest that, on a certain view, this might be unsurprising as the space of agents generated by a fixed agent basis will likely contain agents that are similar in their search through the agent basis. Critically, this redundancy need not apply to an agent basis. And, it is unclear to us what is meant by “...may hinder the transformation of it into a memory and computation efficient CRL algorithm”. If the reviewer could clarify we are happy to discuss further.\n\n> 2, The training process of agent basis is unclear in Figure 2 (b). I guess two examples are presented to show the effectiveness of CRL, but it's not surprising that CRL can beat RL without adaptation in these changing envs. More online learning benchmarks would help to achieve a fair comparison.\n\nThe examples in Section 4.2 are intended to illustrate that our definition of continual RL can directly accommodate standard instances of continual learning—the first case is an instance of the typical multi-task or lifelong RL setting often used in prior work (see, for instance, Wilson et al. 2007 or Brunskill and Li 2014), and the second case is exactly continual supervised learning as described in the survey by Mai et al. 2022. In the first example, the two agents deployed are both tabular Q-learning, where the only difference is the choice of the annealing schedule for the step-size parameter. In the “$\\alpha=C$ case, the step-size is a fixed constant, whereas in the $\\alpha=$anneal case, the step-size is annealed to zero in the limit.\n\n> 3, …only few related works are mentioned. Continual Learning is discussed in many fields, with different names (e.g., online learning, few-shot adaptation, adaptive control), it would be valuable to provide a broader literature review.\n\nWe are happy to include a broader and deeper discussion of related work on continual learning. We will plan to focus this discussion on the explicit relationship between our definition and past approaches to continual RL from the work by Ring and the recent continual RL survey by Khetarpal et al.. As mentioned in our reply to all reviewers, the work by Ring emphasizes the generality of the environment model and the reward function, while the survey by Khetarpal et al. focuses explicitly on non-stationary MDPs, similar to typical work on multi-task RL. We will include discussion showing the sense in which we accommodate and extend both of these views.\n\n> The high-level idea of CRL training is understandable, but I am unsure about the training details in Section 4.2 CRL examples. Including a pseudocode description could clarify the training process and help understand the implementation details.\n\nCan the reviewer clarify which details would be helpful to hear more about? Both algorithms are simply tabular Q-learning with different step-size annealing schedules. We are more than happy to include pseudocode (space permitting, or in the appendix) if that would help.\n"}]

Author rebuttal:
**[Overall Response]**

First we would like to thank all of the reviewers for their time and energy in reading and commenting on our paper. We recognize this takes considerable effort, and we appreciate it

**Summary:** Overall, our impression of the reviews is that there is a lot of enthusiasm around the ambition, importance, novelty, and high writing quality of the work, as well as its potential to open new research pathways and perspectives. Many of the reviewers raise excellent questions and suggestions, and we believe they can each be addressed, and that doing so will strengthen the paper. We here briefly summarize the main points that were raised across several reviews, and provide a more detailed response to each individual reviewer below.

**Point 1: The abstract is too short.**

We had originally thought a simple abstract would be a good choice, but we hear the reviewers’ suggestion, and will modify our abstract accordingly. We will plan to change our abstract to the following:

_[Abstract draft]_

> In the standard view of the reinforcement learning problem, an agent interacts with an environment with the goal of efficiently identifying an optimal behavior. However, this perspective is based on a restricted view of _learning as finding a solution_, rather than treating learning as _endless adaptation_. Instead, _continual_ reinforcement learning refers to the setting in which the best agents keep learning forever. Despite the importance of this setting, the community lacks a simple, canonical definition of the problem that makes its primary commitments and concepts both 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 “keep learning forever” through a pair of operators on agents that we call the “generates” and “reaches” operators that provide 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 any setting in which the best agents are all continual learning agents. We provide two motivating examples of the setting, illustrating that traditional views of continual learning such as multi-task reinforcement learning and continual supervised learning are special cases of our definition. Furthermore, we establish necessary properties of both the continual reinforcement learning problem and the new operators. Collectively, these definitions, insights, and results formalize many intuitive concepts at the heart of continual learning, and open new research pathways surrounding continual learning agents.

We are happy to make changes to the above draft, and we hope this resolves the reviewers’ concern.

**Point 2: We could make additional contact with existing work on continual RL**

This is a very good suggestion. We will plan to add an expanded discussion in the paper commenting in-depth about the relationship between our definition of CRL and prior work on CRL, with an emphasis on the line of work by Ring and the recent CRL survey by Khetarpal et al. Succinctly, the works by Ring emphasizes the generality of the environment model and the reward function, while the survey by Khetarpal et al. focuses explicitly on non-stationarity, similar to work on multi-task RL by Wilson et al. (2007) and Brunskill and Li (2014). Our definition directly accommodates and extends both of these views, and we are happy to include a detailed discussion about this in the paper. 

**Point 3: “Similarly, the authors mention several avenues for future research such as the examination of catastrophic forgetting - it might be interesting to include at least a characterisation of these problems in the new framework to inspire future work.”**

This is another great suggestion. While these lines of research are still in their early stages (we are actively exploring them now), we do believe there is a new opportunity to model and analyze these important empirical phenomena using the language from our work, and we will plan to expand on this discussion in the paper.

As one example of a connection to practical considerations, let’s consider plasticity loss. Plasticity loss can be well thought of using the conceptual tools we develop: _plasticity_ is the fraction of an agent’s corresponding agent basis that remains reachable to the agent over time, and plasticity _loss_ is any reduction of this number. We foresee opportunities to both diagnose agents from a new perspective, and to design algorithms based around this measure; for example, by developing learning rules (Defn. 3.2) that provably maintain plasticity (or analysing which existing learning rules maintain plasticity, and under what conditions).

Regarding pathways toward defining new algorithms, we have two responses.

First, as we argue after giving the definition of CRL (Defn. 4.1), our goal in defining CRL precisely is to encourage a departure in how we _think_ about designing agents: Given a basis, rather than try to build agents that can _solve_ problems by identifying a fixed high-quality element of the basis, we should instead focus on designing agents that continue to update their basis element indefinitely in light of experience. We believe this change in _perspective_ alone is needed, and can shape our basic approach to designing learning algorithms.

Second, as a slightly more concrete proposal, we might explicitly characterize learning rules that are guaranteed to produce a continual learning agent of the kind defined by Definition 4.1—what are the necessary and sufficient conditions of such a learning rule? Answering this question can give rise to algorithmic primitives that are guaranteed to produce continual learning agents (which, as Dohare et al. 2022 showed recently, is not true of many standard learning rules).


Meta-review: The reviewers mostly agreed that this is a solid paper with significant contributions.
Decision: Accept (poster)