# Performance of NPG in Countable State-Space Average-Cost RL

Yashaswini Murthy
Electrical and Computer Engineering
University of Illinois Urbana-Champaign
Urbana, IL 61801
<EMAIL_ADDRESS>
&Isaac Grosof
Electrical and Computer Engineering
University of Illinois Urbana-Champaign
Urbana, IL 61801
<EMAIL_ADDRESS>&Siva Theja Maguluri
Industrial and Systems Engineering
Georgia Institute of Technology
Atlanta, GA 30332
<EMAIL_ADDRESS>&R. Srikant
Electrical and Computer Engineering
University of Illinois Urbana-Champaign
Urbana, IL 61801
<EMAIL_ADDRESS>
###### Abstract

We consider policy optimization methods in reinforcement learning settings
where the state space is arbitrarily large, or even countably infinite. The
motivation arises from control problems in communication networks, matching
markets, and other queueing systems. We consider Natural Policy Gradient
(NPG), which is a popular algorithm for finite state spaces. Under reasonable
assumptions, we derive a performance bound for NPG that is independent of the
size of the state space, provided the error in policy evaluation is within a
factor of the true value function. We obtain this result by establishing new
policy-independent bounds on the solution to Poisson’s equation, i.e., the
relative value function, and by combining these bounds with previously known
connections between MDPs and learning from experts.

##  1 Introduction

We are motivated by control problems in queueing models of resource
allocation, such as those arising in communication networks, cloud computing
systems, and riding hailing services. Examples of such systems include the
following:

  1. (a)

The switch fabric in Internet routers and data centers where packets have to
be transported (or switched) from one of many input ports to one of many
output ports [SY13]: the system is modeled as a bipartite graph with input
ports on one side and output ports on the other side. Technological
constraints dictate that at each time slot, a matching must be selected in the
bipartite graph, and packets are transferred along the edges of the matching
from each input to the corresponding output. The goal is to find a sequence of
matchings to minimize either the average delay experienced by the packets in
the switch or the probability that the delay exceeds some threshold.

  2. (b)

Scheduling problems at base stations in 5G networks [SY13]: at a central
controller (typically the base station associated with a cell in a cellular
network), packets arrive and are queued in a separate queue for each receiver.
The goal is to schedule these packets over different frequencies and time
slots to minimize the average delay of the packets in the system, while taking
into account the time-varying channel conditions in a wireless network due to
fading and other wireless medium effects.

  3. (c)

Scheduling workloads in cloud computing systems [MSV+19]: a workload in such
systems takes the form of a collection directed acyclic graphs, where each DAG
represents a job, the nodes in the graphs represent tasks in the job and the
directed edges represent precedence relationships among the tasks in the
graph. The goal is to allocate resources to tasks from a sequence of arriving
jobs, while respecting the precedence relationships of the tasks within each
job and minimizing the average delay experienced by the jobs.

  4. (d)

Customer-driver matching in ride hailing platforms such as Uber and Lyft
[ÖW20, VBMW23]: the role of such platforms can be modeled as controlling the
number of nodes in a bipartite graph, where one side is the set of waiting
customers and the other side in the set of available drivers. The goal of a
ride hailing platform is to choose a set of prices and match customers to
drivers so that a weighted combination of the average delay experienced by
customers and the average profit is optimized.

The above problems exhibit several common features:

  1. (i)

The state space of these problems is discrete, typically consisting of the
queue lengths of the various entities waiting in the system such as packets,
customers, drivers, jobs and tasks, depending on the context. Discrete state
spaces are commonly studied in the reinforcement learning (RL) literature;
however, in our applications, the state space is also countably infinite for
all practical purposes, since queue lengths can become unbounded. In some
applications, such as communication networks, the packet buffers may be finite
but it is well known that modeling them as infinite buffers leads to good
scheduling algorithms [SY13]. It should be noted that even if one were to
model the finiteness of the buffers explicitly in our model, our results will
still hold, and our performance guarantees would not depend on the size of the
buffers.

  2. (ii)

Because we are dealing with a vector of queue lengths as the state of the
system, the problems have some limited amount of structure that can and should
be exploited to design good algorithms. In particular, it is relatively
straightforward to design algorithms that ensures that the system is stable,
i.e., the queue length is finite with probability one [SY13]. On the other
hand, algorithms to optimize performance objectives such as average delay are
unknown except in limited regimes [ES12, MS16]. Therefore, data-driven
approaches such as reinforcement learning (RL) are natural candidates to solve
such problems.

  3. (iii)

Due to a well-known result called Little’s law, minimizing average delay is
equivalent to minimizing average queue lengths [LG08]. Thus, the natural
instantaneous cost in such problems is the current total queue length. Note
that unlike many RL models, this cost is unbounded and results which assume
that the costs (or rewards) at each (state, action) pair are uniformly bounded
do not hold for our problems.

Given the above background, our goal in this paper is to study policy
optimization algorithms for such countable state space models with discrete,
finite action spaces where the cost is proportional to the total queue length
in the system, and can thus grow in an unbounded fashion. For this purpose, we
study the natural policy gradient (NPG) algorithm. Our main contributions are
the following:

  1. (1)

One of the standard regret results for NPG uses a connection to a fundamental
learning-theoretic problem called the best-experts problem. We show that this
standard analysis does not apply to our problem due to the unbounded nature of
the instantaneous cost in our problem.

  2. (2)

We show that one can obtain nontrivial regret bounds by making a small, but
critical, change to the step-size used in the best-experts algorithm, and by
obtaining bounds on the relative value function (called the solution of the
Poisson’s equation in the applied probability literature).

  3. (3)

An important component of our work is to obtain bounds on the solution of
Poisson’s equation that are uniform across all policies. To the best of our
knowledge, prior works on obtaining bounds on the solution of Poisson’s
equation are limited to specific policies. A key contribution of our paper is
to show that uniform bounds can be obtained by exploiting certain structural
properties of the mathematical models for the motivating applications
mentioned earlier.

  4. (4)

Policy evaluation using temporal difference learning and Monte Carlo methods
have been well studied in the literature, so we do not consider them
explicitly in this paper. However, we do consider the error due to function
approximation. Traditionally, for analytical purposes, it is assumed that
there is a uniform bound on the function approximation error of the value
function. We argue that such an assumption does not make sense for queueing
models and propose a more general model for the function approximation.
Existing mathematical tools for the study of convergence of RL algorithms
cannot handle our proposed model for the function approximation error.
However, we show that, by exploiting the special structure of our queueing
models and the associated bounds on the solution to Poisson’s equation, we can
obtain non-trivial regret bounds for policy optimization.

###  1.1 Related Work

The Natural Policy Gradient algorithm is a well-known and extensively studied
algorithm for MDP optimization, in both the average-reward and discounted-
reward settings [Kak01, AKLM21, GSP19, MS23, MMS23]. An important line of
research on the NPG algorithm treats the MDP-optimization problem as many
parallel instances of the expert advice problem, and treats the NPG algorithm
as many parallel instances of the weighted majority algorithm. Even-dar et al.
[EDKM09] use this approach to prove the first convergence result for NPG in
the finite-state average-reward tabular setting, and [AYBB+19] expand upon
that result to incorporate function approximation. Our result uses the same
“parallel weighted majority” framing, but generalizes the result to the
infinite-state-space setting by incorporating state-dependent learning rates.

Policy gradient algorithms have been studied in certain specialized settings
with average-reward uncountably-infinite state spaces [FGKM18, KT08]: the
Linear Quadratic Regulator and the base-stock inventory control problem,
demonstrating rapid convergence to the optimal policy. However, follow-up
study of these settings has demonstrated that they exhibit additional
structure which is critical to these results, causing these policy-gradient
algorithms to act like policy improvement algorithms [BR24]. Our result is the
first to handle an infinite state-space setting without the specialized
structure of these prior results.

Key to our result are novel bounds on the relative value function, building
off of our drift assumption for the policy space. This drift assumption is
reasonable in a queueing setting, as we discuss in section 3.2 [SY13]. Prior
drift-based bounds on the relative-value function exist [GM96], but are
policy-dependent. In contrast, we prove policy-independent bounds on the
relative-value function using reasonable assumptions on the MDP structure,
which are motivated by the structure of MDPs in queueing networks. Our policy-
independent bounds are critical to implement our state-dependent learning
rates, allowing us to generalize the NPG algorithm to the infinite-state
setting.

Several works have studied applications of reinforcement learning to queueing
problems, including policy-gradient-based algorithms. In [SXX20], discounted
reward reinforcement learning is applied to queue length control. Their
analysis assumes bounded single-step rewards and the presence of an oracle
capable of generating samples from the MDP to learn the value functions. This
combination of discounted rewards and bounded single-step rewards provides a
uniform, state-independent upper bound on the value function. However, this
does not apply to our analysis since the single-step cost, represented by the
current queue length, is unbounded and our objective is the infinite horizon
average cost.

In [LXM19], a model-based approach addresses the challenge of a countable
state space by using thresholding. That is, the optimal policy is learned for
a finite subset of low-cost states using model-based methods, while a fixed
stabilizing policy is applied outside this finite set. The optimality gap is
then determined based on the size of this finite set. Contrary to their
approach, our assumptions accommodate a soft thresholding, allowing for the
learning of better policies beyond a finite set. Additionally, our analysis is
model-free.

Several results focus on the problem of learning the relative value function
from samples, including variance reduction techniques [DG22] and sample
augmentation techniques [WLWY23]. Our results complement these results, as we
focus on the function approximation step, and prove results on overall
algorithmic performance, while these results focus on the policy evaluation
step, and empirically demonstrate performance improvements. Dai and Gluzman
[DG22] in particular empirically demonstrate that with variance reduction
techniques in use, policy gradient algorithms with function approximation
rapidly converge to the optimal policy in an infinite-state-space queueing
setting. Our results theoretically justify this empirical observation.

##  2 Model and Preliminaries

We consider the class of Markov Decision Processes (MDP) with countably
infinite states $\mathcal{S}$ (possibly $\mathbb{Z}^{K}_{+}$), finite actions
$\mathcal{A}$ and the infinite horizon average cost objective. Particularly,
we consider the context of queuing systems where each state of the MDP is
denoted by a vector $\mathbf{q}\in\mathcal{S}$. Each element of the vector
$\mathbf{q}$ indicates the queue length for a specific type of job, with a
total of $K$ different job types. We assume the buffer associated with the
queue is of infinite capacity and therefore we obtain a state space whose
cardinality is countably infinite. We consider a randomized class of policies
$\Pi,$ where a policy $\pi\in\Pi$ maps each state to a probability vector over
actions $\mathcal{A}$, that is, $\pi:\mathcal{S}\to\Delta\mathcal{A}$. The
actions in the context of queues denote which particular job type to service,
if any.

The underlying probability transition kernel is denoted by
$\mathbb{P}:\mathcal{S}\to\mathcal{S}$ and the transition kernel corresponding
to any policy $\pi$ is denoted by $\mathbb{P}_{\pi},$ where
$\mathbb{P}_{\pi}(\mathbf{q^{\prime}}|\mathbf{q})=\sum_{a\in\mathcal{A}}\pi(a|\mathbf{q})\mathbb{P}(\mathbf{q^{\prime}}|\mathbf{q},a)$
is the probability of transitioning from $\mathbf{q}$ to $\mathbf{q^{\prime}}$
under policy $\pi$ in a single step. Associated with each state $\mathbf{q}$
is a single step cost $c(\mathbf{q})$, which in the context of queues is the
total queue length, that is, $c(\mathbf{q})=\|\mathbf{q}\|_{1}$. Since we
consider unbounded queue lengths in this formulation, the single step costs
also are unbounded. In this scenario, it is important to note that the costs
incurred in a single step do not depend on the action taken or the policy
being used at that moment. This is because the policy only influences the
queue length in the next time step, not the current one. The infinite horizon
average reward associated with a policy $\pi$ is denoted by $J_{\pi}$, and is
defined as follows:

$J_{\pi}=\lim_{T\to\infty}\frac{\mathbb{E}_{\pi}\left[\sum_{t=0}^{T-1}\|\mathbf{q}_{t}\|_{1}\right]}{T}$
(1)

where the expectation is taken with respect to the trajectory generated by
$\mathbb{P}_{\pi}.$ If the transition kernel $\mathbb{P}_{\pi}$ admits a
unique stationary distribution $d_{\pi}$ over the state space, then the
infinite horizon average reward can be reformulated as
$J_{\pi}=\sum_{\mathbf{q}\in\mathcal{S}}d_{\pi}(\mathbf{q})\|\mathbf{q}\|_{1}$.
If a function $V_{\pi}:\mathcal{S}\to\mathbb{R}$ associated with a policy
$\pi$ is absolutely integrable, that is it satisfies:

$\sum_{\mathbf{q^{\prime}}\in\mathcal{S}}\mathbb{P}_{\pi}(\mathbf{q^{\prime}}|\mathbf{q})|V_{\pi}(\mathbf{q^{\prime}})|<\infty$
(2)

and is a solution to the Poisson’s equation:

$J_{\pi}+V_{\pi}(\mathbf{q})=\|\mathbf{q}\|_{1}+\sum_{\mathbf{q^{\prime}}\in\mathcal{S}}\mathbb{P}_{\pi}(\mathbf{q^{\prime}}|\mathbf{q})V_{\pi}(\mathbf{q^{\prime}}),$
(3)

then $V_{\pi}(\mathbf{q})$ is defined as the relative value function
associated with the policy $\pi$ [GI24]. Since $V_{\pi}(\mathbf{q})$ is unique
upto an additive constant, any function of the form $V_{\pi}(\mathbf{q})+C$,
where $C$ is a constant is also a solution to the Poisson’s equation. However,
the most frequently used representation of the value function, which is also
unique, is given by:

$V_{\pi}(\mathbf{q})=\mathbb{E}_{\pi}\left[\sum_{i=0}^{\tau^{\pi}_{0}-1}\left(\|\mathbf{q}_{i}\|_{1}-J_{\pi}\right)\Bigg{|}\mathbf{q}_{0}=\mathbf{q}\right]$
(4)

where $\tau^{\pi}_{0}$ represents the first time to hit state $\mathbf{0}$
starting from any state $\mathbf{q}$ under policy $\pi.$ Hence, from
definition it follows that $V_{\pi}(\mathbf{0})=0.$ The value function
associated with a state $\mathbf{q}$ represents the expected difference
between the total cost and the expected total cost obtained under policy $\pi$
when starting from state $\mathbf{q}$ until state $\mathbf{0}$ is reached for
the first time. The relative state action value function $Q_{\pi}(\mathbf{q})$
is analogously defined as the solution to the following equation:

$J_{\pi}+Q_{\pi}(\mathbf{q},a)=\|\mathbf{q}\|_{1}+\sum_{\mathbf{q^{\prime}}\in\mathcal{S}}\mathbb{P}(\mathbf{q^{\prime}}|\mathbf{q},a)V_{\pi}(\mathbf{q^{\prime}})$
(5)

The state action value function $Q_{\pi}(\mathbf{q},a)$ has a similar
interpretation as state value function $V_{\pi}(\mathbf{q})$ except the action
enacted at time $0$ is $a$ and not dictated by the policy $\pi.$

The goal of reinforcement learning is to determine the policy $\pi^{*}\in\Pi,$
such that the infinite horizon average cost is minimized. That is, to solve
for

$J^{*}=\min_{\pi\in\Pi}J_{\pi}$ (6)

where $\pi^{*}=\operatorname*{arg\,min}_{\pi\in\Pi}J_{\pi}$. The focus of this
paper is to analyze the performance of Natural Policy Gradient in determining
the optimal policy that minimizes the infinite horizon average reward.

###  2.1 Natural Policy Gradient Algorithm

Natural Policy Gradient algorithm is related to the mirror descent algorithm
in the context of tabular policies. The objective of mirror descent involves
minimizing the first order approximation of the average cost with
$\mathsf{KL}$ regularizer. In the context of tabular policies, the NPG policy
update is of the form below:

$\pi_{i+1}(a|\mathbf{q})\propto\pi_{i}(a|\mathbf{q})\exp{\left(-\eta_{\mathbf{q}}\widehat{Q}_{\pi_{i}}(\mathbf{q},a)\right)}$
(7)

where $\eta_{\mathbf{q}}>0$ is the state dependent step size. Since in the
limit as $\eta_{\mathbf{q}}\to\infty$, the above update picks the action with
the lowest state action value function, NPG is also considered to be a form of
soft policy iteration. The magnitude of $\eta_{\mathbf{q}}$ determines the
greediness of the policy.

With the state space being infinitely large, a common approach to evaluate
value functions is through linear function approximations. This simplifies the
complexity from infinity to the dimension of the parameter vector, although
with some loss in accuracy. A popular method involves using neural networks,
where the weights act as the parameter vector and the network itself serves as
the feature space. For each policy $\pi$, the estimate $\widehat{Q}_{\pi}$ of
the state-action value function $Q_{\pi}$ is then computed using
overparametrized neural networks and samples gathered from trajectories under
policy $\pi$. For further details, please see Subsection 4.1.

Require : $T$, $\pi_{0}\in\Delta\mathcal{A}$

1 for  _$i=0,1,2,3,\cdots,T-1$_ do

2 Generate trajectory
$\left\\{\mathbf{q}_{0},a_{0},\mathbf{q}_{1},a_{1},\ldots,\mathbf{q}_{n},a_{n}\right\\}$
using policy $\pi_{i}$. Evaluate $\widehat{Q}_{\pi_{i}}$ using neural network
linear function approximation.

3 Update policy as:

4
$\pi_{i+1}(a|\mathbf{q})=\frac{\pi_{i}(a|\mathbf{q})\exp{\left(-\eta_{\mathbf{q}}\widehat{Q}_{\pi_{i}}(\mathbf{q},a)\right)}}{\sum_{a^{\prime}\in\mathcal{A}}\pi_{i}(a^{\prime}|\mathbf{q})\exp{\left(-\eta_{\mathbf{q}}\widehat{Q}_{\pi_{i}}(\mathbf{q},a^{\prime})\right)}}$
(8)

5 end for

return $\pi_{T}$

Algorithm 1 Natural Policy Gradient Algorithm

To aide our analysis, we make the following assumptions, which are typically
met by queuing systems. The irreducibility of the Markov chain under any
policy is a standard assumption in reinforcement learning. This ensures
adequate exploration and visitation of all state-action pairs, which is
crucial for learning policies with reasonable confidence.

######  Assumption 2.1.

For all policies $\pi\in\Pi$ the induced Markov Chain $\mathbb{P}_{\pi}$ is
irreducible.

In countable state Markov chains, irreducibility together with positive
recurrence ensures the existence of the stationary distribution which aides in
the proof of convergence of NPG. The next assumption ensures that the
underlying Markov chain is positive recurrent (see Lemma A.2.

######  Assumption 2.2.

There exist constants $\epsilon,c$ independent of policy $\pi$ such that for
every policy $\pi\in\Pi$ the following drift equation is satisfied:

$\mathbb{E}_{\pi}\left[\|\mathbf{q}_{k+1}\|^{2}-\|\mathbf{q}_{k}\|^{2}|\mathbf{q}_{k}=\mathbf{q}\right]\leq-\epsilon\|\mathbf{q}\|_{1}+c$
(9)

In addition to ensuring positive recurrence, the drift equation (9) gives a
uniform bound on the average cost of any policy. It turns out that we also
need policy independent bounds on the value function, which is ensured by our
next assumption on a finite set of low cost states. More precisely, consider
the finite set $B$ defined as:

$B:=\left\\{\mathbf{q}\in\mathcal{S}:\|\mathbf{q}\|_{1}\leq\frac{2c}{\epsilon}\right\\}.$
(10)

Clearly, $B$ is a set of low cost states and is finite since $c,\epsilon$ are
finite quantities.

######  Assumption 2.3.

Structural Assumptions on the underlying Markov Decision Process:

  * •

We assume that there exist constants $x_{B}$ and $p_{B}$, independent of
policy $\pi$, such that

$\mathbb{P}_{\pi}^{x_{B}}\left(\mathbf{q^{\prime}}|\mathbf{q}\right)\geq
p_{B}\qquad\qquad\forall\mathbf{q}\in B,\forall\mathbf{q^{\prime}}\in
B,\forall\pi\in\Pi$ (11)

where $\mathbb{P}_{\pi}^{x_{B}}$ is the $x_{B}$-step probability transition
matrix.

  * •

We assume that the number of jobs that can arrive and the number of jobs that
can depart in a single time step are both bounded.

Equation (11) indicates that any state $\mathbf{q}\in B$ can be reached from
any state $\mathbf{q^{\prime}}\in B$ in utmost $x_{B}$ transitions with
atleast $p_{B}$ probability under any policy $\pi\in\Pi$.

Bounded arrivals and departures ensures that the length of the queues in a
single transition under any policy $\pi$ cannot grow unbounded. That is, there
exists constants $c_{1},c_{2}$ independent of policy $\pi$ such that,

$\mathbb{P}_{\pi}\left(\mathbf{q^{\prime}}|\mathbf{q}\right)>0\implies\|\mathbf{q^{\prime}}\|^{2}\leq
c_{1}\|\mathbf{q}\|^{2}+c_{2}\qquad\forall\pi\in\Pi$ (12)

##  3 Main Result and Discussion

We now present the main result, which is the performance of NPG in the context
of infinite state MDPs within the learning framework. We then contextualize
Assumptions 2.1, 2.2 and 2.3 and elaborate on how they can be satisfied in the
context of queuing systems.

###  3.1 Main Result

######  Theorem 3.1.

Consider the sequence of policies $\pi_{1},\pi_{2},\ldots,\pi_{T}$ obtained
from Algorithm 1 with a state-dependent step size
$\eta_{\mathbf{q}}=\sqrt{\frac{8\log|\mathcal{A}|}{T}}\frac{1}{M_{\mathbf{q}}}$,
where $M_{\mathbf{q}}$ is quadratic in $\mathbf{q}$. Let $J_{\pi_{k}}$ be the
average cost associated with policy $\pi_{k}$ and let $J_{*}$ be the minimum
average cost across policy class $\Pi$. Let $\widehat{Q}_{\pi_{k}}$ be an
estimate of state action value function $Q_{\pi_{k}}$ associated with policy
such that with probability at least $1-\frac{\delta}{2T}$ it is true that,

$\left\|Q_{\pi}(\mathbf{q},a)-\widehat{Q}_{\pi}(\mathbf{q},a)\right\|\leq\kappa\|\mathbf{q}\|^{2}\qquad\forall\mathbf{q}\in\mathcal{S},\pi\in\Pi$
(13)

Then, under Assumptions 2.1, 2.2 and 2.3, there exist constants
$c^{\prime},c^{\prime\prime}$ not depending on $T$ or
$\pi_{1},\pi_{2},\ldots,\pi_{T}$ such that with probability at least
$1-\delta$:

$\sum_{k=1}^{T}\left(J_{\pi_{k}}-J_{*}\right)\leq
c^{\prime}\sqrt{T}+c^{\prime\prime}T$ (14)

where
$c^{\prime}=\left(2\kappa+\frac{2c_{1}}{\epsilon}\right)\mathbb{E}_{\mathbf{q}\sim
d^{\pi^{*}}}\|\mathbf{q}\|^{2}\sqrt{\frac{\log|\mathcal{A}|}{2}}+\sqrt{\frac{\log|\mathcal{A}|}{2}}\left(\frac{2c_{2}}{\epsilon}+\frac{x_{B}c}{\epsilon}\left(1+\frac{2}{p_{B}}+\frac{1}{p_{B}^{2}}+\frac{1}{p_{B}^{3}}\right)\right)$
and $c^{\prime\prime}=\kappa\mathbb{E}_{\mathbf{q}\sim
d^{\pi^{*}}}\|\mathbf{q}\|^{2}.$

###### Proof.

The proof is in Appendix A.3. An outline is provided in Section 4.

###  3.2 Discussion on Assumptions: Applications in Stochastic Networks

Assumptions 2.1 and 2.3 are easily satisfied in queueing systems under mild
conditions on the arrival and service process that are fairly standard in
queuing literature [SY13]. For instance, suppose that the policy class allows
for a non-zero probability of both zero job arrivals and zero job departures.
Under such a policy class, it is possible to transition from any state
$\mathbf{q}$ to the state $\mathbf{0}$ and from the state $\mathbf{0}$ to any
state $\mathbf{q}$, ensuring irreducibility. Similarly, within a finite set
$B$, it is possible to establish uniform lower bounds for transitioning from
any state to any other state within the set under any policy, thereby
satisfying both assumptions.

In a large class of queueing systems, the MaxWeight policy is known to ensure
stability, i.e., positive recurrence (see Chapter 4, [SY13]). Assumption 2.2
is inspired by the so-called MaxWeight policy, which is known to satisfy the
drift equation below:

$\mathbb{E}_{\pi_{\mathsf{MW}}}\left[\|\mathbf{q}_{k+1}\|^{2}-\|\mathbf{q}_{k}\|^{2}|\mathbf{q}_{k}=\mathbf{q}\right]\leq-\epsilon\|\mathbf{q}\|_{1}+d_{1}$
(15)

where the expectation is taken with respect to $\pi_{\mathsf{MW}}$ and
$\epsilon,d_{1}$ are some positive constants independent of policy. Assumption
2.2 is designed so that we explore a family of randomized policies that
inherit stability from MaxWeight, while also enabling us to learn policies
that outperform MaxWeight.

In particular, we consider policies obtained by using a combination of
MaxWeight and arbitrary randomized acations by transforming the underlying MDP
as follows. Let the policies obtained from update Equation 8 be referred to as
$\pi_{\mathsf{NPG}}$. Modify the underlying MDP such that the probability
transition kernel corresponds to a policy $\pi$ defined below:

$\pi(a|\mathbf{q})=\begin{cases}\pi_{\mathsf{NPG}}(a|\mathbf{q}),&\text{w.p.}\quad\min\left(1,\frac{1}{\lambda\|\mathbf{q}\|}\right)\\\
\pi_{\mathsf{MW}}(a|\mathbf{q}),&\text{w.p.}\quad
1-\min\left(1,\frac{1}{\lambda\|\mathbf{q}\|}\right)\end{cases}$ (16)

where $\lambda>0$ is a fixed parameter with a very small positive value.

As the queue length grows larger, the above transformed MDP enacts the Max-
Weight policy with greater probability at higher queue lengths. The value of
$\lambda$ decides the threshold at which Max-Weight policy starts influencing
the transition dynamics. Once queue lengths exceed $\frac{1}{\lambda}$, this
soft thresholding compromises some optimality to prioritize stability. This
differs from the hard thresholding approach taken in [LXM19].

We will now illustrate that this family of soft-thresholded policies satisfy
Assumption 2.2. First note that from Assumption 2.3 and Equation 12 it is easy
to show that $\pi_{\mathsf{NPG}}$ satisfies

$\mathbb{E}_{\pi_{\mathsf{NPG}}}\left[\|\mathbf{q}_{k+1}\|^{2}-\|\mathbf{q}_{k}\|^{2}|\mathbf{q}_{k}=\mathbf{q}\right]\leq
d_{2}\|\mathbf{q}\|_{1}+d_{3}$ (17)

where the expectation is taken with respect to $\pi_{\mathsf{NPG}}$ and
$d_{2},d_{3}$ are some positive constants independent of policy. Thus the
drift equation corresponding to policy $\pi$ in Equation 16 is as follows:

$\displaystyle\mathbb{E}_{\pi}$
$\displaystyle\left[\|\mathbf{q}_{k+1}\|^{2}-\|\mathbf{q}_{k}\|^{2}|\mathbf{q}_{k}=\mathbf{q}\right]\leq$
$\displaystyle\begin{cases}\frac{d_{2}}{\lambda}+d_{3},&\|\mathbf{q}\|_{1}\leq\frac{1}{\lambda}\\\
\frac{1}{\lambda\|\mathbf{q}\|_{1}}\left(d_{2}\|\mathbf{q}\|_{1}+d_{3}\right)+\left(1-\frac{1}{\lambda\|\mathbf{q}\|_{1}}\right)\left(-\epsilon\|\mathbf{q}\|_{1}+d_{1}\right),&\|\mathbf{q}\|_{1}>\frac{1}{\lambda}\end{cases}$
(18)

Combining the cases in Equations 18, we obtain the following drift relation
for policy $\pi$ for all $\mathbf{q}\in\mathcal{S}$:

$\mathbb{E}_{\pi}\left[\|\mathbf{q}_{k+1}\|^{2}-\|\mathbf{q}_{k}\|^{2}|\mathbf{q}_{k}=\mathbf{q}\right]\leq-\epsilon\|\mathbf{q}\|_{1}+D$
(19)

where $D$ is a constant independent of policy $\pi$ but is a function of
constants $d_{1},d_{2},d_{3},\epsilon$ and $\lambda$. Note that the constant
$\epsilon$ remains the same in both (15) and (19). This constitutes one such
class of policies that satisfies the required the drift equation (9) for our
analysis.

##  4 Proof outline and Key Insights

The difference in average cost associated with a policy $\pi$ and the optimal
average cost is linked to the $Q_{\pi}$ function through the performance
difference lemma ([Cao99]) as below:

$J_{\pi}-J^{*}=\mathbb{E}_{\mathbf{q}\sim
d_{\pi^{*}}}\left[Q_{\pi}\left(\mathbf{q},\pi(\mathbf{q})\right)-Q_{\pi}\left(\mathbf{q},\pi^{*}(\mathbf{q})\right)\right].$
(20)

Hence, the regret in LHS of Equation (14) can be captured in terms of
difference in the state action action $Q_{\pi}$. However, in practise it is
not possible to determine $Q_{\pi}$ exactly since the model might be unknown
or the state space is infinite. Hence, we incorporate the estimates
$\widehat{Q}_{\pi}$ of the value function $Q_{\pi}$. If the estimates satisfy
Equation (13), then from Equation (20) we obtain the following regret
formulation:

$\sum_{k=1}^{T}J_{\pi_{k}}-J^{*}\leq 2\kappa T\mathbb{E}_{\mathbf{q}\sim
d^{\pi^{*}}}\|\mathbf{q}\|^{2}+\underbrace{\mathbb{E}_{\mathbf{q}\sim
d_{\pi^{*}}}\left[\sum_{k=1}^{T}\widehat{Q}_{\pi_{k}}\left(\mathbf{q},\pi^{*}(\mathbf{q})\right)-\widehat{Q}_{\pi_{k}}\left(\mathbf{q},\pi_{k}(\mathbf{q})\right)\right]}_{(a)}$
(21)

The term linear in $T$, i.e., $2\kappa T\mathbb{E}_{\mathbf{q}\sim
d^{\pi^{*}}}\|\mathbf{q}\|^{2}$ is a consequence of function approximation and
is generally unavoidable [AYBB+19].The primary task is to bound $(a)$ in
Equation (21). We approach this in four steps: (i) examining the link between
NPG and prediction through expert advice as highlighted in prior literature,
and identifying challenges specific to our countable state-space model and
cost structure, (ii) deriving policy-independent bounds on the value
functions, i.e., the solution to Poisson’s Equation (3), (iii) accounting for
policy evaluation errors and establishing policy-independent bounds on the
estimates of the value function, and (iv) integrating all these steps to
achieve the final result. We now proceed with the proof outline.

Step 1 (Connection to Weighted Averaging): This step involves connecting
learning within Markov Decision Processes (MDPs) to prediction through expert
advice. This connection was initially identified in [EDKM09] for MDPs and
later extended to the learning setting in [AYBB+19]. We now discuss this
connection in some detail and why need our proof techniques to adapt this
connection to the countable state-space setting. In the framework of
prediction through expert advice, the agent selects an action $a_{t}$ at time
$t$, and the environment responds with a corresponding loss $l_{t}(a_{t})$.
Concurrently, an expert follows a predetermined strategy, which in our context
can be simplified to a single action $a^{*}$ taken at each time step, also
experiencing a loss of $l_{t}(a^{*})$. The agent’s objective is to minimize
the overall loss by considering all it’s past observations when choosing an
action. If the expert opts for a fixed strategy $\pi^{*}$ over the available
actions, the following holds true.

######  Theorem 4.1.

(Section 4.2, Corollary 4.2, [CBL06].) Consider the exponentially weighted
average forecaster problem. Let the set of actions possible at each time step
and each instance be denoted by $\mathcal{A}:=\left\\{1,\ldots,n\right\\}$.
For a fixed instance $s$, let $l_{t}(s,i)$ be the loss associated with action
$i\in\mathcal{A}$ at time $t$ such that for any pair of actions
$i,i^{\prime}\in\mathcal{A}$,

$\left|l_{t}(s,i)-l_{t}(s,i^{\prime})\right|\leq M(s)$ (22)

Consider the action strategy below:

$\pi_{t}(i|s)=\frac{\pi_{t-1}(i|s)\exp{\left(-\eta_{s}l_{t-1}(s,i)\right)}}{\sum_{k=1}^{n}\pi_{t-1}(k|s)\exp{\left(-\eta_{s}l_{t-1}(s,k)\right)}}$
(23)

Then, for any fixed policy $\pi^{*}$, setting $\eta_{s}=\sqrt{\frac{8\log
n}{T}}\frac{1}{M(s)}$ yields the following overall regret corresponding to
instance $s$.

$\sum_{k=1}^{T}\left(l_{k}\left(s,\pi_{k}(s)\right)-l_{k}\left(s,\pi^{*}(s)\right)\right)\leq
M(s)\sqrt{\frac{T\log n}{2}}$ (24)

The NPG algorithm can be interpreted as applying the weighted averaging
algorithm to each state $\mathbf{q}$ in the state space, with the goal of
learning the optimal policy for each state. In this context, the loss function
associated with an action $a$ in state $\mathbf{q}$ at time $k$ is the
estimate $\widehat{Q}_{\pi_{k}}(\mathbf{q},a)$ of the state-action value
function, where the policy in use at time $k$ is $\pi_{k}$. However, as
indicated by Equation (22), the loss
function—$\widehat{Q}_{\pi_{k}}(\mathbf{q},a)$—must be bounded for any given
state $\mathbf{q}$. In finite-dimensional MDPs, a state-independent uniform
bound on the state-action value function is typically assumed [AYBB+19]. This
is due to the fact that the step-size $\eta$ is assumed to be independent of
$s.$ Note that, compared to [EDKM09, AYBB+19], we have made a small, but
critical, change to the best-experts algorithm by allowing the step-size
$\eta$ to be a function of $s.$ When the state-space is countable, the state-
action value function $Q_{\pi}$ cannot be uniformly bounded and hence, a
constant step-size cannot be assumed. With the introduction of a state-
dependent step-size, we can choose a different step-size for each state using
bounds on the solution to Poisson’s equation, i.e., $Q_{\pi}(s,a)$, which
depends on the state, but is uniform over all policies. Obtaining such bounds
is one of the key contributions of the paper.

Step 2 (Value Function Bounds): To establish bounds on Poisson’s Equation 5,
we initially rely on Assumptions 2.1 and 2.2. In dealing with countable state
space MDPs, along with irreducibility, we require the Markov chain to be
positive recurrent for a unique stationary distribution to exist. The drift
equation 9 within Assumption 2.2 ensures the positive recurrence of the
underlying Markov chain. Since $Q_{\pi}$ is related to the state value
function $V_{\pi}$(see Equation 5), we initially constrain $V_{\pi}$ using
Assumptions 2.1 and 2.2. This leads to an upper bound on $V_{\pi}(\mathbf{q})$
for all $\mathbf{q}\in B^{\mathsf{c}}$, where $B$ is defined in Equation 10.

$V_{\pi}(\mathbf{q})\leq\frac{2}{\epsilon}\|\mathbf{q}\|^{2}+\underbrace{\max_{\begin{subarray}{c}\mathbf{q^{\prime}}\in
B\\\ \pi\in\Pi\end{subarray}}V_{\pi}(\mathbf{q^{\prime}})}_{(b)}$ (25)

Recall Equation (22) in the context of weighted expert averaging. The
constraint on the loss function’s bound $\left(M(s)\right)$ must be
independent of time. When applied to the NPG framework, this implies the
necessity of a policy-independent upper bound on the state-action function
$Q_{\pi}$, which, in turn, necessitates a policy-independent bound on the
state value function $V_{\pi}$. For $(b)$ to be well-defined, the drift alone
is insufficient, as indicated in previous studies [GI24, GM96]. Addressing
this is the second challenge in our analysis, which we navigate by introducing
a mild structural Assumption 2.3 commonly satisfied in queuing systems.

These structural assumptions yield a uniform upper bound on the hitting time
of state $\mathbf{0}$ when starting from any point within $B$. This uniform
upper bound on hitting time aids in bounding the state value function
$V_{\pi}$ from below since the drift inequality (9) assists in bounding the
value function $V_{\pi}$ from above alone. As a consequence, we obtain the
following,

$\left|Q_{\pi}(\mathbf{q},a)-Q_{\pi}(\mathbf{q},a^{\prime})\right|\leq
O(\|\mathbf{q}\|^{2})\qquad\forall\pi\in\Pi,\forall
a,a^{\prime}\in\mathcal{A}\ \text{and}\ \forall\mathbf{q}\in\mathcal{S}$ (26)

As a result, we establish policy-independent bounds on the value function
$Q_{\pi}$. While the drift assumption 2.2 played a crucial role in deriving
policy-dependent bounds on the value function $V_{\pi}$, for the purpose of
NPG, we need these bounds to be independent of the policy. The structural
assumption 2.3 eliminates this policy dependence. Consequently, from Equation
5, this translates into policy-independent bounds on $Q_{\pi}$.

Step 3 (Handling Estimation Errors): Since our loss function in the context of
Theorem 4.1 is $\widehat{Q}_{\pi}$, we need uniform bounds on
$\widehat{Q}_{\pi}$. We leverage the bounds on $Q_{\pi}$ obtained in Equation
26 and in conjunction with the evaluation error characterized in Subsection
4.1 Equation 34, we obtain the following:

$\left|\widehat{Q}_{\pi}(\mathbf{q},a)-\widehat{Q}_{\pi}(\mathbf{q},a^{\prime})\right|\leq
O(\|\mathbf{q}\|^{2})\qquad\forall\pi\in\Pi,\forall
a,a^{\prime}\in\mathcal{A}\ \text{and}\ \forall\mathbf{q}\in\mathcal{S}$ (27)

Adapting Equation 22 to the context of context of infinite state NPG, implies
that $M_{\mathbf{q}}=O(\|\mathbf{q}\|^{2})$.

Step 4 (Piecing it all together): The upper bound $M_{\mathbf{q}}$ on
$\widehat{Q}_{\pi}$ in Step 3 is utilized to determine the state dependent
step size as
$\eta_{\mathbf{q}}=\sqrt{\frac{8\log|\mathcal{A}|}{T}}\frac{1}{M_{\mathbf{q}}}$.
With bounds over $\widehat{Q}$ quantified in Equation 27, $(a)$ of Equation
(21) is upper bounded by leveraging the connection to the prediction through
expert advice Theorem 4.1. This yields the final result.

The detailed proof of all steps and the main theorem can be found in Appendix.

###  4.1 Policy Evaluation in Countable State MDPs

It is a well-known fact that neural networks with at least one hidden layer of
sufficient width and a non-linear activation function can approximate any
continuous function on a compact domain arbitrarily well [Cyb89, Fun89,
HSW89]. A potential technique to evaluate value functions associated with
infinite state spaces can be through neural network temporal difference
learning. In order to do so, consider the following transformation to
compactify the domain of the problem. Let the system comprise of $K$ queues
that is, $\mathbf{q}\in\mathbb{R}^{K}_{+}$, where $\mathbb{R}_{+}^{K}$ denotes
the non-negative subspace of $\mathbb{R}^{K}.$ Let $q_{i}$ represent the
number of jobs in the $i^{\text{th}}$ queue. Then define a vector
$\mathbf{x}\in\left[0,1\right]^{K}$ such that the $i^{\text{th}}$ element is
$x_{i}=\frac{1}{1+q_{i}}$. Given a policy $\pi$, consider a linear function
approximation $\widehat{Q}_{\pi}(\mathbf{q},a)$ of the state-action value
function $Q_{\pi}(\mathbf{q},a)$ as below:

$\frac{\widehat{Q}_{\pi}(\mathbf{q},a)}{\|\mathbf{q}\|^{2}}={\theta_{\pi}}^{\top}\phi\left(\mathbf{x(q)},a\right)$
(28)

where the feature vector $\phi$ is defined as below,

$\phi\left(\mathbf{x(q)},a\right)=\begin{bmatrix}\mathbb{I}_{w_{1}^{\top}\left(\mathbf{x(q)},a\right)\geq
0}\ \left(\mathbf{x(q)},a\right)\\\ \vdots\\\
\mathbb{I}_{w_{m}^{\top}\left(\mathbf{x(q)},a\right)\geq 0}\
\left(\mathbf{x(q)},a\right)\end{bmatrix}.$ (29)

Here, $w_{i}\sim\mathcal{N}(0,I)$ and $I\in\mathbb{R}^{(K+1)\times(K+1)}$ is
the identity matrix. This linearized model is well-studied approximation to a
neural network and is called the Neural Tangent kernel (NTK) approximation;
see [JT19], for example. We will not discuss the merits of the NTK
approximation here since that is irrelevant to our analysis, but we only
introduce the NTK approximation to discuss we why we chose our model for
function approximation. In the NTK approximation, $w_{i}\in\mathbb{R}^{K+1}$
is random initialization which chooses a random set of features. Each feature
vector $\phi\left(\mathbf{x(q)},a\right)$ is of length ${m|\mathcal{A}|K}$,
where $m$ represents the width of the hidden layer in the neural network.
Finally, $\theta^{*}_{\pi}$ represents the optimal parameter vector, i.e., the
parameter that best estimates $Q_{\pi}(\mathbf{q},a).$

The state action value function $Q_{\pi}(\mathbf{q},a)$ can be approximated
arbitrarily well if $Q_{\pi}$ is a continuous function. This is indeed the
case for some simple contexts such as the M/M/1 queue, where the value
function is a quadratic function in queue length ([Mey08]). More generally,
Equation (26) indicates that the $Q_{\pi}(\mathbf{q},a)$ can be upper bounded
by a quadratic function. Therefore, under the assumption that $Q_{\pi}$ is
continuous, the learning error due to policy evaluation using the neural
network can be characterized as follows:

$\displaystyle\|Q_{\pi}(\mathbf{q},a)-\widehat{Q}_{\pi}(\mathbf{q},a)\|$
$\displaystyle=\|Q_{\pi}(\mathbf{q},a)-{\theta_{\pi}}^{\top}\phi\left(\mathbf{x(q)},a\right){\|\mathbf{q}\|^{2}}\|$
(30)
$\displaystyle\leq\left\|Q_{\pi}(\mathbf{q},a)-{\theta^{*}_{\pi}}^{\top}\phi\left(\mathbf{x(q)},a\right){\|\mathbf{q}\|^{2}}\right\|$
(31)
$\displaystyle+\left\|{\theta^{*}_{\pi}}^{\top}\phi\left(\mathbf{x(q)},a\right){\|\mathbf{q}\|^{2}}-{\theta_{\pi}}^{\top}\phi\left(\mathbf{x(q)},a\right){\|\mathbf{q}\|^{2}}\right\|$
(32)

The function approximation error is captured in Equation (31) as follows:

$\left\|Q_{\pi}(\mathbf{q},a)-{\theta^{*}_{\pi}}^{\top}\phi\left(\mathbf{x(q)},a\right){\|\mathbf{q}\|^{2}}\right\|=\left\|\frac{Q_{\pi}(\mathbf{q},a)}{\|\mathbf{q}\|^{2}}-{\theta^{*}_{\pi}}^{\top}\phi\left(\mathbf{x(q)},a\right)\right\|{\|\mathbf{q}\|^{2}}\leq\kappa_{1}(m){\|\mathbf{q}\|^{2}}$
(33)

where $\kappa(m)$ is a constant that is independent of the underlying policy
but depends on the width of the hidden layer. In fact, it is shown in [SS21]
that when approximating polynomials, as $m\to\infty$, $\kappa_{1}(m)\to 0$.
The temporal difference (TD) learning error is captured in Equation (32) and
is a function of the number of samples available and can be quantified as
$\kappa_{2}\|\mathbf{q}\|^{2}$ with high probability. And thus, with high
probability, the overall state dependent error can be quantified as follows:

$\|Q_{\pi}(\mathbf{q},a)-\widehat{Q}_{\pi}(\mathbf{q},a)\|\leq\kappa\|\mathbf{q}\|^{2}$
(34)

where $\kappa=\kappa_{1}(m)+\kappa_{2}$.

## References

  * [AKLM21] Alekh Agarwal, Sham M. Kakade, Jason D. Lee, and Gaurav Mahajan.  On the theory of policy gradient methods: Optimality, approximation, and distribution shift.  J. Mach. Learn. Res., 22(1), jan 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.
  * [BR24] Jalaj Bhandari and Daniel Russo.  Global optimality guarantees for policy gradient methods.  Operations Research, 2024.
  * [Bré13] Pierre Brémaud.  Markov chains: Gibbs fields, Monte Carlo simulation, and queues, volume 31.  Springer Science & Business Media, 2013.
  * [Cao99] Xi-Ren Cao.  Single sample path-based optimization of markov chains.  Journal of optimization theory and applications, 100:527–548, 1999.
  * [CBL06] Nicolo Cesa-Bianchi and Gábor Lugosi.  Prediction, learning, and games.  Cambridge university press, 2006.
  * [Cyb89] George Cybenko.  Approximation by superpositions of a sigmoidal function.  Mathematics of control, signals and systems, 2(4):303–314, 1989.
  * [DG22] J. G. Dai and Mark Gluzman.  Queueing network controls via deep reinforcement learning.  Stochastic Systems, 12(1):30–67, 2022.
  * [EDKM09] Eyal Even-Dar, Sham M Kakade, and Yishay Mansour.  Online markov decision processes.  Mathematics of Operations Research, 34(3):726–736, 2009.
  * [ES12] Atilla Eryilmaz and R. Srikant.  Asymptotically tight steady-state queue length bounds implied by drift conditions.  Queueing Systems, 72:311–359, 2012.
  * [FGKM18] Maryam Fazel, Rong Ge, Sham Kakade, and Mehran Mesbahi.  Global convergence of policy gradient methods for the linear quadratic regulator.  In International conference on machine learning, pages 1467–1476. PMLR, 2018.
  * [Fun89] Ken-Ichi Funahashi.  On the approximate realization of continuous mappings by neural networks.  Neural networks, 2(3):183–192, 1989.
  * [GI24] Peter W Glynn and Alex Infanger.  Solution representations for poisson’s equation, martingale structure, and the markov chain central limit theorem.  Stochastic Systems, 14(1):47–68, 2024.
  * [GM96] Peter W Glynn and Sean P Meyn.  A liapounov bound for solutions of the poisson equation.  The Annals of Probability, pages 916–931, 1996.
  * [GSP19] Matthieu Geist, Bruno Scherrer, and Olivier Pietquin.  A theory of regularized Markov decision processes.  In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pages 2160–2169. PMLR, 09–15 Jun 2019.
  * [Haj82] Bruce Hajek.  Hitting-time and occupation-time bounds implied by drift analysis with applications.  Advances in Applied probability, 14(3):502–525, 1982.
  * [HSW89] Kurt Hornik, Maxwell Stinchcombe, and Halbert White.  Multilayer feedforward networks are universal approximators.  Neural networks, 2(5):359–366, 1989.
  * [JT19] Ziwei Ji and Matus Telgarsky.  Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks.  arXiv preprint arXiv:1909.12292, 2019.
  * [Kak01] Sham M Kakade.  A natural policy gradient.  Advances in neural information processing systems, 14, 2001.
  * [KT08] Sumit Kunnumkal and Huseyin Topaloglu.  Using stochastic approximation methods to compute optimal base-stock levels in inventory control problems.  Operations Research, 56(3):646–664, 2008.
  * [LG08] John DC Little and Stephen C Graves.  Little’s law.  Building intuition: insights from basic operations management models and principles, pages 81–100, 2008.
  * [LXM19] Bai Liu, Qiaomin Xie, and Eytan Modiano.  Reinforcement learning for optimal control of queueing systems.  In 2019 57th annual allerton conference on communication, control, and computing (allerton), pages 663–670. IEEE, 2019.
  * [Mey08] Sean Meyn.  Control techniques for complex networks.  Cambridge University Press, 2008.
  * [MMS23] Yashaswini Murthy, Mehrdad Moharrami, and R Srikant.  Performance bounds for policy-based average reward reinforcement learning algorithms.  Advances in Neural Information Processing Systems, 36:19386–19396, 2023.
  * [MS16] Siva Theja Maguluri and R Srikant.  Heavy traffic queue length behavior in a switch under the maxweight algorithm.  Stochastic Systems, 6(1):211–250, 2016.
  * [MS23] Yashaswini Murthy and R Srikant.  On the convergence of natural policy gradient and mirror descent-like policy methods for average-reward mdps.  In 2023 62nd IEEE Conference on Decision and Control (CDC), pages 1979–1984. IEEE, 2023.
  * [MSV+19] Hongzi Mao, Malte Schwarzkopf, Shaileshh Bojja Venkatakrishnan, Zili Meng, and Mohammad Alizadeh.  Learning scheduling algorithms for data processing clusters.  In Proceedings of the ACM special interest group on data communication, pages 270–288. Association for Computing Machinery, 2019.
  * [MT92] Sean P Meyn and Richard L Tweedie.  Stability of markovian processes i: Criteria for discrete-time chains.  Advances in Applied Probability, 24(3):542–574, 1992.
  * [ÖW20] Erhun Özkan and Amy R Ward.  Dynamic matching for real-time ride sharing.  Stochastic Systems, 10(1):29–70, 2020.
  * [SS21] Siddhartha Satpathi and R. Srikant.  The dynamics of gradient descent for overparametrized neural networks.  In Learning for Dynamics and Control, pages 373–384. PMLR, 2021.
  * [SXX20] Devavrat Shah, Qiaomin Xie, and Zhi Xu.  Stable reinforcement learning with unbounded state space.  arXiv preprint arXiv:2006.04353, 2020.
  * [SY13] R. Srikant and Lei Ying.  Communication networks: an optimization, control, and stochastic networks perspective.  Cambridge University Press, 2013.
  * [VBMW23] Sushil Mahavir Varma, Pornpawee Bumpensanti, Siva Theja Maguluri, and He Wang.  Dynamic pricing and matching for two-sided queues.  Operations Research, 71(1):83–100, 2023.
  * [WLWY23] Honghao Wei, Xin Liu, Weina Wang, and Lei Ying.  Sample efficient reinforcement learning in mixed systems through augmented samples and its applications to queueing networks.  NeurIPS, 2023.

##  Appendix A Appendix / supplemental material

The proof of Step 1 can be found in Chapter 4 of [CBL06].

###  A.1 Proof of Step 2

The following lemmas are a consequence of Assumptions 2.1 and 2.2.

######  Lemma A.1.

Given Assumptions 2.1 and 2.2, there exists a positive constant $\alpha$ such
that $\mathbb{E}_{\pi}[e^{\alpha\|q\|}]<\infty$. Consequently, for any $p\geq
1$, there exists a constant $\beta_{p}>0$ such that for all policies $\pi$, it
is true that $\mathbb{E}_{\pi}\left[\|q\|^{p}\right]<\beta_{p}$. [Haj82,
ES12].

This lemma ensures that for all policies $\pi\in\Pi$, all moments of
$||\mathbf{q}||$ exist. The second moment is particularly important since
final regret depends on $\mathbb{E}_{\mathbf{q}\sim
d^{\pi^{*}}}\left[\|\mathbf{q}\|^{2}\right]$.

######  Lemma A.2.

Let $\mathbb{P}_{\pi}$ be an irreducible transition matrix on the countable
state space $\mathcal{S}.$ Suppose that (9) is satisfied. Then the
corresponding homogenous Markov Chain is positive recurrent. Consequently, the
stationary distribution $d_{\pi}$ corresponding to $\mathbb{P}_{\pi}$ exists
and is unique [Bré13].

Lemmas A.1 and A.2 are utilized to establish a policy independent upper bound
on the infinite-horizon average-cost. Such a bound is indicative of stable
policies since the negative drift in Equation (9) prevents the average cost
from being unbounded. Thus it is possible to show that all policies that
satisfy the drift equation 9, have an uniform upper bound on the expected
total queue length. This is proven in the Lemma below.

######  Lemma A.3.

Given Assumptions 2.1 and 2.2, for all policies $\pi\in\Pi$ it is true that,

$J_{\pi}\leq\frac{c}{\epsilon}$ (35)

where $J_{\pi}=\mathbb{E}_{\pi}\left[\|\mathbf{q}\|_{1}\right]$ is the average
cost associated with policy $\pi$ and constants $c,\epsilon$ are the drift
parameters in Equation 9.

###### Proof.

From Assumption 2.2, it follows that for any policy $\pi\in\Pi$, the following
drift inequality is satisfied,

$\mathbb{E}_{\pi}\left[\|\mathbf{q}_{k+1}\|^{2}-\|\mathbf{q}_{k}\|^{2}|\mathbf{q}_{k}=\mathbf{q}\right]\leq-\epsilon\|\mathbf{q}\|_{1}+c.$
(36)

Recall that $d_{\pi}$ represents the stationary measure associated with policy
$\pi$. Since we assume that all policies induce irreducible Markov chains and
from Lemma A.2, we know that the drift equation (9) implies positive
recurrence of the Markov chain, $d_{\pi}$ exists and is unique. Since
$d_{\pi}\geq 0$, consider the following weighted drift inequality:

$\sum_{\mathbf{q}\in\mathcal{S}}d_{\pi}(\mathbf{q})\left[\mathbb{E}_{\pi}\left[\|\mathbf{q}_{k+1}\|^{2}-\|\mathbf{q}_{k}\|^{2}|\mathbf{q}_{k}=\mathbf{q}\right]\right]\leq-\epsilon\sum_{\mathbf{q}\in\mathcal{S}}d_{\pi}(\mathbf{q})\|\mathbf{q}\|_{1}+c$
(37)

From Lemma A.1, recall that the second moment of $\mathbf{q}$ is defined and
exists for all policies $\pi\in\Pi.$ Hence the left hand summation in Equation
37 is well defined. Since the expectation is taken with respect to
$\mathbb{P}_{\pi}$ and since $d_{\pi}\mathbb{P}_{\pi}=d_{\pi}$, the left hand
summation in Equation 37 is 0. Hence the expected drift in stationarity is
zero.

From Lemma A.1, we know that $J_{\pi}$ exists and can be defined as
$J_{\pi}=\sum_{\mathbf{q}\in\mathcal{S}}d_{\pi}(\mathbf{q})\left(\|\mathbf{q}\|_{1}\right)$.
We thus obtain the following:

$\displaystyle 0$ $\displaystyle\leq-\epsilon J_{\pi}+c$ (38)

Therefore,

$\displaystyle J_{\pi}\leq\frac{c}{\epsilon}$ (39)

Equation 39 is true for all policies $\pi$. Hence, the average cost is
uniformly upper bounded by $\frac{c}{\epsilon}.$

Since $Q_{\pi}$ is related to $V_{\pi}$ through Equation (5), in order to
bound $Q_{\pi}$, we first bound $V_{\pi}$. We now derive an upper bound on the
value function $V_{\pi}$ leveraging the drift equation 9 and the uniform upper
bound on $J_{\pi}$ in Equation 39. First we leverage Assumptions 2.1 and 2.2
to establish policy dependent upper bounds on the value function as elaborated
in the following subsection.

####  A.1.1 Policy Dependent upper bound on State Value Function

######  Lemma A.4.

Consider a set $B$ defined in Equation 10. Let $V_{\pi}(\mathbf{q})$ represent
the state value function associated with state $\mathbf{q}\in\mathcal{S}$ and
policy $\pi\in\Pi$. Under Assumptions 2.1 and 2.2, for all $\mathbf{q}\in
B^{\mathsf{c}}$ and for all policies $\pi\in\Pi$, it is true that,

$V_{\pi}(\mathbf{q})\leq\frac{2}{\epsilon}\|\mathbf{q}\|^{2}+\max_{\begin{subarray}{c}\mathbf{q^{\prime}}\in
B\\\ \pi\in\Pi\end{subarray}}V_{\pi}(\mathbf{q^{\prime}})$ (40)

###### Proof.

Define the following set:

$A_{\pi}:=\left\\{\mathbf{q}\in\mathcal{S}:\|\mathbf{q}\|_{1}\leq\frac{2c}{\epsilon}-\mathbb{E}_{\pi}\left[\|\mathbf{q}\|_{1}\right]\right\\}$
(41)

Since $J_{\pi}\leq\frac{c}{\epsilon}$, $A_{\pi}$ is a finite non-empty set.
Multiplying (36) throughout by $\frac{2}{\epsilon}$, we obtain the following:

$\mathbb{E}_{\pi}\left[\frac{2}{\epsilon}\|\mathbf{q}_{k+1}\|^{2}-\frac{2}{\epsilon}\|\mathbf{q}_{k}\|^{2}\Big{|}\mathbf{q}_{k}=\mathbf{q}\right]\leq-2\|\mathbf{q}\|_{1}+\frac{2c}{\epsilon}$
(42)

Consider a $\mathbf{q}\in A_{\pi}^{\mathsf{c}}$. Then, from definition it is
true that
$-\|\mathbf{q}\|_{1}\leq-\frac{2c}{\epsilon}+\mathbb{E}_{\pi}\left[\|\mathbf{q}\|_{1}\right]$.
Bounding $-\|\mathbf{q}\|_{1}$ from above, we obtain,

$\mathbb{E}_{\pi}\left[\frac{2}{\epsilon}\|\mathbf{q}_{k+1}\|^{2}-\frac{2}{\epsilon}\|\mathbf{q}_{k}\|^{2}\Big{|}\mathbf{q}_{k}=\mathbf{q}\right]\leq-\|\mathbf{q}\|_{1}+\mathbb{E}_{\pi}\left[\|\mathbf{q}\|_{1}\right]$
(43)

Let $\tau_{A_{\pi}}$ be the first time to enter set $A_{\pi}$ starting from
state $\mathbf{q}\in A_{\pi}^{\mathsf{c}}.$ Note that $\tau_{A_{\pi}}$ is
almost surely finite, because stability follows from lemma A.1. Let
$\mathbf{q}_{\tau_{A_{\pi}}}\in A^{\pi}$ represent the state first reached
within $A_{\pi}.$ Then, consider the drift equation summed up along the
trajectory starting from $\mathbf{q}$ till the first time it enters the set
$A_{\pi}$,

$\displaystyle\underbrace{\mathbb{E}\left[\sum_{k=0}^{\tau_{A_{\pi}}-1}\|\mathbf{q}_{k}\|_{1}-\mathbb{E}_{\pi}\left[\|\mathbf{q}_{k}\|_{1}\right]\Big{|}\mathbf{q}_{0}=\mathbf{q}\right]}_{(a)}\leq\underbrace{-\mathbb{E}_{\pi}\left[\mathbb{E}_{\pi}\left[\sum_{k=0}^{\tau_{A_{\pi}}-1}{\frac{2}{\epsilon}\|\mathbf{q}_{k+1}\|^{2}-\frac{2}{\epsilon}\|\mathbf{q}_{k}\|^{2}\Big{|}\mathcal{F}_{k}}\right]\right]}_{(b)}$
(44)

where
$\mathcal{F}_{k}=\sigma\left(\left\\{\mathbf{q}_{0},a_{0},\mathbf{q}_{1},a_{1},\ldots,\mathbf{q}_{k},a_{k}\right\\}\right)$
represents the filtration till time $k.$ Consider the expression in $(b)$.
Since $\tau_{A_{\pi}}$ is a valid stopping time and since $\|\mathbf{q}\|^{2}$
is a non-negative random variable, from discrete Dynkin’s formula [MT92] we
have the following:

$\displaystyle(b)$
$\displaystyle=-\mathbb{E}_{\pi}\left[\sum_{k=0}^{\tau_{A_{\pi}}-1}\mathbb{E}_{\pi}\left[{\frac{2}{\epsilon}\|\mathbf{q}_{k+1}\|^{2}\Big{|}\mathcal{F}_{k}}\right]-\frac{2}{\epsilon}\|\mathbf{q}_{k}\|^{2}\right]$
(45)
$\displaystyle=\frac{2}{\epsilon}\|\mathbf{q}\|^{2}-\mathbb{E}_{\pi}\left[\frac{2}{\epsilon}\|\mathbf{q}_{\tau_{A_{\pi}}}\|^{2}\Big{|}\mathbf{q}_{0}=\mathbf{q}\right]$
(46)

where $\|\mathbf{q}_{\tau_{A_{\pi}}}\|^{2}=\sum_{\mathbf{q^{\prime}}\in
A_{\pi}}\mathbb{P}_{\pi}\left(\mathbf{q}_{\tau_{A_{\pi}}}=\mathbf{q^{\prime}}|\mathbf{q}_{0}=\mathbf{q}\right)f(\mathbf{q^{\prime}})$.

Since $\|\mathbf{q}_{\tau_{A_{\pi}}}\|^{2}>0$, we obtain the following:

$(b)\leq\frac{2}{\epsilon}\|\mathbf{q}\|^{2}$ (47)

Consider the expression in $(a).$ From definition of $A_{\pi}$ in (41), we
know that the state corresponding to zero queue length, that is $\mathbf{0}\in
A_{\pi},\forall\pi\in\Pi.$ Let $\tau^{\pi}_{0}$ denote the time to hit state
$\mathbf{0}$. Then,

$\displaystyle(a)=\mathbb{E}_{\pi}\Bigg{[}\sum_{k=0}^{\tau_{A_{\pi}}-1}\left(\|\mathbf{q}_{k}\|_{1}-\mathbb{E}_{\pi}\left[\|\mathbf{q}_{k}\|_{1}\right]\right)$
$\displaystyle+\sum_{k=\tau_{A_{\pi}}}^{\tau^{\pi}_{0}-1}\left(\|\mathbf{q}_{k}\|_{1}-\mathbb{E}_{\pi}\left[\|\mathbf{q}_{k}\|_{1}\right]\right)\Bigg{|}\mathbf{q}_{0}=\mathbf{q}\Bigg{]}$
(48)
$\displaystyle-\mathbb{E}_{\Pi}\left[\sum_{k=\tau_{A_{\pi}}}^{\tau^{\pi}_{0}-1}\left(\|\mathbf{q}_{k}\|_{1}-\mathbb{E}_{\pi}\left[\|\mathbf{q}_{k}\|_{1}\right]\right)\Bigg{|}\mathbf{q}_{0}=\mathbf{q}\right]$
(49)

Recall the definition of value function $V_{\pi}(\mathbf{q})$ from Equation
(4). We thus obtain:

$(a)=V_{\pi}(\mathbf{q})-\mathbb{E}_{\pi}\left[\sum_{k=\tau_{A_{\pi}}}^{\tau^{\pi}_{0}-1}\left(\|\mathbf{q}_{k}\|_{1}-\mathbb{E}_{\pi}\left[\|\mathbf{q}_{k}\|_{1}\right]\right)\Big{|}\mathbf{q}_{0}=\mathbf{q}\right]$
(50)

Let $\mathbb{I}$ denote the indicator function. Since $\tau_{A_{\pi}}$ is the
first time to enter set $A_{\pi}$ when starting from state $\mathbf{q},$

$\displaystyle(a)$
$\displaystyle=V_{\pi}(\mathbf{q})-\mathbb{E}_{\pi}\left[\left(\sum_{k=\tau_{A_{\pi}}}^{\tau^{\pi}_{0}-1}\left(\|\mathbf{q}_{k}\|_{1}-\mathbb{E}_{\pi}\left[\|\mathbf{q}_{k}\|_{1}\right]\right)\right)\left(\sum_{\mathbf{q^{\prime}}\in
A_{\pi}}\mathbb{I}_{\mathbf{q}_{\tau_{A_{\pi}}}=\mathbf{q^{\prime}}}\right)\Bigg{|}\mathbf{q}_{0}=\mathbf{q}\right]$
(51) $\displaystyle=V_{\pi}(\mathbf{q})-\sum_{\mathbf{q^{\prime}}\in
A_{\pi}}\mathbb{E}_{\pi}\left[\sum_{k=\tau_{A_{\pi}}}^{\tau^{\pi}_{0}-1}\left(\|\mathbf{q}_{k}\|_{1}-\mathbb{E}_{\pi}\left[\|\mathbf{q}_{k}\|_{1}\right]\right)\Bigg{|}\mathbf{q}_{0}=\mathbf{q},\mathbf{q}_{\tau_{A_{\pi}}=\mathbf{q^{\prime}}}\right]\mathbb{P}_{\pi}\left(\mathbf{q}_{\tau_{A_{\pi}}=\mathbf{q^{\prime}}}|\mathbf{q}_{0}=\mathbf{q}\right)$
(52)

Since $\tau_{A_{\pi}}$ is the first time to enter set $A_{\pi}$, it qualifies
as a valid stopping time. Hence, from the strong Markov property we know that:

$\mathbb{E}_{\pi}\left[\sum_{k=\tau_{A_{\pi}}}^{\tau^{\pi}_{0}-1}\left(\|\mathbf{q}_{k}\|_{1}-\mathbb{E}_{\pi}\left[\|\mathbf{q}_{k}\|_{1}\right]\right)\Bigg{|}\mathbf{q}_{0}=\mathbf{q},\mathbf{q}_{\tau_{A_{\pi}}=\mathbf{q^{\prime}}}\right]={\mathbb{E}_{\pi}\left[\sum_{k=0}^{\tau^{\pi}_{0}-1}\left(\|\mathbf{q}_{k}\|_{1}-\mathbb{E}_{\pi}\left[\|\mathbf{q}_{k}\|_{1}\right]\right)\Bigg{|}\mathbf{q}_{0}=\mathbf{q^{\prime}}\right]}$
(53)

Since,
$V_{\pi}(\mathbf{q^{\prime}}):={\mathbb{E}_{\pi}\left[\sum_{k=0}^{\tau^{\pi}_{0}-1}\left(\|\mathbf{q}_{k}\|_{1}-\mathbb{E}_{\pi}\left[\|\mathbf{q}_{k}\|_{1}\right]\right)\Bigg{|}\mathbf{q}_{0}=\mathbf{q^{\prime}}\right]}$,

$(a)=V_{\pi}(\mathbf{q})-\sum_{\mathbf{q^{\prime}}\in
A_{\pi}}\mathbb{P}_{\pi}\left(\mathbf{q}_{\tau_{A_{\pi}}=\mathbf{q^{\prime}}}|\mathbf{q}_{0}=\mathbf{q}\right)V_{\pi}(\mathbf{q^{\prime}})$
(54)

Combining Equations 44,47 and 54, we obtain the following,

$V_{\pi}(\mathbf{q})\leq\frac{2}{\epsilon}\|\mathbf{q}\|^{2}+\sum_{\mathbf{q^{\prime}}\in
A_{\pi}}\mathbb{P}_{\pi}\left(\mathbf{q}_{\tau_{A_{\pi}}=\mathbf{q^{\prime}}}|\mathbf{q}_{0}=\mathbf{q}\right)V_{\pi}(\mathbf{q^{\prime}})$
(55)

Recall the definition of set $B$ in Equation 10

$B:=\left\\{\mathbf{q}\in\mathcal{S}:\|\mathbf{q}\|_{1}\leq\frac{2c}{\epsilon}\right\\}$
(56)

Since $\mathbb{E}_{\pi}\left[\|\mathbf{q}\|_{1}\right]\geq 0$ for all policies
$\pi\in\Pi$, it is evident from Equation 41 that $A_{\pi}\subset B$. Thus the
following is true:

$\max_{\begin{subarray}{c}\mathbf{q^{\prime}}\in A_{\pi}\\\
\pi\in\Pi\end{subarray}}V_{\pi}(\mathbf{q^{\prime}})\leq\max_{\begin{subarray}{c}\mathbf{q^{\prime}}\in
B\\\ \pi\in\Pi\end{subarray}}V_{\pi}(\mathbf{q^{\prime}})$ (57)

Hence Equation 55 reduces to,

$\displaystyle V_{\pi}(\mathbf{q})$
$\displaystyle\leq\frac{2}{\epsilon}\|\mathbf{q}\|^{2}+\sum_{\mathbf{q^{\prime}}\in
A_{\pi}}\mathbb{P}_{\pi}\left(\mathbf{q}_{\tau_{A_{\pi}}=\mathbf{q^{\prime}}}|\mathbf{q}_{0}=\mathbf{q}\right)\max_{\begin{subarray}{c}\mathbf{q}^{\prime\prime}\in
A_{\pi}\\\ \pi\in\Pi\end{subarray}}V_{\pi}(\mathbf{q}^{\prime\prime})$
$\displaystyle\leq\frac{2}{\epsilon}\|\mathbf{q}\|^{2}+\sum_{\mathbf{q^{\prime}}\in
A_{\pi}}\mathbb{P}_{\pi}\left(\mathbf{q}_{\tau_{A_{\pi}}=\mathbf{q^{\prime}}}|\mathbf{q}_{0}=\mathbf{q}\right)\max_{\begin{subarray}{c}\mathbf{q}^{\prime\prime}\in
B\\\ \pi\in\Pi\end{subarray}}V_{\pi}(\mathbf{q}^{\prime\prime})$
$\displaystyle\leq\frac{2}{\epsilon}\|\mathbf{q}\|^{2}+\max_{\begin{subarray}{c}\mathbf{q^{\prime}}\in
B\\\ \pi\in\Pi\end{subarray}}V_{\pi}(\mathbf{q^{\prime}})$ (58)

Recall that Equation A.1.1 holds true for all $\mathbf{q}\in
A_{\pi}^{\mathsf{c}}$. Since $B^{\mathsf{c}}\subset A_{\pi}^{\mathsf{c}}$ for
all policies $\pi\in\Pi,$ we thus obtain that for all $\mathbf{q}\in
B^{\mathsf{c}}$, it is true that,

$V_{\pi}(\mathbf{q})\leq\frac{2}{\epsilon}\|\mathbf{q}\|^{2}+\max_{\begin{subarray}{c}\mathbf{q^{\prime}}\in
B\\\ \pi\in\Pi\end{subarray}}V_{\pi}(\mathbf{q^{\prime}})$ (59)

In order to invoke the connection of NPG to prediction through expert advice,
we need policy independent bounds on the estimate $\widehat{Q}_{\pi}.$ As a
step towards achieving that, we first need to establish policy independent
bounds on the exact value function $V_{\pi}$ and therefore on $V_{\pi}$. Since
the drift provides us with a policy dependent upper bound alone, we exploit
the structure of queuing systems in order to obtain a policy independent lower
bound and upper bound.

####  A.1.2 Policy Independent bounds on the State Value Function

The structural assumption 2.3 aids in obtaining policy independent bounds by
providing an uniform upper bound on the hitting time of state $\mathbf{0}$
from any state within a finite set $B$ across all policies $\pi.$

######  Lemma A.5.

Consider the set $B$ in Equation (10). By definition, the state $\mathbf{0}$,
which represents zero queue length, is included in the set $B$, i.e.,
$\mathbf{0}\in B.$ Let $\tau^{\text{bound}}_{B}$ represent the maximum time
taken to hit $\mathbf{0}$ starting from any state $\mathbf{q}\in B$ across all
policies $\pi\in\Pi$. Then under Assumption 2.3, for any policy $\pi\in\Pi$,
$\tau^{\text{bound}}_{B}$ is bounded from above as follows:

$\tau^{\text{bound}}_{B}\leq\frac{x_{B}}{p_{B}^{2}}+x_{B}.$ (60)

###### Proof.

For each state $\mathbf{q}\in B$, let $t_{\pi,B}(\mathbf{q})$ be the expected
amount of time until policy $\pi$ next reaches a state $\mathbf{q^{\prime}}\in
B$, starting in state $\mathbf{q}$. Let $t_{\pi,B}^{\max}$ be the maximum over
$\mathbf{q}\in B$ of $t_{\pi,B}(\mathbf{q})$. Let $\mathbf{q}^{*}$ be the
state in $B$ which achieves this maximum. By 2.3, every state $\mathbf{q}\in
B$ has at least $p_{B}$ probability of moving to state $\mathbf{q}^{*}$ in the
next $x_{B}$ steps, and therefore spending at most $x_{B}$ of the next
$t_{\pi,B}^{\max}+x_{B}$ steps inside $B$.

Let us use a renewal-reward argument, where the renewal moments are steps on
which the system visits state $\mathbf{q}^{*}$. Let us subdivide this renewal
period into three segments:

  1. 1.

Starting at $\mathbf{q}^{*}$, the time until a state $\mathbf{q}\in B$ is next
visited.

  2. 2.

Starting from a state $\mathbf{q}\in B$, the next $x_{B}$ steps, during which
there is at least a $p_{B}$ probability of reaching the state
$\mathbf{q}^{*}$.

  3. 3.

Any time not in either of these two segments, which must be spent outside of
$B$.

From these segments, we can upper-bound the fraction of time during the
renewal period that the system spends in $B$: The system can only be in $B$
during item 2, and the system can spend at most $\frac{1}{p_{B}}$ periods of
length at most $x_{B}$ in that segment. The fraction of time spent in $B$ is
maximized if no time is spent in item 3, resulting in the following bound:

$\displaystyle\mathbb{P}\left(\mathbf{q}_{t}\in
B\right)\leq\frac{x_{B}/p_{B}}{t_{\pi,B}^{\max}+x_{B}/p_{B}}$

Since the system accrues a cost of atleast $\frac{2c}{\epsilon}$ outside $B$
and a cost of atleast $0$ inside $B$, the average cost $J_{\pi}$ can be
bounded as below:

$J_{\pi}\geq\left(\frac{2c}{\epsilon}\right)\left(\frac{t_{\pi,B}^{\max}}{t_{\pi,B}^{\max}+x_{B}/p_{B}}\right)$
(61)

However, from Lemma A.3, we know that $J_{\pi}\leq\frac{c}{\epsilon}.$ We can
use this fact to bound $t_{\pi,B}^{\max}$ as follows:

$\left(\frac{2c}{\epsilon}\right)\left(\frac{t_{\pi,B}^{\max}}{t_{\pi,B}^{\max}+x_{B}/p_{B}}\right)\leq\frac{c}{\epsilon}$
(62) $\implies t_{\pi,B}^{\max}\leq\frac{x_{B}}{p_{B}}$ (63)

Now, we can bound the time until we reach $B$, starting from $\mathbf{q}\in
B$. Whenever the system is in a state in $B$, there is a $p_{B}$ chance of
reaching $B$ in the next $x_{B}$ steps, and a maximum expected time of
$t_{\pi,B}^{\max}$ until we next get the opportunity. Let
$p_{\pi,B}(\mathbf{q})$ be the probability that the system reaches
$\mathbf{0}$ from $\mathbf{q}$ in at most $x_{B}$ steps. Let
$t^{\prime}_{\pi,B}(\mathbf{q})$ be the expected time until the system re-
enters $B$, conditional on not reaching $\mathbf{0}$ in at most $x_{B}$ steps.
Note that
$t^{\prime}_{\pi,B}(\mathbf{q})\leq\frac{t_{\pi,B}(\mathbf{q})}{1-p_{\pi,B}(\mathbf{q})}$,
because the probability of the event of not reaching $B$ in at most $x_{B}$
steps is $1-p_{\pi,B}(\mathbf{q})$.

We can now start to bound $\tau_{\pi}(\mathbf{q})$ as follows:

$\displaystyle\tau_{\pi}(\mathbf{q})\leq
p_{\pi,B}(\mathbf{q})x_{B}+(1-p_{\pi,B}(\mathbf{q}))(t^{\prime}_{\pi,B}(\mathbf{q})+\tau_{\pi}(\mathbf{q^{\prime}}))$

where $\mathbf{q^{\prime}}$ is the state at which we re-enter $B$. Thus,

$\displaystyle\tau_{\pi}(\mathbf{q})$ $\displaystyle\leq
p_{\pi,B}(\mathbf{q})x_{B}+(1-p_{\pi,B}(\mathbf{q}))\left(\frac{t_{\pi,B}(\mathbf{q})}{1-p_{\pi,B}(\mathbf{q})}+\tau_{\pi}(\mathbf{q^{\prime}})\right)$
$\displaystyle=x_{B}+t_{\pi,B}(\mathbf{q})+(1-p_{\pi,B}(\mathbf{q}))(\tau_{\pi}(\mathbf{q^{\prime}})-x_{B})$

In particular, letting $\tau_{\pi}^{\text{bound}}$ be the maximum over
$\mathbf{q}\in B$ of $\tau_{\pi}(\mathbf{q})$, and letting
$\mathbf{q}_{\tau}^{*}$ be the state in which that maximum occurs, we have

$\displaystyle\tau_{\pi}^{\text{bound}}$ $\displaystyle\leq
x_{B}+t_{\pi,B}(\mathbf{q}_{\tau}^{*})+(1-p_{\pi,B}(\mathbf{q}_{\tau}^{*}))(\tau_{\pi}^{\text{bound}}-x_{B})$
$\displaystyle\tau_{\pi}^{\text{bound}}$ $\displaystyle\leq
x_{B}+\frac{t_{\pi,B}(\mathbf{q}_{\tau}^{*})}{p_{\pi,B}(\mathbf{q}_{\tau}^{*})}\leq
x_{B}+\frac{t_{\pi,B}^{\max}}{p_{B}}$ $\displaystyle\tau_{\pi}^{\text{bound}}$
$\displaystyle\leq\frac{x_{B}}{p_{B}^{2}}+x_{B}$

∎

The uniform hitting bound provides with a uniform lower bound on the value
function $V_{\pi}.$ This lower bound is further leveraged to get a policy
independent upper bound on the quantity
$\max_{\begin{subarray}{c}\mathbf{q}\in B\\\
\pi\in\Pi\end{subarray}}V_{\pi}(\mathbf{q})$. This leads to the upper bound on
the value functions being policy independent.

######  Lemma A.6.

Let $x_{B},p_{B}$ be policy independent constants that satisfy Assumption 2.3
and $c,\epsilon$ be policy independent constants that satisfy Assumptions 2.1
and 2.2. Then, the following are true.

  1. 1.

The value function $V_{\pi}(\mathbf{q})$ is lower bounded
$\forall\mathbf{q}\in\mathcal{S}$ and for all policies $\pi\in\Pi$ as follows:

$V_{\pi}(\mathbf{q})\geq-\frac{c}{\epsilon}\left(\frac{x_{B}}{p_{B}^{2}}+x_{B}\right)$
(64)

  2. 2.

For all $\mathbf{q}\in B$, where $B$ is a set defined in Equation (10), the
value function $V_{\pi}(\mathbf{q})$ is uniformly bounded from above across
all policies $\pi\in\Pi$ as follows:

$\max_{\begin{subarray}{c}\mathbf{q}\in B\\\
\pi\in\Pi\end{subarray}}V_{\pi}(\mathbf{q})\leq\frac{c}{p_{B}\epsilon}\left(\frac{x_{B}}{p_{B}^{2}}+2x_{B}\right).$
(65)

  3. 3.

The value function $V_{\pi}(\mathbf{q})$ is upper bounded
$\forall\mathbf{q}\in\mathcal{S}$ and for all policies $\pi\in\Pi$ as follows:

$V_{\pi}(\mathbf{q})\leq\frac{2}{\epsilon}\|\mathbf{q}\|^{2}+\frac{c}{p_{B}\epsilon}\left(\frac{x_{B}}{p_{B}^{2}}+2x_{B}\right)$
(66)

Proof of Part 1:

###### Proof.

Recall the definition of the state value function $V_{\pi}(\mathbf{q})$ in
Equation 4. Consider any state $\mathbf{q}\in\mathcal{S}$ and policy
$\pi\in\Pi,$ such that $\tau^{\pi}_{0}$ represents the time to hit state
$\mathbf{0}$ when starting at $\mathbf{q}$. Then,

$\displaystyle V_{\pi}(\mathbf{q})$
$\displaystyle=\mathbb{E}_{\pi}\left[\sum_{k=0}^{\tau^{\pi}_{0}-1}\|\mathbf{q}_{k}\|_{1}-\mathbb{E}_{\pi}\left[\|\mathbf{q}\|_{1}\right]\Big{|}\mathbf{q}_{0}=\mathbf{q}\right]$
(67)
$\displaystyle=\mathbb{E}_{\pi}\left[\sum_{k=0}^{\tau^{\pi}_{0}-1}c(\mathbf{q}_{k})-J_{\pi}\Big{|}\mathbf{q}_{0}=\mathbf{q}\right]$
(68)

where $c(\mathbf{q})$ is the single step cost associated with state
$\mathbf{q}$, particularly the total queue length at that instant.

Consider the following definitions:

  * •

$\tau_{\pi,B}^{\text{out}}$ is the first time to enter $B$ when starting at
$\mathbf{q}$.

  * •

$\tau_{\pi,B}^{\text{in}}$ is the first time to hit state $0$ from the first
time to enter state $B.$

  * •

$\overline{c}_{\pi}^{\text{out}}$ be the aggregate average cost obtained till
time $\tau_{\pi,B}^{\text{out}}.$

  * •

$\overline{c}_{\pi}^{\text{in}}$ be the aggregate average cost in the next
time interval $\tau_{\pi,B}^{\text{in}}$.

Then the value function $V_{\pi}(\mathbf{q})$ can be decomposed as follows:

$V_{\pi}(\mathbf{q})=V^{\text{out}}_{\pi}(\mathbf{q})+V^{\text{in}}_{\pi}(\mathbf{q})$
(69)

When further expanded, we obtain,

$V_{\pi}(\mathbf{q})=\left(\overline{c}_{\pi}^{\text{out}}-J_{\pi}\right)\tau_{\pi,B}^{\text{out}}+\left(\overline{c}_{\pi}^{\text{in}}-J_{\pi}\right)\tau_{\pi,B}^{\text{in}}$
(70)

From definition $\forall\mathbf{q}\in B^{\mathsf{c}}$,
$\|\mathbf{q}\|_{1}>\frac{2c}{\epsilon}.$ Hence the aggregate cost outside $B$
is also greater than $\frac{2c}{\epsilon}$, that is
$\overline{c}_{\pi}^{\text{out}}>\frac{2c}{\epsilon}$. Since from Lemma A.3 we
know that $J_{\pi}\leq\frac{c}{\epsilon}$, it is true that
$\left(\overline{c}_{\pi}^{\text{out}}-J_{\pi}\right)>0.$ Hence, we obtain,

$V_{\pi}(\mathbf{q})\geq\left(\overline{c}_{\pi}^{\text{in}}-J_{\pi}\right)\tau_{\pi,B}^{\text{in}}$
(71)

Since all the costs are non-negative,

$V_{\pi}(\mathbf{q})\geq-J_{\pi}\tau_{\pi,B}^{\text{in}}$ (72)

Since from Lemma A.3 we know that $J_{\pi}\leq\frac{c}{\epsilon}$,

$V_{\pi}(\mathbf{q})\geq-\frac{c}{\epsilon}\tau_{\pi,B}^{\text{in}}$ (73)

Since $\tau_{\pi,B}^{\text{in}}$ represents the time to reach $\mathbf{0}$
starting from the first state in $B$ to be reached from $\mathbf{q}$, this
quantity can be bounded from above using Lemma A.5. That is
$\tau_{\pi,B}^{\text{in}}\leq\tau_{B}^{\text{bound}}$. Hence for all
$\mathbf{q}\in\mathcal{S}$, we obtain the following policy-independent uniform
lower bound on the state value function,

$V_{\pi}(\mathbf{q})\geq-\frac{c}{\epsilon}\left(\frac{x_{B}}{p_{B}^{2}}+x_{B}.\right)$
(74)

∎

Proof of Part 2:

The proof of part 2 relies on the result in Part 1. Part 2 is essential in
establishing policy independent upper bounds on the value function, and relies
on assumptions 2.1,2.2 and 2.3. This analysis is one of the key contributions
of this paper and is presented below.

###### Proof.

Let $\mathbf{q}_{0}=\mathbf{0}$, i.e., the trajectory is starting from state
$\mathbf{0}.$ Let $\tau_{\pi}^{K}$ represent the first time at which the
trajectory hits the state $\mathbf{0}$ for the $K^{\text{th}}$ time. That is,

$\tau_{\pi}^{K}=\inf_{k}\left\\{\left(\sum_{i=1}^{k}\mathbb{I}(\mathbf{q}_{i}=\mathbf{0})\right)=K\Big{|}\mathbf{q}_{0}=\mathbf{0}\right\\}$
(75)

$\tau_{\pi}^{K}$ represents the minimum time to complete $K$ recurrent cycles
with the recurrent state being $\mathbf{0}$ when starting from $\mathbf{0}.$
Recall $x_{B}$ from Assumption 2.3. Consider the following quantity.

$\widetilde{N}=\min\left\\{N\in\mathbb{N},\tau_{\pi}^{N}\geq x_{B}\right\\}$
(76)

Consider $\widetilde{V}_{\pi}(\mathbf{0})$ defined below:,

$\widetilde{V}_{\pi}(\mathbf{0})=\mathbb{E}_{\pi}\left[\sum_{i=0}^{\tau_{\pi}^{\widetilde{N}}-1}\|\mathbf{q}_{i}\|_{1}-\mathbb{E}_{\pi}\left[\|\mathbf{q}\|_{1}\right]\Big{|}\mathbf{q}_{0}=\mathbf{0}\right]$
(77)

Note that since $\widetilde{N}$ is a random quantity, Equation 77 does not
correspond to the recurrent state characterization of the state value function
in Equation 4. Hence, we need to consider the following. The above equation
can be decomposed into sum of recurrent cycles as below:

$\widetilde{V}_{\pi}(\mathbf{0})=\mathbb{E}_{\pi}\left[\sum_{i=1}^{\widetilde{N}}\sum_{k=\tau_{\pi}^{i-1}}^{\tau_{\pi}^{i}-1}\|\mathbf{q}_{i}\|_{1}-\mathbb{E}_{\pi}\left[\|\mathbf{q}\|_{1}\right]\Big{|}\mathbf{q}_{0}=\mathbf{0}\right]$
(78)

Since from definition of $\tau_{\pi}^{\widetilde{N}}$ in Equation 76 there can
be a maximum of $x_{B}$ such recurrent cycles, $\widetilde{N}$ is bounded from
above by $x_{B}$.

$\displaystyle\widetilde{V}_{\pi}(\mathbf{0})$
$\displaystyle=\mathbb{E}_{\pi}\left[\sum_{i=1}^{x_{B}}\sum_{k=\tau_{\pi}^{i-1}}^{\tau_{\pi}^{i}-1}\left(\|\mathbf{q}_{i}\|_{1}-\mathbb{E}_{\pi}\left[\|\mathbf{q}\|_{1}\right]\right)\mathbb{I}\left(\widetilde{N}\geq
i\right)\Big{|}\mathbf{q}_{0}=\mathbf{0}\right]$ (79)
$\displaystyle=\sum_{i=1}^{x_{B}}\mathbb{E}_{\pi}\left[\sum_{k=\tau_{\pi}^{i-1}}^{\tau_{\pi}^{i}-1}\left(\|\mathbf{q}_{i}\|_{1}-\mathbb{E}_{\pi}\left[\|\mathbf{q}\|_{1}\right]\right)\mathbb{I}\left(\widetilde{N}\geq
i\right)\Big{|}\mathbf{q}_{0}=\mathbf{0}\right]$ (80)
$\displaystyle=\sum_{i=1}^{x_{B}}\mathbb{E}_{\pi}\left[\mathbb{E}_{\pi}\left[\sum_{k=\tau_{\pi}^{i-1}}^{\tau_{\pi}^{i}-1}\left(\|\mathbf{q}_{i}\|_{1}-\mathbb{E}_{\pi}\left[\|\mathbf{q}\|_{1}\right]\right)\mathbb{I}\left(\widetilde{N}\geq
i\right)\Bigg{|}\mathcal{F}_{i-1}\right]\right]$ (81)

where
$\mathcal{F}_{i-1}=\sigma\left(\left\\{\mathbf{q}_{0},a_{0},\mathbf{q}_{1},a_{1},\ldots,\mathbf{q}_{\tau_{\pi}^{i-1}},a_{\tau_{\pi}^{i-1}}\right\\}\right)$
is the filtration till the end of the ${i-1}^{\text{th}}$ cycle. Since
$\mathbb{I}\left(\widetilde{N}\geq i\right)$ is a deterministic function when
conditioned on $\mathcal{F}_{i-1}$, we obtain the following:

$\widetilde{V}_{\pi}(\mathbf{0})=\sum_{i=1}^{x_{B}}\mathbb{E}_{\pi}\left[\mathbb{I}\left(\widetilde{N}\geq
i\right)\underbrace{\mathbb{E}_{\pi}\left[\sum_{k=\tau_{\pi}^{i-1}}^{\tau_{\pi}^{i}-1}\left(\|\mathbf{q}_{i}\|_{1}-\mathbb{E}_{\pi}\left[\|\mathbf{q}\|_{1}\right]\right)\Bigg{|}\mathcal{F}_{i-1}\right]}_{(a)}\right]$
(82)

$(a)$ now corresponds to $V_{\pi}(\mathbf{0})$, which from definition in
Equation 4 is 0. Hence,

$\widetilde{V}_{\pi}(\mathbf{0})=0$ (83)

From definition in Equation (76), we can decompose
$\widetilde{V}_{\pi}(\mathbf{0})$ as follows:

$\widetilde{V}_{\pi}(\mathbf{0})=\mathbb{E}_{\pi}\left[\sum_{k=0}^{x_{B}-1}\|\mathbf{q}_{k}\|_{1}-\mathbb{E}_{\pi}\left[\|\mathbf{q}\|_{1}\right]\Big{|}\mathbf{q}_{0}=\mathbf{0}\right]+\sum_{\mathbf{q^{\prime}}\in\mathcal{S}}\mathbb{P}_{\pi}^{x_{B}}\left(\mathbf{q^{\prime}}|\mathbf{q}_{0}=\mathbf{0}\right)V_{\pi}(\mathbf{q^{\prime}})$
(84)

where $\mathbb{P}_{\pi}^{x_{B}}$ is the $x_{B}$ step probability transition
matrix under policy $\pi.$ Let $\mathbf{q}\in B$. Since
$\widetilde{V}_{\pi}(\mathbf{0})=0$ from Equation 83, we obtain the following,

$-\mathbb{E}_{\pi}\left[\sum_{k=0}^{x_{B}-1}\|\mathbf{q}_{k}\|_{1}-\mathbb{E}_{\pi}\left[\|\mathbf{q}\|_{1}\right]\Big{|}\mathbf{q}_{0}=\mathbf{0}\right]=\mathbb{P}_{\pi}^{x_{B}}\left(\mathbf{q}|\mathbf{q}_{0}=\mathbf{0}\right)V_{\pi}(\mathbf{q})+\sum_{\mathbf{q^{\prime}}\in\mathcal{S}/\left\\{\mathbf{q}\right\\}}\mathbb{P}_{\pi}^{x_{B}}\left(\mathbf{q^{\prime}}|\mathbf{q}_{0}=\mathbf{0}\right)V_{\pi}(\mathbf{q^{\prime}})$
(85)
$\mathbb{P}_{\pi}^{x_{B}}\left(\mathbf{q}|\mathbf{q}_{0}=\mathbf{0}\right)V_{\pi}(\mathbf{q})=-\mathbb{E}_{\pi}\left[\sum_{k=0}^{x_{B}-1}\|\mathbf{q}_{k}\|_{1}-\mathbb{E}_{\pi}\left[\|\mathbf{q}\|_{1}\right]\Big{|}\mathbf{q}_{0}=\mathbf{0}\right]-\sum_{\mathbf{q^{\prime}}\in\mathcal{S}/\left\\{\mathbf{q}\right\\}}\mathbb{P}_{\pi}^{x_{B}}\left(\mathbf{q^{\prime}}|\mathbf{q}_{0}=\mathbf{0}\right)V_{\pi}(\mathbf{q^{\prime}})$
(86)

From Part 1 of this lemma, we know that
$-V_{\pi}(\mathbf{q})\leq\frac{c}{\epsilon}\left(\frac{x_{B}}{p_{B}^{2}}+x_{B}\right)\forall\mathbf{q}\in\mathcal{S}.$

$\displaystyle\mathbb{P}_{\pi}^{x_{B}}\left(\mathbf{q}|\mathbf{q}_{0}=\mathbf{0}\right)V_{\pi}(\mathbf{q})$
$\displaystyle\leq-\mathbb{E}_{\pi}\left[\sum_{k=0}^{x_{B}-1}\|\mathbf{q}_{k}\|_{1}-\mathbb{E}_{\pi}\left[\|\mathbf{q}\|_{1}\right]\Big{|}\mathbf{q}_{0}=\mathbf{0}\right]$
(87)
$\displaystyle+\sum_{\mathbf{q^{\prime}}\in\mathcal{S}/\left\\{\mathbf{q}\right\\}}\mathbb{P}_{\pi}^{x_{B}}\left(\mathbf{q^{\prime}}|\mathbf{q}_{0}=\mathbf{0}\right)\frac{c}{\epsilon}\left(\frac{x_{B}}{p_{B}^{2}}+x_{B}\right)$
(88)
$\displaystyle\leq\mathbb{E}_{\pi}\left[\sum_{k=0}^{x_{B}-1}\mathbb{E}_{\pi}\left[\|\mathbf{q}\|_{1}\right]\Big{|}\mathbf{q}_{0}=\mathbf{0}\right]+\frac{c}{\epsilon}\left(\frac{x_{B}}{p_{B}^{2}}+x_{B}\right)$
(89) $\displaystyle\leq
x_{B}\left(\frac{c}{\epsilon}\right)+\frac{c}{\epsilon}\left(\frac{x_{B}}{p_{B}^{2}}+x_{B}\right)$
(90)

where the last inequality follows from Lemma A.3.

If $V_{\pi}(\mathbf{q})$ is negative, then 0 is an upper bound on
$V_{\pi}(\mathbf{q})$. However, if $V_{\pi}(\mathbf{q})$ is positive,

$\displaystyle
V_{\pi}(\mathbf{q})\leq\frac{1}{\mathbb{P}_{\pi}^{x_{B}}\left(\mathbf{q}|\mathbf{q}_{0}=\mathbf{0}\right)}\frac{c}{\epsilon}\left(\frac{x_{B}}{p_{B}^{2}}+2x_{B}\right)$
(91)

Recall from Assumption 2.3, since $\mathbf{0},\mathbf{q}\in B$,
$\mathbb{P}_{\pi}^{x_{B}}\left(\mathbf{q}|\mathbf{q}_{0}=\mathbf{0}\right)\geq
p_{B}$. That is the probability of reaching any $\mathbf{q}\in B$ from
$\mathbf{0}$ in $x_{B}$ steps is at least $p_{B}$. Hence for all
$\mathbf{q}\in B$, it is true that,

$V_{\pi}(\mathbf{q})\leq\frac{c}{p_{B}\epsilon}\left(\frac{x_{B}}{p_{B}^{2}}+2x_{B}\right)$
(92)

Since the above bound is uniform across all policies $\pi\in\Pi$ and
$\mathbf{q}\in B$,

$\max_{\begin{subarray}{c}\mathbf{q}\in B\\\
\pi\in\Pi\end{subarray}}V_{\pi}(\mathbf{q})\leq\frac{c}{p_{B}\epsilon}\left(\frac{x_{B}}{p_{B}^{2}}+2x_{B}\right)$
(93)

∎

Proof of Part 3:

###### Proof.

Combining Equation (93) from Part 2 and Equation (59) from Lemma A.4 yields
the results. That is $\forall\mathbf{q}\in\mathcal{S}$ and for all
$\pi\in\Pi$,

$V_{\pi}(\mathbf{q})\leq\frac{2}{\epsilon}\|\mathbf{q}\|^{2}+\frac{c}{p_{B}\epsilon}\left(\frac{x_{B}}{p_{B}^{2}}+2x_{B}\right)$
(94)

We thus obtain a policy independent upper bound on the value function for all
states in the state space. ∎

####  A.1.3 Policy Independent bounds on the State-Action Value Function

In order to obtain policy independent bounds on the estimate
$\widehat{Q}_{\pi}$ of the state action value function associated with some
policy $\pi$, it is necessary to first obtain bounds on the exact state action
value function $Q_{\pi}.$ The following lemma provides with state-dependent,
policy-independent bounds on the state action value function $Q.$

######  Lemma A.7.

There exists constant $c_{4}>0$, such that under Assumptions 2.1,2.2 and 2.3,
the state action value function $Q_{\pi}$ for all policies $\pi\in\Pi$ and
forall $\mathbf{q}\in\mathcal{S}$ satisfies:

$\left|Q_{\pi}(\mathbf{q},a)-Q_{\pi}(\mathbf{q},a^{\prime})\right|\leq\frac{2}{\epsilon}c_{1}\|\mathbf{q}\|^{2}+c_{4}\qquad
a,a^{\prime}\in\mathcal{A}$ (95)

where $\epsilon$ is the drift parameter and $c_{1}$ is defined in Assumption
2.3.

###### Proof.

Recall the Poisson Equation (5) corresponding to the state action value
function $Q_{\pi}$:

$Q_{\pi}(\mathbf{q},a)=\|\mathbf{q}\|_{1}+\mathbb{E}_{\mathbf{q^{\prime}}\sim\mathbb{P}(\cdot|\mathbf{q},a)}V_{\pi}(\mathbf{q^{\prime}})-J_{\pi}$
(96)

For any pair of actions $a,a^{\prime}\in\mathcal{A}$

$\displaystyle Q_{\pi}(\mathbf{q},a)-Q_{\pi}(\mathbf{q},a^{\prime})$
$\displaystyle=\mathbb{E}_{\mathbf{q^{\prime}}\sim\mathbb{P}(\cdot|\mathbf{q},a)}V_{\pi}(\mathbf{q^{\prime}})-\mathbb{E}_{\mathbf{q^{\prime}}\sim\mathbb{P}(\cdot|\mathbf{q},a^{\prime})}V_{\pi}(\mathbf{q^{\prime}})$
$\displaystyle\leq\mathbb{E}_{\mathbf{q^{\prime}}\sim\mathbb{P}(\cdot|\mathbf{q},a)}\left(\frac{2}{\epsilon}f(\mathbf{q^{\prime}})+\frac{c}{p_{B}\epsilon}\left(\frac{x_{B}}{p_{B}^{2}}+2x_{B}\right)\right)$
$\displaystyle+\mathbb{E}_{\mathbf{q^{\prime}}\sim\mathbb{P}(\cdot|\mathbf{q},a^{\prime})}\left(\frac{c}{\epsilon}\left(\frac{x_{B}}{p_{B}^{2}}+x_{B}.\right)\right)$
(97)

where the last inequality follows from Lemma A.6. Hence we obtain,

$Q_{\pi}(\mathbf{q},a)-Q_{\pi}(\mathbf{q},a^{\prime})\leq\mathbb{E}_{\mathbf{q^{\prime}}\sim\mathbb{P}(\cdot|\mathbf{q},a)}\left(\frac{2}{\epsilon}f(\mathbf{q^{\prime}})\right)+\frac{c}{\epsilon}\left(\frac{x_{B}}{p_{B}^{2}}+x_{B}\right)+\frac{c}{p_{B}\epsilon}\left(\frac{x_{B}}{p_{B}^{2}}+2x_{B}\right)$
(98)

Let
$c_{3}=\frac{c}{\epsilon}\left(\frac{x_{B}}{p_{B}^{2}}+x_{B}\right)+\frac{c}{p_{B}\epsilon}\left(\frac{x_{B}}{p_{B}^{2}}+2x_{B}\right)$.

We know from Assumption 2.3, that $\forall\mathbf{q^{\prime}}\in\mathcal{S}$
such that $\mathbb{P}_{\pi}(\mathbf{q^{\prime}}|\mathbf{q},a)>0$ it is true
that, $\|\mathbf{q^{\prime}}\|^{2}\leq c_{1}\|\mathbf{q}\|^{2}+c_{2}.$ Since
$\|\mathbf{q}\|^{2}=\|\mathbf{q}\|^{2},$,

$Q_{\pi}(\mathbf{q},a)-Q_{\pi}(\mathbf{q},a^{\prime})\leq\frac{2}{\epsilon}\left(c_{1}\|\mathbf{q}\|^{2}+c_{2}\right)+c_{3}$
(99)

Since the above inequality is true for all $a,a^{\prime}\in\mathcal{A}$,

$\left|Q_{\pi}(\mathbf{q},a)-Q_{\pi}(\mathbf{q},a^{\prime})\right|\leq\frac{2}{\epsilon}\left(c_{1}\|\mathbf{q}\|^{2}+c_{2}\right)+c_{3}$
(100)

Setting $c_{4}=\frac{2}{\epsilon}c_{2}+c_{3}$ yields the result. ∎

###  A.2 Proof of Step 3

The previous step provided us with bounds over the exact state action value
function. Here we incorporate the policy evaluation error in Equation 34 to
obtain bounds over the state action value function estimate.

######  Lemma A.8.

There exists a constant $c_{5}$ such that for all states
$\mathbf{q}\in\mathcal{S}$, all pairs of actions $a,a^{\prime}\in\mathcal{A}$,
and all policies $\pi$,

$\displaystyle\left|\widehat{Q}_{\pi}(\mathbf{q},a)-\widehat{Q}_{\pi}(\mathbf{q},a^{\prime})\right|\leq
c_{5}\|\mathbf{q}\|^{2}+c_{4}$

where $\widehat{Q}_{\pi}(\mathbf{q},a)$ is the estimate of
$Q_{\pi}(\mathbf{q},a)$ such that
$\left|\widehat{Q}_{\pi}(\mathbf{q},a)-Q_{\pi}(\mathbf{q},a)\right|\leq\kappa\|\mathbf{q}\|^{2},\forall
a\in\mathcal{A}.$

###### Proof.

$\displaystyle\left|\widehat{Q}_{\pi}(\mathbf{q},a)-\widehat{Q}_{\pi}(\mathbf{q},a^{\prime})\right|$
$\displaystyle=\left|\widehat{Q}_{\pi}(\mathbf{q},a)-Q_{\pi}(\mathbf{q},a)+Q_{\pi}(\mathbf{q},a)-\widehat{Q}_{\pi}(\mathbf{q},a^{\prime})+Q_{\pi}(\mathbf{q},a^{\prime})-Q_{\pi}(\mathbf{q},a^{\prime})\right|$
(101)
$\displaystyle\leq\left|\widehat{Q}_{\pi}(\mathbf{q},a)-Q_{\pi}(\mathbf{q},a)\right|+\left|\widehat{Q}_{\pi}(\mathbf{q},a^{\prime})-Q_{\pi}(\mathbf{q},a^{\prime})\right|$
(102)
$\displaystyle+\left|Q_{\pi}(\mathbf{q},a)-Q_{\pi}(\mathbf{q},a^{\prime})\right|$
(103)

From Equation 34 and Lemma A.7, it follows that,

$\left|\widehat{Q}_{\pi}(\mathbf{q},a)-\widehat{Q}_{\pi}(\mathbf{q},a^{\prime})\right|\leq\left(2\kappa+\frac{2}{\epsilon}c_{1}\right)\|\mathbf{q}\|^{2}+c_{4}$
(104)

Defining $c_{5}:=2\kappa+\frac{2}{\epsilon}c_{1}$ yields the result. ∎

###  A.3 Proof of Main theorem (Step 4)

The proof requires utilizing the performance difference lemma to establish a
connection between the difference in average cost associated with a policy
$\pi$ and the optimal average cost in terms of the state-action value function
$Q_{\pi}$.

######  Lemma A.9.

Let $J_{\pi}$ and $J_{\pi^{\prime}}$ be the expected infinite horizon average
cost associated with policies $\pi$ and $\pi^{\prime}$ respectively. Let
$d_{\pi}$ be the stationary distribution over state space $\mathcal{S}$
associated with $\mathbb{P}_{\pi}.$ Then it is true that,

$J_{\pi}-J_{\pi^{\prime}}=\sum_{\mathbf{q}\in\mathcal{S}}d_{\pi}(\mathbf{q})\left[Q_{\pi^{\prime}}(\mathbf{q},\pi(\mathbf{q}))-Q_{\pi^{\prime}}(\mathbf{q},\pi^{\prime}(\mathbf{q}))\right]$
(105)

where
$Q_{\pi^{\prime}}(\mathbf{q},\pi(\mathbf{q}))=\sum_{a\in\mathcal{A}}\pi(a|\mathbf{q})Q_{\pi^{\prime}}(\mathbf{q},a)$
and
$Q_{\pi^{\prime}}(\mathbf{q},\pi^{\prime}(\mathbf{q}))=V_{\pi^{\prime}}(\mathbf{q}).$

###### Proof.

The proof can be found in [Cao99]. ∎

We restate the theorem for convenience. See 3.1

###### Proof.

Let $J^{*}$ be the optimal average cost. Let $\pi^{*}\in\Pi$ be the optimal
policy. For any policy $\pi\in\Pi$, performance difference lemma provides the
following,

$\displaystyle J_{\pi}-J^{*}$ $\displaystyle=-\mathbb{E}_{\mathbf{q}\sim
d_{\pi^{*}}}\left[Q_{\pi}\left(\mathbf{q},\pi^{*}(\mathbf{q})\right)-Q_{\pi}\left(\mathbf{q},\pi(\mathbf{q})\right)\right]$
(106) $\displaystyle=-\mathbb{E}_{\mathbf{q}\sim
d_{\pi^{*}}}\Big{[}Q_{\pi}\left(\mathbf{q},\pi^{*}(\mathbf{q})\right)-\widehat{Q}_{\pi}\left(\mathbf{q},\pi^{*}(\mathbf{q})\right)+\widehat{Q}_{\pi}\left(\mathbf{q},\pi^{*}(\mathbf{q})\right)-Q_{\pi}\left(\mathbf{q},\pi(\mathbf{q})\right)$
(107)
$\displaystyle\qquad\qquad\qquad+\widehat{Q}_{\pi}\left(\mathbf{q},\pi(\mathbf{q})\right)-\widehat{Q}_{\pi}\left(\mathbf{q},\pi(\mathbf{q})\right)\Big{]}$
(108) $\displaystyle\leq\mathbb{E}_{\mathbf{q}\sim
d_{\pi^{*}}}\left[\left|Q_{\pi}\left(\mathbf{q},\pi^{*}(\mathbf{q})\right)-\widehat{Q}_{\pi}\left(\mathbf{q},\pi^{*}(\mathbf{q})\right)\right|\right]+\mathbb{E}_{\mathbf{q}\sim
d_{\pi^{*}}}\left[\left|Q_{\pi}\left(\mathbf{q},\pi(\mathbf{q})\right)-\widehat{Q}_{\pi}\left(\mathbf{q},\pi(\mathbf{q})\right)\right|\right]$
(109) $\displaystyle\qquad\qquad\qquad+\mathbb{E}_{\mathbf{q}\sim
d_{\pi^{*}}}\left[\widehat{Q}_{\pi}\left(\mathbf{q},\pi(\mathbf{q})\right)-\widehat{Q}_{\pi}\left(\mathbf{q},\pi^{*}(\mathbf{q})\right)\right]$
(110)

From Equation 34, we know that
$\left|Q_{\pi}\left(\mathbf{q},a\right)-\widehat{Q}_{\pi}\left(\mathbf{q},a\right)\right|\leq\kappa\|\mathbf{q}\|^{2}$
with probability $1-\frac{\delta}{2T}$. Hence we obtain the following:

$J_{\pi}-J^{*}\leq 2\kappa\mathbb{E}_{\mathbf{q}\sim
d_{\pi^{*}}}\|\mathbf{q}\|^{2}+\mathbb{E}_{\mathbf{q}\sim
d_{\pi^{*}}}\left[\widehat{Q}_{\pi}\left(\mathbf{q},\pi(\mathbf{q})\right)-\widehat{Q}_{\pi}\left(\mathbf{q},\pi^{*}(\mathbf{q})\right)\right]$
(111)

The total regret across time horizon $T$, with probability $1-\delta$, can be
expressed by summing the above inequality as follows,

$\sum_{k=1}^{T}J_{\pi_{k}}-J^{*}\leq 2\kappa T\mathbb{E}_{\mathbf{q}\sim
d^{\pi^{*}}}\|\mathbf{q}\|^{2}+\mathbb{E}_{\mathbf{q}\sim
d_{\pi^{*}}}\left[\sum_{k=1}^{T}\left(\widehat{Q}_{\pi_{k}}\left(\mathbf{q},\pi_{k}(\mathbf{q})\right)-\widehat{Q}_{\pi_{k}}\left(\mathbf{q},\pi^{*}(\mathbf{q})\right)\right)\right]$
(112)

where $\pi_{k}$ are policy iterates obtained through the NPG policy update
below:

$\pi_{k}(a|\mathbf{q})=\frac{\pi_{k-1}(a|\mathbf{q})\exp{\left(-\eta_{\mathbf{q}}\widehat{Q}_{\pi_{k-1}}(\mathbf{q},a)\right)}}{\sum_{l\in\mathcal{A}}\pi_{k-1}(l|\mathbf{q})\exp{\left(-\eta_{\mathbf{q}}\widehat{Q}_{\pi_{k-1}}(\mathbf{q},l)\right)}}$
(113)

The above update is performed for all $\mathbf{q}$ and $a\in\mathcal{A}$. Let
the update parameter
$\eta_{\mathbf{q}}=\sqrt{\frac{8\log|\mathcal{A}|}{T}}\frac{1}{M_{\mathbf{q}}}$,
where $M_{\mathbf{q}}=c_{5}\|\mathbf{q}\|^{2}+c_{4}.$ Then from Theorem 4.1,
it follows that,

$\displaystyle\sum_{k=1}^{T}J_{\pi_{k}}-J^{*}$ $\displaystyle\leq 2\kappa
T\mathbb{E}_{\mathbf{q}\sim
d_{\pi^{*}}}\|\mathbf{q}\|^{2}+\mathbb{E}_{\mathbf{q}\sim
d_{\pi^{*}}}\left[\sqrt{\frac{T\log|\mathcal{A}|}{2}}M_{\mathbf{q}}\right]$
(114) $\displaystyle=\left(\kappa
T+\sqrt{\frac{T\log|\mathcal{A}|}{2}}c_{5}\right)\mathbb{E}_{\mathbf{q}\sim
d_{\pi^{*}}}\left[\|\mathbf{q}\|^{2}\right]+c_{4}\sqrt{\frac{T\log|\mathcal{A}|}{2}}$
(115)

From Lemma A.1, it follows that $\mathbb{E}_{\mathbf{q}\sim
d_{\pi^{*}}}\left[\|\mathbf{q}\|^{2}\right]\leq\beta_{2}$. Hence,with
probability $1-\delta$, we obtain,

$\sum_{k=1}^{T}J_{\pi_{k}}-J^{*}\leq\kappa\beta_{2}T+\sqrt{T}\left(\sqrt{\frac{\log|\mathcal{A}|}{2}}c_{5}\beta_{2}+\sqrt{\frac{\log|\mathcal{A}|}{2}}c_{4}\right)$
(116)

Setting
$c^{\prime}=\left(\sqrt{\frac{\log|\mathcal{A}|}{2}}c_{5}\beta_{2}+\sqrt{\frac{\log|\mathcal{A}|}{2}}c_{4}\right)$
and $c^{\prime\prime}=\kappa\beta_{2}$ yields the result in the theorem. ∎