An Online Learning Approach for Two-Player Zero-Sum Linear Quadratic Games

إليك ملخص تقني مفصل للورقة البحثية بعنوان "نهج التعلم عبر الإنترنت لألعاب التربيع الخطي ذات لاعبين وصفر من المجموع" (An Online Learning Approach for Two-Player Zero-Sum Linear Quadratic Games).

1. صياغة المشكلة

تتناول الورقة البحثية تحدي التحكم في ألعاب التربيع الخطي (LQ) ذات لاعبين وصفر من المجموع حيث تكون ديناميكيات النظام غير معروفة.

• نموذج النظام: نظام خطي في الزمن المنفصل $x_{t+1} = A x_t + B_1 u_t + B_2 v_t + w_t$، حيث $u_t$ و $v_t$ هما مدخلا التحكم للاعب 1 (المُقلل/Minimizer) واللاعب 2 (المُعظم/Maximizer)، على التوالي. المصفوفات $A, B_1, B_2$ غير معروفة.
• الهدف: يسعى اللاعب 1 إلى تقليل دالة تكلفة الأفق اللانهائي $J(u, v)$، بينما يسعى اللاعب 2 إلى تعظيمها.
• التوازن: الهدف هو إيجاد استراتيجيات توازن ناش (Nash Equilibrium) التي هي سياسات تغذية راجعة خطية ($u_t = -K^* x_t, v_t = -L^* x_t$) مشتقة من حل معادلة ريكاتي الجبرية المعممة (GARE).
• التحدي: بخلاف مشاكل المنظم التربيع الخطي (LQR) أحادية الوكيل، تتضمن ألعاب صفر المجموع استراتيجيات مقترنة وتفاعلات عدائية. غالبًا ما تفشل طرق التعلم عبر الإنترنت القياسية (مثل اليقين التام/Certainty Equivalence) لأن النموذج المقدر قد لا يستوفي شروط الاستقرار المطلوبة لحل معادلة GARE (أي أن المصفوفات المقدرة قد لا تسمد نقطة توازن مستقرة).
• مقياس الأداء: يُقاس أداء الخوارزمية من خلال الندم (Regret)، والذي يُعرف بأنه الفرق التراكمي بين التكلفة المتكبدة بواسطة خوارزمية التعلم والتكلفة المثلى تحت الديناميكيات الحقيقية. الهدف هو تحقيق ندم دون خطي ($O(\sqrt{T})$).

2. المنهجية

يقترح المؤلفون خوارزمية تعلم عبر الإنترنت معتمدة (الخوارزمية 1) تدمج تحديد هوية النظام مع ضمانات استقرار صارمة. تتكون المنهجية من أربع مراحل رئيسية:

أ. تقدير المعلمات مع مجموعات الثقة

• انحدار ريدج (Ridge Regression): يتم تقدير معلمات النظام $\Theta = [A, B_1, B_2]$ باستخدام المربعات الصغرى المنتظمة (regularized least squares) على بيانات الحالة والمدخلات المرصودة.
• شبه منحرف الثقة (Confidence Ellipsoid): يتم إنشاء مجموعة ثقة عالية الاحتمالية $\mathcal{C}_k(\delta)$ حول التقدير $\hat{\theta}_k$. تحتوي هذه المجموعة على المعلمة الحقيقية $\theta^*$ باحتمال $1-\delta$.

ب. اختيار النموذج البديل المعتمد (الابتكار الجوهري)

• المشكلة: قد يقع التقدير الخام $\hat{\theta}_k$ خارج المنطقة التي تسمح فيها معادلة GARE بحل مستقر، مما يؤدي إلى وحدات تحكم غير مستقرة.
• الحل: بدلاً من استخدام $\hat{\theta}_k$ مباشرة، تقوم الخوارزمية بخطوة تقلص (Shrinkage). حيث تبحث على طول القطعة المستقيمة التي تربط بين النموذج المعتمد السابق $\tilde{\theta}_{k-1}$ والتقدير الجديد $\hat{\theta}_k$.
• معيار الاختيار: تختار أكبر حجم خطوة $\alpha$ بحيث يحقق النموذج البديل الجديد $\tilde{\theta}_k = (1-\alpha)\tilde{\theta}_{k-1} + \alpha\hat{\theta}_k$ ما يلي:
  1. يظل ضمن مجموعة الثقة $\mathcal{C}_k(\delta)$.
  2. يقع في "منطقة انتظام" $\theta_{reg}(\mu, \gamma)$ حيث تكون معادلة GARE قابلة للحل، والحل موجب محدد، والنظام مغلق الحلقة مستقر (Schur stable) مع هوامش محددة.
• النتيجة: يضمن ذلك أن كل تحديث للسياسة هو قابل للتنفيذ ومستقر.

ج. تحديث التحكم والاستكشاف

• اليقين التام (Certainty Equivalence): بمجرد اختيار نموذج بديل معتمد $\tilde{\theta}_k$، يتم حل معادلة GARE للحصول على مكاسب التغذية الراجعة الجديدة $(K_k, L_k)$.
• الاستكشاف: لضمان الإثارة المستمرة (الضرورية لتقارب المعلمات)، يتم حقن ضوضاء غاوسية صغيرة في مدخلات التحكم.
• تكرار التحديث: يتم إعادة تقدير النموذج فقط عندما تنمو مصفوفة المعلومات بشكل كافٍ (باستخدام "خدعة المضاعفة"/doubling trick)، مما يحد من عدد التحديثات إلى $O(\log T)$.

د. تحليل الاضطراب المحلي

• يثبت المؤلفون أن الأخطاء الصغيرة في معلمات النموذج تؤدي إلى أخطاء متناسبة في حل ريكاتي وفي مكاسب التغذية الراجعة. هذا الاستمرار لـ "ليبتشيتز" (Lipschitz continuity) أمر بالغ الأهمية لحد التندم.

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

1. الخوارزمية المعتمدة: تطوير أول خوارزمية تعلم عبر الإنترنت لألعاب التربيع الخطي ذات لاعبين وصفر من المجموع مع ديناميكيات غير معروفة تضمن الاستقرار في كل خطوة من خلال آلية اختيار النموذج البديل المعتمد.
2. حد الندم: وضع حد ندم دون خطي قدره $O(\sqrt{T})$. ويتحقق ذلك من خلال تفكيك الندم إلى تكاليف عابرة، وتكاليف استكشاف، وتكاليف فجوة السياسة، وحد كل منها باستخدام خطأ التقدير وخصائص ليبتشيتز لحل GARE.
3. تحليل التقارب: إثبات صارم بأن المعلمات المقدرة ومكاسب التغذية الراجعة تتقارب إلى قيم توازن ناش الحقيقية، بشرط أن يستوفي النظام شرط الإثارة المستمرة.
4. إطار اختيار النموذج البديل: تقديم إجراء تقلص بنائي يسد الفجوة بين التقدير الإحصائي (مجموعات الثقة) والجدوى من منظور نظرية التحكم (قابلية حل GARE).

4. النتالئج

• المحاكاة العددية: تعرض الورقة محاكاة لنظام مكون من 3 حالات على مدى أفق زمني قدره $T=50,000$.
• تقارب المعلمات: يتناقص خطأ التقدير ($\|\tilde{\theta}_k - \theta^*\|_2$) وأخطاء مكاسب التغذية الراجعة ($\|K_k - K^*\|_F$) بمرور الوقت، مما يؤكد أن الخوارزمية تتعلم الديناميكيات الحقيقية.
• النموذج البديل مقابل التقدير الخام: تُظهر المحاكاة فجوة واضحة بين خطأ تقدير ريدج الخام وخطأ النموذج البديل المعتمد. يظل النموذج البديل أكثر تحفظًا لضمان الاستقرار، مما يثبت ضرورة خطوة التقلص.
• أداء الندم: يظل الندم الطبيعي ($\text{Reg}(T)/\sqrt{T}$) محدودًا ويستقر، مما يثبت تجريبيًا حد $O(\sqrt{T})$ النظري.

5. الأهمية

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

باختًا، تقدم الورقة البحثية نهجًا صارمًا رياضيًا وقابلًا للتطبيق عمليًا لتعلم استراتيجيات التحكم المثلى في البيئات العدائية غير المعروفة، مما يضمن أن كفاءة التعلم لا تأتي على حساب استقرار النظام.