Misspecified $Q$-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error

Thank you for your careful review! We address your questions below:

Practicability: In this paper, we focus on the setting where the sparsity $k$ is much smaller than the feature dimension $d$. In particular, when the sparsity $k$ is a constant, our algorithm has a polynomial dependency on $H$ and $d$. This is because we are considering a much smaller epsilon-net that exploits the sparsity structure, instead of an epsilon-net for the whole feature space. For instance, when the optimal Q-function is a $d=100$ dimensional linear function, but can be approximated by a $k=2$-sparse linear function, the sample complexity and running time of our algorithm would be quadratic and could be practical for real-life applications.

Exponentially large state space: When state space is small, we can directly use algorithms in tabular RL setting and get arbitrarily small suboptimality with polynomial sample complexity, using, for example, the algorithm in Jin et al.(2018). Therefore, we cannot construct a hard instance with a small state space.

$\Delta(\cdot)$: $\Delta(S)$ is the set of all distribution over $S$. We have added in this definition in the preliminary section in the revised version. Thank you for pointing it out.

Sphere vs. Ball: In Assumption 1, we stated that each optimal parameter $\theta_h^*$ is in the d-dimensional unit sphere $\mathbb{S}^{d-1}$. Our results can be extended to assuming $\theta_h^*$’s are in the unit ball, i.e. $\|\theta_h^*\|\leq 1$ by creating a grid for the radius.

$s_0$: Yes. We assumed the initial state $s_0$ is deterministic at line 229.

Question: In the upper bound result, we agree that we mainly exploit the sparseness through the cardinality of the set of non-zero indices and through the cardinality of the epsilon net. Therefore, the results supersede a setting where the misspecified Q-function of each layer is in a finite-sized function class as a special case. Assuming there are $F$ functions at each layer, we can construct the feature vector as $F$-dimension, where the i-th index is the value of the i-th function. Then, this setting is captured by a $1$-sparse parameter $\theta^*$.

References: Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, Michael I. Jordan. Is Q-learning Provably Efficient? Advances in Neural Information Processing Systems 31 (NeurIPS 2018)

Thank you for your careful review and positive evaluation! Below, we respond to all your questions:

Weakness1: If the parameters are shared across levels, then the problem setting can only apply to a very limited number of scenarios. Because of the sparsity assumption, such a setting only has $k$ non-zero parameters. On the other hand, our setting can be applied to a much larger range of problems since we have $Hk$ non-zero parameters.

Weakness2: We believe core RL theory is an important research topic :)

Question1: Yes. The function class setting can be thought of as a special case of our linear setting. When there are $F$ functions at each layer, we can construct the feature vector as $F$-dimension, where the i-th index is the value of the i-th function. Then, this setting is captured by a $1$-sparse parameter $\theta^*$.

Question2: If the transition is deterministic, then we could modify our Algorithm 1 to achieve $H/C \cdot \epsilon$ vs. $\exp(C)$ trade-off. Specifically, we first separate the $H$ levels into blocks, each consisting of $C$ levels. Within each block, we would traverse through all the possible actions, with in total $a^C$ trajectories. Then, we eliminate each block based on the smallest Bellman error in these trajectories. This process ensures that we incur at most $\epsilon$ suboptimality within each block, leading to $O(H/C \epsilon)$ suboptimality. The total sample complexity scale by $a^C$.

If the transition is stochastic, we might be able to use the importance sampling idea of Kearns et al. (1999) in our setting. Such a generalization could be nontrivial and we will leave it as a future work.

However, restricting the sample complexity to be polynomial in this setting forces $C$ to be a log factor, resulting in only a log improvement in suboptimality. As this improvement is relatively minor and risks complicating the presentation, we chose not to include these results in the paper.

Question3: Previous works (Weisz et al., 2022, Wang et al., 2021) show that even when the optimal Q-function is well-specified, any RL algorithm would have exponential dependency on $d$ or $H$. Note that this is equivalent to the case where the sparsity $k = d$ and the approximation error $\epsilon = 0$ in our setting. Therefore, in our misspecified setting which is strictly harder, exponential dependency on $k$ is unavoidable, unless we can accept an exponential dependency on $H$. However, we agree that a better dependency on $k$, such as $O(2^k)$ rather than $\epsilon^{-k}$, might be possible. We have added such improvements as future work.

References:

Michael Kearns, Yishay Mansour, Andrew Ng. Approximate Planning in Large POMDPs via Reusable Trajectories. Advances in Neural Information Processing Systems 12 (NIPS 1999)

Gellert Weisz, Csaba Szepesvari, and Andras Gyorgy. TensorPlan and the Few Actions Lower Bound for Planning in MDPs under Linear Realizability of Optimal Value Functions. 2022.

Yuanhao Wang, Ruosong Wang, and Sham M. Kakade. An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap. 2021

Thank you for your careful review!

First, we want to emphasize that our algorithm is not brute-force. By Assumption 1.1, each horizon $h$ has a different optimal $\theta^*_h$. Therefore, a brute-force algorithm would have a sample complexity with exponential dependency on $H$ unlike our algorithm. Moreover, In the setting where the sparsity $k$ is a constant, which is the main focus of this paper, our algorithm has a polynomial dependency on $H$ and $d$, since in our algorithm we considered a much smaller net that exploits the sparsity structure. For instance, when the optimal Q-funcion is a $d=100$ dimensional linear function, but can be approximated by a $k=2$-sparse linear function, the sample complexity and running time of our algorithm would be quadratic.

The exponential dependency on k is necessary. Previous works (Weisz et al., 2022, Wang et al., 2021) show that even when the optimal Q-function is well-specified, any RL algorithm would have exponential dependency on $d$ or $H$. Note that this is equivalent to the case where the sparsity $k = d$ and the approximation error $\epsilon = 0$ in our setting. Therefore, in our misspecified setting which is strictly harder, exponential dependency on $k$ is unavoidable, unless we can accept an exponential dependency on $H$.

References:

Gellert Weisz, Csaba Szepesvari, and Andras Gyorgy. TensorPlan and the Few Actions Lower Bound for Planning in MDPs under Linear Realizability of Optimal Value Functions. 2022.

Yuanhao Wang, Ruosong Wang, and Sham M. Kakade. An Exponential Lower Bound for Linearly-Realizable MDPs with Constant Suboptimality Gap. 2021

Thank you for your careful review and the positive score! Below, we respond to all your questions:

Computationally intractable: In this paper, we focus on the setting where the sparsity $k$ is much smaller than the feature dimension $d$. In particular, when the sparsity $k$ is a constant, our algorithm has polynomial dependency on $H$ and $d$. This is because we are considering a much smaller epsilon-net that exploits the sparsity structure, instead of an epsilon-net for the whole feature space. For instance, when the optimal Q-funcion is a $d=100$ dimensional linear function, but can be approximated by a $k=2$-sparse linear function, the sample complexity and running time of our algorithm would be quadratic.

“MDP without sample”: This setting serves as a warmup for the more complicated problem instance construction in the next section. Moreover, since our hard instance is 1-dimensional, the feature $\phi$ is equal to the optimal Q-value up to an error of $\epsilon$, so it is a very simple setting where an approximate version of the optimal Q-function is given to the algorithm. Our lower bound indicates that, even in this very simple setting, a suboptimality of $O(H\epsilon)$ is the best one can hope for. Therefore, the problem we are studying here is:

• if we are given a perturbed optimal $Q$-function, without further learning, how does the perturbation translate to the suboptimality of the resulting policy in the minimax sense.

Eliminating most promising candidate: In UCB of the Bandit setting, arms are eliminated based on the confidence bound of each arm's reward. In our algorithm, we maintain a set of all the remaining parameters, select the parameters with the largest value at each iteration, and eliminate them if the Bellman Error (Def. 4.1, measuring consistency between parameters of two consecutive horizons) is large. The two algorithms follow completely different frameworks, one maintains a set of remaining arms, and the otehr maintains a set of possible parameters.

Optimal sizes of $\epsilon_{net}$ and $\epsilon_{stat}$: The optimal value of $\epsilon_{net}$ and $\epsilon_{stat}$ depends on users' priorities. A larger value of $\epsilon_{net}$ and $\epsilon_{stat}$ leads to a larger number of iteration (Lemma 4.1) and a larger data requirement (Line 448). However, it leads to a smaller suboptimality with high probability (Line 459-461). Therefore, there is no universal optimal value of $\epsilon_{net}$ and $\epsilon_{stat}$. As a rule of thumb, if one wants the final suboptimality to scales with $\epsilon$, then $\epsilon_{net}$ and $\epsilon_{stat}$ should be in the scale of $\epsilon$.

$\epsilon$-optimal: We define $\epsilon$ as the misspecification error (Assumption 1.1). If we see $\epsilon$ as the suboptimality (i.e. $V(\pi^*) - V(\pi) \leq \epsilon$) and use a separate notation for the misspecification error, then the sample complexity would indeed need to scale by $H^2$.

However, as indicated by our lower bounds (Theorem 3.1 and 3.2), we are unable to achieve less than $O(H\epsilon)$ suboptimality (here $\epsilon$ is the misspecification error), unless we take a sample size that is exponential in $H$. We have added a footnote to clarify this.

$H^2m$: We apologize for the typo. In each iteration of the algorithm, we draw a new sample of $m$ trajectories for the estimation at each level, so we need $Hm$ samples per iteration.