# Average-reward model-free reinforcement learning:
a systematic review and literature mapping

Vektor Dewanto  School of Information Technology and Electrical Engineering,
University of Queensland, AU  George Dunn  School of Mathematical and Physical
Sciences, University of Newcastle, AU  Ali Eshragh  School of Mathematical and
Physical Sciences, University of Newcastle, AU  International Computer Science
Institute, Berkeley, CA, USA  Marcus Gallagher  School of Information
Technology and Electrical Engineering, University of Queensland, AU  Fred
Roosta  School of Mathematics and Physics, University of Queensland, AU
International Computer Science Institute, Berkeley, CA, USA

###### Abstract

Reinforcement learning is important part of artificial intelligence. In this
paper, we review model-free reinforcement learning that utilizes the average
reward optimality criterion in the infinite horizon setting. Motivated by the
solo survey by Mahadevan, 1996a , we provide an updated review of work in this
area and extend it to cover policy-iteration and function approximation
methods (in addition to the value-iteration and tabular counterparts). We
present a comprehensive literature mapping. We also identify and discuss
opportunities for future work.

##  1 Introduction

Reinforcement learning (RL) is one promising approach to the problem of making
sequential decisions under uncertainty. Such a problem is often formulated as
a Markov decision process (MDP) with a state set $\mathcal{S}$, an action set
$\mathcal{A}$, a reward set $\mathcal{R}$, and a decision-epoch set
$\mathcal{T}$. At each decision-epoch (i.e. timestep) $t\in\mathcal{T}$, a
decision maker (henceforth, an agent) is at a state $s_{t}\in\mathcal{S}$, and
chooses to then execute an action $a_{t}\in\mathcal{A}$. Consequently, the
agent arrives at the next state $s_{t+1}$ and earns an (immediate) reward
$r_{t+1}$. For $t=0,1,\ldots,t_{\mathrm{max}}$ with
$t_{\mathrm{max}}\leq\infty$, the agent experiences a sequence of
$S_{0},A_{0},R_{1},S_{1},A_{1},R_{2},\ldots,S_{t_{\mathrm{max}}}$. Here,
$S_{0}$ is drawn from an initial state distribution $p_{s_{0}}$, whereas
$s_{t+1}$ and $r_{t+1}$ are governed by the environment dynamics, which is
fully specified by the state-transition probability
$p(s^{\prime}|s,a)\coloneqq\mathrm{Pr}\\{S_{t+1}=s^{\prime}|S_{t}=s,A_{t}=a\\}$,
and the reward function
$r(s,a,s^{\prime})=\sum_{r\in\mathcal{R}}\mathrm{Pr}\\{r|s,a,s^{\prime}\\}\cdot
r$.

The solution to the decision making problem is a mapping from every state to a
probability distribution over the set of available actions in that state. This
mapping is called a policy, i.e.
$\pi:\mathcal{S}\times\mathcal{A}\mapsto[0,1]$, where
$\pi(a_{t}|s_{t})\coloneqq\mathrm{Pr}\\{A=a_{t}|S_{t}=s_{t}\\}$. Thus, solving
such a problem amounts to finding the optimal policy, denoted by $\pi^{*}$.
The basic optimality criterion asserts that a policy with the largest value is
optimal. That is, $v(\pi^{*})\geq v(\pi),\forall\pi\in\Pi$, where the function
$v$ measures the value of any policy $\pi$ in the policy set $\Pi$. There are
two major ways to value a policy based on the infinite reward sequence that it
generates, namely the average- and discounted-reward policy value
formulations. They induce the average- and discounted-reward optimality
criteria, respectively. For an examination of their relationship, pros, and
cons in RL, we refer the readers to (Dewanto and Gallagher,, 2021).

Furthermore, RL can be viewed as simulation-based asynchronous approximate
dynamic programming (DP) (Gosavi,, 2015, Ch 7). Particularly in model-free RL,
the simulation is deemed expensive because it corresponds to direct
interaction between an agent and its (real) environment. Model-free RL
mitigates not only the curse of dimensionality (inherently as approximate DP
methods), but also the curse of modeling (since no model learning is
required). This is in contrast to model-based RL, where an agent interacts
with the learned model of the environment (Dean et al.,, 2017; Jaksch et al.,,
2010; Tadepalli and Ok,, 1998). Model-free RL is fundamental in that it
encompasses the bare essentials for updating sequential decision rules through
natural agent-environment interaction. The same update machinery can generally
be applied to model-based RL. In practice, we may always desire a system that
runs both model-free and model-based mechanisms, see e.g. the so-called Dyna
architecture (Silver et al.,, 2008; Sutton,, 1990).

This work surveys the existing value- and policy-iteration based average-
reward model-free RL. We begin by reviewing relevant DP (as the root of RL),
before progressing to the tabular then function approximation settings in RL.
For comparison, the solo survey on average-reward RL (Mahadevan, 1996a, )
embraced only the tabular value-iteration based methods. We present our review
in Secs 3 and 4, which are accompanied by concise Tables
LABEL:tbl:valiter_work and LABEL:tbl:politer_work (in Appendix
LABEL:sec:table_of_existing) along with literature maps (Figs
LABEL:fig:taxonomy_optgainapprox, LABEL:fig:taxonomy_gain,
LABEL:fig:taxonomy_stateval, and LABEL:fig:taxonomy_actval in Appendix
LABEL:sec:taxonomy). We then discuss the insight and outlook in Sec 5.
Additionally in Appendix LABEL:sec:problem_spec, we compile environments that
were used for evaluation by the existing works.

In order to limit the scope, this work focuses on model-free RL with a single
non-hierarchical agent interacting _online_ with its environment. We do not
include works that _approximately_ optimize the average reward by introducing
a discount factor (hence, the corresponding approximation error), e.g.
Schneckenreither, (2020); Karimi et al., (2019); Bartlett and Baxter, (2002).
We also choose not to examine RL methods that are based on linear programming
(Wang,, 2017; Neu et al.,, 2017), and decentralized learning automata (Chang,,
2009; Wheeler and Narendra,, 1986).

##  2 Preliminaries

We assume that the problem we aim to tackle can be well modeled as a Markov
decision process (MDP) with the following properties.

  * •

The state set $\mathcal{S}$ and action set $\mathcal{A}$ are finite. All
states are fully observable, and all actions $a\in\mathcal{A}$ are available
in every state $s\in\mathcal{S}$. The decision-epoch set
$\mathcal{T}=\mathbb{Z}^{\geq 0}$ is discrete and infinite. Thus, we have
discrete-time infinite-horizon finite MDPs.

  * •

The state-transition probability $p(s_{t+1}|s_{t},a_{t})$ and the reward
function $r(s_{t},a_{t})$ are both stationary (time homogenous, fixed over
time). Here,
$r(s_{t},a_{t})=\mathbb{E}\mathopen{}\mathclose{{}\left[r(s_{t},a_{t},S_{t+1})}\right]$,
and it is uniformly bounded by a finite constant $r_{\mathrm{max}}$, i.e.
$|r(s,a)|\leq
r_{\mathrm{max}}<\infty,\forall(s,a)\in\mathcal{S}\times\mathcal{A}$.

  * •

The MDP is recurrent, and its optimal policies belong to the stationary policy
set $\Pi_{\mathrm{S}}$.

Furthermore, every stationary policy $\pi\in\Pi_{\mathrm{S}}$ of an MDP
induces a Markov chain (MC), whose transition (stochastic) matrix is denoted
as $\boldsymbol{P}_{\pi}\in[0,1]^{|\mathcal{S}|\times|\mathcal{S}|}$. The
$[s,s^{\prime}]$-entry of $\boldsymbol{P}_{\pi}$ indicates the probability of
transitioning from a current state $s$ to the next state $s^{\prime}$ under a
policy $\pi$. That is,
$\boldsymbol{P}_{\pi}[s,s^{\prime}]=\sum_{a\in\mathcal{A}}\pi(a|s)p(s^{\prime}|s,a)$.
The $t$-th power of $\boldsymbol{P}_{\pi}$ gives $\boldsymbol{P}_{\pi}^{t}$,
whose $[s_{0},s]$-entry indicates the probability of being in state $s$ in $t$
timesteps when starting from $s_{0}$ and following $\pi$. That is,
$\boldsymbol{P}_{\pi}^{t}[s_{0},s]=\mathrm{Pr}\\{S_{t}=s|s_{0},\pi\\}\eqqcolon
p_{\pi}^{t}(s|s_{0})$. The limiting distribution of $p_{\pi}^{t}$ is given by

$p_{\pi}^{\star}(s|s_{0})=\lim_{t_{\mathrm{max}}\to\infty}\frac{1}{t_{\mathrm{max}}}\sum_{t=0}^{t_{\mathrm{max}}-1}p_{\pi}^{t}(s|s_{0})=\lim_{t_{\mathrm{max}}\to\infty}p_{\pi}^{t_{\mathrm{max}}}(s|s_{0}),\quad\forall
s\in\mathcal{S},$ (1)

where the first limit is proven to exist in finite MDPs, while the second
limit exists whenever the finite MDP is aperiodic (Puterman,, 1994, Appendix
A.4). This limiting state distribution $p_{\pi}^{\star}$ is equivalent to the
unique stationary (time-invariant) state distribution that satisfies
$(\boldsymbol{p}_{\pi}^{\star})^{\intercal}\boldsymbol{P}_{\pi}=(\boldsymbol{p}_{\pi}^{\star})^{\intercal}$,
which may be achieved in finite timesteps. Here,
$\boldsymbol{p}_{\pi}^{\star}\in[0,1]^{|\mathcal{S}|}$ is
$p_{\pi}^{\star}(s|s_{0})$ stacked together for all $s\in\mathcal{S}$.

The _expected_ average reward (also termed the gain) value of a policy $\pi$
is defined for all $s_{0}\in\mathcal{S}$ as

$\displaystyle v_{g}(\pi,s_{0})$
$\displaystyle\coloneqq\lim_{t_{\mathrm{max}}\to\infty}\frac{1}{t_{\mathrm{max}}}\mathbb{E}_{S_{t},A_{t}}\mathopen{}\mathclose{{}\left[\sum_{t=0}^{t_{\mathrm{max}}-1}r(S_{t},A_{t})\Big{|}S_{0}=s_{0},\pi}\right]$
(2)
$\displaystyle=\sum_{s\in\mathcal{S}}\Big{\\{}\lim_{t_{\mathrm{max}}\to\infty}\frac{1}{t_{\mathrm{max}}}\sum_{t=0}^{t_{\mathrm{max}}-1}p_{\pi}^{t}(s|s_{0})\Big{\\}}r_{\pi}(s)=\sum_{s\in\mathcal{S}}p_{\pi}^{\star}(s|s_{0})r_{\pi}(s)$
(3)
$\displaystyle=\lim_{t_{\mathrm{max}}\to\infty}\mathbb{E}_{S_{t_{\mathrm{max}}},A_{t_{\mathrm{max}}}}\mathopen{}\mathclose{{}\left[r(S_{t_{\mathrm{max}}},A_{t_{\mathrm{max}}})\Big{|}S_{0}=s_{0},\pi}\right],$
(4)

where $r_{\pi}(s)=\sum_{a\in\mathcal{A}}\pi(a|s)\ r(s,a)$. The limit in (2)
exists when the policy $\pi$ is stationary, and the MDP is finite (Puterman,,
1994, Prop 8.1.1). Whenever it exists, the equality in (3) follows due to the
existence of limit in (1) and the validity of interchanging the limit and the
expectation. The equality in (4) holds if its limit exists, for instance when
$\pi$ is stationary and the induced MC is aperiodic (nonetheless, note that
even if the induced MC is periodic, the limit in (4) exists for certain reward
structures, see Puterman, (1994, Problem 5.2)). In matrix forms, the gain can
be expressed as

$\boldsymbol{v}_{g}(\pi)=\lim_{t_{\mathrm{max}}\to\infty}\frac{1}{t_{\mathrm{max}}}\boldsymbol{v}_{t_{\mathrm{max}}}(\pi)=\lim_{t_{\mathrm{max}}\to\infty}\frac{1}{t_{\mathrm{max}}}\sum_{t=0}^{t_{\mathrm{max}}-1}\boldsymbol{P}_{\pi}^{t}\boldsymbol{r}_{\pi}=\boldsymbol{P}_{\pi}^{\star}\boldsymbol{r}_{\pi},$

where $\boldsymbol{r}_{\pi}\in\real{|\mathcal{S}|}$ is $r_{\pi}(s)$ stacked
together for all $s\in\mathcal{S}$. Notice that the gain involves taking the
limit of the average of the _expected_ total reward
$\boldsymbol{v}_{t_{\mathrm{max}}}$ from $t=0$ to $t_{\mathrm{max}}-1$ for
$t_{\mathrm{max}}\to\infty$.

Since unichain MDPs have a single chain (i.e. a closed irreducible recurrent
class), the stationary distribution is invariant to initial states. Therefore,
$\boldsymbol{P}_{\pi}^{\star}$ has identical rows so that the gain is constant
across all initial states. That is,
$v_{g}(\pi)=\boldsymbol{p}_{\pi}^{\star}\cdot\boldsymbol{r}_{\pi}=v_{g}(\pi,s_{0}),\forall
s_{0}\in\mathcal{S}$, hence
$\boldsymbol{v}_{g}(\pi)=v_{g}(\pi)\cdot\boldsymbol{1}$. The gain $v_{g}(\pi)$
can be interpreted as the stationary reward because it represents the average
reward per timestep of a system in its steady-state under $\pi$.

A policy $\pi^{*}\in\Pi_{\mathrm{S}}$ is gain-optimal (hereafter, simply
called optimal) if

$v_{g}(\pi^{*},\cancel{s_{0}})\geq
v_{g}(\pi,\cancel{s_{0}}),\quad\forall\pi\in\Pi_{\mathrm{S}},\forall
s_{0}\in\mathcal{S},\quad\text{hence}\
\pi^{*}\in\operatorname*{\arg\\!\max}_{\pi\in\Pi_{\mathrm{S}}}v_{g}(\pi)$ (5)

Such an optimal policy $\pi^{*}$ is also a greedy (hence, deterministic)
policy in that it selects actions maximizing the RHS of the average-reward
Bellman _optimality_ equation (which is useful for deriving optimal control
algorithms) as follows,

$v_{b}(\pi^{*},s)+v_{g}(\pi^{*})=\max_{a\in\mathcal{A}}\Big{\\{}r(s,a)+\sum_{s^{\prime}\in\mathcal{S}}p(s^{\prime}|s,a)\
v_{b}(\pi^{*},s^{\prime})\Big{\\}},\quad\forall s\in\mathcal{S},$ (6)

where $v_{b}$ denotes the bias value. It is defined for all
$\pi\in\Pi_{\mathrm{S}}$ and all $s_{0}\in\mathcal{S}$ as

$\displaystyle v_{b}(\pi,s_{0})$
$\displaystyle\coloneqq\lim_{t_{\mathrm{max}}\to\infty}\mathbb{E}_{S_{t},A_{t}}\mathopen{}\mathclose{{}\left[\sum_{t=0}^{t_{\mathrm{max}}-1}\Big{(}r(S_{t},A_{t})-v_{g}(\pi)\Big{)}\Big{|}S_{0}=s_{0},\pi}\right]$
(7)
$\displaystyle=\lim_{t_{\mathrm{max}}\to\infty}\sum_{t=0}^{t_{\mathrm{max}}-1}\sum_{s\in\mathcal{S}}\Big{(}p_{\pi}^{t}(s|s_{0})-p_{\pi}^{\star}(s)\Big{)}r_{\pi}(s)$
(8)
$\displaystyle=\underbrace{\sum_{t=0}^{\tau-1}\sum_{s\in\mathcal{S}}p_{\pi}^{t}(s|s_{0})r_{\pi}(s)}_{\text{the
expected total reward $v_{\tau}$}}-\ \tau
v_{g}(\pi)+\underbrace{\lim_{t_{\mathrm{max}}\to\infty}\sum_{t=\tau}^{t_{\mathrm{max}}-1}\sum_{s\in\mathcal{S}}\Big{(}p_{\pi}^{t}(s|s_{0})-p_{\pi}^{\star}(s)\Big{)}r_{\pi}(s)}_{\text{approaches
0 as $\tau\to\infty$}}$ (9)
$\displaystyle=\sum_{s\in\mathcal{S}}\Big{\\{}\lim_{t_{\mathrm{max}}\to\infty}\sum_{t=0}^{t_{\mathrm{max}}-1}\Big{(}p_{\pi}^{t}(s|s_{0})-p_{\pi}^{\star}(s)\Big{)}\Big{\\}}r_{\pi}(s)=\sum_{s\in\mathcal{S}}d_{\pi}(s|s_{0})r_{\pi}(s),$
(10)

where all limits are assumed to exist, and (7) is bounded because of the
subtraction of $v_{g}(\pi)$. Whenever exchanging the limit and the expectation
is valid in (10), $d_{\pi}(s|s_{0})$ represents the $[s_{0},s]$-entry of the
non-stochastic deviation matrix
$\boldsymbol{D}_{\pi}\coloneqq(\boldsymbol{I}-\boldsymbol{P}_{\pi}+\boldsymbol{P}_{\pi}^{\star})^{-1}(\boldsymbol{I}-\boldsymbol{P}_{\pi}^{\star})$.

The bias $v_{b}(\pi,s_{0})$ can be interpreted in several ways. Firstly based
on (7), the bias is the expected total difference between the immediate reward
$r(s_{t},a_{t})$ and the stationary reward $v_{g}(\pi)$ when a process starts
at $s_{0}$ and follows $\pi$. Secondly from (8), the bias indicates the
difference between the expected total rewards of two processes under $\pi$:
one starts at $s_{0}$ and the other at an initial state drawn from
$p_{\pi}^{\star}$. Put in another way, it is the difference of the total
reward of $\pi$ and the total reward that would be earned if the reward per
timestep were $v_{g}(\pi)$. Thirdly, decomposing the timesteps as in (9)
yields $v_{\tau}(\pi,s_{0})\approx v_{g}(\pi)\tau+v_{b}(\pi,s_{0})$. This
suggests that the bias serves as the intercept of a line around which the
expected total reward $v_{\tau}$ oscillates, and eventually converges as
$\tau$ increases. Such a line has a slope of the gain value. For example in an
MDP with zero reward absorbing terminal state (whose gain is 0), the bias
equals the expected total reward before the process is absorbed. Lastly, the
deviation factor $(p_{\pi}^{t}(s|s_{0})-p_{\pi}^{\star}(s))$ in (10) is non-
zero only before the process reaches its steady-state. Therefore, the bias
indicates the transient performance. It may be regarded as the “transient”
reward, whose values are earned during the transient phase.

For any reference states $s_{\mathrm{ref}}\in\mathcal{S}$, we can define the
(bias) relative value $v_{brel}$ as follows

$v_{brel}(\pi,s)\coloneqq
v_{b}(\pi,s)-v_{b}(\pi,s_{\mathrm{ref}})=\lim_{t_{\mathrm{max}}\to\infty}\\{v_{t_{\mathrm{max}}}(\pi,s)-v_{t_{\mathrm{max}}}(\pi,s_{\mathrm{ref}})\\},\quad\forall\pi\in\Pi_{\mathrm{S}},\forall
s\in\mathcal{S}.$

The right-most equality follows from (7) or (9), since the gain are the same
from both $s$ and $s_{\mathrm{ref}}$. It indicates that $v_{brel}$ represents
the asymptotic different in the expected total reward due to starting from
$s$, instead of $s_{\mathrm{ref}}$. More importantly, the relative value
$v_{brel}$ is equal to $v_{b}$ up to some constant for any $s\in\mathcal{S}$.
Moreover, $v_{brel}(\pi,s=s_{\mathrm{ref}})=0$. After fixing
$s_{\mathrm{ref}}$, therefore, we can substitute $v_{brel}$ for $v_{b}$ in
(6), then uniquely determine $v_{brel}$ for all states. Note that (6) with
$v_{b}$ is originally an underdetermined nonlinear system with $|\mathcal{S}|$
equations and $|\mathcal{S}|+1$ unknowns (i.e. one extra of $v_{g}$).

In practice, we often resort to $v_{brel}$ and abuse the notation $v_{b}$ to
also denote the relative value whenever the context is clear. In a similar
fashion, we call the bias as the relative/differential value. One may also
refer to the bias as relative values due to (8), average-adjusted values (due
to (7)), or potential values (similar to potential energy in physics whose
values differ by a constant (Cao,, 2007, p193)).

For brevity, we often use the following notations, $v_{g}^{\pi}\coloneqq
v_{g}(\pi)\eqqcolon g^{\pi}$, and $v_{g}^{*}\coloneqq v_{g}(\pi^{*})\eqqcolon
g^{*}$, as well as $v_{b}^{\pi}(s)\coloneqq v_{b}(\pi,s)$, and
$v_{b}^{*}(s)\coloneqq v_{b}(\pi^{*},s)$. Here, $v_{b}^{\pi}(s)$ may be read
as the relative state value of $s$ under a policy $\pi$.

##  3 Value-iteration schemes

Based on the Bellman optimality equation (6), we can obtain the optimal policy
once we know the optimal state value
$\boldsymbol{v}_{b}^{*}\in\real{|\mathcal{S}|}$, which includes knowing the
optimal gain $v_{g}^{*}$. Therefore, one approach to optimal control is to
(approximately) compute $\boldsymbol{v}_{b}^{*}$, which leads to the value-
iteration algorithm in DP. The value-iteration scheme in RL uses the same
principle as its DP counterpart. However, we approximate the optimal
(state-)action value
$\boldsymbol{q}_{b}^{*}\in\real{|\mathcal{S}||\mathcal{A}|}$, instead of
$\boldsymbol{v}_{b}^{*}$.

In this section, we begin by introducing the foundations of the value-
iteration scheme, showing the progression from DP into RL. We then cover
tabular methods by presenting how to estimate the optimal action values
iteratively along with numerous approaches to estimating the optimal gain.
Lastly, we examine function approximation methods, where the action value
function is parameterized by a weight vector, and present different techniques
of updating the weights. Table LABEL:tbl:valiter_work (in Appendix
LABEL:sec:table_of_existing) summarizes existing average reward model-free RL
based on the value-iteration scheme.

###  3.1 Foundations

In DP, the basic value iteration (VI) algorithm _iteratively_ solves for the
optimal state value $\boldsymbol{v}_{b}^{*}$ and outputs an
$\varepsilon$-optimal policy; hence it is deemed exact up to the convergence
tolerance $\varepsilon$. The basic VI algorithm proceeds with the following
steps.

  1. Step 1:

Initialize the iteration index $k\leftarrow 0$ and
$\hat{v}_{b}^{k=0}(s)\leftarrow 0$, where $\hat{v}_{b}^{k}(s)\approx
v_{b}^{*}(s),\forall s\in\mathcal{S}$.
Also select a small positive convergence tolerance $\varepsilon>0$.
Note that $\hat{v}_{b}^{k}$ may not correspond to any stationary policy.

  2. Step 2:

Perform updates on _all_ iterates (termed as _synchronous_ updates) as
follows,

$\hat{v}_{b}^{k+1}(s)=\mathbb{B}^{*}\mathopen{}\mathclose{{}\left[\hat{v}_{b}^{k}(s)}\right],\quad\forall
s\in\mathcal{S},$ (Basic VI: synchronous updates)

where the average-reward Bellman optimality operator $\mathbb{B}^{*}$ is
defined as

$\mathbb{B}^{*}\mathopen{}\mathclose{{}\left[\hat{v}_{b}^{k}(s)}\right]\coloneqq\max_{a\in\mathcal{A}}\Big{[}r(s,a)+\sum_{s^{\prime}\in\mathcal{S}}p(s^{\prime}|s,a)\
\hat{v}_{b}^{k}(s^{\prime})\Big{]},\quad\forall s\in\mathcal{S}.$

Clearly, $\mathbb{B}^{*}$ is non-linear (due to the $\max$ operator), and is
derived from (6) with $\hat{v}_{g}^{*}\leftarrow 0$.

  3. Step 3:

If the span seminorm
$sp(\hat{\boldsymbol{v}}_{b}^{k+1}-\hat{\boldsymbol{v}}_{b}^{k})>\varepsilon$,
then increment $k$ and go to Step 2.
Otherwise, output a greedy policy with respect to the RHS of (6); such a
policy is $\varepsilon$-optimal. Here,
$sp(\boldsymbol{v})\coloneqq\max_{s\in\mathcal{S}}v(s)-\min_{s^{\prime}\in\mathcal{S}}v(s^{\prime})$,
which measure the range of all components of a vector $\boldsymbol{v}$.
Therefore, although the vector changes, its span may be constant.

The mapping in Step 2 of the VI algorithm is not contractive (because there is
no discount factor). Moreover, the iterates $\hat{\boldsymbol{v}}_{b}^{k}$ can
grow very large, leading to numerical instability. Therefore, White, (1963)
proposed substracting out the value of an arbitrary-but-fixed reference state
$s_{\mathrm{ref}}$ at every iteration. That is,

$\hat{v}_{b}^{k+1}(s)=\mathbb{B}^{*}\mathopen{}\mathclose{{}\left[\hat{v}_{b}^{k}(s)}\right]-\hat{v}_{b}^{k}(s_{\mathrm{ref}}),\quad\forall
s\in\mathcal{S},$ (Relative VI: synchronous updates)

which results in the so-called _relative_ value iteration (RVI) algorithm.
This update yields the same span and the same sequence of maximizing actions
as that of the basic VI algorithm. Importantly, as $k\to\infty$, the iterate
$\hat{v}_{b}^{k}(s_{\mathrm{ref}})$ converges to $v_{g}^{*}$.

The _asynchronous_ version of RVI may diverge Abounadi et al.,, 2001, p682,
Gosavi,, 2015, p232. As a remedy, Jalali and Ferguson, (1990) introduced the
following update,

$\hat{v}_{b}^{k+1}(s)=\mathbb{B}^{*}\mathopen{}\mathclose{{}\left[\hat{v}_{b}^{k}(s)}\right]-\hat{v}_{g}^{k},\quad\forall(s\neq
s_{\mathrm{ref}})\in\mathcal{S},$ (Relative VI: asynchronous updates)

where $\hat{v}_{g}^{k}$ is the estimate of $v_{g}^{*}$ at iteration $k$, and
$\hat{v}_{b}^{k}(s_{\mathrm{ref}})=0$, for all iterations $k=0,1,\ldots$. It
is shown that this asynchronous method converges to produce a gain optimal
policy in a regenerative process, where there exists a _single_ recurrent
state under _all_ stationary and deterministic policies.

In RL, the reward function $r(s,a)$ and the transition distribution
$p(s^{\prime}|s,a)$ are unknown. Therefore, it is convenient to define a
relative (state-)action value $\boldsymbol{q}_{b}(\pi)$ of a policy $\pi$ as
follows,

$\displaystyle q_{b}(\pi,s,a)$
$\displaystyle\coloneqq\lim_{t_{\mathrm{max}}\to\infty}\mathbb{E}_{S_{t},A_{t}}\mathopen{}\mathclose{{}\left[\sum_{t=0}^{t_{\mathrm{max}}-1}\mathopen{}\mathclose{{}\left(r(S_{t},A_{t})-v_{g}^{\pi}}\right)\Big{|}S_{0}=s,A_{0}=a,\pi}\right]$
$\displaystyle=r(s,a)-v_{g}^{\pi}+\mathbb{E}\mathopen{}\mathclose{{}\left[v_{b}^{\pi}(S_{t+1})}\right],\qquad\forall(s,a)\in\mathcal{S}\times\mathcal{A},$
(11)

where for brevity, we define $q_{b}^{\pi}(s,a)\coloneqq q_{b}(\pi,s,a)$, as
well as $q_{b}^{*}(s,a)\coloneqq q_{b}(\pi^{*},s,a)$. The corresponding
average reward Bellman optimality equation is as follows (Bertsekas,, 2012,
p549),

$q_{b}^{*}(s,a)+v_{g}^{*}=r(s,a)+\sum_{s^{\prime}\in\mathcal{S}}p(s^{\prime}|s,a)\underbrace{\max_{a^{\prime}\in\mathcal{A}}q_{b}^{*}(s^{\prime},a^{\prime}),}_{\text{$v_{b}^{*}(s^{\prime})$}}\quad\forall(s,a)\in\mathcal{S}\times\mathcal{A},$
(12)

whose RHS is in the same form as the quantity maximized over all actions in
(6). Therefore, the gain-optimal policy $\pi^{*}$ can be obtained simply by
acting greedily over the optimal action value; hence, $\pi^{*}$ is
deterministic. That is,

$\pi^{*}(s)=\operatorname*{\arg\\!\max}_{a\in\mathcal{A}}\Big{[}\underbrace{r(s,a)+\sum_{s^{\prime}\in\mathcal{S}}p(s^{\prime}|s,a)\max_{a^{\prime}\in\mathcal{A}}q_{b}^{*}(s^{\prime},a^{\prime})-v_{g}^{*}}_{q_{b}^{*}(s,a)}\Big{]},\qquad\forall
s\in\mathcal{S}.$

As can be observed, $\boldsymbol{q}_{b}^{*}$ combines the effect of
$p(s^{\prime}|s,a)$ and $\boldsymbol{v}_{b}^{*}$, without estimating them
separately at the cost of an increased number of estimated values since
typically $|\mathcal{S}|\times|\mathcal{A}|\gg|\mathcal{S}|$. The benefit is
that action selection via $\boldsymbol{q}_{b}^{*}$ does not require the
knowledge of $r(s,a)$ and $p(s^{\prime}|s,a)$. Note that $v_{g}^{*}$ is
invariant to state $s$ and action $a$; hence its involvement in the above
maximization has no effect.

Applying the idea of RVI on action values $\boldsymbol{q}_{b}^{*}$ yields the
following iterate,

$\displaystyle\hat{q}_{b}^{k+1}(s,a)$
$\displaystyle=\mathbb{B}^{*}\mathopen{}\mathclose{{}\left[\hat{q}_{b}^{k}(s,a)}\right]-v_{b}^{k}(s_{\mathrm{ref}})$
(Relative VI on $\boldsymbol{q}_{b}^{*}$: asynchronous updates)
$\displaystyle=\underbrace{r(s,a)+\sum_{s^{\prime}\in\mathcal{S}}p(s^{\prime}|s,a)\max_{a^{\prime}\in\mathcal{A}}\hat{q}_{b}^{k}(s^{\prime},a^{\prime})}_{\mathbb{B}^{*}\mathopen{}\mathclose{{}\left[\hat{q}_{b}^{k}(s,a)}\right]}-\underbrace{\max_{a^{\prime\prime}\in\mathcal{A}}\hat{q}_{b}^{k}(s_{\mathrm{ref}},a^{\prime\prime})}_{\text{can
be interpreted as $\hat{v}_{g}^{*}$}},$ (13)

where $\hat{\boldsymbol{q}}_{b}^{k}$ denotes the estimate of
$\boldsymbol{q}_{b}^{*}$ at iteration $k$, and $\mathbb{B}^{*}$ is based on
(12) so it operates on action values. The iterates of
$\hat{v}_{b}^{k}(s)=\max_{a\in\mathcal{A}}\hat{q}_{b}^{k}(s,a)$ are
conjectured to converge to $v_{b}^{*}(s)$ for all $s\in\mathcal{S}$ by
Bertsekas, (2012, Sec 7.2.3).

###  3.2 Tabular methods

In model-free RL, the iteration for estimating $\boldsymbol{q}_{b}^{*}$ in
(13) is carried out asynchronously as follows,

$\hat{q}_{b}^{*}(s,a)\leftarrow\hat{q}_{b}^{*}(s,a)+\beta\big{\\{}r(s,a)+\max_{a^{\prime}\in\mathcal{A}}\hat{q}_{b}^{*}(s^{\prime},a^{\prime})-\hat{v}_{g}^{*}-\
\hat{q}_{b}^{*}(s,a)\big{\\}},$ (14)

where $\beta$ is a positive stepsize, whereas $s$, $a$, and $s^{\prime}$
denote the current state, current action, and next state, respectively. Here,
the sum over $s^{\prime}$ in (13), i.e. the expectation with respect to
$S^{\prime}$, is approximated by a single sample $s^{\prime}$. The stochastic
approximation (SA) based update in (14) is the essense of $Q_{b}$-learning
(Schwartz,, 1993, Sec 5), and most of its variants. One exception is that of
Prashanth and Bhatnagar, (2011, Eqn 8), where there is no subtraction of
$\hat{q}_{b}^{*}(s,a)$.

In order to prevent the iterate $\hat{q}_{b}^{*}$ from becoming very large
(causing numerical instability), Singh, (1994, p702) advocated assigning
$q_{b}^{*}(s_{\mathrm{ref}},a_{\mathrm{ref}})\leftarrow 0$, for arbitrary-but-
fixed reference state $s_{\mathrm{ref}}$ and action $a_{\mathrm{ref}}$.
Alternatively, Bertsekas and Tsitsiklis, (1996, p404) advised setting
$\hat{q}_{b}^{*}(s_{\mathrm{ref}},\cdot)\leftarrow 0$. Both suggestions seem
to follow the heuristics of obtaining the unique solution of the
underdetermined Bellman optimality non-linear system of equations in (6).

There are several ways to approximate the optimal gain $v_{g}^{*}$ in (14), as
summarized in Fig LABEL:fig:taxonomy_optgainapprox (Appendix
LABEL:sec:taxonomy). In particular, Abounadi et al., (2001, Sec 2.2) proposed
three variants as follows.

  1. i.

$\hat{v}_{g}^{*}\leftarrow\hat{q}_{b}^{*}(s_{\mathrm{ref}},a_{\mathrm{ref}})$
with reference state $s_{\mathrm{ref}}$ and action $a_{\mathrm{ref}}$. Yang et
al., (2016) argued that properly choosing $s_{\mathrm{ref}}$ can be difficult
in that the choice of $s_{\mathrm{ref}}$ affects the learning performance,
especially when the state set is large. They proposed setting
$\hat{v}_{g}^{*}\leftarrow c$ for a constant $c$ from prior knowledge.
Moreover, Wan et al., (2020) showed empirically that such a reference retards
learning and causes divergence. This happens when
$(s_{\mathrm{ref}},a_{\mathrm{ref}})$ is infrequently visited, e.g. being a
trasient state in unichain MDPs.

  2. ii.

$\hat{v}_{g}^{*}\leftarrow\max_{a^{\prime}\in\mathcal{A}}\hat{q}_{b}^{*}(s_{\mathrm{ref}},a^{\prime})$,
used by Prashanth and Bhatnagar, (2011, Eqn 8). This inherits the same issue
regarding $s_{\mathrm{ref}}$ as before. Whenever the action set is large, the
maximization over $\mathcal{A}$ should be estimated, yielding another layer of
approximation errors.

  3. iii.

$\hat{v}_{g}^{*}\leftarrow\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}\hat{q}_{b}^{*}(s,a)/(|\mathcal{S}||\mathcal{A}|)$,
used by Avrachenkov and Borkar, (2020, Eqn 11). Averaging all entries of
$\hat{\boldsymbol{q}}_{b}^{*}$ removes the need for $s_{\mathrm{ref}}$ and
$a_{\mathrm{ref}}$. However, because $\hat{q}_{b}^{*}$ itself is an estimating
function with diverse accuracy across all state-action pairs, the estimate
$\hat{v}_{g}^{*}$ involves the averaged approximation error. The potential
issue due to large state and action sets is also concerning.

Equation (14) with one of three proposals (i - iii) for $v_{g}^{*}$ estimators
constitutes the RVI $Q_{b}$-learning. Although it operates asynchronously, its
convergence is assured by decreasing the stepsize $\beta$.

The optimal gain $v_{g}^{*}$ in (14) can also be estimated iteratively via SA
as follows,

$\hat{v}_{g}^{*}\leftarrow\hat{v}_{g}^{*}+\beta_{g}\Delta_{g},\quad\text{for
some update $\Delta_{g}$ and a positive stepsize $\beta_{g}$}.$ (15)

Thus, the corresponding $Q_{b}$-learning becomes 2-timescale SA, involving
both $\beta$ and $\beta_{g}$. There exist several variations on $\Delta_{g}$
as listed below.

  1. i.

In Schwartz, (1993, Sec 5),

$\Delta_{g}\coloneqq
r(s,a)+\underbrace{\max_{a^{\prime}\in\mathcal{A}}\hat{q}_{b}^{*}(s^{\prime},a^{\prime})-\max_{a^{\prime}\in\mathcal{A}}\hat{q}_{b}^{*}(s,a^{\prime})}_{\text{to
minimize the variance of updates}}-\ \hat{v}_{g}^{*},\quad\text{if}\
\underbrace{a=\operatorname*{\arg\\!\max}_{a^{\prime}\in\mathcal{A}}\hat{q}_{b}^{*}(s,a^{\prime})}_{\text{a
greedy action $a$}}.$ (16)

By updating only when greedy actions are executed, the influence of
exploratory actions (which are mostly suboptimal) can be avoided.

  2. ii.

In Singh, (1994, Algo 3), and Wan et al., (2020, Eqn 6),

$\Delta_{g}\coloneqq\underbrace{r(s,a)+\max_{a^{\prime}\in\mathcal{A}}\hat{q}_{b}^{*}(s^{\prime},a^{\prime})-\hat{q}_{b}^{*}(s,a)}_{\text{$v_{g}^{*}$
in expectation of $S^{\prime}$ when using $q_{b}^{*}$ (see
\eqref{equ:avgrew_bellmanopt_q})}}-\ \hat{v}_{g}^{*}.$ (To update at every
action)

Since the equation for $v_{g}^{*}$ (12) applies to any state-action pairs, it
is reasonable to update $\hat{v}_{g}^{*}$ for both greedy and exploratory
actions as above. This also implies that information from non-greedy actions
is not wasted. Hence, it is more sample-efficient than that of (16).

  3. iii.

In Singh, (1994, Algo 4), and Das et al., (1999, Eqn 8),

$\Delta_{g}\coloneqq r(s,a)-\hat{v}_{g}^{*},\quad\text{if $a$ is chosen
greedily with $\beta_{g}$ set to $1/(n_{u}+1)$},$

where $n_{u}$ denotes the number of $\hat{v}_{g}^{*}$ updates so far (15).
This special value of $\beta_{g}$ makes the estimation equivalent to the
sample average of the rewards received for greedy actions.

  4. iv.

In Bertsekas and Tsitsiklis, (1996, p404), Abounadi et al., (2001, Eqn 2.9b),
and Bertsekas, (2012, p551),

$\Delta_{g}\coloneqq\underbrace{\max_{a^{\prime}\in\mathcal{A}}\hat{q}_{b}^{*}(s_{\mathrm{ref}},a^{\prime})}_{\hat{v}_{b}^{*}(s_{\mathrm{ref}})},\quad\text{for
an arbitrary reference state $s_{\mathrm{ref}}$}.$ (17)

This benefits from having $s_{\mathrm{ref}}$ such that
$v_{b}^{*}(s_{\mathrm{ref}})$ can be interpreted as $v_{g}^{*}$, while also
satisfying the underdetermined system of average-reward Bellman optimality
equations.

###  3.3 Methods with function approximation

We focus on _parametric_ techniques for $Q_{b}$-learning with function
approximation. In such cases, the action value is parameterized by a weight
(parameter) vector $\boldsymbol{w}\in\mathcal{W}=\real{\dim(\boldsymbol{w})}$,
where $\dim(\boldsymbol{w})$ is the number of dimensions of $\boldsymbol{w}$.
That is, $\hat{q}_{b}^{*}(s,a;\boldsymbol{w})\approx
q_{b}^{*}(s,a),\forall(s,a)\in\mathcal{S}\times\mathcal{A}$. Note that there
also exist non-parametric techniques, for instance, kernel-based methods
(Ormoneit and Glynn,, 2002, 2001) and those based on state aggregation
(Ortner,, 2007).

Bertsekas and Tsitsiklis, (1996, p404) proposed the following weight update,

$\boldsymbol{w}\leftarrow\boldsymbol{w}+\beta\Big{\\{}\Big{(}r(s,a)-\hat{v}_{g}^{*}+\max_{a^{\prime}\in\mathcal{A}}\hat{q}_{b}^{*}(s^{\prime},a^{\prime};\boldsymbol{w})\Big{)}\nabla\hat{q}_{b}^{*}(s,a;\boldsymbol{w})-\boldsymbol{w}\Big{\\}}.$
(18)

Particularly, the optimal gain $v_{g}^{*}$ is estimated using (15, 17). They
highlighted that even if $\hat{q}_{b}^{*}(\boldsymbol{w})$ is bounded,
$\hat{v}_{g}^{*}$ may diverge.

Das et al., (1999, Eqn 9) updated the weight using temporal difference (TD, or
TD error) as follows,

$\boldsymbol{w}\leftarrow\boldsymbol{w}+\beta\Big{\\{}\Big{(}\underbrace{r(s,a)-\hat{v}_{g}^{*}+\max_{a^{\prime}\in\mathcal{A}}\hat{q}_{b}^{*}(s^{\prime},a^{\prime},\boldsymbol{w})-\hat{q}_{b}^{*}(s,a;\boldsymbol{w})}_{\text{relative
TD in terms of
$\hat{q}_{b}^{*}$}}\Big{)}\nabla\hat{q}_{b}^{*}(s,a;\boldsymbol{w})\Big{\\}},$
(19)

which can be interpreted as the parameterized form of (14), and is a _semi-
gradient_ update, similar to its discounted-reward counterpart in
$Q_{\gamma}$-learning (Sutton and Barto,, 2018, Eqn 16.3). This update is
adopted by Yang et al., (2016, Algo 2). The approximation for $v_{g}^{*}$ can
be performed in various ways, as for tabular settings in Sec 3.2. Note that
(19) differs from (18) in the use of TD, affecting the update factor. In
contrast, Prashanth and Bhatnagar, (2011, Eqn 10) leveraged (14) in order to
suggest the following update,

$\boldsymbol{w}\leftarrow\boldsymbol{w}+\beta\Big{\\{}r(s,a)-\hat{v}_{g}^{*}+\max_{a^{\prime}\in\mathcal{A}}\hat{q}_{b}^{*}(s^{\prime},a^{\prime},\boldsymbol{w})\Big{\\}},\quad\text{whose
$\hat{v}_{g}^{*}$ is updated using
(\ref{equ:vgstar_sa},~{}\ref{equ:optgain_sa_bertsekas})}.$

##  4 Policy-iteration schemes

Instead of iterating towards the value of optimal policies, we can iterate
policies directly towards the optimal one. At each iteration, the current
policy iterate is evaluated, then its value is used to obtain the next policy
iterate by taking the greedy action based on the RHS of the Bellman optimality
equation (6). The latter step differentiates this so-called policy iteration
from naive policy enumeration that evaluates and compares policies as
prescribed in (5).

Like in the previous Sec 3, we begin with the original policy iteration in DP,
which is then generalized in RL. Afterward, we review average-reward policy
gradient methods, including actor-critic variants, because of their prominence
and proven empirical successes. The last two sections are devoted to
approximate policy evaluation, namely gain and relative value estimations.
Table LABEL:tbl:politer_work (in Appendix LABEL:sec:table_of_existing)
summarizes existing works on average-reward policy-iteration-based model-free
RL.

###  4.1 Foundations

In DP, Howard, (1960) proposed the first policy iteration algorithm to obtain
gain optimal policies for unichain MDPs. It proceeds as follows.

  1. Step 1:

Initialize the iteration index $k\leftarrow 0$ and set the initial policy
arbitrarily, $\hat{\pi}^{k=0}\approx\pi^{*}$.

  2. Step 2:

Perform (exact) policy evaluation:
Solve the following underdetermined linear system for $v_{g}^{k}$ and
$\boldsymbol{v}_{b}^{k}$,

$v_{b}^{k}(s)+v_{g}^{k}=r(s,a)+\sum_{s^{\prime}\in\mathcal{S}}p(s^{\prime}|s,a)\
v_{b}^{k}(s^{\prime}),\qquad\forall s\in\mathcal{S},\text{with}\
a=\hat{\pi}^{k}(s),$ (20)

which is called the Bellman policy expectation equation, also the Poisson
equation (Feinberg and Shwartz,, 2002, Eqn 9.1).

  3. Step 3:

Perform (exact) policy improvement:
Compute a policy $\hat{\pi}^{k+1}$ by greedy action selection (analogous to
the RHS of (6)):

$\hat{\pi}^{k+1}(s)\leftarrow\operatorname*{\arg\\!\max}_{a\in\mathcal{A}}\big{[}\underbrace{r(s,a)+\sum_{s^{\prime}\in\mathcal{S}}p(s^{\prime}|s,a)\
v_{b}^{k}(s^{\prime})}_{\text{$q_{b}^{k}(s,a)+v_{g}^{k}$}}\big{]},\ \forall
s\in\mathcal{S}.$ (Synchronous updates)

  4. Step 4:

If stable, i.e. $\hat{\pi}^{k+1}(s)=\hat{\pi}^{k}(s),\forall s\in\mathcal{S}$,
then output $\hat{\pi}^{k+1}$ (which is equivalent to $\pi^{*}$).
Otherwise, increment $k$, then go to Step 2.

The above _exact_ policy iteration is generalized to the generalized policy
iteration (GPI) for RL (Sutton and Barto,, 2018, Sec 4.6). Such generalization
is in the sense of the details of policy evaluation and improvement, such as
approximation (_inexact_ evaluation and _inexact_ improvement) and the update
granularity, ranging from per timestep (incremental, step-wise) to per number
(batch) of timesteps.

GPI relies on the policy improvement theorem (Sutton and Barto,, 2018, p101).
It assures that any $\epsilon$-greedy policy with respect to $q_{b}(\pi)$ is
an improvement over any $\epsilon$-soft policy $\pi$, i.e. any policy whose
$\pi(a|s)\geq\epsilon/|\mathcal{A}|,\forall(s,a)\in\mathcal{S}\times\mathcal{A}$.
Moreover, $\epsilon$-greediness is also beneficial for exploration. There
exist several variations on policy improvement that all share a similar idea
to $\epsilon$-greedy, i.e. updating the current policy _towards_ a greedy
policy. They include Chen-Yu Wei, (2019, Eqn 5), Abbasi-Yadkori et al., 2019a
(, Eqn 4), Hao et al., (2020, Eqn 4.1), and approximate gradient-ascent
updates used in policy gradient methods (Sec 4.2).

###  4.2 Average-reward policy gradient methods

In this section, we outline policy gradient methods, which have proven
empirical successes in function approximation settings (Agarwal et al.,, 2019;
Duan et al.,, 2016). They requires explicit policy parameterization, which
enables _not only_ learning appropriate levels of exploration (either control-
or parameter-based Vemula et al.,, 2019, Miyamae et al.,, 2010, Fig 1), _but
also_ injection of domain knowledge (Deisenroth et al.,, 2013, Sec 1.3). Note
that from a sensitivity-based point of view, policy gradient methods belong to
perturbation analysis (Cao,, 2007, p18).

In policy gradient methods, a policy $\pi$ is parameterized by a parameter
vector $\boldsymbol{\theta}\in\Theta=\real{\dim(\boldsymbol{\theta})}$, where
$\dim(\boldsymbol{\theta})$ indicates the number of dimensions of
$\boldsymbol{\theta}$. In order to obtain a smooth dependence on
$\boldsymbol{\theta}$ (hence, smooth gradients), we restrict the policy class
to a set of _randomized_ stationary policies $\Pi_{\mathrm{SR}}$. We further
assume that $\pi(\boldsymbol{\theta})$ is twice differentiable with bounded
first and second derivatives. For discrete actions, one may utilize a
categorical distribution (a special case of Gibbs/Boltzmann distributions) as
follows,

$\pi(a|s;\boldsymbol{\theta})\coloneqq\frac{\exp(\boldsymbol{\theta}^{\intercal}\boldsymbol{\phi}(s,a))}{\sum_{a^{\prime}\in\mathcal{A}}\exp(\boldsymbol{\theta}^{\intercal}\boldsymbol{\phi}(s,a^{\prime}))},\quad\forall(s,a)\in\mathcal{S}\times\mathcal{A},$
(soft-max in action preferences)

where $\boldsymbol{\phi}(s,a)$ is the feature vector of a state-action pair
$(s,a)$ for this policy parameterization (Sutton and Barto, (2018, Sec 3.1),
Bhatnagar et al., 2009a (, Eqn 8)). Note that parametric policies may not
contain the optimal policy because there are typically fewer parameters than
state-action pairs, yielding some approximation error.

The policy improvement is based on the following optimization with
$v_{g}(\boldsymbol{\theta})\coloneqq v_{g}(\pi(\boldsymbol{\theta}))$,

$\boldsymbol{\theta}^{*}\coloneqq\operatorname*{\arg\\!\max}_{\boldsymbol{\theta}\in\Theta}v_{g}(\boldsymbol{\theta}),\quad\text{with
iterative update:}\
\boldsymbol{\theta}\leftarrow\boldsymbol{\theta}+\alpha\boldsymbol{C}^{-1}\nabla
v_{g}(\boldsymbol{\theta}),$ (21)

where $\alpha$ is a positive step length, and
$\boldsymbol{C}\in\real{\dim(\boldsymbol{\theta})\times\dim(\boldsymbol{\theta})}$
denotes some preconditioning positive definite matrix. Based on (3), we have

$\displaystyle\nabla v_{g}(\boldsymbol{\theta})$
$\displaystyle=\sum_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}r(s,a)\
\nabla\\{p_{\pi}^{\star}(s)\ \pi(a|s;\boldsymbol{\theta})\\}$
($\nabla\coloneqq\frac{\partial}{\partial\boldsymbol{\theta}}$)
$\displaystyle=\sum_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}p_{\pi}^{\star}(s)\
\pi(a|s;\boldsymbol{\theta})\ r(s,a)\
\\{\nabla\log\pi(a|s;\boldsymbol{\theta})+\nabla\log p_{\pi}^{\star}(s)\\}$
$\displaystyle=\sum_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}p_{\pi}^{\star}(s)\
\pi(a|s;\boldsymbol{\theta})\ \underbrace{q_{b}^{\pi}(s,a)}_{\text{in lieu of
$r(s,a)$}}\nabla\log\pi(a|s;\boldsymbol{\theta})$ (does not involve
$\nabla\log p_{\pi}^{\star}(s)$)
$\displaystyle=\sum_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}\sum_{s^{\prime}\in\mathcal{S}}p_{\pi}^{\star}(s)\
\pi(a|s;\boldsymbol{\theta})\ p(s^{\prime}|s,a)\ v_{b}^{\pi}(s^{\prime})\
\nabla\log\pi(a|s;\boldsymbol{\theta}).$ (22)

The penultimate equation above is due to the (randomized) policy gradient
theorem (Sutton et al., (2000, Thm 1), Marbach and Tsitsiklis, (2001, Sec 6),
Deisenroth et al., (2013, p28)). The last equation was proven to be equivalent
by Castro and Meir, (2010, Appendix B).

There exist (at least) two variants of preconditioning matrices
$\boldsymbol{C}$. First is through the second derivative
$\boldsymbol{C}=-\nabla^{2}v_{g}(\boldsymbol{\theta})$, as well as its
approximation, see Furmston et al., (2016, Appendix B.1), (Morimura et al.,,
2008, Sec 3.3, 5.2), Kakade, (2002, Eqn 6). Second, one can use a Riemannian-
metric matrix for natural gradients. It aims to make the update directions
invariant to the policy parameterization. Kakade, (2002) first proposed the
Fisher information matrix (FIM) as such a matrix, for which an incremental
approximation was suggested by Bhatnagar et al., 2009a (, Eqn 26). A
generalized variant of natural gradients was introduced by Morimura et al.,
(2009, 2008). In addition, Thomas, (2014) derived another generalization that
allows for a positive semidefinite matrix. Recall that FIM is only guaranteed
to be positive semidefinite (hence, describing a semi-Riemannian manifold);
whereas the natural gradient ascent assumes the function being optimized has a
Riemannian manifold domain.

In order to obtain more efficient learning with efficient computation, several
works propose using backward-view eligibility traces in policy parameter
updates. The key idea is to keep track of the eligibility of each component of
$\boldsymbol{\theta}$ for getting updated whenever a reinforcing event, i.e.
$q_{b}^{\pi}$, occurs. Given a state-action sample $(s,a)$, the update in (21)
becomes

$\boldsymbol{\theta}\leftarrow\boldsymbol{\theta}+\alpha\boldsymbol{C}^{-1}q_{b}^{\pi}(s,a)\
\boldsymbol{e}_{\boldsymbol{\theta}},\quad\text{which is carried out after}\
\boldsymbol{e}_{\boldsymbol{\theta}}\leftarrow\lambda_{\boldsymbol{\theta}}\boldsymbol{e}_{\boldsymbol{\theta}}+\underbrace{\nabla\log\pi(a|s;\boldsymbol{\theta})}_{\text{the
eligibility}},$ (23)

where
$\boldsymbol{e}_{\boldsymbol{\theta}}\in\real{\dim(\boldsymbol{\theta})}$
denotes the accumulating eligibility vector for $\boldsymbol{\theta}$ and is
initialized to $\boldsymbol{0}$, whereas
$\lambda_{\boldsymbol{\theta}}\in(0,1)$ the trace decay factor for
$\boldsymbol{\theta}$. This is used by Iwaki and Asada, (2019, Sec 4), Sutton
and Barto, (2018, Sec 13.6), Furmston et al., (2016, Appendix B.1), Degris et
al., (2012, Sec III.B), Matsubara et al., 2010a (, Sec 4), and Marbach and
Tsitsiklis, (2001, Sec 5).

As can be observed in (22), computing the gradient $\nabla
v_{g}(\boldsymbol{\theta})$ exactly requires (exact) knowledge of
$p_{\pi}^{\star}$ and $q_{b}^{\pi}$, which are both unknown in RL. It also
requires summation over all states and actions, which becomes an issue when
state and action sets are large. As a result, we resort to the gradient
estimate, which if _unbiased_ , leads to _stochastic_ gradient ascent.

In order to reduce the variance of gradient estimates, there are two common
techniques based on control variates (Greensmith et al.,, 2004, Sec 5, 6).

First is the baseline control variate, for which the _optimal_ baseline is the
one that minimizes the variance. Choosing $v_{b}^{\pi}$ as a baseline
(Bhatnagar et al., 2009a, , Lemma 2) yields

$\underbrace{q_{b}^{\pi}(s,a)-v_{b}^{\pi}(s)}_{\text{relative action
advantage,
$\mathrm{a}_{b}^{\pi}(s,a)$}}=\mathbb{E}_{S^{\prime}}\Big{[}\underbrace{\Big{\\{}r(s,a)-v_{g}^{\pi}+v_{b}^{\pi}(S^{\prime})\Big{\\}}-v_{b}^{\pi}(s)\big{|}s,a}_{\text{relative
TD,
$\delta_{v_{b}}^{\pi}(s,a,S^{\prime})$}}\Big{]},\quad\forall(s,a)\in\mathcal{S}\times\mathcal{A},$
(24)

where $S^{\prime}$ denotes the next state given the current state $s$ and
action $a$. It has been shown that
$\mathrm{a}_{b}^{\pi}(s,a)=\mathbb{E}_{S^{\prime}}\mathopen{}\mathclose{{}\left[\delta_{v_{b}}^{\pi}(s,a,S^{\prime})}\right]$,
meaning that the TD, i.e. $\delta_{v_{b}}^{\pi}(s,a,S^{\prime})$, can be used
as an _unbiased_ estimate for the action advantage Iwaki and Asada,, 2019,
Prop 1, Castro and Meir,, 2010, Thm 5, Bhatnagar et al., 2009a, , Lemma 3.
Hence, we have

$\nabla
v_{g}(\boldsymbol{\theta})=\mathbb{E}_{S,A}\big{[}\mathrm{a}_{b}^{\pi}(S,A)\
\nabla\log\pi(A|S;\boldsymbol{\theta})\big{]}\approx\delta_{v_{b}}^{\pi}(s,a,s^{\prime})\
\nabla\log\pi(a|s;\boldsymbol{\theta}),$

where the expectation of $S$, $A$, and $S^{\prime}$ is approximated with a
single sample $(s,a,s^{\prime})$. This yields an unbiased gradient estimate
with lower variance than that using $q_{b}^{\pi}$. Note that in RL, the exact
$\mathrm{a}_{b}^{\pi}$ and $v_{b}^{\pi}$ (for calculating
$\delta_{v_{b}}^{\pi}$) should also be approximated.

Second, a policy value estimator is set up and often also parameterized by
$\boldsymbol{w}\in\mathcal{W}=\real{\dim(\boldsymbol{w})}$. This gives rise to
actor-critic methods, where “actor” refers to the parameterized policy,
whereas “critic” the parameterized value estimator. The critic can take either
one of these three forms,

  1. i.

relative state-value estimator $\hat{v}_{b}^{\pi}(s;\boldsymbol{w}_{v})$ for
computing the relative TD approximate $\hat{\delta}_{v_{b}}^{\pi}$,

  2. ii.

both relative state- and action-value estimators for
$\hat{\mathrm{a}}_{b}^{\pi}(s,a)\leftarrow\hat{q}_{b}^{\pi}(s,a;\boldsymbol{w}_{q})-\hat{v}_{b}^{\pi}(s;\boldsymbol{w}_{v})$,

  3. iii.

relative action-advantage estimator
$\hat{\mathrm{a}}_{b}^{\pi}(s,a;\boldsymbol{w}_{\mathrm{a}})$,

for all $s\in\mathcal{S},a\in\mathcal{A}$, and with the corresponding critic
parameter vectors $\boldsymbol{w}_{v}$, $\boldsymbol{w}_{q}$, and
$\boldsymbol{w}_{\mathrm{a}}$. This parametric value approximation is reviewed
in Sec 4.4.

###  4.3 Gain Approximation

We classify gain approximations into incremental and batch categories.
Incremental methods update their current estimates using information only from
one timestep, hence step-wise updates. In contrast, batch methods uses
information from multiple timesteps in a batch. Every update, therefore, has
to wait until the batch is available. Notationally, we write $g^{\pi}\coloneqq
v_{g}(\pi)$. The superscript $\pi$ is often dropped whenever the context is
clear.

####  4.3.1 Incremental methods

Based on (4), we can define an increasing function $f(g)\coloneqq
g-\mathbb{E}\mathopen{}\mathclose{{}\left[r(S,A)}\right]$. Therefore, the
problem of estimating $g$ becomes finding the root of $f(g)$, by which
$f(g)=0$. As can be observed, $f(g)$ is unknown because
$\mathbb{E}\mathopen{}\mathclose{{}\left[r(S,A)}\right]$ is unknown. Moreover,
we can only obtain noisy observations of
$\mathbb{E}\mathopen{}\mathclose{{}\left[r(S,A)}\right]$, namely
$r(s,a)=\mathbb{E}\mathopen{}\mathclose{{}\left[r(S,A)}\right]+\varepsilon$
for some additive error $\varepsilon>0$. Thus, the _noisy_ observation of
$f(\hat{g}_{t})$ at iteration $t$ is given by
$\hat{f}(\hat{g}_{t})=\hat{g}_{t}-r(s_{t},a_{t})$. Recall that an increasing
function satisfies $df(x)/dx>0$ for $x>x^{*}$ where $x^{*}$ indicates the root
of the $f(x)$.

We can solve for the root of $f(g)$ iteratively via the Robbins-Monro (RM)
algorithm as follows,

$\displaystyle\hat{g}_{t+1}$
$\displaystyle=\hat{g}_{t}-\beta_{t}\\{\hat{f}(\hat{g}_{t})\\}=\hat{g}_{t}-\beta_{t}\\{\hat{g}_{t}-r(s_{t},a_{t})\\}$
(for an increasing function $f$)
$\displaystyle=\hat{g}_{t}+\beta_{t}\\{r(s_{t},a_{t})-\hat{g}_{t}\\}=(1-\beta_{t})\hat{g}_{t}+\beta_{t}\\{r(s_{t},a_{t})\\},$
(25)

where $\beta_{t}\in(0,1)$ is a gain approximation step size; note that setting
$\beta_{t}\geq 1$ violates the RM algorithm since it makes the coefficient of
$\hat{g}_{t}$ non-positive. This recursive procedure converges to the root of
$f(g)$ with probability 1 under several conditions, including
$\varepsilon_{t}$ is i.i.d with
$\mathbb{E}\mathopen{}\mathclose{{}\left[\varepsilon_{t}}\right]=0$, the step
size satisfies the standard requirement in SA, and some other technical
conditions (Cao,, 2007, Sec 6.1). The stochastic approximation technique in
(25) is the most commonly used. For instance, Wu et al., (2020, Algo 1), Heess
et al., (2012), Powell, (2011, Sec 10.7), Castro and Meir, (2010, Eqn 13),
Bhatnagar et al., 2009a (, Eqn 21), Konda and Tsitsiklis, (2003, Eqn 3.1),
Marbach and Tsitsiklis, (2001, Sec 4), and Tsitsiklis and Roy, (1999, Sec 2).

Furthermore, a learning rate of $\beta_{t}=1/(t+1)$ in (25) yields

$\hat{g}_{t+1}=\frac{t\times\hat{g}_{t}+r(s_{t},a_{t})}{t+1}=\frac{r(s_{t},a_{t})+r(s_{t-1},a_{t-1})+\ldots+r(s_{0},a_{0})}{t+1},$
(26)

which is the average of a noisy gain observation sequence up to $t$. The
ergodic theorem asserts that for such a Markovian sequence, the time average
converges to (4) as $t$ approaches infinity (Gray,, 2009, Ch 8). This decaying
learning rate is suggested by Singh, (1994, Algo 2). Additionally, a variant
of $\beta_{t}=1/(t+1)^{\kappa}$ with a positive constant $\kappa<1$ is used by
Wu et al., (2020, Sec 5.2.1) for establishing the finite-time error rate of
this gain approximation under non-i.i.d Markovian samples.

Another iterative approach is based on the Bellman expectation equation (20)
for obtaining the noisy observation of $g$. That is,

$\displaystyle\hat{g}_{t+1}$
$\displaystyle=(1-\beta_{t})\hat{g}_{t}+\beta_{t}\big{\\{}\underbrace{r(s_{t},a_{t})+\hat{v}_{b,t}^{\pi}(s_{t+1})-\hat{v}_{b,t}^{\pi}(s_{t})}_{\text{$g$
in expectation of $S_{t+1}$ when $\hat{v}_{b,t}^{\pi}=v_{b}^{\pi}$}}\big{\\}}$
(The variance is reduced, cf. (25))
$\displaystyle=\hat{g}_{t}+\beta_{t}\big{\\{}\underbrace{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\\{}r(s_{t},a_{t})-\hat{g}_{t}+\hat{v}_{b,t}^{\pi}(s_{t+1}){\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\\}}-\hat{v}_{b,t}^{\pi}(s_{t})}_{\text{$\hat{\delta}_{v_{b},t}^{\pi}(s_{t},a_{t},s_{t+1})$}}\big{\\}}.$
(27)

In comparison to (25), the preceding update is anticipated to have lower
variance due to the adjustment terms of
$\hat{v}_{b,t}^{\pi}(s_{t+1})-\hat{v}_{b,t}^{\pi}(s_{t})$. This update is used
by Singh, (1994, Algo 1), Degris et al., (2012, Sec 3B), and Sutton and Barto,
(2018, p333). An analogous update can be formulated by replacing $v_{b}^{\pi}$
with $q_{b}^{\pi}$, which is possible only when the next action $a_{t+1}$ is
already available, as in the differential Sarsa algorithm (Sutton and Barto,,
2018, p251).

####  4.3.2 Batch methods

In batch settings, there are at least two ways to approximate the gain of a
policy, denoted as $g$.

First, $\hat{g}$ is set to the total rewards _divided_ by the number of
timesteps in a batch, as in (26), which also shows its incremental
equivalence. This is used in Powell,, 2011, p339; Yu and Bertsekas,, 2009, Sec
2B; Gosavi, 2004a, , Sec 4, Feinberg and Shwartz,, 2002, p319. The work of
Marbach and Tsitsiklis, (2001, Eqn 16) also falls in this category, but
$\hat{g}$ is computed as a weighted average of _all_ past rewards from all
batches (regenerative cycles), mixing on- and off-policy samples. Nonetheless,
it is shown to yield lower estimation variance.

Second, based on similiar justification as RVI, we can specify a reference
state and action pair. For instance, Cao, (2007, Eqn 6.23, p311) proposed
$\hat{g}\leftarrow\hat{v}_{b}^{\pi}(s_{\mathrm{ref}})$, whereas Lagoudakis,
(2003, Appendix A) advocated
$\hat{g}\leftarrow\hat{q}_{b}^{\pi}(s_{\mathrm{ref}},a_{\mathrm{ref}})$.

###  4.4 Relative state- and action-value approximation

####  4.4.1 Tabular methods

Singh, (1994, Algo 1, 2) proposed the following incremental TD-based update,

$\hat{v}_{b}^{\pi}(s)\leftarrow\hat{v}_{b}^{\pi}(s)+\beta\\{\underbrace{\big{(}r(s,a)-\hat{v}_{g}^{\pi}+\hat{v}_{b}^{\pi}(s^{\prime})\big{)}-\hat{v}_{b}^{\pi}(s)}_{\delta_{v_{b}}^{\pi}(s,a,s^{\prime})}\\},\quad\text{for
a sample $(s,a,s^{\prime})$}.$

A similar update for $\hat{q}_{b}^{\pi}$ can be obtained by substituting
$\hat{v}_{b}^{\pi}$ with $\hat{q}_{b}^{\pi}$ along with a sample for the next
action, as in Sarsa-like algorithms.

In a batch fashion, the relative action value can be approximated as follows,

$q_{b}^{\pi}(s_{t},a_{t})\approx\underbrace{\sum_{\tau=t}^{t_{s_{\mathrm{ref}}}^{\pi}}r(s_{\tau},a_{\tau})-\hat{v}_{g}^{\pi},}_{\text{an
episode return}}\quad\text{using a sample set
$\\{(s_{\tau},a_{\tau})\\}_{\tau=t}^{t_{s_{\mathrm{ref}}}^{\pi}}$}$ (28)

where $t_{s_{\mathrm{ref}}}^{\pi}$ denotes the timestep at which
$s_{\mathrm{ref}}$ is visited while following a policy $\pi$, assuming that
$s_{\mathrm{ref}}$ is a recurrent state under all policies. This is used by
Sutton et al., (2000, Sec 1), and Marbach and Tsitsiklis, (2001, Sec 6).
Another batch approximation technique is based on the inverse-propensity
scoring (Chen-Yu Wei,, 2019, Algo 3).

####  4.4.2 Methods with function approximation

Here, we review gradient-based approximate policy evaluation that relies on
the gradient of an error function to update its parameter. Note that there
exist approximation techniques based on least squares, e.g. LSPE($\lambda$)
(Yu and Bertsekas,, 2009), gLSTD and LSTDc (Ueno et al.,, 2008), and LSTD-Q
(Lagoudakis,, 2003, Appendix A).

##### Relative state-value approximation:

The value approximator is parameterized as
$\hat{\boldsymbol{v}}_{b}^{\pi}(\boldsymbol{w})\approx\boldsymbol{v}_{b}^{\pi}$,
where ${\boldsymbol{w}\in\mathcal{W}=\real{\dim(\boldsymbol{w})}}$. Then, the
mean squared error (MSE) objective is minimized. That is,

$\|\boldsymbol{v}_{b}^{\pi}-\hat{\boldsymbol{v}}_{b}^{\pi}(\boldsymbol{w})\|_{\mathrm{diag}(\boldsymbol{p}_{\pi}^{\star})}^{2}\coloneqq\mathbb{E}_{S\sim
p_{\pi}^{\star}}\mathopen{}\mathclose{{}\left[\\{v_{b}^{\pi}(S)-\hat{v}_{b}^{\pi}(S,\boldsymbol{w})\\}^{2}}\right],$

where $\mathrm{diag}(\boldsymbol{p}_{\pi}^{\star})$ is a
$|\mathcal{S}|$-by-$|\mathcal{S}|$ diagonal matrix with
$\boldsymbol{p}_{\pi}^{\star}(s)$ in its diagonal. As a result, the gradient
estimate for updating $\boldsymbol{w}$ is given by

$\displaystyle-\frac{1}{2}\nabla\mathbb{E}_{S\sim
p_{\pi}^{\star}}\mathopen{}\mathclose{{}\left[\\{v_{b}^{\pi}(S)-\hat{v}_{b}^{\pi}(S;\boldsymbol{w})\\}^{2}}\right]$
$\displaystyle=\mathbb{E}_{S\sim
p_{\pi}^{\star}}\mathopen{}\mathclose{{}\left[\\{v_{b}^{\pi}(S)-\hat{v}_{b}^{\pi}(S;\boldsymbol{w})\\}\nabla\hat{v}_{b}^{\pi}(S;\boldsymbol{w})}\right]$
$\displaystyle\approx\\{v_{b}^{\pi}(s)-\hat{v}_{b}^{\pi}(s;\boldsymbol{w})\\}\nabla\hat{v}_{b}^{\pi}(s;\boldsymbol{w})$
(Via a single sample $s$)
$\displaystyle\approx\big{\\{}\underbrace{{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\\{}r(s,a)-\hat{v}_{g}^{\pi}+\hat{v}_{b}^{\pi}(s^{\prime};\boldsymbol{w}){\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\\}}}_{\text{TD
target that approximates $v_{b}^{\pi}(s)$}}-\
\hat{v}_{b}^{\pi}(s;\boldsymbol{w})\big{\\}}\nabla\hat{v}_{b}^{\pi}(s;\boldsymbol{w})$
$\displaystyle=\hat{\delta}_{v_{b}}^{\pi}(s,a,s^{\prime};\boldsymbol{w})\nabla\hat{v}_{b}^{\pi}(s;\boldsymbol{w}).$
(29)

The key difference to supervised learning lies in the fact that the true value
$v_{b}^{\pi}(s)$ is approximated by a bootstrapping TD target involving
$\hat{v}_{b}^{\pi}(s^{\prime};\boldsymbol{w})$, which is biased due to its
dependency on $\boldsymbol{w}$. Such a dependency, however, is not captured
(hence, ignored) in the gradient in (29) because the TD target plays the role
of true values. As a result, this way of learning $\boldsymbol{w}$ belongs to
semi-gradient methods.

With the same motivation as in policy gradient updates (23), one may use an
(accumulating) eligibility trace vector $\boldsymbol{e}_{v}$ with reinforcing
event $\delta_{v_{b}}^{\pi}$. This leads to a backward view of TD($\lambda$),
whose weight update is given by

$\boldsymbol{w}_{t+1}=\boldsymbol{w}_{t}+\beta_{t}\hat{\delta}_{v_{b}}^{\pi}(s_{t},a_{t},s_{t+1})\boldsymbol{e}_{v,t},\qquad\text{with}\
\boldsymbol{e}_{v,t}=\lambda_{v}\boldsymbol{e}_{v,t-1}+\nabla\hat{v}_{b}^{\pi}(s_{t};\boldsymbol{w}_{t}),$
(30)

for a trace decay factor $\lambda_{v}\in(0,1)$ and
$\boldsymbol{e}_{-1}=\boldsymbol{0}$ such that
$\boldsymbol{e}_{v,t}=\sum_{\tau=0}^{t}\lambda_{v}^{t-\tau}\nabla\hat{v}_{b}^{\pi}(s_{\tau};\boldsymbol{w}_{\tau})$.
For linear function approximation, Tsitsiklis and Roy, (1999, Thm 1) provide
an asymptotic convergence proof (with probability 1 with incremental gain
estimation, as well as with fixed gain estimates) and a bound on the resulting
approximation error. This TD($\lambda$) learning for $\hat{v}_{b}^{\pi}$ is
also used by Sutton and Barto, (2018, Eqn 11.4, p333), and Castro and Meir,
(2010, Eqn 13).

As can be observed, there are 2 dedicated step lengths, i.e. the actor’s
$\alpha_{t}$ (23) and the critic’s $\beta_{t}$ (30). Together, they form
2-timescale SA-type approximation, where both actor and critic are updated at
each iteration but with different step lengths, $\alpha_{t}\neq\beta_{t}$.
Intuitively, the policy (actor) should be updated on a slower timescale so
that the critic has enough updates to catch up with the ever-changing policy.
This implies that $\alpha_{t}$ should be smaller than $\beta_{t}$. More
precisely, we require that $\lim_{t\to\infty}\beta_{t}/\alpha_{t}=\infty$ for
assuring the asymptotic convergence (Wu et al.,, 2020; Bhatnagar et al.,
2009a, ; Konda and Tsitsiklis,, 2003). Nevertheless, Castro and Meir, (2010)
argued that from biological standpoint, 2-timescale operation within the same
anatomical structure is not well justified. They analyzed the convergence of
1-timescale actor-critic methods to the _neighborhood_ of a local maximum of
$v_{g}^{*}$.

##### Relative action-value and action-advantage approximation:

Estimation for $q_{b}^{\pi}$ can be carried out similarly as that for
$v_{b}^{\pi}$ in (30), but uses the relative TD on action values, namely

$\hat{\delta}_{q_{b}}^{\pi}(s,a,s^{\prime},a^{\prime})\coloneqq\underbrace{\\{r(s,a)-\hat{v}_{g}^{\pi}+\hat{q}_{b}^{\pi}(s^{\prime},a^{\prime};\boldsymbol{w})\\}}_{\text{TD
target that approximates $q_{b}^{\pi}(s,a)$}}-\
\hat{q}_{b}^{\pi}(s,a;\boldsymbol{w}),\quad\text{with $a^{\prime}\coloneqq
a_{t+1}$},$

as in Sarsa (Sutton and Barto,, 2018, p251), as well as Konda and Tsitsiklis,
(2003, Eqn 3.1). It is also possible to follow this pattern but with different
approaches to approximating the true value of $q_{b}^{\pi}(s,a)$, e.g. via
episode returns in (28) (Sutton et al.,, 2000, Thm 2).

For approximating the action advantage parametrically through
$\hat{\mathrm{a}}_{b}^{\pi}(\boldsymbol{w})$, the technique used in (29) can
also be applied. However, the true value $\mathrm{a}_{b}^{\pi}$ is estimated
by TD on state values. That is,

$\displaystyle-\frac{1}{2}\nabla\mathbb{E}_{S\sim
p_{\pi}^{\star},A\sim\pi}\mathopen{}\mathclose{{}\left[\\{\mathrm{a}_{b}^{\pi}(S,A)-\hat{\mathrm{a}}_{b}^{\pi}(S,A;\boldsymbol{w}_{\mathrm{a}})\\}^{2}}\right]$
$\displaystyle=\mathbb{E}\mathopen{}\mathclose{{}\left[\\{\mathrm{a}_{b}^{\pi}(S,A)-\hat{\mathrm{a}}_{b}^{\pi}(S,A;\boldsymbol{w}_{\mathrm{a}})\\}\nabla\hat{\mathrm{a}}_{b}^{\pi}(S,A;\boldsymbol{w}_{\mathrm{a}})}\right]$
$\displaystyle\approx\big{\\{}\mathrm{a}_{b}^{\pi}(s,a)-\hat{\mathrm{a}}_{b}^{\pi}(s,a;\boldsymbol{w}_{\mathrm{a}})\big{\\}}\nabla\hat{\mathrm{a}}_{b}^{\pi}(s,a;\boldsymbol{w}_{\mathrm{a}})$
(Approximation via a single sample $(s,a)$)
$\displaystyle\approx\big{\\{}\hat{\delta}_{v_{b}}^{\pi}(s,a,s^{\prime};\boldsymbol{w}_{v})-\
\hat{\mathrm{a}}_{b}^{\pi}(s,a;\boldsymbol{w}_{\mathrm{a}})\big{\\}}\nabla\hat{\mathrm{a}}_{b}^{\pi}(s,a;\boldsymbol{w}_{\mathrm{a}}).$
(Approximation via
$\hat{\delta}_{v_{b}}^{\pi}\approx\mathrm{a}_{b}^{\pi}(s,a)$, see (24))

This is used by Iwaki and Asada, (2019, Eqn 17), Heess et al., (2012, Eqn 13),
and Bhatnagar et al., 2009a (, Eqn 30). In particular, Iwaki and Asada, (2019,
Eqn 27) proposed a preconditioning matrix for the gradients, namely:
$\boldsymbol{I}-\kappa(\boldsymbol{f}(s,a)\boldsymbol{f}^{\intercal}(s,a))/(1+\kappa\|\boldsymbol{f}(s,a)\|^{2})$,
where $\boldsymbol{f}(s,a)$ denotes the feature vector of a state-action pair,
while $\kappa\geq\beta_{\mathrm{a}}$ some scaling constant.

Futhermore, the action-value or action-advantage estimators can be
parameterized linearly with the so-called $\boldsymbol{\theta}$-compatible
state-action feature, denoted by $\boldsymbol{f}_{\boldsymbol{\theta}}(s,a)$,
as follows,

$\hat{q}_{b}^{\pi}(s,a;\boldsymbol{w})=\boldsymbol{w}^{\intercal}\boldsymbol{f}_{\boldsymbol{\theta}}(s,a),\quad\text{with}\
\underbrace{\boldsymbol{f}_{\boldsymbol{\theta}}(s,a)\coloneqq\nabla\log\pi(a|s;\boldsymbol{\theta})}_{\text{$\boldsymbol{\theta}$-compatible
state-action feature}},\quad\forall(s,a)\in\mathcal{S}\times\mathcal{A}.$ (31)

This parameterization along with the minimization of MSE loss are beneficial
for two reasons. First, their use with (locally) optimal parameter
$\boldsymbol{w}^{*}\in\mathcal{W}$ satisfies

$\mathbb{E}_{S,A}\Big{[}\underbrace{\hat{q}_{b}^{\pi}(S,A;\boldsymbol{w}=\boldsymbol{w}^{*})}_{\text{in
lieu of $q_{b}^{\pi}(S,A)$}}\nabla\pi(A|S;\boldsymbol{\theta})\Big{]}=\nabla
v_{g}(\boldsymbol{\theta}),$ (Exact policy gradients when
$\boldsymbol{w}=\boldsymbol{w}^{*}$)

as shown by Sutton et al., (2000, Thm 2). Otherwise, the gradient estimate is
likely to be biased (Bhatnagar et al., 2009a, , Lemma 4). Second, they make
computing natural gradients equivalent to finding the optimal weight
$\boldsymbol{w}^{*}$ for $\hat{q}_{b}^{\pi}(\boldsymbol{w})$. That is,

$\displaystyle\sum_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}p_{\boldsymbol{\theta}}^{\star}(s)\pi(a|s;\boldsymbol{\theta})\boldsymbol{f}_{\boldsymbol{\theta}}(s,a)\big{(}\boldsymbol{f}_{\boldsymbol{\theta}}^{\intercal}(s,a)\boldsymbol{w}^{*}-q_{b}^{\pi}(s,a)\big{)}$
$\displaystyle=\boldsymbol{0}$ (Since MSE is 0 when
$\boldsymbol{w}=\boldsymbol{w}^{*}$)
$\displaystyle\Big{\\{}\underbrace{\sum_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}p_{\boldsymbol{\theta}}^{\star}(s)\pi(a|s;\boldsymbol{\theta})\boldsymbol{f}_{\boldsymbol{\theta}}(s,a)\boldsymbol{f}_{\boldsymbol{\theta}}^{\intercal}(s,a)}_{\boldsymbol{F}_{a}(\boldsymbol{\theta})}\Big{\\}}\boldsymbol{w}^{*}$
$\displaystyle=\underbrace{\sum_{s\in\mathcal{S}}\sum_{a\in\mathcal{A}}p_{\boldsymbol{\theta}}^{\star}(s)\pi(a|s;\boldsymbol{\theta})q_{b}^{\pi}(s,a)\boldsymbol{f}_{\boldsymbol{\theta}}(s,a)}_{\nabla
v_{g}(\boldsymbol{\theta})}$ $\displaystyle\boldsymbol{w}^{*}$
$\displaystyle=\underbrace{\boldsymbol{F}_{a}^{-1}(\boldsymbol{\theta})\
\nabla v_{g}(\boldsymbol{\theta})}_{\text{The natural gradient}},$ (32)

where $\boldsymbol{F}_{a}(\boldsymbol{\theta})$ denotes the Fisher
(information) matrix based on the action distribution (hence, the subscript
$a$), as introduced by Kakade, (2002, Thm 1). This implies that the estimation
for natural gradients is reduced to a regression problem of state-action value
functions. It can be either regressing

  1. i.

action value $q_{b}^{\pi}$ Sutton et al.,, 2000, Thm 2, Kakade,, 2002, Thm 1,
Konda and Tsitsiklis,, 2003, Eqn 3.1,

  2. ii.

action advantage $\mathrm{a}_{b}^{\pi}$ Bhatnagar et al., 2009a, , Eqn 30,
Algo 3, 4; Heess et al.,, 2012, Eqn 13; Iwaki and Asada,, 2019, Eqn 17, or

  3. iii.

the immediate reward $r(s,A\sim\pi)$ as a known ground truth (Morimura et
al.,, 2008, Thm 1), recall that the ground truth $q_{b}^{\pi}$ (Item i.) and
$\mathrm{a}_{b}^{\pi}$ (Item ii.) above are unknown. This reward regression is
used along with a $\boldsymbol{\theta}$-compatible state-action feature that
is defined differently compared to (31), namely
$\boldsymbol{f}_{\boldsymbol{\theta}}(s,a)\coloneqq\nabla\log
p_{\pi}^{\star}(s,a)=\nabla\log
p_{\pi}^{\star}(s)+\nabla\log\pi(a|s;\boldsymbol{\theta})$, where
$\boldsymbol{f}_{\boldsymbol{\theta}}$ is based on the stationary joint state-
action distribution $p_{\pi}^{\star}(s,a)$. In fact, this leads to a new
Fisher matrix, yielding the so-called natural state-action gradients
$\boldsymbol{F}_{s,a}$ (which subsumes $\boldsymbol{F}_{a}$ in (32) as a
special case when $\nabla\log p_{\pi}^{\star}$ is set to $\boldsymbol{0}$).

In addition, Konda and Tsitsiklis, (2003) pointed out that the dependency of
$\nabla v_{g}(\boldsymbol{\theta})$ to $q_{b}^{\pi}$ is only through its inner
products with vectors in the subspace spanned by
$\\{\nabla_{i}\log\pi(a|s;\boldsymbol{\theta})\\}_{i=1}^{\dim(\boldsymbol{\theta})}$.
This implies that learning the projection of $q_{b}^{\pi}$ onto the
aforementioned (low-dimensional) subspace is sufficient, instead of learning
$q_{b}^{\pi}$ fully. A $\boldsymbol{\theta}$-dependent state-action feature
can be defined based on either the action distribution (as in (31)), or the
stationary state-action distribution (as mentioned in Item iii. in the
previous passage).

##  5 Discussion

In this section, we discuss several open questions as first steps towards
completing the literature in average-reward model-free RL. We begin with those
of value iteration schemes (Sec 5.1), then of policy iteration schemes
focussing on policy evaluation (Sec 5.2). Lastly, we also outline several
issues that apply to both or beyond the two aforementioned schemes.

###  5.1 Approximation for optimal gain and optimal action-values (of optimal
policies)

Two main components of $Q_{b}$-learning are $\hat{q}_{b}^{*}$ and
$\hat{v}_{g}^{*}$ updates. The former is typically carried out via either (14)
for tabular, or (19) for (parametric) function approximation settings. What
remains is determining how to estimate the optimal gain $v_{g}^{*}$, which
becomes the main bottleneck for $Q_{b}$-learning.

As can be seen in Fig LABEL:fig:taxonomy_optgainapprox (Appendix
LABEL:sec:taxonomy), there are two classes of $v_{g}^{*}$ approximators.
First, approximators that are not SA-based generally need $s_{\mathrm{ref}}$
and $a_{\mathrm{ref}}$ specification, which is shown to affect the performance
especially in large state and action sets (Wan et al.,, 2020; Yang et al.,,
2016). On the other hand, SA-based approximators require a dedicated stepsize
$\beta_{g}$, yielding more complicated 2-timescale $Q_{b}$-learning.
Furthermore, it is not yet clear whether the approximation for $v_{g}^{*}$
should be on-policy, i.e. updating only when a greedy action is executed, at
the cost of reduced sample efficiency. This begs the question of which
approach to estimating $v_{g}^{*}$ is “best” (in which cases).

In discounted reward settings, Hasselt, (2010) (also, Hasselt et al., (2016))
pointed out that the approximation for
$\mathbb{E}\mathopen{}\mathclose{{}\left[\max_{a\in\mathcal{A}}q_{\gamma}^{*}(S_{t+1},a)}\right]$
poses overestimation, which may be non-uniform and not concentrated at states
that are beneficial in terms of exploration. He proposed instantiating two
decoupled approximators such that

$\mathbb{E}_{S_{t+1}}\mathopen{}\mathclose{{}\left[\max_{a^{\prime}\in\mathcal{A}}q_{\gamma}^{*}(S_{t+1},a^{\prime})}\right]\approx\hat{q}_{\gamma}^{*}(s_{t+1},\operatorname*{\arg\\!\max}_{a^{\prime}\in\mathcal{A}}\hat{q}_{\gamma}^{*}(s_{t+1},a^{\prime};\boldsymbol{w}_{q}^{(2)});\boldsymbol{w}_{q}^{(1)}),$
(Double $Q_{\gamma}$-learning)

where $\boldsymbol{w}_{q}^{(1)}$ and $\boldsymbol{w}_{q}^{(2)}$ denote their
corresponding weights. This was shown to be successful in reducing the
negative effect of overestimation. In average reward cases, the overestimation
of $q_{b}^{*}$ becomes more convoluted due to the involvement of
$\hat{v}_{g}^{*}$, as shown in (12). We believe that it is important to extend
the idea of double action-value approximators to $Q_{b}$-learning.

To our knowledge, there is no finite-time convergence analysis for
$Q_{b}$-learning thus far. There are also very few works on $Q_{b}$-learning
with function approximation. This is in contrast with its discounted reward
counterpart, e.g. sample complexity of $Q_{\gamma}$-learning with UCB-
exploration bonus (Wang et al.,, 2020), as well as deep $Q_{\gamma}$-learning
neural-network (DQN) and its variants with _non-linear_ function approximation
(Hessel et al.,, 2018).

###  5.2 Approximation for gain, state-, and action-values of any policy

##### Gain approximation $\hat{v}_{g}^{\pi}$:

In order to have more flexibility in terms of learning methods, we can
parameterize the gain estimator, for instance,
$\hat{v}_{g}^{\pi}(s;\boldsymbol{w}_{g})\coloneqq\boldsymbol{f}^{\intercal}(s)\boldsymbol{w}_{g}$,
by which the gain _estimate_ is state-dependent. The learning uses the
following gradients,

$\displaystyle-\frac{1}{2}\nabla\mathbb{E}_{S\sim
p_{\pi}^{\star}}\mathopen{}\mathclose{{}\left[\big{\\{}v_{g}^{\pi}-\hat{v}_{g}^{\pi}(S;\boldsymbol{w}_{g})\big{\\}}^{2}}\right]$
$\displaystyle=\mathbb{E}_{S\sim
p_{\pi}^{\star}}\mathopen{}\mathclose{{}\left[\big{\\{}v_{g}^{\pi}-\hat{v}_{g}^{\pi}(S;\boldsymbol{w}_{g})\big{\\}}\nabla\hat{v}_{g}^{\pi}(S;\boldsymbol{w}_{g})}\right]$
$\displaystyle\approx\big{\\{}v_{g}^{\pi}(s)-\hat{v}_{g}^{\pi}(s;\boldsymbol{w}_{g})\big{\\}}\nabla\hat{v}_{g}^{\pi}(s;\boldsymbol{w}_{g})$
(By a single sample $s$)
$\displaystyle\approx\big{\\{}\underbrace{r(s,a)+\hat{v}_{b}^{\pi}(s^{\prime})-\hat{v}_{b}^{\pi}(s)}_{\text{approximates
the true $v_{g}^{\pi}$ based on \eqref{equ:poisson}}}-\
\hat{v}_{g}^{\pi}(s;\boldsymbol{w}_{g})\big{\\}}\nabla\hat{v}_{g}^{\pi}(s;\boldsymbol{w}_{g})$
$\displaystyle=\hat{\delta}_{v_{b}}^{\pi}(s,a,s^{\prime};\boldsymbol{w}_{g})\nabla\hat{v}_{g}^{\pi}(s;\boldsymbol{w}_{g}).$

This requires further investigation whether the above parameterized
approximator for the gain $v_{g}^{\pi}$ is beneficial in practice.

##### State-value approximation $\hat{v}_{b}^{\pi}$:

We observe that most, if not all, relative state-value approximators are based
on TD, leading to semi-gradient methods (Sec 4.4.2). In discounted reward
settings, there are several non-TD approaches. These include the true gradient
methods (Sutton et al.,, 2009), as well as those using the Bellman residual
(i.e. the expected value of TD), such as Zhang et al., (2019); Geist et al.,
(2017); see also surveys by Dann et al., (2014); Geist and Pietquin, (2013).

It is interesting to investigate whether TD or not TD for learning
$\hat{v}_{b}^{\pi}$. For example, we may formulate a (true) gradient TD method
that optimizes the mean-squared _projected_ Bellman error (MSPBE), namely
$\|\hat{v}_{b}^{\pi}(\boldsymbol{w})-\mathbb{P}[\mathbb{B}_{g}^{\pi}[\hat{v}_{b}^{\pi}(\boldsymbol{w})]]\|_{\mathrm{diag}(\boldsymbol{p}_{\pi}^{\star})}^{2}$
with a projection operator $\mathbb{P}$ that projects any value approximation
onto the space of representable paramaterized approximators.

##### Action-value approximation $\hat{q}_{b}^{\pi}$:

Commonly, the estimation for $q_{b}^{\pi}$ involves the gain estimate
$\hat{v}_{g}^{\pi}$ as dictated by the Bellman expectation equation (20). It
is natural then to ask: _is it possible to perform average-reward GPI without
estimating the gain of a policy at each iteration?_ We speculate that the
answer is affirmative as follows.

Let the gain $v_{g}^{\pi}$ be the baseline for $q_{b}^{\pi}$ in a similiar
manner to $v_{b}^{\pi}$ in (24); cf. in discounted reward settings, see Weaver
and Tao, (2001, Thm 1). Then, based on the Bellman expectation equation in
action values (analogous to (12)), we have the following identity,

$q_{b}^{\pi}(s,a)-(-v_{g}^{\pi})=\underbrace{r(s,a)+\mathbb{E}_{S_{t+1}}\mathopen{}\mathclose{{}\left[v_{b}^{\pi}(S_{t+1})}\right]}_{\text{The
surrogate action-value $\mathfrak{q}_{b}^{\pi}(s,a)$}}.$ (Note different
symbols, $q_{b}^{\pi}$ vs $\mathfrak{q}_{b}^{\pi}$)

This surrogate can be parameterized as
$\hat{\mathfrak{q}}_{b}^{\pi}(s,a;\boldsymbol{w})$. Its parameter
$\boldsymbol{w}$ is updated using the following gradient estimates,

$\displaystyle-\frac{1}{2}\nabla\mathbb{E}_{S,A}\mathopen{}\mathclose{{}\left[\\{\mathfrak{q}_{b}^{\pi}(S,A)-\hat{\mathfrak{q}}_{b}^{\pi}(S,A;\boldsymbol{w})\\}^{2}}\right]$
$\displaystyle=\mathbb{E}_{S,A}\mathopen{}\mathclose{{}\left[\\{\mathfrak{q}_{b}^{\pi}(S,A)-\hat{\mathfrak{q}}_{b}^{\pi}(S,A;\boldsymbol{w})\\}\nabla\hat{\mathfrak{q}}_{b}^{\pi}(S,A;\boldsymbol{w})}\right]$
$\displaystyle=\mathbb{E}_{S,A,S^{\prime}}\Big{[}\Big{\\{}\underbrace{r(S,A)+v_{b}^{\pi}(S^{\prime})}_{\text{The
surrogate $\mathfrak{q}_{b}^{\pi}(S,A)$}}-\
\hat{\mathfrak{q}}_{b}^{\pi}(S,A;\boldsymbol{w})\Big{\\}}\nabla\hat{\mathfrak{q}}_{b}^{\pi}(S,A;\boldsymbol{w})\Big{]}$
$\displaystyle\approx\Big{\\{}r(s,a)+v_{b}^{\pi}(s^{\prime})-\hat{\mathfrak{q}}_{b}^{\pi}(s,a;\boldsymbol{w})\Big{\\}}\nabla\hat{\mathfrak{q}}_{b}^{\pi}(s,a;\boldsymbol{w})$
(Using a single sample $(s,a,s^{\prime})$)
$\displaystyle\propto\Big{\\{}r(s,a)+\underbrace{v_{b}^{\pi}(s^{\prime})+(v_{g}^{\pi}+\kappa)}_{\text{The
surrogate state-value $\nu_{b}^{\pi}(s^{\prime})$}}-\
\hat{\mathfrak{q}}_{b}^{\pi}(s,a;\boldsymbol{w})\Big{\\}}\nabla\hat{\mathfrak{q}}_{b}^{\pi}(s,a;\boldsymbol{w}),$
(Note different symbols, $v_{b}^{\pi}$ vs $\nu_{b}^{\pi}$)

for some arbitrary constant $\kappa\in\real{}$. The key is to exploit the fact
that we have one degree of freedom in the underdetermined linear systems for
policy evaluation in (20). Here, the surrogate state-value $\nu_{b}^{\pi}$ is
equal to $v_{b}^{\pi}$ up to some constant, i.e.
$\nu_{b}^{\pi}=v_{b}^{\pi}+(v_{g}^{\pi}+\kappa)$. One can estimate
$\nu_{b}^{\pi}$ in a similar fashion as $\hat{v}_{b}^{\pi}$ in (29), except
that now the gain approximation $\hat{v}_{g}^{\pi}$ is no longer needed. The
parameterized estimator $\hat{\nu}_{b}^{\pi}(\boldsymbol{w}_{\nu})$ can be
updated by following below gradient estimate,

$-\frac{1}{2}\nabla\mathbb{E}_{S\sim
p_{\pi}^{\star}}\mathopen{}\mathclose{{}\left[\\{\nu_{b}^{\pi}(S)-\hat{\nu}_{b}^{\pi}(S,\boldsymbol{w}_{\nu})\\}^{2}}\right]\approx\big{\\{}r(s,a)+\nu_{b}^{\pi}(s^{\prime};\boldsymbol{w}_{\nu})-\hat{\nu}_{b}^{\pi}(s;\boldsymbol{w}_{\nu})\big{\\}}\nabla\hat{\nu}_{b}^{\pi}(s;\boldsymbol{w}_{\nu}),$
(33)

which is based on a single sample $(s,a,s^{\prime})$. In the RHS of (33)
above, the TD of $\nu_{b}^{\pi}$ looks similar to that of discounted reward
$v_{\gamma}$, but with abused $\gamma=1$. Therefore, its stability (whether it
will grow unboundedly) warrants experiments.

##### Extras:

We notice that existing TD-based value approximators simply re-use the TD
estimate $\hat{\delta}_{v_{b}}^{\pi}$ obtained using the _old_ gain estimate
from the previous iteration, e.g. Sutton and Barto, (2018, p251, 333). They do
not harness the newly updated gain estimate for cheap recomputation of
$\hat{\delta}_{v_{b}}^{\pi}$. We anticipate that doing so will yield more
accurate evaluation of the current policy.

There are also open research questions that apply to both average- and
discounted-reward policy evaluation, but generally require different
treatment. They are presented below along with the parallel works in
discounted rewards, if any, which are put in brackets at the end of each
bullet point.

  * •

How sensitive is the estimation accuracy of $\hat{v}_{b}^{\pi}$ with respect
to the trace decay factor $\lambda$ in TD($\lambda$)? Recall that
$\hat{v}_{b}^{\pi}$ involves $\hat{v}_{g}$, which is commonly estimated using
$\hat{\delta}_{v_{b}}^{\pi}$ as in (27). (cf. Sutton and Barto, (2018, Fig
12.6))

  * •

What are the advantages and challenges of natural gradients for the critic?
Note that natural gradients typically are applied only for the actor. (cf. Wu
et al., (2017))

  * •

As can be observed, the weight update in (30) resembles that of SGD with
momentum. It begs the question: what is the connection between backward-view
eligibility traces and momentum in gradient-based step-wise updates for both
actor and critic parameters? (cf. Vieillard et al., (2020); Nichols, (2017);
Xu et al., (2006))

  * •

How to construct “high-performing” basis vectors for the value approximation?
To what extent does the limitation of $\boldsymbol{\theta}$-compatible critic
((31)) outweigh its benefit? Also notice the Bellman average-reward bases
(Mahadevan,, 2009, Sec 11.2.4), as well as non-linear (over-)parameterized
neural networks. (cf. Wang et al., (2019))

  * •

Among 3 choices for advantage approximation (Sec 4.2), which one is most
beneficial?

###  5.3 Further open research questions

In the following passages, relevant works in discounted reward settings are
mentioned, if any, inside the brackets at the end of each part.

##### On batch settings:

For on-policy online RL without experience replay buffer, we pose the
following questions. How to determine a batch size that balances the trade-off
between collecting more samples with the current policy and updating the
policy more often with fewer numbers of samples? How to apply the concept of
backward-view eligibility traces in batch settings? (cf. Harb and Precup,
(2017)).

##### On value- vs policy-iteration schemes:

As can be observed in Tables LABEL:tbl:valiter_work and LABEL:tbl:politer_work
(in Appendix LABEL:sec:table_of_existing), there is less work on value- than
policy-iteration schemes; even less when considering only function
approximation settings. Our preliminary experiments suggest that although
following value iteration is straightforward (cf. policy iteration with
evaluation and improvement steps), it is more difficult to make it “work”,
especially with function approximation. One challenge is to specify the proper
offset, e.g. $v_{g}^{*}$ or its estimate, in RVI-like methods to bound the
iterates. Moreover, Mahadevan, 1996a (, Sec 3.5) highlighted that the seminal
value-iteration based RL, i.e. average reward $Q_{b}$-learning, is sensitive
to exploration.

We posit these questions. Is it still worth it to adopt the value iteration
scheme after all? Which scheme is more advantageous in terms of exploration in
RL? How to reconcile both schemes? (cf. O’Donoghue et al., (2016); Schulman et
al., (2017); Wang et al., (2020)).

##### On distributional (cf. expected-value) perspective:

There exist few works on distributional views. Morimura et al., (2010)
proposed estimating $\nabla\log p^{\boldsymbol{\theta}}(s)$ for obtaining the
gradient estimate $\hat{\nabla}v_{g}(\boldsymbol{\theta})$ in (22), removing
the need to estimate the action value $q_{b}^{\boldsymbol{\theta}}$. One
important question is how to scale up the distribution (density) estimation
for large RL problems. (cf. Bellemare et al., (2017)).

##### On MDP modeling:

The broadest class that can be handled by existing average-reward RL is the
unichain MDP; note that most works assume the more specific class, i.e. the
recurrent (ergodic) MDP. To our knowledge, there is still no average reward
model-free RL for multichain MDPs (which is the most general class).

We also desire to apply average-reward RL to continuous state problems, for
which we may benefit from the DP theory on general states, e.g. Sennott,
(1999, Ch 8). There are few attempts thus far, for instance, (Yang et al.,,
2019), which is limited to linear quadratic regulator with ergodic cost.

##### On optimality criteria:

The average reward optimality is underselective for problems with transient
states, for which we need $(n=0)$-discount (bias) optimality, or even higher
$n$-discount optimality. This underselective-ness motivates the weighted
optimality in DP (Krass et al.,, 1992). In RL, Mahadevan, 1996b  developed
bias-optimal Q-learning.

In the other extreme, $(n=\infty)$-discount optimality is the most selective
criterion. According to Puterman, (1994, Thm 10.1.5), it is proven to be
equivalent to the Blackwell optimality, which intuitively claims that upon
considering sufficiently far into the future via the Blackwell’s discount
factor $\gamma_{\mathrm{Bw}}$, there is no policy better than the Blackwell
optimal policy. Moreover, optimizing the discounted reward does not require
any knowledge about the MDP structure (i.e. recurrent, unichain, multichain
classification). Therefore, one of pressing questions is on estimating such
$\gamma_{\mathrm{Bw}}$ in RL.

## Acknowledgments

We thank Aaron Snoswell, Nathaniel Du Preez-Wilkinson, Jordan Bishop, Russell
Tsuchida, and Matthew Aitchison for insightful discussions that helped improve
this paper. Vektor is supported by the University of Queensland Research
Training Scholarship.

## References

  * (1) Abbasi-Yadkori, Y., Bartlett, P., Bhatia, K., Lazic, N., Szepesvari, C., and Weisz, G. (2019a).  POLITEX: Regret bounds for policy iteration using expert prediction.  In ICML.
  * (2) Abbasi-Yadkori, Y., Lazic, N., and Szepesvari, C. (2019b).  Model-free linear quadratic control via reduction to expert prediction.  In AISTATS.
  * Abdulla and Bhatnagar, (2007) Abdulla, M. S. and Bhatnagar, S. (2007).  Reinforcement learning based algorithms for average cost markov decision processes.  Discrete Event Dynamic Systems, 17(1).
  * Abounadi et al., (2001) Abounadi, J., Bertsekas, D., and Borkar, V. S. (2001).  Learning algorithms for markov decision processes with average cost.  SIAM J. Control Optim., 40(3).
  * Agarwal et al., (2019) Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. (2019).  On the theory of policy gradient methods: Optimality, approximation, and distribution shift.  arXiv: 1908.00261.
  * Avrachenkov and Borkar, (2020) Avrachenkov, K. and Borkar, V. S. (2020).  Whittle index based q-learning for restless bandits with average reward.  arXiv:2004.14427.
  * Bagnell and Schneider, (2003) Bagnell, J. A. D. and Schneider, J. (2003).  Covariant policy search.  In Proceeding of the International Joint Conference on Artifical Intelligence.
  * Bartlett and Baxter, (2002) Bartlett, P. L. and Baxter, J. (2002).  Estimation and approximation bounds for gradient-based reinforcement learning.  Journal of Computer and System Sciences, 64(1).
  * Bellemare et al., (2017) Bellemare, M. G., Dabney, W., and Munos, R. (2017).  A distributional perspective on reinforcement learning.  In ICML.
  * Bertsekas, (2012) Bertsekas, D. P. (2012).  Dynamic Programming and Optimal Control, Vol. II.  Athena Scientific, 4th edition.
  * Bertsekas and Tsitsiklis, (1996) Bertsekas, D. P. and Tsitsiklis, J. N. (1996).  Neuro-Dynamic Programming.  Athena Scientific, 1st edition.
  * Bhatnagar et al., (2008) Bhatnagar, S., Ghavamzadeh, M., Lee, M., and Sutton, R. S. (2008).  Incremental natural actor-critic algorithms.  In NIPS.
  * (13) Bhatnagar, S., Sutton, R. S., Ghavamzadeh, M., and Lee, M. (2009a).  Natural actor-critic algorithms.  Automatica, 45.
  * (14) Bhatnagar, S., Sutton, R. S., Ghavamzadeh, M., and Lee, M. (2009b).  Natural actor-critic algorithms.  Technical report.
  * Cao, (2007) Cao, X. (2007).  Stochastic Learning and Optimization: A Sensitivity-Based Approach.  International Series on Discrete Event Dynamic Systems, v. 17. Springer US.
  * Castro and Mannor, (2010) Castro, D. D. and Mannor, S. (2010).  Adaptive bases for reinforcement learning.  In Machine Learning and Knowledge Discovery in Databases.
  * Castro and Meir, (2010) Castro, D. D. and Meir, R. (2010).  A convergent online single time scale actor critic algorithm.  Journal of Machine Learning Research.
  * Castro et al., (2009) Castro, D. D., Volkinshtein, D., and Meir, R. (2009).  Temporal difference based actor critic learning - convergence and neural implementation.  In NIPS.
  * Chang, (2009) Chang, H. S. (2009).  Decentralized learning in finite markov chains: Revisited.  IEEE Transactions on Automatic Control, 54(7):1648–1653.
  * Chen-Yu Wei, (2019) Chen-Yu Wei, Mehdi Jafarnia-Jahromi, H. L. H. S. R. J. (2019).  Model-free reinforcement learning in infinite-horizon average-reward markov decision processes.  arXiv:1910.07072.
  * Dann et al., (2014) Dann, C., Neumann, G., and Peters, J. (2014).  Policy evaluation with temporal differences: A survey and comparison.  Journal of Machine Learning Research, 15(24):809–883.
  * Das et al., (1999) Das, T., Gosavi, A., Mahadevan, S., and Marchalleck, N. (1999).  Solving semi-markov decision problems using average reward reinforcement learning.  Manage. Sci., 45(4).
  * Dean et al., (2017) Dean, S., Mania, H., Matni, N., Recht, B., and Tu, S. (2017).  On the sample complexity of the linear quadratic regulator.  arXiv:1710.01688.
  * Degris et al., (2012) Degris, T., Pilarski, P. M., and Sutton, R. S. (2012).  Model-free reinforcement learning with continuous action in practice.  In 2012 American Control Conference (ACC).
  * Degris et al., (2012) Degris, T., White, M., and Sutton, R. S. (2012).  Off-policy actor-critic.  In ICML.
  * Deisenroth et al., (2013) Deisenroth, M. P., Neumann, G., and Peters, J. (2013).  A survey on policy search for robotics.  Foundations and Trends in Robotics, 2(1–2):1–142.
  * Devraj et al., (2018) Devraj, A. M., Kontoyiannis, I., and Meyn, S. P. (2018).  Differential temporal difference learning.  arXiv:1812.11137.
  * Devraj and Meyn, (2016) Devraj, A. M. and Meyn, S. P. (2016).  Differential td learning for value function approximation.  In 2016 IEEE 55th Conference on Decision and Control (CDC), pages 6347–6354.
  * Dewanto and Gallagher, (2021) Dewanto, V. and Gallagher, M. (2021).  Examining average and discounted reward optimality criteria in reinforcement learning.  arXiv:2107.01348.
  * Duan et al., (2016) Duan, Y., Chen, X., Houthooft, R., Schulman, J., and Abbeel, P. (2016).  Benchmarking deep reinforcement learning for continuous control.  In ICML.
  * Feinberg and Shwartz, (2002) Feinberg, E. A. and Shwartz, A. (2002).  Handbook of Markov Decision Processes: Methods and Applications, volume 40.  Springer US.
  * Furmston and Barber, (2012) Furmston, T. and Barber, D. (2012).  A unifying perspective of parametric policy search methods for markov decision processes.  In Advances in Neural Information Processing Systems 25.
  * Furmston et al., (2016) Furmston, T., Lever, G., and Barber, D. (2016).  Approximate newton methods for policy search in markov decision processes.  Journal of Machine Learning Research, 17(227).
  * Geist and Pietquin, (2013) Geist, M. and Pietquin, O. (2013).  Algorithmic survey of parametric value function approximation.  IEEE Transactions on Neural Networks and Learning Systems, 24(6):845–867.
  * Geist et al., (2017) Geist, M., Piot, B., and Pietquin, O. (2017).  Is the bellman residual a bad proxy?  In Advances in Neural Information Processing Systems 30.
  * (36) Gosavi, A. (2004a).  A reinforcement learning algorithm based on policy iteration for average reward: Empirical results with yield management and convergence analysis.  Machine Learning, 55(1).
  * (37) Gosavi, A. (2004b).  Reinforcement learning for long-run average cost.  European Journal of Operational Research, 155(3):654 – 674.
  * Gosavi, (2015) Gosavi, A. (2015).  Simulation-Based Optimization: Parametric Optimization Techniques and Reinforcement Learning.  Springer Publishing Company, Incorporated, 2nd edition.
  * Gosavi et al., (2002) Gosavi, A., BANDLA, N., and DAS, T. K. (2002).  A reinforcement learning approach to a single leg airline revenue management problem with multiple fare classes and overbooking.  IIE Transactions, 34(9).
  * Gray, (2009) Gray, R. M. (2009).  Probability, Random Processes, and Ergodic Properties.  Springer US, 2nd edition.
  * Greensmith et al., (2004) Greensmith, E., Bartlett, P. L., and Baxter, J. (2004).  Variance reduction techniques for gradient estimates in reinforcement learning.  J. Mach. Learn. Res., 5.
  * Hao et al., (2020) Hao, B., Lazic, N., Abbasi-Yadkori, Y., Joulani, P., and Szepesvari, C. (2020).  Provably efficient adaptive approximate policy iteration.
  * Harb and Precup, (2017) Harb, J. and Precup, D. (2017).  Investigating recurrence and eligibility traces in deep q-networks.  CoRR, abs/1704.05495.
  * Hasselt, (2010) Hasselt, H. V. (2010).  Double q-learning.  In Lafferty, J. D., Williams, C. K. I., Shawe-Taylor, J., Zemel, R. S., and Culotta, A., editors, Advances in Neural Information Processing Systems 23, pages 2613–2621. Curran Associates, Inc.
  * Hasselt et al., (2016) Hasselt, H. v., Guez, A., and Silver, D. (2016).  Deep reinforcement learning with double q-learning.  In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence.
  * Heess et al., (2012) Heess, N., Silver, D., and Teh, Y. W. (2012).  Actor-critic reinforcement learning with energy-based policies.  In European Workshop on Reinforcement Learning, Proceedings of Machine Learning Research.
  * Hessel et al., (2018) Hessel, M., Modayil, J., van Hasselt, H., Schaul, T., Ostrovski, G., Dabney, W., Horgan, D., Piot, B., Azar, M. G., and Silver, D. (2018).  Rainbow: Combining improvements in deep reinforcement learning.  In AAAI. AAAI Press.
  * Howard, (1960) Howard, R. A. (1960).  Dynamic Programming and Markov Processes.  Technology Press of the Massachusetts Institute of Technology.
  * Iwaki and Asada, (2019) Iwaki, R. and Asada, M. (2019).  Implicit incremental natural actor critic algorithm.  Neural Networks, 109.
  * Jafarnia-Jahromi et al., (2020) Jafarnia-Jahromi, M., Wei, C.-Y., Jain, R., and Luo, H. (2020).  A model-free learning algorithm for infinite-horizon average-reward mdps with near-optimal regret.
  * Jaksch et al., (2010) Jaksch, T., Ortner, R., and Auer, P. (2010).  Near-optimal regret bounds for reinforcement learning.  J. Mach. Learn. Res., 11:1563–1600.
  * Jalali and Ferguson, (1990) Jalali, A. and Ferguson, M. J. (1990).  A distributed asynchronous algorithm for expected average cost dynamic programming.  In 29th IEEE Conference on Decision and Control, pages 1394–1395 vol.3.
  * Kakade, (2002) Kakade, S. (2002).  A natural policy gradient.  In NIPS.
  * Karimi et al., (2019) Karimi, B., Miasojedow, B., Moulines, E., and Wai, H.-T. (2019).  Non-asymptotic analysis of biased stochastic approximation scheme.
  * Konda and Tsitsiklis, (2003) Konda, V. R. and Tsitsiklis, J. N. (2003).  On actor-critic algorithms.  SIAM J. Control Optim., 42(4).
  * Krass et al., (1992) Krass, D., Filar, J. A., and Sinha, S. S. (1992).  A weighted markov decision process.  Operations Research, 40(6).
  * Lagoudakis, (2003) Lagoudakis, M. G. (2003).  Efficient Approximate Policy Iteration Methods for Sequential Decision Making in Reinforcement Learning.  PhD thesis, Department of Computer Science, Duke University.
  * Liu et al., (2018) Liu, Q., Li, L., Tang, Z., and Zhou, D. (2018).  Breaking the curse of horizon: Infinite-horizon off-policy estimation.  In Advances in Neural Information Processing Systems 31.
  * (59) Mahadevan, S. (1996a).  Average reward reinforcement learning: Foundations, algorithms, and empirical results.  Machine Learning.
  * (60) Mahadevan, S. (1996b).  Sensitive discount optimality: Unifying discounted and average reward reinforcement learning.  In ICML.
  * Mahadevan, (2009) Mahadevan, S. (2009).  Learning representation and control in markov decision processes: New frontiers.  Foundations and Trends in Machine Learning, 1(4):403–565.
  * Marbach and Tsitsiklis, (2001) Marbach, P. and Tsitsiklis, J. N. (2001).  Simulation-based optimization of markov reward processes.  IEEE Transactions on Automatic Control, 46(2):191–209.
  * (63) Matsubara, T., Morimura, T., and Morimoto, J. (2010a).  Adaptive step-size policy gradients with average reward metric.  In Proceedings of the 2nd Asian Conference on Machine Learning, JMLR Proceedings.
  * (64) Matsubara, T., Morimura, T., and Morimoto, J. (2010b).  Adaptive step-size policy gradients with average reward metric.  In Proceedings of the 2nd Asian Conference on Machine Learning, ACML 2010, Tokyo, Japan, November 8-10, 2010, pages 285–298.
  * Miyamae et al., (2010) Miyamae, A., Nagata, Y., Ono, I., and Kobayashi, S. (2010).  Natural policy gradient methods with parameter-based exploration for control tasks.  In Advances in Neural Information Processing Systems 23.
  * Morimura et al., (2014) Morimura, T., Osogami, T., and Shirai, T. (2014).  Mixing-time regularized policy gradient.  In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence, AAAI’14.
  * Morimura et al., (2008) Morimura, T., Uchibe, E., Yoshimoto, J., and Doya, K. (2008).  A new natural policy gradient by stationary distribution metric.  In European Conference Machine Learning and Knowledge Discovery in Databases ECML/PKDD, pages 82–97. Springer.
  * Morimura et al., (2009) Morimura, T., Uchibe, E., Yoshimoto, J., and Doya, K. (2009).  A generalized natural actor-critic algorithm.  In Advances in Neural Information Processing Systems 22.
  * Morimura et al., (2010) Morimura, T., Uchibe, E., Yoshimoto, J., Peters, J., and Doya, K. (2010).  Derivatives of logarithmic stationary distributions for policy gradient reinforcement learning.  Neural Computation, 22(2):342–376.
  * Neu et al., (2017) Neu, G., Jonsson, A., and Gómez, V. (2017).  A unified view of entropy-regularized markov decision processes.  CoRR, abs/1705.07798.
  * Nichols, (2017) Nichols, B. D. (2017).  A comparison of eligibility trace and momentum on sarsa in continuous state-and action-space.  In 2017 9th Computer Science and Electronic Engineering (CEEC), pages 55–59.
  * O’Donoghue et al., (2016) O’Donoghue, B., Munos, R., Kavukcuoglu, K., and Mnih, V. (2016).  PGQL: combining policy gradient and q-learning.  CoRR, abs/1611.01626.
  * Ormoneit and Glynn, (2001) Ormoneit, D. and Glynn, P. W. (2001).  Kernel-based reinforcement learning in average-cost problems: An application to optimal portfolio choice.  In Advances in Neural Information Processing Systems 13.
  * Ormoneit and Glynn, (2002) Ormoneit, D. and Glynn, P. W. (2002).  Kernel-based reinforcement learning in average-cost problems.  IEEE Transactions on Automatic Control, 47(10):1624–1636.
  * Ortner, (2007) Ortner, R. (2007).  Pseudometrics for state aggregation in average reward markov decision processes.  In Hutter, M., Servedio, R. A., and Takimoto, E., editors, Algorithmic Learning Theory, pages 373–387, Berlin, Heidelberg. Springer Berlin Heidelberg.
  * Peters and Schaal, (2008) Peters, J. and Schaal, S. (2008).  Natural actor-critic.  Neurocomputing, 71(7).
  * Powell, (2011) Powell, W. (2011).  Approximate Dynamic Programming: Solving the Curses of Dimensionality.  Wiley Series in Probability and Statistics. Wiley, 2nd edition.
  * Prashanth and Bhatnagar, (2011) Prashanth, L. A. and Bhatnagar, S. (2011).  Reinforcement learning with average cost for adaptive control of traffic lights at intersections.  In 2011 14th International IEEE Conference on Intelligent Transportation Systems (ITSC), pages 1640–1645.
  * Puterman, (1994) Puterman, M. L. (1994).  Markov Decision Processes: Discrete Stochastic Dynamic Programming.  John Wiley & Sons, Inc., 1st edition.
  * Qiu et al., (2019) Qiu, S., Yang, Z., Ye, J., and Wang, Z. (2019).  On the finite-time convergence of actor-critic algorithm.  In Optimization Foundations for Reinforcement Learning Workshop, NeurIPS 2019.
  * Schneckenreither, (2020) Schneckenreither, M. (2020).  Average reward adjusted discounted reinforcement learning: Near-blackwell-optimal policies for real-world applications.  arXiv: 2004.00857.
  * Schulman et al., (2017) Schulman, J., Abbeel, P., and Chen, X. (2017).  Equivalence between policy gradients and soft q-learning.  CoRR, abs/1704.06440.
  * Schwartz, (1993) Schwartz, A. (1993).  A reinforcement learning method for maximizing undiscounted rewards.  ICML, pages 298–305.
  * Sennott, (1999) Sennott, L. I. (1999).  Stochastic Dynamic Programming and the Control of Queueing Systems.  Wiley-Interscience, New York, NY, USA.
  * Silver et al., (2008) Silver, D., Sutton, R. S., and Müller, M. (2008).  Sample-based learning and search with permanent and transient memories.  In Proceedings of the 25th International Conference on Machine Learning, ICML ’08.
  * Singh, (1994) Singh, S. P. (1994).  Reinforcement learning algorithms for average-payoff markovian decision processes.  AAAI ’94, pages 700–705.
  * Strens, (2000) Strens, M. J. A. (2000).  A bayesian framework for reinforcement learning.  In ICML.
  * Sutton, (1990) Sutton, R. S. (1990).  Integrated architecture for learning, planning, and reacting based on approximating dynamic programming.  In Proceedings of the Seventh International Conference (1990) on Machine Learning.
  * Sutton and Barto, (2018) Sutton, R. S. and Barto, A. G. (2018).  Introduction to Reinforcement Learning.  MIT Press.
  * Sutton et al., (2009) Sutton, R. S., Maei, H. R., Precup, D., Bhatnagar, S., Silver, D., Szepesvári, C., and Wiewiora, E. (2009).  Fast gradient-descent methods for temporal-difference learning with linear function approximation.  In Proceedings of the 26th ICML.
  * Sutton et al., (2000) Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y. (2000).  Policy gradient methods for reinforcement learning with function approximation.  In NIPS.
  * Tadepalli and Ok, (1998) Tadepalli, P. and Ok, D. (1998).  Model-based average reward reinforcement learning.  Artificial Intelligence, 100(1).
  * Thomas, (2014) Thomas, P. (2014).  Genga: A generalization of natural gradient ascent with positive and negative convergence results.  In Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research.
  * Tsitsiklis and Roy, (1999) Tsitsiklis, J. N. and Roy, B. V. (1999).  Average cost temporal-difference learning.  Automatica, 35(11).
  * Ueno et al., (2008) Ueno, T., Kawanabe, M., Mori, T., Maeda, S.-i., and Ishii, S. (2008).  A semiparametric statistical approach to model-free policy evaluation.  In Proceedings of the 25th International Conference on Machine Learning.
  * Vemula et al., (2019) Vemula, A., Sun, W., and Bagnell, J. A. (2019).  Contrasting exploration in parameter and action space: A zeroth-order optimization perspective.  In The 22nd AISTATS 2019, Proceedings of Machine Learning Research.
  * Vieillard et al., (2020) Vieillard, N., Scherrer, B., Pietquin, O., and Geist, M. (2020).  Momentum in reinforcement learning.  In Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research. PMLR.
  * Wan et al., (2020) Wan, Y., Naik, A., and Sutton, R. S. (2020).  Learning and planning in average-reward markov decision processes.
  * Wang et al., (2019) Wang, L., Cai, Q., Yang, Z., and Wang, Z. (2019).  Neural policy gradient methods: Global optimality and rates of convergence.
  * Wang, (2017) Wang, M. (2017).  Primal-dual $\pi$ learning: Sample complexity and sublinear run time for ergodic markov decision problems.  CoRR, abs/1710.06100.
  * Wang et al., (2020) Wang, Y., Dong, K., Chen, X., and Wang, L. (2020).  Q-learning with {ucb} exploration is sample efficient for infinite-horizon {mdp}.  In International Conference on Learning Representations.
  * Weaver and Tao, (2001) Weaver, L. and Tao, N. (2001).  The optimal reward baseline for gradient-based reinforcement learning.  In Proceedings of the Seventeenth Conference on Uncertainty in Artificial Intelligence, UAI’01.
  * Wheeler and Narendra, (1986) Wheeler, R. and Narendra, K. (1986).  Decentralized learning in finite markov chains.  IEEE Transactions on Automatic Control, 31(6):519–526.
  * White, (1963) White, D. (1963).  Dynamic programming, markov chains, and the method of successive approximations.  Journal of Mathematical Analysis and Applications, 6(3):373 – 376\.
  * Wu et al., (2017) Wu, Y., Mansimov, E., Grosse, R. B., Liao, S., and Ba, J. (2017).  Scalable trust-region method for deep reinforcement learning using kronecker-factored approximation.  In Advances in Neural Information Processing Systems 30.
  * Wu et al., (2020) Wu, Y., Zhang, W., Xu, P., and Gu, Q. (2020).  A finite time analysis of two time-scale actor critic methods.  arXiv:2005.01350.
  * Xu et al., (2006) Xu, J., Liang, F., and Yu, W. (2006).  Learning with eligibility traces in adaptive critic designs.  In 2006 IEEE International Conference on Vehicular Electronics and Safety, pages 309–313.
  * Yang et al., (2016) Yang, S., Gao, Y., An, B., Wang, H., and Chen, X. (2016).  Efficient average reward reinforcement learning using constant shifting values.  In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI’16. AAAI Press.
  * Yang et al., (2019) Yang, Z., Chen, Y., Hong, M., and Wang, Z. (2019).  Provably global convergence of actor-critic: A case for linear quadratic regulator with ergodic cost.  In Advances in Neural Information Processing Systems 32.
  * Yu and Bertsekas, (2009) Yu, H. and Bertsekas, D. P. (2009).  Convergence results for some temporal difference methods based on least squares.  IEEE Transactions on Automatic Control, 54(7):1515–1531.
  * Zhang et al., (2019) Zhang, S., Boehmer, W., and Whiteson, S. (2019).  Deep residual reinforcement learning.  CoRR, abs/1905.01072.