计算机科学

计算机科学 ›› 2026, Vol. 53 ›› Issue (10): 207-215.doi: 10.11896/jsjkx.260600049

• 数据库 & 大数据 & 数据科学 • 上一篇    下一篇

孤立核函数及其分布扩展在离线马尔可夫决策序列中的可达性建模

商元义1,2, 万盛华1,2, 甘乐3, 詹德川1,2   

  1. 1 南京大学人工智能学院 南京 210023
    2 南京大学计算机软件新技术国家重点实验室 南京 210023
    3 南京理工大学计算机科学与工程学院 南京 210094
  • 收稿日期:2026-06-08 修回日期:2026-08-25 发布日期:2026-10-13
  • 通讯作者: 詹德川(zhandc@nju.edu.cn)
  • 作者简介:(shangyy@lamda.nju.edu.cn)
  • 基金资助:
    国家自然科学基金青年学生基础研究项目(博士研究生)(624B200197);国家重点研发计划(2022ZD0114805)

Reachability Modeling in Offline Markov Decision Process Sequences via the Isolation Kernel and Its Distributional Extension

SHANG Yuanyi1,2, WAN Shenghua1,2, GAN Le3, ZHAN Dechuan1,2   

  1. 1 School of Artificial Intelligence,Nanjing University,Nanjing 210023, China
    2 State Key Laboratory for Novel Software Technology at Nanjing University,Nanjing 210023, China
    3 School of Computer Science and Engineering,Nanjing University of Science and Technology,Nanjing 210094, China
  • Received:2026-06-08 Revised:2026-08-25 Online:2026-10-13
  • About author:SHANG Yuanyi,born in 1997,doctoral candidate.His main research interests include machine learning and data mi-ning.
    ZHAN Dechuan,born in 1982,Ph.D,professor.His main research interests include machine learning and data mi-ning.
  • Supported by:
    Young Scientists Fund of the National Natural Science Foundation of China(Ph.D Candidate)(624B200197) and National Key Research and Development Program of China(2022ZD0114805).

PDF (PC)

67

摘要： 在离线马尔可夫决策过程序列中,状态相似性的定义影响经验可达性建模。几何型距离、时序型距离和局部动力学型距离分别侧重观测空间接近性、轨迹时间邻近性或短期转移差异,难以同时反映经验到达难度与未来演化一致性。为此,构建状态级与分布级相结合的分析框架:采用孤立核(IK)完成状态检索、离线k近邻目标重标注和图规划,采用孤立分布核(IDK)比较H步后继状态集合。在D4RL的PointMaze-Umaze-v2,PointMaze-Large-v2和AntMaze-Umaze-diverse-v1数据集上,评估局部排序、目标重标注、图规划和H步后继区域匹配。IK在PointMaze-Large和AntMaze重标注任务中的Spearman相关系数最高,而马氏距离在PointMaze-Umaze上更优,说明其优势依赖于任务。H=10时,IDK在3个数据集上的AUROC分别为0.9734,0.9938和0.9955;相较于保留访问顺序的原始H步距离,其在PointMaze-Umaze上的差异很小,在AntMaze上的增益较为明显。敏感性分析表明,性能受表示空间、随机划分规模、未来窗口长度和规划验收阈值影响。重复随机划分可降低给定离线状态池下的估计波动,但不能消除数据覆盖偏差;均值嵌入具有排列不变性,不能保留完整的访问顺序。规划结果属于相似性度量的独立诊断,不构成端到端离线策略回报改善的证据。该实验结论主要适用于具有明确几何瓶颈和可用轨迹覆盖的迷宫环境。

关键词: 孤立核, 孤立分布核, 马尔可夫决策过程, 可达性, 离线强化学习, 状态相似性

Abstract: In offline Markov decision process sequences,the definition of state similarity affects empirical reachability modeling.Geometric,temporal,and local-dynamics distances focus on proximity in observation space,temporal adjacency,or short-horizon transition differences,respectively,and may not jointly capture empirical reaching difficulty and similarity of future evolution.A framework combining state-level and distribution-level analysis is developed:the isolation kernel(IK) is used for state retrieval,offline k-nearest-neighbor goal relabeling,and graph planning,while the isolation distributional kernel(IDK) compares H-step successor-state sets.Local ranking,goal relabeling,graph planning,and H-step successor-region matching are evaluated on PointMaze-Umaze-v2,PointMaze-Large-v2,and AntMaze-Umaze-diverse-v1 from D4RL.IK achieves the highest Spearman correlations in the PointMaze-Large and AntMaze relabeling tasks,whereas Mahalanobis distance performs better on PointMaze-Umaze,indicating that the advantage is task dependent.At H=10,IDK achieves AUROC values of 0.9734,0.9938,and 0.9955 on the three datasets;compared with the order-sensitive raw H-step distance,the difference is small on PointMaze-Umaze and more pronounced on AntMaze.Sensitivity analyses show that performance depends on the representation,partition scale,future-window length,and planning acceptance threshold.Repeated random partitions reduce estimation variability conditional on the offline state pool but do not remove coverage bias;mean embeddings are permutation invariant and cannot preserve the full visitation order.The planning results are metric-level diagnostics and do not establish improved end-to-end offline-policy return.The empirical findings in this study mainly apply to maze environments with explicit geometric bottlenecks and usable trajectory coverage.

Key words: Isolation kernel, Isolation distributional kernel, Markov decision processes, Reachability, Offline reinforcement lear-ning, State similarity

中图分类号: 

  • TP311.13
[1] LEVINE S,KUMAR A,TUCKER G,et al.Offline reinforcement learning:Tutorial,review,and perspectives on open problems[PP/OL].arXiv(2020-05-04)[2026-09-11].https://arxiv.org/abs/2005.01643.
[2] MAHALANOBIS P C.Reprint of:Mahalanobis,P.C.(1936)“On the Generalised Distance in Statistics”[J].Sankhya A,2018,80(Suppl 1):1-7.
[3] FERNS N,PANANGADEN P,PRECUP D.Metrics for finite Markov decision processes[C]//Proceedings of the 19th NationalConference on Artificial Intelligence.2004:950-951.
[4] GELADA C,KUMAR S,BUCKMAN J,et al.DeepMDP:Learning continuous latent space models for representation learning[C]//Proceedings of the 36th International Conference on Machine Learning.2019:2170-2179.
[5] CASTRO P S,KASTNER T,PANANGADEN P,et al.MICo:Improved representations via sampling-based state similarity for Markov decision processes[C]//Advances in Neural Information Processing Systems(NeurIPS 2021).2021:30113-30126.
[6] DADASHI R,REZAEIFAR S,VIEILLARD N,et al.Offline reinforcement learning with pseudometric learning[C]//Procee-dings of the 38th International Conference on Machine Lear-ning.2021:2307-2318.
[7] GHOSH D,GUPTA A,LEVINE S.Learning actionable representations with goal-conditioned policies[PP/OL].arXiv(2018-11-19)[2026-09-11].https://arxiv.org/abs/1811.07819.
[8] ZANG H Y,LI X,ZHANG L J,et al.Understanding and addressing the pitfalls of bisimulation-based representations in offline reinforcement learning[C]// Advances in Neural Information Processing Systems(NeurIPS 2023).2023:28311-28340.
[9] TING K M,ZHU Y,ZHOU Z H.Isolation kernel and its effect on SVM[C]//Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.2018:2329-2337.
[10] TING K M,WASHIO T,WELLS J R,et al.Isolation kerneldensity estimation[C]//2021 IEEE International Conference on Data Mining.IEEE,2021:619-628.
[11] XU B C,TING K M,ZHOU Z H.Isolation set-kernel and its application to multi-instance learning[C]//Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.2019:941-949.
[12] TING K M,XU B C,WASHIO T,et al.Isolation distributional kernel:A new tool for kernel based anomaly detection[C]//Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.2020:198-206.
[13] ZELNIK-MANOR L,PERONA P.Self-tuning spectral cluste-ring[C]//Proceedings of the 18th International Conference on Neural Information Processing Systems.2004:1601-1608.
[14] FERNS N,PANANGADEN P,PRECUP D.Bisimulation metrics for continuous Markov decision processes[J].SIAM Journal on Computing,2011,40(6):1662-1714.
[15] CASTRO P S.Scalable methods for computing state similarity in deterministic markov decision processes[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2020:10069-10076.
[16] ZHANG A,MCALLISTER R,CALANDRA R,et al.Learning invariant representations for reinforcement learning without reconstruction[PP/OL].arXiv(2020-06-18)[2026-09-11].https://arxiv.org/abs/2006.10742.
[17] KEMERTAS M,AUMENTADO-ARMSTRONG T.Towardsrobust bisimulation metric learning[C]//Proceedings of the 35th International Conference on Neural Information Proces-sing Systems.2021:4764-4777.
[18] SMOLA A,GRETTON A,SONG L,et al.A Hilbert space embedding for distributions[C]//International Conference on Algorithmic Learning Theory.Berlin:Springer,2007:13-31.
[19] JEBARA T,KONDOR R,HOWARD A.Probability productkernels[J].Journal of Machine Learning Research,2004,5:819-844.
[20] CUTURI M.Sinkhorn Distances:Lightspeed computation of optimal transportation distances[C]//Advances in Neural Information Processing Systems(NIPS 2013).2013:2292-2300.
[21] ARONSZAJN N.Theory of reproducing kernels[J].Transactions of the American Mathematical Society,1950,68(3):337-404.
[22] HOFMANN T,SCHÖLKOPF B,SMOLA A J.Kernel methods in machine learning[J].The Annals of Statistics,2008,36(3):1171-1220.
[23] WILLIAMS C,SEEGER M.Using the Nyström method tospeed up kernel machines[C]//Proceedings of the 14th International Conference on Neural Information Processing Systems.2000:661-667.
[24] RAHIMI A,RECHT B.Random features for large-scale kernel machines[C]// Proceedings of the 21st International Conference on Neural Information Processing Systems.2007:1177-1184.
[25] ANDRYCHOWICZ M,WOLSKI F,RAY A,et al.Hindsightexperience replay[C]//Advances in Neural Information Processing Systems 30.2017.
[26] CHEBOTAR Y,HAUSMAN K,LU Y,et al.Actionable models:Unsupervised offline reinforcement learning of robotic skills[PP/OL].arXiv(2021-04-15)[2026-09-14].https://arxiv.org/abs/2104.07749.
[27] DIJKSTRA E W.A note on two problems in connexion with graphs[J].Numerische Mathematik,1959,1:269-271.
[28] FU J,KUMAR A,NACHUM O,et al.D4RL:Datasets for deep data-driven reinforcement learning[PP/OL].arXiv(2020-04-15)[2026-09-14].https://arxiv.org/abs/2004.07219.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市两江新区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发