2025-11-24T22:28:17.253920

Exploration-free Algorithms for Multi-group Mean Estimation

Wei, Zhong, Li
We address the problem of multi-group mean estimation, which seeks to allocate a finite sampling budget across multiple groups to obtain uniformly accurate estimates of their means. Unlike classical multi-armed bandits, whose objective is to minimize regret by identifying and exploiting the best arm, the optimal allocation in this setting requires sampling every group on the order of $Θ(T)$ times. This fundamental distinction makes exploration-free algorithms both natural and effective. Our work makes three contributions. First, we strengthen the existing results on subgaussian variance concentration using the Hanson-Wright inequality and identify a class of strictly subgaussian distributions that yield sharper guarantees. Second, we design exploration-free non-adaptive and adaptive algorithms, and we establish tighter regret bounds than the existing results. Third, we extend the framework to contextual bandit settings, an underexplored direction, and propose algorithms that leverage side information with provable guarantees. Overall, these results position exploration-free allocation as a principled and efficient approach to multi-group mean estimation, with potential applications in experimental design, personalization, and other domains requiring accurate multi-group inference.
academic

خوارزميات خالية من الاستكشاف لتقدير متوسط المجموعات المتعددة

المعلومات الأساسية

  • معرّف الورقة: 2510.10374
  • العنوان: خوارزميات خالية من الاستكشاف لتقدير متوسط المجموعات المتعددة
  • المؤلفون: Ziyi Wei (جامعة فرجينيا التقنية)، Huaiyang Zhong (جامعة فرجينيا التقنية)، Xiaocheng Li (كلية لندن الإمبراطورية)
  • التصنيف: cs.LG, stat.ML
  • تاريخ النشر: 12 أكتوبر 2025
  • رابط الورقة: https://arxiv.org/abs/2510.10374

الملخص

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

الخلفية البحثية والدافع

تعريف المشكلة

تتطلب مشكلة تقدير متوسط المجموعات المتعددة توزيع ميزانية أخذ العينات على K مجموعة خلال فترة زمنية محدودة T، بحيث تحقق التقديرات لجميع متوسطات المجموعات دقة متسقة. بشكل محدد، بالنسبة للمجموعة k، توزيع المكافآت هو Pk، والمتوسط هو μk، والتباين هو σk²، والهدف هو تقليل هدف p-norm:

Rp(n)=∥{σk2nk}k=1K∥pR_p(n) = \left\|\left\{\frac{\sigma_k^2}{n_k}\right\}_{k=1}^K\right\|_p

حيث nk هو عدد مرات أخذ العينات من المجموعة k.

دافع البحث

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

المساهمات الأساسية

  1. التحسينات النظرية: تحسين عدم المساواة في تركيز التباين شبه الغاوسي بناءً على عدم المساواة هانسون-رايت، وتحديد فئة التوزيعات شبه الغاوسية الصارمة، والحصول على ضمانات نظرية أكثر حدة.
  2. تصميم الخوارزمية: اقتراح خوارزميتين خاليتين من الاستكشاف:
    • خوارزمية غير تكيفية (تتطلب معرفة مسبقة بحد أدنى للتباين)
    • خوارزمية تكيفية (بدون معرفة مسبقة، باستخدام فترات الثقة)
  3. توسيع الإطار: توسيع تقدير متوسط المجموعات المتعددة لأول مرة إلى إعداد آلات الجشع السياقية، مع اقتراح الخوارزميات المقابلة والتحليل النظري.
  4. تحسن الأداء: مقارنة بأفضل النتائج الموجودة، إزالة عامل log T من حد الندم، وتحقيق حد نظري أكثر إحكاماً.

شرح الطريقة

تعريف المهمة

بالنظر إلى K مجموعة، كل مجموعة k لها توزيع مكافآت Pk بمتوسط غير معروف μk وتباين σk². خلال فترة زمنية T، اختر مجموعة واحدة في كل لحظة لأخذ عينات، والهدف هو تقليل p-norm لخطأ التقدير لجميع المجموعات.

مخطط التوزيع الأمثل

الاقتراح 2.1 يعطي التوزيع الأمثل نظرياً: nk∗=σkq∑j=1Kσjq⋅Tn_k^* = \frac{\sigma_k^q}{\sum_{j=1}^K \sigma_j^q} \cdot T

حيث q = 2p/(p+1) (عندما يكون p محدوداً) أو q = 2 (عندما يكون p = ∞).

الخوارزمية 1: التوزيع غير التكيفي

الفكرة الأساسية: تنفيذ على مرحلتين

  1. المرحلة الأولى: أخذ عينات موحدة من كل مجموعة لـ τ جولة، وتقدير التباين
  2. المرحلة الثانية: توزيع الميزانية المتبقية وفقاً للنسبة المثلى بناءً على التباين المقدر

المعاملات الرئيسية:

  • الطول الأولي: τ=σqσq+(K−1)σ‾q⋅T\tau = \frac{\sigma^q}{\sigma^q + (K-1)\underline{\sigma}^q} \cdot T
  • وزن التوزيع: λk,τ=σ^k,τq∑j=1Kσ^j,τq\lambda_{k,\tau} = \frac{\hat{\sigma}_{k,\tau}^q}{\sum_{j=1}^K \hat{\sigma}_{j,\tau}^q}

الخوارزمية 2: الخوارزمية التكيفية

نقاط التحسين: لا تتطلب معرفة مسبقة بحد أدنى للتباين، وتعديل تكيفي من خلال فترات الثقة.

الآلية الأساسية:

  1. بناء فترة الثقة: بناء LCB و UCB بناءً على عدم المساواة المحسّن في تركيز التباين
  2. التوقف التكيفي: حساب وقت التوقف الديناميكي لكل مجموعة
  3. استراتيجية حذف الأذرع: تقنية مشابهة للحذف في تحديد الذراع الأمثل

فترة الثقة:

  • LCBk,n=max⁡{σ^k,n2−εk,n+,0}LCB_{k,n} = \max\{\hat{\sigma}_{k,n}^2 - \varepsilon_{k,n}^+, 0\}
  • UCBk,n=σ^k,n2+εk,n−UCB_{k,n} = \hat{\sigma}_{k,n}^2 + \varepsilon_{k,n}^-

الخوارزمية 3: التوسيع السياقي

تعريف المشكلة: كل مجموعة k مرتبطة بمتجه معاملات βk، عند ملاحظة السياق ct، المكافأة هي: Xk,n=βkTcn+ηk,nX_{k,n} = \beta_k^T c_n + \eta_{k,n}

دالة الهدف: min⁡E[∑k=1K∥β^k,nk−βk∥2]\min \mathbb{E}\left[\sum_{k=1}^K \|\hat{\beta}_{k,n_k} - \beta_k\|^2\right]

الابتكارات الرئيسية:

  • استخدام مقدر الانحدار الحرجي
  • استراتيجية أخذ العينات "قرر ثم لاحظ"
  • الحفاظ على استقلالية متجهات السياق

إعداد التجارب

مجموعات البيانات

  1. التوزيع الغاوسي: K=4 مجموعات، المتوسطات مأخوذة من U(-1,1)، التباينات {1, 1.5, 2, 2.5}
  2. Rademacher + غاوسي: إعادة إنتاج إعداد التجارب من Carpentier وآخرون
  3. توزيع Beta متماثل: التحقق من مزايا الخاصية شبه الغاوسية الصارمة
  4. الإعداد السياقي: K∈{5,10,20}، البعد d=4، السياق مأخوذ بشكل موحد من المكعب الفائق

مؤشرات التقييم

  • الندم التجريبي: Rp(nπ)−Rp(n∗)R_p(n^{\pi}) - R_p(n^*)
  • إحكام الحد النظري
  • سرعة تقارب الخوارزمية

طرق المقارنة

  • إعداد شبه غاوسي عام (GSG) مقابل إعداد شبه غاوسي صارم (SSG)
  • حد أدنى معروف للتباين مقابل حد أدنى غير معروف
  • الأداء مع قيم p مختلفة

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

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

  1. إحكام الحد النظري: الحد النظري في إعداد شبه الغاوسي الصارم أقرب إلى النتائج التجريبية، خاصة عندما يكون p=∞.
  2. تأثير حد التباين الأدنى: عندما يكون حد التباين الأدنى غير معروف، تنخفض أداء الخوارزمية بشكل ملحوظ، وهذا الانخفاض يحدث في نقاط زمنية مختلفة في إعدادات GSG و SSG.
  3. التعقيد الزمني: يتناقص طول المرحلة الأولى بشكل كبير في إعداد SSG، من الارتباط بـ σ² إلى ثابت يعتمد فقط على log T.

النتائج العددية المحددة

  • في التجارب الغاوسية، عندما T > 2×10⁴، تبدأ الخوارزمية في إظهار الأداء المتوقعة نظرياً
  • الحد النظري في إعداد SSG أكثر إحكاماً من إعداد GSG بحوالي رتبة حجم واحدة
  • في التجارب السياقية، ميل الندم التجريبي قريب من -2، متطابق مع التنبؤ النظري

تجارب الاستئصال

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

الأعمال ذات الصلة

تقدير متوسط المجموعات المتعددة

  • Antos وآخرون (2008، 2010): أول من درس التعلم النشط تحت الضوضاء غير المتجانسة
  • Carpentier وآخرون (2011): اقتراح خوارزميات من نوع UCB للتعامل مع الحالات غير المحدودة
  • Aznag وآخرون (2023): إدخال دالة هدف p-norm وإنشاء حدود سفلى

نظرية تركيز التباين

  • التطورات الحديثة لعدم المساواة هانسون-رايت
  • تحديد وخصائص التوزيعات شبه الغاوسية الصارمة
  • تحسينات حدود Bernstein التجريبية

آلات الجشع السياقية

  • تقدير المعاملات في آلات الجشع الخطية
  • تطبيق نظرية التصميم التجريبي
  • قيود خوارزميات من نوع UCB في الإعدادات السياقية

التحليل النظري

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

النظرية 3.1 (خوارزمية غير تكيفية، p=∞): E[Rp(nπ1)−Rp(n∗)]≤42σ2FAlg1,∞(λ,σ2)T−3/2log⁡T+o(T−3/2)\mathbb{E}[R_p(n^{\pi_1}) - R_p(n^*)] \leq 4\sqrt{2}\sigma^2 F_{Alg1,\infty}(\lambda, \sigma^2) T^{-3/2}\sqrt{\log T} + o(T^{-3/2})

النظرية 3.2 (خوارزمية غير تكيفية، p<∞): E[Rp(nπ1)−Rp(n∗)]≤24σ4FAlg1,p(λ,σ2)T−2log⁡T+o(T−2)\mathbb{E}[R_p(n^{\pi_1}) - R_p(n^*)] \leq 24\sigma^4 F_{Alg1,p}(\lambda, \sigma^2) T^{-2}\log T + o(T^{-2})

النظرية 4.1 (خوارزمية تكيفية): توفير حد من نفس الرتبة، لكن مع عوامل ثابتة مختلفة قليلاً.

التحسينات الرئيسية

  1. تركيز التباين: استخدام عدم المساواة هانسون-رايت لتحسين عدم المساواة في تركيز التباين، وإزالة عامل log⁡(1/δ)\sqrt{\log(1/\delta)}.
  2. شبه غاوسي صارم: تحديد فئة التوزيعات شبه الغاوسية الصارمة، حيث معامل التباين يساوي التباين الحقيقي، مما يوفر حد أكثر حدة.
  3. تصميم خالي من الاستكشاف: إثبات أن الاستكشاف الصريح من نوع UCB غير ضروري في هذه المشكلة، لأن الحل الأمثل نفسه يتطلب أخذ عينات من كل ذراع Θ(T) مرة.

الخلاصة والمناقشة

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

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

القيود

  1. افتراضات التوزيع: تعتمد الخوارزميات على افتراض شبه الغاوسي، وقد لا تكون مناسبة للتوزيعات ذات الذيل الثقيل.
  2. العوامل الثابتة: على الرغم من أنها مثلى بشكل مقارب، قد تكون العوامل الثابتة كبيرة في حالات العينات الصغيرة.
  3. قيود السياق: يتطلب التوسيع السياقي استراتيجية "قرر ثم لاحظ"، مما يحد من مرونة التطبيق العملي.

الاتجاهات المستقبلية

  1. التوزيعات المنظمة: البحث عن كيفية الاستفادة من معلومات هيكل التوزيع الإضافية لتحسين الخوارزميات بشكل أكبر.
  2. التوسيع غير البارامتري: توسيع الطريقة إلى الإعدادات غير البارامترية.
  3. التطبيقات العملية: التحقق من فعالية الخوارزمية في مجالات التطبيق المحددة (مثل اختبارات A/B والتجارب السريرية).

التقييم المتعمق

المزايا

  1. مساهمات نظرية كبيرة: تحسينات جوهرية في كل من نظرية تركيز التباين وتصميم الخوارزمية.
  2. رؤى عميقة في المشكلة: تحديد الفرق الأساسي بين تقدير متوسط المجموعات المتعددة وآلات الجشع التقليدية.
  3. تصميم طريقة أنيق: الخوارزميات بسيطة وحدسية وسهلة الفهم والتطبيق.
  4. التحقق التجريبي الشامل: التحقق من النتائج النظرية من خلال توزيعات وإعدادات متعددة.

أوجه القصور

  1. التحقق من التطبيق العملي محدود: نقص التحقق على نطاق واسع على مجموعات البيانات الحقيقية.
  2. تحليل التعقيد الحسابي: لا يوجد تحليل تفصيلي لتعقيد الخوارزمية الحسابي.
  3. نقاش الاستقرار: نقص التحليل للأداء عند انتهاك افتراضات التوزيع.

التأثير

  1. القيمة النظرية: توفير إطار نظري جديد لمشاكل الاستدلال متعدد المجموعات.
  2. القيمة العملية: قيمة تطبيق مباشرة في مجالات مثل تصميم التجارب والتوصيات الشخصية.
  3. قابلية إعادة الإنتاج: وصف الخوارزمية واضح والتحليل النظري كامل، مع قابلية إعادة إنتاج جيدة.

السيناريوهات المعمول بها

  1. اختبارات A/B: السيناريوهات التي تتطلب مقارنة عادلة لمجموعات مستخدمين متعددة.
  2. التجارب السريرية: تقييم فعالية مجموعات العلاج المتعددة.
  3. أبحاث السوق: تقدير دقيق لتفضيلات السكان المختلفين.
  4. أنظمة التوصيات: ضمان العدالة متعددة المجموعات في التوصيات الشخصية.

المراجع

تستشهد هذه الورقة بعدة أعمال ذات صلة مهمة، بما في ذلك:

  • Aznag وآخرون (2023): إطار التعلم النشط لتقدير متوسط المجموعات المتعددة
  • Carpentier وآخرون (2011): خوارزميات الحد الأعلى للثقة للتعلم النشط في آلات الجشع متعددة الأذرع
  • الأعمال النظرية ذات الصلة بعدم المساواة هانسون-رايت
  • النتائج الكلاسيكية للتوزيعات شبه الغاوسية وتركيز التباين

تقدم هذه الورقة مساهمات مهمة في النظرية والطريقة، وتوفر منظوراً جديداً وحلاً فعالاً لمشكلة تقدير متوسط المجموعات المتعددة. يشكل اقتراح الخوارزميات الخالية من الاستكشاف تحولاً عن النموذج الكلاسيكي للمقايضة بين الاستكشاف والاستغلال في آلات الجشع متعددة الأذرع التقليدية، مما يحمل أهمية نظرية وقيمة عملية كبيرة.