Communication-Efficient Federated Online Decision-Making with Stateful Costs

ملخص تقني: اتخاذ القرار عبر الإنترنت في بيئة اتحادية كفؤة في الاتصالات مع تكاليف مرتبطة بالحالة

صياحة المشكلة
تتناول هذه الورقة تحدي اتخاذ القرار عبر الإنترنت في الأنظمة الاتحادية (Federated) حيث تؤدي القرارات إلى دفع حالة تشغيلية متطورة، وتُتكبد التكاليف بناءً على مسار الحالة الناتج. وخلافًا للتعلم الاتحادي القياسي الذي يحسن الأهداف النقطية، أو التحكم عبر الإنترنت التقليدي الذي يفترض توفر معلومات كاملة، يتضمن هذا الإعداد خادمًا مركزيًا و$N$ من العملاء يعملون تحت نظام تزامن قائم على الكتل المتفرقة (sparse block-based synchronization) ومشاركة جزئية للعملاء.

ينشأ الصعوبة الجوهرية من التفاعل بين قيود الاتصال وديناميكيات النظام:

1. التكاليف المرتبطة بالحالة (Stateful Costs): تعتمد التكلفة عند الزمن $t$، وهي $c_t(\chi_t, u_t)$، على حالة النظام $\chi_t$، التي تتطور وفقًا لديناميكيات خطية $\chi_{t+1} = A\chi_t + Bu_t + Ed_t$.
2. الاتصال المتفرق (Sparse Communication): يتم تحديث القرارات فقط عند حدود الكتل (كل $K$ جولة). وخلال الكتلة الواحدة، تظل القرار $u_t$ ثابتًا ($u_t = \bar{u}_b$).
3. عدم تطابق المسار (Trajectory Mismatch): نظرًا لأن النظام التشغيي يتطور باستمرار بينما يظل القرار ثابتًا داخل الكتلة، فإن القرار القديم (stale decision) يدفع النظام على طول مسار حالة مختلف عن المسار الذي كان سيحققه قرار مثالي لكل جولة، مما يغير التكلفة التراكمية المتكبدة.
4. الندم الديناميكي (Dynamic Regret): تُقاس الأداء بالنسبة لتسلسل مقارن $u^\star_{1:T}$ محدود بطول المسار، والذي يمكن أن يتغير عند كل جولة (ضمن ميزانية إجمالي التباين $V_T$)، ولكنه ليس مقيدًا ببروتوكول الاتصال المتفرق.

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

المنهجية: BLADE
يقترح المؤلفون خوارزمية BLADE (التقريب المحلي القائم على الكتل للتنفيذ الديناميكي)، وهي طريقة اتخاذ قرار اتحادي عبر الإنترنت قائمة على الكتل والمشاريع (projected blockwise). تعمل الخوارزمية كما يلي:

• التحديثات القائمة على الكتل: يتم تقسيم الأفق الزمني إلى كتل بطول $K$. يحتفظ الخادم بمتغير كتلة $\bar{u}_b$ يتم نشره لجميع الجولات في الكتلة.
• البدائل ذات الذاكرة المحدودة: للتعامل مع الطبيعة المرتبطة بالحالة دون الحاجة إلى التاريخ الكامل، تستخدم BLADE تقريبًا ذا ذاكرة محدودة للحالة. حيث تُعرف "حالة بديلة قطرية" $\bar{\chi}_t(u)$ حيث يُفترض أن جميع الإجراءات ضمن نافذة ذاكرة $H$ هي القرار المرشح الحالي $u$.
• التفكك المحلي: يُفترض أن التكلفة البديلة القطرية تقبل التفكك المحلي، $c_t(\bar{\chi}_t(u), u) = \frac{1}{N}\sum c_{i,t}(u)$، مما يسمح للعملاء بحساب التدرجات المحلية.
• المشاركة الجزئية: في نهاية كل كتلة، يتم أخذ عينة من $m$ من العملاء لحساب وإرجاع مجموع التدرجات عبر الكتلة. يقوم الخادم بتحديث متغير الكتلة التالية عبر خطوة تدرج مسقط:
  $$\bar{u}_{b+1} = \Pi_Z \left( \bar{u}_b - \eta_B \frac{1}{m} \sum_{i \in S_b} \sum_{t \in I_b} \nabla c_{i,t}(\bar{u}_b) \right)$$

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

1. صياغة المشكلة: تصيغ الورقة مشكلة جديدة لاتخاذ القرار عبر الإنترنت الاتحادي حيث يؤثر الاتصال المتفرق ليس فقط على خطأ التحسين ولكن أيضًا على مسار الحالة الواقعي والتكاليف المتكبدة الناتجة عنه.
2. تصميم الخوارزمية: تقدم خوارزمية BLADE، التي تدمج التزامن القائم على الكتل، وتقريب الحالة ذات الذاكرة المحدودة، والمشاركة الجزئية للعملاء في إطار موحد للتكاليف المرتبطة بالحالة.
3. التحليل النظري: يستنتج المؤلفون حد الندم الديناميكي لـ التكلفة المتكبدة (ليس فقط خسارة بديلة). يفصل الحد صراحةً مصادر الخطأ:
   • خطأ التحسين الناتج عن الهبوط عبر الإنترنت المسقط.
   • خطأ أخذ العينات الناتج عن المشاركة الجزئية.
   • خطأ عدم تطابق المسار الناتج عن تثبيت القرارات داخل الكتل.
   • خطأ بتر الذاكرة المحدودة.
4. ضمانات الندم: في حالة الإعداد $K = \lceil \sqrt{T} \rceil$، تثبت الورقة أن الندم الديناميكي المتوقع هو دون خطي في $T$ بشرط أن يكون تباين المقارن $V_T = o(T^{1/4})$. كما أظهر أن التعقيد الاتصالي هو $O(\sqrt{T})$.

النتائج والتحقق
تم التحقق من الحدود النظرية من خلال تجارب على نظام خطي مستقر اصطناعي متحكم به. تعزل التجارب الآليات التي تنبأت بها النظرية:

• المقايضة بين الاتصال والندم: يؤدي زيادة طول الكتلة $K$ إلى تقليل عدد مرات الاتصال ولكنه يزيد من الندم الديناميكي، مما يؤكد المقايضة النظرية.
• طول الذاكرة: تؤدي زيادة نافذة الذاكرة $H$ إلى تقليل الندم حتى يصبح خطأ البتر ضئيلاً، وهو ما يتوافق مع الاضمحلال الهندسي لديناميكيات النظام.
• المشاركة الجزئية: تؤدي نسب المشاركة المنخفضة ($m/N$) إلى زيادة الندم بسبب زيادة ضوضاء أخذ العينات.
• تباين الاضطرابات: تؤدي زيادة التباين في الاضطرابات الخارجية إلى زيادة الندم المتكبد، كما هو متوقع لمخطط ديناميكي.
• توسع الأفق: تتوسع تكلفة الاتصال بمعدل $O(\sqrt{T})$ عندما تكون $K = \lceil \sqrt{T} \rceil$، وهو ما يطابق التنبؤ النظري.

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

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