A Broader View of Thompson Sampling

ملخص تقني: رؤية أوسع لـ "تثمين تومسون" (Thompson Sampling)

بيان المشكلة
يُعد "تثمين تومسون" (TS) خوارزمية استدلالية مستخدمة على نطاق واسع في مسألة "المتعدد الأذرع" (Multi-Armed Bandit - MAB)، وهي معروفة بنجاحها التجريبي وحدود الندم (regret bounds) النظرية. ومع ذلك، وعلى عكس سياسات "الحد الأعلى لموثوقية الثقة" (UCB) أو "مؤشر جيتينز" (Gittens index)، يظل مبدأ التحسين الصريح الذي يحكم توازن (TS) بين الاستكشاف والاستغلال غامضاً. وبينما صاغ "جيتينز" (1979) مسألة (MAB) البايزية كعملية اتخاذ قرار ماركوفية (MDP) لاستخلاص سياسة مثلى، إلا أن هذا النهج يعتمد على مكافآت أفق غير محدود بخصم (discounted rewards). وتؤدي هذه الصيغة إلى "تعلم غير مكتمل" (الفشل في تحديد الذراع الأمثل بشكل متكرر لا نهائي)، مما يتعارض مع هدف تقليل الندم في الأفق المحدود (finite-horizon) المركزي في أدبيات (MAB) (روبنز 1952؛ لاي وروبنز 1985). تعالج الورقة الفجوة في فهم (TS) من خلال البحث عن صيغة ثابتة "أمينة" تتوافق مع تقليل الندم في الأفق المحدود مع الحفاظ على قابلية الحل عبر البرمجة الديناميكية.

المنهجية
يقترح المؤلفون إطار عمل لـ "التثبيت الأمين" (faithful stationarization) لإعادة صياغة مسألة تقليل الندم في الأفق المحدود غير المستقرة إلى مسألة تحسين عبر الإنترنت (online optimization) مستقرة.

1. هدف الندم المربع: بدلاً من تقليل الندم التراكمي $R_T$ مباشرة أو استخدام المكافآت المخصومة، يقدم المؤلفون تقليل الندم المربع التراكمي $R_2$. ويضعون حداً هو $R_T \leq \sqrt{R_2 \cdot T}$. إن تقليل مجموع الندمات المربعة في الأفق اللانهائي $R_2(Q; \pi_0) = \mathbb{E}[\sum r^2(q_t; \pi_t)]$ يضمن أن السياسة تحقق معدل ندم أمثل قدره $O(\sqrt{T})$ مع توفير هدف ثابت.
2. معادلة بيلمان الثابتة: ينتج عن هذا الهدف الجديد معادلة "بيلمان" ثابتة لدالة القيمة $V(\pi_t)$ (الندم المربع المستقبلي الأدنى):
   $$V(\pi_t) = \min_{q_t} \left[ r^2(q_t; \pi_t) + q_t \cdot \mathbb{E}_{\pi_t}[V(\pi_{t+1}) | A_t = \cdot] \right]$$
   وعلى عكس "مؤشر جيتينز" (الذي يعظم المكافأة الخطية المخصومة)، فإن هذا التقليل يكون تربيعياً في احتمالات الإجراء، مما يؤدي إلى سياسة مثلى عشوائية بدلاً من سياسة حتمية.
3. صيغة التحسين عبر الإنترنت: من خلال تغيير المتغيرات بالتركيز على المكافأة المتوقعة للجولة التالية $x_t$، يستنتج المؤلفون أن السياسة المثلى لـ $R_2$ (المسماة $Q_{R2}$) تأخذ شكل مسألة تحسين عبر الإنترنت:
   $$x_{R2}^t = \arg\min_{x_t} \left[ (\mathbb{E}_{\pi_t}[\max(\theta_1, \theta_2)] - x_t)^2 + \nu_{R2}(\pi_t) x_t \right]$$
   هنا، يمثل الحد الأول الاستغلال اللحظي (الجشع)، ويمثل الحد الثاني التنظيم الخطي الذي يمثل الاستكشاف. ويُشتق المنظم $\nu_{R2}(\pi_t)$ من معادلة بيلمان وهو يقيس التوتر (tension) بين الاستكشاف والاستغلال (الفرق في القيمة المستقبلية بين سحب الأذرع).
4. إعادة تفسير تثمين تومسون: يوضح المؤلفون أن "تثمين تومسون" (TS) يتبنى نفس صيغة التحسين عبر الإنترنت تماماً:
   $$x_{TS}^t = \arg\min_{x_t} \left[ (\mathbb{E}_{\pi_t}[\max(\theta_1, \theta_2)] - x_t)^2 + \nu_{TS}(\pi_t) x_t \right]$$
   ومع ذلك، فإن المنظم الخاص به $\nu_{TS}(\pi_t)$ هو التباين ثنائي السلسلة (biserial covariance) بين فجوة المكافأة ($\theta_1 - \theta_2$) وهوية الذراع الأمثل ($\text{sign}(\theta_1 - \theta_2)$). يقيس هذا المنظم عدم اليقين بشأن أي ذراع هو الأفضل، بدلاً من قياس التوتر بين المكافأة الفورية والقيمة المستقبلية.

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

• التثبيت الأمين: تقدم الورقة صيغة ثابتة (تقليل الندم المربع) تحافظ على جوهر تقليل الندم في الأفق المحدود، مما يسد الفجوة بين أخذ العينات الاستدلالي والبرمجة الديناميكية المبدئية.
• التوحيد الهيكلي: تكشف الورقة أن كلاً من "تثمين تومسون" وسياسة بيلمان المثلى ($Q_{R2}$) هما حالتان من خوارزميات التحسين عبر الإنترنت التي توازن بين الجشع ومنظم ما.
• تحديد الآلية: تحدد الورقة الآلية المحددة التي تحرك (TS): فهي تنظم الجشع بناءً على عدم اليقين (التباين ثنائي السلسلة)، بينما تنظم السياسة المثلى بناءً على التوتر (فرق القيمة المستقبلية).
• تحسين السياسة: بالاستفادة من إطار عمل بيلمان، يقترح المؤلفون خطوة تحسين سياسة معيارية. فمن خلال تقييم دالة القيمة لـ (TS) وإعادة إدخالها في معادلة بيلمان، يستنتجون سياسة محسنة ($Q_{TS'}$) تستخدم منظماً قائماً على التوتر.

النتائج

• فجوة الأداء: تُظهر التجارب العددية على نماذج "غوس" (Gaussian) و"بيرنولي" (Bernoulli) أن السياسة المثلى لـ $R_2$ ($Q_{R2}$) تحقق ندماً تراكمياً أقل بكثير من "تثمين تومسون". وتُعزى الفجوة إلى كون منظم (TS) مقياساً لعدم اليقين يفشل في التقاط "التوتر" عندما يكون الذراع الرائد غير مؤكد ولكن الذراع الأقل كفاءة قد تم استكشافه بشكل مفرط.
• أخذ العينات الموجه بالمعلومات (IDS): تجد الورقة أن (IDS)، وهي خوارزمية استدلالية أخرى، تشترك في نفس هيكل المنظم القائم على التوتر مع $Q_{R2}$ وتؤدي أداءً يكاد يتطابق مع السياسة المثلى لبيلمان، مما يربط بين المنظور المعلوماتي ومنظور البرمجة الدينامية.
• التحسين بخطوة واحدة: خطوة تحسين واحدة مطبقة على "تثمين تومسون" تغلق حوالي 90% من فجوة الأداء بين (TS) والمعيار المرجعي الأمثل لـ بيلمان. هذا التحسين يحول فعلياً منظم (TS) من مقياس لعدم اليقين إلى مقياس للتوتر.
• الخاصية الهيكلية في حالة K-أذرع: في حالة $K$-أذرع، تخصص السياسة المثلى لبيلمان (و(TS) المحسن) احتمالية موجبة لما لا يزيد عن ذراعين اثنين فقط في أي جولة، بينما قد يخصص (TS) القياسي احتمالية موجبة لجميع الأذرع. تمنح خطوة تحسين السياسة خاصية التناثر الهيكلي لـ (TS).

الأهمية
تدعي الورقة أنها تقدم "رؤية أوسع" لـ "تثمين تومسون" من خلال إعادة صياغته كخوارزمية تحسين عبر الإنترنت. هذا المنظور:

1. يشرح الاستدلال: يوضح أن (TS) يوازن بين الاستكشاف والاستغلال عن طريق تنظيم الجشع بمقياس لعدم اليقين المتبقي.
2. يحدد القيود: يحدد أن اعتماد (TS) على عدم اليقين بدلاً من التوتر يؤدي إلى سلوك غير أمثل في أنظمة محددة (على سبيل المثال، عندما يكون الذراع الأمثل غير مؤكد ولكن الذراع الأقل كفاءة قد تم استكشافه بشكل مفرط).
3. يسمح بالتحسين المبدئي: يوفر إطار عمل صارم لتحسين خوارزميات أخذ العينات من البعد الخلفي (posterior sampling). ومن خلال مواءمة المنظم مع مقياس التوتر الأمثل لبيلمان، يوضح المؤلفون أنه يمكن تحسين (TS) بشكل كبير مع حد أدنى من التكلفة الحسابية، وذلك عبر خطوة واحدة من تكرار السياسة، مما ينقله ليكون أقرب إلى المثالية النظرية دون التخلي عن طبيعته القائمة على أخذ العينات.