HAL: Harmonic Learning in High-Dimensional MDPs

Thank you for finding our work interesting and clear, and thank you for providing review for our paper.

---

1. ” This paper is based on the key notion of $\epsilon$-Stable Basis for both linear MDPs and general function approximation. A natural question directly comes to me is the existence of such $\epsilon$-Stable Basis. As it requires all $s,a$ to hold for the inequality, it is not trivial. I suggest the author may have more discussions about this such as providing some proofs. Maybe some smoothness assumptions over rewards are required. The paper adopts the Fourier basis in experiments, maybe the authors can show the Fourier basis satisfy the inequality.“

---

One natural class of smoothness assumptions that lead to an $\epsilon$-stable basis is that the reward function and the feature map do not have a large projection onto any individual basis vector $v_i$. In particular, for a feature map $\Phi:S\times A\to \mathbb{R}^{\kappa}$ we assume that $\lvert\hat{\Phi}(s,a)\_i\rvert = \lvert\Phi(s,a)^{\top}v\_i\rvert < \epsilon/2$ for all $i$. Similarly, the reward function can be written as $r(s,a) = \Phi(s,a)^{\top}w_r$ a some vector $w_r \in \mathbb{R}^{\kappa}$. We assume that $\lvert v_i^{\top}w_r \rvert < \epsilon/2$ for all $i$. Finally, without loss of generality by rescaling the rewards we may assume that the parameters $\theta$ of the $Q$ function are bounded i.e. $\lVert \theta \rVert \leq 1$. Under these smoothness assumptions we have that

$\Phi(s,a)^{\top}\theta = Q_{\theta}(s,a) = \mathbb{E}\left[\sum_t\gamma^t r(s_t,a_t)\right] = \mathbb{E}\left[\sum_t\gamma^t \Phi(s_t,a_t)\right]^{\top}w_r.$

Rewriting the above in the orthonormal $v_i$ basis we have

$\sum\_{j=1}^{\kappa} \hat{\Phi}(s\_t,a\_t)\_jv\_j^{\top}\theta = \sum\_{j=1}^{\kappa}\mathbb{E}\left[\sum\_t\gamma^t \hat{\Phi}(s_t,a_t)\_j\right]v\_j^{\top}w\_r.$

Hence

$\left\lvert \frac{1}{\kappa}\Phi(s,a)^{\top}\theta - \hat{\Phi}(s,a)\_i v\_i^{\top}\theta \right\rvert = \left\lvert\frac{1}{\kappa}\sum\_{j=1}^{\kappa}\mathbb{E}\left[\sum\_t\gamma^t \hat{\Phi}(s\_t,a\_t)\_j\right]v\_j^{\top}w\_r - \hat{\Phi}(s,a)\_i v\_i^{\top}\theta\right\rvert < \frac{1}{\kappa} \cdot\kappa\epsilon/2 + \epsilon/2\lVert\theta\rVert \leq \epsilon$

That is, we have proved that under smoothness assumptions on the rewards and the feature map, the basis $v_1,\dots,v_{\kappa}$ is an $\epsilon$-stable basis.

Furthermore, these smoothness assumptions are quite natural in the case of the Fourier basis. In particular, the feature map that produces natural two-dimensional images is indeed smooth with respect to the Fourier basis. This follows from the fact that the Fourier transform of natural images are spread out, i.e. if $v_i$ is the Fourier basis $\lvert\hat{\Phi}_i(s,a)\rvert$ is bounded for all $i$ whenever $s$ is a natural image. Similarly, if we assume the rewards depend on some “natural features” of natural images, we expect the reward function to also be smooth with respect to the Fourier basis.

---

2. “For the key algorithm 2: HAL: Harmonic Learning, I think it is worthwhile to explain the main steps in detail. For example, like line 277, the authors mention it is the discrete Fourier transform of the state s in section 4.1, but what is $m,n$ and $s(m,n)$ ? (I guess it is something like grids to discretize $s$, maybe the author can explain this in detail.)”

---

Yes, indeed $m$ and $n$ represents the indices of high dimensional two axis input. For instance, for images $x(m,n)$ would correspond to a particular pixel value.

---

3. “One more question: the theorems in section 3 hold for real Q function, will similar results hold for estimated Q function? I understand this is not easy to understand and make it clear during rebuttal. The authors can only provide some high-level explanation to me.”

---

Similar results will hold for the estimated $Q$-function as long as it is sufficiently close to the real $Q$-function. The basic idea is that if we have an estimated $\hat{Q}(s,a)$ that assigns values that are within $\epsilon’$ of the true $Q(s,a)$, then an $\epsilon$-stable basis for $Q(s,a)$ will be an $\epsilon + \epsilon’$-stable basis for $\hat{Q}(s,a)$. Similarly, all the arguments we make will go through with the error parameter $\epsilon + \epsilon’$

Thank you for stating that our paper explains the idea very well with promising results in sample-efficiency while further considering several different approaches to study robustness.

---

1. “How is the epsilon-stable basis different from radial basis functions [1]?”

---

These are completely different concepts.

The radial basis functions are a set where each function $\phi_c$ is associated with a point $c$, and the value of $\phi_c(x)$ only depends on the distance from $c$ to $x$ in some norm.

An $\epsilon$-stable basis is a set of vectors $\{v_i\}$ such that subtracting the $v_i$ component from the state observation will not significantly change the optimal $Q$-function in an MDP.

These are just completely different concepts that happen to have the word “basis” in them.

---

2. ”While the authors allude to the robustness of their method I am unclear as to what is the robustness with respect to? I would expect them to explain how Korkzman, 2024 measure natural robustness (line 314-315). While the authors do describe a measure for "impact on the policy performance" (line 382) I am not sure if this is the same as natural robustness. They also plot the score $\mathcal{I}$ wrt $\delta$ but I do not see an explaination as to what $\delta$ is and how it is connected to the frequency of the Fourier basis. I have a guess based on algorithm 3 but I would expect it to be explained in detail as it is central to the authors' work.“

---

Please see that natural robustness is initially introduced in [1], and also has been recently used to measure and understand deep reinforcement learning robustness in [2]. We describe the work [1] between Line 131 to 134 and also further refer to it in Line 484 and Line 485. Essentially this work [1] demonstrates that deep reinforcement learning policies are vulnerable to imperceptible natural adversarial attacks, and furthermore reveals these natural adversarial perturbations cause more damage on the policy performance compared to adversarial perturbations, and furthermore robust training techniques cannot in fact resist and indeed are non-robust against these natural invisible perturbations.

$\delta$ has been described in Line 375 and 377. Furthermore, Figure 3 also provides a visual understanding of $\delta$.

[1] Adversarial Robust Deep Reinforcement Learning Requires Redefining Robustness. AAAI 2023.

[2] Understanding and Diagnosing Deep Reinforcement Learning. ICML 2024.

---

3. ”Issues with time variance vs time invariance: up until section 3 you use time variant notation for $Q$ function and parameters, then in section 3.1 and later you drop this notation. This gives me the impression that you are switching the setting. I hope they can clarify this. It surfaces again in line 284 of algorithm 2 but then it is nowhere in rest of the algorithm. This can be confusing for the reader.“

---

The provable regret bounds that we refer to in our theoretical analysis hold in the general time-varying MDP setting. The setting of time-invariant MDPs is a subset of time-varying MDPs and is the main case of interest in deep reinforcement learning in which our empirical analysis is conducted. Hence, the theoretical foundations capture the most general setting available.

---

6. “How does the algorithm handle computational complexity as the state dimension d increases?”

---

Harmonic learning only requires taking a Fourier transform of the state-observation, and subsequently an inverse Fourier transform. The fast Fourier transform (FFT) algorithm can be used for both of these operations, and runs in time $O(n \log n)$ for $n$-dimensional state-observations. Thus, the method scales quite well to higher dimensional larger state spaces.

Thank you for stating that our paper introduces a unique approach with experimental results supporting the robustness and sample efficiency of our algorithm.

---

1. ”The experimental evaluation only includes a comparison with inverse Q-learning, lacking other standard benchmarks. Including additional benchmarks, such as Generative Adversarial Imitation Learning (GAIL) or Adversarial Inverse Reinforcement Learning (AIRL), would help position the proposed algorithm within the broader IRL landscape and offer a more comprehensive evaluation.”

---

Please find the general comparison below. Particularly, please note that inverse Q learning [1] already substantially outperforms GAIL and VDice, and VDice outperforms AIRL, and nonetheless harmonic learning is the best performing algorithm amongst all of them.

These results once more demonstrate that harmonic learning substantially outperforms a broad portfolio of existing training methods.

We can add our Table to the paper to offer a more comprehensive evaluation within the broader IRL landscape.

[1] IQ-Learn: Inverse soft-Q Learning for Imitation, NeurIPS 2021. [Spotlight Presentation]

---

2. “Why was inverse Q-learning selected as the only comparison benchmark? It is recommended that the authors give a stronger justification or provide additional experiments.”

Please see our response to Item 1.

---

3. ”The authors introduce a novel robustness measure, referred to as SBRA, to evaluate RL policy robustness. While the intuition and process behind SBRA are described, its effectiveness as a robustness metric appears inadequately supported. The current evidence, including Figure 2, does not provide sufficient support for SBRA as a reliable or comprehensive robustness measure.”

---

Please note that the effectiveness of SBRA can be found and captured in Figure 5 center and right graph. Figure 5 reports the results for inverse $Q$-learning and harmonic learning under imperceptible perturbations intrinsic to the MDP, i.e. the state-of-the-art black-box adversarial attacks, and these results demonstrate that indeed harmonic learning, apart from being sample-efficient, is more robust. If we look at the results reported in the supplementary material and compute the area under curve for the SBRA results we see that the area under the curve for harmonic learning is 2.084564 and the area under the curve for the inverse $Q$-learning is 2.53216. The higher the area under the SBRA curve means higher non-robustness.

Thus this immediately demonstrates that indeed harmonic learning is more robust as also independently measured and analyzed by SBRA.

---

4. ”Following the previous question, the results from SBRA seem inconsistent with the other two robustness measures in Figure 5. For example, while the other two measures illustrate that harmonic learning is more robust in almost every case, in SBRA, there are certain scenarios in which inverse Q-learning is better.”

---

Please note the corresponding SBRA results for the center and right graphs of Figure 5 are reported in the supplementary material. Here in Figure 4 of the supplementary material, while we can see indeed harmonic learning is more stable and robust supporting the robustness results in Figure 5; furthermore, we can compute the area under the curve for Figure 4. The area under the curve for harmonic learning is 2.084564 and the area under the curve for the inverse $Q$-learning is 2.53216. Thus these results also quantitatively demonstrate that indeed harmonic learning is more robust.

---

5. ”The algorithm seems to fall under the category of inverse reinforcement learning, but the authors avoid this term in both the abstract and introduction. Is there a specific reason for this choice?”

---

This line of algorithms has both the elements of imitation learning and inverse reinforcement learning, and is referred to as both inverse reinforcement learning and imitation learning in the literature. We also explain this in line 114 and Line 115.

---

8. ”The networks used are not particularly big by 2024 standards. (I think).”

---

We used the identical network sizes with prior work to provide a consistent and fair comparison [1].

[1] IQ-Learn: Inverse soft-Q Learning for Imitation, NeurIPS 2021. [Spotlight Presentation]

---

9. ”Would it be possible to add a proof (or reference) for 231, “

---

Yes indeed the proof of 231 is currently presented in the paper in the proof of Proposition 3.3. right above Line 231.

---

10. ”253: is the assumption that the weighted gap between the value of the best and second best action is greater than epsilon reasonable? In many MDPs (especially discounted ones), many actions have the same value (think moving up or right on a grid to reach the top right corner).”

---

Essentially the exact same proof can be used to demonstrate that nearly optimal rewards will be obtained, in the case that there are actions with similar values. In particular, the assumed gap is used to prove that removing a random component from a stable basis will leave the top-ranked action completely unchanged. However, if there are several actions with nearly equal values, after which there is a gap of $\epsilon$ to the next $Q$-value, then the same argument shows that the policy will always choose one of these “nearly optimal” actions and thus still obtain nearly identical rewards.

---

11. “Should Osband, Ian, Benjamin Van Roy, and Zheng Wen. "Generalization and exploration via randomized value functions." be cited for RLSVI?”

---

Yes, of course we can add the citation.

---

12. ”447, what does DCT stand for?”

---

DCT stands for Discrete Cosine Transform.

Thank you for stating that our paper explores a novel and an interesting idea with clear writing and proofs.

---

1. ”DQN was used instead of rainbow”

---

In the empirical analysis for comparison with reinforcement learning DDQN is used as also has been cited and explained in Line 314. This is to provide a fair and consistent comparison with the prior work [1,2,3,4,5].

[1] IQ-Learn: Inverse soft-Q Learning for Imitation, NeurIPS 2021.

[2] Robust Deep Reinforcement Learning against Adversarial Perturbations on State Observations, NeurIPS 2020.

[3] Robust Deep Reinforcement Learning through Adversarial Loss, NeurIPS 2021.

[4] Detecting Adversarial Directions in Deep Reinforcement Learning to Make Robust Decisions, ICML 2023.

[5] Understanding and Diagnosing Deep Reinforcement Learning, ICML 2024.

---

2. ”Given that this paper claims to be much more sample efficient in practice, more effort (put into tuning) is necessary.”

---

We used the exact hyperparameters reported in the prior work which are tuned for the algorithm proposed in the prior work [1] to provide consistent and transparent comparison. Thus, we did not tune any of the hyperparameters for our algorithm. Hence, it is further possible to tune hyperparameters specifically for our algorithm and indeed obtain higher scores and more sample efficiency.

---

3. ”The setting of the experiment is a weird mix between on-policy and off-policy, where they sample trajectories at every epoch but from the expert policy. Usually, a dataset of expert trajectories is given.”

---

Please note that the setting is identical to prior work in which a fixed dataset of expert trajectories is given [1].

[1] IQ-Learn: Inverse soft-Q Learning for Imitation, NeurIPS 2021. [Spotlight Presentation]

---

4. ”A fairer benchmark would have also compared the result with the output of an algorithm like SQL or Munchausen or actual human data. This is also relevant for 4.2, the soft algorithm may have to overestimate Q to get the right policy. From personal experience, temperature is particularly important in games like pong.”

---

We used the exact same hyperparameter settings as the prior work [1]. Temperature is 0.01, not 0.1. Thus, the temperatures are identical.

[1] IQ-Learn: Inverse soft-Q Learning for Imitation, NeurIPS 2021. [Spotlight Presentation]

Please also find below the comparison against SQIL and human as well.

---

5. “The results of section 4.1, robustness to the exact perturbation model, are somehow, not meaningful. It's not surprising that the model trained to be robust to noise is robust to the exact kind of noise it was trained on.”

---

You might have a slight confusion here. This section reports results on robustness of standard reinforcement learning and standard inverse reinforcement learning. Thus, none of these policies are in fact trained to be robust to noise. Yet, we see a clear difference in their robustness.

---

6. ”This paper includes citations to Korkmaz 2022, 2023, 2024, and Korkmaz & Brown-Cohen 2023. Unfortunately, it misses critical citations to Korkmaz 2020, 2021a, 2021b. The introduction presents more adversarial definitions of robustness, which are not tested here (think FSGM or Korkmaz 2020). “

---

Please note that more recent work demonstrates that deep reinforcement learning policies can be attacked via the imperceptible natural adversarial attacks [1,2], and that these are currently the state-of-the-art perturbations, while they are computed in a black-box setting, and furthermore pierce through existing robust methods while causing substantial degradation on the policy performance.

[1] Adversarial Robust Deep Reinforcement Learning Requires Redefining Robustness, AAAI 2023.

[2] Understanding and Diagnosing Deep Reinforcement Learning. ICML 2024.