في هذه المقالة، سوف نقوم بتنفيذ Double DQN مع الأولوية النسبية من Schaul, etc 2016 ، حيث أنه يتفوق على DDQN مع احتمالية موحدة للانتقال في مخزن إعادة التشغيل.

إعادة تشغيل التجربة كما أظهرنا في المحاضرة السابقة، إذا استخدمنا مخزن إعادة تشغيل يكسر الارتباطات الزمنية عن طريق خلط تجربة أحدث وأحدث للتحديثات، فسيتم استخدام التجربة النادرة لأكثر من مجرد تحديث واحد. تم شرح ذلك في خوارزمية Deep Q-Network (DQN) (Mnih et al., 2013; 2015)، والتي استقرت تدريب دالة القيمة، التي تمثلها شبكة عصبية عميقة، باستخدام إعادة تشغيل التجربة

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

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

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

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

𝑃 ( 𝑖 )=(Pᵢ)ᵃ / ∑ₖ (P ₖ)ᵃ

حيث Pᵢ>0 هي أولوية الانتقال i . يحدد الأس α مقدار الأولوية المستخدمة، حيث يتوافق α=0 مع الحالة الموحدة. لذا، أصبح α معلمة فرعية أخرى نحتاج إلى ضبطها ولكن بالنسبة للعبة Atari، كما وجد مؤلف الورقة α=0.6

هو الأفضل لهذه المشكلة ولكن بالنسبة للمشاكل الأخرى يجب علينا ضبط قيمته للحصول على أفضل تقريب.

𝐼𝑚𝑝𝑜𝑟𝑡𝑎𝑛𝑡𝑁𝑜𝑡𝑒 :

Pᵢ >0 هو خطأ TD الذي يأتي من التعريف [ 𝑅 ⱼ + 𝛾 ⱼ 𝑄 ( 𝑠 ⱼ₊₁ ، 𝑎𝑟𝑔𝑚𝑎𝑥 ₐ 𝑄 ( 𝑠 ⱼ₊₁ ، 𝑎 ، 𝜃 ⁺) ، 𝜃 ⁻)− 𝑄 ( 𝑠 ⱼ ، 𝑎 ⱼ ، 𝜃 ⁺)] ولكننا سنستخدم الخطأ من الشبكة العصبية، وهو مربع خطأ TD لأن هدف نموذجنا هو [ 𝑅 ⱼ + 𝛾 ⱼ 𝑄 ( 𝑠 ⱼ₊₁ ، 𝑎𝑟𝑔𝑚𝑎𝑥 ₐ 𝑄 ( 𝑠 ⱼ₊₁ ، 𝑎 ، 𝜃 ⁺)، 𝜃 ⁻)،)] وهذا هو نفس ما كان عليه من قبل بدون الحد الأخير الذي هو ناتج النموذج، نضيف ثابتًا موجبًا صغيرًا 𝜖

وهذا يمنع إعادة النظر في حالة حافة التحولات بمجرد أن يصبح الخطأ فيها صفرًا.

الآن بعد أن أعطينا الأولوية للانتقال، سيتم أخذ عينات من الانتقال ذي الأولوية العالية بشكل متكرر حتى ينخفض ​​خطأ هذا الانتقال وقد يؤدي ذلك إلى الإفراط في الملاءمة. يمكننا تصحيح هذا التحيز باستخدام أوزان أخذ العينات ذات الأهمية (IS):

𝑤 ᵢ =( 𝑁 ∗ 𝑃 ( 𝑖 ) )− 𝛽

حيث 𝑁 هو عدد العينات الموجودة في الذاكرة و𝑃 ( 𝑖 ) هو احتمال الانتقال 𝑖.

𝛽 هو معامل فائق يتحكم في مقدار ما نريد تعويضه عن تحيز أخذ العينات حسب الأهمية (0 يعني عدم التعويض على الإطلاق، بينما 1 يعني التعويض بالكامل). في الورقة البحثية، استخدم المؤلفون β=0.4 في بداية التدريب وزادوها خطيًا إلى 𝛽 =1 بحلول نهاية التدريب. مرة أخرى، ستعتمد القيمة المثلى على المهمة بعد تسليط الضوء على النقطة الأساسية، دعنا نبدأ التنفيذ.

أولاً: شجرة المجموع:

إن بنية بيانات شجرة المجموع المستخدمة هنا تشبه إلى حد كبير في روحها تمثيل المصفوفة لكومة ثنائية. ومع ذلك، بدلاً من خاصية الكومة المعتادة، تكون قيمة العقدة الأصلية هي مجموع أبنائها. تخزن العقد الورقية أولويات الانتقال والعقد الداخلية عبارة عن مجموعات وسيطة، مع احتواء العقدة الأصلية على مجموع جميع الأولويات، 𝑝𝑡𝑜𝑡𝑎𝑙 .

يوفر هذا طريقة فعالة لحساب المجموع التراكمي للأولويات، مما يسمح بتحديثات O(log N) وأخذ العينات. لأخذ عينات من دفعة صغيرة بحجم k، يتم تقسيم النطاق [0، 𝑝𝑡𝑜𝑡𝑎𝑙 ] بالتساوي إلى نطاقات k. بعد ذلك، يتم أخذ عينات من قيمة بشكل موحد من كل نطاق. أخيرًا، يتم استرداد التحولات التي تتوافق مع كل من هذه القيم المأخوذة من العينات من الشجرة بالإضافة إلى هذا الهيكل، سنضيف بنية بيانات متدحرجة أخرى، عندما تمتلئ البيانات، يتم تدويرها إلى العنصر الأول وكتابتها فوقه. مقال جيد يشرح شجرة المجموع: مقدمة إلى شجرة المجموع

تم تنفيذ هذه الفئة على بنية بيانات Sum Tree، وهي عبارة عن شجرة ثنائية كاملة وهي نفس قائمة انتظار الأولوية حيث تحتوي العقدة الجذرية على مجموع جميع العقد الورقية في الشجرة. باستخدام بنية البيانات هذه، يتم تقليل وقت التحديث إلى 𝑂 ( 𝑙𝑜𝑔 ( 𝑛 ))، ويجد المجموع إلى 𝑂 (1). تحتوي العقدة الجذرية على 𝑖𝑛𝑑𝑒𝑥 =1 وتحافظ على الفهرس 0 غير مستخدم وأن الأبناء الأيسر هو 2 × فهرس الوالدين من أجل البساطة.

نقوم بتنفيذ بنية البيانات هذه لاستخدامها في تحديد الأولويات النسبية في إعادة تشغيل التجربة ذات الأولوية من DeepMind

صفات:

• الحجم : يمثل حجم المخزن المؤقت
• الشجرة : هي الشجرة الثنائية التي تحتوي على الأولوية التي تحتاج إلى الحصول على المجموع والتحديث.
• البيانات : حيث نقوم بحفظ المعلومات
• current_pos : هو المؤشر إلى الموضع الحالي للبيانات
• n_entries : عدد المعلومات التي لدينا.
• max_prio : هذا لا يرتبط بشجرة المجموع ولكننا نحتاجه لتتبع الأولوية القصوى للاستخدام في خوارزميتنا ومن خلال القيام بذلك فإننا نختصر الوقت إلى 𝑂 (1)

طريقة:

• إضافة : استخدام هذه الطريقة لإضافة انتقال إلى قائمة البيانات والأولوية للشجرة وتحديث الشجرة عن طريق "Bubbel up" كقائمة أولوية
• التحديث : تمامًا مثل "Bubbel up" حيث أضف الأولوية إلى فتحة فارغة في الشجرة ثم قم بتحديث عقدتها الأصلية حتى نقوم بإثراء عقدة الجذر.
• الإجمالي : إرجاع القيمة الجذرية التي تمثل مجموع كل الأوراق في الشجرة
• get_sample : يسافر في الشجرة للعثور على الأولوية والبيانات المرتبطة بهذه الأولوية.

ثانياً: الذاكرة

الآن سوف نقوم بتنفيذ فئة الذاكرة التي تعتمد على بنية بيانات Sum-Tree والتي هي مخزن إعادة التشغيل . مخزن إعادة التشغيل الآن هو Sum-Tree مع بعض الوظائف الأخرى وأهمها وظيفة تجارب العينة في هذه الوظيفة، نقوم بأخذ عينات من البيانات من الذاكرة كما شرحنا أعلاه ونحسب أيضًا أوزان العينة كما في المعادلة 𝑤𝑖 =( 𝑁 ∗ 𝑃 ( 𝑖 ))− 𝛽

يتم استخدام هذه الفئة لإنشاء مخزن إعادة التشغيل الخاص بنا لاستخدامه في إعادة تشغيل التجربة ذات الأولوية

صفات:

• الحجم : حجم مخزن إعادة التشغيل.
• الشجرة : هي بنية بيانات الشجرة المجموعية.
• ألفا : هذه المعلمة تستخدم في الاحتمال العشوائي 𝑝𝑟𝑖𝑜𝑟𝑖𝑡𝑦 =( 𝑝𝑖 + 𝑒𝑝𝑠𝑖𝑙𝑜𝑛 )
• إبسيلون : قيمة إيجابية صغيرة تضاف إلى الخطأ
• بيتا : هو المعامل المستخدم لحساب الأوزان
•  : هي القيمة الأولية للبيتا

أخيرا : الوكيل

يمكننا تدريب أي نوع من الوكلاء الذي أنشأناه من قبل، مثل DQN وDDQN وDueling-DQN وSARSA وما إلى ذلك.. وكما ذكر مؤلف الورقة، فإن استخدام Prioritized Replay Buffer يتفوق على جميع الخوارزميات السابقة إذا كان يستخدم أخذ العينات بشكل موحد. وسنقوم بتغيير فئة Double_DQN التي أنشأناها في البرنامج التعليمي السابق.

الخوارزمية:

#----> الذاكرة التي نحفظ فيها الملاحظات للتدريب نستخدم الآن ذاكرتنا. 
self.replay_buffer=Memory(replay_size)

هنا نقوم باستبدال dueque بكائن الذاكرة.

def _sample_experiences(self): 
       #----> بدلاً من استخدام الاختيار العشوائي لتحديد الانتقال، نستخدم كائن الذاكرة ذي الأولوية لعينة البيانات. 
        batch,weights,indices=replay_buffer.sample_experiences(self.batch_size) 
        # نجمع الخبرات معًا حيث يحتوي المخزن المؤقت على مجموعة مثل هذه (state,action,reward,done,next_state) 
        states,actions,rewords,dones,next_states=[np.array([experiance[field_index] for experiance in batch]) for field_index in range(5)] 
#----> نرجع الأوزان والإدخالات لأننا نحتاجها لخطوة التدريب. 
        return states,actions,rewords,dones,next_states,weights,indices

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