# Reward-Respecting Subtasks for Model-Based Reinforcement Learning

Richard S. Sutton  Marlos C. Machado  G. Zacharias Holland  David Szepesvari
Finbarr Timbers  Brian Tanner  Adam White

# Supplemental Material
Reward-Respecting Subtasks for Model-Based Reinforcement Learning

Richard S. Sutton  Marlos C. Machado  G. Zacharias Holland  David Szepesvari
Finbarr Timbers  Brian Tanner  Adam White

###### Abstract

To achieve the ambitious goals of artificial intelligence, reinforcement
learning must include planning with a model of the world that is abstract in
state and time. Deep learning has made progress in state abstraction, but,
although the theory of time abstraction has been extensively developed based
on the options framework, in practice options have rarely been used in
planning. One reason for this is that the space of possible options is immense
and the methods previously proposed for option discovery do not take into
account how the option models will be used in planning. Options are typically
discovered by posing subsidiary tasks such as reaching a bottleneck state, or
maximizing a sensory signal other than the reward. Each subtask is solved to
produce an option, and then a model of the option is learned and made
available to the planning process. The subtasks proposed in most previous work
ignore the reward on the original problem, whereas we propose subtasks that
use the original reward plus a bonus based on a feature of the state at the
time the option stops. We show that options and option models obtained from
such reward-respecting subtasks are much more likely to be useful in planning
and can be learned online and off-policy using existing learning algorithms.
Reward respecting subtasks strongly constrain the space of options and thereby
also provide a partial solution to the problem of option discovery. Finally,
we show how the algorithms for learning values, policies, options, and models
can be unified using general value functions.

Machine Learning, ICML

In model-based reinforcement learning (MBRL), a reinforcement learning agent
learns a model of the transition dynamics of its environment and then converts
that model into improvements in its policy and, commonly, in its approximate
value function. The conversion process, generically referred to as _planning_
, is typically computationally expensive and may be distributed over many time
steps (or even performed offline). MBRL is well-suited to environments whose
transition dynamics are relatively simple but whose policy or value function
are complex (such as in Chess and Go). More generally, MBRL may enable
dramatically faster adaptation whenever the agent is long-lived, the
environment is non-stationary, and much of the environment’s transition
dynamics are stable (as approximately modeled by the agent). These are the
properties that we see as applying to animals (including people) operating in
the real world.

For planning to be tractable on large problems, an AI agent’s model must be
abstract in state and time. Abstraction in state is important because the
original states of the world may be too numerous to deal with individually, or
may not be observable by the agent. In these cases, how the state should be
constructed from observations is an important problem on which much work has
been done with deep learning, in particular with LSTMs (Hochreiter &
Schmidhuber, 1997) and in other ways (e.g., Lecun, Bottou, Bengio, & Haffner,
1998; Mnih et al., 2015). We do not address state abstraction in this paper
other than by allowing the agent’s state representation to be a non-Markov
feature vector.

This paper concerns how we should create and work with environment models that
are abstract in _time_. The most common way of formulating temporally-extended
and temporally-variable ways of behaving in a reinforcement learning agent is
as _options_ (Sutton, Precup, & Singh, 1999), each of which comprises a way of
behaving (a policy) and a way of stopping. The appeal of options is that they
are in some ways interchangeable with actions. Just as we can learn models of
action’s consequences and plan with those models, so we can learn and plan
with models of options’ effects. There remains the critical question of where
the options come from. A common approach to option discovery is to pose
subsidiary tasks such as reaching a bottleneck state or maximizing a sensory
signal. Given a subtask, the agent can then develop temporally abstract
structure for its cognition by following a standard progression, in which the
subtask is solved to produce an option, the option’s consequences are learned
to produce a model, and the model is used in planning. We refer to this
progression (SubTask, Option, Model, Planning) as the STOMP progression for
the development of temporally-abstract cognitive structure. All the steps of
the STOMP progression were described in the original paper on options (Sutton
et al., 1999), and it has been used in several previous works (e.g., Silver &
Ciosek, 2012; Singh, Barto, & Chentanez, 2004; Sorg & Singh, 2010).

The conceptual innovation of the current work is to introduce the notion of a
_reward-respecting_ subtask, that is, of a subtask that optimizes the rewards
of the original task until terminating in a state that is sometimes of high
value. Reward-respecting subtasks contrast with commonly used subtasks, such
as shortest path to bottleneck states (e.g., McGovern & Barto, 2001; Simsek &
Barto, 2004; Simsek, Wolfe, & Barto, 2005), pixel maximization (Jaderberg et
al., 2017), and diffusion maximization (c.f. Machado, Barreto, & Precup,
2021), which explicitly maximize the cumulative sum of a signal other than the
reward of the original task.

For example, consider the two-room gridworld shown inset in Figure 1, with a
start state in one room, a terminal goal state in the other, and a hallway
state in-between. The usual four actions move the agent one cell up, down,
right, or left unless blocked by a wall. A reward of $+1$ is received on
reaching the goal state, which ends the episode. Transitions ending in the
gray region between the start and hallway states produce a reward of $-1$ per
step, while all other transitions produce a reward of zero. The discount
factor is $\gamma\\!=\\!0.99$, so the optimal path from start to goal,
traveling the roundabout path that avoids the field of negative reward, yields
a return of $0.99^{18}\\!\approx\\!0.83$. The hallway state is a bottleneck
and thus a natural terminating subgoal for a subtask on this problem (as in
Solway et al., 2014). With a reward-respecting subtask, the agent would learn
a way to the hallway that maximizes the reward along the way; in this
gridworld it finds the option that goes down from the start state and _around_
the field of negative rewards. In contrast, solving the version of this
subtask that does not take the reward into consideration would be to learn the
shortest path from start to hallway, passing _through_ the field of negative
rewards.

Which of these two options are more useful when their models are learned and
used in planning? Assuming the optimal options for both subtasks, and that all
the models of the options and actions are known exactly, we can contrast the
progress of planning by value iteration (as detailed later in this paper) with
the primitive actions only, and with the primitive actions augmented by the
models of the two options. The results, shown in Figure 1, are much as you
would expect. Planning using the shortest-path option is less efficient than
when using primitive actions only; likely because the option being considered
is _not_ part of the final solution. Importantly, planning with the model of
the option based on the reward-respecting subtask is most efficient. In all
cases the optimal policy is found and the value of the start state is
eventually correctly estimated as $\approx 0.83$.

Figure 1:  A gridworld example contrasting the progress of planning with
reward-respecting options, with shortest-path options, and without options.
Planning with reward respecting options is much faster in terms of number of
states updated. Each line is averaged over 100 runs and the shading represents
the standard error. See text for details.

##  1 Reward-respecting subtasks

In this section we define the agent–environment interaction, the primary task,
GVF subtasks, reward-respecting subtasks, and the reward-respecting subtask
used to produce Figure 1. This is the first step in the STOMP progression for
developing temporally-abstract cognitive structure.

We consider an agent interacting with an environment in a sequence of
episodes, each beginning in environment state $S_{0}\in\mathscr{S}$ and ending
in the terminal state $S_{L}\\!=\\!\bot$ at time step $L\in\mathbb{N}$. At
time steps $t<L$, the agent selects an action $A_{t}\in\mathscr{A}$, and in
response the environment emits a reward $R_{t+1}\in{\cal
R}\subset{\mathbb{R}}$ and transitions to a next state
$S_{t+1}\in\mathscr{S}+\bot$ with probability $p(s^{\prime},r|s,a)\doteq{{\rm
Pr\\!}\left\\{S_{t+1}\\!=\\!s^{\prime},R_{t+1}\\!=\\!r\mid
S_{t}\\!=\\!s,A_{t}\\!=\\!a\right\\}}$, where $\mathscr{A}$, $\mathscr{S}$,
and ${\cal R}$ are all finite sets. Capitalized letters ($S_{t}$, $A_{t}$,
$R_{t}$, and $L$) denote random variables that differ from episode to episode;
technically these should be indexed by an episode number, but we suppress that
in our notation. The agent’s primary task is to find a policy
$\pi:\mathscr{S}\times\mathscr{A}\rightarrow[0,1]$ that maximizes the expected
discounted sum of rewards on an episode,
$\mathbb{E}_{\,\\!\\!}\left[R_{1}+\gamma
R_{2}+\cdots+\gamma^{L-1}R_{L}\right]$, where $\gamma\in[0,1)$ is the discount
rate, a parameter of the problem.

Solution methods for the primary task often involve approximating the value
function $v_{\pi}:\mathscr{S}\rightarrow{\mathbb{R}}$ for the agent’s current
policy $\pi$, defined by

$v_{\pi}(s)\doteq\mathbb{E}_{\pi\\!\\!}\left[{\textstyle\sum_{j=1}^{L}\gamma^{j-1}R_{j}}~{}\middle|~{}{S_{0}\\!=\\!s}\right],\forall
s\in\mathscr{S},$ (1)

where the expectation is conditional on the actions being selected according
to $\pi$. In the current work we are particularly concerned with linear
approximations to $v_{\pi}$. In this case, each state is converted to a
feature vector by a function ${\bf x}:\mathscr{S}\rightarrow{\mathbb{R}}^{d}$
(with ${\bf x}(\bot)\\!\doteq\\!\vec{0}$), which might be all the layers of a
neural network except for the last, or might be provided by a domain expert,
and then $v_{\pi}(s)$ is approximated as linear in ${\bf x}(s)$ and a
modifiable weight vector ${\bf w}\in{\mathbb{R}}^{d}$:

$v_{\pi}(s)\approx{\hat{v}}({\bf x}(s),{\bf w})\doteq{\bf w}{{}^{\top}}{\bf
x}(s)\doteq\textstyle\sum_{i=1}^{d}w_{i}x_{i}(s),$ (2)

for all $s\in\mathscr{S}$, where $w_{i}$ and $x_{i}(s)$ are individual
components of ${\bf w}$ and ${\bf x}(s)$, respectively.

We now generalize the primary task to include a full range of tasks for the
episodic setting, based on the framework of general value functions (GVFs)
introduced for the Horde architecture (Sutton et al., 2011). Instead of
maximizing the sum of rewards $R_{t}$, we maximize the sum of a cumulant
$C_{t}\\!\doteq\\!c(S_{t})$ for some function
$c:\mathscr{S}\rightarrow{\mathbb{R}}$. Instead of the accumulation stopping
only at the terminal state, it stops at every state with probability
$\beta(S_{t})$ for some function $\beta:\mathscr{S}\rightarrow[0,1]$ (with
$\beta(\bot)\\!\doteq\\!1$). Upon stopping, there is an additional
contribution to the accumulation, a final _stopping value_ $z(S_{t})$ for some
function $z:\mathscr{S}\rightarrow{\mathbb{R}}$ (with $z(\bot)\\!\doteq\\!0$).
The functions $c,z$ define the task, and the policy and stopping function,
$\pi,\beta$, which together constitute an option,111Options sometimes also
include a condition on the states in which the option can be initiated, but we
do not use that here. define an attempted solution to the task. If option
$\langle\pi,\beta\rangle$ were initiated in state $S_{t}$, then $A_{t}$ and
subsequent actions would be selected according to $\pi$ until the option
ended, or stopped, according to $\beta$ at step $K$. Given a GVF task $c,z$,
the objective is to find an option that maximizes
$\mathbb{E}_{\,\\!\\!}\left[C_{1}\\!+\\!\gamma
C_{2}\\!+\\!\cdots\\!+\\!\gamma^{K-1}C_{K}\\!+\\!\gamma^{K-1}z(S_{K})\right]$
for whatever state $S_{0}$ the option is started in. That is, the objective is
to maximize the general value function:

$v^{c,z}_{\pi,\beta}(s)\doteq\mathbb{E}_{\pi,\beta\\!\\!\\!}\left[{\textstyle\sum_{j=1}^{K}\gamma^{j-1}c(S_{j})+\gamma^{K-1}z(S_{K})\\!}~{}\middle|~{}{\\!S_{0}\\!=\\!s}\right]\\!\\!,$
(3)

where the expectation is conditional on the actions being determined by $\pi$
and the stopping time $K$ being determined by $\beta$. Note that “stopping” is
not termination, as it does not affect the actual flow of events in the
trajectory. The primary task is a special case of a GVF task in which
$C_{t}\\!\doteq\\!R_{t}$ and $Z_{t}\\!\doteq\\!-\infty$, $\forall t<L$.
Shortest path subtasks are defined by $C_{t}\\!\doteq\\!-1$ and
$z(s)\\!\doteq\\!0$ at subgoal states and $z(s)\\!\doteq\\!-\infty$ otherwise.
GVF tasks includes all the common subtasks in the literature including (if we
allow the state to formally include agent-internal variables) all those based
on curiosity and other intrinsic motivations (e.g., Baranes & Oudeyer, 2013;
Eysenbach et al., 2019).

Reward-respecting subtasks are GVF tasks whose cumulant is identical with the
reward, $C_{t}=R_{t}$, and whose stopping values take into account the
estimated value of the state stopped in. The stopping values cannot be equal
to the estimated values, as then the subtask would approximate the primary
task (exactly, in the tabular case) and solving it would add nothing new.

In this paper we consider reward-respecting subtasks of feature attainment, in
which the objective is to maximize an individual feature of the state
representation at stopping time while being mindful of the rewards received
along the way. There will be many such subtasks, and we will use the
superscript position to indicate the task number. For now we assume that we
can have at most one task per feature, so the feature index $i$ can serve
double duty as a task number. The subtask for maximizing feature $i$ has
stopping-value function $z^{i}$:

$z^{i}(s)\doteq{\hat{v}}({\bf x}(s),{\bf w})+x_{i}(s)(\bar{w}^{i}-w_{i}),$ (4)

where ${\bf w}$ and its $i$th component, $w_{i}$, are the weights for
approximating the primary task, and $\bar{w}^{i}$ is a bonus weight for
subtask $i$, provided as part of defining the subtask. Note that under the
linear form for $\hat{v}$ (2), $z^{i}$ does not depend on $w_{i}$. The
quantity $\bar{w}^{i}x_{i}$ is called the _stopping bonus_. Generally, it is
only useful to construct subtasks for attaining a feature $i$ if its
contribution to value on the primary task, $w_{i}$, is sometimes high and
sometimes low. If $w_{i}$ never varied, then its static value could be fully
taken into account without planning. If $w_{i}$ does vary, then its bonus
weight should be set to one of its higher values so that an option can be
learned in preparation for the occasional times at which $w_{i}$ is high.

Finally, the reward-respecting subtask used in producing Figure 1 was for the
tabular feature for the hallway state, with bonus weight $\bar{w}^{h}=1$,
where $h$ denotes the index of the feature for the hallway state. The
shortest-path subtask used $C_{t}=-1$ and stopped upon reaching the hallway or
terminal goal states.

##  2 Option learning for feature attainment

In this section we specify the off-policy learning algorithms we use to
approximate the optimal value functions and optimal options. This is the
second step in the STOMP progression for developing temporally-abstract
cognitive structure.

Define the optimal value function
$v^{i}_{*}:\mathscr{S}\rightarrow{\mathbb{R}}$ for the reward-respecting
subtask for attaining the $i$th feature by (3) with $C_{t}\\!\doteq\\!R_{t}$,
$z\\!\doteq\\!z^{i}$, and the $\pi$ and $\beta$ that maximize the value.
Define the optimal option as that pair $\langle\pi,\beta\rangle$. We will
describe these algorithms in a somewhat unusual way that lets us cover all the
cases very compactly and uniformly, including the model learning in the next
section. First we define a general TD (Temporal Difference) error function
$\delta:{\mathbb{R}}^{4}\times[0,1]\rightarrow{\mathbb{R}}$:

$\delta(c,z,v,v^{\prime},\beta)\doteq c+\beta
z+\gamma(1\\!-\\!\beta)v^{\prime}-v.$ (5)

We use various TD errors to specify our learning algorithms, together with a
general update procedure for learning with traces, which we call
UpdateWeights&Traces (UWT):

Procedure UWT $\bigl{(}{\bf w},{\bf
e},{\nabla},\alpha\delta,\rho,\gamma\lambda(1\\!-\\!\beta)\bigr{)}$:
---
${\bf e}\leftarrow\rho({\bf e}+{\nabla})$
${\bf w}\leftarrow{\bf w}+\alpha\delta{\bf e}$
${\bf e}\leftarrow\gamma\lambda(1\\!-\\!\beta){\bf e}$

The first two arguments to UWT are a weight vector and an eligibility-trace
vector. These arguments are both inputs and outputs; the same pair are
expected to be provided together on every time step. The weight vector is the
ultimate result of learning. The eligibility trace is a short-term memory that
helps with credit assignment. The third argument is usually a gradient vector
with respect to the weight vector. The fourth and sixth arguments to UWT are
scalars—the names of the formal arguments are just suggestive of their use.
Finally, the fifth argument is a scalar importance-sampling ratio used in off-
policy learning (for on-policy learning it should be one).

Here is how these tools would be used to implement on-policy linear
TD($\lambda$) (Sutton, 1988) on the primary task. First we would zero-
initialize ${\bf w}$ and corresponding eligibility-trace vector ${\bf
e}\in{\mathbb{R}}^{d}$. Then we would have the agent behave according to some
policy $\pi$ and, on each time step in which $S_{t}$ is nonterminal, we would
do:

$\displaystyle\delta\leftarrow\delta(R_{t+1},0,{\hat{v}}({\bf x}_{t},{\bf
w}),{\hat{v}}({\bf x}_{t+1},{\bf w}),0),\text{~{}and}$ (6)
$\displaystyle\mbox{\sf UWT}({\bf w},{\bf e},\nabla_{\\!{\bf w}}{\hat{v}}({\bf
x}_{t},{\bf w}),\alpha\delta,1,\gamma\lambda),$ (7)

where $\alpha$ and $\lambda$ are step-size and bootstrapping parameters. Note
that in the linear case, $\nabla{\hat{v}}({\bf x}_{t},{\bf w})$ in (7) is just
${\bf x}_{t}$. Now suppose the policy $\pi$ is parameterized by
${\bm{\theta}}\in{\mathbb{R}}^{d^{\prime}}$ and we wanted to learn it as well,
in an actor-critic algorithm (Sutton, 1984). This would be achieved by
invoking UWT one more time on each step, immediately after (7):

$\mbox{\sf UWT}({\bm{\theta}},{\bf
e}^{\prime},\nabla_{\\!{\bm{\theta}}}\ln\pi(A_{t}|S_{t},{\bm{\theta}}),\alpha^{\prime}\delta,1,\gamma\lambda^{\prime}),$
(8)

where ${\bf e}^{\prime}\in{\mathbb{R}}^{d^{\prime}}$ is another zero-
initialized eligibility-trace vector, and $\alpha^{\prime}$ and
$\lambda^{\prime}$ are step-size and bootstrapping parameters for the actor.

Now we show how to use these tools to learn the value functions and options
for the subtasks, off-policy. Let $\mathscr{F}\subset\\{0,\ldots,d\\}$ be the
set of features for which we have subtasks. Each subtask will have a weight
vector ${\bf w}^{i}\in{\mathbb{R}}^{d}$ such that ${\hat{v}}({\bf x}(s),{\bf
w}^{i})\\!\doteq\\!{\bf w}^{i}{{}^{\top}}{\bf x}(s)$ approximates a GVF (2)
where $C_{t}\\!=\\!R_{t}$, $z\\!=\\!z^{i}$ (4),
$\pi\\!=\\!\pi(\cdot|\cdot,{\bm{\theta}}^{i})$, where
${\bm{\theta}}^{i}\in{\mathbb{R}}^{d^{\prime}}$ is another modifiable weight
vector, and $\beta\\!=\\!\beta^{i}$, defined by

$\beta^{i}(s)\doteq\begin{cases}1,&\text{if }z^{i}(s)\geq{\bf
w}^{i}{{}^{\top}}{\bf x}(s);\\\ 0,&\text{otherwise,}\end{cases}$ (9)

for all $s\in\mathscr{S}$, with $\beta^{i}(\bot)\\!\doteq\\!1$. We will be
learning off-policy, so we will need the importance sampling ratios

$\rho^{i}_{t}\doteq\frac{\pi(A_{t}|S_{t},{\bm{\theta}}^{i})}{\mu(A_{t}|S_{t})},$
(10)

where $\mu:\mathscr{A}\times\mathscr{S}\rightarrow[0,1]$ is the behavior
policy (the policy actually used to select actions, as opposed to the policies
being learned about). For each subtask $i\in\mathscr{F}$, in addition to ${\bf
w}^{i}$ and ${\bm{\theta}}^{i}$ we will also have eligibility-trace vectors
${\bf e}^{i}\in{\mathbb{R}}^{d}$ and ${{\bf
e}^{\prime}}^{i}\in{\mathbb{R}}^{d^{\prime}}$, all initialized to zero. Then,
on each time step on which $S_{t}$ is nonterminal, for each $i\in\mathscr{F}$
we do:

$\displaystyle\delta\leftarrow\delta\bigl{(}R_{t+1},z^{i}_{t+1},{\hat{v}}({\bf
x}_{t},{\bf w}^{i}),{\hat{v}}({\bf x}_{t+1},{\bf
w}^{i}),\beta^{i}_{t+1}\bigr{)},$ $\displaystyle\mbox{\sf UWT}\bigl{(}{\bf
w}^{i},{\bf e}^{i},\nabla_{\\!{\bf w}}{\hat{v}}({\bf x}_{t},{\bf
w}^{i}),\alpha\delta,\rho^{i}_{t},\gamma\lambda(1\\!-\\!\beta^{i}_{t+1}\bigr{)}\bigr{)},\text{~{}and}$
$\displaystyle\mbox{\sf UWT}\bigl{(}{\bm{\theta}}^{i},{{\bf
e}^{\prime}}^{i},\nabla_{\\!{\bm{\theta}}^{i}}\ln\pi(A_{t}|S_{t},{\bm{\theta}}^{i}),\alpha^{\prime}\delta,\rho^{i}_{t},\gamma\lambda^{\prime}(1\\!-\\!\beta^{i}_{t+1}\bigr{)}\bigr{)},$

where here we use the shorthands $z^{i}_{t}\\!\doteq\\!z^{i}(S_{t})$ and
$\beta^{i}_{t}\\!\doteq\\!\beta^{i}(S_{t})$. Under this algorithm, the learned
approximate values ${\hat{v}}({\bf x}(s),{\bf w}^{i})\\!\doteq\\!{\bf
w}^{i}{{}^{\top}}{\bf x}(s)$ come to approximate the optimal subtask values
$v_{*}^{i}(s)\doteq\max_{\pi,\beta}v_{\pi,\beta}^{i}(s)$, $\forall
s\in\mathscr{S}$ and $i\in\mathscr{F}$, and the options
$\langle\pi(\cdot|\cdot,{\bm{\theta}}^{i}),\beta^{i}\rangle$ come to
approximate the corresponding optimal options. In the tabular case, the
approximations become exact with sufficient exploration and if the step sizes
are decreased appropriately.

Figure 2: The off-policy learning algorithm applied to find the optimal option
for the reward-respecting subtask for attaining the hallway feature. The data
comes from a policy in which all four actions were selected with equal
probability. Shown with arrows is a representation of the policy learned after
50,000 steps; the red cells are those in which the agent learned to stop. The
option shown is from a single run of the system, whereas each line is averaged
over 100 runs and the shading represents the standard error. The learned
option avoids the negative-reward region on the way to the hallway state (gray
region), while the policy mostly moves toward the goal in the second room. The
plot shows the progress of learning. The blue line (right scale) shows the
value of the start state for the learned option, and the red line (left scale)
shows the RMSE between the learned and optimal value functions.

Figure 2 shows such exact convergence for the hallway-feature attaining
subtask. We used a behavior policy that selected all four actions with equal
probability: $\mu(a|s)\doteq 0.25,\forall s\in\mathscr{S},a\in\mathscr{A}$.
The state-feature vectors were 1-hot, producing a tabular representation with
$d\\!=\\!72$ for the 72 non-terminal grid cells. The policy was of the softmax
form with linear preferences:

$\pi(a|s,{\bm{\theta}})\doteq\frac{e^{{\bm{\theta}}{{}^{\top}}{\bm{\phi}}(s,a)}}{{\textstyle\sum_{b}}e^{{\bm{\theta}}{{}^{\top}}{\bm{\phi}}(s,b)}},$
(11)

where the state-action feature vectors
${\bm{\phi}}(s,a)\in{\mathbb{R}}^{d^{\prime}},\forall
s\in\mathscr{S},a\in\mathscr{A}$ were again 1-hot or tabular
($d^{\prime}\\!=\\!288$). We ran for 50,000 steps and averaged the results
over 100 runs.

Figure 2 depicts the root mean squared error, throughout time, between the
estimated subtask value, $\hat{v}(S_{t},{\bf w}^{h}_{t})$, for the subtask for
attaining the $h$th feature, corresponding to the hallway state, and the
optimal subtask value, $v_{*}^{h}(S_{t})$. The curve shows the actor-critic
algorithm is able to effectively learn the correct option policy. Notice that
the option terminates either at the bottleneck state or the goal state, as
shown in red. Reward-respecting options trade off rewards, the value of the
state, and the stopping bonus. In the right room, close to the bottleneck
state it is more beneficial to go to the bottleneck state because the stopping
bonus plus the value of that state is greater than the value of directly going
to the goal state. In states closer to the goal state, it is better to
directly go to the goal state rather than to go back to the hallway.

##  3 Model learning

In this section we describe the third step in the STOMP progression: learning
a model of the environment’s action and option transitions. Recall that an
option is a pair, $o\doteq\langle\pi_{o},\beta_{o}\rangle$, consisting of a
policy and a stopping function. Actions are a special case of options in which
the policy $\pi_{o}$ always selects the action and the stopping function
always stops, $\beta_{o}(s)\\!=\\!1,\forall s\in\mathscr{S}$. Let
$\mathscr{O}(s)$ denote the set of options (including actions) available in
state $s$, and let $\mathscr{O}$ denote the set of all options (unioning over
all states). With a slight abuse of notation, we allow $\mathscr{O}$ to also
include the indices of state-features $i\in\mathscr{F}$ for which the agent
has learned an option; when that feature index appears in a position that is
expecting an option (as in the next few equations) we mean the option
corresponding to that feature.

The idealized model is expressed in terms of the underlying environment states
$s\in\mathscr{S}$ and exactly matches the true underlying dynamics. Like all
models, it is comprised of a reward part and a state-transition part. The
reward part is a function
$r:\mathscr{S}\times\mathscr{O}\rightarrow{\mathbb{R}}$ returning the expected
cumulative discounted reward if the option were executed starting from the
state:

$r(s,o)\doteq\mathbb{E}_{\pi_{o},\beta_{o}\\!\\!}\left[{{\textstyle\sum_{j=1}^{K}}\gamma^{j-1}R_{t+j}}~{}\middle|~{}{S_{t}\\!=\\!s}\right],$
(12)

for all $o\in\mathscr{O}$ and $s\in\mathscr{S}$, and where the expectation is
conditional on actions being selected by $\pi_{o}$ and $K$ being determined by
$\beta_{o}$. The state-transition part of an idealized model is a function
${p}:\mathscr{S}\times\mathscr{S}\times\mathscr{O}\rightarrow[0,1]$ returning,
for each state $s$ in which an option might be started, the probability of
stopping in each state $s^{\prime}$, discounted by the time until stopping:

$p(s^{\prime}|s,o)\doteq\textstyle\sum_{k=1}^{\infty}\gamma^{k}{{\rm
Pr\\!}\left\\{K\\!=\\!k,S_{t+k}\\!=\\!s^{\prime}\\!\mid\\!S_{t}\\!=\\!s\right\\}},$
(13)

for all $o\in\mathscr{O}$ and $s,s^{\prime}\in\mathscr{S}$, and where the
probability is conditional on the actions from $t$ being selected according to
the policy of option $o$ and $K$ being determined by its stopping function.
Note that we write the $p$ function with a $|$, suggesting that it is a
probability distribution, but for $\gamma<1$ it is not. This precise form is
dictated by the requirement that option models and action models be
interchangeable in planning methods such as value iteration (see next
section).

Approximate models do not in general have access to environmental states, but
instead must work with a representation of state constructed by the agent,
which might be called the agent state. Unlike the environment state, the agent
state is generally not a Markov summary of the past. In this paper we assume
the agent state is a state-feature vector ${\bf x}\in{\mathbb{R}}^{d}$ (in the
tabular special case these would be 1-hot vectors and they would be Markov)
which can be determined from the environment state by a known function ${\bf
x}:\mathscr{S}\rightarrow{\mathbb{R}}^{d}$. The reward part of an approximate
model of an option is a function
$\hat{r}:{\mathbb{R}}^{d}\times\mathscr{O}\rightarrow{\mathbb{R}}$ such that

${\hat{r}}({\bf x}(s),o)\approx r(s,o),~{}~{}~{}~{}\forall s\in\mathscr{S},$
(14)

weighted over some distribution of states such as the state distribution under
the behavior policy. The state-transition part of an approximate model could
take several forms. In an expectation model, the state-transition part is a
function
${\bf\hat{n}}:{\mathbb{R}}^{d}\times\mathscr{O}\rightarrow{\mathbb{R}}^{d}$
such that

$\displaystyle{\bf\hat{n}}({\bf x}(s),o)$
$\displaystyle\approx\sum_{s^{\prime}\in\mathscr{S}}p(s^{\prime}|s,o){\bf
x}(s^{\prime})$ (15) $\displaystyle=\mathbb{E}_{o\\!\\!}\left[{\gamma^{K}{\bf
x}(S_{t+K})}~{}\middle|~{}{S_{t}\\!=\\!s}\right],$ (16)

for all $s\in\mathscr{S}$ under some state weighting, perhaps given by the
behavior policy, and where the expectation is conditional on the actions being
selected according to $o$’s policy and the stopping time $K$ being determined
by $o$’s stopping function.

For the illustrative example in Figure 1, we learned models for the four
options corresponding to the actions and the reward-respecting option for the
hallway state. The approximate model was linear in the state-feature vector,
meaning that

${\hat{r}}({\bf x},o)\doteq{\bf w}_{r}^{o}{{}^{\top}}{\bf x},$ (17)

where each ${\bf w}_{r}^{o}\in{\mathbb{R}}^{d}$ is a learned weight vector,
and

${\bf\hat{n}}({\bf x},o)\doteq{\bf W}^{o}{\bf x},$ (18)

where each ${\bf W}^{o}$ is a $d\times d$ matrix, with rows ${\bf w}^{o}_{j}$.
In this tabular problem ($d=|\mathscr{S}|=72$) the states were represented by
1-hot feature vectors. To learn the weights, each weight vector (the ${\bf
w}^{o}_{r}$ and the ${\bf w}^{o}_{j}$, for
$o\in\mathscr{O},j\\!=\\!1,\ldots,d$) was paired with an eligibility trace
vector, ${\bf e}^{o}_{r}$ and the ${\bf e}^{o}_{j}$s. All these vectors were
initialized to zero. The agent wandered all over the two rooms following the
equi-probable random policy for many episodes. On each step
($S_{t},A_{t},R_{t+1},S_{t+1}$) for which $S_{t}$ was non-terminal, for each
$o\in\mathscr{O}$, we did:

$\displaystyle\delta\leftarrow\delta\bigl{(}R_{t+1},0,{\hat{r}}({\bf
x}_{t},o),\gamma{\hat{r}}({\bf x}_{t+1},o),\beta^{o}_{t+1}\bigr{)}$ (19)
$\displaystyle\mbox{\sf UWT}\bigl{(}{\bf w}_{r}^{o},{\bf
e}_{r}^{o},\nabla{\hat{r}}({\bf
x}_{t},o),\alpha_{r}\delta,\rho^{o}_{t},\gamma\lambda(1\\!-\\!\beta^{o}_{t+1}\bigr{)}\bigr{)}$
(20) and, for each $j=1,\ldots,d$:
$\displaystyle~{}~{}\delta\leftarrow\delta\bigl{(}0,\gamma
x_{j,t+1},\hat{n}_{j}({\bf x}_{t},o),\gamma\hat{n}_{j}({\bf
x}_{t+1},o),\beta^{o}_{t+1}\bigr{)}\\!\\!$ (21) $\displaystyle~{}~{}\mbox{\sf
UWT}\bigl{(}{\bf w}_{j}^{o},{\bf e}^{o}_{j},\nabla\hat{n}_{j}({\bf
x}_{t},o),\alpha_{p}\delta,\rho^{o}_{t},\gamma\lambda(1\\!-\\!\beta^{o}_{t+1}\bigr{)}\bigr{)},\\!$
(22)

where $x_{j,t+1}$ denotes the $j$th component of ${\bf x}_{t+1}$,
$\hat{n}_{j}$ denotes the $j$th component of the vector returned by
${\bf\hat{n}}$, and $\beta^{i}_{t}\\!\doteq\\!\beta^{i}(S_{t})$. This way of
using TD($\lambda$) algorithms to learn a temporally abstract model of the
world was introduced by Sutton (1995; see also Sutton and Barto, 2018, Section
17.2) Note that for one-step options such as actions, the use of UWT is not
necessary; the algorithm is correct as specified, but if desired it could be
implemented more efficiently without eligibility traces.

Figure 3: Transition and reward models are efficiently learned online. The red
line (left scale) shows the root mean square error (RMSE) between the learned
reward model for the option and the idealized reward model. The blue line
(right scale) shows the RMSE between the learned transition model for the
option and the idealized state-transition model. The state-transition model
captures discounting and termination. The performance of planning for learned,
approximate models with different levels of accuracy is depicted in the inset
plot. In this environment, 17,000 steps of model learning is sufficient to
achieve near-optimal planning performance. All lines were averaged over 100
runs and the shading represents the standard error. See appendix for other
details.

The procedure described above allows us to efficiently learn both transition
and reward models, as shown in Figure 3. We also evaluated the impact of
planning with imperfect models, using the planning algorithm described in the
next section. The results are shown in the inset plot. Planning leads to near-
optimal performance using an imperfect model trained for $17,000$ steps.
Further training improves model error but does not significantly improve
planning in this environment.

It can be advantageous to learn a linear expectation model under function
approximation. In the general case, the transition-part must be able to
produce the entire distribution of resultant states. These distribution models
are important theoretically and have been used effectively when the possible
distributions can be assumed to be of a special form (e.g., Gaussian), as in
the PILCO method (Deisenroth & Rasmussen, 2011). Generally, these are very
large objects and would be hopelessly unwieldy for large $d$. Fortunately, if
the value function is linear in the state features, then there is no loss of
generality when using an expectation model in planning (Wan et al., 2019,
Kudashkina, 2022).

##  4 Planning with options and approximations

Our planning method approximates _value iteration_ , the classical planning
algorithm for finite MDPs, in its asynchronous form extended to options
(Sutton, Precup, & Singh, 1999). In that tabular algorithm, the state-value
estimates $V(s),\forall s\in\mathscr{S}$, are initialized arbitrarily and then
updated one-by-one, in some sequence, by:

$V(s)\leftarrow\max_{o\in\mathscr{O}(s)}\left[r(s,o)+\textstyle\sum_{s^{\prime}}p(s^{\prime}|s,o)V(s^{\prime})\right],$
(23)

where $r$ and $p$ are the reward and state-transition parts of the idealized
model of option $o$, as defined in the previous section, and $\mathscr{O}(s)$
is the set of options considered in state $s$, which may include all or some
of the primitive actions available. If $\mathscr{O}(s)$ is exactly the
primitive actions, then $\hat{p}(s^{\prime}|s,o)$ is exactly the state-
transition probabilities, times $\gamma$, and the general form (23) reduces to
classical value iteration.

(a) Impact in planning induced by the reward-respecting options learned with
different values of $\bar{w}^{i}$ from (4). Each line is averaged over 100
runs and the shading represents the standard error.

(b) Reward-respecting options learned with different values of $\bar{w}^{i}$.
The problem of option discovery can be summarized as the problem of defining
$z^{i}$; even different values of $\bar{w}^{i}$ lead to different options.

Figure 4: Impact of different values of $\bar{w}^{i}$ on the options learned
and the induced planning performance. See Section 5 for details.

In our planning method, _approximate value iteration_ (AVI), the estimated
value function is maintained not as a table $V(s)$, but as a parameterized
form $\hat{v}({\bf x}(s),{\bf w})$ with parameter ${\bf w}\in{\mathbb{R}}^{d}$
with $d\ll|\mathscr{S}|$. Moreover, the planner will iterate over state-
feature vectors ${\bf x}\in{\mathbb{R}}^{d}$ instead of environmental states
$s\in\mathscr{S}$. In this paper we use a linear form $\hat{v}({\bf x},{\bf
w})\doteq{\bf w}{{}^{\top}}{\bf x}$, which combines favorably with expectation
models, but in general any differentiable parameterized form could be used.
The parameter vector ${\bf w}$ is initialized arbitrarily and then updated,
for each state-feature vector ${\bf x}$, in some sequence of state-feature
vectors, by

${\bf w}\leftarrow{\bf w}+\alpha\Bigl{[}\max_{o\in\mathscr{O}({\bf x})}b({\bf
x},o,{\bf w})-\hat{v}({\bf x},{\bf w})\Bigr{]}\nabla_{\\!{\bf w}}\hat{v}({\bf
x},{\bf w}),$ (24)

where $\alpha>0$ is a step-size parameter, and

$b({\bf x},o,{\bf w})\doteq{\hat{r}}({\bf x},o)+\hat{v}({\bf\hat{n}}({\bf
x},o),{\bf w}).$ (25)

The quantity $b({\bf x},o,{\bf w})$ is the backed-up value of the state
represented by ${\bf x}$, when projected ahead by the model of option $o$,
using the approximate value function given by the weights ${\bf w}$. Using the
backed-up value in (24) takes the place of the full sum in (23). This can only
be done without introducing any additional approximation error if the value
function involved is linear in the state-feature vector ${\bf x}$ (Wan et al.,
2019).

To obtain the results in Figure 1, we sampled states $s$ randomly from the
state set $\mathscr{S}$, computed their feature vectors ${\bf x}(s)$, and then
applied (24) using (25). The weight vector ${\bf w}$ was initialized to zero.
The models of the actions and options were learned until near convergence as
described in the preceding section.

The primary definition of a useful option is one that takes the maximum in
(23) or (24) at some state and thus makes a difference in planning. We assume
here that the model of the option has been learned and is stable, but the
approximate value function has not been fully learned and is not stable (as
otherwise no further planning would be necessary). These assumptions are
noteworthy and deserve examination. Certainly there are cases where they are
appropriate. In Chess, the model of the game’s dynamics is known completely,
and could have been learned, but the value of almost all states can only be
approximated, and the planning problem is so large that it is never completely
solved and the state values are never all known exactly.

So, to make the backed-up values large, we certainly seek options for which
$r(s,o)$, the cumulative reward during the option, is large. This is the main
point about reward-respecting options. We also want the second term of the
backed-up value to be large, which is achieved if the option terminates in
states of high approximate value. That is, we seek options that produce high
rewards and that drive the environment to states that, occasionally, have high
value.

(a) Reward-respecting options learned in a stochastic gridworld. Four options
are learned as solutions to four subtasks seeking to attain the four hallway
states (labeled H1-H4). Stochastic transitions make states close to the
negative reward region (shaded gray) less desirable due to the natural
uncertainty over their return.

(b) Progress of planning with different types of options in the four-rooms
gridworld. Each line is averaged over 30 runs and the shading represents the
standard error.

Figure 5: Illustration of the STOMP progression in a four-rooms problem. We
include two baselines: the option-critic (Bacon et al., 2017) and eigenoptions
(Machado et al., 2017, 2018). The option-critic parameterizes options’
policies and uses option-value functions and the policy gradient theorem to
learn options that maximize the return. Eigenoptions are options designed for
temporally-extended exploration that do not take rewards into consideration.

##  5 Stopping bonuses matter

The definition of subtasks presented in Section 2 constrains the search space
for option discovery. The magnitude of the bonus weight defines how much the
agent wants to take the rewards observed along the way into consideration when
compared to the agent’s estimated value of that state. Reward-respecting
subtasks are a particular type of subtask defined by a cumulant and the value
of the stopping state. Because the subtask’s cumulant is the reward, the value
of the stopping state contains the only parameter of the subtask: the bonus
weight, $\bar{w}^{i}$. So far, we only considered the case where
$\bar{w}^{i}=1$. We now evaluate the impact of different values of
$\bar{w}^{i}$ and show how different values allow us to approximate shortest-
path options.

Figure 4 depicts the impact of different values of $\bar{w}^{i}$ in the two-
room gridworld. We report the progress of planning for different values of
$\bar{w}^{i}$, having run all steps of the STOMP progression in order to
generate the results. We also depict the options learned for different values
of $\bar{w}^{i}$ to illustrate how the options’ policies are impacted. The
progress of option and model learning is unaffected by $\bar{w}^{i}$.

As expected, small values of $\bar{w}^{i}$ make attaining feature $i$ less
important. In particular, when $\bar{w}^{i}\\!=\\!0.1$, the agent avoids the
region of negative rewards, but is much more interested in the goal state, as
seen in the right room. Large values of $\bar{w}^{i}$, such as
$\bar{w}^{i}\\!=\\!100$, makes attaining feature $i$ much more attractive,
such that the reward-respecting option becomes the shortest-path option.
Different values of $\bar{w}^{i}$ also impact the degree to which the agent is
willing to experience negative rewards in order to complete the subtask
quicker (c.f. $\bar{w}^{i}\\!=\\!10$ vs. $\bar{w}^{i}\\!=\\!100$). Naturally,
different options could make planning more or less effective.

##  6 Multiple options and stochasticity

In this section we present results for a larger STOMP progression with
multiple subtasks in a stochastic environment, and we compare reward-
respecting options to other choices. Specifically, we used the four-room
episodic gridworld depicted in Figure 5a, with a start state in one room, and
a terminal goal state in another. As in the two-room gridworld, a reward of
$+1$ is received on reaching the goal, which ends the episode, and passing
through the gray region produces a reward of $-1$ per step, while all other
transitions produce a reward of zero. The discount factor is $\gamma=0.99$.
There are four actions, available in all nonterminal states: up, down, left,
and right. Importantly, each action causes the agent to _stochastically_ move
in the corresponding direction with probability $\nicefrac{{2}}{{3}}$ and in
one of the other three directions with probability $\nicefrac{{1}}{{9}}$.

We defined four subtasks, each subtask directed toward reaching one of the
four hallways states. The hallways are labeled in Figure 5a as H1-H4. Notice
that reward-respecting options take into consideration the fact that the
environment’s stochasticity is not under the agent’s control. For the most
part, the options take the shortest path to the hallway or the goal state, but
the uncontrolled stochasticity and the negative reward region causes some
options to prefer a longer (and safer) path. For example, when in the South-
West room, options sometimes take the roundabout way to reach H3 and H4.

Here, besides the shortest-path option, we consider _eigenoptions_ (Machado et
al., 2017; 2018) and the _option-critic_ (Bacon, Harb, & Precup, 2017) as
alternative option construction methods. The option-critic generates reward-
respecting options that were not used for planning, and eigenoptions are
options designed for model-free exploration, not planning, and which do not
take the rewards into consideration. As aforementioned, in this paper we
introduce general formulation of the option discovery problem (3). We can
illustrate that with eigenoptions, which can be seen as maximizing (3), but
with $C_{t}\doteq 0$ and $z(S_{K})$ being the value assigned by the
eigenvector of the graph Laplacian to state $S_{K}$.

The results in Figure 5b show that reward-respecting options are more
appropriate than alternative subtask formulations when these options are to be
used in the STOMP progression. Moreover, considering multiple options in the
STOMP progression does not impact performance. The stochastic nature of the
environment also does not impact the applicability of the approach presented.
The results for option and model learning, which are similar to those reported
in previous sections, can be found in the Appendix.

##  7 Conclusions, limitations, and future work

In this paper, we introduced reward-respecting subtasks and showed how they
lead to more efficient planning because they are more likely to be part of the
agent’s final plan. We did so through the language of general value functions
(GVFs), which allowed us to introduce a general procedure that unifies option
learning, value learning, and model learning. Our formulation can also be seen
as a formalization of the option discovery problem that unifies option
discovery methods. We also introduced reward-respecting subtasks of feature
attainment. This simple choice reduces the option discovery problem to one of
deciding what features to maximize.

We have focused on presenting the problem formulation and each step of the
STOMP progression in a general way in order to be amenable to different forms
of function approximation. We considered only time abstraction, not state
abstraction, but it is natural to ask how our approach would perform with
different forms of function approximation. An interesting related question is
how feature attainment interacts with representation learning techniques that
automatically construct state abstractions.

## Acknowledgements

The authors would like to thank Francesco Visin for his feedback on an earlier
draft; and Joseph Modayil, Martha White, and Michael Bowling for useful
discussions. Richard S. Sutton, Marlos C. Machado and Adam White are supported
by a Canada CIFAR AI Chair.

## References

* (1) Bacon, P.-L., Harb, J., & Precup, D. (2017). The Option-Critic Architecture. In _Proceedings of the National Conference on Artificial Intelligence (AAAI)_. Baranes, A., & Oudeyer, P.-Y.. Active Learning of Inverse Models with Intrinsically Motivated Goal Exploration in Robots. Robotics and Autonomous Systems, 61(1): 49–73, 2013.
* (2) Deisenroth, M. P., & Rasmussen, C. E. (2011). PILCO: A Model-Based and Data-Efficient Approach to Policy Search. In _Proceedings of the International Conference on Machine Learning (ICML)_. Eysenbach, B., Gupta, A., Ibarz, J., & Levine, S. (2019). Diversity is All You Need: Learning Skills without a Reward Function. In Proceedings of the International Conference on Learning Representations (ICLR).
* (3) Hochreiter, S., & Schmidhuber, J. (1997). Long Short-Term Memory. _Neural Computation, 9_(8), 1735–1780.
* (4) Jaderberg, M., Mnih, V., Czarnecki, W. M., Schaul, T., Leibo, J. Z., Silver, D., & Kavukcuoglu, K. (2017). Reinforcement Learning with Unsupervised Auxiliary Tasks. In Proceedings of the International Conference on Learning Representations (ICLR). Kudashkina, K. (2022). Model-based Reinforcement Learning Methods for Developing Intelligent Assistants (PhD dissertation). Department of Engineering, University of Guelph.
* (5) Lecun, Y., Bottou, L., Bengio, Y., & Haffner, P. (1998). Gradient-based Learning Applied to Document Recognition. _Proceedings of the IEEE, 86_(11), 2278–2324.
* (6) Machado, M. C., Barreto, A., & Precup, D. (2021). Temporal Abstraction in Reinforcement Learning with the Successor Representation. ArXiv, abs/2110.05740.
* (7) Machado, M. C., Bellemare, M. G., & Bowling, M. H. (2017). A Laplacian Framework for Option Discovery in Reinforcement Learning. In Proceedings of the International Conference on Machine Learning (ICML).
* (8) Machado, M. C., Rosenbaum, C., Guo, X., Liu, M., Tesauro, G., & Campbell, M. (2018). Eigenoption Discovery through the Deep Successor Representation. In Proceedings of the International Conference on Learning Representations (ICLR).
* (9) McGovern, A., & Barto, A. G. (2001). Automatic Discovery of Subgoals in Reinforcement Learning using Diverse Density. In Proceedings of the International Conference on Machine Learning (ICML).

* (10) Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., …Hassabis, D. (2015). Human-level Control through Deep Reinforcement Learning. Nature, 518, 529–533.
* (11) Silver, D., & Ciosek, K. (2012). Compositional Planning Using Optimal Option Models. In Proceedings of the International Conference on Machine Learning (ICML).
* (12) Simsek, O., & Barto, A. G. (2004). Using Relative Novelty to Identify Useful Temporal Abstractions in Reinforcement Learning. In Proceedings of the International Conference on Machine Learning (ICML).
* (13) Simsek, O., Wolfe, A. P., & Barto, A. G. (2005). Identifying Useful Subgoals in Reinforcement Learning by Local Graph Partitioning. In Proceedings of the International Conference on Machine Learning (ICML).
* (14) Singh, S. P., Barto, A. G., & Chentanez, N. (2004). Intrinsically Motivated Reinforcement Learning. In Advances in Neural Information Processing Systems (NeurIPS).
* (15) Solway, A., Diuk, C., Cordova, N., Yee, D., Barto, A. G., Niv, Y., & Botvinick, M. (2014). Optimal Behavioral Hierarchy. PLoS Computational Biology, 10(8).
* (16) Sorg, J., & Singh, S. P. (2010). Linear Options. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
* (17) Sutton, R. S. (1984). Temporal Credit Assignment in Reinforcement Learning (PhD dissertation). Department of Computer Science, University of Massachusetts, Amherst.
* (18) Sutton, R. S. (1988). Learning to Predict by the Methods of Temporal Differences. Machine Learning, 3: 9–44.
* (19) Sutton, R. S. (1995). TD Models: Modeling the World at a Mixture of Time Scales. In Proceedings of the International Conference on Machine Learning (ICML).
* (20) Sutton, R. S., & Barto, A. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press.
* (21) Sutton, R. S., Modayil, J., Delp, M., Degris, T., Pilarski, P. M., White, A., & Precup, D. (2011). Horde: A Scalable Real-Time Architecture for Learning Knowledge from Unsupervised Sensorimotor Interaction. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS).
* (22) Sutton, R. S., Precup, D., & Singh, S. (1999). Between MDPs and semi-MDPs: A Framework for Temporal Abstraction in Reinforcement Learning. Artificial Intelligence, 112(1–2), 181–211.
* (23) Wan, Y., Zaheer, M., White, A., White, M., & Sutton, R. S. (2019). Planning with Expectation Models. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).

## Organization of the Supplemental Material

A. Details about empirical evaluation in the tabular case

A.1.  Environment dynamics

A.2.  Subtask specification

A.3.  Option learning for feature attainment

A.4.  Model learning

A.5.  Planning

B. Multiple options and stochasticity

B.1.  Option learning for feature attainment

B.2.  Model learning

##  A Details about empirical evaluation in the tabular case

In the main paper, when presenting empirical results, for better readability,
we did not provide enough details to reproduce the reported results, such as
the parameters used. We do so here.

###  A.1 Environment dynamics

In both the two-room and four-room gridworlds we use a tabular representation
(i.e., one-hot encoding) and four primitive actions are available to the
agent: up, down, right, and left. A reward of +1 is received on reaching the
goal, which ends the episode. Passing through the gray region between the
start and hallway states produces a reward of $-1$ per step, while all other
transitions produce a reward of zero. While the two-room gridworld is
deterministic, the four-room gridworld is stochastic: any chosen action causes
the agent to move to the desired direction with probability
$\nicefrac{{2}}{{3}}$, with the agent instead moving in one of the other three
directions with probability $\nicefrac{{1}}{{9}}$. The discount factor is
$\gamma=0.99$.

###  A.2 Subtask specification

We define the reward-respecting subtasks such that the cumulant, $C_{t}$, is
equal to the reward signal, $R_{t}$; and $\bar{w}^{i}=1$ upon reaching the
hallway state and $\bar{w}^{i}=0$ otherwise. We use an estimate of the value
function for the equi-probable random policy as the value function in Eq. 4.
We learn the estimate of the value function at the same time as we learn the
option’s policy. We use TD($0$) to learn the value of the equi-probable random
policy, with a step-size $\alpha=0.9$ in the two-room gridworld and
$\alpha=0.1$ in the four-room gridworld. We initialize $\mathbf{{\bf
w}}=\vec{0}$. We define shortest-path options such that $C_{t}=0$; and
$\bar{z}^{i}=1$ upon reaching the hallway state and $\bar{z}^{i}=0$ otherwise.

###  A.3 Option learning for feature attainment

To learn the option’s policy, for both reward-respecting and reward-oblivious
subtasks, we used _UpdateWeights &Traces_ (UWT) to implement an actor-critic
algorithm, as described in Eq. 6-8. We initialize the critic’s
$\mathbf{w}\text{ and }\mathbf{e}$, and the actor’s $\mathbf{\omega}\text{ and
}\mathbf{e^{\prime}}$ parameters to be $\vec{0}$. We set $\alpha=0.1$ and
$\lambda=0.0$ for the critic, and $\alpha^{\prime}=0.1$ and
$\lambda^{\prime}=0.0$ for the actor. Finally, $\beta$ is defined as in Eq. 9
for reward-respecting options and, for the reward-oblivious options, it is
defined to be $1$ upon reaching the hallway state or upon reaching the goal
state, and to be $0$ otherwise. In the two-room gridworld, we learn the
options’ policies for 50,000 time steps, and in the four-room gridworld we
learn the options’ policies for 200,000 time steps. We used a behavior policy
that selected all four actions with equal probability: $\mu(a|s)\doteq 0.25$
for all $s\in\mathscr{S}$ and $a\in\mathscr{A}$. We executed this process
$100$ times in the two-room gridworld and $30$ times in the four-room
gridworld.

###  A.4 Model learning

We used the procedure outlined in Section 3 (Eq. 19-22) to learn the models
for reward-respecting and reward-oblivious options, as well as the transition
model for primitive actions only. As usual, we initialize all weights
($\mathbf{w}^{o}_{r}$ and $\mathbf{w}^{o}_{s^{\prime}}$) and eligibility trace
vectors ($\mathbf{e}_{r}^{o}$ and $\mathbf{e}_{s^{\prime}}^{o}$) to be
$\vec{0}$. We set the step-sizes $\alpha_{r}$ and $\alpha_{p}$, to be $0.1$ in
the two-room gridworld and to be $0.05$ in the four-room gridworld, and the
eligibility trace parameters, $\lambda_{r}$ and $\lambda_{p}$, to be zero. In
the two-room gridworld, we learn the options’ models for 50,000 time steps,
and in the four-room gridworld we learn the options’ policies for 200,000 time
steps. We use the same number of time steps for both transition and reward
models. We compute the RMSE reported in Figure 3 at each time step. We
executed this process $100$ times in the two-room gridworld and $30$ times in
the four-room gridworld.

###  A.5 Planning with options and approximations

We use approximate value iteration (AVI) as the planning algorithm in all
experiments in the tabular case, following Eq. 24 and 25 closely. In that
context, there are not many parameters to report. We perform 6,000 AVI updates
in the two-room gridworld, and 20,000 AVI updates in the four-room gridworld.
We consider value iteration has converged if a change smaller than $10^{-4}$
is observed. As mentioned in the main text, we selected the states to be
updated randomly. Finally, we executed this process $100$ times in the two-
room gridworld and $30$ times in the four-room gridworld.

##  B Multiple options and stochasticity

In Section 6, we presented the outcome of the STOMP progression when multiple
options were being used for planning. Due to space constraints, we only
presented the planning performance of different options, briefly mentioning
policy and model learning. In this section we present results in the four-room
domain equivalent to those presented in Sections 2 and 3.

We use the four-room episodic gridworld depicted in Figure 8, with a start
state in one room and a terminal goal state in another. Similar to the two-
room gridworld, a reward of $+1$ is received on reaching the goal, which ends
the episode. Passing through the gray region produces a reward of $-1$ per
step, while all other transitions produce a reward of zero. The discount
factor is $\gamma=0.99$. There are four actions, available in all nonterminal
states: up, down, left, and right. Importantly, any chosen action causes the
agent to _stochastically_ move in the corresponding direction with probability
$\nicefrac{{2}}{{3}}$ and in one of the other three directions with
probability $\nicefrac{{1}}{{9}}$. The parameters used were described in
Appendix A. We now focus on discussing the results obtained at the end of each
step of the option-learning and model-learning steps of the STOMP progression,
which we did not discuss in the main paper.

###  B.1 Option learning for feature attainment

As in Section 2, Figure 7 shows the convergence for the hallway-feature
attaining subtasks, but now in the four-room gridworld. We used a behavior
policy that selected all four actions with equal probability: $\mu(a|s)\doteq
0.25,\forall s\in\mathscr{S},a\in\mathscr{A}$. The state-feature vectors were
1-hot, producing a tabular representation. The policy was of the softmax form
with linear preferences:

$\pi(a|s,{\bm{\theta}})\doteq\frac{e^{{\bm{\theta}}{{}^{\top}}{\bm{\phi}}(s,a)}}{{\textstyle\sum_{b}}e^{{\bm{\theta}}{{}^{\top}}{\bm{\phi}}(s,b)}},$
(26)

where the state-action feature vectors
${\bm{\phi}}(s,a)\in{\mathbb{R}}^{d^{\prime}},\forall
s\in\mathscr{S},a\in\mathscr{A}$ were again 1-hot or tabular. We ran for
200,000 steps and averaged the results over 30 runs.

Figure 7: The off-policy learning algorithm applied to find the optimal option
for the reward-respecting subtask for attaining the hallway features (H1, H2,
H3, and H4, clockwise). The data comes from a policy in which all four actions
are selected with equal probability. The plot shows the progress of learning.
The blue line (right scale) shows the value of the start state for the learned
option, and the red line (left scale) shows the RMSE between the learned and
optimal value functions. Each line is averaged over 30 runs and the shading
represents the standard error.

Figure 7 depicts the root mean squared error, throughout time, between the
estimated subtask value, $\hat{v}(S_{t},{\bf w}^{h}_{t})$, for the subtask for
attaining the $h$th feature, corresponding to one of hallway states, and the
_optimal subtask value_ ,
$v_{*}^{h}(s)\doteq\max_{\pi,\beta}v_{\pi,\beta}^{h}(s)$, for all
$s\in\mathscr{S}$. The plots are organized in clockwise order for hallways H1,
H2, H3, and H4. These curves show actor-critic is able to effectively learn
the correct option policy. The main difference from the plot in Figure 2 is
the duration of learning. This is because the environment is bigger and it is
stochastic, requiring more samples for accurate value estimation. For the
hallway-H4-reaching subtask, we see more samples would be beneficial for a
more accurate option, but this does not seem to impact the planning
performance shown in Figure 4.

Figure 8 depicts the corresponding learned option policies. As before, the
option terminates either at the bottleneck state or at the goal state, as
shown in red. Reward-respecting options trade-off rewards, the value of the
state, and the stopping bonus. Reward-respecting options do take into
consideration the fact that the environment’s stochasticity is not under the
agent’s control. For the most part, the options take the shortest path to the
appropriate hallway or the goal state, but the uncontrolled stochasticity and
the negative reward region causes some options to take a longer path. For
example, when in the SW room, options sometimes take the roundabout way to
reach H3 and H4.

Figure 8: Illustration of reward-respecting options learned in a stochastic
gridworld. Passing through the gray region between the start and hallway
states produces a reward of $-1$ per step, while all other transitions produce
a reward of zero. Reaching the goal state produces a reward of $+1$.
Stochastic transitions make states close to the shaded region less desirable
due to the natural uncertainty over their return.

###  B.2 Model learning

We used the UWT procedure we described in the main paper to learn the models
in the four-room gridworld. As shown in Figure 9, this procedure allow us to
efficiently learn both transition and reward models. The plots are organized
in clockwise order for hallways H1, H2, H3, and H4. The main difference from
the plot in Figure 3 is the duration of learning. This is because the
environment is bigger and it is stochastic, requiring more samples for
accurate value estimation.

Figure 9: Transition and reward models are efficiently learned online (H1, H2,
H3, and H4, clockwise). The red line (left scale) shows the root mean square
error (RMSE) between the learn reward model for the option and the idealized
reward model. The blue line (right scale) shows the RMSE between the learned
transition model for the option and the idealized state-transition model. The
state-transition model captures discounting and termination. All lines were
averaged over 30 runs and the shading represents the standard error.

We also evaluated the impact of planning with imperfect models, using
approximate value iteration, as described in the main paper. The final
performance is what we report in Figure 5b. Here we report the performance of
planning not when the model was learned for 200,000 time steps, but when it
was learned for $10$k, $20$k, $30$k, and $40$k time steps. Planning leads to
near-optimal performance using an imperfect model trained for 50,000 steps.
Further training improves model error but does not significantly improve
planning in this environment.

Figure 10: Performance of planning for learned, approximate models with
different levels of accuracy. In this environment, 50,000 steps of model
learning is sufficient to achieve near-optimal planning performance. All lines
were averaged over 30 runs and the shading represents the standard error.


# FlapAI Bird: Training an Agent to Play Flappy Bird Using Reinforcement
Learning Techniques

Tai Vu
Department of Computer Science
Stanford University
<EMAIL_ADDRESS>Leon Tran
Department of Computer Science
Stanford University
<EMAIL_ADDRESS>
###### Abstract

Reinforcement learning is one of the most popular approaches for automated
game playing. This method allows an agent to estimate the expected utility of
its state in order to make optimal actions in an unknown environment. We seek
to apply reinforcement learning algorithms to the game Flappy Bird. We
implement SARSA and Q-Learning with some modifications such as
$\epsilon$-greedy policy, discretization and backward updates. We find that
SARSA and Q-Learning outperform the baseline, regularly achieving scores of
1400+, with the highest in-game score of 2069.

##  1 Introduction

In the past decade, the advent of artificial intelligence (AI) has caused
major advancements in speech recognition, machine translation, and computer
vision, among other fields. One particular application has been to teach AI
systems to play games. In fact, AI agents have surpassed human ability in
classic arcade games and Go [1] [2].

The most common way that these agents are trained to play games is using
reinforcement learning methods. Reinforcement learning is the process where an
agent in a certain state $s$ chooses to take some action $a$ in a predefined
environment and receives some reward $r$. As the agent takes more actions, it
is able to determine, for each $s$, which action is the best to take if the
agent wants to maximize its score.

We specifically focus on how reinforcement learning can be applied to newer
games like Flappy Bird. In the game, a bird moves at a constant horizontal
rate and falls according to in-game gravity. There are pipes with gaps that
are initialized at random points. The player must navigate the bird through
the pipes by tapping on the bird to make the bird jump vertically. After
overcoming each obstacle, the player gains 1 in-game point. The game ends when
the bird collides with a pipe or hits the ground. The player’s goal is to
maximize the total score.

In this project, we apply various AI algorithms to train an agent to play
Flappy Bird. Specifically, the approaches we use are SARSA and Q-Learning. We
experiment with SARSA and different variants of Q-Learning: a tabular
approach, Q-value approximation via linear regression, and approximation via a
neural network. In addition, we implement several modifications including
$\epsilon$-greedy policy, discretization and backward updates. After comparing
the Q-Learning and SARSA agents, we find that Q-Learning agents perform the
best with regular scores of 1400+ and a maximum score of 2069. SARSA agents
decisively outperform the baseline with a maximum score of 832.

##  2 Related Work

We have seen successful attempts at training agents to play Atari games using
reinforcement learning. Mnih et al. tried this approach on seven Atari 2600
games and found that agents trained using Q-Learning outperformed human
experts on three Atari games [3]. Instead of engineering features from scratch
to represent state $s$ and using those features to estimate $Q(s,a)$, Mnih et
al. used a convolutional neural network to learn $Q(s,a)$ instead.

There have been attempts to play Flappy Bird using Q-Learning with
convolutional neural networks as function approximators as well. A team tried
using a similar approach to Mnih et al. by passing an image of the screen into
a convolutional neural network [1]. We were inspired by this project and Mnih
et al. to experiment with convolutional neural networks to estimate $Q$
values. Our approach differs from these two resources in network architecture
and hyperparameter choices, however.

Flappy Bird was a natural choice of game, because of work done by Mnih et al.
and the novelty of teaching AI agents to play newer games. While we thought
that using Q-Learning with convolutional neural networks to play Flappy Bird
was an interesting application, we also wanted to see how it compared to other
variants of Q-Learning as well. Therefore, we took the base Q-Learning
algorithm and modified it in different ways, such as adjusting our exploration
probability $\epsilon$, discretizing our screen into grids of varying sizes,
and using different function approximators to estimate $Q(s,a)$. We find that
simpler methods like Q-Learning and SARSA outperform more complex deep
Q-Learning approaches.

##  3 Infrastructure

We decided to use OpenAI Gym, which is an environment for training
reinforcement learning agents [4][5]. OpenAI Gym provided an emulator for
Flappy Bird and a useful representation of game states, namely the positions
of the nearest two pipes, and the y-position of the bird. There were also
images of the screen that were accessible from using the emulator. We slightly
modified the state in the ways noted in section 5 and implemented a reward
function.

##  4 Implementation

Our implementation for the program was structured into the following
modularized files.

  * •

main.py: The main program that processes command line arguments and runs
different agents.

  * •

FlappyBirdGame.py: The game environment for Flappy Bird.

  * •

TemplateAgent.py: A template for different agents.

  * •

BaselineAgent.py: Baseline agent.

  * •

SARSAAgent.py: SARSA agent.

  * •

QLearningAgent.py: Q-Learning agent.

  * •

FuncApproxLRAgent.py: Function approximation agent with linear regression.

  * •

FuncApproxDNNAgent.py: Function approximation agent with a feed forward neural
network.

  * •

FuncApproxCNNAgent.py: Function approximation agent with a convolutional
neural network.

  * •

utils.py: A file containing some helper functions.

Link to our project: https://github.com/taivu1998/FlapAI-Bird

##  5 Model

###  5.1 States

We came up with two formulations of state. The second formulation in Table 2
is only used in the Q-Learning agents that use a convolutional neural network
as a function approximator. The first formulation of state in Table 1 is used
in the remaining SARSA and Q-Learning agents.

Note that the $80\times 80\times 1$ input image has been convolved into a
$17\times 17\times 32$ output volume and flattened. The remaining features
$act$ and $y_{vel}$ are then appended to this flattened vector. Then, this
whole vector is passed into the fully connected layer of the network.

Feature | Description
---|---
$x_{diff}$ | The horizontal distance between the bird and the next pipe.
$y_{diff}$ | The vertical distance between the bird and the bottom pipe.
$y_{vel}$ | The in-game velocity of the bird.

Table 1: State representation for SARSA, Q-Learning and
function approximation using linear model and FFNN Feature | Description
---|---
$image$ | A 80 $\times$ 80 grayscale image of the screen.
$y_{vel}$ | The in-game velocity of the bird.

Table 2: State representation for function approximation using CNN Figure 1: A
graphic illustration of the first state representation

###  5.2 Actions

We represented the an action $a$ using $a\in\\{0,1\\}$. In particular, $0$
represents "flap", and $1$ represents "do not flap", as predefined by the game
environment we used.

###  5.3 Rewards

OpenAI Gym steps through frames of the game and sets a terminal flag if the
agent hits a pipe in the current frame. We decided to formulate rewards by
giving the agent a positive reward of +5 every time it passes a pipe and -1000
for hitting a pipe. This is to heavily discourage the bird from making bad
decisions and dying. In addition, we gave the bird a smaller reward of +0.5
for surviving in between frames. This is to incentivize the bird to stay alive
even if it has not passed a pipe yet. We found that without this +0.5 reward,
the bird essentially moves randomly in between pipes. This makes sense, as the
bird does not prefer one state to another in between pipes, if it is not
rewarded for staying alive. Only when the bird passes a pipe does it learn the
optimal actions to get to the pipe in the first place.

##  6 Methods

###  6.1 Baseline

For our baseline algorithm, we simply applied a random policy. In particular,
for each state, the agent selects action 0 with some probability $p$ and
selects action 1 with probability $1-p$. Here, we experimented with $p=0.5$.
We believed that this was a good baseline because it was relatively simple to
implement and defined a clear strategy that a better trained agent could
outperform.

###  6.2 Oracle

Since Flappy Bird has no maximum score, we decided that the oracle should be
an agent that achieves an infinite score. Therefore, any of our agents will be
outperformed by the oracle.

###  6.3 Reinforcement Learning Algorithms

We decided to use both on-policy and off-policy, model-free reinforcement
learning algorithms to teach our agent to play Flappy Bird. We chose to do so
because rewards and transitions are unknown to the agent. Therefore, we used
Q-Learning and SARSA. We also made modifications to Q-Learning, by adjusting
$\epsilon$, discretizing the state space, using function approximation, and
using backward Q-Learning. We also modified SARSA by discretizing our screen
into $10\times 10$ grids, adding backward updates, and varying $\epsilon$.

###  6.4 SARSA

SARSA [6] is an on-policy reinforcement learning algorithm that estimates
$\hat{Q}_{\pi}(s,a)$ for a given state-action pair $(s,a)$, where the agent is
following some policy $\pi$. SARSA takes in tuples
$(a,a,r,s^{\prime},a^{\prime})$ and updates our estimates for
$\hat{Q}_{\pi}(s,a)$ as follows:

$\hat{Q}_{\pi}(s,a)=(1-\eta)\hat{Q}_{\pi}(s,a)+\eta(r+\gamma\hat{Q}_{\pi}(s^{\prime},a^{\prime}))$

where $r$ is the reward for taking action $a$ in state $s$, $\gamma$ is some
discount value (in this case $\gamma=1$), and for some choice of $\eta$.
Intuitively, SARSA creates a bootstrapped estimate $\hat{Q}_{\pi}(s,a)$ by
minimizing the difference between that estimate and the "true value" of our
policy $r+\gamma\hat{Q}_{\pi}(s^{\prime},a^{\prime})$ over many iterations.

###  6.5 Q-Learning

Q-Learning [7] is an off-policy reinforcement learning algorithm. Q-Learning
creates bootstrapped estimates of $\hat{Q}_{opt}(s,a)$ by minimizing the
difference between the estimate and the "true value" of our policy
$\displaystyle r+\gamma\max_{a^{\prime}}\hat{Q}_{opt}(s^{\prime},a^{\prime})$.
It is similar to SARSA, except that it has the agent take the optimal action
(according to our current Q-value estimates) rather than an action defined by
the policy $\pi$. At the end of each iteration, our Q-value estimates
$\hat{Q}_{opt}(s,a)$ are updated according to the following rule:

$\hat{Q}_{opt}(s,a)=(1-\eta)\hat{Q}_{opt}(s,a)+\eta(r+\gamma\max_{a^{\prime}}\hat{Q}_{opt}(s^{\prime},a^{\prime}))$

where $r$ is the reward for taking action $a$ in state $s$, $\gamma$ is some
discount value (in this case $\gamma=1$), and for some choice of $\eta$.

###  6.6 Modifications

We modified Q-Learning and SARSA in the following ways to speed up learning
and improve performance. The implementations of the base algorithms had low
performance on our task.

####  6.6.1 Discretization

Initially, we treated our screen as a $288\times 512$ matrix of pixels, where
each individual pixel as a location for our agent. We quickly found out that
the number of locations were too large. Therefore we chose to treat our screen
as discrete grids of sizes $5\times 5$, $10\times 10$, $20\times 20$,
$50\times 50$, and $100\times 100$ to reduce the number of states our bird
could occupy.

Specifically, for a positive integer $n$ and a level of discretization $r$, we
discretize $n$ using the following formula:

$\displaystyle d(n,r)=r\left\lfloor{\frac{n}{r}}\right\rfloor$

####  6.6.2 Epsilon-Greedy

We implemented an epsilon-greedy approach to start off because we needed some
way to explore our state space in early iterations. In our implementations of
epsilon-greedy Q-Learning and SARSA, we experiment with
$\epsilon\in\\{0,0.1\\}$. This means with probability $\epsilon$, our agent
moves randomly, and with probability $1-\epsilon$ our agent takes an action
$a^{*}$, where $\displaystyle a^{*}=\max_{a}\hat{Q}(s,a)$. We have the
following algorithms for Q-Learning and SARSA in this case:

Algorithm 1 Q-Learning with epsilon-greedy policy

1:Initialize all Q-values to 0

2:for iteration = 1, N do

3: Initialize memory $\mathcal{M}$

4: Set initial state $s_{1}$

5: Set $t=1$

6: while $s_{t}$ is not terminal do

7: With probability $\epsilon$ select a random action $a_{t}$ from $\\{0,1\\}$

8: otherwise select $a_{t}=\max_{a}(Q(s_{t},a))$

9: Perform action $a_{t}$ and observe next state $s_{t+1}$ and reward $r_{t}$

10: Store observation $(s_{t},a_{t},r_{t},s_{t+1})$ in $\mathcal{M}$

11: Increment $t$

12: end while

13: for observation $(s_{i},a_{i},r_{i},s_{i+1})$ in $\mathcal{M}$ do

14: Set $\displaystyle
Q(s_{i},a_{i})=(1-\eta)Q(s_{i},a_{i})+\eta(r_{i}+\gamma\max_{a_{i+1}}Q(s_{i+1},a_{i+1}))$

15: end for

16:end for

Algorithm 2 SARSA with epsilon-greedy policy

1:Initialize all Q-values to 0

2:for iteration = 1, N do

3: Initialize memory $\mathcal{M}$

4: Set initial state $s_{1}$

5: Set $t=1$

6: With probability $\epsilon$ select a random action $a_{t}$ from $\\{0,1\\}$

7: otherwise select $a_{t}=\max_{a}(Q(s_{t},a))$

8: while $s_{t}$ is not terminal do

9: Perform action $a_{t}$ and observe next state $s_{t+1}$ and reward $r_{t}$

10: With probability $\epsilon$ select a random action $a_{t+1}$ from
$\\{0,1\\}$

11: otherwise select $a_{t+1}=\max_{a}(Q(s_{t+1},a))$

12: Store observation $(s_{t},a_{t},r_{t},s_{t+1},a_{t+1})$ in $\mathcal{M}$

13: Increment $t$

14: end while

15: for observation $(s_{i},a_{i},r_{i},s_{i+1},a_{i+1})$ in $\mathcal{M}$ do

16: Set $Q(s_{i},a_{i})=(1-\eta)Q(s_{i},a_{i})+\eta(r_{i}+\gamma
Q(s_{i+1},a_{i+1}))$

17: end for

18:end for

####  6.6.3 Forward versus Backward Updates

We also experimented with backward updates. The updates were performed from
the first frame to the most recent frame in forward updates. Backward updates
performed Q-value updates in the opposite direction; this allows more
important information, specifically when the bird hits the pipe, to be
considered first.

###  6.7 Function Approximation

Similar to the original version of Q-Learning, function approximation [8]
attempts to minimize the difference between the predicted value
$\hat{Q}_{opt}(s,a)$ and the target value $\displaystyle
r+\gamma\max_{a^{\prime}}\hat{Q}_{opt}(s^{\prime},a^{\prime})$. In other
words, the implied loss function is

$\mathcal{L}(s,a,s^{\prime})=\left(\hat{Q}_{opt}(s,a)-(r+\gamma\max_{a^{\prime}}\hat{Q}_{opt}(s^{\prime},a^{\prime}))\right)^{2}$

However, instead of using the above update rule, function approximation
estimates the Q-values $\hat{Q}_{opt}(s,a)$ with a function $h$ and a set of
weights $w$, i.e.

$\hat{Q}_{opt}(s,a)=h(s,a;w)$

####  6.7.1 Linear Regression

We chose to estimate our Q-values by using a linear model. Specifically, we
used the first formulation of state as described in section 5.1, $\phi(s,a)$,
with an action appended at the end. We took weight vector
$\theta\in\mathbb{R}^{3}$ and a bias term $b\in\mathbb{R}$ and estimated
Q-values as follows:

$\hat{Q}(s,a)=\theta^{T}\phi(s,a)+b$

We only used linear function approximation for Q-Learning.

####  6.7.2 Feed-Forward Neural Network (FFNN)

We also chose to use a more complex estimator in the form of a feed-forward
neural network. Our network consisted of a 3-neuron input layer, a 50-neuron
hidden layer, 20-neuron hidden layer, and 2-neuron output layer. If we call
the size of the current layer $m$, and the size of the previous layer $n$,
then each layer is modeled as follows:

$a=f(Wa_{prev}+b)$

where $f$ is some nonlinearity (e.g. tanh, ReLU, sigmoid). In this case, we
use the ReLU functions. $a_{prev}\in\mathbb{R}^{n}$ is the output of the
previous layer, $W\in\mathbb{R}^{m\times n}$ is the weight matrix,
$b\in\mathbb{R}^{m}$ is the bias vector, and $y\in\mathbb{R}^{m}$ is the
output of the current layer.

Our 2-neuron output layer was set up such that we get the Q-values of the
agent being in its current state $s$ and taking action $0$ or $1$. We chose
the action associated with the neuron with the highest output.

####  6.7.3 Convolutional Neural Network (CNN)

We believed that the game images were also a good way to encode state, so we
used our second formulation of state in section 5.1. Since we were working
with image data, a convolutional neural network was a natural choice. We
preprocessed the input images by removing the background, turning them into
grayscale and resizing them to 80 x 80. This helped limiting the number of
parameters and eliminated unnecessary features like backgrounds and colors.

We used two convolutional layers, one using sixteen $5\times 5$ kernels with
stride $2$, and another with thirty-two $5\times 5$ kernels with stride $2$.
Finally, we flattened the output of the last convolutional layer and
constructed our state vector $x$, as described in section 5.1, where
$x\in\mathbb{R}^{9248}$.

We passed $x$ through fully connected layers. In this case, our nonlinearity
$f$ is the ReLU function. The fully connected layers consisted of a
9248-neuron input layer and a 2-neuron output layer.

The output of the 2-neuron layer represented the Q-values of the agent being
in state $s$ and taking two actions 0 and 1.

##  7 Results and Discussion

###  7.1 Model Performance: SARSA and Q-Learning

We decided to evaluate each model based on its maximum score and average
score. We chose to do so because both are important in determining which
algorithm is "best" for playing Flappy Bird. The maximum score represents the
peak-performance for an algorithm, while the average score is a better
descriptor of the performance consistency for each agent when trained for a
large number of iterations.

Figures 3 and 3 show some examples of the curves that we see when training our
agent for 10,000 iterations using Q-Learning. Across all variants of
Q-Learning that we implemented, we see that the maximum score and average
score are increasing. Especially since the average score is increasing
steadily, we know that the agent is gradually learning to play the game
exponentially better as we increase the number of iterations.

Figure 2: Training curve for Q-Learning,
backward updates, $\epsilon=0.1$

Figure 3: Training curve for Q-Learning,
forward updates, $\epsilon=0$

Algorithm | Discretization | Update Order | Epsilon | Mean | Standard Deviation | Max
---|---|---|---|---|---|---
Baseline | None |  |  |  0.130 |  0.357 |  2
Q-Learning | 10 | Backward | 0 | 209.298 | 216.967 | 1491
Q-Learning | 10 | Backward | 0.1 | 159.398 | 162.553 | 1224
Q-Learning | 10 | Forward | 0 |  67.210 |  69.067 |  582
Q-Learning | 10 | Forward | 0.1 |  63.480 |  63.346 |  448
Q-Learning | None | Backward | 0 |  0.507 |  0.796 |  4
Q-Learning | None | Backward | 0.1 |  0.772 |  0.942 |  5
Q-Learning | None | Forward | 0 |  0.386 |  0.644 |  4
Q-Learning | None | Forward | 0.1 |  0.316 |  0.593 |  3
Q-Learning | 5 | Backward | 0 |  36.236 |  41.438 |  438
Q-Learning | 50 | Backward | 0 |  80.486 |  77.624 |  622
SARSA | 10 | Forward | 0 |  87.553 |  87.310 |  530
SARSA | 10 | Forward | 0.1 | 117.317 | 112.998 |  811
Table 3: Comparision across all levels of hyperparameters for SARSA and
Q-Learning, 8000 iterations

###  7.2 SARSA versus Q-Learning

We first seek to understand the difference in performance between Q-Learning
and SARSA. From the plots in Figure 4, when discretization is held constant at
$10\times 10$, we see that Q-Learning has a higher maximum than SARSA earlier
on. This is likely because Q-Learning is an off-policy algorithm and, thus, is
able to estimate the optimal policy faster than SARSA, an on-policy algorithm
can. Especially when trained for only a few thousand iterations, the agent
trained by SARSA must try out both the zero and one actions at different
states to find the one that yields the greatest value, rather than following a
supposed optimal policy directly, like Q-Learning can. Once we trained our
SARSA agent for more iterations, though, we see that it does perform the same
in terms of maximum and average score as our Q-Learning Agent.

Figure 4: Training curve for Q-Learning, SARSA, forward updates, $\epsilon=0$

###  7.3 Comparision of Discretization Levels

We also chose to try out different discretizations of our screen. We
experimented with $5\times 5$, $10\times 10$, $20\times 20$, $50\times 50$,
and $100\times 100$. The main trade-off that we considered was the precision
of our Q-value estimate versus the reduction in state space.

Implementing Q-Learning without discretization caused our agent to converge
extremely slowly. Since our screen was $288\times 512$, there were about
$288\times 512$ different locations the bird could be, and $16$ velocities the
bird could have. Therefore, there were roughly $288\times 512\times 16$ states
to explore. The number of states were too large, which translated to the bird
only sparsely exploring the state space. For most states $s$ and action $a$,
we have $Q(s,a)=0$ because most states are unexplored. As a result, the agent
would move randomly most of the time when we ran it for 8000 iterations,
thereby making it no better than the baseline. It will take an unreasonably
large number of iterations to explore all states.

On the other hand, discretizing to an extreme extent, like in the $50\times
50$ case, converges quickly but leads to a suboptimal solution. Quick
convergence is the result of the agent being able to explore most of the state
space. However, we make a strong, and often false, assumption that every state
in a $50\times 50$ grid has the same Q-value. Thus, we are not able to
converge to the optimal solution, simply because our initial modeling
assumptions were false.

Out of the different discretizations, the $10\times 10$ discretization level
performs the best, with a max score of 1896. This means that slicing the
screen into $10\times 10$ grids best trades off the Q-value estimate precision
and the state space size. After a certain number of iterations, we see that
each line in Figure 5 plateaus. This corresponds to convergence; once the
state space is completely explored, then the agent has found the optimal
policy at their level of discretization. Note that, as our discretization
level become smaller, the line plateaus slower, but attains a higher score.
Naturally, this follows our intuition, that no discretization, which
corresponds to the $1\times 1$ discretization level will perform the best as
the number of iterations increase, but will take the longest to converge.

Figure 5: Maximum score achieved for Q-Learning, backward updates,
$\epsilon=0$

###  7.4 Comparison of $\epsilon$ greedy policies

Our next batch of experiments explored the effect of an epsilon-greedy policy.
One of the most interesting differences came from evaluating the performance
of Q-Learning with $10\times 10$ discretization with and without an epsilon-
greedy approach, where $\epsilon=0.1$ or $\epsilon=0$. Surprisingly, we see
that the model where $\epsilon=0.1$ performed worse than when $\epsilon=0$.
This is consistent with the cliff-walking effect detailed by Sutton and Barto
[2], where agents trained by Q-Learning tend to choose paths that are at the
"edge" of the cliff. Our pipe represents the cliff, because it is associated
with a negative value. We see that the Q-Learning agents stay very close to
pipes; using an epsilon-greedy approach is almost guaranteed to cause the bird
to choose a random action when it is passing through a pipe. Acting randomly
inside a pipe is likely to end the game. This is reflected in our results,
where the averages of the two are quite similar, 225 for $\epsilon=0$ and 154
for $\epsilon=0.1$. However, for maximum score, we get 1896 for $\epsilon=0$
and 1125 for $\epsilon=0.1$, which is a significant difference.

In the emulator, SARSA agents try to maximize their distance from the pipes
when passing in between them. This is in direct contrast to Q-Learning which
remains close to one pipe. Therefore, the impact of an epsilon-greedy policy
is less pronounced for SARSA. This is evident in Figures 7 and 7, where the
difference between maximum scores for SARSA of 448 versus the difference
between maximum scores for Q-Learning of 987. This is because a random move is
not likely to end the game if a "safe" middle path is take compared to a path
close to a pipe.

In addition, both the Q-Learning and SARSA agents are able fully explore the
state space, since it is discretized into $10\times 10$ grids. Thus, there is
no advantage to having an $\epsilon>0$. Having an $\epsilon>0$ is only useful
when the state space is too large to explore in the first place.

Figure 6: Epsilon comparisions for Q-Learning,
forward updates, $10\times 10$ discretization

Figure 7: Epsilon comparisions for SARSA,
forward updates, $10\times 10$ discretization

###  7.5 Comparison of Forward versus Backward Q-Learning

We observe in Figure 8 that backward Q-Learning increases the scores
significantly to about 2000 after the first 3000 iterations. Then, the scores
stay around 1500 for the rest of the time. Meanwhile, the scores produced by
forward updates go up more gradually and stay below the figures for backward
updates most of the time. However, the scores eventually reach 2000 after
10000 iterations. Hence, we can see that backward Q-Learning converges to the
optimal policy much more quickly than forward Q-Learning does. Here, we define
the optimal policy as the policy determined the best set of Q-values that an
agent converges to after a sufficient number of iterations, given a certain
level of discretization. For example, in Figure 8, backward Q-Learning with 10
x 10 discretization converges to the optimal policy that produces scores of
around 1500 after 3500 iterations.

The reason while backward Q-Learning leads to faster convergence than forward
Q-Learning does is that backward updates allow the agent to learn important
information earlier. Specifically, backward Q-Learning performs updates of
Q-values from the most recent and also the most important experience first,
which is the frame when the bird hits the pipes. This information is then
propagated through all earlier states in one iteration. Thus, the bird learns
the bad states that leads to hitting the pipes more quickly and effectively,
so it is able to avoid the pipes after a small number of iterations.

For example, consider a simple iteration with the sequence
$s_{1},a_{1},r_{1},s_{2},a_{2},r_{2},s_{3}$, where $s_{3}$ is a terminal state
where the bird hits the pipes. If we perform forward Q-Learning,
$Q(s_{1},a_{1})$ will get updated first based on $s_{2}$ and it receives no
information about the pipes at $s_{3}$. However, if we perform backward
Q-Learning, $Q(s_{2},a_{2})$ will get updated first based on $s_{3}$ and it
will change significantly because $r_{2}=-1000$. Then, $Q(s_{1},a_{1})$ get
updated based on $s_{2}$, so $s_{1}$ now gets notified about the pipes at
$s_{3}$ via $s_{2}$.

Figure 8: Comparison of forward and backward updates
for Q-Learning, $\epsilon=0$, 10 $\times$ 10 discretization

###  7.6 Model Performance: Function Approximation

All our attempts at function approximation performed comparable to our
baseline, which is noted in Figure 10. We believe that this is due to various
shortcomings in our formulation of features and neural networks as described
below.

Algorithm | Discretization | Update Order | Epsilon | Mean | Standard Deviation | Max
---|---|---|---|---|---|---
Baseline |  |  | 0.1 | 0.130 | 0.357 | 2
Linear Regression | None | Backward | 0.1 | 0.210 | 0.415 | 2
FFNN | None | Backward | 0.1 | 0.326 | 0.437 | 3
CNN | None | Backward | 0.1 | 0.280 | 0.372 | 3
Table 4: Comparison accross all Q-Learning agents with function approximation,
backward updates, $\epsilon=0.1$

####  7.6.1 Linear Regression

For linear regression, a line was likely too simple to capture the underlying
complexities around the value of a certain state. Intutively, this makes
sense; for example, for our $x_{diff}$ feature as described in section 5.1,
there is not a clear linear relationship between the reward an agent receives
and the distance it is from the pipe. In other words, moving closer to a pipe
does not increase the expected reward of an agent by a fixed amount.
Therefore, we needed a more complicated model to estimate our Q-values.

####  7.6.2 Feed-Forward Neural Network (FFNN)

After we saw that our linear regression failed to outperform the baseline, we
decided to switch to a model that could model a highly nonlinear relationship
between the states and the resultant Q-values. The FFNN had a similar issue as
linear regression; while the model itself has higher variance, our inputs were
still too simple. Essentially, we believed that only having $x_{diff}$,
$y_{diff}$, and $y_{vel}$ were not enough to predict the value of state $s$.

###  7.7 Convolutional Neural Network (CNN)

We wanted to add more relevant features than our initial three in section 5.1.
Therefore, we created a second formulation of state, also described in 5.1.
However, this formulation of state did not seem to make a difference, most
likely because we trained it for too few iterations. Looking up related
resources, we found that a deep learning approach to Flappy Bird requires
learning over hundreds of thousands of iterations [9]. We trained our network
for 8000 iterations due to limited computing resources. This result was
expected; no discretization was applied to the grid beforehand and, as a
result, the CNN must learn the Q-values for all states in a large state space.
Thus, it will take many iterations for the policy learned by the CNN to be
optimal.

##  8 Conclusion

In this paper, we implement and compare the performance of agents trained by
modified variants of the SARSA and Q-Learning algorithms. We notice that
discretization techniques helped our agent converge more quickly within 8000
iterations and achieved a reasonably high score of 2069. We also find that,
with discretization, epsilon-greedy policies generally perform worse for
Q-Learning on average. Finally, we find that updating our Q-values backwards
temporally helps our Q-values converge their true values faster, as well. For
function approximation, we go through a natural progression of models,
starting off with a simple linear model and progressing to a CNN. However, we
find none of them outperformed the baseline.

Altogether, all of our Q-Learning and SARSA agents outperform the baseline. It
was only the Q-Learning with function approximation agents that either
performed at or slightly above the baseline. This was largely due to poor
feature engineering or lack of training. In the end, our Q-Learning agent with
$10\times 10$ discretization, backward updates, and $\epsilon=0$ performed the
best.

In the future, training the CNN for hundreds of thousands of iterations is
likely to be successful. We would also want to adjust hyperparameters and
experiment with more levels of discretization to see if an agent trained with
smaller levels of discretization can outperform our current top model. In
addition, we would like to try adding polynomial features in our linear
regression and FFNN models to have them represent more complex relationships
in our data.

## References

  * [1] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis, “Human-level control through deep reinforcement learning,” in Nature 518, p. 529–533, 2015.
  * [2] R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction.  Cambridge, Massachusetts: The MIT Press, 2nd ed., 1992.
  * [3] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller, “Playing atari with deep reinforcement learning,” arXiv preprint arXiv:1312.5602, 2013.
  * [4] G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba, “Openai gym,” arXiv preprint arXiv:1606.01540, 2016.
  * [5] N. Tasfi, “Ple: A reinforcement learning environment,” 2016.
  * [6] G. A. Rummery and M. Niranjan, “On-line q-learning using connectionist systems,” 1994.
  * [7] C. J. C. H. Watkins and P. Dayan, “Q-learning,” in Machine Learning volume 8, p. 279–292, 1992.
  * [8] F. S. Melo and M. I. Ribeiro, “Q-learning with linear function approximation,” in International Conference on Computational Learning Theory, pp. 308–322, 2007.
  * [9] B. Lau, “Using keras and deep q-network to play flappybird,” 2016.
  * [10] L. Sobrecueva, “gym-ple,” 2018.