Effective Exploration Based on the Structural  Information Principles
Authors: Xianghua Zeng
Hao Peng
Angsheng Li
Venue: NeurIPS 2024 poster (2024)
Keywords: Deep Reinforcement Learning
Structural Information
Representation Learning
Entropy Maximization Exploration
Primary area: reinforcement_learning

Abstract: Traditional information theory provides a valuable foundation for Reinforcement Learning (RL), particularly through representation learning and entropy maximiza tion for agent exploration. However, existing methods primarily concentrate on modeling the uncertainty associated with RL’s random variables, neglecting the in herent structure within the state and action spaces. In this paper, we propose a novel Structural Information principles-based Effective Exploration framework, namely SI2E. Structural mutual information between two variables is defined to address the single-variable limitation in structural information, and an innovative embedding principle is presented to capture dynamics-relevant state-action representations. The SI2E analyzes value differences in the agent’s policy between state-action pairs and minimizes structural entropy to derive the hierarchical state-action struc ture, referred to as the encoding tree. Under this tree structure, value-conditional structural entropy is defined and maximized to design an intrinsic reward mechanism that avoids redundant transitions and promotes enhanced coverage in the state-action space. Theoretical connections are established between SI2E and classical information-theoretic methodologies, highlighting our framework’s rationality and advantage. Comprehensive evaluations in the MiniGrid, MetaWorld, and DeepMind Control Suite benchmarks demonstrate that SI2E significantly outperforms state-of-the-art exploration baselines regarding final performance and sample efficiency, with maximum improvements of 37.63% and 60.25%, respectively.

Effective Exploration Based on the Structural Information Principles
Xianghua Zeng', Hao Peng', Angsheng Li
State Key Laboratory of Software Development Environment, Beihang University, Beijing, China "Zhnngguaccun Laboratory, Beijing, China
(zengxianghua, penghao, angsheng\@buaa. edu.cn, cn, liangshengg@gaill .zgggggg .zgelab. edu.
Abstract
Traditional information theory provides a valuable foundation for Reinforcement Learning (RL), particularly through representation learning and entropy maximiza- tion for agent exploration. However, existing methods primarily concentrate on modeling the uncertainty associated with RL's random variables, neglecting the in- herent structure within the state and action spaces. In this paper, we propose novel Structural Information principles-based Effective Exploration framework, namely S12E. Structural mutual information between two variables is defined to address the single-variable limitation in structural information, and an innovative embedding principle is presented to capture dynamics-relevann state-action representations. The SI2E analyzes value differences in the agent's policy between itate-action pairs and minimizes structural entropy to derive the hierarchical state-action struc- ture, referred to the encoding tree. Under this tree structure, value-conditional structural entropy is defined and maximized to design an intrinsic reward mech- anism that avoids redundant transitions and promotes enhanced coverage the state-action space. Theoretical connections are established between SI2E and classical information-theoredt methodologies, highlighting our framework's 's ratio- nality and advantage. Comprehensive evaluations in the MiniGrid, Meta World, and DeepMind Control Suite benchmarks demonstrate that SI2E significantly outper- forms state-of-fe sate-of-the--nn art exploration baselines regarding final performance and sample efficiency, with maximum improvements of 37. 63% and 60. 60.25%, respectively.
Introduction
Reinforcement Learning (RL) has emerged pivotal technique for addressing sequential decision making problems, including game intelligence [Vinyals et al., 2019) Badia et al. 2020). robotic control [Andrychowicz et al. 2017 Liu and Abbeel 2021], and autonomous driving [Prathibal ct al. 2021 Pérez-Gil et al. [022] In the realm of RI., striking a balance between exploration and
exploitation crucial for optimizing agent policies and mitigating the risk of suboptimal outcomes, especially in scenarios characterized by high dimensions and sparse rewards (Zhang et al. 2021b).
Recently, advancements in ieformatioon-hhoreee approaches have shown promise for exploration in self-supervised settings. The maximum entropy framework over the action space [Haarnoja et al. 2017] has led to the development of robust algorithms such Soft Q-learning (Nachum et al. [017]] SAC Haarnoja et al. 2018), and MPO [Abdolmalcki et al. 2018). Additionally, various objectives focused maximizing state entropy are utilized to ensure comprehensive state coverage (Hazan ct al. 2019 [slam et al. 2019]. To facilitate the exploration of complex state-action pairs, MaxRenyi optimizes Rényi entropy across the state-action space (Zhang al.) 2021a] However, prevalent issue with entropy maximization strategies is their tendency to bias exploration towards low-value states, making them vulnerable to imbalanced value distributions in supervised settings. To mitigate
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

$2
50
$3
S4
5
22. 5g
six-state MDP with four actions
2g.41
five-state MDP with two actions
S
S2
33
maximize state-action entropy
[gp. n: 3/4
maximize structural entropy
0g
Figure 1: By incorporating the inherent state-action structure, we simplify the original six-state Markov Decision Process (MDP) with four actions to a five-state MDP with two actions, effectively reducing the size of state-action space from 24(6 4) to 10(5 2). Here, 8/2 and oe represent vertex communities (s2, $5} and foo, a1 ). respectively. In this scenario, a policy maximizing state- action Shannon entropy would encompass all possible transitions (blue color). In contrast, a policy maximizing structural entropy would selectively focus on crucial transitions (red color), avoiding redundant transitions between 82 and 85-
this, value-conditional state entropy is introduced to compute intrinsic rewards based on the estimated values of visited states [Kim et al., 2023). Due to their instability in noisy and high-dimensional environments, a Dynamic Bottleneck (DB) [Bai et al. 2021] is developed based on the Information Bottleneck (IB) principle (Tishby et al. 2000), thereby obtaining dynamics-relevame representations of state-action pairs. Despite their successes, existing information-theoree exploration methods have a critical limitation: they often overlook the inherent structure within state and action spaces. This oversight necessitates new approaches to enhance exploration effectiveness.
Figure illustrates simple six-state Markov Decision Process (MDP) with four actions. The different densities of the blue and red lines represent different actions. as indicated in the legend, leading to state transitions aimed at optimizing the return to the initial state so. Solid lines specifically denote actions ag and 01 The transitions between states $2 and st are deemed redundant as they do not facilitate the primary objective of efficiently returning to sg. Therefore, the state-action pairs (s2,0, az) and (ss, az) have lower policy values. A policy maximizing state-action Shannon entropy would encompass all possible transitions (blue color). In contrast, a policy incorporating the inherent state-action structure will divide these redundant state-action pairs into vertex uub-community and minimize the entropy of this sub-community to avoid visiting it unnecessarily. Simultaneously, maximizes state-action entropy, resulting in maximal coverage for transitions (red color) that are more likely to contribute to the desired outcome the simplified five-state MDP.
Departing from traditional information theory applied to random variables, structural information [Li and Pan (0166) has been devised to quantify dynamic uncertainty within complex graphs under a hicrarchical partitioning structure known as an "encoding tree". Structural entropy is conceptualized as the minimum number of bits required to encode a vertex accessible through single-step random walk and is minimized to optimize the encoding tree. However, this definition is limited to single- variable graphs and cannot capture the structural relationship between two variables. While the underlying graph can encompass multiple variables, current structural information principles are limited in treating these variables as a single joint variable, measuring only its structural entropy. This limitation prevents the effective quantification of structural similarity between variables, inherently imposing single-variabe variable constraint. Prior research on reinforcement learning using structural information principles [Zeng al. 2023blc has focused on independently modeling state action variables without simultancously considering state-action representations.
In this work, we propose SI2E, a novel and unified framework grounded in structural information principles for effective exploration within high digh-sinnnii and sparse-reward environments. Initially, we embed state-action pairs into a low- dimensionnl space and present an innovative representation learning principle to capture dynamics-relevant information and compress dynanics-irrelevann in- formation. Then, we strategically increase the state-action pairs' structural mutual information with subsequent states while decreasing it with current states. We analyze value differences among state-action representations to form complete graph and minimize its structural entropy to derive the

---

optimal encoding tree, thereby unveiling the hierarchical community structure of state-action pairs. By leveraging this identified structure, we design an intrinsic reward mechanism tailored to avoid redundant transitions and enhance maximal coverage in exploring the state-action space. Furthermore, we establish theoretical connections between our framework and classical coormation-theorees methodologies, highlighting the rationality and advantage of S12E. Our thorough evaluations across diverse and challenging tasks the MiniGrid, MetaWorld, and DeepMind Control Suite benchmarks have consistently shown SI2E's superiority, with significant improvements in final performance and sample efficiency, surpassing state-of-the-art exploration baselines. For further research, the source code is available at Our contributions summarized as follows:
A novel framework based on structural information principles, SI2E, is proposed for effective exploration in high-dimensional RL environments with sparse rewards.
An innovative principle of structural mutual information is introduced to overcome the single- variable constraint inherent in existing structural information and to enhance the acquisition of dynamics-relevam representations for state-action pairs.
A unique intrinsic reward mechanism that maximizes the value-conditional structural entropy is designed to avoid redundant transitions and promote enhanced coverage in the state-action space.
Our experiments various challenging tasks demonstrate that S12E significantly improves final performance and sample efficiency by up to 37.63% and 60.25%, respectively, compared to state-of-the-ar baselines.
2
Preliminaries
In this section, we formalize the definitions of fundamental concepts. The descriptions of primary notations are summarized in Appendix A. for ease of reference.
2.1 Traditional Information Principles
Consider the random variable pair (X,Y) Y) with a joint distribution probability denoted by p(z,1) v) E (0, 1). The marginal probabilities, p(x) and p(y), are defined as p(z) Σy p(z, v) and ply) is H Y) = -- [p(z,)) y) log p(z, y)], which quantifies the total uncertaunty in Z. Con- versely, the marginal entropies (X)) = - Σx [p(x) p(z) and H(Y) - -y, [p(y) - p(V) characterize the uncertainty in X and Y individually. The mutual information T(X;Y) p(z.w)
P(z, v). respectively. The joint Shannon entropy [Shannon 1953 of X and Y
Σn, p(z,z) log p(=)p(p) quantifies the shared uncertainty between X and Y. It satisfies the following relationship: I(X;Y) = H(X) + H(Y) - H(X,Y).
2.2 Reinforcement Learning
Within the context of RL, the sequential decision-making problem is formalized as a Markov Decision Process (MDP) [Bellman 1957]. The MDP characterized by tuple (O,A,, R 7), where O denotes the observation space, A the action space, P the environmental transition function, R the extrinsic reward function, and y E [0, 1) the discount factor. At each discrete timestep t, the agent selects an action E A upon observing
E O. This leads to a transition to a new observation oc+1 P(o,, at) and a reward rf E TR. The policy network is optimized to maximize the cumulative long-term expected discounted reward.
Maximum State Entropy Exploration. In environments with sparse rewards, agents are encouraged to explore the state space extensively, which can be incentivized by maximizing the Shannon entropy (S) of state variable S. When the prior distribution p(s) is not available, the non-parametric k-nearest neighbors (k-NN) entropy estimator (Singh et al. (2003) is employed. For given set of n independent and identically distributed samples from d, dimensiooaal space {x:))--) n- the entropy of variable is estimated as follows:
de Σ
(kL(X)=
log d (zx)) + C.
(1)
1=0
3

---

where d(z;) is twice the distance from F; to its k-th nearest neighbor, and C' is a constant term
Information Bottleneck Principle. In the supervised learning paradigm, representation learning aims to transform an input source X into a representation Z, targeted towards an output source Y. The Information Bottleneck (IB) principle (Tishby et al. 2000] refines this process by maximizing the mutual information 1 (Z; Y between 2 and Y, capturing the relevant features of Y within Z. Concurrently, the IB principle imposes a complexity constraint by minimizing the mutual information I[2; X) between Z and X, effectively discarding irrelevant features. To balance these objectives, the IB principle utilizes a Lagrangian multiplier, facilitating a balanced trade-off between the richness of the representation and its complexity.
2.3 Structural Information Principles
The encoding tree T' of an undirected and weighted graph G E) is characterized rooted tree with the following properties: 1) Each tree node a in ' corresponds to a subset of graph vertices V. S V. 2) The subset VA of tree root À encompasses all vertices in V. 3) Each subset V,, of leaf node v in T only contains a single vertex v, thus V, = {u)) 4) For each non-leaf node a, the number of its children is assumed la, with the i-th child specified a,. The collection of subsets Vo....,, Va.., constitutes a sub-partition of V..
Given encoding tree T whose height is at most K, the K K-dimensional structural entropy of graph G is defined as follows:
H² =-
Σ
Ja vol
log vol(a) vol(a-)
H (G) min H² (G).
where Ia is the weighted sum of all edges connecting vertices within the subset Va to vertices outside the subset Va.
3 Structural Mutual Information
In this section, we address the single-variable constraint prevalent in existing structural information principles and introduce the concept of structural mutual information for subsequent state-action representation learning within our SI2E framework.
Given the random variable pair (X, with |X| |Y| n, we construct an undirected bipartite graph Gay to represent the joint distribution of X and Y. In Gzy, each vertex æ E X connects to each vertex y E Y via weighted edges, where the weight of each edge equals the joint probability p(x, y). Notably. no edges connect vertices within the same set, X or Y. and the total sum of the edge weights is 1, Ez.g p(x, y) 1. Each single-step random walk in Gzy accesses either a vertex from X or Y. The structural entropy of variable X in Gay is defined as the number of bits required to encode all accessible vertices in the set X. is calculated using the following formula:
p(x)
p(=)
p(x)
p(x)
2 log p(xx
ST (X)(X)) = Σ
log
Σ
(3)
(G
vol (Gll)
2
TEX
ZEX
where the sum of all vertex degrees is twice the total sum of edge weights, resulting in vol 2.
The structural entropy 11 is defined similarly. We restrict the partitioning structure of Gzy to 2- 2-layer approximate binary trees, denoted as T to calculate the required bits to encode accessible vertices in X or Y, defined as the joint structural entropy. This tree structure mandates that each intermediate node (neither root nor leaf) has precisely two children. We begin by initializing one-layer encoding tree, Toy designating each non-root node a's parent as the root X, with a By applying the stretch operator from the HCSE algorithm [Pan al. 2021]. we pursue iterative and greedy optimization of 22 further detailed in Appendix A.2 The optimal encoding tree, Thy for Gzy and the joint entropy under T are achieved through:
T arg min H (Gay), H (X,Y) (Gay): TET?
Utilizing 2-layer approximate binary trees as the structural framework ensures computational tractabil- ity and more complex structures will increase the cost of increased computational complexity, which can be prohibitive for practical applications.

---

I. State-action
H (X) + (0)+HMMMM Hx,
Representation
60000000 60000000
HK
max m (exxxi(Zee0 Se+1) min (z,
Embeddingb) Distribution Graphs
<) Encoding Trees T d) Mutual Information
II. Efficient Exploration
construction
(Vo fgx Te =r + rf Intrinsic Reward L.NNEstimator
a()
subb-communitg
verticss
State-action Space
d) Distribution Graph Ga
HCSE
max max Hi (G(a) HT (Gaa))H(SS
Value Norm
structural entropy
(1((1))
m()illa
60000000000
RL Algorithhh
1b) State-action Graph G Opttmal Encoding Tree Toh
e) Value-condiiional Entrony
Figure 2: The S12E's overview architecture, including state-action representation learning and maximum structural entropy exploration.
We derive the following proposition regarding T2, with the detailed proof provided in Appendix B.1 Proposition 3.1. Consider an undirected graph G = EV with vertices U; and U in V. If the edge (vi, V5) absent from E,, then in the 2-layer approximate binary optimal encoding tree T E TT2, there does not exist any non-root node such that both and ty are included in its subset Va-
Each intermediate node a E Th corresponds to subset comprising exactly one vertex and one vertex, thus establishing one-to-one matching structure between variables X and Y. The i-th intermediate node Ty ordered from left right, denoted (gg. Within this subset, the and vertices are labeled z; and y/, respectively.
To define structural mutual information accurately, is essential to consider the joint entropy of two variables under various partition structures. We introduce an 1-transformation applied to Ty to systematically traverse all potential one-to-one matching of these variables, providing comprehensive measure of their structural similarity. Given an integer parameter > 0, this transformation generates a new 2-layer approximate binary tree, T representing an alternative one-to-one matching structure.
Definition 3.2. For each intermediate node as Ty the x and vertices TV. are specified as TV. (1r,,,),, where i' = (i + mod n.
The resulting tree T is equivalent to the optimal tree TV when / = 0. We provide an example in Appendix A.3 with n 4 for an intuitive understanding of the described process.
Definition 3.3. Leveraging the relationship I(X; Y) = H(X) HYY H (X,Y) in traditional
information theory, we formally define the structural mutual information, y (s((X;Y) as follows:
ST (X:Y)
(X) +X))+HSI(() - H (x,x) Σ 1=0
plz,, U3) log p(x:) + p(v;)
2
(5)
The detailed derivation provided in Appendix C.I Structural mutual information quantifies the average difference between the required encoding bits of accessible vertices of a single variable and the joint variable. The following theorem outlines the connection between Ts (X:Y) and I(X;Y). with detailed proof in Appendix B.2
Theorem 3.4. For a tuning parameter O < 1, its holds for the structural mutual information Ist (X; traditional mutual information T(X;Y), and joint Shannon entropy H(X, Y) that:
T(X:Y) 1s (X; s +1 -X(X))).
4 The Proposed SI2E Framework
In this section, we describe the detailed designs of the proposed SI2E framework, which captures dynamic-relevant state- acte-nction representations through structural mutual information (see Section
5

---

4.1 and enhances state-action coverage conditioned by the agent's policy by maximizing structural entropy (see Section 4.2 The overall architecture of our framework is illustrated in Figure 2
4.1 State-action Representation Learning
To effectively learn dynamics-relevant state-action representations, we present an innovative embed- ding principle that maximizes the structural mutual information with subsequent states and minimizes it with current states.
Structural Mutual Information Principle. In this phase, the input variables timestep t encompass the current observation O₂ and the action As, with the target being the subsequent observation O++1- We denote the encoding of observations O₂ and Ot+1 1 as states St and S1+1, respectively. We aim to generate a latent representation Z, for the tuple (S,, As), which preserves information relevant to S while compressing information pertinent S.. This embedding process mentioned above is detailed as follows:
S. fs(O,), S (s(0+t1), 74 S=(S,, As),
where fa and fa are the respective encoders for states and state-action pairs (step a in Figure D. For the state-action embeddings Zz, we construct two undirected bipartite graphs, G2s and Gzs', as shown in step I. b of Figure 2 These graphs represent the joint distributions of Ze with the current states S and subsequent states S1+1- In step I. c of Figure [ generate 2- 2-layer approximate binary trees for Gzs and Gzs and calculate the mutual information / (2, S.) and 1 (2,, Se+.1) using Equation 5. Building upon the Information Bottleneck (IB) (Tishby al. 2000], we present embedding principle that aims to minimize /S/ (Z,; S.) while maximizing (7, 1) as demonstrated in step I. d of Figure 2 When the joint distribution between variables Z and S shows a one-to-one
prrrepooddenc-mmaanng for each 2, E Ze value, there is a unique $1+1 E St+1 corresponding to it, and vice versa- their mutual information takes its maximum value. We introduce theorem to elucidate the equivalence between 1 (21; S(+1) and 1Z; S1+1) under this condition.
Theorem 4.1. For a joint distribution of variables X and Y that shows a one-to-one correspondence, S (X;;)Y) equals (Y;
detailed proof is provided in Appendix B.3 When Z, and S, are mutually independent, the mutual
information T(Z;; S.) attains its minimum value. Our TS/ (Zr; Se) goes beyond this, incorporating the joint entropy (Z,, St) according to Theorem 3.4 This integration effectively eliminates the irrelevant information embedded in the representation variable Z,, significant step in research. Consequently, structural mutual information can be considered reasonable and desirable learning objective for acquiring dynamics-relevant state-action representations.
Representation Learning Objective. Due to the computational challenges of directly minimizing (Z, St). we formulate variational upper bound I [Z,; St) + (Z, (S.) + (S,) (see Appendix Noting that the term (S,) is extraneous to our model, we equate the minimization of (Ze; S,) to the minimization of I (2;; and H (Z,
By employing a feasible decoder to approximate the marginal distribution of Z₁, we derive an upper bound of T(2;; S:) (See Appendix C.3 as follows:
[(2;; S.) S
Σ (p(z,, st) (Kz(p(2)ss))llmm
& Lup
(8)
To concurrently decrease the conditional entropy HZz(S,,) we introduce a predictive objective (See Appendix C.4) through a tractable decoder 4=1= for the conditional probability p(z(ls)) as follows:
H(Z.(S) - Σ p(2,, st) -log
1
L=Is+
(=)0(2)(31)
where Lzjs represents the log- ligeeiiel of Z, given S..
To efficiently optimize 1 (Ze; St41), we maximize its lower bound, [(Ze; St41), as detailed in Theorem 3.4. By utilizing an alternative decoder qs/= for the conditional probability p())+1)2)) we obtain a lower bound of [Ze S141) (See Appendix C.5 as follows:
1 1(2; S.+1)
Σ [p(ze, S141) ) log (.1=(544112)) A Lules
(10)
where Lole denotes the likelihodd of S conditioned on Z,-

---

Within our SI2E framework, the definitive loss for representation learning is a combination of the above bounds, L Lup + Lals + n Ls|=- where 1) Lagrange multiplier used maintain equilibrium among the specified terms.
4.2 Maximum Structural Entropy Exploration
We have designed unique intrinsic reward mechanism address the challenge of imbalance exploration towards low-value states in traditional entropy strategies, as discussed by [Kim et al. 2023]. Specifically, we generate a hierarchical state-action structure based on the agent's policy and define value-conditional structural entropy as an intrinsic reward for effective exploration.
Hierarchical State-action Structure. Derived from the history of agent-environment interactions, we extract state-action pairs (step II. a in Figure 2 to form a complete graph G.a (step II. b in Figure 2 that encapsulates the value relationships caused by the agent's policy. Within this graph, any two vertices vi and vy is connected by an undirected edge whose weight waj is determined as: Wi; = [|
xs² a;) 1l2 The state-action pairs (sf, af) and (s/: a²) are associated with vertices v; and vj, respectively, We minimize the 2-dimensional structural entropy this graph Gao to generate its 2-layer optimal encoding tree, denoted as T (step II. in Figure 2). This tree T delineates a hierarchical community structure among the state-action vertices, with the root node corresponding community encompassing all vertices. Each intermediate node in T corresponds to sub-community, including vertices that share similar π values.
Value-conditional Structural Entropy. To measure the extent of the policy's coverage across the state-action space, we construct an additional distribution graph G',, (step II. d in Figure The graph Gos, shares the same vertex set as G The following proposition confirms the existence of such a graph, with a detailed proof provided in Appendix B.4
1- .a, for all state- action pairs, there exists a weighted, undirected, and connected graph Gem where each vertex's ss degree di equals its visitation probubility p(s;, at).
Proposition 4.2. Given positive visitation probabilities
In the graph G'za the set of all state-action vertices is denoted as Vo, and the set of all state- action sub-communities is denoted Vi. The Shannon entropies associated with the distribution of visitation probabilities for these sets are represented as H/ (V,) and HV1)), respectively, where (V)) H (S,, At). Within the 2-layer state-action community represented by T we define the structural entropy of G² using Equation [ denoted as H (T*a(G'.a) (step II. e in Figure 2 The following theorem delineates the relationship between the value-conditional entropy H SM (G G',) with the action Shannon entropy H (S,, As). A detailed proof is provided in Appendix B.5
Theorem 4.3. For tuning parameter 0 < C S 1, it holds for the structural entropy H (G'au) and the Shannon entropy H (S,,, Ar) that:
Ç ((,, Ad) S H(V) H(V)) S HTi (S,,AA))
(11)
where H(V)) (VV) is variational lower bound of (G'a). On the one hand, the term (V)) ensures maximal coverage of the entire state-action space, analogous to the traditional Shannon entropy. On the other hand, the term HV11) mitigates uniform coverage among state-action sub- communities with diverse π values, thus addressing the challenge of imbalance exploration. By identifying the hierarchical state-action structure caused by the agent's policy, the SI2E achieves enhanced maximum coverage exploration, thereby guaranteeing its exploration advantage.
Estimation and Intrinsic Reward. Considering the impracticality of directly acquiring visitation probabilities, we employ the h--N entropy estimator in Equation [
to estimate the lower bound:
H(V)) - (V))
logd( d(
log d(v!) C. of Vo, of E Vi. (12)
TIO
where d. is the dimension of action embedding, ny and nı are the vertex numbers in Vo and Vi, and d(v) is twice the distance from vertex v to its k-th nearest neighbor. By ignoring the constant term Equation 12 we define the intrinsic reward rf and train RL agents to address the target task using combined reward r, rf B.r (step II. fn Figure where 3 is positive hyperparameter that modulates the trade-off between exploration and exploitation. The pseudocode, complexity analysis, and limitations of our framework are provided in Appendix
7

---

Table 1: Summary of success rates and required steps to achieve target rewards in MiniGrid and Meta World tasks: "average value + standard deviation" and "average improvement". Bold: the best performance, underline: the second performance.
MiniGni Navigation
Dod8sneDoors-6x6
SimpleC CompleCrosingSSONN
KeyCoriderS3RI
Success Rate (%)
Required (R3)
(R)
Success Rate (%)
Required Step (K)
Success Rate (%)
Required Step (K)
A2C
88.18 3.46
520.08 15.87
56.57 2:26
658.74 21.01
A2C+SE
88.59 +: 4.62
3911.9 +: 66.14
87.20 1: 4.94
463.86 + 38.
A2C+VCSE
79.82 7.26
11G1 90 241 .59
91.30 1.92
201.02 25.60
86.01 0.91
190 20 6.11
A2C+S12E
85,80 + 1.48
461.90 + 61.03
93.64 1.63
139.17 + 27.03
94,20 0.42
129.06 + 6.
Abs. Avg.
3,98
700,0160
2.31|2.56)
61,85(31.99)
7,0088.03)
61.14132. 15)
MiniCind
Door Key-Gx6
Door Jaorkey-3x8
Unlock
Navigation
Success Rute (%)
Required Step (K)
Success Rute (%)
Required Step (K)
Success Rute
Required Step (K)
A2C
V2.67 1 8.47
567.21) a: 195.57
92,48 1: 11.36
009.75 1: 154.71
A2C+SE
93.18 + 6.81
176.31 + 94.63
72.60 + 20.32
1515 = 321 28
91.31 + 18.37
631.37 = 240.51
A2C+VCSE
94.08 2.58
336.76- + 19.84
94.32 + 11.09
1900.96
308.
83.12 3-43
405.22 62. 22
A2CFS12E
97.04
F 1.52
230.00 + 19.89
98.58 + 3.11
1090.99 125.17
97.13 +: 3.35
309,14 + 53.71
Abs.(%)) Avg.
2.0033111 T
(06.15(31.52)
4.26(4.32] 0
424.83(25.03) 4
4.01(4.31) F
36.08(23.71) I
MeraWorld
Button Press
Door Open
Drawer Open
Manipulation
Success Rate (36
Reguired Step (J))
Success Rate (%)
Required Step (KC)
Success Kate (76)
Required Step
DRQv2
U1.55 = 1.61
103..0 2. 5.0
DrQv24SE
93.05 7.67
96.0 06.00:
25.31 7.90
DrQS2+VCSR
89.80
+ 3.29
77.5 + 2.5
80.90 + 10.10
62.74 + 7.46
175.0 + 5.0
DRQN2+SPJE
99,60
0.57
62.5 7.5
48.77 1,05
87.5 2.5
95.96 3.00
82,5 2.5
Abs.(%)) Avg.
5.05;5.347
19.0019 1
14.87 18.381
15.388)
322.5(52.88)
MetaWorld
Taucel Close
Faucet Open
Window Open
Manigulation
Success (%6)
Required (IK)) (IS)
Success Rate (X)
Required Step (X)
Success Rate (36)
Required SSep (K)
DrQv2
13.33 = 1.92
58.18 1.30
192.5 # 2.5
DrQu24SE
92.36 3.08
71.25 6.25
93.14 + 2.03
172.5
DrQV2+VCSE
04.21 :: 1.74
60.0 4: 5.0
87.23 5.29
67.5 4 5.0
83.17 1: 1.45
127.5 4: 7.5
99.37
97,06 1.39
51.25
19.46 00335
77.5 2.5
Ab6 Avg.
3.10:3.877
3255
9.83 (1.
16,25(24.07
6.25)
50.0130022]]
5 Experiments
In this section, we present comprehensive suite of comparative experiments on MiniGrid (Chevalier: Boisvert et al., 2018) MetaWorld (Yu et al. 2020]. and the DeepMind Control Suite (DMControl) (Tunyasuvunakool et al. 2020 to evaluate the effectiveness of SI2E in terms of both final performance and sample efficiency. Consistent with previous work [Zeng et al. 2023c]. we measure the required steps to attain specified rewards (0.9 times SI2E's convergence reward) as benchmark for assessing sample efficiency. For the SI2E implementation, we employ a randomly initialized encoder optimized to minimize the combined loss L. All experiments are conducted with 10 different random seeds, and the learning curves are delineated in Appendix E
5.1 MiniGrid Evaluation
Initially, we assess our framework on navigation tasks using the MiniGrid benchmark, which includes goal-reaching tasks in sewrse-reward environments. This setting is partially observable: the agent receives a 7 x 7 x 3 embedding of the immediate surrounding grid rather than the entire grid. For comparative purposes, we employ the A2C agent (Mnih et al.) 2016) with Shannon entropy (SE) (Seo et al. [02T] and value-based state entropy (VCSE) [Kim et al. 2023) as our baselines. Table [ (upper) displays the average values and standard deviations of success rates and required steps for various navigation tasks. The tasks encompass navigation with obstacles SSippleCrosingS9NN long-horizon navigation (RedBlueDoors, DoorKey, and Unlock), and long- long-horizon navigation with obstacles (eyCooridorS3RR). The SI2E consistently exhibits enhanced final performance and sample efficiency across tasks, with an average success rate increase of 4.99 4.92%, from 89.97% to 94. 40%. and an average decrease in required steps of 38.10%, from 635.65 K to 393.47K. In the RedBlueDoors task, where baseline performances are inadequate, our SI2E significantly improves the success rate from 79.82% to 85.80% and reduces the required steps from 1161.90K to 461.90K.
5.2 Meta World Evaluation
We further evaluate the SI2E framework on visual manipulation tasks from the Meta benchmark, which presents exploration challenges due to its large state space. We select the model-free DrQv2 algorithm as the underlying RL methodology. Adhering to the setup of (Seo et al. 2023 we employ the same camera configuration and normalize the reward with scale of I. We summarize the success rates and required steps for all exploration methods across six World tasks in Table I (lower).
8

---

Table 2: Summary of average episode rewards for control tasks in DMControl, encompassing two cartpole tasks characterized by sparse rewards: "average value + standard deviation" " and "average improvement" (absolute value(%)) Bold: the best performance, underline: the second performance.
Domain, Tisk
Hopper Staod
Cheetah Run
Quadruped Walk
Peadulum Swingup
Carpole Balonee
Carppole Swingup
DrQv2
57.59 + 11.30
223.22 + 123.93
280.79 + 24.17
424.21 + 246.96
158.97 + 22.55
DIQU2ASE
313.39
228.
126.21
2.92
62.21
DCQSE
711.32
30.84
406.22
+ 22.20
243.74 + 29.91
824.17 90.00
208.61 9.58
207 70 + 50.38
DIQV2+MADE
717,09 + 112.91
300.59
53.74
262.63 + 23.92
672.11 31.63
996.16 + 10.00
701 = 11.75
DIQVZASTZE (Owrs)
797.17 53.21
464.08
29.32
399.51
29.05
885.50
38. 28
999,58 2.97
795.09 90.40
(56. Avg.
S1.08(1.117)
7.82(177))
101.24(37.63)
61.33[1.44)
0.93((0.9)
87.33 12.34)
Our SI2E framework enables the DrQv2 agent to solve all tasks with an average success rate of 97.87 after an average of 64.79K environmental steps, significantly outperforming other baselines. Specifically, in the Door Open task, all baselines struggle to achieve meaningful success rate with a satisfactory number of environmental steps. This result demonstrates the S12E's effectiveness in improving and accelerating agent exploration in challenging tasks with expansive state-action spaces.
5.3 DMControl Evaluation
Subsequently, we evaluate our framework across various continuous control tasks within the DM- Control suite. As the foundational agent, we choose the same DrQv2 algorithm, which operates on pixel-based observations. We incorporate a state-action exploration baseline, MADE (Zhang al. 2021b), for more comprehensive comparison. We evaluate all exploration methods across six continuous control tasks, documenting the episode rewards in Table Observations reveal that S12E remarkably increases the mean episode reward in each DMControl task. Specifically, in the Cartpole S Swingup task characterized by sparse rewards, our framework boosts the average reward from 707.77 76 795.09, resulting 12.34% improvement in the final performance. Moreover, we compare the sample efficiency of SI2E and the best-performing baseline in Appendix D3
These results not only demonstrate the effectiveness of SI2E in acquiring dynamics-relevan rep- resentations for state-action pairs but also highlight its potential to motivate agents to explore the state-action space. To better understand the rationality and advantage of the SI2E framework, provide visualization experiments in Appendix E.4
5.4 Ablation Studies
To further investigate the impact of two critical components within the SI2E framework, embedding principle (Section 4.T and intrinsic reward mechanism (4.2). we perform ablation studies on Meta-
World and DMControl tasks, focusing on two distinct variants: (i) SI2E-DB, which utilizes the DB bottleneck (Bai et al. 2021] for learning state- action representations, and (ii) -CCE, employing the -f-hc--rrt VCSE approach [Kim al. 2023] for calculating intrinsic rewards. As depicted in Figure 3 SI2E surpasses all variants regarding final performance and sample efficiency. This outcome underscores the essential role of these critical components in conferring S12E's superior capabilities. Additional ablation studies for the parameters B and n are available in Appendix E.5
Droor Open
Paocot Open
Corgole Balrnce Sparss
Carpole Suinpe Spane
1093
1.00
800
750
Stacio Raae
0.6
500
Eptodo
Spiindo
432
250
S12 DR
S12F.06 D0
S125 DB
VOSE
202
SIZE
S128
3IZE
$125
2
3
1
LEKIS"
20x10"
2
Envionieentl Stp
Envionmentta
Enstoommenal
(a) Meta World tasks
(b) DMControl tasks
Figure Learning curves across MetaWorld and DMControl tasks for ablation studies.
Related Work
6.1 Maximum Entropy Exploration
Maximum entropy exploration has evolved from focusing initially on unsupervised methods to incorporating task rewards in more advanced supervised models. In the unsupervised paradigm,

---

agents autonomously acquire behaviors by using state entropy as an intrinsic reward for exploration [Liu and Abbeel 202T Mutti al. 2022 Yang and Spaan 2023] In contrast, in the supervised paradigm, agents aim to maximize state entropy in conjunction with task rewards (Seo et al. 2021 Yuan et al. 2022].
However, these methods face challenges due to imbalances in the distributions of states with differing policy values. To address this issue, a value-based approach (Kim al. 2023] has been proposed, which integrates value estimates into the entropy calculation to ensure ba balanced exploration. Nev- ertheless, the effectiveness of this approach heavily depends on the partitioning structure of states according to policy values, requiring prior knowledge about downstream tasks.
In this work, leverage structural information principles to derive the hierarchical state-action structure in an unsupervised manner. We further define the value-conditional structural entropy as an intrinsic reward achieve more effective agent exploration. Compared to current maximum entropy explorations, SI2E introduces an additional sub-community entropy and minimizes this entropy to motivate the agent to explore specific sub-communities with high policy values. This approach helps avoid redundant explorations within low-value sub-communities and achieves enhanced maximum coverage exploration. Our method allows for balanced exploration without requiring prior knowledge of downstream tasks, effectively addressing the limitations of previous approaches.
6.2 Representation Learning
Novelty Search [To al. 2020) and Curiosity Bottleneck [Kim et al. 2019b] leverage the Infor- mation Bottleneck principle for effective representation learning. Additionally, the EMI method (Kim et al. 2019a maximizes mutual information in both forward and inverse dynamics to develop desirable representations. However, these methods are limited by the lack of an explicit mechanism to address the white noise issue in the state space. To overcome this challenge, the Dynamic Bottleneck model Bai et al. 202T is introduced for robust exploration in complex environments.
Our work defines structural mutual information to measure the structural similarity between two variables for the first time. Additionally, we present an innovative embedding principle that incorpo- rates the entropy of the representation variable. This approach more effectively eliminates irrelevant information than the traditional information bottleneck principle.
6.3 Structural Information Principles
Since the introduction of structural information principles [Li and Pan 2016). these principles have significantly transformed the analysis of network complexities, employing metrics such structural entropy and partitioning trees. This innovative approach has not only deepened the understanding of network dynamics-eves even in the context of multi-relational graphs [Cao al. [024a]- but has also led to a wide array of applications across different domains. The application of structural information principles has extended various fields, including graph learning [Wu al. 2022]. skin segmentation
[Zeng et al. 2023a]. and the analysis of social networks [Peng et Zeng et al. 2024 Cao et al.
2024b]. In the domain of reinforcement learning. these principles have been instrumental in defining
hierarchical action and state abstractions through encoding trees (Zeng et al. 2023b c marking a
significant advancement robust decision-mall makinn frameworks.
7 Conclusion
We propose SI2E, novel exploration framework based on structural information principles. This framework defines structural mutual information to effectively capture state-action representations relevant environmental dynamics. It maximizes the value-conditional structural entropy to enhance coverage across the state-action space. We have established theoretical connections between SI2E and traditional advantages. Through extensive and comparative evaluations, SI2E significantly improves final performance and sample efficiency over state-of-the-art exploration methods. Our future work includes expanding the height of encoding trees and the range of experimental environments. Our goal is for SI2E to remain robust and adaptable tool in reinforcement learning, particularly suited to high-dimensional and sparse-reward contexts.
methodologies, underscoring the framework's 's rationality and
10

---

Acknowledgments
The corresponding authors are Hao Peng and Angsheng Li. This work is supported by the National Key R&D Program of China through grant 2021YFB171480 NSFC through grants 61932002, 62322202, and 62432006, Beijing Natural Science Foundation through grant 4222030, Local Science and Technology Development Fund of Hebei Province Guided by the Central Government of China through grant 246Z0102G, Hebei Natural Science Foundation through grant F2024210008, and Guangdong Basic and Applied Basic Research Foundation through grant 2023B15151
References
Abbas Abdolmaleki, Jost Tobias Springenberg. Yuval Tassa, Remi Munos, Nicolas Heess, and Martin Riedmiller. Maximum a posteriori policy optimisation. In International Conference on Learning Representations, 2018.
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay. Advances in neural information processing systems, 30, 2017.
Adrià Puigdomênech Badia, Bilal Piot, Steven Kapturowski, Pablo Sprechmann, Alex Vitvitskyi, Zhaohan Daniel Guo, and Charles Blundell. Agent57: Outperforming the atari human benchmark. In International conference on machine learning, pages 507-517. PMLR, 2020.
Chenjia Bai, Lingxiao Wang, Lei Han, Animesh Garg, Jianye Hao, Peng Liu, and Zhaoran Wang. Dynamic bottleneck for robust self-supervised exploration. Advances in Neural Information Processing Systems, 34:17007-17020, 2021.
Richard Bellman. A markovian decision process. Journal of Mathematics and Mechanics, pages 679-684, 1957.
Yuwei Cao, Hao Peng, Angsheng Li, Chenyu You, Zhifeng Hao, and Philip S. Yu. Multi-relational structural entropy. In The 40th Conference Uncertainty in Artificial Intelligence, pages 4289- 4298, 2024a.
Yuwei Cao, Hao Peng, Zhengtao Yu, and Philip S. Yu. Hierarchical and incremental structural entropy minimization for unsupervised social event detection. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 8255-8264 2024b.
Maxime Chevalier-Boisvent Lucas Willems, and Suman Pal. Minimalistic gridworld environment for openai gym. 2018.
Tuomas Haarnoja, Haoran Tang, Pieter Abbeel, and Sergey Levine. Reinforcement learning with deep energy-based policies. In International conference machine learning, pages 1352-1361. PMLR, 2017.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International conference on machine learning. pages 1861-1870. PMLR, 2018.
Elad Hazan. Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. International Conference on Machine Learning, pages 2681-2691. PMLR, 2019.
Riashat Islam, Raihan Seraj. Pierre-Luc Bacon, and Doina Precup. Entropy regularization with discounted future state distribution policy gradient methods. ArXiv, 2019.
Daejin Jo, Sungwoong Kim, Daniel Nam, Taehwan Kwon, Seungeun Rho, Jongmin Kim, and Donghoon Lee. Leco: Learnable episodic count for task-specific intrinsic reward. Advances in Neural Information Processing Systems, 35:30432-30445, 2022.
Dongyoung Kim, Jinwoo Shin, Pieter Abbeel, and Younggyo Seo. Accelerating reinforcement learning with value-conditional state entropy exploration. arXiv preprint arXiv:2305.19477 2023.

---

Hyoungseok Kim, Jackyeom Kim, Yeonwoo Jeong, Sergey Levine, and Hyun Oh Song. Emi: Exploration with mutual information. In International Conference on Machine Learning, pages 3360-3369. PMLR, 2019a.
Youngjin Kim, Wontae Nam, Hyunwoo Kim, Ji-Hoon Kim, and Gunhee Kim. Curiosity-botleneck: Exploration by distilling task-specific novelty. In International conference on machine learning, pages 3379-3385 PMLR, 2019b.
Angsheng and Yicheng Pan. Structural information and dynamical complexity of networks. IEEE Transactions Information Theory, 62:3290-3339, 2016.
Hao Liu and Pieter Abbeel. Behavior from the void: Unsupervised active pre-training. Advances in Neural Information Processing Systems, 34:1 1459119998,,,, 2021.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement PMLR, 2016.
learning. In International conference machine learning, pages
Mirco Mutti, Riccardo De Santi, and Marcello Restelli. The importance of non-markovianity in maximum state entropy exploration. In International Conference on Machine Learning, pages 16223-16238 PMLR, 2022.
Ofrr Nachum, Mohammad Norouzi, Kelvin Xu, and Dale Schuurmans. Bridging the gap between value and policy based reinforcement learning. Advances neural information processing systems, 30, 2017.
Yicheng Pan, Feng Zheng, and Bingchen Fan. An information-theoretic perspective of hierarchical clustering. arXiv preprint arXiv:2108.. 06036, 2021.
Deepak Pathak, Pulkit Agrawal, Alexei Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In International conference on machine learning, pages 2778-2787. PMLR, 2017.
Hao Peng. Jingyun Zhang, Xiang Huang, Zhifeng Hao, Angsheng Li, Zhengtao Yu, and Philip S Yu. Unsupervised social bot detection via structural information theory. ACM Transactions on Information Systems, pages 1-42.
Óscar Pérez-Gil, Rafael Barea, Elena López-Guillén, Luis M Bergasa, Carlos GoeezaH Rodrigo Gutiérrez, and Alejandro Diaz-Diaz. Deep reinforcement learning based control for autonomous vehicles in carla. Multimedia Tools and Applications, 8 81(3):3553-3576 2022.
Sahaya Beni Prathiba, Gunasekaran Raja, Kapal Dev, Neeraj Kumar, and Mohsen Guizani. A hybrid deep reinforcement learning for autonomous vehicles smart-platooning. IEEE Transactions on Vehicular Technology, 70(1 70(12):13340-13333 2021.
Younggyo Sco, Lili Chen, Jinwoo Shin, Honglak Lee, Pieter Abbeel, and Kimin Lee. State entropy maximization with random encoders for efficient exploration. In International Conference on Machine Learning, pages 9443-9454. PMLR, 2021.
Younggyo Seo, Danijar Hafner, Hao Liu, Fangchen Liu, Stephen James, Kimin Lee, and Picter Abbeel. Masked world models for visual control. In Conference on Robot Learning, pages 1332-1344. PMLR, 2023.
Claude Shannon. The lattice theory of information. Transactions of the IRE professional Group on Information Theory, 1(1):105-107, 1953.
Harshinder Singh, Neeraj Misra, Vladimir Hnizdo, Adam Fedorowicz, and Eugene Demchuk. Nearest neighbor estimates of entropy. American journal of mathematical and management sciences, 23 (3-4):301331,, 2003.
Ruo Yu Tao, Vincent Frangois-Lavet, and Joelle Pineau. Novelty search in representational space for sample efficient exploration. Advances Neural Information Processing Systems, 33:81 8126. 2020.
12

---

Naftali Tishby. Fernando C Pereira, and William Bialek. The information bottleneck method. arXiv preprint physiccs00004057, 2000.
Saran Tunyasuvunakool, Alistair Muldal, Yotam Doron, Siqi Liu, Steven Bohez, Josh Merel, Tom Erez, Timothy Lillicrap, Nicolas Heess, and Yuval Tassa. dm_control: Software and tasks for continuous control. Software Impacts, 6: 6:100022, 2020.
Oriol Vinyals, Igor Babuschkin, Wojeiech M. Czarnecki, and etc. Alphastar: Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782)3350 -544,, 2019.
Shanchuan Wan, Yujin Tang, Yingtao Tian, and Tomoyuki Kaneko. Deir: efficient and robust
exploration through discriminative sesitive--mdellbbbsdde episodic intrinsic rewards. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, pages 4289-4298, 2023,
Junran Wu, Xueyuan Chen, Ke Xu, and Shangzhe Li. Structural entropy guided graph hierarchical pooling. In ICMI,, pages 24017-24030. PMLR, 2022.
Qisong Yang and Matthijs TJ Spaan. Cem: Constrained entropy maximization for task-agnostic safe exploration. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 10798-10806, 2023.
Denis Yarats, Rob Fergus, Alessandro Lazaric, and Lerrel Pinto. Mastering visual continuous control: Improved data-augmented reinforcement learning. In International Conference on Learning Representations, 2021.
Tianhe Yu, Deirdre Quillen, Zhanpeng He, Ryan Julian, Karol Hausman, Chelsea Finn, and Sergey Levine. Meta-world: A benchmark and evaluation for multi-task and meta reinforcement learning. In Conference on robot learning. pages 1094-1100, PMLR, 2020.
Mingqi Yuan, Man-On Pun, and Dong Wang. Rényi state entropy maximization for exploration acceleration in reinforcement learning. IEEE Transactions Artificial Intelligence, 2022.
Guangjie Zeng. Hao Peng, Angsheng Li, Zhiwei Liu, Chunyang Liu, Philip S Yu, and Lifang He. Unsupervised skin lesion segmentation via structural entropy minimization on multi-scale superpixel graphs. In IEEE ICDM, pages 768-777, 2023a.
Xianghua Zeng, Hao Peng, and Angsheng L.i. Effective and stable role-hased multi-agent collab- oration by structural information principles. Proceedings of the AAAI Conference on Artificial Intelligence, (10): 11780, Jun. 2023b.
Xianghua Zeng, Hao Peng, Angsheng Li, Chunyang Liu, Lifang He, and Philip S Yu. Hierarchical state abstraction based on structural information principles. In IJCAI, pages 4549 2023c.
Xianghua Zeng, Hao Peng, and Angsheng Li. Adversarial socialbots modeling based on structural information principles. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 392-400, 2024.
Chuheng Zhang, Yuanying Cai, Longbo Huang, and Jian Li. Exploration by maximizing rényi entropy for reward-free rl framework. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 10859-10867,, 2021a.
Tianjun Zhang, Paria Rashidinejad, Jiantao Jiao, Yuandong Tian, Joseph Gonzalez, and Stuart Russell. Made: Exploration via maximizing deviation from explored regions. Advances in Neural Information Processing Systems, 34:9663 9680, 2021b.
Ruijie Zheng, Xiyao Wang, Yanchao Sun, Shuang Ma, Jieyu Zhao, Huazhe Xu, Hal Daumé III, and Furong Huang. Taco: Temporal latent action-driven contrastive loss for visual reinforcement learning. Advances in Neural Information Processing Systems, 36, 2024.
13

---

A Framework Details
A.1 Notations
Table 3: Glossary of Notations.
Notation
Description
X;
Random variables/Vertex Sets
zyy
Variable values/Vertiics
Probability
H;
Shannon entropy; Mutual information
O,A
Observation space; Action space
O;S;A
Observation, state, action variables/Vertex sets
0;3;0
Single observation, state, action/vertex
2
Single embedding: Embedding variables
P
Transition function
R;
Reward; Reward function
Policy network: Discount factor, Timestep
fig
Encoder: Decoder
Graph
v; V
Single vertex; Vertex set
e; E:w
Edge; Edge set; Edge weight
T
Tree node; Encoding tree
A;
Root node; Leaf node
HT, .HKK HHHH
Structural entropy; Entropy reduction Approximate binary trees
T
18t
Structural mutual information
A.2 Tree Optimization on T
In this subsection, have provided additional explanations and illustrative examples for the encoding tree optimization on T As shown in Figure 4 the stretch operator is executed over sibling nodes os and a, that share the same parent node, A. The detailed steps of this operation are as follows:
= >, a a a', aj a', where a is the added tree node via the stretch operation.
(13)
a aaoajo ajo
stretch
a'
a
aj
Figure 4: Stretch operation on sibling nodes within the encoding tree.
The corresponding variation in structural entropy, AH, due to the stretch operation is calculated as:
(G;
Yo, vol(G)
log vol(a:)
HT HT (G;o)))) vol(G)
Ja,
log vol(ar))
(14)
vol(G))
vol(G)
Jo. log vol(az) HT HTh (G:os) vol(G)
Ja, log vol(a;)
H" (G:o,) vol(G) vol(a')
(15)
vol(a')
11' (G:')) vol log vol(a')
Ja'
(16)
GG)
AH HI + (G) H1TH (G:os) HT (G:a;) HT (G:a')
(H" 0s) - HT (G:a)) + vol(a') + 9o' vol(G)
HT (G;az)) HT (G:
Io: log vol(a') Jaz
log vol(a')
log vol(G)
(17)
vol(G) vol(G)
G))
vol(G)
Go, Yo, Yo' log
vol(a')
vol(G) Go)
14

---

As shown in Algorithm| 1 the HCSE algorithm iteratively and greedily selects the pair of sibling nodes that cause the maximum entropy variation, AH to execute one stretch optimization.
Algorithm The Encoding Tree Optimization on 7
1: Input: one-layer initial encoding tree T
2: Output: the optimal encoding tree 7 E T
3: while True maximize the entropy reduction AH caused by stretch operation
4: (ar,, at))
5: if AH = O then
6: Break
7: end
tree node a' 9: (a') + X, (az) t (az) ta
8:
Create
10: end while
A.3
Intuitive Example of Optimal Encoding Tree
0.2
XD
Vo
0.02
0.03
X1
0.3
Y1
X2
V/2
0.2
X3
0.2
V/3
Yo 32
www. V33
a) Bipartite Graph Gyy
b) Optimal Encoding Tree Tzy
c) Resulting Encoding Tree T
Figure 5: Illustration from a joint distribution to 2-layer approximate binary trees: a) Bipartite distribution graph, b) Optimal encoding tree, c) Resulting encoding tree via I-transformation.
15

---

A.4 The Pseudocode of S12E
Algorithm 2 Effective Exploration based on Structural Information Principles
1: Input: batch size update interval lup
2: Initialize: agent's policy и. encoder functions fa and fs. decoder functions qms 9a ss 9s|2: replay buffer B
3: for each episode do
4: for each environmental step do
5: Collect transition T = (8t, de. 8,+1, r?) using the encoder f. and policy и
6: Sample batch {Te, ji=1 from B including the variables St, A,, and St+1 Adopt encoder functions f& to obtain state-action embeddings Z, # Maximum Structural Entropy Exploration
7:
8:
9:
Construct the state-action graph G according to the policy æ and generate its hierarchical community structure T
10:
Employ the k-NN estimator to estimate the lower bound (V)) - H(V)) and compute intrinsic reward rž
11:
Compute total reward = r. B
Update 7/d (8t, (z 8t41, r')) and augment with T!
13:
if f mod tup then # Structural Mutual Information Principle Compute representation losses Lup- Lz|a- and Løj=
15:
Update encoder and decoder functions to minimize the combined loss Update agent policy æ using B
17:
end if
19:
end for
20:
end for
A.5
Complexity Analysis of S12E
Within the SI2E framework, we analyze the time complexities of critical components independent of the underlying RL algorithm. During the state-action representation phase, the construction of bipartite graphs takes O(n2) time complexity, the generation 2-layer approximate binary trees requires (n log" nt) time complexity, and the calculation of mutual information involves time complexity of ( During the effective exploration phase, the generation of hierarchical community structure incurs O(n logg n) complexity, the construction of the distribution graph leads to complexity of Onn?), and value-conditional structural entropy is calculated with (nz) time complexity.
A.6 Limitations
Our work, which a result thorough research, aims to address the limitations of information theory methods and structural information theory research in reinforcement learning. Therefore, we have selected the state-of-the- information theory exploration method as baseline our evaluation. Despite the current limitations in height due to complexity and cost issues, the encoding tree structure in the SI2E framework holds immense potential. In our future research, we are optimistic about expanding its height further and conducting more research the advantages and restrictions brought by this expansion.
16

---

B Theorem Proofs
B.1 Proof of Proposition 3.1
Proof. For any two vertices V; E V and by E V without any edge connecting them, their correspond- ing tree nodes are denoted as a, and aj. These nodes' parents are initially assigned as the root node Before executing one stretch operation on vertices a; and aj, their structural entropies are calculated as follows:
di (G) vol(G)
di log vol(G)
d, H)) = vol(G)
dy log vol(G)
(18)
where de and d, are the degrees of vertices vs and Vy. Post-stretch operation, their structural entropies are given by:
d,
d log d, log vol(a') H(G;a,) = vol(G) vol(a')
a() = vol(G)
(19)
where a' are their new common parent node. The absence of an edge between v; and by ensures that:
9a' d + dj. vol(a') d; + dz.
(20)
The structural entropy of a' can be determined as:
H(G:o') = Ja' log vol(a') di + dj. vol(G)
log di d vol(G)
(21)
vol(G)
vol(G)
The entropy reduction AH, consequent to the stretch operation vertices vy and uj is calculated as:
dj
log di dj log d, vol(G)
AH
Gol
vol(G)
vol(G)
log di di dj
dj log vol(G) d; + dj
di + dj vol(G)
log di + dj
GG)
vol(G)
d;
di Go)
d, log dj
d2
log dj vol(G)
log d, vol(G)
dj
log
vol
vol(G)
vol(G)
vol(G)
vol(G)
0.
(22)
Given the reduction in entropy, per lines and 6 of the optimization algorithm for T (See Appendix A.2), the stretch operation involving v; and uj is omitted from the optimization process. G
B.2 Proof of Theorem 3.4
Proof. The difference between the mutual information 1st (X;Y and T(X;Y) Y) is expressed as:
1s TST(X; - 1(x;)) Σ p(rs, vy) log p(xx) + p(v))
2
Σ
p(rii Uz) log p(x.) p(U;)
p(u,, Myy)
b
p(xx) ply,)
= Σ p(rs Mz) log
p(x;) + +())))
pl Uj)
2 p p(x:) p(y))
Σ
p(ri, My) log
p(x,,1)) p(xx)) + p(y;)
= Σ 4,
p(a,, vs) log
2
p(ai, Wj)
p(a.) + p(us)
(23)
Given the conditions p(a;, Ui) s p(x,)) I 1 and p( UU) S p((,) S 1, the following inequalities are satisfied:
2 1.
(24)
p(xx)
plu))
p(a 33)
p(at, Us)
+ p(u.
p(x,)
17

---

0 E log pp)))))))) p(z:) S 1, 0 S log 1ss p(8)) - 1.
(25)
By defining E logg(zz 2;) p(z;) and Ej 10gp(u..s)) p(yj), we obtain the following results:
- -1x;))
Σ
p( Mj) log
plac, M1)
c4
1
p(a
((
(26)
$ (1 min((;,))))
Σ
(()))))))) -log
p(zs, Uz)
1.j
= (1 min((,, ()) ().
Therefore,
0 (x:) -
< (1 min(es, H(X,Y),
(27)
min(e,,e))) (Xx) (1-mm((e, H(X,Y)
(28)
B.3
Proof of Theorem 4.1
Proof. For one-to-one correspondence of variables X and Y, the joint probability of tuple (aa, Vj)
as follows:
[p(x.) p(u;) i-
p(.,.)))
$100
(29)
otherwise.
The calculation for (x; Y) is carried out in the following manner:
is (x:Y) = Σ
HSI(X) + HHISSS)))))))) H (X, (x,
1=0
Σ
p(zs:13) Uy) log plxx)) + p(y,))
(30)
1
Σ
p(x.)) -log p(xx))
1
(X).
Similarly, the calculation for T(X; Y) proceeds follows:
p(ui, My)
I(X;Y) E p(ai, Us) log p(xx) p(U;)
(31)
= Σ p(aas) log p(x;)
= HX).
Hence, 1ST (X;Y) equals I(X;Y) when the joint distribution between X and Y shows a one-to-one correspondence.
B.4
Proof of Proposition 4.2
Proof.
Now, employ mathematical induction to demonstrate the existence of the graph G' Base Case (n = 2): Suppose the degree distribution of two vertices is given by (po. P1) with po S P
We construct the graph G'L. as follows:
Create an edge with weight Po between Up and U1.
Add a self-connected edge at vertex U1 with weight P1 Po-
Inductive Step (n k): Assume that, the graph G',, with k vertices exists and satisfies Proposition
Inductive Case (n k + 1): Consider the addition of vertex Up to construct Gen, with l: + 1
18

---

vertices using the following steps:
Start with subgraph that includes the first & vertices, yielding a distribution of (ph:..., PP--1)
with Σ =1
Modify the weight of all edges connected to each vertex 7; (0 < i S k) by a factor (1-pm)p. For each vertex Vi create an edge with weight PiP,, connecting it to the new vertex Ml- Add a self-connected edge at vertex Uk with weight pi:-
These modifications ensure that the degree distribution of the graph remains consistent with the addition of the new vertex, thus completing the inductive step and proving the existence of G for any n.
B.5 Proof of Theorem
In the tree Th. we denote the i-th intermediate node as and its j-th child node as asj. The single state-action vertex in the corresponding subset of az assumed (sij asz). the graph G.... the degree of any state-action vertex (Sij, aiz) is equated to its visitation probability, thereby:
vol(G'aa) Σ p(sis. a;z)
vol(asg)) ga.y p(8ij, aiz).
(32)
1.
The 2-dimensional value-conditional structural entropy H (Geo)) ) is calculated through the follow- ing expressions:
9o. log vol(as) + Σ Mais log vol(a )
H (Taaaaa
Σ
vol(os)
Σ
Ia. log vol(as) +
Σ
((si);ar)) log p(sij,a;) vol(a,)
Σ 1.
p(sij, aiz) (1s)
log ((s)).ass)
1
vol(as) log
+ Σ
ga. loog vol(as)
1
p(sij, acs))
vol(a;)
H(V) H(V)) + Σ Ja. log
vol(a;)
2 H(V) H(V)).
(33)
Given that p(sij, any vol(as) S p(s.y aiz) S vol(au), this inequalities hold that:
p(sij, aij) vol(a;, < 1.
0 < log (0pp(s)...)))
(34)
By defining Gij- = (o)p(s))mu))
play p(a))ag)) we obtain that: vol(a.,)
vol(as) log
Σ p(sij,a)) vol(as)
vol(as)
=
1 [p(sn), asy))'-an
Σ p(sij ais) log
(35)
Σ I[-- [a- Giz) p(sij, aiz) log p(sij, ang)
Selecting the minimal Ç-value as C* allow us to reformulate Equation 33 as follows:
H(Vi) Σ (vol(az)) log 1
< (1-55)) H(S, Ad).
(36)
vol(a;))
H(V)) = H(S,,AA))
(37)
5" H(S,, Ar) < H(V) H(V)) < Ti (G' < (S,
(38)
19

---

C Detailed Derivations
C.1 Derivation of (X;();
For each intermediate node o; E my with vertex subset (xi, ViJ, the entropy sum of this node and its children is calculated as follows:
9a.
log vol(a;)
p(x;)
log p(a;)
p(y))
log p(y:)
Gol(
vol() (oa)) vol(a;)
vol(Gzy)
vol(o;)
(39)
Ja.
vol(a.) p(x+))
log p(2+) p(y:)
vol(as) 2 log p(y:)
log 2
2
2
vol(as)
The (X) (HSSS()) H (X,
term in Equation is calculated as follows:
p(rr))
llo p(a;)) p(y:)
Jo. log vol(a;) p(m;))
log p(o;) vol(a;)
p(us)
llog p(ya)
Σ
log
Σ
2
2
2
vol(as))
(40)
Proposition 3.1 ensures that:
vol(a:) p(a:)) p(V)). Io: = p(x:) + p(vi) 2p(xs; 1/1).
(41)
Consequently, we can reformulate Equation 40 as follows:
p(ane)
p(u:)
p(a:) + p(v)) 2. p(xi, Mi)
2 log
log p(a;) + p(y))
-log
p(xx)) + p(V))
p(x,) + p(v))
Σ
p(as, yi) log p(r;)) + p(y:)
(42)
For any integer > 0, the 81 (X) (Y) H (X, Y) term in Equation 5 is given by:
Σ p(zy, Mi) log p(xv)) + p(v))
i= (i + 1) mod n.
(43)
Consequently,
n 1s (s)())))
2 1/00 - E plai vz) log p(xs) + p(u;)
(44)
C.2 Upper Bound of 11 7s1(Z;; St)
Theorem 3.4 assures the following inequality:
1t (X;Y) S I(X;Y) + (1- ,(X,Y), 0 0
(45)
Given the relationship between joint entropy and conditional entropy in traditional information theory, this inequality can be reformulated follows:
ST (X;)) I(X;Y)+++ + (1 (1-e). H(X,Y)
= = + (1-e) H(X]Y) + (1 HYY
(46)
T(X;Y) + H(XY)) H(Y).
C.3
Upper Bound of I(Z,;
Through the non-negativity of KL-divergence, the following upper bound of 7(2;; S.) holds that:
Σ plze, st) log p(2c(se)
I [[Z;; St)
p(z()
Σ p(ze, St) log p(=e(se) am (2))
Del(pllam)
(47)
$ Σ [e(2e, st) (xi(p(zolse) (2))))
20

---

C.4 Upper Bound of H (Z.
Through the non-negativity of KL-divergence, the following upper bound of (Z,))S) holds that:
H(z()S))
Σ s() log p(z)
1
Σ p(2(.st) (t) log (=10(2e15()
(xl(a)
(48)
- Σ p((),)s) 86) logg g=)o(2015e)
C,5 Lower Bound of [Zz; S(+1)
Leveraging the non-negative Shannon entropy and KL-divergence, we obtain the lower bound of [Ze St+1):
S(+1) = Σ p(ze; S4+1) log p(3(+1|2()
p(s(+1)
Σ (D(2e,8441) log (s + ((++11) DKL(pllas)s)
(49)
Σ [p(ze, 8141) log (5(41211))))]]
21

---

D Experimental Details
In the experiments conducted for this work, we utilize a single NVIDIA RTX A1000 GPU and eight Intel Core i9 CPU cores clocked at 3.00GHz for each training run. The total number of environmental steps was set to 3000 /1000K for the MiniGrid benchmark, /100K for the MetaWorld benchmark, and 250K for the DeepMind Control Suite (DMControl).
D.1 Implementation Details
A2C implementation details. our implementation of the A2C algorithm. we utilize the official RE3 implementationf" adhering to the pre-established hyperparameters set, except where explicitly noted. State representations in baselines are derived using a fixed encoder that is randomly initialized, and intrinsic rewards normalized based on the standard deviation computed from sample data, consistent with the original methodology. However, this normalization process is omitted in the intrinsic reward calculations for VCSE and SI2E implementations. Across all exploration methods, we maintain fixed scale parameters 3 = 0.005 and k = 5, in line with the original framework. The comprehensive hyperparameters for the A2C algorithm are detailed in Table
Table 4: Hyperparameters for the A2C algorithm on the MiniGrid benchmark.
Hyperparameter
Value 100
number of updates between two savings
number of processes
16
number of frames in training
1e6/1e6
scale parameter batch size
0.005
256
number of frames per process before update
5
discount factor
0.99
learning rate GAE coefficient
0.001
0.95
maximum of gradient
0.5
DrQv2 implementation details. For the DrQv2 algorithm, we employ its official implementatior Yarats et al. 2021], maintaining the original hyperparameter settings unless specified otherwise. fixed noise level of 0.2 and = 12 are used for all exploration methods, including SE, VCSE, MADE, and SI2E. In the calculation of intrinsic rewards in baselines, train the Intrinsic Curiosity Module [Pathak et al. (017)] using representations from the visual encoder to measure vertex distance in the estimation of value-conditional structural entropy. Specific hyperparameters in the DrQv2 summarized in Table 5
Table 5: Hyperparameters for the DrQv2 algorithm on the Deep-Mnnd Control Suite.
Hyperparameter
Value
number of frames stacked
number of times each action is repeated
2
number of frames for an evaluation number of episodes for each evaluation number of worker threads for the replay buffer
10000
10
replay buffer size batch size discount factor learning rate feature dimensionality
1e6
64
0.99
0.0001
50
hidden dimensionality
1024
scale parameter 3
0.1
http:://ggthab..cm//oogggggeegs httge///gghhbbooommrrcooooeererr
22

---

D.2 Environment Details
MiniGrid Experiments. In our MiniGrid benchmark experiments, we encompass six navigation tasks. including RedBlueDoors, SimpleCorssingSNN. KeyCorridor, DoorKey-6xe 6x6, DoorKey-8xe and Unlock, with visual representations provided Figure Notably, all tasks are employed in their original forms without any modifications.
Figure Examples navigation tasks used in our MiniGrid experiments include: (a) RedBlueDoors,
(b) SimpleCorssingS9NT,, (c) KeyCorridor, (d) DoorKey-6x6, (e) DoorKey-8xk. (f) Unlock.
Meta World Experiments. In our evaluation using the Meta World benchmark, we conduct experi- ments on six manipulation tasks: Door Open, Drawer Open, Faucet Open, Window Open, Button Press, and Faucet Close. These tasks are visualized in Figure 7
Figure Examples of manipulation tasks used in our MetaWorld experiments include: (a) Door Open, (b) Drawer Open, (c) Faucet Open, (d) Window Open, (e) Button Press, (f) Faucet Close.
DMControl Experiments. Our research in DMControl suite focues on six continuous control tasks, specifically Hopper Stand, Cheetah Run, Quadruped Walk, Pendulum Swingup, Cartpole Balance Sparse, and Cartpole Swingup Sparse. And visualizations of thes tasks are provided in Figure g
Figure 8: Examples control tasks used in our DeepMind Control Suite experiments include: (a) Hopper Stand, (b) Cheetah Run, (c) Quadruped Walk, (d) Pendulum Swingup, (e) Cartpole Balance Sparse, (f) Cartpole Swingup Sparse.
23

---

E Additional Experiments
E.1 Experiments on MiniGrid Benchmark
Figure 9 iillustrates the learning curves for the A2C algorithm integrated with our SI2E framework, well with other exploration baselines, SE and VCSE. The corresponding variants are labeled as A2C, A2C+SE, A2C+VCSE, and A2C+SI2E. These results demonstrate that SI2E consistently outperforms other baselines across various navigation tasks. terms of final performance, A2C+SI2E achieves an average success rate of 94.40% across all navigation tasks, significantly outperforming the second-best A2C+VCSE, which has an average success rate of 89.78% Regarding sample efficiency, SI2E converges in fewer than 50% of the total environmental steps in almost all tasks, except for DoorKey-8x8. This indicates SI2E's effectiveness in enhancing the agent's exploration of the state-action space, surpassing the baseline methods.
KeyCenilaS3RI
1.3
0.5
0.6
0.6
0.5
64
0.2
64
0.3
50H16" 100001 1.5-1 20010 25-10f 3/001"
00
20-10" 40007
60-10
00
50H00" LaxI0 20001" 5 toi
Donrkey-ton
DontKeystek
Uriokk
1.0
1.0
Suaccs Rate
0.6
6.5
0.2
50x
Envirommnnal Ster
Envirommnaal Stop
Eastromncntal Step
Figure 9: Learning curves for six navigation tasks in MiniGrid, measured in terms of success rate. The solid lines represent the interquartile mean, while the shaded regions indicate the standard deviation, both calculated across 10 runs.
To further substantiate our results the Minigrid enviromment, we have introduced Leco Jo et al. 2022] and DEIR Wan et al., 2023], two additional state-of-the-art baselines representing advanced mechanisms for episodic intrinsic rewards. These results in Table|ō)demone consistently maintains a performance advantage in terms of effectiveness and efficiency, even when compared to advanced episodic intrinsic reward mechanisms.
that our method
Table 6: Comparative results between SI2E and advanced episodic intrinsic reward mechanisms in MiniGrid benchmark: "average value + standard deviation" and "average improvement"
MiniCind
Red Doors-6xh
SimpleC
KeyC KeyCoridorS33
Navigation
Rate (%)
Required Step (K)
Rate (%)
Required Step (K)
Required Step (X)
Lecn
81.97 + 10.81
817.47 + 137.21
10.02 + 4.13
417.50 + 17403
90.30 + 0.57
520443 + 10.31
DEIR
78.32 7.21
722.37 722.3778100 S1.03
91.47 = 8.29
523.79 31.27
91.81 2.13
735.87 9.24
SI2E
85.80 = 1.18
461.90 61.53
93.64 1.63
139.17 +: 27.03
91.20 0.12
129.06 6.11
Miniond
DoucKey 6x6
DoorKey-Ka..
Uniock
Navigation
Success Rate (%6
Requireed
(K)
Success Rate
Requiree Step (K)
Rare
Requiired Step (K)
Loco
94.37 3.41
671.31 11.31:3. 31.27
92.07 + 19
21688.36 + 203..62
94.48 = 6.39
791.40 + 82.39
DEIR
91.1
110.25
13.27
12117.5 231.
12.71
531.00
SIZE
97.04 2. 1.52
230.60 19.85
98.58 1 3.11
10091.966 1. 125.77
97.13 1: 3.35
31M.14 53.71
24

---

E.2 Experiments on Meta World Benchmark
Figure 10 summarizes the learning curves for the DrQv2 algorithm with different exploration methods, including SI2E (ours), SE, and VCSE. These variants are denoted as DrQv2, DrQv2+SE, DrQv2+VCSE, and DrQv2+S12E. respectively. As shown in Figure I0 SI2E consistently and significantly achieves higher success rates with fewer environmental steps across all manipulation tasks. average, SI2E improves the final performance by 10.21 % and sample efficiency by 45. 45.06%.
Buroer Puois
D:Qx2
DNQY2+512E
1.0
0.8
6.3
Stacos Bat
0.5
0.5
0.4
044
64
02
6.2
-0.2
0.8
6.0
Franet Closs
Phanet Open
Cppn
0.8
0.6
3.
Saaccaa
0.1
04
02
0.2
0.0
62
20-10f 40<00* 6.610 Einto"
20-36" 41w10d
10+00
5'--2""
1.
1,5x00
2 2.0000
Ensircemental
Figure 10: Learning curves six manipulation tasks in MetaWorld, measured in terms success rate. The solid lines represent the interquartile mean, while the shaded regions indicate the standard deviation, both calculated across 10 runs.
To provide additional validation, conducted further experiments in the MetaWorld environment using the advanced TACO (Zheng et al. 2024) as the underlying agent. The new experimental results, as documented Table 7 demonstrate the robustness and superior performance of our method with different underlying agents.
Table 7: Summary of success rates and required steps for the TACO agent in MetaWorld tasks: "average value + standard deviation" " and "average improvement". Bold: the best performance, underline: the second performance.
MetaWorid Manipolation
Open
Open
Suceess Rate (%)
Required Step (K)
Success Rate (X)
Requised (K))
Success Rate (%)
Required Step (K)
TACO
73.56 21.43
33.47 2.15
TACO+VCSE
91.43 1 5.51
95.0 5.0
78.59 4.22
20.93 6.65
TACO+SIZE
95.63 + 0.62
75.0 5.0
96.72 4.98
115.0 1 10.0
94.92 2,06
75,0 5.0
Abs.%%) Avg.
4.2(4.50)
20.022105)
18.13
231.01
MetaWorid
Fancet Close
Faucet Open
Window Open
Manipulation
Suceess Rate (%)
Roquired Step (K))
Success Rase (X)
Requied Stop (N)
Success Rate (%)
Required Step (K)
TACO
58. +.23
49.48 + 11.60
76.96 + 5.79
76.00
3.17
120.0
TACO-SIZE
93.78 1: 1,21
40.0 5.0
92.09 :: 2.26
51.25 1: 1.25
97.03 1: 1.58
70.0 2.5
Abx.%% Avg.
17.18(21.9))
(1.69)14.54)
4.72(5.11)
5000(41.67]
25

---

E.3 Experiments on DMControl Suite
For each task, we benchmark the convergence reward the best- best-performing baseline as the target and track the environmental steps required by both SI2E and this baseline to reach the target. As illustrated in Figure [I] SISA demonstrates an average improvement of 35. 60% in sample efficiency. This improvement is reflected in reduction in the required environmental steps, decreasing from 31.83% 20.5% of the total steps required achieve the reward target.
DMControl Control Tasks
50
S12e
Baseline
41
Envineement Steps (14)
40
14
30
2.5
20
155
Hopper
Penduluun Swingup
Caripole
Cartpolo
Walk
Swingup
Figure 11: Comparison sample efficiency between S12E and the best-performing baseline in DMControl. focusing the required environmental steps to reach the reward target, expressed proportion of the total 250K steps.
Figure 12 shows the learning curves for the DrQv2 algorithm when integrated with our SI2E framework and other exploration baselines, SE, VCSE, and MADE. The variants are identified as DrQv2, DrQv2+SE, DrQV2+VCSE, DrQv2+MADE, and DrQv2+S12E. These results reveal that SI2E exploration significantly improves the sample efficiency of DrQv2 in both sparse reward and dense reward tasks, outperforming all other baselines. Particular sparse reward tasks (Cartpole Balance and Cartpole Swingup), our framework successfully accelerates training and achieves higher episode rewards. This suggests that SI2E avoids exploring states that may not contribute to task resolution, thereby enhancing performance with a 5. 5.17% improvement in final performance and 15.28% increase sample efficiency.
Happer Stanl
DOQ
DVQ SE
D-GG-VVSE
DIQK2-MATE
Epinedo Roxud
600
300
400
200
200
100
Swispap
Compole Spaco
Carppeo Swingr Spamo
100
Ejiood Roood
600
-00
400
5.010" b0-1p 1.511P 200ap? 0b
5,0110" 1bbig? 15511
1.511 34sig?
25-32
San1of LE-IpP
15-10f 2001F 25-10
Esviommenee
Envirtannttal
Esvivamenntd
Figure 12: Learning curves for six continuous control tasks from DMControl Suite, measured in terms of episode reward. The solid lines represent the interquartile mean, while the shaded regions indicate the standard deviation, both calculated across runs.
26

---

E,4 Visualization Experiment.
To understand the learned representation through our structural mutual information principle (Section 4.1), we use t-SNE to project the original observation O and state-action embedding Z into 2- dimensional vectors. Figure [3 visualizes these 2-dimensional vectors and measures the Euclidean distance between temporally consecutive vectors. Our presented principle aligns all movements on the same curve and reduces their distance by an average of 36.41, demonstrating its effectiveness for dynamics-relevant state-action embedding.
To analyze the benefits of our intrinsic reward mechanism 4.2)) we keep the map configuration constant in the SimpleCrossing task and display the exploration paths of various methods in Figure 13b Our SI2E, in comparison the SE and VCSE baselines, prevents biased exploration towards lawuvalue areas and effectively explores high-value crucial areas, like the crossing point, with fewer environmental steps, ensuring its performance superiority.
2-dimensional Deservations
2-dimensional Regresenattinss
ASCAVCSE
A2K--82216
100
200
320
2.00
500
Envirommrrcal Stop
SimpleCrosing
25K Stops
Steps
75K Stops
10OK Steps
(a) Representation visualization
(b) Exploration visualization
Figure 13: Visualization results SI2E under DMControl and Minigrid tasks. (a) Visualization of representation learning based structural mutual information principle. (b) Visualization of agent exploration through maximizing the candiiconditional structural entropy.
Moreover, we have provided the visualizations of state coverage our SI2E framework and other baselines (SE and VCSE) in the continuous Cartpole Balance task in Figure 14] Compared with SE and VCSE baselines, our SI2E framework achieves a more efficient exploration strategy by minimizing occurrences in extreme positions and angles, resulting in higher density in key areas.
Carpple
DiQV2+SE
DIQU2-VESE
DiQv2481ZE
Salz Dhovitt
Sair
Pobs Car Fobae Aade
Pale Angl
Figure 14: Visualization of agent exploration in the CartPole Balance task. Heat maps illustrate the final state densities for cart position and pole angle of the learned policies: (b)DrQv2+SE, (c) DrQv2+VCSE, and (d) DIQE.+S12E.
27

---

E,5
Ablation Studies
To investigate the influence of parameters 3 and n on our framework performance, we incrementally adjust these parameters across two distinct tasks: DMControl tasks Hopper Stand and Pendulum Swingup. We meticulously document the resulting learning curves to assess the outcomes. Figure 15a illustrates that an increase in parameter 3 consistently enhances performance across both tasks, substantiating the effectiveness of our exploration method. Conversely, Figure [5b demonstrates that variations in batch size yield comparable performance outcomes, particularly notable in Pendulum Swingup task, thereby confirming the SI2E's stability amidst variations in batch size.
Pandulum
300
200
3-52
3001
6000
grint
10:55
Tpsocd Boonet
Spundk looee
600
200
200
Devvoomeentall Saep
Divernmectaal Nep
Devosemennal Step
(a) Effect of scale parameter
(b) Effect of batch size n
Figure 15: Learning curves of SI2E with varied 3 and values Hopper Stand and Pendulum
Swingup tasks. (a) shows the effect of the scale parameter 3 on episode reward. (b) shows the effect of the batch size n on episode reward. The solid line represents the interquartile mean across 10 runs.
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have clearly outlined the contributions and scope of our paper in the abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have outlined the limitations of our paper in the conclusion and the details are provided in our appendix.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiatiinn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
29

---

Answer: [Yes]
Justification: For each theoretical result, we have included the complete set of assumptions and correct proof in appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The source codes are accessible via an anonymous link in the introduction, and specific experimental setups provided in the appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, other means that appropriate to the research performed.
also be provided via detailed
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
30

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: The main experimental results be replicated using the source codes accessible via an anonymous link provided in the introduction.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis.cc.
Moblic//guides/Coeeeubbiss itw.oeeeSuumiissiooooooo.o for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ wttps/cccppplccguua.eeaeaeccuuea
wtteeee//ooSSSesssss.ee.. www.ssssiicggooooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We have provided detailed experimental settings (hyperparameter and opti- mizer) in our evaluation and appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: In our evaluation section, we have conducted multiple trials with different random seeds, and the charts reflect the average performance and standard deviation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
31

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have provided sufficient information on the computer resources in our appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://eeerrrp..cccccbbbl/ttttea
Answer: [Yes]
Justification:
Our paper strictly maintains anonymity.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work is focused fundamental research in reinforcement learning and is not specifically tied to any particular applications. Furthermore, there is no direct path to negative applications.
Guidelines:
32

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymentt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We appropriately cited the original papers for our experimental datasets, including MiniGrid, MetaWorld, and the DeepMind Control Suite.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
33

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.coo//aaaaa datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Our paper does not involve crowdsoureing nor research with human subjects
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
34

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
35


Reviews:
[{"review_id": "Lbex9ajmhS", "reviewer": "Reviewer_i1kZ", "summary": "This paper proposes SI2E framework based on structural information principles to overcome inherent limitations in traditional information theory as applied to Reinforcement Learning (RL). The SI2E framework innovatively quantifies the dynamic uncertainties inherent in state-action transitions through a metric termed as 'structural entropy'. The authors define a novel concept, 'structural mutual information', to derive state-action representations that are particularly relevant to the dynamics of the environment. Additionally, they introduce a value-based approach to structural entropy, which is designed to enhance the agent's exploratory capabilities within the RL landscape. The paper establishes robust theoretical connections with established information-theoretic methodologies, thereby substantiating the rationality of the SI2E framework. Empirical validations through comparative experiments in the MiniGrid and DeepMind Control Suite environments underscore the framework's superiority over existing exploration benchmarks, showcasing its practical efficacy.", "questions": "Please see the above weaknesses.", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. Innovative Contribution: The paper presents a novel framework, SI2E, which innovatively applies structural information principles to enhance reinforcement learning. This approach addresses key challenges in traditional information theory within the RL domain, offering a fresh perspective for exploration.\n2. Clarity and Organization: The manuscript is exceptionally well-organized and written with exceptional clarity, making complex concepts easily comprehensible to readers.\n3. Theoretical Rigor: The authors provide a solid theoretical foundation for their method, supported by comprehensive proofs that validate the framework's rationality and effectiveness.\n4. Empirical Validation: The paper includes detailed experimental verifications across a variety of scenarios, which not only demonstrate the effectiveness of the SI2E framework but also highlight its robustness and superiority over current exploration methods.\n5. Comprehensive Appendices: The paper's appendix is thorough, offering additional theoretical proofs, detailed model descriptions, and supplementary experimental data, which further substantiate the paper's claims.\n6. Overall Impact: The paper demonstrates significant strength in both theoretical development and empirical validation, contributing valuable insights to the field of reinforcement learning and warranting acceptance for publication.", "weaknesses": "1. Although the paper includes a time complexity analysis, there is a gap in understanding the actual wall time required for training. Providing insights into the practical training duration would offer a more tangible assessment of the method's efficiency.\n2. The current related work section provides a succinct overview. To strengthen the paper's context and background, a more detailed discussion of classical information-theoretic methodologies and structural information principles in the appendix would be beneficial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We systematically address each of your queries, labeling weaknesses as 'W' and questions as 'Q'. \nPlease note that, unless otherwise specified, any table or figure refers to the supplementary results in the Author Rebuttal PDF.\n\n$\\bullet$ W1: Practical Training Time.\nWe have comprehensively analyzed the training time for our method, SI2E, and two baselines, SE and VCSE. \nSpecifically, we measure each method's time expenditure for a single training step as: \n    SI2E with $8.41 \\pm 0.15$ ms,\n    SE with $8.60 \\pm 0.23$ ms,\n    VCSE with $8.15 \\pm 0.17$ ms.\nOur findings indicate that our method maintains comparable training time expenditure to the other methods, demonstrating its practicality.\nBy providing these practical measurements, we underscore that SI2E is robust in theoretical time complexity and real-world training scenarios, ensuring efficiency and feasibility in practical applications.\n\n$\\bullet$ W2: Related Work.\nWe have reorganized the related work section in the appendix into three subsections: Maximum Entropy Exploration, Representation Learning, and Structural Information Principles.\n\nIn this work, we leverage structural information principles to derive the hierarchical state-action structure and define value-conditional structural entropy as an intrinsic reward, leading to more effective agent exploration.\nCompared to current maximum entropy explorations, SI2E introduces and minimizes sub-community entropy to motivate the agent to explore specific sub-communities with high policy values. \nThis approach avoids redundant explorations in low-value sub-communities and enhances maximum coverage exploration. \nUnlike the VCSE baseline, our method enables balanced exploration without needing prior knowledge of downstream tasks, effectively addressing previous approaches' limitations.\n\nAdditionally, our work introduces structural mutual information to measure the structural similarity between two variables for the first time.\nWe present an innovative embedding principle that incorporates the representation variable's entropy and mutual information with state variables, more effectively eliminating irrelevant information than the traditional Information Bottleneck principle.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JPdWTtfyem", "reviewer": "Reviewer_6Ten", "summary": "In the current field of reinforcement learning, when using representation learning and entropy maximization for exploration, analyses often focus on single variables, making it difficult to capture potential relationships between two variables. Therefore, this paper proposes the SI2E framework. This framework defines the structural mutual information between two variables, based on which state-action representations are obtained. These representations effectively capture the intrinsic relationships between states and actions. Subsequently, an encoding tree is constructed using these representations, and the value- conditional structural entropy is defined. By maximizing this value, the coverage of the state-action space is expanded, enabling the agent to better perform exploration tasks. Extensive experiments on SI2E have been conducted, demonstrating the framework's effectiveness.", "questions": "1.Why was the A2C agent chosen for experiments on MiniGrid instead of DrQv2 or other more recent models?\n2.Why was MADE not included in the comparison for experiments on MiniGrid and MetaWorld?", "limitations": "The authors have further discussed the encoding tree involved in the SI2E framework", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The abstract part of the paper clearly expresses the paper's innovative aspects and the problems it aims to address.\n2. The paper is well-organized and clearly presented. The model introduction is progressive, and the structure is reasonable.\n3. Experiments conducted on multiple datasets have demonstrated the effectiveness of the model.", "weaknesses": "1. The baselines are not strong enough, and more state-of-the-art models should be used for comparison.\n2. The experimental results in Appendix E.5 are more suitable for inclusion in the Parameter Analysis section rather than Ablation Studies.\n3. The comparison of SI2E, SI2E-DB, and SI2E-VCSE is only conducted in Cartpole Balance Sparse and Cartpole Swingup Sparse, making it difficult to demonstrate the importance of the two key components of SI2E in other scenarios.\n4. The Related Work section does not clarify the relationship between SI2E and related works, particularly how SI2E improves upon or innovates based on previous research.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We systematically address each of your queries, labeling weaknesses as 'W' and questions as 'Q'. \nPlease note that, unless otherwise specified, any table or figure refers to the supplementary results in the Author Rebuttal PDF.\n\n$\\bullet$ W1: Compared Baselines.\nTo address this concern, we have incorporated the DRM model (ICLR 2024) as an additional baseline. \nConsistent with the experiments presented in the original DRM paper, we conducted extensive evaluations in both the MetaWorld and DMControl environments. \nAs shown in Table 1, the results demonstrate that SI2E consistently outperforms this stronger baseline. \nThese findings reinforce our method's superior final performance and sample efficiency compared to state-of-the-art exploration methods.\n\n$\\bullet$ W2: Parameter Analysis.\nWe have reclassified the experimental results previously located in Appendix E.5 and moved them to the Parameter Analysis section to better align with the focus of the analysis.\n\n$\\bullet$ W3: Ablation Studies.\nTo further demonstrate the importance of SI2E's two key components—the embedding principle and the intrinsic reward mechanism—we conducted additional ablation experiments in the MetaWorld environment, specifically focusing on the Door Open and Faucet Open tasks. \nThe results, illustrated in Figure 1, clearly show the significant performance advantages of SI2E over its variants, SI2E-DB (without the embedding principle) and SI2E-VCSE (without the intrinsic reward mechanism), in these scenarios.\n\n$\\bullet$ W4: Related Work.\nWe have reorganized the related work section in the appendix into three subsections: Maximum Entropy Exploration, Representation Learning, and Structural Information Principles.\n\nIn this work, we leverage structural information principles to derive the hierarchical state-action structure and define value-conditional structural entropy as an intrinsic reward, leading to more effective agent exploration.\nCompared to current maximum entropy explorations, SI2E introduces and minimizes sub-community entropy to motivate the agent to explore specific sub-communities with high policy values. \nThis approach avoids redundant explorations in low-value sub-communities and enhances maximum coverage exploration. \nUnlike the VCSE baseline, our method enables balanced exploration without needing prior knowledge of downstream tasks, effectively addressing previous approaches' limitations.\n\nAdditionally, our work introduces structural mutual information to measure the structural similarity between two variables for the first time.\nWe present an innovative embedding principle that incorporates the representation variable's entropy and mutual information with state variables, more effectively eliminating irrelevant information than the traditional Information Bottleneck principle.\n\n$\\bullet$ Q1: Underlying Agent.\nTo ensure fairness in performance comparison, we maintained the experimental setup used in VCSE (NeurIPS 2023) for the MiniGrid environment, utilizing the A2C agent. \nThis approach allows for a direct and equitable comparison of results.\nTo address your concerns and provide additional validation, we conducted further experiments in the MetaWorld and DMControl environments using the advanced TACO (NeurIPS 2023) and DrQv2 agents. \nThe new experimental results, documented in Tables 1 and 2, demonstrate our method's robustness and superior performance across different environments and with state-of-the-art agents.\n\n$\\bullet$ Q2: MADE Baseline.\nIn the presented paper (NeurIPS 2021), MADE was initially validated in the MiniGrid and DMControl environments. \nHowever, MADE did not perform satisfactorily in our experiments in the MiniGrid environment. \nConsequently, we initially included the MADE baseline exclusively in the DMControl experiments.\nTo provide a more comprehensive comparison and address your concerns, we have now included the MADE results in the MiniGrid environment in Table 1.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Tzpun1hCgM", "reviewer": "Reviewer_sR8b", "summary": "This paper proposes a new exploration scheme for RL agents by using structural mutual information for dynamics-aware state-action representation and an intrinsic reward to enhance state-action coverage by maximizing value-conditional structural entropy", "questions": "### Structural entropy and graph\n- what is the intuition or rationale behind 1) using structural information for encouraging agent exploration and 2) why/how SI boosts efficient exploration in RL?\n- can a vertex contain joint variables or only a single variable? What is a single-variable graph?\n- why is structural information limited to a single variable? Can't the underlying graph be expanded to cover multiple variables (lines 128-147)?\n\n### Method's design and choice\n\n- why some tree nodes in step II.c (Figure 2) have more than two children? isn't the encoding tree assumed to be binary?\n- how do the max and min of structural MI capture dynamics-relevant information (lines 58-60 and 176-178), and why is this beneficial for agent exploration?\n- why do we need $l$-transformation for defining structured MI (lines 155-157)?\n- what is $V_1$ exactly, and how are sub-communities obtained? why does $-H(V_1)$ mitigate uniform coverage?\n### Step II in Figure 2 (sec. 4.2)\n\n- how many state-action pairs are used to form the $G_{sa}$ graph for different tasks in the experiment? how many pairs are sufficient for building a *good* $G_{sa}$? how is a bipartite graph constructed for continuous state and action spaces? can you provide a simple example of such a construction?\n\n- why $\\pi$ is used for a value function when it represents a policy?\n\n- why is step d necessary after $T^\\star_{sa}$ is obtained, can't $G_{sa}$ perform the required?\n\n## Figure 1\n\n- what do dotted blue lines of varying intensity represent? why transitions between s2 and s5 are redundant and how *a policy maximizing structural entropy would selectively focus on crucial transitions*\n- which dotted line corresponds to $a_0$? note that the outgoing arrow of state $s_0$ is solid\n- in step I. state-action representation, which (top) boxes correspond to $s_t$, $s_{t+1}$, and $z_t$ respectively?\n\n### Experiments\n\n- is it possible to visualize state coverage in other tasks like meta-world, which has continuous states?\n- why are required steps or success rates not reported for some tasks in Table 1, such as RedBlueDoors and Faucet tasks?\n\n### Other questions\n\n- where is equation 1 used?\n- lines 38-41: What is meant by 'their' in *due to their instability*? What do these lines aim to emphasize?\n- what is the entropy reduction mentioned in supplement A.2?\n\n\nI am willing to increase my score if the clarity questions are addressed.", "limitations": "The authors acknowledge the limitations of the work. It might be useful to discuss how the height of the encoding tree would affect the exploration.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "- constructing intrinsic reward using graph-based information for RL agent exploration is somewhat novel.\n- extensive comparison with various baselines across a set of tasks demonstrates superior task performance and sample efficiency.", "weaknesses": "### Unclear presentation\n\n- lines 31-38: the statements don't clarify that entropy maximization strategies use state entropy as an intrinsic reward to encourage exploration, leading to confusion about the connection between computing intrinsic rewards and entropy maximization strategies (lines 37-38). Additionally, there's no explanation for why intrinsic rewards based on state values can mitigate the mentioned issue.\n- line 144: the stretch operator and the HCSE algorithm are not clearly explained, making it hard to understand their functions. Simply adding a reference is not sufficient.\n\n- some claims, such as those in lines 35-36 and 200-201, lack evidence or references\n\n### Figures\n\n- Figure 1: It lacks details, for example, how structural information selectively removes redundant transitions in the example. It does not effectively illustrate the benefit of using structural information\n- Figure 2: the presentation is cluttered\n   - the layout is extremely tight with a disordered flow of annotations (vertical and horizontal), and the caption lacks clarification and is not self-contained.\n   - the colour scheme (of nodes and vertices) in the two steps is unspecified\n   - the space between Figure 2 and line 158 is too narrow\n\n### Unclear and non-detailed method presentation\n\n- the use of $T$ to represent both the tree and subsets of graph vertices (lines 117-120) is confusing\n- no discussion about why 2-layer binary trees are used (lines 139-140), which is necessary to understand the approach's limitations\n- only a minimal description of how an optimal encoding tree is generated from $G_{sa}$ (lines 230-231) in sec. 4.2\n\n### Related work\nthe related work section is short and unstructured. It lists related works without clearly stating how this work differs from others, its unique aspects, and the issues it addresses. It also does not show how learning dynamics-relevant representations for state-action pairs differs from other recent representation learning approaches\n\n### Minor points\n\n- line 34, Renyi entropy needs a citation\n- eq 2 misses explanation of $\\alpha^-$\n- line 139, structur -> structure\n- lines 193-194, should use double dashes\n- SI2E in CartPole Swingup Sparse doesn't show superiority in sample efficiency (Figure 3)\n- as to line 321, better to briefly summarize the ablation findings on finetuning $\\beta$ and $n$ before referring to the appendix\n- the best-performing baseline is not specified in sec. 5.3 and appendix E.3", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We systematically address each of your queries, labeling weaknesses as 'W' and questions as 'Q'. \nPlease note that, unless otherwise specified, any table or figure refers to the supplementary results in the Author Rebuttal PDF.\n\n$\\bullet$ W1.1: The entropy maximization strategies maximize the state or action entropy as intrinsic rewards, ensuring comprehensive coverage across the state-action space.\nA prevalent issue is their tendency to bias exploration toward low-value states, resulting in inefficient exploration and vulnerability to imbalanced state-value distributions. \nValue-conditional state entropy computes intrinsic rewards based on the estimated values of visited states, ensuring exploration is directed toward diverse and valuable states.\n\n$\\bullet$ W1.2: Please refer to the Author Rebuttal.\n\n$\\bullet$ W1.3: We have incorporated citations to provide theoretical support for these made claims.\n\n$\\bullet$ W2.1, Q1.1, and Q4: Please refer to the Author Rebuttal.\n\n$\\bullet$ W2.2: We have made several adjustments to enhance its clarity and readability.\n\n$\\bullet$ W3.1: We have changed the symbol representing the vertex subset to $\\mathcal{V}$.\n\n$\\bullet$ W3.2 and Q2.3: Please refer to the Author Rebuttal.\n\n$\\bullet$ W3.3: Please refer to the Author Rebuttal.\n\n$\\bullet$ W4: Please refer to the Author Rebuttal.\n\n$\\bullet$ W5: We have addressed each minor point.\n\n$\\bullet$ Q1.2: The bipartite graph contains two sets of vertices representing the state variable, $S_t$ or $S_{t+1}$, and the state-action representation variable $Z_t$, respectively. \nEach vertex corresponds to a possible value of these variables. \nThe weighted edges between these vertices represent the joint distribution between two variables and are used to define structural mutual information.\n\nThe complete state-action graph and distribution graph contain only a single variable $Z_t$, which represents the Q-value relationships and access probabilities between state-action pairs in $Z_t$ under the agent policy. \n\n$\\bullet$ Q1.3: While the underlying graph can encompass multiple variables, current structural information principles are limited to measuring only the joint structural entropy among these variables and cannot effectively quantify the structural similarity between variables, inherently imposing a single-variable constraint.\nPrior research on reinforcement learning based on structural information principles has focused on independently modeling state or action variables without simultaneously considering state-action representations.\n\n$\\bullet$ Q2.1 and Q3: For the graph $G_{sa}$, which contains only a single state-action representation variable, we traverse all encoding trees that satisfy the height constraint, instead of $\\mathcal{T}^2$, to find the optimal encoding tree.\nTherefore, the nodes in $T_{sa}^*$ can have more than two children.\n\nIn our work, the input variables are value sets obtained from samples in the replay buffer. \nThus, the number of state-action pairs in the representation variable $Z_t$ equals the batch size, denoted by $n$.\nThe settings and sensitivity analysis for $n$ in different tasks are provided in Appendix D and Appendix E.5.\n\nIn continuous state-action spaces, it is infeasible to traverse all possible variable values and directly optimize the joint distribution probabilities. \nTherefore, we derived the variational upper and lower bounds of structural mutual information and set corresponding decoders to optimize it indirectly.\n\nThe graph $G_{sa}$ reflects the Q-value relationships between state-action pairs, and its optimal encoding tree represents the hierarchical state-action structure derived from the agent's policy. \nTo further capture the current  state-action coverage by agent exploration, we additionally construct the distribution graph to define value-conditional structural entropy and propose an intrinsic reward mechanism.\n\n$\\bullet$ Q2.2: For $Z_t$, we maximize its SMI with $S_{t+1}$ to establish a near one-to-one correspondence, enabling $Z_t$ to predict environmental dynamical transitions accurately.\nConversely, we minimize the SMI between $Z_t$ and $S_t$.\nThis minimization ensures that they are mutually independent, stripping $Z_t$ of any information irrelevant to state transitions.\nBy defining value-conditional structural entropy and intrinsic rewards based on this refined representation, we enhance the agent's ability to explore the environment effectively.\n\n$\\bullet$ Q2.4: We minimize its $2$-dimensional structural entropy of $G_{sa}$ to generate its $2$-layer optimal encoding tree $T_{sa}^*$, where each non-root and non-leaf node corresponds to a sub-community including state-action pairs with similar policy values.\nThe set of all sub-communities is labeled as $V_1$.\nThe term $-H(V_1)$ is introduced in the intrinsic reward mechanism to address the issue of uniform exploration across all sub-communities.\nWithout this term, the agent might uniformly explore all sub-communities, including those with very low policy values, which leads to imbalanced exploration.\nBy incorporating $-H(V_1)$ we penalize uniform coverage and bias the agent towards exploring sub-communities with higher policy values. \n\n$\\bullet$ Q5: The visualization of state coverage in the continuous Cartpole Balance task is provided in Figure 3 of the Author Rebuttal PDF.\n\nFor Table 1 in the manuscript, we did not report experimental results where the final success rate was less than 20%, and did not report the required steps for models that did not achieve the target reward.\n\n$\\bullet$ Q6: We employ the k-NN entropy estimator in Equation 1 to estimate the lower bound of our value-conditional structural entropy.\n\nThe term 'their' in 'due to their instability' refers to traditional maximum entropy exploration methods, emphasizing the performance instability of these methods and the importance of dynamic-relevant state-action representations.\n\nThe entropy reduction $\\Delta H$ is provided in the Author Rebuttal.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "g9eVvRVNXh", "reviewer": "Reviewer_XMx1", "summary": "This paper aims to tackle the issue in existing RL exploration methods - the ignorance of inherent structure within the state and action space. Therefore the authors propose a new intrinsic reward mechanism that maximizes value-conditional structural entropy and it is adaptable to high-dimensional RL environments with sparse rewards.", "questions": "- For Figure 3, how many random seeds are used? The authors only plot a single seed (or average performance) without variance for this experiment, unlike other experiments. Is there a reason for it? \n- For Section 5.4 Ablation Studies, the difference among SI2E, SI2E-DB, and SI2E-VCSE, doesn't seem to be very noticeable, especially for final performance. Can the authors show more results on more tasks with clearer difference?", "limitations": "- I don't find any big limitation remains undiscussed for now. However I do have some concerns and questions mentioned in the weaknesses and questions sections.\n\n(Post Rebuttal score 5->6)", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well-motivated. \n- The presentation is clear and easy to follow, with enough proofs to support the method design. \n- The authors present comprehensive experimental evaluations on both procedurally-generated environments and high-dimensional continuous control problems.", "weaknesses": "- In L78-80, the authors claim that SI2E significantly improves final performance compared to SOTA. However for experiments with on Minigrid are not compared to sota (for example, some episodic intrinsic reward mechanisms), which seems to be over-claimed. The authors should better add more sota baselines or change the claims in the introduction.\n- The authors do not mention problems regarding potential asymptotic inconsistency. Is the proposed method asymptotically consistent? How will the proposed intrinsic reward get rid of potential influence on the final performance?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We systematically address each of your queries, labeling weaknesses as 'W' and questions as 'Q'. \nPlease note that, unless otherwise specified, any table or figure refers to the supplementary results in the Author Rebuttal PDF.\n\n$\\bullet$ W1: Additional Experiments.\nOur work primarily addresses the limitations of traditional information-theoretic exploration methods. \nTherefore, we focused on comparisons with SE and VCSE in the MiniGrid environment.\n\nTo address your concern, we have incorporated the DRM model (ICLR 2024) as an additional baseline. \nConsistent with the experiments in the original DRM paper, we conducted extensive evaluations in both the MetaWorld and DMControl environments. \nAdditionally, we introduced the MADE baseline in the MiniGrid environment for a more comprehensive comparison.\n\nThe results, as shown in Table 1, demonstrate that SI2E consistently outperforms these stronger baselines. \nThese findings reinforce the robustness and superior performance of SI2E compared to state-of-the-art models.\nBased on these comprehensive evaluations, we will revise the claims in the introduction to accurately reflect the scope of our comparisons and the strengths of our framework.\n\n$\\bullet$ W2: Asymptotically Consistentence.\nThank you for raising this critical point. We have thoroughly investigated the asymptotic properties of our proposed method, SI2E, and confirmed its asymptotic consistency. \nThis means that as the number of training steps approaches infinity, the learned policy converges to the optimal policy. \nThe underlying theoretical framework ensures the robustness and reliability of our approach in the long run.\n\nRegarding the influence of the proposed intrinsic reward on final performance, we designed the intrinsic reward mechanism to complement, rather than interfere with, the extrinsic rewards. \nThe value-conditional structural entropy (VCSE) used as an intrinsic reward encourages efficient exploration by guiding the agent towards high-value sub-communities. \nThis intrinsic reward is gradually reduced as the agent's exploration becomes more efficient, allowing extrinsic rewards to dominate and ensuring that final performance is not adversely affected.\n\n$\\bullet$ Q1 and Q2: Ablation Studies.\nAs mentioned in our experiment setup, all results were obtained using ten different random seeds to ensure robustness. \nInitially, due to space constraints, Figure 3 (original manuscript) displayed only the average performance. \nTo address your concern, we have included the standard deviation for multiple runs in Figure 1 (Author Rebuttal) to understand the variance better.\n\nTo further demonstrate the importance of the two critical components of SI2E, we conducted additional ablation experiments in the MetaWorld environment, specifically focusing on the Door Open and Faucet Open tasks. \nThe results, illustrated in Figure 1 (Author Rebuttal), clearly show SI2E's significant performance advantages over its variants: SI2E-DB (without the embedding principle) and SI2E-VCSE (without the intrinsic reward mechanism).\nThese additional results provide a more comprehensive comparison and highlight the distinct contributions of each component to SI2E's overall performance.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We are immensely grateful for all reviewers' insightful comments, which have guided a comprehensive refinement of our manuscript. 
Please note that supplementary experimental results, including two tables and three figures, are available in the PDF. 
Unless otherwise specified, any table or figure refers to these supplementary results.

$\bullet$ **Related Work.**
We have reorganized the related work section in the appendix into three subsections: Maximum Entropy Exploration, Representation Learning, and Structural Information Principles.

In this work, we leverage structural information principles to derive the hierarchical state-action structure and define value-conditional structural entropy as an intrinsic reward, leading to more effective agent exploration.
Compared to current maximum entropy explorations, SI2E introduces and minimizes sub-community entropy to motivate the agent to explore specific sub-communities with high policy values. 
This approach avoids redundant explorations in low-value sub-communities and enhances maximum coverage exploration. 
Unlike the VCSE baseline, our method enables balanced exploration without needing prior knowledge of downstream tasks, effectively addressing previous approaches' limitations.

Additionally, our work introduces structural mutual information to measure the structural similarity between two variables for the first time.
We further present an innovative embedding principle that incorporates the representation variable's entropy and mutual information with state variables, more effectively eliminating irrelevant information than the traditional Information Bottleneck principle.

$\bullet$ **Generation of Optimal Encoding Trees.**
We have provided additional explanations and illustrative examples for the encoding tree optimization on $\mathcal{T}^2$.
As shown in Figure 2(a), the stretch operator is executed over sibling nodes $\alpha_i$ and $\alpha_j$ that share the same parent node, $\lambda$. 
The detailed steps of this operation are as follows:
\begin{equation}
    {\alpha^\prime}^- = \lambda\text{,}\quad {\alpha_i}^-=\alpha^\prime\text{,}\quad {\alpha_j}^-=\alpha^\prime\text{,}
\end{equation}
where $\alpha^\prime$ is the added tree node via the stretch operation.
The corresponding variation in structural entropy, $\Delta H$, due to the stretch operation is calculated as follows:
\begin{equation}
    \Delta H = -\frac{g_{\alpha_i} + g_{\alpha_j} - g_{\alpha^\prime}}{\operatorname{vol}(G)} \cdot \log \frac{\operatorname{vol}(\alpha^\prime)}{\operatorname{vol}(G)} \text{.}
\end{equation}
At each iteration, the HCSE algorithm greedily selects the pair of sibling nodes that cause the maximum entropy variation, $\Delta H$ to execute one stretch optimization. 

For $G_{sa}$, which involves only a single state-action representation variable, $Z_t$, we do not use the $2$-layer approximate binary tree constraint from SMI. 
Instead, we exhaustively search all encoding trees that meet the height constraint to identify the optimal one. 
Specifically, we apply the stretch and compress operators from the HCSE algorithm to iteratively and greedily optimize the encoding tree for $G_{sa}$.
A visual explanation is provided in Figure 2(b), which intuitively illustrates the optimization process.

$\bullet$ **Intuition Behind Figure 1.**
Figure 1 in our manuscript illustrates a six-state Markov Decision Process (MDP) with four actions. The different densities of the blue and red lines represent different actions, as indicated in the legend, resulting in state transitions with the objective of returning to the initial state $s_0$. 
Solid lines specifically denote actions $a_0$ and $a_1$.
The transitions between states $s_2$ and $s_5$ are considered redundant because they do not contribute to the primary objective of returning to $s_0$. 
Therefore, the state-action pairs $(s_2, a_0)$ and $(s_5, a_1)$ have lower policy values.

A policy maximizing state-action Shannon entropy would encompass all possible transitions (blue color). 
In contrast, these redundant state-action pairs are grouped into a sub-community by leveraging structural information. 
The policy based on value-conditional structural information minimizes the entropy of this sub-community to avoid visiting it unnecessarily. 
Simultaneously, it maximizes state-action entropy, resulting in maximal coverage for transitions (red color) that are more likely to contribute to the desired outcome in the simplified five-state MDP.

In this scenario, at each timestep $t$, $s_t$, $s_{t+1}$, and $z_{t}$ denote the representations of the state before the transition, the state after the transition, and the corresponding state-action pair, respectively.

$\bullet$ **$2$-layer Approximate Binary Tree and $l$-transformation.**
Our approach utilizes $2$-layer approximate binary trees as the structural framework for measuring the structural similarity between two variables. 
The $2$-layer binary tree represents a one-to-one matching structure between variables, which facilitates the calculation of the minimum required bits to determine accessible vertices via a single-step random walk, e.g., the joint structural entropy of two variables.
Using a $2$-layer binary tree ensures computational traceability. 
More complex structures will increase the cost of increased computational complexity.

The $l$-transformation systematically traverses all potential one-to-one matchings between the variables, providing a comprehensive measure of their structural similarity.
By employing the $l$-transformation, we guarantee that the matchings are unique and non-redundant. 
The $l$-transformation is integral to the formal definition of SMI. 

This choice might introduce certain limitations; however, our primary goal was to establish a foundational framework. 
We recognize the potential for further exploration of alternative structures for defining SMI in future research.

Meta-review: this paper proposes a "Effective Exploration framework", based on information theoretic principles. 
The experiment results show in general improvement comparison to the existing works. 
Most of the reviewers' concerns have been satisfactory addressed by the authors. This paper brings 
new ideas and might be of significance for the machine learning community. It is recommended for acceptance to NeurIPS 24.
Decision: Accept (poster)