acceptodds
Under review as a conference paper at ICLR 2027

Snapshot Entropy Exploration in Reinforcement Learning

Abstract

Maximum state-entropy exploration seeks broad state visitation, but the standard visitation distribution pools variation across both time and independent executions. Consequently, the same pooled coverage can arise either from a reproducible, time-structured route or from dispersion across runs. We make this distinction explicit by sampling a time according to the visitation weights, independently of a run, and letting denote the agent's state at that time. Then is the pooled state entropy, while the chain rule separates it into two components. We call the snapshot entropy: it measures the uncertainty across executions that remains once elapsed time is known. We study exploration with certainty, which maximizes pooled state entropy subject to a snapshot-entropy budget. This budget limits time-aligned disagreement across runs and guarantees that expected within-run visitation entropy is at least the pooled state entropy minus the budget. We derive an exact policy-gradient identity for this objective and obtain Certainty Policy Gradient (Certainty PG), a model-free method that estimates time-indexed state distributions from synchronized rollouts. We characterize the structure and limits of exploration with certainty. Deterministic policies suffice to minimize snapshot entropy; selecting a high-coverage certain route is NP-hard; and stochastic transitions impose an unavoidable uncertainty floor computable by dynamic programming. On Ant, a continuous-control benchmark used in prior maximum-entropy exploration work, synchronized rollouts expose same-time dispersion hidden by pooled occupancy: Certainty PG reduces this dispersion, though at a cost in coverage. On clean Rooms-8, where broad reproducible routes exist, Certainty PG retains 98.0% of Pooled PG's pooled entropy while increasing single-run all-state coverage from 31.5% to 99.8%. A trajectory-entropy objective achieves similarly high coverage but substantially greater time-aligned uncertainty, demonstrating that single-run coverage and repeatability are distinct objectives. On noisy Rooms-8, it approaches the uncertainty floor, while navigation stress tests show that excessive concentration can produce incomplete routes.

Primary area:
reinforcement learning
Keywords:
Reinforcement Learning, State Entropy, Entropy Exploration, Snapshot Entropy

Reviews

Among:
Shape:
1234this paper, Bottom 25%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.75 over 4 reviews, above 25% of the others.
Reviewer_bGL9OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This work considers reward-free exploration and highlights a limitation of maximum state-entropy exploration where an agent can achieve high state coverage without reliably visiting diverse states within each trajectory. This is because policies may also achieve good coverage due to variation across different trajectories. They introduce the snapshot entropy which measures uncertainty in the agent's state over different trajectories for the same timestep. Building on this, they propose an algorithm that optimizes for broad pooled state entropy with a constraint on the snapshot entropy to encourage broad coverage and repeatable exploration. They theoretically analyze the method and derive a lower bound on the visitation entropy within a trajectory based on pooled and snapshot entropy. The experiments show that their method can improve performance for single trajectory coverage on tabular environments and also evaluate on the Ant.

Critical strengths
  • This is an interesting exploration objective and distinguishing between coverage across time vs uncertainty over trajectories seems new to me. The information theory formulation makes sense and the theoretical connection between snapshot entropy an coverage within a trajectory gives a mathematical justification for the method.
  • The paper offers a thorough theoretical and experimental analysis with meaningful results on the optimization landscape and feasibility with stochastic dynamics. The experiments also investigate failure cases which gives valuable insights into the method's limitations.
Critical weaknesses
  • It is unclear to me what the practical benefit of the method is, for instance why making trajectories more repeatable is beneficial beyond just maximizing the within-trajectory coverage and it is not demonstrated that the repeatability improves downstream learning. In fact, the trajectory entropy baseline appears to give similarly high coverage in a single trajectory on the Rooms-8 task and better coverage on the harder navigation tasks.
  • While the paper provides a thorough analysis, the main contributions are somewhat obscured by the large number of theoretical results, technical details, and investigations. The presentation does not always prioritise the results most relevant to understanding the practical value of the method. Also the positioning within the literature is currently surface level and should be further extended.
Questions for authors
  • When is repeatability useful apart from giving within-trajectory coverage? Could this be demonstrated experimentally?
  • How can the method avoid concentrating on incomplete routes while still satisfying the uncertainty constraint?
  • Could this approach reliably estimate and enforce snapshot entropy in high-dimensional environments, in light of the constraint violations on Ant?
2 comments
AuthorsOpenReview ↗

Practical Benefits, Incomplete Routes, and Estimation Limits

Thank you. We will foreground the practical question, simplify the theoretical presentation, and distinguish what the new experiments resolve from what remains open.

Q1/W1: when is repeatability useful beyond coverage? When a downstream decision depends on where the explorer will be at a given time. We test scheduled rendezvous, access-window selection, and repeat-survey change detection.

The strongest control preserves coverage exactly. Independently permuting exchangeable room labels each episode preserves the Rooms-8 policy's within-run entropy J = 2.401 and all-state coverage = 99.75%, while substantially changing downstream performance:

MetricOriginal policyPermuted-room control
U (bits)0.0101.451
Rendezvous success0.9990.577
Safest 2-step access-window risk0.0000.125
Change-detection power75.7%11.1%

The detection test uses a nominal 5% false-positive rate. These controlled evaluations demonstrate that identical within-run coverage can support different downstream utility when timing matters. The access-window result concerns this controlled task, rather than deployment-level safety.

The benefit also holds against learned J-PG policies. On the noisy cycle, Certainty PG/J-PG achieve 99.9%/100% coverage, but rendezvous is 0.943/0.802 and detection power is 70.1%/35.8%. A partner observing just one prior run achieves rendezvous success 0.894/0.688. Thus the advantage extends to prediction from limited observations.

For coverage-only downstream learning, we agree that repeatability need not help. On open-grid goal reaching, coverage-first certainty/J-PG score 70.8%/95.8% with the original planner and 100%/100% with a planner that does not trust unobserved actions. We will state that distinction explicitly.

Q2: avoiding incomplete routes. Prop. 7 shows that λ > 1 makes every deterministic route a strict local maximum in state-law space; it does not show that lock-in requires λ > 1. With deterministic transitions and a fixed initial state, our new result establishes, for λ ≥ 1,

max⁡π(C−λU)=max⁡πJ=max⁡routesC.\max_{\pi}(C-\lambda U)=\max_{\pi}J=\max_{\text{routes}}C.

Thus λ > 1 is unnecessary to attain the optimal-route value, although changing λ alone does not guarantee successful training.

We tested coverage-first certainty: optimize J for 300 updates, then J − λU. The default was selected on calibration seeds 0–9; results below use held-out seeds 100–109.

TaskOriginal certaintyCoverage-firstJ-PG
Ring: all-state coverage0%99.99%99.98%
Open grid: all-state coverage0%99.67%98.71%
73-state grid: distinct states24.863.771.5

Coverage-first meets the budget on all 10 seeds for each task. Its U is 0.007/0.016/0.021, versus J-PG's 0.196/0.521/1.532. Starting J − λU without the coverage phase still locks in early. These results support discovering coverage before enforcing certainty, while the 73-state grid retains a coverage–certainty trade-off.

Q3: high-dimensional estimation and enforcement. The continuous-control experiments measure a low-dimensional torso-position representation, so they cannot establish reliable estimation in the full state space. At B = 32, sparse histogram counts distort the training score. In our position-space checks, kNN estimates change by at most 0.17 bits between 32 and 128 replicas, versus up to 1.12 bits for the binned estimate. This supports greater empirical stability, but does not establish unbiasedness; differential-entropy estimates also do not directly certify the discrete U budget.

Enforcement remains unresolved on Ant. At 10× training the original penalty meets the budget on 4/5 seeds by nearly standing still (C = 0.70). A kNN-based score with λ ≤ 1 preserves broader coverage (C = 6.92 at 3×) but does not lower U. We will report this limit plainly.

W2: presentation and related work. We will lead with the coverage/alignment distinction and the new downstream table; put J-PG in the main comparison; explain the connection to visitation entropy, finite-trial exploration, SMM/DIAYN, and general-utility gradients; and move secondary geometry and proofs to the appendix. The main theory will support three questions: what U certifies, why optimization can lock in, and when noise makes a budget impossible.

Anonymous code and supplementary results: https://hido.science/r/draxne5fpqcwts3hr2vy95f1

Reviewer_bGL9OpenReview ↗

Response to Rebuttal

Thank you for the responses and additional experiments. The new rendezvous and change detection evaluations are helpful to show a practical benefit of the method which addresses one of my concerns. Although the benefits seem limited to tasks where timing and predictability are important rather than being more generally useful. The coverage-first experiments also show promising improvements in avoiding incomplete routes, although the approach remains somewhat heuristic and does not resolve the difficulties on harder navigation tasks. My main outstanding concern is the estimation and enforcement of the snapshot-entropy constraint in higher-dimensional environments. Overall, I appreciate the additional work and believe the rebuttal has strengthened the paper while some important limitations for practical applicability remain. Therefore I will keep my score for now.

Reviewer_M2aYOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces Snapshot Entropy to distinguish pooled state coverage from time-aligned uncertainty across independent executions in reward-free reinforcement learning. The authors formulate exploration as maximizing pooled state entropy subject to a snapshot-entropy constraint and derive a model-free optimization method, Certainty Policy Gradient. The paper also provides theoretical analyses of single-run coverage, computational complexity, and feasibility under stochastic transitions. Experiments demonstrate improved single-run coverage and repeatability in structured tabular environments, while revealing significant coverage–certainty trade-offs in continuous-control tasks.

Critical strengths
  1. Well-motivated exploration objective. The paper identifies an important limitation of pooled state entropy: high aggregate coverage does not necessarily imply reliable coverage within individual executions. The proposed snapshot-entropy formulation provides a principled way to distinguish exploration coverage from cross-run uncertainty.

  2. Substantial theoretical analysis. Beyond introducing the objective, the authors derive a policy-gradient formulation and establish theoretical results concerning single-run coverage, optimization complexity, and feasibility. The controlled experiments further illustrate both the benefits and limitations of the proposed approach.

Critical weaknesses

a. Limited effectiveness in complex continuous-control environments. Although Certainty PG performs well in structured tabular environments, its performance on Ant and Humanoid reveals a substantial reduction in exploration coverage when enforcing certainty. Moreover, the prescribed snapshot-entropy constraint is not satisfied in either environment. These results raise concerns about whether the proposed method can achieve its intended balance between broad exploration and repeatability in more realistic settings.

b. Insufficient evidence for the practical necessity of time-aligned certainty. The paper demonstrates that snapshot entropy captures a property distinct from conventional state entropy and trajectory entropy. However, the trajectory-entropy baseline already achieves similarly high single-run coverage in Rooms-8. It remains unclear when additional time-aligned consistency provides meaningful practical benefits, particularly in stochastic or dynamic environments where different exploration trajectories may be equally effective.

Questions for authors
  1. Given the substantial coverage degradation and constraint violations observed in Ant and Humanoid, can the authors clarify under what conditions Certainty PG is expected to maintain broad exploration while satisfying the snapshot-entropy constraint?

  2. Can the authors provide an example or downstream evaluation demonstrating that lower snapshot entropy offers a practical advantage over trajectory-entropy maximization when both approaches achieve comparable single-run coverage?

1 comment
AuthorsOpenReview ↗

Practical Value of Alignment and Conditions for Broad Coverage

Thank you. The new experiments address both questions: when broad coverage and low uncertainty can coexist, and whether alignment adds practical value at comparable coverage.

Q2/W(b): practical benefit beyond within-run coverage. We evaluated scheduled rendezvous and repeat-survey change detection, where execution time affects downstream performance.

Noisy cycleJ-PGCertainty PG
All-state coverage100%99.9%
U (bits)0.8680.327
Rendezvous success0.8020.943
Change-detection power35.8%70.1%

Change detection uses a nominal 5% false-positive rate. The benefit persists when a rendezvous partner sees only one previous run: 0.894 success for Certainty PG versus 0.688 for J-PG.

An exactly coverage-preserving control isolates the contribution of alignment. We independently permute the exchangeable room labels of the Rooms-8 policy each episode. J remains 2.401 and all-state coverage remains 99.75%, but U rises from 0.010 to 1.451 bits. Rendezvous success falls from 0.999 to 0.577 and detection power from 75.7% to 11.1%. Thus identical within-run coverage can yield substantially different downstream utility when timing matters.

We agree that different trajectories can be equally useful for coverage-only tasks. We will recommend direct J optimization for that setting and make the intended scope explicit: the additional benefit of alignment arises when downstream decisions depend on execution time.

Q1/W(a): when can broad coverage and low U coexist? The answer depends on feasibility, optimization, and estimation.

Feasibility. With deterministic transitions and a fixed start, optimal within-run coverage is attainable by a route with U = 0. More precisely, for every λ ≥ 1,

max⁡π(C−λU)=max⁡πJ=max⁡routesC.\max_{\pi}(C-\lambda U)=\max_{\pi}J=\max_{\text{routes}}C.

This follows from

C−λU≤C−U≤J≤max⁡τH(mτ),C-\lambda U\le C-U\le J\le\max_{\tau}H(m_{\tau}),

with equality on an optimal route. Under stochastic transitions, low uncertainty may be impossible: Prop. 8 gives a computable lower bound on U. A budget at least as large as this bound is necessary, but not generally sufficient, for feasibility. On noisy Rooms-8 the learned U is only 0.003 bits above the bound.

Optimization. Even when a broad, certain route exists, the original schedule can settle on an incomplete route. Coverage-first certainty therefore optimizes J for 300 updates before adding the uncertainty penalty. On held-out seeds it improves all-state coverage from 0% to 99.99% on the ring and from 0% to 99.67% on the open grid, while meeting the budget on all 10 seeds for each task. On the 73-state grid it improves distinct states from 24.8 to 63.7 at U = 0.021; J-PG still covers more (71.5), at U = 1.532. These results demonstrate improved training behavior, while retaining the coverage–certainty trade-off on the harder task.

Estimation and representation. Ant's sparse per-time histograms make the training score sensitive to finite-batch estimation. Alternative estimators are more stable in our torso-position tests, but this does not establish unbiased estimation or enforcement in high-dimensional state spaces. Humanoid further shows that predictable behavior in the chosen position representation can mean falling and settling.

What the larger-budget Ant tests establish. At 10× training, Pooled PG and J-PG reach C = 7.72 and 7.75 bits, versus random's 6.56. The baselines therefore do exceed random when trained longer. The original certainty penalty satisfies the budget on 4/5 seeds but collapses coverage to C = 0.70. A kNN-based score with λ ≤ 1 retains C = 6.92 at 3× training but does not lower U. No tested variant achieves both goals.

We will make this boundary explicit: the theory establishes compatibility and impossibility conditions; the revised tabular experiments demonstrate useful alignment; continuous-control enforcement remains unresolved.

Anonymous code and supplementary results: https://hido.science/r/draxne5fpqcwts3hr2vy95f1

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

The paper starts by raising the (true) concern that the (time-averaged) state-visitation distribution used in standard maximum state-entropy exploration mixes two things: the change over time and the disagreement between independent runs at the same time step. For this reason, the authors propose to sample a time-index (from a distribution induced by discounting) and apply chain-tule of entropy with respect to that. The authors call H(X|T) “snapshot entropy” and they propose to do “exploration with certainty”: maximize pooled entropy subject to an upper bound constraint on snapshot entropy H(X|T).

The contributions are:

  • Interpretation. Snapshot entropy bounds the probability that two runs disagree at a sampled time (Prop. 2). Expected within-run entropy is at least pooled − snapshot entropy (Thm. 3).
  • Certainty PG. A likelihood-ratio policy gradient for the Lagrangian pooled − \lambda snapshot (Thm. 4). It estimates the time-indexed state laws from B syncronized rollouts, using leave-one-out estimates and a dual update on the Lagrangian multiplier.
  • Structural results. The snapshot entropy is concave in the occupancy measure, so the constraint is reverse-convex. Deterministic policies minimize it. Choosing a high-coverage zero-uncertainty route is NP-hard (proved via Hamiltonian path). For \lambda > 1, every deterministic route is a strict local maximum. Transition noise sets a lower bound on the snapshot that can be computed by dynamic programming.
  • Validation: --Tabular tasks (Rooms-8, directed cycle, noisy variants) with exact state distribution computation. On clean Rooms-8, Certainty PG keeps 98% of Pooled PG’s pooled entropy and yet raises single-run all-state coverage from 31.5% to 99.8%. On noisy Rooms-8 it gets close to the noise floor -- Navigation stress tests (ring, grids) where it locks onto incomplete routes -- Ant and Humanoid with binned torso position. Same-time dispersion falls (Ant: 2.51 m \to 1.13 m), but pooled coverage drops sharply! -- Appendix follow-ups: trajectory-entropy PG, Frank–Wolfe mixtures, downstream goal reaching, and robustness to start delays.
Critical strengths
  • A clean, correct and meaningful new decomposition. Splitting pooled entropy is simple but new in this literature. It allows some nice and interpretable guarantees: the disagreement bound (Prop. 2) and the single-run certificate (Thm. 3). Additionally, it reveals a blind spot of pooled-entropy objectives. Even if the constrained objective is proven to be of limited use, synchronized rollouts and snapshot entropy are still a good diagnostic others can adopt.
  • Honest characterization, including negative results. The paper is honest and fair. It establishes hardness, a local-optimality threshold at \lambda = 1, and a computable feasibility floor. It also reports several failures. Thus, the claims are generally trustworthy and future works are presented where the problem is hard.
Critical weaknesses
  • The paper never shows that repeatability is worth pursuing, and its own evidence points against it. The paper's motivation is to obtain useful coverage within a few executions. That is what expected within-run entropy J measures, and the paper's main guarantee lower-bounds J. But when J is optimized directly (trajectory-entropy PG):

    • it matches Certainty PG on clean Rooms-8: 99.3% vs. 99.8% all-state coverage, with higher J (Table 10);
    • it beats it by a wide margin on every navigation task: open grid (Table 8 vs. Table 10); 73-state grid, 71.5 vs. 24.8 expected distinct states (Table 15);
    • it is more robust to start delays: on the cycle, 99.99% vs. 49.7% (Table 17).

    In the downstream goal-reaching test there is no benefit from repeatability: on the open grid, 25% vs. 100% success (Table 16). Without a setting where time-aligned predictability is itself the goal (safety, reproducibility, multi-agent coordination), snapshot entropy works better as a diagnostic than as an exploration objective.

  • The method fails beyond toy examples.

    • On every non-scheduled navigation task, Certainty PG meets the budget but scores below random on pooled entropy and worst-state discovery. On the 73-state grid it visits fewer distinct states than random.
    • In continuous control the constraint is never satisfied: 0/5 seeds on both robots. Pooled coverage drops (Ant 6.19 \to 3.88 bits, Humanoid 5.08 \to 2.85).
    • On Humanoid, the extra "certainty" comes with falling over.
    • The training budget is so low that the baselines do not beat random (uniform random has the highest pooled entropy on Ant). That makes these results hard to interpret.

    So the empirical evidence for the method rests on two hand-designed tabular tasks.

  • Secondary: related work is limited. It omits convex RL in finite trials (Mutti et al.), which formalizes the same expected-vs-single-trial gap. It also omits the general-utility policy gradient (Zhang et al.). And it does not connect to the mutual-information objectives used in unsupervised RL, such as DIAYN.

Questions for authors

Discounting. In Eq. 2 weights times geometrically, citing analogy with discounted RL, but there is no reward or task here. Why should earlier visits count more for exploration? How do the results change with uniform weights over time, which is the natural choice for a fixed-horizon episode?

2 comments
AuthorsOpenReview ↗

Value Beyond Coverage, Navigation Improvements, and Discounting

Thank you for identifying the distinction the paper needs to make explicit: within-run coverage alone does not justify repeatability. Our new experiments evaluate settings in which time alignment has operational value.

W1: does repeatability add value beyond J? Yes, in the new alignment-dependent evaluations, at comparable coverage:

Noisy cycleJ-PGCertainty PG
All-state coverage100%99.9%
U (bits)0.8680.327
Rendezvous, partner knows policy0.8020.943
Rendezvous, one observed run0.6880.894
Change-detection power35.8%70.1%

The survey test uses a nominal 5% false-positive rate. Certainty PG also learns to resynchronize: a run one step ahead of schedule advances only 0.7% of the time; a run one step behind advances 99.8%.

We isolate alignment with an exactly coverage-preserving control on Rooms-8: independently permuting exchangeable room labels each episode leaves J = 2.401 and all-state coverage = 99.75% unchanged. U rises from 0.010 to 1.451 bits, rendezvous falls from 0.999 to 0.577, and detection power from 75.7% to 11.1%. These controlled tasks establish value when timing matters. For coverage-only downstream uses, our results favor direct J optimization; we will state that scope prominently.

J-PG's parity on clean tasks is also theoretically natural. With deterministic transitions and a fixed start, for λ ≥ 1,

max⁡π(C−λU)=max⁡πJ=max⁡routesC.\max_{\pi}(C-\lambda U)=\max_{\pi}J=\max_{\text{routes}}C.

Indeed,

C−λU≤C−U≤J≤max⁡τH(mτ),C-\lambda U\le C-U\le J\le\max_{\tau}H(m_{\tau}),

with equality attained by an optimal route. Thus optimal within-run coverage and certainty are compatible, although the objectives need not select the same policies or have the same optimization behavior.

W2: navigation failures. We tested coverage-first certainty: 300 J-PG updates followed by J − λU. The default was selected on calibration seeds 0–9; results below use held-out seeds 100–109.

TaskOriginal certaintyCoverage-firstJ-PG
Ring: all-state coverage0%99.99%99.98%
Open grid: all-state coverage0%99.67%98.71%
73-state grid: distinct states24.863.771.5
Slippery grid: all-state coverage0%82.8%89.6%

Coverage-first meets the budget on all 10 seeds in the first three tasks, with U = 0.007/0.016/0.021, versus J-PG's 0.196/0.521/1.532. On the cycle, it also retains 100% coverage under the tested 1–3-step start delays. J-PG remains better on the harder grids; we will retain those comparisons.

Prop. 7 motivates delaying concentration: λ > 1 makes every deterministic route a strict local maximum in state-law space. It does not prove that λ ≤ 1 prevents lock-in. Moreover, J − λU can also lock in without the coverage phase (ring 40%, open grid 0%). The revised schedule substantially improves the observed results, but does not guarantee escape from local optima.

Continuous control. The larger-budget experiments address your concern about weak baselines. At 10× training, Pooled PG/J-PG reach C = 7.72/7.75 on Ant, versus random's 6.56. However, no tested certainty variant achieves both broad coverage and low U. With the original penalty, feasibility can come from standing still; kNN scoring with λ ≤ 1 preserves broader coverage but does not resolve enforcement. Humanoid's position representation likewise permits predictable falling. We will state these limits explicitly.

W3: related work. We will connect C − U ≤ J ≤ C to Mutti et al.'s finite-trial formulation, credit Thm. 4 as an application of the general-utility policy gradient, and explain that λ = 1 yields I(T;X), analogous to skill-discriminability objectives with time as the conditioning variable.

Q: discounting. Geometric weights match discounted occupancy and correspond to a geometrically distributed observation time conditioned on the finite horizon. Uniform weights are a natural fixed-horizon alternative. The principal identities, gradient, and feasibility bound hold for arbitrary positive weights; Thm. 6 uses a specific discount in its reduction.

Uniform-weight experiments preserve the main distinction: Rooms-8 achieves 99.77% coverage with U = 0.011, and the noisy-cycle U values are 0.336 versus J-PG's 0.741 at comparable coverage. However, open-grid coverage-first is less robust (70.1% mean), so we will report this exception rather than claim complete invariance.

Anonymous code and supplementary results: https://hido.science/r/draxne5fpqcwts3hr2vy95f1

I thanks the authors for their fair rebuttal, it is scientifically very valuable. Unfortunately though the main points remain open:

  • Q: discounting. Discounting is usually well-motivated in infinite-horizon settings. As far as I understood, the horizon K here is fixed, thus the idea of weighting specific time-steps is still unclear to me.
  • Coverage-first is an interesting idea, but it needs further justifications and cannot be added as a fix on top as it is right now at this point of discussion. It could be a nice way to achieve good performances in general while pushing for this idea but it needs substantial justification.
  • W1: does repeatability add value beyond J? Yes, in the new alignment-dependent evaluations: while this is a valid test, the overall scope of the contribution would need to be reduced accordingly.

I therefore stick with my evaluation. In order to address some of the concerns, and to adjust the overall scope of the paper the manuscript would go substantial changes which would make it a different paper, in practice. The fact that continuous control setups remain substantially an open issue (as far as I understood) is a blocking point to me as well.

Reviewer_WfXNOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies reward-free maximum state-entropy exploration. The contribution is snapshot entropy U = H(X|T), an objective that maximizes pooled entropy subject to a budget on U, the Certainty PG algorithm with an exact policy gradient, and theory (deterministic policies suffice, NP-hardness of choosing a route, a DP floor under noisy transitions).

The validation is on tabular gridworlds (Rooms-8, Cycle-16, noisy and stress variants, ten seeds) and Ant/Humanoid with binned torso position.

Critical strengths
  1. The idea is clean and easy to check: splitting pooled entropy by the chain rule gives a measure of run-to-run disagreement at the same time, and the two-rooms example (Fig 1) shows two policies with the same pooled distribution but 100% vs 49.45% of runs visiting both rooms.
  2. The theory and protocol are careful: proofs with numerical checks in the appendix, held-out seeds, final iterates without checkpoint selection, and failure cases reported in the main text (Sec 6.2).
Critical weaknesses
  1. The contribution is mainly conceptual, and the paper does not position it against the closest work. Only 7 of 16 references are RL papers, the newest from 2022. The core quantity U=∑twtH(dt)U = \sum_t w_t H(d_t) has the same form as the visitation entropy ∑hH(dh)\sum_h H(d_h) of Tiapkin et al. (ICML 2023, arXiv:2303.08059), which is maximized there and bounded here. Convex RL in finite trials (Mutti et al., JMLR 2023, arXiv:2202.01511), state marginal matching (Lee et al. 2019, arXiv:1906.05274) and parallel-agent state entropy (arXiv:2505.01336) are not cited either, and Thm 6 is not compared with the NP-hardness in Mutti et al. (ICML 2022, arXiv:2202.03060).
  2. The method does not improve any task metric over the best comparator. The headline 31.5% to 99.8% is against Pooled PG, but Random already gets 31.31% (Table 1) and Trajectory-entropy PG gets 99.33% (L377/378, not in Table 1). Only U is lower, but the downstream test finds "not a general downstream advantage", and on Ant pooled entropy drops 6.19 to 3.88 (Table 18).
Questions for authors
  1. How does U differ from the visitation entropy ∑hH(dh)\sum_h H(d_h) of Tiapkin et al. (ICML 2023, arXiv:2303.08059), and how does this work relate to convex RL in finite trials (Mutti et al., JMLR 2023) and the NP-hardness in Mutti et al. (ICML 2022)? (clarification)
  2. Can you show a task where low U itself helps when within-run coverage is equal, with Trajectory-entropy PG as the comparator? (suggestion)
  3. The code is not provided. Can you share it, at least for the comparator implementations, which are re-implemented without per-comparator tuning? (clarification)
1 comment
AuthorsOpenReview ↗

Related Work, Benefits Beyond Coverage, and Code

Thank you. Your review identifies two issues we address directly: the relationship to existing entropy objectives, and evidence of benefit against J-PG rather than only Pooled PG.

W1/Q1: Tiapkin et al. and finite-trial exploration. You are correct: with uniform time weights and state rather than state–action marginals, KU is the visitation entropy of Tiapkin et al. (2023). We will credit this explicitly and remove any suggestion that the functional form itself is new. Our contribution is to bound this quantity and characterize the resulting coverage, agreement, and optimization properties.

Let C be pooled entropy and J the expected entropy of a single run's visitation distribution. For an independently sampled time T and trajectory τ,

C=U+I(T;X),J=I(T;X∣τ)=I(T;X)+I(T;τ∣X).C=U+I(T;X),\qquad J=I(T;X\mid\tau)=I(T;X)+I(T;\tau\mid X).

Hence 0 ≤ C − J ≤ U. This connects directly to Mutti et al.'s finite-trial distinction: U certifies an upper bound on the pooled/single-trial gap. Over the same policy class constrained by U ≤ ε, a maximizer of either C or J is ε-optimal for the other. This does not claim equivalence to unrestricted, unconstrained non-Markovian optimization.

Hardness. Mutti et al. (ICML 2022) establish NP-hardness of finding an optimal non-Markovian policy for J. Our Thm. 6 establishes hardness of additive 1/(3n)-approximation for C under a small U budget, already with deterministic transitions, a fixed start, and time-dependent Markov policies. The distinction is the restricted dynamics and approximation guarantee; we will not characterize the earlier hardness as arising solely from history dependence.

The connection is especially direct with deterministic transitions and a fixed initial state: for λ ≥ 1,

max⁡π(C−λU)=max⁡πJ=max⁡routesC.\max_{\pi}(C-\lambda U)=\max_{\pi}J=\max_{\text{routes}}C.

Indeed, C − λU ≤ C − U ≤ J ≤ max_τ H(m_τ), and an optimal deterministic route attains every bound. Thus our reduction also rules out efficiently returning a deterministic route whose J is within 1/(3n) of optimal.

We will also discuss SMM, parallel-agent entropy, and MI-based skill discovery. At λ = 1, our objective is I(T;X): the conditioning variable is the clock, rather than an episode-level skill. We will credit Thm. 4 as an application of the general-utility policy gradient.

W2/Q2: benefit at comparable coverage, against J-PG. We agree that the original headline against Pooled PG did not answer this question. New held-out evaluations do:

Noisy cycleJ-PGCertainty PG
All-state coverage100%99.9%
U (bits)0.8680.327
Scheduled rendezvous success0.8020.943
Change-detection power35.8%70.1%

Change detection compares repeat surveys at a nominal 5% false-positive rate. These tasks explicitly require time alignment.

An exactly coverage-preserving control strengthens the comparison: randomly permuting exchangeable room labels independently each episode preserves the Rooms-8 policy's J = 2.401 and 99.75% all-state coverage. U increases from 0.010 to 1.451; rendezvous falls from 0.999 to 0.577 and detection power from 75.7% to 11.1%. J-PG achieves 99.33% coverage, rendezvous 0.983, and power 30.5%. Thus the added benefit is not explained by greater within-run coverage.

Coverage-first training also recovers 99.99%/99.67% all-state coverage on the ring/open grid, with all 10 seeds feasible. We retain the negative findings: J-PG covers more of the 73-state grid, and no tested Ant variant achieves both broad coverage and low U. At 10× training, Ant baselines do exceed random: C = 7.72/7.75 for Pooled/J-PG versus 6.56.

Q3: code and tuning. Anonymous code, comparator implementations, and supplementary results are available at https://hido.science/r/draxne5fpqcwts3hr2vy95f1. Equal-budget tuning uses six configurations per learned method, selected on calibration seeds 0–9 and evaluated on held-out seeds 100–109; we also select directly on all-state coverage as a sensitivity check. Tuned J-PG reaches 99.16% open-grid coverage at U = 0.164, versus 99.67% at U = 0.016 for coverage-first certainty. Tuning the original certainty schedule alone does not fix navigation.

We will add J-PG to the main table and center the revised claims on coverage with alignment, with coverage-only and continuous-control limitations explicit.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Response to All Reviewers: Value Beyond Coverage, New Experiments, and Clarified Scope

Thank you for the careful reviews. The central question is whether time-aligned predictability adds value beyond within-run coverage. Our new experiments address this directly: at comparable coverage, lower snapshot entropy improves scheduled rendezvous and repeat-survey change detection. A controlled comparison preserves within-run entropy and coverage exactly while varying alignment.

Anonymous code and supplementary results: https://hido.science/r/draxne5fpqcwts3hr2vy95f1

Write C=H(X)C = H(X), U=H(X∣T)U = H(X|T), and J=E[H(mτ)]J = E[H(m_τ)], the expected entropy of one run's visitation distribution. We call the direct J-maximizing comparator J-PG.

1. Value beyond coverage. On the noisy cycle, Certainty PG and J-PG achieve 99.9% and 100% all-state coverage. Certainty PG reduces U from 0.868 to 0.327 bits, raises rendezvous success from 0.802 to 0.943, and raises change-detection power from 35.8% to 70.1% at a nominal 5% false-positive rate. A partner observing only one previous run also benefits: rendezvous success is 0.894 versus 0.688.

To isolate alignment from coverage, we randomly permute the exchangeable room labels of the Rooms-8 policy independently each episode. This preserves J = 2.401 and all-state coverage = 99.75%, while U rises from 0.010 to 1.451 bits. Rendezvous success falls from 0.999 to 0.577 and detection power from 75.7% to 11.1%. Thus, identical within-run coverage can support substantially different downstream performance when execution time matters.

These controlled tasks demonstrate the value of alignment when timing matters. For coverage-only applications, our results favor optimizing J directly.

2. Recovering coverage before enforcing certainty. The original schedule can concentrate on incomplete routes. We therefore tested coverage-first certainty: optimize J for 300 updates, then J − λU. The default schedule was selected on calibration seeds 0–9; the following results use held-out seeds 100–109 and final iterates.

TaskOriginal certaintyCoverage-firstJ-PG
Ring: all-state coverage0%99.99%99.98%
Open grid: all-state coverage0%99.67%98.71%
73-state grid: distinct states24.863.771.5

Coverage-first satisfies the budget on all 10 seeds for each task. Its U values are 0.007/0.016/0.021 bits, versus 0.196/0.521/1.532 for J-PG. The 73-state result remains a coverage–certainty trade-off. We will report all tested schedules, including weaker results.

3. Theoretical contribution and positioning. We will explicitly credit the state-marginal version of Tiapkin et al.'s visitation entropy: with uniform time weights, it equals KU. Our contribution is its use as a constraint and certificate. The identities

C=U+I(T;X),C = U + I(T;X),

J=I(T;X)+I(T;τ∣X)J = I(T;X) + I(T;τ|X)

give 0≤C−J≤U0 ≤ C − J ≤ U. Consequently, over the same feasible policy class U≤εU ≤ ε, a maximizer of either CC or JJ is ε-optimal for the other.

With deterministic transitions and a fixed initial state, for every λ ≥ 1, max⁡π(C−λU)=max⁡πJ=max⁡routesC.\max_{\pi}(C-\lambda U)=\max_{\pi}J=\max_{\text{routes}}C. An optimal route attains all three values. Thus, optimal within-run coverage and certainty are compatible in this setting, although policy-gradient training is not guaranteed to find that route.

4. Continuous-control limitations. At 10× the original Ant training budget, Pooled PG and J-PG reach C = 7.72 and 7.75 bits, versus 6.56 for random actions. However, no tested certainty variant achieves both broad coverage and low U. The original penalty can obtain feasibility through near-stationary behavior; a kNN-based score with λ ≤ 1 preserves broader coverage but does not resolve constraint enforcement. We will present Ant as evidence of the diagnostic’s value and the method’s limitations, and Humanoid as a caution about the state representation.

Revisions and reproducibility. We will foreground J-PG, add the alignment evaluations, expand related work, credit the general-utility gradient connection, and report equal-budget tuning and uniform-weight results. The anonymous link above provides code, comparator implementations, and supplementary results.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.