من loop لـ model
الدرس 14.1 وصف التفاعل: state، وبعدين action، وبعدين reward، وبعدين state جاية، وهكذا. والوصف ده كفاية عشان تتكلّم عن المشكلة ومش كفاية خالص عشان تحلّها. فعشان تحسب أي حاجة لازم تقول بدقة الـ environment إيه، والإجابة المعتادة هي الـ Markov decision process (عملية قرار ماركوف) — أو MDP. ودي الصياغة اللي المجال كله اتبنى عليها، وساتون وبارتو (2018) مخصّصين لها الفصل التالت من كتابهم.
وثمرة الصياغة دي معادلة recursive واحدة، راجعة لبلمان (1957)، بتربط قيمة المكان اللي إنت فيه بقيمة الأماكن اللي ممكن تتنقل لها. وأول ما يبقى معاك المعادلة دي تقدر تحل المشاكل الصغيّرة حل مظبوط، وكل طريقة في الدرسين 14.3 و14.4 هي طريق لتقريب حلّها لما المشكلة متبقاش صغيّرة.
الـ Markov property، وبتشيل إيه من الحساب
الـ state بيبقى عندها الـ Markov property (خاصية ماركوف) لو بتلخّص الماضي تلخيص كفاية لدرجة إن الماضي مبيزوّدش حاجة. وبالصيغة الرسمية: احتمال الـ state والـ reward الجايين بيعتمد على الـ state والـ action الحاليين بس — مش على الطريق اللي وصّلك هناك.
ويستاهل تقول صراحةً الخاصية دي بتشيل إيه من الحساب. وضعية الشطرنج Markov: الرقعة، ومين عليه الدور، وحقوق التبييت والـ en passant، بيحدّدوا كل اللي ممكن ييجي بعد كده، وسلسلة النقلات اللي طلّعت الوضعية مالهاش أهمية. أما frame فيديو واحد لكورة بتتحرّك فهو مش Markov: مفيهوش سرعة الكورة، فميقدرش يتنبأ بالـ frame الجاي. وتحليل دم واحد لدكتور مش Markov برضه، لأن الاتجاه على مدار السنة اللي فاتت ناقص.
والحل في أغلب الأحوال إنك تعيد تعريف الـ state مش إنك تسيب الإطار: رصّ آخر كام frame، أو زوّد السرعة، أو زوّد الملخّص الجاري. وده هندسة، وليها تمن — كل كمية بتزوّدها بتضاعف حجم فضاء الـ states. وبلمان سمّى الكبر ده الـ curse of dimensionality (لعنة الأبعاد)، وهو سبب إن الطرق الـ tabular بتخلص منها المساحة، وسبب إن الدرس 14.3 بيخلص بإنه يبدّل الجدول بـ neural network.
ساعات مفيش أي هندسة بتخلّي الرصد Markov، لأن المعلومة مش متاحة أصلًا — روبوت بكاميرا محدودة مبيشوفش اللي وراه. والحالة دي ليها اسمها الخاص، الـ partially observable MDP (عملية قرار ماركوف جزئية الرصد)، وهي أصعب بجد: لأن الـ agent لازم يحتفظ بـ belief موزّع على الـ states بدل state واحدة. وكل اللي في الوحدة دي بيفترض الـ state متشافة بالكامل، ودي نقطة البداية المعتادة، وفيها معادلات بلمان بتصح زي ما هي مكتوبة.
الخمس أجزاء
الـ Markov decision process خمس حاجات مع بعض، وتسميتهم هي أغلب شغل صياغة المشكلة.
الـ states S. مجموعة المواقف اللي الـ agent ممكن يبقى فيها. وشوية منها ممكن يبقوا terminal، فبينهوا الـ episode.
الـ actions A. اللي الـ agent مسموح له يعمله. وكتير ده بيعتمد على الـ state، فبيتكتب A(s).
الـ transition probabilities p(s′, r | s, a). الـ dynamics اللي فوق. والـ environments الحتمية هي الحالة الخاصة اللي الاحتمال كله فيها بيقع على نتيجة واحدة.
الـ reward function r. الـ reward المتوقّعة لانتقال معيّن، وبتتطلع من p بالمتوسط على r. وهي خاصية الـ environment مش خاصية الـ agent، وتحذير الدرس 14.1 من الـ reward hacking هو تحذير من طريقة كتابة الجزء ده.
الـ discount factor γ (عامل الخصم). رقم بيحقق 0 ≤ γ ≤ 1 بيقول reward متأخرة خطوة واحدة تساوي قد إيه بالنسبة لـ reward دلوقتي.
الـ return، وليه المستقبل بيتخصم
الـ agent مبيكبّرش الـ reward الجاية، بيكبّر كل اللي بعدها، والمجموع ده محتاج اسم وتعريف. الـ return (العائد) Gt هو المجموع المخصوم لكل الـ rewards الجاية من الزمن t ورايح.
وللخصم تلات أسباب، أولهم بس رياضي. لو التفاعل عمره ما خلص، مجموع الـ rewards من غير خصم ممكن يبقى لا نهائي، واللانهايات مبتتقارنش — فـ policyين الاتنين بيلمّوا لا نهاية مينفعش تفرّق بينهم. ومع γ < 1 وrewards محدودة الـ geometric series بتعمل convergence، فكل policy بتاخد درجة محدودة والمقارنة بتبقى ليها معنى.
وتانيًا، الأقرب أحسن بجد في أغلب المشاكل الواقعية: الفلوس دلوقتي أحسن من الفلوس بعدين، والروبوت اللي بيوصل للهدف في عشر خطوات أحسن من اللي بيوصل في ألف. وتالتًا، γ بيشفّر عدم اليقين في المستقبل البعيد — فحق في reward بعد مية خطوة يساوي أقل، لأن حاجات كتير ممكن تقف في الطريق.
والطرفين مفيدين في الفهم. عند γ = 0 الـ return بيبقى Rt+1 بس والـ agent بيبقى قصير النظر خالص: بيكبّر الخطوة الجاية وهيمشي مطمّن لحافة جُرف في الخطوة اللي بعدها. وكل ما γ يقرّب من 1 الـ agent بيبقى أبعد نظرًا وreturns الـ policies المختلفة بتبقى أصعب تتفرّق، وده بيبطّأ التعلّم. والقيم المعتادة عمليًا بين 0.9 و0.99. وγ = 1 مقبول بس في المهام الـ episodic المضمون إنها تخلص، اللي المجموع فيها محدود لأن ليها نهاية.
الـ policy، وقيمة الـ state، وقيمة الـ action
الـ policy π(a | s) هي قاعدة سلوك الـ agent: احتمال اختيار الـ action a في الـ state s. وكل اللي الـ agent بيتحاسب عليه طالع من الـ policy بتاعته، لأن الـ policy مع الـ dynamics p بيحدّدوا التوزيع على الـ trajectories، وبالتالي التوزيع على الـ returns.
وfunctionين بيحوّلوا التوزيع ده لأرقام تقدر تتصرّف على أساسها. الـ state-value function (دالة قيمة الحالة) بتجاوب على: لو بدأت من هنا ومشيت ورا π، المفروض أتوقّع return قد إيه؟
أما الـ action-value function (دالة قيمة الفعل) فبتسأل سؤال مختلف شوية وأنفع بكتير: إيه اللي يحصل لو خدت action معيّن هنا الأول، وبعدين مشيت ورا π؟
الـ Bellman expectation equation
هنا الفكرة اللي الوحدة كلها قايمة عليها. الـ return من state بيتقسم للـ reward الجاية على طول زائد الـ return المخصوم من المكان اللي بتنزل فيه. خد التوقّع للناحيتين والـ value function بتبقى recursive: V بتظهر في الناحيتين من تعريفها.
فقيمة الـ policy مش حاجة لازم تعمل لها simulation ألف episode عشان تكتشفها. دي حل نظام معادلات تقدر تكتبه من الـ model. وده عائد ضخم لافتراض واحد عن الـ states.
الـ optimality: بدّل المتوسط بحد أقصى
تقييم policy معيّنة مش هو الهدف؛ الهدف إنك تلاقي أحسن واحدة. والـ optimal policy (السياسة المثلى) π* هي اللي قيمتها مش أقل من قيمة أي policy تانية في كل state. ولكل MDP محدودة فيه optimal policy واحدة على الأقل، وكل الـ optimal policies بيشتركوا في نفس الـ value function V*.
ومعادلة بلمان للـ optimality بتختلف عن معادلة التوقّع في مكان واحد بالظبط. الـ agent الـ optimal مبياخدش متوسط اللي الـ policy بتاعته ممكن تعمله — بياخد أحسن action متاح. فالمجموع اللي بره على π بيبقى حد أقصى على a.
وفيه نتيجة تستاهل تتقال لوحدها، لأنها اللي بتخلّي الطريقة كلها عملية: أول ما يبقى معاك V*، السلوك الـ optimal مش محتاج أي بحث. بص خطوة واحدة لقدّام، وخد الـ action اللي بيكبّر القوس اللي فوق، وتبقى اتصرّفت تصرّف optimal على أفق لا نهائي. فكل التخطيط البعيد المدى اتضغط في الـ value function.
حلّها لما الـ model يبقى معروف
لو p معروفة، معادلة بلمان للـ optimality ينفع تتحل بـ الـ dynamic programming (البرمجة الدينامية) — طريقة بلمان (1957)، وموضوع الفصل الرابع في ساتون وبارتو. والحيلة إنك تبطّل تعاملها كمعادلة بتتحل وتعاملها كـ assignment بيتكرّر.
اشتغلها بإيدك على ممر من أربع خلايا. الـ states هي 1 و2 و3 وهدف terminal G، على خط واحد. والـ actionين شمال ويمين، والاتنين حتميين؛ والخبط في الحيطة الشمال من الـ state 1 بيخلّيك في الـ state 1. والحركة يمين من الـ state 3 بتوصل لـ G، فبتدفع reward 1 وبتنهي الـ episode. وكل انتقال تاني بيدفع 0. اظبط γ = 0.9 وV0 = 0 في كل حتة.
الـ pass 1. الـ state 3: يمين بيدّي 1 + 0.9 × 0 = 1، وشمال بيدّي 0 + 0.9 × 0 = 0، فـ V1(3) = 1. والـ statesين 1 و2 مبيشوفوش غير أصفار في كل اتجاه، فبيفضلوا عند 0.
الـ pass 2. الـ state 2: يمين بيدّي 0 + 0.9 × V1(3) = 0.9، فـ V2(2) = 0.9. والـ state 3 بتفضل عند 1. والـ state 1 لسه 0.
الـ pass 3. الـ state 1: يمين بيدّي 0 + 0.9 × 0.9 = 0.81، فـ V3(1) = 0.81. ومفيش حاجة بتتغيّر في الـ pass اللي بعده، فدي V*: 0.81 و0.9 و1.
اقرا الإجابة. القيمة بتقل مع البعد عن الهدف بعامل γ لكل خطوة، وده بالظبط معنى γ. والتصرّف بشكل greedy بالنسبة للأرقام دي بيدّي «روح يمين دايمًا» — ودي الـ optimal policy، طالعة من غير أي بحث.
والبديل هو الـ policy iteration، اللي بيبدّل بين خطوتين بدل ما يدمجهم. الـ policy evaluation بيحل معادلة بلمان للتوقّع للـ policy الحالية، فبيدّي Vπ مظبوطة. وبعدين الـ policy improvement بيخلّي الـ policy greedy بالنسبة لـ Vπ دي. كرّر لحد ما خطوة التحسين متغيّرش حاجة، وساعتها الـ policy بتحقق معادلة الـ optimality وبتبقى optimal.
ابدأ من الـ policy الوحشة بقصد «روح شمال دايمًا». الـ evaluation بيدّي V = 0 في كل state، لأن الهدف عمره ما بيتوصل. والـ improvement بيلاقي إن الحركة يمين في الـ state 3 تساوي 1 قصاد 0، فبيقلب الـ state 3 ليمين.
قيّم تاني: V(3) = 1 وV(2) = 0 وV(1) = 0. والـ improvement بيلاقي دلوقتي إن الـ state 2 تساوي 0.9 يمين قصاد 0 شمال، فبيقلبها. قيّم: V(3) = 1 وV(2) = 0.9 وV(1) = 0. والـ improvement بيقلب الـ state 1، لأن 0.9 × 0.9 = 0.81 أكبر من 0. قيّم: 0.81 و0.9 و1 — والـ improvement اللي بعده مبيغيّرش حاجة، فالـ policy optimal.
وخد بالك اللي حصل: الـ policy بقت optimal بعد تلات improvements مع إن القيم كانت لسه بتتصقل. وده الـ pattern المعتاد، وهو سبب إن الـ policy iteration محتاج دورات قليلة بشكل يدهش. الـ value iteration أرخص في الـ pass الواحد لأنه مبيستنّاش الـ evaluation يخلص؛ والـ policy iteration بيعمل convergence في دورات أقل لأن كل دورة بتستخدم value function مظبوطة. والاتنين dynamic programming، والاتنين محتاجين p.
وده بياخد الدرس لحدّه هو. كل اللي فات محتاج تعرف الـ transition probabilities، وهي في أغلب المشاكل الواقعية مش معروفة: محدش بيسلّمك dynamics مخزن أو سوق أو مستخدم. والمكوّن الواحد الناقص ده هو موضوع الدرس 14.3 — تعلّم Q من الخبرة لوحدها، من غير أي model للـ environment خالص.
- الـ Markov decision process هي الصياغة الرسمية لمشكلة الـ reinforcement learning: states، وactions، وtransition probabilities p(s′, r | s, a)، وreward function، وdiscount factor γ بيحقق 0 ≤ γ ≤ 1.
- الـ Markov property بتقول إن الـ state والـ action الحاليين بيحدّدوا توزيع اللي جاي بعدهم، من غير أي اعتماد على التاريخ. والسرعة والاتجاهات ورصّ الـ frames موجودين عشان يحقّقوا ده.
- الـ return هو المجموع المخصوم للـ rewards الجاية. والخصم بيخلّي المهام الـ continuing محدودة، وبيفضّل الـ reward الأقرب، وبيتحوّط للمستقبل البعيد. وγ = 1 آمن بس لما الـ episodes تخلص.
- Vπ(s) هي الـ return المتوقّع من s تحت π؛ وQπ(s, a) هي الـ return المتوقّع بعد ما تلتزم بـ a الأول. وQ هي الشكل اللي تقدر تتصرّف بيه من غير model.
- الـ Bellman expectation equation بتخلّي V recursive: الـ reward الفورية زائد القيمة المخصومة للـ state الجاية، بالمتوسط على الـ policy وعلى الـ environment.
- الـ Bellman optimality equation بتبدّل المتوسط على الـ actions بحد أقصى. وهي مش خطّية، وحلّها V* بيخلّي السلوك الـ optimal بصّة خطوة واحدة لقدّام.
- الـ value iteration بيعدّي بتحديث الـ optimality لحد الـ convergence؛ والـ policy iteration بيبدّل بين evaluation مظبوط وimprovement greedy. والاتنين dynamic programming بتاع بلمان (1957)، والاتنين محتاجين p.
- الـ curse of dimensionality بتاعة بلمان هي سبب التمن الحقيقي لتكبير الـ state عشان ترجّع الـ Markov property، وسبب إن الطرق الـ tabular في الآخر بتتراجع قدّام الـ function approximation.