Steady-state Based Approach to Online Non-stochastic Control

إليك ملخص تقني مفصل للورقة البحثية بعنوان "نهج قائم على الحالة المستقرة للتحكم عبر الإنترنت غير العشوائي" (Steady-state Based Approach to Online Non-stochastic Control) من تأليف هيبار وآخرون.

1. بيان المشكلة

تتناول الورقة البحثية التحكم عبر الإنترنت غير العشوائي (ONC)، وهو إطار عمل حيث يقوم متعلم بالتحكم في نظام خطي ثابت زمنياً (LTI) يخضع لاضطرابات عدائية ودوال تكلفة محدبة عدائية. الهدف هو تقليل التكلفة التراكمية عبر أفق زمني $T$.

• ديناميكيات النظام: $x_{t+1} = Ax_t + Bu_t + w_t$، حيث $x_t$ هي الحالة، و $u_t$ هو المدخل، و $w_t$ هو اضطراب عدائي.
• التحدي: يجب على المتعلم اختيار المدخلات $u_t$ دون معرفة التكاليف المستقبلية $f_t$ أو الاضطرابات $u_t$.
• مقياس الأداء: المقياس القياسي هو الندم (Regret)، والذي يُعرف بالفرق بين التكلفة التراكمية للمتعلم وأفضل تكلفة تكبدها أفضل متحكم في "فئة مرجعية" محددة تم اختيارها بعد فوات الأوان.

الفجوة:
عادةً ما تقارن أدبيات الـ ONC السابقة بين:

1. متحكمات التغذية الراجعة الخطية: (مثل Agarwal et al.) والتي قد يصعب تفسيرها بالنسبة للتكاليف المحدبة العامة.
2. حالات المدخلات الثابتة المستقرة: (عمل المؤلفين السابق [13]) والتي تقارن المتعلم بأفضل حالة مستقرة يمكن تحقيقها بواسطة مدخل ثابت $u$.
   • القصور: هذا المعيار المرجعي مقيد؛ فهو يتجاهل قدرة التحكم بالتغذية الراجعة على تثبيت النظام عند حالات مستقرة لا يمكن الوصول إليها عبر المدخلات الثابتة ذات الحلقة المفتوحة (open-loop)، خاصة في الأنظمة ناقصة التفعيل (underactuated systems).

الهدف:
يهدف المؤلفون إلى تصميم خوارزمية تحقق ندماً دون خطي (sublinear regret) مقابل معيار مرجعي أغنى: مجموعة كافة الحالات المستقرة التي يمكن الوصول إليها بواسطة متحكمات تآلفية مثبتة (affine stabilizing controllers) من الشكل $u_t = -Kx_t + v$، حيث $K$ هو كسب التثبيت و $v$ هو إزاحة ثابتة.

2. المنهجية

الحل المقترح، BatchFTPL، يجمع بين طريقة "اتبع القائد المضطرب" (Follow-the-Perturbed-Leader - FTPL) من التحسين غير المحدب عبر الإنترنت مع استراتيجية الدفعات (batching strategy) لضمان استقرار النظام.

أ. مجموعة المعيار المرجعي (متعدد الحالات المستقرة للحلقة المغلقة)

يعرف المؤلفون مجموعة المعيار المرجعي الجديدة $\mathcal{Z}$، وهي اتحاد جميع الحالات المستقرة التي يمكن تحقيقها بواسطة أي متحكم تآلفي مثبت بقوة:
$$\mathcal{Z} = \bigcup_{K \in \mathcal{K}} \{ z \mid z = (A - BK)z + Bv, \, v \in \mathcal{U} \}$$
حيث $\mathcal{K}$ هي مجموعة مكاسب التثبيت القوية.

• الصعوبة الرئيسية: بخلاف مجموعة المدخلات الثابتة، فإن $\mathcal{Z}$ غير محدبة بشكل عام لأنها اتحاد مجموعات محدبة مُعلمة بـ $K$. وهذا يستبعد الطرق القياسية القائمة على الإسقاط (مثل Gradient Descent المعتمد على الإسقاط).

ب. تصميم الخوارزمية: BatchFTPL

للتعامل مع عدم التحدب والطبيعة الديناميكية لتغيير المتحكمات، تستخدم الخوارزمية:

1. الدفعات (Batching): يتم تقسيم الأفق الزمني $T$ إلى دفعات بطول $H$.
2. تحديث FTPL: في بداية كل دفعة $n$، يختار المتعلم حالة مستقرة مستهدفة $z_n \in \mathcal{Z}$ باستخدام تحديث FTPL:
   $$z_n = \mathcal{O}_\epsilon \left( -\sum_{\tau=0}^{(n-1)H} f_\tau(z) + \langle \sigma, z \rangle, \mathcal{Z} \right)$$
   حيث $\sigma$ هو متغير عشوائي أسي (اضطراب) و $\mathcal{O}_\epsilon$ هو أوراكل تقليل تقريبي.
3. تخليق المتحكم (Controller Synthesis): بمجرد اختيار $z_n$، يجد المتعلم زوجاً $(K_n, v_n)$ بحيث تكون $z_n$ هي الحالة المستقرة للمتحكم $u = -K_n x + v_n$.
4. التنفيذ: يتم الإبقاء على المتحكم $(K_n, v_n)$ ثابتاً طوال مدة الدفعة ($H$ خطوة).

ج. آلية الاستقرار

يمكن أن يؤدي التبديل بين متحكمات مستقرة مختلفة إلى زعزعة استقرار النظام. يضمن المؤلفون الاستقرار من خلال:

• التثبيت القوي: استخدام متحكمات تضمن معدل تقارب محدد ($\gamma, \kappa$).
• اختيار حجم الدفعة: اختيار $H$ كبيرة بما يكفي (تحديداً $H \approx \frac{\ln(2\kappa)}{-\ln(1-\gamma)}$) بحيث تتقارب حالة النظام بالقرب من الحالة المستهدفة $z_n$ قبل تغيير المتحكم. هذا يخلق "تضاؤلاً هندسياً" لأخطاء التتبع من الدفعات السابقة.

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

1. تعريف معيار مرجعي أغنى: توسع الورقة إطار عمل ONC للحالة المستقرة من المدخلات الثابتة إلى المتحكمات التآلفية المثبتة. هذا يوسع فئة المقارنة بشكل كبير، مما يسمح للخوارزمية بالتنافس ضد المتحكمات التي تستخدم التغذية الراجعة للوصول إلى حالات مستقرة كانت تُعتبر سابقاً غير قابلة للتحقيق.
2. خوارزمية لـ ONC غير المحدب: يقترح المؤلفون BatchFTPL، وهي أول خوارزمية تحقق ندماً دون خطي مقابل مجموعة معيار مرجعي غير محدبة في ONC. لقد نجحت في التعامل مع عدم التحدب في \mathcal{Z ومخاطر الاستقرار الناتجة عن تبديل المتحكمات.
3. ضمانات الندم: يثبت المؤلفون أن الخوارزمية تحقق ندماً متوقعاً قدره $O(\sqrt{T})$ بالنسبة للمعيار التآلفي.
   • يعتمد حد الندم على بارامترات استقرار النظام ($\kappa, \gamma$) ودقة أوراكل التحسين ($\epsilon$).
   • من المهم ملاحظة أنهم أظهروا أن الحل التقريبي للمشكلة الفرعية غير المحدبة كافٍ؛ ولا يشترط التحسين الدقيق.
4. التعامل مع الاضطرابات: بينما يفترض التحليل النظري وجود اضطرابات صفرية لضمان الوضوح (باستخدام التراكب لفصل آثار الاضطراب)، فقد تم توسيع الطريقة للتعامل مع الاضطرابات العدائية في عمليات المحاكاة.

4. النتائج

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

• النظرية 8: تثبت أن الندم هو $O(\sqrt{T})$. هذا الحد مستقل عن الحالة (static regret)، على عكس حدود الندم الديناميكي التي غالباً ما تتناسب مع تغير المسار الأمثل.
• الاستقرار: تثبت اللمة 7 أن حالة النظام تظل محدودة طوال فترة التنفيذ، بشرط اختيار حجم الدفعة $H$ بشكل صحيح.

النتائج التجريبية (المحاكاة)

• الإعداد: نظام مكون من 3 حالات و مدخلين مع تكاليف تربيعية واضطرابات عدائية موحدة.
• المقارنة: تمت مقارنة BatchFTPL مع متحكم فعل الاضطراب (DAC) من Agarwal et al. [5].
• الأداء:
  • التكلفة: حققت BatchFTPL باستمرار تكلفة تراكمية أقل من DAC، مما يؤكد أن المعيار المرجعي التآلفي الأغنى يترجم إلى أداء عملي أفضل.
  • الحوسبة:
    • استدعاء أوراكل واحد في BatchFTPL أكثر تكلفة من تحديث DAC (حيث يقوم بمسح بنك من 100 كسب تثبيت وحل مشكلات فرعية محدبة).
    • ومع ذلك، ولأن BatchFTPL يحدّث السياسة مرة واحدة كل $H$ خطوة (بينما يحدث DAC كل خطوة)، فإن وقت التشغيل الإجمالي لـ BatchFTML كان أقل من DAC في التجارب.
  • الخلاصة: هذه الطريقة أكثر كفاءة في الأداء وفي الحوسبة في الإعداد المختبر، رغم التعقيد النظري للتحسين غير المحدب.

5. الأهمية والعمل المستقبلي

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

القيود والتوجهات المستقبلية:

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

باختصار، توفر هذه الورقة أساساً نظرياً رصيناً وخوارزمية عملية للتحكم عبر الإنترنت تتفوق على الطرق الموجودة من خلال الاستفادة من معيار مرجعي أقوى يعتمد على التغذية الراجعة، مع الحفاظ على ضمان الندم $O(\sqrt{T})$ الضروري للتعلم عبر الإنترنت.