ملخص تقني: التعلم عبر الإنترنت في نماذج ماركوف لاتخاذ القرار الشجرية (Tree MDPs) من خلال معاملة السياسات كأذرع بانديت (Bandit Arms)

1. تعريف المشكلة

تتناول الورقة مشكلة التعلم عبر الإنترنت (on-line learning) في نماذج ماركوف لاتخاذ القرار الشجرية (T-MDPs). يُعرَّف الـ T-MDP بأنه نموذج ماركوف لاتخاذ القرار ذو أفق زمني محدد، حيث تشكل انتقالات الحالة بنية شجرية جذورها هي الحالة الابتدائية $s_1$. ومن الخصائص الجوهرية لـ T-MDP أن كل حالة يمكن الوصول إليها من $s_1$ عبر مسار واحد فقط من (الحالة-الإجراء).

تنشأ هذه الهياكل بشكل طبيعي كتمثيلات تجريدية للألعاب ذات الصيغة الموسعة ذات الذاكرة الكاملة (extensive-form games with perfect recall) التي تُلعب ضد خصوم ثابتين. الهدف التعليمي المحدد هو إيجاد الاستجابة المثلى (best response) لخصم غير معروف ولكنه ثابت من خلال التفاعلات المتكررة مع اللعبة. لا يعرف الوكيل احتمالات الانتقال $p$، لكنه يعرف دالة المكافأة $r$. يتفاعل الوكيل مع البيئة من خلال لعب حلقات كاملة تبدأ من $s_1$، ومراقبة المسارات، واختيار سياسات جديدة للحلقات اللاحقة.

تستقصي الورقة هذه المشكلة في نظامين:

1. التعلم التقريبي المحتمل (PAC): الهدف هو إخراج سياسة $\pi$ بحيث يكون $V(\pi) \geq V(\pi^*) - \epsilon$ باحتمال لا يقل عن $1-\delta$، مع تقليل عدد الحلقات (التعقيد في العينات).
2. تقليل الندم (Regret Minimization): الهدف هو تقليل الندم التراكمي $R_T = \sum_{t=1}^T (V(\pi^*) - \mathbb{E}[V(\pi_t)])$ عبر $T$ من الحلقات.

2. المنهجية

الابتكار المنهجي الأساسي هو معاملة كل سياسة في الـ T-MDP كـ ذراع بانديت (bandit arm). وبينما يعد هذا النهج بسيطاً من الناحية المفاهيمية، فإن عدد السياسات الحتمية هو عدد أسي بالنسبة لعدد الحالات ($|A|^{|S|}$)، مما يجعل التنفيذ الساذج مستحيلاً من الناحية الحسابية والذاكرة.

للتغلب على ذلك، يقترح المؤلفون إطار عمل حيث تتشارك السياسات البيانات بناءً على البنية الشجرية للـ MDP.

2.1 تفكيك القيمة (Value Decomposition)

يؤكد المؤلفون أن قيمة أي سياسة $\pi$، وهي $V(\pi)$، يمكن التعبير عنها كتركيبة محدبة للعوائد النهائية. وتحديداً، $V(\pi) = \sum_{\sigma \in X(\pi)} q(\sigma) \cdot \rho(\sigma)$، حيث:

• $X(\pi)$ هي مجموعة الحالات النهائية المتسقة مع السياسة $\pi$.
• $q(\sigma)$ هو احتمال الوصول إلى الحالة النهائية $\sigma$ من $s_1$ تحت السياسة $\pi$.
• $\rho(\sigma)$ هو المكافأة التراكمية المخصومة على طول المسار إلى $\sigma$.

بما أن دالة المكافأة مفترضة كمعلومة، فإن $\rho(\sigma)$ معلومة. وبذلك يتقلص مشكلة التعلم إلى تقدير احتمالات الانتقال $q(\sigma)$ للحالات النهائية. ومن الأهمية بمكان أن البيانات اللازمة لتقدير $q(\sigma)$ يمكن جمعها عن طريق لعب أي سياسة متسقة مع $\sigma$، وليس فقط $\sigma$ نفسها.

2.2 حدود الثقة ومشاركة البيانات

تقدم الورقة حداً للثقة جديداً لـ $V(\pi)$ يستفيد من البيانات المشتركة بين السياسات.

• آلية العد: بالنسبة للحالة النهائية $\sigma$، يتتبع الخوارزمي $n_t(\sigma)$، وهو عدد الحلقات التي كانت فيها السياسة الملعوبة متسقة مع $\sigma$، و $n_t^+(\sigma)$، وهو عدد المرات التي تم فيها الوصول فعلياً إلى $\sigma$.
• عد السياسة: بالنسبة للسياسة $\pi$، يتم تعريف "عد اللعب" $n_t(\pi)$ كـ $\min_{\sigma \in X(\pi)} n_t(\sigma)$. ويمثل هذا "عنق الزجاجة" في توافر البيانات لتقييم $\pi$.
• المُقدِّر (Estimator): القيمة التجريبية $\hat{V}_t(\pi)$ هي مُقدِّر غير منحاز يتم بناؤه من الاحتمالات التجريبية $\hat{q}_t(\sigma) = n_t^+(\sigma) / n_t(\sigma)$.

2.3 الأساس النظري: التبعية الأسطوانية السالبة (Negative Cylinder Dependence)

التحدي التقني الكبير هو أن المتغيرات العشوائية المستخدمة لتقدير $V(\pi)$ (النتائج من نوع برنولي للوصول إلى الحالات النهائية) هي متكافئة (dependent) لأن سياسات متعددة قد تُلعب في نفس الحلقة.

• يثبت المؤلفون أن هذه المتغيرات تظهر تبعية أسطوانية سالبة (NCD).
• قدموا "متغيرات توأم" (متغيرات برنولي مستقلة لها نفس المتوسطات) للحد من انحراف المُقدِّر المعتمد.
• باستخدام متباينة بيرنشتاين (Bernstein's Inequality) على هذه المتغيرات التوأم، اشتقوا حدود الثقة (UCB و LCB) التي تتحقق باحتمالية عالية. وهذا يسمح بتطبيق خوارزميات البانديت (Lucb و Ucb) على المجموعة الأسية من السياسات مع استخدام ذاكرة وحوسبة حدودية في كل خطوة.

2.4 الخوارزميات

قام المؤلفون بتكييف خوارزميتين قياسيتين للبانديت:

1. Lucb-T: وهو تكييف لخوارزمية Lucb لإعداد الـ PAC. يقوم بشكل متكرر باختيار السياسة ذات القيمة الأعلى والسياسة ذات أعلى حد ثقة علوي (UCB) من بين البقية، ويلعبهما حتى يتم الفصل بينهما بـ $\epsilon$.
2. Ucb-T: وهو تكييف لخوارزمية Ucb لتقليل الندم. يختار السياسة ذات أعلى حد ثقة علوي (UCB) في كل حلقة.

تستخدم كلتا الخوارزميتين إجراءً يسمى PU (السياسة ذات أعلى UCB) لحساب السياسة المعظمة بكفاءة في زمن قدره $O(|S||A||k_{max}| + |\Sigma|)$، مما يتجنب الحاجة إلى تعداد جميع السياسات.

3. المساهمات الرئيسية

1. النتيجة التحليلية: متباينة تركيز جديدة (النظرية 2) تؤسس حدود الثقة لقيم السياسات في T-MDPs. تتعامل هذه النتيجة مع التبعية بين البيانات المشتركة بين السياسات وقد يكون لها تطبيقات أوسع في التعلم في المهام المتسلسلة.
2. التصميم الخوارزمي: خوارزميات بسيطة مفاهيمياً (Lucb-T و Ucb-T) تعامل السياسات كأذرع بانديت ولكنها تستغل البنية الشجرية للتنفيذ الفعال.
3. الضمانات النظرية:
   • التعقيد في العينات (النظرية 9): حد علوي يعتمد على الحالة لـ Lucb-T يقوم بجمع "حد الفجوة" (gap term) عبر الحالات النهائية ($\sum_{\sigma \in \Sigma} \frac{1}{(\Delta^\epsilon_\sigma)^2}$) بدلاً من السياسات.
   • حد الندم (النظرية 10): حد علوي يعتمد على الحالة لـ Ucb-T، والذي يلخص أيضاً عبر الحالات النهائية.
4. التحقق التجريبي: التنفيذ والاختبار على ثلاث ألعاب ذات معلومات ناقصة متفاوتة الأحجام: Kuhn Poker (صغيرة)، Leduc Poker (متوسطة)، و Reconnaissance Blind Tic-Tac-Toe (RBT، كبيرة، مع ملايين الحالات).

4. النتائج

• القابلية للتوسع: تتفوق الخوارزميات المقترحة باستمرار على البدائل المتاحة (مثل Lucb التقليدي، Bpi-Ucrl، Mdp-GapE، Mccfr، و Uct) مع زيادة حجم المشكلة.
• كفاءة مشاركة البيانات: في المشكلات الصغيرة (3-card Kuhn Poker)، تكون خوارزمية Lucb التقليدية (بدون مشاركة بيانات) منافسة. ومع ذلك، في المتغيرات الأكبر (5-card Kuhn Poker، Leduc، RBT)، تتفوق متغيرات "الشجرة" (Lucb-T، Ucb-T) بشكل كبير على خطوط الأساس غير المشاركة، مما يثبت ضرورة مشاركة البيانات من أجل القابلية للتوسع.
• أداء RBT: نجحت الخوارزميات في التعامل مع RBT، وهي لعبة تصل حالاتها إلى $2 \times 10^7$ حالة، حيث فشلت خوارزميات PAC الأخرى (Bpi-Ucrl، Mdp-GapE) في الأداء الجيد.
• النظرية مقابل الممارسة: تسلط التجارب الضوء على الفجوات بين الحدود النظرية والأداء العملي، خاصة في إعداد PAC حيث يمكن أن تكون أوقات التوقف كبيرة جداً، مما يشير إلى أنه بينما الخوارزميات سليمة نظرياً، فإن الضبط العملي أمر ضروري.

5. الأهمية والادعاءات

تدعي الورقة أن مساهمتها الأساسية هي تعميم خوارزميات البانديت المعروفة (Lucb و Ucb) على T-MDPs من خلال معاملة السياسات كأذرع. تكمن الأهمية في:

• التغلب على التعقيد الأسي: إثبات إمكانية تحقيق تعقيد ذاكرة وحوسبة حدودي رغم العدد الأسي للسياسات، وذلك عبر استخدام بنية الشجرة لمشاركة البيانات.
• الحدود المعتمدة على الحالة (Instance-Dependent Bounds): تقديم ضمانات نظرية تعتمد على "الفجوة" عند الحالات النهائية بدلاً من إجمالي عدد السياسات، مما يوفر تحليلاً أكثر دقة من الحدود في أسوأ الحالات.
• القابلية للتطبيق العملي: التحقق من النهج في ألعاب المعلومات الناقصة واسعة النطاق (تحديداً RBT)، والتي تعمل كمعيار لجدوى تعلم الاستجابات المثلى في مشايات اتخاذ القرار المتسلسلة المعقدة ضد خصوم ثابتين.

يشير المؤلفون إلى أن افتراضهم بـ معرفة دالة المكافأة هو افتراض منطقي لمجالهم المحفز (ألعاب المعلومات الناقصة)، ولكنه قيد مقارنة بـ MDPs العامة حيث قد تكون المكافآت غير معروفة. كما يقرون بأن حدودهم تتجنب الاعتماد على احتمالات زيارة الحالة (والتي يمكن أن تكون صغيرة جداً في MDPs العامة)، وهذا ميزة محددة لبنية T-MDP.