فهم عملية قرار ماركوفية جزئية الرصد
للعملية الماركوفية جزئية الرصد نموذج الانتقال ومجموعة الأفعال ودالة المكافأة نفسها التي لعملية ماركوفية عادية، مضافًا إليها نموذج استشعار يعطي احتمال كل إدراك في كل حالة. وتبدو الإضافة يسيرة وهي تغيّر المسألة تغييرًا تامًا: إذ صار الفعل الأمثل يتوقف لا على موضع العميل فحسب بل على ما يعرفه، فلا يمكن للسياسة أن تكون دالةً في الحالة.
والحلّ أن تُجعل دالةً في الاعتقاد. فلأن حالة الاعتقاد إحصاءة كافية للتاريخ ومتاحة للعميل دائمًا، تكون السياسة المثلى للعملية الماركوفية المعرَّفة على حالات الاعتقاد مثلى للمسألة الأصلية أيضًا. والإحالة مضبوطة لا تقريبية - لكن العملية الناتجة عنها ذات فضاء حالات متصل وعالي البعد عادةً، فلا يمكن ببساطة إجراء التكرار على القيم أو على السياسات عليها.
وما يتيح التقدم هو صورة دالة القيمة. فتنفيذ خطة شرطية ثابتة لا يتخذ قرارات أخرى، فتكون منفعتها المتوقَّعة جداءً داخليًا بين الاعتقاد ومتجهٍ من المنافع لكل حالة - أي مستوى فائقًا على فضاء الاعتقادات. وتأخذ دالة القيمة المثلى أفضل خطة عند كل اعتقاد، فهي إذن قيمة عظمى لمستويات فائقة: خطية بالقطع ومحدّبة. وتحدّبها قولٌ عن عدم اليقين، إذ إن نقاطها الدنيا هي الاعتقادات التي يقلّ فيها علم العميل بما يفعل.
وتدعم هذه البنية خوارزمية تكرار على القيم تجري على مجموعات من هذه المتجهات لا على أعداد، مع تشذيب الخطط المهيمَن عليها في كل خطوة. وهي مضبوطة ولا تتوسّع: فعدد الخطط الشرطية من العمق d ينمو نموًّا أسّيًا مضاعفًا، والتشذيب يبطئ نمو المجموعة الواجب حفظها ولا يوقفه. ولذلك يلجأ العمل التطبيقي إلى تقطيع فضاء الاعتقادات، أو حصر الاهتمام بالاعتقادات القابلة للبلوغ، أو التخطيط المباشر بالاستشراف من الاعتقاد الراهن مع مرشِّح جسيمي يتتبعه.
كيفية الحساب
U(b) = max_p Σ_s b(s) · α_p(s)
حيث
- b
- حالة الاعتقاد الراهنة - توزيع على الحالات الخفية
- p
- خطة شرطية: فعل أول ثم ما يُفعَل بعد كل إدراك
- α_p(s)
- المنفعة المتوقَّعة لتنفيذ الخطة p حين تكون الحالة الحقيقية s
- max_p
- الغلاف الأعلى على الخطط، وهو ما يجعل U خطية بالقطع ومحدّبة
مثال على عملية قرار ماركوفية جزئية الرصد
في عالم ذي حالتين مكافأتاهما 0 و1، وفعلٍ يستمر باحتمال 0.9 وآخر يبدّل باحتمال 0.9، ومستشعرٍ يصيب 60% من الوقت، يكون لخطتَي الخطوة الواحدة متجها منفعة (0.1, 1.9) و(0.9, 1.1). وتتقاطع المستقيمتان عند اعتقاد قدره 1/2 حيث تساويان 1 بالضبط: بدّل تحته، واستمرّ فوقه.
والامتداد إلى خطوتين ينتج 8 خطط شرطية متمايزة، أربعٌ منها فقط غير مهيمَن عليها. ثم تنفلت الأعداد - 128 عند العمق الثالث و32,768 عند الرابع - ولا ينقذها التشذيب: فعبر سبعة مسوح من التكرار المضبوط على القيم نمت المجموعة غير المهيمَن عليها 2 و4 و8 و16 و30 و52 و88.
وتقطيع مجال الاعتقادات وإجراء تكرار عادي على القيم مع الاستيفاء يتقارب في 281 مسحًا، فيعطي 6.822940 عند الاعتقادين اليقينيين و5.886486 عند المنتظم - فعدم اليقين هو ما يكلّف. ومحاكاة السياسة الناتجة على 30,000 مسار تعيد 6.8230 ± 0.0216 و5.8769 ± 0.0188، وهو التحقق المستقل من أن التقريب لم يتقارب بهدوء إلى جواب خاطئ.
الأسئلة الشائعة
لِمَ لا نتصرف كأن أرجح الحالات هي الحقيقية؟
لأن ذلك يطرح بالضبط المعلومة التي تدور المسألة حولها. فالعميل الذي يلتزم بأفضل تخميناته لا يقدّر فعلًا قط لما قد يكشفه، فلن يتخذ فعل الاستشعار الرخيص الذي يزيل التباسًا - وفي POMDP تكون قيمة المعلومات جزءًا من القرار لا اعتبارًا منفصلًا.
ما الذي يجعل POMDP أصعب بكثير من MDP؟
فضاء الحالات. فعملية ماركوفية بإحدى عشرة حالة تافهة؛ أما فضاء الاعتقادات المقابل فمتصلٌ في عشرة أبعاد، لأن الاحتمالات الأحد عشر مجموعها واحد. والحلّ المضبوط غير عملي إلا في المسائل الضئيلة، والسؤال النافع عادةً أي تقريب نقبل لا هل نقرّب.
كيف تُحلّ عمليًا؟
بالتقريب: تقطيع فضاء الاعتقادات أو أخذ عينات منه، أو حصر الاهتمام بالاعتقادات القابلة للبلوغ فعلًا من البداية، أو التخطيط المباشر - بإجراء استشراف محدود من الاعتقاد الراهن بينما يصونه مرشِّح جسيمي، وإعادة التخطيط بعد كل إدراك.
الخلاصة
الـ POMDP عمليةٌ ماركوفية مضافًا إليها نموذج استشعار، وتُحال بالضبط إلى عملية ماركوفية على حالات الاعتقاد - مقايضةً حالةً منفصلة خفية بحالة متصلة مرصودة. وتلك المقايضة تجعل النظرية نظيفة والحساب صعبًا، فتتتبّع الأنظمة الواقعية الاعتقادَ بمرشِّح وتخطّط مسافةً قصيرة من موضعه الراهن.