التصرّف حين لا ترى الحالة

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

ويعرض هذا المقال ما يحلّ محلّه، في عالم صغير بما يكفي لأن يكون كل عدد فيه قابلًا للحساب المضبوط.

أ. إضافة واحدة

للعملية الماركوفية جزئية الرصد كل ما للعملية الماركوفية - نموذج انتقال وأفعال ومكافآت - مضافًا إليه نموذج استشعار ‎$P(e \mid s)$‎: أي احتمال إدراك الشاهد $e$ في الحالة $s$.

والنتيجة فورية. فالسياسة ‎$\pi(s)$‎ تقتضي مراجعة الحالة، والعميل لا يستطيع. والأسوأ أن الفعل الأمثل لم يعد يتوقف على موضع العميل وحده بل على مقدار ما يعرفه: فعميلان في الحالة نفسها، أحدهما متيقن والآخر حائر، ينبغي أن يتصرفا في الغالب تصرفين مختلفين.

ب. حالة الاعتقاد

والبديل هو التوزيع على الحالات المتسق مع كل ما فُعل وأُدرك: حالة الاعتقاد $b$، حيث ‎$b(s)$‎ احتمال الكون في $s$.

وخاصيتان تجعلانها الشيء الصحيح. فهي مرصودة للعميل دائمًا - إذ تلخّص تاريخ العميل لا العالم - فتكون ‎$\pi(b)$‎ قابلة للتنفيذ حيث لا تكون ‎$\pi(s)$‎ كذلك. وهي إحصاءة كافية: فلأن الانتقالات والإدراكات ماركوفية، يكون كل ما يقوله الماضي عن المستقبل موجودًا سلفًا في التوزيع الراهن، فيمكن طرح التاريخ.

وتُصان بعَودية واحدة:

$$b'(s') = \alpha \; P(e \mid s') \sum_{s} P(s' \mid s, a) \, b(s) .$$

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

ج. عالم صغير بما يكفي لرؤيته

حالتان، 0 و1، مع ‎$R(0) = 0$‎ و‎$R(1) = 1$‎. والاستمرار يبقي الحالة باحتمال 0.9، والتبديل يغيّرها باحتمال 0.9. والمستشعر يصيب باحتمال 0.6. والاعتقاد عدد واحد، ‎$b(1)$‎، فيكون فضاء الاعتقادات كله ‎$[0, 1]$‎.

من ‎$b(1) = 1/2$‎، كل زوج فعل–إدراك:

لم يُحدث الفعل فرقًا. فمن اعتقاد منتظم يترك الاستمرار والتبديل التنبؤَ منتظمًا - إذ يستمر أحدهما بـ0.9 ويبدّل الآخر بـ0.9، وهما من ‎50/50‎ شيء واحد - فيقوم الإدراك بالعمل كله. وذلك يفصل الوظيفتين اللتين يؤديهما الفعل في POMDP: تغيير العالم، وتغيير ما تعرفه عنه. وهنا تتلاشى الأولى ولا تظهر إلا الثانية.

د. سقف اليقين

فقدُ الثقة أيسر من كسبها. فاعتقاد قدره 0.99 يستمرّ ثم يلقى إدراكًا مناقضًا يهبط إلى ‎$446/527 = 0.846300$‎، ومعظم ذلك من تسريب «ابقَ»، الذي ينزل وحده بـ0.99 إلى تنبؤ قدره 0.892. وفي الاتجاه الآخر، بالاستمرار ورؤية الإدراك 1 مرارًا من ‎1/2‎:

$$0.600, \; 0.674, \; 0.727, \; 0.762, \; 0.786, \; 0.801, \; 0.811, \; 0.817, \ldots$$

وهو لا يبلغ 1. فالتكرار يتقارب إلى ‎$0.827934423$‎، وحلّ معادلة النقطة الثابتة رمزيًا يعطي

$$b^{*} = \frac{3 + \sqrt{105}}{16} = 0.827934 .$$

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

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

في ما يلي فضاء الاعتقاد كلّه، أي الفترة، والاعتقاد عليه نقطةٌ واحدة. اضغط «ابقَ، ورأيتُ 1» وواصِل الضغط: تتقلّص الخطوات أمام عينيك، وينحني الصعود نحو الخط المتقطّع ثم يقف عنده. ثم اضغط «ابقَ، ورأيتُ 0» مرة واحدة من قرب السقف: قراءة واحدة من مستشعر يخطئ 40٪ من الوقت تكلّف أكثر مما كسبه تأكيدان. وهذه اللاتماثلية ليست طرافةً في هذه الأرقام، بل هي ما يفعله الدليل المناقض دائمًا باعتقاد واثق.

هـ. الإحالة

وهنا العائد. تُحدَّث الاعتقادات تحديثًا حتميًا من الفعل والإدراك، واحتمال كل إدراك قابل للحساب، فيمكننا تعريف عملية ماركوفية حالاتها هي الاعتقادات - والسياسة المثلى لها مثلى لـ POMDP. والإحالة مضبوطة.

والفاتورة: لتلك العملية فضاء حالات متصل. ففي عالم الشبكة ‎4×3‎ ذي الإحدى عشرة حالة يكون الاعتقاد نقطةً في متصل ذي عشرة أبعاد (أحد عشر احتمالًا مجموعها واحد). ولا تعدّد أي خوارزمية ماركوفية معيارية ذلك.

والتعويض: أن الفعل، إذ يحرّك الاعتقاد لا العالم فحسب، يُقدَّر جزئيًا بما ينتجه من معلومات. فتكفّ قيمة المعلومات عن كونها حسابًا منفصلًا وتصير جزءًا من القرار العادي.

و. لماذا تكون دالة القيمة قابلة للحساب مبدئيًا

ثبّت خطة شرطية - فعلًا أول، ثم ما يُفعَل بعد كل إدراك، إلى عمق ما. وهي لا تتخذ قرارات في الطريق، فتكون منفعتها المتوقَّعة في الحالة الحقيقية $s$ عددًا. اجمعها في ‎$\alpha_p$‎، فيكون

$$U_p(b) = \sum_s b(s) \, \alpha_p(s)$$

جداءً داخليًا: خطيًا في $b$، أي مستوى فائقًا. وتأخذ دالة القيمة المثلى أفضل خطة عند كل اعتقاد، فهي قيمة عظمى لمستويات فائقة - خطية بالقطع ومحدّبة. والتحدّب يقول شيئًا: فنقاطه الدنيا هي اعتقادات أشدّ عدم يقين، فعدم اليقين هو ما يكلّف.

ولخطط الخطوة الواحدة بـ‎$\gamma = 1$‎:

$$\alpha_{[\text{Stay}]} = (0.1,\, 1.9), \qquad \alpha_{[\text{Go}]} = (0.9,\, 1.1),$$

متقاطعتين عند ‎$b(1) = 1/2$‎ حيث تساويان 1 بالضبط. بدّل تحته واستمرّ فوقه - السياسة الحدسية، واصلةً حسابًا بنقطة تحوّل مثبَّتة تمامًا.

وخطط الخطوتين ‎$2 \times 2 \times 2 = 8$‎، واكتساح مجال الاعتقادات يُظهر أن أربعًا فقط تعلو الغلاف: ‎$(0.28, 2.72)$‎ و‎$(0.68, 2.48)$‎ و‎$(1.48, 1.68)$‎ و‎$(1.72, 1.28)$‎. أما الأربع الأخرى فتحته في كل موضع، فحذفها لا يغيّر ‎$U(b)$‎ في أي مكان.

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

ز. لماذا لا تكون كذلك عمليًا

خطط العمق $d$ عددها ‎$|A|^{(|E|^{d}-1)/(|E|-1)}$‎:

أسّيٌّ مضاعف، في أصغر POMDP مثيرة للاهتمام على الإطلاق. وتشذيب الخطط المهيمَن عليها ضروري - وغير كافٍ. فبإجراء التكرار المضبوط على القيم بـ‎$\gamma = 0.9$‎ وحفظ المتجهات التي تعلو الغلاف فقط، تنمو المجموعة الناجية مسحًا بعد مسح:

$$2, \; 4, \; 8, \; 16, \; 30, \; 52, \; 88 .$$

وهي لا تنهار أبدًا، لأن دالة القيمة المضبوطة تكتسب فعلًا مزيدًا من القطع الخطية كلما طال الأفق. فالخوارزمية صحيحة؛ لكنها ببساطة لا تنتهي.

ح. قطّع، ثم تحقّق بالتنفيذ

فضاء الاعتقادات هنا مجال، فضع عليه شبكة وأجرِ تكرارًا عاديًا على القيم، موزّعًا كل اعتقاد خلف بين جارتيه. ويُبقي ذلك الاستيفاء التحديثَ تقلّصيًا فيتقارب - في 281 مسحًا عند 2001 نقطة:

$$U(0) = 6.822940, \quad U(0.5) = 5.886486, \quad U(1) = 6.822940 .$$

أدنى ما يكون في المنتصف: فمعرفة موضعك تساوي هنا ‎$0.936454$‎. والطرفان متساويان، وذلك يستحق التحقق لا الافتراض - فمن الحالة 0 اليقينية يبدّل العميل فيبلغ الحالة 1 باحتمال 0.9؛ ومن الحالة 1 اليقينية يستمر فيبقى باحتمال 0.9. الموضع نفسه في الخطوة التالية، والقيمة نفسها.

وتنقيح الشبكة يعطي 6.822981 و6.822942 و6.822940 عند 201 و801 و2001 نقطة. لكن ذلك لا يُظهر إلا تقارب التقريب إلى شيء ما - فمخطط الاستيفاء قد يتقارب بهدوء إلى جواب متحيّز ويبدو تمامًا هكذا.

فشغّل السياسة إذن. على 30,000 مسار بأفق 160:

تنقيح الشبكة يسأل هل التقريب متسق مع نفسه. والتنفيذ يسأل هل السياسة تكسب ذلك القدر فعلًا. وهو وحده ما كان يمكن أن يلتقط تحيّزًا استيفائيًا منهجيًا، وهو المهمّ.

نصفا المسألة في الشكل أدناه. عدد الخطط مطبوع بأعداد صحيحة مضبوطة، لأن الجواب عند العمق ستّة هو 2^63، ومع أن العدد العشري العائم يخزّنه تمامًا، فإن JavaScript تطبعه 9223372036854776000، وهو رقم لا تحويه هذه الصفحة. أما دالّة القيمة إلى جانبه فمحلولة على الشبكة، والمزلاج يمشي بك في جدول التنقيح: 6.822981 عند 201 نقطة، و6.822942 عند 801، و6.822940 عند 2001، في 281 مسحة. وراقب الطرفين يبقيان متساويين والوسط يهبط: تلك هي التحدّب.

أهم النقاط

• الـ POMDP عمليةٌ ماركوفية مضافًا إليها نموذج استشعار، وتلك الإضافة وحدها تعني أن السياسة لا يمكن أن تُفهرَس بالحالة.
• وتحلّ حالة الاعتقاد محلّها: مرصودة دائمًا، وإحصاءة كافية للتاريخ كله.
• والمستشعر المشوَّش يُشبع الاعتقاد بدل أن يحسمه - هنا عند ‎$(3 + \sqrt{105})/16$‎ بالضبط - فيكون التخطيط تحت عدم اليقين دائمًا.
• والإحالة إلى عملية ماركوفية على الاعتقادات مضبوطة، وتكلّف فضاء حالات متصلًا.
• ودالة القيمة خطية بالقطع ومحدّبة، وهو ما يجعل التكرار المضبوط ممكنًا وغير عملي، قياسًا.
• قرّب، ثم تحقّق بتنفيذ السياسة لا بتنقيح التقريب.

ما التالي

افترضت كل الطرائق هنا أن النماذج معلومة. أما تعلّم نموذجَي الانتقال والاستشعار من التجربة أثناء العمل بهما فهو المسألة نفسها مع إخفاء المعالم أيضًا - وتتبيّن خوارزمية EM أنها الأداة.