تنبؤ مونت كارلو والفرق الزمني

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

إذا كنا نعرف أن نموذج المكافآت P(s ′|s, a) والتوقع على الحالات التالية تم حسابهما بشكل دقيق، فإن البرمجة الديناميكية تحسب ذلك عن طريق إعادة حساب بقية العائد المتوقع بواسطة تقدير القيمة Vₖ₋₁.

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

مونت كارلو

طرق مونت كارلو هي طرق لحل مشكلة التعلم التعزيزي تعتمد على متوسط ​​عوائد العينة، وهي خوارزمية مستخدمة على نطاق واسع، وتستخدمها الكثير من البرامج مثل AlphaGo الذي سنحاول تنفيذه في المستقبل.

Gₜ= Rₜ+ γRₜ₊₁+ γ²Rₜ₊₁+ · · · (1)

V(s) = E ₜ∼π [Gₜ|sₜ= s] · · · (2)

دالة القيمة هي التوقع على المسارات T التي يتم إنشاؤها باتباع π . في عالم آخر، إنها مجرد متوسط ​​العائد

لضمان توفر عوائد محددة جيدًا، نُعرّف هنا طرق مونت كارلو فقط للمهام العرضية. أي أننا نفترض أن الخبرة مقسمة إلى عوائد، وأن جميع العوائد تنتهي في النهاية بغض النظر عن الإجراءات التي يتم اختيارها. فقط عند اكتمال العوائد تتغير تقديرات القيمة والسياسات. وبالتالي يمكن أن تكون طرق مونت كارلو تدريجية بمعنى العوائد بحلقة، ولكن ليس بالمعنى التدريجي (عبر الإنترنت). غالبًا ما يُستخدم مصطلح مونت كارلو على نطاق أوسع لأي طريقة تقدير تتضمن عملياتها مكونًا عشوائيًا كبيرًا. نستخدمه هنا على وجه التحديد للطرق القائمة على متوسط ​​العوائد الكاملة (على عكس الطرق التي تتعلم من العوائد الجزئية مثل TD ).

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

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

سنقدم أولاً خوارزمية التقييم التي تقوم بتقييم بعض السياسات π ثم سنقدم
خوارزمية التحكم التي تعمل على تحسين السياسة لتحقيق إجراءات أفضل.

الزيارة الأولى لتقييم مونت كارلو.

عندما نقول بينما تكون صحيحة فإننا نعني حلقة ممكنة قدر الإمكان. بالنسبة للحلقة الثانية، نستخدم خطوة زمنية عكسية، ولحساب عائد الخصم من خلال القيام بذلك فإننا نوفر الكثير من الحسابات. على سبيل المثال، لنفترض أن لدي حلقة بها 3 خطوات زمنية والمكافآت هي كما يلي [5، −2، 8] إذا أردت حساب العائد لخطوة الوقت الأولى ولنقل أن γ يساوي 0.6. إذن.

G₀ = 5 + 0.6 ∗ −2 + 0.6²∗8 = 6.68
G₁ = −2 + 0.6 ∗ 8 = 2.8
G₂ = 8

نحن بحاجة إلى حساب العائد لكل حالة من البداية، باستخدام التقنية العكسية نحسبها جميعًا في لقطة واحدة أو بتقنية تدريجية.

G₂ = 8
G₁ = −2 + 0.6 ∗ G₂ = 2.8
G₀ = 5 + 0.6 ∗ G₁= 6.68

إذا أردنا استخدام Every-visit، فنحن نحذف فقط سطر if من الخوارزمية السابقة، والآن سنقوم بتحسين هذه الخوارزمية لمشكلة التحكم كما قلنا من قبل، لا أريد فقط تقييم السياسة، أريد أن أتعلم السياسة لاتخاذ قرار. كما في السابق ولكن الآن سنستخدم دالة Q وهي العائد
المتوقع عند البدء في الحالة s، واتخاذ الإجراء a، ثم اتباع السياسة بعد ذلك.

الزيارة الأولى لمونتي كارلو للسيطرة.

هناك مشكلتان في هذا التنفيذ:

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

بالنسبة للمشكلة الأولى، يمكننا استخدام التقنية التدريجية حتى لا نحتاج إلى تتبع جميع أزواج الحالة والفعل مما قد يستغرق قدرًا كبيرًا من الذاكرة. بالنسبة للمشكلة الأخرى، يجب أن نستخدم خوارزمية الاستكشاف
(UCB، ϵ−greedy، ...) ، هذا موضوع مهم للغاية سنحاول كتابة مقال عنه لاحقًا، ولكن في الوقت الحالي، سأشرح باختصار خوارزمية ϵ−greedy والتي سنستخدمها كثيرًا عندما ننفذ الخوارزميات في المستقبل.

خوارزمية ϵ−greedy

بالنسبة لخوارزمية النموذج الحر، لا يمكن أن تعمل إلا إذا استكشفت سياسة الاستكشاف العالم بشكل كافٍ. وعلى الرغم من أن السياسة العشوائية البحتة مضمونة لزيارة كل حالة وكل انتقال عدة مرات في النهاية، فقد يستغرق الأمر وقتًا طويلاً للغاية للقيام بذلك. لذلك، فإن الخيار الأفضل هو استخدام سياسة الجشع ϵ ( ϵ هي إبسيلون): في كل خطوة تعمل بشكل عشوائي باحتمالية ϵ ، أو بجشع باحتمالية 1– ϵ . تتمثل ميزة سياسة الجشع ϵ (مقارنة بسياسة عشوائية تمامًا) في أنها ستقضي وقتًا أطول وأكثر في استكشاف الأجزاء المثيرة للاهتمام من البيئة، مع تحسن المقدر بشكل أفضل وأفضل، مع الاستمرار في قضاء بعض الوقت في زيارة مناطق غير معروفة من البيئة. من الشائع جدًا البدء بقيمة عالية لـ ϵ (على سبيل المثال، 1.0) ثم تقليلها تدريجيًا (على سبيل المثال، إلى 0.05). الكود الزائف:

• ϵ ← 1
• a ← عشوائي − القيمة ∈ [0, 1]:
• إذا كانت a < ϵ: خذ عشوائيًا a ∈ A.
• وإلا: اختر الإجراء الجشع باستخدام المقدر (على سبيل المثال argmax a Q(s, a))
• ϵ ← تحديث

الزيارة الأولى لمدينة مونت كارلو باستخدام تقنية الزيادة.

الفرق الزمني

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

تعلم TD كما كان من قبل خوارزميته الخالية من النماذج، لا أحتاج إلى النموذج الديناميكي لتعلم السياسة. هناك مزايا على MC، حيث أحتاج إلى الانتظار حتى نهاية الحلقة لإجراء تحديث، وهذا يجعل عمليات التعلم بطيئة. بينما في TD هو تدريب عبر الإنترنت ، أجريت
تحديثًا بعد كل انتقال إذا كنت أستخدم TD (0) أو بعد انتقال λ إذا كنت أستخدم TD (λ) حيث يشير λ إلى الخطوات التي يجب اتخاذها في المستقبل. ميزة أخرى هي أنه يمكننا استخدام TD في المهام المستمرة وعدم وجود حلقة على الإطلاق.

لخوارزمية MC

V(sₜ) ← V(sₜ) + α[Gₜ− V(sₜ)]…… (3)

في المعادلة أعلاه، Gₜ هو العودة الكاملة للحالة s في خطوة الوقت t بينما بالنسبة لتحديث TD (0) يكون على النحو التالي.

V(sₜ) ← V(sₜ) + α[Rₜ+γV(sₜ₊₁)− V(sₜ)]…… (4)

حيث α هو حجم الخطوة (معدل التعلم) وعامل الخصم γ. لذا فإننا نأخذ عينات من العالم من مجموعة (s ₜ ، a ₜ ، r ₜ ، s ₜ₊₁ ) ثم نقوم بالتحديث وفقًا لـ (4).

الهدف TD هو: الهدف = Rₜ+ γV(sₜ₊₁)

خطأ TD هو: δₜ= Rₜ+ γV (sₜ₊₁) − V (sₜ)

خطأ TD هو الفرق بين قيمة التقدير الحالية وقيمة التقدير التالية، في عالم آخر كم أنا بعيد عن توقع الحالة التالية. خطأ TD ليس بالضرورة أن يصل إلى الصفر.

تقييم TD(0)

قبل أن ننتقل إلى الأمام، سنتحدث بإيجاز عن السياسة خارج/داخل . في السياسة داخل، نتعلم كيفية تقدير وتقييم السياسة، من خلال الخبرة المكتسبة من اتباع هذه السياسة. بينما في خارج السياسة، نتعلم كيفية تقدير وتقييم السياسة باستخدام الخبرة المكتسبة من اتباع سياسات مختلفة.

التحكم في TD

ننتقل الآن إلى استخدام طرق التنبؤ TD لمشكلة التحكم. سنتحدث عن خوارزميتين SARSA و Q-learning . sarsa هو اختصار لـ state,action,reward,next_state,next_action. و

التحكم في TD على السياسة الخاصة بـ SARSA.

Q_learning التحكم في TD خارج السياسة.

في هذه الحالة، تقترب دالة قيمة الفعل المكتسبة، Q، بشكل مباشر من Q*، دالة قيمة الفعل المثلى، بغض النظر عن السياسة المتبعة

ملخص

في هذه المقالة نقدم خوارزمية مونت كارلو وخوارزميات الفرق الزمني والتي تشكل جزءًا من التعلم التعزيزي. يجب عليك قراءة هذه المقالة جيدًا وفهم جميع التفاصيل لأنه في المقالة التالية سنبدأ الكود باستخدام الخوارزميات المذكورة في هذه المقالة.

آمل أن تجد هذه المقالة مفيدة وأنا آسف للغاية إذا كان هناك أي خطأ أو خطأ إملائي في المقالة، فلا تتردد في الاتصال بي، أو ترك تعليق لتصحيح الأمور.

خليل حنارة
مهندس ذكاء اصطناعي في مسراج