From Optimal Actions to World Models: Identifiability of Transition Kernels in Discounted MDPs

ملخص تقني: قابلية التحديد لنواة الانتقال في عمليات ماركوف لاتخاذ القرار (MDP) المخصمة

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

تقارن الدراسة ثلاث فئات متميزة من المكافآت، والتي تختبر الديناميكيات بطرق مختلفة:

1. مكافآت الحالة: $r(s)$، تعتمد فقط على الحالة الحالية.
2. مكافآت الحالة-الفعل: $r(s, a)$، تعتمد على الحالة والفعل الحاليين.
3. المكافآت المعتمدة على الانتقال: $r(s, a, s')$، تعتمد على الحالة، والفعل، والحالة التالية الناتجة.

ويعرف البحث ثلاثة مفاهيم للتكافؤ: $P \equiv_{tr} Q$ (غير قابلتين للتمييز تحت مكافآت الانتقال)، و $P \equiv_{sa} Q$ (غير قابلتين للتمييز تحت مكافآت الحالة-الفعل)، و $P \equiv_{s} Q$ (غير قابلتين للتمييز تحت مكافآت الحالة).

المنهجية
يعتمد التحليل على الخصائص الهيكلية لمعادلات بلمان المثلى والعلاقة بين دالات القيمة ونواة الانتقال.

• مكافآت الحالة-الفعل: يقوم المؤلف ببناء عائلة محددة من المكافآت، $r^P_v(s, a) = v(s) - \gamma P_{s,a}v$، والتي تجعل كل فعل أمثل لقيمة متجهة $v$ معينة. ومن خلال مقارنة معادلات تقييم السياسة تحت النواتين $P$ و $Q$ لهذه المكافآت، تستنتج الورقة شرطاً ضرورياً وكافياً للتكافؤ. ويتضمن ذلك تحديد مصفوفة فريدة قابلة للعكس $L$ تربط بين دالات القيمة للنواتين.
• المكافآت المعتمدة على الانتقال: تستغل المنهجية القدرة على عزل صفوف انتقال محددة. إذا كانت للحالة عدة أفعال، يمكن تصميم مكافأة معتمدة على الانتقال بحيث تكون قيمتها المتوقعة صفراً تحت صف انتقال معين وغير صفرية تحت صف آخر، مما يؤدي إلى تمييزها. أما بالنسبة للحالات ذات الفعل الواحد، فيعتمد التحليل على ما إذا كان صف الانتقال المحدد يؤثر على مثالية الأفعال في حالات أخرى من فضاء الحالات.
• مكافآت الحالة: يحدد التحليل التكافؤ من خلال فحص "مناطق السياسة" $R_P(\pi)$، المعرفة بأنها مجموعة مكافآت الحالة التي تكون عندها سياسة حتمية $\pi$ مثلى. وتكون النواتان متكافئتين إذا وفقط إذا كانت هذه المناطق متطابقة لجميع السياسات الحتمية.

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

1. تكافؤ الحالة-الفعل ($P \equiv_{sa} Q$):
   تنتج النواتان $P$ و $Q$ نفس الأفعال المثلى لكل مكافأة حالة-فعل إذا وفقط إذا وجدت مصفوفة فريدة قابلة للعكس $L$ (تحقق $L\mathbf{1} = \mathbf{1}$) بحيث:
   $$Q_{s,a} = \left( P_{s,a} + \frac{1}{\gamma} e_s^T (L - I) \right) L^{-1}$$
   وهذا يعني أن ميزة أي فعل بالنسبة لسياسة ما يتم الحفاظ عليها تحت هذا التحويل. وبالقرب من نواة ذات مدخلات موجبة تماماً، تشكل مجموعة النواوات غير القابلة للتمييز مجمعاً أملساً (smooth manifold) ذا بُعد $n(n-1)$، حيث $n$ هو عدد الحالات. وهذا يمثل مجموعة جزئية صارمة من فضاء النواة المحيط، مما يعني أنه بينما لا يتم تحديد نواة الانتقال بشكل فريد، فإن الغموض يظل محصوراً في عائلة محددة ذات بُعد أقل. وتظل هذه النتيجة قائمة حتى لو تم تقييد البيانات بالمكافآت التي تملك فعلاً فريداً أمثلاً عند كل حالة.

2. التكافؤ المعتمد على الانتقال ($P \equiv_{tr} Q$):
   توفر المكافآت المعتمدة على الانتقال معلومات أكثر بكثير.

• عند أي حالة تحتوي على فعلين على الأقل، يتم تحديد صف الانتقال بشكل فريد.
• في الحالات ذات الفعل الواحد، يتم تحديد الصف ما لم يؤثر صف الانتقال المحدد على مثالية الأفعال في حالات أخرى (وهو شرط يتحقق فقط في مجموعة قياس صِفري من النواوات الموجبة تماماً).
• وبناءً على ذلك، إذا احتوت عملية ماركوف (MDP) على حالة واحدة على الأقل بها خيار حقيقي (أفعال متعددة)، فإن كل نواة موجبة تماماً تقريباً يتم تحديدها بشكل فريد بواسطة المكافآت المعتمدة على الانتقال.

3. تكافؤ مكافأة الحالة ($P \equiv_{s} Q$):
   توفر مكافآت الحالة أقل قدر من المعلومات. تكون النواتان متكافئتين إذا وفقط إذا اشتركتا في نفس مجموعة السياسات الحتمية المثلى لكل مكافأة حالة. وهذا الشرط يكافئ تساوي مناطق السياسة $R_P(\pi) = R_Q(\pi)$ لجميع السياسات $\pi$. وهذا التكافؤ أضعف بوضوح من تكافؤ الحالة-الفعل؛ حيث يمكن لنواوات متميزة أن تكون غير قابلة للتمييز تحت مكافآت الحالة بينما يمكن تمييزها تحت مكافآت الحالة-الفعل.

4. تسلسل قابلية التحديد:
   تثبت الورقة وجود تسلسل هرمي صارم للتكافؤ:
   $$P \equiv_{tr} Q \implies P \equiv_{sa} Q \implies P \equiv_{s} Q$$
   ولا يمكن عكس أي من هذه الاستلزامات. إن السماح للمكافأة بالاعتماد على مكونات أكثر من الانتقال (تحديداً الحالة التالية) يزيد بشكل صارخ من القدرة على التمييز بين نماذج الانتقال المختلفة.

الأهمية والادعاءات
تدعي الورقة أنها تحل مسألة مدى إمكانية استعادة القدر الكافي من ديناميكيات الانتقال من السلوك الأمثل وحده. وهي توضح أن:

• الأفعال المثلى غير كافية للاستعادة الكاملة: حتى مع معرفة الأفعال المثلى لجميع المكافآت، فإن نواة الانتقال لا تُحدد بشكل فريد عموماً عندما تعتمد المكافآت فقط على الحالات أو الحالات-الأفعال.
• توجد قيود هيكلية: بالنسبة لمكافآت الحالة-الفعل، فإن الغموض ليس عشوائياً؛ بل يتم توصيفه بدقة عبر تحويل مصفوفي يحافظ على مقارنات الأفعال (المزايا/advantages) عبر جميع السياسات.
• بنية المكافأة تملي قابلية الاستعادة: شكل المكافأة أمر حاسم. يمكن للمكافآت المعتمدة على الانتقال استعادة النواة بالكامل تقريباً، بينما قد تترك مكافآت الحالة اختلافات هيكلية جوهرية مخفية.
• التمييز بين اتخاذ القرار والتنبؤ: تبرز النتائج أن النموذج قد يكون كافياً لإعادة إنتاج القرارات المثلى (إعادة إنتاج السياسة) دون أن يكون كافياً للتنبؤ بالانتقالات، أو محاكاة السيناريوهات المضادة للواقع، أو النقل إلى فئات مكافآت غير مرئية.

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