नीति मूल्यांकन के लिए उच्च-संभावना सैंपल जटिलताएँ रैखिक फलन अनुमान के साथ

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