2025-11-20T13:28:14.804433

Towards Blackwell Optimality: Bellman Optimality Is All You Can Get

Boone, Tuynman
Although average gain optimality is a commonly adopted performance measure in Markov Decision Processes (MDPs), it is often too asymptotic. Further incorporating measures of immediate losses leads to the hierarchy of bias optimalities, all the way up to Blackwell optimality. In this paper, we investigate the problem of identifying policies of such optimality orders. To that end, for each order, we construct a learning algorithm with vanishing probability of error. Furthermore, we characterize the class of MDPs for which identification algorithms can stop in finite time. That class corresponds to the MDPs with a unique Bellman optimal policy, and does not depend on the optimality order considered. Lastly, we provide a tractable stopping rule that when coupled to our learning algorithm triggers in finite time whenever it is possible to do so.
academic

Blackwell इष्टतमता की ओर: बेलमैन इष्टतमता ही आप प्राप्त कर सकते हैं

मौलिक जानकारी

  • पेपर ID: 2510.13476
  • शीर्षक: Towards Blackwell Optimality: Bellman Optimality Is All You Can Get
  • लेखक: Victor Boone (Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG & IRIT, Université de Toulouse), Adrienne Tuynman (Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189-CRIStAL)
  • वर्गीकरण: cs.LG (मशीन लर्निंग)
  • प्रकाशन समय: 15 अक्टूबर 2025 (arXiv प्रीप्रिंट)
  • पेपर लिंक: https://arxiv.org/abs/2510.13476v1

सारांश

यद्यपि औसत लाभ इष्टतमता मार्कोव निर्णय प्रक्रियाओं (MDPs) में एक सामान्य प्रदर्शन माप है, यह अक्सर अत्यधिक स्पर्शोन्मुख होती है। तत्काल हानि के माप को आगे जोड़ने से पूर्वाग्रह इष्टतमता की एक पदानुक्रम उत्पन्न होती है, जो Blackwell इष्टतमता तक जाती है। यह पेपर ऐसी इष्टतमता के क्रम की नीतियों को पहचानने की समस्या का अध्ययन करता है। इसके लिए, प्रत्येक क्रम के लिए, हम लुप्त होती त्रुटि संभावना के साथ एक सीखने वाला एल्गोरिदम बनाते हैं। इसके अलावा, हम MDP की श्रेणियों को चिन्हित करते हैं जहां पहचान एल्गोरिदम सीमित समय में रुक सकता है। यह श्रेणी अद्वितीय Bellman इष्टतम नीति वाले MDPs के अनुरूप है, और विचार की गई इष्टतमता के क्रम पर निर्भर नहीं करती है। अंत में, हम एक सुगम्य रोक नियम प्रदान करते हैं, जो हमारे सीखने वाले एल्गोरिदम के साथ युग्मित होने पर, जब भी संभव हो सीमित समय में ट्रिगर होता है।

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

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

इस पेपर द्वारा अध्ययन की गई मूल समस्या मार्कोव निर्णय प्रक्रियाओं में उच्च-क्रम इष्टतम नीतियों को सीखने की पहचान योग्यता समस्या है। विशेष रूप से:

  1. पारंपरिक औसत लाभ इष्टतमता की सीमाएं: MDP में, पारंपरिक औसत लाभ इष्टतमता केवल दीर्घकालीन स्पर्शोन्मुख प्रदर्शन पर ध्यान केंद्रित करती है, अल्पकालीन तत्काल पुरस्कार के महत्व को नजरअंदाज करती है।
  2. उच्च-क्रम इष्टतमता की पदानुक्रम: लाभ इष्टतमता से पूर्वाग्रह इष्टतमता तक, और फिर Blackwell इष्टतमता तक, एक संपूर्ण इष्टतमता पदानुक्रम बनता है, जहां प्रत्येक स्तर प्रदर्शन में अधिक सूक्ष्म अंतर पर विचार करता है।
  3. सीखने की कठिनाई: पेपर एक सरल लेकिन गहन उदाहरण (चित्र 1) के माध्यम से दिखाता है कि सबसे सरल परिस्थितियों में भी, उच्च-क्रम इष्टतम नीतियों को सीखना मौलिक कठिनाइयों का सामना करता है।

अनुसंधान प्रेरणा

पेपर की मूल प्रेरणा एक महत्वपूर्ण अवलोकन से उत्पन्न होती है: यहां तक कि केवल एक अज्ञात पैरामीटर वाले सरल MDP में भी, उच्च-क्रम इष्टतम नीतियों को सीखना असंभव हो सकता है। यह प्रतीत होने वाला विरोधाभासी घटना उच्च-क्रम इष्टतमता सीखने की आंतरिक कठिनाइयों को प्रकट करती है।

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

  1. मानक सीखने की विधियां विफल होती हैं: पारंपरिक अनुभवजन्य इष्टतम नीति चयन उच्च-क्रम इष्टतमता के तहत अब लागू नहीं होता है
  2. सांख्यिकीय परीक्षण की सीमाएं: पैरामीटर के सटीक मान (जैसे θ=0) को निर्धारित करने के लिए सांख्यिकीय परीक्षण के माध्यम से नहीं किया जा सकता है
  3. असंतुलन समस्या: पैरामीटर स्पेस में इष्टतम नीति सेट की असंतुलनता सीखने में कठिनाई का कारण बनती है

मूल योगदान

  1. सुसंगत एल्गोरिदम HOPE का निर्माण: प्रत्येक इष्टतमता क्रम n≥-1 के लिए, Higher Order Policy iteration Epsilonized (HOPE) एल्गोरिदम प्रस्तावित किया गया है, जिसमें लुप्त होती त्रुटि संभावना है।
  2. गैर-अपक्षयी MDP श्रेणी का संपूर्ण लक्षण वर्णन: सिद्ध किया गया है कि MDP गैर-अपक्षयी है (अर्थात्, पहचान एल्गोरिदम सीमित समय में रुक सकता है) यदि और केवल यदि इसमें अद्वितीय Bellman इष्टतम नीति है।
  3. अपक्षय पतन प्रमेय: सिद्ध किया गया है कि सभी इष्टतमता क्रमों (लाभ इष्टतमता से Blackwell इष्टतमता तक) की गैर-अपक्षयी MDP श्रेणियां पूरी तरह से समान हैं, यह एक आश्चर्यजनक परिणाम है।
  4. गणनीय रोक नियम प्रदान किया: एक सुगम्य रोक नियम दिया गया है, जो HOPE एल्गोरिदम को संभव होने पर सीमित समय में रोकने में सक्षम बनाता है।

विधि विस्तार

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

इनपुट: अज्ञात संचार MDP M = (Z, ν, p), जहां Z स्थिति-क्रिया जोड़ी स्पेस है, ν पुरस्कार फ़ंक्शन है, p संक्रमण कर्नेल है आउटपुट: n-क्रम इष्टतम नीति π ∈ Π*_n(M) लक्ष्य: पहचान एल्गोरिदम का निर्माण करें ताकि अनुशंसित नीति की त्रुटि संभावना 0 की ओर जाए

मूल एल्गोरिदम आर्किटेक्चर

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

इनपुट: वांछित इष्टतमता क्रम n ≥ -1
प्रारंभिकीकरण: t ← 0
लूप:
    1. अनुभवजन्य MDP M̂_t का निर्माण करें
    2. ε ← t^(-1/4) सेट करें
    3. ∏_s A_n(s) ← HOPI_{n,ε}(M̂_t) की गणना करें
    4. ∏_s A_n(s) में से कोई भी नीति अनुशंसित करें
    5. क्रिया को समान रूप से नमूना करें, पुरस्कार और अगली स्थिति का अवलोकन करें
    6. t ← t + 1

HOPI एल्गोरिदम का मूल विचार

HOPI उच्च-क्रम नीति पुनरावृत्ति का "epsilon-संस्करण" है, मुख्य नवाचार में शामिल हैं:

  1. सॉफ्ट argmax ऑपरेशन: सटीक Bellman समीकरण बाधा Δ^π_m(s,a) = 0 को Δ^π_m(s,a) ≤ ε में शिथिल करें
  2. दो-चरणीय नीति सुधार:
    • पहला चरण: पहले से ज्ञात m-1 क्रम इष्टतम क्रियाओं में m+1 क्रम सुधार खोजें
    • दूसरा चरण: m+2 क्रम इष्टतमता में आगे परिशोधन करें
  3. क्रमिक सटीकता नियंत्रण: ε_t = t^(-1/4) चुनें एल्गोरिदम की सुसंगतता सुनिश्चित करने के लिए

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

1. शोर के तहत नीति पुनरावृत्ति

पारंपरिक नीति पुनरावृत्ति को Bellman समीकरण को सटीक रूप से संतुष्ट करने की आवश्यकता होती है, लेकिन सीखने के वातावरण में यह असंभव है। HOPI शोर के वातावरण में एल्गोरिदम को सही तरीके से काम करने के लिए शिथिलता पैरामीटर ε को शुरू करके इसे संभव बनाता है।

2. विखंडन तकनीक (Shattering)

प्रस्ताव 5: किसी भी एकल-श्रृंखला Bellman इष्टतम नीति π और सटीकता ε > 0 के लिए, M' ∈ M मौजूद है जैसे कि d_∞(M,M') < ε और π M' की अद्वितीय लाभ इष्टतम नीति है।

यह तकनीक दो चरणों के माध्यम से लागू की जाती है:

  • पहले गैर-इष्टतम क्रियाओं को दंडित करके π को अद्वितीय Bellman इष्टतम नीति बनाएं
  • फिर π को अद्वितीय लाभ इष्टतम नीति बनाने के लिए ergodic परिवर्तन के माध्यम से

3. रोक नियम डिजाइन

थ्रेसहोल्ड फ़ंक्शन परिभाषित करें:

β(M) := min{d_min(Δ*)/((1+4α)(2+sp(b*))), 1/α}

जहां α सबसे खराब पहुंच समय है, यह थ्रेसहोल्ड पड़ोस त्रिज्या का सटीक माप प्रदान करता है।

सैद्धांतिक परिणाम

मुख्य प्रमेय

प्रमेय 1 (सुसंगतता)

सभी n ≥ -1 के लिए, HOPE(n) एल्गोरिदम Π*_n के लिए सुसंगत है।

प्रमेय 2 (गैर-अपक्षय लक्षण वर्णन)

M को Π*_n(M) के संबंध में गैर-अपक्षयी कहा जाता है यदि और केवल यदि M में अद्वितीय Bellman इष्टतम नीति है।

अनुपात 3 (अपक्षय पतन)

Π_{-1}, Π0, Π_1, ..., Π∞ के संबंध में अपक्षयी मॉडल सेट पूरी तरह से समान हैं।

प्रमाण रणनीति

गैर-अपक्षय की आवश्यकता (प्रमेय 4)

यदि M गैर-अपक्षयी है, तो एक नीति π ∈ Π*(M) मौजूद है जो M के पड़ोस में इष्टतम रहती है। प्रमाण एल्गोरिदम निर्णय की निरंतरता का उपयोग करता है।

पर्याप्तता (प्रमेय 10-11)

स्पष्ट रोक नियम और विश्वास अंतराल के निर्माण के माध्यम से, सिद्ध करें कि अद्वितीय Bellman इष्टतम नीति वाले MDP वास्तव में गैर-अपक्षयी हैं।

प्रायोगिक सेटअप और परिणाम

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

पेपर मुख्य रूप से एक सैद्धांतिक कार्य है, कठोर गणितीय प्रमाण के माध्यम से सभी मुख्य परिणामों को सत्यापित करता है। मुख्य सत्यापन में शामिल हैं:

  1. एल्गोरिदम सही्तता: सिद्ध करें कि HOPI शोर-मुक्त परिस्थितियों में सही इष्टतम नीति सेट लौटाता है
  2. सुसंगतता गारंटी: सिद्ध करें कि HOPE एल्गोरिदम की त्रुटि संभावना वास्तव में 0 की ओर जाती है
  3. रोक नियम प्रभावशीलता: सिद्ध करें कि प्रस्तावित रोक नियम वास्तव में सीमित समय में ट्रिगर होता है

जटिलता विश्लेषण

  • समय जटिलता: Bellman इष्टतम नीति की अद्वितीयता निर्धारित करने की समय जटिलता O(|Z| + |S|^4) है
  • नमूना जटिलता: यद्यपि पेपर सटीक नमूना जटिलता सीमा नहीं देता है, यह सिद्ध करता है कि गैर-अपक्षयी परिस्थितियों में एल्गोरिदम अवश्य अभिसरण करता है

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

इष्टतम भुजा पहचान

बहु-भुजा डाकू समस्या में इष्टतम भुजा पहचान समस्या से संबंधित, लेकिन MDP सेटिंग में स्थिति निर्भरता समस्या को अधिक जटिल बनाती है।

औसत पुरस्कार सुदृढ़ करण सीखना

(ε,δ)-PAC सेटिंग में लाभ इष्टतम नीतियों की पहचान करने पर हाल के कार्य, लेकिन ये कार्य मुख्य रूप से अनुमानित इष्टतमता पर ध्यान केंद्रित करते हैं न कि सटीक इष्टतमता पर।

Blackwell इष्टतमता गणना

Grand-Clément और Petrik (2023) जैसे लोगों द्वारा छूट कारक के ऐतिहासिक परिभाषा के आधार पर Blackwell इष्टतम नीतियों की गणना जटिलता का अध्ययन।

निर्धारक MDP में संबंधित परिणाम

Boone और Gaujal (2023) ने निर्धारक संक्रमण MDP में Blackwell इष्टतम नीतियों की सीखने की क्षमता का अध्ययन किया, यह पेपर इसे यादृच्छिक परिस्थितियों तक विस्तारित करता है।

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

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

  1. Bellman इष्टतमता मौलिक सीमा है: सभी उच्च-क्रम इष्टतमता की सीखने की क्षमता Bellman इष्टतमता की अद्वितीयता तक सीमित है
  2. अपक्षय की सार्वभौमिकता: विभिन्न इष्टतमता क्रमों की अपक्षयी MDP श्रेणियां पूरी तरह से समान हैं
  3. एल्गोरिदम की अस्तित्व: कठिनाइयों के बावजूद, सुसंगत एल्गोरिदम वास्तव में मौजूद हैं

सीमाएं

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

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

  1. PAC ढांचा विस्तार: अनुमानित इष्टतम नीतियों की सीखने का अध्ययन करें
  2. नमूना जटिलता विश्लेषण: सटीक नमूना जटिलता सीमा स्थापित करें
  3. एल्गोरिदम अनुकूलन: HOPE एल्गोरिदम के व्यावहारिक प्रदर्शन में सुधार करें

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

शक्तियां

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

कमजोरियां

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

प्रभाव

  1. सैद्धांतिक योगदान: सुदृढ़ करण सीखने के सिद्धांत के लिए महत्वपूर्ण नकारात्मक परिणाम प्रदान करता है
  2. विधि प्रेरणा: विखंडन तकनीक अन्य समस्याओं में अनुप्रयोग हो सकती है
  3. अनुसंधान दिशा: PAC सेटिंग के महत्व के लिए बाद के अनुसंधान को निर्देशित करता है

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

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

संदर्भ

पेपर सुदृढ़ करण सीखने और मार्कोव निर्णय प्रक्रियाओं के क्षेत्र के महत्वपूर्ण साहित्य का हवाला देता है, जिसमें शामिल हैं:

  • Puterman (1994): मार्कोव निर्णय प्रक्रियाओं की शास्त्रीय पाठ्यपुस्तक
  • Blackwell (1962): Blackwell इष्टतमता की मूल परिभाषा
  • Kaufmann et al. (2016): इष्टतम भुजा पहचान की जटिलता सिद्धांत
  • Boone and Gaujal (2023): निर्धारक MDP में Blackwell इष्टतमता की सीखने की क्षमता

यह पेपर कठोर सैद्धांतिक विश्लेषण के माध्यम से सुदृढ़ करण सीखने में एक मौलिक और गहन घटना को प्रकट करता है: उच्च-क्रम इष्टतमता की सीखने की कठिनाई पूरी तरह से Bellman इष्टतमता की संरचना द्वारा निर्धारित होती है। यह परिणाम न केवल महत्वपूर्ण सैद्धांतिक महत्व रखता है, बल्कि व्यावहारिक एल्गोरिदम डिजाइन के लिए भी महत्वपूर्ण मार्गदर्शन प्रदान करता है।