acceptodds
Under review as a conference paper at ICLR 2027

Useful empowerment approximation for its use in Learning Agents

Abstract

Process (closed-loop) empowerment is a relevant measure for agency, with promising uses for intrinsic motivation and reinforcement learning. However, its prohibitive computational cost, especially in discrete environments, precludes many of its applications to anything but toy examples and the smallest environments. We introduce a reformulation of process empowerment for Markovian dynamics under which the empowerment computation becomes tractable, and derive from it a variant of the Alternating Blahut-Arimoto algorithm whose per-iteration cost is polynomial in the number of states, actions and horizon compared to previous exponential in the horizon per-iteration cost; making empowerment a viable signal in more complex environments. Moreover, we introduce even faster approximations of empowerment via early-stopping, showing that few iterations are enough to compute empowerment to a reasonable precision, and a warm-start initialisation reusing other states' empowerment information to hasten computation. Across six Minigrid environments, the resulting approximations reach a STARC distance, a reward comparison metric, of 0.025 from exact empowerment making the approximation behaviourally interchangeable with the exact signal at almost no cost. Our approach achieved this in between 1.0 and 6.4 iterations per state on average compared to between 75 and 1275 for the exact computation.

Primary area:
learning theory
Keywords:
Empowerment, artificial intelligence, reinforcement learning, autonomous agents

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_dAt3OpenReview ↗
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 τ\tau

Critical strengths
  1. 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

  2. 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.

  3. 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
  1. 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.

  2. The reported speedups in Tables 1 and 2 rely on an oracle early-stopping threshold ϵ∗\epsilon* selected post-hoc by comparing against the fully converged landscape E∗E^* 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.

  3. The manuscript suffers from noticeable drafting flaws, including an unfinished sentence ending in an ellipsis in Section 4 , unresolved LaTeX citations ((?)).

Questions for authors
  1. How do the computational speedups, STARC distances, and Kendall's τ\tau values in Tables 1 and 2 change if you apply a fixed, environment-agnostic stopping hyperparameter across all settings

  2. If warm-start is applied along the agent's trajectory (s0→s1→s2…s_0 \to s_1 \to s_2 \dots) 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?

  3. can you provide RL training experiments in MiniGrid demonstrating that your approximated empowerment successfully guides exploration?

5 comments
AuthorsOpenReview ↗

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\varepsilon = 0.1 bits: every state, in every environment and horizon, stops at the first iteration with ∣E(k)−E(k−1)∣<ε|\mathcal{E}^{(k)} - \mathcal{E}^{(k-1)}| < \varepsilon. We agree the previous experimental set up relied on an oracle. To make results more informative, ε\varepsilon 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 ε\varepsilon 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.

T+1T+1ES speedup (iterations)ES speedup (time)WS+ES speedup (iterations)WS+ES speedup (time)STARC ESSTARC WS+ESKendall τ\tau ESKendall τ\tau WS+ES
248.9×14.7×48.9×14.1×0.02500.02270.9950.960
486.4×51.1×111.7×57.2×0.01970.01670.9210.907
6107.2×84.0×176.2×105.3×0.01510.01440.9600.943
8155.7×124.1×320.4×188.7×0.01290.00970.9630.949

Fixed tolerance ε=0.1\varepsilon = 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=2T+1 = 2, 0.062 at T+1=6T+1 = 6 and 0.053 at T+1=4T+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−1310^{-13} bits), so iteration counts, STARC and Kendall τ\tau are unaffected, while the time per state dropped by 2×2\times at T+1=2T+1 = 2 to 5×5\times at T+1=8T+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.

AuthorsOpenReview ↗

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 2%2\% 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 δ∗\delta^*. In the following, all mentioned predecessors are computed at tolerance δ=0.1\delta = 0.1.

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 δ=0.1\delta = 0.1. 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 δ=0.1\delta = 0.1. The policies used to warm-start are the ones of the predecessor when it stops at δ\delta.

T+1T+1Iterations, cold-started predecessorIterations, chain of warm startsSTARC, cold-started predecessorSTARC, chain of warm starts
22.002.000.02250.0227
42.192.610.01350.0167
62.222.680.01530.0144
82.252.470.01360.0097

Median over the 8 environments at δ=0.1\delta = 0.1. 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.

T+1T+1Speedup, cold-started predecessor (iterations)Speedup, cold-started predecessor (time)Speedup, chain of warm starts (iterations)Speedup, chain of warm starts (time)
248.5×18.8×48.9×14.1×
4138.3×58.6×111.7×57.2×
6215.2×120.6×176.2×105.3×
8374.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 δ=0.1\delta = 0.1. 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 chain1–45–910–1415–1920–2425+
Factor (iterations)1.101.151.141.151.121.12
Mean relative error, chained warm start2.2%2.1%2.1%2.1%2.1%2.0%
Mean relative error, cold-started predecessor2.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: ∣E^(s)−E∗(s)∣E∗(s)\frac{\lvert \hat{\mathcal{E}}(s) - \mathcal{E}^{\ast}(s) \rvert}{\mathcal{E}^{\ast}(s)} averaged over the states of that depth, with E^(s)\hat{\mathcal{E}}(s) the value at the early stop and E∗(s)\mathcal{E}^{\ast}(s) 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 2%2\% at all depths. The factor does not grow with depth: chaining costs about 1.11.1 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.

AuthorsOpenReview ↗

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 P^\hat P 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 R(s,a,s′)=E^(s′)\mathcal{R}(s, a, s') = \hat{\mathcal{E}}(s'), 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 η\eta-greedy with exploration rate η\eta linearly decaying from 11 to 0.10.1 in the exploration phase and then staying constant at 0.10.1 for exploitation. Untried state-action pairs get a pessimistic value Q=0Q = 0. This fails to find the regions with the highest empowerment in 3 of the 8 environments (SimpleCrossingS9N2, DoorKey-5x5 at T+1=8T+1 =8 and KeyCorridorS3R2), with success dependent on the seed. This happens only for the learning agent (see table), so the failures come from E^\hat{\mathcal{E}}: 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 η\eta decays, which we refer in this answer as Decay R-MAX: untried pairs are valued optimistically Rmax⁡/(1−γ)R_{\max}/(1-\gamma) for all three agents, with Rmax⁡=log⁡2(∣S∣+1)R_{\max} = \log_2(|\mathcal{S}|+1) an upper bound of empowerment, and go back to Q=0Q = 0 after η\eta reaches 0.10.1. 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η\eta-greedy, T+1=4T+1=4time (s)Decay R-MAX, T+1=4T+1=4time (s)η\eta-greedy, T+1=8T+1=8time (s)Decay R-MAX, T+1=8T+1=8time (s)
MultiRoom-N2-S498.6 ± 0.93.399.8 ± 0.52.995.5 ± 0.812100.2 ± 0.713
SimpleCrossingS9N269.9 ± 16.44.697.5 ± 1.35.177.2 ± 13.02299.8 ± 0.339
KeyCorridorS3R197.6 ± 1.84.997.4 ± 1.44.998.3 ± 1.61699.3 ± 0.624
DoorKey-5x595.1 ± 7.16.699.2 ± 0.84.575.8 ± 22.51998.5 ± 1.524
FourRooms95.5 ± 1.26295.5 ± 1.14998.6 ± 1.017599.6 ± 0.4260
Unlock98.7 ± 0.66998.4 ± 0.74199.8 ± 0.121499.8 ± 0.0280
ObstructedMaze-1Dl96.6 ± 0.513495.9 ± 0.97197.0 ± 3.624399.3 ± 0.2298
KeyCorridorS3R275.9 ± 11.314697.4 ± 2.08767.5 ± 22.518699.1 ± 0.8209
Below 9018/800/8020/800/80

Learning score SS (see next comment, 0 = random walker, 100 = Oracle), mean ±\pm 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 (T+1=4,8T+1 = 4, 8), 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, T+1=4,8T+1 = 4, 8). 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.

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

The authors in this paper propose an approximate, efficient method for computing empowerment in Markovian settings. Empowerment is an information-theoretic measure, the maximum mutual information (channel capacity) between a sequence of actions, the intermediate states, and the final state over different possible actions. They propose in a Markovian environment to let the policies probing for these maximum mutual information trajectories depend solely on intermediate states in a Markovian setting. They show a Markovian probing policy is then sufficient. This part comes directly from Tiomkin, Salge and Polani (2025). The resulting policy is computed with Alternating Blahut-Arimoto (ABA).

Critical strengths
  • Interesting, very different approach drawing from empowerment strand of literature.
  • Paper avoids a need to specify rewards which is a huge perk.
  • Problem reduces to a convex optimization problem, which is nice.
  • It is first, to my knowledge, to explore in Markovian closed-loop setting.
Critical weaknesses
  • Method remains exponential in time-horizon, which presumably prevents it from scaling beyond very small settings that they test.
  • Complexity results for polynomial-time per iteration seem standard for tabular learning methods?
  • Several claims appear unfounded. These include the claim that the solution found is unique and can be found via alternating maximization and that the ABA converges to this. They cite Tiomkin et al 2025, which does not provide such a proof and even if it did it considers history-dependent policies. "global convergence to a unique optimal value from any strictly positive initialisation" seems unfounded?
  • In general I would guess there is not a unique optimal policy.
  • Convergence is very slow.
  • Experiments are weak
  • Early stopping tolerance is chosen per environment and horizon as the loosest tolerance where the algorithm stays within START 0.0025 of the exact one. Therefore, when the abstract says they reach this STARC distance, it is because they literally forced this to be the case via oracle. In practice, these parameter values would never be know and would have to be searched over.
  • They never compare ABA against an off-the-shelf convex solver. Similarly, they never compare their approach against either exact or approximate alternatives for the same settings.
  • Many missing citations. Derman and Strauch 1966 and Puterman MDP's 1994 Thm 5.5.1 already establish that a markov representation is sufficient for objectives that depend only on time-T values. So, then there is an unclear contribution compared to Tiomkin et al 2025, since the proof of that markovian reduction and alternative standard solving producing a speedup seems to be the major contribution .
  • Step 1 in their algorithm makes this a convex RL problem on final-step occupancy. This is used by Hazan et al 2019, Zhang et al 2021 ("Variational Policy Gradient Method for Reinforcement Learning with General Utilities"), Moreno et al 2024 ("Efficient Model-Based Concave Utility Reinforcement Learning through Greedy Mirror Descent"), Eysenbach et al 2022 ("The Information Geometry of Unsupervised Reinforcement Learning"). None are cited.
  • General polynomial-time per-iteration dynamic programming algorithms already exist for variants on empowerment. Tiomkin and Tishby 2017, Leibfried et al 2019, Naiss and Permuter 2013. Again none are cited.
  • Practically empowerment seems to be a highly specific subarea. Ideally, the paper should be written in a way to make it more accessible to a broader RL audience.
  • It remains unclear, especially given the exponential time growth and limitation to small environments what the use for empowerment-based formulations would be against convex optimization-based approaches with convex solvers. Similar question on ABA.

Primarily because of the unclear contribution compared to the prior literature, less clear presentation, and small-scale experiments (even accounting for theory), I have to give it a 2. However, the idea is very intriguing and I'd like to see larger examples and/or more clear benchmarking showing the practical benefit. Or, hard theoretical results/complexity results showing why this approach makes sense in theory terms.

Questions for authors
  • How does this work differ from Tiomkin and Tishby 2017, Leibfried et al 2019, Naiss and Permuter 2013?
  • How does it differ from Tiomkin et al 2025 and what is main contribution relative to this? Is it Markovian representation + ABA + Tiomkin et al 2025?
  • Why should the empowerment community care about this result? What makes it important? What about the broader unsupervised or reward-free reinforcement community care about this result?
  • Why is empowerment the appropriate measure of ability to affect the environment. As a point of clarification can you just explain in more detail why capturing this measure via maximum mutual information is natural and/or appropriate. If it had theoretical guarantees of convergence and/or efficiency or similar, I would understand the choice, but lacking those should it be taken as primarily heuristic? Or are there some guarantees/theory backing it? Or practical results against alternatives?
7 comments
AuthorsOpenReview ↗

Answer to Q1: How does this work differ from Tiomkin and Tishby 2017, Leibfried et al 2019, Naiss and Permuter 2013?

We thank reviewer SC8x for its review, we will address this works in the related work section.

Tiomkin & Tishby (2017) derived a Bellman recursion for the directed information from actions to states, maximised as an average rate over an infinite horizon. Leibfried et al. (2019) relate one variant of their operator to that formulation, and also combine it with reward and scale it to deep RL, so we focus the comparison on them. Without reward, their operator maximises cumulative one-step empowerment, ∑tγtI[At;St+1∣St]\sum_t \gamma^t I[A_t; S_{t+1} \mid S_t]. As they note themselves, this focuses on “the cumulative RL setting rather than the non-cumulative setting that is typical for empowerment”, using one-step empowerment as a reference to avoid a multi-step policy. It coincides with process empowerment only for horizon 1, which a single Blahut–Arimoto run already computes.

This quantity is meant as a proxy for empowerment as defined in the literature (Klyubin et al., 2005; Salge et al., 2014; Tiomkin et al., 2025) and the two measure different things. Directed information rewards the number and diversity of state paths the agent can reliably take. Empowerment, both open-loop and process, values the number of distinct states the agent can reliably reach with its actions over a horizon T+1T+1. Process empowerment differs from open-loop empowerment in that the agent can react to the outcome of its actions during the horizon, as agents normally do, and Tiomkin et al. (2025) show it is a more robust measure of influence in stochastic environments.

Leibfried et al. (2019) also give valuable insight into how empowerment-style objectives can guide the learning of RL agents, through their Empowered Actor-Critic (EAC) and Actor-Critic with Intrinsic Empowerment (ACIE). This is beyond the scope of this paper, which focuses on an empowerment measure that is cheap and reliable for use in RL. We will discuss their contribution in the related work, as further motivation for the relevance of empowerment to RL and as future work, and we thank the reviewer for pointing us in this direction.

Naiss & Permuter (2013) extend Blahut–Arimoto to maximise directed information over a finite horizon, the kind of quantity Tiomkin & Tishby (2017) consider, so it is only a related work.

AuthorsOpenReview ↗

Answer to Q2: How does it differ from Tiomkin et al 2025 and what is main contribution relative to this? Is it Markovian representation + ABA + Tiomkin et al 2025?

We again wish to thank reviewer S8Cx for its answers and its dedication.

Tiomkin et al, 2025 introduce process empowerment as a closed-loop generalization of empowerment and show it is better than more widely used open-loop empowerment at measuring the influence an agent has on the environment being more robust to a noisy transition funciton. Together with that they introduce with ABA, a variant of Blahut-Arimoto, to compute process empowerment.

Process empowerment computation with ABA as described by Tiomkin et al, 2025 is exponential in the horizon (denoted by T+1T+1), O((∣S≤T+1(s0)∣∣A∣)T+1)O((|\mathcal{S}_ {\le T+1}(s_0)| |\mathcal{A}|)^{T+1}), with S≤T+1(s0)\mathcal{S}_ {\le T+1}(s_0) is the set of reachable sets from the state s0s_0 for which empowerment is being computed. This makes it impractical at short horizons and untractable at bigger ones. This is further illustrated by experimentation in the baselines provided at the request of reviewer aQ49 (see comment https://openreview.net/forum?id=IrGoukcxc5&noteId=9w2ykFTSnP).

Our contributions are the following:

  1. We show in a Markovian environment Markovian policies suffice to compute process empowerment by maximizing mutual information. This is seen in Proposition 1. We acknowledge this result follows from Derman and Strauch 1966 and Puterman MDP's 1994 Thm 5.5.1. after the decomposition I[ST;S1T,A0T∣s0]=I[ST;ST,AT∣s0]I[S_T; S_1^T, A_0^T|s_0] = I[S_T; S_T, A_T|s_0] is done in our proof's first step. These results were unknown to us, and we will cite them in the text. Even if based in a classical result this is, to the best of our knowledge, the first time it is applied to both process and open-loop empowerment, and allows the optimization problem to be defined over the much lower dimensional space of Markovian policies.
  2. We adapt ABA to optimize over Markovian policies in Markovian environments. With this the cost of computing process empowerment in Markovian environments goes from exponential O((∣S≤T+1(s0)∣∣A∣)T+1)O((|\mathcal{S}_ {\le T+1}(s_0)| |\mathcal{A}|)^{T+1}), to polynomial O(Tb∣S≤T+1(s0)∣∣A∣)O(T b|\mathcal{S}_ {\le T+1}(s_0)| |\mathcal{A}|), with bb being the branching factor of the states in S≤T+1(s0)\mathcal{S}_ {\le T+1}(s_0).
  3. Early-stop and warm-start: we prove in our experimentation that the empowerment value obtained by early stopping Markovian ABA at loose tolerances is nearly interchangeable for its use as a reward in RL. We prove this by showing empowerment computed by early stopping ABA has a low STARC distance to exact empowerment. We finally introduce warm-start which initializes the policies using a predecessor state's policies, this further reduce the time and iterations needed to reach tolerances.

We acknowledge the experimentation backing 3 previously relied on an oracle. We've changed it so that it is no longer the case, new results are available in this answer to reviewer dAt3 (see comment: https://openreview.net/forum?id=IrGoukcxc5&noteId=YQPJMAWuOg), they will be in the final version of the manuscript. In this new experiment, it is seen that empowerment computed by early-stopping at tolerance of 0.1 is interchangeable with that of exact empowerment

Finally, RL experimentation done at request of dAt3 (see comment: https://openreview.net/forum?id=IrGoukcxc5&noteId=h1irlsF9tX) further shows early-stopped empowerment is almost interchangeable with exact empowerment when used as a reward. It is also seen this interchangeability is not affected when using early-stop and a model learnt online to compute empowerment. Finally, this experiment also shows our approximation is cheap enough for RL experimentation. All this further strengthens the usefulness for RL of this work's contribution.

AuthorsOpenReview ↗

Critical Weakneses [1/2]

The authors thank reviewer S8Cx for their effort and suggestions in the review. We would like to address various of the critical weaknesses.

Method remains exponential in time-horizon, which presumably prevents it from scaling beyond very small settings that they test The method is not exponential, its cost per iteration is polynomial as stated in the previous message and further explained in Appendix A. We also added bigger MiniGrid environments, KeyCorridorS3R2 and ObstructedMaze-1Dl, with 28,161 and 18,059 states once expanded with sticky actions to address these concerns. Finally, in the RL experimentation done with reviewer dAt3 we show Markovian ABA with early-stop and warm-start can be used to compute empowerment online learning using empowerment as a reward. In the experiment the agent successfully seeks the states with the highest empowerment while. The longest time per run is around 5 minutes and corresponds to using horizon 8 in ObstructedMaze-1DI. All runs were done in a single CPU thread of a mid-range laptop. This shows that the method scales and is suitable for online learning (which requires recomputing empowerment as the model is learnt), moreover that it can do so for longer horizons.

In general I would guess there is not a unique optimal policy.

We do not claim there is a unique optimal policy, we apologise if at any moment this seems to be the case in the paper. We'll check the text to correct any place where it can seem this is claimed

Early stopping tolerance is chosen per environment and horizon as the loosest tolerance where the algorithm stays within START 0.0025 of the exact one. Therefore, when the abstract says they reach this STARC distance, it is because they literally forced this to be the case via oracle. In practice, these parameter values would never be know and would have to be searched over.

The claim on early-stopping tolerance is indeed a keen assessment. When designing the experimental results, we considered that working with an oracle would better show the convergence times and remove the 'error' component from the table (as using a static convergence of tolerance would need to report both the time to stop and the final error with respect to exact). Nevertheless, we acknowledge that it is more relevant from a practitioners use to forego the oracle and use a tolerance threshold instead (to clarify, it would be the distance between empowerment values across two iterations of the technique). How early-stopped is applied can be seen more clearly in the pseudocode for Markovian ABA with early-stop and warm-start provided at the request of aQ49 https://openreview.net/forum?id=IrGoukcxc5&noteId=hUpA3LnXKd. To address this point of the critical weaknesses and a similar question by reviewer dAt3 we rerun experiments with Markovian ABA early stopping at a fixed tolerance of 0.1, it has been seen the conclusions of the initial experimentation remain valid after switching to a fixed early-stop condition across all settings. All other experiments in the reviews use also tolerance 0.1 for the early-stop. We refer the reviewer to the answer addressing this for a more in depth analysis: https://openreview.net/forum?id=IrGoukcxc5&noteId=YQPJMAWuOg.

They never compare ABA against an off-the-shelf convex solver. Similarly, they never compare their approach against either exact or approximate alternatives for the same settings

At a similar request by reviewer aQ49 we've provided a comparison of our Markovian ABA with warm-start and early-stop (Markovian ABA WS+ES) and our Exact Markovian ABA against the following baselines Clarabel (an off-the shelf convex solver), Blahut Arimoto computing open-loop empowerment and Original Alternating Blahut-Arimoto as described by Tiomkin et al., 2025. A brief assessment is provided here see the experiment at https://openreview.net/forum?id=IrGoukcxc5&noteId=9w2ykFTSnP. Markovian ABA WS+ES outperforms Clarabel with a median speedup of between 170 and 340 depending on the horizon. Moreover, after a peak median speedup at horizon 2, Markovian ABA WS+ES median speedup against Clarabel grows with the horizon (it should still be noted that speedups spread across environments different horizons overlap). Finally, the speedup of Markovian ABA WS+ES against Blahut-Arimoto's and the Original ABA's grows dramatically with the horizon, this is expected taking into account the exponential cost of each of the iterates of Blahut-Arimoto's and the Original ABA. As for Exact Markovian ABA performs much better than Blahut-Arimoto and the Original ABA, and has at least a comparable performance with Clarabel. Note: as stated in the experiment answer open-loop is a different measure of empowerment, however both open-loop and Blahut-Arimoto to compute it are widely present in related works, and so we decided to include them for the time comparison.

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

The paper derives a new algorithm to compute the empowerment. It makes Markovian assumption and is polynomial in the number of states. The algorithm is a modification of Alternating Blahut-Arimoto algorithm, incorporating the Markovian assumption to avoid the exponential dependence on the horizon. It evaluates the algorithm on multiple small MDPs and shows that the early stopping and warm start are especially effective.

Critical strengths

The paper fills a hole in the literature namely computing the empowerment in polynomial time in the number of states building on Blahut-Arimoto algorithm. The empirical results are reasonable and especially effective with early stopping and warm start.

Critical weaknesses

The significance of the paper is not clear for a number of reasons. Most practical MDPs have a large number of states and polynomial in the number of states is only theoretically interesting. Second, the motivation behind computing empowerment is not clear. Solving MDPs does not require computing the empowerment, and there are already effective polytime algorithms for solving MDPs like RMAX and LP. It is not shown, but claimed, how empowerment computation helps explore MDPs better or solve them faster.

The algorithms should be described clearly in pseudocode including the early stopping and warm start.

There are no baselines compared. At the least it should be compared to Blahut-Arimoto. Exponential in planning horizon is not necessarily impractical nor is polynomial in number of states necessarily practical. It all depends on the number of states vs. the planning horizon, which is different in each case and needs empirical demonstration.

Questions for authors

Please give pseudocode for the algorithm.

Can you compare to more baselines?

5 comments
AuthorsOpenReview ↗

Answer to Q1: Please give pseudocode for the algorithm

We wish to thank reviewer aQ49 for their comments and dedication.

The pseudocode for the algorithm can be found below and will be included in an updated version of the manuscript in the following days. We chose the absolute gap between mutual information at consecutive iterations as a stopping criterion as it is a cheap approximation for closeness to the exact empowerment value.

Algorithm 2: Markovian ABA with early stop

Input: initial state s0s_0, Markovian dynamics PP, horizon TT, tolerance δ>0\delta > 0, initial probing policies π(0)={πt(0)}t=0T\pi^{(0)} = \lbrace \pi^{(0)}_t \rbrace_{t=0}^{T} (warm-start by Algorithm 3 or any other st πt(0)>0\pi_t^{(0)} > 0 at all tt, we use uniform policy when we cold-start)

  1. repeat (iteration k=1,2,…k = 1, 2, \dots)
  2.  update Q(s1T,a0T∣s0,sT+1)Q(s_1^T, a_0^T \mid s_0, s_{T+1}) under π(k−1)\pi^{(k-1)}, through the marginals P(st∣s0)P(s_t \mid s_0) for t≤T+1t \le T+1 (one forward pass, Appendix A)
  3.  for every t′t': πt′(k)(at′∣st′)∝exp⁡(EFPR(at′,st′)+EPPR(at′,st′∣s0))\pi^{(k)}_{t'}(a_{t'} \mid s_{t'}) \propto \exp\big(\mathcal{E}^{\mathrm{FPR}}(a_{t'}, s_{t'}) + \mathcal{E}^{\mathrm{PPR}}(a_{t'}, s_{t'} \mid s_0)\big) (one backward pass, Appendix A)
  4. until ∣E(k)(s0)−E(k−1)(s0)∣<δ\big\lvert \mathcal{E}^{(k)}(s_0) - \mathcal{E}^{(k-1)}(s_0) \big\rvert < \delta
  5. Output E(k)(s0)\mathcal{E}^{(k)}(s_0)

where π(k):={πt(k)}t=0T\pi^{(k)} := \lbrace \pi^{(k)}_t \rbrace_{t=0}^{T} is the set of probing policies at iteration kk, πt\pi_t being the one for timestep tt, E(k)(s0):=I[ST+1;S1T,A0T∣s0]\mathcal{E}^{(k)}(s_0) := I[S_{T+1}; S_1^T, A_0^T \mid s_0] under π(k)\pi^{(k)}, and ∝\propto denotes normalization over at′∈Aa_{t'} \in \mathcal{A}, as in Theorem 2.

Algorithm 3: Warm-start initialisation from a predecessor state

Input: state s0s_0, predecessor s−1s_{-1} and its early-stopped probing policies {πtpred}t=0T\lbrace \pi^{\mathrm{pred}}_t \rbrace_{t=0}^{T}, smoothing threshold θ\theta and weight λ\lambda (10−310^{-3} and 0.010.01 in our experiments)

  1. for t=0,…,Tt = 0, \dots, T and every ss reachable from s0s_0 in tt steps do
  2.  if πtpred(⋅∣s)\pi^{\mathrm{pred}}_t(\cdot \mid s) is defined then
  3.   πt(0)(⋅∣s)←πtpred(⋅∣s)\pi^{(0)}_t(\cdot \mid s) \leftarrow \pi^{\mathrm{pred}}_t(\cdot \mid s)
  4.  else if πt′pred(⋅∣s)\pi^{\mathrm{pred}}_{t'}(\cdot \mid s) is defined for some t′≠tt' \neq t then
  5.   πt(0)(⋅∣s)←πt⋆pred(⋅∣s)\pi^{(0)}_t(\cdot \mid s) \leftarrow \pi^{\mathrm{pred}}_{t^\star}(\cdot \mid s), with t⋆t^\star the nearest such t′t' and the later one on ties (usually t⋆=t+1t^\star = t+1)
  6.  else
  7.   πt(0)(⋅∣s)←\pi^{(0)}_t(\cdot \mid s) \leftarrow uniform over A\mathcal{A}
  8.  end if
  9.  if min⁡aπt(0)(a∣s)<θ\min_a \pi^{(0)}_t(a \mid s) < \theta then
  10.   πt(0)(a∣s)←(πt(0)(a∣s)+λ)/(1+∣A∣λ)\pi^{(0)}_t(a \mid s) \leftarrow \big(\pi^{(0)}_t(a \mid s) + \lambda\big) / \big(1 + |\mathcal{A}| \lambda\big) (Laplace smoothing)
  11.  end if
  12. end for
  13. Output {πt(0)}t=0T\lbrace \pi^{(0)}_t \rbrace_{t=0}^{T}

where πtpred(⋅∣s)\pi^{\mathrm{pred}}_t(\cdot \mid s) is defined when ss is reachable from s−1s_{-1} in tt steps with positive probability under {πtpred}t=0T\lbrace \pi^{\mathrm{pred}}_t \rbrace_{t=0}^{T}.

This algorithm guarantees a warm start for all policies at all states at timesteps 0 to T−1T-1, because any state reachable from s0s_0 in tt steps is reachable from its predecessor in t+1t+1 steps. At timestep TT, states the predecessor never reached at any timestep fall back to uniform.

AuthorsOpenReview ↗

Answer to critical weakness [1/2]

The paper's aim is not to solve MDPs, is to show that empowerment can be computed in polynomial time with ABA for Markovian empowerments, not only that but by stopping ABA at loose tolerances and warm-starting. This makes future research on empowerment. Additionally, in the experiment run for the answer to reviewer dAt3 (further details in the following comment: https://openreview.net/forum?id=IrGoukcxc5&noteId=h1irlsF9tX) we show our method is suitable for use in RL seeking the regions with the highest empowerment at the same time that the transition function is learnt.

Regarding practical MDPs having many states, it should be remarked ABA is polynomial in the number of reachable states from the state for which empowerment is computed, not with respect to the total size of state space, therefore it only needs local information and its complexity is just dependent on the local structure of the environment, locality is a general property of empowerment (both process empowerment and classical open-loop). An expanded and detailed reasoning is available below:

Specifically, the time complexity per iteration for the Markovian ABA variant is O(Tb∣S≤T+1(s0)∣∣A∣)O(T b|\mathcal{S}_ {\le T+1}(s_0)| |\mathcal{A}|) with bb being the branching factor of the states in the reachable set S≤T+1(s0)\mathcal{S}_ {\le T+1}(s_0) compared to the original non-Markovian ABA algorithm by Tiomkin et al 2025 which is exponential in horizon (denoted by T+1T+1), O((∣S≤T+1(s0)∣∣A∣)T+1)O((|\mathcal{S}_ {\le T+1}(s_0)| |\mathcal{A}|)^{T+1}). The difference lies in how the policy update is evaluated. In the original non-Markovian ABA, the posterior QQ and the terms ENMFPR\mathcal{E}^{\mathrm{FPR}}_ {\mathrm{NM}} and ENMPPR\mathcal{E}^{\mathrm{PPR}}_ {\mathrm{NM}} are sums over every trajectory of length T+1T+1. Under Markovian dynamics, both are evaluated with one forward and one backward pass over the reachable states, akin to policy evaluation, which gives the polynomial cost (Appendix A). Markovian ABA is never costlier than the original one, up to a constant factor, whatever the number of states and the horizon. The original ABA sums over every trajectory, while our variant visits each reachable state once per timestep, and every reachable state lies on at least one trajectory. When several trajectories pass through the same state, the original ABA processes that state once for each trajectory, while our variant processes it once. This happens from horizon 2 onwards, whenever different paths lead to the same state. The two costs are of the same order only when trajectories almost never meet, which is not the common case. Additionally, early-stop and warm-start reduce the number of iterations needed to have approximations nearly interchangeable with exact values for its use in RL. Additional baselines on experimentation our method will soon be provided.

AuthorsOpenReview ↗

Answer to critical weakneses [2/2]

We again wish to thank reviewer aQ49 for their reviews.

We reproduce with slight adaptation the answer to reviewer dAt3 on the claim that empowerment helps explore MDPs:

This paper is about how to compute and approximate empowerment in a cheap way that later allow for it to be useful in the context of RL. The use of empowerment for exploration is out of scope for this paper and is deemed as future work. After reviewing the manuscript we acknowledge two phrases in the introduction and in the discussion may lead to think this paper promises to show empowerment is useful for exploration. We will rework them so that this cannot be read from them.

In addition, the RL experiment done at reviewer dAt3's request (further details in the following comment: https://openreview.net/forum?id=IrGoukcxc5&noteId=h1irlsF9tX) shows it is possible to use our Markovian ABA with warm-start and early-stop to train RL agents while learning a model online and using empowerment as an intrinsic reward. Tiomkin et al. (2025) show that greedily maximizing process empowerment, the quantity we compute, yields robust behaviour in noisy and adversarial gridworlds, outperforming open-loop empowerment. Beyond this, pre-training on multi-step empowerment makes later learning in gridworlds more data-efficient, especially for longer horizons (Schneider et al., 2025). Leibfried et al. (2019), using a proxy of empowerment, show that it helps in early learning when combined with extrinsic rewards. Volpi & Polani (2023) study agents that maximize empowerment while pursuing an extrinsic goal. Also, and empowerment has driven meaningful behaviour in robotic manipulation with sparse rewards (Dai et al., 2023). This research is currently constrained by the cost of computing empowerment, leaving them to use proxies of it, very short horizons or deterministic environments (in which the computation of empowerment reduces to the logarithm of the number of reachable states in the chosen horizon).

Our method contributes to this area of research by providing a way to approximate empowerment that is efficient, as useful as exact empowerment and suitable for RL (as shown by experimentation in the paper and in the RL experiment done at dAt3's request), this enables further research into the uses of empowerment in RL, however, these are left as future work.

References:

Felix Leibfried, Sergio Pascual-Díaz, and Jordi Grau-Moya. A unified Bellman optimality principle combining reward maximization and empowerment. In Advances in Neural Information Processing Systems, volume 32, 2019. URL https://proceedings.neurips.cc/paper_files/paper/2019/file/13384ffc9d8bdb21c53c6f72d46f7866-Paper.pdf

Moritz Schneider, Robert Krug, Narunas Vaskevicius, Luigi Palmieri, Michael Volpp, and Joschka Boedecker. Information-theoretic policy pre-training with empowerment. arXiv preprint arXiv:2510.05996, 2025. URL https://arxiv.org/abs/2510.05996

Siyu Dai, Wei Xu, Andreas Hofmann, and Brian Williams. An empowerment-based solution to robotic manipulation tasks with sparse rewards. Autonomous Robots, 47:617–633, 2023. URL https://doi.org/10.1007/s10514-023-10087-8

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.