# Query Based Access Control for Linked Data

Sabrina Kirrane  Vienna University of Economics and Business, Austria
Alessandra Mileo  Dublin City University, Ireland  Axel Polleres  Vienna
University of Economics and Business, Austria  Stefan Decker  Fraunhofer FIT,
RWTH Aachen University, Germany

###### Abstract

In recent years we have seen significant advances in the technology used to
both publish and consume Linked Data. However, in order to support the next
generation of ebusiness applications on top of interlinked machine readable
data suitable forms of access control need to be put in place. Although a
number of access control models and frameworks have been put forward, very
little research has been conducted into the security implications associated
with granting access to partial data or the correctness of the proposed access
control mechanisms. Therefore the contributions of this paper are two fold: we
propose a query rewriting algorithm which can be used to partially restrict
access to SPARQL 1.1 queries and updates; and we demonstrate how a set of
criteria, which was originally used to verify that an access control policy
holds over different database states, can be adapted to verify the correctness
of access control via query rewriting.

##  1 Introduction

The term Linked Data Web (LDW) is used to describe a World Wide Web where data
is directly linked with other relevant data using machine-accessible formats
[9, 6]. Although the LDW has seen considerable growth in recent years, the
focus continues to be on linking public data. This can partially be attributed
to the fact that no formal recommendation exists for allowing partial access
to Linked Data based on predefined access control policies.

Several researchers have proposed access control strategies for the Resource
Description Framework (RDF), which could be applied to Linked Data. Broadly
speaking, these frameworks enforce access control either at the data layer [4,
8], the query layer [1, 5, 2, 10, 11] or a combination of both [7].
Enforcement of access control at the data layer is concerned with removing
unauthorised data from a dataset. Whereas, enforcement at the query layer
relies on using query rewriting techniques to ensure that only authorised
query results are returned.

Given we need to cater for many users, with many different authorisations a
filtering approach will not scale well, therefore in this paper we adopt a
query rewriting approach. To date researchers have proposed query rewriting
strategies that involve adding contextual information pertaining to the
requester to the query using path expressions and bindings [1, 5, 11], or
adding bindings for authorised/unauthorised classes, properties or instances
using filters [2, 10]. Our query rewriting strategy builds on the latter
approach by demonstrating how quad patterns can be used to grant or deny
access to RDF data at multiple levels of granularity (triple, named graph,
classes, properties, instances). In addition, we demonstrate how our query
rewriting strategy can be used not only to enforce access control over basic
graph patterns but also in conjunction with SPARQL 1.1 queries that include
subqueries and negation, graph update operations and graph management
operations. Although in this paper we discuss how access can be restricted to
a single quad pattern as we use FILTER NOT EXISTS to deny access to
unauthorised data our approach can easily be extended to work with graph
patterns. In order to verify the effectiveness of our query rewriting
strategy, we define a set of criteria that can be used to compare the results
obtained when a query is executed over a dataset where all unauthorised data
has been removed, and the results obtained when a query is rewritten and
executed over a dataset, which contains both authorised and unauthorised data.
The contributions of the paper can be summarised as follows: we  (i) formally
define a set of criteria which can be used to verify the correctness of access
control via query rewriting;  (ii) propose query rewriting strategies that can
be used to partially restrict access to SPARQL 1.1 queries and updates; and
(iii) demonstrate how the proposed correctness criteria can be used to verify
existing query rewriting strategies.

The remainder of the paper is structured as follows: _Section_ 2 describes the
different data filtering and query rewriting strategies that are used to
restrict access to RDF data. _Section_ 3 presents a set of correctness
criteria, which allows for access control via query rewriting to be compared
to access control via data filtering. _Section_ 4 proposes query rewriting
strategies for both SPARQL 1.1 queries and updates. In _Section_ 5 we use the
proposed correctness criteria to evaluate both an existing query rewriting
strategy and the alternative strategy presented in this paper. Finally, we
present conclusions and directions for future work in _Section_ 6.

##  2 Related Work

Both Dietzold and Auer [4] and Muhleisen et al. [8] adopt a filtering approach
to access control over RDF data. Dietzold and Auer [4] propose access control
policy specification at multiple levels of granularity (_triples_ , _classes_
and _properties_). Authorisations are used to associate filters (SPARQL
CONSTRUCT queries) with users and resources. When a requester submits a query,
a virtual model is created based on the matched authorisations. The query is
subsequently executed against the virtual model, which only contains data that
the requester is authorised to access. Whereas, Muhleisen et al. [8] allow
access control policies to be specified for _triple patterns_ , _resources_ or
_instances_ using SWRL rules. When a requester submits a query, the system
uses the access control rules to generate a temporary named graph containing
only authorised data. The requesters query is subsequently executed against
the temporary named graph and the results are returned to the user.

A number of researchers Abel et al. [1], Franzoni et al. [5], Oulmakhzoune et
al. [11] have proposed strategies that involve adding policy information to
the query (for example, the requester can only see information relating to
papers that they have authored). Abel et al. [1] specify authorisations in
terms of sets of _contextual predicates_ , _path expressions_ and _boolean
expressions_ that are used to restrict access to instance data. For positive
authorisations, the path expressions and the bindings are appended to the
query WHERE clause. For negative authorisations, the path expressions and the
bindings are added to a MINUS clause, which in turn is appended to the query.
Franzoni et al. [5] also propose a query rewriting strategy which is used to
grant/deny access to _ontology instances_ , based on contextual information
pertaining to the user or the environment. Like Abel et al. [1] bindings are
generated for path expressions specified in the access control policy and both
the path expressions and the bindings are added to the query WHERE clause.
Oulmakhzoune et al. [11] extend previous work by demonstrating how the SERVICE
operator can be used to return bindings based on an external privacy
preferences policy.

Both Chen and Stuckenschmidt [2] and Oulmakhzoune et al. [10] use simple
filters to bind/unbind query solutions based on access control policies that
are specified for specific _classes, properties_ or _individuals_. According
to the rewriting strategy proposed by Oulmakhzoune et al. [10], when access is
prohibited to predicates or objects, the relevant triple patterns are made
OPTIONAL. Although both Chen and Stuckenschmidt [2] and Oulmakhzoune et al.
[10] propose query rewriting strategies for SPARQL queries, the authors focus
specifically on SELECT queries composed of basic graph patterns and no special
consideration is given to complex SPARQL queries that include subqueries or
negation.

Costabello et al. [3] also use contextual data to restrict access to RDF.
However, the proposed query rewriting strategy restricts access to _named
graphs_ as opposed to specific classes, properties and instances. Li and
Cheung [7] propose a query rewriting strategy for views generated from
ontological relations. The proposed query rewriting strategy involves
expanding the view concepts to include implicit concepts, retrieving both
explicit and implicit access control policies and adding range and instance
restrictions, associated with the matched authorisation, to the view query.

When it comes to the evaluations of the aforementioned access control
strategies only Oulmakhzoune et al. [11] examine the correctness of their
access control strategy. The authors present a set of criteria which is used
by Wang et al. [12] to verify that a given access control policy holds over
different relational database states and discuss how their algorithm satisfies
the criteria. However, no formal evaluation is performed.

In contrast to other approaches, our query rewriting strategy can be used not
only to enforce access control over basic graph patterns but also in
conjunction with SPARQL 1.1 queries that include subqueries and negation,
graph update operations and graph management operations. In addition, we
demonstrate how a set of correctness criteria, that was originally used to
verify that a given access control policy holds over different database
states, can be adapted to verify the correctness of access control via query
rewriting, by performing a comparison with access control via data filtering.
As the formal correctness criteria we propose in this paper is not specific to
RDF, it can be used in conjunction with any non-monotonic query language.

##  3 Access Control Correctness Criteria

According to Wang et al. [12] a query processing algorithm should be secure,
sound and maximum. An algorithm is secure if it does not return information
which has not been authorised. An algorithm is sound if it does not return
invalid results. Furthermore, an algorithm is maximum if it returns as much
information as possible without violating the secure and sound constraints. In
its current form, the formal correctness criteria presented in Wang et al.
[12] is unsuitable for the verification of access control over RDF data.
Although it is possible to use their formalism to verify that a secure query
processing algorithm holds over different database states, it cannot be used
to verify that the algorithm is in fact secure, nor can it be used in
conjunction with non monotonic queries such as MINUS and FILTER NOT EXISTS.
Therefore, in this paper we redefine each of the criteria to cater for a
comparison between the results obtained when:  (i) a query is executed against
a dataset which is generated by removing the unauthorised data (henceforth
referred to as filtering); and  (ii) when the same query is rewritten so that
unauthorised data will not be returned and subsequently executed over the
unmodified dataset (which we refer to as rewriting).  In the definitions that
follow the term dataset is used to denote a collection of RDF graphs, which
can include a default graph and one or more named graphs. In this paper we
assume that the dataset does not contain blank nodes. Before formally defining
the correctness criteria we provide definitions for an authorised dataset and
an unauthorised dataset:

######  Definition 1 (Authorised Dataset and Unauthorised Dataset).

Let $D$ denote a dataset and $P$ an access control policy. Given $D$ and $P$,
let $DG$ denote the set of quads in $D$ where access is granted by $P$ and
$DD$ the set of quads in $D$ where access is denied by $P$. Assuming that $DG$
is disjoint from $DD$, then $DG$ is the RDF subgraph of $D$ which is
authorised by $P$, and $DD$ is the RDF subgraph of $D$ which is unauthorised
by $P$ .

###  3.1 Correctness Criteria for Non-Monotonic Queries

When access control via query rewriting is compared to access control via data
filtering, a query rewriting algorithm is deemed secure if each of the
resources returned by the algorithm are present in the authorised dataset. The
algorithm is sound if all of the results returned by the algorithm are also
present in the result set which is generated when the original query is
executed over the authorised dataset. The algorithm is maximum if the data
returned by the algorithm is equivalent to the data returned when the query is
executed over the authorised dataset. We formally redefine the correctness
criteria proposed by Wang et al. [12] as follows:

######  Definition 2 (Query correctness criteria).

Given our definition of _an authorised dataset_ $DG$, let $S$ denote a query
processing algorithm without access control. It follows that when query $Q$ is
executed on $DG$ the result set returned by $S(DG,Q)$ only contains authorised
data.

Let $A(D,P,Q)$ represent a query processing algorithm with access control,
which returns the result set authorised by $P$ when query $Q$ is executed on
$D$. A query processing algorithm is:
_Secure_ if and only if
$\forall{{}_{P}}\forall{{}_{Q}}\forall{{}_{D}}\forall{{}_{DG}}\forall{{}_{r}}$[$r\in
A(D,P,Q)\implies r\in DG$].

_Sound_ if and only if
$\forall{{}_{P}}\forall{{}_{Q}}\forall{{}_{D}}\forall{{}_{DG}}$[$A(D,P,Q)\sqsubseteq
S(DG,Q)$].

_Maximum_ if and only if
$\forall{{}_{P}}\forall{{}_{Q}}\forall{{}_{D}}\forall{{}_{DG}}$[$A(D,P,Q)\equiv
S(DG,Q)$].

###  3.2 Correctness Criteria for Updates

Although Wang et al. [12] focused specifically on queries, in this paper we
are also interested in updates. As SPARQL 1.1 updates change the state of the
dataset, it is necessary to examine the resulting datasets as opposed to
comparing the query results. Here we use the term rewritten dataset to refer
to the dataset which is generated when a rewritten query is executed against a
given dataset, and the term merged filtered dataset to refer to the merge of
the unauthorised dataset with the authorised dataset after the update query
has been executed. A delete query processing algorithm is deemed secure, if
every resource that is in the merged filtered dataset, is in the rewritten
dataset. The algorithm is sound, if the rewritten dataset does not contain
less resources than the merged filtered dataset. The algorithm is maximum, if
the rewritten dataset is equivalent to the merged filtered dataset. An insert
query processing algorithm is deemed secure, if all of the data contained in
the rewritten dataset is also in the merged filtered dataset. The algorithm is
sound, if the rewritten dataset does not contain more resources than the
merged filtered dataset. The algorithm is maximum, if all of the rewritten
dataset is equivalent to the merged filtered dataset.

######  Definition 3 (Update correctness criteria).

Given our definitions for an _authorised dataset_ $DG$ and an _unauthorised
dataset_ $DD$, let $U$ denote an update query processing algorithm without
access control. It follows that when query $Q$ is executed on $DG$ the dataset
generated by $U(DG,Q)$ only contains authorised data.

Let $UD$ denote a delete processing algorithm with access control, where
$UD(D,P,Q)$ produces a new dataset when query $Q$ is executed on the subset of
$D$ which is authorised by policy $P$. A delete query processing algorithm is:
_Secure_ if and only if

$\forall{{}_{P}}\forall{{}_{Q}}\forall{{}_{D}}\forall{{}_{DG}}\forall{{}_{r}}$[$r\in(U(DG,Q)\cup
DD)\implies r\in UD(D,P,Q)$].

_Sound_ if and only if

$\forall{{}_{P}}\forall{{}_{Q}}\forall{{}_{D}}\forall{{}_{DG}}\forall{{}_{DD}}$[$UD(D,P,Q)\sqsupseteq(U(DG,Q)\cup
DD)$].

_Maximum_ if and only if

$\forall{{}_{P}}\forall{{}_{Q}}\forall{{}_{D}}\forall{{}_{DG}}\forall{{}_{DD}}$[$UD(D,P,Q)\equiv(U(DG,Q)\cup
DD)$].

Let $UI$ denote an insert processing algorithm with access control and
$UI(D,P,Q)$ produces a new dataset when query $Q$ is executed on the subset of
$D$ which is authorised by policy $P$. An insert query processing algorithm
is:
_Secure_ if and only if

$\forall{{}_{P}}\forall{{}_{Q}}\forall{{}_{D}}\forall{{}_{DG}}\forall{{}_{DD}}\forall{{}_{r}}$[$r\in
UI(D,P,Q)\implies r\in(U(DG,Q)\cup DD)$].

_Sound_ if and only if

$\forall{{}_{P}}\forall{{}_{Q}}\forall{{}_{D}}\forall{{}_{DG}}\forall{{}_{DD}}$[$UI(D,P,Q)\sqsubseteq(U(DG,Q)\cup
DD)$].

_Maximum_ if and only if

$\forall{{}_{P}}\forall{{}_{Q}}\forall{{}_{D}}\forall{{}_{DG}}\forall{{}_{DD}}$[$UI(D,P,Q)\equiv(U(DG,Q)\cup
DD)$].

##  4 Query Rewriting for SPARQL Queries and Updates

An RDF _triple_ is used to asserts a binary relationship between two pieces of
information. A triple is represented as a tuple $\langle
S,P,O\rangle\in\mathbf{(U\cup B)}\times\mathbf{(I)}\times\mathbf{(I\cup B\cup
L)}$, where $S$ is called the _subject_ , $P$ the _predicate_ , and $O$ the
_object_ and I, B and L, are used to represent _Internationalized Resource
Identifier (IRIs)_ , _blank nodes_ and _literals_ respectively. A _triple
pattern_ is a triple that can potentially contain _variables_ in the subject,
predicate and object positions. A _quad pattern_ is a an extension of a triple
pattern where the fourth element is used to denote the named graph, which can
take the form of either an IRI or a variable. In this paper, we focus
specifically on rewriting the query to filter out the data which has been
restricted, as such we assume that an authorisation framework has already
determined the unauthorised quad patterns that are relevant for a given query.
Although we demonstrate how access can be restricted to a quad pattern, the
approach can easily be extended to work with graph patterns. We use the foaf
prefix to denote the FOAF Vocabulary http://xmlns.com/foaf/0.1/ 111FOAF
vocabulary Specification, http://xmlns.com/foaf/spec/. and the entx prefix to
refer to our sample enterprise vocabulary http://example.org/enterprisex#. The
query results presented throughout this paper are based on the sample data
presented in _Figure_ 1 and the authorisations presented in _Figure_ 2. The
quad pattern, entx:MRyan entx:salary  _?o ?g_ , denies access to May Ryan’s
salary. Whereas, entx:MRyan entx:worksFor  _?o ?g_ , restricts access to
information pertaining to the people that May Ryan works for.

⬇

1entx:EmployeeDetails{

2entx:JBloggs rdf:type foaf:Person.

3entx:JBloggs foaf:name "Joe Bloggs" .

4entx:JBloggs entx:salary 60000 .

5entx:MRyan rdf:type foaf:Person .

6entx:MRyan foaf:name "May Ryan" .

7entx:MRyan entx:salary 33000 .

8entx:JSmyth rdf:type foaf:Person .

9entx:JSmyth foaf:name "John Smyth" .

10entx:JSmyth entx:salary 33000 . }

11entx:OrgStructure{

12entx:MRyan entx:worksFor entx:JBloggs .

13entx:JSmyth entx:worksFor entx:MRyan . }

Figure 1: Enterprise Dataset

⬇

1$\langle\texttt{entx:MRyan},~{}\texttt{entx:salary},~{}{?o},~{}{?g}\rangle$

2$\langle\texttt{entx:MRyan},~{}\texttt{entx:worksFor},~{}{?o},~{}{?g}\rangle$

Figure 2: Unauthorised quad patterns

###  4.1 SPARQL Queries

The SPARQL query language supports four distinct query types (SELECT, ASK,
CONSTRUCT and DESCRIBE). In each case, SPARQL graph pattern matching is used
in order to determine the output of the query. Although the queries presented
in this section are limited to SELECT queries, the proposed query rewriting
strategy is identical for each of the query types.

#### Basic Graph Patterns and Aggregate.

Basic Graph Patterns (BGPs) are sets of triple patterns and aggregates are
functions that are applied to groups of solutions, for example COUNT, SUM,
MIN, MAX, AVG, GROUP_CONCAT and SAMPLE. When we execute _Query_ 1 without any
access restrictions the identifiers, names and the salaries of all persons are
returned.

######  Query 1 (Basic graph pattern).

Given the following query:

⬇

SELECT ?id ?name ?salary WHERE { GRAPH entx:EmployeeDetails {

?id foaf:name ?name. ?id entx:salary ?salary } }

The output is as follows:
?id ?name ?salary entx:JBloggs "Joe Bloggs" 60000 entx:MRyan "May Ryan" 33000
entx:JSmyth "John Smyth" 33000

However, if the requester is denied access to the salary pertaining to
entx:MRyan, by authorisation 1 in _Figure_ 2, we need to filter out the
restricted data. This can be achieved by using a FILTER NOT EXISTS to filter
out unauthorised data and adding it to the relevant graph pattern group.
_Query_ 2 limits the result set to the identities, names and salaries of
authorised persons.

######  Query 2 (Basic graph pattern restricted using binding).

Given the following query:

⬇

SELECT ?id ?name ?salary WHERE { GRAPH entx:EmployeeDetails {

?id foaf:name ?name. ?id entx:salary ?salary

FILTER NOT EXISTS {GRAPH entx:EmployeeDetails {

?id foaf:name ?name. ?id entx:salary ?salary

FILTER ( ?id = entx:MRyan ) } } } }

The output is as follows:
?id ?name ?salary entx:JBloggs "Joe Bloggs" 60000 entx:JSmyth "John Smyth"
33000

#### Subqueries and Filters.

In SPARQL 1.1, negation can be achieved by filtering query results using
FILTER EXISTS, FILTER NOT EXISTS or MINUS expressions. Although subqueries are
not classified under negation, such queries are used to limit the result set
based on the results of an embedded query. The following queries are
constructed using an inner SELECT query, however the query rewriting strategy
is the same for queries that contain FILTER EXISTS, FILTER NOT EXISTS and
MINUS expressions. _Query_ 3 returns the names of all people and the names of
the people that they work for.

######  Query 3 (Subqueries).

Given the following query:

⬇

SELECT DISTINCT ?employee ?manager WHERE { GRAPH ?g {

?x foaf:name ?employee . ?y foaf:name ?manager {

SELECT ?x ?y WHERE { GRAPH ?g { ?x entx:worksFor ?y } } } } }

The output is as follows:
?employee ?manager "John Smyth" "May Ryan" "May Ryan" "Joe Bloggs"

As authorisation 2 in _Figure_ 2 matches a quad in the inner query we add a
FILTER NOT EXISTS to the relevant graph pattern group in the subquery. _Query_
4 results in the filtering of May Ryan and her manager from the result set.

######  Query 4 (Subqueries restricted with binding).

Given the following query:

⬇

SELECT DISTINCT ?employee ?manager WHERE { GRAPH ?g {

?x foaf:name ?employee . ?y foaf:name ?manager

{ SELECT ?x ?y WHERE { GRAPH ?g { ?x entx:worksFor ?y

FILTER NOT EXISTS { GRAPH ?g { ?x entx:worksFor ?y

FILTER ( ?x = entx:MRyan ) } } } } } } }

The output is as follows:
?employee ?manager "John Smyth" "May Ryan"

###  4.2 Query Rewriting Algorithm

Based on the query rewriting strategies presented in the previous section, we
propose a query rewriting algorithm, which ensures that only authorised data
is returned by SPARQL 1.1 queries. The algorithm takes as input a query, and a
set of quad patterns that need to be filtered out of the query results, and
checks each SPARQL graph pattern recursively:

  1. (i)

If any of the graph patterns in the outer query match any of the unauthorised
quad patterns, a FILTER NOT EXISTS element is generated. If the named graph in
the query is a variable and the named graph in the authorisation is a
constant, then a new graph pattern group is constructed using the named graph
from the authorisation and the graph pattern from the query. Otherwise the
unchanged graph pattern group from the query is added to the filter. In
addition, the constants in the subject, predicate and object positions of the
authorisation are bound to the variables in the query using FILTER =
expression. If multiple bindings exists the FILTER is generated using the
conjunction of the bindings.

  2. (ii)

If any of the graph patterns in an inner SELECT, EXISTS FILTER, NOT EXISTS
FILTER or a MINUS match any of the unauthorised quad patterns, a FILTER NOT
EXISTS element is generated as described above and added to the relevant graph
pattern group in the subquery or the filter expression.

###  4.3 SPARQL Updates

SPARQL 1.1 update caters for a number of update operations (CLEAR, LOAD,
INSERT DATA, DELETE DATA and DELETE/INSERT) and a number of graph management
operations (CREATE, DROP, MOVE, COPY and ADD). In the case of update queries
there are two possible options:  (i) the system should inform the requester
that the query cannot be completed and provide a list of the triples that
cannot be deleted, inserted etc.; or  (ii) the system should behave as if the
unauthorised data is not present.  If we adopt the first option, the requester
will be aware that data exists which they do not have access to, and could
potentially infer unauthorised information by issuing one or more additional
queries. As a result we adopt the second option and behave as per access
control via data filtering. For SPARQL update queries, three distinct query
rewriting strategies are required.

#### DELETE, INSERT, DELETE/INSERT.

As the DELETE/INSERT operation uses graph patterns in order to determine the
data to be inserted, deleted or updated, the query rewriting strategy proposed
in _Section_ 4.2 is used to filter out unauthorised data.

#### DELETE DATA and INSERT DATA.

Given, that the DELETE DATA and the INSERT DATA operations are used to delete
and insert specific data, any quads matching an unauthorised quad pattern need
to be removed from the query. The query presented in _Query_ 5 is used to
delete all data relating to Joe Bloggs and May Ryan from the
entx:EmployeeDetails graph.

######  Query 5 (DELETE authorised data ).

Given the following query:

⬇

DELETE WHERE { GRAPH entx:EmployeeDetails {

entx:JBloggs rdf:type foaf:Person.

entx:JBloggs foaf:name "Joe Bloggs" .

entx:JBloggs entx:salary 60000 .

entx:MRyan rdf:type foaf:Person .

entx:MRyan foaf:name "May Ryan" .

entx:MRyan entx:salary 33000 . } }

If authorisation 1 in _Figure_ 2 is used to prohibit the requester from
deleting May Ryan’s salary, the query is rewritten as follows:

⬇

DELETE WHERE { GRAPH entx:EmployeeDetails {

entx:JBloggs rdf:type foaf:Person.

entx:JBloggs foaf:name "Joe Bloggs" .

entx:JBloggs entx:salary 60000 .

entx:MRyan rdf:type foaf:Person .

entx:MRyan foaf:name "May Ryan" . } }

After the rewritten query is executed over the dataset presented in _Figure_
1, the new state of the dataset is as follows:

⬇

1entx:EmployeeDetails{

2entx:JSmyth rdf:type foaf:Person .

3entx:JSmyth foaf:name "John Smyth" .

4entx:JSmyth entx:salary 33000 .

5entx:MRyan entx:salary 33000 . }

6entx:OrgStructure{

7entx:MRyan entx:worksFor entx:JBloggs .

8entx:JSmyth entx:worksFor entx:MRyan . }

#### Graph based update operations.

As the CLEAR, DROP, ADD, LOAD, COPY and the MOVE operations work at the graph
level, when the requester does not have access to the entire graph these
queries need to be rewritten so that they operate at the triple level. For
example the CLEAR operation removes all of the data from a target graph. When
the requester does not have access to the entire graph, the DELETE operation
can be used to only remove authorised data. _Query_ 6 demonstrates how the
CLEAR operation can be represented using a DELETE operation.

######  Query 6 (CLEAR authorised data ).

Given the following query:

⬇

CLEAR GRAPH entx:EmployeeDetails

If authorisation 1 in _Figure_ 2 is used to prohibit the requester from
clearing salary information pertaining to entx:MRyan, the query is rewritten
as follows:

⬇

DELETE { GRAPH entx:EmployeeDetails { ?s ?p ?o } }

WHERE { GRAPH entx:EmployeeDetails { ?s ?p ?o

FILTER NOT EXISTS { GRAPH entx:EmployeeDetails {?s ?p ?o

FILTER (?s = entx:MRyan && ?p = entx:salary ) } } } }

After the rewritten query is executed over the dataset presented in _Figure_
1, the new state of the dataset is as follows:

⬇

1entx:EmployeeDetails{

2entx:MRyan entx:salary 33000 . }

3entx:OrgStructure{

4entx:MRyan entx:worksFor entx:JBloggs .

5entx:JSmyth entx:worksFor entx:MRyan . }

###  4.4 Update Rewriting Algorithm

Based on the query rewriting strategies presented in the previous section, we
propose an update query rewriting algorithm, which ensures that only
authorised data is inserted and deleted. The algorithm takes as input a query,
and a set of quads that need to be filtered out of the query results. In the
case of:

  1. (i)

DELETE/INSERT. The query rewriting algorithm presented in _Section_ 4.2 is
used to filter out unauthorised quad patterns.

  2. (ii)

DELETE DATA and INSERT DATA. If any of the quads in the query match an
unauthorised quad pattern these quads are removed from the query.

  3. (iii)

CLEAR and DROP. Negative authorisations pertaining to the specified graph are
added as filters to a DELETE query, which is used to ensure that only
authorised data is removed from the graph.

  4. (iv)

ADD and LOAD. Negative authorisations relating to the source and the
destination graphs are added as filters to an INSERT query, which is used to
add/load only authorised data to the destination graph.

  5. (v)

COPY. A DELETE query which is constructed using negative authorisations
matching the destination graph, is used to remove all data from the
destination graph. While negative authorisations matching the source and the
destination graphs are added as filters to an INSERT query, which is used to
copy only authorised data into the destination graph.

  6. (vi)

MOVE. The rewriting strategy for the MOVE operation is the same as the COPY
operation with an additional DELETE query, constructed using negative
authorisations matching the source graph, which is subsequently used to remove
authorised data from the source graph.

##  5 Query Rewriting Evaluation

In _Section_ 3 we formally defined a set of correctness criteria that can be
used to compare access control via query rewriting against access control via
data filtering. In this section, we demonstrate how the proposed correctness
criteria can be used to verify the effectiveness of alternative query
rewriting proposals. Given that SPARQL query results are dependent on pattern
matching and filtering, in order to prove the correctness of a query rewriting
strategy we only have to show it works for all $2^{4}$ possible combinations
of quad patterns for each of the SPARQL 1.1 query types presented in _Section_
4.1 and _Section_ 4.3. Both the size of the dataset and the data itself are
irrelevant. The entire system (test data generator, query rewriting algorithm
and model checking algorithm) is implemented in Java, and the query evaluation
is performed over an in memory store using Jena. The Berlin SPARQL Benchmark
(BSBM) dataset generator is used to generate a dataset containing 1194 quads.
The dataset, queries and authorisations used in the experiments described in
this paper can be found at http://correctness.sabrinakirrane.com/.

###  5.1 Evaluation of SPARQL Query Rewriting

In order to evaluate the different query rewriting strategies we
systematically generate authorisations and queries from our auto generated
dataset.The following algorithm is used to evaluate each of the auto generated
queries:

  1. (i)

Firstly, the unauthorised quad pattern is used to remove unauthorised data,
and the query is executed against the resulting authorised dataset.

  2. (ii)

Secondly, the unauthorised quad pattern is used to rewrite the query based on
the query rewriting algorithm and this rewritten query is executed over the
dataset which contains both authorised and unauthorised data.

  3. (iii)

Finally, the results of both approaches are compared using the criteria
presented in _Section_ 3.1.

#### Existing query rewriting algorithms.

Both Chen and Stuckenschmidt [2] and Oulmakhzoune et al. [10] use filters to
bind/unbind query solutions based on access control policies that are
associated with _classes, properties_ or _individuals_. Although the authors
propose query rewriting strategies for both positive and negative
authorisations our evaluation focuses on negative authorisations.

  * •

Chen and Stuckenschmidt [2] use a FILTER != expressions to remove bindings for
unauthorised individuals. Whereas OPTIONAL {?s ?p ?o. FILTER (?p=R)}  is used
to filter matches for a named relation R and OPTIONAL {?s rdf:type ?o.
FILTER(?o=C)} FILTER(!BOUND (?o)) is used to filter out matches for a named
class C.

  * •

Oulmakhzoune et al. [10] also use FILTER != expressions to remove bindings for
specific individuals. However, according to their rewriting strategy if access
is restricted to the entire triple pattern then the triple pattern is removed.
Whereas, if access is partially restricted then the triple pattern is
converted to an optional OPTIONAL pattern and the FILTER expression is added
to the optional pattern.

As both query rewriting strategies are based on triples as opposed to quads,
in order to evaluate we systematically generate authorisations from all
$2^{3}$ possible combinations (of constants and variables) for each quad in
the auto generated dataset (the graph is always a variable). As the authors
focus on BGPs, we auto generated queries, composed of either one, two or three
RDF quad patterns that are randomly generated from the dataset, for each
authorisation.

As the query rewriting strategies proposed by Chen and Stuckenschmidt [2]
relies on binding/unbinding constants in the authorisation to variables in the
query, when the restricted class, property or individual appears as a constant
in the query, it is not possible to generate a binding. In such instances
their respective query rewriting strategies fail to satisfy the secure, sound
and maximum criteria. Whereas, according to the rewriting strategy proposed by
Oulmakhzoune et al. [10], when access is prohibited to predicates or objects,
the relevant triple patterns are made OPTIONAL, which changes the semantics of
the query. Although the query does not return any unauthorised data both the
sound and maximum criteria are violated.

#### Our query rewriting algorithm.

For each RDF quad in the BSBM dataset, we generate $2^{4}$ authorisations,
resulting in a total of 19104 authorisations. As SAMPLE returns different data
each time it is executed it is not possible to compare query rewriting to
results filtering. Therefore, for each of the authorisations eleven queries
are generated as follows:

  * •

Basic Graph Patterns. A query is generated, which contains either one, two or
three RDF quad patterns, that are randomly generated from data selected from
the entire dataset.

  * •

Aggregates. For COUNT and GROUP_CONCAT operations, queries are also generated
from up to three RDF quad patterns that randomly generated from the entire
dataset. Given SUM, MIN, MAX and AVG operations are dependent on numeric data,
these queries are generated from a quad pattern which matches all offers (_?s_
rdf:type bsbm:offer _?g_) together with a pattern that matches the associated
delivery days (_?s_ bsbm:deliveryDays _?o_ _?g_).

  * •

Subqueries and Filters. A pattern with all variables is added to the outer
query, and the inner SELECT, MINUS, FILTER EXISTS and FILTER NOT EXISTS are
generated from either one, two or three RDF quad patterns, which are randomly
selected from the entire dataset.

In the case of basic graph patterns, aggregates and negation, each of the
queries generated from the BSBM dataset were deemed secure, sound and maximum.
However, in the case of property paths, given a FILTER NOT EQUALS does not
restrict access to the path data, in some instances the algorithm failed to
satisfy all three criteria. If we remove the FILTER = binding, the query
rewriting strategy is both secure and sound, however it is not maximum. As
such, further analysis is required in order to determine a rewriting strategy
for property paths.

###  5.2 Evaluation of SPARQL Update Rewriting

For SPARQL updates,the following algorithm is used to evaluate each of the
auto generated queries:

  1. (i)

Firstly, the unauthorised quad pattern is used to create a dataset which only
contains authorised data and a dataset which only contains unauthorised data.
The query is subsequently executed against the authorised dataset and both the
unauthorised dataset and the updated authorised dataset are merged to form a
new merged filtered dataset. In the case of INSERT DATA unauthorised triples
need to be removed from the query before it is executed over the authorised
dataset. In such instances the filtering approach is quite similar to the
rewriting approach.

  2. (ii)

Secondly, the quad pattern is used to rewrite the query and this rewritten
query is executed over the original dataset.

  3. (iii)

Finally, the results of both approaches are compared using the criteria
presented in _Section_ 3.2.

#### Our update rewriting algorithm.

The query rewriting strategy for LOAD is identical to that for the ADD
operation and no rewriting strategy is required for CREATE as access is either
granted or denied. Therefore, for each of the authorisations we generate ten
different queries as follows:

  * •

Delete Data and Insert Data. For DELETE DATA and INSERT DATA, queries are
generated from one, two or three RDF quads, that are randomly selected from
the entire dataset.

  * •

Delete, Insert and Delete/Insert. As per basic graph patterns, DELETE, INSERT
and DELETE/INSERT queries are generated from graph patterns that are randomly
selected from the entire dataset.

  * •

Graph Update Operations. CLEAR, DROP, ADD, COPY and MOVE queries are generated
for each graph appearing in the dataset.

As each of the update queries, that were generated from the BSBM dataset, were
deemed secure, sound and maximum, we can conclude that the update query
processing algorithm is secure, sound and maximum.

##  6 Conclusion and Future Directions

Although the technology to link web data with other relevant data using
machine-readable formats has been in existence for a number of years, in order
to support the next generation of eBusiness applications on top of Linked Data
appropriate security and privacy mechanisms need to be put in place. When it
comes to access control via query rewriting, existing proposals do not
consider complex queries that include negation and subqueries, and to the best
of our knowledge there is currently no query rewriting strategy for update
queries. Also, to date researchers have focused on performance evaluations, as
opposed to verifying the correctness of the proposed access control
mechanisms.

In this paper, we proposed a query rewriting strategy for both the SPARQL 1.1
queries and updates. We redefined a set of criteria, which was originally used
to verify that an access control policy holds over different database states,
to allow for access control via query rewriting to be compared against access
control via results filtering. We subsequently used the adapted correctness
criteria to evaluate the proposed query rewriting algorithms. In future work
we plan to devise an appropriate query rewriting strategy for property paths.
Based on our initial performance evaluation, which is not presented in the
paper, it is evident that FILTER NOT EXISTS can be expensive. As such, we plan
to investigate query optimisation techniques for the different SPARQL 1.1
query types and to publish a benchmark that can be used to assess alternative
access control strategies.

## References

  * Abel et al. [2007] Fabian Abel, JuriLuca De Coi, Nicola Henze, ArneWolf Koesling, Daniel Krause, and Daniel Olmedilla.  Enabling advanced and context-dependent access control in rdf stores.  In _The Semantic Web_ , volume 4825 of _Lecture Notes in Computer Science_ , pages 1–14. Springer Berlin Heidelberg, 2007.
  * Chen and Stuckenschmidt [2010] W. Chen and H. Stuckenschmidt.  A model-driven approach to enable access control for ontologies.  _Business Services: Konzepte, Technologien, Anwendungen: Wirtschaftsinformatik 2009_ , pages 663–672, 2010.
  * Costabello et al. [2012] Luca Costabello, Serena Villata, Nicolas Delaforge, and Fabien Gandon.  Linked data access goes mobile: Context-aware authorization for graph stores.  In _LDOW - 5th WWW Workshop on Linked Data on the Web_ , 2012.
  * Dietzold and Auer [2006] Sebastian Dietzold and Soren Auer.  Access control on rdf triple stores from a semantic wiki perspective.  In _Proceedings of the ESWC’06 Workshop on Scripting for the Semantic Web_ , 2006.
  * Franzoni et al. [2007] S. Franzoni, P. Mazzoleni, S. Valtolina, and E. Bertino.  Towards a fine-grained access control model and mechanisms for semantic databases.  In _Web Services, 2007. ICWS 2007. IEEE International Conference on_ , pages 993–1000, July 2007.
  * Heath and Bizer [2011] Tom Heath and Christian Bizer.  _Linked data: Evolving the web into a global data space_ , volume 1.  Morgan & Claypool Publishers, 2011.
  * Li and Cheung [2008] Jian Li and WilliamK. Cheung.  Query rewriting for access control on semantic web.  In Willem Jonker and Milan Petković, editors, _Secure Data Management_ , volume 5159 of _Lecture Notes in Computer Science_ , pages 151–168. Springer Berlin Heidelberg, 2008.  ISBN 978-3-540-85258-2.
  * Muhleisen et al. [2010] Hannes Muhleisen, Martin Kost, and Johann-Christoph Freytag.  SWRL-based Access Policies for Linked Data.  In _Proceedings of the Second Workshop on Trust and Privacy on the Social and Semantic Web (SPOT2010)_ , 2010.
  * O’Hara et al. [2013] Kieron O’Hara, Noshir S Contractor, Wendy Hall, James A Hendler, and Nigel Shadbolt.  Web science: understanding the emergence of macro-level features on the world wide web.  _Foundations and Trends in Web Science_ , 4(2-3), 2013.
  * Oulmakhzoune et al. [2010] Said Oulmakhzoune, Nora Cuppens-Boulahia, Frédéric Cuppens, and Stephane Morucci.  fquery: Sparql query rewriting to enforce data confidentiality.  In Sara Foresti and Sushil Jajodia, editors, _Data and Applications Security and Privacy XXIV_ , volume 6166 of _Lecture Notes in Computer Science_ , pages 146–161. Springer Berlin Heidelberg, 2010.
  * Oulmakhzoune et al. [2012] Said Oulmakhzoune, Nora Cuppens-Boulahia, Frederic Cuppens, and Stephane Morucci.  Privacy policy preferences enforced by sparql query rewriting.  In _Availability, Reliability and Security (ARES), 2012 Seventh International Conference on_ , pages 335–342. IEEE, 2012.
  * Wang et al. [2007] Qihua Wang, Ting Yu, Ninghui Li, Jorge Lobo, Elisa Bertino, Keith Irwin, and Ji-Won Byun.  On the correctness criteria of fine-grained access control in relational databases.  In _Proceedings of the 33rd International Conference on Very Large Data Bases_ , VLDB ’07, pages 555–566. VLDB Endowment, 2007.


marginparsep has been altered.
topmargin has been altered.
marginparpush has been altered.
The page layout violates the ICML style. Please do not change the page layout,
or include packages like geometry, savetrees, or fullpage, which change it for
you. We’re not able to reliably undo arbitrary changes to the style. Please
remove the offending package(s), or layout-changing commands and try again.

Discovering User Types: Mapping User Traits by Task-Specific Behaviors in
Reinforcement Learning

Lars L. Ankile * 1  Brian S. Ham * 1  Kevin Mao 1  Eura Shin 1  Siddharth
Swaroop 1  Finale Doshi-Velez 1  Weiwei Pan 1

††footnotetext: *Equal contribution 1Harvard University, Cambridge MA, USA.
Correspondence to: Lars L. Ankile<EMAIL_ADDRESS>
Workshop paper at the $\mathit{40}^{th}$ International Conference on Machine
Learning, Honolulu, Hawaii, USA. 2023. Copyright 2023 by the author(s).

###### Abstract

When assisting human users in reinforcement learning (RL), we can represent
users as RL agents and study key parameters, called _user traits_ , to inform
intervention design. We study the relationship between _user behaviors_
(policy classes) and user traits. Given an environment, we introduce an
intuitive tool for studying the breakdown of “user types”: broad sets of
traits that result in the same behavior. We show that seemingly different
real-world environments admit the same set of user types and formalize this
observation as an equivalence relation defined on environments. By
transferring intervention design between environments within the same
equivalence class, we can help rapidly personalize interventions.

##  1 Introduction

Mobile Health (mHealth) applications, like a physical therapy (PT) app that
recommends personalized exercises to a user working to regain ankle mobility,
are gaining popularity as cost-effective interventions. In these applications,
personalization can be achieved by inferring the user-specific internal
obstacles to reaching health targets, then designing treatments for those
obstacles Shin et al. (2022). In this paper, we provide a set of novel tools
for studying the relationship between user-specific obstacles and user
behavior, thereby generating insights for treatment design.

We model user-internal obstacles as discrepancies between the real-world
environment, formalized as a Markov Decision Process (MDP), and the user’s
perceived environment, another MDP. We want the user, as a Reinforcement
Learning (RL) agent, to adopt a target policy in the real-world environment
(e.g., perform recommended daily exercises until full recovery), but since the
user plans in their perceived environment, their perceived optimal policy can
deviate drastically from the target (e.g., prematurely terminate the PT
program due to the perceived infeasibility of full recovery).

For a real environment, we characterize the user-perceived environments using
MDP parameters that map to well-studied human traits—which we call _user
traits_ —in the behavioral sciences. In particular, for many mHealth
applications, a user’s confidence in their physical capabilities and their
ability to perform long-term planning (their degree of myopia) both
significantly impact their success in prescribed fitness regimens (Picha et
al., 2021b). In our work, we model _myopia_ as the discount factor and
_confidence_ as the dynamics (specifically, the perceived probability of
positive outcomes) of the user’s MDP (Section 3).

Given a real environment, we introduce a tool for visualizing the relationship
between user traits (the user’s MDP parameters) and the corresponding user
behavior (the user’s possible policies). Specifically, within the environment,
we study the breakdown of “user types”—regions in the space of all possible
user traits that define the same user behavior—and visualize these types as
two-dimensional behavior maps (Section 4). Behavior maps shed light on the
extent to which it is possible to infer user traits by observing user
behavior.

Finally, we show that seemingly different real-world environments admit the
same behavior maps. We formalize this observation as an equivalence relation
defined on real-world environments (Section 5). We map several environments
commonly used in the RL literature (that also model mHealth tasks) to just a
small set of equivalence classes, where the sets of user behaviors are similar
across different environments within each class (Section 6.2). This result
allows us to provide guidelines on intervention design in various complex
environments by lifting insights from an equivalent and simpler toy
environment (Section 6.4).

##  2 Related Work

#### Inferring a user’s parameters from demonstrations.

Like us, some works (Evans et al., 2016; Shah et al., 2019; Zhi-Xuan et al.,
2020) model humans as RL agents with different perceived MDPs. However,
inferring an agent’s MDP parameters from demonstration is a difficult and
nonidentifiable problem (Shah et al., 2019). This paper shows that, while user
parameters cannot be exactly recovered from behavior data in most settings, we
can infer general rules about the relationship between user parameters and
user behavior. These rules can help us design mHealth interventions.

#### Equivalence in Inverse RL (IRL).

In IRL, when parameters of an MDP cannot be uniquely identified, we infer
classes of these parameters, typically rewards (Ziebart, 2010) or transitions
functions (Reddy et al., 2018; Golub et al., 2013), that are equally likely
under the behavior data provided by _one_ user. In this work, we study the
behaviors of _multiple users_ and equate different environments (MDPs) in
which the partitioning of the set of users by behavior is similar.

#### Equivalence of MDPs.

Notions of equivalence between MDPs allow for knowledge transfer between
different environments (Soni & Singh, 2006; Sorg & Singh, 2009). For example,
bisimulation-based equivalence definitions are used in MDP minimization, where
large state spaces are reduced to speed up planning (Givan et al., 2003).
Relaxed versions of bisimulations, e.g., MDP homomorphism (Biza & Platt,
2018), stochastic homomorphism (van der Pol et al., 2020), and approximate
homomorphisms (Ravindran & Barto, 2004) allow optimal policies in simple MDPs
to be lifted to desirable policies in more complex and comparable MDPs. More
general definitions of MDP equivalence can be defined through other methods of
state aggregation (e.g., value equivalence) Li et al. (2006). While these
notions of equivalence are defined over the set of MDPs, we decompose an MDP
into task-specific and user-specific components and consider equivalences
between the task-specific components of MDPs while varying the user-specific
ones.

##  3 Formalizing Users as RL Agents

We formalize an RL environment for an mHealth application as a Markov Decision
Process (MDP). An MDP is a 5-tuple,
$\mathcal{M}=\langle\mathcal{S},\mathcal{A},T,R,\gamma\rangle$, consisting of
a set of states $\mathcal{S}$, a set of actions $\mathcal{A}$, a reward
function $R:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\to\mathbb{R}$, a
transition function $T:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\to[0,1]$
and a discount rate $\gamma\in[0,1]$. For simplicity, in this paper, we only
consider discrete state spaces.

An optimal RL agent acts in $\mathcal{M}$ according to a policy
$\pi_{\mathcal{M}}:\mathcal{S}\rightarrow\mathcal{A}$, giving a cumulative
reward (expected returns):
$J^{\pi}_{\mathcal{M}}=\mathbb{E}\left[\sum\limits_{t=0}^{T}\gamma^{t}r_{t}\right]$,
where $r_{t}$ is the random variable representing the reward received at time
$t$. The optimal policy for $\mathcal{M}$ maximizes the expected returns:
$\pi^{*}_{\mathcal{M}}=\max\limits_{\pi}J^{\pi}$.

We want the user to adopt the optimal policy $\pi^{*}_{\mathcal{M}}$ in
$\mathcal{M}$. However, the user plans in their perceived environment,
$\mathcal{M}^{\text{user}}=\langle\mathcal{S}^{\text{user}},\mathcal{A}^{\text{user}},T^{\text{user}},R^{\text{user}},\gamma^{\text{user}}\rangle$
and adopts the policy, $\pi^{*}_{\mathcal{M}^{\text{user}}}$, that is optimal
for $\mathcal{M}^{\text{user}}$. Discrepancies between the real environment
and the user’s perceived one can lead to drastic differences between the
target policy, $\pi^{*}_{\mathcal{M}}$, and the adopted one,
$\pi^{*}_{\mathcal{M}^{\text{user}}}$.

In this work, we shall assume that the perceived environment differs from the
real only in the transition function (modeling the user trait confidence) and
the discount rate (modeling the user trait myopia). Specifically, we define a
_world_ as a tuple $\mathcal{W}=\langle\mathcal{S},\mathcal{A},R\rangle$ of
states $\mathcal{S}$, actions $\mathcal{A}$, and reward function $R$. This
captures the real environment and the task in an application of interest (see
Fig. 2 for example-grid worlds). Since the user’s perceived states, actions,
and rewards match the real environment, we set
$\mathcal{S}^{\text{user}}=\mathcal{S}$,
$\mathcal{A}^{\text{user}}=\mathcal{A}$ and $R^{\text{user}}=R$.

Furthermore, since we are interested in the set of optimal policies generated
by varying the user’s perceived environment $\mathcal{M}^{\text{user}}$, we do
not keep track of the real transition function $T$ and the real discount rate
$\gamma$. Instead, the user’s policy depends only on their (fixed) perception
of the environment, $T^{\text{user}}$, and their (fixed) discount rate
$\gamma^{\text{user}}$. The real $T$ is useful only when the user is learning
(updating $T^{\text{user}}$) based on data generated by $T$.

We use $\gamma^{\text{user}}\in[0,1]$ to represent the user’s level of
_myopia_. To represent the level of _confidence_ , we parameterize the user’s
transition $T^{\text{user}}_{p}$ function with $p\in[0,1]$, which is the level
of stochasticity in the environment transitions that the user perceives. Other
parameterizations of $T^{\text{user}}$ are possible, but this one aligns with
the intuition that a user with low confidence is unsure whether their actions
$a\in\mathcal{A}^{\text{user}}$ will lead to desired outcomes
$s^{\prime}\in\mathcal{S}^{\text{user}}$.

In Section 4, we model how and why users with distinct traits behave
differently (i.e., adopt different policies) in the same real-life setting.
For example, two people with different levels of myopia would judge different
PT behaviors to be optimal in their respective MDPs. However, we first connect
our formalization of user traits (their level of myopia
$\gamma^{\text{user}}$, and their confidence level $p$ parameterizing
$T^{\text{user}}_{p}$) to well-studied constructs in psychology and behavioral
science.

#### Mapping RL to Behavior Science.

_Myopia_ corresponds to the concept of temporal discounting in psychology. In
user MDPs, we represent temporal discounting with
$\gamma^{\text{user}}\in[0,1)$. This captures people’s tendency to undervalue
future rewards, often leading to unhealthy behavior (Story et al., 2014).
However, we note that in RL, discounting is exponential by default, which does
not capture the phenomenon observed in humans called preference reversal
Ainslie & Haslam (1992); Shah et al. (2019) (which hyperbolic discounting is
more suited for).

In behavioral science, _confidence_ , also known as self-efficacy, measures an
agent’s belief in their capability to perform a task Picha et al. (2021a).
Intuitively, this is the user’s perceived probability that their intended
outcome can be achieved through action. In user MDPs, we represent the user’s
confidence level with $p\in[0,1]$, which is the level of stochasticity in the
transitions. Concretely, $T^{\text{user}}_{p}(s,a,s^{\prime})=p$ for a user’s
intended outcome $s^{\prime}$ from performing action $a$ in state $s$. We
divide the remaining $1-p$ probability equally among the alternate outcomes:
$T^{\text{user}}(s,a,\hat{s}^{\prime})=\frac{1-p}{|\hat{\mathcal{S}}|}$. Our
current instantiation of confidence is simple, and it is equivalent to adding
epsilon-noise to the real-world transition matrix. However, the transition
$T^{\text{user}}_{p}$ can be a function of $p$ in more complex ways.

Figure 1: Example behavior map (Big-Small world). The two colors indicate the
two possible behaviors (see Fig. 2(c) for the world and the behaviors).
Annotations describe the procedure for deriving the equivalence class. The
x-axis varies over the discounting factor, $\gamma$; the y-axis varies over
the confidence level, $p$. “Extreme” users, i.e., corners of the map, are
labeled as circles. The number of “behavior switches” when tracing each edge
between extreme users (from A to B, to C, to D, and back to A) are labeled as
squares.

##  4 Behavior Maps: A Tool for Understanding User Traits and User Behaviors

In the previous section, we formalized the user’s MDP
$\mathcal{M}^{\text{user}}$ and their optimal policy $\pi^{*}_{\text{user}}$.
We now introduce behavior maps, a tool for studying the relationship between
the user-specific parameters ($T^{\text{user}}_{p}$, $\gamma^{\text{user}}$)
and the corresponding optimal user policy $\pi^{*}_{\text{user}}$.

Given a world $\mathcal{W}$, we denote the set of possible (deterministic)
policies, $\pi:\mathcal{S}\to\mathcal{A}$, as $\Pi_{\mathcal{W}}$. We note
that in many real-life applications, distinct policies may functionally
describe the same type of behavior (e.g., if we are interested in overall
adherence, skipping PT exercises every Tuesday can be considered functionally
equivalent to skipping every Monday). Thus, we work with a concept that
generalizes the notion of policy; we define a “ _user behavior_ ”, denoted
$B\subset\Pi_{\mathcal{W}}$, as a set of policies considered _equivalent_ in
the application domain. We study how differences in user traits lead to
different user behaviors.

To do this, we introduce a _behavior map_ of the world $\mathcal{W}$ as a
mapping of user traits to the corresponding user behaviors in $\mathcal{W}$.
That is, the behavior map $\mathcal{B}_{\mathcal{W}}$ maps
$(\gamma^{\text{user}},p)$ to the user behavior $B$ that contains the optimal
policy for the user MDP
$\mathcal{M}_{\text{user}}=\langle\mathcal{S},\mathcal{A},\mathcal{R},T^{\text{user}}_{p},\gamma^{\text{user}}\rangle$.

In Fig. 1, we show an example of a behavior map. We see that it classifies the
user parameter space into regions where parameters map to the same user
behavior. In this world, there are only two behaviors (indicated by color),
and the user’s behavior depends on the value of their user traits (the two
axes).

#### Applications of Behavior Maps.

We demonstrate that behavior maps can inform the design and deployment of
interventions on user traits (for example, interventions to increase
$\gamma^{\text{user}}$). Specifically, they can help us (1) determine to what
extent user traits are identifiable through behavioral observations; (2) warm-
start an intervention strategy for interacting with new users.

#### Identifiability of User Traits.

Since behavior maps tell us which set of parameters gives the same user
behavior, they allow us to anticipate the limits of what we can infer about a
user (using Inverse Reinforcement Learning (IRL) or related methods) by
observing their behavior in a given world. For example, in worlds with the
behavior map in Fig. 1, we can distinguish between users with low and high
discount factors because users have different optimal policies (different
colors). On the other hand, the difference in confidence does not generally
correspond to a difference in behavior. Therefore, we cannot generally
distinguish between users with different confidence levels. However, we find
that behavior maps can inform intervention design, even when the parameters of
individual users cannot be exactly inferred.

#### Warm-start Intervention Strategy.

Given a world and a new user, behavior maps can help identify interventions
that, a priori, is likely to be more impactful. In particular, the more
variation there is in user behavior along a given axis, the more likely an
intervention on the corresponding trait will change the user’s behavior. For
example, in Fig. 1, we know that an intervention on $\gamma^{\text{user}}$ is
more likely to change the user’s behavior than an intervention on
$T_{p}^{\text{user}}$.

Although useful, directly computing the behavior map for a complex application
such as PT requires solving user MDPs for a range of user parameters and can
thus be computationally costly. Instead, to get the same insights, we reduce
the PT world $\mathcal{W}$ to a simpler toy world $\mathcal{W}^{\prime}$, for
which we can easily compute $\mathcal{B}_{\mathcal{W^{\prime}}}$. We define an
equivalence relation that allows us to make this reduction.

##  5 A Behavior-Based Equivalence Relation

This section uses behavior maps to draw analogies between seemingly different
worlds.

Suppose that two different applications, such as PT and dieting, have the same
behavior map, such as the one from Fig. 1. Then, in both applications, we know
that confidence does not impact user behavior and that users with “low” gamma
have one behavior, while users with “high” gamma have another. In this way, we
consider PT and dieting equivalent worlds because intervention design
principles can be transferred from one to the other. For example, in both
cases, the initial intervention strategy should focus on
$\gamma^{\text{user}}$ instead of $T_{p}^{\text{user}}$. Note that this
transfer can work in cases where the state and action spaces differ between
the two applications because the behavior maps depend on _high-level
behaviors_ (not exact states and actions). For example, in PT, the behaviors
may be a set of exercises. In dieting, the behaviors may be a set of food
choices. In either case, there is a desired behavior (e.g., choosing
nutritious foods or choosing the right exercises) and an undesired behavior.
We are only concerned with what interventions will help the user go from
undesired to desired behaviors, not that the actions defining those behaviors
match exactly.

Moreover, we can transfer between worlds with similar but not necessarily
identical behavior maps. For example, we might see that both PT and dieting
have two possible behaviors, where users with lower $\gamma^{\text{user}}$ act
differently from users with higher $\gamma^{\text{user}}$. However, what is
considered to be “low” or “high” $\gamma^{\text{user}}$ need not match exactly
between the two applications: in PT, the range for “low”
$\gamma^{\text{user}}$ could be $[0,0.3]$ and in dieting the range could be
$[0,0.2]$. If we knew both applications had similar behavior maps, we could
still transfer the knowledge that the initial intervention strategy should
focus on $\gamma^{\text{user}}$ instead of $T_{p}^{\text{user}}$. We could
also transfer the knowledge that users with different $\gamma^{\text{user}}$
are identifiable, while users with different $T_{p}^{\text{user}}$ are not.

###  5.1 Equivalence Between Behavior Maps

Thus motivated, we call two behavior maps equivalent if the _shapes_ of the
decision boundaries between user behaviors in the behavior maps are the same
and use an equivalence definition invariant to stretching or translation of
these boundaries. We formalize this in Definition 5.1.

(a) A $6\times 5$ Wall world where agents can pass directly through a costly
wall (orange) or take the longer, safer path around it (blue).

(b) A $4\times 8$ Cliff world where agents can walk close to the cliff and
risk ruin (blue) or keep space but walk farther (orange).

(c) A $5\times 5$ Big-Small world where agents can walk straight down to a
small reward (orange) or farther to a bigger reward (blue).

Figure 2: Each atomic world has two qualitatively distinct behaviors (shown
with blue and orange arrows). Each diagram shows what the world looks like for
one setting of the parameters, and other sizes are usually also valid.

In the following, we assume, without loss of generality, that the axes of each
behavior map $\mathcal{B}_{\mathcal{W}}$ is scaled to the unit interval, that
is, $\mathcal{B}_{\mathcal{W}}$ is a map over $I^{2}$, where $I=[0,1]$. Thus,
the decision boundary classifying different user behaviors in
$\mathcal{B}_{\mathcal{W}}$ is a 1-dimensional submanifold in $I^{2}$ defined
by the map $g_{\mathcal{W}}:[0,1]\to I^{2}$ satisfying some additional
constraints. Although we consider the case where the decision boundary is
connected here, our definition extends straightforwardly to cases where it is
not.

######  Definition 5.1 (World Equivalence Induced by Behavior Map).

We define an equivalence relation, $\equiv_{\mathrm{map}}$, on the set of
discrete worlds $\mathfrak{W}$ by

$\mathcal{W}\equiv_{\mathrm{map}}\mathcal{W}^{\prime},\quad\mathcal{W},\mathcal{W}^{\prime}\in\mathfrak{W}$

when (1) the number of behaviors in $\mathcal{B}_{\mathcal{W}}$ and
$\mathcal{B}_{\mathcal{W}^{\prime}}$ are equal, and (2) there is a continuous
map $h:I^{2}\times[0,1]\to I^{2}$, such that $h_{t}:I^{2}\times\\{t\\}\to
I^{2}$ is bijective, where $h_{0}$ is the identity map, and where $h_{1}$
satisfies $h_{1}\circ g_{\mathcal{W}}=g_{\mathcal{W}^{\prime}}$.

Note that we can simply say that $h$ is an _ambient isotopy_ between the
decision boundaries in $\mathcal{W}$ and $\mathcal{W}^{\prime}$.

The idea behind Definition 5.1 can be made more intuitive. We consider each
behavior map as a diagram in which (i) $n_{i}$ number of vertices (each
representing a switch between behaviors) is placed on the $i$-th edge, and
where (ii) each pair of vertices is connected by a curve defined by a decision
boundary that separates two user behaviors (see Fig. 1). We say that two maps
are equivalent if they are labeled by the same number of distinct behaviors,
and, as diagrams, they are topologically equivalent: the decision boundary in
one behavior map can be continuously deformed, by using the map $h$, to look
like that in the other.

For the set of worlds studied in this work, we note that whether two worlds
are equivalent boils down to counting the number of behavior switches along
the edges of their behavior maps (counterclockwise, starting from the bottom
edge). We can focus exclusively on the edges because our worlds do not induce
behavior maps with decision boundaries that behave differently in the middle
(e.g. Fig. 19). By counting the number of behavior switches along the edges,
we can represent the set of worlds in the same equivalence class as a count
vector (see Fig. 1).

###  5.2 Intervention Transfer Between Equivalent Worlds

Recall that our primary motivation for defining an equivalence relation on
worlds is to develop intervention strategies in simple settings and transfer
them to more complex analogous ones. This section provides the formalism for
transferring interventions between equivalent worlds. In Section 6.1, we will
introduce a set of simple worlds to which many commonly studied RL
environments can be reduced through our equivalence.

Given a world $\mathcal{W}$, we represent a single _intervention_ on a user’s
myopia and confidence level as a real-valued pair
$(\Delta_{\gamma},\Delta_{p})\in I^{2}$ that is added to the user’s current
parameters. Thus, a sequence of interventions defines a (piece-wise linear)
path, which we call an _intervention strategy_ and denote by
$\tau_{\mathcal{W}}$, in the behavior map $\mathcal{B}_{\mathcal{W}}$. Our
goal is to map an intervention strategy $\tau_{\mathcal{W}}$ in
$\mathcal{B}_{\mathcal{W}}$, that realizes a behavior change, to a strategy
$\tau_{\mathcal{W}^{\prime}}$ in an equivalent map
$\mathcal{B}_{\mathcal{W}^{\prime}}$ that realizes an analogous behavior
change.

We first observe that the continuous map $h$ in Definition 5.1 induces a
mapping from the set of user parameters related to one world $\mathcal{W}$ to
the user parameters related to $\mathcal{W}^{\prime}$, defined by
$h_{1}:I^{2}\to I^{2}.$ Hence, every path $\tau_{\mathcal{W}}$ defines a path
$\tau_{\mathcal{W}^{\prime}}=h_{1}\circ\tau_{\mathcal{W}}$. Since $h$
continuously deforms the decision boundary of $\mathcal{B}_{\mathcal{W}}$, it
preserves the number of times $\tau_{\mathcal{W}}$ intersects the decision
boundary in $\mathcal{B}_{\mathcal{W}}$. In particular, if
$\tau_{\mathcal{W}}$ represents an intervention strategy that achieves $N$
number of behavior changes in $\mathcal{B}_{\mathcal{W}}$, then
$\tau_{\mathcal{W}^{\prime}}$ is a strategy that achieves the same number of
behavior changes in $\mathcal{B}_{\mathcal{W}^{\prime}}$.

Note that, unlike knowledge generalization approaches in RL wherein one
computes a mapping between all parameters of two MDPs, our approach to
intervention transfer between two worlds by-passes explicit mappings between
the state and action sets of $\mathcal{W}$ and $\mathcal{W}^{\prime}$.
Instead, we rely on $h$, the mapping between user parameter and policy spaces.

In practice, explicitly computing $h$ can be difficult. In the next section,
we show that we can derive a more general set of heuristics for intervention
design in a complex world by reasoning about an equivalent simple world.

(a) _Wall world_ example behavior map belonging to equivalence class [2, 0, 2,
0].

(b) _Cliff world_ example behavior map belonging to equivalence class [1, 1,
0, 0].

(c) _Big-Small_ world example behavior map belonging to equivalence class [1,
0, 1, 0].

(d) _Chain world_ example behavior map belonging to equivalence class [1, 0,
1, 0].

(e) _RiverSwim world_ example behavior map belonging to equivalence class [1,
0, 1, 0].

(f) _Gambler’s Ruin world_ (varying $p_{C}$) example behavior map in
equivalence class [1, 0, 1, 0].

(g) _Gambler’s Ruin world_ (varying $p_{F}$) example behavior map in
equivalence class [1, 1, 0, 0].

(h) _Café world_ example behavior map belonging to equivalence class [1, 0, 1,
0].

Figure 3: Seemingly different worlds (bottom row) are equivalent to one of our
atomic worlds (top row).

Figure 4: A _Big-Small world_ stays within its equivalence class for many
different parameter combinations. The example behavior maps have different
values for the world width and the ratio of the small reward to the big
reward, while the rest of the parameters are fixed as height = 7 and Big far R
= 300.

##  6 Atomic Worlds: Simple Representatives of Equivalence Classes

Under Definition 5.1, we seek the simplest representative, called _atomic
worlds_ , for each equivalence class. User behaviors can be characterized in
atomic worlds, and the insights transferred thereafter to more complex
equivalent worlds. We describe three atomic worlds and reduce commonly studied
worlds in RL literature to our atomic worlds.

###  6.1 Atomic Worlds

We visualize an instance of each of the following worlds in Fig. 2 and their
corresponding behavior maps in Fig. 3.

The _Big-Small world_ is an atomic world that captures a trade-off between
choosing a smaller, more convenient reward and a bigger reward that is more
difficult to reach. In mHealth, this world reflects scenarios in which smaller
immediate rewards, such as the time saved by skipping PT for the day, preclude
larger but delayed rewards, such as a fully rehabilitated ankle.

The _Cliff world_ captures settings in which a harmful absorbing state may be
reached due to an action going awry. For example, deciding the intensity of
the PT regimen can be modeled as a Cliff world. A high-intensity regimen could
accelerate recovery but also risk re-injuring the patient.

The _Wall world_ captures the choice between a short, costly path to the goal
and a longer, free path to the same goal. This can model the trade-off in
choosing the type of physical therapy: virtual therapy may be more affordable,
while in-person therapy is more costly and targeted.

In the above, we note that different aspects of user decision-making (e.g.,
choosing the intensity vs choosing the type of therapy) in the same mHealth
application (PT), can map to different equivalence classes. We hypothesize
that more complex worlds (e.g., larger portions of the user decision-making
process in PT) can be captured by compositions of simpler atomic worlds. In
future work, we are interested in characterizing the set of complex worlds
that can be studied through decomposition into atomic worlds. Further
discussion can be found in Section 7 and Appendix C.

###  6.2 Atomic Worlds Capture Commonly Studied RL Environments

We compare the behavior maps corresponding to four types of RL environments
commonly studied in the literature: Chain, RiverSwim, Gambler’s Fallacy, and
Café worlds (details on each world are in Appendix A), and illustrate that the
set of worlds they define reduces to the three atomic worlds we identify in
Section 6.1. We note that these RL environments are diverse in their state and
action spaces; more interestingly, they are diverse in how they map to real-
life tasks. Thus, we expect that many useful mHealth applications can be
modeled by known atomic worlds or straightforward combinations of atomic
worlds (see Section 7 and Appendix C for more details), allowing us to
transfer intervention design from familiar, simpler settings onto unexplored
and more complex ones.

Under our definition, Chain (Fig. 3(d)), RiverSwim (Fig. 3(e)), Gambler’s
Fallacy V1 (Fig. 3(f)), and the Café worlds (Fig. 3(h)) are equivalent to the
Big-Small world (Fig. 3(c)); these are worlds in which the user chooses
between a readily available but small reward (i.e., disengaging in Chain,
swimming downstream in RiverSwim, and performing the _Finish_ action in the
Gambler’s Ruin world) and a greater but more time-consuming reward. Gambler’s
Fallacy V2 (Fig. 3(g)) is equivalent to Cliff World—both worlds have a
“catastrophic absorbing state,” i.e., a nonzero risk of ending up in a
terminal state with a negative reward.

###  6.3 The Equivalence Definition Is Robust to Parameter Perturbations in
World Definitions

We want a world to remain within its equivalence class despite minor parameter
adjustments (e.g., the world for a month-long PT program should be in the same
class as that for a 2-month program). This is evidence that our equivalence
definition captures essential rather than incidental qualities of
applications.

In Fig. 4, we verify that the Big-Small world remains within its equivalence
class despite parameter changes, such as the world’s width or the ratio of the
big to a small reward. In Appendix B, we provide additional evidence of how
our equivalence classes withstand perturbations across more parameters for all
$8$ worlds investigated.

###  6.4 Heuristics for Intervention Transfer

Many real-world applications may be roughly mapped to an atomic world through
domain knowledge rather than computing an explicit map $h$, as in Section 5.2.
For example, behavior scientists can often describe the types of expected user
behavior, e.g., “how many different behaviors are there for users with very
low confidence?”. Absent a map $h$, we cannot transfer an intervention
strategy in precise terms. However, the broader insights we obtain from
studying the behavior maps of atomic worlds can be easily transferred. For
example, conclusions we reach on the identifiability of user traits and the
effectiveness of a particular warm-start intervention strategy (see Section 4)
apply to all worlds within the same equivalence class.

##  7 Discussion & Future Work

#### Exhaustive World Search.

We expect there to be many equivalence classes outside the three identified in
this paper. The existence of such classes may be especially relevant when we
try to capture multiple distinct aspects of an mHealth application in a single
world. In future work, we intend to explore the space of possible equivalence
classes more exhaustively.

#### World Compositions.

Complex real-life scenarios are unlikely to neatly map to a singular atomic
world; however, we conjecture that some worlds may fall into compositions of
atomic worlds. Some initial experiments with composite worlds indicate that
the composition of the Big-Small and Cliff worlds leads to a behavior map that
combines the atomic worlds’ respective maps. See Appendix C for examples of
these experiments. This finding further supports the generality of our
equivalence classes as seemingly-complicated scenarios can be broken down into
atomic worlds that each capture a unique aspect of the application.

#### Other User-Intrinsic Obstacles.

While we focus on myopia ($\gamma^{\text{user}}$) and confidence
($T_{p}^{\text{user}}$) in this paper, we are interested in modeling a wider
range of user-intrinsic obstacles, as differences between the real and user-
perceived MDP. For motivation, works like Evans et al. (2016), under a
different model of the user’s decision-making process, capture behaviors that
cannot be parameterized as combinations of $\gamma^{\text{user}}$ and
$T_{p}^{\text{user}}$ in the Café world. This observation raises the question
of whether our formal framework can capture behaviors observed under other
paradigms of sequential decision-making (e.g. hyperbolic discounting,
replanning, etc).

#### Real World Dynamics vs. User Perceived Dynamics.

We note that the definition of behavior maps does not rely on the
environment’s true dynamics $T$ since the user’s policy is computed based on
their perceived dynamics $T_{p}^{\text{user}}$. In reality, if $T$ and
$T_{p}^{\text{user}}$ are significantly different, it would be reasonable to
assume that the user iteratively updates $T_{p}^{\text{user}}$ as they
interact with the real world.

#### The Topology of Behavior Maps.

For the set of worlds in this work, verifying that any two are equivalent
reduces to matching the number of behavior changes along the edges of their
behavior maps. That is, the decision boundaries of their behavior maps have no
interesting topology. See Appendix D for a discussion on intervention
transfers between worlds whose behavior maps are topologically distinct in
more nuanced ways. Future research could characterize the set of worlds for
which the decision boundaries of the behavior maps are not as “well-behaved”.

##  8 Conclusion

In this work, we propose a novel tool, the behavior map, to study the
relationship between user traits and user behaviors for worlds in which the
user acts as an RL agent. We define an equivalence relation between worlds
based on the shapes of their corresponding behavior maps. We show that
intervention strategies can be transferred between equivalent worlds. In
particular, we demonstrate that many seemingly different RL environments map
to one of a few equivalence classes, each represented by a simple atomic
world. We further argue that many real-world applications can be mapped to
atomic worlds by leveraging domain knowledge in behavioral science and
psychology. Finally, we show how broad insight into intervention design for
simple worlds can be lifted to complex ones in the same equivalence class.

## Acknowledgements

This material is based upon work supported by the National Science Foundation
under Grant No. IIS-2107391. Any opinions, findings, conclusions, or
recommendations expressed in this material are those of the author(s) and do
not necessarily reflect the views of the National Science Foundation.

## References

  * Ainslie & Haslam (1992) Ainslie, G. and Haslam, N.  Hyperbolic discounting.  _Choice over time_ , 1992.
  * Biza & Platt (2018) Biza, O. and Platt, R.  Online abstraction with mdp homomorphisms for deep learning.  _arXiv preprint arXiv:1811.12929_ , 2018.
  * Evans et al. (2016) Evans, O., Stuhlmüller, A., and Goodman, N.  Learning the preferences of ignorant, inconsistent agents.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 30, 2016.
  * Givan et al. (2003) Givan, R., Dean, T., and Greig, M.  Equivalence notions and model minimization in markov decision processes.  _Artificial Intelligence_ , 147(1-2):163–223, 2003.
  * Golub et al. (2013) Golub, M., Chase, S., and Yu, B.  Learning an internal dynamics model from control demonstration.  In _International Conference on Machine Learning_ , pp. 606–614. PMLR, 2013.
  * Li et al. (2006) Li, L., Walsh, T. J., and Littman, M. L.  Towards a unified theory of state abstraction for mdps.  In _AI &M_, 2006.
  * Picha et al. (2021a) Picha, K. J., Valier, A. S., Heebner, N. R., Abt, J. P., Usher, E. L., Capilouto, G., and Uhl, T. L.  Physical therapists’ assessment of patient self-efficacy for home exercise programs.  _International Journal of Sports Physical Therapy_ , 16(1):184, 2021a.
  * Picha et al. (2021b) Picha, K. J., Valier, A. S., Heebner, N. R., Abt, J. P., Usher, E. L., Capilouto, G., and Uhl, T. L.  Physical therapists’ assessment of patient self-efficacy for home exercise programs.  _International Journal of Sports Physical Therapy_ , 16(1):184, 2021b.
  * Ravindran & Barto (2004) Ravindran, B. and Barto, A. G.  Approximate homomorphisms: A framework for non-exact minimization in markov decision processes.  _College of Information and Computer Sciences, University of Massachusetts_ , 2004.
  * Reddy et al. (2018) Reddy, S., Dragan, A., and Levine, S.  Where do you think you’re going?: Inferring beliefs about dynamics from behavior.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Shah et al. (2019) Shah, R., Gundotra, N., Abbeel, P., and Dragan, A.  On the feasibility of learning, rather than assuming, human biases for reward inference.  In Chaudhuri, K. and Salakhutdinov, R. (eds.), _Proceedings of the 36th International Conference on Machine Learning_ , volume 97 of _Proceedings of Machine Learning Research_ , pp. 5670–5679. PMLR, 09–15 Jun 2019.
  * Shin et al. (2022) Shin, E., Swaroop, S., Pan, W., Murphy, S., and Doshi-Velez, F.  Modeling mobile health users as reinforcement learning agents.  _arXiv preprint arXiv:2212.00863_ , 2022.
  * Soni & Singh (2006) Soni, V. and Singh, S.  Using homomorphisms to transfer options across continuous reinforcement learning domains.  In _AAAI_ , volume 6, pp. 494–499, 2006.
  * Sorg & Singh (2009) Sorg, J. and Singh, S.  Transfer via soft homomorphisms.  In _Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems-Volume 2_ , pp. 741–748, 2009.
  * Story et al. (2014) Story, G. W., Vlaev, I., Seymour, B., Darzi, A., and Dolan, R. J.  Does temporal discounting explain unhealthy behavior? a systematic review and reinforcement learning perspective.  _Frontiers in behavioral neuroscience_ , 8:76, 2014.
  * van der Pol et al. (2020) van der Pol, E., Kipf, T., Oliehoek, F. A., and Welling, M.  Plannable approximations to mdp homomorphisms: Equivariance under actions.  _arXiv preprint arXiv:2002.11963_ , 2020.
  * Zhi-Xuan et al. (2020) Zhi-Xuan, T., Mann, J., Silver, T., Tenenbaum, J., and Mansinghka, V.  Online bayesian goal inference for boundedly rational planning agents.  _Advances in neural information processing systems_ , 33:19238–19250, 2020.
  * Ziebart (2010) Ziebart, B. D.  _Modeling purposeful adaptive behavior with the principle of maximum causal entropy_.  Carnegie Mellon University, 2010.

##  Appendix A Descriptions of Each World from the Literature

In this section, we present the MDPs for the MDPs from the mHealth literature
we study in this work, i.e., the Chain World, RiverSwim World, and Gambler’s
Ruin in Fig. 5, Fig. 6, and Fig. 7, respectively. Blue arrows indicate the
behavior corresponding to the blue behavior in the corresponding behavior maps
and, likewise, for orange arrows.

Figure 5: In the Chain world, users can choose to “exercise,” or progress
step-by-step to reach the desired goal. At each stage, they also have the
option to “disengage,” which results in a smaller reward and the termination
of their progression. Figure 6: In the RiverSwim world, the user can choose
the rightward “upstream” action, which has a chance of successfully advancing
the user toward the larger reward but also a failure probability of staying in
place or falling behind. They can also choose the leftward “downstream” action
that deterministically moves the user toward the small reward on the far left.
Figure 7: In the Gambler’s Ruin (Bandit Problem) world, users can choose the
“continue” action, which can either move the user one step left toward the
dead-end state or one step right toward the goal state. They can also choose
the “finish” action, moving them directly to the dead-end or goal state.
Figure 8: In the Café world, users start at the bottom of a 13 $\times$ 8 grid
and must choose where to get food. The choices are two donut stores, a noodle
shop, and a vegan café. The rewards of 50, 50, 100, and 200 represent the
long-term satisfaction someone might feel from eating the food. An important
dynamic in this world is that users must pass the donut stores to reach the
noodle shop or vegan café, and the noodles are closer to the start than the
vegan café. In our initial experiments, we look at the choice between the
unhealthy choice (donuts) versus the comparatively healthy choice of noodles
or vegan food. We indicate the paths users take when making the unhealthy
choice in orange and the healthy choices in blue. In Appendix C, we look at
the dynamics of the behavior maps when all three choices are evaluated
separately.

##  Appendix B Parameter Perturbations for Each World

In the following, we present more comprehensive investigations into the
invariance of the different worlds to changes in the world parameters under
our definition of equivalence. Different worlds have different sets of
parameters to perturb and ranges for which they remain invariant.

Figure 9: This array of graphs depicts behavior maps within the Cliff world
across variations of three parameters: height, width, and reward size. These
maps are placed in the same equivalence class under our definition, indicating
their robustness to parameter perturbations. Figure 10: This array of graphs
depicts behavior maps within the Big-Small world across variations of multiple
parameters, such as world size and magnitude of rewards. While the graphs are
not identical, all these maps are still in the same equivalence class under
our definition, indicating their robustness to parameter perturbations. Figure
11: This array of graphs depicts behavior maps within the Chain world across
variations of six parameters, including world size and disengagement
probabilities. These maps are placed in the same equivalence class under our
definition, indicating their robustness to parameter perturbations. Figure 12:
This array of graphs depicts behavior maps within the Gambler’s Ruin world
across the width and reward size variations while holding the failure
probability $\left(p^{F}\right)$ constant. These maps are placed in the same
equivalence class under our definition, indicating their robustness to
parameter perturbations. Figure 13: This array of graphs depicts behavior maps
within the Gambler’s Ruin world across the width and reward size variations
while holding the “continue” probability $\left(p^{C}\right)$ constant. These
maps are placed in the same equivalence class under our definition, indicating
their robustness to parameter perturbations. Figure 14: This array of graphs
depicts behavior maps within the RiverSwim world across the width and reward
sizes variations. These maps are placed in the same equivalence class under
our definition, indicating their robustness to parameter perturbations. Figure
15: This array of graphs depicts behavior maps within the Wall world across
variations of world size and reward magnitude. These maps are placed in the
same equivalence class under our definition, indicating their robustness to
parameter perturbations. Figure 16: This array of graphs depicts behavior maps
within the Cafe world, presented in Evans et al. (2016), across variations of
relative reward for the types of eating options: Donuts, noodles/veggie. These
maps are placed in the same equivalence class under our definition, indicating
their robustness to parameter perturbations.

##  Appendix C Initial World Composition Experiments

In this section, we present two behavior map perturbations that indicate that
more complex worlds can be decomposed as a combination of several smaller
atomic worlds.

#### Big-Small & Cliff Composition.

The first, seen in Fig. 17(a), is a Cliff world with an added option of
disengaging. This disengagement state is modeled as a state immediately below
the start state in Fig. 2(b). The disengagement is associated with a small
positive reward, which can, e.g., be interpreted as the user’s sense of relief
for not having to engage in physical therapy anymore (which is obviously
smaller than the faraway reward of being fully rehabilitated). The
compositionality comes from the observation that the user now has two choices:
(1) to engage or disengage, and (2) if they engage, be safe, or take risks.
The first choice is similar to a Big-Small world (disengage for a small reward
or engage for an expected bigger reward farther away).

#### Big-Small & Big-Small Composition.

The second composition, whose behavior map is shown in Fig. 17(b), is the Café
world with the choices between donuts, noodles, and vegan. Intuitively, the
agent is now faced with two separate decisions, where both are the choice
between a small reward near and a relatively larger reward farther away.

(a) In the Cliff world with the possibility for disengagement, the agent is
effectively faced with first the choice between a small and big reward, and
then the choice of strategy for traversing the cliff (safe or risky). This
effect is evident from the new decision boundary that crosses from the top
edge’s left side to the bottom edge’s right side, just like a Big-Small
decision boundary.

(b) In the Café world, the agent is effectively faced with two, sequential
Big-Small worlds. This can be seen by considering the boundary between the
orange and blue areas as the first decision between a far and big reward
(noodle/vegan) and a near and small reward (donuts). If the user avoids the
donuts, they are faced with the choice between another far and big reward
(vegan) and a near and (relatively) small reward (noodle).

Figure 17: Two worlds that appear to be straightforward compositions of two
atomic worlds. Characterizing these compositions and understanding whether and
how they can be useful is an interesting avenue for future research.

##  Appendix D Consideration on the Interior of Behavior Maps

We have argued that the most important part of behavior maps is the extreme
regions, i.e. the behavior along the edges. One way to argue this is by using
literature from the behavioral sciences, which has been one motivating factor.
Another observation one can make is the following. Let worlds (a) and (b) in
Fig. 18 be two different worlds that belong to the same equivalence class [1,
0, 1, 0]. Since $n_{1}=n_{3}=1$, there can be no ambiguity about how the
vertices are connected. However, we place no restrictions on where along the
$\gamma$-axis the vertices are. If we decide the blue region is the desired
behavior, but we observe the user in the orange region (regardless of where),
the optimal intervention will be the same in both worlds (a) and (b).

In the more complex case shown in Fig. 19, both worlds (a) and (b) are in the
same equivalence class [2, 0, 2, 0], despite having very different middle
regions. This disparity arises since $\sum_{i}n_{i}\geq 4$ and there will be
more than one valid way to connect the vertices. If we again imagine that blue
is the desired behavior and orange is observed, these two worlds will still
share the optimal behavior, as indicated with gray arrows in Fig. 19.

We have not proven this exhaustively; atomic worlds where this observation
does not hold might still arise. From our initial experiments, however, worlds
with $\sum_{i}n_{i}\geq 4$ appear rare.

Figure 18: Two different worlds with equivalent and simple behavior maps. Gray
arrows indicate the optimal intervention for an agent that exists in the
orange region. Despite having their decision boundaries in different locations
along the $\gamma$-axis, the best intervention is the same. Figure 19: Two
different worlds with more complex and differing behavior maps still belong to
the same equivalence class. Despite having very different interior regions, in
many cases, the optimal intervention on an agent located in the orange region
would be the same.