तकनीकी सारांश: बजट और कवरेज बाधाओं के तहत इष्टतम नीति सीखना (Optimal Policy Learning)

1. समस्या विवरण

यह शोध पत्र उस समस्या को संबोधित करता है जहाँ एक निर्णय लेने वाले को कुल कल्याण (अपेक्षित लाभ) को अधिकतम करने के लिए आबादी के $N$ इकाइयों में एक सीमित संसाधन (उपचार) आवंटित करना होता है। यह आवंटन दो साथिक बाधाओं के अधीन है:

1. बजट बाधा (Budget Constraint): उपचार की कुल लागत एक निश्चित बजट $B$ (या प्रति-व्यक्ति बजट $C$) से अधिक नहीं होनी चाहिए।
2. न्यूनतम कवरेज बाधा (Minimum Coverage Constraint): आबादी का कम से कम $\rho$ हिस्सा उपचारित किया जाना चाहिए।

यह समस्या सार्वजनिक रोजगार प्रशिक्षण, चिकित्सा हस्तक्षेप, या सामाजिक लाभ जैसे संदर्भों में उत्पन्न होती है, जहाँ दक्षता (लाभ को अधिकतम करना) को व्यापक कवरेज (निष्पक्षता या राजनीतिक आवश्यकताओं) के साथ संतुलित करना आवश्यक होता है। मुख्य चुनौती यह है कि इष्टतम समाधान के लिए विकल्पों के एक घातीय (exponentially large) सेट ($2^N$) में से इकाइयों के एक उपसमुच्चय (subset) का चयन करना आवश्यक है, जो एक संयोजन अनुकूलन (combinatorial optimization) समस्या बनाता है जो कि NP-hard है।

2. कार्यप्रणाली और सैद्धांतिक ढांचा

2.1 प्राइमल-डुअल लक्षण वर्णन (Primal-Dual Characterization)

लेखक इस समस्या को 'पोटेंशियल आउटकम्स' फ्रेमवर्क के भीतर तैयार करते हैं। मान लीजिए कि $\tau(x)$ कंडीशनल एवरेज ट्रीटमेंट इफेक्ट (CATE) है और $c(x)$ किसी व्यक्ति $x$ के उपचार की लागत है। लक्ष्य $E[\pi(X)c(X)] \leq C$ और $E[\pi(X)] \geq \rho$ के अधीन $E[\pi(X)\tau(X)]$ को अधिकतम करना है।

लैग्रेंजियन डुअलिटी (Lagrangian duality) का उपयोग करते हुए, शोध पत्र स्थापित करता है कि इष्टतम नीति $\pi^*$ एक एफाइन थ्रेशोल्ड नियम (affine threshold rule) का रूप लेती है:
$$\pi^*(x) = \mathbb{1}\{ \tau(x) - \lambda^* c(x) + \nu^* \geq 0 \}$$
जहाँ:

• $\lambda^*$ बजट बाधा की शैडो प्राइस (shadow price) है।
• $\nu^*$ कवरेज बाधा की शैडो प्राइस है।
• यह नियम किसी व्यक्ति का उपचार तब करता है जब उसका लाभ, कवरेज शैडो प्राइस द्वारा समायोजित होने के बाद, बजट शैडो प्राइस द्वारा स्केल की गई लागत से अधिक होता है।

यह संरचना मानक बजट-बाधित समस्याओं (जो एक सरल अनुपात नियम $\tau(x)/c(x) \geq \lambda^*$ देती हैं) से भिन्न है क्योंकि कवरेज बाधा एक योगात्मक बदलाव ($\nu^*$) पेश करती है, जिससे एक विषम (heterogeneous) निर्णय सीमा निर्मित होती है।

2.2 नैपसैक समानता और LP रिलैक्सेशन (Knapsack Equivalence and LP Relaxation)

समस्या के अनुभवजन्य (empirical) समकक्ष को एक अतिरिक्त कार्डिनैलिटी बाधा के साथ 0-1 नैपसैक समस्या के समान दिखाया गया है।

• संयोजन रूप (Combinatorial Form): $\sum c_i d_i \leq nC$ और $\sum d_i \geq n\rho$ के अधीन $\sum \hat{\tau}_i d_i$ को अधिकतम करने के लिए एक बाइनरी वेक्टर $d \in \{0,1\}^n$ चुनें।
• लीनियर प्रोग्रामिंग (LP) रिलैक्सेशन: बाइनरी बाधा को $z_i \in [0,1]$ में बदल दिया जाता है।

एक महत्वपूर्ण सैद्धांतिक परिणाम इंटीग्रैलिटी गैप (integrality gap) (इष्टतम LP मान और इष्टतम 0-1 मान के बीच का अंतर) का विश्लेषण है। शोध पत्र सिद्ध करता है कि:

1. LP रिलैक्सेशन का कोई भी एक्सट्रीम पॉइंट समाधान अधिकतम दो भिन्नात्मक (fractional) घटकों को रखता है।
2. फलस्वरूप, पूर्ण इंटीग्रैलिटी गैप एक स्थिरांक $O(1)$ (विशेष रूप से $2V_{max}$) द्वारा सीमित है।
3. प्रति-व्यक्ति (per-capita) आधार पर, यह गैप $O(1/n)$ के रूप में स्पर्शोन्मुख रूप से (asymptotically) लुप्त हो जाता है। इसका तात्पर्य यह है कि LP रिलैक्सेशन, स्पर्शोन्मुख रूप से, असतत (discrete) इष्टतम समाधान के समान है।

2.3 कार्यान्वयन योग्य एल्गोरिदम

LP रिलैक्सेशन और एफाइन थ्रेशोल्ड संरचना के आधार पर, दो एल्गोरिदम प्रस्तावित किए गए हैं:

1. ग्रीडी-लैग्रेंजियन विद कवरेज (GLC):

   • तंत्र: बजट शैडो प्राइस $\lambda$ के ऊपर एक प्राइमल-डुअल खोज। एक निश्चित $\lambda$ के लिए, इकाइयों को स्कोर $a_i(\lambda) = \hat{\tau}_i - \lambda c_i$ द्वारा रेट किया जाता है।
   • प्रक्रिया: एल्गोरिदम कवरेज बाधा को लागू करने के लिए स्कोर के आधार पर शीर्ष $K_n$ (न्यूनतम आवश्यक) इकाइयों को उपचार सेट में शामिल करता है, और फिर बजट समाप्त होने तक धनात्मक स्कोर वाली शेष इकाइयों को लालची (greedily) तरीके से जोड़ता है। बजट बाधा को संतुष्ट करने के लिए द्वि-खंडन (bisection) के माध्यम से मल्टीप्लायर $\lambda$ को ट्यून किया जाता है।
   • जटिलता: $O(n \log n \cdot \log(1/\varepsilon))$।

2. रैंक-एंड-कट (RC):

   • तंत्र: एक गैर-पुनरावृत्ति (non-iterative), ह्यूरिस्टिक नियम जो केवल लागत-प्रभावशीलता अनुपात $s_i = \hat{\tau}_i / c_i$ द्वारा इकाइयों को रैंक करता है।
   • प्रक्रिया: इकाइयों को $s_i$ के आधार पर अवरोही क्रम में व्यवस्थित किया जाता है। एल्गोरिदम बजट और कवरेज दोनों बाधाओं को संतुष्ट करने वाला सबसे बड़ा व्यवहार्य प्रीफिक्स (prefix) चुनता है।
   • जटिलता: $O(n \log n)$।

3. मुख्य परिणाम

3.1 स्पर्शोन्मुख इष्टतमता (Asymptotic Optimality)

शोध पत्र स्थापित करता है कि GLC एल्गोरिदम स्पर्शोन्मुख रूप से इष्टतम (asymptotically optimal) है। चूंकि LP रिलैक्सेशन का प्रति-व्यक्ति इंटीग्रैलिटी गैप लुप्त हो जाता है, इसलिए कोई भी व्यवहार्य ग्रीडी नियम जो LP इष्टतम का अनुमान लगाता है (जैसा कि GLC करता है), मूल संयोजन समस्या के लिए भी स्पर्शोन्मुख रूप से इष्टतम होगा।

3.2 रैंक-एंड-कट (RC) का प्रदर्शन

शोध पत्र सटीक रूप से स्पष्ट करता है कि कब सरल RC नियम लगभग इष्टतम होता है। RC के सापेक्ष इष्टतम नीति का कल्याण नुकसान (welfare loss), RC द्वारा उपयोग किए जाने वाले स्थिर थ्रेशोल्ड और इष्टतम नीति के विषम एफाइन थ्रेशोल्ड के बीच विसंगति से संचालित होता है।

• समानता की स्थिति: RC लगभग इष्टतम है यदि:
  1. लागत समरूप है ($c(x) \approx c_0$), या
  2. कवरेज बाधा शिथिल (slack) है ($\nu^* \approx 0$)।
• गलत आवंटन की स्थिति: महत्वपूर्ण गलत आवंटन केवल तभी होता है जब लागत विषमता (cost heterogeneity) पर्याप्त हो और कवरेज बाधा बाध्यकारी (binding) हो ($\nu^* > 0$)। इस विशिष्ट शासन (regime) में, इष्टतम नीति की एफाइन सीमा को सरल अनुपात-आधारित रैंकिंग द्वारा पुनरुत्पादित नहीं किया जा सकता है, जिससे बजट के कारण उच्च-अनुपात वाली इकाइयों को बाहर रखा जाता है और कवरेज को पूरा करने के लिए निम्न-अनुपात वाली इकाइयों का उपचार किया जाता है।

3.3 मोंटे कार्लो साक्ष्य (Monte Carlo Evidence)

दो सिमुलेशन अध्ययन इसके सैद्धांतिक निष्कर्षों का समर्थन करते हैं:

1. GLC बनाम LP: जैसे-जैसे नमूना आकार $n$ बढ़ता है, सटीक इष्टतम समाधान (MILP) के सापेक्ष GLC का प्रति-व्यक्ति पछतावा (regret) तेजी से घटता है और निम्न स्तरों पर स्थिर हो जाता है। LP इंटीग्रैलिटी गैप भी तेजी से लुप्त हो जाता है, जो $O(1/n)$ अभिसरण (convergence) की पुष्टि करता है।
2. RC बनाम LP: चार शासनों (परिवर्तित लागत विषमता और कवरेज कसावट) में सिमुलेशन पुष्टि करते हैं कि RC और इष्टतम नीति के बीच गलत आवंटन सभी मामलों में नगण्य है, सिवाय उस मामले के जब लागत विषम होती है और कवरेज बाध्यकारी होती है। इस विशिष्ट "सबसे खराब मामले" (worst-case scenario) में, गलत आवंटन का क्षेत्र महत्वपूर्ण (~15%) है, जो इस सैद्धांतिक अंतःक्रिया प्रभाव को प्रमाणित करता है।

4. योगदान और महत्व

यह शोध पत्र तीन प्राथमिक योगदान देता है:

1. संरचनात्मक प्रतिनिधित्व: यह दो शैडो प्राइस वाले एफाइन थ्रेशोल्ड नियम के साथ नैपसैक-प्रकार की समस्या के रूप में बाधित नीति शिक्षण के संरचनात्मक लक्षण वर्णन को प्रदान करता है, जो बजट और कवरेज बाधाओं के बीच परस्पर क्रिया को स्पष्ट रूप से मॉडल करता है।
2. स्पर्शोन्मुख सटीकता: यह स्थापित करता है कि इस संयोजन समस्या का LP रिलैक्सेशन में $O(1)$ इंटीग्रैलिटी गैप है, जो रिलैक्स्ड और असतत समाधानों के बीच प्रति-व्यक्ति आधार पर स्पर्शोन्मुख समानता को सिद्ध करता है। यह सरल, स्केलेबल नियमों के उपयोग को न्यायसंगत बनाता है।
3. कार्यान्वयन और सीमाएं: यह दो स्केलेबल एल्गोरिदम (GLC और RC) का प्रस्ताव करता है और उनका विश्लेषण करता है। महत्वपूर्ण रूप से, यह उन सटीक संरचनात्मक स्थितियों की पहचान करता है जिनमें सरल, गैर-पुनरावृत्ति वाला RC नियम विफल हो जाता है। यह शोध पत्र सांख्यिकीय नीति शिक्षण और संयोजन अनुकूलन के बीच के अंतर को पाटता है, एक ऐसा ढांचा प्रदान करता है जो सैद्धांतिक रूप से सुदृढ़ और गणनात्मक रूप से स्केलेबल है।

इस कार्य का महत्व इष्टतम नीतियों के सैद्धांतिक लक्षण वर्णन से आगे बढ़कर कार्यान्वयन योग्य, स्केलेबल समाधान प्रदान करने की क्षमता में निहित है। यह स्पष्ट करता है कि हालांकि सरल लागत-प्रभावशीलता रैंकिंग अक्सर पर्याप्त होती है, नीति निर्माताओं को उन विशिष्ट संरचनात्मक स्थितियों के प्रति सचेत रहना चाहिए (विषम लागत + बाध्यकारी कवरेज) जहाँ ऐसे ह्यूरिस्टिक्स महत्वपूर्ण कल्याण हानि का कारण बन सकते हैं।