# On the Expressivity of Multidimensional Markov Reward

Shuwa Miura
Manning College of Information and Computer Sciences
University of Massachusetts Amherst
Amherst, MA 01003
<EMAIL_ADDRESS>

###### Abstract

We consider the expressivity of Markov rewards in sequential decision making
under uncertainty. We view reward functions in Markov Decision Processes
(MDPs) as a means to characterize desired behaviors of agents. Assuming
desired behaviors are specified as a set of acceptable policies, we
investigate if there exists a scalar or multidimensional Markov reward
function that makes the policies in the set more desirable than the other
policies. Our main result states both necessary and sufficient conditions for
the existence of such reward functions. We also show that for every non-
degenerate set of deterministic policies, there exists a multidimensional
Markov reward function that characterizes it.

Keywords:

Reinforcement Learning, Reward, Reward Hypothesis, Markov Decision Process,
Multidimensional Reward

### Acknowledgements

This research was supported by the National Science Foundation grants number
IIS-1724101 and IIS-1954782. We would like to thank Connor Basich, Saaduddin
Mahmud, and Shlomo Zilberstein at University of Massachusetts Amherst for
their helpful comments and feedback on this work.

##  1 Introduction

Reward functions direct behaviors of agents. In some problems such as games,
rewards are available for agents by default (e.g. as scores). For other
problems, however, there are no reward signals inherently available in the
environment. Rather, rewards are designed by the designer of the agent as a
means to produce desired behaviors.

The vast majority of previous work on sequential decision making under
uncertainty has focused on MDPs with scalar Markov rewards. Similarly, most
Inverse Reinforcement Learning (IRL) [1] techniques learn scalar Markov reward
functions from behaviors. The implicit assumption is that scalar Markov
rewards are sufficient to characterize desired behaviors of agents (Reward
Hypothesis [11]).

On the other hand, many real-world problems often contain multiple competing
objectives and seem to require multidimensional reward functions [9]. For
example, an autonomous vehicle might want to minimize both the time to reach
its destination and fuel consumption. While the problem can intuitively be
formulated using a two-dimensional reward function, there is little formal
study on exactly when we need more than scalar Markov rewards. One could still
argue that a carefully engineered scalar reward function can represent the
desired behaviors (e.g. via linear scalarization), but it is not clear when
scalarization is possible.

This paper provides an initial direction to study expressivity of
multidimensional Markov reward. Previous work [2] recently pointed out that
some set of desired behaviors in Markov environment cannot be characterized by
scalar Markov rewards. Our work extends the previous work [2] and asks the
question: given a Markov environment and a specification for desired
behaviors, does there exist a multidimensional Markov reward function that
characterizes the desired behaviors? Our main result states both necessary and
sufficient conditions for the existence of scalar and multidimensional Markov
rewards that characterize a given set of acceptable policies (Proposition 1
and 2). We also show that for every non-degenerate set of deterministic
policies, there exists a multidimensional Markov reward function that
characterizes it (Corollary 1).

##  2 Background

MDP A finite MDP is a tuple $E=\langle S,A,T,\gamma,s_{0},R\rangle$ where: $S$
is finite a set of states, $A$ is a finite set of actions, $T:S\times A\times
S\rightarrow[0,1]$ is a transition function, $\gamma$ is a discount factor,
$s_{0}$ is the initial state, and $R:S\times A\rightarrow\mathbb{R}$ is a
reward function. We use $\bm{r}$ to denote a vector of size $(|S|\times|A|)$
representing $R$. We refer to an MDP without a reward function as a Markov
environment ($E=\langle S,A,T,\gamma,s_{0}\rangle$). A solution to an MDP is a
_policy_. In this paper, We only consider _stationary policies_ , policies
that do not change over time. A _deterministic policy_ $\pi$ maps a state $s$
to an action $a\in A$. A _stochastic policy_ $\pi$ maps a state $s$ to a
probability distribution over $A$. A policy $\pi$ induces a value function
$V^{\pi}(s)=\mathbb{E}[\sum_{t=0}^{\infty}\gamma^{t}R(S_{t},A_{t})|S_{0}=s,\pi]$,
which represents the expected discounted sum of rewards from $s_{0}$ by
following $\pi$. An _optimal policy_ $\pi^{*}$ is a policy that maximizes
$V^{\pi}(s_{0})$. A _discounted expected state-action visitation_ of a policy
$\pi$ is defined as
$\rho^{\pi}(s,a)=\mathbb{E}[\sum_{t=0}^{\infty}\gamma^{t}Pr(S_{t}=s,A_{t}=a)|S_{0}=s_{0},\pi]$.
We use $\bm{\rho}^{\pi}$ to denote a vector of $\rho^{\pi}(s,a)$. We have
$V^{\pi}(s_{0})=\sum_{s\in S,a\in
A}R(s,a)\rho^{\pi}(s,a)=\bm{r}^{\top}\bm{\rho}^{\pi}$.
$(1-\gamma)\bm{\rho}^{\pi}$ is called an _occupancy measure_.

Reward Design Problem To formally investigate the expressivity of various
reward functions, we ask questions of the form: given a Markov environment and
a specification for desired behaviors, does there exist a Markov reward
function that characterizes the desired behaviors? Previous work [2] explored
reward design problems for different forms of specifications for desired
behaviors. Among the different specifications considered in the previous work,
we focus on the case where a finite set of acceptable (good) policies and
unacceptable (bad) policies ($\langle\Pi_{G},\Pi_{B}\rangle$) are given. We
require that $\Pi_{G}$ and $\Pi_{B}$ are disjoint, and call the pair SOAP as
in the original paper [2]. We say a scalar Markov reward function $R$ realizes
$\langle E,\Pi_{G},\Pi_{B}\rangle$ if every policy in $\Pi_{G}$ is optimal
while every policy in $\Pi_{B}$ is not.

######  Definition 1 (Scalar Reward Design Problem for SOAP).

Given a Markov environment $E$ and SOAP $\langle\Pi_{G},\Pi_{B}\rangle$, is
there a reward function $R:S\times A\rightarrow\mathbb{R}$ such that $R$
realizes $\langle E,\Pi_{G},\Pi_{B}\rangle$?

$s_{0}$start$s_{1}$$a_{1},a_{2}$$a_{1},a_{2}$ (a) Entailment

$s_{0}$start$s_{1}$$a_{2}$$a_{1},a_{2}$$a_{1}$ (b) Steady State

Figure 1: Examples of Markov environments from previous work [2].

For example, consider the environment in Figure 1(a). Let $\pi_{ij}$ be a
deterministic policy taking $a_{i}$ at $s_{0}$ and $a_{j}$ at $s_{1}$. When
$\Pi_{G}=\\{\pi_{11}\\}$ and $\Pi_{B}=\\{\pi_{12},\pi_{21},\pi_{22}\\}$
(taking $a_{1}$ is always better), a reward function that sets
$R(s_{0},a_{1})$ and $R(s_{1},a_{1})$ high realizes the given SOAP. On the
other hand, previous work [2] pointed out that when
$\Pi_{G}=\\{\pi_{12},\pi_{21}\\}$ and $\Pi_{B}=\\{\pi_{11},\pi_{22}\\}$, there
exists no scalar Markov reward function that characterizes the set of
acceptable policies. To make both $\pi_{12}$ and $\pi_{21}$ optimal, we would
have to make $\pi_{11}$ and $\pi_{22}$ optimal as well.

Figure 1(b) shows another example where scalar Markov reward is not enough.
When $\pi_{21}\in\Pi_{G}$ and $\pi_{22}\in\Pi_{B}$, as the agent never visits
$s_{1}$, $\pi_{21}$ cannot be better than $\pi_{22}$.

Note that Definition 1 is a generalization of the original definition [2]. The
original definition assumes $\Pi_{B}=\overline{\Pi_{G}}$ and policies are
deterministic. Previous work [2] proposed an LP formulation to solve the
scalar reward design problem.

##  3 Reward Design Problems for Multidimensional Markov Rewards

While the previous work focused on scalar Markov reward setting, we now
consider characterizing a set of acceptable policies using multidimensional
Markov rewards. First, we define consistency of SOAP to exclude degenerate
problem instances like the one in Figure 1(b).

######  Definition 2 (Consistency of SOAP).

A SOAP $\langle\Pi_{G},\Pi_{B}\rangle$ is consistent iff for all
$\pi_{a}\in\Pi_{G}$ and $\pi_{b}\in\Pi_{B}$,
$\bm{\rho}^{\pi_{a}}\neq\bm{\rho}^{\pi_{b}}$.

In other words, SOAP is consistent when policies with the same discounted
expected state-action visitations are preferred equally. For example, in
Figure 1(b), as $\bm{\rho}^{\pi_{21}}=\bm{\rho}^{\pi_{22}}$ ,
$\langle\Pi_{G},\Pi_{B}\rangle=\langle\\{\pi_{21}\\},\\{\pi_{11},\pi_{12},\pi_{22}\\}\\}\rangle$
is not consistent.

With the presence of multiple objectives, there could be different ways to
characterize acceptable policies. One common approach is to use a set of
Pareto-optimal policies [9]. Another approach is to use Constrained Markov
Decision Processes (CMDPs) [3], and characterize acceptable policies as those
satisfying constraints. In this paper, we use a constraint-based formulation
for the ease of analysis. We leave the Pareto-based approach to future work.

######  Definition 3.

Given $\langle E,R,\mathbf{c}\rangle$ where $E$ is a Markov environment,
$\mathbf{c}\in\mathbb{R}^{d}$ is a lower-bound vector, and $R:S\times
A\rightarrow\mathbb{R}^{d}$ is a $d$-dimensional reward function, a policy
$\pi$ is feasible for $\langle E,R,\mathbf{c}\rangle$ iff for all $i\in[d]$,
$V^{\pi}_{i}(s_{0})\geq c_{i}$.

In other words, feasibility is defined as in CMDPs. But as we are only
interested in characterizing a set of acceptable policies, we do not consider
the maximization aspect of CMDPs. For example, consider again the environment
in Figure 1(a). Let $R(s_{0},a_{1})=R(s_{1},a_{1})=\begin{bmatrix}0\\\
0\end{bmatrix}$, $R(s_{0},a_{2})=R(s_{1},a_{2})=\begin{bmatrix}1\\\
-1\end{bmatrix}$, and $\mathbf{c}=\begin{bmatrix}2\\\ -8\end{bmatrix}$. Then
as in Figure 2(a), $\pi_{12}$ and $\pi_{21}$ are feasible policies while
$\pi_{11}$ and $\pi_{22}$ are infeasible. We say $\langle
E,R,\mathbf{c}\rangle$ _realizes_ $\langle\Pi_{G},\Pi_{B}\rangle$ if every
policy in $\Pi_{G}$ is feasible and every policy in $\Pi_{B}$ is infeasible.
The example shows that
$\langle\Pi_{G},\Pi_{B}\rangle=\langle\\{\pi_{12},\pi_{21}\\},\\{\pi_{11},\pi_{22}\\}\rangle$
can be realized with $d=2$.

$-1$$-0.5$$0.5$$1$$1.5$$2$$2.5$$3$$3.5$$4$$4.5$$5$$5.5$$6$$-1$$1$$2$$3$$4$$5$$6$$\pi_{11}$$\pi_{22}$$\pi_{21}$$\pi_{12}$$\rho(s_{0},a_{2})$$\rho(s_{1},a_{2})$
(a) $\Pi_{G}=\\{\pi_{12},\pi_{22}\\}$ and $\Pi_{B}=\\{\pi_{11},\pi_{22}\\}$

$-1$$-0.5$$0.5$$1$$1.5$$2$$2.5$$3$$3.5$$4$$4.5$$5$$5.5$$6$$-1$$1$$2$$3$$4$$5$$6$$\pi_{22}$$\pi_{11}$$\pi_{21}$$\pi_{12}$$\rho(s_{0},a_{2})$$\rho(s_{1},a_{2})$
(b) $\Pi_{G}=\\{\pi_{22}\\}$ and $\Pi_{B}=\\{\pi_{11},\pi_{12},\pi_{21}\\}$

Figure 2: Visualization of policies for Figure 1(a) in discounted expected
state-action visitation space with $\gamma=0.9$. Black dots represent policies
in $\Pi_{G}$. White dots represent policies in $\Pi_{B}$. The grey area
represents the feasible region.

The problem we consider then is:

######  Definition 4 (Multidimensional Reward Design Problem for SOAP).

Given a Markov environment $E$ and SOAP $\langle\Pi_{G},\Pi_{B}\rangle$, is
there $d\in\mathbb{N}$, $\mathbf{c}\in\mathbb{R}^{d}$, and $R:S\times
A\rightarrow\mathbb{R}^{d}$ such that $\langle R,\mathbf{c}\rangle$ realizes
$\langle E,\Pi_{G},\Pi_{B}\rangle$?

We now argue that multidimensional reward design problems are equivalent to
_polyhedral separability_ problems [7]. Let $\bm{r}_{i}$ be a vector of size
$(|S|\times|A|)$ representing $i$-th dimensional rewards and
$\bm{R}=\begin{bmatrix}\bm{r}_{1}^{\top}\\\ \vdots\\\ \bm{r}_{d}^{\top}\\\
\end{bmatrix}$. Then as $V^{\pi}_{i}(s_{0})=\
\bm{r}_{i}^{\top}\bm{\rho}^{\pi}$, a policy $\pi$ is feasible iff
$\bm{R}\bm{\rho}^{\pi}\geq\bm{c}$. In other words, a policy $\pi$ is feasible
iff it is within the polyhedron
$\\{\bm{x}\in\mathbb{R}^{|S|\times|A|}|\bm{R}\bm{x}\geq\bm{c}\\}$, where each
dimension of the reward function defines a hyperplane. Let $\mathrm{P}$ be the
set of discounted expected state-action visitation corresponding to a set of
policies $\Pi$. Now given $\langle\Pi_{G},\Pi_{B}\rangle$, asking if there
exists $d$-dimensional $\langle R,\mathbf{c}\rangle$ that realizes $\langle
E,\Pi_{G},\Pi_{B}\rangle$ is equivalent to asking if there exists a polyhedron
using $d$ hyperplanes that separates $\mathrm{P}_{G}$ and $\mathrm{P}_{B}$. We
denote the convex hull of $\mathrm{P}$ with $k$ elements as
$\textup{conv}(\mathrm{P})=\\{\sum_{i=1}^{k}\lambda_{i}\bm{\rho}_{i}|\bm{\rho}_{i}\in\mathrm{P},\sum_{i=1}^{k}\lambda_{i}=1,\lambda_{i}\in\mathbb{R}_{\geq
0}\\}$. From Proposition 2.2 on polyhedral separability in [4], we immediately
get the following result:

######  Proposition 1.

Given a Markov environment $E$ and SOAP $\langle\Pi_{G},\Pi_{B}\rangle$, there
exists $d\leq|\Pi_{B}|$, $\mathbf{c}\in\mathbb{R}^{d}$, and $R:S\times
A\rightarrow\mathbb{R}^{d}$ that realizes $\langle E,\Pi_{G},\Pi_{B}\rangle$
iff $\textup{conv}(\mathrm{P}_{G})\cap\mathrm{P}_{B}=\emptyset$.

Intuitively, if we let $d=|\Pi_{B}|$, for each bad policy $\pi_{b}$, as
$\bm{\rho}^{\pi_{b}}\not\in\textup{conv}(\mathrm{P}_{G})$, we can pick a
hyperplane that separates $\bm{\rho}^{\pi_{b}}$ from $\mathrm{P}_{G}$. Note
that $d=|\Pi_{B}|$ is not necessarily the smallest $d$ that realizes a given
SOAP. It is possible that one hyperplane separates multiple bad policies at
once. For example, Figure 2(b) shows a case where $|\Pi_{B}|=3$ but $d=1$ is
enough to separate $\mathrm{P}_{G}$ from $\mathrm{P}_{B}$. We now consider a
special case where all policies are deterministic:

######  Corollary 1.

Given a Markov environment $E$ and consistent SOAP
$\langle\Pi_{G},\Pi_{B}\rangle$, if all policies in
$\langle\Pi_{G},\Pi_{B}\rangle$ are deterministic, there exists
$d\leq|\Pi_{B}|$, $\mathbf{c}\in\mathbb{R}^{d}$, and $R:S\times
A\rightarrow\mathbb{R}^{d}$ that realizes $\langle E,\Pi_{G},\Pi_{B}\rangle$.

###### Proof Sketch.

Consistency of the SOAP ensures that $\mathrm{P}_{G}$ and $\mathrm{P}_{B}$ are
disjoint. Let $\mathrm{P}$ be the set of all possible discounted expected
state-action visitations for the given environment. As each
$\pi_{b}\in\Pi_{B}$ is a deterministic policy, $\bm{\rho}^{\pi_{b}}$ is an
extreme point of $\mathrm{P}$. That is, $\bm{\rho}^{\pi_{b}}$ cannot be
written as a convex combination of other points in $\mathrm{P}$. So for each
$\pi_{b}\in\Pi_{B}$, we have
$\bm{\rho}^{\pi_{b}}\not\in\textup{conv}(\mathrm{P}_{G})$, which implies
$\textup{conv}(\mathrm{P}_{G})\cap\mathrm{P}_{B}=\emptyset$. ∎

An interesting question is whether there exists a scalar Markov reward
function ($d=1$) that realizes a given SOAP. In other words, we are asking if
there exists a hyperplane that separates $\mathrm{P}_{G}$ from
$\mathrm{P}_{B}$. From Theorem 3 in [6], we get:

######  Proposition 2.

Given a Markov environment $E$ and SOAP $\langle\Pi_{G},\Pi_{B}\rangle$, there
exists $c\in\mathbb{R}$, and $R:S\times A\rightarrow\mathbb{R}$ that realizes
$\langle E,\Pi_{G},\Pi_{B}\rangle$ iff
$\textup{conv}(\mathrm{P}_{G})\cap\textup{conv}(\mathrm{P}_{B})=\emptyset$.

Note that the setting is slightly different from that of Definition 1. Every
policy $\pi_{a}\in\Pi_{G}$ must satisfy $V^{\pi_{a}}(s_{0})\geq c$, but does
not have to be optimal. If $R$ makes every $\pi_{a}\in\Pi_{G}$ optimal, we can
easily characterize $\Pi_{G}$ as a set of feasible policies with the same $R$
and $c=V^{*}(s_{0})$. However, the converse is not true in general111This is
essentially difference between range-SOAP and equal-SOAP described in the
previous work [2].

##  4 Conclusions and Future Work

We have presented our initial attempts to investigate the expressivity of
multidimensional Markov rewards, extending the recent work [2]. Our main
result shows both necessary and sufficient conditions for the existence of
scalar and multidimensional Markov rewards that realizes a given set of
acceptable policies (Proposition 1 and 2). We additionally show that a set of
deterministic policies can always be characterized by some multidimensional
Markov rewards (Corollary 1).

We foresee the following directions for future research:

More General Task Specifications This paper assumes that desired behaviors of
agents are specified as a set of acceptable policies. A natural direction
forward is to extend our results to general preferences among policies and
trajectories.

Algorithm and Complexity While our results state conditions under which
multidimensional Markov rewards realize a given set of acceptable policies, we
did not provide an algorithm to check the conditions. We plan to develop the
algorithm based on ideas from [4] and analyze the computational complexity of
the problem.

Preference-based IRL using Multidimensional Rewards We plan to extend our idea
to preference-based IRL [13, 5] using multidimensional rewards. The binary
classification problem we considered above can be thought of as a special case
of preference learning, where the preference forms only two classes. Our
preference-based IRL approach would use a loss function inspired by
separability of policies.

Decision Theory Exploring expressivity of rewards has a strong connection to
classical decision theory. In particular, SOAPs considered in this work can
thought of as violating the Independence Axiom from the VNM Theorem [12]. We
plan to explore the connection between bounded rationality of the designer and
expressivity of Markov rewards. There is some previous work [10, 8] that
explored the connection between reinforcement learning and decision theory.

## References

  * [1] Pieter Abbeel and Andrew Y. Ng.  Apprenticeship learning via inverse reinforcement learning.  In Proceedings of the twenty-first international conference on Machine learning, pages 1–8, 2004.
  * [2] David Abel, Will Dabney, Anna Harutyunyan, Mark K Ho, Michael Littman, Doina Precup, and Satinder Singh.  On the expressivity of Markov reward.  In Advances in Neural Information Processing Systems, volume 34, pages 7799–7812, 2021.
  * [3] Eitan Altman.  Constrained Markov decision processes, volume 7.  CRC Press, 1999.
  * [4] A. Astorino and M. Gaudioso.  Polyhedral separability through successive LP.  Journal of Optimization Theory and Applications, 112(2):265–293, 2002.
  * [5] Daniel Brown, Wonjoon Goo, Prabhat Nagarajan, and Scott Niekum.  Extrapolating beyond suboptimal demonstrations via inverse reinforcement learning from observations.  In Proceedings of the 36th International Conference on Machine Learning, pages 783–792, 2019.
  * [6] O. L. Mangasarian.  Linear and Nonlinear Separation of Patterns by Linear Programming.  Operations Research, 13(3):444–452, 1965.
  * [7] Nimrod Megiddo.  On the complexity of polyhedral separability.  Discrete & Computational Geometry, 3(4):325–337, 1988.
  * [8] Silviu Pitis.  Rethinking the discount factor in reinforcement learning: A decision theoretic approach.  In Proceedings of theThirty-third AAAI Conference on Artificial Intelligence, pages 7949–7956, 2019.
  * [9] Diederik M. Roijers and Shimon Whiteson.  Multi-Objective Decision Making.  Synthesis Lectures on Artificial Intelligence and Machine Learning, 11(1):1–129, 2017.
  * [10] Peter Sunehag and Marcus Hutter.  Axioms for rational reinforcement learning.  In Algorithmic Learning Theory, Lecture Notes in Computer Science, pages 338–352. Springer, 2011.
  * [11] Richard S. Sutton.  The reward hypothesis, 2004.  http://incompleteideas.net/rlai.cs.ualberta.ca/RLAI/rewardhypothesis.html.
  * [12] John von Neumann, Oskar Morgenstern, and Ariel Rubinstein.  Theory of Games and Economic Behavior.  Princeton University Press, 1944.
  * [13] Christian Wirth, Riad Akrour, Gerhard Neumann, and Johannes Fürnkranz.  A survey of preference-based reinforcement learning methods.  The Journal of Machine Learning Research, 18(1):4945–4990, 2017\.