2025-11-17T07:58:12.711519

Posterior Sampling for Continuing Environments

Xu, Dong, Van Roy
We develop an extension of posterior sampling for reinforcement learning (PSRL) that is suited for a continuing agent-environment interface and integrates naturally into agent designs that scale to complex environments. The approach, continuing PSRL, maintains a statistically plausible model of the environment and follows a policy that maximizes expected $γ$-discounted return in that model. At each time, with probability $1-γ$, the model is replaced by a sample from the posterior distribution over environments. For a choice of discount factor that suitably depends on the horizon $T$, we establish an $\tilde{O}(τS \sqrt{A T})$ bound on the Bayesian regret, where $S$ is the number of environment states, $A$ is the number of actions, and $τ$ denotes the reward averaging time, which is a bound on the duration required to accurately estimate the average reward of any policy. Our work is the first to formalize and rigorously analyze the resampling approach with randomized exploration.
academic

أخذ العينات اللاحقة للبيئات المستمرة

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

  • معرّف الورقة: 2211.15931
  • العنوان: Posterior Sampling for Continuing Environments
  • المؤلفون: Wanqiao Xu (جامعة ستانفورد)، Shi Dong (Google DeepMind)، Benjamin Van Roy (جامعة ستانفورد)
  • التصنيف: cs.LG stat.ML
  • المؤتمر المنشور: RLJ | RLC 2024
  • رابط الورقة: https://arxiv.org/abs/2211.15931

الملخص

تقترح هذه الورقة خوارزمية تعلم تعزيزي قائمة على أخذ العينات اللاحقة للبيئات المستمرة (Continuing PSRL)، والتي يمكن دمجها بشكل طبيعي في تصاميم الوكلاء القابلة للتوسع. تحافظ الخوارزمية على نموذج بيئة معقول إحصائياً وتتبع سياسة تعظم العائد المخصوم بـ γ في هذا النموذج. في كل خطوة زمنية، تعيد الخوارزمية أخذ عينات من النموذج من التوزيع اللاحق للبيئة باحتمالية 1-γ. من خلال اختيار عامل الخصم بشكل مناسب بناءً على نطاق زمني T، يتم إنشاء حد ندم بايزي بقيمة Õ(τS√AT)، حيث S هو عدد الحالات في البيئة، و A هو عدد الإجراءات، و τ يمثل متوسط الوقت للمكافأة.

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

المشكلة الأساسية

تم تصميم خوارزميات أخذ العينات اللاحقة الموجودة في التعلم التعزيزي بشكل أساسي للبيئات الحلقية (episodic)، وتعتمد على الحفاظ على عدادات زيارة الحالة-الإجراء، مما يجعلها غير مناسبة للبيئات المستمرة المعقدة ذات فضاء الحالة عالي الأبعاد.

أهمية المشكلة

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

قيود الطرق الموجودة

  1. TSDE (Ouyang et al., 2017): يتطلب معايير إعادة أخذ عينات معقدة، بما في ذلك شروط مضاعفة العدادات، وغير قابل للتطبيق في فضاء الحالة الكبير
  2. DS-PSRL (Theocharous et al., 2018): على الرغم من تجنب العدادات، فإن التحليل يعتمد على افتراضات تقنية قوية، وحد الندم ينمو خطياً بدونها
  3. PSRL التقليدي: ينطبق فقط على البيئات الحلقية، ولا يمكن توسيعه مباشرة إلى الإعدادات المستمرة

دافع البحث

اقتراح خوارزمية أخذ عينات لاحقة بسيطة وقابلة للتوسع وصارمة نظرياً للبيئات المستمرة، والتي يمكنها:

  • تجنب الحفاظ على عدادات زيارة الحالة-الإجراء
  • الدمج الطبيعي في طرق التقريب الوظيفي الموجودة
  • توفير ضمانات نظرية تطابق أفضل الطرق الموجودة

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

  1. أول خوارزمية PSRL قابلة للتوسع للبيئات المستمرة: اقتراح Continuing PSRL بناءً على مخطط عشوائي بسيط، يتجنب معايير إعادة الأخذ المعقدة
  2. تحليل نظري صارم: إنشاء حد ندم بايزي بقيمة Õ(τS√AT)، يطابق أفضل النتائج الموجودة
  3. اختراق القابلية للتوسع: يمكن توسيع الخوارزمية بشكل طبيعي إلى فضاء الحالة عالي الأبعاد وإعدادات التقريب الوظيفي
  4. منظور جديد لعامل الخصم: النظر إلى عامل الخصم كأداة تصميم خوارزمية وليس خاصية بيئة، مما يوفر منظوراً جديداً لفهم دور عامل الخصم

شرح الطريقة

تعريف المهمة

ضع في الاعتبار عملية قرار ماركوف مصممة بواسطة بيئة غير معروفة E = (A,S,ρ)، حيث:

  • A هو فضاء الإجراء المحدود، |A| = A
  • S هو فضاء الحالة المحدود، |S| = S
  • ρ هي دالة احتمالية الانتقال بين الحالات
  • دالة المكافأة r : S × A → 0,1 حتمية ومعروفة

الهدف هو تقليل الندم المتراكم: Regret(T,π):=∑t=0T−1(λ∗,E−Rt+1)\text{Regret}(T,π) := \sum_{t=0}^{T-1}(λ_{*,E} - R_{t+1})

حيث λ_{*,E} هو متوسط المكافأة الأمثل.

بنية النموذج

بناء الحلقات الزائفة

تقسم الخوارزمية مشكلة التعلم على نطاق زمني لا نهائي إلى حلقات زائفة ذات طول عشوائي:

  • في كل خطوة زمنية t، يتم أخذ عينة من مؤشر ثنائي X_t
  • عندما X_t = 0، يبدأ حلقة زائفة جديدة وإعادة أخذ عينات من نموذج البيئة
  • عندما X_t = 1، يستمر في الحلقة الزائفة الحالية

دالة القيمة المخصومة

بالنسبة للبيئة E والسياسة π، يتم تعريف دالة القيمة المخصومة بـ γ كالتالي: Vπ,Eγ:=E[∑h=0H−1Pπhrπ∣E]=E[∑h=0∞γhPπhrπ∣E]V^γ_{π,E} := \mathbb{E}\left[\sum_{h=0}^{H-1} P^h_π r_π | E\right] = \mathbb{E}\left[\sum_{h=0}^{∞} γ^h P^h_π r_π | E\right]

حيث H هو طول الحلقة الزائفة، ويتبع توزيعاً هندسياً.

متوسط وقت المكافأة

المفهوم الرئيسي هو متوسط وقت المكافأة τ_{π,E}، المعرّف كالحد الأدنى τ بحيث: ∣Eπ[∑t=0T−1Rt+1∣E,S0=s]−T⋅λπ,E(s)∣≤τ\left|\mathbb{E}_π\left[\sum_{t=0}^{T-1} R_{t+1} | E, S_0 = s\right] - T \cdot λ_{π,E}(s)\right| \leq τ

تدفق الخوارزمية

الخوارزمية 1: Continuing PSRL

الإدخال: التوزيع السابق f، عامل الخصم γ، إجمالي وقت التعلم T
1. تهيئة t=1, k=1, X₁=0
2. for t ≤ T:
3.   if Xₜ = 0:
4.     tₖ ← t
5.     أخذ عينات Eₖ ~ f(·|H_tₖ)
6.     حساب πₖ = π^γ_Eₖ
7.     k ← k+1
8.   أخذ عينات وتنفيذ Aₜ ~ πₖ(·|Sₜ)
9.   ملاحظة Rₜ₊₁ و Sₜ₊₁
10.  t ← t+1
11.  أخذ عينات Xₜ₊₁ ~ Bernoulli(γ)

نقاط الابتكار التقني

  1. آلية إعادة أخذ عينات بسيطة: استخدام مولد أرقام عشوائي برنولي فقط، مما يتجنب شروط العدادات المعقدة
  2. الربط بين عامل الخصم واحتمالية إعادة الأخذ: تعيين γ = 1-p، حيث p هو احتمالية إعادة الأخذ
  3. إعادة أخذ عينات مستقلة عن السياسة: معايير إعادة الأخذ مستقلة عن السياسة، مما يبسط التحليل
  4. عامل خصم متغير بمرور الوقت: السماح بنمو عامل الخصم بمرور الوقت، مما يحقق ندماً دون خطي

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

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

  1. بيئة RiverSwim الجدولية:
    • هيكل سلسلة بـ 6 حالات
    • مكافأة 0.005 في الحالة اليسرى، مكافأة 1.0 في الحالة اليمنى
    • السياسة المثلى هي السباحة دائماً نحو اليمين
  2. بيئة RiverSwim بالميزات المستمرة:
    • هيكل مشابه لكن باستخدام ملاحظات الميزات بالبكسل
    • تعيين الميزات: φ(s_t) = 1{x ≤ s_t} ∈ 0,1^N
    • اختبار أداء الخوارزمية في إعدادات التقريب الوظيفي

مقاييس التقييم

  • الندم المتراكم (Cumulative Regret)
  • تغير متوسط الندم بمرور الوقت

طرق المقارنة

  1. TSDE (Ouyang et al., 2017): Thompson sampling القائم على العدادات
  2. DS-PSRL (Theocharous et al., 2018): مخطط إعادة أخذ عينات بفترات زمنية ثابتة
  3. وكيل عشوائي: كخط أساس
  4. DQN مع ε-greedy: المقارنة في البيئات ذات الميزات المستمرة

تفاصيل التنفيذ

  • التوزيع السابق: توزيع ديريشليت (الانتقال) وتوزيع غاوسي-غاما (المكافأة)
  • المعاملات الفائقة: عدد وهمي n=1، α=1/S، μ=σ²=1
  • استخدام Bootstrapped DQN في البيئات المستمرة، γ=0.99

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

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

  1. البيئات الجدولية:
    • أداء Continuing PSRL مماثلة لـ TSDE، على الرغم من أن الأخير يحسّن متوسط المكافأة مباشرة
    • تفوق واضح على DS-PSRL
    • التحقق من نمو الندم دون خطي المتنبأ به نظرياً
  2. البيئات ذات الميزات المستمرة:
    • Bootstrapped DQN + إعادة أخذ عينات عشوائية يحقق ندماً دون خطي
    • تفوق واضح على vanilla DQN مع استكشاف ε-greedy
    • إثبات قابلية التوسع للطريقة في البيئات المعقدة

الاكتشافات التجريبية

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

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

Thompson Sampling وأخذ العينات اللاحقة

  • Thompson Sampling الكلاسيكي: استُخدم في الأصل لمشاكل الآلات ذات الأذرع المتعددة
  • توسيع PSRL: وسّعها Osband وآخرون إلى التعلم التعزيزي، لكن بشكل أساسي للبيئات الحلقية
  • Bootstrapped DQN: استخدام طرق المجموعات لتقريب التوزيع اللاحق

الاستكشاف في البيئات المستمرة

  • TSDE: أول طريقة Thompson sampling للبيئات المستمرة، لكنها تعتمد على معايير إعادة أخذ عينات معقدة
  • DS-PSRL: بسطت إعادة الأخذ لكن تحتاج افتراضات تقنية قوية
  • هذا العمل: أول طريقة عشوائية بسيطة وصارمة لإعادة الأخذ

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

  • تركز الأعمال الموجودة بشكل أساسي على ندم الخصم γ، بينما تركز هذه الورقة على الندم بدون خصم
  • استخدام متوسط وقت المكافأة τ يحل محل مفهوم الامتداد التقليدي
  • افتراض MDP الضعيف المتصل هو الإعداد الأكثر عمومية لحدود الندم في الوقت المحدود

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

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

  1. المساهمة النظرية: إنشاء حد ندم بقيمة Õ(τS√AT)، يطابق أفضل النتائج الموجودة
  2. بساطة الخوارزمية: يتطلب فقط مولد أرقام عشوائي برنولي لتحقيق استكشاف فعال
  3. القيمة العملية: يمكن دمج الخوارزمية مباشرة في طرق التعلم التعزيزي العميق الموجودة
  4. منظور جديد لعامل الخصم: النظر إلى عامل الخصم كأداة تصميم خوارزمية وليس خاصية بيئة

القيود

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

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

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

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

المميزات

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

أوجه القصور

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

التأثير

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

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

  1. التعلم التعزيزي المستمر: بيئات تتطلب تفاعلاً طويل الأجل بدون هيكل تقسيم طبيعي
  2. فضاء الحالة عالي الأبعاد: بيئات معقدة حيث لا تنطبق الطرق التقليدية المعتمدة على العدادات
  3. التعلم عبر الإنترنت: سيناريوهات تتطلب التعلم والتكيف المستمر أثناء التفاعل
  4. التعلم التعزيزي العميق: يمكن دمجها في أطر عمل التعلم التعزيزي العميق الموجودة

المراجع

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

  • الأعمال الكلاسيكية لـ Thompson sampling (Thompson, 1933)
  • الأعمال الرائدة لـ PSRL (Osband et al., 2013)
  • الأبحاث ذات الصلة بالبيئات المستمرة (Ouyang et al., 2017; Theocharous et al., 2018)
  • التطورات المهمة في التعلم التعزيزي العميق (Mnih et al., 2015)

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