Continual Learning In Environments With Polynomial Mixing Times
Authors: Matthew Riemer
Sharath Chandra Raparthy
Ignacio Cases
Gopeshh Raaj Subbaraj
Maximilian Puelma Touzel
Irina Rish
Venue: NeurIPS 2022 Accept (2022)

Abstract: The mixing time of the Markov chain induced by a policy limits performance in real-world continual learning scenarios. Yet, the effect of mixing times on learning in continual reinforcement learning (RL) remains underexplored. In this paper, we characterize problems that are of long-term interest to the development of continual RL, which we call scalable MDPs, through the lens of mixing times. In particular, we theoretically establish that scalable MDPs have mixing times that scale polynomially with the size of the problem. We go on to demonstrate that polynomial mixing times present significant difficulties for existing approaches that suffer from myopic bias and stale bootstrapped estimates. To validate the proposed theory, we study the empirical scaling behavior of mixing times with respect to the number of tasks and task switching frequency for pretrained high performing policies on seven Atari games. Our analysis demonstrates both that polynomial mixing times do emerge in practice and how their existence may lead to unstable learning behavior like catastrophic forgetting in continual learning settings.

Continual Learning In Environments With Polynomial Mixing Times
Matthew Riemer+1.2, Sharath Chandra Raparthy Ignacio Cases', Gopeshh Subbaraj', Maximilian Puelma Touzel?, Irina Rish
Abstract
The mixing time of the Markov chain induced by a policy limits performance in real-world continual learning scenarios. Yet, the effect of mixing times on learning in continual reinforcement learning (RL) remains underexplored. In this paper, we characterize problems that are of long-term interest the development of continual RL, which we call scalable MDPs, through the lens of mixing times. In particular, we theoretically establish that scalable MDPs have mixing times that scale polynomially with the size of the problem. We go on to demonstrate that polynomial mixing times present significant difficulties for existing approaches, which suffer from myopic bias and stale bootstrapped estimates. To validate our theory, we study the empirical scaling behavior of mixing times with respect to the number of tasks and task duration for high performing policies deployed across multiple Atari games. Our analysis demonstrates both that polynomial mixing times do emerge in practice and how their existence may lead to unstable learning behavior like catastrophic forgetting in continual learning settings.
Introduction
Continual reinforcement learning (RL) [1] is an aspirational field of research confronting the dif- ficulties of long-term, real-world applications by studying problems of increasing scale, diversity, and non-stationariiy. The practical requirement for researchers to work problems of reasonable complexity in the short-term presents a meta-challenge: choosing the right small-scale problems so that the approaches we develop scale up to the use cases of the future. Here, we address this meta-challenge by formalizing RL problems that vary in size and by analyzing the scaling behavior of popular RL algorithms. In particular, we analyze on the often ignored mixing time that expresses the amount of time until the agent- enveroeenvronmment dynamics converge to some stationary behaviour.
Towards this end, we specifically make the following contributions in this work:
1. Scalable MDPs:
We propose the formalism of scalable MDPs in Definition to characterize an abstract class of MDPs where the MDPs within the class are differentiated based on changing scale parameter. Understanding the influence of this scale parameter on learning can promote better understanding the meta-challenge of extrapolating our results on small scale problems to large scale problems of the same class.
2. Polynomial Mixing Times: Theorem establishes the key result of this paper that as any scalable MDP is scaled, its mixing time must grow polynomially as function of the growing state space. This has major implications for regret analysis these MDPs.
3. Myopic Bias During Scaling: We demonstrate in Corollaries 2, 3, and 4 that Theorem implies traditional approaches to RL cannot efficiently seale to problems large size without experiencing myopic bias in optimization that slows down learning.
'Equal Contribution
IBB Research; Mila, Université de Montréal; 'Massachusetts Institute
of Technology
36th Conference on Neural Information Processing Systems (NeurIPS 2022).

---

4. Empirical Analysis of Mixing for Continual RL: We back up our theory with empirical analysis of mixing time scaling in continual RL settings based on the Atari and Mujoco benchmarks. Our analysis provides insight into why agents experience significant catas- trophic forgetting or other optimization instability when learning these domains. We hope that our analysis into the fundamental driver of these issues can open the door for more successful and principled approaches to continual RI. domains like these moving forward.
We refer readers to Appendix D) for detailed proofs of all propositions and theorems in our paper.
2 Formalizing Our Continual RL Setting
Aiming characterize a broad range of settings, we focus on the formulation of RL in continuing environments. As explained in Khetarpal et al. [1]. not only are supervised learning and episodic RL special cases of RL in continuing environments, but are their non-stationary variants (continual supervised learning and continual episodic RI.), despite violating the stationarity assumptions of their root settings. Indeed, approaches that do not acknowledge the more general RL in continuing environments setting exhibit myopic bias in their optimization when faced with non-stationarity [1].
Unfortunately, the popular discounted reward setting inserts the very same kind of myopic bias in optimization that we would like to avoid [2]. As typically implemented, discounting does not correspond to the maximization of any objective function over set of policies [3] and the policy gradient is not the gradient of any function [4]. These fundamental issues do not resolve as the discount factor approaches [3] and discounting does not influence the ordering of policies, suggesting it likely has no role to play in the definition of the control problem [5]. In contrast, the average reward per step objective, which explicitly includes an average over the stationary distribution, avoids inducing myopic biases and hence is well-suited for continual RL problems [5, 1].
2.1 Average Reward RL in Continuing Environments
RL in continuing environments is typically formulated using finite, discrete-time, infinite horizon Markov Decision Process (MDP) [6. 5], which is a tuple AM = (S, T, It), where the set of states, A the set of actions, R: S Sx A + [0. [emaa] is the reward function, and T SSSx - [0, 1] the environment transition probability function. At each time step, the learning agent perceives state E S and takes an action E A drawn from a policy π S x A + 0. with internal parameters E O The agent then receives a reward R(s, a) and with probability T(s'|s, next state s'. Markov chains may be periodic and have multiple recurrent classes, but optimality is difficult to define in such cases [7], making the following assumption necessary for analysis:
(e|[s, a) enters
Assumption All stationary policies are aperiodic and unichain, meaning they give rise to a Markov chain with single recurrent class that recurrent in the Markov chain of every policy.
Any RL problem may be modified such that Assumption holds by adding an arbitrarily small positive constant e to all transition probabilities in ('''|s, a) and renormalizing in which case the effect on the objective of each stationary policy is O(c) [8]. An important corollary to Assumption I that the steady-state distribution μM induced by the policy æ independent of the initial state:
Corollary All stationary policies π induce a unique steady-state distribution (s)
lim PK (s: =6==50 s|su) that is independent of the initial state such that Exes 1Ct (s) EnEA ((a)s)
n²" (s') Vs' E S.
Corollary implies that the long- term-trrmme rewards of any л will be independent of the current state. As such, the average reward per step objective p(IT) can be defined independently of its starting state [5]:
p(a) = lim
1
E R(s on)
lim E, +
R(s an)
h-000
h
Σ 1 (s) SES
a(als)
aeAA
Computing the average reward with the last expression is limited by the amount of time the Markov chain induced by the policy T (s'[s)
= Enea (a))))(s')s) a))a) needs to be run for before reaching
This corresponds what called ergodicity assumption for all stationary policies in [5].
2

---

the steady-state distribution jr" (s). This amount of time is referred to in the literature as the mixing time of the induced Markov chain. We denote (e) as the e-mixing time of the chain induced by x:
(c) = min {t max drv (P" = -(50). (² {c SuES
T mix
where dlv is the total variation distance between the two distributions. The so-called conventional mixing time is defined as mix = m (1/4). The conventional mixing time only gives insight about distributional mismatch with respect to the steady distribution, which led [9] to introduce the notion of a mismatch with respect to the reward rate. The c-return mixing time is a measure of the time it takes to formulate accurate estimate of the true reward rate. More formally, if we denote the h-step average undiscounted return starting from state s as p(T, s, h), then we define the E-return mixing time as:
(e) := min {A |P((T so, h') p()) S
Vso E S and Vh 2 n)
(2)
We will come back to this definition when we present our experiments. As emphasized in Levin and Peres [10], however, one should not get bogged down in the use-case specific definitions of mixing time (we prove their equivalent scaling behaviour in fact, c.f. Proposition 1 ). Rather, it is their shared property of being determined by both policy æ and environment M, and not simply property of the environment itself, that is important. Thus the environment's 's contribution can be assessed only through mixing times obtained from extreme policies such as the optimal policy, ti
An alternative approach for quantifying mixing is by considering the structure of the transition matrix T (s'(ss) induced by m. It is well known that the mixing properties of a Markov chain are governed by the spectral gap derived from the eigenvalues of the matrix 7 (s'[s). Unfortunately, it is difficult to reason about the spectral gap of a class of MDPs directly. Towards this end, one useful interpretation of Markov chain is random walk over graph ((T, with vertex set S and edge set {(ss s')}. for all s and s' satisfying (''(s)) (s]ss) + T (s) s') > O. The diameter D" of the Markov chain induced by is thus the diameter or maximal graph distance of (mT, T). It is defined using the hitring time hit ($1 (s)), the first time step in which 81 is reached following the Markov chain T (s'|s) from 80.
47
D=
max Ex (11((19)) ; D = min D" E0.
D' then denotes the minimum diameter achieved by any policy. All MDPs that follow Assumption
1 have finite diameter Dd for all policies [11]. Levin and Peres [10] (eq. 7.4) established the relationship, 2t 2 D", so that the diameter provides a lower bound for the mixing time and thus serves as very relevant quantity when conducting mixing time analyses.
2.2 The Role Tasks And Non-stationarity
The preceding single-task formulation of RL in continuing environments can, in fact, be used to formulate continual RL, which typically makes notions of multiple tasks and non-stationarity explicit. This is indeed useful construct because arbitrary non-stationarity precludes any consistent signal to learn from, and thus further assumptions about the environment structure must be made to make progress [1]. In this paper, we consider tasks as sub-regions of the total MDP (which alternatively can be thought of as independent MDPs connected together) and we assume the transition dynamics between and within tasks are both stationary. As highlighted in [1], this setting is quite general as it is capable of modeling many continual RI. problems. For example, it easily extends to partially observable variants: if the task component is not directly observed, the problem appears non-stationary from the perspective of an agent that learns from observations of only the within-task state. That said, the continual learning literature demonstrates that optimization issues are generally experienced whether task labels are observed or not [12). Our analysis of mixing times in this paper is an attempt to understand these difficulties even when the total MDP is fully observable and stationary.
To help the reader picture 1 in continual RL, we offer the example depicted in Figure Here, the agent's 's state space S is decomposed into a task component, x E Z and a within-task component, I E X.. For a policy, म, the pair of Markov chains induced by marginalizing over x and over z have diameters D and D7 respectively. Using the result connecting mixing times and diameters here, we can establish universal rule for problems of this type: 2 2 D 2 D 2 D where D" the diameter over the entire state space. This rule highlights the intimate connection between mixing
3

---

23
Universal Rule
2f 2 1 2 D D
D
Figure 1: Continual RL Setting: The state space 8 E S is decomposed as $ [z. 2] where & E 2 is the task and E X₂ is the within-task state. The mixing time, mixx is lower-bounded by the diameter over the full state space D The latter is lower-bounded by the diameter over the within-task state space D which in turn is lower-bounded by the diameter over the space of tasks, D
times and continual RL: task locality and bottleneck structure inherently lead to environments with correspondingly high mixing times due to high minimum diameters between states in different tasks.
Scalable MDPs
In this section, we formalize the notion of scaling in the context of MDPs and provide intuition about the effect of this scaling with the aid of the schematic shown in Figure 2. We assume MDPs can be described in terms of an n-dimensional parameter vector q E R", and that some subset of these dimensions are the parameters of interest that will be scaled up. We would like to analyze the effect of this scaling on mixing times.² With reference to Figure 1, these parameters can be non-spatial such the number of tasks, spatial such as the size of individual task. More generally and with reference to Figure 2, the effect of scaling up parameters can contribute to longer mixing times by adding bottleneck states (akin to increasing the number of tasks) and increasing the size of the regions generated by a bottleneck (akin to increasing the size of each task). How parameters are scaled is specified by a scaling function, controlled by scaling parameter, v. All MDPs accessible through a by varying y form a family of MDPs, C = (My), }, where Mr is the MDP specified by consider proportional scaling functions, for which subset of elements of
qu- In particular, are scaled linearly with v. In our experiments, we show results for proportional scaling of two MDP parameters central to continual RL: the number of tasks and the time between task switches.
As the MDP scales up according to a, the overall state space size will grow with [S] + 3o as v - co. Regions within the state space can also grow and the steady-state probability on them from π may change as a result. region S S is a connected subset of states with steady-
probability n² (R) = = E μ (s). The boundary of R. is subset 8R C R. with states having finite probability of transitioning to at least one state that is outside of R, EXESR (s'('(ss) > O Vs E OR. We denote the scalable regions and boundaries Ry and ØR., respectively. If the size of a region's s boundary grows faster than the region's interior, there no longer has an interior. In that case, the problem type is of bounded complexity and not relevant to the development of scaling friendly algorithms. We are thus interested in problems where scalable regions can maintain an interior as they are scaled (as measured by steady-state probability) in the limit of large v. See Appendix for a precise formulation leading to the following definition:
finite state space size at which the region
Definition A scalable MDP is a family of MDPs C₂ = {M,} arising from a proportional scaling function a satisfying the property that there exists an initial scalable region Ro with finite interior, n (ÖRo) < n² (Ro). that scales that nº' (ŌR,) nT (R₂) as and thus |S| -
"Scalar parameters with discrete domains are incorporated by embedding them into R. *Formally, this is scaling deformation, a I x I + R² parameterized by an order parameter that takes any qu to q = a agu. v). with (-, 0) as the identity map. Proportional scaling has qu o v for all i indexing scaled parameters such that = + vág. with Ag E H² giving the rates of linear growth in with v up from qo.

---

scalable region.
state space,
Mixing times grow with:
S
S
R.
1) larger region size
2) additional bottlenecks
legend:
unit length
S
trajectory
probability
bottleneck
Mixing times grow as MDPs are scaled up. Top left: A more general version of the continual RL setting shown in Figure I, where individual tasks correspond regions, of the state space, S, connected through bottlenecks (see legend). An example of the possible steady-state probability of I is shown in black gradient. The mixing time of an MDP can grow by increasing its diameter (number of equidistant arrow heads) via (1) scaling that increases the size of visited regions R. and thus the expected residence time 1 of x² (right) and/or (2) scaling that increases the number of bottlenecks between regions of the state space (bottom left).
Figure 2:
4 Polynomial Mixing Times
Prior work analyzing the scaling mixing times makes the practical distinction between slow mixing Markov chains that scale exponentially with size parameter and rapid mixing Markov chains that scale most polynomially. Since the learning speed of any algorithm lower bounded by the mixing time of the optimal policy [9]. environments with slow mixing Markov chain induced by the optimal policy may very well be outside the practical reach of RI algorithms. In this section, we would like to further characterize mixing times over the space of practically solvable problems of sufficient complexity to still be of interest for real-world applications.
For continuing environments, the tightest known lower bound satisfying Assumption has H-step regret Regret(H) Q( (=VD= D= | S C ( A(H) [11]. Additionally, because we know that 1 log Ai (IS)) 3 [11], we can bound our regret the general case as Regret(HH)
((VS ( Few practical problems are simple enough to exhibit diameters with such logarithmic contributions. More typical and thus of greater interest are diameters (and mixing times) having polynomial scaling in [S). Focusing on polynomial scaling is thus warranted, and provides more stringent lower bounds on regret. We thus consider the following definition:
Definition A set or family of MDPs C has polynomial mixing time if the environment mixing dynamics contributes S( multiplicative increase for some k >> 0) to the intrinsic lower bound on regret as |S] + co E
An immediate utility of Definition 2 is that it subsumes the diversity of different diameter and mixing time definitions by explicitly stating their equivalence in scaling with respect to the state space size:
Proposition 1 all MDPs M within the subclass of MDPs C have the tor the D= 2((S))) for some h > 0 we can say that C has a polynomial mixing time."
D
We can thus hereon focus on formulating scaling in MDPs through their state space size. One way to understand how a scalable region, Ry, contributes to the mixing time through its residence time, 1 i.e. the average time that n" spends in R during single visit. Using results from the theory of bottleneck ratios in Markov chains [10], we show that if scaling the MDP leads to to increasing by polynomial factor in SS) then the mixing time also increases at a polynomial rate:
'The bias span is only lower for weakly communicating MDPs violating Assumption that D 'The e-return mixing time (e((e) is for assessing mixing from the perspective of accumulated rewards, whereas the e- Cesaro mixing time (c) is for periodic problems that do not converge in the limit from Corollary I. See Appendix D for additional details.
5

---

Any scalable MDP Co exhibits a polynomial mixing time if there exists a scalable region Ry such that E y= [2, E (((S)))) for some k >> O.
Proposition 2
The purpose of Proposition 2 and Figure 2 are to provide intuition to readers about why scalable MDPs inherently must have polynomial mixing times. Our paper's main result builds off Proposition 2, to make general statement about the set of all possible scalable MDPs:
Theorem (Mixing Time Scaling): Any scalable MDP Co has polynomial mixing time.
Myopic Bias During Scaling
Monte Carlo sampling and bootstrapping are the two primary policy evaluation frameworks for RL [5]. Both implicitly assume that finite and fixed maximum frequency (*(T) E [0, 1] of policy improvement steps is possible for unbiased updates regardless of the problem size. We now propose three corollaries of Theorem that together argue how polynomial mixing times invalidate this assumption simply because (*) 2 1/Emiy and f grows over scalable MDPs. In practice, algorithm designers cannot afford to wait until reaching the mixing time before updating their model when mixing times are high. This results in a myopic bias in the policy improvement steps taken.
Monte Carlo sampling: In continuing environments with polynomial mixing times, this sampling procedure poses a problem when optimizing for p(πr). To get an unbiased estimate of p(Tr), we must be able to sample from the steady-state distribution μ (s), which is only available after fixx steps in the environment. Moreover, as demonstrated by Zahavy et al. [13] in the general case where no upper bound on the mixing time is known apriori, O([S (mxx) samples are needed to retrieve single unbiased sample from μr" (s). As such, it is clear that the length of the policy evaluation phase strongly depends the mixing time of the current policy and thus the maximum frequency (*(
of unbiased policy improvement steps decreases as the mixing time increases:
Corollary 2 A Monte Carlo sampling algorithm for policy π in scalable MDP C. has a maximum frequency of unbiased policy improvement steps (x) + as |S] + 0c.
For scalable MDPs of significant size. Corollary 2 implies that model-free Monte Carlo methods perform unbiased updates arbitrarily slowly and that model-based Monte Carlo methods will need arbitrary amounts of compute for unbiased updates even when a true environment model is known. As such, to address scaling concerns over large horizons, bootstrapping methods based on the Bellman equation are generally recommended [5].
This process is referred to as iterative policy evaluation [5] and is known converge to the true V in the limit of infinite evaluations of fixed policy. However, in practice, RL algorithms constantly change their policy as they learn and only can afford partial backups during policy evaluation when applied theoretical principle in RI. is that as long as the agent constantly explores all states and actions with some probability. bootstrapping with only partial backups will still allow an agent to learn n² in the limit of many samples [5]. However, sample efficiency can still be quite poor since partial backups insert bias into each individual policy evaluation step. This bias, referred to as staleness [14], arises when the value function used for bootstrapping at the next state is reflective of an old policy that is currently out of date. Unfortunately, if we want to avoid staleness bias during learning, the length of policy evaluation for each policy must once again depend strongly on the mixing time:
Bootstrapping for Evaluation:
large-scale domains. Indeed, a foundational
Corollary 3 A bootstrapping algorithm with policy in scalable MDP C2 has maximum frequency of unbiased policy improvement steps f (*(T)) + as |S| + co.
Bootstrapping for Improvement: the process of using bootstrapping for policy improvement as popularized by dynamic programming algorithms such as policy iteration and value iteration, as well as by RI. frameworks such as temporal difference (TD) learning and actor-critic. The theoretical foundation of these approaches is the policy improvement theorem, which demonstrates the value of taking a greedy action with respect to the estimated action-value function Q" (s, a) at each step. The policy improvement theorem then tells us that policy changes towards x' are worthwhile as (*(s) < Q (s. x'ss.'(()) (s)) < V= (s) eventually yielding n" in the limit of many changes [5]. However, this improvement unlikely to be efficient when mixing times are high. To demonstrate this, we decompose value into the transient and limiting components respectively (*()) = trans (x) + V (s). While clearly V*(s) S Q" (x, x (s)), the functions both follow π into the future, so their limiting distribution is the same implying that trans (s) < Q (s, n' r')s) and V (s) Q Dim (s, x (s)).

---

Corollary 4 Policy improvement steps with bootstrapping based on the Bellman optimality operator guarantee monotonic improvement V vamss but do not for Vim
See Appendix A for details on how these ideas connect to relevant off-policy or offline RL approaches and to the literature on catastrophic forgetting in continual RL.
6 Empirical Analysis of Mixing Behavior
We have established theoretically that scalable MDPs have polynomial mixing times and that polyno- mial mixing times present significant optimization difficulties for current approaches to RL. However, we still must demonstrate 1) that scalable MDPs are useful construct for understanding the scaling process within modern continual RL benchmarks and 2) that large mixing times become a significant practical impediment to performing reliable policy evaluation in these domains. Towards this end, we consider empirical scaling of the mixing time with respect to the number of distinct tasks, | and to the task duration, T, which controls the bottleneck structure. For this purpose, we evaluate a set of high-quality pretrained policies. In both cases, we report empirical results via the dependence of the e-return mixing time (equation 2) on the relative precision with which the reward rate is estimated. Presenting the relationship in this way ensures we isolate the contribution that myopic policy evaluation has on the performance relative to the optimum and that high mixing times are not inflated by spurious sources of distributional mismatch that do not hinder policy evaluation.
Empirical Mixing Time Estimation. In order to quantitatively estimate the c-return mixing time ir (e) in equation 2, we need estimate two terms: the average true reward rate p(T)) (which is agnostic to the start state), and the h-step undiscounted return p(h, 80, TT) from a start state So for all E S. We can then provide (e) for any desired value of To calculate p(T)) we unroll the policy in the environment for a large number of time steps (more than a million steps) while accumulating the rewards that we received and finally compute the average over the total number of environment interactions. Estimating p(h, 8, π for every start state & E S in equation 2 is challenging because of the large state spaces in Atari and Mujoco. Hence we rely on approximations where we choose a subset of states from S to estimate p(h, s, T). However, since the estimates could be biased based on the start states we choose, instead of randomly sampling fixed set of start states, we leverage reservoir sampling [15] to ensure that the limited fraction of possible start states that we consider is unbiased according to the on-policy distribution. Conservative definitions of the mixing time take the maximum over start states [9]. Here, since we are interested in the characteristic mixing time size, we report the average among start states, which ensures that the mixing times reported are representative of those actually needed for evaluation over the course of on-policy training. Finally, in order to provide an intuitive interpretation for e across domains, we leverage the relative error, c/ e/T()), ) as a common reference point for comparison. We can then calculate the e-return mixing times for fixed relative error. See Appendix B for further details.?
Setting of Interest. We focus our experiments on the following scalable MDP formulation that is broadly representative of the majority of work continual RL [16, 17, 18, 19, 20]:
Example (Continual Learning with Passive Task Switching): Consider an environment with tasks E Z and within-task states x E Xz. The residence time of the region encompassed by task z before moving to another region is fixed for all tasks at T for any x such that tx, T 22 E 2. Regardless of the way that tasks are connected, the diameter of such an MDP must scale as D [((T) because the residence time bounds the minimum possible time to travel between two states in different tasks.
Utilizing our formulation of scalable MDPs with initial MDP parameters qu (T, (2). the space
of possible proportional scaling functions on J only, |2| only, and both T and [2] simultaneously
are a-(q6. v) = (r + av, [1), 0| (qo 2) (T, 12| + bv), and o 07,12)(90.) v) = (r + az, |2| + +bv). respectively, where a, b E R span the respective spaces.
6.1 A Simple Motivating Example
We consider a simple 10x 10 10 3-dimensional grid world environment with 6 actions corresponding to up and down actions each dimension. In this environment, we can define 1,000 different tasks corresponding to considering each unique state as a goal location. At each time-step the agent is sent
OOr code is available at http://gtttb.cooooSmnmmnlppppyyt mixing times.git.
7

---

3D Grid World: REINFORCE 10k Triningg Steps Per Task
1.0
0.9
Final Reward Rate
0.8
0.7
episodic
- T= 100
0.6
T= 1000
== 10000
0.5
10
10'
10'
|2]
Figure 3: Average reward rate across tasks at the end of training function of | and
60-dimensional concatenation of six 10-dimensional one-hot vectors. The first three one-hot vectors correspond to the agent's x.y. and Z coordinates and the second three correspond to the goal location.
Myopic Optimization Bias: As have motivated in Section 2.2, this environment is made to demonstrate the difficulty associated with myopic optimization bias even when task boundaries and their relation are fully observable. We consider continual episodic RL formulation following the description in Example where task sequences arise from changing the goal location every T steps and the set of goal locations defines the set of tasks, Z. As such, the diameter of the MDP clearly increases as T and the number tasks [2] are scaled up, leading to at least linear scaling. As result, an agent that updates only based the current episode experiences myopic bias with respect to the steady-state distribution over which the tasks are uniformly balanced.
Training Procedure: The 60-dimensional sparse observation vector is processed by multi-layer perceptron with two 100 unit hidden layers and Relu activations. The agent performs optimization following episodic REINFORCE. We explore different configurations of this scalable MDP by varying | from to 1,000 and varying from 100 10,000. An important baseline consider the extreme of switching tasks after every episode as in multi-task RL (which is generally considered an upper bound on continual RL performance). The agent receives a reward progress towards its goal and a reward of 0 otherwise. This implies that the reward rate of x² is p(TT)== = 1 and that the reward rate a uniform action policy is 0.5 for every task = E regardless of the distance travelled from the start state for each episode. For each |2| and we train the agent for 10,000 total steps and report the average reward rate after training as an average across 300 seeds, which correspond to randomly selected task progressions. See Appendix C for further details.
every step makes
Results: We display the results of these experiments in Figure 3. It interesting to notice the episodic transition performance, which can near flawlessly learn a single task in 10,000 steps but struggles significantly with interference in the multitask setting. Performance goes down from to 30 tasks and appears to rebound afterward, which is logical because the similarity between incoming tasks and old tasks is increasing and the total number of training steps across tasks is going up. When both r and [Z] are high at the same time, learning performance is quite poor (not much better than a uniform policy). The starting location always the same corner, so some commonalities can be exploited even by policy experiencing significant interference. Performance bottoms out after fewer tasks when 7 is larger, which makes sense as that when the myopic bias of optimization is greatest.
6.2 Overview of Empirical Findings on Atari and Mujoco
Domains of Focus. We perform experiments involving sequential interaction across Atari environ- ments: Breakout, Pong, SpaceInvaerss, BeamRider, Enduro, SeaQuest and Qbert. This is a typical number of tasks explored the continual RL literature [16, 17, 18, 19, 20]. We consider a sequential Atari setup where the individual environments can be seen as sub-regions of larger environment that are stitched together (see Figure/ and Appendix for further details). To demonstrate the validity of our results on vector- vector-valued state spaces, we also consider sequential Mujoco experiments with

---

1e6
60
Algorithms
A2C
(edde) / T/Z)
DON
40
20
1
0.05 0.1
0.15
0.2
0.3
0.5
0.05
0.1
0.
0.2 0.3 0.5
delative Error
Relative Error
Figure 4: Mixing time as a function of relative error for fixed scaling parameters. Left: e-return mixing time (equation 2) as a function of relative error, c/p(T), ), in reward rate estimation for standard algorithms. Right: Same left, here normalized by 7 2| where 10,000 and | 7. Note the difference in range on the y-axis, which reflects this normalization.
50
Algorithms
200000
A2C
150000
DON
PPO
100000
20-
50000
[2]
|2]
Figure 5: Mixing time scaling with the number of tasks (]. Left: Average c-return mixing time across different task combinations 2 for different algorithms. Right: Same left, here normalized by r|2] where т =1,000. Note the difference in range on the y-axis, which reflects this normalization.
the following 5 environments: HalfCheetah, Hopper, Walker2d, Ant and Swimmer. For both our sequential Atari and Mujoco experiments, we leverage high-performing pretrained policies that are publicly available [21] for mixing time calculations. We leverage task labels to use the pretrained model specific to each task as our behavior policy as appropriate when tasks change.
Mixing Time as a Function of Relative Error. As the task connection structure following Example
1 can take any arbitrary form, we have focused our experiments on random transitions between tasks. In Figure 4 we plot both tse (e) and t (e)/r for T 10,000 and Z = 7 as a function of the relative error p(T,, s, h) with respect p( i.c. e p(TT, s, h) (TT). We see the intuitive fact that higher demands for precision define longer mixing times and that it is clear that the lower bound on the diameter is very conservative estimate of the mixing time where we only see t (e)/T|Z) < for reward rates estimated to a poor tolerance of more than 30% error.
We now analyze Example in the case where the state space and diameter grow increase the number of tasks |Z]. Specifically we scale | from to 4 to as r is kept fixed at 1,000 and generate 10 random task combinations from the list of for each value of [ In Figure 5 we plot the resulting mixing times for a precision of 10% error in approximating the reward rate. We find that there is linear trend in the expected mixing time and not just the theoretical lower bound.
Scaling |z].
Scaling r. We finally analyze Example in the case where the state space held constant but the diameter grows with the increasingly severe bottleneck structure we increase т. Here we consider |2| 7 and 1,000, 3,000, 10,000, and 30,000, while calculating p(h, 8, .) and p(xx) by unrolling
te7
1+7
Aigorilmns
100
SAC
ACC
75-
0.8-
PFD
1.0-
50
0.6
DON
0.5
04-
02-
1000
3000
10000
30000
2000
3000
10000
30000
1000
5000
10300
30000
2000 3000 10000 30000
(a) Continual Mujoco |Z|
(b) Continual Atari |2| =
Figure 6: Mixing time scaling with the task duration, Left (a, b): c-return mixing time across
different T values for different algorithms. Right (a, b): Same as left, here normalized by 7| r|. Note the difference in range on the y-axis and the distinct subset of algorithms tested (see legend).

---

the policy π for TX 1,000 environment steps each. In Figure 6 we once again plot both t (e) and the value normalized by the diameter lower bound t (e)/T(Z find that empirical average mixing times scale linearly with increasing T and not just the lower bound.
6.3 Implications For Continual RL
In summary, we have observed in Figure 4 that average mixing times reach staggering high for lower relative errors, and shorter mixing times are associated with very high relative errors. Additionally, in Figures 5 and we observed that, for broad class of algorithms, there seems to be a linear dependency of the expected mixing time with increasing Z and increasing T.
Optimization Instability for Continual Atari. While we have empirically established that mixing times scale to be quite large in the Atari domain following Example and established theoretically how RL approaches struggle when this is the case in Section 5, would like emphasize that the prior literature applying deep RL to continual learning on Atari has empirically come to the same conclusion. Indeed, [17] looked at continual learning across 10 Atari games with a randomized duration between task switches and found that all approaches were significantly outperformed by the single task baseline, reflecting significant instability in optimizing across tasks. Additionally, perhaps the most common setting in the literature considered by [18], [19], and [22] is to train on set of 50,000, 000. Note that extrapolating from our results would indicate
tasks where |z| 6 and average mixing times on the order of R 15 billion steps for a precision of 5% error or R 5 billion steps for a precision of 10% error. Across number of RL approaches tried on these domains, we would expect, all approaches have experienced significant instability in their learning curves. A very popular failure mode is approaches that display too much plasticity such that their performance for a task goes through big peaks and valleys resulting from myopic bias towards optimization on the current task. This phenomena often known in the literature as catastrophic forgetting [23].
7 Inspiring New Approaches for Continual RL
While the focus of our paper is on highlighting the difficulty of the polynomial mixing time problem, not proposing an approach to solve it, we believe that our analysis provides significant insights that the community will be able to draw on to build better approaches for continual RL:
Direct Steady-State Estimation: In the context of commonly considered problems that follow the high-level structure of Example I, we have showcased the deep connection between catastrophic forgetting and myopic bias in the presence of very large mixing times. In Appendix A we demonstrate how this perspective explains some of the value of replay based approaches in this setting. Moreover, this perspective naturally points towards approaches that directly reason over the steady-state distri- bution as natural solution to the catastrophic forgetting problem. In Appendix C we consider simple tabular RL experiments across 3 example classes of scalable MDPs. Our analysis demonstrates that on-policy and off-policy versions of Q-Learning that perform policy evaluation using an estimate of the steady-state distribution, derived from matrix inversion of a tabular environment model, con- sistently outperform standard model-based and model-free baselines in terms of lifelong regret as environments are scaled up. Even though estimating the steady-state distribution would clearly be quite challenging in complex state and observation spaces, recent approaches have made great strides towards developing practical and scalable approaches leveraging data buffers [24].
Tracking Approaches: It was originally noted by [25] that it could be a better strategy even in stationary environments with temporal coherence to learn to track the best local solution instead of attempting to converge to a globally optimal fixed policy. This indeed, may be a necessity in environments that experience extreme temporal coherence governed by high mixing times and could provide a formalization of the benefit for approaches based on meta-learning in this context as noted by [25]. For example, [26] recently was successful in addressing the non-stationarity of multi-agent RL by learning to converge to recurrent set of joint policies rather than a single joint policy.
Looking Forward. In this work, we have considered the implicit premise of the current continual RL literature that results from currently manageable small-scale experiments are indicative of performance for the large-scale aspirational use cases of the future. In particular, we have highlighted that mixing times will scale significantly as the problems we deal with are scaled and how traditional approaches to RL are ill-suited to deal with this. We hope that our work will encourage the community to carefully consider the theoretical implications of scaling environments, especially with regard to how proposed continual RL algorithms scale with the mixing time.
10

---

Acknowledgements
We would like to thank Riashat Islam, Gerald Tesauro, Miao Liu and Sarthak Mittal for helpful discussions. Irina Rish acknowledges the support from the Canada CIFAR AI Chair Program and from the Canada Excellence Research Chairs Program. We also thank the IBM Cognitive Compute Cluster, the Mila cluster, and Compute Canada for providing computational resources.
References
[1] Khimya Khetarpal, Matthew Riemer, Irina Rish, and Doina Precup. Towards continual rein- forcement learning: A review and perspectives. arXiv preprint arXiv:2012. 2020.
[2] Anton Schwartz. A reinforcement learning method for maximizing undiscounted rewards. In Proceedings of the tenth international conference on machine learning, volume 298, pages 298-305, 1993.
[3] Abhishek Naik, Roshan Shariff, Niko Yasui, Hengshuai Yao, and Richard S Sutton. Discounted reinforcement learning is not an optimization problem. arXiv preprinl arXiv:1910.02144 2019.
[4] Chris Nota and Philip S. Thomas. Is the policy gradient a gradient? CoRR, abbs/1906.07000
2019. URL bett:///rrxse org/ awspaaab...../0../ 07073.
[5] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. 2018.
[6] ML Puterman. Markov decision processes. 1994. Jhon Wiley & Sons, New Jersey, 1994.
[7] Yi Wan, Abhishek Naik, and Richard S Sutton. Learning and planning in average-reward markov decision processes. arXiv preprint arXiv:2006. 16318, 2020.
[8] Dimitri Bertsekas. A new value iteration method for the average cost dynamic programming problem. SIAM journal on control and optimization, 36(2)7422-79, 1998.
[9] Michael Kearns and Satinder Singh. Near-optimal reinforcement learning in polynomial time. Machine learning, 49(2):209-22) 232, 2002.
[10] David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
[11] Thomas Jaksch, Ronald Ortner, and Peter Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, (4).. 2010.
[12] Matthias De Lange, Rahaf Aljundi, Mare Masana, Sarah Parisot, Xu Jia, Aleš Leonardis, Gregory Slabaugh, and Tinne Tuytelaars. A continual learning survey: Defying forgetting in classification tasks. IEEE transactions on pattern analysis and machine intelligence, 44(7): 3366-3385, 2021.
[13] Tom Zahavy, Alon Cohen, Haim Kaplan, and Yishay Mansour. Unknown mixing times in apprenticeship and reinforcement learning. In Conference on Uncertainty in Artificial Intelligence, pages 430-439. PMIR, 2020.
[14] Emmanuel Bengio, Joelle Pineau, and Doina Precup. Correcting momentum in temporal difference learning, arXiv preprint vrXiv:2106.03953 2021.
[15] Jeffrey S Vitter. Random sampling with reservoir. ACM Transactions on Mathematical Software (TOMS), 11(1):37-57, 1985.
[16] Andrei Rusu, Neil Rabinowitz, Guillaume Desjardins, Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell. Progressive neural networks. arXiv preprint arXiv: (66666006677 2016.
[17] James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Ctrabska-Bawwinskee et al. Overcoming catastrophic forgetting in neural networks. Proceedings of the National Academy of Sciences of the United States of America, 114((3),3511-3526, 2017.
11

---

[18] Jonathan Schwarz, Wojeiech Czarnecki. Jelena Luketina, Agnieszka Trabska-Barwiinse Yee Whye Teh, Razvan Pascanu, and Raia Hadsell. Progress & compress: A scalable framework for continual learning. In International Conference on Machine Learning, pages 0728-4537,
2018.
[19] David Rolnick, Arun Ahuja, Jonathan Schwarz, Timothy Lillicrap, and Gregory Wayne. Experi- replay for continual learning. Advances in Neural Information Processing Systems, 32: 350-360, 2019.
[20] Matthew Riemer, Ignacio Cases, Robert Ajemian, Miao Liu, Irina Rish, Yuhai Tu, and Ger- ald Tesauro. Learning to learn without forgetting by maximizing transfer and minimizing interference. arXiv preprint arXiv:1810.11910 2018.
[21] Antonin Raffin. RI baselines3 zoo. http::///gttuub..omm/aaa//////// 2020.
[22] AGI-Labs. Continual rl project. httpss//githhb..com/6ll----aa Lwt.://bo..ooo/eA--aaaaaaao//o//
2021.
[23]
Michael McCloskey and Neal J Cohen. Catastrophic interference connectionist networks:
The sequential learning problem. Psychology of learning and motivation, 24:109-16: 1989.
[24] Junfeng Wen, Bo Dai, Lihong Li, and Dale Schuurmans. Batch stationary distribution estimation. arXiv preprint arXiv:2003.0077 007022 2020.
[25] Richard S Sutton, Anna Koop, and David Silver. On the role of tracking in stationary envi- ronments. In Proceedings of the 24th international conference on Machine learning, pages 871-878, 2007.
[26] Dong-Ki Kim, Matthew Riemer, Miao Liu, Jakob N Foerster, Michael Everett, Chuangchuang Sun, Gerald Tesauro, and Jonathan P How. Influencing long-term behavior in multiagent reinforcement learning. arXiv preprint arXiv:2203.03533, 2022.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
12

---

(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you' ro using/curating? [N/A]
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "gwgOWytbVy_", "reviewer": "Reviewer_bA29", "summary": "This paper devises a broad class of MDPs, referred to as Scalable MDPs, for which they provide mathematical evidence to suggest that continual learning algorithms will struggle on. The authors provide several characterizations of the class of Scalable MDPs based on simpler statistical properties of the Markov chains induced by Markov policies. Furthermore, empirical evidence from common RL benchmarks is given to support the hypothesis that continual learning algorithms struggle in Scalable MDPs.", "questions": "*Assumption 1*: What is a *unichain* policy? Does this assumption just\nmean that all stationary policies induce ergodic Markov chains?\n\n*Corollary 1*: I believe there is a notational mistake here, it says\n$\\mu^\\pi(s) = \\lim_{t\\to\\infty}P^\\pi(s_t\\mid s_0)$, where the RHS is\ncompletely independent of the LHS. I believe $s_t$ corresponds to $s$\nand you're arguing that $s_0$ is irrelevant, but this is a little\nconfusing.\n\nIn the equation under line 81, a similar notational mistake is made,\nwhere I'm assuming $s_h$ corresponds to $s$.\n\n*Section 3*: The definition of a scalable MDP, as well as other concepts\nintroduced in this section, should be formalized. I also don't find\nFigure 2 and its exceptionally long label particularly helpful for\nillustrating the concepts.\n\n- *Intrinsic dimensions*: what is the difference between the intrinsic\n  dimensions of the state space and the dimensions of the state space\n  themselves? Also, who's to say which dimensions should be considered\n  extensive rather than intensive? For example, the number of spatial\n  dimensions of a gridworld can conceivably be interpreted as both\n  extensive and intensive for some tasks, or at least the extensive and\n  intensive dimensions can be highly correlated. In this case, I'm not\n  sure I understand why it's useful to distinguish them like this.\n- *Extensive and Intensive dimensions*: this is more of a nitpick, but\n  where do these names come from? They are not at all intuitive to\n  me. Maybe external/internal?\n- *Scaling functions*: lots of notation is introduced here, and in my\n  opinion, it's \"over-engineered\". It says \"... each $\\sigma\\in\\Sigma$\n  induces $\\mathbb{C}_\\sigma$, a $\\nu$-parameterized abstract\n  class...\" -- if the class is parameterized by $\\nu$, why is it called\n  $\\mathbb{C}_\\sigma$? Then, it says \"An important example of $\\sigma$\n  is *proportional scaling*, $\\sigma(q, \\nu) = c(\\nu)\\circ q$ with\n  $c_i(\\nu)\\in\\Theta(\\nu)$. There's a lot that confuses me here, namely:\n  1. What is $\\Theta(\\nu)$?\n  2. What is the $\\circ$ in $c(\\nu)\\circ q$? Usually $\\circ$ refers to\n     function composition, but I believe this should actually be\n     elementwise multiplication, which I'd expect to be written as\n     $c(\\nu)\\otimes q$.\n  3. It's confusing to have $\\sigma$ parameterized by a scalar $\\nu$\n     only to then introduce this new function $c$ with the purpose of\n     (to my understanding) transforming $\\nu$ into a vector by some\n     mysterious process. Why not allow $\\sigma$ to be parameterized by\n     an arbitrary object and do away with $c$ altogether? This is what I\n     meant by \"over-engineering\", my impression is that there are too\n     many \"free variables\" here than are necessary.\n  4. Since ultimately you're going to restrict $\\sigma$ to be a\n     proportional scaling function, why bother with all of the\n     structural conditions you impose on $\\sigma$, like $\\sigma(\\cdot,\n     0)$ being the identity? Especially since $\\sigma$ will be\n     multiplicative, having $0$ represent the identity is awkward and\n     all of these conditions just make the presentation much more\n     difficult to comprehend.\n\nAfter having finished section 3, my impression is that all of this\nmachinery that was introduced will be used simply to encode a scaling\noperation on the features of the state space. Is it really necessary to\nintroduce all of this abstraction?\n\nOn line 142, it says\n\n      Applying this distinction to our task formulation and\n      example in Figure 1, intensive scaling increases the number\n      of tasks, and extensive scaling increases the size of each\n      task.\n\nThis sentence is much clearer to me than the previous ones discussing\nextensive and intensive scaling. What does the remainder of section 3\ntell us that this statement doesn't?\n\n*Definition of Scalable MDP*:\n- Is $\\mathbb{M}$ ever defined? I assume it's the set of all classes of\n  MDPs than are induced by scaling functions?\n- Why specify that $\\sigma$ is a scaling operation on a subset of\n  intrinsic dimensions? I think it would be clearer to omit this, since\n  one can avoid scaling dimensions $i$ by having $c_i(\\nu) = 1$.\n- What is an /applicable scalable/ region?\n- Why must $\\mu^{\\pi^*}(\\mathcal{R})\\leq 1/2$? Is this what defines an\n  applicable scalable region? What is the significance of such a region?\n- What does it mean for the inequality to be preserved as\n  $|\\mathcal{S}|\\to\\infty$? Why/how is the cardinality of the state\n  space increasing?\n\nI think it would go a long way to give some intuition for this\ndefinition.\n\n*Definition 2*: Is this definition novel? If so, I think the name should\nbe changed -- the \"polynomial mixing time\" is defined here in terms of\nregret, and very indirectly w.r.t. the mixing time.\n\nRather, why not define polynomial mixing time by Proposition 1? For\nexample, \"a family of MDPs $\\mathbb{C}$ is said to have a polynomial\nmixing time if for each $\\mathcal{M}\\in\\mathbb{C}$ we have\n$\\min(t_{\\text{ret}}^{\\pi^*}, t_{\\text{ces}}^{\\pi^*},\nt_{\\text{mix}}^{\\pi^*}, D^{\\pi^*}, D^*)\\in\\Omega(|\\mathcal{S}|^k)$...\".\n\n*Proposition 2*: What are \"scalable regions\"? I'm assuming this is the\nsame as the \"applicable scalable regions\" from before, but then it\ndoesn't help to specify that the MDPs have scalable regions /and/ that\nthere exists a region $\\mathcal{R}$ with $\\mu^{\\pi^*}(\\mathcal{R})\\leq\n1/2$. As I understand it, Proposition 2 claims that a family of MDPs has\na polynomial mixing time if it has a scalable region with polynomial\nresidence time.\n\nRight before Theorem 1, it says\n\n      The purpose of Proposition 2 and Figure 2 are to provide\n      intuition to readers about why scalable MDPs inherently must\n      have polynomial mixing times.\n\nAt least personally, I find Figure 2 to be much too dense and\nmysterious. For example, why are $\\mathcal{R}$ and\n$\\mu^{\\pi^*}(\\mathcal{R})$ pointing to two distinct areas always?  Also,\nwhat are the translucent blue \"shadows\" around the black paths?  How\ndoes the number of equidistant arrowheads reflect the residence time?\n\n*Section 5*: Why is this called \"myopic\" bias? The word \"myopic\" occurs\nonly in the section title. Also, about the Corollaries, I believe the\nsame results would hold for arbitrary families of MDPs (since\n$t_{\\text{mix}}\\in \\Omega(\\log|S|)$, so $f^*(\\pi)\\in o(1)$).\n\nMoreover, most of the content in this section is background material for\nvalue-based RL methods, and has nothing to do with continual learning\nand/or mixing times. I think it would be better to move such content to\nthe background section or to the appendix, as it disturbs the flow of\nlogic in the paper.\n", "limitations": "As mentioned, I believe the method of empirically validating the theoretical asymptotic results has limited value.\n\nMoreover, the proofs of just about all of the theoretical claims were omitted, which limits the soundness of the paper. Having said that, I believe some of the definitions presented in this work are valuable contributions on their own.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\nI believe the direction of work chosen in this paper -- that being the goal of classifying families of MDPs by complexity in certain regimes -- to be very interesting and important. The presentation of the paper is nice and the grammar is mostly quite good.\n\n# Weaknesses\n\nUnfortunately, I find much of the mathematical formalism to be highly confusing and convoluted. I believe many of the abstractions presented in the paper are unnecessarily complicated, making it difficult to parse some sections of the paper. Also, I found that very little intuition was given for the definitions that were contributed in this paper. Figure 2 is extremely difficult to comprehend (at least in my opinion). Finally, I don't quite see the value in the empirical results. It doesn't really make sense to me to estimate asymptotic rates this way, since the number of tasks ranges only from 1 to 7. The empirical results do not necessarily suggest any asymptotic trend. While I agree that those inferred by the authors are fairly reasonable, they're also not very surprising, so I don't find the empirical evidence helped convince me of any properties of Scalable MDPs. \n\nAlso, it appears that the authors submitted a copy of the paper in place of the appendix, so I could not find any of the proofs. This is really a shame, since I was hoping that reading through the proofs would help me understand the intuition and rationale behind some of the contributions of this work.\n\nDue to the lack of proofs as well as what I understand to be a weak method of empirical validation, I have to give this a score of 3. \n\n### Post-Rebuttal Edit\n\nThe revised version of the paper is, in my opinion, quite a bit more clear and easy to read. I still believe Figure 2 can be improved, since I find it difficult to infer from the diagram what is said in its caption. In general, the authors addressed most of my concerns. In particular, the simplified mathematical framework is tremendously more legible (to me) than the original one.\n\nUpon reading the proofs, the most I can say is that they look reasonable and I couldn't find any clear flaws. Having said that, some of the proofs allude to theorems from the literature that I'm not very familiar with, and I have not had as much time as I would have liked to dive deeper into these.\n\nOverall, I do think this paper presents an interesting approach to understanding the complexity of continual RL. I have increased my score to reflect the clarifications in the revised paper as well as the inclusion of the proofs.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "WdI6AjlAfFj", "reviewer": "Reviewer_oAr4", "summary": "This paper investigates the effect of scalability and mixing time in MDPS for RL. The Authors introduce scalable MDPs as a family where the state space or a region of that can be scaled subject to a scaling parameter and a scaling operation. They show that any scalable MDP has a polynomial mixing time with respect to state space. The authors also discuss that traditional RL algorithms (monte carlo and bootstrapping) cannot scale well  to larger size problems because of the myopic bias which slows down learning. They conclude the paper by showing that polynomial mixing time can emerge in continual RL tasks (atari environments) and analyze instability caused by this bias.", "questions": "In empirical studies the average mixing time is used instead of the actual mixing time (with maximum), would you explain how this might change your settings and empirical results? for example if we change the starting state distribution, how does your empirical result change? \n\nThis paper is on the analysis side of the problem that arises because of the polynomial mixing time, I was wondering if authors can provide some clues on possible approaches to solve the issue?", "limitations": "In section 7, Authors have discussed the limitations of their paper from different perspective.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: Paper is fairly well-written, the topic of this paper and analyzing mixing time induced by policies is fundamental to RL. The flow of the paper on theorems and corollaries and the discussion after was enjoyable to read.\nWeakness: For the purpose of reach in the RL community,  I think it would be nice if the authors could start with a simpler markov chain in the empirical section to show the mixing time, bias and etc, before jumping to atari environments", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2Ina4Rqum4a", "reviewer": "Reviewer_hA9x", "summary": "In this paper, the authors propose scalable MDPs in which the MDPs can be defined using the scale parameter. Using scalable MDPs, the learned algorithm can be evaluated on small scale problem to large scale problem. Based on the notion of mixing times, they show that the scalable MDPs have mixing times that scales polynomially. In the experiments, they show the empirical analysis of mixing behavior on Atari games, and the results show that the mixing time on given scalable MDPs is a function of relative error and the number of tasks.", "questions": "Specified in Cons.", "limitations": "None", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros:\n\nThe definitions of each component on scalable MDPs are well explained, and the theorems and experimental results are consistent. \n\nCons:\n\n1. It would be better to carry out the experiments on Roboschool or MuJoCo that have vector-valued state space. Is the mixing time much smaller than the original experiment?\n\n2. Though it focuses on the scalable MDPs in terms of the continual reinforcement learning, the performance of continual learner in this setting is not mentioned. As a result, it was hard to notice the importance of the mixing time in scalable MDPs for the continual reinforcement learning scenario", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-4qTHD4dF_l", "reviewer": "Reviewer_VEPZ", "summary": "In this paper, the authors discuss bounds on the mixing time for the continual RL setting. In particular, the authors raise the setup of scalable MDPs. The authors further characterize the condition for families of MDPs to have polynomial mixing time and show that the scalable MDPs have polynomial mixing time, which guarantees a tight lower bound of the corresponding regret. The authors then discuss the myopic bias that arises for the scalable MDPs with polynomial mixing time. Finally, the authors conduct experiments on Atari to justify their theoretical findings.", "questions": "-The setup of continual RL seems to be confusing to me. Given that the transition of states still follows a (static) probability function both across tasks and within tasks, what makes it different between a regular MDP and the continuing environment?\n\n-The setup of scalable MDPs seems to be a bit confusing to me as well. How does the raised expansive property restrict the family of scaling functions and why is it necessary? Could the authors provide more intuition in the definition of scalable MDPs (Definition 1)? Could the authors raise a more concrete example for better understanding? For instance, simple tabular MDPs with explicitly specified transition dynamics, intrinsic variable $q$, and the scaling functions $\\Sigma$ are sufficient to demonstrate. In addition, the results could be greatly strengthened if the authors could justify the generality of such scalable MDPs in capturing real-world applications.\n\n-In terms of the discussion of myopic bias, the authors discuss the effect of mixing time on the sample efficiency of policy evaluation. Does similar arguments also hold for value-based approaches such as the fitted-Q-iteration (FQI)? In the typical previous analysis, FQI hinges on good coverage of (notions of) steady-state probability of optimal policy (e.g.[1, 2]). Does such coverage presume tractable mixing time for the policies that collect the data?\n\n-For the experiment, it would be better if the authors could explain why the selected tasks with the scaling parameters fit into the definition of scalable MDPs in Section 3.\n\n\n\n[1] Chen and Jiang. Information-Theoretic Considerations in Batch Reinforcement Learning. 2019.\n\n[2] Xie et al., Bellman-consistent pessimism for offline reinforcement learning. 2021.", "limitations": "N.A.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n-The mixing time is scarcely explored yet crucial in the analysis of MDP. The analysis and the perspective of the authors are novel to me. In addition, the theoretical findings are backed up by experiments on Atari.\n\nWeaknesses:\n\n-The presentation of the authors makes it unclear whether such analysis captures real-world applications of RL and hinders the usefulness of the results. See Questions for the details.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept