Information Routing across Batch Boundaries: Memory--Batch Tradeoffs in Lipschitz Bandits

ملخص تقني: توجيه المعلومات عبر حدود الدفعات في خوارزميات "ليبتشيتز بانديتس" (Lipschitz Bandits)

صياغة المشكلة
تتقصى هذه الورقة المقايضة الجوهرية بين عرض الحالة (الذاكرة) وعمق التحديث (التكيف مع الدفعات) في مسائل "ليبتشيتز بانديتس" العشوائية. يتضمن الإعداد تفاعل متعلم مع دالة مكافأة متوسطة مجهولة $f: [0, 1]^d \to [0, 1]$ وهي دالة "ليبتشيتز" بقيمة 1 في معيار الـ "sup-norm". يعمل المتعلم تحت قيدين متزامنين:

1. الذاكرة ($W$): بعد كل سحبة، يحتفظ المتعلم بـ $W$ بت كحد أقصى من الحالة المتغيرة المعتمدة على المكافأة.
2. الدفعات ($B$): تُقسم أفعال المتعلم إلى ما لا يتجاوز $B$ من الدفعات الملتزمة. عند حد الدفعة، تقوم الحالة الحالية بتثبيت (commit) الدفعة التالية وكامل تسلسل الأفعال لتلك الدفعة. تُحدث المكافآت المرصودة داخل الدفعة الحالة عبر الإنترنت (online)، ولكنها لا تستطيع تغيير شريط الأفعال الملتزم به بالفعل.

الهدف هو توصيف الحد الأدنى للأقصى (minimax) للندم الزائف المتوقع، $R_T(B, W)$، كدالة لـ $T$ (الأفق)، و $d$ (البعد)، و $W$ (ميزانية الذاكرة)، و $B$ (ميزانية الدفعات).

المنهجية والنهج التقني
يضع المؤلفون جبهة "المينيمكس" (minimax frontier) عبر بناء "عائلة صعبة" من نماذج المسائل التي تكشف عن عائقين مختلفين للموارد في آن واحد:

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

بناء الحد الأدنى (Lower Bound Construction):
يعتمد بناء الحد الأدنى على بناء هندسي يتضمن $m \asymp s^{-d}$ من أزواج المناطق المنفصلة عند المقياس $s$. داخل كل منطقة، توجد $q \asymp (s/r)^d$ من المجسات (probes) عند مقياس أدق $r$. يقوم متجه توجيه كامن $V \in \{0, 1\}^m$ باختيار الجانب "الجيد" من كل زوج.

• قيد توجيه المعلومات: لتحقيق ندم منخفض، يجب على المتعلم تحديد الجانب الصحيح من كل زوج. يتطلب هذا أن يقوم نص الأفعال الملتزم به بتشفير $\Theta(s^{-d})$ بت من المعلومات حول $V$.
• عنق زجاجة الإنتروبيا: يتم تحديد إجمالي إنتروبيا حالات الحدود عبر $B$ من الدفعات بـ $(B-1)W$. باستخدام حجة "تغيير القياس المتوقف" (stopped change-of-measure) ومعادلة "فانو" (Fano's inequality)، يوضح المؤلفون أنه إذا كانت ميزانية إنتروبيا حالة الحدود غير كافية لتشفير قرارات التوجيه، فإن المتعلم سيتكبد ندماً مرتفعاً بسبب توجيه جهود التحقق بشكل خاطئ إلى مناطق غير مختارة.
• عائق عمق التحديث: يوفر بناء شبكة تكيفي منفصل (مقتبس من Feng et al., 2024) حداً أدنى يعتمد فقط على $B$، وبشكل مستقل عن $W$، مما يظهر أنه حتى مع ذاكرة لانهائية، فإن الدفعات المحدودة تقيد معدل الصقل (refinement).

بناء الحد الأعلى (Upper Bound Construction):
يستخدم الحد الأعلى المطابق سياسة تحافظ على قناع المجموعة النشطة الآمنة (safe active-set mask) (وهو متجه ثنائي يشير إلى المناطق التي تحتوي على محتملات التعظيم) بينما تقوم ببث ومحو إحصائيات التحقق دقيقة التفاصيل.

• الحدود الثابتة: تستخدم السياسة حدود دفعات ثابتة.
• التسلسل مقابل الهرمية:
  • عندما يتسع قناع المجموعة النشطة في الذاكرة ($W$ كبيرة)، يستخدم المتعلم صقلاً هرمياً داخل الذاكرة لتحديث جميع الإحداثيات في وقت واحد.
  • عندما يتجاوز القناع الذاكرة، يستخدم المتعلم بناءً تسلسلياً. يقوم بإعادة توليد أجزاء من القناع بحجم الذاكرة، ويستخدمها للالتزام بالمجسات الفرعية المقابلة، ويحدث سجلاً لأفضل طفل عالمي (global best-child record)، ثم يمحو الجزء. يسمح هذا للمتعلم بمعالجة المجموعة النشطة في أجزاء دون تجاوز حد الـ $W$ بت.
• الآلية الرئيسية: يتم تجميع إحصائيات التحقق عبر الإنترنت، ومقارنتها مع سجل "أفضل ذراع" مقيم، ومحوها فوراً. فقط قناع المجموعة النشطة (أو أجزائه) وسجلات التحكم اللوغاريتمية هي التي تستمر عبر الحدود.

النتائج الرئيسية
تحدد الورقة ندم "المينيمكس" حتى العوامل اللوغاريتمية. يتم التحكم في الندم بواسطة أسوأ ثلاثة عوائق:

1. التقدير المتسلسل: $T^{(d+1)/(d+2)}$ (معدل "ليبتشيتز بانديتس" القياسي).
2. عمق الدفعة: حد يعتمد على $B$ مشتق من قيود الشبكة التكيفية.
3. تفاعل العرض والعمق: حد جديد يلتقط القيد المشترك:
   $$T^{\frac{d+2}{d+3}} \left(1 + (B-1)W\right)^{-\frac{1}{d(d+3)}}$$

الجبهة الرسمية (Theorem 3.4):
عندما يكون $W \gtrsim_d \log(eT)$، فإن ندم المينيمكس يحقق:
$$R_T(B, W) \asymp \max \left( T^{\frac{d+1}{d+2}}, \frac{T^{\beta_{d,B}}}{B^2}, T^{\frac{d+2}{d+3}} (1 + (B-1)W)^{-\frac{1}{d(d+3)}} \right)$$
حيث $\beta_{d,B} = \frac{d+1}{d+2} \frac{1}{1 - (d+2)^{-B}}$.

حالات خاصة وتضمينات:

• الذاكرة غير المقيدة ($W \to \infty$): يستعيد النتيجة الكاملة لجبهة "الدفعات فقط" التي وضعها Feng et al. (2024).
• التسلسل الكامل ($B=T$): يستعيد ندم المينيمكس المتسلسل مع ذاكرة لوغاريتمية ($W \asymp \log T$)، بما يتوافق مع Zhu and Huang (2025).
• عدم التبادلية: يظهر حاصل الضرب $(B-1)W$ في الأس، مما يثبت أن عرض الحالة وعمق التحديث هما مكملان، وليسا بدائل. لا يمكن لـ حالة واحدة عريضة أن تحل محل سلسلة من الحالات الأضيق التي يُعاد حسابها بين جولات الاستكشاف بشكل عام.
• تعقيد الدفعات: لتحقيق ندم قريب من التسلسلي، يجب أن يتوسع عدد الدفعات $B$ كـ $\log \log T$ (إذا كانت $W$ كافية)، ويجب أن تتوسع إنتروبيا حالة الحدود $(B-1)W$ كـ $T^{d/(d+2)}$.

الأهمية والادعاءات
تدعي الورقة أنها حلت السؤال الهيكلي حول كيفية تحديد الذاكرة والتكيف للأداء بشكل مشترك في الأمثلة غير المعلمية (nonparametric optimization).

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

يشير المؤلفون إلى أن إزالة الخسائر اللوغاريتمية، وتوصيف نظام الذاكرة دون اللوغاريتمي، والحصول على نظائر تعتمد على الحالة (instance-dependent) تظل مسائل مفتوحة.