Proper Laplacian Representation Learning

We thank the reviewer for pointing out how in its initial version the manuscript seemed to suggest that our derivations only applied to the tabular setting where the state space is finite. On the contrary, both theory and experiments apply to the abstract setting, meaning that the state space is a measure space that is potentially uncountable. This is more general than the case in which the state space is a continuous Euclidean space, and therefore applies to it. To make this unambiguous, we included a whole new subsection in the Appendix (Appendix A.5) that details how the theory developed in Section 4 applies to the abstract setting.

We also included a final paragraph in Section 2 that makes this explicit and that connects the abstract/continuous setting with the use of neural network approximators. Something to note here is that the action space we consider is still discrete, as in all the previous Laplacian literature. However, we do not see any relationship between this assumption and our objective since, once the policy is fixed, what matters is the resulting Laplacian, whose dimensionality depends on the state space and not the action space.

Now we would like to address the points raised as weaknesses in the review:

Weakness 1: The primary limitation is my view is the lack of justification in the practical context. Experiments are only provided in very simple maze scenarios, and it is not demonstrated here (or in primary related work I saw) why, in practice, one would chose a Laplacian representation over a standard representation.

Answer: The Laplacian representation is useful for specific applications such as the ones we mentioned in Section 1 (e.g., exploration, reward shaping, and preserving information relevant for value estimation) and it is not meant as a state representation suitable for solving any possible application. In this sense, the utility of the Laplacian representation has been established by previous literature (e.g., refer to Klissarov and Machado, 2023) and we do not consider necessary a further comparison with other types of representations. All this being said, we consider that we could have been more clear about the motivation of the Laplacian representation and for this reason we updated the third paragraph in Section 1.

Moreover, the reason we limited the experiments to gridworlds is that the tabular setting is the only setting for which one can calculate exactly the eigenvectors of the Laplacian. Since we want to evaluate the correctness and generality of the proposed objective to learn the Laplacian representation, and not to motivate this representation, we concluded that the appropriate environment hyperparameters to vary were sizes and topologies. In particular, note that the number of states ranges from 11 (GridMaze-7) to 1088 (GridRoom-64), and the environments present both totally disconnected regions (e.g., GridMaze-32), highly connected regions (e.g., GridRoom-1), and symmetries (compare GridRoom-4 and GridRoomSym-4). Also note that the largest environments are larger than any of the tabular environments considered in the literature we reviewed (specifically, see Wu, 2019; Wang, 2021; Wang, 2023).

All that being said, your invitation to consider additional experiments made us reconsider an additional environment hyperparameter that was explored by previous works. Specifically, our initial submission only considered as a representation of the state the (x, y) location of the agent in the grid. Now we include in the Appendix similar results for the pixel-based representation of the state, where each tile in the grid corresponds to a pixel (see Figure 10 and Table 2). In particular, our results continue to be promising and they continue to outperform the existing solutions, further strengthening the claims in our paper.

Weakness 2: On a similar note, there lacks more thorough discussion on the stability of the now-induced minimax game. This likewise seems like something necessary in order to demonstrate practical utility of this framework, at least theoretically.

Answer: We are unsure about what additional discussion regarding the stability of the induced minimax game is appropriate. We are open to any suggestion that you consider relevant. So far, we proved with Theorem 1, and the new extension to the abstract setting in the Appendix, that the Laplacian representation is the unique stable equilibrium point of the induced minimax game, meaning that we have theoretical guarantees (under no function approximation and Monte Carlo estimation of gradients) that the minimax game is stable. In addition, now you can observe in Appendix D how the only permutation that is stable is the one corresponding to the Laplacian representation.

Please check the author's comment and if your review submitted is the correct one.

This review is clearly for a different paper. Maybe there was an error in uploading the correct review?

We thank the reviewer for pointing out the absence of any comment regarding the complexity of our proposed objective. Interpreting complexity as the computational and memory complexity of an algorithm that optimizes this objective, there is an addition of ~$d^2$ parameters that have to be stored and updated. Typically, $d^2$ will be orders of magnitude smaller than the number of parameters and hyperparameters in standard neural networks (e.g., in our experiments $d^2=121$, while the number of parameters is larger than $100,000$), and so the overhead of the proposed objective is negligible. We now address this point at the end of the third paragraph in Section 3.

Regarding the lack of clarity in Sections 1 and 2, we are happy to further clarify any question or confusion and make the corresponding modifications in the manuscript. However, we need to know exactly what is not clear. That being said, we edited the third paragraph in Section 1 to make more precise the properties of the Laplacian representation that make it a suitable state representation.

We find valuable the questions posed by the reviewer. In particular, they let us understand what was unclear, what required more theoretical details, or what could be further clarified with additional plots. That being said, we would like to emphasize that the paper is theoretical in nature. Correspondingly, we think the proof of Lemma 2 and the proof sketch of Theorem 1 should be kept as is in the main text, as opposed to moving them to the Appendix.

Now, we will provide explicit answers to the questions in the review:

Question 1: While in the paper the approach focuses on the eigenvectors of the graph Laplacian, in the experiments it is used for finding eigenfunctions. I think that further information should be provided for the actual formulation/solution of this problem.

Answer: The term eigenfunction is equivalent to the term eigenvector of the graph Laplacian in the abstract setting, i.e., when the state space is not necessarily a finite set. In this sense, our proposed objective can be used to approximate the eigenfunctions of the Laplacian, or what we refer to as the Laplacian representation. We added a new last paragraph in the Background section that we hope clarifies this point. In addition, we extended our original proofs to the abstract setting in the Appendix.

Question 2: I find Corollary 1 and the paragraph above a bit unclear. Why does an optimum of (2) and (4) imply that the constraint must be violated?

Answer: Consider Equation 7, it states that the gradient consists of 3 terms: a Laplacian product $Lu_i$, a sum of dual terms, and a sum of barrier terms. The proof of Lemma 2 relies on the fact that the dual sum goes from the index $j=1$ to $j=i$, and that the barrier loss sum is 0 in the equilibrium points. In cases where the dual variables are not used, that is, when $\beta_{ij}=0$, and stop-gradient operators are not used (i.e., in both GDO and GGDO), the barrier sum cannot be 0 since it needs to cancel the product term $Lu_i$. Hence, if we assume that $u_i$ is an eigenvector of $L$, we have that $u_i$ must lie in the span of the first d eigenvectors $u_1,\cdots,u_d$. Thus, we can conclude that the inner product between $u_i$ and some other eigenvector $u_j$ must be different from the Kronecker delta, as stated in the Corollary 1. Now you can find a proof in Appendix A.3.

Question 3: Perhaps, an experiment to test the stability of the equilibrium with respect to permutations.

Answer: We added Figure 8 in Appendix D that shows how after permuting the coordinates of the Laplacian representation, optimizing ALLO results in recovering the correct ordering. This shows that no permutation is stable besides the desired one.

Question 4: Why rotated eigenvectors do not provide a good representation?

Answer: There are two particular reasons that motivate learning the eigenvectors exactly and not its rotations. First, consider their use as intrinsic rewards to induce option discovery. In this case, the idea is to find a policy that maximizes the cumulative reward determined by each eigenvector, with the characteristic that, once a local maxima is reached, the agent stops using the option. This means that the number of local maxima in the eigenvectors (and minima, since the negative of each eigenvector is also an eigenvector) affects the number of sink states where the options are stopped. When the eigenvectors are rotated, the number of local maxima increases, in general, and so does the number of sink states. The result is that the trajectories traversed by the agent are shorter and so, effectively, the less exploratory that the agent behaves (for a similar intuition, see Jinnai, 2019). In the same vein, rotations correspond to combinations of eigenvectors, which results in different temporal scales being combined. The eigenvalues can be used to normalize these scales for reward shaping, but once there are multiple scales, no normalization is possible. Thus, rotations are not as effective for this use case. To provide some evidence of this phenomena and make things more intuitive, we now include Figure 7 in Appendix C. Moreover, to make it more explicit, now we also briefly mention the problem with using rotations in the fifth paragraph of Section 1.