acceptodds
Under review as a conference paper at ICLR 2027

Compressing What an Agent Can Steer: Control-Aware Structural Entropy

Abstract

A state abstraction for reinforcement learning should preserve what the agent can control, yet reward-free codelength objectives for compressing transition graphs score how predictable the dynamics are once actions are averaged out, not how far an agent can steer them. We prove that this gap is structural for structural entropy (SE), a random-walk codelength used to build hierarchical state abstractions: the SE codelength of a Markov decision process under any encoding tree is a function of the action-marginalised kernel alone, so no SE variant computed from the passive chain can distinguish two MDPs that differ only in their action-conditioned structure. We then define the minimal repair: the control gain at resolution , , the codelength saved when the block-level code may condition on actions. At the finest partition it equals stationary-averaged uniform-prior empowerment (exactly Klyubin–Salge empowerment in balanced deterministic MDPs), and it is monotone under coarsening. Each estimate is calibrated against a matched null, a within-state action shuffle that preserves the passive chain and all per-state action marginals exactly. On tabular MDP families where controllability is a construction knob independent of connectivity, the calibrated estimator recovers the constructed gain to  0.015 bits (Spearman , , in both families), while effective rank is blind where the passive chain is fixed (); the passive SE baseline breached its preregistered blindness threshold (, ), which a post-hoc 100-run extension attributes to sampling noise. In quotient planning on a checkerboard-inversion gridworld (gate failed) no reward-free partition objective we tested — passive, action-conditioned, or profile consistency — reliably yields plannable quotients, although plan-preserving partitions exist and the control-aware objective found one (retained 0.95 of optimal return, in 1 of 15 cells). On 15 learned agents both exploratory predictions hold in sign but not significantly. All gates and verdicts are reported verbatim.

Primary area:
reinforcement learning
Keywords:
structural entropy, empowerment, state abstraction, controllability, Markov decision processes, information theory

Reviews

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

The paper studies reward-free compression for state abstaction in RL. Specifically, they prove that passive structural entropy cannot distinguish different MDPs but with identical dynamics under action averaging. To address the limitation, they introduces control gain to measure the action identifiability. They also proposed to use action condition-code length as criteria for state aggregation.

The experiment show that the proposed control gain indeed distinguish what preivous method cannot. However, the rest of experiment results inconclusive.

Critical strengths
  1. I appreciate that the authors are open about the reuslts that did not work well. The learned-agent study is described as inconclusive. Post-hoc analyses are clearly labelled. I find the level of transparency unusual and is of high standard.

  2. The paper identifies a real limitation of passive structural entropy and illustrated with clear arugment and examples.

Critical weaknesses
  1. The novelty relative to existing action-information based method need to be better justified. The idea of using action uncertainty or information gain is not novel.

  2. Downstream usefulness is not established. According to the exmperiments, the action-conditioned codelength objective does not reliably produce planning-preserving partitions.

  3. Practical scalability is not established for the implemented estimator and partition search. The envs used in experiments are simple with specifically designed MDP. It is not clear how this idea can scale into more realistic settings.

Questions for authors

What is the main new insight beyond existing action-conditioned mutual information and empowerment measures, particularly Seitzer et al.’s uniform-policy causal influence measure?

Given the unsuccessful abstraction-planning test and inconclusive learned-agent study, what useful role for the diagnostic is established by the current results?

1 comment
AuthorsOpenReview ↗

Response to Reviewer oRge: what is new beyond known action-information measures, and what use the paper shows

Thank you for the review. We agree with all three weaknesses.

Q1 and W1: what is new beyond action-conditioned mutual information and empowerment, in particular Seitzer et al. The information quantity is not new. For one state, our control gain is the mutual information between the action and the next state under uniformly random actions. Seitzer et al. (NeurIPS 2021) define this conditional mutual information for a state and one component of the next state, also under uniform actions, estimate it with a learned model, and use it to improve exploration and off-policy learning on robotic manipulation tasks. We did not cite them and should have. The link to empowerment, which Seitzer et al. also note for their measure, is Proposition 2: the quantity is a lower bound on empowerment averaged over the stationary state distribution, with equality when uniform actions achieve the channel capacity.

So what is new in the paper is not the measure. What is specific to the paper is a statement about structural entropy: its codelength for an MDP, under any encoding tree, depends only on the action-averaged transition kernel (Proposition 1). It cannot tell apart two MDPs that have the same averaged kernel, however differently their actions select successors. Beyond that the paper contains two things:

  1. The same quantity read for a partition, I(A;m(S′)∣m(S))I(A; m(S') \mid m(S)), where m(s)m(s) is the block of state ss: the bits a two-level code saves when it may condition on the action. Merging blocks cannot increase it (Proposition 4).
  2. A within-state permutation null for the estimate: shuffling the action labels within each state leaves the action-averaged chain unchanged and gives the estimator's value when the action has no effect (0.012 and 0.022 bits in the two families of MDPs used to test the estimate, of 36 and 40 states; Section 5.1). We subtract it, and the paper calls the result the calibrated estimate.

Q2 and W2: what useful role is established. Only measurement, and only on small constructed MDPs. Where the true value is known, the calibrated estimate, with every state as its own block, matches it: at each of the five settings per family (ff in the paper) the mean estimate is within about 0.015 bits of the true value. A use for choosing abstractions is not established, as you say. In the planning test, partitions chosen with the action-aware code beat partitions chosen with the action-blind code in at most 2 of 5 seeds at each partition size (1 of 5 when ties are not counted). Across all 45 partitions (these two codes and a third objective added afterwards; three sizes; five seeds; a post-hoc analysis), the action information a partition keeps is not significantly related to the return it keeps (rank correlation 0.17, p = 0.26; Section 5.2). Across 15 trained agents, the rank correlation between the calibrated estimate and planning success is 0.18 (p = 0.54; Section 5.3).

W3: scale. Agreed. Every positive result is on a tabular MDP of at most 40 states, built for the purpose. The one continuous case reduces the latent space to 40 clusters and the actions to four bins; there the calibrated values are −0.004 to 0.006 bits, above twice the null's standard deviation for 2 of the 15 agents. The paper does not show that the estimator or the partition search works at a realistic scale (Section 7).

Three points of our own. First, the caption of Figure 1 says "Averaged over any fixed behaviour policy the two are the same Markov chain", and the label inside the figure implies the same. That holds for uniformly random actions, which the experiments use (Section 2), not for an arbitrary policy. Proposition 1 is stated for a given averaged kernel and is not affected. Second, Section 5.1 says that subtracting the null "removes that offset at every f", and Remark 1 calls the estimator "biased upward". Table 3 (Appendix B) shows that the subtraction moves the mean estimate closer to the true value at seven of the ten settings and further from it at the three highest settings of the 36-state family, where there was no upward offset to remove. With every state controllable, the true value is 2 bits, the uncalibrated estimate is 1.996 and the calibrated one 1.985. That setting is where the 0.015 bits above comes from. Third, not an error: the rank correlation of 0.98 in the abstract is the largest value that 25 runs at five tied settings can give, so it shows only that the estimates at different settings never overlap.

We have not uploaded a revised PDF.

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

The paper proposes a "control gain," I(A; m(S') | m(S)), as an action-aware replacement for structural entropy in reward-free state abstraction. On small constructed MDPs, the estimate tracks the constructed controllability. In planning experiments, the method does not produce useful abstractions.

Critical strengths

The problem is important. Abstraction is central to efficient solution of large MDPs. The paper reports its negative results honestly.

Critical weaknesses
  1. Contribution is unclear. State abstraction is very well studied (bisimulation, MDP homomorphisms, abstraction-refinement in formal verification). The paper does not say what it adds. The main quantity is also known: Seitzer et al. (NeurIPS 2021) and InfoPower (ICLR 2022) use the same conditional mutual information, InfoPower as a representation objective. Information-theoretic Markov aggregation (Geiger et al.) is also missing. A short literature search finds all of this work, so the omission is a significant gap. The propositions follow directly from the chain rule and data processing.
  2. Experiments are synthetic and do not show a benefit. The positive results use 36- and 40-state MDPs built to vary the measured quantity. The planning experiment failed, and the learned-agent results are not significant. No experiment shows a task where the method helps.
  3. Writing is hard to follow. The paper uses terms before it defines them ("block," "fibre," "lifted block policy"). Its experiment vocabulary ("gates," "arms," "verdicts reported verbatim") makes the results section difficult to read. A plain statement of each hypothesis and its result would be clearer.
Questions for authors
  1. What does this quantity give that Seitzer et al. or InfoPower do not?
  2. Is there a task where the control gain improves abstraction over a reward-aware baseline such as approximate bisimulation?
1 comment
AuthorsOpenReview ↗

Response to Reviewer pBm6: the quantity is known, three works are missing, and no task in the paper shows a benefit

Thank you for the review. Short answers first: the quantity is known, the three works you name should have been cited, and no task in the paper shows the control gain improving an abstraction.

W1 and Q1: what the quantity gives beyond Seitzer et al. and InfoPower. As an information measure, nothing new. For one state it is the mutual information between the action and the next state under uniform actions. Seitzer et al. (NeurIPS 2021) define that quantity for a state and one component of the next state, under uniform actions, and estimate it with a learned model. InfoPower (ICLR 2022) uses a variational bound on the same form, I(At−1;Zt∣Zt−1)I(A_{t-1}; Z_t \mid Z_{t-1}), on learned latents, in its representation objective. Geiger et al. (IEEE TAC, 2015, which we take to be the work you mean) score a partition of a Markov chain, with no actions, by a Kullback-Leibler cost: in our terms, an action-blind objective. We cited none of the three, which is a gap in our literature review.

What the paper contains beyond the quantity is three things: (i) the consequence for structural entropy: its codelength for an MDP depends only on the action-averaged kernel, so it cannot tell apart two MDPs with the same averaged kernel, however differently their actions select successors (Proposition 1); (ii) for a discrete partition, the reading of the quantity as the bits a two-level code saves when it may condition on the action, which merging blocks cannot increase (Definition 1, Proposition 4); (iii) a null for the estimate: action labels shuffled within each state, which keeps the action-averaged chain exactly and gives the estimator's value when the action has no effect. Subtracting it gives the paper's calibrated estimate. You are right about the propositions: each proof in Section 3 is a few lines, and Propositions 2 and 4 rest on the chain rule and data processing. Against the state-abstraction literature you list, the paper shows no abstraction method that works. The closest objective it tests is a reward-free homomorphism-style score of our own, added post hoc, which also failed (Section 5.2). It cites bisimulation and MDP homomorphisms, not abstraction refinement from formal verification.

W2 and Q2: is there a task where the control gain improves an abstraction over a reward-aware baseline? No: the paper has no comparison with a reward-aware baseline. Two reward-aware objectives (one-step bisimulation and Q∗Q^*-consistency) were specified after the planning test. We have no results for them; Section 7 says only that they are "not reported here".

W3: writing. Agreed, including the experiment vocabulary. A plain statement of the main hypotheses and their results:

  • The estimate recovers a value built into small MDPs of 36 and 40 states, at five settings each. Yes: at every setting the mean estimate is within about 0.015 bits of the true value (Section 5.1).
  • Measures of the action-averaged chain do not move in the 36-state family, where that chain is the same at every setting. Effective rank did not. The structural-entropy baseline gave a rank correlation with the setting of 0.34 (p = 0.10), above our preset limit of 0.3, so this test failed as stated; over 125 runs, 100 of them added post hoc, it is 0.027 (p = 0.76).
  • Partitions chosen with the action-aware code plan better than those chosen with the action-blind code. No: better in at most 2 of 5 seeds at each partition size, 1 of 5 when ties are not counted (Section 5.2).
  • The estimate goes with planning success across 15 trained agents. Not significant (rank correlation 0.18, p = 0.54; Section 5.3).

The three terms you list are never defined in the paper:

  • Block. A partition assigns every state to one of KK groups. Each group is a block; m(s)m(s) is the block of state ss.
  • Fibre (Proposition 3, deterministic transitions). For a state ss and one of its successors s′s', the set of actions that lead from ss to s′s'. Fibres are balanced when every reachable successor is reached by the same number of actions.
  • Lifted block policy. Plan on the small MDP whose states are the blocks, which gives one action per block; every state then takes the action of its block.

Two corrections of our own. The caption of Figure 1 says "Averaged over any fixed behaviour policy the two are the same Markov chain"; that holds for uniform actions, which the experiments use, not for an arbitrary policy, and Proposition 1 is not affected. Section 5.1 says subtracting the null "removes that offset at every f" (ff is the setting); Table 3 (Appendix B) shows it moves the mean estimate closer to the true value at seven of the ten settings and further from it at the three highest settings of the 36-state family (with every state controllable: true value 2 bits, uncalibrated 1.996, calibrated 1.985).

We have not uploaded a revised PDF.

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

This paper considers the problem of controllable state abstractions in reinforcement learning.

Critical strengths

The problem considered is relevant in the RL community.

Critical weaknesses

The exposition is extremely opaque, making the paper almost unreadable and the results impossible to interpret. There are many critical undefined components (e.g. structural entropy is never defined), non-standard acronyms used throughout, and no formal problem statement is given. There is essentially no commentary around the stated results, making them almost impossible to interpret.

Given the state of the writing, I am unable to evaluate the technical quality or significance of the results.

Questions for authors

None.

1 comment
AuthorsOpenReview ↗

Response to Reviewer Z8zC: the missing definition of structural entropy, a problem statement, and the results in plain terms

Thank you for the review. You are right about the exposition. Below is what the paper should have contained.

Structural entropy is not defined. Correct. The paper describes it in words and cites Li and Pan (2016), but never writes it down. Take a Markov chain with transition matrix PP and stationary distribution π\pi, and a partition of its states into blocks BB. Let VB=∑s∈BπsV_B = \sum_{s \in B} \pi_s be the weight of block BB and gB=∑s∈Bπs∑s′∉BP(s′∣s)g_B = \sum_{s \in B} \pi_s \sum_{s' \notin B} P(s' \mid s) the stationary flow that leaves it, which equals the flow that enters it. The two-level structural entropy is

H2=−∑B[∑s∈Bπslog⁡2(πs/VB)+gBlog⁡2VB].H^2 = -\sum_B \Big[ \sum_{s \in B} \pi_s \log_2 (\pi_s / V_B) + g_B \log_2 V_B \Big].

It is the average number of bits to name the next state of a random walk when the code names the state within its block, and the block only when the walk enters a new one. This is Li and Pan's formula with stationary probabilities in place of degrees, as Section 2 says. An encoding tree is a hierarchy of such partitions; none of our experiments uses more than two levels. The one-level version is H1=−∑sπslog⁡2πsH^1 = -\sum_s \pi_s \log_2 \pi_s, and what the paper calls "structural information" (SI) is H1−H2H^1 - H^2, the bits the partition saves. Section 2 glosses SI as "the two-level structural information (SE)"; the number computed is this difference.

The baseline of Section 5.1 is SI for a partition found by greedy search, minus the mean of the same score on five randomly rewired chains. The partition objectives of Section 5.2 use a second form (Definition 1). Write m(s)m(s) for the block of state ss, and SS, AA, S′S' for the state, the action and the next state when actions are chosen uniformly at random. The action-blind code is H(m(S′)∣m(S))+∑BVBH(π⋅∣B)H(m(S') \mid m(S)) + \sum_B V_B H(\pi_{\cdot \mid B}): the bits to name the next block given the current one, plus the bits to name the state inside its block. The action-aware code replaces the first term by H(m(S′)∣m(S),A)H(m(S') \mid m(S), A). The paper notes that Proposition 1 covers H2H^2 and the action-blind code alike.

No formal problem statement. The setting is a finite MDP with a set of states, a set of actions and transitions P(s′∣s,a)P(s' \mid s, a), explored with uniformly random actions, and a partition mm of the states into KK blocks. Averaging over actions gives a Markov chain Pu(s′∣s)P_u(s' \mid s), the mean of P(s′∣s,a)P(s' \mid s, a) over aa. The paper asks three questions:

  1. Can a structural-entropy score of mm tell apart two MDPs that have the same PuP_u but differ in how their actions select successors?
  2. How many bits does the action add about the next block, I(A;m(S′)∣m(S))I(A; m(S') \mid m(S)) (the paper's "control gain"), and can this be estimated from a rollout (a recorded run of random actions)?
  3. Does choosing mm with the action-aware code give a partition that keeps the return of planning? We plan on the MDP whose states are the blocks, give every state the action of its block, and report the share of the optimal policy's advantage over a random policy that is kept.

The results in plain terms.

  1. No: the score is a function of PuP_u alone (Proposition 1; the proof is a few lines). In Figure 1 the two states have the same PuP_u, but the action decides the successor in one (2 bits) and not in the other (0 bits).
  2. With every state as its own block, on small MDPs built with a known answer, the mean estimate (after subtracting its value under shuffled action labels) is within about 0.015 bits of the true value at every setting (two families, five settings each; Section 5.1). For coarser partitions the paper has no such check. Propositions 2 to 4 say that, with every state as its own block, the quantity is a lower bound on empowerment (the most information the action can carry about the next state) averaged over states, equal to it in the deterministic case when every reachable next state is reached by the same number of actions; and that merging blocks cannot increase the quantity.
  3. No. Partitions chosen with the action-aware code did not plan better than partitions chosen with the action-blind code: they were better in at most 2 of 5 seeds at each partition size (1 of 5 when ties are not counted). Of the 45 partitions (these two codes and a third objective added afterwards; three sizes; five seeds), only one kept more than a quarter of the optimal policy's advantage over a random policy (it kept 0.95), and most were at the level of the random policy (Section 5.2).

A separate check, whether the estimate goes with planning success across 15 trained agents, was not significant (rank correlation 0.18, p = 0.54; Section 5.3).

Acronyms and labels. SE is structural entropy and SI is structural information, as above. F1 to F3 name three families of test MDPs, and G1 to G6 name the six tests listed in Table 1. These labels are ours and carry no meaning for a reader. They should not have been in the paper.

We have not uploaded a revised PDF.

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

The paper identifies a weakness of structural entropy, that it does not take into account the actions available to an agent. They provide a definition of control gain, that defines the information lost from throwing away actions in structural entropy methods. I believe they try to use this to select partitions for quotient planning but showed no gain in performance.

Critical strengths

Throwing away actions when abstracting MDPs does indeed miss useful information about the MDP and they provide a metric that measures how much information is lost.

Critical weaknesses

I am very bullish on using AI to accelerate research but I do believe the results of AI accelerated research should be fit for human consumption and I don't think this paper is. Labelling experiment "gates" with letters and numbers (e.g F1) is convenient for agents to keep track of experiments but it is very hard for humans to remember what the different experiment symbols correspond to.

The paper reads like the output of a Claude auto-research session - which I personally think is a reasonable way to do research, it just need to be presented in a way that is human readable. I think asking Claude to rewrite the paper in the style of an ICLR paper would improve the readability for humans but even then I think writing the portions of the paper yourself would be preferable. For example, I would not put gate failed in an abstract (nor do I think any human would?).

For example, figure 3, what is F1 and F2? I can go back and look at the text but why not just label the axes with human understandable terms.

With its current presentation, it is difficulty for me to understand the theory behind the paper and the experimental results.

Questions for authors

Can you define partition and blocks? I know these terms from other papers but a definition would make this paper easier to understand.

Can we define fibres?

1 comment
AuthorsOpenReview ↗

Response to Reviewer d4E5: partition, block and fibre defined; what F1 and F2 are in Figure 3; the labels

Thank you for the review. You are right about the presentation, and your two questions have short answers.

Can you define partition and blocks? A partition splits the set of states into KK non-overlapping groups, so that every state belongs to exactly one group. Each group is a block, and m(s)m(s) is the block that contains state ss. Example: a 6×6 grid has 36 states, and cutting it into nine 2×2 squares is a partition with nine blocks. A state abstraction, in this paper, is such a partition: the agent plans as if all states in a block were one state.

Can we define fibres? Take one state ss in an MDP with deterministic transitions, and one state s′s' that can be reached from it in a step. The fibre of s′s' is the set of actions that lead from ss to s′s'. Example: with four actions, if "up" and "left" both lead to the same cell, that cell's fibre has size 2. Fibres are balanced when every reachable next state is reached by the same number of actions. Proposition 3 says that when this holds at every state, the control gain (the paper's measure: the bits the action adds about the next state) equals empowerment (the most information the action can carry about the next state), averaged over states.

Figure 3: what are F1 and F2? They are our names for two families of small test MDPs (Section 4), and the figure should have said so. F1 (top row) is a 6×6 grid that wraps around at the edges. In a fraction ff of its states, each of the four actions moves to its own neighbouring cell. In the other states, every action moves to a random neighbour. So ff is the share of states the agent can control, and the true value of the control gain is 2f2f bits. F2 (bottom row) is a family of random 40-state MDPs in which ff sets how much the next state depends on the action. The horizontal axis "knob ff" is this ff. The left column is the control gain minus the value it takes when the action labels are shuffled ("− null"); the dashed line is the true value. The middle column is the structural-entropy baseline ("plain SI"), also shown minus a null, here its value on randomly rewired chains. The right column is effective rank, an effective number of singular values of the action-averaged transition matrix. The middle and right columns see only the chain with the actions averaged out. Thin lines are the five seeds.

The theory and the results in plain terms. Theory: once actions are averaged out, a state where the action decides what happens next can look exactly like a state where it does not (Figure 1), and then no score computed from the averaged chain can tell them apart. Results: on small MDPs with a known answer the estimate is accurate. At every setting of ff the mean estimate is within about 0.015 bits of the true value. When we chose partitions with a score that uses the action, they did not plan better than partitions chosen with a score that ignores it, which you read correctly. A separate check, whether the estimate goes with planning success across 15 trained agents, was not significant.

Labels and "gate failed". Agreed. "Gate" is our word for one of the six tests in Table 1, each with a stated criterion, and the letter-number labels (F1 to F3, G1 to G6) are bookkeeping that a reader should not have to decode. "Gate failed" does not belong in an abstract. What it stood for is the planning result above.

AI use. AI tools were used throughout the work, including to draft parts of the paper, as its AI Use Statement lists. The paper as submitted is our responsibility, labels and abstract included, and the criticism is fair.

We have not uploaded a revised PDF.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.