# Continual Learning as
Computationally Constrained Reinforcement Learning

Saurabh Kumar  Henrik Marklund  Ashish Rao  Department of Computer Science,
Stanford University  Yifan Zhu  Department of Electrical Engineering, Stanford
University
Hong Jun Jeon  Department of Computer Science, Stanford University  Yueyang
Liu  Department of Management Science and Engineering, Stanford University
Benjamin Van Roy  Department of Electrical Engineering, Stanford University
Department of Management Science and Engineering, Stanford University

###### Abstract

An agent that efficiently accumulates knowledge to develop increasingly
sophisticated skills over a long lifetime could advance the frontier of
artificial intelligence capabilities. The design of such agents, which remains
a long-standing challenge of artificial intelligence, is addressed by the
subject of continual learning. This monograph clarifies and formalizes
concepts of continual learning, introducing a framework and set of tools to
stimulate further research.

Metrics presented in previous literature for evaluating continual learning
agents tend to focus on particular behaviors that are deemed desirable, such
as avoiding catastrophic forgetting, retaining plasticity, relearning quickly,
and maintaining low memory or compute footprints. In order to systematically
reason about design decisions and compare agents, a coherent, holistic
objective that encompasses all such requirements would be helpful. To provide
such an objective, we cast continual learning as reinforcement learning with
limited compute resources. In particular, we pose the continual learning
objective to be the maximization of infinite-horizon average reward subject to
a computational constraint. Continual supervised learning, for example, is a
special case of our general formulation where the reward is taken to be
negative log loss or accuracy. Among implications of maximizing average reward
are that remembering all information from the past is unnecessary, forgetting
non-recurring information is not “catastrophic,” and learning about how an
environment changes over time is useful.

A binding computational constraint bears implications on factors to consider
when designing a continual learning agent. First, we explain how computation
limits the agent’s information capacity. A consequence is that, unlike more
traditional framings of machine learning in which regret vanishes as an agent
learns, the regret experienced in continual learning typically persists.
Related to this is that a stationary environment can appear nonstationary to a
capacity-bounded agent, and therefore, the computational constraint induces
the need for perpetual adaptation. Second, the limited information capacity
gives rise to the familiar stability-plasticity dilemma, which we formalize in
information-theoretic terms. Finally, to illustrate implications of our
continual learning objective on performant agent behaviors such as forgetting,
relearning, and exploration, we present a range of empirical case studies.

###### Contents

  1. 1 Introduction
  2. 2 An Objective for Continual Learning
    1. 2.1 Continual Interaction
    2. 2.2 Average Reward
    3. 2.3 Continual Learning Agents
      1. 2.3.1 Tracking
      2. 2.3.2 Exploration
      3. 2.3.3 Delayed Consequences
      4. 2.3.4 Supervised Learning
    4. 2.4 Computational Constraints
    5. 2.5 Learning Complex Skills over a Long Lifetime
  3. 3 Agent State and Information Capacity
    1. 3.1 Agent State
    2. 3.2 Information Content
    3. 3.3 Information Capacity
    4. 3.4 Performance versus Information Capacity
      1. 3.4.1 Prediction Error
      2. 3.4.2 Informational Error Quantifies Absent Information
      3. 3.4.3 Information Capacity Constrains Performance
  4. 4 Vanishing-Regret Versus Continual Learning
    1. 4.1 Vanishing-Regret Learning
      1. 4.1.1 Learning Targets, Target Policies, and Vanishing Regret
      2. 4.1.2 Regret Analysis
      3. 4.1.3 The Cosmic Learning Target
    2. 4.2 Continual Learning
      1. 4.2.1 Constraints Incentivize Persistent Regret
      2. 4.2.2 Nonstationary Learning Targets
    3. 4.3 On Learning About an Unknown Environment
  5. 5 Stability Versus Plasticity
    1. 5.1 Stability-Plasticity Decomposition
    2. 5.2 A Didactic Example
      1. 5.2.1 LMS with an AR(1) Process
      2. 5.2.2 Constraining Information Content
      3. 5.2.3 Analysis
      4. 5.2.4 Stepsize Adaptation
  6. 6 Case Studies
    1. 6.1 Continual Supervised Learning
      1. 6.1.1 Environment
      2. 6.1.2 Agents
      3. 6.1.3 Evaluation Protocol
      4. 6.1.4 Results
    2. 6.2 Continual Exploration
      1. 6.2.1 Exploration in Stationary Environments
      2. 6.2.2 Exploration in Nonstationary Environments
      3. 6.2.3 Coin Swapping Games
      4. 6.2.4 Experiments in AR(1) Bandits
    3. 6.3 Continual Learning from Delayed Consequences
      1. Results
  7. 7 Conclusion
  8. Appendix
  9. A MDP Exchangeability
  10. B Capacity-Constrained LMS with an AR(1) Process
    1. B.1 Reparameterizing the Agent
    2. B.2 Plasticity and Forgetting Error
    3. B.3 The Optimal Learning Rate is Independent of Information Capacity
    4. B.4 Modifying IDBD to Account for Quantization Noise
  11. C Case Studies
    1. C.1 Continual Supervised Learning
    2. C.2 Continual Learning with Delayed Consequences

##  1 Introduction

Continual learning remains a long-standing challenge of artificial
intelligence. An agent that efficiently accumulates knowledge to develop
increasingly sophisticated skills over a long lifetime could advance the
frontier of artificial intelligence capabilities [Hadsell et al., 2020,
Khetarpal et al., 2022, Ring, 2005, Thrun and Pratt, 1998]. Success requires
continuously ingesting new knowledge while retaining old knowledge that
remains useful. Existing incremental machine learning techniques have failed
to demonstrate this capability as they do not judiciously control what
information they ingest, retain, or forget. Indeed, catastrophic forgetting
(ejecting useful information from memory) and implasticity (forgoing useful
new information) are recognized as primary obstacles to effective continual
learning.

Traditional framings of machine learning view agents as acquiring knowledge
about a fixed unknown latent variable. The aim is to develop methods that
quickly learn about the latent variable, which we will refer to as the
learning target, as data accumulates. For instance, in supervised learning,
the learning target could be an unknown function mapping inputs to labels. In
the reinforcement learning literature, the learning target is often taken to
be the unknown transition matrix of a Markov decision process. With such
traditional framings, an agent can be viewed as driving per-timestep regret –
the performance shortfall relative to what could have been if the agent began
with perfect knowledge of the learning target – to zero. If the agent is
effective, regret vanishes as the agent accumulates knowledge about the
learning target. When regret becomes negligible, the agent is viewed as “done”
with learning.

In contrast, continual learning addresses environments in which there may be
no natural fixed learning target and a performant agent ought to never stop
acquiring new knowledge. The need for continual learning can arise, for
example, if properties of the agent’s data stream appear to change over time.
A performant agent must constantly adapt its behavior in response to these
evolving patterns.

There is a large gap between the state of the art in continual learning and
what may be possible, making the subject ripe for innovation. This difference
becomes evident when examining an approach to continual learning commonly
deployed in industrial applications, which entails periodically training a new
model from scratch on buffered data. To crystalize this, consider as a
hypothetical example an agent designed to trade stocks. At the end of each
month, this agent trains a new neural network model from scratch on data
observed over the preceding twelve months. Replacing the old, this new model
then governs decisions over the next month. This agent serves as a simple
baseline that affords opportunity for improvement. For example, training each
month’s model from scratch is likely wasteful since it does not benefit from
computation invested over previous months. Further, by limiting knowledge
ingested by each model to that available from data acquired over the preceding
twelve months, the agent forgoes the opportunity to acquire complex skills
that might only be garnered over a much longer duration.

While it ought to be possible to design more effective continual learning
agents, how to go about that or even how to assess improvement remains
unclear. Work on deep learning suggests that agent performance improves with
increasing sizes of models, data sets, and inputs. However, computational
resource requirements scale along with these and become prohibitive. A
practically useful objective must account for computation. The primary goals
of this monograph are to propose such an objective for continual learning and
to understand key factors to consider in designing a performant continual
learning agent. Rather than offer definitive methods, we aim to stimulate
research toward identifying them.

Metrics presented in previous literature for evaluating continual learning
agents tend to focus on particular behaviors that are deemed desirable, such
as avoiding catastrophic forgetting, retaining plasticity, relearning quickly,
and maintaining low memory or compute footprints [Ashley et al., 2021, Dohare
et al., 2021, Fini et al., 2020, Kirkpatrick et al., 2017]. For instance, the
most common evaluation metric measures prediction accuracy on previously seen
tasks to study how well an agent retains past information [Wang et al., 2023].
However, the extent to which each of these behaviors matters is unclear. In
order to systematically reason about design decisions and compare agents, a
coherent, holistic objective that reflects and encompasses all such
requirements would be helpful.

In this paper, we view continual learning under the lens of reinforcement
learning [Agarwal et al., 2019, Bertsekas and Tsitsiklis, 1996, Meyn, 2022,
Sutton and Barto, 2018, Szepesvári, 2010] to provide a formalism for what an
agent is expected to accomplish. Specifically, we consider maximization of
infinite-horizon average reward subject to a computational constraint. Average
reward emphasizes long-term performance, which is suitable for the purpose of
designing long-lived agents. The notion of maximizing average reward
generalizes that of online average accuracy, as used in some literature on
continual supervised learning [Cai et al., 2021, Ghunaim et al., 2023, Hammoud
et al., 2023, Hu et al., 2022, Lin et al., 2021, Prabhu et al., 2023a, Xu et
al., 2022].

As reflected by average reward, an agent should aim to perform well on an
ongoing basis in the face of incoming data it receives from the environment.
Importantly, remembering all information from the past is unnecessary, and
forgetting non-recurring information is not “catastrophic.” An agent can
perform well by remembering the subset that continues to remain useful.
Although our objective relaxes the requirement of retaining all information to
only retaining information useful in the future, even this remains difficult,
or even impossible, in practice. Computational resources limit an agent’s
capacity to retain and process information. The computational constraint in
our continual learning objective reflects this gating factor. This is in line
with recent work highlighting the need to consider computational costs in
continual learning [Prabhu et al., 2023b].

The remainder of this monograph is organized as follows. In Section 2, we
introduce our framing of continual learning as reinforcement learning with an
objective of maximizing average reward subject to a computational constraint.
In Section 3, we introduce information-theoretic tools inspired by Jeon et al.
[2023], Lu et al. [2021] to offer a lens for studying agent behavior and
performance. In Section 4, we interpret in these information-theoretic terms
what it means for an agent to perpetually learn rather than drive regret to
zero and be “done” with learning. This line of thought draws inspiration from
Abel et al. [2023], who define a notion of convergence and associates
continual learning with non-convergence. In Section 5, we formalize the
concepts of stability and plasticity to enable coherent analysis of trade-offs
between these conflicting goals. Finally, in Section 6, to highlight the
implications of our continual learning objective, we study simulation results
from a set of case studies. In the first case study, on continual supervised
learning, we study the role of forgetting in relation to our continual
learning objective. In the second and third case studies, on continual
exploration and continual learning with delayed consequences, we study
implications of nonstationarity and our objective on how an agent ought to
explore and learn from delayed consequences.

##  2 An Objective for Continual Learning

Continual learning affords the never-ending acquisition of skills and
knowledge [Ring, 1994]. An agent operating over an infinite time horizon can
develop increasingly sophisticated skills, steadily building on what it
learned earlier. On the other hand, due to computational resource constraints,
as such an agent observes an ever-growing volume of data, it must forgo some
skills to prioritize others. Designing a performant continual learning agent
requires carefully trading off between these considerations. A suitable
mathematical formulation of the design problem must account for that. While
many metrics have been proposed in the literature, they have tended to focus
on particular behaviors that are deemed desirable. A coherent, holistic
objective would help researchers to systematically reason about design
decisions and compare agents. In this section, we formulate such an objective
in terms of computationally constrained reinforcement learning (RL).

The subject of RL addresses the design of agents that learn to achieve goals
through interacting with an environment [Sutton and Barto, 2018]. As we will
explain, the general RL formulation subsumes the many perspectives that appear
in the continual learning literature. We review RL and its relation to
continual learning, illustrating with examples. We will then highlight the
critical role of computational constraints in capturing salient trade-offs
that arise in continual learning. Imposing a computational constraint on the
general RL formulation gives rise to a coherent objective for continual
learning. Aside from formulating this objective, we reflect on several
implications of framing continual learning in these terms.

###  2.1 Continual Interaction

We consider continual interaction across a general agent-environment interface
as illustrated in Figure 1. At each time step $t=0,1,2,\ldots$, an agent
executes an action $A_{t}$ and then observes a response $O_{t+1}$ produced by
the environment. Actions take values in an action set $\mathcal{A}$.
Observations take values in an observation set $\mathcal{O}$. The agent’s
experience through time $t$ forms a sequence
$H_{t}=(A_{0},O_{1},A_{1},O_{2},\ldots,A_{t-1},O_{t})$, which we refer to as
its history. We denote the set of possible histories by
$\mathcal{H}=\cup_{t=0}^{\infty}(\mathcal{A}\times\mathcal{O})^{t}$.

Figure 1: The agent-environment interface.

An environment is characterized by a triple
$\mathcal{E}=(\mathcal{A},\mathcal{O},\rho)$, where $\rho$ is an observation
probability distribution, which satisfies
$\rho(\cdot|H_{t},A_{t})=\mathbb{P}(O_{t+1}\in\cdot|H_{t},A_{t})$. From the
agent designer’s perspective, it is as though the environment samples
$O_{t+1}$ from $\rho(\cdot|H_{t},A_{t})$.

The agent generates each action $A_{t}$ based on the previous history $H_{t}$.
This behavior is characterized by a policy $\pi$, for which
$\pi(\cdot|H_{t})=\mathbb{P}_{\pi}(A_{t}\in\cdot|H_{t})$. The subscript $\pi$
indicates the policy under which this probability is calculated. We refer to
this policy, which characterizes the agent’s behavior, as the agent policy.
While the agent may carry out sophisticated computations to determine each
action, from the environment’s perspective, it is as though the agent simply
samples $A_{t}$ from $\pi(\cdot|H_{t})$.

Note that we take event probabilities to represent uncertainty from the agent
designer’s perspective. For example,
$\mathbb{P}_{\pi}((A_{t},O_{t+1})\in\tilde{\mathcal{A}}\times\tilde{\mathcal{O}}|H_{t})$
is the designer’s subjective assessment of the chance that the next action-
observation pair will fall in a set
$\tilde{\mathcal{A}}\times\tilde{\mathcal{O}}$ conditioned on $H_{t}$, given
that the agent implements $\pi$. We take the function $\rho$ to be
deterministic, or equivalently, known to the designer. Note that the fact that
$\rho$ is deterministic does not mean observations are fully determined by
history and action. Rather,
$\mathbb{P}(O_{t+1}\in\tilde{\mathcal{O}}|H_{t},A_{t})=\rho(\tilde{\mathcal{O}}|H_{t},A_{t})$
can lie between zero and one. With some abuse of notation, as shorthand, with
singleton sets $\tilde{\mathcal{A}}$ and $\tilde{\mathcal{O}}$, we write
$\pi(a|h)\equiv\pi(\\{a\\}|h)$ and $\rho(o|h,a)\equiv\rho(\\{o\\}|h,a)$. The
following simple example offers a concrete instantiation of our formulation
and notation.

######  Example 1.

(coin tossing) Consider an environment with two actions
$\mathcal{A}=\\{1,2\\}$, each of which identifies a distinct coin. At each
time $t$, an action $A_{t}$ selects a coin to toss next. Observations are
binary, meaning $\mathcal{O}=\\{0,1\\}$, with $O_{t+1}$ indicating whether the
selected coin lands heads. The coin biases $(p_{1},p_{2})$ are independent but
initially unknown, and the designer’s uncertainty prescribes prior
distributions. These environment dynamics are characterized by a function
$\rho$ for which $\rho(1|h,a)$ is the probability that coin $a$ lands heads,
regardless of the history $h$.

As a concrete special case, suppose the prior distribution over each coin’s
bias is uniform over the unit interval. Then, at each time $t$, each bias
$p_{a}$ is distributed $\mathrm{beta}(\alpha_{t,a},\beta_{t,a})$, with
parameters initialized at $\alpha_{0,a}=\beta_{0,a}=1$ and updated according
to
$(\alpha_{t+1,A_{t}},\beta_{t+1,A_{t}})=(\alpha_{t,A_{t}}+O_{t+1},\beta_{t,A_{t}}+1-O_{t+1})$.
Hence,
$\rho(1|H_{t},A_{t})=\alpha_{t,A_{t}}/(\alpha_{t,A_{t}}+\beta_{t,A_{t}})$.

The form of interaction we consider is fully general; each observation can
exhibit any sort of dependence on history. Notably, we do not assume that
observations identify the state of the environment. While such an assumption –
that the “environment is MDP,” so to speak – is common to much of the RL
literature [Sutton and Barto, 2018], a number of researchers have advocated
for the general action-observation interface, especially when treating design
of generalist agents for complex environments [Daswani et al., 2013, 2014,
Dong et al., 2022, Hutter, 2007, Lu et al., 2021, McCallum, 1995, Ring, 1994,
2005].

Note that we characterize the environment via a deterministic function $\rho$.
Hence, the environment is known to the agent designer. This is in contrast to
common formulations that treat the environment as unknown. As we will explain
in Section 4, it is often more natural to treat environments of the sort that
call for continual learning as known. Further, characterizing the environment
as known never sacrifices generality, even when it is natural to treat the
environment as unknown. In particular, observations generated by an unknown
(random) function $\tilde{\rho}$ are indistinguishable from those generated by
a known (deterministic) function $\rho$ for which
$\rho(\cdot|H_{t},A_{t})=\mathbb{E}[\tilde{\rho}(\cdot|H_{t},A_{t})|H_{t},A_{t}]$.
To make this concrete, consider the environment of Example 1, which is
characterized by a random function $\tilde{\rho}$, defined by
$\tilde{\rho}(1|h,a)=p_{a}$ , for each $h$ and $a$, together with a prior
distribution over $\tilde{\rho}$. The prior distribution over $\tilde{\rho}$
is induced by a prior distribution over the coin biases $(p_{1},p_{2})$. This
environment can alternatively be characterized by the deterministic function
$\rho$ for which
$\rho(1|H_{t},A_{t})=\mathbb{E}[\tilde{\rho}(1|H_{t},A_{t})|H_{t},A_{t}]$. In
this context, where we marginalize over an unknown latent variable
$\tilde{\rho}$, the deterministic function $\rho(\cdot|H_{t},A_{t})$ is is the
posterior predictive distribution. If, for example, the prior distribution
over coin biases is uniform then
$\rho(1|h,a)=\frac{\alpha_{a,t}}{\alpha_{a,t}+\beta_{a,t}}=1-\rho(0|h,a)$ for
each $h$ and $a$.

Finally, there is a possibly subtle point that the coin tossing example
highlights. The observation probability function for the coin tossing example
is $\rho(1|h,a)=\frac{\alpha_{a,t}}{\alpha_{a,t}+\beta_{a,t}}$ which means
that, from the perspective of the agent, the outcomes of the coin tosses are
not iid. Indeed, if they were iid there would be nothing to learn. Data
generating processes that the literature refers to as iid are typically iid
only if conditioned on a latent random variable. For instance, in supervised
learning, the data is typically assumed to be iid conditioned on an unknown
function and assuming the input distribution is known. This is why the
observation probability function $\rho$, which does not depend on any latent
variable, prescribes a non-iid distribution over outcomes.

###  2.2 Average Reward

The agent designer’s preferences are expressed through a reward function
$r:\mathcal{H}\times\mathcal{A}\times\mathcal{O}\rightarrow\mathbb{R}$. The
agent computes a reward $R_{t+1}=r(H_{t},A_{t},O_{t+1})$ at each time. As is
customary to the RL literature, this reward indicates whether the agent is
achieving its purpose, or goals.

A coherent objective requires trading off between short and long term rewards
because decisions expected to increase reward at one point in time may reduce
reward at another. As a continual learning agent engages in a never-ending
process, a suitable objective ought to emphasize the long game. In other
words, a performant continual learning agent should attain high expected
rewards over asymptotically long horizons. This behavior is incentivized by an
average reward objective function:

$\overline{r}_{\pi}=\liminf_{T\rightarrow\infty}\mathbb{E}_{\pi}\left[\frac{1}{T}\sum_{t=0}^{T-1}R_{t+1}\right].$
(1)

Analogously with $\mathbb{P}_{\pi}$, the subscript of $\mathbb{E}_{\pi}$
indicates the policy under which this expectation is calculated. We will frame
the goal of agent design to be maximizing average reward subject to a
computation constraint that we will later introduce and motivate. The
expectation integrates with respect to probability distributions prescribed by
$\pi$ and $\rho$. In particular, $\pi$ provides each next action distribution,
conditioned on history, while $\rho$ provides each next observation
distribution, conditioned on history and action. The probability distribution
of a history $H_{t}$ is the product of these conditional probabilities across
actions and observations through time $t$, and $H_{t}$ determines rewards
received through that time.

Average reward may seem like a strange choice of objective for assessing agent
performance in an environment of the kind described in Example 1. In
particular, many policies, some of which learn quickly and some of which learn
extremely slowly, converge on the better coin and thus attain the maximal
average reward. The fact that this objective can not discriminate between
these policies poses a limitation. However, in the realm of continual
learning, such an environment is degenerate. Environments of interest are
those in which an agent ought to continually acquire new useful information
rather than effectively complete its learning after some time. Indeed, the
environment of Example 1 is stationary, whereas the subject of continual
learning aims to address nonstationarity. A simple modification of Example 1
gives rise to a nonstationary environment.

######  Example 2.

(coin swapping) Recall the environment of Example 1, but suppose that, at each
time $t$, before action $A_{t}$ is executed, each coin $a$ is replaced by a
new coin with some fixed probability $q_{a}$. Coin replacement events are
independent, and each new coin’s bias is independently sampled from its prior
distribution. With this change, biases of the two available coins can vary
over time. Hence, we introduce time indices and denote biases by
$(p_{t,1},p_{t,2})$.

Agents that learn quickly attain higher average reward in nonstationary
environments such as this one. In particular, there is benefit to quickly
learning about coin biases and capitalizing on that knowledge for as long as
possible before the coins are replaced.

While some work on continual learning has advocated for average reward as an
objective [Chen et al., 2022, Sharma et al., 2021], discounted reward has
attracted greater attention [Khetarpal et al., 2022, Ring, 2005]. Perhaps this
is due to the technical burden associated with design and analysis of agents
that aim to maximize average reward. We find average reward to better suit the
spirit of continual learning as it emphasizes long-term performance. Continual
learning affords the possibility of learning very sophisticated skills that
build on experience accumulated over a long lifetime, and emphasizing long-
term behavior incentivizes design of agents that learn such skills if
possible.

The continual learning literature has spawned a multitude of other metrics for
assessing agent performance. Prominent criteria tend to focus on detecting
particular behaviors rather than holistic evaluation. Examples include the
ability to perform an old task well after learning a new task, the ability to
more quickly learn to perform a new task, and better performance on a new task
before gathering enough data to learn new skills [Vallabha and Markowitz,
2022]. Average reward subsumes such criteria when they are relevant to online
operation over an infinite time horizon. For example, an agent’s initial
performance on a new task as well as the time required to learn to do better
impact average reward. On the other hand, the ability to perform well on an
old task that will never reappear is irrelevant, and average reward is
appropriately insensitive to that.

Assessing performance in terms of average reward gives rise to additional
intriguing implications. First, even if the agent forgets recurring
information, the agent can do well if it can relearn that quickly when needed.
This is intuitive: a competent software engineer who forgets a programming
language can, when required for a new year-long project, quickly relearn it
and successfully complete the project. Second, the agent can benefit from
predicting changing patterns. Modeling dynamics can help the agent decide what
skills to retain. For instance, certain recurrence is periodic and therefore
predictable, like queries about ice cream during the summer. Something not
recurring may also be predictable such as when an elected official finishes
their term and steps out of the limelight. An agent could in principle learn
to predict future events to prioritize skills. Our theoretical and empirical
analyses will further elucidate on these implications of the average reward
objective.

###  2.3 Continual Learning Agents

In our abstract formulation, a continual learning agent is characterized by an
agent policy $\pi$, which specified the conditional distribution of each
action $A_{t}\sim\pi(\cdot|H_{t})$. To crystalize this notion, in this section
we describe a few specific instances as concrete examples of agents. In each
instance we present the interface $(\mathcal{A},\mathcal{O})$ for which the
agent is designed, the algorithm the agent implements to compute each action
$A_{t}$, and an environment in which the agent ought to be effective.

####  2.3.1 Tracking

Suppose observations $O_{1},O_{2},O_{3},\ldots$ are noisy measurements of a
latent stochastic process. For example, each could be a thermostat reading,
which is not exactly equal to the current temperature. A tracking agent
generates estimates $A_{t}$ of the latent process, each of which can be viewed
as predictions of $O_{t+1}$. The least mean squares (LMS) algorithm implements
a simple tracking agent. While the algorithm more broadly applies to vector-
valued observations, to start simple, we consider only the scalar case.

######  Example 3.

(scalar LMS) This agent interacts with an environment through real-valued
actions and observations: $\mathcal{A}=\mathcal{O}=\mathbb{R}$. Each action
$A_{t}$ represents a prediction of the next observation $O_{t+1}$, and to
penalize errors, the reward function is taken to be negative squared error:
$r(H_{t},A_{t},O_{t+1})=-(O_{t+1}-A_{t})^{2}$. Initialized with
$\mu_{0}\in\mathbb{R}$, the agent updates this parameter according to

$\mu_{t+1}=\eta\mu_{t}+\alpha(O_{t+1}-\eta\mu_{t}),$

where $\eta\in[0,1]$ and $\alpha\in[0,1]$ are shrinkage and stepsize
hyperparameters. The agent executes actions $A_{t}=\eta\mu_{t}$.

The LMS algorithm is designed to track a latent process that generates
observations. Let us offer an example of an environment driven by such a
process, for which the algorithm is ideally-suited. Consider a random sequence
$(\theta_{t}:t\in\mathbb{Z}_{+})$, with the initial latent variable
$\theta_{0}$ distributed according to a prior
$\mathcal{N}(\mu_{0},\Sigma_{0})$ and updated according to
$\theta_{t+1}=\eta\theta_{t}+Z_{t+1}$, with each process perturbation
$Z_{t+1}$ independently sampled from $\mathcal{N}(0,\zeta^{2})$. Further,
suppose that $O_{t+1}=\theta_{t+1}+W_{t+1}$, with each observation noise
sample $W_{t+1}$ drawn independently from $\mathcal{N}(0,\sigma^{2})$.

What we have described provides a way of generating each observation
$O_{t+1}$. We have thus fully characterized an environment
$\mathcal{E}=(\mathcal{A},\mathcal{O},\rho)$. Note that we are using the
parameter $\eta$ for two purposes. First, it is a hyperparameter of the agent
described in Example 3. Second, it serves in the specification of this
hypothetical environment that we frame as one for which the agent is ideally
suited. For this environment, with an optimal choice of stepsize, the LMS
algorithm attains minimal average reward over all agent designs. Figure 2(a)
plots average reward as a function of stepsize. The tracking behavior in
Figure 2(b) is attained by the optimal stepsize.

(a) Average reward as a function of stepsize $\alpha$, averaged over $10^{4}$
time steps and $10^{3}$ trials.

(b) The LMS agent with optimal stepsize ($\alpha=0.35$) tracks the latent
scalar process well.

Figure 2: Tracking a latent scalar process using the LMS algorithm. The plots
are generated with $\mu_{0}=0$, $\Sigma_{0}=1$, $\eta=0.9$, $\zeta=0.5$, and
$\sigma=1$.

####  2.3.2 Exploration

In Example 3, actions do not impact observations. The following agent updates
parameters in a similar incremental manner but then uses them to select
actions that determine what information is revealed through observations.

######  Example 4.

(nonstationary Gaussian Thompson sampling) This agent interfaces with a finite
action set $\mathcal{A}$ and real-valued observations
$\mathcal{O}=\mathbb{R}$. The reward is taken to be the observation, so that
$R_{t+1}=r(H_{t},A_{t},O_{t+1})=O_{t+1}$. Initialized with
$\mu_{0}\in\mathbb{R}^{\mathcal{A}}$, the agent updates parameters according
to

$\displaystyle\mu_{t+1,a}=\left\\{\begin{array}[]{ll}\eta\mu_{t,a}+\alpha_{t+1}(O_{t+1}-\eta\mu_{t,a})&\qquad\mathrm{if\
}a=A_{t}\\\ \eta\mu_{t,a}&\qquad\mathrm{otherwise.}\end{array}\right.$

Note that each observation only impacts the component of $\mu_{t}$ indexed by
the executed action. The stepsize varies with time according to
$\alpha_{t+1}=\Sigma_{t+1,A_{t}}/\sigma^{2}$, for a sequence initialized with
a vector $\Sigma_{0}\in\mathbb{R}_{+}^{\mathcal{A}}$ and updated according to

$\displaystyle\Sigma_{t+1,a}=\left\\{\begin{array}[]{ll}\frac{1}{\frac{1}{\eta^{2}\Sigma_{t,a}+\zeta^{2}}+\frac{1}{\sigma^{2}}}&\qquad\mathrm{if\
}a=A_{t}\\\
\eta^{2}\Sigma_{t,a}+\zeta^{2}&\qquad\mathrm{otherwise,}\end{array}\right.$

where $\eta\in\mathbb{R}$, $\zeta\in\mathbb{R}_{+}$, $\sigma\in\mathbb{R}_{+}$
are scalar hyperparameters. Each $\hat{\theta}_{t,a}$ is drawn independently
from $\mathcal{N}(\mu_{t,a},\Sigma_{t,a})$. Then, $A_{t}$ is sampled uniformly
from the set $\operatorname*{arg\,max}_{a\in\mathcal{A}}\hat{\theta}_{t,a}$.

This agent is especially suited for a particular environment, which is
characterized by latent random variables $\theta_{a}$, each independent and
initially distributed $\mathcal{N}(\mu_{0,a},\Sigma_{0,a})$. Rewards and
observations are generated according to
$R_{t+1}=O_{t+1}=\theta_{A_{t}}+W_{t+1}$, with each $W_{t+1}$ sampled
independently from $\mathcal{N}(0,\sigma^{2})$. It is natural to think of this
as a stationary environment because the latent mean rewards $\theta_{a}$ do
not change over time.

The environment we have described constitutes a bandit; this is a somewhat
antiquated reference to a slot machine, which tends to “rob” players of their
money. With multiple arms, as illustrated in Figure 3, a player chooses at
each time an arm $A_{t}$ and receives a payout $R_{t+1}$. Because payout
distributions are not listed, the player can learn them only by experimenting.
As the gambler learns about each arm’s payouts, they face a dilemma: in the
immediate future they expect to earn more by exploiting arms that yielded high
payouts in the past, but by continuing to explore alternative arms they may
learn how to earn higher payouts in the future.

Figure 3: A two-armed bandit.

In the stationary environment we have described, the distribution for arm $a$
is Gaussian with unknown mean $\theta_{a}$, which can be learned by observing
payouts. For this environment, if $\eta=1$ and $\zeta=0$, the agent can be
interpreted as selecting actions via Thompson sampling [Russo et al., 2018,
Thompson, 1933]. In particular, at each time $t$, the posterior distribution
of $\theta_{a}$ is $\mathcal{N}(\mu_{t,a},\Sigma_{t,a})$, and the agent
samples statistically plausible estimates $\hat{\theta}_{t,a}$ from this
distribution, then executes an action that maximizes among them.

If $\eta\in(-1,1)$ and $\zeta>0$, on the other hand, the environment is
considered a nonstationary bandit because the arm payout distributions vary
over time. In particular, the environment is characterized by latent random
variables updated according to $\theta_{t+1,a}=\eta\theta_{t,a}+Z_{t+1,a}$,
with each $Z_{t+1,a}$ independently sampled from $\mathcal{N}(0,\zeta^{2})$.
The agent maintains parameters of the posterior distribution of
$\theta_{t,a}$, which is $\mathcal{N}(\mu_{t,a},\Sigma_{t,a})$. For each
action $a$, the agent samples $\hat{\theta}_{t,a}$ from the posterior
distribution. The agent then executes an action that maximizes among these
samples.

This nonstationary Gaussian Thompson sampling agent may be applied in other
environments as well, whether or not observations are driven by Gaussian
processes. For example, with a suitable choice of $\zeta$, it may exhibit
reasonable behavior in the coin swapping environment of Example 2. However,
the agent does not adequately address environments in which actions induce
delayed consequences.

####  2.3.3 Delayed Consequences

The agent of Example 4 maintains parameters $\mu_{t}$ that serve the
prediction $\eta\mu_{t,A_{t}}$ of the expected immediate reward $R_{t+1}$.
These predictions can guide the agent to select actions that earn high
immediate reward. To learn from and manage delayed rewards, the Q-learning
algorithm [Watkins, 1989] instead maintains predictions $Q(S_{t},A_{t})$ of
the expected discounted return $\sum_{k=0}^{\infty}\gamma^{k}R_{t+k+1}$. In
addition to the action $A_{t}$, such predictions are conditioned on a
situational state $S_{t}$, which provides context for the agent’s decision.
The following example elaborates.

######  Example 5.

(optimistic Q-learning) This agent is designed to interface with any
observation set $\mathcal{O}$ and any finite action set $\mathcal{A}$. It
maintains an action value function $Q_{t}$, which maps the situational state
$S_{t}$, which takes values in a finite sets $\mathcal{S}$, and action $A_{t}$
to a real value $Q_{t}(S_{t},A_{t})$. The situational state $S_{t}$ represents
features of the history $H_{t}$ that are predictive of future value. It is
determined by an update function $f$, which forms part of the agent design,
according to

$S_{t+1}=f(S_{t},A_{t},O_{t+1}),$

and substitutes for history in the computation of rewards, which take the form
$R_{t+1}=r(S_{t},A_{t},S_{t+1})$. We consider an optimistic version of
Q-learning, which updates the action value function according to

$Q_{t+1}(s,a)=\left\\{\begin{array}[]{ll}Q_{t}(S_{t},A_{t})+\alpha\left(R_{t+1}+\gamma\max_{a\in\mathcal{A}}Q_{t}(S_{t+1},a)-Q_{t}(S_{t},A_{t})\right)+\zeta&\text{if
}(s,a)=(S_{t},A_{t})\\\ Q_{t}(s,a)+\zeta&\text{otherwise.}\end{array}\right.$

Hyperparameters include a discount factor $\gamma\in(0,1)$, a stepsize
$\alpha\in(0,1)$, and an optimistic boost $\zeta\in\mathbb{R}_{+}$. Each
action $A_{t}$ is sampled uniformly from
$\operatorname*{arg\,max}_{a\in\mathcal{A}}Q_{t}(S_{t},a)$.

To interpret this algorithm, consider situational state dynamics generated by
a latent MDP, identified by a tuple $(\mathcal{S},\mathcal{A},r,P,S_{0})$.
Here, $P$ is a random variable that specifies transition probabilities
$P_{a,s,s^{\prime}}$ for actions $a\in\mathcal{A}$ and situational states
$s,s^{\prime}\in\mathcal{S}$. In particular,
$\mathbb{P}(S_{t+1}|P,A_{t},S_{t})=P_{A_{t},S_{t},S_{t+1}}$ for all $t$. If
the hyperparameters $\gamma$, $\alpha$, and $\zeta$ anneal over time at
suitable rates to $1$, $0$, and $0$, along the lines a more sophisticated
version of Q-learning analyzed by Dong et al. [2022], the sequence
$(Q_{t}:t\in\mathbb{Z}_{+})$ should converge to the optimal action value
function of the MDP. By the same token, the agent would attain optimal average
reward.

Versions of Q-learning permeate the RL literature. The one we have described
presents some features that are worth discussing in relation to continual
learning. First, action values are boosted by exploration bonuses, as
considered by Sutton [1990], but in a manner that incentivizes visits to
state-action pairs that have not been visited for a long time even if they
have already been visited many times. Second, unlike common treatments that
assume the aforementioned Markov property, our algorithm applies more broadly.
It suffices for $S_{t}$ to enable useful predictions of value that guide
effective decisions rather than approximate the state of the environment,
which could be far more complex. This suits the spirit of continual learning,
since the subject is oriented toward addressing very complex environments.
Another noteworthy feature is that the hyperparameters $\gamma$, $\alpha$, and
$\zeta$ are fixed. If the situational state dynamics were stationary,
annealing hyperparameters over time is beneficial. However, as we will further
discuss in Section 6.3, fixed parameters fare better in the face of
nonstationarity.

####  2.3.4 Supervised Learning

Much of the literature on continual learning focuses on supervised learning
(SL). As noted by Khetarpal et al. [2022], continual SL is a special case of
reinforcement learning. In particular, take each observation to be a data pair
$O_{t}=(Y_{t},X_{t})$, consisting of a label $Y_{t}$ assigned to the previous
input $X_{t-1}$ and a next input $X_{t}$. Labels take values in a finite set
$\mathcal{Y}$ and inputs take values in a set $\mathcal{X}$ which could be
finite, countable, or uncountable. The set $\mathcal{O}$ of observations is a
product $\mathcal{Y}\times\mathcal{X}$. Take each action $A_{t}$ to be a
predictive distribution $P_{t}$, which assigns a probability $P_{t}(y)$ to
each label $y\in\mathcal{Y}$. Hence, $P_{t}$ takes values in a unit simplex
$\Delta_{\mathcal{Y}}$. We view $P_{t}$ as a prediction of the label $Y_{t+1}$
that will be assigned to the input $X_{t}$. The observation probability
function $\rho$ samples the next data pair $O_{t+1}=(Y_{t+1},X_{t+1})$ in a
manner that depends on history only through past observations, not past
actions. Finally, take the reward function to be $r(H_{t},A_{t},O_{t+1})=\ln
P_{t}(Y_{t})$. With this formulation, average reward is equivalent to average
negative log-loss:

$\overline{r}_{\pi}=\liminf_{T\rightarrow\infty}\mathbb{E}_{\pi}\left[\frac{1}{T}\sum_{t=0}^{T-1}\ln
P_{t}(Y_{t+1})\right].$ (2)

This is a common objective used in online supervised learning. The following
agent is designed to minimize log-loss. Recall that $\Delta_{\mathcal{Y}}$
denotes the unit simplex or, equivalently, the set of probability vectors with
one component per element of $\mathcal{Y}$.

######  Example 6.

(incremental deep learning) Consider an input space $\mathcal{X}$ and finite
set of labels $\mathcal{Y}$. This agent is designed to interface with actions
$\mathcal{A}=\Delta_{\mathcal{Y}}$ and observations
$\mathcal{O}=\mathcal{Y}\times\mathcal{X}$. Consider a deep neural network
with a softmax output node. The inference process maps an input $X_{t}$ to a
predictive distribution $P_{t}(\cdot)=f_{\theta_{t}}(\cdot|X_{t})$. Here, $f$
is an abstract representation of the neural network and $\theta_{t}$ is the
vector of parameters (weights and biases) at time $t$. Trained online via
stochastic gradient descent (SGD) with a fixed stepsize to reduce log-loss,
these parameters evolve according to

$\theta_{t+1}=\theta_{t}+\alpha\nabla\ln f_{\theta_{t}}(Y_{t+1}|X_{t}).$

This is a special case of our general reinforcement learning formulation, with
action $A_{t}=P_{t}$, observation $O_{t+1}=(Y_{t+1},X_{t+1})$, and reward
$r(H_{t},A_{t},O_{t+1})=\ln P_{t}(Y_{t+1})$.

Note that we could alternatively consider average accuracy as an objective by
taking the action to be a label $A_{t}=\hat{Y}_{t+1}$. This label could be
generated, for example, by sampling uniformly from
$\operatorname*{arg\,max}_{y\in\mathcal{Y}}P_{t}(y)$. A reward function
$r(H_{t},A_{t},O_{t+1})=\mathbbm{1}(Y_{t+1}=\hat{Y}_{t+1})$ can then be used
to express accuracy. This is perhaps the objective most commonly used by
applied deep learning researchers.

The incremental deep learning agent is designed for a prototypical supervised
learning environment, where the relationship between inputs and labels is
characterized by a random latent function $F$. In particular, $F\perp X_{0:t}$
and $\mathbb{P}(Y_{t+1}\in\cdot|F,H_{t})=F(\cdot|X_{t})$.

The agent can also be applied to a nonstationary supervised learning
environment, where the latent function varies over time, taking the form of a
stochastic process $(F_{t}:t\in\mathbb{Z}_{+})$. With this variation,
$F_{t}\perp X_{0:t}$ and
$\mathbb{P}(Y_{t+1}\in\cdot|F_{t},H_{t})=F_{t}(\cdot|X_{t})$. However, due to
loss of plasticity, incremental deep learning does not perform as well in such
an environment as one would hope [Dohare et al., 2021]. In particular, while
the nonstationarity makes it important for the agent to continually learn, its
ability to learn from new data degrades over time. A simple alternative
addresses this limitation by periodically replacing the model under use with a
new one, trained from scratch on recent data.

######  Example 7.

(model replacement) Given a neural network architecture and algorithm that
trains the model on a fixed batch of $N$ data pairs, one can design a
continual supervised learning agent as follows. At each time
$t=0,\tau,2\tau,\ldots$, reinitialize the neural network parameters and train
on $N$ most recent data pairs $(X_{t-n},Y_{t+1-n}:n=1,\ldots,N)$. No further
training occurs until time $t+\tau$, when the model is reinitialized and
retrained. Each prediction $A_{t}=P_{t}$ is given by
$P_{t}(\cdot)=f_{\theta_{t}}(\cdot|X_{t})$, where $\theta_{t}$ is the most
recent model. In particular, $\theta_{t+1}=\theta_{t}$ unless $t$ is a
multiple of $\tau$. The hyperparameters $\tau$ and $N$ specify the replacement
period and number of data pairs in each training batch.

This approach to continual learning is commonly used in production systems.
For example, consider an agent that at the end of each $t$th day predicts the
next day’s average electricity spot price $Y_{t+1}$. A prototypical system
might, at the end of each month, initialize a neural network and train it on
the preceding twelve months of data. Then, this model could be used over the
subsequent month, at the end of which the next replacement arrives. The reason
for periodically replacing the model is that very recent data is most
representative of future price patterns, which evolve with the changing
electricity market.

The reason for not replacing the model more frequently is the cost of
training. There are a couple reasons for training only on recent history, in
this case over the past twelve months. One is that recent data tends to best
represent patterns that will recur in the future. However, this does not in
itself prevent use of more data; given sufficient computation, it may be
beneficial to train on all history, with data pairs suitably weighted to
prioritize based on recency. The binding constraint is on computation, which
scales with the amount of training data.

While model replacement is a common approach to continual learning, it is
wasteful in and limited by its use of computational resources. In particular,
each new model does not leverage computation invested in past models because
it is trained from scratch. Developing an incremental training approach that
affords a model benefits from all computation carried out since inception
remains an important challenge to the field. Dohare et al. [2021] propose one
approach. The subject remains an active area of research, motivated by
limitations of the model replacement approach. These limitations also
highlight the need for computational constraints in formulating a coherent
objective for continual learning that incentivizes better agent designs.

###  2.4 Computational Constraints

Traditional machine learning paradigms such as supervised learning make use of
fixed training datasets. A continual learning agent, on the other hand,
processes endless data stream. An agent with bounded computational resources,
regardless of scale, cannot afford to query every data point in its history
$H_{t}$ at each time step because this dataset grows indefinitely. Instead,
such an agent must act based on a more concise representation of historical
information. In complex environments, this representation will generally forgo
knowledge, some of which could have been used given greater computational
resources. The notion that more compute ought to always be helpful in complex
environments may be intuitively obvious. Nevertheless, it is worth pointing
out corroboration by extensive empirical evidence from training large models
on text corpi, where performance improves steadily along the range of feasible
compute budgets [Brown et al., 2020, Hoffmann et al., 2022, Rae et al., 2022,
Smith et al., 2022, Thoppilan et al., 2022].

In order to reflect the gating nature of computational resources in continual
learning, we introduce a per-timestep computation constraint, as considered,
for example, by Bagus et al. [2022], Lesort [2020], Prabhu et al. [2023b].
This specializes the continual learning problem formulation of Abel et al.
[2023], which recognizes that constraints on the set of feasible agent
policies give rise to continual learning behavior but does not focus on
computation as the gating resource. As an objective for continual learning we
propose maximization of average reward subject to this constraint on per-
timestep computation. We believe that such a constraint is what gives rise to
salient challenges of continual learning, such as catastrophic forgetting and
loss of plasticity. Our theoretical analysis and empirical case studies will
serve to motivate and justify this view.

Constraining per time step compute gives rise to our formulation of
computation-constrained reinforcement learning:

$\begin{split}\max_{\pi}&\quad\overline{r}_{\pi}\\\
\text{s.t.}&\quad\text{computational constraint}.\end{split}$ (3)

The nature of practical computational constraints and which is binding vary
with prevailing technology and agent designs. For example, if calculations are
carried out in parallel across an ample number of processors, it could be the
channels for communication among them pose a binding constraint on overall
computation. Or if agents are designed to use a very large amount of computer
memory, that can become the binding constraint. Rather than study the
capabilities of contemporary computer technologies to accurately identify
current constraints, our above formulation intentionally leaves the constraint
ambiguous. For the purposes of theoretical analysis and case studies presented
in the remainder of the paper, we will usually assume all computation is
carried out on a single processor that can execute a fixed number of serial
floating point operations per time step, and that this is the binding
constraint. We believe that insights generated under this assumption will
largely carry over to formulations involving other forms of computational
constraints.

While maximizing average reward subject to a computation constraint offers a
coherent objective, an exact solution even for simple, let alone complex,
environments is likely to be intractable. Nevertheless, a coherent objective
is valuable for assessing and comparing alternative agent designs. Indeed,
algorithmic ingredients often embedded in RL agents, such as Q-learning,
neural networks, SGD, and exploration schemes such as optimism and Thompson
sampling are helpful because they enable a favorable tradeoff between average
reward and computation. Further, these ideas are scalable in the sense that
they can leverage greater computational resources when available. As Sutton
[2019] argues, with steady advances in computer technology, agent designs that
naturally improve due to these advances will stand the test of time, while
those that do not will phase out.

###  2.5 Learning Complex Skills over a Long Lifetime

An aspiration of continual learning is to design agents that exhibit ever more
complex skills, building on skills already developed [Ring, 1994]. As opposed
to paradigms that learn from a fixed data set, this aspiration is motivated by
the continual growth of the agent’s historical data set, and thus, information
available to the agent. With this perspective, continual learning researchers
often ask whether specific design ingredients are really needed or if they
should be supplanted by superior skills that the agent can eventually learn.
For example, should an agent implement a hard-coded exploration scheme or
learn to explore? Or ought an agent apply SGD to update its parameters rather
than learn on its own adaptation algorithm?

More concretely, consider the agent of Example 6, which implements SGD with a
fixed stepsize. The performance of such an agent may improve with a stepsize
adaptation scheme such as incremental delta-bar-delta (IDBD), which produces
stepsizes that vary across parameters and time [Sutton, 1992]. With such a
stepsize adaptation scheme, the agent can be seen as learning how to learn
more effectively than fixed stepsize SGD. However, IDBD requires maintaining
and updating three times as many parameters, and thus, increased compute. If
compute were not a constraint, one could take things even further and design a
more complex update procedure that requires not only computing gradients but
also Hessians. For neural networks of practical scale, the associated
computational requirements would be egregious.

As our discussion of two alternative to fixed stepsize SGD suggests, there is
always room to improve average reward by designing the agent to learn more
sophisticated skills. However, as we will discuss in the next section, this
complexity is constrained by the agent’s information capacity, which is gated
by computational constraints. There are always multiple ways to invest this
capacity. For example, instead of maintaining statistics required by a
stepsize adaptation scheme, a designer could increase the size of the neural
network, which might also increase average reward.

Related to this is the stability-plasticity dilemma [McCloskey and Cohen,
1989, Ratcliff, 1990], a prominent subject in the continual learning
literature. Stability is the resilience to forgetting useful skills, while
plasticity is the ability to acquire new skills. Empirical studies demonstrate
that agents do forget and that, as skills accumulate, become less effective at
acquiring new skills [Dohare et al., 2021, Goodfellow et al., 2013,
Kirkpatrick et al., 2017, Lesort, 2020]. Researchers have worked toward agent
designs that improve stability and plasticity. But limited information
capacity poses a fundamental tradeoff. For example, Mirzadeh et al. [2022] and
Dohare et al. [2021] demonstrate that larger neural networks forget less and
maintain greater plasticity. And as we will further discuss in Section 5, in
complex environments, constrained agents must forget and/or lose plasticity,
with improvements along one dimension coming at a cost to the other.

### Summary

  * •

An environment is characterized by a tuple $(\mathcal{A},\mathcal{O},\rho)$,
comprised of a set of actions, a set of observations, and an observation
probability function.

  * •

The agent’s experience through time $t$ forms a history
$H_{t}=(A_{0},O_{1},\ldots,A_{t-1},O_{t})$.

  * •

Observations are generated as though

$O_{t+1}\sim\rho(\cdot|H_{t},A_{t}).$

  * •

The behavior of an agent is characterized by an agent policy $\pi$. Actions
are generated as though

$A_{t}\sim\pi(\cdot|H_{t}).$

  * •

The designer’s preferences are encoded in terms of a reward function $r$,
which generates rewards

$R_{t+1}=r(H_{t},A_{t},O_{t+1}).$

  * •

The average reward attained by an agent policy $\pi$ in an environment
$(\mathcal{A},\mathcal{O},\rho)$ is

$\overline{r}_{\pi}=\liminf_{T\rightarrow\infty}\mathbb{E}_{\pi}\left[\frac{1}{T}\sum_{t=0}^{\infty}R_{t+1}\right].$

  * •

Design of a continual learning agent can be framed as maximizing average
reward subject to a per-timestep computational constraint:

$\begin{split}\max_{\pi}&\quad\overline{r}_{\pi}\\\
\text{s.t.}&\quad\text{computational constraint}.\end{split}$

  * •

Continual supervised learning with log-loss is a special case in which

    * –

$\mathcal{O}=\mathcal{X}\times\mathcal{Y}$, where $\mathcal{X}$ and
$\mathcal{Y}$ are input and label sets,

    * –

$\mathcal{A}=\Delta_{\mathcal{Y}}$ is the unit simplex of predictive
distributions,

    * –

each observation is a pair $O_{t+1}=(Y_{t+1},X_{t+1})$ comprising a label
assigned to the previous input $X_{t}$ and the next input $X_{t+1}$,

    * –

the observation distribution $\rho(\cdot|H_{t},A_{t})$ depends on
$(H_{t},A_{t})$ only through past observations $O_{1:t}$,

    * –

the reward function expresses the negative log-loss $R_{t+1}=\ln
P_{t}(Y_{t+1})$.

Another common reward function used in supervised learning expresses the
accuracy $R_{t+1}=\mathbbm{1}(Y_{t+1}=\hat{Y}_{t+1})$, where the action is a
label $A_{t}=\hat{Y}_{t+1}$.

##  3 Agent State and Information Capacity

Practical agent designs typically maintain a bounded summary of history, which
we refer to as the agent state and which is used to select actions.
Information encoded in the agent state is constrained to regulate
computational requirements. In this section, we formalize these concepts in
information-theoretic terms, along the lines of Jeon et al. [2023], Lu et al.
[2021], and explore their relation to agent performance. The tools we develop
allow us to more clearly distinguish continual from convergent learning and
define and analyze stability and plasticity, as we do in Sections 4 and 5.

###  3.1 Agent State

Computational constraints prevent an agent from processing every element of
history at each time step because the dataset grows indefinitely. To leverage
more information than can be efficiently accessed from history, the agent
needs to maintain a representation of knowledge that enables efficient
computation of its next action. In particular, the agent must implement a
policy $\pi$ that depends on a statistic $U_{t}$ derived from $H_{t}$, rather
than directly on $H_{t}$ itself. Such a policy samples each action according
to

$A_{t}\sim\pi(\cdot|U_{t}).$

The statistic $U_{t}$ must itself be computed using budgeted resources. An
agent that computes $U_{t}$ directly from $H_{t}$ would run into constraints
of the same sort that motivated construction of agent state in the first
place. In particular, the agent cannot accesses all history within a time step
and must maintain an agent state that facilitates efficient computation of the
next agent state. To this end, $U_{t}$ serves two purposes: computation of
$A_{t}$ and $U_{t+1}$. Specifically, there must be an update function $\psi$
such that

$U_{t+1}\sim\psi(\cdot|U_{t},A_{t},O_{t+1}).$

This sort of incremental updating allows $U_{t+1}$ to selectively encode
historical information while amortizing computation across time. Since $U_{t}$
includes all information about $H_{t}$ that the agent will subsequently use,
it can be thought of as a state; thus the term agent state.

Agents presented in Section 2.3 each use a highly compressed representation of
history as agent state. In the scalar LMS algorithm of Example 3, the agent
state $U_{t}=\mu_{t}$ is an estimate of a latent variable $\theta_{t}$. The
agent state $U_{t}=(\mu_{t,a},\Sigma_{t,a}:a\in\mathcal{A})$ of Example 4
includes mean and variance estimates for each action. The optimistic
Q-learning agent (Example 5) maintains a situational state and action value
function as its agent state $U_{t}=(S_{t},Q_{t})$. Finally, with supervised
deep learning, as described in Example 6, the agent state
$U_{t}=(X_{t},\theta_{t})$ includes the current input and a vector of neural
network parameters. If the agent were also to maintain a replay buffer $B_{t}$
of recent action-observation pairs for supplemental training, the replay
buffer would also reside within the agent state
$U_{t}=(X_{t},\theta_{t},B_{t})$. In each of these examples, the agent state
is updated incrementally according to
$U_{t+1}\sim\psi(\cdot|U_{t},A_{t},O_{t+1})$ for some function $\psi$.

###  3.2 Information Content

Intuitively, the agent state retains information from history to select
actions and update itself. But how ought this information be quantified? In
this section, we offer a formal approach based on information theory [Shannon,
1948]. Attributing precise meaning to information affords coherent
characterization and analysis of information retained by an agent as well as
forgetting and plasticity, which are subjects we will discuss in subsequent
sections.

The agent state $U_{t}$ is a random variable since it depends on other random
variables, including the agent’s experience $H_{t}$ through that time and
possible algorithmic randomness arising in sampling from
$\psi(\cdot|U_{t-1},A_{t-1},O_{t})$. A simple way of quantifying the
information content of $U_{t}$ is in terms of the minimal number of bits that
suffices for a lossless encoding. Or, using a unit of measurement more
convenient for analysis of machine learning, the number of nats; there are
$\ln 2$ nats per bit.

For reasons we will discuss, at large scale in terms of environment complexity
and model size, this number ought to be well-approximated by the entropy
$\mathbb{H}(U_{t})$. The entropy of a random variable $B$ with countable range
is defined by

$\mathbb{H}(B)=\mathbb{E}[-\ln\mathbb{P}(B)].$

More generally, if the range is uncountable then entropy is defined by
$\mathbb{H}(B)=\sup_{f\in\mathcal{F}_{\mathrm{finite}}}\mathbb{H}(f(B))$,
where $\mathcal{F}_{\mathrm{finite}}$ is the set of functions that map
$\mathcal{U}$ to a finite range.

Let us now discuss conditions under and the sense in which entropy closely
approximates the number of nats that suffices for a lossless encoding.
Consider a fixed environment and an agent design that is indexed by a
parameter $M\in\mathbb{Z}_{++}$, with memory requirements that increase with
$M$. Suppose that, for each $M$, the agent state $U_{t,1:M}$ is a vector with
$M$ components. Further, suppose that these components are the first $M$
elements of a stationary stochastic process $(U_{t,m}:m\in\mathbb{Z}_{++})$.
Under this assumption, $\mathbb{H}(U_{t,1:M})=\Theta(M)$. As a simple example,
$(U_{t,m}:m\in\mathbb{Z}_{++})$ could be an iid sequence, with each $U_{t,m}$
representing a feature extracted from the history $H_{t}$. If these features
are ordered from most to least important for selecting effective actions, it
is natural to retain only the first $M$ in the agent state if that exhausts
the memory budget. A standard result in information theory implies that, for
any $\epsilon>0$, there is a $\mathbb{H}(U_{t,1:M})+\epsilon M$ nat encoding
that affords lossless recovery of $U_{t,1:M}$ with a probability that
approaches one as $M$ grows [Cover and Thomas, 2012, Theorem 5.4.2]. Hence, as
$M$ grows, the percentage difference between $\mathbb{H}(U_{t,1:M})$ and the
required number of nats vanishes.

The preceding argument assumed the agent state $U_{t}$ to be a high-
dimensional vector with components generated by a stationary stochastic
process. While this is not typically the case, we expect the key insight –
that $\mathbb{H}(U_{t})$ closely approximates, in percentage terms, the number
of nats that suffices for lossless encoding – to extend broadly to contexts
where the agent state is a large object and the environment is much more
complex, even than that. Intuitively and loosely speaking, this insight
applies when the information encoded in $U_{t}$ originates from many
independent random sources. A complex environment ought to afford an enormous
diversity of random sources, and a large agent state ought to encode
information from a large number. It is exactly such contexts that motivate the
subject of continual learning.

###  3.3 Information Capacity

Recall our continual learning objective:

$\displaystyle\max_{\pi}$ $\displaystyle\quad\overline{r}_{\pi}$ s.t.
$\displaystyle\quad\text{computational constraint}.$

The nature of the computational constraint was purposely left ambiguous. If
computer memory is binding, that directly constrains information content. We
will assume for the remainder of this paper that the binding constraint is the
number of floating point operations that can be carried out per time step
(FLOPS). This does not necessarily constrain information content. For example,
even if we take the agent state to be $U_{t}=H_{t}$ and the entropy
$\mathbb{H}(U_{t})$ grows indefinitely, an agent can efficiently select each
action based on sparsely queried data, perhaps by randomly sampling a small
number of action-observation pairs from history. However, as a practical
matter, common agent designs apply computation in ways that limit the amount
of information that the agent retains. We refer to the constraint on
information content of agent state as the information capacity.

A constraint on FLOPS limits information content when an agent is designed so
that computation grows with information capacity. Supervised deep learning, as
described in Example 6, offers a concrete case. Recall that, over each $t$th
time step, the agent carries out a single SGD step:

$\theta_{t+1}=\theta_{t}+\alpha\nabla\ln f_{\theta_{t}}(Y_{t+1}|X_{t}).$

Each data pair $(X_{t},Y_{t+1})$ is immediately processed when observed, then
discarded. Compute per data pair grows proportionally with the number of model
parameters. Hence, a computation constraint restricts the number of model
parameters. Conversely, the number of model parameters determines per-timestep
computation. If each parameter is encoded by $K$ nats, a neural network model
with $N$ parameters can encode $NK$ nats of information. We refer to this as
the physical capacity of the neural network.

While information content is constrained not to exceed the physical capacity,
large neural networks trained via SGD actually use only a fraction of their
physical capacity to retain information garnered from data. Much of the $NK$
nats instead serves to facilitate computation. Therefore, the physical
capacity constrains the information capacity to far fewer nats:
$\mathbb{H}(U_{t})\ll NK$.

Similar reasoning applies if the agent state is expanded to include a replay
buffer. In this case, the physical capacity is $NK+B$ nats, if $B$ nats is
used to store the replay buffer. Again, the information capacity is
constrained to far fewer nats than the physical capacity. As before only a
fraction of the neural network’s physical capacity stores information content.
But also, a replay buffer that stores raw data from history can typically be
compressed losslessly to occupy a much smaller number of nats.

###  3.4 Performance versus Information Capacity

If the agent makes efficient use of its information capacity, it is natural to
expect agent performance to increase as this constraint is loosened.
Information theory offers an elegant interpretation of this relation. To
illustrate this, let us work through this interpretation for the case of
continual SL.

####  3.4.1 Prediction Error

Recall that, in our continual SL formulation, the agent’s action is a
predictive distribution $A_{t}=P_{t}$ and the reward is taken to be
$r(H_{t},A_{t},O_{t+1})=\ln P_{t}(Y_{t+1})$. Hence, the objective is to
minimize average log-loss. To enable an elegant analysis, we define a
prediction

$P^{*}_{t}=\mathbb{P}(Y_{t+1}=\cdot|H_{t})=\operatorname*{arg\,max}_{Q\in\Delta_{\mathcal{Y}}}\mathbb{E}[\ln
Q(Y_{t+1})|H_{t}]$ (4)

as a gold standard. The expected reward $\mathbb{E}[\ln
P^{*}_{t}(Y_{t+1})|H_{t}]$ represents the largest that a computationally
unconstrained agent can attain given the history $H_{t}$. The difference
between this gold standard value and the expected reward attained by the agent
is expressed by the KL-divergence:

$\displaystyle{\mathbf{d}}_{\rm
KL}(P^{*}_{t}\|P_{t})=\sum_{y\in\mathcal{Y}}P^{*}_{t}(y)\ln\frac{P^{*}_{t}(y)}{P_{t}(y)}=\mathbb{E}[\ln
P^{*}_{t}(Y_{t+1})-\ln P_{t}(Y_{t+1})|H_{t}].$

This KL-divergence serves as a measure of error between the agent’s prediction
$P_{t}$ and the gold standard $P^{*}_{t}$. Maximizing average reward is
equivalent to minimizing this prediction error, since

$\underbrace{\mathbb{E}[\ln
P_{t}(Y_{t+1})]}_{\text{reward}}=\underbrace{\mathbb{E}[\ln
P^{*}_{t}(Y_{t+1})]}_{\text{optimal
reward}}-\underbrace{\mathbb{E}[{\mathbf{d}}_{\rm
KL}(P^{*}_{t}\|P_{t})]}_{\text{prediction error}}$ (5)

and $\mathbb{E}[\ln P^{*}_{t}(Y_{t+1})]$ does not depend on $P_{t}$.

When making its prediction $P_{t}$, the agent only has information supplied by
its agent state $U_{t}$. The best prediction that can be generated based on
this information is

$\tilde{P}_{t}=\mathbb{P}(Y_{t+1}=\cdot|U_{t})=\operatorname*{arg\,max}_{Q\in\Delta_{\mathcal{Y}}}\mathbb{E}[\ln
Q(Y_{t+1})|U_{t}].$ (6)

If the agent’s prediction $P_{t}$ differs from $\tilde{P}_{t}$, the error
attained by the agent decomposes into informational versus inferential
components, as established by the following result.

######  Theorem 1.

For all $t$,

$\underbrace{\mathbb{E}[{\mathbf{d}}_{\rm
KL}(P^{*}_{t}\|P_{t})]}_{\mathrm{prediction\
error}}=\underbrace{\mathbb{E}[{\mathbf{d}}_{\rm
KL}(P^{*}_{t}\|\tilde{P}_{t})]}_{\mathrm{informational\
error}}+\underbrace{\mathbb{E}[{\mathbf{d}}_{\rm
KL}(\tilde{P}_{t}\|P_{t})]}_{\mathrm{inferential\ error}}.$

###### Proof.

For all $t$,

$\displaystyle\mathbb{E}[{\mathbf{d}}_{\rm KL}(P^{*}_{t}\|P_{t})]=$
$\displaystyle\mathbb{E}[\ln P^{*}_{t}(Y_{t+1})-\ln P_{t}(Y_{t+1})]$
$\displaystyle=$ $\displaystyle\mathbb{E}[\mathbb{E}[\ln
P^{*}_{t}(Y_{t+1})-\ln\tilde{P}_{t}(Y_{t+1})|H_{t}]]+\mathbb{E}[\mathbb{E}[\ln\tilde{P}_{t}(Y_{t+1})-\ln
P_{t}(Y_{t+1})|U_{t}]]$ $\displaystyle=$
$\displaystyle\mathbb{E}[{\mathbf{d}}_{\rm
KL}(P^{*}_{t}\|\tilde{P}_{t})]+\mathbb{E}[{\mathbf{d}}_{\rm
KL}(\tilde{P}_{t}\|P_{t})].$

∎

####  3.4.2 Informational Error Quantifies Absent Information

The informational error can be interpreted as historical information absent
from the agent state $U_{t}$ but that would be useful for predicting
$Y_{t+1}$. This can be expressed in elegant information theoretic terms. To do
so, we first review a few information measures for which Figure 4 illustrates
intuitive relationships. Let $B$ and $C$ be random variables, and to simplify
math, though the concepts extend to address uncountable ranges, let us assume
for this discussion that each has countable range. The conditional entropy of
$B$ conditioned on $C$ is defined by

$\mathbb{H}(B|C)=\mathbb{E}\left[-\ln\mathbb{P}(B|C)\right].$

It follows from the definition of conditional probability that
$\mathbb{H}(B|C)=\mathbb{E}\left[-\ln\mathbb{P}(B,C)+\ln\mathbb{P}(C)\right]=\mathbb{H}(B,C)-\mathbb{H}(C)$.
This represents the expected number of nats that remain to be revealed by $B$
after $C$ is observed, or the union of the two discs in the venn diagram minus
the content of the blue disc. The mutual information between $B$ and $C$ is
defined by

$\mathbb{I}(B;C)=\mathbb{H}(B)-\mathbb{H}(B|C)=\mathbb{H}(C)-\mathbb{H}(C|B)=\mathbb{I}(C;B).$

This represents the number of nats shared by $B$ and $C$, depicted as the
intersection between the two discs. If the variables are independent then
$\mathbb{I}(B;C)=0$. Finally, the mutual conditional information between $B$
and $C$, conditioned on a third random variable $D$, is defined by

$\mathbb{I}(B;C|D)=\mathbb{I}(B;C,D)-I(B;D).$

This represents information remaining in the intersection of $B$ and $C$ after
$D$ is observed.

Figure 4: Venn diagram relating various information measures.

The following result establishes that the informational error
$\mathbb{E}[{\mathbf{d}}_{\rm KL}(P^{*}_{t}\|\tilde{P}_{t})]$ equals the
information $\mathbb{I}(Y_{t+1};H_{t}|U_{t})$ that the history $H_{t}$
presents about $Y_{t+1}$ but that is absent from $U_{t}$.

######  Theorem 2.

For all $t$,

$\underbrace{\mathbb{E}[{\mathbf{d}}_{\rm
KL}(P^{*}_{t}\|\tilde{P}_{t})]}_{\mathrm{informational\
error}}=\underbrace{\mathbb{I}(Y_{t+1};H_{t}|U_{t})}_{\mathrm{absent\ info}}.$

###### Proof.

From the definitions of conditional entropy, $P^{*}_{t}$, and $\tilde{P}_{t}$,
we have $\mathbb{H}(Y_{t+1}|H_{t})=\mathbb{E}[-\ln P^{*}_{t}(Y_{t+1})]$ and
$\mathbb{H}(Y_{t+1}|U_{t})=\mathbb{E}[-\ln\tilde{P}_{t}(Y_{t+1})]$. It follows
that,

$\displaystyle\mathbb{E}[{\mathbf{d}}_{\rm KL}(P^{*}_{t}\|\tilde{P}_{t})]=$
$\displaystyle\mathbb{E}[\ln P^{*}_{t}(Y_{t+1})-\ln\tilde{P}_{t}(Y_{t+1})]$
$\displaystyle=$
$\displaystyle\mathbb{H}(Y_{t+1}|U_{t})-\mathbb{H}(Y_{t+1}|H_{t})$
$\displaystyle=$
$\displaystyle\mathbb{H}(Y_{t+1}|U_{t})-\mathbb{H}(Y_{t+1}|U_{t},H_{t})$
$\displaystyle=$ $\displaystyle\mathbb{I}(Y_{t+1};H_{t}|U_{t}).$

The third equality follows from the fact that $Y_{t+1}\perp U_{t}|H_{t}$. ∎

####  3.4.3 Information Capacity Constrains Performance

It is natural to think that information capacity can constrain performance.
This relationship is formalized by the following result.

######  Theorem 3.

For all $t$,

$\underbrace{\mathbb{E}[{\mathbf{d}}_{\rm
KL}(P^{*}_{t}\|P^{*}_{0})]}_{\mathrm{uninformed\
error}}-\underbrace{\mathbb{E}[{\mathbf{d}}_{\rm
KL}(P^{*}_{t}\|\tilde{P}_{t})]}_{\mathrm{informational\
error}}=\underbrace{\mathbb{I}(Y_{t+1};U_{t})}_{\mathrm{useful\
info}}\leq\underbrace{\mathbb{H}(U_{t})}_{\mathrm{info}}.$

###### Proof.

For all $t$,

$\displaystyle\mathbb{E}[{\mathbf{d}}_{\rm KL}(P^{*}_{t}\|\tilde{P}_{t})]=$
$\displaystyle\mathbb{I}(Y_{t+1};H_{t}|U_{t})$ $\displaystyle=$
$\displaystyle\mathbb{I}(Y_{t+1};H_{t},U_{t})-\mathbb{I}(Y_{t+1};U_{t})$
$\displaystyle=$
$\displaystyle\mathbb{I}(Y_{t+1};H_{t})-\mathbb{I}(Y_{t+1};U_{t})$
$\displaystyle=$ $\displaystyle\mathbb{E}[{\mathbf{d}}_{\rm
KL}(P^{*}_{t}\|P^{*}_{0})]-\mathbb{I}(Y_{t+1};U_{t}).$

We arrive at the first inequality in our result by rearranging terms. The
second follows from the fact that mutual information between two variables is
bounded by the entropy of each. ∎

Note that
$P^{*}_{0}=\mathbb{P}(Y_{t+1}=\cdot|H_{0})=\mathbb{P}(Y_{t+1}=\cdot)$ is an
uninformed prediction, which is based on no data. The left-hand-side
expression $\mathbb{E}[{\mathbf{d}}_{\rm
KL}(P^{*}_{t}\|P^{*}_{0})]-\mathbb{E}[{\mathbf{d}}_{\rm
KL}(P^{*}_{t}\|\tilde{P}_{t})]$ is the reduction in informational error
relative to an uninformed prediction. The middle expression
$\mathbb{I}(Y_{t+1};U_{t})$ is the degree to which the agent state $U_{t}$
informs the agent about $Y_{t+1}$. The right-hand-side expression
$\mathbb{H}(U_{t})$ is the information content of the agent state. If the
information capacity constrains this content to be small, that in turn
constrains the reduction in error. When the constraint is binding, larger
information capacity affords smaller errors.

### Summary

  * •

An agent state $U_{t}$ is a summary of the history $H_{t}$ maintained to
facilitate efficient computation of each action

$A_{t}\sim\pi(\cdot|U_{t}),$

and subsequent agent state

$U_{t+1}\sim\psi(\cdot|U_{t},A_{t},O_{t+1}).$

The agent policy of an agent designed in this way is characterized by the pair
$(\psi,\pi)$.

  * •

The information content of agent state is the number of nats required to
encode it. At large scale and under plausible technical conditions, this is
well-approximated by the entropy $\mathbb{H}(U_{t})$.

  * •

An agent’s information capacity is a constraint on the information content and
is typically limited by computational resources.

  * •

Information capacity limits agent performance, which we measure in terms of
average reward.

  * •

In the special case of continual supervised learning with rewards $R_{t+1}=\ln
P_{t}(Y_{t+1})$, expected reward is determined by prediction error via

$\underbrace{\mathbb{E}[\ln
P_{t}(Y_{t+1})]}_{\text{reward}}=\underbrace{\mathbb{E}[\ln
P^{*}_{t}(Y_{t+1})]}_{\text{optimal
reward}}-\underbrace{\mathbb{E}[{\mathbf{d}}_{\rm
KL}(P^{*}_{t}\|P_{t})]}_{\text{prediction error}},$

where $P_{t}$ denotes the agent’s prediction and
$P_{t}^{*}(\cdot)=\mathbb{P}(Y_{t}=\cdot|H_{t})$ is the optimal prediction.
Prediction error decomposes into informational and inferrential errors:

$\underbrace{\mathbb{E}[{\mathbf{d}}_{\rm
KL}(P^{*}_{t}\|P_{t})]}_{\mathrm{prediction\
error}}=\underbrace{\mathbb{E}[{\mathbf{d}}_{\rm
KL}(P^{*}_{t}\|\tilde{P}_{t})]}_{\mathrm{informational\
error}}+\underbrace{\mathbb{E}[{\mathbf{d}}_{\rm
KL}(\tilde{P}_{t}\|P_{t})]}_{\mathrm{inferential\ error}},$

where $\tilde{P}_{t}(\cdot)=\mathbb{P}(Y_{t}=\cdot|U_{t})$ is the best
prediction that can be produced based on the agent state. The informational
error is equal to the information absent from agent state that would improve
the prediction:

$\underbrace{\mathbb{E}[{\mathbf{d}}_{\rm
KL}(P^{*}_{t}\|\tilde{P}_{t})]}_{\mathrm{informational\
error}}=\underbrace{\mathbb{I}(Y_{t+1};H_{t}|U_{t})}_{\mathrm{absent\ info}}.$

Informational error is limited by the information capacity according to

$\underbrace{\mathbb{E}[{\mathbf{d}}_{\rm
KL}(P^{*}_{t}\|P^{*}_{0})]}_{\mathrm{uninformed\
error}}-\underbrace{\mathbb{E}[{\mathbf{d}}_{\rm
KL}(P^{*}_{t}\|\tilde{P}_{t})]}_{\mathrm{informational\
error}}=\underbrace{\mathbb{I}(Y_{t+1};U_{t})}_{\mathrm{useful\
info}}\leq\underbrace{\mathbb{H}(U_{t})}_{\mathrm{info}}.$

##  4 Vanishing-Regret Versus Continual Learning

Traditional framings of machine learning view the agent as accumulating
knowledge about a fixed latent variable, which we refer to as a learning
target. For example, in supervised learning, the learning target is typically
taken to be a mapping from input to label probabilities. As a sanity check on
agent performance, researchers then study regret relative to a hypothetical
agent with privileged knowledge of the learning target. By the same token,
traditional treatments of reinforcement learning center around learning about
a latent MDP, or a derivative, such as a value function or a policy. Any of
these can serve as a learning target, and again, regret analysis serves as a
sanity check on agent performance.

Traditional framings orient agent designs toward ensuring that average regret
vanishes as the dataset grows. To highlight this emphasis, we use the term
vanishing-regret learning. Agents designed in this vein aim to reduce per-
timestep regret, and are viewed as essentially “done” with learning when that
becomes negligible.

Continual learning agents, on the other hand, engage in a perpetual mode of
knowledge acquisition. Unlike vanishing-regret learning, the pace of continual
learning does not taper off. Instead, in the never-ending process, some
information is retained and some forgotten as new information is ingested. The
notion of vanishing regret gives way to understanding this non-transient
behavior.

In this section, we elaborate on this distinction between continual and
vanishing-regret learning. To do so, we formalize the notion of a learning
target and what it means for regret to vanish. We then discuss how
computational constraints incentivize different qualitative behavior. The
contrast offers insight into how and why continual learning agents should be
designed differently. This discussion also leads us to reflect on why we have
taken the environment $\mathcal{E}=(\mathcal{A},\mathcal{O},\rho)$ to be
deterministic or, in other words, known, in contrast to work on vanishing-
regret learning, which typically treats the environment as unknown.

###  4.1 Vanishing-Regret Learning

We begin by motivating the notation of a learning target and then discuss the
role of vanishing regret in traditional machine learning. We leverage
information theory as a lens that affords general yet simple interpretations
of these concepts.

####  4.1.1 Learning Targets, Target Policies, and Vanishing Regret

Recall the coin tossing environment of Example 1. It is natural to think of an
agent as learning about the coin biases from toss outcomes, with an eye toward
settling on a simple policy that selects the coin with favorable bias. This
framing can serve to guide comparisons among alternative agents and give rise
to insight on how design decisions impact performance. For example, one could
study whether each agent ultimately behaves as though it learned the coin
biases. Such an analysis assesses agent performance relative to a benchmark,
which is framed in terms of an agent with privileged knowledge of a learning
target comprised of coin biases and a target policy that selects the favorable
coin.

In the most abstract terms, a learning target is a random variable, which we
will denote by $\chi$. A target policy $\tilde{\pi}$ assigns to each
realization of $\chi$ a random policy. In particular, $\tilde{\pi}_{\chi}$ is
a random variable that takes values in the set of policies. Intuitively,
$\chi$ represents an interpretation of what an agent aims to learn about, and
$\tilde{\pi}_{\chi}$ is the policy the agent would use if $\chi$ were known.
Note that the target policy selects actions with privileged knowledge of the
learning target. We will denote the average reward of the target policy
conditioned on the learning target by

$\overline{r}_{\chi,\tilde{\pi}}=\liminf_{T\rightarrow\infty}\mathbb{E}_{\tilde{\pi}_{\chi}}\left[\frac{1}{T}\sum_{t=0}^{T-1}R_{t+1}\Big{|}\chi\right],$
(7)

where the subscript $\tilde{\pi}_{\chi}$ indicates the policy under which the
conditional expectation is evaluated. Note that
$\overline{r}_{\chi,\tilde{\pi}}$ is a random variable because it depends on
$\chi$. This level of reward may be not attainable by any viable agent policy.
This is because it can rely on knowledge of $\chi$, which the agent does not
observe. An agent policy, on the other hand, generates each action $A_{t}$
based only on the history $H_{t}$. Rather than offer a viable agent policy,
the learning target and target policy serve as conceptual tools that more
loosely guide agent design and analysis.

For each duration $T\in\mathbb{Z}_{++}$, let

$\overline{r}_{\pi,T}=\mathbb{E}_{\pi}\left[\frac{1}{T}\sum_{t=0}^{T-1}R_{t+1}\right]\qquad\text{and}\qquad\overline{r}_{\chi,\tilde{\pi},T}=\mathbb{E}_{\tilde{\pi}_{\chi}}\left[\frac{1}{T}\sum_{t=0}^{T-1}R_{t+1}\Big{|}\chi\right],$

so that $\overline{r}_{\pi}=\liminf_{T\rightarrow\infty}\overline{r}_{\pi,T}$
and
$\overline{r}_{\tilde{\pi},\chi}=\liminf_{T\rightarrow\infty}\overline{r}_{\chi,\tilde{\pi},T}$.
Like $\overline{r}_{\chi,\tilde{\pi},T}$, the limit
$\overline{r}_{\tilde{\pi},\chi}$ is a random variable. We define the average
regret over duration $T$ incurred by $\pi$ with respect to
$(\chi,\tilde{\pi})$ to be

$\overline{\mathrm{Regret}}_{\chi,\tilde{\pi}}(T|\pi)=\mathbb{E}[\overline{r}_{\chi,\tilde{\pi},T}-\overline{r}_{\pi,T}].$
(8)

This represents the expected per-timestep shortfall of the agent policy $\pi$
relative to the target policy $\tilde{\pi}_{\chi}$, which is afforded the
advantage of knowledge about the learning target $\chi$.

We say $\pi$ exhibits vanishing regret with respect to $(\chi,\tilde{\pi})$ if
$\limsup_{T\rightarrow\infty}\overline{\mathrm{Regret}}_{\chi,\tilde{\pi}}(T|\pi)\leq
0$. If rewards are bounded and limits of $\overline{r}_{\chi,\tilde{\pi},T}$
and $\overline{r}_{\pi,T}$ exist then, by the dominated convergence theorem,
$\limsup_{T\rightarrow\infty}\mathbb{E}[\overline{r}_{\chi,\tilde{\pi},T}-\overline{r}_{\pi,T}]\leq\mathbb{E}[\overline{r}_{\chi,\pi}-\overline{r}_{\pi}]$,
and therefore, vanishing regret is implied by
$\mathbb{E}[\overline{r}_{\chi,\tilde{\pi}}-\overline{r}_{\pi}]\leq 0$.
Intuitively, the notation of vanishing regret indicates that $\pi$ eventually
performs at least as well as the target policy $\tilde{\pi}_{\chi}$ in spite
of the latter’s privileged knowledge of $\chi$.

The choice of learning target and target policy are subjective in the sense
that they are not uniquely determined by an agent-environment pair. Rather,
they are chosen as means to interpret the agent’s performance in the
environment. In particular, given $(\chi,\tilde{\pi})$, we can analyze how the
agent learns about $\chi$ and uses that knowledge to make effective decisions.
In this regard, three properties make for useful choices:

  1. 1.

Given knowledge of the learning target $\chi$, an agent can execute
$\tilde{\pi}_{\chi}$ in a computationally efficient manner.

  2. 2.

The target policy $\tilde{\pi}_{\chi}$ attains a desired level of average
reward.

  3. 3.

An agent can learn enough about $\chi$ in reasonable time to perform about as
well as $\tilde{\pi}_{\chi}$.

The first property ensures that knowledge of $\chi$ is actionable, and the
second requires that resulting actions are performant to a desired degree. The
third property ensures that acquiring useful knowledge about $\chi$ is
feasible. These properties afford analysis of performance in terms of whether
and how quickly an agent learns about $\chi$. We will further explore this
sort of analysis in Section 4.1.2. But we close this section with a simple
example of logit data and an agent that produces optimal predictions
conditioned on history. This serves as an introduction to the notion of a
learning target and what makes one useful.

######  Example 8.

(learning targets for logit data) Consider a binary observation sequence
$(O_{t}:t\in\mathbb{Z}_{++})$ that is iid conditioned on a latent variable
$\theta$. In particular, let $\mathcal{O}=\\{0,1\\}$,
$\mathbb{P}(O_{t+1}=1|\theta,H_{t},A_{t})=e^{\theta}/(1+e^{\theta})$, and
$\mathbb{P}(\theta\in\cdot)\sim\mathcal{N}(0,1)$. Each action is a predictive
distribution $A_{t}=P_{t}$ and results in reward $R_{t+1}=\ln P_{t}(O_{t+1})$.
We consider an optimal agent policy $\pi_{*}$, which generates predictive
distributions $P^{*}_{t}\sim\pi_{*}(\cdot|H_{t})$ that perfectly condition on
history: $P^{*}_{t}(\cdot)=\mathbb{P}(O_{t+1}=\cdot|H_{t})$. We will consider
three different choices of learning target $\chi$ together, in each case, with
the target policy $\tilde{\pi}_{\chi}$ that assigns all probability to
$P_{t}^{\chi}=\mathbb{P}(O_{t+1}=\cdot|\chi,H_{t})$. This target policy
executes actions that are optimally conditioned on knowledge of $\chi$ in
addition to history.

For the “obvious” learning target $\chi=\theta$,
$\overline{\mathrm{Regret}}_{\chi,\tilde{\pi}}(T|\pi)$ vanishes at a
reasonable rate, which we will characterize in the next section. Intuitively,
this is because, as data accumulates, the agent is able to produce estimates
of $\theta$ that suffice for accurate predictions.

For contrast, let us now consider two poor choices of learning targets, each
of which represents a different extreme. One is the “uninformative” learning
target $\chi=\emptyset$, for which
$\overline{r}_{\chi,\tilde{\pi},T}=\overline{r}_{\pi,T}$ for all $T$.
Convergence is as fast as can be, and in fact, instant. However, the role of
$\chi$ is vacuous. At the other extreme, suppose the learning target
$\chi=(O_{t+1}:t\in\mathbb{Z}_{+})$ includes all observations from the past,
present, and future. With this privileged knowledge, predictions
$P^{\chi}_{t}(\cdot)=\mathbbm{1}(O_{t+1}=\cdot)$ perfectly anticipate
observations. However, with this “overinformative” learning target,
$\overline{\mathrm{Regret}}_{\chi,\tilde{\pi}}(T|\pi)$ does not vanish and
instead converges to $\mathbb{E}[\ln(1+e^{-\theta})]>0$. This is because the
agent never learns enough to compete with target policy, which has privileged
access to future observations.

####  4.1.2 Regret Analysis

The machine learning literature offers a variety of mathematical tools for
regret and sample complexity analysis. These tools typically study how agents
accumulate information about a designated learning target and make decisions
that become competitive with those that could be made with privileged
knowledge of the learning target. To more concretely illustrate the nature of
this analysis and the role of learning targets, we will present in this
section examples of results in this area. In order to keep the exposition
simple and transparent, we will restrict attention to supervised learning.

Rather than cover results about specific agents, we will review results about
an optimal agent policy, which produces predictions
$P^{*}_{t}(\cdot)=\mathbb{P}(Y_{t+1}=\cdot|H_{t})$. Such an agent maximizes
$\mathbb{E}_{\pi}[\frac{1}{T}\sum_{t=0}^{T-1}R_{t+1}]$ over every duration
$T$, with rewards given by $R_{t+1}=\ln P^{*}_{t}(Y_{t+1})$. Hence, the
results we review pertain to what is possible rather than what is attained by
a particular algorithm.

For any learning target $\chi$, we will take the target policy to be that
which generates actions $P_{t}^{\chi}(y)=\mathbb{P}(Y_{t+1}=y|\chi,H_{t})$.
This represents an optimal prediction for an agent with privileged knowledge
of $\chi$ in addition to the history $H_{t}$. For this target policy, average
regret satisfies

$\displaystyle\overline{\mathrm{Regret}}_{\chi,\tilde{\pi}}(T|\pi)=$
$\displaystyle\overline{r}_{\chi,\tilde{\pi},T}-\overline{r}_{\pi,T}$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\mathbb{E}\left[\frac{1}{T}\sum_{t=0}^{T-1}\ln
P^{\chi}_{t}(Y_{t+1})\Big{|}\chi\right]\right]-\mathbb{E}\left[\frac{1}{T}\sum_{t=0}^{T-1}\ln
P^{*}_{t}(Y_{t+1})\right]$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[\frac{1}{T}\sum_{t=0}^{T-1}\mathbb{E}\left[\ln\frac{P^{\chi}_{t}(Y_{t+1})}{P^{*}_{t}(Y_{t+1})}\Big{|}\chi\right]\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\frac{1}{T}\sum_{t=0}^{T-1}{\mathbf{d}}_{\rm
KL}(P_{t}^{\chi}\|P_{t}^{*})\right].$

To characterize regret incurred by an optimal agent, we start with a basic
result of [Jeon et al., 2023, Theorem 9]:

$\overline{\mathrm{Regret}}_{\chi,\tilde{\pi}}(T|\pi)\leq\frac{\mathbb{H}(\chi)}{T}.$
(9)

The right-hand side is the entropy of the learning target divided by the
duration $T$. If this entropy is finite then, as $T$ grows, the right-hand
side, and therefore regret, vanishes. That the bound increases with the
entropy of the learning target is intuitive: if there is more to learn, regret
ought to be larger for longer.

While the aforementioned regret bound offers useful insight, it becomes
vacuous when the $\mathbb{H}(\chi)=\infty$. Entropy is typically infinite when
$\chi$ is continuous-valued. In order to develop tools that enable analysis of
continuous variables and that lead to much tighter bounds, even when
$\mathbb{H}(\chi)<\infty$, let us introduce a new concept: the rate-distortion
function. Let

$\Theta_{\epsilon}=\left\\{\tilde{\chi}:\mathbb{E}\left[{\mathbf{d}}_{\rm
KL}\left(P_{t}^{\chi}\|P_{t}^{\tilde{\chi}}\right)\right]\leq\epsilon\text{
for all }t\right\\}$

be the set of all random variables $\tilde{\chi}$ that enable predictions
close to those afforded by the $\chi$. The _rate_ of $\chi$ with _distortion_
tolerance $\epsilon$ is defined by the rate-distortion function:

$\mathbb{H}_{\epsilon}(\chi)=\inf_{\tilde{\chi}\in\Theta_{\epsilon}}\mathbb{I}(\chi;\tilde{\chi}).$
(10)

Loosely speaking, this is the number of nats required to identify a useful
approximation to the learning target. The rate-distortion function
$\mathbb{H}_{\epsilon}$ serves an alternative upper bound as well as a lower
bound [Jeon et al., 2023, Theorem 12]:

$\sup_{\epsilon\geq
0}\min\left(\frac{\mathbb{H}_{\epsilon}(\chi)}{T},\epsilon\right)\leq\overline{\mathrm{Regret}}_{\chi,\tilde{\pi}}(T|\pi)\leq\inf_{\epsilon\geq
0}\left(\frac{\mathbb{H}_{\epsilon}(\chi)}{T}+\epsilon\right).$ (11)

Even when $\mathbb{H}(\chi)=\infty$, the rate $\mathbb{H}_{\epsilon}(\chi)$
can increase at a modest pace as $\epsilon$ vanishes. We build on Example 8 to
offer a simple and concrete illustration. While that example was not framed as
one of supervised learning, it can be viewed as such by taking each
observation $O_{t+1}$ to encode only a label $Y_{t+1}$ resulting from a non-
informative input $X_{t}$. We will characterize the rate-distortion function
and regret for each of the three learning targets considered in Example 8.

######  Example 9.

(rate-distortion and convergence for logit data) Recall the environment of
Example 8, in which binary labels are generated according to
$\mathbb{P}(O_{t+1}=1|\theta,H_{t},A_{t})=e^{\theta}/(1+e^{\theta})$ based on
a latent variable $\theta\sim\mathcal{N}(0,1)$.

For the “obvious” learning target $\chi=\theta$ and all $\tilde{\chi}$,
$\mathbb{E}[{\mathbf{d}}_{\rm
KL}(P^{\chi}_{t}\|P^{\tilde{\chi}}_{t})]\leq\mathbb{E}[(\chi-\mathbb{E}[\chi|\tilde{\chi}])^{2}]$.
As a result, $\tilde{\chi}\sim\mathcal{N}(\chi,\epsilon)$ is an element of
$\Theta_{\epsilon}$, and therefore,

$\mathbb{H}_{\epsilon}(\chi)\leq\frac{1}{2}\ln\left(1+\frac{1}{\epsilon}\right).$

It follows from Equation 11 that

$\overline{\mathrm{Regret}}_{\chi,\tilde{\pi}}(T|\pi)\leq\ \inf_{\epsilon\geq
0}\left(\frac{1}{2T}\ln\left(1+\frac{1}{\epsilon}\right)+\epsilon\right)\
\leq\ \frac{\ln\left(1+2T\right)+1}{2T}.$

For the “uninformative” learning target $\chi=\emptyset$,
$\mathbb{H}_{\epsilon}(\chi)=0$, and therefore
$\overline{\mathrm{Regret}}_{\chi,\tilde{\pi}}(T|\pi)=0$ for all $T$. For the
“overinformative” learning target $\chi=(O_{t+1}:t\in\mathbb{Z}_{+})$, on the
other hand, for $\epsilon<\mathbb{E}[\ln(1+e^{\theta})/(1+e^{\theta})]$,
$\mathbb{H}_{\epsilon}(\chi)=\infty$ and
$\overline{r}_{\chi,T}-\overline{r}_{*,T}>\mathbb{E}[\ln(1+e^{\theta})/(1+e^{\theta})]/2>0$.

For this example, though the “obvious” choice of learning target $\chi=\theta$
yields $\mathbb{H}(\chi)=\infty$, the rate $\mathbb{H}_{\epsilon}(\chi)$ is
modest even for small positive values of $\epsilon$. Because of this, an
optimal agent converges quickly, as expressed by $O((\ln T)/T)$ bound.
Further, knowledge $\theta$ enables efficient computation of predictions
$P_{t}(1)=\mathbb{P}(Y_{t+1}=1|\theta,H_{t})=e^{\theta}/(1+e^{\theta})$. On
the other hand, the “underinformed” learning target $\chi=\emptyset$ is not
helpful, and with respect to the “overinformed” learning target, regret does
not vanish.

####  4.1.3 The Cosmic Learning Target

The universe is identified by a finite number of bits. Consider a “cosmic”
learning target $\chi^{*}$ that expresses the entirety of this information.
Lloyd [2002] derives an upper bound of $\mathbb{H}(\chi^{*})\leq 10^{120}$.
For an agent that retains all information about $\chi^{*}$ that it observes,
regret must vanish since, by Equation 9,
$\overline{\mathrm{Regret}}_{\chi,\tilde{\pi}}(T|\pi)\leq\mathbb{H}(\chi^{*})/T$.
However, this entropy is so large that the bound is effectively vacuous,
establishing meaningful levels of error only for astronomically large $T$. The
following example illustrates how a simpler learning target can give rise to a
more relevant analysis.

######  Example 10.

(logit data from cosmic information) Consider again a supervised learning
environment with binary labels, along the lines studied in Examples 8 and 9.
In principle, given privileged knowledge of the cosmic learning target
$\chi^{*}$, an agent should be able to generate perfect predictions
$P^{\chi^{*}}_{t}(1)=\mathbb{P}(O_{t+1}=1|\chi^{*},H_{t},A_{t})=\mathbbm{1}(O_{t+1}=1)$.
This is because all uncertainty is resolved by $\chi^{*}$. However, the rate
at which $\overline{\mathrm{Regret}}_{\chi^{*},\tilde{\pi}}(T|\pi)$ vanishes
may be too slow to be relevant.

Suppose that for some statistic $\theta$, which is determined by $\chi^{*}$,
$\mathbb{P}(O_{t+1}=1|\theta,H_{t},A_{t})$ is very closely approximated by
$e^{\theta}/(1+e^{\theta})$. Perhaps so closely that an agent with knowledge
of $\theta$ will not be able to tell the difference over any reasonable time
frame. Taking $\chi=\theta$ to be the learning target, we obtain the regret
bound of Example 9.

A diligent reader may wonder how to reconcile the finiteness of cosmic
information with infinite entropy of learning targets we sometimes consider,
like in our treatment of logit data in Example 8. The continuous variable
$\chi=\theta$ of that example, for which $\mathbb{H}(\theta)=\infty$, serves
as an approximation. In particular, $\theta$ is a random variable with respect
to a probability space $(\Omega,\mathbb{F},\mathbb{P})$ and thus determined by
an atomic outcome $\omega$ in an infinite set $\Omega$. The infinite set
approximates the set of possible realizations of the cosmic learning target
$\chi^{*}$. In particular, the latter set is so large that, for practical
purposes, we consider it infinite. This gives rise to a mathematical formalism
that accommodates random variables with infinite entropy.

###  4.2 Continual Learning

Unlike more traditional framings of machine learning, continual learning does
not generally afford an obvious choice of learning target. In traditional
framings, the agent is considered “done” with learning when it has gathered
enough information about a learning target to make effective decisions.
Performant continual learning agents perpetually ingest new information. This
unending process is incentivized by constraints, as we now discuss.

####  4.2.1 Constraints Incentivize Persistent Regret

Recall that practical agent designs typically maintain an agent state, with
behavior characterized by functions $\psi$ and $\pi$. In particular, the agent
state evolves according to $U_{t+1}\sim\psi(\cdot|U_{t},A_{t},O_{t+1})$ and
actions are sampled according to $A_{t}\sim\pi(\cdot|U_{t})$. Hence, the agent
policy is encoded in terms of the pair $(\psi,\pi)$. Let
$\overline{r}_{\psi,\pi}=\mathbb{E}_{\pi,\psi}[\frac{1}{T}\sum_{t=0}^{T-1}R_{t+1}]$
denote the average reward attained by such an agent.

The information content of $U_{t}$ is quantified by the entropy
$\mathbb{H}(U_{t})$, which is constrained by the agent’s information capacity.
As discussed in Section 3.3, for common scalable agent designs, computation
grows with this information content. Hence, computational constraints limit
information capacity. To understand implications of this restriction, in this
section, we focus on the problem of agent design with fixed information
capacity $C$:

$\displaystyle\begin{split}\max_{\psi,\pi}&\quad\overline{r}_{\psi,\pi}\\\
\text{s.t.}&\quad\sup_{t}\mathbb{H}(U_{t})\leq C.\end{split}$ (12)

The following simple example, which is similar to one presented in [Sutton et
al., 2007, Section 2], illustrates how such a constraint incentivizes non-
convergence.

######  Example 11.

(bit flipping) Consider an environment that generates a sequence of binary
observations $\mathcal{O}=\\{0,1\\}$, initialized with $O_{1}$ distributed
$\mathrm{Bernoulli}(1/2)$, and evolving according to
$\mathbb{P}(O_{t+1}=o|p,H_{t},A_{t})=p(1-o)+(1-p)o$, where $p$ is a random
variable. Note that $p$ governs the probability of a bit flip. Each action is
a binary prediction $A_{t}$ of the next observation $O_{t+1}$ and yields
reward $R_{t+1}=\mathbbm{1}(A_{t}=O_{t+1})$. In other words, the agent
predicts the next bit and receives a unit of reward if its prediction is
correct.

It is natural to consider $\chi=p$ as a learning target. In particular, with
privileged knowledge of this learning target, an agent can act according to a
target policy $\tilde{\pi}$ that generates a prediction $A_{t}=1$ if and only
if $\mathbb{P}(O_{t+1}=1|p,H_{t})>1/2$ or, equivalently,
$p(1-O_{t})+(1-p)O_{t}>1/2$. The optimal unconstrained agent policy $\pi$
generates action $A_{t}=1$ if and only if $\mathbb{P}(O_{t+1}=1|H_{t})>1/2$
and satisfies $\overline{\mathrm{Regret}}_{\chi,\tilde{\pi}}(T|\pi)\rightarrow
0$. This is because, if not hindered by constraints, an agent can identify $p$
over time from observations.

Now suppose the agent is constrained by an information capacity of $C=\ln
2\mathrm{\ nats}=1\mathrm{\ bit}$. Encoding an accurate approximation of $p$
in the agent state becomes infeasible. Instead, the optimal solution to
Equation 12 is comprised of an agent state update function $U_{t}=O_{t}$ and a
policy function for which $A_{t}=1$ if and only if
$\mathbb{E}[p](1-U_{t})+\mathbb{E}[1-p]U_{t}>1/2$. In other words, the agent
simply retains its most recent observation as agent state and predicts a bit
flip with probability $\mathbb{E}[p]$. This agent does not aim to identify
$\chi=p$ nor, for that matter, any nontrivial learning target. And regret with
respect to $\overline{\mathrm{Regret}}_{\chi,\tilde{\pi}}(T|\pi)$ does not
vanish.

####  4.2.2 Nonstationary Learning Targets

Continual learning is often characterized as addressing nonstationary
environments. But whether an environment is nonstationary is a subjective
matter. With respect to the cosmic learning target $\chi^{*}$, any environment
is stationary. However, as illustrated by Example 10, it can be useful to view
an environment as nonstationary with respect to a simpler latent stochastic
process $(\theta_{t}:t\in\mathbb{Z}_{++})$. An agent that tracks this process
can be viewed at each time $t$ as trying to learn about $\theta_{t}$. This
suggests viewing $\chi_{t}=\theta_{t}$ as a time-varying – or nonstationary –
learning target.

Motivated by this view, we interpret nonstationarity as indicating agent
behavior that is naturally explained by a time-varying learning target.
Example 11 illustrates how this sort of behavior is incentivized by
restricting information capacity. The optimal unconstrained agent learns about
the latent variable $p$, which constitutes a fixed learning target. On the
other hand, the capacity-constrained agent learns at each time about $O_{t}$.
This bit of information is ingested into the agent state and can be viewed as
a nonstationary learning target $\chi_{t}=O_{t}$.

Our narrative is aligned with that of Sutton et al. [2007], who suggest that
tracking a nonstationary learning target is warranted even in a stationary
environment if the environment is sufficiently complex. The cosmic learning
target $\chi^{*}$ is helpful to making this point. Consider a supervised
learning environment for which an enormous amount of information is required
to attain reasonable performance. In other words, for any reasonable
$\epsilon$, $\mathbb{H}_{\epsilon}(\chi^{*})$ is huge. An agent with modest
capacity $C\ll\mathbb{H}_{\epsilon}(\chi^{*})$ ought not aim to accumulate all
information required to attain error $\epsilon$ because of its insufficient
information capacity. However, it may be possible to attain error $\epsilon$
by only retaining at each time step information that will be helpful in the
near term. This amounts to tracking a nonstationary learning target.

Our notion of a nonstationary learning target relates to the work of Abel et
al. [2023], which proposes a definition of continual reinforcement learning.
This definition offers a formal expression of what it means for an agent to
never stop learning. The characterization is subjective in that it defines
non-convergence with respect to a basis, which is a fixed set of policies. An
agent is interpreted as searching among these and then of converging if it
settles on one that it follows thereafter. The work associates continual
learning with non-convergence. A learning target offers an alternative
subjective construct for interpretation of agent behavior. Loosely speaking,
if an agent converges on an element of the basis, that can be thought of as
deriving from a fixed learning target. Perpetually transitioning among element
of the basis is akin to pursuing a nonstationary learning target.

###  4.3 On Learning About an Unknown Environment

In traditional framings of machine learning, it is common to characterize the
environment as a random (unknown) latent variable. The agent is then
interpreted as learning about the environment – that is, this random variable
– from its experience. Indeed, the random environment can serve as a learning
target in the vein of vanishing-regret learning. In supervised learning, if
the input distribution is known, this latent variable may be the unknown
function that maps inputs to distributions over labels. In some traditional
framings of reinforcement learning, it may be the unknown transition
probability matrix of a Markov Decision Process (MDP).

In contrast, our general formulation of continual learning, as described in
Section 2.1, takes the environment, and in particular, the observation
probability function $\rho$, to be known. With this formulation, the
environment is no longer a random variable and can not serve as a useful
learning target. In this subsection, we will motivate this decision. We first
discuss why a deterministic characterization is general and minimal. We then
explain that, because the sort of environment of interest to continual
learning does not give rise to an obvious fixed learning target, random
characterizations of the environment do not afford the kind of interpretation
and analysis enjoyed by vanishing-regret learning.

As discussed in Section 2.1, the dynamics represented by a random observation
probability function $\tilde{\rho}$ can be expressed in terms of a
deterministic one $\rho$ for which
$\rho(\cdot|H_{t},A_{t})=\mathbb{E}[\tilde{\rho}(\cdot|H_{t},A_{t})|H_{t},A_{t}]$.
The converse also holds. In particular, for any deterministic $\rho$ and
random variable $\chi$, we can define an equivalent random $\tilde{\rho}$ for
which
$\tilde{\rho}(\cdot|H_{t},A_{t})=\mathbb{P}(O_{t+1}\in\cdot|\chi,H_{t},A_{t})$.
Note that $\tilde{\rho}$ offers an equivalent characterization because
$\rho(\cdot|H_{t},A_{t})=\mathbb{P}(O_{t+1}\in\cdot|H_{t},A_{t})=\mathbb{E}[\mathbb{P}(O_{t+1}\in\cdot|\chi,H_{t},A_{t})|H_{t},A_{t}]=\mathbb{E}[\tilde{\rho}(\cdot|H_{t},A_{t})|H_{t},A_{t}]$.
Since this is true for any random variable $\chi$, there are many random
environments that represent the same deterministic environment. As such, the
deterministic representation is minimal, while the random representation
requires choice of a random variable $\chi$, which is inconsequential to the
dynamics of the environment.

In the traditional framing of supervised learning, data pairs are assumed to
be exchangeable. Consequently, de Finetti’s Theorem establishes existence of a
learning target $\chi$ conditioned on which the data pairs are iid [de
Finetti, 1929]. It is natural to think of $\chi$ as identifying an unknown
environment and bringing to bear interpretation and analysis afforded by
vanishing-regret learning. Specifically, assuming the input distribution is
known, $\chi$ is often taken to be an unknown function that maps inputs to
distributions over labels. A similar story goes for the traditional framing of
reinforcement learning. Under a weaker exchangeability condition presented in
Appendix A, it is natural to characterize dynamics in terms of an unknown MDP
$\chi$. In both cases, an agent can learn over time to do about as well as if
$\chi$ were known.

In contrast, environments of the sort considered in continual learning tend
not to give rise to an obvious choice of fixed learning target. In particular,
regret generally does not vanish with respect to any particular learning
target that enables efficient computation of performant actions. For example,
Liu et al. [2023a] discusses how regret does not vanish with respect to common
choices of learning targets in non-stationary bandit learning. Absent the
analytic role of a learning target, we opted for minimality in using a
deterministic environment characterization for our formulation of continual
learning. That being said, for the purpose of exposition, it can often be more
intuitive to characterize a specific environment using a latent variable
model. For instance, many of the examples in this monograph are described as
latent AR(1) processes, such as the scalar tracking problem in Section 2.3.1.
Such a characterization can be helpful to facilitate interpretation.

### Summary

  * •

A learning target (denoted by $\chi$) is random variable which represents what
an agent aims to learn about.

  * •

A target policy (denoted by $\tilde{\pi}_{\chi}$) is a random variable which
takes values in the set of policies which represents the policy the agent
would use if $\chi$ were known.

  * •

For each duration $T\in\mathbb{Z}_{++}$,

$\overline{r}_{\pi,T}=\mathbb{E}_{\pi}\left[\frac{1}{T}\sum_{t=0}^{T-1}R_{t+1}\right]\qquad\text{and}\qquad\overline{r}_{\chi,\tilde{\pi},T}=\mathbb{E}_{\tilde{\pi}_{\chi}}\left[\frac{1}{T}\sum_{t=0}^{T-1}R_{t+1}\Big{|}\chi\right].$

  * •

The average regret over duration $T$ incurred by $\pi$ w.r.t
$(\chi,\tilde{\pi})$ is

$\overline{\mathrm{Regret}}_{\chi,\tilde{\pi}}(T|\pi)=\mathbb{E}\left[\overline{r}_{\chi,\tilde{\pi},T}-\overline{r}_{\pi,T}\right].$

  * •

$\pi$ exhibits vanishing regret w.r.t. $(\chi,\tilde{\pi})$ if
$\limsup_{T\to\infty}\overline{\mathrm{Regret}}_{\chi,\tilde{\pi}}(T|\pi)\leq
0$.

  * •

In the special case of continual supervised learning,
$P_{t}^{*}(y)=\mathbb{P}(Y_{t+1}=y|H_{t})$ maximizes $\overline{r}_{\pi,T}$
and $P_{t}^{\chi}(y)=\mathbb{P}(Y_{t+1}=y|\chi,H_{t})$ maximizes
$\overline{r}_{\chi,\tilde{\pi},T}$ for every duration $T$ For the above
optimal choices of $\pi,\tilde{\pi}_{\chi}$,

$\overline{\mathrm{Regret}}_{\chi,\tilde{\pi}}(T|\pi)=\mathbb{E}\left[\frac{1}{T}\sum_{t=0}^{T-1}{\mathbf{d}}_{\rm
KL}(P_{t}^{\chi}\|P_{t}^{*})\right].$

For all durations $T$,

$\overline{\mathrm{Regret}}_{\chi,\tilde{\pi}}(T|\pi)\leq\frac{\mathbb{H}(\chi)}{T}.$

For continuous-valued $\chi$, $\mathbb{H}(\chi)$ is often $\infty$, leading to
a vacuous upper bound. The bound can be improved via _rate-distortion theory_.
For any $\epsilon\geq 0$, let

$\Theta_{\epsilon}=\left\\{\tilde{\chi}:\mathbb{E}[{\mathbf{d}}_{\rm
KL}(P_{t}^{\chi}\|P_{t}^{\tilde{\chi}})]\leq\epsilon\text{ for all
}t\right\\}$

be the set of all random variables $\tilde{\chi}$ which enable predictions
with _distortion_ at most $\epsilon$. The _rate_ of $\chi$ with _distortion_
tolerance $\epsilon$ is defined by the rate-distortion function:

$\mathbb{H}_{\epsilon}(\chi)=\inf_{\tilde{\chi}\in\Theta_{\epsilon}}\mathbb{I}(\chi;\tilde{\chi}).$

For all durations $T$,

$\sup_{\epsilon\geq
0}\min\left(\frac{\mathbb{H}_{\epsilon}(\chi)}{T},\epsilon\right)\leq\overline{\mathrm{Regret}}_{\chi,\tilde{\pi}}(T|\pi)\leq\inf_{\epsilon\geq
0}\left(\frac{\mathbb{H}_{\epsilon}(\chi)}{T}+\epsilon\right).$

  * •

The notion of learning about an uncertain environment does not play a central
role in continual learning as it does in vanishing-regret learning:

    * –

In vanishing-regret learning, it is common to characterize the environment as
a random (unknown) latent variable.

    * –

In contrast, our general formulation of continual learning takes the
environment, and in particular, the observation probability function $\rho$,
to be deterministic (known). This characterization is general and minimal.

    * –

In continual learning, random characterizations of the environment do not
generally afford the kind of interpretation and analysis enjoyed by vanishing-
regret learning. This is because performant agents do not generally focus on
identifying a fixed learning target.

##  5 Stability Versus Plasticity

While the subjects of catastrophic forgetting and loss of plasticity have
attracted a great deal of attention in the continual learning literature, the
terms have lacked definitional clarity of the sort that would afford coherent
reasoning about tradeoffs. Both notions relate to how an agent processes
information. Catastrophic forgetting refers to elimination of useful
information. Loss of plasticity refers to an inability to ingest useful new
information. In this section, we build on information-theoretic tools
introduced in the previous section to formalize these concepts and clarify the
interaction between information capacity, stability, and plasticity. To keep
the analysis simple, we restrict attention to the special case of continual
supervised learning, as presented in Section 2.3.4. Recall that each action is
a predictive distribution $A_{t}=P_{t}$ and each reward $R_{t+1}=\ln
P_{t}(Y_{t+1})$ is the logarithm of the probability assigned to the realized
label.

###  5.1 Stability-Plasticity Decomposition

If the agent had infinite information capacity and could maintain history as
its agent state $U_{t}=H_{t}$ then the informational error would be
$\mathbb{E}[{\mathbf{d}}_{\rm
KL}(P^{*}_{t}\|\tilde{P}_{t})]=\mathbb{I}(Y_{t+1};H_{t}|H_{t})=0$. However,
with an agent state that retains partial information, the error will typically
be larger. In this way, and as expressed by Theorem 3, a constraint on
capacity can induce error. This happens through requiring that the agent
either forget some old information, forgo ingestion of some new information,
or both.

We can formalize the relation between these quantities in information-
theoretic terms. At each time step $t$, the informational error
$\mathbb{E}[{\mathbf{d}}_{\rm KL}(P^{*}_{t}\|\tilde{P}_{t})]$ arises as a
consequence of useful information forgotten or forgone due to implasticity
over previous time steps. As shorthand, let
$H_{t-k:t}=(O_{t-k},\ldots,O_{t})$. The error due to information forgotten $k$
time steps earlier can be expressed as
$I(Y_{t+1};U_{t-k-1}|U_{t-k},H_{t-k:t})$: the information about $Y_{t+1}$ that
is available in $U_{t-k-1}$ but not the next agent state $U_{t-k}$ or the
subsequent experience $H_{t-k+1:t}$. In other words, this is the information
lost in transitioning from $U_{t-k-1}$ to $U_{t-k}$ and not recoverable by
time step $t$. The error due to implasticity $k$ time steps earlier can be
expressed as $\mathbb{I}(Y_{t+1};O_{t-k}|U_{t-k},H_{t-k+1:t})$: the
information about $Y_{t+1}$ that is available in $O_{t-k}$ but absent from the
preceding agent state $U_{t-k}$ and the subsequent experience $H_{t-k+1:t}$.
In other words, this is information presented by $O_{t-k}$ but not $U_{t-k}$
and that is not otherwise available through time step $t$.

The following theorem provides a formal decomposition, attributing error to
forgetting and implasticity. Note that actions are omitted because in the case
of supervised learning they do not impact observations.

######  Theorem 4.

For all $t\in\mathbb{Z}_{+}$,

$\underbrace{\mathbb{E}[{\mathbf{d}}_{\rm
KL}(P^{*}_{t}\|\tilde{P}_{t})]}_{\mathrm{error}}=\sum_{k=0}^{t}\left(\underbrace{\mathbb{I}(Y_{t+1};U_{t-k-1}|U_{t-k},H_{t-k:t})}_{\mathrm{forgetting\
at\ lag\
}k}+\underbrace{\mathbb{I}(Y_{t+1};O_{t-k}|U_{t-k},H_{t-k+1:t})}_{\mathrm{implasticity\
at\ lag\ }k}\right).$

###### Proof.

We have

$\displaystyle\mathbb{E}[{\mathbf{d}}_{\rm KL}(P^{*}_{t}\|\tilde{P}_{t})]$
$\displaystyle\overset{(a)}{=}\mathbb{I}(Y_{t+1};H_{t}|U_{t})$
$\displaystyle\overset{(b)}{=}\mathbb{I}(Y_{t+1};H_{t},U_{0:t-1}|U_{t})$
$\displaystyle\overset{(c)}{=}\sum_{k=0}^{t}\mathbb{I}(Y_{t+1};O_{t-k},U_{t-k-1}|U_{t-k:t},H_{t-k+1:t})$
$\displaystyle\overset{(d)}{=}\sum_{k=0}^{t}\mathbb{I}(Y_{t+1};O_{t-k},U_{t-k-1}|U_{t-k},H_{t-k+1:t})$
$\displaystyle\overset{(e)}{=}\sum_{k=1}^{t}\left(\mathbb{I}(Y_{t+1};U_{t-k-1}|U_{t-k},H_{t-k:t})+\mathbb{I}(Y_{t+1};O_{t-k}|U_{t-k},H_{t-k+1:t})\right),$

where $(a)$ follows from Theorem 2; $(b)$ follows from $U_{0:t-1}\perp
Y_{t+1}|U_{t},H_{t}$; $(c)$ follows from the chain rule of mutual information,
and we take $Y_{0}$ and $U_{-1}$ to be the singleton $\emptyset$; $(d)$
follows from the fact that for all $j$, $U_{j+1}$ is determined by
$(U_{j},O_{j+1})$ and independent algorithmic randomness; and $(e)$ follows
from chain rule of mutual information. ∎

Implasticity and forgetting terms are indexed by a lag $k$ relative to the
current time step $t$. In the process of updating the agent state from
$U_{t-k-1}$ to $U_{t-k}$ in response to an observation, information may be
ingested and/or forgotten. The implasticity and forgetting terms measure how
this ultimately impacts the agent’s ability to predict $Y_{t+1}$. Summing over
lags $k$ produces the immediate error $\mathbb{I}(Y_{t+1};H_{t}|U_{t})$.

The implasticity at lag $k$ measures the amount of information presented by
$O_{t-k}$ that is useful for predicting $Y_{t+1}$ that the agent fails to
ingest and is absent from the intermediate data $H_{t-k+1:t}$. Note that, due
to the conditioning on the data $H_{t-k+1:t}$, this term only penalizes the
inability to extract information about $Y_{t+1}$ that will not be again
available from observations between $t-k$ and $t$.

The forgetting at lag $k$ derives from the agent ejecting information that is
relevant to predicting $Y_{t+1}$ when updating its agent state from
$U_{t-k-1}$ to $U_{t-k}$. Again, due to conditioning on $H_{t-k:t}$, this term
only penalizes for forgotten information that cannot be recovered from other
observations to be made before time step $t$.

Our decomposition indicates that errors due to implasticity and forgetting are
forward looking in the sense that they only impact predictions at subsequent
times; thus the lag $k$ relative to prediction error. This is in contrast with
much of the continual SL literature, which aims to develop agents that
remember information that would have been useful in their past, even if that
is unlikely to be useful to their future. Indeed, the term catastrophic
forgetting typically refers to loss of useful information, whether useful in
the future or past.

Our expressions for implasticity and forgetting are complicated by sums over
lags. The expressions simplify greatly when the input sequence $X_{t}$ is
independent of history, i.e., $X_{t+1}\perp H_{t}$, and when the sequence of
agent states and observations forms a stationary stochastic process. This
corresponds to a prototypical nonstationary supervised learning formulation:
iid inputs and a mapping to label probabilities that is modulated by a
stationary stochastic process.

######  Theorem 5.

Suppose $((U_{t},O_{t}):t\in\mathbb{Z}_{+})$ is a stationary process and, for
all $t\in\mathbb{Z}_{+}$, $X_{t+1}\perp H_{t}$. Then, for all
$t\in\mathbb{Z}_{+}$,

$\lim_{t\to\infty}\underbrace{\mathbb{E}[{\mathbf{d}}_{\rm
KL}(P^{*}_{t}\|\tilde{P}_{t})]}_{\mathrm{error}}=\lim_{t\to\infty}\left(\underbrace{\mathbb{I}(H_{t+1:\infty};U_{t-1}|U_{t},O_{t})}_{\mathrm{forgetting}}+\underbrace{\mathbb{I}(H_{t+1:\infty};O_{t}|U_{t})}_{\mathrm{implasticity}}\right).$

###### Proof.

We establish the result by taking limits of the expressions from Theorem 4 for
cumulative forgetting and implasticity. The forgetting term yields

$\displaystyle\lim_{t\to\infty}\sum_{k=0}^{t}\mathbb{I}(Y_{t+1};U_{t-k-1}|U_{t-k},H_{t-k:t})$
$\displaystyle\overset{(a)}{=}\lim_{t\to\infty}\sum_{k=0}^{t}\mathbb{I}(Y_{t+k+1};U_{t-1}|U_{t},H_{t:t+k})$
$\displaystyle\overset{(b)}{=}\lim_{t\to\infty}\sum_{k=0}^{t}\mathbb{I}(X_{t+k+1},Y_{t+k+1};U_{t-1}|U_{t},H_{t:t+k})$
$\displaystyle\overset{(c)}{=}\lim_{t\to\infty}\mathbb{I}(H_{t+1:2t+1};U_{t-1}|U_{t},O_{t})$
$\displaystyle=\mathbb{I}(H_{t+1:\infty};U_{t-1}|U_{t},O_{t}),$

where $(a)$ follows from the fact that since $(U_{t},O_{t})$ is stationary,
$\mathbb{I}(Y_{t+1};U_{t-k-1}|U_{t-k},H_{t-k:t})$ is a constant independent of
$t$, $(b)$ follows from the fact that $X_{t+k+1}\perp H_{t+k}$, and $(c)$
follows from the chain rule of mutual information. The implasticity term
yields

$\displaystyle\lim_{t\to\infty}\sum_{k=0}^{t}\mathbb{I}(Y_{t+1};O_{t-k}|U_{t-k},H_{t-k+1:t})$
$\displaystyle\overset{(a)}{=}\lim_{t\to\infty}\sum_{k=0}^{t}\mathbb{I}(Y_{t+k+1};O_{t}|U_{t},H_{t+1:t+k})$
$\displaystyle\overset{(b)}{=}\lim_{t\to\infty}\sum_{k=0}^{t}\mathbb{I}(X_{t+k+1},Y_{t+k+1};O_{t}|U_{t},H_{t+1:t+k})$
$\displaystyle\overset{(c)}{=}\lim_{t\to\infty}\mathbb{I}(H_{t+1:2t+1};O_{t}|U_{t})$
$\displaystyle=\mathbb{I}(H_{t+1:\infty};O_{t}|U_{t}),$

where $(a)$ follows from the fact that since $(U_{t},O_{t})$ is stationary,
$\mathbb{I}(Y_{t+1};O_{t-k}|U_{t-k},H_{t-k+1:t})$ is a constant independent of
$t$, $(b)$ follows from the fact that $X_{t+k+1}\perp H_{t+k}$, and $(c)$
follows from the chain rule of mutual information.∎

The first term on the right-hand-side equates error due to forgetting with the
information available in the previous agent state $U_{t-1}$, but neither in
the subsequent agent state $U_{t}$ or the subsequent observation $O_{t}$. The
second term characterizes error due to implasticity as the information about
the future $H_{t+1:\infty}$ available in the current observation $O_{t}$ but
not ingested into the current agent state $U_{t}$.

###  5.2 A Didactic Example

We will illustrate concretely through a simple example how agent and
environment dynamics influence implasticity and forgetting errors. We focus
here on insight that can be drawn from analysis of the example, deferring
details of the analysis to Appendix B.

####  5.2.1 LMS with an AR(1) Process

We consider a very simple instance of continual SL in which the input set is a
singleton $\mathcal{X}=\\{\emptyset\\}$ and the label set $\mathcal{Y}=\Re$ is
of real numbers. Since inputs $X_{0},X_{1},\ldots$ are uninformative, we take
the history to only include labels $H_{t}=(Y_{1},\ldots,Y_{t})$. Each label is
generated according to

$Y_{t+1}=\theta_{t}+W_{t+1},$

where $\theta_{t}$ is a latent variable that represents the state of the
process and $W_{t+1}$ is a sample of an iid $\mathcal{N}(0,\sigma^{2})$
sequence. The sequence $\theta_{t}$ is initialized with
$\theta_{0}\sim\mathcal{N}(0,1)$ and evolves according to

$\theta_{t+1}=\eta\theta_{t}+V_{t+1},$

where $\eta$ is a fixed parameter and $V_{t+1}$ is a sample of an iid
$\mathcal{N}(0,1-\eta^{2})$ sequence. Note that, for all $t$, the marginal
distribution of $\theta_{t}$ is standard normal.

Consider an agent that maintains a real-valued agent state, initialized with
$U_{0}\sim\mathcal{N}(0,1)$ and updated according to the least mean squares
(LMS) algorithm [Widrow and Hoff, 1960]

$U_{t+1}=U_{t}+\alpha(Y_{t+1}-U_{t}),$

with a fixed stepsize $\alpha\in(0,1)$. This agent can then generate
predictions $P_{t}(\cdot)=\mathbb{P}(Y_{t+1}\in\cdot|U_{t})$, which are
Gaussian distributions. This agent does not necessarily make optimal use of
history, meaning that ${\mathbf{d}}_{\rm KL}(P^{*}_{t}\|P_{t})>0$. However,
for a suitably chosen stepsize, the agent attains zero error in steady state:
$\lim_{t\rightarrow\infty}{\mathbf{d}}_{\rm KL}(P^{*}_{t}\|P_{t})=0$. With
this optimal stepsize the LMS algorithm becomes a steady-state Kalman filter
[Kalman, 1960].

####  5.2.2 Constraining Information Content

Note that, for our agent, the forgetting error
$\mathbb{I}(Y_{t+1};U_{t-k-1}|U_{t-k},H_{t-k:t})$ is always zero because
$U_{t-k-1}$ is determined by the next agent state $U_{t-k}$ and the label
$Y_{t-k}$, which makes up part of $H_{t-k:t}$, according to
$U_{t-k-1}=(U_{t-k}-\alpha Y_{t-k})/(1-\alpha)$. This degeneracy stems from
the agent’s infinite capacity – since the agent state is a real number, it can
encode an infinite amount of information. As discussed earlier, practical
designs of agents subject to computational constraints limit information
capacity. As a microcosm that may yield insight relevant to such contexts, we
will consider a variant of LMS with bounded information capacity.

More relevant qualitative behavior emerges when the agent restricts the
information content $\mathbb{H}(U_{t})$ of the agent state to operate with
limited information capacity. Such a constraint arises, for example, if
instead of retaining a continuous-valued variable the agent must quantize,
encoding an approximation to the agent state with a finite alphabet. The state
of such an agent might evolve according to

$U_{t+1}=U_{t}+\alpha(Y_{t+1}-U_{t})+Q_{t+1},$ (13)

where $Q_{t+1}$ represents quantization error. We can think of this error as
quantization noise, which perturbs results of agent state updates. In
particular, it is the difference between the real value
$U_{t}+\alpha(Y_{t+1}-U_{t})$ that the agent would store as $U_{t+1}$, if it
could, and the quantized value that it actually stores.

Because the effects of quantization noise can be difficult to quantify, for
the purpose of analysis, it is common in information theory to approximate
quantization noise as an independent Gaussian random variable. In some cases,
this does not impact qualitative insights [e.g., Cover and Thomas 2012,
Theorem 10.3.2]. For analytical tractability, we will approximate the
quantization noise $(Q_{t}:t\in\mathbb{Z}_{++})$ as an iid
$\mathcal{N}(0,\delta^{2})$ sequence, for some $\delta>0$, which we will refer
to as the quantization noise intensity.

Like actual quantization, this Gaussian noise moderates information content of
the agent state. However, while actual quantization keeps the information
content $\mathbb{H}(U_{t})$ bounded, with Gaussian noise, $\mathbb{H}(U_{t})$
becomes infinite. This is because $U_{t}$ encodes infinite irrelevant
information expressed by the Gaussian noise itself. When Gaussian noise is
used to approximation quantization, rather than $\mathbb{H}(U_{t})$, it is
more appropriate to take the information to be $\mathbb{I}(U_{t};H_{t})$. This
represents the number of nats of information from the history $H_{t}$ retained
by the agent state $U_{t}$. In particular, $\mathbb{I}(U_{t};H_{t})$ excludes
irrelevant information expressed by the Gaussian noise $Q_{t}$.

As one would expect, for our setting of LMS with an AR(1) process,
$\mathbb{I}(U_{t};H_{t})$ is infinite when $\delta=0$, then monotonically
decreases, vanishing as the quantization noise intensity $\delta$ increases.
We impose a constraint $\mathbb{I}(U_{t};H_{t})\leq C$ to express a fixed
information capacity $C$. Given a choice of stepsize $\alpha$, we take the
quantization noise intensity to be the value $\delta_{*}$ so that this
constraint is binding: $\mathbb{I}(U_{t};H_{t})=C$. This models a quantization
scheme that maximizes information content subject to the information capacity.
As established by Theorem 12 in Appendix B.1,

$\delta_{*}(\alpha)=\alpha^{2}\frac{\sigma^{2}(1-\eta+\eta\alpha)+1+\eta-\eta\alpha}{1-\eta+\eta\alpha}\frac{\exp(-2C)}{1-\exp(-2C)}.$
(14)

####  5.2.3 Analysis

Figure 5 plots errors due to implasticity
$\mathbb{I}(Y_{t+1:\infty};Y_{t}|U_{t})$ and forgetting
$\mathbb{I}(Y_{t+1:\infty};U_{t-1}|U_{t},Y_{t})$ versus stepsize, for
asymptotically large $t$ and observation noise standard deviation
$\sigma=0.5$, an information capacity $C=2$, and autoregressive model
coefficients $\eta=0.9,0.95,0.99$.

|  |
---|---|---

(a) $\eta=0.9$

(b) $\eta=0.95$

(c) $\eta=0.99$

Figure 5: Average forgetting and implasticity errors versus the stepsize
$\alpha$ for environments with observation noise standard deviation
$\sigma=0.5$, agent capacity $\mathbb{I}(U_{t};H_{t})=2$, and autoregressive
model coefficients $\eta=0.9,0.95,0.99$. As $\alpha$ increases, the forgetting
error increases and the implasticity error decreases, then the former
decreases and the latter increases, albeit to much lesser extents. As $\eta$
increases, the optimal stepsize $\alpha^{*}$ decreases.

As $\alpha$ increases, the forgetting increases and the implasticity
decreases. Then, as $\alpha$ approaches one, the former decreases and the
latter increases, albeit to much lesser extents. It is natural for a small
stepsize to reduce forgetting and implasticity since increasing the stepsize
increases the weight placed on recent versus previously observed data. For the
same reason, as the figure indicates, the optimal stepsize $\alpha^{*}$
decreases as $\eta$ increases. This is because a larger coefficient $\eta$
increases the mixing time of the process, and this warrants placing more
weight on less recent observations to increase the duration over which they
influence predictions.

Figure 6 plots the optimal stepsize as a function of $\eta$ (Figure 6(a)), the
information capacity (Figure 6(b)), and the quantization noise intensity
$\delta$ (Figure 6(c)). Note that we use $\alpha^{*}$ to represent the optimal
stepsize for fixed $C$ and $\tilde{\alpha}$ for fixed $\delta$. As suggested
by Figure 5, as $\eta$ increases, the optimal stepsize decreases. This makes
sense since the mixing time of the AR(1) process scales with $1/(1-\eta)$,
while the duration over which LMS averages observations scales with
$1/\alpha$. As the mixing time grows, the optimal stepsize $\alpha^{*}$
decreases to induce averaging over longer durations. Interestingly, as
demonstrated by the second plot, the optimal stepsize does not vary with the
information capacity $C$. This observation is generalized and formalized by
Theorem 15 in the appendix. It is interesting to note, however, that this does
not imply invariance of the optimal stepsize to the quantization noise
intensity $\delta$. In particular, when information content is unconstrained,
the optimal stepsize varies with $\delta$, as demonstrated in Figure 6(c).

|  |
---|---|---

(a) $\alpha^{*}$ decreases $\eta$ increases.

(b) $\alpha^{*}$ does not depend on $C$.

(c) $\tilde{\alpha}$ increases as $\delta$ increases.

Figure 6: As $\eta$ increases, so does the mixing time $1/(1-\eta)$. The
optimal stepsize $\alpha^{*}$ decreases in response to induce averaging over a
longer duration. The information capacity $C$ does not impact the optimal
stepsize $\alpha^{*}$. However, the optimal stepsize $\tilde{\alpha}$
increases with the quantization noise standard deviation $\delta$. These plots