# Performance Bounds for Policy-Based Average Reward Reinforcement Learning
Algorithms

Yashaswini Murthy
Electrical and Computer Engineering
University of Illinois Urbana-Champaign
Urbana, IL 61801
<EMAIL_ADDRESS>
&Mehrdad Moharrami
Electrical and Computer Engineering
University of Illinois Urbana-Champaign
Urbana, IL 61801
<EMAIL_ADDRESS>&R. Srikant
Electrical and Computer Engineering
University of Illinois Urbana-Champaign
Urbana, IL 61801
<EMAIL_ADDRESS>
###### Abstract

Many policy-based reinforcement learning (RL) algorithms can be viewed as
instantiations of approximate policy iteration (PI), i.e., where policy
improvement and policy evaluation are both performed approximately. In
applications where the average reward objective is the meaningful performance
metric, discounted reward formulations are often used with the discount factor
being close to $1,$ which is equivalent to making the expected horizon very
large. However, the corresponding theoretical bounds for error performance
scale with the square of the horizon. Thus, even after dividing the total
reward by the length of the horizon, the corresponding performance bounds for
average reward problems go to infinity. Therefore, an open problem has been to
obtain meaningful performance bounds for approximate PI and RL algorithms for
the average-reward setting. In this paper, we solve this open problem by
obtaining the first finite-time error bounds for average-reward MDPs, and show
that the asymptotic error goes to zero in the limit as policy evaluation and
policy improvement errors go to zero.

##  1 Introduction

Reinforcement Learning algorithms can be broadly classified into value-based
methods and policy-based methods. In the case of discounted-reward Markov
Decision Processes (MDPs), value-based methods such as Q-learning [WD92,
Tsi94, JJS93, SB18, BT96], fitted value iteration [MS08] and target network
Q-learning [CCM22] can be viewed as approximately solving the fixed point of
the Bellman optimality equation to find the value function and an
approximately optimal control policy. In other words value iteration is
approximately implemented for discounted reward MDPs [Ber11, Ber12, Put14]. In
policy-gradient methods [AKLM21], a gradient step is used to improve the
policy, somewhat similar to the policy improvement step in policy iteration
for discounted-reward MDPs. In a recent paper [CM22], it has been shown that
many policy-based methods for discounted-reward MDPs can be viewed as special
cases of approximate policy iteration. The classical results on approximate
policy iteration [BT96] assume that the error in the policy evaluation and
improvement steps are constant, independent of the iteration. The key idea in
[CM22] is to show that a simple modification of the proof in [BT96] can be
used to allow for iteration-dependent policy evaluation and improvement
errors, which is then used to make the connection to policy-based methods. Our
goal in this paper is to derive similar results for average-reward problems.
Average-reward problems [ABB01, WNS21, ZWSW21, Mah96, YB09, Gos04, Sin94] are,
in some sense, harder to study than their discounted-reward counterparts. We
now discuss why this is so by recalling the error bounds for discounted-reward
problems and examining them in an appropriate limit to study their
applicability to average-reward problems.

The fundamental result on approximate policy iteration for discounted reward
MDPs which allows the connection to policy-based methods is the following
[BT96]:

$\limsup_{k\to\infty}\|J_{\mu_{k}}-J_{*}^{\alpha}\|_{\infty}\leq
H_{\alpha}^{2}(\epsilon+2\alpha\delta),$ (1)

where $\alpha$ is the discount factor, $H_{\alpha}=1/(1-\alpha),$
$J_{*}^{\alpha}$ is the optimal value function, $J_{\mu_{k}}$ is the value
function associated with the policy obtained after $k$ iterations of
approximate policy iteration, $\epsilon$ is the policy improvement error, and
$\delta$ is the policy evaluation error. Thus, as $\epsilon,\delta\rightarrow
0,$ we recover the result that standard policy iteration converges. On the
other hand, to understand whether the above bound is useful to study average-
reward problems, we write Equation 1 as

$\limsup_{k\to\infty}\frac{1}{H_{\alpha}}\|J_{\mu_{k}}-J_{*}^{\alpha}\|_{\infty}\leq
H_{\alpha}(\epsilon+2\alpha\delta).$

Under mild conditions [Ber11, Ros14], it is well known that each element of
the value function vector approaches the average-reward for each fixed policy
and for the optimal policy, in the limit $\alpha\rightarrow 1$. Hence, the
left-hand side of the above equation is an approximation to the error in
approximate policy iteration for average-reward MDPs; the right-hand side
which gives an upper bound on this error blows up to infinity, i.e., when
$\alpha\rightarrow 1.$ Thus, unlike in the discounted-reward case, the above
bound fails to even recover the well-known convergence of standard policy
iteration in average-reward case in the limit $\epsilon,\delta\rightarrow 0$
(since we have to let $\alpha\rightarrow 1$ before letting
$\epsilon,\delta\rightarrow 0$ ). However, as mentioned in [BT96], it is also
well known that approximate policy iteration performs much better than the
bound suggests. The main goal of our paper is to resolve this discrepancy
between theory and practice.

###  1.1 Contributions

It is well known that the error bound for discounted-reward, approximate
policy iteration is tight for unichain MDPs [BT96]. Thus, it is impossible to
improve upon the bound in general. However, as will be explained in a later
section, it is easy to convert most reasonable unichain MDPs to MDPs where
every stationary policy results in an irreducible Markov chain with an
arbitrarily small loss of reward. So the natural question to ask is whether
the bound can be dramatically improved for MDPs where every stationary policy
results in an irreducible Markov chain. To the best of our knowledge, no such
bound was available in the prior literature.

Our main contributions are as follows:

  * •

Under the assumption that every stationary policy induces an irreducible
Markov chain, we first perform a Schweitzer transformation of the MDP [Sch71]
and obtain finite-time error bounds for average-reward approximate policy
iteration.

  * •

Using the above finite-time error bounds, we prove an error bound of the form

$\limsup_{k\to\infty}J^{*}-J_{\mu_{k}}\leq f(\epsilon,\delta),$

for average-reward approximate policy iteration for a function $f$ such that
$f(\epsilon,\delta)\rightarrow 0$ in the limit as $\epsilon,\delta\rightarrow
0.$ Note that this is in sharp contrast to the result that one can obtain from
the discounted-reward analysis where the error bound blows up to infinity when
applied to discount factors approaching $1,$ which is the appropriate limit to
convert discounted-reward problems to average-reward problems.

  * •

The main difficulty in obtaining the above bound when compared to the
discounted-reward case is the lack of infinity-norm contraction property for
the Bellman operator in the average-reward case. In most analysis of average-
reward problems, this difficulty is circumvented by the use of a span-
contraction property [Put14]. However, the span contraction property is
insufficient for our purpose and therefore, we use a technique due to [VdW80]
for the study of a different algorithm called modified policy iteration in
[Put14].

  * •

Next, we extend the above analysis to obtain finite-iteration error bounds for
the case where the policy evaluation and improvement errors can potentially
vary from iteration to iteration. Further, we allow these errors to be random
(as would be the case, for example, when one uses TD learning for policy
evaluation and soft policy improvement) and obtain expected error bounds on
approximate policy iteration after a finite number of iterations.

  * •

Our error bounds are in a form such that one can then apply them to many
policy-based RL algorithms, i.e., we can simply plug in error bounds for
specific policy evaluation or policy improvement algorithms. We illustrate the
applicability of the results to several different policy-based RL methods
(softmax update, greedy update and mirror descent update) studied in the
literature [MXSS20, BT96, AYBB+19, AKLM21].

  * •

While the main focus of our paper is on offline learning, we provide
connections to regret bounds for online learning in average-reward MDPS as in
[AYBB+19, LYAYS21].

###  1.2 Related Work

Our work in this paper is most closely related to the work in [CM22]. The main
contribution there was to recognize that an extension of the approximate
policy iteration results in [BT96] can be used to derive finite-time error
bounds for many RL-based algorithms. The idea of considering iteration-
dependent policy evaluation and improvement bounds was also used to study
policy iteration with function approximation in discounted-reward MDPs in
[WLLS21]. Our contribution here is to derive the first error bound for
approximate policy iteration for average-reward MDPs and then write it in a
form which can be applied to policy-based RL methods for average-reward TD
learning. To the best of our knowledge, no known error bounds existed in prior
literature for average-reward approximate policy iteration due to the fact
that the corresponding bounds for discounted MDPs increase proportional to the
square of length of the horizon. Thus, in the limit as the horizon increases
to infinity, we have essentially reduced the dependence of the error from the
square of the length of the horizon to linear in the length of the horizon.

RL algorithms have not been studied as extensively for the average-reward case
as they are for discounted-reward MDPs. There is recent work [ZZM21] on
average-reward TD-learning which we leverage to illustrate the applicability
of our results. There are also asymptotic convergence results for policy
gradient and actor-critic methods for average-reward MDPs [TVR99, KT99,
BSGL09, MMT00]. However, these results only prove convergence to a stationary
point and there are no global convergence results. The original paper on
natural policy gradient (NPG) is written for average-reward MDPs, but the
extensive performance analysis of NPG in subsequent work such as [AKLM21]
seems to only consider the discounted-reward case. Recent work [AYBB+19,
LYAYS21] considers mirror descent in average reward RL but do not provide
performance results for other RL algorithms. In a later section, we compare
our results to [AYBB+19, LYAYS21] in the special case of mirror descent-type
policy updates

##  2 Model and Preliminaries

###  2.1 Average Reward Formulation

We consider the class of infinite horizon MDPs with finite state space
$\mathcal{S}$, finite action space $\mathcal{A}$, and transition kernel
$\mathbb{P}$, where $|\mathcal{S}|=n$ and $|\mathcal{A}|=m$. Let
$\Delta\mathcal{A}$ denote the probability simplex over actions. We consider
the class of randomized policies
$\Pi=\\{\mu:\mathcal{S}\to\Delta\mathcal{A}\\}$, so that a policy $\mu$
assigns a probability vector over actions to each state. Given a policy $\mu$,
the transition kernel for the underlying Markov process is denoted by
$\mathbb{P}_{\mu}:\mathcal{S}\to\mathcal{S}$, where
$\mathbb{P}_{\mu}(s^{\prime}|s):=\sum_{a\in\mathcal{A}}\mu(a|s)\mathbb{P}(s^{\prime}|s,a)$
is the probability of moving to state $s^{\prime}\in\mathcal{S}$ from
$s\in\mathcal{S}$ upon taking action $\mu(s)\in\mathcal{A}$. Associated with
each state-action pair $(s,a)$, is a one-step reward which is denoted by
$r_{\mu}(s):=\mathbb{E}_{a\sim\mu(s)}r(s,a)$.

Let $J_{\mu}\in\mathbb{R}$ be the average reward associated with the policy
$\mu\in\Pi$, i.e. $J_{\mu}$ is defined as:

$J_{\mu}=\lim_{T\to\infty}\frac{\mathbb{E}_{\mu}\left(\sum_{i=0}^{T-1}r_{\mu}(s_{i})\right)}{T}.$

Here the expectation is taken with respect to the measure $\mathbb{P}_{\mu}$
associated with the policy $\mu$. Let $h_{\mu}\in\mathbb{R}^{n}$ be the
relative value function associated with the policy $\mu$. Defining
$\boldsymbol{1}\in\mathbb{R}^{n}$ to be the vector of all ones, the pair
$(J_{\mu},h_{\mu})$ satisfies the following average reward Bellman equation:

$J_{\mu}\boldsymbol{1}+h_{\mu}=r_{\mu}+\mathbb{P}_{\mu}h_{\mu}.$ (2)

Let $\pi_{\mu}\in\mathbb{R}^{n}$ denote the stationary distribution associated
with the kernel $\mathbb{P}_{\mu}$. Let
$\mathbb{P}^{*}_{\mu}=\boldsymbol{1}\pi_{\mu}^{\top}\in\mathbb{R}^{n\times n}$
denote the matrix whose rows are $\pi_{\mu}^{\top}$. Using
$\mathbb{P}^{*}_{\mu}=\mathbb{P}_{\mu}^{*}\mathbb{P}_{\mu}$, we get the
following characterization of the average reward by multiplying both sides of
Equation 2 with $\mathbb{P}^{*}_{\mu}$:
$J_{\mu}\boldsymbol{1}=\mathbb{P}^{*}_{\mu}r_{\mu}$.

Let $J^{*}:=\max_{\mu\in\Pi}J_{\mu}$ be the optimal average reward. From
standard MDP theory, there exists $h^{*}\in\mathbb{R}^{n}$, for which the pair
($J^{*}$,$h^{*}$) satisfies the following Bellman optimality equation:

$J^{*}\boldsymbol{1}+h^{*}=\max_{\mu\in\Pi}r_{\mu}+\mathbb{P}_{\mu}h^{*}.$ (3)

Let $\mu^{*}$ be the optimizing policy in Equation 3. Then, similar reasoning
shows that $J^{*}\boldsymbol{1}=\mathbb{P}^{*}_{\mu^{*}}r_{\mu^{*}}.$

The goal of dynamic programming and reinforcement learning is to determine
this optimal average reward $J^{*}$ and its corresponding optimal policy
$\mu^{*}$. Policy iteration is one of the most widely used dynamic programming
algorithms for this purpose. It consists of two steps: (i) evaluation of the
value function associated with a policy, and (ii) determining a greedy policy
with respect to this evaluation. There are primarily two challenges that arise
when applying such an algorithm: (i) high memory and time complexity when the
state space is too large, and (ii) the unknown transition probability kernel
that governs the dynamics of the MDP.

When the state space is too large, it may be computationally infeasible to
perform policy iteration exactly. Existing literature suggests that
approximate policy iteration in the context of discounted reward MDPs yields
good performance. However, such an algorithm has not been studied in the
context of average reward MDPs. In fact, the results obtained for the
discounted reward MDPs yield vacuous performance bounds for average reward
MDPs given the standard relationship between discounted reward and average
reward MDPs. We explore this further in Section 2.2.

###  2.2 Relationship to the Discounted Reward MDP

To provide some background, we first discuss the approximate policy iteration
algorithm in the context of discounted reward MDPs. Let $\alpha\in[0,1)$
denote the discount factor. The discounted reward associated with a
deterministic policy $\mu\in\Pi$ starting from some state $s\in\mathcal{S}$ is
denoted $J_{\mu}^{\alpha}(s)$ and is defined as:

$J_{\mu}^{\alpha}(s)=\mathbb{E}_{\mu}\left[\sum_{i=0}^{\infty}\alpha^{i}r(s_{i},\mu(s_{i}))\Big{|}s_{0}=s\right].$

The value function $J_{\mu}^{\alpha}\in\mathbb{R}^{n}$ is the unique fixed
point of the Bellman operator
$\mathsf{T}^{\alpha}_{\mu}:\mathbb{R}^{n}\to\mathbb{R}^{n}$ associated with
the policy $\mu$, which is defined as
$\mathsf{T}^{\alpha}_{\mu}J=r_{\mu}+\alpha\mathbb{P}_{\mu}J$. For each state
$s\in\mathcal{S}$, let $J_{*}^{\alpha}(s)$ denote the optimal discounted
reward, i.e., $J_{*}^{\alpha}(s)=\max_{\mu\in\Pi}J_{\mu}^{\alpha}(s).$
Similarly, $J_{*}^{\alpha}\in\mathbb{R}^{n}$ is the unique fixed point of the
optimality Bellman operator
$\mathsf{T}^{\alpha}:\mathbb{R}^{n}\to\mathbb{R}^{n}$, which is defined as
$\mathsf{T}^{\alpha}J=\max_{\mu\in\Pi}\left(r_{\mu}+\alpha\mathbb{P}_{\mu}J\right)$.
Algorithm 1 is Approximate Policy Iteration for the discounted reward MDP:

Algorithm 1 Approximate Policy Iteration: Discounted Reward

Require $J_{0}\in\mathbb{R}^{n}$

for $k=0,1,2,\ldots$ do

1\. Compute $\mu_{k+\\!1}\\!\\!\in\\!\Pi$ such that
$\|\mathsf{T}^{\alpha}J_{k}\\!-\\!\mathsf{T}^{\alpha}_{\mu_{k+1}}\\!J_{k}\|_{\infty}\\!\leq\\!\epsilon$
$\triangleright$ Approximate Policy Improvement

2\. Choose $J_{k+1}$ such that $\|J_{k+1}-J_{\mu_{k+1}}\|_{\infty}\leq\delta$
$\triangleright$ Approximate Policy Evaluation

where $J_{\mu_{k+1}}=\mathsf{T}^{\alpha}_{\mu_{k+1}}J_{\mu_{k+1}}$

end for

######  Theorem 2.1.

Let $\mu_{k}$ be the sequence of policies generated from the approximate
policy iteration algorithm (Algorithm 1). Then the performance error is
bounded as:

$\limsup_{k\to\infty}\|J_{\mu_{k}}-J_{*}^{\alpha}\|_{\infty}\leq\frac{\epsilon+2\alpha\delta}{(1-\alpha)^{2}}.$
(4)

###### Proof.

The proof of this theorem can be found in [Ber11] ∎

From literature [Ros14, Ber11], we know that the average reward $J_{\mu}$
associated with any policy $\mu$ is related to its discounted reward
$J^{\alpha}_{\mu}(s)$ counterpart as follows:

$J_{\mu}=\lim_{\alpha\to 1}(1-\alpha)J^{\alpha}_{\mu}(s).$

Note that the above relation is independent of the state $s\in\mathcal{S}$, as
the average reward does not depend on the initial state. Multiplying Equation
4 with $(1-\alpha)$, and letting $\alpha\to 1$, still yields an approximation
performance bound with $(1-\alpha)$ in the denominator. This term blows up to
infinity as $\alpha\to 1$. Note that this bound is known to be tight under
unichain Markov structure of the probability transition kernel [Ber11].
However, in practice it is observed that approximate policy iteration works
well in the average reward MDP case although these theoretical bounds are not
representative of this performance. To the best of our knowledge, we are
unaware of an average reward approximate policy iteration performance bound,
when the policies induce an irreducible Markov chain. We bridge this gap
between theory and practice by providing a theoretical analysis of approximate
policy iteration in the average reward MDP setting, with non trivial
performance bounds.

##  3 Approximate Policy Iteration for Average Reward

A crucial component of the proof of convergence of approximate policy
iteration in the context of discounted reward MDPs is the contraction due to
the discount factor $\alpha$ which is absent in the average reward setting
(since $\alpha=1$). To get some source of contraction, we have to make some
assumptions on the MDP.

######  Assumption 3.1.

We make the following assumptions:

  1. (a)

Every deterministic policy $\mu\in\Pi$ induces an irreducible Markov Chain
$\mathbb{P}_{\mu}$.

  2. (b)

For all policies, the diagonal elements of the probability transition matrix
are positive, i.e., the Markov chain stays in the same state with non-zero
probability.

Assumption (a) need not be satisfied by all MDPs. However, in order to satisfy
this assumption, we consider a modified MDP where at every time step with
probability $\varepsilon,$ an action is chosen from the set of all possible
actions with equal probability. Simultaneously, with probability
$1-\varepsilon$, we choose an action dictated by some policy. The problem then
is to choose this policy optimally. For most MDPs of interest, this small
modification will satisfy our assumption with a small $O(\varepsilon)$ loss in
performance. It is straightforward to show the $O(\varepsilon)$ loss, but we
include the proof in the appendix for completeness. Assumption (b) is without
loss of generality in the following sense: there exists a simple
transformation which essentially leaves the MDP unchanged but ensures that
this assumption is satisfied. This transformation known as the aperiodicity
transformation or Schweitzer transformation was introduced in [Sch71]. For
more details, the reader is referred to the appendix. In the remainder of this
paper, we assume that all MDPs are transformed accordingly to ensure the
assumptions are satisfied. One consequence of Assumption (b) is the following
lemma which will be useful to us later.

######  Lemma 3.2.

There exists a $\gamma>0$ such that, for any policy $\mu\in\Pi$,

$\min_{i\in\mathcal{S}}\pi_{\mu}(i)\geq\gamma,$

where $\pi_{\mu}$ is stationary distribution over states associated with the
policy $\mu$.

###### Proof.

This lemma has been proved in a more general sense in the context of
deterministic policies in [VdW80]. Since the aperiodicity transformation
ensures a non-zero probability of staying in the same state, the expected
return times are bounded and the lemma holds true for randomized policies as
well. ∎

Prior to presenting the algorithm, consider the following definitions. The
average-reward Bellman operator
$\mathsf{T}_{\mu}:\mathbb{R}^{n}\to\mathbb{R}^{n}$ corresponding to a policy
$\mu$ is defined as $\mathsf{T}_{\mu}h={r}_{\mu}+{\mathbb{P}}_{\mu}h.$ The
average-reward optimal Bellman operator
$\mathsf{T}:\mathbb{R}^{n}\to\mathbb{R}^{n}$ is defined as
$\mathsf{T}h=\max_{\mu\in\Pi}{r}_{\mu}+{\mathbb{P}}_{\mu}h.$ The value
function $h_{\mu}$ associated with a policy $\mu$ satisfies the Bellman
Equation 2 with single step reward ${r}_{\mu}$ and the transition kernel
${\mathbb{P}}_{\mu}$. Note that $h_{\mu}$ is unique up to an additive
constant.

Solving for $\left({J}_{\mu},{h}_{\mu}\right)$ using Equation 2 involves
setting the value function for some fixed state $x^{*}$ as $0$ (since this
reduces the system from being underdetermined to one with a unique solution).
Further, the value function $h_{\mu}$ can be alternatively expressed as the
$\lim_{m\to\infty}\mathsf{T}^{m}_{\mu}h_{0}$ for any $h_{0}\in\mathbb{R}^{n}$
as is the case with discounted reward MDPs. However, unlike the discounted
reward Bellman Equation, there is no discount factor $\alpha<1$ preventing the
value function from exploding to infinity. Hence, we consider value function
computed using the relative Bellman operator $\widetilde{\mathsf{T}}_{\mu}$
defined as

$\widetilde{\mathsf{T}}_{\mu}h={r}_{\mu}+{\mathbb{P}}_{\mu}h-{r}_{\mu}(x^{*})\boldsymbol{1}-\left({\mathbb{P}}_{\mu}h\right)(x^{*})\boldsymbol{1}.$

We now state the algorithm for Approximate Policy Iteration for Average Reward
MDPs.

###  3.1 Approximate Policy Iteration Algorithm for Average Reward MDPs

Algorithm 2 Approximate Policy Iteration: Average Reward

1:Require $h_{0}\in\mathbb{R}^{n}$

2:for $k=0,1,2,\ldots$ do

3: 1\. Compute $\mu_{k+1}\\!\in\\!\Pi$ such that
$\|\mathsf{T}h_{k}\\!-\\!\mathsf{T}_{\mu_{k+1}}h_{k}\|_{\infty}\leq\epsilon$
$\triangleright$ Approx. Policy Improvement

4: 2\. Compute $h_{k+1}$ such that
$\|h_{k+1}-h_{\mu_{k+1}}\|_{\infty}\leq\delta$ $\triangleright$ Approx. Policy
Evaluation

5: where
$h_{\mu_{k+1}}=\lim_{m\to\infty}\widetilde{\mathsf{T}}^{m}_{\mu_{k+1}}h_{k}$

6:end for

###  3.2 Performance bounds for Average Reward Approximate Policy Iteration

We are now ready to present the main result of this work.

######  Theorem 3.3.

Let ${J}^{*}$ be the optimal average reward of an MDP that satisfies 3.1. The
sequence of policies $\mu_{k}$ generated by Algorithm 2 and their associated
average rewards ${J}_{\mu_{k}}$ satisfy the following bound:

$\displaystyle\Big{(}{J}^{*}-$
$\displaystyle{J}_{\mu_{k+1}}\Big{)}\leq\underbrace{\frac{\left(1-\left(1-\gamma\right)^{k}\right)}{\gamma}\left(\epsilon\left(\gamma+1\right)+2\delta\right)}_{\text{approximation
error}}+\underbrace{\left(1-\gamma\right)^{k}\left({J}^{*}-{\min_{i}\left(\mathsf{T}h_{0}-h_{0}\right)(i)+\epsilon}\right)}_{\text{initial
condition error}}.$

Interpretation of the Bound: Since $0<\gamma<1$, as $k\to\infty$, the error
due to initial condition $h_{0}$ drops to zero. The approximation error
consists of two components, $\epsilon$ and $\delta$. Here, $\epsilon$
represents the approximation error due to a suboptimal policy and $\delta$
represents the approximation error associated with evaluating the value
function corresponding to a policy. The limiting behavior of the average
reward associated with the policies obtained as a consequence of the algorithm
is captured in the following corollary.

######  Corollary 3.4.

The asymptotic performance of the policies obtained from Algorithm 2
satisfies:

$\limsup_{k\to\infty}{\left({J}^{*}-{J}_{\mu_{k}}\right)}\leq\frac{(1+\gamma)\epsilon+2\delta}{\gamma}.$
(5)

Note that the asymptotic bound in Equation 5 is in a very similar form as the
asymptotic performance bound for the discounted reward MDP in Equation 4 where
$\gamma$ plays the role of $(1-\alpha)^{2}$. However, when $\epsilon$ and
$\delta$ got to zero, this bound also goes to zero which is not the case if we
try to approximate average-reward problems by using the results for
discounted-reward problems in the limit where the horizon goes to infinity.

##  4 Application to Reinforcement Learning

Approximate policy iteration is closely related to RL. In general, approximate
policy improvement and approximate policy evaluation in Algorithm 2 are
executed through approximations to policy improvement (such as greedy update,
mirror descent, softmax) and TD learning for value function approximation.
First, we present a generic framework to analyze policy-based RL algorithms by
building upon the theory presented in the last section. For this purpose, we
define the state-action relative value function $Q$ (instead of the relative
state value function $h$ as before) to evaluate a policy. Let
$\mathsf{T}^{\mathsf{Q}}_{\mu}Q$ denote the Bellman operator with respect to
$Q$ and policy $\mu$ where
$(\mathsf{T}^{\mathsf{Q}}_{\mu}Q)(s,a)=r(s,a)+\left(\mathbb{Q}_{\mu}Q\right)(s,a),$
where
$\mathbb{Q}_{\mu}(s^{\prime},a^{\prime}|s,a)=\mu(a^{\prime}|s^{\prime})\mathbb{P}(s^{\prime}|s,a).$
The relative state action value function corresponding to policy $\mu$ is
represented by $Q_{\mu}$ and is the solution to the following Bellman
equation:
$J_{\mu}+Q_{\mu}(s,a)=r(s,a)+\sum_{s^{\prime}\in\mathcal{S},a^{\prime}\in\mathcal{A}}\mathbb{Q}_{\mu}(s^{\prime},a^{\prime}|s,a)Q_{\mu}(s^{\prime},a^{\prime})$,
for all state action pairs $(s,a)\in(\mathcal{S},\mathcal{A})$. We present a
generic policy-based algorithm for average-reward problem below.

Algorithm 3 Generic Policy Based Algorithm: $Q$-function Average Reward

Require $Q_{0}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$

for $k=0,1,2,\ldots,T$ do

1\. Determine $\mu_{k+1}\\!\in\\!\Pi$ as a function of $Q_{k}$ using a
possibly random policy improvement step

2\. Compute $Q_{k+1}$ as an approximation to $Q_{\mu_{k+1}}$ using (state,
action, reward) samples from a trajectory generated by policy $\mu_{k+1}$

end for

Note that the error in Steps 1 (policy improvement) and 2 (policy evaluation)
of the above algorithm could be random. Thus, the analysis for Theorem 3.3 has
to be adapted to Algorithm 3. The resulting expected deviation from optimality
is characterized in the lemma below.

######  Lemma 4.1.

Let $\mu_{k}$ and $Q_{k}$ be the sequence of policies and relative state-
action value function iterates generated by Algorithm 3. For all $k\in
0,\ldots,T$, we have:

$\displaystyle\\!\\!\Big{(}{J}^{*}-\left(\min_{(s,a)}\left(\mathsf{T}^{\mathsf{Q}}Q_{k}-Q_{k}\right)(s,a)\right)\\!\Big{)}$
$\displaystyle\leq\left(1-\gamma\right)\left({J}^{*}-\left(\min_{(s,a)}\left(\mathsf{T}^{\mathsf{Q}}Q_{k-1}-Q_{k-1}\right)(s,a)\right)\right)$
$\displaystyle+\left\|\mathsf{T}^{\mathsf{Q}}Q_{k-\\!1}\\!-\\!\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}Q_{k-\\!1}\\!\right\|_{\infty}\\!\\!\\!+\\!2\\!\left\|Q_{k}\\!-\\!Q_{\mu_{k}}\\!\right\|_{\infty}\\!,$

where

$\gamma=\min_{\begin{subarray}{c}\mu\in{\mu_{1},\mu_{2},\ldots,\mu_{T}}\\\
(s,a)\in\mathcal{S}\times\mathcal{A}\end{subarray}}\mathbb{Q}_{\mu}^{*}(s,a)>0,$

and $\mathbb{Q}_{\mu}^{*}$ is a matrix with identical rows corresponding to
the invariant distribution of $\mathbb{Q}_{\mu}$.

Iteratively applying Lemma 4.1 yields the following proposition for a generic
policy-based algorithm.

######  Proposition 4.2.

For any $T>0$, the iterates of Algorithm 3 satisfy

$\displaystyle\mathbb{E}\big{[}{J}^{*}\\!-\\!{J}_{\mu_{T+1}}\big{]}\\!$
$\displaystyle\leq\\!\underbrace{\left(1\\!-\\!\gamma\right)^{T}\mathbb{E}\\!\left[{J}^{*}\\!-\\!\min_{i}\left(\mathsf{T}^{\mathsf{Q}}Q_{0}\\!-\\!Q_{0}\right)(i)\right]}_{\text{Initial
condition
error}}\\!+\\!\underbrace{2\sum_{\ell=0}^{T-1}\left(1\\!-\\!\gamma\right)^{\ell}\mathbb{E}\\!\left[\left\|Q_{T-\ell}\\!-\\!Q_{\mu_{T-\ell}}\right\|_{\infty}\right]}_{\text{Policy
evaluation error}}$
$\displaystyle\\!+\\!\underbrace{\\!\sum_{\ell=1}^{T-1}\\!\left(1-\gamma\right)^{\ell-1}\mathbb{E}\\!\left[\left\|\mathsf{T}^{\mathsf{Q}}_{\mu_{T+1-\ell}}\\!Q_{T-\ell}\\!-\\!\mathsf{T}^{\mathsf{Q}}Q_{T-\ell}\right\|_{\infty}\right]+\mathbb{E}\left[{\left\|\mathsf{T}^{\mathsf{Q}}_{\mu_{T+1}}Q_{T}-\mathsf{T}^{\mathsf{Q}}Q_{T}\right\|_{\infty}}\right]}_{\text{Policy
improvement error}}.$

We now illustrate the applicability of the above result to specific RL
algorithms. More specifically, we characterize finite time performance bounds
when state-action relative value functions are learnt through TD-Learning
[ZZM21], while several different update rules are employed for policy
improvement.

###  4.1 Performance bounds for RL algorithms

For every iteration of Algorithm 3, it is necessary to observe trajectories of
length $\tau$ in order to learn the state action value function associated
with any policy. Using linear function approximations for value functions, the
error in policy evaluation at iteration $k$ in Algorithm 3 can be expressed in
the following form:

$\|Q_{k}-Q_{\mu_{k}}\|_{\infty}\leq\|\Phi(\theta_{k}-\theta^{*}_{\mu_{k}})\|_{\infty}+\|Q_{\mu_{k}}-\Phi\theta^{*}_{\mu_{k}}\|_{\infty},$
(6)

where $\Phi\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\times d}$ corresponds to
the feature vector matrix and $\theta\in\mathbb{R}^{d}$ is the parameter
vector. Further, $\theta_{k}$ is the parameter vector obtained as a result of
the TD learning algorithm. The projection of $Q_{\mu_{k}}$ onto the span of
$\Phi$ is given by $\Phi\theta^{*}_{\mu_{k}}$. The last term in Equation 6
corresponds to the function approximation error which depends on the span of
the feature matrix $\Phi$. We denote this error term by $\delta_{0,k}.$ The
error due to TD learning (first term in Equation 6) is denoted by
$\delta_{\text{TD},k}$. Assuming
$\max_{(s,a)\in\mathcal{S}\times\mathcal{A}}\|\phi(s,a)\|_{2}\leq 1$, and
$\|\theta_{\mu_{k}}^{*}\|_{2}$ is bounded uniformly in $k$, [ZZM21] shows that
there exists $C>0$ such that the length of the sample trajectory $\tau$ and
$\delta_{\text{TD},k}$ are related as follows:

$\mathbb{E}\left[\delta_{\text{TD},k}\right]=\frac{C}{\sqrt{\tau}}.$ (7)

Let
$c_{0}=\left(J^{*}-\min_{i\in\mathcal{S}}\left(\mathsf{T}^{\mathsf{Q}}Q_{0}-Q_{0}\right)(i)\right)$
be the error due to initial condition and
$\overline{\delta}_{0}=\max_{t}\delta_{0,t}$ be the maximum function
approximation error across all iterations. Then we obtain the following
performance bounds when TD learning is used for policy evaluation.

######  Corollary 4.3.

(Greedy policy update) Let
$\tilde{a}(s)=\operatorname*{argmax}_{a\in\mathcal{A}}Q_{k}(s,a^{\prime}).$
Let $\beta>0$ be such that the sequence of policies in Algorithm 3
corresponding to all state action pairs $(s,a)$ are obtained using the
following algorithm, which we call the greedy policy update.

$\displaystyle\mu_{k+1}(a|s)=\begin{cases}\frac{1}{\beta|\mathcal{A}|},&\text{if
}a\neq\tilde{a}(s)\\\ \frac{1}{\beta|\mathcal{A}|}+1-\frac{1}{\beta},&\text{if
}a=\tilde{a}(s),\end{cases}$ (8)

Let $\eta=\max_{\begin{subarray}{c}s\in\mathcal{S},a\in\mathcal{A}\\\ k\in
1\ldots T\end{subarray}}|Q_{k}(s,a)|.$ Using TD Learning with linear value
function approximation for policy evaluation, we get the following finite time
performance bound:

$\displaystyle\mathbb{E}\left[J^{*}-J_{\mu_{T+1}}\right]$
$\displaystyle\leq(1-\gamma)^{T}c_{0}+\left(\frac{1+\gamma}{\gamma}\right)\frac{2\eta}{\beta}+\frac{2}{\gamma}\left(\overline{\delta}_{0}+\frac{C}{\sqrt{\tau}}\right).$
(9)

######  Corollary 4.4.

(Softmax policy update) Let $\beta>0$ be such that the sequences of policies
in Algorithm 3 corresponding to all state action pairs $(s,a)$ are obtained
using the following algorithm, which we call the softmax policy update.

$\mu_{k+1}(a|s)=\frac{\exp\left(\beta
Q_{k}(s,a)\right)}{\sum_{a^{\prime}\in\mathcal{A}}\exp\left(\beta
Q_{k}(s,a^{\prime})\right)}.$ (10)

Using TD Learning with linear value function approximation for policy
evaluation, we get the following finite time performance bound:

$\displaystyle\mathbb{E}\left[J^{*}-J_{\mu_{T+1}}\right]$
$\displaystyle\leq(1-\gamma)^{T}c_{0}+\left(\frac{1+\gamma}{\gamma}\right)\frac{\log\left(|\mathcal{A}|\right)}{\beta}+\frac{2}{\gamma}\left(\overline{\delta}_{0}+\frac{C}{\sqrt{\tau}}\right).$
(11)

######  Corollary 4.5.

(Mirror descent update) Let $\beta>0$ be such that the sequences of policies
in Algorithm 3 corresponding to all state action pairs $(s,a)$ are obtained
using the following algorithm, which we call the mirror descent policy update.

$\mu_{k+1}(a|s)\propto\mu_{k}(a|s)\exp\\{\beta Q_{k}(s,a)\\}.$ (12)

Let $\omega=\min_{\begin{subarray}{c}k\in 1\ldots T\\\
s\in\mathcal{S}\end{subarray}}\mu_{k}(a^{*}(s)|s)$ where $a^{*}(s)$ is the
optimal action at state $s.$ Using TD Learning with linear value function
approximation for policy evaluation, we get the following finite time
performance bound:

$\displaystyle\mathbb{E}\left[J^{*}-J_{\mu_{T+1}}\right]$
$\displaystyle\leq(1-\gamma)^{T}c_{0}+\left(\frac{1+\gamma}{\gamma\beta}\right)\log\left(\frac{1}{\omega}\right)+\frac{2}{\gamma}\left(\overline{\delta}_{0}+\frac{C}{\sqrt{\tau}}\right).$
(13)

######  Remark 4.6.

The following remarks are in order:

  * •

In each of the above performance bounds, there is an inevitable constant error
$(\overline{\delta}_{0})$ due to function approximation. If the value function
lies in the class of functions chosen, then this error will be zero.

  * •

The error due to policy update (characterized by $\beta$) can be made
arbitrarily small by choosing $\beta$ large. However, choosing a large $\beta$
may increase $C$ due to the fact that $C$ is a function of the mixing time of
each policy, which is affected by the choice of $\beta.$ However, $C$ cannot
be arbitrarily large due to Assumption (a).

  * •

The error due to the initial condition decays exponentially fast but the rate
of decay can be slow because $\gamma$ can be very small. In this regard, it is
interesting to compare our work with the results in [AYBB+19, LYAYS21]. We do
so in the next subsection.

###  4.2 Comparison with [AYBB+19, LYAYS21]

Our model for approximate policy iteration is intended to be a general
framework to study policy-based RL algorithms. A specific class of such
algorithms has been studied in [AYBB+19, LYAYS21], where regret bounds are
presented for a mirror descent like algorithm referred to as Politex. Although
our model is intended for offline algorithms, it is possible to adapt the
techniques in [AYBB+19, LYAYS21] to obtain regret bounds for our model as
well.

Let $r(s_{t},a_{t})$ be the reward obtained at time $t.$ Let $K$ be the total
number of time units for which Algorithm 3 is executed. Hence $K=T\tau$, where
$\tau$ is the length of the sample trajectory for every iteration of policy
evaluation. The regret, defined as
$R(K)=\sum_{t=1}^{K}\left(J^{*}-r(s_{t},a_{t})\right)$ can be further
decomposed as:

$R(K)=\sum_{t=1}^{K}\left(J^{*}-J_{\mu_{t}}\right)+\left(J_{\mu_{t}}-r(s_{t},a_{t})\right).$
(14)

The first term i.e., $\sum_{t=1}^{K}\left(J^{*}-J_{\mu_{t}}\right)$ is
referred to as the pseudo regret $R_{\text{PS}}(K)$. The second term is
essentially bounding the average value from its estimate and can be bounded
using a martingale analysis identical to [AYBB+19, LYAYS21]. Here, we focus on
obtaining an upper bound on the pseudo regret with mirror descent update and
TD learning. The pseudo regret can be further decomposed as:

$R_{\text{PS}}(K)=\tau\sum_{t=1}^{T}\left(J^{*}-J_{\mu_{t}}\right).$

For the mirror descent policy update in Corollary 4.5, we get the following
expected regret bound

$R_{\text{PS}}(K)\leq\tau\sum_{t=1}^{T}(1-\gamma)^{T}c_{0}+\frac{1+\gamma}{\gamma\beta}\log\left(\frac{1}{\omega}\right)+\frac{2}{\gamma}\left(\overline{\delta}_{0}+\frac{c_{3}}{\sqrt{\tau}}\right).$
(15)

Let $\beta=\sqrt{\tau}$, then the above regret can be expressed as:

$R_{\text{PS}}(K)\leq\frac{1}{\gamma}\left({\tau
c_{0}}+{2K\overline{\delta}_{0}}+\frac{Kc_{5}}{\sqrt{\tau}}\right).$

Optimizing for the regret yields $\tau=O(K^{\frac{2}{3}})$ and the following
pseudo regret upper bound,

$R_{\text{PS}}(K)\leq\frac{1}{\gamma}\left(2K\overline{\delta}_{0}+c_{6}K^{\frac{2}{3}}\right).$
(16)

We now compare our regret bounds to the ones in [AYBB+19, LYAYS21]. Since all
of the bounds will have an inevitable error $(\overline{\delta}_{0})$ due to
function approximation, the comparison is with respect to the other terms in
the regret bound.

  * •

We get a better order-wise bound on the regret compare to [AYBB+19] which
obtains a bound of $O(K^{3/4}).$ However, they have better constants which are
in terms of mixing-time coefficients rather than in terms of $\gamma.$

  * •

[LYAYS21] gets a better regret bound $(O(\sqrt{K}))$ than us.

The results in [AYBB+19, LYAYS21] use Monte Carlo policy evaluation, which
allows for a closed-form expression for the value function estimate. The
structure of the closed-form expressions allows them to exploit the fact that
the policy varies slowly from one iteration to the next (which is specific to
the mirror descent policy update) and hence $\gamma$ does not appear in their
analysis. However, the Monte Carlo policy evaluation algorithms use matrix
inversion which is often too expensive to implement in practice unlike the TD
learning algorithm in our analysis which is widely used. Nevertheless, the
ideas in [AYBB+19, LYAYS21] provide a motivation to investigate whether one
can extend their analysis to more general policy evaluation and policy
improvement algorithms. This is an interesting topic for future research.

##  5 Conclusions

We present a general framework for analyzing policy-based reinforcement
learning algorithms for average-reward MDPs. Our main contribution is to
obtain performance bounds without using the natural source of contraction
available in discounted reward formulations. We apply our general framework to
several well-known RL algorithms to obtain finite-time error bounds on the
average reward. We conclude with a comparative regret analysis and an outline
of possible future work.

## References

  * [ABB01] Jinane Abounadi, Dimitri Bertsekas, and Vivek S Borkar.  Learning algorithms for markov decision processes with average cost.  SIAM Journal on Control and Optimization, 40(3):681–698, 2001.
  * [AKLM21] Alekh Agarwal, Sham M Kakade, Jason D Lee, and Gaurav Mahajan.  On the theory of policy gradient methods: Optimality, approximation, and distribution shift.  The Journal of Machine Learning Research, 22(1):4431–4506, 2021\.
  * [AYBB+19] Yasin Abbasi-Yadkori, Peter Bartlett, Kush Bhatia, Nevena Lazic, Csaba Szepesvari, and Gellért Weisz.  Politex: Regret bounds for policy iteration using expert prediction.  In International Conference on Machine Learning, pages 3692–3702. PMLR, 2019.
  * [Ber11] Dimitri P Bertsekas.  Dynamic programming and optimal control 3rd edition, volume ii.  Belmont, MA: Athena Scientific, 2011.
  * [Ber12] Dimitri Bertsekas.  Dynamic programming and optimal control: Volume I, volume 1.  Athena scientific, 2012.
  * [BSGL09] Shalabh Bhatnagar, Richard S Sutton, Mohammad Ghavamzadeh, and Mark Lee.  Natural actor–critic algorithms.  Automatica, 45(11):2471–2482, 2009.
  * [BT96] Dimitri Bertsekas and John N Tsitsiklis.  Neuro-dynamic programming.  Athena Scientific, 1996.
  * [CCM22] Zaiwei Chen, John Paul Clarke, and Siva Theja Maguluri.  Target network and truncation overcome the deadly triad in $q$-learning.  arXiv preprint arXiv:2203.02628, 2022.
  * [CM22] Zaiwei Chen and Siva Theja Maguluri.  Sample complexity of policy-based methods under off-policy sampling and linear function approximation.  In International Conference on Artificial Intelligence and Statistics, pages 11195–11214. PMLR, 2022.
  * [Gos04] Abhijit Gosavi.  Reinforcement learning for long-run average cost.  European journal of operational research, 155(3):654–674, 2004\.
  * [JJS93] Tommi Jaakkola, Michael Jordan, and Satinder Singh.  Convergence of stochastic iterative dynamic programming algorithms.  Advances in neural information processing systems, 6, 1993.
  * [KT99] Vijay Konda and John Tsitsiklis.  Actor-critic algorithms.  Advances in neural information processing systems, 12, 1999.
  * [LYAYS21] Nevena Lazic, Dong Yin, Yasin Abbasi-Yadkori, and Csaba Szepesvari.  Improved regret bound and experience replay in regularized policy iteration.  In International Conference on Machine Learning, pages 6032–6042. PMLR, 2021.
  * [Mah96] Sridhar Mahadevan.  Average reward reinforcement learning: Foundations, algorithms, and empirical results.  Recent advances in reinforcement Learning, pages 159–195, 1996\.
  * [MMT00] Peter Marbach, Oliver Mihatsch, and John N Tsitsiklis.  Call admission control and routing in integrated services networks using neuro-dynamic programming.  IEEE Journal on selected areas in communications, 18(2):197–208, 2000.
  * [MS08] Rémi Munos and Csaba Szepesvári.  Finite-time bounds for fitted value iteration.  Journal of Machine Learning Research, 9(5), 2008.
  * [MXSS20] Jincheng Mei, Chenjun Xiao, Csaba Szepesvari, and Dale Schuurmans.  On the global convergence rates of softmax policy gradient methods.  In International Conference on Machine Learning, pages 6820–6829. PMLR, 2020.
  * [Put14] Martin L Puterman.  Markov decision processes: discrete stochastic dynamic programming.  John Wiley & Sons, 2014.
  * [Ros14] Sheldon M Ross.  Introduction to stochastic dynamic programming.  Academic press, 2014.
  * [SB18] Richard S Sutton and Andrew G Barto.  Reinforcement learning: An introduction.  MIT press, 2018.
  * [Sch71] Paul J Schweitzer.  Iterative solution of the functional equations of undiscounted markov renewal programming.  Journal of Mathematical Analysis and Applications, 34(3):495–501, 1971.
  * [Sin94] Satinder P Singh.  Reinforcement learning algorithms for average-payoff markovian decision processes.  In AAAI, volume 94, pages 700–705, 1994.
  * [Tsi94] John N Tsitsiklis.  Asynchronous stochastic approximation and q-learning.  Machine learning, 16:185–202, 1994.
  * [TVR99] John N Tsitsiklis and Benjamin Van Roy.  Average cost temporal-difference learning.  Automatica, 35(11):1799–1808, 1999.
  * [VdW80] J Van der Wal.  Successive approximations for average reward markov games.  International Journal of Game Theory, 9(1):13–24, 1980.
  * [WD92] Christopher JCH Watkins and Peter Dayan.  Q-learning.  Machine learning, 8:279–292, 1992.
  * [WLLS21] Anna Winnicki, Joseph Lubars, Michael Livesay, and R Srikant.  The role of lookahead and approximate policy evaluation in reinforcement learning with linear value function approximation.  arXiv preprint arXiv:2109.13419, 2021.
  * [WNS21] Yi Wan, Abhishek Naik, and Richard S Sutton.  Learning and planning in average-reward markov decision processes.  In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 10653–10662. PMLR, 18–24 Jul 2021.
  * [YB09] Huizhen Yu and Dimitri P Bertsekas.  Convergence results for some temporal difference methods based on least squares.  IEEE Transactions on Automatic Control, 54(7):1515–1531, 2009.
  * [ZWSW21] Shangtong Zhang, Yi Wan, Richard S Sutton, and Shimon Whiteson.  Average-reward off-policy policy evaluation with function approximation.  In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 12578–12588. PMLR, 18–24 Jul 2021.
  * [ZZM21] Sheng Zhang, Zhe Zhang, and Siva Theja Maguluri.  Finite sample analysis of average-reward td learning and $q$-learning.  Advances in Neural Information Processing Systems, 34:1230–1242, 2021.

##  6 Appendix

###  6.1 Discussion on Assumption 3.1

####  6.1.1 Assumption 3.1(a)

In order to ensure every policy induces an irreducible Markov chain, we modify
the MDP where at every time step with probability $\epsilon$, an action is
chosen from the set of all possible actions with equal probability.
Simultaneously, with probability $1-\epsilon$, we choose an action dictated by
some policy. Let the transition kernel of the MDP associated with policy $\mu$
be denoted as $\mathbb{P}_{\mu}$. We denote the modified kernel by
$\widehat{\mathbb{P}}_{\mu}$, where the transition probability from state $i$
to $j$ is given by:

$\widehat{\mathbb{P}}_{\mu}(j|i)=(1-\epsilon)\mathbb{P}_{\mu}(j|i)+\epsilon\left(\frac{1}{|\mathcal{A}|}\sum_{a\in\mathcal{A}}\mathbb{P}(j|i,a)\right)$

Let
$\mathbb{P}_{\rho}(j|i)=\frac{1}{|\mathcal{A}|}\sum_{a\in\mathcal{A}}\mathbb{P}(j|i,a),$
where $\rho$ represents randomized policy, that is
$\rho(a|i)=\frac{1}{|\mathcal{A}|.}$ Let $(J_{\mu},V_{\mu})$ be the average
reward and state value function vector associated with the policy $\mu.$ Then
they the satisfy the following Bellman Equation:

$J_{\mu}+V_{\mu}=r_{\mu}+\mathbb{P}_{\mu}V_{\mu},$

where $r_{\mu}(i)=\sum_{a\in\mathcal{A}}\mu(a|i)r(i,a).$ Similarly
$(\widehat{J}_{\mu},\widehat{V}_{\mu})$ be the average reward and state value
function vector that satisfy the following Bellman Equation,

$\widehat{J}_{\mu}+\widehat{V}_{\mu}=\widehat{r}_{\mu}+\widehat{\mathbb{P}}_{\mu}\widehat{V}_{\mu}$

where $\widehat{r}_{\mu}=(1-\epsilon)r_{\mu}+\epsilon r_{\rho}$. Since
$\widehat{\mathbb{P}}_{\mu}=(1-\epsilon)\mathbb{P}_{\mu}+\epsilon\mathbb{P}_{\rho},$
the above equation can be rewritten as:

$\widehat{J}_{\mu}=\left(1-\epsilon\right)\left(r_{\mu}+\mathbb{P}_{\mu}\widehat{V}_{\mu}-\widehat{V}_{\mu}\right)+\epsilon\left(r_{\rho}+\mathbb{P}_{\rho}\widehat{V}_{\mu}-\widehat{V}_{\mu}\right)$

Multiplying the above equation by the vector $\mathbb{P}^{*}_{\mu}$, which is
the invariant distribution over the state space due to policy $\mu$, we
obtain,

$\widehat{J}_{\mu}=\left(1-\epsilon\right)\left(\mathbb{P}^{*}_{\mu}r_{\mu}\right)+\epsilon\mathbb{P}^{*}_{\mu}\left(r_{\rho}+\mathbb{P}_{\rho}\widehat{V}_{\mu}-\widehat{V}_{\mu}\right)$

since $\mathbb{P}^{*}_{\mu}\mathbb{P}_{\mu}=\mathbb{P}^{*}_{\mu}$. We also
know that $J_{\mu}=\mathbb{P}^{*}_{\mu}r_{\mu}.$. Hence we obtain,

$\widehat{J}_{\mu}=\left(1-\epsilon\right)J_{\mu}+\epsilon\mathbb{P}^{*}_{\mu}\left(r_{\rho}+\mathbb{P}_{\rho}\widehat{V}_{\mu}-\widehat{V}_{\mu}\right)$

Therefor we obtain the following result,

$J_{\mu}-\widehat{J}_{\mu}=\epsilon\left(J_{\mu}-\mathbb{P}^{*}_{\mu}\left(r_{\rho}+\mathbb{P}_{\rho}\widehat{V}_{\mu}-\widehat{V}_{\mu}\right)\right)$

Since the rewards are bounded, so are $J_{\mu},r_{\rho}$ and
$\mathbb{P}_{\rho}\widehat{V}_{\mu}-\widehat{V}_{\mu}$ for all $\mu$. Hence we
obtain,

$J_{\mu}-\widehat{J}_{\mu}=O(\epsilon)$

The difference in the average reward associated with the original MDP and the
modified MDP vary by $O(\epsilon).$ Let the optimal policy corresponding to
original MDP be $\mu^{*}$ and the optimal policy corresponding to modified MDP
be $\widehat{\mu}^{*}$. Then,

$J_{\mu^{*}}-\widehat{J}_{\widehat{\mu}^{*}}=J_{\mu^{*}}-\widehat{J}_{\mu^{*}}+\widehat{J}_{\mu^{*}}-\widehat{J}_{\widehat{\mu}^{*}}$

Since $\widehat{\mu}^{*}$ is the optimizing policy for the modified MDP, we
have $\widehat{J}_{\mu^{*}}-\widehat{J}_{\widehat{\mu}^{*}}\leq 0$. Hence, we
obtain,

$J_{\mu^{*}}-\widehat{J}_{\widehat{\mu}^{*}}\leq
J_{\mu^{*}}-\widehat{J}_{\mu^{*}}=O(\epsilon).$

Similarly,

$J_{\mu^{*}}-\widehat{J}_{\widehat{\mu}^{*}}=J_{\mu^{*}}-J_{\widehat{\mu}^{*}}+J_{\widehat{\mu}^{*}}-\widehat{J}_{\widehat{\mu}^{*}}$

Since $\mu^{*}$ is the optimizing policy for the original MDP, we have
$J_{\mu^{*}}-J_{\widehat{\mu}^{*}}\geq 0$. Hence we obtain,

$J_{\mu^{*}}-\widehat{J}_{\widehat{\mu}^{*}}\geq
J_{\widehat{\mu}^{*}}-\widehat{J}_{\widehat{\mu}^{*}}=O(\epsilon).$

Thus the optimal average reward of the original MDP and modified MDP differ by
$O(\epsilon).$ That is,

$|J_{\mu^{*}}-\widehat{J}_{\widehat{\mu}^{*}}|\leq O(\epsilon)$

####  6.1.2 Assumption 3.1 (b)

To ensure Assumption 3.1 (b) is satisfied, an aperiodicity transformation can
be implemented. Under this transformation, the transition probabilities of the
original MDP are modified such that the probability of staying in any state
under any policy is non-zero. In order to compensate for the change in
transition kernel, the single step rewards are analogously modified such that
the Bellman equation corresponding to the original and transformed dynamics
are scaled versions of one another. This thus ensures that the optimality of a
policy remains the same irrespective of this transformation, along with
yielding quantifiable convergence properties. Mathematically, this
transformation is described below.

######  Definition 6.1 (Aperiodicity Transformation).

Let $\kappa\in\left(0,1\right)$. For every policy $\mu\in\Pi$ and for all
states $i,j\in\mathcal{S}$, consider the following transformation:

$\displaystyle\widehat{\mathbb{P}}_{\mu}\left(i|i\right)$
$\displaystyle=\kappa+(1-\kappa)\mathbb{P}_{\mu}\left(i|i\right)$ (17)
$\displaystyle\widehat{\mathbb{P}}_{\mu}\left(j|i\right)$
$\displaystyle=(1-\kappa)\mathbb{P}_{\mu}\left(j|i\right),\qquad j\neq i$ (18)
$\displaystyle\widehat{r}(i,\mu(i))$ $\displaystyle=(1-\kappa)r(i,\mu(i))$
(19)

######  Theorem 6.2.

Given the transformation in Equation 17-Equation 19, for every $\mu\in\Pi$,
let $(J_{\mu},h_{\mu})$ and $(\widehat{J}_{\mu},\widehat{h}_{\mu})$ be the
solution to the Bellman Equation (Equation 2) corresponding to the original
MDP $(\mathbb{P}_{\mu},r_{\mu})$ and the transformed MDP
$(\widehat{\mathbb{P}}_{\mu},\widehat{r}_{\mu})$. Then,

$\left(\widehat{J}_{\mu},\widehat{h}_{\mu}\right)=\left((1-\kappa)J_{\mu},h_{\mu}\right)$

###### Proof.

The proof of this theorem can be found in [Sch71]. ∎

######  Remark 6.3.

Due to this bijective relationship between the original and the transformed
problem, it suffices to solve the transformed problem. Given that the
trajectory used for algorithms such as TD Learning corresponds to the original
system, such a transformation necessitates a mild change in how samples from a
given policy are utilized in TD learning. More specifically, for each (state,
action) sample, with probability $\kappa,$ we have to add the same sample to
the data set for the next time instant. With probability $1-\kappa$ choose the
next state in the trajectory. Hence, this transformation is easy to
incorporate in RL algorithms.

###  6.2 Proof of Theorem 3.3

Prior to presenting the proof, we define

$\displaystyle u_{k}=\max_{i}(\mathsf{T}h_{k}-h_{k})(i),$ (20) $\displaystyle
l_{k}=\min_{i}(\mathsf{T}h_{k}-h_{k})(i).$

A key lemma in the proof of convergence of approximate policy iteration in the
context of average reward is:

######  Lemma 6.4.

Let $J^{*}$ be the optimal average reward associated with the transformed MDP.
For all $k\in\mathbb{N}$:

$l_{k}-\epsilon\leq J_{\mu_{k+1}}\leq{J}^{*}\leq u_{k}$

###### Proof.

From definition,

$\displaystyle l_{k}\boldsymbol{1}$ $\displaystyle\leq\mathsf{T}h_{k}-h_{k}$

Since $\|\mathsf{T}h_{k}-\mathsf{T}_{\mu_{k+1}}h_{k}\|_{\infty}\leq\epsilon$,

$\displaystyle l_{k}\boldsymbol{1}$
$\displaystyle\leq\mathsf{T}_{\mu_{k+1}}h_{k}-h_{k}+\epsilon\boldsymbol{1}$
$\displaystyle=r_{\mu_{k+1}}+\mathbb{P}_{\mu_{k+1}}h_{k}-h_{k}+\epsilon\boldsymbol{1}$
$\displaystyle\mathbb{P}_{\mu_{k+1}}^{*}l_{k}\boldsymbol{1}$
$\displaystyle\leq\mathbb{P}_{\mu_{k+1}}^{*}r_{\mu_{k+1}}+\mathbb{P}_{\mu_{k+1}}^{*}\mathbb{P}_{\mu_{k+1}}h_{k}-\mathbb{P}_{\mu_{k+1}}^{*}h_{k}+\mathbb{P}_{\mu_{k+1}}^{*}\epsilon\boldsymbol{1}$

where $\mathbb{P}_{\mu_{k+1}}^{*}$ is a matrix whose rows are identical and
are the invariant distribution associated with the probability transition
kernel $\mathbb{P}_{\mu_{k+1}}$. Since
$\mathbb{P}_{\mu_{k+1}}^{*}\mathbb{P}_{\mu_{k+1}}=\mathbb{P}_{\mu_{k+1}}^{*}$,

$\displaystyle l_{k}\boldsymbol{1}$
$\displaystyle\leq\mathbb{P}^{*}_{\mu_{k+1}}r_{\mu_{k+1}}+\epsilon\boldsymbol{1}$
$\displaystyle l_{k}\boldsymbol{1}-\epsilon\boldsymbol{1}$
$\displaystyle\leq{J}_{\mu_{k+1}}\boldsymbol{1}$ $\displaystyle
l_{k}-\epsilon$ $\displaystyle\leq{J}_{\mu_{k+1}}$

From definition,

$\displaystyle{J}^{*}=\max_{\mu\in\Pi}{J}_{\mu}\geq{J}_{\mu_{k+1}}$

Let $\mu^{*}$ be the policy corresponding to the optimal average reward
${J}^{*}$ and value function $h^{*}$, ie.,

$\displaystyle{J}^{*}+h^{*}$
$\displaystyle=\max_{\mu}r_{\mu}+\mathbb{P}_{\mu}h^{*}$
$\displaystyle=r_{\mu^{*}}+\mathbb{P}_{\mu^{*}}h^{*}$

Then,

$\displaystyle u_{k}\boldsymbol{1}$ $\displaystyle\geq\mathsf{T}h_{k}-h_{k}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}\mathsf{T}_{\mu^{*}}h_{k}-h_{k}$
$\displaystyle=r_{\mu^{*}}+\mathbb{P}_{\mu^{*}}h_{k}-h_{k}$
$\displaystyle\mathbb{P}_{\mu^{*}}^{*}u_{k}\boldsymbol{1}$
$\displaystyle\geq\mathbb{P}_{\mu^{*}}^{*}r_{\mu^{*}}+\mathbb{P}_{\mu^{*}}^{*}\mathbb{P}_{\mu^{*}}h_{k}-\mathbb{P}_{\mu^{*}}^{*}h_{k}$
$\displaystyle u_{k}\boldsymbol{1}$
$\displaystyle\geq\mathbb{P}^{*}_{\mu^{*}}r_{\mu^{*}}$ $\displaystyle u_{k}$
$\displaystyle\geq{J}^{*}$

where $(a)$ is due to the fact that $\mathsf{T}$ is the maximising Bellman
operator.
Hence $\forall k\in\mathbb{N}$,

$\displaystyle l_{k}-\epsilon\leq{J}_{\mu_{k+1}}\leq{J}^{*}\leq u_{k}$

∎

Without any approximation, the above lemma indicates that there exists a state
whose value function changes by an amount less than the average reward
associated with the optimizing policy at that iteration, and also that there
exists a state whose value function increases by an amount larger than the
optimal average reward.

The proof proceeds by showing a geometric convergence rate for $l_{k}$. More
precisely, the following lemma is proved.

######  Lemma 6.5.

For all $k\in\mathbb{N}$, it is true that:

$\left({J}^{*}-l_{k}\right)\leq\left(1-\gamma\right)\left({J}^{*}-l_{k-1}\right)+\epsilon+2\delta$

###### Proof.

Define:

$g_{k}(i)=\left(\mathsf{T}h_{k}-h_{k}\right)(i)$ $\displaystyle g_{k}(i)$
$\displaystyle\geq\left(\mathsf{T}_{\mu_{k}}h_{k}-h_{k}\right)(i)$

Since $\mathsf{T}$ is the maximizing Bellman operator.
We know that:

  1. 1.

$\left\|h_{k}-h_{\mu_{k}}\right\|_{\infty}\leq\delta$

  2. 2.

For all constant $p\in\mathbb{R}$:

$\displaystyle\mathsf{T}_{\mu_{k}}\left(h_{k}+p\boldsymbol{1}\right)$
$\displaystyle=r_{\mu_{k}}+\mathbb{P}_{\mu_{k}}\left(h_{k}+p\boldsymbol{1}\right)$
$\displaystyle=r_{\mu_{k}}+\mathbb{P}_{\mu_{k}}h_{k}+p\boldsymbol{1}$
$\displaystyle=\mathsf{T}_{\mu_{k}}h_{k}+p\boldsymbol{1}$

We thus obtain,

$\displaystyle g_{k}(i)$
$\displaystyle\geq\mathsf{T}_{\mu_{k}}(h_{\mu_{k}}-\delta)-(h_{\mu_{k}}+\delta)$
(21)
$\displaystyle\geq\left(\mathsf{T}_{\mu_{k}}h_{\mu_{k}}-h_{\mu_{k}}\right)(i)-2\delta$
(22)

Recall that $h_{\mu_{k}}=\lim_{m\to\infty}\widetilde{T}^{m}_{\mu_{k+1}}h_{k}$

$\displaystyle\widetilde{\mathsf{T}}_{\mu_{k}}^{m}h_{k-1}$
$\displaystyle=\widetilde{\mathsf{T}}_{\mu_{k}}^{m-1}\widetilde{\mathsf{T}}_{\mu_{k}}h_{k-1}$
$\displaystyle=\widetilde{\mathsf{T}}_{\mu_{k}}^{m-1}\left(r_{\mu_{k}}+\mathbb{P}_{\mu_{k}}h_{k-1}-r_{\mu_{k}}(x^{*})\boldsymbol{1}-\left(\mathbb{P}_{\mu_{k}}h_{k-1}\right)(x^{*})\boldsymbol{1}\right)$
$\displaystyle=\widetilde{\mathsf{T}}_{\mu_{k}}^{m-1}\left(\mathsf{T}_{\mu_{k}}h_{k-1}-\left(\mathsf{T}_{\mu_{k}}h_{k-1}\right)(x^{*})\boldsymbol{1}\right)$
$\displaystyle=\widetilde{\mathsf{T}}_{\mu_{k}}^{m-2}\widetilde{\mathsf{T}}_{\mu_{k}}\left(\mathsf{T}_{\mu_{k}}h_{k-1}-\left(\mathsf{T}_{\mu_{k}}h_{k-1}\right)(x^{*})\boldsymbol{1}\right)$
$\displaystyle=\widetilde{\mathsf{T}}_{\mu_{k}}^{m-2}\left(r_{\mu_{k}}+\mathbb{P}_{\mu_{k}}\left(\mathsf{T}_{\mu_{k}}h_{k-1}-\mathsf{T}_{\mu_{k}}h_{k-1}(x^{*})\right)-r_{\mu_{k}}(x^{*})\boldsymbol{1}-\left(\mathbb{P}_{\mu_{k}}\left(\mathsf{T}_{\mu_{k}}h_{k-1}-\mathsf{T}_{\mu_{k}}h_{k-1}(x^{*})\right)\right)(x^{*})\boldsymbol{1}\right)$
$\displaystyle=\widetilde{\mathsf{T}}_{\mu_{k}}^{m-2}\left(r_{\mu_{k}}+\mathbb{P}_{\mu_{k}}\left(\mathsf{T}_{\mu_{k}}h_{k-1}\right)-\mathsf{T}_{\mu_{k}}h_{k-1}(x^{*})-r_{\mu_{k}}(x^{*})\boldsymbol{1}-\mathbb{P}_{\mu_{k}}\left(\mathsf{T}_{\mu_{k}}h_{k-1}\right)(x^{*})\boldsymbol{1}+\mathsf{T}_{\mu_{k}}h_{k-1}(x^{*})\right)$
$\displaystyle=\widetilde{\mathsf{T}}_{\mu_{k}}^{m-2}\left(\mathsf{T}^{2}_{\mu_{k}}h_{k-1}-\mathsf{T}^{2}_{\mu_{k}}h_{k-1}(x^{*})\boldsymbol{1}\right)$

Iterating, we thus obtain,

$h_{\mu_{k}}=\lim_{m\to\infty}\mathsf{T}^{m}_{\mu_{k}}h_{k-1}-\mathsf{T}^{m}_{\mu_{k}}h_{k-1}(x^{*})\boldsymbol{1}$

Substituting back in Equation 21,

$\displaystyle g_{k}(i)$
$\displaystyle\geq\left(\mathsf{T}_{\mu_{k}}\left(\lim_{m\to\infty}\mathsf{T}^{m}_{\mu_{k}}h_{k-1}-\mathsf{T}^{m}_{\mu_{k}}h_{k-1}(x^{*})\boldsymbol{1}\right)-\lim_{m\to\infty}\mathsf{T}^{m}_{\mu_{k}}h_{k-1}-\mathsf{T}^{m}_{\mu_{k}}h_{k-1}(x^{*})\boldsymbol{1}\right)(i)-2\delta$
$\displaystyle=\left(\mathsf{T}_{\mu_{k}}\left(\lim_{m\to\infty}\mathsf{T}^{m}_{\mu_{k}}h_{k-1}\right)-\lim_{m\to\infty}\mathsf{T}^{m}_{\mu_{k}}h_{k-1}(x^{*})\boldsymbol{1}-\lim_{m\to\infty}\mathsf{T}^{m}_{\mu_{k}}h_{k-1}-\lim_{m\to\infty}\mathsf{T}^{m}_{\mu_{k}}h_{k-1}(x^{*})\boldsymbol{1}\right)(i)-2\delta$
$\displaystyle=\left(\mathsf{T}_{\mu_{k}}\left(\lim_{m\to\infty}\mathsf{T}^{m}_{\mu_{k}}h_{k-1}\right)-\lim_{m\to\infty}\mathsf{T}^{m}_{\mu_{k}}h_{k-1}\right)(i)-2\delta$

Since $\mathsf{T}_{\mu_{k}}$ is a continuous operator, it is possible to take
the limit outside. We thus obtain,

$\displaystyle g_{k}(i)$
$\displaystyle\geq\lim_{m\to\infty}\left(\mathsf{T}^{m+1}_{\mu_{k}}h_{k-1}-\mathsf{T}^{m}_{\mu_{k}}h_{k-1}\right)(i)-2\delta$
$\displaystyle=\lim_{m\to\infty}\left(\mathsf{T}^{m}_{\mu_{k}}\mathsf{T}_{\mu_{k}}h_{k-1}-\mathsf{T}^{m}_{\mu_{k}}h_{k-1}\right)(i)-2\delta$
$\displaystyle=\lim_{m\to\infty}\left(\mathbb{P}^{m}_{\mu_{k}}\left(\mathsf{T}_{\mu_{k}}h_{k-1}-h_{k-1}\right)\right)(i)-2\delta$
$\displaystyle=\mathbb{P}^{*}_{\mu_{k}}\left(\mathsf{T}_{\mu_{k}}h_{k-1}-h_{k-1}\right)(i)-2\delta$

Since $\left\|T_{\mu_{k}}h_{k-1}-Th_{k-1}\right\|_{\infty}\leq\epsilon$,

$\displaystyle g_{k}(i)$
$\displaystyle\geq\mathbb{P}^{*}_{\mu_{k}}\left(\mathsf{T}h_{k-1}-h_{k-1}\right)(i)-2\delta-\epsilon$
$\displaystyle=\left(\mathbb{P}^{*}_{\mu_{k}}g_{k-1}\right)(i)-2\delta-\epsilon$

Note that from Lemma 3.2 in the mainpaper, we know that

$\min_{i,j\in\mathcal{S}}{\mathbb{P}}^{*}_{\mu_{k}}(j|i)>\gamma>0$

Also, since every policy is assumed to induce an irreducible Markov Process,
we have a limiting distribution with all positive entries. We thus obtain the
following crucial relationship,

$\displaystyle g_{k}(i)\geq(1-\gamma)l_{k-1}+\gamma u_{k-1}-2\delta-\epsilon$
(23)

Since the above inequation is true for all states $i$, it has to also be true
for $\operatorname*{argmin}_{i}\left(\mathsf{T}h_{k}-h_{k}\right)(i)$.
Hence, we obtain,

$\displaystyle l_{k}\geq(1-\gamma)l_{k-1}+\gamma u_{k-1}-2\delta-\epsilon$

Note that from Lemma 6.4, we know that $u_{k}\geq{J}^{*}$ for all
$k\in\mathbb{N}$.
Hence we obtain,

$\displaystyle l_{k}\geq(1-\gamma)l_{k-1}+\gamma{J}^{*}-2\delta-\epsilon$

Upon rearranging we obtain the result, that is,

$\displaystyle\left({J}^{*}-l_{k}\right)\leq(1-\gamma)\left({J}^{*}-l_{k-1}\right)+2\delta+\epsilon$

∎

We now present the proof of Theorem 3.3.

From Lemma 6.5, we thus have,

$\left({J}^{*}-l_{k}\right)\leq(1-\gamma)\left({J}^{*}-l_{k-1}\right)+2\delta+\epsilon$
(24)

However, we know that,

$l_{k}-\epsilon\leq{J}^{*}$

In order to iterate Equation 24, need to ensure the terms are non-negative.
Rearranging the terms thus yields,

$\left({J}^{*}-l_{k}+\epsilon\right)\leq(1-\gamma)\left({J}^{*}-l_{k-1}+\epsilon\right)+2\delta+(1+\gamma)\epsilon$

Let

$\omega=2\delta+(1+\gamma)\epsilon$

and

$a_{k}={J}^{*}-l_{k}+\epsilon.$

Then upon iterating, we obtain,

$\displaystyle a_{k}$ $\displaystyle\leq(1-\gamma)a_{k-1}+\omega$
$\displaystyle\leq(1-\gamma)((1-\gamma)a_{k-2}+\omega)+\omega$
$\displaystyle\leq\omega\frac{1-(1-\gamma)^{k}}{\gamma}+(1-\gamma)^{k}a_{0}$

Substituting back, we obtain,

$\displaystyle\left({J}^{*}-l_{k}+\epsilon\right)\leq\left(\frac{1-(1-\gamma)^{k}}{\gamma}\right)\left(2\delta+(1+\gamma)\epsilon\right)+(1-\gamma)^{k}({J}^{*}-l_{0}+\epsilon)$
(25)
$\displaystyle\left({J}^{*}-l_{k}\right)\leq\left(\frac{1-(1-\gamma)^{k}}{\gamma}\right)\left(2\delta+(1+\gamma)\epsilon\right)-\epsilon+(1-\gamma)^{k}({J}^{*}-l_{0}+\epsilon)$

Note that from Lemma 6.4 we know that

$l_{k}\leq{J}_{\mu_{k+1}}+\epsilon\leq{J}^{*}+\epsilon$

Hence we get,

$\left({J}^{*}-{J}_{\mu_{k+1}}\right)\leq\left({J}^{*}-l_{k}+\epsilon\right)$

Thus we obtain,

$\left({J}^{*}-{J}_{\mu_{k+1}}\right)\leq\left(\frac{1-(1-\gamma)^{k}}{\gamma}\right)\left(2\delta+(1+\gamma)\epsilon\right)+(1-\gamma)^{k}({J}^{*}-l_{0}+\epsilon)$

Theorem 3.3 presents an upper bound on the error in terms of the average
reward. Recall that, for the optimal relative value function $h$, the
following relationship holds: $Th-h=J^{*}\boldsymbol{1}.$ Thus, it is also
interesting to understand how $Th_{k}-h_{k}$ behaves under approximate policy
iteration. The following proposition characterizes the behavior of this term.

######  Proposition 6.6.

The iterates generated from approximate policy iteration algorithm 2 satisfy
the following bound:

$\displaystyle\left(u_{k-1}-l_{k-1}\right)$
$\displaystyle\leq\underbrace{\left(\frac{1-(1-\gamma)^{k}}{\gamma^{2}}\right)\left(2\delta+(1+\gamma)\epsilon\right)+\frac{2\delta+\epsilon}{\gamma}}_{\text{approximation
error}}+\underbrace{\frac{(1-\gamma)^{k}({J}^{*}-l_{0}+\epsilon)}{\gamma}}_{\text{initial
condition error}},$

where $u_{k},l_{k}$ are defined in Equation 20.

###### Proof.

It is known from Equation 23 that,

$g_{k}(i)\geq(1-\gamma)l_{k-1}+\gamma u_{k-1}-2\delta-\epsilon$

This further yields,

$l_{k}\geq(1-\gamma)l_{k-1}+\gamma u_{k-1}-2\delta-\epsilon$

From Lemma 6.4, we know that,

$l_{k}\leq{J}^{*}+\epsilon$ ${J}^{*}+\epsilon\geq(1-\gamma)l_{k-1}+\gamma
u_{k-1}-2\delta-\epsilon$
${J}^{*}-l_{k}+\epsilon\geq\gamma(u_{k-1}-l_{k-1})-2\delta-\epsilon$
$\gamma(u_{k-1}-l_{k-1})\leq\left({J}^{*}-l_{k}+\epsilon\right)+2\delta+\epsilon$

From Equation 25, we thus obtain,

$\gamma(u_{k-1}-l_{k-1})\leq\left(\frac{1-(1-\gamma)^{k}}{\gamma}\right)\left(2\delta+(1+\gamma)\epsilon\right)+(1-\gamma)^{k}({J}^{*}-l_{0}+\epsilon)+2\delta+\epsilon$

We thus obtain the result in Proposition 3.11,

$\left(u_{k-1}-l_{k-1}\right)\leq\left(\frac{1-(1-\gamma)^{k}}{\gamma^{2}}\right)\left(2\delta+(1+\gamma)\epsilon\right)+\frac{2\delta+\epsilon}{\gamma}+\frac{(1-\gamma)^{k}({J}^{*}-l_{0}+\epsilon)}{\gamma}$

∎

######  Corollary 6.7.

The asymptotic behavior of the relative value function iterates is given by

$\limsup_{k\to\infty}\left(u_{k}-l_{k}\right)\leq\frac{\epsilon\left(1+2\gamma\right)+2\delta\left(1+\gamma\right)}{\gamma^{2}}$

##### Comment of the Novelty of our Proof Technique:

As mentioned in the main body of the paper, our proof is inspired by the proof
of convergence of modified policy iteration in [VdW80]. However, since our
algorithm is quite different from modified policy iteration due to the
presence of errors in each step of the algorithm, special care is needed to
obtain useful performance bounds. Specifically, the impact of the errors at
each step have to be carefully bounded to ensure that the performance bounds
do not blow up to infinity as it does when we obtain a similar result for the
discounted-reward case and let the discount factor go to one.

###  6.3 Proofs from Section 4

Algorithm 2 and its analysis, adapted to the context of $Q$ function with time
dependent approximation errors is presented in this section. Most RL
algorithms use the state-action relative value function $Q$ instead of the
relative state value function $h$ to evaluate a policy. The corresponding
Bellman Equation in terms of $Q$ associated with any state-action pair $(s,a)$
is given by

${J}_{\mu}+Q_{\mu}(s,a)=r(s,a)+\left(\mathbb{Q}_{\mu}Q_{\mu}\right)(s,a)$

where
$\mathbb{Q}_{\mu}(s^{\prime},a^{\prime}|s,a)=\mu(a^{\prime}|s^{\prime})\mathbb{P}(s^{\prime}|s,a).$
Since we are interested in randomized policies for exploration reasons, the
irreducibility assumptions imposed on $\mathbb{P}_{\mu}$ also hold true for
the transition kernel $\mathbb{Q}_{\mu}$. The state relative value function
$h_{\mu}$ and state-action relative value function $Q_{\mu}$ are related as
$h_{\mu}(s)=\sum_{a}\mu(a|s)Q_{\mu}(s,a)$. Consider the following similar
definitions of the Bellman operators corresponding to the state-action value
function:

$(\mathsf{T}^{\mathsf{Q}}_{\mu}Q)(s,a)=r(s,a)+\left(\mathbb{Q}_{\mu}Q\right)(s,a)$

and

$(\mathsf{T}^{\mathsf{Q}}Q)(s,a)=r(s,a)+\max_{\mu\in\Pi}\left({\mathbb{Q}}_{\mu}Q\right)(s,a).$

Let $(s^{*},a^{*})$ represent some fixed state. Then the relative Bellman
operator, relative to $(s^{*},a^{*})$ is defined as:

$\left(\widetilde{\mathsf{T}}^{\mathsf{Q}}_{\mu}Q\right)(s,a)=r(s,a)+\left(\mathbb{Q}_{\mu}Q\right)(s,a)-r(s^{*},a^{*})-\left(\mathbb{Q}_{\mu}Q\right)(s^{*},a^{*}).$

The algorithm, thus adapted to state action relative value function is given
below:

Algorithm 4 Approximate Policy Iteration: Average Reward

1:Require $Q_{0}\in\mathbb{R}^{n}$

2:for $k=0,1,2,\ldots$ do

3: 1\. Compute $\mu_{k+1}\in\Pi$ such that
$\|\mathsf{T}Q_{k}-\mathsf{T}_{\mu_{k+1}}Q_{k}\|_{\infty}\leq\epsilon_{k}$

4: 2\. Compute $Q_{k+1}$ such that
$\|Q_{k+1}-Q_{\mu_{k+1}}\|_{\infty}\leq\delta_{k+1}$

5: where
$Q_{\mu_{k+1}}=\lim_{m\to\infty}\left({\widetilde{\mathsf{T}}^{\mathsf{Q}}_{\mu_{k+1}}}\right)^{m}Q_{k}$

6:end for

Define

$\displaystyle
g_{k}(s,a)=\left(\mathsf{T}^{\mathsf{Q}}Q_{k}-Q_{k}\right)(s,a),\qquad\forall(s,a)\in\mathcal{S}\times\mathcal{A},$

and set

$\displaystyle
l_{k}=\min_{(s,a)\in\mathcal{S}\times\mathcal{A}}g_{k}(s,a),\qquad
u_{k}=\max_{(s,a)\in\mathcal{S}\times\mathcal{A}}g_{k}(s,a).$

We prove the convergence in three parts:

  1. 1.

We prove that $l_{k}-\epsilon_{k}\leq{J}_{\mu_{k+1}}\leq{J}^{*}\leq u_{k}$.

  2. 2.

We use the result from 1 to prove Lemma 4.1.

  3. 3.

We iteratively employ the result in Lemma 4.1 to prove Proposition 4.2.

####  6.3.1 Proof of part 1

By definition, we have

$\displaystyle l_{k}\boldsymbol{1}$
$\displaystyle\leq\mathsf{T}^{\mathsf{Q}}Q_{k}-Q_{k}.$

Since
$\|\mathsf{T}^{\mathsf{Q}}Q_{k}-\mathsf{T}^{\mathsf{Q}}_{\mu_{k+1}}Q_{k}\|_{\infty}\leq\epsilon_{k}$,
it follows that

$\displaystyle l_{k}\boldsymbol{1}$
$\displaystyle\leq\mathsf{T}^{\mathsf{Q}}_{\mu_{k+1}}Q_{k}-Q_{k}+\epsilon_{k}\boldsymbol{1}$
$\displaystyle=r+\mathbb{Q}_{\mu_{k+1}}Q_{k}-Q_{k}+\epsilon_{k}\boldsymbol{1}.$

Multiplying by $\mathbb{Q}^{*}_{\mu_{k+1}}$, we get

$\displaystyle\mathbb{Q}_{\mu_{k+1}}^{*}l_{k}\boldsymbol{1}$
$\displaystyle\leq\mathbb{Q}_{\mu_{k+1}}^{*}r+\mathbb{Q}_{\mu_{k+1}}^{*}\mathbb{Q}_{\mu_{k+1}}Q_{k}-\mathbb{Q}_{\mu_{k+1}}^{*}Q_{k}+\mathbb{Q}_{\mu_{k+1}}^{*}\epsilon_{k}\boldsymbol{1}$
$\displaystyle=\mathbb{Q}_{\mu_{k+1}}^{*}r+\epsilon_{k}\boldsymbol{1}$ (26)

where $\mathbb{Q}_{\mu_{k+1}}^{*}$ is a matrix whose rows are identical and
are the invariant distribution associated with the probability transition
kernel $\mathbb{Q}_{\mu_{k+1}}$. Note that
$\mathbb{Q}_{\mu_{k+1}}^{*}\boldsymbol{1}=\boldsymbol{1}$, and that
$\mathbb{Q}_{\mu_{k+1}}^{*}\mathbb{Q}_{\mu_{k+1}}=\mathbb{Q}_{\mu_{k+1}}^{*}$.

Consider the Bellman Equation corresponding to the state-action relative value
function associated with the policy $\mu_{k+1}$:

$\displaystyle{J}_{\mu_{k+1}}+Q_{\mu_{k+1}}=r+\mathbb{Q}_{\mu_{k+1}}Q_{\mu_{k+1}}$

It follows that

$\displaystyle\mathbb{Q}^{*}_{\mu_{k+1}}{J}_{\mu_{k+1}}+\mathbb{Q}^{*}_{\mu_{k+1}}Q_{\mu_{k+1}}=\mathbb{Q}^{*}_{\mu_{k+1}}r+\mathbb{Q}^{*}_{\mu_{k+1}}\mathbb{Q}_{\mu_{k+1}}Q_{\mu_{k+1}}.$

Since
$\mathbb{Q}_{\mu_{k+1}}^{*}\mathbb{Q}_{\mu_{k+1}}=\mathbb{Q}^{*}_{\mu_{k+1}}$,
we have that

$\displaystyle{J}_{\mu_{k+1}}\boldsymbol{1}=\mathbb{Q}_{\mu_{k+1}}^{*}r.$

Hence, Equation 26 yields

$\displaystyle l_{k}\leq{J}_{\mu_{k+1}}+\epsilon_{k}.$

Equivalently, we have

$\displaystyle l_{k}-\epsilon_{k}\leq{J}_{\mu_{k+1}}.$

From definition,

$\displaystyle{J}^{*}=\max_{\mu\in\Pi}{J}_{\mu}\geq{J}_{\mu_{k+1}}.$

Let $\mu^{*}$ be the policy corresponding to the optimal average reward
${J}^{*}$. Let $Q^{*}$ denote the state-action relative value function
associated with the policy $\mu^{*}$. Note that $({J}^{*},Q^{*})$ is the
solution of the Bellman optimality equation, i.e.,

$\displaystyle{J}^{*}+Q^{*}$
$\displaystyle=r+\max_{\mu\in\Pi}\mathbb{Q}_{\mu}Q^{*}$
$\displaystyle=r+\mathbb{Q}_{\mu^{*}}Q^{*}.$

Then,

$\displaystyle u_{k}\boldsymbol{1}$
$\displaystyle\geq\mathsf{T}^{\mathsf{Q}}Q_{k}-Q_{k}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\geq}}\mathsf{T}^{\mathsf{Q}}_{\mu^{*}}Q_{k}-Q_{k}$
$\displaystyle=r+\mathbb{Q}_{\mu^{*}}Q_{k}-Q_{k},$

where (a) is due to the fact that $\mathsf{T}^{\mathsf{Q}}$ is the Bellman
optimality operator. Therefore, we have

$\displaystyle\mathbb{Q}_{\mu^{*}}^{*}u_{k}\boldsymbol{1}$
$\displaystyle\geq\mathbb{Q}_{\mu^{*}}^{*}r+\mathbb{Q}_{\mu^{*}}^{*}\mathbb{Q}_{\mu^{*}}Q_{k}-\mathbb{Q}_{\mu^{*}}^{*}Q_{k}$

Equivalently,

$\displaystyle u_{k}\boldsymbol{1}$
$\displaystyle\geq\mathbb{Q}^{*}_{\mu^{*}}r$

Therefore, we conclude that

$\displaystyle u_{k}$ $\displaystyle\geq{J}^{*}$

Hence, for all $k\in\mathbb{N}$,

$\displaystyle l_{k}-\epsilon_{k}\leq{J}_{\mu_{k+1}}\leq{J}^{*}\leq u_{k}$
(27)

####  6.3.2 Proof of Lemma 4.1

Recall that

$\displaystyle
g_{k}(s,a)=\left(\mathsf{T}^{\mathsf{Q}}Q_{k}-Q_{k}\right)(s,a)\geq\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}Q_{k}-Q_{k}\right)(s,a),$

where the inequality follows by the fact that $\mathsf{T}^{\mathsf{Q}}$ is the
Bellman optimality operator. Note that the Bellman operator
$\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}$ is shift-invariant, i.e., for all
$p\in\mathbb{R}$:

$\displaystyle\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}\left(Q_{k}+p\boldsymbol{1}\right)$
$\displaystyle=r+\mathbb{Q}_{\mu_{k}}\left(Q_{k}+p\boldsymbol{1}\right)$
$\displaystyle=r+\mathbb{Q}_{\mu_{k}}Q_{k}+p\boldsymbol{1}$
$\displaystyle=\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}Q_{k}+p\boldsymbol{1}$

Recall that $\left\|Q_{k}-Q_{\mu_{k}}\right\|_{\infty}\leq\delta_{k}$. Hence,
we have

$\displaystyle g_{k}(s,a)$
$\displaystyle\geq\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}(Q_{\mu_{k}}-\delta_{k}\boldsymbol{1})(s,a)-(Q_{\mu_{k}}(s,a)+\delta_{k})$
$\displaystyle\geq\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}Q_{\mu_{k}}-Q_{\mu_{k}}\right)(s,a)-2\delta_{k}$
(28)

Recall that
$Q_{\mu_{k}}=\lim_{m\to\infty}\left(\widetilde{\mathsf{T}}^{\mathsf{Q}}_{\mu_{k+1}}\right)^{m}Q_{k}$.
Therefore,

$\displaystyle\left(\widetilde{\mathsf{T}}^{\mathsf{Q}}_{\mu_{k}}\right)^{m}Q_{k-1}$
$\displaystyle=\left(\widetilde{\mathsf{T}}^{\mathsf{Q}}_{\mu_{k}}\right)^{m-1}\left(\widetilde{\mathsf{T}}^{\mathsf{Q}}_{\mu_{k}}\right)Q_{k-1}$
$\displaystyle=\left(\widetilde{\mathsf{T}}^{\mathsf{Q}}_{\mu_{k}}\right)^{m-1}\left(r+\mathbb{Q}_{\mu_{k}}Q_{k-1}-r(s^{*},a^{*})\boldsymbol{1}-\left(\mathbb{Q}_{\mu_{k}}Q_{k-1}\right)(s^{*},a^{*})\boldsymbol{1}\right)$
$\displaystyle=\left(\widetilde{\mathsf{T}}^{\mathsf{Q}}_{\mu_{k}}\right)^{m-1}\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}Q_{k-1}-\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}Q_{k-1}\right)(s^{*},a^{*})\boldsymbol{1}\right)$
$\displaystyle=\left(\widetilde{\mathsf{T}}^{\mathsf{Q}}_{\mu_{k}}\right)^{m-2}\left(\widetilde{\mathsf{T}}^{\mathsf{Q}}_{\mu_{k}}\right)\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}Q_{k-1}-\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}Q_{k-1}\right)(s^{*},a^{*})\boldsymbol{1}\right)$
$\displaystyle=\left(\widetilde{\mathsf{T}}^{\mathsf{Q}}_{\mu_{k}}\right)^{m-2}\bigg{(}r+\mathbb{Q}_{\mu_{k}}\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}Q_{k-1}-\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}Q_{k-1}\right)(s^{*},a^{*})\boldsymbol{1}\right)$
$\displaystyle\qquad\qquad\qquad-r(s^{*},a^{*})\boldsymbol{1}-\left(\mathbb{Q}_{\mu_{k}}\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}Q_{k-1}-\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}Q_{k-1}\right)(s^{*},a^{*})\boldsymbol{1}\right)\right)(s^{*},a^{*})\boldsymbol{1}\bigg{)}$
$\displaystyle=\left(\widetilde{\mathsf{T}}^{\mathsf{Q}}_{\mu_{k}}\right)^{m-2}\bigg{(}r+\mathbb{Q}_{\mu_{k}}\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}Q_{k-1}\right)-\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}Q_{k-1}\right)(s^{*},a^{*})\boldsymbol{1}$
$\displaystyle\qquad\qquad\qquad-r(s^{*},a^{*})\boldsymbol{1}-\mathbb{Q}_{\mu_{k}}\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}Q_{k-1}\right)(s^{*},a^{*})\boldsymbol{1}+\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}Q_{k-1}\right)(s^{*},a^{*})\boldsymbol{1}\bigg{)}$
$\displaystyle=\left(\widetilde{\mathsf{T}}^{\mathsf{Q}}_{\mu_{k}}\right)^{m-2}\left(\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}\right)^{2}Q_{k-1}-\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}\right)^{2}Q_{k-1}(s^{*},a^{*})\boldsymbol{1}\right)$

Iterating, we thus obtain,

$Q_{\mu_{k}}=\lim_{m\to\infty}(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}})^{m}Q_{k-1}-(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}})^{m}Q_{k-1}(s^{*},a^{*})\boldsymbol{1}$

Substituting back in Equation 28,

$\displaystyle g_{k}(s,a)$
$\displaystyle\geq\bigg{(}\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}\left(\lim_{m\to\infty}(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}})^{m}Q_{k-1}-(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}})^{m}Q_{k-1}(s^{*},a^{*})\boldsymbol{1}\right)$
$\displaystyle\qquad\qquad\qquad\qquad-\lim_{m\to\infty}\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}\right)^{m}Q_{k-1}-\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}\right)^{m}Q_{k-1}(s^{*},a^{*})\boldsymbol{1}\bigg{)}(s,a)-2\delta_{k}$
$\displaystyle=\bigg{(}\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}\left(\lim_{m\to\infty}(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}})^{m}Q_{k-1}\right)-\lim_{m\to\infty}(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}})^{m}Q_{k-1}(s^{*},a^{*})\boldsymbol{1}$
$\displaystyle\qquad\qquad\qquad\qquad-\lim_{m\to\infty}\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}\right)^{m}Q_{k-1}-\lim_{m\to\infty}\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}\right)^{m}Q_{k-1}(s^{*},a^{*})\boldsymbol{1}\bigg{)}(s,a)-2\delta_{k}$
$\displaystyle=\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}\left(\lim_{m\to\infty}\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}\right)^{m}Q_{k-1}\right)-\lim_{m\to\infty}\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}\right)^{m}Q_{k-1}\right)(s,a)-2\delta_{k}$

Since $\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}$ is a continuous operator, it is
possible to take the limit outside. We thus obtain,

$\displaystyle g_{k}(s,a)$
$\displaystyle\geq\lim_{m\to\infty}\left(\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}\right)^{m+1}Q_{k-1}-\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}\right)^{m}Q_{k-1}\right)(s,a)-2\delta_{k}$
$\displaystyle=\lim_{m\to\infty}\left(\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}\right)^{m}\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}Q_{k-1}-\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}\right)^{m}Q_{k-1}\right)(s,a)-2\delta_{k}$
$\displaystyle=\lim_{m\to\infty}\left(\mathbb{Q}^{m}_{\mu_{k}}\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}Q_{k-1}-Q_{k-1}\right)\right)(s,a)-2\delta_{k}$
$\displaystyle=\mathbb{Q}^{*}_{\mu_{k}}\left(\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}Q_{k-1}-Q_{k-1}\right)(s,a)-2\delta_{k}.$

Since
$\left\|\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}Q_{k-1}-\mathsf{T}^{\mathsf{Q}}Q_{k-1}\right\|_{\infty}\leq\epsilon_{k-1}$,

$\displaystyle g_{k}(s,a)$
$\displaystyle\geq\mathbb{Q}^{*}_{\mu_{k}}\left(\mathsf{T}^{\mathsf{Q}}Q_{k-1}-Q_{k-1}\right)(s,a)-2\delta_{k}-\epsilon_{k-1}$
$\displaystyle=\left(\mathbb{Q}^{*}_{\mu_{k}}g_{k-1}\right)(s,a)-2\delta_{k}-\epsilon_{k-1}.$

Recall the definition of $\gamma>0$ in Lemma 4.1. Note that all entries of
$\mathbb{Q}^{*}_{\mu_{k}}$ are bounded from below by $\gamma$. Hence, we have

$\displaystyle g_{k}(s,a)\geq(1-\gamma)l_{k-1}+\gamma
u_{k-1}-2\delta_{k}-\epsilon_{k-1}.$

Since the above inequality is true for all states
$(s,a)\in\mathcal{S}\times\mathcal{A}$, we obtain,

$\displaystyle l_{k}\geq(1-\gamma)l_{k-1}+\gamma
u_{k-1}-2\delta_{k}-\epsilon_{k-1}.$

The above inequality combined with Equation 27, yields

$\displaystyle
l_{k}\geq(1-\gamma)l_{k-1}+\gamma{J}^{*}-2\delta_{k}-\epsilon_{k-1}.$

Upon rearranging the above inequality, we obtain the result, that is,

$\displaystyle\left({J}^{*}-l_{k}\right)\leq(1-\gamma)\left({J}^{*}-l_{k-1}\right)+2\delta_{k}+\epsilon_{k-1}.$

Subsequently,

$\displaystyle\left({J}^{*}-\min_{(s,a)}\left(\mathsf{T}^{\mathsf{Q}}Q_{k}-Q_{k}\right)(s,a)\right)$
$\displaystyle\leq(1-\gamma)\left({J}^{*}-\min_{(s,a)}\left(\mathsf{T}^{\mathsf{Q}}Q_{k-1}-Q_{k-1}\right)(s,a)\right)$
$\displaystyle\qquad\qquad\qquad+2\left\|Q_{k}-Q_{\mu_{k}}\right\|_{\infty}+\left\|\mathsf{T}^{\mathsf{Q}}Q_{k-1}-\mathsf{T}^{\mathsf{Q}}_{\mu_{k}}Q_{k-1}\right\|_{\infty}$

####  6.3.3 Proof of Proposition 4.2

We now prove Proposition 4.2. From Lemma 4.1, we have

$\left({J}^{*}-l_{k}\right)\leq(1-\gamma)\left({J}^{*}-l_{k-1}\right)+2\delta_{k}+\epsilon_{k-1}.$
(29)

To iterate over Equation 29, we need to ensure the terms are non-negative.
Note that by the first part,

$l_{k}-\epsilon_{k}\leq{J}^{*}.$

Hence, rearranging the terms thus yields,

$\left({J}^{*}-l_{k}+\epsilon_{k}\right)\leq(1-\gamma)\left({J}^{*}-l_{k-1}+\epsilon_{k-1}\right)+\epsilon_{k}+2\delta_{k}+\epsilon_{k-1}-(1-\gamma)\epsilon_{k-1}.$

This is equivalent to

$\displaystyle\left({J}^{*}-l_{k}+\epsilon_{k}\right)\leq\left(1-\gamma\right)\left({J}^{*}-l_{k-1}+\epsilon_{k-1}\right)+\left(\epsilon_{k}+\gamma\epsilon_{k-1}\right)+2\delta_{k}.$

Let

$a_{k}={J}^{*}-l_{k}+\epsilon_{k}.$

Then, we obtain,

$\displaystyle a_{k}$
$\displaystyle\leq(1-\gamma)a_{k-1}+\epsilon_{k}+\gamma\epsilon_{k-1}+2\delta_{k}$
$\displaystyle\leq(1-\gamma)\left[(1-\gamma)a_{k-2}+\epsilon_{k-1}+\gamma\epsilon_{k-2}+2\delta_{k-1}\right]+\epsilon_{k}+\gamma\epsilon_{k-1}+2\delta_{k}$
$\displaystyle=(1-\gamma)^{k}a_{0}+\sum_{\ell=0}^{k-1}(1-\gamma)^{\ell}\epsilon_{k-\ell}+\gamma\sum_{\ell=0}^{k-1}(1-\gamma)^{\ell}\epsilon_{k-1-\ell}+2\sum_{\ell=0}^{k-1}(1-\gamma)^{\ell}\delta_{k-\ell}$

Since $\epsilon_{0}=0$,

$\displaystyle
a_{k}\leq\left(1-\gamma\right)^{k}a_{0}+\epsilon_{k}+\sum_{\ell=1}^{k-1}\left(1-\gamma\right)^{\ell-1}\epsilon_{k-\ell}+2\sum_{\ell=0}^{k-1}\left(1-\gamma\right)^{\ell}\delta_{k-\ell}$

Substituting for $a_{k}$, we get

$\displaystyle\left({J}^{*}-l_{k}\right)\leq\left(1-\gamma\right)^{k}\left({J}^{*}-l_{0}\right)+\sum_{\ell=1}^{k-1}\left(1-\gamma\right)^{\ell-1}\epsilon_{k-\ell}+2\sum_{\ell=0}^{k-1}\left(1-\gamma\right)^{\ell}\delta_{k-\ell}.$

Since from part 1, we know that
${J}^{*}-{J}_{\mu_{k+1}}\leq{J}^{*}-l_{k}+\epsilon_{k}$, we have

$\displaystyle{J}^{*}-{J}_{\mu_{k+1}}$
$\displaystyle\leq\left(1-\gamma\right)^{k}\left[{J}^{*}-\min_{i}\left(\mathsf{T}^{\mathsf{Q}}Q_{0}-Q_{0}\right)(i)\right]$
$\displaystyle+\sum_{\ell=1}^{k-1}\left(1-\gamma\right)^{\ell-1}\left[\left\|\mathsf{T}^{\mathsf{Q}}_{\mu_{k+1-\ell}}Q_{k-\ell}-\mathsf{T}^{\mathsf{Q}}Q_{k-\ell}\right\|_{\infty}\right]+{\left\|\mathsf{T}^{\mathsf{Q}}_{\mu_{k+1}}Q_{k}-\mathsf{T}^{\mathsf{Q}}Q_{k}\right\|_{\infty}}$
$\displaystyle+2\sum_{\ell=0}^{k-1}\left(1-\gamma\right)^{\ell}\left[\left\|Q_{k-\ell}-Q_{\mu_{k-\ell}}\right\|_{\infty}\right].$

Taking expectation, we have

$\displaystyle\mathbb{E}\left[{J}^{*}-{J}_{\mu_{k+1}}\right]$
$\displaystyle\leq\left(1-\gamma\right)^{k}\mathbb{E}\left[{J}^{*}-\min_{i}\left(\mathsf{T}^{\mathsf{Q}}Q_{0}-Q_{0}\right)(i)\right]$
$\displaystyle+\sum_{\ell=1}^{k-1}\left(1-\gamma\right)^{\ell-1}\mathbb{E}\left[\left\|\mathsf{T}^{\mathsf{Q}}_{\mu_{k+1-\ell}}Q_{k-\ell}-\mathsf{T}^{\mathsf{Q}}Q_{k-\ell}\right\|_{\infty}\right]+\mathbb{E}\left[\left\|\mathsf{T}^{\mathsf{Q}}_{\mu_{k+1}}Q_{k}-\mathsf{T}^{\mathsf{Q}}Q_{k}\right\|_{\infty}\right]$
$\displaystyle+2\sum_{\ell=0}^{k-1}\left(1-\gamma\right)^{\ell}\mathbb{E}\left[\left\|Q_{k-\ell}-Q_{\mu_{k-\ell}}\right\|_{\infty}\right].$

####  6.3.4 TD Learning for $Q$ function

One RL algorithm to estimate the state-action relative value function with
linear function approximation, associated with a policy $\mu$ is
TD($\lambda$). Finite-time sample complexity of TD($\lambda$) has been
recently studied in [ZZM21]. Invoking their results, restating it in terms of
the state-action relative value function rather than the state relative value
function, we characterize the sample complexity required to achieve certain
accuracy in the approximation.

We estimate $Q_{\mu}(s,a)$ linearly by $\phi(s,a)^{\top}\theta^{*}_{\mu}$, for
some $\theta^{*}_{\mu}\in\mathbb{R}^{d}$, where $\phi(s,a)=$
$[\phi_{1}(s,a),\cdots,\phi_{d}(s,a)]^{T}\in\mathbb{R}^{d}$ is the feature
vector associated with $(s,a)\in\mathcal{S}\times\mathcal{A}$. Here,
$\theta^{*}_{\mu}$ is a fixed point of
$\Phi\theta=\Pi_{D,W_{\phi}}\mathsf{T}^{\mathsf{Q},\lambda}_{\mu}\Phi\theta$,
where $\Phi$ is an $|\mathcal{S}|\times d$ matrix whose $k$-th column is
$\phi_{k}$,
$\mathsf{T}^{\mathsf{Q},\lambda}_{\mu}=(1-\lambda)\sum_{m=0}^{\infty}\lambda^{m}\left(\widehat{\mathsf{T}}^{\mathsf{Q}}_{\mu}\right)^{m+1}$
where
$\widehat{\mathsf{T}}^{\mathsf{Q}}_{\mu}=\mathsf{T}^{\mathsf{Q}}_{\mu}-{J}_{\mu}\boldsymbol{1}$,
$D$ is the diagonal matrix with diagonal elements given by the stationary
distribution of the policy $\mu$ on $\mathcal{S}\times\mathcal{A}$, and
$\Pi_{D,W_{\phi}}=\Phi(\Phi^{\top}D\Phi)^{-1}\Phi^{\top}D$ is the projection
matrix onto $W_{\Phi}=\\{\Phi\theta|\theta\in\mathbb{R}^{d}\\}$ with respect
to the norm $\|\cdot\|_{D}$. Note that this fixed point equation may have
multiple solutions. In particular, if $\Phi\theta_{e}=\boldsymbol{1}$, then
$\theta^{*}_{\mu}+p\theta_{e}$ is also a solution for any $p\in\mathbb{R}$.
Hence, we focus on the set of equivalent classes $E$ where we say
$\theta_{1}\sim\theta_{2}$ if $\Phi(\theta_{1}-\theta_{2})=\boldsymbol{1}$.
The value of $\mathbb{E}[\|\Pi_{2,E}(\theta-\theta^{*}_{\mu})\|_{2}^{2}]$
characterizes the accuracy of our approximation, where $\Pi_{2,E}$ is the
projection onto $E$ with respect to $\|\cdot\|_{2}$. Suppose that
$\\{\phi_{1},\phi_{2},\cdots,\phi_{d}\\}$ are linearly independent and that
$\max_{(s,a)\in\mathcal{S}\times\mathcal{A}}\|\phi(s,a)\|_{2}\leq 1$.

Upon making a new observation $(s_{t+1},a_{t+1})$ for $t\geq 0$, the average
reward $TD(\lambda)$ uses the following update equations:

$\displaystyle\text{Eligibility trace: }z_{t}=\lambda
z_{t-1}+\phi(s_{t},a_{t})$ (30) $\displaystyle\text{TD error:
}d_{t}=r(s_{t},a_{t})-{J}_{t}+\phi(s_{t+1},a_{t+1})^{\top}\theta_{t}$
$\displaystyle\qquad\qquad\qquad\qquad-\phi(s_{t},a_{t})^{\top}\theta_{t}$
$\displaystyle\text{average-reward update:
}{J}_{t+1}={J}_{t}+c_{\alpha}\beta_{t}(r(s_{t},a_{t})-{J}_{t}),$
$\displaystyle\text{parameter update:
}\theta_{t+1}=\theta_{t}+\beta_{t}\delta_{t}(\theta)z_{t},$

where $\beta_{t}$ is the scalar step size, $c_{\alpha}>0$ is a constant, and
$z_{-1}$ is initialized to be zero. Following the same argument as in [ZZM21],
we get the following theorem which characterizes the number of samples
required to get a certain accuracy in the approximation.

######  Theorem 6.8.

Let $\beta_{t}=\frac{c_{1}}{t+c_{2}}$, and suppose that the positive constants
$c_{1}$, $c_{2}$, and $c_{\alpha}$ are properly chosen. Then, the number of
samples required to ensure an approximation accuracy of
$\mathbb{E}[\|\Pi_{2,E}(\theta-\theta^{*}_{\mu})\|_{2}^{2}]\leq\delta$, is
given by

$\displaystyle\tau=O\left(\frac{K\log(\frac{1}{\Delta})\|\theta^{*}_{\mu}\|_{2}^{2}}{\Delta^{4}(1-\lambda)^{4}\delta^{2}}\right),$

where $K$ is the minimum mixing time constant across all probability
transition matrices induced by the policies,

$\displaystyle\Delta=\min_{\|\theta\|_{2}=1,\theta\in
E}\theta^{T}\Phi^{T}D(I-\mathbb{Q}^{\lambda})\Phi\theta>0,$

and
$\mathbb{Q}^{\lambda}=(1-\lambda)\sum_{m=0}^{\infty}\lambda^{m}\mathbb{Q}^{m+1}$.

###### Proof.

The proof is a simple adaptation of the proof in [ZZM21] for the state
relative value function. ∎

Let $Q_{k}=\Phi\theta_{k}$, where $\theta_{k}$ is the output of TD($\lambda$)
algorithm with $T$ samples. Then, we have

$\displaystyle\|Q_{k}-Q_{\mu_{k}}\|_{\infty}\leq\|\Phi(\theta_{k}-\theta_{\mu_{k}}^{*})\|_{\infty}+\|\Phi\theta_{\mu_{k}}^{*}-Q_{\mu_{k}}\|_{\infty},$

where the second term above is the error associated with the choice of $\Phi$.

Since $\max_{(s,a)\in\mathcal{S}\times\mathcal{A}}\|\phi(s,a)\|_{2}\leq 1$, we
get

$\displaystyle\delta_{k}=d\|\theta_{k}-\theta_{\mu_{k}}^{*}\|_{\infty}+\|\Phi\theta_{\mu_{k}}^{*}-Q_{\mu_{k}}\|_{\infty}.$

Using Theorem 6.8, we get a bound on the value of
$\|\theta_{k}-\theta_{\mu_{k}}^{*}\|_{\infty}$. Note that if
$\Phi\theta_{e}=\boldsymbol{1}$ for some $\theta_{e}\in\mathbb{R}^{d}$, then
we can pick $\theta_{k+1}$ and $\theta_{\mu_{k+1}}^{*}$ so that
$\phi(s^{*},a^{*})^{T}\theta_{k+1}=\phi(s^{*},a^{*})^{T}\theta_{\mu_{k+1}}^{*}=0$.
Otherwise, there is a unique choice for $\theta_{\mu_{k+1}}^{*}$, and we have
$E=\mathbb{R}^{d}$.

The expected value of learning error can thus be expressed as:

$\displaystyle\mathbb{E}\left[\delta_{k}\right]=\mathbb{E}\left[\delta_{\mathsf{TD},k}\right]+\mathbb{E}\left[\delta_{0,k}\right]$

where
${\delta_{\mathsf{TD},k}}=d\|\theta_{k+1}-\theta_{\mu_{k+1}}^{*}\|_{\infty}$
represents the TD learning error of the parameter vector
$\theta_{\mu_{k+1}}^{*}$ and
${\delta_{0,k}}=\|\Phi\theta_{\mu_{k+1}}^{*}-Q_{\mu_{k+1}}\|_{\infty}$
represents the function approximation error associated with the span of the
feature vector matrix $\Phi$.

${\delta_{\mathsf{TD},k}}$ has a direct dependence on the number of samples
utilized for TD learning and the mixing time of the corresponding Markov Chain
induced by the policy $\mu_{k}.$ More precisely, from Theorem 3.1,

$\displaystyle\mathbb{E}\left[\delta_{\mathsf{TD},k}\right]=O\left(\sqrt{\frac{K\log(\frac{1}{\Delta})\|\theta^{*}_{\mu_{k}}\|_{2}^{2}}{\Delta^{4}(1-\lambda)^{4}\tau}}\right),$

Hence as long as the mixing constant $\Delta$ is uniformly greater than zero,
and the feature vectors $\theta^{*}_{\mu_{k}}$ are such that they are
uniformly upper bounded in $k$, it is true that

$\displaystyle\mathbb{E}\left[\delta_{\mathsf{TD},k}\right]=\frac{C}{\sqrt{\tau}},$

for some constant $C>0$.

Next, we prove the corollaries for specific policy improvement algorithms.
Since the policy improvement part does not depend on whether the problem is a
discounted-reward problem or an average reward problem, we can borrow the
results from [CM22] to identify $\epsilon_{k}$ in each of the corollaries.

####  6.3.5 Proof of Corollary 4.3

Recall the greedy update rule. Let
$a^{*}=\operatorname*{argmax}_{a^{\prime}}Q_{k}(s,a^{\prime})$. Given a
parameter $\beta>0$, at any time instant $k$, the greedy policy update
$\mu_{k+1}$ is given by:

$\displaystyle\mu_{k+1}(a|s)=\begin{cases}\frac{1}{\beta|\mathcal{A}|},&\text{if
}a\neq a^{*}\\\ \frac{1}{\beta|\mathcal{A}|}+1-\frac{1}{\beta},&\text{if
}a=a^{*}\end{cases}$ (31)

Let $\eta_{k}=\max_{\begin{subarray}{c}s^{\prime}\in\mathcal{S}\\\
a^{\prime}\in\mathcal{A}\end{subarray}}|\mathbb{Q}_{k}(s^{\prime},a^{\prime})|$.
The policy improvement approximation can be shown to be the following:

$\displaystyle\epsilon_{k}$
$\displaystyle=\left(\mathsf{T}^{\mathsf{Q}}Q_{k}-\mathsf{T}^{\mathsf{Q}}_{\mu_{k+1}}Q_{k}\right)(s,a)$
$\displaystyle\leq\sum_{s^{\prime}\in\mathcal{S}}\mathbb{P}(s^{\prime}|s,a)\frac{2}{\beta}\max_{a^{\prime}\in\mathcal{A}}|Q_{k}(s^{\prime},a^{\prime})|$
$\displaystyle\leq\frac{2\eta_{k}}{\beta}.$

Recall the error due to TD Learning

$\displaystyle\mathbb{E}\left[\delta_{k}\right]=\mathbb{E}\left[\delta_{\mathsf{TD},k}\right]+\mathbb{E}\left[\delta_{0,k}\right].$

Let $\overline{\delta}_{0}=\max_{t}\delta_{0,t}$. Then we obtain the
following:

$\displaystyle\mathbb{E}\left[\delta_{k}\right]=\overline{\delta}_{0}+\frac{C}{\sqrt{\tau}}.$

Substituting for expressions in Proposition 4.2, we obtain,

$\displaystyle\mathbb{E}\left[J^{*}-J_{\mu_{T+1}}\right]$
$\displaystyle\leq\left(1-\gamma\right)^{T}\mathbb{E}\left[{J}^{*}-\min_{i}\left(\mathsf{T}^{\mathsf{Q}}Q_{0}-Q_{0}\right)(i)\right]$
$\displaystyle+2\sum_{\ell=0}^{T-1}\left(1-\gamma\right)^{\ell}\left(\overline{\delta}_{0}+\frac{C}{\sqrt{\tau}}\right)+\sum_{\ell=1}^{T-1}\left(1-\gamma\right)^{\ell-1}\frac{2\eta_{T-\ell}}{\beta}+\frac{2\eta_{T}}{\beta}.$

Let
$c_{0}=\mathbb{E}\left[{J}^{*}-\min_{i}\left(\mathsf{T}^{\mathsf{Q}}Q_{0}-Q_{0}\right)(i)\right]$
be the error associated with the initial condition. Let
$\overline{\eta}=\max_{t}\eta_{t}$ ($\overline{\eta}$ can be the uniform upper
bound of the estimates $Q_{k}$ of relative state action value function
$Q_{\mu_{k}}$ over $k.$) Then we obtain the result in the corollary,

$\displaystyle\mathbb{E}\left[J^{*}-J_{\mu_{T+1}}\right]$
$\displaystyle\leq(1-\gamma)^{T}c_{0}+\frac{2}{\gamma}\left(\overline{\delta}_{0}+\frac{C}{\sqrt{\tau}}\right)+\left(\frac{1+\gamma}{\gamma}\right)\frac{2\overline{\eta}}{\beta}.$
(32)

####  6.3.6 Proof of Corollary 4.4

Recall the softmax policy update. Given a parameter $\beta>0$, at any time
instant $k$, the Softmax update policy $\mu_{k+1}$ is:

$\mu_{k+1}(a|s)=\frac{\exp\left(\beta
Q_{k}(s,a)\right)}{\sum_{a^{\prime}\in\mathcal{A}}\exp\left(\beta
Q_{k}(s,a^{\prime})\right)}.$ (33)

The policy improvement approximation for this update rule turns out to be time
independent and is given by:

$\displaystyle\epsilon_{k}=\left(\mathsf{T}^{\mathsf{Q}}Q_{k}-\mathsf{T}^{\mathsf{Q}}_{\mu_{k+1}}Q_{k}\right)(s,a)\leq\frac{\log|\mathcal{A}|}{\beta}.$

Given $\overline{\delta}_{0}=\max_{t}\delta_{0,t}$ the following is true,

$\displaystyle\mathbb{E}\left[\delta_{k}\right]=\overline{\delta}_{0}+\frac{C}{\sqrt{\tau}}.$

Substituting for expressions in Proposition 4.2, we obtain,

$\displaystyle\mathbb{E}\left[J^{*}-J_{\mu_{T+1}}\right]$
$\displaystyle\leq\left(1-\gamma\right)^{T}\mathbb{E}\left[{J}^{*}-\min_{i}\left(\mathsf{T}^{\mathsf{Q}}Q_{0}-Q_{0}\right)(i)\right]$
$\displaystyle+2\sum_{\ell=0}^{T-1}\left(1-\gamma\right)^{\ell}\left(\overline{\delta}_{0}+\frac{C}{\sqrt{\tau}}\right)+\sum_{\ell=1}^{T-1}\left(1-\gamma\right)^{\ell-1}\frac{\log|\mathcal{A}|}{\beta}+\frac{\log|\mathcal{A}|}{\beta}.$

Let
$c_{0}=\mathbb{E}\left[{J}^{*}-\min_{i}\left(\mathsf{T}^{\mathsf{Q}}Q_{0}-Q_{0}\right)(i)\right]$
be the error associated with the initial condition. Then we obtain the result
in the corollary,

$\displaystyle\mathbb{E}\left[J^{*}-J_{\mu_{T+1}}\right]$
$\displaystyle\leq(1-\gamma)^{T}c_{0}+\frac{2}{\gamma}\left(\overline{\delta}_{0}+\frac{C}{\sqrt{\tau}}\right)+\left(\frac{1+\gamma}{\gamma}\right)\frac{\log\left(|\mathcal{A}|\right)}{\beta}.$
(34)

####  6.3.7 Proof of Corollary 4.5

Recall the mirror descent update. Given $\beta>0$ the mirror descent update is
given by:

$\displaystyle\mu_{k+1}(a|s)=\frac{\mu_{k}(a|s)e^{\beta
Q_{k}(s,a)}}{\sum_{a^{\prime}\in\mathcal{A}}\mu_{k}(a^{\prime}|s)e^{\beta
Q_{k}(s,a^{\prime})}}$ (35)

The policy improvement error for this update rule and is given by:

$\displaystyle\epsilon_{k}$
$\displaystyle=\left(\mathsf{T}^{\mathsf{Q}}Q_{k}-\mathsf{T}^{\mathsf{Q}}_{\mu_{k+1}}Q_{k}\right)(s,a)$
$\displaystyle\leq\frac{1}{\beta}\log\frac{1}{\min_{s\in\mathcal{S}}\mu_{k+1}\left(a^{*}(s)|s\right)}.$

where $a^{*}(s)$ is the optimal action at state $s.$ Let
$\omega_{k+1}=\min_{s\in\mathcal{S}}\mu_{k+1}\left(a^{*}(s)|s\right)$ Given
that the TD learning error is of the form

$\displaystyle\mathbb{E}\left[\delta_{k}\right]=\overline{\delta}_{0}+\frac{C}{\sqrt{\tau}},$

Substituting for expressions in Proposition 4.2, we obtain,

$\displaystyle\mathbb{E}\left[J^{*}-J_{\mu_{T+1}}\right]$
$\displaystyle\leq\left(1-\gamma\right)^{T}\mathbb{E}\left[{J}^{*}-\min_{i}\left(\mathsf{T}^{\mathsf{Q}}Q_{0}-Q_{0}\right)(i)\right]$
$\displaystyle+2\sum_{\ell=0}^{T-1}\left(1-\gamma\right)^{\ell}\left(\overline{\delta}_{0}+\frac{C}{\sqrt{\tau}}\right)+\sum_{\ell=1}^{T-1}\left(1-\gamma\right)^{\ell-1}\frac{2}{\beta}\log{\frac{1}{\omega_{T-\ell}}}+\frac{2}{\beta}\log{\frac{1}{\omega_{T}}}.$

Let
$c_{0}=\mathbb{E}\left[{J}^{*}-\min_{i}\left(\mathsf{T}^{\mathsf{Q}}Q_{0}-Q_{0}\right)(i)\right]$
be the error associated with the initial condition. Let
$\underline{\omega}=\min_{t}\omega_{t}$ Then we obtain the result in the
corollary,

$\displaystyle\mathbb{E}\left[J^{*}-J_{\mu_{T+1}}\right]$
$\displaystyle\leq(1-\gamma)^{T}c_{0}+\frac{2}{\gamma}\left(\overline{\delta}_{0}+\frac{C}{\sqrt{\tau}}\right)+\left(\frac{1+\gamma}{\gamma\beta}\right)\log\left(\frac{1}{\underline{\omega}}\right).$
(36)

####  6.3.8 Regret Analysis

Recall the pseudo regret defined as follows:

$\displaystyle R_{\text{PS}}(K)=\sum_{t=1}^{K}\left(J^{*}-J_{\mu_{t}}\right),$
(37)

where $\mu_{t}$ us the policy utilized at time $t$ and obtained through mirror
descent, and $K$ is the time horizon. Since $K=\tau T$, we have

$\displaystyle
R_{\text{PS}}(K)=\tau\sum_{t=1}^{T}\left(J^{*}-J_{\mu_{t}}\right).$ (38)

Substituting for $J^{*}-J_{\mu_{t}}$, it is true that

$\displaystyle
R_{\text{PS}}(K)=\tau\left(\sum_{t=1}^{T}(1-\gamma)^{T}c_{0}+\frac{1+\gamma}{\gamma\beta}\log\left(\frac{1}{\omega}\right)+\frac{2}{\gamma}\left(\overline{\delta}_{0}+\frac{c_{3}}{\sqrt{\tau}}\right)\right).$
(39)

Let $\beta=\sqrt{\tau}$. The above regret can be simplified as:

$\displaystyle R_{\text{PS}}(K)=\frac{\tau
c_{0}}{\gamma}+\frac{K}{\gamma\sqrt{\tau}}\left((1+\gamma)\log\left(\frac{1}{\omega}\right)+2c_{3}\right)+\frac{2K\overline{\delta}_{0}}{\gamma}$
(40)

Let $c_{5}=(1+\gamma)\log(1/\omega)+2c_{3}$. We then have

$\displaystyle R_{\text{PS}}(K)=\frac{\tau
c_{0}}{\gamma}+\frac{Kc_{5}}{\gamma\sqrt{\tau}}+\frac{2K\overline{\delta}_{0}}{\gamma}.$
(41)

Optimizing for regret involves equating $\frac{\tau c_{0}}{\gamma}$ and
$\frac{Kc_{5}}{\gamma\sqrt{\tau}}$. This yields
$\tau=\left(\frac{Kc_{5}}{c_{0}}\right)^{2/3}$. Further substituting for
$\tau$ yields

$\displaystyle R_{\text{PS}}(K)$
$\displaystyle=\left(\frac{Kc_{3}}{c_{0}}\right)^{2/3}\cdot\frac{c_{0}}{\gamma}+\frac{Kc_{5}c_{0}^{1/3}}{\gamma(Kc_{5})^{1/3}}+\frac{2K\overline{\delta}_{0}}{\gamma}$
(42) $\displaystyle=\frac{(Kc_{5})^{2/3}\cdot
c_{0}^{1/3}}{\gamma}+\frac{(Kc_{5})^{2/3}\cdot
c_{0}^{1/3}}{\gamma}+\frac{2K\overline{\delta}_{0}}{\gamma}$ (43)
$\displaystyle=\frac{2c_{5}^{2/3}\cdot c_{0}^{1/3}\cdot
K^{2/3}}{\gamma}+\frac{2K\overline{\delta}_{0}}{\gamma}.$ (44)

Let $c_{6}=2c_{5}^{2/3}c_{0}^{1/3}$. We have

$\displaystyle
R_{\text{PS}}(K)=\frac{K^{2/3}c_{6}}{\gamma}+\frac{2K\overline{\delta_{0}}}{\gamma}.$
(45)