Robust Average-Reward Markov Decision Processes: Minimax-Optimal Learning via Plug-in Reductions

ملخص تقني: عمليات ماركوف لاتخاذ القرار ذات المكافأة المتوسطة والمتينة (Robust Average-Reward MDPs)

صياغة المشكلة
يستقصي هذا العمل التعقيد الإحصائي لتعلم سياسة مثالية بمقدار $\epsilon$ لعمليات ماركوف لاتخاذ القرار ذات المكافأة المتوسطة والمتينة توزيعياً (Distributionally Robust AMDPs) في إطار النموذج التوليدي (Generative Model). يعمل الوكيل ضمن بيئة اسمية محددة عبر نواة انتقال $P^0$ ودالة مكافأة $r$. ومع ذلك، فإن ديناميكيات البيئة الحقيقية غير مؤكدة وقد تقع ضمن مجموعة عدم يقين $\mathcal{P}$ ممركزة حول $P^0$. وتحديداً، تدرس الورقة مجموعات عدم اليقين من نوع (s, a)-rectangular ذات مسافة التباين الكلي (Total-Variation) التي لا يتجاوز نصف قطرها $\sigma$.

الهدف هو تعظيم متوسط المكافأة المتينة، والمعرف كأدنى مكافأة متوسطة طويلة الأمد عبر جميع نوى الانتقال في $\mathcal{P}$:
$$\rho^{\pi, \sigma} := \inf_{P \in \mathcal{P}} \lim_{T \to \infty} \mathbb{E}^\pi_P \left[ \frac{1}{T} \sum_{t=0}^{T-1} r(s_t, a_t) \right]$$
الهدف التعليمي هو حساب سياسة $\hat{\pi}$ باستخدام $N$ من العينات لكل زوج (حالة-إجراء) بحيث يكون $\rho^{\star, \sigma} - \rho^{\hat{\pi}, \sigma} \leq \epsilon$، حيث $\rho^{\star, \sigma}$ هي المكافأة المتوسطة المتينة المثلى.

المعلمات الرئيسية والافتراضات الهيكلية
يعتمد التحليل على معلمتين هيكليتين حرجتين:

1. مدى الانحراف الأمثل الاسمي ($H_0$): مدى دالة الانحراف (Bias function) التي تحقق معادلة بلمان المثلى الاسمية.
2. مدى الانحراف الأمثل المتين ($H_\sigma$): مدى دالة الانحراف التي تحقق معادلة بلمان المثلى المتينة.

تثبت الورقة أن $H_0$ و $H_\sigma$ مستقلان عموماً، ولا يتحكم أحدهما في الآخر. وقد تم تحديد مقياس اضطراب حاسم وهو $\sigma H_0$، والذي يفصل مشكلة التعلم إلى نظامين متميزين:

• نظام التسامح العالي ($\epsilon \gtrsim \sigma H_0$): الاضطراب الناتج عن عدم اليقين صغير مقارنة بدقة الهدف.
• نظام التسامح المنخفض ($\epsilon \lesssim \sigma H_0$): الاضطراب كبير، والتحسين الاسمي وحده غير كافٍ لضمان المثالية المتينة.

المنهجية: إجراءات الاستبدال القائمة على الاختزال (Reduction-Based Plug-in Procedures)
المساهمة المنهجية الجوهرية هي إطار عمل اختزال يحول مشكلة المكافأة المتوسطة المتينة الصعبة إلى مشكلة عملية ماركوف لاتخاذ القرار الخصمية (DMDP) المتينة الأكثر سهولة في المعالجة. يقترح المؤلفون خوارزميتين بناءً على هذا الاختزال:

1. الإجراء المستند إلى المدى (Algorithm 1): يفترض معرفة $H_0$ و $H_\sigma$. يقوم باختيار تكيفي بين اختزال اسمي (حل DMDP قياسي باستخدام النواة التجريبية) و اختزال متين (حل DMDM عبر مجموعة عدم اليقين). يعتمد الاختيار على ترتيب $H_0$ و $H_\sigma$ ونظام التسامح. يتم معايرة عامل الخصم $\gamma$ بناءً على معلمة المدى ذات الصلة (على سبيل المثال، $\gamma = 1 - \epsilon/(3H_\sigma)$).
2. الإجراء غير المستند إلى المدى (Algorithm 2): يعمل دون معرفة $H_0$ أو $H_\sigma$. يقوم بإنشاء مجموعة من السياسات المرشحة من كل من الاختزالات الاسمية والمتينة عبر شبكة ديادية (Dyadic grid) من عوامل الخصم. ثم يختار أفضل سياسة باستخدام حد ثقة سفلي (LCB) على المكافأة المتوسطة المتينة، والمستمد من "شهادة مرساة" (Anchor certificate) يتم حسابها من دفعة بيانات منفصلة. وهذا يسمح للخوارزمية بالتكيف لاختيار الاختزال وعامل الخصم الصحيحين بناءً على البيانات.

تستفيد التحليلات من ثلاثة تحسينات تقنية رئيسية لتحقيق حدود ضيقة:

• مقارنة المشكلة الخصمية المتينة بحل مرجعي اسمي (مرساة) لتضييق حدود التباين.
• التحكم في دوال القيمة الخصمية عبر مداها ($H_\sigma$) بدلاً من الأفق الفعال.
• استخدام حدود تركيز موضعية محكومة بهذه المداى.

النتائج الرئيسية: تعقيد العينات الأدنى-الأقصى (Minimax Sample Complexity)
تقدم الورقة حدوداً عليا وسفلى متطابقة لتعقيد العينات الأدنى-الأقصى $N_{SA}$ (العينات لكل حالة-إجراء)، مع مراعاة العوامل اللوغاريتمية. يتم توصيف التعقيد عبر ملخص من أربعة أنظمة بناءً على ترتيب $H_0$ و $H_\sigma$ ونظام التسامح:

$$N_{SA} \asymp \frac{SA}{\epsilon^2} \times \begin{cases} \min\{H_0, H_\sigma\} & \text{if } \epsilon \gtrsim \sigma H_0 \quad (\text{High Tolerance}) \\ \min\{H_0, H_\sigma\} + \sigma H_\sigma^2 & \text{if } \epsilon \lesssim \sigma H_0 \quad (\text{Low Tolerance}) \end{cases}$$

• نظام التسامح العالي: يهيمن عليه حد المدى الخطي $\min\{H_0, H_\sigma\}$. إذا كان $H_\sigma \leq H_0$، فإن الاختزال المتين يعطي حداً أضيق من الاختزال الاسمي.
• نظام التسامح المنخفض: يظهر حد إضافي "خاص بالمتانة" وهو $\sigma H_\sigma^2$، والذي يمثل تكلفة التعامل مع عدم اليقين التوزيعي عندما تتطلب الدقة العالية ذلك.
• الحد الأدنى: يثبت المؤلفون حداً أدنى (Minimax lower bound) يطابق الحد الأعلى، مما يؤكد أن المصطلح $\sigma H_\sigma^2$ جوهري ولا يمكن تجنبه في نظام التسامح المنخفض. هذا هو أول حد أدنى يحدد الحدود الإحصائية لعمليات AMDP المتينة توزيعياً.

الأهمية والادعاءات
تدعي الورقة أنها تقدم أول توصيف للأمثلية الدنيا-القصوى (Minimax-optimal) لتعقيد العينات لعمليات AMDP المتينة توزيعياً. المساهمات الرئيسية تشمل:

• حل فجوة تعقيد العينات: اعتمدت الحدود العليا المتينة السابقة (مثل Roch et al., 2025, 2026) تربيعياً على معلمات المدى المتين ($H_{Roch}^2$ أو $H_{RHI}^2$) دون التمييز بين التسامح العالي والمنخفض. تعمل هذه الدراسة على تحسين الاعتماد إلى $\min\{H_0, H_\sigma\}$ في نظام التسامح العالي وتحديد تكلفة $\sigma H_\sigma^2$ الدقيقة في نظام التسامح المنخفض.
• خوارزميات تكيفية: الإجراء غير المستند إلى المدى (Algorithm 2) يحقق هذه المعدلات المثلى دون معرفة مسبقة بمعلمات المدى، حيث يتكيف تلقائياً مع النظام ومع المقادير النسبية لـ $H_0$ و $H_\sigma$.
• العمومية: تسري النتائج حتى لو افترضنا فقط أن $H_\sigma$ محدود، مما يعطي تعقيداً قدره $\tilde{\Theta}(SA(H_\sigma + \sigma H_\sigma^2)\epsilon^{-2})$.

تتحقق النتائج التجريبية في محاكاة محكومة من الاعتماد الخطي المتوقع على $\min\{H_0, H_\sigma\}$ والاعتماد التربيعي على $\sigma H_\sigma^2$ في نظام التسامح المنخفض، بالإضافة إلى قدرة التكيف للخوارزمية غير المستندة إلى المدى. يشير المؤلفون إلى أن العمل المستقبلي يمكن أن يستكشف هياكل عدم اليقين المقترنة أو الإعدادات عبر الإنترنت (القائمة على الندم)، لكن العمل الحالي يركز حصرياً على إطار النموذج التوليدي.