2025-11-20T19:43:15.563163

Homomorphic Mappings for Value-Preserving State Aggregation in Markov Decision Processes

Zhao, Li, Feng et al.
State aggregation aims to reduce the computational complexity of solving Markov Decision Processes (MDPs) while preserving the performance of the original system. A fundamental challenge lies in optimizing policies within the aggregated, or abstract, space such that the performance remains optimal in the ground MDP-a property referred to as {"}optimal policy equivalence {"}. This paper presents an abstraction framework based on the notion of homomorphism, in which two Markov chains are deemed homomorphic if their value functions exhibit a linear relationship. Within this theoretical framework, we establish a sufficient condition for the equivalence of optimal policy. We further examine scenarios where the sufficient condition is not met and derive an upper bound on the approximation error and a performance lower bound for the objective function under the ground MDP. We propose Homomorphic Policy Gradient (HPG), which guarantees optimal policy equivalence under sufficient conditions, and its extension, Error-Bounded HPG (EBHPG), which balances computational efficiency and the performance loss induced by aggregation. In the experiments, we validated the theoretical results and conducted comparative evaluations against seven algorithms.
academic

मार्कोव निर्णय प्रक्रियाओं में मूल्य-संरक्षण स्थिति एकत्रीकरण के लिए होमोमॉर्फिक मैपिंग

बुनियादी जानकारी

  • पेपर ID: 2510.09965
  • शीर्षक: मार्कोव निर्णय प्रक्रियाओं में मूल्य-संरक्षण स्थिति एकत्रीकरण के लिए होमोमॉर्फिक मैपिंग
  • लेखक: शुओ झाओ, योंगकियांग ली, यू फेंग, झोंगशेंग हौ, युआनजिंग फेंग
  • वर्गीकरण: cs.LG cs.AI stat.ML
  • प्रकाशन समय: 14 अक्टूबर, 2025 (arXiv प्रीप्रिंट)
  • पेपर लिंक: https://arxiv.org/abs/2510.09965

सारांश

यह पेपर मार्कोव निर्णय प्रक्रिया (MDP) में स्थिति एकत्रीकरण समस्या के लिए होमोमॉर्फिक मैपिंग पर आधारित एक अमूर्त ढांचा प्रस्तावित करता है। यह ढांचा दो मार्कोव श्रृंखलाओं के बीच मूल्य फलनों के बीच रैखिक संबंध स्थापित करके होमोमॉर्फिज्म को परिभाषित करता है, जिससे कम्प्यूटेशनल जटिलता को कम करते हुए इष्टतम नीति समतुल्यता को संरक्षित किया जाता है। पेपर HPG और EBHPG दो एल्गोरिदम प्रस्तावित करता है, जो क्रमशः पर्याप्त शर्तों को पूरा करने और न करने पर सैद्धांतिक गारंटी प्रदान करते हैं, और प्रयोगों के माध्यम से सैद्धांतिक परिणामों की प्रभावशीलता को सत्यापित करते हैं।

अनुसंधान पृष्ठभूमि और प्रेरणा

समस्या परिभाषा

जटिल वास्तविक समस्याओं में MDP के व्यापक अनुप्रयोग के साथ, बड़े पैमाने पर स्थिति स्थान से उत्पन्न कम्प्यूटेशनल जटिलता की समस्या तेजी से प्रमुख हो गई है। स्थिति एकत्रीकरण एक महत्वपूर्ण रणनीति के रूप में, स्थिति स्थान को संपीड़ित करके कम्प्यूटेशनल लागत को कम करने का लक्ष्य रखता है, लेकिन मुख्य चुनौती यह सुनिश्चित करना है कि अमूर्त स्थान में अनुकूलित नीति मूल MDP में इष्टतम रहे।

अनुसंधान का महत्व

  1. कम्प्यूटेशनल दक्षता: बड़े पैमाने पर MDP का समाधान जटिलता स्थिति स्थान के साथ घातीय रूप से बढ़ता है
  2. व्यावहारिक अनुप्रयोग: बहु-एजेंट समन्वय, दृश्य प्रतिनिधित्व सीखना, परिचालन प्रणाली आदि क्षेत्रों की तत्काल आवश्यकता
  3. सैद्धांतिक महत्व: इष्टतम नीति समतुल्यता के लिए व्यवस्थित सैद्धांतिक विश्लेषण उपकरणों की कमी

मौजूदा विधियों की सीमाएं

  1. विशेषता-आधारित विधियां: विशेष रूप से उच्च-आयामी सेटिंग में बड़ी कम्प्यूटेशनल संसाधनों की आवश्यकता होती है
  2. मूल्य-आधारित एकत्रीकरण: हालांकि मूल्य फलन त्रुटि न्यूनीकरण पर ध्यान केंद्रित करते हैं, लेकिन इष्टतम नीति समतुल्यता के लिए सैद्धांतिक उपकरणों की कमी है
  3. होमोमॉर्फिक MDP सिद्धांत: अमूर्त MDP को मूल MDP के पुरस्कार और संक्रमण गतिशीलता को पूरी तरह से संरक्षित करने की आवश्यकता है, शर्तें बहुत कठोर हैं

मुख्य योगदान

  1. होमोमॉर्फिक मार्कोव श्रृंखला ढांचा प्रस्तावित करना: पारंपरिक होमोमॉर्फिक MDP की तुलना में अधिक शिथिल सैद्धांतिक ढांचा स्थापित किया गया है, जिसमें केवल मूल्य फलनों के बीच रैखिक संबंध की आवश्यकता है
  2. इष्टतम नीति समतुल्यता के लिए पर्याप्त शर्तें स्थापित करना: साबित किया गया है कि जब एन्कोडिंग मैट्रिक्स की पंक्ति स्थान मौलिक संक्रमण वेक्टर के विस्तार को शामिल करता है, तो इष्टतम नीति समतुल्यता सत्य है
  3. HPG एल्गोरिदम विकसित करना: पर्याप्त शर्तों को पूरा करने पर इष्टतम नीति समतुल्यता की गारंटी देने वाली नीति ढाल एल्गोरिदम
  4. EBHPG एल्गोरिदम डिजाइन करना: पर्याप्त शर्तों को न पूरा करने वाले मामलों को संभालने के लिए विस्तारित एल्गोरिदम, प्रदर्शन निचली सीमा गारंटी प्रदान करता है
  5. त्रुटि सीमा विश्लेषण प्रदान करना: अनुमानित त्रुटि ऊपरी सीमा और उद्देश्य फलन प्रदर्शन निचली सीमा प्राप्त की गई है

विधि विवरण

कार्य परिभाषा

अनंत समय क्षितिज MDP MS=(S,A,PSA,γ,r)M_S = (S,A,P_{SA},\gamma,r) दिया गया है, लक्ष्य एन्कोडिंग मैट्रिक्स PνP_\nu और अमूर्त स्थिति स्थान UU खोजना है, ताकि अमूर्त स्थान में अनुकूलित नीति मूल MDP में इष्टतम रहे।

मुख्य सैद्धांतिक ढांचा

होमोमॉर्फिक मार्कोव श्रृंखला परिभाषा

परिभाषा 1: नीति π\pi द्वारा प्रेरित मूल मार्कोव श्रृंखला MSπM^\pi_S और अमूर्त मार्कोव श्रृंखला MUμM^\mu_U दिए गए हैं, यदि निम्नलिखित शर्तें पूरी होती हैं, तो MUμM^\mu_U को MSπM^\pi_S की होमोमॉर्फिक मार्कोव श्रृंखला कहा जाता है:

PUμPν=PνPSπP^\mu_U P_\nu = P_\nu P^\pi_SRUπ,ν=PνRSπR^{\pi,\nu}_U = P_\nu R^\pi_S

जहां Pν∈R∣U∣×∣S∣P_\nu \in \mathbb{R}^{|U| \times |S|} एन्कोडिंग मैट्रिक्स है।

मूल्य फलन रैखिक संबंध

प्रमेय 1: यदि MUμM^\mu_U MSπM^\pi_S की होमोमॉर्फिक मार्कोव श्रृंखला है, तो उनके मूल्य फलन रैखिक संबंध को संतुष्ट करते हैं: VUμ=PνVSπV^\mu_U = P_\nu V^\pi_S

होमोमॉर्फिक मैपिंग अस्तित्व शर्तें

प्रमेय 3: मूल MDP MSM_S और एन्कोडिंग मैट्रिक्स PνP_\nu दिए गए हैं, होमोमॉर्फिक मैपिंग fν:ΠS→ΠUf_\nu: \Pi_S \to \Pi_U अस्तित्व में है यदि और केवल यदि PνP_\nu की पंक्ति स्थान span(F)\text{span}(F) को शामिल करता है, जहां FF सभी मौलिक संक्रमण वेक्टर का अधिकतम रैखिक स्वतंत्र उपसमुच्चय है।

एल्गोरिदम डिजाइन

HPG एल्गोरिदम (एल्गोरिदम 1)

जब पर्याप्त शर्तें पूरी होती हैं:

  1. PνP_\nu के मूर-पेनरोज़ छद्म-व्युत्क्रम Pν†P_\nu^\dagger की गणना करें
  2. Cπθt=PSπθtPν†C^{\pi_{\theta_t}} = P^{\pi_{\theta_t}}_S P_\nu^\dagger के माध्यम से अमूर्त संक्रमण मैट्रिक्स की गणना करें
  3. अमूर्त मूल्य फलन VUfν(πθt)V^{f_\nu(\pi_{\theta_t})}_U का मूल्यांकन करें
  4. नीति पैरामीटर θt+1\theta_{t+1} को अपडेट करें

कम्प्यूटेशनल जटिलता: O(∣S∣∣A∣+∣U∣∣S∣2+∣U∣3)O(|S||A| + |U||S|^2 + |U|^3), जब ∣U∣≪∣S∣|U| \ll |S| हो तो मानक नीति मूल्यांकन के O(∣S∣∣A∣+∣S∣3)O(|S||A| + |S|^3) से काफी बेहतर है।

EBHPG एल्गोरिदम (एल्गोरिदम 2)

जब पर्याप्त शर्तें पूरी नहीं होती हैं, प्रदर्शन निचली सीमा को अनुकूलित करें: JS(π~)≥JU(fν(π~))−∥g(π~,ν)∥1−γJ_S(\tilde{\pi}) \geq J_U(f_\nu(\tilde{\pi})) - \frac{\|g(\tilde{\pi},\nu)\|}{1-\gamma}

जहां ∥g(π,ν)∥1−γ\frac{\|g(\pi,\nu)\|}{1-\gamma} प्रदर्शन अंतर की ऊपरी सीमा है।

तकनीकी नवाचार बिंदु

  1. शर्तों को शिथिल करना: पारंपरिक होमोमॉर्फिक MDP की तुलना में जो संक्रमण संभावनाओं की पूर्ण समानता की आवश्यकता है, यह पेपर केवल रैखिक निर्भरता संबंध की आवश्यकता है
  2. मैट्रिक्स संचालन अनुकूलन: पुनरावृत्तिमूलक लूप के बजाय मैट्रिक्स संचालन के माध्यम से एकत्रीकरण को लागू करना, कम्प्यूटेशनल दक्षता में सुधार
  3. त्रुटि सीमाएं: आदर्श शर्तों को न पूरा करने पर सैद्धांतिक गारंटी और अनुकूलन दिशा प्रदान करना

प्रयोगात्मक सेटअप

डेटासेट

  1. यादृच्छिक मॉडल: ∣S∣=100,∣A∣=10|S|=100, |A|=10, संक्रमण मैट्रिक्स घनत्व 10%-100%
  2. कमजोर युग्मित MDP: ∣S∣=3600,∣A∣=10|S|=3600, |A|=10, स्तरीय निर्णय का अनुकरण
  3. चार कमरे ग्रिड विश्व: ∣S∣=6400,∣A∣=4|S|=6400, |A|=4, शास्त्रीय नेविगेशन कार्य
  4. श्रृंखलाबद्ध कतार प्रबंधन: ∣S∣=6084,∣A∣=3|S|=6084, |A|=3, वास्तविक सर्वर प्रणाली से प्रेरित

मूल्यांकन मेट्रिक्स

  • नीति प्रदर्शन: JS(π)=Es0∼ξS[VSπ(s0)]J_S(\pi) = \mathbb{E}_{s_0 \sim \xi_S}[V^\pi_S(s_0)]
  • कम्प्यूटेशनल समय: वास्तविक दक्षता के लिए दीवार घड़ी समय माप
  • अभिसरण: नीति पुनरावृत्ति इष्टतम समाधान में अभिसरण

तुलना विधियां

7 आधारभूत विधियों को शामिल करता है:

  • मानक नीति पुनरावृत्ति (PolicyIter)
  • शास्त्रीय एकत्रीकरण तकनीक (Bertsekas)
  • हाल की विधियां: Ayoub et al., Chen, Forghieri et al., Ishfaq et al., Lee et al.

कार्यान्वयन विवरण

  • सीखने की दर: 1×10−31 \times 10^{-3}
  • अमूर्त स्थिति संख्या: ∣U∣=int(0.5×r)|U| = \text{int}(0.5 \times r)
  • हार्डवेयर: AMD Ryzen 7 5800X CPU + NVIDIA GeForce RTX 3090 GPU

प्रयोगात्मक परिणाम

सैद्धांतिक सत्यापन प्रयोग

चित्र 2 ∣S∣=100|S|=100 के छोटे पैमाने के कार्यों पर सत्यापन परिणाम प्रदर्शित करता है:

  1. पर्याप्त शर्तें पूरी होने पर: "100%" के रूप में चिह्नित वक्र (संबंधित ∣U∣=r|U|=r) सभी कार्यों में इष्टतम मान में अभिसरित होते हैं, प्रमेय 2 और 3 की सही्ता को सत्यापित करते हैं
  2. पर्याप्त शर्तें पूरी न होने पर: "80%", "50%", "20%" के रूप में चिह्नित वक्र स्पष्ट दोलन प्रदर्शित करते हैं, इष्टतम समाधान में अभिसरण की गारंटी नहीं दे सकते
  3. EBHPG प्रदर्शन: ठोस रेखा (वास्तविक प्रदर्शन) बिंदीदार रेखा (प्रदर्शन निचली सीमा) के साथ सुधार होता है, प्रमेय 5 और 6 को सत्यापित करता है

बड़े पैमाने पर प्रदर्शन तुलना

चित्र 3 बड़े पैमाने के कार्यों पर प्रदर्शन तुलना प्रदर्शित करता है:

  1. कम्प्यूटेशनल दक्षता: यह विधि चार कमरे के वातावरण को छोड़कर सभी कार्यों में आधारभूत विधियों से काफी बेहतर है
  2. मॉडल-आधारित बनाम मॉडल-मुक्त: मॉडल-आधारित विधियां आम तौर पर मॉडल-मुक्त विधियों से बेहतर हैं, क्योंकि वे नमूनाकरण के बजाय सटीक योजना का उपयोग करते हैं
  3. मैट्रिक्स संचालन लाभ: आधारभूत विधियों के नेस्टेड लूप कार्यान्वयन की तुलना में, मैट्रिक्स संचालन महत्वपूर्ण दक्षता सुधार लाता है

विशेष मामला विश्लेषण

चार कमरे के वातावरण में सभी विधियां आधारभूत को पार करने में कठिनाई का सामना करती हैं, संभावित कारण:

  • पुरस्कार संरचना अत्यंत विरल है
  • बड़ी स्थिति स्थान और विरल पुरस्कार का संयोजन अन्वेषण को कठिन बनाता है
  • पुरस्कार फलन विरलता नीति पुनरावृत्ति दक्षता को धीमा कर सकती है

संबंधित कार्य

स्थिति अमूर्तता विधियों का वर्गीकरण

  1. विशेषता-आधारित विधियां: हाथ से डिजाइन किए गए या सीखे गए विशेषता फलनों का उपयोग, जैसे गतिशील बेयस नेटवर्क, वर्णक्रमीय विश्लेषण
  2. मूल्य-आधारित एकत्रीकरण: मूल्य फलन अनुमान त्रुटि न्यूनीकरण पर ध्यान केंद्रित, जैसे अनुकूली पुनरावृत्तिमूलक एकत्रीकरण एल्गोरिदम

सैद्धांतिक ढांचा विकास

  1. होमोमॉर्फिक MDP सिद्धांत: Ravindran द्वारा प्रस्तावित संरचना-संरक्षण मैपिंग ढांचा
  2. द्विसिमुलेशन सिद्धांत: MDP में शास्त्रीय व्यवहार समतुल्यता अवधारणा का विस्तार
  3. निरंतर स्थान विस्तार: Ferns आदि द्वारा द्विसिमुलेशन मेट्रिक को निरंतर स्थिति स्थान तक विस्तारित करना

इस पेपर के सापेक्ष लाभ

मौजूदा विधियों की तुलना में, यह पेपर अधिक शिथिल पर्याप्त शर्तें और अधिक कुशल कम्प्यूटेशनल कार्यान्वयन प्रदान करता है।

निष्कर्ष और चर्चा

मुख्य निष्कर्ष

  1. होमोमॉर्फिक मैपिंग पर आधारित स्थिति एकत्रीकरण सैद्धांतिक ढांचा स्थापित किया गया है
  2. इष्टतम नीति समतुल्यता के लिए पर्याप्त शर्तें प्रदान की गई हैं, जो पारंपरिक होमोमॉर्फिक MDP शर्तों से अधिक शिथिल हैं
  3. HPG और EBHPG दो व्यावहारिक एल्गोरिदम विकसित किए गए हैं, जो सैद्धांतिक और प्रायोगिक दोनों रूप से सत्यापित हैं

सीमाएं

  1. पर्याप्त शर्तें सीमा: कुछ मामलों में, पर्याप्त शर्तों को पूरा करने की कम्प्यूटेशनल लागत अभी भी बहुत अधिक हो सकती है
  2. अभिसरण गारंटी: अनुमानित त्रुटि मौजूद होने पर, इष्टतम नीति में अभिसरण की गारंटी नहीं दी जा सकती
  3. निरंतर स्थान: विश्लेषण निरंतर स्थिति स्थान तक विस्तारित नहीं किया गया है

भविष्य की दिशाएं

  1. इष्टतम नीति समतुल्यता के लिए पर्याप्त शर्तों को शिथिल करना
  2. निरंतर स्थिति स्थान तक विस्तार करना
  3. अनुमानित मामलों में अभिसरण गारंटी में सुधार करना

गहन मूल्यांकन

शक्तियां

  1. सैद्धांतिक योगदान: मौजूदा विधियों की तुलना में अधिक सामान्य सैद्धांतिक ढांचा प्रस्तावित किया गया है
  2. व्यावहारिकता: एल्गोरिदम डिजाइन कम्प्यूटेशनल दक्षता पर विचार करता है, बड़े पैमाने पर अनुप्रयोगों के लिए उपयुक्त है
  3. पूर्णता: सैद्धांतिक विश्लेषण से एल्गोरिदम डिजाइन तक प्रायोगिक सत्यापन तक, एक संपूर्ण अनुसंधान श्रृंखला बनाई गई है
  4. कठोरता: गणितीय व्युत्पत्ति सुदृढ़ है, प्रायोगिक डिजाइन उचित है

कमियां

  1. लागू सीमा: पर्याप्त शर्तें कुछ मामलों में अभी भी बहुत कठोर हो सकती हैं
  2. प्रायोगिक कवरेज: चार कमरे के वातावरण में असामान्य परिणामों को अधिक गहन विश्लेषण की आवश्यकता है
  3. तुलना आधारभूमि: कुछ तुलना विधियां नवीनतम SOTA विधियां नहीं हो सकती हैं

प्रभाव

  1. सैद्धांतिक मूल्य: MDP स्थिति एकत्रीकरण के लिए नए सैद्धांतिक उपकरण प्रदान करता है
  2. व्यावहारिक मूल्य: एल्गोरिदम कई वास्तविक कार्यों में लाभ प्रदर्शित करते हैं
  3. विस्तारशीलता: ढांचा अन्य समस्याओं तक विस्तार की संभावना रखता है

लागू परिदृश्य

  1. बड़े पैमाने पर MDP समाधान
  2. स्तरीय सुदृढ़ शिक्षा
  3. बहु-एजेंट प्रणाली
  4. संरचित स्थिति स्थान वाली निर्णय समस्याएं

संदर्भ

पेपर 50 संबंधित संदर्भों का हवाला देता है, जो MDP सिद्धांत, स्थिति अमूर्तता, सुदृढ़ शिक्षा आदि कई क्षेत्रों के महत्वपूर्ण कार्यों को शामिल करता है, जो अनुसंधान के लिए एक मजबूत सैद्धांतिक आधार प्रदान करता है।

समग्र मूल्यांकन: यह एक सैद्धांतिक और व्यावहारिक दोनों रूप से महत्वपूर्ण उच्च गुणवत्ता वाला पेपर है, जो MDP स्थिति एकत्रीकरण क्षेत्र में महत्वपूर्ण योगदान देता है। सैद्धांतिक ढांचा नवीन और व्यावहारिक है, एल्गोरिदम डिजाइन उचित है, प्रायोगिक सत्यापन पर्याप्त है। कुछ सीमाओं के बावजूद, यह समग्र रूप से इस क्षेत्र के विकास के लिए मूल्यवान सैद्धांतिक उपकरण और व्यावहारिक विधियां प्रदान करता है।