Regret Bounds for Expected Improvement Algorithms in Gaussian Process Bandit Optimization

ملخص تقني لورقة بحثية: حدود الندم لخوارزميات التحسين بالتحسين المتوقع (Expected Improvement) في خوارزميات "بانديت" العمليات الغاوسية (Gaussian Process Bandits).

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

تتناول الورقة مشكلة تحسين بانديت العمليات الغاوسية (GP-Bandit Optimization)، وتحديداً في إطار غير بايزي (حيث تكون الدالة ثابتة ولكن مجهولة وتقع في فضاء هيلبرت لإعادة الإنتاج - RKHS). الهدف هو اختيار نقاط $x_t$ بالتتابع لتعظيم دالة "الصندوق الأسود" المكلفة $f(x)$ بناءً على ملاحظات مشوبة بالضجيج $y_t = f(x_t) + \epsilon_t$.

يُقاس الأداء من خلال الندم التراكمي $R_T = \sum_{t=1}^T (f(x^*) - f(x_t^+))$، حيث $x^*$ هي القيمة المثلى العالمية و $x_t^+$ هي أفضل نقطة أبلغت عنها الخوارزمية حتى اللحظة $t$.

التحدي الجوهري:
بينما تُعد خوارزمية التحسين المتوقع (Expected Improvement - EI) نموذجاً رائجاً للتحسين البايزي نظراً لبساطتها، إلا أن خصائص تقاربها النظرية في الإطار المشوب بالضجيج ظلت سؤالاً مفتوحاً.

• في الحالات الخالية من الضجيج، يكون "المستقر" (incumbent) -أي أفضل قيمة حالية- هو ببساطة القيمة القصوى الملحوظة، وهي دالة رتيبة.
• في الحالات المشوبة بالضجيج، يتم تعريف المستقر عادةً كأقصى قيمة لـ المتوسط التنبؤي للعملية الغاوسية ($\mu_t^+$) أو أقصى قيمة للملاحظة المشوبة بالضجيج ($y_t^+$).
• بخلاف الحالة الخالية من الضجيج، فإن المتوسط التنبؤي للعملية الغاوسية $\mu_t^+$ ليس رتيباً بمرور الوقت. هذا الافتقار إلى الرتابة يجعل التحليل النظري القياسي (الذي يعتمد على حصر الندم عبر رتابة المستقر) أمراً صعباً للغاية. تطلبت الأعمال السابقة إما معرفة المعلمات المجهولة (مثل حد معيار RKHS $B$ وخاصية الضجيج تحت-غاوسية $R$) أو استخدمت مستقرات غير قياسية تتطلب خطوات تحسين عالمية مكلفة.

2. المنهجية

يقترح المؤلفون خوارزميتين لسد هذه الفجوات النظرية والعملية.

أ. خوارزمية GP-EI مع المستقر القياسي

المساهمة الأولى هي تحليل دقيق لخوارزمية GP-EI قياسية، حيث يتم تعريف المستقر كأقصى قيمة للمتوسط التنبؤي للعملية الغاوسية فوق النقاط المرصودة:
$$\xi_t = \mu_t^+ = \max_{x_i \in D_{t-1}} \mu_{t-1}(x_i)$$

• دالة الاستحواذ (Acquisition Function): تختار الخوارزمية النقطة التالية $x_t$ عن طريق تعظيم التحسين المتوقع:
  $$\alpha_{EI}(x) = \mathbb{E}[\max\{0, f(x) - \mu_t^+\} | D_t]$$
  ويتم حساب ذلك في شكل مغلق باستخدام الدالة $\rho(u, v) = u\Phi(u/v) + v\phi(u/v)$.
• عامل القياس المتغير زمنياً: للتعامل مع الضجيج وضمان التقارب دون معرفة معيار RKHS ($B$) أو معلمة الضجيج ($R$)، تستخدم الخوارزمية معامل قياس متغيراً زمنياً $\omega_t = \sqrt{\gamma_{t-1} + 1 + \ln(1/\delta)}$، حيث $\gamma_t$ هو أقصى كسب للمعلومات.
• الابتكار النظري الرئيسي: يتغلب المؤلفون على عدم رتابة $\mu_t^+$ من خلال استغلال رتابة دالة التباين ($\sigma_t(x)$ التي تتناقص مع زيادة $t$). يقومون بتفكيك الندم اللحظي وحصر مجموع "مصطلحات التحسين" باستخدام خاصية التباين هذه، وهي تقنية لم تُطبق بهذا الشكل سابقاً في تحسين بانديت العمليات الغاوسية.

ب. خوارزمية Improved-GP-EI

لمعالجة قيود خوارزمية GP-EI القياسية (تحديداً أن حد الندم لنواة ماتيرن - Matérn kernels - ليس دائماً دون خطي، وأن معامل القياس $\omega_t$ ينمو بسرعة كبيرة مما يسبب استكشافاً غير ضروري)، يقترح المؤلفون Improved-GP-EI.

• الإلهام: مستوحاة من خوارزمية $\pi$-GP-UCB (Janz et al., 2020).
• استراتيجية التقسيم: يتم تقسيم فضاء البحث إلى مكعبات فائقة (hypercubes) - أي غطاء (covering). وفي كل مكعب، يتم ملاءمة عملية غاوسية مستقلة باستخدام البيانات المحلية فقط.
• القياس العالمي: بدلاً من $\omega_t$ المتغير زمنياً، يتم استخدام قياس عالمي ثابت $\omega_T = \sqrt{\ln(T)\ln\ln(T)}$، والذي ينمو بشكل لوغاريتمي متعدد فقط.
• الآلية: في كل خطوة، تختار الخوارزمية نقطة عن طريق تعظيم التحسين المتوقع (EI) داخل المكعب الفائق الذي يحتوي على أفضل مرشح حالي، مما يؤدي فعلياً إلى توطين عملية التحسين.

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

1. أول ضمانات نظرية لـ GP-EI القياسية:
   تقدم الورقة أول إثبات بأن خوارزمية GP-EI مع مستقر قياسي ($\xi = \mu_t^+$) تتقارب في الإطار المشوب بالضجيج.

   • حد الندم: يُحصر الندم التراكمي بـ $O(\gamma_T \sqrt{T})$.
   • الاستقلالية عن المعلمات: من المهم ملاحظة أن الخوارزمية لا تتطلب معرفة بمعيار RKHS ($B$) أو معلمة الضجيج تحت-الغاوسية ($R$)، وهي معلمات مجهولة عادة في التطبيقات الواقعية.

2. خوارزمية Improved-GP-EI:
   نسخة جديدة تحقق معدلات تقارب أسرع لنواة ماتيرن.

   • حد الندم: بالنسبة لنواة ماتيرن ذات النعومة $\nu > 1$، يكون الندم $\tilde{O}(T^{\frac{d(2d+3)+2\nu}{d(2d+4)+4\nu}})$. هذا الناتج دون خطي لجميع قيم $\nu > 1$ و $d \geq 1$، مما يحسن من قيود GP-EI القياسية.
   • الكفاءة: من خلال استخدام استراتيجية التقسيم ومعامل قياس لوغاريتمي متعدد، تتجنب الخوارزمية النمو السريع لمقياس التباين الملاحظ في الطرق السابقة وتقلل من الاستكشاف غير الضروري.

3. تقنيات إثبات مبتكرة:
   قدم المؤلفون استراتيجية إثبات تتعامل مع عدم رتابة مستقر المتوسط التنبؤي للعملية الغاوسية من خلال الاستفيد من الرتابة التناقصية لدالة التباين للعملية الغاوسية لحصر مجموع مصطلحات التحسين.

4. النتائج

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

• Standard GP-EI: تحقق ندماً قدره $O(\gamma_T \sqrt{T})$. بالنسبة لنواة التربيع الأسي (SE)، هذا الناتج دون خطي. وبالنسبة لنواة ماتيرن، فهو دون خطي إذا كان $2\nu > d$.
• Improved-GP-EI: تحقق حداً أدق للندم وهو دون خطي لجميع قيم $\nu > 1$. وهي تماثل معدل ندم $\pi$-GP-UCB ولكنها تلغي الحاجة لمعرفة $B$ و $R$.

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

اختبر المؤلفون خوارزمياتهم على دوال اصطناعية (Hartmann3, Shekel, Hartmann6, Ackley) ودوال مولدة من فضاءات RKHS.

• الأداء: تفوقت Improved-GP-EI باستمرار على Standard GP-EI، و Modified-GP-EI، و $\pi$-GP-UCB المتطورة.
• المتانة: على عكس $\pi$-GP-UCB، التي تتطلب ضبطاً تجريبياً للمعلمات المجهولة ($B$ و $R$) وتؤدي أداءً سيئاً عند تخمينها بشكل خاطئ، فإن Improved-GP-EI خالية من المعلمات فيما يتعلق بهذه الحدود وأظهرت استقراراً فائقاً.
• الكفاءة: قللت استراتيجية التقسيم في Improved-GP-EI من التعقيد الحسابي. على سبيل المثال، كان متوسط وقت التشغيل لكل تكرار في Hartmann3 هو 1.21 دقيقة لـ Improved-GP-EI مقارنة بـ 1.37 دقيقة لـ Standard GP-EI، مع اتساع الفجوة عند الآفاق الزمنية الكبيرة بسبب صغر حجم عمليات قلب مصفوفة النواة (قلب مصفوفات محلية أصغر بدلاً من مصفوفة عالمية).

5. الأهمية

تحل هذه الورقة مشكلة طويلة الأمد في التحليل النظري للتحسين المتوقع في بانديت العمليات الغاوسية.

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