- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper addresses the computational cost of calculating process empowerment in discrete environments, where the existing Alternating Blahut-Arimoto algorithm requires exponential time per iteration with respect to the planning horizon. The authors prove that under Markovian transition dynamics, the search space can be restricted to Markovian probing policies without loss of optimality (Proposition 1), and derive simplified self-consistent equations (Theorem 2) that reduce the per-iteration complexity to be polynomial in the horizon, state space, and action space via forward-backward dynamic programming passes. Furthermore, the authors propose early stopping and warm-start initialization (reusing probing policies from predecessor states) to accelerate convergence, demonstrating across six stochastic MiniGrid environments from the BRIDGE dataset that a few iterations suffice to produce empowerment landscapes highly consistent with exact computation in terms of STARC distance and Kendall's
Critical strengths
-
Proving that Markovian probing policies suffice to achieve exact process empowerment and eliminating history-dependent residuals in the ABA update equations is a clean, rigorous, and highly practical theoretical contribution that reduces per-iteration complexit
-
Evaluating the empowerment approximations under reward-equivalence metrics and state-ranking correlation rather than relying solely on numerical precision aligns well with how intrinsic motivation signals are actually utilized in reinforcement learning.
-
The paper provides an intuitive analysis of when and why warm-starting from a predecessor state can underperform uniform initialization at short horizons, formalizing this boundary effect clearly as the magic portal phenomenon.
Critical weaknesses
-
the paper contains no RL training experiments; all evaluations are conducted offline on pre-computed ground-truth tabular transition matrices from the BRIDGE dataset, leaving the effectiveness of the approximated signal under online policy learning or learned world models unverified.
-
The reported speedups in Tables 1 and 2 rely on an oracle early-stopping threshold selected post-hoc by comparing against the fully converged landscape until STARC distance reaches 0.025, and the warm-start evaluation tests single-step transfers from converged predecessors rather than chained warm-starts along trajectories where approximation errors could compound.
-
The manuscript suffers from noticeable drafting flaws, including an unfinished sentence ending in an ellipsis in Section 4 , unresolved LaTeX citations ((?)).
Questions for authors
-
How do the computational speedups, STARC distances, and Kendall's values in Tables 1 and 2 change if you apply a fixed, environment-agnostic stopping hyperparameter across all settings
-
If warm-start is applied along the agent's trajectory () where each state is initialized from the early-stopped probing policy of the previous state, do approximation errors accumulate over time, and how does this approximate empowerment perform when actually used to train an RL agent in MiniGrid?
-
can you provide RL training experiments in MiniGrid demonstrating that your approximated empowerment successfully guides exploration?
5 comments
Answer to Q2: If warm-start is applied along the agent's trajectory where each state is initialized from the early-stopped probing policy of the previous state, do approximation errors accumulate over time?
We again wish to thank reviewer dAt3 for his question and suggestion.
In short:
Chained warm-starts across a trajectory do not accumulate errors (relative error is stable at for all tested depths) while the number of iterations of the algorithm until early-stop stays constant at all points in the trajectory. It has been found that when warm-start is applied along a trajectory it takes around 1.1 times on average the amount of iterations it takes when the predecessor has not been warm-started. Finally, landscapes of empowerment computed with warm-start along a chain maintain a STARC distance comparable to that of landscapes computed with warm-start from a non warm-started predecessor.
Full answer:
To address the first part of the question: experimentation in the submission warm-started each state from a random predecessor that had been computed from the uniform policy and early-stopped at an oracle-given . In the following, all mentioned predecessors are computed at tolerance .
We add a chained ablation to answer wether errors acumulate. Empowerment is approximated without warm-start for the initial state of the environment by running until early stop at . Every other state starts from a predecessor one step closer to the initial state, itself warm-started this way except at the first step. The chain of warm starts for a state goes along a shortest trajectory from the initial state. These chains have length 8 to 24 steps on average, and up to 16 to 38 depending on the environment. Every run stops at . The policies used to warm-start are the ones of the predecessor when it stops at .
| Iterations, cold-started predecessor | Iterations, chain of warm starts | STARC, cold-started predecessor | STARC, chain of warm starts | |
|---|---|---|---|---|
| 2 | 2.00 | 2.00 | 0.0225 | 0.0227 |
| 4 | 2.19 | 2.61 | 0.0135 | 0.0167 |
| 6 | 2.22 | 2.68 | 0.0153 | 0.0144 |
| 8 | 2.25 | 2.47 | 0.0136 | 0.0097 |
Median over the 8 environments at . Iterations: mean per warm-started state (the cold-started initial states are excluded).
From this the speedup against running Markovian ABA until convergence for both warm-start experimentations is derived.
| Speedup, cold-started predecessor (iterations) | Speedup, cold-started predecessor (time) | Speedup, chain of warm starts (iterations) | Speedup, chain of warm starts (time) | |
|---|---|---|---|---|
| 2 | 48.5× | 18.8× | 48.9× | 14.1× |
| 4 | 138.3× | 58.6× | 111.7× | 57.2× |
| 6 | 215.2× | 120.6× | 176.2× | 105.3× |
| 8 | 374.4× | 208.1× | 320.4× | 188.7× |
Speedup over the exact computation, as in the table of Question 1, median over the 8 environments at . For the iterations we choose the median of environment averages.
Finally, we provide an estimate of how the average number of iterations and the relative error in the empowerment approximation evolve across chain depths.
| Depth in the chain | 1–4 | 5–9 | 10–14 | 15–19 | 20–24 | 25+ |
|---|---|---|---|---|---|---|
| Factor (iterations) | 1.10 | 1.15 | 1.14 | 1.15 | 1.12 | 1.12 |
| Mean relative error, chained warm start | 2.2% | 2.1% | 2.1% | 2.1% | 2.1% | 2.0% |
| Mean relative error, cold-started predecessor | 2.9% | 2.7% | 2.8% | 2.8% | 2.8% | 2.6% |
| Mean relative error, no warm start (ES) | 3.7% | 3.6% | 3.6% | 3.7% | 3.7% | 3.5% |
Factor corresponds to the ratio of the average number of iterations of warm-start using predecessors in a chain of warm-starts against cold-started predecessors. Mean relative error: averaged over the states of that depth, with the value at the early stop and the exact value.
The error does not propagate along the chain: at every depth, chained states have a lower mean relative error than the same states without warm start or warm-started from a cold-started predecessor, and it stays at about at all depths. The factor does not grow with depth: chaining costs about times the iterations whatever the length of the chain.
This new experiment shows warm-start is robust to being applied to a whole trajectory. In particular, the speed-ups remain strong while the usefulness measured by the STARC distance to converged is not hurt compared to our previous warm-start experiment using the policies of a cold-started predecessor.
In the final manuscript this is intended to be mainly discussed in the appendix and only briefly discussed in the main text.
Answer to Q2, RL esperiment [1/2]: How does this approximate empowerment perform when actually used to train an RL agent in MiniGrid?
We thank dAt3 for its review and for pointing in this direction.
In short:
We execute an online learning RL experiment using empowerment as a reward. The Learning agent approximates empowerment using Markovian ABA with warm-start and early-stop (Markovian ABA WS+ES) from the model while learning it. It is then compared against a random walker and an Oracle agent learning the model using true exact empowerment. With optimistic exploration (Decay R-MAX), the Learning agent is seen to be almost as good at seeking the highest empowerment sates as the Oracle (see table) both are successful at reaching the highest empowerment states. The longest training run, using horizon 8, takes a mean of 5 minutes at most on a single CPU thread in a mid-range laptop (see Appendix B), highlighting the cost-efficiency and suitability for RL of Markovian ABA WS+ES.
Markovian ABA WS+ES makes empowerment a practical online reward: cheap to compute from a model still being learned, and almost as effective as true empowerment at leading an agent to the most empowered states.
Full answer:
We train an RL agent in MiniGrid with reward , MiniGrid's original reward is ignored. We divide the number of steps in two halves, the first for exploration, the second mainly for exploitation. We also train as a reference an oracle for whom the transition function is unknown, but that uses true empowerment as its reward, then a random walker.
In a first try we used -greedy with exploration rate linearly decaying from to in the exploration phase and then staying constant at for exploitation. Untried state-action pairs get a pessimistic value . This fails to find the regions with the highest empowerment in 3 of the 8 environments (SimpleCrossingS9N2, DoorKey-5x5 at and KeyCorridorS3R2), with success dependent on the seed. This happens only for the learning agent (see table), so the failures come from : on a partly learned model, states whose actions are still untried get low empowerment, and nothing draws the agent out of the first region it has fully explored. This highlights the need to correctly handle exploration.
To improve exploration, we use R-MAX (Brafman & Tennenholtz, 2002), while decays, which we refer in this answer as Decay R-MAX: untried pairs are valued optimistically for all three agents, with an upper bound of empowerment, and go back to after reaches . Optimism, by assigning an empowerment upper bound to what the model does not know yet, was used by (Jung et al., 2011).
Results for both trainings are:
| Environment | -greedy, | time (s) | Decay R-MAX, | time (s) | -greedy, | time (s) | Decay R-MAX, | time (s) |
|---|---|---|---|---|---|---|---|---|
| MultiRoom-N2-S4 | 98.6 ± 0.9 | 3.3 | 99.8 ± 0.5 | 2.9 | 95.5 ± 0.8 | 12 | 100.2 ± 0.7 | 13 |
| SimpleCrossingS9N2 | 69.9 ± 16.4 | 4.6 | 97.5 ± 1.3 | 5.1 | 77.2 ± 13.0 | 22 | 99.8 ± 0.3 | 39 |
| KeyCorridorS3R1 | 97.6 ± 1.8 | 4.9 | 97.4 ± 1.4 | 4.9 | 98.3 ± 1.6 | 16 | 99.3 ± 0.6 | 24 |
| DoorKey-5x5 | 95.1 ± 7.1 | 6.6 | 99.2 ± 0.8 | 4.5 | 75.8 ± 22.5 | 19 | 98.5 ± 1.5 | 24 |
| FourRooms | 95.5 ± 1.2 | 62 | 95.5 ± 1.1 | 49 | 98.6 ± 1.0 | 175 | 99.6 ± 0.4 | 260 |
| Unlock | 98.7 ± 0.6 | 69 | 98.4 ± 0.7 | 41 | 99.8 ± 0.1 | 214 | 99.8 ± 0.0 | 280 |
| ObstructedMaze-1Dl | 96.6 ± 0.5 | 134 | 95.9 ± 0.9 | 71 | 97.0 ± 3.6 | 243 | 99.3 ± 0.2 | 298 |
| KeyCorridorS3R2 | 75.9 ± 11.3 | 146 | 97.4 ± 2.0 | 87 | 67.5 ± 22.5 | 186 | 99.1 ± 0.8 | 209 |
| Below 90 | 18/80 | 0/80 | 20/80 | 0/80 |
Learning score (see next comment, 0 = random walker, 100 = Oracle), mean 95% confidence interval over 10 seeds. Time: wall time of a full learning run, mean over seeds. Below 90: runs with score < 90. Bold: higher score, both if tied.
With Decay R-MAX, the Learning agent has a median score of 97.9 and 99.7 over runs (), and none of its 160 runs scores below 90. It therefore collects almost as much true empowerment as the Oracle. Empowerment approximated by Markovian ABA WS+ES on a model learned online is thus nearly as good a reward for reaching the states with the highest empowerment as true empowerment.
Both the Learning agent and the Oracle are close to the best achievable at seeking the higher empowerment states. On a scale from the random walker (0) to the mean true empowerment of the best 1% of states (100), the Oracle scores 96.3 and 98.5 and the Learning agent with Decay R-MAX 94.2 and 98.2 (median over runs, ). Empowerment computed with Markovian ABA WS+ES on a model learnt online is therefore enough, on its own, to bring an agent close to the highest-empowerment states.
Citations and details next.
Answer to Q1: How do the computational speedups, STARC distances, and Kendall's values in Tables 1 and 2 change if you apply a fixed, environment-agnostic stopping hyperparameter across all settings?
We wish to thank reviewer dAt3 for its feedback and questions. We would like now to answer the first question.
In short:
With one fixed tolerance for every environment and horizon, both early stopping and warm start keep the median environment within STARC distance 0.025 of the exact empowerment at every horizon (on a scale from 0 to 2), with median speedups with respect to the exact Markovian ABA of 49–156× (ES) and 49–320× (WS+ES) in iterations, and 14–189× in time. Below a more in detail answer.
Full answer
We choose to apply as an early-stop parameter a fixed tolerance ε=0.1 bits: every state, in every environment and horizon, stops at the first iteration with ∣E(k)−E(k−1)∣<ε. We agree the previous experimental set up relied on an oracle. To make results more informative, ε is now fixed in advance, and no landscape is used to choose anything.
In order to test our method in bigger environments we added KeyCorridorS3R2 and ObstructedMaze-1Dl, with 28,161 and 18,059 states once expanded with sticky actions.
Warm-start previously relied on the predecessor's policies computed using a cold-start until an oracle given tolerance. It is now stopped at the same ε used by early-stop. Additionally, as in the answer Question 2 replaces the cold-started predecessor with a chain of warm starts, as it is a more realistic situation. This procedure is explained as an answer to the next question.
Fixed tolerance ε=0.1, median over the 8 environments for all metrics
The median environment remains within STARC distance at most 0.025 of the exact empowerment. The three worst STARC distances are all in Unlock: 0.085 at T+1=2, 0.062 at T+1=6 and 0.053 at T+1=4 for ES, which warm start lowers to 0.081, 0.032 and 0.041. Speedups are smaller at shorter horizons, partly due to a higher proportion of their execution time being carried by constant overhead and by convergence to the exact value of empowerment being faster.
On the correction of an inefficiency bug in our ABA implementation: All wall-clock times in this response were measured after we corrected an inefficiency bug in our implementation of the backward pass of Markovian ABA. The iterates are unchanged (the same number of iterations for every state, values equal to within 10−13 bits), so iteration counts, STARC and Kendall τ are unaffected, while the time per state dropped by 2× at T+1=2 to 5× at T+1=8. Times are therefore not directly comparable with the submitted Table 2, a general response on that will soon be published.
The experiments included in the final submission using early-stop will use a fixed tolerance as in here instead of with an oracle given one.