11institutetext:  Department of Computer Science, Government College of
Engineering and Textile Technology, Serampore, Calcutta, India
22institutetext: Department of Mathematics, Kuwait American School of
Education, Salmiya, Hawalli, Kuwait 33institutetext: Department of Computer
Science, Vellore Institute of Technology, Vellore Campus, Vellore, Tamil Nadu,
India 44institutetext: Department of Mathematics, Velammal Engineering
College, Anna University, Chennai, Tamil Nadu, India

44email<EMAIL_ADDRESS>

# A Comparative Investigation into the Operation of an Optimal Control
Problem: The Maximal Stretch

Anurag Dutta 11 * * K. Lakshmanan 22 John Harshith 33 A. Ramamoorthy 44

###### Abstract

Mathematical Selection is a method in which we select a particular choice from
a set of such. It have always been an interesting field of study for
mathematicians. Combinatorial optimisation is the practice of selecting the
best constituent from a collection of prospective possibilities according to
some particular characterization. In simple cases, an optimal process problem
encompasses identifying components out of a finite arrangement and
establishing the function’s significance in possible to lessen or achieve
maximum with a functional purpose. To extrapolate optimisation theory, it
employs a wide range of mathematical concepts. Optimisation, when applied to a
variety of different types of optimization algorithms, necessitates
determining the best consequences of the specific predetermined characteristic
in a particular circumstance. In this work, we will be working on one similar
problem - The Maximal Stretch Problem with computational rigour. Beginning
with the Problem Statement itself, we will be developing numerous step - by -
step algorithms to solve the problem, and will finally pose a comparison
between them on the basis of their Computational Complexity. The article
entails around the Brute Force Solution, A Recursive Approach to deal with the
problem, and finally a Dynamically Programmed Approach for the same.

###### Keywords:

Dynamic Programming Matrices Recursion Operation Research

##  1 Introduction

Determining the contiguous subspace [1] with the biggest sum,
$\sum_{i=\alpha}^{\beta}\mathcal{A}\left[i\right]\forall\mathcal{A}[i]\in\mathbb{R}$
together within specified linear array [2] $\mathcal{A}[1..n]$ of data, is
defined as the ”Maximum Summation SubArray Problem” [3] in Computing Science.
This problem is also referred to as the ”Maximal Segmentation Sum Problem”.
Ulf Grenander presented the maximal subarray problem [4] in 1977 as a
streamlined framework for the expectation - maximization estimate of features
in digitised images. In this article, we intend to provide an overview, and
indeed outline a comprehensive evaluation, of the multiple alternatives to
solving the problem - ”The Maximal Stretch.” The problem statement is as
follows.

Problem Statement: Given a binary square matrix, $\mathcal{A}$ with binary
entries, i.e,

$\displaystyle\mathcal{A}=\left[\begin{matrix}\alpha_{0,\
0}&\cdots&\alpha_{0,\ n-1}\\\ \vdots&\ddots&\vdots\\\ \alpha_{n-1,\
0}&\cdots&\alpha_{n-1,\ n-1}\\\ \end{matrix}\right]\ni\alpha_{i,\
j}=\left\\{0,\ 1\right\\}\ \ \forall\left(i,\ j\right)$

We will have to fetch a sub matrix

$\displaystyle\mathcal{B}=\left[\begin{matrix}\beta_{0,\ 0}&\cdots&\beta_{0,\
m-1}\\\ \vdots&\ddots&\vdots\\\ \beta_{m-1,\ 0}&\cdots&\beta_{m-1,\ m-1}\\\
\end{matrix}\right]\ni\beta_{i,\ j}=1\ \ \forall\left(i,\ j\right)$

and find such a value of $m^{2}$ such that
$\left\lfloor\frac{n}{m}\right\rfloor$ is minimized.

A sparse matrix [5], also known as a sparse array, is a matrix where the
majority of the entries are zero in quantitative simulation [6] and computer
sciences. The total number of non-zero representatives is usually equivalent
to the total number of the columns and rows, which is a common rule of thumb
to determine whether such a structure is sparse. Nevertheless, there’s
currently no technical definition of the considered necessary percentage of
zero-value modules. The matrix, on the other contrary, is considered to be
intense if the significant proportion of its modules are non-zero.

##  2 Naïve Approach

The Naive Approach [7] is the one, which one’s mind would spill out
instantaneously after apprehending the Problem Statement. Infact, for the
Maximal Stretch Problem, the Naïve Approach is mentioned in the Problem
Statement itself, that is, look out for all sub matrices and find out the one
having highest order with all affirmative entries. Generically, suppose, we
have a matrix $\mathcal{M}$ of order $m\times n$, and let us declare a
function $\varphi(m,\ n)$ which is ought to find out the number of sub -
matrices [8] possible for $\mathcal{M}$. Let us try to build some recursive
[9] stuff out of it,
Base Case

$\varphi(1,\ \lambda)=\varphi(\ \lambda,\ 1)=\sum_{i=1}^{\lambda}i$ (1)

Recursive Case
Taking into consideration, the Matrix, $\mathcal{M}$ of order $m\times n$,
there will be $\sum_{i=1}^{m}i$ sub - matrices of width 1. For each such
matrix, there will be $n+1$ sub - matrices. Hence, number of nascent sub -
matrices will be $\left(n+1\right)\sum_{i=1}^{m}i$. So, the recursive form
would be

$\varphi(m,\ n)=\varphi(m,\ n-1)+n\sum_{i=1}^{m}i$ (2)

The Closed form of this Recursion [10] comes out to be

$\displaystyle\varphi(m,\
n)=\left(\sum_{i=1}^{n}i\right)\times\left(\sum_{i=1}^{m}i\right)$

In our case, for the Maximal Stretch Problem, we have considered the Matrices
to be Square in nature, so, $n=m$. Hence, the closed form of this Recursion
[11] comes out to be

$\displaystyle\varphi(n,\
n)=\sum_{i=1}^{n}i^{3}=\frac{n^{2}\left(n+1\right)^{2}}{4}$

Hence, the Computational Complexity for this Naïve Approach would be of
Quartic [12] Order. The Algorithm corresponding to this Solution is mentioned
in the Algorithm 1.

Algorithm 1 Naïve Solution to the Maximal Stretch Problem

1:$\mathcal{M}_{n\times n}\ni\mathcal{M}_{\left(i,\ j\right)}=\left(0,\
1\right)\ \forall\ \left(i,\ j\right)<\left(n,\ n\right)$

2:$m^{2}$ $\exists\ {\mathcal{M}^{\prime}}_{m\times
m}\ni{\mathcal{M}^{\prime}}_{\left(i,\ j\right)}=1\ \forall\ \left(i,\
j\right)<\left(m,m\right)$

3:function Naïve Solution($\mathcal{M}_{n\times n}$)

4: $m\leftarrow 0$ $\triangleright$ $m$ stores the Maximal Length

5: for ${\mathcal{M}^{\prime}}$ in $\mathcal{M}$ do

6: if ${\mathcal{M}^{\prime}}_{\left(i,\ j\right)}=0$ then

7: continue

8: end if

9: $m\leftarrow max(m,$ ORDER$({\mathcal{M}^{\prime}}))$

10: end for

11:end function

##  3 Recursive Approach

Recursion is a mathematical problem-solving technique used in computing
science in which the result is dependent on resolutions to local solutions of
the exact same problem. To confront those very recurring issues, recursion
employs practises that replicate themselves from within their own framework.
Recursion is indeed a fundamental premise in computing science, and it can be
used to alleviate a wide range of problems. Using a recursive approach, we
will make an effort to achieve the consequence. The Methodology we will use is
still quite simple.

  1. 1.

Iterate over all elements of the matrix $\mathcal{M}$.

  2. 2.

The recurrence subjecting to the problem can be declared as

$\psi\left(i,\ j\right)=1+min\left(\psi\left(i^{+},\ j\right),\psi\left(i,\
j^{+}\right),\psi\left(i^{+},\ j^{+}\right)\right)$ (3)

where, $i^{+}=i+1$ and $j^{+}=j+1$ with a base case of

$\psi\left(i,\ j\right)=0$ (4)

if ${\mathcal{M}}_{\left(i,\ j\right)}=0$

  3. 3.

The maximum value [13] of $\psi\left(i,\ j\right)$ will give the value of $m$
for which $\left\lfloor\frac{n}{m}\right\rfloor$ is maximized.

The Algorithm corresponding to this Solution is mentioned in the Algorithm 2.

Algorithm 2 Recursive Solution

1:$\mathcal{M}_{n\times n}\ni\mathcal{M}_{\left(i,\ j\right)}=\left(0,\
1\right)\ \forall\ \left(i,\ j\right)<\left(n,\ n\right)$

2:$m^{2}$ $\exists\ {\mathcal{M}^{\prime}}_{m\times
m}\ni{\mathcal{M}^{\prime}}_{\left(i,\ j\right)}=1\ \forall\ \left(i,\
j\right)<\left(m,m\right)$

3:function $\psi\left(i,\ j\right)$

4: if ${\mathcal{M}}_{\left(i,\ j\right)}=0$ or $\left(i,\ j\right)$ out of
Range then

5: $\psi\left(i,\ j\right)=0$

6: else

7: $\psi\left(i,\ j\right)=1+min\left(\psi\left(i+1,\ j\right),\psi\left(i,\
j+1\right),\psi\left(i+1,\ j+1\right)\right)$

8: end if

9:end function

10:function Recursive Solution($\mathcal{M}_{n\times n}$)

11: $m\leftarrow 0$ $\triangleright$ $m$ stores the Maximal Length

12: for $i=0$ to $n$ do

13: for $j=0$ to $n$ do

14: $m\leftarrow max(m,\psi\left(i,\ j\right))$

15: end for

16: end for

17:end function

The Computational Complexity of this Recursive Solution is of the order
$n^{2}\times\mathcal{T}_{\psi\left(i,\ j\right)}$. It is quite obvious that,
$\mathcal{T}_{\psi\left(i,\ j\right)}=3^{n+n}$. since in each step, 3
computations are being performed. So, on a whole, the Computational Complexity
of the problem is of the order $n^{2}3^{2n}$.

##  4 Dynamic Programming

The significant proportion of languages used for computer programming endorse
recursion by allowing a methodology to enact selves from within its own
framework. A component that is called recurrently from the inside of itself
may cause the request heap to develop to the dimensions of the system’s total
dimensions of all calls implicated. This means that recursion is typically
less effective for challenges that can be solved quickly through iteration
[14], and that using objective functions like dynamic programming [15] is
essential for solving big problems. In this approach, we will make use of
Dynamic Programming. The Algorithm, that will be followed follows as

  1. 1.

We will create a 2 - Dimensional Bottom to Top look up table,
$\mathcal{M}^{\prime}$ and initialize it with zeroes.

  2. 2.

Iterate over the entries of the matrix $\mathcal{M}$

    1. (a)

If $\mathcal{M}_{\left(i,\ j\right)}=1$, ${\mathcal{M}^{\prime}}_{\left(i,\
j\right)}=min({\mathcal{M}^{\prime}}_{\left(i-1,\
j\right)},{\mathcal{M}^{\prime}}_{\left(i,\ j-1\right)},\
{\mathcal{M}^{\prime}}_{\left(i-1,\ j-1\right)})+1\ $.

    2. (b)

Else ${\mathcal{M}^{\prime}}_{\left(i,\ j\right)}=0$.

  3. 3.

Return the maximum value of ${\mathcal{M}^{\prime}}_{\left(i,\ j\right)}$.

The Algorithm corresponding to this Solution is mentioned in the Algorithm 3.

Algorithm 3 DP Solution

1:$\mathcal{M}_{n\times n}\ni\mathcal{M}_{\left(i,\ j\right)}=\left(0,\
1\right)\ \forall\ \left(i,\ j\right)<\left(n,\ n\right)$

2:$m^{2}$ $\exists\ {\mathcal{M}^{\prime}}_{m\times
m}\ni{\mathcal{M}^{\prime}}_{\left(i,\ j\right)}=1\ \forall\ \left(i,\
j\right)<\left(m,m\right)$

3:function DP Solution($\mathcal{M}_{n\times n}$)

4: ${\mathcal{M}^{\prime}}_{(n+1)\times(n+1)}\leftarrow 0$

5: $m\leftarrow 0$ $\triangleright$ $m$ stores the Maximal Length

6: for $i=0$ to $n$ do

7: for $j=0$ to $n$ do

8: if ${\mathcal{M}}_{\left(i,\ j\right)}=0$ then

9: ${\mathcal{M}^{\prime}}_{\left(i,\ j\right)}=0$

10: else

11: ${\mathcal{M}^{\prime}}_{\left(i,\
j\right)}=min({\mathcal{M}^{\prime}}_{\left(i-1,\
j\right)},{\mathcal{M}^{\prime}}_{\left(i,\ j-1\right)},\
{\mathcal{M}^{\prime}}_{\left(i-1,\ j-1\right)})+1\ $

12: end if

13: $m\leftarrow max(m,{\mathcal{M}^{\prime}}_{\left(i,\ j\right)})$

14: end for

15: end for

16:end function

The Computational Complexity for this DP Solution is of the Quadratic Order.

##  5 Conclusion

To Conclude our work, The Maximal Stretch Problem can be solved in 3 ways

  1. 1.

By looking up all possible Sub matrices,

$\displaystyle\mathcal{B}=\left[\begin{matrix}\beta_{0,\ 0}&\cdots&\beta_{0,\
m-1}\\\ \vdots&\ddots&\vdots\\\ \beta_{m-1,\ 0}&\cdots&\beta_{m-1,\ m-1}\\\
\end{matrix}\right]\ni\beta_{i,\ j}=1\ \ \forall\left(i,\ j\right)$

that are possible for a given matrix,

$\displaystyle\mathcal{A}=\left[\begin{matrix}\alpha_{0,\
0}&\cdots&\alpha_{0,\ n-1}\\\ \vdots&\ddots&\vdots\\\ \alpha_{n-1,\
0}&\cdots&\alpha_{n-1,\ n-1}\\\ \end{matrix}\right]\ni\alpha_{i,\
j}=\left\\{0,\ 1\right\\}\ \ \forall\left(i,\ j\right)$

Now, this approach will compute the result in Quartic Order, $n^{4}$.

  2. 2.

By Recurring though all possible indices of the matrix, for the relation

$\displaystyle\psi\left(i,\
j\right)=\left\\{\begin{matrix}1+min\left(\psi\left(i^{+},\
j\right),\psi\left(i,\ j^{+}\right),\psi\left(i^{+},\ j^{+}\right)\right)\\\
0\\\ \end{matrix}\right.$

This will compute the result in a Hyper tonic order of $n^{2}3^{2n}$.

  3. 3.

By Preparing a Look Up table to implement the recurrence mentioned above. This
will compute the result in Quadratic Time, $n^{2}$.

Figure 1: Comparative Plot between the 3 Techniques for solving the Maximal
Stretch Problem. The computational time is taken on the Y - axes, and the
Cardinality of the Dataset subjected to the problem is taken on the X - axes.

It is quite observable from the Comparative Plot, that the Computational
Algorithm of the problem subjective to Dynamic Programming turns out to be the
best.

## References

  * [1] Gallier, J.: Basics of euclidean geometry. Texts in Applied Mathematics. 177–212 (2011).
  * [2] Garcia, R., Lumsdaine, A.: MultiArray: A C++ library for generic programming with arrays. Software: Practice and Experience. 35, 2, 159–188 (2005).
  * [3] Brodal, G.S., Jørgensen, A.G.: A linear time algorithm for the K maximal sums problem. Mathematical Foundations of Computer Science 2007. 442–453.
  * [4] Bentley, J.: Programming pearls. Communications of the ACM. 27, 9, 865–873 (1984).
  * [5] Yan, D. et al.: An efficient sparse-dense matrix multiplication on a multicore system. 2017 IEEE 17th International Conference on Communication Technology (ICCT). (2017).
  * [6] Filelis-Papadopoulos, C.K. et al.: Towards simulation and optimization of cache placement on large virtual content distribution networks. Journal of Computational Science. 39, 101052 (2020).
  * [7] Appel, K. et al.: Every planar map is four colorable. part II: Reducibility. Illinois Journal of Mathematics. 21, 3, (1977).
  * [8] Grcar, J.F.: John von Neumann’s analysis of gaussian elimination and the origins of modern numerical analysis. SIAM Review. 53, 4, 607–682 (2011).
  * [9] Dijkstra, E.W.: Recursive programming. Numerische Mathematik. 2, 1, 312–318 (1960).
  * [10] Andrew Nevins et al.: Evidence and argumentation: A reply to Everett (2009). Language. 85, 3, 671–681 (2009).
  * [11] Pinker, S., Jackendoff, R.: The faculty of language: What’s special about it? Cognition. 95, 2, 201–236 (2005).
  * [12] Chávez-Pichardo, M. et al.: A complete review of the general quartic equation with real coefficients and multiple roots. Mathematics. 10, 14, 2377 (2022).
  * [13] Barfuss, W., Meylahn, J.M.: Intrinsic fluctuations of reinforcement learning promote cooperation. Scientific Reports. 13, 1, (2023).
  * [14] Khan, M.A. et al.: A new implicit high-order iterative scheme for the numerical simulation of the two-dimensional time fractional cable equation. Scientific Reports. 13, 1, (2023).
  * [15] Eddy, S.R.: What is dynamic programming? Nature Biotechnology. 22, 7, 909–910 (2004).


# Performance-Weighed Policy Sampling for Meta-Reinforcement Learning

Ibrahim Ahmed, Marcos Quiñones-Grueiro, Gautam Biswas
Vanderbilt University
{ibrahim.ahmed, marcos.quinones<EMAIL_ADDRESS>
###### Abstract

This paper discusses an Enhanced Model-Agnostic Meta-Learning (E-MAML)
algorithm that generates fast convergence of the policy function from a small
number of training examples when applied to new learning tasks. Built on top
of Model-Agnostic Meta-Learning (MAML), E-MAML maintains a set of policy
parameters learned in the environment for previous tasks. We apply E-MAML to
developing reinforcement learning (RL)-based online fault tolerant control
schemes for dynamic systems. The enhancement is applied when a new fault
occurs, to re-initialize the parameters of a new RL policy that achieves
faster adaption with a small number of samples of system behavior with the new
fault. This replaces the random task sampling step in MAML. Instead, it
exploits the extant previously generated experiences of the controller. The
enhancement is sampled to maximally span the parameter space to facilitate
adaption to the new fault. We demonstrate the performance of our approach
combining E-MAML with proximal policy optimization (PPO) on the well-known
cart pole example, and then on the fuel transfer system of an aircraft.

##  1 Introduction

No physical system operating in the real world is immune to degradation,
changing environments, and faults. These situations can occur during
operation, and it is important for the system to respond to these changes in a
way that it continues to operate, be it in a degraded manner. This ensures
safety and cost-effectiveness by reducing system down-time. Fault-tolerant
control (FTC) [5] seeks to keep a faulty system operating within acceptable
margins of sub-optimal performance. This relaxes the constraints on the
designers to make a system completely fail-safe and allows for a trade-off
between design and operating costs.

Data-driven approaches to FTC [14, 12] exploit the preponderance of data
collected from system operations. They generate models that avoid the need for
time-consuming and accurate physics-based simulations of system dynamics to
analyze and respond to different situations that may occur in the system.
However, such methods depend on the data to span the breadth of operating
conditions, and the model has to contain sufficient detail to capture multiple
operating modes and faulty situations. This represents another compromise
between design and operating costs.

In many cases, systems are complex, the number of possible faults are large,
and faults that have not been seen before can occur during operations.
Therefore, there is no available system operational data to model such
behaviors, and data-driven approaches cannot learn a sufficiently optimal
control policy to address such behaviors. Reinforcement learning (RL) presents
a semi-supervised approach by forfeiting the dependence on labeled ground
truth, and instead relying on accumulated feedback (i.e., experience gained)
from a sequence of actions to converge to a globally optimal policy over time.
This ability to learn during operations alleviates design time effort and
costs. Deep RL methods use complex, nonlinear approximations of the value
function to overcome the computational intractability of the problem [6, 3].
However, the dependence on data to learn such approximations limits how fast
and how accurately a RL-based controller can adjust to faults.

In our past work ([1]), we have developed data-driven models to supplement
experience with the real environment when known and unknown faults occur in a
system. In this work, we employ meta-RL for faster adaption of the RL policy
parameters to collected data samples [19]. Our approach is not dependent on
the time-consuming step of learning a data-driven model first. Instead, it
uses introspection to evaluate its prior experiences under faults to
initialize parameters closer to an optimum. Our approach builds upon the
popular MAML algorithm [10] by foregoing the need to randomly sample different
tasks for the initialization.

The rest of this paper is organized as follows. The next section provides a
background on meta-RL approaches, especially those that have been developed
for Model Agnostic Meta Learning (MAML). Following that, section 3 discusses
RL and meta-learning concepts for this work. Section 4 describes our approach,
and section 5 evaluates it on a test example.

##  2 Background

One way meta-reinforcement learning differs from basic reinforcement learning
approaches in that the agent must learn to solve the task variability problem.
While the overarching goal of an agent may remain the same, e.g., continue to
fly the UAV or drive the car to its destination, task variability occurs
because the environment dynamics (i.e., the MDP model) changes, and,
therefore, the control policy employed by the agent does not produce the
expected results. This can happen because of changes, such as faults in an
autonomous vehicle, or because the environment in which the vehicle operates
(the terrain or weather conditions) changes significantly. Therefore, the
agent has to adapt its control policy to maintain satisfactory performance
towards achieving its goals.

Recent work has proposed efficient meta-gradient update rules to solve the
meta-RL problem. For example, the MAML algorithm learns a good model
initialization so that a new task is learned with small amounts of new
experiences and a few gradient steps [10]. Typically, an agent is trained with
MAML by interacting with a distribution of tasks. The idea behind MAML is to
find a policy that achieves an average performance across the task set. This
is accomplished by sampling experiences from the different tasks and using
them to compute a meta-gradient to update the policy. MAML generates
satisfactory results as long as the set of tasks come from the same known
distribution.

Computing sufficiently accurate low variance gradient estimates remains a
significant challenge for MAML-like approaches. [13] (Liu2019) propose TMAML
to improve the quality of gradient estimation by reducing variance without
introducing bias. TMAML adds control variates into gradient estimation via
automatic differentiation. Other approaches for improving gradient estimation
in MAML include Reptile [16] and FO-MAML [4]. Some approaches solve the meta-
RL problem by training a model that directly updates the agent hyper-
parameters [9], but these methods can lead to non-converging behavior, making
the training process very labor intensive. Others find internal
representations of the environment that augment the agent’s state space to
capture task variability [17], but these methods require careful tuning to
achieve successful results.

In all of the meta-RL approaches described above, the agent “learns to learn”
by exposure to a multitude of environments in offline settings. Therefore,
these methods apply when the changes in the environments can be generated
during training as opposed to online operations. Therefore, their scope is
typically limited to a small subset of task adaptations. This does not include
scenarios where the system dynamics or the environment may change in unknown
ways as discussed above. Therefore, learning to learn efficiently to promote
rapid adaptation to new tasks remains a challenging problem. More recently,
online meta-learning algorithms have been proposed that include model-free and
model-based RL approaches. Some of these approaches combine model-based RL and
Model Predictive Control for online adaptation [15]. In other work, [11]
(Finn2019) has introduced the follow the meta leader (FTML) algorithm as an
extension of MAML for online meta-learning. In their approach, tasks are
revealed one after the other, and the goal of FTML is to minimize a notion of
regret defined as the difference between the learner’s loss and the best
performance achievable by some family of methods. [21] (Zhou2020) propose an
online meta-critic that is (meta)-trained to improve the learning process
rather than merely estimating the action-value function.

Our model-free approach optimizes policy parameters to quickly adapt to novel
tasks. We propose a meta-update rule that exploits the knowledge accumulated
from previous tasks and promotes rapid learning of new tasks in online
settings.

##  3 E-MAML: Preliminaries

In our work, we adopt Reinforcement Learning (RL) as a semi-supervised policy
learning approach for learning and updating an “optimal” dynamic system
controller during online operations. The goal of the RL controller is to
maximize a total discounted cumulative reward, $J_{\pi}(x,u)$, where $x$
represents the state of the environment and $u$ represents the action taken by
the controller operating under a policy $\pi$. Policy gradient algorithms [20]
parameterize $\pi$, i.e., $\pi_{\theta}$, where the parameters, $\theta$ are
the weights of a model such as a neural network that represents the policy.
During training, they directly learn $\pi_{\theta}$ by implicitly optimizing
for a value function $V$ using gradient ascent on the gain function
$G\leftarrow\mathbb{E}[J_{\pi}(x,u)]$. Gradient ascent produces iterative
updates to $\theta$, whose size is determined by a learning rate,
$\alpha\in[0,1]$.

Parameter updates at each iteration are dependent rewards computed with the
latest policy. This approach, called on-policy RL, is sample inefficient
because new experiences need to be obtained at each iteration. A way to
overcome this is by applying importance sampling to the gain function. By
modeling the policy as a stochastic function over actions, $\pi_{\theta}(u\mid
x)$, the gain function can reuse the same batch to evaluate new iterations of
$\pi_{\theta}$. Large gradient updates may cause the next iteration of
$\pi_{\theta}$ to overshoot the optimum, causing the learning process to
diverge. Proximal Policy Optimization (PPO) [18] clips the size of gradient
updates by restricting the importance ratio between iterations. Thus, a policy
does not drastically change between updates. We use PPO in this work to learn
a new control policy under fault conditions.

###  3.1 Model-Agnostic Meta-Learning

As discussed, MAML [10] speeds up model learning through gradient updates. It
does so by running an inner introspective loop within each iteration of the
gradient update to the model’s parameters in the outer loop. In the inner
loop, variants of the process are sampled as $p^{i}\sim P$, where $P$
represents a family of probability distributions that characterize the
plausible variability in the process dynamics. The model parameters
$\theta_{k}$ at step $k$ are then optimized by training for several
interactions on each $p^{i}$ using gradient ascent to yield $\theta^{i}$. At
the end of the inner loop, gains $G^{i}$ on sets of test interactions are
computed. In the outer loop, the update to $\theta_{k}$, $\Delta\theta_{k}$,
is a weighed aggregate of the test gradients from the inner loop $\partial
G^{i}/\partial\theta_{k}$. Therefore, the training step for the outer loop is
based on the test error of the inner loop. MAML standard method is presented
in Algorithm 1. Figure 1 illustrates how MAML initializes parameters for
faster learning.

The update step in MAML requires second-order gradient computations, which
have quadratic complexity in the size of the parameter vector. Some approaches
([16], [10]) simplify the computation by assuming a linear relationship
between the updated and original parameters,
$\partial\theta^{i}/\partial\theta_{k}\approx 1$. A tabulation of such
approximations is provided in Table 1.

Algorithm | $\Delta\theta^{\prime}_{k_{out}}$
---|---
MAML | $\sum_{i}\frac{\partial G^{i}}{\partial\theta^{i}_{K_{in}}}\times\frac{\partial\theta^{i}_{K_{in}}}{\theta^{\prime}_{k_{out}}}$
FOMAML | $\sum_{i}\frac{\partial G^{i}}{\partial\theta^{i}_{K_{in}}}$
Reptile | $\sum_{i}\left(\theta^{i}_{K_{in}}-\theta^{\prime}_{k_{out}}\right)$
Table 1: Formulation of the update to parameters by variants of MAML. Figure
1: The meta-update initializes policy parameters closer to an optimum, after
which RL converges faster to a solution. The meta-update depends on the
aggregate gradients of policies in the complement. The gradients are
calculated from samples of the buffer of recent experiences. The meta-update
step from $\theta_{k}$ to $\theta^{\prime}$ is described in algorithm 2.

##  4 Enhanced Model-Free Meta-Learning

###  4.1 Problem Formulation

The problem posed to the controller is this: adapt to a new process
$p^{\prime}$ representing a fault on the existing process $p$. The faulty
process may not belong to the known population, i.e., $p^{\prime}\notin P$.
Adaption implies that the controller has to quickly recover performance. In
this work, we assume adaption is initiated by fault detection, i.e., we know a
fault has occurred but we may not know the exact nature of the fault. We also
assume the fault is not catastrophic, therefore, the system can continue to
operate in a degraded manner. As a result of the fault, the MDP representing
the system dynamics is changed, but the controller continues to interact with,
and records experiences (states, actions, and rewards) in its memory,
$\mathcal{M}$. Once a small but sufficient set of interactions $t_{update}$
under the fault conditions have been buffered, the controller attempts to
learn a new policy from its memory. Once learning is complete, the controller
consolidates the newly learned policy with its prior policies. Thus, when a
new fault occurs, it can exploit its past experiences and adapt faster.

The learning phase consists of two stages: (1) the meta-update, followed by
(2) iterations of a gradient based learning algorithm to converge to the
“optimal” policy. During the meta-update, the controller uses its consolidated
prior experience to initialize new policy parameters. After that, the
parameters are iteratively updated by the RL algorithm through interactions
with the actual system. Consolidation of knowledge happens by maintaining a
set of prior policies $\mathcal{C}=\\{\theta\mid\pi_{\theta}\\}$ that have
been trained under different processes. The set of policies is periodically
pruned to ensure that they capture diverse behavior but it is small enough to
evaluate within the time constraints of learning a new policy when a fault
occurs.

Input: parameters $\theta_{k}$, MDPs $P$, learning rates
$\alpha_{in},\alpha_{out}$, iterations $K_{in},K_{out}$

1 begin

2 Set $\theta^{\prime}_{1}\leftarrow\theta_{k}$;

3 for  _$k_{out}=1$ to $K_{out}$_ do

4 Sample MDPs $p_{i}\sim P$;

5 for  _all $p^{i}$_ do

6 Set $\theta^{i}_{1}\leftarrow\theta$;

7 for  _$k_{in}=1$ to $K_{in}$_ do

8 Sample training trajectories $\mathcal{M}_{i}$ from $p^{i}$;

9 Calculate gain $G$ from $\mathcal{M}_{i}$;

10 Update
$\theta^{i}_{k_{in}+1}\leftarrow\theta^{i}_{k_{in}}+\alpha_{in}\cdot\nabla_{\theta^{i}_{k_{in}}}G$;

11

12 Sample test trajectories from $p_{i}$;

13 Calculate test gain $G^{i}$ on sample;

14 Update
$\theta^{\prime}_{k_{out}+1}\leftarrow\theta^{\prime}_{k_{out}}+\alpha_{out}\cdot\Delta\theta^{\prime}_{k_{out}}$;

15

16 return _$\theta^{\prime}\leftarrow\theta^{\prime}_{K_{out}}$_

17

Algorithm 1 Model-Agnostic Meta-Learning (MAML)

###  4.2 Performance Weighted Policy meta-update

In the meta-update step after a fault, the controller using a policy
$\theta_{k}$ evaluates the memory of experiences under the new process to re-
initialize its policy parameters closer to an optimum, $\theta_{k+1}$. Our
approach mirrors MAML’s nested loop structure for updating the controller’s
policy parameters. E-MAML diverges in its formulation of the nested loops. We
forego sampling intermediate parameters anew, and instead exploit the history
of the controller’s experience. In other words, MAML evaluates multiple
processes $p^{i}$ on a single set of parameters $\theta_{k}$, and we propose
to evaluate a single process $p^{\prime}$ on multiple sets of parameters
$\theta^{i}\in\mathcal{C}$.

Since the parameters from previous experiences $\theta^{i}\in\mathcal{C}$ are
not derived from the nominal population defining the process, the parameter
space can be more expansive as illustrated in Figure 2. It should be noted
that the relationship between parameters derived from earlier faults and the
current parameters may be highly non-linear, therefore, the assumption used to
discard second-order gradients, namely
$\partial\theta^{i}/\partial\theta_{k}\approx 1$, may not hold.

In MAML, the sampling of processes assumes the next process to be adapted to
will be from the same population, but E-MAML relaxes that assumption. The
gradient updates for each of $\theta^{i}$ in MAML point to the local optimum
for $p^{i}$. However, for a faulty process $p^{\prime}$ not sampled from $P$,
such gradients may point in a sub-optimal direction. This is true for our
approach if the relationship (gradients) of
$\partial\theta^{i}/\partial\theta_{k}$ is simplified, as illustrated in
Figure 3. The parameters in $\mathcal{C}$, representing different faults, may
cause divergent behaviors for the current policy. For example, control actions
considered optimal under one fault may be counter-productive under another.
Hence, gradients derived from some parameters in the complement may be sub-
optimal.

To address this, we performance-weigh parameters in $\mathcal{C}$ based on
$\mathcal{M}$. Only parameters that can be expected to give favorable
gradients are selected for the meta-update step. We utilize the fact that the
control policy is stochastic, so there is a probability associated with the
actions taken. Therefore, we calculate the expected cumulative reward
$\mathbb{E}(J^{\mathcal{M}}_{\pi_{\theta^{i}}})$ for the states and actions in
$\mathcal{M}$ under policy parameters in $\mathcal{C}$:

$\displaystyle\mathbb{E}(J^{\mathcal{M}}_{\pi_{\theta^{i}}})$
$\displaystyle=\sum_{t=0}^{\mid\mathcal{M}\mid}\left(\pi_{\theta^{i}}(u_{t}\mid
s_{t})\cdot\sum_{t^{\prime}=t}^{\mid\mathcal{M}\mid}(\gamma^{t^{\prime}-t}r_{t}).\right)$
(1)

Favorable policies highly weigh actions in $\mathcal{M}$ that yielded greater
cumulative rewards. While the derivation in Equation 1 is not an exact
calculation of the expected value since it does not sum over all possible
actions for each state, it does serve as a metric to set up an ordinal
relationship between parameters in $\mathcal{C}$. The controller selects the
most favorable policies and uses them for updating $\theta_{k}$.

In the resulting algorithm, prior to the meta-update, a memory $\mathcal{M}$
of interactions under the new process $p^{\prime}$ is buffered. The meta-
update step assumes a prior set $\mathcal{C}=\\{\theta\mid\pi_{\theta}\\}$ of
prior policies trained on the system for different processes. This foregoes
the need of sampling an altogether new set of processes for the meta-update.
The top most favorable policies, ranked by their expected performance on
$\mathcal{M}$ are selected. For each iteration of the meta-update: (1) the
selected parameters are optionally fine-tuned for a few steps $K_{in}$ to
yield an updated set of meta-parameters; and (2) $\mathcal{M}$ is evaluated on
the policies in the prior set to calculate the update step $\Delta\theta_{k}$
for $\theta_{k}$. After a number of iterations of updates to $\theta_{k}$, the
resulting parameters $\theta_{k+1}$ are used as initialization for learning
the controller for the new process $p^{\prime}$.

Figure 2: A visual comparison between MAML and our approach. MAML samples
multiple parameters in a vicinity, each with their own optimum, and aggregates
their evaluations for the update. e-MAML re-uses past parameters from
different populations but evaluates them for a single optimum. The arrows
represent gradients of the gain with respect to the parameters. Figure 3:
Pitfalls of MAML-based approaches. In MAML, when the new process is not from
the training distribution $P$. In E-MAML, when parameters in complement
$\theta^{i}$ are spread out in parameter space. In both cases, updates to
control policy, $\theta_{k}$, are in a sub-optimal direction. The curves
represent contours of the gain function and the arrows represent gradients. An
‘*’ marks the optimal parameter.

1

Input: parameters $\theta_{k}$, memory $\mathcal{M}$, learning rates
$\alpha_{in},\alpha_{out}$, iterations $K_{in},K_{out}$, policy complement
$\mathcal{C}=\\{\varnothing\\}$, rank $r$

2

3begin

4 Sample trajectories from $\mathcal{M}$;

5 Set meta-updated params $\theta^{\prime}_{1}\leftarrow\theta$;

6 Sort $\theta\in\mathcal{C}$ by $\mathbb{E}(J^{\mathcal{M}}_{\pi_{\theta}})$;

7 Set $\mathcal{C}^{\prime}\leftarrow$ top $r$ $\theta\in\mathcal{C}$;

8 for  _$k_{out}=1$ to $K_{out}$_ do

9 for  _$\theta^{i}$ in $\mathcal{C}^{\prime}$_ do

10 for  _$k_{in}=1$ to $K_{in}$_ do

11 Calculate training gain $G$ on $\mathcal{M}$;

12 Update
$\theta^{i}_{k_{in}+1}\leftarrow\theta^{i}_{k_{in}}+\alpha_{in}\cdot\nabla_{\theta^{i}_{k_{in}}}G$;

13

14 Calculate test gain $G^{i}$ on $\mathcal{M}$;

15 Update
$\theta^{\prime}_{k_{out}+1}\leftarrow\theta^{\prime}_{k_{out}}+\alpha_{out}\cdot\Delta\theta^{\prime}_{k_{out}}$;

16

17 return _$\theta^{\prime}\leftarrow\theta^{\prime}_{K_{out}}$_

18

Algorithm 2 Enhanced meta-RL

###  4.3 Population of Previous Fault Policies

The set of saved policies should maximally span the parameter space of
possible faults that may occur in the system. Policies should be different
enough so that the meta-update has a greater likelihood of adapting to novel
faults. The difference between policies is evaluated on the memory of
interactions collected by the controller. Each policy in $\mathcal{C}$
generates a probability of actions taken in $\mathcal{M}$. KL-divergence is a
measure of difference between probabilities. A related metric is the Jensen-
Shannon (JS) divergence [8], which satisfies the triangle inequality and is
used as the distance metric here. The total divergence of each policy from the
rest of the complement becomes a score of a policy’s uniqueness. Given a
complement size $s\leftarrow|\mathcal{C}|$, the $s$ most unique policies are
returned as members of $\mathcal{C}$.

Input: policy complement $\mathcal{C}$, complement size $s$, memory
$\mathcal{M}$

1 begin

2 Initialize divergence matrix $D=[0]^{|C|\times|C|}$;

3 for  _$\theta_{1},\theta_{2}\text{ in Permute}(\mathcal{C})$_ do

4 Action probabilities
$p_{1},p_{2}=\pi_{\theta_{1}}(\mathcal{M}),\pi_{\theta_{2}}(\mathcal{M})$;

5 Set $p_{m}\leftarrow 0.5\cdot(p_{1}+p_{2})$;

6 JS-Divergence $d=0.5\cdot(\Sigma p_{1}\cdot\log(p_{2}/p_{m})+\Sigma
p_{1}\cdot\log(p_{2}/p_{m}))$;

7 $D[\theta_{1},\theta_{2}]=d$;

8 Sum each row of $D$ for total divergence $D_{T}^{|C|\times 1}$;

9 Most divergent parameters
$\mathcal{C}\leftarrow\text{Sort}(\mathcal{C})\text{ by }D_{T}$;

10 return _First $s$ parameters from $\mathcal{C}$_

11

12

Algorithm 3 Populating the stored policy set $\mathcal{C}$

##  5 Experiments

(a) Cart-pole

(b) Fuel tanks

Figure 4:

We evaluate our approach on two processes (figure 4). The first, discussed in
greater detail, is the popular OpenAI Gym [7] implementation of the cart-pole
environment. The environment constitutes of moving cart balancing a pole. The
environment starts with the pole at an angle. The objective is to keep the
pole upright as long as possible by moving the cart left or right. The reward
is the number of steps the pole is kept upright. The environment is
parameterized by the cart and pole masses, the pole length, and the force
magnitude on the cart ($m_{c},m_{p},l,F$). For the cart-pole, a fault
increased all masses, lengths, and force magnitudes, and reversed force
direction.

The second is a 6-tank fuel transfer system on the wings of an aircraft. The
objective is to transfer fuel between tanks to keep fuel mass balanced about
the longitudinal axis, to keep fuel mass concentrated at the extremities, and
to conserve fuel mass against leaks. This is a hybrid system. The state space
constitutes of fuel levels and the action space is the status of valves on
each tank. The environment is parametrized by the tank geometry, valve
resistances, and engine fuel consumption rates. For the fuel tanks, a fault
increased fuel consumption asymmetrically and disabled a valve.

For the following experiments, a complement of four policies was trained on
top of the controller trained on a nominal system, with each policy derived
from a fault. Figure 5 shows the training of policies in the complement. For
the cart-pole (5(a)) policies 2 & 3 are for different force polarities and
therefore take longer to regain performance. For the fuel tanks (5(b)), each
fault can limit the maximum achievable reward.

(a) Cart-pole

(b) Fuel tanks

Figure 5: Policies in $\mathcal{C}$ trained on faults.

###  5.1 On Performance-Weighed Sampling

The objective of performance-weighed policy sampling is to select parameters
which are expected to perform most favorably under the new process
$p^{\prime}$. Table 2 shows the results of the ranking operation as described
in Algorithm 2 and Equation 1. From the results, it is evident that the
ranking favors policies trained on faults where the force directions were
reversed. Furthermore, the top-ranked policy was trained on a fault where both
masses were increased as well. This ranking makes intuitive sense as well:
policy changes with slight changes in mass require changes in duration of
force application by degrees. However, a reversal in force direction
essentially calls for an inversion of the behavior altogether.

Figure 6 shows performance when the controller is more selective in sampling
parameters from $\mathcal{C}$. Higher selectivity lowers the chances of sub-
optimal contributions to $\Delta\theta_{k}$. In both cases, E-MAML outperforms
MAML, which samples processes from the nominal distribution only. For a cart-
pole, a good initial state can balance the pole forever, and rewards can tend
to infinity. A reward curve that ends early shows that there were fewer
episodes in a more successful run because the pole did not tip over and the
episode continued. In this case the benefits of sampling were less perceptible
but outperformed standard PPO and MAML-initialized learning.

(a) Cart-pole

(b) Fuel tanks

Figure 6: Performance of PPO on $p^{\prime}$ for 30000 steps after the fault and meta-update, with and without performance-weighed policy sampling (rank=$s$=4, rank=2). $m_{c}$ | $m_{p}$ | $l$ | $F$ | $\mathbb{E}(J_{\pi_{\theta^{i}}}^{\mathcal{M}})$ | Rank
---|---|---|---|---|---
1.5 | 0.125 | 0.75 | -12 | -60 | N/A
1 | 0.1 | 0.5 | 10 | -30 | 3
2 | 0.2 | 0.5 | 15 | -66 | 4
1 | 0.1 | 0.5 | -10 | 52 | 2
2 | 0.2 | 0.5 | -15 | 70 | 1
Table 2: The expected returns of the memory on the policy parameters in
$\mathcal{C}$. The first row is the faulty process $p^{\prime}$. The following
rows are processes for which policy parameters exist in $\mathcal{C}$.

###  5.2 On Maximally Parameter-Spanning Complement

The objective of a maximally parameter-spanning complement is to select policy
parameters that exhibit the most diverse behaviors. This is done so that there
is a higher probability that a favorable set of parameters is present during
performance-weighed sampling when a fault occurs. Table 3 shows the
divergences between 7 policies in $\mathcal{C}$ trained on various faults on
the cart-pole. Policies with the force direction reversed are the most
mutually divergent. This hints that the controller behavior is more sensitive
to changes in force magnitude and direction than it is to variations in masses
and lengths. However, the size of the complement, $s=4$, in our work is a
design time parameter. If $s\leq 3$, $\mathcal{C}$ would only have had
policies with reversed force directions.

Figure 7 shows the performance after a meta-update based on the 4 most
divergent and the 3 least divergent policies. For the cart-pole, having a
diverse set of behaviors gives an early advantage. For the fuel tanks, the
diversity in $\mathcal{C}$ does not discriminate. However e-MAML outperforms
the benchmark approaches.

$j$ | $m_{c}$ | $m_{p}$ | $l$ | $F$ | $\sum_{i}^{\mid\mathcal{C}\mid}\texttt{JS-Div}(\theta^{j},\theta^{i})$
---|---|---|---|---|---
1 | 1 | 0.1 | 0.5 | 10 | 2.667
2 | 1.5 | 0.1 | 0.5 | 10 | 2.278
3 | 2 | 0.2 | 0.5 | 15 | 2.284
4 | 2 | 0.15 | 0.5 | 15 | 2.362
5 | 1 | 0.1 | 0.5 | -10 | 2.883
6 | 1 | 0.1 | 0.5 | -12 | 2.503
7 | 2 | 0.2 | 0.5 | -15 | 2.686
Table 3: The divergences between policy parameters in $\mathcal{C}$ trained on
faults as tabulated. They were evaluated on a buffer of size 500 from the
nominal process $p$.

(a) Cart-pole

(b) Fuel tanks

Figure 7: Performance on 30000 steps on $p^{\prime}$. For $\Delta\theta_{k}$,
the FOMAML approximation was used.

###  5.3 On $\Delta\theta_{k}$ approximations

We proposed to use performance-weighed policy sampling to mitigate the
pitfalls associated with greater spread in parameter space and with out-of-
population processes for adaption (Figure 3). The former can also be addressed
by computing higher-order gradients $\partial\theta^{i}/\partial\theta_{k}$ as
is done in MAML. Figure 8 shows the performance comparison for different
$\Delta\theta_{k}$ approximation approaches with and without ranking. For the
cart-pole, when performance-weighed sampling is done, the spread in
performance when using accurate and approximated gradients is reduced (Figure
8(b)). Without ranking (Figure 8(b)), the spread is increased, and approximate
gradient approaches (FOMAML, Reptile) take a greater number of episodes to
balance the cart-pole system for longer time periods. This demonstrates that,
while performance-weighed policy sampling is not a perfect substitute for
accurate gradients, it can be a compromise between computational complexity
and performance.

For the fuel tanks, there is little perceptible difference between ranking.
However the two gradient-based approaches yield better results. The near-
identical performance of MAML and FOMAML approximations hints towards the
absence of higher order relationships between $\theta^{i}$ and $\theta_{k}$.
Similarly, the near identical performance regardless of ranking can mean that
the faults may not be very different in terms of control policy. Indeed the
minimal change in flow rates between tanks as resistances change can neuter
any drastic changes in control actions in valves. These peculiarities of
different processes present another meta-dimension for optimizing the
reinforcement learning process.

(a) Cart-pole: No ranking

(b) Cart-pole: rank=2

(c) Fuel tanks: No ranking

(d) Fuel tanks: rank=2

Figure 8: Comparison for different approximations for $\Delta\theta_{k}$ with
and without performance-weighed sampling. All simulations were run for 30000
steps.

##  6 Conclusions

Quick adaption to changing conditions is a tenet of fault-tolerant control.
RL-based control is weighed down by its reliance on data and stochastic,
iterative methods for deriving optimal control. Meta-learning seeks to
initialize these derivations such that iterations to a locally optimal policy
are fewer. We introduced E-MAML: a model-free meta-learning approach for
initializing controllers after a fault. E-MAML curates a complement of past
policies representing the system under different faults. The complement is
kept diverse to cover as wide a set of behaviors as possible. After a fault,
favorable policies are selected from the complement, evaluated on a buffer of
experiences with the new process, and used to update the controller
parameters.

We demonstrated that performance-weighed policy sampling and maximally
parameter-spanning algorithms make intuitive choices over policies.
Furthermore, we showed that a controller can improve when it is selective, but
searches over a diverse space. E-MAML, like MAML, is sensitive to the choice
of hyperparameters [2], and introduces a few of its own (library size, rank).
This approach merits further investigation into stability and convergence
guarantees which are necessary for safety and performance critical systems.

## Appendix

The code for this work can be found at
https://git.isis.vanderbilt.edu/ahmedi/airplanefaulttolerance/-/tree/aaai2020.

Parameter | Cart-pole | Fuel tanks
---|---|---
Optimizer | Adam | Adam
$\alpha$ | 0.002 | 0.002
$\beta$ | (0.9, 0.999) | (0.9, 0.999)
Epochs | 3 | 3
$t_{update}$ | 500 | 1000
Value net | 2x (32, tanh), 1) | 2x (64, tanh), 1)
Action net | 2x (32, tanh), 1, $\sigma$) | 2x (64, tanh), 6, $\sigma$)
$\gamma$ | 0.99 | 0.99
$\epsilon$ | 0.2 | 0.2
Table 4: Parameters used by the PPO algorithm, as documented in code. Parameter | Cart-pole | Fuel tanks
---|---|---
$|\mathcal{M}|$ | 2000 | 4000
$\alpha_{in}$ | 0.001 | 0.001
$\alpha_{out}$ | 0.002 | 0.001
$K_{in}$ | 0 | 3
$K_{out}$ | 5 | 3
$s$ | 4 | 4
Table 5: e-MAML parameters, unless otherwise specified.

This section further explains the difference in performances between the cart-
pole and fuel tanks processes with regards to sampling from the complement.
For the cart pole, figures 6(a) and 7(a) demonstrate that being selective over
a diverse set of policies produces better adaption to faults. However, for the
fuel tanks system, figures 6(b) and 7(b) show similar adaption for permissive
sampling and for homogeneous policies. A brief explanation of this discrepancy
was provided in section 5.3.

Figures 9 and 10 show how the system dynamics and learned policies are diverse
and homogeneous respectively in response to process faults for the two
processes. The similar dynamics are reflected in the smaller total divergence
measurements for the fuel tanks compared to the cart pole. Since the policies
in $\mathcal{C}$ for the fuel tanks are similar, the utility of being
selective over them is diminished when faced with a novel fault.

This supports our hypothesis on the value of a diverse complement of policies
and of the efficacy of algorithm 3 for discriminating over different polices
using bufferred experience.

Figure 9: The behaviors of policies trained on faulty processes as tabulated in Table 3. Two of the four state variables, cart position $X$ and pole tilt angle, are plotted. The other two variables are time-derivatives of the former. Initialized at the same state but with different faults, the policies exhibit different behaviors. $j$ | Resistance | Pumps | Engines | $\sum_{i}^{\mid\mathcal{C}\mid}\texttt{JS-Div}(\theta^{j},\theta^{i})$
---|---|---|---|---
1 | [100, 100, 100, 70, 80, 90] | [0.1, 0.1, 0.1, 0., 0.1, 0.1] | [0.05, 0.1] | 0.376
2 | [100, 100, 100, 70, 80, 90] | [0. , 0.1, 0.1, 0., 0.1, 0.1] | [0.05, 0.1] | 0.412
3 | [100, 100, 100, 150, 200, 100] | [0.1, 0.1, 0.1, 0.1, 0.1, 0.1] | [0.1, 0.05] | 0.376
4 | [100, 100, 100, 150, 200, 100] | [0.1, 0.1, 0.1, 0.1, 0. , 0. ] | [0.1, 0.05] | 0.383
5 | [90, 100, 100, 70, 80, 90] | [0.1, 0.1, 0., 0.1, 0.1, 0.1] | [0.05, 0.1] | 0.372
6 | [90, 100, 100, 70, 80, 90] | [0. , 0.1, 0., 0.1, 0.1, 0. ] | [0.05, 0.1] | 0.547
7 | [100, 75, 100, 100, 75, 100] | [0.1, 0. , 0.1, 0.1, 0.1, 0.1] | [0.05, 0.1] | 1.664
Table 6: The divergences between policy parameters in $\mathcal{C}$ for the
fuel tanks system. They were evaluated on a buffer of size 1000 from the
nominal process $p$. In the nominal case, Resistances=100, pumps=0.1, and
engines=0.1. The policies are less diverse than for the cart-pole process in
table 3. Figure 10: The behaviors of policies trained on faulty processes as
tabulated in table 6. Each row depicts the 6 fuel tank levels for a faulty
process. The shaded backgrounds indicate open and closed valves. It is evident
from this figure, and from the distance metric in table 6, that the complement
of policies in the fuel-tank system are much less diverse under faults
compared to the cart pole system. The policies are less diverse because the
process dynamics in response to faults are similar.

## References

  * [1] Ibrahim Ahmed, Marcos Quiñones-Grueiro and Gautam Biswas  “Fault-Tolerant Control of Degrading Systems with On-Policy Reinforcement Learning”  In _IFAC-PapersOnLine_ , 2020  IFAC
  * [2] Antreas Antoniou, Harrison Edwards and Amos Storkey  “How to train your MAML”  In _International Conference on Learning Representations_ , 2018
  * [3] Leemon Baird  “Residual algorithms: Reinforcement learning with function approximation”  In _Machine Learning Proceedings 1995_ Elsevier, 1995, pp. 30–37
  * [4] Abhijat Biswas and Shubham Agrawal  “First-order Meta-Learned Initialization for Faster Adaptation in Deep Reinforcement Learning”, 2018
  * [5] Mogens Blanke et al.  “Diagnosis and fault-tolerant control”  Springer, 2006
  * [6] Justin A Boyan and Andrew W Moore  “Generalization in reinforcement learning: Safely approximating the value function”  In _Advances in neural information processing systems_ , 1995, pp. 369–376
  * [7] Greg Brockman et al.  “OpenAI Gym”, 2016  eprint: arXiv:1606.01540
  * [8] Ido Dagan, Lillian Lee and Fernando Pereira  “Similarity-based methods for word sense disambiguation”  In _arXiv preprint cmp-lg/9708010_ , 1997
  * [9] Yan Duan et al.  “RL2: Fast reinforcement learning via slow reinforcement learning”, 2017, pp. 1–14  arXiv:arXiv:1611.02779v2
  * [10] Chelsea Finn, Pieter Abbeel and Sergey Levine  “Model-agnostic meta-learning for fast adaptation of deep networks”  In _Proceedings of the 34th International Conference on Machine Learning-Volume 70_ , 2017, pp. 1126–1135  JMLR. org
  * [11] Chelsea Finn, Aravind Rajeswaran, Sham Kakade and Sergey Levine  “Online Meta-Learning”, 2019
  * [12] WANG Hongm, CHAI Tian-You, DING Jin-Liang and Martin Brown  “Data driven fault diagnosis and fault tolerant control: some advances and possible new directions”  In _Acta Automatica Sinica_ 35.6 Elsevier, 2009, pp. 739–747
  * [13] Hao Liu, Richard Socher and Caiming Xiong  “Taming MAML : Efficient Unbiased Meta-Reinforcement Learning”, 2019
  * [14] John MacGregor and Ali Cinar  “Monitoring, fault diagnosis, fault-tolerant control and optimization: Data driven methods”  In _Computers & Chemical Engineering_ 47 Elsevier, 2012, pp. 111–120
  * [15] Anusha Nagabandi et al.  “Learning to adapt in dynamic, real-world environments through meta-reinforcement learning”, 2019, pp. 1–17  arXiv:arXiv:1803.11347v6
  * [16] Alex Nichol, Joshua Achiam and John Schulman  “On first-order meta-learning algorithms”  In _arXiv preprint arXiv:1803.02999_ , 2018
  * [17] Kate Rakelly et al.  “Efficient Off-Policy Meta-Reinforcement Learning via Probabilistic Context Variables”, 2019
  * [18] John Schulman et al.  “Proximal policy optimization algorithms”  In _arXiv preprint arXiv:1707.06347_ , 2017
  * [19] Nicolas Schweighofer and Kenji Doya  “Meta-learning in reinforcement learning”  In _Neural Networks_ 16.1 Elsevier, 2003, pp. 5–9
  * [20] Richard S Sutton, David A McAllester, Satinder P Singh and Yishay Mansour  “Policy gradient methods for reinforcement learning with function approximation”  In _Advances in neural information processing systems_ , 2000, pp. 1057–1063
  * [21] Wei Zhou et al.  “Online Meta-Critic Learning for Off-Policy Actor-Critic Methods”, 2020  arXiv:arXiv:2003.05334v1


# Templates, Arrays, and Overlays

Jordan Broussard

An _array_ is a function $A:\mathbb{Z}^{2}\rightarrow\mathbb{F}$, where
$\mathbb{F}$ is a field. We adopt the matrix notation $A_{r,c}$ instead of
$A(r,c)$. An array can be thought of as an extention of Riordan arrays
(removing the condition that the array is lower-triangular) with indices from
$\mathbb{Z}$ rather than indices from $\mathbb{N}$. Instead of using the rows
of the array to store powers of the coefficients of the generating
function[2], we store the coefficients of a generating function in two
variables ($x$ and $y$) where the degree of $x$ denotes the row and the degree
of $y$ denotes the column. ***Add comment about how to actually use it as a
Riordan array *** Since the array allows negative indices, then the
corresponding generating function is a formal Laurent series rather than a
formal power series. That is, we can define the generating function $a(x,y)$
as

$a(x,y)=\sum_{(r,c)\text{ }\in\text{ }\mathbb{Z}^{2}}A_{r,c}\text{
}x^{r}y^{c}.$

[1]

######  Observation 1.

The set of arrays is a vector space under entry-wise addition and scalar
multiplication.

Let $X$ and $Y$ be shift operators such that $(XA)_{r,c}=A_{r,c-1}$ and
$(YA)_{r,c}=A_{r-1,c}$. Notice that $X$ and $Y$ are invertible linear
operators and they commute.

######  Definition 1.

A _template $T$_ is a polynomial in $X$ and $Y$, where $X^{0}=Y^{0}=I$, the
identity operator.

Since $T$ is a polynomial of linear operators, then $T$ is also linear.

######  Definition 2.

$A$ is _annihilated by_ the operator $\Psi$ if $\Psi A=0$, where 0 denotes the
zero array.

######  Definition 3.

We also say that $A$ is a _template array with template $T$_ if $A$ is
annihilated by a template $T$.

As an example, let $A$ be a template array with template $T$, where
$T=I-Y(I+X)$. Then we can recover the two-dimensional recurrence by
considering the $(r,c)$ entry of $T$ applied to $A$. Since $A$ is a template
array, then we have

$\displaystyle(TA)_{r,c}$ $\displaystyle=0\Leftrightarrow$
$\displaystyle((I-Y(I+X))A)_{r,c}$ $\displaystyle=0\Leftrightarrow$
$\displaystyle((I-Y-XY)A)_{r,c}$ $\displaystyle=0\Leftrightarrow$
$\displaystyle A_{r,c}-A_{r-1,c}-A_{r-1,c-1}$ $\displaystyle=0\Leftrightarrow$
$\displaystyle A_{r,c}=A_{r-1,c}+A_{r-1,c-1}$ .

######  Definition 4.

An _overlay for a template T_ is an array with finite support that contains
the coefficients of $T$.

We typically draw overlays with only their nonzero entries visible. We can
define the _overlay product_ of two arrays by the Hadamard product (or the sum
of entry-wise products). We define the dimensions of an overlay to be (number
of rows containing non-zero entries) $\times$ (number of columns containing
non-zero entries). Let the array $B=\left(b_{i,j}\right)$ be an overlay for
the template $T$. Let the right-most nonzero entry have column index 0 and the
left-most nonzero entry have column index $n$. Likewise, let the vertically
lowest nonzero entry have row index 0 and the verically highest entry have row
index $m$. The coefficient $b$ for the term $bX^{c}Y^{r}$ is the entry in the
cell with row index $r$ and column index $c$.

For example, for the template $T=I-Y(I+X)=I-Y(I+X)$, the corresponding overlay
would be

$-1$$-1$$1$

Let $A$ be an array annihilated by $T$. Then the Hadamard product of the
overlay $B$ (derived from the template $T$) and the array $A$ will always be
zero for all $(r,c)$ such that $A_{r,c}$ is lined up to mutliply by $b_{0,0}$.

Let $B=\left(b_{i,j}\right)$ be an overlay with dimension $(m+1)\times(n+1)$
for a template $T$ that annihilates $A$. Then for all $r,c\in\mathbb{Z}$,

$\sum_{i=0}^{m}\sum_{j=0}^{n}b_{i,j}A_{r-i,c-j}=0.$

For an overlay $B=\left(b_{i,j}\right)$, we define $n,m,u,$ and $l$ such that
the top row of the overlay is $u+1$ units wide, the bottom row of the overlay
is $l+1$ units wide, the furthest column to the right containing a nonzero
entry in the overlay is indexed zero, the furthest column to the left
containing a nonzero entry in the overlay is indexed $n$, and the height of
the overlay is $m+1$ units tall. We often omit writing the zero entries prior
to the first nonzero entry in that row and after the last nonzero entry in
that row. An overlay may look something like the following, where $*$ is an
element from $\mathbb{F}$.

$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$\cdots$$\cdots$$\ddots$$\cdots$$\cdots$$\ddots$$\cdots$$\cdots$$\ddots$$\cdots$$\cdots$$\ddots$$\cdots$$\cdots$$\ddots$$*$$*$$\cdots$$*$$*$$\cdots$

For example, consider the recurrence
$A_{r-1,c-1}+3A_{r-1,c}+2A_{r,c-1}-A_{r,c}=0$. Then the corresponding template
would be $T=XY+3Y+2X-I$, and the corresponding overlay is

$2$$-1$$1$$3$

Now suppose that we want to construct an array $A$ that is annihilated by $T$,
and we are given that $A_{0,0}=1,A_{0,c}=0$ if $c\neq 0,A_{r,0}=0$ if $r\neq
0$. Then initially, $A$ looks like

$\cdots$$0$$1$$0$$0$$0$$\cdots$$\vdots$$0$$0$$0$$0$$\vdots$

Imagine placing the overlay on top of $A$ such that the one in the upper left
corner of the overlay is in the same position as the 1 in $A$. We can observe
that three of the four corresponding entries in $A$ are known. Since the
Hadamard product must be zero, we can solve for the value in $A$ that
corresponds to the bottom right corner of where the overlay is placed. Call
this value $z$. Then by solving the equation $1*1+0*3+0*2+z*-1=0$ for $z$, we
have that $z=1$. By placing it into $A$, that gives us

$\cdots$$0$$1$$0$$0$$0$$\cdots$$\vdots$$0$$0$$0$$0$$\vdots$

$\cdots$$0$$1\cdot 1$$0\cdot 3$$0$$0$$\cdots$$\vdots$$0$$0$$0\cdot
2$$0$$\vdots$$z\cdot-1$

$\cdots$$0$$1$$0$$0$$0$$\cdots$$\vdots$$0$$0$$0$$0$$\vdots$$1$

Notice that if we look at the original recurrence
$A_{r-1,c-1}+3A_{r-1,c}+2A_{r,c-1}-A_{r,c}=0$ with $r=1,c=1$, we have the same
computation to solve for $A_{1,1}$ as when we use the overlay to compute
$A_{1,1}$. By shifting the overlay one position to the right, then $r=1,c=2$,
which corresponds to the equation $0*1+0*3+1*2-z*-1=0$. Solving for $z$, we
have that $z=2$.

$\cdots$$0$$1$$0$$0$$0$$\cdots$$\vdots$$0$$0$$0$$0$$\vdots$$1$

$\cdots$$0$$1$$0\cdot 1$$0\cdot 3$$0$$\cdots$$\vdots$$0$$0$$0$$1\cdot
2$$0$$\vdots$$z\cdot-1$

$\cdots$$0$$1$$0$$0$$0$$\cdots$$\vdots$$0$$0$$0$$1$$0$$\vdots$$2$

By shifting the array one unit down from the first position of the overlay,
this is another step that we could have taken as our second movement as it
does not rely on the computation done above (although it will be left in the
array). For this computation, we solve for $z$ in the equation
$0*1+0*3+1*2-z*-1=0$, which results in $z=3$.

$\cdots$$0$$1$$0$$0$$0$$\cdots$$\vdots$$0$$0$$0$$0$$\vdots$$1$$2$

$\cdots$$0$$1$$0$$0$$0$$\cdots$$\vdots$$0$$0\cdot 2$$0\cdot 1$$1\cdot
3$$0$$\vdots$$2$$z\cdot-1$

$\cdots$$0$$1$$0$$0$$0$$\cdots$$\vdots$$0$$0$$0$$1$$0$$\vdots$$2$$3$

By shifting the overlay in different positions throughout $A$ such that three
of the four corresponding entries in $A$ are known, we can populate the rest
of $A$, as seen below.

$\ddots$

$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$$\ddots$$\cdots$$-\frac{3}{8}$$0$$9$$58$$249$$\cdots$$\cdots$$\frac{3}{4}$$0$$3$$13$$40$$\cdots$$\cdots$$-\frac{3}{2}$$0$$1$$2$$4$$\cdots$$\cdots$$0$$1$$0$$0$$0$$\cdots$$\cdots$$1$$0$$-\frac{2}{3}$$\frac{2}{9}$$-\frac{2}{27}$$\cdots$$\ddots$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$

$\ddots$

This example illustrates the use of the overlay to populate $A$ rather than
working directly with the recurrence.

######  Theorem 2.

If we have an overlay $B=\left(b_{i,j}\right)$ such that the top row of the
overlay is $u+1$ units wide, the bottom row is $l+1$ units wide, the furthest
column to the right containing a nonzero entry in the overlay is indexed zero,
the furthest column to the left containing a nonzero entry in the overlay is
indexed $n$, and the bottom-most row containing a nonzero entry in the overlay
is indexed $0$ while the top-most row containing a nonzero entry in the
overlay is indexed $m$, then $m$ consecutive rows of initial conditions, along
with $u$ consecutive columns coming out of the top and $l$ consecutive columns
coming out of the bottom of these rows is sufficient to populate the rest of
the array.

###### Proof.

Observe that if $n=0$ and $m=0$ then $b_{0,0}\neq 0$ (otherwise we would not
have a valid overlay). Then the overlay corresponds to the recurrence

$0=\sum_{i=0}^{0}\sum_{j=0}^{0}b_{i,j}A_{r-i,c-j}=b_{0,0}A_{r,c}.$

Since $b_{0,0}\neq 0$, then $A_{r,c}=0$, so the only valid array is the zero
array. Suppose that $n$ and $m$ are not both simultaneously zero.

If $m=0$ and $n\neq 0$, then the initial conditions we claim to be sufficient
to populate the entire array is $n$ columns that are pre-populated and no rows
that are pre-populated. Without loss of generality, let the pre-populated
columns be indexed 0 through $n-1$. Then we have

$\sum_{j=0}^{n}b_{0,j}A_{r,c-j}=0.$

If trying to populate a column one unit to the right of the previously
constructed columns, say column $c\geq n$, then by our assumptions, the
columns indexed 0 through $c-1$ have already been populated. Thus for our
summation, we have

$\sum_{j=0}^{n}b_{0,j}A_{r,c-j}=0.$

Since $j$ ranges between 0 and $n$, then $c-1-j\leq c-1$ and $0\leq c-n\leq
c-j$. Thus each $A_{r,c-j}$ is already determined except for $A_{r,c}$, and
since $b_{0,0}\neq 0$, $A_{r,c}$ is uniquely determined by the recurrence.
Since $r$ is arbitrary, then the entire column can be populated this way.

Similarly, relying on the fact that $b_{0,n}\neq 0$, we can constrcut a column
$c<0$

For the remaining cases, it suffices to show that we can construct a row above
the $m$ consecutive rows and a row below the $m$ consecutive rows in order to
populate the array because if we do one, then we can build the next row above
by placing the overlay in the starting position from the previous row, move
the overlay up one row, and repeat the process outlined below. The same holds
for rows below, we just move the overlay down instead of up.

Given the overlay described above, the overlay corresponds to the recurrence

$\sum_{i=0}^{m}\sum_{j=0}^{n}b_{i,j}A_{r-i,c-j}=0$

where $b_{i,j}$ are the coefficients in the overlay with at least one nonzero
entry in the $0^{\text{th}}$ row, in the $0^{\text{th}}$ column, in the
$m^{\text{th}}$ row and in the $n^{\text{th}}$ column.

Without loss of generality, let the $m$ consecutive rows of initial conditions
be the rows indexed 0 through $m-1$.

Case 1 ($u=0$): Since $u=0$, then there is a single nonzero value in the top
row of the overlay. Let the nonzero element in the $m^{\text{th}}$ row of the
overlay (top row) be the column indexed $a\in\mathbb{Z}$. Through the
description of the overlay, we know that $0\leq s\leq n$. Since there is a
single nonzero value in the top row of the overlay, there are no columns of
initial conditions protruding out of the top of the $m$ consecutive rows. If
we place the bottom row of the overlay in the $m-1$ row, then the top row of
the overlay is in the row indexed $-1$. Let $y\in\mathbb{Z}$. Since there are
no columns of initial conditions, let the column in which the $s$ column in
the overlay resides be indexed $y$. By the recurrence, we have

$0=\sum_{i=0}^{m}\sum_{j=0}^{n}b_{i,j}A_{r-i,c-j}.$

Taking $c=s+y$ and $r=m-1$ as described in the placement of the bottom row,
our recurrence becomes

$\displaystyle 0$
$\displaystyle=\sum_{i=0}^{m}\sum_{j=0}^{n}b_{i,j}A_{m-1-i,s+y-j}$
$\displaystyle 0$
$\displaystyle=b_{m,s}A_{m-1-m,s+y-s}+\sum_{i=0}^{m-1}\sum_{j=0}^{s-1}b_{i,j}A_{m-1-i,s+y-j}+\sum_{i=0}^{m-1}\sum_{j=s+1}^{n}b_{i,j}A_{m-1-i,s+y-j}$
$\displaystyle\hskip
28.45274pt+\sum_{i=0}^{m-1}b_{i,s}A_{m-1-i,s+y-s}+\sum_{j=0}^{s-1}b_{m,j}A_{m-1-m,s+y-j}+\sum_{j=s+1}^{n}b_{m,j}A_{m-1-m,s+y-j}$

Since the $m^{\text{th}}$ row of the overlay contains only one nonzero
element, then $b_{m,j}=0$ for all $j\neq s$. Thus

$\sum_{j=0}^{s-1}b_{m,j}A_{m-1-m,s+y-j}+\sum_{j=s+1}^{n}b_{m,j}A_{m-1-m,s+y-j}=0.$

So simplifying some of the indices in the previous expansion, we have

$\displaystyle 0$
$\displaystyle=b_{m,s}A_{-1,y}+\sum_{i=0}^{m-1}\sum_{j=0}^{s-1}b_{i,j}A_{m-1-i,s+y-j}+\sum_{i=0}^{m-1}\sum_{j=s+1}^{n}b_{i,j}A_{m-1-i,s+y-j}+\sum_{i=0}^{m-1}b_{i,s}A_{m-1-i,y}$
$\displaystyle\Leftrightarrow-
b_{m,s}A_{-1,y}=\sum_{i=0}^{m-1}\sum_{j=0}^{s-1}b_{i,j}A_{m-1-i,s+y-j}+\sum_{i=0}^{m-1}\sum_{j=s+1}^{n}b_{i,j}A_{m-1-i,s+y-j}+\sum_{i=0}^{m-1}b_{i,s}A_{m-1-i,y}.$

Since $b_{m,s}\neq 0$, dividing both sides by $-b_{m,s}$, we have

$A_{-1,y}=-\dfrac{1}{b_{m,s}}\left(\sum_{i=0}^{m-1}\sum_{j=0}^{s-1}b_{i,j}A_{m-1-i,s+y-j}+\sum_{i=0}^{m-1}\sum_{j=s+1}^{n}b_{i,j}A_{m-1-i,s+y-j}+\sum_{i=0}^{m-1}b_{i,s}A_{m-1-i,y}\right).$

Since the rows in each sum range from $m-1-(m-1)=0$ to $m-1-0=m-1$, then each
$A_{m-1-i,s+y-j}$ is determined by the initial conditions. Thus, $A_{-1,y}$ is
uniquely determined by the recurrence. Since $y$ is arbitrary, then the entire
row can be populated this way.

Case 2 ($u>0$): Let $a,d,\in\mathbb{Z}$. Then let the $u$ consecutive columns
above the $m$ consecutive rows be the columns indexed $a$ through $a+u-1$ and
the $l$ columns below the $m$ consecutive rows be indexed $d$ through $d+l-1$.
Below, an array with the initial conditions present can be seen.

$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$\cdots$$\cdots$$\ddots$$\cdots$$\cdots$$\ddots$$\cdots$$\cdots$$\ddots$$\cdots$$\cdots$$\ddots$$\cdots$$\cdots$$\ddots$$\cdots$$\cdots$$\ddots$$\cdots$$\cdots$$\ddots$$*$$*$$*$$*$$\vdots$$\vdots$$*$$*$$*$$*$$\vdots$$\vdots$$m$
rows0$m-1$$u$ columns$a$$a+u$$l$ columns$d$$d+l$$n$ columns$n-1$0

Observe that $u\leq n$ and $l\leq n$. Let the column of the right-most nonzero
entry in the top row ($m^{\text{th}}$ row) in the overlay be denoted $s$ and
let the column of the right-most nonzero entry in the bottom row
($0^{\text{th}}$ row) in the overlay be denoted $t$. If we place the bottom
row of the overlay in the $m-1$ row of the array, then the top row is in the
row indexed $-1$. If we then slide the overlay horizontally so that the left-
most nonzero entry in the top row of the overlay is in the column indexed by
$a$ in the array. By positioning the overlay in this manner, this corresponds
to taking $c=s+a+u$ and $r=m-1$ in the recurrence, as described in the
placement of the bottom row, as demonstrated in the image below.

$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$\cdots$$\cdots$$\ddots$$\cdots$$\cdots$$\ddots$$\cdots$$\cdots$$\ddots$$\cdots$$\cdots$$\ddots$$\cdots$$\cdots$$\ddots$$\cdots$$\cdots$$\ddots$$\cdots$$\cdots$$\ddots$$*$$*$$*$$*$$\vdots$$\vdots$$*$$*$$*$$*$$\vdots$$\vdots$$m$
rows0$m-1$$u$ columns$a$$a+u$$l$ columns$d$$d+l$$n$ columns$n-1$0

$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$*$$*$$\vdots$$\cdots$$\cdots$$\ddots$$\cdots$$\cdots$$\ddots$$\cdots$$\cdots$$\ddots$$\cdots$$\cdots$$\ddots$$\cdots$$\cdots$$\ddots$$\cdots$$\cdots$$\ddots$$\cdots$$\cdots$$\ddots$$*$$*$$*$$*$$\vdots$$\vdots$$*$$*$$*$$*$$\vdots$$\vdots$$m$
rows0$m-1$$u$ columns$a$$a+u$$l$ columns$d$$d+l$$n$ columns$n-1$0

Thus our recurrence becomes

$\displaystyle 0$
$\displaystyle=\sum_{i=0}^{m}\sum_{j=0}^{n}b_{i,j}A_{m-1-i,s+a+u-j}$
$\displaystyle\Leftrightarrow 0$
$\displaystyle=b_{m,s}A_{m-1-m,s+a-u-s}+\sum_{i=0}^{m-1}\sum_{j=0}^{s-1}b_{i,j}A_{m-1-i,s+a+u-j}+\sum_{i=0}^{m-1}\sum_{j=s+1}^{n}b_{i,j}A_{m-1-i,s+a+u-j}$
$\displaystyle\hskip
28.45274pt+\sum_{i=0}^{m-1}b_{i,s}A_{m-1-i,s+a+u-s}+\sum_{j=0}^{s-1}b_{m,j}A_{m-1-m,s+a+u-j}+\sum_{j=s+1}^{n}b_{m,j}A_{m-1-m,s+a+u-j}$

Since the $m^{\text{th}}$ row of the overlay contains only entries from $s$ to
$s+u$, then $b_{m,j}=0$ for all $j<s$, and $b_{m,j}=0$ for all $j>s+u$. Thus,

$\sum_{j=0}^{s-1}b_{m,j}A_{m-1-m,s+a+u-j}=0+\sum_{j=s+1}^{s+u}b_{m,j}A_{m-1-m,s+a+u-j}.$

So simplifying some of our indices from the previous expansion, we have

$\displaystyle 0=b_{m,s}A_{-1,a+u}$
$\displaystyle+\sum_{i=0}^{m-1}\sum_{j=0}^{s-1}b_{i,j}A_{m-1-i,s+a+u-j}+\sum_{i=0}^{m-1}\sum_{j=s+1}^{n}b_{i,j}A_{m-1-i,s+a+u-j}$
$\displaystyle+\sum_{i=0}^{m-1}b_{i,s}A_{m-1-i,a+u}+\sum_{j=s+1}^{s+u}b_{m,j}A_{-1,s+a+u-j}$
$\displaystyle\Leftrightarrow-b_{m,s}A_{-1,a+u}$
$\displaystyle=\sum_{i=0}^{m-1}\sum_{j=0}^{s-1}b_{i,j}A_{m-1-i,s+a+u-j}+\sum_{i=0}^{m-1}\sum_{j=s+1}^{n}b_{i,j}A_{m-1-i,s+a+u-j}$
$\displaystyle+\sum_{i=0}^{m-1}b_{i,s}A_{m-1-i,a+u}+\sum_{j=s+1}^{s+u}b_{m,j}A_{-1,s+a+u-j}.$

Since $b_{m,s}\neq 0$, dividing both sides by $-b_{m,s}$, we have

$\displaystyle A_{-1,a+u}$
$\displaystyle=-\dfrac{1}{b_{m,s}}\left(\sum_{i=0}^{m-1}\sum_{j=0}^{s-1}b_{i,j}A_{m-1-i,s+a+u-j}+\sum_{i=0}^{m-1}\sum_{j=s+1}^{n}b_{i,j}A_{m-1-i,s+a+u-j}\right.$
$\displaystyle+\left.\sum_{i=0}^{m-1}b_{i,s}A_{m-1-i,a+u}+\sum_{j=s+1}^{s+u}b_{m,j}A_{-1,s+a+u-j}\right).$

Since the rows of the array in each of the first three sums range from
$m-1-(m-1)=0$ to $m-1-0=m-1$, then each $A_{m-1-i,s+a+u-j}$ is determined by
the initial conditions. Now let’s consider the $m^{\text{th}}$ row of the
overlay, which is denoted by the last sum and is the row indexed $-1$ in the
array. In the fourth sum, the columns in the array range from $s+a+u-(s+u)=a$
to $s+a+u-(s+1)=a+u-1$. Since the columns in which the initial conditions are
defined are columns $a$ through $a+u-1$, then each $A_{-1,s+a+u-j}$ is
determined by the initial conditions.

Since all entries on the right side of the equals sign are determined by the
initial conditions, then $A_{-1,a+u}$ is uniquely determined by the
recurrence. By shifting the overlay to the right one column, we can similarly
get the next entry and thus fill in the right side of the row. If we orient
the overlay in the same location vertically but shift the overlay one column
to the left compared to the original orientation, then this corresponds to
$r=m-1$ and $c=s+a+u-1$ in the recurrence. Thus our recurrence becomes

$\displaystyle 0$
$\displaystyle=\sum_{i=0}^{m}\sum_{j=0}^{n}b_{i,j}A_{m-1-i,s+u-1-j}$
$\displaystyle\Leftrightarrow 0$
$\displaystyle=b_{m,s+u}A_{m-1-m,s+a+u-1-(s+u)}+\sum_{i=0}^{m-1}\sum_{j=0}^{s+u-1}b_{i,j}A_{m-1-i,s+a+u-1-j}$
$\displaystyle\hskip
28.45274pt+\sum_{i=0}^{m-1}\sum_{j=s+u+1}^{n}b_{i,j}A_{m-1-i,s+a+u-1-j}+\sum_{i=0}^{m-1}b_{i,s+u}A_{m-1-i,s+a+u-1-(s+u)}$
$\displaystyle\hskip
28.45274pt+\sum_{j=0}^{s+u-1}b_{m,j}A_{m-1-m,s+a+u-1-j}+\sum_{j=s+u+1}^{n}b_{m,j}A_{m-1-m,s+a+u-1-j}$

Since the $m^{\text{th}}$ row of the overlay contains only entries from $s$ to
$s+u$, then $b_{m,j}=0$ for all $j<s$ and $b_{m,j}=0$ for all $j>s+u$. Thus

$\sum_{j=0}^{s+u-1}b_{m,j}A_{m-1-m,s+a+u-1-j}+\sum_{j=s+u+1}^{n}b_{m,j}A_{m-1-m,s+a+u-1-j}=\sum_{j=s}^{s+u-1}b_{m,j}A_{m-1-m,s+a+u-1-j}+0.$

So simplifying some of the indices in the previous expansion, we have

$\displaystyle 0$
$\displaystyle=b_{m,s+u}A_{-1,a-1}+\sum_{i=0}^{m-1}\sum_{j=0}^{s+u-1}b_{i,j}A_{m-1-i,s+a+u-1-j}+\sum_{i=0}^{m-1}\sum_{j=s+u+1}^{n}b_{i,j}A_{m-1-i,s+a+u-1-j}$
$\displaystyle\hskip
28.45274pt+\sum_{i=0}^{m-1}b_{i,s+u}A_{m-1-i,a-1}+\sum_{j=s}^{s+u-1}b_{m,j}A_{-1,s+a+u-1-j}$
$\displaystyle\Leftrightarrow-
b_{m,s+u}A_{-1,a-1}=\sum_{i=0}^{m-1}\sum_{j=0}^{s+u-1}b_{i,j}A_{m-1-i,s+a+u-1-j}+\sum_{i=0}^{m-1}\sum_{j=s+u+1}^{n}b_{i,j}A_{m-1-i,s+a+u-1-j}$
$\displaystyle\hskip
28.45274pt+\sum_{i=0}^{m-1}b_{i,s+u}A_{m-1-i,a-1}+\sum_{j=s}^{s+u-1}b_{m,j}A_{-1,s+a+u-1-j}.$

Since $b_{m,s+u}\neq 0$, dividing both sides by $-b_{m,s+u}$, we have

$\displaystyle A_{-1,a-1}$
$\displaystyle=-\dfrac{1}{b_{m,s+u}}\left(\sum_{i=0}^{m-1}\sum_{j=0}^{s+u-1}b_{i,j}A_{m-1-i,s+a+u-1-j}+\sum_{i=0}^{m-1}\sum_{j=s+u+1}^{n}b_{i,j}A_{m-1-i,s+a+u-1-j}\right.$
$\displaystyle\hskip
28.45274pt+\left.\sum_{i=0}^{m-1}b_{i,s+u}A_{m-1-i,a-1}+\sum_{j=s}^{s+u-1}b_{m,j}A_{-1,s+a+u-1-j}\right).$

Since the rows of the array in each of the first three sums range from
$m-1-(m-1)=0$ to $m-1-0=m-1$, then each $A_{m-1-i,s+a+u-1-j}$ is determined by
the initial conditions. Now let’s consider the $m^{\text{th}}$ row of the
overlay, which is denoted by the last sum and is the row indexed $-1$ in the
array. In the fourth sum, the columns in the array range from
$s+a+u-1-(s+u-1)=a$ to $s+a+u-1-(s)=a+u-1.$ Since the columns in which the
initial conditions are defined are columns $a$ through $a+u-1$, then each
$A_{-1,s+a+u-1-j}$ is determined by the initial conditions.

Since all entries on the right side of the equals sign are determined by the
initial conditions, then $A_{-1,a-1}$ is uniquely determined by the
recurrence.

By shifting the overlay horizontally to the left by one column, then we can
similarly get the next entry, and thus fill in the left side of the first row.
In order to get the row above this, we shift the overlay up one row from its
initial position and repeat this process, thus filling in the negative rows of
the array.

For the positive rows indexed $\geq m$, the proof is similar, which $l$ is
used instead of $u$, $d$ is used instead of $a$, $t$ is used instead of $s$,
$m$ is used instead of $-1$, and a shift of the overlay up a row becomes a
shift of the overlay down a row. Alternatively, we can think about getting the
positive rows through plane transformations.

######  Definition 5.

A _valid initial conditions layout_ is the set of elements in $\mathbb{Z}^{2}$
(coordinates) that define the location of the initial conditions.

In order to be an initial conditions layout, the initial conditions must
construct a unique array when the overlay is applied. In other words, a layout
is the locations on the array that must be filled in with initial values in
order to construct a unique array for a given overlay. We do assume here that
the overlay contains at least one nonzero entry.

######  Definition 6.

A _standard initial conditions layout_ is the layout described in theorem 2.

However, there are other possible initial conditions layouts that are valid
for different overlays. For example, if we have the template
$T=b_{0,0}+b_{1,0}Y+b_{1,1}XY$, where $b_{0,0},b_{1,0},b_{1,1}\neq 0$, with
corresponding overlay

$b_{1,1}$$b_{1,0}$$b_{0,0}$

then the standard initial conditions layout would be

$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$\cdots$$\cdots$$\vdots$

where * denotes a populated cell due to an initial condition. Alternatively,
another valid initial conditions layout could be

$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$\ddots$$\ddots$$\cdots$

where * denotes a populated cell due to an initial condition

We can see that this is a valid initial conditions layout for this overlay
because we can uniquely construct the array as we move around the overlay,
filling in cells as shown below.

######  Lemma 3.

If we have an overlay $B=(b_{i,j})$ with template
$T=b_{0,0}+b_{1,0}Y+b_{1,1}XY$, where $b_{0,0},b_{1,0},b_{1,1}\neq 0$, then
populated values of $A_{r,c}$ such that $A_{i,i},i\in\mathbb{Z}$ and for a
fixed row $k$, $A_{k,c}$ such that $c\in\mathbb{Z},c<k$, then we can uniquely
construct the array $A$ from this initial conditions layout.

###### Proof.

Let $k$ be the integer such that $A_{k,c}$ such that $c<k$ is populated by the
initial conditions. Since $T=b_{0,0}+b_{1,0}Y+b_{1,1}XY$, then for all
$(r,c)\in\mathbb{Z}^{2}$,

$b_{0,0}A_{r,c}+b_{1,0}A_{r-1,c}+b_{1,1}A_{r-1,c-1}=0$

Region 1: First, we will show $A_{r,c}$ can be populated uniquely for
$A_{r,c}$ such that $r\geq k,c\geq r$. For the base case, we have that
$A_{r,r},r\in\mathbb{Z}$ is populated due to initial conditions. In this case,
$r=c$, or equivalently, $c-r=0$ Let $p\geq 0$, and suppose $A_{r,c}$ can be
uniquely populated for $0\leq c-r\leq p$. We want to show this holds for
$c-r=p+1$. From the recurrence, we have that
$b_{0,0}A_{r,c}+b_{1,0}A_{r-1,c}+b_{1,1}A_{r-1,c-1}=0$. Consider $c,r$ such
that $c-r=p$, or $c=r+p$. Then our recurrence becomes

$b_{0,0}A_{r,r+p}+b_{1,0}A_{r-1,r+p}+b_{1,1}A_{r-1,r+p-1}=0.$

Notice that for the term $A_{r-1,r+p+1}$, subtracting the row index from the
column index, we have $r+p-(r-1)=p+1$. However, for the term $A_{r,r+p}$,
subtracting the row index from the column index is $r+p-(r)=p$, so $A_{r,r+p}$
has already been populated by our assumption, and for the term
$A_{r-1,r+p-1}$, subtracting the row index from the column index is
$r+p-1-(r-1)=p$, so $A_{r-1,r+p-1}$ has also already been populated by our
assumption. Since $b_{0,0},b_{1,0},b_{1,1}\neq 0$, then we have

$A_{r-1,r+p}=-\frac{1}{b_{1,0}}\left(b_{0,0}A_{r,r+p}+b_{1,1}A_{r-1,r+p-1}\right).$

Thus $A_{r-1,r+p}$ is uniquely determined, thus $A_{r,c}$ is uniquely
determined for $c-r=p+1$.

Region 2: Next, we will show $A_{r,c}$ can be populated uniquely for $A_{r,c}$
such that $r\leq k,c\leq r$. For the outer induction base case, we have that
$A_{k,c}$ for $c\leq k$ is populated due to initial conditions. Furthermore,
we also have that $A_{r,r},r\in\mathbb{Z}$ is populated due to initial
conditions. Let $p\in\mathbb{Z},p\geq 0$, and suppose, for the outer induction
hypothesis, $A_{r,c}$ can be uniquely populated for $A_{k-p,c},c\leq k-p$. We
want to show we can uniquely populate $A_{k-(p+1),c},c\leq k-(p+1)$. From the
recurrence, we have that
$b_{0,0}A_{r,c}+b_{1,0}A_{r-1,c}+b_{1,1}A_{r-1,c-1}=0$. For the inner
induction base case, consider $r=k-p,c=k-(p+1)=k-p-1$. Then the recurrence
becomes

$b_{0,0}A_{k-p,k-p-1}+b_{1,0}A_{k-p-1,k-p-1}+b_{1,1}A_{k-p-1,k-p-2}=0.$

Observe that $A_{k-p-1,k-p-1}$ is populated due to the initial conditions, and
$A_{k-p,k-p-1}$ is populated due to the outer induction hypothesis since
$c=k-p-1<k-p$. Thus since $b_{1,1}\neq 0$, we have

$A_{k-p-1,k-p-2}=-\frac{1}{b_{1,1}}\left(b_{0,0}A_{k-p,k-p-1}+b_{1,0}A_{k-p-1,k-p-1}\right),$

so $A_{k-p-1,k-p-2}$ is uniquely populated by the recurrence. Let
$j\in\mathbb{Z},j\geq 0$, and suppose, for the inner induction hypothesis,
that $A_{r,c}$ can be uniquely populated for $A_{k-(p+1),k-(p+1)-j}$ i.e.
$A_{k-p-1,k-p-j-1}$ (thus maintaining that the column index less than or equal
to the row index). We want to show $A_{k-(p+1),k-(p+1)-(j+1)}$ i.e.
$A_{k-p-1,k-p-j-2}$ can be uniquely populated. By considering
$r=k-p,c=k-(p+1)-j$, the recurrence becomes
$b_{0,0}A_{k-p,k-p-j-1}+b_{1,0}A_{k-p-1,k-p-j-1}+b_{1,1}A_{k-p-1,k-p-j-2}=0$
i.e.

$b_{0,0}A_{k-p,k-j-(p+1)}+b_{1,0}A_{k-(p+1),k-j-(p+1)}+b_{1,1}A_{k-(p+1),k-(p+1)-(j+1)}=0.$

Since $A_{k-(p+1),k-j-(p+1)}$ is uniquely populated by the outer induction
hypothesis and $A_{k-(p+1),k-j-(p+1)}$ is uniquely populated by the inner
induction hypothesis. Thus since $b_{1,1}\neq 0$,

$A_{k-(p+1),k-(p+1)-(j+1)}=-\frac{1}{b_{1,1}}\left(b_{0,0}A_{k-p,k-j-(p+1)}+b_{1,0}A_{k-(p+1),k-j-(p+1)}\right)$

and thus $A_{k-(p+1),k-(p+1)-(j+1)}$ is uniquely determined by the recurrence.

Region 3: Finally, we will show $A_{r,c}$ can be populated uniquely for
$A_{r,c}$ such that $r\geq k,c\leq r$. For the outer induction base case, we
have that $A_{k,c}$ for $c\leq k$ is populated due to initial conditions.
Furthermore, we also have that $A_{r,r},r\in\mathbb{Z}$ is populated due to
initial conditions. Let $p\in\mathbb{Z},p\geq 0$, and suppose, for the outer
induction hypothesis, $A_{r,c}$ can be uniquely populated for $A_{k+p,c},c\leq
k+p$. We want to show we can uniquely populate $A_{k+(p+1),c},c\leq k+(p+1)$.
From the recurrence, we have that
$b_{0,0}A_{r,c}+b_{1,0}A_{r-1,c}+b_{1,1}A_{r-1,c-1}=0$. For the inner
induction base case, consider $r=k+p+1,c=k+p$. Then the recurrence becomes

$b_{0,0}A_{k+p+1,k+p}+b_{1,0}A_{k+p,k+p}+b_{1,1}A_{k+p,k+p-1}=0.$

Observe that $A_{k+p,k+p}$ is populated due to the initial conditions, and
$A_{k+p,k+p-1}$ is populated due to the outer induction hypothesis since
$c=k+p-1<k+p$. Thus since $b_{0,0}\neq 0$, we have

$A_{k+p+1,k+p}=-\frac{1}{b_{0,0}}\left(b_{1,0}A_{k+p,k+p}+b_{1,1}A_{k+p,k+p-1}\right),$

so $A_{k+p+1,k+p}$ is uniquely populated by the recurrence. Let
$j\in\mathbb{Z},j\geq 0$, and suppose, for the inner induction hypothesis,
that $A_{r,c}$ can be uniquely populated for $A_{k+p+1,k+p+1-j}$ (thus
maintaining that the column index less than or equal to the row index). We
want to show $A_{k+p+1,k+p+1-(j+1)}$ i.e. $A_{k+p+1,k+p-j}$ can be uniquely
populated. By considering $r=k+p+1,c=k+p-j$, the recurrence becomes
$b_{0,0}A_{k+p+1,k+p-j}+b_{1,0}A_{k+p,k+p-j}+b_{1,1}A_{k+p,k+p-j-1}=0$, i.e.

$b_{0,0}A_{k+p+1,k+p-j}+b_{1,0}A_{k+p,k+p-j}+b_{1,1}A_{k+p,k+p-(j+1)}=0.$

Since $A_{k+p,k+p-j}$ is uniquely populated by the outer induction hypothesis
since $c=k+p-j<k+p$ and $A_{k+p,k+p-(j+1)}$ is uniquely populated by the inner
induction hypothesis.

$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$\ddots$$\ddots$$\cdots$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$\ddots$$\ddots$$\cdots$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$\ddots$$\ddots$$\cdots$$*$

$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$\ddots$$\ddots$$\cdots$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$\ddots$$\ddots$$\cdots$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$*$$\ddots$$\ddots$$\cdots$$*$$*$$*$

######  Lemma 4.

Let $B=(b_{ij})$ be a $2\times 2$ overlay and $E(i,j)$ be basis arrays built
from the overlay applied to initial conditions defined as follows: for $k,l$
in the initial conditions layout $\gamma$,

$E(i,j)_{k,l}=\begin{cases}1&k=i\text{ and }l=j\\\ 0&otherwise.\end{cases}$

For $(i,j)\in\gamma$,
Case 1: If $j>0,$ then $E(i,j)_{k,l}=0$ for $l<j$.
Case 2: If $j<0,$ then $E(i,j)_{k,l}=0$ for $l>j$.
Case 3: If $i>0,$ then $E(i,j)_{k,l}=0$ for $k<i$.
Case 4: If $i<0,$ then $E(i,j)_{k,l}=0$ for $k>i$.

###### Proof.

Case 1: $j>0$. Without loss of generality, take $\gamma$ to be the standard
initial conditions layout. Then $E(0,j)_{\alpha,0}=0$ for all $\alpha$ and
$E(0,j)_{0,\beta}=0$ for all $\beta\neq j$ by the initial conditions. We will
show $E(i,j)_{k,l}=0$ for $l<j$ by induction on $l$. $l=0$ is given from the
initial conditions, so assume that $E(0,j)_{k,l}=0$ for all $l$ such that
$0\leq l\leq\lambda<j-1$. We want to show this holds for $l=\lambda+1$.

We know $E(0,j)_{0,\lambda+1}=0$ by the initial conditions, so assume by
induction on $k>0$ that $E(0,j)_{k,\lambda+1}=0$. We want to show that
$E(0,j)_{k+1,\lambda+1}=0.$ By our recurrence, we have

$E(0,j)_{k+1,\lambda+1}=-\dfrac{1}{b_{00}}(b_{11}E(0,j)_{k,\lambda}+b_{10}E(0,j)_{k,\lambda+1}+b_{01}E(0,j)_{k+1,\lambda})$

By our inductive hypothesis on $l$, $E(0,j)_{k,\lambda}=0$ and
$E(0,j)_{k+1,\lambda}=0$, and by our inductive hypothesis on $k$,
$E(0,j)_{k,\lambda+1}=0.$ Thus,

$E(0,j)_{k+1,\lambda+1}=-\dfrac{1}{b_{00}}\left(b_{11}(0)+b_{10}(0)+b_{01}(0)\right)=0$

.

Similarly, assume by induction on $k<0$ that $E(0,j)_{k,\lambda+1}=0$. We want
to show that $E(0,j)_{k-1,\lambda+1}=0.$ By our recurrence, we have

$E(0,j)_{k-1,\lambda+1}=-\dfrac{1}{b_{10}}(b_{11}E(0,j)_{k-1,\lambda}+b_{00}E(0,j)_{k,\lambda+1}+b_{01}E(0,j)_{k,\lambda})$

By our inductive hypothesis on $l$, $E(0,j)_{k,\lambda}=0$ and
$E(0,j)_{k-1,\lambda}=0$, and by our inductive hypothesis on $k$,
$E(0,j)_{k,\lambda+1}=0.$ Thus,

$E(0,j)_{k-1,\lambda+1}=-\dfrac{1}{b_{1,0}}(b_{1,1}(0)+b_{0,0}(0)+b_{0,1}(0))=0$

.

Therefore for $j>0$, $E(0,j)_{k,l}=0$ for all $l<j$. ∎

######  Theorem 5.

Let $\alpha$ be an initial conditions layout and let

$B=\sum_{(i,j)\in\alpha}a_{i,j}E(i,j)=\left(b_{k,l}\right),$

where $a_{i,j}\in\mathbb{F}$. There are only a finite number of $E(i,j)$ that
contribute nonzero entries to each $b_{k,l}$.

######  Theorem 6.

Let $B=(b_{i,j})$ be an $(m+1)\times(n+1)$ overlay and $E(i,j)$ be basis
arrays built from the overlay applied to initial conditions defined as
follows: for $(k,l)$ in the initial conditions layout $\gamma$,

$E(i,j)_{k,l}=\begin{cases}1&\text{if }k=i\text{ and }l=j\\\
0&otherwise.\end{cases}$

For $(i,j)\in\gamma$,
Case 1: If $j\geq m,$ then $E(i,j)_{k,l}=0$ for $l<j$.
Case 2: If $j<0,$ then $E(i,j)_{k,l}=0$ for $l>j$.
Case 3: If $i\geq n,$ then $E(i,j)_{k,l}=0$ for $k<i$.
Case 4: If $i<0,$ then $E(i,j)_{k,l}=0$ for $k>i$.

###### Proof.

Case 1: $j\geq m$. Without loss of generality, take $\gamma$ to be the
standard initial conditions layout. Then $E(0,j)_{\alpha,0}=0$ for all
$\alpha$ and $E(0,j)_{0,\beta}=0$ for all $\beta\neq j$ by the initial
conditions. We will show $E(i,j)_{k,l}=0$ for $l<j$ by induction on $l$. $l=0$
is given from the initial conditions, so assume that $E(0,j)_{k,l}=0$ for all
$l$ such that $0\leq l\leq\lambda<j-1$. We want to show this holds for
$l=\lambda+1$.

We know $E(0,j)_{0,\lambda+1}=0$ by the initial conditions, so assume by
induction on $k>0$ that $E(0,j)_{k,\lambda+1}=0$. We want to show that
$E(0,j)_{k+1,\lambda+1}=0.$ By our recurrence, we have

$E(0,j)_{k+1,\lambda+1}=-\dfrac{1}{b_{00}}(b_{11}E(0,j)_{k,\lambda}+b_{10}E(0,j)_{k,\lambda+1}+b_{01}E(0,j)_{k+1,\lambda})$

By our inductive hypothesis on $l$, $E(0,j)_{k,\lambda}=0$ and
$E(0,j)_{k+1,\lambda}=0$, and by our inductive hypothesis on $k$,
$E(0,j)_{k,\lambda+1}=0.$ Thus,

$E(0,j)_{k+1,\lambda+1}=-\dfrac{1}{b_{00}}\left(b_{11}(0)+b_{10}(0)+b_{01}(0)\right)=0$

.

Similarly, assume by induction on $k<0$ that $E(0,j)_{k,\lambda+1}=0$. We want
to show that $E(0,j)_{k-1,\lambda+1}=0.$ By our recurrence, we have

$E(0,j)_{k-1,\lambda+1}=-\dfrac{1}{b_{10}}(b_{11}E(0,j)_{k-1,\lambda}+b_{00}E(0,j)_{k,\lambda+1}+b_{01}E(0,j)_{k,\lambda})$

By our inductive hypothesis on $l$, $E(0,j)_{k,\lambda}=0$ and
$E(0,j)_{k-1,\lambda}=0$, and by our inductive hypothesis on $k$,
$E(0,j)_{k,\lambda+1}=0.$ Thus,

$E(0,j)_{k-1,\lambda+1}=-\dfrac{1}{b_{1,0}}(b_{1,1}(0)+b_{0,0}(0)+b_{0,1}(0))=0$

.

Therefore for $j>0$, $E(0,j)_{k,l}=0$ for all $l<j$. ∎

######  Lemma 7.

$A=\sum_{(i,j)\in\gamma}d_{i,j}E(i,j)$

where $d_{i,j}$ is the initial condition of the array $A$ in the $(i,j)$
position. Assuming that for any position $(r,c)$, there are finitely many
$E(i,j)_{r,c}$ that contribute nonzero values.

###### Proof.

Consider

$\left(\sum_{(i,j)\in\gamma}d_{i,j}E(i,j)\right)_{r,c}$

$\left(B\sum_{(i,j)\in\gamma}d_{i,j}E(i,j)\right)_{r,c}=\sum_{(i,j)\in\gamma}d_{i,j}B\left(E(i,j)\right)_{r,c}$

Since $E(i,j)$ is annihilated by $B$, then

$\left(\sum_{(i,j)\in\gamma}d_{i,j}B\left(E(i,j)\right)\right)_{r,c}=0$

.

## References

  * [1] Philippe Flajolet and Robert Sedgewick.  Analytic Combinatorics.  Cambridge Unversity Press, 2007.
  * [2] Herbert S. Wilf.  Generatingfunctionology.  Academic Press, 1990.