# Online Learning and Planning in Cognitive Hierarchies

Bernhard Hengst  Maurice Pagnucco  David Rajaratnam
Claude Sammut and Michael Thielscher
School of Computer Science and Engineering
The University of New South Wales, Australia

###### Abstract

Complex robot behaviour typically requires the integration of multiple robotic
and Artificial Intelligence (AI) techniques and components. Integrating such
disparate components into a coherent system, while also ensuring global
properties and behaviours, is a significant challenge for cognitive robotics.
Using a formal framework to model the interactions between components can be
an important step in dealing with this challenge. In this paper we extend an
existing formal framework Clark et al. (2016) to model complex integrated
reasoning behaviours of robotic systems; from symbolic planning through to
online learning of policies and transition systems. Furthermore the new
framework allows for a more flexible modelling of the interactions between
different reasoning components.

##  1 Introduction

Complex robot behaviour typically requires the integration of multiple robotic
and Artificial Intelligence (AI) techniques and components. For example, a
typical social/domestic robot must integrate vision, speech recognition,
motion planning, as well as high-level control. More concretely, the object
manipulation task, where a robot must manipulate objects to achieve a goal,
requires the combination of high-level task planning as well as geometric
reasoning and motion planning Lozano-Pérez et al. (1987). Integrating such
disparate components into a coherent system, while also ensuring global
properties and behaviours, is a significant challenge for robotics.

Prior research in this area has mostly focused on integrating components on a
case-by-case basis. For example, the object manipulation challenge has been
tackled by combining symbolic planning with probabilistic sampling Cambon et
al. (2009); Garrett et al. (2014). However, such individual cases do not
address the larger challenge of developing general principles for integration
or incorporating sub-systems into larger, more complex, systems.

Dealing with the more general integration issue has largely been left as a
software development challenge. Diagrammatic or descriptive modelling is
performed, for example using the Robot Control System (RCS) Albus and Meystel
(2001), followed by integration using a software framework, such as ROS
Quigley et al. (2009). However, while software frameworks provide the
programming tools and middleware required to build and integrate robotic
components, they do not, and were not intended to, provide a structured basis
on which to analyse robot design and establish global behavioural properties.
As a result, while the behaviour of individual components of a system may be
well-understood, the behaviour of the system as a whole is often unclear.

A solution to this problem has been to use a formal framework for integrating
disparate representations into a cognitive hierarchy. The framework introduced
by Clark et al. (2016), and extended by Hengst et al. (2018), adopts a meta-
theoretic approach to modelling cognitive robotic systems. It formalises the
interaction between nodes in a cognitive hierarchy, while making no
commitments about the details within individual nodes. It presents the
possibility for a more structured approach to the integration challenge and
the potential for establishing global properties of a system.

As it stands, the formal framework has been mainly applied to cases where the
robot’s behaviour has been largely reactive, and has only limited support for
more complex deliberative reasoning, such as online learning and planning. In
this paper we extend the formal meta-theory to provide the flexibility
required to capture a wider variety of deliberative behaviour; from planning
through to online learning of policies and transition models. Furthermore our
new framework allows for a greater flexibility in propagating the utilities of
actions between levels of a cognitive hierarchy.

The rest of the paper proceeds as follows. We first provide a brief overview
of the notion of a cognitive hierarchy and the underlying intuitions necessary
to understand the formal framework. We then present a motivating example to
serve as a running example that shows how symbolic planning and reinforcement
learning can be integrated into a cognitive hierarchy. Next, the formal
framework will be presented and properties shown, highlighting how our
extension differs from the original. We will then finish with a discussion of
the formal developments and some complexity considerations, with reference to
the motivating example.

##  2 Cognitive Hierarchy Overview

We start here with a brief overview of some of the underlying ideas and
intuitions of the theory. A cognitive hierarchy (Figure 1) consists of a set
of nodes, where a node has two primary functions: world-modelling and
behaviour-generation. World-modelling involves maintaining a _belief state_ ,
while behaviour-generation is achieved through _policies_ , where a policy
maps states to sets of actions.

Figure 1: Overview of a Cognitive Hierarchy

The belief state of a high-level node represents an abstraction of the belief
state of lower-level nodes, ultimately abstracting from the physical
environment. These belief states are updated through sensing. Similarly,
actions at a high-level successively reduce to low-level actions that drive
physical actuators. The external world itself can be modelled simply as a
lowest-level node, albeit a node with opaque internal behaviour that is
accessed only through sensing and actions.

A _process model_ is required to specify how a cognitive hierarchy is updated.
In the model by Clark et al. (2016) a simple two step process was defined,
consisting of a sensing pass followed by an action generation pass.
Unfortunately, such a model is no longer adequate for scenarios that
incorporate online learning and planning. Consequently, we introduce a multi-
stage process model (Figure 1) involving a number of distinct passes up and
down the cognitive hierarchy .

First, a _prediction update_ is performed down the hierarchy, updating how the
robot predicts the external world will change. Next a _correction update_
progressively corrects the predicted belief states based on actual
observations of the external world. Thirdly, comparing the change between
observations, a _transition function update_ is performed to learn or refine
each node’s transition model. Fourthly, a _utility update_ is performed
whereby costs of lower-level actions are passed up for use by higher-level
action planners/learners. Finally, the _action update_ phase selects policies
which results in action selection down the hierarchy.

##  3 Motivating Scenario

As an explanatory aid to formalising the integration of planning and learning
in a cognitive hierarchy we consider the task of a robot that needs to reach a
goal by navigating between rooms (Figure 2 (a)). While we allow for
stochasticity of robot motion, for example due to slipping of the wheels, for
the simplicity of presentation we assume that the robot is able to accurately
sense its location within the environment.

(a)

(b)

(c)

Figure 2: A model for robot navigation with stochastic robot motion. Rooms are
identical except that doorways may differ for individual rooms. The robot and
goal are located in rooms R4 and R3 respectively.

This problem can be modelled as a three level cognitive hierarchy (Figure 2
(c)); a lowest-level node representing the external world, a lower-level node
for learning motion control and costs, and a higher-level node for planning
abstract actions to move between rooms. At the planning level there are two
(loop free) paths for the robot to reach the goal: R4-R5-R3 and R4-R1-R2-R3.
From a global perspective path R4-R5-R3 traverses fewer doorways while path
R4-R1-R2-R3 is a shorter distance. However, determining which of these is
optimal requires accounting for the stochastic motion of the robot. For
example, if high-precision movements are difficult then it may be preferable
to minimise the doorways traversed rather than minimising the distance
travelled.

To highlight the learning of the motion model we simplify the scenario to
ensure that each room is identical except for the presence of the key features
of the doorways and the goal location (Figure 2 (b)). Consequently, at the
lower-level the system learns both a transition model as well as an action
model for moving to the different features within a room.

A key contribution of this paper is to show how different robotic and AI
techniques can be combined in a principled manner within a single robotic
system. The example illustrates this point by constructing a simple integrated
system where a high-level symbolic planner is able to determine optimal paths
using cost information extracted from a low-level transition model learnt
through reinforcement learning.

##  4 Cognitive Hierarchy Meta-Theory

For the sake of brevity the following presentation both summarises and extends
the formalisation of cognitive hierarchies as introduced in Clark et al.
(2016), and extended in Hengst et al. (2018). We shall, however, highlight how
our contribution differs from these earlier works. The essence of this
framework is to adopt a meta-theoretic approach, formalising the interaction
between abstract cognitive nodes, while making no commitments about the
representation and reasoning mechanism within individual nodes.

###  4.1 Nodes

Nodes in a cognitive hierarchy achieve goals through maintaining a belief
state and a policy. The belief state can be modified through two distinct
mechanisms: by sensing lower-level nodes (_correction update_) or by the
combination of actions and higher-level context (_prediction update_). The
prediction update involves applying a transition model of how the world
changes, which itself can be learnt. As well as modelling observed changes in
the world a robot also takes actions. Actions are selected by applying the
belief state to a policy. The appropriate policy is determined by a planning
(or learning) operator that selects a policy based on the transition model,
action costs, and the goals to be achieved.

######  Definition 1.

A cognitive language is a tuple $\mbox{${\cal L}$}=(\mbox{${\cal
S}$},\mbox{${\cal A}$},\mbox{${\cal T}$},\mbox{${\cal O}$},\mbox{${\cal
C}$},\mbox{${\cal P}$},\mbox{${\cal U}$})$, where ${\cal S}$ is a set of
belief states, ${\cal A}$ is a set of actions, ${\cal T}$ is a set of task
parameters, ${\cal O}$ is a set of observations, and ${\cal C}$ is a set of
contextual elements, ${\cal P}$ is a set of internal planning states, and
${\cal U}$ is a set of utilities.

A cognitive node is a tuple $\mbox{${N}$}=(\mbox{${\cal
L}$},\mbox{$\Pi$},\mbox{${\Gamma}$},\mbox{$\lambda$},\mbox{$\mu$},\mbox{$\tau$},\mbox{${\delta}$},\mbox{$\gamma$}^{0},\mbox{$\pi$}^{0},\mbox{$s$}^{0},\mbox{$p$}^{0})$
s.t:

  * •

${\cal L}$ is the cognitive language for ${N}$, with initial belief state
$\mbox{$s$}^{0}\in\mbox{${\cal S}$}$, and initial planning state
$\mbox{$p$}^{0}\in\mbox{${\cal P}$}$.

  * •

An observation update operator $\mbox{$\tau$}:\mbox{${\cal S}$}\times
2^{\mbox{\scriptsize${\mbox{${\cal O}$}}$}}\rightarrow\mbox{${\cal S}$}$.

  * •

${\delta}$ is a utility update function such that
$\mbox{${\delta}$}:\mbox{${\cal P}$}\times 2^{\mbox{\scriptsize${\mbox{${\cal
U}$}}$}}\rightarrow\mbox{${\cal P}$}$.

  * •

${\Gamma}$ is a set of transition functions such that for all
$\mbox{$\gamma$}\in\mbox{${\Gamma}$}$, $\mbox{$\gamma$}:\mbox{${\cal
S}$}\times 2^{\mbox{\scriptsize${\mbox{${\cal C}$}}$}}\times
2^{\mbox{\scriptsize${\mbox{${\cal A}$}}$}}\rightarrow\mbox{${\cal S}$}$ with
initial transition function $\mbox{$\gamma$}^{0}\in\mbox{${\Gamma}$}$.

  * •

A transition learning operator
$\mbox{$\mu$}:\mbox{${\Gamma}$}\times\mbox{${\cal S}$}\times
2^{\mbox{\scriptsize${\mbox{${\cal C}$}}$}}\times
2^{\mbox{\scriptsize${\mbox{${\cal A}$}}$}}\times\mbox{${\cal
S}$}\rightarrow\mbox{${\Gamma}$}$.

  * •

$\Pi$ is a set of policies such that for all $\mbox{$\pi$}\in\mbox{$\Pi$}$,
$\mbox{$\pi$}:\mbox{${\cal S}$}\rightarrow 2^{\mbox{\scriptsize${\mbox{${\cal
A}$}}$}}$ and initial policy $\mbox{$\pi$}^{0}\in\mbox{$\Pi$}$.

  * •

A planning operator
$\mbox{$\lambda$}\\!:\\!\mbox{$\Pi$}\\!\times\\!\mbox{${\cal
P}$}\\!\times\\!\mbox{${\Gamma}$}\\!\times\\!2^{\mbox{\scriptsize${\mbox{${\cal
T}$}}$}}\\!\times\\!\mbox{${\cal
S}$}\rightarrow\mbox{$\Pi$}\\!\times\\!\mbox{${\cal P}$}$.

Definition 1 differs from the original in two important respects. First, it
allows for learning of the transition function through the use of a
_transition learning operator_. Secondly, it allows for planning (or learning
of an action policy) through the use of a richer function for policy
selection.

An _internal planning state_ provides a mechanism to model complex planning
behaviour operating over multiple calls to the planning function. For example,
for a given belief state, the planning function might initially return a do-
nothing action, when the underlying planner has not had time to find a plan,
but return a plan on subsequent calls. The planning operator also incorporates
utilities, where determining the costs of individual actions requires knowing
the cost of executing the underlying low-level actions. A _utility update
function_ incorporates these costs into the planner’s internal state.

The motivating example can now be instantiated with low and high level nodes.
The low-level node is encoded as a simple Q-learner Watkins and Dayan (1992)
that learns the transition function and policy to navigate within a room.

######  Example.

For the sub-symbolic node $\mbox{${N}$}_{1}$, the belief state $\mbox{${\cal
S}$}_{1}$ consist of the robot’s room location
$R_{1}=\\{\mbox{\text{\footnotesize{r1}}},\ldots,\mbox{\text{\footnotesize{r5}}}\\}$
and grid $G_{1}=\\{0,\ldots,9\\}\times\\{0,\ldots,10\\}$, i.e. $\mbox{${\cal
S}$}_{1}=R_{1}\times G_{1}$. The model of a robot with perfect sensing
simplifies the set of observations, so $\mbox{${\cal O}$}_{1}=\mbox{${\cal
S}$}_{1}$, and the observation update operator $\tau$ simply replaces the
current belief state with the observation.

The robot can perform four distinct actions $\mbox{${\cal
A}$}_{1}=\\{\mbox{${N}$},\mbox{${S}$},\mbox{${E}$},\mbox{${W}$}\\}$ intending
to move one step north, south, east, and west respectively. The task
parameters $\mbox{${\cal
T}$}_{1}=\\{\mbox{\text{\footnotesize{d1}}},\ldots,\mbox{\text{\footnotesize{d6}}},\mbox{\text{\footnotesize{goal}}}\\}$
encode the intra-room navigation destinations, in particular the goal and the
six numbered doors (Figure 2). We do not require context from the higher-level
node so $\mbox{${\cal C}$}_{1}=\\{\\}$, and since the lower level node
$\mbox{${N}$}_{0}$ is the external world there are no utilities being supplied
from below so $\mbox{${\cal U}$}_{1}=\\{\\}$. Wheel slippage is simulated by
$\mbox{${N}$}_{0}$ moving the robot $80\%$ in the intended direction and
$20\%$ randomly to either side.

Since all rooms are similar, the $\mbox{${N}$}_{1}$ transition and planning
functions use a projected state space $\\{\langle\cdot,g_{1}\rangle|g_{1}\in
G_{1}\\}$ represented by just grid locations for a typical relativised room.
The transition function $\mbox{$\gamma$}_{1}$ keeps a tally of how many times
a successor state is reached from a previous state and action. The planning
state $\mbox{$p$}_{1}$ comprises the reinforcement learning $Q$-values, one
set for each task parameter. The planning operator $\mbox{$\lambda$}_{1}$ uses
the latest transition function to update the $Q$-values in a value iteration
process known as temporal difference learning. Each primitive action is
assumed to incur a unit cost. The greedy policy
$\mbox{$\pi$}_{1}(\langle\cdot,g_{1}\rangle)=argmax_{a}Q$-value$(\langle\cdot,g_{1}\rangle,\;a,\;t_{1})$,
$t_{1}\in\mbox{${\cal T}$}_{1}$.

In contrast to the low-level’s reinforcement learner, the high-level node is
instantiated with a symbolic planner. We use Answer Set Programming (ASP)
Gelfond (2008) to represent the planning problem, and generate solutions using
the ASP solver Clingo Gebser et al. (2011). The solver returns models that
represent solutions to the planning problem.

######  Example.

The belief state of the symbolic node $\mbox{${N}$}_{2}$, consists of the
robot’s room location and whether it is at a specific feature; let
$F=\\{\mbox{\text{\footnotesize{d1}}},\ldots,\mbox{\text{\footnotesize{d6}}},\mbox{\text{\footnotesize{goal}}}\\}$
then $\mbox{${\cal S}$}_{2}=\\{\mbox{\text{\footnotesize{at}}}(r,f)\mid
r\in\\{\mbox{\text{\footnotesize{r1}}},\ldots,\mbox{\text{\footnotesize{r5}}}\\},f\in
F\cup\\{\mbox{\text{\footnotesize{unkn}}}\\}\\}$, where unkn denotes that the
robot is not at a known feature. Observations simply replace the belief state
so $\mbox{${\cal O}$}_{2}=\mbox{${\cal S}$}_{2}$. The actions consist of
either traversing a doorway in a room or moving to the goal location,
$\mbox{${\cal A}$}_{2}=\\{\mbox{\text{\footnotesize{trv}}}(d)\mid
d\in\\{\mbox{\text{\footnotesize{d1}}},\ldots,\mbox{\text{\footnotesize{d6}}}\\}\\}\cup\\{\mbox{\text{\footnotesize{mv\\_goal}}}\\}$.

The rooms and doorways are fixed so, in the following ASP fragment, we
consider a fixed transition function $\mbox{$\gamma$}^{0}_{2}$ to encode the
movements between rooms and the goal (Figure 2):

⬇

time(0..10). % 10 step time horizon

goal_in(r3). % goal is in R3

conn(r1,d4,r2,d3). % R1-D4 connects to R2-D3

conn(r1,d6,r4,d1). ... conn(r5,d2,r3,d5).

% precondition axioms

poss(mv_goal,T) :- at(R,L,T), L != goal, goal_in(R).

poss(trv(D1)),T) :- at(R1,_,T), conn(R1,D1,R2,D2).

% successor state axioms

at(R,goal,T+1) :- robot_at(R,_,T), do(mv_goal,T).

at(R2,D2,T+1) :-

do(trv(D1),T), in(R1,_,T), conn(R1,D1,R2,D2).

A plan requires a sequence of actions that reaches the goal:

⬇

1 { do(A,T):poss(A,T)} 1 :- time(T), not done(T).

done(T) :- at(_,goal,T).

done(T+1) :- done(T), time(T).

done :- done(T).

:- not done.

Plan generation needs to take into account action costs. The utility for the
node consists of a pair of functions; the first returns the cost of navigating
from the robot’s current location in a room to features in that room, and the
second returns the cost of navigating between features within a room;
$\mbox{${\cal
U}$}_{2}=\\{\langle\mbox{\text{\footnotesize{ctf}}}:F\rightarrow\mathbb{I},\mbox{\text{\footnotesize{cbf}}}:F\times
F\rightarrow\mathbb{I}\rangle\\}$. The sum of the cost of each action can then
be minimised:

⬇

cost(trv(D),T,C) :- at(R,unkn,T), do(trv(D),T), ctf(D,C).

cost(mv_goal,T,C) :-

at(R,unkn,T), do(mv_goal,T), ctf(goal,C).

cost(traverse(D),T,C) :-

at(R,F,T), F != unkn, do(trv(D),T), cbf(F,D,C).

cost(mv_goal,T,C) :-

at(R,F,T), F != unkn, do(mv_goal,T), cbf(F,goal,C).

#minimize { C,A,T : cost(A,T,C) }. % minimise plan cost

###  4.2 Cognitive Hierarchy

Nodes are interlinked in a hierarchy, where sensing data and utilities are
passed up the _abstraction hierarchy_ , while actions and context are passed
down the hierarchy (Figure 3).

Figure 3: A cognitive hierarchy, highlighting the flow of sensing, utilities,
action, and context data. Except for sensing and acting the behaviour of
$\mbox{${N}$}_{0}$ is opaque.

######  Definition 2.

A cognitive hierarchy is a tuple $\mbox{$H$}=(\mbox{${\cal
N}$},\mbox{${N}$}_{0},\mbox{${F}$})$ s.t:

  * •

${\cal N}$ is a set of cognitive nodes and $\mbox{${N}$}_{0}\in\mbox{${\cal
N}$}$ is a distinguished node corresponding to the external world.

  * •

${F}$ is a set of function tuples
$\langle\mbox{$\phi$}_{i,j},\mbox{$\varrho$}_{j,i},\mbox{$\sigma$}_{i,j},\mbox{$\psi$}_{j,i}\rangle\in\mbox{${F}$}$
that connect nodes $\mbox{${N}$}_{i},\mbox{${N}$}_{j}\in\mbox{${\cal N}$}$
where:

    * –

$\mbox{$\phi$}_{i,j}:\mbox{${\cal S}$}_{i}\rightarrow
2^{\mbox{\scriptsize${\mbox{${\cal O}$}_{j}}$}}$ is a sensing function, and

    * –

$\mbox{$\varrho$}_{j,i}:\mbox{${\cal S}$}_{j}\rightarrow
2^{\mbox{\scriptsize${\mbox{${\cal C}$}_{i}}$}}$ is a context enrichment
function.

    * –

$\mbox{$\sigma$}_{i,j}:\mbox{${\cal P}$}_{i}\rightarrow
2^{\mbox{\scriptsize${\mbox{${\cal U}$}_{j}}$}}$ is a utility enrichment
function.

    * –

$\mbox{$\psi$}_{j,i}:2^{\mbox{\scriptsize${\mbox{${\cal
A}$}_{j}}$}}\rightarrow 2^{\mbox{\scriptsize${\mbox{${\cal T}$}_{i}}$}}$ is a
task parameter function.

  * •

Upward graph: each $\mbox{$\phi$}_{i,j}$ represents an edge from node
$\mbox{${N}$}_{i}$ to $\mbox{${N}$}_{j}$ and forms a directed acyclic graph
(DAG) with $\mbox{${N}$}_{0}$ as the unique source node of the graph.

  * •

Downward graph: the set of task parameter functions forms a converse to the
upward graph such that $\mbox{${N}$}_{0}$ is the unique sink node of the
graph.

Definition 2 differs from Hengst et al. (2018) with the introduction of the
_utility enrichment_ functions and the naming of the graphs (previously
sensing and prediction graphs). These functions provide the connection between
nodes. For example the sensing function extracts observations from the belief
state of a lower-level node, while the utility function allows the cost of
actions from a lower-level node to be passed to the planner of a higher-level
node.

The running example can now be encoded formally as a cognitive hierarchy,
again with the following showing only the salient features of the encoding.

######  Example.

Let $\mbox{$H$}=(\mbox{${\cal N}$},\mbox{${N}$}_{0},\mbox{${F}$})$ where
$\mbox{${\cal N}$}=\\{\mbox{${N}$}_{0},\mbox{${N}$}_{1},\mbox{${N}$}_{2}\\}$
and
$\mbox{${F}$}=\\{\langle\mbox{$\phi$}_{0,1},\mbox{$\varrho$}_{1,0},\mbox{$\sigma$}_{0,1},\mbox{$\psi$}_{1,0}\rangle,\langle\mbox{$\phi$}_{1,2},\mbox{$\varrho$}_{2,1},\mbox{$\sigma$}_{1,2},\mbox{$\psi$}_{2,1}\rangle\\}$
s.t.:
$\phi$_0,1($s$_0 ∈${\cal S}$_0) = {⟨r,x,y⟩} , for robot location $\langle
r,x,y\rangle$.$\phi$_1,2:⟨r,x,y⟩↦{⟨r,f ⟩}, where $f$ is the feature atlocation
$x,y$, or unkn if there is no such feature.$\sigma$_1,2($p$∈${\cal P}$) =
{⟨ctf,cbf⟩}, where ctf and cbf aregenerated from the Q-values of node
$\mbox{${N}$}_{1}$.$\psi$_2,1:{trv(d)} ↦{d}, where $d$ is the given
doorway.{mv_goal} ↦{goal}$\psi$_1,0:{${N}$} ↦{⟨0,-1⟩}, {${S}$} ↦{⟨0,1⟩}{${W}$}
↦{⟨-1,0⟩}, {${E}$} ↦{⟨1,0⟩}, where$\langle\\{-1,0,1\\},\\{-1,0,1\\}\rangle$
can be understood assignals to drive a robot base.For
$\mbox{$\varrho$}_{1,0},\mbox{$\varrho$}_{2,1},\mbox{$\sigma$}_{0,1}$ the
functions return the empty set.

###  4.3 Active Cognitive Hierarchy

In order to formalise the behaviour of an operational cognitive system,
additional definitions are required. The following are modified from the
original in order to add support for learning and the requirements of a more
complex process model.

######  Definition 3.

An active cognitive node is a tuple
$\mbox{$Q$}=(\mbox{${N}$},\mbox{$\gamma$},\mbox{$\pi$},\mbox{$s$}^{c},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\gamma$}}$}},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\tau$}}$}},\mbox{$p$})$
where: 1) ${N}$ is a cognitive node with ${\cal S}$, $\Pi$, ${\Gamma}$, and
${\cal P}$ being its set of belief states, set of policies, set of transition
functions, and internal planning states respectively, 2)
$\mbox{$s$}^{c},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\gamma$}}$}},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\tau$}}$}}\in\mbox{${\cal
S}$}$ is, respectively, the current belief states, and two intermediate belief
states, 3) $\mbox{$\gamma$}\in\mbox{${\Gamma}$}$ and
$\mbox{$\pi$}\in\mbox{$\Pi$}$ is the current transition function and policy
respectively, and $\mbox{$p$}\in\mbox{${\cal P}$}$ is the current internal
planning state.

Essentially an active cognitive node couples a (static) cognitive node with
some dynamic information. A similar coupling is also performed for the
hierarchy itself.

######  Definition 4.

An active cognitive hierarchy is a tuple $\mbox{$\cal
X$}=(\mbox{$H$},\mbox{$\cal Q$})$ where $H$ is a cognitive hierarchy with set
of cognitive nodes ${\cal N}$ such that for each $\mbox{${N}$}\in\mbox{${\cal
N}$}$ there is a corresponding active cognitive node
$\mbox{$Q$}=(\mbox{${N}$},\mbox{$\gamma$},\mbox{$\pi$},\mbox{$s$}^{c},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\gamma$}}$}},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\tau$}}$}},\mbox{$p$})\in\mbox{$\cal
Q$}$ and vice-versa.

The active cognitive hierarchy captures the dynamic state of a system at a
particular instance in time. Finally, an _initial active cognitive hierarchy_
is an active hierarchy where each node is initialised with the initial
transition function $\mbox{$\gamma$}^{0}$, policy $\mbox{$\pi$}^{0}$, and
belief state $\mbox{$s$}^{0}$ (for $\mbox{$s$}^{c}$,
$\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\gamma$}}$}}$ and
$\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\tau$}}$}}$) of the corresponding
cognitive node.

###  4.4 Cognitive Process Model

The _process model_ defines how an active cognitive hierarchy evolves over
time. The process model from Hengst et al. (2018) consists of two steps, a
sensing update followed by an action update. Unfortunately this model is no
longer adequate for the requirements of learning and planning, and we now
formally define the process model consisting of the five distinction passes
outlined in Section 2.

To define the process model we first define the updating of a single node, and
then define the updating of the entire hierarchy. The intuition behind a node
update function is that given a cognitive hierarchy and a node, the function
returns an identical hierarchy except for the updated node. We define five
functions to match the five passes of the hierarchy.

######  Definition 5.

Let $\mbox{$\cal X$}\\!=\\!(\mbox{$H$},\mbox{$\cal Q$})$ be an active
cognitive hierarchy with $\mbox{$H$}\\!=\\!(\mbox{${\cal
N}$},\mbox{${N}$}_{0},\mbox{${F}$})$. The prediction update of $\cal X$ with
respect to an active cognitive node
$\mbox{$Q$}_{i}\\!=\\!(\mbox{${N}$}_{i},\mbox{$\gamma$}_{i},\mbox{$\pi$}_{i},\mbox{$s$}^{c}_{i},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\gamma$}}$}}_{i},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\tau$}}$}}_{i},\mbox{$p$}_{i})\in\mbox{$\cal
Q$}$, written as $\mbox{\text{\bf PredictionUpdate}}(\mbox{$\cal
X$},\mbox{$Q$}_{i})$ is $\cal X$ if $i=0$, else is an active cognitive
hierarchy $\mbox{$\cal X$}^{\prime}=(\mbox{$H$},\mbox{$\cal Q$}^{\prime})$
where $\mbox{$\cal Q$}^{\prime}=\mbox{$\cal
Q$}\\!\setminus\\!\\{\mbox{$Q$}_{i}\\}\cup\\{\mbox{$Q$}_{i}^{\prime}\\}$ and
$\mbox{$Q$}^{\prime}_{i}=(\mbox{${N}$}_{i},\mbox{$\gamma$}_{i},\mbox{$\pi$}_{i},\mbox{$s$}^{c}_{i},\mbox{$s$},\mbox{$s$},\mbox{$p$}_{i})$
s.t:
$\begin{array}[t]{l@{}l@{}l@{}l@{}l}&\mbox{$s$}&~{}={}&\lx@intercol\mbox{$\gamma$}_{i}(\mbox{$s$}^{c}_{i},C,\mbox{$\pi$}_{i}(\mbox{$s$}^{c}_{i})),\hfil\lx@intercol\\\
&C&~{}={}&\bigcup~{}\\{&\mbox{$\varrho$}_{x,i}(\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\gamma$}}$}}_{x})~{}|~{}\langle\mbox{$\phi$}_{i,x},\mbox{$\varrho$}_{x,i},\mbox{$\sigma$}_{i,x},\mbox{$\psi$}_{x,i}\rangle\in\mbox{${F}$}\mbox{~{}for~{}}\\\
&&&&~{}\mbox{$Q$}_{x}=(\mbox{${N}$}_{x},\mbox{$\gamma$}_{x},\mbox{$\pi$}_{x},\mbox{$s$}^{c}_{x},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\gamma$}}$}}_{x},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\tau$}}$}}_{x},\mbox{$p$}_{x})\in\mbox{$\cal
Q$}\\}\\\ \end{array}$

Definition 5 performs a prediction update on a node, applying the transition
function to the current belief state, the context, and actions. Note, since we
have no access to the external world other than sensing and undertaking
physical actions, the update function produces no change if the selected node
is $\mbox{${N}$}_{0}$. This will similarly be the case for the transition
learning, and utility update functions.

######  Definition 6.

Let $\mbox{$\cal X$}\\!=\\!(\mbox{$H$},\mbox{$\cal Q$})$ be an active
cognitive hierarchy with $\mbox{$H$}\\!=\\!(\mbox{${\cal
N}$},\mbox{${N}$}_{0},\mbox{${F}$})$. The correction update of $\cal X$ with
respect to an active cognitive node
$\mbox{$Q$}_{i}\\!=\\!(\mbox{${N}$}_{i},\mbox{$\gamma$}_{i},\mbox{$\pi$}_{i},\mbox{$s$}^{c}_{i},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\gamma$}}$}}_{x},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\tau$}}$}}_{x},\mbox{$p$}_{i})\in\mbox{$\cal
Q$}$, written as $\mbox{\text{\bf CorrectionUpdate}}(\mbox{$\cal
X$},\mbox{$Q$}_{i})$ is:

  * •

$\cal X$, if $i=0$ or there does not exist a node $\mbox{${N}$}_{x}$ such that
$\langle\mbox{$\phi$}_{x,i},\mbox{$\varrho$}_{i,x},\mbox{$\sigma$}_{x,i},\mbox{$\psi$}_{i,x}\rangle\\!\in\\!\mbox{${F}$}$

  * •

an active cognitive hierarchy $\mbox{$\cal
X$}^{\prime}=(\mbox{$H$},\mbox{$\cal Q$}^{\prime})$ where
$\mbox{$\cal Q$}^{\prime}=\mbox{$\cal
Q$}\setminus\\{\mbox{$Q$}_{i}\\}\cup\\{\mbox{$Q$}_{i}^{\prime}\\}$ and
$\mbox{$Q$}^{\prime}_{i}=(\mbox{${N}$}_{i},\mbox{$\gamma$}_{i},\mbox{$\pi$}_{i},\mbox{$s$}^{c}_{i},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\gamma$}}$}}_{x},\mbox{$\tau$}_{i}(O,\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\tau$}}$}}_{i}),\mbox{$p$}_{i})$
s.t:
$\begin{array}[t]{l@{}l@{}l@{}l@{}l}{}{}{}&O={}&\bigcup\\{&\mbox{$\phi$}_{x,i}(\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\tau$}}$}}_{x})~{}|~{}\langle\mbox{$\phi$}_{x,i},\mbox{$\varrho$}_{i,x},\mbox{$\sigma$}_{x,i},\mbox{$\psi$}_{i,x}\rangle\\!\in\\!\mbox{${F}$}\mbox{~{}for~{}}\\\
&&&~{}\mbox{$Q$}_{x}=(\mbox{${N}$}_{x},\mbox{$\gamma$}_{i},\mbox{$\pi$}_{i},\mbox{$s$}^{c}_{x},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\gamma$}}$}}_{x},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\tau$}}$}},\mbox{$p$}_{x})\in\mbox{$\cal
Q$}\\}\\\ \end{array}$

Definition 6 establishes how to update the current belief state of a node
based on sensing observations.

######  Definition 7.

Let $\mbox{$\cal X$}\\!=\\!(\mbox{$H$},\mbox{$\cal Q$})$ be an active
cognitive hierarchy with $\mbox{$H$}\\!=\\!(\mbox{${\cal
N}$},\mbox{${N}$}_{0},\mbox{${F}$})$. The update of the transition function of
$\cal X$ with respect to an active cognitive node
$\mbox{$Q$}_{i}\\!=\\!(\mbox{${N}$}_{i},\mbox{$\gamma$}_{i},\mbox{$\pi$}_{i},\mbox{$s$}^{c}_{i},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\gamma$}}$}}_{i},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\tau$}}$}}_{i},\mbox{$p$}_{i})\in\mbox{$\cal
Q$}$, written as $\mbox{\text{\bf TransFuncUpdate}}(\mbox{$\cal
X$},\mbox{$Q$}_{i})$ is $\cal X$, if $i=0$ else is an active cognitive
hierarchy $\mbox{$\cal X$}^{\prime}=(\mbox{$H$},\mbox{$\cal Q$}^{\prime})$
where $\mbox{$\cal Q$}^{\prime}=\mbox{$\cal
Q$}\\!\setminus\\!\\{\mbox{$Q$}_{i}\\}\cup\\{\mbox{$Q$}_{i}^{\prime}\\}$ and
$\mbox{$Q$}^{\prime}_{i}=(\mbox{${N}$}_{i},\mbox{$\mu$}(\mbox{$\gamma$}_{i},\mbox{$s$}^{c}_{i},C,\mbox{$\pi$}_{i}(\mbox{$s$}^{c}_{i}),\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\tau$}}$}}_{i}),\mbox{$\pi$}_{i},\mbox{$s$}^{c}_{i},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\gamma$}}$}}_{i},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\tau$}}$}}_{i},\mbox{$p$}_{i})$
s.t:
$\begin{array}[t]{l@{}l@{}l@{}l@{}l}&C&~{}=~{}\bigcup\\{&\mbox{$\varrho$}_{x,i}(\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\gamma$}}$}}_{x})~{}|~{}\langle\mbox{$\phi$}_{i,x},\mbox{$\varrho$}_{x,i},\mbox{$\sigma$}_{i,x},\mbox{$\psi$}_{x,i}\rangle\in\mbox{${F}$}\mbox{~{}for~{}}\\\
&&&~{}\mbox{$Q$}_{x}=(\mbox{${N}$}_{x},\mbox{$\gamma$}_{x},\mbox{$\pi$}_{x},\mbox{$s$}^{c}_{x},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\gamma$}}$}}_{x},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\tau$}}$}}_{x},\mbox{$p$}_{x})\in\mbox{$\cal
Q$}\\}\\\ \end{array}$

Definition 7 establishes the updating of the state transition function for the
node. This learning phase selects a new state transition function based on the
previous transition function, as well as the previous and currently observed
states and the actions (and context) that lead to the new observed state.

######  Definition 8.

Let $\mbox{$\cal X$}\\!=\\!(\mbox{$H$},\mbox{$\cal Q$})$ be an active
cognitive hierarchy with $\mbox{$H$}\\!=\\!(\mbox{${\cal
N}$},\mbox{${N}$}_{0},\mbox{${F}$})$. The utility update of $\cal X$ with
respect to an active cognitive node
$\mbox{$Q$}_{i}\\!=\\!(\mbox{${N}$}_{i},\mbox{$\gamma$}_{i},\mbox{$\pi$}_{i},\mbox{$s$}^{c}_{i},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\gamma$}}$}}_{i},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\tau$}}$}}_{i},\mbox{$p$}_{i})\in\mbox{$\cal
Q$}$, written as $\mbox{\text{\bf UtilityUpdate}}(\mbox{$\cal
X$},\mbox{$Q$}_{i})$ is $\cal X$, if $i=0$ else is an active cognitive
hierarchy $\mbox{$\cal X$}^{\prime}=(\mbox{$H$},\mbox{$\cal Q$}^{\prime})$
where $\mbox{$\cal Q$}^{\prime}=\mbox{$\cal
Q$}\\!\setminus\\!\\{\mbox{$Q$}_{i}\\}\cup\\{\mbox{$Q$}_{i}^{\prime}\\}$ and
$\mbox{$Q$}^{\prime}_{i}=(\mbox{${N}$}_{i},\mbox{$\gamma$}_{i},\mbox{$\pi$}_{i},\mbox{$s$}^{c}_{i},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\gamma$}}$}}_{i},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\tau$}}$}}_{i},\mbox{${\delta}$}_{i}(\mbox{$p$}_{i},U))$
s.t:
$\begin{array}[t]{l@{}l@{}l@{}l@{}l}&U&~{}=~{}\bigcup\\{&\mbox{$\sigma$}_{i,x}(\mbox{$p$}_{x})~{}|~{}\langle\mbox{$\phi$}_{i,x},\mbox{$\varrho$}_{x,i},\mbox{$\sigma$}_{i,x},\mbox{$\psi$}_{x,i}\rangle\in\mbox{${F}$}\mbox{~{}for~{}}\\\
&&&~{}\mbox{$Q$}_{x}=(\mbox{${N}$}_{x},\mbox{$\gamma$}_{x},\mbox{$\pi$}_{x},\mbox{$s$}^{c}_{x},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\gamma$}}$}}_{x},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\tau$}}$}}_{x},\mbox{$p$}_{x})\in\mbox{$\cal
Q$}\\}\\\ \end{array}$

The utility update function (Definition 8) updates the internal planning state
of a node with the utilities derived from the planning states of its children.

######  Definition 9.

Let $\mbox{$\cal X$}\\!=\\!(\mbox{$H$},\mbox{$\cal Q$})$ be an active
cognitive hierarchy with $\mbox{$H$}\\!=\\!(\mbox{${\cal
N}$},\mbox{${N}$}_{0},\mbox{${F}$})$. The action update of $\cal X$ with
respect to an active cognitive node
$\mbox{$Q$}_{i}\\!=\\!(\mbox{${N}$}_{i},\mbox{$\gamma$}_{i},\mbox{$\pi$}_{i},\mbox{$s$}^{c}_{i},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\gamma$}}$}}_{i},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\tau$}}$}}_{i},\mbox{$p$}_{i})\in\mbox{$\cal
Q$}$, written as $\mbox{\text{\bf ActionUpdate}}(\mbox{$\cal
X$},\mbox{$Q$}_{i})$ is an active cognitive hierarchy $\mbox{$\cal
X$}^{\prime}=(\mbox{$H$},\mbox{$\cal Q$}^{\prime})$ where $\mbox{$\cal
Q$}^{\prime}=\mbox{$\cal
Q$}\\!\setminus\\!\\{\mbox{$Q$}_{i}\\}\cup\\{\mbox{$Q$}_{i}^{\prime}\\}$ and
$\mbox{$Q$}^{\prime}_{i}=(\mbox{${N}$}_{i},\mbox{$\gamma$}_{i},\mbox{$\pi$}^{\prime}_{i},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\tau$}}$}}_{i},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\gamma$}}$}}_{i},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\tau$}}$}}_{i},\mbox{$p$}^{\prime}_{i})$
s.t:
$\begin{array}[t]{l@{}l@{}l@{}l@{}l}\lx@intercol\langle\mbox{$\pi$}^{\prime}_{i},\mbox{$p$}^{\prime}_{i}\rangle=\mbox{$\lambda$}(\mbox{$\pi$}_{i},\mbox{$\gamma$}_{i},T,\mbox{$p$}_{i},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\tau$}}$}}_{i}),\hfil\lx@intercol\\\
T&~{}=\bigcup\\{&\mbox{$\psi$}_{x,i}(\mbox{$\pi$}_{x}(\mbox{$s$}^{c}_{x}))|\langle\mbox{$\phi$}_{i,x},\mbox{$\varrho$}_{x,i},\mbox{$\sigma$}_{i,x},\mbox{$\psi$}_{x,i}\rangle\in\mbox{${F}$}\mbox{~{}for~{}}\\\
&&~{}\mbox{$Q$}_{x}=(\mbox{${N}$}_{x},\mbox{$\gamma$}_{x},\mbox{$\pi$}_{x},\mbox{$s$}^{c}_{x},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\gamma$}}$}}_{x},\mbox{$s$}^{\mbox{\scriptsize${\mbox{$\tau$}}$}}_{x},\mbox{$p$}_{x})\in\mbox{$\cal
Q$}\\}\\\ \end{array}$

Finally, the action update of a node encodes the process of the planner
selecting a new policy. It does so based on the current policy, the current
transition function, the task parameters, and the current belief state. A
secondary task of this process is to ensure that the node’s current belief
state is updated to it’s newly observed belief state.

Note, when this process is applied to the external world node,
$\mbox{${N}$}_{0}$, the intuition is that the task parameters of the directly
connected nodes, which were generated by applying the policy of those nodes to
their respective belief states, represents the robot acting on the real world.
These task parameters therefore represent physical actions, for example,
applying some voltage to an actuator for some period of time.

Now, in order to formalise the updating of a complete hierarchy, we first
introduce an intermediate function that successively applies a given function
to a sequence of nodes.

######  Definition 10.

Let $\Phi$ be a function that takes as parameters an active cognitive
hierarchy and an active cognitive node within that hierarchy, and returns
another active cognitive hierarchy. Furthermore, let $\mbox{$\cal
X$}=(\mbox{$H$},\mbox{$\cal Q$})$ be an active cognitive hierarchy, and let
${\vec{Q}}=[\mbox{$Q$}_{1},\ldots,\mbox{$Q$}_{n}]$ consist of a sequence over
all the active cognitive nodes in $\cal Q$. Then the update pass of $\Phi$
over $\cal X$ and $\vec{Q}$, written $\mbox{\text{\bf
UpdatePass}}(\Phi,\mbox{$\cal X$},\vec{Q})$, is an active cognitive hierarchy:

$\mbox{$\cal X$}^{\prime}=\Phi(\ldots\Phi(\mbox{$\cal
X$},\mbox{$Q$}_{1}),\ldots\mbox{$Q$}_{n})$

Definition 10 provides a mechanism for applying the individual node update
functions over the entire cognitive hierarchy in some order. We use this to
define the individual passes as part of a complete update of the cognitive
hierarchy.

######  Definition 11.

Let $\mbox{$\cal X$}=(\mbox{$H$},\mbox{$\cal Q$})$ be an active cognitive
hierarchy with $\Phi$ and $\Psi$ being the upward and downward graphs of $H$
respectively. The process update of $\cal X$, written $\mbox{\text{\bf
Update}}(\mbox{$\cal X$})$, is an active cognitive hierarchy:

$\mbox{$\cal X$}^{\prime}=\mbox{\text{\bf A}}(\mbox{\text{\bf
U}}(\mbox{\text{\bf T}}(\mbox{\text{\bf C}}(\mbox{\text{\bf P}}(\mbox{$\cal
X$})))))$

where:

  * •

$\mbox{\text{\bf P}}(\mbox{$\cal X$}^{\mbox{\tiny${T}$}})=\mbox{\text{\bf
UpdatePass}}(\mbox{\text{\bf PredictionUpdate}},\mbox{$\cal
X$}^{\mbox{\tiny${T}$}},\vec{Q}_{D})$

  * •

$\mbox{\text{\bf C}}(\mbox{$\cal X$}^{\mbox{\tiny${T}$}})=\mbox{\text{\bf
UpdatePass}}(\mbox{\text{\bf CorrectionUpdate}},\mbox{$\cal
X$}^{\mbox{\tiny${T}$}},\vec{Q}_{U})$

  * •

$\mbox{\text{\bf T}}(\mbox{$\cal X$}^{\mbox{\tiny${T}$}})=\mbox{\text{\bf
UpdatePass}}(\mbox{\text{\bf TransFuncUpdate}},\mbox{$\cal
X$}^{\mbox{\tiny${T}$}},\vec{Q}_{U})$

  * •

$\mbox{\text{\bf U}}(\mbox{$\cal X$}^{\mbox{\tiny${T}$}})=\mbox{\text{\bf
UpdatePass}}(\mbox{\text{\bf UtilityUpdate}},\mbox{$\cal
X$}^{\mbox{\tiny${T}$}},\vec{Q}_{U})$

  * •

$\mbox{\text{\bf A}}(\mbox{$\cal X$}^{\mbox{\tiny${T}$}})=\mbox{\text{\bf
UpdatePass}}(\mbox{\text{\bf ActionUpdate}},\mbox{$\cal
X$}^{\mbox{\tiny${T}$}},\vec{Q}_{D})$

  * •

$\vec{Q}_{U}$ is a sequence consisting of all active cognitive nodes in $\cal
Q$ such that the sequence satisfies the partial ordering induced by the upward
graph $\Phi$.

  * •

$\vec{Q}_{D}$ is a sequence consisting of all active cognitive nodes in $\cal
Q$ such that the sequence satisfies the partial ordering induced by the
downward graph $\Psi$.

Definition 11 formalises the process update model outlined in Section 2. The
cognitive hierarchy’s upward graph induces a sequence of nodes passing up the
hierarchy, while the downward graph induces a sequence passing down the
hierarchy. Depending on the particular update being performed the appropriate
sequence is chosen and the corresponding function is repeatedly applied.

Finally, to complete the formal developments, we establish the main result
that underlines the importance of the process update model, namely that it is
well-defined.

######  Theorem 1.

The cognitive process model Update is well-defined.

###### Proof.

By inspection on the five individual passes of cognitive hierarchy. The proof
that each pass is well-defined is structurally identical to the proof for
Lemma 1 from Clark et al. (2016), hinging on the partial-ordering induced by
the appropriate DAG. ∎

Theorem 1 establishes that the process model Update does indeed produce an
active cognitive hierarchy, and that there is only one possible output given
the input. Consequently, the process model performs what one would intuitively
require of an operational cognitive hierarchy; updating nodes up the hierarchy
and propagating actions back down the hierarchy, resulting in changes to the
physical actuators of a robot.

##  5 Discussion

The previous section established the cognitive hierarchy formalism. We now
turn to a discussion of its broader implications. We do so with reference to
the motivating example, and its implementation within a simulation
environment, to illustrates several of its salient features.

The importance of problem decomposition is well established in AI, from
hierarchy learning Kaelbling (1993) through to factored planning Amir and
Engelhardt (2003). Formally, the decomposition of a node into two distinct
nodes within a cognitive hierarchy can reduce an $M\times N$ search space to
an $M+N$ search space Rajaratnam et al. (2016).

Our example illustrates this point. The complexity of reinforcement learning
in grid-worlds is $O(n^{2})$, where $n$ is the size of the state-space Koenig
and Simmons (1993). The decomposition into rooms reduces complexity from order
$n^{2}=450^{2}$ to $5\times 90^{2}+5^{2}$. Additionally, the similarity of the
five rooms allows transfer learning of the transition and policy functions.
Together the decomposition reduces the complexity of learning the optimal
policy by a factor of 25. Figure 4 shows the faster convergence in the optimum
number of steps to reach the goal for the decomposed problem.

Figure 4: Learning to minimise the steps to reach the goal converges faster if
the problem is decomposed (results averaged over 10 runs).

To ensure proper behaviour with a hierarchical decomposition it is necessary
to account for action utilities. In our example, a purely abstract inter-room
planner, with no access to low-level action costs, might choose to minimise
the number of rooms to the goal rather than choosing the shortest path.
However, the cognitive hierarchy is able to account for the local intra-room
costs with the utility update and choose an optimal path that traverses three
instead of two rooms (Figure 5, left). Importantly, this behaviour is
dependent on the stochasticity of the motion model and when the amount of
slippage increases, an optimal path minimises the number of doorways as an
increasing number of attempts may be necessary to move between rooms (Figure
5, right).

Figure 5: Location visitation count for optimal policy trials ($>$ 1000). The
depth of shading indicates the frequency of visits. Increasing the slippage to
only $40\%$ in the intended direction, and $60\%$ for either side, changes the
optimal to the longer path with fewer doorways.

In our motivating example the high-level planner was able to find the optimal
path to the goal using the costs learnt by the low-level motion model.
However, in general, hierarchical reinforcement learning cannot guarantee that
a globally optimal policy will be learnt. In particular, a subtask cannot take
into account the context in which it is learnt and therefore the best that can
be hoped for is _recursive optimality_ Dietterich (2000). Recursive optimality
can be guaranteed in our mixed representation cognitive hierarchy for the
general case, where the lower-level learns without access to the high-level
context of the planner.

##  6 Conclusion and Future Work

In this paper we formalised the integration of online learning and planning,
using differing representations, within a cognitive hierarchy. This
formalisation takes the form of a meta-theory, whereby the interaction between
nodes in a hierarchy is specified while leaving open the internal details of
each node. This provides the flexibility to use arbitrary representations and
reasoning mechanisms within individual nodes. The process model, that defines
how to update an operational cognitive hierarchy, was also shown to be well-
defined.

The key features of the extended formalisation was to show how planning and
online learning can be integrated into a cognitive hierarchy. To this end a
motivating example was introduced to illustrate the power and flexibility of
the framework. The example established how a reinforcement learner could be
used to learn both a transition model and action policy for a robot moving
within a room, and how this could be combined with a symbolic planner for
navigating between rooms. Costs for low-level navigation were passed to the
high-level to ensure that the planner could find a lowest cost plan.

This work opens up a number of interesting avenues for future research. In the
first place it will be important to validate the framework on a variety of
robot platforms and problems, from simple robots with limited capabilities
through to complex robots such as those used for the Robocup@Home challenge.

A second important avenue for future work will be to explore more deeply the
interaction of learning and planning at multiple levels of the hierarchy. In
some cases it may be desirable to perform a series of what-if scenarios
involving multiple levels of the hierarchy. Interestingly, our framework could
achieve this through a process model that ignores the external world node,
$\mbox{${N}$}_{0}$. The process model would then provide a “deep” simulation
that could be used for highly deliberative reasoning.

## References

  * Albus and Meystel [2001] James S. Albus and Alexander M. Meystel.  Engineering of Mind: An Introduction to the Science of Intelligent Systems.  Wiley-Interscience, 2001.
  * Amir and Engelhardt [2003] E. Amir and B. Engelhardt.  Factored planning.  In IJCAI, pages 929–935. Morgan Kaufmann, 2003.
  * Cambon et al. [2009] Stéphane Cambon, Rachid Alami, and Fabien Gravot.  A hybrid approach to intricate motion, manipulation and task planning.  I. J. Robotics Res., 28(1):104–126, 2009.
  * Clark et al. [2016] Keith Clark, Bernhard Hengst, Maurice Pagnucco, David Rajaratnam, Peter Robinson, Claude Sammut, and Michael Thielscher.  A framework for integrating symbolic and sub-symbolic representations.  In 25th Joint Conference on Artificial Intelligence (IJCAI -16), 2016.
  * Dietterich [2000] Thomas G. Dietterich.  Hierarchical reinforcement learning with the MAXQ value function decomposition.  J. Artif. Intell. Res., 13:227–303, 2000.
  * Garrett et al. [2014] Caelan Reed Garrett, Tomás Lozano-Pérez, and Leslie Pack Kaelbling.  Ffrob: An efficient heuristic for task and motion planning.  In H. Levent Akin, Nancy M. Amato, Volkan Isler, and A. Frank van der Stappen, editors, Algorithmic Foundations of Robotics XI - Selected Contributions of the Eleventh International Workshop on the Algorithmic Foundations of Robotics, WAFR 2014, 3-5 August 2014, Boğaziçi University, İstanbul, Turkey, volume 107 of Springer Tracts in Advanced Robotics, pages 179–195. Springer, 2014.
  * Gebser et al. [2011] Martin Gebser, Roland Kaminski, Benjamin Kaufmann, Max Ostrowski, Torsten Schaub, and Marius Schneider.  Potassco: The Potsdam answer set solving collection.  AICOM, 24, 2011.  potassco.sourceforge.net/.
  * Gelfond [2008] Michael Gelfond.  Answer sets.  In F. van Harmelen, V. Lifschitz, and B. Porter, editors, Handbook of Knowledge Representation, pages 285–316. Elsevier, 2008.
  * Hengst et al. [2018] Bernhard Hengst, Maurice Pagnucco, David Rajaratnam, Claude Sammut, and Michael Thielscher.  Perceptual context in cognitive hierarchies.  CoRR, abs/1801.02270, 2018.
  * Kaelbling [1993] Leslie Pack Kaelbling.  Hierarchical learning in stochastic domains: Preliminary results.  In Machine Learning, Proceedings of the Tenth International Conference, University of Massachusetts, Amherst, MA, USA, June 27-29, 1993, pages 167–173. Morgan Kaufmann, 1993.
  * Koenig and Simmons [1993] Sven Koenig and Reid G. Simmons.  Complexity analysis of real-time reinforcement learning.  In Richard Fikes and Wendy G. Lehnert, editors, Proceedings of the 11th National Conference on Artificial Intelligence. Washington, DC, USA, July 11-15, 1993., pages 99–107. AAAI Press / The MIT Press, 1993.
  * Lozano-Pérez et al. [1987] Tomás Lozano-Pérez, Joseph L. Jones, Emmanuel Mazer, Patrick A. O’Donnell, W. Eric L. Grimson, Pierre Tournassoud, and Alain Lanusse.  Handey: A robot system that recognizes, plans, and manipulates.  In Proceedings of the 1987 IEEE International Conference on Robotics and Automation, Raleigh, North Carolina, USA, March 31 - April 3, 1987, pages 843–849. IEEE, 1987.
  * Quigley et al. [2009] Morgan Quigley, Brian Gerkey, Ken Conley, Josh Faust, Tully Foote, Jeremy Leibs, Eric Berger, Rob Wheeler, and Andrew Ng.  ROS: an open-source Robot Operating System, 2009.
  * Rajaratnam et al. [2016] David Rajaratnam, Bernhard Hengst, Maurice Pagnucco, Claude Sammut, and Michael Thielscher.  Composability in cognitive hierarchies.  In Byeong Ho Kang and Quan Bai, editors, AI 2016: Advances in Artificial Intelligence - 29th Australasian Joint Conference, Hobart, TAS, Australia, December 5-8, 2016, Proceedings, volume 9992 of Lecture Notes in Computer Science, pages 42–55. Springer, 2016.
  * Watkins and Dayan [1992] Christopher J. C. H. Watkins and Peter Dayan.  Q-learning.  Machine Learning, 8(3):279–292, May 1992.


[app-]appendix

# Large Language Models
Can Implement Policy Iteration

Ethan Brooks1, Logan Walls2, Richard L. Lewis2, Satinder Singh1
1Computer Science and Engineering, University of Michigan
2Department of Psychology, University of Michigan
<EMAIL_ADDRESS>

###### Abstract

In this work, we demonstrate a method for implementing policy iteration using
a large language model. While the application of foundation models to RL has
received considerable attention, most approaches rely on either (1) the
curation of expert demonstrations (either through manual design or task-
specific pretraining) or (2) adaptation to the task of interest using gradient
methods (either fine-tuning or training of adapter layers). Both of these
techniques have drawbacks. Collecting demonstrations is labor-intensive, and
algorithms that rely on them do not outperform the experts from which the
demonstrations were derived. All gradient techniques are inherently slow,
sacrificing the “few-shot” quality that makes in-context learning attractive
to begin with. Our method demonstrates that a large language model can be used
to implement policy iteration using the machinery of in-context learning,
enabling it to learn to perform RL tasks without expert demonstrations or
gradients. Our approach iteratively updates the contents of the prompt from
which it derives its policy through trial-and-error interaction with an RL
environment. In order to eliminate the role of in-weights learning (on which
approaches like Decision Transformer rely heavily), we demonstrate our method
using Codex [10], a language model with no prior knowledge of the domains on
which we evaluate it.

##  1 Introduction

In many settings, models implemented using a transformer or recurrent
architecture will improve their performance as information accumulated in
their context or memory. We refer to this phenomenon as “in-context learning.”
[6] demonstrated a technique for inducing this phenomenon by prompting a large
language model with a small number of input/output exemplars. An interesting
property of in-context learning in the case of large pre-trained models (or
“foundation models”) is that the models are not directly trained to optimize a
meta-learning objective, but demonstrate an emergent capacity to generalize
(or at least specialize) to diverse downstream task-distributions [36].

A litany of existing work has explored methods for applying this remarkable
capability to downstream tasks (see Related Work), including Reinforcement
Learning (RL). Most work in this area either (1) assumes access to expert
demonstrations — collected either from human experts [18, 3], or domain-
specific pre-trained RL agents [8, 22, 19, 28, 38]. — or (2) relies on
gradient-based methods — e.g. fine-tuning of the foundation models parameters
as a whole [22, 28, 3] or newly training an adapter layer or prefix vectors
while keeping the original foundation models frozen [24, 30, 20].

Our work demonstrates an approach to in-context learning which relaxes these
assumptions. Our method, In-Context Policy Iteration (ICPI), implements policy
iteration using the prompt content, instead of the model parameters, as the
locus of learning, thereby avoiding gradient methods. Furthermore, the use of
policy iteration frees us from expert demonstrations because suboptimal
prompts can be improved over the course of training.

We illustrate the method empirically on six small illustrative RL tasks—
_chain, distractor-chain, maze, mini-catch, mini-invaders_ , and _point-mass_
—in which the method very quickly finds good policies. We also compare five
pretrained Large Language Models (LLMs), including two different size models
trained on natural language—OPT-30B and GPT-J—and three different sizes of a
model trained on program code—two sizes of Codex as well as InCoder. On our
six domains, we find that only the largest model (the code-davinci-001 variant
of Codex) consistently demonstrates learning.

Figure 1: For each possible action $\mathcal{A}(1),\dots,\mathcal{A}(n)$, the
LLM generates a rollout by alternately predicting transitions and selecting
actions. Q-value estimates are discounted sums of rewards. The action is
chosen greedily with respect to Q-values. Both state/reward prediction and
next action selection use trajectories from $\mathcal{D}$ to create prompts
for the LLM. Changes to the content of $\mathcal{D}$ change the prompts that
the LLM receives, allowing the model to improve its behavior over time.

##  2 Related Work

A common application of foundation models to RL involves tasks that have
language input, for example natural language instructions/goals [14, 16] or
text-based games [27, 31, 25, 2]. Another approach encodes RL trajectories
into token sequences, and processes them with a foundation model, model
representations as input to deep RL architectures [23, 33, 32]. Finally, a
recent set of approaches treat RL as a sequence modeling problem and use the
foundation models itself to predict states or actions. This section will focus
on this last category.

###  2.1 Learning from demonstrations

Many recent sequence-based approaches to reinforcement learning use
demonstrations that come either from human experts or pretrained RL agents.
For example, [18] use a frozen LLM as a planner for everyday household tasks
by constructing a prefix from human-generated task instructions, and then
using the LLM to generate instructions for new tasks. This work is extended by
[17]. Similarly, [1] use a value function that is trained on human
demonstrations to rank candidate actions produced by an LLM. [3] use human
demonstrations to train the foundation model itself: they use video recordings
of human Minecraft players to train a foundation models that plays Minecraft.
Works that rely on pretrained RL agents include [19] who train a “Trajectory
Transformer” to predict trajectory sequences in continuous control tasks by
using trajectories generated by pretrained agents, and [8], who use a dataset
of offline trajectories to train a “Decision Transformer” that predicts
actions from state-action-reward sequences in RL environments like Atari. Two
approaches build on this method to improve generalization: [22] use
trajectories generated by a DQN agent to train a single Decision Transformer
that can play many Atari games, and [38] use a combination of human and
artificial trajectories to train a Decision Transformer that achieves few-shot
generalization on continuous control tasks. [28] take task-generality a step
farther and use datasets generated by pretrained agents to train a multi-modal
agent that performs a wide array of RL (e.g. Atari, continuous control) and
non-RL (e.g. image captioning, chat) tasks.

Some of the above works include non-expert demonstrations as well. [8] include
experiments with trajectories generated by random (as opposed to expert)
policies. [22] and [38] also use datasets that include trajectories generated
by partially trained agents in addition to fully trained agents. Like these
works, our proposed method (ICPI) does not rely on expert demonstrations—but
we note two key differences between our approach and existing approaches.
Firstly, ICPI only consumes self-generated trajectories, so it does not
require any demonstrations (like [8] with random trajectories, but unlike
[22], [38], and the other approaches reviewed above). Secondly, ICPI relies
primarily on in-context learning rather than in-weights learning to achieve
generalization (like [38], but unlike [8] & [22]). For discussion about in-
weights vs. in-context learning see [7].

###  2.2 Gradient-based Training & Finetuning on RL Tasks

Most approaches involve training or fine-tuning foundation models on RL tasks.
For example, [19, 8, 22, 38, 3, 28] all use models that are trained from
scratch on tasks of interest, and [30, 1, 17] combine frozen foundation models
with trainable components or adapters. In contrast, [18] use frozen foundation
models for planning, without training or fine-tuning on RL tasks. Like [18],
ICPI does not update the parameters of the foundation model, but relies on the
frozen model’s in-context learning abilities. However, ICPI gradually builds
and improves the prompts within the space defined by the given fixed text-
format for observations, actions, and rewards (in contrast to [18], which uses
the frozen model to select good prompts from a given fixed library of
goal/plan descriptions).

###  2.3 In-Context Learning

Several recent papers have specifically studied in-context learning. [21]
demonstrates an approach to performing in-context reinforcement learning by
training a model on complete RL learning histories, demonstrating that the
model actually distills the improvement operator of the source algorithm. [7]
and [15] provide analyses of the properties that drive in-context learning,
the first in the context of image classification, the second in the context of
regression onto a continuous function. These papers identify various
properties, including “burstiness,” model-size, and model-architecture, that
in-context learning depends on. [11] studies the sensitivity of in-context
learning to small perturbations of the context. They propose a novel method
that uses sensitivity as a proxy for model certainty.

Algorithm 1 Training Loop

1:function Train(environment)

2: initialize $\mathcal{D}$ $\triangleright$ replay buffer containing full
history of behavior

3: while training do

4: $o_{0}\leftarrow$ Reset environment.

5: while episode is not done do

6: $a_{t}\leftarrow\arg\max_{a}$ $Q$($o_{t},a,\mathcal{D}$) $\triangleright$
policy improvement

7: $o_{t+1},r_{t},b_{t}\leftarrow$ Execute $a_{t}$ in environment.

8: $t\leftarrow t+1$

9: end while

10:
$\mathcal{D}\leftarrow\mathcal{D}\cup\left(o_{0},a_{0},r_{0},b_{0},o_{1},\dots,o_{t},a_{t},r_{t},b_{t},o_{t+1}\right)$
$\triangleright$ add trajectory to buffer

11: end while

12:end function

Algorithm 2 Computing Q-values

1:function $Q$($o_{t},a,\mathcal{D}$)

2: $u\leftarrow t$

3: $o^{\left(1\right)}=o_{t}$

4: $a^{\left(1\right)}=a$

5: repeat$\triangleright$ All samples come from the experience buffer
$\mathcal{D}$

6: $\mathcal{D}_{b}\sim$ time-steps with action $a^{\left(u\right)}$
$\triangleright$ balancing terminal and non-terminal

7:
$b^{\left(u\right)}\sim\operatorname*{LLM}\left(\mathcal{D}_{b},o^{\left(u\right)},a^{\left(u\right)}\right)$

8: $\mathcal{D}_{r}\sim$ time-steps with action $a^{\left(u\right)}$ and
termination $b^{\left(u\right)}$ $\triangleright$ balancing reward

9:
$r^{\left(u\right)}\sim\operatorname*{LLM}\left(\mathcal{D}_{r},o^{\left(u\right)},a^{\left(u\right)}\right)$

10: $\mathcal{D}_{o}\sim$ time-steps with action $a^{\left(u\right)}$ and
termination $b^{\left(u\right)}$ $\triangleright$ no balancing

11:
$o^{\left(u+1\right)}\sim\operatorname*{LLM}\left(\mathcal{D}_{o},o^{\left(u\right)},a^{\left(u\right)}\right)$

12: $\mathcal{D}_{a}\sim c$ recent trajectories

13:
$a^{\left(u+1\right)}\sim\operatorname*{LLM}\left(o^{\left(u+1\right)},\mathcal{D}_{a}\right)$

14: $u\leftarrow u+1$

15: until $b^{\left(u\right)}$ is terminal

16: return $\sum_{k=1}^{u}\gamma^{k-1}r^{\left(k\right)}$

17:end function

##  3 Method

How can standard policy iteration make use of in-context learning? Policy
iteration is either model-based—using a world-model to plan future
trajectories in the environment—or model-free—inferring value-estimates
without explicit planning. Both methods can be realized with in-context
learning. We choose model-based learning because planned trajectories make the
underlying logic of value-estimates explicit to our foundation model backbone,
providing a concrete instantiation of a trajectory that realizes the values.
This ties into recent work [35, 26] demonstrating that “chains of thought” can
significantly improve few-shot performance of foundation models.

Model-based RL requires two ingredients, a rollout-policy used to act during
planning and a world-model used to predict future rewards, terminations, and
states. Since our approach avoids any mutation of the foundation model’s
parameters (this would require gradients), we must instead induce the rollout-
policy and the world-model using in-context learning, i.e. by selecting
appropriate prompts. We induce the rollout-policy by prompting the foundation
model with trajectories drawn from the current (or recent) behavior policy
(distinct from the rollout-policy). Similarly, we induce the world-model by
prompting the foundation models with transitions drawn from the agent’s
history of experience. Note that our approach assumes access to some
translation between the state-space of the environment and the medium
(language, images, etc.) of the foundation models. This explains how an
algorithm might plan and estimate values using a foundation model. It also
explains how the rollout-policy approximately tracks the behavior policy.

How does the policy improve? When acting in the environment (as opposed to
planning), we choose the action that maximizes the estimated Q-value from the
current state (see Training Loop pseudocode, line 6). At time step $t$, the
agent observes the state of the environment (denoted $s_{t}$) and executes
action $a_{t}=\arg\max_{a\in\mathcal{A}}Q^{(\pi_{t})}(o_{t},a)$, where
$\mathcal{A}=\\{\mathcal{A}(1),\cdots,\mathcal{A}(n)\\}$ denotes the set of
$n$ actions available, $\pi_{t}$ denotes the policy of the agent at time step
$t$, and $Q^{(\pi)}$ denotes the Q-estimate for policy $\pi$. Taking the
greedy ($\arg\max$) actions with respect to $Q^{\pi_{t}}$ implements a new and
improved policy.

#### Computing Q-values

This section provides details on the prompts that we use in our computation of
Q-values (see Computing Q-values pseudocode & Figure 1). During training, We
maintain a buffer $\mathcal{D}$ of transitions experienced by the agent. To
compute $Q^{(\pi_{t})}(o_{t},a)$ at time step $t$ in the real-world we rollout
a simulated trajectory $o^{\left(1\right)}=o_{t}$, $a^{\left(1\right)}=a$,
$r^{\left(1\right)}$, $o^{\left(2\right)}$, $a^{\left(2\right)}$,
$r^{\left(2\right)}$, $\cdots$, $o^{\left(T\right)}$, $a^{\left(T\right)}$,
$r^{\left(T\right)}$, $o^{\left(T+1\right)}$ by predicting, at each simulation
time step $u$: reward
$r^{\left(u\right)}\sim\operatorname*{LLM}\left(\mathcal{D}_{r},o^{\left(u\right)},a^{\left(u\right)}\right)$;
termination
$b^{\left(u\right)}\sim\operatorname*{LLM}\left(\mathcal{D}_{b},o^{\left(u\right)},a^{\left(u\right)}\right)$;
observation
$o^{\left(u+1\right)}\sim\operatorname*{LLM}\left(\mathcal{D}_{o},o^{\left(u\right)},a^{\left(u\right)}\right)$;
action
$a^{\left(1\right)}\sim\operatorname*{LLM}\left(\mathcal{D}_{a},o^{\left(u\right)}\right)$.
Termination $b^{\left(u\right)}$ decides whether the simulated trajectory ends
at step $u$.

The prompts $\mathcal{D}_{r}$, $\mathcal{D}_{b}$ contain data sampled from the
replay buffer. For each prompt, we choose some subset of replay buffer
transitions, shuffle them, convert them to text (examples are provided in
table 4.1) and clip the prompt at the 4000-token Codex context limit. We use
the same method for $\mathcal{D}_{a}$, except that we use random trajectory
subsequences.

In order to maximize the relevance of the prompt contents to the current
inference we select transitions using the following criteria.
$\mathcal{D}_{b}$ contains $(o_{k},a_{k},b_{k})$ tuples such that $a_{k}$
equals $a^{\left(u\right)}$, the action for which the LLM must infer
termination. $\mathcal{D}_{r}$ contains $(o_{k},a_{k},r_{k})$ tuples, again
constraining $a_{k}=a^{\left(u\right)}$ but also constraining
$b_{k}=b^{\left(k\right)}$ — that the tuple corresponds to a terminal time-
step if the LLM inferred $b^{\left(u\right)}=$ true, and to a non-terminal
time-step if $b^{\left(u\right)}=$ false. For $\mathcal{D}_{o}$, the prompt
includes $(o_{k},a_{k}o_{k+1})$ tuples with $a_{k}=a^{\left(u\right)}$ and
$b_{k}=$ false (only non-terminal states need to be modelled).

We also maintain a balance of certain kinds of transitions in the prompt. For
termination prediction, we balance terminal and non-terminal time-steps. Since
non-terminal time-steps far outnumber terminal time-steps, this eliminates a
situation wherein the randomly sampled prompt time-steps are entirely non-
terminal, all but ensuring that the LLM will predict non-termination.
Similarly, for reward prediction, we balance the number of time-steps
corresponding to each reward value stored in $\mathcal{D}$. In order to
balance two collections of unequal size, we take the smaller and duplicate
randomly chosen members until the sizes are equal.

In contrast to the other predictions, we condition the rollout policy on
trajectory subsequences, not individual time-steps. Prompting with sequences
better enables the foundation model to apprehend the logic behind a policy.
Trajectory subsequences consist of $(o_{k},a_{k})$ pairs, randomly clipped
from the $c$ most recent trajectories. More recent trajectories will, in
general demonstrate higher performance, since they come from policies that
have benefited from more rounds of improvement.

In contrast to the other predictions, we condition the rollout policy on
trajectory subsequences, not individual time-steps. Prompting with sequences
better enables the foundation model to apprehend the logic behind a policy.
Trajectory subsequences consist of $(o_{k},a_{k})$ pairs, randomly clipped
from the $c$ most recent trajectories. More recent trajectories will, in
general demonstrate higher performance, since they come from policies that
have benefited from more rounds of improvement.

Finally, the Q-value estimate is simply the discounted sum of rewards for the
simulated episode. Given this description of Q-value estimation, we now return
to the concept of policy improvement.

#### Policy-Improvement

The $\arg\max$ (line 6 of Algorithm 1) drives policy improvement in ICPI.
Critically this is not simply a one-step improvement as with Trajectory
Transformer [19] but a mechanism that builds improvement on top of
improvement. This occurs through a cycle in which the $\arg\max$ improves
behavior. The improved behavior is stored in the buffer $\mathcal{D}$, and
then used to condition the rollout policy. This improves the returns generated
by the LLM during planning rollouts. These improved rollouts improve the
Q-estimates for each action. Completing the cycle, this improves the actions
chosen by the $\arg\max$. Because this process feeds into itself, it can drive
improvement without bound until optimality is achieved.

Note that this process takes advantage of properties specific to in-context
learning. In particular, it relies on the assumption that the rollout policy,
when prompted with trajectories drawn from a mixture of policies, will
approximate something like an average of these policies. Given this
assumption, the rollout policy will improve with the improvement of the
mixture of policies from which its prompt-trajectories are drawn. This results
in a kind of rapid policy improvement that works without any use of gradients.

#### Prompt-Format

The LLM cannot take non-linguistic prompts, so our algorithm assumes access to
a textual representation of the environment—of states, actions, terminations,
and rewards—and some way to recover the original action, termination, and
reward values from their textual representation (we do not attempt to recover
states). Since our primary results use the Codex language model (see Table 1),
we use Python code to represent these values (examples are available in Table
LABEL:app-tab:promptformat in the appendix).

In our experiments, we discovered that the LLM world-model was unable to
reliably predict rewards, terminations, and next-states on some of the more
difficult environments. We experimented with providing domain _hints_ in the
form of prompt formats that make explicit useful information — similar to
Chain of Thought Prompting [35]. For example, for the _chain_ domain, the hint
includes an explicit comparison (== or !=) of the current state with the goal
state. Note that while hints are provided in the initial context, the LLM must
infer the hint content in rollouts generated from this context.

We use a consistent idiom for rewards and terminations, namely assert reward
== x and assert done or assert not done. Some decisions had to be made when
representing states and actions. In general, we strove to use simple,
idiomatic, concise Python. On the more challenging environments, we did search
over several options for the choice of hint. We anticipate that in the future,
stronger foundation models will be increasingly robust to these decisions.

Figure 2: Comparison of ICPI with three baselines, “No $\arg\max$”, “Tabular
Q,” and “Nearest Neighbor.” The $y$-axis depicts regret (normalized between 0
and 1), computed relative to an optimal return with a discount-factor of 0.8.
The $x$-axis depicts time-steps during training. Error bars are standard
errors from four seeds.

##  4 Experiments

We have three main goals in our experiments: (1) Demonstrate that the agent
algorithm can in fact quickly learn good policies, using pretrained LLMs, in a
set of six simple illustrative domains of increasing challenge; (2) provide
evidence through an ablation that the policy-improvement step—taking the
$\arg\max$ over Q-values computed through LLM rollouts—accelerates learning;
and (3) investigate the impact of using different LLMs (see Table 1)—different
sizes and trained on different data, in particular, trained on (mostly)
natural language (GPT-3 and GPT-J) vs. program code (Codex and InCoder). We
next describe the six domains and their associated prompt formats, and then
describe the experimental methodology and results.

###  4.1 Domains and prompt format

#### Chain.

In this environment, the agent occupies an 8-state chain. The agent has three
actions: _Left_ , _right_ , and _try goal_. The _try goal_ action always
terminates the episode, conferring a reward of 1 on state 4 (the goal state)
and 0 on all other states. Episodes also terminate after 8 time-steps. States
are represented as numbers from 0 to 7, as in assert state == n, with the
appropriate integer substituted for n. The actions are represented as
functions left(), right(), and try_goal(). For the hint, we simply indicate
whether or not the current state matches the goal state, 4.

#### Distractor Chain.

This environment is an 8-state chain, identical to the _chain_ environment,
except that the observation is a _pair_ of integers, the first indicating the
true state of the agent and the second acting as a distractor which
transitions randomly within $\\{0,\dots,7\\}$. The agent must therefore learn
to ignore the distractor integer and base its inferrences on the information
contained in the first integer. Aside from the addition of this distractor
integer to the observation, all text representations and hints are identical
to the _chain_ environment.

#### Maze.

The agent navigates a small $3\times 3$ gridworld with obstacles. The agent
can move _up_ , _down_ , _left_ , or _right_. The episode terminates with a
reward of 1 once the agent navigates to the goal grid, or with a reward of 0
after 8 time-steps. This environment tests our algorithms capacity to handle
2-dimensional movement and obstacles, as well as a 4-action state-space. We
represent the states as namedtuples — C(x, y), with integers substituted for x
and y. Similar to _chain_ , the hint indicates whether or not the state
corresponds to the goal state.

#### Mini Catch.

The agent operates a paddle to catch a falling ball. The ball falls from a
height of 5 units, descending one unit per time step. The paddle can _stay_ in
place (not move), or move _left_ or _right_ along the bottom of the 4-unit
wide plane. The agent receives a reward of 1 for catching the ball and 0 for
other time-steps. The episode ends when the ball’s height reaches the paddle
regardless of whether or not the paddle catches the ball. We chose this
environment specifically to challenge the action-inference/rollout-policy
component of our algorithm. Specifically, note that the success condition in
Mini Catch allows the paddle to meander before moving under the ball—as long
as it gets there on the final time-step. Successful trajectories that include
movement away from the ball thus make a good rollout policies more challenging
to learn (i.e., elicit from the LLM via prompts).

Again, we represent both the paddle and the ball as namedtuples C(x, y) and we
represent actions as methods of the paddle object: paddle.stay(),
paddle.left(), and paddle.right(). For the hint, we call out the location of
the paddle’s $x$-position, the ball’s $x$-position, the relation between these
positions (which is larger than which, or whether they are equal) and the
ball’s $y$-position. Table LABEL:app-tab:promptformat in the appendix provides
an example. We also include the text ball.descend() to account for the change
in the ball’s position between states.

#### Mini Invaders.

The agent operates a ship that shoots down aliens which descend from the top
of the screen. At the beginning of an episode, two aliens spawn at a random
location in two of four columns. The episode terminates when an alien reaches
the ground (resulting in 0 reward) or when the ship shoots down both aliens
(the agent receives 1 reward per alien). The agent can move _left_ , _right_ ,
or _shoot_. This domain highlights ICPI’s capacity to learn incrementally,
rather than discovering an optimal policy through random exploration and then
imitating that policy, which is how our “No $\arg\max$” baseline learns (see
Comparison of ICPI with baseline algorithms.). ICPI initially learns to shoot
down one alien, and then builds on this good but suboptimal policy to discover
the better policy of shooting down both aliens. In contrast, random
exploration takes much longer to discover the optimal policy and the “No
$\arg\max$” baseline has only experienced one or two successful trajectories
by the end of training.

We represent the ship by its namedtuple coordinate (C(x, y)) and the aliens as
a list of these namedtuples. When an alien is shot down, we substitute None
for the tuple, as in aliens == [C(x, y), None]. We add the text for a in
aliens: a.descend() in order to account for the change in the alien’s position
between states.

#### Point-Mass.

A point-mass spawns at a random position on a continuous line between $-6$ and
$+6$ with a velocity of 0. The agent can either _accelerate_ the point-mass
(increase velocity by 1) or _decelerate_ it (decrease the velocity by 1). The
point-mass position changes by the amount of its velocity each timestep. The
episode terminates with a reward of 1 once the point-mass is between $-2$ and
$+2$ and its velocity is 0 once again. The episode also terminates after 8
time-steps. This domain tests the algorithm’s ability to handle continuous
states.

States are represented as assert pos == p and vel == v, substituting floats
rounded to two decimals for p and v. The actions are accel(pos, vel) and
decel(pos, vel). The hint indicates whether the success conditions are met,
namely the relationship of pos to $-2$ and $+2$ and the whether or not vel ==
0. The hint includes identification of the aliens’ and the ship’s
$x$-positions as well as a comparison between them.

###  4.2 Experiment Methodology and Results

#### Methodology and evaluation.

For the results, we record the agent’s regret over the course of training
relative to an optimal policy computed with a discount factor of 0.8. For all
experiments $c=8$ (the number of most recent successful trajectories to
include in the prompt). We did not have time for hyperparameter search and
chose this number based on intuition, however the $c=16$ baseline demonstrates
results when this hyperparameter is doubled. All results use 4 seeds.

For both versions of Codex, we used the OpenAI Beta under the API Terms of
Use. For GPT-J [34] , InCoder [12] and OPT-30B [39], we used the open-source
implementations from Huggingface Transformers [37], each running on one Nvidia
A40 GPU. All language models use a sampling temperature of 0.1.

#### Comparison of ICPI with baseline algorithms.

We compare ICPI with three baselines (Fig. 2).

The “No $\arg\max$” baseline learns a good policy through random exploration
and then imitates this policy. This baseline assumes access to a “success
threshold” for each domain — an undiscounted cumulative return greater than
which a trajectory is considered successful. The action selection mechanism
emulates ICPI’s rollout policy: prompting the LLM with a set of trajectories
and eliciting an action as output. For this baseline, we only include
trajectories in the prompt whose cumulative return exceeds the success
threshold. Thus the policy improves as the number of successful trajectories
in the prompt increases over time. Note that at the start of learning, the
agent will have experienced too few successful trajectories to effectively
populate the policy prompt. In order to facilitate exploration, we act
randomly until the agent experiences 3 successes.

“Tabular Q” is a standard tabular Q-learning algorithm, which uses a learning
rate of $1.0$ and optimistically initializes the Q-values to $1.0$.

“Matching Model” is a baseline which uses the trajectory history instead of an
LLM to perform modelling. This baseline searches the trajectory buffer for the
most recent instance of the current state, and in the case of
transition/reward/termination prediction, the current action. If a match is
found, the model’s outputs the historical value (e.g. the reward associated
with the state-action pair found in the buffer). If no match is found, the
modelling rollout is terminated. Recall that ICPI breaks ties randomly during
action selection so this will often lead to random action selection.

As our results demonstrate, only ICPI learns good policies on all domains. We
attribute this advantage to ICPI’s ability to generalize from its context to
unseen states and state/action pairs (unlike “Tabular Q” and “Matching
Model”). Unlike “No $\arg\max$” ICPI is able to learn progressively, improving
the policy before experiencing good trajectories.

Figure 3: Comparison of ICPI with ablations. The $y$-axis depicts regret
(normalized between 0 and 1), computed relative to an optimal return with a
discount-factor of 0.8. The $x$-axis depicts time-steps during training. Error
bars are standard errors from four seeds.

#### Ablation of ICPI components.

With these experiments, we ablate those components of the algorithm which are
not, in principle, essential to learning (Fig. 3). “No Hints” ablates the
hints described in the Prompt-Format paragraph. “No Balance” removes the
balancing of different kinds of time-steps described in the Computing Q-values
paragraph (for example, $\mathcal{D}_{b}$ is allowed to contain an unequal
number of terminal and non-terminal time-steps). The “No Constraints” baseline
removes the constraints on these time-steps described in the same paragraph.
For example, $\mathcal{D}_{r}$ is allowed to contain a mixture of terminal and
non-terminal time-steps (regardless of the model’s termination prediction).
Finally, “$c=16$” prompts the rollout policy with the last 16 trajectories
(instead of the last 8, as in ICPI). We find that while some ablations match
ICPI’s performance in several domains, none match its performance on all six.

#### Comparison of Different Language Models.

While our lab lacks the resources to do a full study of scaling properties, we
did compare several language models of varying size (Fig. 4). See Table 1 for
details about these models. Both code-davinci-002 and code-cushman-001 are
variations of the Codex language model. The exact number of parameters in
these models is proprietary according to OpenAI, but [9] describes Codex as
fine-tuned from GPT-3 [5], which contains 185 billion parameters. As for the
distinction between the variations, the OpenAI website describes code-
cushman-001 as “almost as capable as Davinci Codex, but slightly faster.”

We found that none of the smaller models were capable of demonstrating
learning on any domain but the simplest, _chain_. Examining the trajectories
generated by agents trained using these models, we noted that in several
cases, they seemed to struggle to apprehend the underlying “logic” of
successful trajectories, which hampered the ability of the rollout policy to
produce good actions. Since these smaller models were not trained on identical
data, we are unable to isolate the role of size in these results. However, the
failure of all of these smaller models to learn suggests that size has some
role to play in performance. We conjecture that larger models developed in the
future may demonstrate comparable improvements in performance over our Codex
model.

#### Limitations

In principle, ICPI can work on any control task with a discrete state space.
All that the method requires is a sequence prediction model (in the paper we
use Codex) capable of inferring state transitions and action probabilities
given a history of behavior. Such a model will ensure that the rollouts
(described in Computing Q-values) are unbiased monte-carlo estimates of value
for the current policy. Given such estimates, the algorithm will implement
policy iteration, a method which is proven to converge. The domains in our
paper were limited by the abilities of Codex to accurately predict transitions
and actions in more complex domains. As sequence models mature, we anticipate
that more domains will become tractable for ICPI.

#### Societal Impacts

An extensive literature has explored the possible positive and negative
impacts of LLMs. Some of this work has explored mitigation strategies. In
extending LLMs to RL, our work inherits these benefits and challenges. We
highlight two concerns: the use of LLMs to spread misinformation and the
detrimental carbon cost of training and using these models.

Figure 4: Comparison of ICPI with ablations. The $y$-axis depicts regret (normalized between 0 and 1), computed relative to an optimal return with a discount-factor of 0.8. The $x$-axis depicts time-steps of training. Error bars are standard errors from four seeds. Table 1: Pretrained Large Language Models (LLMs) Used in Experiments Model | Parameters |  Training data
---|---|---
GPT-J [34] | 6 billion |  “The Pile” [13], an 825GB English corpus incl. Wikipedia, GitHub, academic pubs
InCoder [12] | 6.7 billion |  159 GB of open-source StackOverflow code
OPT-30B [39] | 30 billion |  180B tokens of predominantly English data including “The Pile” [13] and “PushShift.io Reddit” [4]
Codex [9] | 185 billion |  179 GB of GitHub code

##  5 Conclusion

Our main contribution is a method for implementing policy iteration algorithm
using Large Language Models and the mechanism of in-context learning. The
algorithm uses a foundation models as both a world model and policy to compute
Q-values via rollouts. Although we presented the method here as text-based, it
is general enough to be applied to any foundation models that works through
prompting, including multi-modal models like [28] and [29]. In experiments we
showed that the algorithm works in six illustrative domains imposing different
challenges for ICPI, confirming the benefit of the LLM-rollout-based policy
improvement. While the empirical results are quite modest, we believe the
approach provides an important new way to use LLMs that will increase in
effectiveness as the models themselves become better, as our size comparison
study suggests.

##  6 NeurIPS Paper Checklist

###  6.1 For all authors…

  1. 1.

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? Yes. Our claim about a novel algorithm is
substantiated in the Related Works and Algorithms section. Our claim that it
can produce improved behavior is substantiated in the Experiments section.

  2. 2.

Did you describe the limitations of your work? Yes. We have a Limitations
section that addresses this directly.

  3. 3.

Did you discuss any potential negative societal impacts of your work? Yes. We
have a Societal Impacts section that addresses this directly.

  4. 4.

Have you read the ethics review guidelines and ensured that your paper
conforms to them? Yes.

###  6.2 If you are including theoretical results…

This paper does not include theoretical results.

###  6.3 If you ran experiments…

  1. 1.

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? Yes.
This information is included in the supplemental material

  2. 2.

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? Yes. This information is described in the Methodology
and Evaluation section of our paper.

  3. 3.

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? Yes. We report error bands for all graphs.

  4. 4.

Did you include the amount of compute and the type of resources used (e.g.,
type of GPUs, internal cluster, or cloud provider)? Yes. This information is
present in the Methodology and Evaluation section of our paper. We were not
able to compute an estimate of our CO2 emissions, since we do not have access
to the details of the OpenAI machines that were accessed through the API.

###  6.4 If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

  1. 1.

If your work uses existing assets, did you cite the creators? Yes. In our
Pretrained Large Language Models (LLMs) Used in Experiments table, we cited
all of the authors of the original models as well as the authors of the
datasets that those models used.

  2. 2.

Did you mention the license of the assets? Yes. The only asset that we are
using that is subject to a license is the OpenAI API. We link to the Terms of
Use Methodology and Evaluation section.

  3. 3.

Did you include any new assets either in the supplemental material or as a
URL? Yes. Our source code is included in the supplemental material.

  4. 4.

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? No. We are not using any data derived directly from
human sources.

  5. 5.

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? No. We are not using any data
derived directly from human sources.

###  6.5 If you used crowdsourcing or conducted research with human subjects…

This paper does not use crowdsourcing or conduct research with human subjects.

## References

  * [1] Michael Ahn et al.  “Do As I Can, Not As I Say: Grounding Language in Robotic Affordances” arXiv:2204.01691 [cs]  arXiv, 2022  DOI: 10.48550/arXiv.2204.01691
  * [2] Prithviraj Ammanabrolu and Mark Riedl  “Learning Knowledge Graph-based World Models of Textual Environments”  In _Advances in Neural Information Processing Systems_ 34 Curran Associates, Inc., 2021, pp. 3720–3731  URL: https://proceedings.neurips.cc/paper/2021/hash/1e747ddbea997a1b933aaf58a7953c3c-Abstract.html
  * [3] Bowen Baker et al.  “Video PreTraining (VPT): Learning to Act by Watching Unlabeled Online Videos” arXiv:2206.11795 [cs]  arXiv, 2022  DOI: 10.48550/arXiv.2206.11795
  * [4] Jason Baumgartner et al.  “The Pushshift Reddit Dataset” Number: arXiv:2001.08435 arXiv:2001.08435 [cs]  arXiv, 2020  DOI: 10.48550/arXiv.2001.08435
  * [5] Tom Brown et al.  “Language Models are Few-Shot Learners”  In _Advances in Neural Information Processing Systems_ 33 Curran Associates, Inc., 2020, pp. 1877–1901  URL: https://papers.nips.cc/paper/2020/hash/1457c0d6bfcb4967418bfb8ac142f64a-Abstract.html
  * [6] Tom Brown et al.  “Language models are few-shot learners”  In _Advances in neural information processing systems_ 33, 2020, pp. 1877–1901
  * [7] Stephanie C.. Chan et al.  “Data Distributional Properties Drive Emergent In-Context Learning in Transformers” arXiv:2205.05055 [cs]  arXiv, 2022  DOI: 10.48550/arXiv.2205.05055
  * [8] Lili Chen et al.  “Decision Transformer: Reinforcement Learning via Sequence Modeling”  In _arXiv:2106.01345 [cs]_ , 2021  URL: http://arxiv.org/abs/2106.01345
  * [9] Mark Chen et al.  “Evaluating Large Language Models Trained on Code”, 2021  URL: http://arxiv.org/abs/2107.03374
  * [10] Mark Chen et al.  “Evaluating large language models trained on code”  In _arXiv preprint arXiv:2107.03374_ , 2021
  * [11] Yanda Chen et al.  “On the Relation between Sensitivity and Accuracy in In-context Learning” arXiv:2209.07661 [cs]  arXiv, 2022  URL: http://arxiv.org/abs/2209.07661
  * [12] Daniel Fried et al.  “InCoder: A Generative Model for Code Infilling and Synthesis”  In _arXiv:2204.05999 [cs]_ , 2022  URL: http://arxiv.org/abs/2204.05999
  * [13] Leo Gao et al.  “The Pile: An 800GB Dataset of Diverse Text for Language Modeling”  In _arXiv:2101.00027 [cs]_ , 2020  URL: http://arxiv.org/abs/2101.00027
  * [14] Divyansh Garg et al.  “LISA: Learning Interpretable Skill Abstractions from Language”  In _arXiv:2203.00054 [cs]_ , 2022  URL: http://arxiv.org/abs/2203.00054
  * [15] Shivam Garg, Dimitris Tsipras, Percy Liang and Gregory Valiant  “What Can Transformers Learn In-Context? A Case Study of Simple Function Classes” arXiv:2208.01066 [cs]  arXiv, 2022  DOI: 10.48550/arXiv.2208.01066
  * [16] Felix Hill, Sona Mokra, Nathaniel Wong and Tim Harley  “Human Instruction-Following with Deep Reinforcement Learning via Transfer-Learning from Text”  In _arXiv:2005.09382 [cs]_ , 2020  URL: http://arxiv.org/abs/2005.09382
  * [17] Wenlong Huang et al.  “Inner Monologue: Embodied Reasoning through Planning with Language Models” arXiv:2207.05608 [cs]  arXiv, 2022  DOI: 10.48550/arXiv.2207.05608
  * [18] Wenlong Huang, Pieter Abbeel, Deepak Pathak and Igor Mordatch  “Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents”  In _arXiv:2201.07207 [cs]_ , 2022  URL: http://arxiv.org/abs/2201.07207
  * [19] Michael Janner, Qiyang Li and Sergey Levine  “Offline Reinforcement Learning as One Big Sequence Modeling Problem” arXiv:2106.02039 [cs]  arXiv, 2021  DOI: 10.48550/arXiv.2106.02039
  * [20] Rabeeh Karimi Mahabadi et al.  “Prompt-free and Efficient Few-shot Learning with Language Models”  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ Dublin, Ireland: Association for Computational Linguistics, 2022, pp. 3638–3652  DOI: 10.18653/v1/2022.acl-long.254
  * [21] Michael Laskin et al.  “In-context reinforcement learning with algorithm distillation”  In _arXiv preprint arXiv:2210.14215_ , 2022
  * [22] Kuang-Huei Lee et al.  “Multi-Game Decision Transformers” arXiv:2205.15241 [cs]  arXiv, 2022  DOI: 10.48550/arXiv.2205.15241
  * [23] Shuang Li et al.  “Pre-Trained Language Models for Interactive Decision-Making”  In _arXiv:2202.01771 [cs]_ , 2022  URL: http://arxiv.org/abs/2202.01771
  * [24] Xiang Lisa Li and Percy Liang  “Prefix-Tuning: Optimizing Continuous Prompts for Generation”, 2021  DOI: 10.48550/arXiv.2101.00190
  * [25] Arjun Majumdar et al.  “Improving Vision-and-Language Navigation with Image-Text Pairs from the Web”  In _arXiv:2004.14973 [cs]_ , 2020  URL: http://arxiv.org/abs/2004.14973
  * [26] Maxwell Nye et al.  “Show Your Work: Scratchpads for Intermediate Computation with Language Models” arXiv:2112.00114 [cs]  arXiv, 2021  DOI: 10.48550/arXiv.2112.00114
  * [27] Xiangyu Peng, Mark O. Riedl and Prithviraj Ammanabrolu  “Inherently Explainable Reinforcement Learning in Natural Language”  In _arXiv:2112.08907 [cs]_ , 2021  URL: http://arxiv.org/abs/2112.08907
  * [28] Scott Reed et al.  “A Generalist Agent” arXiv:2205.06175 [cs]  arXiv, 2022  DOI: 10.48550/arXiv.2205.06175
  * [29] Younggyo Seo et al.  “HARP: Autoregressive Latent Video Prediction with High-Fidelity Image Generator” arXiv:2209.07143 [cs]  arXiv, 2022  URL: http://arxiv.org/abs/2209.07143
  * [30] Aaditya K. Singh et al.  “Know your audience: specializing grounded language models with the game of Dixit” arXiv:2206.08349 [cs]  arXiv, 2022  DOI: 10.48550/arXiv.2206.08349
  * [31] Ishika Singh, Gargi Singh and Ashutosh Modi  “Pre-trained Language Models as Prior Knowledge for Playing Text-based Games”  In _arXiv:2107.08408 [cs]_ , 2021  URL: http://arxiv.org/abs/2107.08408
  * [32] Allison C. Tam et al.  “Semantic Exploration from Language Abstractions and Pretrained Representations”  In _arXiv:2204.05080 [cs]_ , 2022  URL: http://arxiv.org/abs/2204.05080
  * [33] Denis Tarasov, Vladislav Kurenkov and Sergey Kolesnikov  “Prompts and Pre-Trained Language Models for Offline Reinforcement Learning”, 2022  URL: https://openreview.net/forum?id=Spf4TE6NkWq
  * [34] Ben Wang and Aran Komatsuzaki  “GPT-J-6B: A 6 Billion Parameter Autoregressive Language Model”, 2021  URL: https://github.com/kingoflolz/mesh-transformer-jax
  * [35] Jason Wei et al.  “Chain of Thought Prompting Elicits Reasoning in Large Language Models”  In _arXiv:2201.11903 [cs]_ , 2022  URL: http://arxiv.org/abs/2201.11903
  * [36] Jason Wei et al.  “Emergent Abilities of Large Language Models” arXiv:2206.07682 [cs]  arXiv, 2022  DOI: 10.48550/arXiv.2206.07682
  * [37] Thomas Wolf et al.  “Transformers: State-of-the-Art Natural Language Processing”  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ Online: Association for Computational Linguistics, 2020, pp. 38–45  DOI: 10.18653/v1/2020.emnlp-demos.6
  * [38] Mengdi Xu et al.  “Prompting Decision Transformer for Few-Shot Policy Generalization” arXiv:2206.13499 [cs]  arXiv, 2022  DOI: 10.48550/arXiv.2206.13499
  * [39] Susan Zhang et al.  “OPT: Open Pre-trained Transformer Language Models” _eprint: 2205.01068, 2022