We are sorry to see that the reviewer has decreased their rating. We believe that there is a misunderstanding, and we are sorry for the confusion. We provide a clarification below to address this.
**1. How to achieve small approximation error in our case?** For smaller approximation error, one needs a richer function approximation scheme (please also see the second point in our response below). In our case, this can be achieved by choosing a larger dimension $d$, large radius $\rho > 0$ for the parameter space, and a well-designed set of feature vectors $\{\Phi(x): x\in\mathbb{X}\}$. We first note that our Robust TD learning algorithm with linear function approximation is flexible, and works for *any given* $d, \Phi$ and $\rho > 0$ that defines the linear function approximation class. As such, small approximation errors can be achieved by using a richer function class (large $d$ and $\rho$, and good feature vectors $\Phi$ that leads to full-rank Gram matrix) at the expense of increased sample complexity, which is reflected explicitly in our bounds in **Theorems 1-3**: if we use a larger $\rho$ (which is naturally required if dimension $d$ is large), our error bounds in all cases grow polynomially in $\rho$, which implies larger statistical error to achieve smaller approximation error. This is an instance of the bias-complexity tradeoff: better approximation capability requires larger function classes, making the parameter search harder.
For example, in an extreme case where $\mathbb{X}$ is a finite state-space (denoted by integers from 1 to $n$), $d = n$, $\rho = \frac{M}{1-\gamma}$ and $\Phi(x)$ is a unit vector with $1$ at the location of $x$, we obtain the tabular TD learning, and the function approximation error is 0. Of course, the above is tractable only if the state space $\mathbb{X}$ is small, and when $\mathbb{X}$ is large, one needs to use a function approximation scheme with $d \ll |\mathbb{X}|$ for tractability, with the hope that the underlying value function can be well-approximated by some (unknown) parameter with the specified function class. TD learning enters the picture at that point to find this unknown parameter by using only samples from the system. For example, in the case of Linear MDPs (Jin et al., 2020), one may achieve arbitrarily small error by using linear function approximation even when $d \ll |\mathbb{X}|$.
We kept our bounds as general as possible, similar to the seminal works (Tsitsiklis and van Roy, 1997; Bhandari et al., 2018), to cover these structured cases with any given $d, \rho, \Phi$.
**2. Clarification on approximation error:** The objective of an RL algorithm equipped with function approximation is to achieve the smallest error possible by using the given function approximation architecture. Approximation error is the minimum error that can be achieved by *any* algorithm that uses the given function approximation scheme. We would like to emphasize that the approximation error is independent of the algorithm, and it solely depends how rich the function class is. As such, it is not the task of TD learning to prevent encountering significant approximation errors: TD learning only aims to find the best function within the class defined by the given function approximation architecture. One needs to use a richer function class to avoid large approximation errors at the expense of larger statistical errors (i.e., sample complexity), as we discussed in the previous point.
---
Since the main focus of this work is providing the means of managing heavy-tailed noise in the RL framework, we have focused on providing the rigorous findings in the cleanest form. We hope that our response above addresses the questions asked by the reviewer, and we will be happy to include the discussion on how to release the assumption in a revision. Thank you.