ملخص تقني: الندم شبه الأمثل في نطاقات النواة التنافسية (Near-Optimal Regret in Adversarial Kernel Bandits)

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

تتناول الورقة مشكلة نطاق النواة التنافسي (adversarial kernel bandit)، وهي تعميم لنطاقات الخطية التنافسية حيث تنتمي دالات الخسارة إلى فضاء هيلبرت لإعادة الإنتاج (RKHS).

• الإعداد: في كل جولة $t \in [T]$، يختار المتعلم إجراءً $x_t$ من مجموعة إجراءات منتهية $\mathcal{X} \subset \mathbb{R}^d$. وفي الوقت نفسه، يختار خصم غافل (oblivious adversary) متجهًا $w_t$ في فضاء RKHS.
• الخسارة: يتكبد المتعلم خسارة $\ell_t(x_t) = \langle \Phi(x_t), w_t \rangle_{\mathcal{H}}$، حيث $\Phi: \mathcal{X} \to \mathcal{H}$ هي خريطة الميزات المرتبطة بنواة متماثلة وموجبة التحديد $K$.
• التغذية الراجعة: لا يلاحظ المتعلم سوى الخسارة القياسية $\ell_t(x_t)$، وليس المتجه $w_t$ أو دالة الخسارة الكاملة.
• الهدف: تقليل الندم المتوقع $R_T$ مقابل أفضل إجراء ثابت $x^*$ في الماضي:
  $$R_T = \mathbb{E}\left[ \sum_{t=1}^T \langle \Phi(x_t), w_t \rangle_{\mathcal{H}} - \sum_{t=1}^T \langle \Phi(x^*), w_t \rangle_{\mathcal{H}} \right]$$
• الافتراضات: الخصم محدود ($\|w_t\|_{\mathcal{H}} \le B$)، والنواة محدودة ($K(x,x) \le 1$). وبخلاف العمل السابق لـ Chatterji et al. [2019]، فإن الخصم ليس مقيدًا بخسائر ذات رتبة واحدة (أي أن $w_t$ ليس بالضرورة على شكل $\Phi(z_t)$)؛ حيث يمكن أن يكون $w_t$ أي عنصر في $\mathcal{H}$ بمعيار محدود.

2. المنهجية والخوارزمية

تقترح الورقة خوارزمية تعتمد على الأوزان الأسية (Exp2) المكيفة مع فضاءات الميزات ذات الأبعاد اللانهائية. التحدي الجوهري هو أن المقدرات الموزونة بالأهمية القياسية في النطاقات الخطية تصبح غير محدودة عندما تكون خريطة الميزات في فضاء RKHS ذي أبعاد لانهائية بسبب تلاشي القيم الذاتية لمؤثر التباين.

للتغلب على ذلك، قدم المؤلفون تعديلين رئيسيين:

1. المقدر الموزون بالأهمية المنظم (Regularized Importance-Weighted Estimator):
   بدلاً من عكس مؤثر التباين التجريبي $\Sigma_t = \mathbb{E}_{x \sim p_t}[\Phi(x)\Phi(x)^\top]$، تستخدم الخوارزمية نسخة منظمة بـ "القمة" (ridge-regularized) $\Sigma_t^\lambda = \Sigma_t + \lambda I_{\mathcal{H}}$. يضمن هذا التنظيم بقاء المقدر محدودًا حتى عندما تكون القيم الذاتية لـ $\Sigma_t$ قريبة من الصفر. ومع ذلك، فإن هذا التنظيم يُدخل انحيازًا منهجيًا: $\mathbb{E}[\hat{w}_t | \mathcal{F}_{t-1}] = (\Sigma_t^\lambda)^{-1}\Sigma_t w_t \neq w_t$.

2. حد تصحيح الانحياز الصريح (Explicit Bias Correction Term):
   لتعويض انحياز التنظيم، تبني الخوارزمية نموذج خسارة بديل مصحح $\hat{\ell}_t(x)$:
   $$\hat{\ell}_t(x) = \langle \hat{w}_t, \Phi(x) \rangle_{\mathcal{H}} - c_t(x)$$
   حيث حد التصحيح $c_t(x) = B\sqrt{\lambda} \|\Phi(x)\|_{(\Sigma_t^\lambda)^{-1}}$.

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

3. استراتيجية الاستكشاف:
   تحافظ الخوارزمية على توزيع $p_t$ وهو مزيج من توزيع الأوزان الأسية الحالي $q_t$ وتوزيع استكشاف ثابت $\nu_G$. يتم اختيار توزيع الاستكشاف عبر تصميم G-optimal منظم لضمان التحكم في البعد الفعال.

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

• تصميم الخوارزمية: خوارزمية مبدئية تجمع بين الأوزان الأسية مع مقدر منظم وحد تصحيح انحياز صريح. يتجنب هذا النهج فرضية الخصم ذات الرتبة الواحدة التي تطلبها أعمال Chatterji et al. [2019].
• تحليل الندم عبر البعد الفعال: يستنتج المؤلفون حدًا للندم يعتمد على البعد الفعال $d^*(\lambda)$ للنواة، والمعرف كالتالي:
  $$d^*(\lambda) = \max_{\nu \in \Delta(\mathcal{X})} \text{Tr}\left( (\Sigma(\nu) + \lambda I_{\mathcal{H}})^{-1} \Sigma(\nu) \right)$$
• إزالة فرضية الرتبة الواحدة: يسمح الإطار بنطاقات RKHS عشوائية (arbitrary) محدودة، مما يوسع نطاق التطبيق بشكل كبير مقارنة بالأعمال السابقة التي اعتمدت على مقدرات قائمة على الإسقاط تتطلب قيود الرتبة الواحدة.

4. النتائج الرئيسية

تثبت الورقة حدًا للندم على شكل:
$$R_T = \tilde{O}\left( B \sqrt{T d^*(\lambda) \log |\mathcal{X}|} \right)$$
حيث يلتقط $d^*(\lambda)$ تعقيد النواة. وهذا المعدل يطابق المعدلات المثلى المعروفة لنطاقات النواة العشوائية (stochastic kernel bandit) (مع مراعية العوامل اللوغاريتمية).

معدلات النواة المحددة:

• نواة Matérn$(\nu, d)$: بالنسبة لنواة Matérn ذات النعومة $\nu$ على $\mathbb{R}^d$، يعطي البعد الفعال حدًا للندم قدره:
  $$R_T = \tilde{O}\left( T^{\frac{\nu+d}{2\nu+d}} \right)$$
  وهذا يحسن المعدل الأفضل المعروف سابقًا وهو $\tilde{O}(T^{\frac{2\nu+d}{4\nu}})$ بواسطة Chatterji et al. [2019] ويطابق الحد الأدنى من العمل المتزامن [Iwazaki, 2026] مع مراعاة العوامل اللوغاريتمية. ومن الجدير بالذكر أن المعدل السابق لم يكن حتى دون خطي (sublinear) عندما $\nu < d/2$، بينما الحد الجديد دائمًا دون خطي.
• نواة الأس التربيعي (SE Kernel): يستعيد الحد المعدل القريب من الأمثل $\tilde{O}(\sqrt{T})$، مطابِقًا Chatterji et al. [2019] ولكن بدون قيود الرتبة الواحدة.
• الاضمحلال متعدد الحدود العام ($\mu_j \le C j^{-\beta}$): يحقق $R_T = \tilde{O}(T^{\frac{\beta+1}{2\beta}})$.
• الاضمحلال الأسي ($\mu_j \le C e^{-\beta j}$): يحقق $R_T = \tilde{O}(\sqrt{T})$.

5. الأهمية والادعاءات

تدعي الورقة سد الفجوة بين أداء النطاقات النووية التنافسية والعشوائية. وتحديدًا:

• المثالية: تطابق المعدلات المستمدة المعدلات المثلى المعروفة للنطاقات النووية العشوائية (على سبيل المثال، عبر SupKernelUCB أو طرق التحسين البايزي) مع مراعاة العوامل اللوغاريتمية.
• التقدم النظري: من خلال إزالة فرضية الخصم ذات الرتبة الواحدة، تنطبق النتائج على فئة أكثر عمومية وواقعية من البيئات التنافسية حيث تكون دالة الخسارة عنصرًا محدودًا عشوائيًا في RKHS.
• المقارنة بالأعمال السابقة: يحسن هذا العمل من نتائج Chatterji et al. [2019] لنواة Matérn والاضمحلال متعدد الحدود العام، مما يوفر حدودًا أكثر دقة وهي دون خطية في $T$ في الظروف التي لم تكن فيها الحدود السابقة كذلك.
• العمل المتزامن: يقر المؤلفون بوجود عمل متزامن مستقل من قبل Iwazaki [2026] يحقق نتائج مماثلة باستخدام نهج وثيق الصلة (الأوزان الأسية مع المقدرات المنظمة وتصحيح الانحياز). تشير الورقة إلى اختلافات طفيفة في إعداد المشكلة (مثل الخصم الغافل مقابل التكيفي، ومقاييس التعقيد المحددة) لكنها تؤكد أن المساهمات الخوارزمية والتحليلية الجوهرية متكافئة أساسًا.

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