🔢 mathematics

Linking PageRank, Time Reversal, and Policy Evaluation

यह शोध पत्र यह प्रदर्शित करके कि वैल्यू फंक्शन्स (value functions) को उपयुक्त रूप से परिभाषित टाइम-रिवर्सड (time-reversed) मार्कोव चेन्स के पेजरैंक वेक्टर्स से प्राप्त किया जा सकता है, मार्कोव डिसीजन प्रोसेस में पॉलिसी इवैल्यूएशन को पेजरैंक से जोड़ने वाला एक सैद्धांतिक ढांचा स्थापित करता है, जिससे सामान्य पॉलिसी इवैल्यूएशन समस्याओं को रिकरेंट और ट्रांजिएंट स्टेट्स के बीच सुलभ पेजरैंक घटकों में विभाजित किया जा सके।

मूल लेखक: Konstantin Avrachenkov, Lorenzo Gregoris, Nelly Litvak

प्रकाशित 2026-05-04

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Konstantin Avrachenkov, Lorenzo Gregoris, Nelly Litvak

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक विशाल, जटिल भूलभुलैया के हर कमरे का "दीर्घकालिक मूल्य" (long-term value) पता लगाने की कोशिश कर रहे हैं। इस भूलभुलैया में, आपके पास एक मानचित्र (एक पॉलिसी) है जो आपको बताता है कि प्रत्येक कमरे से कौन सा दरवाजा चुनना है। हर बार जब आप चलते हैं, तो आपको एक छोटा इनाम (जैसे एक सिक्का मिलना) मिल सकता है या कोई दंड मिल सकता है। आपका लक्ष्य यह गणना करना है कि यदि आप एक विशिष्ट कमरे से शुरू करते हैं और हमेशा के लिए अपने मानचित्र का अनुसरण करते हैं, तो आप कुल कितना अपेक्षित खजाना एकत्र करेंगे, लेकिन इसमें एक मोड़ है: भविष्य के पुरस्कार वर्तमान के मुकाबले कम मूल्यवान होते हैं (इसे "डिस्काउंटिंग" कहा जाता है)।

कंप्यूटर विज्ञान और गणित की दुनिया में, इसे पॉलिसी इवैल्यूएशन (Policy Evaluation) कहा जाता है। आमतौर पर, इसे हल करना समीकरणों की एक विशाल गांठ को सुलझाने जैसा होता है। यह धीमा और गणनात्मक रूप से भारी होता है, विशेष रूप से विशाल भूलभुलैया के लिए।

यह शोध पत्र एक चतुर शॉर्टकट पेश करता है। लेखकों, एव्राचेनकोव, ग्रेगोरिस और लिटवैक ने खोजा कि इस "भूलभुलैया के खजाने" वाली समस्या को हल करना गणितीय रूप से एक पूरी तरह से अलग समस्या को हल करने के समान है: पेजरैंक (PageRank)।

मुख्य विचार: भूलभुलैया को उल्टा करना

आप पेजरैंक को जानते होंगे जिसे गूगल ने वेबसाइटों को रैंक करने के लिए एल्गोरिदम के रूप में उपयोग किया था। यह इस कल्पना के साथ काम करता है कि एक "रैंडम सर्फर" वेबसाइट पर लिंक पर क्लिक करता है। अधिकांश समय, वे एक लिंक का अनुसरण करते हैं, लेकिन कभी-कभी (मान लीजिए 15% बार), वे ऊब जाते हैं और एक यादृच्छिक (random) पेज पर "टेलीपोर्ट" हो जाते हैं। एक पेज का "महत्व" इस बात से तय होता है कि सर्फर कितनी बार वहां लैंड करता है।

पेपर दिखाता है कि आपकी "भूलभुलैया के खजाने" वाली समस्या वास्तव में एक छद्म रूप में पेजरैंक समस्या है, लेकिन कुछ जादुई ट्रिक्स के साथ:

पीछे की ओर चलना (समय उलटना - Time Reversal): सर्फर को भूलभुलैया के माध्यम से आगे चलते हुए सिम्युलेट करने के बजाय, लेखक कहते हैं, "आइए पीछे चलें।" वे आपके भूलभुलभैया के नियमों को लेते हैं और उन्हें उलट देते हैं। यदि आप आमतौर पर कमरे A से कमरे B की ओर जाते हैं, तो "टाइम-रिवर्सड" संस्करण यह देखता है कि आप B से A पर कैसे पहुँच सकते थे।
डिस्काउंट फैक्टर "ऊबने वाला बटन" है: पेजरैंक में, "टेलीपोर्टेशन पैरामीटर" (वह संभावना कि सर्फर ऊब जाएगा और एक रैंडम पेज पर कूद जाएगा) आमतौर पर उपयोगकर्ता द्वारा सेट किया जाता है। इस पेपर में, "डिस्काउंट फैक्टर" (आप भविष्य की कितनी परवाह करते हैं) उस "ऊबने वाले बटन" में बदल जाता है। यदि आप भविष्य की बहुत अधिक परवाह करते हैं (उच्च डिस्काउंट), तो सर्फर शायद ही कभी टेलीपोर्ट करता है। यदि आप केवल वर्तमान की परवाह करते हैं (कम डिस्काउंट), तो सर्फर अक्सर टेलीपोर्ट करता है।
इनाम तय करते हैं कि कहाँ से पुनः आरंभ करना है: मानक पेजरैंक में, सर्फर किसी यादृच्छिक पेज या किसी विशिष्ट पसंदीदा पेज पर फिर से शुरू कर सकता है। यहाँ, आपकी भूलभुलैया के "इनाम" तय करते हैं कि सर्फर कहाँ से फिर से शुरू करेगा। यदि किसी कमरे में बहुत बड़ा खजाना है, तो सर्फर के वहां फिर से शुरू करने की संभावना अधिक होगी।

"अहा!" वाला क्षण (The "Aha!" Moment)

लेखक सिद्ध करते हैं कि यदि आप इस "पीछे की ओर चलने वाले" पेजरैंक सिमुलेशन को चलाते हैं, तो जो परिणाम आपको मिलते हैं वे आपकी मूल भूलभुलैया के खजाने के मूल्यों का एक सीधा गणितीय मानचित्र होते हैं। आपको भूलभुलैया के भारी, उलझे हुए समीकरणों को सीधे हल करने की आवश्यकता नहीं है। इसके बजाय, आप उन सभी सुपर-फास्ट, अत्यधिक अनुकूलित उपकरणों का उपयोग कर सकते हैं जिन्हें इंजीनियरों ने पहले से ही वेबसाइटों को रैंक करने के लिए बनाया है (जैसे कि पेपर में उल्लेखित "रेड-लाइट-ग्रीन-लाइट" एल्गोरिदम)।

जटिल भूलभुलैया के बारे में क्या?

वास्तविक भूलभulैया हमेशा सरल लूप नहीं होती हैं। कभी-कभी आप एक डेड एंड (क्षणिक अवस्था/transient states) में फंस जाते हैं या एक ऐसे लूप में प्रवेश करते हैं जिससे आप बाहर नहीं निकल सकते (पुनरावर्ती अवस्था/recurrent states)।

पेपर आगे कहता है: "जटिलता की चिंता न करें।" आप भूलभुलैया को उसके अलग-अलग हिस्सों में तोड़ सकते हैं:

लूप्स (The Loops): उन कमरों के लिए जो एक बंद लूप बनाते हैं, आप बस मानक बैकवर्ड पेजरैंक चलाते हैं।
डेड एंड्स (The Dead Ends): उन कमरों के लिए जो अंततः आपको खेल से बाहर ले जाते हैं, वे एक विशेष गणितीय ट्रिक (जिसे "डूब h-ट्रांसफॉर्म" कहा जाता है) का उपयोग करते हैं ताकि डेड एंड को एक लूप में बदला जा सके, उसे हल किया जा सके, और फिर उत्तर को वापस अनुवादित किया जा सके।

यह एक जटिल, टूटी हुई मशीन को लेने, उसके सरल गियरों में अलग करने, प्रत्येक गियर को एक मानक उपकरण का उपयोग करके ठीक करने और फिर उसे वापस जोड़ने जैसा है।

प्रमाण (The Proof in the Pudding)

यह दिखाने के लिए कि यह केवल सिद्धांत नहीं है, लेखकों ने विशाल ग्राफों (सोचिए कि वे विशाल सोशल नेटवर्क या सड़क मानचित्र हैं) पर एक "स्टीकी रैंडम वॉक" पर इसका परीक्षण किया। उन्होंने अपने नए "पेजरैंक तरीके" से भूलभुलैया को हल करने की तुलना पुराने, मानक तरीकों (जैसे गौस-सीडेल) के विरुद्ध की।

परिणाम? पेजरैंक विधि (विशेष रूप से "रेड-लाइट-ग्रीन-लाइट" संस्करण) त्रुटियों को कम करने में अधिक तेज़ और कुशल थी। यह पारंपरिक तरीकों की तुलना में कम चरणों में सही उत्तर तक पहुँच गई।

सारांश

संक्षेप में, यह पेपर कहता है: "भारी गणित के साथ भूलभुलैया को आगे की ओर हल करने की कोशिश करना बंद करें। भूलभुलैया को पीछे की ओर पलटें, अपने पुरस्कारों को एक रीस्टार्ट बटन में बदलें, और खजाना खोजने के लिए पेजरैंक के तेज़, सिद्ध उपकरणों का उपयोग करें।"

यह कनेक्शन शोधकर्ताओं को वेब रैंकिंग के लिए डिज़ाइन किए गए तेज़ एल्गोरिदम की विशाल लाइब्रेरी का उपयोग जटिल निर्णय लेने वाली समस्याओं (रोबोटिक्स, अर्थशास्त्र और AI में) को हल करने के लिए करने की अनुमति देता है, जिससे वे बहुत तेज़ हो सकते हैं।

यहाँ अव्राचेनकोव, ग्रेगोरिस और लिटवाक के शोध पत्र "Linking PageRank, Time Reversal, and Policy Evaluation" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र मार्कोव निर्णय प्रक्रियाओं (MDPs) में पॉलिसी इवैल्यूएशन (Policy Evaluation) की कम्प्यूटेशनल बाधाओं को संबोधित करता है। एक निश्चित पॉलिसी $\pi$ के लिए, लक्ष्य वैल्यू फंक्शन $v_\pi$ की गणना करना है, जो प्रत्येक अवस्था (state) से अपेक्षित संचयी डिस्काउंटेड रिवॉर्ड (expected cumulative discounted reward) को दर्शाता है।

वर्तमान चुनौती: बड़े पैमाने की समस्याओं में, स्टेट स्पेस विशाल होता है, और ट्रांजिशन मैट्रिक्स अक्सर स्पार्स (sparse) और नॉन-सिमेट्रिक (non-symmetric) होता है। मानक विधियों (जैसे, गॉस-सीडेल, प्रायोरिटाइज्ड स्वीपिंग) का उपयोग करके बेलमैन समीकरण (एक लीनियर सिस्टम) को हल करना कम्प्यूटेशनल रूप से महंगा हो सकता है।
समानांतर क्षेत्र: नेटवर्क साइंस में, पेजरैंक (PageRank) विशाल ग्राफ पर रैंडम वॉक विद रीस्टार्ट्स (random walks with restarts) के स्टेशनरी डिस्ट्रीब्यूशन को कंप्यूट करने की एक अत्यधिक अनुकूलित विधि है।
मुख्य प्रश्न: क्या पॉलिसी इवैल्यूशन की समस्या को पेजरैंक गणना के साथ गणितीय रूप से मैप किया जा सकता है, जिससे MDPs के लिए कुशल पेजरैंक सॉल्वर का उपयोग किया जा सके?

2. कार्यप्रणाली (Methodology)

लेखक एक टाइम-रिवर्स्ड (time-reversed) मार्कोव चेन के पेजरैंक वेक्टर और एक डिस्उंटेड MDP के वैल्यू फंक्शन के बीच एक कठोर गणितीय संबंध स्थापित करते हैं।

अ. इररेड्यूसिबल (Irreducible) MDPs (मुख्य पत्राचार)

एक इररेड्यूसिबल पॉलिसी-प्रेरित मार्कोव चेन के लिए जिसका ट्रांजिशन मैट्रिक्स $P_\pi$ , स्टेशनरी डिस्ट्रीब्यूशन $\mu$ , डिस्काउंट फैक्टर $\gamma$ , और रिवॉर्ड वेक्टर $r$ है:

टाइम रिवर्शल (Time Reversal): लेखक टाइम-रिवर्स्ड ट्रांजिशन मैट्रिक्स $P^*_\pi = D^{-1} P_\pi^\top D$ को परिभाषित करते हैं, जहाँ $D = \text{diag}(\mu)$ है।
पैरामीटर मैपिंग:
- MDP में डिस्काउंट फैक्टर $\gamma$ , पेजरैंक में टेलीपोर्टेशन पैरामीटर (रीस्टार्ट प्रोबेबिलिटी) के अनुरूप है।
- रिवॉर्ड वेक्टर $r$ , पेजरैंक समस्या के लिए रीस्टार्ट डिस्ट्रीब्यूशन $u$ को निर्धारित करता है, जिसे $u(s) \propto r(s)\mu(s)$ के रूप में परिभाषित किया गया है।
परिणाम: वैल्यू फंक्शन $v_\pi(s)$ , टाइम-रिवर्स्ड चेन के पेजरैंक वेक्टर $w(s)$ के समानुपाती होता है:
$v_\pi(s) = \frac{\langle r \rangle_\mu}{1 - \gamma} \frac{w(s)}{\mu(s)}$
जहाँ $\langle r \rangle_\mu$ स्टेशनरी डिस्ट्रीब्यूशन के तहत अपेक्षित रिवॉर्ड है।

ब. सामान्य MDPs (विघटन प्रमेय/Decomposition Theorem)

वास्तविक दुनिया के MDPs अक्सर ट्रांजिएंट (transient) और रिकरेंट (recurrent) क्लासेस वाले रिड्यूसिबल (reducible) चेन्स होते हैं। लेखक एक विघटन प्रमेय सिद्ध करते हैं:

रिकरेंट क्लासेस: स्टेशनरी डिस्ट्रीब्यूशन का उपयोग करके इररेड्यूसिबल केस की तरह ही वैल्यू फंक्शन की सटीक गणना की जाती है।
ट्रांजिएंट क्लासेस: चूंकि ट्रांजिएंट चेन्स में स्टेशनरी डिस्ट्रीब्यूशन नहीं होता है, इसलिए लेखक क्वासी-स्टेशनरी डिस्ट्रीब्यूशन (QSD) और डूब $h$ -ट्रांसफॉर्म (Doob $h$ -transforms) का उपयोग करते हैं।
- वे एक ट्रांजिएंट क्लास के सब-स्टोकेस्टिक ट्रांजिशन मैट्रिक्स को डूब ट्रांसफॉर्म के माध्यम से एक स्टोकेस्टिक मैट्रिक्स में बदलते हैं।
- ट्रांजिएंट क्लास पर वैल्यू फंक्शन को एक टाइम-रिवर्स्ड डूब-ट्रांसफॉर्मेड चेन पर पेजरैंक समस्या के रूप में व्यक्त किया जाता है, जहाँ टेलीपोर्टेशन पैरामीटर $\gamma \lambda$ (जहाँ $\lambda$ ट्रांजिएंट सबमैट्रिक्स का स्पेक्ट्रल रेडियस है) बन जाता है।

स. अनडिस्काउंटेड (Undiscounted) MDPs

यह ढांचा टर्मिनल (एब्जॉर्बिंग) अवस्थाओं वाले अनडिस्काउंटेड MDPs ( $\gamma=1$ ) तक विस्तारित है। इस सीमा में, पेजरैंक फॉर्मूलेशन वैध रहता है, जिसमें टेलीपोर्टेशन पैरामीटर ट्रांजिएंट डायनेमिक्स के स्पेक्ट्रल गुणों द्वारा निर्धारित होता है।

3. मुख्य योगदान (Key Contributions)

सैद्धांतिक एकीकरण: यह पेपर टाइम रिवर्शल के माध्यम से पॉलिसी इवैल्यूएशन (हल करना: $(I - \gamma P)v = r$ ) और पेजरैंक (हल करना: $w = \gamma w P^* + (1-\gamma)u$ ) के बीच एक औपचारिक द्वैत (duality) स्थापित करता है।
सामान्य विघटन: यह एक सामान्य प्रमेय प्रदान करता है जो किसी भी अर्थों में (रिड्यूसिबल और ट्रांजिएंट मामलों सहित) मनमाने परिमित (finite) MDPs के लिए पॉलिसी इवलेशन को स्वतंत्र पेजरैंक समस्याओं के संग्रह में बदल देता है।
एल्गोरिद्मिक पुनरुद्देश्य (Algorithmic Repurposing): यह प्रदर्शित करता है कि स्केलेबल पेजरैंक एल्गोरिदम (जैसे, पावर इटरेशन, कोऑर्डिनेट अपडेट्स, मोंटे कार्लो) का व्यापक पुस्तकालय सीधे बेलमैन समीकरणों को हल करने के लिए उपयोग किया जा सकता है।
संख्यात्मक सत्यापन: लेखक बड़े ग्राफों (प्रेफरेंशियल अटैचमेंट, एर्डोस-रेनी, और 2D ग्रिड्स के साथ $10^5$ नोड्स) पर एक "स्टिकी रैंडम वॉक" कंट्रोल समस्या के लिए RLGL (Red-Light-Green-Light) एल्गोरिदम—जो एक अत्याधुनिक कोऑर्डिनेट-अपडेट पेजरैंक सॉल्वर है—को लागू करते हैं।

4. परिणाम (Results)

लेखकों ने बड़े ग्राफों पर एक "स्टिकी रैंडम वॉक" कंट्रोल समस्या पर संख्यात्मक प्रयोग किए।

तुलना: उन्होंने RLGL पेजरैंक सॉल्वर की तुलना मानक पॉलिसी इवैल्यूएशन विधियों: गॉस-सीडेल और प्रायोरिटाइजड स्वीपिंग से की।
प्रदर्शन:
- RLGL-GSD (GSD ह्यूरिस्टिक के साथ ग्रीन-लाइट-रेड-लाइट) एल्गोरिदम ने नॉर्मलाइज्ड इटरेशन्स (संचयी किनारे/edges प्रोसेस किए गए) के आधार पर अन्य विधियों की तुलना में बेलमैन रेसिडुअल को लगातार तेजी से कम किया।
- रिवर्सिबल सेटिंग्स (जहाँ टाइम रिवर्शल सरल है) में, पॉलिसी इवैल्यूएशन समस्या एक एकल पेजरैंक गणना में बदल गई, जिससे महत्वपूर्ण दक्षता लाभ दिखाई दिए।
निष्कर्ष: पेजरैंक-आधारित कोऑर्डिनेट सॉल्वर अत्यधिक प्रभावी बेलमैन सॉल्वर हैं, विशेष रूप से बड़े पैमाने, स्पार्स और रिवर्सिबल सिस्टम के लिए।

5. महत्व और निहितार्थ (Significance and Implications)

कम्प्यूटेशनल दक्षता: पॉलिसी इवैल्यूएशन को पेजरैंक समस्या के रूप में पुनर्गठित करके, शोधकर्ता डायनेमिक प्रोग्रामिंग और रिइन्फोर्समेंट लर्निंग को तेज करने के लिए नेटवर्क विश्लेषण में दशकों के अनुकूलन का लाभ उठा सकते हैं।
स्केलेबिलिटी: यह दृष्टिकोण उन विशाल स्टेट स्पेस के लिए विशेष रूप से आशाजनक है जहाँ पारंपरिक लीनियर सॉल्वर मेमोरी या कन्वर्जेंस स्पीड के मामले में संघर्ष करते हैं।
नए अनुसंधान मार्ग: यह पेपर भविष्य के कार्य के लिए कई मार्ग खोलता है:
- इरिवर्सिबल (Irreversible) MDPs (जहाँ टाइम रिवर्शल गैर-तुच्छ है) पर इन विधियों को लागू करना।
- आधुनिक डीप रिइन्फोर्समेंट लर्निंग फ्रेमवर्क में पेजरैंक-प्रेरित कोऑर्डिनेट विधियों को एकीकृत करना।
- यह जांचना कि क्या RL एजेंट एक्सप्लोरेशन और पॉलिसी इम्प्रूवमेंट को निर्देशित करने के लिए टाइम-रिवर्स्ड डायनेमिक्स को सीख सकते हैं।

संक्षेप में, यह शोध पत्र दो अलग-अलग क्षेत्रों (MDPs और नेटवर्क विश्लेषण) के बीच एक गहरा सैद्धांतिक संबंध प्रदान करता है और रिइन्फोर्समेंट लर्निंग में एक मौलिक सबरूटीन को हल करने के लिए एक उच्च-प्रदर्शन विकल्प पेश करता है।