# Coagent Networks Revisited

###### Abstract.

This work is aiming to discuss and close some of the gaps in the literature on
models using options (and more generally coagents). Briefly surveying the
theory behind these models, it also aims to provide a unifying point of view
on the many diverse examples that fall under a same category called coagent
network. Motivated by the result of [10] on parameter sharing of options, we
revisit the theory of (a)synchronous Coagent Network [8] by generalizing the
result to the context where parameters are shared among the function
approximators of coagents. The proof is more intuitive and uses the concept of
execution paths in a coagent network. Theoretically, this informs us of some
necessary modifications to the algorithms found in the literature which make
them more mathematically accurate. It also allows us to introduce a new simple
option framework, Feedforward Option Network, which outperforms the previous
option models in time to convergence and stability in the famous nonstationary
Four Rooms task. In addition, a stabilization effect is observed in
hierarchical models which justify the unnecessity of the target network in
training such models. Finally, we publish our code which allows us to be
flexible in our experiments settings.

Modjtaba Shokrian Zini 1<EMAIL_ADDRESS>
Perimeter Institute for Theoretical Physics, Waterloo, Canada

Research Consultant, Microsoft

Mohammad Pedramfar 1<EMAIL_ADDRESS>

Matthew Riemer<EMAIL_ADDRESS>
Mila, Université de Montréal, Montreal, Canada

IBM Research, Yorktown Heights, NY

Miao Liu<EMAIL_ADDRESS>
1Equal contribution

IBM Research, Yorktown Heights, NY

###### Contents

  1. 1 Coagent Network
    1. 1.1 Definition
    2. 1.2 Policy gradient theorem
  2. 2 Examples of Coagent Networks
    1. 2.1 Hierarchical Option Critic
      1. 2.1.1 Conventions and notations
      2. 2.1.2 A review on the HOC execution
      3. 2.1.3 Graph of HOC as a coagent network
      4. 2.1.4 A review on the HOC policy gradient theorem
    2. 2.2 Feedforward Option Network (FON)
    3. 2.3 Options of Interest
    4. 2.4 Stochastic Neural Nets
  3. 3 Non-examples of Coagent Network
    1. 3.1 Attention Option-Critic (AOC)
    2. 3.2 Hierarchical Actor-Critic (HAC)
  4. 4 Algorithm and Experiments
    1. 4.1 Algorithm
      1. 4.1.1 Update only on arrival and its runtime advantage
      2. 4.1.2 Incorrect termination function update in the literature
      3. 4.1.3 Using the not-terminated option for action value estimate
      4. 4.1.4 Not computing the discounted probability for policy updates
    2. 4.2 Experiment: settings and results
      1. 4.2.1 Settings
      2. 4.2.2 Analysis and comparison of HOC results
      3. 4.2.3 Analysis and comparison of FON results
      4. 4.2.4 Hyperparameters
    3. 4.3 Option length and termination temperature
      1. 4.3.1 Option length and prior solutions to early termination
      2. 4.3.2 Tuning the termination temperature
      3. 4.3.3 Using only parents for critics target computation
      4. 4.3.4 Using only parents for termination update rule
      5. 4.3.5 $\left<1,\ldots,1\right>$ and $\left<1,2,\ldots,2\right>$ FON models with low temperature
    4. 4.4 Stability in the long term for nonstationary tasks
      1. 4.4.1 Comparison of $\left<1,\ldots,1\right>$ and $\left<1,2,\ldots,2\right>$ FON models in long runs
    5. 4.5 Non-linear models
  5. 5 Conclusion and Future Works
  6. A Hierarchical Option Critic
    1. A.1 Bellman equations
    2. A.2 Policy gradient theorem
  7. B Coagent Network
    1. B.1 More details on examples of Coagent Networks
      1. B.1.1 (A)Synchronous Coagent Network
      2. B.1.2 HOC
      3. B.1.3 Feedforward Option Network

## Introduction

The main question after constructing a Hierarchical Reinforcement Learning
(HRL) model is how to train the model, for which policy gradient theorems has
been the primary tool. In this paper, we take a step in deriving the policy
gradient theorem in the most general context.

In the first section, we discuss the notion of a Coagent Network and write the
policy gradient theorem. Then we review examples of coagent networks found in
the literature and show how to apply our theorem. We also mention some
important non-examples which help to understand the crucial aspects of coagent
networks. HRL has been studied through different approaches. Recently, the so-
called option [13] approach has attracted some renewed attention [1, 11, 10].
Our experiments will involve these models. In fact, we find improvements in
some of the experiments in the literature using a more mathematical algorithm.
We fill in the details of the previous sections and theorems in the Appendix.

Lastly, our code can be found online 555https://github.com/mojishoki/Coagent-
Networks-Revisited. It allows one to easily build hierarchical option models
with different configurations, such as arbitrary number of hierarchies,
different connection patterns (tree-like or feedforward) between levels of
hierarchy, arbitrary number of options at each level and the use of different
learning algorithms and neural networks for each option.

Preliminaries. We refer to [12] for background on reinforcement learning. We
will study policies acting in a setting described by a finite Markov Decision
Process (MDP) : A tuple
$(\mathcal{S},\\{\mathcal{A}_{s}\\}_{s\in\mathcal{S}},R,P,\gamma)$ where
$\mathcal{S}$ is the finite set of states, and $\mathcal{A}_{s}$ is the finite
set of actions $a\in\mathcal{A}_{s}$ available at state $s$. The reward
function for a transition $(s,a,s^{\prime})$ is defined as
$R:(s,a,s^{\prime})\to r\in\mathbb{R}$, the discount factor is denoted by
$\gamma\in[0,1]$, and $P:(s,a)\to\textit{Dist}(\mathcal{S})$ is the transition
function.

In the problems we will consider, each state contains not only information
about the environment but also information about the state of the agent $\pi$,
describing something internal to the agent that is relevant to its execution.
Thus, we will use the subscript $\pi$ in $\mathcal{S}_{\pi}$ to denote this
augmented set of states. Sometimes we will also use $\mathcal{S}_{env}$ to
explicitly talk about only states of the environment. In both cases, the exact
definition will be dependent on the context. For this part, we will simply use
$\mathcal{S}$. Further, a subset $\mathcal{S}_{init}\subset\mathcal{S}$ is
defined as the subset of possible initial states.

At each time-step $t$, the agent/policy
$\pi:s\in\mathcal{S}\to\textit{Dist}(\mathcal{A}_{s})$ acts on a state
$s_{t}\in\mathcal{S}$ and an action $a_{t}\in\mathcal{A}_{s_{t}}$ is picked
from the distribution $\pi(s_{t})$ on $\mathcal{A}_{s_{t}}$ with probability
$\pi(a_{t}|s_{t})$. Notice the agent's action only depends on $s_{t}$ and not
on the history of states, hence $\pi$ satisfies the Markov property.

After taking the action, the agent enters the state $s_{t+1}$ with probability
$P(s_{t+1}|s_{t},a_{t})$ and receives the reward $R(s_{t},a_{t},s_{t+1})$. We
define

  * •

the expected return of $\pi$ as
$J_{\pi}=E_{\pi,\mathcal{S}_{init}}[\sum_{t=0}^{\infty}\gamma^{t}r_{t}]$,

  * •

the value function of $\pi$ as
$V_{\pi}(s_{0}):=E_{\pi}[\sum_{t=0}^{\infty}\gamma^{t}r_{t}|s_{0}]$ which is
the expected return given initial state $s_{0}\in\mathcal{S}_{init}$,

  * •

and the action-value function of $\pi$ as
$Q_{\pi}(s,a):=E_{\pi}[\sum_{t=0}^{\infty}\gamma^{t}r_{t}|(s_{0},a_{0})]$
which is the expected reward given initial state-action pair $(s_{0},a_{0})$.

On-policy algorithms are one of the main class of algorithms used in
reinforcement learning to learn the policy with the highest expected return.
Assume we want to train the parameters $\theta$ describing $\pi$. On-policy
algorithms use gradient ascent following the formula of the policy gradient
which refers to $\mbox{\boldmath$\nabla$}_{\theta}J_{\pi}$ and can be written
as:

(1)
$\displaystyle\mbox{\boldmath$\nabla$}_{\theta}J_{\pi}=\sum_{s_{0}}d(s_{0})\sum_{s\in\mathcal{S}}d(s|s_{0})\sum_{a\in\mathcal{A}_{s}}\frac{d\pi}{d\theta}(a|s)Q_{\pi}(s,a).$

Here, $d(s_{0})$ is the initial distribution for state
$s_{0}\in\mathcal{S}_{init}$ and $d(s|s_{0})$ is the discounted probability of
reaching state $s$ from $s_{0}$, meaning

(2) $\displaystyle
d(s|s_{0})=\sum_{l=1}^{\infty}\sum_{\begin{subarray}{c}(s_{0},\ldots,s_{l})\\\
s_{l}=s\end{subarray}}\sum_{i=0}^{l-1}\gamma^{i}P_{\pi,\mathcal{S}}(s_{i+1}|s_{i}),$

where $P_{\pi,\mathcal{S}}(s_{i+1}|s_{i})$ is the transition probability of
$s_{i}$ to $s_{i+1}$ given policy $\pi$ and transition function $P$ of
$\mathcal{S}$.

##  1\. Coagent Network

###  1.1. Definition

We study an agent $\Pi$ composed of a network of Markov policies $\pi_{o}$,
also called coagents, where at each time-step, rules set by the user determine
the sequence of policies $(\pi_{o_{1}},\ldots,\pi_{o_{k}})$ that act. Perhaps
the easiest way to think about a coagent network like $\Pi$ is a stochastic
policy which can be broken down to a series of smaller stochastic policies.
Formalizing this can be a bit tedious (see e.g. [8] for the definition of
Synchronous Coagent Network), and we try to present a succinct definition of
$\Pi$.

######  Definition 1.

Let $\Pi$ be a Markov policy with state space $\mathcal{S}_{\Pi}$ and action
space $\mathcal{A}_{x}$ for $x\in\mathcal{S}_{\Pi}$. Let
$\mathcal{C}_{\Pi}=\\{\pi_{o}\\}_{o\in\mathcal{O}_{\Pi}}$, where $\pi_{o}$ are
markov policies, indexed with a set of nodes $\mathcal{O}_{\Pi}$, with state
and action space $\mathcal{S}_{o},\mathcal{A}_{x_{o}}$ for
$x_{o}\in\mathcal{S}_{o}$. $\Pi$ is a Markov single reward coagent network
with coagent set $\mathcal{C}_{\Pi}$ if

  * •

Every state $x\in\mathcal{S}_{\Pi}$ uniquely determines a coagent
$\pi_{o_{1}}\in\mathcal{C}_{\Pi}$ with state
$x_{o_{1}}\in\mathcal{S}_{o_{1}}$, which will be the first coagent in a
sequence that will define the action of $\Pi$.

  * •

This sequence is generated using a rule $\Delta$. This is inherent to the
model (designed by the user and not influenced by the parameters), and
determines the next acting coagent, along with its input state, using the
state and action of the previous coagent:

(3) $\displaystyle\Delta:(x_{o},u_{o})\to(o^{\prime},x_{o^{\prime}}),\ \
x_{o^{\prime}}\in\mathcal{S}_{o^{\prime}}.$

This rule can be stochastic if $o$ is the last coagent that performs a
primitive action within a stochastic environment. Primitive actions are those
that change the state of the environment. In that case, $x_{o^{\prime}}$ may
not be deterministically determined. Moreover, $\Delta$ can also be stochastic
in the selection of the next coagent $o^{\prime}$. For simplicity, we shall
assume that the only way in which $\Delta$ is stochastic is the former, and
there is no randomness in the selection of $o^{\prime}$.

  * •

Eventually, after finitely many applications of $\Delta$, a coagent applies a
primitive action $a$ that leads to the next state
$x^{\prime}\in\mathcal{S}_{\Pi}$. Note this does not mean that the last
coagent's action is exactly $a$, as it could contain additional information
necessary for the next execution of $\Pi$.

#### Actions of $\Pi$: Execution paths

One may see the action of $\Pi$ as being simply $a$ and that would ultimately
lead to the policy gradient in (1). So let us be more precise:

######  Definition 2.

Each action of $\Pi$ is an execution path
$P=((x_{o_{i}},u_{o_{i}}))_{i=1}^{k}$ where $k$ coagents $\pi_{o_{i}}$ act to
produce a primitive action $a$, with the last action $u_{o_{k}}$ containing
that information.

From the point of view of the environment, only the primitive action matters,
but to derive a more useful policy gradient we will need to distinguish
$Q_{\Pi}(x,a)$ and $Q_{\Pi}(x,P)$ as the former does not inform us of the
status of the agent $\Pi$ while executing $a$, while the latter does so by
providing $(x_{o_{k}},u_{o_{k}})$. Hence, we can compute $Q_{\Pi}(x,a)$ as
$E_{P:u_{o_{k}}\text{leading to }a}[Q_{\Pi}(x,P)]$.

#### Computing reward for $\pi_{o}$

Assume that $\pi_{o}$ acts on $x_{o}^{(0)}$ by $u_{o}$ and only acts again at
$x_{o}^{(l)}$, meaning after $\Pi$ has gone through $l$ many execution paths.
The transition tuple for $\pi_{o}$ is defined as
$(x_{o}^{(0)},u_{o},x_{o}^{(l)})$.

The cumulative reward for $\Pi$ is computed by using a discount factor
$\gamma$ and the rewards $r\in\mathbb{R}$ of each of $\Pi$ transition given by
a function $R:(x,a,x^{\prime})\to r$. More interestingly, we can use $R$ to
uniquely define the reward functions for all coagents transitions as well.

Let us assume that the states and primitive actions for $\Pi$ in the time
interval associated to $\pi_{o}$ transition $(x_{o}^{(0)},u_{o},x_{o}^{(l)})$
were $(x^{(i)},a^{(i)})_{i=0}^{l-1}$. The reward $R_{o}$ for the transition
$(x_{o}^{(0)},u_{o},x_{o}^{(l)})$ is

(4) $\displaystyle
R_{o}(x_{o}^{(0)},u_{o},x_{o}^{(l)}):=\sum_{i=0}^{l-1}r_{i}\gamma^{i},\ \
\text{where }r_{i}=R(x^{(i)},a^{(i)},x^{(i+1)}).$

Notice that if $\pi_{o}$ is never reactivated (i.e. $l=\infty$), then the
reward corresponding to $(x_{o}^{(0)},u_{o})$ is an infinite sum.

######  Remark 1.

The reward source of all coagents is the same $R$, hence the name single
reward in our definition. We will show why this assumption is necessary, in
the proof of 1.1 and Remark 5.

Convention. Throughout this text, we will use coagent network (CN) to refer to
a Markov single reward coagent network. Also, the term ``Markov'' can be
dropped as shown later in Remark 12.

######  Remark 2.

Generally, $x$ itself contains the information regarding the state of the
environment and the state of the agent, such as which coagent should pick up
the environment state and start the execution. Also, each
$x_{o}\in\mathcal{S}_{\pi_{o}}$ contains some information regarding the
original state $x\in\mathcal{S}_{\Pi}$ and some information that may have been
received from the previous coagents in the execution path.

######  Remark 3.

For the examples of CNs in this text, only a high-level description of
$\Delta$ and the state spaces will be given, as the detailed abstract formulae
do not add much to the understanding of the model. As alluded to in the
beginning, the picture to have in mind of such models is a network of
stochastic policies which process some information and pass it to each other
until a final decision is made. The model and the next theorem, apply to any
agent which decision making process can be broken down to a set of stochastic
policies sharing a single reward source.

Since we use the terminology of coagent network and execution path and nodes
($\mathcal{O}_{\Pi}$), it is natural to define a directed graph representation
for the model when possible.

######  Definition 3.

The graph of a CN $\Pi$ is a graph with vertex set $\mathcal{O}_{\Pi}$ and
directed edges which show which coagent could follow the next in some
execution path.

######  Remark 4.

Notice a loop in a graph simply means that the coagent can act multiple times
in a row. Furthermore, following the last statement in the previous remark,
one can start with the most refined decomposition of $\Pi$ into stochastic
policies and its corresponding graph, and contract any edge to combine any two
coagents into a bigger one to derive different graph representations. Of
course, the policy gradient will not change as it should not since the agent
$\Pi$ has not changed; indeed, the policy gradient for the new composite
coagent decomposes to the sum of the two original ones. For a concrete
example, we refer to HOC in 2.1.3, where there are two different graph
representations related by the contraction of edges.

###  1.2. Policy gradient theorem

Let $\mbox{\boldmath$\nabla$}J_{\Pi}$ be the policy gradient for $\Pi$. The
agent is dependent on parameters $\theta$ which can be shared between
coagents. Recall the policy gradient (1) for an agent $\Pi$ can always be
written as

(5)
$\displaystyle\mbox{\boldmath$\nabla$}J_{\Pi}=\sum_{x_{0}\in\mathcal{S}_{\Pi,init}}d(x_{0})\sum_{x\in\mathcal{S}_{\Pi}}d(x|x_{0})\sum_{P\in\mathcal{A}_{x}}\frac{d\Pi}{d\theta}(P|x)Q_{\Pi}(x,P).$

where $d(x_{0})$ is the initial distribution for state
$x_{0}\in\mathcal{S}_{\Pi,init}\subset\mathcal{S}_{\Pi}$ and $d(x|x_{0})$ is
the discounted probability of reaching state $x$ from $x_{0}$. Here, actions
are viewed as execution paths $P=((x_{o_{i}},u_{o_{i}}))_{i=1}^{k}$ of length
$k$ inside the network and the last action $u_{o_{k}}$ implies a primitive
action.

######  Theorem 1.1.

The policy gradient of $\Pi$

(6)
$\displaystyle\mbox{\boldmath$\nabla$}J_{\Pi}=\sum_{x_{0}\in\mathcal{S}_{\Pi,init}}d(x_{0})\sum_{x\in\mathcal{S}_{\Pi}}d(x|x_{0})\sum_{P\in\mathcal{A}_{x}}\frac{d\Pi}{d\theta}(P|x)Q_{\Pi}(x,P)$

can be rewritten as the sum of the policy gradient for the coagents:

(7)
$\displaystyle\boxed{\sum_{x_{0}\in\mathcal{S}_{\Pi,init}}d(x_{0})\sum_{o}\sum_{x\in
S_{\Pi},x_{o}\in\mathcal{S}_{\pi_{o}}}d(x_{o},x|x_{0})\sum_{u_{o}\in\mathcal{A}_{x_{o}}}\frac{d\pi_{o}}{d\theta}(u_{o}|x_{o})Q_{\pi_{o}}(x_{o},u_{o})}.$

Here, $d(x_{o},x|x_{0})$ is the discounted probability of reaching state $x$
from $x_{0}$, i.e. $d(x|x_{0})$, multiplied by the probability of reaching
$x_{o}$ from $x$ within a single execution path.

###### Proof.

Clearly, $\Pi(P|x)=\prod_{o\in P}\pi_{o}(u_{o}|x_{o})$ where $o\in P$ means
every coagent $o_{i},1\leq i\leq k$. We use this to rewrite (6):

(8)
$\displaystyle\sum_{x_{0}\in\mathcal{S}_{\Pi,init}}d(x_{0})\sum_{x\in\mathcal{S}_{\Pi}}d(x|x_{0})\sum_{P\in\mathcal{A}_{x}}\frac{d}{d\theta}\Big{(}\prod_{o\in
P}\pi_{o}(u_{o}|x_{o})\Big{)}Q_{\Pi}(x,P).$

Distributing the derivative over the product leads to

(9) $\displaystyle\sum_{o}\Big{(}\prod_{o^{\prime}\in
P_{<o}}\pi_{o^{\prime}}(u_{o^{\prime}}|x_{o^{\prime}})\Big{)}\frac{d\pi_{o}}{d\theta}(u_{o}|x_{o})\Big{(}\prod_{o^{\prime}\in
P_{>o}}\pi_{o^{\prime}}(u_{o^{\prime}}|x_{o^{\prime}})\Big{)},$

where $P_{<o},P_{>o}$ are the parts of the path before and after $o$. The
product on the left over all coagents in $P_{<o}$, summed over all possible
$P_{<o}$ paths leading to $x_{o}$, gets absorbed by $d(x|x_{0})$ and gives us
$d(x,x_{o}|x_{0})$; this is the multiplicative factor mentioned in the
statement that differentiates $d(x,x_{o}|x_{0})$ from $d(x|x_{0})$.

On the other hand, for the term $P_{>o}$ on the right, summed over all
possible $P_{>o}$ paths with state-action $(x_{o},u_{o})$ for $o$, gets
absorbed by $Q_{\Pi}(x,P)$ and gives $Q_{\pi_{o}}(x_{o},u_{o})$. This is
derived by using a Bellman-type equation relating the action value of
$\pi_{o}$ to the action value of the next coagent in the execution path:

(10) $\displaystyle
Q_{\pi_{o}}(x_{o},u_{o})=\sum_{u_{o^{\prime}}}\pi_{o^{\prime}}(u_{o^{\prime}}|x_{o^{\prime}})Q_{\pi_{o^{\prime}}}(x_{o^{\prime}},u_{o^{\prime}}),$

where $o^{\prime}$ is the next coagent according to the rule $\Delta$
(assuming for simplicity that the next state $x_{o^{\prime}}$ is
deterministic). Applied iteratively, this gives:

(11) $\displaystyle Q_{\pi_{o}}(x_{o},u_{o})=\sum_{P_{>o}}\prod_{o^{\prime}\in
P_{>o}}\pi_{o^{\prime}}(u_{o^{\prime}}|x_{o^{\prime}})Q_{\pi_{l_{P_{>o}}}}(x_{l_{P_{>o}}},u_{l_{P_{>o}}}),$

where the summation is over all execution paths $P$ that involve
$(x_{o},u_{o})$, and $l_{P_{>o}}$ is the index of the last coagent in $P_{>o}$
which action immediately leads to a primitive action $a$, thus
$Q_{\pi_{l_{P_{>o}}}}(x_{l_{P_{>o}}},u_{l_{P_{>o}}})=Q_{\Pi}(x,P)$.

Note that summing over both parts independently while having
$\frac{d\pi_{o}}{d\theta}(u_{o}|x_{o})$ fixed was possible, due to the Markov
assumption on coagents. In other words, when the term
$\frac{d\pi_{o}}{d\theta}(u_{o}|x_{o})$ is fixed and both sides are summed
over independently, one is implicitly assuming that what has happened before
and what happens after $\pi_{o}$ execution, given $(x_{o},u_{o})$, are
completely independent. ∎

######  Remark 5.

Consider the case where the reward source for each $\pi_{o}$ is dependent on
$o$ (and not just on $R$). This case is called pseudo or intrinsic reward, of
which there are many kinds in the literature (see 3.2). This makes it
impossible in general to derive the Bellman equations in a meaningful way as
one has to compare/combine the many kinds of rewards $R_{o}$, especially when
relating $Q_{\Pi}$ to $Q_{\pi_{o}}$ as done in the proof in (10,11).
Therefore, our main result does not apply to these settings.

We refer to Appendix B for more on the policy gradient
$\mbox{\boldmath$\nabla$}J$ and some general remarks on CNs.

##  2\. Examples of Coagent Networks

###  2.1. Hierarchical Option Critic

####  2.1.1. Conventions and notations

We refer to [10, and references therein] for a survey of HOC. Here, we need to
use new notations that we believe are more helpful to see HOC as a CN. An HOC
has $N$ levels of hierarchy with $\pi^{1}$, sitting at the first level of
hierarchy, as the most abstract option and selecting the first option $o^{1}$
with probability $\pi^{1}(o^{1}|s)$ given a state $s$.

We would like to view HOC as a tree of options, where each non-leaf option has
equally many children, say $M$. An option is equipped with a policy $\pi$
which selects a child and a termination function $\beta$. Each option is
uniquely determined by an ``address'', a sequence
$o^{1:j}=(o^{1},\ldots,o^{j})$ where $o^{i}\in\\{1,\ldots,M\\}$, and $0\leq
j\leq N-1$ with the most abstract option (also called the root) labelled by
$o^{1:0}:=o^{0}$. Therefore an option with label $o^{1:j}$, sitting at the
$j+1$ level of hierarchy, has a policy
$\pi_{o^{1:j}}:=\pi^{j+1}(\cdot|s,o^{1:j})$ which selects a child $o^{1:j+1}$
with probability $\pi^{j+1}(o^{j+1}|s,o^{1:j})$ and termination function
$\beta_{o^{1:j}}:=\beta_{j}(s,o^{1:j})$ which decides to terminate with
probability $\beta_{j}((s,o^{1:j}),1)$ and to not terminate with probability
$\beta_{j}((s,o^{1:j}),0):=1-\beta_{j}((s,o^{1:j}),1)$. We will abuse notation
and denote $\beta_{j}((s,o^{1:j}),1)$ by $\beta_{j}(s,o^{1:j})$. Finally, a
node in this tree is another name for an option.

######  Remark 6.

Here we have given a rough picture of the graph representation of HOC, with
the more accurate one given in 2.1.3.

As is observed in the options framework, instead of considering the states of
the environment $s\in\mathcal{S}_{env}$ alone, it is better to consider the
states of the environment and the agent in our state description.

Let us denote the HOC policy by $\Pi$. The states, forming the set
$\mathcal{S}_{\Pi}$, are tuples of the form $(s,o^{1:i},d)$ or
$(s,o^{1:i},u)$. The third component $d$ or $u$ is called the execution mode
of the state and

  * •

$(s,o^{1:i},d)$ means the state of the environment is $s$, and the algorithm
is about to execute the policy of option $o^{1:i}$ on $s$. The $d$ stands for
downward execution. At the beginning, the algorithm is in the state
$(s,o^{0},d)$. This means the environment state is $s\in\mathcal{S}_{env}$,
and the root is about to select an option.

  * •

$(s,o^{1:i},u)$ means the state of the environment is $s$, and the algorithm
is about to decide whether $s$ is a termination state for option $o^{1:i}$. It
will be a termination state with probability $\beta_{i}(s,o^{1:i})$. The
letter $u$ stands for upward execution.

Let $s_{o,i,d}:=(s,o^{1:i},d),s_{o,i,u}:=(s,o^{1:i},u)\in\mathcal{S}_{\Pi}$
for the set of states. Notice that although ``$1:$'' is dropped in the
subscript index, the option $o^{1:i}$ is still meant in subscript. When given
to a policy $\pi^{i}(o^{i}|s_{o,i-1})$, the execution mode $d$ is suppressed,
as is the case for the termination function $\beta_{i}(s_{o,i})$ and execution
mode $u$.

####  2.1.2. A review on the HOC execution

We review how HOC functions using the above notations. Starting from the root
option policy $\pi^{1}$, each node chooses a lower level node, i.e. we move
from $s_{o,j,d}\to s_{o,j+1,d}$, until we reach $s_{o,N-1,d}$. At this level,
the node $o^{1:N-1}$ selects a primitive action $o^{N}$ with policy
$\pi^{N}(\cdot|s_{o,N-1})$, which leads us to $s_{o,N,d}$, where $o^{N}$ is
some primitive action. Right afterwards, the environment state changes to
$s^{\prime}$ with some transition probability, and the upward execution mode
is initiated, i.e. $s^{\prime}_{o,N-1,u}$ where $u$ refers to upward. In this
phase of execution, the termination functions enter the picture. Starting from
$\beta_{N-1}(s^{\prime}_{o,N-1})$, the nodes that have been selected along the
previous path (determined by the address $o^{1:N-1}$) decide whether to
terminate or not, in reverse order. This means if a node is terminated, the
termination function of the higher level node (parent) is called. Therefore,
starting at $s^{\prime}_{o,N-1,u}$, the state moves from
$s^{\prime}_{o,j+1,u}\to s^{\prime}_{o,j,u}$ if termination (with probability
$\beta_{j+1}(s_{o,j+1})$) is decided. This continues up to some level $l+1$,
where node $o^{1:l}$ decides to not terminate (with probability
$1-\beta_{l}(s_{o,l})$). Note $l$ may be zero, which means the root has been
called back (and the root never terminates). Therefore, the execution mode of
$s^{\prime}_{o,l,u}$ has to change to $d$, i.e. $s^{\prime}_{o,l,u}\to
s^{\prime}_{o,l,d}$. The policy of the option $o^{1:l}$ then selects a new
option $o^{\prime l+1}$, and the downward execution culminates into a possibly
new set of options, until the bottom of the tree is reached at some node
$o^{\prime 1:N-1}$ with $o^{\prime 1:l}=o^{1:l}$ and state
$s^{\prime}_{o^{\prime},N-1,d}$.

What was described above was essentially the rule $\Delta$ of HOC as a CN.
Therefore, with the exception of the very first execution of the model, where
the root starts and a primitive action is applied by a leaf node, the actions
of $\Pi$ or execution paths (Definition 2) are paths with two phases. The
first from the bottom of the tree to some level upward and the second downward
to the bottom.

######  Remark 7.

As discussed above, an execution path in HOC changes the environment state at
the beginning as the first option is a leaf option. This is inconsistent with
the Definition 2 and to apply our Theorem 1.1, the execution path needs to end
at a primitive action. This means an execution path should start at
$s_{o,N-1,u}$ and end at $s^{\prime}_{o,N-1,u}$. However, this is a simple
technicality that is resolved easily (see B.1.2).

####  2.1.3. Graph of HOC as a coagent network

For an option $o^{1:l}$, we have two coagents $\pi^{l+1}(\cdot|s_{o,l})$ and
$\beta_{l}(s_{o,l})$. Consider the case of $N=3$ with each option having two
children ($M=2$). This means $o^{i}\in\\{1,2\\}$ and an option address is a
sequence of $1$ and $2$. For example, $o^{1:2}=(1,2)$ is representing a bottom
level (third level) option $o=(o^{1}=1,o^{2}=2)$, and given a state
$s_{o,2,d}$, we act by $\pi^{3}(a|s_{o,2}),a\in\\{\text{primitive
actions}\\}$, while given a state $s_{o,2,u}$, we act by
$\beta_{2}(b|s_{o,2})$, where
$b\in\\{0=\text{continue},1=\text{termination}\\}$.

$\beta_{(11)}$$\beta_{(12)}$$\beta_{(21)}$$\beta_{(22)}$$\beta_{(1)}$$\beta_{(2)}$$\beta_{()}$$\pi_{(11)}$$\pi_{(12)}$$\pi_{(21)}$$\pi_{(22)}$$\pi_{(1)}$$\pi_{(2)}$$\pi_{()}$
Figure 1. A graph representing the coagent network of HOC with $N=3$ and
$M=2$. The policy and termination function of an option each form a coagent.
Nodes are labelled by their unique address and type (policy or termination).
The termination functions send an edge to their corresponding policies. The
policies of the leaf nodes are also followed by their corresponding
termination after applying a primitive action.

We can view the options as a full binary tree with depth three. The CN can be
viewed as two such binary trees (Figure 1) where on one we have the policies
and on the other the termination functions. The corresponding vertices on
these two binary trees are connected, where directed edges in this graph mean
that a coagent can be followed by another in an execution path. The edges on
the policy subgraph go downwards while the ones on the termination subgraph go
upwards. The edges connecting the termination graph to the policy graph are
directed towards the policy vertices. As the policies of the leaf nodes act by
primitive action and change the execution mode to $u$, they are followed by
the corresponding termination function. Therefore, there is also a directed
edge from each of the policies of the leaf nodes to the corresponding
termination.

######  Remark 8.

It is possible to define the CN differently by taking the policy and
termination function corresponding to an option $o^{1:j}$ as a single coagent
$\kappa_{o^{1:j}}$ (Figure 2). This coagent will act as
$\pi^{j+1}(\cdot|s_{o,j})$ when given a state with execution mode $d$, and act
as the termination function $\beta_{j}(s_{o,j})$ given a state with execution
mode $u$. In this case, the graph of the CN is a tree where each edge is
doubled, with one edge going up and another going down, and each vertex has a
loop. Notice this graph is a contraction of the previous graph along the edges
connecting the two copies of the binary tree.

$(11)$$(12)$$(21)$$(22)$$(1)$$(2)$$()$ Figure 2. A graph representing the
coagent network of HOC with $N=3$ and $M=2$. The policy and termination
function of each option form a single coagent. Nodes are labelled by their
unique address.

####  2.1.4. A review on the HOC policy gradient theorem

We rewrite the HOC policy gradient theorem (HOCPGT):

######  Theorem 2.1.

$\frac{dQ}{d\theta}((s_{0})_{o_{0},N-1,d})=$

(12)
$\displaystyle\sum_{s,o^{1:N-1},s^{\prime}}\mu(s^{\prime},s_{o,N-1,d}|(s_{0})_{o_{0},N-1,d})\Big{[}\sum_{o^{N}}\frac{d\pi^{N}}{d\theta}(o^{N}|s_{o,N-1})Q(s_{o,N-1,d},o^{N})$
(13)
$\displaystyle-\gamma\sum_{l=1}^{N-1}\Big{(}\prod_{k=l+1}^{N-1}\beta_{k}(s^{\prime}_{o,k})\Big{)}\frac{d\beta_{l}}{d\theta}(s^{\prime}_{o,l})(Q_{\beta_{l}}(s_{o,l},0)-Q_{\beta_{l}}(s_{o,l},1))$
(14)
$\displaystyle+\gamma\sum_{j=0}^{N-1}\Big{(}\prod_{k=j}^{N-1}\beta_{k}(s^{\prime}_{o,k})\Big{)}\sum_{o^{\prime
1:j}}P_{\beta,\pi}(s^{\prime}_{o^{\prime},j-1,d}|s^{\prime}_{o,j-1,u})\frac{d\pi^{j}}{d\theta}(o^{\prime
j}|s^{\prime}_{o^{\prime},j-1})Q(s^{\prime}_{o^{\prime},j-1,d},o^{\prime
j})\Big{]}$

The proof that this rewrite is equivalent to [10, Theorem 1] is given in the
Appendix (A.1, A.2). There are a few notations that need to be defined:

  * •

$\mu(s_{o,N-1,d},s^{\prime}|(s_{0})_{o_{0},N-1,d})$ is the discounted
probability of starting at $(s_{0})_{o_{0},N-1,d}$, reaching the state
$s_{o,N-1,d}$, which after $\pi^{N}$ execution is followed by
$s^{\prime}_{o,N-1,u}$.

  * •

$P_{\beta,\pi}(s^{\prime}_{o^{\prime},j-1,d}|s^{\prime}_{o,j-1,u})$ is the
transition probability from $s^{\prime}_{o,j-1,u}$ to
$s^{\prime}_{o^{\prime},j-1,d}$, which is dependent on the termination
functions $\beta$ and policies $\pi$. It is the probability of the algorithm
reaching $s^{\prime}_{o^{\prime},j-1,d}$ at level $j$, after finishing its
upward phase of execution (which started at the same level at
$s^{\prime}_{o,j-1,u}$) and coming down again to level $j$ (see (25) in the
appendix for the computations).

  * •

$Q_{\beta_{l}}(s_{o,l},0),Q_{\beta_{l}}(s_{o,l},1)$ are the action value
functions of $\beta_{l}$ for option $o^{1:l}$ at $s_{o,l}$. Action $1$ denotes
termination and $0$ denotes the opposite (see (36) in the appendix for the
computations).

As shown in equations (42-48) in the appendix, we can interpret the above sum
as the sum of the policy gradients of $\pi^{j}$ and $\beta_{j}$ of the
options, as their similarity to the usual policy gradient
$\sum_{x}d(x|x_{0})\sum_{a}\frac{d\pi}{d\theta}(a|x)Q(x,a)$ in (1) can be
observed.

######  Remark 9.

We introduced many new notations for HOC which will be useful when writing the
algorithm. However, we often need to view HOC as a CN and use our notations in
CN to be brief in our equations which apply to all layers. In that case, we
will directly call an option $o^{1:i}$ by $o$, which means
$\pi_{o}(\cdot|s)=\pi^{i}(\cdot|s_{o,i})$ and
$\beta_{o}(s)=\beta_{i}(s_{o,i})$. In case we need to refer to the parent of
$o^{1:i}$, i.e. $o^{1:i-1}$, we will simply use $parent(o)$.

###  2.2. Feedforward Option Network (FON)

This is a new coagent network extensively used in our experiments. It is
similar to HOC in that we use options that have policies and termination
functions as coagents, but the graph is a feedforward network; every option at
each level of hierarchy is connected to all options at the higher and lower
level. The rules of execution are similar to that of HOC where every path of
execution is a path from lowest hierarchy to some level (where termination
stops), and from there back to the lowest level.

Let us denote by $\left<m_{1},m_{2},\ldots,m_{N}\right>$ an $N$ layer FON
where the $i$-th layer has $m_{i}$ many options. In all cases, there is a
single root, thus $m_{1}=1$. In our experiments, we tested configurations such
as $m_{i}=1,\forall i$, and $\left<1,2,\ldots,2\right>$.

The particular case of $\left<1,1,\ldots,1\right>$ is interesting. In terms of
performance, one might expect that it is not any better than $\left<1\right>$.
However, as explained in the Appendix B.1.3, assuming the coagents are trained
by standard on-policy Actor-Critic (AC) algorithm, each parent is effectively
acting as a value target network with rollout. In fact, one can see
$\left<1,1\right>$ as an Actor-Critic model (the child) which is soft-updated
using a value target network with rollout (the root) at a learnable rate
(determined by the termination function of the child). This also explains why
in many hierarchical networks, including for example the Hierarchical Actor-
Critic [9, section 7.6] which uses goals and an off-policy DDPG update, the
presence of a target network for the whole agent is unnecessary, as the agent
is somewhat stabilizing its learning by itself, or more precisely, inside the
agent, each coagent is stabilizing the learning of its children.

######  Remark 10.

Similar to HOC, we adopt a notation that will be useful to discuss facts about
both HOC and FON simultaneously. More precisely, the sequence $o^{1:i}$ used
to refer to a unique option (and option path from the root) in HOC can still
be used to refer to an option path in FON, if we enumerate options of the
$i$-th layer by $\\{1,\ldots,m_{i}\\}$, and let
$o^{j-1}\in\\{1,\ldots,m_{j}\\}$. Then $o^{1:i-1}=(o^{1},\ldots,o^{i-1})$ will
not only contain the information about which option the execution is at, i.e.
$o^{i-1}$, but also the parents $o^{j}$ ($j<i-1$) which are waiting to be
called back. Note that $o^{0}\in\\{1,\ldots,m_{1}\\}=\\{1\\}$ refers to the
root. Also note that the same Remark 9 applies to FON as well, where we will
directly use CN notations to describe equations that apply to all layers.

On the other hand, we shall also use $\left<m_{1},\ldots,m_{N}\right>$ for an
HOC model where each parent at layer $i$ has $m_{i+1}$ many children. As the
graph of this CN is a tree, we would have in total
$\sum_{j=1}^{N}\prod_{i=1}^{j}m_{i}$ many options. Furthermore, in all our HOC
experiments $m_{i}=2$ for all $i>1$. Finally, note the FON and HOC models for
$\left<1,\ldots,1\right>$ and $\left<1,m\right>$ are identical.

###  2.3. Options of Interest

One of the structures that one can add to the HOC is an interest function
$I_{\omega}$ for each option $\omega$ [6]. One interpretation of this function
is that it introduces a deterministic part in the process of the selection of
$\omega$ by its parent $\Omega$, which is unique to $\omega$ and disjoint from
the process of selection of the other children. This modularity has an effect
similar to attention which is the next example. We can still apply Theorem 1.1
if we simply consider combining the parent with the interest functions of its
children, i.e. the new coagent is
$\pi^{new}_{\Omega}(\omega|s)=I_{\omega}(s)\pi^{old}_{\Omega}(\omega|s)$. Then
Theorem 1.1 applied to $\\{\pi_{o}^{new},\beta_{o}\\}_{\text{options }o}$ will
give the same algorithm in [6].

###  2.4. Stochastic Neural Nets

Stochastic Neural Nets have stochastic activation functions and/or weights. In
all cases, each neuron forms a coagent with its parameters being the
parameters of the activation function along with the weights connected to the
neuron that compute its input. A more refined decomposition of the agent to
coagents is possible if the weights are stochastic, in which case, every
weight is also a coagent by itself. Notice that although our discussion has
been mainly around reinforcement learning applications, we can apply our
results to the supervised learning setting by simply using a discount factor
$\gamma=0$.

The behavior of a stochastic network can approach that of a deterministic
network, if for example, the stochastic parameters are Gaussian distributions
with very small variance. Stochasticity is also used for improving exploration
in a model.

######  Remark 11.

Indeed, as a general idea, one could inject stochasticity into deterministic
(parts of) learning models and apply the coagent network policy gradient
theorem, and potentially obtain better results, as demonstrated in the noisy
DQN model [4].

##  3\. Non-examples of Coagent Network

There are important examples which do not completely fit into our Definition 1
and require examination. We focus on two of them, where the first violates the
stochasticity of the coagent and the second one does not have a single reward
source.

###  3.1. Attention Option-Critic (AOC)

The Attention Option-Critic (AOC) [3] model is an OC augmented with attention
mechanisms $h_{\omega}$ for each option $\omega$. The state $s_{\omega}$,
input for $\pi_{\omega}$ and its termination function $\beta_{\omega}$, is
obtained as follows:

  * •

Take the environment state $s$ along with the address of the option and the
mode of execution (like $s_{o,2,d}$),

  * •

change the environment state $s$ to $s_{\omega}=h_{\omega}(s)\odot s$ where
$h_{\omega}(s)$ has the same shape as $s$ with values in $[0,1]$, and $\odot$
is the Hadamard multiplication.

This model leverages attention to show that it is possible to achieve useful
options with reasonable lengths.

The AOC learning algorithm can not be recast as a policy gradient of a CN. The
main obstacle is the attention mechanism, which is deterministic and learned
using gradients of the option action value.

However, following Remark 11, if the attention mechanisms were stochastic,
then we could apply the PGT as in Theorem 1.1. The coagents in this case are
the policies, terminations and the attention mechanisms. The rule $\Delta$ is
a similar to that of HOC, where we let the attention corresponding to an
option choose an action when execution mode is $d$.

###  3.2. Hierarchical Actor-Critic (HAC)

From the point of view of Definition 1, there are two ways that HAC fails to
be a CN.

First, we recall how HAC functions. It is a hierarchical goal-based model of
policies $\pi^{1},\ldots,\pi^{N}$ where each policy selects a goal $g_{i}$ to
be accomplished by $\pi^{i+1}$. Each policy has a fixed time horizon of $K$
steps in which it has the chance to achieve the goal. It then terminates
automatically (once it reaches the goal or after $K$ many executions), and the
parent selects a new goal. As a result, the policy $\pi^{i}$ acts again after
at most $K^{N-i}$ many time-steps. The reward given to a policy is how close
the current state is to the goal, which is measured by a metric set by the
user. The edge case of $g_{0}$ (the goal for $\pi^{1}$) is either set by the
user or simply not chosen, in which case the reward for $\pi^{1}$ is just the
environmental reward. In practice, the reward for $\pi^{i}$ is a linear
combination of the goal reward and the environmental reward. Clearly, the more
abstract the policy is, the more emphasis there should be on the environmental
reward. In any case, it is clear that the policies do not have a single reward
source (Remark 5).

Another way that HAC differs from a CN concerns the Markov property, although
this difference can be somehow resolved, in theory, but also in practice as
long as the number $N$ is not too large. If one considers, say, the mid-level
policy of a $3-$level HAC, its action depends on the subgoal it has received
from the highest policy for a fixed $K^{2}$ executions paths or until it
reaches the subgoal ($K$ is some fixed time horizon). During each $K$
executions of the $K^{2}$ executions, the mid-level policy is only called
once, as the lowest policy tries to reach the subgoal assigned by the mid-
policy during that $K$ time-steps. The mid-policy has to remember the subgoal
it was assigned to in the first execution path for the next $K^{2}$ execution
paths. Note that such non-markovianness is also present in the case of
asynchronous firing in [8]. So our main theorem does not directly apply to
that scenario.

######  Remark 12.

The non-markov property is not an obstacle to derive the policy gradient
theorem for HAC as long as one makes a judicious choice for the definition of
state, as also shown in the case of asynchronous CNs [8] by using the so-
called Markov trick; in the case of goal-conditioned models, one can provide
the information of all selected subgoals into the state. This is a practical
assumption as long as the number of hierarchies $N$ is not too large, as the
dimension of the state gets larger proportionally since it has to record all
assigned subgoals. Thus, using the Markov trick, the condition in Definition 1
that every coagent is markov can be lifted.

##  4\. Algorithm and Experiments

###  4.1. Algorithm

####  4.1.1. Update only on arrival and its runtime advantage

The main difference between our Tabular Algorithm 1 and the ones found in the
literature [11, 10, 6, 1, 3] on (H)OC and its variants, is the way the update
is done for parent options during a time-step. In our algorithm, we accumulate
the rewards (in a discounted fashion) and only update the options as they get
called back. This is the ``more'' mathematical way to update, given what the
Theorem 1.1 states. Indeed, in (7), notice that the gradient term
$\frac{d\pi_{o}}{d\theta}$ only appears at states $x_{o}$, meaning only when
$\pi_{o}$ has been involved in the execution path. We should note that
strictly following the math means that we should update the policy or
termination only when they act. Here, we choose to update them both once their
option is reactivated. So even though sometimes the termination function
$\beta_{o}$ is the only part of the option $o$ that acts (because it
terminates), the policy $\pi_{o}$ will also be updated, although it did not
act. The strict mathematical update implemented in the attached code is the
algorithm employing Proximal Policy Optimization (PPO) to train each coagent
(see also [7] for the option-critic PPO implementation).

In contrast, in the literature, every parent of the current active option is
updated (including the root) at each time-step, even if they are not called
back. This update clearly makes the algorithm slower, and depending on the
levels of hierarchy $N$ and average duration of options, there is an increase
of $O(N)$ factor in the runtime of each update step in the algorithm. One
would expect that this method of doing more updates in a single time-step may
provide faster convergence in terms of the number of episodes, but as
demonstrated in the experiments, for models with the best performance, this is
not the case either. Thus, the convergence time is indeed increased by a
factor of $O(N)$.

Another important modification to the algorithm is to use only the parent of
the child for the critics target computation; this is discussed later in 4.3.

####  4.1.2. Incorrect termination function update in the literature

A small mistake made in the literature in the update of $\beta$ is also
addressed in our algorithm. As the policy gradient theorem states the gradient
of the policy should be accompanied by the action value. This means, for an
option $o$, the term $\frac{d\beta_{o}}{d\theta}(s,a)$ should be multiplied by
the value of the action $a$ (termination or not) taken at $s$, i.e.
$Q_{\beta_{o}}(s,a)$. If $a=\ $termination, then
$Q_{\beta_{o}}(s,\text{termination})=V_{\beta_{parent(o)}}(s)$ which is the
value of the higher option termination function at $s$. Otherwise,
$Q_{\beta_{o}}(s,\text{not termination})=V_{\pi_{o}}(s)$. For simplicity, we
consider the case of the Option-Critic model with the $root$ option as the
parent of $o$. Note that in this setting,
$V_{\beta_{parent(o)}}(s)=V_{\pi_{root}}(s)$, as the root never terminates.
Throughout the literature, instead of multiplying the gradient by either
$V_{\pi_{root}}(s)$ or $V_{\pi_{o}}(s)$, the difference of these two terms
denoted by $A_{\beta_{o}}(s)=V_{\pi_{o}}(s)-V_{\pi_{root}}(s)$ is considered.
Hence, no matter the action, the update is always

$d\theta_{\beta_{o}}\leftarrow
d\theta_{\beta_{o}}-\alpha_{\beta_{o}}\frac{d\beta_{o}(s)}{d\theta_{\beta_{o}}}A_{\beta_{o}}(s),$

where $\theta_{\beta_{o}}$ are ${\beta_{o}}$s parameters. In theory, it is
clear that $A_{\beta_{o}}(s)$ is always negative as $V_{\pi_{o}}(s)\leq
V_{\pi_{root}}(s)$, therefore encouraging early termination. This becomes a
reason behind adding a regularizer $\eta>0$ to $A_{\beta_{o}}$ to discourage
option switching (as in [1, 5]).

Correcting this mistake in the update does not eliminate the early termination
issue. Indeed, at the beginning since the lower options get their values
updated more frequently, as long as rewards are nonnegative and values are
initialized similarly, one can expect the value functions of the lower options
to be generally higher than those of their parents. This would push the
options to terminate less.

However, the rate at which the parents are updated is important, and depending
on the task, this rate may need to be quite small. Based on our experiments,
we hypothesize that in the Four Rooms task we must have a much lower rate of
update. This is ensured by lowering the temperature of termination functions
and is discussed further in 4.3.

####  4.1.3. Using the not-terminated option for action value estimate

When estimating the action value of $\beta_{o}$ that has terminated, normally
one uses the value of the termination function of the parent
$V_{\beta_{parent(o)}}(s)$. However, experiments have shown that we can be
more precise in this estimate by taking the action value of the option that
did not terminate, as that is the beginning of the next phase of execution and
clearly takes into account the decisions of the lower termination functions.
This is illustrated in line 38 of Algorithm 2.

####  4.1.4. Not computing the discounted probability for policy updates

Theorem 1.1 states that the update term of each coagent must include a
discounted probability $d(x_{o},x|x_{0})$. In the case of the termination
functions, we compute these in $Probs$ in line 39 of Algorithm 2. However, no
such term is computed for the policy functions. Recall that in the case of
HOC, this discounted probability term is
$\Big{(}\prod_{k=j}^{N-1}\beta_{k}(s^{\prime}_{o,k})\Big{)}P_{\beta,\pi}(s^{\prime}_{o^{\prime},j-1,d}|s^{\prime}_{o,j-1,u})$
as shown in (14).

We did not use this discounted probability in the policy updates, as we
observed that they did not improve results, reduced efficiency of the
algorithms, and furthermore, made it far more difficult to control the option
length, which is what we intend to do later in 4.3.

Algorithm 1 HOC/FON Tabular Actor-Critic

1:procedure
LearnEpisode($env,t_{max},\left<m_{1},\ldots,m_{N}\right>,\alpha_{Q},\alpha_{\pi},\alpha_{\beta},\gamma,\theta$)

2: $o\leftarrow RootOption$

3: $PathToRoot=[o]$

4: $t=0$

5: // get initial state

6: $s\leftarrow s_{0}$

7: // select options for initial step

8: $omega,PathToRoot=ChoosePrimitiveAction(s,t,o)$

9: repeat

10: // take an action and step through the environment

11: $s^{{}^{\prime}},r,\text{done}\leftarrow env.step(omega)$

12: for $o\in PathToRoot$ do // Computing rewards $R_{o}$ (see (4))

13: $o.Reward\leftarrow o.Reward+\gamma^{t-o.ActivationTime-1}r$

14: for $o\in PathToRoot$ do

15: if $o.SampleTermination(s)$ then // $o.SampleTermination$ uses $\beta_{o}$

16: $o.Terminated\leftarrow True$

17: else

18: $omega\leftarrow o$ // $\omega$ is the option that did not terminate

19: break

20: $UpdateCritics(s,PathToRoot,t,\text{done})$

21: // $s$ is not an input for $UpdateActors$ as the previous state-action of
the actors are used for update

22: $UpdateActors(PathToRoot,t,\text{done})$

23: $UpdateTerminations(s,PathToRoot,t,omega)$

24: for $o\in PathToRoot$ do

25: if $o.Terminated$ then

26: $o.Terminated\leftarrow False$ // Re-initializing for the next step

27: $s\leftarrow s^{\prime}$ , $t\leftarrow t+1$

28: $omega,PathToRoot=ChoosePrimitiveAction(s,t,omega)$

29: until done or $t>t_{max}$

Algorithm 2 Update and helper functions for Algorithm 1

1:procedure ChoosePrimitiveAction($s,t,o$)

2: repeat

3: $o.ActivationTime\leftarrow t,\ \ o.Reward\leftarrow 0$

4: $o^{\prime}\leftarrow\pi_{o}(s)$ // $o^{\prime}\in o.Children$

5: $PathToRoot.append(o^{\prime})$

6: $o.PrevAction=o^{\prime},\ \ o.LastObservation=s$

7: $o^{\prime}.ActiveParent=o$

8: $o\leftarrow o^{\prime}$

9: until $o$ is primitive

10: return $o,PathToRoot$

11:

12:procedure UpdateCritics($s,PathToRoot,t,\text{done}$)

13: // To compute $v_{o}$ at $s$, refer to 4.3.3

14: for $o\in PathToRoot.Reverse$ do // Starting from $o=$ root, where
$\beta_{o}\equiv 0$

15:
$v_{o}\leftarrow(1-\beta_{o}(s))Q_{\pi_{o.ActiveParent}}(s,o)+\beta_{o}v_{o.ActiveParent}$

16: for $o\in PathToRoot$ do

17: $x_{o},\ \ u_{o}\leftarrow o.LastObservation,\ \ o.PrevAction$

18: $\delta_{o}\leftarrow
Q_{\pi_{o}}(x_{o},u_{o})-(o.Reward+\gamma^{t-o.ActivationTime}v_{o})$

19: $Q_{\pi_{o}}(x_{o},u_{o})\leftarrow
Q_{\pi_{o}}(x_{o},u_{o})+\alpha_{Q}\delta_{o}$

20: if not $o.Terminated$ then

21: break // No update for options that have not been called back

22:

23:procedure UpdateActors($PathToRoot,t,\text{done}$)

24: for $o\in PathToRoot$ do

25: $c\leftarrow o.PrevAction$

26: $x_{o}\leftarrow o.LastObservation$

27: // Using active parent action value instead of
$\max_{o^{\prime}}Q_{\pi_{o}}(x_{o},o^{\prime})$ for baseline

28:
$\theta_{\pi_{o}}\leftarrow\theta_{\pi_{o}}+\alpha_{\pi}\frac{d\pi_{o}}{d\theta_{\pi_{o}}}(x_{o},c)(Q_{\pi_{o}}(x_{o},c)-Q_{\pi_{o.ActiveParent}}(x_{o},o))$

29: if not $o.Terminated$ then

30: break // No update for options that have not been called back

31:

32:procedure UpdateTerminations($s,PathToRoot,t,omega$)

33: // Not the same as in line 15, wish to only compute $v_{\omega}$

34: for $o\in PathToRoot.Reverse$ do

35:
$v_{o}\leftarrow(1-\beta_{o}(s))\max_{o^{\prime}}Q_{\pi_{o}}(s,o^{\prime})+\beta_{o}v_{o.ActiveParent}$

36: if $o==\omega$ then

37: break

38: $q\leftarrow\max_{o^{\prime}}Q_{\pi_{\omega}}(s,o^{\prime})$ // used in
line 42

39: $Probs\leftarrow 1$

40: for $o\in PathToRoot$ do

41: if $o.Terminated$ then

42: $q_{\beta_{o}}\leftarrow q$ // see 4.1.3

43: $\theta_{\beta_{o}}\leftarrow\theta_{\beta_{o}}+\alpha_{\beta}\cdot
Probs\cdot\frac{d\beta_{o}}{d\theta_{\beta_{o}}}(s)(q_{\beta_{o}}-v_{o})$

44: $Probs\leftarrow Probs\cdot\beta_{o}(s)$

45: else// $o=\omega$ and the opposite of the gradient $\beta_{o}$ has to be
used (see 4.1.2)

46: $q_{\beta_{o}}\leftarrow\max_{o^{\prime}}Q_{\pi_{o}}(s,o^{\prime})$

47: $\theta_{\beta_{o}}\leftarrow\theta_{\beta_{o}}-\alpha_{\beta}\cdot
Probs\cdot\frac{d\beta_{o}}{d\theta_{\beta_{o}}}(s)(q_{\beta_{o}}-v_{o})$

48: break // No update for options that have not been called back

###  4.2. Experiment: settings and results

####  4.2.1. Settings

We will focus exclusively on the classic Four Rooms (FR) experiment. The
variant chosen for our task is the most nonstationary one (also used in [11,
10]) where in each episode the agent starts at a random cell and the goal
state to be reached is also picked uniformly from the 104 cells. This task is
highly nonstationary as the goal changes every episode. Each action succeeds
with a probability of $\frac{2}{3}$ and if failed, the agent goes randomly to
one of the other adjacent cells. The agent receives a reward of $1$ if it
reaches the goal, and zero otherwise.

In all tabular models tested below, the weight sharing pattern is the most
trivial one, i.e. there is no weight sharing among the coagents, as the
experiments are tabular. Furthermore, all coagents are initialized with a
table of $0$s. This means that the $Q$-values are all zero, while the action
probabilities are all equal, similar to termination being set at $\frac{1}{2}$
(as it is the sigmoid function at zero).

Unless mentioned otherwise, we take 50 runs with different random seeds for
50000 episodes, and show the 500 moving average of the number of steps to the
goal or option lengths as discussed next.

####  4.2.2. Analysis and comparison of HOC results

Although our models generally outperform their previous versions as shown in
Figure 3, it is clear that the performance degrades when the number of lowest
options increase (Figure 4). This is in contrast to the finding in [11],
although as illustrated in Figure 4, one can see that more levels in an HOC
(or more lowest options in an FON) simply means slower convergence, and not an
eventual reduction in the best possible performance. In any case, there is an
inefficiency in the number of episodes required to converge. However, we
should also note that the training time for HOC model with $4$ levels to reach
score below 150 in 100000 episodes is around the same (if not less) than that
of [11] (reached in 50000 episodes) if we take into account the efficiency of
our algorithm as discussed in 4.1.1.

Figure 3. The results for the OC model $\left<1,2\right>$ and HOC models
$\left<1,2,2\right>,\left<1,2,2,2\right>$ (notice the last two models have a
total of 9 and 17 options, respectively). Compared to the results in [11]
(right chart) we observe how the simplest $\left<1,2\right>$ OC model
outperforms all other models. It should be noted that the OC model in the
bottom figure is a $\left<1,4\right>$ model, and the moving average in the
right chart is taken over 100 episodes instead of 500. Figure 4. The results
for the HOC model $\left<1,2,2,2\right>$ and FON models $\left<1,2,2,8\right>$
and $\left<1,2,2,2\right>$ ran for 100000 episodes for 5 different random
seeds. We see the eventual convergence of the HOC to the performance achieved
by the same architecture in [11] (the right chart of Figure 3, HOC  (N=4)). We
hypothesize the slower convergence of the HOC model is mostly due to the
number of lowest options present in this model. This is demonstrated by the
similar performance of the FON model $\left<1,2,2,8\right>$ with the same
number (8) of lowest options as the HOC model, versus the better performing
$\left<1,2,2,2\right>$ FON model with the same number of levels of hierarchy
but only two lowest options.

####  4.2.3. Analysis and comparison of FON results

We showed in 2.2 (with more details in B.1.3) that the FON model
$\left<1,1\right>$ has some improvements over a vanilla Actor-Critic model
which is represented by $\left<1\right>$. We see this fact reflected in the
performance of $\left<1,1\right>$ in Figure 5, compared to all of the other
models, even the deeper ones.

Figure 5. We compare the results of some simple FON models. The best model, in
terms of architectural simplicity, convergence time and eventual performance
is the simplest model $\left<1,1\right>$. This also outperforms the previous
HOC models in Figure 3. Note that only two options, a root and a child are
present in this model, and the primitive actions are executed by the child.
Even though a single option can apparently learn this task, during its
learning the presence of another option (the root) is essential. This is
further discussed in B.1.3 and also supported by the result of the AC model in
the right chart of Figure 3.

####  4.2.4. Hyperparameters

The hyperparameters in all our experiments are the same, with the exception of
the termination temperature in sections 4.3 and 4.4. We choose $\gamma=0.99$,
termination and actor temperature $1$ and $0.01$, and termination, critic and
actor learning rates $\alpha_{\beta}=0.001,\alpha_{Q}=0.01$ and
$\alpha_{\pi}=0.00001$, respectively.

###  4.3. Option length and termination temperature

####  4.3.1. Option length and prior solutions to early termination

One of the main issues in option models has been the length of the options,
with the model converging to an option dominating, or options of very small
length (high termination probability). In the old update model of $\beta$
(incorrect as discussed in 4.1.2), one potential fix for this issue has been
to introduce a deliberation cost [1], where a regularizer $\eta$ is added to
the advantage function in the update rule:

$d\theta_{\beta_{o}}\leftarrow
d\theta_{\beta_{o}}-\alpha_{\beta_{o}}\frac{d\beta_{o}(s)}{d\theta_{\beta_{o}}}(A_{\beta_{o}}(s)+\eta).$

This discourages frequent switching of options as that incurs a cost $\eta$.
One can show that this model (in theory) tries to achieve ``an $\eta$-optimal
policy'', details of which are discussed in [5].

Two other methods to solve this issue include interest functions or attention
modules, previously discussed in 2.3 and 3.1.

####  4.3.2. Tuning the termination temperature

Here, we examine the effect of tuning a hyperparameter on this matter, namely,
the temperature of the sigmoid function used in computing $\beta$.

As noted before, we initialize all coagents tables with $0$s. What we hope is
that at first the termination probabilities drop, and then due to the numerics
of the sigmoid function with low temperature, it becomes numerically hard for
their value to rise.

In the beginning, the lower options will be updated twice more often than the
higher options even if temperature is 1.0, as the termination function is
initialized at $\frac{1}{2}$. Given that the rewards are nonnegative numbers,
the value functions of lower options, at any given state, will be larger than
those of the higher options. If temperature is chosen low enough, this makes
the termination probability drop quickly at the beginning. As long as the
lower options are able to collect just enough positive rewards, this turns
into a feedback loop, thereby lowering the termination probability even
further. Over a long period of time, one can expect the higher options to have
learned their value function as well, but since the termination probability is
too small with temperature too low, it becomes numerically hard for it to
rise. Thus, eventually our model has high option lengths, but whether its
performance is as good as previous models requires experimentation.

####  4.3.3. Using only parents for critics target computation

Experiments show that in low temperatures, we need to fully leverage the
parent option as a value target network in the critic update of the child.
Recall that for an option $o$ and corresponding policy $\pi_{o}$, the usual
$Q$-learning target for $Q_{\pi_{o}}(s,a)$ has the following form:

$\delta_{o}\leftarrow
Q_{\pi_{o}}(s,a)-\big{(}r+\gamma^{t}((1-\beta_{o}(s^{(t)}))\max_{a}Q_{\pi_{o}}(s^{(t)},a)+\beta_{o}(s^{(t)})(\text{higher
parents terms}))\big{)},$

where $t$ is the number of time-steps it took for $o$ to be called back, and
$r$ the discounted cumulative rewards accumulated during that time. $a$ can be
a primitive action or a child of $o$. Notice that the multiplier of
$\gamma^{t}$ is simply $V_{\beta_{o}}(s^{(t)})$ which can be computed by
considering two cases: not terminating, with probability
$(1-\beta_{o}(s^{(t)}))$, and terminating, with probability
$\beta_{o}(s^{(t)})$. In theory,
$\max_{a}Q_{\pi_{o}}(s^{(t)},a)=V_{\pi_{o}}(s^{(t)})=Q_{\pi_{parent(o)}}(s^{(t)},o)$
and in practice, the parent serves the role of a value target network.
Therefore, one can make the following change in the update

$\delta_{o}\leftarrow
Q_{\pi_{o}}(s,a)-\big{(}r+\gamma^{t}((1-\beta_{o}(s^{(t)}))Q_{\pi_{parent(o)}}(s^{(t)},o)+\beta_{o}(s^{(t)})(\text{higher
parents terms}))\big{)}.$

Going further, we implement the same kind of change to the term
``$(\text{higher parents terms})$'' where we replace any
$\max_{a}Q_{\pi_{o^{\prime}}}(s^{(t)},a)$ by
$Q_{\pi_{parent(o^{\prime})}}(s^{(t)},o^{\prime})$ for any $o^{\prime}$ that
is in the path to root for $o$. We implement the discussed changes in the
function UpdateCritics, in line 15 of Algorithm 2.

As supported by our experiments, we hypothesize that this change ensures that
the action value functions $Q_{\pi_{o}}(s,a)$ of the lowest options do not get
too much larger than those of their parents, as the target includes the action
value of the parent instead of the option itself. Hence termination
probability drops in a less dramatic way, allowing the higher options to learn
enough to be able to play their role as a value target and stabilize the
learning. Eventually, this allows us to obtain models with longer lasting
options and good performance.

####  4.3.4. Using only parents for termination update rule

Note a similar target term is present in the update for $\beta_{o}$, as the
value of its actions are computed using those of the critics. Therefore one
can use the same tactic there as well. Experiments have shown that using this
modification (in line 35 of Algorithm 2) does not reduce performance but has
an impact on the rate of increase of the option length, and makes it harder to
get highly lengthy options as in Figures 7 or 8. Hence we do not apply the
tactic in this case.

####  4.3.5. $\left<1,\ldots,1\right>$ and $\left<1,2,\ldots,2\right>$ FON
models with low temperature

The models we experiment with have termination temperature 0.05, compared to
the normal 1.0 in the previous section. Figure 6 shows that lowering the
temperature slightly degrades the performance in 50000 episodes. We will see
later in 4.4 that longer runs can potentially close this gap.

Figure 6. Lower temperature seems to slow the convergence to the best possible
performance in both $\left<1,\ldots,1\right>$ and $\left<1,2,\ldots,2\right>$
FON models.

However, option lengths dramatically increase (Figures 7 and 8), spanning
almost the entire episode length but leaving room for other options to be
used/called back as well. So no option in the $\left<1,2,\ldots,2\right>$ FON
models becomes dominant, as also shown by their almost equal length, meaning
both lowest options are active participants in the task.

Figure 7. Option lengths compared for the $\left<1,\ldots,1\right>$ models
with low and normal temperature. Options are enumerated by $\\{0,\ldots,O\\}$
where $0$ denotes the root and $O$ the lowest option. Normal temperature leads
to almost constant (very small) length throughout the entire training, while
low temperature leads to a stable increase and eventual stabilization. Even
though the option length for intermediary options has almost attained the
episode length, they and the root are called back (used at least twice in an
episode), as their child option length is smaller than the episode length
(above 150 as shown in Figure 6).

Figure 8. Option lengths compared for the $\left<1,2,\ldots,2\right>$ models
with low and normal temperature. Options are enumerated by $\\{0,\ldots,O\\}$
where $0$ denotes the root, $1,2$ the second and third options at the first
level, … , and $O-1,O$ the lowest two options. As in Figure 7, normal
temperature leads to almost constant very small option length, while low
temperature leads to its stable increase and eventual stabilization (showed in
longer runs of Figure 10). Similarly, no option becomes dominant as their
length is almost equal and around half of the episode length (shown in Figure
6).

###  4.4. Stability in the long term for nonstationary tasks

The instability of RL algorithms is well-documented, especially when using
non-linear functional approximators. Although the FR experiment uses a tabular
learning, but the nonstationarity of the task can still be a source for
instability.

By running our algorithms for ten times longer than previous experiments, we
observe that in terms of stability, having two options at each layer is better
than having one. We hypothesize that as the reward function changes
dramatically from episode to episode (due to the goal changing), it can be
easier for the model to be stable in the long term if there is more width to
the network. However, as expected and clearly shown in Figure 9, the trade-off
is a slower convergence to the best performance.

####  4.4.1. Comparison of $\left<1,\ldots,1\right>$ and
$\left<1,2,\ldots,2\right>$ FON models in long runs

To test the stability, we take runs of 500000 episodes on a single random
seed, for FON models of the form $\left<1,\ldots,1\right>$ and
$\left<1,2,\ldots,2\right>$ in Figure 9. We observe how the stability of the
algorithm in the long term is generally better for the
$\left<1,2,\ldots,2\right>$ models. We can see how the crashes in performance,
which are spikes in the graphs, are correlated with those present in the
option length of the lowest option(s) as shown in Figure 10.

Figure 9. Performance comparison of $\left<1,\ldots,1\right>$ and
$\left<1,2,\ldots,2\right>$ FON models with the same number of levels of
hierarchy (two to seven). General stability increases as we switch from the
former to the latter model. Note that almost all deeper models achieve the
best performance of 125 steps as in Figure 5.

Figure 10. Lowest option(s) length comparison of $\left<1,\ldots,1\right>$ and
$\left<1,2,\ldots,2\right>$ FON models with the same number of levels of
hierarchy (two to seven). General stability increases as we switch from the
former to the latter model. The lowest options of the latter model are
enumerated by $1$ and $2$. We observe how both of the lowest options are
almost equally used and none is dominant, yet their length is substantial,
confirming the previous results in Figure 8 for even deeper models. Note the
correlation between option length spikes and performance crashes in Figure 9.

###  4.5. Non-linear models

Despite the improvements seen in the tabular models, our preliminary
experiments suggest that using non-linear functional approximators makes it
hard to replicate previous results with the current algorithms, although the
efficiency of the model is still increased by a factor of $O(N)$. We leave a
detailed study of this case to future works and refer to the documentation of
our code for more details in this case.

##  5\. Conclusion and Future Works

In this work, we proved a policy gradient theorem for an agent which decision
making process decomposes to smaller stochastic policies called coagents. The
parameter sharing pattern between these coagents does not change the statement
of the theorem.

Regarding the experiments, we demonstrated what changes to the learning
algorithm of HOC can deliver improvements in a simple tabular yet
nonstationary tasks. We also studied the impact of hyperparameters such as the
temperature of the termination function in the options length. We found high
length options without the use of any regularizing term in the learning
algorithm. Furthermore, we share our code where one can use PPO or simply on-
policy Actor-Critic for learning each option.

Future works include a better understanding of the tuning of the
hyperparameters and initializations of policies and termination functions in
(non-tabular) non-linear tasks. We also need a better measure to compare the
stability of hierarchical models $\left<1,\ldots,1\right>$ with that of the AC
model, and compare/compute the stability as one uses more levels of hierarchy.
Some links have been established (B.1.3) between the hierarchical model
$\left<1,1\right>$ and the AC model with a target network, which is well-known
to improve stability. One wonders if using any more levels like
$\left<1,1,1\right>$ actually improves stability compared to
$\left<1,1\right>$. This may not be true for small tasks like the Four Rooms
experiment, but could be for more complicated ones.

More fundamentally perhaps, a closer examination of the nature of the tasks
against which option models are evaluated is overdue. As mentioned in the
literature, options are supposed to represent different skills. If so, then
the training and tasks should be such that they can accommodate such outcome
and the trained model should be also examined if it delivers such an outcome.
For example, we need tasks where the optimal policy can be decomposed to
policies achieving goals with different nature (requiring different skills) in
the service of a more abstract goal. On the other hand, having options which
focus/have their attention on different parts of a screen or different
parts/phases of the task, does not necessarily mean we have a decomposition to
skills. It simply means we have leveraged the capacity and modularity of our
model to tackle the problem, but the decomposition achieved may not reflect
any decomposition to skills which can be reused in a transfer learning
setting. We should also be aware of the possibility that additional structures
and auxiliary losses need to be added to the vanilla options model to
facilitate such an outcome.

## Acknowledgements

The first named author would like to acknowledge the support of the Perimeter
Institute for Theoretical Physics and Microsoft. Research at Perimeter
Institute is supported by the Government of Canada through Innovation, Science
and Economic Development Canada and by the Province of Ontario through the
Ministry of Research, Innovation and Science. The experiments were conducted
using Microsoft computational resources.

## References

  * Bacon et al., [2017] Bacon, P.-L., Harb, J., and Precup, D. (2017).  The option-critic architecture.  In Thirty-First AAAI Conference on Artificial Intelligence.
  * Bertsekas and Tsitsiklis, [2000] Bertsekas, D. P. and Tsitsiklis, J. N. (2000).  Gradient convergence in gradient methods with errors.  SIAM Journal on Optimization, 10(3):627–642.
  * Chunduru and Precup, [2020] Chunduru, R. and Precup, D. (2020).  Attention option-critic.
  * Fortunato et al., [2017] Fortunato, M., Azar, M. G., Piot, B., Menick, J., Osband, I., Graves, A., Mnih, V., Munos, R., Hassabis, D., Pietquin, O., et al. (2017).  Noisy networks for exploration.  arXiv preprint arXiv:1706.10295.
  * Harb et al., [2018] Harb, J., Bacon, P.-L., Klissarov, M., and Precup, D. (2018).  When waiting is not an option: Learning options with a deliberation cost.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32.
  * Khetarpal et al., [2020] Khetarpal, K., Klissarov, M., Chevalier-Boisvert, M., Bacon, P.-L., and Precup, D. (2020).  Options of interest: Temporal abstraction with interest functions.  arXiv preprint arXiv:2001.00271.
  * Klissarov et al., [2017] Klissarov, M., Bacon, P.-L., Harb, J., and Precup, D. (2017).  Learnings options end-to-end for continuous action tasks.  arXiv preprint arXiv:1712.00004.
  * Kostas et al., [2019] Kostas, J., Nota, C., and Thomas, P. S. (2019).  Asynchronous coagent networks: Stochastic networks for reinforcement learning without backpropagation or a clock.  arXiv preprint arXiv:1902.05650.
  * Levy et al., [2017] Levy, A., Platt, R., and Saenko, K. (2017).  Hierarchical actor-critic.  arXiv preprint arXiv:1712.00948.
  * Riemer et al., [2019] Riemer, M., Cases, I., Rosenbaum, C., Liu, M., and Tesauro, G. (2019).  On the role of weight sharing during deep option learning.  arXiv preprint arXiv:1912.13408.
  * Riemer et al., [2018] Riemer, M., Liu, M., and Tesauro, G. (2018).  Learning abstract options.  In Advances in Neural Information Processing Systems, pages 10424–10434.
  * Sutton et al., [1998] Sutton, R. S., Barto, A. G., et al. (1998).  Introduction to reinforcement learning, volume 135.  MIT press Cambridge.
  * Sutton et al., [1999] Sutton, R. S., Precup, D., and Singh, S. (1999).  Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning.  Artificial intelligence, 112(1-2):181–211.

##  Appendix A Hierarchical Option Critic

###  A.1. Bellman equations

Some explanations are necessary regarding our notation for the edge cases:

  * •

The state $s_{o,N,d}$: $s_{o,N,d}$ is followed by some state
$s^{\prime}_{o,N,u}$ for some $s^{\prime}\in\mathcal{S}_{env}$. Notice it is
always the case that a primitive action, after being taken, immediately
terminates, if it were to be looked at as an option, in other words
$\beta_{N}()\equiv 1$. So $s^{\prime}_{o,N,u}$ is immediately followed by
$s^{\prime}_{o,N-1,u}$. Therefore, it is safe to take
$s^{\prime}_{o,N,u}=s^{\prime}_{o,N-1,u}$.

  * •

$s_{o,0,d}$ or $s_{o,0,u}$ means the highest level of hierarchy $o^{0}$ at
state $s$, where the first option has not been chosen yet. The highest level
policy never terminates. Therefore, as $\beta_{0}()\equiv 0$, $s_{o,0,u}$ is
immediately followed by $s_{o,0,d}$ and as such $s_{o,0,u}=s_{o,0,d}$. This
state is followed by $s_{o,1,d}$ for some option $o^{1}$ assigned by
$\pi^{1}$.

  * •

Whenever in a summation $\sum_{x}^{y}$ or product $\prod_{x}^{y}$, the higher
index is smaller than the lower index $x>y$, we consider the result to be $1$.
This convention is helpful as it makes the equations easier to express without
specifically accounting for the edge cases.

To describe $Q-$values of HOC, recall that in standard RL, we tend to
differentiate the action value and the state value by using a different
notation ($Q$ and $V$). Our terminology allows us to unambiguously use the
same notation $Q()$ for the value of our augmented states at any level of
hierarchy or any state of execution $d$ or $u$.

First, let $r(s_{o,N})$ be the reward (or expected reward, if the environment
reward process is stochastic) given by the environment to the agent which has
taken primitive action $o^{N}$ at $s\in\mathcal{S}_{env}$. Let
$\gamma\in[0,1]$ be the discount factor. All $Q-$values will be computed in
succession. Starting with the easiest case, at the lowest level:

(15) $\displaystyle
Q(s_{o,N,d})=r(s_{o,N})+\gamma\sum_{s^{\prime}}P(s^{\prime}_{o,N-1,u}|s_{o,N,d})Q(s^{\prime}_{o,N-1,u})$

where $P$ is the transition probability of the environment, that given action
$o^{N}$ at $s$, the state changes to $s^{\prime}$. Note that
$Q(s_{o,N,d})=Q(s_{o,N-1,d},o^{N})$, i.e. the $Q$-value of the state-action
pair $(s_{o,N-1,d},o^{N})$ for the policy $\pi^{N}$ of the option $o^{1:N-1}$.

The equation above is obvious, as the next state is
$s^{\prime}_{o,N,u}=s^{\prime}_{o,N-1,u}$, which is in the upward execution
phase. Next, we need to compute the value at this state:

(16) $\displaystyle
Q(s_{o,N-1,u})=\sum_{i=0}^{N-1}(1-\beta_{i}(s_{o,i}))\big{(}\prod_{j=i+1}^{N-1}\beta_{j}(s_{o,j})\big{)}Q(s_{o,i,d})$

Note that the product
$(1-\beta_{i}(s_{o,i}))\big{(}\prod_{j=i+1}^{N-1}\beta_{j}(s_{o,j})\big{)}$ is
the probability of upward trajectory up to level $i+1$. At that level, the
decision is to not terminate, which has probability $1-\beta_{i}(s_{o,i})$.
Notice $Q(s_{o,N-1,u})$ can also be interpreted as the state-value for
termination $\beta_{N-1}$ of option $o^{1:N-1}$ at state $s_{o,N-1,u}$.
Similar interpretations exist for the $Q$-values computed later.

Finally, computing $Q(s_{o,i,d})$ completes the cycle needed to compute
$Q(s_{o,N,d})$, as the Bellman equation for $Q$ is a recursive equation. To do
so, observe the following Bellman equation:

(17) $\displaystyle
Q(s_{o,l-1,d})=\sum_{o^{l}}\pi^{l}(o^{l}|s_{o,l-1})Q(s_{o,l,d}),\ \forall
l\leq N$

Applied iteratively, one obtains an expression of $Q(s_{o,i,d})$ in terms of
$Q(s_{o,N,d})$, which was already computed.

In similar fashion, one can compute the $Q$ value at all other states. To do
so, we shall define the rewards for any node, similar to how it is done in [8,
Section 4.1].

(18) $\displaystyle
r(s_{o,l})=\frac{\sum_{o^{l+1:N}}\prod_{i=l+1}^{N}\pi^{i}(o^{i}|s_{o,i-1})r(s_{o,N})}{\sum_{o^{l+1:N}}\prod_{i=l+1}^{N}\pi^{i}(o^{i}|s_{o,i-1})},\
\forall l\leq N$

Notice the normalization factor is equal to one. Then, using the transition
probability:

(19) $\displaystyle
P_{\pi}(s^{\prime}_{o,N,u}|s_{o,l,d})=\Big{(}\prod_{i=l+1}^{N}\pi^{i}(o^{i}|s_{o,i-1})\Big{)}P(s^{\prime}|s_{o,N}),\
\forall l\leq N$

it follows

(20) $\displaystyle
Q(s_{o,l,d})=r(s_{o,l})+\gamma\sum_{s^{\prime},o^{l+1:N}}P_{\pi}(s^{\prime}_{o,N,u}|s_{o,l,d})Q(s^{\prime}_{o,N,u})$

Notice in both equations above, $s^{\prime}_{o,N,u}$ can be replaced by
$s^{\prime}_{o,N-1,u}$. Further, for all states with upward execution mode,
one can write:

(21) $\displaystyle
Q(s_{o,l,u})=\sum_{i=0}^{l}(1-\beta_{i}(s_{o,i}))\big{(}\prod_{j=i+1}^{l}\beta_{j}(s_{o,j})\big{)}Q(s_{o,i,d}),\
\forall l\leq N$

When the algorithm is at $s_{o,l,u}$, it will begin executing upward and reach
some state $s_{o,i,u}$, for some $0\leq i\leq l$ (with probability
$\prod_{j=i+1}^{l}\beta_{j}(s_{o,j})$), where it decides to execute downward
with probability $(1-\beta_{i}(s_{o,i})$), i.e. the state changes to
$s_{o,i,d}$. The above equation multiplies these probabilities by the value
$Q(s_{o,i,d})$ of the state $s_{o,i,d}$ it starts executing downward at.

######  Remark 13.

In the literature [13, 1, 11], $Q_{\Omega}(s,o^{1:i})$ generally corresponds
to our $Q(s_{o,i,d})$ while $Q_{U}(s,o^{1:i})$ generally corresponds to
$Q(s_{o,i,u})$; in the edge case of $i=N$, this correspondence could become a
bit imprecise, due to the fact that the literature notation accounts for those
cases separately by introducing new notations. Finally, $V_{\Omega}(s)$
corresponds to $Q(s_{o,0,d})$.

######  Remark 14.

The equations (20) and (17) give the following in the case of $l=2,N=2$:

(22) $\displaystyle
Q(s_{o,1,d})=\sum_{o^{2}}\pi^{2}(o^{2}|s_{o,1})Q(s_{o,2,d})$ (23)
$\displaystyle
Q(s_{o,2,d})=r(s_{o,2})+\gamma\sum_{s^{\prime}}P(s^{\prime}_{o,1,u}|s_{o,2,d})Q(s^{\prime}_{o,1,u})$

which are the equations for $Q_{\Omega}$ in terms of $Q_{U},U$ as written in
[1, Eq. 1,2].

###  A.2. Policy gradient theorem

In this section, the HOC policy gradient theorem (HOCPGT) is reviewed [10,
Theorem 1] using the new notations. The notations that match with the
reference have also the same meaning, for example
$P_{\beta,\pi}(\cdot|\cdot),\mu(\cdot|\cdot)$ or the advantage $A()$. This
section is needed as a reference, as we apply our main result to get a direct
proof for HOCPGT.

Let us rewrite (21) so that the $Q-$value on the right-hand side is evaluated
at states with the same level as the left-hand side. To do so, apply (17)
repeatedly on $Q(s_{o,i,d})$ to get to $Q(s_{o,l,d})$, which leads to the
following when $l\leq N$:

$Q(s_{o,l,u})=$ (24) $\displaystyle\sum_{o^{\prime
1:l}}\Big{(}\sum_{i=0}^{l}(1-\beta_{i}(s_{o,i}))\big{(}\prod_{j=i+1}^{l}\beta_{j}(s_{o,j})\big{)}\big{(}\prod_{p=i+1}^{l}\pi^{p}(o^{\prime
p}|s_{o^{\prime},p-1})\big{)}1_{o^{\prime
1:i}=o^{1:i}}\Big{)}Q(s_{o^{\prime},l,d}),$

where $1_{o^{\prime 1:i}=o^{1:i}}$ is one if $o^{\prime 1:i}=o^{1:i}$ and zero
otherwise. The term multiplied by $Q(s_{o^{\prime},l,d})$ has an independent
meaning, which will allow to make this equation more compact. Denote
$P_{\beta,\pi}(s_{o^{\prime},l,d}|s_{o,l,u})$ as the transition probability
from $s_{o,l,u}$ to $s_{o^{\prime},l,d}$, which is dependent on the
termination functions $\beta$ and policies $\pi$. Hence, this probability
solely depends on what the model and not the environment, and it is the
probability of the algorithm executing downward at $o^{\prime 1:l}$ at level
$l+1$, after finishing its upward phase of execution (which started at level
$l+1$) and coming down again to level $l+1$. It is easy to see that this
probability is the same multiplicative term in the equation above:

(25) $\displaystyle
P_{\beta,\pi}(s_{o^{\prime},l,d}|s_{o,l,u})=\sum_{i=0}^{l}(1-\beta_{i}(s_{o,i}))\big{(}\prod_{j=i+1}^{l}\beta_{j}(s_{o,j})\big{)}\big{(}\prod_{p=i+1}^{l}\pi^{p}(o^{\prime
p}|s_{o^{\prime},p-1})\big{)}1_{o^{\prime 1:i}=o^{1:i}}$

One can generalize this to compute other useful transition probabilities:

(26) $\displaystyle
P_{\beta,\pi}(s_{o^{\prime},m,d}|s_{o,l,u})=\prod_{p=l+1}^{m}\pi^{p}(o^{\prime
p}|s_{o^{\prime},p-1})P_{\beta,\pi}(s_{o^{\prime},l,d}|s_{o,l,u}),\ \forall
l\leq m\leq N,$ (27) $\displaystyle
P_{\beta,\pi}(s_{o^{\prime},m,d}|s_{o,l,u})=P_{\beta,\pi}(s_{o^{\prime},m,d}|s_{o,m,u})\prod_{j=m+1}^{l}\beta_{j}(s_{o,j}),\
\forall m\leq l\leq N$

Using the above, equation (24) becomes:

(28) $\displaystyle Q(s_{o,l,u})=\sum_{o^{\prime
1:l}}P_{\beta,\pi}(s_{o^{\prime},l,d}|s_{o,l,u})Q(s_{o^{\prime},l,d})$

Next, let us define $\mu(s^{\prime}_{o^{\prime},l-1,d}|s_{o,l-1,d})$, which is
the sum of discounted ($\gamma^{k}\times$) probability of getting from
$s_{o,l-1,d}$ to $s^{\prime}_{o^{\prime},l-1,d}$ (in $k$ steps). We will
compute two transition probabilities. Using (19) to write the transition
probability for $s_{o,l,d}\to s^{\prime}_{o,N-1,u}$:

(29) $\displaystyle
P_{\pi}(s^{\prime}_{o,N-1,u}|s_{o,l,d})=P_{\pi}(s^{\prime}_{o,N,u}|s_{o,l,d})=\sum_{o^{l+1:N}}P(s^{\prime}|s_{o,N})\prod_{i=l+1}^{N}\pi^{i}(o^{i}|s_{o,i-1})$

Also, for $s_{o,l-1,d}\to s^{\prime}_{o,l-1,u}$:

(30) $\displaystyle
P_{\beta,\pi}(s^{\prime}_{o,l-1,u}|s_{o,l-1,d})=\sum_{o^{l:N-1}}\prod_{j=l}^{N-1}\beta_{j}(s^{\prime}_{o,j})P_{\pi}(s^{\prime}_{o,N-1,u}|s_{o,l-1,d})$

Next, define the discounted one-step and $k$-steps recursively as follows
$\forall l\leq N$:

(31) $\displaystyle
P_{\gamma}^{(0)}(s^{\prime}_{o^{\prime},l-1,d}|s_{o,l-1,d})=1_{s^{\prime}_{o^{\prime},l-1,d}=s_{o,l-1,d}},$
(32) $\displaystyle
P_{\gamma}^{(1)}(s^{\prime}_{o^{\prime},l-1,d}|s_{o,l-1,d})=\gamma
P_{\beta,\pi}(s^{\prime}_{o^{\prime},l-1,d}|s^{\prime}_{o,l-1,u})P_{\beta,\pi}(s^{\prime}_{o,l-1,u}|s_{o,l-1,d}),$
(33) $\displaystyle
P_{\gamma}^{(k)}(s^{\prime}_{o^{\prime},l-1,d}|s_{o,l-1,d})=\sum_{s^{\prime\prime}_{o^{\prime\prime},l-1}}P_{\gamma}^{(k-1)}(s^{\prime}_{o^{\prime},l-1,d}|s^{\prime\prime}_{o^{\prime\prime},l-1,d})P_{\gamma}^{(1)}(s^{\prime\prime}_{o^{\prime\prime},l-1,d}|s_{o,l-1,d})$

The definition for $\mu()$ can be written for different transitions. The one
needed for HOCPGT is:

(34)
$\displaystyle\mu(s^{\prime}_{o^{\prime},l-1,d}|s_{o,l-1,d})=\sum_{k=0}^{\infty}P_{\gamma}^{(k)}(s^{\prime}_{o^{\prime},l-1,d}|s_{o,l-1,d}),\
\forall l\leq N$

Let us now define the advantage as follows:

(35) $\displaystyle A(s_{o,l})=Q(s_{o,l,d})-Q(s_{o,l-1,u})$

The advantage answers this question: If one is able to choose, then how much
advantageous it is to start executing downward from $s_{o,l}$, than to change
the higher level options and try a different set of options
$s_{o^{\prime},l}$? The difference above in the values determines the
advantage of this choice. Indeed, just like the first term $Q(s_{o,l,d})$ is
the value of not terminating, the second term is the value of terminating.
Thus, alternatively, one can write:

(36) $\displaystyle
A(s_{o,l})=Q_{\beta_{l}}(s_{o,l},0)-Q_{\beta_{l}}(s_{o,l},1)$

using the action value functions of $\beta_{l}$. It is clear that

(37) $\displaystyle Q_{\beta_{l}}(s_{o,l},1)=Q(s_{o,l-1,u})\ ,\
Q_{\beta_{l}}(s_{o,l},0)=Q(s_{o,l,d})$

$1$ denotes the termination action, and $0$ the opposite action. These actions
have probabilities:

(38) $\displaystyle\beta_{l}(1|s_{o,l}):=\beta_{l}(s_{o,l})\ ,\
\beta_{l}(0|s_{o,l}):=1-\beta_{l}(s_{o,l})$

We are ready to state HOCPGT. Assume that all nodes are determined by
parameters $\theta$. Assume an initial state $(s_{0})_{o_{0},N-1,d}$ at the
lowest level of the tree at node $o_{0}^{1:N-1}$.

######  Theorem A.1.

[10, Theorem 1] $\frac{dQ}{d\theta}((s_{0})_{o_{0},N-1,d})=$

(39)
$\displaystyle\sum_{s,o^{1:N-1},s^{\prime}}\mu(s^{\prime},s_{o,N-1,d}|(s_{0})_{o_{0},N-1,d})\Big{[}\sum_{o^{N}}\frac{d\pi^{N}}{d\theta}(o^{N}|s_{o,N-1})Q(s_{o,N,d})$
(40)
$\displaystyle-\gamma\sum_{l=1}^{N-1}\Big{(}\prod_{k=l+1}^{N-1}\beta_{k}(s^{\prime}_{o,k})\Big{)}\frac{d\beta_{l}}{d\theta}(s^{\prime}_{o,l})A(s^{\prime}_{o,l})$
(41)
$\displaystyle+\gamma\sum_{j=0}^{N-1}\Big{(}\prod_{k=j}^{N-1}\beta_{k}(s^{\prime}_{o,k})\Big{)}\sum_{o^{\prime
1:j}}P_{\beta,\pi}(s^{\prime}_{o^{\prime},j-1,d}|s^{\prime}_{o,j-1,u})\frac{d\pi^{j}}{d\theta}(o^{\prime
j}|s^{\prime}_{o^{\prime},j-1})Q(s^{\prime}_{o^{\prime},j,d})\Big{]}$

where $\mu(s_{o,N-1,d},s^{\prime}|(s_{0})_{o_{0},N-1,d})$ is the discounted
probability of starting at $(s_{0})_{o_{0},N-1,d}$, reaching the state
$s_{o,N-1,d}$, which after $\pi^{N}$ execution is followed by
$s^{\prime}_{o,N-1,u}$.

######  Remark 15.

The third term above might seem different from the one in the reference [10,
Theorem 1], but they are the same. Our convention, motivated from our point of
view, is to sum over each node $o^{\prime 1:j}$ individually, while in the
reference, the last node $o^{\prime 1:N-1}$ at the bottom of the tree is taken
and the sum is over its parents.

Next, we try to rewrite the above in a form that will be closer to our main
result. Let us denote $x_{0}=(s_{0})_{o_{0},N-1,d}$ and $x=s_{o,N-1,d}$.
Recall the HOC policy is denoted by $\Pi$. Then the first term in the bracket
above can be written as:

(42)
$\displaystyle\sum_{x}d^{\Pi}(x|x_{0})\sum_{o^{N}}\frac{d\pi^{N}}{d\theta}(o^{N}|x)Q_{o^{1:N-1}}(x,o^{N})$

Where $d^{\Pi}(x|x_{0})$ is the discounted transition probability for a policy
$\Pi$, for reaching $x$ from $x_{0}$. Notice there is no sign of $s^{\prime}$,
because $\frac{d\pi^{N}}{d\theta}(o^{N}|s_{o,N-1})Q(s_{o,N,d})$ does not
depend on $s^{\prime}$, hence the summation over $s^{\prime}$ averages out
this outcome state. Also note that $Q_{o^{1:N-1}}(x,o^{N})$ is the $Q$-value
of $\pi^{N}(\cdot|o^{1:N-1})$ policy of the node $o^{1:N-1}$. It is of course
equal to $Q(s_{o,N,d})$. Hence, the first term is nothing but the usual policy
gradient of the lowest level node.

For the second term, for a given node $o^{1:l}$ for $1\leq l\leq N-1$, the
term $\gamma\Big{(}\prod_{k=l+1}^{N-1}\beta_{k}(s^{\prime}_{o,k})\Big{)}$ can
be absorbed into the discounted transition probability $\mu()$ to create
$d^{\Pi}(x^{\prime}_{o,l},x|x_{0})$ where
$x^{\prime}_{o,l}=s^{\prime}_{o,l,u}$. This is the discounted transition
probability from $x_{0}\to x$ in any number of execution paths, and from $x\to
x^{\prime}_{o,l}$ in a single execution path.

######  Remark 16.

Notice that an execution path in this setting, is an execution from $\pi^{N}$
followed by a path upward, then a path downward until before the next
execution of $\pi^{N}$ takes place. Thus, as the path involves an
environmental step due to the execution of $\pi^{N}$ at the beginning of the
path, the discounted transition probability takes a discount factor $\gamma$.

The above remark applies when going from $d^{\Pi}(x|x_{0})$ to
$d^{\Pi}(x^{\prime}_{o,l},x|x_{0})$, as is the case in
$\gamma\Big{(}\prod_{k=l+1}^{N-1}\beta_{k}(s^{\prime}_{o,k})\Big{)}$.
Furthermore, using (38),

(43)
$\displaystyle\frac{d\beta_{l}}{d\theta}(1|s^{\prime}_{o,l})=\frac{d\beta_{l}}{d\theta}(s^{\prime}_{o,l})\
,\
\frac{d\beta_{l}}{d\theta}(0|s^{\prime}_{o,l})=-\frac{d\beta_{l}}{d\theta}(s^{\prime}_{o,l})$

From the above with (36) and (37):

(44)
$\displaystyle-\sum_{s,o^{1:N-1},s^{\prime}}\mu(s^{\prime},s_{o,N-1,d}|(s_{0})_{o_{0},N-1,d})\gamma\Big{(}\prod_{k=l+1}^{N-1}\beta_{k}(s^{\prime}_{o,k})\Big{)}\frac{d\beta_{l}}{d\theta}(s^{\prime}_{o,l})A(s^{\prime}_{o,l})=$
(45)
$\displaystyle\sum_{x^{\prime}_{o,l},x}d^{\Pi}(x^{\prime}_{o,l},x|x_{0})\sum_{a=0,1}\frac{d\beta_{l}}{d\theta}(a|x^{\prime}_{o,l})Q_{\beta_{l}}(x^{\prime}_{o,l},a)$

Similar to (42), one can see that (45) is nothing but the usual policy
gradient theorem for the termination policies $\beta_{l}$ at $o^{1:l}$.
Finally, for the last term, for each $\pi^{j}$ at $o^{\prime 1:j-1}$:

(46)
$\displaystyle\sum_{s,o^{1:N-1},s^{\prime}}\mu(s^{\prime},s_{o,N-1,d}|(s_{0})_{o_{0},N-1,d})\Big{[}\gamma\Big{(}\prod_{k=j}^{N-1}\beta_{k}(s^{\prime}_{o,k})\Big{)}P_{\beta,\pi}(s^{\prime}_{o^{\prime},j-1,d}|s^{\prime}_{o,j-1,u})\times$
(47) $\displaystyle\sum_{o^{\prime j}}\frac{d\pi^{j}}{d\theta}(o^{\prime
j}|s^{\prime}_{o^{\prime},j-1})Q(s^{\prime}_{o^{\prime},j,d})\Big{]}=$ (48)
$\displaystyle\sum_{x^{\prime}_{o^{\prime},j-1},x}d^{\Pi}(x^{\prime}_{o^{\prime},j-1},x|x_{0})\sum_{o^{\prime
j}}\frac{d\pi^{j}}{d\theta}(o^{\prime
j}|x^{\prime}_{o^{\prime},j-1})Q_{o^{\prime
1:j-1}}(x^{\prime}_{o^{\prime},j-1},o^{\prime j})$

Where $d^{\Pi}(x^{\prime}_{o^{\prime},j-1},x|x_{0})$ is the discounted
transition probability from $x_{0}\to x$ in any number of execution paths, and
from $x\to x^{\prime}_{o^{\prime},j-1}=s^{\prime}_{o^{\prime},j-1}$ in a
single execution path. The factor
$\gamma\Big{(}\prod_{k=j}^{N-1}\beta_{k}(s^{\prime}_{o,k})\Big{)}P_{\beta,\pi}(s^{\prime}_{o^{\prime},j-1,d}|s^{\prime}_{o,j-1,u})$
is what describes the discounted probability of this last transition in a
single execution path.

##  Appendix B Coagent Network

The usual convergence theorem for the policy gradient theorem applies, as the
Theorem 1.1 is essentially a rewrite of the policy gradient for $\Pi$.

######  Theorem B.1.

The following holds (with some Lipschitz conditions as in [2]): The unbiased
policy update above makes $J_{\Pi}(\theta)$ converge to a finite value and
$\lim_{t\to\infty}\mbox{\boldmath$\nabla$}_{\theta}J_{\Pi}=0$.

######  Remark 17.

Complicated networks can be trained using this policy gradient theorem, but
let us consider the simple case of a single loop. The nodes are labeled by
$o_{n}$ for $n\in\\{1,\ldots,N\\}$, where each node, depending on the input,
makes a primitive action or sends some information via its action $u_{n}$ to
the next node (with $o_{N}$ sending to $o_{1}$). The description of the rule
$\Delta$ is as follows: one assigns each state $s$ of the environment two
integers $n_{s}\in\\{1,\ldots,N\\}$ and $l_{s}\in\mathbb{N}$, which means the
node $o_{n_{s}}$ is the one that performs a primitive action at environment
state $s$ after $s$ has passed through $l_{s}$ many cycles. More generally,
one can imagine $N$ decision functions
$f_{n,s}:\mathcal{S}_{\pi_{o_{n}}}\to\\{1,\ 0\\}$ for any
$s\in\mathcal{S}_{env}$ and $n\in\\{1,\ldots,N\\}$, where $1$ means primitive
and $0$ non-primitive. Depending on the input of the node, after finitely many
coagent executions, we have $f_{n,s}(x_{o_{n}})=1$. This should be guaranteed
by the programmer to happen to avoid infinite loops. This forces the node
$o_{n}$ to apply a primitive action at $x_{o_{n}}$, which contains $s$ as the
information regarding the environment.

######  Remark 18.

The freedom in the graph structure and parameter sharing pattern, could allow
us to exploit the relational bias in a given environment/task to build more
powerful RL agents.

###  B.1. More details on examples of Coagent Networks

####  B.1.1. (A)Synchronous Coagent Network

Notice that by deriving the shared parameter version of the synchronous
Coagent Policy Gradient Theorem (CPGT) [8], one can go through the same
argument in [8, Section 5.1], to derive the shared parameter version for the
asynchronous CPGT. Alternatively, one can see the asynchronous CPGT as the
non-markov version of our model for a network of coagents. Either way, using
the Markov trick (Remark 12), we have

######  Theorem B.2.

The policy gradient of $\Pi$ for a single reward coagent network that is
formed by non-markov coagents can still be written as the sum of the policy
gradient of its coagents.

####  B.1.2. HOC

To obtain (A.1), we simply apply (1.1) giving us the same equations in
(42),(45), and (48) for HOCPGT with some small changes due to our different
definition of execution paths. More precisely, since the start of the path is
at $s_{o,N-1,u}$, one first obtains the terminations policy gradients:

(49)
$\displaystyle\sum_{x_{o,l},x}d^{\Pi}(x_{o,l},x_{o}|x_{0})\sum_{a=0,1}\frac{d\beta_{l}}{d\theta}(a|x_{o,l})Q_{\beta_{l}}(x_{o,l},a)$

where $x=s_{o,N-1,u},x_{o,l}=s_{o,l,u}$ and $x_{0}=(s_{0})_{o_{0},N-1,u}$.
Then going the downward phase, one obtains the policy gradient of $\pi$'s

(50)
$\displaystyle\sum_{x_{o^{\prime},j-1},x}d^{\Pi}(x_{o^{\prime},j-1},x_{o}|x_{0})\sum_{o^{\prime
j}}\frac{d\pi^{j}}{d\theta}(o^{\prime j}|x_{o^{\prime},j-1})Q_{\pi_{o^{\prime
1:j-1}}}(x_{o^{\prime},j-1},o^{\prime j}),$

where $x_{o^{\prime},j-1}=s_{o^{\prime},j-1,d}$ and $\pi_{o^{\prime
1:j-1}}(-|s)=\pi^{j}(-|s,o^{\prime 1:j-1})$ is the policy of the option
$o^{\prime 1:j-1}$. Note the above is for all $j=1,\ldots,N$ and it is unlike
(42) and (48), where $j=N$ had to be separated from the rest. The reason for
the separation is that some reward had to be counted only towards the value of
$\pi^{N}$, which executed the primitive action first.

######  Remark 19.

There exists another proof of HOCPGT (A.1) in [10, See appendix] using the
CPGT in [8], though it relies on the assumption that one has a shared
parameter version of the CPGT (a corollary of our theorem). Notice our proof
does not involve any further state-augmentation. This is in contrast to the
proof in [10], where something called the termination vector $T$ is defined
and the graph structure is completely forgotten to be able to cast HOC into a
synchronous coagent network (only two coagents). This shows that our framework
can provide more intuitive ways for computing the policy gradient of coagent
networks.

####  B.1.3. Feedforward Option Network

We want to understand the algorithm for $\left<1,1\right>$ by building it
piece by piece starting from an AC algorithm and changing it where
appropriate. For simplicity, we will assume that we have a fixed value of
termination $\frac{1}{n}$ for some $n>0$. This means the option terminates
every $n$ steps. This is a practical assumption as observed in the FR
experiments, where unless termination temperature is low, the termination
function (more or less) stays constant throughout the training of
$\left<1,1\right>$ (Figures 7 and 8). Next, notice that the root has just one
action (selecting the child), and its action value is in theory the value
function of the children. Therefore, we add a value target network computing
$V_{target}$ for the algorithm, where:

  1. (a)

It is updated only every $n$ ($=(\frac{1}{n})^{-1}$) steps using its own
update rule

$V_{target}(s)\leftarrow r_{1}+\gamma
r_{2}+\ldots+\gamma^{n-1}r_{n-1}+\gamma^{n}V_{target}(s^{(n)}).$

  2. (b)

The target is used to soft-update the $Q$-value of the AC, where instead of
choosing $V_{target}(s^{\prime})$ to build the target of $Q(s,a)$, we choose
$\frac{1}{n}V_{target}(s^{\prime})+(1-\frac{1}{n})\max_{a}Q(s^{\prime},a)$,
meaning

$Q(s,a)\leftarrow
r+\gamma(\frac{1}{n}V_{target}(s^{\prime})+(1-\frac{1}{n})\max_{a}Q(s^{\prime},a)),$

instead of

$Q(s,a)\leftarrow r+\gamma V_{target}(s^{\prime}).$

Notice there are two effects: (1) the rollout effect that trickles down from
(a) to the update rule (b), (2) the target network used softly in the update,
with the rate being the same as its update frequency, i.e. $1/n$.

The above assumed a fixed termination function. In general, the termination
function also learns, so the rate of the target network update is learned. In
summary, $\left<1,1\right>$ can be viewed as an actor-critic model which is
soft-updated with a value target network with rollout and a learnable rate of
update. This is the reason behind $\left<1,1\right>$ outperforming the AC
model as it is equipped with several improvements.

######  Remark 20.

This ``target effect'' is generalized/compounded if one uses more levels of
hierarchy, i.e. $\left<1,1,\ldots,1\right>$. Understanding the exact benefit
of having more levels is the object of future research.