Partially Observable Markov Decision Process Modelling for Assessing Hierarchies

Guangyuan Piao; Neil J. Hurley; Raul Moreno; Weipeng Huang

REVIEW 1 major objections 5 minor 26 references

Partially Observable Markov Decision Process Modelling for Assessing Hierarchies

T0 review · 1 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A search-bot's expected reward, modeled as a POMDP, scores how well a hierarchy supports finding items, with no ground-truth labels needed.

desk verdict The POMDP extension is coherent and the stress-test's squared-η concern does not hold up, but HQS rests on an unvalidated equivalence between the bot's beliefs and the true dynamics. read the letter →

arxiv 1908.07031 v7 pith:W6HQ3PU3 submitted 2019-08-19 stat.ML cs.AIcs.LGstat.AP

Weipeng Huang , Guangyuan Piao , Raul Moreno , Neil J. Hurley This is my paper · ORCID

classification stat.MLcs.AIcs.LGstat.AP

keywords hierarchicalclusteringevaluationPOMDPbeliefstatessearchefficiencyhierarchyqualityground-truth-freeguidancefunctiononlineplanning

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper sets out to measure the quality of a hierarchical clustering arrangement by the efficiency with which a searcher can find items in it, without using any ground-truth labels. It defines Hierarchy Quality for Search (HQS) as the average, over all target items, of the long-run expected reward a stochastic search bot collects while navigating the hierarchy. The bot's uncertainty, decisions, and the cognitive payoff of stopping at a small cluster are modeled as a Partially Observable Markov Decision Process (POMDP), with branch choices driven by how similar each child cluster is to the target. The authors argue that this score needs no ground-truth hierarchy; in their case study it places a ground-truth hierarchy top and a deliberately poor hierarchy bottom.

What carries the argument

The load-bearing machinery is a Partially Observable Markov Decision Process (POMDP)---a decision model for an agent that never observes the true state and acts on a probability distribution over states---together with the belief update $b_{c'}=\eta(c,c')b_c$, which collapses the full belief state to one scalar per node because the bot cannot backtrack and always observes its location. That identity makes the probability of being on the correct path the product of softmax similarities along the path. On top of it, the paper's simplified real-time belief-space search policy compares the value of stopping at the current node, $Q(b,a_s)=b_c(r(c)+1)-1$, with the one-level look-ahead estimate $\hat{Q}(b,a_d)=\sum_{c'\in C(c)}\eta(c,c')(b_{c'}(r(c')+1)-1)$, and descends only when the look-ahead is larger. HQS then averages the resulting per-item oracle values.

What would settle it

Measure human search times for the same item set in two hierarchies that HQS ranks far apart; if searchers are not consistently faster in the higher-scoring hierarchy, the claim that HQS tracks search efficiency is refuted. A cheaper computational check is to re-rank the hierarchies under several values of the temperature $\delta$; if the ordering flips within a plausible range, the score depends on an uncalibrated knob rather than on the hierarchy itself.

Watch

Extended reading notes

Core claim

The paper's central claim is that hierarchy quality for search can be reduced to a single number computed from a POMDP's oracle value: for each item $x$, the bot starts at the root with belief $b=1$ that it is on the correct path, and the probability of being on the correct path after reaching a node $c$ is $b_c=\prod_{t=1}^T\eta(c_{t-1},c_t)$, the product of guidance values along the path. The guidance function is the softmax $\eta(c,c')=\exp\{\mathrm{sim}(x,c')/\delta\}/\sum_{c''\in C(c)}\exp\{\mathrm{sim}(x,c'')/\delta\}$, so the model treats the searcher's branch choice and the searcher's belief as the same probability. The value for the target is $V_x^\pi(H)=(r(c_T)+1)\prod_{t=1}^T\eta(c_{t-1},c_t)-1$, where $r(c_T)$ rewards stopping at a small cluster on the correct path and $-1$ penalizes a wrong stop; HQS is the average of these values over all items. The discovery is that this decision-theoretic quantity orders hierarchies by search efficiency consistently with intuition in the paper's experiments, and that it can be approximated efficiently by sampling items.

Load-bearing premise

The entire score rests on assuming a searcher picks each branch with probability proportional to an exponential of an item-cluster similarity, with a temperature parameter set by the user; if real people choose branches differently, HQS measures the assumed model rather than actual search efficiency.

Editorial extensions

If this is right

HQS assigns a single number to a whole hierarchy, not just to one cut, so hierarchies with different depths and branching structures can be compared on the same scale.
Because HQS needs no ground truth, it can be used to tune hyperparameters of hierarchical clustering algorithms, a use the paper explicitly points toward.
The score has polynomial worst-case cost $O(N^3F(\mathrm{sim}))$ and logarithmic average cost, so evaluating large catalogues is practical; in the paper's scaling test, sampling 30% of items already brings the normalized L1 error below 5%.
Hierarchies that split a target's close neighbours into different branches are penalized automatically, because the relevant product of guidance values shrinks even if the item is ultimately found.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Inference: Because $\delta$ is a user-set temperature in the guidance softmax, HQS is really a family of measures indexed by how decisive searchers are assumed to be; ranking hierarchies under several $\delta$ values would show whether a top-ranked hierarchy is robust or an artifact of the chosen temperature.
Inference: The per-item values that HQS averages could be used diagnostically to locate the branches and items that drag a hierarchy's score down, turning the measure from a ranking tool into a repair guide.
Inference: The model suggests a direct behavioural test the paper does not run: if HQS genuinely tracks search efficiency, hierarchies with higher scores should produce faster human search times in a controlled user study, and the assumed softmax guidance could be measured against actual branch choices.
Inference: The guidance function could be learned from clickstream or navigation logs instead of being fixed by a similarity function, letting HQS adapt to the search behaviour of a specific population while keeping the same POMDP evaluation structure.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

Short take: this is a legitimate extension of Moreno et al.'s MDP hierarchy evaluation into POMDP territory, and the mathematics is more consistent than the stress-test note suggests. The squared η in the transition model is not an error; it follows from the model treating η as both the physical move probability and the probability that the target is in that child. The Bayes filter then correctly yields the posterior belief η b_c, and the oracle value in Section 3.2 is the right expected reward of the stochastic descent process. The RTBSS Q̂ function is also computing the correct ex ante expectation; the stress-test's 0.62 versus 0.5 example confuses the conditional reward at the correct child with the unconditional expectation over random descent. So I would not pursue that thread.

What the paper does well: it gives a clean POMDP specification, a concrete policy (RTBSS with two-step look-ahead), a closed-form oracle value, and a definition of HQS that is easy to compute. The code is available, and the scaling experiment suggests sampling works. The five-hierarchy case study at least demonstrates that HQS orders obvious cases in a sensible direction.

Soft spots, in order of importance. First, the big one: the model assumes the guidance function η is simultaneously (i) the bot's subjective posterior, (ii) the physical probability of moving to a child, and (iii) the true probability that the target lies in that child. That is a strong calibration assumption. If real searchers use different choice probabilities, HQS measures the hierarchy's support for a specific, idealized bot, not search efficiency generally. The paper hand-waves this by saying the transition is "designed", but it never discusses the gap. Second, the validation is thin: 12 items, five hand-built hierarchies, one value of δ, no sensitivity analysis for any of the four free parameters, no error bars. Third, the HAI comparison is not apples-to-apples: HAI measures agreement with a ground truth, while HQS measures search efficiency, so "outperforming" HAI on a few hand-made trees doesn't tell us much. Fourth, the complexity proof is only a sketch and the constants are unclear.

Who it's for: people working on evaluation metrics for hierarchical clustering without labels, especially in e-commerce catalogues. It's a useful tool if you buy the calibration assumption. I'd send it to a serious referee; it deserves a hearing, but the referee should push on the η assumption and demand more robust empirical support.

Referee Report

1 major / 5 minor

Summary. The paper proposes HQS (Hierarchy Quality for Search), a quantitative measure for evaluating hierarchical clusterings without ground-truth labels. The author models an item search as a Partially Observable Markov Decision Process in which a bot descends a tree stochastically according to a softmax guidance function based on item-cluster similarities, and may stop and search at any node. The quality score is the expected long-term reward of the bot's policy, specifically the oracle value in the underlying MDP when the bot uses a belief-based RTBSS policy. The paper provides a POMDP formulation, a simplified policy with polynomial complexity, a case study on 12 Amazon items under five constructed hierarchies, and a scaling experiment with sampling. The central claim is that HQS orders hierarchies by their support for efficient search without requiring ground-truth information.

Significance. If the model were internally consistent, HQS would address a genuine gap: few existing measures evaluate the structural organization of a hierarchy independently of ground truth, and the decision-theoretic framing is original. The paper is clearly written, introduces an interesting notion of an 'oracle value' for a stochastic search policy, and releases a public implementation. The scaling experiment usefully demonstrates that a sampled approximation of HQS converges quickly. However, the correctness of the measure as defined is undermined by an inconsistency between the transition model used for policy optimization and the oracle value used for scoring, so the practical contribution cannot be accepted without reworking the model.

major comments (1)

[Sec. 5.2] The scaling experiment uses a different similarity function (inverse Euclidean distance after PCA) from the case study (cosine similarity on TF-IDF), and a single automatically generated hierarchy via agglomerative clustering. The relation between the two experimental settings is not explained, and it is unclear whether the sampling approximation result generalizes to the original guidance function. The paper should clarify the experimental protocol or provide results for the same similarity on both settings.

minor comments (5)

[Sec. 3, first paragraph] The phrase 'we develop a POMPD model' contains a typo: 'POMPD' should be 'POMDP'.
[Sec. 3, value function paragraph] The sentence 'Let use denote a policy by π' should read 'Let us denote a policy by π'.
[Sec. 3, Eq. (2)] The notation sim(x,c′) is used without a formal definition for a cluster c′; the later definition in Section 5.1 is specific to the experimental similarity and should be introduced earlier or clearly referenced.
[Appendix D.2] The justification for setting δ = ⌈1/100⌉ = 0.01 based on the number of PCA dimensions is unclear; the ceiling notation is unusual for a temperature parameter, and the paper would benefit from an explanation of why δ should scale inversely with dimensionality.
[Sec. 5.1.2] The sentence 'Both HQS and HAI rank Hier-E and Hier-B as first and second, excluding the ground-truth' could be clearer; the paper should explicitly state the full ranking produced by HAI and the full ranking produced by HQS for comparison.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: HQS is a self-contained POMDP construction; the eta-squared mismatch is a correctness issue, not circularity.

full rationale

No load-bearing step in the paper reduces, by the paper's own equations or by self-citation, to its inputs. HQS is explicitly defined in Definition 1 as the average over items of the POMDP value V_pi, and V_pi is computed from an explicit transition model (Eq. 3), a Bayes belief update (Eqs. 5-7), a chosen softmax guidance function (Eq. 2), and a specified RTBSS policy (Section 4.1, Algorithm 1). The scalar output is therefore a defined function of the hierarchy and similarity function rather than a fitted parameter: delta=0.01 is a hand-set temperature, not a parameter fitted to a target quantity, so the fitted-input-called-prediction pattern does not apply. The only self-citation, Moreno et al. (2017), is invoked as the predecessor MDP prototype that the paper extends; it supplies no uniqueness theorem and is not load-bearing for the claimed derivation. The experimental validation is partly self-referential, since Hier-E is constructed so that item text similarities align with the guidance softmax, but that is a weak-test issue rather than a circular derivation. A substantive internal-consistency problem exists: Section 4.1's Q_hat(b_t,ad) = sum over c' of eta(c,c') (b_{c'}(r(c')+1)-1) with b_{c'}=eta(c,c')b_c, so the policy compares squared eta, while Section 3.2's oracle value V_x=(r(c_T)+1) times prod eta minus 1 uses unsquared eta; this can make RTBSS stop when descending would score higher. This is a modeling/calibration flaw in the claimed search-efficiency interpretation, not a case where HQS equals its inputs by construction, so it does not raise the circularity score.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

No new physical or mathematical entities are postulated; the POMDP model components (search bot, belief states, guidance function) are formal modeling constructs. The measure depends on several user-chosen functions and parameters, listed above.

free parameters (4)

Temperature δ of guidance softmax = 0.01 in both experiments
Set by hand in Section 5.1 ('we set δ = 0.01 which helps us increase the weight of the best cluster') and in D.2 (δ = ceil(1/100)); it controls how peaked η is and directly shapes every HQS value and ranking.
Depth-scaling exponent ν = not specified
Appendix B proposes δ_t = δ ν^t with ν ∈ [1,∞), but no value is given and no sensitivity is reported; if used, it changes η with depth.
RTBSS look-ahead depth d = 2
Algorithm 2 fixes maximum look-aheads to 2; HQS is the value of the resulting myopic policy, so the score depends on this policy choice.
Reward function r(c) = 1 - (e^{|c|/N} - 1)/(e - 1)
The reward for stopping at a correct node is chosen arbitrarily to decrease with cluster size; the authors state it can be customized, so it is a free modeling choice.

assumptions (4)

domain assumption The target item is certainly contained in the hierarchy and the bot starts at root with correct state (c0,1).
Section 3: 'Throughout our analysis, we assume that the target x is certainly contained inside the hierarchy and hence, the bot always starts in state ⟨c0,1⟩.' This rules out failed searches from outside the catalog.
domain assumption The bot cannot backtrack once it descends.
Section 3: 'The bot cannot backtrack, once a descent step has been performed.' This makes each node reachable by exactly one path and lets belief be summarized by a single product.
ad hoc to paper Searchers choose child nodes according to the softmax guidance η, and this same η is the searcher's subjective posterior.
Eq. (2) defines η as a Boltzmann softmax over similarities; Section 3 assumes both the physical movement probabilities and the belief updates use η. HQS values are essentially products of η along the correct path, so the measure inherits all bias in this assumption.
ad hoc to paper Stopping at a correct node yields reward r(c), any wrong stop yields -1, and navigation yields 0.
The reward definition in Section 3 is a modeling choice; the relative scale of r(c) versus -1 controls how much deeper search is rewarded.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Partially Observable Markov Decision Process Modelling for Assessing Hierarchies." pith.science (2026). https://pith.science/paper/W6HQ3PU3

@misc{pith2026190807031,
  author       = {Pith},
  title        = {Pith review of: Partially Observable Markov Decision Process Modelling for Assessing Hierarchies},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/W6HQ3PU3}},
  note         = {Machine review of arXiv:1908.07031}
}

read the original abstract

Hierarchical clustering has been shown to be valuable in many scenarios. Despite its usefulness to many situations, there is no agreed methodology on how to properly evaluate the hierarchies produced from different techniques, particularly in the case where ground-truth labels are unavailable. This motivates us to propose a framework for assessing the quality of hierarchical clustering allocations which covers the case of no ground-truth information. This measurement is useful, e.g., to assess the hierarchical structures used by online retailer websites to display their product catalogues. Our framework is one of the few attempts for the hierarchy evaluation from a decision-theoretic perspective. We model the process as a bot searching stochastically for items in the hierarchy and establish a measure representing the degree to which the hierarchy supports this search. We employ Partially Observable Markov Decision Processes (POMDP) to model the uncertainty, the decision making, and the cognitive return for searchers in such a scenario.

Figures

Figures reproduced from arXiv: 1908.07031 by the authors.

**Figure 2.** Five different hierarchies Hier-A This hierarchy is generated given the ground truth labels of the items. For instance, node 4 refers to “Clothing, Shoes & Jewelry”, node 7 refers to “Women”, and 5 refers to “Shoe Care & Accessories” etc., as shown in Table S1 and S2. For item x0, “Women Boots”, staying and searching at the root earns an estimate Q(b0, as) = 0. Now, the similarities x0 with the child nodes are sim(… view at source ↗

**Figure 5.** Runtime of the sampled cases Overall, HQS can benefit from that it is completely parallelisable. In addition, sampling techniques can also help improve the efficiency. We would like to emphasise that the runtime efficiency is apparently improvable with better programming code and machines. 6 Conclusion We have proposed HQS, an approach for assessing the quality of hierarchical clusters which needs no ground-truth in… view at source ↗

Figures from the paper (1 more)

**Figure 6.** Figure 6: An AND-OR tree of reachable belief states from node [PITH_FULL_IMAGE:figures/full_fig_p019_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 25 canonical work pages

[1]

Balcan, Y

M.-F. Balcan, Y. Liang, and P. Gupta. Robust Hierarchical Clustering . The Journal of Machine Learning Research, 15 0 (1): 0 3831--3871, 2014

work page 2014
[2]

Boutilier and D

C. Boutilier and D. Poole. Computing Optimal Policies for Partially Observable Decision Processes Using Compact Representations . In AAAI, pages 1168--1175, 1996

work page 1996
[3]

A. R. Cassandra, L. P. Kaelbling, and M. L. Littman. Acting Optimally in Partially Observable Stochastic Domains . In AAAI, volume 94, pages 1023--1028, 1994

work page 1994
[4]

J. M. Cigarran, A. Pe\ n as, J. Gonzalo, and F. Verdejo. Evaluating hierarchical clustering of search results. In 12th SPIRE 2005, pages 49--54, 2005

work page 2005
[5]

W. H. Day and H. Edelsbrunner. Efficient algorithms for agglomerative hierarchical clustering methods. Journal of Classification , 1 0 (1): 0 7--24, 1984

work page 1984
[6]

M. O. Duff. Optimal Learning: Computational Procedures for Bayes-adaptive Markov Decision Processes . PhD thesis, Univ. of Massachusetts at Amherst, 2002

work page 2002
[7]

A. Fern, S. Natarajan, K. Judah, and P. Tadepalli. A Decision-Theoretic Model of Assistance . In IJCAI, pages 1879--1884, 2007

work page 2007
[8]

K. A. Heller and Z. Ghahramani. Bayesian Hierarchical Clustering . In ICML, pages 297--304, 2005

work page 2005

Show all 26 references

[9]

E. Ie, V. Jain, J. Wang, S. Narvekar, R. Agarwal, R. Wu, H.-T. Cheng, M. Lustman, V. Gatto, P. Covington, J. McFadden, T. Chandra, and C. Boutilier. Reinforcement learning for slate-based recommender systems: A tractable decomposition and practical methodology. Technical repor...

2019 arXiv
[10]

D. M. Johnson, C. Xiong, J. Gao, and J. J. Corso. Comprehensive Cross-Hierarchy Cluster Agreement Evaluation . In AAAI (Late-Breaking Developments), 2013

2013
[11]

L. P. Kaelbling, M. L. Littman, and A. R. Cassandra. Planning and Acting in Partially Observable Stochastic Domains . Artificial Intelligence, 101 0 (101): 0 99--134, 1998. ISSN 00043702

1998
[12]

Kobren, N

A. Kobren, N. Monath, A. Krishnamurthy, and A. McCallum. A Hierarchical Algorithm for Extreme Clustering . In SIGKDD, pages 255--264. ACM, 2017

2017
[13]

Y. Liu, Z. Li, H. Xiong, X. Gao, J. Wu, and S. Wu. Understanding and Enhancement of Internal Clustering Validation Measures . IEEE Transactions on Cybernetics, 43 0 (3): 0 982--994, 2013. ISSN 2168-2267

2013
[14]

McAuley, C

J. McAuley, C. Targett, Q. Shi, and A. Van Den Hengel. Image-based Recommendations on Styles and Substitutes . In SIGIR , pages 43--52. ACM, 2015

2015
[15]

Meuleau, K.-E

N. Meuleau, K.-E. Kim, L. P. Kaelbling, and A. R. Cassandra. Solving POMDPs by Searching the Space of Finite Policies . In UAI , pages 417--426, 1999

1999
[16]

Moreno, W

R. Moreno, W. Hu \'a ng, A. Younus, M. O'Mahony, and N. J. Hurley. Evaluation of Hierarchical Clustering via Markov Decision Processes for Efficient Navigation and Search . In CLEF 2017, Proceedings , pages 125--131. Springer, 2017

2017
[17]

B. Ng, K. Boakye, C. Meyers, and A. Wang. Bayes-Adaptive Interactive POMDPs . 2012

2012
[18]

C. H. Papadimitriou and J. N. Tsitsiklis. The Complexity of Markov Decision Processes . Mathematics of operations research, 12 0 (3): 0 441--450, 1987

1987
[19]

Paquet, L

S. Paquet, L. Tobin, and B. Chaib-Draa. An Online POMDP Algorithm for Complex Multiagent Environments . In Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, pages 970--977. ACM, 2005 a

2005
[20]

Paquet, L

S. Paquet, L. Tobin, and B. Chaib-draa. Real-Time Decision Making for Large POMDPs . In Conference of the Canadian Society for Computational Studies of Intelligence , pages 450--455. Springer, 2005 b

2005
[21]

S. Ross, J. Pineau, and S. Paquet. Online Planning Algorithms for POMDPs . Journal of Artificial Intelligence Research, 32: 0 663--704, 2008

2008
[22]

Shani, D

G. Shani, D. Heckerman, and R. I. Brafman. An mdp-based recommender system. Journal of Machine Learning Research, 6 0 (Sep): 0 1265--1295, 2005

2005
[23]

Silver and J

D. Silver and J. Veness. Monte-Carlo Planning in large POMDPs . In Advances in neural information processing systems, pages 2164--2172, 2010

2010
[24]

S. P. Singh, T. Jaakkola, and M. I. Jordan. Learning without State-Estimation in Partially Observable Markovian Decision Processes . In Machine Learning Proceedings 1994 , pages 284--292. Elsevier, 1994

1994
[25]

Steinbach, G

M. Steinbach, G. Karypis, and V. Kumar. A Comparison of Document Clustering Techniques . In TextMining Workshop at KDD2000, 2000

2000
[26]

Zheng, F

G. Zheng, F. Zhang, Z. Zheng, Y. Xiang, N. J. Yuan, X. Xie, and Z. Li. Drn: A deep reinforcement learning framework for news recommendation. In Proceedings of the 2018 World Wide Web Conference, pages 167--176, 2018

2018

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Balcan, Y

M.-F. Balcan, Y. Liang, and P. Gupta. Robust Hierarchical Clustering . The Journal of Machine Learning Research, 15 0 (1): 0 3831--3871, 2014

work page 2014

[2] [2]

Boutilier and D

C. Boutilier and D. Poole. Computing Optimal Policies for Partially Observable Decision Processes Using Compact Representations . In AAAI, pages 1168--1175, 1996

work page 1996

[3] [3]

A. R. Cassandra, L. P. Kaelbling, and M. L. Littman. Acting Optimally in Partially Observable Stochastic Domains . In AAAI, volume 94, pages 1023--1028, 1994

work page 1994

[4] [4]

J. M. Cigarran, A. Pe\ n as, J. Gonzalo, and F. Verdejo. Evaluating hierarchical clustering of search results. In 12th SPIRE 2005, pages 49--54, 2005

work page 2005

[5] [5]

W. H. Day and H. Edelsbrunner. Efficient algorithms for agglomerative hierarchical clustering methods. Journal of Classification , 1 0 (1): 0 7--24, 1984

work page 1984

[6] [6]

M. O. Duff. Optimal Learning: Computational Procedures for Bayes-adaptive Markov Decision Processes . PhD thesis, Univ. of Massachusetts at Amherst, 2002

work page 2002

[7] [7]

A. Fern, S. Natarajan, K. Judah, and P. Tadepalli. A Decision-Theoretic Model of Assistance . In IJCAI, pages 1879--1884, 2007

work page 2007

[8] [8]

K. A. Heller and Z. Ghahramani. Bayesian Hierarchical Clustering . In ICML, pages 297--304, 2005

work page 2005