# A Simple Finite-Time Analysis of TD Learning with Linear Function
Approximation

Aritra Mitra A. Mitra is with the Department of Electrical and Computer
Engineering, North Carolina State University. Email<EMAIL_ADDRESS>
###### Abstract

We study the finite-time convergence of TD learning with linear function
approximation under Markovian sampling. Existing proofs for this setting
either assume a projection step in the algorithm to simplify the analysis, or
require a fairly intricate argument to ensure stability of the iterates. We
ask: Is it possible to retain the simplicity of a projection-based analysis
without actually performing a projection step in the algorithm? Our main
contribution is to show this is possible via a novel two-step argument. In the
first step, we use induction to prove that under a standard choice of a
constant step-size $\alpha$, the iterates generated by TD learning remain
uniformly bounded in expectation. In the second step, we establish a recursion
that mimics the steady-state dynamics of TD learning up to a bounded
perturbation on the order of $O(\alpha^{2})$ that captures the effect of
Markovian sampling. Combining these pieces leads to an overall approach that
considerably simplifies existing proofs. We conjecture that our inductive
proof technique will find applications in the analyses of more complex
stochastic approximation algorithms, and conclude by providing some examples
of such applications.

##  1 Introduction

We study sequential decision-making within the framework of a Markov Decision
Process (MDP) with a finite state and action space. At each time-step, an
agent/learner interacts with an environment by playing an action, observing a
reward for this action, and transitioning to a new state in the MDP. The
reward functions and probability transition kernels of the MDP that generate
the agent’s observations are _unknown_ to the agent. Via repeated interactions
with the environment, the goal of the agent is to learn a policy (sequence of
actions) that maximizes a long-term cumulative return. In this paper, we focus
on the simpler problem of _policy evaluation_ : estimating the expected
infinite-horizon cumulative discounted return - known as the value function -
corresponding to a _fixed_ policy. To solve this policy evaluation problem,
Sutton introduced a family of on-line incremental algorithms known as
_temporal-difference_ (TD) methods in his 1988 paper [1]. While these
algorithms are easy to describe and implement, their analyses turn out to be
quite non-trivial: in [2], Tsitsiklis and Van Roy note: “ _Though temporal-
difference learning is simple and elegant, a rigorous analysis of its behavior
requires significant sophistication_ ”. This is more so the case when in
practice, due to large state spaces, a function approximator is used to
approximate the value function. In this context, our goal is to provide a
short and accessible _finite-time_ convergence proof of TD learning with
linear function approximation. Before we explain our contribution in this
regard, it is instructive to briefly summarize what is known for this setting.

Related Work. The first paper to provide an asymptotic convergence analysis
for TD learning with linear function approximation was [2]. This was achieved
by viewing TD methods as instances of stochastic approximation algorithms [3,
4]. While the results in [2] provided foundational insights, they came with no
rates. In the years to come, several papers did manage to provide finite-time
convergence rates for TD learning [5, 6, 7, 8]; however, their analyses made
the restrictive assumption that the data samples used for performing updates
are generated in an i.i.d. manner over time from the stationary distribution
of the underlying Markov chain (induced by the policy). In reality, however,
these samples are all part of a single trajectory generated by the Markov
chain, and, as such, exhibit _temporal correlations_. It is precisely these
temporal correlations that make the analysis of even the simplest TD method -
known as TD(0) - quite non-trivial.

By making interesting connections to the dynamics of stochastic gradient
descent (SGD), the authors in [9] were able to provide the first finite-time
analysis of TD learning under Markovian sampling. However, their analysis
hinges crucially on a projection step in the algorithm to ensure that the
iterates generated by the projected TD method remain uniformly bounded. To
summarize, all the papers above either only provide asymptotic rates, or
assume i.i.d. sampling, or assume a projection step. To our knowledge, the
first paper to provide finite-time mean-square error bounds for TD learning
with linear function approximation under Markovian sampling _without a
projection step_ was [10]. The approach in [10] is control-theoretic, where
the authors draw on Lyapunov theory for analyzing the stability of linear
dynamical systems. While the analysis in [10] is elegant, it requires a
relatively more involved argument than the simpler projection-based analysis
in [9]. This leads to the main question we investigate in this paper: _Is it
possible to retain the simplicity of a projection-based analysis without
actually performing a projection step in the algorithm?_

Our Contribution. We start by answering the above question in the affirmative
for the TD(0) algorithm with linear function approximation. Our proof is
simple, and relies on a novel inductive argument. In what follows, we provide
the crux of the argument; the details are deferred to Section 3. Like in any
standard stochastic optimization proof, we first use the update rule to write
down a recursion for the mean-squared error. With little algebra, the right
hand side of this recursion can be effectively decomposed into three terms:
(i) an exponentially decaying term that captures the “steady-state” dynamics
of TD(0); (ii) a noise variance term that is typical of any noisy iterative
algorithm; and (iii) a term that captures an additional error due to Markovian
sampling.

In the absence of the third term, the proof would be standard, akin to an SGD
(stochastic gradient descent) analysis under i.i.d. noise. We view the third
term as a disturbance; the rationale for this will become clear soon. Unlike
an input-to-stability argument in control where a uniformly bounded
disturbance excites a stable system, the disturbance in our case depends on
the _time-varying iterates_. At this stage, a projection step would greatly
simplify the analysis since we could then argue boundedness of the iterates,
and hence, of the disturbance. However, recall that we do not assume a
projection step. So is there a simple way then to control the disturbance
term? Yes, this is where our novel inductive idea kicks in. By assuming a
suitable uniform bound in expectation - say $B$ \- on the past iterates as
part of our induction hypothesis, we bound the disturbance term. Plugging this
bound back into our main recursion, we are able to then show that the same
uniform bound $B$ applies to the new iterate. In short, we show in Theorem 1
that under a standard choice of a constant step-size $\alpha$, the iterates
generated by TD(0) remain uniformly bounded in expectation. The proof of this
result is the main contribution of our work. Armed with Theorem 1, we go back
to the main recursion with the knowledge that the disturbance term is an
$O(\alpha^{2})$ uniformly bounded perturbation, of the same order as the noise
variance. The rest is trivial.

Motivation and Applications. One might ask: Why care about this new proof
technique? Here are our reasons. First, each new analysis of TD learning -
like ours - sheds new insights into the dynamics of a rather complex
stochastic process. Second, as we discuss in Section 4, the scope of our
inductive proof technique extends well beyond TD(0) to a much broader class of
general (potentially nonlinear) stochastic approximation schemes that include
the TD($\lambda$) family (with linear function approximation) and variants of
Q-learning as special cases. Finally, perhaps the most compelling reason is
the following. Iterative optimization algorithms like SGD form the cornerstone
of almost all large-scale machine learning applications for a reason: SGD is
_provably robust_ to a variety of structured perturbations that invariably
show up in these applications, e.g., delays, asynchrony, quantization and
compression errors, and adversarial corruption. However, it remains poorly
understood whether even basic reinforcement learning (RL) algorithms like the
TD methods are robust to similar perturbations. In principle, one can view the
effect of these perturbations as a disturbance (potentially iterate-dependent)
to the nominal dynamics, much like the effect of Markovian noise. Lumping all
the disturbances together, a natural next step could then be to apply the
inductive proof technique we outlined earlier. In a companion paper [11], we
show that this approach is essential to deriving tight rates for a broad class
of stochastic approximation algorithms perturbed by time-varying delays and
Markovian noise - a challenging setting that was previously unexplored. In
Section 4, we also explain that it is unclear whether the existing approach in
[10] can handle such time-varying delays; in fact, this was precisely the
motivation for developing the technique in this paper. Thus, we believe that
the simplicity of our approach can help reason about the robustness of various
complex stochastic approximation algorithms, beyond what we cover in this
note.

##  2 Background on TD Learning

In this section, we set up notation and provide the necessary technical
background. Given a positive integer $n$, we use $[n]$ to denote the set
$\\{1,2,\ldots,n\\}.$ Unless otherwise stated, we will use $\|\cdot\|$ to
denote the standard Euclidean norm. We consider a Markov Decision Process
(MDP) denoted by
$\mathcal{M}=(\mathcal{S},\mathcal{A},\mathcal{P},\mathcal{R},\gamma)$, where
$\mathcal{S}$ is a finite state space of size $n$, $\mathcal{A}$ is a finite
action space, $\mathcal{P}$ is a set of action-dependent Markov transition
kernels, $\mathcal{R}$ is a reward function, and $\gamma\in(0,1)$ is the
discount factor. A deterministic policy
$\mu:\mathcal{S}\rightarrow\mathcal{A}$ is a mapping from the states to the
actions. When a fixed policy $\mu$ interacts with the underlying MDP, it
generates a Markov reward process (MRP) characterized by a transition matrix
$P_{\mu}$, and a reward function $R_{\mu}$. At a given state $s$, upon playing
the action $\mu(s)$, an agent receives an expected instantaneous reward
denoted by $R_{\mu}(s)$, and its probability of transitioning from state $s$
to state $s^{\prime}$ is given by $P_{\mu}(s,s^{\prime})$. The discounted
expected cumulative reward obtained by playing policy $\mu$ starting from
initial state $s$ is given by:

$V_{\mu}(s)=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}R_{\mu}(s_{t})|s_{0}=s\right],$
(1)

where $s_{t}$ represents the state of the Markov chain (induced by $\mu$) at
time $t$, when initiated from $s_{0}=s$. In essence, the value function
$V_{\mu}$ measures the “goodness” of the policy $\mu$, and the central goal in
RL is to find an optimal policy that simultaneously maximizes
$V_{\mu}(s),\forall s\in\mathcal{S}.$ For an MDP with finite state and action
spaces, such a (deterministic) optimal policy is known to always exist [12].
We will primarily focus on the simpler task of policy evaluation, where the
goal is to evaluate the value function $V_{\mu}$ corresponding to a fixed
policy $\mu$.111Later in Section 4, we will comment on how our developments
also aid the problem of finding the optimal policy. It is well-known [2] that
$V_{\mu}$ is the fixed point of the policy-specific Bellman operator
$\mathcal{T}_{\mu}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$, i.e.,
$\mathcal{T}_{\mu}V_{\mu}=V_{\mu}$, where for any $V\in\mathbb{R}^{n}$,

$(\mathcal{T}_{\mu}V)(s)=R_{\mu}(s)+\gamma\sum_{s^{\prime}\in\mathcal{S}}P_{\mu}(s,s^{\prime})V(s^{\prime}),\hskip
2.84526pt\forall s\in\mathcal{S}.$ (2)

When the underlying MDP is known, the above key property is sufficient to
devise a simple dynamic programming approach that guarantees convergence to
the value function $V_{\mu}$ [12]. Our interest is however in the RL setting
where the state transition matrices and the reward functions of the MDP are
_unknown_. In addition to this challenge, for contemporary RL applications,
the size of the state space $\mathcal{S}$ can be extremely large. This renders
the task of estimating $V_{\mu}$ exactly (based on observations of rewards and
state transitions) intractable. The common workaround is to consider a
parametric approximation $\hat{V}_{\theta}$ of $V_{\mu}$ in the linear
subspace spanned by a set $\\{\phi_{k}\\}_{k\in[K]}$ of $K\ll n$ basis
vectors, where
$\phi_{k}=[\phi_{k}(1),\ldots,\phi_{k}(n)]^{\top}\in\mathbb{R}^{n}$.
Specifically, we have
$\hat{V}_{\theta}(s)=\sum_{k=1}^{K}\theta(k)\phi_{k}(s),$ where
$\theta=[\theta(1),\ldots,\theta(K)]^{\top}\in\mathbb{R}^{K}$ is a
weight/parameter vector. Let $\Phi\in\mathbb{R}^{n\times K}$ be a matrix with
$\phi_{k}$ as its $k$-th column; we then have $\hat{V}_{\theta}=\Phi\theta$.
Let us also denote the $s$-th row of $\Phi$ by $\phi(s)\in\mathbb{R}^{K}$, and
refer to it as the feature vector for state $s$. For each state
$s\in\mathcal{S}$, we then have:
$\hat{V}_{\theta}(s)=\langle\phi(s),\theta\rangle$. To proceed, we will make
the standard assumption that the columns of $\Phi$ are linearly independent,
and that the feature vectors are normalized, i.e., for each $s\in\mathcal{S}$,
$\|\phi(s)\|^{2}\leq 1$ [9]. Given this premise, the problem of interest is to
find the parameter $\theta^{*}$ corresponding to the best parametric
approximation (in a suitable norm) of $V_{\mu}$. We now describe the classical
TD(0) algorithm [1] \- due to Sutton - for achieving this goal.

The TD(0) Algorithm. Starting from an initial parameter estimate $\theta_{0}$,
the TD(0) algorithm operates as follows. At each time-step $t=0,1,\ldots$, an
observation in the form of a data tuple
$X_{t}=(s_{t},s_{t+1},r_{t}=R_{\mu}(s_{t}))$ is received. The tuple comprises
the current state $s_{t}$, the next state $s_{t+1}$ reached by playing action
$\mu(s_{t})$, and the instantaneous reward $r_{t}$. Given this tuple $X_{t}$,
the current parameter $\theta_{t}$ is updated by moving along the TD(0) update
direction; for a fixed $\theta\in\mathbb{R}^{K}$, we define this direction
$g_{t}(\theta)=g(\theta;X_{t})$ as follows:

$g_{t}(\theta)\triangleq\left(r_{t}+\gamma\langle\phi(s_{t+1}),\theta\rangle-\langle\phi(s_{t}),\theta\rangle\right)\phi(s_{t}),\forall\theta\in\mathbb{R}^{K}.$

The TD(0) update rule can then be described as

$\theta_{t+1}=\theta_{t}+\alpha_{t}g_{t}(\theta_{t}),$ (3)

where $\alpha_{t}\in(0,1)$ is the step-size/learning rate. Our main goal in
this paper is to provide a short non-asymptotic proof of convergence for the
above algorithm. To do so, we will make the following standard assumption [2,
9, 10].

######  Assumption 1.

The Markov chain induced by the policy $\mu$ is aperiodic and irreducible.

For the value functions to be well-defined, we will also make the standard
assumption that $\exists\bar{r}>0$ such that $R_{\mu}(s)\leq\bar{r},\forall
s\in\mathcal{S}.$ Under these assumptions, Tsitsiklis and Van Roy showed that
with a suitable step-size sequence $\\{\alpha_{t}\\}$, the iterates generated
by Eq. (3) converge almost surely to the best linear approximator of $V_{\mu}$
in the span of $\\{\phi_{k}\\}_{k\in[K]}$ [2]. To be more precise, we note
that under Assumption 1, the Markov chain induced by the policy $\mu$ admits a
unique stationary distribution $\pi$ [13]. Let $D$ be a diagonal matrix with
$D(i,i)=\pi(i),\forall i\in[n].$ Moreover, let $\Pi_{D}(\cdot)$ denote the
projection operator onto the subspace spanned by $\\{\phi_{k}\\}_{k\in[K]}$
with respect to the inner product $\langle\cdot,\cdot\rangle_{D}$. Then, the
main result in [2] shows that $\theta_{t}\rightarrow\theta^{*}$ with
probability $1$, where $\theta^{*}$ is the unique solution of the projected
Bellman equation $\Pi_{D}\mathcal{T}_{\mu}(\Phi\theta^{*})=\Phi\theta^{*}$.
Notably, this result is _asymptotic_ : it does not provide a sense of the
_rate_ at which $\theta_{t}$ approaches $\theta^{*}$ as a function of the
discrete time-index $t$. An object that provides a lot of intuition about the
rate is the “steady-state” version of the TD(0) update direction, defined as
follows:

$\bar{g}(\theta)\triangleq\mathbb{E}_{s_{t}\sim\pi,s_{t+1}\sim
P_{\mu}(\cdot|s_{t})}\left[g(\theta;X_{t})\right],\forall\theta\in\mathbb{R}^{K}.$
(4)

In [9], it was shown that the _deterministic_ steady-state recursion
$\theta_{t+1}=\theta_{t}+\alpha\bar{g}(\theta_{t})$ converges _linearly_ to
$\theta^{*}$ with a suitable step-size $\alpha$. To extend this result to the
stochastic recursion in (3), we will require the notion of a mixing time.

######  Definition 1.

Define $\tau_{\epsilon}\triangleq\min\\{t\geq
1:\|\mathbb{E}\left[g(\theta;X_{k})|X_{0}\right]-\bar{g}(\theta)\|\leq\epsilon\left(\|\theta\|+1\right),\forall
k\geq t,\forall\theta\in\mathbb{R}^{K},\forall X_{0}\\}.$

A key implication of Assumption 1 is that the total variation distance between
the conditional distribution $\mathbb{P}\left(s_{t}=\cdot|s_{0}=s\right)$ and
the stationary distribution $\pi$ decays geometrically fast, regardless of the
initial state $s\in\mathcal{S}$ [13]. This, in turn, immediately implies that
$\tau_{\epsilon}$ in Definition 1 is $O\left(\log(1/\epsilon)\right)$ [14].
For our purpose, we will set the precision $\epsilon=\alpha$, and henceforth
simply use $\tau$ as a shorthand for $\tau_{\alpha}$. By exploiting the
geometric mixing property above, and by making elegant connections to smooth
and strongly convex optimization using (stochastic) gradient descent, the
authors in [9] were able to provide a finite-time convergence rate for TD(0).
However, as explained in the Introduction, the analysis in [9] crucially
relies on a projection step to control the effect of temporal correlations in
the data tuples - a consequence of Markovian sampling. _Can we continue to
leverage the insights from optimization in[9], while analyzing the TD(0)
update rule in (3) without projection?_ The next section answers this question
in the affirmative.

##  3 Convergence Analysis

We start by compiling a few basic results that will aid our subsequent
analysis. The first such result provides the connection to optimization: it
shows that the steady-state TD(0) update direction $\bar{g}(\theta)$ acts like
a “pseudo-gradient”, driving the TD(0) iterates towards the minimizer
$\theta^{*}$ of the projected Bellman equation. A proof of this result was
provided in [9]. We provide an alternate proof in the Appendix to keep the
paper self-contained.

######  Lemma 1.

The following holds $\forall\theta\in\mathbb{R}^{K}$:

$\langle\theta^{*}-\theta,\bar{g}(\theta)\rangle\geq\omega(1-\gamma)\|\theta^{*}-\theta\|^{2},$

where $\omega$ is the smallest eigenvalue of the matrix
$\Sigma=\Phi^{\top}D\Phi$.

Under the assumptions on the feature matrix $\Phi$ in Section 2, and
Assumption 1, it is easy to see that $\Sigma$ is positive definite with
$\omega\in(0,1).$ We will make use of the fact that the TD(0) update
direction, along with its steady-state version, are both $2$-Lipschitz, i.e.,
$\forall t\in\mathbb{N}$, and $\forall\theta_{1},\theta_{2}\in\mathbb{R}^{K}$,

$\max\\{\|\bar{g}(\theta_{1})-\bar{g}(\theta_{2})\|,\|{g}_{t}(\theta_{1})-{g}_{t}(\theta_{2})\|\\}\leq
2\|\theta_{1}-\theta_{2}\|.$ (5)

Next, at several points in our analysis, we will invoke the following bound on
the norm of the TD(0) update direction:

$\|g_{t}(\theta)\|\leq 2\|\theta\|+2\bar{r}\leq 2\|\theta\|+2\sigma,\forall
t\in\mathbb{N},\forall\theta\in\mathbb{R}^{K},$ (6)

where $\sigma=\max\\{1,\bar{r},\|\theta^{*}\|\\}.$ This immediately yields:

$\|g_{t}(\theta)\|\leq 2\|\theta-\theta^{*}\|+4\sigma,\forall
t\in\mathbb{N},\forall\theta\in\mathbb{R}^{K}.$ (7)

The bounds in Eq. (5) and Eq. (6) follow straightforwardly from the fact that
the TD(0) update direction $g_{t}(\theta)$ is affine in the parameter
$\theta$. Hence, we omit the proof here; an interested reader can take a look
at [15]. Since $\bar{g}(\theta^{*})=0$ (see [2]), the Lipschitz property in
(5) implies

$\|\bar{g}(\theta)\|\leq
2\|\theta-\theta^{*}\|,\forall\theta\in\mathbb{R}^{K}.$ (8)

Let us now provide some intuition behind our analysis. Throughout, to present
our arguments in a clean way, we will use the big-$O$ notation to suppress
universal constants. We begin by defining a couple of objects for all $t\geq
0$:

$d_{t}\triangleq\mathbb{E}[\|\theta_{t}-\theta^{*}\|^{2}],\hskip
5.69054pte_{t}\triangleq\mathbb{E}[\langle\theta_{t}-\theta^{*},g_{t}(\theta_{t})-\bar{g}(\theta_{t})\rangle].$
(9)

Now observe from the update rule (3) that

$\displaystyle\|\theta_{t+1}-\theta^{*}\|^{2}$
$\displaystyle=\|\theta_{t}-\theta^{*}\|^{2}+2\alpha\langle\theta_{t}-\theta^{*},g_{t}(\theta_{t})\rangle+\alpha^{2}\|g_{t}(\theta_{t})\|^{2}$
$\displaystyle=\|\theta_{t}-\theta^{*}\|^{2}+2\alpha\langle\theta_{t}-\theta^{*},\bar{g}(\theta_{t})\rangle+\alpha^{2}\|g_{t}(\theta_{t})\|^{2}$
$\displaystyle\hskip
5.69054pt+2\alpha\langle\theta_{t}-\theta^{*},g_{t}(\theta_{t})-\bar{g}(\theta_{t})\rangle$
$\displaystyle\leq\left(1-2\alpha\omega(1-\gamma)+8\alpha^{2}\right)\|\theta_{t}-\theta^{*}\|^{2}+32\alpha^{2}\sigma^{2}$
$\displaystyle\hskip
5.69054pt+2\alpha\langle\theta_{t}-\theta^{*},g_{t}(\theta_{t})-\bar{g}(\theta_{t})\rangle,$

where in the last step, we used Lemma 1 and Eq. (7). Taking expectations on
both sides of the above display then yields:

$\boxed{d_{t+1}\leq\underbrace{\left(1-2\alpha\omega(1-\gamma)+8\alpha^{2}\right)d_{t}}_{T_{1}}+\underbrace{32\alpha^{2}\sigma^{2}}_{T_{2}}+\underbrace{2\alpha
e_{t}}_{T_{3}}.}$ (10)

We are left to analyze the key recursion above. Notice that the right hand
side of the above recursion features three terms: (i) the term $T_{1}$
captures the steady-state behavior of TD(0); (ii) the term $T_{2}$ is a noise
variance term that typically shows up in the analysis of any noisy iterative
algorithm (e.g., SGD); and (iii) the term $T_{3}$ captures the effect of
Markovian sampling. In the absence of the third term, one can immediately see
from Eq. (10) that with a suitably chosen step-size $\alpha$, the iterates
would converge linearly (in the mean-square sense) to a ball of radius
$O(\alpha\sigma^{2})$ centered around the optimal parameter $\theta^{*}$.
Moreover, the proof would be near-identical to that of SGD. Intuitively, if we
could thus show that $T_{3}=O(\alpha^{2}\sigma^{2})$, i.e., the same order as
$T_{2}$, we would be done. However, observe from Eq. (9) that $e_{t}$ depends
on the current iterate $\theta_{t}$; as such, we cannot directly claim a
uniform upper bound on $T_{3}$ in the absence of a projection step. For a
moment, suppose we wish to overcome this difficulty via an inductive argument
where we assume a uniform upper bound - say $B$ \- on all the iterates up to
time $t$. Our goal would then be to appeal to Eq. (10) to show that the same
bound $B$ applies to the iterate at time $t+1$. Unfortunately, a naive
inductive argument such as the one above would only tell us that $T_{3}$ is an
$O(\alpha)$ perturbation. The issue with this bound is that it is too loose:
we wanted an $O(\alpha^{2})$ additive perturbation, but ended up with an
$O(\alpha)$ perturbation. The reason why we fell short of our desired outcome
is because we did not exploit the additional structure in $e_{t}$: the
geometric mixing property in Definition 1 tells us that eventually, $e_{t}$
should be “small”. Thus, we need a finer inductive argument that leverages
this fact.

Our first step in providing such an argument is a result that simply states
that for a step-size $\alpha$ that scales inversely with the mixing time
$\tau$, the iterate sequence $\\{\theta_{t}\\}$ will remain uniformly bounded
for the first $\tau$ time-steps. This result will serve as the base case of
our subsequent induction argument.

######  Lemma 2.

Suppose $\alpha\leq 1/(8\tau).$ Define $B\triangleq
10\max\\{\|\theta_{0}-\theta^{*}\|^{2},\sigma^{2}\\}.$ Then, we have:

$\|\theta_{k}-\theta^{*}\|^{2}\leq B,\forall k\in[\tau].$ (11)

###### Proof.

From the update rule (3), we have

$\displaystyle\|\theta_{t+1}-\theta^{*}\|$
$\displaystyle\leq\|\theta_{t}-\theta^{*}\|+\alpha\|g_{t}(\theta_{t})\|$ (12)
$\displaystyle\leq(1+2\alpha)\|\theta_{t}-\theta^{*}\|+4\alpha\sigma,$

where we used (7) in the second step. Iterating the above inequality yields
the following $\forall k\in[\tau]$:

$\displaystyle\|\theta_{k}-\theta^{*}\|$
$\displaystyle\leq(1+2\alpha)^{k}\|\theta_{0}-\theta^{*}\|+4\alpha\sigma\sum_{j=0}^{k-1}(1+2\alpha)^{j}$
$\displaystyle\leq(1+2\alpha)^{\tau}\|\theta_{0}-\theta^{*}\|+4\alpha\tau(1+2\alpha)^{\tau}\sigma$
$\displaystyle\leq 2\|\theta_{0}-\theta^{*}\|+8\alpha\tau\sigma$
$\displaystyle\leq 2\|\theta_{0}-\theta^{*}\|+\sigma,$

where in the third step, we used $(1+x)\leq\exp(x),\forall x\in\mathbb{R}$ to
deduce that $(1+2\alpha)^{\tau}\leq\exp(0.25)<2$, for $\alpha\leq 1/(8\tau).$
Squaring both sides of the final inequality above leads to the desired claim.
∎

Our next goal is to show that a bound akin to that in the above lemma applies
to time-steps greater than $\tau$ as well. To that end, we need the following
intermediate result.

######  Lemma 3.

Consider any $t\geq\tau.$ Suppose $d_{k}\leq B,\forall k\in[t].$ Then, the
following is true:

$\mathbb{E}[\|\theta_{t}-\theta_{t-\tau}\|^{2}]\leq O(\alpha^{2}\tau^{2}B).$

###### Proof.

Observe:

$\displaystyle\|\theta_{t}-\theta_{t-\tau}\|$
$\displaystyle\leq\sum_{k=t-\tau}^{t-1}\|\theta_{k+1}-\theta_{k}\|$ (13)
$\displaystyle\leq\alpha\sum_{k=t-\tau}^{t-1}\|g_{k}(\theta_{k})\|$
$\displaystyle\leq
O(\alpha)\sum_{k=t-\tau}^{t-1}\left(\|\theta_{k}-\theta^{*}\|+\sigma\right),$

where in the last step, we used (7). Squaring both sides of the above
inequality, and taking expectations, we obtain

$\displaystyle\mathbb{E}[\|\theta_{t}-\theta_{t-\tau}\|^{2}]$
$\displaystyle\leq O(\alpha^{2}\tau)\sum_{k=t-\tau}^{t-1}(d_{k}+\sigma^{2})$
(14) $\displaystyle\leq O(\alpha^{2}\tau^{2}B),$

where we used $d_{k}\leq B,\,\forall k\in[t]$, and $\sigma^{2}\leq B$. ∎

The final piece we need to complete our main inductive argument is the
following lemma.

######  Lemma 4.

Consider any $t\geq\tau.$ Suppose $d_{k}\leq B,\forall k\in[t].$ Then, the
following is true: $e_{t}\leq O(\alpha\tau B).$

###### Proof.

Let us start with the following decomposition:
$\langle\theta_{t}-\theta^{*},g_{t}(\theta_{t})-\bar{g}(\theta_{t})\rangle=T_{1}+T_{2}+T_{3}+T_{4}$,
where

$\displaystyle T_{1}$
$\displaystyle=\langle\theta_{t}-\theta_{t-\tau},g_{t}(\theta_{t})-\bar{g}(\theta_{t})\rangle,$
$\displaystyle T_{2}$
$\displaystyle=\langle\theta_{t-\tau}-\theta^{*},g_{t}(\theta_{t-\tau})-\bar{g}(\theta_{t-\tau})\rangle,$
$\displaystyle T_{3}$
$\displaystyle=\langle\theta_{t-\tau}-\theta^{*},g_{t}(\theta_{t})-g_{t}(\theta_{t-\tau})\rangle,\hskip
5.69054pt\textrm{and}$ $\displaystyle T_{4}$
$\displaystyle=\langle\theta_{t-\tau}-\theta^{*},\bar{g}(\theta_{t-\tau})-\bar{g}(\theta_{t})\rangle.$

We will now argue that $\mathbb{E}[T_{i}]\leq O(\alpha\tau B),\forall
i\in\\{1,2,3,4\\}.$ For $T_{1}$, observe that:

$\displaystyle T_{1}$
$\displaystyle\leq\|\theta_{t}-\theta_{t-\tau}\|\|g_{t}(\theta_{t})-\bar{g}(\theta_{t})\|$
$\displaystyle\leq\frac{1}{2\alpha\tau}\|\theta_{t}-\theta_{t-\tau}\|^{2}+\frac{\alpha\tau}{2}\|g_{t}(\theta_{t})-\bar{g}(\theta_{t})\|^{2}$
$\displaystyle\leq\frac{1}{2\alpha\tau}\|\theta_{t}-\theta_{t-\tau}\|^{2}+\alpha\tau\left(\|g_{t}(\theta_{t})\|^{2}+\|\bar{g}(\theta_{t})\|^{2}\right)$
$\displaystyle\overset{\eqref{eqn:nrmbnd},\eqref{eqn:nrmbnd2}}{\leq}\frac{1}{2\alpha\tau}\|\theta_{t}-\theta_{t-\tau}\|^{2}+O(\alpha\tau)\left(\|\theta_{t}-\theta^{*}\|^{2}+\sigma^{2}\right).$

Now taking expectations on both sides of the above inequality, invoking Lemma
3, and using $d_{t}\leq B$, we conclude that $\mathbb{E}[T_{1}]\leq
O(\alpha\tau B).$

Next, for $T_{3}$, we have

$\displaystyle T_{3}$
$\displaystyle\leq\|\theta_{t-\tau}-\theta^{*}\|\|g_{t}(\theta_{t})-{g}_{t}(\theta_{t-\tau})\|$
$\displaystyle\overset{\eqref{eqn:Lipschitz}}{\leq}2\|\theta_{t-\tau}-\theta^{*}\|\|\theta_{t}-\theta_{t-\tau}\|$
$\displaystyle\leq\frac{1}{\alpha\tau}\|\theta_{t}-\theta_{t-\tau}\|^{2}+\alpha\tau\|\theta_{t-\tau}-\theta^{*}\|^{2}.$

Taking expectations on both sides of the above inequality and using Lemma 3
yields:

$\mathbb{E}[T_{3}]\leq O(\alpha\tau B)+\alpha\tau d_{t-\tau}\leq O(\alpha\tau
B),$

where in the last step, we used $d_{k}\leq B,\forall k\in[t].$ The fact that
$\mathbb{E}[T_{4}]\leq O(\alpha\tau B)$ follows exactly the same analysis as
above. We are left to bound $T_{2}$; _this is the only place in the entire
proof where we will exploit the geometric mixing property of the underlying
Markov chain._ We proceed as follows.

$\displaystyle\mathbb{E}\left[T_{2}\right]$
$\displaystyle=\mathbb{E}\left[\langle\theta_{t-\tau}-\theta^{*},g_{t}(\theta_{t-\tau})-\bar{g}(\theta_{t-\tau})\rangle\right]$
$\displaystyle=\mathbb{E}\left[\mathbb{E}\left[\langle\theta_{t-\tau}-\theta^{*},g_{t}(\theta_{t-\tau})-\bar{g}(\theta_{t-\tau})\rangle|\theta_{t-\tau},X_{t-\tau}\right]\right]$
$\displaystyle=\mathbb{E}\left[\langle\theta_{t-\tau}-\theta^{*},\mathbb{E}\left[g_{t}(\theta_{t-\tau})-\bar{g}(\theta_{t-\tau})|\theta_{t-\tau},X_{t-\tau}\right]\rangle\right]$
$\displaystyle\leq\mathbb{E}\left[\|\theta_{t-\tau}-\theta^{*}\|\|\mathbb{E}\left[g_{t}(\theta_{t-\tau})-\bar{g}(\theta_{t-\tau})|\theta_{t-\tau},X_{t-\tau}\right]\|\right]$
$\displaystyle\overset{(a)}{\leq}\alpha\mathbb{E}\left[\|\theta_{t-\tau}-\theta^{*}\|\left(1+\|\theta_{t-\tau}\|\right)\right]$
$\displaystyle\leq\alpha\mathbb{E}\left[\|\theta_{t-\tau}-\theta^{*}\|\left(1+\|\theta^{*}\|+\|\theta_{t-\tau}-\theta^{*}\|\right)\right]$
$\displaystyle\overset{(b)}{\leq}\alpha\mathbb{E}\left[\|\theta_{t-\tau}-\theta^{*}\|\left(2\sigma+\|\theta_{t-\tau}-\theta^{*}\|\right)\right]$
$\displaystyle\leq
O(\alpha)\mathbb{E}\left[\|\theta_{t-\tau}-\theta^{*}\|^{2}+\sigma^{2}\right]$
$\displaystyle\overset{(c)}{\leq}O(\alpha)\left(d_{t-\tau}+\sigma^{2}\right)=O(\alpha
B),$

where (a) follows from the definition of the mixing time $\tau$ in Definition
1; (b) follows from recalling that
$\sigma=\max\\{1,\bar{r},\|\theta^{*}\|\\}$; and (c) follows from us again
using $d_{k}\leq B,\forall k\in[t]$. This concludes the proof. ∎

We are now ready to state and prove the key technical result that guarantees
uniform boundedness of the iterates under a suitable choice of the step-size
$\alpha$.

######  Theorem 1.

(Boundedness of Iterates) There exists a universal constant $C\geq 8$ such
that for

$\alpha\leq\frac{\omega(1-\gamma)}{C\tau},$ (15)

the following is true: $d_{t}\leq B,\forall t\geq 0.$

###### Proof.

We will prove this result via induction. For the base case of induction, note
that we have already established in Lemma 2 that $d_{k}\leq B,\forall
k\in[\tau]$. Now consider any $t\geq\tau$, and suppose that $d_{k}\leq
B,\forall k\in[t].$ We will now show that under the requirement on the step-
size $\alpha$ in the statement of the lemma, it holds that $d_{t+1}\leq B.$ To
that end, starting from the main recursion in Eq. (10), we have (using
$\sigma^{2}\leq B$):

$\displaystyle d_{t+1}$
$\displaystyle\leq{\left(1-2\alpha\omega(1-\gamma)+8\alpha^{2}\right)d_{t}}+{32\alpha^{2}B}+{2\alpha
e_{t}}$ $\displaystyle d_{t+1}$
$\displaystyle\overset{(a)}{\leq}\left(1-2\alpha\omega(1-\gamma)+8\alpha^{2}\right)d_{t}+O(\alpha^{2}\tau
B)$
$\displaystyle\overset{(b)}{\leq}\left(1-2\alpha\omega(1-\gamma)+\alpha^{2}(8+O(\tau))\right)B.$

For (a), we used the induction hypothesis in tandem with Lemma 4; for (b), we
invoked the induction hypothesis again. We conclude that there exists some
universal constant $C\geq 8$ such that

$d_{t+1}\leq\left(1-2\alpha\omega(1-\gamma)+C\alpha^{2}\tau\right)B\leq(1-\alpha\omega(1-\gamma))B\leq
B,$

where we used the choice of the step-size in Eq. (15). This establishes the
induction claim and completes the proof. ∎

The final convergence rate for TD learning now follows almost immediately.

######  Theorem 2.

Suppose the step-size $\alpha$ is chosen as in Eq. (15). Then, the following
is true for all $t\geq\tau$:

$d_{t+1}\leq(1-\alpha\omega(1-\gamma))d_{t}+O(\alpha^{2}\tau B).$

###### Proof.

Now that we have argued in Theorem 1 that $d_{t}\leq B,\forall t\geq 0$, we
can appeal to Lemma 4 to conclude that $e_{t}\leq O(\alpha\tau B),\forall
t\geq\tau.$ Plugging this bound on $e_{t}$ back in the main recursion Eq. (10)
leads to the desired claim. ∎

Theorem 2 tells us that with a constant step-size, the iterates generated by
TD(0) converge exponentially fast (in the mean-square sense) to a ball of
radius $O(\alpha B)$ around the optimal parameter $\theta^{*}$. While we claim
no novelty for this result, what is novel is how we arrive at it using our
inductive technique. By using a carefully weighted combination of the
iterates, one can obtain a finer convergence result; to state this result, we
use the notation $\|x\|_{D}=\sqrt{x^{\top}Dx}$, where recall that $D$ is the
diagonal matrix containing the entries of the stationary distribution $\pi$
along the diagonal. The specific form of the next result appears to be new for
TD learning.

######  Theorem 3.

There exists a sequence of weights $\\{w_{t}\\}$ satisfying
$w_{t}\in(0,1),\forall t\in[T],\sum_{t=0}^{T}w_{t}=1$, and a constant step-
size $\alpha$ satisfying the condition in Eq. (15), such that the following is
true:

$\displaystyle\mathbb{E}[{\|\hat{V}_{\bar{\theta}_{T}}-\hat{V}_{\theta^{*}}\|}^{2}_{D}]$
$\displaystyle\leq
C_{1}\exp{\left(-\frac{\omega^{2}(1-\gamma)^{2}(T+1)}{2C\tau}\right)}$ (16)
$\displaystyle\hskip 8.53581pt+\tilde{O}\left(\frac{\tau
B}{\omega^{2}(1-\gamma)^{2}(T+1)}\right),$

where $C\geq 8$ is the same universal constant as in Theorem 1,
$B=10\max\\{\|\theta_{0}-\theta^{*}\|^{2},\sigma^{2}\\}$,
$\bar{\theta}_{T}=\sum_{t=0}^{T}w_{t}\theta_{t},$ and

$C_{1}={O}\left(\frac{B\tau}{\omega^{3}(1-\gamma)^{3}}\right).$

The proof of the above result is a simple adaptation of that of Lemma 25 in
[16]. We spell out the parts unique to our setting in the appendix.

Let us quickly distill the main steps of our argument.

  * •

Step 1. We used the contraction property and the Lipschitz property of the
TD(0) update direction to set up the main recursion in Eq. (10).

  * •

Step 2. Viewing the effect of Markovian noise as a disturbance/perturbation,
our goal was to then show that this perturbation is uniformly bounded. To that
end, we developed our novel inductive argument and showed that the iterates
generated by TD(0) remain uniformly bounded in expectation.

  * •

Step 3. We went back to the main recursion from Step 1, but this time having
proven that the disturbance is uniformly bounded. The rest is straightforward.

As we will discuss in the next section, the above steps constitute a general
recipe for analyzing (potentially nonlinear) contractive stochastic
approximation algorithms. Before we do so, it is instructive to elaborate on
how our analysis relates to existing work on this topic.

Comments on our analysis. Step 1 of our analysis builds on Lemma 1 from [9],
which, in turn, is inspired from prior results in [2]. We provide a proof of
Lemma 1 \- different from that in [9] \- in the Appendix. The idea of
conditioning sufficiently into the past to exploit the geometric mixing
property of the underlying Markov chain is quite standard by now [9, 10, 14].
We use this idea in Lemma 4. The main distinguishing feature of our analysis
relative to prior work in [9] and [10] is how we handle the disturbance term
$T_{3}$ in the main recursion Eq. (10). The projected TD algorithm studied in
[9] automatically ensures that the iterates remain uniformly bounded. This
considerably simplifies the process of controlling $T_{3}$. A close inspection
of the proof in [10] reveals that Lemma 3 in their paper plays a crucial role
in analyzing the _unprojected_ version of TD(0). This lemma provides a bound
of the following form:

$\|\theta_{t}-{\theta}_{t-\tau}\|\leq
O(\alpha\tau)(\|\theta_{t}\|+\sigma),\forall t\geq\tau.$ (17)

In words, this lemma relates the change in the iterates over the interval
$[t-\tau,t]$ to the current iterate. Versions of Lemma 3 from [10] have also
appeared in follow-up works to study Q-learning with linear function
approximation [14]. At a technical level, one of our main contributions is to
show that one can analyze unprojected TD(0) _without this lemma._ We will
revisit the significance of this point again in Section 4. To the best of our
knowledge, the idea of first arguing uniform boundedness of the iterates via
induction, and then using this fact to derive uniform bounds on the
disturbance term $T_{3}$ (due to Markov noise) has not appeared before. We
also note that the main claim of boundedness in Theorem 1 does not require a
decaying step-size; rather, the choice of constant step-size in Theorem 1
complies with the standard choice of step-size in [9] and [10]. Finally, we
would like to draw attention to the works [17, 18, 19] that provide inductive
arguments to establish boundedness of the iterates for constant step-size
Q-learning. However, the analyses in these papers only apply to a _tabular_
setting without function approximation. Whether similar inductive arguments
could be developed for contractive stochastic approximation algorithms with
function approximation was unclear prior to our work.

##  4 Applications of our Analysis Technique

In this section, we briefly discuss a few applications to demonstrate that the
scope of the inductive proof technique outlined in Section 3 extends well
beyond the TD(0) algorithm with linear function approximation.

$\bullet$ Nonlinear Stochastic Approximation. In a typical non-linear
stochastic approximation (SA) problem, the goal is to solve for a parameter
$\theta^{*}$ such that $\bar{g}(\theta^{*})=0$, where
$\bar{g}(\theta)=\mathbb{E}_{X\sim\pi}[g(\theta;X)]$; one can interpret this
as a root-finding problem. Here, $X$ is a noise random variable that comes
from a statistical sample space $\mathcal{X}$, and has distribution $\pi$.
Importantly, $\pi$ is assumed to be _unknown_ (hence, the learning aspect).
The function $g:\mathcal{X}\times\mathbb{R}^{d}\mapsto\mathbb{R}^{d}$ is a
general nonlinear mapping. The learner has access to $\bar{g}(\cdot)$ only
through the noisy samples $\\{g(\cdot\,;X_{t})\\}$, where $\\{X_{t}\\}$ is
generated from a finite-state Markov chain that is aperiodic and irreducible
with stationary distribution $\pi$. The celebrated SA protocol for finding
$\theta^{*}$ takes the form:

$\theta_{t+1}=\theta_{t}+\alpha g(\theta_{t};X_{t}),$ (18)

where $\\{\eta_{t}\\}$ is the learning-rate (step-size) sequence. Algorithms
within the TD($\lambda$) family are instances of linear SA - a special case of
the formulation above - where $g(\theta;X_{t})$ is affine in the parameter
$\theta$. To extend our results beyond the linear SA setting, we make the
following standard assumptions.

######  Assumption 2.

There exist $L,\sigma\geq 1$ s.t. $\|g(\theta_{1};X)-g(\theta_{2};X)\|\leq
L\|\theta_{1}-\theta_{2}\|,\forall\theta_{1},\theta_{2}\in\mathbb{R}^{d}$,
$\forall X\in\mathcal{X}$, and

$\|g(\theta;X)\|\leq
L\left(\|\theta\|+\sigma\right),\forall\theta\in\mathbb{R}^{d},\forall
X\in\mathcal{X}.$ (19)

######  Assumption 3.

The equation $\bar{g}(\theta)=0$ has a solution $\theta^{*}$, and
$\exists\beta>0$ s.t.

$\langle\theta-\theta^{*},\bar{g}(\theta)-\bar{g}(\theta^{*})\rangle\leq-\beta\|\theta-\theta^{*}\|^{2},\forall\theta\in\mathbb{R}^{d}.$
(20)

Assumption 2 tells us that $g(\theta;X)$ is globally uniformly (w.r.t. $X$)
Lipschitz in the parameter $\theta$. This assumption is met by TD- and
Q-learning with linear function approximation [9, 10, 14], and is typical in
the analysis of stochastic optimization [20]. Assumption 3 is referred to as
the strong monotone property of the operator $\bar{g}(\theta)$, and is
directly responsible for exponentially fast convergence (to $\theta^{*}$) of
the steady-state version of (18). We note that this strong monotone property
is satisfied by TD-learning with linear function approximation [9, 10],
variants of Q-learning with linear function approximation [14], and strongly
convex loss functions in the context of optimization. We have the following
result.

######  Theorem 4.

Let $\bar{\beta}\triangleq\min\\{\beta,1/\beta\\},$ and $B\triangleq
10\max\\{\|\theta_{0}-\theta^{*}\|^{2},\sigma^{2}\\}$. Suppose Assumptions 2
and 3 hold. Then, there exists a universal constant $C\geq 8$ such that for
$\alpha\leq\frac{\bar{\beta}}{C\tau L^{2}}$, the iterates generated by Eq.
(18) satisfy $d_{t}\leq B,\forall t\geq 0$, and

$d_{t+1}\leq(1-\alpha\beta)d_{t}+O(\alpha^{2}L^{2}\tau B),$

where $d_{t}\triangleq\mathbb{E}[\|\theta_{t}-\theta^{*}\|^{2}]$, and
$\tau=\tau_{\alpha}$ is the mixing time as defined in Definition 1.

The proof of this result is identical to that of Theorems 1 and 2, and the
only additional work pertains to keeping track of how the Lipschitz parameter
$L$ propagates through the bounds. We omit repeating the same arguments here
again.

Main Takeaway. The main message conveyed by Theorem 4 is that the simple
analysis recipe we outlined in Section 3 \- involving our novel inductive
argument - carries over seamlessly to a broad class of stochastic
approximation algorithms that cover the linear TD($\lambda$) family, variants
of Q-learning, and smooth, strongly convex stochastic optimization under
Markovian noise. In particular, Lipschitzness and some notion of contractivity
of the underlying operator appear to be enough for our induction argument to
go through.

$\bullet$ Stochastic Approximation with Perturbations. Motivated by the
question of robustness of iterative RL algorithms to structured perturbations,
let us consider the following _inexact_ SA scheme shown below:

$\theta_{t+1}=\theta_{t}+\alpha\tilde{g}_{t},$ (21)

where $\tilde{g}_{t}$ is a perturbed version of $g(\theta_{t};X_{t})$. To
convey our key points, let us consider a specific type of perturbation
introduced by delays, where
$\tilde{g}_{t}=g(\theta_{t-\tau_{t}};X_{t-\tau_{t}})$, and $0\leq\tau_{t}\leq
t$ is a time-varying (potentially random) delay that is uniformly bounded,
i.e., $\tau_{t}\leq\tau_{\max},\forall t\geq 0$, where $\tau_{\max}$ is some
positive integer. Such delays are usually unavoidable in the context of
distributed/networked learning problems where information (e.g., models and
model-differentials) gets exchanged over imperfect channels, and, as such,
have been extensively studied in the context of optimization with i.i.d. data.
However, there is little to no work providing an understanding of how
arbitrary time-varying (albeit bounded) delays affect the finite-time
performance of SA schemes driven by Markovian noise. Now suppose we try to
invoke some variant of Lemma 3 from [10] to account for Markovian sampling. In
this context, a bound of the form in Eq. (17) is no longer applicable, since
due to the presence of delays, $\|\theta_{t}-\theta_{t-\tau}\|$ _is not just a
function of the current iterate, but several other iterates from the past._

The above discussion tells us why existing proof techniques for SA under
Markov noise do not immediately lend themselves to the analysis of perturbed
SA schemes, where the perturbation can contain terms from the past. Now
suppose we rewrite Eq. (21) in the following way:

$\theta_{t+1}=\underbrace{\theta_{t}+\alpha\bar{g}(\theta_{t})}_{\mathcal{A}}+\underbrace{\alpha\left(g(\theta_{t};X_{t})-\bar{g}(\theta_{t})\right)}_{e_{1,t}}+\underbrace{\alpha\left(\tilde{g}_{t}-g(\theta_{t};X_{t})\right)}_{e_{2,t}}.$
(22)

In the above decomposition, $e_{1,t}$ and $e_{2,t}$ can be each viewed as a
disturbance to the nominal steady-state dynamics of Eq. (18), as captured by
the term $\mathcal{A}.$ Here, while $e_{1,t}$ arises from Markovian sampling,
$e_{2,t}$ captures the effect of delays (or more generally, some other
perturbation). The main message is that we can lump these iterate-dependent
disturbances together, and use an inductive argument - akin to what we did in
Section 3 \- to establish uniform bounds on them in expectation. Once this is
done, we are again back to a scenario where a uniformly bounded additive
perturbation hits the steady-state nominal dynamics. While we flesh out these
details for delayed SA in a companion paper [11], _the scope of the above
argument is by no means just limited to perturbations arising from delays_. In
principle, as long as we can use induction to argue that the perturbation is
on the order of $O(\alpha^{2})$, the approach in Section 3 will go through.

##  5 Conclusion

We provided a simple and self-contained finite-time analysis of TD learning
with linear function approximation based on a novel inductive argument. We
showed that our proof technique extends to more general nonlinear SA schemes,
and can be used to analyze inexact SA schemes with perturbations. The relative
simplicity of our overall approach opens up various interesting possibilities.
We discuss some of them below.

  1. 1.

In a recent work [21], the authors investigate the finite-time performance of
TD learning with neural-network based function approximators. Their analysis
builds on their prior work [22] where an interesting “gradient-splitting”
interpretation is provided for the TD update direction. However, both [22] and
[21] require a projection step in the algorithm to ensure stability of the
iterates. Whether our inductive technique to guarantee uniform boundedness of
the iterates (in expectation) carries over to neural function approximators
remains to be seen.

  2. 2.

Our results in this paper focus exclusively on single-time-scale SA
algorithms. It would be interesting to see if similar simpler proofs can be
developed for two-time-scale SA schemes in the context of RL.

  3. 3.

As we described in the main paper, one immediate benefit of our technique is
that it can allow for handling multiple forms of disturbances/perturbations in
the update rule simultaneously. In this context, we briefly talked about
handling perturbations in the form of delays. We plan to explore how one can
use our technique to study other types of perturbations typical in large-scale
problems, such as those in [15] involving aggressive compression.

##  Appendix A Omitted Proofs

Proof of Lemma 1. Our proof will leverage the following result from [2].

######  Lemma 5.

Given any $x\in\mathbb{R}^{n}$, the following is true:

$\|P_{\mu}x\|_{D}\leq\|x\|_{D}.$

We will also make use of the fact that
$\bar{g}(\theta)=\bar{A}\theta-\bar{b}$, where
$\bar{A}=\Phi^{\top}D\left(\gamma P_{\mu}-I\right)\Phi$, and
$\bar{b}=-\Phi^{\top}DR_{\mu}$ [2]. Using $\bar{g}(\theta^{*})=0$ and
$\hat{V}_{\theta}=\Phi\theta$, we then have

$\displaystyle\langle\theta-\theta^{*},\bar{g}(\theta)\rangle$
$\displaystyle=\langle\theta-\theta^{*},\bar{g}(\theta)-\bar{g}(\theta^{*})\rangle$
(23)
$\displaystyle=\langle\theta-\theta^{*},\bar{A}\left(\theta-\theta^{*}\right)\rangle$
$\displaystyle=\gamma(\theta-\theta^{*})^{\top}\Phi^{\top}DP_{\mu}\Phi(\theta-\theta^{*})$
$\displaystyle\hskip
7.11317pt-(\theta-\theta^{*})^{\top}\Phi^{\top}D\Phi(\theta-\theta^{*})$
$\displaystyle=\underbrace{\gamma(\hat{V}_{\theta}-\hat{V}_{\theta^{*}})^{\top}DP_{\mu}(\hat{V}_{\theta}-\hat{V}_{\theta^{*}})}_{(*)}$
$\displaystyle\hskip
7.11317pt-\underbrace{(\hat{V}_{\theta}-\hat{V}_{\theta^{*}})^{\top}D(\hat{V}_{\theta}-\hat{V}_{\theta^{*}})}_{(**)}.$

Observe that $(**)=\|\hat{V}_{\theta}-\hat{V}_{\theta^{*}}\|^{2}_{D}.$ Next,
to bound $(*)$, we proceed as follows:

$\displaystyle(*)$
$\displaystyle\overset{(a)}{\leq}\gamma{\|D(\hat{V}_{\theta}-\hat{V}_{\theta^{*}})\|}_{D}{\|P_{\mu}(\hat{V}_{\theta}-\hat{V}_{\theta^{*}})\|}_{D}$
(24)
$\displaystyle\overset{(b)}{\leq}\gamma{\|D(\hat{V}_{\theta}-\hat{V}_{\theta^{*}})\|}_{D}{\|\hat{V}_{\theta}-\hat{V}_{\theta^{*}}\|}_{D}$
$\displaystyle\overset{(c)}{\leq}\gamma\|\hat{V}_{\theta}-\hat{V}_{\theta^{*}}\|^{2}_{D}.$

For (a), we used Cauchy-Schwarz; for (b), we used Lemma 5; and for (c), we
used the fact that $D^{3}\preceq D$ since each diagonal entry of $D$ belongs
to $(0,1)$. Combining the above with Eq. (23), we obtain

$\displaystyle\langle\theta-\theta^{*},\bar{g}(\theta)\rangle$
$\displaystyle\leq-(1-\gamma)\|\hat{V}_{\theta}-\hat{V}_{\theta^{*}}\|^{2}_{D}$
(25)
$\displaystyle=-(1-\gamma)(\theta-\theta^{*})^{\top}\Phi^{\top}D\Phi(\theta-\theta^{*})$
$\displaystyle=-(1-\gamma)(\theta-\theta^{*})^{\top}\Sigma(\theta-\theta^{*})$
$\displaystyle\leq-\omega(1-\gamma)\|\theta-\theta^{*}\|^{2},$

where in the last step, we used that $\Sigma$ is positive definite with
smallest eigenvalue $\omega.$ This completes the proof of Lemma 1.

Proof of Theorem 3. Our first goal is to get an estimate of $e_{t}$ in Eq. (9)
for $t\in[\tau-1].$ To that end, fix any $t\in[\tau-1]$, and observe that

$\displaystyle\langle\theta_{t}-\theta^{*},g_{t}(\theta_{t})-\bar{g}(\theta_{t})\rangle$
$\displaystyle\leq\|\theta_{t}-\theta^{*}\|\left(\|g_{t}(\theta_{t})\|+\|\bar{g}(\theta_{t})\|\right)$
$\displaystyle\leq
4\|\theta_{t}-\theta^{*}\|\left(\|\theta_{t}-\theta^{*}\|+\sigma\right)$
$\displaystyle\leq 8B,$

where in the second inequality, we used equations (6) and (7), and for the
last inequality, we used $\|\theta_{t}-\theta^{*}\|\leq\sqrt{B},\forall
t\in[\tau-1]$ from Lemma 2. Thus, $e_{t}\leq 8B,\forall t\in[\tau-1].$
Plugging this bound in Eq. (10), we obtain

$d_{t+1}\leq(1-\alpha\omega(1-\gamma))d_{t}+O(\alpha B),\forall t\in[\tau-1],$
(26)

where we used the choice of the step-size in Eq. (15). To proceed, we note
that for any $\theta\in\mathbb{R}^{K}$,
$\|\hat{V}_{\theta}-\hat{V}_{\theta^{*}}\|^{2}_{D}=(\theta-\theta^{*})^{\top}\Sigma(\theta-\theta^{*})\leq\|\theta-\theta^{*}\|^{2}$,
since $\Sigma$ is positive definite with largest eigenvalue less than 1.
Defining
$s_{t}\triangleq\mathbb{E}[\|\hat{V}_{\theta_{t}}-\hat{V}_{\theta^{*}}\|^{2}_{D}],$
$A\triangleq 0.5\omega(1-\gamma)$, and using Eq. (26) in tandem with Theorem
2, we then have

$d_{t+1}\leq\begin{cases}(1-\alpha A)d_{t}-\alpha As_{t}+c\alpha
B,&t\in[\tau-1]\\\ (1-\alpha A)d_{t}-\alpha As_{t}+c\alpha^{2}\tau
B,&t\geq\tau,\end{cases}$ (27)

where $c$ is some universal constant. Let us define a sequence of weights as
$\bar{w}_{t}\triangleq(1-\alpha A)^{-(t+1)},\forall t\geq 0$, and set
$W_{T}=\sum_{t=0}^{T}\bar{w}_{t}.$ Using (27), we then have

$\displaystyle A\left(\sum_{t=0}^{T}\frac{\bar{w}_{t}s_{t}}{W_{T}}\right)$
$\displaystyle\leq\underbrace{\frac{1}{\alpha
W_{T}}\sum_{t=0}^{T}\left(\bar{w}_{t}(1-\alpha
A)d_{t}-\bar{w}_{t}d_{t+1}\right)}_{(*)}$ $\displaystyle\hskip
8.53581pt\underbrace{\frac{cB}{W_{T}}\sum_{t=0}^{\tau-1}\bar{w}_{t}}_{(**)}+\underbrace{\frac{c\alpha\tau
B}{W_{T}}\sum_{t=\tau}^{T}\bar{w}_{t}}_{(***)}.$

We now bound each term above. For $(*)$, we use $w_{t}(1-\alpha A)=w_{t-1}$ to
obtain a telescoping sum, yielding

$(*)\leq\frac{(1-\alpha A)\bar{w}_{0}d_{0}}{\alpha
W_{T}}\leq\frac{d_{0}}{\alpha}\left(1-\alpha A\right)^{T+1},$

where in the last step, we used $W_{T}\geq\bar{w}_{T}\geq(1-\alpha
A)^{-(T+1)}.$ Next, it is easy to see that $(***)\leq c\alpha\tau B.$ Finally,
we have

$(**)\leq\frac{cB}{\alpha AW_{T}}(1-\alpha A)^{-\tau}\leq\frac{2cB}{\alpha
A}(1-\alpha A)^{T+1}.$

Here, we used that for $\alpha$ satisfying Eq. (15), it holds that $\alpha
A\tau\leq 1/2.$ Thus, from Bernoulli’s inequality, we have $(1-\alpha
A)^{\tau}\geq(1-\alpha A\tau)\geq 1/2.$ Combining the bounds above, using
$d_{0}\leq B$, $A\leq 1$, and setting $w_{t}=\bar{w}_{t}/W_{T},$ we have

$A\left(\sum_{t=0}^{T}w_{t}s_{t}\right)\leq\frac{3cB}{\alpha
A}\exp\left(-\alpha A(T+1)\right)+c\alpha\tau B.$

From the above display, the final bound in Eq. (16) can be obtained by tuning
$\alpha$ exactly as in the proof of Lemma 25 in [16], followed by Jensen’s
inequality.

## References

  * [1] Richard S Sutton.  Learning to predict by the methods of temporal differences.  Machine learning, 3(1):9–44, 1988.
  * [2] John N Tsitsiklis and Benjamin Van Roy.  An analysis of temporal-difference learning with function approximation.  In IEEE Transactions on Automatic Control, 1997.
  * [3] Vivek S Borkar.  Stochastic approximation: a dynamical systems viewpoint, volume 48.  Springer, 2009.
  * [4] Vivek S Borkar and Sean P Meyn.  The ODE method for convergence of stochastic approximation and reinforcement learning.  SIAM Journal on Control and Optimization, 38(2):447–469, 2000.
  * [5] Nathaniel Korda and Prashanth La.  On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergence.  In Int. conf. on machine learning, pages 626–634. PMLR, 2015.
  * [6] C Narayanan and Csaba Szepesvári.  Finite time bounds for temporal difference learning with function approximation: Problems with some “state-of-the-art” results.  Technical report, Technical report, 2017.
  * [7] Chandrashekar Lakshminarayanan and Csaba Szepesvári.  Linear stochastic approximation: Constant step-size and iterate averaging.  arXiv:1709.04073, 2017.
  * [8] Gal Dalal, Balázs Szörényi, Gugan Thoppe, and Shie Mannor.  Finite sample analyses for TD (0) with function approximation.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
  * [9] Jalaj Bhandari, Daniel Russo, and Raghav Singal.  A finite time analysis of temporal difference learning with linear function approximation.  In Conference on learning theory, pages 1691–1692. PMLR, 2018.
  * [10] Rayadurgam Srikant and Lei Ying.  Finite-time error bounds for linear stochastic approximation and TD learning.  In Conference on Learning Theory, pages 2803–2830. PMLR, 2019.
  * [11] Arman Adibi, Nicolo Dal Fabbro, Luca Schenato, Sanjeev Kulkarni, H Vincent Poor, George J Pappas, Hamed Hassani, and Aritra Mitra.  Stochastic approximation with delayed updates: Finite-time rates under Markovian sampling.  arXiv:2402.11800, 2024.
  * [12] Martin L Puterman.  Markov decision processes.  Handbooks in operations research and management science, 2:331–434, 1990.
  * [13] David A Levin and Yuval Peres.  Markov chains and mixing times, volume 107.  American Math. Soc., 2017.
  * [14] Zaiwei Chen, Sheng Zhang, Thinh T Doan, Siva Theja Maguluri, and John-Paul Clarke.  Performance of Q-learning with linear function approximation: Stability and finite-time analysis.  arXiv:1905.11425, page 4, 2019.
  * [15] Aritra Mitra, George J Pappas, and Hamed Hassani.  Temporal difference learning with compressed updates: Error-feedback meets reinforcement learning.  arXiv:2301.00944, 2023.
  * [16] Sebastian U Stich.  On communication compression for distributed optimization on heterogeneous data.  arXiv:2009.02388, 2020.
  * [17] Abhijit Gosavi.  Boundedness of iterates in Q-learning.  Systems & control letters, 55(4):347–349, 2006.
  * [18] Carolyn L Beck and Rayadurgam Srikant.  Error bounds for constant step-size Q-learning.  Systems & control letters, 61(12):1203–1208, 2012.
  * [19] Guannan Qu and Adam Wierman.  Finite-time analysis of asynchronous stochastic approximation and Q-learning.  In Conference on Learning Theory, pages 3185–3205. PMLR, 2020\.
  * [20] Thinh T Doan.  Finite-time analysis of markov gradient descent.  IEEE Transactions on Automatic Control, 68(4):2140–2153, 2022.
  * [21] Haoxing Tian, Ioannis Ch Paschalidis, and Alex Olshevsky.  On the performance of temporal difference learning with neural networks.  arXiv:2312.05397, 2023.
  * [22] Rui Liu and Alex Olshevsky.  Temporal difference learning as gradient splitting.  In International Conference on Machine Learning, pages 6905–6913. PMLR, 2021.


# Covering $b$-Symbol Metric Codes and the Generalized Singleton Bound

Hao Chen Hao Chen is with the College of Information Science and
Technology/Cyber Security, Jinan University, Guangzhou, Guangdong Province,
510632, China<EMAIL_ADDRESS>The research of Hao Chen was supported by
NSFC Grant 62032009.

###### Abstract

Symbol-pair codes were proposed for the application in high density storage
systems, where it is not possible to read individual symbols. Yaakobi, Bruck
and Siegel proved that the minimum pair-distance of binary linear cyclic codes
satisfies $\lceil d_{2}\geq\frac{3d_{H}}{2}\rceil$ and introduced $b$-symbol
metric codes in 2016. In this paper covering codes in $b$-symbol metrics are
considered. Some examples are given to show that the Delsarte bound and the
Norse bound for covering codes in the Hamming metric are not true for covering
codes in the pair metric. We give the redundancy bound on covering radii of
linear codes in the $b$-symbol metric and give some optimal codes attaining
this bound. Then we prove that there is no perfect linear symbol-pair code
with the minimum pair distance $7$ and there is no perfect $b$-symbol metric
code if $b\geq\frac{n+1}{2}$. Moreover a lot of cyclic and algebraic-geometric
codes are proved non-perfect in the $b$-symbol metric. The covering radius of
the Reed-Solomon code as a $b$-symbol code is determined. As an application
the generalized Singleton bound on the sizes of list-decodable $b$-symbol
codes is also presented. Then an upper bound on lengths of general MDS symbol-
pair codes is proved.

Index terms: $b$-Symbol metric, Covering code, The Delsarte bound, The Norse
bound, Redundancy bound, Reed-Solomon code, Perfect $b$-symbol metric code.
List-decodable $b$-symbol code, MDS symbol-pair code, The generalized
Singleton bound.

##  1 Introduction

The Hamming weight $wt({\bf a})$ of a vector ${\bf a}\in{\bf F}_{q}^{n}$ is
the number of non-zero coordinate positions. The Hamming distance $d_{H}({\bf
a},{\bf b})$ between two vectors ${\bf a}$ and ${\bf b}$ is the Hamming weight
of ${\bf a}-{\bf b}$. The minimum Hamming distance of a code ${\bf
C}\subset{\bf F}_{q}^{n}$,

$d_{H}({\bf C})=\min_{{\bf a}\neq{\bf b}}\\{d_{H}({\bf a},{\bf b}),{\bf
a}\in{\bf C},{\bf b}\in{\bf C}\\},$

is the minimum of Hamming distances $d_{H}({\bf a},{\bf b})$ between any two
different codewords ${\bf a}$ and ${\bf b}$ in ${\bf C}$. Theory of Hamming
error-correcting codes has been fully developed and numerous nice
constructions have been proposed, we refer to [19]. The Singleton bound for a
linear $[n,k,d]_{q}$ code is $d_{H}\leq n-k+1$. When the equality holds, this
code is an MDS code. Let ${\bf F}_{q}$ be an arbitrary finite field,
$P_{1},\ldots,P_{n}$ be $n\leq q$ elements in ${\bf F}_{q}$. The Reed-Solomon
code is defined by

$RS(n,k)=\\{(f(P_{1}),\ldots,f(P_{n})):f\in{\bf F}_{q}[x],\deg(f)\leq k-1\\}.$

This is a $[n,k,n-k+1]_{q}$ linear MDS codes attaining the Singleton bound,
since a degree $\deg(f)\leq k-1$ nonzero polynomial has at most $k-1$ roots.

A code ${\bf C}\subset{\bf F}_{q}^{n}$ is called $(d,L)$ list-decodable in the
Hamming metric if each ball $B_{H}({\bf x},d)=\\{{\bf y}:d_{H}({\bf x},{\bf
y})\leq r\\}\subset{\bf F}_{q}^{n}$, contains at most $L$ codewords of ${\bf
C}$ for each ${\bf x}\in{\bf F}_{q}^{n}$, see [27]. The generalized Singleton
bound

$|{\bf C}|\leq Lq^{n-\lfloor\frac{(L+1)d}{L}}\rfloor$

for $(d,L)$ list-decodable Hamming metric codes was proved in [27]. When
$d=\lfloor\frac{d_{H}({\bf C})-1}{2}\rfloor$ and the list size $L=1$, this is
the classical Singleton bound.

For a code ${\bf C}\subset{\bf F}_{q}^{n}$, we define its covering radius in
the Hamming metric by

$R_{H}({\bf C})=\max_{{\bf x}\in{\bf F}_{q}^{n}}\min_{{\bf c}\in{\bf
C}}\\{wt({\bf x}-{\bf c})\\}.$

Hence the Hamming balls $B(x,R_{H}({\bf C}))$ centered at all codewords
$x\in{\bf C}$, with the radius $R_{H}({\bf C})$ cover the whole space ${\bf
F}_{q}^{n}$, and moreover this radius is the smallest possible such radius.
For this beautiful topic of coding theory on covering codes, we refer to the
nice book [7].

A code in the Hamming metric is perfect if the covering radius of this code is
$R_{H}({\bf C})=\lfloor\frac{d_{H}({\bf C})-1}{2}\rfloor$. For a length $n$
perfect code ${\bf C}$, the whole space ${\bf F}_{q}^{n}$ is the disjoint
union of the Hamming balls of the radius $R_{H}({\bf
C})=\lfloor\frac{d_{H}({\bf C})-1}{2}\rfloor$ centered at all codewords. Then
this is a beautiful intersecting point of both packing and covering problems
in the Hamming metric space ${\bf F}_{q}^{n}$. Perfect codes in the Hamming
metric have the same parameters as parameters of Hamming codes, or the binary
$[23,12,7]_{2}$ Golay code or the ternary $[11,6,5]_{3}$ Golay code, see [20,
30, 7]. We cite the comment in page 49, [19], ” The classification of perfect
codes as summarized in this theorem was a significant and difficult piece of
mathematics.” Covering codes and in particular perfect cods in rank-metric
have been studied in [1, 6, 17]. Another interesting intuition of the
generalized covering radii of linear codes was introduced and studied in a
recent paper [13].

Hence it seems good to study perfect codes in $b$-symbol metrics. There have
been extensive research on covering radii of codes in the Hamming metric. For
example, in a paper [12] published in 1991, covering radii of more than six
thousand binary cyclic codes were calculated and determined. On the other hand
many MDS symbol-pair codes have been constructed by cyclic codes or
constacyclic codes, see [24, 9, 10, 5, 25]. Then what will happen when these
well-known linear codes such as cyclic codes, constacyclic codes, Reed-Solomon
codes and algebraic-geometric codes are considered as covering $b$-symbol
metric codes?

Symbol-pair codes were introduced for high density data storage, we refer to
[2, 3]. Set

$({\bf
F}_{q}^{n})^{2}=\\{(x_{1},x_{2}),(x_{2},x_{3}),\ldots,(x_{n-1},x_{n}),(x_{n},x_{1})):{\bf
x}=(x_{1},\ldots,x_{n})\in{\bf F}_{q}^{n}\\}.$

The space $({\bf F}_{q}^{n})^{b}$ for $b=3,4,\ldots,n-1$ can be defined
similarly. The pair metric on ${\bf F}_{q}^{n}$ is defined as follows. For
${\bf x}=(x_{1},\ldots,x_{n})\in{\bf F}_{q}^{n}$, the mapping $\pi_{2}:{\bf
F}_{q}^{n}\longrightarrow({\bf F}_{q}^{n})^{2}$ is defined by $\pi_{2}({\bf
x})=((x_{1},x_{2}),\ldots,(x_{n},x_{1}))\in({\bf F}_{q}^{n})^{2}$. The pair
weight of ${\bf x}\in{\bf F}_{q}^{n}$ is

$wt_{2}({\bf x})=wt_{H}(\pi_{2}({\bf x}))=\\{i:(x_{i},x_{i+1})\neq 0\\}.$

The pair distance $d_{2}$ is defined by

$d_{2}({\bf x},{\bf y})=wt_{2}(\pi_{2}({\bf x})-\pi_{2}({\bf y})),$

see [2, 3]. It follows from the definition that

$d_{H}({\bf x},{\bf y})+1\leq d_{2}({\bf x},{\bf y})\leq 2d_{H}({\bf x},{\bf
y}).$

The ball in the pair-metric is $B_{2}({\bf x},r)=\\{{\bf y}:d_{2}({\bf x},{\bf
y})\leq r\\}$. For a code ${\bf C}\subset{\bf F}_{q}^{n}$, the minimum pair
distance is

$d_{2}({\bf C})=\min\\{d_{2}(\pi_{2}({\bf x}),\pi_{2}({\bf y})):{\bf
x}\neq{\bf y},{\bf x}\in{\bf C},{\bf y}\in{\bf C}\\}.$

The Singleton bound $|{\bf C}|\leq q^{n-d_{P}+2}$ for symbol-pair codes was
proved in [4] and some MDS symbol-pair codes have been constructed in [4, 24,
5, 11, 9, 25]. In [31] $b$-symbol metric was introduced and the following nice
lower bound of the minimum pair distances for linear binary cyclic codes was
proved,

$d_{2}\geq\lceil\frac{3d_{H}}{2}\rceil.$

A symbol-pair code ${\bf C}\subset{\bf F}_{q}^{n}$ is called $(d_{list},L)$
list-decodable if each ball $B_{2}({\bf x},d_{list})\subset{\bf F}_{q}^{n}$,
contains at most $L$ codewords of ${\bf C}$ for each ${\bf x}\in{\bf
F}_{q}^{n}$. The list-decodability and list-decoding of symbol-pair codes have
been studied in [22]. More constructions and bounds for symbol-pair codes was
given in [14]. Generalized pair weights of linear codes were introduced and
studied in [21].

We recall the $b$-symbol metric on ${\bf F}_{q}^{n}$ for $2\leq b\leq n-1$.
For ${\bf x}\in{\bf F}_{q}^{n}$, set $\pi_{b}({\bf
x})=((x_{1},\ldots,x_{b}),(x_{2},\ldots,x_{b+1}),\ldots,(x_{n},x_{1},\ldots,x_{b-1}))\in({\bf
F}_{q}^{n})^{b}$. Then the $b$-symbol Hamming metric on ${\bf F}_{q}^{n}$ was
introduced in [31]. The $b$-symbol weight of ${\bf
x}=(x_{1},\ldots,x_{n})\in{\bf F}_{q}^{n}$ is

$wt_{b}({\bf x})=wt_{H}(\pi_{b}({\bf
x}))=\\{i:(x_{i},x_{i+1},\ldots,x_{i+b-1})\neq 0\\}.$

The $b$-symbol distance is defined by

$d_{b}({\bf x},{\bf y})=wt_{b}(\pi_{b}({\bf x})-\pi_{b}({\bf y})).$

The $b$-symbol ball in ${\bf F}_{q}^{n}$ is $B_{b}({\bf x},r)=\\{{\bf
y}\in{\bf F}_{q}^{n}:d_{b}({\bf x},{\bf y})\leq r\\}$. It is clear

$d_{H}({\bf x},{\bf y})+b-1\leq d_{b}({\bf x},{\bf y})\leq bd_{H}({\bf x},{\bf
y}),$

see Proposition 3 in [31]. The minimum $b$-symbol distance of a code ${\bf C}$
is

$d_{b}({\bf C})=\min\\{d_{b}(\pi_{b}({\bf x}),\pi_{b}({\bf y})):{\bf
x}\neq{\bf y},{\bf x}\in{\bf C},{\bf y}\in{\bf C}\\}.$

For recent work on minimum $b$-symbol distances of linear cyclic codes, we
refer to [10, 29].

For a $b$-symbol code ${\bf C}\subset{\bf F}_{q}^{n}$, we define its covering
radius in the $b$-symbol Hamming metric by

$R_{b}({\bf C})=\max_{{\bf x}\in{\bf F}_{q}^{n}}\min_{{\bf c}\in{\bf
C}}\\{d_{b}({\bf x}-{\bf c})\\}.$

Hence the balls $B_{b}(x,R_{b}({\bf C}))$ centered at all codewords $x\in{\bf
C}$, with the radius $R_{b}({\bf C})$ cover the whole space ${\bf F}_{q}^{n}$,
and moreover this radius is the smallest possible such radius. To the best of
our knowledge there has been no previous work on covering codes in the
$b$-symbol metric. It is interesting to determine perfect codes in the
$b$-symbol metric, that is these codes ${\bf C}\subset{\bf F}_{q}^{n}$
satisfying

$R_{b}({\bf C})=\lfloor\frac{d_{b}({\bf C})-1}{2}\rfloor.$

A $b$-symbol code ${\bf C}\subset{\bf F}_{q}^{n}$ is called $(d_{list},L)$
list-decodable if each ball $B_{b}({\bf x},d_{list})\subset{\bf F}_{q}^{n}$,
contains at most $L$ codewords of ${\bf C}$ for each ${\bf x}\in{\bf
F}_{q}^{n}$. There is no previous work about list-decodable codes in the
$b$-symbol metric.

There are many classical beautiful results about covering codes in the Hamming
metric, for example, the Delsarte bound in [8] and the Norse bound in [18]. We
give some examples to show these bounds are not true for covering codes in the
pair metric. Then the redundancy upper bound on covering radii of linear codes
in the $b$-symbol metric is given and some optimal codes attaining this bound
is constructed. The covering radius of the Reed-Solomon code in the $b$-symbol
metric is determined. We prove that perfect $b$-symbol metric code does not
exist when $b\geq\frac{n+3}{2}$ and perfect linear symbol-pair code of the
minimum pair distance $7$ does not exist neither. Moreover it is proved that a
linear $[n,k]_{q}$ code can not be perfect in the $2(k+1)$-symbol metric. Many
well-known cyclic codes, constacyclic codes and algebraic-geometric codes are
proved not perfect in the pair metric. On the other hand the generalized
Singleton bound on list-decodable $b$-symbol codes is proved as an application
of covering $b$-symbol metric codes. From our generalized Singleton bound on
symbol-pair codes, we give an upper bound on the lengths of a MDS symbol-pair
codes.

##  2 The covering codes in the $b$-symbol metric

We prove the following two upper bounds on the covering radii of linear codes
in ${\bf F}_{q}^{n}$ in the $b$-symbol metric.

Proposition 2.1. Let ${\bf C}\subset{\bf F}_{q}^{n}$ be a code then
$R_{H}({\bf C})+b-1\leq R_{b}({\bf C})\leq\min\\{bR_{H}({\bf C}),n\\}$.

Proof. From the inequality $d_{H}({\bf x},{\bf y})+b-1\leq d_{b}({\bf x},{\bf
y})$, then $B_{b}({\bf x},r)\subset B_{H}({\bf x},r-b+1)$. The second bound
$R_{b}({\bf C})\leq bR_{H}({\bf C})$ follows from the inequality $d_{b}({\bf
x},{\bf y})\leq bd_{H}({\bf x},{\bf y})$.

From [23] covering radii of many best known binary covering codes were
determined. Then their covering radii in the pair metric are ranging from
$R_{H}+1$ to $2R_{H}$, it is interesting to determine their $R_{2}$ exactly.
It is interesting to ask if these binary codes are best covering codes in the
pair metric.

For any given code ${\bf C}\subset{\bf F}_{q}^{n}$, let $Perm$ be a
permutation of $n$ coordinate positions, then the code after permutation is
denoted by $Perm({\bf C})$. If ${\bf C}$ is a linear $[n,k]_{q}$ code, then
$Perm({\bf C})$ is also a linear $[n,k]_{q}$ code for any permutation. We
recall that the covering radius in the Hamming metric of a linear $[n,k]_{q}$
code is at most $n-m$, this is the redundancy bound, see page 217 [7].

Theorem 2.1. Let ${\bf C}\subset{\bf F}_{q}^{n}$ be a linear $[n,k]_{q}$ code,
then there exists a permutation $Perm$ of $n$ coordinate positions such that
the covering radius in the $b$-symbol Hamming metric of $Perm({\bf C})$ is at
most $n-k+b-1$, that is,

$R_{insdel}(Perm({\bf C}))\leq\min\\{n-k+b-1,n\\}.$

Proof. Suppose that the first $k$ columns of one generator matrix are linear
independent. Then for any given vector ${\bf y}$ in ${\bf F}_{q}^{k}$ there is
a codeword ${\bf c}$ in ${\bf C}$ such that the first $k$ coordinates of ${\bf
c}$ equal to ${\bf y}$. Therefore in each coset ${\bf y}+{\bf C}$ we can find
a vector with first $k$ coordinates zero. Then the smallest $b$-symbol weight
in each coset is at most $n-k+b-1$. If the first $k$ columns of this linear
code are not linear independent, suppose that columns at
$i_{1}<i_{2}<\cdots<i_{k}$ are linear independent. We take a permutation
$Perm$ transforming $i_{1},\ldots,i_{k}$ to $n-k+1,\ldots,n$. Then the
conclusion follows immediately.

Corollary 2.1 (redundancy bound for $b$-symbol covering codes). Let ${\bf C}$
be linear $[n,k]_{q}$ code, if there are $k$ consecutive coordinate positions
$i,i+1,\ldots,i+k-1$ such that columns in one generator matrix of ${\bf C}$ at
these positions are linear independent, then $R_{b}({\bf
C})\leq\min\\{n-k+b-1,n\\}$.

For a linear $[n,k]_{q}$ code ${\bf C}$, let $wt_{coset}({\bf v}+{\bf C})$ be
the minimum Hamming weight among all weights of vectors in this coset. Hence

$R_{H}({\bf C})=\max_{{\bf v}\in{\bf F}_{q}^{n}}\\{wt_{coset}({\bf v}+{\bf
C})\\},$

see Theorem 11.1.2 in [19]. Then $R_{H}({\bf C})$ is minimum positive integer
$s$ such each nonzero vector in ${\bf F}_{q}^{n-k}$ can be represented as
linear combinations of at most $s$ columns in its parity check matrix.
Moreover such a linear combination corresponds to a vector in one coset of the
least Hamming weight. Then redundancy bound about covering radii of linear
codes follows immediately. This bound $R_{H}({\bf C})\leq n-k$ for a linear
$[n,k]_{q}$ code is attained when ${\bf C}$ is a Reed-Solomon code. It seems
that it is easier that the above redundancy bound for linear symbol-pair codes
to be attained as illustrated in the following example 1 and 3. Similarly for
a linear $[n,k]_{q}$ code ${\bf C}\subset{\bf F}_{q}^{n}$ let
$wt_{b,coset}({\bf v}+{\bf C})$ be the minimum $b$-symbol weight among all
weights of vectors in this coset. Then

$R_{b}({\bf C})=\max_{{\bf v}\in{\bf F}_{q}^{n}}\\{wt_{b,coset}({\bf v}+{\bf
C})\\}.$

Example 1. Let ${\bf C}$ be a binary linear self-dual $[2n,n,2]_{2}$ code with
one generator matrix $({\bf I}_{n},{\bf I}_{n})$. Then it is easy to verify
that $R_{H}({\bf C})=n+1$. On the other hand the vectors in cosets can be of
the form $({\bf 0},{\bf y})$, where ${\bf 0}$ and ${\bf y}$ are vectors in
${\bf F}_{2}^{n}$, Hence the smallest possible pair weight is $n+1$, and
$R_{2}({\bf C})=n+1$. The above redundancy bound for symbol-pair code is
attained. The following Example 2 shows that the condition in Corollary 2.1 is
necessary.

Example 2. If we use different coordinate ordering of binary linear
$[4t,2t,2]_{2}$ code ${\bf C}_{1}$ with the following generator matrix.

$\left(\begin{array}[]{cccccccccccccccccccc}1&1&0&0&0&0&0&\cdots&0&0\\\
0&0&1&1&0&0&0&\cdots&0&0\\\ 0&0&0&0&1&1&0&\cdots&0&0\\\
\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots&\cdots\\\
0&0&0&0&0&0&0&\cdots&1&1\\\ \end{array}\right)$

From the above observation from the parity check (then the generator matrix
since ${\bf C}$ is self-dual) matrix, the smallest possible pair weight
vectors in cosets is of the form

$(0110110110\ldots 0110),$

therefore the smallest possible pair weight of vectors in cosets is $3t$. We
have $R_{2}({\bf C}_{1})=3t$.

Example 3. Let ${\bf C}$ be a binary linear $[6,3,3]_{2}$ code with the
following parity check matrix.

$\left(\begin{array}[]{ccccccccc}1&0&0&1&1&0\\\ 0&1&0&0&1&1\\\ 0&0&1&1&0&1\\\
\end{array}\right)$

Since $(000111)$ is a codeword, $d_{2}({\bf C})=4$. Hence the covering radius
of the above binary linear $[6,3,3]_{2}$ code is $2$. From Proposition 2.1,
the covering radius of this linear $[6,3,3]_{2}$ code in the pair-metric
satisfies $3\leq R_{2}({\bf C})\leq 4$. If $R_{2}({\bf C})=3$, then in each
coset ${\bf v}+{\bf C}\subset{\bf F}_{2}^{6}$, the vector of Hamming weight
$2$ has to contain two consecutive support positions. This is not the case,
since we can check $(1,1,1)$ has no representation as the sum of two
consecutive columns in the above matrix. Therefore $R_{2}({\bf C})=4$ attains
the above redundancy bound for symbol pair codes and the bound in Proposition
2.1.

The Norse bound in [18] claims that for a binary linear code ${\bf C}$, if its
dual distance is at least $2$, that is no two columns in any generator matrix
of ${\bf C}$ are linear dependent, then the covering radius $R_{H}({\bf
C})\leq\lfloor\frac{n}{2}\rfloor$, or see Corollary 11.2.2 in [19]. Example 3
is a counterexample for such claim in pair metric. Hence the Norse bound on
covering radii in $b$-symbol metric is not true.

The Delsarte bound in [8] asserts that the covering radius of a linear code is
not more than the number of nonzero weights of its dual. The following example
shows that this is not true for covering symbol-pair codes.

Example 4. Let ${\bf C}$ be the Hamming $[8,4,4]_{2}$ code with the following
generator matrix. This is a binary linear code with $d_{H}({\bf C})=4$ with
$16$ codewords, Their weights are $4$ and $8$ and this code have two nonzero
weights $4$ and $8$.

$\left(\begin{array}[]{cccccccccccccccccccc}1&1&1&1&0&0&0&0\\\
0&0&0&0&1&1&1&1\\\ 1&1&0&0&1&1&0&0\\\ 0&1&1&0&0&1&1&0\\\ \end{array}\right)$

The covering radius of ${\bf C}$ in the Hamming metric is $R_{H}({\bf C})=2$,
from the Delsarte bound in [8] or from the fact to analysis the minimum
weights in each cosets.

It is clear that all pair weights of codewords are in the set $\\{5,6,7,8\\}$.
By checking the shape of Hamming weight $4$ codewords, the pair weight $7$ is
not possible. Hence this code have three nonzero pair weights. We observe the
vectors of Hamming weight $2$ in each coset. It is easy to verify that there
are many vectors with two support positions, one support position in
$\\{1,2,3,4\\}$ and one support position in $\\{5,6,7,8\\}$, in some cosets.
Then the smallest pair weight

$\max_{{\bf v}\in{\bf F}_{q}^{n}}\\{wt_{2,coset}({\bf v}+{\bf C})\\}=4.$

We have $R_{2}({\bf C})=4$. This is a counterexample of the Delsarte bound for
covering codes in pair metric. This is also an example with the covering
radius in the pair metric smaller than the redundancy upper bound.

A symbol-pair code ${\bf C}\subset{\bf F}_{q}^{n}$ satisfies the Singleton
bound

$|{\bf C}|\leq q^{n-d_{2}+2},$

we refer to [4]. A code attaining this bound is called MDS symbol-pair code.
Many linear MDS codes have been constructed, see [4, 24, 5, 11, 25, 9, 10].
Similarly a linear $[n,k]_{q}$ code satisfying $d_{b}=n-k+b$ is called MDS
$b$-symbol code and some linear MDS $b$-symbol codes have been constructed,
see [11, 10].

Corollary 2.2. Let ${\bf C}$ be a linear MDS $b_{1}$-symbol code for $1\leq
b_{1}\leq n-1$, then its covering radius in the $b$-symbol metric satisfies
$R_{b}({\bf C})\leq\min\\{n-k+b-1,n\\}$.

Proof. Let ${\bf G}$ be one generator matrix, then its last $k$ columns have
to be linear independent. Otherwise there is a nonzero codeword such that last
$k$ coordinates are zero. Then $d_{b_{1}}({\bf C})\leq n-k+b_{1}-1$, not MDS
$b_{1}$-symbol codes. The conclusion follows from Corollary 2.1.

Theorem 2.2. The covering radius of Reed-Solomon codes in the $b$-symbol
metric satisfies $R_{b}(RS(n,k))=\min\\{n-k+b-1,n\\}$.

Proof. Any $k$ consecutive coordinate positions satisfy the required property
in Corollary 2.2 for Reed-Solomon codes. On the other hand it is well-known
that the covering radius of $RS(n,k)$ is $n-k$, see [7]. The conclusion
follows from $R_{H}({\bf C})+b-1\leq R_{b}({\bf C})$.

Since there are many MDS symbol-pair or MDS $b$-symbol linear cyclic codes
constructed, see for example [24, 10], it is an interesting open problem to
determine the covering radii of these MDS codes in pair-metric or $b$-symbol
metric, as in Theorem 2.2. In Theorem 2.4 and Corollary 2.4 some lower bounds
on their covering radii in the pair metric are given.

Let ${\bf X}$ be an absolutely irreducible projective smooth genus $g$ curve
defined over ${\bf F}_{q}$. Let $P_{1},\ldots,P_{n}$ be $n$ distinct rational
points of ${\bf X}$ over ${\bf F}_{q}$. Let ${\bf G}$ be a rational divisor
over ${\bf F}_{q}$ of degree $\deg({\bf G})$ where $2g-2<\deg({\bf G})<n$ and

$support({\bf G})\bigcap{\bf P}=\emptyset.$

Let ${\bf L}({\bf G})$ be the function space associated with the divisor ${\bf
G}$. The algebraic-geometric code associated with ${\bf G}$,
$P_{1},\ldots,P_{n}$ is defined by

${\bf C}(P_{1},\ldots,P_{n},{\bf G},{\bf
X})=\\{(f(P_{1}),\ldots,f(P_{n})):f\in{\bf L}({\bf G})\\}.$

The dimension of this code is

$k=\deg({\bf G})-g+1$

follows from the Riemann-Roch Theorem, see [28]. The minimum Hamming distance
is

$d_{H}\geq n-\deg({\bf G}).$

The Reed-Solomon codes are just the algebraic-geometric codes over the genus
$0$ curve. Algebraic-geometric residual code with the dimension $k=n-m+g-1$
and minimum Hamming distance $d_{H}\geq m-2g+2$ can be defined, we refer to
[19, 28] for the detail.

From the Riemann-Roch Theorem any $k-1$ columns in one generator matrix of an
algebraic-geometric $[n,k]_{q}$ code are linear independent. Hence we have the
following upper bound on the covering radius of an algebraic-geometric code.

Corollary 2.3. Let ${\bf C}$ be an algebraic-geometric $[n,k]_{q}$ code, then
its covering radius in the $b$-symbol metric is at most $n-k+b$.

Proof. This conclusion follows from a similar argument as in the proof of
Theorem 2.1.

Theorem 2.3. Let ${\bf C}$ be a linear $[n,k]_{q}$ code, then its covering
radius in the $b$-symbol metric is at least

$(b+1)\cdot\lfloor\frac{n}{2(k+1)}\rfloor$

.

Proof. Divide $t=\\{1,2,\ldots,n\\}$ to $\lfloor\frac{n}{k+1}\rfloor$ parts
$A_{1},\ldots,A_{t}$, each part have consective $k+1$ coordinate positions.
Since any $k+1$ columns in one generator matrix of ${\bf G}$ are linear
dependent. Then we can find a vector ${\bf y}$ in ${\bf F}_{q}^{n}$ such that
in the coset ${\bf y}+{\bf C}$, has at least one nonzero coordinate in
$A_{1},\ldots,A_{t}$. In every consecutive two parts, the least $b$-weight
happens when the vector in the coset is of the form $(\ldots 0110\ldots)$.
Then the conclusion follows directly.

From the calculations of pair distances and $b$-symbol distances of some
cyclic codes and constacyclic codes in [9, 10] we can give lower bounds on the
covering radii of these codes in the pair or $b$-symbol metric as follows.

Theorem 2.4. Let ${\bf C}_{i,i}$ be the cyclic code over ${\bf F}_{p^{m}}$ of
the length $2p^{s}$ generated by $(x^{2}-1)^{i}$. Suppose that
$p^{s}-p^{s-e}+\tau p^{s-e-1}+2\leq i\leq p^{s}-p^{s-e}+(\tau+1)p^{s-e-1}+1$,
where $0\leq\tau\leq p-2$, $0\leq e\leq s-1$. Then

$R_{2}({\bf C}_{i,i})\geq 2(\tau+1)p^{e}.$

Proof. The cyclic code satisfies ${\bf C}_{i,i}\subset{\bf C}_{i-1,i-1}$ and
these two codes are not the same. Then in the coset ${\bf v}+{\bf C}_{i,i}$
for some ${\bf v}\in{\bf C}_{i-1,i-1}-{\bf C}_{i,i}$, the pair weight of each
vector is at least $d_{2}({\bf C}_{i-1,i-1})$. The conclusion follows from
Theorem 9 in [9].

Let $p$ be a prime and $s,m$ be two positive integers, $s=r_{1}m+r$, where
$r_{1}$ and $r$ are two nonnegative integers satisfying $0\leq r\leq m-1$.
$\lambda$ be a nonzero element $\lambda\in{\bf F}_{p^{m}}$. Set
$\gamma=\lambda^{p^{(r_{1}+1)m-s}}$. Then length $p^{s}$
$\lambda$-constacyclic code ${\bf C}_{i}$ is generated by $(x-\gamma)^{i}$,
$0\leq i\leq p^{s}$, see [10] page 2.

Corollary 2.4. Suppose that $i$ satisfies $p^{s}-p^{s-e}+\tau
p^{s-e-1}+\beta+1\leq i\leq p^{s}-p^{s-e}+(\tau+1)p^{s-e-1}+1$ where $0\leq
e\leq s-2$, $0\leq\tau\leq p-2$ and $b\leq\beta(\tau+1)$. Then the covering
radius of ${\bf C}_{i}$ in the $b$-symbol metric satisfies

$R_{b}({\bf C}_{i})\geq b(\tau+2)p^{e}.$

Proof. The conclusion follows from a similar argument as in the proof of
Theorem 2.4 and Theorem 9 in [10].

##  3 Perfect $b$-symbol metric code

When $b=2$, $B_{2}({\bf x},2)$ is exactly the $B_{H}({\bf x},1)$, we refer to
[2] Example 2. Hence binary Hamming $[2^{n}-1,2^{n}-1,3]_{2}$ code with the
pair distance $5$ is a perfect pair-metric code as showed in Theorem 19 in
[2]. It is interesting to study the perfect $b$-symbol metric codes in
general.

Proposition 3.1. $B_{b}({\bf x},r)\subset B_{H}({\bf x},r-b+1)$ and
$B_{H}({\bf x},r)\subset B_{b}({\bf x},br)$. Moreover $B_{b}({\bf x},r)={\bf
x}$ for $r\leq b-1$, $B_{b}({\bf x},b)=B_{H}({\bf x},1)$.

Proof. This is a direct analysis about the shape of balls.

The following result is a direct generalization of Theorem 19 in [2].

Proposition 3.2. The minimum $b$-symbol distance of the Hamming
$[\frac{q^{m}-1}{q-1},m,3]_{q}$ code over ${\bf F}_{q}$ is at most $2b+1$. If
the minimum $b$-symbol distance of this $q$-ary Hamming code is $2b+1$, it is
a perfect $b$-symbol metric code.

Proof. It is clear there is one Hamming weight $3$ codeword

${\bf c}=(110\ldots 0x\ldots 0)$

in the $q$-ary Hamming code for some nonzero $x\in{\bf F}_{q}$. Then from the
definition of $b$-symbol distance, we have $d_{b}(\pi_{b}({\bf
c}),\pi_{b}({\bf 0}))\leq 2b+1$. The second conclusion follows from
Proposition 3.1.

Theorem 3.1. For any given finite field ${\bf F}_{q}$, there is no perfect
symbol-pair code with the cardinality $q^{k}$ and the minimum pair distance
$7$.

Proof. We analysis the shape of the ball

$B_{2}({\bf 0},3)=B_{2}({\bf 0},2)\bigcup\\{{\bf x}:d_{2}({\bf x},{\bf
0})=3\\}.$

Moreover $B_{2}({\bf 0},2)$ and the sphere $\\{{\bf x}:d_{2}({\bf 0},{\bf
x})=3\\}$ is disjoint. For any ${\bf x}$ satisfying $d_{2}({\bf x},{\bf
0})=3$, it is clear $d_{2}({\bf x},{\bf 0})=2$ and ${\bf x}$ has two
consecutive support positions. Then $|B_{2}({\bf 0},3)|=1+n(q-1)+n(q-1)^{2}$.
If there is a size $q^{k}$ symbol-pair code with the minimum pair distance $7$
which is perfect in the pair-metric, then $|B_{2}({\bf 0},3)|q^{k}=q^{n}$.
Hence $nq=n(q-1)+n=q^{n-k-1}+q^{n-k-2}+\cdots+q+1$. This is a contradiction.

Theorem 3.2. If ${\bf C}$ is a perfect $b$-symbol metric code, then

$d_{b}({\bf C})\geq d_{H}({\bf C})+2b-1.$

In particular If $b\geq\frac{n+1}{2}$, there is no perfect $b$-symbol metric
code.

Proof. From Proposition 2.1, $R_{b}({\bf C})\geq R_{H}({\bf
C})+b-1\geq\lfloor\frac{d_{H}({\bf C})-1}{2}\rfloor+b-1$, we have

$\lfloor\frac{d_{b}({\bf C})-1}{2}\geq\lfloor\frac{d_{H}({\bf
C})-1}{2}\rfloor+b-1,$

since for a perfect $b$-symbol code $R_{b}({\bf C})=\lfloor\frac{d_{b}({\bf
C})-1}{2}\rfloor$. Then the conclusion follows immediately.

Theorem 3.3. Let ${\bf C}$ be a linear $[n,k]_{q}$ code. Then ${\bf C}$ is not
perfect in the $2(k+1)$-symbol metric.

Proof. From the proof of Theorem 2.3, there is a vector in some coset, every
consecutive $(2k+2)$ coordinate positions can not be zero. Therefore
$R_{2(k+1)}({\bf C})=n$ from $R_{2(k+1)}({\bf C})=\max_{{\bf v}\in{\bf
F}_{q}^{n}}\\{wt_{2(k+1),coset}({\bf v}+{\bf C})\\}.$ . The conclusion follows
immediately.

Theorem 3.4. Let ${\bf C}\subset{\bf C}^{\prime}\subset{\bf F}_{q}^{n}$ be two
linear codes satisfying $d_{2}({\bf C}^{\prime})\geq\frac{b}{2}\cdot
d_{H}({\bf C})$ and ${\bf C}\neq{\bf C}^{\prime}$. Then ${\bf C}$ is not
perfect in the $b$-symbol matric.

Proof Let ${\bf v}\in{\bf C}^{\prime}-{\bf C}$, then any vector in the coset
${\bf v}+{\bf C}$ has its pair weight at least $d_{b}({\bf C}^{\prime})$.
Therefore $R_{b}({\bf C})\geq d_{b}({\bf C}^{\prime})\geq\frac{b}{2}d_{H}({\bf
C})>\frac{d_{b}({\bf C})-1}{2}$. The conclusion follows directly.

The following result follows from Theorem 3.4 for the pair metric case.

Corollary 3.1. Let ${\bf C}$ be an MDS symbol-pair $[n,k]_{q}$ linear code,
then any linear subcode ${\bf C}^{\prime}$ in ${\bf C}$ of dimension $k-1$ is
not perfect in the pair metric.

Proof. From the Singleton bound on the Hamming metric $d_{H}({\bf
C}^{\prime})\leq n-(k-1)+1=n-k+2=d_{2}({\bf C})$. The conclusion follows from
Theorem 3.4 immediately.

Corollary 3.2. Let ${\bf C}$ be a linear subcode of a linear code ${\bf
C}_{1}$ and these two codes are not the same. Assume $d_{2}({\bf C}_{1})\geq
d_{H}({\bf C})$ or $d_{H}({\bf C}_{1})\geq d_{H}({\bf C})-1$. Then ${\bf C}$
is not perfect in the pair metric.

Theorem 3.4 and Corollary 3.2 can be used to exclude a lot of linear codes as
perfect codes in the pair metric. For example from the computation of optimum
distance profiles (ODPs) of self-dual binary codes in [15, 16], many
codimension $1$ linear subcode of some self-dual binary codes are not perfect
in the pair metric. Moreover a lot of cyclic codes and algebraic-geometric
codes are not perfect in the $b$-symbol metric, as proved in the following two
results.

Corollary 3.3. Let ${\bf C}$ be an algebraic-geometric residual code with the
dimension $n-m+g-1$ and the minimum Hamming distance $m-2g+2$, defined by a
degree $m$ divisor of the form $m{\bf Q}$, where ${\bf Q}$ is a rational point
of the curve. Then ${\bf C}$ is not perfect in the pair metric.

Proof. Let ${\bf C}_{1}$ be the residual code defined by the divisor
$(m-1){\bf Q}$. Then ${\bf C}$ is a real subcode of ${\bf C}_{1}$. Since
$d_{H}({\bf C}_{1})\geq m-1-2g+2\geq d_{H}({\bf C})+1$. The conclusion follows
from Corollary 3.2.

The Hermitian curve $x^{q}z+z^{q}x=y^{q+1}$ over ${\bf F}_{q^{2}}$ is a genus
$g=\frac{q^{2}-q}{2}$ curve and it has $1+q^{3}$ rational points. Let $m$ be a
positive integer satisfying $2g-2<m\leq q^{3}-1$. The Hermitian code ${\bf
C}_{m}$ is a linear $[q^{3},q^{3}-m+g-1,\geq m-2g+2]_{q^{2}}$ code, see [26].
When $m\geq 2q^{2}-2q-2$, the true minimum Hamming distance is $m-2g+2$. From
Corollary 3.3 these Hermitian codes are not perfect symbol-pair codes.

From Theorem 8 and Theorem 9 in [9] most cyclic codes of the length $2p^{s}$
over ${\bf F}_{p^{m}}$ of the form ${\bf C}_{i,i}$ as in Section 2 can not be
perfect. We give the following result.

Corollary 3.4. Let ${\bf C}_{i,i}$ be the cyclic code over ${\bf F}_{p^{m}}$
of the length $2p^{s}$ generated by $(x^{2}-1)^{i}$. Suppose that
$p^{s}-p^{s-e}+\tau p^{s-e-1}+2\leq i\leq p^{s}-p^{s-e}+(\tau+1)p^{s-e-1}+1$,
where $0\leq\tau\leq p-2$, $0\leq e\leq s-1$. Then ${\bf C}_{i,i}$ can not be
perfect code in the pair metric.

Proof. From Theorem 8 and Theorem 9 in [9], $d_{2}({\bf C}_{i,i})=2d_{H}({\bf
C}_{i-1,i-1})$. The conclusion follows from Corollary 3.2.

Similarly many constacyclic codes studied in [10] are not perfect in the
$b$-symbol metric from Corollary 3.2, and the exact determination of their
minimum Hamming distances and minimum pair distances in [10].

##  4 The generalized Singleton bound

When $b=n-1$, $B_{b-1}({\bf x},n-1)=B_{H}({\bf x},1)$, hence any code is
$(n-1,(1+n(q-1)))$ list-decodable $(n-1)$-symbol code. It is not interesting
to discuss list-decodable $b$-symbol codes when $b$ is big.

From the definitions as above, for an $(d_{list},L)$ list-decodable code ${\bf
C}\subset{\bf F}_{q}^{n}$ in the $b$-symbol metric, and a covering code ${\bf
C}_{1}\subset{\bf F}_{q}^{n}$ in the $b$-symbol metric with the radius at most
$d_{list}$, we have the following upper bound on the size of the list-
decodable code or the lower bound on the list size,

$|{\bf C}|\leq L|{\bf C}_{1}|.$

Actually balls centered at codewords of ${\bf C}_{1}$ of the radius $d_{list}$
cover the whole space ${\bf F}_{q}^{n}$. Then the number of all codewords in
${\bf C}$ is not bigger than the number of codewords in these $|{\bf C}_{1}|$
balls. From this simple observation and some good covering codes in the
$b$-symbol metric the generalized Singleton bound on list-decodable $b$-symbol
metric codes can be obtained.

Proposition 4.1. An $(d,L)$ list-decodable $b$-symbol code ${\bf C}\subset{\bf
F}_{q}^{n}$ has its cardinality $|{\bf C}|\leq L\cdot q^{n-d+b-1}$.

Proof. We take a linear $[n,n-d+b-1]_{q}$ code ${\bf C}_{1}$ with linear
independent first $k$ columns in one of its generator matrix. Then the
covering radius of ${\bf C}_{1}$ in the $b$-symbol metric is at most
$n-(n-d+b-1)+b-1=d$. The conclusion follows from the above simple observation.

When $L=1$ and $d=\lfloor\frac{d_{b}({\bf C})-1}{2}\rfloor$, this bound is
weaker than the Singleton bound $|{\bf C}|\leq q^{n-d_{b}({\bf C})+b}$.
However it holds for any list size.

This bound can be improved significantly as follows. Let ${\bf H}$ be the
following $tm\times n$ matrix where $n=\frac{t(q^{m}-1)}{q-1}$.

$\left(\begin{array}[]{cccccccccccccccc}{\bf H}_{1}&{\bf 0}&{\bf
0}&\cdots&{\bf 0}\\\ {\bf 0}&{\bf H}_{2}&{\bf 0}&\cdots&{\bf 0}\\\ {\bf
0}&{\bf 0}&{\bf H}_{3}&\cdots&{\bf 0}\\\ \cdots&\cdots&\cdots&\cdots&\cdots\\\
{\bf 0}&{\bf 0}&{\bf 0}&\cdots&{\bf H}_{t}\\\ \end{array}\right)$

Here ${\bf H}_{i}$ are the parity check $m\times\frac{q^{m}-1}{q-1}$ matrix
for the $[\frac{q^{m}-1}{q-1},\frac{q^{m}-1}{q-1}-m]_{q}$ Hamming code. Let
${\bf C}$ be the linear
$[n=\frac{t(q^{m}-1)}{q-1},k=\frac{t(q^{m}-1)}{q-1}-tm]_{q}$ code with the
above parity check matrix ${\bf H}$. From the equality

$R_{b}({\bf C})=\max_{{\bf v}\in{\bf F}_{q}^{n}}\\{wt_{b,coset}({\bf v}+{\bf
C})\\},$

we have $R_{b}({\bf C})=bt=\frac{b(n-k)}{m}$ if $b\leq q^{m}-1$. Then from the
above observation about list-decodable codes from covering codes, we have the
following result.

Theorem 4.1. Let $q$ be a prime power, $m$ be a positive integer, $t$ be an
even positive integer, and set $n=\frac{t(q^{m}-1)}{q-1}$. Let ${\bf
C}\subset{\bf F}_{q}^{n}$ be a $(bt,L)$ list-decodable $b$-symbol code, where
$b\leq\frac{q^{m}-1}{q-1}$. Then

$|{\bf C}|\leq Lq^{n-\frac{md}{b}}.$

When $\frac{m}{b}$ is larger than $2$, this is better than the Singleton bound
for the list-decodable codes with list size $L=1$ (and then
$d=\lfloor\frac{d_{b}({\bf C})-1}{2}\rfloor$). This is the generalized
Singleton bound for list-decodable $b$-symbol codes, which can be argued
simply from a covering $b$-symbol metric code.

Corollary 4.1. Let $q$ be a prime power and $n$ be a positive integer
satisfying $n=\frac{t(q^{5}-1)}{q-1}+v$, where $t$ is a positive integer and
$0\leq v\leq\frac{q^{5}-1}{q-1}-1$. Let ${\bf C}\subset{\bf F}_{q}^{n}$ be a
length $n$ symbol-pair code with the minimum pair distance $D\leq 4t+1$. Then

$|{\bf C}|\leq
q^{\min\\{n-\frac{5(D-1)}{4}+\frac{v}{4},n-\frac{5(D-1)}{4}+\frac{q^{5}-1}{q-1}-v\\}}.$

.

Proof. Puncturing last $v$ coordinates or adding $\frac{q^{5}-1}{q-1}-v$ zero
coordinates, and then applying Theorem 4.1 we get the conclusion.

The above results asserts that for a given minimum pair distance when the code
length is long, the above generalized Singleton bound is much stronger than
the Singleton bound $|{\bf C}|\leq q^{n-d_{2}({\bf C})+2}$ in [4] on the sizes
of the symbol-pair codes.

Since the construction of MDS symbol-pair codes in two papers [4, 24] there
have been many constructions on the MDS symbol-pair codes in [5, 11, 9, 10,
25] from cyclic or constacyclic codes. However no upper bound on the lengths
of general MDS symbol-pair codes has been given. It was proved in [11] that
lengths of linear MDS symbol-pair codes over ${\bf F}_{q}$ of the minimum pair
distance $5$ or $6$ can not larger than $q^{2}+q+1$ or $q^{2}$. From Corollary
4.1 we give the following upper bound on the lengths of (even no linear) MDS
symbol-pair codes.

Corollary 4.2. Let ${\bf C}\subset{\bf F}_{q}$ be a symbol-pair code with the
length $n$ and the minimum pair distance $D$. If $n$ and $D$ satisfy
$D>2q^{5}+1$ and $n>\frac{(D-1)(q^{5}-1)}{2(q-1)}$. Then the symbol-pair code
${\bf C}$ is not MDS. In particular there is no MDS symbol-pair binary code
with the minimum pair distance $D\geq 63$ and the length
$n\geq\frac{31(D-1)}{2}$.

##  5 Conclusion

In this paper covering codes and covering radii of some famous linear codes in
the $b$-symbol metric are considered. First of all some classical beautiful
results about covering codes in the Hamming metric, such as the Delsarte bound
and the Norse bound, are not true in the pair metric. Some highly nontrivial
upper and lower bounds on covering radii of some cyclic, constacyclic and
algebraic-geometric codes in the $b$-symbol metric are given. The covering
radius of the Reed-Solomon code as a $b$-symbol code is determined. As an
application of covering $b$-symbol metric codes, the generalized Singleton
bound on list-decodable $b$-symbol codes is proved and an upper bound on the
lengths of general MDS symbol-pair codes is given. We give a simple sufficient
condition of non-perfect code in the $b$-symbol metric and prove that many
well-known codes are not perfect in the $b$-symbol metric. It is an
interesting open problem to classify all perfect codes in $b$-symbol metric
for small $b=2$ or $3$. In particular is there any perfect symbol-pair code of
the minimum pair distance bigger than or equal $9$?

## References

  * [1] E. Byrne and A, Ravagnani, Covering radius of matrix codes endowed with rank metric, SIAM J. Discrete Math., vol. 31, no. 2, pp. 927-944, 2018.
  * [2] Y. Cassuto and M. Blaum, Codes for symbol-pair read channels, IEEE Trans. Inf. Theory, vol. 57, no. 12, pp. 8011-8020, 2011.
  * [3] Y. Cassuto and S. Litsyn, Symbol-pair codes: Algebraic constructions and asymptotic bounds, Proc. IEEE Int. Sym. Inf. Theory Process., St. Peterburg, pp. 2348-2352, Jun. 2011.
  * [4] Y. M. Chee, L. Ji, H. M. Kiah, C. Wang and J. Yin, Minimum distance separable codes for symbol-pair read channels, IEEE Trans. Inf. Theory, vol. 59, no. 11, pp. 7259-7267, 2013.
  * [5] B. Chen, L. Lin and H. Liu, Constacyclic symbol-pair codes: Lower bounds and optimal constructions, IEEE Trans. Inf. Theory, vol. 63, no. 12, pp. 7661-7666, 2017.
  * [6] K. Chen, On the non-existence of perfect codes with rank distance, Math. Nachr., vol. 182, pp. 89-98, 1996.
  * [7] G. D. Cohen, I. Honkala, S. Litsyn and A. Lobstein, Covering codes, North-Hollan Math, Libarary, Elsecier, 1997.
  * [8] P. Delsarte, Four fundamental parameters of a code and their combinatorial significance, Inform. and Control, vol. 23, pp.407-438, 1973.
  * [9] H. Q. Dinh, B. T. Nguyen and S. Sriboonchitta, MDS symbol-pair cyclic codes of length $2p^{s}$ over ${\bf F}_{p^{m}}$, IEEE Trans. Inf. Theory, vol. 66, no. 1, pp. 240-262, 2020.
  * [10] H. Q. Dinh, X. Wang, H. Liu and S. Sriboonchitta, On the $b$-distances of repeated-root constacyclic codes of prime power lengths, Discrete Mathematics, vol. 343, no. 4, 11780, 2020.
  * [11] B. Ding, G. Ge, J. Zhang, T. Zhang and Y. Zhang, New constructions of MDS symbol-pair codes, Designs, Codes and Cryptography, vol. 86, no. 4, pp. 841-859, 2018.
  * [12] R. Dougherty and H. Janwa, Covering radius computations for binary cyclic codes, Mathematics of Computation, vol. 57, no. 195, pp. 415-434, 1991.
  * [13] D. Elimelech, M. Firer and M. Schwartz, The generalized covering radii of linear codes, IEEE Trans. Inf. Theory, vol. 67, no. 12, pp. 8070-8085, 2021.
  * [14] O. Elishco, R. Gabrys and E. Yaakobi, Bounds and constructions of codes over symbol-pair read channels, IEEE Trans. Inf. Theory, vol. 66, no. 3, pp. 1385-1395, 2020.
  * [15] F. J. Freibert and J-L. Kim, Optimal subcodes and optimum distance profiles of self-dual codes, Finite Fields and Their Applications, vol. 25, pp. 146-164, 2014.
  * [16] F. J. Freibert, Self-dual codes, subcode structures and applications, University of Louisville Dissertation, 2012.
  * [17] M. Gadouleau and Z. Yan, Packing and covering properties of rank-metric codes, IEEE Trans. Inf. Theory, vol. 54, no. 9, pp. 3873-3883, 2008.
  * [18] T. Helleseth, T. Klove and J. Mykkeltveit, On the covering radius of binary codes, IEEE Trans. Inf. Theory, vol. 24, pp. 627-628, 1978.
  * [19] W. C. Huffman and V. Pless, Fundamentals of error-correcting codes, Cambridge University Press, Cambridge, U. K., 2003.
  * [20] J. H. van Lint, Nonexistence theorems for perfect error-correcting codes, Computers in Algebra and Theory, vol. IV (SIAM-AMS Proceedings), 1971.
  * [21] H. Liu and X. Pan, Generalized pair weights of linear codes and linear isopmorphisms preserving pair weights, IEEE Trans. Inf. Theory, vol. 68, no. 11, pp. 105-117, 2022.
  * [22] S. Liu, C. Xing and C. Yuan, List decoding of symbol-pair codes, IEEE Trans. Inf. Theory, vol. 65, no. 8, pp. 4815-4821, 2019.
  * [23] S. Litsyn, Tables of the best known binary covering codes, http://www.eng.tau.il/ litsyn/.
  * [24] X. Kai, S. Zhu and P. Li, A construction of new MDS symbol-pair codes, IEEE Trans. Inf. Theory, vol. 61, no. 11, pp. 5828-5834, 2015.
  * [25] J. Ma and J. Luo, MDS symbol-pair codes from repeated-root cyclic codes, Designs, Codes and Cryptography, vol. 90, pp. 121-137, 2022.
  * [26] C. Marcolla and M. Roggero, Hermitian codes and complete intersections, Finite Fields and Their Applications, vol. 62, 101621, 2020.
  * [27] C. Shangguan and I. Tamo, Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius, Proceedings of the 52th Annual ACM Symposium on Theory of Computing (STOC), pp. 538-551, 2020.
  * [28] M. Tsfasman and S. G. Vládut, Algebraic-geometric codes, Vol.58, Springer Science and Business Media, Netherland, 2013.
  * [29] M. Shi, F. Özbudak and P. Solé, Geometric approach to $b$-symbol Hamming weights of cyclic codes, IEEE Trans. Inf. Theory, vol. 67, no. 6, pp. 3735-3751, 2021.
  * [30] A. Tietäváinen, On the nonexistence of perfect codes over finite fields, SIAM Journal on Applied Mathematics, vol. 24, pp. 88-96, 1973.
  * [31] E. Yaakobi, J. Bruck and P. H. Siegel, Construction and decoding of cyclic codes over $b$-symbol read channels, IEEE Trans. Inf. Theory, vol. 62, no. 4, pp. 1541-1551, 2016.