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 العدائية

المعلومات الأساسية

  • معرّف الورقة: 2510.08882
  • العنوان: An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPs
  • المؤلفون: Haolin Liu (جامعة فيرجينيا)، Chen-Yu Wei (جامعة فيرجينيا)، Julian Zimmert (Google Research)
  • التصنيف: cs.LG (تعلم الآلة)
  • تاريخ النشر: أكتوبر 2025
  • رابط الورقة: https://arxiv.org/abs/2510.08882v1

الملخص

تدرس هذه الورقة مشكلة صنع القرار مع الملاحظات المنظمة (DMSO). حاولت الأعمال السابقة توصيف تعقيد DMSO من خلال معامل تقدير القرار (DEC)، لكنها تركت فجوة بين الحدود العليا والدنيا للندم مرتبطة بحجم فئة النموذج. قدّم Foster وآخرون (2023b) معامل تقدير القرار المتفائل لتضييق هذه الفجوة، محققين حدوداً تتعلق فقط بحجم فئة دالة القيمة. ومع ذلك، لا يزال غير واضح ما إذا كان الاستكشاف القائم على التفاؤل يمكن توسيعه للبيئات العدائية.

تقترح هذه الورقة Dig-DEC، وهي طريقة DEC خالية من النموذج تزيل التفاؤل وتدفع الاستكشاف بحتاً من خلال الكسب المعلوماتي. يكون Dig-DEC دائماً أقل من أو يساوي معامل تقدير القرار المتفائل، وفي حالات خاصة يمكن أن يكون أصغر بكثير. الأهم من ذلك، أن إزالة التفاؤل تمكّنه من التعامل مع البيئات العدائية دون الحاجة إلى مقدّر مكافآت صريح. من خلال تطبيق Dig-DEC على MDPs الهجينة ذات الانتقالات العشوائية والمكافآت العدائية، تم الحصول على أول حد ندم خالٍ من النموذج لـ MDPs الهجينة مع ردود فعل bandit تحت هياكل انتقالية عامة متعددة.

الخلفية البحثية والدافع

  1. المشكلة المراد حلها: يوجد فجوة في إطار معامل تقدير القرار الحالي بين حجم فئة النموذج وحجم فئة دالة القيمة، والطرق القائمة على التفاؤل لا تتعامل بفعالية مع البيئات العدائية.
  2. أهمية المشكلة:
    • صنع القرار عبر الإنترنت هو مشكلة أساسية في التعلم المعزز
    • غالباً ما تواجه التطبيقات العملية بيئات هجينة جزئياً عشوائية وجزئياً عدائية
    • توجد فجوة بين الضمانات النظرية والأداء العملي في الطرق الموجودة
  3. قيود الطرق الموجودة:
    • نموذج Foster وآخرين القائم على DEC/E2D يتطلب تحمل تكلفة تقدير النموذج log|M|
    • بينما يحسّن معامل تقدير القرار المتفائل التعقيد، إلا أنه يعتمد على مبدأ التفاؤل ولا يمكنه التعامل مع الإعدادات العدائية
    • طريقة Liu وآخرين (2025) للـ MDP الهجينة تتعامل فقط مع ردود الفعل الكاملة، وحالة bandit لا تزال مشكلة مفتوحة
  4. الدافع البحثي: تطوير إطار عمل موحد يمكنه تحسين النتائج الموجودة في البيئات العشوائية والتعامل للمرة الأولى مع حالة bandit في MDP الهجينة.

المساهمات الأساسية

  1. اقتراح مقياس تعقيد Dig-DEC: إدخال معامل تقدير القرار ذي الكسب المعلوماتي المزدوج، الذي يزيل التفاؤل ويدفع الاستكشاف بحتاً من خلال الكسب المعلوماتي
  2. إطار نظري موحد: بناء إطار عمل خوارزمي عام يمكنه التعامل مع البيئات العشوائية والهجينة في نفس الوقت
  3. تحسين تقدير الدوال عبر الإنترنت:
    • متوسط خطأ التقدير: تحسين من T^{3/4}/T^{5/6} إلى T^{2/3}/T^{7/9}
    • الخطأ التربيعي: تحسين من T^{2/3} إلى √T، وتحقيق نفس أداء الطرق المتفائلة للمرة الأولى في MDPs الكاملة من Bellman
  4. حل المشاكل المفتوحة: تقديم أول حد ندم خالٍ من النموذج لـ MDP الهجينة تحت ردود فعل bandit

شرح الطريقة

تعريف المهمة

إطار DMSO: بالنظر إلى فضاء النموذج M، فضاء السياسة Π، فضاء الملاحظة O وقيمة الدالة V. في كل جولة t:

  • يختار البيئة نموذجاً Mt ∈ M
  • يختار المتعلم سياسة πt ∈ Π
  • ملاحظة ot ~ Mt(·|πt)
  • الهدف: تقليل الندم Reg(π*) = Σt(VMt(π*) - VMt(πt))

البيئة المقيدة بـ Φ: تقسيم M×Π من خلال مجموعات المعلومات Φ، حيث تحتوي كل مجموعة معلومات ϕ على سياسة واحدة πϕ.

بنية النموذج

1. الإطار العام (الخوارزمية 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 المختلف:

  • متوسط خطأ التقدير: استخدام خوارزمية معالجة الدفعات (الخوارزمية 2)
  • الخطأ التربيعي: استخدام خوارزمية التعلم ثنائي الطبقة (الخوارزمية 3)

نقاط الابتكار التقني

  1. تصميم الكسب المعلوماتي المزدوج:
    • يُستخدم حد KL للتنظيم، لتجنب آلية التفاؤل
    • يلتقط حد D^π الاختلافات في التوزيع، مما يحقق تحسيناً صارماً
  2. إزالة التفاؤل: من خلال استبدال حد التنظيم KL(ν_{ϕ}, ρ) بحد V_ϕ(π_ϕ) في معامل تقدير القرار المتفائل
  3. إجراءات تقدير محسّنة:
    • متوسط الخطأ: استخدام مقدّر غير متحيز بدلاً من مقدّر متحيز
    • الخطأ التربيعي: إعادة تصميم برنامج ثنائي المقياس الزمني، تحسين حد Est من T^{1/3} إلى ثابت

إعداد التجارب

بيئات التحقق النظري

  1. الإعداد العشوائي:
    • MDPs ثنائي الخطية
    • MDPs بحد أبعاد Bellman-eluder
    • MDPs بقابلية تغطية محدودة
  2. الإعداد الهجين:
    • فئة ثنائية الخطية هجينة
    • MDP قابل للتغطية هجين
    • خصائص المكافآت الخطية المعروفة

مؤشرات التقييم

  • حد الندم: الحد الأعلى لـ EReg(π*)
  • مقارنة التعقيد: dig-dec مقابل o-dec مقابل DEC الكلاسيكي
  • معدل التقارب: اعتماد قوة T

طرق المقارنة

  • معامل تقدير القرار المتفائل لـ Foster وآخرين (2023b)
  • إطار AIR لـ Liu وآخرين (2025)
  • الطرق المتفائلة الكلاسيكية (Jin وآخرين 2021، Xie وآخرين 2023)

نتائج التجارب

النتائج الرئيسية

التحسينات في البيئة العشوائية (الجدول 1):

فئة الإعدادFoster وآخرين (2023b)الطريقة المقترحة
ثنائي الخطية/BE (متوسط الخطأ)T^{3/4}/T^{5/6}T^{2/3}/T^{7/9}
Bellman كامل (الخطأ التربيعي)T^{2/3}√T

اختراقات البيئة الهجينة (الجدول 2):

فئة الإعدادLiu وآخرين (2025)الطريقة المقترحة
ثنائي الخطية (متوسط الخطأ)معلومات كاملة فقطT^{5/6}/T^{13/15}
Bellman كامل (الخطأ التربيعي)غير قابل للتطبيقT^{3/4}

التحقق من المزايا النظرية

النظرية 13: في الإعداد العشوائي، dig-dec^{Φ,D}_η ≤ o-dec^{Φ,D}_η + η

النظرية 14: بناء مثيل bandit ثلاثي الأذرع، إثبات وجود حالات حيث:

  • طريقة Foster: EReg(a) ≥ Ω(√T)
  • الطريقة المقترحة: EReg(a) ≤ 1

الاكتشافات التجريبية

  1. أهمية الكسب المعلوماتي: يمكن لحد KL التقاط معلومات التوزيع التي يتجاهلها معامل تقدير القرار المتفائل
  2. تحسين إجراء التقدير: يحسّن المقدّر غير المتحيز بشكل كبير من تأثير عدم المساواة في التركيز
  3. مزايا إزالة التفاؤل: تمكّن الخوارزمية من التوسع بشكل طبيعي إلى البيئات العدائية

الأعمال ذات الصلة

الاتجاهات البحثية الرئيسية

  1. تطور إطار DEC:
    • Foster وآخرين (2021b, 2023a): إنشاء نظرية DEC الأساسية
    • Foster وآخرين (2023b): إدخال معامل تقدير القرار المتفائل
    • Chen وآخرين (2025): التوسع إلى إعدادات أخرى
  2. بحث MDP العدائي:
    • Neu وآخرين (2013): جداول MDP عدائية
    • Luo وآخرين (2021): MDP عدائية خطية
    • Liu وآخرين (2025): نظرية MDP الهجينة
  3. التعلم المعزز الخالي من النموذج:
    • Jin وآخرين (2021): بعد Bellman-eluder
    • Xie وآخرين (2023): نظرية القابلية للتغطية

مزايا هذه الورقة

  1. توحيد نظري: أول إطار DEC يتعامل مع البيئات العشوائية والهجينة في نفس الوقت
  2. ابتكار تقني: تصميم الكسب المعلوماتي المزدوج، إزالة الاعتماد على التفاؤل
  3. حل المشاكل: حل المشكلة المفتوحة التي تركها Liu وآخرين (2025)

الخلاصة والمناقشة

الاستنتاجات الرئيسية

  1. يوفر Dig-DEC توصيفاً أكثر دقة للتعقيد، مما يمكن أن يحقق تحسينات كبيرة في حالات خاصة
  2. إزالة التفاؤل تمكّن الخوارزمية من التعامل بشكل طبيعي مع البيئات العدائية
  3. برنامج التقدير المحسّن له أهمية كبيرة من الناحية النظرية والعملية

القيود

  1. قيود الافتراضات: يتطلب الإعداد الهجين معرفة خصائص المكافآت الخطية (الافتراض 4)
  2. القيود التقنية: لا تزال بعض حالات MDP منخفضة الرتبة غير قابلة للمعالجة
  3. التعقيد الحسابي: لم يتم مناقشة كفاءة الحساب العملي لتحسين النقطة السرجية بالتفصيل

الاتجاهات المستقبلية

  1. تخفيف قيود الافتراضات 3 و 4
  2. دراسة الحدود الأساسية للتعلم الخالي من النموذج
  3. تطوير خوارزميات حسابية أكثر كفاءة

التقييم المتعمق

المزايا

  1. مساهمة نظرية كبيرة:
    • اقتراح مقياس تعقيد جديد dig-dec
    • التعامل الموحد مع البيئات العشوائية والعدائية
    • حل مشكلة مفتوحة مهمة
  2. قوة الابتكار التقني:
    • تصميم الكسب المعلوماتي المزدوج ذكي
    • تحسين إجراء التقدير فعال
    • تقنيات التحليل متقدمة
  3. قوة إقناع النتائج:
    • حدود نظرية محكمة وعملية
    • بناء أمثلة يثبت التحسين الصارم
    • تغطية فئات MDP الكلاسيكية المتعددة

أوجه القصور

  1. التحقق التجريبي محدود: يركز بشكل أساسي على التحليل النظري، ويفتقر إلى تنفيذ الخوارزمية الفعلية والتحقق التجريبي
  2. نطاق التطبيق محدود: الافتراضات المتعلقة بـ MDP الهجينة قوية نسبياً، مما يحد من عمومية الطريقة
  3. التعقيد الحسابي: تحتاج قابلية الحل العملي وكفاءة تحسين النقطة السرجية إلى مزيد من البحث

التأثير

  1. القيمة النظرية: توفير اتجاه جديد لتطور نظرية DEC، قد تلهم الأبحاث اللاحقة
  2. الإمكانات العملية: توفير إرشادات نظرية لتصميم خوارزميات التعلم المعزز العملية
  3. تقدم المجال: تحقيق اختراق في المجال المتقاطع بين التعلم الخالي من النموذج و MDP العدائية

السيناريوهات القابلة للتطبيق

  1. البحث النظري: توسيع إطار DEC، تحليل التعقيد
  2. تصميم الخوارزميات: خوارزميات التعلم المعزز التي تحتاج إلى التعامل مع البيئات الهجينة
  3. مجالات التطبيق: التداول المالي وأنظمة التوصيات وغيرها من البيئات العدائية جزئياً

المراجع

تشمل المراجع الرئيسية:

  • Foster وآخرين (2021b, 2023a, 2023b): الأساس النظري لـ DEC
  • Liu وآخرين (2025): بحث MDP الهجينة
  • Jin وآخرين (2021): بعد Bellman-eluder
  • Xie وآخرين (2023): نظرية القابلية للتغطية
  • Xu و Zeevi (2023): إطار AIR

حققت هذه الورقة تقدماً مهماً في نظرية معامل تقدير القرار، وحلت المشاكل الرئيسية في هذا المجال من خلال الابتكار التقني الذكي، وقدمت مساهمة قيمة لتطور نظرية التعلم المعزز. بينما لا تزال هناك مجالات للتحسين في التحقق من التطبيقات العملية، فإن قيمتها النظرية وابتكارها يجعلانها عملاً مهماً في هذا المجال.