Effective Exploration Based on the Structural  Information Principles

Authors: xianghua  zeng
hao  peng
angsheng  li
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 04:57:04

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.

Main paper: 
 introduction: 
 Reinforcement Learning (RL) has emerged as a pivotal technique for addressing sequential decisionmaking 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 [Prathiba et al., 2021 , Pérez-Gil et al., 2022] . In the realm of RL, striking a balance between exploration and exploitation is 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 information-theoretic 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 as Soft Q-learning [Nachum et al., 2017] , SAC [Haarnoja et al., 2018] , and MPO [Abdolmaleki et al., 2018] . Additionally, various objectives focused on maximizing state entropy are utilized to ensure comprehensive state coverage [Hazan et al., 2019 , Islam et al., 2019] . To facilitate the exploration of complex state-action pairs, MaxRenyi optimizes Rényi entropy across the state-action space [Zhang et al., 2021a] . However, a prevalent issue with entropy maximization strategies is their tendency to bias exploration towards low-value states, making them vulnerable to imbalanced state-value distributions in supervised settings. To mitigate Here, s ′ 2 and a ′ 0 represent vertex communities {s 2 , s 5 } and {a 0 , a 1 }, respectively. In this scenario, a policy maximizing stateaction 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 s 2 and s 5 . 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-relevant representations of state-action pairs. Despite their successes, existing information-theoretic 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 1 illustrates a 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 s 0 . Solid lines specifically denote actions a 0 and a 1 . The transitions between states s 2 and s 5 are deemed redundant as they do not facilitate the primary objective of efficiently returning to s 0 . Therefore, the state-action pairs (s 2 , a 3 ) and (s 5 , a 3 ) 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 a vertex sub-community and minimize 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.Departing from traditional information theory applied to random variables, structural information [Li and Pan, 2016] has been devised to quantify dynamic uncertainty within complex graphs under a hierarchical partitioning structure known as an "encoding tree". Structural entropy is conceptualized as the minimum number of bits required to encode a vertex accessible through a single-step random walk and is minimized to optimize the encoding tree. However, this definition is limited to singlevariable 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 a single-variable constraint. Prior research on reinforcement learning using structural information principles [Zeng et al., 2023b,c] has focused on independently modeling state or action variables without simultaneously 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-dimensional and sparse-reward environments. Initially, we embed state-action pairs into a low-dimensional space and present an innovative representation learning principle to capture dynamics-relevant information and compress dynamics-irrelevant information. 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 a 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 information-theoretic methodologies, highlighting the rationality and advantage of SI2E. Our thorough evaluations across diverse and challenging tasks in 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 at1 . Our contributions are 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 singlevariable constraint inherent in existing structural information and to enhance the acquisition of dynamics-relevant 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.  
preliminaries: 
 In this section, we formalize the definitions of fundamental concepts. The descriptions of primary notations are summarized in Appendix A.1 for ease of reference.Consider the random variable pair Z = (X, Y ) with a joint distribution probability denoted by p(x, y) ∈ (0, 1). The marginal probabilities, p(x) and p(y), are defined as p(x) = y p(x, y) and p(y) = x p(x, y), respectively. The joint Shannon entropy [Shannon, 1953] x,y p(x, y) • log p(x,y) p(x)p(y) quantifies the shared uncertainty between X and Y . It satisfies the following relationship:I(X; Y ) = H(X) + H(Y ) -H(X, Y ).Within the context of RL, the sequential decision-making problem is formalized as a Markov Decision Process (MDP) [Bellman, 1957] . The MDP is characterized by a tuple (O, A, P, R e , γ), where O denotes the observation space, A the action space, P the environmental transition function, R e the extrinsic reward function, and γ ∈ [0, 1) the discount factor. At each discrete timestep t, the agent selects an action a t ∈ A upon observing o t ∈ O. This leads to a transition to a new observation o t+1 ∼ P(o t , a t ) and a reward r e t ∈ R. 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 H(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 a given set of n independent and identically distributed samples from a d x -dimensional space {x i } n-1 i=0 , the entropy of variable X is estimated as follows:EQUATIONwhere d(x i ) is twice the distance from x i 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 I(Z; Y ) between Z and Y , capturing the relevant features of Y within Z.Concurrently, the IB principle imposes a complexity constraint by minimizing the mutual information I(Z; 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.The encoding tree T of an undirected and weighted graph G = (V, E) is characterized as a rooted tree with the following properties: 1) Each tree node α in T corresponds to a subset of graph verticesV α ⊆ V .2) The subset V λ of tree root λ encompasses all vertices in V . 3) Each subset V ν of a leaf node ν in T only contains a single vertex v, thus V ν = {v}. 4) For each non-leaf node α, the number of its children is assumed as l α , with the i-th child specified as α i . The collection of subsets V α1 , . . . , V α lα constitutes a sub-partition of V α .Given an encoding tree T whose height is at most K, the K-dimensional structural entropy of graph G is defined as follows:EQUATIONwhere g α is the weighted sum of all edges connecting vertices within the subset V α to vertices outside the subset V α .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 no 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 (e.g., independence assumptions, noiseless settings, model well-specification, 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to 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 fairness. • 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 acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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, Y ) with |X| = |Y | = n, we construct an undirected bipartite graph G xy to represent the joint distribution of X and Y . In G xy , each vertex x ∈ X connects to each vertex y ∈ 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, x,y p(x, y) = 1. Each single-step random walk in G xy accesses either a vertex from X or Y . The structural entropy of variable X in G xy is defined as the number of bits required to encode all accessible vertices in the set X. It is calculated using the following formula:EQUATION)where the sum of all vertex degrees is twice the total sum of edge weights, resulting in vol(G xy ) = 2.The structural entropy H SI (Y ) is defined similarly. We restrict the partitioning structure of G xy to 2-layer approximate binary trees, denoted as T 2 , 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 a one-layer encoding tree, T 0 xy , designating each non-root node α's parent as the root λ, with α -= λ. By applying the stretch operator from the HCSE algorithm [Pan et al., 2021] , we pursue an iterative and greedy optimization of T 0 xy , further detailed in Appendix A.2. The optimal encoding tree, T * xy , for G xy and the joint entropy under T * xy are achieved through:EQUATIONUtilizing 2-layer approximate binary trees as the structural framework ensures computational tractability and more complex structures will increase the cost of increased computational complexity, which can be prohibitive for practical applications. We derive the following proposition regarding T 2 , with the detailed proof provided in Appendix B.1. Proposition 3.1. Consider an undirected graph G = (V, E) with vertices v i and v j in V . If the edge (v i , v j ) is absent from E, then in the 2-layer approximate binary optimal encoding tree T * ∈ T 2 , there does not exist any non-root node α such that both v i and v j are included in its subset V α .Each intermediate node α ∈ T * xy corresponds to a subset comprising exactly one x vertex and one y vertex, thus establishing a one-to-one matching structure between variables X and Y . The i-th intermediate node in T * xy , ordered from left to right, is denoted as α i . Within this subset, the x and y vertices are labeled as x i and y i , respectively.To define structural mutual information accurately, it is essential to consider the joint entropy of two variables under various partition structures. We introduce an l-transformation applied to T *xy to systematically traverse all potential one-to-one matching of these variables, providing a comprehensive measure of their structural similarity. Given an integer parameter l > 0, this transformation generates a new 2-layer approximate binary tree, T l xy , representing an alternative one-to-one matching structure. Definition 3.2. For each intermediate node α i in T l xy , the x and y vertices in T l αi are specified as T l αi = {x i ′ , y i }, where i ′ = (i + l) mod n. The resulting tree T l xy is equivalent to the optimal tree T * xy when l = 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) + H(Y ) -H(X, Y ) in traditional information theory, we formally define the structural mutual information, I SI (X; Y ), as follows:I SI (X; Y ) = n-1 l=0 H SI (X) + H SI (Y ) -H T l xy (X, Y ) = i,j p(x i , y j ) • log 2 p(x i ) + p(y j ).(5) The detailed derivation is provided in Appendix C.1. 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 I SI (X; Y ) and I(X; Y ), with a detailed proof in Appendix B.2. Theorem 3.4. For a tuning parameter 0 ≤ ϵ ≤ 1, its holds for the structural mutual information I SI (X; Y ), traditional mutual information I(X; Y ), and joint Shannon entropy H(X, Y ) that:EQUATION)4 The Proposed SI2E FrameworkIn this section, we describe the detailed designs of the proposed SI2E framework, which captures dynamic-relevant state-action representations through structural mutual information (see Section 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 .Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes] Justification: The main experimental results can 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. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
state-action representation learning: 
 To effectively learn dynamics-relevant state-action representations, we present an innovative embedding 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 at timestep t encompass the current observation O t and the action A t , with the target being the subsequent observation O t+1 . We denote the encoding of observations O t and O t+1 as states S t and S t+1 , respectively. We aim to generate a latent representation Z t for the tuple (S t , A t ), which preserves information relevant to S t+1 while compressing information pertinent to S t . This embedding process mentioned above is detailed as follows:EQUATIONwhere f s and f z are the respective encoders for states and state-action pairs (step I. a in Figure 2 ). EQUATION)To concurrently decrease the conditional entropy H(Z t |S t ), we introduce a predictive objective (See Appendix C.4) through a tractable decoder q z|s for the conditional probability p(z t |s t ) as follows:EQUATIONwhere L z|s represents the log-likelihood of Z t given S t .To efficiently optimize I SI (Z t ; S t+1 ), we maximize its lower bound, I(Z t ; S t+1 ), as detailed in Theorem 3.4. By utilizing an alternative decoder q s|z for the conditional probability p(s t+1 |z t ), we obtain a lower bound of I(Z t ; S t+1 ) (See Appendix C.5) as follows:EQUATIONwhere L s|z denotes the log-likelihood of S t+1 conditioned on Z t .Within our SI2E framework, the definitive loss for representation learning is a combination of the above bounds, L = L up + L z|s + η • L s|z , where η is a Lagrange multiplier used to maintain equilibrium among the specified terms.We have designed a unique intrinsic reward mechanism to 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 sa (step II. b in Figure 2 ) that encapsulates the value relationships caused by the agent's policy. Within this graph, any two vertices v i and v j is connected by an undirected edge whose weight w ij is determined as:w ij = ||π(s i t , a i t ) -π(s j t , a j t )|| 2 .The state-action pairs (s i t , a i t ) and (s j t , a j t ) are associated with vertices v i and v j , respectively. We minimize the 2-dimensional structural entropy of this graph G sa to generate its 2-layer optimal encoding tree, denoted as T * sa (step II. c in Figure 2 ). This tree T * sa delineates a hierarchical community structure among the state-action vertices, with the root node corresponding to a community encompassing all vertices. Each intermediate node in T * sa corresponds to a 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 ′ sa (step II. d in Figure 2 ). The graph G ′ sa shares the same vertex set as G sa . The following proposition confirms the existence of such a graph, with a detailed proof provided in Appendix B.4. Proposition 4.2. Given positive visitation probabilities p(s 0 t , a 0 t ), . . . , p(s n-1 t , a n-1 t) for all stateaction pairs, there exists a weighted, undirected, and connected graph G ′ sa , where each vertex's degree d i equals its visitation probability p(s i t , a i t ). In the graph G ′ sa , the set of all state-action vertices is denoted as V 0 , and the set of all stateaction sub-communities is denoted as V 1 . The Shannon entropies associated with the distribution of visitation probabilities for these sets are represented as H(V 0 ) and H(V 1 ), respectively, where H(V 0 ) = H(S t , A t ). Within the 2-layer state-action community represented by T * sa , we define the structural entropy of G ′ sa using Equation 2, denoted as H T * sa (G ′ sa ) (step II. e in Figure 2 ). The following theorem delineates the relationship between the value-conditional entropy H T * sa (G ′ sa ) with the state-action Shannon entropy H(S t , A t ). A detailed proof is provided in Appendix B.5.Theorem 4.3. For a tuning parameter 0 ≤ ζ ≤ 1, it holds for the structural entropy H T * sa (G ′ sa ) and the Shannon entropy H(S t , A t ) that:EQUATIONwhereH(V 0 ) -H(V 1 ) is a variational lower bound of H T * sa (G ′ sa ).On the one hand, the term H(V 0 ) ensures maximal coverage of the entire state-action space, analogous to the traditional Shannon entropy. On the other hand, the term H(V 1 ) mitigates uniform coverage among state-action subcommunities 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 k-NN entropy estimator in Equation 1 to estimate the lower bound:EQUATION)where d z is the dimension of state-action embedding, n 0 and n 1 are the vertex numbers in V 0 and V 1 , and d(v) is twice the distance from vertex v to its k-th nearest neighbor. By ignoring the constant term in Equation 12, we define the intrinsic reward r i t and train RL agents to address the target task using a combined reward r t = r e t + β • r i t (step II. f in Figure 2 ), where β is a positive hyperparameter that modulates the trade-off between exploration and exploitation. The pseudocode, complexity analysis, and limitations of our framework are provided in Appendix A.Table 1 : Summary of success rates and required steps to achieve target rewards in MiniGrid and MetaWorld tasks: "average value ± standard deviation" and "average improvement". Bold: the best performance, underline: the second performance.  
experiments: 
 In this section, we present a 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 a 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.Initially, we assess our framework on navigation tasks using the MiniGrid benchmark, which includes goal-reaching tasks in sparse-reward environments. This setting is partially observable: the agent receives a 7 × 7 × 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., 2021] and value-based state entropy (VCSE) [Kim et al., 2023] as our baselines. We further evaluate the SI2E framework on visual manipulation tasks from the MetaWorld 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 a scale of 1. We summarize the success rates and required steps for all exploration methods across six MetaWorld tasks in Table 1 (lower). 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 a meaningful success rate with a satisfactory number of environmental steps. This result demonstrates the SI2E's effectiveness in improving and accelerating agent exploration in challenging tasks with expansive state-action spaces.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 et al., 2021b] , for a more comprehensive comparison. We evaluate all exploration methods across six continuous control tasks, documenting the episode rewards in Table 2 . Observations reveal that SI2E remarkably increases the mean episode reward in each DMControl task. Specifically, in the Cartpole Swingup task characterized by sparse rewards, our framework boosts the average reward from 707.76 to 795.09, resulting in a 12.34% improvement in the final performance. Moreover, we compare the sample efficiency of SI2E and the best-performing baseline in Appendix E.3.These results not only demonstrate the effectiveness of SI2E in acquiring dynamics-relevant representations 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, we provide visualization experiments in Appendix E.4.To further investigate the impact of two critical components within the SI2E framework, embedding principle (Section 4.1) 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) SI2E-VCSE, employing the state-of-the-art VCSE approach [Kim et 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 SI2E's superior capabilities. Additional ablation studies for the parameters β and n are available in Appendix E.5. 6 Related Work 
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, 2021 , Mutti et 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 et al., 2023] has been proposed, which integrates value estimates into the entropy calculation to ensure balanced exploration. Nevertheless, 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, we 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 to 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.Novelty Search [Tao et al., 2020] and Curiosity Bottleneck [Kim et al., 2019b] leverage the Information 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., 2021] 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 incorporates the entropy of the representation variable. This approach more effectively eliminates irrelevant information than the traditional information bottleneck principle.Since the introduction of structural information principles [Li and Pan, 2016] , these principles have significantly transformed the analysis of network complexities, employing metrics such as structural entropy and partitioning trees. This innovative approach has not only deepened the understanding of network dynamics-even in the context of multi-relational graphs [Cao et al., 2024a] -but has also led to a wide array of applications across different domains. The application of structural information principles has extended to various fields, including graph learning [Wu et al., 2022] , skin segmentation [Zeng et al., 2023a] , and the analysis of social networks [Peng et al., 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 in robust decision-making frameworks.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes] Justification: We have provided detailed experimental settings (hyperparameter and optimizer) in our evaluation and appendix.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a 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, in appendix, or as supplemental material. 
conclusion: 
 We propose SI2E, a novel exploration framework based on structural information principles. This framework defines structural mutual information to effectively capture state-action representations relevant to 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 information-theoretic methodologies, underscoring the framework's rationality and 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 a robust and adaptable tool in reinforcement learning, particularly suited to high-dimensional and sparse-reward contexts.Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?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 error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.• 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 or the standard error of the mean. Justification: We have provided sufficient information on the computer resources in our appendix.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs 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). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: Our paper strictly maintains anonymity.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 on fundamental research in reinforcement learning and is not specifically tied to any particular applications. Furthermore, there is no direct path to negative applications.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment 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 a 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 to 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 as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?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 a 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 to 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 a 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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 creators. 
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/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was 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. 
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 to 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 contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS 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. 
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 crowdsourcing nor research with human subjects Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• 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. 
 
 Appendix: A.1 Notations In this subsection, we have provided additional explanations and illustrative examples for the encoding tree optimization on T 2 . As shown in Figure 4 , the stretch operator is executed over sibling nodes α i and α j that share the same parent node, λ. The detailed steps of this operation are as follows:EQUATION) where α ′ is the added tree node via the stretch operation.… … 𝜆𝜆 𝛼𝛼 𝑖𝑖 𝛼𝛼 𝑗𝑗 … … 𝜆𝜆 𝛼𝛼 𝑖𝑖 𝛼𝛼 𝑗𝑗 𝛼𝛼 ′Figure 4 : Stretch operation on sibling nodes within the encoding tree. The corresponding variation in structural entropy, ∆H, due to the stretch operation is calculated as:EQUATION)EQUATION)EQUATIONEQUATION)As shown in Algorithm 1, the HCSE algorithm iteratively and greedily selects the pair of sibling nodes that cause the maximum entropy variation, ∆H to execute one stretch optimization.Algorithm 1 The Encoding Tree Optimization on T 21: Input: one-layer initial encoding tree T 2: Output: the optimal encoding tree T * ∈ T 2 3: while True do 4:(α i , α j ) ← maximize the entropy reduction ∆H caused by one stretch operation 5:if ∆H = 0 then 6:Break 7:end ifCreate a new tree node α ′ 9: (α ′ ) -← λ, (α i ) -← α ′ , (α j ) -← α ′ 10: end while A.3 Intuitive Example of Optimal Encoding Tree 𝑥𝑥 0 𝑥𝑥 1 𝑥𝑥 2 𝑥𝑥 3 𝑦𝑦 0 𝑦𝑦 1 𝑦𝑦 2 𝑦𝑦 3 0.2 0.3 0.2 0.2 0.05 0.03 0.02 a) Bipartite Graph 𝐺𝐺 𝑥𝑥𝑥𝑥 {𝑥𝑥 0 , 𝑦𝑦 0 }{𝑥𝑥 1 , 𝑦𝑦 1 }{𝑥𝑥 2 , 𝑦𝑦 2 }{𝑥𝑥 3 , 𝑦𝑦 3 } b) Optimal Encoding Tree 𝑇𝑇 𝑥𝑥𝑥𝑥 * {𝑥𝑥 1 , 𝑦𝑦 0 }{𝑥𝑥 2 , 𝑦𝑦 1 }{𝑥𝑥 3 , 𝑦𝑦 2 }{𝑥𝑥 0 , 𝑦𝑦 3 } c) Resulting Encoding Tree 𝑇𝑇 𝑥𝑥𝑥𝑥 1Algorithm 2 Effective Exploration based on Structural Information Principles 1: Input: batch size n, update interval t up 2: Initialize: agent's policy π, encoder functions f s and f z , decoder functions q m , q z|s , q s|z , replay buffer B 3: for each episode do 4:for each environmental step t do 5:Collect transition τ t = (s t , a t , s t+1 , r e t ) using the encoder f s and policy π 6:Sample a batch {τ ti } n i=1 from B including the variables S t , A t , and S t+1 7:Adopt encoder functions f z to obtain state-action embeddings Z t 8:# Maximum Structural Entropy Exploration 9:Construct the state-action graph G sa according to the policy π and generate its hierarchical community structure T * sa 10:Employ the k-NN estimator to estimate the lower bound end for 20: end forH(V 0 ) -H(V 1 )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(n 2 ) time complexity, the generation of 2-layer approximate binary trees requires O(n • log 2 n) time complexity, and the calculation of mutual information involves a time complexity of O(n 2 ). During the effective exploration phase, the generation of hierarchical community structure incurs a O(n • log 2 n) complexity, the construction of the distribution graph leads to a complexity of O(n 2 ), and value-conditional structural entropy is calculated with O(n) time complexity.Our work, which is a result of 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-art information theory exploration method as the baseline in 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 on the advantages and restrictions brought by this expansion.B.1 Proof of Proposition 3.1 Proof. For any two vertices v i ∈ V and v j ∈ V without any edge connecting them, their corresponding tree nodes are denoted as α i and α j . These nodes' parents are initially assigned as the root node λ. Before executing one stretch operation on vertices α i and α j , their structural entropies are calculated as follows:EQUATION)where d i and d j are the degrees of vertices v i and v j . Post-stretch operation, their structural entropies are given by:EQUATION)where α ′ are their new common parent node. The absence of an edge between v i and v j ensures that:EQUATION)The structural entropy of α ′ can be determined as:EQUATION)The entropy reduction ∆H, consequent to the stretch operation on vertices v i and v j , is calculated as:∆H = - d i vol(G) • log d i vol(G) - d j vol(G) • log d j vol(G) -- d i vol(G) • log d i d i + d j - d j vol(G) • log d j d i + d j - d i + d j vol(G) • log d i + d j vol(G) = - d i vol(G) • log d i vol(G) - d j vol(G) • log d j vol(G) -- d i vol(G) • log d i vol(G) - d j vol(G)• log d j vol(G) = 0.(22) Given the zero reduction in entropy, as per lines 5 and 6 of the optimization algorithm for T 2 (See Appendix A.2), the stretch operation involving v i and v j is omitted from the optimization process.Proof. The difference between the mutual information I SI (X; Y ) and I(X; Y ) is expressed as:I SI (X; Y ) -I(X; Y ) = i,j p(x i , y j ) • log 2 p(x i ) + p(y j ) - i,j p(x i , y j ) • log p(x i , y j ) p(x i ) • p(y j ) = i,j p(x i , y j ) • log 2 p(x i ) + p(y j ) • p(x i ) • p(y j ) p(x i , y j ) = i,j p(x i , y j ) • log 1 p(x i , y j ) • 2 • p(x i ) • p(y j ) p(x i ) + p(y j ) = i,j p(x i , y j ) • log 1 p(x i , y j ) • 2 1 p(xi) + 1 p(yj ).(23) Given the conditions p(x i , y j ) ≤ p(x i ) ≤ 1 and p(x i , y j ) ≤ p(y j ) ≤ 1, the following inequalities are satisfied:EQUATIONEQUATIONBy defining ϵ i = log p(xi,yj ) p(x i ) and ϵ j = log p(xi,yj ) p(y j ), we obtain the following results:EQUATIONEQUATIONB.3 Proof of Theorem 4.1Proof. For a one-to-one correspondence of variables X and Y , the joint probability of a tuple (x i , y j ) is as follows:EQUATION)The calculation for I SI (X; Y ) is carried out in the following manner:I SI (X; Y ) = n l=0 H SI (X) + H SI (Y ) -H T l xy (X, Y ) = i,j p(x i , y j ) • log 2 p(x i ) + p(y j ) = i p(x i ) • log 1 p(x i ) = H(X). (30)Similarly, the calculation for I(X; Y ) proceeds as follows:EQUATIONHence, I SI (X; Y ) equals I(X; Y ) when the joint distribution between X and Y shows a one-to-one correspondence.Proof. Now, we employ mathematical induction to demonstrate the existence of the graph G ′ sa . Base Case (n = 2): Suppose the degree distribution of two vertices is given by (p 0 , p 1 ) with p 0 ≤ p 1 . We construct the graph G ′ sa as follows:• Create an edge with weight p 0 between v 0 and v 1 .• Add a self-connected edge at vertex v 1 with weight p 1 -p 0 . Inductive Step (n = k): Assume that, the graph G ′ sa with k vertices exists and satisfies Proposition 4.2. Inductive Case (n = k + 1): Consider the addition of a new vertex v k to construct G ′ sa with k + 1 vertices using the following steps:• Start with a subgraph that includes the first k vertices, yielding a distribution of (p ′ 0 , . . . , p ′ k-1 ) with k-1 i=0 p ′ i = 1. • Modify the weight of all edges connected to each vertex v i (0 ≤ i ≤ k) by a factor (1-pn)pi p ′ i .• For each vertex v i , create an edge with weight p i p n connecting it to the new vertex v k .• Add a self-connected edge at vertex v k with weight p 2 k . 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 ′ sa for any n.In the tree T * sa , we denote the i-th intermediate node as α i and its j-th child node as α ij . The single state-action vertex in the corresponding subset of α ij is assumed as (s ij , a ij ). In the graph G ′ sa , the degree of any state-action vertex (s ij , a ij ) is equated to its visitation probability, thereby:EQUATION)The 2-dimensional value-conditional structural entropy H T * sa (G ′ sa ) is calculated through the following expressions:EQUATION)By definingζ ij = log p(sij ,aij ) p(sij ,aij ) vol(αi), we obtain that:EQUATION)Selecting the minimal ζ-value as ζ * allow us to reformulate Equation 33 as follows:EQUATIONEQUATIONEQUATION) C Detailed Derivations C.1 Derivation of I SI (X; Y )For each intermediate node α i ∈ T * xy with vertex subset {x i , y i }, the entropy sum of this node and its children is calculated as follows:-g αi vol(G xy ) • log vol(α i ) vol(G xy ) - p(x i ) vol(G xy ) • log p(x i ) vol(α i ) - p(y i ) vol(G xy ) • log p(y i ) vol(α i ) = - g αi 2 • log vol(α i ) 2 - p(x i ) 2 • log p(x i ) vol(α i ) - p(y i ) 2 • log p(y i ) vol(α i ).(39)TheH SI (X) + H SI (Y ) -H T * xy (X, Y ) term in Equation 5 is calculated as follows: i - p(x i ) 2 • log p(x i ) 2 - p(y i ) 2 • log p(y i ) 2 - i - g αi 2 • log vol(α i ) 2 - p(x i ) 2 • log p(x i ) vol(α i ) - p(y i ) 2 • log p(y i ) vol(α i ).(40) Proposition 3.1 ensures that:EQUATIONConsequently, we can reformulate Equation 40 as follows:i p(x i ) 2 • log 2 p(x i ) + p(y i ) + p(y i ) 2 • log 2 p(x i ) + p(y i ) - p(x i ) + p(y i ) -2 • p(x i , y i ) 2 • log 2 p(x i ) + p(y i ) = i p(x i , y i ) • log 2 p(x i ) + p(y i ).(42) For any integer l > 0, the H SI (X) + H SI (Y ) -H T l xy (X, Y ) term in Equation 5is given by:EQUATIONConsequently,EQUATION)C.2 Upper Bound of I SI (Z t ; S t ) Theorem 3.4 assures the following inequality:EQUATION)Given the relationship between joint entropy and conditional entropy in traditional information theory, this inequality can be reformulated as follows:EQUATION) C.3 Upper Bound of I(Z t ; S t )Through the non-negativity of KL-divergence, the following upper bound of I(Z t ; S t ) holds that:I(Z t ; S t ) = p(z t , s t ) • log p(z t |s t ) p(z t ) = p(z t , s t ) • log p(z t |s t ) q m (z t ) -D KL (p||q m ) ≤ [p(z t , s t ) • D KL (p(z t |s t )||q m (z t ))]. (47) C.4 Upper Bound of H(Z t |S t )Through the non-negativity of KL-divergence, the following upper bound of H(Z t |S t ) holds that:EQUATION)C.5 Lower Bound of I(Z t ; S t+1 )Leveraging the non-negative Shannon entropy and KL-divergence, we obtain the lower bound of I(Z t ; S t+1 ):EQUATION)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 3000K/1000K for the MiniGrid benchmark, 200K/100K for the MetaWorld benchmark, and 250K for the DeepMind Control Suite (DMControl).A2C implementation details. In our implementation of the A2C algorithm, we utilize the official RE3 implementation2 , 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 are 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 β = 0.005 and k = 5, in line with the original framework. The comprehensive hyperparameters for the A2C algorithm are detailed in Table 4 . DrQv2 implementation details. For the DrQv2 algorithm, we employ its official implementation3 [Yarats et al., 2021] , maintaining the original hyperparameter settings unless specified otherwise.A fixed noise level of 0.2 and k = 12 are used for all exploration methods, including SE, VCSE, MADE, and SI2E. In the calculation of intrinsic rewards in baselines, we train the Intrinsic Curiosity Module [Pathak et al., 2017] using representations from the visual encoder to measure vertex distance in the estimation of value-conditional structural entropy. Specific hyperparameters in the DrQv2 are summarized in Table 5 . MiniGrid Experiments. In our MiniGrid benchmark experiments, we encompass six navigation tasks, including RedBlueDoors, SimpleCorssingS9N1, KeyCorridor, DoorKey-6x6, DoorKey-8x8, and Unlock, with visual representations provided in Figure 6 . Notably, all tasks are employed in their original forms without any modifications. MetaWorld Experiments. In our evaluation using the MetaWorld benchmark, we conduct experiments 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 9 illustrates the learning curves for the A2C algorithm integrated with our SI2E framework, as well as 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. In 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. To further substantiate our results on the Minigrid environment, 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 6 demonstrate that our method consistently maintains a performance advantage in terms of effectiveness and efficiency, even when compared to advanced episodic intrinsic reward mechanisms. 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+SI2E, respectively. As shown in Figure 10 , SI2E consistently and significantly achieves higher success rates with fewer environmental steps across all manipulation tasks. On average, SI2E improves the final performance by 10.21% and sample efficiency by 45.06%. To provide additional validation, we 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 in Table 7 , demonstrate the robustness and superior performance of our method with different underlying agents.î 4 î 5 î 5 î 5 6XFFHVV5DWH %XWWRQ3UHVV î 4 î 5 î 5 î 5 'RRU2SHQ î 4 î 5 î 5 î 5 'UDZHU2SHQ î 4 î 4 î 4 î 4 î 5 (QYLURQPHQWDO6WHS 6XFFHVV5DWH )DXFHW&ORVH î 4 î 4 î 4 î 4 î 5 (QYLURQPHQWDO6WHS )DXFHW2SHQ î 4 î 5 î 5 î 5 (QYLURQPHQWDO6WHS :LQGRZ2SHQ 'U4Y 'U4Y6( 'U4Y9&6( 'U4Y6,(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. For each task, we benchmark the convergence reward of the 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 11 , SISA demonstrates an average improvement of 35.60% in sample efficiency. This improvement is reflected in a reduction in the required environmental steps, decreasing from 31.83% to 20.5% of the total steps required to achieve the reward target. 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+SI2E. 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 in 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.17% improvement in final performance and a 15.28% increase in sample efficiency. 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 2dimensional vectors. Figure 13a 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 (Section 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 to the SE and VCSE baselines, prevents biased exploration towards low-value areas and effectively explores high-value crucial areas, like the crossing point, with fewer environmental steps, ensuring its performance superiority. To investigate the influence of parameters β and n on our framework's 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 β consistently enhances performance across both tasks, substantiating the effectiveness of our exploration method. Conversely, Figure 15b demonstrates that variations in batch size n yield comparable performance outcomes, particularly notable in Pendulum Swingup task, thereby confirming the SI2E's stability amidst variations in batch size. Guidelines:î 5 î 5 (QYLURQPHQWDO6WHS (SLVRGH5HZDUG +RSSHU6WDQG î 5 î 5 (QYLURQPHQWDO6WHS (SLVRGH5HZDUG 3HQGXOXP6ZLQJXS (a) Effect of scale parameter β î 5 î 5 (QYLURQPHQWDO6WHS (SLVRGH5HZDUG +RSSHU6WDQG Q Q Q î 5 î 5 (QYLURQPHQWDO6WHS (SLVRGH5HZDUG 3HQGXOXP6ZLQJXS Q Q Q (b) Effect of batch size n• 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 in 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 as long as it is clear that these goals are not attained by the paper.https://github.com/SELGroup/SI2Ehttps://github.com/younggyoseo/RE3https://github.com/facebookresearch/drqv2 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. 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.
questions: questions: Please see the above weaknesses.
limitations: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The baselines are not strong enough, and more state-of-the-art models should be used for comparison.
2. The experimental results in Appendix E.5 are more suitable for inclusion in the Parameter Analysis section rather than Ablation Studies.
3. 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.
4. 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.
questions: questions: 1.Why was the A2C agent chosen for experiments on MiniGrid instead of DrQv2 or other more recent models?
2.Why was MADE not included in the comparison for experiments on MiniGrid and MetaWorld?
limitations: limitations: The authors have further discussed the encoding tree involved in the SI2E framework
paper_summary: paper_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
strength_weakness: strength_weakness: ### Unclear presentation

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

- some claims, such as those in lines 35-36 and 200-201, lack evidence or references

### Figures

- 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
- Figure 2: the presentation is cluttered
   - the layout is extremely tight with a disordered flow of annotations (vertical and horizontal), and the caption lacks clarification and is not self-contained.
   - the colour scheme (of nodes and vertices) in the two steps is unspecified
   - the space between Figure 2 and line 158 is too narrow

### Unclear and non-detailed method presentation

- the use of $T$ to represent both the tree and subsets of graph vertices (lines 117-120) is confusing
- no discussion about why 2-layer binary trees are used (lines 139-140), which is necessary to understand the approach's limitations
- only a minimal description of how an optimal encoding tree is generated from $G_{sa}$ (lines 230-231) in sec. 4.2

### Related work
the 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

### Minor points

- line 34, Renyi entropy needs a citation
- eq 2 misses explanation of $\alpha^-$
- line 139, structur -> structure
- lines 193-194, should use double dashes
- SI2E in CartPole Swingup Sparse doesn't show superiority in sample efficiency (Figure 3)
- as to line 321, better to briefly summarize the ablation findings on finetuning $\beta$ and $n$ before referring to the appendix
- the best-performing baseline is not specified in sec. 5.3 and appendix E.3
questions: questions: ### Structural entropy and graph
- 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?
- can a vertex contain joint variables or only a single variable? What is a single-variable graph?
- why is structural information limited to a single variable? Can't the underlying graph be expanded to cover multiple variables (lines 128-147)?

### Method's design and choice

- why some tree nodes in step II.c (Figure 2) have more than two children? isn't the encoding tree assumed to be binary?
- 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?
- why do we need $l$-transformation for defining structured MI (lines 155-157)?
- what is $V_1$ exactly, and how are sub-communities obtained? why does $-H(V_1)$ mitigate uniform coverage?
### Step II in Figure 2 (sec. 4.2)

- 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?

- why $\pi$ is used for a value function when it represents a policy?

- why is step d necessary after $T^\star_{sa}$ is obtained, can't $G_{sa}$ perform the required?

## Figure 1

- 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*
- which dotted line corresponds to $a_0$? note that the outgoing arrow of state $s_0$ is solid
- in step I. state-action representation, which (top) boxes correspond to $s_t$, $s_{t+1}$, and $z_t$ respectively?

### Experiments

- is it possible to visualize state coverage in other tasks like meta-world, which has continuous states?
- why are required steps or success rates not reported for some tasks in Table 1, such as RedBlueDoors and Faucet tasks?

### Other questions

- where is equation 1 used?
- lines 38-41: What is meant by 'their' in *due to their instability*? What do these lines aim to emphasize?
- what is the entropy reduction mentioned in supplement A.2?


I am willing to increase my score if the clarity questions are addressed.
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.
- 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?
questions: 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? 
- 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: 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.

(Post Rebuttal score 5->6)

Comments: title: DrQv2 Agent for MiniGrid Experiments
SOTA Baselines in MiniGrid
Asymptotic Consistency.
SOTA Baselines in MiniGrid.
Asymptotic Consistency
SOTA Baselines in MiniGrid
Additional Details about Key Issues
Additional Details about Key Issues
Additional Details about Key Issues
Additional Details about Key Issues
comment: To further address your concerns, we have conducted additional experiments using DrQv2 as the underlying agent in the MiniGrid environment and compared the performance of the VCSE and SI2E exploration methods.
The results indicates that the superior performance of our method is not limited to a specific agent but is broadly applicable and effective across a range of modern reinforcement learning models.

$\bullet$ Success Rate：
|MiniGrid|RedBlueDoors-$6$x$6$|SimpleCrossingS$9$N$1$|KeyCorridorS$3$R$1$|DoorKey-$6$x$6$|DoorKey-$8$x$8$|Unlock|
|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|
|DrQv2|$31.27 \pm 14.58$|$90.23 \pm 10.25$|$78.62 \pm 5.39$|$87.49 \pm 7.21$|-|$93.29 \pm 9.46$|
|DrQv2+VCSE|$82.05 \pm 9.17$|$92.13 \pm 6.73$|$83.27 \pm 2.33$|$94.27 \pm 2.15$|$90.15 \pm 23.71$|$93.13 \pm 5.77$|
|DrQv2+SI2E|$89.71 \pm 4.93$|$95.27 \pm 3.00$|$90.07 \pm 0.57$|$96.47 \pm 1.71$|$97.21 \pm 4.49$|$98.33 \pm 2.96$|

$\bullet$ Required Step:
|MiniGrid|RedBlueDoors-$6$x$6$|SimpleCrossingS$9$N$1$|KeyCorridorS$3$R$1$|DoorKey-$6$x$6$|DoorKey-$8$x$8$|Unlock|
|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|
|DrQv2|-|$614.71 \pm 34.72$|-|$439.23 \pm 109.24$|-|$538.22 \pm 97.36$|
|DrQv2+VCSE|$1530.92 \pm 237.18$|$179.34 \pm 26.14$|$359.22 \pm 13.29$|$517.44 \pm 31.23$|$2103.49 \pm 197.33$|$514.00 \pm 72.93$|
|DrQv2+SI2E|$847.06 \pm 74.39$|$134.97 \pm 19.77$|$198.71 \pm 6.31$|$251.17 \pm 14.94$|$1318.46 \pm 142.57$|$293.49 \pm 46.71$|
Thank you very much for your valuable suggestions and the insightful discussion regarding our work. 
Your feedback has been instrumental in guiding us to refine and enhance our research.

We will ensure that the specific experiment you recommended is included in the final version, and we will revise the associated claims accordingly.

Additionally, we sincerely appreciate your constructive feedback on our rebuttal. 
We will make sure to enhance the clarity of our responses in the future, including improved formatting of mathematical formulas and explicitly referencing specific papers by name.
We also recognize the importance of providing clear and accessible information, particularly when referencing recent findings that may not have been included in the submitted version.

We have now completed the experimental validation of another intrinsic reward mechanism, DIER, within the MiniGrid environment. 
These results have been integrated with the supplementary findings we previously provided, offering a more comprehensive analysis of the mechanism's effectiveness.

$\bullet$ Success Rate：
|MiniGrid|RedBlueDoors-$6$x$6$|SimpleCrossingS$9$N$1$|KeyCorridorS$3$R$1$|DoorKey-$6$x$6$|DoorKey-$8$x$8$|Unlock|
|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|
|Leco [1]|$81.97 \pm 10.81$|$90.02 \pm 4.13$|$90.36 \pm 0.57$|$94.37 \pm 3.41$|$92.07 \pm 19.11$|$94.48 \pm 6.39$|
|DEIR [2]|$78.32 \pm 7.21$|$91.47 \pm 8.29$|$91.81 \pm 2.13$|$94.81 \pm 5.13$|$95.41 \pm 13.27$|$95.13 \pm 12.74$|
|SI2E|$85.80 \pm 1.48$|$93.64 \pm 1.63$|$94.20 \pm 0.42$|$97.04 \pm 1.52$|$98.58 \pm 3.11$|$97.13 \pm 3.35$|

$\bullet$ Required Step:
|MiniGrid|RedBlueDoors-$6$x$6$|SimpleCrossingS$9$N$1$|KeyCorridorS$3$R$1$|DoorKey-$6$x$6$|DoorKey-$8$x$8$|Unlock|
|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|
|Leco [1]|$817.47 \pm 137.21$|$417.59 \pm 17.63$|$520.43 \pm 10.31$|$571.31 \pm 31.27$|$2168.35 \pm 293.52$|$791.40 \pm 82.39$|
|DEIR [2]|$722.37 \pm 81.93$|$523.79 \pm 31.27$|$735.87 \pm 9.24$|$410.25 \pm 29.16$|$1247.58 \pm 231.42$|$531.06 \pm 131.84$|
|SI2E|$461.90 \pm 61.53$|$139.17 \pm 27.03$|$129.06 \pm 6.11$|$230.60 \pm 19.85$|$1090.96 \pm 125.77$|$309.14 \pm 53.71$|

We are committed to making any additional revisions that may be necessary and look forward to any further feedback you may have. 
Thank you again for your time and effort in reviewing our paper. 
Your guidance has been invaluable in improving the quality and clarity of our research.

$\bullet$ Reference Paper:

[1] Jo D, Kim S, Nam D, et al. Leco: Learnable episodic count for task-specific intrinsic reward[J]. Advances in Neural Information Processing Systems, 2022, 35: 30432-30445.

[2] Wan S, Tang Y, Tian Y, et al. DEIR: efficient and robust exploration through discriminative-model-based episodic intrinsic rewards[C]//Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence. 2023: 4289-4298.
Thank you for the detailed rebuttal (although I'm not sure if it is a display issue from my end or not, I can't see most of the formulas display correctly in the compiled format).
> ... During this process, we observed that SI2E's final performance consistently stabilized at a fixed value as the number of training steps increased. 

Thank you, please also include this experiment in a later version.

> We have revised the claim in lines 78-80 of the paper to ensure accuracy and to avoid any potential overstatement. The claim now specifically highlights that SI2E significantly enhances performance within the context of "information-theoretic exploration," thereby more accurately reflecting the scope of our contribution in this domain.

Honestly speaking LECO is not sota on minigrid. Therefore please don't forget to change this claim in the final version. The experiment itself is useful to add.

I also hope that next time the authors make the rebuttal more clear to the reviewers, for example, make the formula format to be better, include the specific paper names when you mention them, and don't mention something like we prove it in the latest version of our paper without showing them when you can't submit them.

Given the above I'm a bit hesitate about my original score, and I also think the paper deserves a higher average score. Therefore for now I will increase to score to a 6. As I'm not an expert in the field I'm also open for further discussion.
To further validate the effectiveness of our proposed method, we have included an additional comparison with more advanced baselines, Leco [1] and DEIR [2]. 
We conducted experiments in the MiniGrid environment to provide a more comprehensive evaluation. The experimental results, focusing on success rate and required steps, are presented in the following two tables.

$\bullet$ Success Rate：
|MiniGrid|RedBlueDoors-$6$x$6$|SimpleCrossingS$9$N$1$|KeyCorridorS$3$R$1$|DoorKey-$6$x$6$|DoorKey-$8$x$8$|Unlock|
|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|
|Leco|$81.97 \pm 10.81$|$90.02 \pm 4.13$|$90.36 \pm 0.57$|$94.37 \pm 3.41$|$92.07 \pm 19.11$|$94.48 \pm 6.39$|
|DEIR|$78.32 \pm 7.21$|$91.47 \pm 8.29$|$91.81 \pm 2.13$|$94.81 \pm 5.13$|$95.41 \pm 13.27$|$95.13 \pm 12.74$|
|SI2E|$85.80 \pm 1.48$|$93.64 \pm 1.63$|$94.20 \pm 0.42$|$97.04 \pm 1.52$|$98.58 \pm 3.11$|$97.13 \pm 3.35$|

$\bullet$ Required Step:
|MiniGrid|RedBlueDoors-$6$x$6$|SimpleCrossingS$9$N$1$|KeyCorridorS$3$R$1$|DoorKey-$6$x$6$|DoorKey-$8$x$8$|Unlock|
|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|
|Leco|$817.47 \pm 137.21$|$417.59 \pm 17.63$|$520.43 \pm 10.31$|$571.31 \pm 31.27$|$2168.35 \pm 293.52$|$791.40 \pm 82.39$|
|DEIR|$722.37 \pm 81.93$|$523.79 \pm 31.27$|$735.87 \pm 9.24$|$410.25 \pm 29.16$|$1247.58 \pm 231.42$|$531.06 \pm 131.84$|
|SI2E|$461.90 \pm 61.53$|$139.17 \pm 27.03$|$129.06 \pm 6.11$|$230.60 \pm 19.85$|$1090.96 \pm 125.77$|$309.14 \pm 53.71$|

[1] Jo D, Kim S, Nam D, et al. Leco: Learnable episodic count for task-specific intrinsic reward[J]. Advances in Neural Information Processing Systems, 2022, 35: 30432-30445.

[2] Wan S, Tang Y, Tian Y, et al. DEIR: efficient and robust exploration through discriminative-model-based episodic intrinsic rewards[C]//Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence. 2023: 4289-4298.
Thank you very much for your thoughtful feedback and for acknowledging the clarifications we provided in our rebuttal. We greatly appreciate your constructive suggestions, which will certainly enhance the clarity and completeness of our paper.

In response to your recommendations, we have made the following adjustments to the paper:

$\bullet$ **Integration of Clarifications**: 
We have incorporated detailed explanations of Q1.2 (Explanation About Graph Vertices), Q1.3 (Single-variable Constraint of Structural Information), Q2.2 (Structural Mutual Information Principle), and Q2.4 (Sub-communities Explanation) directly into the main body of the paper. 
This ensures that the clarifications are accessible and integrated into the core content, improving the overall readability and comprehension for the readers.

$\bullet$ **Differentiation of Encoding Trees**: 
We have added an additional section in the appendix that emphasizes the distinctions between the generation of the encoding trees for $G_{xy}$ and $G_{sa}$.
This section provides a clear and concise explanation of these differences, addressing your request to highlight this aspect in the revised paper.

$\bullet$ **Figure 1 Adjustments**: 
Following your advice, we have made the legend in Figure 1 more straightforward and aligned with the clarifications provided in our earlier responses. 
This should enhance the visual clarity and facilitate a better understanding of the figure.

We hope that these revisions align with your expectations and contribute to the overall quality of the paper. 
We appreciate your willingness to raise your rating based on the improvements made and your ongoing support for our work.
Thank you for pointing this out. 
You are correct that we are not allowed to submit a revised version of the paper during the rebuttal process. 
To clarify, we have included the additional content in the appendix of our original submission, but due to the restrictions of the rebuttal phase, we are unable to submit a new version of the paper for your review.

In our previous response, we provided an overview of the main validation process to address your concerns. 
Additionally, we are providing a more comprehensive proof of asymptotic consistency here, but we acknowledge that due to the limitations of markdown formatting, some formulas may not display correctly. 
We appreciate your understanding and are happy to elaborate further if needed.

We begin by analyzing the asymptotic mean and consistency of the $k$-NN estimator for the lower bound of the value-conditional structural entropy.
In the work by Singh et al. (2003), the asymptotic consistency of the $k$-nn entropy estimator was established.
Specifically, for the entropy terms $H(V_0)$ and $H(V_1)$ in Equation 12, the following relationships hold:

\begin{equation}
    \lim_{n \rightarrow \infty}{\mathbb{E}(\widehat{H}_{KL}(V_0))}=H(V_0)\text{,}\quad\lim_{n \rightarrow \infty}{\operatorname{Var}(\widehat{H}_{KL}(V_0))} = 0\text{,}
\end{equation}

\begin{equation}
    \lim_{n \rightarrow \infty}{\mathbb{E}(\widehat{H}_{KL}(V_1))}=H(V_1)\text{,}\quad\lim_{n \rightarrow \infty}{\operatorname{Var}(\widehat{H}_{KL}(V_1))} = 0\text{.}
\end{equation}

This implies that the $k$-NN entropy estimators are asymptotically unbiased and consistent.
Considering the difference $\widehat{H}_{KL}(V_0) - \widehat{H}_{KL}(V_1)$, the asymptotic mean is given by:

\begin{equation}
    \lim_{n \rightarrow \infty}{\mathbb{E}\left(\widehat{H}_{KL}(V_0) - \widehat{H}_{KL}(V_1)\right)} = H(V_0) - H(V_1)\text{.}
\end{equation}

This result confirms that the difference estimator is asymptotically unbiased.
In the context of a $2$-layer encoding tree $T^*_{sa}$, the set $V_1$ represents sub-communities for all state-action pairs $V_0$, leading to a linear dependence between their visitation probabilities.
The covariance between $\widehat{H}_{KL}(V_0)$ and $\widehat{H}_{KL}(V_1)$ is given by:

\begin{equation}
    \operatorname{Cov}\left(\widehat{H}_{KL}(V_0),\widehat{H}_{KL}(V_1)\right) = c \cdot \operatorname{Var}(\widehat{H}_{KL}(V_0))\text{,}
\end{equation}

where $c$ is a constant parameter.
Finally, we consider the variance of the difference estimator $\widehat{H}_{KL}(V_0) - \widehat{H}_{KL}(V_1)$. 
Using the results obtained above, we have:

\begin{equation}
    \begin{aligned}
        \lim_{n \rightarrow \infty}{\operatorname{Var}\left(\widehat{H}_{KL}(V_0) - \widehat{H}_{KL}(V_1)\right)} &= \lim_{n \rightarrow \infty}{\left(\operatorname{Var}(\widehat{H}_{KL}(V_0)) + \operatorname{Var}(\widehat{H}_{KL}(V_1)) - 2 \cdot \operatorname{Cov}(\widehat{H}_{KL}(V_0),\widehat{H}_{KL}(V_1)) \right)} \\
        &= (1 - 2c) \cdot \operatorname{Var}(\widehat{H}_{KL}(V_0)) + \operatorname{Var}(\widehat{H}_{KL}(V_1)) \\
        &= 0\text{.}
    \end{aligned}
\end{equation}

This shows that the variance of the difference estimator tends to $0$ as $n$ increases, thereby proving its consistency.

Subsequently, we demonstrate the asymptotic behavior of our intrinsic reward.
Let $n_{s,a}$ denote the visitation count for a state-action pair $(s,a)$ within a finite state-action space.
Given the episodic nature of MDPs, it is assumed that all state-action pairs communicate over multiple episodes, ensuring that every pair $(s,a)$ is visited infinitely often. 
Since the state space is finite, this implies:

\begin{equation}
    \lim_{n \rightarrow \infty} n_{s,a} = \infty\text{.}
\end{equation}

This result implies that for any state-action pair $(s,a)$, there exists parameter $n$ such that $n_{s,a}$ exceeds any finite number $k$ as $n \rightarrow \infty$.
Given that $n_{s,a}$ becomes arbitrarily large as $n \rightarrow \infty$, the $k$ nearest neighbors become increasingly close to $(s,a)$ itself.
This means that as $n_{s,a}$ grows, the difference in distance between $(s,a)$ and its $k$ nearest neighbors diminishes.
Thus, we have:

\begin{equation}
    \lim_{n \rightarrow \infty}{r_t^i} = 0\text{,}
\end{equation}

which formalizes the idea that the intrinsic reward decreases to zero as most of the state-action space is visited extensively.

Finally, we conducted additional experiments in which we progressively increased the number of training steps for SI2E across various tasks in the MiniGrid environment. 
During this process, we observed that SI2E's final performance consistently stabilized at a fixed value as the number of training steps increased. 
This empirical finding indirectly supports the asymptotic consistency of our method, as it demonstrates that SI2E converges to a stable solution over time, independent of the specific task.
Thank you for your insightful questions. 
To clarify, the numbers presented in the tables represent the final test-time rewards obtained after the convergence of the algorithms. 
We understand that demonstrating sample efficiency is crucial, especially in the context of effective exploration, which is the focus of our work.

Due to the limitations of markdown formatting, the above provided table focused on presenting the final rewards after convergence. 
To address your concerns and provide a more comprehensive view of our results, we have displayed the number of steps required to achieve the target rewards as an indicator of sample efficiency.

|MiniGrid|RedBlueDoors-$6$x$6$|SimpleCrossingS$9$N$1$|KeyCorridorS$3$R$1$|DoorKey-$6$x$6$|DoorKey-$8$x$8$|Unlock|
|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|
|Leco|$817.47 \pm 137.21$|$417.59 \pm 17.63$|$520.43 \pm 10.31$|$571.31 \pm 31.27$|$2168.35 \pm 293.52$|$791.40 \pm 82.39$|
|SI2E|$461.90 \pm 61.53$|$139.17 \pm 27.03$|$129.06 \pm 6.11$|$230.60 \pm 19.85$|$1090.96 \pm 125.77$|$309.14 \pm 53.71$|

We hope that this additional data resolves any uncertainties and provides a clearer picture of the exploration effectiveness and efficiency of our proposed approach.
I've read the detailed rebuttal and appreciate the authors' efforts in addressing my questions and adding the state density heatmap. The clarification on "Generation of Optimal Encoding Trees" is helpful, and I encourage the authors to highlight the differences in generating the encoding trees for $G_{xy}$ in sec.3 and $G_{sa}$ in sec. 4 in the revised paper. Additionally, while the annotation of Figure 1 is now clearer, I suggest making the legend in Figure 1 more straightforward based on your clarification.

I also recommend integrating the provided clarifications into the main paper, particularly when writing the following points: 
- Q1.2: Explanation About Graph Vertices
- Q1.3: Single-variable Constraint of Structural Information
- Q2.2: Structural Mutual Information Principle
- Q2.4: Sub-communities Explanation
  
  Given that the majority of clarity questions have been addressed, I'll raise my rating.
> In the latest version of our paper, we have added a new appendix section to provide a comprehensive and rigorous validation of SI2E's asymptotic properties.

I'm sorry but as far as I remember you are not allowed to submit a new version of the paper during rebuttal. How did you do that? I can't find the section from my end as well.

> ... These results demonstrate that our method consistently maintains a performance advantage, even when benchmarked against advanced episodic intrinsic reward mechanisms like Leco.

What do the numbers in the tables mean? Are they the final test-time rewards after convergence? As this paper is about effective exploration can the authors show the sample efficiency?
In the latest version of our paper, we have added a new appendix section to provide a comprehensive and rigorous validation of SI2E's asymptotic properties.

We begin by analyzing the asymptotic mean and consistency of the $k$-NN estimator for the lower bound of the value-conditional structural entropy. 
In the work by Singh et al. (2003), the asymptotic consistency of the $k$-NN entropy estimator was established.
Specifically, for the entropy terms $H(V_0)$ and $H(V_1)$ in Equation 12, the following relationships hold:
\begin{equation}
    \lim_{n \rightarrow \infty}{\mathbb{E}(\widehat{H}_{KL}(V_0))}=H(V_0)\text{,}
\end{equation}

\begin{equation}
   \lim_{n \rightarrow \infty}{\operatorname{Var}(\widehat{H}_{KL}(V_0))} = 0\text{,}
\end{equation}

\begin{equation}
    \lim_{n \rightarrow \infty}{\mathbb{E}(\widehat{H}_{KL}(V_1))}=H(V_1)\text{,}
\end{equation}

\begin{equation}
   \lim_{n \rightarrow \infty}{\operatorname{Var}(\widehat{H}_{KL}(V_1))} = 0\text{.}
\end{equation}

This implies that the $k$-NN entropy estimators discussed are both asymptotically unbiased and consistent. 
Therefore, the asymptotic mean of the estimator difference is $0$, which confirms its asymptotic unbiasedness. 
Within the context of a $2$-layer encoding tree $T^*_{sa}$, the set $V_1$ represents sub-communities corresponding to all state-action pairs in $V_0$, leading to a linear dependence between their visitation probabilities. 
The covariance between estimators is expressed as $c \cdot \operatorname{Var}(\widehat{H}_{KL}(V_0))$, where $c$ is a constant parameter. 
By examining the variance of the difference between the $k$-NN estimators, we calculate this difference variance as $0$, thereby demonstrating the consistency of the estimators.

Subsequently, we explore the asymptotic behavior of our intrinsic reward. 
Let $n_{s,a}$ denote the visitation count for a state-action pair $(s,a)$ within a finite state-action space. 
Given the episodic nature of MDPs, it is assumed that all state-action pairs communicate over multiple episodes, ensuring that every pair $(s,a)$ is visited infinitely often.
Since the state space is finite, this implies:

\begin{equation}
    \lim_{n \rightarrow \infty} n_{s,a} = \infty\text{.}
\end{equation}

This result implies that for any state-action pair $(s,a)$, there exists a parameter $n$ such that $n_{s,a}$ exceeds any finite number $k$ as $n \rightarrow \infty$. 
As $n_{s,a}$ becomes arbitrarily large, the $k$ nearest neighbors become increasingly close to $(s,a)$ itself. 
This indicates that as $n_{s,a}$ grows, the difference in distance between $(s,a)$ and its $k$ nearest neighbors diminishes.
Thus, we have:

\begin{equation}
    \lim_{n \rightarrow \infty}{r_t^i} = 0\text{,}
\end{equation}

which formalizes the idea that the intrinsic reward decreases to zero as most of the state-action space is visited extensively.

Finally, we conducted additional experiments in which we progressively increased the number of training steps for the SI2E method across various tasks in the MiniGrid environment. During this process, we observed that SI2E's final performance consistently stabilized at a fixed value as the number of training steps increased. This empirical finding indirectly supports the asymptotic consistency of our method, as it demonstrates that SI2E converges to a stable solution over time, independent of the specific task within MiniGrid.

In summary, we have demonstrated the asymptotic consistency of our method through both theoretical derivation and empirical validation. Due to constraints in the current environment, some detailed derivation steps could not be fully presented, leading to the omission of certain intricate details. We trust that the explanations provided above address your concerns and offer sufficient clarity regarding the robustness of our approach.
We have revised the claim in lines 78-80 of the paper to ensure accuracy and to avoid any potential overstatement. 
The claim now specifically highlights that SI2E significantly enhances performance within the context of "information-theoretic exploration," thereby more accurately reflecting the scope of our contribution in this domain.

To further substantiate our results and address concerns regarding the comparison on the Minigrid environment, we have introduced Leco (NeurIPS 2022), a state-of-the-art baseline that represents an advanced episodic intrinsic reward mechanism. 
These results demonstrate that our method consistently maintains a performance advantage, even when benchmarked against advanced episodic intrinsic reward mechanisms like Leco.

|MiniGrid|RedBlueDoors-$6$x$6$|SimpleCrossingS$9$N$1$|KeyCorridorS$3$R$1$|DoorKey-$6$x$6$|DoorKey-$8$x$8$|Unlock|
|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|
|Leco|$81.97 \pm 10.81$|$90.02 \pm 4.13$|$90.36 \pm 0.57$|$94.37 \pm 3.41$|$92.07 \pm 19.11$|$94.48 \pm 6.39$|
|SI2E|$85.80 \pm 1.48$|$93.64 \pm 1.63$|$94.20 \pm 0.42$|$97.04 \pm 1.52$|$98.58 \pm 3.11$|$97.13 \pm 3.35$|
I appreciate the rebuttal from the authors. I have read the rebuttal and the global rebuttal and determine to keep my score.
> To address your concern, we have incorporated the DRM model (ICLR 2024) as an additional baseline. … we introduced the MADE baseline in the MiniGrid environment for a more comprehensive comparison.

Thank you for providing the additional experiments. However I was asking for minigrid and I don’t think MADE is the sota method on minigrid as it performs worse than many more recent intrinsic rewards, such as the episodic intrinsic reward methods. I think the authors should just change the claim in the paper, avoiding to claim this is sota performance.

> We have thoroughly investigated the asymptotic properties of our proposed method, SI2E, and confirmed its asymptotic consistency. 

How and where did you do this?
$\bullet$ Q6: Other Questions.
Considering the impracticality of directly acquiring visitation probabilities, we employ the k-NN entropy estimator in Equation 1 to estimate the lower bound of our value-conditional structural entropy.

The term 'their' in 'due to their instability' refers to traditional maximum entropy exploration methods. 
Lines 38-41 aim to emphasize the performance instability of these traditional methods and highlight the importance of dynamic-relevant state-action representations.

The entropy reduction $\Delta H$ caused by one stretch operation in Appendix A.2 is provided in 'Generation of Optimal Encoding Trees' section of the Author Rebuttal.
$\bullet$ Q2.1 and Q3: Step \uppercase\expandafter{\romannumeral2} in Figure 2.
For the graph $G_{sa}$, which contains only a single state-action representation variable, we do not use the $2$-layer approximate binary tree constraint from SMI.
Instead, we traverse all encoding trees that satisfy the height constraint to find the optimal encoding tree.
Therefore, the nodes in $T_{sa}^*$ can have more than two children.

In our work, the input variables are value sets obtained from samples in the replay buffer. 
Thus, the number of state-action pairs in the representation variable $Z_t$ equals the batch size, denoted by $n$.
Appendix D and Appendix E. 5 provide the settings and sensitivity analysis for $n$ in different tasks.

In continuous state-action spaces, traversing all possible variable values and optimizing the joint distribution probabilities is infeasible. 
Therefore, we derived the variational upper and lower bounds of structural mutual information and set corresponding decoders to optimize it indirectly.

The 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. 
However, it does not capture the current coverage of the state-action space by the agent's exploration. 
Therefore, we additionally construct the state-action distribution graph to define value-conditional structural entropy and propose an intrinsic reward mechanism.

$\bullet$ Q2.2: Structural Mutual Information Principle.
For the state-action representation variable $Z_t$, we maximize its SMI with the subsequent state variable $S_{t+1}$.
This process establishes a near one-to-one correspondence between $Z_t$ and $S_{t+1}$, effectively enabling $Z_t$ to accurately predict environmental dynamical transitions.
By ensuring that $Z_t$ contains sufficient information about the future state $S_{t+1}$, we can derive a representation that inherently captures the dynamics of the environment.

Conversely, we minimize the SMI between $Z_t$ and the current state variable $S_t$.
This minimization ensures that $Z_t$ and $S_t$ are mutually independent, effectively stripping $Z_t$ of any information irrelevant to state transitions.
Furthermore, we constrain the joint entropy $H(Z_t,S_t)$ to eliminate as much redundant information as possible from $Z_t$.
Consequently, this process refines $Z_t$ to a dynamics-relevant state-action representation by filtering out extraneous data that does not contribute to predicting future states.

By defining value-conditional structural entropy and intrinsic rewards based on this refined representation, we enhance the agent's ability to explore the environment effectively. 
The ablation studies comparing SI2E and its variant SI2E-DB demonstrate the critical role of this approach in improving exploration. 
These studies show that agents utilizing our proposed dynamics-relevant state-action representation achieve superior exploration performance, as they are better equipped to understand and predict environmental transitions.

$\bullet$ Q2.4: Sub-communities Explanation.
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.
The set of all sub-communities is labeled as $V_1$.

The term $-H(V_1)$ is introduced in the intrinsic reward mechanism to address the issue of uniform exploration across all sub-communities.
Without this term, the agent might uniformly explore all sub-communities, including those with very low policy values, which leads to imbalanced exploration.
By incorporating $-H(V_1)$ we penalize uniform coverage and bias the agent towards exploring sub-communities with higher policy values. 
This approach ensures that the agent focuses its exploration on more promising areas of the state-action space, enhancing the efficiency and effectiveness of the agent's exploration strategy.

$\bullet$ Q5: Experiments.
The visualization of state coverage in the continuous Cartpole Balance task is provided in Figure 3 of the Author Rebuttal PDF.

In the MiniGrid and MetaWorld tasks, we chose not to 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.
$\bullet$ W3.1: Subset of Graph Vertices.
For any tree node $\alpha$ in the encoding tree, we have changed the symbol representing the corresponding subset of graph vertices to $\mathcal{V}_\alpha$ with $\mathcal{V}_\alpha \subset V$.

$\bullet$ W3.2 and Q2.3: $2$-layer Approximate Binary Tree And $l$-transformation.
Please refer to the '$2$-layer Approximate Binary Tree and $l$-transformation' in the Author Rebuttal.

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, which can be prohibitive for practical applications.
We acknowledge that this choice might introduce certain limitations; however, our primary goal was to establish a foundational framework that can be expanded in future work.

To define structural mutual information (SMI) accurately, it is essential to define the joint entropy of two variables under various partition structures. 
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. 

In summary, our approach introduces a $2$-layer Approximate Binary Tree as an initial partition structure and utilizes $l$-transformation to explore all possible one-to-one matching.
We recognize the potential for further exploration of alternative structures for defining SMI and intend to pursue this in future research.

$\bullet$ W3.3: Generation of Optimal Encoding Tree.
Please refer to the 'Generation of Optimal Encoding Trees' section in the Author Rebuttal.

$\bullet$ W4: Related Work.
Please refer to the 'Related Work' section in the Author Rebuttal.

$\bullet$ W5: Minor Points.
We have carefully addressed each point in our latest revision.

$\bullet$ Q1.2: Explanation About Graph Vertices.
In our work, we primarily deal with three types of graphs: undirected bipartite graph, complete state-action graph, and directed distribution graph.

1) Undirected Bipartite Graph.
This 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. 
Each vertex corresponds to a possible value of these variables. 
The weighted edges between these vertices represent the joint distribution between two variables and are used to define structural mutual information.

2) Complete State-Action Graph and Directed Distribution Graph.
These graphs contain only a single state-action representation variable, $Z_t$. 
The vertices in these graphs represent the Q-value relationships and access probabilities between state-action pairs under a given agent policy. 
These graphs are employed for hierarchical state-action structure analysis and for defining value-conditional structural entropy, which ultimately aids in constructing the intrinsic reward mechanism.

$\bullet$ Q1.3: Single-variable Constraint of Structural Information.
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 a single-variable constraint. Prior research on reinforcement learning using structural information principles has focused on independently modeling state or action variables without simultaneously considering state-action representations.

Therefore, in our work, we introduce structural mutual information (SMI) to measure structural similarity between two distinct variables for the first time. This innovation allows us to use SMI as the objective for state-action representation learning, thereby bridging the gap left by previous studies.
Owing to space and word count limitations, we were unable to address each of your concerns in detail within the rebuttal section. 
Therefore, we would like to take this opportunity to provide additional details on some of the key issues here, with the intention of addressing your queries comprehensively. If the above rebuttal has successfully addressed all your questions, you can skip the subsequent content.

$\bullet$ W1.1: Connection Between Intrinsic Rewards and Entropy Maximization.
The maximum entropy exploration methods maximize the state or action entropy as intrinsic rewards, ensuring comprehensive coverage across the state-action space.
A prevalent issue with entropy maximization strategies is their tendency to bias exploration toward low-value states. 
This bias can result in inefficient exploration and vulnerability to imbalanced state-value distributions, particularly in settings where certain states are inherently more valuable.
To address this issue, value-conditional state entropy is introduced. 
This method computes intrinsic rewards based on the estimated values of visited states, ensuring exploration is directed toward diverse and valuable states.

$\bullet$ W1.2: Stretch Operator.
Please refer to the 'Generation of Optimal Encoding Trees' section in the Author Rebuttal.

$\bullet$ W1.3: Claim Evidence.
We have incorporated citations to provide theoretical support for these claims made in lines 35-36 and 200-201.

$\bullet$ W2.1, Q1.1, and Q4: Details and Intuition of Figure 1.
Please refer to the 'Intuition Behind Figure 1' section in the Author Rebuttal.

Figure 1 illustrates a 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, 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$ W2.2: Illustration of Figure 2.
We have made several adjustments to enhance its clarity and readability, including layout adjustment, clarified caption, color scheme specification, and spacing adjustment.

1) Layout Adjustment. 
We have restructured the layout of Figure 2 to reduce clutter and improve the flow of information. 
The annotations have been reorganized to follow a more logical sequence, with vertical and horizontal annotations clearly distinguished and aligned to avoid overlapping.

2) Clarified Caption. 
The caption of Figure 2 has been expanded to be more self-contained and informative. 
It now provides a comprehensive explanation of the figure's components and their significance in the context of our study. 
Specifically, we describe how square and diamond shapes represent state representations and state-action representations, respectively. 
Circles enclosing squares or diamonds indicate tree nodes containing different types of graph vertices.

3) Color Scheme Specification. 
We have specified the color scheme used in the figure to differentiate between nodes and vertices in the two steps.
Specifically, we use distinct colors for different variables: $O_t$ with dark grey, $O_{t+1}$ with light grey, $S_t$ with green, $S_{t+1}$ with orange, and $Z_t$ with blue.

4) Spacing Adjustment. 
We have ensured adequate spacing between Figure 2 and the surrounding text, particularly between the figure and line 158, to improve the overall presentation and readability of the manuscript.