1 Introduction↩︎

Good control rarely requires tracking every detail of the environment [1]–[4]. For instance, task-irrelevant symmetries can be factored away without hindering the ability of a reinforcement-learning agent to find an optimal policy [5], [6]. More generally, useful abstractions act like sufficient statistics: they preserve what matters the most and discard distinctions whose effects are unimportant.

But how should an agent decide what information to keep and which to discard? Classical abstraction theory gives exact answers to this question in special cases. State bisimulation and MDP homomorphisms identify states that are perfectly equivalent from a planning perspective [5], [7], [8]. Bisimulation metrics extend these conditions to quasi-symmetry and almost-bisimilarity providing quantitative performance guarantees [9]–[12]. These ideas are closely related to lossy compression, which has been formally studied under rate-distortion theory [13] and the information bottleneck method [14].

While the literature offers a rich account of how to build abstractions, comparatively little is known about how to adjust their granularity during learning. Existing adaptive methods refine abstractions based on the distinguishability of transition estimates or the discovery of verification counterexamples [15]–[18]. However, to my knowledge, no existing adaptive method handles state-action abstraction jointly. This is not an incidental restriction: state aggregation can factor invariances (i.e., distinctions that do not matter) but fails to capture equivariances, in which the same behavioural function carries different action labels depending on the context [6], [11]. Equivariance is often the rule rather than the exception — for instance, in bilateral locomotion the action that functions as ‘advance the free leg’ maps to a right-leg command when the left leg is planted, and to a left-leg command when the right leg is planted.

This paper introduces a formal framework to dynamically adjust the resolution of state-action abstractions. Our central technical result is a value-error decomposition that splits the total error into a Bellman residual measuring how well the current abstract problem has been solved, and an abstraction error bounded by a bisimulation metric. The decomposition motivates a simple adaptive rule: switch to a finer abstraction as soon as the Bellman residual reaches the scale of the abstraction error. We formalise this rule by building a continuous family of soft abstractions through rate-distortion, indexed by a temperature parameter that controls resolution. We validate the framework on classic tabular control benchmarks and a SysAdmin [19] scaling test. Results show that the adaptive rule traces meaningful compression-distortion frontiers and achieves near-optimal performance under substantial state and action compression. The framework further reveals whether state, action, or joint state-action information is the binding constraint on performance for a given task.

Together, these findings yield an adaptive method that refines abstractions only as far as a task requires, and in doing so quantifies how much state and action information that task actually contains. Overall, the main contributions are:

• Soft state-action abstractions. A stochastic generalisation of MDP homomorphisms, equipped with bisimulation metrics that compare state-action pairs.

• A learning-abstraction decomposition. A control certificate that decomposes value error into a Bellman residual within the abstraction and bisimulation distortion of the abstraction itself.

• The adaptive abstraction principle. A refinement rule that ties abstraction granularity to learning progress — refine only when the residual within the current abstraction reaches the scale of the abstraction error.

• State-action abstraction built from rate-distortion principles. A continuous family of soft abstractions in which the information allocated to states and actions is independently controllable.

• A decomposition of task compressibility. The separable rates make it possible to attribute a task’s compressibility to its states, actions, or their interaction.

2 Related Work↩︎

2.0.0.1 Bisimulation and MDP homomorphisms.

Abstractions have been studied via state bisimulation [7] and MDP homomorphisms [5], which give exact conditions under which the value function of a reduced MDP can be lifted to the original one [8]. These ideas have been used to build state-action abstractions that account for equivariant symmetries [6] and have been combined with the options framework [20]. This work extends MDP homomorphisms [5], [6] from hard state-action abstractions based on coarse-grainings to soft abstractions based on stochastic encoders and decoders, whose granularity is dynamically adjusted during planning.

2.0.0.2 Bisimulation metrics.

Work on approximate abstraction generalises exact bisimulation, allowing quantitative error and providing performance bounds [11], [12], [21]. [9] introduced state bisimulation pseudometrics as quantitative relaxations of exact bisimulation (see also [22]). Approximate homomorphism and lax bisimulation-style metrics extend this by comparing actions through matchings rather than fixed labels [11], [23]. A survey on abstraction guarantees and approximation-estimation tradeoffs can be found in [24]. Also, policy-conditioned relaxations [23], [25], [26] enable ways to account for equivalence during behaviour. In deep RL, bisimulation-inspired losses are often optimised from samples [27]–[31]. Our work extends bisimulation metrics to soft state-action abstractions, allowing stochastic encoders to compress ‘quasi-equivariant’ relationships.

2.0.0.3 Information-theoretic compression.

[32] formulate state abstraction as lossy compression in apprenticeship learning, and use a Blahut–Arimoto scheme to solve the resulting rate-distortion problem; [33] use a variational information bottleneck over state-action pairs to learn discrete state abstractions; and [34] distil policies into variational MDP abstractions. Related work studies deterministic bottlenecks [35], bottleneck regularisation for exploration and transfer [36]–[38], and variational objectives whose optima recover bisimulation relations [39]. More generally, information-theoretic principles have been used to ask what an agent should learn [40]–[44], and bounded-rational control has studied related tradeoffs between information and reward [45]–[47]. Our framework builds abstractions using the rate-distortion principle while introducing key differences in the object and the distortion: it compresses state-action control structure rather than only states, and uses bisimulation metrics as distortion rather than expert demonstration.

2.0.0.4 Adaptive refinement.

Incremental abstraction takes place during partition refinement when computing bisimulation quotients [7], as well as in earlier model-reduction heuristics [48], but this has not been used for online calibration. [15] has studied online state aggregation based on statistical uncertainty about rewards and transitions during learning. Methods such as CEGAR [16], data-driven bisimulation learning [17], and multi-resolution bisimulation constructions [18] also refine abstractions when a behavioural or verification condition fails. Our refinement procedure is qualitatively different: we refine neither based on transition estimates nor on verification counterexamples, but instead focus on whether the Bellman residual of the abstract planner reaches the error induced by the abstraction.

3 Soft state-action abstractions↩︎

Consider a MDP \((\mathcal{S},\mathcal{A},P,r,\gamma)\), with finite state space \(\mathcal{S}\), finite action space \(\mathcal{A}\), transition kernel \(P(s'|s,a)\), reward \(r(s,a)\), and discount factor \(\gamma\in[0,1)\) [49]. For a bounded value function \(V:\mathcal{S}\to\mathbb{R}\), the one-step backup operator is \[(BV)(s,a) := r(s,a)+\gamma\mathbb{E}_{s'\sim P(\cdot\mid s,a)}\big[V(s')\big]. \label{eq:b-backup}\tag{1}\] The Bellman optimality operator is \((TV)(s):=\max_{a\in\mathcal{A}}(BV)(s,a)\).

In many situations the MDP may be too hard to solve directly. A common way to simplify the problem is to compress states, actions, or state-action pairs via coarse-graining mappings. Instead, here we consider a more general approach based on stochastic coarse-grainings specified by \[\begin{align} \nu_S:\mathcal{S}\to\Delta(\bar{\mathcal{S}}) \quad\text{(state encoder),}\quad \nu_A:\mathcal{S}\times\mathcal{A}\to\Delta(\bar{\mathcal{A}}) \quad\text{(action encoder),} \\ \eta_S:\bar{\mathcal{S}}\to\Delta(\mathcal{S}) \quad\text{(state decoder),}\quad \eta_A:\bar{\mathcal{S}}\times\bar{\mathcal{A}}\to\Delta(\mathcal{A}) \quad\text{(action decoder),} \end{align}\] where \(\bar{\mathcal{S}}\) and \(\bar{\mathcal{A}}\) are sets of abstract states and actions. We denote the joint encoder and decoder as \(\nu(\bar s,\bar a|s,a) := \nu_S(\bar s|s) \,\nu_A(\bar a|s,a) \quad\text{and}\quad \eta(s,a|\bar s,\bar a) := \eta_S(s|\bar s)\,\eta_A(a|\bar s,\bar a)\).

Soft state-action abstractions generalise state bisimulation and other approaches to build abstractions (see 9). The Bellman optimality operator of a soft state-action abstraction is \[\big(\bar T\bar V\big)(\bar s) := \max_{\bar a\in\bar{\mathcal{A}}(\bar s)} \Big\{ \bar r(\bar s,\bar a) +\gamma\mathbb{E}_{\bar s'\sim\bar P(\cdot\mid\bar s,\bar a)}\big[\bar V(\bar s')\big] \Big\}. \label{eq:closed-abstract}\tag{4}\] The encoder and decoder induce a ‘lifting’ (from concrete to abstract) and ‘grounding’ (from abstract to concrete) operators \[\big(LV\big)(\bar s)=\sum_{s\in\mathcal{S}} V(s)\eta_S(s\mid\bar s) \quad\text{and}\quad \big(\Gamma\bar V\big)(s)=\sum_{\bar s\in\bar{\mathcal{S}}}\bar V(\bar s)\nu_S(\bar s\mid s). \label{eq:lift-ground-value}\tag{5}\]

Soft abstractions are a stochastic extension of traditional MDP homomorphisms [5], [6], which correspond to a deterministic encoder \(\nu(\bar s,\bar a\mid s,a)=\mathbf{1}\{f(s,a)=(\bar s,\bar a)\}\) and decoder \(\eta(s,a\mid\bar s,\bar a)=\mathbf{1}\{g(\bar s,\bar a)=(s,a)\}\), where \[f(s,a)=\big(f_S(s),f_A(s,a)\big) \quad\text{with}\quad f_S:\mathcal{S}\to\bar{\mathcal{S}} \quad\text{and}\quad f_A:\mathcal{S}\times\mathcal{A}\to\bar{\mathcal{A}}\] are coarse-graining functions, and \(g(\bar s,\bar a)=\big(g_S(\bar s),g_A(\bar s,\bar a)\big)\in\mathcal{S}\times\mathcal{A}\) is a representative selector. For this scenario, the abstract MDP has rewards and transitions given by \[\bar r(\bar s,\bar a)=r\big(g(\bar s,\bar a)\big) \quad\text{and}\quad \bar P\big(\bar s' \mid \bar s,\bar a\big) = \sum_{s'\in\mathcal{S}:f_S(s')=\bar s'} P\big(s'\mid g(\bar s,\bar a)\big).\] The lifting and grounding operators become \(\big(L V)(\bar s) = V\big(g_S(\bar s)\big)\) and \(\big(\Gamma\bar V\big)(s) = \bar V\big(f_S(s)\big)\). For a more extended comparison with other abstraction frameworks, see 9.

4 Learning and abstraction errors↩︎

4.1 Assessing distortion between state-action pairs↩︎

To compare state-action pairs, it is useful to consider distortion pseudometrics¹ over \(\mathcal{S}\times\mathcal{A}\) that measure how different two state-action pairs are for planning purposes.

The tightest Bellman-compatible distortion for a given class of value functions \(\mathcal{V}\) is often of the form  [9], [10] \[d_{\rho}\big((s,a),(s',a')\big) := |r(s,a)-r(s',a')| \;+\; \gamma\,W_{1,\rho}\Big(P(\cdot\mid s,a),P(\cdot\mid s',a') \Big), \label{eq:v-distortion-upper-bound}\tag{7}\] where \(W_{1,\rho}\) is the Wasserstein/Kantorovich metric with base metric \(\rho\). For instance, \(d_{\rho_\text{ind}}\) with \(\rho_\text{ind}(s,u)=\mathbf{1}\{s=u\}\) (so that \(W_{1,\rho_\text{ind}}\) is the total variation distance) is the tightest Bellman-compatible distortion for bounded value functions \(\mathcal{V}=\{V:\|V\|_\infty\le 1\}\). Another important distortion is given by the fixed-point construction by [10], which satisfies \(\rho^*=d_{\rho^*}\). The partition induced by the zeros of Ferns’ distortion corresponds to the minimal bisimulation of the MDP. For a discussion of this and other distortions, see 10.

Distortion can be used to estimate the effect of errors induced by the simplifications associated with an abstract MDP. Consider the composition of the lifting and grounding operators, as defined in 5 , which gives the ‘round-trip’ operator \(K:=\Gamma L\) with kernel \[\kappa(s',a'\mid s,a) = \sum_{\bar s\in \bar{\mathcal{S}}}\sum_{\bar a\in\bar{\mathcal{A}}}\eta(s',a'\mid\bar s,\bar a)\nu(\bar s,\bar a\mid s,a). \label{eq:pair-round-trip}\tag{8}\] By marginalising actions, the state round-trip kernel is \(\kappa_S(s'\mid s) := \sum_{\bar s\in \bar S}\eta_S(s'\mid\bar s)\nu_S(\bar s\mid s)\). Then, the expected distortion introduced by the round-trip can be measured by \[D_\mathrm{E}(s,a) := \mathbb{E}_{(S',A')\sim \kappa(\cdot\mid s,a)} \Big[ d_\mathcal{V}\big((s,a),(S',A')\big)\Big]. \label{eq:roundtrip-defect}\tag{9}\]

4.2 Decomposing errors in optimal value estimation↩︎

We now use the above ideas to derive a decomposition of value error in terms of learning and abstraction effects. For this, we first introduce a new operator that will be useful for our derivations.

While \(\bar T^\dagger\) and \(\bar T\) act on the same space and use the same state encoder and decoder, they differ in whether the maximum is taken before or after the lifting. That said, they do have some similar properties, as shown next.

As a second ingredient, consider the geometry of the state-action space induced by the distortion \(d\). One way to assess it is to calculate its diameter \(\Delta_\text{max}:=\sup_{s,a}\sup_{s',a'} d\big((s,a),(s',a')\big)\). A subtler way to assess this is given next.

The Hausdorff distance \(D_\text{H}(s,u)\) provides a tighter estimate than state bisimulation distance \(D_B(s,u):=\max_a d\big((s,a),(u,a)\big)\) [11], [50], as it compares each action with its best matching action at the other state. For deterministic abstractions, the abstraction error bound reduces to \(\Delta_\text{H}(\kappa_S;d) = \sup_{s\in\mathcal{S}} D_H(s,g_S\circ f_S(s))\).

With all this in place, we can now formulate the following bound.

1 reveals that errors made while performing optimal value estimation on an abstract MDP can be decomposed into two types: errors within the abstract MDP, and errors due to the abstraction itself. This leads to a simple yet powerful idea:

The next section provides a formalisation of this principle using rate-distortion theory.

5 Adaptive abstractions based on rate-distortion theory↩︎

We now exploit the adaptive abstraction principle by building a family of abstractions of increasing degree of granularity using rate-distortion theory.

5.1 Building abstractions from rate-distortion theory↩︎

To use rate-distortion theory, one first needs to specify a suitable distortion function. While \(\Delta_H\) would be an attractive candidate, Hausdorff metrics are often very expensive to calculate. Following standard rate-distortion practice, let us instead take \(\mu\in\Delta(\mathcal{S}\times\mathcal{A})\) to be a replay, design, or occupancy measure, and consider the \(\mu\)-averaged distortion \[\overline{\Delta}_\mu(\nu,g) := \mathbb{E}_{(S,A)\sim\mu,\,(\bar S,\bar A)\sim\nu(\cdot\mid S,A)} \Big[d_{\mathcal{V}}\big((S,A),g(\bar S,\bar A)\big)\Big]. \label{eq:mu-decoder-defect}\tag{12}\] 11 shows under what conditions a \(\mu\)-averaged distortion can still assess the worst-case. Additionally, Appendix 8.3 shows that the choice of having a deterministic decoder in 12 does not imply lack of generality.

The resulting rate-distortion problem is as follows: \[\min_{\nu,g} \overline{\Delta}_\mu(\nu,g) \quad \text{subject to}\quad I_{\mu}(\bar S;S) \leq c_1 \quad\text{and}\quad I_\mu(\bar A;S,A\mid \bar S) \leq c_2,\] where \(c_1\) and \(c_2\) are bounds on the amount of information allowed to go into abstract states and actions, respectively. A Lagrangian formulation of the problem is \[\min_{\nu,g} \Big\{ I_{\mu}(\bar S;S) + \lambda I_\mu(\bar A;S,A\mid \bar S) + \beta \overline{\Delta}_\mu(\nu,g) \Big\}. \label{eq:rd-objective}\tag{13}\] Here, small \(\beta\) emphasises compression and therefore yields coarse soft abstractions; large \(\beta\) emphasises distortion and therefore yields finer ones. Moreover, \(I_{\mu}(\bar S;S)\) and \(I_{\mu}(\bar A;S,A|\bar S)\) disentangle the amount of information about the state and action retained by the encoder, respectively. Large \(\lambda\) encourages compressing action information, and \(\lambda=1\) means that state and action bits are weighted equally; indeed \(I_{\mu}(\bar S;S)+ I_\mu(\bar A;S,A\mid \bar S) = I(\bar S,\bar A;S,A)\).

Several familiar abstraction frameworks appear as constrained or limiting cases of 13 :

• If the encoder \(\nu\) is deterministic, then the objective reduces to a hard state-action partition. In the zero-distortion limit it recovers state bisimulation and MDP homomorphisms.

• If actions are preserved, then only the state encoder is learned and the objective then reduces to classical state abstraction.

• If \(\lambda=0\), the action encoder can perform state-dependent action matching, yielding an analogue of lax bisimulation.

• If \(\beta\to\infty\) at fixed alphabet size, the rate term becomes negligible and the problem approaches minimum-distortion clustering of state-action pairs, analogous to \(K\)-medoids.

In contrast, varying \(\beta\) and \(\lambda\) turns static bisimulation clustering into an adaptive refinement procedure. For a detailed discussion on these comparisons, see 12.

5.1.0.1 Optimisation.

For given \(\beta\), \(\lambda\), abstract alphabets \(\bar{\mathcal{S}}\) and \(\bar{\mathcal{A}}\), and distortion metric, 13 can be optimised by a generalised alternating Blahut–Arimoto scheme [51], [52]. The update alternates between refreshing the abstract marginals, updating the state encoder with the current abstract-action marginal frozen, updating the tied action encoder, and choosing blockwise decoder representatives. The technical details are provided in 13.

5.2 Rate-distortion for adaptive abstractions↩︎

We can now exploit the adaptive abstraction principle (4.2) using families of abstractions with varying granularity built via rate-distortion, indexed by the resolution parameter \(\beta\).

5.2.0.1 Algorithm sketch.

The resulting adaptive continuation method is:

1. Estimate a Bellman-compatible state-action distortion \(d\). In practice, this may be via a lax-bisimulation surrogate, a MICo-style sample-based similarity, or another critic/model-based Bellman proxy [23], [29].

2. Fix a finite abstract state alphabet \(\bar{\mathcal{S}}\), abstract action supports \(\bar{\mathcal{A}}(\bar s)\), an initial decoded codebook \(g^{(0)}\in\mathcal{G}\), a conditional-rate multiplier \(\lambda\), and a small starting temperature \(\beta_0\).

3. Solve the rate-distortion problem outlined in 13 for \(\beta=\beta_0\) using the methods described in 13, store the distortion \(\bar \Delta_{\beta_0}\), and build or update the value operator \(\bar T^\dagger\).

4. Plan or learn on the current abstract problem while monitoring the error \(\|\bar T^\dagger(\bar V) - \bar V\|\).

5. When the learning error has fallen to the scale of the current \(\bar \Delta_\beta\), increase \(\beta\) to the next value on the continuation schedule, warm-start the encoders and decoded codebook, and solve the new rate-distortion problem.

6. Stop when the desired value tolerance, compute budget, or memory budget is reached.

The resulting sequence \(\{(\nu_{S,\beta},\nu_{A,\beta},g_\beta)\}_{\beta}\) corresponds to a Pareto family of soft state-action abstractions with guarantees of minimal distortion \(\overline{\Delta}_\mu\) for given amounts of state-action information. Note that this does not necessarily result in a nested family of hard quotients. If a hard abstraction is needed for interpretation or deployment, one can set \(\beta\to\infty\) and instead regulate the abstraction by progressively decreasing the alphabet sizes \(|\bar S|\) and \(|\bar A|\), as developed by [53].

6 Case studies↩︎

This section presents experiments used to evaluate the proposed framework for adaptive abstraction. These experiments investigate three questions: whether the rate-distortion objective produces a usable compression-distortion frontier; whether the adaptive rule can navigate this frontier during planning; and how the selected abstractions compare with classic bisimulation and MDP homomorphisms. All experiments use \(\lambda=1\) and a simplified flat rate-distortion solver described in 13; additional environment and evaluation details are given in 14.

6.1 Tabular control benchmarks↩︎

We first apply the adaptive abstraction scheme (5.2) to three well-known control benchmarks: Four Rooms [54], Taxi [55], and a fully observable DoorKey variant inspired by MiniGrid [56] (see 1). The domains were chosen because they expose different forms of compressible control structure. Four Rooms is a navigation problem with spatial regularity and bottlenecks, so it is used to test state compression. Taxi adds object-oriented task variables, where pickup and dropoff are relevant only in special contexts, making action compression suitable. DoorKey combines navigation with a task-phase dependency: the agent must acquire a key before opening the door and reaching the goal, so useful compression involves both state identity and local action relevance.

Results show that a rate-distortion family of abstractions can be successfully built for these three settings: increasing \(\beta\) reduces abstraction error while increasing the effective number of abstract state-action symbols (1). Interestingly, the adaptive rule uses this frontier differently across tasks. In Four Rooms and DoorKey, the scheme settles at an intermediate resolution that already recovers near-optimal performance. In contrast, the coarsest abstractions in Taxi are too lossy and performance improves only at abstractions of relatively high rate.

Our framework allows us to probe what kind of compression takes place in these scenarios. Analyses at the first adaptive checkpoint whose policy attains optimal performance show that the compression profiles match the structure of the tasks: Four Rooms compresses most heavily the state factor, Taxi compresses primarily actions, and DoorKey compresses both the task phase and the locally appropriate action set (see 1). Overall, adaptive abstractions were found to retain substantially less effective state-action information than the exact bisimulation and MDP homomorphisms. This is not a contradiction: bisimulation preserves full value information, whereas the adaptive criterion allows errors that may be irrelevant for constructing the optimal policy.

6.2 SysAdmin scaling↩︎

We next use a ring-structured SysAdmin benchmark [19] to investigate how our approach scales with problem size. In this benchmark, the goal is to keep a set of machines working (see 2). The environment’s state is a binary vector recording which machines are operational; each timestep either does nothing or reboots one machine, and failures are more likely when neighbouring machines are down (see Appendix 14.3). Thus, a SysAdmin instance with \(N\) machines has \(2^N\) states and \(N+1\) actions, and dynamics are generated by local ring interactions. This makes the domain useful for testing whether our approach captures local control structure rather than memorising the full state-action specification.

Results show that larger systems exhibit more pronounced rate-distortion curves, which suggests that they allow for more compression with less distortion (see 2). Furthermore, the abstraction at which near-optimal performance (\(99\%\) of the full-resolution return) is achieved maintains roughly stable normalised distortion, while retaining a decreasing fraction of the concrete state-action information. This suggests that the learned codes effectively exploit the local ring structure of the dynamics rather than memorising global configurations.

We also investigated to what degree the learned near-optimal encoder provides human-readable ring features (for details of methodology, see Appendix 14.3). Results are shown in 2. On the state side, the largest mutual informations are with local failure motifs and global load variables, such as triplet histograms, pair histograms, failed count, and largest failure run. On the action side, the strongest factors describe the local context of the target machine, including its five-site neighbourhood, its failure-run size, and whether it is isolated. Overall, the probes suggest that abstractions are organised around local outage structure and locally relevant interventions rather than generic low-rank compression.

7 Conclusion↩︎

What is the essential information that an agent needs to solve a task? The approach presented here addresses this question by tuning abstraction granularity according to two sources of error: the difficulty of solving an abstract problem and the error introduced by the abstraction itself. This idea is formalised using soft state-action abstractions built from rate-distortion principles, which lead to the identification of a value error bound that distinguishes learning error as a Bellman residual and abstraction error as bisimulation distortion. This yields a simple adaptive rule: plan at the current resolution while the residual dominates, and refine once it reaches the abstraction floor.

Experiments in tabular domains support this principle. In Four Rooms, Taxi, DoorKey, and SysAdmin, the rate-distortion objective yielded a useful compression-vs-distortion trade-off, and the adaptive rule selected abstractions that recovered optimal performance while retaining substantially fewer effective state-action pairs. Moreover, the separation of state and action information rates makes the resulting abstractions diagnostically useful — they indicate if compression comes mainly from state irrelevance (as in Four Rooms), action matching (as in Taxi), or both (as in DoorKey).

This work focuses on tabular problems to provide a proof-of-principle of the proposed framework that can cleanly highlight its fundamental principles. A natural next step is to extend the adaptive principle to model-free settings, where the learning term can be estimated from sampled Bellman or TD errors and the abstraction term from sample-based behavioural metrics or latent-MDP losses [27]–[29], [31]. Another interesting extension would be to combine this framework with options, which would connect state-action compression at a single decision step with temporal abstraction over action sequences [20], [54], [57].

Future work may also use adaptive rate-distortion abstractions to enhance the interpretability of deep reinforcement learning agents. Building upon the simplicity biases of deep learning systems [58]–[60], this could be used to track how the effective state-action rate changes during training, and whether refinement events align with improvements in performance. This also connects to a long-standing observation in cognitive psychology and developmental neuroscience, which states that infants appear to navigate complex tasks by first solving coarse versions and refining only when the coarse solution stops being adequate [61]–[63]. Whether AI systems or infants implement a rule similar to the one proposed in this work, or arrive at a similar coarse-to-fine trajectory through different mechanisms, is an empirical question that we hope this work may help to address.

8 Proofs↩︎

8.1 Proof of 1↩︎

The above proof uses the following basic lemmas, whose proof we include for completeness.

8.2 Proof of 1↩︎

8.3 Proof of generality of 12↩︎

9 From state bisimulation to soft state-action abstractions↩︎

This appendix provides a brief overview of various approaches for building abstractions in reinforcement learning, tracing a path from classic bisimulation to soft state-action abstractions as defined in 3.

9.1 Bisimulation↩︎

A classic approach to building lossless state abstractions is bisimulation [7], [48].

Thus, two states are bisimilar when every action yields the same immediate reward and the same next-state law after one forgets distinctions inside the equivalence classes. Here, the equivalence classes of bisimilar states are built deterministically, primitive action labels are compared directly, and the conditions on reward and transition equalities must hold exactly. Bisimulation builds upon the notion of lumpability of Markov chains, which highlights coarse-grainings of Markov chains that result in processes that are also Markovian [64]. The term ‘bisimulation’ comes from the idea that bisimilar MDPs can simulate each other, in the sense that they are behaviourally equivalent [8] and hence everything that can be done in one can also be done in the other.

9.2 MDP homomorphisms↩︎

State bisimulation leverages the idea of relaxing distinctions between environmental states; thus, a natural extension is to abstract state-action pairs jointly. Indeed, Equations 16 and 17 suggest state-action pairs \((s,a)\) as natural objects to coarse-grain, as they determine immediate reward and next-state transitions. Thus, a state-action abstraction assigns ‘concrete’ state-action pairs to ‘abstract’ pairs via coarse-graining mappings [5], [11], [12], [20], [23]. A standard way to operationalise this idea is through MDP homomorphisms, as defined next.

Equivalently, one may define a homomorphic quotient directly from a map \(f=(f_S,f_A)\) without first specifying \(\bar r\) and \(\bar P\). The required condition is that concrete pairs with the same abstract label have the same one-step control effect at the abstract level: \[\begin{align} f(s,a)=f(t,b) &\Longrightarrow r(s,a)=r(t,b), \tag{20}\\ f(s,a)=f(t,b) &\Longrightarrow \sum_{s':f_S(s')=\bar u}P(s'\mid s,a) = \sum_{s':f_S(s')=\bar u}P(s'\mid t,b) \quad \text{for every }\bar u\in\bar{\mathcal{S}}. \tag{21} \end{align}\] When equations 20 and 21 hold, the abstract reward and transition in 6 are obtained by choosing any representative \((s,a)\) of an abstract pair \((\bar s,\bar a)\) and setting \[\bar r(\bar s,\bar a)=r(s,a), \qquad \bar P(\bar u\mid\bar s,\bar a) = \sum_{s':f_S(s')=\bar u}P(s'\mid s,a).\] The conditions ensure that this does not depend on which representative is chosen.

One can think of an MDP homomorphism as a state-action analogue of bisimulation.² Indeed, the map \(f\) induces the following equivalence relation on \(\mathcal{S}\times\mathcal{A}\): \[(s,a)\sim_{SA}(t,b) \quad\Longleftrightarrow\quad f(s,a)=f(t,b).\] Equations 20 and 21 establish that state-action-equivalent pairs have equal rewards and equal transition mass into every state block, being the pair-level analogue of 5. If the action component is forced to preserve its labels (i.e., \(f_A(s,a)=a\)), then the construction reduces to standard bisimulation.

9.3 Action-role matching via symmetry-based homomorphisms↩︎

Classical state bisimulation compares two states by asking whether every concrete action has the same effect in both states; in contrast, the action component of an MDP homomorphism can depend on the state. This raises an interesting question for state-action abstraction: under what conditions can one say that different primitive actions play the same control role in different concrete states?

Symmetry-based homomorphisms give an elegant answer to this question. These are a particular case of MDP homomorphisms, in which states and actions are matched via a structural symmetry [5], [6].

Concretely, let a group \(G\) act on \(\mathcal{S}\) through state maps \(\sigma_g:\mathcal{S}\to\mathcal{S}\), and let \(\rho_g^s:\mathcal{A}\to\mathcal{A}\) be the corresponding action relabelling at state \(s\). One can show that this group yields a MDP homomorphism if the following conditions hold [6]: \[r\big(\sigma_g(s),\rho_g^s(a)\big)=r(s,a), \qquad P\big(\sigma_g C\mid \sigma_g(s),\rho_g^s(a)\big) = P(C\mid s,a),\] where \(C\) is an orbit generated by the action \(\sigma_g\) and \(\sigma_g C=\{\sigma_g(u):u\in C\}\).

Thus, using the resulting orbits as equivalence classes produces a MDP homomorphism. The fact that \(\rho_g^s\) may depend on the current state is what allows symmetry-based homomorphisms to capture equivariant relationships, where the same functional role is expressed by different primitive action labels in different states.

9.4 Relaxations of state bisimulation and MDP homomorphisms↩︎

The various notions above can be relaxed along several axes — one can replace equality by a metric error, replace same-label action comparison by action-role matching, replace worst-case all-action requirements by policy-conditioned ones, or replace exact model preservation by learned surrogate losses. We review some of these approaches next.

9.4.0.1 Bisimulation metrics.

The canonical relaxation of bisimulation is the fixed-point pseudometric presented by [9], [10] (see 10). Instead of asking whether two states have identical rewards and identical transition mass into every equivalence class, it assigns a distance by comparing the same primitive action at both states. To build this metric, one considers the following functional: \[\mathcal{F}(\rho)(s,t) := \max_{a\in\mathcal{A}} \Big\{ c_r \big|r(s,a)-r(t,a)\big| + c_p W_\rho\big(P(\cdot\mid s,a),P(\cdot\mid t,a)\big) \Big\},\] where \(c_r,c_p\) are nonnegative constants, and \(W_\rho\) is the Kantorovich/Wasserstein distance induced by the current state pseudometric \(\rho\). It can be shown [9], [10] that the smallest fixed point of \(\mathcal{F}\) gives zero distance exactly on bisimulation classes, while also providing a graded notion of almost-bisimilarity. Note that this is primarily a state abstraction method: actions are used to test states, but they are not coarse-grained.

9.4.0.2 Lax bisimulation and approximate homomorphisms.

A lax bisimulation metric [11] is used to relax the notion of MDP homomorphism in an analogous way as Ferns’ bisimulation metric is used to relax state bisimulation. Given a state pseudometric \(\rho:\mathcal{S}\times\mathcal{S}\to\mathbb{R}_+\) and nonnegative weights \(c_r,c_p\), a state-action pair discrepancy can be written as \[\delta_\rho\big((s,a),(t,b)\big) := c_r |r(s,a)-r(t,b)| + c_p W_\rho\big(P(\cdot\mid s,a),P(\cdot\mid t,b)\big).\] This quantity compares two concrete pairs even when \(a\) and \(b\) are different primitive labels. Bisimulation uses this quantity to create a state-only pseudometric by considering the action that gives the worst-case divergence. A subtler approach is taken by lax bisimulation, which builds a state metric through a symmetric Hausdorff matching over actions: \[D_\text{H}(\rho)(s,t) := \max\left\{ \sup_{a\in\mathcal{A}}\inf_{b\in\mathcal{A}} \delta_\rho\big((s,a),(t,b)\big), \; \sup_{b\in\mathcal{A}}\inf_{a\in\mathcal{A}} \delta_\rho\big((s,a),(t,b)\big) \right\}.\] The fixed point of this Hausdorff-style operator has zeros corresponding to the state classes of exact homomorphic quotients. At nonzero distance, the same construction gives a quantitative approximate-homomorphism error [11], [23]. Thus, the lax bisimulation metric is state-level, but it is induced by state-action pair comparisons and Hausdorff action matching. Thus, it can be used to relax MDP homomorphisms in general, and symmetry-based homomorphisms in particular.

9.4.0.3 Behavioural and learned relaxations.

Another kind of relaxation is to preserve only distinctions relevant to a policy, a value criterion, or the data distribution under which the representation is learned. Policy-conditioned similarities and value-preserving state-action abstractions weaken exact bisimulation or exact homomorphism by preserving the aspects of the dynamics needed for a particular behavioural objective rather than the full controlled transition structure [20], [25], [26]. In deep RL, the exact reward and transition comparisons are often replaced by sample-based losses or latent-model objectives, as in DeepMDP-style latent models, MICo, robust bisimulation metric learning, contrastive behavioural similarities, and related objectives [27]–[31], [65]. These methods often do not explicitly construct a quotient MDP, but they aim to learn representations in which irrelevant behavioural distinctions are small.

9.5 Soft state-action coarse-grainings↩︎

A final step is to relax the coarse-graining map itself. State bisimulation, homomorphisms, and their metric relaxations still presuppose ‘hard’ assignments: a concrete state or state-action pair either belongs to a block or it does not. Soft abstractions replace this hard membership by stochastic encoders, in the same broad family as stochastic model reduction, variational abstractions, and information-bottleneck approaches to representation learning [32]–[37], [48].

For state-action abstraction, the stochastic encoder used in 3 has the factorised form \[\nu(\bar s,\bar a\mid s,a) = \nu_S(\bar s\mid s)\,\nu_A(\bar a\mid s,a),\] where \(\nu_S:\mathcal{S}\to\Delta(\bar{\mathcal{S}})\) and \(\nu_A:\mathcal{S}\times\mathcal{A}\to\Delta(\bar{\mathcal{A}})\). This keeps the state/action separation of MDP homomorphisms, while allowing each concrete pair to distribute mass over several abstract pairs. Because there are no hard coarse-grainings anymore, this does not lead to equivalence classes. Instead, the concrete and abstract dynamics should intertwine: evolving in the concrete MDP and then encoding should agree, in expectation, with encoding first and then evolving in the abstract MDP.

The construction presented in 3 is one way to instantiate such a soft abstraction. In addition to the encoder \(\nu\), it introduces a decoder \(\eta\), and defines \(\bar r\) and \(\bar P\) by the decoder-averaged formulas (Equations 2 and 3 ). The phrase ‘soft state-action abstraction’ is meant to emphasize the specific line of descent here: it is a stochastic version of the pair-level behavioural equivalence encoded by MDP homomorphisms.

A comparison of the various abstraction approaches discussed here is provided in 3.

10 Bellman-compatible state-action distortions↩︎

Let \(x=(s,a)\) and \(y=(u,b)\) be two state-action pairs and use \(P_x:=P(\cdot\mid x)\) and \(P_y:=P(\cdot\mid y)\) as shorthand notation for the transition kernels. For a class of value functions \(\mathcal{V}\), the worst Bellman-backup discrepancy is bounded by \[\begin{align} \sup_{V\in\mathcal{V}} \big| (BV)(x)-(BV)(y) \big| &= \sup_{V\in\mathcal{V}} \left| r(x)-r(y) \;+\; \gamma \sum_{s'\in\mathcal{S}} V(s')\,\Big(P(s'|x) - P(s'|y)\Big) \right| \notag \\ &\le |r(x)-r(y)| \;+\; \gamma D_{\mathcal{V}}(P_x,P_y), \label{eq:value-compatible-decomposition} \end{align}\tag{22}\] where \[D_{\mathcal{V}}(p,q) := \sup_{V\in\mathcal{V}} \left| \sum_{s'\in\mathcal{S}} V(s')\,\Big( p(s') - q(s')\Big) \right|. \label{eq:value-induced-ipm}\tag{23}\] If \(\mathcal{V}\) is closed under sign changes (i.e., \(V\in\mathcal{V}\) implies \(-V\in\mathcal{V}\)), then the upper bound in 22 is tight whenever \(D_{\mathcal{V}}(P_x,P_y)<\infty\). Indeed, for any \(\varepsilon>0\) choose \(V_\varepsilon\in\mathcal{V}\) such that \[\left|\sum_{s'\in\mathcal{S}} V_\varepsilon(s')\,\Big( P(s'|x) - P(s'|y)\Big)\right| \ge D_{\mathcal{V}}(P_x,P_y)-\varepsilon.\] Using the fact that one can always replace \(V_\varepsilon\) by \(-V_\varepsilon\) if needed to align the sign of the transition term with \(r(x)-r(y)\), one can guarantee that \[\sup_{V\in\mathcal{V}} \left| r(x)-r(y)+\gamma\sum_{s'\in\mathcal{S}} V(s')\,\Big(P(s'|x) - P(s'|y)\Big) \right| \ge |r(x)-r(y)| +\gamma\Big(D_{\mathcal{V}}(P_x,P_y)-\varepsilon\Big).\] Letting \(\varepsilon\downarrow0\) gives equality. This motivates the canonical Bellman-compatible upper bound \[d_{\mathcal{V}}^*(x,y) := |r(x)-r(y)| \;+\; \gamma D_{\mathcal{V}}(P_x,P_y). \label{eq:value-compatible-symmetric}\tag{24}\] In the following we consider special cases of \(\mathcal{V}\).

10.0.0.1 Bounded \(L^\infty\) value classes.

If \(\mathcal{V}_{\infty,C}:=\{V:\|V\|_\infty\le C\}\), then \[\begin{align} D_{\mathcal{V}_{\infty,C}}(p,q) &= C\sup_{\|f\|_\infty\le 1} \left| \sum_{s\in\mathcal{S}} f(s)\Big(p(s) - q(s)\Big) \right| \notag = C\sum_{z\in\mathcal{S}}|p(z)-q(z)|, \label{eq:linfty-ipm-tv} \end{align}\tag{25}\] where the second equality follows by taking \(f(z)=\operatorname{sign}(p(z)-q(z))\). With the convention \(d_{\mathrm{TV}}(p,q):=\sum_{s\in\mathcal{S}}|p(s)-q(s)|\), this gives \[d_{\mathcal{V}_{\infty,C}}^*(x,y) = |r(x)-r(y)| \;+\; \gamma\,C\, d_{\mathrm{TV}}\!\big(P_x,P_y\big).\] This choice gives a uniform estimate, but ignores any geometry on \(\mathcal{S}\) and therefore provides a conservative estimate.

10.0.0.2 Bounded Lipschitz classes.

Let \(\rho\) be a pseudometric on \(\mathcal{S}\) and set \[\mathcal{V}_{\mathrm{Lip}(\rho),C} := \{V:\|V\|_{\mathrm{Lip},\rho}\le C\}, \quad\text{where}\quad \|V\|_{\mathrm{Lip},\rho} := \sup_{\rho(s,u)>0}\frac{|V(s)-V(u)|}{\rho(s,u)}.\] Since \(P_x\) and \(P_y\) are probability measures with equal total mass, additive constants in \(V\) do not affect \(\sum_{s\in\mathcal{S}} V(s)\,\Big(P(s|x) - P(s|y)\Big)\). Then, one can show that \[\begin{align} D_{\mathcal{V}_{\mathrm{Lip}(\rho),C}}(P_x,P_y) &= C \sup_{\|f\|_{\mathrm{Lip},\rho}\le1} \left|\sum_{s\in\mathcal{S}} f(s)\,\Big(P(s|x) - P(s|y)\Big)\right| = C\,W_{1,\rho}(P_x,P_y), \label{eq:lip-ipm-wasserstein} \end{align}\tag{26}\] where \(W_{1,\rho}\) is the Wasserstein distance with ground cost \(\rho\) defined as \[W_{1,\rho}(p,q) := \min_{\zeta\in\Pi(p,q)} \sum_{s,u\in\mathcal{S}}\rho(s,u)\,\zeta(s,u)\] and \(\Pi(p,q)\) is the set of couplings with marginals \(p\) and \(q\) \[\Pi(p,q) := \Big\{\zeta: \zeta(s,u)\ge 0, \sum_{s\in\mathcal{S}}\zeta(s,u)=q(u), \sum_{u\in\mathcal{S}}\zeta(s,u)=p(s)\Big\}.\] Above, the second equality in 26 follows from the Kantorovich-Rubinstein duality. Thus \[d_{\mathcal{V}_{\mathrm{Lip}(\rho),C}}^*(x,y) = |r(x)-r(y)| \;+\; \gamma\,C\, W_{1,\rho}\!\big(P_x,P_y\big).\] The finite-state setting makes the first-moment condition automatic. In more general spaces, the same formula requires finite first moments under \(\rho\).

10.0.0.3 Ferns’ fixed-point metric.

The two distortions considered above evaluate dynamics considering only one step ahead. Thus, they may state that two state-action pairs are similar without taking into account their long-term consequences. A classic construction that goes beyond this is Ferns’ fixed-point metric [9], [10], which we introduce next.

Given a state pseudometric \(\rho:\mathcal{S}\times\mathcal{S}\to[0,\infty)\), define the associated distortion \[d_\rho\big((s,a),(u,b)\big) := |r(s,a)-r(u,b)| \;+\; \gamma W_{1,\rho}\!\big(P(\cdot\mid s,a),P(\cdot\mid u,b)\big). \label{eq:rho-pair-distortion}\tag{27}\] The operator introduced in [9], [10] compares states using the worst-case action matching: \[(\mathcal{F}\rho)(s,u) := \max_{a\in\mathcal{A}} d_\rho\big((s,a),(u,a)\big). \label{eq:ferns-state-operator}\tag{28}\] It can be shown that \(\mathcal{F}\) is a \(\gamma\)-contraction in \(L^\infty\) for finite MDPs, and thus it has a fixed point. At this fixed point, \[\rho_B(s,u) = \max_{a\in\mathcal{A}} \Big\{ |r(s,a)-r(u,a)| +\gamma W_{1,\rho_B}\!\big(P(\cdot\mid s,a),P(\cdot\mid u,a)\big) \Big\}.\] The zero sets of \(\rho_B\) are exactly the state-bisimulation classes: distance zero forces equal rewards and equal transition mass into each zero-distance class for every action, and those two equalities conversely make the fixed-point distance vanish. This is the sense in which the metric used inside the Wasserstein term is also the metric being solved for.

For state-action abstraction with action relabelling, one can replace the same-label maximum in 28 by the Hausdorff/lax action matching used in the main text: \[D_H^\rho(s,u) := \max\left\{ \sup_{a\in\mathcal{A}}\inf_{b\in\mathcal{A}} d_\rho\big((s,a),(u,b)\big), \; \sup_{b\in\mathcal{A}}\inf_{a\in\mathcal{A}} d_\rho\big((s,a),(u,b)\big) \right\}. \label{eq:lax-hausdorff-state-distance}\tag{29}\] This replaces literal action identity by best action matching across states. The main bound only requires a Bellman-compatible pair distortion; it can therefore use either the same-action Ferns metric, the Hausdorff/lax variant, or a computable surrogate for them.

11 From \(\mu\)-averaged to worst-case distortion↩︎

The main bound in 1 is stated in terms of the worst-case Hausdorff abstraction distortion \[\Delta_H(\kappa_S;d_{\mathcal{V}}) = \sup_{s\in\mathcal{S}} \mathbb{E}_{U\sim\kappa_S(\cdot\mid s)} \big[D_H(s,U)\big].\] By contrast, the rate-distortion objective in 13 optimises a \(\mu\)-averaged reconstruction defect. This appendix makes explicit what such an average can and cannot guarantee.

For this purpose, let us consider the quantity \(e_{\kappa}(s) := \mathbb{E}_{U\sim\kappa_S(\cdot\mid s)} \big[D_H(s,U)\big]\). Using it, the worst-case Hausdorff distortion can be expressed as \[\Delta_H(\kappa_S;d_{\mathcal{V}})=\sup_{s\in\mathcal{S}} e_\kappa(s).\] Additionally, for a given distribution \(\mu_S\in\Delta(\mathcal{S})\) we can also use \(e_{\kappa}(s)\) to build the averaged Hausdorff distortion as \[\Delta^H_{\mu_S}(\kappa_S;d_{\mathcal{V}}) := \mathbb{E}_{S\sim\mu_S}[e_\kappa(S)]. \label{eq:mu-hausdorff-defect}\tag{30}\] We now study relationships between these two quantities.

The proposition shows that a \(\mu\)-averaged distortion can certify the worst case when \(\mu\) assigns sufficient mass to each state at which distortion may be large. Note that the resulting constant may be poor: for a uniform distribution on a finite state space, ?? gives the factor \(|\mathcal{S}|\). However, no distribution-free converse is possible without such a coverage condition.

Finally, average distortion \(\overline{\Delta}_\mu(\nu,g)\) used in 12 should be read as a computable surrogate for these averaged defects. It becomes a uniform certificate only with the corresponding coverage assumptions, and only when the chosen pair reconstruction controls the Hausdorff state defect relevant to 1. Otherwise, it remains a useful design criterion for building a family of abstractions.

12 How rate-distortion generalises abstraction frameworks↩︎

The rate-distortion formulation presented in 13 can be seen as an umbrella construction containing many familiar bisimulation and abstraction constructions as limiting or constrained cases. Some of these constructions are discussed in detail in 9.

1. Hard abstractions. If the state and action encoders are deterministic Dirac kernels \[\begin{align} \nu(\bar s,\bar a\mid s,a) =\mathbf{1}\{f(s,a)=(\bar s,\bar a)\} \end{align}\] for \(f(s,a)=\big(f_S(s),f_A(s,a)\big)\) with \(f_S:\mathcal{S}\to\bar{\mathcal{S}}\) and \(f_A:\mathcal{S}\times\mathcal{A}\to\bar{\mathcal{A}}\), then every concrete state \(s\) and action \(a\) is assigned to a unique abstract state/action \((\bar s,\bar a)\). The stochastic rate-distortion problem then reduces to a hard partition or quotient problem with decoded representatives. In the zero-distortion case, and with enough abstract symbols, this is the usual exact quotient/homomorphism setting of stochastic bisimulation and MDP homomorphisms [5], [7], [11].

2. Approximate hard homomorphisms. If the encoders are deterministic but the attained pair distortion is nonzero, then the objective is an approximate homomorphism problem: each block has a representative decoded state and decoded actions, and the abstraction error is the averaged Bellman-compatible mismatch within that block. This is the finite-alphabet, lossy analogue of approximate MDP homomorphisms and value-preserving state-action abstractions [11], [20], [23].

3. Lax bisimulation/action matching. Setting \(\lambda=0\) removes the penalty for retaining action information inside an abstract state. The action encoder can then use as much action information as the abstract action alphabet permits to match state-dependent control roles, so the objective becomes an averaged, rate-distortion version of the lax-bisimulation geometry. It becomes the lax bisimulation metric itself only if the distortion is replaced by the Hausdorff aggregation introduced in 4, and \(d_{\mathcal{V}}\) is chosen to be the corresponding Bellman fixed-point pseudometric (see 9); otherwise it is a tractable mean-distortion surrogate built from the same state-action matching idea.

4. Classical state abstractions. If actions are not compressed (for example \(\bar{\mathcal{A}}=\mathcal{A}\), \(\nu_A(\bar a\mid s,a)=\mathbf{1}\{\bar a=a\}\) and the action component of \(g(\bar s,\bar a)\) is \(\bar a\)), then the only learned compression is the state encoder \(\nu_S\). In this case, the objective reduces to a state-abstraction problem with action labels preserved, recovering the standard setting studied in state aggregation, stochastic bisimulation partitions, and the abstraction taxonomy of [8]; approximate variants correspond to replacing exact equivalence by a positive distortion budget [7], [8], [12], [24].

5. Bisimulation clustering for a fixed alphabet. If \(\beta\to\infty\) while the number of abstract states and decoded abstract actions is fixed, the rate term becomes negligible and the problem becomes minimum-distortion clustering under a given distortion \(d\). With deterministic encoders this is the state-action analogue of \(K\)-medoids or partition-around-medoids [66]. If \(d\) is a bisimulation or homomorphism metric, this recovers the usual practice of clustering states or state-action pairs by behavioural distance; if the alphabet is large enough to achieve zero distortion, it recovers exact bisimulation minimisation [9], [10].

6. Deterministic annealing and soft clustering. Finite \(\beta\) is the soft counterpart of hard bisimulation clustering: blocks are probabilistic, high-distortion assignments are exponentially suppressed, and increasing \(\beta\) follows a deterministic-annealing path from coarse to fine abstractions. This is the same optimisation principle behind classical rate-distortion and information-bottleneck state abstraction, now using a Bellman-compatible state-action distortion rather than an imitation or prediction loss.

The formulation also introduces numerous novel settings corresponding to other parameter settings:

• Degenerate action collapse is not ordinary state abstraction. If instead the action encoder is constant, or each \(\bar{\mathcal{A}}(\bar s)\) has only one action, the method collapses control choices rather than merely abstracting states. This can be useful as a deliberately low-capacity controller, but it should not be identified with classical state abstraction, which normally keeps the primitive action labels available at every abstract state [8], [20].

• Symmetries and action relabellings. Because \(\nu_A\) enters the distortion term, the objective can learn state-dependent action relabellings and equivariances. This is the homomorphism intuition behind state-action abstraction: different concrete actions may play the same behavioural role in different states, and the abstraction should preserve that role rather than the literal action name [5], [6], [11], [23], [26].

• Adaptive refinement. Finally, varying \(\beta\), the alphabet size, or the admissible action supports turns static bisimulation clustering into an adaptive refinement procedure. Classical model minimisation and partition refinement split until exact behavioural consistency is reached; the present formulation replaces the hard consistency test by a residual-versus-distortion scale comparison, allowing the abstraction resolution to track what the learner can currently estimate.

13 Rate-Distortion Solvers↩︎

Throughout this appendix, write \(d\) for the Bellman-compatible pair distortion \(d_{\mathcal{V}}\). Let \(\mathcal{G}\) denote the set of admissible representative maps \(g:\bar{\mathcal{S}}\times\bar{\mathcal{A}}\to\mathcal{S}\times\mathcal{A}\), and let \(\mathcal{G}(\bar s)\) denote the corresponding set of decoder slices \(h:\bar{\mathcal{A}}(\bar s)\to\mathcal{S}\times\mathcal{A}\) at abstract state \(\bar s\).

13.1 Structured solver↩︎

For any state and action encoders, write their abstract marginals and posterior as \[\begin{align} \pi_{\nu}(\bar s) &:= \sum_s \mu_S(s)\nu_S(\bar s\mid s), \label{eq:ba-pair-marginal} \\ m_{\nu}(\bar a\mid \bar s) &:= \frac{ \sum_{s,a}\mu(s,a)\nu_S(\bar s\mid s)\nu_A(\bar a\mid s,a) }{ \pi_{\nu}(\bar s) }, \\ \nu_{\mu_S}(s\mid\bar s) &:= \frac{\mu_S(s)\nu_S(\bar s\mid s)}{\pi_{\nu}(\bar s)}. \end{align}\tag{31}\] The conditional marginal and posterior are defined arbitrarily on zero-mass abstract states. These quantities are recomputed whenever the encoder changes. Write \(\mu_A(\cdot\mid s)\) for the conditional action reference induced by \(\mu\).

For fixed \(\beta\), we optimise the objective (13 ) using a generalised alternating Blahut–Arimoto scheme, viewed as alternating minimisation over encoders, marginals, and decoders [51], [52], [67], [68]. The state-encoder step is the BA update with the current abstract-state marginal and abstract-action marginal frozen. Its state cost includes both a distortion term and the contribution of \(I_\mu(S,A;\bar A\mid\bar S)\). The action-encoder step is the analogous conditional rate-distortion update for the soft action code. It can be solved by projected gradient or exponentiated gradient. In the variant where the action encoder is allowed to condition on the sampled abstract state, \(\nu_A(\bar a\mid s,a,\bar s)\), this subproblem has the usual BA softmax form with prior \(m_\nu(\bar a\mid\bar s)\) and distortion \(d\big((s,a),g^{(n)}(\bar s,\bar a)\big)\). Under the convention of this paper, where \(\nu_A(\bar a\mid s,a)\) is shared across the possible abstract states, the same step becomes a tied-parameter conditional rate-distortion update. The decoder step is a blockwise state-action medoid update of the structured decoder slices \(g(\bar s,\cdot)\). See an implementation in 3.

13.2 Simplified flat pairwise solver used in the diagnostics↩︎

With \(\lambda=1\) and the joint-encoder simplification described below, the experiments solve \[\min_{\nu,\,g\in\mathcal{G}} \left\{ I_{\mu}(S,A;\bar S,\bar A) + \beta \overline{\Delta}_\mu(\nu,g) \right\}.\] Additionally, they introduce the following simplification: instead of optimising \(\nu_S\) and \(\nu_A\) separately, they focus on \(\nu:\mathcal{S}\times\mathcal{A}\to \Delta(\bar{\mathcal{S}}\times\bar{\mathcal{A}})\) as a single entity. This allows for a more computationally efficient algorithm, which is described in 4.

14 Experimental details↩︎

This appendix provides additional information regarding the experiments. Code to reproduce the experimental results can be found in github.com/ferosas/adaptive-state-action-abstraction.

14.1 Shared model-based protocol↩︎

All experiments in 6 are tabular discounted MDPs whose transitions and rewards are assumed to be known. Thus the transition tensor \(P(\cdot\mid s,a)\), reward function \(r(s,a)\), Bellman updates, policy evaluation, and state-action distortion matrices are all computed exactly. No Monte Carlo rollouts are used for the reported returns. Unless stated otherwise, the discount is \(\gamma=0.95\), the reference measure in the rate-distortion objective is the uniform measure \(\mu(s,a)=1/(|\mathcal{S}||\mathcal{A}|)\), and the reported abstraction error is the average decoder distortion \[\overline{\Delta}_\mu(\nu,g) = \mathbb{E}_{(S,A)\sim \mu,\,Z\sim\nu(\cdot\mid S,A)} \big[d((S,A),g(Z))\big].\] The switching rule therefore uses this average distortion proxy, not the Hausdorff worst-case quantity from 4.

14.1.0.1 Distortion.

All experiments build a fixed-point state-action bisimulation pseudometric of the form \[d^*\big((s,a),(u,b)\big) = |r(s,a)-r(u,b)| +\gamma W_{d^*}\!\left(P(\cdot\mid s,a),P(\cdot\mid u,b)\right).\] Here \(W_{d^*}\) is the finite-state Wasserstein distance with ground cost \(d^*\). For deterministic domains such as Taxi and DoorKey, this Wasserstein term reduces to the distance between the successor states. For stochastic SysAdmin, it is solved exactly by the dual linear program. Four Rooms uses the same fixed-point object, with an implementation that exploits the uniform-reset structure to compute it efficiently.

14.1.0.2 Rate-distortion fitting.

The experiments use the flat solver from 13 with \(\lambda=1\). Internally this solver fits a single soft encoder \(\nu(z\mid s,a)\) over concrete state-action pairs and a deterministic representative \(g(z)\in\mathcal{S}\times\mathcal{A}\) for each active code \(z\). The abstract alphabet cap is set to the full number of concrete state-action pairs, \(|\mathcal{S}||\mathcal{A}|\); after fitting, codes whose abstract marginal under \(\mu\) is below \(10^{-4}\) are pruned and the encoder is renormalised. Blahut–Arimoto updates use tolerance \(10^{-6}\). The per-domain limits on outer and inner alternating updates are given below.

14.1.0.3 Planning and grounding.

Planning is performed in \(Q\)-space. The full-resolution baseline starts from \(Q_0=0\) and applies the concrete optimality update \[(FQ)(s,a) = r(s,a) +\gamma\sum_{s'}P(s'| s,a)\max_{a'}Q(s',a').\] For a given abstraction, \(\bar Q(\bar s,\bar a)\) can be grounded to concrete state-action pairs via \[Q^{\mathrm{gr}}(s,a) = \sum_{\bar s,\bar a} \nu(\bar s,\bar a| s,a)\bar Q(\bar s,\bar a),\] and the decoder can be used to read the concrete Bellman update back: \[(\bar F\bar Q)(\bar s,\bar a)=(FQ^{\mathrm{gr}})(g(\bar s,\bar a)).\]

For a fixed \(\beta\), traces start from \(\bar Q_0=0\) and repeatedly apply \(\bar F\). For the adaptive setting, traces start at the coarsest \(\beta\) and switch to finner abstractions when the residual \[\max_{s\in\mathcal{S}} \left| \max_a Q^{\mathrm{gr}}_{\mathrm{next}}(s,a) - \max_a Q^{\mathrm{gr}}(s,a) \right|\] falls below the current \(\overline{\Delta}_\mu\). When switching, the current grounded \(Q\)-function is transferred to candidate finner abstractions, and the controller skips any later abstraction whose transferred residual is still below its abstraction error.

14.1.0.4 Evaluation.

The return traces shown in the paper measure the quality of the grounded concrete policy against the corresponding number of Bellman updates. At a recorded checkpoint \(k\), the plotted policy is always the deterministic greedy concrete policy \[\pi_k(s)\in\arg\max_{a\in\mathcal{A}} Q^{\mathrm{gr}}_k(s,a),\] with ties broken by the listed action order. The value plotted for this policy is its exact value in the original concrete MDP. Concretely, we solve \[(I-\gamma P^{\pi_k})v^{\pi_k}=r^{\pi_k}, \qquad r^{\pi_k}(s)=r(s,\pi_k(s)), \qquad P^{\pi_k}(s,s')=P(s'\mid s,\pi_k(s)),\] and report the uniform state average \[\frac{1}{|\mathcal{S}|}\sum_{s\in\mathcal{S}}v^{\pi_k}(s),\] including the absorbing terminal state when a domain has one.

14.1.0.5 Information and compression diagnostics.

All information quantities are computed in bits. For a given abstraction with states \(\bar s\in\bar{\mathcal{S}}\) and actions \(\bar a\in\bar{\mathcal{A}}\), the effective number of abstract labels is \(2^{I_\mu(S,A;\bar S,\bar A)}\). We then report the chain-rule split \[I_\mu(S,A;\bar S,\bar A) = I_\mu(S,A;\bar S) + I_\mu(S,A;\bar A\mid \bar S).\] The corresponding information-equivalent sizes are \(2^{I_\mu(S,A;\bar S)}\) and \(2^{I_\mu(S,A;\bar A\mid\bar S)}\). These effective sizes are not the same as the raw alphabet sizes — they discount unused or imbalanced labels and stochastic assignments. Rates divide these two effective sizes by \(|\mathcal{S}|\) and \(|\mathcal{A}|\), respectively, and the normalised state-action rate is their product.

14.1.0.6 Exact bisimulation baselines.

The state-bisimulation column of 1 is computed by exact partition refinement: states are split until states in the same block have the same reward and the same transition mass into every current block for every primitive action. Since this baseline keeps \(\bar{\mathcal{A}}=\mathcal{A}\), the normalised state-action rate is \((\#\text{state equivalence classes})/|\mathcal{S}|\). The MDP homomorphism column is computed from the zero-distance relation of the fixed-point pair metric \(d\), using connected components of \(\{((s,a),(u,b)):d((s,a),(u,b))=0\}\) with numerical tolerance \(10^{-8}\max\{1,\max d\}\). The adaptive point in 1 is the first adaptive checkpoint whose exact grounded return reaches the optimal return.

14.2 Classic tabular benchmarks↩︎

14.2.0.1 Four Rooms.

The Four Rooms experiment uses the classic \(11\times 11\) four-room layout with four hallways. A state is a pair consisting of the current cell and the current goal index. The four goal cells are the room centers \((2,2)\), \((3,8)\), \((8,2)\), and \((8,8)\). There are \(104\) playable cells (i.e. discounting walls) and four possible goal rooms, giving \(104\times 4=416\) states. The action set is \(\{\texttt{up},\texttt{right},\texttt{down},\texttt{left}\}\), so \(|\mathcal{S}||\mathcal{A}|=1664\). With probability \(1-\eta\) the intended move is executed, and with probability \(\eta\) the agent stays in place; wall collisions also leave the agent in place (experiments use \(\eta=0.10\)). If the landing cell is the current goal center, the agent receives reward \(1\) and the next state is reset uniformly over all cell-goal pairs, including the same goal. All other rewards are zero. The fixed and adaptive \(\beta\) ladder is \(\{0,5,10,15,20\}\). The Blahut–Arimoto limit is \(500\) outer iterations and \(50\) inner iterations per \(\beta\), and the planning budget is \(150\) full-resolution sweeps with evaluation every sweep.

14.2.0.2 Taxi.

The Taxi experiment follows the Taxi-v3 dynamics on the \(5\times 5\) map with depot locations \(R,G,Y,B\), but adds a single absorbing success state so that the episodic task is represented as a discounted MDP. Nonterminal states are \((\text{row},\text{column},\text{passenger location},\text{destination})\), where the passenger is either at one of the four depots or in the taxi. This gives \(500\) nonterminal states plus one absorbing state, for \(501\) states total. The action set is \(\{\texttt{south},\texttt{north},\texttt{east},\texttt{west}, \texttt{pickup},\texttt{dropoff}\}\), so \(|\mathcal{S}||\mathcal{A}|=3006\). Transitions are deterministic. Each ordinary step has reward \(-1\), illegal pickup/dropoff has reward \(-10\), and a successful dropoff has reward \(20\) and transitions to the absorbing state. The \(\beta\) ladder is \(\{0.02,0.04,0.06,0.08,0.10\}\). The Blahut–Arimoto limit is \(10\) outer iterations and \(100\) inner iterations per \(\beta\), and the planning budget is \(100\) full-resolution sweeps with evaluation every sweep.

14.2.0.3 DoorKey.

The DoorKey experiment is a fully observable tabular variant inspired by MiniGrid. The grid has side length \(5\). An internal wall separates two rooms; the locked door is at \((2,2)\), the key is at \((1,3)\), and the goal is at \((3,3)\). The state records the agent position, facing direction, whether the key is carried, and whether the door is open. Only reachable task phases are included: key absent with door closed, key carried with door closed, and key carried with door open, plus one absorbing terminal state. This yields \(233\) states. The action set is \(\{\texttt{turn\_left},\texttt{turn\_right},\texttt{forward}, \texttt{pickup},\texttt{toggle}\}\), so \(|\mathcal{S}||\mathcal{A}|=1165\). Transitions are deterministic. The only positive reward is the goal reward, equal to \(1\), obtained when the agent moves into the goal and enters the absorbing state. The fixed \(\beta\) ladder is \(\{6,7,7.5,8,10\}\). The adaptive ladder is the unit-spaced refinement \(\{6,7,8,9,10\}\). The Blahut–Arimoto limit is \(200\) outer iterations and \(50\) inner iterations per \(\beta\), and the planning budget is \(100\) full-resolution sweeps with evaluation every sweep.

14.3 SysAdmin↩︎

We use a fully observable ring variant of the SysAdmin benchmark [19]. A state \(x\in\{0,1\}^N\) records which machines are operational, with \(x_i=1\) meaning that machine \(i\) is up. For \(N\ge 3\) the neighbours of \(i\) are \(i-1\) and \(i+1\) modulo \(N\); for \(N=2\), each machine has the other machine as its single neighbour. Let \(\mathcal{N}(i)\) denote this ring-neighbour set. The action set is \[\mathcal{A}=\{\mathrm{noop},\mathrm{reboot}_1,\ldots,\mathrm{reboot}_N\}.\] At each step the controller either does nothing or attempts to reboot one machine. The reward is the fraction of machines currently up, minus a reboot cost when a reboot action is used: \[r(x,a) = \frac{1}{N}\sum_{i=1}^N x_i - c_{\mathrm{reboot}}\mathbf{1}\{a\neq \mathrm{noop}\}.\] The parameters used in all SysAdmin experiments are \[p_{\mathrm{base}}=0.95,\qquad \rho=0.15,\qquad p_{\mathrm{recover}}=0.05,\qquad p_{\mathrm{reboot}}=0.95,\qquad c_{\mathrm{reboot}}=0.2.\] Conditional on the current state and action, machines transition independently. If machine \(i\) is rebooted, then \(\mathbb{P}(X'_i=1\mid x,a)=p_{\mathrm{reboot}}\). If it is down and not rebooted, then \(\mathbb{P}(X'_i=1\mid x,a)=p_{\mathrm{recover}}\). If it is up and not rebooted, then its probability of remaining up decreases by \(\rho\) for each failed neighbour: \[\mathbb{P}(X'_i=1\mid x,a) = \left[ p_{\mathrm{base}} - \rho\sum_{j\in\mathcal{N}(i)}(1-x_j) \right]_{[0,1]},\] where \([\cdot]_{[0,1]}\) denotes clipping to \([0,1]\). Thus the tabular problem has \(2^N\) states, \(N+1\) actions, and \((N+1)2^N\) state-action pairs, while the transition law has local ring structure.

14.3.0.1 Scaling sweep.

The scaling experiment in 2 runs for systems of sizes \(N=2,\ldots,7\). For each \(N\), the full-resolution reference return is the exact value of the final concrete baseline policy under the same \(100\)-sweep full-resolution compute budget. The selected checkpoint is the first adaptive checkpoint whose grounded concrete policy return is at least \(99\%\) of this reference. The star in 2 is then placed at the rate-distortion row whose \(\beta\) matches that selected checkpoint. Distortion in the scaling plots is normalised by the maximum entry of the fixed-point state-action metric for that \(N\), and effective size is reported using the information-equivalent counts described in 14.1.

14.3.0.2 Factor probes.

For the factor analysis in 2, we load the adaptive encoder at the selected near-optimal checkpoint for each \(N=2,\ldots,7\). The flat decoder representatives are projected to labels \(\bar S\) and \(\bar A\) as above. For a discrete state factor \(F(S)\), we compute \(I(F;\bar S)\). For a discrete action-side factor \(F(S,A)\), we compute \(I(F;\bar A\mid \bar S)\). Relevance is the same quantity divided by the entropy of the probed factor, so it lies in \([0,1]\) when the factor has positive entropy. State probes include global load variables, adjacent-pair and triplet histograms around the ring, failure-run statistics, isolated-failure indicators, and counts of vulnerable or critical alive machines. Action probes include whether the action is \(\mathrm{noop}\) or a reboot, target identity, target up/down status, wasted reboot indicators, failed-neighbour counts, target-centred triplet and five-site patterns, and the size of the alive or failed run containing the target. To avoid reporting many redundant probes, the table first groups related factors, chooses the strongest raw-mutual-information factor within each group, and then reports the top four state-side and action-side representatives averaged across \(N=2,\ldots,7\).

The factors reported in 2 are defined as follows.

• Triplet hist. is the eight-dimensional histogram of cyclic local patterns \((x_{i-1},x_i,x_{i+1})\), one count for each binary triplet.

• Pair hist. is the four-dimensional histogram of cyclic adjacent patterns \((x_i,x_{i+1})\), with one count for each binary pair.

• Failed count is \(\sum_i(1-x_i)\), the number of down machines.

• Max fail run is the length of the longest contiguous cyclic run of down machines. On the action side, the target of \(\mathrm{reboot}_i\) is machine \(i\), while \(\mathrm{noop}\) is assigned a separate no-target symbol.

• Target 5-bit is the five-site neighbourhood \((x_{i-2},x_{i-1},x_i,x_{i+1},x_{i+2})\) around the reboot target, with cyclic indexing.

• Target run size is the size of the contiguous failed run containing the reboot target, and is zero when the target machine is up.

• Target index is the identity of the machine selected for reboot.

• isolated target indicates whether the reboot target is down while both of its neighbours are up.

References↩︎