2025-11-15T23:58:12.055440

An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPs

Liu, Wei, Zimmert
We study decision making with structured observation (DMSO). Previous work (Foster et al., 2021b, 2023a) has characterized the complexity of DMSO via the decision-estimation coefficient (DEC), but left a gap between the regret upper and lower bounds that scales with the size of the model class. To tighten this gap, Foster et al. (2023b) introduced optimistic DEC, achieving a bound that scales only with the size of the value-function class. However, their optimism-based exploration is only known to handle the stochastic setting, and it remains unclear whether it extends to the adversarial setting. We introduce Dig-DEC, a model-free DEC that removes optimism and drives exploration purely by information gain. Dig-DEC is always no larger than optimistic DEC and can be much smaller in special cases. Importantly, the removal of optimism allows it to handle adversarial environments without explicit reward estimators. By applying Dig-DEC to hybrid MDPs with stochastic transitions and adversarial rewards, we obtain the first model-free regret bounds for hybrid MDPs with bandit feedback under several general transition structures, resolving the main open problem left by Liu et al. (2025). We also improve the online function-estimation procedure in model-free learning: For average estimation error minimization, we refine the estimator in Foster et al. (2023b) to achieve sharper concentration, improving their regret bounds from $T^{3/4}$ to $T^{2/3}$ (on-policy) and from $T^{5/6}$ to $T^{7/9}$ (off-policy). For squared error minimization in Bellman-complete MDPs, we redesign their two-timescale procedure, improving the regret bound from $T^{2/3}$ to $\sqrt{T}$. This is the first time a DEC-based method achieves performance matching that of optimism-based approaches (Jin et al., 2021; Xie et al., 2023) in Bellman-complete MDPs.
academic

एक सुधारित मॉडल-मुक्त निर्णय-अनुमान गुणांक और प्रतिकूल MDPs में अनुप्रयोग

मूल जानकारी

  • पेपर ID: 2510.08882
  • शीर्षक: An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPs
  • लेखक: Haolin Liu (University of Virginia), Chen-Yu Wei (University of Virginia), Julian Zimmert (Google Research)
  • वर्गीकरण: cs.LG (मशीन लर्निंग)
  • प्रकाशन समय: अक्टूबर 2025
  • पेपर लिंक: https://arxiv.org/abs/2510.08882v1

सारांश

यह पेपर संरचित अवलोकन निर्णय निर्माण समस्या (DMSO) का अध्ययन करता है। पूर्ववर्ती कार्य ने निर्णय-अनुमान गुणांक (DEC) के माध्यम से DMSO की जटिलता को चिह्नित किया, लेकिन पश्चाताप की ऊपरी और निचली सीमाओं के बीच मॉडल वर्ग के आकार से संबंधित एक अंतराल छोड़ा। Foster et al. (2023b) ने इस अंतराल को कम करने के लिए आशावादी DEC पेश किया, केवल मूल्य फ़ंक्शन वर्ग के आकार से संबंधित सीमाएं प्राप्त कीं। हालांकि, आशावाद-आधारित अन्वेषण केवल स्टोकेस्टिक वातावरण को संभाल सकता है, और क्या इसे प्रतिकूल वातावरण तक विस्तारित किया जा सकता है यह स्पष्ट नहीं है।

यह पेपर Dig-DEC प्रस्तावित करता है, एक मॉडल-मुक्त DEC विधि जो आशावाद को हटाता है और विशुद्ध रूप से सूचना लाभ द्वारा संचालित अन्वेषण करता है। Dig-DEC हमेशा आशावादी DEC से कम या बराबर होता है, और विशेष मामलों में काफी छोटा हो सकता है। महत्वपूर्ण रूप से, आशावाद को हटाना इसे स्पष्ट पुरस्कार अनुमानक के बिना प्रतिकूल वातावरण को संभालने में सक्षम बनाता है। Dig-DEC को स्टोकेस्टिक संक्रमण और प्रतिकूल पुरस्कार के साथ हाइब्रिड MDP पर लागू करके, विभिन्न सामान्य संक्रमण संरचनाओं के तहत बैंडिट प्रतिक्रिया के साथ हाइब्रिड MDP के लिए पहली मॉडल-मुक्त पश्चाताप सीमा प्राप्त की गई है।

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

  1. समस्या को हल करना: मौजूदा निर्णय-अनुमान गुणांक (DEC) ढांचे में मॉडल वर्ग के आकार और मूल्य फ़ंक्शन वर्ग के आकार के बीच अंतराल है, और आशावाद-आधारित विधियां प्रतिकूल वातावरण को प्रभावी ढंग से संभाल नहीं सकती हैं।
  2. समस्या की महत्ता:
    • ऑनलाइन निर्णय निर्माण सुदृढ़ शिक्षा की मूल समस्या है
    • व्यावहारिक अनुप्रयोगों में अक्सर आंशिक रूप से स्टोकेस्टिक, आंशिक रूप से प्रतिकूल हाइब्रिड वातावरण का सामना करना पड़ता है
    • मौजूदा विधियों में सैद्धांतिक गारंटी और व्यावहारिक प्रदर्शन के बीच अंतराल है
  3. मौजूदा विधियों की सीमाएं:
    • Foster et al. के मॉडल को DEC/E2D पर आधारित log|M| की मॉडल अनुमान लागत वहन करनी पड़ती है
    • आशावादी DEC जटिलता में सुधार करता है, लेकिन आशावादी सिद्धांत पर निर्भर है, प्रतिकूल सेटिंग को संभाल नहीं सकता है
    • Liu et al. (2025) की हाइब्रिड MDP विधि केवल पूर्ण सूचना प्रतिक्रिया को संभाल सकती है, बैंडिट स्थिति अभी भी खुली समस्या है
  4. अनुसंधान प्रेरणा: एक एकीकृत ढांचा विकसित करना जो स्टोकेस्टिक वातावरण में मौजूदा परिणामों में सुधार कर सके और पहली बार हाइब्रिड MDP की बैंडिट प्रतिक्रिया को संभाल सके।

मुख्य योगदान

  1. Dig-DEC जटिलता माप प्रस्तुत करना: दोहरे सूचना लाभ निर्णय-अनुमान गुणांक पेश करना, आशावाद को हटाना, विशुद्ध रूप से सूचना लाभ द्वारा संचालित अन्वेषण
  2. एकीकृत सैद्धांतिक ढांचा: स्टोकेस्टिक और हाइब्रिड वातावरण दोनों को संभालने में सक्षम सामान्य एल्गोरिदम ढांचा निर्माण
  3. ऑनलाइन फ़ंक्शन अनुमान में सुधार:
    • औसत अनुमान त्रुटि: T^{3/4}/T^{5/6} से T^{2/3}/T^{7/9} तक सुधार
    • वर्ग त्रुटि: T^{2/3} से √T तक सुधार, Bellman पूर्ण MDP में पहली बार आशावादी विधियों के समान प्रदर्शन प्राप्त करना
  4. खुली समस्या का समाधान: पहली बार बैंडिट प्रतिक्रिया के तहत हाइब्रिड MDP के लिए मॉडल-मुक्त पश्चाताप सीमा प्रदान करना

विधि विवरण

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

DMSO ढांचा: मॉडल स्पेस M, नीति स्पेस Π, अवलोकन स्पेस O और मूल्य फ़ंक्शन V दिया गया। प्रत्येक दौर t में:

  • पर्यावरण मॉडल Mt ∈ M चुनता है
  • शिक्षार्थी नीति πt ∈ Π चुनता है
  • अवलोकन ot ~ Mt(·|πt)
  • लक्ष्य: पश्चाताप Reg(π*) = Σt(VMt(π*) - VMt(πt)) को कम करना

Φ-प्रतिबंधित वातावरण: सूचना सेट Φ के माध्यम से M×Π को विभाजित करना, प्रत्येक सूचना सेट ϕ में एकल नीति πϕ होती है।

मॉडल आर्किटेक्चर

1. सामान्य ढांचा (Algorithm 1)

मुख्य विचार निम्नलिखित सैडल पॉइंट समस्या को हल करना है:

min_{p∈Δ(Π)} max_{ν∈Δ(Ψ)} AIR^{Φ,D}_η(p,ν;ρt)

जहां विचलन माप है:

D^π(ν||ρ) = E_{M~ν}E_{o~M(·|π)}[KL(ν_{ϕ}(·|π,o), ρ) + E_{ϕ~ρ}[D^π(ϕ||M)]]

2. Dig-DEC परिभाषा

dig-dec^{Φ,D}_η = max_{ρ∈Δ(Φ)} min_{p∈Δ(Π)} max_{ν∈Δ(Ψ)} 
E_{π~p}E_{(M,π*)~ν}[V_M(π*) - V_M(π) - (1/η)E_{o~M(·|π)}[KL(ν_{ϕ}(·|π,o), ρ)] - (1/η)E_{ϕ~ρ}[D^π(ϕ||M)]]

3. पश्च अद्यतन तंत्र

D की विभिन्न पसंद के अनुसार:

  • औसत अनुमान त्रुटि: बैच प्रोसेसिंग एल्गोरिदम (Algorithm 2) का उपयोग करना
  • वर्ग अनुमान त्रुटि: दोहरी-परत शिक्षण एल्गोरिदम (Algorithm 3) का उपयोग करना

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

  1. दोहरे सूचना लाभ डिजाइन:
    • KL पद नियमितीकरण के लिए उपयोग किया जाता है, आशावादी तंत्र से बचने के लिए
    • D^π पद वितरण अंतर को पकड़ता है, कठोर सुधार प्राप्त करता है
  2. आशावाद को हटाना: नियमितीकरण पद KL(ν_{ϕ}, ρ) के माध्यम से आशावादी DEC में V_ϕ(π_ϕ) पद को प्रतिस्थापित करना
  3. अनुमान प्रक्रिया में सुधार:
    • औसत त्रुटि: पक्षपाती अनुमानक को निष्पक्ष अनुमानक से प्रतिस्थापित करना
    • वर्ग त्रुटि: दोहरी समय-स्केल प्रक्रिया को पुनः डिजाइन करना, Est सीमा T^{1/3} से स्थिरांक तक सुधार

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

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

  1. स्टोकेस्टिक सेटिंग:
    • द्विरेखीय वर्ग MDP
    • Bellman-eluder आयाम सीमित MDP
    • कवरेबिलिटी सीमित MDP
  2. हाइब्रिड सेटिंग:
    • हाइब्रिड द्विरेखीय वर्ग
    • हाइब्रिड कवरेबिलिटी MDP
    • ज्ञात रैखिक पुरस्कार विशेषताएं

मूल्यांकन मेट्रिक्स

  • पश्चाताप सीमा: EReg(π*) की ऊपरी सीमा
  • जटिलता तुलना: dig-dec vs o-dec vs शास्त्रीय DEC
  • अभिसरण दर: T की शक्ति निर्भरता संबंध

तुलना विधियां

  • Foster et al. (2023b) की आशावादी DEC
  • Liu et al. (2025) की AIR ढांचा
  • शास्त्रीय आशावादी विधियां (Jin et al. 2021, Xie et al. 2023)

प्रायोगिक परिणाम

मुख्य परिणाम

स्टोकेस्टिक वातावरण सुधार (तालिका 1):

सेटिंग श्रेणीFoster et al. (2023b)यह पेपर
द्विरेखीय/BE (औसत त्रुटि)T^{3/4}/T^{5/6}T^{2/3}/T^{7/9}
Bellman पूर्ण (वर्ग त्रुटि)T^{2/3}√T

हाइब्रिड वातावरण सफलता (तालिका 2):

सेटिंग श्रेणीLiu et al. (2025)यह पेपर
द्विरेखीय (औसत त्रुटि)केवल पूर्ण सूचनाT^{5/6}/T^{13/15}
Bellman पूर्ण (वर्ग त्रुटि)लागू नहींT^{3/4}

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

प्रमेय 13: स्टोकेस्टिक सेटिंग में, dig-dec^{Φ,D}_η ≤ o-dec^{Φ,D}_η + η

प्रमेय 14: तीन-भुजा बैंडिट उदाहरण का निर्माण, यह साबित करना कि ऐसे मामले मौजूद हैं:

  • Foster विधि: EReg(a) ≥ Ω(√T)
  • यह पेपर: EReg(a) ≤ 1

प्रायोगिक निष्कर्ष

  1. सूचना लाभ की महत्ता: KL पद आशावादी DEC द्वारा अनदेखी वितरण सूचना को पकड़ सकता है
  2. अनुमान प्रक्रिया सुधार: निष्पक्ष अनुमानक एकाग्रता असमानता प्रभाव को काफी बढ़ाता है
  3. आशावाद को हटाने का लाभ: एल्गोरिदम को प्रतिकूल वातावरण तक स्वाभाविक रूप से विस्तारित करने में सक्षम बनाता है

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

मुख्य अनुसंधान दिशाएं

  1. DEC ढांचा विकास:
    • Foster et al. (2021b, 2023a): मूल DEC सिद्धांत स्थापित करना
    • Foster et al. (2023b): आशावादी DEC पेश करना
    • Chen et al. (2025): अन्य सेटिंग्स तक विस्तार
  2. प्रतिकूल MDP अनुसंधान:
    • Neu et al. (2013): तालिका प्रतिकूल MDP
    • Luo et al. (2021): रैखिक प्रतिकूल MDP
    • Liu et al. (2025): हाइब्रिड MDP सिद्धांत
  3. मॉडल-मुक्त सुदृढ़ शिक्षा:
    • Jin et al. (2021): Bellman-eluder आयाम
    • Xie et al. (2023): कवरेबिलिटी सिद्धांत

यह पेपर के लाभ

  1. सैद्धांतिक एकीकरण: स्टोकेस्टिक और हाइब्रिड वातावरण दोनों को संभालने वाला पहला DEC ढांचा
  2. तकनीकी नवाचार: दोहरे सूचना लाभ डिजाइन, आशावाद निर्भरता को हटाना
  3. समस्या समाधान: Liu et al. (2025) द्वारा छोड़ी गई खुली समस्या को हल करना

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

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

  1. Dig-DEC अधिक सटीक जटिलता माप प्रदान करता है, विशेष मामलों में मनमाने ढंग से बड़ा सुधार प्राप्त कर सकता है
  2. आशावाद को हटाना एल्गोरिदम को प्रतिकूल वातावरण को स्वाभाविक रूप से संभालने में सक्षम बनाता है
  3. सुधारी गई अनुमान प्रक्रिया सिद्धांत और व्यवहार दोनों में महत्वपूर्ण है

सीमाएं

  1. धारणा प्रतिबंध: हाइब्रिड सेटिंग को ज्ञात रैखिक पुरस्कार विशेषताओं की आवश्यकता है (Assumption 4)
  2. तकनीकी बाधाएं: कुछ निम्न-रैंक MDP मामले अभी भी संभाले नहीं जा सकते हैं
  3. कम्प्यूटेशनल जटिलता: सैडल पॉइंट अनुकूलन की व्यावहारिक कम्प्यूटेशनल दक्षता विस्तार से चर्चा नहीं की गई है

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

  1. Assumption 3 और 4 की प्रतिबंधों को कम करना
  2. मॉडल-मुक्त शिक्षा की मौलिक सीमाओं का अध्ययन करना
  3. अधिक कुशल कम्प्यूटेशनल एल्गोरिदम विकसित करना

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

लाभ

  1. सैद्धांतिक योगदान महत्वपूर्ण:
    • नई जटिलता माप dig-dec प्रस्तावित करना
    • स्टोकेस्टिक और प्रतिकूल वातावरण को एकीकृत रूप से संभालना
    • महत्वपूर्ण खुली समस्या को हल करना
  2. तकनीकी नवाचार मजबूत:
    • दोहरे सूचना लाभ डिजाइन चतुर है
    • अनुमान प्रक्रिया सुधार प्रभावी है
    • विश्लेषण तकनीक उन्नत है
  3. परिणाम विश्वसनीयता मजबूत:
    • सैद्धांतिक सीमाएं tight और व्यावहारिक हैं
    • निर्माण उदाहरण कठोर सुधार साबित करते हैं
    • कई शास्त्रीय MDP वर्गों को कवर करता है

कमियां

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

प्रभाव

  1. सैद्धांतिक मूल्य: DEC सिद्धांत विकास के लिए नई दिशा प्रदान करता है, बाद के अनुसंधान को प्रेरित कर सकता है
  2. व्यावहारिक संभावना: व्यावहारिक सुदृढ़ शिक्षा एल्गोरिदम डिजाइन के लिए सैद्धांतिक मार्गदर्शन प्रदान करता है
  3. क्षेत्र प्रगति: मॉडल-मुक्त शिक्षा और प्रतिकूल MDP के अंतरविषय क्षेत्र में सफलता प्राप्त करता है

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

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

संदर्भ

मुख्य संदर्भ साहित्य में शामिल हैं:

  • Foster et al. (2021b, 2023a, 2023b): DEC सिद्धांत आधार
  • Liu et al. (2025): हाइब्रिड MDP अनुसंधान
  • Jin et al. (2021): Bellman-eluder आयाम
  • Xie et al. (2023): कवरेबिलिटी सिद्धांत
  • Xu and Zeevi (2023): AIR ढांचा

यह पेपर निर्णय-अनुमान गुणांक सिद्धांत में महत्वपूर्ण प्रगति प्राप्त करता है, चतुर तकनीकी नवाचार के माध्यम से इस क्षेत्र की मुख्य समस्याओं को हल करता है, और सुदृढ़ शिक्षा सिद्धांत विकास में मूल्यवान योगदान देता है। हालांकि व्यावहारिक अनुप्रयोग सत्यापन में सुधार की गुंजाइश है, लेकिन इसका सैद्धांतिक मूल्य और नवाचार इसे इस क्षेत्र का एक महत्वपूर्ण कार्य बनाते हैं।