- 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
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.
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:
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=maxroutesC.
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.
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