acceptodds
Under review as a conference paper at ICLR 2027

Discovering Hierarchical Opponent Strategies via Structural Entropy Minimization in Imperfect-Information Games

Abstract

In imperfect-information games, an opponent behaves at more than one level, from immediate reactions to strategies that persist over time, but these levels are hidden and the active strategy can change at any time. Most opponent models compress the interaction history into one flat latent state, while methods that use hierarchy require it to be specified in advance or rely on a large language model. We present Structural Entropy-based Opponent Modeling (SEOM), which builds an online interaction graph, finds a minimum-code-length encoding tree by structural entropy minimization, and selects the tree depth from the data. A context-conditional detector compares action distributions within decision contexts, so it responds to genuine strategy changes and stays silent as the learner’s own visits shift; a structural compression ratio, computed before training, indicates whether hierarchy will help. On a benchmark of opponents with planted hierarchies, SEOM recovers every planted depth and partition, with level agreement approaching one as the stream grows, and turns this recovery into gains over flat and structured baselines in return, log-loss, sample efficiency, and post-switch adaptation. The detector identifies genuine switches while suppressing false alarms under learner drift, and the compression ratio chooses between hierarchical and flat modeling with no cross-validation errors.

Primary area:
reinforcement learning
Keywords:
Imperfect-Information Games, Opponent Modeling, Structural-Entropy, Multi-agent Learning

Reviews

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

This paper addresses opponent modeling in imperfect-information games. It tries to find the most likely hierarchical structure of the opponent. It starts by constructing a reduced graph of the opponent's transitions, then tries to find a tree of a given depth that best fits the structure the opponent might have used, with respect to the structural entropy. This additional hierarchical information is then used as input to the actor-critic to improve the training against that specific opponent.

Critical strengths

The main idea of modeling the opponent using a learned hierarchical structure is an intriguing line of research, and I believe it is a good approach for modeling human players.

Critical weaknesses

In line 199, you state: "a standard constructive heuristic" without any reference. It is not clear whether the description that follows is the exact construction taken off-the-shelf or is proposed by the authors as a contribution. I think the description of this construction in Section 4.2 is weak, and a simple example would greatly benefit it. Several of my concerns about this description: Is the tree constructed from the game tree or from the graph constructed in 4.1? If it uses the graph from 4.1, then it is not clear how this general graph is transformed into a tree, as the authors only state, "On read we symmetrize and remove self-loops," but it is not clear how they do it, or even why that would be a good idea. Also, it is not clear to me what the "degenerate two-level tree of entropy H1H^1" looks like, and whether the algorithm uses this H1H^1 tree only for comparison or modifies it to find deeper trees. Some of these concerns are addressed by pseudocode Algorithm 1, but these should still be explained in the main text.

The paper includes some unnecessary details that are not explained, particularly in Sections 4.3 and 4.5. For example, the exact network sizes used, which are not relevant to the method, or the hyperparameter settings such as 24 context prototypes, τatt=0.5\tau_{att} = 0.5, and η=0.25\eta = 0.25. I am not saying those details are not important, but if there is no specific theoretical reason why those were (and should be) selected, then they should appear in a hyperparameter section and in the method description, since it is more about hyperparameter tuning than about explaining the method. Ideally, an ablation study could show the effect of changing those hyperparameters, but I do not think it is necessary.

The description of Figure 2 does not seem to correspond fully to the figure itself, as it is not clear what (a), (b), (c), and (d) should correspond to in the figure itself.

The authors use the regime-level adjusted Rand index as their main comparison metric, without formally defining it (they rely only on its informal implications).

It is not clear whether the baselines the authors are using in their experiment are their own, or whether they have been used in prior work. Without these details, it is hard to assess the strength of their approach.

The authors train the Actor-critic, but it does not seem that they evaluate it in any experiment. My understanding is that the goal is both to learn the model and to learn how to play well against it with the actor, but this is not evaluated anywhere. If the actor serves only to guide the opponent's exploration, the authors should state this explicitly.

(minor) Based on the description, it seems the paper is for two-player games only, because line 159 defines a^op_t as the action of a single opponent rather than a collection. If that is true, the authors should state explicitly that they are considering only those games.

(minor) τi\tau_i is not defined in Preliminaries, but I assume it is a sequence of actions and observations of the agent ii.

(minor) I think the NashOpponent in Leduc, in the implementation, is not actually Nash. I did not find any other obvious mistakes. This mistake is not relevant to the paper, as the authors do not use it for any evaluation, so it is not a problem, but it makes me skeptical about other claims in the paper.

Questions for authors
  1. You define o_t as the opponent's observation at line 159. Then, in Section 4.1, you work with this concept. Does this mean that the algorithm is aware of the opponent's observation? Is it only during a pretraining phase, when you are not actually playing against the opponent? Otherwise, I do not understand how you get this information.

  2. The opponent interaction graph construction uses cosine similarity between two observations. Does the environment define the observations, or are the observations somewhat learned in latent space? Because if they are defined, then the whole merging depends on how the author defined the observations. So the quality of the merging would directly correspond to the quality of the observation definition.

  3. In Section 4.2, are you constructing the tree H from the graph you construct in Section 4.1? If so, how do you then remove the cycles from that graph?

1 comment
AuthorsOpenReview ↗

Response: graph-to-tree construction, observations, and actor–critic evaluation

We thank the reviewer for the detailed questions. Several arise because our notation obscures what the learner observes and because the method section mixes principles with implementation constants.

1. Observation. In the revision we will replace oto_t by an explicitly learner-side decision context, specify its components for each environment, and give a concrete record →\rightarrow prototype →\rightarrow edge example.

The observations used for prototype merging are environment-provided feature vectors, not learned latent observations. Cosine merging therefore depends on their scaling and representation.

2. From graph to tree. The encoding tree is built from the interaction graph of Section 4.1, not from the game tree. Cycles in the interaction graph are not removed. Instead, an encoding tree is a nested partition of graph vertices: initially the root contains all vertices and every vertex is a singleton leaf. Bottom-up merges introduce internal nodes grouping vertices; the graph and its cycles remain unchanged.

At each step we choose a same-height merge that most decreases the structural-entropy objective. Thus the initial two-level tree is modified to produce deeper candidate trees; it is not merely a comparison baseline. Reading a directed interaction graph uses W=(A+A⊤)/2W=(A+A^\top)/2 and removes diagonal entries to obtain a well-defined undirected cut volume. This discards direction, which we will state as a limitation. We will cite the constructive heuristic and clarify that our contribution is its opponent-model instantiation and online maintenance. A worked example with a handful of vertices and one merge will be added.

3. Evaluation and baselines. The actor–critic is evaluated, not used only to guide exploration. Figure 11(a,b) reports stationary and switching returns of the learned actor; Section 5.3 additionally reports sample efficiency, success, transfer, and adaptation, while Figure 11(c) separately evaluates opponent-action log-loss. We will move the return comparison into the main text and state this distinction explicitly.

All learned baselines use our implementations under the same PPO trunk and optimization budget: PPO has no opponent encoder; DRQN is recurrent; MBOM and UAOM follow their published opponent-model constructions; SOM-adapted is our learned-constructor adaptation of Cao et al. (2026), not the original LLM-based system. We will label this clearly to avoid overstating it as the original baseline.

4. Presentation and scope. We will move architecture sizes and numerical hyperparameters to Appendix C; retain only the method-defining symbols in Section 4; fix Figure 2’s panel/caption mismatch; and define the level-wise ARI as ARI=RI−E[RI]max⁡(RI)−E[RI],\mathrm{ARI}=\frac{\mathrm{RI}-\mathbb E[\mathrm{RI}]}{\max(\mathrm{RI})-\mathbb E[\mathrm{RI}]}, computed independently at each tree level against the corresponding planted partition. The depth-selection lift/cutoff will also be written explicitly.

The current formulation is single-opponent. We will state this scope explicitly. The undefined history symbol will be defined in Preliminaries. Finally, we will inspect and correct/remove the unused NashOpponent implementation and avoid calling any opponent “Nash” without an equilibrium computation. Thank you.

Reviewer_WyqJOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper suggests that if structural hierarchies exist within adversarial players, that a learner could learn this structure to better model their opponents and improve their payoffs. The work targets POSGs; the structure is learned from local interactions of observations/actions/beliefs.

Critical strengths

The paper is clearly motivated, with an overview of work on in different areas of opponent modeling. The approach appears to work, with the modeling improving over baselines, and tests to see if the hierarchal modeling is expected to work in practice.

The problem of learning against opponents with non-stationary strategies is both interesting and difficult. The paper makes headway by making assumptions about the structure of opponents.

Critical weaknesses

Taken as a whole, the paper shows that if you insert hierarchy into the domain, a learner can learn that and exploit it. But no evidence is shown that this happens in any real domain or in practice. Thus, at the highest level the paper looks to be solving a problem that won’t have application outside of this paper.

The paper does not go into detail in any of the domains used of how the planted tree is actually used. From the description in section 5.1 I would not be able to duplicate this procedure in practice. The paper would be strengthened if it were to provide an example in the appendix of how this is done in practice.

The paper has a large number of parameters that are not well justified. For instance, Section 4.1 has a cosine similarity limit of 0.8, a prototype limit of 500 (language is unclear), unit edge weights on opponent actions, but 0.5 weights on public belief representations. There is a decay of 0.95 and edge pruning below 10^-4. It is very difficult to know if these parameters are tuned or if they have been tested with parameter sweeps, (These change slightly in section 4.5 as well.)

Questions for authors
  1. Are there practical contexts (eg without planted trees) where this approach would apply?

  2. Can you provide more details about the planted trees? How do they interact with Nash equilibria in games like Leduc Hold’em? Is the resulting player far outside Nash as a result?

  3. How are parameters determined?

1 comment
AuthorsOpenReview ↗

Response: applicability beyond planted trees, reproducibility, and hyperparameters

We appreciate the reviewer’s central concern: our experiments establish that SEOM can exploit a hierarchy when one is planted, not that such hierarchies arise naturally in unrestricted play. We agree that the current manuscript does not sufficiently separate these claims.

1. Applicability beyond planted trees. SEOM does not require a game tree or an equilibrium hierarchy; it requires repeated context–action co-occurrence whose conditional response patterns admit nested regularities. Plausible sources are recurring skill/tactic modes in human play, curricula or checkpoints producing families of related policies, and opponents that reuse a low-dimensional strategy library.

2. What the planted opponent is, and its relation to Nash. The planted tree is over decision contexts, not the Leduc game tree. Each leaf is assigned a categorical action distribution; a latent regime activates a subtree and changes on a recorded schedule. Context clusters determine which situations share response structure; the tree does not represent betting sequences or an equilibrium decomposition.

Accordingly, these opponents are behavioral, non-stationary test opponents, not claimed to be Nash or near-Nash. Their purpose is to provide known recovery ground truth and controlled switch times. The revision will include a small Leduc-specific example mapping public/private information to context features, leaf response distributions, active subtrees, and transitions, plus the generator configuration.

3. Hyperparameters and validation. The values were fixed before the main study rather than selected through a large sweep; except for the height cap, they were not retuned per domain. We agree that this is not a justification by itself. The revision will move numerical settings out of the method exposition and provide (i) their roles, (ii) selection provenance, and (iii) sensitivity analyses for the prototype similarity/cap, EMA decay, belief-edge weight, pruning threshold, detector window/threshold, and depth cutoff.

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

SEOM builds an online interaction graph, discovers an encoding tree through greedy structural-entropy minimization, and uses hierarchical representations for opponent prediction and PPO. A context-conditional change detector triggers tree reconstruction, while a compression statistic is proposed to predict whether hierarchy will help. Experiments use generated opponents with planted hierarchies and four domain instantiations, reporting hierarchy recovery, improved returns and prediction, switch detection, and model-family selection.

Critical strengths
  1. Comparing conditional action distributions is preferable to interpreting every change in marginal actions as an opponent switch. Proposition 3 gives a useful asymptotic argument under its fixed-conditional-law assumption.

  2. Planted hierarchies, flat and shuffled nulls, and oracle/random/tree-shuffling interventions are appropriate ways to test whether the discovered structure contributes to performance rather than merely adding model capacity. This is a stronger experimental design than reporting returns alone.

Critical weaknesses
  1. Equation (3) weights a node’s code length by g_parent V_child / (vol(G) V_parent), whereas standard structural entropy uses g_child / vol(G). These quantities are generally different: stationary mass within a parent does not determine the distribution of boundary-entry destinations, and transitions between siblings also enter a child. Appendix B.2 therefore does not establish the claimed random-walk coding interpretation. Separately, Proposition 4 does not justify the implemented false-alarm threshold. With n_min = 6, its stated expectation bound is at least sqrt(1/12) ≈ 0.289 for any action space with at least two actions, already above η = 0.25. The argument also assumes a converged reference distribution rather than the finite reference samples used in practice, and does not provide an error probability for repeated online tests.

  2. Appendix A describes a generated reward stream rescaled to domain-specific units, but does not make clear whether the reported returns result from interactive play in the stated games or from the planted generator. This distinction matters for the claimed applicability to imperfect-information games. Several key results are also inconsistent: Section 5.5 describes leave-one-configuration-out validation as holding out an entire domain; Figure 13 reports conditional-detector AUC-PR of 0.97, whereas Table 4 and the main text report 0.84.

Questions for authors
  1. Which entropy expression is actually optimized? After correcting the coding interpretation, do hierarchy recovery and compression-based model selection remain unchanged?
  2. What false-alarm probability is guaranteed for the implemented window, finite reference, and threshold? Please distinguish an asymptotic conditional-law argument from finite-sample, sequential error control.
  3. Are returns generated by actual environment transitions and learner actions? Please specify the learner-visible information, the graph construction from that information, the exact validation folds and depth cutoff, and reconcile the reported inconsistencies in detection and depth recovery.
1 comment
AuthorsOpenReview ↗

Response: entropy correction, detector guarantees, and evaluation

We thank the reviewer for identifying the entropy-expression error and the gap between Proposition 4 and our implementation. We agree that the current wording overstates what is established.

1. Entropy expression. The standard expression is HT(G)=−∑α≠λgαvol(G)VαVα−log⁡2VαVα−,H^T(G)=-\sum_{\alpha\neq\lambda}\frac{g_\alpha}{\mathrm{vol}(G)}\frac{\mathcal V_\alpha}{\mathcal V_{\alpha^-}}\log_2\frac{\mathcal V_\alpha}{\mathcal V_{\alpha^-}}, not the parent-cut weighting printed in Eq. (3). Our coding argument in Appendix B.2 confuses the rate of entering the parent with the destination-conditional rate of entering a child, and is therefore invalid as written. We will correct the objective and proof and explicitly distinguish the exact optimum HKH^K from our greedy upper bound HT⋆H^{T^\star}.

2. Detector guarantee. We agree that Proposition 4 does not justify η=0.25\eta=0.25 at nmin⁡=6n_{\min}=6: its expectation bound is at least 1/12≈0.289\sqrt{1/12}\approx0.289 when k≥2k\ge2. It also assumes a converged reference and does not control repeated tests. We will rename Proposition 4 as a fixed-time fluctuation result, remove the claimed guarantee for the implemented threshold, and retain Proposition 3 only as the asymptotic visit-invariance argument.

For finite references, a valid per-context analysis must bound both errors: with window and reference counts nc,mcn_c,m_c, Pr⁡{TV(qc,rc)≥ε+ε′}≤(2k−2)(e−2ncε2+e−2mcε′2),\Pr\{\mathrm{TV}(q_c,r_c)\ge\varepsilon+\varepsilon'\}\le (2^k-2)(e^{-2n_c\varepsilon^2}+e^{-2m_c\varepsilon'^2}), under independent multinomial sampling. Repeated votes require an additional time/union correction (and an effective-sample-size correction under dependence). We will either state such a bound for the implemented rule, with η\eta chosen accordingly, or present the detector as heuristic with empirical false-alarm rates—whichever the corrected analysis supports.

3. Evaluation and inconsistencies. We will explicitly separate (i) results generated by the planted model and (ii) any results from environment rollouts with learner actions, and revise applicability claims accordingly. For every reported return, the revision will identify the transition and reward source.

We will also add a graph-vertex/edge example. The graph will be described only in terms of information actually available to the learner and the appendix will include the construction pseudocode. Thank you again.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.