A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation

Thank you for your encouraging feedback!

Q1 My main concern is about technical novelty. It seems that the only different component compared to LSVI-UCB++ is the policy-switching framework. It would be better if the authors could highlight the technical novelty, especially the part that is different from [1].

A1 Our main technical novelty lies in the new and more efficient policy-switching scheme for RL with general function approximation, where the policy is updated when the cumulative sensitivity score exceeds a predetermined threshold (as discussed in Section 3.1). Unlike the linear function approximation setting, where the rare-switching technique has been extensively studied and based on the determinant of the covariance [1], it is relatively underexplored for the function class with bounded generalized eluder dimension. We propose a low-switching scheme based on the $D^2$ quantity originally proposed by [2, 3]. Compared with [4], our algorithm has a tractable value-iteration-based planning phase and does not need to recompute the cumulative loss at each episode to check the switching criterion. [5] also considered RL with low-switching cost beyond linear function approximation, i.e., MDPs with low inherent Bellman error and generalized linear MDPs, both of which belong to the class of MDPs studied in our paper. Their approach can be seen as a slight extension of RL with low-switching cost for linear MDPs, since in both settings, the covariance matrix still exists and they can still use the determinant of the covariance as a criterion for policy switching. Furthermore, we have proved that the low switching cost of our algorithm is nearly optimal (See Appendix C for the new lower bound and its proof.)

With this new rare-switching scheme, it becomes possible to maintain a monotonic series of optimistic and pessimistic value functions while guaranteeing that the covering number of the value function class is still tractable. Previously, it was shown in [1] that ensuring monotonic value functions is crucial to obtaining minimax optimal regret bound for linear MDPs. However, it is underexplored whether similar idea can be applied to nonlinear function approximation. As discussed in Section 1, prior to our approach, the only minimax regret bound beyond linear function approximation was achieved by [3], but with a complex non-Markovian planning phase. Our work is the first work for RL with general function approximation that achieves the nearly minimax optimal regret when specialized to linear MDPs, while still enjoys simple Markov planning phase.

We have also highlighted the above technical novelty in Section 1 and Section 3 in the revision.

Q2 It is not very clear how general the function approximation is. It would be better if the authors could discuss more about the relationship between this setting and some other settings, like the linear Bellman complete MDP and the Eluder Condition class. Under these settings, [4] and [5] design algorithms with low switching cost and sub-linear regret bound.

A2 [5] considers a class of MDPs with generalized linear function, which belongs to the class of MDPs with bounded eluder dimension [6]. According to the discussion in Section 4.1, the class of MDPs studied in our paper contains the class of MDPs with bounded eluder dimension.

As for [4], it is known that both their setting and ours capture MDPs with bounded eluder dimension as special cases. However, it is unclear which one is more general and we leave it for future study.

We have also added a discussion on the two related works in Section 1 in our revision.

Q3 The presentation is not very clear. As a paper focused on theory, a proof sketch is expected. In addition, in line 6 of Algorithm 1, the switching condition is replaced by '...', which is very confusing (although it is discussed in the main text).

A3 Thank you for your suggestion. Due to the space limit of the main text, the high-level proof of the main theorems are deferred to Appendix D. We will add a proof sketch in the main text provided we are granted additional pages in the final version.

[1] He et al., Nearly minimax optimal reinforcement learning for linear markov decision processes.

[2] Ye et al., Corruption-robust algorithms with uncertainty weighting for nonlinear contextual bandits and markov decision processes.

[3] Agarwal et al., Voql: Towards optimal regret in model-free rl with nonlinear function approximation.

[4] Xiong et al., A General Framework for Sequential Decision-Making under Adaptivity Constraints.

[5] Qiao et al., Logarithmic switching cost in reinforcement learning beyond linear mdps.

[6] Russo et al., Eluder dimension and the sample complexity of optimistic exploration

Thank you for your insightful comments!

Q1 I have doubts on whether the claim that "MQL-UCB achieves near-optimal policy switching" is true. It seems to me this paper only considered the case where the algorithm is only allowed to deploy deterministic policy at each iteration, and the $\Omega(dH)$ policy switching lower bound the authors compared with also only holds for such setting. There are also several closely related works ([1] and [2]) have reported that when the algorithm can deploy stochastic or even non-Markovian policies at each iteration, the lower bound of deployment complexity would be $\Omega(H)$ and can be matched.

A1 Thank you for pointing out these two related works! To thoroughly show the optimality regarding the switching cost, we have added Appendix C in the revision, where a lower bound of order $\tilde \Omega(dH)$ is provided for arbitrary policies including random policies. The reason why we can achieve a different lower bound is that in our setting, we consider reset-free MDPs where the initial state $s_1$ at each episode may be generated according to the historical episodes (or chosen by the environment adaptively) instead of being chosen from a fixed distribution. Our lower bound is new in literature because the previous works such as [1], [2] only considered the environments which will reset the MDP to the same initial state (or initialized from the same state distribution) at the beginning of each episode.

We have also added Remark C.3 to further clarify the difference between these two settings.

Q2 What are the technical novelty and innovation in algorithm designs? Could you highlight it more clearly?

A2 Our main technical novelty lies in the new and more efficient policy-switching scheme for RL with general function approximation, where the policy is updated when the cumulative sensitivity score exceeds a predetermined threshold (as discussed in Section 3.1). Unlike the linear function approximation setting, where the rare-switching technique has been extensively studied and based on the determinant of the covariance [3], it is relatively underexplored for the function class with bounded generalized eluder dimension. We propose a low-switching scheme based on the $D^2$ quantity originally proposed by [4, 5]. Compared with [6], our algorithm has a tractable value-iteration-based planning phase and does not need to recompute the cumulative loss at each episode to check the switching criterion. [7] also considered RL with low-switching cost beyond linear function approximation, i.e., MDPs with low inherent Bellman error and generalized linear MDPs, both of which belong to the class of MDPs studied in our paper. Their approach can be seen as a slight extension of RL with low-switching cost for linear MDPs, since in both settings, the covariance matrix still exists and they can still use the determinant of the covariance as a criterion for policy switching. Furthermore, we have proved that the low switching cost of our algorithm is nearly optimal (See Appendix C for the new lower bound and its proof.)

With this new rare-switching scheme, it becomes possible to maintain a monotonic series of optimistic and pessimistic value functions while guaranteeing that the covering number of the value function class is still tractable. Previously, it was shown in [5] that ensuring monotonic value functions is crucial to obtaining minimax optimal regret bound for linear MDPs. However, it is underexplored whether similar idea can be applied to nonlinear function approximation. As discussed in Section 1, prior to our approach, the only minimax regret bound beyond linear function approximation was achieved by [4], but with a complex non-Markovian planning phase. Our work is the first work for RL with general function approximation that achieves the nearly minimax optimal regret when specialized to linear MDPs, while still enjoys simple Markov planning phase.

We have also highlighted the above technical novelty in Section 1 and Section 3 in the revision.

[1] Huang et. al., Towards Deployment-Efficient Reinforcement Learning: Lower Bound and Optimality

[2] Zhang et. al., Near-optimal regret bounds for multi-batch reinforcement learning

[3] He et al. Nearly minimax optimal reinforcement learning for linear markov decision processes.

[4] Ye et al., Corruption-robust algorithms with uncertainty weighting for nonlinear contextual bandits and markov decision processes.

[5] Agarwal et al., Voql: Towards optimal regret in model-free rl with nonlinear function approximation.

[6] Xiong et al., A General Framework for Sequential Decision-Making under Adaptivity Constraints.

[7] Qiao et al., Logarithmic switching cost in reinforcement learning beyond linear mdps.

Thank you for your insightful comments!

Q1 A few assumptions look really strong. For example, assuming completeness holds for any function as well as for second moments is not common in my opinion.

A1 The completeness for the second moment is indeed not common in existing works on RL with general function approximation. It is first introduced by [1], and is crucial for obtaining a tighter regret bound. More specifically, making use of the variance of the value function at the next state is known to be crucial to achieve minimax-optimal regret bound in RL settings ranging from tabular MDPs [2] to linear mixture MDPs [3] and linear MDPs [4]. In MDPs with general function approximation, the second-moment completeness assumption makes the variance of value functions computationally tractable. It is still an open problem whether a nearly optimal regret can be achieved in MDPs with general function approximation without this assumption.

We have also added a discussion on this point in Remark 2.3 in the revision.

Q2 The optimality of regret is only for linear MDPs, and the authors prove no lower bound for general function approximation.

A2 This is a great question. We would also like to clarify that in the literature of RL with general function approximation, sometimes people claim the result as an optimal regret bound as long as the regret is optimal when it is specialized to the linear function approximation case, e.g., [1].

Currently, we don’t know how to construct a hard-to-learn instance for general function approximation in our framework. Among existing studies of RL with general function approximation, there is a lack of lower bounds that are dependent on the complexity of the function class, except DEC [5]. However, the corresponding algorithm for DEC requires solving a non-convex min-max optimization problem over the distributions of the policy and model class, which is computationally intractable. The pursuit of methodologies to obtain a lower bound for general function approximation under Bellman completeness assumption is an interesting future direction.

Q3 Overall, the paper could be better organized, and adding some more intuitive explanations will be helpful for readers.

A3 Thank you for your suggestion. We have added more detailed explanations about our algorithmic design in Section 3.

Q4 There are quite a few typos in the paper. For example, in page 3, $O$ is missing for regrets in table 1. In page 6, a parenthesis is missing in the definition of $b_{k, h}$, and there is an excessive He et al (2022). In page 8, "may differs" should be "may differ".

A4 Thank you for pointing out these typos. We have corrected them in the revision.

Q5 Can you elaborate more on how to find the bonus oracle?

A5 In the linear case, the bonus is the elliptical norm of the feature vectors of the state-action pair, as discussed in Remark 2.5. Correspondingly, in the generalized linear setting, the bonus oracle is set to $K / \kappa$ times the elliptical norm. In the general case, according to the discussion provided in [6], to obtain the bonus function satisfying the required properties, we need to consider the constrained optimization problem $\\max \\bigg\\{ |f_1(z_h)-f_2(z_h)|, f_1,f_2 \\in \\mathcal{F}_h: \\sum\_{k \\in [K] } \\frac{(f\_1(z\_h\^k)- f\_2(z\_h\^k))\^2}{\\hat \\sigma\_{k,h}\^2} \\le (\\hat \\beta\_{k, h})\^2 \\bigg\\}$, and apply a binary search method to find the optimal solution to the optimization problem.

Q6 Why should we care about the monotonic properties of the value functions?

A6 The monotoic properties of the value function is needed for the construction of variance estimator. For each state-action pair $(s_h^k,a_h^k)$ and any subsequent episode $i>k$, the value function $V_{i,h}$ and the corresponding variance $\\big$ \mathbb{V}_h (V_{i, h+1} - V_{h+1}^* )\big $(s\_h\^k,a\_h\^k)$ may differ from the previous value function $V_{k,h}$ and variance $\\big$ \mathbb{V}_h (V_{k,h+1}-V_{h+1}^)\big $(s\_h^k,a\_h^k)$, but we still want to use the same weight $1 / \bar \sigma_{k, h}^2$ for future episode $i>k$ so that the variance $\\big$ \mathbb{V}_h (V_{i,h+1}-V_{h+1}^)\big $(s\_h^k,a\_h^k)$ can be uniformly bounded for all $i > k$. Note that $\\big$ \mathbb{V}_h (V_{i,h+1}-V_{h+1}^*)\big $(s\_h^k,a\_h^k) = O(\\mathbb{E}\_{s'\sim s\_h^k, a\_h^k}[V\_{i, h + 1} - V\_{h + 1}^*(s')])$. Thus, if we maintain a series of monotomic value functions, we can further control their variance terms by $O(\mathbb{E}\_{s'\sim s\_h^k, a\_h^k}[V\_{k, h + 1} - \check V\_{k, h + 1}(s')])$.

Q7 Given Theorem 4.4, can you rephrase the regret bound in terms of eluder dimension?

A7 Yes, according to Section 4.1, the generalized eluder dimension is upper bounded by eluder dimension up to logarithmic terms. When the number of episodes $K$ is sufficiently large, the leading term in our regret bound is $\tilde O \big(\sqrt{\dim_E(\mathcal{F}) \log \mathcal{N} \cdot HK}\big)$, where $\dim_E(\mathcal{F})$ is the eluder dimension of the function class $\mathcal{F}$.

[1] Agarwal et al., Voql: Towards optimal regret in model-free rl with nonlinear function approximation.

[2] Azar et al., Minimax Regret Bounds for Reinforcement Learning

[3] Zhou et al., Nearly minimax optimal reinforcement learning for linear mixture markov decision processes

[4] He et al., Nearly minimax optimal reinforcement learning for linear markov decision processes.

[5] Foster et al., The statistical complexity of interactive decision making

[6] Kong et al., Online sub-sampling for reinforcement learning with general function approximation.

Thank you very much for your helpful comments!

Q1 Why in definition 2.8, it is reasonable to assume a bounded covering class for bonus? Since you assume covering for $\mathcal{F}$ in 1 of Def 2.8, and def. of $\mathcal{F}$ is clear, can you derive the covering number of the bonus class rather than assuming it exists?

A1 First of all, in general function approximation, it is common to introduce the additional assumption on the covering number of bonus function classes. For example, in [1], [2], and [3], the authors either assume that the bonus function class itself is a finite class or its covering number is bounded.

Second, even when the function $\mathcal{F}$ is clearly defined and $|\mathcal{F}|$ is finite, the bonus function class $D_\mathcal{F}$ can still be very large. For example, consider $\mathcal{F} = \{f_1, f_2\}$ where $f_1$ is 1 on every state-action pair, and $f_2 = 2$ on every state-action pair. Then for $\epsilon = 1 / 4$, the covering number of $D_\mathcal{F}$ is at least the number of state-action pairs. This is because the bonus functions resulted from taking each state-action pair as historical data are far from each other in $l_\infty$ measure. Given this fact, we still need to assume the covering number of the bonus function class is finite, even though the covering number of $\mathcal{F}$ is finite. This is exactly the reason why [4] assumes the covering number of the set of state-action pairs is bounded (Assumption 2). With this assumption, they can provide an upper bound for the covering number of the bonus function class $W$ in their Proposition 2.

Q2 The update criteria in Line 6 of Algorithm 1 is incomplete, and I cannot find it directly. Maybe that corresponds to the last equation in page 5? This is crucial as it will decide the switching cost of the algorithm.

A2 Thanks for pointing out the typo! It should be Eq. (3.1) on page 5. We have added the missing condition in Line 6 of Algorithm 1 in the revision.

Q3 How is policy updated in Algorithm 1 if the "if condition" in line 6 is not satisfied? Without it how do you rollout in Line 21?

A3 If the condition is not satisfied, we will simply use the same policy as in the last episode. We have made it clear in the revision.

Q4 The monotonic value function seems to be an interesting idea that can keep the conditional variance on track. However, the explanation is too short. May I ask how could you "ensure that the pessimistic value maintains a monotonically increasing property during updates, while the optimistic value function maintains a monotonically decreasing property"? Also, you say inspired by He et al. [5], is the idea the same or there are some differences?

A4 The monotonic property is ensured by our algorithmic design stated in Lines 10 and 11 in Algorithm 1, i.e., taking the maximum (or minimum) between the current value function estimate and the value function estimate in the previous episode when the policy-switching condition is satisfied. However, taking these steps will increase the covering number of the value function class exponentially with respect to $K$ in general, which will further make the uniform convergence-based concentration for the least-square estimation of value functions vacuous.

To solve this issue, we apply the idea by [5] for linear MDPs, which uses rare policy-switching technique to reduce the number of value functions we are taking max or min. Unlike the linear function approximation setting, where the rare-switching technique has been extensively studied and based on the determinant of the covariance matrices, it is relatively underexplored for the function class with bounded generalized eluder dimension. To this end, we proposed a new rate-switching condition based on the $D^2$ quantity, i.e., Eq. (3.1) and Line 6 in Algorithm 1, making it possible to extend the idea by [5].

[1] Ye et al., Corruption-robust algorithms with uncertainty weighting for nonlinear contextual bandits and markov decision processes.

[2] Agarwal et al., Voql: Towards optimal regret in model-free rl with nonlinear function approximation.

[3] Di et al., Pessimistic nonlinear least-squares value iteration for offline reinforcement learning.

[4] Wang et al., Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension.

[5] He et al. Nearly minimax optimal reinforcement learning for linear markov decision processes.