Thesis Department Thesis Division Doctor of philosophy Live as if you were to
die tomorrow. Learn as if you were to live forever.
—Mahatma Ghandi

# On Reward Structures
of Markov Decision Processes

Falcon Z. Dai

(September, 2022)

###### Abstract

###### Contents

  1. 0 Introduction
    1. 1 Markov decision processes
    2. 2 Related processes
    3. 3 Values
    4. 4 Transition structures
    5. 5 Problem formulations
      1. 1 Policy evaluation
      2. 2 Regret minimization
  2. 1 Efficient policy evaluation
    1. 1 Introduction
    2. 2 Related works
    3. 3 Preliminaries
      1. 1 Markov reward processes and Markov chains
      2. 2 Discounted total rewards
      3. 3 Problem statement
      4. 4 Renewal theory and loops
    4. 4 Main results
      1. 1 Bellman equations over loops
      2. 2 Loop estimator
      3. 3 Rates of convergence
    5. 5 Additional results
      1. 1 Conditions for consistency
      2. 2 Concentration of first return times
      3. 3 Cover times
    6. 6 Numerical experiments
      1. 1 Alternative estimators
      2. 2 Comparative experiments
    7. 7 Discussions
  3. 2 Incorporating expert knowledge
    1. 1 Introduction
      1. 1 Related work
    2. 2 Results
      1. 1 Markov decision process
      2. 2 Average reward criterion, and regret
      3. 3 Optimism in the face of uncertainty, extended MDP, and UCRL2
      4. 4 Informativeness of rewards
      5. 5 Potential-based reward shaping
    3. 3 Discussion
  4. 3 Safety, recoverability, and multiple rewards
    1. 1 Irrecoverable MDPs
    2. 2 Resets and reset-efficient RL
    3. 3 Planning with multiple rewards
  5. 4 Concluding thoughts
  6. 5 Appendix
    1. 5.A Detailed proofs of Chapter 1
      1. 1 Proof of Theorem 4.1
      2. 2 Proof of Theorem 4.2
      3. 3 Proof of Lemma 4.3
      4. 4 Proof of Corollary 4.4
      5. 5 Proof of Theorem 4.5
      6. 6 Proof of Corollary 4.6
    2. 5.B Detailed proofs of Chapter 2
      1. 1 Proof of Lemma 2.1
      2. 2 Proof of Theorem 2.3
    3. 5.C Details of the numerical experiment in Section 2
    4. 5.D Details of the numerical experiment in Section 3

###### List of Figures

  1. 1 Diagram of three Markov reward processes with transition probabilities labeled on the edges. The rewards are $1$ for $s_{2}$ and $0$ elsewhere.
  2. 2 Diagram of Markov chain $M_{k}$ with transition probabilities labeled on the edges.
  3. 3 The induced RiverSwim MRP. The arrows are labeled with transition probabilities. The rewards are all zero except for state $s_{6}$, where $r(s_{6})=1$.
  4. 4 The estimation error of each state (normalized by $\max_{s}v(s)$) is plotted over the square root of maximal expected hitting times $\sqrt{\tau_{s}}$ of that state. Error bars show the standard deviations over 200 runs and the discount factor is $\gamma=0.9$ over timesteps $T=10^{5}$.
  5. 5 Estimation errors (normalized by $\max_{s}v(s)$ to be comparable across discount factors) of different estimators at different discount factors (top) $\gamma=0.9$ and (bottom) $\gamma=0.99$. Shaded areas represent the standard deviations over 200 runs. Note the vertical log scale.
  6. 1 Circular nodes represent states and square nodes represent actions. The solid edges are labeled by the transition probabilities and the dashed edges are labeled by the mean rewards. Furthermore, $r_{\text{max}}=1$. For concreteness, one can consider setting $\alpha=0.11,\beta=0.1,\epsilon=0.05$.
  7. 1 Typical cumulative resets over steps.
  8. 2 Typical running averages of resets over steps.
  9. 3 Typical running averages of rewards over steps.
  10. 4 Typical cumulative resets in the optimal sub-chain.
  11. 5 Gains of some stochastic policies (colored in blue) and _all_ deterministic policies (colored in red). This illustrates the feasible gains of a particular MDP with two reward functions.
  12. 6 The gains of iterates of a run of the proposed Direct-cone policy optimization algorithm color-coded from dark blue to bright yellow. The blue dots are gains of some stochastic policies as seen in Figure 5.
  13. 1 Circular nodes represent states and square nodes represent actions. The solid edges are labeled by the transition probabilities and the dashed edges are labeled by the two kinds of rewards in red font. For our experiment, we set $\epsilon=0.1$.
  14. 2 The gains of different policies plotted over the policy space.
  15. 3 Extra examples of iterates of the proposed Direct-cone policy optimization algorithm color-coded from dark blue to bright yellow. The trajectories have different initial policies. The blue dots are gains of some stochastic policies as seen in Figure 5.

###### Acknowledgements.

My journey into the world of machine learning started in the summer of 2012
after my graduation from the University of Chicago. I was fascinated by the
possibility of a learning machine, not unlike what Alan Turing had envisioned
as a path to artificial intelligence [Tur50]. A decade later, I am delighted
to have acquired the modern language to frame the obstacles to that dream and
made my small contributions to that endeavor. Along the way, I experienced the
joy of unexpected discovery and the excitement of recognition. I remained
frequently amazed by how the study of reinforcement learning could provide
ideas for living a better life. First and foremost, I would like to thank my
advisor, Matt Walter. His support and guidance have enabled my exploration of
many ideas some of which are presented here. His work ethics and his kindness
will always be an inspiration to me. There are many people whose company I am
deeply thankful for. Without them, my intellectual voyage would have been
unbearably lonely: Zheng Cai, Andrea Daniele, Chip Schaff, David Yunis, Lifu
Tu, Shubham Toshniwal, Jiading Feng, Igor Vasiljević, Ruotian Luo, Takuma
Yoneda, Shengjie Lin, Jon Michaux, Daping Weng, Payman Yadollahpour, Ruixi
Mao, Ronan Fruit, Audrey Sedal, Karl Stratos, Kevin Gimpel, Greg
Shakhnarovich, Leo Towle, David McAllester, Sasha Rush, Avrim Blum, Julia
Chuzhoy, Mary Silber and many others. With the generous support of TTIC, my
many intellectual interests have gone further than I imagined [DC17, DC19].
Mary Marre, Amy Minick, Jessica Jacobson, Adam Bohlander has made me feel part
of a family. Lastly, I wish to thank my parents for their patience and love:
You Dai, whose liking of philosophy has shaped my taste; Xuetian Wu, whose
resilience taught me not to give up. During the last years of my study, I have
been fortunate enough to form my own family: Yunxi Duan, whose pragmatism and
grace have greatly enriched my life.

##  Chapter 0 Introduction

Reinforcement learning (RL) is concerned with sequential decision making in an
unknown environment. The environment is modeled as a discrete-time finite
Markov decision process (MDP) in the context of this thesis as in classical
literature. We interact with an MDP by choosing an action (based on history)
and this decision affects transition probabilities over the next states. We
receive an immediate reward based on the current state and the action we
choose. The sum of immediate rewards would be the primary rubric for measuring
the merits of a policy or an algorithm that we follow. Despite the initial
ignorance of the actual environment, it is expected that through properly
chosen actions, we can learn more and more about the environment and gradually
improve the rewards we obtain and the policy we follow. Thanks to the
flexibility of MDPs, RL has been applied to many domains and demonstrated
superior performance, including games [Sil+16, Mni+15], language modeling
[Ouy+22], robotics [KBP13] among others.

Being surrounded by colleagues that are concerned with the applicability of RL
in real-world robotics (in developing optimal controllers), we are inspired to
formalize some of the challenges and analyze them. Due to the nature of
reinforcement learning, it generally takes many interactions to learn a good
policy. Thus we study the “cost” of reinforcement learning and ways to lower
it. The main concerns that guide our investigations revolve around the “cost”
of learning are:

  * •

How many samples (interactions) do we need to learn?

  * •

Can we learn faster with some extra help from an expert?

  * •

Can we learn safely incurring few costly mistakes?

After introducing some prerequisite definitions and notational conventions, we
shall present the various investigations roughly in an ascending order of
complexities and generality of their assumptions. In Chapter 1, we consider
the policy evaluation problem where we wish to evaluate how rewarding a given
policy is via samples. We present a novel policy evaluation routine called
_loop estimator_ that enables efficiently evaluating the value of a single
state, a capability absent in other methods [DW21]. In Chapter 2, we present a
novel analysis of a well-known practical method of providing expert knowledge
to an RL algorithm, _potential-based reward shaping_ [NHR99]. Despite being a
popular method in applied RL studies, reward shaping is not well understood
formally. By constructing a new MDP constant, _maximum expected hitting cost_
(MEHC), that measures how costly it is to move from one state to another
within an MDP, we are able to show that reward shaping changes the maximum
expected hitting cost of an MDP, and thereby it changes the “speed” of
learning [DW19]. Surprisingly, we also discover that the effect of reward
shaping on MEHC is limited to a multiplicative factor of two [DW19]. In
Chapter 3, we examine the problem of safety in the context of RL. Firstly, we
discuss a more general class of MDPs, _multichain_ MDPs, and show that they
can model environments containing irrecoverable actions. Secondly, we recast
resets as actions (and not an automatic or involuntary transition as in
episodic MDPs) and we shall evaluate how safe a learning algorithm
quantitatively is by counting the resets it takes. Lastly, by framing reset
counts as a second sort of reward in an environment, we consider the problem
of finding Pareto-optimal policies in environments with multiple reward
functions. In Chapter 4, we conclude with thoughts on future directions.

###  1 Markov decision processes

We model our interactive environments with (discrete-time) Markov decision
processes, i.e., the stochastic processes are indexed by $t\in\mathbb{N}$.

######  Definition 1.1 (discrete-time Markov decision process).

Given a state space $\mathcal{S}$, an action space $\mathcal{A}$, an action
sequence $(A_{t})_{t\geq 0}$ where $A_{t}\in\mathcal{A}$, a transition kernel
$p:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{P}\left(\mathcal{S}\right)$,
and rewards
$r:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{P}\left(\left[0,r_{\text{max}}\right]\right)$,
a (discrete-time) _Markov decision process_ (MDP)
$\left(S_{t},A_{t},R_{t}\right)_{t\geq 0}$ is a stochastic process in which
states transition according to $p$, i.e., $S_{t+1}\sim p(S_{t},A_{t})$ and
rewards are drawn independently and identically from $r$, i.e., $R_{t}\sim
r(S_{t},A_{t})$.

A _finite_ MDP has a finite state space and a finite action space, i.e.,
$S\coloneqq\left|\mathcal{S}\right|<\infty$ and
$A\coloneqq\left|\mathcal{A}\right|<\infty$. It is often sufficient to
characterize the $\left[0,r_{\text{max}}\right]$-bounded reward distributions
up to their means denoted by
$\bar{r}(s,a)\coloneqq\mathbb{E}\left[R_{0}|S_{0}=s,A_{0}=a\right]$.

As suggested in the name Markov _decision_ process, we need to decide the
sequence of actions $\left(A_{t}\right)_{t\geq 0}$ and thereby affect the
states and rewards. We may follow a policy to choose the actions. Formally, a
(deterministic and Markov) _policy_ $\pi:\mathcal{S}\rightarrow\mathcal{A}$
recommends what actions to take at each state, akin to a feedback controller.
Relatedly, a stochastic Markov policy chooses an action based on the state
according to a distribution over actions,
$\mathcal{S}\rightarrow\mathcal{P}\left(\mathcal{A}\right)$. Since the smaller
class of deterministic policies achieve the same optimal long-term rewards as
the strictly larger class in many settings [Put94], we will mainly study the
deterministic policies and revisit the stochastic policies in Section 3.
Similarly, an _algorithm_ $\mathfrak{L}$ at step $n$ can recommend an action
based on the process $(S_{t},A_{t},R_{t})_{0\leq t<n}$.

In reinforcement learning, we typically consider $p$ and $\bar{r}$ to be
unknown to the algorithm and $\mathcal{S}$, $\mathcal{A}$, and
$r_{\text{max}}$ to be given. We may refer to an MDP by its parameters
$\mathcal{M}\coloneqq(\mathcal{S},\mathcal{A},p,r)$. We will abbreviate
$\mathbb{E}_{s}\left[\cdot\right]\coloneqq\mathbb{E}\left[\cdot|S_{0}=s\right]$
and
$\mathbb{E}_{s}^{\pi}\left[\cdot\right]\coloneqq\mathbb{E}\left[\cdot|S_{0}=s,A_{t}=\pi(S_{t})\right]$.

For finite MDPs, we can conveniently represent the transition kernel $p$ as a
rank-3 tensor $\mathbf{P}$ with index from $[S]\times[A]\times[S]$, where
$[n]=\left\\{1,\cdots,n\right\\}$ such that

$P_{s,a,s^{\prime}}\coloneqq\mathbb{P}\left[S_{1}=s^{\prime}|S_{0}=s,A_{0}=a\right].$

Similarly, when given a policy $\pi$, we can present the transition kernel as
a row-stochastic matrix $\mathbf{P}^{\pi}$, where

$P^{\pi}_{s,s^{\prime}}\coloneqq\mathbb{P}\left[S_{1}=s^{\prime}|S_{0}=s,A_{0}=\pi(s)\right].$

Furthermore, distributions over states are represented by row vectors, whereas
functions over states, column vectors.

######  Remark.

MDPs are very flexible models as they allow for stochastic transitions, unlike
the deterministic dynamics typically studied in (optimal) control theory.

###  2 Related processes

There are several notable stochastic processes related to MDPs.

######  Definition 2.1 (Markov reward process).

Given a state space $\mathcal{S}$, a transition kernel
$p:\mathcal{S}\rightarrow\mathcal{P}\left(\mathcal{S}\right)$, and rewards
$r:\mathcal{S}\rightarrow\mathcal{P}\left(\left[0,r_{\text{max}}\right]\right)$,
a _Markov reward process_ (MRP) $\left(S_{t},R_{t}\right)_{t\geq 0}$ is a
stochastic process in which states transition according to $p$, i.e.,
$S_{t+1}\sim p(S_{t})$ and rewards are drawn independently and identically
from $r$, i.e., $R_{t}\sim r(S_{t})$.

Given an MDP and a policy $\pi:\mathcal{S}\rightarrow\mathcal{A}$, if we take
actions according to $\pi$, i.e., $A_{t}=\pi(S_{t})$, then states transition
according to $S_{t+1}\sim p(S_{t},\pi(S_{t}))$ and rewards distribute
according to $R_{t}\sim r(S_{t},\pi(S_{t}))$. Therefore
$\left(S_{t},R_{t}\right)$ is an MRP of transition kernel
$p(\cdot,\pi(\cdot))$ and rewards $r(\cdot,\pi(\cdot))$.

######  Definition 2.2 (Markov chains).

Given a state space $\mathcal{S}$, and a transition kernel
$p:\mathcal{S}\rightarrow\mathcal{P}\left(\mathcal{S}\right)$, a _Markov
chain_ (MC) $\left(S_{t}\right)_{t\geq 0}$ is a stochastic process in which
states transition according to $p$, i.e., $S_{t+1}\sim p(S_{t})$.

Observe that $\left(S_{t}\right)_{t\geq 0}$ is an MC embedded in an MRP
$\left(S_{t},R_{t}\right)_{t\geq 0}$ when we omit the rewards.

The key property that MDP, MRP and MC share is the Markov property. Informally
speaking, it means that the “memory” of a process is limited to the _latest_
state (or state-action in the case of an MDP) with respect to a linear order
of the index. This linearly ordered index is often thought of as time. For
example, in a Markov chain, we have

$\mathbb{P}\left[S_{t+1}|S_{0},\cdots,S_{t}\right]=\mathbb{P}\left[S_{t+1}|S_{t}\right].$

In contrast, a set of independently and identically distributed (IID) random
variables have no “memory.” One can also extend the single step “memory” to
$n$-many steps and this is called $n$-step Markov property. In online
learning, one often considers a process that has unlimited memory and is
adversarial.

One important phenomenon in finite Markov chains is the existence of
stationary distributions. Using the matrix notations, we call
$\sigma\in\mathcal{P}\left(\left[S\right]\right)$ a _stationary distribution_
of a Markov chain with transition kernel $\mathbf{P}$ if

$\sigma\mathbf{P}=\sigma.$

Therefore, $\sigma$ is a left eigenvector of $\mathbf{P}$ corresponding to the
eigenvalue of one. $\mathbf{P}$ must have an eigenvalue of one because it is a
stochastic matrix where each row sums to one. One way to construct the
stationary distribution $\sigma$ is via the limit of the running distribution
of states

$\lim_{n\rightarrow\infty}\frac{1}{n}\sum_{i=1}^{n}x\mathbf{P}^{i},$

where $x\in\mathcal{P}\left(\left[S\right]\right)$ is an arbitrary
distribution over $[S]$. If $\mathbf{P}$ is aperiodic, then a faster
converging limit can be used, c.f., power iteration algorithm,

$\lim_{n\rightarrow\infty}x\mathbf{P}^{n}.$

The stationary distribution of a Markov chain need not be unique.

We can extend discrete-time MDPs slightly to continuous time while retaining
the discrete state transitions by allowing the transitions to occur at
discrete random times.

######  Definition 2.3 (semi-Markov decision process).

Given a state space $\mathcal{S}$, an action space $\mathcal{A}$, an action
sequence $(A_{t})_{t\geq 0}$ where $A_{t}\in\mathcal{A}$, a transition kernel
$p:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{P}\left(\mathcal{S}\times\left(0,\infty\right)\right)$,
and reward rates
$r:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{P}\left(\left[0,r_{\text{max}}\right]\right)$,
a _semi-Markov decision process_ (SMDP)
$\left(S_{t},A_{t},R_{t},I_{t}\right)_{t\geq 0}$ is a stochastic process in
which state transitions and interarrival times distribute according to $p$,
i.e., $S_{t+1},I_{t}\sim p(S_{t},A_{t})$ and reward rates are drawn
independently and identically from $r$, i.e., $R_{t}\sim r(S_{t},A_{t})$ and
the reward received over the transition would be $R_{t}I_{t}$.

Given an MDP, if we think of committing to a policy until some termination
condition is met and we decide on the next action, then the transitions occur
at random times and we can model the resulting process as an SMDP [SPS99]. In
this case, the random waiting times till transitions are integers.

If we remove states from MDPs instead of actions (as we did in MRPs), then we
get an important model called multi-armed bandits (MAB). MABs are widely
studied in online learning literature as they encapsulate many problems that
require some “exploration vs exploitation” tradeoff. Similar to MDPs, we need
to make decisions as the action sequence is left unspecified.

######  Definition 2.4 (Multi-armed bandits).

Given an action space $\mathcal{A}$, an action sequence $(A_{t})_{t\geq 0}$
where $A_{t}\in\mathcal{A}$, and rewards
$r:\mathcal{A}\rightarrow\mathcal{P}\left(\left[0,r_{\text{max}}\right]\right)$,
a _multi-armed bandit_ (MAB) $\left(A_{t},R_{t}\right)_{t\geq 0}$ is a
stochastic process for which $R_{t}\sim r(A_{t})$.

A particularly nice algorithm UCB (upper confidence bound) [ACF02] for solving
RL problems in MABs provides good intuition known as “optimism in the face of
uncertainty” (OFU) and has been extended to UCRL (upper confidence bound for
reinforcement learning), which solves RL problems in MDPs [JOA10]. We will
follow this general idea in learning. A popular alternative is Thompson
sampling which presents some computational difficulty [FPL18].

###  3 Values

We shall evaluate the merit of a policy by the expected long-term rewards it
receives. By “long-term,” we mean to distinguish the cumulative rewards over
many time steps from the immediate rewards that we receive at each step. More
concretely, we consider the rewards we receive over infinitely many time
steps, c.f., summing over a specific finite time horizon. We use two common
evaluation criteria that incorporate immediate rewards over an infinite time
horizon: exponentially discounted value and average reward.

######  Definition 3.1 (Discounted value).

Given an MRP $\left(S_{t},R_{t}\right)_{t\geq 0}$, _discount_
$\gamma\in[0,1)$, and a state $s\in\mathcal{S}$, we define _the (
$\gamma$-discounted) value of state $s$_ as

$v(s)\coloneqq\mathbb{E}_{s}\left[\sum_{t=0}^{\infty}\gamma^{t}R_{t}\right].$
(1)

This quantity is well-defined since $R_{t}\in[0,r_{\text{max}}]$. In the case
of an MDP with a stationary and Markov policy $\pi$, we write
$v^{\pi}(s)\coloneqq\mathbb{E}_{s}^{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}R_{t}\right]$
and the optimal value
$v^{*}(s)\coloneqq\max_{\pi:\mathcal{S}\rightarrow\mathcal{A}}v^{\pi}(s)$. The
choice of exponential discounting might seem arbitrary at first. Two
equivalent (in expectation) models using undiscounted total rewards can
provide some intuitions. One is to imagine that there is an interest accruing
at a fixed rate of $(1-\gamma)$ on the rewards obtained and that we report the
total earnings in terms of the initial value of money. The other is to imagine
that the process may terminate with a fixed probability of $(1-\gamma)$ at the
current step and all further rewards after termination are zero.

There exists a policy (not necessarily unique) that achieves the optimal value
of every state. This can be seen by considering the Bellman optimality
equation whose solution, the optimal state value function, is unique.

One of the key early insights in the study of MDPs is the subproblem
structure, e.g., dynamic programming. In the case of an infinite horizon
discounted values, we have

$v^{\pi}(s)=\bar{r}^{\pi}(s)+\gamma\sum_{s^{\prime}\in\mathcal{S}}P^{\pi}_{s,s^{\prime}}v^{\pi}(s^{\prime})$
(2)

where
$\bar{r}^{\pi}(s)\coloneqq\mathbb{E}\left[R_{1}|S_{1}=s,A_{1}=\pi(S_{1})\right]$
is the expected immediate reward at state $s$ following policy $\pi$.

In particular, the optimal value satisfies the optimal Bellman equations

$v^{*}(s)=\max_{a}\bar{r}(s,a)+\gamma\sum_{s^{\prime}\in\mathcal{S}}P_{s,a,s^{\prime}}v^{*}(s^{\prime}).$
(3)

######  Definition 3.2 (Gain).

Given an MDP with parameters $\mu=\left(\mathcal{S},\mathcal{A},p,r\right)$
with a policy $\pi$, and a state $s\in\mathcal{S}$, the expected $n$-step
cumulative reward starting in state $s$ is

$c(\mu,\pi,n,s)\coloneqq\mathbb{E}^{\pi}_{s}\left[\sum_{t=1}^{n}R_{t}\right]$

and the _gain_ (or _average reward_) of a state $s$ is

$g(\mu,\pi,s)\coloneqq\lim_{n\rightarrow\infty}\frac{1}{n}c(\mu,\pi,n,s)=\lim_{n\rightarrow\infty}\frac{1}{n}\mathbb{E}^{\pi}_{s}\left[\sum_{t=1}^{n}R_{t}\right]$

and the _optimal gain of state $s$_

$g^{*}(\mu,s)\coloneqq\max_{\pi\in\mathcal{S}\rightarrow\mathcal{A}}g(\mu,\pi,s).$

The (optimal) gain of a state is well-defined due to the existence of
stationary distributions in a Markov chain and sometimes it is referred to as
the stationary reward.

One nice consequence of using these criteria in the infinite horizon setting
is that there exists value-maximizing _stationary_ policies [Put94]. In
contrast, there may not be value-maximizing stationary policies in the finite
horizon setting, that is, the optimal actions might depend on both the current
state and the time left till termination.

The analog of Bellman equations for gains is more complicated. For the states
$\mathcal{S}$ that have the same gain $g$ under policy $\pi$, the gain $g$ and
_bias_ $b:\mathcal{S}\rightarrow\mathbb{R}$ satisfy a set of equations,

$b(s)=\bar{r}^{\pi}(s)+\sum_{s^{\prime}}P^{\pi}_{s,s^{\prime}}b(s^{\prime})-g.$
(4)

Biases measure the excess expected total rewards starting in a given state
than starting in some reference distribution of states and they are only
defined up to an additive constant [Put94]. This constant reflects the choice
of reference distribution.

In contrast to gains, which are determined by the rewards in the infinitely
long tail when visited states converge to the stationary distribution, the
discounted values mix the early rewards and the later ones while heavily
favoring former. The two forms of values are related by the Laurent series
expansion of the discounted value around the perturbation of the discount
factor from one [Put94].

###  4 Transition structures

One way to classify states is based on what states can be reached from what
other states. Recall that similar classification exists for MCs.

######  Definition 4.1 (reachability).

In an MC, we say that state $s^{\prime}$ is _reachable_ from state $s$ if
there exists $n\in\mathbb{N}$ such that
$\mathbb{P}\left[S_{n}=s^{\prime}|S_{1}=s\right]>0$.

If we consider whether a state can appear infinitely many times in an MC, we
can classify states as ergodic or transient. Furthermore, we can partition the
states based on how they recur with other states. A set of states are
considered _closed_ if no other states are reachable from these states. If no
proper subset of states is closed, then it is considered _irreducible_. We
call these sets of states closed _irreducible recurrent classes_ , or
_subchains_ for short. In general, an MC can have multiple subchains and the
rest are called transient states. The transit states have finite expected
visits.

By applying the the Fox-Landi algorithm [FL68] to the transition matrix of an
MC, we can find the partition of the states into subchains and a (possibly
empty) set of transient states.

For an MDP, different policies can induce different subchains. We can
nevertheless extend many notions in MC to MDP by ranging over all policies.
State $s$ _communicates_ with state $s^{\prime}$ if there exist policies $\pi$
such that $s$ and $s^{\prime}$ both belong to the same subchain.

If all states communicate with all other states, then the MDP is a
_communicating_ MDP. One important consequence of communication is that the
_optimal_ gain is the same for all states.

We can quantify how “large” a communicating MDP is by measuring how long it
takes to visit any state from any other state. Let
$H_{s}\coloneqq\inf\\{n:S_{n}=s\\}$ be the hitting time of state $s$, then

######  Definition 4.2 (Diameter [JOA10]).

Given an MDP $\mathcal{M}$, we define _the diameter of $\mathcal{M}$_ as

$\tau(\mathcal{M})\coloneqq\max_{s,s^{\prime}\in\mathcal{S}}\min_{\pi\in\mathcal{S}\rightarrow\mathcal{A}}\mathbb{E}^{\pi}_{s}\left[H_{s^{\prime}}\right].$
(5)

More generally, an MDP can have more than one subchain and can have states
that are transient under all policies. This is called a _multichain_ MDP. For
mulitchain MDPs, we can partition its state-action space so that each
component forms a communicating MDP, that is, communicating when restricted to
some actions, and the transient states. Unique chain decomposition [Sch84] is
an algorithm that can find such subchain structures of a multichain MDP. Once
the MDP is decomposed into communicating subchains, for some computational
purposes, we can view the original MDP as an SMDP over the subchains. Such a
hierarchical representation is the basis for extending value iteration to
multichain MDPs [Ohn88].

###  5 Problem formulations

If we assume full knowledge of both the transition and reward functions, and
wish to find an optimal policy. This is known as a planning problem and the
main challenge is computational. Near-optimal policies with respect to
discounted value or gain can be obtained with efficient algorithms such as
value iteration [Put94]. These approximate solutions to planning are often
relied upon to find good actions to take in the context of RL when we do not
have full knowledge of the environment.

In reinforcement learning-theoretic settings, we typically assume little
knowledge of the transition and reward functions of the actual environment.
Under this weaker assumption, knowledge of the environment is gradually
obtained through interactions thus presenting an additional challenge of
statistical efficiency.

####  1 Policy evaluation

Without prior knowledge of the transitions or rewards, we are interested in
evaluating the value of a given policy through samples. More formally, we wish
to find algorithms that can accurately estimate the value of a policy $\pi$
given a truncated sample path of an MDP $\left(S_{t},A_{t},R_{t}\right)_{1\leq
t\leq n}$, where $A_{t}=\pi(S_{t})$. This sample path is considered “on-
policy” as the actions are taken according to the policy we wish to evaluate.
In a policy iteration algorithm, this estimation process interleaves with
policy improvement in which we update the policy to be greedy with respect to
the estimated values. In contrast, one can imagine that the sample path is
collected with a policy different other than $\pi$ and that will be considered
“off-policy.” Q-learning [WD92] is the classic off-policy RL algorithm that
estimates the _optimal_ action values, which are the action values of an
optimal policy, from samples collected by a policy that visits every state-
action pair infinitely often. Once we know the approximate optimal action
values, a policy greedy with respect to the estimated values would be near-
optimal. If we wish to build continuously adaptive systems that learn and
improve online, a more appropriate formulation is regret minimization.

####  2 Regret minimization

Suppose that we measure learning progress not by samples but by rewards. We
can evaluate how well an algorithm behaves by using the rewards in the
environment. In this setting, we compare the rewards collected by a learner as
it learns to the rewards would have been collected by a policy optimal for the
environment. This is the basis for the game-theoretic notion of regret. This
analysis framework straightforwardly captures the effect of acting on both
learning and reward collecting. Good algorithms in such analysis balance
exploration and exploitation to learn a good policy efficiently.

##  Chapter 1 Efficient policy evaluation

###  1 Introduction

The problem of policy evaluation arises naturally in the context of
reinforcement learning (RL) [SB18] when one wants to evaluate the (action)
values of a policy in a Markov decision process (MDP). In particular, policy
iteration [How60] is a classic algorithmic framework for solving MDPs that
poses and solves a policy evaluation problem during each iteration. Being
motivated by the setting of reinforcement learning, i.e., the underlying MDP
parameters are unknown and samples are obtained interactively, we focus on
solving the policy evaluation problem given only a _single_ sample path.

Following a stationary Markov policy in an MDP, i.e., actions are determined
based solely on the current state, gives rise to a _Markov reward process_
(MRP) [Put94]. For the rest of the article, we focus on MRPs and consider the
problem of estimating the infinite-horizon _discounted_ state values of an
unknown MRP.

A straightforward approach to policy evaluation is to estimate the parameters
of the MRP and then the value by plugging them into the classic Bellman
equation (5) [BT96]. We call this the model-based estimator in the sequel.
This approach has recently been proven to be minimax-optimal given a
generative model [PW19] and it provides excellent estimates of discounted
values in the single sample path setting as well (Section 6). However, model-
based estimators suffer from a space complexity of $O\left(S^{2}\right)$,
where $S$ is the number of states in the MRP. In contrast, _model-free_
methods enjoy a lower space complexity of $O(S)$ by not explicitly estimating
the model parameters [Sut88], but tend to exhibit greater estimation error.

A popular class of estimators, $k$-step bootstrapping temporal difference or
TD(k)111An important variant is TD($\lambda$), but we do not include it in our
experiments since there is not a canonical implementation of the idea of
estimating $\lambda$-return [SB18]. However, any implementation is expected to
exhibit similar behaviors as TD(k) with large $k$ corresponding to large
$\lambda$ [KS00]. estimates a state’s value based on the estimated values of
other states. Like the model-based estimator, TD(k) is based on the classic
Bellman equation (5). The key property of the Bellman equation (5) is that the
estimate of a state’s value is tied to the estimates of other states. This
makes it hard to study the convergence of a specific state’s value estimate in
isolation and motivates the traditional analysis approach of generative model
in existing literature.

Traditionally, prior works [KS99, EM03, GMK13, PW19] first show efficient
estimation of _all_ state values under the “generative model” assumption that
we can generate a sample of next states and rewards starting in each states,
and then invoke an argument that such a batch of samples can be obtained over
a single sample path when all states are visited for at least once, i.e., over
cover times. In this work, we break with the traditional approach by directly
studying the convergence of the value estimate of a _single_ state over the
sample path. The convergence over all states is obtained as a simple
consequence of the union bound. Our key insight is that it is possible to
circumvent the general difficulties of non-independent samples in the single
sample path setting by recognizing the embedded regenerative structure of an
MRP. We alleviate the reliance on estimates of other states by studying
segments of the sample path that start and end in the same state, i.e.,
_loops_. This results in a novel and simple algorithm we call the _loop
estimator_ (Algorithm 1) which is a plug-in estimator based on a novel loop
Bellman equation (10). One important consequence is that the loop estimator
can estimate the value of a single state with a space complexity of $O(1)$
which neither $TD(k)$ or the model-based estimator can achieve.

We first review the requisite definitions (Section 3) and then propose the
loop estimator (Section 2). First, we analyze the algorithm’s rate of
convergence over visits to a single state (Theorem 4.2). Second, we study many
steps it takes to visit a state. Using the exponential concentration of first
return times (Lemma 4.3), we relate visits to their waiting times and
establish the rate of convergence over steps (Theorem 4.5). Lastly, we obtain
the convergence in $\ell_{\infty}$-norm over all states via the union bound as
a consequence (Corollary 4.6). Besides theoretical analysis, we also compare
the loop estimator to several other estimators numerically on a commonly used
example (Section 6). Finally, we discuss the model-based vs. model-free status
of the loop estimator (Section 7).

Our main contributions in this work are two-fold:

  * •

By recognizing the embedded regenerative structure in MRPs, we derive a new
Bellman equation over loops, segments that start and end in the same state.

  * •

We introduce _loop estimator_ , a novel algorithm that can provably
efficiently estimate the discounted values of a single state in an MRP from a
single sample path.

In the interest of a concise presentation, we defer detailed proofs to
Appendix 5.A with fully expanded logarithmic factors and constants. An
implementation of the proposed loop estimator and the presented experiments is
publicly available.222https://github.com/falcondai/loop-estimator

###  2 Related works

Much work that formally studies the convergence of value estimators
(particularly the TD estimators) relies on having access to independent
trajectories that start in _all_ states [DS94, EM03, JJS94, KS00]. This is
called a _generative model_ or sometimes a parallel sampling model [KS99].
Given a convergence over batches of generative samples, we still need some
reduction arguments to actually obtain a batch of generative (or parallel)
samples over the sample path of a MRP. [KS99] consider how a set of
independent trajectories can be obtained via mixing, i.e., approximately
samples from the stationary distribution. This suggests on _average_ it takes
$O\left(t_{\text{mix}}/p^{*}\right)$-many steps where $t_{\text{mix}}$ is the
expected steps to get close to the stationary distribution
($\nicefrac{{1}}{{4}}$ in total variation distance) and $p^{*}$ is the
smallest nonzero probability in the stationary distribution.

This reduction can be improved by considering the steps the chain takes to
visit all states at least once, i.e., _cover times_ , which is exactly when we
have a batch of generative samples. This is an improved reduction in that we
can study its convergence rate with high probability instead of the average
behavior. But the cover time of a Markov chain can be quite large: its
concentration can be related to that of the hitting times to _all_ states. In
contrast, for a single state, our results compares favorable scaling with the
maximal expected hitting time of that specific state. When running over all
states, we see that TD(0) updates the value of a single state thus incurring
time complexity of $O(1)$ per step whereas running $S$-many the loop
estimators incurs time complexity of $O(S)$ per step to update. We provide
more detailed discussion of cover times n Section 3.

To ensure consistency of estimation is at all possible, we assume that the
specific state to estimate is positive recurrent (Assumption 3.1), otherwise
we cannot hope to (significantly) improve its value estimate after the final
visit (see Section 1 for an illustrative example). We think that this
assumption is reasonable as recurrence is a key feature of many Markov chains
and it connects naturally to the online (interactive) setting where we cannot
arbitrarily restart the chain. Moreover, this assumption is no stronger than
the assumption used in the cover time reduction which assumes that we can
repeatedly visit all states. If a resetting mechanism is available, values of
transient states can be estimated from values of the recurrent states.
Furthermore, in a finite MRP, there is at least one recurrent state due to the
infinite length of a trajectory.

Besides the interest in the RL community to study the policy evaluation
problem, operation researchers were also motivated to study estimation in
order to leverage simulations as a computational tool. In such settings, the
restriction of estimating only from a single sample path is usually not a
concern. Classic work in simulations by [FG89] deals with estimating
discounted value in a continuous time setting, including an estimator using
regenerative structure. In comparison to their work, we provides an instance-
dependent rate based on the transition structure which is relevant for the
single sample path setting. [HP92] and [Der70] propose unbiased value
estimators whereas the loop estimator is biased due to inversion.

Outside of the studies on reward processes, the regenerative structure of
Markov chains has found application in the _local_ computation of PageRank
[LOS13]. We make use of a lemma (Lemma 4.3, whose proof is included in the
Appendix 3 for completeness) from this work to establish an upper bound on
waiting times (Corollary 4.4). Furthermore, we provide an example to support
why hitting times do not exponentially concentrate over its expectation in
general (see Section 2). Similar in spirit to the concept of locality studied
by [LOS13], our loop estimator enables space-efficient estimation of a single
state value with a space complexity of $O(1)$ and an error bound without
explicit dependency on the size of the state space. As a consequence, the loop
estimator can provably estimate the value of a state with a finite maximal
expected hitting time even if the state space is infinite.

Recently, an independent work by [SM19] makes a similar observation of the
regenerative structure and studies using estimates similar to the loop
estimator in the context of a policy gradient algorithm. It provides promising
experimental results that complement our novel theoretical guarantees on the
rates of convergence. Taken together, these works show that regenerative
structure is a promising direction in RL.

###  3 Preliminaries

####  1 Markov reward processes and Markov chains

Consider a finite state space $\mathcal{S}\coloneqq\\{1,\cdots,S\\}$ whose
size is $S=\lvert\mathcal{S}\rvert$, a transition probability matrix
$\mathbf{P}:\mathcal{S}\times\mathcal{S}\rightarrow[0,1]$ that specifies the
transition probabilities between consecutive states $X_{t}$ and $X_{t+1}$,
i.e., (strong) Markov property
$\mathbb{P}[X_{t+1}=s^{\prime}|X_{t}=s,\cdots,X_{0}]=\mathbb{P}[X_{t+1}=s^{\prime}|X_{t}=s]=P_{ss^{\prime}}$,
and a reward function
$r:\mathcal{S}\rightarrow\mathcal{P}([0,r_{\text{max}}])$ where $R_{t}\sim
r(X_{t})$, then $(X_{t},R_{t})_{t\geq 0}$ is called a discrete-time finite
_Markov reward process_ (MRP) [Put94]. Note that $(X_{t})_{t\geq 0}$ is an
embedded Markov chain with transition law $\mathbf{P}$. Furthermore, we denote
the mean rewards as $\bar{\mathbf{r}}:s\mapsto\mathbb{E}[r(s)]$. As
conventions, we denote
$\mathbb{E}_{s}[\cdot]\coloneqq\mathbb{E}[\cdot|X_{0}=s]$ and
$\mathbb{P}_{s}[\cdot]\coloneqq\mathbb{P}[\cdot|X_{0}=s]$.

The first step when a Markov chain visits a state $s$ is called the _hitting
time to $s$_, i.e., $H_{s}\coloneqq\inf\\{t:X_{t}=s\\}$. Note that if a chain
starts at $s$, then $H_{s}=0$. We refer to the first time a chain returns to
$s$ as the _first return time to $s$_

$H_{s}^{+}\coloneqq\inf\\{t>0:X_{t}=s\\}.$ (1)

######  Definition 3.1 (Expected recurrence time).

Given a Markov chain, we define the _expected recurrence time of state $s$_ as
the expected first return time of $s$ starting in $s$

$\rho_{s}\coloneqq\mathbb{E}_{s}\left[H_{s}^{+}\right].$ (2)

A state $s$ is _positive recurrent_ if its expected recurrence time is finite,
i.e., $\rho_{s}<\infty$.

######  Definition 3.2 (Maximal expected hitting time).

Given a Markov chain, we define the _maximal expected hitting time of state
$s$_ as the maximal expected first return time over starting states

$\tau_{s}\coloneqq\max_{s^{\prime}\in\mathcal{S}}\mathbb{E}_{s^{\prime}}[H_{s}^{+}].$
(3)

####  2 Discounted total rewards

In RL, we are generally interested in some expected long-term rewards that are
collected by following a policy. In the infinite-horizon discounted total
reward setting, following a Markov policy on an MDP induces an MRP and the
_state value_ of state $s$ is

$v(s)\coloneqq\mathbb{E}_{s}\left[\sum_{t=0}^{\infty}\gamma^{t}R_{t}\right],$
(4)

where $\gamma\in[0,1)$ is the _discount factor_. Note that since the reward is
bounded by $r_{\text{max}}$, state values are also bounded by
$\nicefrac{{r_{\text{max}}}}{{1-\gamma}}$. A fundamental result relating
values to the MRP parameters $(\mathbf{P},\bar{\mathbf{r}})$ is the Bellman
equation for each state $s\in\mathcal{S}$ [SB18]

$v(s)=\bar{r}_{s}+\gamma\sum_{s^{\prime}\in\mathcal{S}}P_{ss^{\prime}}v(s^{\prime}).$
(5)

####  3 Problem statement

Suppose that we have a sample path $(X_{t},R_{t})_{0\leq t<T}$ of length $T$
from an MRP whose parameters $(\mathbf{P},\bar{\mathbf{r}})$ are unknown.
Given a state $s$ and discount factor $\gamma$, we want to estimate $v(s)$.

######  Assumption 3.1 (State $s$ is reachable).

We assume state $s$ is reachable from all states, i.e., $\tau_{s}<\infty$.

Otherwise there is some non-negligible probability that state $s$ would not be
visited from some starting state. This prevents the convergence in probability
(in the form of a PAC-style error bound) that we seek (see Section 1 for a
counterexample).

######  Remark.

Assumption 3.1 can be weakened to the assumption that $s$ is positive
recurrent and the MRP starts in the recurrent class containing $s$. All
following results can be recovered by restricting $\mathcal{S}$ in the
definition of $\tau_{s}$ to the recurrent class containing $s$. However, for
ease of presentation, we will adopt Assumption 3.1 in the rest of the article
without loss of generality.

Note that Assumption 3.1 implies the positive recurrence of $s$, i.e.,
$\rho_{s}<\infty$, by definition, and that the MRP visits state $s$ for
infinitely many times with probability 1.

####  4 Renewal theory and loops

Stochastic processes in general can exhibit complex dependencies between
random variables at different steps, and thus often fall outside of the
applicability of approaches that rely on independence assumptions. Renewal
theory [Ros96] focuses on a class of stochastic processes where the process
restarts after a renewal event. Such regenerative structure allows us to apply
results from the independent and identical distribution (IID) settings.

In particular, we consider the visits to state $s$ as renewal events and
define _waiting times_ $W_{n}(s)$ for $n=1,2,\cdots$, to be the number of
steps before the $n$-th visit

$W_{n}(s)\coloneqq\inf\left\\{w:n\leq\sum_{t=0}^{w}\mathbbm{1}[X_{t}=s]\right\\},$
(6)

and the _interarrival times_ $I_{n}(s)$ to be the steps between the $n$-th and
$(n+1)$-th visit

$I_{n}(s)\coloneqq W_{n+1}(s)-W_{n}(s).$ (7)

######  Remark.

The random times relate to each other in a few intuitive relations. The
waiting time of the first visit is the same as the hitting time
$W_{1}(s)=H_{s}\leq H_{s}^{+}$. Waiting times relate to interarrival times
$W_{n+1}(s)=W_{1}(s)+\sum_{i=1}^{n}I_{i}(s)$.

To justify treating visits to $s$ as renewal events, consider the sub-
processes starting at $W_{1}(s)$ and at $W_{2}(s)$—both MRPs start in state
$s$—due to Markov property of MRP, they are statistical replica of each other.
Since segments $(X_{t},R_{t})_{W_{n}(s)\leq t<W_{n+1}(s)}$ start and end in
the same state, we call them _loops_. It follows that loops are independent of
each other and obey the same statistical law. Intuitively speaking, an MRP is
(probabilistically) specified by its starting state.

######  Definition 3.3 (Loop $\gamma$-discounted rewards).

Given a Markov reward process and a positive recurrent state $s$, we define
the $n$-th _loop $\gamma$-discounted rewards_ as the discounted total rewards
over the $n$-th loop

$G_{n}(s)\coloneqq\sum_{u=0}^{I_{n}(s)-1}\gamma^{u}R_{W_{n}(s)+u}.$ (8)

######  Definition 3.4 (Loop $\gamma$-discount).

Given a Markov reward process and a positive recurrent state $s$, we define
the $n$-th _loop $\gamma$-discount_ as the total discounting over the $n$-th
loop

$\Gamma_{n}(s)\coloneqq\gamma^{I_{n}(s)}.$ (9)

$\left(I_{n}(s),G_{n}(s)\right)_{n>0}$ forms a regenerative process that has
nice independence relations. Specifically, $I_{n}(s)\Perp I_{m}(s)$,
$G_{n}(s)\Perp G_{m}(s)$, and $G_{n}(s)\Perp I_{m}(s)$ when $n\neq m$.
Furthermore, $\left(I_{n}(s)\right)_{n>0}$ are identically distributed the
same as $H_{s}^{+}$ when starting in $s$. Similarly,
$\left(G_{n}(s)\right)_{n>0}$ are identically distributed. Note however that
$G_{n}(s)\centernot{\Perp}I_{n}(s)$.

###  4 Main results

####  1 Bellman equations over loops

Given the regenerative process $\left(I_{n}(s),G_{n}(s)\right)_{n>0}$, we
derive a new Bellman equation over the loops for state value $v(s)$.

######  Theorem 4.1 (Loop Bellman equations).

Suppose the expected loop $\gamma$-discount is
$\alpha(s)\coloneqq\mathbb{E}_{s}[\Gamma_{1}(s)]$ and the expected loop
$\gamma$-discounted rewards is $\beta(s)\coloneqq\mathbb{E}_{s}[G_{1}(s)]$, we
can relate the state value $v(s)$ to itself

$v(s)=\beta(s)+\alpha(s)\,v(s).$ (10)

######  Remark.

The key difference between the loop Bellman equations (10) and the classic
Bellman equations (5) is the state values involved. Only state value $v(s)$
appears on the right-hand side of (10).

####  2 Loop estimator

We plug in the empirical means for the expected loop $\gamma$-discount
$\alpha(s)$ and the expected loop $\gamma$-discounted rewards $\beta(s)$ into
the loop Bellman equation (10) and define the $n$-th _loop estimator_ for
state value $v(s)$

$\hat{v}_{n}(s)\coloneqq\hat{\beta}_{n}(s)/(1-\hat{\alpha}_{n}(s)),$ (11)

where $\hat{\alpha}_{n}(s)\coloneqq\frac{1}{n}\sum_{i=1}^{n}\gamma^{I_{i}(s)}$
and $\hat{\beta}_{n}(s)\coloneqq\frac{1}{n}\sum_{i=1}^{n}G_{i}(s)$.
Furthermore, we have visited state $s$ for $(N+1)$ times before step $T$ where
$N$ is a random variable that counts the number of loops before step $T$

$N\coloneqq\sup\\{n:W_{n+1}(s)\leq T\\},$ (12)

and the estimate $\hat{v}_{N}(s)$ would be the last estimate before step $T$.
Hence, with a slight abuse of notations, we define

$\hat{v}_{T}(s)\coloneqq\hat{v}_{N}(s).$ (13)

By using incremental updates to keep track of empirical means, Algorithm 1
implements the loop estimator $\hat{v}_{T}(s)$ with a space complexity of
$O(1)$. Running $S$-many copies of loop estimators, one for each state
$s\in\mathcal{S}$, takes a space complexity of $O(S)$. Due to the parallel
updates, time complexity is $O(S)$ at each step.

Algorithm 1 Loop estimator (for a specific state)

1: Input: discount factor $\gamma$, state $s$, sample path
$(X_{t},R_{t})_{0\leq t<T}$ of some length $T$.

2: Return: an estimate of the discounted value $v(s)$.

3: Initialize the empirical mean of loop discounts $\hat{\alpha}\leftarrow 0$.

4: Initialize the empirical mean of loop discounted rewards
$\hat{\beta}\leftarrow 0$.

5: Initialize the loop count $n\leftarrow 0$.

6: for each loop in $(X_{t},R_{t})_{0\leq t<T}$ do

7: Increment visit count $n\leftarrow n+1$.

8: Compute the length of the interarrival time $I_{n}(s)\leftarrow
W_{n+1}(s)-W_{n}(s)$.

9: Compute the partial discounted sum of rewards,
$G_{n}(s)\leftarrow\sum_{u=0}^{I_{n}(s)-1}\gamma^{u}R_{W_{n}(s)+u}$.

10: Update the empirical means incrementally,
$\hat{\alpha}\leftarrow\frac{1}{n}\gamma^{I_{n}(s)}+\left(1-\frac{1}{n}\right)\hat{\alpha}$,
and
$\hat{\beta}\leftarrow\frac{1}{n}G_{n}(s)+\left(1-\frac{1}{n}\right)\hat{\beta}$.

11: end for

12: return $\hat{\beta}/(1-\hat{\alpha})$

####  3 Rates of convergence

Now we investigate the convergence of the loop estimator, first over visits,
i.e., $\hat{v}_{n}(s)\xrightarrow{p}v(s)$ as $n\rightarrow\infty$, then over
steps, i.e., $\hat{v}_{T}(s)\xrightarrow{p}v(s)$ as $T\rightarrow\infty$. By
applying Hoeffding bound to the definition of loop estimator (11), we obtain a
PAC-style upper bound on the estimation error.

######  Theorem 4.2 (Convergence rate over visits).

Given a sample path from an MRP $(X_{t},R_{t})_{t\geq 0}$, a discount factor
$\gamma\in[0,1)$, and a positive recurrent state $s$, with probability of at
least $1-\delta$, the loop estimator converges to $v(s)$

$|\hat{v}_{n}(s)-v(s)|=O\left(\frac{r_{\text{max}}}{(1-\gamma)^{2}}\sqrt{\frac{1}{n}\,\log\frac{1}{\delta}}\right).$

To determine the convergence rate over steps, we need to study the
concentration of waiting times which allows us to lower-bound the random
visits with high probability. As an intermediate step, we use the fact that
the tail of the distribution of first return times is upper-bounded by an
exponential distribution per the Markov property of MRP [LOS13, AF99].

######  Lemma 4.3 (Exponential concentration of first return times [LOS13,
AF99]).

Given a Markov chain $(X_{t})_{t\geq 0}$ defined on a finite state space
$\mathcal{S}$, for any state $s\in\mathcal{S}$ and any $t>0$, we have

$\mathbb{P}\left[H_{s}^{+}\geq t\right]\leq e\cdot e^{-t/e\tau_{s}}.$

Secondly, since by Remark Remark we have
$W_{n+1}(s)=W_{1}(s)+\sum_{i=1}^{n}I_{i}(s)$, we apply the union bound to
upper-bound the tail of waiting times.

######  Corollary 4.4 (Upper bound on waiting times).

With probability of at least $1-\delta$,
$W_{n}(s)=O\left(n\,\tau_{s}\,\log\frac{n}{\delta}\right)$.

Note that the waiting time $W_{n}(s)$ is nearly linear in $n$ with a
dependency on the Markov chain structure via the maximal expected hitting time
of $s$, namely $\widetilde{O}(n\,\tau_{s})$. In contrast, the _expected_
waiting time scales with the expected recurrence time
$\mathbb{E}[W_{n}(s)]=\Theta(n\,\rho_{s})$. However, an exponential
concentration with the expected recurrence time is not possible in general
(see Section 2 for a counterexample).

Using Lambert W function, we invert Corollary 4.4 to lower-bound the visits by
step $T$ with high probability. Finally, the convergence rate of
$\hat{v}_{T}(s)$ follows from Theorem 4.2.

######  Theorem 4.5 (Convergence rate over steps).

With probability of at least $1-\delta$, for any $T>e\,\delta\,\tau_{s}$, the
MRP $(X_{t},R_{t})_{0\leq t<T}$ visits state $s$ for at least
$\widetilde{\Omega}(T/\tau_{s})$ many times, and the last loop estimate
converges to $v(s)$

$\left|\hat{v}_{T}(s)-v(s)\right|=\widetilde{O}\,\left(\frac{r_{\text{max}}}{(1-\gamma)^{2}}\sqrt{\frac{\tau_{s}}{T}\log\frac{1}{\delta}}\right).$

Suppose we run a copy of loop estimator to estimate each state’s value in
$\mathcal{S}$, and denote them with a vector
$\hat{\mathbf{v}}_{T}:s\mapsto\hat{v}_{T}(s)$. Convergence of the estimation
error $\hat{\mathbf{v}}_{T}-\mathbf{v}$ in terms of the $\ell_{\infty}$-norm
follows immediately by applying the union bound.

######  Corollary 4.6 (Convergence rate over all states).

With probability of at least $1-\delta$, for any
$T>e\,\delta\,\max_{s}\tau_{s}$, the MRP $(X_{t},R_{t})_{0\leq t<T}$ visits
each state $s$ for at least $\widetilde{\Omega}(T/\tau_{s})$ many times, and
the last loop estimates converge to state values $\mathbf{v}$

$\|\hat{\mathbf{v}}_{T}-\mathbf{v}\|_{\infty}=\widetilde{O}\,\left(\frac{r_{\text{max}}}{(1-\gamma)^{2}}\sqrt{\frac{\max_{s}\tau_{s}}{T}\log\frac{S}{\delta}}\right).$

###  5 Additional results

####  1 Conditions for consistency

We provide an example to show that if a state is not positive recurrent, i.e.,
transient, then we cannot attain a consistent estimate of its value in
general. This suggests that Assumption 3.1 is not too strong as a sufficient
condition to study. Recall that we are interested in consistent estimation of
the discounted value of a state given a single sample path from an unknown
MRP. If a state is not positive recurrent, then without assuming any reset
mechanisms, it is visited finitely many times over any sample path almost
surely.

Consider the following three MRPs in Figure 1. It is obvious that
$v(s_{1}^{\prime})=\nicefrac{{\gamma}}{{1-\gamma}}$,
$v(s_{1}^{\prime\prime})=0$, and
$v(s_{1})=\nicefrac{{\gamma}}{{2(1-\gamma)}}$. Suppose we start in $s_{1}$ (of
the MRP in the middle), there are only two possible sample paths:
$(s_{1},0,s_{2},1,s_{2},1,\cdots)$ and $(s_{1},0,s_{3},0,s_{3},0,\cdots)$.
Note that $s_{1}$ is only visited _once_ in either sample path thus transient.
Furthermore, we obtain the first sample path with probability of
$\nicefrac{{1}}{{2}}$ in which case we cannot distinguish it from a sample
path from the MRP on the top. Similarly, with probability of
$\nicefrac{{1}}{{2}}$, we get the second sample path which is
indistinguishable from a sample path from the MRP at the bottom. However, the
values of $s_{1}^{\prime}$ and $s_{1}^{\prime\prime}$ are different (and both
not equal to that of $s_{1}$). Hence we cannot devise an estimator that can
_consistently_ estimate $v(s_{1})$, $v(s_{1}^{\prime})$ and
$v(s_{1}^{\prime\prime})$.

$s_{1}^{\prime}$$s_{2}$$1$$1$

$s_{1}$$s_{2}$$s_{3}$$0.5$$0.5$$1$$1$

$s_{1}^{\prime\prime}$$s_{3}$$1$$1$

Figure 1: Diagram of three Markov reward processes with transition
probabilities labeled on the edges. The rewards are $1$ for $s_{2}$ and $0$
elsewhere.

####  2 Concentration of first return times

We provide an example to show that an exponential concentration of first
return times given the expected recurrence time is impossible. In contrast, in
Lemma 4.3 we proved an exponential concentration given the maximal expected
hitting time. Furthermore, this is consistent with what one would expect from
Markov’s inequality since first return times are nonnegative random variables.

Consider a class of Markov chains $\left\\{M_{k}\right\\}$ indexed by $k\geq
3$ where Markov chain $M_{k}$ has a state space
$\left\\{s_{1},\cdots,s_{k}\right\\}$ and a transition kernel as depicted in
Figure 2. Starting in $s_{1}$, the chain $M_{k}$ can either transition back to
$s_{1}$ in one step with probability $1-\frac{1}{k-1}$ or to $s_{2}$ with
probability $\frac{1}{k-1}$. Thus, there are only two possible values for the
first return time to $s_{1}$: 1 by the self-transition, and $k$ by going
through $s_{2},s_{3},\ldots,s_{k},s_{1}$. We can calculate the expected
recurrence time as

$\rho_{s_{1}}=\left(1-\frac{1}{k-1}\right)\cdot 1+\frac{1}{k-1}\cdot k=2.$

Suppose that there is an exponential concentration of $H^{+}_{s_{1}}$ given
$\rho_{s_{1}}$, then we can upper-bound $\mathbb{P}\left[H^{+}_{s_{1}}\geq
t\right]$ by some exponential function of $t$. However $H^{+}_{s_{1}}=k$ with
probability of $\frac{1}{k-1}$ in $M_{k}$ makes such an exponential bound
impossible as the same $\rho$-dependent upper bound has to work for all
$M_{k}$.

Note that the maximal expected hitting time is $\tau_{s_{1}}=k-1$ in $M_{k}$
when the chain starts in $s_{2}$. A $\tau$-dependent upper bound such as Lemma
4.3 is not denied by such example.

$s_{1}$$s_{2}$$s_{3}$$s_{4}$$s_{k-1}$$s_{k}$$\frac{1}{k-1}$$1-\frac{1}{k-1}$$1$$1$$\dots$$1$$1$
Figure 2: Diagram of Markov chain $M_{k}$ with transition probabilities
labeled on the edges.

####  3 Cover times

To convert convergence results obtained under the generative model to per
steps, we can consider the concentration of cover times.

######  Definition 5.1 (Cover time).

Given a Markov chain $(X_{t})_{t\geq 0}$ with state space $\mathcal{S}$,
_cover time_ is a stopping time when we have visited all the states at least
once

$C\coloneqq\inf\left\\{t:\\{X_{0},\dots,X_{t}\\}=\mathcal{S}\right\\}.$

Conveniently, we can rewrite cover times as the maximum of the hitting times
to all the states

$C=\max_{s\in\mathcal{S}}H_{s}.$

As a consequence, we can apply Lemma 4.3 and obtain a concentration of cover
times using the maximal expected hitting time.

######  Proposition 5.1.

Given a Markov chain $(X_{t})_{t\geq 0}$ defined on a finite state space
$\mathcal{S}$, with probability of at least $1-\delta$

$C\leq e\max_{s}\tau_{s}\log\frac{eS}{\delta}.$

Using this upper bound, convergence results obtained under generative model
reduction such as for the model-based estimator [PW19] match the statistical
rate of $\widetilde{O}\left(\sqrt{\nicefrac{{\max_{s}\tau_{s}}}{{T}}}\right)$
of the $\ell_{\infty}$ bound of the loop estimator (Corollary 4.6). It should
be noted that the loop estimator retains its advantage in local value
estimation due to the state-specific constant.

###  6 Numerical experiments

We consider RiverSwim, an MDP proposed by [SL08] that is often used to
illustrate the challenge of exploration in RL. The MDP consists of six states
$\mathcal{S}=\\{s_{1},\cdots,s_{6}\\}$ and two actions
$\mathcal{A}=\\{\text{``swim downstream''},\text{``swim upstream''}\\}$.
Executing the “swim upstream” action often fails due to the strong current,
while there is a high reward for staying in the most upstream state $s_{6}$.
For our experiments, we use the MRP induced by always taking the “swim
upstream” action (see Figure 3 for numerical details).

The most relevant aspect of the induced MRP is that the maximal expected
hitting times are very different for different states: $\tau_{s_{1}}\approx
752$, $\tau_{s_{2}}\approx 237$, $\tau_{s_{3}}\approx 68$,
$\tau_{s_{4}}\approx 15$, $\tau_{s_{5}}\approx 17$, $\tau_{s_{6}}\approx 22$.
Figure 4 shows a plot of the estimation errors of the loop estimator for each
state over the _square root_ of maximal expected hitting times
$\sqrt{\tau_{s}}$ of that state. The observed linear relationship between the
two quantities (supported by a good linear fit) is consistent with the
instance-dependence in our result of
$\left|\hat{v}_{T}(s)-v(s)\right|=\widetilde{O}\left(\sqrt{\tau_{s}}\right)$,
c.f., Theorem 4.5.

$s_{1}$$s_{2}$$s_{3}$$s_{4}$$s_{5}$$s_{6}$$0.3$$0.7$$0.3$$0.6$$0.1$$0.3$$0.6$$0.1$$0.3$$0.6$$0.1$$0.3$$0.6$$0.1$$0.3$$0.7$
Figure 3: The induced RiverSwim MRP. The arrows are labeled with transition
probabilities. The rewards are all zero except for state $s_{6}$, where
$r(s_{6})=1$. Figure 4: The estimation error of each state (normalized by
$\max_{s}v(s)$) is plotted over the square root of maximal expected hitting
times $\sqrt{\tau_{s}}$ of that state. Error bars show the standard deviations
over 200 runs and the discount factor is $\gamma=0.9$ over timesteps
$T=10^{5}$.

####  1 Alternative estimators

We define several alternative estimators for $v(s)$ and briefly mention their
relevance for comparison.

Model-based. We compute add-1 smoothed maximum likelihood estimates (MLE) of
the MRP parameters $\left(\mathbf{P},\bar{\mathbf{r}}\right)$ from the sample
path

$\hat{P}_{s\,s^{\prime}}\coloneqq\frac{\frac{1}{S}+\sum_{t=0}^{T-1}\mathbbm{1}\left[X_{t+1}=s^{\prime},X_{t}=s\right]}{1+\sum_{t=0}^{T-1}\mathbbm{1}\left[X_{t}=s\right]}$
(14)

and

$\hat{\bar{r}}_{s}\coloneqq\frac{\sum_{t=0}^{T-1}R_{t}\mathbbm{1}\left[X_{t}=s\right]}{1+\sum_{t=0}^{T-1}\mathbbm{1}\left[X_{t}=s\right]}.$
(15)

We then solve for the discounted state values from the Bellman equation (5)
for the MRP parameterized by
$\left(\hat{\mathbf{P}},\hat{\bar{\mathbf{r}}}\right)$, i.e., the (column)
vector of estimated state values

$\hat{\mathbf{v}}_{\text{MB}}\coloneqq\left(\mathbf{I}-\gamma\hat{\mathbf{P}}\right)^{-1}\hat{\bar{\mathbf{r}}}$
(16)

where $\mathbf{I}$ is the identity matrix.

TD(k). $k$-step temporal difference (or $k$-step backup) estimators are
commonly recursively defined [KS00] with TD(0) being a textbook classic [BT96,
SB18]. Let $\hat{v}_{\text{TD}}(0,s)\coloneqq 0$ for all states
$s\in\mathcal{S}$. And for $t>0$

$\hat{v}_{\text{TD}}(t,s)\coloneqq\left\\{\begin{aligned}
&(1-\eta_{t})\,\hat{v}_{\text{TD}}(t-1,s)\\\
&\quad+\eta_{t}\Big{(}\gamma^{0}R_{t}+\cdots+\gamma^{k}R_{t+k}\\\
&\quad+\gamma^{k+1}\hat{v}_{\text{TD}}(t-1,X_{t+k+1})\Big{)},&\text{if
}s=X_{t}&\\\
&\hat{v}_{\text{TD}}(t-1,s),&\text{otherwise}&\end{aligned}\right.$

where $\eta_{t}$ is the learning rates. A common choice is to set
$\eta_{t}=1/\left(\sum_{u=0}^{t}\mathbbm{1}\left[X_{u}=s\right]\right)$ which
satisfies the Robbins-Monro conditions [BT96]. But it has been shown to lead
to slower convergence than
$\eta_{t}=1/\left(\sum_{u=0}^{t}\mathbbm{1}\left[X_{u}=s\right]\right)^{d}$
where $d\in(\nicefrac{{1}}{{2}},1)$ [EM03].

It is more accurate to consider TD methods as a large family of estimators
each with different choices of $k$, $\eta_{t}$. Choosing these parameters can
create extra work and sometimes confusion for practitioners. Whereas the loop
estimator, like the model-based estimator, has no parameters to tune. In any
case, it is not our intention to compare with the TD family exhaustively (see
more results on TD on [KS00, EM03]). Instead, we compare with $\text{TD}(0)$
and $\text{TD}(10)$, both with $d=1$, and $\text{TD}(0)^{*}$ with
$d=\nicefrac{{1}}{{2}}$.

Convergence of a TD estimator may be complicated by the backing up of errors
from statistical estimation. It takes
$\widetilde{O}(\nicefrac{{1}}{{1-\gamma}})$ updates even in the deterministic
setting. In contrast, the model-based estimator and the loop estimator would
require no further updates to refine their estimates in the deterministic
setting. In comparison to the generative model-based convergence analysis of
TD (theorem 4 and 5 of [EM03]), our results on loop estimator is markedly
simpler. Furthermore, our results shows explicit (state) instance dependence.

####  2 Comparative experiments

We experiment with different values for the discount factor $\gamma$, because,
roughly speaking, $1/(1-\gamma)$ sets the horizon beyond which rewards are
discounted too heavily to matter. We compare the estimation errors measured in
$\ell_{\infty}$ norm, which is important in RL. The results are shown in
Figure 5.

Figure 5: Estimation errors (normalized by $\max_{s}v(s)$ to be comparable
across discount factors) of different estimators at different discount factors
(top) $\gamma=0.9$ and (bottom) $\gamma=0.99$. Shaded areas represent the
standard deviations over 200 runs. Note the vertical log scale.

  * •

The model-based estimator dominates all estimators for every discount setting
we tested.

  * •

TD(k) estimators perform well if $k>1/(1-\gamma)$. This is related the issue
of backing up. TD(k) effectively backs up the value $k$ times at each update
and we know that $\widetilde{O}\left(\nicefrac{{1}}{{1-\gamma}}\right)$-many
back ups are needed for TD(0).

  * •

The loop estimator performs worse than, but is competitive with, the model-
based estimator. Furthermore, similar to the model-based estimator and unlike
the TD(k) estimators, its performance seems to be less influenced by
discounting.

###  7 Discussions

The elementary identity below relates the expected first return times
$Y_{s\,s^{\prime}}\coloneqq\mathbb{E}_{s}\left[H_{s^{\prime}}^{+}\right]$ to
the transition probabilities $P_{s\,s^{\prime}}$ for a finite Markov chain.
Using the matrix notations, suppose that the expected first return times are
organized in a matrix $\mathbf{Y}$, and $\mathbf{P}$ the transition matrix of
the Markov chain, then we have
$\mathbf{Y}=\mathbf{P}\left(\mathbf{Y}-\text{diag}\mathbf{Y}+\mathbf{E}\right)$
where $\text{diag}\mathbf{Y}$ is a matrix with the same diagonal as
$\mathbf{Y}$ and zero elsewhere, and $\mathbf{E}$ is a matrix with all ones.
Thus, knowing $\mathbf{Y}$ is equivalent to knowing the full model, as we can
compute $\mathbf{P}$ using this identity. Recall that by definition
$\mathbb{E}\left[I_{1}(s)\right]=\mathbb{E}_{s}\left[H_{s}^{+}\right]$, which
is exactly the diagonal of $\mathbf{Y}$. But only knowing the diagonal is not
sufficient to determine the entire set of model parameters, namely
$\mathbf{Y}$, the loop estimator based on $\left(I_{n}\right)_{n>0}$ indeed
falls short of being a model-based method. It may be considered a _semi_
-model-based method as it estimates some but not all of the model parameters.

For large MRPs, a natural extension of our work is to consider recurrence of
features instead of states, e.g., a video game screen might not repeat itself
completely but the same items might reappear. After all, without repetition
exactly or approximately, it would not be possible for an agent to learn and
improve its decisions.

We believe that regenerative structure can be further exploited in RL
(particularly in the form of the loop Bellman equation (10)) and we think this
article provides the fundamental results for future study in this direction.

##  Chapter 2 Incorporating expert knowledge

It can be very costly to learn rewarding behavior in an unknown environment.
We see that in terms of the samples needed for policy evaluation. In response,
we consider ways to incorporate expert knowledge about the environment. We
briefly consider a mixed imitation learning and reinforcement learning [SDW17]
where a special query action allows the agent to ask an expert for the optimal
action for that state. This is similar to the setting studied by [Clo96].
However, the assumption of knowing the optimal actions for arbitrary states
seems too strong rendering the need to reinforcement learn somewhat redundant.
We decide to investigate alternative forms of knowledge that is more
compatible to reinforcement learning in the sense that we can still
reinforcement learn the optimal behaviors given some ill-specified knowledge.
A well-known technique called potential-based reward shaping satisfies such
desideratum and more by preserving the linear order over policies by their
values (thus suboptimality).

###  1 Introduction

In the average reward setting of reinforcement learning (RL) [Put94, SB98], an
algorithm learns to maximize its average rewards by interacting with an
_unknown_ Markov decision process (MDP). Similar to analysis in multi-armed
bandits and other online machine learning problems, (cumulative) regret
provides a natural model to evaluate the efficiency of a learning algorithm.
With the UCRL2 algorithm, [JOA10] show a problem-dependent bound of
$\tilde{O}(DS\sqrt{AT})$ on regret and an associated logarithmic bound on the
expected regret, where $D$ is the diameter of the actual MDP (Definition 2.1),
$S$ the size of the state space, and $A$ the size of the action space. Many
subsequent algorithms [FLP19] enjoy similar diameter-dependent bounds. This
establishes diameter as an important measure of complexity for an MDP.
However, strikingly, this measure is independent of rewards and is a function
of only the transitions. This is obviously peculiar as two MDPs differing only
in their rewards would have the same regret bounds even if one gives the
maximum reward for all transitions. We review the related key observation by
[JOA10], and refine it with a new lemma (Lemma 2.1), establishing a reward-
_sensitive_ complexity measure that we refer to as the _maximum expected
hitting cost_ (MEHC, Definition 2.2), which tightens the regret bounds of
UCRL2 and similar algorithms by replacing diameter (Theorem 2.2).

Next, with respect to this new complexity measure, we describe a notion of
reward informativeness (Section 4). Intuitively speaking, in an environment,
the _same_ desired policies can be motivated by different (immediate) rewards.
These differing definitions of rewards can be more or less _informative_ of
useful actions, i.e., yielding high long-term rewards. To formalize this
intuition, we study a way to reparametrize rewards via potential-based reward
shaping (PBRS) [NHR99] that can produce different rewards with the same near-
optimal policies (Section 5). We show that the MEHC changes under
reparametrization by PBRS and, in turn, so do regret and sample complexity,
substantiating this notion of informativeness. Lastly, we study the extent of
its impact. In particular, we show that there is a multiplicative factor-of-
two limit on its impact on MEHC in a large class of MDPs (Theorem 2.3). This
result and the concept of reward informativeness may be useful for a task
designer crafting a reward function (Section 3). The detailed proofs are
deffered to Appendix 5.B.

The main contributions of this work are two-fold:

  * •

We propose a new MDP structural parameter, maximum expected hitting cost
(MEHC), that accounts for both transitions and rewards. This parameter
replaces diameter in the regret bounds of several model-based RL algorithms.

  * •

We show that potential-based reward shaping can change the maximum expected
hitting cost of an MDP and thus the regret bound. This results in a set of
equivalent MDPs with different learning difficulties as measured by regret.
Moreover, we show that their MEHCs differ by a factor of at most two in a
large class of MDPs.

####  1 Related work

This work is closely related to the study of diameter as an MDP complexity
measure [JOA10], which is prevalent in the regret bounds of RL algorithms in
the average reward setting [FLP19]. As noted by [JOA10], unlike some previous
measures of MDP complexity such as the return mixing time [KS02, BT02],
diameter depends only on the transitions, but not the rewards. The core reason
for the presence of diameter in the regret analysis is that it upper bounds
the optimal value span of the extended MDP that summarizes the observations
(Section 3 and Equation 8). We review and update this observation with a
reward-dependent parameter we called maximum expected hitting cost (Lemma
2.1). Interestingly, the gap between diameter and MEHC can be arbitrarily
large $\kappa(M)\leq r_{\text{max}}D(M)$; there are MDPs with finite MEHC and
infinite diameter. These MDPs are non-communicating but have saturated optimal
average rewards $\rho^{*}(M)=r_{\text{max}}$. Intuitively, there is a state
$s$ in these MDPs from which the learner cannot visit some other state
$s^{\prime}$, but can nonetheless achieve the maximum possible average reward,
thus allowing for good regret guarantees; the unreachable states do not appear
more attractive than the reachable ones under the principle of optimism in the
face of uncertainty (OFU). We will use UCRL2 [JOA10] as an example algorithm
throughout the rest of the article, however the main results do not depend on
it. In particular, with MEHC, its regret bounds are updated (Theorem 2.2).

Another important comparison is with optimal bias span [Put94, BT09, Fru+18],
a reward-dependent parameter of MDPs. Here, we again find that the gap can be
arbitrarily large $sp(M)\leq\kappa(M)$.111This inequality can be derived as a
consequence of Lemma 2.1 as $N(s,a)\rightarrow\infty$, $M^{+}$ has very tight
confidence intervals around the actual transition and mean rewards of $M$.
Observe that the span of $u_{i}$ is equal to $sp(M)$ at the limit of
$i\rightarrow\infty$ [JOA10, remark 8]. These non-communicating MDPs would
have unsaturated optimal average reward $\rho^{*}(M)<r_{\text{max}}$. But as
shown elsewhere [FPL18, Fru+18], extra knowledge of (some upper bound on) the
optimal bias span is necessary for an algorithm to enjoy a regret that scales
with this smaller parameter. In contrast, UCRL2, which scales with MEHC, does
not need to know the diameter or MEHC of the actual MDP.

Potential-based reward shaping [NHR99] was originally proposed as a _solution
technique_ for a programmer to influence the sample complexity of their
reinforcement learning algorithm, without changing the near-optimal policies
in episodic and discounted settings. Prior theoretical analysis involving PBRS
[NHR99, Wie03, WCE03, ALZ08, Grz17] mostly focuses on the consistency of RL
against the shaped rewards, i.e., the resulting learned behavior is also
(near-)optimal in the original MDP, while suggesting empirically that the
sample complexity can be changed by a well specified potential. In this work,
we use PBRS to construct $\Pi$-equivalent reward functions in the average
reward setting (Section 4) and show that two reward functions related by a
shaping potential can have different MEHCs, and thus different regrets and
sample complexities (Section 5). However, a subtle but important technical
requirement of $[0,r_{\text{max}}]$-boundedness of MDPs makes it difficult to
immediately apply our results (Section 5 and Theorem 2.3) to the treatment of
PBRS as a solution technique because an arbitrary potential function picked
without knowledge of the original MDP may not preserve the
$[0,r_{\text{max}}]$-boundedness. Nevertheless, we think our work may bring
some new perspectives to this topic.

###  2 Results

####  1 Markov decision process

A Markov decision process is defined by the tuple
$M=(\mathcal{S},\mathcal{A},p,r)$, where $\mathcal{S}$ is the state space,
$\mathcal{A}$ is the action space,
$p:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{P}(\mathcal{S})$ is the
transition function, and
$r:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{P}([0,r_{\text{max}}])$ is
the reward function with mean $\bar{r}(s,a)\coloneqq\mathbb{E}[r(s,a)]$. We
assume that the state and action spaces are finite, with sizes
$S\coloneqq\lvert\mathcal{S}\rvert$ and $A\coloneqq\lvert\mathcal{A}\rvert$,
respectively. At each time step $t=0,1,2,\ldots$, an algorithm $\mathfrak{L}$
chooses an action $a_{t}\in\mathcal{A}$ based on the observations up to that
point. The state transitions to $s_{t+1}$ with probability
$p(s_{t+1}|s_{t},a_{t})$ and a reward $r_{t}\in[0,r_{\text{max}}]$ is drawn
according to the distribution $r(s_{t},a_{t})$.222It is important to assume
that the support of rewards lies in a _known_ bounded interval, often $[0,1]$
by convention. This is sometimes referred to as a _bounded_ MDP in the
literature. Analogous to bandits, the details of the reward distribution often
is unimportant, and it suffices to specify an MDP with the mean rewards
$\bar{r}$. The transition probabilities and reward function of the MDP are
unknown to the learner. The sequence of random variables
$(s_{t},a_{t},r_{t})_{t\geq 0}$ forms a stochastic process. Note that a
stationary deterministic policy $\pi:\mathcal{S}\rightarrow\mathcal{A}$ is a
restrictive type of algorithm whose action $a_{t}$ depends only on $s_{t}$. We
refer to stationary deterministic policies as policies in the rest of the
exposition.

Recall that in a Markov chain, the _hitting time_ of state $s^{\prime}$
starting at state $s$ is a random variable $h_{s\rightarrow
s^{\prime}}\coloneqq\inf\\{t\in\mathbb{N}_{\geq 0}|s_{t}=s^{\prime}\text{ and
}s_{0}=s\\}$333$0$-indexing ensures that $h_{s\rightarrow s}=0$. Note also
that by convention, $\inf\varnothing=\infty$. [LPW08].

######  Definition 2.1 (Diameter, [JOA10]).

Suppose in the stochastic process induced by following a policy $\pi$ in MDP
$M$, the time to hit state $s^{\prime}$ starting at state $s$ is
$h_{s\rightarrow s^{\prime}}(M,\pi)$. We define the _diameter_ of $M$ to be

$D(M)\coloneqq\max_{s,s^{\prime}\in\mathcal{S}}\min_{\pi:\mathcal{S}\rightarrow\mathcal{A}}\mathbb{E}\left[h_{s\rightarrow
s^{\prime}}(M,\pi)\right].$

We incorporate rewards into diameter, and introduce a novel MDP parameter.

######  Definition 2.2 (Maximum expected hitting cost).

We define the _maximum expected hitting cost_ of a Markov decision process $M$
to be

$\kappa(M)\coloneqq\max_{s,s^{\prime}\in\mathcal{S}}\min_{\pi:\mathcal{S}\rightarrow\mathcal{A}}\mathbb{E}\left[\sum_{t=0}^{h_{s\rightarrow
s^{\prime}}(M,\pi)-1}r_{\text{max}}-r_{t}\right].$

Observe that MEHC is a smaller parameter, that is, $\kappa(M)\leq
r_{\text{max}}D(M)$, since for any $s,s^{\prime},\pi$, we have
$r_{\text{max}}-r_{t}\leq r_{\text{max}}$.

####  2 Average reward criterion, and regret

The accumulated reward of an algorithm $\mathfrak{L}$ after $T$ time steps in
MDP $M$ starting at state $s$ is a random variable

$R(M,\mathfrak{L},s,T)\coloneqq\sum_{t=0}^{T-1}r_{t}.$

We define the average reward or gain [Put94] as

$\rho(M,\mathfrak{L},s)\coloneqq\lim_{T\rightarrow\infty}\frac{1}{T}\mathbb{E}\left[R(M,\mathfrak{L},s,T)\right].$
(1)

We evaluate policies by their average reward. This can be maximized by a
stationary deterministic policy and we define the optimal average reward of
$M$ starting at state $s$ as

$\rho^{*}(M,s)\coloneqq\max_{\pi:\mathcal{S}\rightarrow\mathcal{A}}\rho(M,\pi,s).$
(2)

Furthermore, we assume that the optimal average reward starting at any state
to be the same, i.e., $\rho^{*}(M,s)=\max_{s^{\prime}}\rho^{*}(M,s^{\prime})$
for any state $s$. This is a natural requirement of an MDP in the online
setting to allow for any hope for a vanishing regret. Otherwise, the learner
may take actions leading to states with a lower average optimal reward due to
ignorance and incur linear regret when compared with the optimal policy
starting at the initial state. In particular, this condition is true for
communicating MDPs [Put94] by virtue of their transitions, but this is also
possible for non-communicating MDPs with appropriate rewards. We will write
$\rho^{*}(M)\coloneqq\max_{s^{\prime}}\rho^{*}(M,s^{\prime})$.

We compete with the expected cumulative reward of an optimal policy _on its
trajectory_ , and define the _regret_ of a learning algorithm $\mathfrak{L}$
starting at state $s$ after $T$ time steps as

$\Delta(M,\mathfrak{L},s,T)\coloneqq T\rho^{*}(M)-R(M,\mathfrak{L},s,T).$ (3)

####  3 Optimism in the face of uncertainty, extended MDP, and UCRL2

The principle of optimism in the face of uncertainty (OFU) [SB98] states that
for uncertain state-action pairs, i.e., those that we have not visited enough
up to this point, we should be optimistic about their outcome. The intuition
for doing so is that taking reward-maximizing actions with respect to this
optimistic model (in terms of both transitions and immediate rewards for these
uncertain state-action pairs), we will have no regret if the optimism is well
placed or we will quickly learn more about these suboptimal state-action pairs
to avoid them in the future. This fruitful idea has been the basis for many
model-based RL algorithms [FLP19] and in particular, UCRL2 [JOA10], which
keeps track of the statistical uncertainty via upper confidence bounds.

Suppose we have visited a particular state-action pair $(s,a)$ $N(s,a)$-many
times. With confidence at least $1-\delta$, we can establish that a confidence
interval for both its mean reward $\bar{r}(s,a)$ and its transition
$p(\cdot|s,a)$ from the Chernoff-Hoeffding inequality (or Bernstein, [FPL18]).
Let $b(\delta,n)\in\mathbb{R}$ be the $\delta$-confidence bound after
observing $n$ i.i.d. samples of a $[0,1]$-bounded random variable,
$\hat{r}(s,a)$ the empirical mean of $r(s,a)$, $\hat{p}(\cdot|s,a)$ the
empirical transition of $p(\cdot|s,a)$. The statistically plausible mean
rewards are

$B_{\delta}(s,a)\coloneqq\bigl{\\{}r^{\prime}\in\mathbb{R}:|r^{\prime}-\hat{r}(s,a)|\leq
r_{\text{max}}\,b(\delta,N(s,a))\bigr{\\}}\cap[0,r_{\text{max}}]$

and the statistically plausible transitions are

$C_{\delta}(s,a)\coloneqq\bigl{\\{}p^{\prime}\in\mathcal{P}(\mathcal{S}):||p^{\prime}(\cdot)-\hat{p}(\cdot|s,a)||_{1}\leq
b(\delta,N(s,a))\bigr{\\}}.$

We define an _extended MDP_
$M^{+}\coloneqq(\mathcal{S},\mathcal{A}^{+},p^{+},r^{+})$ to summarize these
statistics [GLD00, SL05, TB07, JOA10], where $\mathcal{S}$ is the same state
space as in $M$, the action space $\mathcal{A}^{+}$ is a union over state-
specific actions

$\mathcal{A}^{+}_{s}\coloneqq\bigl{\\{}(a,p^{\prime},r^{\prime}):a\in\mathcal{A},p^{\prime}\in
C_{\delta}(s,a),r^{\prime}\in B_{\delta}(s,a)\bigr{\\}},$ (4)

where $\mathcal{A}$ is the same action space in $M$, $p^{+}$ the transitions
according to the selected distribution $p^{\prime}$

$p^{+}\big{(}\cdot|s,(a,p^{\prime},r^{\prime})\big{)}\coloneqq
p^{\prime}(\cdot),$ (5)

and $r^{+}$ is the rewards according to the selected mean reward $r^{\prime}$

$r^{+}\big{(}s,(a,p^{\prime},r^{\prime})\big{)}\coloneqq r^{\prime}.$ (6)

It is not hard to see that $M^{+}$ is indeed an MDP with an infinite but
compact action space.

By OFU, we want to find an optimal policy for an optimistic MDP within the set
of statistically plausible MDPs. As observed in [JOA10], this is equivalent to
finding an optimal policy $\pi^{+}:\mathcal{S}\rightarrow\mathcal{A}^{+}$ in
the extended MDP $M^{+}$, which specifies a policy in $M$ via
$\pi(s)\coloneqq\sigma_{1}(\pi^{+}(s))$, where $\sigma_{i}$ is the projection
map onto the $i$-th coordinate (and an optimistic MDP
$\widetilde{M}=(\mathcal{S},\mathcal{A},\widetilde{p},\widetilde{r})$ via
transitions $\widetilde{p}(\cdot|s,\pi(s))\coloneqq\sigma_{2}(\pi^{+}(s))$ and
mean rewards $\widetilde{r}(s,\pi(s))\coloneqq\sigma_{3}(\pi^{+}(s))$ over
actions selected by $\pi$444We can set transitions and mean rewards over
actions $a\neq\pi(s)$ to $\hat{p}$ and $\hat{r}$, respectively.).

By construction of the extended MDP $M^{+}$, $M$ is in $M^{+}$ with high
confidence, i.e., $\bar{r}(s,a)\in B_{\delta}(s,a)$ and $p(\cdot|s,a)\in
C_{\delta}(s,a)$ for all $s\in\mathcal{S},a\in\mathcal{A}$. At the heart of
UCRL2-type regret analysis, there is a key observation [JOA10, equation (11)]
that we can bound the span of optimal values in the _extended_ MDP $M^{+}$ by
the diameter of the actual MDP $M$ under the condition that $M$ is in $M^{+}$.
This observation is needed to characterize how good following the “optimistic”
policy $\sigma_{1}(\pi^{+})$ in the actual MDP $M$ is. For $i\geq 0$, the _$i$
-step optimal values_ $u_{i}(s)$ of $M^{+}$ is the expected total reward by
following an optimal non-stationary $i$-step policy starting at state
$s\in\mathcal{S}$. We can also define them recursively (via dynamic
programming555In fact, the exact maximization of Equation 7 can be found via
extended value iteration [JOA10, section 3.1])

$u_{0}(s)\coloneqq 0$ $\displaystyle u_{i+1}(s)$
$\displaystyle\coloneqq\max_{(a,p^{\prime},r^{\prime})\in\mathcal{A}^{+}_{s}}\left[r^{+}\big{(}s,(a,p^{\prime},r^{\prime})\big{)}+\sum_{s^{\prime}}p^{+}\big{(}s^{\prime}|s,(a,p^{\prime},r^{\prime})\big{)}\,u_{i}(s^{\prime})\right]$
$\displaystyle\triangleright\text{By \eqref{eq:p-plus} and \eqref{eq:r-plus}}$
$\displaystyle=\max_{(a,p^{\prime},r^{\prime})\in\mathcal{A}^{+}_{s}}\left[r^{\prime}+\sum_{s^{\prime}}p^{\prime}(s^{\prime})\,u_{i}(s^{\prime})\right]$
$\displaystyle\triangleright\text{By \eqref{eq:a-plus}}$
$\displaystyle=\max_{a\in\mathcal{A}}\left[\max_{r^{\prime}\in
B_{\delta}(s,a)}r^{\prime}+\max_{p^{\prime}\in
C_{\delta}(s,a)}\sum_{s^{\prime}}p^{\prime}(s^{\prime})\,u_{i}(s^{\prime})\right]$
(7)

We are now ready to restate the observation. If $M$ is in $M^{+}$, which
happens with high probability, [JOA10] observe that

$\max_{s}u_{i}(s)-\min_{s^{\prime}}u_{i}(s^{\prime})\leq r_{\text{max}}D(M).$
(8)

However, this bound is too conservative because it fails to account for the
rewards collected. By patching this, we tighten the upper bound with MEHC.

######  Lemma 2.1 (MEHC upper bounds the span of values).

Assuming that the actual MDP $M$ is in the extended MDP $M^{+}$, i.e.,
$\bar{r}(s,a)\in B_{\delta}(s,a)$ and $p(\cdot|s,a)\in C_{\delta}(s,a)$ for
all $s\in\mathcal{S},a\in\mathcal{A}$, we have

$\max_{s}u_{i}(s)-\min_{s^{\prime}}u_{i}(s^{\prime})\leq\kappa(M)$

where $u_{i}(s)$ is the $i$-step optimal undiscounted value of state $s$.

This refined upper bound immediately plugs into the main theorems of [JOA10,
equations 19 and 22, theorem 2].

######  Theorem 2.2 (Reward-sensitive regret bound of UCRL2).

With probability of at least $1-\delta$, for any initial state $s$ and any
$T>1$, and $\kappa\coloneqq\kappa(M)$, the regret of UCRL2 is bounded by

$\displaystyle\Delta(M,\texttt{UCRL2},s,T)$
$\displaystyle\quad\leq\sqrt{\frac{5}{8}T\log\left(\frac{8T}{\delta}\right)}+\sqrt{T}+\kappa\sqrt{\frac{5}{2}T\log\left(\frac{8T}{\delta}\right)}+\kappa
SA\log_{2}\left(\frac{8T}{SA}\right)$
$\displaystyle\quad\quad+\Bigg{(}\kappa\sqrt{14S\log\left(\frac{2AT}{\delta}\right)}+\sqrt{14\log\left(\frac{2SAT}{\delta}\right)}+2\Bigg{)}(\sqrt{2}+1)\sqrt{SAT}$
$\displaystyle\quad\leq
34\max\\{1,\kappa\\}S\sqrt{AT\log\left(\frac{T}{\delta}\right)}.$

As a corollary, Theorem 2.2 implies that UCRL2 offers
$O\left(\frac{\kappa^{2}S^{2}A}{\varepsilon^{2}}\log\frac{\kappa
SA}{\delta\varepsilon}\right)$ sample complexity [Kak03], by inverting the
regret bound by demanding that the per-step regret is at most $\varepsilon$
with probability of at least $1-\delta$ [JOA10, corollary 3]. Similarly, we
have an updated logarithmic bound on the expected regret [JOA10, theorem 4],
$\mathbb{E}[\Delta(M,\texttt{UCRL2},s,T)]=O\left(\frac{\kappa^{2}S^{2}A\log
T}{g}\right)$ where $g$ is the gap in average reward between the best policy
and the second best policy.

####  4 Informativeness of rewards

Informally, it is not hard to appreciate the challenge imposed by delayed
feedback inherent in MDPs, as actions with high immediate rewards do not
necessarily lead to a high _optimal_ value. Are there different but
“equivalent” reward functions that differ in their _informativeness_ with the
more informative ones being easier to reinforcement learn? Suppose we have two
MDPs differing only in their rewards,
$M_{1}=(\mathcal{S},\mathcal{A},p,r_{1})$ and
$M_{2}=(\mathcal{S},\mathcal{A},p,r_{2})$, then they have the same diameters
$D(M_{1})=D(M_{2})$ and thus the same diameter-dependent regret bounds from
previous works. With MEHC, however, we may get a more meaningful answer.

Firstly, let us make precise a notion of equivalence. We say that $r_{1}$ and
$r_{2}$ are _$\Pi$ -equivalent_ if for any policy
$\pi:\mathcal{S}\rightarrow\mathcal{A}$, its average rewards are the same
under the two reward functions $\rho(M_{1},\pi,s)=\rho(M_{2},\pi,s)$.
Formally, we study the MEHC of a class of $\Pi$-equivalent reward functions
related via a potential.

####  5 Potential-based reward shaping

Originally introduced by [NHR99], potential-based reward shaping (PBRS) takes
a potential $\varphi:\mathcal{S}\rightarrow\mathbb{R}$ and defines shaped
rewards

$r^{\varphi}_{t}\coloneqq r_{t}-\varphi(s_{t})+\varphi(s_{t+1}).$ (9)

We can think of the stochastic process $(s_{t},a_{t},r^{\varphi}_{t})_{t\geq
0}$ being generated from an MDP
$M^{\varphi}=(\mathcal{S},\mathcal{A},p,r^{\varphi})$ with reward function
$r^{\varphi}:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{P}([0,r_{\text{max}}])$666One
needs to ensure that $\varphi$ respects the $[0,r_{\text{max}}]$-boundedness
of $M$. whose mean rewards are

$\bar{r^{\varphi}}(s,a)=\bar{r}(s,a)-\varphi(s)+\mathbb{E}_{s^{\prime}\sim
p(\cdot|s,a)}\left[\varphi(s^{\prime})\right].$

It is easy to check that $r^{\varphi}$ and $r$ are indeed $\Pi$-equivalent.
For any policy $\pi$,

$\displaystyle\rho(M^{\varphi},\pi,s)$
$\displaystyle=\lim_{T\rightarrow\infty}\frac{1}{T}\mathbb{E}\left[R(M^{\varphi},\pi,s,T)\right]$
$\displaystyle=\lim_{T\rightarrow\infty}\frac{1}{T}\mathbb{E}\left[\sum_{t=0}^{T-1}r^{\varphi}_{t}\right]$
$\displaystyle=\lim_{T\rightarrow\infty}\frac{1}{T}\mathbb{E}\left[\sum_{t=0}^{T-1}r_{t}-\varphi(s_{t})+\varphi(s_{t+1})\right]$
$\displaystyle\triangleright\text{By telescoping sums of potential terms over
consecutive $t$}$
$\displaystyle=\lim_{T\rightarrow\infty}\frac{1}{T}\mathbb{E}\left[-\varphi(s_{0})+\varphi(s_{T})+\sum_{t=0}^{T-1}r_{t}\right]$
$\displaystyle=\lim_{T\rightarrow\infty}\frac{1}{T}\Big{(}-\varphi(s)+\mathbb{E}[\varphi(s_{T})]+\mathbb{E}\left[R(M,\pi,s,T)\right]\Big{)}$
$\displaystyle\triangleright\text{The first two terms vanish in the limit}$
$\displaystyle=\lim_{T\rightarrow\infty}\frac{1}{T}\mathbb{E}\left[R(M,\pi,s,T)\right]$
$\displaystyle=\rho(M,\pi,s).$ (10)

To get some intuition, it is instructive to consider a toy example (Figure 1).
Suppose $0<\beta<\alpha$ and $\epsilon\in(0,1)$, then the optimal average
reward in this MDP is $1-\beta$, and the optimal stationary deterministic
policy is $\pi^{*}(s_{1})\coloneqq a_{2}$ and $\pi^{*}(s_{2})\coloneqq a_{1}$,
as staying in state $s_{2}$ yields the highest average reward. As the expected
number of steps needed to transition from state $s_{1}$ to $s_{2}$ and vice
versa are both $\nicefrac{{1}}{{\epsilon}}$ via action $a_{2}$, we conclude
that
$\kappa(M)=\max\\{\alpha,\nicefrac{{\alpha}}{{\epsilon}},\nicefrac{{\beta}}{{\epsilon}},\beta\\}=\nicefrac{{\alpha}}{{\epsilon}}$.
Furthermore, notice that taking action $a_{2}$ in either state transitions to
the other state with probability of $\epsilon$, however the immediate rewards
are the same as taking the alternative action $a_{1}$ to stay in the current
state—the immediate rewards are not _informative_. We can differentiate the
actions better by shaping with a potential of $\varphi(s_{1})\coloneqq 0$ and
$\varphi(s_{2})\coloneqq\nicefrac{{(\alpha-\beta)}}{{2\epsilon}}$. The shaped
mean rewards become, at $s_{1}$,

$\bar{r^{\varphi}}(s_{1},a_{2})=1-\alpha-\varphi(s_{1})+\epsilon\varphi(s_{2})+(1-\epsilon)\varphi(s_{1})=1-\nicefrac{{(\alpha+\beta)}}{{2}}>1-\alpha=\bar{r^{\varphi}}(s_{1},a_{1})$

and at $s_{2}$,

$\bar{r^{\varphi}}(s_{2},a_{2})=1-\beta-\varphi(s_{2})+\epsilon\varphi(s_{1})+(1-\epsilon)\varphi(s_{2})=1-\nicefrac{{(\alpha+\beta)}}{{2}}<1-\beta=\bar{r^{\varphi}}(s_{2},a_{1}).$

This encourages taking actions $a_{2}$ at state $s_{1}$ and discourages taking
actions $a_{1}$ at state $s_{2}$ simultaneously. The maximum expected hitting
cost becomes smaller

$\displaystyle\kappa(M^{\varphi})$
$\displaystyle=\max\left\\{\alpha,\beta,\varphi(s_{1})-\varphi(s_{2})+\frac{\alpha}{\epsilon},\,\varphi(s_{2})-\varphi(s_{1})+\frac{\beta}{\epsilon}\right\\}$
$\displaystyle=\max\left\\{\alpha,\beta,\frac{\alpha+\beta}{2\epsilon},\,\frac{\alpha+\beta}{2\epsilon}\right\\}$
$\displaystyle=\frac{\alpha+\beta}{2\epsilon}$
$\displaystyle<\frac{\alpha}{\epsilon}=\kappa(M).$

$s_{1}$$s_{2}$$a_{1}$$a_{2}$$a_{1}$$a_{2}$$\epsilon$$1-\epsilon$$\epsilon$$1-\epsilon$$1$$1$$1-\alpha$$1-\alpha$$1-\beta$$1-\beta$
Figure 1: Circular nodes represent states and square nodes represent actions.
The solid edges are labeled by the transition probabilities and the dashed
edges are labeled by the mean rewards. Furthermore, $r_{\text{max}}=1$. For
concreteness, one can consider setting $\alpha=0.11,\beta=0.1,\epsilon=0.05$.

In this example, MEHC is halved at best when $\beta$ is made arbitrarily close
to zero. Noting that the original MDP $M$ is equivalent to $M^{\varphi}$
shaped with potential $-\varphi$, i.e. $M=(M^{\varphi})^{-\varphi}$ from (9),
we see that MEHC can be almost doubled. It turns out that halving or doubling
the MEHC is the most PBRS can do in a large class of MDPs.

######  Theorem 2.3 (MEHC under PBRS).

Given an MDP $M$ with finite maximum expected hitting cost $\kappa(M)<\infty$
and an unsaturated optimal average reward $\rho^{*}(M)<r_{\text{max}}$, the
maximum expected hitting cost of any PBRS-parameterized MDP $M^{\varphi}$ is
bounded by a multiplicative factor of two

$\frac{1}{2}\kappa(M)\leq\kappa(M^{\varphi})\leq 2\kappa(M).$

The key observation is that the expected total rewards along a loop remains
unchanged by shaping, which originally motivated PBRS [NHR99]. To see this,
consider a loop as a concatenation of two paths, one from $s$ to $s^{\prime}$
and the other from $s^{\prime}$ to $s$. Under the shaping of a potential
$\varphi$, the expected total rewards of the former is increased by
$\varphi(s^{\prime})-\varphi(s)$ and the latter is decreased by the same
amount. For more details, see Appendix 2.

###  3 Discussion

If we view RL as an engineering tool that “compiles” an arbitrary reward
function into a behavior (as represented by a policy) in an environment, then
a programmer’s primary responsibility would be to craft a reward function that
faithfully expresses the intended goal. However, this problem of reward design
is complicated by practical concerns for the difficulty of learning. As
recognized by [KBP13, section 3.4 ],

> “[t]here is also a trade-off between the complexity of the reward function
> and the complexity of the learning problem.”

Accurate rewards are often easy to specify in a sparse manner (reaching a
position, capturing the king, etc), thus hard to learn, whereas dense rewards,
providing more feedback, are harder to specify accurately, leading to
incorrect trained behaviors. The recent rise of deep RL also exposes “bugs” in
some of these designed rewards [CA16]. Our results show that the
informativeness of rewards, an aspect of “the complexity of the learning
problem” can be controlled to some extent by a well specified potential
without inadvertently changing the intended behaviors of the original reward.
Therefore, we propose to separate the definitional concern from the training
concern. Rewards should be first defined to faithfully express the intended
task, and then any extra knowledge can be incorporated via a shaping potential
to reduce the sample complexity of training to obtain the same desired
behaviors. That is not to say that it is generally easy to find a helpful
potential making the rewards more informative.

Though Theorem 2.3 might be a disappointing result for PBRS, we wish to
emphasize that this result most directly concerns algorithms whose regrets
scale with MEHC, such as UCRL2. It is conceivable that in a different setting
such as discounted total rewards, or for a different RL algorithm, such as
SARSA with epsilon-greedy exploration [NHR99, footnote 4], PBRS might have a
greater impact on the learning efficiency.

##  Chapter 3 Safety, recoverability, and multiple rewards

We shall first reflect on the idea of acting safely. Sometimes an action can
make changes that cannot be undone within the capability of the agent, e.g.,
dropping and breaking a glass with only some glue at our disposal. The
qualification of capability is important as classical physics is fundamentally
reversible albeit sometimes at the cost of a large amount of work. We can
model such situations in a dynamical model such as an MDP by considering
whether a state can be reached from another under some policy. In a
communicating MDP, by definition, we can reach all the states from all other
states (in some steps at some cost). Thus in order to model the absence of
full reachability, we need to relax the assumption of communication and
consider multichain MDPs.

###  1 Irrecoverable MDPs

More concretely, a multichain MDP has a state space that can be partitioned
into components such that we cannot reach some components starting in another
component. The actions that take us from one such component to another demand
special care since we would not able to return to the first component. So far,
the discussion is based on the reachability of states but we would not mind if
such an irreversible transition takes place if the second component is as
rewarding as the initial one. Some of the irreversible change might in fact be
desired, e.g., mixing cream in a cup of coffee. Therefore, we shall focus on
the difference in the long-term rewards of the components which is the gain in
the average reward setting. We shall refer to a multichain MDP _irrecoverable_
if its components do not have the same optimal gain.

######  Definition 1.1 (Recoverability).

An MDP $\mu$ is _recoverable_ if
$\max_{s}g^{*}(\mu,s)-\min_{s^{\prime}}g^{*}(\mu,s^{\prime})=0$.

This concept of safety resembles _controllability_ in control theory but a key
difference is that we are ultimately concerned with whether rewards can be
recovered. As we have seen previously, a communicating MDP has a constant
optimal gain, and thus recoverable. Another related reward-based concept is
robustness where we wish to act defensively against bad luck. This can be
formalized by evaluating a policy more conservatively by its cumulative
rewards at some percentile rather by the expectation, i.e., its value.
Examples are value at risk (VaR) and conditional value at risk (CVaR).
Robustness is inherently statistical whereas recoverability is dynamical and
thus they are semantically orthogonal to each other. Value stability is a
condition similar to recoverability proposed by [RH08]. It concerns whether
the loss of rewards can be restored in more general processes. They
established a general notion of learning and adaptation in such value stable
(recoverable) environments. In contrast, we are more interested in notions of
learning in an irrecoverable environment.

The regret we used in Chapter 2 does not work for irrecoverable environments
as we cannot hope to achieve sublinear regret due to the presence of states
with lower optimal gains. The benchmark used in its definition crucially
depends on the MDP being communicating and thus all states have the same
optimal gain. One way to extend the regret over communicating MDPs to
multichain MDPs is to account for regret over different sample paths by
allowing multiple starts. In such framework, we can think of the multiple
starts corresponding to multiple agents acting in replica of the same
environment. In such regret over both starts and steps where we would be more
concerned with achieving sublinear regret over starts.

Given a set of ongoing trajectories, say
$\\{\left(S_{t},A_{t},R_{t}\right)_{t\leq t_{i}}:i=0,\dots,K\\}$, it is not
immediately clear which action(s) we get to decide next or if we can decide to
start an entirely new trajectory. The different answers to these questions
would result in different specifications that should be driven by the
applications being modeled. For example, if we think of each trajectory
corresponding to a patient in a medical treatment trial, then at each step, we
need to decide treatments for all existing patients and a new trajectory is
created upon a new patient’s arrival. This seems like a demanding scenario. On
the opposite end, during robotic controller development in a simulatior, we
may be able to decide which simulation to advance and which to pause, and we
can decide to spawn another replica altogether.

Even though there can be a variety of learning protocols involving multichain
MDPs, we suspect that there is a lower bound on expected regret that is (at
least) linear in the number of subchains of the actual MDP. We based this
conjecture on lower bounds in MAB by turning each arm into a subchain.

###  2 Resets and reset-efficient RL

Non-catastrophic mistakes are common and important to deal with in practice as
mistakes imply costs. We seek to model such mistakes that cannot be corrected
by a robot but can restored by costly interventions of an operator. This is
particularly relevant during the development of a controller which aims to
avoid catastrophes in deployment. Developing an optimal controller for an
unknown irrecoverable environment is challenging as there are actions that can
entrap us in a low rewarding subchain. This sets a harsh limit on learning as
it is impossible to behave well in states that we cannot revisit (see Section
1).

Furthermore, such restrictive learning protocol does not model practical
development processes well. During the development of controllers,
interventions by human operators (or other equipments) such as replacing
excessively worn robot parts or clearing workspaces are routinely performed.
The availability of such interventions effectively forgives an agent of
mistakes by bringing the system to a specified state by actions beyond the
system’s capability. Naturally in such setting, we would want to design
learning algorithms that utilize these often costly interventions sparingly.
We shall call these interventions which restore the system to a distinguished
state deterministically _resets_.

Formally, we call an MDP as a _reset-equipped MDP_ if it contains a
distinguished state $s_{i}$ called the _initial state_ and a distinguished
action RESET that deterministically transitions the MDP to $s_{i}$ with zero
reward.

######  Definition 2.1 (reset-equipped MDP).

Given a state space $\mathcal{S}$, an _initial state_ $s_{i}\in\mathcal{S}$,
an action space $\mathcal{A}$, a distinguished action
$\texttt{RESET}\in\mathcal{A}$, an action sequence $(A_{t})_{t\geq 0}$ where
$A_{t}\in\mathcal{A}$, a transition kernel
$p:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{P}\left(\mathcal{S}\right)$,
and rewards
$r:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{P}\left(\left[0,r_{\text{max}}\right]\right)$,
the resulting process $\left(S_{t},A_{t},R_{t}\right)_{t\geq 0}$ is a _reset-
equipped MDP_ if $\left(S_{t},A_{t},R_{t}\right)_{t\geq 0}$ is an MDP, and
that RESET deterministically transition the MDP to the initial state $s_{i}$
with zero rewards, i.e.,

$\mathbb{P}\left[S_{t+1}=s_{i}|S_{t}=s,A_{t}=\texttt{RESET}\right]=1\text{ and
}\mathbb{P}\left[R_{t}=0|A_{t}=\texttt{RESET}\right]=1\text{ for any $s$ and
$t$}.$

If $\mu=\left(\mathcal{S},\mathcal{A},p,r\right)$ is an irrecoverable MDP and
$\tilde{\mu}=\left(\mathcal{S},\mathcal{A}\cup\left\\{\texttt{RESET}\right\\},\tilde{p},\tilde{r},s_{i}\right)$
an reset-equipped MDP where $\tilde{p}(s,a)=p(s,a)$ and
$\tilde{r}(s,a)=r(s,a)$ whenever $a\neq\texttt{RESET}$, then we say
$\tilde{\mu}$ is reset-augmented from $\mu$, and $\mu$ is reset-restricted
from $\tilde{\mu}$.

The essential challenge of “irrecoverable” actions posed to learning is
recognized in earlier works [Ber+17, MA12]. But prior works [Ber+17, MA12]
define “recoverability” more narrowly via transitions, i.e., if a state can be
revisited after taking an action, whereas we more broadly consider if the same
rewards can still be obtained. Another limitation is that due to the lack of
resets, prior works relied on assumptions of detailed knowledge about the
possible environments (through Gaussian process over deterministic dynamics
[Ber+17], or Bayesian priors over finite MDPs [MA12]) to avoid taking any
actions that are risky in any possible environment. On one hand, this seems
overly conservative for an adaptive agent, and on the other hand, it seems to
contradict the central tenant of ignorance in learning by demanding detailed
prior knowledge about all possible environments. In summary, without an
assumption of some mechanism to “forgive” a mistake, these prior studies are
more appropriate for modeling the most critical of errors that are truly
impossible to recover from in any meaningful sense (even during learning).

By making a mechanism to restart an otherwise irrecoverable MDP available to
the algorithm, we can evaluate different learning algorithms by how they
utilize resets besides other reward-based metrics such as regret. The first
concern is the choice of benchmark (policy) in this setting. In general, the
reset-augmented MDP $\tilde{\mu}$ has a higher optimal gain than the original
MDP $\mu$ due to the additional reset actions. In particular, if
$g^{*}(\tilde{\mu},s_{i})>g^{*}(\mu,s_{i})$, it implies that all optimal
policies have to reset sometimes when starting in $s_{i}$. This is not the
situation we intend to model: the trained policy has no access to resets in
deployment. So we shall restrict our attention to suitable MDPs and postpone
discussion of the more general case to the next section.

######  Assumption 2.1.

The optimal gain of the initial state is not increased by the availability of
resets $g^{*}(\mu,s_{i})=g^{*}(\tilde{\mu},s_{i})$.

We refer to this assumption as _the hazardous setting_ and our benchmark
policy would be one that achieves the optimal gain on $s_{i}$ without
utilizing any resets. To evaluate learning algorithms, we shall consider both
their regret and their use of resets. In fact, we can think of the latter as a
regret for the reward function
$r(s,a)=-\mathbbm{1}\left[a=\texttt{RESET}\right]$. We have two kinds of
rewards and our hazardous setting assumption ensures that the benchmarks,
optimal gain and zero reset rate, are achieved by the same policy. Technically
speaking, this assumption keeps us from considering the general setting with
multiple reward functions, which we will discuss in Section 3.

To avoid technical complications nonessential to the issue at hand such as a
disconnected state space, we make some regularity assumptions on the reset-
augmented MDPs.

######  Assumption 2.2 (One-way reachability).

For any state $s\in\mathcal{S}$, there exists a policy $\pi$ such that we can
reach $s$ starting in the initial state $s_{i}$ with some non-negligible
probability.

######  Assumption 2.3 (Non-transient initial state).

The initial state $s_{i}$ is not a transient state.

It is not a coincident that we call the special action reset, the same as an
API call in the popular OpenAI gym [Bro+16]. In a gym environment and some
formulation of MDPs [SB98], some states are _absorbing_ , meaning that an MDP
in those states transitions deterministically to the same states (with zero
rewards). This is a special case of a MDP subchain which contains only a
single state. In the gym environment, the environment would inform the agent
whether the current state is absorbing via a “terminal” indicator variable.
When encountering an absorbing state, the agent is expected to call a “reset”
API to return to a prescribed initial state or distribution of states. This is
exactly what an agent sufficiently certain of itself being in a sub-optimal
subchain should do in our proposed framework. Through the lens of comparison,
we can think of our model as a generalization of an absorbing state with zero
rewards to a subchain with sub-optimal gain which can have a complex MDP
structure involving many states and actions. Furthermore, the agent must learn
through interactions whether it is in such a sub-optimal subchain.

Specifically, we empirically tested UCRL2, an improved variant of UCRL2 with
empirical Bernstein bounds [FPL20], and our proposed algorithm Reset-UCRL.

Since reset-equipped MDPs are communicating, we can directly apply UCRL2. But
this is not a good solution as it does not incorporate our knowledge of the
RESET actions.

We benefit heavily from UCRL2’s explicit representation of the estimated MDP
parameters _and_ the confidence about them. Specifically, we can supply the
true transition probabilities and rewards associated with RESET and eliminate
the uncertainty about those parameters in the extended MDP that UCRL2 solves
in its extended value iteration routine (Algorithm 2).

Algorithm 2 Extended value iteration of Reset-UCRL

1: Input: Initial state $s_{i}$, reset actions, extended MDP, tolerance
$\delta$.

2: Return: Optimistic MDP and its near-optimal policy.

3: Set the empirical transition probabilities of reset actions in the extended
MDP to be one if the next state is $s_{i}$ and zero otherwise.

4: Set the empirical immediate reward of reset actions to be zero.

5: Set the confidence bounds of transitions and rewards of reset actions to be
zero.

6: return Run the extended value iteration algorithm with the modified
extended MDP and tolerance $\delta$.

As we have touched on the connection to gym environments earlier, if the
environment provides a terminal signal for some states, we can easily
incorporate that information into the estimated model parameters. The explicit
representation of the environment parameters (and our confidence) of model-
based nature of UCRL2 provides intuitive ways to encode our knowledge about
the environment.

In numerical experiments111Details of the MDP we used is deferred to Appendix
5.C., as we expect, all three algorithms steadily improve their average
rewards (see Figure 3) as their resets plateau (see Figure 1 and Figure 2).
But clearly Reset-UCRL has both superior rewards and resets. (All trajectories
share the same random seed.) More strikingly, we see that Reset-UCRL does not
reset at all in the optimal sub-chain (see Figure 4). This is how an agent
that knows whether it is in the optimal sub-chain should behave but Reset-UCRL
does the same without such knowledge. Its avoidance of unnecessary resetting
over these states is a consequence that the uncertainty-free parameters about
resets naturally makes them unattractive alternatives.

Figure 1: Typical cumulative resets over steps. Figure 2: Typical running
averages of resets over steps. Figure 3: Typical running averages of rewards
over steps. Figure 4: Typical cumulative resets in the optimal sub-chain.

###  3 Planning with multiple rewards

Without the restriction of Assumption 2.1, we consider MDPs where resetting
can potentially improve the gain of the initial state. This can model problems
involving maintenance for example which may tradeoff between productivity and
maintenance savings.

A useful observation is that the asymptotic average reset can be written as a
negative reward by defining another reward function
$r_{\text{reset}}(s,a)\coloneqq-\mathbbm{1}\left[a=\texttt{RESET}\right]$. The
negative sign enforces the reward convention and the semantics that fewer
resets are preferred. We can define the _reset gain_ as the gain with respect
to $r_{\text{reset}}$

$\rho(\tilde{\mu},\pi,s)\coloneqq\lim_{n\rightarrow\infty}\frac{1}{n}\mathbb{E}^{\pi}_{s}\left[\sum_{t=1}^{n}r_{\text{reset}}\left(S_{t},A_{t}\right)\right].$

This observation reveals the multi-objective nature of the problem and more
specifically, an MDP with two _kinds_ of rewards. It is natural to consider an
alternative notion of optimality, namely, _(local) Pareto optimality_ over the
two (or more) objectives, $g(\tilde{\mu},\cdot,s_{i})$ and
$\rho(\tilde{\mu},\cdot,s_{i})$. Instead of searching for a policy maximizing
one of the objectives (or a positive linear combination of them), one might
ask for a (locally) Pareto optimal policy.

######  Definition 3.1 (locally Pareto optimality).

For a metric space $\mathcal{X}$ and a set of (differentiable) objectives
$\\{f_{i}\\}$ where $f_{i}:\mathcal{X}\rightarrow\mathbb{R}$,
$x\in\mathcal{X}$ is _locally Pareto-optimal_ if there is some neighborhood
$N$ around $x$ such that for any $y\in N$, if $f_{i}(y)>f_{i}(x)$ for some $i$
then there is some $j$ such that $f_{j}(y)<f_{j}(x)$, i.e., $y$ does not
dominate $x$.

In a break from the previous sections, we focus on the planning problem where
the MDP parameters $p,r$ are known and we study the search/optimization
problem. To setup for the optimization problem, we expand the policy class to
be stochastic $\mathcal{S}\rightarrow\mathcal{P}(\mathcal{A})$.

As research interest in RL over increasingly complex environments grows,
partly driven by a pursuit of artificial general intelligence, we should
recognize that it is unnatural to rank policies linearly in some control
problems. Pareto optimality is natural extension of the optimality of a single
objective when there are multiple objectives. It induces a partial order over
policies, and the resulting Pareto frontier offers a rich set of “good”
policies trading off different performance criteria efficiently. We will
continue the discussion of multiple objectives at the more general level of
having multiple reward functions mostly ignoring the specifics of the reset
gain other than noting that the hazardous setting implies a special Pareto
frontier that maximizes two objectives simultaneously. In prior works, dealing
with multiple reward functions is sometimes referred to as a vector-valued MDP
[Fur80].

A straightforward metric to quantify the (local) suboptimality of multiple
objectives would be $\ell_{\infty}$ metric which corresponds to the condition
that there does not exist any (neighboring) policy that significantly improves
some objectives without lowering some. Our goal in planning is to find a near-
locally Pareto-optimal policy given the MDP parameters efficiently (in
computation).

In another break from previous problem settings with single-reward MDPs, we
need to consider stochastic Markov policies seriously as they can provide some
Pareto-efficient solutions with gains that no deterministic Markov policies
can attain (see Figure 5 for an example).

Figure 5: Gains of some stochastic policies (colored in blue) and _all_
deterministic policies (colored in red). This illustrates the feasible gains
of a particular MDP with two reward functions.

The compact solution domain consisted of stochastic policies
$\prod_{s\in\mathcal{S}}\mathcal{P}\left(\mathcal{A}_{s}\right)$ naturally
suggests local search methods. There are two primary difficulties in this
approach. Firstly, it is not obvious how to efficiently obtain a gradient of
the gain with respect to the policy due to the presence of limit in the
definition of gain (Definition 3.2). Secondly, after obtaining gradients for
each gain, we still need to decide on how to change the policy.

Recall that following a Markov policy in an MDP induces an MRP with transition
probabilities and rewards that is weighted by the action probabilities of the
policy. The gain can be written as the inner product between the stationary
distribution and the rewards. By exploiting a clever observation of [PD12] (in
the study of iterated prisoner’s dilemma), we can calculate this inner product
by computing the determinant of a matrix formed by the transition and the
reward of the MRP under some condition (Assumption 3.1). The algebraic
characterization allows us to differentiate and efficiently compute the exact
gradient from a policy. Implementation-wise, this can be done with the help of
automatic differentiation software.

######  Assumption 3.1.

For a stochastic matrix, the multiplicity of its eigenvalue of $1$ is one
which implies that it has a unique stationary distribution.

For an MRP of $S$ states, suppose that its transition matrix is
$\mathbf{P}\in\mathbb{R}^{S\times S}$ and the reward is a column vector
$\mathbf{r}\in\mathbb{R}^{S\times 1}$. If $\mathbf{P}$ satisfies Assumption
3.1, and its unique stationary distribution is
$\mathbf{\sigma}\in\mathbb{R}^{1\times S}$, then we can write the inner
product as

$\mathbf{\sigma}\mathbf{r}=\frac{\det\begin{bmatrix}P_{11}-1&P_{12}&\dots&P_{1(S-1)}&r_{1}\\\
P_{21}&P_{22}-1&\dots&P_{2(S-1)}&r_{2}\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\
P_{S1}&\dots&&P_{S(S-1)}&r_{S}\end{bmatrix}}{\det\begin{bmatrix}P_{11}-1&P_{12}&\dots&P_{1(S-1)}&1\\\
P_{21}&P_{22}-1&\dots&P_{2(S-1)}&1\\\ \vdots&\vdots&\ddots&\vdots&\vdots\\\
P_{S1}&\dots&&P_{S(S-1)}&1\end{bmatrix}}.$ (1)

######  Remark.

If Assumption 3.1 does not hold, then we may have different gains depending on
which state we start at. Furthermore, the denominator of (1) would be zero.

Next, being true to the philosophy of non-linear orderings, we try to find a
direction in the policy (tangent) space that improve all gains simultaneously.
Such direction exists only if the intersection of all the positive half spaces
formed by the gradients is non-empty. If the intersection is empty, we are at
a locally Pareto-optimal solution. We find a direction by solving a
feasibility linear program by encoding the positive half spaces as linear
inequality constraints. The constraints on the search domain (as a subset of
$\mathbb{R}^{SA}$) can also be principally incorporated in the linear program
as additional linear inequality constraints.

Algorithm 3 Direct-cone policy optimization

1: Input: multi-reward MDP parameters $\mathbf{P}$, $\\{\mathbf{r}_{k}\\}$,
and initial stochastic policy $\pi(a|s)$.

2: Return: a near-locally Pareto-optimal policy.

3: Let the current iterate be the initial policy $\pi$.

4: while not convergent do

5: Project MDP transitions into an MRP transition matrix with the current
policy.

6: for each reward function $\mathbf{r}_{k}$ do

7: Project the MDP reward function into an MRP reward function with the
current policy.

8: Compute the gain $g_{k}$ using (1).

9: Differentiate gain $g_{k}$ with respect to the action probabilities
$\pi(a|s)$ to obtain a gradient $\nabla_{\pi}g_{k}$.

10: end for

11: Solve a feasibility linear program to find a vector inside the
intersection of positive half spaces induced by gradients
$\\{\nabla_{\pi}g_{k}\\}$.

12: if not feasible then

13: return the current iterate.

14: end if

15: Line search and increment the current iterate respecting the policy space.

16: end while

17: return the current iterate.

We can see from a run of the proposed direct-cone policy optimization
algorithm, the iterates quickly converged to a policy on the Pareto frontier
(see Figure 6). Notably, the iterates converged to a stochastic policy
(compare with Figure 5). For more details of the numerical experiments, see
Appendix 5.D.

Figure 6: The gains of iterates of a run of the proposed Direct-cone policy
optimization algorithm color-coded from dark blue to bright yellow. The blue
dots are gains of some stochastic policies as seen in Figure 5.

With the capability of finding a policy on (or near) the Pareto frontier, we
can also traverse (close to) the frontier in search of Pareto-efficient
policies with different gains. In particular, we can “steer” the early
iterates towards improving only a subset of gains by excluding the rest from
the linear program.

An interesting future work in this direction would be to construct a regret
framework that can handle multiple types of regrets. We found it difficult to
come up with a sensical regret notion since there are many “good” policies in
this setting.

##  Chapter 4 Concluding thoughts

As we have seen in the results presented, instance-specific bounds often
provide insights into what makes an MDP complex. Furthermore, these
transition-based and reward-based constants help us understand the behaviors
and limitations of our learning algorithms. We think that structures of MDPs
deserve more attention in RL. MDPs can be very challenging to learn in general
but many MDPs in practice have structures that can be exploited. For example,
the loop estimator exploits the fact that we can revisit the same state
quickly in some MDPs. It may be possible to efficiently solve MDPs that is
simple with respect to some other dynamical constants.

RL algorithms that explicitly represent the MDP parameters may suffer from a
high space complexity in comparison to so-called “model-free” RL algorithms as
in the case of the model-based estimator vs the TD estimators. But as the loop
estimator has shown, there may be other ways to be “model-based” without
estimating all model parameters. By taking the Markov property seriously and
estimating a smaller set of parameters, we are able to obtain statistical and
computational benefits. In particular, the loop estimator indirectly estimates
the transitions by estimating the interarrival times. The connection between
transition probabilities and time is a core topic in the study of Markov
chains and we believe that such connections may lead to novel RL algorithms.

Besides statistical efficiency, model-based RL algorithms also tend to offers
algorithm designers clear ways to encode extra knowledge about the actual MDP
if they are available. We exploit this advantage to adapt UCRL2 to the setting
of reset-equipped MDPs.

While all the works contained herein may benefit from more research, we are
particularly excited by the future development of learning protocols of
multichain MDPs, of multi-reward MDPs, and RL algorithms specialized to non-
generic MDPs. Beyond RL, machine learning problems that involve multiple
objectives seem very relevant to practical applications.

## References

  * [ACF02] Peter Auer, Nicolò Cesa-Bianchi and Paul Fischer  “Finite-Time Analysis of the Multiarmed Bandit Problem”  In _Machine Learning_ 47.2–3 USA: Kluwer Academic Publishers, 2002, pp. 235–256  DOI: 10.1023/A:1013689704352
  * [AF99] David Aldous and James Fill  “Reversible Markov chains and random walks on graphs” Book in preparation (available at http://www.stat.berkeley.edu/~aldous/RWG/Chap2.pdf)  Berkeley, 1999
  * [ALZ08] John Asmuth, Michael L Littman and Robert Zinkov  “Potential-based Shaping in Model-based Reinforcement Learning.”  In _Proceedings of the National Conference on Artificial Intelligence (AAAI)_ , 2008, pp. 604–609
  * [Ber+17] Felix Berkenkamp, Matteo Turchetta, Angela Schoellig and Andreas Krause  “Safe model-based reinforcement learning with stability guarantees”  In _Advances in neural information processing systems_ , 2017, pp. 908–918
  * [Bro+16] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang and Wojciech Zaremba  “OpenAI Gym”, 2016  eprint: arXiv:1606.01540
  * [BT02] Ronen I Brafman and Moshe Tennenholtz  “R-max-a general polynomial time algorithm for near-optimal reinforcement learning”  In _Journal of Machine Learning Research_ 3.Oct, 2002, pp. 213–231
  * [BT09] Peter L Bartlett and Ambuj Tewari  “REGAL: A regularization based algorithm for reinforcement learning in weakly communicating MDPs”  In _Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI)_ , 2009, pp. 35–42  AUAI Press
  * [BT96] Dimitri P Bertsekas and John N Tsitsiklis  “Neuro-dynamic programming”  Athena Scientific Belmont, MA, 1996
  * [CA16] Jack Clark and Dario Amodei  “Faulty Reward Functions in the Wild”, 2016  URL: https://openai.com/blog/faulty-reward-functions/
  * [Clo96] Jeffery Allen Clouse  “On Integrating Apprentice Learning and Reinforcement Learning”, 1996  URL: http://scholarworks.umass.edu/dissertations/AAI9709584
  * [DC17] Falcon Z Dai and Zheng Cai  “Glyph-aware Embedding of Chinese Characters”  In _Proceedings of Empirical Methods of Natural Language Processing_ , 2017, pp. 64
  * [DC19] Falcon Z Dai and Zheng Cai  “Towards Near-imperceptible Steganographic Text”  In _Proceedings of Association for Computational Linguistics_ Association for Computational Linguistics, 2019
  * [Der70] Cyrus Derman  “Finite state Markovian decision processes”  Academic Press, 1970
  * [DS94] Peter Dayan and Terrence J Sejnowski  “TD ($\lambda$) converges with probability 1”  In _Machine Learning_ 14.3 Springer, 1994, pp. 295–301
  * [DW19] Falcon Z Dai and Matthew R Walter  “Maximum Expected Hitting Cost of a Markov Decision Process and Informativeness of Rewards”  In _Advances in Neural Information Processing Systems_ , 2019, pp. 7677–7685  URL: https://arxiv.org/abs/1907.02114
  * [DW21] Falcon Z Dai and Matthew R Walter  “Loop Estimator for Discounted Values in Markov Reward Processes”  In _Proceedings of Association for the Advancement of Artificial Intelligence Conference_ Association for the Advancement of Artificial Intelligence, 2021  URL: https://arxiv.org/abs/2002.06299
  * [EM03] Eyal Even-Dar and Yishay Mansour  “Learning rates for Q-learning”  In _Journal of machine learning Research_ 5.Dec, 2003, pp. 1–25
  * [FG89] Bennett L Fox and Peter W Glynn  “Simulating discounted costs”  In _Management Science_ 35.11 INFORMS, 1989, pp. 1297–1315
  * [FL68] B.. Fox and D.. Landi  “Scientific Applications: An Algorithm for Identifying the Ergodic Subchains and Transient States of a Stochastic Matrix”  In _Commun. ACM_ 11.9 New York, NY, USA: Association for Computing Machinery, 1968, pp. 619–621  DOI: 10.1145/364063.364082
  * [FLP19] Ronan Fruit, Alessandro Lazaric and Matteo Pirotta  “Exploration-Exploitation in Reinforcement Learning”, Tutorial at Algorithmic Learning Theory conference, 2019  URL: https://rlgammazero.github.io/docs/2019_ALT_exptutorial.pdf
  * [FPL18] Ronan Fruit, Matteo Pirotta and Alessandro Lazaric  “Near optimal exploration-exploitation in non-communicating markov decision processes”  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2018, pp. 2994–3004
  * [FPL20] Ronan Fruit, Matteo Pirotta and Alessandro Lazaric  “Improved Analysis of UCRL2 with Empirical Bernstein Inequality”  arXiv, 2020  URL: https://arxiv.org/abs/2007.05456
  * [Fru+18] Ronan Fruit, Matteo Pirotta, Alessandro Lazaric and Ronald Ortner  “Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning”  In _Proceedings of the International Conference on Machine Learning (ICML)_ , 2018, pp. 1573–1581
  * [Fur80] Nagata Furukawa  “Characterization of optimal policies in vector-valued Markovian decision processes”  In _Mathematics of operations research_ 5.2 INFORMS, 1980, pp. 271–279
  * [GLD00] Robert Givan, Sonia Leach and Thomas Dean  “Bounded-parameter Markov decision processes”  In _Artificial Intelligence_ 122.1–2 Elsevier, 2000, pp. 71–109
  * [GMK13] Mohammad Gheshlaghi Azar, Rémi Munos and Hilbert J. Kappen  “Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model”  In _Machine Learning_ 91.3, 2013, pp. 325–349  DOI: 10.1007/s10994-013-5368-1
  * [Grz17] Marek Grześ  “Reward shaping in episodic reinforcement learning”  In _Proceedings of the International Conference on Autonomous Agents and MultiAgent Systems (AAMAS)_ , 2017, pp. 565–573  International Foundation for Autonomous AgentsMultiagent Systems
  * [How60] Ronald A Howard  “Dynamic programming and Markov processes.”  John Wiley, 1960
  * [HP92] Moshe Haviv and Martin L Puterman  “Estimating the value of a discounted reward process”  In _Operations Research Letters_ 11.5, 1992, pp. 267–272  DOI: 10.1016/0167-6377(92)90002-K
  * [JJS94] Tommi Jaakkola, Michael I Jordan and Satinder P Singh  “Convergence of stochastic iterative dynamic programming algorithms”  In _Advances in Neural Information Processing Systems_ , 1994, pp. 703–710
  * [JOA10] Thomas Jaksch, Ronald Ortner and Peter Auer  “Near-optimal regret bounds for reinforcement learning”  In _Journal of Machine Learning Research_ 11.Apr, 2010, pp. 1563–1600
  * [Kak03] Sham Machandranath Kakade  “On the sample complexity of reinforcement learning”, 2003
  * [KBP13] Jens Kober, J Andrew Bagnell and Jan Peters  “Reinforcement learning in robotics: A survey”  In _The International Journal of Robotics Research_ 32.11 SAGE Publications Sage UK: London, England, 2013, pp. 1238–1274
  * [KS00] Michael J Kearns and Satinder P Singh  “Bias-Variance Error Bounds for Temporal Difference Updates”  In _Conference on Learning Theory_ , 2000, pp. 142–147
  * [KS02] Michael Kearns and Satinder Singh  “Near-optimal reinforcement learning in polynomial time”  In _Machine learning_ 49.2-3 Springer, 2002, pp. 209–232
  * [KS99] Michael J Kearns and Satinder P Singh  “Finite-sample convergence rates for Q-learning and indirect algorithms”  In _Advances in Neural Information Processing Systems_ , 1999, pp. 996–1002