Stochastic Linear Bandits with Parameter Noise

ملخص تقني: النطاقات الخطية العشوائية مع ضجيج المعلمات

تعريف المشكلة
يبحث هذا العمل في نموذج النطاقات الخطية العشوائية مع ضجيج المعلمات (stochastic linear bandits with parameter noise). في هذا الإعداد، يتفاعل المتعلم مع بيئة عبر أفق زمني $T$ من خلال اختيار إجراءات $a_t$ من مجموعة إجراءات $\mathcal{A} \subseteq \mathbb{R}^d$. وخلافًا لنموذج الضجيج الجمعي القياسي حيث تكون المكافأة $X_t = a_t^\top \theta^\star + \eta_t$ (مع $\theta^\star$ ثابت و$\eta_t$ ضجيج)، يفترض نموذج ضجيج المعلمات أن المكافأة تُعطى بـ $X_t = a_t^\top \theta_t$، حيث يتم أخذ عينات $\theta_t$ بشكل مستقل ومتماثل التوزيع (i.i.d.) من توزيع ثابت مجهول $\nu$ بمتوسط $\theta^\star$ ومصفوفة تغاير (covariance matrix) $\Sigma$.

يسلط البحث الضوء على تميز جوهري: في نموذج ضجيج المعلمات، يمكن للمتعلم التأثير على تباين المكافأة. تحديدًا، $\text{Var}(X_t) = a_t^\top \Sigma a_t$، بينما في نموذج الضجيج الجمعي، يتم تحديد التباين بواسطة البيئة وحدها. ويشير المؤلفون إلى أنه بينما يعد نموذج ضجيج المعلمات تخفيفًا (relaxation) لنموذج النطاقات الخطية الخصمي (adversarial linear bandit model) -حيث يتم اختيار $\theta_t$ من قبل خصم- فإنه يقدم خصائص هيكلية فريدة تسمح بالحصول على حدود ندم (regret bounds) قد تكون أكثر إحكامًا من نموذج الضجيج الجمعي في إعدادات هندسية معينة.

المنهجية والخوارزميات
يقترح المؤلفون خوارزميتين مصممتين لمجموعات إجراءات ذات هندسات مختلفة:

1. VASE (التخلص المتتالي القائم على التصميم الأمثل الواعي بالتباين):

   • الهدف: مجموعات الإجراءات المنتهية العامة (والمجموعات اللانهائية عبر حجج التغطية).
   • الآلية: خوارزمية تخلص متتالي تستفيد من معلومات التباين. في كل مرحلة، تحسب تصميمًا من نوع G-optimal $\pi_\ell$ لاختيار الإجراءات. وهي تقوم صراحةً بتقدير تباينات الإجراءات الموجودة في دعم التصميم باستخدام خوارزمية قاعدة التوقف (SR).
   • الابتكار الرئيسي: تستخدم الخوارزمية التباينات المقدرة بطريقتين: لتقليل عدد العينات المطلوبة للاستكشاف، وكأوزان في مقدر المربعات الصغرى الموزون. يضمن هذا التوزين بقاء تغاير المقدر تحت السيطرة حتى مع عدد أقل من العينات، مما يؤدي إلى حدود ندم تعتمد على التباين.

2. VALEE (الاستكشاف والاستغلال الخطي الواعي بالتباين):

   • الهدف: كرات الوحدة من النوع $\ell_p$ حيث $p \in (1, 2]$ (وكرات المعايير المزدوجة لها $q \ge 2$).
   • الآلية: خوارزمية استكشاف واستغلال بسيطة.
     • الاستكشاف: تلعب الخوارزمية متجهات الوحدة القياسية $e_i$. وتقوم بتقدير متجه المتوسط $\theta^\star$ لكل إحداثي باستخدام تقنية "وسيط المتوسطات" (Median-of-Means - MoM). إذا كانت مصفوفة التغاير $\Sigma$ مجهولة، فإنها تقوم أولاً بتقدير تباينات متجهات الوحدة.
     • الاستغلال: بمجرد أن يصبح خطأ التقدير صغيرًا بما يكفي بالنسبة للتباين والأفق الزمني، تلتزم الخوارزمية بإجراء $\hat{a}$ مشتق من المتوسط المقدر $\hat{\theta}$، وتحديدًا $\hat{a}_i = \text{sign}(\hat{\theta}_i)|\hat{\theta}_i|^{q-1} / \|\hat{\theta}\|_q^{q-1}$.
   • الابتكار الرئيسي: يستغل التحليل هندسة كرة $\ell_p$ وهيكل ضجيج المعلمات. يوضح المؤلفون أن استكشاف متجهات الوحدة يؤدي إلى خطأ تقدير يتناسب مع $\sqrt{\sigma^2(e_i)}$، وهو ما يعد أكثر إحكامًا من حد $\epsilon$ القياسي في نماذج الضجيج الجمعي. وهذا يسمح للخوارزمية بتحقيق حدود ندم مثالية تعتمد على بنية تباين توزيع المكافأة.

النتائج الرئيسية
يضع البحث كلاً من الحدود العليا والدنيا، مما يثبت أن الخوارزميات المقترحة مثالية في الحد الأدنى (minimax optimal) (مع مراعاة العوامل اللوغاريتمية) لإعدادات محددة.

• مجموعات الإجراءات المنتهية العامة ($K$ من الإجراءات):

  • الحد الأعلى: تحقق خوارزمية VASE ندمًا قدره $\tilde{O}(d^2 + \sqrt{dT \log(K/\delta) M_\sigma})$، حيث $M_\sigma$ كمية تعتمد على التباين ومحدودة بـ $\max_a \sigma^2(a)$.
  • الحد الأدنى: تم إثبات حد أدنى قدره $\tilde{\Omega}(d\sqrt{T \sigma^2_{\max}})$، مما يظهر أن الحد الأعلى دقيق حتى العوامل اللوغاريتمية عندما يكون $\log(K) \approx d$.

• كرات الوحدة $\ell_p$ ($p \le 2$):

  • تغاير معروف: تحقق خوارزمية VALEE ندمًا قدره $\tilde{O}(d + \sqrt{dT \sigma^2_q})$، حيث $\sigma^2_q = (\sum \Sigma_{ii}^{q/2})^{2/q}$. وقد ثبت أن هذا مثالي عبر حد أدنى مطابق قدره $\tilde{\Omega}(\sqrt{dT \sigma^2_q})$.
  • تغاير مجهول: تتحمل VALEE حدًا إضافيًا، مما ينتج عنه ندم قدره $\tilde{O}(\sqrt{dT \sigma^2_q} + d^{2/3 + 2/3q} T^{1/3})$. يشير المؤلفون إلى أن هذا الحد الإضافي ينشأ من مرحلة تقدير التباين.

• كرات الوحدة $\ell_p$ ($p > 2$):

  • يقدم البحث حدًا أدنى قدره $\tilde{\Omega}(d\sqrt{T \sigma^2_{\max}})$، وهو يطابق الحدود الدنيا المعروفة للنموذج الخصمي في هذه الهندسات.

الأهمية والادعاءات
يدعي البحث أنه يحل "حالة غريبة" تتعلق بالنطاقات الخطية حيث غالبًا ما يعطي نموذج الضجيج الجمعي حدود ندم أسوأ ($d\sqrt{T}$) من النموذج الخصمي ($\sqrt{dT}$) لمجموعات إجراءات معينة مثل كرة الوحدة $\ell_2$. يوضح المؤلفون أن نموذج ضجيج المعلمات يتماشى أكثر مع الحدس القائل بأن النماذج العشوائية يجب أن تكون أسهل من النماذج الخصمية.

• حدود أكثر إحكامًا: بالنسبة لكرات $\ell_p$ حيث $p \le 2$، يسمح نموذج ضجيج المعلمات بحدود ندم من الرتبة $\sqrt{dT \sigma^2_q}$، والتي يمكن أن تكون أصغر بكثير من حد $d\sqrt{T}$ النموذجي لنماذج الضجيج الجمعي عندما يكون التباين صغيرًا.
• الميزة الهيكلية: تسلط النتائج الضوء على أن خطية التحقق (وليس فقط التوقع) والقدرة على تأثير المتعلم على التباين هما أمران حاسمان لتحقيق هذه الحدود المحسنة.
• البساطة: من المثير للدهشة أن الندم الأمثل لكرات $\ell_p$ ($p \le 2$) يمكن تحقيقه باستخدام خوارزمية استكشاف واستغلال بسيطة جدًا (VALEE)، على عكس خوارزميات التصميم الأمثل المعقدة التي قد تتطلبها إعدادات الضجيج الجمعي.

يختتم المؤلفون بأنه بينما نتائجهم لـ $p \le 2$ مثالية (باستثناء العوامل اللوغاريتمية) عندما يكون التغاير معروفًا، فإن حالة التغاير المجهول تترك فجوة مفتوحة (الحد $T^{1/3}$) قد يعالجها العمل المستقبلي. كما يتركون تصميم خوارزمية تطابق الحد الأدنى لـ $p > 2$ كمسألة مفتوحة.