# Adversarial Attacks to Reward Machine-based Reinforcement Learning

Lorenzo Nodari

(July 2023)

See pages 1 of frontespizio.pdf

###### Contents

  1. 1 Introduction
  2. 2 Background
    1. 2.1 Artificial Intelligence
      1. 2.1.1 Tasks, agents, and environments
      2. 2.1.2 Agent functions and programs
      3. 2.1.3 Characterization of task environments
    2. 2.2 Reinforcement Learning
      1. 2.2.1 Markov Decision Processes
      2. 2.2.2 Classes of RL techniques
      3. 2.2.3 Tabular Q-learning
      4. 2.2.4 Deep Q-learning
      5. 2.2.5 Reward Shaping
  3. 3 Reward machine-based RL
    1. 3.1 Intuition, definitions, and properties
      1. 3.1.1 Full observability
      2. 3.1.2 Partial observability
    2. 3.2 Exploiting RMs for learning
      1. 3.2.1 Q-Learning with Reward Machines
      2. 3.2.2 Automated Reward Shaping
  4. 4 Attacking reward machine-based agents
    1. 4.1 Threat model
      1. 4.1.1 Objective, knowledge and capabilities
      2. 4.1.2 Elements of vulnerability
      3. 4.1.3 Potential attack methodologies
    2. 4.2 Blinding attacks on reward machines
      1. 4.2.1 Random noise attacks
      2. 4.2.2 Choice of blinding strategy
      3. 4.2.3 Timing strategies
      4. 4.2.4 Event-blinding attacks
      5. 4.2.5 Edge-blinding attacks
  5. 5 Evaluation of the proposed attacks
    1. 5.1 Experimental setting
      1. 5.1.1 Benchmark domains
      2. 5.1.2 Agent training
      3. 5.1.3 Testing sessions
      4. 5.1.4 Evaluation metrics
    2. 5.2 Experimental results
      1. 5.2.1 Baseline results
      2. 5.2.2 Random noise attacks
      3. 5.2.3 Event-based blinding attacks
      4. 5.2.4 Edge-based blinding attacks
        1. 6 Conclusions

## Sommario

Negli ultimi dieci anni, il campo dell’Intelligenza Artificiale (IA) ha subito
un enorme sviluppo. Ciò è stato, ed è tuttora, possibile grazie agli ingenti
investimenti nel settore da parte dei principali istituti di ricerca pubblici
e privati, e dalle aziende leader del settore tecnologico. In particolare, uno
dei principali fattori alla base di tale interesse verso l’IA può essere
identificato nei risultati ottenuti grazie a nuove, promettenti tecniche, che
stanno dimostrando un potenziale di innovazione senza precedenti in una
miriade di ambiti, sia accademici che commerciali. Pertanto, in questo
contesto di rapido progresso, la necessità di studiare le implicazioni, in
termini di sicurezza, derivanti dall’uso di tali tecnologie è più alta che
mai. Una mancanza di analisi in tal senso porterebbe infatti, negli anni a
venire, ad enormi rischi di natura etica, personale ed economica e, nel caso
peggiore, a danni inestimabili alla società e ai singoli individui.

Tra i vari sotto-ambiti dell’IA che stanno alimentando i sopracitati
progressi, un esempio notevole è rappresentato dal Reinforcement Learning
(RL)— _i.e.,_ apprendimento per rinforzo — disciplina che studia i fondamenti
teorici e le tecniche pratiche per la creazione di agenti artificiali in grado
di apprendere autonomamente mediante la sperimentazione di nuovi comportamenti
e la correzione di quelli non adeguati. Grazie a tale approccio, l’uso del
reinforcement learning permette di affrontare problemi la cui soluzione
risulterebbe impossibile a fronte dell’utilizzo di altre tecniche. In tale
ambito, una promettente classe di tecniche correntemente studiate dalla
comunità scientifica nasce dall’utilizzo delle cosiddette Reward Machines
(RM), una rappresentazione strutturata, basata sul formalismo degli automi a
stati finiti, dei segnali di rinforzo utilizzati dagli agenti per orientare il
loro apprendimento. Uno dei principali vantaggi di tale approccio è la
possibilità di migliorare le prestazioni degli agenti addestrati in ambienti
altamente complessi e caratterizzati da parziale osservabilità. Nonostante la
loro rilevanza, ad oggi, e al meglio della mia conoscenza, nella letteratura
in materia non è mai stata proposta alcuna analisi delle implicazioni, in
termini di sicurezza, derivanti dall’utilizzo di tali tecniche.

Alla luce di ciò, la mia tesi mira ad essere una prima analisi sulla sicurezza
degli approcci di reiforcement elarning basati su reward machines, con la
speranza di fungere da base per lo sviluppo di ulteriori studi in materia.
Partendo da un’analisi teorica delle implicazioni di sicurezza derivanti dal
loro utilizzo, questa tesi propone una nuova classe di attacchi mirati a
degradare le prestazioni di agenti ottimi e discute un ampio sprettro di
variazioni sull’approccio alla loro base. Infine, il mio lavoro si conclude
con una presentazione dei risutati ottenuti mediante la valutazione
sperimentale delle tecniche proposte in tre diversi ambienti di test
parzialmente osservabili.

##  Chapter 1 Introduction

Reinforcement Learning (RL) is a sub-field of artificial intelligence (AI)
that deals with the training of autonomous agents that learn while being
guided by a reward signal obtained using iterative interaction with their
environment. In formal terms, the object of study of reinforcement learning is
the optimal solution of Markov Decision Processes (MDPs) and their
generalizations. Following this scheme, an RL agent aims at learning the best
_policy_ for completing its task: a mapping from environment states to actions
to be taken.

In the last decade, following the introduction and refinement of deep-
learning-based algorithms designed explicitly for RL, the field has obtained
astonishing successes in a variety of highly-complex tasks, with robotics
[Li+21], game playing [Vin+19], and conversational AI111See
https://openai.com/blog/chatgpt. URL visited on 26/07/2023 being just a few
notable examples demonstrating the breadth of its impact on today’s artificial
intelligence research. Thus, building on the advances above, recent years’
work has focused on solving some of the issues that still limit RL potential
for many real-world applications, such as its low sample efficiency, the need
for high-quality memory architectures to handle partial observability, the
difficulty associated with the representation of highly-structured tasks and
rewards, and the poor explainability of learned policies.

Neuro-symbolic Reinforcement Learning is an emerging paradigm that can tackle
some of these problems by combining deep learning with symbolic artificial
intelligence techniques such as logics-based knowledge representation and
inference. Following this trend, Reward Machines (RMs) have stood out as a
simple yet effective automata-based formalism for exposing and exploiting
underlying task structure during training, allowing for improved sample
efficiency and demonstrating the ability to converge in partially observable
benchmark environments where state-of-the-art A3C, ACER and PPO algorithms
equipped with LSTM-based memory could not make any progress. These results
sparked the interest of the research community, leading to a high number of
works refining the approach in various ways for both single-agent and multi-
agent settings, _e.g.:_[Fur+22], [Nea+21], [Li+22], [Doh+22], among others.

Despite their relevance, little to no attention has been directed to the study
of the security and robustness of neuro-symbolic approaches, likely due to
their recent appearance in the literature, with most research efforts being
spent on attack techniques targeting traditional deep-learning components in
RL systems, such as policy networks [Pan+22], [Ila+22]. While, in theory, some
of the known attacks on deep reinforcement learning could also apply to neuro-
symbolic systems, the lack of studies addressing the security issues
specifically raised by the introduction of symbolic components makes their
investigation a fundamental requirement for the safe deployment of such
techniques in real-world scenarios.

This issue becomes particularly concerning in light of the fact that, with the
recent advent of neuro-symbolic techniques, the relevance of reinforcement
learning algorithms shows the potential for further increase, due to the vast
possibilities opened by the combination of deep-learning techniques for low-
level perception and actuation, and symbolic components for high-level action
planning and knowledge representation. Furthermore, during the last decade, we
witnessed the fast-paced adoption222See
https://www.ibm.com/watson/resources/ai-adoption and
https://www.ibm.com/watson/resources/ai-adoption for reference. URLs visited
on 27/07/2023. of artificial intelligence techniques in a plethora of both
academic and industrial research fields, enterprise applications and consumer-
ready services. Consequently, the number of potential risks arising from the
use of AI-powered solutions has vastly increased as well, thus determining a
greater need for the evaluation of their robustness.

The autonomous driving technology found in Tesla vehicles exemplifies the
incredible possibilities opened by the real-world adoption of artificial
intelligence and, at the same time, their huge implications from a security
point of view. However, while Tesla’s autopilot, alongside recently introduced
generative AIs like ChatGPT and DALL-E, represent some of the most notable
examples of consumer-ready AI that sparked the public discussion about their
trustworthiness and safety, the scientific literature yields a plethora of
other lesser-known examples that likewise call for a deeper investigation of
these fundamental requirements. Drug discovery and development [PIT18],
industrial cooling systems optimization [Won+22], brain-computer interfaces
[MN19], and automated cloud workload scaling [Qiu+23] are nothing but a few of
the numerous examples of applications where RL-powered technologies, in all
likelihood, will begin to be adopted more and more frequently in years to come
by both consumer markets and enterprise solutions.

Altogether, while it is undeniable that such applications could lead to huge
benefits from a myriad of perspectives, such gains will only be possible if we
are able to properly address the critical issues that currently limit the
trustworthiness of AI-powered solutions, the main being the explainability of
model outputs and their robustness to unforeseen circumstances, such as noisy
inputs or adversarial attacks. Moreover, in response to the rising
availability of AI-based products, laws and regulations regarding their use
and associated responsibility are starting to emerge as well, with relevant
corpora being under work in both European and American institutions, among
others. Thus, as regulations evolve and consolidate, the research on the
security of artificial intelligence will also have an increasing value from a
legal compliance point of view, further increasing its relevance and urgency.

Motivated by all the above considerations, with my thesis, I aim to provide
the first analysis of the security of RM-based reinforcement learning
techniques, with the hope of motivating further research in the field.
Starting from a theoretical analysis of the security implications arising from
the use of reward machines, I propose a novel class of attacks aimed at
hindering the performance of optimally trained RM-based agents: blinding
attacks. Then, after discussing a wide range of variations over their
underlying basic approach, I conclude by presenting an analysis of the results
obtained by the experimental evaluation of the proposed techniques over three
partially observable benchmark domains.

##  Chapter 2 Background

###  2.1 Artificial Intelligence

Artificial Intelligence (AI) is a vast field of computer science research that
aims at the development of intelligent agents. While proposing a proper,
formal definition of such a concept could lead to a breadth of interesting —
often philosophical — discussion relating to topics such as _intelligence_ ,
_agency_ , and _autonomy_ , this is beyond the scope of my thesis. Instead, I
will adopt a simpler, practical definition of AI, adapted from the one
provided by [RN10] in the preface of [RN10]:

> We define AI as the study of [artificial] agents that receive percepts from
> the environment and perform actions [to achieve a task].

This definition works well in the context of my work as it highlights all the
key concepts that will be fundamental in understanding subsequent topics while
also being sufficiently general to showcase to the reader the potential
applicability of AI to a myriad of scenarios, well beyond those that will be
analyzed in the remainder of my thesis.

However, since this degree of generality inevitably induces a large amount of
uncertainty as to the exact scope of the definition, the following section
clarifies the three foundational concepts introduced above: agents,
environments, and tasks.

####  2.1.1 Tasks, agents, and environments

Among the three, the concept of a task is the easiest to comprehend, as its
meaning does not differ from the one suggested by common sense: it simply
represents what the agent is required to do, be it a one-time objective or a
recurrent activity. As such, the definition of the task is usually the first
aspect that is fixed during the development of an AI system, as it strongly
influences both the agent design and the definition of the environment.
Another aspect that strongly relates to the task at hand is the performance
measure that is used to quantify how good — or bad — the agent is.

An agent is the final desired output of any AI development effort. Its design
is the primary object of study of the discipline and, in most practical
contexts of interest, the main technical challenge. When looking for an
adequate answer to the question of what an agent is, [RN10] again provide a
simple, elegant definition:

> An agent is anything that can be viewed as perceiving its environment
> through sensors and acting upon that environment through actuators.

While, at first glance, the above definition might not seem to provide a clear
answer, its merit lies in its generality. For an agent to be considered as
such, it only needs to be able to interact with its surrounding environment by
acquiring and emitting signals that are meaningful in the context of its task
of interest. Thus, this condition allows for the characterization of agents of
arbitrary complexity: under this definition, a simple text-suggestion system —
such as the ones available on most commercially available smartphone keyboards
— is no less of an agent than a complex humanoid-like robot capable of object
identification and fluent movement in the three-dimensional space. Indeed,
just like the former might be able to perceive its — purely software-in-nature
— environment by having access to the text typed so far and to act on it by
outputting its suggestion, the latter might be able to obtain information from
the physical world via a complex array of sensors and to manipulate it, for
instance, via mechanical arms and legs. From a high-level point of view, none
of the above examples is any less of an agent than the other, as both fully
comply with the above definition.

An environment is the context in which an agent operates to achieve its task.
Contrary to what the common sense interpretation of the word might suggest,
environments are not restricted to portions of the physical world: they can
also be purely virtual. For example, we could imagine a surveillance robot
whose task is to patrol the perimeter of a building during nighttime. In
addition to the sensors needed to sense its — physical — surroundings, the
robot might also be designed to receive a live stream of the security cameras
placed around the building, thus allowing it to sense its _virtual_
surroundings.

This last example allows us to highlight an essential aspect of the
relationship between tasks, agents, and environments: what is considered part
of the environment highly depends on the signals the agent needs to achieve
its mission and the ones available to him via its sensors.

####  2.1.2 Agent functions and programs

Mathematically, any agent’s behavior can be fully described through an agent
function:

$f:P^{*}\rightarrow A$ (2.1)

where $P$ is the set of all possible percepts the agent can receive from the
environment, $A$ is the set of agent actions, and $P^{*}$ is the set of all
possible percept sequences $(p_{0},p_{1},...)$, with $p_{i}\in P\ \forall
i\in\mathbb{N}$. However, while this representation represents a useful
conceptual base for the theoretical design of an agent, it does not help us in
the actual implementation of the agent, which necessarily needs to be embodied
by an agent program running on some physical computing infrastructure.

When considering an agent function, it is convenient to represent it as a
_table_ containing a row for each possible percept sequence and a column
containing the agent’s associated action. However, while conceptually
convenient, this representation is impossible to adopt in practice. Since, in
theory, there is not an a priori upper limit on the length of a percept
sequence, such a table would require an infinite amount of memory to be
stored. While this problem could be fixed by introducing a finite limit on the
length of the percept sequences we are willing to consider, we are immediately
faced with another one: even game environments, like chess, that can be
described by a small set of rules might be characterized by state spaces with
a cardinality that _vastly_ surpasses the number of atoms in the universe111In
the specific case of chess, we are faced with a number of unique possible
games in the order of $10^{1}20$. On the other side, the number of atoms in
the universe is currently estimated to be in the order of $10^{8}0$.. Thus,
when aiming to address even more complex tasks, any hope for a simple one-
fits-all tabular design for an agent program quickly vanishes.

In light of this, most of the research efforts that are put in the field of
artificial intelligence are directed to the development of smart solutions for
the design of agent programs, leading to a rich diversification in both
general and special purpose techniques and algorithms that allow us to
effectively and efficiently deal with complex environments and tasks. In
recent years, the field of neuro-symbolic AI has emerged as a new promising
paradigm relying on the use of both symbolic techniques, which are based on
the use of high-level, human-understandable languages for the representation
of the problem at hand, and neural-network-based ones, which instead rely on
immense networks of opaque, numerical parameters. Due to this peculiar

####  2.1.3 Characterization of task environments

Due to the vastness of the possible environments that might arise in AI
applications, it is helpful to define a few axes along which they can be
characterized, as different techniques might work best or even be applicable
only when faced with given kinds of environments.

The first distinction depends on whether the agent has access, via its
sensors, to the _complete_ state of the environment at each point in time.
When this is true, the environment is said to be fully observable. This
represents the simplest case in terms of required agent design: as every
percept contains all the relevant information the agent needs, it does not
need to keep track of the state of the world. On the other hand, when this
condition does not hold, the environment is said to be partially observable.
In particular, this latter case is very prominent in real-world environments,
where partial observability might arise due to imperfect or noisy sensors or
plain unavailability — for instance, due to resource constraints or actual
physical impossibility — of adequate sensors.

The second distinction arises between deterministic and stochastic
environments: in the former case, the next state of the environment is
entirely determined by the current state and the agent’s actions, while in the
latter, the state transitions are probabilistic. Unsurprisingly, stochastic
environments present additional challenges, as they introduce _uncertainty_ in
the agent’s trajectories through the environment state space, which, in most
cases, must be accounted for to achieve optimal behavior. Finally, it is
interesting to note how a deterministic environment might _appear_ to be
stochastic due to it being partially observable. If the agent has no access to
the information that would be required to determine the following environment
state, to its eyes, the state transitions would appear non-deterministic.

If we shift our focus from the actual environment transition dynamics to the
agent’s knowledge of them and the possible states, we can further distinguish
between known and unknown environments. In the first case, the agent knows all
the possible outcomes of his actions, while in the second, in layman’s terms,
he does not know what to expect. Note that this characterization is entirely
orthogonal to the distinction between fully and partially observable, where
the focus is on the availability of relevant information during the agent’s
course of action. A solitary card game is an excellent example of a partially
observable yet known environment. While the game’s rules are well-known by the
agent, the actual state of the deck of cards is unavailable during the game.
On the other side, using a computer program for the first time is a good proxy
example for a deterministic environment that is also unknown: every action of
the user has a well-defined, deterministic effect, but the user himself needs
to figure out what he can do, how can he do it, and so on. This last example
highlights one fundamental requirement most often posed by unknown
environments when trying to act optimally: the ability to _explore_ and
_learn_.

Regarding the temporal dependency between current and future actions,
environments can be divided into episodic and sequential ones. In episodic
environments, at every time step, the agent obtains a percept from the
environment and decides what to do only based on the information it contains,
as current actions have no impact on future decisions. Every sense-decide-act
iteration is self-contained and independent from future ones. A perfect
example of such environments can be found in object recognition tasks: the
agent is presented with a picture, outputs its predicted label, and goes on to
the next one. Conversely, sequential environments are characterized by long-
term consequences arising from present actions.

###  2.2 Reinforcement Learning

Reinforcement Learning (RL) is a sub-field of artificial intelligence that
deals with finding optimal strategies for solving sequential decision-making
tasks through agents that learn via _trial-and-error_. Taking direct
inspiration from the idea of operant conditioning — widely studied in the
field of _behavioral psychology_ — RL agents are trained by iteratively acting
in their environment under the guidance of a reward signal: after observing
the current state of the world, the agents choose the action to be taken and —
after executing it — receive feedback that quantifies the quality of their
course of action, given the circumstances. The agents then use this feedback
to tune their current policy, and the cycle repeats. When the agent’s behavior
leads to a desirable outcome, a positive reward encourages it to replicate
such or similar actions, whereas, in the opposite case, a negative reward aims
at driving the agent away from its current strategy. Regardless of their level
of sophistication, all RL algorithms share this same basic structure,
consisting of a series of _observation-action-reward_ loops.

This framework starkly contrasts with the _learn-by-example_ one adopted by
Supervised Learning (SL) techniques, which require the agents to access pre-
existing, labeled datasets as the knowledge source guiding the learning
process. While for some tasks, like video classification or time series
prediction, satisfying this requirement might be feasible, in others, it could
be practically impossible for several reasons. For example, let us consider
flying a helicopter in a straight line from point A to point B. The first
problem we would encounter if we decided to resort to SL techniques to train
such an agent is the number of possible states that need to be accounted for.
Even considering a minimal configuration of sensors consisting of three
accelerometers, one for each axis of the 3D space, three sensors for assessing
the current velocity of the helicopter’s rotors, and a simple relative
location sensor, we are immediately faced with a complex _continuous_ state
space that would need to be exhaustively represented in our training dataset
to ensure the reliable operation of our helicopter agent.

Even if we assumed the feasibility of collecting such a dataset, we face a
second problem: the need for _labeled_ data. Indeed, every state configuration
would need to be associated with the correct action — _i.e.,_ how much power
to direct to each rotor — that the agent should take in that situation.
Unfortunately, even the best pilots in the world would struggle if asked to
provide such information accurately, let alone have the time to review every
single data point in our training set. In light of these considerations, the
use of supervised learning for solving such a task appears doomed to
failure222In reality, there exists a sub-field of supervised learning that
allows for the solution of such problems by relying on _expert demonstrations_
, namely Imitation Learning. This, however — while extremely interesting — is
out of the scope of my thesis..

On the other hand, the reinforcement learning paradigm allows us to overcome
said limitations by eliminating the need for a labeled dataset. To solve such
a task, an RL agent would only require us to provide it with a reward function
that accurately captures the desirability, or lack thereof, of a given
scenario. Doing so eliminates the need for a precise specification of the
correct actions to be taken, and we leave our agent responsible for figuring
that out. Moreover, with this solution, we can now effectively rely on domain
experts to guide the learning process, for example, by informing us that, to
keep its trajectory stable, the agent should be rewarded for limiting the
amount of horizontal acceleration it is subject to. In light of this, the
reinforcement learning paradigm shows great promise in allowing us to tackle
such a complex task, and it has been used to solve it333See [Kim+03].. In
general, as long as we can come up with a sufficiently expressive reward
function, reinforcement learning is — at least in theory — a suitable solution
and, in many cases, might even be the only feasible approach to produce an
agent able to reach high-performance levels.

##### Limitations of the reinforcement learning approach

Despite the undeniable advantages of RL techniques, these do not come without
limitations. Firstly, while the reward function is fundamental in eliminating
the need for an explicit description of how an agent should behave, it also
bears a significant responsibility in determining the quality of the learning
process. The impact of an ill-designed reward function might range from
convergence to sub-optimal behavior — in the “best” case — to a complete lack
of progress in learning the task. Moreover, in some pathological — yet easily
encountered — cases, it could also cause the agent to learn gimmicky policies
that gain high rewards while achieving no progress for the actual task.

To exemplify, let us consider the toy scenario of an agent tasked with
reaching a door at the end of a corridor: the obvious choice would be to
reward the agent for reaching their destination. However, if the corridor were
sufficiently long, requiring the agent to take a large number of steps before
reaching its end, this would lead to a very sparse reward, a fairly common
problem encountered in reinforcement learning scenarios that could
significantly hinder the progress of the agent. To deal with this issue, we
could encourage the agent by rewarding it every time it progresses by, for
instance, 25% of the total length of the corridor. By doing so, the agent
would have access to some _partial reward_ that could guide it towards its
actual goal. This is the basic idea behind reward shaping, a technique that
will be further discussed in section 2.2.5. This solution, however, hides a
subtle problem: if improperly designed444Fortunately, [NHR99] provides us with
a general design that allows for the elimination of some of these pathological
cases, as discussed in section 2.2.5., the partial rewards might lead the
agent in learning a “smart” strategy to maximize its reward, consisting in
reaching the first quarter milestone, taking a step back, going back to the
milestone and so on ad infinitum. While, in such a simple environment, this
pathological scenario could be foreseen, more complex ones usually do not
allow for a simple apriori analysis and thus require extreme care in
developing and testing adequate reward functions.

Another limit in the applicability of RL techniques comes directly from one of
its foundational principles: the need for the agent to interact with its
environment. The reason why this might represent a limitation is twofold. On
the one hand, it requires us to be able to provide the agent with a copy of
its environment. In many software-based tasks, this might be trivial. However,
in most robotics applications, for instance, this requirement might pose a
significant obstacle: obtaining access to a copy of the physical agent at
training time might impose an impractical economic cost, exacerbated by the
risk of damages arising from agent errors, especially in the initial phases of
the training process, when the agent might not have yet reached safe levels of
proficiency. In such cases, to make training feasible, there might be the need
for emphcomputer-simulated environments, which themselves introduce a
significant development cost. Moreover, even if the simulation represents a
good proxy for the actual environment, there is usually no guarantee for the
learned policy to transfer to the physical world seamlessly: agents acting
optimally in the simulated environment might be overwhelmed by the intrinsic
difficulties posed by the real world, for instance, in the form of sensor
noise and unpredictable environment dynamics.

On the other hand, regardless of the nature of the agent’s environment, the
need for iterative interaction also represents a sensible cost in
computational effort. Even apparently modest environments might require
millions of environmental steps to provide the agent with a solid
understanding of its laws and many more to fine-tune its behavior to reach
optimality. Thus, in this regard, access to high-throughput environments — in
terms of steps-per-second — is a fundamental requirement for assuring an
effective training process and further highlights the difficulties related to
using simulated environments, which often need to be based on accurate physics
engines.

Finally, one further limit of RL techniques — also shared by most supervised
learning approaches — is related to the generally low generalization potential
of the learned policies to new scenarios: even though the agent might have
reached optimal performance in its training environment, subtle changes in
environment parameters or structure might be sufficient to cause a
catastrophic drop in its ability to solve the task. While, in theory, this
could be solved by exposing the agent to a broader array of environmental
conditions, the feasibility of this approach is often limited by its
associated computational costs and, above all, by the impossibility of
determining beforehand which changes in the environment will lead to such
problems.

####  2.2.1 Markov Decision Processes

The tasks of interest in reinforcement learning are usually described as
Markov Decision Processes (MDPs).

######  Definition 1.

A _Markov Decision Process_ is a tuple $\mathcal{M}=(S,F,A,r,p,\gamma)$,
where:

  * •

S is the finite set of _environment states_ ;

  * •

$F\subset S$ is the subset of _final – or goal – states_ ;

  * •

A is the finite set of available _agent actions_ ;

  * •

$r:S\times A\times S\rightarrow\mathbb{R}$ is a _reward function_ mapping from
the current state of the environment, the action taken by the agent in such
state, and the resulting state of the environment to a real-valued reward;

  * •

$p(s_{t+1}|s_{t},a_{t})$ is the — markovian — _environment transition model_ ,
describing the probability of reaching environment state $s_{t+1}\in S$ after
executing action $a_{t}\in A$ while in state $s_{t}\in S$;

  * •

$\gamma\in(0,1]$ is the _discount factor_ weighting the preference for
imminent rewards over future ones.

The presence of the “Markov” connotation is not a simple matter of
terminological conventions. On the contrary, it highlights a fundamental
property that the environment at hand must show: the current state of the
environment must provide all the information needed to determine the next
state of the environment, given the action taken by the agent. In other words,
the knowledge of the environment _history_ does not grant any benefit in terms
of computing the environment transition model. Formally, $\forall
s_{0},...,s_{t},s_{t+1}\in S,\ a_{0},...a_{t}\in A$ this can be expressed by
the following condition:

$p(s_{t+1}|s_{t},a_{t})=p(s^{\prime}|s_{0},a_{0},...,s_{t},a_{t})$ (2.2)

This motivates the specific formulation provided for defining the environment
transition model.

By adopting the above definition for an MDP, I implicitly restricted myself to
a specific class of tasks characterized by fully-observable, stochastic
environments, as showcased, respectively, by the absence of a distinction
between _environment states_ and _agent percepts_ , and by the probabilistic
definition of the environment transition model. Indeed, we are assuming that:

  1. 1.

on each timestep $t$, the agent percept coincides with the whole environment
state $s_{t}$. In other words, the agent has, at any given moment, complete
access to the true state of the environment;

  2. 2.

the outcome of an action $a_{t}$ taken while in state $s_{t}$ is non-
deterministic;

While true in many practical RL applications, the former assumption is
currently motivated by the ease of exposition. It will be relaxed during the
dissertation to accurately describe the environments that were analyzed by my
work. The latter condition, instead, will remain unvaried as it plays an
important role in justifying the need for reinforcement learning techniques,
both in my work and in many other applications of RL. Moreover, its presence
determines the need for a specific definition for the solution of an MDP.

In fact, in the case of a fully deterministic environment, a solution would be
represented by _any_ sequence of actions leading from the initial state
$s_{0}$ to a goal state $s_{t}\in F$. Moreover, informally, an optimal
solution would be any solution maximizing the reward cumulated during the
agent’s trajectory in the environment. While a fascinating topic, the solution
of such problems is often better handled with techniques different from RL,
usually in the form of _seach-based algorithms_ , that do not share the same
limitations in the previous section.

Instead, in the context of MDPs, a solution, to be complete, needs to specify
the action to be taken in _every_ state since the stochasticity of the
environment dynamics could, in theory, lead the agent to any state. Thus,
instead of looking for a sequence of actions, we look for solutions in the
form of policies.

######  Definition 2.

Given an MDP $\mathcal{M}=(S,F,A,r,p,\gamma)$, a _policy_ is any function:

$\pi:S\rightarrow A$

mapping from any environment state $s\in S$ to the action $a\in A$ to be taken
by the agent while in such state.

Having defined what represents a valid solution for an MDP, there is now the
need for a method for _comparing_ the quality of two different solutions to
characterize optimal policies, the ultimate objective when solving an MDP. To
do so, the utility of an environment trajectory must first be defined.

######  Definition 3.

Given an MDP $\mathcal{M}=(S,F,A,r,p,\gamma)$ and an environment trajectory
$\tau=[s_{0},a_{0},...,s_{t-1},a_{t-1},s_{t}]$ with $s_{i}\in S,\ a_{i}\in A\
\forall i=0,...,t$ its _true utility_ is defined as:

$U(\tau)=\sum_{k=0}^{t-1}\gamma^{k}r(s_{k},a_{k},s_{k+1})$

The above equation also clarifies the purpose of the discount factor
introduced by the definition of MDPs: when $\gamma=1$, future rewards are
weighted equally to imminent ones. At the same time, lower values
progressively reduce their influence in the computation of a trajectory’s
utility.

Finally, we can then assess the quality of any given policy by quantifying the
expected utility obtained by an agent executing it. Assuming the stationarity
of the environment transition model, the probability distribution over
environment trajectories is entirely determined by the initial environmental
state $s_{0}$. For the agent’s policy $\pi(s)$, we can simplify our notation
by directly talking about the expected utility of a _single state under a
given policy_.

######  Definition 4.

Given an MDP $\mathcal{M}=(S,F,A,r,p,\gamma)$ and a policy $\pi$, we define
the _expected utility_ of any state $s\in S$ as:

$U^{\pi}(s)=\mathbb{E}\left[\
\sum_{k=0}^{t-1}\gamma^{k}r(s_{k},a_{k},s_{k+1})\ \right]$

where $s_{0}=s$, $s_{i+1}\sim p(\cdot|s_{i},a_{i}),\ a_{i}=\pi(s_{i})\ \forall
i$. The expectation is taken with respect to the probability distribution over
environment trajectories induced by $s$ and $\pi$.

######  Definition 5.

Given an MDP $\mathcal{M}=(S,F,A,r,p,\gamma)$ and an initial environment state
$s$, we define _optimal policy_ any policy:

$\pi^{*}_{s}=\operatorname*{argmax}_{\pi}U^{\pi}(s)$

Since, by definition, an optimal policy maximizes the expected utility
cumulated by the agent during its execution, it follows that, for any state
$s\in S$, its true utility must be equal to $U^{\pi^{*}_{s}}(s)$. Moreover,
since any two _different_ optimal policies must, again by definition, lead to
the same set of expected state utilities, we will denote the true utility of
any state $s\in S$ simply as $U(s)$.

The existence of the true utility function $U(s)$ allows us to derive a
conceptually simple criterion to be followed by an agent to act optimally:
choosing the action that maximizes the expected utility of the subsequent
state:

$\pi^{*}(s)=\operatorname*{argmax}_{a\in
A}\sum_{s^{\prime}}p(s^{\prime}|s,a)U(s^{\prime})$ (2.3)

This Maximum Expected Utility (MEU) formulation, coupled with the one exposed
by definition 4, highlights the direct relationship that exists between the
true utility of any state and its neighbors: assuming the agent is acting
optimally, we can express the true utility of any state $s\in S$ as:

$U(s)=r(s)+\gamma\max_{a\in A}\sum_{s^{\prime}}p(s^{\prime}|s,a)U(s^{\prime})$
(2.4)

where, for ease of notation, we also assumed the reward obtained by the agent
to only depend on the current state of the environment. Equation 2.4 is
commonly known as the Bellman equation, after Richard Bellman, the
mathematician who first described it in 1957. For a state space $S$ such that
$|S|=n$, there are exactly $n$ Bellman equations, each describing the utility
of a state as the sum of its associated reward and the maximum — discounted —
expected utility of any of its neighbors. Moreover, the utilities of the
states are their _unique solutions_. As such, we would like to solve the
Bellman equations since doing so would grant us the _true utility_ of each
environment state and, in turn, the ability to determine an optimal MEU policy
via equation 2.3. Unfortunately, while ideal in theory, the practical
application of this approach becomes rapidly infeasible as the size of the
state increases, both due to the linear dependency of the number of equations
to $|S|$ and the difficulties posed in their solution by their non-linear
nature.

Nonetheless, the discussion of said approach is relevant as it forms the
conceptual basis from which many modern reinforcement learning algorithms are
built. Two basic approaches can be followed to exploit the Bellman equations:
value iteration and policy iteration.

##### Value iteration

Algorithm 1 presents the pseudocode for value iteration. As showcased by its
simple, iterative structure, this approach consists of a progressive
refinement in the estimates for the state utilities. It progresses from
arbitrarily chosen — zero, in our case — values until a fixed point is
reached. The core of this method lies in the _Bellman update_ , a direct
application of the Bellman equation to the current utility estimates. With a
series of local updates, the information relating to each state’s utility is
propagated from the right-hand side of the equation to the current estimates,
progressively reducing their associated error. It can be shown that, after a
sufficient number of iterations, value iteration is _guaranteed_ to converge
to the unique set of solutions of the Bellman equations, _i.e.,_ the true
utility function.

One interesting property demonstrated in practice by value iteration is its
ability to lead to optimal MEU policies long before $U_{i}$ has converged to
the true utilities. Intuitively, as long as the estimates are sufficiently
accurate to distinguish between _good_ and _bad_ states, there is no need for
extreme precision in their values.

Algorithm 1 Value iteration algorithm for producing an arbitrarily accurate
estimate of state utilities given an MDP $\mathcal{M}$ and a tolerance
parameter $\epsilon$.

function Value-Iteration($\mathcal{M},\epsilon$)

local variables:

U, U’: vectors of utility estimates, zero-initialized

$\delta$: the maximum variation in utility estimates during an iteration

$\triangleright$ Iterative estimation of utility values

repeat

$U\leftarrow U^{\prime},\ \delta\leftarrow 0$

for all $s\in S$ do

$U^{\prime}[s]\leftarrow
r(s)+\gamma\max\limits_{a}\sum\limits_{s^{\prime}}p(s^{\prime}|s,a)U[s^{\prime}]$
$\triangleright$ Bellman update

if $|U^{\prime}[s]-U[s]|>\delta$ then

$\delta\leftarrow|U^{\prime}[s]-U[s]|$

until $\delta<\epsilon(1-\gamma)/\gamma$

return U

##### Policy iteration

The value iteration algorithm leads to optimal policies _indirectly_ by first
computing the true state utilities and then adopting the MEU approach to
compute the actual policy. On the other hand, policy iteration reverses this
approach: first, the current policy is used to estimate each state’s utility,
then these estimates are used to improve the policy — once again — according
to the application of the MEU framework to each state’s successors.

Algorithm 2 provides the pseudocode for the policy iteration algorithm. When
the current policy $\pi_{t}$ yields no change in the utilities, a fixed point
in the Bellman update has been reached and, thus, $\pi_{t}$ must be optimal.
Moreover, the termination of the algorithm is guaranteed since the policy
space for an MDP with a finite state space is finite as well, and every
iteration necessarily yields an improved policy.

The Policy-Evaluation subroutine has been intentionally left unspecified in
the pseudocode, as there are multiple possible ways of implementing it. One
possibility is to apply the Bellman equation directly. However, since the
current policy fixes the action to be taken in each state, we can adopt the
following _simplified_ version of the equation:

$U_{i}(s)=r(s)+\gamma\sum_{s^{\prime}}p(s^{\prime}|s,\pi_{i}(s))U_{i}(s^{\prime})$
(2.5)

which is significantly easier to solve due to the absence of nonlinearity
arising from the $\max$ operator. Using standard linear algebra methods, given
a state space $S$ such that $|S|=n$, the associated system of $n$ equations
can be _exactly_ solved with time $\mathcal{O}(n^{3})$. Unfortunately, as n
grows, the cubic time complexity quickly becomes prohibitive. Luckily, just
like for value iteration, computing the exact utilities arising from the
current policy is unnecessary. By once again applying the simplification above
— this time to the Bellman update — we can obtain an estimated policy
evaluation method that is feasible even for large state spaces555In this
context, by _large_ state spaces we are nonetheless referring to state spaces
small enough to make the application of policy iteration feasible.:

$U_{i+1}=r(s)+\gamma\sum_{s^{\prime}}p(s^{\prime}|s,\pi_{i}{s})U_{i}(s)$ (2.6)

With this approach, the utility estimates can be efficiently obtained by
repeatedly applying this update rule $k$ times, with $k$ being a parameter
that can be tuned to find the right balance between computational cost and
estimation accuracy.

Algorithm 2 Policy iteration algorithm for producing an optimal policy for an
MDP $\mathcal{M}$.

function Policy-Iteration($\mathcal{M}$)

local variables:

U: vector of utility estimates, zero-initialized

$\pi$: state-indexed policy vector, randomly initialized

$\triangleright$ Iterative refinement of current policy

repeat

$U\leftarrow$ Policy-Evaluation($\pi,U,\mathcal{M}$)

$unchanged?\leftarrow true$

for all $s\in S$ do

$improvable?\leftarrow\max\limits_{a}\sum\limits_{s^{\prime}}p(s^{\prime}|s,a)U[s^{\prime}]>\sum\limits_{s^{\prime}}p(s^{\prime}|s,\pi[s])U[s^{\prime}]$

if $improvable?$ then

$\pi[s]\leftarrow\operatorname*{argmax}\limits_{a}\sum\limits_{s^{\prime}}p(s^{\prime}|s,a)U[s^{\prime}]$
$\triangleright$ Policy improvement

$unchanged?\leftarrow false$

until $unchanged?$

return $\pi$

##### Solving MDPs with reinforcement learning

In the previous sections, I assumed the MDP of interest to be completely
_known_ to the agent: all the presented equations and algorithms rely on the
knowledge of the state space $S$, action space $A$, reward function $r(s)$,
and environment transition model $p(s^{\prime}|s,a)$. When this — quite strong
— assumption holds true, there might be a need to consider reinforcement
learning techniques for solving the MDP. However, many practical scenarios do
not allow for such an assumption to be made and, instead, are characterized by
either a lack of knowledge regarding the environment transition model, reward
function, or both. Moreover, there might even be cases where the state and
action spaces are partially or wholly unknown to the agent.

When the MDP is unknown, the agent initially has no idea of what he can do,
which states it can reach, what the outcome of its actions is, or which
achievements are desirable for solving the task. Thus, in such a situation,
the only possibility for it to learn anything is to explore the environment
and progressively figure out the inner workings of its surroundings while
trying to maximize the rewards observed during its trials. Therefore, when
faced with such a scenario, reinforcement learning techniques are not only
effective but also _necessary_ for successfully training an agent.

##### Partially observable MDPs

The last assumption about the nature of an environment modeled by an MDP that
we need to relax — before describing the tasks that I analyzed during my work
properly — is that of _full observability_. However, the previously provided
definition of a Markov Decision Process is insufficiently expressive to do so.
Therefore, this section introduces a new class of MDPs: Partially Observable
Markov Decision Processes (POMDPs).

######  Definition 6.

A _Partially Observable Markov Decision Process_ is a tuple
$\mathcal{P}_{\mathcal{O}}=(S,F,A,O,r,p,\omega,\gamma)$, where:

  * •

$S,F,A,r,p$, and $\gamma$ are defined in the same way as for regular MDPs;

  * •

$O$ is a finite set of _observations_ that the agent can obtain from the
environment;

  * •

$\omega(s|o)$ is the _environment observation model_ , describing the
probability of the environment being in state $s\in S$ when the agent observes
$o\in O$.

In the POMDP setting, the true environment state at any point in time is
unavailable to the agent, which can only obtain _observations_ that might,
depending on the environment observation model, partially reveal the
information the agent needs for progressing in the task at hand. In the best
case, given the latest observation $o_{t}\in O$ obtained by the agent, there
might exist some state $\bar{s}\in S$ for which $\omega(\bar{s}|o_{t})\simeq
1$, thus allowing the agent to infer the underlying environment state
reliably. Unfortunately, such a condition is neither guaranteed nor common in
practice. On the other hand, in the worst case, the agent could obtain an
observation $\bar{o}\in O$ such that $\omega(s|\bar{o})=\frac{1}{|S|}\ \forall
s\in S$, thus effectively providing no information at all regarding the state
of the environment. While, in practice, many tasks may not be characterized by
an abundance of this last pathological case, the agent could have no knowledge
of the environment observation model. This condition substantially increases
the complexity already introduced by the environment’s partial observability.

It is important to note that, even in the case of partial observability, the
Markov property is still required by the above definition of the environment
transition model: the knowledge of the true state of the environment is
nonetheless sufficient for fully determining the probability distribution
governing the state transition dynamics. However, as the agent has no access
to the actual state of the world, this may _appear_ to him as being non-
Markovian. For instance, there might be two _distinct_ states $s_{1},s_{2}\in
S$, leading, after the agent’s action, to the same observation $o\in O$ but
different transition probabilities.

##### Agent policies under partial observability

In the case of partial observability, the previously provided definition for
an agent policy is intrinsically inadequate, as it relies on direct knowledge
of the true environmental state. To adapt it to the POMDP setting, it might be
tempting to resort to the following naive extension:

$\pi:O\rightarrow A$ (2.7)

However, while such a definition could show _some_ level of effectiveness in
practice, from a theoretical standpoint, it is inherently inadequate due to
POMDPs being non-Markovian concerning the environment observation space.
Intuitively, this formulation is equivalent to requiring the agent to act
based _only_ on what he currently sees. To consolidate this intuition, I will
resort to the example of a blackjack-playing agent, as such card games are a
perfect example of POMDPs. The current order of the cards in the deck, _i.e.,_
the state of the environment, is fixed and fully determines the order in which
they will be extracted, _i.e.,_ the environment state transitions. On the
other side, the drawn cards represent the observations available to the agent.
Resorting to the formulation proposed by equation 2.7 would be equivalent to
requiring the agent always to do the same thing when faced with the same
cards, even though previous extractions might have removed cards from the
deck, thus changing the overall probability distribution of future
extractions666For the sake of simplicity, I am knowingly ignoring the fact
that, in real casino blackjack, the deck of cards is changed between games to
avoid the possibility for card counting strategies..

To solve this problem, we need to consider policies in the form of:

$\pi:O^{*}\rightarrow A$ (2.8)

which considers the whole history of observations up to the present moment. By
doing so, the agent can effectively exploit all the information it can gather
_from the environment_ to decide its course of action. Unfortunately, this
formulation can again not lead to optimal behavior in the general case. While
keeping track of past observations is undoubtedly an improvement, there is a
source of influence on the environment state transitions that are being
unaccounted for: the agent’s actions. Thus, this observation leads to the
following formulation:

$\pi:(O\times A)^{*}\rightarrow A$ (2.9)

which effectively allows the agent to exploit _all_ the information it has to
try and act optimally under an MEU interpretation. This is possible as, by
keeping track of the history of observations and actions, the agent can make
its best possible guess for the true underlying state of the environment.
Formally, this last concept of ”agent’s guess” is usually presented as a
belief state:

######  Definition 7.

Given a POMDP $\mathcal{P}_{\mathcal{O}}=(S,F,A,O,r,p,\omega,\gamma)$, a
_belief state_ is a probability distribution over the set of true environment
states $S$:

$b:S\rightarrow[0,1]\qquad\text{s.t. }\sum_{s\in S}b(s)=1$

that represents the probability of each state being the current environment
state.

On the first timestep, the agent’s belief state solely depends on the
environment observation model and the first observation received from the
environment:

$b_{0}(s)=\omega(s|o)\qquad\forall s\in S$

Then, at any timestep $t\geq 1$, the new belief state also depends on the
environment transition model and the agent’s action:

$b_{t+1}(s^{\prime})=\alpha\omega(s|o)\sum_{s\in
S}p(s^{\prime}|s,a)b(s)\qquad\forall s,s^{\prime}\in S,\ a\in A$

It can be shown that, in the context of POMDPs, the optimal action at each
point in time depends only on the agent’s current belief state. In light of
this, we can provide one last formulation for a POMDP policy:

$\pi:\mathcal{B}_{S}\rightarrow A$ (2.10)

where $\mathcal{B}_{S}$ represents the set of all possible belief states over
a set $S$ of environment states. However, since partially observable
reinforcement learning tasks are usually characterized by unknown
environments, this last formulation is rarely explicitly used in practice and
is mainly adopted for the theoretical analysis of POMDPs. In fact, explicitly
computing belief states is impossible without knowledge regarding
$p(s^{\prime}|s,a)$ and $\omega(s|o)$. Therefore, the policy formulation most
commonly adopted during the design of reinforcement learning algorithms is the
one presented in equation 2.9.

To conclude this section, it is important to note that the study of POMDPs is
an important research topic in the field of reinforcement learning, as many
real-world tasks might fall under this category for a variety of reasons, such
as the unavailability of sufficiently exhaustive sensor arrays, perceptual
noise, or intrinsic uncertainty of available information. In light of this,
there exists an active research community investigating the algorithms and
techniques required to deal with the unique challenges posed by such
environments effectively. Among them, one approach that stood out in recent
years in the neurosymbolic RL literature is reward machine-based reinforcement
learning. Due to its central role in my work, the entirety of chapter 3 is
dedicated to thoroughly describing such a framework.

####  2.2.2 Classes of RL techniques

Reinforcement learning algorithms are usually classified based on three main
features:

  1. 1.

the object of focus of the learning process;

  2. 2.

the reliance on an explicit model for predicting the evolution of the
environment;

  3. 3.

the source of the experiences the agent uses to derive the optimal policy.

Starting from their object of focus, RL techniques can either be value-based
of policy-based, depending on whether they follow an overall approach that is
comparable with the value or policy iteration algorithms presented in section
2.2.1: in the former case, the algorithms aim at learning utility estimates,
which are then used to derive the optimal policy. On the other hand, policy-
based algorithms directly tweak their current policy based on its observed
quality: the learning process continues as long as the performance of the
policy improves, and then it stops. As this approach can be interpreted as a
search in the space of policies, another connotation commonly used to refer to
such techniques is, unsurprisingly, that of _policy-search_ methods. Usually,
the policy space that is explored is induced by a specific parametrization in
the policy representation.

Then, depending on whether the agent relies on the environment transition
model to learn its policy or each state’s utility, RL algorithms can be
classified as either model-based or model-free. In the case of model-based
techniques, the model for $p(s^{\prime}|s,a)$ can either be known a priori,
for instance, in game-playing settings, or progressively learned by the agent.
In light of this, both value iteration and policy iteration are model-based
techniques. On the other side, model-free techniques do not rely on any kind
of prediction of the environment’s evolution and rely solely on the experience
obtained via direct exploration of the environment. This, in practice,
provides model-free methods with a few advantages over model-based ones: on
the one hand, they apply to a broader range of problems; on the other hand,
they are usually computationally cheaper in terms of time and space
complexity. At the same time, model-free methods come with some disadvantages
when compared with model-based ones: they are usually characterized by a lower
_sample efficiency_ , meaning they need a larger number of trials to progress
in the learning process, and, depending on the exact techniques at hand, they
might present the risk of relying on biased samples of agent experience.

Finally, a third distinction can be made between _on-policy_ and _off-policy_
techniques. To understand the difference, a distinction must be introduced
between the target policy and the behavior policy: the latter is the policy
the agents use for deciding which actions need to be taken during learning,
while the former represents the current agent’s estimate of the optimal policy
it aims to learn. When the target and behavior policy are distinct from each
other, the algorithm is off-policy; on the other side, when the agent acts to
improve its current policy, the two policies are, in fact, the same, and the
technique is said to be on-policy. Intuitively, an off-policy agent observes
samples of behavior and uses them to determine how one should ideally act. In
contrast, an on-policy agent acts and tries to understand how it could improve
its strategy.

####  2.2.3 Tabular Q-learning

One commonly used and widely studied reinforcement learning algorithm is
Q-learning. The name of this technique derives from its use of a Q-function,
which gives the value of taking an action in a given environmental state:

######  Definition 8.

Let $S,A$ be the sets of environment states and agents actions of an arbitrary
MDP. A _Q-function_ is any function:

$Q:S\times A\rightarrow\mathbb{R}$

such that:

$U(s)=\max_{a}Q(s,a)\quad\forall s\in S,\ a\in A$

where $U(s)$ is the true utility of state $s$, as for equation 2.4.

Using a Q-function is not a simple change in the utility’s adopted
representation. Indeed, it shows a fundamental property: an agent learning a
Q-function does not need any model $p(s^{\prime}|s,a)$ for either learning or
selecting the best action. In light of this, Q-learning is a _model-free_
method. Moreover, it is a _value-based_ method following the same conceptual
structure of value-iteration: starting from initially arbitrary values, the
agent keeps an estimate for the Q-value of each state-action pair, then
chooses an action based on the MEU principle:

$\pi(s)=\operatorname*{argmax}_{a}Q(s,a)$

Then, after taking action $\pi(s)$, the agent uses the obtained reward to
update its estimates of Q-values. The cycle is repeated until convergence to
the true Q-values and, consequently, to the optimal policy. Indeed, Q-learning
is guaranteed to converge to the optimal Q-values in the limit of visiting
each state-action pair infinitely often [WD92].

While the Bellman equation for utilities can be readily adapted to the use of
a Q-function to provide both a condition that must hold for optimal Q-values
and a possible update rule:

$Q(s,a)=r(s)+\gamma\sum_{s^{\prime}}p(s^{\prime}|s,a)\max_{a^{\prime}}Q(s^{\prime},a^{\prime})$

The Q-learning algorithm does not directly use this equation to learn the
correct Q-values, as it does require knowledge of the environment transition
model. Instead, the update rule used by the method is given by:

$Q(s,a)\leftarrow
Q(s,a)+\alpha(r(s)+\gamma\max_{a^{\prime}}Q(s^{\prime},a^{\prime})-Q(s,a)$
(2.11)

where $\alpha\in[0,1]$ is a hyper-parameter controlling the magnitude of the
updates, usually referred to as the _learning rate_. This update rule is
applied every time an action $a$ is executed in state $s$, leading to state
$s^{\prime}$.

Moreover, notice that Q-learning is an _off-policy_ method, as the Q-value
updates do not depend on the policy used to choose the action taken. Thus, in
principle, a Q-learning agent can use any behavioral policy to generate the
experiences used to update the Q-value estimates and, thus, the current best-
known policy. Indeed, in light of the condition for the convergence of
Q-learning, most implementations resort to exploratory policies that allow the
agent to explore the state-action space thoroughly, as an insufficient number
of experiences relating to even one critical, state-action pair might be
sufficient for Q-learning not being able to converge to the optimal policy. At
the same time, however, resorting to poor policies might lead the agent not to
visit relevant sequences of states and actions, thus hindering the time
required for convergence. Therefore, an agent must adequately balance the need
for exploration with the benefits associated with the exploitation of its
current knowledge regarding the best possible course of action.

One standard solution to this problem is using an $\epsilon$-greedy
exploration strategy. At each time step, the agent chooses a random action
with probability $\epsilon\in[0,1]$ or the action suggested by its current
Q-values otherwise. In many practical cases, doing so allows for an adequate
balance between exploiting the current best-known policy and exploring the
environment, given the proper tuning of the $\epsilon$ parameter. In
conclusion, as a concise summary of all the exposed concepts, algorithm 3
provides the pseudo-code for the core of a Q-learning agent training process
under an $\epsilon$-greedy exploration strategy.

Algorithm 3 Pseudocode for one step of a Q-learning agent’s learning process,
using an $\epsilon$-greedy exploration strategy, given the current state
$s^{\prime}$ and reward $r^{\prime}$

function Q-Learning-Agent($s^{\prime},r^{\prime}$)

static variables:

$Q[s,a]$: table of Q-value estimates, zero-initialized;

$s,a,r$: the previous state, action, and reward, null-initialized

if Terminal?($\mathcal{M},s$) then

$Q[s,null]\leftarrow r^{\prime}$

if $s\neq null$ then $\triangleright$ Update Q-value estimates

$Q[s,a]\leftarrow
Q[s,a]+\alpha(r+\gamma\max\limits_{a^{\prime}}Q[s^{\prime},a^{\prime}]-Q[s,a])$

$explore?\ \leftarrow\ $ Random($0,1$)

if $explore?<\epsilon$ then $\triangleright$ $\epsilon$-greedy exploration

$action\leftarrow$ Random-Action()

else

$action\leftarrow\operatorname*{argmax}\limits_{a^{\prime}}Q[s^{\prime},a^{\prime}]$

$\triangleright$ Update previous state, action, and reward

$s,a,r\leftarrow s^{\prime},action,r^{\prime}$ return $action$

####  2.2.4 Deep Q-learning

Despite its theoretical convergence guarantee and the practical advantages of
its off-policy, model-free nature, Q-learning has one major drawback that
strongly limits its applicability in practical scenarios. As the state-action
space grows, it rapidly becomes impractical due to its lack of generalization
potential. Since the Q-values are estimated separately for each state-action
sequence, training an agent to learn the optimal policy for every possible
scenario would require an enormous amount of computational resources, both in
terms of time, to visit each sequence multiple times, and space, to store the
Q-value estimates of each state-action pair, making the training process
completely unfeasible for sufficiently large state-action spaces.

However, since the Q-learning approach remains theoretically valid regardless
of the Q-function’s representation, the solution adopted in practice consists
of substituting the tabular design in favor of some parametrized
representation $Q_{(}s,a;\theta)$. In the case of simple Q-functions, this
might be possible with some linear function approximators; however, when
facing complex environments, a more suitable solution is to use non-linear
deep neural network models due to their unique properties as generalized
function approximators. When used to approximate a Q-function, such models are
usually referred to as deep Q-networks (DQN), and the resulting algorithm is
called deep Q-learning.

As for any neural network model, a DQN can be trained by iteratively adjusting
its parameters in such a way that minimizes the value of a _loss function_
quantifying the distance between the current network’s outputs and the correct
values — a.k.a. the _targets_ — of the function being approximated. This can
be done thanks to the backpropagation algorithm, which uses gradient descent
to compute the parameter updates that lead to the minimization of the loss
function. In the specific case of Q-learning, the DQN can be trained by
minimizing:

$L_{i}(\theta_{i})=\operatorname*{\mathbb{E}}_{s,a\sim\rho(\cdot)}\left[(y_{i}-Q(s,a;\theta_{i}))^{2}\right]$
(2.12)

for iteration $i$, where $y_{i}$ are the target Q-values and $\rho(s,a)$ is
the distribution governing the probability of encountering the state-action
pair $(s,a)$. As this distribution depends on the agent’s behavior while
collecting its experiences, it is usually referred to as the _behavior
distribution_. However, if the targets $y_{i}$, _i.e.,_ the real Q-values,
were known, there would be no point in going through the process of training a
DQN: instead, they too need to be estimated, and this is done by resorting to
the MEU approach on the _previous_ Q-value estimates:

$y_{i}=\operatorname*{\mathbb{E}}_{s^{\prime}\sim
p(\cdot)}\left[r+\gamma\max_{a^{\prime}}Q(s^{\prime},a^{\prime};\theta_{i-1})\right]$
(2.13)

When the parameter updates are carried out for every agent step, and the full
expectations are replaced with single samples from the behavior and
environment model distributions — as motivated by the _stochastic_ variant of
the gradient descent algorithm — the learning process is analogous to the one
from standard tabular Q-learning, leading to a model-free, off-policy
technique.

Unfortunately, naively adapting Q-learning to the use of DQNs leads, in most
cases, to abysmal performance or even the Q-network diverging777 _i.e.,_
causing a steady increase in the value of the loss function as training
progresses., as the experience samples collected by the agent violate the
_i.i.e._ 888 _i.e.,_ independent and identically distributed assumption that
neural network training algorithms rely on. Consecutive samples of experience
are usually highly correlated as environments mostly evolve sequentially.

An effective solution for this problem was introduced by [Mni+13], in the form
of an experience replay mechanism: instead of using each experience sample
$e_{t}=(s_{t},a_{t},r_{t},s_{t+1}$ immediately, the agent stores them in a set
$\mathcal{D}$, the replay memory. Then, after collecting a given number of
samples, the Q-learning update is applied using a batch of experiences
randomly drawn from the replay memory. This approach presents two critical
advantages over standard Q-learning. Firstly, it allows for improved data
efficiency, thanks to each experience sample being used in many updates. Then,
thanks to the random sampling of experiences from the replay memory, the
_i.i.e._ assumption is recovered, thus significantly reducing the risk of
oscillations or, in the worst case, the divergence of the training process. In
light of this, experience replay proved to be a fundamental requirement for
the practical use of DQNs, leading to an enormous increase in their
applicability to many previously infeasible tasks. To summarise, algorithm 4
presents the pseudocode for deep Q-learning with experience replay.

Algorithm 4 Pseudocode for the Deep Q-learning with Experience Replay
algorithm for a given MDP $\mathcal{M}$, running over $M$ episodes, using
replay memory size $N$, batch size $n$ and update frequency $k$.

function DQN-ER($\mathcal{M},M,N,n,k$)

local variables:

$\mathcal{D}$: FIFO queue of $N$ agent experiences, initially empty.

$Q(s,a;\theta)$: Q-network with weight vector $\theta$, randomly initialized.

for $episode=1,...,M$ do

$t\leftarrow 1$

$s_{1}\leftarrow$ Initial-Environment-State($\mathcal{M}$)

repeat

$a_{t}\leftarrow\max\limits_{a}Q(s_{t},a;\theta)$

$s_{t+1},r_{t}\leftarrow$ Execute-Action($\mathcal{M},a_{t}$)

Push($\mathcal{D},(s_{t},a_{t},r_{t},s_{t+1})$)

if $t\ mod\ k=0$ then $\triangleright$ Update weights $\theta$

$batch\leftarrow$ Sample-Experiences($\mathcal{D},n$)

for $i=1,...,n$ do

$s_{j},a_{j},r_{j},s_{j+1}\leftarrow batch[i]$

$y_{i}=\begin{cases}r_{j}\quad&\text{if {Is-Terminal?}($s_{j+1}$)}\\\
r_{j}+\gamma\max_{a^{\prime}}Q(s_{j+1},a^{\prime};\theta)\quad&\text{otherwise}\end{cases}$

$\triangleright$ Loss function as in equation 2.12

$\theta\leftarrow$ Gradient-Descent($y_{1},...,y_{n}$)

$t\leftarrow t+1$

until Is-Terminal?($\mathcal{M},s_{t+1}$) return $Q$

####  2.2.5 Reward Shaping

As previously anticipated, one common issue encountered in reinforcement
learning is the sparseness of the reward signal. In many environments, the
agent might be required to take many steps before receiving a reward $r\neq
0$. This presents a problem as it leaves the agent without feedback on its
actions for long and, consequently, without information to update its
estimates for the encountered states’ utility. In the worst case, this
phenomenon might severely hinder the agent’s ability to find the optimal
policy; for instance, in the unfortunate case the latter involves a
significantly larger number of zero-reward steps — before finally reaching a
highly rewarding terminal state — than a sub-optimal policy, which leads to a
medium-rewarding terminal state. In the case of Q-learning, its convergence
guarantee might seem like a solution to this problem. While true on a
theoretical level, the convergence requirement of an infinite number of visits
to _every_ state-action pair is impossible to satisfy perfectly in practice,
leaving failure as a possibility unless adequate measures are taken to ensure
the environment is explored thoroughly. Nonetheless, such precautions could
lead to a sensible increase in the time required to converge. Moreover, when
using algorithms that do not benefit from any kind of convergence guarantee,
the risk of consequences arising from the sparseness of rewards is even
higher.

To solve this problem, one solution is to _lead_ the agent into following good
paths in the environment by providing a series of intermediate
rewards999Intuitively, this is the same idea motivating the practice of luring
someone to a location of choice by leaving a trail of money on the ground..
This is the main idea behind reward shaping, which formally translates into a
substitution of the original reward function $r(s,a,s^{\prime})$ with a new
one:

$r^{\prime}(s,a,s^{\prime})=r(s,a,s^{\prime})+f(s,a,s^{\prime})$

for a given function $f:S\times A\times S\rightarrow\mathbb{R}$, which is
commonly defined as a shaping function. However, as anticipated by the
corridor example from section 2.2, for the shaping reward function to help,
intermediate rewards must be designed in a way that avoids the introduction in
the environment of new policies that, while numerically optimal, lead to
behavior not relevant for the task’s completion.

Fortunately, [NHR99] provides a simple condition that the $f(\cdot)$ function
must satisfy to guarantee the preservation of the original set of optimal
policies by the shaping reward function, based on the concept of potential-
based shaping functions:

######  Definition 9.

Given an MDP $\mathcal{M}=(S,F,A,r,p,\gamma)$ and a function $f:S\times
A\times S\rightarrow\mathbb{R}$, we say that $f$ is a _potential-based shaping
function_ if there exists a function $\Phi:S\rightarrow\mathbb{R}$ such that:

$f(s,a,s^{\prime})=\gamma\Phi(s^{\prime})-\Phi(s)\quad\forall s\in
S-{s_{0}},a\in A,s^{\prime}\in S$

The use of such a class of shaping functions is sufficient in guaranteeing the
preservation of every optimal policy in the original MDP.

##  Chapter 3 Reward machine-based RL

Reward machines (RMs) are a simple yet effective, automata-based formalism
recently proposed in the neurosymbolic reinforcement learning literature to
facilitate an agent’s learning process by granting it access to a structured
representation of the reward signal. In particular, this approach is very
effective in dealing with tasks characterized by a strong hierarchical
structure. By decomposing the reward function in the form of a finite-state
automaton, agents can keep explicit track of their current progress in the
task, thus allowing them to:

  * •

increase their _overall proficiency_ by learning a set of sub-policies, each
expressing the adequate behavior for progressing in a specific portion of the
task;

  * •

improve the _sample efficiency_ of the learning process by allowing for the
generation of synthetic experiences.

Initially proposed in the context of fully observable MDPs by [Ica+18], the
framework has been extended to deal with partially observable environments in
[Ica+19]. In such problems, one key issue is the need for effective memory
mechanisms that allow the agents to maintain a model of the unobservable
portion of the environmental state. In this regard, reward machine-based
techniques demonstrated the ability to converge to optimal policies in
benchmark environments where standard state-of-the-art RL algorithms equipped
with LSTM-based neural network memory architectures could make no progress.
Thus, the approach proved to be a viable choice for dealing with memory-
related issues in partially observable environments.

###  3.1 Intuition, definitions, and properties

The fundamental intuition behind the use of reward machines is to introduce a
higher layer of abstraction in the representation of the environment: every
time the agent observes the current state of the world, it supplies it to a
labeling function which, in turn, has the role of detecting any _high-level
events_ that might have verified. Depending on the task at hand, detecting an
event of interest might trigger a transition in the reward machine state:
this, intuitively, corresponds to a progression in the overall task. Moreover,
each state of a reward machine can be associated with a different reward
function, thus allowing for the effective modeling of complex reward dynamics,
possibly consisting of conditional choices or loops defined over the given set
of high-level events.

To clarify the above intuition, let us consider an example of a simple, fully
observable environment: _Simple Cookie World_ 111The “simple” connotation will
be clear to the reader in Section 5.1.1., depicted in figure 3.1. The agent
starts in the hallway and aims to eat the cookie in room 1, which gives a
reward of +1. Moreover, due to its incredible hunger, the agent receives a
reward of -0.1 for each step before eating the cookie, except when pressing
the button. However, the cookie appears only after the agent has pressed the
button in room 2. Full observability is granted by allowing the agent to see
the content of both rooms while in either of them. The high-level events for
this simple task are B, indicating the agent has pressed the button, and C,
indicating the agent has eaten its desired treat. In addition, the dummy event
– represents the absence of any other event.

Figure 3.1: Simple Cookie World environment. The agent is represented by the
red circle, the cookie by the green diamond, and the button by the blue
square.

The 3-state reward machine in figure 3.2 accurately describes the structure of
the task and, dually, its reward signal. The reward machine’s initial state
$u_{0}$ represents the beginning of the task when the agent has not yet
pressed the button. Then, after pressing the button, the state transitions to
$u_{1}$, indicating the cookie’s presence in room 1. Finally, after the cookie
is eaten, the RM transitions to its terminal state $u_{2}$, marking the
successful completion of the task.

$u_{0}$$u_{1}$$u_{2}$$\langle{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}\textbf{B}}\rangle$$\langle{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}\textbf{C}},{\color[rgb]{0,1,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,1,0}\pgfsys@color@cmyk@stroke{1}{0}{1}{0}\pgfsys@color@cmyk@fill{1}{0}{1}{0}\textbf{+1}}\rangle$$\langle{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}\textbf{--}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\pgfsys@color@cmyk@stroke{0}{1}{1}{0}\pgfsys@color@cmyk@fill{0}{1}{1}{0}\textbf{-0.1}}\rangle$$\langle{\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color@cmyk@fill{0.94}{0.54}{0}{0}\textbf{--}},{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\pgfsys@color@cmyk@stroke{0}{1}{1}{0}\pgfsys@color<EMAIL_ADDRESS>Figure 3.2: Reward machine for the Simple Cookie World.

####  3.1.1 Full observability

Starting from the case of fully observable environments, let us formally
define a reward machine:

######  Definition 10.

Let $\mathcal{P}$ be a set of propositional symbols, and $S,A$ be the sets of
environment states and agent actions for an arbitrary MDP.
A _Reward Machine_ is a tuple
$\mathcal{R}_{\mathcal{P}}=(U,u_{0},T,\delta_{u},\delta_{r})$, where:

  * •

$U$ is a finite set of _states_ ;

  * •

$u_{0}\in U$ is the _initial state_ ;

  * •

$T$ is a finite set of _terminal states_ such that $U\cap T=\emptyset$;

  * •

$\delta_{u}:U\times 2^{\mathcal{P}}\rightarrow U\cup T$ is the _state-
transition function_ ;

  * •

$\delta_{r}:U\rightarrow[S\times A\times S\rightarrow\mathbb{R}]$ is the
_state-reward function_.

In light of the intuition presented in the previous section, the definition is
easily interpreted: $\mathcal{P}$ represents the set of every possible high-
level event that is relevant to the task at hand, $\delta_{u}$ is the function
governing the state transitions of the reward machine, based on its current
state and the latest subset of events detected in the environment. Finally,
$\delta_{r}$ is the function associating each reward machine state to a
different reward function. Let us now properly define a labeling function:

######  Definition 11.

Let $\mathcal{P}$ be a set of propositional symbols and $S,A$ be the sets of
environment states and agent actions for an arbitrary MDP.
A _labeling function_ is any function in the form:

$L:S\times A\times S\rightarrow 2^{\mathcal{P}}$

Given the state of the environment $s\in S$, the action taken by the agent
$a\in A$, and subsequent state $s^{\prime}\in S$, $L(s,a,s^{\prime})\subseteq
2^{\mathcal{P}}$ is the set of propositional symbols, _i.e.,_ events, that
currently hold in the environment.

All the formal tools needed for presenting a fundamental observation that
motivates the techniques which will be examined later in this chapter are now
available:

######  Observation 1.

Given an arbitrary MDP $\mathcal{M}=(S,F,A,r,p,\gamma)$, a labeling function
$L$, and a reward machine
$\mathcal{R}_{\mathcal{P}}=(U,u_{0},T,\delta_{u},\delta_{r})$, a new MDP
$\mathcal{M}_{\mathcal{R}_{\mathcal{P}}}=(S^{\prime},A,F,p^{\prime},r^{\prime},\gamma)$
can be defined, where:

  * •

the new state space is defined as the cross product between environment and
reward machine states:

$S^{\prime}=S\times U$

  * •

the new reward function $r^{\prime}:S^{\prime}\times A\times
S^{\prime}\rightarrow\mathbb{R}$ produces its output based on the reward
function associated with the current reward machine state:

$r^{\prime}(\langle s,u\rangle,a,\langle
s^{\prime},u^{\prime}\rangle)=\begin{cases}\delta_{r}(u)(s,a,s^{\prime})&\text{if
}u\notin T\\\ 0&\text{otherwise}\end{cases}$

  * •

the new environment transition model $p^{\prime}$ is defined by:

$p^{\prime}(\langle s^{\prime},u^{\prime}\rangle|\langle
s,u\rangle,a)=\begin{cases}p(s^{\prime}|s,a)&\text{if }u\in T\land
u^{\prime}=u\\\ p(s^{\prime}|s,a)&\text{if }u\in U\land
u^{\prime}=\delta_{u}(u,L(s,a,s^{\prime}))\\\ \ \ \quad
0&\text{otherwise}\end{cases}$

While apparently complex, this definition requires the reward machine state
dynamics to be respected for a transition from $\langle s,u\rangle\in
S^{\prime}$ to $\langle s^{\prime},u^{\prime}\rangle\in S^{\prime}$ to be
possible in the new cross-product state space. In other words, it associates a
null probability to every transition leading from a non-terminal RM state to
another one unless the output of the labeling function properly triggers such
transition. This aside, the underlying environment transition model is left
unmodified.

The above observation serves a dual purpose: on the one hand, it provides a
proper formalization for the integration of reward machine-based reward
signals into arbitrary MDPs; on the other hand, it motivates the idea of
augmenting the environmental state space with the high-level information
provided by reward machine states, which – as we will see – is the main
advantage offered by the adoption of the RM framework, especially when dealing
with partial observability.

##### Dealing with non-markovian reward signals

In terms of their expressive potential, reward machines are significantly more
powerful than the regular reward functions introduced by definition 1:

$r:S\times A\times S\rightarrow\mathbb{R}$

In fact, by providing the latter definition I implicitly extended the
assumption of a Markovian environment transition model to the reward signal as
well. However, when faced with non-Markovian reward signals, such a definition
is intrinsically inadequate in representing, for instance, rewards that change
over time, or depending on the history of agent actions and/or environment
transitions. On the contrary, the reward machine-based formulation is able to
represent a subclass of signals in the form:

$R:(S\times A\times S)^{*}\rightarrow\mathbb{R}$

mapping environment trajectories to their associated reward — intuitively — as
long as such trajectories can be correctly summarized by the reward machine
states, thus leading, at any given time, to the usage of the correct reward
function $\delta_{r}(u)$. In such cases, by passing from the original MDP to
the RM-based MDP characterized by the cross-product state space, the Markov
property of the reward function can be recovered, thus highlighting another
advantage arising from the state space augmentation.

##### Simple reward machines

The definition of the state-reward function $\delta_{r}$ presented in
definition 10 might be unnecessarily complex for many practical tasks of
interest. In such cases, we can restrict ourselves to a smaller class of
reward machines:

######  Definition 12.

Given a set $\mathcal{P}$ of propositional symbols, a _Simple Reward Machine_
is a tuple $\mathcal{R}_{\mathcal{P}}=(U,u_{0},T,\delta_{u},\delta_{r})$,
where:

  * •

$U,u_{0},T,\delta_{u}$ are defined as for a regular RM;

  * •

the state-reward function

$\delta_{r}:U\times 2^{\mathcal{P}}\rightarrow\mathbb{R}$

also depends on $2^{\mathcal{P}}$ and directly returns a real number.

Due to a lack of need for the increased expressiveness of general reward
machines, from now on, when referring to reward machines, I will implicitly
assume this more straightforward formulation.

As a final note, it is easy to show that simple reward machines are, in fact,
a subclass of regular reward machines:

######  Observation 2.

Let L be an arbitrary labeling function. Any simple reward machine
$\mathcal{R}_{\mathcal{P}}=(U,u_{0},T,\delta_{u},\delta_{r})$ is equivalent to
a regular reward machine
$\mathcal{R}_{\mathcal{P}}^{\prime}=(U,u_{0},T,\delta_{u},\delta^{\prime}_{r})$,
with:

$\delta^{\prime}_{r}(u)(s,a,s^{\prime})=\delta_{r}(u,L(s,a,s^{\prime}))\quad\forall
u\in U,\ s,s^{\prime}\in S,\ a\in A$

####  3.1.2 Partial observability

As previously anticipated, using a reward machine can be a very effective tool
for dealing with partially observable environments. Recalling the definitions
presented in section 2.2.1, POMDPs require policies that depend on the history
of agent observations and actions. From a practical point of view, this
requires the agents to be provided with some type memory mechanism allowing
them to keep track of such history effectively. However, implementing
effective memory mechanisms is a complex technical challenge, especially when
the task requires deep-learning-based RL algorithms.

As argued by [Mor+23] in [Mor+23], when de-facto standard implementations of
state-of-the-art RL algorithms are analyzed, it is easy to observe the lack of
availability of a wide array of different memory architectures. Most
implementations resort to frame stacking, _i.e.,_ the simple concatenation of
subsequent observations, while others resort to the use of recurrent neural
network architectures such as Long Short-Term Memory (LSTM) or Gated Recurrent
Units (GRU). However, the former approach is only suitable for tasks that pose
extremely short-term memory requirements; on the other side, the latter, while
able to handle much longer temporal dependencies, imposes a significant
computational cost to the training procedure. While they do not represent a
one-fits-all solution for the memory problem in POMDPs, reward machines can
represent a powerful tool for increasing an agent’s ability to keep track of
crucial information, thus increasing its overall memory capacity even without
any other memory mechanism.

Since the formalization of a — simple — reward machine presented by definition
12 does not depend on any specific component of an MDP, it can be adopted
without modification in the context of POMDPs. The same does not apply to the
definition of a labeling function, as it requires environmental states.
Nonetheless, adjusting such a definition to the case of partial observability
is trivial:

######  Definition 13.

Let $\mathcal{P}$ be a set of propositional symbols and $O,A$ be the sets of
agent observations and actions for an arbitrary POMDP.
A _labeling function_ is any function in the form:

$L:O_{\emptyset}\times A_{\emptyset}\times O\rightarrow 2^{\mathcal{P}}$

where, for any set $X$, $X_{\emptyset}=X\cup\\{\emptyset\\}$ by definition.

Aside from the substitution of environment states with agent observations, the
only minor difference lies in the first two terms of the function’s domain,
which are now allowed to be empty. Conventionally, $L(\emptyset,\emptyset,o)$
represents the initial set of high-level events that can be detected upon
entering the environment before the agent takes any action.

Thus, by having access to a proper labeling function, an agent can exploit a
reward machine in a partially observable setting in the same way it would if
faced with a fully observable environment: given its current reward machine
state $u_{t}$, the agent, for each observation $o_{t}$ it obtains, determines
the action $a_{t}$ to be taken according to its policy and executes it,
receiving a new observation $o_{t+1}$. Then, the agent receives an output
$\sigma_{t}=L(o_{t},a_{t},o_{t+1})$ from its labeling function, which can
finally be used to determine the next state of the reward machine
$u_{t+1}=\delta_{u}(u_{t},\sigma_{t})$ and reward
$r_{t}=\delta_{r}(u_{t},\sigma_{t})$. After updating its policy via its method
of choice, the agent starts a new iteration of this procedure.

##### Reward machines as agent memory

While, in a fully observable environment, the usefulness of reward machines
mainly derives from the use of specially designed learning algorithms that
exploit their structure, in partially observable settings, they intrinsically
allow the agent to keep track of information that might no longer be available
from its current observations. To clarify, let us refer to the example
environment from section 3.1. When its reward machine is in state $u_{1}$, the
agent knows that the cookie is in room 1. However, due to the assumed full
observability, the agent does not need the RM to access this information; it
can simply see it by itself. However, if we remove the agent’s ability to see
everything and instead allow him only to see the content of the room it is
currently in, thus making the environment partially observable, suddenly the
$u_{1}$ reward machine state enable the agent to know about the presence of
the cookie _even though it may not be able to see it_. Therefore, the reward
machine effectively becomes a form of memory for the agent, thus providing him
with a fundamental tool to deal with the complexity introduced by partial
observability. In other words, a reward machine can provide an agent with
_additional_ information, otherwise unavailable, that it can use to guide its
learning and decision-making processes.

However, the reward machine is not the source of such information: it could
more appropriately be described as its _storage medium_ 222For the sake of
precision, it is the current reward machine state that stores such
information. Thus, the set of reward machine states could equivalently be seen
as a set of propositions about the state of the environment. Only the
proposition associated with the current state can be deemed true at any given
time.. Instead, the _actual source_ of such information is the labeling
function, which, via its outputs, allows the reward machine to transition
between different states, thus allowing the agent to update its current
knowledge regarding the high-level state of the environment.

This observation leads to two fundamental insights: On the one hand, a proper
design of the labeling function allows the agent to be provided with
information that is not yet available. For instance, in the partially
observable Simple Cookie World, the agent’s RM transitions to $u_{1}$ upon
pressing the button333For example, when
$L(o,a,o^{\prime})={\color[rgb]{0.0600000000000001,0.46,1}\definecolor[named]{pgfstrokecolor}{rgb}{0.0600000000000001,0.46,1}\pgfsys@color@cmyk@stroke{0.94}{0.54}{0}{0}\pgfsys@color<EMAIL_ADDRESS>thus, before the agent has had any opportunity to observe the presence of the
cookie in the other room. Furthermore, a labeling function could even provide
the agent with information that could _never_ be available to him via its
observations. Under the latter scenario, the labeling function could be seen
as a potential method of giving advice to the agent. On the other hand, the
role of the labeling function makes its correct design — and operation —
highly critical to the agent’s training and decision-making correctness. This
observation is the fundamental idea motivating the attack techniques I propose
with my thesis, thoroughly presented in chapter 4.

##### Perfect reward machines

In light of the above considerations, ideally, in a partially observable
setting, a reward machine should allow keeping track of relevant past
information in such a way that renders the environment Markovian with respect
to $O\times U$. A reward machine showing this property is called a perfect
reward machine for the environment at hand and can be formally defined as
follows:

######  Definition 14.

A reward machine $\mathcal{R}_{\mathcal{P}}=(U,u_{0},T,\delta_{u},\delta_{r})$
is said to be _perfect_ for a given POMDP $\mathcal{P}_{\mathcal{O}}$ with
respect to a labeling function $L$ if, and only if, for each trajectory
$(o_{0},a_{0},...,o_{t},a_{t})$ generated by any policy over
$\mathcal{P}_{\mathcal{O}}$:

$Pr(o_{t+1},r_{t}|o_{0},a_{0},...,o_{t},a_{t})=Pr(o_{t+1},r_{t}|o_{t},u_{t},a_{t})$

where $Pr(A|B)$ denotes the conditional probability for $A$ given $B$.

Indeed, the above definition requires the Markov property to hold for the
probability of observing any given observation-reward pair, given the current
observation, reward machine state, and agent action. Also, it is to be noted
that whether a reward machine is perfect or not for a given environment
depends on the choice of the labeling function, thus once again highlighting
its fundamental role in the proper operation of RM-based RL agents.

Finally, this definition leads to two important theorems, proved by [Ica+19],
that effectively enable the use of perfect reward machines:

######  Theorem 1.

Given any arbitrary POMDP $\mathcal{P}_{\mathcal{O}}$ with a _finite_ ,
_reachable_ belief space, there will always exist at least one perfect reward
machine $\mathcal{R}_{\mathcal{P}}$ for $\mathcal{P}_{\mathcal{O}}$ with
respect to _some_ labeling function L.

Despite the nice existence guarantee provided by this theorem, its usefulness
is mainly theoretical, as it gives no indication of such a reward machine’s
size or structure, nor does it hint at the labeling function that must be
used. Nonetheless, it ultimately provides the theoretical basis that allows
one to know that finding a perfect reward machine is, at least, always
possible as long as the POMDP of interest is characterized by a specific type
of belief space.

On the contrary, the following theorem provides a much more important
guarantee, as it ensures that the use of a perfect reward machine is
sufficient for finding optimal policies for any given POMDP:

######  Theorem 2.

Let $\mathcal{R}_{\mathcal{P}}$ be a perfect reward machine for a given POMDP
$\mathcal{P}_{\mathcal{O}}$ with respect to a labeling function $L$. Then, any
optimal policy for the $\mathcal{R}_{\mathcal{P}}$-augmented444Once again, I
am referring to the equivalent POMDP obtained by adapting observation 1 to the
case of partial observability, _i.e.,_ the POMDP characterized by the cross-
product space $O\times U$. POMDP is also optimal for
$\mathcal{P}_{\mathcal{O}}$.

###  3.2 Exploiting RMs for learning

As anticipated in the introduction of this chapter, the main purpose of a
reward machine is to aid the agent’s learning process: doing so requires the
use of specially designed algorithms.

This section presents two such techniques: _Q-learning with Reward Machines_
(QRM) — [Ica+18] — and _Automated Reward Shaping_ (ARS) — [Ica+22]. The former
is a variation of Q-learning that relies on the state-space augmentation
presented in observation 1 to allow for the generation of synthetic
experiences that the agent can use to speed up its convergence, while the
latter is a novel technique that exploits the agent’s reward machine to
automatically compute a potential-based shaping function that can then be used
to introduce reward shaping in the agent’s training.

####  3.2.1 Q-Learning with Reward Machines

Being a variation of standard Q-learning, the Q-learning with Reward Machines
algorithm follows the same conceptual design: it uses the agent experiences to
update its Q-value estimates iteratively until convergence to the true
Q-function. Moreover, it also uses the Q-values to determine the current
agent’s behavioral policy under the MEU framework. In light of this, just like
standard Q-learning, QRM is a value-based, model-free, off-policy algorithm.
Furthermore, it also allows for the seamless use of DQNs for the
representation of the Q-function, thus leading to the DQRM variation of the
algorithm. However, by operating over the — equivalent — RM-augmented MDP
obtained from the original MDP via the transformations presented by
observation 1, the QRM algorithm introduces two key modifications aimed at
allowing the agent to fully exploit the high-level information and task
structure exposed by its reward machine.

The first of these expedients is the use of a different Q-function
$\tilde{q}_{u}(s,a)$ for each reward machine state. Thus, the global
Q-function becomes:

$Q(\langle s,u\rangle,a)=\tilde{q}_{u}(s,a)\quad\forall u\in U$

This effectively allows the agent to learn a different policy for each reward
machine state, potentially aiding the learning process when the task of
interest is characterized by a series of sub-phases, each requiring the agent
to adopt a substantially different strategy. Moreover, the potential benefits
arising from this are even higher in partially observable environments in
light of the memory interpretation of RMs presented in section 3.1.2. On the
other hand, the main downside of this approach lies in an increase in the
space required to store the Q-function, which now effectively needs to store
$n=|U|$ values for each state-action pair or, for DQRM, $n$ distinct neural
networks.

##### Counterfactual reasoning with reward machines

The second, most important, tweak over standard Q-learning consists of the use
of counterfactual reasoning as a tool for simulating the outcome the agent
would have obtained were it acting while in a different reward machine state,
thus allowing for the generation of synthetic experience that can be used to
speed up the learning process. This approach — aptly termed _counterfactual
experiences for reward machines_ (CRM) — is based on the following
observation:

######  Observation 3.

Suppose the agent took action $a$ while in cross-product state $\langle
s,u\rangle$, consequently reaching $\langle s^{\prime},u^{\prime}\rangle$ and
obtaining a reward $r$. Then, had the initial RM state been $\bar{u}$, the
agent would have reached state $\langle
s^{\prime},\delta_{u}(\bar{u},L(s,a,s^{\prime}))\rangle$ while receiving a
reward $\bar{r}=\delta_{r}(\bar{u},L(s,a,s^{\prime}))$.

This observation follows directly from the definition of a reward machine and
is made possible by the fact that the use of a reward machine does not alter
the environment dynamics: regardless of the current RM state, taking action
$a$ in environment state $s$ will always lead to a new state $s^{\prime}$ that
depends solely on the environment transition model $p(s^{\prime}|s,a)$.
Therefore, since the reward machine dynamics are known and superimposed over
the environmental ones, they can be easily simulated by the agent via the
above method, effectively allowing for the generation of synthetic experience
in the RM-augmented state space. Therefore, thanks to CRM, after each step,
the agent, in addition to $(s,u,a,r,s^{\prime},u^{\prime})$, can use the
following set of experiences to update its Q-value estimates:

$\\{(s,\bar{u},a,\delta_{r}(\bar{u},L(s,a,s^{\prime})),s^{\prime},\delta_{u}(\bar{u},L(s,a,s^{\prime}))\
|\ \forall\bar{u}\in U\\}$

effectively multiplying the data acquisition rate by a factor of $n=|U|$. As a
final summary of the presented concepts, algorithm 5 provides the pseudocode
for the QRM algorithm.

Algorithm 5 Pseudocode for the Q-learning with Reward Machines algorithm for a
given MDP $\mathcal{M}$, reward machine $\mathcal{R}_{\mathcal{P}}$ and
labeling function $L$, running over $k$ episodes with learning rate $\alpha$.
Note that $x\overset{\alpha}{\leftarrow}y$ is used as shorthand notation for
$x\leftarrow x+\alpha(y-x)$

function DQN-ER($\mathcal{M},\mathcal{R}_{\mathcal{P}},L,k,\alpha$)

local variables:

$\tilde{q}_{u}[s,a]:\forall u\in U$, table of Q-values estimates, zero
initialized.

for $episode=1,...,k$ do

$u\leftarrow u_{0}$

$s\leftarrow$ Initial-Environment-State($\mathcal{M}$)

repeat

$a\leftarrow\max\limits_{a^{\prime}}\tilde{q}_{u}[s,a^{\prime}]$

$s^{\prime}\leftarrow$ Execute-Action($\mathcal{M},a$)

$l\leftarrow L(s,a,s^{\prime})$ $\triangleright$ Detect high-level events

$r,u^{\prime}\leftarrow\delta_{r}(u,l),\ \delta_{u}(u,l)$

$\triangleright$ Counterfactual reasoning

$experience\leftarrow\\{\langle
s,\bar{u},\bar{a},\delta_{r}(\bar{u},l),s^{\prime},\delta_{u}(\bar{u},l\rangle\
|\ \forall\bar{u}\in U\\}$

for $\langle s,\bar{u},a,s^{\prime},\bar{u}^{\prime}\rangle\in experience$ do

if Is-Terminal?($\mathcal{M},s^{\prime}$) or Terminal-
State?($\mathcal{R}_{\mathcal{P}},u^{\prime}$) then

$\tilde{q}_{\bar{u}}[s,a]\overset{\alpha}{\leftarrow}r$

else

$\tilde{q}_{\bar{u}}[s,a]\overset{\alpha}{\leftarrow}r+\gamma\max\limits_{a^{\prime}}\tilde{q}_{\bar{u}^{\prime}}[s,a^{\prime}]$

$s,u\leftarrow,s^{\prime},u^{\prime}$

until Is-Terminal?($\mathcal{M},s^{\prime}$) or Terminal-
State?($\mathcal{R}_{\mathcal{P}},u^{\prime}$) return $\\{\tilde{q}_{u}\ |\
\forall u\in U\\}$

####  3.2.2 Automated Reward Shaping

Reward machines allow for more than the generation of synthetic agent
experience. Indeed, by exploiting their structure, it is possible to
automatically determine a potential-based shaping function that can be used to
introduce reward shaping into the agent’s training process and, thus, all its
associated advantages. The main intuition behind this technique — named
Automated Reward Shaping — is the same motivating reward shaping itself:
rewarding an agent for making progress towards the completion of its task. In
general, this requires one to arbitrarily decide which $(s,a,s^{\prime})$
tuples are associated with meaningful progress that should be rewarded.
However, the task structure exposed by an agent’s reward machine already
contains such information, which can, therefore, be extracted automatically by
considering the RM itself as an MDP and using the value iteration algorithm to
compute the utility $V(u)$ of each RM state. Then, the obtained utilities can
be used to define the potential function $\Phi(s,u)=V(u)$555In the original
publication, the authors actually define $\Phi(s,u)=-V(u)$. By experimenting
with both approaches, I found the positive-signed alternative to also work in
practice, while leading to easier-to-interpret shaping rewards. In light of
this, I decided to prefer it to the original formulation. for each environment
state $s$ and RM state $u$. The following observation and algorithm 6
formalize the described approach.

######  Observation 4.

Given any simple reward machine
$\mathcal{R}_{\mathcal{P}}=(U,u_{0},T,\delta_{u},\delta_{r})$, one can
construct an MDP $\mathcal{M}=(S,F,A,r,p,\gamma)$, where:

  * •

the MDP state space is defined by the reward machine state space:

$S=U\quad F=T$

  * •

the agent actions are defined by every possible sub-set of high-level events:

$A=2^{\mathcal{P}}$

  * •

the reward function is induced by the reward machine:

$r(u,\sigma,u^{\prime})=\delta_{r}(u,\sigma)\quad\forall u,u^{\prime}\in U,\
\sigma\in 2^{\mathcal{P}}$

  * •

the environment transition model derives from the reward machine state
dynamics:

$p(u^{\prime}|u,\sigma)=\begin{cases}1\quad&\text{if }u\in T\text{ and
}u^{\prime}=u\\\ 1\quad&\text{if }u\in U\text{ and
}u^{\prime}=\delta_{u}(u,\sigma)\\\ 0\quad&\text{otherwise}\end{cases}$

  * •

the discount factor $\gamma$ can be chosen arbitrarily in $(0,1]$

Algorithm 6 Pseudocode for the Automated Reward Shaping algorithm for a given
reward machine $\mathcal{R}_{\mathcal{P}}=(U,u_{0},T,\delta_{u},\delta_{r})$
using discount factor $\gamma$

function ARS($\mathcal{R}_{\mathcal{P}},\gamma$)

local variables:

$V[u]$: array of utility estimates $\forall u\in U\cup T$, zero initialized.

$error\leftarrow 1$

while $e>0$ do

$error\leftarrow 0$

for $u\in U$ do

$v^{\prime}\leftarrow\max\limits_{\sigma\in
2^{\mathcal{P}}}\\{\delta_{r}(u,\sigma)+\gamma V[\delta_{u}(u,\sigma)]\\}$

$error\leftarrow$ Max($e,|V[u]-v^{\prime}|$)

$V[u]\leftarrow v^{\prime}$ return V

##  Chapter 4 Attacking reward machine-based agents

Given the many benefits originating from the use of reward machines in
reinforcement learning, it is reasonable to believe that, in future years,
their adoption will steadily increase, allowing for the solution of many real-
world tasks that are now deemed too hard to deal with. However, as for any
real-world deployment of recently developed technologies, a solid
understanding of their associated security implications is imperative for
avoiding the potentially huge risks arising from their use, possibly
originating from design flaws, environmental factors, or, in the worst case,
adversarial agents knowingly aiming at undermining the system functioning.
Moreover, a deeper understanding of the conditions and techniques that could
lead to undesirable outcomes arising from the use of reward machines might
also have an intrinsic value, providing meaningful insights that could, in
turn, lead to progress being made toward the improved effectiveness of the
original approach.

While, from a theoretical point of view, the RL research community rapidly
started investigating many variations of the basic RM-based approach in
numerous different settings, its security implications remain unexplored by
currently available literature. For this reason, in this chapter, I present
what is, to the best of my knowledge, the first proposed class of attacks on
reward machine-based reinforcement learning.

###  4.1 Threat model

Before any type of attack on RM-based agents can be designed, it is
fundamental to obtain a solid understanding of every component involved in
their operation, its relationships with other entities, its impact on the
system as a whole, and the practical requirements it poses to real-world
deployments of RM-based agents. Following standard practice in security
research, I thus lead the first part of my investigation according to the
methodology of threat modeling, a systematic approach aimed at highlighting
the aforementioned information relating to the system under analysis, together
with any assumption relating to the attacker’s objective, knowledge and
capabilities. After being collected, all such information can then be used to
create a _threat model_ accurately outlining all the requirements that an
attacker must be able to satisfy to carry out an attack successfully.

####  4.1.1 Objective, knowledge and capabilities

Before analyzing the different elements of vulnerability characterizing an RM-
based agent, in this section, I clarify the preliminary assumptions motivating
the choices that I will describe later, thus giving the reader a clearer
picture of the design process that ultimately led to the proposed class of
attacks. By adopting such assumptions, I aimed to define an attack methodology
characterized by:

  1. 1.

applicability to a wide range of scenarios;

  2. 2.

weak requirements for the attacker;

  3. 3.

ease of execution and implementation;

  4. 4.

high impact on the agent’s behavior;

thus potentially posing as much of a risk for practical deployments of reward
machines as possible.

##### Attacker’s objective

In light of this, the first assumption relates to the objective pursued by the
attacker. Given the reinforcement learning setting, there are many
possibilities as to what an attacker could aim to obtain from its attack. In
the most general case, the adversarial actor might simply want to degrade the
agent’s performance, leading to a situation commonly referred to as _denial-
of-service_ (DoS). From a cybersecurity perspective, this type of attack is
both very common and impactful, since it _usually_ does not require highly
specialized knowledge or techniques to be carried out, and it prevents the
victim’s organization from acquiring the value, arising from the trained
agent’s operativity, it needs to compensate for the high amount of resources
needed to train and deploy the agent in the first place. As an example, let us
consider the domain of financial portfolio management111A simple Google
Scholar query for ”deep reinforcement learning portfolio management” leads to
a plethora of research work, thus making the chosen example reasonable for our
purposes., a highly safety-critical field where any agent’s malfunction could
lead to enormous economic loss for its parent organization. Assuming an agent
is trained to decide the amounts of resources to be allocated for each
investment in its portfolio, an adversarial actor could carry out a DoS attack
to hinder the agent’s ability to make good decisions, thus leading to bad
investments and, consequently high monetary losses.

Alternatively, the attacker might aim at inducing the agent to act following a
_specific trajectory_ of its choice, in order to collect any benefit he could
gain from such a course of action. This is equivalent, in terms of the above
example, to the adversarial actor attempting to drive the agent into making a
specific set of investments that might somehow benefit him. This type of
attacks — named evasion attacks, as they allow the attacker to ”evade” the
agent’s decision-making logic — are usually more sophisticated than DoS, as
they typically require some form of knowledge regarding the attacked model or,
in lack thereof, some technique allowing for model extraction. They generally
allow the attacker to pursue more subtle objectives and are thus harder to
detect. When the subtlety requirement is weaker than the attacker’s need for
consistent agent behavior, the former might aim to induce the agent into
learning a specific policy, leading to what is commonly referred to as a
poisoning attack, for instance by causing it to _systematically_ making a
specific set of investments in favor of attacker-controller enterprises,
regardless of their quality as an asset.

Among all the different possibilities, for which the above examples provide
just a notable selection, I decided to assume the DoS objective for the
attacker, as it represents the scenario that is applicable to the widest set
of practical scenarios. While there might be a limited number of tasks where
an attacker could be reasonably interested in inducing specific behavior from
an agent, any time someone resorts to reinforcement learning for solving some
problem — reasoning under the ”everyone is hostile” assumption that
characterizes most cybersecurity research — there could be someone else, such
as an unfair business rival, aiming at causing the malfunctioning of the
system. Moreover, evaluating a DoS scenario carries the additional benefit of
allowing one to assess the robustness of the agent to both adversarial
settings and unforeseen environmental noise, a common occurrence in the real
world. Finally, the last motivating factor behind my choice lies in its
associated lack of need for specialized knowledge of the victim model, thus
aiding in achieving a simpler attack design.

##### Attacker’s knowledge

From an attacker’s knowledge point of view, there are three types of
assumptions that are usually considered when carrying out cybersecurity
research. The first one is the white-box assumption, which grants the attacker
_complete knowledge_ of the internal structure of the system under analysis.
In the context of reinforcement learning, this translates to the attacker
having full knowledge of the algorithm used to train the agent, its policy,
and any other relevant parameter, depending on the context at hand. For
instance, in the case of a DQN agent, the white box assumption would grant the
attacker unlimited knowledge regarding the internal structure of the agent’s
deep Q-networks, including the value for each network weight. It is
immediately apparent how this type of assumption is really hard to satisfy in
practice. Nonetheless, its adoption is useful in allowing an analyst to assess
the potential impact arising from a worst-case scenario point of view: by
granting an attacker with unlimited knowledge one can determine an upper bound
for the damages arising from any realistic attack.

On the other end, the opposite possibility consists of the black-box
assumption, which grants the attacker no knowledge whatsoever regarding the
inner workings of the target system. Thus, the only information he can resort
to consists of what is publicly available, for instance in the form of the
system’s well-known inputs and outputs. As an example, assuming a black-box
scenario in reinforcement learning might translate to allowing the attacker
only to see the agent acting in its environment, with no type of access to its
internal state. From an attack’s impact perspective, this type of assumption
usually leads to a lower impact, since the adversary has a substantially lower
amount of information to help him achieve its goals. However, this reduced
impact is counterbalanced by the now-higher attack feasibility, which makes
black-box attack far more common in practice than their white-box counterpart.
At the same time, assuming a complete lack of information from the attacker’s
perspective might represent an unrealistically restrictive hypothesis, as
rarely would one try and attack a system without any type of prior gathering
of relevant information.

Moreover, many attacks are carried out in an incremental fashion, starting
from the acquisition of an initial foothold on the target system and
progressively leading to further exploitation thanks to the gradual increase
in available information and capabilities. In light of this, the third
possibility consists of the gray-box assumption, which can be seen as the
middle point between the previous ones: like the white-box one, it allows some
degree of knowledge regarding the inner workings of the system, but, like in
the black-box case, no knowledge is assumed regarding the rest of the system.
Being a combination of the previous approaches, the gray-box assumption likely
represents the most realistic proxy for most real-world cybersecurity attacks,
usually requiring some kind of prior knowledge and, at the same time, allowing
for a considerable impact on the victim system.

During my investigation on the security of RM-based agents, I tried to adhere
to the black-box assumption, with the aim of designing an attack that requires
the lowest possible amount of prior information, thus increasing its overall
practical feasibility. Even though, as will be discussed in the following
sections, clearly classifying the attacks that I developed as either black-box
or gray-box might be, to some degree, debatable, I nonetheless discarded,
during the design phase, any choice that would intrinsically require a
substantial relaxation of the black-box hypothesis.

##### Attacker’s capabilities

Defining what might represent a relevant _capability_ in the context of a
cybersecurity attack clearly depends on both the theoretical and practical
context of interest. In the case of reinforcement learning, a plethora of them
could be easily identified: manipulating the agent’s environment to alter its
dynamics, modifying the agent percepts before it can obtain them, and altering
the reward signal are all reasonable examples of things that an attacker might
need to do to achieve its goals. Therefore, to reduce the breadth of
possibilities that could be considered, a first fundamental distinction must
be made between training-time and deploy-time capabilities, where the firsts
include any action the attacker could carry out during the agent’s training
process and, conversely, the seconds consist of any type of intervention
targeting the agent acting to achieve the task it was previously trained for.
Generally speaking, obtaining training-time access to a reinforcement learning
agent is very difficult. Given its critical role, the agent’s training process
is usually conducted in isolated development environments protected by layers
of firewalls, intrusion prevention systems, and other kinds of defenses.222In
practice, the degree of truth of this statement _highly_ depends on the
organization at hand and its overall security posture. Nonetheless, given any
entity with a sufficient amount of resources and expertise, it is reasonable
to assume this to be at least partially true. On the contrary, once an agent
is ready to be deployed, its operation is more likely to be supported by near-
public systems with just a limited amount of indirection introduced between
them and the end-user. Therefore, once again for feasibility’s sake, I decided
to assume the hypothetical adversary only to have deploy-time access to its
victim.

A second, general class of potential capability assumptions arises depending
on whether the attacker is able only to observe some kind of agent-related
data — thus having read capabilities — or also to introduce new data — _i.e.,_
injection capabilities — or to modify existing data — _i.e.,_ tampering
capabilities. While it may appear impossible for an attack to be feasible when
only having read capabilities, some attacks, such as model extraction, might
indeed just rely on such an assumption. Nonetheless, restricting an attacker
to this scenario drastically reduces the amount of possible attacks, with the
remaining ones usually being characterized by a low impact. This is especially
true when the read-only assumption is adopted in conjunction with the black-
box and deploy-time ones. Therefore, during the design of my attacks, I
allowed the attacker to have some type of write access when needed.

####  4.1.2 Elements of vulnerability

By recalling the defining elements of a reward machine
$\mathcal{R}_{\mathcal{P}}=(U,u_{0},T,\delta_{u},\delta_{r})$, the potential
high-level targets for an attack can be readily identified in:

  * •

its _structure_ , represented by its set of states $U\cup T$ and the
connections between them, implicitly defined by $\delta_{u}$;

  * •

its _state dynamics_ , represented by the interactions between the state-
transition function $\delta_{u}$ and the agent’s labeling function $L$;

  * •

its _reward dynamics_ , represented by the state-reward function $\delta_{r}$
and, again, its interactions with the agent’s labeling function $L$.

Given their fundamental importance in determining the agent’s behavior both
during its training, as is true for all three of them, or during its post-
training operativity, as is the case for just the former two, all three of the
identified alternatives potentially represent a valid target for an attack
aimed at impairing the agent’s performance. However, thanks to the assumptions
presented in the previous section, two of them can immediately be ruled out,
thus showcasing the value of the threat modeling methodology in allowing one
to outline its possible routes of attack clearly. Indeed, since the agent’s
reward machine structure is fixed before the training process is even started,
looking for some way to alter it would violate the deploy-time assumption.
Moreover, even assuming some degree of knowledge relating to the reward
machine states or their connections would translate into granting the attacker
access to a large portion of the agent’s internal structure, thus conflicting
with my stated preference towards the black-box setting. Similar
considerations apply to the choice of the RM’s reward dynamics as a potential
target: on the one hand, the reward signal is only relevant for the agent
during its training333For the sake of simplicity, I am knowingly ignoring
online-learning settings, where an agent could still be able to learn during
the operativity _following_ its deployment. and thus any attempt to exploit it
is ruled out once again by the deploy-time assumption. On the other hand,
granting the agent any knowledge relating to its reward signal would represent
no less of a violation of the black-box assumption’ than granting him read
access to its reward machine’s structure.

Therefore, the only remaining possibility lies in the choice of the RM’s state
dynamics as the attack’s high-level target. Then, after determining the
pursued plan, the attack’s scope can be further restricted by considering the
single components that play a role in determining how an RM transitions
between its states. As previously observed, there are two of such components:
the RM’s _state-transition function_ $\delta_{u}$, and the _labeling function_
$L$, which cooperate in determining which state the agent’s reward machine
should transition to, based on its current state and the high-level events
detected in the environment. Thus, this suggests a possible attack plan: An
adversarial actor could aim at tampering with such dynamics in a way that
leads the agent into a false belief regarding the high-level state of the
environment, represented by its reward machine state according to the memory-
based interpretation presented in section 3.1.2.

From a theoretical standpoint, this looks highly promising as an agent might
need to rely heavily on its reward machine state to derive optimal policies,
especially in partially observable environments. To exemplify, recall the
Simple Cookie World example from chapter 3, in its partially observable
variation. In such a scenario, the optimal policy for the agent is very simple
and maps perfectly onto its reward machine: at the beginning of the episode,
_i.e.,_ when its RM is in state $u_{0}$, and there is no cookie yet to be
eaten, the agent needs to go right until it finds the button, then press it.
Conversely, when the agent knows the cookie is available, _i.e.,_ when its RM
is in state $u_{1}$, the only thing the agent needs to do is go left until it
reaches the cookie. Therefore, it is easy to see how an error in the agent’s
reward machine could lead to its complete inability to achieve the task: if,
for instance, the agent’s reward machine were to transition to state $u_{1}$
mistakingly, with the cookie not yet available, the agent would be stuck _ad
infinitum_ in going left, trying to reach a cookie that does not exist. While
a toy example in nature, the showcased scenario is not to be excluded a priori
as a possibility in any more complex environment, where the increase in
complexity is very likely to hide subtle dependencies between the agent’s
policy and its reward machine state, thus potentially giving rise to analogous
situations. For these reasons, I chose to pursue this exact attack plan to try
and hinder an RM-based agent’s performance.

Thus, in light of the above considerations, there remains only one element
that needs to be defined before the actual attack strategy can be outlined:
the low-level target of the attack. Between the RM’s state-transition function
and the agent’s labeling function, I chose the latter. The labeling function,
with respect to the stated assumptions and objectives for the design of the
attack, represents the perfect target for two reasons. On the one hand, its
fundamental role in triggering the agent’s RM state transitions grants an
attacker a wide range of possibilities in terms of the potential consequences
arising from its careful manipulation. On the other hand, by being a
conceptually separated entity from the agent’s reward machine, the labeling
function might, in practice, allow for a wider range of solutions to be
adopted for its implementation. Indeed, it is not unreasonable to hypothesize
an agent having the need for two separate programs running on its physical
architecture: one computing its policy and, therefore, its reward machine
dynamics, and one with the sole role of computing the labeling function
outputs. For instance, this could be a valid practical solution in the case of
tasks characterized by the agent receiving observations in the form of images.
In such cases, detecting high-level events, such as the presence of a given
object, might require the use of complex computer vision models, likely in the
form of convolutional neural networks. Thus, in such a scenario, it would be
reasonable to decouple the actual agent’s program from the event-detection one
to obtain an array of potential advantages, including easier development,
lower maintenance, efficiency, and modularity. In some cases, it might even be
desirable to resort to network-based solutions requiring the agent to forward
its $(s,a,s^{\prime})$ tuples to a labeling server which, in turn, reports the
detected events back to the agent via some type of communication channel. All
of the above scenarios introduce many openings that an attack could exploit
for tampering with the labeling function, thus highlighting another reason for
its choice.

####  4.1.3 Potential attack methodologies

As a quick summary of all the decisions that were taken up to the definition
of the target, the proposed attacks:

  * •

aims at hindering the pre-trained agent’s performance;

  * •

by manipulating its labeling function to alter the reward machine’s state
dynamics;

  * •

assuming access to the least amount of information possible;

  * •

attempting to minimize the number of actions required from the attacker.

The methodology that I initially considered consists of the attacker injecting
arbitrary sets of high-level events _in place_ of the correct labeling
function outputs. By doing so, he could, in theory, induce the agent’s RM into
transitioning to any of the states reachable by its current one. For instance,
in the Simple Cookie World example, the attacker could lead the agent to
believe that the cookie is available, _i.e.,_ induce its RM to transition from
$u_{0}$ to $u_{1}$ — by _falsely_ informing him that the button has been
pressed, as depicted in figure 4.1. This type of attack is, in theory, very
powerful, as it allows one to control the evolution of the agent’s reward
machine arbitrarily and, consequently, its policy. However, being able to
achieve this in practice is far from trivial for a number of reasons.

Figure 4.1: Example of altered RM state dynamics arising from an attacker
_injecting_ an arbitrary high-level event — denoted by the red label — to the
victim’s reward machine in the Simple Cookie World environment. Green nodes
represent the true reward machine states, while red nodes denote the attacker-
induced ones.

Firstly, it requires the attacker to know _what_ and _when_ he must inject to
obtain the desired effect: providing the agent with a set of high-level events
that do not trigger any transition from its current state has no effect other
than creating noise that could aid the victim in detecting the attempted
attack. Thus, the attacker needs to either be _very_ lucky and indifferent to
the possibility of being detected or, more realistically must be armed with
in-depth knowledge regarding the victim’s reward machine. Secondly, even if we
assume the attacker to be able to trigger any arbitrary transition at will, a
second problem is quick to emerge: How can he determine which transition would
lead to the greatest decrease in the victim’s performance? While simple
scenarios might allow for some speculation in this regard, any sufficiently
complex environment would lead to proportionally sophisticated agent behavior
that would likely render such analysis practically impossible. Even in case
the attacker had control over a _complete_ copy of the agent, allowing him to
simulate every possible attack route, he is faced with the task of choosing
the best path — in terms of worst agent performance — among all the possible
ones that exist in the victim’s RM. On the one hand, the number of such paths
might even be infinite in the presence of any loop in the reward machine’s
structure. On the other hand, even assuming their number is finite and small
enough to make the task tractable in theory, the huge computational costs