Exploring the State and Action Space in Reinforcement Learning with Infinite-Dimensional Confidence Balls

Rebuttal:

Q1: The proof appears to be incomplete and is hard to follow. It is not clear how the concentration analysis in A.2 helps the regret bound in A.1. It is not clear how these two parts relate to each other and it is further unclear how "the sum of the right-hand side" is bounded in Lemma 3, without invoking the later lemmas.

A1: We're really sorry if any process of our proof puzzled you. Let us explain it to you. After we get the Lemma 3, which means $Regret(NH) \lesssim \sqrt{\beta_{N+1}}NH^2+H\sum_{n=1}^{N}\mathbb{P}[E_n=0]$, it is natural for us to consider bounding the right side. The first term of the right side is determined by the radius of the confidence ball, while the second term of the right side require the probability that $M^*$ is in the confidence ball. It is actually a trade-off about the confidence ball, so we want to learn more about how "small" can the confidence ball be if we want to ensure a high probability that $M^*$ is in the confidence ball, which is the Lemma 6, the final goal of A.2 Concentration. So we start A.2.

Then in the A.3, we use Lemma 6, which shows the relation between the two terms of the right side of Lemma 3, and set optimal values to minimize the order of the sum of the two terms. Finally, by Lemma 3, we complete the bound of the Regret.

We don't exactly know if we have explained it clearly. So if there is still any problem, feel free to question us. What's more, thanks to your advice, we have added some detailed ideas of proof in our revised version.

Q2: Some related works appear to be missing, such as earlier works on sample-efficient RL for low-rank MDPs or MDPs with bounded Bellman-Eluder dimension, or recent works such as admissible Bellman characterization.

A2: Related work:

There is a line of work on sample efficient RL in low rank MDPs [1][2]. [3] introduces Bellman Eluder dimension to find the minimal structure assumptions that empower sample efficient learning. [4] proposes an Admissible Bellman Characterization class that subsumes nearly all MDP models in the literature for tractable RL.

[1]Agarwal A, Kakade S, Krishnamurthy A, et al. Flambe: Structural complexity and representation learning of low rank mdps[J]. Advances in neural information processing systems, 2020, 33: 20095-20107.

[2]Shah D, Song D, Xu Z, et al. Sample efficient reinforcement learning via low-rank matrix estimation[J]. Advances in Neural Information Processing Systems, 2020, 33: 12092-12103.

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

[4]Chen Z, Li C J, Yuan A, et al. A general framework for sample-efficient function approximation in reinforcement learning[J]. arXiv preprint arXiv:2209.15634, 2022.

Q3: Is it assumed, perhaps implicitly, that the reward function is known beforehand? The paper appears to estimate the transition kernel only and does not discuss how the reward function $r$ is estimated. It would be surprising if the paper can obtain the regret guarantee without any regularity assumptions on the reward function.

A3: In our paper, we need to know the immediate reward $r_h(s,a)$ after playing $a$ at $s$. This is in fact without loss of generality because learning about the environment $P$ is much harder than learning about $r$. In the case if $r$ is unknown, we can extend our algorithm by adding a step of optimistic reward estimation like in LinUCB. There are also works having the same assumptions on reward.[1][2][3]

[1]Yang L, Wang M. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound[C]//International Conference on Machine Learning. PMLR, 2020: 10746-10756.

[2]Agrawal S, Jia R. Optimistic posterior sampling for reinforcement learning: worst-case regret bounds[J]. Advances in Neural Information Processing Systems, 2017, 30.

[3]Azar M G, Osband I, Munos R. Minimax regret bounds for reinforcement learning[C]//International Conference on Machine Learning. PMLR, 2017: 263-272.

Q4: Algorithm 2 requires $S$ and $A$ to be finite, which is not assumed by Section 3.4.

A4: The simulation (Algorithm 2) is based on a special case that the state and action space is finite (and thus the kernel space must be finite-dimensional) just as the Section 3.4, where we have defined the setting of the RKHS model in this specific case.

Rebuttal:

Q1: The computational complexity of the proposed method has not been addressed.

A1: Our algorithm and computation does not scale with the very large dimension of the state and action space, instead it is actually related to the Hilbert space which contains real-valued functions (that we want to include) based on the state and action space. For example, if there is a really large state and action space with a finite-dimensional ($d$) feature space, then our algorithm may only scale with the dimension $d$ hidden in the constant of our RKHS regularity. This case reduces to Yang & Wang. Therefore, in the case of infinite state spaces, if the feature space is finite-dimensional, our algorithm coincides with Yang & Wang(2020), achieving an algorithm similar to our Algorithm 2.

Q2: It would be beneficial to explain in detail what specific challenges arise and how they were addressed using mathematical techniques in the paper compared with Yang & Wang 2020.

A2: Obtaining a similar outcome of regret bound in an infinite-dimensional case is not trivial. On one hand, many of the techniques available in the finite-dimensional setting are difficult to use in our proof. We overcome these problems using Fr$\acute{e}$chet derivatives, Azuma-type inequality for Banach space-valued martingales, and many other tools.

On the other hand, generalizing the model to the RKHS framework is not a trivial task. Specifically, instead of naively assuming that the transition probability $P$ belongs to an RKHS, we assume a more delicate structure of $P$ which is that $P$ has a decomposable structure, as illustrated in Assumption 1. Only on this assumption can we derive an efficient algorithm to conduct RL but still make the model quite general as long as $P$ is smooth enough. Naively assuming $P$ belongs to an RKHS will lead to an unattainable outcome.

Q3: There is a gap between the settings discussed in the paper and the simulations.

A3: Our simulation is just a special case of our theory and Algorithm 1. Our theory and Algorithm 1 are much more universal and applicable to more cases since their modeling is infinite-dimensional. We have compared Algorithm 2 with established techniques such as Q-Learning and SARSA and found that our Algorithm 2 reaches a lower regret in this specific case in our latest edition.

Q4: The regret bound of RKHS-RL does not include the effective dimension of the kernel. In that case, does the regret not depend on dimension even when using a finite-dimensional kernel?

A4: The regret may depend on dimension when using a finite-dimensional kernel since constants in Assumption 2 (RKHS regularity) may depend on the dimension of the kernel. We can see A5 as an example.

Q5: In the finite-dimensional case of RKHS-RL, how is the regularity bound in Assumption 2 defined?

A5: Under our finite-dimensional case of RKHS-RL, Assumption 2 reduces to $\sum_{s,a,\widetilde{s}} M((s,a),\widetilde{s})^2 \leq C$, $d_1+d_2 \leq C$, $d_1\leq C$, $0\leq c\leq 1\leq C$, where $d_1$ is the dimension of $\mathcal{S}$ and $d_2$ is the dimension of $\mathcal{A}$. Our regularity bound isn't related to the dimension of state-action space but may scale with the dimension of the kernel (this case reduces to Yang & Wang).

Q6: Why does Figure 1-(b) show negative values for regret?

A6: Thanks for your correction. We made some mistakes in the former edition, mistaking the step-by-step strategy obtained by Q-learning as the best strategy when calculating the regret. We have corrected this mistake in the revised edition and added some comparisons with other algorithms like Q-learning and SARSA.

Q7: How does the following inequality in the Proof of Lemma 2 hold? :

A7: Thanks for your question. Under the assumption that the Lebesgue measure of space $S$ is finite, we can use the Jensen's inequality and get that

$H ||$ $\Phi_{n,h}$ $\tilde{\circ}$ $(M^* - M'_n)$ $||_1$

$\lesssim$ $H ||$ $\Phi_{n,h}$ $\tilde{\circ}$ $(M^* - M'_n)$ $||_2$

Q8. How was it possible to achieve a tight regret bound with respect to $H$ when compared to the regret bound of Yang & Wang (2020)?

A8. We achieve a tight regret bound with respect to $H$ when compared to the regret bound of Yang & Wang (2020) because the "radius" of our confidence ball $\beta_n$ converges faster than Yang & Wang (2020).

Rebuttal:

Thanks for your encouraging words and constructive comments. We sincerely appreciate your time in evaluating our work. Our point-to-point responses to your comments are given below.

Q1: Empirical Evidence: The paper could be strengthened by including more empirical evidence to support the theoretical findings.

A1: We have added the comparison with existing methods like Q-Learning and SARSA in our simulation of finite-dimensional case(Algorithm 2) and concluded that our algorithm achieves a lower regret.

Q2: Scalability and Computation: While the theoretical aspects are strong, the paper does not thoroughly address the scalability of the algorithm. The paper could improve by discussing how this aspect of the algorithm translates to practical implementations and what trade-offs might be involved.

A2: About Scalability: Since our algorithm needs to get the estimated function $M_n$ by the idea of kernel ridge regression, the computational complexity scales with the state-action pairs. However, it does not scale with the very large dimension of the state and action space. Instead, it is related to the Hilbert space which contains real-valued functions (that we want to study) based on the state and action space. For example, if there is a very large state and action space with finite features, then our algorithm may only scale with the feature dimension $d$ hidden in the constant of our RKHS regularity. This case reduces to Yang & Wang. About Practicality: The practical implementation of the infinite-dimensional confidence ball is solving the maximum problem in equation (4). We present a practical approach for addressing the maximum problem. Leveraging the representer theorem, we express the objective function $M_n$ as a linear combination of kernels. Through the application of Lagrange Duality, we effectuate a conversion of the constrained optimization problem into a penalized version. By substituting the linear combination for $M_n$, we successfully reframe the original infinite-dimensional problem as a finite-dimensional quadratic counterpart. Consequently, this transformation enables an efficient solution to the problem.

Q3: Generalization and Application: The paper would benefit from a discussion on the generalization capabilities of RKHS-RL across different domains and a demonstration of its application to real-world problems, which are areas of interest in the references.

A3: Our algorithm can be used in different domain of state by using different kernels. In practice, our infinite-dimensional modelling can capture nonlinearity which is more practical. What's more, RKHS-based model can tackle the curse of dimensionality and it offers greater flexibility in capturing intricate patterns and relationships. Furthermore, kernel methods can proceed with high-dimensional data.

Q4: Is it a typo in section 4 simulation? (we observe that $\operatorname{Regret}(T) / N^{2 / 3}$ is bounded.)

A4: Thanks for your correction. We have corrected this typo in our revised version.

Q5: Assumptions of RKHS-Embedding: Could you elaborate on the conditions under which the RKHS-embedding of transition probabilities is a valid assumption? Are there known classes of RL problems where this assumption may not hold?

A5: Assumption 1 can be satisfied if the coefficient of basis expansion for $P((s,a),\tilde{s})$ decays fast enough. In specific, let $\{a_{ij}\}$ be the coefficient of basis expansion $P((s,a),\tilde{s})=\sum_{i,j}a_{ij}h_i(s,a)g_j(\tilde{s})$, where $\{g_i\}$ is the orthonormal basis in $\mathcal{L}^2(\mathcal{S})$ and $\{h_i\}$ is the orthonormal basis in $\mathcal{L}^2(\mathcal{S}\times\mathcal{A})$. Let $\{\gamma_i\}$ be the eigenvalues of $\mathcal{H}_1$ and $\{\mu_j\}$ be the eigenvalues of $\mathcal{H}_2$.

Then Assumption 1 can be satisfied as long as $\sum_{i,j} a_{ij}^2/\gamma_i^3 \mu_j < \infty$. For example, $\{\gamma_i\}$ and $\{\mu_j\}$ are polynomial decay, corresponding to $\mathcal{H}_1$ and $\mathcal{H}_2$ are sobolev spaces.

$\gamma_i\leq i^{-\alpha}$ and $\mu_j\leq j^{-\beta}$ for some $\alpha$ and $\beta$. If $a_{ij}\leq i^{-3\alpha/2-1}j^{-\beta/2-1}$, then Assumption 1 will be satisfied. This rate of decay can be satisfied by most of the smooth functions. Details will be in the updated paper.

Q6: Hyperparameter Sensitivity: How sensitive is the RKHS-RL algorithm to the choice of hyperparameters, including the selection of kernels and regularization parameters in ridge regression?

A6: The choice of some hyperparameters like $\lambda_n$ is determined in our theoretical proof. Also, we have done some tests on the choice of $\lambda_n$ in simulation in our updated supplementary material. We can see that in this case, the order of $\lambda_n$ is insensitive to the regret. Considering the constant coefficient term, we can get it through cross-validation. The selection of kernel is determined by real-world setting.