acceptodds
Under review as a conference paper at ICLR 2027

Directed Laplacian Representation Learning for Non-Reversible Markov Chains in RL

Abstract

This paper presents a method for Laplacian representation learning in directed Markov chains induced by a fixed reinforcement-learning policy, using the Chung Laplacian as the spectral target. Prior approaches estimate this target from discounted forward transitions, which is exact on reversible chains or at a single step. But a fixed policy generically induces a non-reversible chain, and learning the representation from its stationary transitions poses two challenges, as the energy and orthonormality constraints depend on the unknown stationary distribution, while the forward multi-step sampling can distort the desired representation. Learning in weighted coordinates removes the explicit dependence on the stationary distribution, while a discounting scheme based on the reversible component of the dynamics preserves the target eigenvectors. The method combines forward and time-reversed transitions to construct an unbiased estimator of this energy under stationary sampling. Coupling this estimator with an augmented Lagrangian objective yields local stability guarantees for spectral recovery under a simple-spectrum assumption. Experiments show that the method matches competing approaches in reversible environments and substantially outperforms them in recovering the eigenvectors of the Chung Laplacian in non-reversible settings.

Primary area:
reinforcement learning
Keywords:
RL, Laplacian Representation Learning, Spectral Recovery, Chung Laplacian

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_1R7HOpenReview ↗
Rating
2
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies a spectral-target mismatch in Laplacian representation learning for non-reversible Markov chains. Forward geometric-lag sampling discounts the transition kernel before reversibilization, whereas preserving the Chung eigenvectors requires reversing this order. DALLO independently selects forward or time-reversed transitions at each substep and retains ALLO's augmented-Lagrangian optimization. Under stationary sampling and exact conditional transitions, the resulting estimator targets the intended energy. Experiments on discrete grid mazes, directed cycles, and coupled cycles report improved eigenvector recovery, including comparisons with one-step ALLO.

Critical strengths
  1. A substantive diagnosis of sampling-induced target bias. The analysis separates population operator mismatch from optimization error and provides a principled sampler correction. The sufficient condition for eigenspace changes and the explicitly scoped local-stability result make the theoretical contribution more precise than a generic extension from undirected to directed graphs.

  2. Informative experimental controls. Target-alignment experiments, one-step controls, three readout conventions, buffer-distribution audits, and repeated-seed evaluations directly examine the proposed mechanism. On uniform Cycle-240, the practical recovery scores are 0.9979 for DALLO, 0.4243 for discounted ALLO, and 0.9587 for one-step ALLO (Table 1). Appendix K also provides useful matched-horizon comparisons, with DALLO retaining substantial advantages in many settings.

Critical weaknesses
  1. The empirical attribution remains incomplete, and the main text overstates the collection-horizon control. The primary comparison changes both the sampler and the reset horizon: 1,000 steps for DALLO versus 50 for ALLO. Contrary to Section 5's no-improvement statement, discounted ALLO on biased CycleNet-2 improves from 0.7856 to 0.9534 with longer trajectories (Table 27), exceeding DALLO's 0.6382 in the matched-horizon comparison (Table 21). Furthermore, independent buffers and method-specific density readouts change the empirical geometry. The grid-buffer audits show substantial departures from the stationarity assumed by the estimator, although DALLO's directed-buffer deviations are small. These issues do not invalidate the population theorem, but they limit attribution of the reported empirical differences to the sampler correction alone.

  2. The practical significance remains insufficiently established beyond spectral recovery. All evaluations concern finite discrete graphs; there is no value-approximation, planning, or control result establishing when the corrected representation is preferable for an RL task. Incoming-record resampling also relies on repeated discrete states, while continuous-state use requires an additional reverse-conditional estimator. Its error and computational cost are not evaluated. The manuscript therefore establishes a useful operator-learning result, but provides limited evidence that its sampler offers a practical advantage in the broader RL setting motivating the work.

Questions for authors
  1. Can DALLO and both ALLO controls be evaluated using a common transition corpus and matched collection horizons, with oracle and practical readouts? Please reconcile the biased CycleNet-2 result and revise the main-text summary. A matched comparison from existing buffers or logs that preserves the principal gains, together with a corrected account of the exceptions, would support reconsideration toward acceptance.

  2. Which operator and weighting measure does the finite-buffer implementation actually estimate when the buffer is nonstationary? Please document incoming-transition sampling, resets, and endpoint handling, and quantify the resulting operator discrepancy on an existing difficult configuration. Small discrepancies accompanied by preserved recovery gains would address the gap between the estimator guarantee and implementation.

  3. Which practical claims are intended beyond finite-state spectral recovery? Please distinguish established recovery benefits from prospective control benefits and state the reverse-sampling requirements explicitly. A precise, evidence-supported account of the method’s finite-state applicability would strengthen the case for acceptance.

4 comments

We appreciate the thoughtful feedback. We conducted the experiments you suggested and the results strengthen the case for the proposed approach.

We present the results for the shared buffer below. We will add these to the revised manuscript. For the downstream effectiveness of the proposed approach please see bullet 2. in the response to Reviewer z2jR or Appendix M in the revised paper.

Q1. Can DALLO and both ALLO controls be evaluated using a common transition corpus and matched collection horizons, with oracle and practical readouts? Please reconcile the biased CycleNet-2 result and revise the main-text summary. A matched comparison from existing buffers or logs that preserves the principal gains, together with a corrected account of the exceptions, would support reconsideration toward acceptance.

We trained ALLO on DALLO's own replay buffers over biased CycleNet-2 (same 10 seeds, the same 10610^6 transitions in 1000 trajectories of 1000 steps). It reaches 0.935 with the oracle and 0.933 with the practical readout, against DALLO's 0.637 and 0.638, so the gap is not caused by the data. With matched 1000-step collection horizons on all CycleNets (Appendix K, Tables 20 to 22), DALLO stays above both ALLO controls in 11 of the 12 settings, and biased CycleNet-2 is the only exception. This is a special case in which ALLO's sampling-induced target nearly coincides with the Chung eigenvectors (see the answer to Q3 of Reviewer tB56). We will revise the main-text summary and the account of this exception accordingly. Thank you for noticing this.

Q2. Which operator and weighting measure does the finite-buffer implementation actually estimate when the buffer is nonstationary? Please document incoming-transition sampling, resets, and endpoint handling, and quantify the resulting operator discrepancy on an existing difficult configuration. Small discrepancies accompanied by preserved recovery gains would address the gap between the estimator guarantee and implementation.

The implementation learns the operator that the buffer defines: I−12(P^π+Pπrev^)I-\frac12(\hat P_\pi+\hat{P_\pi^{rev}}) in L2(dbuf)L^2(d_{\mathrm{buf}}), where dbufd_{\mathrm{buf}} is the buffer's state distribution. We sample states uniformly from the buffer; at each substep, we choose a random occurrence of the current state and move forward or backward (the 0.1% of steps crossing an endpoint become self-transitions). This walk is reversible with stationary distribution dbufd_{\mathrm{buf}}. Thus, our unbiasedness and local stability results apply under the same assumptions, replacing dπd^\pi with dbufd_{\mathrm{buf}}. DALLO's stable equilibria are therefore the eigenvectors of this buffer operator.

When the buffer is stationary, this operator equals our target, as in the reset-chain view of Wu et al. (2019, Appendix B). In our directed settings, the buffer is nearly stationary (TV(dbuf,dπ)≤0.023\mathrm{TV}(d_{\mathrm{buf}},d^\pi)\le 0.023), and the operator matches the exact eigenvectors at 0.991 per vector on CycleNet-2 biased. In contrast, on GridRoom-64 biased (TV=0.70\mathrm{TV}=0.70), the buffer operator differs greatly from the target (0.24 even for a perfect learner), but DALLO recovers its subspace (overlap 0.98). Thus, the gap comes from the data, not the estimator. We will add this analysis to the appendix.

Q3. Which practical claims are intended beyond finite-state spectral recovery? Please distinguish established recovery benefits from prospective control benefits and state the reverse-sampling requirements explicitly. A precise, evidence-supported account of the method’s finite-state applicability would strengthen the case for acceptance.

Our main claim is finite-state spectral recovery. On non-reversible chains DALLO learns the eigenvectors of I−PaltI - P_{alt}, which give the Chung Laplacian eigenvectors after scaling by D1/2D^{1/2}. For control we now have evidence but no guarantee. In the new downstream experiment (See the bullet 2. in the response to Reviewer z2jR or Appendix M in the revised paper).

For the reverse sampling, the backward step itself only needs the predecessor of the current position in the stored trajectory. A jump to another occurrence of the same state is needed only when the walk changes direction, since going forward and then back on the same trajectory returns to the same state instead of giving a fresh sample. So the multi-step walk requires states that are revisited in the buffer, which holds in finite or discretized state spaces, and extending it to continuous states is future work.

If the reviewer would find it helpful in reconsidering their assessment, we would be happy to provide a preliminary revised manuscript incorporating the proposed changes, so that they can verify these changes before making their final recommendation.

After posting our response, we ran two more experiments to check that the difference in collected data does not explain our results.

1. Same data for both methods on CycleNet-4 biased. We trained ALLO with γ=0.9\gamma=0.9 and with γ=0\gamma=0 on DALLO’s own buffer. All methods used DALLO’s buffer (1,000 chains of 1,000 steps per seed) for 10 seeds, and the same readout, the per-vector cosine against the Chung eigenvectors at the final checkpoint. ALLO used its published hyperparameters, and for the one-step version we changed only the discount.

MethodMean cosine
DALLO0.757
One-step ALLO (γ=0\gamma=0)0.516
Discounted ALLO (γ=0.9\gamma=0.9)0.382

DALLO beats both on all 10 seeds (paired tt-test, p<0.001p<0.001 for each). With γ=0\gamma=0, moving ALLO from its own 1,000-step episodes to DALLO’s buffer takes it from 0.476 to 0.516 on the same 10 seeds (p=0.42p=0.42). In the CycleNet-2 shared-buffer run from our response, ALLO with γ=0.9\gamma=0.9 goes from 0.954 to 0.934 (p=0.26p=0.26). So training ALLO on DALLO’s buffer did not change its results in a significant way, and on CycleNet-4 DALLO keeps its advantage with the same data and the same one-step target, which supports the proposed sampler correction. Because of the rebuttal time we ran 10 seeds and not the 30 of the paper, so these means have more seed noise. We will add a full shared-buffer evaluation of DALLO and ALLO to the revised paper.

2. Same data in the downstream task. In Appendix M the two methods were trained on different data. Released ALLO used its own 50-step episodes and γ=0.9\gamma=0.9, while DALLO used its own buffer, and we did not run one-step ALLO there. The aim of Appendix M is to show the downstream utility of DALLO’s one-step representation (I−PaltI-P_{\mathrm{alt}}) relative to ALLO’s discounted representation (I−12(Pπγ+(Pπrev)γ)I-\frac12(P^\gamma_\pi+(P_\pi^{\mathrm{rev}})^\gamma)), and not to compare how well each method estimates the one-step operator. So Appendix M does not isolate the sampler correction. The CycleNet-4 experiment above and the directed problems (Table 1, Appendix K) do that. To check that the difference in data does not explain the downstream result, we trained ALLO with γ=0.9\gamma=0.9 on DALLO’s buffer of the river lake (10 seeds), so both methods use the same data, and ran the same DQN. With this data ALLO gets 27.0%, lower than the 55.4% it gets with its own 50-step episodes, and DALLO (88.0%) wins on all 10 seeds. So the different data in Appendix M did not give DALLO an advantage.

Thanks for running the extra comparisons and fixing the discussion of biased CycleNet-2. Appendix P answers my question on the finite-buffer operator and clarifies how trajectory endpoints are handled. I also found the biased CycleNet-4 result helpful: on the same transitions, RALLO outperforms both versions of ALLO (including the one-step baseline), which addresses my concern about the collection protocol on that graph.

What I'm still unsure about is how far this carries over to control. My concern with the extensive rewrite is that the revised version puts more weight on the goal-reaching experiment to motivate the one-step target and demonstrate practical value. The river layout experiment does show a clear gain over discounted ALLO on the same data, but I still can't tell how much the proposed sampler itself adds over one-step ALLO for goal reaching, since that comparison was only run for spectral recovery. On the wider set of graphs, the 11/12 CycleNet result only matches the collection horizon, so biased CycleNet-4 is still the only setting where all three methods are trained on the exact same transitions.

Overall, the revision strengthens the finite-state recovery result and gives a concrete downstream example, but the evidence for the sampler's practical advantage is still too limited for me to raise my score. I'll keep my rating at 2.

Thank you for reviewing the additional experiments and for acknowledging that Appendix P resolves your questions about the finite-buffer operator and trajectory endpoints. We also appreciate your recognition that the CycleNet-4 comparison addresses the collection-protocol concern on that graph, and that the river experiment demonstrates a downstream gain on identical data.

We agree that a downstream comparison with one-step ALLO would further clarify how much the sampler’s improvement in spectral recovery translates into control. We also recognize the additional value of extending the identical-buffer comparisons across the benchmark suite.

We would, however, respectfully ask that the remaining empirical questions be weighed alongside the contribution already established. The paper provides an analysis of how discounting and reversibilization interact, together with a sampling construction that preserves the reversibilized one-step eigenspaces under discounting and the associated recovery guarantees. The controlled CycleNet-4 experiment demonstrates improved recovery over both ALLO variants, including the one-step method sharing the same target, when all three methods use identical transitions. The river experiment then provides a concrete case in which the resulting representations improve downstream control over discounted ALLO on the same data.

The purpose of the downstream experiment is to give practical support for the choice of target in a setting where one-step bottlenecks matter. We believe that this example, together with the operator analysis and controlled recovery result, provides a theoretically and empirically justified basis for the paper’s present claims.

Given the concerns that you now consider resolved and the results you acknowledge, we would be grateful if you would reconsider the overall assessment. If the breadth of the downstream evidence remains decisive, we would appreciate clarification of how that limitation is weighed against the theoretical contribution and the controlled empirical findings. This would help us and the area chair understand the remaining basis for your assessment.

Thank you again for the time and care you have devoted to the paper.

Reviewer_tB56OpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper introduces DALLO, a method designed to correct the spectral bias introduced by forward multi-step sampling in non-reversible Markov chains.

Critical strengths

Technically solid work with a strong theoretical foundation, clear objectives, and identifiable methodological innovation.

Precisely identifies the mathematical inconsistency between multi-step discounting and reversibilization.

Principled solution based on forward and time-reversed sampling.

Strong experimental protocol, including 30 random seeds, statistical testing, multiple evaluation readouts, and matched-horizon controls.

Critical weaknesses

The contribution focuses on spectral recovery without demonstrating improvements in downstream RL tasks, such as value approximation, policy learning, or option discovery.

Reverse-transition sampling relies on exact state matching, limiting its applicability to continuous-state environments.

Unbiasedness requires stationary sampling, whereas the experimental buffers show substantial deviations from stationarity.

Some theoretical components build directly on established results. The principal novelty lies in the operator-bias analysis and the proposed sampler.

Theoretical guarantees are limited to local asymptotic stability under exact gradients, without finite-sample recovery guarantees.

Questions for authors

Does improved spectral recovery translate into measurable improvements in downstream RL performance? Including even a limited downstream evaluation would substantially strengthen the contribution.

How robust is DALLO to nonstationary replay buffers and evolving policies?

On CycleNet-2 biased, DALLO (0.644) underperforms ALLO1000 (0.954). Could the authors explain this exception?

Figure 5 compares eigenvalue errors against different reference spectra. Are these errors directly comparable without normalization?

1 comment

We thank the reviewer for recognizing the operator-bias analysis and forward/reverse sampler as the central contributions. Your questions help sharpen their practical implications.

Q1. Does improved spectral recovery translate into downstream RL gains?

See the bullet 2. in the response to Reviewer z2jR or Appendix M in the revised paper.

Q2. How robust is DALLO to nonstationary replay buffers and evolving policies?

Our analysis and experiments assume a fixed policy, so the induced chain and its stationary distribution do not change during learning. Extending DALLO to nonstationary buffers and evolving policies is an important direction that we leave for future work.

Q3. Why does DALLO underperform ALLO-1000 on CycleNet-2 biased?

This is an exceptional case where ALLO's target nearly matches the Chung eigenvectors (cosine 0.970 for the leading 11, versus 0.11--0.51 in other CycleNet settings). Since ALLO-1000 recovers its target well (0.984), it also scores highly against Chung.

DALLO's lower per-vector score is due to nearly degenerate Chung eigenvalue pairs (1,2), (3,4), (5,6), and (8,9), separated by only 3--5%. On each method's training-operator scale, these gaps are smaller for DALLO (1.5×10−51.5\times10^{-5} to 8.8×10−58.8\times10^{-5}) than ALLO (2.5×10−42.5\times10^{-4} to 1.1×10−21.1\times10^{-2}). Per-vector cosine penalizes rotations within these pairs, even when the subspace is recovered. Indeed, DALLO achieves 0.965 subspace overlap (versus 0.961 for ALLO-1000) and 0.958 when allowing rotations within these pairs. Increasing γ\gamma to 0.98 widens the gaps and raises DALLO's per-vector score to 0.854 (Appendix L).

We also ruled out data differences: training ALLO on DALLO's exact replay buffers (same 10 seeds, transitions, and 1,000-step resets) yields 0.935 versus DALLO's 0.637. We will discuss this exception and correct our claim that 1,000-step episodes do not improve ALLO.

Q4. Are the eigenvalue errors in Figure 5 comparable without normalization?

You are right that we did not normalize these errors. We provide here the scores with normalization as you suggest, and we will add them to the paper. We divide the error of each method by the mean size of its own target spectrum, ∑i=110∣λi^−λi∣/∑i=110λi\sum_{i=1}^{10}|\hat{\lambda_i}-\lambda_i|/\sum_{i=1}^{10}\lambda_i. The entries are DALLO / ALLO, mean over 30 seeds, lower is better. For the updated graph see Appendix N in the revised manuscript.

Environmentuniformnear-uniformbiased
Cycle-2400.037 / 0.4370.038 / 0.4390.038 / 0.449
Cycle-5000.028 / 0.4070.027 / 0.4080.024 / 0.415
Cycle-6000.020 / 0.4020.019 / 0.4040.019 / 0.416
Cycle-11000.011 / 0.3830.012 / 0.3840.010 / 0.391
Cycle-13000.014 / 0.3700.014 / 0.3700.011 / 0.370
CycleNet-21.891 / 0.4271.955 / 0.4271.825 / 0.478
CycleNet-30.401 / 0.4660.411 / 0.4650.416 / 0.477
CycleNet-40.577 / 0.4150.538 / 0.4130.505 / 0.506
CycleNet-100.245 / 0.3370.247 / 0.3350.191 / 0.427

After the normalization DALLO still has the lower error in 22 of the 27 settings (623 of 810 seeds). The results in the manuscript are updated.

Reviewer_z2jROpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies the implications of non-reversibility in Markov chains for an existing deep learning algorithm (ALLO) designed to learn Laplacian representations. Specifically, in a Markov chain with transition kernel PP and normalized 1-step-shifted successor representation matrix SRγ(P)=(1−γ)P(I−γP)−1\mathrm{SR}_{\gamma}(P)=(1-\gamma)P(I-\gamma P)^{-1}, the ALLO algorithm converges to the eigenvectors of the self-adjoint part of SRγ(P)\mathrm{SR}_{\gamma}(P) with respect to the inner product ⟨u,v⟩D=u⊤Dv\langle u,v\rangle_D=u^\top Dv, defined in R∣S∣\mathbb R^{\vert{}\mathcal{S}\vert{}}. Within this framework, this work elucidates how the discount factor γ\gamma interacts with DD when PP is not symmetric and DD corresponds to the stationary distribution of PP. In particular, it demonstrates that, given a non-uniform DD and γ>0\gamma>0, the successor representation and the self-adjoint operators do not commute. More formally, defining the self-adjoint operator as symD(X)=(X+X†D)/2\mathrm{sym}_D(X)=(X+X^{\dagger_D})/2, where X†DX^{\dagger_D} is the adjoint of XX with respect to DD, the derivation shows that symD(SRγ(P))≠SRγ(symD(P))\mathrm{sym}_D(\mathrm{SR}_{\gamma}(P)) \neq \mathrm{SR}_{\gamma}(\mathrm{sym}_D(P)), meaning the eigenvectors of these matrices will generally differ. Consequently, by symmetrizing long-term dynamics, ALLO loses its correspondence to the original eigenvectors of the 1-step symmetrized dynamics symD(P)\mathrm{sym}_D(P). To address this discrepancy, the paper proposes a modified objective alongside a Monte-Carlo mechanism for optimization in deep learning settings (DALLO). Finally, empirical results confirm that this approach successfully recovers the eigenvectors of SRγ(symD(P))\mathrm{SR}_{\gamma}(\mathrm{sym}_D(P)).

Note on notation: For clarity of exposition in this review, I omit the policy subscript π\pi (as the discussion applies to any fixed policy, and Markov chain more generally) and use explicit operator notation rather than the shorthand introduced in the paper. Specifically, SRγ(P)\mathrm{SR}_{\gamma}(P) corresponds to the paper's PγP^{\gamma}, and symD(P)\mathrm{sym}_D(P) corresponds to PaltP_{\mathrm{alt}}. In particular, the paper's 12(Pπγ+(Pπrev)γ)\frac{1}{2}(P_{\pi}^{\gamma}+(P_{\pi}^{\mathrm{rev}})^{\gamma}) and PaltγP_{\mathrm{alt}}^{\gamma} correspond to symD(SRγ(P))\mathrm{sym}_D(\mathrm{SR}_{\gamma}(P)) and SRγ(symD(P))\mathrm{SR}_{\gamma}(\mathrm{sym}_D(P)), respectively.

Critical strengths
  • Originality & Significance: This paper provides a valuable analysis of an operator that most Laplacian representation learning algorithms overlook or treat merely as a hyperparameter choice (SR⁡γ(P)\operatorname{SR}_{\gamma}(P)). In doing so, it sheds critical light on the theoretical implications of the sampling mechanisms used to approximate the underlying objectives in these algorithms.
  • Quality & Clarity: The manuscript thoroughly supports its theoretical claims with rigorous mathematical derivations, which clearly motivates how the the proposed objective and corresponding algorithm, DALLO, follows from the identified commutativity gap.
Critical weaknesses

While the paper provides a mathematically sound algorithm to learn a specific variant of the Laplacian representation, I identify three major, interconnected weaknesses regarding the exposition, motivation, and empirical evaluation of the method:

1. Misleading exposition and terminology regarding "Directed" Laplacians: The paper motivates the proposed objective and algorithm by introducing the Chung Laplacian, L=D1/2symD(L)D−1/2\mathcal{L}=D^{1/2}\mathrm{sym}_D(L)D^{-1/2}, where L=I−PL=I-P is the standard Laplacian matrix considered in RL. The text explains that this is a form of directed Laplacian defined for non-reversible transition kernels PP and symmetric by design, and argues that, because of these properties, it "reflects the geometry of the directed random walk" and, "compared with the symmetrized Laplacian (...) accounts for the stationary distribution of the chain." From this framing, the reader is led to infer that learning the eigenvectors of this alternative Laplacian is the appropriate remedy to the eigenvectors obtained by ALLO.

Next, the paper introduces the concept of Dirichlet energy to extend the original graph-drawing objective underlying ALLO to the case of the Chung Laplacian. It is shown that this energy expression contains factors of the form Dss\sqrt{D_{ss}} dividing the kk principal eigenvectors (gi)i=1k(g_i)_{i=1}^k of the Chung Laplacian (precisely because of the D−1/2D^{-1/2} postmultiplying symD(L)\mathrm{sym}_D(L)). The authors reason that these factors are undesirable not only because they must be approximated or learned, but also because they can produce poorly behaved optimization dynamics. Consequently, to remove these factors from the energy, they propose learning the transformed eigenvectors fi=D1/2gif_i=D^{1/2}g_i instead.

The issue with this exposition is twofold:

  1. The original Laplacian is already well-defined for the non-reversible case.
  2. The Appendix of the paper introducing ALLO already shows that, in the general setting, the algorithm converges precisely to the eigenvectors of the symmetrized Laplacian symD(L)\mathrm{sym}_D(L), which are precisely the transformed eigenvectors (fi)i=1k(f_i)_{i=1}^k.

Hence, the Chung Laplacian symmetrizes the dynamics to the exact same extent as the original learning dynamics, suffering from the very limitation the paper aims to address. While introducing the Chung Laplacian might offer minor notational intuition for why ALLO converges to a symmetrized solution, it yields no practical advantage, as the proposed D1/2D^{1/2} transformation simply reverts the target back to the exact eigenvectors already learned under the original framework. Worse yet, framing the objective through the Chung Laplacian artificially introduces the need to learn or approximate a state-density model D^\hat{D}—which, as the paper itself acknowledges, is a difficult task in general settings. Finally, because the resulting method relies on the exact same symmetrization operator symD\mathrm{sym}_D, naming the objective and algorithm 'Directed ALLO' (DALLO), and emphasizing this in the paper's title, is misleading. It implies that the method preserves the directed, asymmetric structure of the Markov chain in a way that prior work does not, when in reality it merely applies the exact same symmetrization to the 1-step transition kernel PP rather than the multi-step successor representation.

2. Unmotivated preference for the target operator: Stripping away the framing around the Chung Laplacian, the core difference between ALLO and DALLO reduces to the order in which symmetrization and the successor representation are applied. The paper’s underlying assumption is that using the principal eigenvectors of the matrix symD(SRγ(P))\mathrm{sym}_D(\mathrm{SR}_{\gamma}(P)) as a Laplacian representation is inadequate. It is stated that the sampling mechanism paired with ALLO, which results in learning precisely those eigenvectors, "can distort the desired representation" and that the matrix itself is the "wrong operator." Despite the mathematical thoroughness applied in proving that symD(SRγ(P))≠SRγ(symD(P))\mathrm{sym}_D(\mathrm{SR}_{\gamma}(P)) \neq \mathrm{SR}_{\gamma}(\mathrm{sym}_D(P)), the paper never explains or motivates the reason to prefer one object over the other.

In particular, while the paper is motivated as an analysis of non-reversible transition kernels PP, it focuses on an operator that symmetrizes the dynamics without explaining why the order of symmetrization and long-term propagation (through the SR) matters. This is not a trivial question; I would argue that the standard applications of the Laplacian representation, which include long-term planning, credit assignment, and exploration, better motivate a representation that captures the spectral structure of the long-term SRγ(P)\mathrm{SR}_{\gamma}(P) matrix rather than that of the 1-step PP. Because SRγ(symD(P))\mathrm{SR}_{\gamma}(\mathrm{sym}_D(P)) preserves the spectral structure of the 1-step symD(P)\mathrm{sym}_D(P), it is not clear why it would be a more desirable object of interest than symD(SRγ(P))\mathrm{sym}_D(\mathrm{SR}_{\gamma}(P)).

3. Tautological empirical evaluation: This lack of motivation for the target operator carries over into the experimental evaluation. The empirical section primarily evaluates DALLO against ALLO by measuring how closely each algorithm recovers the eigenvectors of SRγ(symD(P))\mathrm{SR}_{\gamma}(\mathrm{sym}_D(P)). However, this comparison is tautological. Because ALLO is mathematically designed to converge to the eigenvectors of symD(SRγ(P))\mathrm{sym}_D(\mathrm{SR}_{\gamma}(P)), and the manuscript has already proven that symD(SRγ(P))≠SRγ(symD(P))\mathrm{sym}_D(\mathrm{SR}_{\gamma}(P)) \neq \mathrm{SR}_{\gamma}(\mathrm{sym}_D(P)) for non-reversible chains with non-uniform stationary distribution DD, ALLO is guaranteed by definition to fail at recovering the eigenvectors of SRγ(symD(P))\mathrm{SR}_{\gamma}(\mathrm{sym}_D(P)). Showing that DALLO outperforms ALLO on this metric only demonstrates that DALLO successfully optimizes its own proposed objective; it does not provide empirical evidence that the resulting representation is superior or more useful for downstream reinforcement learning tasks. To validate claims that ALLO learns the "wrong operator," the evaluation would need to compare both representations on downstream tasks where the distinction between 1-step and multi-step symmetrization actually matters.

Questions for authors

Suggestions

In order of relevance:

  • The Experiments section does not explicitly state the evaluation objective or the metrics used. While they can be inferred from the text, it remains unclear what qualitative descriptions like "significantly better" and "significantly outperforms" actually mean quantitatively.
  • Comparing ALLO with γ=0\gamma=0 against DALLO with γ=0.9\gamma=0.9 without making this distinction explicit is potentially misleading, as it suggests ALLO is inherently worse than DALLO. However, when γ=0\gamma=0 (and γ=0.9\gamma=0.9, respectively), they share the same underlying 1-step target structure, and it is well known that γ\gamma heavily affects how well eigenvectors can be recovered in practice.
  • I find the notation more complex than necessary and believe it could be streamlined for ease of exposition and comprehension. In particular:
    • I find it unnecessary and possibly confusing the mix of the graph-based and the general inner-product definitions of the Dirichlet energy.
    • The inclusion of a policy π\pi is unnecessary.
    • Sometimes PP is denoted with the letter QQ.
    • PrevP^{\mathrm{rev}} is introduced, when a standard notation for adjoint as P†P^{\dagger} or P∗P^{*} already exists in the literature.
    • The relevant matrices are identified with some text symbols like rev\mathrm{rev} and alt\mathrm{alt}. Sometimes they are superscripts and sometimes they are subscripts, without any explanation.
    • Unexpectedly, the Laplacian corresponding to PaltγP_{\mathrm{alt}}^{\gamma} is not LaltγL_{\mathrm{alt}}^{\gamma}, but L~alt\tilde{L}_{\mathrm{alt}}. This is the only place I could identify where the tilde is used and the choice is not explained.
    • Lowercase letters are used both as regular elements of a set (the state space) and as random variables mapping to those sets (namely, ss for both purposes, instead of ss and SS, as is standard in the field).
    • While the notation P(s,s’)P(s,s’) makes sense to define the probability density or mass assigned to the event {S’=s’}\{S’=s’\} conditioned on ss, P(s’∣s)P(s’|s) would facilitate things, making straightforward the Equation 7 and the equation right before Proposition 5, for example. In the case of Equation 7, in particular, the role of ss and s’s’ seems to be shifted.
    • Calligraphic capital leters are indistinctively used to denote matrices, objectives, and sets.
    • Introducing the combinatorial form of the Chung-Laplacian W\mathcal{W} does not seem particularly enlightening while introducing a new symbol to a long list of symbols.
    • The inner product ⟨⋅,⋅⟩Dπ\langle\cdot,\cdot\rangle_{D_{\pi}} is introduced before DπD_{\pi}.

Questions

  • Can the authors provide a downstream RL task or theoretical justification for why preserving the spectrum of 1-step symmetrized dynamics is preferable to multi-step symmetrization?
4 comments

We thank the reviewer for the careful and detailed review. We agree with several points, and we believe the review will make the paper stronger. We will make all the notation changes in the list, state the evaluation metric in the main text (see 3), and state clearly that on the directed chains the main comparison is DALLO with γ=0.9\gamma=0.9 against ALLO with γ=0\gamma=0, and why. We also agree that recovering a chosen eigenspace alone does not show downstream usefulness, so we added a downstream RL task to the paper (see 2). Finally, we will change the title to Laplacian Representation Learning for Non-Reversible Markov Chains in RL and rename the method RALLO (see 1(c)). Below we keep the name DALLO, as in the submitted paper.

Two facts behind most of the review

Geometry. Wu, Tucker and Nachum (2019, GDO) define the objective in L2(d)L^2(d), where dd is the stationary distribution. The main texts of Wang, Zhou, Zhang, Shao, Hooi and Feng (2021, GGDO) and of Gomez, Bowling and Machado (2024, ALLO) write it with the Euclidean inner product, but the training samples the states from the data, so in practice it works in L2(d)L^2(d). Giorgi, Olivieri, Jiang, Toni and Papini (2026) point this out for ALLO, and they also note that the appendix of Gomez et al. (2024) has a correct weighted form. So we agree with the reviewer that with one-step sampling ALLO targets symD(L)\mathrm{sym_D}(L).

Discount. Gomez et al. (2024, page 3) define the Laplacian as L=I−f(Pπ)L=I-f(P_\pi). If PπP_\pi is symmetric, LL is "typically defined as either" I−PπI-P_\pi or I−(1−λ)ΦπλI-(1-\lambda)\Phi^\lambda_\pi with Φπλ=(I−λPπ)−1\Phi^\lambda_\pi=(I-\lambda P_\pi)^{-1}, the successor representation, so their λ\lambda plays the role of our γ\gamma. If PπP_\pi is not symmetric, L=I−12(Pπ+Pπ⊤)L=I-\tfrac12(P_\pi+P_\pi^\top), the one-step form (Appendix A.5 gives its weighted version, citing Eq. 4 of Wu et al., 2019). A non-reversible chain is never symmetric, since a symmetric PπP_\pi is reversible with respect to the uniform distribution.

So on the chains of our paper, their text prescribes the one-step operator, which is the symD(L)\mathrm{sym_D} (L) of the reviewer. Whenever γ>0\gamma > 0 and the chain is non-reversible, ALLO sampler targets I−symD(SRγ(P))I-\mathrm{sym_D} (\mathrm{SR_\gamma}(P)) and not the one-step operator that their text prescribes for a non-symmetric PπP_\pi.

This is a different operator (Proposition 3), and it can have a different leading eigenspace (Proposition 4). This is what our paper is partially about.

1. Exposition and terminology

(a) The density model. We agree that fi=D−1/2gif_i=D^{-1/2}g_i are the eigenvectors of symD(L)\mathrm{sym}_D(L), and this is exactly what the DALLO network outputs. Nothing has to be estimated for this, and one can use ff directly. The density estimate is needed only to get the Chung eigenvectors g=D1/2fg=D^{1/2}f, which weight each state by its stationary frequency. In some tasks this matters. In the downstream task (see 2), in the two-rooms lake with a fixed start on the current at (17,0)(17,0) and the goal at (21,8)(21,8), the Chung vectors reach the goal in 83% of the test episodes, against 23% with ff and 0% with ALLO (10 seeds).

(b) Why not simply ALLO with γ=0\gamma=0? With γ=0\gamma=0 ALLO loses the benefit of the discount, the small eigenvalues are close to each other and the recovery is harder. DALLO keeps the one-step target and uses the discount only to widen the gaps between the eigenvalues, so it gets both. For example on Cycle-240 with the uniform policy, DALLO reaches 0.998, ALLO with γ=0\gamma=0 0.959 and ALLO with γ=0.9\gamma=0.9 0.424 (Table 1). DALLO is better than one-step ALLO in all 15 directed-cycle settings and in all 12 CycleNet settings.

(c) The name. DALLO does not keep the antisymmetric part of PP, and we agree that "directed" in the title can be read this way. We meant the setting, non-reversible chains, and not the representation. So we will change the title as written above, and rename the method RALLO, where R stands for "reversibilized", since it reversibilizes the chain before discounting.

2. Motivation for the target operator

We agree that the choice of the spectral target deserves a clearer motivation, and we will revise "wrong operator" and "distort" to say that ALLO's discounted sampler targets a different operator than our one-step target. Our aim is to recover the Laplacian eigenspaces of the one-step kernel PP, and to use the discount only to make them easier to learn. DALLO keeps these eigenspaces for every γ\gamma, while on non-reversible chains the eigenspaces that ALLO learns with geometric-lag sampling change with γ\gamma.

Chung's Cheeger inequality holds for every irreducible transition matrix QQ with stationary distribution dd, 12h(Q)2≤λ2(I−symD(Q))≤2h(Q)\tfrac12 h(Q)^2 \le \lambda_2\big(I-\mathrm{sym_D}(Q)\big) \le 2h(Q), where the conductance h(Q)h(Q) is the smallest ratio, over sets of states, between the stationary flow that leaves the set in one step of QQ and the stationary mass of the smaller side (Chung, 2005, Theorem 5.1). DALLO recovers I−symD(P)I-\mathrm{sym_D}(P), so its spectrum reflects the bottlenecks of the one-step chain PP. ALLO's target is I−symD(SRγ(P))I-\mathrm{sym_D}(\mathrm{SR_\gamma}(P)), and SRγ(P)\mathrm{SR_\gamma}(P) is also a transition matrix with the same dd, so by the same inequality ALLO's spectrum reflects the bottlenecks of the multi-step chain SRγ(P)\mathrm{SR_\gamma}(P). These are not the same bottlenecks, since (1−γ) h(P)≤h(SRγ(P))≤h(P)/(1−γ)(1-\gamma)\,h(P)\le h(\mathrm{SR_\gamma}(P))\le h(P)/(1-\gamma), so at γ=0.9\gamma=0.9 a narrow door can look up to ten times wider (or a region up to ten times more closed) to the multi-step chain. Neither is better for every task. But when the agent has to find a narrow passage, the one-step bottlenecks are the relevant ones.

To test this, we added a downstream RL task to the appendix (Appendix M, Table 30). A DQN agent has to reach a goal inside a walled box with two rooms in a gridworld lake, starting from a current around the lake, so it has to leave the current and pass through narrow doors. The reward is shaped with each learned representation as in Wu et al. (2019). In the three layouts with the box, shaping with DALLO's ff reaches 53.4%, 90.6% and 88.0% final success, against 0.0%, 65.6% and 55.4% with ALLO (10 seeds, DALLO ahead in 28 of the 30 seeds and the other 2 tied). In an open lake without a box the straight-line distance is already enough, and DALLO matches it.

3. Evaluation

We do not think the evaluation is tautological. On the directed chains the main comparison is DALLO against ALLO with γ=0\gamma=0, which targets the same operator symD(L)\mathrm{sym_D}(L), as the reviewer notes. So both methods are scored against a target that both of them aim for, and the difference comes from how well each method learns it. We added γ=0.9\gamma=0.9 only to emphasize that it's not recovering Chung eigenvectors.

If the reviewer would find it helpful in reconsidering their assessment, we would be happy to provide a preliminary revised manuscript incorporating the proposed changes, so that they can verify these changes before making their final recommendation.

Let me start by thanking the authors for their response; I think this discussion moves the paper one step closer to being ready for publication. The response acknowledges, for example, that the word “directed” is a misnomer, as the proposed method learns the eigenvectors of sym⁡D(L)\operatorname{sym}_D(L), the same one-step target that ALLO already learns with γ=0\gamma=0. In that context, I agree that the focus (and the name) of the method needs to change. It seems to me the paper's narrative is moving away from the Chung Laplacian per se and is now arguing that the issue is that the discounted sampling by Gomez et al. (2024) departs from the one-step operator for non-symmetric kernels, as well as the idea of using the discount for spectral conditioning.

However, I’m not comfortable raising my score. First, as far as I can tell, I do not have access to a complete new version of the paper. For some reason, reviewers can’t see the original version of the paper to compare with the new one, but looking at the current version, seeing the title, the method name, the abstract, Section 3, Proposition 1, the language around "wrong operator"/"distort", the notation, and the conclusion still listing downstream evaluation as future work suggests to me that changes haven’t been carried out, and I simply can’t assess the paper without them. I recognize that this reply comes close to the end of the discussion period, but I don’t think it matters because, even more importantly, I believe there is a limit to how much a paper should change within a single review cycle. Taken together, the proposed revisions include a major repositioning of the paper, and at this point it is a substantially different paper. Right now, the title, the method name, and the motivation should change; and the contribution should be reframed from a directed Laplacian objective to an objective that preserves the reversibilized one-step target under discounting. It also seems to me that, in this context, some empirical results would need to move from the Appendix to the main text. It is simply too much. I am excited about the prospects of this research, but I think a paper with this framing and these claims should be evaluated in a new round of reviews rather than be accepted based on what it can potentially be in the camera-ready version.

Thank you for your careful reading and for explaining why you felt unable to reassess the paper on the basis of our response alone. We appreciate your concern about the scope of the revisions within a single review cycle. We have now posted the complete revised manuscript with the changes we promised marked in blue.

Your comments helped us see where our presentation obscured the relationship between ALLO and RALLO. The revision explicitly credits one-step ALLO with learning the eigenspaces of the reversibilized one-step chain. It then states what RALLO contributes: by reversibilizing before discounting, it preserves those eigenspaces while using the discount for spectral conditioning. We revised the title, method name, abstract, and notation accordingly. Section 3 and Proposition 1 now make the distinction between Euclidean and stationary-weighted symmetrization explicit.

The main text now also reports the downstream goal-reaching experiment you asked about. In all three layouts with narrow passages, reward shaping with RALLO features gave higher final success rates than shaping with discounted ALLO features. This gives a concrete example of when preserving the one-step structure can help. We believe the present framing reflects both what the analysis establishes and what the experiments support.

We are grateful for the care you have given the paper. If time permits, we would greatly appreciate your taking a look at the posted revision and reconsidering your assessment in light of the manuscript now available.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.