Response to Reviewer ZRKX

Thank you for your insightful comments and suggestions! We answer your questions as follows.

Q1 Some of the assumptions look very strong. The completeness of all functions $V: \mathcal{S} \to [0, 1]$, the second-order completeness and the existence of bonus oracle are not standard to my knowledge. It seems that the weighted regression is possible only if these assumptions hold.

A1 The completeness assumption on the second moment, introduced by [1], is crucial for achieving tighter regret bounds in reinforcement learning (RL) with general function approximation. This assumption involves leveraging the variance of the value function at the next state, which is essential for obtaining minimax-optimal regret bounds in various RL settings. These settings range from tabular Markov Decision Processes (MDPs), as shown by [2], to more complex scenarios like linear mixture MDPs, as demonstrated by [3], and linear MDPs, as discussed by [4]. Given that the only previous work [1] to achieve the optimal regret bound also relies on this assumption, we believe it does not lessen the importance of our contribution. Additionally, while GOLF [9] only requires the standard completeness assumption, both in [1] and our work, a series of optimistic value functions are computed for a tractable planning phase. This requires including the optimistic/pessimistic value functions in the function classes, making the normal completeness assumption on $\mathcal{F_h}$ insufficient from an algorithmic perspective.

As for the bonus oracle, when the function class $\mathcal{F}$ is convex, [6, 7] has shown that using a binary-search based algorithm such sup over $f_1$ and $f_2$ in the bonus oracle can be efficiently and accurately evaluated. Empirically, [8] approximated uncertainty by computing the standard deviation of an ensemble of networks and showed experimental results supporting the effectiveness of using such an uncertainty weighting technique in offline RL.

Q2 The paper [5] also studies low switching reinforcement learning with general function approximation. It seems that the setting in [5] is slightly more general (please correct me if there is misunderstanding) and their algorithm is cleaner.

A2 Both their setting and ours encompass MDPs with bounded eluder dimensions as special cases. Upon closer examination, [5] proves to be slightly more general because, in our Definition 2.4, the dimension is equivalent to (3.2) in [5] after taking the supremum of each term. Compared to [5], our approach is oracle efficient, assuming an oracle is available to compute the bonus for UCB-based exploration. As discussed in Section 1, [5] addresses low-switching RL with general function approximation, achieving a switching cost of the same order. However, the algorithm in [5] features an intractable planning phase and is not statistically optimal. Additionally, checking the policy-switching in [5] requires recomputing the cumulative loss functions at every episode, which becomes inefficient when $K$ is large.

Q3 The algorithm itself is very complicated and whether it can be implemented in practice is unclear. Since low switching RL is a very practical problem, some experiments (even under the simplified linear MDP) to show the performance of the algorithm will be helpful. I am curious about how this algorithm performs compared to the standard approach: LSVI-UCB with a doubling trick under linear MDP.

A3 Since our algorithm provides a general framework for solving MDPs with general function classes, the computational complexity of our method highly relies on the efficiency of the regression subroutine and bonus oracle implementation. Actually, our proposed algorithm reduces to LSVI-UCB++ in the linear MDP case, which is a computationally efficient algorithm that shares the same computational complexity as LSVI-UCB with a doubling trick. Additionally, we want to clarify that it is a desirable property for an RL algorithm designed for general function classes to resemble a more efficient algorithm designed for simpler settings.

[1] A Agarwal, Y Jin, T Zhang. VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation. The Thirty Sixth Annual Conference on Learning Theory, 2023

[2] MG Azar, I Osband, R Munos. Minimax regret bounds for reinforcement learning. International conference on machine learning, 2017

[3] D Zhou, Q Gu, C Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. Conference on Learning Theory, 2021

[4] J He, H Zhao, D Zhou, Q Gu. Nearly minimax optimal reinforcement learning for linear markov decision processes. International Conference on Machine Learning, 2023

[5] Xiong, N., Yang, Z., and Wang, Z. A general framework for sequential decision-making under adaptivity constraints.

[6] D Kong, R Salakhutdinov, R Wang, LF Yang. Online sub-sampling for reinforcement learning with general function approximation.- arXiv preprint arXiv:2106.07203, 2021

[7] Q Di, H Zhao, J He, Q Gu. Pessimistic nonlinear least-squares value iteration for offline reinforcement learning. ICLR 2024

[8] C Ye, R Yang, Q Gu, T Zhang. Corruption-robust offline reinforcement learning with general function approximation. Advances in Neural Information Processing Systems, 2024

[9] C Jin, Q Liu, S Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances in neural information processing systems, 2021

Response to Reviewer Zbvr

Thank you for your positive feedback! We address your questions point-by-point.

Q1 The assumptions made on completeness and eluder dimension are somehow stronger than the usual assumptions in related literatures. Is there a lower bound showing that the normal completeness assumption $\mathcal{T}\_h \mathcal{F}\_{h + 1} \subseteq \mathcal{F}\_h$ is not enough?

A1 To our knowledge, there is no lower bound proving that the normal completeness assumption$\mathcal{T}\_h \mathcal{F}\_{h + 1} \subseteq \mathcal{F}_h$ is insufficient for achieving a minimax optimal regret bound. However, all existing works that achieve minimax optimal regret for linear MDPs or MDPs with general function approximation require estimating the variance of the next-state expected return. This necessitates a slightly stronger completeness assumption of the second-order moment. Additionally, while GOLF [1] only requires the standard completeness assumption, both in [2] and our work, a series of optimistic value functions are computed for a tractable planning phase. This requires including the optimistic/pessimistic value functions in the function classes, making the normal completeness assumption on $\mathcal{F_h}$ insufficient from an algorithmic perspective.

Q2 In the algorithm, calculating $D_{\mathcal{F}}$ requires solving an optimization problem over $f_1, f_2 \in \mathcal{F}$, which is not computational tractable due to the non-convexity of the function. Is there any way to bypass this?

A2 Thanks for your insightful question! Here we do not require the functions are convex. However, when the function class $\mathcal{F}$ is convex, [2, 3] have showed that using a binary-search based algorithm such sup over $f_1$ and $f_2$ in the bonus oracle can be efficiently and accurately evaluated. Empirically, [4] approximated the uncertainty by computing the standard deviation of an ensemble of networks and showed experimental results supporting the effectiveness of using such an uncertainty weighting technique in offline RL.

[1] C Jin, Q Liu, S Miryoosefi. Bellman eluder dimension: New rich classes of rl problems, and sample-efficient algorithms. Advances in neural information processing systems, 2021

[2] D Kong, R Salakhutdinov, R Wang, LF Yang. Online sub-sampling for reinforcement learning with general function approximation.- arXiv preprint arXiv:2106.07203, 2021

[3] Q Di, H Zhao, J He, Q Gu. Pessimistic nonlinear least-squares value iteration for offline reinforcement learning. ICLR 2024

[4] C Ye, R Yang, Q Gu, T Zhang. Corruption-robust offline reinforcement learning with general function approximation. Advances in Neural Information Processing Systems, 2024

Response to Reviewer 6wYy

Thank you so much for your strong support! We address your questions as follows.

Q1 It would be helpful to provide a bit more details for readers who are not very familiar with the literature on RL with policy switching cost on how to obtain the counting of switches in Table 1. For example, [1] doesn't seem to optimize the number of policy switches (while only trying to optimize the regret).

A1 Thanks for your suggestion! In [1], to compute the bonus function, the authors slightly generalize the method proposed by [2] (see Algorithm 2, [1]). According to Theorem 1 in [2], the utilization of this online subsampling subroutine will automatically lead to an $\tilde{O}(\dim(\mathcal{F})^2H)$ switching cost guarantee. We will add the explanation for the result shown in the table in the revision. Specifically, [2] employs online subsampling techniques, which maintain a small 'core' set of the history data and the policy is switched only if the subset is updated. In contrast, our algorithm applies a novel uncertainty-based policy switching strategy, which directly controls the cumulative sensitivity of historical datapoints.

Q2 You have proposed an algorithm that achieves optimality of regret of switching costs simultaneously under the condition that $K$ is large. Also, the lower bound from Theorem B.1 suggests $\tilde{O}(\dim H)$ is unavoidable when one wants to achieve a regret sublinear in $K$. Obviously, the current results will not make sense if the number of episodes is relatively small compared to the length of the episode. I am thus wondering: do you have any insights (what can be done and what cannot be done) in this different regime?

A2 Thanks so much for your insightful question!

• For the regret bound, when restricted to linear MDPs, our regret bound still suffers from the $\tilde{O}(H^{2.5}d^5\sqrt{H + d^2})$ $K$-independent term, which will be the leading term when $K = O(H^4d^8(H + d^2))$. If we aim to achieve better results in the small $K$ regime, it is crucial to improve the $\tilde{O}(H^{2.5}d^5\sqrt{H + d^2})$ term in the current regret upper bound. Essentially, this term results from the inaccuracy of the variance estimators. It is still an open problem if we can achieve optimal regret for linear MDPs even when $K$ is relatively small. To tackle this issue, we may consider (1) more accurate estimation of the variance term $\sigma_{k, h}$ (e.g. [3] for linear mixture MDPs) or (2) variance-aware confidence set which does not require additional knowledge of the value of variance [4, 5, 6].

• For the switching cost, our lower bound also holds when $K$ is small. For example, if $K = o(\dim(\mathcal{F}) H)$, our lower bound can be interpret as 'to achieve sublinear regret, the switching cost should be $\Omega(\dim(\mathcal{F}) H)$'. Since such a high switching cost is not achievable, our lower bound result implicitly implies that sublinear worst-case regret is not possible when $K = o(\dim(\mathcal{F}) H)$.

[1] A Agarwal, Y Jin, and T Zhang. "VOQL: Towards Optimal Regret in Model-free RL with Nonlinear Function Approximation." The Thirty-Sixth Annual Conference on Learning Theory. PMLR, 2023.

[2] D Kong, R Salakhutdinov, R Wang, L Yang. "Online sub-sampling for reinforcement learning with general function approximation"

[3] D Zhou, Q Gu. "Computationally efficient horizon-free reinforcement learning for linear mixture mdps." Advances in neural information processing systems, 2022

[4] Z Zhang, J Yang, X Ji, SS Du. "Improved variance-aware confidence sets for linear bandits and linear mixture mdp." Advances in Neural Information Processing Systems, 2021

[5] H Zhao, J He, D Zhou, T Zhang, Q Gu. "Variance-dependent regret bounds for linear bandits and reinforcement learning: Adaptivity and computational efficiency." The Thirty Sixth Annual Conference on Learning Theory, 2023

[6] Z Zhang, JD Lee, Y Chen, SS Du. "Horizon-Free Regret for Linear Markov Decision Processes." ICLR 2024