Optimal strategies in Markov decision processes with finitely additive evaluations

यहाँ शोध पत्र "Optimal strategies in Markov decision processes with finitely additive evaluations" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र परिमित अवस्था (finite state) और क्रिया स्थानों (action spaces) वाले अनंत-क्षितिज मार्कोव निर्णय प्रक्रियाओं (Infinite-Horizon Markov Decision Processes - MDPs) की जांच करता है। मुख्य नवीनता उस मूल्यांकन मानदंड (evaluation criterion) में निहित है जिसका उपयोग निर्णय लेने वाले द्वारा किया जाता है। मानक MDPs के विपरीत, जो डिस्काउंटेड योग (discounted sums) या दीर्घकालिक औसत पुरस्कारों का उपयोग करते हैं, यह शोध पत्र एक डिफ्यूज़ चार्ज (diffuse charge) (प्राकृतिक संख्याओं $\mathbb{N}$ के सेट पर एक फाइनाइटली एडिटिव प्रोबेबिलिटी मेजर, जहाँ प्रत्येक सिंगलटन का माप शून्य होता है) का उपयोग करके अपेक्षित चरण पुरस्कारों (expected stage rewards) के अनंत प्रवाह के एकत्रीकरण पर विचार करता है।

केंद्रीय शोध प्रश्न यह है: क्या ऐसे MDPs में एक इष्टतम रणनीति (optimal strategy) हमेशा अस्तित्व में होती है?

• पूर्ववर्ती कार्य (नेमन, 2023) ने स्थापित किया कि यदि एकत्रीकरण चार्ज "टाइम वैल्यू ऑफ मनी सिद्धांत" (धैर्यवान मूल्यांकन से संबंधित एक विशिष्ट स्थिति) का पालन करता है, तो एक शुद्ध स्थिर इष्टतम रणनीति (pure stationary optimal strategy) मौजूद होती है।
• लेखक यह पूछते हैं कि क्या अस्तित्व का यह परिणाम "टाइम वैल्यू ऑफ मनी" की बाधा के बिना, किसी भी डिफ्यूज़ चार्ज के लिए लागू होता है।

2. कार्यप्रणाली और ढांचा (Methodology and Framework)

2.1 गणितीय पूर्ववृत्त (Mathematical Preliminaries)

• चार्जेस (Charges): लेखक $\mathbb{N}$ पर फाइनाइटली एडिटिव मेजर (charges) के सिद्धांत का उपयोग करते हैं। एक चार्ज $\mu$ एक मैपिंग $\mu: 2^\mathbb{N} \to [0,1]$ है जो फाइनाइटली एडिटिव है।
• डिफ्यूज़ चार्जेस (Diffuse Charges): एक चार्ज "डिफ्यूज़" है यदि $\mu(\{n\}) = 0$ सभी $n \in \mathbb{N}$ के लिए हो।
• एकीकरण (Integration): पेऑफ (payoff) को चार्ज $\mu$ के सापेक्ष अपेक्षित पुरस्कारों के अभिन्न (integral) के रूप में परिभाषित किया गया है:
  $$u_\mu(\sigma) = \int_{t \in \mathbb{N}} \mathbb{E}_\sigma[r_t] \, \mu(dt)$$
• टोपोलॉजी (Topology): चार्जेस के सेट $\Delta_f$ को पॉइंटवाइज कन्वर्जेंस की टोपोलॉजी के साथ सुसज्जित किया गया है। यह स्थान कॉम्पैक्ट और हाउसडॉर्फ (Hausdorff) है लेकिन मेट्रिजेबल (metrizable) नहीं है। चार्जेस के अनुक्रमों के एक्युमुलेशन पॉइंट्स (accumulation points) के माध्यम से काउंटर-एग्जांपलल (counterexample) बनाने के लिए यह टोपोलॉजिकल गुण अत्यंत महत्वपूर्ण है।

2.2 मॉडल (The Model)

• MDP संरचना: परिमित अवस्था स्थान $S$, परिमित क्रिया स्थान $A(s)$, सीमित पुरस्कार $r(s,a)$, और ट्रांजिशन प्रोबेबिलिटी $p(s'|s,a)$।
• रणनीतियाँ (Strategies): लेखक शुद्ध रणनीतियों (pure strategies) (निश्चयात्मक विकल्प) और रैंडमाइज्ड/व्यवहारात्मक रणनीतियों (randomized/behavioral strategies) दोनों पर विचार करते हैं।
• पेऑफ (Payoff): MDP का मान $v_\mu = \sup_{\sigma} u_\mu(\sigma)$ है। एक रणनीति इष्टतम (optimal) तब होती है जब वह इस सुप्रीमकम (supremum) को प्राप्त करती है।

3. मुख्य योगदान और परिणाम (Key Contributions and Results)

3.1 मौजूदा साहित्य की समीक्षा (नेमन, 2023)

यह शोध पत्र पहले नेमन के परिणाम को याद दिलाता है: यदि एकत्रीकरण चार्ज "टाइम वैल्यू ऑफ मनी सिद्धांत" (जो "पेशनट वैल्यूएशन" के समकक्ष है) का पालन करता है, तो एक शुद्ध स्थिर रणनीति (pure stationary strategy) मौजूद होती है जो सभी ऐसे चार्जेस के लिए एक साथ इष्टतम होती है। यह इस विशिष्ट उप-वर्ग के चार्जेस में मजबूती (robustness) को दर्शाता है।

3.2 मुख्य परिणाम: इष्टतम रणनीतियों का गैर-अस्तित्व (Theorem 3)

प्राथमिक योगदान सामान्य डिफ्यूज़ चार्जेस के लिए अस्तित्व संबंधी प्रश्न का एक नकारात्मक उत्तर है। लेखक एक विशिष्ट काउंटर-एग्जांपलल निर्मित करते हैं, जिसे "इवन-ओर-ऑड MDP" (Even-or-Odd MDP) कहा जाता है, जिसे एक "सूक्ष्मता से निर्मित" एकत्रीकरण चार्ज $\mu$ के साथ जोड़ा गया है, जिससे कोई भी इष्टतम रणनीति अस्तित्व में नहीं रहती, न ही शुद्ध और न ही रैंडमाइज्ड।

काउंटर-एग्जांपलल निर्माण:

1. MDP:

   • अवस्थाएँ (States): $\{1, 2, 3\}$। प्रारंभिक अवस्था: 1।
   • अवस्था 1 में क्रियाएँ: $T$ (Top) और $B$ (Bottom)। अवस्थाओं 2 और 3 में केवल एक ही क्रिया है।
   • ट्रांजिशन: $T$ अवस्था 2 की ओर ले जाता है; $B$ अवस्था 3 की ओर ले जाता है। दोनों 2 और 3 निश्चित रूप से वापस 1 पर ट्रांजिशन करते हैं।
   • पुरस्कार (Rewards):
     • अवस्था 1, क्रिया $T$: पुरस्कार 1।
     • अवस्था 1, क्रिया $B$: पुरस्कार 0।
     • अवस्था 2: पुरस्कार 0।
     • अवस्था 3: पुरस्कार 1।
   • गतिकी (Dynamics): प्रक्रिया अवस्था 1 और अवस्था 2 या 3 के बीच चक्रित (cycle) होती है। निर्णय लेने वाला प्रभावी रूप से प्रत्येक विषम (odd) चरण (अवस्था 1) पर यह चुनता है कि अभी 1 का पुरस्कार प्राप्त करे और अगले चरण में 0, या अभी 0 प्राप्त करे और अगले चरण में 1।

2. एकत्रीकरण चार्ज ($\mu$):

   • चार्ज को एक कॉनवेक्स कॉम्बिनेशन (convex combination) के रूप में निर्मित किया गया है: $\mu = \frac{1}{2}\mu_0 + \frac{1}{2}\mu^*$।
   • $\mu_0$: विषम संख्याओं ($E_0$) पर केंद्रित है। यह क्रिया $T$ को बार-बार चुनने का पक्ष लेता है।
   • $\mu^*$: चार्जेस के एक अनुक्रम $\mu_n$ के एक एक्युमुलेशन पॉइंट के रूप में निर्मित है। प्रत्येक $\mu_n$ सेट $E_n = \{k \cdot 2^n : k \in \mathbb{N}\}$ पर केंद्रित है।
   • द्वंद्व (The Conflict):
     • $\mu_0$ के तहत पेऑफ को अधिकतम करने के लिए, एजेंट को आवृत्ति 1 के साथ $T$ चुनना चाहिए।
     • $\mu^*$ के तहत पेऑफ को अधिकतम करने के लिए, एजेंट को $B$ को सकारात्मक आवृत्ति के साथ चुनना चाहिए (विशेष रूप से, $E_n$ पर $T$ से बचना चाहिए)।
     • चार्ज $\mu^*$, प्रत्येक $E_n$ को 1 का माप देता है, फिर भी सभी $E_n$ का प्रतिच्छेदन (intersection) खाली है। यह एक ऐसी स्थिति बनाता है जहाँ एजेंट सैद्धांतिक अधिकतम को प्राप्त करने के लिए $\mu_0$ और $\mu^*$ दोनों की आवश्यकताओं को एक साथ पूरा नहीं कर सकता।

3. गैर-अस्तित्व का प्रमाण:

   • दावा 1: MDP का मान $v_\mu = 1$ है। लेखक दिखाते हैं कि किसी भी $\epsilon > 0$ के लिए, एक रणनीति $\sigma_n$ मौजूद है जो $1 - \epsilon$ का पेऑफ प्राप्त करती है।
   • दावा 2: कोई भी रणनीति ठीक 1 प्राप्त नहीं करती है।
     • यदि कोई रणनीति 1 का पेऑफ देती है, तो अपेक्षित पुरस्कार $> 0.5$ वाले चरणों का सेट $\mu$-माप 1 होना चाहिए।
     • इसका अर्थ है कि उस सेट का $\mu_0$ और $\mu^*$ दोनों के तहत माप 1 होना चाहिए।
     • हालाँकि, चार्ज $\mu^*$ के संरचनात्मक गुण (जो $E_n$ के अनुक्रम से प्राप्त हुए हैं) और MDP की निश्चयात्मक प्रकृति (जहाँ $r_t + r_{t+1} = 1$) एक तार्किक विरोधाभास पैदा करते हैं। एक सेट $\mu_0$ के तहत माप 1 (जिसके लिए $T$ की उच्च आवृत्ति आवश्यक है) और $\mu^*$ के तहत माप 1 (जिसके लिए विशिष्ट बचाव पैटर्न आवश्यक है) को एक साथ संतुष्ट नहीं कर सकता, बिना MDP की गतिकी की सीमाओं का उल्लंघन किए।
   • निष्कर्ष: चूँकि सुप्रीमकम 1 है लेकिन कभी प्राप्त नहीं होता, इसलिए कोई इष्टतम रणनीति मौजूद नहीं है।

3.3 अतिरिक्त निष्कर्ष

• स्थिर बनाम शुद्ध रणनीतियाँ (Stationary vs. Pure Strategies): यह शोध पत्र एक उदाहरण (उदाहरण 4) प्रदान करता है जो दिखाता है कि भले ही किसी विशिष्ट चार्ज के लिए एक इष्टतम शुद्ध रणनीति मौजूद हो, वह स्थिर (stationary) नहीं हो सकती है।
• गैर-डिफ्यूज़ चार्जेस (Non-Diffuse Charges): लेखक उन चार्जेस पर संक्षिप्त चर्चा करते हैं जो पूरी तरह से डिफ्यूज़ नहीं हैं (अर्थात, उनमें एक एटम/atom है)। वे दिखाते हैं कि यदि चार्ज में धनात्मक भार के साथ एक काउंटेबली एडिटिव घटक है, तो भी इष्टतम रणनीति का अस्तित्व विफल हो सकता है (उदाहरण 5), विशेष रूप से डिस्काउंटेड और औसत पुरस्कारों को मिलाने पर।

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

1. फाइनाइटली एडिटिव मेजर की मौलिक सीमा: यह शोध पत्र प्रदर्शित करता है कि जब मूल्यांकन मानदंड एक सामान्य फाइनाइटली एडिटिव मेजर पर निर्भर करता है, तो MDPs में इष्टतम रणनीतियों का अस्तित्व सुनिश्चित नहीं होता है। यह मानक MDP सिद्धांत (डिस्काउंटेड या काउंटेबली एडिटिव एवरेज) के बिल्कुल विपरीत है जहाँ इष्टतम रणनीतियाँ (अक्सर स्थिर) गारंटीकृत होती हैं।
2. नेमन के परिणाम की मजबूती: यह नेमन (2023) के प्रमेय की सीमा को स्पष्ट करता है। "टाइम वैल्यू ऑफ मनी सिद्धांत" केवल एक तकनीकी सुविधा नहीं है; यह इस सामान्य सेटिंग में इष्टतम रणनीतियों की गारंटी के लिए एक आवश्यक शर्त है।
3. टोपोलॉजिकल सूक्ष्मताएँ (Topological Nuances): निर्माण चार्जेस के गैर-मेट्रिजेबल स्पेस पर बहुत अधिक निर्भर करता है। यह इस बात पर प्रकाश डालता है कि कैसे चार्जेस के स्पेस की कॉम्पैक्टनेस "लिमिट" चार्जेस के अस्तित्व की अनुमति देती है जो मानक मेजर की तुलना में विरोधाभासी व्यवहार करते हैं, जिससे इष्टतम नीतियों का गैर-अस्तित्व होता है।
4. सैद्धांतिक गहराई: यह परिणाम निर्णय सिद्धांत (decision theory) के मॉडलों के लिए एक चेतावनी के रूप में कार्य करता है जो गैर-मानक मेजरों का उपयोग करके अनंत क्षितिज को एकत्रित करते हैं, यह दिखाते हुए कि डायनेमिक प्रोग्रामिंग संदर्भों में "सुप्रीमकम" हमेशा "अधिकतम" (maximum) का संकेत नहीं देता है।

संक्षेप में, यह शोध पत्र MDPs के सिद्धांत में एक महत्वपूर्ण खुले प्रश्न को हल करता है, यह सिद्ध करते हुए कि जब पेऑफ का मूल्यांकन एक मनमाने डिफोज फाइनाइटली एडिटिव चार्ज के माध्यम से किया जाता है, तो इष्टतम रणनीतियाँ आवश्यक रूप से मौजूद नहीं होती हैं, जो मेजर थ्योरी और डायनेमिक ऑप्टिमाइजेशन के बीच एक कठोर काउंटर-एग्जांपलल प्रदान करता है।